面试官：你们项目中用到多表关联了吗？

我们来看这样一个面试场景。

面试官：“在你们的项目中，用到多表关联查询了吗？”

候选人：“嗯，每个项目都用到了。”

面试官听了似乎有些愤怒，说：“多表关联查询这么慢，为什么你们还要用它，那你们项目的性能如何保障呢？”

面对这突如其来地质问，候选人明显有些慌了，解释道：“主要是项目周期太紧张了，这样写在开发效率上能高一些，后期我们会慢慢进行优化的。”

面试官听了，带着三分理解、三分无奈、四分恨铁不成钢地摇了摇头。

面试之后，这个同学问我说：“学长，是不是在项目中使用多表关联太low了，可是从业这五年多，我换过三家公司，哪个公司的项目都是这么用的。”

下面我来从实现原理的角度，回答一下这个问题。

“是否应该使用多表关联”，这绝对是个王炸级别的话题了，其争议程度，甚至堪比“中医废存之争”了。

一部分人坚定地认为，应该禁止使用SQL语句进行多表关联，正确的方式是把各表的数据读到应用程序中来，再由程序进行数据merge操作。

而另一部分人则认为，在数据库中进行多表关联是没有问题的，但需要多关注SQL语句的执行计划，只要别产生过大的资源消耗和过长的执行时间即可。

嗯，我完全支持后者的观点，况且MySQL在其底层算法的优化上，一直在努力完善。

MySQL表连接算法

我们以最常用的MySQL数据库为例，其8.0版本支持的表连接算法为Nested-Loops Join（嵌套循环连接）和Hash Join（哈希连接）。

如下图所示：

嵌套循环连接算法，顾名思义，其实现方式是通过内外层循环的方式进行表连接，SQL语句中有几个表进行连接就实现为几层循环。

接下来，我们看看嵌套循环连接算法的四种细分实现方式。

1、简单嵌套循环连接（Simple Nested-Loops Join）

这是嵌套循环连接中最简单粗暴的一种实现方式，直接用驱动表A中符合条件的数据，一条一条地带入到被驱动表B中，进行全表扫描匹配。

其伪代码实现为：

for each row in table A matching range {
     for each row in table B matching join column{
           if row satisfies join conditions，send to client
     }
}

我们以下面的SQL语句举例：

SELECT * FROM product p INNER JOIN order o ON p.id = o.product_id;

其对应的详细执行步骤为：

（1）外循环从product表中每次读取一条记录。

（2）以内循环的方式，将该条记录与order表中的记录进行关联列的逐一比较，并找到匹配记录。

（3）将product表中的记录和order表中的匹配记录进行关联，放到结果集中。

（4）重复执行步骤1、2、3，直到内外两层循环结束。

也就是说，如果驱动表A中符合条件的数据有一万条，那么就需要带入到被驱动表B中进行一万次全表扫描，这种查询效率会非常慢。因此，除非特殊场景，否则查询优化器不太会选择这种连接算法。

2、索引嵌套循环连接（Index Nested-Loops Join）

接上文，如果在被驱动表B的关联列上创建了索引，那MySQL查询优化器极大概率会选择这种这种实现方式，因为其非常高效。

我们依然以下面的SQL语句举例：

SELECT * FROM product p INNER JOIN order o ON p.id = o.product_id;

其对应的详细执行步骤为：

（1）外循环从product表中每次读取一条记录。

（2）以内循环的方式，将该条记录与order表中关联列的索引进行匹配，直接找到匹配记录。

（3）将product表中的记录和order表中的匹配记录进行关联，放到结果集中。

（4）重复执行步骤1、2、3，直到内外两层循环结束。

这里需要说明一下，若order表的关联列是主键索引，则可以直接在表中查到记录；若order表的关联列是二级索引，则通过索引扫描的方式查到记录的主键，然后再回表查到具体记录。

3、缓存块嵌套循环连接（Block Nested-Loops Join）

我们在上文中说过，在简单嵌套循环连接中，如果驱动表A中符合条件的数据有一万条，那么就需要带入到被驱动表B中进行一万次全表扫描，这种查询效率会非常慢。

而缓存块嵌套循环连接，则正是针对于该场景进行的优化。

当驱动表A进行循环匹配的时候，数据并不会直接带入到被驱动表B，而是使用Join Buffer（连接缓存）先缓存起来，等到Join Buffer满了再去一次性关联被驱动表B，这样可以减少被驱动表B被全表扫描的次数，提升查询性能。

其伪代码实现为：

for each row in table A matching range {
    store join column in join buffer
    if（join buffer is full）{
        for each row in table B matching join column{
            if row satisfies join conditions，send to client
        }
    }
}

我们依然以下面的SQL语句举例：

SELECT * FROM product p INNER JOIN order o ON p.id = o.product_id;

其对应的详细执行步骤为：

（1）外循环从product表中每次读取一定数量的记录，将Join Buffer装满。

（2）以内循环的方式，将Join Buffer中记录与order表中的记录进行关联列的逐一比较，并找到匹配记录。

（3）将product表中的记录和order表中的匹配记录进行关联，放到结果集中。

（4）重复执行步骤1、2、3，直到内外两层循环结束。

需要注意的是，从MySQL 8.0.20开始，MySQL就不再使用缓存块嵌套循环连接了，将以前使用缓存块嵌套循环连接的场景全部改为哈希连接。

所以，MySQL的研发者一直在努力优化这款产品，其产品本身也没有大家所想的那么弱鸡。

4、批量键访问连接（Batched Key Access Joins）

说到这里，不得不先提一下MySQL5.6版本的新特性，多范围读（Multi-Range Read）。

我们继续拿product表的场景进行举例。

SELECT * FROM product WHERE price > 5 and price < 20;

没有使用MRR的情况下：

由上图可见，在MySQL InnoDB中使用二级索引的范围扫描时，所获取到的主键ID是无序的，因此在数据量很大的情况下进行回表操作时，会产生大量的磁盘随机IO，从而影响数据库性能。

使用MRR的情况下：

显而易见的是，在二级索引和数据表之间增加了一层buffer，在buffer中进行主键ID的排序操作，这样回表操作就从磁盘随机I/O转化为顺序I/O，并可减少磁盘的I/O次数（1个page里面可能包含多个命中的record），提高查询效率。

而从MySql 5.6开始支持Batched Key Access Joins，则正是结合了MRR和Join Buffer，以此来提高多表关联的执行效率，其发生的条件为被驱动表B有索引，并且该索引为非主键。

其伪代码实现和详细步骤为：

for each row in table A matching range {
    store join column in join buffer
    if（join buffer is full）{       
        for each row in table B matching join column{
            send to MRR interface，and order by its primary key
            if row satisfies join conditions，send to client
        }
    }
}

另外，如果查询优化器选择了批量键访问连接的实现方式，我们可以在执行计划中的Extra列中看到如下信息：

Using where; Using join buffer (Batched Key Access)

结语

在本文中，我们介绍了嵌套循环连接的四种实现方式，下文会继续讲解哈希连接算法，以及跟在程序中进行多表数据merge的实现方式进行对比。