MySQL · 源码分析 · Subquery代码分析

在上一篇介绍derived table的文章中，开头已经介绍了MySQL中子查询的基本概念，具体详见：

https://ata.alibaba-inc.com/articles/221930?spm=ata.25287382.0.0.78a241676LAHnE

这篇文章将重点介绍条件/投影中的子查询在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$ \<max\>(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件事情

1. 负责对AST对resolve，包括所有涉及的tables/columns，以及每一个查询中的表达式(Item)
2. 基于启发式规则，完成一些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子查询
             是 >/>=/</<= 的运算符 + 非相关子查询 + 所在条件会将UNKNOWN视为FALSE的情况下可以转换
             没有group by + aggregation + 没有having + 没有windows
             1. 满足这些条件时，会构造一个新的Item_singlerow_subselect，但投影列是MIN/MAX的计算
             2. 不满足条件，构造一个Item_maxmin_subselect对象，替换原有IN子查询表达式   
          -> 无法转换，做如下一系列操作，来为转换为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等操作，但其实主体的处理思路是比较清晰的：

1. 对子查询内部化简
2. 判断是否可能转换为semi-join，收集
3. 判断是否可能转换为derived table，收集
4. 都不行的，为转换为EXISTS做好准备
5. 对上面收集的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阶段

执行期间的逻辑就比较简单了，针对之前分析的几种执行方式，总结如下：

1. semi-join/anti-join/derived table，由于都转换为join，原始的item对象已经没用
2. 物化执行，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，供感兴趣的同学可以进一步研究源码时参考。