这篇文章将重点介绍条件/投影中的子查询在MySQL中的处理，例如
SELECT t1.c2, （select sum(t2.c1) from t2) <= subq1
FROM t1
WHERE t1.c1 in (select c2 from t1); <= subq2其投影列中，和where条件中，各有一个子查询，这些在MySQL中都使用Item来描述，具体来说是Item_subselect
背景
首先对于子查询这个SQL construct，有相关和非相关两个类别，SQL planner在完成语法解析和语义检查后，就可以确定一个子查询是否是相关的（和外层的某些表列有相关条件），当然在后续的优化过程中，还可能再相关/非相关之间转换，先来看下MySQL中对于subquery的描述结构。
所有子查询都是Item_subselect这个表达式类的子类，其继承关系如下：
Item_subselect
-> Item_singlerow_subselect
标量子查询，即最多只会产生一行结果的子查询，在投影列中的必然是这种
-> Item_maxmin_subselect
对于ANY/ALL子查询，在某些情况下可以转换为oe $cmp$ \(SELECT ...)的形式，这时用这个类来描述
这个类是内部变换后产生
-> Item_exists_subselect EXIST子查询
-> Item_in_subselect IN子查询
-> Item_allany_subselect ALL/ANY/SOME子查询，经常与 < / > 这样的运算符配合使用以上就是MySQL中支持的所有子查询类型，每种类型都可能是相关/非相关的，类内部会有标记来描述。
而各种不同类型的子查询，在MySQL中都有哪些可能的执行方式呢，只要看Subquery_strategy这个enum就可以了：
enum class Subquery_strategy : int {
/// Nothing decided yet
UNSPECIFIED,
...
/// 转换为semi-join
SEMIJOIN,
/// 子查询一定是空集，直接替换为恒false
ALWAYS_FALSE,
/// 转换为derived table
DERIVED_TABLE,
/// EXIST方式执行（外表每行，触发内层子查询执行一次）
SUBQ_EXISTS,
/// 子查询物化（非相关）
SUBQ_MATERIALIZATION,
};略过其中一些中间状态的strategy（后面会讲到），最终执行方式无非5种。
Subquery处理流程
MySQL对于一条查询语句的处理基本分为3个阶段，分别是prepare -> optimize -> execute，我们从3个阶段分别看下对于subquery的处理，相对于derived table，子查询的处理要复杂很多，后面会涉及到大量函数，但有些函数的内部细节可以跳过，只关注最为重要的整体流程即可。
Prepare阶段
这个查询的处理在经过parse，基本就构成了最初级的抽象语法树(AST)，即这种SELECT_LEX_UNIT作为root的嵌套结构，prepare阶段主要完成2件事情
负责对AST对resolve，包括所有涉及的tables/columns，以及每一个查询中的表达式(Item)
基于启发式规则，完成一些query transformation，包括将子查询转换为semi-join，outer join简化为inner join，derived table展开到上层，消除常量表达式等等。。。
这一阶段的transformation是完全基于规则的，不考虑代价因素。这里专注于对subquery的处理流程：
SELECT_LEX::prepare
...
-> remove_redundant_subquery_clauses
如果当前SELECT_LEX是子查询，看是否可以去掉其中的一些clause:
1. single row的标量子查询，可以去掉order by
2. IN/EXIST子查询，可以去掉order by / distinct
如果有group by但没有aggr + having + rollup + windows，可以去掉group by
-> SELECT_LEX::resolve_subquery, 如果当前是子查询
-> 对于IN/EXIST subselect，判断subquery是否可以转换为semi-join/anti-join，设置strategy为 CANDIDATE_FOR_SEMIJOIN
FROM ot WHERE ot.x IN (SELECT y FROM it1)
=>
FROM ot semi-join it on ot.x = it.y
这里会有很严苛的大量判断条件，极简的概括就是，只有SPJ的subquery，可以转换为semi/anti join
-> 对于IN/EXIST subselect，如果无法转semi-join，尝试转为derived_table，设置strategy为 CANDIDATE_FOR_DERIVED_TABLE
FROM ot WHERE ot.x IN (SELECT y FROM it1, it2)
=>
FROM ot LEFT JOIN (SELECT DISTINCT y FROM it1, it2) AS derived ON ot.x = derived.y
WHERE derived.y IS NOT NULL
同样大量条件判断，但与上面不同的是，如果当前是IN子查询，是允许其中包含group by + aggregation的
-> 如果以上都不成立，调用select_transformer，做可能的变换（除一些特殊情况，都转换为EXISTS）
-> Item_singlerow_subselect::select_transformer
满足如下特定条件：
子查询没有union + 没有table + 只有一个投影列 + 没有where + 没有having
整个subquery可以被消除，直接用唯一的投影列替换掉子查询
-> Item_in_subselect::select_transformer
-> select_in_like_transformer 适用于IN/ALL/ANY/SOME子查询
-> 创建Item_in_optimizer，这是一个辅助子查询执行的封装类，内部会处理左右NULL值时的计算
具体细节请看Item_in_optimizer class注释
-> 设置strategy为 CANDIDATE_FOR_IN2EXISTS_OR_MAT，表示尚不确定其执行方式是EXISTS还是物化
-> 如果left_expr只有1列，调用single_value_transformer
-> 在特定情况下，可以将ANY/ALL转换为MIN/MAX子查询
是 >/>=/ 无法转换，做如下一系列操作，来为转换为EXIST做准备
1. 创建m_injected_left_expr，是一个Item_ref，指向IN子查询的左表达式（外层相关表达式）
2. 创建In2exists_info结构，这个对象用来辅助做IN -> EXIST的转换
3. 生成pushed_cond_guards数组，辅助对相关条件的两侧出现的NULL值的处理
-> single_value_in_to_exists_transformer
这个函数主要是把外层相关条件注入到子查询中，但根据子查询中是否有聚集，注入方式稍有不同
1. 如果子查询中有group by/having/sum/window:
-> 创建必要的Item_ref_null_helper/Item_func_trig_cond，放在having_cond里，在EXISTS的执行中使用，辅助left/right null值的处理
2. 没有聚集
-> 创建 Item_is_not_null_test/Item_func_trig_cond，放到where_cond/having_cond中
具体变换详见函数注释和实现，这里不再深入
-> 如果left_expr有多列，就变成一个row而不是一个标量，调用row_value_transformer
内部处理逻辑其实和single value的基本一致，只是变成了对多个value的处理
-> Item_exist_subselect没有实现select_transformer，不做任何处理
-> flatten_subqueries，对于之前收集的可以转换为semi-join/anti-join/derived_table的subquery，尝试转换
遍历每个收集的subquery_item
-> CANDIDATE_FOR_DERIVED_TABLE，调用 transform_table_subquery_to_join_with_derived，转换为derived_table
-> strategy从 CANDIDATE_FOR_DERIVED_TABLE 变为 DERIVED_TABLE
-> transform_subquery_to_derived
...
-> CANDIDATE_FOR_SEMIJOIN
-> strategy从 CANDIDATE_FOR_SEMIJOIN 变为 SEMIJOIN
-> convert_subquery_to_semijoin
...
-> 对于sj_candidates中无法做前两种的，只能转为EXISTS
-> 调用select_transformer，和前面逻辑相同这里略过了transform_subquery_to_derived和convert_subquery_to_semijoin这两个函数的实现细节，内部还是比较复杂的，篇幅原因这里就不介绍了。
到这里针对子查询的主要变换逻辑就结束了，涉及的代码还是比较复杂的，有很多来回merge，替换item，添加item等操作，但其实主体的处理思路是比较清晰的：
对子查询内部化简
判断是否可能转换为semi-join，收集
判断是否可能转换为derived table，收集
都不行的，为转换为EXISTS做好准备
对上面收集的subquery做相应变换
完成这些变换后，所有subquery中，只剩下标记为CANDIDATE_FOR_IN2EXISTS_OR_MAT的subquery item，其执行方式在优化期确定。
Optimize阶段
优化期间会基于CBO估算的代价，决定CANDIDATE_FOR_IN2EXISTS_OR_MAT的子查询，最终是物化执行还是EXISTS方式执行。优化的逻辑很多，这里只介绍针对subquery的部分。
JOIN::optimize
...
-> JOIN::make_join_plan
最主要的CBO优化函数，包括确定semi-join执行策略，join ordering，子查询执行方式...
-> 当前是子查询，调用JOIN::decide_subquery_strategy
对于 CANDIDATE_FOR_IN2EXISTS_OR_MAT 的子查询， 基于代价决定其执行方式：exists或者materialize
-> compare_costs_of_subquery_strategies
-> Item_in_subselect::subquery_allows_materialization，硬性限制，无法做物化
-> calculate_materialization_costs 物化的代价
-> calculate_subquery_executions exists子查询的执行次数
对比cost_mat和cost_exists
如果是exist执行，finalize_exists_transform
-> 只是非空判断，加上limit 1
如果是materialize执行，finalize_materialization_transform
-> remove_in2exists_conds 去掉在resolve阶段，为exist转换注入的额外cond
-> 创建 subselect_hash_sj_engine （物化执行一定使用这个engine）
-> subselect_hash_sj_engine::setup 用unit的投影列做初始化
在leader上，对应item由于是后优化(在pq_finalize_shared_strategy之前)，因此没有PQ_PUSHDOWN_SHARED标记，只有worker有!
-> 正常创建Query_result_union，调用 create_result_table 创建物化的临时表，保存在Query_result_union::table上
-> 在table上建索引，要构建对应QEP_TAB/TABLE/TABLE_REF对象，便于后续读取
-> pq_finalize_shared_strategy ,判断这个物化子查询是否可以shared方式下推到worker:
外层是并行的且子查询本身是非相关的，且已经决定要下推了，这里处理了IN_SUBS/ANY_SUBS/ALL_SUBS!!
对于SINGLEROW_SUBS，add_subselects_to_template 里设置了PQ_PUSHDOWN_SHARED
...
-> JOIN::replace_index_subquery ，针对一种特殊情况，把Item_in_subselect的SUBQ_EXISTS策略，改为用 subselect_indexsubquery_engine 这个执行方式，这样本层subquery直接优化完成
...Execute阶段
执行期间的逻辑就比较简单了，针对之前分析的几种执行方式，总结如下：
semi-join/anti-join/derived table，由于都转换为join，原始的item对象已经没用
物化执行，EXISTS执行，都会由所在的条件/投影列的计算作为入口，调用Item_subselect::exec方法来执行
Item_subselect::exec
-> 对于前面提到的单表index lookup方式，调用subselect_indexsubquery_engine::exec
-> ExecuteExistsQuery
这是一个通用方法，用来执行一个返回boolen标量的子查询，传入的是在子查询优化时生成的root iterator
对于单表lookup，这个iterator就是内层表的ref iterator
返回结果保持在所属item的value字段中，供外层读取
-> 对于物化执行，调用subselect_hash_sj_engine::exec
-> ExecuteExistsQuery
也是类似的流程，但这里root iterator是表示物化操作的MaterializeIterator
-> MaterializeIterator::Init 完成物化操作
-> instantiate_tmp_table 创建引擎层的实际table对象，对应Query_result_union::table
-> 遍历m_query_blocks_to_materialize这个数组，针对其中每个query block，调用MaterializeQueryBlock
-> 每个query block对象也包含一个subquery_iterator，是对应子查询优化后的root iterator，触发执行流程，结果写入到物化table中
-> MaterializeIterator::Read 读取物化结果表，触发后续执行流程
-> 对于EXISTS执行，调用SubqueryWithResult::exec
-> SELECT_LEX_UNIT::exec 完成执行，返回标量的boolean结果传递到外层
总结
到这里对于subquery的大体处理流程已经讲完了，可以发现相对于derived table，subquery的处理流程复杂度要更高些，尤其集中在prepare阶段做的transformation，这里介绍的粒度仍然是比较粗的，可以作为outline，供感兴趣的同学可以进一步研究源码时参考。
