數據庫管理提速：SQL解析的探索與應用
作者介紹
數據庫作為核心的基礎組件，是需要重點保護的對象。任何一個線上的不慎操作，都有可能給數據庫帶來嚴重的故障，從而給業務造成巨大的損失。
為了避免這種損失，一般會在管理上下功夫，比如為研發人員制定數據庫開發規范；新上線的SQL，需要DBA進行審核；維護操作需要經過領導審批等等。而且如果希望能夠有效地管理這些措施，需要有效的數據庫培訓，還需要DBA細心的進行SQL審核。很多中小型創業公司可以通過設定規范、進行培訓、完善審核流程來管理數據庫。
隨著美團點評的業務不斷發展和壯大，上述措施的實施成本越來越高。如何更多的依賴技術手段，來提高效率，越來越受到重視。業界已有不少基于MySQL源碼開發的SQL審核、優化建議等工具，極大的減輕了DBA的SQL審核負擔。那么我們能否繼續擴展MySQL的源碼，來輔助DBA和研發人員來進一步提高效率呢？比如，更全面的SQL優化功能；多維度的慢查詢分析；輔助故障分析等。要實現上述功能，其中最核心的技術之一就是SQL解析。
現狀與場景
SQL解析是一項復雜的技術，一般都是由數據庫廠商來掌握，當然也有公司專門提供SQL解析的API（參考鏈接：http://sqlparser.com/）。
由于這幾年MySQL數據庫中間件的興起，需要支持讀寫分離、分庫分表等功能，就必須從SQL中抽出表名、庫名以及相關字段的值。因此像Java語言編寫的Druid，C語言編寫的MaxScale，Go語言編寫的Kingshard等，都會對SQL進行部分解析。而真正把SQL解析技術用于數據庫維護的產品較少，主要有如下幾個：
-
美團點評開源的SQLAdvisor。它基于MySQL原生態詞法解析，結合分析SQL中的where條件、聚合條件、多表Join關系給出索引優化建議。
參考鏈接：https://github.com/Meituan-Dianping/SQLAdvisor
-
去哪兒開源的Inception。側重于根據內置的規則，對SQL進行審核。
參考鏈接：http://mysql-inception.github.io/inception-document
-
阿里的Cloud DBA。根據官方文檔介紹，其也是提供SQL優化建議和改寫。
參考鏈接：https://yq.aliyun.com/articles/218442
上述產品都有非常合適的應用場景，在業界也被廣泛使用。但是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解析與優化是屬于編譯器范疇，和C語言等其他語言的解析沒有本質的區別。其中分為詞法分析、語法和語義分析、優化、執行代碼生成。對應到MySQL的部分，如下圖：
SQL解析原理
1、詞法分析
SQL解析由詞法分析和語法/語義分析兩個部分組成。詞法分析主要是把輸入轉化成一個個Token。其中Token中包含Keyword（也稱symbol）和非Keyword。例如：SQL語句select username from userinfo，在分析之后，會得到4個Token，其中有2個Keyword，分別為select和from：
通常情況下，詞法分析可以使用Flex來生成。
參考鏈接：https://www.gnu.org/software/flex
但是MySQL并未使用該工具，而是手寫了詞法分析部分（據說是為了效率和靈活性，可參考：https://yq.aliyun.com/articles/71979）。具體代碼在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，有興趣的同學可以下載源碼研究。
2、語法分析
語法分析就是生成語法樹的過程。這是整個解析過程中最精華、最復雜的部分，不過這部分MySQL使用了Bison來完成。即使如此，如何設計合適的數據結構以及相關算法，去存儲和遍歷所有的信息，也是值得在這里研究的。
語法分析樹
SQL語句：
- select username, ismale from userinfo where age > 20 and level > 5 and 1 = 1
會生成如下語法樹：
語法樹
對于未接觸過編譯器實現的同學，肯定會好奇如何才能生成這樣的語法樹，不過其背后的原理都是編譯器的范疇，大家可以參考維基百科的一篇文章，以及該鏈接中的參考書籍。本人也是在學習MySQL源碼過程中，閱讀了部分內容。
參考鏈接：https://en.wikipedia.org/wiki/LR_parser
由于編譯器涉及的內容過多，本人經歷和時間有限，不做過多探究。從工程的角度來說，學會如何使用Bison去構建語法樹，來解決實際問題，對我們的工作也許有更大幫助。下面我就以Bison為基礎，探討該過程。
MySQL語法分析樹生成過程
全部的源碼在sql/sql_yacc.yy中，在MySQL5.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
- 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)
- union_clause
- ;
- select_part2:
- 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))
- X AND (Y1 AND Y2) ==> AND (X, Y1, Y2)
- */ item3->add_at_head($1);
- /* X AND Y */
- $$ = new (YYTHD->mem_root) Item_cond_and($1, $3);
- if ($$ == )
上下拉動可完整查看
在大家瀏覽上述代碼的過程，會發現Bison中嵌入了C++的代碼。通過C++代碼，把解析到的信息存儲到相關對象中。例如表信息會存儲到TABLE_LIST中，order_list存儲order by子句里的信息，where字句存儲在Item中。有了這些信息，再輔助以相應的算法就可以對SQL進行更進一步的處理了。
核心數據結構及其關系
在SQL解析中，最核心的結構是SELECT_LEX，其定義在sql/sql_lex.h中。下面僅列出與上述例子相關的部分。
SQL解析樹結構
上面圖示中，列名username、ismale存儲在item_list中，表名存儲在table_list中，條件存儲在where中。其中以where條件中的Item層次結構最深，表達也較為復雜，如下圖所示：
where條件
SQL解析的應用
為了更深入的了解SQL解析器，這里給出2個應用SQL解析的例子：
1、無用條件去除
“無用條件去除”屬于優化器的邏輯優化范疇，僅僅根據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)
無用條件去除a：
無用條件去除c
無用條件去除d
如果對其代碼實現有興趣的同學，需要對MySQL中的一個重要數據結構Item類有所了解。因為其比較復雜，所以MySQL官方文檔專門介紹了Item類。
參考鏈接：https://dev.mysql.com/doc/internals/en/item-class.html
阿里的MySQL小組也有類似的文章。如需更詳細的了解，就需要去查看源碼中sql/item_*等文件。
2、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性能優化》；
-
其次，要閱讀源碼，但是***以某個版本為基礎，比如MySQL5.6.23，因為SQL解析、優化部分的代碼在不斷變化，尤其是在跨越大的版本時，改動力度大；
-
再次，多使用GDB調試，驗證自己的猜測，檢驗閱讀質量；
-
***，需要寫相關代碼驗證，只有寫出來了才能算真正的掌握。
