今天也沒啥講的涌哲，就跟大家一起探索一下MySQL編譯器。
數(shù)據(jù)庫系統(tǒng)能夠接受SQL語句尚镰，并返回數(shù)據(jù)查詢的結(jié)果阀圾，或者對數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行修改，可以說幾乎每個程序員都使用過它狗唉。
而MySQL又是目前使用最廣泛的數(shù)據(jù)庫初烘。所以，解析一下MySQL編譯并執(zhí)行SQL語句的過程，一方面能幫助你加深對數(shù)據(jù)庫領(lǐng)域的編譯技術(shù)的理解肾筐；另一方面哆料，由于SQL是一種最成功的DSL（特定領(lǐng)域語言），所以理解了MySQL編譯器的內(nèi)部運作機(jī)制吗铐，也能加深你對所有使用數(shù)據(jù)操作類DSL的理解剧劝，比如文檔數(shù)據(jù)庫的查詢語言。另外抓歼，解讀SQL與它的運行時的關(guān)系讥此，也有助于你在自己的領(lǐng)域成功地使用DSL技術(shù)。
那么谣妻，數(shù)據(jù)庫系統(tǒng)是如何使用編譯技術(shù)的呢萄喳？接下來，我就會花兩講的時間蹋半，帶你進(jìn)入到MySQL的內(nèi)部他巨，做一次全面的探秘。
今天這一講减江，我先帶你了解一下如何跟蹤MySQL的運行染突，了解它處理一個SQL語句的過程，以及MySQL在詞法分析和語法分析方面的實現(xiàn)機(jī)制辈灼。
好份企，讓我們開始吧！
編譯并調(diào)試MySQL’
按照慣例巡莹，你要下載MySQL的源代碼司志。我下載的是8.0版本的分支。
源代碼里的主要目錄及其作用如下降宅，我們需要分析的代碼基本都在sql目錄下骂远，它包含了編譯器和服務(wù)端的核心組件。
MySQL的源代碼主要是.cc結(jié)尾的腰根，也就是說激才，MySQL主要是用C++編寫的。另外额嘿，也有少量幾個代碼文件是用C語言編寫的瘸恼。
為了跟蹤MySQL的執(zhí)行過程，你要用Debug模式編譯MySQL岩睁，具體步驟可以參考這篇開發(fā)者文檔钞脂。
如果你用單線程編譯揣云，大約需要1個小時捕儒。編譯好以后，先初始化出一個數(shù)據(jù)庫來：
./mysqld --initialize --user=mysql
這個過程會為root@localhost用戶，生成一個缺省的密碼刘莹。
接著阎毅，運行MySQL服務(wù)器：
./mysqld &
之后，通過客戶端連接數(shù)據(jù)庫服務(wù)器点弯，這時我們就可以執(zhí)行SQL了：
./mysql -uroot -p #連接mysql server
最后扇调，我們把GDB調(diào)試工具附加到mysqld進(jìn)程上，就可以對它進(jìn)行調(diào)試了抢肛。
gdb -p `pidof mysqld` #pidof是一個工具狼钮，用于獲取進(jìn)程的id，你可以安裝一下
提示：這一講中捡絮，我是采用了一個CentOS 8的虛擬機(jī)來編譯和調(diào)試MySQL熬芜。我也試過在macOS下編譯，并用LLDB進(jìn)行調(diào)試福稳，也一樣方便涎拉。
注意，你在調(diào)試程序的時候的圆，有兩個設(shè)置斷點的好地方：
● dispatch_command：在sql/sql_parse.cc文件里鼓拧。在接受客戶端請求的時候（比如一個SQL語句），會在這里集中處理越妈。
● my_message_sql：在sql/mysqld.cc文件里季俩。當(dāng)系統(tǒng)需要輸出錯誤信息的時候，會在這里集中處理梅掠。
這個時候种玛，我們在MySQL的客戶端輸入一個查詢命令，就可以從雇員表里查詢姓和名了瓤檐。在這個例子中赂韵，我采用的數(shù)據(jù)庫是MySQL的一個示例數(shù)據(jù)庫employees，你可以根據(jù)它的文檔來生成示例數(shù)據(jù)庫挠蛉。
mysql> select first_name, last_name from employees; #從mysql庫的user表中查詢信息
這個命令被mysqld接收到以后祭示，就會觸發(fā)斷點，并停止執(zhí)行谴古。這個時候质涛，客戶端也會老老實實地停在那里欢嘿，等候從服務(wù)端傳回數(shù)據(jù)瞧预。即使你在后端跟蹤代碼的過程會花很長的時間撰糠，客戶端也不會超時参萄，一直在安靜地等待匿刮。給我的感覺就是典蜕，MySQL對于調(diào)試程序還是很友好的笤喳。
在GDB中輸入bt命令间校，會打印出調(diào)用棧，這樣你就能了解一個SQL語句教寂，在MySQL中執(zhí)行的完整過程捏鱼。為了方便你理解和復(fù)習(xí)，這里我整理成了一個表格：
我也把MySQL執(zhí)行SQL語句時的一些重要程序入口記錄了下來酪耕，這也需要你重點關(guān)注导梆。它反映了執(zhí)行SQL過程中的一些重要的處理階段，包括語法分析迂烁、處理上下文看尼、引用消解、優(yōu)化和執(zhí)行盟步。你在這些地方都可以設(shè)置斷點狡忙。
好了，現(xiàn)在你就已經(jīng)做好準(zhǔn)備址芯，能夠分析MySQL的內(nèi)部實現(xiàn)機(jī)制了灾茁。不過，由于MySQL執(zhí)行的是SQL語言谷炸，它跟我們前面分析的高級語言有所不同北专。所以，我們先稍微回顧一下SQL語言的特點旬陡。
SQL語言：數(shù)據(jù)庫領(lǐng)域的DSL
SQL是結(jié)構(gòu)化查詢語言（Structural Query Language）的英文縮寫拓颓。舉個例子，這是一個很簡單的SQL語句：
select emp_no, first_name, last_name from employees;
其實在大部分情況下描孟，SQL都是這樣一個一個來做語句執(zhí)行的驶睦。這些語句又分為DML（數(shù)據(jù)操縱語言）和DDL（數(shù)據(jù)定義語言）兩類。前者是對數(shù)據(jù)的查詢匿醒、修改和刪除等操作场航，而后者是用來定義數(shù)據(jù)庫和表的結(jié)構(gòu)（又叫模式）。
我們平常最多使用的是DML廉羔。而DML中溉痢，執(zhí)行起來最復(fù)雜的是select語句。所以憋他，在本講孩饼，我都是用select語句來給你舉例子。
那么竹挡，SQL跟我們前面分析的高級語言相比有什么不同呢镀娶？
第一個特點：SQL是聲明式（Declarative）的。這是什么意思呢揪罕？其實就是說梯码，SQL語句能夠表達(dá)它的計算邏輯宝泵，但它不需要描述控制流。
高級語言一般都有控制流忍些，也就是詳細(xì)規(guī)定了實現(xiàn)一個功能的流程：先調(diào)用什么功能鲁猩，再調(diào)用什么功能坎怪，比如if語句罢坝、循環(huán)語句等等。這種方式叫做命令式（imperative）編程搅窿。
更深入一點嘁酿，聲明式編程說的是“要什么”，它不關(guān)心實現(xiàn)的過程男应；而命令式編程強(qiáng)調(diào)的是“如何做”闹司。前者更接近人類社會的領(lǐng)域問題，而后者更接近計算機(jī)實現(xiàn)沐飘。
第二個特點：SQL是一種特定領(lǐng)域語言（DSL游桩，Domain Specific Language），專門針對關(guān)系數(shù)據(jù)庫這個領(lǐng)域的耐朴。SQL中的各個元素能夠映射成關(guān)系代數(shù)中的操作術(shù)語借卧，比如選擇、投影筛峭、連接铐刘、笛卡爾積、交集影晓、并集等操作镰吵。它采用的是表、字段挂签、連接等要素疤祭，而不需要使用常見的高級語言的變量、類饵婆、函數(shù)等要素画株。
所以，SQL就給其他DSL的設(shè)計提供了一個很好的參考：
● 采用聲明式啦辐，更加貼近領(lǐng)域需求谓传。比如，你可以設(shè)計一個報表的DSL芹关，這個DSL只需要描述報表的特征续挟，而不需要描述其實現(xiàn)過程。
● 采用特定領(lǐng)域的模型侥衬、術(shù)語诗祸，甚至是數(shù)學(xué)理論跑芳。比如，針對人工智能領(lǐng)域直颅，你完全就可以用張量計算（力學(xué)概念）的術(shù)語來定義DSL博个。
好了，現(xiàn)在我們分析了SQL的特點功偿，從而也讓你了解了DSL的一些共性特點盆佣。那么接下來，順著MySQL運行的脈絡(luò)械荷，我們先來了解一下MySQL是如何做詞法分析和語法分析的共耍。
詞法和語法分析
詞法分析的代碼是在sql/sql_lex.cc中，入口是MYSQLlex()函數(shù)吨瞎。在sql/lex.h中痹兜，有一個symbols[]數(shù)組，它定義了各類關(guān)鍵字颤诀、操作符字旭。
MySQL的詞法分析器也是手寫的，這給算法提供了一定的靈活性崖叫。比如遗淳，SQL語句中，Token的解析是跟當(dāng)前使用的字符集有關(guān)的归露。使用不同的字符集洲脂，詞法分析器所占用的字節(jié)數(shù)是不一樣的，判斷合法字符的依據(jù)也是不同的剧包。而字符集信息恐锦，取決于當(dāng)前的系統(tǒng)的配置。詞法分析器可以根據(jù)這些配置信息疆液，正確地解析標(biāo)識符和字符串一铅。
MySQL的語法分析器是用bison工具生成的，bison是一個語法分析器生成工具堕油，它是GNU版本的yacc潘飘。bison支持的語法分析算法是LALR算法，而LALR是LR算法家族中的一員掉缺，它能夠支持大部分常見的語法規(guī)則卜录。bison的規(guī)則文件是sql/sql_yacc.yy，經(jīng)過編譯后會生成sql/sql_yacc.cc文件眶明。
sql_yacc.yy中艰毒，用你熟悉的EBNF格式定義了MySQL的語法規(guī)則。我節(jié)選了與select語句有關(guān)的規(guī)則搜囱，如下所示丑瞧，從中你可以體會一下柑土，SQL語句的語法是怎樣被一層一層定義出來的：
select_stmt:
query_expression
| …
| select_stmt_with_into
;
query_expression:
query_expression_body opt_order_clause opt_limit_clause
| with_clause query_expression_body opt_order_clause opt_limit_clause
| …
;
query_expression_body:
query_primary
| query_expression_body UNION_SYM union_option query_primary
| …
;
query_primary:
query_specification
| table_value_constructor
| explicit_table
;
query_specification:
…
| SELECT_SYM /*select關(guān)鍵字*/
select_options /*distinct等選項*/
select_item_list /*select項列表*/
opt_from_clause /*可選：from子句*/
opt_where_clause /*可選：where子句*/
opt_group_clause /*可選：group子句*/
opt_having_clause /*可選：having子句*/
opt_window_clause /*可選：window子句*/
;
…
其中，query_expression就是一個最基礎(chǔ)的select語句绊汹，它包含了SELECT關(guān)鍵字稽屏、字段列表、from子句西乖、where子句等狐榔。
你可以看一下select_options、opt_from_clause和其他幾個以opt開頭的規(guī)則浴栽，它們都是SQL語句的組成部分荒叼。opt是可選的意思轿偎，也就是它的產(chǎn)生式可能產(chǎn)生ε典鸡。
opt_from_clause:
/* Empty. */
| from_clause
;
另外，你還可以看一下表達(dá)式部分的語法坏晦。在MySQL編譯器當(dāng)中萝玷，對于二元運算，你可以大膽地寫成左遞歸的文法昆婿。因為它的語法分析的算法用的是LALR球碉，這個算法能夠自動處理左遞歸。
一般研究表達(dá)式的時候仓蛆，我們總是會關(guān)注編譯器是如何處理結(jié)合性和優(yōu)先級的睁冬。那么，bison是如何處理的呢看疙？
原來豆拨，bison里面有專門的規(guī)則，可以規(guī)定運算符的優(yōu)先級和結(jié)合性能庆。在sql_yacc.yy中施禾，你會看到如下所示的規(guī)則片段：
你可以看一下bit_expr的產(chǎn)生式，它其實完全把加減乘數(shù)等運算符并列就行了搁胆。
bit_expr :
…
| bit_expr '+' bit_expr %prec ‘+’
| bit_expr '-' bit_expr %prec ‘-‘
| bit_expr '*' bit_expr %prec ‘*’
| bit_expr '/' bit_expr %prec ‘/‘
…
| simple_expr
如果你只是用到加減乘除的運算弥搞，那就可以不用在產(chǎn)生式的后面加%prec這個標(biāo)記。但由于加減乘除這幾個還可以用在其他地方渠旁，比如“-a”可以用來表示把a(bǔ)取負(fù)值攀例；減號可以用在一元表達(dá)式當(dāng)中，這會比用在二元表達(dá)式中有更高的優(yōu)先級顾腊。也就是說粤铭，為了區(qū)分同一個Token在不同上下文中的優(yōu)先級，我們可以用%prec投慈，來說明該優(yōu)先級是上下文依賴的承耿。
好了冠骄，在了解了詞法分析器和語法分析器以后，我們接著來跟蹤一下MySQL的執(zhí)行加袋，看看編譯器所生成的解析樹和AST是什么樣子的凛辣。
在sql_class.cc的sql_parser()方法中，編譯器執(zhí)行完解析程序之后职烧，會返回解析樹的根節(jié)點root扁誓，在GDB中通過p命令，可以逐步打印出整個解析樹蚀之。你會看到蝗敢，它的根節(jié)點是一個PT_select_stmt指針（見圖3）。
解析樹的節(jié)點是在語法規(guī)則中規(guī)定的足删，這是一些C++的代碼寿谴，它們會嵌入到語法規(guī)則中去。
下面展示的這個語法規(guī)則就表明失受，編譯器在解析完query_expression規(guī)則以后讶泰，要創(chuàng)建一個PT_query_expression的節(jié)點，其構(gòu)造函數(shù)的參數(shù)分別是三個子規(guī)則所形成的節(jié)點拂到。對于query_expression_body和query_primary這兩個規(guī)則痪署，它們會直接把子節(jié)點返回，因為它們都只有一個子節(jié)點兄旬。這樣就會簡化解析樹狼犯，讓它更像一棵AST。關(guān)于AST和解析樹（也叫CST）的區(qū)別领铐，我在解析Python的編譯器中講過了悯森，你可以回憶一下。
query_expression:
query_expression_body
opt_order_clause
opt_limit_clause
{
$$ = NEW_PTN PT_query_expression($1, $2, $3); /*創(chuàng)建節(jié)點*/
}
| …
query_expression_body:
query_primary
{
$$ = $1; /*直接返回query_primary的節(jié)點*/
}
| …
query_primary:
query_specification
{
$$= $1; /*直接返回query_specification的節(jié)點*/
}
| …
最后罐孝，對于“select first_name, last_name from employees”這樣一個簡單的SQL語句呐馆，它所形成的解析樹如下：
而對于“select 2 + 3”這樣一個做表達(dá)式計算的SQL語句，所形成的解析樹如下莲兢。你會看到汹来，它跟普通的高級語言的表達(dá)式的AST很相似：
圖4中的PT_query_expression等類，就是解析樹的節(jié)點改艇，它們都是Parse_tree_node的子類（PT是Parse Tree的縮寫）收班。這些類主要定義在sql/parse_tree_nodes.h和parse_tree_items.h文件中。
其中谒兄，Item代表了與“值”有關(guān)的節(jié)點摔桦，它的子類能夠用于表示字段、常量和表達(dá)式等。你可以通過Item的val_int()邻耕、val_str()等方法獲取它的值鸥咖。
由于SQL是一個個單獨的語句，所以select兄世、insert啼辣、update等語句，它們都各自有不同的根節(jié)點御滩，都是Parse_tree_root的子類鸥拧。
好了，現(xiàn)在你就已經(jīng)了解了SQL的解析過程和它所生成的AST了削解。前面我說過富弦，MySQL采用的是LALR算法，因此我們可以借助MySQL編譯器氛驮，來加深一下對LR算法家族的理解腕柜。
重溫LR算法
你在閱讀yacc.yy文件的時候，在注釋里柳爽，你會發(fā)現(xiàn)如何跟蹤語法分析器的執(zhí)行過程的一些信息媳握。
你可以用下面的命令碱屁，帶上“-debug”參數(shù)磷脯，來啟動MySQL服務(wù)器：
mysqld --debug="d,parser_debug"
然后，你可以通過客戶端執(zhí)行一個簡單的SQL語句：“select 2+3*5”娩脾。在終端赵誓，會輸出語法分析的過程。這里我截取了一部分界面柿赊，通過這些輸出信息俩功，你能看出LR算法執(zhí)行過程中的移進(jìn)、規(guī)約過程碰声，以及工作區(qū)內(nèi)和預(yù)讀的信息诡蜓。
我來給你簡單地復(fù)現(xiàn)一下這個解析過程。
第1步胰挑，編譯器處于狀態(tài)0蔓罚，并且預(yù)讀了一個select關(guān)鍵字。你已經(jīng)知道瞻颂，LR算法是基于一個DFA的豺谈。在這里的輸出信息中，你能看到某些狀態(tài)的編號達(dá)到了一千多贡这，所以這個DFA還是比較大的茬末。
第2步，把select關(guān)鍵字移進(jìn)工作區(qū)盖矫，并進(jìn)入狀態(tài)42丽惭。這個時候击奶，編譯器已經(jīng)知道后面跟著的一定是一個select語句了，也就是會使用下面的語法規(guī)則：
query_specification:
…
| SELECT_SYM /*select關(guān)鍵字*/
select_options /*distinct等選項*/
select_item_list /*select項列表*/
opt_from_clause /*可選：from子句*/
opt_where_clause /*可選：where子句*/
opt_group_clause /*可選：group子句*/
opt_having_clause /*可選：having子句*/
opt_window_clause /*可選：window子句*/
;
為了給你一個直觀的印象责掏，這里我畫了DFA的局部示意圖（做了一定的簡化）正歼，如下所示。你可以看到拷橘，在狀態(tài)42局义，點符號位于“select”關(guān)鍵字之后、select_options之前冗疮。select_options代表了“distinct”這樣的一些關(guān)鍵字萄唇，但也有可能為空。
第3步术幔，因為預(yù)讀到的Token是一個數(shù)字（NUM）另萤，這說明select_options產(chǎn)生式一定生成了一個ε，因為NUM是在select_options的Follow集合中诅挑。
這就是LALR算法的特點四敞，它不僅會依據(jù)預(yù)讀的信息來做判斷，還要依據(jù)Follow集合中的元素拔妥。所以編譯器做了一個規(guī)約忿危，也就是讓select_options為空。
也就是没龙，編譯器依據(jù)“select_options->ε”做了一次規(guī)約铺厨，并進(jìn)入了新的狀態(tài)920。注意硬纤，狀態(tài)42和920從DFA的角度來看解滓，它們是同一個大狀態(tài)。而DFA中包含了多個小狀態(tài)筝家，分別代表了不同的規(guī)約情況洼裤。
你還需要注意，這個時候溪王，老的狀態(tài)都被壓到了棧里腮鞍，所以棧里會有0和42兩個狀態(tài)。棧里的這些狀態(tài)在扰，其實記錄了推導(dǎo)的過程缕减，讓我們知道下一步要怎樣繼續(xù)去做推導(dǎo)。
第4步芒珠，移進(jìn)NUM桥狡。這時又進(jìn)入一個新狀態(tài)720。
而舊的狀態(tài)也會入棧，記錄下推導(dǎo)路徑：
第5~8步裹芝，依次依據(jù)NUM_literal->NUM部逮、literal->NUM_literal、simple_expr->literal嫂易、bit_expr->simple_expr這四條產(chǎn)生式做規(guī)約兄朋。這時候，編譯器預(yù)讀的Token是+號怜械，所以你會看到颅和，圖中的紅點停在+號前。
第9~10步缕允，移進(jìn)+號和NUM峡扩。這個時候，狀態(tài)又重新回到了720障本。這跟第4步進(jìn)入的狀態(tài)是一樣的教届。
而棧里的目前有5個狀態(tài)，記錄了完整的推導(dǎo)路徑驾霜。
到這里案训，其實你就已經(jīng)了解了LR算法做移進(jìn)和規(guī)約的思路了。不過你還可以繼續(xù)往下研究粪糙。由于棧里保留了完整的推導(dǎo)路徑强霎，因此MySQL編譯器最后會依次規(guī)約回來，把棧里的元素清空猜旬，并且形成一棵完整的AST脆栋。
課程小結(jié)
這一講，我?guī)愠醪教剿髁薓ySQL編譯SQL語句的過程洒擦。你需要記住幾個關(guān)鍵點：
● 掌握如何用GDB來跟蹤MySQL的執(zhí)行的方法。你要特別注意的是怕膛，我給你梳理的那些關(guān)鍵的程序入口熟嫩，它是你理解MySQL運行過程的地圖。
● SQL語言是面向關(guān)系數(shù)據(jù)庫的一種DSL褐捻，它是聲明式的掸茅，并采用了領(lǐng)域特定的模型和術(shù)語，可以為你設(shè)計自己的DSL提供啟發(fā)柠逞。
● MySQL的語法分析器是采用bison工具生成的昧狮。這至少說明，語法分析器生成工具是很有用的板壮，連正式的數(shù)據(jù)庫系統(tǒng)都在使用它逗鸣，所以你也可以大膽地使用它，來提高你的工作效率。我在最后的參考資料中給出了bison的手冊撒璧，希望你能自己閱讀一下透葛，做一些簡單的練習(xí)，掌握bison這個工具卿樱。
● 最后僚害，你一定要知道LR算法的運行原理，知其所以然繁调，這也會更加有助于你理解和用好工具萨蚕。
我依然把本講的內(nèi)容給你整理成了一張知識地圖，供你參考和復(fù)習(xí)回顧：
參考資料
- MySQL的內(nèi)行手冊（MySQL Internals Manual）能提供一些重要的信息蹄胰。但我發(fā)現(xiàn)文檔內(nèi)容經(jīng)常跟源代碼的版本不同步门岔，比如介紹源代碼的目錄結(jié)構(gòu)的信息就過時了，你要注意這點烤送。
