性能优化技巧：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*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脚本执行测试：
A1=now()/记录时间2=4/并行数3=file("/home/topn/topn.ctx").create()/产生组表对象4=A3.cursor@m(id,amount;;A2).groups(;top(100;-amount))5=interval@s(A1,now())/算出执行时间与SQL不同，SPL把TopN看成是一种聚合运算，和sum/count这类运算一样，不同的只是TopN将返回一个集合，而sum/count返回的是单值。但它们的计算逻辑是一样的，都只需要对原数据集遍历一次，并且不涉及全排序。A4格中的groups(;top(100;-amount)就是对全集做TopN聚合运算，计算出前100名。3. 结论与分析常规TopN测试时间见下表：测试结果（时间单位：秒）并行数124812Oracle1922952526308256SPL组表26411565729371321测试表明，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) rnfrom topn) where rn <= 100;SQL无法直接写出分组后取TopN的运算，只能借助窗口函数计算序号，语法中还是有排序（order by）的字样。2. SPL组表测试编写SPL脚本执行测试：
A1=now()/记录时间2=4/并行数3=file("/home/topn/topn.ctx").create()/产生组表对象4=A3.cursor@m(id,amount;;A2).groups@u(id%10:gid;top(100;-amount))5=interval@s(A1,now())/算出执行时间因为SPL把TopN看成是聚合计算，所以可以很容易放在分组汇总中，和全量聚合的写法几乎是一样的。3. 结论与分析测试结果（时间单位：秒）并行数124812Oracle4164919602935946273211SPL组表438021271007465349增加难度后，Oracle比之前的简单情况慢了10倍还多，而且比SPL做同样运算也慢了近10倍。这说明Oracle在这种情况下很可能做了排序动作，情况复杂化之后，Oracle的优化引擎不起作用了。而SPL在这两种情况下的运算时间差别不到2倍，基本上在同一数量级，符合我们之前的分析，算法的优势得到了充分的体现。