一 背景和架構
我們都知道，利用編寫程序來動態實現我們應用所需要的邏輯，從而程序執行時得到我們需要的結果。那么數據庫就是一種通過輸入SQL字符串來快速獲取數據的應用。當然，假設沒有數據庫這種系統應用，用程序如何實現呢？我們可能會發現，即使不管數據如何存儲、數據是否并發訪問，仍然需要不斷通過修改程序處理不同應用對數據的不同請求。比如大數據領域，我們通常通過非關系型數據庫的API，實現對數據的獲取。然而這種方式雖然入門簡單，但是維護極難，而且通用性不強，即使不斷進行軟件架構設計或者抽象重構，仍然需要不斷地變換應用，這也是為何非關系型數據庫回頭擁抱數據庫SQL優化器的原因。
SQL優化器本質上是一種高度抽象化的數據接口的實現，經過該設計，客戶可以使用更通用且易于理解的SQL語言，對數據進行操作和處理，而不需要關注和抽象自己的數據接口，極大地解放了客戶的應用程序。
本文就來通過圖形解說的方式介紹下MySQL 8.0 SQL優化器如何把一個簡單的字符串（SQL），變成數據庫執行器可以理解的執行序列，最終將數據返還給客戶。強大的優化器是不需要客戶關注SQL如何寫的更好來更快獲得需要的數據，因此優化器對原始SQL一定會做一些等價的變化。在《MySQL 8.0 Server層最新架構詳解》一文中我們重點介紹了MySQL最新版本關于Server層解析器、優化器和執行器的總體介紹，包括一些代碼結構和變化的詳細展示，并且通過simple_joins函數拋磚引玉展示了MySQL優化器在邏輯變換中如何簡化嵌套Join的優化。本文我們會一步一步帶你進入神奇的優化器細節，詳細了解優化器優化部分的每個步驟如何改變著一個SQL最終的執行。
本文基于最新MySQL8.0.25版本，因為優化器轉換部分篇幅比較長，我們分成兩篇文章來介紹，第一部分介紹基于基本結構的Setup和Resolve的解析轉換過程，第二部分介紹更為復雜的子查詢、分區表和連接的復雜轉換過程，大綱如下：
Setup and Resolve
二 詳細轉換過程
轉換的整個框架是由Query_expression到Query_block調用prepare函數(sql/sql_resolver.cc)并且根據不同轉換規則的要求自頂向下或者自底向上的過程。
圖片
1 傳遞null到join的內表列表（propagate_nullability）
prepare開始先要處理nullable table，它指的是table可能包含全為null的row，根據JOIN關系（top_join_list）null row可以被傳播。如果能確定一個table為nullable會使得一些優化退化，比如access method不能為EQ_REF、outer join不能優化為inner join等。
2 解析設置查詢塊的leave_tables（setup_tables）
SELECT t1.c1FROM t1, (SELECt t2.c1 FROM t2, (SELECt t3.c1 FROM t3 UNIOn SELECt t4.c1 FROM t4) AS t3a) AS t2a;未在setup_table調用之前，每個Query_block的leaf_tables是為0的。
該函數的作用就是構建leaf_tables，包括base tables和derived tables列表，用于后續的優化。setup_tables并不會遞歸調用，而是只解決本層的tables，并統計出本層derived table的個數。但是隨后會調用resolve_placeholder_tables()->resolve_derived()->derived(Query_expression)::prepare->Query_block::prepare來專門遞歸處理derived table對應的Query_expression。
接下來我們根據prepare的調用順序，繼續看下針對于derived table處理的函數resolve_placeholder_tables。
3 解析查詢塊Derived Table、View、Table函數 （resolve_placeholder_tables）
這個函數用于對derived table、view和table function的處理，如果該table已經merged過了，或者是由于使用transform_grouped_to_derived()被調用到，已經決定使用materialized table方式，則直接忽略。
前面已經介紹過resolve_derived()的作用，我們重點介紹merge_derived()函數，merge_derived是改變Query_expression/Query_block框架結構，將derived table或者view合并到到query block中。
merge_derived 處理和合并Derived table
1）merge_derived transformation的先決條件
2）merge_derived transformation的轉換過程
過程簡化為：
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");該優化可以通過set optimizer_switch="derived_merge=on/off"來控制。
setup_materialized_derived 設置物化Derived Table
對于剩下不能采用 merge 算法的 derived table ，會轉為materialize 物化方式去處理。但此時只是做一些變量設置等預處理，實際的物化執行是在executor階段執行。
trace_derived.add_utf8_table(this) .add("select#", derived->first_query_block()->select_number) .add("materialized", true);setup_table_function 處理表函數
如果 query block 中有 table function，整個過程會處理兩遍。第一遍會跳過 table function 的 table ，第二遍才專門再對table function 的 table 執行一遍上述邏輯。這里的考慮應該是先 resolve 了外部環境（相對于table function），因為有可能函數參數會有依賴外部的 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）、聚合函數引用（Item_aggregate_ref）、外查詢列的引用（Item_outer_ref）、subquery 子查詢產生NULL value的引用輔助（Item_ref_null_helper）。
舉例說明比較復雜的Item_outer_ref：
6 對select_fields進行fix_fields()和列權限檢查（setup_fields）
下圖是比較復雜的帶子查詢的fixed field過程。有些field和表關聯，有的要添加相應的Item_xxx_ref引用。
7 解析和fixed_fields WHERe條件和Join條件（setup_conds）
setup_join_cond如果有nested_join會遞歸調用setup_join_cond進行解析和設置。這里也順帶介紹下simplify_const_condition函數的作用，如果發現可以刪除的const Item，則會用Item_func_true/Item_func_false來替代整個的條件，如圖。
8 解析和設置ROLLUP語句（resolve_rollup）
在數據庫查詢語句中，在 GROUP BY 表達式之后加上 WITH ROLLUP 語句，可以使得通過單個查詢語句來實現對數據進行不同層級上的分析與統計。
SELECT YEAR, country, product, SUM(profit) AS profitFROM salesGROUP 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_tableORDER 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很簡單就可以實現效果，下面看下rollup在解析過程做了什么樣的轉換達到了意想不到的效果。
9 解析和設置GROUP BY/ORDER BY語句（setup_group/setup_order）
其中一個函數find_order_in_list(): 嘗試在select fields里去尋找可以映射的列，否則就得在最后投影的all fields里加上當前列，同時也做fix_fields。
remove_redundant_subquery_clause : 對于Table Subquery的表達式，通常是IN/ANY/ALL/EXISTS/etc，如果沒有聚合函數和Having子句，通常可以考慮刪除不必要的ORDER/DISTINCT/GROUP BY。該函數支持三種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);轉化為 =>select c1 from t1 where t1.c2 in (select c1 from t2);is_grouped() && hidden_group_field_count == 0 && olap == UNSPECIFIED_OLAP_TYPE例如場景：
SELECT DISTINCT c1, max(c2) from t1 group by c1;10 解析和設置Window函數（Window::setup_windows1）
SELECt id, release_year, rating, avg(rating) over(PARTITION BY release_year) AS year_avgFROM 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 |+------+--------------+--------+-------------------+執行的過程和結果類似于下圖：
我們看下它在開始Query_block::prepare解析過程做了哪些事情：
select_lex->m_windows 不為空，就調用 Window::setup_windows1
三 綜述
本文重點介紹了下優化器的基于規則的其中一部分優化，更多的偏重于SQL中的基本操作符，如表、列、函數、聚合、分組、排序等元素的解析和設置以及一些顯而易見的結構變化。下一篇文章我們將繼續介紹子查詢、分區表和JOIN操作的轉換部分，敬請期待。
四 參考資料
五 關于我們
PolarDB 是阿里巴巴自主研發的云原生分布式關系型數據庫，于2020年進入Gartner全球數據庫Leader象限，并獲得了2020年中國電子學會頒發的科技進步一等獎。PolarDB 基于云原生分布式數據庫架構，提供大規模在線事務處理能力，兼具對復雜查詢的并行處理能力，在云原生分布式數據庫領域整體達到了國際領先水平，并且得到了廣泛的市場認可。在阿里巴巴集團內部的最佳實踐中，PolarDB還全面支撐了2020年天貓雙十一，并刷新了數據庫處理峰值記錄，高達1.4億TPS。歡迎有志之士加入我們，簡歷請投遞到daoke.wangc@alibaba-inc，期待與您共同打造世界一流的下一代云原生分布式關系型數據庫。
作者 | 道客
原文鏈接：click.aliyun/m/1000295120/
本文為阿里云原創內容，未經允許不得轉載。
