【原创】JOIN 详述（中）

JOIN 的执行流程

建表

create table test8 (id int(11) PRIMARY key,a int(11) not null, b int(11) not null,key a(`a`))

delimiter ;;
CREATE PROCEDURE idata()
BEGIN
    DECLARE i int;
    set i = 1;
    WHILE i < 1000 DO
        INSERT into test8 values(i,i,i);
        SET i = i + 1;
    END WHILE;
END;;
delimiter ;
CALL idata();

CREATE table test9 like test8;

INSERT into test9 (select * FROM test8 WHERE id <= 100)

Index Nested-Loop Join

对于如下 SQL 语句:

select * FROM test9 STRAIGHT_JOIN test8 on test9.a = test8.a;

NOTE:
STRAIGHT_JOIN 可以手动指定驱动表和被驱动表，而不要经过优化器的判断，有时候可以用来优化 JOIN 查询，但最好不要那么做，因为现在的优化器会做出合理的判断。上述 SQL 只是为了便于分析！

上述SQL的执行计划如下：

执行计划1.png

由于被驱动表 test8 的字段 a 上有索引，join 过程用上了该索引，所以上述 SQL 的执行流程如下：

1. 从表 test9 取出一行 D
2. 取出D行中的 a 的值到表 test8 中去查找
3. 取出 test8 中满足条件的行，和 R 组成一行，作为结果集的一部分
4. 重复执行 步骤 1 到步骤 2 ，直到取到表 test9 的最后一行

上述流程称之为 "Index Nested-Loop Join"，简称 NIJ
在这个流程中，对表 test9 做全表扫描，需要扫描 100 行，对于每一行 D，根据 a 字段去表 test8 查找，由于走的是树的搜索过程，因此每次搜索都只扫描一行，也是总共扫描 100 行，所以整个流程一共扫描 200 行。

假设驱动表的行数是 N，被驱动表的行数 是 M，那整个过程的复杂度近似是 N + 2 * N * log₂M，显然 N 的值对扫描行数更大些，所以应该用小表做驱动表

Simple Nested-Loop Join

对于如下 SQL 语句

select * FROM test9 STRAIGHT_JOIN test8 on test9.b = test8.b;

NOTE：
b 字段没有建立索引

如果继续使用 上述的流程，那么这个 SQL 得扫描 100 * 1000 = 10万 行数据，如果两个表的行数都比价大，那么这样速度会很慢，好在 MySQL 没有使用这个，而是使用了一个叫 "Block Nested-Loop Join"
的算法，简称 BNL。

Block Nested-Loop Join

被驱动表上没有索引，则执行的流程是：

1. 把表 test9(驱动表) 的数据读入线程内存 join_buffer ，由于是 select * ，因此是把整个表 test9 放入内存中
   2.扫描表 test8(被驱动表) ，把 test8 中的每一行和 join_buffer 中的数据做对比，满足 join 条件的作为结果集的一部分返回。

其执行计划如下：

image.png

虽然也是扫描了 100 * 1000 = 10 万 行，但是这十万次判断是在内存中进行，速度上会快很多，性能也会更好。
在这种情况下，应该选择哪个表作为驱动表？
假设小表的行数是 N，大表的行数是 M，那么在这个算法中：
1.两个表都要做一次全表扫描，扫描行数是 M + N
2.在内存中判断次数是 M * N
因此不论谁做驱动表都是一样的

如果 join_buffer 一次放不下驱动表的数据，则需要驱动表的数据分段放进 join_buffer ，则流程是：
1.取驱动表的一部分数据放入 join_buffer，直至 join_buffer 放不了
2.扫描被驱动表的每一行数据，跟 join_buffer 中的数据做对比，满足
join 条件的数据作为结果集的一部分返回
3.清空 join_buffer
4.继续读取驱动表剩下的数据，重复步骤 1 到步骤 3，一直驱动表的数据被扫描完
若驱动表的行数是 N，需要分 K 段才能扫描完，被驱动表的行数是 M
则扫描的行数是 N + K * M （N 越大，K 越大） ==> N + λ * N * M( 0 < λ < 1 )
内存判断次数还是 N + M
由此可见在 M ，N 大小固定的情况下，N越小，其扫描行数越小。

综上所述，
1.如果是 NLJ 算法，应该选择小表做驱动
2.如果是 BNL 算法

• 如果 join_buffer 足够大，是一样的
• 如果 join_buffer 不是足够大，应该选择小表做驱动表

所以不管如何，都应该选择小表作为驱动表

[备注] 参考了 极客时间 的 MySQL实战45讲。链接如下：
https://time.geekbang.org/column/article/79700