正文

建表语句

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

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

"straight_join" 是一种特殊的 join，它基于连接操作的顺序完成。

通过 explain 命令查询出来的结果。

id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	NULL	ALL	a	NULL	NULL	NULL	100	100.00	Using where
1	SIMPLE	t2	NULL	ref	a	a	5	mysql45.t1.a	1	100.00	NULL

• t1 作为驱动表，t2 作为被驱动表，由于 t2 的 a 上是有索引的。
• 从 t1 中取出一行 R，到 t2 上去查找。
• t2 上满足条件的结果，分别跟 R 组成一行，作为结果集中的一部分。
• 循环，直到 t1 结束。

这个过程类似嵌套查询，并且用到了被驱动表上的索引，叫做 Index Nested-Loop Join（索引嵌套循环连接）。

这个过程只扫描了 200 行，过程如下。

1. 对驱动表进行全表扫描，为 100 行，每一行记为 R。
2. 每一行 R 去 t2 上查找，由于走的是索引，所以又扫描了 100 行，所以加起来是 200 行。

笔记

这里可能会有误解，就是说我搜索的是 *，而不是主键，为什么 t2 上只扫描了 100 行，难道不应是再回表扫描 100 行吗？

"rows" 的计数通常是指数据库需要在具体的数据行上执行的工作，因为即使是回表操作了，查询的还是同一行，并不会新增行数。

该不该用 join？

• 如果不用 join 直接使用单表查询，效果会是执行了 101 条语句，select * from t1+(select * from t2 where a = t1.a)*100，除此之外客户端还要自己拼接结果。显然还不如直接用 join。
• 而使用 join，驱动表的时间复杂度是 O (n)，被驱动表走的是索引，每一行的时间复杂度是 O ($log_2{m}$)，因为要回表一次所以再乘上 2，n 行为 O ($n \times 2 \times log_2{m}$)。总计的时间复杂度就是 O (n + $2nlog_2{m}$)，通过这个公式可以发现，n 对于这个值的影响是最大的，应该让 n 越小越好，所以就是让小表作为驱动表是最合适的。

Simple Nested-Loop Join

Simple Nested-Loop Join（简单嵌套循环连接），首先对两个要连接的表一中的每一行，再对另一个表二进行完全扫描，查找是否有满足连接条件的行。所以如果表一有 M 行，表二有 N 行，那么总共需要进行$M \times N$ 次比较。

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

由于 t2 的 b 字段上没有索引，这个时候就要做一次全表扫描了。这样算下来，总共要扫描$100 \times 1000 = 100000$ 行，这还是比较小的表了，如果都是 10 万行的数据，最后就要扫描 100 亿行。这个性能是不可接受的。

所以 MySQL 也没使用这种算法，而是使用了 Block Nested-Loop Join。

Block Nested-Loop Join

Block Nested-Loop Join（块嵌套循环连接），将一个表（通常是较小的表或选择性更高的表）的一部分数据（一个块）加载到内存中。然后，我们会从磁盘读取另一个表（通常是较大的表）的数据，（注意：即使是从大表中读取的数据，它们也是被分块加载到内存中的。）对其进行扫描，每次读取一个数据元素，然后与内存中的块进行比较。

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

这条语句的执行过程是

1. 把 t1 的数据读取一部分到内存 join_buffer 中。
2. 读取 t2，把 t2 每一行读取出来，跟 join_buffer 比较，如果满足了 join 条件，作为结果集一部分返回。

id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	NULL	ALL	a	NULL	NULL	NULL	100	100.00	NULL
1	SIMPLE	t2	NULL	ALL	NULL	NULL	NULL	NULL	1000	10.00	Using where; Using join buffer (hash join)

在这个过程中扫描了 1100 行，由于 t1 每一行都要到 t2 上全部扫描，所以做了$1 \times 1000 \times 100 = 100000$ 次操作。但是这个过程是在内存中进行操作的，并不会有很长的等待时间。 所以这个时间复杂度理论上就是 O$(n \times m)$。

然后，上面说了较小的表，一部分等这些并没有在例子中有解释。现在解释一下。

如果说 t1 是个大表，join_buffer 中并不能放下怎么办？join_buffer 的大小是由参数 join_buffer_size 设定的，默认值是 256k。所以这就是上面所说的一部分的概念，如果放不下表 t1 的所有数据话，策略很简单，就是分段放。

• 比如说扫描 t1，到 88 行 join_buffer 满了。
• 扫描 t2，把 t2 中一部分取出来，到内存中跟 t1 比较，满足了就返回。
• 清空 join_buffer。继续上面的步骤。

所以 Simple Nested-Loop Join 和 Block Nested-Loop Join 最大的不同就是，后者是将一部分查询结果放入到内存中，而前者是读取一行放一行，IO 会很频繁的操作。

如果分段了，假设驱动表的数据为 N，需要分成 K 段才能完成，被驱动表的数据为 M，K 越大 N 就会越大。

在这个过程中扫描的行数为 K*M+N 行，时间复杂度基本上为$O(N+K \times M)$。

注意

要注意的是在最新版的 MySQL (8.3) 中已经看不到这个 Block NLJ 了，通过 explain 命令会有一个 hash join 的算法。

该不该用 join？

1. 如果可以使用 Index Nested-Loop Join 算法，也就是说可以用上被驱动表上的索引，没问题。
2. 如果使用的是 Block Nested-Loop Join 算法，这种的会导致被驱动表被扫描很多次，不要用。

如果要使用 join，应该选择大表做驱动表还是选择小表做驱动表？

1. 如果是 Index Nested-Loop Join 算法，应该选择小表做驱动表。
2. 如果是 Block Nested-Loop Join 算法。
   • 在 join_buffer_size 足够大的时候，是一样的。
   • 在 join_buffer_size 不够大的时候（这种情况更常见），应该选择小表做驱动表。
   • 所以，这个问题的结论就是，总是应该使用小表做驱动表。

什么是 “小表”？

--  这两个语句都没用到索引字段b
select * from t1 straight_join t2 on (t1.b=t2.b) where t2.id<=50;
select * from t2 straight_join t1 on (t1.b=t2.b) where t2.id<=50;

这上面这个语句中使用第二条是更好的，虽然 t2 有 1000 条数据，但是这里小表的意义是在 join_buffer 中的数据，而不是字面意义上的，在 where 条件中只去了 t2 的前 50 行，所以 join_buffer 里只有 50 行数据，显然是更合适的。

select t1.b,t2.* from  t1  straight_join t2 on (t1.b=t2.b) where t2.id<=100;
select t1.b,t2.* from  t2  straight_join t1 on (t1.b=t2.b) where t2.id<=100;

在这个例子中只需要的查询 t1 的 b 字段，而需要查询 t2 的所有数据，因此如果 t2 作为驱动表的话，需要存所有数据到 join_buffer 中，而 t1 作为驱动表只需要存储 b 字段即可。

在决定哪个表做驱动表的时候，应该是两个表按照各自的条件过滤，过滤完成之后，计算参与 join 的各个字段的总数据量，数据量小的那个表，就是 “小表”，应该作为驱动表。

上一章答案

如果客户端由于压力过大，迟迟不能接收数据，会对服务端造成什么严重的影响？

这个问题主要造成了 “长事务”。

• 如果是更新语句，意味着正在占用某些行的锁，会导致个别的语句更新被锁住。
• 读取的语句也会受到影响，因为更新的时候会创建一个快照，在事务没提交之前，其他的事务不能读到，所以这样导致回滚段过长，undo log 过大。