引言
Apache Calcite 是一個動態(tài)數(shù)據(jù)管理框架，其中包含了許多組件凤价，例如 SQL 解析器鸽斟、SQL 驗證器、SQL 優(yōu)化器料仗、SQL 生成器等湾盗。因為 Calcite 的體系結(jié)構(gòu)并不支持?jǐn)?shù)據(jù)的存儲和處理，所以 Calcite 天然具備了在多種計算引擎和存儲格式之間作為“中介者”的能力立轧。前文《一條 SQL 的查詢優(yōu)化之旅》提到格粪，SQL 的查詢是從 SQL 解析和 SQL 驗證開始的，所以本文將圍繞這兩個話題展開氛改。
目標(biāo)和收益
本文第一部分介紹如何基于 Calcite 實現(xiàn)一個簡單的 SQL 解析器并擴(kuò)展其語法帐萎，并將外部數(shù)據(jù)庫的 SQL 語法轉(zhuǎn)換成 Calcite 內(nèi)部的解析體系。第二部分將介紹 SQL 驗證的流程和如何驗證擴(kuò)展的 SQL，如自定義函數(shù)等士鸥。
一歉秫、基于 Calcite 實現(xiàn)一個自定義 SQL 解析器
1.1 Calcite SQL 解析器介紹
Calcite 默認(rèn)使用 JavaCC 生成 SQL 解析器局齿，可以很方便的將其替換為 Antlr 作為代碼生成器 澈段。JavaCC 全稱 Java Compiler Compiler悠菜，是一個開源的 Java 程序解析器生成器，生成的語法分析器采用遞歸下降語法解析败富，簡稱 LL(K)悔醋。主要通過一些模版文件生成語法解析程序（例如根據(jù) .jj 文件或者 .jjt 等文件生產(chǎn)代碼）。
Calcite 的解析體系是將 SQL 解析成抽象語法樹兽叮， Calcite 中使用 SqlNode 這種數(shù)據(jù)結(jié)構(gòu)表示語法樹上的每個節(jié)點芬骄，例如 "select 1 + 1 = 2" 會將其拆分為多個 SqlNode。
SqlNode 有幾個重要的封裝子類鹦聪，SqlLiteral账阻、SqlIdentifier 和 SqlCall。SqlLiteral：封裝常量泽本，也叫字面量淘太。SqlIdentifier：SQL 標(biāo)識符，例如表名观挎、字段名等琴儿。SqlCall：表示一種操作，SqlSelect嘁捷、SqlAlter造成、SqlDDL 等都繼承 SqlCall。
1.2 實現(xiàn)一個簡單自定義 SQL Parser
Calcite 提供了一個默認(rèn)的 SQL 語法解析器雄嚣，默認(rèn)支持的語法可以查看此文檔：https://calcite.apache.org/docs/reference.html晒屎，除了默認(rèn)語法外，Calcite 還提供了其他 SQL 語法的兼容缓升，例如 STRICT_92鼓鲁、STRICT_99、STRICT_2003港谊、MYSQL_5骇吭、ORACLE_12 等，這部分可參考 Calcite 源碼 SqlConformanceEnum 類歧寺。
如果 Calcite 解析器并不能滿足我們的需求燥狰，需要擴(kuò)展語法操作怎么辦呢？
第一種方法是直接修改 Calcite 源碼斜筐，添加我們需要的語法實現(xiàn)龙致。但這種方式顯然對 Calcite 的侵入性太強(qiáng)，并不是最優(yōu)的辦法顷链。
第二種方法是采用模版引擎來擴(kuò)展 SQL 語法目代，相比第一種侵入性更小，達(dá)到了解耦的目的。
Calcite 支持使用 FreeMarker 模版引擎擴(kuò)展語法榛了，下圖是 Calcite 源碼中通過模版引擎擴(kuò)展 SQL 語法的相關(guān)目錄結(jié)構(gòu)在讶。
其中，templates 文件夾下的 Parser.jj 作為模版忽冻，includes 目錄下是擴(kuò)展語法文件真朗，config.fmpp 作為整體的配置，包含定義解析器類名僧诚、導(dǎo)入擴(kuò)展語法文件和自定義關(guān)鍵字等。
所以我們實現(xiàn)自定義 SQL Parser 的步驟為：
獲取 Calcite 源碼中的 Parser.jj 文件蝗碎，將此文件作為模版用于后續(xù)擴(kuò)展湖笨。
編寫自定義 SQL 擴(kuò)展語法文件和配置文件。
使用 JavaCC 編譯蹦骑。
1.2.1 獲取 Calcite 源碼中的 Parser.jj 文件
使用 Maven 插件 maven-dependency-plugin 直接從 Calcite 源碼包中進(jìn)行拷貝慈省，將 Parser.jj 文件拷貝到項目構(gòu)建目錄下。
<plugin>
? ? <groupId>org.apache.maven.plugins</groupId>
? ? <artifactId>maven-dependency-plugin</artifactId>
? ? <executions>
? ? ? ? <execution>
? ? ? ? ? ? <id>unpack-parser-template</id>
? ? ? ? ? ? <phase>initialize</phase>
? ? ? ? ? ? <goals>
? ? ? ? ? ? ? ? <goal>unpack</goal>
? ? ? ? ? ? </goals>
? ? ? ? ? ? <configuration>
? ? ? ? ? ? ? ? <artifactItems>
? ? ? ? ? ? ? ? ? ? <artifactItem>
? ? ? ? ? ? ? ? ? ? ? ? <groupId>org.apache.calcite</groupId>
? ? ? ? ? ? ? ? ? ? ? ? <artifactId>calcite-core</artifactId>
? ? ? ? ? ? ? ? ? ? ? ? <version>1.31.0</version>
? ? ? ? ? ? ? ? ? ? ? ? <type>jar</type>
? ? ? ? ? ? ? ? ? ? ? ? <overWrite>true</overWrite>
? ? ? ? ? ? ? ? ? ? ? ? <outputDirectory>${project.build.directory}/</outputDirectory>
? ? ? ? ? ? ? ? ? ? ? ? <includes>**/Parser.jj</includes>
? ? ? ? ? ? ? ? ? ? </artifactItem>
? ? ? ? ? ? ? ? </artifactItems>
? ? ? ? ? ? ? ? <skip>false</skip>
? ? ? ? ? ? </configuration>
? ? ? ? </execution>
? ? </executions>
</plugin>
可以使用 mvn initialize 進(jìn)行命令測試眠菇，如果成功我們會在 target 目錄下找到拷貝的語法模版文件边败。
1.2.2 自定義 SQL 語法
我們可以仿照 Calcite 在代碼目錄中創(chuàng)建 codegen 目錄結(jié)構(gòu)，新建一個 .ftl 文件捎废，下面以 Trino 的 CREATE MATERIALIZED VIEW 為例笑窜，演示如何在 Calcite 中新增這個語法：
/*為了演示方便 SQL語法有所簡化*/
CREATE MATERIALIZED VIEW
[ IF NOT EXISTS ] view_name
AS query
第一步，新增一種 SqlCall登疗，新建一個類繼承 SqlCall排截，實現(xiàn)構(gòu)造方法并重寫 unparse()，unparse()方式是 SqlNode 的解析器辐益，負(fù)責(zé)將 SqlNode 轉(zhuǎn)換為 Sql断傲。getOperator() 方法返回當(dāng)前 SqlNode 的操作符類型，所有的操作符類型可以在 org.apache.calcite.sql.SqlKind 中找到智政，CREATE MATERIALIZED VIEW 顯然是一種擴(kuò)展的 DDL，應(yīng)該返回 SqlKind.OTHER_DDL续捂，getOperandList() 返回操作符列表垦垂，這里我們可以返回物化視圖的名字和 AS 后面的語句，用于自定義 DDL 的校驗疾忍。
public class CreateMaterializedView
? ? ? ? extends SqlCall
{
? ? public static final SqlSpecialOperator CREATE_MATERIALIZED_VIEW = new SqlSpecialOperator("CREATE_MATERIALIZED_VIEW", SqlKind.OTHER_DDL);
? ? SqlIdentifier viewName;
? ? boolean existenceCheck;
? ? SqlSelect query;
? ? public CreateMaterializedView(SqlParserPos pos, SqlIdentifier viewName, boolean existenceCheck, SqlSelect query)
{
? ? ? ? super(pos);
? ? ? ? this.viewName = viewName;
? ? ? ? this.existenceCheck = existenceCheck;
? ? ? ? this.query = query;
? ? }
? ? @Override
? ? public SqlOperator getOperator()
{
? ? ? ? return CREATE_MATERIALIZED_VIEW;
? ? }
? ? @Override
? ? public List<SqlNode> getOperandList()
{
? ? ? ? List<SqlNode> operands = new ArrayList<>();
? ? ? ? operands.add(viewName);
? ? ? ? operands.add(SqlLiteral.createBoolean(existenceCheck, SqlParserPos.ZERO));
? ? ? ? operands.add(query);
? ? ? ? return operands;
? ? }
? ? @Override
? ? public void unparse(SqlWriter writer, int leftPrec, int rightPrec)
{
? ? ? ? writer.keyword("CREATE MATERIALIZED VIEW");
? ? ? ? if (existenceCheck) {
? ? ? ? ? ? writer.keyword("IF NOT EXISTS");
? ? ? ? }
? ? ? ? viewName.unparse(writer, leftPrec, rightPrec);
? ? ? ? writer.keyword("AS");
? ? ? ? query.unparse(writer, leftPrec, rightPrec);
? ? }
}
第二步乔外，編寫語法文件，在 codegen/includes 目錄下新建 parserImpls.ftl 文件一罩。語法文件內(nèi)容如下：
SqlNode SqlCreateMaterializedView() :
{
? ? SqlParserPos pos;
? ? SqlIdentifier viewName;
? ? boolean existenceCheck = false;
? ? SqlSelect query;
}
{
? ? <CREATE> { pos = getPos(); }
? ? <MATERIALIZED> <VIEW>
? ? <#-- [] 代表里面的元素可能出現(xiàn) -->
? ? ? ? [ <IF> <NOT> <EXISTS> { existenceCheck = true; } ]
? ? <#-- CompoundIdentifier() 為 Calcite 內(nèi)置函數(shù)杨幼，
? ? 可以解析類似 catalog.schema.tableName 這樣的全路徑表示形式 -->
? ? viewName = CompoundIdentifier()
? ? <AS>
? ? <#-- SqlSelect() 為 Calcite 內(nèi)置函數(shù)，解析一個 select sql -->
? ? query = SqlSelect()
? ? {
? ? ? ? return new CreateMaterializedView(pos, viewName, existenceCheck, query);
? ? }
}
第三步，配置 config.fmpp 文件差购，在 codegen 目錄下新建 config.fmpp 文件四瘫。定義解析器的包名和類型，聲明新增的關(guān)鍵字和解析方法等欲逃。
data: {
? parser: {
? ? package: "com.aloudata.demo.parser.impl",
? ? class: "DemoSqlParserImpl",
? ? imports: [
? ? ? ? "com.aloudata.tardis.parser.CreateMaterializedView.CreateType"
? ? ]
? ? keywords: [
? ? ? ? "IF",
? ? ? ? "MATERIALIZED"
? ? ]
? ? statementParserMethods: [
? ? ? ? "SqlCreateMaterializedView()"
? ? ]
? ? implementationFiles: [
? ? ? ? "parserImpls.ftl"
? ? ]
? }
}
freemarkerLinks: {
? includes: includes/
}
package 和 class 就是 JavaCC 生成的解析器的類名和包路徑找蜜。imports 中需要導(dǎo)入語法文件中使用到的 Java 類，keywords 關(guān)鍵字只需包含 Calcite 原生不存在的即可稳析，statementParserMethods 應(yīng)包含解析的入口方法洗做，implementationFiles 中為自定義語法文件名，freemarkerLinks.includes 為自定義語法文件相對路徑彰居。
1.2.3 JavaCC 編譯
使用 FreeMarker 模版插件根據(jù) config.fmpp 生成 parser.jj 文件诚纸，最后使用 JavaCC 編譯插件生成最終的解析器代碼。
配置 FreeMarker 插件
Maven 配置中 表示 config.fmpp 文件路徑陈惰。 表示輸出路徑畦徘。 表示從 Calcite 拷貝的模版文件路徑。配置好后可以使用 mvn generate-resources 命令測試是否生成了新的 parser.jj 文件抬闯。
<plugin>
? ? ? <groupId>com.googlecode.fmpp-maven-plugin</groupId>
? ? ? <artifactId>fmpp-maven-plugin</artifactId>
? ? ? <version>1.0</version>
? ? ? <configuration>
? ? ? ? ? <cfgFile>src/main/codegen/config.fmpp</cfgFile>
? ? ? ? ? <outputDirectory>target/generated-sources/fmpp<outputDirectory>
? ? ? ? ? <templateDirectory>${project.build.directory}/codegen/templates</templateDirectory>
? ? ? </configuration>
? ? <dependencies>
? ? ? ? <dependency>
? ? ? ? ? ? <groupId>org.freemarker</groupId>
? ? ? ? ? ? <artifactId>freemarker</artifactId>
? ? ? ? ? ? <version>2.3.28</version>
? ? ? ? </dependency>
? ? </dependencies>
? ? <executions>
? ? ? ? <execution>
? ? ? ? ? ? <id>generate-fmpp-sources</id>
? ? ? ? ? ? <phase>generate-sources</phase>
? ? ? ? ? ? <goals>
? ? ? ? ? ? ? ? <goal>generate</goal>
? ? ? ? ? ? </goals>
? ? ? ? </execution>
? ? </executions>
</plugin>
配置 JavaCC 插件
<plugin> <!-- generate the parser (Parser.jj is itself generated wit fmpp above) -->
? ? <groupId>org.codehaus.mojo</groupId>
? ? <artifactId>javacc-maven-plugin</artifactId>
? ? <version>2.6</version>
? ? <executions>
? ? ? ? <execution>
? ? ? ? ? ? <id>javacc</id>
? ? ? ? ? ? <phase>generate-sources</phase>
? ? ? ? ? ? <goals><goal>javacc</goal></goals>
? ? ? ? ? ? <configuration>
? ? ? ? ? ? ? ? <sourceDirectory>${project.build.directory}/generated-sources/fmpp</sourceDirectory>
? ? ? ? ? ? ? ? <includes>
? ? ? ? ? ? ? ? ? ? <include>**/*.jj</include>
? ? ? ? ? ? ? ? </includes>
? ? ? ? ? ? ? ? <lookAhead>1</lookAhead>
? ? ? ? ? ? ? ? <isStatic>false</isStatic>
? ? ? ? ? ? ? ? <outputDirectory>${project.build.directory}/generated-sources/javacc</outputDirectory>
? ? ? ? ? ? </configuration>
? ? ? ? </execution>
? ? </executions>
</plugin>
為 FreeMarker 生成的模版文件路徑井辆。后續(xù)再次執(zhí)行 mvn generate-resources 命令，在 <outputDirectory> 標(biāo)簽配置的路徑下會生成解析器相關(guān)的類溶握。至此杯缺，整個自定義解析器就基本完成了。
測試
我們可以寫一段簡單的測試代碼：
@Test
? ? public void test() throws SqlParseException {
? ? ? ? String sql = "CREATE MATERIALIZED VIEW IF NOT EXISTS \"test\".\"demo\".\"materializationName\" AS SELECT * FROM \"system\"";
? ? ? ? SqlParser.Config myConfig = SqlParser.config()
? ? ? ? ? ? ? ? .withQuoting(Quoting.DOUBLE_QUOTE)
? ? ? ? ? ? ? ? .withQuotedCasing(Casing.UNCHANGED)
? ? ? ? ? ? ? ? .withParserFactory(DemoSqlParserImpl.FACTORY);
? ? ? ? SqlParser parser = SqlParser.create(sql, myConfig);
? ? ? ? SqlNode sqlNode = parser.parseQuery();
? ? ? ? assertTrue(sqlNode instanceof CreateMaterializedView);
? ? ? ? System.out.println(sqlNode);
? ? }
輸出：
1.3 原理
上文介紹時提到奈虾，JavaCC 生成的語法分析器采用遞歸下降（自頂向下）語法解析夺谁，簡稱 LL(K)，第一個 L 代表從左到右掃描輸入肉微，第二個 L 代表每次都進(jìn)行最左推導(dǎo)匾鸥，K 表示每次向右探索 K 個終結(jié)符。JavaCC 默認(rèn)生成 LL(1) 的解析器碉纳。
JavaCC 中的詞法分析器會將語句拆分成一系列的子單元勿负，在 JavaCC 中稱為 token，語法分析器會拿著這個 token 串以 LL(1) 的方式進(jìn)行匹配劳曹，看是否符合定義的語法結(jié)構(gòu)奴愉。描述起來比較抽象，下面舉個例子：
例如 Total = price + tax; 這個語句铁孵，JavaCC 會將整條語句拆分成以下5個 token锭硼。
1.3.1 自頂向下 LL(1) 分析基本流程
上下文無關(guān)文法是 LL(1) 的充要條件，上下文無關(guān)文法的形式定義比較晦澀（可以參考https://baike.baidu.com/item/上下文無關(guān)文法/2001908）蜕劝，可以簡單理解為 A 可以直接推到出 aB （A → aB）是一個上下文無關(guān)文法檀头，u A b 推導(dǎo)出 aB （u A b → aB）當(dāng) A 的前一個是 u轰异，下一個是 b 的時候才能應(yīng)用次規(guī)則，這樣就是上下文有關(guān)文法∈钍迹現(xiàn)在有一種語法：
S –> AB
A –> aA | ε? // ε 代表一個空字符
B –> b |
上面每一行搭独，形如“A –> aA | ε”的式子稱為產(chǎn)生式。產(chǎn)生式左邊的符號稱為“非終結(jié)符”廊镜，這個符號既可以出現(xiàn)在產(chǎn)生式的左邊也可以出現(xiàn)在產(chǎn)生式的右邊牙肝，位于產(chǎn)生式右邊的 'a' 稱為“終結(jié)符”，它意味著無法再產(chǎn)生新的符號嗤朴，終結(jié)符只能出現(xiàn)在產(chǎn)生式右邊配椭。同時，上述產(chǎn)生式中有一個特別的非終結(jié)符 'S'雹姊，這種語法的所有句子都以它為起點產(chǎn)生颂郎，這個符號被稱為“起始符號（startsymbol）”。
例如容为，要分析的句子為 aaab，我們把解析過程和中間句子整理成以下表格：首先從起始符號 S 開始展開到最終語句 aaab寺酪，要匹配 aaab 中左邊第一個字符 a坎背，S 只能推導(dǎo)為 AB，所以用 AB 替換 S寄雀。
中間句子要匹配的語句產(chǎn)生式
Sa aabS → AB
ABa aab
由于 A 是非終結(jié)符得滤，下面要展開 A，A 有兩種產(chǎn)生式 A → aA, A → ε盒犹，和要匹配的語句進(jìn)行比較發(fā)現(xiàn) A → aA 可以匹配第一個字符 a懂更，以此類推前三個 'a' 都可以以這種方式匹配。展開過程如下：
中間句子要匹配的語句產(chǎn)生式
Sa aabS → AB
ABa aabA → aA
aABa a abA → aA
aaABaa a bA → aA
aaaABaaa b
最后一個 a 匹配結(jié)束后急膀，發(fā)現(xiàn)只能應(yīng)用產(chǎn)生式 A -> ε沮协，否則就無法得到 aaab，應(yīng)用此產(chǎn)生式后得到：
中間句子要匹配的語句產(chǎn)生式
Sa aabS → AB
ABa aabA → aA
aABa a abA → aA
aaABaa a bA → aA
aaaABaaa bA → ε
aaaBaaa bB →
最后按照上面的原則嘗試展開非終結(jié)符 B卓嫂，最終得到 aaab慷暂，整個語句推導(dǎo)成功。
中間句子要匹配的語句產(chǎn)生式
Sa aabS → AB
ABa aabS → aA
aABa a abS → aA
aaABaa a bS → aA
aaaABaaa bS → ε
aaaBaaa bB → b
aaabaaabACCEPT
這是一個非常簡單的語句推導(dǎo)過程晨雳，LL(1) 還會有其他更多的復(fù)雜情況與約束行瑞，感興趣可以參考此書的第九章和第十章（http://pandolia.net/tinyc）
1.3.2 LL(1) 的優(yōu)缺點
LL(1) 分析法的優(yōu)點是構(gòu)造方法較簡單，且分析速度非巢徒快血久，每讀到第一個符號就可以預(yù)測出整個產(chǎn)生式。缺點則是對語法的限制太強(qiáng)帮非，它要求同一個非終結(jié)符的不同產(chǎn)生式的首字符集合之間互不相交氧吐，否則我們就無法唯一確定一種語法讹蘑。
不過，在 JavaCC 編譯插件中或語法文件中可以使用 lookAhead 配置解析時向前探測的 token 數(shù)量副砍，也就是修改 LL(K) 中的 K 值衔肢，來解決一些語法沖突問題。
JavaCC 插件中配置
<configuration>
? <lookAhead>2</lookAhead>
</configuration>
詞法中使用 lookAhead
SqlNode SqlCreateMaterializedView() :
{
? ? ...
}
{
? ? LOOKAHEAD(2)
? ? ...
}
1.3.3 擴(kuò)展
與 LL 分析法對應(yīng)的還有 LR 分析法豁翎，和 LL 正好相反角骤，LR 是從最終表達(dá)式向上折疊，直到跟產(chǎn)生式無法再匹配為止心剥。LR 分析法相比于 LL 來說在普適性方面占有絕對的優(yōu)勢邦尊，因為 LR 文法能夠支持更多上下文無關(guān)文法，并且不需要考慮消除左遞歸的問題优烧。
左遞歸問題
左遞歸：是指形如 A -> A u 這樣的規(guī)則蝉揍。
LL(1) 的分析法無法解決“左遞歸”問題，這是 LL 解析器的局限畦娄，因為一個含左遞歸的語法（如：A -> Aa | c）中又沾，必然存在相交的現(xiàn)象。Antlr4 中的 ALL 解析器解決了左遞歸問題熙卡，但是對于間接左遞歸仍然無能為力杖刷。并且在自頂向下分析法中，左遞歸的出現(xiàn)對性能的影響極大驳癌，因為出現(xiàn)左遞歸就意味著需要對匹配串進(jìn)行回溯滑燃，而回溯分析一般都非常慢，所以應(yīng)該盡量避免這種語法的出現(xiàn)颓鲜。
總結(jié)
本文介紹了 Calcite SQL 解析模塊以及語法擴(kuò)展的方式表窘，并對 LL(k) 分析法做了簡單闡述，以 LL(1) 為例探究了整個分析過程甜滨。下一篇乐严，我們將介紹Calcite SQL 的驗證流程與原理，一起探究如何在 SQL 驗證階段進(jìn)行語法的擴(kuò)展艳吠。
錢可以帶來快樂麦备，玩技術(shù)也可以！最后昭娩，如果你對數(shù)據(jù)虛擬化凛篙、Calcite 原理技術(shù)、湖倉平臺栏渺、SQL 優(yōu)化器感興趣的話呛梆，歡迎關(guān)注“Aloudata技術(shù)團(tuán)隊”公眾號。
??本文作者/淳譯磕诊，Aloudata OLAP 引擎開發(fā)工程師填物，參與 Aloudata AIR Engine 的多個核心模塊開發(fā)纹腌，目前負(fù)責(zé) Aloudata 數(shù)據(jù)虛擬化引擎的 SQL 層、元數(shù)據(jù)和多源異構(gòu)引擎集成等相關(guān)工作滞磺。
