Join 算法与调优

前言：随着 MySQL 不停的迭代，会有很多新的特性出现，一些新特性会替代老的特性，在文档开头会备注 MySQL 的版本。

版本：MySQL 5.7

在 MySQL 8.0 之前，MySQL 存在如下几种 Join 算法：

• Nested-Loop Join
  • Simple Nested-Loop Join
  • Index Nested-Loop Join
  • Block Nested-Loop Join
• Batched Key Access Join

TODO：在 MySQL 8.0 中新推出了 Hash Join 算法，用来替代 Block Nested-Loop Join，后面有机会再补充到文档中。

接下来我们就逐步分析 MySQL 的这几种 Join 算法，目的是提高我们对 MySQL 底层 Join 算法的认识。

截止到 MySQL 5.7 不支持 Hash Join，也不支持 Sort Merge Join，但是 MySQL 在 Join 上也有自己的独特的优化与处理，此外，分支版本 MariaDB 已支持 Hash Join，因此拿 MySQL 来做一些“简单”的分析查询也是完全能够接受的。当然，如果数据量真的上去了，那么即使支持 Hash Join 的传统 MPP 架构的关系型数据库可能也是不合适的，这类分析查询或许应该交给更为专业的 Hadoop 集群来计算。

Join 的成本

在讲述 MySQL 的 Join 类型与算法前，看看两张表的 Join 的过程：

上图的 Fetch 阶段是指当内表关联的列是辅助索引时，但是需要访问表中的数据，那么这时就需要再访问主键索引才能得到数据的过程，不论表的存储引擎是 InnoDB 存储引擎还是 MyISAM，这都是无法避免的，只是 MyISAM 的回表速度要快点，因为其辅助索引存放的就是指向记录的指针，而 InnoDB 存储引擎是索引组织表，需要再次通过索引查找才能定位数据。

Fetch 阶段也不是必须存在的，如果是聚集索引链接，那么直接就能得到数据，无需回表，也就没有 Fetch 这个阶段。另外，上述给出了两张表之间的 Join 过程，多张表的 Join 就是继续上述这个过程。

接着计算两张表 Join 的成本，这里有下列几种概念：

• 外表的扫描次数，记为 O。通常外表的扫描次数都是1，即 Join 时扫描一次驱动表的数据即可。
• 内表的扫描次数，记为 I。根据不同 Join 算法，内表的扫描次数不同。
• 读取表的记录数，记为 R。根据不同 Join 算法，读取记录的数量可能不同。
• Join 的比较次数，记为 M。根据不同 Join 算法，比较次数不同。
• 回表的读取记录的数，记为 F。若 Join 的是辅助索引，可能需要回表取得最终的数据。

评判一个 Join 算法是否优劣，就是查看上述这些操作的开销是否比较小。当然，这还要考虑 I/O 的访问方式，顺序还是随机，总之 Join 的调优也是门艺术，并非想象的那么简单。

Simple Nested-Loop Join

网上大部分说 MySQL 只支持 Nested-Loop Join，故性能差。但是 Nested-Loop Join 一定差吗？Hash Join 比Nested-Loop Join 强？Inside 君感觉这样的理解都是片面的，Hash Join 可能仅是 Nested-Loop Join 的一种变种。

所以 Inside 君打算从算法的角度来分析 MySQL 支持的 Join，并以此分析对于 Join 语句的优化。

首先来看 Simple Nested-Loop Join（以下简称 SNLJ），也就是最朴素的 Nested-Loop Join，其算法伪代码如下所示：

Foreach row r in R do   # 扫描R表
  Foreach row s in S do # 扫描S表
    If r and s satisfy the join condition # 如果r和s满足join条件
      Then output the tuple <r,s> # 那就输出结果集

下图能更好地显示整个 SNLJ 的过程：

SNLJ 的算法相当简单、直接。即外表（驱动表）中的每一条记录与内表中的记录进行判断。但是这个算法也是相当粗暴的，粗暴的原因在于这个算法的开销其实非常大。假设外表的记录数为 R，内表的记录数位 S，根据上一节Inside 君对于 Join 算法的评判标准来看，SNLJ 的开销如下表所示：

可以看到读取记录数的成本和比较次数的成本都是 S*R，也就是笛卡儿积。假设外表内表都是1万条记录，那么其读取的记录数量和 Join 的比较次数都需要上亿。

Index Nested-Loop Join

SNLJ 算法虽然简单明了，但是也是相当的粗暴。因此，在 Join 的优化时候，通常都会建议在内表建立索引，以此降低 Nested-Loop Join 算法的开销，MySQL 数据库中使用较多的就是这种算法，以下称为 INLJ，来看这种算法的伪代码：

For each row r in R do  # 扫描R表
  lookup r in S index   # 查询S表的索引（固定3~4次IO，B+树高度）
    if found s == r     # 如果r匹配了索引s
      Then output the tuple <r,s>  # 输出结果集

由于内表上有索引，所以比较的时候不再需要一条条记录进行比较，而可以通过索引来减少比较，从而加速查询。整个过程如下图所示：

可以看到外表中的每条记录通过内表的索引进行访问，因为索引查询的成本是比较固定的，故优化器都倾向于使用记录数少的表作为外表，又称驱动表（这里是否又会存在潜在的问题呢，会在另外一篇补充说明文档中描述该问题）。故 INLJ 的算法成本如下表所示：

上表 S 表示通过索引找到匹配的记录数量。同时可以发现，通过索引可以大幅降低内表的 Join 的比较次数，每次比较 1 条外表的记录，其实就是一次 index lookup（索引查找），而每次 index lookup 的成本就是树的高度，即 Index。

INLJ 的算法并不复杂，也算简单易懂。但是效率是否能达到用户的预期呢？其实如果是通过表的主键索引进行 Join，即使是大数据量的情况下，INLJ 的效率亦是相当不错的。因为索引查找的开销非常小，并且访问模式也是顺序的（假设大多数聚集索引的访问都是比较顺序的）。

大部分人诟病 MySQL 的 INLJ 慢，主要是因为在进行 Join 的时候可能用到的索引并不是主键的聚集索引，而是辅助索引，这时 INLJ 的过程又需要多一步 Fetch 的过程，而且这个过程开销会相当的大：

由于访问的是辅助索引，如果查询需要访问聚集索引上的列，那么必要需要进行回表取数据，看似每条记录只是多了一次回表操作，但这才是 INLJ 算法最大的弊端。

首先，辅助索引的 index lookup 是比较随机 I/O 访问操作。其次，根据 index lookup 再进行回表又是一个随机的 I/O 操作。所以说，INLJ 最大的弊端是其可能需要大量的离散操作，这在 SSD 出现之前是最大的瓶颈。而即使 SSD 的出现大幅提升了随机的访问性能，但是对比顺序 I/O，其还是慢了很多，依然不在一个数量级上。

例如下面的这个SQL语句：

SELECT COUNT(*)
FROM part, lineitem
WHERE l_partkey = p_partkey
    AND p_retailprice > 2050
    AND l_discount > 0.04;

其中 p_partkey 是表 part 的主键，l_partkey 是表 lineitem 的一个辅助索引，由于表 part 数据较小，因此作为外表（驱动表）。但是内表 Join 完成后还需要判断条件 l_discount > 0.04，这个在聚集索引上，故需要回表进行读取。根据 explain 得到上述 SQL 的执行计划如下图所示：

Block Nested-Loop Join

算法说明

在有索引的情况下，MySQL 会尝试去使用 Index Nested-Loop Join 算法，在有些情况下，可能 Join 的列就是没有索引，那么这时 MySQL 的选择绝对不会是最先介绍的 Simple Nested-Loop Join 算法，因为那个算法太粗暴，不忍直视。数据量大些的复杂 SQL 估计几年都可能跑不出结果。

Simple Nested-Loop Join 算法的缺点在于其对于内表的扫描次数太多，从而导致扫描的记录太过庞大。Block Nested-Loop Join 算法较 Simple Nested-Loop Join 的改进就在于可以减少内表的扫描次数，甚至可以和 Hash Join 算法一样，仅需扫描内表一次。

接着 Inside 君带你来看看 Block Nested-Loop Join 算法的伪代码：

For each tuple r in R do
  store used columns as p from R in join buffer # 将部分或者全部R的记录保存到join buffer中，记为p
  For each tuple s in S do
    If p and s satisfy the join condition # p与s满足join条件
      Then output the tuple <p,s> # 输出为结果集

可以看到相比 Simple Nested-Loop Join 算法，Block Nested-Loop Join 算法仅多了一个所谓的 Join Buffer，然为什么这样就能减少内表的扫描次数呢？下图相比更好地解释了 Block Nested-Loop Join 算法的运行过程：

可以看到 Join Buffer 用以缓存链接需要的列，然后以 Join Buffer 批量的形式和内表中的数据进行链接比较。就上图来看，记录 r1，r2 … rT 的链接仅需扫内表一次，如果 Join Buffer 可以缓存所有的外表列，那么链接仅需扫描内外表各一次，从而大幅提升 Join 的性能。

Block Nested-Loop Join 可被用于联接的类型是 ALL，index，range。

Join Buffer

变量 join_buffer_size

从上一节中可以发现 Join Buffer 是用来减少内表扫描次数的一种优化，但 Join Buffer 又没那么简单，在上一节中 Inside 君故意忽略了一些实现。

首先变量 join_buffer_size 用来控制 Join Buffer 的大小，调大后可以避免多次的内表扫描，从而提高性能。也就是说，当 MySQL 的 Join 有使用到 Block Nested-Loop Join，那么调大变量 join_buffer_size 才是有意义的。而前面的 Index Nested-Loop Join 如果仅使用索引进行 Join，那么调大这个变量则毫无意义。

变量 join_buffer_size 的默认值是 256K，显然对于稍复杂的 SQL 是不够用的。好在这个是会话级别的变量，可以在执行 SQL 前进行扩展。Inside 君建议在会话级别进行设置，而不是全局设置，因为很难给一个通用值去衡量。另外，这个内存是会话级别分配的，如果设置不好容易导致因无法分配内存而导致的宕机问题。

需要特别注意的是，变量 join_buffer_size 的最大值在 MySQL 5.1.22 版本前是 4G-1，而之后的版本才能在 64 位操作系统下申请大于 4G 的 Join Buffer 空间。

Join Buffer 缓存的对象

Join Buffer 缓存的对象是什么，这个问题相当关键和重要。然在 MySQL 的官方手册中是这样记录的：

Only columns of interest to the join are stored in the join buffer, not whole rows.

used columns 还是非常模糊。为此，Inside 君询问了好友李海翔，也是官方 MySQL 优化器团队的成员，他答复我的结果是：“所有参与查询的列”都会保存到 Join Buffer，而不是只有 Join 的列。

最后，Inside 君调试了 MySQL，在 sql_join_buffer.cc 文件中验证了这个结果。

比如下面的 SQL 语句，假设没有索引，需要使用到 Join Buffer 进行链接：

SELECT a.col3 FROM a, b
WHERE a.col1 = b.col2
AND a.col2 > ... AND b.col2 = ...

假设上述 SQL 语句的外表是 a，内表是 b，那么存放在 Join Buffer 中的列是所有参与查询的列，在这里就是（a.col1，a.col2，a.col3）。

通过上面的介绍，我们现在可以得到内表的扫描次数为：

Scan inner_table = (Rn * used_column_size) / join_buffer_size + 1

对于有经验的 DBA 就可以预估需要分配的 Join Buffer 大小，然后尽量使得内表的扫描次数尽可能的少，最优的情况是只扫描内表一次。

Join Buffer 的分配

需要牢记的是，Join Buffer 是在 Join 之前就进行分配，并且每次 Join 就需要分配一次 Join Buffer，所以假设有 N 张表参与 Join，每张表之间通过 Block Nested-Loop Join，那么总共需要分配 N-1 个 Join Buffer，这个内存容量是需要 DBA 进行考量的。

Join Buffer 可分为以下两类：

• regular join buffer
• incremental join buffer

regular join buffer 是指 Join Buffer 缓存所有参与查询的列， 如果第一次使用 Join Buffer，必然使用的是 regular join buffer。

incremental join buffer 中的 Join Buffer 缓存的是当前使用的列，以及之前使用 Join Buffer 的指针。在多次进行 Join 的操作时，这样可以极大减少 Join Buffer 对于内存开销的需求。

此外，对于 NULL 类型的列，其实不需要存放在 Join Buffer 中，而对于 VARCHAR 类型的列，也是仅需最小的内存即可，而不是以 CHAR 类型在 Join Buffer 中保存。最后，从 MySQL 5.6 版本开始，对于 Outer Join 也可以使用 Join Buffer。

Block Nested-Loop Join 总结

Block Nested-Loop Join 极大的避免了内表的扫描次数，如果 Join Buffer 可以缓存外表的数据，那么内表的扫描仅需一次，这和 Hash Join 非常类似。但是 Block Nested-Loop Join 依然没有解决的是 Join 比较的次数，其仍然通过Join 判断式进行比较。综上所述，到目前为止各 Join 算法的成本比较如下所示：

Batched Key Access Join

Index Nested-Loop Join 虽好，但是通过辅助索引进行链接后需要回表，这里需要大量的随机 I/O 操作。若能优化随机 I/O，那么就能极大的提升 Join 的性能。为此，MySQL 5.6 推出了 Batched Key Access Join，该算法通过常见的空间换时间，随机 I/O 转顺序 I/O，以此来极大的提升 Join 的性能。

Multi-Range Read Optimization（MRR）

在说明 Batched Key Access Join 前，首先介绍下 MySQL 5.6 的新特性 MRR — Multi-Range Read。这个特性根据 rowid 顺序地，批量地读取记录，从而提升数据库的整体性能。看下面的 SQL 语句的执行计划：

mysql> explain select * from orders
-> where o_orderdate >= '1993-08-01'
-> and o_orderdate < date_add( '1993-08-01' ,interval '3' month)\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: orders
partitions: NULL
type: range
possible_keys: i_o_orderdate
key: i_o_orderdate
key_len: 4
ref: NULL
rows: 143210
filtered: 100.00
Extra: Using index condition
1 row in set, 1 warning (0.00 sec)

上述的 SQL 语句需要根据辅助索引 i_o_orderdate 进行查询，但是由于要求得到的是表中所有的列，因此需要回表进行读取。而这里就可能伴随着大量的随机 I/O。这个过程如下图所示：

而 MRR 的优化在于，并不是每次通过辅助索引读取到数据就回表去取记录，而是将其 rowid 给缓存起来，然后对 rowid 进行排序后，再去访问记录，这样就能将随机 I/O 转化为顺序 I/O，从而大幅地提升性能。这个过程如下所示：

从上图可以发现 MRR 通过一个额外的内存来对 rowid 进行排序，然后再顺序地，批量地访问表。这个进行 rowid 排序的内存大小由参数 read_rnd_buffer_size 控制，默认 256K。

要开启 MRR 还有一个比较重要的参数是在变量 optimizer_switch 中的 mrr 和 mrr_cost_based 选项。mrr 选项默认为 on，mrr_cost_based 选项默认为 on。mrr_cost_based 选项表示通过基于成本的算法来确定是否需要开启 mrr 特性。然而，在 MySQL 当前版本中，基于成本的算法过于保守，导致大部分情况下优化器都不会选择 MRR 特性。为了确保优化器使用 MRR 特性，请执行下面的 SQL 语句：

mysql>set optimizer_switch='mrr=on,mrr_cost_based=off';

同样执行前面的 SQL 语句，可以发现这时优化的执行计划为：

mysql> explain select * from orders where
-> o_orderdate >= '1993-08-01'
-> and o_orderdate < date_add('1993-08-01' ,interval '3' month)\G
*************************** 1. row***************************
id: 1
select_type: SIMPLE
table: orders
partitions: NULL
type: range
possible_keys: i_o_orderdate
key: i_o_orderdate
key_len: 4
ref: NULL
rows: 143210
filtered: 100.00
Extra: Using index condition; Using MRR
1row in set, 1 warning (0.00 sec)

上面说到为了确保优化器使用 MRR 特性，把 MRR 的基于成本的算法关闭了（mrr_cost_based=off），不建议在实际使用中这么做，因为这相当于强制 MySQL 不考虑当前 SQL 的成本，只要使用了辅助索引就都走 MRR，这样一些回表成本不高的也会被强制执行 MRR。

最后来对比一下关闭和开启 MRR 特性后上述 SQL 的执行时间：

BKA Join

在讲述完 MRR 特性后，再来看 BKA Join 就非常清晰了。通过 MRR 特性优化 Join 的回表操作，从而提升 Join 的性能。BKA Join 算法的伪代码：

For each tuple r in R do
  store used columns as p from R in join buffer
  For each tuple s in S do
    If p and s satisfy the join condition
      use mrr interface to sort rowId
      Then output the tuple <p, s>

BKA Join 的整个过程如下所示：

然而，这么好的特性，却是在 MySQL 中默认关闭的，这可能是导致用户认为 MySQL Join 性能比较差的一个原因。若要使用 BKA Join，务必执行下列的 SQL 语句：

mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
Query OK, 0 rows affected (0.00 sec)

若开启了 BKA Join，则通过 EXPLAIN 命令，可以发现优化器的执行结果选项会有 Using join buffer (Batched Key Access) 的提示，如：

mysql> explain SELECT
-> COUNT(*)
-> FROM
-> part,
-> lineitem
-> WHERE
-> l_partkey， = p_partkey
-> AND p_retailprice > 2050 AND p_size < 100
-> AND l_discount > 0.04\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: part
partitions: NULL
type: ALL
possible_keys: PRIMARY
key: NULL
key_len: NULL
ref: NULL
rows: 196810
filtered: 11.11
Extra: Using where
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: lineitem
partitions: NULL
type: ref
possible_keys: i_l_suppkey_partkey,i_l_partkey
key: i_l_suppkey_partkey
key_len: 5
ref: dbt3_s1.part.p_partkey
rows: 28
filtered: 33.33
Extra: Using where; Using join buffer (Batched Key Access)
2 rows in set, 1 warning (0.00 sec)

最后来看下执行速度，可以发现 BKA 的提升非常明显：

再次强调一下关于上面把 MRR 的基于成本的算法关闭，这种操作不建议在实际使用中这么做。

MariaDB Join

MySQL 数据库虽然提供了 BKA Join 来优化传统的 JOIN 算法，的确在一定程度上可以提升 JOIN 的速度。但不可否认的是，仍然有许多用户对于 Hash Join 算法有着强烈的需求。Hash Join 不需要任何的索引，通过扫描表就能快速地进行 JOIN 查询，通过利用磁盘的带宽最大程度的解决大数据量下的 JOIN 问题。

MariaDB 支持 Classic Hash Join 算法，该算法不同于 Oracle 的 Grace Hash Join，但是也是通过 Hash 来进行连接，不需要索引，可充分利用磁盘的带宽。

Classic Hash Join

其实 MariaDB 的 Classic Hash Join 和 Block Nested Loop Join 算法非常类似（Classic Hash Join 也称为 Block Nested Loop Hash Join），并不是直接通过进行 JOIN 的键值进行比较，而是根据 Join Buffer 中的对象创建哈希表，内表通过哈希算法进行查找，从而在 Block Nested Loop Join 算法的基础上，又进一步减少了内表的比较次数，从而提升 JOIN 的查询性能。过程如下图所示：

同样地，如果 Join Buffer 能够缓存所有驱动表（外表）的查询列，那么驱动表和内表的扫描次数都将只有 1 次，并且比较的次数也只是内表记录数（假设哈希算法冲突为 0）。

Classic Hash Join 和 BKA Join 算法一样，需要强制开启，优化器无法做自动的选择，这点也是目前 MariaDB 和 MySQL 数据库都存在的问题。但是，MySQL 团队已经在重构优化器模块，相信不久的将来，这些问题将很快得到解决。

最后，各 JOIN 算法成本之间的比较如下表所示：

Hash Join 算法虽好，但是仅能用于等值连接，非等值连接的 JOIN 查询，其就显得无能为力了。另外，创建哈希表也是费时的工作，但是一旦建立完成后，其就能大幅提升 JOIN 的速度。所以通常情况下，大表之间的 JOIN，Hash Join 算法会比较有优势。小表通过索引查询，利用 BKA Join 就已经能很好的完成查询。

总结

本文介绍了 MySQL 数据库的各类 JOIN 算法，其中有 Index Nested-Loop Join、Block Nested-Loop Join、Batched Key Access Join 算法，最后还介绍了 MariaDB 的 Classic HashJoin 算法。通过本文，用户可以发现，虽然 MySQL 在 JOIN 算法的支持力度上远不如传统的 Oracle、Microsoft SQL Server 数据库，但是完成一般的 JOIN 查询任务是完全没有问题的。用户可能需要选对各种 JOIN 算法，然后根据不同算法进行参数调优，从而提升 JOIN 的速度。

不可否认的是 MySQL 的优化器现在还是存在缺陷的，如优化器无法直接选择 Batched Key Access Join 和 Classic Hash Join。好在 Oracle 官方已经在重构 MySQL 优化器模块，相信一个更好的基于成本计算的优化器终将来临。

即使 MySQL 未来支持 Hash Join，但是大数据的查询已经不是传统数据库适合解决的问题，未来这部分工作将越来越多地通过 Hadoop 这样的集群来解决。

转载

文章内容主要来自姜承尧大佬的四篇公众号文章，我把它们整合到一篇文章中，方便查看。

• MySQL Join算法与调优白皮书（一）
• MySQL Join算法与调优白皮书（二）
• MySQL Join算法与调优白皮书（三）
• MySQL Join算法与调优白皮书（四）

作者：殷建卫 链接：https://www.yuque.com/yinjianwei/vyrvkf/oeazs3 来源：殷建卫 - 架构笔记 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。