MySQL 8.0 Server层最新架构详解
文章目录
简介:本文基于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 ¶m = path->table_scan();
iterator = NewIterator<TableScanIterator>(
thd, param.table, path->num_output_rows, examined_rows);
break;
}
case AccessPath::INDEX_SCAN: {
const auto ¶m = 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
| Old executor<ul><li>Nested loop focused</li><li>Hard to extend</li><li>COde for one operation spread out</li><li>Different interfaces for each operation</li><li>Combination of operations hard coded</li></ul><span class="lake-card-margin-top lake-card-margin-bottom"><img src="https://ucc.alicdn.com/pic/developer-ecology/5d7894314f7e4cc782ce41492736b275.png" class="image lake-drag-image" alt="image.png" title="image.png"></span> | New (current) executor<ul><li>Modular</li><li>Easy to extend</li><li>Each iterator encapsulates on operation</li><li>Same interface for all iterators</li><li>All operations can be connected</li></ul><span class="lake-card-margin-top lake-card-margin-bottom"><img src="https://ucc.alicdn.com/pic/developer-ecology/97e2132d6db84247a0f92c2884f047e2.png" class="image lake-drag-image" alt="image.png" title="image.png"></span> |
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论