🪴 Obsidian Publish

MySQL join逻辑

24分钟阅读

Join 操作会在执行时分为两种：Index Nested-Loop Join & Block Nested-Loop Join。

  • Index Nested-Loop Join 从表可以走索引的，
  • Simple Nested-Loop Join 从表一定全表查询的 (不会使用)
  • Block Nested-Loop Join 是无法走索引后，将驱动表放到内存中，然后从被驱动表中拿一条条数据进行 join 操作。若 join buffer 不够大，那么会对驱动表进行分块，每次取一部分放到内存，然后再 join 操作。

两种都推荐使用小表作为驱动表。
如果驱动表很大，并且使用了 Block Nested-Loop Join 进行 join，那最好不进行 join 操作。
通过 explain 查看语句执行使用了哪种 join，如果是后者，会显示“Block Nested Loop”字样。

使用 straight_join 可以强制语句按照顺序进行 join 操作。

本章课后题，被驱动表是大表 & 冷数据表，除了 IO 压力大还会有什么问题？
答：Join 时频繁加载到内存中，buffer pool 的 LRU 从 old → young，淘汰掉真正热点数据，导致 buffer pool 命中率下降，热点数据需要访问磁盘，进而影响响应速度，再进而导致大部分请求阻塞。
除此之外，还可以考虑长事务导致的各种问题。

MRR 将主键 ID 排序后再查找，通过空间换时间来优化查询速度。
MRR 和 Index Nexted-Loop Join(NLJ) 结合，将主表要连接的数据放到 join buffer 中排序后，再去从表中进行查找，从而优化速度。这种叫做 Batched Key Access(BKL) > Block Nested-Loop Join(BNL) 在从表特别大的情况下，会影响到 buffer pool 命中率。在确认无法优化 SQL 语句下，可能要对从表加索引，将 BNL 转换为 BKL。
还有一种方式，建立临时表，从而避免 BNL 操作，见文中例子。
还有一种方式，在业务端实现 hash join。

为了便于量化分析，我还是创建两个表 t1 和 t2 来和你说明。

CREATE TABLE `t2` (
  `id` int(11) NOT NULL,
  `a` int(11) DEFAULT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `a` (`a`)
) ENGINE=InnoDB;
 
drop procedure idata;
delimiter ;;
create procedure idata()
begin
  declare i int;
  set i=1;
  while(i<=1000)do
    insert into t2 values(i, i, i);
    set i=i+1;
  end while;
end;;
delimiter ;
call idata();
 
create table t1 like t2;
insert into t1 (select * from t2 where id<=100)

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

Index Nested-Loop Join

我们来看一下这个语句：

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

如果直接使用 join 语句，MySQL 优化器可能会选择表 t1 或 t2 作为驱动表，这样会影响我们分析 SQL 语句的执行过程。所以，为了便于分析执行过程中的性能问题，我改用 straight_join 让 MySQL 使用固定的连接方式执行查询，这样优化器只会按照我们指定的方式去 join。在这个语句里，t1 是驱动表，t2 是被驱动表。

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

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

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

Simple Nested-Loop Join

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

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

每取到一个 t1.a 就在 t2 表中进行一次全量查询。这个算法也有一个名字，叫做“Simple Nested-Loop Join”。当数据量上来后，这个算法看上去太“笨重”了。

当然，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 条件的，作为结果集的一部分返回。

对应地，这条 SQL 语句的 explain 结果如下所示：

该方法和 Simple Nested-Loop Join 方法的比较次数相同，但是该方法在内存中操作，速度更快。

join_buffer 的大小是由参数 join_buffer_size 设定的，默认值是 256k。如果放不下表 t1 的所有数据话，策略很简单，就是分段放。 每次取一段 t1 的数据到内存中，进行比较，获得结果；然后将下一段放到内存中。

假设驱动表的行数是 N，被驱动表为 M，那么整个算法执行中：

（1）扫描行数 = N + λNM，其中假设，驱动表的数据行数是 N，需要分 K 段才能完成算法流程，被驱动表的数据行数是 M。注意，这里的 K 不是常数，N 越大 K 就会越大，因此把 K 表示为 λ*N，显然 λ 的取值范围是(0,1)。
（2）内存判断 = NM。

能不能用 join？

  1. 如果可以使用 Index Nested-Loop Join 算法，也就是说可以用上被驱动表上的索引，其实是没问题的；
  2. 如果使用 Block Nested-Loop Join 算法，扫描行数就会过多。尤其是在大表上的 join 操作，这样可能要扫描被驱动表很多次，会占用大量的系统资源。所以这种 join 尽量不要用。
  3. 所以你在判断要不要使用 join 语句时，就是看 explain 结果里面，Extra 字段里面有没有出现“Block Nested Loop”字样。

总是应该使用小表做驱动表。更准确地说，在决定哪个表做驱动表的时候，应该是两个表按照各自的条件过滤，过滤完成之后，计算参与 join 的各个字段的总数据量，数据量小的那个表，就是“小表”，应该作为驱动表。

我们在上文说到，使用 Block Nested-Loop Join 算法，可能会因为 join_buffer 不够大，需要对被驱动表做多次全表扫描。

课后题

我的问题是，如果被驱动表是一个大表，并且是一个冷数据表，除了查询过程中可能会导致 IO 压力大以外，你觉得对这个 MySQL 服务还有什么更严重的影响吗？（这个问题需要结合上一篇文章的知识点）

如果驱动表分段，那么被驱动表就被多次读，而被驱动表又是大表，循环读取的间隔肯定得超 1 秒，这就会导致上篇文章提到的：“数据页在 LRU_old 的存在时间超过 1 秒，就会移到 young 区”。最终结果就是把大部分热点数据都淘汰了，导致“Buffer pool hit rate”命中率极低，其他请求需要读磁盘，因此系统响应变慢，大部分请求阻塞。

因为 join_buffer 不够大，需要对被驱动表做多次全表扫描，也就造成了“长事务”。除了老师上节课提到的导致 undo log 不能被回收，导致回滚段空间膨胀问题，还会出现：

  1. 长期占用 DML 锁，引发 DDL 拿不到锁堵慢连接池；
  2. SQL 执行 socket_timeout 超时后业务接口重复发起，导致实例 IO 负载上升出现雪崩；
  3. 实例异常后，DBA kill SQL 因繁杂的回滚执行时间过长，不能快速恢复可用；
  4. 如果业务采用 select * 作为结果集返回，极大可能出现网络拥堵，整体拖慢服务端的处理；
  5. 冷数据污染 buffer pool，block nested-loop 多次扫描，其中间隔很有可能超过 1s，从而污染到 lru 头部，影响整体的查询体验。

Batched Key Access

二级索引回表优化：MRR优化&索引下推, MySQL 在 5.6 版本后开始引入的 Batched Key Acess(BKA)算法了。这个 BKA 算法，其实就是对 NLJ 算法的优化。

MySQL 整理-10.png|600

通过上一篇文章，我们知道 join_buffer 在 BNL 算法里的作用，是暂存驱动表的数据。但是在 NLJ 算法里并没有用。那么，我们刚好就可以复用 join_buffer 到 BKA 算法中。

MySQL 整理-11.png|600

我在 join_buffer 中放入的数据是 P1P100，表示的是只会取查询需要的字段。当然，如果 join buffer 放不下 P1P100 的所有数据，就会把这 100 行数据分成多段执行上图的流程。

那么，这个 BKA 算法到底要怎么启用呢？

如果要使用 BKA 优化算法的话，你需要在执行 SQL 语句之前，先设置

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 Buffer Pool 机制 中，我们说到 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 算法了。

但是，有时候你确实会碰到一些不适合在被驱动表上建索引的情况。比如下面这个语句：

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 亿次，这个判断的工作量很大。

图 6 explain 结果

图 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 语句的写法如下：

create temporary table temp_t(id int primary key, a int, b int, index(b))engine=innodb;
insert into temp_t select * from t2 where b>=1 and b<=2000;
select * from t1 join temp_t on (t1.b=temp_t.b);

图 8 就是这个语句序列的执行效果。

图 8 使用临时表的执行效果

可以看到，整个过程 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 结构的数据表中寻找匹配的数据。满足匹配的条件的这行数据，就作为结果集的一行。

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

课后问题

CREATE TABLE `t1` (
`id` int(11) NOT NULL,
`a` int(11) DEFAULT NULL,
`b` int(11) DEFAULT NULL,
`c` int(11) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB;
create table t2 like t1;
create table t3 like t2;
insert into ... //初始化三张表的数据
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 来重写这个语句，配合你创建的索引，你就需要安排连接顺序，你主要考虑的因素是什么呢？

第一原则是要尽量使用 BKA 算法。需要注意的是，使用 BKA 算法的时候，并不是“先计算两个表 join 的结果，再跟第三个表 join”，而是直接嵌套查询的。

具体实现是：在 t1.c>=X、t2.c>=Y、t3.c>=Z 这三个条件里，选择一个经过过滤以后，数据最少的那个表，作为第一个驱动表。此时，可能会出现如下两种情况。

第一种情况，如果选出来是表 t1 或者 t3，那剩下的部分就固定了。

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

  • 如果驱动表是 t3，则连接顺序是 t3→t2→t1，需要在 t2.b 和 t1.a 上创建索引。

同时，我们还需要在第一个驱动表的字段 c 上创建索引。

第二种情况是，如果选出来的第一个驱动表是表 t2 的话，则需要评估另外两个条件的过滤效果。

反向链接