TiDB 源碼閱讀系列文章（五）TiDB SQL Parser 的實現

本文為 TiDB 源碼閱讀系列文章的第五篇，主要對 SQL Parser 功能的實現進行了講解，內容來自社區小夥伴——馬震（GitHub ID：mz1999 ）的投稿。

TiDB 源碼閱讀系列文章的撰寫初衷，就是希望能與資料庫研究者、愛好者進行深入交流，我們欣喜於如此短的時間內就收到了來自社區的反饋。後續，也希望有更多小夥伴加入到與 TiDB 『坦誠相見』的陣列中來~

PingCAP 發布了 TiDB 的源碼閱讀系列文章，讓我們可以比較系統的去學習了解 TiDB 的內部實現。最近的一篇《SQL 的一生》，從整體上講解了一條 SQL 語句的處理流程，從網路上接收數據，MySQL 協議解析和轉換，SQL 語法解析，查詢計劃的制定和優化，查詢計劃執行，到最後返回結果。

其中，SQL Parser 的功能是把 SQL 語句按照 SQL 語法規則進行解析，將文本轉換成抽象語法樹（AST），這部分功能需要些背景知識才能比較容易理解，我嘗試做下相關知識的介紹，希望能對讀懂這部分代碼有點幫助。

TiDB 是使用 goyacc 根據預定義的 SQL 語法規則文件 parser.y 生成 SQL 語法解析器。我們可以在 TiDB 的 Makefile 文件中看到這個過程，先 build goyacc 工具，然後使用 goyacc 根據 parser.y 生成解析器 parser.go：

goyacc: $(GOBUILD) -o bin/goyacc parser/goyacc/main.goparser: goyacc bin/goyacc -o /dev/null parser/parser.y bin/goyacc -o parser/parser.go parser/parser.y 2>&1 ...

goyacc 是 yacc 的 Golang 版，所以要想看懂語法規則定義文件 parser.y，了解解析器是如何工作的，先要對 Lex & Yacc 有些了解。

Lex & Yacc 介紹

Lex & Yacc 是用來生成詞法分析器和語法分析器的工具，它們的出現簡化了編譯器的編寫。Lex & Yacc 分別是由貝爾實驗室的 Mike Lesk 和 Stephen C. Johnson 在 1975 年發布。對於Java程序員來說，更熟悉的是ANTLR，ANTLR 4 提供了 Listener+Visitor 組合介面， 不需要在語法定義中嵌入actions，使應用代碼和語法定義解耦。Spark的 SQL 解析就是使用了ANTLR。Lex & Yacc 相對顯得有些古老，實現的不是那麼優雅，不過我們也不需要非常深入的學習，只要能看懂語法定義文件，了解生成的解析器是如何工作的就夠了。我們可以從一個簡單的例子開始：

上圖描述了使用 Lex & Yacc 構建編譯器的流程。Lex 根據用戶定義的 patterns 生成詞法分析器。詞法分析器讀取源代碼，根據 patterns 將源代碼轉換成 tokens 輸出。Yacc 根據用戶定義的語法規則生成語法分析器。語法分析器以詞法分析器輸出的tokens作為輸入，根據語法規則創建出語法樹。最後對語法樹遍歷生成輸出結果，結果可以是產生機器代碼，或者是邊遍歷 AST 邊解釋執行。

從上面的流程可以看出，用戶需要分別為 Lex 提供 patterns 的定義，為 Yacc 提供語法規則文件，Lex & Yacc 根據用戶提供的輸入文件，生成符合他們需求的詞法分析器和語法分析器。這兩種配置都是文本文件，並且結構相同：

... definitions ...%%... rules ...%%... subroutines ...

文件內容由 %% 分割成三部分，我們重點關注中間規則定義部分。對於上面的例子，Lex 的輸入文件如下：

...%%/* 變數 */[a-z] { yylval = *yytext - a; return VARIABLE; } /* 整數 */[0-9]+ { yylval = atoi(yytext); return INTEGER; }/* 操作符 */[-+()=/*
] { return *yytext; }/* 跳過空格 */[ ] ;/* 其他格式報錯 */. yyerror("invalid character");%%...

上面只列出了規則定義部分，可以看出該規則使用正則表達式定義了變數、整數和操作符等幾種 token。例如整數 token 的定義如下：

[0-9]+ { yylval = atoi(yytext); return INTEGER; }

當輸入字元串匹配這個正則表達式，大括弧內的動作會被執行：將整數值存儲在變數 yylval 中，並返回 token 類型 INTEGER 給 Yacc。

再來看看 Yacc 語法規則定義文件：

%token INTEGER VARIABLE%left + -%left * /...%%program: program statement
| ;statement: expr { printf("%d
", $1); } | VARIABLE = expr { sym[$1] = $3; } ; expr: INTEGER | VARIABLE { $$ = sym[$1]; } | expr + expr { $$ = $1 + $3; } | expr - expr { $$ = $1 - $3; } | expr * expr { $$ = $1 * $3; } | expr / expr { $$ = $1 / $3; } | ( expr ) { $$ = $2; } ;%%...

第一部分定義了 token 類型和運算符的結合性。四種運算符都是左結合，同一行的運算符優先順序相同，不同行的運算符，後定義的行具有更高的優先順序。

語法規則使用了BNF定義。BNF 可以用來表達上下文無關（context-free）語言，大部分的現代編程語言都可以使用 BNF 表示。上面的規則定義了三個產生式。產生式冒號左邊的項（例如 statement）被稱為非終結符， INTEGER 和 VARIABLE 被稱為終結符,它們是由 Lex 返回的 token 。終結符只能出現在產生式的右側。可以使用產生式定義的語法生成表達式：

expr -> expr * expr -> expr * INTEGER -> expr + expr * INTEGER -> expr + INTEGER * INTEGER -> INTEGER + INTEGER * INTEGER

解析表達式是生成表達式的逆向操作，我們需要歸約表達式到一個非終結符。Yacc 生成的語法分析器使用自底向上的歸約（shift-reduce）方式進行語法解析，同時使用堆棧保存中間狀態。還是看例子，表達式 x + y * z 的解析過程：

1 . x + y * z2 x . + y * z3 expr . + y * z4 expr + . y * z5 expr + y . * z6 expr + expr . * z7 expr + expr * . z8 expr + expr * z .9 expr + expr * expr .10 expr + expr .11 expr .12 statement .13 program .

點（.）表示當前的讀取位置，隨著 . 從左向右移動，我們將讀取的 token壓入堆棧，當發現堆棧中的內容匹配了某個產生式的右側，則將匹配的項從堆棧中彈出，將該產生式左側的非終結符壓入堆棧。這個過程持續進行，直到讀取完所有的 tokens，並且只有啟始非終結符（本例為 program）保留在堆棧中。

產生式右側的大括弧中定義了該規則關聯的動作，例如：

expr: expr * expr { $$ = $1 * $3; }

我們將堆棧中匹配該產生式右側的項替換為產生式左側的非終結符，本例中我們彈出 expr * expr，然後把 expr 壓回堆棧。 我們可以使用 $position 的形式訪問堆棧中的項，$1 引用的是第一項，$2 引用的是第二項，以此類推。$$ 代表的是歸約操作執行後的堆棧頂。本例的動作是將三項從堆棧中彈出，兩個表達式相加，結果再壓回堆棧頂。

上面例子中語法規則關聯的動作，在完成語法解析的同時，也完成了表達式求值。一般我們希望語法解析的結果是一棵抽象語法樹（AST），可以這麼定義語法規則關聯的動作：

...%%...expr: INTEGER { $$ = con($1); } | VARIABLE { $$ = id($1); } | expr + expr { $$ = opr(+, 2, $1, $3); } | expr - expr { $$ = opr(-, 2, $1, $3); } | expr * expr { $$ = opr(*, 2, $1, $3); } | expr / expr { $$ = opr(/, 2, $1, $3); } | ( expr ) { $$ = $2; } ; %%nodeType *con(int value) { ...}nodeType *id(int i) { ...}nodeType *opr(int oper, int nops, ...) { ...}

上面是一個語法規則定義的片段，我們可以看到，每個規則關聯的動作不再是求值，而是調用相應的函數，該函數會返回抽象語法樹的節點類型 nodeType，然後將這個節點壓回堆棧，解析完成時，我們就得到了一顆由 nodeType 構成的抽象語法樹。對這個語法樹進行遍歷訪問，可以生成機器代碼，也可以解釋執行。

至此，我們大致了解了Lex & Yacc的原理。其實還有非常多的細節，例如如何消除語法的歧義，但我們的目的是讀懂 TiDB 的代碼，掌握這些概念已經夠用了。

goyacc 簡介

goyacc 是 golang 版的 Yacc。和 Yacc的功能一樣，goyacc 根據輸入的語法規則文件，生成該語法規則的 go 語言版解析器。goyacc 生成的解析器 yyParse 要求詞法分析器符合下面的介面：

type yyLexer interface { Lex(lval *yySymType) int Error(e string)}

或者

type yyLexerEx interface { yyLexer // Hook for recording a reduction. Reduced(rule, state int, lval *yySymType) (stop bool) // Client should copy *lval.}

TiDB 沒有使用類似 Lex 的工具生成詞法分析器，而是純手工打造，詞法分析器對應的代碼是 parser/lexer.go， 它實現了 goyacc 要求的介面：

...// Scanner implements the yyLexer interface.type Scanner struct { r reader buf bytes.Buffer errs []error stmtStartPos int // For scanning such kind of comment: /*! MySQL-specific code */ or /*+ optimizer hint */ specialComment specialCommentScanner sqlMode mysql.SQLMode}// Lex returns a token and store the token value in v.// Scanner satisfies yyLexer interface.// 0 and invalid are special token id this function would return:// return 0 tells parser that scanner meets EOF,// return invalid tells parser that scanner meets illegal character.func (s *Scanner) Lex(v *yySymType) int { tok, pos, lit := s.scan() v.offset = pos.Offset v.ident = lit ...}// Errors returns the errors during a scan.func (s *Scanner) Errors() []error { return s.errs}

另外lexer 使用了字典樹技術進行 token 識別，具體的實現代碼在 parser/misc.go

TiDB SQL Parser 的實現

終於到了正題。有了上面的背景知識，對 TiDB 的 SQL Parser 模塊會相對容易理解一些。TiDB 的詞法解析使用的 手寫的解析器（這是出於性能考慮），語法解析採用 goyacc。先看 SQL 語法規則文件 parser.y，goyacc 就是根據這個文件生成 SQL 語法解析器的。

parser.y 有 6500 多行，第一次打開可能會被嚇到，其實這個文件仍然符合我們上面介紹過的結構：

... definitions ...%%... rules ...%%... subroutines ...

parser.y 第三部分 subroutines 是空白沒有內容的， 所以我們只需要關注第一部分 definitions 和第二部分 rules。

第一部分主要是定義token的類型、優先順序、結合性等。注意 union 這個聯合體結構體：

%union { offset int // offset item interface{} ident string expr ast.ExprNode statement ast.StmtNode}

該聯合體結構體定義了在語法解析過程中被壓入堆棧的項的屬性和類型。

壓入堆棧的項可能是終結符，也就是 token，它的類型可以是item 或 ident；

這個項也可能是非終結符，即產生式的左側，它的類型可以是 expr 、 statement 、 item 或 ident。

goyacc 根據這個 union 在解析器里生成對應的 struct 是：

type yySymType struct { yys int offset int // offset item interface{} ident string expr ast.ExprNode statement ast.StmtNode}

在語法解析過程中，非終結符會被構造成抽象語法樹（AST）的節點 ast.ExprNode 或 ast.StmtNode。抽象語法樹相關的數據結構都定義在 ast 包中，它們大都實現了 ast.Node 介面：

// Node is the basic element of the AST.// Interfaces embed Node should have Node name suffix.type Node interface { Accept(v Visitor) (node Node, ok bool) Text() string SetText(text string)}

這個介面有一個 Accept 方法，接受 Visitor 參數，後續對 AST 的處理，主要依賴這個 Accept 方法，以 Visitor 模式遍歷所有的節點以及對 AST 做結構轉換。

// Visitor visits a Node.type Visitor interface { Enter(n Node) (node Node, skipChildren bool) Leave(n Node) (node Node, ok bool)}

例如 plan.preprocess 是對 AST 做預處理，包括合法性檢查以及名字綁定。

union 後面是對 token 和 非終結符 按照類型分別定義：

/* 這部分的token是 ident類型 */%token <ident> ... add "ADD" all "ALL" alter "ALTER" analyze "ANALYZE" and "AND" as "AS" asc "ASC" between "BETWEEN" bigIntType "BIGINT" .../* 這部分的token是 item 類型 */ %token <item> /*yy:token "1.%d" */ floatLit "floating-point literal" /*yy:token "1.%d" */ decLit "decimal literal" /*yy:token "%d" */ intLit "integer literal" /*yy:token "%x" */ hexLit "hexadecimal literal" /*yy:token "%b" */ bitLit "bit literal" andnot "&^" assignmentEq ":=" eq "=" ge ">=" .../* 非終結符按照類型分別定義 */%type <expr> Expression "expression" BoolPri "boolean primary expression" ExprOrDefault "expression or default" PredicateExpr "Predicate expression factor" SetExpr "Set variable statement values expression" ...%type <statement> AdminStmt "Check table statement or show ddl statement" AlterTableStmt "Alter table statement" AlterUserStmt "Alter user statement" AnalyzeTableStmt "Analyze table statement" BeginTransactionStmt "BEGIN TRANSACTION statement" BinlogStmt "Binlog base64 statement" ... %type <item> AlterTableOptionListOpt "alter table option list opt" AlterTableSpec "Alter table specification" AlterTableSpecList "Alter table specification list" AnyOrAll "Any or All for subquery" Assignment "assignment" ...%type <ident> KeyOrIndex "{KEY|INDEX}" ColumnKeywordOpt "Column keyword or empty" PrimaryOpt "Optional primary keyword" NowSym "CURRENT_TIMESTAMP/LOCALTIME/LOCALTIMESTAMP" NowSymFunc "CURRENT_TIMESTAMP/LOCALTIME/LOCALTIMESTAMP/NOW" ...

第一部分的最後是對優先順序和結合性的定義：

...%precedence sqlCache sqlNoCache%precedence lowerThanIntervalKeyword%precedence interval%precedence lowerThanStringLitToken%precedence stringLit...%right assignmentEq%left pipes or pipesAsOr%left xor%left andand and%left between...

parser.y文件的第二部分是SQL語法的產生式和每個規則對應的 aciton 。SQL 語法非常複雜，parser.y 的大部分內容都是產生式的定義。

SQL 語法可以參照 MySQL 參考手冊的 SQL Statement Syntax 部分，例如 SELECT 語法的定義如下：

SELECT [ALL | DISTINCT | DISTINCTROW ] [HIGH_PRIORITY] [STRAIGHT_JOIN] [SQL_SMALL_RESULT] [SQL_BIG_RESULT] [SQL_BUFFER_RESULT] [SQL_CACHE | SQL_NO_CACHE] [SQL_CALC_FOUND_ROWS] select_expr [, select_expr ...] [FROM table_references [PARTITION partition_list] [WHERE where_condition] [GROUP BY {col_name | expr | position} [ASC | DESC], ... [WITH ROLLUP]] [HAVING where_condition] [ORDER BY {col_name | expr | position} [ASC | DESC], ...] [LIMIT {[offset,] row_count | row_count OFFSET offset}] [PROCEDURE procedure_name(argument_list)] [INTO OUTFILE file_name [CHARACTER SET charset_name] export_options | INTO DUMPFILE file_name | INTO var_name [, var_name]] [FOR UPDATE | LOCK IN SHARE MODE]]

我們可以在 parser.y 中找到 SELECT 語句的產生式：

SelectStmt: "SELECT" SelectStmtOpts SelectStmtFieldList OrderByOptional SelectStmtLimit SelectLockOpt { ... }| "SELECT" SelectStmtOpts SelectStmtFieldList FromDual WhereClauseOptional SelectStmtLimit SelectLockOpt { ... } | "SELECT" SelectStmtOpts SelectStmtFieldList "FROM" TableRefsClause WhereClauseOptional SelectStmtGroup HavingClause OrderByOptional SelectStmtLimit SelectLockOpt { ... }

產生式 SelectStmt 和 SELECT 語法是對應的。

我省略了大括弧中的 action ，這部分代碼會構建出 AST 的 ast.SelectStmt 節點：

type SelectStmt struct { dmlNode resultSetNode // SelectStmtOpts wraps around select hints and switches. *SelectStmtOpts // Distinct represents whether the select has distinct option. Distinct bool // From is the from clause of the query. From *TableRefsClause // Where is the where clause in select statement. Where ExprNode // Fields is the select expression list. Fields *FieldList // GroupBy is the group by expression list. GroupBy *GroupByClause // Having is the having condition. Having *HavingClause // OrderBy is the ordering expression list. OrderBy *OrderByClause // Limit is the limit clause. Limit *Limit // LockTp is the lock type LockTp SelectLockType // TableHints represents the level Optimizer Hint TableHints []*TableOptimizerHint}

可以看出，ast.SelectStmt 結構體內包含的內容和 SELECT 語法也是一一對應的。

其他的產生式也都是根據對應的 SQL 語法來編寫的。從 parser.y 的注釋看到，這個文件最初是用工具從 BNF 轉化生成的，從頭手寫這個規則文件，工作量會非常大。

完成了語法規則文件 parser.y 的定義，就可以使用 goyacc 生成語法解析器：

bin/goyacc -o parser/parser.go parser/parser.y 2>&1

TiDB對 lexer 和 parser.go 進行了封裝，對外提供 parser.yy_parser 進行 SQL 語句的解析：

// Parse parses a query string to raw ast.StmtNode.func (parser *Parser) Parse(sql, charset, collation string) ([]ast.StmtNode, error) { ...}

最後，我寫了一個簡單的例子，使用 TiDB 的 SQL Parser 進行 SQL 語法解析，構建出 進行 SQL語句的解析：sitor 遍歷 AST ：

package mainimport ( "fmt" "github.com/pingcap/tidb/parser" "github.com/pingcap/tidb/ast")type visitor struct{}func (v *visitor) Enter(in ast.Node) (out ast.Node, skipChildren bool) { fmt.Printf("%T
", in) return in, false}func (v *visitor) Leave(in ast.Node) (out ast.Node, ok bool) { return in, true}func main() { sql := "SELECT /*+ TIDB_SMJ(employees) */ emp_no, first_name, last_name " + "FROM employees USE INDEX (last_name) " + "where last_name=Aamodt and gender=F and birth_date > 1960-01-01" sqlParser := parser.New() stmtNodes, err := sqlParser.Parse(sql, "", "") if err != nil { fmt.Printf("parse error:
%v
%s", err, sql) return } for _, stmtNode := range stmtNodes { v := visitor{} stmtNode.Accept(&v) }}

我實現的 visitor 什麼也沒幹，只是輸出了節點的類型。 這段代碼的運行結果如下，依次輸出遍歷過程中遇到的節點類型：

*ast.SelectStmt*ast.TableOptimizerHint*ast.TableRefsClause*ast.Join*ast.TableSource*ast.TableName*ast.BinaryOperationExpr*ast.BinaryOperationExpr*ast.BinaryOperationExpr*ast.ColumnNameExpr*ast.ColumnName*ast.ValueExpr*ast.BinaryOperationExpr*ast.ColumnNameExpr*ast.ColumnName*ast.ValueExpr*ast.BinaryOperationExpr*ast.ColumnNameExpr*ast.ColumnName*ast.ValueExpr*ast.FieldList*ast.SelectField*ast.ColumnNameExpr*ast.ColumnName*ast.SelectField*ast.ColumnNameExpr*ast.ColumnName*ast.SelectField*ast.ColumnNameExpr*ast.ColumnName

了解了 TiDB SQL Parser 的實現，我們就有可能實現 TiDB 當前不支持的語法，例如添加內置函數，也為我們學習查詢計劃以及優化打下了基礎。希望這篇文章對你能有所幫助。

作者介紹： 馬震，金蝶天燕架構師，曾負責中間件、大數據平台的研發，今年轉向了 NewSQL 領域，關注 OLTP/AP 融合，目前在推動金蝶下一代 ERP 引入 TiDB 作為資料庫存儲服務。

推薦閱讀：