MySQL表连接算法

1. 前言

MySQL 属于关系型数据库，我们建的表大多也都存在业务上的关联关系，同时我们又不可能将所有的数据都冗余一份，这不符合数据库的设计范式。因此，当我们需要把多张表的数据融合在一起的时候，就需要使用到「多表连接查询」。

多表连接查询虽然用的很爽，但是常常会带来性能问题。大家可以回忆一下自己遇到的慢 SQL，大多数都是多表联查导致的。有的 DBA 甚至会要求严格限制连接查询中表的数量，理论上来说，连接表的数量越多，效率越低。表连接最坏的情况，就是「笛卡尔积」，它没有任何限制条件，结果集中包含一张表中所有的记录与其它表所有的记录相互匹配的组合。两张各一万条记录的表，产生的笛卡尔积就有一亿条记录，如果是三张表结果更是不敢想象。

大家也不用被笛卡尔积吓到，它只是最坏的结果而已，只要使用得当，连接查询的效率也可以很高。

2. 连接查询的过程

在介绍具体的连接算法前，我们先来熟悉一下 MySQL 连接查询的过程。现有两张表 t1、t2 结构如下：

CREATE TABLE t1(
 `id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
 `a` INT NOT NULL DEFAULT 0
)ENGINE=InnoDB AUTO_INCREMENT=1;

CREATE TABLE t2(
 `id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
 `b` INT NOT NULL DEFAULT 0
)ENGINE=InnoDB AUTO_INCREMENT=1;

使用存储过程向两张表格插入一些记录，然后执行下面这个 SQL：

SELECT * FROM t1 INNER JOIN t2 ON t2.b=t1.id WHERE t1.id<10;

对于左外连接和右外连接，表的连接顺序是固定的，MySQL 优化器能帮我们优化的点比较少，所以我们以内连接为主进行分析。对于内连接查询，表的连接顺序是可以互换的，因此 MySQL 优化器可以分别计算以 t1 为驱动表和以 t2 为驱动表的查询成本各是多少，然后选出执行成本更低的方案，也就是最终的执行计划。

具体执行成本的计算不在本文的讨论范围内，先跳过。

对于这个查询，我们指定了两个过滤条件：

t1.id < 10
t2.b = t1.id < 10

1、确定驱动表

MySQL 首先需要从 t1 和 t2 中确定谁是驱动表。对于内连接，表的连接顺序是可以互换的，意味着 t1 和 t2 都可以作为驱动表，就看谁的执行成本更低了。MySQL 会根据表/索引的统计数据或访问表中少量的数据来评估各自的执行成本，细节我们就先跳过。

2、驱动表获取到的每一条记录去被驱动表中进行匹配。

假设 t1 是驱动表，查询过程是这样的：

获取 t1 表中第一条 id<10 的记录。
拿着这个记录的 id 去查询 t2 表，条件是t2.b=t1.id，由于t2.b没有索引，所以只能对 t2 做全表扫描。符合条件的记录返回，不符合条件的记录丢弃。
获取 t1 表中第二条 id<10 的记录，重复前面的流程，直到 t1 表中没有 id<10 的记录了。

t1 表作为驱动表，只需要访问一次，且 id 是主键，因此t1.id<10可以使用range访问方法，效率还是很高的。问题在于对 t2 表的访问，由于t2.b没有索引，因此对于 t1 表中符合条件的每一条记录，都需要全表扫描一次 t2 表，这个开销是非常大的。

假设 t2 是驱动表，查询过程是这样的：

对 t2 进行全表扫描，取出第一条t2.b<10的记录。
拿着该记录列 b 的值，去查询 t1 表，条件是t1.id=t2.b。因为t1.id是主键，所以可以使用const访问方法，效率是很高的。
取出第二条t2.b<10的记录，重复前面的流程，直到 t1 表中没有 b<10 的记录了。

t2 表作为驱动表，只需要对 t2 全表扫描一次，但是需要对 t1 表的主键做等值匹配多次，匹配的次数取决于 t2 表中b<10的记录数量。

综上所述，t1 表作为驱动表最大的开销是需要对 t2 表进行多次全表扫描，全表扫描的次数取决于t1.id<10的记录数量。t2 表作为驱动表需要对 t2 全表扫描一次，但是需要对 t1 表主键等值匹配多次，匹配的次数取决于t2.b<10的记录数量。除非t1.id<10的记录足够的少，否则 MySQL 会跟偏向于使用 t2 作为驱动表，因为ALL比const访问效率要低的多。

笔者实测，对于t1.id<5MySQL 认为 t1 表过滤出的记录足够少，使用 t1 作为驱动表的成本更低。

mysql> EXPLAIN SELECT * FROM t1 INNER JOIN t2 ON t2.b=t1.id WHERE t1.id<5;
+----+-------------+-------+------------+-------+---------------+---------+---------+------+-------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                                              |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+-------+----------+----------------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | range | PRIMARY       | PRIMARY | 4       | NULL |     4 |   100.00 | Using where                                        |
|  1 | SIMPLE      | t2    | NULL       | ALL   | NULL          | NULL    | NULL    | NULL | 50424 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+-------+----------+----------------------------------------------------+

而对于t1.id<100MySQL 担心会对 t2 执行太多次全表扫描，因此更偏向于使用 t2 作为驱动表。

mysql> EXPLAIN SELECT * FROM t1 INNER JOIN t2 ON t2.b=t1.id WHERE t1.id<100;
+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+-------+----------+-------------+
| id | select_type | table | partitions | type   | possible_keys | key     | key_len | ref       | rows  | filtered | Extra       |
+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+-------+----------+-------------+
|  1 | SIMPLE      | t2    | NULL       | ALL    | NULL          | NULL    | NULL    | NULL      | 50424 |   100.00 | Using where |
|  1 | SIMPLE      | t1    | NULL       | eq_ref | PRIMARY       | PRIMARY | 4       | test.t2.b |     1 |   100.00 | NULL        |
+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+-------+----------+-------------+

Using join buffer (Block Nested Loop)代表 MySQL 使用了基于块的嵌套循环连接算法，减少全表扫描的次数。

3. 连接算法

MySQL 表连接查询，支持多种连接算法。

3.1 Simple Nested Loop Join

简单嵌套循环连接，最简单也最笨拙的一种算法。从 t1 表读取的每一条记录，都需要扫描 t2 表的所有记录进行匹配。这个过程就像是一个嵌套的循环，连接的表的数量就是循环嵌套的层数，当表中数据量较大，或者连接的表的数量过多时，这种算法的效率是极低的。

对于 t1 表获取到的每一条记录，都会立马去 t2 表进行匹配查询，而不会等 t1 表的记录检索完成了再去查询 t2。说白了，MySQL 并不会使用额外的空间来保存 t1 表记录的检索结果。

3.2 Index Nested Loop Join

第一种算法，t1 表过滤出多少条记录，就需要对 t2 表进行多少次全表扫描。对于 t1 表的每一条记录，其实都是一次针对于 t2 的单表查询，如果我们能优化每一次对 t2 的单表查询效率，也就能优化整个连接查询的效率了。

如何优化针对 t2 的单表查询效率？加索引啊！如果连接查询的过滤条件是 t2 表的列 b，那么就给列 b 加索引。如果加的是普通索引，那么访问方法可以从ALL优化为ref，如果加的是唯一索引，更是能直接优化为const。

3.3 Block Nested Loop Join

现在我们已经知道，如果不能通过索引来加速被驱动表的查询效率，MySQL 只能对被驱动表执行 N 次全表扫描了。如果表中的记录很少，碰巧机器的内存又很大，全表扫描尚且可以接受，因为内存可以容纳足够多的索引页，N 次全表扫描的开销也只需要将聚簇索引的叶子节点加载到内存中一次，后面都可以命中缓存了。然而现实情况是表中的数据通常会很多，且内存又十分紧张。这种场景下，InnoDB 加载完后面的索引页，前面的索引页缓存就不得不淘汰了，第二次全表扫描又得来一遍 IO，这个开销就没法接受了。MySQL 还能怎么优化呢？

MySQL 提出了一个名为 Join Buffer 的概念，连接缓冲区，在执行连接查询前先申请一块固定大小的内存空间，然后将驱动表中的若干条记录放到 Join Buffer 里，访问被驱动表时就可以一次性与 Join Buffer 里的所有记录进行匹配了，这样可以显著减少被驱动表的访问次数。理论上 Join Buffer 越大越好，最好能大到可以容纳驱动表过滤出的所有记录，这样被驱动表只需要全表扫描一次就好了。这种基于 Join Buffer 来减少被访问表的访问次数的算法，就是 Block Nested Loop Join。

Join Buffer 不会存放驱动表的所有列信息，只会存储 SELECT 查询的列和过滤条件涉及到的列，所以查询时要尽量避免使用 SELECT *

4. 总结

连接查询可以将多张表的数据汇总到一起，使用连接查询时要特别注意性能问题，最差的结果就是笛卡尔积。MySQL 支持多种连接查询算法，最简单最笨拙的就是简单嵌套循环连接，驱动表只需要访问一次，被驱动表要访问多次，访问次数取决于驱动表过滤出的记录数量。连接查询的主要开销，来自于对被驱动表的访问。驱动表过滤出的每一条记录其实都对应着被驱动表的一次单表查询，我们可以通过给被驱动表加索引的方式，来优化对被驱动表的查询效率，进而提高连接查询的效率，这就是基于索引的嵌套循环连接。如果实在是无法通过索引来提高连接查询的效率，MySQL 还可以通过 Join Buffer 性存储若干条驱动表的记录，访问被驱动表时就可以一次性与这些记录进行匹配了，显著减少访问被驱动表的次数。