[[423091]]

一、背景和架構(gòu)

我們都知道，利用編寫程序來動態(tài)實現(xiàn)我們應(yīng)用所需要的邏輯，從而程序執(zhí)行時得到我們需要的結(jié)果。那么數(shù)據(jù)庫就是一種通過輸入SQL字符串來快速獲取數(shù)據(jù)的應(yīng)用。當然，假設(shè)沒有數(shù)據(jù)庫這種系統(tǒng)應(yīng)用，用程序如何實現(xiàn)呢？我們可能會發(fā)現(xiàn)，即使不管數(shù)據(jù)如何存儲、數(shù)據(jù)是否并發(fā)訪問，仍然需要不斷通過修改程序處理不同應(yīng)用對數(shù)據(jù)的不同請求。比如大數(shù)據(jù)領(lǐng)域，我們通常通過非關(guān)系型數(shù)據(jù)庫的API，實現(xiàn)對數(shù)據(jù)的獲取。然而這種方式雖然入門簡單，但是維護極難，而且通用性不強，即使不斷進行軟件架構(gòu)設(shè)計或者抽象重構(gòu)，仍然需要不斷地變換應(yīng)用，這也是為何非關(guān)系型數(shù)據(jù)庫回頭擁抱數(shù)據(jù)庫SQL優(yōu)化器的原因。

SQL優(yōu)化器本質(zhì)上是一種高度抽象化的數(shù)據(jù)接口的實現(xiàn)，經(jīng)過該設(shè)計，客戶可以使用更通用且易于理解的SQL語言，對數(shù)據(jù)進行操作和處理，而不需要關(guān)注和抽象自己的數(shù)據(jù)接口，極大地解放了客戶的應(yīng)用程序。

本文就來通過圖形解說的方式介紹下MySQL 8.0 SQL優(yōu)化器如何把一個簡單的字符串（SQL），變成數(shù)據(jù)庫執(zhí)行器可以理解的執(zhí)行序列，最終將數(shù)據(jù)返還給客戶。強大的優(yōu)化器是不需要客戶關(guān)注SQL如何寫的更好來更快獲得需要的數(shù)據(jù)，因此優(yōu)化器對原始SQL一定會做一些等價的變化。在 《MySQL 8.0 Server層最新架構(gòu)詳解》 一文中我們重點介紹了MySQL最新版本關(guān)于Server層解析器、優(yōu)化器和執(zhí)行器的總體介紹，包括一些代碼結(jié)構(gòu)和變化的詳細展示，并且通過simple_joins函數(shù)拋磚引玉展示了MySQL優(yōu)化器在邏輯變換中如何簡化嵌套Join的優(yōu)化。本文我們會一步一步帶你進入神奇的優(yōu)化器細節(jié)，詳細了解優(yōu)化器優(yōu)化部分的每個步驟如何改變著一個SQL最終的執(zhí)行。

本文基于最新MySQL8.0.25版本，因為優(yōu)化器轉(zhuǎn)換部分篇幅比較長，我們分成兩篇文章來介紹，第一部分介紹基于基本結(jié)構(gòu)的Setup和Resolve的解析轉(zhuǎn)換過程，第二部分介紹更為復雜的子查詢、分區(qū)表和連接的復雜轉(zhuǎn)換過程，大綱如下：

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.

二、詳細轉(zhuǎn)換過程

轉(zhuǎn)換的整個框架是由Query_expression到Query_block調(diào)用prepare函數(shù)(sql/sql_resolver.cc)并且根據(jù)不同轉(zhuǎn)換規(guī)則的要求自頂向下或者自底向上的過程。

1.傳遞null到j(luò)oin的內(nèi)表列表（propagate_nullability）

prepare開始先要處理nullable table，它指的是table可能包含全為null的row，根據(jù)JOIN關(guān)系（top_join_list）null row可以被傳播。如果能確定一個table為nullable會使得一些優(yōu)化退化，比如access method不能為EQ_REF、outer join不能優(yōu)化為inner join等。

2.解析設(shè)置查詢塊的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調(diào)用之前，每個Query_block的leaf_tables是為0的。

該函數(shù)的作用就是構(gòu)建leaf_tables，包括base tables和derived tables列表，用于后續(xù)的優(yōu)化。setup_tables并不會遞歸調(diào)用，而是只解決本層的tables，并統(tǒng)計出本層derived table的個數(shù)。但是隨后會調(diào)用resolve_placeholder_tables()->resolve_derived()->derived(Query_expression)::prepare->Query_block::prepare來專門遞歸處理derived table對應(yīng)的Query_expression。

接下來我們根據(jù)prepare的調(diào)用順序，繼續(xù)看下針對于derived table處理的函數(shù)resolve_placeholder_tables。

3.解析查詢塊Derived Table、View、Table函數(shù) （resolve_placeholder_tables）

這個函數(shù)用于對derived table、view和table function的處理，如果該table已經(jīng)merged過了，或者是由于使用transform_grouped_to_derived()被調(diào)用到，已經(jīng)決定使用materialized table方式，則直接忽略。

前面已經(jīng)介紹過resolve_derived()的作用，我們重點介紹merge_derived()函數(shù)，merge_derived是改變Query_expression/Query_block框架結(jié)構(gòu)，將derived table或者view合并到到query block中。

merge_derived 處理和合并Derived table

1）merge_derived transformation的先決條件

• 外層query block是否允許merge（allow_merge_derived）

• • 外層query block為nullptr

• • 外層query expression的子查詢?yōu)閚ullptr，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是否已經(jīng)被標記為需要物化materialize，比如創(chuàng)建視圖的方法是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需要多次執(zhí)行時，不支持；

• derived table中如果查詢塊包含SEMI/ANTI-JOIN，并指定STRAIGHT_JOIN時，不支持；

• 如果合并的derived table和現(xiàn)有query block的leaf table count大約 MAX_TABLES時，不支持；

2）merge_derived transformation的轉(zhuǎn)換過程

• 利用derived_table->nested_join結(jié)構(gòu)來輔助處理OUTER JOIN的情況。

• 把derived table中的表merge到NESTED_JOIN結(jié)構(gòu)體（derived_table->merge_underlying_tables()）。

• 將derived table中的所有表連接到父查詢的table_list列表中，同時把derived table從父查詢中刪除。

• 對父查詢的所有相關(guān)數(shù)據(jù)結(jié)構(gòu)進行重新計算（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）。

• 傳播設(shè)置父查詢OPTION_SCHEMA_TABLE（add_base_options()）和如果是外查詢JOIN的內(nèi)表，傳播設(shè)置nullable屬性（propagate_nullability()）。

• 合并derived table的where條件到外查詢中（merge_where()）。

• 建立對derived table需要獲取的列的引用（create_field_translation()）。

• 將Derived table的結(jié)構(gòu)從父查詢中刪除（exclude_level()）。

• 將derived table中的列或者表的重命名合并到父查詢（fix_tables_after_pullout()/repoint_contexts_of_join_nests()）。

• 因為已經(jīng)把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條件，但是不能有g(shù)roup by或聚合函數(shù)

  • 本身并不是有序的

過程簡化為：

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"); 

該優(yōu)化可以通過set optimizer_switch="derived_merge=on/off"來控制。

setup_materialized_derived 設(shè)置物化Derived Table

對于剩下不能采用 merge 算法的 derived table ，會轉(zhuǎn)為materialize 物化方式去處理。但此時只是做一些變量設(shè)置等預處理，實際的物化執(zhí)行是在executor階段執(zhí)行。

• setup_materialized_derived_tmp_table(): 設(shè)置一個臨時表包含物化Derived Table的所有行數(shù)據(jù)。

• check_materialized_derived_query_blocks(): 設(shè)置屬于當前Derived Table所在的查詢塊結(jié)構(gòu)。

trace_derived.add_utf8_table(this) 
       .add("select#", derived->first_query_block()->select_number) 
       .add("materialized", true); 

setup_table_function 處理表函數(shù)

如果 query block 中有 table function，整個過程會處理兩遍。第一遍會跳過 table function 的 table ，第二遍才專門再對table function 的 table 執(zhí)行一遍上述邏輯。這里的考慮應(yīng)該是先 resolve 了外部環(huán)境（相對于table function），因為有可能函數(shù)參數(shù)會有依賴外部的 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）、聚合函數(shù)引用（Item_aggregate_ref）、外查詢列的引用（Item_outer_ref）、subquery 子查詢產(chǎn)生NULL value的引用輔助（Item_ref_null_helper）。

舉例說明比較復雜的Item_outer_ref：

6.對select_fields進行fix_fields()和列權(quán)限檢查（setup_fields）

下圖是比較復雜的帶子查詢的fixed field過程。有些field和表關(guān)聯(lián)，有的要添加相應(yīng)的Item_xxx_ref引用。

7.解析和fixed_fields WHERE條件和Join條件（setup_conds）

setup_join_cond如果有nested_join會遞歸調(diào)用setup_join_cond進行解析和設(shè)置。這里也順帶介紹下simplify_const_condition函數(shù)的作用，如果發(fā)現(xiàn)可以刪除的const Item，則會用Item_func_true/Item_func_false來替代整個的條件，如圖。

8.解析和設(shè)置ROLLUP語句（resolve_rollup）

在數(shù)據(jù)庫查詢語句中，在 GROUP BY 表達式之后加上 WITH ROLLUP 語句，可以使得通過單個查詢語句來實現(xiàn)對數(shù)據(jù)進行不同層級上的分析與統(tǒng)計。

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很簡單就可以實現(xiàn)效果，下面看下rollup在解析過程做了什么樣的轉(zhuǎn)換達到了意想不到的效果。

9.解析和設(shè)置GROUP BY/ORDER BY語句（setup_group/setup_order）

其中一個函數(shù)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的函數(shù)，對相關(guān)Item進行fix_fields。

• remove_redundant_subquery_clause : 對于Table Subquery的表達式，通常是IN/ANY/ALL/EXISTS/etc，如果沒有聚合函數(shù)和Having子句，通常可以考慮刪除不必要的ORDER/DISTINCT/GROUP BY。該函數(shù)支持三種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); 
轉(zhuǎn)化為 => 
select c1 from t1 where t1.c2 in (select c1 from t2); 

• 處理是否可以刪除不必要的distinct語句，刪除的條件就是GROUP BY的列都在SELECT列表中，并且沒有ROLLUP和Window函數(shù)。

is_grouped() && hidden_group_field_count == 0 && olap == UNSPECIFIED_OLAP_TYPE 

例如場景：

SELECT DISTINCT c1, max(c2) from t1 group by c1; 

10.解析和設(shè)置Window函數(shù)（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 | 
+------+--------------+--------+-------------------+ 

執(zhí)行的過程和結(jié)果類似于下圖：

我們看下它在開始Query_block::prepare解析過程做了哪些事情：

select_lex->m_windows 不為空，就調(diào)用  Window::setup_windows1

• 遍歷window函數(shù)列表，調(diào)用resolve_window_ordering來解析m_partition_by和m_order_by

• 處理inter-window的引用關(guān)系（如WINDOW w1 AS (w2), w2 AS (), w3 AS (w1)），但必須是一個有向無環(huán)圖（DAG）

• 重新遍歷檢查是否唯一名字check_unique_name、創(chuàng)建window partition by和window order by的引用items

• 檢查窗口函數(shù)特征（Window::check_window_functions1(THD *thd, _block *select)）

• • 首先判斷的是當前是靜態(tài)窗口還是動態(tài)窗口；靜態(tài)窗口即判斷了 frame 的定義是否有定義上下邊界。 m_static_aggregates  為 true, 意味著是靜態(tài)窗口，同時對每一個分區(qū)都可以進行一次評估。如果  ma_static_aggregates  為 false, 則進一步判斷其滑動窗口使用的是基于范圍還是基于行。  m_row_optimizable  基于行  m_range_optimizable  基于范圍 

• • 獲取聚合函數(shù)作為窗口函數(shù)時候窗口的特殊規(guī)格要求 wfs->check_wf_semantics1(thd, select, &reqs)  這個方法其實就是判斷是不是需要row_buffer作為評估，如果我們只看當前分區(qū)的行無法進行正確的計算不需要，而需要看之后的或者之前的行，就需要使用row_buffer。

三、綜述

本文重點介紹了下優(yōu)化器的基于規(guī)則的其中一部分優(yōu)化，更多的偏重于SQL中的基本操作符，如表、列、函數(shù)、聚合、分組、排序等元素的解析和設(shè)置以及一些顯而易見的結(jié)構(gòu)變化。下一篇文章我們將繼續(xù)介紹子查詢、分區(qū)表和JOIN操作的轉(zhuǎn)換部分，敬請期待。