MySQL subquery、dependent subquery、uncacheable subquery 是怎么执行的？
前几天在看官方文档的时候，看到关于 dependent subquery 和 uncacheable subquery 的一句说明，被搞的神魂颠倒的，各种百度、谷歌也没有找到能够解释清楚这句话是什么意思的，去折腾了几天 5.7.35 版本的源码，对于 subquery、dependent subquery、uncacheable subquery 的执行过程，多了一些了解。
官方文档的说明是这样的：
DEPENDENT SUBQUERY evaluation differs from UNCACHEABLE SUBQUERY evaluation. For DEPENDENT SUBQUERY, the subquery is re-evaluated only once for each set of different values of the variables from its outer context. For UNCACHEABLE SUBQUERY, the subquery is re-evaluated for each row of the outer context.
我理解的意思大概是这样的：
dependent subquery 和 uncacheable subquery 的执行过程不一样。dependent subquery，对于外层查询的每一组变量的不同值，子查询只执行一次。uncacheable subquery，对于外层查询的每一行，子查询都会执行一次。
以前，我对于 dependent subquery 和 uncacheable subquery 的执行过程的理解是一样的： 对于外层查询的每一行，都会把子查询中使用到的外层查询的字段替换为具体的值，去执行一次子查询。
看了官方文档的说明之后，把我搞懵了，怎么也理解不了文档中那句话的意思，折腾完源码之后，发现了它们之间的不一样，接下来就说说 subquery、dependent subquery、uncacheable subquery 这 3 类子查询的执行过程。
进入正题之前，还有一点要唠叨一下，本文所讲的内容，是以
optimizer_switch='semijoin=off'以及optimizer_switch='materialization=on'为前提的，为什么呢？
因为，子查询有 5 种优化策略
- 子查询表上拉（table pullout）
- 重复值消除（duplicate weedout）
- 首次匹配（first match）
- 松散扫描（loose scan）
- 物化
第 1 ~ 4 种优化策略，子查询都不再是子查询了，会和外层查询组成一个连接（JOIN）查询，只有第 5 种优化策略，子查询还是那个子查询。
使用 optimizer_switch='semijoin=off' 就是把第 2 ~ 4 种优化策略给禁用了，使用 optimizer_switch='materialization=on' 就是把第 5 种优化策略启用了（当然，这个选项在 MySQL 5.7.35 中默认是开启的，其它版本没试过），至于第 1 种策略，本文的示例 SQL 中都不满足使用这种优化策略。
1. subquery
1select * from t1 where t1.i1 in (
2 select i1 from t3 where id in (3, 666, 990, 887, 76) and i2 > 16384
3);
1+----+-------------+-------+------------+-------+---------------+---------+---------+--------+------+----------+-------------+
2| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
3+----+-------------+-------+------------+-------+---------------+---------+---------+--------+------+----------+-------------+
4| 1 | PRIMARY | t1 | <null> | ALL | <null> | <null> | <null> | <null> | 8 | 100.0 | Using where |
5| 2 | SUBQUERY | t3 | <null> | range | PRIMARY | PRIMARY | 4 | <null> | 5 | 33.33 | Using where |
6+----+-------------+-------+------------+-------+---------------+---------+---------+--------+------+----------+-------------+
从 explain 结果可以看到，上面的 SQL 中子查询的执行方式 SUBQUERY，接下来我们通过 optimizer_trace 看一下它的大体执行方案：
1{
2 "join_preparation": {
3 "select#": 1,
4 "steps": [
5 {
6 "join_preparation": {
7 "select#": 2,
8 "steps": [
9 {
10 "IN_uses_bisection": true
11 },
12 {
13 "expanded_query": "/* select#2 */ select `t3`.`i1` from `t3` where ((`t3`.`id` in (3,666,990,887,76)) and (`t3`.`i2` > 16384))"
14 },
15 {
16 "transformation": {
17 "select#": 2,
18 "from": "IN (SELECT)",
19 "to": "semijoin",
20 "chosen": false
21 }
22 },
23 {
24 "transformation": {
25 "select#": 2,
26 "from": "IN (SELECT)",
27 "to": "EXISTS (CORRELATED SELECT)",
28 "chosen": true,
29 "evaluating_constant_where_conditions": []
30 }
31 }
32 ]
33 }
34 },
35 {
36 "expanded_query": "/* select#1 */ select `t1`.`id` AS `id`,`t1`.`str1` AS `str1`,`t1`.`str2` AS `str2`,`t1`.`str3` AS `str3`,`t1`.`str4` AS `str4`,`t1`.`i1` AS `i1`,`t1`.`type` AS `type`,`t1`.`i2` AS `i2`,`t1`.`blob1` AS `blob1` from `t1` where <in_optimizer>(`t1`.`i1`,<exists>(/* select#2 */ select `t3`.`i1` from `t3` where ((`t3`.`id` in (3,666,990,887,76)) and (`t3`.`i2` > 16384) and (<cache>(`t1`.`i1`) = `t3`.`i1`))))"
37 }
38 ]
39 }
40}
上面的 JSON 是 查询准备阶段 的 trace，从中可以看到，没有使用半连接进行子查询优化（"from": "IN (SELECT)", "to": "semijoin", "chosen": false），因为我通过设置 set optimizer_switch='semijoin=off' 把半连接优化给关掉了。
"from": "IN (SELECT)", "to": "EXISTS (CORRELATED SELECT)", "chosen": true 表示 IN 子查询被转换成了 EXISTS 相关子查询。
1{
2 "transformation": {
3 "select#": 2,
4 "from": "IN (SELECT)",
5 "to": "materialization",
6 "chosen": true,
7 "unknown_key_1": {
8 "creating_tmp_table": {
9 "tmp_table_info": {
10 "row_length": 5,
11 "key_length": 4,
12 "unique_constraint": false,
13 "location": "memory (heap)",
14 "row_limit_estimate": 3355443
15 }
16 }
17 }
18 }
19}
上面的 JSON 是 查询优化阶段 的 trace，从中可以看到，使用了物化（materialization）来优化子查询。
说完了大体的执行方案，接下来详细描述一下子查询执行的具体过程：
第 1 步
外层查询从存储引擎读取一条记录
第 2 步
1where <in_optimizer>(`t1`.`i1`,<exists>(/* select#2 */ select `t3`.`i1` from `t3` where ((`t3`.`id` in (3,666,990,887,76)) and (`t3`.`i2` > 16384) and (<cache>(`t1`.`i1`) = `t3`.`i1`))))
这是上面的 SQL 语句在查询准备阶段处理之后，WHERE 条件变成的样子，可以看到变成 exists 了，t1.i1 in (子查询) 变成了 (t1.i1) = t3.i1)
外层查询从存储引擎读取到第 1 条记录时，会对外层查询的 WHERE 条件进行求值，此时就会第一次执行子查询（注意：此时，外层查询的字段 t1.i1 就已经有具体的值了，这个在后面执行子查询时会用到这个字段的具体值）。
因为会使用物化表来存储子查询的结果集，所以，在第一次执行时，会把子查询符合条件的记录存储到物化表中。
对于子查询中查出来的每一条记录，会判断记录是否匹配 ((t3.id in (3,666,990,887,76)) and (t3.i2 > 16384) 这两个查询条件，匹配就插入到物化表，不匹配就忽略。
第 3 步
子查询结果集物化完成之后，会循环读取物化表的每一条记录，判断记录是否匹配 (t1.i1) = t3.i1)第 4 步。
可以看到子查询物化使用了个小技巧，在物化过程中，并没有使用下推到子查询的 (
( 条件去过滤记录，而是等到物化完成之后，从物化表中读取记录时，再用这个条件去过滤一遍物化表中的记录，这样就能做到子查询只物化一次。t1.i1) =t3.i1)
另外，下推到子查询的条件中，前面有个
<cache>，这也是一个优化，假设外层查询有连续 2 条或者多条记录的 i1 字段的值是55，那么对于第 1 条值为 55 的记录，会去物化表中遍历每条记录，判断是否匹配 t1.i1 = t3.i1 这个条件，如果物化表中有一条记录匹配这个条件，说明 exists 为 true，跳转到第 4 步继续执行，如果物化表中的记录全都不匹配这个条件，exists = false，跳转到第 1 步继续执行。对于第 2 条及以后的（注意是连续的）值为 55 的记录，不会再去遍历物化表了，而是直接根据第 1 条值为 55 的记录的结果作为外层查询当前记录的 exists 子查询的结果（相当于是缓存的作用了，也可以参考下 shell 的 uniq 命令的实现逻辑）。
第 4 步
判断外层查询的记录是否匹配外层查询中其它的 WHERE 条件，如果匹配，则把记录发送给客户端；如果不匹配，继续读取外层查询的下一条记录。
所以，整体 SQL 的执行过程，就是先执行第 1、2、3、4 步，读取外层查询第 1 条记录，然后循环读取外层查询的第 2 条及以后的记录，执行第 1、3、4 步（相比之下，少了第 2 步物化这个过程），直到外层查询符合条件的记录全部读取完成，结束 SQL 的执行。
2. uncacheable subquery
1select * from t1 where t1.i1 in (
2 select i1 from t3 where id in (3, 666, 990, 887, 76) and i2 > rand() * 100
3) and t1.str1 > 'abc';
1+----+----------------------+-------+------------+-------+---------------+---------+---------+--------+------+----------+-------------+
2| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
3+----+----------------------+-------+------------+-------+---------------+---------+---------+--------+------+----------+-------------+
4| 1 | PRIMARY | t1 | <null> | ALL | <null> | <null> | <null> | <null> | 8 | 33.33 | Using where |
5| 2 | UNCACHEABLE SUBQUERY | t3 | <null> | range | PRIMARY | PRIMARY | 4 | <null> | 5 | 33.33 | Using where |
6+----+----------------------+-------+------------+-------+---------------+---------+---------+--------+------+----------+-------------+
上面的 SQL 中子查询的执行方式为 UNCACHEABLE SUBQUERY（因为存在 i2 > rand() * 100 这个查询条件）。
uncacheable subquery 类型的子查询，执行过程和 subquery 类型的子查询是一样的（也是上面 subquery 小节中的第 1、2、3、4 步），不同的地方在于：
- 包含 uncacheable subquery 类型的子查询的整条 SQL 是不能使用 Query Cache 的（Query Cache 在 MySQL 8.0 之后已经被移除了）
- uncacheable subquery 类型的子查询，像
i2 > rand() * 100这样导致子查询uncacheable的条件不能使用索引条件下推，也会对 group by 子段有一些影响（这个先忽略吧）
目前发现的不同点，也就是上面这些吧，所以其实可以简单粗暴的认为 uncacheable subquery 和 subquery 基本上是一样的。
3. dependent subquery
其实上面列举的关于 uncacheable subquery 和 subquery 的两个 SQL，都是属于相关子查询，而本节要讲的 dependent subquery 也是相关子查询，只是执行方式不一样而已。
dependent subquery 类型的子查询，执行起来简单粗暴，有两种场景下会使用：
- 作为 in 子查询的兜底的执行逻辑，就是在子查询的 5 种优化策略都不能使用的情况下，in 子查询转换为 exists 子查询后，会使用 dependent subquery 方式执行
- SQL 中直接把子查询直接写成 exists 相关子查询（就是本小节要讲的这种情况）
本文前面两小节关于 uncacheable subquery 和 subquery 的两个 SQL，如果这样设置：
set optimizer_switch='semijoin=off'、set optimizer_switch='materialization=off'，这两条 SQL 的执行方式也会变成dependent subquery
1select * from t1 where exists (
2 select i1 from t3 where id in (3, 666, 990, 887, 76) and i2 > 16384 and t1.i1 = t3.i1
3) and t1.str1 > 's5';
1+----+--------------------+-------+------------+-------+---------------+---------+---------+--------+------+----------+-------------+
2| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
3+----+--------------------+-------+------------+-------+---------------+---------+---------+--------+------+----------+-------------+
4| 1 | PRIMARY | t1 | <null> | ALL | <null> | <null> | <null> | <null> | 8 | 33.33 | Using where |
5| 2 | DEPENDENT SUBQUERY | t3 | <null> | range | PRIMARY | PRIMARY | 4 | <null> | 5 | 3.33 | Using where |
6+----+--------------------+-------+------------+-------+---------------+---------+---------+--------+------+----------+-------------+
从 explain 的结果可以看到，上面的 SQL 中子查询的执行方式为 DEPENDENT SUBQUERY，接下来通过 optimizer_trace 看一下它的执行过程：
1{
2 "join_execution": {
3 "select#": 1,
4 "steps": [
5 { // 这是第 1 个
6 "subselect_execution": {
7 "select#": 2,
8 "steps": [
9 {
10 "join_execution": {
11 "select#": 2,
12 "steps": []
13 }
14 }
15 ]
16 }
17 },
18 // 中间省略了 8 个 subselect_execution 结构
19 { // 这是第 10 个
20 "subselect_execution": {
21 "select#": 2,
22 "steps": [
23 {
24 "join_execution": {
25 "select#": 2,
26 "steps": []
27 }
28 }
29 ]
30 }
31 }
32 ]
33 }
34}
上面的 JSON 中，最外层的 join_execution 表示执行了一次外层查询，subselect_execution 表示执行子查询（每执行一次子查询都对应一个 subselect_execution），subselect_execution 里面的 join_execution，表示是真正执行子查询的 SQL 去原表里查数据。下面我们来对比一下使用物化方式执行子查询的 join_execution：
1{
2 "join_execution": {
3 "select#": 1,
4 "steps": [
5 { // 这是第 1 个
6 "subselect_execution": {
7 "select#": 2,
8 "steps": [
9 {
10 "join_execution": {
11 "select#": 2,
12 "steps": []
13 }
14 }
15 ]
16 }
17 },
18 { // 这是第 2 个
19 "subselect_execution": {
20 "select#": 2,
21 "steps": []
22 }
23 },
24 // 中间省略了 7 个 subselect_execution 结构
25 { // 这是第 10 个
26 "subselect_execution": {
27 "select#": 2,
28 "steps": []
29 }
30 }
31 ]
32 }
33}
对比一下可以看到，使用物化方式执行的子查询，只有第一个 subselect_execution 里面有一个 join_execution，其它的 subselect_execution 里面都没有，这就是因为第 1 次执行子查询时，去原表里读取记录并物化，第 2 次及以后都直接从物化表里读取记录，并没有去原表里查询记录。
从上面的对比可知，dependent subquery 的执行效率是比较低的，因为每次都要去原表里读数据，外层查询有多少条符合条件的记录，子查询就要执行多少次，特别是单次执行子查询时间长，执行次数又多的时候，这是很要命的。这也就是为什么 dependent subquery 是作为 in 子查询的兜底逻辑了（不到万不得已是不会使用的）。
接下来还是总结一下 dependent subquery 的执行过程：
第 1 步
外层查询从存储引擎读取一条记录。
第 2 步
把子查询中使用的外层查询字段替换为具体的值，然后执行子查询，判断子查询中的记录对于 exists 条件是否为 true，不为 true，则外层查询的记录被跳过，回到第 1 步；如果为 true，跳到第 3 步继续执行。
第 3 步
判断外层查询中其它的 WHERE 条件是否匹配，不匹配则回到第 1 步；匹配则把记录发送给客户端。
重复执行第 1、2、3 步，直到读取完外层查询中符合条件的所有记录，结束 SQL 的执行。
4. 提升 SQL 性能小技巧
以前面小节 dependent subquery 的 SQL 为例：
1select * from t1 where exists (
2 select i1 from t3 where id in (3, 666, 990, 887, 76) and i2 > 16384 and t1.i1 = t3.i1
3) and t1.str1 > 's5';
WHERE 条件中有 2 个条件：exists (子查询)、t1.str1 > 's5'，我的 t1 表里有 10 条记录，子查询就会执行 10 次。
上面的 SQL，外层查询没有使用索引，所以执行过程是这样的：
读取外层查询的一条记录，执行子查询后如果 exists 为 false，就继续读取外层查询的下一条记录，不会判断外层查询的当前记录是否匹配 t1.str1 > 's5'；如果 exists 为 true，然后再判断外层查询当前记录是否匹配 t1.str1 > 's5'，不匹配则继续读取外层查询的下一条记录，匹配则把记录发送给客户端。
这样就存在一个问题了，判断 t1.str1 > 's5' 的成本肯定要比执行 exists 子查询的成本低，执行子查询后，exists 为 true 时，外层记录如果不满足 t1.str1 > 's5' 这个条件，子查询就白白的执行了，浪费了时间和性能。
如果像下面这样修改一下 SQL 语句：
1select * from t1 where t1.str1 > 's5' and exists (
2 select i1 from t3 where id in (3, 666, 990, 887, 76) and i2 > 16384 and t1.i1 = t3.i1
3);
t1 表里还是有 10 条记录，满足 t1.str1 > 's5' 的只有 4 条记录，经过 t1.str1 > 's5' 的筛选之后，只有 4 条外层查询的记录会触发子查询，这样性能就提升了 60% 了，还是很可观的。
基于此，总结一个小技巧：
在写一个包含 in、exists 子查询，并且 select_type = subquery、dependent subquery、uncacheable subquery、union、union all、dependent union 的 SQL 时，把其它简单 WHERE 条件放在前面（如：t1.str1 > 's5'），包含子查询的 WHERE 条件放在后面，可以减少子查询的执行次数，提升性能。
欢迎扫码关注公众号，我们一起学习更多 MySQL 知识：
