简介：本文重点介绍了优化器的基于规定的其中一部分优化，更多的偏重于SQL中的根本操作符

一  背景和架构

咱们都晓得，利用编写程序来动静实现咱们利用所须要的逻辑，从而程序执行时失去咱们须要的后果。那么数据库就是一种通过输出SQL字符串来疾速获取数据的利用。当然，假如没有数据库这种零碎利用，用程序如何实现呢？咱们可能会发现，即便不论数据如何存储、数据是否并发拜访，依然须要一直通过批改程序处理不同利用对数据的不同申请。比方大数据畛域，咱们通常通过非关系型数据库的API，实现对数据的获取。然而这种形式尽管入门简略，然而保护极难，而且通用性不强，即便一直进行软件架构设计或者形象重构，依然须要一直地变换利用，这也是为何非关系型数据库回头拥抱数据库SQL优化器的起因。

SQL优化器实质上是一种高度抽象化的数据接口的实现，通过该设计，客户能够应用更通用且易于了解的SQL语言，对数据进行操作和解决，而不须要关注和形象本人的数据接口，极大地解放了客户的应用程序。

本文就来通过图形讲解的形式介绍下MySQL 8.0 SQL优化器如何把一个简略的字符串（SQL），变成数据库执行器能够了解的执行序列，最终将数据返还给客户。弱小的优化器是不须要客户关注SQL如何写的更好来更快取得须要的数据，因而优化器对原始SQL肯定会做一些等价的变动。在《MySQL 8.0 Server层最新架构详解》一文中咱们重点介绍了MySQL最新版本对于Server层解析器、优化器和执行器的总体介绍，包含一些代码构造和变动的具体展现，并且通过simple\_joins函数抛砖引玉展现了MySQL优化器在逻辑变换中如何简化嵌套Join的优化。本文咱们会一步一步带你进入神奇的优化器细节，具体理解优化器优化局部的每个步骤如何扭转着一个SQL最终的执行。

本文基于最新MySQL8.0.25版本，因为优化器转换局部篇幅比拟长，咱们分成两篇文章来介绍，第一局部介绍基于根本构造的Setup和Resolve的解析转换过程，第二局部介绍更为简单的子查问、分区表和连贯的简单转换过程，纲要如下：

Setup and Resolve

• setup\_tables : Set up table leaves in the query block based on list of tables.

• resolve\_placeholder\_tables/merge\_derived/setup\_table\_function/setup\_materialized\_derived : Resolve derived table, view or table function references in query block.

• setup\_natural\_join\_row\_types : Compute and store the row types of the top-most NATURAL/USING joins.

• setup\_wild : Expand all '*' in list of expressions with the matching column references.

• setup\_base\_ref\_items : Set query\_block's base\_ref\_items.

• setup\_fields : Check that all given fields exists and fill struct with current data.

• setup\_conds : Resolve WHERE condition and join conditions.

• setup\_group : Resolve and set up the GROUP BY list.

• m\_having\_cond->fix\_fields : Setup the HAVING clause.

• resolve\_rollup : Resolve items in SELECT list and ORDER BY list for rollup processing.

• resolve\_rollup\_item : Resolve an item (and its tree) for rollup processing by replacing items matching grouped expressions with Item\_rollup\_group\_items and updating properties (m\_nullable, PROP\_ROLLUP\_FIELD). Also check any GROUPING function for incorrect column.

• setup\_order : Set up the ORDER BY clause.

• resolve\_limits : Resolve OFFSET and LIMIT clauses.

• Window::setup\_windows1: Set up windows after setup\_order() and before setup\_order\_final().

• setup\_order\_final: Do final setup of ORDER BY clause, after the query block is fully resolved.

• setup\_ftfuncs : Setup full-text functions after resolving HAVING.

• resolve\_rollup\_wfs : Replace group by field references inside window functions with references in the presence of ROLLUP.

二  具体转换过程

转换的整个框架是由Query\_expression到Query\_block调用prepare函数(sql/sql\_resolver.cc)并且依据不同转换规则的要求自顶向下或者自底向上的过程。

1  传递null到join的内表列表（propagate\_nullability）

prepare开始先要解决nullable table，它指的是table可能蕴含全为null的row，依据JOIN关系（top\_join\_list）null row能够被流传。如果能确定一个table为nullable会使得一些优化进化，比方access method不能为EQ\_REF、outer join不能优化为inner join等。

2  解析设置查问块的leave\_tables（setup\_tables）

SELECT  t1.c1FROM t1,     (SELECT       t2.c1     FROM t2,          (SELECT            t3.c1          FROM t3          UNION          SELECT            t4.c1          FROM t4) AS t3a) AS t2a;

未在setup\_table调用之前，每个Query\_block的leaf\_tables是为0的。

该函数的作用就是构建leaf\_tables，包含base tables和derived tables列表，用于后续的优化。setup\_tables并不会递归调用，而是只解决本层的tables，并统计出本层derived table的个数。然而随后会调用resolve\_placeholder\_tables()->resolve\_derived()->derived(Query\_expression)::prepare->Query\_block::prepare来专门递归解决derived table对应的Query\_expression。

接下来咱们依据prepare的调用程序，持续看下针对于derived table解决的函数resolve\_placeholder\_tables。

3  解析查问块Derived Table、View、Table函数 （resolve\_placeholder\_tables）

这个函数用于对derived table、view和table function的解决，如果该table曾经merged过了，或者是因为应用transform\_grouped\_to\_derived()被调用到，曾经决定应用materialized table形式，则间接疏忽。

后面曾经介绍过resolve\_derived()的作用，咱们重点介绍merge\_derived()函数，merge\_derived是扭转Query\_expression/Query\_block框架结构，将derived table或者view合并到到query block中。

merge\_derived 解决和合并Derived table

1）merge\_derived transformation的先决条件

• 外层query block是否容许merge（allow\_merge\_derived）

• • 外层query block为nullptr

• • 外层query expression的子查问为nullptr，derived table是第一层子查问

• • 外层的外层query block能够allow\_merge\_derived=true，或者不包含外层的外层query block话是否为SELECT/SET

• 外层lex是否能够反对merge（lex->can\_use\_merged()+lex->can\_no\_use\_merged()）

• derived table是否曾经被标记为须要物化materialize，比方创立视图的办法是CREATE ALGORITHM=TEMPTABLE VIEW（derived\_table->algorithm == VIEW\_ALGORITHM\_TEMPTABLE）

• 整个dervived table所在的查问表达式单元中，不能是（Query\_expression::is\_mergeable() ）：

• • Union查问
  • 蕴含汇集、HAVING、DISTINCT、WINDOWS或者LIMIT
  • 没有任何table list

• HINT或者optimizer\_switch没有禁止derived\_merge；

• heuristic倡议合并(derived\_query\_expressionmerge\_heuristic())；

• • 如果derived table蕴含的子查问SELECT list依赖于本人的列时，不反对；

• • 如果是dependant subquery须要屡次执行时，不反对；

• derived table中如果查问块蕴含SEMI/ANTI-JOIN，并指定STRAIGHT\_JOIN时，不反对；

• 如果合并的derived table和现有query block的leaf table count大概 MAX\_TABLES时，不反对；

2）merge\_derived transformation的转换过程

• 利用derived\_table->nested\_join构造来辅助解决OUTER JOIN的状况。

• 把derived table中的表merge到NESTED\_JOIN构造体（derived\_table->merge\_underlying\_tables()）。

• 将derived table中的所有表连贯到父查问的table\_list列表中，同时把derived table从父查问中删除。

• 对父查问的所有相干数据结构进行从新计算（leaf\_table\_count、derived\_table\_count、table\_func\_count、materialized\_derived\_table\_count、has\_sj\_nests、has\_aj\_nests、partitioned\_table\_count、cond\_count、between\_count、select\_n\_having\_items）。

• 流传设置父查问OPTION\_SCHEMA\_TABLE（add\_base\_options()）和如果是外查问JOIN的内表，流传设置nullable属性（propagate\_nullability()）。

• 合并derived table的where条件到外查问中（merge\_where()）。

• 建设对derived table须要获取的列的援用（create\_field\_translation()）。

• 将Derived table的构造从父查问中删除（exclude\_level()）。

• 将derived table中的列或者表的重命名合并到父查问（fix\_tables\_after\_pullout()/repoint\_contexts\_of\_join\_nests()）。

• 因为曾经把derived table中蕴含的表merge到了父查问，所以须要对TABLE\_LIST中的表所在的地位进行从新定位（remap\_tables()）。

• 将derived table合并到父查问之后，须要从新批改原来derived table中所有对derived table中所有列的援用（fix\_tables\_after\_pullout()）。

• 如果derived table中蕴含ORDER BY语句，如果满足下列条件，derived table将会保留ORDER BY并合并到父查问中，其余状况ORDER BY将会被疏忽掉：

• • 如果父查问容许排序并且正好是只有derived table
  • 不是一个UNION
  • 能够有WHERE条件，然而不能有group by或聚合函数
  • 自身并不是有序的

过程简化为：

merge\_derived 图解过程

看起来官网的derived merge还是不够完满，无奈自底向上的递归merge蕴含的opt trace：

trace_derived.add_utf8_table(derived_table)       .add("select#", derived_query_block->select_number)       .add("merged", true);trace_derived.add_alnum("transformations_to_derived_table", "removed_ordering");

该优化能够通过set optimizer\_switch="derived\_merge=on/off"来管制。

setup\_materialized\_derived 设置物化Derived Table

对于剩下不能采纳 merge 算法的 derived table ，会转为materialize 物化形式去解决。但此时只是做一些变量设置等预处理，理论的物化执行是在executor阶段执行。

• setup\_materialized\_derived\_tmp\_table(): 设置一个长期表蕴含物化Derived Table的所有行数据。

• check\_materialized\_derived\_query\_blocks(): 设置属于以后Derived Table所在的查问块构造。

trace_derived.add_utf8_table(this)       .add("select#", derived->first_query_block()->select_number)       .add("materialized", true);

setup\_table\_function 处理表函数

如果 query block 中有 table function，整个过程会解决两遍。第一遍会跳过 table function 的 table ，第二遍才专门再对table function 的 table 执行一遍上述逻辑。这里的思考应该是先 resolve 了外部环境（绝对于table function），因为有可能函数参数会有依赖内部的 derived table。

trace_derived.add_utf8_table(this)       .add_utf8("function_name", func_name, func_name_len)       .add("materialized", true);

4  将SELECT *的通配符开展成具体的fields（setup\_wild）

5  建设Query\_block级别的base\_ref\_items（setup\_base\_ref\_items)

base\_ref\_items记录了所有Item的地位，不便查问块的其余Item能够进行援用，或者通过Item\_ref及其Item\_ref子类进行间接援用，例如子查问的援用（Item\_view\_ref）、聚合函数援用（Item\_aggregate\_ref）、外查问列的援用（Item\_outer\_ref）、subquery 子查问产生NULL value的援用辅助（Item\_ref\_null\_helper）。

举例说明比较复杂的Item\_outer\_ref：

6  对select\_fields进行fix\_fields()和列权限查看（setup\_fields）

下图是比较复杂的带子查问的fixed field过程。有些field和表关联，有的要增加相应的Item\_xxx\_ref援用。

7  解析和fixed\_fields WHERE条件和Join条件（setup\_conds）

setup\_join\_cond如果有nested\_join会递归调用setup\_join\_cond进行解析和设置。这里也顺带介绍下simplify\_const\_condition函数的作用，如果发现能够删除的const Item，则会用Item\_func\_true/Item\_func\_false来代替整个的条件，如图。

8  解析和设置ROLLUP语句（resolve\_rollup）

在数据库查问语句中，在 GROUP BY 表达式之后加上 WITH ROLLUP 语句，能够使得通过单个查问语句来实现对数据进行不同层级上的剖析与统计。

SELECT YEAR,       country,       product,       SUM(profit) AS profitFROM salesGROUP BY YEAR,         country,         product WITH ROLLUP;+------+---------+------------+--------+| year | country | product    | profit |+------+---------+------------+--------+| 2000 | Finland | Computer   |   1500 || 2000 | Finland | Phone      |    100 || 2000 | Finland | NULL       |   1600 || 2000 | India   | Calculator |    150 || 2000 | India   | Computer   |   1200 || 2000 | India   | NULL       |   1350 || 2000 | USA     | Calculator |     75 || 2000 | USA     | Computer   |   1500 || 2000 | USA     | NULL       |   1575 || 2000 | NULL    | NULL       |   4525 || 2001 | Finland | Phone      |     10 || 2001 | Finland | NULL       |     10 || 2001 | USA     | Calculator |     50 || 2001 | USA     | Computer   |   2700 || 2001 | USA     | TV         |    250 || 2001 | USA     | NULL       |   3000 || 2001 | NULL    | NULL       |   3010 || NULL | NULL    | NULL       |   7535 |+------+---------+------------+--------+相当于做了上面的查问：SELECT *FROM  (SELECT YEAR,          country,          product,          SUM(profit) AS profit   FROM sales   GROUP BY YEAR,            country,            product   UNION ALL SELECT YEAR,                    country,                    NULL,                    SUM(profit) AS profit   FROM sales   GROUP BY YEAR,            country   UNION ALL SELECT YEAR,                    NULL,                    NULL,                    SUM(profit) AS profit   FROM sales   GROUP BY YEAR   UNION ALL SELECT NULL,                    NULL,                    NULL,                    SUM(profit) AS profit   FROM sales) AS sum_tableORDER BY YEAR, country, product;+------+---------+------------+--------+| YEAR | country | product    | profit |+------+---------+------------+--------+| NULL | NULL    | NULL       |   7535 || 2000 | NULL    | NULL       |   4525 || 2000 | Finland | NULL       |   1600 || 2000 | Finland | Computer   |   1500 || 2000 | Finland | Phone      |    100 || 2000 | India   | NULL       |   1350 || 2000 | India   | Calculator |    150 || 2000 | India   | Computer   |   1200 || 2000 | USA     | NULL       |   1575 || 2000 | USA     | Calculator |     75 || 2000 | USA     | Computer   |   1500 || 2001 | NULL    | NULL       |   3010 || 2001 | Finland | NULL       |     10 || 2001 | Finland | Phone      |     10 || 2001 | USA     | NULL       |   3000 || 2001 | USA     | Calculator |     50 || 2001 | USA     | Computer   |   2700 || 2001 | USA     | TV         |    250 |+------+---------+------------+--------+

排序因为有NULL的问题，所以分级汇总的成果十分难弄，而且group 列不同扭转，SQL复杂度来回变动，而ROLLUP很简略就能够实现成果，上面看下rollup在解析过程做了什么样的转换达到了意想不到的成果。

9  解析和设置GROUP BY/ORDER BY语句（setup\_group/setup\_order）

其中一个函数find\_order\_in\_list(): 尝试在select fields里去寻找能够映射的列，否则就得在最初投影的all fields里加上当前列，同时也做fix\_fields。

• m\_having\_cond->fix\_fields : 对having条件进行fixed\_fields。

• resolve\_limits : 解决OFFSET和LIMIT子句（offset\_limit和select\_limit的Items）。

• setup\_ftfuncs : 如果有full-text的函数，对相干Item进行fix\_fields。

• remove\_redundant\_subquery\_clause : 对于Table Subquery的表达式，通常是IN/ANY/ALL/EXISTS/etc，如果没有聚合函数和Having子句，通常能够思考删除不必要的ORDER/DISTINCT/GROUP BY。该函数反对三种REMOVE\_ORDER | REMOVE\_DISTINCT | REMOVE\_GROUP，如果是SINGLEROW\_SUBS的子查问，只思考删除REMOVE\_ORDER。

select c1 from t1 where t1.c2 in (select distinct c1 from t2 group by c1, c2 order by c1);转化为 =>select c1 from t1 where t1.c2 in (select c1 from t2);

• 解决是否能够删除不必要的distinct语句，删除的条件就是GROUP BY的列都在SELECT列表中，并且没有ROLLUP和Window函数。

is_grouped() && hidden_group_field_count == 0 && olap == UNSPECIFIED_OLAP_TYPE

例如场景：

SELECT DISTINCT c1, max(c2) from t1 group by c1;

10  解析和设置Window函数（Window::setup\_windows1）

SELECT id,       release_year,       rating,       avg(rating) over(PARTITION BY release_year) AS year_avgFROM tw;+------+--------------+--------+-------------------+| id   | release_year | rating | year_avg          |+------+--------------+--------+-------------------+|    1 |         2015 |      8 |               8.5 ||    3 |         2015 |      9 |               8.5 ||    2 |         2015 |    8.5 |               8.5 ||    4 |         2016 |    8.2 |               8.3 ||    5 |         2016 |    8.4 |               8.3 ||    6 |         2017 |      7 |                 7 |+------+--------------+--------+-------------------+

执行的过程和后果相似于下图：

咱们看下它在开始Query\_block::prepare解析过程做了哪些事件：
select\_lex->m\_windows 不为空，就调用 Window::setup\_windows1

• 遍历window函数列表，调用resolve\_window\_ordering来解析m\_partition\_by和m\_order\_by

• 解决inter-window的援用关系（如WINDOW w1 AS (w2), w2 AS (), w3 AS (w1)），但必须是一个有向无环图（DAG）

• 从新遍历查看是否惟一名字check\_unique\_name、创立window partition by和window order by的援用items

• 查看窗口函数特色（Window::check\_window\_functions1(THD *thd, \_block *select)）

• • 首先判断的是以后是动态窗口还是动静窗口；动态窗口即判断了 frame 的定义是否有定义高低边界。m\_static\_aggregates 为 true, 意味着是动态窗口，同时对每一个分区都能够进行一次评估。如果 ma\_static\_aggregates 为 false, 则进一步判断其滑动窗口应用的是基于范畴还是基于行。 m\_row\_optimizable 基于行 m\_range\_optimizable 基于范畴 

• • 获取聚合函数作为窗口函数时候窗口的非凡规格要求wfs->check\_wf\_semantics1(thd, select, &reqs) 这个办法其实就是判断是不是须要row\_buffer作为评估，如果咱们只看以后分区的行无奈进行正确的计算不须要，而须要看之后的或者之前的行，就须要应用row\_buffer。

三  综述

本文重点介绍了下优化器的基于规定的其中一部分优化，更多的偏重于SQL中的根本操作符，如表、列、函数、聚合、分组、排序等元素的解析和设置以及一些不言而喻的构造变动。下一篇文章咱们将持续介绍子查问、分区表和JOIN操作的转换局部，敬请期待。

四  参考资料

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

• 《Mysql derived\_MySQL · 新个性剖析 · 5.7中Derived table变形记》

• 《ROLLUP性能加强》

• 《WL#9236, WL#9603 and WL#9727 - Add SQL window functions to MySQL》

五  对于咱们

PolarDB 是阿里巴巴自主研发的云原生分布式关系型数据库，于2020年进入Gartner寰球数据库Leader象限，并取得了2020年中国电子学会颁发的科技进步一等奖。PolarDB 基于云原生分布式数据库架构，提供大规模在线事务处理能力，兼具对简单查问的并行处理能力，在云原生分布式数据库畛域整体达到了国内领先水平，并且失去了宽泛的市场认可。在阿里巴巴团体外部的最佳实际中，PolarDB还全面撑持了2020年天猫双十一，并刷新了数据库解决峰值记录，高达1.4亿TPS。欢送有志之士退出咱们，简历请投递到daoke.wangc@alibaba-inc.com，期待与您独特打造世界一流的下一代云原生分布式关系型数据库。

版权申明：本文内容由阿里云实名注册用户自发奉献，版权归原作者所有，阿里云开发者社区不领有其著作权，亦不承当相应法律责任。具体规定请查看《阿里云开发者社区用户服务协定》和《阿里云开发者社区知识产权爱护指引》。如果您发现本社区中有涉嫌剽窃的内容，填写侵权投诉表单进行举报，一经查实，本社区将立即删除涉嫌侵权内容。