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

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

在上篇文章中，我们主要介绍了排序和聚合的实现，覆盖了单个表的大部分操作。但数据库强大的地方在于，它能够把现实中的某一块业务，映射地表达成一系列的表的集合，并且其查询语句 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 数据平台负责数据收集，整理，并提供后续应用。

相关阅读：

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

数据库内核杂谈（二）：存储“演化论”

数据库内核杂谈（三）：索引优化

数据库内核杂谈（四）：执行模式

数据库内核杂谈（五）：如何实现排序和聚合