SQL抽象語法樹及改寫場景應用-有解無憂

1 背景

我們平時會寫各種各樣或簡單或復雜的sql陳述句，提交后就會得到我們想要的結果集，比如sql陳述句，”select * from t_user where user_id > 10;”，意在從表t_user中篩選出user_id大于10的所有記錄，你有沒有想過從一條sql到一個結果集，這中間經歷了多少坎坷呢？

2 SQL引擎

從MySQL、Oracle、TiDB、CK，到Hive、HBase、Spark，從關系型資料庫到大資料計算引擎，他們大都可以借助SQL引擎，實作“接受一條sql陳述句然后回傳查詢結果”的功能，

他們核心的執行邏輯都是一樣的，大致可以通過下面的流程來概括：

中間藍色部分則代表了SQL引擎的基本作業流程，其中的詞法分析和語法分析，則可以引申出“抽象語法樹”的概念，

3 抽象語法樹

3.1 概念

高級語言的決議程序都依賴于決議樹（Parse Tree），抽象語法樹（AST，Abstract Syntax Tree）是忽略了一些決議樹包含的一些語法資訊，剝離掉一些不重要的細節，它是源代碼語法結構的一種抽象表示，以樹狀的形式表現編程語言的結構，樹的每個節點ASTNode都表示原始碼中的一個結構；AST在不同語言中都有各自的實作，

決議的實作程序這里不去深入剖析，重點在于當SQL提交給SQL引擎后，首先會經過詞法分析進行“分詞”操作，然后利用語法決議器進行語法分析并形成AST，

下圖對應的SQL則是“select username,ismale from userInfo where age>20 and level>5 and 1=1”;

這棵抽象語法樹其實就簡單的可以理解為邏輯執行計劃了，它會經過查詢優化器利用一些規則進行邏輯計劃的優化，得到一棵優化后的邏輯計劃樹，我們所熟知的“謂詞下推”、“剪枝”等操作其實就是在這個程序中實作的，得到邏輯計劃后，會進一步轉換成能夠真正進行執行的物理計劃，例如怎么掃描資料，怎么聚合各個節點的資料等，最后就是按照物理計劃來一步一步的執行了，

3.2 ANTLR4

決議（詞法和語法）這一步，很多SQL引擎采用的是ANTLR4工具實作的，ANTLR4采用的是構建G4檔案，里面通過正則運算式、特定語法結構，來描述目標語法，進而在使用時，依賴語法字典一樣的結構，將SQL進行拆解、封裝，進而提取需要的內容，下圖是一個描述SQL結構的G4檔案，

3.3 示例

3.2.1 SQL決議

在java中的實作一次SQL決議，獲取AST并從中提取出表名，

首先引入依賴：

<dependency>
    <groupId>org.antlr</groupId>
    <artifactId>antlr4-runtime</artifactId>
    <version>4.7</version>
</dependency>

在IDEA中安裝ANTLR4插件；

示例1，決議SQL表名，

使用插件將描述MySQL語法的G4檔案，轉換為java類（G4檔案忽略），

類的結構如下：

其中SqlBase是G4檔案名轉換而來，SqlBaseLexer的作用是詞法決議，SqlBaseParser是語法決議，由它生成AST物件，HelloVisitor和HelloListener：進行抽象語法樹的遍歷，一般都會提供這兩種模式，Visitor訪問者模式和Listener監聽器模式，如果想自己定義遍歷的邏輯，可以繼承這兩個介面，實作對應的方法，

讀取表名程序，是重寫SqlBaseBaseVisitor的幾個關鍵方法，其中TableIdentifierContext是表定義的內容；

SqlBaseParser下還有SQL其他“詞語”的定義，對應的就是G4檔案中的各類描述，比如TableIdentifierContext對應的是G4中TableIdentifier的描述，

3.2.2 字串決議

上面的SQL決議程序比較復雜，以一個簡單字串的決議為例，了解一下ANTLR4的邏輯，

1）定義一個字串的語法：Hello.g4

2）使用IDEA插件，將G4檔案決議為java類

3）語法決議類HelloParser，內容就是我們定義的h和world兩個語法規則，里面詳細轉義了G4檔案的內容，

4）HelloBaseVisitor是采用訪問者模式，開放出來的介面，需要自行實作，可以獲取xxxParser中的規則資訊，

5）撰寫測驗類，使用決議器，識別字串“hi abc”：

6）除錯后發現命中規則h，決議為Hi和abc兩部分，

7）如果是SQL的決議，則會一層層的獲取到SQL中的各類關鍵key，

4 SqlParser

利用ANTLR4進行語法決議，是比較底層的實作，因為Antlr4的結果，只是簡單的文法決議，如果要進行更加深入的處理，就需要對Antlr4的結果進行更進一步的處理，以更符合我們的使用習慣，

利用ANTLR4去生成并決議AST的程序，相當于我們在寫rpc框架前，先去實作一個netty，因此在工業生產中，會直接采用已有工具來實作決議，

Java生態中較為流行的SQL Parser有以下幾種（此處摘自網路）：

fdb-sql-parser 是FoundationDB在被Apple收購前開源的SQL Parser，目前已無人維護，
jsqlparser 是基于JavaCC的開源SQL Parser，是General SQL Parser的Java實作版本，
Apache calcite 是一款開源的動態資料管理框架，它具備SQL決議、SQL校驗、查詢優化、SQL生成以及資料連接查詢等功能，常用于為大資料工具提供SQL能力，例如Hive、Flink等，calcite對標準SQL支持良好，但是對傳統的關系型資料方言支持度較差，
alibaba druid 是阿里巴巴開源的一款JDBC資料庫連接池，但其為監控而生的理念讓其天然具有了SQL Parser的能力，其自帶的Wall Filer、StatFiler等都是基于SQL Parser決議的AST，并且支持多種資料庫方言，

Apache Sharding Sphere(原當當Sharding-JDBC，在1.5.x版本后自行實作)、Mycat都是國內目前大量使用的開源資料庫中間件，這兩者都使用了alibaba druid的SQL Parser模塊，并且Mycat還開源了他們在選型時的對比分析Mycat路由新決議器選型分析與結果.