【性能优化】4.5 [遍历技术] 多路游标

4.6 分组汇总

分组是一种常见的遍历型运算，它需要读出并计算所有参与分组的记录。对这类需要全集参与的运算，索引几乎没有意义（极个别的场景有用，我们在下一章会讲到）。有些程序员在分组慢的时候也去给数据库表增加索引，是没有理解分组的原理，结果只会给数据库增加负担。

分组的过程通常是这样：先产生一个空的分组结果集，然后遍历每一条原数据，计算其分组键值，到分组结果集中查找该键值对应的分组子集将把这条记录加入到分组子集中，如果找不到则新增一个由该条记录构成的分组子集。

这个运算过程中，读取原数据中记录、计算其分组键值、将其加入到分组子集，这几个动作的发生次数都是确定的（等于原数据记录数），没有办法再减少，可以想办法的环节只有在分组结果集中寻找分组子集。这是个标准的查找操作，在没有特别的条件可利用时，一般会采用哈希方法。即把将分组子集按其对应的分组键值的哈希值排列（即相当于序号定位了），有新记录时，计算分组键值及其哈希值，可以迅速在少量哈希值相同的分组子集中找到自己的那一组。这种分组算法也称为哈希分组。

分组子集的总和和原数据集一样大。如果数据量大到不能在内存中装下，那么分组子集也不可能，所以这种办法只能适用于内存数据集。不过，大多数情况时，分组都伴随着汇总，我们并不需要保留这些分组子集，而只要计算出分组子集的汇总值即中，而这些汇总值经常都可以用累计方法计算，比如求和、计数、最大 / 最小等。这样，可以丢弃分组子集，只保持分组键值和对应的汇总值就可以了（相当于一个序表而不再是集合的集合），结果集就会小很多，即使原数据量很大也可能得到了一个内存可放下的小分组结果集。这个过程中仍然要查找到目标记录去做累计，仍然是用哈希方案，这种分组汇总也仍然称为哈希分组。

有时候即使只要汇总值，分组结果集也仍然可能巨大到无法被内存放下，也就是分组键值的数量非常多。这种情况我们称为大分组，对应的结果集小到可以在内存放下的情况称为小分组。

处理大分组要把哈希分组算法扩展到外存。首先要扩大哈希值的范围，使得分组键值尽量散落在不同的哈希值下，同一个哈希值对应分组键值并不多。哈希函数的范围事先知道，把这个范围划分成几个能被内存放下的区间（简单等分就可以了）。在遍历数据时，每读出一批记录，计算出其分组键值的哈希值后，根据其所在的区间分别写入不同的缓存文件中，然后可以释放空间再去读取下一批，直到遍历完成。然后从分别从每个缓存文件中读出数据再做一遍哈希分组，因为每个缓存文件中的数据的哈希值都落在其中一个区间内，一定能在内存中放下，所以可以分别来做而不会导致内存溢出。

SPL 为大分小组汇总分别设计了两个函数。小分组会直接返回结果集，而大分组将返回游标，这个游标即是建立在上述的缓存文件上，取数过程中再完成第二轮的分组汇总。

两个函数的参数规则都一样，小分组 groups 函数直接会使用哈希算法，而大分组 groupx 函数要加 @u 选项才会使用哈希算法。

小分组不需要产生缓存文件，而大分组则一定会。如果大分组的函数来实现小分组时，即使最后的分组结果是小的，也会浪费很多时间用于写出成缓存文件。事先预测分组结果集的大小选择合适的函数非常重要的，也因此 SPL 提供了两个分组函数。读者可以分别对比 A2 和 A3 的计算时间。

我们还会发现 groupx 返回的分组结果集的次序是乱的，看起来和分组键值没有关系，和原数据集的次序也没什么关系。其实，这就是哈希分组的特点，其结果集会按分组键值的哈希值排序，看起来就像是乱的了。而小分组 groups 函数在返回前，SPL 会按分组键值执行一次排序，所以看起来是按键值有序的，如果使用 groupx@u，也会发现同样的结果。

还有另一种办法实现大分组，这个方法也可以实现大排序。

依次遍历每一条记录，执行开始讲过的哈希分组方法（哈希范围不能太大），但时时监控内存中这个分组结果集中有效的分组键值的数量，达到一定限度后，将当前的分组结果集按分组键值排序后写成一个缓存文件，然后清除释放分组结果集的空间，继续遍历剩下的记录，如此反复直到遍历完毕，最后会得到一批缓存文件，这些文件中的数据都是按分组键值有序的，再执行有序归并算法和有序分组汇总就可以了，有序归并和有序分组都只要占很小的内存就可以实现。这种分组算法称为排序分组。

类似地，这种大分组的结果也是个基于缓存文件的游标，在游标取数过程完成第二轮的归并和分组汇总。

没有选项的 groupx 是按这种算法工作的。

排序分组比哈希分组有一些优势，它的分组结果集是直接对分组键值有序的，有可能在下一轮计算利用。更方便的在于，可以使用大分组的算法（和函数）去实现小分组。仔细研究上述的算法过程就会发现，如果事实上的结果集是小的，就不会真地触发写出缓存文件的动作，因为内存中的分组结果集永远不会大到要被缓存写出的地步。

排序分组还有的个好处是比较稳定，因为哈希函数存在运气不好的时候，对于内存查找，运气不好只是导致浪费时间，而对于大分组则可能会出现某个哈希值下对应的分组键值太多而不能在内存中放下，这还需要做第二轮哈希，非常麻烦且性能低下。

所以，SPL 缺省提供的大分组是排序分组（无选项）。

不过，在确定知道是大分组结果集时（也就是一定会写出缓存文件了），且哈希函数运气较好时，哈希分组的效率会比排序分组好。因为排序本身会就比较慢，而且第二轮要做归并时需要同时读取多个缓存文件，造成更多硬盘并发读现象。而哈希分组的第二轮每次只要读一个缓存文件，不会造成硬盘并发读。所以，SPL 也提供了这种哈希大分组的方法。

数据库通常使用优化过的哈希分组方法，会先用小范围的哈希函数尝试，如果发现分组键值太多，则会做二次哈希并实施缓存。这样也能避免总是写出缓存数据的现象，在小分组时性能较好，不过算法过程要麻烦很多，在大分组时性能就会下降严重。

不过，即使排序分组可以自适应小分组和大分组，在工程实现上 groupx 仍然比 groups 要复杂一些，性能也会差一点。更重要的问题是，大分组的并行效果并不好。多个线程同时向同一个中间结果集去累计，会因为抢夺写入权经常处于等待状态；如果每个线程有各自的中间结果集，那又会造成内存要被拆分使用（每个线程只能使用几分之一），本来可能不需要写缓存文件（整片内存足够放下分组结果集）的情况，也会出现发生要写缓存文件现象（几分之一就放不下了），硬盘读写很慢，很容易把 CPU 并行的那点好处都抵消殆尽。即使总是要写出缓存文件的情况，多线程同时写出缓存文件，会导致硬盘出现并发写，这常常严重影响性能。所以 groupx 函数针对多路游标运算并不一定能获得更好的性能。

所以，如果明确知道结果集是小的，仍然要用 groups 才能跑出最优性能，如果能预测结果集的规模，还可以选择合适的并行数。在不太清楚结果集大小时，使用 groupx 就会更稳妥一些，单线程时的性能损失不算大。

理解了排序分组，大数据排序也比较简单，每读一批数据后排序写出成缓存文件，最后再对这些缓存文件执行归并排序就可以了。排序运算的结果集和原数据集的规模是相同的，不会像分组那样有可能变小，所以大排序一定会产生缓存文件。

类似地，大排序的并行也不容易产生线性的性能提升，能在内存排序那个环节更快，但多个线程并发写硬盘又可能把优势给抵消掉。

SPL 没有直接提供类似哈希分组那样的大排序算法，在了解下一章的程序游标技术和序号分段机制后，可以自己拼出这种算法。大排序通常只在数据准备阶段时使用，而且大部分情况时都可以归并，针对原始大数据做排序的情况并不多。

【性能优化】4.7 [遍历技术] 聚合理解
【性能优化】 前言及目录