【数据蒋堂】第35期：JOIN提速 - 有序归并

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

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

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

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

  正文结束  

 课程视频（可点击底部阅读原文观看）

https://edu.hellobi.com/course/197/lessons  （主题二）

 近期文章

    关于数据蒋堂    

《数据蒋堂》的作者蒋步星，从事信息系统建设和数据处理长达20多年的时间。他丰富的工程经验与深厚的理论功底相互融合、创新思想与传统观念的相互碰撞，虚拟与现实的相互交织，产生出了一篇篇的沥血之作。此连载的内容涉及从数据呈现、采集到加工计算再到存储以及挖掘等各个方面。大可观数据世界之远景、小可看技术疑难之细节。针对数据领域一些技术难点，站在研发人员的角度从浅入深，进行全方位、360度无死角深度剖析；对于一些业内观点，站在技术人员角度阐述自己的思考和理解。蒋步星还会对大数据的发展，站在业内专家角度给予预测和推断。静下心来认真研读你会发现，《数据蒋堂》的文章，有的会让用户避免重复前人走过的弯路，有的会让攻城狮面对扎心的难题茅塞顿开，有的会为初入行业的读者提供一把开启数据世界的钥匙，有的甚至会让业内专家大跌眼镜，产生思想交锋。

蒋步星，清华大学计算机硕士，著有《非线性报表模型原理》等

1989年中国国际奥林匹克数学竞赛团体冠军成员，个人金牌。

2000年创立润乾公司，首次在润乾报表中提出非线性报表模型，完美解决了中国式复杂报表制表难题，目前该模型已经成为报表行业的标准。

2008年开始研发不依赖关系型数据的计算引擎，历经多个版本后，于2014年集算器正式发布。有效地提高了复杂结构化大数据计算的开发速度和运算效率。

2016年荣获中国电子信息产业发展研究院评选的“2016年中国软件和信息服务业 • 十大领军人物”。

2017年创办数据领域技术讲堂《数据蒋堂》，专注数据、每周一期。

2017年获得中国大数据产业生态大会评选的“2017年度中国数据大工匠”