引文
在【MySQL·8.0·源码】subquery 子查询处理分析（一）中，已经介绍了 MySQL 子查询的语法树形式，并简单介绍了非相关 scalar 子查询的一些处理流程，本文将继续介绍更多子查询的处理流程。
本文后续以 “分析（一）” 来代替 “【MySQL·8.0·源码】subquery 子查询处理分析（一）”
假如对子查询不做任何优化处理，那么子查询应该怎么执行呢？
先来看一个 IN 子查询
Q1>: select * from t1 where a in (select pk from t2);
显然，先执行子查询，将 t2 的所有 pk 都查询出来，然后以所有的 pk 作为查询条件，检索 t1 中满足条件的记录返回即可。
再来看一个 Exists 子查询
Q2>: select * from t3 where exists (select * from t2 where t2.b=t3.a);
在 “分析（一）” 中已经知道其等同于
select * from t3 where WHERE 0 < (select count(*) from t2 where t2.b=t3.a)
所以只要检索遍历 t3 表记录，然后用 t3 一行行的 t3.a 值去充当 t2 的 select count(*) 条件，不为 0 则返回 t3 记录，否则跳过并继续下一行即可。
到此，IN 子查询和 Exists 子查询的大致执行过程已经清楚，那么就此执行会有什么问题？
- 假如 Q1 中，t2 表非常大，而 t1 表只有几行记录，也要遍历完 t2 表，代价很高
- 假如 Q2 中，t3 表非常大，而 t2 表满足条件的记录只有几行记录，也要遍历完所有的 t3 表，代价也很高
有没有发现，上述问题都是子查询按着严格的表的先后执行顺序引来的，那么如果子查询是否可以不按着严格的先后执行顺序来执行？
这就引申出了对子查询的各种优化策略。
去重策略
总统上，为了打破子查询的固有执行顺序，只有将子查询转换为 JOIN 操作，
但转换为 JOIN 操作后会引来什么问题? 例如：
Q3> select * from t1 where a in (select b from t2);
转换为 JOIN 之后
Q4> select * from t1 join t2 where t1.a = t2.b;
假如
t1 有 2 条记录，t1(a,b)：(1，1)，(2，2)
t2 有 4 条记录，t2(a,b)：(1，1)，(1，1)，(2，2)，(2，2)
则转换为 JOIN 之后结果为：
select * from t1 join t2 where t1.a = t2.b;
+------+------+------+------+
| a | b | a | b |
+------+------+------+------+
| 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 |
| 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 |
+------+------+------+------+
4 rows in set (0.00 sec)
而子查询结果为：
select * from t1 where a in (select b from t2);
+------+------+
| a | b |
+------+------+
| 1 | 1 |
| 2 | 2 |
+------+------+
可以看到，如果做 JOIN 操作，可能导致问题：
- Q4 查询结果的 schema 比子查询 Q3 多，Q3 只需要 t1 表对应的列；
- Q4 查询结果可能会比子查询 Q3 更多，原因在于子查询 t2 有重复的记录
Q5> select b from t2;
+------+
| b |
+------+
| 1 |
| 2 |
| 1 |
| 2 |
+------+
为了解决第 1 个问题，需要保证外表的 select list 中的 “*” 要在转成 JOIN 之前展开或者把 JOIN 换为 Semi-Join 即可，即表明只需要返回外表关系的 select list；
为了解决第 2 个问题，需要对结果进行去重 duplicate remove 即可，去重也可以选择对子查询去重，也可以选择对外表结果集去重：
- 对子查询去重即去除 Q5 中重复的记录，即只返回 1，2，而不是 1，2，1，2，即可得到正确结果；
- 对外表结果去重即去除 Q4 中重复的记录也能得到正确结果
MySQL 对子查询的优化策略总是围绕着这些点进行的
MySQL 优化策略
在 MySQL 中，对子查询的优化策略可以总结为：
- Transform to join derived table
- Transform to semi-join
- Pullout as simple JOIN
- FirstMatch
- LooseScan
- DuplicateWeedout
- Materialization
- MaterializeLookup
- MaterializeScan
- Exists
- Transform IN to Exists
- Exists/Not Exists
- Materialize
- MaterializeLookup
首先，对于特定的子查询，MySQL 支持将其子查询谓词转换为派生表来做 JOIN 操作
其次会尽可能尝试转换为 semi-join 来优化表的驱动顺序
MySQL 有一系列相关的开关进行控制（optimizer_switch）
subquery_to_derived=on;
semijoin=on;
loosescan=on
firstmatch=on
duplicateweedout=on
subquery_materialization_cost_based=on
Transform
在子查询诸多优化策略确定之前，在 prepare 阶段，需要将语法树进行 rewrite 改写，改写会改变整个
父子查询 query_expression 和 query_block 的关系，也可能将 where 和 on 条件进行整合重组，整个
带子查询的 Transform 大致处理流程为：
例如有查询语句：
SELECT #1 WHERE X IN (SELECT #2 WHERE Y IN (SELECT#3)) :
Query_block::prepare()（select#1）
-> Query_block::setup_conds() 在父查询块 IN 条件上执行 Item_exists_subselect::fix_fields()
-> Query_block::prepare() 处理子查询（select#2）
-> 在IN条件上执行 fix_fields()
-> Query_block::prepare() 处理子查询（select#3）
<- Query_block::prepare()
<- 在 fix_fields() 中结束
-> flatten_subqueries: 将 #3 合并到 #2 中
<- 在 flatten_subqueries 中结束
<- Query_block::prepare()
<- 在 fix_fields() 中结束
-> flatten_subqueries: 将 #2 合并到 #1 中
从父查询块在解析条件到子查询条件时，不断递归到子查询块的 prepare 工作，再不断深入子查询条件解析，
如果可能，进一步递归到子查询 in 条件的下一个子查询的解析中。
整个工作自顶而下，从父查询一直到最底层子查询
然后自下往上的进行子查询相关优化的判断，可能则进行自底而上的进行 merge 合并，达到去除子查询并简化查询块的目的
Transform to join derived table
转换形式为
FROM [tables] WHERE ... AND/OR oe IN (SELECT ie FROM it) ...
变为
FROM (tables) LEFT JOIN (SELECT DISTINCT ie FROM it) AS derived
ON oe = derived.ie WHERE ... AND/OR derived.ie IS NOT NULL ...
例如，对于上述的 Q3 转换为 join derived table 为：
select t1.* from t1 left join (select distinct b from t2) as derived
on t1.a = derived.b where derived.b is not null;
对于 derived table 的 Transform，子查询需要满足以下条件，才能称为候选者
Item_exists_subselect::is_derived_candidate(THD *thd)
- 开关已开启，optimizer_switch = ‘subquery_to_derived=on’
- 子查询是一个简单的查询（非集合运算，例如 union/intersect/except，非带有括号嵌套查询）
- 如果是 [Not] Exists 子查询，子查询必须不带 group 或者 windows 函数
- 子查询谓词是
- 在 Where 子句中，非 On 子句
- 子查询谓词必须直接链接在根条件谓词 AND 或 OR 之下
- 父查询块必须支持接受 semi-join（如果父查询是 update/delete 是不支持的）
- 父查询块必须存在基表，因为转换之后的 derived 是通过 left join 连接到父查询块基表后的
- 父查询块必须未禁止 semi-join 操作
- 如果是 IN 谓词，IN 谓词的左操作数必须是确定性的（例如，非 random 函数）
- not in/not = ，左右谓词可能为 NULLs 的都不允许做 semi-join
Transform
Query_block::transform_table_subquery_to_join_with_derived()
对于 derived table 转换，查询块会创建一个派生表添加到外部查询块上，派生表的名称一般为 “derived_%d_%d”，
后面两个数字为查询块的 id，例如把 select #3 子查询创建一个派生表添加到 select #2 查询块上，名称为 “derived_2_3”。
同时，子查询 IN 表达式会被替换为关联条件，例如 select #2 上的 Item_in_subselect 替换为 Item_func_eq（t2.a，derived_2_3.Name_exp_1）。
Transform to semi-join
还是以 Q3 为例，转换为 semi-join 为：
select t1.* from t1 semi join t2 where t1.a = t2.b;
对于 semi join 的 Transform，子查询需要满足以下条件，才能称为候选者
Item_exists_subselect::is_semijoin_candidate()
- 启用了 semi join，optimizer_switch = ‘semijoin=on’
- 子查询是简单的查询块（非集合运算，例如 union/intersect/except，非带有括号嵌套查询）
- 子查询没有 group 聚集（显式的或隐式的）
- 子查询没有 having
- 子查询没有 window 窗口函数
- 子查询谓词在 ON/WHERE 子句中，并且在根 AND 谓词下
- 父查询块接受 semi-join（如果父查询是 update/delete 是不支持的）
- 子查询不是不存在基表的查询，例如：select 1
- 父子查询均无 straight join
- 父查询块未禁止 semi-join
- IN 谓词左侧是确定性的
- not in/not = ，左右谓词可能为 NULLs 的都不允许做 semi-join
- 引擎要么支持 anti-join，要么不是 anti-join
- 如果存在 OFFSET，则需从第一行开始，LIMIT 不为 0
Transform
Query_block::convert_subquery_to_semijoin()
对于 semi join 转换，查询块会不断通过调用 convert_subquery_to_semijoin() 尝试将查询块的子查询谓词（比如说 IN 谓词）转换为
Table_ref 的半连接嵌套查询，
转换形式为：
- IN
SELECT ...
FROM ot1 ... otN
WHERE (oe1, ... oeM) IN (SELECT ie1, ..., ieM
FROM it1 ... itK
[WHERE inner-cond])
[AND outer-cond]
[GROUP BY ...] [HAVING ...] [ORDER BY ...]
会被转换为
SELECT ...
FROM (ot1 ... otN) SJ (it1 ... itK)
ON (oe1, ... oeM) = (ie1, ..., ieM)
[AND inner-cond]
[WHERE outer-cond]
[GROUP BY ...] [HAVING ...] [ORDER BY ...]
- EXISTS
SELECT ...
FROM ot1 ... otN
WHERE EXISTS (SELECT expressions
FROM it1 ... itK
[WHERE inner-cond])
[AND outer-cond]
[GROUP BY ...] [HAVING ...] [ORDER BY ...]
会被转换为
SELECT ...
FROM (ot1 ... otN) SJ (it1 ... itK)
[ON inner-cond]
[WHERE outer-cond]
[GROUP BY ...] [HAVING ...] [ORDER BY ...]
- 同理 NOT IN、NOT EXISTS 会被转换为 Anti Join
用图示来展示之前 Q3 的转换如下
Transform to exists
最终，当子查询无法称为 derived table 或 semi join 的候选者时，只能对子查询做 IN->Exists 转换查询
遍历查询块的子查询谓词，调用子查询谓词对应的 transform() 函数进行转换
Item_exists_subselect::transformer()
Item_in_subselect::transformer()
Item_allany_subselect::transformer()
Item_in_subselect::transformer()
Item_allany_subselect::transformer()
在 Item_in_subselect::transformer() 中，会做一些规则性的转换，例如：
-
非表的 IN、NOT IN 子查询并且不带 group by、where、和 having 子句
例如：select * from t1 where a in (select 3)IN 子查询会被转换为
where t1.a = 3 -
单列子查询，子查询左侧操作数为单列
单列子查询会调用 Item_in_subselect::single_value_transformer，以尝试是否可能将子查询转换为 scalar 查询，形如：oe $cmp$ (SELECT ie FROM ... WHERE subq_where ... HAVING subq_having)可以尝试转换为：
- oe $cmp$ (SELECT MAX(...) ) // 由 Item_singlerow_subselect 处理 - oe $cmp$ \<max\>(SELECT ...) // 由 Item_maxmin_subselect 处理如果不能转换，则使用 Item_in_optimzer 类处理子查询
-
多列子查询，子查询左侧操作数为多列
多列子查询会调用 Item_in_subselect::row_value_transformer()，根据规则对多列 IN/ALL/ANY 子查询做一定的重写，形如：(oe1, oe2, ...) $cmp$ (SELECT ie1, ie2, ... FROM ... WHERE subq_where ... HAVING subq_having)转换为类似形如：
(l1, l2, l3) IN (SELECT v1, v2, v3 ... WHERE where) => EXISTS (SELECT ... WHERE where and (l1 = v1 or is null v1) and (l2 = v2 or is null v2) and (l3 = v3 or is null v3) HAVING is_not_null_test(v1) and is_not_null_test(v2) and is_not_null_test(v3))在 where 条件中，为每个左操作创建等值连接条件
对于子查询做完一定的 Transform 之后，就会赋予子查询临时性的执行策 Subquery_strategy::CANDIDATE_FOR_IN2EXISTS_OR_MAT，
即在 IN2EXISTS 转换或 Materialization 两种策略之中二选一，
然后在 optimize 阶段的 JOIN::make_join_plan()->JOIN::decide_subquery_strategy() 中最终决定走 Materialization 或者 EXISTS 执行策略。
![【web | CTF】BUUCTF [HCTF 2018]WarmUp](https://img-blog.csdnimg.cn/direct/254c6310bbd3449f9b7765a390cf7bde.png)
