【数据蒋堂】第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分段时需要同时向某个分段写出数据，造成共享资源冲突；而计算某一段又会几乎耗光所有内存，其它并行任务就无法实施。

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

先按主表（同维表则取较大的即可，其它讨论不影响）分段（如何能够较平均地分段且支持数据追加，我们以后会撰文解释），读出每段第一条记录的主键值，然后用这些键值到子表用二分法寻找定位（是否可以执行二分法和数据存储格式相关，后续文章也会谈到），从而获得子表的分段点。这样可以保证主子表的分段是同步对齐的。

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