本篇文章选自数据库内核杂谈系列文章。

在上篇文章中，我们主要介绍了排序和聚合的实现，覆盖了单个表的大部分操作。但数据库强大的地方在于，它能够把现实中的某一块业务，映射地表达成一系列的表的集合，并且其查询语句SQL支持多个表相关联的查询操作。这种连接多表的查询使得数据库的功能得到了一个质的飞跃。对应用开发者而言，相当于打开了一个新世界的大门。原本一个个独立的表，因为连接而产生了无穷多种可能。本文我们就来细聊一下表与表之间的JOIN(连接)算子的实现。

为什么需要JOIN?

在说具体实现前，咱们先细聊一下为什么数据库需要支持JOIN。这个问题，甚至可以再退一步到为什么数据库需要有多个表？其实答案很简单，上文都提到了：因为现实中的事物就是复杂，多样的。多个表之间的关系能方便地和现实世界的事物映射起来，并且这种映射更直观，更能够让人接受。就像面向对象编程一样，恐怕我们都不能想象如果面向对象编程只能创建一种类型的对象吧。

除了方便映射实物，业务逻辑同样需要JOIN。举个例子，假设现在有个简单的电商系统有买家，卖家和订单三张表，数据科学家想要查询2018年，对于上海客户的销售额最高的前3位卖家信息。这么一个简单的查询其实就用到了每个表里的信息，需要从买家表里得到卖家信息，从买家表里得到地址是上海的买家ID，然后对订单表以卖家ID做组队聚合，最后对销售总额进行排序并取前3。读者可能想到，这些业务逻辑其实也可以放在应用层做，的确如此(并且，如果是使用某些NoSQL的用户，因为还不支持JOIN，应用层实现是唯一的选择)。放在应用层有下面这些短处，一是执行效率方面肯定不如在数据库高效；二是数据一致性和正确性得不到保证。假设在多用户的情形下，有多个用户同时在更新数据和查询数据，如何保证查询数据的正确性。由于应用层没有数据库系统的全局观，在保证对多用户的支持上实现会更加复杂。业务驱动实现，数据库系统就推出了SQL查询语句让实现业务的程序员通过构建不同的SQL语句就能得到相应的信息，而把复杂的执行逻辑，资源管理，多用户协调等等都封装进了数据库内部。这样不仅提高了整体执行效率，也大大简化了业务逻辑的开发工作。这里插个题外话，现在很多互联网公司开始推出数据中台，我觉得和数据库系统提供SQL查询语句的封装是类似的概念：由于业务更加复杂，但迭代需求更快，如果每次实现新的业务或报表都需要写很复杂的查询语句，那岂不是效率很低。如何能够根据业务逻辑需求，把数据标准化，接口化，提供比SQL语句更高层次的API来方便上层开发。除了更进一步提高效率，还能提高安全性和对数据的控制性。未准就出现一套新的数据操作的标准，值得期待。

铺垫做好了，进入正题环节。在查询语句中经常可能涉及多个表的JOIN，比如我们示例中的订单，卖家和买家。在实现过程中，我们可以选择两个表先JOIN变成一个暂存的中间表然后再和下一个表JOIN来获得最终结果（当然也有一些高级的支持多表同时JOIN的算子操作，就不在这篇进行深入了）因此，只要提供两个表JOIN的算子操作，就能依次实现多表JOIN，得到最终结果。今天讨论的实现都针对两个表。

其次，和讨论排序以及聚合一样，为了估计和比较时间复杂度，我们假设有两个表，表A和表B；分别有M个block(页)，m个row以及N个Block和n个row的数据，并且假设M < N 和 m < n。最后，因为绝大部分的JOIN都涉及equality join，也就是JOIN的where condition里面是等式比如（WHERE A.id = B.id），今天讨论的JOIN实现都是基于equality join。

NestedLoopJoin：看似暴力的两层for循环

如果有两个表，让你在应用层做join，最容易想到的是什么方法？你可能应口而出，可以用两层for循环：第一层for循环表A的每一个row，然后嵌套内部另一层表B的for循环，循环体内做具体的join逻辑，如果满足条件，就输出一个joint的结果，代码示例如下图所示：

NestedLoopJoin

这就是我们今天介绍的第一个JOIN算子实现，NestedLoopJoin；名副其实的两层for循环。如果表A和表B都能放进内存里，那总共的IO时间复杂度就是M + N：只需要读取M + N个page。那如果内存有限，每次每个表只能读取一个page，又该怎么改进呢？改进的代码如下图所示：

block-based NestedLoopJoin

如代码所示，先读取一个外层表的block，然后依次读取内层表的block，比较结束后再读取下一个。这种时间下的IO cost是多少？应该是 M + M * N。由此也可见，在运行NestedLoopJoin时，应该尽量把小的表放在外层循环中来减少IO次数。

这里，给大家出一道思考题，现在假设系统允许分配B个page给这个join算子，应该怎么分配读取才能最优，最后IO时间复杂度又是多少呢？

有同学问，还能不能进一步优化，答案是可以的。时间复杂度的大头主要在M * N，有什么办法可以优化这一块？要想办法避免对表B进行全表扫描。优化方法就是，如果表B在对应的join键上建立索引，那我们就能用Index Scan来取代全表扫描。这就是NestedLoopIndexJoin。假设每次Index Scan的时间是常数C，它的时间复杂度就是 M + m * C。相较于前面 block-based NestedLoopJoin又提高了不少。

总结一下，我们第一个介绍的Join实现就是NestedLoopJoin，看似暴力的2层for循环。同时，也引出了block-based和内层循环用IndexScan替代的优化。

SortMergeJoin：Merge 2 sorted List

做过LeetCode的同学肯定都知道这题，Merge 2 sorted list。只要对每个list维护一个指针，然后相互比较后移即可。其实这个思路同样可以应用到表的JOIN上，只要对两个表分别根据JOIN键做排序，然后在JOIN时，对每个表维护一个指针，当两边指针的键值相同，就可以输出JOIN的row。指针不断后移，直到一方终止为止。代码如下图所示：

SortMergeJoin

从IO的时间复杂度来看，又是多少呢？在讲排序那章的时候我们已经讨论过，对M个page的表做排序，复杂度是2M * (log2M)。因此，总共的时间复杂度是M + N + 2M * (log2M) + 2N * (log2N)。因为没有M*N这一项，因此当两个表都比较大的情况下，性能是优于NestedLoopJoin的。

除了性能进步，SortMergeJoin还有什么好的特性？和BTreeIndexScan一样，SortMergeJoin后输出的tuples是已经排过序的。因此，如果上层的SQL语句还有对应键排序的需求，就不再需要额外排序了。并且排序的需求不单单指ORDER BY语句，上一期提到过的，作组队聚合(group aggregation)的时候，有序的tuple就不需要额外建立Hash表，可以直接用SortGroupByAgg来实现。另外，如果系统在JOIN前发现一方或者两方都已经排序过，同样在JOIN时就可以直接使用MERGE JOIN。很多情况下，排序是一个一劳永逸的过程，一旦排序后，上层的语句可能都能获益。

总结一下，第二个JOIN算子实现是SortMergeJoin，分别对两张表根据JOIN键排序然后合并。

HashJoin：最高效的Join

说完了利用排序来作JOIN，结合上篇文章中我们提过的，实现聚类可以用排序或者哈希表。排序和哈希表在数据库算子里有那么些既生瑜何生亮的即视感。你是不是也预料到了，在表JOIN的时候，哈希表依然作为排序的对手出现。这正是我们要介绍的最后一种实现HashJoin，并且HashJoin再一次扮演了亮的角色。HashJoin算法很直观，对相对较小的表表A，根据join condition来建立哈希表。然后对表B，只要依次读入数据去和哈希表里的值去匹配，如果匹配，那就生成一个新的tuple。代码如下图所示：

HashJoin

下面来计算IO时间复杂度，如果假设较小的表A建立的哈希表能够全部放进内存的话，IO时间复杂度只有 M+N。

按照这种方式，假设将较小的外部表M建立哈希表，如果能全部放进内存的话，然后对N表进行全表扫描并且对比hash。IO时间复杂度只有 M + N。如果表A比较大，不能全部放进内存的话，我们又要借助外部哈希表的算法来分而治之。首先，我们用一个哈希函数把表A和表B分别划分到x个bucket，如果在划分的过程中发现某个bucket依然很大，可以借助递归思想，继续划分。我们称之为partition phase。Partition phase的IO复杂度是2 * (M + N)，因为需要把所有的表A和表B读取到内存在写回文件系统。第二阶段就是对于每个bucket，分别读取表A和表B然后建立哈希表做JOIN，称之为probing phase。这个阶段会再次读取所有表A和表B的数据，因此是 M + N。因此，HASH JOIN的时间复杂度，在即使需要依赖外部哈希表的情况下，依然是线性的 3*(M+N)。所以在绝大多数的情况下，性能都是最优的。

总结一下，最后一个JOIN实现是HashJoin，通过对相对较小的表建立哈希表，然后读取另一个表来匹配生成join rows。

总结

总结时刻，本章我们详细介绍了三种JOIN算子的实现，分析了它们的适用场景和时间复杂度。至此，数据库内和杂谈覆盖了常见算子的实现。各位读者可以回想一下写过的SQL，是否能能够使用我们讨论过的算子组合成算子树来实现这些查询语句。

说了那么多种JOIN，读者可能会想，即然已经说了HashJoin普遍情况下性能最优，为什么还需要实现其他JOIN呢？因为在特定的情况下，NestedLoopIndexScan可能会比HashJoin更快，或者在需要排序的情况下，SortMergeJoin也可能更有优势。影响因素有具体的查询语句，表A和表B的大小，join键值的分布，以及是否对join键值有index等等。数据库在执行语句的时候，需要通盘考虑这些影响因素来决定最后具体使用哪种JOIN算子。而做这个决定的就是咱们下一期要讲的内容：数据库的大脑 – 优化器。尽情期待。

作者介绍：

顾仲贤，现任Facebook Tech Lead，专注于数据库，分布式系统，数据密集型应用后端架构与开发。拥有多年分布式数据库内核开发经验，发表数十篇数据库顶级期刊并申请获得多项专利，对搜索，即时通讯系统有深刻理解，爱设计爱架构，持续跟进互联网前沿技术。

2008年毕业于上海交大软件学院，2012年，获得美国加州大学戴维斯计算机硕士，博士学位；2013-2014年任Pivotal数据库核心研发团队资深工程师，开发开源数据库优化器Orca；2016年作为初创员工加入Datometry，任首席工程师，负责全球首家数据库虚拟化平台开发；2017年至今就职于Facebook任Tech Lead，领导重构搜索相关后端服务及数据管道，管理即时通讯软件WhatsApp数据平台负责数据收集，整理，并提供后续应用。

相关阅读：

数据库内核杂谈（一）：一小时实现一个基本功能的数据库

创作场景

数据库内核杂谈（六）：表的 JOIN（连接）