简介： 本文基于 MySQL 8.0.25 源码进行剖析和总结。这里 MySQL Server 层指的是 MySQL 的优化器、执行器局部。咱们对 MySQL 的了解还建设在 5.6 和 5.7 版本的了解之上，更多的是比照 PostgreSQL 或者传统数据库。然而从 MySQL 8.0 开始，继续每三个月的迭代和重构工作，使得 MySQL Server 层的整体架构有了质的飞越。上面来看下 MySQL 最新的架构。

背景和架构

本文基于 MySQL 8.0.25 源码进行剖析和总结。这里 MySQL Server 层指的是 MySQL 的优化器、执行器局部。咱们对 MySQL 的了解还建设在 5.6 和 5.7 版本的了解之上，更多的是比照 PostgreSQL 或者传统数据库。然而从 MySQL 8.0 开始，继续每三个月的迭代和重构工作，使得 MySQL Server 层的整体架构有了质的飞越。上面来看下 MySQL 最新的架构。

咱们能够看到最新的 MySQL 的分层架构和其余数据库并没有太大的区别，另外值得一提的是从图中能够看出 MySQL 当初更多的增强 InnoDB、NDB 集群和 RAPID(HeatWave clusters) 内存集群架构的演进。上面咱们就看下具体细节，咱们这次不随着官网的 Feature 实现和重构程序进行了解，本文更偏差于从优化器、执行器的流程角度来演进。

MySQL 解析器 Parser 

首先从 Parser 开始，官网 MySQL 8.0 应用 Bison 进行了重写，生成 Parser Tree，同时 Parser Tree 会 contextualize 生成 MySQL 形象语法树（Abstract Syntax Tree）。

MySQL 形象语法树和其余数据库有些不同，参考《MySQL 8.0 新的火山模型执行器》文章，是由让比拟让人拗口 SELECT\_LEX\_UNIT/SELECT\_LEX 类交替形成的，然而这两个构造在最新的版本中曾经重命名成规范的 SELECT\_LEX -> Query\_block 和 ELECT\_LEX\_UNIT -> Query\_expression。Query\_block 是代表查问块，而 Query\_expression 是蕴含多个查问块的查问表达式，包含 UNION AND/OR 的查问块（如 SELECT * FROM t1 union SELECT * FROM t2）或者有多 Level 的 ORDER BY/LIMIT (如 SELECT * FROM t1 ORDER BY a LIMIT 10) ORDER BY b LIMIT 5

例如，来看一个简单的嵌套查问：

(SELECT *
   FROM ttt1)
UNION ALL
  (SELECT *
   FROM
     (SELECT *
      FROM ttt2) AS a,
     (SELECT *
      FROM ttt3
      UNION ALL SELECT *
      FROM ttt4) AS b)

在 MySQL 中就能够用上面形式表白：

通过解析和转换后的语法树依然建设在 Query\_block 和 Query\_expression 的框架下，只不过有些 LEVEL 的 query block 被打消或者合并了，这里不在具体开展。

MySQL prepare/rewrite 阶段

接下来咱们要通过 resolve 和 transformation 过程 Query\_expression::prepare->Query\_block::prepare，这个过程包含（按性能分而非齐全依照执行程序）：

Setup and Fix

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

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.

这里，节俭篇幅，咱们只举例关注下和 top\_join\_list 相干的 simple\_joins 这个函数的作用，对于 Query\_block 中嵌套 join 的简化过程。

比照 PostgreSQL

为了更清晰的了解规范数据库的做法，咱们这里援用了 PostgreSQL 的这三个过程：

Parser

下图首先 Parser 把 SQL 语句生成 parse tree。

testdb=# SELECT id, data FROM tbl_a WHERE id < 300 ORDER BY data;

Analyzer/Analyser

下图展现了 PostgreSQL 的 analyzer/analyser 如何将 parse tree 通过语义剖析后生成 query tree。

Rewriter

Rewriter 会依据规定零碎中的规定把 query tree 进行转换改写。

sampledb=# CREATE VIEW employees_list 
sampledb-#      AS SELECT e.id, e.name, d.name AS department 
sampledb-#            FROM employees AS e, departments AS d WHERE e.department_id = d.id;

下图的例子就是一个蕴含 view 的 query tree 如何开展成新的 query tree。

sampledb=# SELECT * FROM employees_list;

MySQL Optimize 和 Planning 阶段

接下来咱们进入了逻辑打算生成物理打算的过程，本文还是重视于构造的解析，而不去介绍生成的细节，MySQL 过来在 8.0.22 之前，次要依赖的构造就是 JOIN 和 QEP\_TAB。JOIN 是与之对应的每个 Query\_block，而 QEP\_TAB 对应的每个 Query\_block 波及到的具体“表”的程序、办法和执行打算。然而在 8.0.22 之后，新的基于 Hypergraph 的优化器算法胜利的摈弃了 QEP\_TAB 构造来表白左深树的执行打算，而间接应用 HyperNode/HyperEdge 的图来示意执行打算。

举例能够看到数据结构表白的 left deep tree 和超图构造表白的 bushy tree 对应的不同打算展示：

| -> Inner hash join (no condition)  (cost=1.40 rows=1)
    -> Table scan on R4  (cost=0.35 rows=1)
    -> Hash
        -> Inner hash join (no condition)  (cost=1.05 rows=1)
            -> Table scan on R3  (cost=0.35 rows=1)
            -> Hash
                -> Inner hash join (no condition)  (cost=0.70 rows=1)
                    -> Table scan on R2  (cost=0.35 rows=1)
                    -> Hash
                        -> Table scan on R1  (cost=0.35 rows=1)
| -> Nested loop inner join  (cost=0.55..0.55 rows=0)
    -> Nested loop inner join  (cost=0.50..0.50 rows=0)
        -> Table scan on R4  (cost=0.25..0.25 rows=1)
        -> Filter: (R4.c1 = R3.c1)  (cost=0.35..0.35 rows=0)
            -> Table scan on R3  (cost=0.25..0.25 rows=1)
    -> Nested loop inner join  (cost=0.50..0.50 rows=0)
        -> Table scan on R2  (cost=0.25..0.25 rows=1)
        -> Filter: (R2.c1 = R1.c1)  (cost=0.35..0.35 rows=0)
            -> Table scan on R1  (cost=0.25..0.25 rows=1)

MySQL8.0.2x 为了更好的兼容两种优化器，引入了新的类 AccessPath，能够认为这是 MySQL 为理解耦执行器和不同优化器形象进去的 Plan Tree。

老优化器的入口

老优化器依然走 JOIN::optimize 来把 query block 转换成 query execution plan (QEP.)

这个阶段依然做一些逻辑的重写工作，这个阶段的转换能够了解为基于 cost-based 优化前做筹备，具体步骤如下：

• Logical transformations:
• • optimize\_derived : Optimize the query expression representing a derived table/view.
  • optimize\_cond : Equality/constant propagation.
  • prune\_table\_partitions : Partition pruning.
  • optimize\_aggregated\_query : COUNT(*), MIN(), MAX() constant substitution in case of implicit grouping.
  • substitute\_gc : ORDER BY optimization, substitute all expressions in the WHERE condition and ORDER/GROUP lists that match generated columns (GC) expressions with GC fields, if any.
• Perform cost-based optimization of table order and access path selection.
• • JOIN::make\_join\_plan() : Set up join order and initial access paths.
• Post-join order optimization
• • substitute\_for\_best\_equal\_field : Create optimal table conditions from the where clause and the join conditions.
  • make\_join\_query\_block : Inject outer-join guarding conditions.
  • Adjust data access methods after determining table condition (several times.)
  • optimize\_distinct\_group\_order : Optimize ORDER BY/DISTINCT.
  • optimize\_fts\_query : Perform FULLTEXT search before all regular searches.
  • remove\_eq\_conds : Removes const and eq items. Returns the new item, or nullptr if no condition.
  • replace\_index\_subquery/create\_access\_paths\_for\_index\_subquery : See if this subquery can be evaluated with subselect\_indexsubquery\_engine
  • setup\_join\_buffering : Check whether join cache could be used
• Code generation
• • alloc\_qep(tables) : Create QEP\_TAB array
  • test\_skip\_sort : Try to optimize away sorting/distinct.
  • make\_join\_readinfo : Plan refinement stage: do various setup things for the executor
  • make\_tmp\_tables\_info : Setup temporary table usage for grouping and/or sorting.
  • push\_to\_engines : Push (parts of) the query execution down to the storage engines if they can provide faster execution of the query, or part of it.
  • create\_access\_paths : generated ACCESS\_PATH.

新优化器的入口

新优化器默认不关上，必须通过 set optimizer\_switch=”hypergraph\_optimizer=on”; 来关上，其代码流程如下：

FindBestQueryPlan
-> MakeJoinHypergraph 构建 hypergraph
  -> MakeRelationalExpressionFromJoinList 基于 top_join_list 构建 operator tree
  ...
  -> MakeJoinGraphFromRelationalExpression 基于 operator tree => hypergraph
     目前对 non-inner join 的束缚比拟粗犷:
     1. Inner join，且左右子树都只有 inner join，只束缚 SES
     2. Inner join，但子树有非 inner join: 将那颗子树整个固定在以后 operator 下, 作为 hypernode
     3. 非 Inner join，间接把左右子树都固定死，变成 2 个 hypernode
...
-> EnumerateAllConnectedPartitions 开始算法流程 (Solve)
  -> EnumerateComplementsTo 找互补对 (EmitCsg)
     -> FoundSubgraphPair 找到 csg-cmp-pair (EmitCsgCmp)
     -> ExpandComplement 扩大互补对 (EnumerateCmpRec)
  -> ExpandSubgraph 扩大连通子图 (EnumerateCsgRec)
辅助函数 FindNeighborhood 获取 neighbors

举例看下 Plan（AccessPath）和 SQL 的关系

最初生成 Iterator 执行器框架须要的 Iterator 执行载体，AccessPath 和 Iterator 是一对一的关系（Access paths are a query planning structure that correspond 1:1 to iterators）。

Query_expression::m_root_iterator = CreateIteratorFromAccessPath(......)
unique_ptr_destroy_only<RowIterator> CreateIteratorFromAccessPath(THD *thd, AccessPath *path, JOIN *join, bool eligible_for_batch_mode) {
......
   switch (path->type) {
     case AccessPath::TABLE_SCAN: {const auto &param = path->table_scan();
       iterator = NewIterator<TableScanIterator>(thd, param.table, path->num_output_rows, examined_rows);
       break;
     }
     case AccessPath::INDEX_SCAN: {const auto &param = path->index_scan();
       if (param.reverse) {
         iterator = NewIterator<IndexScanIterator<true>>(
             thd, param.table, param.idx, param.use_order, path->num_output_rows,
             examined_rows);
       } else {
         iterator = NewIterator<IndexScanIterator<false>>(
             thd, param.table, param.idx, param.use_order, path->num_output_rows,
             examined_rows);
       }
       break;
     }
     case AccessPath::REF: {......}

比照 PostgreSQL

testdb=# EXPLAIN SELECT * FROM tbl_a WHERE id < 300 ORDER BY data;
                          QUERY PLAN                           
---------------------------------------------------------------
 Sort  (cost=182.34..183.09 rows=300 width=8)
   Sort Key: data
   ->  Seq Scan on tbl_a  (cost=0.00..170.00 rows=300 width=8)
         Filter: (id < 300)
(4 rows)

总结

本文次要 focus 在 MySQL 最新版本官网的源码上，重点剖析了官网的重构在多阶段和各阶段构造上的变动和分割，更多的是为了让大家理解一个全新的 MySQL 的倒退。最初这里贴几张官网 youtube 介绍的 refactor 的工作内容。

Refactoring: Separating stages

• Started ~10 years ago

Finished a few years ago

• A clear separation between query processing stages
• Fixed a large number of bugs

Improved stability

• Faster feature devlopment

Fewer surprises and complications during development

Refactoring: Parsing and preparing

• Still ongoing

Implemented piece by piece

• Separating parsing and resolving stages

Elimiating semantic actions that do too much 

Get a true bottom-up parser

• Makes it easier to extend with new SQL syntax

Parsing doesn’t have unintented side effects

• Condistent name and type resolving

Names resolved top-down

Types resolved bottom-up

• Transformations done in the prepare stage

Bottom-up

Refactoring: Execution

• Volcano iterator model
• Possible because stages were separated
• Done silently in 8.0 oever the last two years
• Much more modular executor

Common iterator interface for all iterators

Each operation is contained within an iterator

• Able to put plans together in new ways

Immediate benefix: Remove some instances of teamporary tables

• Join is just an iterator

Nested loop join is just an interator

Hash join is just another iterator

Your favourite join method is just another iterator

Old vs current executor

# 参考资料

《Refactoring Query Processing in MySQL (Norvald H. Ryeng, Oracle)》

《Dynamic Programming Strikes Back – MySQL8.0 的新优化器》

《The Internals of PostgreSQL Chapter 3 Query Processing》

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