性能优化技巧:后半有序分组

一、  问题背景与适用场景

什么是后半有序?如果数据集T已经按字段ab有序,现在我们要将Tb排序或分组时,因为在a值相同的段内,b都是有序的,这种要排序或分组的字段在分段内有序的情况就称为后半有序。

我们知道,快速排序算法的原理就是一种递归的分段排序再归并的算法,对于后半有序这样的已经大体有序的数组,快速排序的速度已经能够很快。所以如果采用快速排序算法对Tb排序后,就可以使用《性能优化技巧:有序分组》中介绍的优化原理进行分组了。

SPL提供了后半有序分组方法,我们实例测试一下,并且与SPLOraclehash分组算法作对比。

 

二、  测试环境与任务

测试机有两个Intel2670 CPU,主频2.6G,共16核,内存64GSSD固态硬盘。在此机上安装虚拟机来测试,设置虚拟机为16核、8G内存。

在虚拟机上创建数据表sales,共四个字段:orderdatearea(字符串)salesman(字符串)amount(实数),生成数据记录10亿行。将此表数据导入Oracle数据库,同时用它生成集算器SPL组表来进行测试。

数据按orderdateareasalesman字段升序排列,要求查询出各地区各销售人员的销售总额,也就是按areasalesman进行分组,结果集总共有100万组。由于Oracle输出这么多行结果需要很长的时间,所以对分组结果再进行一次过滤,只输出销售总额小于471000元的订单,结果只有11条,输出就不占时间了。

 

三、  测试

1.  Oracle测试

编写查询测试SQL如下:

select * from (

       select   /*+ parallel(n)  */

              area, salesman, sum(amount) as amount

       from sales

       group by area, salesman

) where amount<471000;

其中/*+ parallel(n) */ 用于并行测试,n为并行数。

 

2.  SPL后半有序分组

编写SPL脚本如下:


A

1

=now()

2

=file("/home/ctx/sales.ctx").open().cursor@m(area,salesman,amount;;1)

3

=A2.groups@h(area,salesman;sum(amount):amount).select(amount<471000)

4

=interval@s(A1,now())

groups分组时加选项@h就表示分组字段是后半有序(分段有序)的,让SPL先用快速排序算法对分组字段排序,之后再采用有序分组来优化。

需要说明的是,后半有序分组都是在内存中完成的,要求内存中能装下分组后的结果集,多路并行时要求内存能同时放下n个结果集(n为并行路数)

 

3.  SPL  HASH分组

前述SPL脚本中去掉groups的选项@h,就是采用HASH分组了。

4.  测试结果

测试结果如下,单位()

并行数

1

2

4

Oracle

387

195

104

SPL (HASH)

405

208

121

SPL (后半有序)

252

142

83

从测试结果看,SPL后半有序分组的运行时间比使用HASH分组的SPLOracle都要快不少,效率提高50%以上,性能提升比较明显。Java写的SPL常规分组比C语言写的Oracle略慢也是正常现象(测试中使用了所有列,SPL的列存优势没有效果)。

 

 

 


系列性能优化技巧:
性能优化技巧:遍历复用
性能优化技巧:TopN
性能优化技巧:预关联
性能优化技巧:部分预关联
性能优化技巧:外键序号化
性能优化技巧:维表过滤或计算时的关联
性能优化技巧:有序归并
性能优化技巧:有序定位关联提速主子关联后的过滤
性能优化技巧:附表
性能优化技巧:大维表查找
性能优化技巧:单边分堆
性能优化技巧:有序分组
性能优化技巧:后半有序分组
性能优化技巧:前半有序时的排序