【数据蒋堂】第35期:JOIN提速 – 有序归并
我们再来看同维表和主子表的JOIN,这两种情况的优化提速手段是一样的。
设两个关联表的规模(记录数)分别是N和M,则HASH分段技术的计算复杂度(关联字段的比较次数)大概是SUM(Ni*Mi),其中Ni和Mi分别是HASH值为i的两表记录数,满足N=SUM(Ni)和M=SUM(Mi),这大概率会比完全遍历时的复杂度N*M要小很多(运气较好的时候会小K倍,K是HASH值的取值范围)。
如果这两个表针对关联键都有序,那么我们就可以使用归并算法来处理关联,这时的复杂度是N+M;在N和M都较大的时候(一般都会远大于K),这个数会远小于刚才那个SUM(Ni*Mi)。归并算法的细节有很多材料介绍,这里就不再赘述了。
但是,外键JOIN时不能使用这个办法,因为事实表上可能有多个要参与关联的外键字段,不可能让同一个事实表同时针对多个字段都有序。
同维表和主子表却可以!
因为同维表和主子表总是针对主键或主键的一部分关联,我们可以事先把这些关联表的数据按其主键排序。排序的成本虽然较高,但是一次性的。一旦完成了排序,以后就可以总是使用归并算法实现JOIN,效率能提高很多。
有序归并的意义还在于大数据的情况。象订单及其明细这种主子表是不断增长的事实表,时间长了常常会积累得非常大。
当要JOIN的两个表都大到内存无法放下的时候,关系数据库仍然是使用HASH分段的技术。根据关联字段的HASH值,将数据分成若干段,每段都足够小到能装入内存再实施内存的HASH分段算法。但这会发生外存倒换的问题,数据需要先分段写出再读入,多出一写一读,外存读本来就不快,写就更慢,这样性能会差出很多。运气不好时,一次HASH分段时可能会发生某段仍然太大而无法装入内存,这时就需要二次HASH,进一步加剧这个问题。而且,HASH分段算法在处理每一段时需要把整段读入内存,为了减少分段数量,就会根据内存大小尽量让分段变大,这样会用光所有内存,有并发运算时就会严重影响其它任务的性能。
归并算法则没有这个问题了,两个表的数据都只要遍历一次就行了,不仅是CPU的计算量减少,外存的IO量也大幅下降。而且,执行归并算法需要的内存很少,只要在内存中为每个表保持数条缓存记录就可以了,几乎不会影响其它并发任务对内存的需求。
SQL采用笛卡尔积定义的JOIN运算不区分JOIN类型,不假定某些JOIN总是针对主键的,就没办法从算法层面上利用这一特点,只能在工程层面进行优化。有些数据库会检查数据表在物理存储上是否针对关联字段有序,如果有序则采用归并算法,但基于无序集合概念的关系数据库不会刻意保证数据的物理有序性,许多操作都会破坏归并算法的实施条件。使用索引可以实现数据的逻辑有序,但物理无序时的遍历效率还是会大打折扣。
有序归并的前提是将数据按主键排序,而这类数据常常会不断追加,原则上每次追加后就要再次排序,而我们知道大数据排序成本通常很高,这是否会导致追加数据难度很大呢?其实,追加数据再加入的过程也是个有序归并,把新增数据单独排序后和已有序的历史数据归并,复杂度是线性的,相当于把所有数据重写一次,而不象常规的大数据排序需要缓存式写出再读入。在工程上做些优化动作还可以做到不必每次都全部重写,进一步提高维护效率。
有序归并的好处还在于易于分段并行。
现代计算机的都有多核CPU,SSD硬盘也有较强的并发能力,使用多进程(或线程)并行计算就能够显著提高性能。但传统的HASH分段技术很难实现并行,多进程做HASH分段时需要同时向某个分段写出数据,造成共享资源冲突;而计算某一段又会几乎耗光所有内存,其它并行任务就无法实施。
使用有序归并实现并行计算时需要把数据分成多段,单个表分段比较简单,但两个关联表分段时必须同步对齐,否则归并时两个表数据错位了,就无法得出正确的计算结果,而数据有序就可以保证高性能的同步对齐分段。
先按主表(同维表则取较大的即可,其它讨论不影响)分段(如何能够较平均地分段且支持数据追加,我们以后会撰文解释),读出每段第一条记录的主键值,然后用这些键值到子表用二分法寻找定位(是否可以执行二分法和数据存储格式相关,后续文章也会谈到),从而获得子表的分段点。这样可以保证主子表的分段是同步对齐的。
因为键值有序,所以主表每段的记录键值都属于某个连续区间,键值在区间外的记录不会在这一段,键值在区间内的记录一定在这一段,子表对应分段的记录键值也有这个特性,所以不会发生错位情况;而同样因为键值有序,才可以在子表中执行高效的二分查找迅速定位出分段点。即数据有序保证了分段的合理性及高效性,这样就可以放心地执行并行算法了。