数据库内核月报

子查询定义

在一个完整的查询语句中包含的子查询块被称为子查询。通常情况下，我们可以将出现在SELECT、WHERE和HAVING语法中的子查询块称为嵌套子查询，出现在FROM语法后的子查询块称为内联视图或派生表。

本篇文章将会结合源码介绍在MySQL中针对子查询的几种优化策略。

子查询在执行计划中的表示

Semijoin/Antijoin

对于表示是否存在语义的查询语句，在语法上表示为IN/=ANY/EXISTS，优化器会尝试转换为semijoin/antijoin进行优化。与普通join会将左表和右表的记录连接在一起不同，semijoin/antijoin仅关心右表中是否存在可以与左表记录连接的记录，而返回左表记录。

在prepare阶段，优化器会首先检查当前查询是否可以转换为semijoin/antijoin的条件（由于antijoin是semijoin的相反，在代码层面也是一块处理的，所以之后的论述以semijoin为主），这部分代码在SELECT_LEX::resolve_subquery中，具体的条件总结如下：

子查询必须是谓词IN/=ANY/EXISTS的一部分，并且出现在WHERE或ON语法的最高层，可以被包含在AND表达式中。
必须是单个查询块，不带有UNION。
不包含HAVING语法。
不包含任何聚合函数。
不包含LIMIT语法。
外查询语句没有使用STRAIGHT_JOIN语法。

如果满足条件，将会把当前谓词加入到外查询的SELECT_LEX::sj_candidates中作为semijon的备选。

由于优化器对查询块的处理是一种递归的方式，在完成对子查询的判断之后，在外层查询的prepare阶段，会调用SELECT_LEX::flatten_subqueries函数完成子查询到semijoin的最终转换，这个过程在整个查询的生命周期只会发生一次，且不可逆。在SQL语法上等价为：

从一个带有备选semijoin子查询判断条件的查询块：
    SELECT ...
    FROM ot, ...
    WHERE oe IN (SELECT ie FROM it1 ... itN WHERE subq_where) AND outer_where
转换为：
    SELECT ...
    FROM ot SEMI JOIN (it1 ... itN), ...
    WHERE outer_where AND subq_where AND oe=ie

为了实现上述过程，需要进行以下步骤：

创建SEMI JOIN (it1 ... itN)语以部分，并加入到外层查询块的执行计划中。
将子查询的WHERE条件以及JOIN条件，加入到父查询的WHERE条件中。
将子查询谓词从父查询的判断谓词中消除。

具体的伪代码如下：

SELECT_LEX::flatten_subqueries()
     /* Semijoin flattening is bottom-up. Indeed, we have this execution flow,
        for SELECT#1 WHERE X IN (SELECT #2 WHERE Y IN (SELECT#3)) :

        SELECT_LEX::prepare() (select#1)
           -> fix_fields() on IN condition
               -> SELECT_LEX::prepare() on subquery (select#2)
                   -> fix_fields() on IN condition
                        -> SELECT_LEX::prepare() on subquery (select#3)
                        <- SELECT_LEX::prepare()
                   <- fix_fields()
                   -> flatten_subqueries: merge #3 in #2
                   <- flatten_subqueries
               <- SELECT_LEX::prepare()
           <- fix_fields()
           -> flatten_subqueries: merge #2 in #1

        Note that flattening of #(N) is done by its parent JOIN#(N-1), because
        there are cases where flattening is not possible and only the parent can
        know.*/
   |--子查询层层嵌套中采用bottom-up的方式去展开。在fix_fields()的过程中依次从里往外。仅支持IN和EXISTS的子查询，且内层的sj_candidates为空。
   |--由于在WHERE条件同一层可能存在多个可以展开的子查询判断，首先会计算优先级来决定semijoin展开顺序：
      1. 依赖外层查询的子查询优先于不相关子查询。
      2. 有着更多表的子查询优先于更少表的子查询。
      3. 顺序上先计算的子查询优先于后计算的。
   |--semijoin子查询不能和antijoin子查询相互嵌套。
   |--判断子查询的WHERE条件是否为常量。
      如果判断条件永远为FALSE，那么子查询结果永远为空。该情况下，可以将子查询直接清除，不用转换成semijoin。
   |--替换外层查询的WHERE条件中子查询判断的条件
      1. 子查询内条件并不永远为FALSE，或者永远为FALSE的情况下，需要改写为antijoin（antijoin情况下，子查询结果永远为空，外层查询条件永远通过）。
         此时将条件改为永远为True。
      2. 子查询永远为FALSE，且不是antijoin。那么将外层查询中的条件改成永远为False。
      /* 子查询判断条件可能为IN/=ANY/EXISTS，或者对应的否定。参数为Item_exists_subselect *。
         The following transformations are performed:

         1. IN/=ANY predicates on the form:

         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 ...]

         are transformed into:

         SELECT ...
         FROM (ot1 ... otN) SJ (it1 ... itK)
                           ON (oe1, ... oeM) = (ie1, ..., ieM)
                              [AND inner-cond]
         [WHERE outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         Notice that the inner-cond may contain correlated and non-correlated
         expressions. Further transformations will analyze and break up such
         expressions.

         2. EXISTS predicates on the form:

         SELECT ...
         FROM ot1 ... otN
         WHERE EXISTS (SELECT expressions
                       FROM it1 ... itK
                       [WHERE inner-cond])
          [AND outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         are transformed into:

         SELECT ...
         FROM (ot1 ... otN) SJ (it1 ... itK)
                            [ON inner-cond]
         [WHERE outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         3. Negated EXISTS predicates on the form:

         SELECT ...
         FROM ot1 ... otN
         WHERE NOT EXISTS (SELECT expressions
                       FROM it1 ... itK
                       [WHERE inner-cond])
          [AND outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         are transformed into:

         SELECT ...
         FROM (ot1 ... otN) AJ (it1 ... itK)
                            [ON inner-cond]
         [WHERE outer-cond AND is-null-cond(it1)]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         where AJ means "antijoin" and is like a LEFT JOIN; and is-null-cond is
         false if the row of it1 is "found" and "not_null_compl" (i.e. matches
         inner-cond).

         4. Negated IN predicates on the form:

         SELECT ...
         FROM ot1 ... otN
         WHERE (oe1, ... oeM) NOT IN (SELECT ie1, ..., ieM
                                  FROM it1 ... itK
                                  [WHERE inner-cond])
         [AND outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         are transformed into:

         SELECT ...
         FROM (ot1 ... otN) AJ (it1 ... itK)
                            ON (oe1, ... oeM) = (ie1, ..., ieM)
                            [AND inner-cond]
         [WHERE outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         5. The cases 1/2 (respectively 3/4) above also apply when the predicate is
         decorated with IS TRUE or IS NOT FALSE (respectively IS NOT TRUE or IS FALSE).*/
   |--SELECT_LEX::convert_subquery_to_semijoin() // 将当前查询块中包含的子查询判断转换成TABLE_LIST中的semijoin嵌套，antijoin也在里面完成。
     |--生成一个新的semijoin嵌套的TABLE_LIST表
     |--TABLE_LIST::merge_underlying_tables() // 将子查询中潜在的表合并到上述join表中
     |--将子查询的叶子表插入到当前查询块的叶子表后面，重新设置子查询的叶子表的序号和依赖的外表。将子查询的叶子表重置。
     |--如果是outer join的话，在join链表中传递可空性。
     |--SELECT_LEX::decorrelate_condition()
       |--将内层子查询中的关联条件去关联化，这些条件被加入到semijoin的列表里。这些条件必须是确定的，仅支持简单判断条件或者由简单判断条件组成的AND条件。
       |--decorrelate_equality()
         |--判断左右条件是否仅依赖于内外层表，将其表达式分别加入到semijoin内外表的表达式列表中。
     |--decorrelate_join_conds() // 解关联内层查询的join条件
     |--Item_cond_and::fix_after_pullout() // 将子查询的WHERE条件上拉，更新使用表的信息
     |--SELECT_LEX::build_sj_cond() // 根据semijoin的条件列表创建AND条件，如果有条件为常量True，则去除该条件；如果常量为False，则整个条件都去除。
     |--将创建出来的semijoin条件加入到外层查询的WHERE条件中

物化执行 or 迭代式循环执行

对于不能采用semijoin/antijoin执行的存在式语义的子查询，在MySQL源码的表示含义下，会做IN->EXISTS的转换，其实本质是在物化执行和迭代式循环执行中做选择。IN语法代表非相关子查询仅执行一次，将查询结果物化成临时表，之后需要结果时候就去物化表中查找；EXISTS代表对于外表的每一条记录，子查询都会执行一次，是迭代式循环执行。

MySQL会在prepare阶段尝试做IN->EXISTS的转换，然后在optimize阶段，比较IN or EXISTS执行的代价，最后根据代价决定采用哪种执行策略完成最终转换。

在prepare阶段IN->EXISTS的转换主要是将IN语法的左表达式与右表达式中子查询的输出列对应组合，加入到子查询的WHERE或者HAVING条件中，在SQL语义上表示为：

outer_expr IN (SELECT inner_expr FROM ... WHERE subquery_where)
转换为：
EXISTS (SELECT 1 FROM ... WHERE subquery_where AND outer_expr=inner_expr)

这一过程主要发生在Item_in_subselect::single_value_in_to_exists_transformer中，详细过程为：

/* 通过判断条件注入将IN语法转换为EXISTS语法
   向子查询中注入额外的判断条件，并将子查询标记为关联子查询。*/
|--Item_in_subselect::single_value_in_to_exists_transformer()
  |--如果子查询包含聚合函数、窗口函数、GROUP语法、HAVING语法，将判断条件加入到HAVING语法中。
  |--如果我们想区分NULL和False的结果的话，将这个条件封装到触发器中。
     SELECT ie FROM ... HAVING subq_having AND
               trigcond(oe $cmp$ ref_or_null_helper<ie>)
  |--创建指向子查询唯一列的Item_ref_null_helper对象，与之前注入的左表达式Item_ref共同创建比较表达式
  |--如果子查询的第一个列为包含聚合列的表达式，那么WHERE和HAVING语法中可能通过不同的Item_ref引用到这个Item，存入到Item_sum::ref_by数组中
  |--and_items() // 加入到HAVING条件中
|--如果不包含聚合函数、窗口函数、GROUP语法、HAVING语法，将判断条件加入WHERE语句中
  |--如果不需要区分NULL与False的结果：
     SELECT 1 FROM ... WHERE (oe $cmp$ ie) AND subq_where
  |--如果需要区分上述结果的差别，使用触发器
     SELECT 1 FROM ...
     WHERE subq_where AND trigcond((oe $cmp$ ie) OR (ie IS NULL))
           HAVING trigcond(@<is_not_null_test@>(ie))
  |--其他，单个查询块，没有表及上述语法，直接用条件表达式在外查询中替代

总结

以上就是MySQL中针对子查询所做的大部分优化和转换的工作，代码分析基于MySQL 8.0.19版本。

参考：https://dev.mysql.com/doc/refman/8.0/en/subquery-optimization.html

数据库内核月报－ 2020 / 10

MySQL · 源码分析 · 子查询优化源码分析

子查询定义

子查询在执行计划中的表示

Semijoin/Antijoin

物化执行 or 迭代式循环执行

总结