简介：本文基于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