背景

Cobar

Cobar是阿里開源的數(shù)據(jù)庫中間件，關(guān)于它的介紹這里不再贅述，可以參考之前的文章《Cobar SQL審計的設(shè)計與實現(xiàn)》

SQL

SQL是一種領(lǐng)域語言（編程語言），常用于關(guān)系型數(shù)據(jù)庫，方便管理結(jié)構(gòu)化數(shù)據(jù)。數(shù)據(jù)庫執(zhí)行SQL時先對SQL進行詞法分析、語法分析、語義分析生成抽象語法樹（Abstract Syntax Tree，簡稱AST），再被優(yōu)化器處理生成執(zhí)行計劃，由執(zhí)行引擎執(zhí)行。

SQL Parser

將SQL解析為AST的解析器叫SQL Parser，開發(fā)這個解析器通常有兩種方式：

通過工具自動生成

優(yōu)點：簡單易于實現(xiàn)
缺點：性能不佳，二次開發(fā)困難

手工編寫

優(yōu)點：性能好，代碼清晰易于擴展
缺點：對開發(fā)人員要求高，需要了解編譯原理

Cobar中也實現(xiàn)了SQL Parser，它在Cobar中的位置可以從它的架構(gòu)圖中看到SQL Parser之后是SQL Router，可以推斷出SQL Parser解析出AST的目的是為了分庫分表的路由功能。

Cobar的SQL Parser也經(jīng)歷了三個版本的迭代，本質(zhì)是性能考慮：

第一版：基于JavaCC生成SQL parser，性能較差，優(yōu)化不方便
第二版：仿照ANTLR生成的parser結(jié)構(gòu)手寫，中間對象過多
第三版：基于LL(2)識別器手寫

本文不對SQL Parser做過多的介紹，有興趣可以參考這篇文章《比開源快30倍的自研SQL Parser設(shè)計與實踐》，這篇文章我也仔細閱讀了幾遍，附上總結(jié)的腦圖：

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)

經(jīng)過Cobar SQL Parser后，生成了如下AST對象：

這個AST的根節(jié)點就是select語句，然后每個屬性都是葉子節(jié)點，葉子節(jié)點的屬性再分出葉子節(jié)點。可能有點繞，需要從代碼層面感受。

AST的Node定義如下，這里只有個accept方法，是為了遍歷這棵樹，暫時不管，后面會說到：

public interface ASTNode {
    void accept(SQLASTVisitor visitor);
}

實現(xiàn)這個ASTNode主要有這幾個：

SQLStatement：SQL語句，比如select、update、insert等語句，體現(xiàn)在上圖的DMLSelectStatement
Expression：表達式，比如and、or、比較等語句，體現(xiàn)在InExpression、ComparisionEqualsExpression、LiteralNumber、Identifier
TableReference：table相關(guān)語句，體現(xiàn)在TableReferences、TableRefFactor

以ComparisionEqualsExpression的實現(xiàn)為例

其中1是比較的左右表達式，2是判斷符，這里是“=”，3是計算該表達式。

evaluationInternal如何實現(xiàn)？其實表達式被結(jié)構(gòu)化和窮舉之后這個問題變得簡單，比如這里只需要取左右的數(shù)值，進行是否相等的比較即可。

AST操作

有了如上對AST的了解，接下來看對AST的操作，最基本的是遍歷，利用ASTNode的accept，需要實現(xiàn)SQLASTVisitor接口，這個SQLASTVisitor定義如下：

其實是利用了java的多態(tài)，對每種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());

這樣執(zhí)行會輸出

SELECT id, type FROM goods AS G WHERE type IN (SELECT type FROM type_config WHERE status = 0)

SQLParserDelegate.parse(sql)解析出來為DMLSelectStatement對象，它的visit方法實現(xiàn)如下：

@Override
public void accept(SQLASTVisitor visitor) {
    visitor.visit(this);
}

再看MySQLOutputASTVisitor的visit(DMLSelectStatement node)實現(xiàn)：代碼比較長，這里就不貼了，總體思路是遇到葉子節(jié)點就直接按格式存入StringBuilder中，否則繼續(xù)調(diào)用相應節(jié)點的accept繼續(xù)遍歷，是一種深度遍歷的思想。

我們可以參考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慢查詢或其他的統(tǒng)計、針對SQL進行限流時非常有用。

危險SQL攔截

線上寫了一條沒有where條件的update或delete，這時可以利用AST進行表達式計算，對沒有where條件和where條件恒為true的SQL進行攔截。

最后

本文從SQL AST的來源、結(jié)構(gòu)、遍歷原理、應用等方面進行介紹，相信看完文章會對SQL AST有了初步的了解，如果想進一步了解可以參考Cobar項目中的單元測試進行實際的演示感受。

搜索關(guān)注微信公眾號"捉蟲大師"，后端技術(shù)分享，架構(gòu)設(shè)計、性能優(yōu)化、源碼閱讀、問題排查、踩坑實踐。

Cobar源碼分析之AST

背景