简介：SQL 优化器实质上是一种高度抽象化的数据接口的实现，通过该设计，客户能够应用更通用且易于了解的 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.c1
FROM 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 profit
FROM sales
GROUP 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_table
ORDER 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_avg
FROM 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，期待与您独特打造世界一流的下一代云原生分布式关系型数据库。
原文链接
本文为阿里云原创内容，未经容许不得转载。