MySQL中3表join流程分析

常听说MySQL中3表 join 的执行流程并不是前两张表 join 得出结果，再与第三张表进行 join；而是3表嵌套的循环连接。那这个3表嵌套的循环连接具体又是个什么流程呢？与前两张表 join 得出结果再与第三张表进行 join 的执行效率相比如何呢？下面通过一个例子来分析分析。

前提

set optimizer_switch='block_nested_loop=off';
关联字段无索引的情况下强制使用索引嵌套循环连接算法，目的是更好的观察扫描行数。

表结构和数据如下：

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;
create table t3 like t2;
insert into t1 (select * from t2 where id<=100);
insert into t3 (select * from t2 where id<=200);

示例SQL：

select * from t1 join t2 on t1.b=t2.b  join t3 on t1.b=t3.b where t1.a<21;

通过扫描行数结果分析join过程

通过 slow log 得知一共扫描 24100 行：

# Query_time: 0.016162  Lock_time: 0.000249 Rows_sent: 20  Rows_examined: 24100
SET timestamp=1617348099;
select * from t1 join t2 on t1.b=t2.b  join t3 on t1.b=t3.b where t1.a<21;

执行计划显示用的索引嵌套循环连接算法：

mysql> explain select * from t1 join t2 on t1.b=t2.b  join t3 on t1.b=t3.b where t1.a<21;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
| 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 |    20.00 | Using where |
|  1 | SIMPLE      | t3    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  200 |    10.00 | Using where |
|  1 | SIMPLE      | t2    | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 1000 |    10.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+

扫描行数构成：

• t1 扫描 100行；
• t3 扫描 20*200=4000 行；
• t2 扫描 20*1000=20000 行。

总行数=100+4000+20000=24100。
从这个结果来看，join 过程像是先 t1 和 t3 join 得出 20 行中间结果，再与 t2 进行 join 得出结果。这结论与我们通常认为的 3表 join 实际上是3表嵌套的循环连接不一样，接着往下看。

通过执行成本分析join过程

查看执行计划成本：
mysql> explain format=json select * from t1 join t2 on t1.b=t2.b join t3 on t1.b=t3.b where t1.a<21\G

其他信息：

• t1表100行，只有1个数据页(可通过mysql.innodb_table_stats)；
• t2表1000行，有4个数据页；
• t3表200行，只有1个数据页；
• io_block_read_cost=1.0，成本常数(MySQL5.7)：读取一个页面花费的成本默认是1.0；
• row_evaluate_cost=0.2，成本常数(MySQL5.7)：读取以及检测一条记录是否符合搜索条件的成本默认是0.2。

t1 是驱动表，全表扫描

• 扫描 100行；
• 预估满足条件的只有 20%，即 100*20%=20，即t1的扇出。

IO成本=1*1.0=1
CPU成本=100*0.2=20
t1总成本=21

t3 是被驱动表，全表扫描

• 每次扫描200行；
• 因为驱动表扇出为20，所以要查找20次t3，总共会扫描 20*200=4000 行；
• 预估满足条件的行只有扫描行数的 10%，即 4000*10%=400，即为 t1 join t3 后的扇出，即 rows_produced_per_json。

IO成本=1*1.0=1
CPU成本=200*0.2=40
t3表总成本=驱动表扇出*(IO成本+CPU成本)=20*(1+40)=820
阶段性总成本=21+820=841
此处 eval_cost=80，实则为驱动表扇出*被驱动每次扫描行数*filtered*成本常数，即 20*200*10%*0.2。
简化公式为：eval_cost=rows_produced_per_json*成本常数

t2 也是被驱动表，全表扫描

• 每次查找扫描1000行；
• 要查找 400 次，总共会扫描 400*1000=400000 行；
• 预估满足条件的只有 10%，即 400000*10%=40000，即为 t2 的扇出，即 rows_produced_per_json。

IO成本=4*1.0=4
CPU成本=1000*0.2=200
t2表总成本=前2表join的扇出*(IO成本+CPU成本)=400*(4+200)=81600
阶段性总成本=841+81600=82441
此处 eval_cost=8000，即 rows_produced_per_json*成本常数，即 40000*0.2

根据执行计划成本分析：

• t1 表查找 1 次，每次扫描 100行；
• t3 表查找 20 次，每次扫描 200 行；
• t2 表查找 400 次，每次扫描 1000 行。

这样看，3表 join 流程是：

1. 全表扫描 t1，满足条件的有 20 行，先取第1行数据记为 R1；
2. 从 R1 中取出 b 字段去 t3 表中查找；
3. 取出 t3 中满足条件的行，跟 R1 组成一行，作为结果集的一部分，从结果集中取第1行数据记为 X1；
   a. 从X1 中取出 b 字段去 t2 表中查找；
   b. 取出 t2 中满足条件的行，跟 X1 组成一行，作为结果集的一部分；
   c. 重复 a、b 步骤，直到结束。
4. 重复 2、3步骤，直到结束。

图示(这里展示的是索引嵌套循环算法时3表join的流程，块循环嵌套算法不一样)：

注意，由于造的数据比较特殊，所以第 3 步得出的中间结果集实际上只有 1行，所以最终 t2 表的查找次数是 20*1=20，所以扫描总行数是 20*1000。所以单看 slow log 中显示的 24100 行，会误认为是先得出 t1 和 t3 join 的结果，再去和 t2 进行 join。

当我调整 t3 的数据，删除20行，再插入20行，使满足 b<21 的数据翻倍，这样“第 3 步得出的中间结果集”变成 2 行：

mysql> delete from t3 where id>180;
Query OK, 20 rows affected (0.00 sec)
mysql> insert into t3 select * from t3 where b<21;
Query OK, 20 rows affected (0.00 sec)

再来看slow log 中扫描的总行数为44100，t1、t3的扫描行数不变，t2 的扫描行数变为 20*2*1000=40000：

# Query_time: 0.013848  Lock_time: 0.000100 Rows_sent: 40  Rows_examined: 44100
SET timestamp=1617354884;
select * from t1 join t2 on t1.b=t2.b  join t3 on t1.b=t3.b where t1.a<21;

为什么执行计划中分析得到的是 t2 表查找 400 次呢？
因为执行计划对t1 join t3 的扇出是个估算值，不准确。而 slow log 是真实执行后统计的，是个准确值。

为什么执行计划中，t2表的执行次数是用“t1 join t3 的扇出”表示的？这不是说明 t1 先和 t3 join，结果再和 t2 join？
其实拆解来看，“3表嵌套循环” 和 “前2表 join 的结果和第3张表 join” 两种算法，成本是一样的，而且如果要按3表嵌套循环的方式展示每张表的成本将非常复杂，可读性不强。所以执行计划中这么表示没有问题。

总结

总的来说，对于3表join或者多表join 来说，“3表嵌套循环” 和 “先2表 join，结果和第3张表join” 两种算法，成本是一样的。要注意的一点是3表嵌套循环成本并非如下图写的：nmx，而是 n(m+ax)，其中 a 为 t2 满足单个等值条件的平均值。

当被驱动表的关联字段不是唯一索引，或者没有索引，每次扫描行数会大于1时，其扇出误差会非常大。比如在上面的示例中：
t3 实际的扇出只有 20，但优化器估算值是 总扫描行数的 10%，由于t3表的关联字段没有索引，所以每次都要全表扫描200行，总的扫描行数=20*200=4000，扇出=4000*10%=400，比实际的20大了20倍。尤其对于后续表的 join 来说，成本估算会产生更严重的偏差。

如果是 left join，每个被驱动表的 filtered 都会被优化器认定为 100%，误差更大！

通常建议join不超过2表，就是因为优化器估算成本误差大导致选择不好的执行计划，如果要用，一定要记住：关联字段必须要有索引，最好有唯一性或者基数大。