连接运算 8- 有序归并

连接运算 7- 进一步的外键关联

八、有序归并

我们再来看同维表和主子表的 JOIN,这两种情况的优化提速手段是类似的。

我们前面讨论过,HASH JOIN 算法的计算复杂度(即关联键的比较次数)是 sum(ni*mi),比全遍历的复杂度 n*m 要小很多,不过要看 HASH 函数的运气。

如果这两个表都对关联键有序,那么我们就可以使用归并算法来处理关联,这时的复杂度是 n+m;在 n 和 m 都较大的时候(一般都会远大于 HASH 函数的取值范围),这个数也会远小于 HASH JOIN 算法的复杂度。归并算法的细节有很多材料介绍,这里就不再赘述了。

但是,外键 JOIN 时不能使用这个办法,因为事实表上可能有多个要参与关联的外键字段,不可能让同一个事实表同时针对多个字段都有序。

同维表和主子表却可以!

因为同维表和主子表总是针对主键或主键的一部分关联,我们可以事先把这些关联表的数据按其主键排序。排序的成本虽然较高,但是一次性的。一旦完成了排序,以后就可以总是使用归并算法实现 JOIN,性能可以提高很多。

这还是利用了关联键是主键(及其部分)的特征。

有序归并对于大数据特别有效。象订单及其明细这种主子表是不断增长的事实表,时间长了常常会积累得非常大,很容易超出内存容量。

外存大数据的 HASH 分堆算法需要产生很多缓存,数据在外存中被读两次写一次,IO 开销很大。而归并算法时,两个表的数据都只要读一次就行了,没有写。不仅是 CPU 的计算量减少,外存的 IO 量也大幅下降。而且,执行归并算法需要的内存很少,只要在内存中为每个表保持数条缓存记录就可以了,几乎不会影响其它并发任务对内存的需求。而 HASH 分堆需要较大内存,每次读出更多数据,以减少分堆的次数。

SQL 采用笛卡尔积定义的 JOIN 运算不区分 JOIN 类型,不假定某些 JOIN 总是针对主键的,就没办法从算法层面上利用这一特点,只能在工程层面进行优化。有些数据库会检查数据表在物理存储上是否针对关联字段有序,如果有序则采用归并算法,但基于无序集合概念的关系数据库不会刻意保证数据的物理有序性,许多操作都会破坏归并算法的实施条件。使用索引可以实现数据的逻辑有序,但物理无序时的遍历效率还是会大打折扣。

有序归并的前提是将数据按主键排序,而这类数据常常会不断追加,原则上每次追加后就要再次排序,而我们知道大数据排序成本通常很高,这是否会导致追加数据难度很大呢?其实,追加数据再加入的过程也是个有序归并,把新增数据单独排序后和已有序的历史数据归并,复杂度是线性的,相当于把所有数据重写一次,而不象常规的大数据排序需要缓存式写出再读入。在工程上做些优化动作还可以做到不必每次都全部重写,进一步提高维护效率。这些在乾学院上都有介绍。

有序归并的好处还在于易于分段并行。

现代计算机的都有多核 CPU,SSD 硬盘也有较强的并发能力,使用多线程并行计算就能够显著提高性能。但传统的 HASH 分堆技术实现并行比较困难,多线程做 HASH 分堆时需要同时向某个分堆写出数据,造成共享资源冲突;而第二步实现某组分堆关联时又会消费大量内存,无法让实施较大的并行数量。

使用有序归并实现并行计算时需要把数据分成多段,单个表分段比较简单,但两个关联表分段时必须同步对齐,否则归并时两个表数据错位了,就无法得出正确的计算结果,而数据有序就可以保证高性能的同步对齐分段。

先把主表(同维表则取较大的即可,其它讨论不影响)平均分成若干段,读出每段第一条记录的主键值,然后用这些键值到子表中用二分法寻找定位(因为也有序),从而获得子表的分段点。这样可以保证主子表的分段是同步对齐的。

因为键值有序,所以主表每段的记录键值都属于某个连续区间,键值在区间外的记录不会在这一段,键值在区间内的记录一定在这一段,子表对应分段的记录键值也有这个特性,所以不会发生错位情况;而同样因为键值有序,才可以在子表中执行高效的二分查找迅速定位出分段点。即数据有序保证了分段的合理性及高效性,这样就可以放心地执行并行算法了。

主子表这种主键关联的关系还有一个特征,就是子表只会和一个主表在主键上关联(其实同维表也有,但用主子表容易解释),它不会有多个相互无关的主表(可能有主表的主表)。这时候,还可以使用一体化存储的机制,把子表记录作为主表的字段值去存储。这样,一方面减少了存储量(关联键只要存储一次),又相当于预先做好了关联,不需要再做比对了。对于大数据,就能获得更好的性能。

我们已经将上述这些性能优化手段在集算器 SPL 中实现并在实际场景用得到了应用,也取得了非常好的效果。SPL 目前已经开源,读者可以去数速公司或润乾公司官网及论坛下载并获得更多资料。

结语

JOIN 运算确实是数据库中最复杂的运算,本文对 JOIN 运算进行了深入的剖析整理,篇幅已经不小,但仍然也没有完全穷尽所有方面。

感兴趣的同学可以进一步研读乾学院 (c.raqsoft.com.cn) 上的图书和文章。

本文内容还有个视频材料 连接运算的优化与提速