关于sql: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 配置中 <cfgFile> 示意 config.fmpp 文件门路。<outputDirectory> 示意输入门路。<templateDirectory> 示意从 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>

<sourceDirectory> 为 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。

因为 A 是非终结符，上面要开展 A，A 有两种产生式 A → aA, A → ε，和要匹配的语句进行比拟发现 A → aA 能够匹配第一个字符 a，以此类推前三个 ‘a’ 都能够以这种形式匹配。开展过程如下：

最初一个 a 匹配完结后，发现只能利用产生式 A -> ε，否则就无奈失去 aaab，利用此产生式后失去：

最初依照下面的准则尝试开展非终结符 B，最终失去 aaab，整个语句推导胜利。

这是一个非常简单的语句推导过程，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 层、元数据和多源异构引擎集成等相干工作。