Cobar源碼分析之AST
本文轉載自微信公眾號「捉蟲大師」，作者捉蟲大師。轉載本文請聯系捉蟲大師公眾號。
背景
Cobar
Cobar是阿里開源的數據庫中間件，關于它的介紹這里不再贅述，可以參考之前的文章《Cobar SQL審計的設計與實現》
SQL
SQL是一種領域語言(編程語言)，常用于關系型數據庫，方便管理結構化數據。數據庫執行SQL時先對SQL進行詞法分析、語法分析、語義分析生成抽象語法樹(Abstract Syntax Tree，簡稱AST)，再被優化器處理生成執行計劃，由執行引擎執行。
SQL Parser
將SQL解析為AST的解析器叫SQL Parser，開發這個解析器通常有兩種方式：
- 通過工具自動生成
- 優點：簡單易于實現
- 缺點：性能不佳，二次開發困難
- 手工編寫
- 優點：性能好，代碼清晰易于擴展
- 缺點：對開發人員要求高，需要了解編譯原理
Cobar中也實現了SQL Parser，它在Cobar中的位置可以從它的架構圖中看到：
SQL Parser之后是SQL Router，可以推斷出SQL Parser解析出AST的目的是為了分庫分表的路由功能。
Cobar的SQL Parser也經歷了三個版本的迭代，本質是性能考慮：
第一版：基于JavaCC生成SQL parser，性能較差，優化不方便
第二版：仿照ANTLR生成的parser結構手寫，中間對象過多
第三版：基于LL(2)識別器手寫
本文不對SQL Parser做過多的介紹，這篇文章我也仔細閱讀了幾遍，附上總結的腦圖：
https://github.com/lkxiaolou/reading/tree/main/xmind
Cobar AST
Cobar中的SQL Parser將SQL解析為AST，為了直觀感受，先舉個例子：
- select id,type from goods as g where type in (select type from type_config where status = 0)
經過Cobar SQL Parser后，生成了如下AST對象：
這個AST的根節點就是select語句，然后每個屬性都是葉子節點，葉子節點的屬性再分出葉子節點。可能有點繞，需要從代碼層面感受。
AST的Node定義如下，這里只有個accept方法，是為了遍歷這棵樹，暫時不管，后面會說到：
- public interface ASTNode {
- void accept(SQLASTVisitor visitor);
- }
實現這個ASTNode主要有這幾個：
- SQLStatement：SQL語句，比如select、update、insert等語句，體現在上圖的DMLSelectStatement
- Expression：表達式，比如and、or、比較等語句，體現在InExpression、ComparisionEqualsExpression、LiteralNumber、Identifier
- TableReference：table相關語句，體現在TableReferences、TableRefFactor
以ComparisionEqualsExpression的實現為例
其中1是比較的左右表達式，2是判斷符，這里是“=”，3是計算該表達式。
evaluationInternal如何實現?其實表達式被結構化和窮舉之后這個問題變得簡單，比如這里只需要取左右的數值，進行是否相等的比較即可。
AST操作
有了如上對AST的了解，接下來看對AST的操作，最基本的是遍歷，利用ASTNode的accept，需要實現SQLASTVisitor接口，這個SQLASTVisitor定義如下：
其實是利用了java的多態，對每種ASTNode都定義了visit方法，遍歷時不同對象對應到不同方法上。
比如MySQLOutputASTVisitor可以遍歷AST，將AST還原為SQL輸出，只需要這樣：
- SQLStatement stmt = SQLParserDelegate.parse(sql);
- StringBuilder s = new StringBuilder();
- stmt.accept(new MySQLOutputASTVisitor(s));
- System.out.println(s.toString());
這樣執行會輸出
SELECT id, type FROM goods AS G WHERE type IN (SELECT type FROM type_config WHERE status = 0)
SQLParserDelegate.parse(sql)解析出來為DMLSelectStatement對象，它的visit方法實現如下：
- @Override
- public void accept(SQLASTVisitor visitor) {
- visitor.visit(this);
- }
再看MySQLOutputASTVisitor的visit(DMLSelectStatement node)實現：代碼比較長，這里就不貼了，總體思路是遇到葉子節點就直接按格式存入StringBuilder中，否則繼續調用相應節點的accept繼續遍歷，是一種深度遍歷的思想。
我們可以參考MySQLOutputASTVisitor編寫符合自己需求的遍歷器。
AST的應用
分庫分表
Cobar中利用AST可以獲取table名、列名、比較的值進行分庫分表，這也是Cobar最重要的功能。
SQL特征生成
除此之外，我了解的AST還可以對原始SQL生成SQL特征，比如原始SQL是這樣：
select id, name, age from user as u where age >= 20
或者是
select id, name, age from user as u where age >= 30
都可以被歸一化為
select id, name, age from user as u where age >= ?
在進行SQL慢查詢或其他的統計、針對SQL進行限流時非常有用。
危險SQL攔截
線上寫了一條沒有where條件的update或delete，這時可以利用AST進行表達式計算，對沒有where條件和where條件恒為true的SQL進行攔截。
最后
本文從SQL AST的來源、結構、遍歷原理、應用等方面進行介紹，相信看完文章會對SQL AST有了初步的了解，如果想進一步了解可以參考Cobar項目中的單元測試進行實際的演示感受。
