本文主要记录了 MySQL的JOIN语句的NLJ、BLJ和MySQL8.0新增的Hash Join算法,及相关优化如MRR、BKA等,最后回答了到底能不能使用JOIN,驱动表又该如何选择等问题。

1.概述

join语句常见算法为NLJ、BNL和MySQL8.0新增的Hash Join,同时也会使用到MRR和BKA优化。

然后是两个问题

  • 1)到底该不该使用join?
  • 2)如果用那么驱动表又该如何选择?

2. join算法

1. Index Nested-Loop Join(NLJ)

NLJ算法跟我们写程序时的嵌套查询类似,并且可以用上被驱动表的索引,所以我们称之为“Index Nested-Loop Join”,简称 NLJ。

假设为如下查询语句

1
2
# 被驱动表表t2 a列上有索引
select * from t1 straight_join t2 on (t1.a=t2.a);

NLJ具体执行过程如下:

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

如果不使用 join 又该如何手动实现呢:

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

整个过程中扫描行数一致,但是总共执行了 101 条语句,比直接 join 多了 100 次交互。除此之外,客户端还要自己拼接 SQL 语句和结果。

到底该不该使用join?

可以看到,在被驱动表可以使用索引的情况下,使用join效率比手动实现更高。

如何选择驱动表?

在这个 join 语句执行过程中,驱动表是走全表扫描,而被驱动表是走树搜索,所以应该让小表来做驱动表。

假设被驱动表行数为M,需要先走二级索引,在走主键索引,时间复杂度为2*log2M

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

因此整个执行过程,近似复杂度是 N + N2log2M

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

2. Simple Nested-Loop Join

如果查询字段上没有索引,MySQL 还会用前面同样的算法吗?

如果表t1,t2分别都有10万行,无法走索引那么一共需要扫描10万*10万行。

这就是Simple Nested-Loop Join 算法,虽然看起来结果是正确的,但是效率太低了。

当然,MySQL 也没有使用这个 Simple Nested-Loop Join 算法,而是使用了另一个叫作“Block Nested-Loop Join”的算法,简称 BNL

3. Block Nested-Loop Join(BNL)

由于Simple Nested-Loop Join 算法实在太笨了,所以MySQL对其进行了优化,就是这里的BLJ算法。

具体流程如下:

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

同样需要扫描两个表,但是比较操作是在内存中比较,速度上会快很多,性能也更好

如果表t1实在太大了,内存都放不下则会进行分段处理,一块一块的加载到内存中,所以叫 Block Nested-Loop Join。

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

驱动表选择?

可以看到,驱动表被分成多少块,被驱动表就会被扫描多少次,所以还是推荐小表做驱动表,以减少被驱动表的扫描次数。

4. Hash join

MySQL8.0中新增了Hash join方式,不过只能用于等值连接

Hash join 不需要索引的支持。大多数情况下,hash join 比之前的 BNL 算法在没有索引时的等值连接更加高效。

具体步骤:

  • 1)把把驱动表相关字段存入Join Buffer,这一步和BNL套路相同。
  • 2)(build)把Join Buffer中对应的字段值生成一个散列表,保存在内存中。
  • 3)(probe)扫描被驱动表,对被驱动表中的相关字段进行散列并比较。

在最好的场景下,如果Join Buffer能覆盖驱动表所有相关字段,那么在查询的过程中驱动表和被驱动表都只需要扫描一次,如果散列算法够好,比较次数也只是被驱动表的记录数。

在MySQL8.0以后优化器会优先选择使用hash join。

3. 问题

1. 可以用join吗?

  • 1)如果可以使用 NLJ 算法,也就是说可以用上被驱动表上的索引,其实是没问题的,当然了Hash join也是可以的。
  • 2)如果使用 BNL 算法,扫描行数就会过多。尤其是在大表上的 join 操作,这样可能要扫描被驱动表很多次,会占用大量的系统资源。所以这种 join 尽量不要用。

所以你在判断要不要使用 join 语句时,就是看 explain 结果里面,Extra 字段里面有没有出现“Block Nested Loop”字样。

2. 如何选择驱动表?

根据前面的分析可以发现,不管是NLJ算法还是BLJ算法,都是推荐使用小表来做驱动表

那么如何确定小表呢?

并不是表的数据量小就是小表,而是应该是两个表按照各自的条件过滤,过滤完成之后,计算参与 join 的各个字段的总数据量,数据量小的那个表,就是“小表”,应该作为驱动表。

4. join相关优化

1. Multi-Range Read

夺命三连

What

MRR是一种将查询时的随机读转为顺序读的优化手段。

Why

那当然是磁盘的随机读比顺序读慢嘛。

我们都知道对除Id以外字段做范围查询时先走二级索引(如果有索引),然后根据主键id去主键索引树一条条查找,这个过程也叫做回表。

主键索引是按主键顺序排的,但是按二级索引范围查询出来的结果,主键不一定是顺序排列的,大多数情况下都是乱序的。

所以对主键索引来说每次查询都是随机读。

How

举个栗子

优化前:

  • 1)根据查询条件在二级索引树中找到主键id;
  • 2)去主键索引根据id找到对应数据;
  • 3)重复步骤12直到查询出所有满足条件的行;

优化后:

  • 1)根据二级索引,定位到满足条件的记录,将 id 值放入 read_rnd_buffer 中 ;
  • 2)将 read_rnd_buffer 中的 id 进行递增排序;
  • 3)根据排序后的 id 数组,依次到主键 id 索引中查记录,并作为结果返回;

可以看到主要就是将id暂时存在到read_rnd_buffer 中,将其排序后再去主键索引中查询。

2. Batched Key Access

What

这个 BKA 算法,其实就是对 NLJ 算法的优化,因为NLJ是先在驱动表中取一条数据然后去被驱动表中匹配的。

这样的话就用不了前面的MRR优化了。

Why

虽然NLJ因为可以用到被驱动表的索引,效率不错,但还是有进一步优化的空间,BKA算法则是对其的一个优化,

使得优化后的NLJ也可以用到MRR。

How

优化前:

从驱动表 t1,一行行地取出 a 的值,再到被驱动表 t2 去做 join。也就是说,对于表 t2 来说,每次都是匹配一个值。这时,MRR 的优势就用不上了

优化后:

先把表 t1 的数据取出来一部分,先放到一个临时内存 join_buffer中,这样就可以使用MRR进行优化了,将这部分数据排好序后再去t2中查询。

该算法需要手动开启,命令如下

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

5. 参考

MySQL45讲

https://dev.mysql.com/doc/refman/8.0/en/nested-loop-joins.html

https://dev.mysql.com/doc/refman/8.0/en/hash-joins.html

https://dev.mysql.com/doc/refman/8.0/en/mrr-optimization.html

https://dev.mysql.com/doc/refman/8.0/en/bnl-bka-optimization.html

https://blog.csdn.net/horses/article/details/102690076