[[409505]]

本文轉(zhuǎn)載自微信公眾號(hào)「捉蟲大師」，作者捉蟲大師。轉(zhuǎn)載本文請(qǐng)聯(lián)系捉蟲大師公眾號(hào)。

背景

Cobar

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

SQL

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

SQL Parser

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

• 通過工具自動(dòng)生成
  • 優(yōu)點(diǎn)：簡(jiǎn)單易于實(shí)現(xiàn)
  • 缺點(diǎn)：性能不佳，二次開發(fā)困難
• 手工編寫
  • 優(yōu)點(diǎn)：性能好，代碼清晰易于擴(kuò)展
  • 缺點(diǎn)：對(duì)開發(fā)人員要求高，需要了解編譯原理

Cobar中也實(shí)現(xiàn)了SQL Parser，它在Cobar中的位置可以從它的架構(gòu)圖中看到： 

SQL Parser之后是SQL Router，可以推斷出SQL Parser解析出AST的目的是為了分庫(kù)分表的路由功能。

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

第一版：基于JavaCC生成SQL parser，性能較差，優(yōu)化不方便

第二版：仿照ANTLR生成的parser結(jié)構(gòu)手寫，中間對(duì)象過多

第三版：基于LL(2)識(shí)別器手寫

本文不對(duì)SQL Parser做過多的介紹，這篇文章我也仔細(xì)閱讀了幾遍，附上總結(jié)的腦圖：

https://github.com/lkxiaolou/reading/tree/main/xmind

Cobar AST

Cobar中的SQL Parser將SQL解析為AST，為了直觀感受，先舉個(gè)例子：

select id,type from goods as g where type in (select type from type_config where status = 0) 

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

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

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

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

實(shí)現(xiàn)這個(gè)ASTNode主要有這幾個(gè)：

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

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

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

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

AST操作

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

其實(shí)是利用了java的多態(tài)，對(duì)每種ASTNode都定義了visit方法，遍歷時(shí)不同對(duì)象對(duì)應(yīng)到不同方法上。

比如MySQLOutputASTVisitor可以遍歷AST，將AST還原為SQL輸出，只需要這樣：

SQLStatement stmt = SQLParserDelegate.parse(sql); 
StringBuilder s = new StringBuilder(); 
stmt.accept(new MySQLOutputASTVisitor(s)); 
System.out.println(s.toString()); 

這樣執(zhí)行會(huì)輸出

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

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

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

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

我們可以參考MySQLOutputASTVisitor編寫符合自己需求的遍歷器。

AST的應(yīng)用

分庫(kù)分表

Cobar中利用AST可以獲取table名、列名、比較的值進(jìn)行分庫(kù)分表，這也是Cobar最重要的功能。

SQL特征生成

除此之外，我了解的AST還可以對(duì)原始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 >= ?

在進(jìn)行SQL慢查詢或其他的統(tǒng)計(jì)、針對(duì)SQL進(jìn)行限流時(shí)非常有用。

危險(xiǎn)SQL攔截

線上寫了一條沒有where條件的update或delete，這時(shí)可以利用AST進(jìn)行表達(dá)式計(jì)算，對(duì)沒有where條件和where條件恒為true的SQL進(jìn)行攔截。

最后 

本文從SQL AST的來(lái)源、結(jié)構(gòu)、遍歷原理、應(yīng)用等方面進(jìn)行介紹，相信看完文章會(huì)對(duì)SQL AST有了初步的了解，如果想進(jìn)一步了解可以參考Cobar項(xiàng)目中的單元測(cè)試進(jìn)行實(shí)際的演示感受。