SQL解析器詳解
1.概述
最近，有同學留言關於SQL解析器方面的問題，今天筆者就為大家分享一下SQL解析器方便的一些內容。
2.內容
2.1 SQL解析器是什麼？
SQL解析與優化是屬於編輯器方面的知識，與C語言這類編程語言的解析上是類似的。SQL解析主要包含：詞法分析、語義語法分析、優化和執行代碼生成、例如，我們非常熟悉的MySQL的一個SQL解析部分流程，如下圖所以：
這裡給大家介紹一下關於MySQL Lex和Bison生成的相關含義和具體負責的內容。
1.詞法分析
SQL解析由詞法分析和語法、語義分析兩個部分組成。詞法分析主要是把輸入轉化成若干個Token，其中Token包含key和非key。比如，一個簡單的SQL如下所示：
SELECT age FROM user
在分析之後，會得到4個Token，其中有2個key，它們分別是SELECT、FROM。
| key | 非key | key | 非key |
| SELECT | age | FROM | user |
通常情況下，詞法分析可以使用Flex來生成，但是我們熟悉的MySQL裏面並沒有使用該工具，而是手寫了詞法分析的部分（具體原因據說是為了效率和靈活性）。
MySQL在lex.h文件中對key進行了定義，下面是部分的key：
{"&&", SYM(AND_AND_SYM)},
{"<", SYM(LT)},
{"<=", SYM(LE)},
{"<>", SYM(NE)},
{"!=", SYM(NE)},
{"=", SYM(EQ)},
{">", SYM(GE_SYM},
{">=", SYM(GE)},
{"<<", SYM(SHIFT_LEFT)},
{">>", SYM(SHIFT_RIGHT)},
{"<=>", SYM(EQUAL_SYM)},
{"ADD", SYM(ADD)},
{"AFTER", SYM(AFTER_SYM)},
{"AGGREGATE", SYM(AGGREGATE_SYM)},
{"ALL", SYM(ALL_SYM)},
2.語法分析
語法分析是生成語法樹的過程，這是整個解析過程中最核心、最複雜的環節。不過，這部分MySQL使用了Bison來實現，即使如此，如何設計合適的數據結構和相關算法，以及存儲和遍歷所有的信息，也是值得我們去研究的。
例如，如下SQL語句：
SELECT name,age from user where age > 20 and age < 25 and gender = 'F'
解析上述SQL時會生成如下語法數：
2.2 ANTLR VS Calcite ?
2.2.1 ANTLR
ANTLR 是一個功能強大的語法分析生成器，可以用來讀取、處理、執行和轉換結構化文本或者二進制文件。在大數據的一些SQL框架裏面有廣泛的應用，比如Hive的詞法文件是ANTLR3寫的，Presto詞法文件也是ANTLR4實現的，SparkSQL Lambda詞法文件也是用Presto的詞法文件改寫的，另外還有HBase的SQL工具Phoenix也是用ANTLR工具進行SQL解析的。
使用ANTLR來實現一條SQL，執行或者實現的過程大致如下：
- 實現詞法文件（g4）；
- 生成詞法分析器和語法分析器；
- 生成抽象語法數（AST）；
- 遍歷AST；
- 生成語義樹；
- 優化生成邏輯執行計劃；
- 生成物理執行計劃再執行。
實例代碼如下所示：
assign : ID '=' expr ';' ;
解析器的代碼類似如下：
void assign(){ match(ID); match('='); expr(); match(); }
1.Parser
Parser是用來識別語言的程序，其本身包含兩個部分：詞法分析器和語法分析器。詞法分析階段主要解決的問題是key以及各種symbols，比如INT或者ID。語法分析主要是基於詞法分析的結果構造一顆語法分析樹，如下圖所示：
因此，為了讓詞法分析和語法能夠正常工作，在使用ANTLR4的時候，需要定義Grammar。
我們可以把CharStream轉換成一顆AST，CharStream經過詞法分析後會變成Token，TokenStream再最終組成一顆AST，其中包含TerminalNode和RuleNode，具體如下所示：
2.Grammar
ANTLR官方提供了很多常用的語言的語法文件，可以進行膝蓋後直接進行使用：
//github.com/antlr/grammars-v4
在使用語法的時候，需要注意以下事項：
- 語法名稱和文件名要一致；
- 語法分析器規則以小寫字母開始；
- 詞法分析器規則以大寫字母開始；
- 用’string’單引號引出字符串；
- 不需要指定開始字符；
- 規則以分號結束；
- …
3.實例分析
這裡我們使用IDEA來進行編寫，使用IDEA中的ANTLR4相關插件來實現。然後創建一個Maven工程，在pom.xml文件中添加如下依賴：
<dependency> <groupId>org.antlr</groupId> <artifactId>antlr4</artifactId> <version>4.9.3</version> </dependency>
然後，創建一個語法文件，內容如下所示：
grammar Expr; prog : stat+; stat: expr NEWLINE # printExpr | ID '=' expr NEWLINE # assign | NEWLINE # blank ; expr: expr op=('*'|'/') expr # MulDiv | expr op=('+'|'-') expr # AddSub | INT # int | ID # id | '(' expr ')' # parens ; MUL : '*' ; DIV : '/' ; ADD : '+' ; SUB : '-' ; ID : [a-zA-Z]+ ; INT : [0-9]+ ; NEWLINE:'\r'? '\n' ; WS : [ \t]+ -> skip;
上述語法文件很簡單，本質含義就是一個遞歸下降，即定義一個表達式（expr），可以循環調用，也可以直接調用其他表達式，但是最終肯定會有一個最核心的表達式不能再繼續往下調用了。以上語法文件在真正執行的時候會生成一顆AST，然後在IDEA中執行「Test Rule …」，並在執行後的測試框中輸入表達式「((1 + 2 ) + 3 – 4 * 5 ) / 6」，就會生成一顆AST了。AST如下圖所示：
整個語法文件的目的是為了讓ANTLR生成相關的JAVA代碼，我們設置生成visitor，然後，它們會生成如下文件：
- ExprParser；
- ExprLexer；
- ExprBaseVisitor；
- ExprVisitor。
ExprLexer是詞法分析器，ExprParser是語法分析器。一個語言的解析過程一般是從詞法分析到語法分析。這是ANTLR4為我們生成的框架代碼，而我們需要做的事情就是實現一個Visitor，一般從ExprBaseVisitor來繼承即可。生成的文件如下所示：
然後，我編寫一個自定義的實現計算類，代碼如下所示：
public class ExprCalcVistor extends ExprBaseVisitor{ public Integer visitAssign(ExprParser.AssignContext ctx) { String id = ctx.ID().getText(); Integer value = (Integer) visit(ctx.expr()); return value; } @Override public Integer visitInt(ExprParser.IntContext ctx) { return Integer.valueOf(ctx.INT().getText()); } @Override public Integer visitMulDiv(ExprParser.MulDivContext ctx) { Integer left = (Integer) visit(ctx.expr(0)); Integer right = (Integer) visit(ctx.expr(1)); if (ctx.op.getType() == ExprParser.MUL){ return left * right; }else{ return left / right; } } }
最後，執行主函數，代碼如下所示：
public class ExprMain { public static void main(String[] args) throws IOException { ANTLRInputStream inputStream = new ANTLRInputStream("1 + 2 * 3"); ExprLexer lexer = new ExprLexer(inputStream); CommonTokenStream tokenStream = new CommonTokenStream(lexer); ExprParser parser = new ExprParser(tokenStream); ParseTree parseTree = parser.prog(); ExprCalcVistor visitor = new ExprCalcVistor(); Integer rtn = (Integer) visitor.visit(parseTree); System.out.println("result: " + rtn); } }
2.2.2 Calcite
上述ANTLR內容演示了詞法分析和語法分析的簡單流程，但是由於ANTLR要實現SQL查詢，需要自己定義詞法和語法相關文件，然後再使用ANTLR的插件對文件進行編譯，然後再生成代碼。
而Apache Calcite的出現，大大簡化了這些複雜工程，Calcite可以讓用戶很方便的給自己的系統套上一個SQL的外殼，並且提供足夠高效的查詢性能優化。
- query language
- query optimization
- query execution
- data management
- data storage
上述這五個功能，通常是數據庫系統包含的常用功能。Calcite在設計的時候就確定了自己只關注綠色的三個部分，而把下面數據管理和數據存儲留給了外部的存儲或者計算引擎。
數據管理和數據存儲，尤其是數據存儲是很複雜的，也會由於數據本身的特性導致實現上的多樣性。Calcite棄用這2部分的設計，而是專註於上層更加通用的模塊，使得自己能夠足夠的輕量化，系統複雜性得到控制，開發人員的專註點不會耗費太多時間。
同時，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：最核心的模塊，專註於查詢優化
功能模塊的規劃足夠合理，也足夠獨立，使得不用完整的集成，而是可以只選擇其中的一部分使用，而基本上每個模塊都支持自定義，也使得用戶能夠更多的定製系統，如下表所示：
| System | Query Language | JDBC Driver | SQL Parser and Validator | Execution Engine |
| Apache Flink | Streaming SQL | √ | √ | Native |
| Apache Hive | SQL+extensions | √ | √ | Tez, Spark |
| Apache Drill | SQL+extensions | √ | √ | Native |
| Apache Phoenix | SQL | √ | √ | HBase |
| Apache Kylin | SQL | √ | √ | HBase |
| … | … | … | … | … |
上面列舉的這些大數據常用的組件中Calcite均有集成，可以看到Hive就是自己做了SQL解析，只使用了Calcite的查詢優化功能，而像Flink則是從解析到優化都直接使用了Calcite。
上面介紹的Calcite集成方法，都是把Calcite的模塊當作庫來使用，如果覺得太重量級，可以選擇更簡單的適配器功能。通過類似Spark這些框架來自定義的Source或Sink方式，來實現和外部系統的數據交互操作。
| Adapter | Target Language |
| Cassandra | CQL |
| Pig | Pig Latin |
| Spark | RDD |
| Kafka | Java |
| … | … |
上圖就是比較典型的適配器用法，比如通過Kafka的適配器就能直接在應用層通過SQL，而底層自動轉換成Java和Kafka進行數據交互。
1.pom依賴
<dependency> <groupId>org.smartloli</groupId> <artifactId>jsql-client</artifactId> <version>1.0.2</version> </dependency>
2.實例
public static void main(String[] args) throws Exception { JSONObject tabSchema = new JSONObject(); tabSchema.put("id", "integer"); tabSchema.put("name", "varchar"); tabSchema.put("age", "integer"); String tableName = "stu"; List<JSONArray> preRusult = new ArrayList<>(); JSONArray dataSets = new JSONArray(); for (int i = 0; i < 5000; i++) { JSONObject object = new JSONObject(); object.put("id", i); object.put("name", "aa" + i); object.put("age", 10 + i); dataSets.add(object); } preRusult.add(dataSets); String sql = "select count(*) as cnt from stu"; JSONObject result = JSqlUtils.query(tabSchema, tableName, preRusult, sql); System.out.println(result); }
3.Calcite實現KSQL查詢Kafka
Kafka Eagle實現了SQL查詢Kafka Topic中的數據，SQL操作Topic如下所示：
select * from efak_cluster_006 where `partition` in (0) limit 10
執行上圖SQL語句，截圖如下所示：
感興趣的同學，可以關注Kafka Eagle官網，或者源代碼。
4.結束語
這篇博客就和大家分享到這裡，如果大家在研究學習的過程當中有什麼問題，可以加群進行討論或發送郵件給我，我會盡我所能為您解答，與君共勉！
另外，博主出書了《Kafka並不難學》和《Hadoop大數據挖掘從入門到進階實戰》，喜歡的朋友或同學， 可以在公告欄那裡點擊購買鏈接購買博主的書進行學習，在此感謝大家的支持。關注下面公眾號，根據提示，可免費獲取書籍的教學視頻。
