作者：vivo 網際網路搜尋團隊- Deng Jie

一、背景

隨著技術的不斷的發展，在巨量資料領域出現了越來越多的技術框架。而為了降低巨量資料的學習成本和難度，越來越多的巨量資料技術和應用開始支援SQL進行資料查詢。SQL作為一個學習成本很低的語言，支援SQL進行資料查詢可以降低使用者使用巨量資料的門檻，讓更多的使用者能夠使用巨量資料。

本篇文章主要介紹如何實現一個SQL解析器來應用的業務當中，同時結合具體的案例來介紹SQL解析器的實踐過程。

二、為什麼需要SQL解析器？

在設計專案系統架構時，我們通常會做一些技術調研。我們會去考慮為什麼需要SQL解析器？怎麼判斷選擇的 SQL 解析器可以滿足當前的技術要求？

2.1 傳統的SQL查詢

傳統的SQL查詢，依賴完整的資料庫協定。比如資料儲存在MySQL、Oracle等關係型資料庫中，有標準的SQL語法。我們可以通過不同的SQL語句來實現業務需求，如下圖所示：

但是，在處理海量資料的時候，關係型資料庫是難以滿足實際的業務需求的，我們需要藉助巨量資料生態圈的技術元件來解決實際的業務需求。

2.2 實際應用場景

在使用巨量資料生態圈的技術元件時，有些技術元件是自帶SQL的，比如Hive、Spark、Flink等；而有些技術元件本身是不帶SQL的，比如Kafka、HBase。下面，我們可以通過對比不帶SQL和使用SQL解析器後的場景，如下圖所示：

從上圖中，我們可以看到，圖左邊在我們使用不帶SQL的技術元件時，實現一個查詢時，需要我們編寫不同的業務邏輯介面，來與Kafka、HBase這些技術元件來進行資料互動。如果隨著這類元件的增加，查詢功能複雜度的增加，那邊每套介面的複雜度也會隨之增加，對於後續的擴充套件和維護也是很不方便的。而圖右邊在我們引入SQL解析器後，只需要一套介面來完成業務邏輯，對於不同的技術元件進行適配即可。

三、什麼是SQL解析器？

在選擇SQL解析器應用到我們實際的業務場景之前，我們先來了解一下SQL解析器的核心知識點。

3.1 SQL解析器包含哪些內容？

在使用SQL解析器時，解析SQL的步驟與我們解析Java/Python程式的步驟是非常的相似的，比如：

在C/C++中，我們可以使用LEX和YACC來做詞法分析和語法分析
在Java中，我們可以使用JavaCC或ANTLR

在我們使用解析器的過程當中，通常解析器主要包括三部分，它們分別是：詞法解析、語法解析、語意解析。

3.1.1 什麼詞法解析？

如何理解詞法解析呢？詞法解析我們可以這麼來進行理解，在啟動詞法解析任務時，它將從左到右把字元一個個的讀取並載入到解析程式裡面，然後對位元組流進行掃描，接著根據構詞規則識別字元並切割成一個個的詞條，切詞的規則是遇到空格進行分割，遇到分號時結束詞法解析。比如一個簡單的SQL如下所示：

SQL範例

SELECT name FROM tab;

通過詞法解析後，結果如下所示：

3.1.2 什麼是語法解析？

如何理解語法解析呢？語法解析我們可以這麼來進行理解，在啟動語法解析任務時，語法分析的任務會在詞法分析的結果上將詞條序列組合成不同語法短句，組成的語法短句將與相應的語法規則進行適配，若適配成功則生成對應的抽象語法樹，否則報會丟擲語法錯誤異常。比如如下SQL語句：

SQL範例

SELECT name FROM tab WHERE id=1001;

約定規則如下：

上表中，紅色的內容通常表示終結符，它們一般是大寫的關鍵字或者符號等，小寫的內容是非終結符，一般用作規則的命名，比如欄位、表名等。具體AST資料結構如下圖所示：

3.1.3 什麼是語意解析？

如何理解語意解析呢？語意解析我們可以這麼來進行理解，語意分析的任務是對語法解析得到的抽象語法樹進行有效的校驗，比如欄位、欄位型別、函數、表等進行檢查。比如如下語句：

SQL範例

SELECT name FROM tab WHERE id=1001;

上述SQL語句，語意分析任務會做如下檢查：

SQL語句中表名是否存在；
欄位name是否存在於表tab中；
WHERE條件中的id欄位型別是否可以與1001進行比較操作。

上述檢查結束後，語意解析會生成對應的表示式供優化器去使用。

四、如何選擇SQL解析器？

在瞭解瞭解析器的核心知識點後，如何選擇合適的SQL解析器來應用到我們的實際業務當中呢？下面，我們來對比一下主流的兩種SQL解析器。它們分別是ANTLR和Calcite。

4.1 ANTLR

ANTLR是一款功能強大的語法分析器生成器，可以用來讀取、處理、執行和轉換結構化文字或者二進位制檔案。在巨量資料的一些SQL框架裡面有有廣泛的應用，比如Hive的詞法檔案是ANTLR3寫的，Presto詞法檔案也是ANTLR4實現的，SparkSQLambda詞法檔案也是用Presto的詞法檔案改寫的，另外還有HBase的SQL工具Phoenix也是用ANTLR工具進行SQL解析的。

使用ANTLR來實現一條SQL，執行或者實現的過程大致是這樣的，實現詞法檔案（.g4），生成詞法分析器和語法分析器，生成抽象語法樹（也就是我常說的AST），然後再遍歷抽象語法樹，生成語意樹，存取統計資訊，優化器生成邏輯執行計劃，再生成物理執行計劃去執行。

官網範例：

ANTLR表示式

assign : ID '=' expr ';' ;

解析器的程式碼類似於下面這樣：

ANTLR解析器程式碼

void assign() {
  match(ID);
  match('=');
  expr();
  match(';');
}

4.1.1 Parser

Parser是用來識別語言的程式，其本身包含兩個部分：詞法分析器和語法分析器。詞法分析階段主要解決的問題是關鍵字以及各種識別符號，比如INT（型別關鍵字）和ID（變數識別符號）。語法分析主要是基於詞法分析的結果，構造一顆語法分析數，流程大致如下：

因此，為了讓詞法分析和語法分析能夠正常工作，在使用ANTLR4的時候，需要定義語法（Grammar）。

我們可以把字元流（CharStream），轉換成一棵語法分析樹，字元流經過詞法分析會變成Token流。Token流再最終組裝成一棵語法分析樹，其中包含葉子節點（TerminalNode）和非葉子節點（RuleNode）。具體語法分析樹如下圖所示：

4.1.2 Grammar

ANTLR官方提供了很多常用的語言的語法檔案，可以進行修改後直接進行復用：https://github.com/antlr/grammars-v4

在使用語法的時候，需要注意以下事項：

語法名稱和檔名要一致；
語法分析器規則以小寫字母開始；
詞法分析器規則以大寫字母開始；
用'string'單引號引出字串；
不需要指定開始符號；
規則以分號結束；
...

4.1.3 ANTLR4實現簡單計算功能

下面通過簡單範例，說明ANTLR4的用法，需要實現的功能效果如下：

ANTLR範例

1+2 => 1+2=3
1+2*4 => 1+2*4=9
1+2*4-5 => 1+2*4-5=4
1+2*4-5+20/5 => 1+2*4-5+20/5=8
(1+2)*4 => (1+2)*4=12

通過ANTLR處理流程如下圖所示：

整體來說一個原則，遞迴下降。即定義一個表示式(如expr)，可以迴圈呼叫直接也可以呼叫其他表示式，但是最終肯定會有一個最核心的表示式不能再繼續往下呼叫了。

步驟一：定義詞法規則檔案（CommonLexerRules.g4）

CommonLexerRules.g4

// 定義詞法規則
lexer grammar CommonLexerRules;
 
//////// 定義詞法
// 匹配ID
ID     : [a-zA-Z]+ ;
// 匹配INT
INT    : [0-9]+    ;
// 匹配換行符
NEWLINE: '\n'('\r'?);
// 跳過空格、跳格、換行符
WS     : [ \t\n\r]+ -> skip;
 
//////// 運運算元
DIV:'/';
MUL:'*';
ADD:'+';
SUB:'-';
EQU:'=';

步驟二：定義語法規則檔案（LibExpr.g4）

LibExpr.g4

// 定於語法規則
grammar LibExpr;
 
// 匯入詞法規則
import CommonLexerRules;
 
// 詞法根
prog:stat+ EOF?;
 
// 定義宣告
stat:expr (NEWLINE)?         # printExpr
    | ID '=' expr (NEWLINE)? # assign
    | NEWLINE                # blank
    ;
 
// 定義表示式
expr:expr op=('*'|'/') expr # MulDiv
    |expr op=('+'|'-') expr # AddSub
    |'(' expr ')'           # Parens
    |ID                     # Id
    |INT                    # Int
    ;

步驟三：編譯生成檔案

如果是Maven工程，這裡在pom檔案中新增如下依賴：

ANTLR依賴JAR

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

然後，執行Maven編譯命令即可：

Maven編譯命令

mvn generate-sources

步驟四：編寫簡單的範例程式碼

待預算的範例文字：

範例文字

1+2
1+2*4
1+2*4-5
1+2*4-5+20/5
(1+2)*4

加減乘除邏輯類：

邏輯實現類

package com.vivo.learn.sql;
 
import java.util.HashMap;
import java.util.Map;
 
/**
 * 重寫存取器規則，實現資料計算功能
 * 目標：
 *     1+2 => 1+2=3
 *     1+2*4 => 1+2*4=9
 *     1+2*4-5 => 1+2*4-5=4
 *     1+2*4-5+20/5 => 1+2*4-5+20/5=8
 *     (1+2)*4 => (1+2)*4=12
 */
public class LibExprVisitorImpl extends LibExprBaseVisitor<Integer> {
    // 定義資料
    Map<String,Integer> data = new HashMap<String,Integer>();
 
    // expr (NEWLINE)?         # printExpr
    @Override
    public Integer visitPrintExpr(LibExprParser.PrintExprContext ctx) {
        System.out.println(ctx.expr().getText()+"="+visit(ctx.expr()));
        return visit(ctx.expr());
    }
 
    // ID '=' expr (NEWLINE)? # assign
    @Override
    public Integer visitAssign(LibExprParser.AssignContext ctx) {
        // 獲取id
        String id = ctx.ID().getText();
        // // 獲取value
        int value = Integer.valueOf(visit(ctx.expr()));
 
        // 快取ID資料
        data.put(id,value);
 
        // 列印紀錄檔
        System.out.println(id+"="+value);
 
        return value;
    }
 
    // NEWLINE                # blank
    @Override
    public Integer visitBlank(LibExprParser.BlankContext ctx) {
        return 0;
    }
 
    // expr op=('*'|'/') expr # MulDiv
    @Override
    public Integer visitMulDiv(LibExprParser.MulDivContext ctx) {
        // 左側數位
        int left = Integer.valueOf(visit(ctx.expr(0)));
        // 右側數位
        int right = Integer.valueOf(visit(ctx.expr(1)));
        // 操作符號
        int opType = ctx.op.getType();
 
        // 偵錯
        // System.out.println("visitMulDiv>>>>> left:"+left+",opType:"+opType+",right:"+right);
 
        // 判斷是否為乘法
        if(LibExprParser.MUL==opType){
            return left*right;
        }
 
        // 判斷是否為除法
        return left/right;
 
    }
 
    // expr op=('+'|'-') expr # AddSub
    @Override
    public Integer visitAddSub(LibExprParser.AddSubContext ctx) {
        // 獲取值和符號
 
        // 左側數位
        int left = Integer.valueOf(visit(ctx.expr(0)));
        // 右側數位
        int right = Integer.valueOf(visit(ctx.expr(1)));
        // 操作符號
        int opType = ctx.op.getType();
 
        // 偵錯
        // System.out.println("visitAddSub>>>>> left:"+left+",opType:"+opType+",right:"+right);
 
        // 判斷是否為加法
        if(LibExprParser.ADD==opType){
            return left+right;
        }
 
        // 判斷是否為減法
        return left-right;
 
    }
 
    // '(' expr ')'           # Parens
    @Override
    public Integer visitParens(LibExprParser.ParensContext ctx) {
        // 遞迴下調
        return visit(ctx.expr());
    }
 
    // ID                     # Id
    @Override
    public Integer visitId(LibExprParser.IdContext ctx) {
        // 獲取id
        String id = ctx.ID().getText();
        // 判斷ID是否被定義
        if(data.containsKey(id)){
            // System.out.println("visitId>>>>> id:"+id+",value:"+data.get(id));
            return data.get(id);
        }
        return 0;
    }
 
    // INT                    # Int
    @Override
    public Integer visitInt(LibExprParser.IntContext ctx) {
        // System.out.println("visitInt>>>>> int:"+ctx.INT().getText());
        return Integer.valueOf(ctx.INT().getText());
    }
 
}

Main函數列印輸出結果類：

package com.vivo.learn.sql;
 
import org.antlr.v4.runtime.tree.ParseTree;
 
import java.io.FileNotFoundException;
import java.io.IOException;
import org.antlr.v4.runtime.*;
 
/**
 * 列印語法樹
 */
public class TestLibExprPrint {
 
    // 列印語法樹 input -> lexer -> tokens -> parser -> tree -> print
    public static void main(String args[]){
        printTree("E:\\smartloli\\hadoop\\sql-parser-example\\src\\main\\resources\\testCase.txt");
    }
 
 
    /**
     * 列印語法樹 input -> lexer -> token -> parser -> tree
     * @param fileName
     */
    private static void printTree(String fileName){
        // 定義輸入流
        ANTLRInputStream input = null;
 
        // 判斷檔名是否為空,若不為空，則讀取檔案內容，若為空，則讀取輸入流
        if(fileName!=null){
            try{
                input = new ANTLRFileStream(fileName);
            }catch(FileNotFoundException fnfe){
                System.out.println("檔案不存在，請檢查後重試！");
            }catch(IOException ioe){
                System.out.println("檔案讀取異常，請檢查後重試！");
            }
        }else{
            try{
                input = new ANTLRInputStream(System.in);
            }catch(FileNotFoundException fnfe){
                System.out.println("檔案不存在，請檢查後重試！");
 
            }catch(IOException ioe){
                System.out.println("檔案讀取異常，請檢查後重試！");
            }
        }
 
        // 定義詞法規則分析器
        LibExprLexer lexer = new LibExprLexer(input);
 
        // 生成通用字元流
        CommonTokenStream tokens = new CommonTokenStream(lexer);
 
        // 語法解析
        LibExprParser parser = new LibExprParser(tokens);
 
        // 生成語法樹
        ParseTree tree = parser.prog();
 
        // 列印語法樹
        // System.out.println(tree.toStringTree(parser));
 
        // 生命存取器
        LibExprVisitorImpl visitor = new LibExprVisitorImpl();
        visitor.visit(tree);
 
    }
 
}

執行程式碼，最終輸出結果如下圖所示：

4.2 Calcite

上述ANTLR內容演示了詞法分析和語法分析的簡單流程，但是由於ANTLR要實現SQL查詢，需要自己定義詞法和語法相關檔案，然後再使用ANTLR的外掛對檔案進行編譯，然後再生成程式碼（與Thrift的使用類似，也是先定義介面，然後編譯成對應的語言檔案，最後再繼承或者實現這些生成好的類或者介面）。

4.2.1 原理及優勢

而Apache Calcite的出現，大大簡化了這些複雜的工程。Calcite可以讓使用者很方便的給自己的系統套上一個SQL的外殼，並且提供足夠高效的查詢效能優化。

query language；
query optimization；
query execution；
data management；
data storage；

上述這五個功能，通常是資料庫系統包含的常用功能。Calcite在設計的時候就確定了自己只關注綠色的三個部分，而把下面資料管理和資料儲存留給各個外部的儲存或計算引擎。

資料管理和資料儲存，尤其是資料儲存是很複雜的，也會由於資料本身的特性導致實現上的多樣性。Calcite拋棄這兩部分的設計，而是專注於上層更加通用的模組，使得自己能夠足夠的輕量化，系統複雜性得到控制，開發人員的精力也不至於耗費的太多。

同時，Calcite也沒有重複去早輪子，能複用的東西，都是直接拿來複用。這也是讓開發者能夠接受去使用它的一個原因。比如，如下兩個例子：

例子1：作為一個SQL解析器，關鍵的SQL解析，Calcite沒有重複造輪子，而是直接使用了開源的JavaCC，來將SQL語句轉化為Java程式碼，然後進一步轉化成一棵抽象語法樹（AST）以供下一階段使用；
例子2：為了支援後面會提到的靈活的後設資料功能，Calcite需要支援執行時編譯Java程式碼。預設的JavaC太重，需要一個更輕量級的編譯器，Calcite同樣沒有選擇造輪子，而是使用了開源了Janino方案。

上面的圖是Calcite官方給出的架構圖，從圖中我們可以獲取到的資訊是，一方面印證了我們上面提到的，Calcite足夠的簡單，沒有做自己不該做的事情；另一方面，也是更重要的，Calcite被設計的足夠模組化和可插拔。

【JDBC Client】：這個模組用來支援使用JDBC Client的應用；
【SQL Parser and Validator】：該模組用來做SQL解析和校驗；
【Expressions Builder】：用來支援自己做SQL解析和校驗的框架對接；
【Operator Expressions】：該模組用來處理關係表示式；
【Metadata Provider】：該模組用來支援外部自定義後設資料；
【Pluggable Rules】：該模組用來定義優化規則；
【Query Optimizer】：最核心的模組，專注於查詢優化。

功能模組的劃分足夠合理，也足夠獨立，使得不用完整整合，而是可以只選擇其中的一部分使用，而基本上每個模組都支援自定義，也使得使用者能夠更多的客製化系統。

上面列舉的這些巨量資料常用的元件都Calcite均有整合，可以看到Hive就是自己做了SQL解析，只使用了Calcite的查詢優化功能。而像Flink則是從解析到優化都直接使用了Calcite。

上面介紹的Calcite整合方法，都是把Calcite的模組當做庫來使用。如果覺得太重量級，可以選擇更簡單的介面卡功能。通過類似Spark這些框架裡自定義的Source或Sink的方式，來實現和外部系統的資料互動操作。

上圖就是比較典型的介面卡用法，比如通過Kafka的介面卡就能直接在應用層通過SQL，而底層自動轉換成Java和Kafka進行資料互動（後面部分有個案例操作）。

4.2.2 Calcite實現KSQL查詢Kafk

參考了EFAK（原Kafka Eagle開源專案）的SQL實現，來查詢Kafka中Topic裡面的資料。

1.常規SQL查詢

SQL查詢

select * from video_search_query where partition in (0) limit 10

預覽截圖：

2.UDF查詢

SQL查詢

select JSON(msg,'query') as query,JSON(msg,'pv') as pv from video_search_query where `partition` in (0) limit 10

預覽截圖：

4.3 ANTLR4 和 Calcite SQL解析對比

4.3.1 ANTLR4解析SQL

ANTLR4解析SQL的主要流程包含：定義詞法和語法檔案、編寫SQL解析邏輯類、主服務呼叫SQL邏輯類。

1.定義詞法和語法檔案

可參考官網提供的開源地址：詳情

2.編寫SQL解析邏輯類

這裡，我們編寫一個實現解析SQL表名的類，具體實現程式碼如下所示：

解析表名

public class TableListener extends antlr4.sql.MySqlParserBaseListener {

    private String tableName = null;

    public void enterQueryCreateTable(antlr4.sql.MySqlParser.QueryCreateTableContext ctx) {
        List<MySqlParser.TableNameContext> tableSourceContexts = ctx.getRuleContexts(antlr4.sql.MySqlParser.TableNameContext.class);
        for (antlr4.sql.MySqlParser.TableNameContext tableSource : tableSourceContexts) {
            // 獲取表名
            tableName = tableSource.getText();
        }
    }

    public String getTableName() {
        return tableName;
    }
}

3.主服務呼叫SQL邏輯類

對實現SQL解析的邏輯類進行呼叫，具體程式碼如下所示：

主服務

public class AntlrClient {

    public static void main(String[] args) {
        // antlr4 格式化SQL
        antlr4.sql.MySqlLexer lexer = new antlr4.sql.MySqlLexer(CharStreams.fromString("create table table2 select tid from table1;"));
        antlr4.sql.MySqlParser parser = new antlr4.sql.MySqlParser(new CommonTokenStream(lexer));
        // 定義TableListener
        TableListener listener = new TableListener();
        ParseTreeWalker.DEFAULT.walk(listener, parser.sqlStatements());
        // 獲取表名
        String tableName= listener.getTableName();
        // 輸出表名
        System.out.println(tableName);
    }
}

4.3.2 Calcite解析SQL

Calcite解析SQL的流程相比較ANTLR是比較簡單的，開發中無需關注詞法和語法檔案的定義和編寫，只需關注具體的業務邏輯實現。比如實現一個SQL的COUNT操作，Calcite實現步驟如下所示。

1.pom依賴

Calcite依賴JAR

<dependencies>
  <!-- 這裡對Calcite適配依賴進行封裝，引入下列包即可 -->
  <dependency>
    <groupId>org.smartloli</groupId>
    <artifactId>jsql-client</artifactId>
    <version>1.0.0</version>
  </dependency>
</dependencies>

2.實現程式碼

Calcite範例程式碼

package com.vivo.learn.sql.calcite;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import org.smartloli.util.JSqlUtils;

public class JSqlClient {
    public static void main(String[] args) {
        JSONObject tabSchema = new JSONObject();
        tabSchema.put("id","integer");
        tabSchema.put("name","varchar");

        JSONArray datasets = JSON.parseArray("[{\"id\":1,\"name\":\"aaa\",\"age\":20},{\"id\":2,\"name\":\"bbb\",\"age\":21},{\"id\":3,\"name\":\"ccc\",\"age\":22}]");

        String tabName = "userinfo";
        String sql = "select count(*) as cnt from \"userinfo\"";
        try{
           String result = JSqlUtils.query(tabSchema,tabName,datasets,sql);
            System.out.println("result: "+result);
        }catch (Exception e){
            e.printStackTrace();
        }

    }
}

3.預覽截圖

4.3.3 對比結果

綜合對比，我們從對兩種技術的學習成本、使用複雜度、以及靈活度來對比，可以優先選擇Calcite來作為SQL解析器來處理實際的業務需求。

五、總結

另外，在單機模式的情況下，執行計劃可以較為簡單的翻譯成執行程式碼，但是在分散式領域中，因為計算引擎多種多樣，因此，還需要一個更加貼近具體計算引擎的描述，也就是物理計劃。換言之，邏輯計劃只是抽象的一層描述，而物理計劃則和具體的計算引擎直接掛鉤。

滿足上述場景，通常都可以引入SQL解析器：

給關係型資料庫（比如MySQL、Oracle）這類提供客製化化的SQL來作為互動查詢；
給開發人員提供了JDBC、ODBC之類和各種資料庫的標準介面；
對資料分析師等不太會程式語言的但又需要使用資料的人；
巨量資料技術元件不自帶SQL的；

參考資料：

如何實現一個SQL解析器

一、背景

二、為什麼需要SQL解析器？

2.1 傳統的SQL查詢

2.2 實際應用場景

三、什麼是SQL解析器？

3.1 SQL解析器包含哪些內容？

3.1.1 什麼詞法解析？

3.1.2 什麼是語法解析？

3.1.3 什麼是語意解析？

四、 如何選擇SQL解析器？

4.1 ANTLR

4.1.1 Parser

4.1.2 Grammar

4.1.3 ANTLR4實現簡單計算功能

4.2 Calcite

4.2.1 原理及優勢

4.2.2 Calcite實現KSQL查詢Kafk

4.3 ANTLR4 和 Calcite SQL解析對比

4.3.1 ANTLR4解析SQL

4.3.2 Calcite解析SQL

4.3.3 對比結果

五、總結

四、如何選擇SQL解析器？