JOIN查询时，我为什么建议你将小表放在前面？（NLJ，SNL，BNL算法全面解析）

在使用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);

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的执行效率。

当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算法做了一个改进。

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

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

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

流程图如下：

4.1-BNL相比于SNL的优点

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

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

4.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语句时，应该让小表做驱动表。