拯救DBA！美團SQL解析探索實踐
數據庫作為核心的基礎組件，是需要重點保護的對象。任何一個線上的不慎操作，都有可能給數據庫帶來嚴重的故障，從而給業務造成巨大的損失。
為了避免這種損失，一般會在管理上下功夫。比如為研發人員制定數據庫開發規范；新上線的 SQL，需要 DBA 進行審核；維護操作需要經過領導審批等等。
而且如果希望能夠有效地管理這些措施，需要有效的數據庫培訓，還需要 DBA 細心的進行 SQL 審核。
很多中小型創業公司，可以通過設定規范、進行培訓、完善審核流程來管理數據庫。
隨著美團業務的不斷發展和壯大，上述措施的實施成本越來越高。如何更多的依賴技術手段，來提高效率，越來越受到重視。
業界已有不少基于 MySQL 源碼開發的 SQL 審核、優化建議等工具，極大的減輕了 DBA 的 SQL 審核負擔。
那么我們能否繼續擴展 MySQL 的源碼，來輔助 DBA 和研發人員來進一步提高效率呢？
比如，更全面的 SQL 優化功能；多維度的慢查詢分析；輔助故障分析等。要實現上述功能，其中最核心的技術之一就是 SQL 解析。
現狀與場景
SQL 解析是一項復雜的技術，一般都是由數據庫廠商來掌握，當然也有公司專門提供 SQL 解析的 API。
由于這幾年 MySQL 數據庫中間件的興起，需要支持讀寫分離、分庫分表等功能，就必須從 SQL 中抽出表名、庫名以及相關字段的值。
因此像 Java 語言編寫的 Druid，C 語言編寫的 MaxScale，Go 語言編寫的 Kingshard 等，都會對 SQL 進行部分解析。
而真正把 SQL 解析技術用于數據庫維護的產品較少，主要有如下幾個：
- 美團點評開源的 SQLAdvisor。它基于 MySQL 原生態詞法解析，結合分析 SQL 中的 where 條件、聚合條件、多表 Join 關系給出索引優化建議。
- 去哪兒開源的 Inception。側重于根據內置的規則，對 SQL 進行審核。
- 阿里的 Cloud DBA。根據官方文檔介紹，其也是提供 SQL 優化建議和改寫。
上述產品都有非常合適的應用場景，在業界也被廣泛使用。但是 SQL 解析的應用場景遠遠沒有被充分發掘，比如：
- 基于表粒度的慢查詢報表。比如，一個 Schema 中包含了屬于不同業務線的數據表，那么從業務線的角度來說，其希望提供表粒度的慢查詢報表。
生成 SQL 特征。將 SQL 語句中的值替換成問號，方便 SQL 歸類。雖然可以使用正則表達式實現相同的功能，但是其 Bug 較多，可以參考 pt-query-digest。
- 比如 pt-query-digest 中，會把遇到的數字都替換成“?”，導致無法區別不同數字后綴的表。
- 高危操作確認與規避。比如，DBA 不小心 Drop 數據表，而此類操作，目前還無有效的工具進行回滾，尤其是大表，其后果將是災難性的。
- SQL 合法性判斷。為了安全、審計、控制等方面的原因，美團點評不會讓研發人員直接操作數據庫，而是提供 RDS 服務。
尤其是對于數據變更，需要研發人員的上級主管進行業務上的審批。如果研發人員，寫了一條語法錯誤的 SQL，而 RDS 無法判斷該 SQL 是否合法，就會造成不必要的溝通成本。
因此為了讓所有有需要的業務都能方便的使用 SQL 解析功能，我們認為應該具有如下特性：
- 直接暴露 SQL 解析接口，使用盡量簡單。比如，輸入 SQL，則輸出表名、特征和優化建議。
- 接口的使用不依賴于特定的語言，否則維護和使用的代價太高。比如，以 HTTP 等方式提供服務。
千里之行，始于足下，下面我先介紹下 SQL 的解析原理。
SQL 解析原理
SQL 解析與優化屬于編譯器范疇，和 C 等其他語言的解析沒有本質的區別。
其中分為，詞法分析、語法和語義分析、優化、執行代碼生成。對應到 MySQL 的部分，如下圖：
圖 1：SQL 解析原理
詞法分析
SQL 解析由詞法分析和語法/語義分析兩個部分組成。詞法分析主要是把輸入轉化成一個個 Token。其中 Token 中包含 Keyword（也稱 Symbol）和非 Keyword。
例如，SQL 語句 select username from userinfo，在分析之后，會得到 4 個 Token。
其中有 2 個 Keyword，分別為 select 和 from：
通常情況下，詞法分析可以使用 Flex 來生成，但是 MySQL 并未使用該工具，而是手寫了詞法分析部分（據說是為了效率和靈活性，參考此文）。具體代碼在 sql/lex.h 和 sql/sql_lex.cc 文件中。
MySQL 中的 Keyword 定義在 sql/lex.h 中，如下為部分 Keyword：
- { "&&", SYM(AND_AND_SYM)},
- { "<", SYM(LT)},
- { "<=", SYM(LE)},
- { "<>", SYM(NE)},
- { "!=", SYM(NE)},
- { "=", SYM(EQ)},
- { ">", SYM(GT_SYM)},
- { ">=", SYM(GE)},
- { "<<", SYM(SHIFT_LEFT)},
- { ">>", SYM(SHIFT_RIGHT)},
- { "<=>", SYM(EQUAL_SYM)},
- { "ACCESSIBLE", SYM(ACCESSIBLE_SYM)},
- { "ACTION", SYM(ACTION)},
- { "ADD", SYM(ADD)},
- { "AFTER", SYM(AFTER_SYM)},
- { "AGAINST", SYM(AGAINST)},
- { "AGGREGATE", SYM(AGGREGATE_SYM)},
- { "ALL", SYM(ALL)},
詞法分析的核心代碼在 sql/sql_lex.c 文件中的 MySQLLex→lex_one_Token，有興趣的同學可以下載源碼研究。
語法分析
語法分析就是生成語法樹的過程。這是整個解析過程中最精華，最復雜的部分，不過這部分 MySQL 使用了 Bison 來完成。
即使如此，如何設計合適的數據結構以及相關算法，去存儲和遍歷所有的信息，也是值得在這里研究的。
語法分析樹
SQL 語句：
- select username, ismale from userinfo where age > 20 and level > 5 and 1 = 1
會生成如下語法樹：
圖 2：語法樹
對于未接觸過編譯器實現的同學，肯定會好奇如何才能生成這樣的語法樹。其背后的原理都是編譯器的范疇。
本人也是在學習 MySQL 源碼過程中，閱讀了部分內容。由于編譯器涉及的內容過多，本人經歷和時間有限，不做過多探究。
從工程的角度來說，學會如何使用 Bison 去構建語法樹，來解決實際問題，對我們的工作也許有更大幫助。下面我就以 Bison 為基礎，探討該過程。
MySQL 語法分析樹生成過程
全部的源碼在 sql/sql_yacc.yy 中，在 MySQL 5.6 中有 17K 行左右代碼。這里列出涉及到的 SQL：
- select username, ismale from userinfo where age > 20 and level > 5 and 1 = 1
解析過程的部分代碼摘錄出來。有了 Bison 之后，SQL 解析的難度也沒有想象的那么大，特別是這里給出了解析的脈絡之后。
- select /*select語句入口*/:
- select_init
- {
- LEX *lex= Lex;
- lex->sql_command= SQLCOM_SELECT;
- }
- ;
- select_init:
- SELECT_SYM /*select 關鍵字*/ select_init2
- | '(' select_paren ')' union_opt
- ;
- select_init2:
- select_part2
- {
- LEX *lex= Lex;
- SELECT_LEX * sel= lex->current_select;
- if (lex->current_select->set_braces(0))
- {
- my_parse_error(ER(ER_SYNTAX_ERROR));
- MYSQL_YYABORT;
- }
- if (sel->linkage == UNION_TYPE &&
- sel->master_unit()->first_select()->braces)
- {
- my_parse_error(ER(ER_SYNTAX_ERROR));
- MYSQL_YYABORT;
- }
- }
- union_clause
- ;
- select_part2:
- {
- LEX *lex= Lex;
- SELECT_LEX *sel= lex->current_select;
- if (sel->linkage != UNION_TYPE)
- mysql_init_select(lex);
- lex->current_select->parsing_place= SELECT_LIST;
- }
- select_options select_item_list /*解析列名*/
- {
- Select->parsing_place= NO_MATTER;
- }
- select_into select_lock_type
- ;
- select_into:
- opt_order_clause opt_limit_clause {}
- | into
- | select_from /*from 字句*/
- | into select_from
- | select_from into
- ;
- select_from:
- FROM join_table_list /*解析表名*/ where_clause /*where字句*/ group_clause having_clause
- opt_order_clause opt_limit_clause procedure_analyse_clause
- {
- Select->context.table_list=
- Select->context.first_name_resolution_table=
- Select->table_list.first;
- }
- | FROM DUAL_SYM where_clause opt_limit_clause
- /* oracle compatibility: oracle always requires FROM clause,
- and DUAL is system table without fields.
- Is "SELECT 1 FROM DUAL" any better than "SELECT 1" ?
- Hmmm :) */
- ;
- where_clause:
- /* empty */ { Select->where= 0; }
- | WHERE
- {
- Select->parsing_place= IN_WHERE;
- }
- expr /*各種表達式*/
- {
- SELECT_LEX *select= Select;
- select->where= $3;
- select->parsing_place= NO_MATTER;
- if ($3)
- $3->top_level_item();
- }
- ;
- /* all possible expressions */
- expr:
- | expr and expr %prec AND_SYM
- {
- /* See comments in rule expr: expr or expr */
- Item_cond_and *item1;
- Item_cond_and *item3;
- if (is_cond_and($1))
- {
- item1= (Item_cond_and*) $1;
- if (is_cond_and($3))
- {
- item3= (Item_cond_and*) $3;
- /*
- (X1 AND X2) AND (Y1 AND Y2) ==> AND (X1, X2, Y1, Y2)
- */
- item3->add_at_head(item1->argument_list());
- $$ = $3;
- }
- else
- {
- /*
- (X1 AND X2) AND Y ==> AND (X1, X2, Y)
- */
- item1->add($3);
- $$ = $1;
- }
- }
- else if (is_cond_and($3))
- {
- item3= (Item_cond_and*) $3;
- /*
- X AND (Y1 AND Y2) ==> AND (X, Y1, Y2)
- */
- item3->add_at_head($1);
- $$ = $3;
- }
- else
- {
- /* X AND Y */
- $$ = new (YYTHD->mem_root) Item_cond_and($1, $3);
- if ($$ == NULL)
- MYSQL_YYABORT;
- }
- }
在大家瀏覽上述代碼的過程，會發現 Bison 中嵌入了 C++ 的代碼。通過 C++ 代碼，把解析到的信息存儲到相關對象中。
例如表信息會存儲到 TABLE_LIST 中，order_list 存儲 order by 子句里的信息，where 字句存儲在 Item 中。
有了這些信息，再輔助以相應的算法就可以對 SQL 進行更進一步的處理了。
核心數據結構及其關系
在 SQL 解析中，最核心的結構是 SELECT_LEX，其定義在 sql/sql_lex.h 中。下面僅列出與上述例子相關的部分。
圖 3：SQL 解析樹結構
上面圖示中，列名 username、ismale 存儲在 item_list 中，表名存儲在 table_list 中，條件存儲在 where 中。
其中以 where 條件中的 Item 層次結構最深，表達也較為復雜，如下圖所示：
圖 4：where 條件
SQL 解析應用
為了更深入的了解 SQL 解析器，這里給出 2 個應用 SQL 解析的例子。
無用條件去除
無用條件去除屬于優化器的邏輯優化范疇，可以僅僅根據 SQL 本身以及表結構即可完成，其優化的情況也是較多的，代碼在 sql/sql_optimizer.cc 文件中的 remove_eq_conds 函數。
為了避免過于繁瑣的描述，以及大段代碼的粘貼，這里通過圖來分析以下四種情況：
- 1=1 and (m > 3 and n > 4)
- 1=2 and (m > 3 and n > 4)
- 1=1 or (m > 3 and n > 4)
- 1=2 or (m > 3 and n > 4)
圖 5：無用條件去除 a
圖 6：無用條件去除 b
圖 7：無用條件去除 c
圖 8：無用條件去除 d
如果對其代碼實現有興趣的同學，需要對 MySQL 中的一個重要數據結構 Item 類有所了解。
因為其比較復雜，所以 MySQL 官方文檔，專門介紹了 Item 類。阿里的 MySQL 小組，也有類似的文章。如需更詳細的了解，就需要去查看源碼中 sql/item_* 等文件。
SQL 特征生成
為了確保數據庫，這一系統基礎組件穩定、高效運行，業界有很多輔助系統。比如慢查詢系統、中間件系統。
這些系統采集、收到 SQL 之后，需要對 SQL 進行歸類，以便統計信息或者應用相關策略。歸類時，通常需要獲取 SQL 特征。比如 SQL：
- select username, ismale from userinfo where age > 20 and level > 5；
SQL 特征為：
- select username, ismale from userinfo where age > ? and level > ?
業界著名的慢查詢分析工具 pt-query-digest，通過正則表達式實現這個功能但是這類處理辦法 Bug 較多。接下來就介紹如何使用 SQL 解析，完成 SQL 特征的生成。
SQL特征生成分兩部分組成：
- 生成 Token 數組
- 根據 Token 數組，生成 SQL 特征
首先回顧在詞法解析章節，我們介紹了 SQL 中的關鍵字，并且每個關鍵字都有一個 16 位的整數對應，而非關鍵字統一用 ident 表示，其也對應了一個 16 位整數。如下表：
將一個 SQL 轉換成特征的過程：
在 SQL 解析過程中，可以很方便的完成 Token 數組的生成。而一旦完成 Token 數組的生成，就可以很簡單的完成 SQL 特征的生成。
SQL 特征被廣泛用于各個系統中，比如 pt-query-digest 需要根據特征對 SQL 歸類，然而其基于正則表達式的實現有諸多 Bug。
下面列舉幾個已知 Bug：
學習建議
最近，在對 SQL 解析器和優化器探索的過程中，從一開始的茫然無措到有章可循，也總結了一些心得體會，在這里跟大家分享一下：
- 閱讀相關書籍，書籍能給我們一個系統的認識解析器和優化器的角度。但是該類針對 MySQL 的書籍市面上很少，目前中文作品可以看下《數據庫查詢優化器的藝術：原理解析與SQL性能優化》。
- 閱讀源碼，但是***以某個版本為基礎，比如 MySQL 5.6.23，因為 SQL 解析、優化部分的代碼在不斷變化。尤其是在跨越大的版本時，改動力度大。
- 多使用 GDB 調試，驗證自己的猜測，檢驗閱讀質量。
- 需要寫相關代碼驗證，只有寫出來了才能算真正的掌握。
作者：廣友、金龍、邢帆
簡介：廣友，美團到店綜合事業群資深 MySQL DBA，2012 年畢業于中國科學技術大學，2017 年加入美團點評，長期致力于 MySQL 及周邊工具的研究。
金龍，2014 年加入美團，主要從事相關的數據庫運維、高可用和相關的運維平臺建設。
邢帆，美團 DBA，2017 年研究生畢業后加入美團點評，目前對 MySQL 運維有一定經驗，并編寫了一些自動化腳本。
