【性能优化】4.6 [遍历技术] 分组汇总

4.7 聚合理解

考虑这样一个问题：从 1 亿个订单的金额中找出最大的 10 个。

简单的想法，是把这 1 亿条记录按金额从大到小排序，然后取出前 10 条记录的金额字段，剩下的都不用了。

在数据库中写 SQL 解决这个问题就是这个思路。

但是，排序本身就是个非常慢的动作，大排序还会涉及缓存数据，性能会差得更多，而且还不容易并行。

其实，我们很容易想到更简单的算法。

只要保持一个成员数为 10 的结果集，先都填为 0（其实是随便一些很小的数）。然后遍历订单表，如果当前订单金额比这个结果集合中最小的要大，则用这个金额替换结果集中的这个最小成员。遍历完之后的结果集就是我们要的数。

这个运算只要对原数据表遍历一次，不需要排序（排序实际上遍历次数是 log2N），更不需要缓存文件；而且分段并行也很容易，无非就是对每个段都算出前 10 名，再对这些前 10 名的并集计算前 10 名即要，还是不会涉及硬盘并发写的问题。

在 N 个成员中取前 M 名，使用排序的复杂度是 NlogN，而上面这种算法的复杂度 NlogM。具体到这个例子，即使全内存情况，CPU 运算量也能减少 8 倍左右。

这种思路并不新鲜，如果把问题改成计算最大值，那么几乎所有人都会想到用这种办法。但换成前 M 名时，我们会更习惯想到先排序的办法了。

这需要我们扩展对聚合运算的理解。

通常，我们理解的聚合运算是将一个集合计算成一个单值，比如求和、计数、最大、最小这些。但如果我们扩展一下，把返回值是一个小集合的情况也看成是聚合运算，那么就可以使用聚合运算的思路来解决相关问题了。

具体到这个问题，就是把取前 N 名也作为一种聚合运算，它与求和、计数这些运算是一样的，只不过返回的是个集合而不是单值了。

SPL 中 top 函数和 sum 一样被认为是聚合函数，top 只有从小到大的方向，参数中的 -10 表示取最后 10 名，也就是最大的 10 个了。top(-10,amount) 会返回最大的 10 个 amount 值，而 top(-10;amount) 将返回使 amount 最大的 10 条记录。

把 top 作为聚合函数还有个好处，可以在分组汇总中使用，仍然和 sum,count,max,min 这类函数一样：

这样可以计算出每个地区的前 10 大订单额以及相应的订单，也可以使用并行多路游标。需要注意的是，A2 计算结果中有后两个字段的值是序列（集合）。

如果不把 top 看成是聚合函数，在分组汇总中做这种运算就非常困难。在 SQL 中要使用窗口函数才能勉强描述这种运算，运算性能也非常差。

聚合运算本质上是针对某个集合做的运算，但实际实施这个运算时，经常并不需要把这个集合的全体成员都准备好才能计算出来，很多聚合运算都可以使用累计的办法，逐步遍历集合成员就可以完成，这样就适合针对大数据的运算了。

求和、计数、最大、最小以及刚才介绍的前几名，都满足这种特性。

我们把这类聚合函数称为迭代函数，其运算过程可以抽象出这样的特点：

1) 给一个初值作为计算结果

2) 每碰到一个新的集合成员，用该成员和上次的计算结果混合计算得到一个计算结果

3) 遍历完成后即可返回计算结果。

计算迭代函数，只要保持一个当前结果值就可以了，遍历过的集合成员可以丢弃；即使是用于分组运算中对分组子集的汇总，也只要为每个分组保持一个当前结果值，内存占用不大。完成迭代函数的计算只要遍历一次原数据表，不需要借助缓存文件，还可以并行计算。

SPL 为迭代函数设计了一个通用的形式：

iterate(x,a)

其实中 a 是初值，x 是一个表达式，在其中用 ~~ 表示上次的计算结果，~ 表示当前的集合成员，计算出来的 x 就作为新的计算结果，也就是下一次计算时的 ~~。遍历完成后，这个函数就会返回当时的 ~~。

我们可以用它把 sum,count 等常用的聚合运算定义出来：

sum iterate(~~+~,0)
max iterate(if(\~\~<~,~,~~),-inf())
min iterate(if(\~\~>~,~,~~),inf())
count iterate(if(~,\~\~+1,~~),0)

top 要麻烦一些，但也可以定义出来，读者可以把它作为一个练习题。

我们现在可以把聚合运算推广到这种更一般的情况，只要能被 iterate 描述的且计算结果占内存不大的情况，都可以用这种累计方式获得较高的计算性能。可用于分组、原数据表只要遍历一次、不需要借助缓存文件（大分组仍然要缓存，但是大分组本身的缓存，不是聚合计算造成的）。不过，迭代函数的并行计算会有些差别。它本身可以针对分段过的数据表进行并行计算，得到多份计算结果（每个分段一份），需要手工编码完成第二轮汇总（将每个分段的计算结果再汇总成一个结果）。不能直接基于多路游标实现并行（可使用多路游标的 fork 语法，但仍需要自己手动做第二轮汇总运算）。

我们还可以用 iterate 来实现一些事先没有定义过的聚合运算，比如连乘、求并集等：

这里的求并集就是一个没有定义过的聚合运算。

SPL 约定在针对记录计算迭代函数里，可以直接用字段名表示当前记录的字段，不用写成 ~.area。A2 将计算出所有订单销售到的地区，A3 则计算每个产品销售到的地区。

结构化数据运算中常见的简单聚合运算也就是已经定义过的这几个或可以由这些衍生出来，比如连乘可以取对数后求和再用指数，上例中的求并集也可以用去重运算（SPL 中的 id 函数）替代。需要用迭代函数来写的自定义聚合运算其也不算罕见，但可能涉及较复杂的业务背景，不容易简单举例。

假定订单表是按时间有序的，要计算每个产品的税金总和，初始税率为 5%，当累计订单税额超过 10000 后，之后订单的税率降为 3%。这种聚合无法用常规函数描述，但可以用迭代函数描述，也可以较高性能计算出来。

下面这个迭代函数将计算每个地区最多连续有多少金额超过 50 的订单数。

下一章我们还要讲迭代函数应用到有序明细数据上的形式，会举出更多有业务意义的例子。

【性能优化】4.8 [遍历技术] 冗余分组键
【性能优化】 前言及目录