子查询定义

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

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

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

MySQL · 源码分析 · 子查询优化源码分析 - 图1

Semijoin/Antijoin

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

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

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

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

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

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

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

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

具体的伪代码如下：

  1. SELECT_LEX::flatten_subqueries()
  2.      /* Semijoin flattening is bottom-up. Indeed, we have this execution flow,
  3.         for SELECT#1 WHERE X IN (SELECT #2 WHERE Y IN (SELECT#3)) :
  5.         SELECT_LEX::prepare() (select#1)
  6.            -> fix_fields() on IN condition
  7.                -> SELECT_LEX::prepare() on subquery (select#2)
  8.                    -> fix_fields() on IN condition
  9.                         -> SELECT_LEX::prepare() on subquery (select#3)
  10.                         <- SELECT_LEX::prepare()
  11.                    <- fix_fields()
  12.                    -> flatten_subqueries: merge #3 in #2
  13.                    <- flatten_subqueries
  14.                <- SELECT_LEX::prepare()
  15.            <- fix_fields()
  16.            -> flatten_subqueries: merge #2 in #1
  18.         Note that flattening of #(N) is done by its parent JOIN#(N-1), because
  19.         there are cases where flattening is not possible and only the parent can
  20.         know.*/
  21.    |--子查询层层嵌套中采用bottom-up的方式去展开。在fix_fields()的过程中依次从里往外。仅支持IN和EXISTS的子查询，且内层的sj_candidates为空。
  22.    |--由于在WHERE条件同一层可能存在多个可以展开的子查询判断，首先会计算优先级来决定semijoin展开顺序：
  23.       1. 依赖外层查询的子查询优先于不相关子查询。
  24.       2. 有着更多表的子查询优先于更少表的子查询。
  25.       3. 顺序上先计算的子查询优先于后计算的。
  26.    |--semijoin子查询不能和antijoin子查询相互嵌套。
  27.    |--判断子查询的WHERE条件是否为常量。
  28.       如果判断条件永远为FALSE，那么子查询结果永远为空。该情况下，可以将子查询直接清除，不用转换成semijoin。
  29.    |--替换外层查询的WHERE条件中子查询判断的条件
  30.       1. 子查询内条件并不永远为FALSE，或者永远为FALSE的情况下，需要改写为antijoin（antijoin情况下，子查询结果永远为空，外层查询条件永远通过）。
  31.          此时将条件改为永远为True。
  32.       2. 子查询永远为FALSE，且不是antijoin。那么将外层查询中的条件改成永远为False。
  33.       /* 子查询判断条件可能为IN/=ANY/EXISTS，或者对应的否定。参数为Item_exists_subselect *。
  34.          The following transformations are performed:
  36.          1. IN/=ANY predicates on the form:
  38.          SELECT ...
  39.          FROM ot1 ... otN
  40.          WHERE (oe1, ... oeM) IN (SELECT ie1, ..., ieM
  41.                                   FROM it1 ... itK
  42.                                  [WHERE inner-cond])
  43.           [AND outer-cond]
  44.          [GROUP BY ...] [HAVING ...] [ORDER BY ...]
  46.          are transformed into:
  48.          SELECT ...
  49.          FROM (ot1 ... otN) SJ (it1 ... itK)
  50.                            ON (oe1, ... oeM) = (ie1, ..., ieM)
  51.                               [AND inner-cond]
  52.          [WHERE outer-cond]
  53.          [GROUP BY ...] [HAVING ...] [ORDER BY ...]
  55.          Notice that the inner-cond may contain correlated and non-correlated
  56.          expressions. Further transformations will analyze and break up such
  57.          expressions.
  59.          2. EXISTS predicates on the form:
  61.          SELECT ...
  62.          FROM ot1 ... otN
  63.          WHERE EXISTS (SELECT expressions
  64.                        FROM it1 ... itK
  65.                        [WHERE inner-cond])
  66.           [AND outer-cond]
  67.          [GROUP BY ...] [HAVING ...] [ORDER BY ...]
  69.          are transformed into:
  71.          SELECT ...
  72.          FROM (ot1 ... otN) SJ (it1 ... itK)
  73.                             [ON inner-cond]
  74.          [WHERE outer-cond]
  75.          [GROUP BY ...] [HAVING ...] [ORDER BY ...]
  77.          3. Negated EXISTS predicates on the form:
  79.          SELECT ...
  80.          FROM ot1 ... otN
  81.          WHERE NOT EXISTS (SELECT expressions
  82.                        FROM it1 ... itK
  83.                        [WHERE inner-cond])
  84.           [AND outer-cond]
  85.          [GROUP BY ...] [HAVING ...] [ORDER BY ...]
  87.          are transformed into:
  89.          SELECT ...
  90.          FROM (ot1 ... otN) AJ (it1 ... itK)
  91.                             [ON inner-cond]
  92.          [WHERE outer-cond AND is-null-cond(it1)]
  93.          [GROUP BY ...] [HAVING ...] [ORDER BY ...]
  95.          where AJ means "antijoin" and is like a LEFT JOIN; and is-null-cond is
  96.          false if the row of it1 is "found" and "not_null_compl" (i.e. matches
  97.          inner-cond).
  99.          4. Negated IN predicates on the form:
  101.          SELECT ...
  102.          FROM ot1 ... otN
  103.          WHERE (oe1, ... oeM) NOT IN (SELECT ie1, ..., ieM
  104.                                   FROM it1 ... itK
  105.                                   [WHERE inner-cond])
  106.          [AND outer-cond]
  107.          [GROUP BY ...] [HAVING ...] [ORDER BY ...]
  109.          are transformed into:
  111.          SELECT ...
  112.          FROM (ot1 ... otN) AJ (it1 ... itK)
  113.                             ON (oe1, ... oeM) = (ie1, ..., ieM)
  114.                             [AND inner-cond]
  115.          [WHERE outer-cond]
  116.          [GROUP BY ...] [HAVING ...] [ORDER BY ...]
  118.          5. The cases 1/2 (respectively 3/4) above also apply when the predicate is
  119.          decorated with IS TRUE or IS NOT FALSE (respectively IS NOT TRUE or IS FALSE).*/
  120.    |--SELECT_LEX::convert_subquery_to_semijoin() // 将当前查询块中包含的子查询判断转换成TABLE_LIST中的semijoin嵌套，antijoin也在里面完成。
  121.      |--生成一个新的semijoin嵌套的TABLE_LIST表
  122.      |--TABLE_LIST::merge_underlying_tables() // 将子查询中潜在的表合并到上述join表中
  123.      |--将子查询的叶子表插入到当前查询块的叶子表后面，重新设置子查询的叶子表的序号和依赖的外表。将子查询的叶子表重置。
  124.      |--如果是outer join的话，在join链表中传递可空性。
  125.      |--SELECT_LEX::decorrelate_condition()
  126.        |--将内层子查询中的关联条件去关联化，这些条件被加入到semijoin的列表里。这些条件必须是确定的，仅支持简单判断条件或者由简单判断条件组成的AND条件。
  127.        |--decorrelate_equality()
  128.          |--判断左右条件是否仅依赖于内外层表，将其表达式分别加入到semijoin内外表的表达式列表中。
  129.      |--decorrelate_join_conds() // 解关联内层查询的join条件
  130.      |--Item_cond_and::fix_after_pullout() // 将子查询的WHERE条件上拉，更新使用表的信息
  131.      |--SELECT_LEX::build_sj_cond() // 根据semijoin的条件列表创建AND条件，如果有条件为常量True，则去除该条件；如果常量为False，则整个条件都去除。
  132.      |--将创建出来的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语义上表示为：

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

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

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

总结

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

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