这一篇文章就来介绍一下关联查询的优化，文章有点长，请耐心看完，有问题欢迎讨论指正。
1 关联查询的算法特性总结
要想弄懂关联查询的优化，就必须先知道关联查询相关的算法：
Join算法 | 解释 |
Simple Nested-Loop Join算法 | 遍历驱动表中的每一行，每一行再到被驱动表中全表扫描，如果满足关联条件，则返回结果 |
Index Nested-Loop Join算法 | 遍历驱动表中的每一行，都通过索引找到被驱动表中关联的记录，如果满足关联条件，则返回结果 |
Block Nested-Loop Join算法 | 把驱动表的数据读入到 join_buffer 中，把被驱动表每一行取出来跟 join_buffer 中的数据做对比，如果满足 join 条件，则返回结果 |
Hash Join算法 | 将驱动表的数据加载到内存中构建哈希表，然后逐行读取被驱动表的数据，并通过哈希函数将连接条件的列的值映射为哈希值，查找匹配的哈希值，最后返回匹配的结果给客户端，跟Block Nested-Loop Join算法类似，但是不需要将被驱动表的数据块写入内存或磁盘，更少的IO以及更节省资源 |
Batched Key Access算法 | 将驱动表中相关列放入 join_buffer 中 批量将关联字段的值发送到 Multi-Range Read(MRR) 接口 MRR 通过接收到的值，根据其对应的主键 ID 进行排序，然后再进行数据的读取和操作 返回结果给客户端 |
2 Simple Nested-Loop Join算法
图片
循环驱动表中的每一行
再到被驱动表找到满足关联条件的记录
因为关联字段没索引，所以在被驱动表里的查询需要全表扫描
这种方法逻辑简单，但是效率很差
比如驱动表数据量是 m，被驱动表数据量是 n，则扫描行数为 m * n
当然，好在，MySQL也没有采用这种算法，即使关联字段没索引，也会采用Block Nested-Loop Join或者Hash Join，等下会细说。
3 Index Nested-Loop Join算法
刚才我们说的是关联字段没索引的情况，假如关联字段有索引，就会采用Index Nested-Loop Join算法（一般简写成：NLJ）
图片
一次一行循环地从第一张表（称为驱动表）中读取行，在这行数据中取到关联字段，根据关联字段在另一张表（被驱动表）里，通过索引匹配，取出满足条件的行，然后取出两张表的结果合集。
为了方便理解，我们会结合实验进行讲解，先来创建测试表并写入测试数据：
use martin;
drop table if exists t1;
CREATE TABLE `t1` (
`id` int NOT NULL auto_increment,
`a` int DEFAULT NULL,
`b` int DEFAULT NULL,
`create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '记录创建时间',
`update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP
COMMENT '记录更新时间',
PRIMARY KEY (`id`),
KEY `idx_a` (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
drop procedure if exists insert_t1;
delimiter ;;
create procedure insert_t1()
begin
declare i int;
set i=1;
while(i<=10000)do
insert into t1(a,b) values(i, i);
set i=i+1;
end while;
end;;
delimiter ;
call insert_t1();
drop table if exists t2;
create table t2 like t1;
insert into t2 select * from t1 limit 100;我们来看一个例子：
explain select * from t1 inner join t2 on t1.a = t2.a;Tips：表 t1 和表 t2 中的 a 字段都有索引。
执行计划如下：
图片
从执行计划中可以看到这些信息：
驱动表是 t2，被驱动表是 t1。原因是：explain 分析 join 语句时，在第一行的就是驱动表；选择 t2 做驱动表的原因：如果没固定连接方式（比如没加 straight_join）,优化器会优先选择小表做驱动表。所以使用 inner join 时，前面的表并不一定就是驱动表。
使用了 NLJ。原因是：一般 join 语句中，如果执行计划 Extra 中未出现 Using join buffer （***）；则表示使用的 join 算法是 NLJ。
4 Block Nested-Loop Join算法
如果被驱动表的关联字段没索引，在MySQL 8.0.20版本之前，就会使用 Block Nested-Loop Join(简称：BNL)
图片
Block Nested-Loop Join(BNL) 算法的思想是：把驱动表的数据读入到 join_buffer 中，然后扫描被驱动表，把被驱动表每一行取出来跟 join_buffer 中的数据做对比，如果满足 join 条件，则返回结果给客户端。
我们一起看看下面这条 SQL 语句：
select * from t1 inner join t2 on t1.b = t2.b;Tips：表 t1 和表 t2 中的 b 字段都没有索引
在 MySQL 5.7 版本下的执行计划如下：
图片
在 Extra 发现 Using join buffer (Block Nested Loop)，这个就说明该关联查询使用的是 BNL 算法。
在 MySQL 8.0.25 版本下的执行计划如下：
图片
在 Extra 发现 Using join buffer (hash join)，因为前面提到，从 MySQL 8.0.20 开始，哈希连接替换了块嵌套循环。
5 Hash Join算法
从 MySQL 8.0.20 开始，MySQL 不再使用 Block Nested-Loop Join 算法，并且在以前使用 Block Nested-Loop Join 算法的所有情况下都使用 Hash Join 优化。
图片
核心思想是将驱动表的数据加载到内存中构建哈希表
然后逐行读取被驱动表的数据，并通过哈希函数将连接条件的列的值映射为哈希值，去之前构建的Hash表查找匹配的记录
一旦在Hash表中找到匹配的记录，对这些记录进行一一比较，得出最终的Join结果
跟Block Nested-Loop Join算法类似，但是不需要将被驱动表的数据块写入内存或磁盘，更少的IO以及更节省资源
6 Batched Key Access算法
在学了 NLJ 和 BNL 算法后，你是否有个疑问，如果把 NLJ 与 BNL 两种算法的一些优秀的思想结合，是否可行呢？
比如 NLJ 的关键思想是：被驱动表的关联字段有索引。
而 BNL 的关键思想是：把驱动表的数据批量提交一部分放到 join_buffer 中。
从 MySQL 5.6 开始，确实出现了这种集 NLJ 和 BNL 两种算法优点于一体的新算法：Batched Key Access(BKA)。
图片
其原理是：
将驱动表中相关列批量放入 join_buffer 中
批量将关联字段的值发送到 Multi-Range Read(MRR) 接口
MRR 通过接收到的值，根据其对应的主键 ID 进行排序，然后再进行数据的读取和操作
返回结果给客户端。
7 补充下MRR相关知识
当表很大并且没有存储在缓存中时，使用辅助索引上的范围扫描读取行可能导致对表有很多随机访问。
而 Multi-Range Read 优化的设计思路是：查询辅助索引时，对查询结果先按照主键进行排序，并按照主键排序后的顺序，进行顺序查找，从而减少随机访问磁盘的次数。
使用 MRR 时，explain 输出的 Extra 列显示的是 Using MRR。
控制MRR的参数
optimizer_switch 中 mrr_cost_based 参数的值会影响 MRR。
如果 mrr_cost_based=on，表示优化器尝试在使用和不使用 MRR 之间进行基于成本的选择。
如果 mrr_cost_based=off，表示一直使用 MRR。
更多 MRR 信息请参考官方手册：https://dev.mysql.com/doc/refman/8.0/en/mrr-optimization.html。
8 BKA开启
先来看下这条SQL的执行计划：
explain select * from t1 inner join t2 on t1.a = t2.a;
图片
下面尝试开启 BKA ：
set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';这里对上面几个参数做下解释：
- mrr=on 开启 mrr
- mrr_cost_based=off 不需要优化器基于成本考虑使用还是不使用 MRR，也就是一直使用 MRR
- batched_key_access=on 开启 BKA
然后再看 sql1 的执行计划：
explain select * from t1 inner join t2 on t1.a = t2.a;
图片
在 Extra 字段中发现有 Using join buffer (Batched Key Access)，表示确实变成了 BKA 算法。
9 优化关联查询
扯了这么多，我们就来讲一下：究竟怎样优化关联查询：
关联字段添加索引
通过上面的内容，我们知道了 BNL、NLJ 和 BKA 的原理，因此让 BNL（Block Nested-Loop Join）或者Hash Join变成 NLJ （Index Nested-Loop Join）或者 BKA（Batched Key Access），可以提高 join 的效率。我们来看下面的例子
我们构造出两个算法对于的例子：
Block Nested-Loop Join 的例子：
select * from t1 join t2 on t1.b= t2.b;需要 0.08 秒。
Index Nested-Loop Join 的例子：
select * from t1 join t2 on t1.a= t2.a;只需要 0.01 秒。
再对比一下两条 SQL 的执行计划：
图片
前者扫描的行数是 100 和 9963。
对比执行时间和执行计划，再结合在本节开始讲解的两种算法的执行流程，很明显 Index Nested-Loop Join 效率更高。
因此建议在被驱动表的关联字段上添加索引，让 BNL或者Hash Join变成 NLJ 或者 BKA ，可明显优化关联查询。
选择小表作为驱动表
从上面几种Join算法，也能看出来，驱动表需要全表扫描，再存放在内存中
如果小表是驱动表，那遍历的行也会更少。
来举个例子，看下大小表做驱动表执行计划的对比：
我们来看下以 t2 为驱动表的 SQL：
select * from t2 straight_join t1 on t2.a = t1.a;这里使用 straight_join 可以固定连接方式，让前面的表为驱动表。
再看下以 t1 为驱动表的 SQL：
select * from t1 straight_join t2 on t1.a = t2.a;我们对比下两条 SQL 的执行计划：
图片
明显前者扫描的行数少（注意关注 explain 结果的 rows 列），所以建议小表驱动大表。
当然，如果是普通的join语句，一般不需要我们去处理，优化器默认也会选择小表做为驱动表。
数据集较大可以采用BKA优化
BKA算法采用批量处理机制，利用索引快速定位匹配记录，适合大型数据集的Join操作
版本升级
前面也提到了，如果被驱动表的关联字段没索引，在MySQL 8.0.20版本之前，就会使用 Block Nested-Loop Join(简称：BNL)，
从 MySQL 8.0.20 开始，MySQL 不再使用 Block Nested-Loop Join 算法，并且在以前使用 Block Nested-Loop Join 算法的所有情况下都使用 Hash Join 优化。
相对于Block Nested-Loop Join算法，Hash Join不需要将被驱动表的数据块写入内存或磁盘，使用更少的IO以及更节省资源。
所以，假如有条件，可以升级到8.0.20之后的版本。
