在使用 JOIN 语句时，有的同学可能会告诉你：

• 要尽量避免使用 JOIN，太危险了！

• 使用 JOIN SQL 一定要注意连接与筛选条件，否则"笛卡尔积"会让你的程序崩掉！

• ......

今天我们就来介绍 JOIN 连接的底层工作原理。（注：本文不会对 JOIN 语法进行介绍，JOIN 的使用语法请自行搜索参阅相关文章）。

一、数据准备

首先创建表 t1 和表 t2：

• 这两个表都有一个主键索引 id 和一个索引 a，字段 b 上无索引。

• 存储过程 idata()往表 t2 里插入了 1000 行数据，在表 t1 里插入的是 100 行数据。

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);

二、Index Nested-Loop Join（NLJ 算法）

2.1-NLJ 测试语句

首先我们执行如下的语句：

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

2.2-EXPLAIN 结果分析

首先，表 t2 有索引 a，因此 JOIN 语句用到了表 t2 的索引 a。

表 t1 的 rows 和 filtered 都为 100，因此扫描了 100 行数据。

表 t2 的 rows 为 1，filtered 的数量为 100，表明表 t2 一共会扫描 100 行数据，而不是全表扫描。

因此该 JOIN 语句一共扫描了 200 行数据（表 t1 100+表 t2 100）。

2.3-NLJ 算法分析

上面 EXPLAIN 语句的执行结果，表明使用到了 NLJ 算法。

其执行流程为：

• 从表 t1 中取第一行数据，然后使用表 t2 的索引 a，找到表 t2 中与表 t1 这一行匹配的数据（使用 a 字段匹配，见上面 SQL 语句）。

• 匹配到之后从表 t2 中取第二行数据，然后使用表 t2 的索引 a，找到表 t2 中与表 t1 第二行匹配的数据。

• 以此类推.....

• 直到表 t1 的 100 行数据都匹配完成。这里表 t1 总共扫描了 100 行，表 t2 由于使用到了索引 a，因此也扫描了 100 行。所以总共就扫描了 200 行数据。

上面的算法也可以用如下的一张图来表示：

2.4-将小表作为驱动表提高效率

介绍两个概念：

• 驱动表：主动发起连接的一张表。上述表 t1 就是驱动表。

• 被驱动表：被 JOIN 的一张表。上述表 t2 就是被驱动表。

如果将表 t1 作为驱动表，则执行流程复杂度为：

• 遍历表 t1 的每一行，总共扫描 100 行。

• 然后使用表 t2 的索引去匹配扫描 100 行。

• 总共扫描了 200 行。

如果将表 t2 作为驱动表，则执行流程复杂度为：

• 遍历表 t2 的每一行，总共扫描 1000 行。

• 然后使用表 t2 的索引去匹配扫描 100 行。

• 总共扫描了 1100 行。

总结：因此将小表作为驱动表可以提高 SQL 的执行效率。

三、Simple Nested-Loop Join（SNL）

当 JOIN 语句无法使用到表的索引时，就不能使用 NLJ 算法了，而是改为了全表扫描。

例如，我们改写 SQL 语句，连接条件如下，其中使用 t1 的 a 字段与 t2 的 b 字段进行匹配。

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

由于没有使用到表 t2 的索引，因此此时其 JOIN 流程如下：

• 从表 t1 中取第一行数据，然后全表扫描表 t2，找到表 t2 中与表 t1 这一行匹配的数据（使用 a 字段匹配，见上面 SQL 语句）。

• 匹配到之后从表 t2 中取第二行数据，然后全表扫描表 t2，找到表 t2 中与表 t1 第二行匹配的数据。

• 以此类推.....

• 直到表 t1 的 100 行数据都匹配完成。这里表 t1 总共扫描了 100 行，表 t2 扫描了 100*1000=10 万行。所以总共就扫描了 100100 行数据。

当然，这只是一个 1000 行的表，当表的数量更多时，表的扫描行数就呈指数形式增长了。

小结：

• 以上就是 SNL 算法的执行流程。

• 当然，MySQL 没有使用这个算法，而是使用 BNL 算法做了一个改进。

四、Block Nested-Loop Join（BNL）

这时候，被驱动表上没有可用的索引，算法的流程是这样的：

• 把表 t1 的数据读入线程内存 join_buffer 中，由于我们这个语句中写的是 select *，因此是把整个表 t1 放入了内存；

  扫描表 t2，把表 t2 中的每一行取出来，跟 join_buffer 中的数据做对比，满足 join 条件的，作为结果集的一部分返回。

流程图如下：

3.1-BNL 相比于 SNL 的优点

• 前面我们说过，如果使用 Simple Nested-Loop Join 算法进行查询，扫描行数也是 10 万行。因此，从时间复杂度上来说，这两个算法是一样的。

• 但是，Block Nested-Loop Join 算法的这 10 万次判断是内存操作，速度上会快很多，性能也更好。

3.2-在 BNL 算法下，选择大表还是小表作为驱动表？

我们知道，在 BNL 算法下，数据都是在 join_buffer 中进行连接和筛选的，表的数据是无限的，但是 join_buffer 的大小是有限的。

因此当表 t1 的数据大于 join_buffer 的大小时，此时 JOIN 语句的执行流程如下：

• 1. 扫描表 t1，顺序读取数据行放入 join_buffer 中，假设放完第 88 行 join_buffer 满了，继续第 2 步；

• 2. 扫描表 t2，把 t2 中的每一行取出来，跟 join_buffer 中的数据做对比，满足 join 条件的，作为结果集的一部分返回；

• 3.清空 join_buffer；

• 4. 继续扫描表 t1，顺序读取最后的 12 行数据放入 join_buffer 中，继续执行第 2 步。

我们再来看下，在这种情况下驱动表的选择问题。

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

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

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

• 1.扫描行数是 N+λ*N*M；

  2.内存判断 N*M 次。

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

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

五、小结

阅读完整篇文章之后，你应该清楚 JOIN 有哪些工作类型了：

• NLJ：效率高，

• SNL：效率最低。

• BNL：效率比 SNL 高，但是存在全表扫描，效率仍然比较低下。

另外，在使用 JOIN 时需要考虑如下内容：

• 如果可以使用被驱动表的索引，那么 JOIN 语句性能还是可以的；

• 如果不能使用被驱动表的索引，只能使用 Block Nested-Loop Join 算法，那么尽量少用 JOIN 语句。

• 在使用 JOIN 语句时，应该让小表做驱动表。