[[405195]]

SQL（Structured Query Language）作為一種領(lǐng)域語言（編程語言），最早用于關(guān)系型數(shù)據(jù)庫(kù)，方便管理結(jié)構(gòu)化數(shù)據(jù)；SQL由多種不同的類型的語言組成，包括數(shù)據(jù)定義語言，數(shù)據(jù)控制語言、數(shù)據(jù)操作語言；各數(shù)據(jù)庫(kù)產(chǎn)品都有不同的聲明和實(shí)現(xiàn)；用戶可以很方便的使用SQL操作數(shù)據(jù)，數(shù)據(jù)庫(kù)系統(tǒng)中的詞法語法分析器負(fù)責(zé)分析和理解SQL文本的含義，包括詞法分析、語法分析、語義分析3部分。經(jīng)過詞法語法分析器生成AST（Abstract Syntax Tree），會(huì)被優(yōu)化器處理生成生成執(zhí)行計(jì)劃，再由執(zhí)行引擎執(zhí)行，下圖以MySQL架構(gòu)為例展示詞法語法分析器所處的位置。

本文通過介紹詞法語法分析器技術(shù)和業(yè)界的做法，以及過去使用自動(dòng)生成的詞法語法分析器遇到的問題，分享自研SQL Parser的設(shè)計(jì)與實(shí)踐，以及其帶來的性能和功能的提升。

一、業(yè)界產(chǎn)品如何開發(fā)SQL Parser？

按照解析器代碼開發(fā)方式，可分為以下兩種：

1.自動(dòng)生成

為方便開發(fā)詞法、語法分析的過程，業(yè)界有許多詞法、語法分析工具，例如：Flex、Lex、Bison工具常用于生成以C、C++作為目標(biāo)語言的詞法、語法代碼；如果以Java作為目標(biāo)語言，可以使用比較流行的ANTLR和JavaCC等工具，ANTLR、JavaCC工具都以用戶編寫的詞法語法規(guī)則文件作為輸入，其中語法文件需要滿足EBNF（extended Backus–Naur form）[1]語法規(guī)則， 這2個(gè)工具使用LL(k) (Left-to-right, Leftmost derivation)[2] 算法“自頂向下[3]”解析SQL文本并構(gòu)建SQL AST， Presto，Spark、Hive等數(shù)據(jù)庫(kù)和大數(shù)據(jù)系統(tǒng)多采用該方式生成。生成的代碼包含詞法和語法解析部分，語義分析還需要結(jié)合Meta數(shù)據(jù)，各數(shù)據(jù)庫(kù)內(nèi)核自己處理；更多自動(dòng)生成工具的功能和算法對(duì)比[4]在參考文獻(xiàn)中。

2.手工編寫

與自動(dòng)生成工具不同，InfluxDB、H2、Clickhouse等流行的數(shù)據(jù)庫(kù)的SQL Parser組件均是手工編寫而成。

優(yōu)點(diǎn)：

• 代碼邏輯清晰，方便開發(fā)人員調(diào)試和排錯(cuò)；

• 性能更好：有更多代碼優(yōu)化的空間交給開發(fā)人員，可以使用更優(yōu)秀的算法和數(shù)據(jù)結(jié)構(gòu)提升性能；

• 自主可控：無licence約束，可讀性和可維護(hù)性更高；

• 不需要額外依賴第三方詞法語法代碼生成工具。

不足：

• 對(duì)開發(fā)人員的技術(shù)要求較高，需了解編譯原理技術(shù)；

• 開發(fā)工作量較大，實(shí)現(xiàn)MySQL常用語法的各類分支，需要投入很多時(shí)間和精力；

• 需要長(zhǎng)時(shí)間、大規(guī)模測(cè)試才會(huì)趨于穩(wěn)定。

二、問題與挑戰(zhàn)

1.復(fù)雜查詢的性能問題

在實(shí)時(shí)分析型數(shù)據(jù)庫(kù)的實(shí)際生產(chǎn)環(huán)境中，經(jīng)常需要處理數(shù)以千行的復(fù)雜查詢請(qǐng)求或者深層嵌套的查詢請(qǐng)求，自動(dòng)生成的解析器，由于狀態(tài)機(jī)管理復(fù)雜，線程堆棧太深，導(dǎo)致個(gè)別查詢請(qǐng)求在詞法語法解析階段性能下降嚴(yán)重。

2.大批量寫入吞吐問題

分析型數(shù)據(jù)庫(kù)要穩(wěn)定處理大批量、高并發(fā)寫入的場(chǎng)景，要求SQL Parser組件有很好的性能和穩(wěn)定性，我們嘗試使用過ANTLR，JavaCC等工具生成SQL 的詞法語法解析器，大批量寫入時(shí)，values子句在解析過程會(huì)產(chǎn)生太多AST臨時(shí)對(duì)象，導(dǎo)致垃圾回收耗時(shí)的問題。

3.Query Rewriting的靈活性問題

需要快速方便的遍歷AST樹，找到符合某種規(guī)則的葉子節(jié)點(diǎn)，修改改節(jié)點(diǎn)，自動(dòng)生成的解析器并不能很靈活的支持。

自動(dòng)生成的代碼可讀性差，排查問題成本高，復(fù)雜查詢場(chǎng)景下，性能不足，影響系統(tǒng)穩(wěn)定性和版本迭代速度；在設(shè)計(jì)之初，我們放棄了自動(dòng)生成的技術(shù)方案，完全手工編寫詞法語法解析器。

三、自研詞法語法分析器的技術(shù)要點(diǎn)

自動(dòng)生成工具主要處理生成下圖中左側(cè)的 SQL Parser Core和 SQL Tree Nodes的部分，右側(cè)featrues的部分需要開發(fā)同學(xué)處理，當(dāng)右側(cè)功能（例如：SQL rewriting）對(duì)左側(cè)有的Tree nodes的更改功能有更多的需求時(shí)，想修改自動(dòng)生成的代碼，則無從下手。

自動(dòng)生成工具是面向生成通用語法解析器而設(shè)計(jì)的，針對(duì)SQL這一特定領(lǐng)域語言，有特定的優(yōu)化技術(shù)提升穩(wěn)定性和性能，從設(shè)計(jì)之初，我們選擇LL(k)作為語法分析的算法，其自頂向下的特性，在手工編寫分析器時(shí)，邏輯清晰，代碼易讀，方便開發(fā)和維護(hù)，LL(k)的“左遞歸”問題，可通過手工判定循環(huán)編程的方式避免。

1.詞法和語法分析

詞法分析中，Lexer持續(xù)讀取連續(xù)SQL 文本，將具有某特征的一段連續(xù)文本標(biāo)識(shí)為Token，并標(biāo)識(shí)Token的類別，比如賦值語句 x = 30，經(jīng)過詞法分析后x, = , 30 分別被標(biāo)識(shí)為ID、等號(hào)操作符、數(shù)值常量；尤其在識(shí)別標(biāo)識(shí)符（變量，表名，列名等）和保留字（TABLE，F(xiàn)ROM，SELECT等）需要對(duì)字符串進(jìn)行反復(fù)對(duì)比。自動(dòng)生成工具在這一階段使用DFA（Deterministic Finite Automaton）和預(yù)先定義的詞法文件，確定每個(gè)Token的值和類型，手工編寫解析器不需要額外維護(hù)一個(gè)狀態(tài)機(jī)，使用分支預(yù)測(cè)，減少計(jì)算量和調(diào)用堆棧的深度。

語法分析器會(huì)使用詞法分析中的Token作為輸入，以SQL語法描述作為規(guī)則，自頂向下，依次將非葉子節(jié)點(diǎn)展開，構(gòu)建語法樹，整個(gè)過程就像是走迷宮，只有一個(gè)正確入口和出口，走完迷宮后，會(huì)生成一個(gè)正確的AST。

快速Token比較

selECT c1 From T1; 

由于大部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)對(duì)大小寫不敏感，上述query中 selECT 和 From 會(huì)被識(shí)別為保留字，c1和T1會(huì)被識(shí)別為標(biāo)識(shí)符。識(shí)別2者的類型不同，字符串匹配操作是必不可少的，通常將字符統(tǒng)一轉(zhuǎn)為大寫或者小寫，再比較字面值，是一個(gè)可行的方案。首先把數(shù)據(jù)庫(kù)保留字按照 Map<String, Token> 初始化在內(nèi)存里，key是保留字的大寫字符串，value是Token類型；其中key在作大寫轉(zhuǎn)化時(shí)，可使用ASCII值+32的方法取代 toUpperCase() 方法，在不影響正確性的前提下，獲得數(shù)倍性能提升。

快速數(shù)值分析

在解析常量值時(shí)，通常的做法是讀取SQL中的字符串，把字符串作為參數(shù)，調(diào)用Java自帶的 Integer.parseInt() / Float.parseFloat() / Long.parseLong() ，可以直接在原文本上邊讀取邊計(jì)算數(shù)值，該過程只使用基礎(chǔ)類型，避免構(gòu)造字符串，可以節(jié)省內(nèi)存，又提升了解析速度，該優(yōu)化對(duì)大批量寫入數(shù)值的場(chǎng)景優(yōu)化非常明顯。

避免回溯 [5]

SQL語法解析過程中，通常只需要預(yù)讀一個(gè)Token，就可以決定如何構(gòu)建語法節(jié)點(diǎn)的關(guān)系，或者構(gòu)建哪種語法節(jié) 點(diǎn)，有些語法分支較多，需要預(yù)讀2個(gè)及以上的Token才可以做出判斷，預(yù)讀多個(gè)Token可以降低回溯帶來的性能消耗，極少情況下，2個(gè)以上的Token預(yù)讀都也沒有匹配到正確的語法分支，需要撤銷預(yù)讀，走其他分支； 為了提高撤銷的速度，可以在預(yù)讀前保存Token位點(diǎn)，撤銷時(shí)，可以快速回到保存點(diǎn)。

在insert into values語句中，出現(xiàn)常量字面值的概率比出現(xiàn)其他的token要高，通過分支預(yù)測(cè)可以減少判斷邏輯，避免回溯，提升性能。

表達(dá)式替換

Query rewriting[6]技術(shù)基于“關(guān)系代數(shù)”修改AST，保證正確性的前提下，使新的AST在具備更好的執(zhí)行性能，例如：A，B兩張表的大小相差懸殊，而且錯(cuò)誤的Join順序?qū)?shù)據(jù)庫(kù)系統(tǒng)不友好，通過更改A，B表的Join順序可以獲得更高的執(zhí)行性能。使用工具生成的解析器，通常不允許直接更改AST的節(jié)點(diǎn)，每次更改AST某個(gè)節(jié)點(diǎn)都需要重新構(gòu)建整個(gè)AST，性能并不好。自研的Parser中，每個(gè)AST節(jié)點(diǎn)類實(shí)現(xiàn)都replace接口，只需要修改AST中的子樹就可以達(dá)到改寫的目的。

public interface Replaceable { 
    boolean replace(Node expr, Node target); 
} 
 
 
public class BetweenNode implements Replaceable { 
    public Node            beginExpr; 
    public Node            endExpr; 
     
    @Override 
    public int hashCode(){...} 
    @Override 
    public boolean equals(Object obj) {...} 
     
    @Override 
    public boolean replace(SQLExpr expr, SQLExpr target) { 
        if (expr == beginExpr) { 
            setBeginExpr(target); 
            return true; 
        } 
 
 
        if (expr == endExpr) { 
            setEndExpr(target); 
            return true; 
        } 
 
 
        return false; 
    } 
} 

其他優(yōu)化

• 支持AST Clone：如果保持原AST結(jié)構(gòu)不變，克隆出一個(gè)新的AST，在新的AST修改節(jié)點(diǎn)結(jié)構(gòu)，比如：增加Hint，刪減where條件，增加limit 限制等。

• 維護(hù)AST 父子關(guān)系：自動(dòng)生成的解析器維護(hù)了父到子節(jié)點(diǎn)的關(guān)系，是單向的引用關(guān)系。手寫代碼可以增加子節(jié)點(diǎn)對(duì)父節(jié)點(diǎn)的引用，構(gòu)建AST節(jié)點(diǎn)的雙向引用關(guān)系，實(shí)現(xiàn)節(jié)點(diǎn)的快速“回跳”，使得AST的遍歷效率更高。

public abstract class Node { 
    public abstract List<Node> getChildren() 
} 
 
 
public class BetweenNode extends Node { 
    public Node            beginExpr; 
    public Node            endExpr; 
     
    @Override 
    public List<Node> getChildren() { 
        return Arrays.<Node>asList(beginExpr, this.endExpr); 
    } 
     
    @Override 
    public BetweenNode clone() { 
        BetweenNode x = new BetweenNode(); 
        if (beginExpr != null) { 
            x.setBeginExpr(beginExpr.clone()); 
        } 
        if (endExpr != null) { 
            x.setEndExpr(endExpr.clone()); 
        } 
        return x; 
    } 
     
    public void setBeginExpr(Node beginExpr) { 
        if (beginExpr != null) { 
            beginExpr.setParent(this); 
        } 
        this.beginExpr = beginExpr; 
    } 
     
    public void setEndExpr(Node endExpr) { 
        if (endExpr != null) { 
            endExpr.setParent(this); 
        } 
        this.endExpr = endExpr; 
    } 
} 

2.語義分析

寫入事件回調(diào)

前面提到大批量導(dǎo)入數(shù)據(jù)時(shí)，詞法語法分析階段會(huì)產(chǎn)生很多AST小對(duì)象，給垃圾回收帶來壓力，解決這個(gè)問題的核心是要盡量使用基礎(chǔ)數(shù)據(jù)類型，盡量不要產(chǎn)生AST 節(jié)點(diǎn)對(duì)象。需要從詞法分析階段入手，避免進(jìn)入語法分析階段。在詞法分析階段，允許外部注冊(cè)實(shí)現(xiàn)了寫入接口的類，每當(dāng)詞法分析器解析出values中的每個(gè)具體值，或者完整解析出values中的一行，同時(shí)回調(diào)寫入接口，實(shí)現(xiàn)數(shù)據(jù)庫(kù)寫入邏輯。

public interface InsertValueHandler { 
    Object newRow() throws SQLException; 
    void processInteger(Object row, int index, Number value); 
    void processString(Object row, int index, String value); 
    void processDate(Object row, int index, String value); 
    void processDate(Object row, int index, java.util.Date value); 
    void processTimestamp(Object row, int index, String value); 
    void processTimestamp(Object row, int index, java.util.Date value); 
    void processTime(Object row, int index, String value); 
    void processDecimal(Object row, int index, BigDecimal value); 
    void processBoolean(Object row, int index, boolean value); 
    void processNull(Object row, int index); 
    void processFunction(Object row, int index, String funcName, Object... values); 
    void processRow(Object row); 
    void processComplete(); 
} 
 
 
public class BatchInsertHandler implements InsertValueHandler { 
    ... 
} 
 
 
public class Application { 
    BatchInsertHandler handler = new BatchInsertHandler(); 
    parser.parseInsertHeader(); // 頭部：解析 insert into xxx values 部分 
    parser.parseValues(handler); // 批量值：values (xxx), (xxx), (xxx) 部分 
} 

Query Rewriting

手動(dòng)編寫的SQL Parser可以更靈活的與優(yōu)化器配合，將Query rewriting 的部分優(yōu)化能力前置化到SQL Parser中實(shí)現(xiàn)，使得優(yōu)化器能更加專注于基于代價(jià)和成本的優(yōu)化上。Parser可以結(jié)合Meta信息，利用“等價(jià)關(guān)系代數(shù)”，在AST上低成本實(shí)現(xiàn)Query Rewriting功能，以提升查詢性能，例如：常量折疊、函數(shù)變換、條件下推或上提、類型推導(dǎo)、隱式轉(zhuǎn)化、語義去重等。

首先，需要設(shè)計(jì)一個(gè)結(jié)構(gòu)存儲(chǔ)catalog和table結(jié)構(gòu)信息，包括庫(kù)名，表名，列名，列類型等。

然后，使用“訪問者模式”編寫Visitor程序，通過“深度優(yōu)先”遍歷AST，對(duì)字段、函數(shù)、表達(dá)式、操作符進(jìn)行分析，結(jié)合表結(jié)構(gòu)和類型信息，推斷表達(dá)式類型，注意，嵌套的查詢語句中，相同的表達(dá)式出現(xiàn)的位置不同，所屬的作用域也不同。

最后，AST會(huì)經(jīng)過使用“等價(jià)關(guān)系代數(shù)”編寫的RBO（Rule-Based Optimization）規(guī)則處理，達(dá)到優(yōu)化器的目的。

-- 常量折疊示例 
SELECT * FROM T1 
WHERE c_week 
  BETWEEN CAST(date_format(date_add('day', -day_of_week('20180605'), 
                                   date('20180605')), '%Y%m&d') as bigint) 
  AND CAST(date_format(date_add('day', -day_of_week('20180606'), 
                                   date('20180606')), '%Y%m&d') as bigint) 
                                    
------------折疊后----------- 
SELECT * from T1 
WHERE c_week BETWEEN 20180602 and 20180603 

-- 函數(shù)轉(zhuǎn)換示例 
SELECT * FROM T1 
WHERE DATE_FORMAT(t1."pay_time", '%Y%m%d') >= '20180529' 
    AND DATE_FORMAT(t1."pay_time", '%Y%m%d') <= '20180529' 
     
-----------轉(zhuǎn)化后, 更好利用索引------------ 
SELECT * FROM T1 
WHERE t1."pay_time" >= '2018-05-29 00:00:00' 
  AND t1."pay_time" < '2018-05-30 00:00:00' 

四、最后

優(yōu)化后的SQL Parser的性能和穩(wěn)定性提升明顯，以TPC-DS[7] 99個(gè)Query對(duì)比來看，手工編寫的SQL Parser比ANTLR Parser（使用ANTLR生成）速度快20倍，比JSQLParser（使用JavaCC生成）速度快30倍，在批量Insert場(chǎng)景下，速度提升30~50倍。

本文通過介紹自動(dòng)生成工具生成的詞法語法分析器和自研分析器的利弊權(quán)衡和思考，結(jié)合OLAP的大吞吐，處理復(fù)雜SQL的業(yè)務(wù)特性，選擇手工編寫解析器。性能優(yōu)化手段貼近SQL解析的特點(diǎn)；在語義分析層面，結(jié)合Schema信息沉淀了很多語義分析工具，在離線或在線SQL統(tǒng)計(jì)和特征分析方面更輕量化、便捷。