SQL抽象語法樹及改寫場(chǎng)景應(yīng)用

我們平時(shí)會(huì)寫各種各樣或簡(jiǎn)單或復(fù)雜的sql語句，提交后就會(huì)得到我們想要的結(jié)果集。比如sql語句，”select * from t_user where user_id > 10;”，意在從表t_user中篩選出user_id大于10的所有記錄。你有沒有想過從一條sql到一個(gè)結(jié)果集，這中間經(jīng)歷了多少坎坷呢？

從MySQL、Oracle、TiDB、CK，到Hive、HBase、Spark，從關(guān)系型數(shù)據(jù)庫(kù)到大數(shù)據(jù)計(jì)算引擎，他們大都可以借助SQL引擎，實(shí)現(xiàn)“接受一條sql語句然后返回查詢結(jié)果”的功能。

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

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

3.1 概念

高級(jí)語言的解析過程都依賴于解析樹（Parse Tree），抽象語法樹（AST，Abstract Syntax Tree）是忽略了一些解析樹包含的一些語法信息，剝離掉一些不重要的細(xì)節(jié)，它是源代碼語法結(jié)構(gòu)的一種抽象表示。以樹狀的形式表現(xiàn)編程語言的結(jié)構(gòu)，樹的每個(gè)節(jié)點(diǎn)ASTNode都表示源碼中的一個(gè)結(jié)構(gòu)；AST在不同語言中都有各自的實(shí)現(xiàn)。

解析的實(shí)現(xiàn)過程這里不去深入剖析，重點(diǎn)在于當(dāng)SQL提交給SQL引擎后，首先會(huì)經(jīng)過詞法分析進(jìn)行“分詞”操作，然后利用語法解析器進(jìn)行語法分析并形成AST。

下圖對(duì)應(yīng)的SQL則是“select username,ismale from userInfo where age>20 and level>5 and 1=1”;

這棵抽象語法樹其實(shí)就簡(jiǎn)單的可以理解為邏輯執(zhí)行計(jì)劃了，它會(huì)經(jīng)過查詢優(yōu)化器利用一些規(guī)則進(jìn)行邏輯計(jì)劃的優(yōu)化，得到一棵優(yōu)化后的邏輯計(jì)劃樹，我們所熟知的“謂詞下推”、“剪枝”等操作其實(shí)就是在這個(gè)過程中實(shí)現(xiàn)的。得到邏輯計(jì)劃后，會(huì)進(jìn)一步轉(zhuǎn)換成能夠真正進(jìn)行執(zhí)行的物理計(jì)劃，例如怎么掃描數(shù)據(jù)，怎么聚合各個(gè)節(jié)點(diǎn)的數(shù)據(jù)等。最后就是按照物理計(jì)劃來一步一步的執(zhí)行了。

3.2 ANTLR4

解析（詞法和語法）這一步，很多SQL引擎采用的是ANTLR4工具實(shí)現(xiàn)的。ANTLR4采用的是構(gòu)建G4文件，里面通過正則表達(dá)式、特定語法結(jié)構(gòu)，來描述目標(biāo)語法，進(jìn)而在使用時(shí)，依賴語法字典一樣的結(jié)構(gòu)，將SQL進(jìn)行拆解、封裝，進(jìn)而提取需要的內(nèi)容。下圖是一個(gè)描述SQL結(jié)構(gòu)的G4文件。

3.3 示例

3.2.1 SQL解析

在java中的實(shí)現(xiàn)一次SQL解析，獲取AST并從中提取出表名。

首先引入依賴：

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

在IDEA中安裝ANTLR4插件；

示例1，解析SQL表名。

使用插件將描述MySQL語法的G4文件，轉(zhuǎn)換為java類（G4文件忽略）。

類的結(jié)構(gòu)如下：

其中SqlBase是G4文件名轉(zhuǎn)換而來，SqlBaseLexer的作用是詞法解析，SqlBaseParser是語法解析，由它生成AST對(duì)象。HelloVisitor和HelloListener：進(jìn)行抽象語法樹的遍歷，一般都會(huì)提供這兩種模式，Visitor訪問者模式和Listener監(jiān)聽器模式。如果想自己定義遍歷的邏輯，可以繼承這兩個(gè)接口，實(shí)現(xiàn)對(duì)應(yīng)的方法。

讀取表名過程，是重寫SqlBaseBaseVisitor的幾個(gè)關(guān)鍵方法，其中TableIdentifierContext是表定義的內(nèi)容；

SqlBaseParser下還有SQL其他“詞語”的定義，對(duì)應(yīng)的就是G4文件中的各類描述。比如TableIdentifierContext對(duì)應(yīng)的是G4中TableIdentifier的描述。

3.2.2 字符串解析

上面的SQL解析過程比較復(fù)雜，以一個(gè)簡(jiǎn)單字符串的解析為例，了解一下ANTLR4的邏輯。

1）定義一個(gè)字符串的語法：Hello.g4

2）使用IDEA插件，將G4文件解析為java類

3）語法解析類HelloParser，內(nèi)容就是我們定義的h和world兩個(gè)語法規(guī)則，里面詳細(xì)轉(zhuǎn)義了G4文件的內(nèi)容。

4）HelloBaseVisitor是采用訪問者模式，開放出來的接口，需要自行實(shí)現(xiàn)，可以獲取xxxParser中的規(guī)則信息。

5）編寫測(cè)試類，使用解析器，識(shí)別字符串“hi abc”：

6）調(diào)試后發(fā)現(xiàn)命中規(guī)則h，解析為Hi和abc兩部分。

利用ANTLR4進(jìn)行語法解析，是比較底層的實(shí)現(xiàn)，因?yàn)锳ntlr4的結(jié)果，只是簡(jiǎn)單的文法解析，如果要進(jìn)行更加深入的處理，就需要對(duì)Antlr4的結(jié)果進(jìn)行更進(jìn)一步的處理，以更符合我們的使用習(xí)慣。

利用ANTLR4去生成并解析AST的過程，相當(dāng)于我們?cè)趯憆pc框架前，先去實(shí)現(xiàn)一個(gè)netty。因此在工業(yè)生產(chǎn)中，會(huì)直接采用已有工具來實(shí)現(xiàn)解析。

Java生態(tài)中較為流行的SQL Parser有以下幾種（此處摘自網(wǎng)絡(luò)）：

• fdb-sql-parser 是FoundationDB在被Apple收購(gòu)前開源的SQL Parser，目前已無人維護(hù)。

• jsqlparser 是基于JavaCC的開源SQL Parser，是General SQL Parser的Java實(shí)現(xiàn)版本。

• Apache calcite 是一款開源的動(dòng)態(tài)數(shù)據(jù)管理框架，它具備SQL解析、SQL校驗(yàn)、查詢優(yōu)化、SQL生成以及數(shù)據(jù)連接查詢等功能，常用于為大數(shù)據(jù)工具提供SQL能力，例如Hive、Flink等。calcite對(duì)標(biāo)準(zhǔn)SQL支持良好，但是對(duì)傳統(tǒng)的關(guān)系型數(shù)據(jù)方言支持度較差。

• alibaba druid 是阿里巴巴開源的一款JDBC數(shù)據(jù)庫(kù)連接池，但其為監(jiān)控而生的理念讓其天然具有了SQL Parser的能力。其自帶的Wall Filer、StatFiler等都是基于SQL Parser解析的AST。并且支持多種數(shù)據(jù)庫(kù)方言。

Apache Sharding Sphere(原當(dāng)當(dāng)Sharding-JDBC，在1.5.x版本后自行實(shí)現(xiàn))、Mycat都是國(guó)內(nèi)目前大量使用的開源數(shù)據(jù)庫(kù)中間件，這兩者都使用了alibaba druid的SQL Parser模塊，并且Mycat還開源了他們?cè)谶x型時(shí)的對(duì)比分析Mycat路由新解析器選型分析與結(jié)果.

4.1 應(yīng)用場(chǎng)景

• 語法審核：根據(jù)內(nèi)置規(guī)則，對(duì)SQL進(jìn)行審核、合法性判斷。

• 查詢優(yōu)化：根據(jù)where條件、聚合條件、多表Join關(guān)系，給出索引優(yōu)化建議。

• 改寫SQL：對(duì)AST的節(jié)點(diǎn)進(jìn)行增減。

• 生成SQL特征：參考JIRA的慢SQL工單中，生成的指紋（不一定是AST方式，但AST可以實(shí)現(xiàn)）。

4.2 改寫SQL

提到改寫SQL，可能第一個(gè)思路就是在SQL中添加占位符，再進(jìn)行替換；再或者利用正則匹配關(guān)鍵字，這種方式局限性比較大，而且從安全角度不可取。

基于AST改寫SQL，是用SQL字符串生成AST，再對(duì)AST的節(jié)點(diǎn)進(jìn)行調(diào)整；通過遍歷Tree，拿到目標(biāo)節(jié)點(diǎn)，增加或修改節(jié)點(diǎn)的子節(jié)點(diǎn)，再將AST轉(zhuǎn)換為SQL字符串，完成改寫。這是在滿足SQL語法的前提下實(shí)現(xiàn)的安全改寫。

以Druid的SQL Parser模塊為例，利用其中的SQLUtils類，實(shí)現(xiàn)SQL改寫。

4.2.1 新增改寫

1）原始SQL

2）實(shí)際執(zhí)行SQL

4.2.2 查詢改寫

前面省略了Tree的遍歷過程，需要識(shí)別諸如join、sub-query等語法

1）簡(jiǎn)單join查詢

• 原始SQL

• 實(shí)際執(zhí)行SQL

2）join查詢+隱式where條件

• 原始SQL

• 實(shí)際執(zhí)行SQL

3）union查詢+join查詢+子查詢+顯示where條件

• 原始SQL
  （unionQuality_Union_Join_SubQuery_ExplicitCondition）

• 實(shí)際執(zhí)行SQL

本文是基于環(huán)境隔離的技術(shù)預(yù)研過程產(chǎn)生的，其中改寫SQL的實(shí)現(xiàn)，是數(shù)據(jù)庫(kù)在數(shù)據(jù)隔離上的一種嘗試。

可以讓開發(fā)人員無感知的情況下，以插件形式，在SQL提交到MySQL前實(shí)現(xiàn)動(dòng)態(tài)改寫，只需要在數(shù)據(jù)表上增加字段、標(biāo)識(shí)環(huán)境差異，后續(xù)CRUD的SQL都會(huì)自動(dòng)增加標(biāo)識(shí)字段（flag=’預(yù)發(fā)’、flag=’生產(chǎn)’），所操作的數(shù)據(jù)只能是當(dāng)前應(yīng)用所在環(huán)境的數(shù)據(jù)。

-End-