MySQL 中的各种 JOIN

本文主要介绍 SQL 标准中定义的各种连接的意义和区别，例如，交叉连接（ CROSS JOIN ）、内连接（ INNER JOIN ）、外连接（ OUTER JOIN ）、自然连接（ NATURAL JOIN ）等，并结合例子讲解这些连接在 MySQL 中的语法和表现。

从网上的资料看， JOIN 更多翻译为连接，本文中凡是出现中文“连接”的地方都是指 JOIN 。

本文中用到的所有例子涉及两张表—— customers 用户表和 orders 订单表，其中订单表中的 cust_id 字段表示用户的唯一 ID，也就是用户表的主键 cust_id 。两张表的数据如下：

注：两张表都经过了简化，实际业务中这两张表肯定还包括其他字段。

英文维基百科 JOIN 词条 对连接的定义如下：

翻译过来就是，“连接可以根据一张（自连接）或多张表中的共同值将这些表的列数据合并为一个新的结果集，标准 SQL 定义了五种连接：内连接、左外连接、右外连接、全外连接和交叉连接。”

也就是说，连接是 SQL 标准中定义的一种组合多张表的方式，当然一张表自身也可以和自身组合，称为自连接。连接后得到的结果集的每一列其实都来自用于连接的多张表，不同的连接类型只是区分了这些列具体从哪张表里来，列里填充的是什么数据。

其实英文维基百科的 JOIN 词条已经把各种连接的类型解释地非常清楚了，非常值得去看一下。

我们来看一下 SQL 标准中定义的各种连接类型，理解各种连接最好的方法就是把需要连接的表想象成集合，并画出可以反映集合的交与并的情况的图——韦恩图，例如下图就画出了 SQL 中定义的几种主要连接。

请先仔细查看一下图中的内容，你可以从中归纳出几种连接类型呢？

虽然图中画了 7 种集合的交并情况，但是总结起来，主要是两种连接类型在起作用——内连接（ INNER JOIN ）和外连接（ OUTER JOIN ），其中外连接又分为了左外连接（ LEFT OUTER JOIN ）、右外连接（ RIGHT OUTER JOIN ）和全外连接（ FULL OUTER JOIN ）。

下面先简单介绍一下 SQL 标准中各种连接的定义，然后在「MySQL 中的连接」一节再用例子来演示 MySQL 中支持的各种连接。

连接既然是用来合并多张表的，那么要定义一个连接就必须指定需要连接的表，并指定可选的连接条件。例如，一个典型的 SQL 连接语句如下：

我们用表 A 和表 B 指代需要连接的两张表，经过 内连接 后得到的结果集 仅 包含所有满足 连接条件 的数据；而经过 外连接 后得到的数据集 不仅 包含满足 连接条件 的数据，还包含其他数据，具体的差别是：

在上面「SQL 标准定义的主要连接」一图中并没有列出交叉连接，交叉连接会对连接的两张表做笛卡尔积，也就是连接后的数据集中的行是由第一张表中的每一行与第二张表中的每一行配对而成的，而不管它们 逻辑上 是否可以搭配在一起。假设交叉连接的两张表分别有 m 和 n 行数据，那么交叉连接后的数据集就包含 m 乘以 n 行数据。

连接根据连接的条件不同，又可以区分为等值连接和非等值连接，「SQL 标准定义的主要连接」图中画出的连接的连接条件都是比较两个字段是否相等，它们都是等值连接。

自然连接是等值连接的一种特殊形式，自然连接会自动选取需要连接的两张表中字段名相同的 所有 列做相等比较，而不需要再指定连接条件了。

注：以下内容全部基于 MySQL 5.7 版本，所有例子只保证在 MySQL 5.7 上是可以正确执行的。

MySQL 中支持的连接类型和关键字如下：

上面的表示方法摘自 MySQL 5.7 版本 官方文档 ，其中 | 表示两者皆可出现， [] 表示的是可选的， {} 表示的是必选的，例如 NATURAL LEFT JOIN 和 NATURAL JOIN 都是合法的。

可以看到，除了全外连接（ FULL OUTER JOIN ）以外， MySQL 基本支持了 SQL 标准中定义的各种连接。在 MySQL 中全外连接可以通过 UNION 合并的方式做到，当然前提是你知道自己为什么需要这么做，具体参见： Full Out Join in MySQL 。

MySQL 语法中还支持一个并不在 SQL 标准中的 STRAIGHT_JOIN ，它在 表现上 和内连接或者交叉连接并无区别，只是一种给 MySQL 优化器的一个提示， STRAIGHT_JOIN 提示 MySQL 按照语句中表的顺序加载表，只有在你明确清楚 MySQL 服务器对你的 JOIN 语句做了负优化的时候才可能用到它。

还有一点需要说明的是，根据 官方文档 ，在 MySQL 中， JOIN 、 CROSS JOIN 和 INNER JOIN 实现的功能是一致的，它们在语法上是等价的。从语义上来说， CROSS JOIN 特指无条件的连接（没有指定 ON 条件的 JOIN 或者没有指定 WHERE 连接条件的多表 SELECT ）， INNER JOIN 特指有条件的连接（指定了 ON 条件的 JOIN 或者指定了 WHERE 连接条件的多表 SELECT ）。当然，如果你非要写 ... CROSS JOIN ... ON ... 这样的语法，也是可以执行的，虽然写着交叉连接，实际上执行的是内连接。

下面我们就用例子来看一看 MySQL 中支持的几种连接的例子。

注：下面的例子都没有指定 ORDER BY 子句，返回结果的顺序可能会因为数据插入顺序的不同而略有不同。

MySQL 的交叉连接或内连接有两种写法，一种是使用 JOIN 并用 ON 或者 USING 子句指定连接条件的写法，一种是普通的 SELECT 多表，并且用 WHERE 子句指定连接的键的写法。

下面的例子是一个交叉连接：

上面的写法等价于：

当然，第二种写法中如果将 CROSS JOIN 替换成 JOIN 或者 INNER JOIN 也是可以正确执行的。上面两条语句的执行结果如下：

可以看到共返回了 30 行结果，是两张表的笛卡尔积。

一个内连接的例子如下：

上面的写法等价于：

在连接条件比较的字段相同的情况下，还可以改用 USING 关键字，上面的写法等价于：

上面三条语句的返回结果如下：

可以看到只返回了符合连接条件 customers.cust_id = orders.cust_id 的 6 行结果，结果的含义是所有有订单的用户和他们的订单。

左外连接和右外连接的例子如下，其中的 OUTER 关键字可以省略：

其中右外连接的返回与内连接的返回是一致的（思考一下为什么），左外连接的返回结果如下：

可以看到一共返回了 8 行数据，其中最后两行数据对应的 order_id 的值为 NULL ，结果的含义是所有用户的订单，不管这些用户是否已经有订单存在了。

根据前面介绍的自然连接的定义，自然连接会自动用参与连接的两张表中 字段名相同 的列做等值比较，由于例子中的 customers 和 orders 表只有一列名称相同，我们可以用自然连接的语法写一个与上面的内连接的例子表现行为一样的语句如下：

可以看到，使用自然连接就不能再用 ON 子句指定连接条件了，因为这完全是多余的。

当然，自然连接同样支持左外连接和右外连接。

下面用一个 customers 表自连接的例子再来说明一下自然连接，语句如下：

因为是自连接，因此必须使用 AS 指定别名，否则 MySQL 无法区分“两个” customers 表，运行的结果如下：

可以看到结果集和 customers 表完全一致，大家可以思考一下为什么结果是这样的。

文章之前也提到了，MySQL 还支持一种 SQL 标准中没有定义的“方言”， STRAIGHT_JOIN ， STRAIGHT_JOIN 支持带 ON 子句的内连接和不带 ON 子句的交叉连接，我们来看一个 STRAIGHT_JOIN 版本的内连接的例子：

返回结果与前面内连接的例子是一致的，如下：

STRAIGHT_JOIN 的表现和 JOIN 是完全一致的，它只是一种给 MySQL 优化器的提示，使得 MySQL 始终按照语句中表的顺序读取表（上面的例子中，MySQL 在执行时一定会先读取 customers 表，再读取 orders 表），而不会做改变读取表的顺序的优化。关于 MySQL 优化器的话题这里不做展开，需要说明的是除非你非常清楚你在做什么，否则不推荐直接使用 STRAIGHT_JOIN 。

你能理解上面的语句是在检索什么数据吗？

本文主要介绍了 SQL 标准里定义的各种连接的概念，以及 MySQL 中的实现，并通过各种例子来介绍了这些连接的区别。这些连接不一定都能在实际开发中用到，但是做到心中有知识也还是很有必要的。

那么，现在再回忆一下，什么是内连接、外连接、自连接、等值连接和自然连接？他们的区别是什么？

最后，给大家留一个思考题，为什么 MySQL 中没有左外连接或者右外连接版本的 STRAIGHT_JOIN ？

MySQL一直被人诟病没有实现HashJoin，最新发布的8.0.18已经带上了这个功能，令人欣喜。有时候在想，MySQL为什么一直不支持HashJoin呢？我想可能是因为MySQL多用于简单的OLTP场景，并且在互联网应用居多，需求没那么紧急。另一方面可能是因为以前完全靠社区，这种演进速度毕竟有限，Oracle收购MySQL后，MySQL的发版演进速度明显加快了很多。

HashJoin本身算法实现并不复杂，要说复杂，可能是优化器配套选择执行计划时，是否选择HashJoin，选择外表，内表可能更复杂一点。不管怎样现在已经有了HashJoin，优化器在选择Join算法时又多了一个选择。MySQL本着实用主义，相信这个功能增强也回应了一些质疑，有些功能不是没有能力做好，而是有它的优先级。

在8.0.18之前，MySQL只支持NestLoopJoin算法，最简单的就是Simple NestLoop Join，MySQL针对这个算法做了若干优化，实现了Block NestLoop Join，Index NestLoop Join和Batched Key Access等，有了这些优化，在一定程度上能缓解对HashJoin的迫切程度。下文会单独拿一个章节讲MySQL的这些Join优化，下面先讲HashJoin。

Hash Join算法

NestLoopJoin算法简单来说，就是双重循环，遍历外表(驱动表)，对于外表的每一行记录，然后遍历内表，然后判断join条件是否符合，进而确定是否将记录吐出给上一个执行节点。从算法角度来说，这是一个M*N的复杂度。HashJoin是针对equal-join场景的优化，基本思想是，将外表数据load到内存，并建立hash表，这样只需要遍历一遍内表，就可以完成join *** 作，输出匹配的记录。如果数据能全部load到内存当然好，逻辑也简单，一般称这种join为CHJ(Classic Hash Join)，之前MariaDB就已经实现了这种HashJoin算法。如果数据不能全部load到内存，就需要分批load进内存，然后分批join，下面具体介绍这几种join算法的实现。

In-Memory Join(CHJ)

HashJoin一般包括两个过程，创建hash表的build过程和探测hash表的probe过程。

1).build phase

遍历外表，以join条件为key，查询需要的列作为value创建hash表。这里涉及到一个选择外表的依据，主要是评估参与join的两个表(结果集)的大小来判断，谁小就选择谁，这样有限的内存更容易放下hash表。

2).probe phase

hash表build完成后，然后逐行遍历内表，对于内表的每个记录，对join条件计算hash值，并在hash表中查找，如果匹配，则输出，否则跳过。所有内表记录遍历完，则整个过程就结束了。过程参照下图，来源于MySQL官方博客

左侧是build过程，右侧是probe过程，country_id是equal_join条件，countries表是外表，persons表是内表。

On-Disk Hash Join

CHJ的限制条件在于，要求内存能装下整个外表。在MySQL中，Join可以使用的内存通过参数join_buffer_size控制。如果join需要的内存超出了join_buffer_size，那么CHJ将无能为力，只能对外表分成若干段，每个分段逐一进行build过程，然后遍历内表对每个分段再进行一次probe过程。假设外表分成了N片，那么将扫描内表N次。这种方式当然是比较弱的。在MySQL8.0中，如果join需要内存超过了join_buffer_size，build阶段会首先利用hash算将外表进行分区，并产生临时分片写到磁盘上；然后在probe阶段，对于内表使用同样的hash算法进行分区。由于使用分片hash函数相同，那么key相同(join条件相同)必然在同一个分片编号中。接下来，再对外表和内表中相同分片编号的数据进行CHJ的过程，所有分片的CHJ做完，整个join过程就结束了。这种算法的代价是，对外表和内表分别进行了两次读IO，一次写IO。相对于之之前需要N次扫描内表IO，现在的处理方式更好。

第一张图是外表的分片过程，第二张图是内表的分片过程，第三张图是对分片进行build+probe过程。

Grace Hash Join

主流的数据库Oracle，SQLServer，PostgreSQL早就支持了HashJoin。Join算法都类似，这里介绍下Oracle使用的Grace Hash Join算法。其实整个过程与MySQL的HashJoin类似，主要有一点区别。当出现join_buffer_size不足时，MySQL会对外表进行分片，然后再进行CHJ过程。但是，极端情况下，如果数据分布不均匀，导致大量的数据hash后都分布在一个分桶中，导致分片后，join_buffer_size仍然不够，MySQL的处理方式是一次读分片读若干记录构建hash表，然后probe对应的外表分片。处理完一批后，清理hash表，重复上述过程，直到这个分片的所有数据处理完为止。这个过程与CHJ在join_buffer_size不足时，处理逻辑相同。

GraceHash在遇到这种情况时，会继续分片进行二次Hash，直到内存足够放下一个hash表为止。但是，这里仍然有极端情况，如果输入join条件都相同，那么无论进行多少次Hash，都没法分开，那么这个时候GraceHashJoin也退化成和MySQL的处理方式一样。

hybrid hash join

与GraceHashJoin的区别在于，如果缓存能缓存足够多的分片数据，会尽量缓存，那么就不必像GraceHash那样，严格地将所有分片都先读进内存，然后写到外存，然后再读进内存去走build过程。这个是在内存相对于分片比较充裕的情况下的一种优化，目的是为了减少磁盘的读写IO。目前Oceanbase的HashJoin采用的是这种join方式。

MySQL-Join算法优化

在MySQL8.0.18之前，也就是在很长一段时间内，MySQL数据库并没有HashJoin，主要的Join算法是NestLoopJoin。SimpleNestLoopJoin显然是很低效的，对内表需要进行N次全表扫描，实际复杂度是N*M，N是外表的记录数目，M是记录数，代表一次扫描内表的代价。为此，MySQL针对SimpleNestLoopJoin做了若干优化，下面贴的图片均来自网络。

BlockNestLoopJoin(BNLJ)

MySQL采用了批量技术，即一次利用join_buffer_size缓存足够多的记录，每次遍历内表时，每条内表记录与这一批数据进行条件判断，这样就减少了扫描内表的次数，如果内表比较大，间接就缓解了IO的读压力。

IndexNestLoopJoin(INLJ)

如果我们能对内表的join条件建立索引，那么对于外表的每条记录，无需再进行全表扫描内表，只需要一次Btree-Lookup即可，整体时间复杂度降低为N*O(logM)。对比HashJoin，对于外表每条记录，HashJoin是一次HashTable的search，当然HashTable也有build时间，还需要处理内存不足的情况，不一定比INLJ好。

Batched Key Access

IndexNestLoopJoin利用join条件的索引，通过Btree-Lookup去匹配减少了遍历内表的代价。如果join条件是非主键列，那么意味着大量的回表和随机IO。BKA优化的做法是，将满足条件的一批数据按主键排序，这样回表时，从主键的角度来说就相对有序，缓解随机IO的代价。BKA实际上是利用了MRR特性(MultiRangeRead)，访问数据之前，先将主键排序，然后再访问。主键排序的缓存大小通过参数read_rnd_buffer_size控制。

总结

MySQL8.0以后，Server层代码做了大量的重构，虽然优化器相对于Oracle还有很大差距，但一直在进步。HashJoin的支持使得MySQL优化器有更多选择，SQL的执行路径也能做到更优，尤其是对于等值join的场景。虽然MySQL之前对于Join做过若干优化，比如NBLJ，INLJ以及BKA等，但这些代替不了HashJoin的作用。一个好用的数据库就应该具备丰富的基础能力，利用优化器分析出合适场景，然后拿出对应的基础能力以最高效的方式响应请求。

---