用不用join

在实际生产中，关于join语句使用的问题，一般会集中在以下两类：

  1. 我们DBA不让使用join，使用join有什么问题呢？
  2. 如果有两个大小不同的表做join，应该用哪个表做驱动表呢？

今天这篇文章，我就先跟你说说join语句到底是怎么执行的，然后再来回答这两个问题。
为了便于量化分析，我还是创建两个表t1和t2来和你说明。

  1. CREATE TABLE `t2` (
  2.   `id` int(11) NOT NULL,
  3.   `a` int(11) DEFAULT NULL,
  4.   `b` int(11) DEFAULT NULL,
  5.   PRIMARY KEY (`id`),
  6.   KEY `a` (`a`)
  7. ) ENGINE=InnoDB;
  8. drop procedure idata;
  9. delimiter ;;
  10. create procedure idata()
  11. begin
  12.   declare i int;
  13.   set i=1;
  14.   while(i<=1000)do
  15.     insert into t2 values(i, i, i);
  16.     set i=i+1;
  17.   end while;
  18. end;;
  19. delimiter ;
  20. call idata();
  21. create table t1 like t2;
  22. insert into t1 (select * from t2 where id<=100)

可以看到，这两个表都有一个主键索引id和一个索引a，字段b上无索引。存储过程idata()往表t2里插入了1000行数据，在表t1里插入的是100行数据。

Index Nested-Loop Join

我们来看一下这个语句：

  1. select * from t1 straight_join t2 on (t1.a=t2.a);

如果直接使用join语句，MySQL优化器可能会选择表t1或t2作为驱动表，这样会影响我们分析SQL语句的执行过程。所以，为了便于分析执行过程中的性能问题，我改用straight_join让MySQL使用固定的连接方式执行查询，这样优化器只会按照我们指定的方式去join。在这个语句里，t1 是驱动表，t2是被驱动表。
现在，我们来看一下这条语句的explain结果。
Join使用以及优化 - 图1
图1 使用索引字段join的 explain结果
可以看到，在这条语句里，被驱动表t2的字段a上有索引，join过程用上了这个索引，因此这个语句的执行流程是这样的：

  1. 从表t1中读入一行数据 R；
  2. 从数据行R中，取出a字段到表t2里去查找；
  3. 取出表t2中满足条件的行，跟R组成一行，作为结果集的一部分；
  4. 重复执行步骤1到3，直到表t1的末尾循环结束。

这个过程是先遍历表t1，然后根据从表t1中取出的每行数据中的a值，去表t2中查找满足条件的记录。在形式上，这个过程就跟我们写程序时的嵌套查询类似，并且可以用上被驱动表的索引，所以我们称之为“Index Nested-Loop Join”，简称NLJ。
它对应的流程图如下所示：
Join使用以及优化 - 图2
图2 Index Nested-Loop Join算法的执行流程
在这个流程里：

  1. 对驱动表t1做了全表扫描，这个过程需要扫描100行；
  2. 而对于每一行R，根据a字段去表t2查找，走的是树搜索过程。由于我们构造的数据都是一一对应的，因此每次的搜索过程都只扫描一行，也是总共扫描100行；
  3. 所以，整个执行流程，总扫描行数是200。

现在我们知道了这个过程，再试着回答一下文章开头的两个问题。
先看第一个问题：能不能使用join?
假设不使用join，那我们就只能用单表查询。我们看看上面这条语句的需求，用单表查询怎么实现。

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

可以看到，在这个查询过程，也是扫描了200行，但是总共执行了101条语句，比直接join多了100次交互。除此之外，客户端还要自己拼接SQL语句和结果。
显然，这么做还不如直接join好。
我们再来看看第二个问题：怎么选择驱动表？
在这个join语句执行过程中，驱动表是走全表扫描，而被驱动表是走树搜索。
假设被驱动表的行数是M。每次在被驱动表查一行数据，要先搜索索引a，再搜索主键索引。每次搜索一棵树近似复杂度是以2为底的M的对数，记为log2M，所以在被驱动表上查一行的时间复杂度是 2log2M。
假设驱动表的行数是N，执行过程就要扫描驱动表N行，然后对于每一行，到被驱动表上匹配一次。
因此整个执行过程，近似复杂度是 N + N2*log2M。
显然，N对扫描行数的影响更大，因此应该让小表来做驱动表。

如果你没觉得这个影响有那么“显然”， 可以这么理解：N扩大1000倍的话，扫描行数就会扩大1000倍；而M扩大1000倍，扫描行数扩大不到10倍。

到这里小结一下，通过上面的分析我们得到了两个结论：

  1. 使用join语句，性能比强行拆成多个单表执行SQL语句的性能要好；
  2. 如果使用join语句的话，需要让小表做驱动表。

但是，你需要注意，这个结论的前提是 可以使用被驱动表的索引。
接下来，我们再看看被驱动表用不上索引的情况。

Simple Nested-Loop Join

现在，我们把SQL语句改成这样：

  1. select * from t1 straight_join t2 on (t1.a=t2.b);

由于表t2的字段b上没有索引，因此再用图2的执行流程时，每次到t2去匹配的时候，就要做一次全表扫描。
你可以先设想一下这个问题，继续使用图2的算法，是不是可以得到正确的结果呢？如果只看结果的话，这个算法是正确的，而且这个算法也有一个名字，叫做“Simple Nested-Loop Join”。
但是，这样算来，这个SQL请求就要扫描表t2多达100次，总共扫描 N2log2M ==> 100(1001og2100)=10万行。
这还只是两个小表，如果t1和t2都是10万行的表（当然了，这也还是属于小表的范围），就要扫描100亿行，这个算法看上去太“笨重”了。
当然，MySQL也没有使用这个Simple Nested-Loop Join算法，而是使用了另一个叫作“Block Nested-Loop Join”的算法，简称BNL。

Block Nested-Loop Join

这时候，被驱动表上没有可用的索引，算法的流程是这样的：

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

这个过程的流程图如下：
Join使用以及优化 - 图3
图3 Block Nested-Loop Join 算法的执行流程
对应地，这条SQL语句的explain结果如下所示：
Join使用以及优化 - 图4
图4 不使用索引字段join的 explain结果
可以看到，在这个过程中，对表t1和t2都做了一次全表扫描，因此总的扫描行数是1100。由于join_buffer是以无序数组的方式组织的，因此对表t2中的每一行，都要做100次判断，总共需要在内存中做的判断次数是：1001000=10万次。
前面我们说过，如果使用Simple Nested-Loop Join算法进行查询，扫描行数也是10万行。因此，从时间复杂度上来说，这两个算法是一样的。但是，Block Nested-Loop Join算法的这10万次判断是*内存操作，速度上会快很多，性能也更好。
接下来，我们来看一下，在这种情况下，应该选择哪个表做驱动表。
假设小表的行数是N，大表的行数是M，那么在这个算法里：

  1. 两个表都做一次全表扫描，所以总的扫描行数是M+N；
  2. 内存中的判断次数是M*N。

可以看到，调换这两个算式中的M和N没差别，因此这时候选择大表还是小表做驱动表，执行耗时是一样的。
然后，你可能马上就会问了，这个例子里表t1才100行，要是表t1是一个大表，join_buffer放不下怎么办呢？
join_buffer的大小是由参数join_buffer_size设定的，默认值是256k。如果放不下表t1的所有数据话，策略很简单，就是分段放。我把join_buffer_size改成1200，再执行：

  1. select * from t1 straight_join t2 on (t1.a=t2.b);

执行过程就变成了：

  1. 扫描表t1，顺序读取数据行放入join_buffer中，放完第88行join_buffer满了，继续第2步；
  2. 扫描表t2，把t2中的每一行取出来，跟join_buffer中的数据做对比，满足join条件的，作为结果集的一部分返回；
  3. 清空join_buffer；
  4. 继续扫描表t1，顺序读取最后的12行数据放入join_buffer中，继续执行第2步。

执行流程图也就变成这样：
Join使用以及优化 - 图5
图5 Block Nested-Loop Join — 两段
图中的步骤4和5，表示清空join_buffer再复用。这个流程才体现出了这个算法名字中“Block”的由来，表示“分块去join”。
可以看到，这时候由于表t1被分成了两次放入join_buffer中，导致表t2会被扫描两次。虽然分成两次放入join_buffer，但是判断等值条件的次数还是不变的，依然是(88+12)1000=10万次。
我们再来看下，在这种情况下驱动表的选择问题。
假设，驱动表的数据行数是N，需要分K段才能完成算法流程，被驱动表的数据行数是M。
注意，这里的K不是常数，N越大K就会越大，因此把K表示为λN，显然λ的取值范围是(0,1)。
所以，在这个算法的执行过程中：

  1. 扫描行数是 N+λNM；
  2. 内存判断 N*M次。

显然，内存判断次数是不受选择哪个表作为驱动表影响的。而考虑到扫描行数，在M和N大小确定的情况下，N小一些，整个算式的结果会更小。
所以结论是，应该让小表当驱动表。
当然，你会发现，在N+λNM这个式子里，λ才是影响扫描行数的关键因素，这个值越小越好。
刚刚我们说了N越大，分段数K越大。那么，N固定的时候，什么参数会影响K的大小呢？（也就是λ的大小）答案是join_buffer_size。join_buffer_size越大，一次可以放入的行越多，分成的段数也就越少，对被驱动表的全表扫描次数就越少。
这就是为什么，你可能会看到一些建议告诉你，如果你的join语句很慢，就把join_buffer_size改大。
理解了MySQL执行join的两种算法，现在我们再来试着回答文章开头的两个问题。
第一个问题：能不能使用join语句？

  1. 如果可以使用Index Nested-Loop Join算法，也就是说可以用上被驱动表上的索引，其实是没问题的；
  2. 如果使用Block Nested-Loop Join算法，扫描行数就会过多。尤其是在大表上的join操作，这样可能要扫描被驱动表很多次，会占用大量的系统资源。所以这种join尽量不要用。

所以你在判断要不要使用join语句时，就是看explain结果里面，Extra字段里面有没有出现“Block Nested Loop”字样。
第二个问题是：如果要使用join，应该选择大表做驱动表还是选择小表做驱动表？

  1. 如果是Index Nested-Loop Join算法，应该选择小表做驱动表；
  2. 如果是Block Nested-Loop Join算法：
    • 在join_buffer_size足够大的时候，是一样的；
    • 在join_buffer_size不够大的时候（这种情况更常见），应该选择小表做驱动表。

所以，这个问题的结论就是，总是应该使用小表做驱动表。
当然了，这里我需要说明下，什么叫作“小表”。
我们前面的例子是没有加条件的。如果我在语句的where条件加上 t2.id<=50这个限定条件，再来看下这两条语句：

  1. select * from t1 straight_join t2 on (t1.b=t2.b) where t2.id<=50;
  2. select * from t2 straight_join t1 on (t1.b=t2.b) where t2.id<=50;

注意，为了让两条语句的被驱动表都用不上索引，所以join字段都使用了没有索引的字段b。
但如果是用第二个语句的话，join_buffer只需要放入t2的前50行，显然是更好的。所以这里，“t2的前50行”是那个相对小的表，也就是“小表”。
我们再来看另外一组例子：

  1. select t1.b,t2.* from  t1  straight_join t2 on (t1.b=t2.b) where t2.id<=100;
  2. select t1.b,t2.* from  t2  straight_join t1 on (t1.b=t2.b) where t2.id<=100;

这个例子里，表t1 和 t2都是只有100行参加join。但是，这两条语句每次查询放入join_buffer中的数据是不一样的：

  • 表t1只查字段b，因此如果把t1放到join_buffer中，则join_buffer中只需要放入b的值；
  • 表t2需要查所有的字段，因此如果把表t2放到join_buffer中的话，就需要放入三个字段id、a和b。

这里，我们应该选择表t1作为驱动表。也就是说在这个例子里，“只需要一列参与join的表t1”是那个相对小的表。
所以，更准确地说，在决定哪个表做驱动表的时候，应该是两个表按照各自的条件过滤，过滤完成之后，计算参与join的各个字段的总数据量，数据量小的那个表，就是“小表”，应该作为驱动表。

小结

今天，我和你介绍了MySQL执行join语句的两种可能算法，这两种算法是由能否使用被驱动表的索引决定的。而能否用上被驱动表的索引，对join语句的性能影响很大。
通过对Index Nested-Loop Join和Block Nested-Loop Join两个算法执行过程的分析，我们也得到了文章开头两个问题的答案：

  1. 如果可以使用被驱动表的索引，join语句还是有其优势的；
  2. 不能使用被驱动表的索引，只能使用Block Nested-Loop Join算法，这样的语句就尽量不要使用；
  3. 在使用join的时候，应该让小表做驱动表。

最后，又到了今天的问题时间。
我们在上文说到，使用Block Nested-Loop Join算法，可能会因为join_buffer不够大，需要对被驱动表做多次全表扫描。
我的问题是，如果被驱动表是一个大表，并且是一个冷数据表，除了查询过程中可能会导致IO压力大以外，你觉得对这个MySQL服务还有什么更严重的影响吗？（这个问题需要结合上一篇文章的知识点）

join优化

上文介绍了join语句的两种算法，分别是Index Nested-Loop Join(NLJ)和Block Nested-Loop Join(BNL)。
我们发现在使用NLJ算法的时候，其实效果还是不错的，比通过应用层拆分成多个语句然后再拼接查询结果更方便，而且性能也不会差。
但是，BNL算法在大表join的时候性能就差多了，比较次数等于两个表参与join的行数的乘积，很消耗CPU资源。
当然了，这两个算法都还有继续优化的空间，我们今天就来聊聊这个话题。
为了便于分析，我还是创建两个表t1、t2来和你展开今天的问题。

  1. create table t1(id int primary key, a int, b int, index(a));
  2. create table t2 like t1;
  3. drop procedure idata;
  4. delimiter ;;
  5. create procedure idata()
  6. begin
  7.   declare i int;
  8.   set i=1;
  9.   while(i<=1000)do
  10.     insert into t1 values(i, 1001-i, i);
  11.     set i=i+1;
  12.   end while;
  14.   set i=1;
  15.   while(i<=1000000)do
  16.     insert into t2 values(i, i, i);
  17.     set i=i+1;
  18.   end while;
  19. end;;
  20. delimiter ;
  21. call idata();

为了便于后面量化说明，我在表t1里，插入了1000行数据，每一行的a=1001-id的值。也就是说，表t1中字段a是逆序的。同时，我在表t2中插入了100万行数据。

Multi-Range Read优化

MRR，全称「Multi-Range Read Optimization」。简单说：MRR 通过把「随机磁盘读」，转化为「顺序磁盘读」，从而提高了索引查询的性能。
至于：

  • 为什么要把随机读转化为顺序读？
  • 怎么转化的？
  • 为什么顺序读就能提升读取性能？

咱们开始吧。
磁盘：苦逼的底层劳动人民
执行一个范围查询：

  1. mysql > explain select * from stu where age between 10 and 20;
  2. +----+-------------+-------+-------+------+---------+------+------+-----------------------+
  3. | id | select_type | table | type  | key  | key_len | ref  | rows | Extra                 |
  4. +----+-------------+-------+-------+----------------+------+------+-----------------------+
  5. |  1 | SIMPLE      |  stu  | range | age  | 5       | NULL |  960 | Using index condition |
  6. +----+-------------+-------+-------+----------------+------+------+-----------------------+

当这个 sql 被执行时，MySQL 会按照下图的方式，去磁盘读取数据（假设数据不在数据缓冲池里）：
Join使用以及优化 - 图6
图中红色线就是整个的查询过程，蓝色线则是磁盘的运动路线。这张图是按照 Myisam 的索引结构画的，不过对于 Innodb 也同样适用。对于 Myisam，左边就是字段 age 的二级索引，右边是存储完整行数据的地方。
先到左边的二级索引找，找到第一条符合条件的记录（实际上每个节点是一个页，一个页可以有很多条记录，这里我们假设每个页只有一条），接着到右边去读取这条数据的完整记录。
读取完后，回到左边，继续找下一条符合条件的记录，找到后，再到右边读取，这时发现这条数据跟上一条数据，在物理存储位置上，离的贼远！
咋办，没办法，只能让磁盘和磁头一起做机械运动，去给你读取这条数据。
第三条、第四条，都是一样，每次读取数据，磁盘和磁头都得跑好远一段路。
磁盘的简化结构可以看成这样：
Join使用以及优化 - 图7
Join使用以及优化 - 图8
可以想象一下，为了执行你这条 sql 语句，磁盘要不停的旋转，磁头要不停的移动，这些机械运动，都是很费时的。
10,000 RPM（Revolutions Per Minute，即转每分） 的机械硬盘，每秒大概可以执行 167 次磁盘读取，所以在极端情况下，MySQL 每秒只能给你返回 167 条数据，这还不算上 CPU 排队时间。

上面讲的都是机械硬盘，SSD 的土豪，请随意 - - 对于 Innodb，也是一样的。 Innodb 是聚簇索引（cluster index），所以只需要把右边也换成一颗叶子节点带有完整数据的 B+ tree 就可以了。
顺序读：一场狂风暴雨般的革命
到这里你知道了磁盘随机访问是多么奢侈的事了，所以，很明显，要把随机访问转化成顺序访问：

  1. mysql > set optimizer_switch='mrr=on';
  2. Query OK, 0 rows affected (0.06 sec)
  3. mysql > explain select * from stu where age between 10 and 20;
  4. +----+-------------+-------+-------+------+---------+------+------+----------------+
  5. | id | select_type | table | type  | key  | key_len | ref  | rows | Extra          |
  6. +----+-------------+-------+-------+------+---------+------+------+----------------+
  7. |  1 | SIMPLE      | tbl   | range | age  |    5    | NULL |  960 | ...; Using MRR |
  8. +----+-------------+-------+-------+------+---------+------+------+----------------+

我们开启了 MRR，重新执行 sql 语句，发现 Extra 里多了一个「Using MRR」。
这下 MySQL 的查询过程会变成这样：
Join使用以及优化 - 图9
对于 Myisam，在去磁盘获取完整数据之前，会先按照 rowid 排好序，再去顺序的读取磁盘。
对于 Innodb，则会按照聚簇索引键值排好序，再顺序的读取聚簇索引。
顺序读带来了几个好处：
1、磁盘和磁头不再需要来回做机械运动；
2、可以充分利用磁盘预读
比如在客户端请求一页的数据时，可以把后面几页的数据也一起返回，放到数据缓冲池中，这样如果下次刚好需要下一页的数据，就不再需要到磁盘读取。这样做的理论依据是计算机科学中著名的局部性原理： 当一个数据被用到时，其附近的数据也通常会马上被使用。 3、在一次查询中，每一页的数据只会从磁盘读取一次
MySQL 从磁盘读取页的数据后，会把数据放到数据缓冲池，下次如果还用到这个页，就不需要去磁盘读取，直接从内存读。
但是如果不排序，可能你在读取了第 1 页的数据后，会去读取第2、3、4页数据，接着你又要去读取第 1 页的数据，这时你发现第 1 页的数据，已经从缓存中被剔除了，于是又得再去磁盘读取第 1 页的数据。
而转化为顺序读后，你会连续的使用第 1 页的数据，这时候按照 MySQL 的缓存剔除机制，这一页的缓存是不会失效的，直到你利用完这一页的数据，由于是顺序读，在这次查询的余下过程中，你确信不会再用到这一页的数据，可以和这一页数据说告辞了。
顺序读就是通过这三个方面，最大的优化了索引的读取。别忘了，索引本身就是为了减少磁盘 IO，加快查询，而 MRR，则是把索引减少磁盘 IO 的作用，进一步放大。
一些关于这场革命的配置
和 MRR 相关的配置有两个：

  • mrr: on/off
  • mrr_cost_based: on/off

第一个就是上面演示时用到的，用来打开 MRR 的开关：
mysql > set optimizer_switch=‘mrr=on’;
如果你不打开，是一定不会用到 MRR 的。
另一个，则是用来告诉优化器，要不要基于使用 MRR 的成本，考虑使用 MRR 是否值得（cost-based choice），来决定具体的 sql 语句里要不要使用 MRR。
很明显，对于只返回一行数据的查询，是没有必要 MRR 的，而如果你把 mrr_cost_based 设为 off，那优化器就会通通使用 MRR，这在有些情况下是很 stupid 的，所以建议这个配置还是设为 on，毕竟优化器在绝大多数情况下都是正确的。
另外还有一个配置 read_rnd_buffer_size ，是用来设置用于给 rowid 排序的内存的大小。
显然，MRR 在本质上是一种用空间换时间的算法。MySQL 不可能给你无限的内存来进行排序，如果 read_rnd_buffer 满了，就会先把满了的 rowid 排好序去磁盘读取，接着清空，然后再往里面继续放 rowid，直到 read_rnd_buffer 又达到 read_rnd_buffe 配置的上限，如此循环。
你也看出来了，MRR 跟索引有很大的关系。索引是 MySQL 对查询做的一个优化，把原本杂乱无章的数据，用有序的结构组织起来，让全表扫描变成有章可循的查询。而我们讲的 MRR，则是 MySQL 对基于索引的查询做的一个的优化，可以说是对优化的优化了。要优化 MySQL 的查询，就得先知道 MySQL 的查询过程；而要优化索引的查询，则要知道 MySQL 索引的原理。

Batched Key Access

理解了MRR性能提升的原理，我们就能理解MySQL在5.6版本后开始引入的Batched Key Acess(BKA)算法了。这个BKA算法，其实就是对NLJ算法的优化。
我们再来看看上一篇文章中用到的NLJ算法的流程图：
Join使用以及优化 - 图10
图4 Index Nested-Loop Join流程图
NLJ算法执行的逻辑是：从驱动表t1，一行行地取出a的值，再到被驱动表t2去做join。也就是说，对于表t2来说，每次都是匹配一个值。这时，MRR的优势就用不上了。
那怎么才能一次性地多传些值给表t2呢？方法就是，从表t1里一次性地多拿些行出来，一起传给表t2。
既然如此，我们就把表t1的数据取出来一部分，先放到一个临时内存。这个临时内存不是别人，就是join_buffer。
通过上一篇文章，我们知道join_buffer 在BNL算法里的作用，是暂存驱动表的数据。但是在NLJ算法里并没有用。那么，我们刚好就可以复用join_buffer到BKA算法中。
如图5所示，是上面的NLJ算法优化后的BKA算法的流程。
Join使用以及优化 - 图11
图5 Batched Key Acess流程
图中，我在join_buffer中放入的数据是P1~P100，表示的是只会取查询需要的字段。当然，如果join buffer放不下P1~P100的所有数据，就会把这100行数据分成多段执行上图的流程。
那么，这个BKA算法到底要怎么启用呢？
如果要使用BKA优化算法的话，你需要在执行SQL语句之前，先设置

  1. set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

其中，前两个参数的作用是要启用MRR。这么做的原因是，BKA算法的优化要依赖于MRR。

BNL算法的性能问题

说完了NLJ算法的优化，我们再来看BNL算法的优化。
使用Block Nested-Loop Join(BNL)算法时，可能会对被驱动表做多次扫描。如果这个被驱动表是一个大的冷数据表，除了会导致IO压力大以外，还会对系统有什么影响呢？
我们说过在InnoDB的LRU算法，由于InnoDB对Bufffer Pool的LRU算法做了优化，即：第一次从磁盘读入内存的数据页，会先放在old区域。如果1秒之后这个数据页不再被访问了，就不会被移动到LRU链表头部，这样对Buffer Pool的命中率影响就不大。
但是，如果一个使用BNL算法的join语句，多次扫描一个冷表，而且这个语句执行时间超过1秒，就会在再次扫描冷表的时候，把冷表的数据页移到LRU链表头部。
这种情况对应的，是冷表的数据量小于整个Buffer Pool的3/8，能够完全放入old区域的情况。
如果这个冷表很大，就会出现另外一种情况：业务正常访问的数据页，没有机会进入young区域。
由于优化机制的存在，一个正常访问的数据页，要进入young区域，需要隔1秒后再次被访问到。但是，由于我们的join语句在循环读磁盘和淘汰内存页，进入old区域的数据页，很可能在1秒之内就被淘汰了。这样，就会导致这个MySQL实例的Buffer Pool在这段时间内，young区域的数据页没有被合理地淘汰。
也就是说，这两种情况都会影响Buffer Pool的正常运作。
大表join操作虽然对IO有影响，但是在语句执行结束后，对IO的影响也就结束了。但是，对Buffer Pool的影响就是持续性的，需要依靠后续的查询请求慢慢恢复内存命中率。
为了减少这种影响，你可以考虑增大join_buffer_size的值，减少对被驱动表的扫描次数。
也就是说，BNL算法对系统的影响主要包括三个方面：

  1. 可能会多次扫描被驱动表，占用磁盘IO资源；
  2. 判断join条件需要执行M*N次对比（M、N分别是两张表的行数），如果是大表就会占用非常多的CPU资源；
  3. 可能会导致Buffer Pool的热数据被淘汰，影响内存命中率。

我们执行语句之前，需要通过理论分析和查看explain结果的方式，确认是否要使用BNL算法。如果确认优化器会使用BNL算法，就需要做优化。优化的常见做法是，给被驱动表的join字段加上索引，把BNL算法转成BKA算法。
接下来，我们就具体看看，这个优化怎么做？

BNL转BKA

一些情况下，我们可以直接在被驱动表上建索引，这时就可以直接转成BKA算法了。
但是，有时候你确实会碰到一些不适合在被驱动表上建索引的情况。比如下面这个语句：

  1. select * from t1 join t2 on (t1.b=t2.b) where t2.b>=1 and t2.b<=2000;

我们在文章开始的时候，在表t2中插入了100万行数据，但是经过where条件过滤后，需要参与join的只有2000行数据。如果这条语句同时是一个低频的SQL语句，那么再为这个语句在表t2的字段b上创建一个索引就很浪费了。
但是，如果使用BNL算法来join的话，这个语句的执行流程是这样的：

  1. 把表t1的所有字段取出来，存入join_buffer中。这个表只有1000行，join_buffer_size默认值是256k，可以完全存入。
  2. 扫描表t2，取出每一行数据跟join_buffer中的数据进行对比，
    • 如果不满足t1.b=t2.b，则跳过；
    • 如果满足t1.b=t2.b, 再判断其他条件，也就是是否满足t2.b处于[1,2000]的条件，如果是，就作为结果集的一部分返回，否则跳过。

我在上一篇文章中说过，对于表t2的每一行，判断join是否满足的时候，都需要遍历join_buffer中的所有行。因此判断等值条件的次数是1000*100万=10亿次，这个判断的工作量很大。
Join使用以及优化 - 图12
图6 explain结果
Join使用以及优化 - 图13
图7 语句执行时间
可以看到，explain结果里Extra字段显示使用了BNL算法。在我的测试环境里，这条语句需要执行1分11秒。
在表t2的字段b上创建索引会浪费资源，但是不创建索引的话这个语句的等值条件要判断10亿次，想想也是浪费。那么，有没有两全其美的办法呢？
这时候，我们可以考虑使用临时表。使用临时表的大致思路是：

  1. 把表t2中满足条件的数据放在临时表tmp_t中；
  2. 为了让join使用BKA算法，给临时表tmp_t的字段b加上索引；
  3. 让表t1和tmp_t做join操作。

此时，对应的SQL语句的写法如下：

  1. create temporary table temp_t(id int primary key, a int, b int, index(b))engine=innodb;
  2. insert into temp_t select * from t2 where b>=1 and b<=2000;
  3. select * from t1 join temp_t on (t1.b=temp_t.b);
  1.                                                            图8就是这个语句序列的执行效果。<br />![](https://cdn.nlark.com/yuque/0/2021/png/2731883/1610680420541-bcf1ba1a-2555-4ad9-bc7b-90f275932d00.png#align=left&display=inline&height=547&margin=%5Bobject%20Object%5D&originHeight=547&originWidth=1130&size=0&status=done&style=none&width=1130)<br />                                                                       图8 使用临时表的执行效果<br />可以看到，整个过程3个语句执行时间的总和还不到1秒，相比于前面的1分11秒，性能得到了大幅提升。接下来，我们一起看一下这个过程的消耗：
  1. 执行insert语句构造temp_t表并插入数据的过程中，对表t2做了全表扫描，这里扫描行数是100万。
  2. 之后的join语句，扫描表t1，这里的扫描行数是1000；join比较过程中，做了1000次带索引的查询。相比于优化前的join语句需要做10亿次条件判断来说，这个优化效果还是很明显的。

总体来看，不论是在原表上加索引，还是用有索引的临时表，我们的思路都是让join语句能够用上被驱动表上的索引，来触发BKA算法，提升查询性能。

扩展-hash join

看到这里你可能发现了，其实上面计算10亿次那个操作，看上去有点儿傻。如果join_buffer里面维护的不是一个无序数组，而是一个哈希表的话，那么就不是10亿次判断，而是100万次hash查找。这样的话，整条语句的执行速度就快多了吧？
确实如此。
这，也正是MySQL的优化器和执行器一直被诟病的一个原因：不支持哈希join。并且，MySQL官方的roadmap，也是迟迟没有把这个优化排上议程。
实际上，这个优化思路，我们可以自己实现在业务端。实现流程大致如下：

  1. select * from t1;取得表t1的全部1000行数据，在业务端存入一个hash结构，比如C++里的set、PHP的dict这样的数据结构。
  2. select * from t2 where b>=1 and b<=2000; 获取表t2中满足条件的2000行数据。
  3. 把这2000行数据，一行一行地取到业务端，到hash结构的数据表中寻找匹配的数据。满足匹配的条件的这行数据，就作为结果集的一行。

理论上，这个过程会比临时表方案的执行速度还要快一些。如果你感兴趣的话，可以自己验证一下。

小结

今天，我和你分享了Index Nested-Loop Join（NLJ）和Block Nested-Loop Join（BNL）的优化方法。
在这些优化方法中：

  1. BKA优化是MySQL已经内置支持的，建议你默认使用；
  2. BNL算法效率低，建议你都尽量转成BKA算法。优化的方向就是给被驱动表的关联字段加上索引；
  3. 基于临时表的改进方案，对于能够提前过滤出小数据的join语句来说，效果还是很好的；
  4. MySQL目前的版本还不支持hash join，但你可以配合应用端自己模拟出来，理论上效果要好于临时表的方案。

最后，我给你留下一道思考题吧。
我们在讲join语句的这两篇文章中，都只涉及到了两个表的join。那么，现在有一个三个表join的需求，假设这三个表的表结构如下：

  1. CREATE TABLE `t1` (
  2.  `id` int(11) NOT NULL,
  3.  `a` int(11) DEFAULT NULL,
  4.  `b` int(11) DEFAULT NULL,
  5.  `c` int(11) DEFAULT NULL,
  6.   PRIMARY KEY (`id`)
  7. ) ENGINE=InnoDB;
  8. create table t2 like t1;
  9. create table t3 like t2;
  10. insert into ... //初始化三张表的数据

语句的需求实现如下的join逻辑：

  1. select * from t1 join t2 on(t1.a=t2.a) join t3 on (t2.b=t3.b) where t1.c>=X and t2.c>=Y and t3.c>=Z;

现在为了得到最快的执行速度，如果让你来设计表t1、t2、t3上的索引，来支持这个join语句，你会加哪些索引呢？
同时，如果我希望你用straight_join来重写这个语句，配合你创建的索引，你就需要安排连接顺序，你主要考虑的因素是什么呢？
如果改写成straight_join，要怎么指定连接顺序，以及怎么给三个表创建索引。
第一原则是要尽量使用BKA算法。需要注意的是，使用BKA算法的时候，并不是“先计算两个表join的结果，再跟第三个表join”，而是直接嵌套查询的。
具体实现是：在t1.c>=X、t2.c>=Y、t3.c>=Z这三个条件里，选择一个经过过滤以后，数据最少的那个表，作为第一个驱动表。此时，可能会出现如下两种情况。
第一种情况，如果选出来是表t1或者t3，那剩下的部分就固定了。

  1. 如果驱动表是t1，则连接顺序是t1->t2->t3，要在被驱动表字段创建上索引，也就是t2.a 和 t3.b上创建索引；
  2. 如果驱动表是t3，则连接顺序是t3->t2->t1，需要在t2.b 和 t1.a上创建索引。

同时，我们还需要在第一个驱动表的字段c上创建索引。
第二种情况是，如果选出来的第一个驱动表是表t2的话，则需要评估另外两个条件的过滤效果。
总之，整体的思路就是，尽量让每一次参与join的驱动表的数据集，越小越好，因为这样我们的驱动表就会越小。