《MySQL45讲》读书笔记(十一)：join

发表于 | 分类于
字数统计: 3.1k

此文为极客时间：MySQL实战45讲的 34、35节join相关内容的笔记

一、Join的查询流程

假设我们有表 t1 和表 t2，他们都有字段 a，b，其中 t1 有 100条数据，而 t2 有1000条数据。

我们要执行这么一条sql：

1
select * from t1 join t2 on t2.a = t1.a

执行流程就是会这样的：

  1. 先取出 t1 的一条数据 R；
  2. 然后根据 R 的 a 字段 去 t2 表里找复合条件的数据；
  3. 找到以后，就和 R 的数据拼起来作为结果集的一部分；
  4. 重复以上步骤，直到遍历完 t1 最后一条数据。

其中，被驱动表的关联条件是否有索引对性能有着很大的影响。

二、关联条件有索引

1.NJL算法

还是以上面的 sql 为例：

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

这个算法叫做NJL（Index Nested-Loop Join），由于从 t1 往 t2 查找的过程中使用了索引，所以关联查询的过程其实是一个查找树的过程：

假设被驱动表的行数是 M。每次在被驱动表查一行数据，要先搜索索引 a，再搜索主键索引。每次搜索一棵树近似复杂度是以 2 为底的 M 的对数，记为 log2M，所以在被驱动表上查一行的时间复杂度是 2*log2M。

假设驱动表的行数是 N，执行过程就要扫描驱动表 N 行，然后对于每一行，到被驱动表上匹配一次。

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

所以，对于有索引的情况下，需要让小表做驱动表。

2.MRR优化

对于关联条件上有索引，但是查询条件没有实现索引覆盖的字段，仍然需要在获得了非主键索引后，进行回表获取数据。在这过程，回表需要一行一行的扫描主键索引树。

假设我们执行一条sql：

1
select * from t3 join t4 on t3.a = t4.a where t3.a > 20

由于 a 索引树是按 a 排序的，按照 a 的排序去回表，很可能对应主键索引树上的记录是无序的。比如 a 索引树上按顺序是a=1，a=2，a=3....而对应的主键索引树上，是id=1(a=2)，id=2(a=8)，id=3(a=1)....也就是说，可能会出现随机访问，性能较差。

针对这个问题，使用MRR（Multi-Range Read）这个过程优化为顺序读：

  1. 先查找 a 索引树，找到相关记录
  2. 在一块 read_rnd_buffer 内存中对 a 索引树的记录按 id 自增排序
  3. 回表，返回并且拼接复合条件的记录

在这里，read_rnd_buffer 的大小是由 read_rnd_buffer_size 参数控制的。如果步骤 1 中，read_rnd_buffer 放满了，就会先执行完步骤 2 和 3，然后清空 read_rnd_buffer。之后继续找索引 a 的下个记录，并继续循环。

MRR 能够提升性能的核心在于，这条查询语句在索引 a 上做的是一个范围查询，可以得到足够多的主键 id。这样通过排序以后，再去主键索引查数据，才能体现出“顺序读”的优势。

3.BKA算法

基于上面 MRR 优化的思想，MySQL 在 5.6 版本后开始引入的 批量索引访问（Batched Key Access）算法，针对关联条件有索引情况下的索引嵌套循环算法 NLJ 进行了优化。由于 NLJ 并没有像无索引条件下的块嵌套循环 BNL 算法那样，使用到 join_buffer，因此刚好将次内存区作为 MRR 优化的 read_rnd_buffer 。

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

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

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

三、关联条件无索引

1.BNL算法

在无索引的情况下，如果仍然使用索引循环嵌套的算法，那么每次关联 t2 的时候都需要对 t2 进行一次全表扫描，也就是说，如果执行联查的 sql，就需要查询 t2 100000次。这个算法叫做SNL（Simple Nested-Loop Join）

实际上，SNL 太过笨重了，Mysql 选择的是BNL（Block Nested-Loop Join）算法：

  1. 将 t1 读入线程内存 join buffer 中，如果放不下就分块进行；
  2. 全表扫描 t2 ，每扫描一行就和 t1的每一行进行比较；
  3. 把复合条件的数据返回结果集；

这个做法和 SNL 需要扫描的次数一样，但是由于判断在内存进行，所以速度会快很多。

当 join_buffer_size 规定的 join buffer 大小能够装下 t1 时：

假设小表的行数是 N，大表的行数是 M，那么在这个算法里：

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

可以看到，调换这两个算式中的 M 和 N 没差别，因此这时候选择大表还是小表做驱动表，执行耗时是一样的。

但是，如果 join buffer 放不下 t1，这个过程就需要分块进行：

  1. 假如只放得下88行，那么就先将 t1 的前88行读入内存；
  2. 扫描 t2，每一行都比较88次，然后符合条件的放入结果集
  3. 清空 join buffer
  4. 重复以上步骤，处理完剩下的12行数据

这种情况下，驱动表的选择是这么考虑的：

假设，驱动表的数据行数是 N，需要分 K 段才能完成算法流程，被驱动表的数据行数是 M。

注意，这里的 K 不是常数，N 越大 K 就会越大，因此把 K 表示为λ*N，显然λ的取值范围是 (0,1)。

所以，在这个算法的执行过程中：

  1. 扫描行数是 N + λ * N * M；
  2. 内存判断 N*M 次。
  3. 显然，内存判断次数是不受选择哪个表作为驱动表影响的。而考虑到扫描行数，在 M 和 N 大小确定的情况下，N 小一些，整个算式的结果会更小。

所以结论是，还是应该让小表当驱动表。

当然，你会发现，在 N+λNM 这个式子里，λ才是影响扫描行数的关键因素，这个值越小越好，而决定了需要分几块的关键参数就在于 join buffer 的大小，join buffer 越大，一次性放入的数据就越多，需要分的块 K ——也就是 λ*N ——就越小。

所以，如果连表查询速度很慢，可以试着吧 join_buffer_size 调大。

2.BNL算法存在的问题

由于 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 的热数据被淘汰，影响内存命中率。

3.BNL算法的优化

假如我们要执行这样一条sql：

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

其中，表 t1 有1000条数据，表 t2 中有100万条数据，但是经过 where 条件过滤后，需要参与 join 的只有 2000 行数据。

在 BNL 算法的逻辑下：

  1. 把 t1 存入 join_buffer
  2. 扫描 t2，每一条都去跟 t1 的数据对比，先判断 t1.b=t2.b ，再判断 t2.b>=1和 t2.b<=2000
  3. 返回满足条件的结果集

按这个做法，每一条数据都必须要跟 join_buffer 里的每一条数据进行比对，也就是 1000*100 万 =10 亿次，显然很不明智。

加索引

要优化这个情况，最直接的方法仍然是查询条件加上索引，将默认的 BNL 算法转为 NLJ 算法。

临时表

当然，并不是所有情况下都时候给字段加上索引的，为此我们可以将整个查询过程分开来，使用临时表的策略：先将一部分数据筛选出来，出入临时表，然后在临时表上建立索引，最后再用临时表代替 t2 去跟 t1 联查。也就是这样的形式：

  1. 创建一张临时表，为关联字段加上索引
  2. 先从 t2 查出数据，然后插入临时表
  3. 让临时表代替 t2 去跟 t1 联查。

对应的 sql 就像这样：

1
2
3
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);

Hash join

当然，仔细想想，临时表中虽然数据少了很多，但是仍然摆脱不了对数据集的遍历，为此，最好的做法就是使用 hash join，1000*2000次查找换成1000次哈希查找。由于 mysql 并不支持 hash join，所以我们需要自己使用业务代码来实现：

  1. 先查出 t2 的数据，存入 HashMap 这样的结构
  2. 查出 t1 的数据，根据需要从数据结构中去获取值

四、总结

在默认情况下，最好做到以下两点：

  1. 尽量为被驱动表的连接条件加上索引；
  2. 使用小表作为驱动表（即查询行数少的，查询字段少的表）。

在以上情况下，可以继续扩展的做法：

  1. 已经为关联字段建索引的情况：开启 MRR 支持，将 NJL 算法优化为 BKA 算法
  2. 还没有为关联字段建索引的情况：
    • 加索引，将 BNL 算法优化为 NJL 算法；
    • 使用临时表；
    • 在业务代码中实现 hash join。

其中，对应没有给关键字建索引的情况，要注意根据情况调整 join_buffer_size 以减少对表的减少扫描次数：

  1. 一方面，可以提高查找效率；
  2. 另一方面，减少对了 Buffer Pool 的影响，尽可能避免影响内存命中率。
0%