庖丁解牛-图解MySQL 8.0优化器查询转换篇

傷城~ 2022-09-12 00:55 137阅读 0赞

**简介：** 在《庖丁解牛-图解MySQL 8.0优化器查询解析篇》一文中我们重点介绍了MySQL最新版本8.0.25关于SQL基本元素表、列、函数、聚合、分组、排序等元素的解析、设置和转换过程，本篇我们继续来介绍更为复杂的子查询、分区表和JOIN的复杂转换过程。

![image.png][]

作者 | 道客  
来源 | 阿里技术公众号

### 一 背景和架构 ###

在《庖丁解牛-图解MySQL 8.0优化器查询解析篇》一文中我们重点介绍了MySQL最新版本8.0.25关于SQL基本元素表、列、函数、聚合、分组、排序等元素的解析、设置和转换过程，本篇我们继续来介绍更为复杂的子查询、分区表和JOIN的复杂转换过程，大纲如下：

**Transformation**

*  remove\_redundant\_subquery\_clause :

Permanently remove redundant parts from the query if 1) This is a subquery 2) Not normalizing a view. Removal should take place when a query involving a view is optimized, not when the view is created.

*  remove\_base\_options:

Remove SELECT\_DISTINCT options from a query block if can skip distinct

*  resolve\_subquery :Resolve predicate involving subquery, perform early unconditional subquery transformations
    
     *  Convert subquery predicate into semi-join, or
     *  Mark the subquery for execution using materialization, or
     *  Perform IN->EXISTS transformation, or
     *  Perform more/less ALL/ANY -> MIN/MAX rewrite
     *  Substitute trivial scalar-context subquery with its value
 *  transform\_scalar\_subqueries\_to\_join\_with\_derived:

Transform eligible scalar subqueries to derived tables.

*  flatten\_subqueries :

Convert semi-join subquery predicates into semi-join join nests. Convert candidate subquery predicates into semi-join join nests. This transformation is performed once in query lifetime and is irreversible.

*  apply\_local\_transforms :
    
     *  delete\_unused\_merged\_columns : If query block contains one or more merged derived tables/views, walk through lists of columns in select lists and remove unused columns.
     *  simplify\_joins : Convert all outer joins to inner joins if possible.
     *  prune\_partitions ：Perform partition pruning for a given table and condition.
 *  push\_conditions\_to\_derived\_tables :

Pushing conditions down to derived tables must be done after validity checks of grouped queries done by apply\_local\_transforms();

*  Window::eliminate\_unused\_objects:

Eliminate unused window definitions, redundant sorts etc.

### 二 详细转换过程 ###

1 解析子查询（resolve\_subquery）

解析条件中带有子查询的语句，做一些早期的无限制的子查询转换，包括：

*  标记subquery是否变成semi-join
    
     *  转换判断条件
     *  检查OPTIMIZER\_SWITCH\_SEMIJOIN和HINT没有限制
     *  子查询是IN/=ANY和EXIST subquery的谓词
     *  子查询是简单查询块而不是UNION
     *  子查询无隐形和显性的GROUP BY
     *  子查询没有HAVING、WINDOW函数
     *  Resolve的阶段是Query\_block::RESOLVE\_CONDITION和Query\_block::RESOLVE\_JOIN\_NEST并且没有用到最新的Hyper optimizer优化器。
     *  外查询块可以支持semijoins
     *  至少要一个表，而不是类似"SELECT 1"
     *  子查询的策略还没有指定Subquery\_strategy::UNSPECIFIED
     *  父查询也至少有一个表
     *  父查询和子查询都不能有straight join
     *  父查询块不禁止semijoin
     *  IN谓词返回值是否是确定的，不是RAND
     *  根据子查询判断结果是否需要转成true还是false以及是否为NULL，判断是可以做antijoin还是semijoin
     *  Antijoin是可以支持的，或者是semijoin
     *  offset和limit对于semjoin是有效的，offset是从第一行开始，limit也不是0
     *  设置Subquery\_strategy::CANDIDATE\_FOR\_SEMIJOIN并添加sj\_candidates
 *  标记subquery是否执行时采用materialization方案
    
     *  如果不符合转换semijoin，尝试使用物化方式，转换判断条件
     *  Optimzier开关subquery\_to\_derived=on
     *  子查询是IN/=ANY or EXISTS谓词
     *  子查询是简单查询块而不是UNION
     *  如果是\[NOT\] EXISTS，必须没有聚合
     *  Subquery谓词在WHERE子句（目前没有在ON子句实现），而且是ANDs or ORs的表达式tree
     *  父查询块支持semijoins
     *  子查询的策略还没有指定Subquery\_strategy::UNSPECIFIED
     *  父查询也至少有一个表，然后可以做LEFT JOIN
     *  父查询块不禁止semijoin
     *  IN谓词返回值是否是确定的，不是RAND
     *  根据子查询判断结果是否需要转成true还是false以及是否为NULL，判断是可以做antijoin还是semijoin
     *  不支持左边参数不是multi-column子查询（WHERE (outer\_subq) = ROW(derived.col1,derived.col2)）
     *  该子查询不支持转换为Derived table（m\_subquery\_to\_derived\_is\_impossible）
     *  设置Subquery\_strategy::CANDIDATE\_FOR\_DERIVED\_TABLE并添加sj\_candidates
 *  如果上面两个策略无法使用，根据类型选择transformer
    
     *  Item\_singlerow\_subselect::select\_transformer
     *  对于简单的标量子查询，在查询中直接用执行结果代替

select * from t1 where a = (select 1); 
    =>
    select * from t1 where a = 1;

![image.png][image.png 1]

*  Item\_in\_subselect/Item\_allany\_subselect::select\_transformer->select\_in\_like\_transformer
 *  select\_in\_like\_transformer函数来处理 IN/ALL/ANY/SOME子查询转换transformation
 *  处理"SELECT 1"（Item\_in\_optimizer）
 *  如果目前还没有子查询的执行方式，也就是无法使用semijoin/antijoin执行的子查询，会做IN->EXISTS的转换，本质是在物化执行和迭代式循环执行中做选择。IN语法代表非相关子查询仅执行一次，将查询结果物化成临时表，之后需要结果时候就去物化表中查找；EXISTS代表对于外表的每一条记录，子查询都会执行一次，是迭代式循环执行。子查询策略设定为Subquery\_strategy::CANDIDATE\_FOR\_IN2EXISTS\_OR\_MAT
 *  重写single-column的IN/ALL/ANY子查询（single\_value\_transformer）

oe $cmp$ (SELECT ie FROM ... WHERE subq_where ... HAVING subq_having)
    =>
    - oe $cmp$ (SELECT MAX(...) )  // handled by Item_singlerow_subselect
    - oe $cmp$ \<max\>(SELECT ...)   // handled by Item_maxmin_subselect
    
    fails=>Item_in_optimizer
    - 对于已经是materialized方案，不转换
    - 通过equi-join转换IN到EXISTS

*  如果是ALL/ANY单值subquery谓词，尝试用MIN/MAX子查询转换

SELECT * FROM t1 WHERE a < ANY (SELECT a FROM t1); 
    =>
    SELECT * FROM t1 WHERE a < (SELECT MAX(a) FROM t1)

![image.png][image.png 2]

*  不满足上面，调用single\_value\_in\_to\_exists\_transformer转换IN到EXISTS
    
     *  转换将要将子查询设置为相关子查询，设置UNCACHEABLE\_DEPENDENT标识
     *  如果子查询包含聚合函数、窗口函数、GROUP语法、HAVING语法，将判断条件加入到HAVING子句中，另外通过ref\_or\_null\_helper来区分NULL和False的结果，如需要处理NULL IN (SELECT ...)还需要封装到Item\_func\_trig\_cond触发器中。

SELECT ... FROM t1 WHERE t1.b IN (SELECT <expr of SUM(t1.a)> FROM t2)
    =>
    SELECT ... FROM t1 WHERE t1.b IN (SELECT <expr of SUM(t1.a)> FROM t2
                                     [trigcond] HAVING t1.b=ref-to-<expr of SUM(t1.a)>)

![image.png][image.png 3]

*  如果子查询不包含聚合函数、窗口函数、GROUP语法，会放在WHERE查询条件中，当然如果需要处理NULL情况还是要放入HAVING子句（Item\_func\_trig\_cond+Item\_is\_not\_null\_test）。

不需要区分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))

*  JOIN::optimize()会计算materialization和EXISTS转换的代价进行选择，设置m\_subquery\_to\_derived\_is\_impossible = true
 *  ROW值转换，通过Item\_in\_optimizer，不支持ALL/ANY/SOME（row\_value\_transformer）
    
     *  Item\_in\_subselect::row\_value\_in\_to\_exists\_transformer

for (each left operand)
      create the equi-join condition
      if (is_having_used || !abort_on_null)
        create the "is null" and is_not_null_test items
      if (is_having_used)
        add the equi-join and the null tests to HAVING
      else
        add the equi-join and the "is null" to WHERE
        add the is_not_null_test to HAVING

*  没有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)) ] <-- 保证不为NULL可以去掉HAVING

*  有HAVING表达式

(l1, l2, l3) IN (SELECT v1, v2, v3 ... HAVING having) =>
    EXISTS (SELECT ... HAVING having and
                              (l1 = v1 or is null v1) and
                              (l2 = v2 or is null v2) and
                              (l3 = v3 or is null v3) and
                              is_not_null_test(v1) and
                              is_not_null_test(v2) and
                              is_not_null_test(v3))

2 转换的标量子查询转换成Derived Table（transform\_scalar\_subqueries\_to\_join\_with\_derived）

该特性是官方在8.0.16中为了更好的支持Secondary Engine(Heapwave)的分析下推，增强了子查询的转换能力。可以先直观的看下转换和不转换的执行计划的不同：

*  transform\_scalar\_subqueries\_to\_join\_with\_derived具体转换的过程如下：
    
     *  首先从JOIN条件、WHERE条件、HAVING条件和SELECT list中收集可以转换的标量子查询（Item::collect\_scalar\_subqueries）。
     *  遍历这些子查询，判断是否可以增加一个额外的转换（transform\_grouped\_to\_derived）：把隐性的GROUP BY标量子查询变成Derived Table。

*  收集唯一的聚合函数Item列表（collect\_aggregates），这些Item将会被新的Derived Table的列代替。
    
     *  还需要添加所有引用到这些Item的fields，包括直接在SELECT列表的，Window函数参数、ORDER by、Partition by包含的，还有该查询块中ORDER BY的列，因为他们都会引动到Derived Table里。
     *  创建Derived Table需要的Query\_expression/Query\_block（create\_query\_expr\_and\_block）。
     *  添加Derived Table到查询块和top\_join\_list中。
     *  保留旧的子查询单元块，如果包含可以转化的Derived的移到Derived Table下面的Query\_block，如果不包含，保留到原来的子查询块中。
     *  将之前的聚合函数Item列表插入到Derived Table的查询块中。
     *  收集除GROUP AGG表达式中的列，由于这些fields已经移动到Derived Table中，删除不合理的fields引用。
     *  收集所有唯一的列和View的引用后，将他们加到新的Derived Table列表中。
     *  对新的新的Derived Table进行flatten\_subqueries/setup\_tables
     *  重新resolve\_placeholder\_tables，不处理进行转换后的子查询。
     *  处理Derived Table中，新加入的HAVING条件中的聚合函数Item，并通过Item\_aggregate\_refs引用到new\_derived->base\_ref\_items而不是之前的父查询块base\_ref\_items。
     *  永久代替父查询块中的聚合函数列表，变成Derived Table的列，并删除他们。
     *  之前保存和加入到Derived Table的唯一的列和View的引用，也要替换新的fields代替他们的引用。

![image.png][image.png 4]

*  但目前不支持HAVING表达式中包含该子查询，其实也是可以转换的。

SELECT SUM(a), (SELECT SUM(b) FROM t3) scalar
    FROM t1
    HAVING SUM(a) > scalar;
    转换为=>
    SELECT derived0.summ, derived1.scalar
    FROM (SELECT SUM(a) AS summ FROM t1) AS derived0
           LEFT JOIN
           (SELECT SUM(b) AS scalar FROM t3) AS derived1
           ON TRUE
    WHERE derived0.sum > derived1.scalar;

*  接下来遍历所有可以转换的子查询，把他们转换成derived tables，并替换相应的表达式变成列（transform\_subquery\_to\_derived）。
    
     *  生成derived table的TABLE\_LIST（synthesize\_derived）。
     *  将可以移动到derived table的where\_cond设置到join\_cond上。
     *  添加derived table到查询块的表集合中。
     *  decorrelate\_derived\_scalar\_subquery\_pre
     *  添加非相关引用列（NCF）到SELECT list，这些条件被JOIN条件所引用，并且还有另外一个fields包含了外查询相关的列，我们称之为'lifted\_where'
     *  添加COUNT(\*)到SELECT list，这样转换的查询块可以进行cardinality的检查。比如没有任何聚合函数在子查询中。如果确定包含聚合函数，返回一行一定是NCF同时在GROUP BY列表中。
     *  添加NCF到子查询的GROUP列表中，如果已经在了，需要加到最后，如果发生GROUP BY的列由于依赖性检查失败，还要加Item\_func\_any\_value（非聚合列）到SELECT list。对于NCF会创建 derived.field和derived.`count(field)` 。
     *  设置物化的一些准备（setup\_materialized\_derived）。
     *  decorrelate\_derived\_scalar\_subquery\_post：
     *  创建对应的'lifted\_fields'。
     *  更新JOIN条件中相关列的引用，不在引用外查询而换成Derived table相关的列。
 *  代替WHERE、JOIN、HAVING条件和SELECT list中的子查询的表达式变成对应的Derived Table里面列。

下面图解该函数的转换过程和结果：

![image.png][image.png 5]

![image.png][image.png 6]

3 扁平化子查询（flatten\_subqueries）

该函数主要是将Semi-join子查询转换为nested JOIN，这个过程只有一次，并且不可逆。

*  简单来讲步骤可以简化理解为：
    
     *  创建SEMI JOIN (it1 ... itN)语以部分，并加入到外层查询块的执行计划中。
     *  将子查询的WHERE条件以及JOIN条件，加入到父查询的WHERE条件中。
     *  将子查询谓词从父查询的判断谓词中消除。
 *  由于MySQL在一个query block中能够join的tables数是有限的(MAX\_TABLES)，不是所有sj\_candidates都可以做因此做flatten\_subqueries 的，因此需要有优先级决定的先后顺序先unnesting掉，优先级规则如下：
    
     *  相关子查询优先于非相关的
     *  inner tables多的子查询大于inner tables少的
     *  位置前的子查询大于位置后的

subq_item->sj_convert_priority =
            (((dependent * MAX_TABLES_FOR_SIZE) +  // dependent subqueries first
              child_query_block->leaf_table_count) *
             65536) +           // then with many tables
            (65536 - subq_no);  // then based on position

*  另外，由于递归调用flatten\_subqueries是bottom-up，依次把下层的子查询展开到外层查询块中。

for SELECT#1 WHERE X IN (SELECT #2 WHERE Y IN (SELECT#3)) :
    
        Query_block::prepare() (select#1)
           -> fix_fields() on IN condition
               -> Query_block::prepare() on subquery (select#2)
                   -> fix_fields() on IN condition
                        -> Query_block::prepare() on subquery (select#3)
                        <- Query_block::prepare()
                   <- fix_fields()
                   -> flatten_subqueries: merge #3 in #2
                   <- flatten_subqueries
               <- Query_block::prepare()
           <- fix_fields()
           -> flatten_subqueries: merge #2 in #1

*  遍历子查询列表，删除Item::clean\_up\_after\_removal标记为Subquery\_strategy::DELETED的子查询，并且根据优先级规则设置sj\_convert\_priority。根据优先级进行排序。
 *  遍历排序后的子查询列表，对于Subquery\_strategy::CANDIDATE\_FOR\_DERIVED\_TABLE策略的子查询，转换子查询(\[NOT\] \{IN, EXISTS\})为JOIN的Derived table（transform\_table\_subquery\_to\_join\_with\_derived）

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

*  设置策略为Subquery\_strategy::DERIVED\_TABLE
    
     *  semijoin子查询不能和antijoin子查询相互嵌套，或者外查询表已经超过MAX\_TABLE，不做转换，否则标记为Subquery\_strategy::SEMIJOIN策略。
     *  判断子查询的WHERE条件是否为常量。如果判断条件永远为FALSE，那么子查询结果永远为空。该情况下，调用Item::clean\_up\_after\_removal标记为Subquery\_strategy::DELETED，删除该子查询。
     *  如果无法标记为Subquery\_strategy::DELETED/设置Subquery\_strategy::SEMIJOIN策略的重新标记会Subquery\_strategy::UNSPECIFIED继续下一个。
     *  替换外层查询的WHERE条件中子查询判断的条件（replace\_subcondition）
     *  子查询内条件并不永远为FALSE，或者永远为FALSE的情况下，需要改写为antijoin（antijoin情况下，子查询结果永远为空，外层查询条件永远通过）。此时将条件改为永远为True。
     *  子查询永远为FALSE，且不是antijoin。那么将外层查询中的条件改成永远为False。
 *  Item\_subselect::EXISTS\_SUBS不支持有聚合操作
    
     *  convert\_subquery\_to\_semijoin函数解析如下模式的SQL
     *  IN/=ANY谓词
 *  如果条件满足解关联，解关联decorrelate\_condition
 *  添加解关联的内表表达式到 SELECT list
 *  收集FROM子句中的外表相关的 derived table或join条件
 *   *  去掉关联标识UNCACHEABLE\_DEPENDENT，更新used table
 *  Derived table子查询增加SELECT\_DISTINCT标识
 *  转换子查询成为一个derived table，并且插入到所属于的查询块FROM后（transform\_subquery\_to\_derived）
 *  创建derived table及其join条件
 *  遍历父查询块的WHERE，替换该子查询的Item代替成derived table（replace\_subcondition）
 *  遍历排序后的子查询列表，对于Subquery\_strategy::CANDIDATE\_FOR\_SEMIJOIN策略的子查询。
 *  判断是否可以转换为semijoin
 *  遍历排序后的子查询列表，对于Subquery\_strategy::SEMIJOIN的子查询，开始转换为semijoin/antijoin（convert\_subquery\_to\_semijoin）
    
     *  convert\_subquery\_to\_semijoin函数解析如下模式的SQL
     *  IN/=ANY谓词

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 EXISTS谓词

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

*  NOT IN谓词

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

*  查找可以插入semi-join嵌套和其生成的条件的位置，比如对于 t1 LEFT JOIN t2, embedding\_join\_nest为t2，t2也可以是nested，如t1 LEFT JOIN (t2 JOIN t3))
 *  生成一个新的semijoin嵌套的TABLE\_LIST表
 *  处理Antijoin
 *  将子查询中潜在的表合并到上述join表（TABLE\_LIST::merge\_underlying\_tables）
 *  将子查询的叶子表插入到当前查询块的叶子表后面，重新设置子查询的叶子表的序号和依赖的外表。将子查询的叶子表重置。
 *  如果是outer join的话，在join链表中传递可空性（propagate\_nullability）
 *  将内层子查询中的关联条件去关联化，这些条件被加入到semijoin的列表里。这些条件必须是确定的，仅支持简单判断条件或者由简单判断条件组成的AND条件（Query\_block::decorrelate\_condition）
    
     *  判断左右条件是否仅依赖于内外层表，将其表达式分别加入到semijoin内外表的表达式列表中（decorrelate\_equality）
 *  解关联内层查询的join条件（Query\_block::decorrelate\_condition）
 *  移除该子查询表达式在父查询的AST（Query\_express::exclude\_level）
 *  根据semi-join嵌套产生的WHERE/JOIN条件更新对应的table bitmap（Query\_block::fix\_tables\_after\_pullout）
 *  将子查询的WHERE条件上拉，更新使用表的信息（Item\_cond\_and::fix\_after\_pullout()）
 *  根据semijoin的条件列表创建AND条件，如果有条件为常量True，则去除该条件；如果常量为False，则整个条件都去除（Query\_block::build\_sj\_cond）
 *  将创建出来的semijoin条件加入到外层查询的WHERE条件中
 *  最后遍历排序后的子查询列表，对于没有转换的子查询，对于Subquery\_strategy::UNSPECIFIED的策略，执行IN->EXISTS改写（select\_transformer），如果确实原有的子查询已经有替代的Item，调用replace\_subcondition解析并把他们加入到合适的WHERE或者ON子句。
 *  清除所有的sj\_candidates列表
 *  Semi-join有5中执行方式，本文并不介绍Optimizer和Execution过程，详细可以参考引用文章中关于semijoin的介绍，最后引入下控制semijoin优化和执行的优化器开关，其中semijoin=on/off是总开关。

SELECT @@optimizer_switch\G
    *************************** 1. row ***************************
    @@optimizer_switch: ......
                        materialization=on,semijoin=on,loosescan=on,
                        firstmatch=on,
                        subquery_materialization_cost_based=on,
                        ......

*  下图举例说明该转换过程：

SELECT * FROM t1 WHERE t1.a in (SELECT t2.c1 FROM t2 where t2.c1 > 0);
    =>
    /* select#1 */
    SELECT `t1`.`a` AS `a`
    FROM `t1`
    SEMI JOIN (`t2`)
    WHERE ((`t1`.`a` = `t2`.`c1`) and (`t2`.`c1` > 0))
    执行计划如下：
    explain SELECT * FROM t1 WHERE t1.a in (SELECT t2.c1 FROM t2 where t2.c1 > 0);
    +----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-----------------------------------------------------------+
    | id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                                     |
    +----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-----------------------------------------------------------+
    |  1 | SIMPLE      | t2    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where; Start temporary                              |
    |  1 | SIMPLE      | t1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    2 |    50.00 | Using where; End temporary; Using join buffer (hash join) |
    +----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-----------------------------------------------------------+

![image.png][image.png 7]

4 应用当前查询块转换（apply\_local\_transforms）

该函数在flattern subqueries之后，bottom-up调用，主要分几个步骤：

**删除无用列（delete\_unused\_merged\_columns）**

如果查询块已经删除了一些derived tables/views，遍历SELECT列表的列，删除不必要的列

**简化JOIN（simplify\_joins）**

该函数会把Query\_block中的top\_join\_list的嵌套join的简化为扁平化的join list。嵌套连接包括table1 join table2，也包含table1, (table2, table3)这种形式。如果所示的简化过程：

![image.png][image.png 8]

**分区表的静态剪枝（prune\_partitions）**

由于剪枝根据HASH/RANGE/LIST及二级分区都有不同，这里简单介绍下剪枝过程，现有prune\_partitions是在prepare和optimize阶段会被调用，某些常量子查询被评估执行完。

struct TABLE {
       ......    
       partition_info *part_info{nullptr}; /* Partition related information */
       /* If true, all partitions have been pruned away */
       bool all_partitions_pruned_away{false};
       ......
    }
        
    SQL tranformation phase
    SELECT_LEX::apply_local_transforms
    --> prune_partitions
    
    for example, select * from employee where company_id = 1000 ;
    
    SQL optimizer phase
    JOIN::prune_table_partitions
    --> prune_partitions 
    ------>  based on tbl->join_cond_optim() or JOIN::where_cond
    
    for example, explain select * from employee where company_id = (select c1 from t1);

*  举例下面RANGE剪枝的过程：

root:ref> CREATE TABLE R2  (
        ->     a INT,
        ->     d INT
        -> ) PARTITION BY RANGE(a) (
        ->         PARTITION p20 VALUES LESS THAN (20),
        ->         PARTITION p40 VALUES LESS THAN (40),
        ->         PARTITION p60 VALUES LESS THAN (60),
        ->         PARTITION p80 VALUES LESS THAN (80),
        ->         PARTITION p100 VALUES LESS THAN MAXVALUE
        -> );
    Query OK, 0 rows affected (0.09 sec)
    
    root:ref> Select * From R2 where a > 40 and a < 80;

*  剪枝详细过程如下：
    
     *  由于剪枝需要根据不同条件产生的pruning结果进行交集，因此剪枝过程中需要使用read\_partitions这样的bitmap来保存是否使用该对应分区。另外剪枝过程类似迭代判断，因此引入了part\_iterator来保存开始、结束和当前，以及对应需要获取区间范围的endpoint函数和获取下一个值next的迭代器函数。这里巧妙的运用了指针，来兼容不同分区类型Hash/Range/List类型，如下图所示：

![e10bafcfac57127e4c60e98038d17d4.jpg][]

*  获取join\_cond或者m\_where\_cond的SEL\_TREE红黑树（get\_mm\_tree)
 *  调用find\_used\_partitions来获取满足的分区，对于SEL\_TREE的每个区间（interval）：1. 获取区间的左右端点 2.从左边继续获取下一个满足的分区，直到到右边端点结束，每次调用完需要进行bitmap的itersection。
 *  设置read\_partitions和lock\_partitions
 *  find\_used\_partitions是根据SEL\_TREE的结构进行递归，如图从左到右遍历next\_key\_part（and condition），然后再遍历SEL\_TREE的左右（也就是上下方向，or condition）深度递归。

(start)
         |                           $
         |   Partitioning keyparts   $  subpartitioning keyparts
         |                           $
         |     ...          ...      $
         |      |            |       $
         | +---------+  +---------+  $  +-----------+  +-----------+
         \-| par1=c1 |--| par2=c2 |-----| subpar1=c3|--| subpar2=c5|
           +---------+  +---------+  $  +-----------+  +-----------+
                |                    $        |             |
                |                    $        |        +-----------+
                |                    $        |        | subpar2=c6|
                |                    $        |        +-----------+
                |                    $        |
                |                    $  +-----------+  +-----------+
                |                    $  | subpar1=c4|--| subpar2=c8|
                |                    $  +-----------+  +-----------+
                |                    $
                |                    $
           +---------+               $  +------------+  +------------+
           | par1=c2 |------------------| subpar1=c10|--| subpar2=c12|
           +---------+               $  +------------+  +------------+
                |                    $
               ...                   $
    
    例如第一行（par1=c1 and par2=c2 and subpar1=c3 and subpar2=c5）的遍历的stack将是：
    in find_used_partitions(key_tree = "subpar2=c5") (***)
    in find_used_partitions(key_tree = "subpar1=c3")
    in find_used_partitions(key_tree = "par2=c2")   (**)
    in find_used_partitions(key_tree = "par1=c1")
    in prune_partitions(...)
    然后是继续下面的条件，以此类推
    or（par1=c1 and par2=c2 and subpar1=c3 and subpar2=c6）
    or（par1=c1 and par2=c2 and subpar1=c4 and subpar2=c8）
    or（par1=c2 and subpar1=c10 and subpar2=c12）

*  下图来展示了pruning的结构和过程：

![image.png][image.png 9]

5 下推条件到Derived Table（push\_conditions\_to\_derived\_tables）

该函数将条件下推到derived tables，详细见WL\#8084 - Condition pushdown to materialized derived table。

root:test> set optimizer_switch = 'derived_merge=off'; // 关闭dervied_merge 测试下推能力
    Query OK, 0 rows affected (0.00 sec)
    
    root:test> EXPLAIN FORMAT=tree SELECT * FROM (SELECT c1,c2 FROM t1) as dt     WHERE c1 > 10;
    +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
    | EXPLAIN                                                                                                                                                                                             |
    +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
    | -> Table scan on dt  (cost=2.51..2.51 rows=1)
        -> Materialize  (cost=2.96..2.96 rows=1)
            -> Filter: (t1.c1 > 10)  (cost=0.35 rows=1)
                -> Table scan on t1  (cost=0.35 rows=1)
     |
    +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

过程如下：

*  遍历derived table列表，判断是否可以下推（can\_push\_condition\_to\_derived），如果包括下面的情况则不能下推：
    
     *  Derived table有UNION
     *  Derived table有LIMIT
     *  Derived table不能是outer join中的内表，会导致更多NULL补偿的行
     *  不能是CTE包含的Derived table
 *  创建可以下推到的Derived table的where cond（Condition\_pushdown::make\_cond\_for\_derived）
 *  保留剩余不能下推的条件（Condition\_pushdown::get\_remainder\_cond）
 *  Top-down递归调用push\_conditions\_to\_derived\_tables

详细图解该过程如下：

![image.png][image.png 10]

### 三 综述 ###

两篇文章重点介绍了下优化器的基于规则的优化部分，并没有涉及更多的基于代价的优化，可以看到对于直接运用规则优化带来执行的加速，那么可以直接转换，尤其是对于查询结构上面的变化类转换，如merge\_derived。对于运用规则优化无法判断是否带来执行的加速，那么优化器会保留一些临时结构，为后续的代价估算提供更多选择，如IN/EXIST/Materialized转换。当然还有一些，又改变查询结构又无法判定是否规则转换带来的执行加速，MySQL目前还不支持。文章虽然详尽，但无法覆盖全部情况，也是为了抛砖引玉，还需要读者自己通过调试的方法更进一步了解某一类SQL的具体过程。

### 四 参考资料 ###

《MySQL 8.0 Server层最新架构详解》

《WL\#13520: Transform correlated scalar subqueries》

《WL\#8084 - Condition pushdown to materialized derived table》

《WL\#2980: Subquery optimization: Semijoin》

*  WL\#3740: Subquery optimization: Semijoin: Pull-out of inner tables
 *  WL\#3741: Subquery optimization: Semijoin: Duplicate elimination strategy
 *  WL\#3750: Subquery optimization: Semijoin: First-match strategy
 *  WL\#3751: Subquery optimization: Semijoin: Inside-out strategy

《WL\#4389: Subquery optimizations: Make IN optimizations also handle EXISTS》

《WL\#4245: Subquery optimization: Transform NOT EXISTS and NOT IN to anti-join》

《WL\#2985: Perform Partition Pruning of Range conditions》

《MySQL · 源码分析 · Semi-join优化执行代码分析》

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

《Optimizing Subqueries, Derived Tables, View References, and Common Table Expressions》

[原文链接][Link 1]

本文为阿里云原创内容，未经允许不得转载。

[image.png]: /images/20220828/7b4ec6db60034203a9c292d7572726ad.png
[image.png 1]: /images/20220828/89e0a800aaa5491d93e83e8b46720a70.png
[image.png 2]: /images/20220828/f3dc9bca1ebb4b0b98de06b96b38ecd7.png
[image.png 3]: /images/20220828/84e3cc56d54a42268f3c7ebea6537661.png
[image.png 4]: /images/20220828/c65c1f6af2ba48898db1b526b5d706cd.png
[image.png 5]: /images/20220828/19dc7f28978e4a5d8fbcff356f0ba3f3.png
[image.png 6]: /images/20220828/5aad005811f3440289af6691afe82a6b.png
[image.png 7]: /images/20220828/cb37ac495d514099a0bea2d25dc8d0b1.png
[image.png 8]: /images/20220828/8cb13d6f163c4a19b5ed32ebac00e822.png
[e10bafcfac57127e4c60e98038d17d4.jpg]: /images/20220828/bc9d9a8b77174185899875823449ff6a.png
[image.png 9]: /images/20220828/55363e43d8f74cef88f05f30788d7a80.png
[image.png 10]: /images/20220828/9f25044bf2094ceeaa81a3ba60aa1ad0.png
[Link 1]: http://click.aliyun.com/m/1000296620/