性能优化技巧:TopN

TopN是常见的运算,用SQL写出来是这样(以Oracle为例):
       select * from (select * from T order by x desc) where rownum<=N
这个SQL的运算逻辑从其语句上看,要先做排序(Order by),然后再取出前N条。

我们知道,排序是个非常慢的动作,复杂度很高(n*logn),如果涉及数据量大到内存放不下,那还需要进行内外存数据交换,性能还会急剧下降。

而事实上,要计算TopN,我们能设计出不需要全排序的算法,只要保持一个大小为N的小集合,对数据集遍历一次,将遍历过的数据的前N名保存在这个小集合中,遍历到新一条数据,如果比当前的第N名还大,则插入进去并丢掉现在的第N名,如果比当前的第N名要小,则不做动作。

这样计算的复杂度要低很多(n*logNn是总数据条数),而且一般N都不大,可以在内存中放下,无论数据量有多大,都不会涉及内外存交换问题。

但是,SQL无法描述上面这个计算过程,这时,我们只能寄希望于数据库引擎是不是能自己优化。使用SPL就容易描述上面这个计算过程,从而实现高性能计算。

我们来测试一下看Oracle是不是会做这个优化,即用Oracle实现TopN后和SPL做同样运算相比。因为SPL能使用优化算法,如果Oracle的计算时间和SPL差不多,则说明它做了优化,如果差得很远,则可能是做了全排序。

 

一、      数据准备和环境

SPL脚本生成数据文件,数据共两列,第一列id是小于20亿的随机整数,第二列amount是不大于1千万的随机实数。数据记录为80亿行,生成的原始文本文件大小为169G。利用数据库提供的数据导入工具将此文件数据导入到Oracle的数据表topn中,同时也用此文件数据生成SPL组表文件topn.ctx

在一台Intel服务器上完成测试,2Intel3014 CPU,主频1.7G,共12核,内存64G。数据库表数据及SPL组表文件均存储在同一块SSD硬盘上。

我们刻意将数据量设计得比内存大,这样如果进行排序则会有内外存交换动作,性能下降会非常大,容易被观测到。

 

二、      常规TopN

取出topn表中amount最大的前100条。

1.        Oracle测试

查询用的SQL语句是:

select * from (

    select  /*+ parallel(4) */

    * from topn order by amount desc

) where rownum<=100;

说明:/*+ parallel(4) */ Oracle的并行查询语法,其中4是并行数。

 

2.        SPL测试

编写SPL脚本执行测试:


A


1

=now()

/记录时间

2

=4

/并行数

3

=file("/home/topn/topn.ctx").open()

/产生组表对象

4

=A3.cursor@m(id,amount;;A2).groups(;top(100;-amount))


5

=interval@s(A1,now())

/算出执行时间

SQL不同,SPLTopN看成是一种聚合运算,和sum/count这类运算一样,不同的只是TopN将返回一个集合,而sum/count返回的是单值。但它们的计算逻辑是一样的,都只需要对原数据集遍历一次,并且不涉及全排序。

A4格中的groups(;top(100;-amount)就是对全集做TopN聚合运算,计算出前100名。

 

3.        结论与分析

常规TopN测试时间见下表:

测试结果(时间单位:秒)

并行数

1

2

4

8

12

Oracle

1922

952

526

308

256

SPL组表

2641

1565

729

371

321

测试表明,OracleSPL还要更快一点,而SPL没有做全排序,这说明Oracle在这种情况会自动优化。

OracleSPL快也可以理解,因为Oracle是用C++开发的,而目前版本的SPL是用java开发的。C++java计算更快是正常的,而且这次测试读取了全部的两列数据,且数据随机无序,很难压缩,所以组表的列式存储也没有优势。

 

三、      增加复杂度

对于最基本的TopNOracle很聪明,即使写成了子查询也会优化。我们下面增加问题的难度,改成分组后在每一组中做TopN

具体运算设计为:按照id字段最后一位数字值进行分组,然后查询出每组中amount最大的前100条记录。id是个整数,这样也就只有10个分组,分组本身的计算量并不大,不过要对分组数据做TopN,整体计算复杂度略高了一些。如果没有全排序,总体运算时间应当比刚才的情况多,但还在同一数量级范围内。

1.        Oracle测试

查询用的SQL语句是:

select * from (

    select  /*+ parallel(2) */

    mod(id,10) as gid,amount,

    row_number()over (partition by mod(id,10) order by amount desc) rn

    from topn

) where rn <= 100;

SQL无法直接写出分组后取TopN的运算,只能借助窗口函数计算序号,语法中还是有排序(order by)的字样。

 

2.        SPL组表测试

编写SPL脚本执行测试:


A


1

=now()

/记录时间

2

=4

/并行数

3

=file("/home/topn/topn.ctx").open()

/产生组表对象

4

=A3.cursor@m(id,amount;;A2).groups@u(id%10:gid;top(100;-amount))


5

=interval@s(A1,now())

/算出执行时间

因为SPLTopN看成是聚合计算,所以可以很容易放在分组汇总中,和全量聚合的写法几乎是一样的。

 

3.        结论与分析

测试结果(时间单位:秒)

并行数

1

2

4

8

12

Oracle

41649

19602

9359

4627

3211

SPL组表

4380

2127

1007

465

349

增加难度后,Oracle比之前的简单情况慢了10倍还多,而且比SPL做同样运算也慢了近10倍。这说明Oracle在这种情况下很可能做了排序动作,情况复杂化之后,Oracle的优化引擎不起作用了。

SPL在这两种情况下的运算时间差别不到2倍,基本上在同一数量级,符合我们之前的分析,算法的优势得到了充分的体现。

 


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

以下是广告时间

对润乾产品感兴趣的小伙伴,一定要知道软件还能这样卖哟性价比还不过瘾? 欢迎加入好多乾计划。
这里可以低价购买软件产品,让已经亲民的价格更加便宜!
这里可以销售产品获取佣金,赚满钱包成为土豪不再是梦!
这里还可以推荐分享抢红包,每次都是好几块钱的巨款哟!
来吧,现在就加入,拿起手机扫码,开始乾包之旅



嗯,还不太了解好多乾?
猛戳这里
玩转好多乾