Introduction: This article is based on the source code of MySQL 8.0.25 for analysis and summary. The MySQL Server layer refers to the optimizer and actuator parts of MySQL. Our understanding of MySQL is based on the 5.6 and 5.7 versions of MySQL, and more on PostgreSQL or traditional databases. However, starting with MySQL 8.0, iterations and refactoring that have continued every three months have led to a qualitative leap in the overall architecture of the MySQL Server tier. Let’s take a look at the latest architecture of MySQL.

The authors | | passenger source ali technology to the public

A background and architecture

This paper is based on the source code of MySQL 8.0.25 for analysis and summary. The MySQL Server layer refers to the optimizer and actuator parts of MySQL. Our understanding of MySQL is based on the 5.6 and 5.7 versions of MySQL, and more on PostgreSQL or traditional databases. However, starting with MySQL 8.0, iterations and refactoring that have continued every three months have led to a qualitative leap in the overall architecture of the MySQL Server tier. Let’s take a look at the latest architecture of MySQL.

We can see that the latest layered architecture of MySQL is not much different from other databases. In addition, it is worth mentioning from the figure that MySQL is now strengthening InnoDB, NDB cluster and the evolution of memory cluster architecture of RAPID(HeatWave Clusters). Next, let’s take a look at the specific details. This time, we do not follow the official Feature implementation and reconstruction order to understand, and this paper prefers to evolve from the perspective of optimizer and actuator process.

MySQL > MySQL > Parser

Starting with the Parser, official MySQL 8.0 rewrites it using Bison to generate a Parser Tree, which is contextualized to generate MySQL’s Abstract Syntax Tree.

MySQL’s abstract syntax tree is a little different from other databases in that it consists of the tricky alternator of SELECT_LEX_UNIT/SELECT_LEX classes, However, these two constructs have been renamed to the standard SELECT_LEX -> Query_block and SELECT_LEX_UNIT -> Query_expression in the latest version. Query_block represents a query block, while Query_expression is a query expression that contains multiple query blocks, including UNION AND/OR blocks (such as SELECT)

FROM t1 union SELECT

SELECT * FROM T1 ORDER BY a LIMIT 10 ORDER BY b LIMIT 5 SELECT * FROM T1 ORDER BY a LIMIT 10

For example, consider a complex nested query:

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

In MySQL, you can express it as follows:

The parsed and transformed syntax tree is still based on the Query_block and Query_expression framework, but some LEVEL Query blocks have been removed or merged, which will not be expanded in detail here.

The MySQL prepare/rewrite phase

Query_expression::prepare->Query_block::prepare

1 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 exist and fill struct with current data.
  • Setup_conds: Resolve WHERE condition and join conditions.
  • Setup_group: Resolve and setup 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.

2 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, orMark the subquery for execution using materialization, orPerform IN->EXISTS transformation, orPerform more/less ALL/ANY -> MIN/MAX rewriteSubstitute 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 possibleprune_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.

To save space, let’s just focus on top_join_list related simple_joins as an example to simplify the process of nesting joins in query_blocks.

3 contrast PostgreSQL

For a clearer understanding of what standard databases do, here are three PostgreSQL processes:

Parser

First, Parser generates a Parse tree from SQL statements.

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

Analyzer/Analyser

The following figure shows how PostgreSQL’s Analyzer/Analyser generates a Query tree from a Parse tree through semantic analysis.

Rewriter

The Rewriter converts the Query Tree according to the rules in the rule system.

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;
Copy the code

The following example shows how a Query tree containing a View can be expanded to a new Query Tree.

sampledb=# SELECT * FROM employees_list;
Copy the code

Iv MySQL Optimize and Planning phase

Next, we enter the process of generating physical plans from logical plans. This article still focuses on the parsing of structures without introducing the details of generation. MySQL used to rely on JOIN and QEP_TAB before 8.0.22. JOIN is the order, method, and execution plan of the specific “table” involved in each Query_block corresponding to QEP_TAB. However, after 8.0.22, the new optimizer algorithm based on Hypergraph successfully abandoned the QEP_TAB structure to express the execution plan of the left deep tree, and directly used HyperNode/HyperEdge graph to express the execution plan.

For example, you can see the different plan display of the left deep tree expressed in data structure and the Bushy Tree expressed in hypergraph structure:

| - > 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 = 0.35 rows = 1 (cost) - > 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)Copy the code

In order to be more compatible with the two optimizers, the new class AccessPath is introduced in mysql8.0.2x, which can be considered as the Plan Tree abstractions by MySQL to understand the decoupling actuator and different optimizers.

The entry of the old optimizer

The old optimizer still joins ::optimize to translate Query blocks into Query Execution Plans (QEP).

In this stage, some logic rewriting is still done. The transformation in this stage can be understood as preparation before cost-based optimization. The detailed steps are as follows:

  • Logical transformationsoptimize_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 optimizationsubstitute_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 generationalloc_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.

Entry to the new optimizer

The new optimizer is disabled by default. You must set optimizer_switch=” hypergraph_Optimizer =on”; To open. FindBestQueryPlan () ¶ FindBestQueryPlan ();

  • Check whether the Query syntax is supported by the new optimizer (CheckSupportedQuery). If it is not supported, error ER_HYPERGRAPH_NOT_SUPPORTED_YET is returned.

  • Change top_JOIN_list to JoinHypergraph. Since Hypergraph is a relatively independent algorithm implementation, the JoinHypergraph structure is used to better wrap the database structure into the concepts of the Edges and nodes of the Hypergraph.

  • By EnumerateAllConnectedPartitions DPhyp algorithm in paper.

  • The CostingReceiver class contains the main logic of past JOIN Planning, including selecting access paths based on cost, evaluating against DPhyp generated subplans, and keeping the subplan with the lowest cost.

  • After get root_path, the treatment group/agg/having/sort/limit. For Group by operation, Hypergraph currently uses the sorting first + streaming aggregation.

For example, consider the relationship between Plan (AccessPath) and SQL:

Finally, generate the Iterator execution vector required by the Iterator executor framework, 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: {
......
}
Copy the code

3 contrast PostgreSQL

testdb=# EXPLAIN SELECT * FROM tbl_a WHERE id < 300 ORDER BY data; The QUERY PLAN -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the 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)Copy the code

Five summarizes

This article mainly focuses on the official source code of the latest version of MySQL, focusing on the analysis of the changes and connections in the structure of the official reconstruction in multiple stages and each stage, more to let everyone understand the development of a new MySQL.

The original link

This article is ali Cloud original content, shall not be reproduced without permission.