Join 语句执行过程性能差，原因可能是什么？哪里需要建立索引？

小伙伴蚂蚁金服二面遇到的三道题：

1. SQL 查询语句：SELECT * FROM A JOIN B ON A.id = B.id，执行过程性能差，原因可能是什么？
2. 上述 SQL 语句的执行过程是什么？哪里需要建立索引？
3. 在 A.id 还是 B.id 上建立索引呢？

可能你会一脸懵逼，But 实际上，其实考的就是 join 这个知识点，不难，看完这篇文章你就会啦~

老规矩，背诵版在文末。

join 基本语法

MySQL 中常见的有三种用法：

select * from table1 inner join table2 on condition
select * from table1 left join table2 on condition
select * from table1 right join table2 on condition

• inner join：内连接（等值连接）
• left join：左连接
• right join：右连接

下面用例子来解释这三种用法，假设有两张表，用户表 user 和部门表 depart：

inner join

select user.name, user.age, depart.department 
from user inner join depart 
on user.name = depart.name; 

inner join 获取同时符合两张表的数据并组合起来。

在这个例子中，就是在 user 表和 depart 表中找到 name 相同的行记录，并组合起来

来看实际的执行结果：

需要注意的是，如果不指定 on 条件进行过滤的话，取得的结果就是两张表的笛卡尔积

什么是笛卡尔积 ？ 举个例子，两个集合 A{1, 2, 3} 和 B{a, b, c}，则两个集合的笛卡尔积为 {1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c}

select user.name, user.age, depart.department 
from user inner join depart;

光看这个例子大伙儿可能觉得笛卡尔积没啥用，其实还是很常见的，举个例子：如果 A 表示某学校学生的集合，B 表示该学校所有课程的集合，则 A 与 B 的笛卡尔积就表示这个学校所有可能的选课情况（梦回大一被数据库支配的恐惧 🤯）。

另外，多提一嘴，可能有小伙伴还见过 cross join，在 MySQL 中 cross join 与 inner join 的作用是一样的。并且，可以直接省略掉 cross 或者 inner 关键字：

left join

select user.name, user.age, depart.department 
from user left join depart 
on user.name = depart.name; 

left join 取得左表的所有记录，即使右边这个表没有对应的匹配记录(如果没有相匹配的话，用 null 代替)。

在这个例子中，就是获取 user 表的所有记录，然后根据 on 条件去 depart 表中查询，如果有相同的 name，就组合起来，如果 depart 表中找不到和 user 表具有相同 name 的记录，就用 NULL 代替。

来看实际的执行结果：

right join

select user.name, user.age, depart.department 
from user right join depart 
on user.name = depart.name; 

和 left join 相反，right join 取得右表的所有记录，即使左边这个表没有对应的匹配记录(如果没有相匹配的话，用 null 代替)。

在这个例子中，就是获取 depart 表的所有记录，然后根据 on 条件去 user 表中查询，如果有相同的 name，就组合起来，如果 user 表中找不到和 depart 表具有相同 name 的记录，就用 NULL 代替。

来看实际的执行结果：

full join

回顾下上面三张图，小伙伴们不知道有没有感觉缺了点什么，为啥没有把两个圆都填满的？

把两个圆都填满的学名叫作 full join，But，MySQL 中并没有 full join 的语法，需要借助 union 关键字来实现：

select user.name, user.age, depart.department 
from user left join depart 
on user.name = depart.name

union

select user.name, user.age, depart.department 
from user right join depart 
on user.name = depart.name;

针对 join 语句该如何建立索引、如何选择驱动表

先来解释下驱动表的概念，以 left join 为例：

select user.name, user.age, depart.department 
from user left join depart 
on user.name = depart.name; 

就是获取 user 表的所有记录，然后根据 on 条件去 depart 表中查询，如果有相同的 name，就组合起来，如果 depart 表中找不到和 user 表具有相同 name 的记录，就用 NULL 代替。

在这个例子中，驱动表就是 user，是主动发起查询的表，被驱动表是 depart，是根据 on 条件被查询的表。

当然了，MySQL 优化器其实会对驱动表有一个选择的过程，并不会固定说就是 user 或者就是 depart，为了便于下面的分析，我们可以用 straight_join 来固定驱动表。

select * 
from user straight_join depart 
on user.name = depart.name;

现在，user 表是驱动表，depart 表是被驱动表

假设，我们往 user 表中插入了 100 行数据，depart 表中插入了 1000 行数据。下面开始分析 👇

Index Nested-Loop Join

如果我们在被驱动表 depart 的字段 name 上建立索引，那么，上面这条语句的执行流程就是这样的：

1. 从 user 表中读入一行数据 R
2. 从数据行 R 中，取出 name 字段到表 depart 的 name 索引树上去找并取得对应的主键
3. 根据主键回表查询，取出 depart 表中满足条件的行，然后跟 R 组成一行，作为结果集的一部分
4. 重复执行步骤 1 到 3，直到 user 表的末尾则循环结束

文字看不太懂？没关系，来看下面代码的表示：

这条语句的执行过程就跟我们写程序时的嵌套查询 (Nested) 类似，并且可以用上被驱动表 depart 的索引 (Index)，所以我们称之为 Index Nested-Loop Join，简称 NLJ

来分析下这套流程的时间复杂度：

首先，遍历了一遍 user 表，一共扫描了 100 行；然后，对这每一行都去 depart 表中根据 name 字符进行搜索，由于 depart 表上建立了 name 字段的索引，所以每次搜索只需要扫描一行就行了（假设 depart 表中的 name 是 unique，无重复），这样，depart 表上一共只需要扫描 100 行。

所以，这套流程总共需要扫描 100 + 100 = 200 行。

❓ 各位小伙伴们再来思考一下，如果这条语句不用 join，该怎么实现。

流程大概是这样的：

1. 执行 select * from user，查出表 user 的所有数据，这里有 100 行，对吧
2. 循环遍历这 100 行数据：
   • 从每一行 R 取出字段 age 的值 R.a；
   • 执行 select * from depart where a = R.a
   • 把返回的结果和 R 组合构成结果集的一行

可以看到，这套流程一共需要扫描的行数其实也是 200 行

但是！这套流程里，select * from user 执行了 1 次，select * from depart where a = R.a 执行了 100 次，总共需要和数据库进行 101 次交互，而使用 join 的那套流程只需要 1 次交互就可以了。

高下立见。

✅ 上面的语句是基于 straight_join 来固定驱动表的，现在我们来分析下，我们具体该如何选取驱动表呢？

在这个 join 语句执行过程中，驱动表走的是全表扫描，而被驱动表由于用上了索引，所以走的是 B+ 索引树的搜索

• 假设驱动表的行数是 N，执行过程就要扫描驱动表 N 行，然后对于每一行，到被驱动表上匹配一次。时间复杂度 N
• 假设被驱动表的行数是 M。每次在被驱动表查一行数据，要先搜索 name 的辅助索引树，然后再回表搜索主键索引树，搜索一棵树的近似复杂度是 log2M，所以在被驱动表上查一行的时间复杂度就是 2 * log2M

因此整个执行过程，近似复杂度是 N + N * 2 * log2M

⭐ 显然，驱动表行数 N 对扫描行数的影响更大，因此应该让小表来做驱动表。

多提一嘴，并不是哪个表的行数少哪个表就是 “小表”，需要结合过滤条件来判断，计算参与 join 的各个字段的总数据量，数据量小的那个表，才是 “小表”

But，需要注意的是，这个结论的前提是 “可以使用被驱动表的索引”

接下来，我们再看看被驱动表用不上索引的情况 👇

Simple Nested-Loop Join

假设 depart 表上并没有 name 字段的索引，再来看这条语句的执行流程：

select * 
from user straight_join depart 
on user.name = depart.name;

由于表 depart 的字段 name 上没有索引，因此每次到 depart 去匹配的时候，就要做一次全表扫描，整个执行流程是这样的：

1. 从 user 表中读入一行数据 R
2. 从数据行 R 中，取出 name 字段到表 depart 上做全表查询，并取得对应的主键
3. 根据主键回表查询，取出 depart 表中满足条件的行，然后跟 R 组成一行，作为结果集的一部分
4. 重复执行步骤 1 到 3，直到 user 表的末尾则循环结束

显然，这条语句要全表扫描 depart 表多达 100 次，总共扫描 100 * 1000 = 10 万行

。。。。。。

这个笨重的算法也有个名字，叫 Simple Nested-Loop Join，简称 SNL

当然了，这么 ** 的算法一定是不会被 MySQL 使用的，而是使用了另一个叫作 Block Nested-Loop Join 的算法，简称 BNL 👇

Block Nested-Loop Join

BNL 引入了 join_buffer 的概念（别慌，很简单），感觉不需要多作解释，我们直接来看 BNL 的执行流程：

1. 把表 user 中的数据读入线程内存 join_buffer 中，由于我们这个语句中写的是 select *，因此是把整个表 user 都放入了内存
2. 扫描表 depart，把表 depart 中的每一行取出来，跟 join_buffer 中的数据做对比，满足 on 条件的，就作为结果集的一部分返回

上张图看一下：

需要注意的是，join_buffer 中的数据都是无序存储的。基于这点，我们来分析下时间复杂度：

首先，扫描 user 表全部数据并加入 join_buffer，一共 100 行；然后，对表 depart 中的每一行，取出来跟 join_buffer 中的数据分别做判断，每行数据都需要做 100 次判断，因此，总共需要做的判断次数是：100 * 1000 = 10 万次

这么一分析好像和 SNL 的时间复杂度差不多了？

确实，But，这个操作是在 join_buffer 也就是内存中做的，所以速度上会快很多

❓ 不过，看到这里，我想大伙儿还是没明白，这个 Block Nested-Loop 中的 Block 体现在哪里呢?

很简单，join_buffer 的大小肯定是有限的啊，它是由参数 join_buffer_size 设定的，默认值是 256k，如果表 user 中的数据比较大，join_buffer 一次性放不下怎么办？

分块！！！或者说，分块去 join

假设我们调小了 join_buffer_size，使得 user 表在存入第 60 行数据的时候 join_buffer 就存不下了，来看整个的执行流程是什么样的：

1. 扫描表 user，顺序读取数据行放入 join_buffer 中，放完第 60 行 时 join_buffer 满了，执行下一步
2. 扫描表 depart，把 depart 中的每一行取出来，跟 join_buffer 中的数据做对比，满足 join 条件的，作为结果集的一部分返回
3. 清空 join_buffer（重点就是这一步）
4. 继续扫描表 user，顺序读取最后的 40 行数据放入 join_buffer 中，然后继续执行第 2 步

这样，总共需要做的判断次数仍然是 (60 + 40) * 1000 = 10 万次。

✅ 我们再来看下，在这种情况下该如何选择驱动表：

假设，驱动表的数据行数是 N，join_buffer 被分成了 K 段，被驱动表的数据行数是 M：

1. 内存判断 N * M 次。显然，内存判断次数是不受选择哪个表作为驱动表影响的
2. 扫描行数是 N + K * M。另外，N 越大 K 就越大，所以可以把 K 表示为 λ * N，λ 取值范围是 0~1，也即扫描行数是 N + λ * N * M 在 M 和 N 大小确定的情况下，N 越小，整个算式的结果越小。所以结论是，应该让小表当驱动表。 另外，λ 作为式子的参数其实也非常重要，这个值越小就代表分的段越少，即一次可以放入 join_buffer 的行越多，这样，对被驱动表的全表扫描次数就越少。所以，调大 join_buffer_size 也是一个明智的选择。

小结

小结一下，可以看到，对于 join 语句来说，最好的情况就是可以用上被驱动表的索引，这样用的就是 INL 算法，比不用 join 语句的普通嵌套查询性能要好。而如果用不上被驱动表的索引话，无论是 SNL 还是使用 join_buffer 的 BNL，其实代价都是比较大的，都会占用大量的系统资源。

至于 join 语句的驱动表问题，我们总是应该使用小表做驱动表（并不是哪个表的行数少哪个表就是 “小表”，需要结合过滤条件来判断，计算参与 join 的各个字段的总数据量，数据量小的那个表，才是 “小表”）。

最后放上这道题的背诵版：

🥸 面试官：select * from A join B on A.name = B.name; 执行过程性能差，原因可能是什么？哪里需要建立索引? 😎 小牛肉：这条语句性能差的原因可能是被驱动表 B 没有建立 name 索引。 这样的话，MySQL 使用的就是 Block Nested-Loop 算法，具体来说，MySQL 首先把表 A 中的数据读入线程内存 join_buffer 中；然后扫描表 B，把表 B 中的每一行取出来，跟 join_buffer 中的数据做对比，满足 on 条件的，就作为结果集的一部分返回 join_buffer 中的数据都是无序存储的，由于没有用上被驱动表的索引，所以对表 B 中的每一行，取出来后需要跟 join_buffer 中的所有数据分别做判断，假设 A 表 100 行， B 表 1000 行，那么总共需要做的判断次数是：100 * 1000 = 10 万次 为什么说 BNL 算法的性能比较差呢，我们可以看一下如果能够用上被驱动表 B 的索引的情况 这个算法就是 Index Nested-Loop 算法，具体步骤其实就是一个嵌套查询，首先，遍历 A 表，一共需要扫描 100 行；然后，对这每一行都去 B 表中根据 name 字段进行搜索，由于 B 表上建立了 name 字段的索引，所以每次搜索只需要在 name 辅助索引树上扫描一行就行了（额这里我们假设 B 表中的 name 是 unique 的，无重复），这样，B 表上一共只需要扫描 100 行。 所以，INL 算法总共只需要扫描 100 + 100 = 200 行。 所以说，对于这条语句，我们可以在 B 表的 name 字段上建立索引。 另外，对于用不上被驱动表索引的 BNL 算法来说，这个 join_buffer 的大小是有限的，由参数 join_buffer_size 设定，如果表 A 中的数据比较大，join_buffer 一次性放不下的话就会进行分块，就是每次 join_buffer 存满之后，把 B 表中数据取出来进行判断，判断完了之后把 join_buffer 清空，然后再取出 A 表中剩下的数据放入 join_buffer，如此循环。 所以可以看出来，这个 join_buffer 分的块越多，我们需要遍历 B 表的次数越多，所以，增大 join_buffer_size 也就是减少分块，也可以在一定程度上提升这条语句的性能。

流水不争先，争的是滔滔不绝，我是小牛肉，小伙伴们下篇文章再见 👋