mysql表中的join NLJ,BNL算法
- 1、什么是NLJ算法？
- 2、什么是BNL算法？
- 3、被驱动表的关联字段没索引为什么要选择使用 BNL 算法而不使用 Nested-Loop Join 呢？
- 4、对于小表的定义
什么是NLJ算法
nlj Nested-Loop Join(嵌套循环连接)
一次一行循环地从第一张表(称为驱动表)中读取行,再这行数据中取到关联字段,根据关联字段在领一张表(被驱动的表)里取出满足记录的行,然后取出俩张表的结果集合
比如这条sql语句
驱动表会选取数据量比较小的一张表,根据下图的执行计划截图,驱动表是t2表 被驱动表为t1。
EXPLAIN select * from t1 inner join t2 on t1.a= t2.a;
大致执行过程
- 从表t2中读取一行数据(如果t2表有查询过滤条件的,会从过滤结果里取出一条数据)
- 从第一步的数据中,取出关联字段a,到表t1中查询
- 取出表t1中满足条件的行,跟t2中获取到的结果合并,作为结果返回给客户端
- 重复前三个步骤
执行效率计算：整个过程会读取 t2 表的所有数据(扫描100行)，然后遍历这每行数据中字段 a 的值，根据 t2 表中 a 的值索引扫描 t1 表中的对应行(扫描100次 t1 表的索引，1次扫描可以认为最终只扫描 t1 表一行完整数据，也就是总共 t1 表也扫描了100 行)。因此整个过程扫描了 200 行。
如果被驱动表的关联字段没索引,使用NLJ算法性能会比较低,mysql会选择Block nested-loop join算法
BNL算法
BNL block nested-loop join(基于快的嵌套循环连接)
把启动表的数据读到join_buffer中,然后扫描被驱动表,把被驱动表每一行取出来跟join_buffer中的数据作对比
就比如说下面这个sql，Extra 中 的Using join buffer (Block Nested Loop)说明该关联查询使用的是 BNL 算法。
EXPLAIN select * from t1 inner join t2 on t1.b= t2.b;
上面sql的大致执行过程：
1、 把 t2 的所有数据放入到 join_buffer 中。
2、把表 t1 中每一行取出来，跟 join_buffer 中的数据做对比。
3、返回满足 join 条件的数据。
4、重复前三个步骤。
执行效率计算：整个过程对表 t1 和 t2 都做了一次全表扫描，因此扫描的总行数为10000(表 t1 的数据总量) + 100(表 t2 的数据总量) = 10100。并且 join_buffer 里的数据是无序的，因此对表 t1 中的每一行，都要做 100 次判断，所以内存中的判断次数是 100 * 10000= 100 万次。
join buffer一次性放不下t2表怎么办？
join_buffer 的大小是由参数 join_buffer_size 设定的，默认值是 256k。如果放不下表 t2 的所有数据话，策略很简单， 就是分段放。
举栗子：比如 t2 表有1000行记录， join_buffer 一次只能放800行数据，那么执行过程就是先往 join_buffer 里放800行记录，然 后从 t1 表里取数据跟 join_buffer 中数据对比得到部分结果，然后清空 join_buffer ，再放入 t2 表剩余200行记录，再 次从 t1 表里取数据跟 join_buffer 中数据对比。所以就多扫了一次 t1 表。
被驱动表的关联字段没索引为什么使用BNL算法而不使用Nested-Loop Join呢
如果上面第二条sql使用 Nested-Loop Join，那么扫描行数为 100 * 10000 = 100万次，这个是磁盘扫描。 很显然，用BNL磁盘扫描次数少很多，相比于磁盘扫描，BNL的内存计算会快得多。 因此MySQL对于被驱动表的关联字段没索引的关联查询，一般都会使用 BNL 算法。如果有索引一般选择 NLJ 算法，有 索引的情况下 NLJ 算法比 BNL算法性能更高。
对于小表的定义
在决定哪个表做驱动表的时候，应该是两个表按照各自的条件过滤，过滤完成之后，计算参与 join 的各个字段的总数据 量，数据量小的那个表，就是“小表”，应该作为驱动表。