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*logN,n是总数据条数),而且个别N都不大,能够在内存中放下,无论数据量有多大,都不会波及内外存替换问题。

然而,SQL无奈形容下面这个计算过程,这时,咱们只能寄希望于数据库引擎是不是能本人优化。应用SPL就容易形容下面这个计算过程,从而实现高性能计算。

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

一、      数据筹备和环境

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

在一台Intel服务器上实现测试,2个Intel3014 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脚本执行测试:

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

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

3.        论断与剖析

惯例TopN测试工夫见下表:

测试后果(工夫单位:秒)

测试表明,Oracle比SPL还要更快一点,而SPL没有做全排序,这阐明Oracle在这种状况会主动优化。

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

三、      减少复杂度

对于最根本的TopN,Oracle很聪慧,即便写成了子查问也会优化。咱们上面减少问题的难度,改成分组后在每一组中做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脚本执行测试:

因为SPL把TopN看成是聚合计算,所以能够很容易放在分组汇总中,和全量聚合的写法简直是一样的。

3.        论断与剖析

测试后果(工夫单位:秒)

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

而SPL在这两种状况下的运算工夫差异不到2倍,基本上在同一数量级,合乎咱们之前的剖析,算法的劣势失去了充沛的体现。