Calcite SQL 解析、语法扩展、元数据验证原理与实战（上）

引言

Apache Calcite 是一个动态数据管理框架，其中包含了许多组件，例如 SQL 解析器、SQL 验证器、SQL 优化器、SQL 生成器等。因为 Calcite 的体系结构并不支持数据的存储和处理，所以 Calcite 天然具备了在多种计算引擎和存储格式之间作为“中介者”的能力。前文《一条 SQL 的查询优化之旅》提到，SQL 的查询是从 SQL 解析和 SQL 验证开始的，所以本文将围绕这两个话题展开。

目标和收益

本文第一部分介绍如何基于 Calcite 实现一个简单的 SQL 解析器并扩展其语法，并将外部数据库的 SQL 语法转换成 Calcite 内部的解析体系。第二部分将介绍 SQL 验证的流程和如何验证扩展的 SQL，如自定义函数等。

一、基于 Calcite 实现一个自定义 SQL 解析器

1.1 Calcite SQL 解析器介绍

Calcite 默认使用 JavaCC 生成 SQL 解析器，可以很方便的将其替换为 Antlr 作为代码生成器 。JavaCC 全称 Java Compiler Compiler，是一个开源的 Java 程序解析器生成器，生成的语法分析器采用递归下降语法解析，简称 LL(K)。主要通过一些模版文件生成语法解析程序（例如根据 .jj 文件或者 .jjt 等文件生产代码）。

Calcite 的解析体系是将 SQL 解析成抽象语法树， Calcite 中使用 SqlNode 这种数据结构表示语法树上的每个节点，例如 "select 1 + 1 = 2" 会将其拆分为多个 SqlNode。

SqlNode 有几个重要的封装子类，SqlLiteral、SqlIdentifier 和 SqlCall。SqlLiteral：封装常量，也叫字面量。SqlIdentifier：SQL 标识符，例如表名、字段名等。SqlCall：表示一种操作，SqlSelect、SqlAlter、SqlDDL 等都继承 SqlCall。

1.2 实现一个简单自定义 SQL Parser

Calcite 提供了一个默认的 SQL 语法解析器，默认支持的语法可以查看此文档：https://calcite.apache.org/docs/reference.html，除了默认语法外，Calcite 还提供了其他 SQL 语法的兼容，例如 STRICT_92、STRICT_99、STRICT_2003、MYSQL_5、ORACLE_12 等，这部分可参考 Calcite 源码 SqlConformanceEnum 类。

如果 Calcite 解析器并不能满足我们的需求，需要扩展语法操作怎么办呢？

第一种方法是直接修改 Calcite 源码，添加我们需要的语法实现。但这种方式显然对 Calcite 的侵入性太强，并不是最优的办法。

第二种方法是采用模版引擎来扩展 SQL 语法，相比第一种侵入性更小，达到了解耦的目的。

Calcite 支持使用 FreeMarker 模版引擎扩展语法，下图是 Calcite 源码中通过模版引擎扩展 SQL 语法的相关目录结构。


其中，templates 文件夹下的 Parser.jj 作为模版，includes 目录下是扩展语法文件，config.fmpp 作为整体的配置，包含定义解析器类名、导入扩展语法文件和自定义关键字等。

所以我们实现自定义 SQL Parser 的步骤为：

获取 Calcite 源码中的 Parser.jj 文件，将此文件作为模版用于后续扩展。

编写自定义 SQL 扩展语法文件和配置文件。

使用 JavaCC 编译。

1.2.1 获取 Calcite 源码中的 Parser.jj 文件

使用 Maven 插件 maven-dependency-plugin 直接从 Calcite 源码包中进行拷贝，将 Parser.jj 文件拷贝到项目构建目录下。

<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 进行命令测试，如果成功我们会在 target 目录下找到拷贝的语法模版文件。

1.2.2 自定义 SQL 语法

我们可以仿照 Calcite 在代码目录中创建 codegen 目录结构，新建一个 .ftl 文件，下面以 Trino 的 CREATE MATERIALIZED VIEW 为例，演示如何在 Calcite 中新增这个语法：

/*为了演示方便 SQL语法有所简化*/

CREATE MATERIALIZED VIEW

[ IF NOT EXISTS ] view_name

AS query

第一步，新增一种 SqlCall，新建一个类继承 SqlCall，实现构造方法并重写 unparse()，unparse()方式是 SqlNode 的解析器，负责将 SqlNode 转换为 Sql。getOperator() 方法返回当前 SqlNode 的操作符类型，所有的操作符类型可以在 org.apache.calcite.sql.SqlKind 中找到，CREATE MATERIALIZED VIEW 显然是一种扩展的 DDL，应该返回 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 文件。语法文件内容如下：

SqlNode SqlCreateMaterializedView() :

{

    SqlParserPos pos;

    SqlIdentifier viewName;

    boolean existenceCheck = false;

    SqlSelect query;

}

{

    <CREATE> { pos = getPos(); }

    <MATERIALIZED> <VIEW>

    <#-- [] 代表里面的元素可能出现 -->

        [ <IF> <NOT> <EXISTS> { existenceCheck = true; } ]

    <#-- CompoundIdentifier() 为 Calcite 内置函数，

    可以解析类似 catalog.schema.tableName 这样的全路径表示形式 -->

    viewName = CompoundIdentifier()

    <AS>

    <#-- SqlSelect() 为 Calcite 内置函数，解析一个 select sql -->

    query = SqlSelect()

    {

        return new CreateMaterializedView(pos, viewName, existenceCheck, query);

    }

}

第三步，配置 config.fmpp 文件，在 codegen 目录下新建 config.fmpp 文件。定义解析器的包名和类型，声明新增的关键字和解析方法等。

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 中需要导入语法文件中使用到的 Java 类，keywords 关键字只需包含 Calcite 原生不存在的即可，statementParserMethods 应包含解析的入口方法，implementationFiles 中为自定义语法文件名，freemarkerLinks.includes 为自定义语法文件相对路径。

1.2.3 JavaCC 编译

使用 FreeMarker 模版插件根据 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 生成的模版文件路径。后续再次执行 mvn generate-resources 命令，在 <outputDirectory> 标签配置的路径下会生成解析器相关的类。至此，整个自定义解析器就基本完成了。

测试

我们可以写一段简单的测试代码：

@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 代表每次都进行最左推导，K 表示每次向右探索 K 个终结符。JavaCC 默认生成 LL(1) 的解析器。

JavaCC 中的词法分析器会将语句拆分成一系列的子单元，在 JavaCC 中称为 token，语法分析器会拿着这个 token 串以 LL(1) 的方式进行匹配，看是否符合定义的语法结构。描述起来比较抽象，下面举个例子：

例如 Total = price + tax; 这个语句，JavaCC 会将整条语句拆分成以下5个 token。


1.3.1 自顶向下 LL(1) 分析基本流程

上下文无关文法是 LL(1) 的充要条件，上下文无关文法的形式定义比较晦涩（可以参考https://baike.baidu.com/item/上下文无关文法/2001908），可以简单理解为 A 可以直接推到出 aB （A → aB）是一个上下文无关文法，u A b 推导出 aB （u A b → aB）当 A 的前一个是 u，下一个是 b 的时候才能应用次规则，这样就是上下文有关文法。现在有一种语法：

S –> AB

A –> aA | ε  // ε 代表一个空字符

B –> b |

上面每一行，形如“A –> aA | ε”的式子称为产生式。产生式左边的符号称为“非终结符”，这个符号既可以出现在产生式的左边也可以出现在产生式的右边，位于产生式右边的 'a' 称为“终结符”，它意味着无法再产生新的符号，终结符只能出现在产生式右边。同时，上述产生式中有一个特别的非终结符 'S'，这种语法的所有句子都以它为起点产生，这个符号被称为“起始符号（startsymbol）”。

例如，要分析的句子为 aaab，我们把解析过程和中间句子整理成以下表格：首先从起始符号 S 开始展开到最终语句 aaab，要匹配 aaab 中左边第一个字符 a，S 只能推导为 AB，所以用 AB 替换 S。

中间句子要匹配的语句产生式

Sa aabS → AB

ABa aab

由于 A 是非终结符，下面要展开 A，A 有两种产生式 A → aA, A → ε，和要匹配的语句进行比较发现 A → aA 可以匹配第一个字符 a，以此类推前三个 'a' 都可以以这种方式匹配。展开过程如下：

中间句子要匹配的语句产生式

Sa aabS → AB

ABa aabA → aA

aABa a abA → aA

aaABaa a bA → aA

aaaABaaa b

最后一个 a 匹配结束后，发现只能应用产生式 A -> ε，否则就无法得到 aaab，应用此产生式后得到：

中间句子要匹配的语句产生式

Sa aabS → AB

ABa aabA → aA

aABa a abA → aA

aaABaa a bA → aA

aaaABaaa bA → ε

aaaBaaa bB →

最后按照上面的原则尝试展开非终结符 B，最终得到 aaab，整个语句推导成功。

中间句子要匹配的语句产生式

Sa aabS → AB

ABa aabS → aA

aABa a abS → aA

aaABaa a bS → aA

aaaABaaa bS → ε

aaaBaaa bB → b

aaabaaabACCEPT

这是一个非常简单的语句推导过程，LL(1) 还会有其他更多的复杂情况与约束，感兴趣可以参考此书的第九章和第十章（http://pandolia.net/tinyc）

1.3.2 LL(1) 的优缺点

LL(1) 分析法的优点是构造方法较简单，且分析速度非常快，每读到第一个符号就可以预测出整个产生式。缺点则是对语法的限制太强，它要求同一个非终结符的不同产生式的首字符集合之间互不相交，否则我们就无法唯一确定一种语法。

不过，在 JavaCC 编译插件中或语法文件中可以使用 lookAhead 配置解析时向前探测的 token 数量，也就是修改 LL(K) 中的 K 值，来解决一些语法冲突问题。

JavaCC 插件中配置

<configuration>

  <lookAhead>2</lookAhead>

</configuration>

词法中使用 lookAhead

SqlNode SqlCreateMaterializedView() :

{

    ...

}

{

    LOOKAHEAD(2)

    ...

}

1.3.3 扩展

与 LL 分析法对应的还有 LR 分析法，和 LL 正好相反，LR 是从最终表达式向上折叠，直到跟产生式无法再匹配为止。LR 分析法相比于 LL 来说在普适性方面占有绝对的优势，因为 LR 文法能够支持更多上下文无关文法，并且不需要考虑消除左递归的问题。

左递归问题

左递归：是指形如 A -> A u 这样的规则。

LL(1) 的分析法无法解决“左递归”问题，这是 LL 解析器的局限，因为一个含左递归的语法（如：A -> Aa | c）中，必然存在相交的现象。Antlr4 中的 ALL 解析器解决了左递归问题，但是对于间接左递归仍然无能为力。并且在自顶向下分析法中，左递归的出现对性能的影响极大，因为出现左递归就意味着需要对匹配串进行回溯，而回溯分析一般都非常慢，所以应该尽量避免这种语法的出现。

总结

本文介绍了 Calcite SQL 解析模块以及语法扩展的方式，并对 LL(k) 分析法做了简单阐述，以 LL(1) 为例探究了整个分析过程。下一篇，我们将介绍Calcite SQL 的验证流程与原理，一起探究如何在 SQL 验证阶段进行语法的扩展。

钱可以带来快乐，玩技术也可以！最后，如果你对数据虚拟化、Calcite 原理技术、湖仓平台、SQL 优化器感兴趣的话，欢迎关注“Aloudata技术团队”公众号。

✎ 本文作者/淳译，Aloudata OLAP 引擎开发工程师，参与 Aloudata AIR Engine 的多个核心模块开发，目前负责 Aloudata 数据虚拟化引擎的 SQL 层、元数据和多源异构引擎集成等相关工作。

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 193,968评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,682评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,254评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,074评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 60,964评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,055评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,484评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,170评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,433评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,512评论 2赞 308
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,296评论 1赞 325
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,184评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,545评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,880评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,150评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,437评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,630评论 2赞 335

推荐阅读更多精彩内容