关于java:CalciteApache-Calcite-框架初探及概念详解

1. 简介

Calcite 是什么？如果用一句话形容 Calcite，Calcite 是一个用于优化异构数据源的查询处理的根底框架。

最近十几年来，呈现了很多专门的数据处理引擎。例如列式存储 (HBase)、流解决引擎 (Flink)、文档搜索引擎 (Elasticsearch) 等等。这些引擎在各自针对的畛域都有独特的劣势，在现有简单的业务场景下，咱们很难只采纳当中的某一个而舍弃其余的数据引擎。当引擎倒退到肯定成熟阶段，为了缩小用户的学习老本，大多引擎都会思考引入 SQL 反对，但如何防止反复造轮子又成了一个大问题。基于这个背景，Calcite 横空出世，它提供了规范的 SQL 语言、多种查问优化和连贯各种数据源的能力 ，将数据存储以及数据管理的能力留给引擎本身实现。 同时 Calcite 有着良好的可插拔的架构设计，咱们能够只应用其中一部分性能构建本人的 SQL 引擎，而无需将整个引擎依靠在 Calcite 上。因而 Calcite 成为了当初许多大数据框架 SQL 引擎的最佳计划。咱们计算引擎组也基于 Calcite 实现了一个自用的 SQL 校验层，当用户提交 Flink SQL 作业时须要先进过一层语义校验，通过后再利用校验失去的元数据构建模板工作提交给 Flink 引擎执行。

注：目前 Calcite 的官网最新版本是 v1.27，Flink 1.12 应用的是 Calcite v1.26，本文的内容基于 Calcite 1.20 编写，但所有核心内容均不受版本影响。

2. 外围架构

图来自《Apache Calcite》

两头的方框总结了 Calcite 的外围构造，首先 Calcite 通过 SQL Parser 和 Validator 将一个 SQL 查问解析失去一个形象语法树 (AST, Abstract Syntax Tree)，因为 Calcite 不蕴含存储层，因而它提供了另一种定义 table schema 和 view 的机制—— Catalog 作为元数据的存储空间（另外 Calcite 提供了 Adaptor 机制连贯内部的存储引擎获取元数据，这部分内容不在本文范畴内）。之后，Calcite 通过优化器生成对应的关系表达式树，依据特定的规定进行优化。优化器是 Calcite 最为重要的一部分逻辑，它蕴含了三个组件：Rule、MetadataProvider（Catalog）、Planner engine，这些组件在文章后续都会有具体的解说。

通过架构图咱们能够看出，Calcite 最大的特点（劣势）是它将 SQL 的解决、校验和优化等逻辑独自剥离进去，省略了一些要害组件，例如，数据存储，解决数据的算法以及用于存储元数据的存储库。其次 Calcite 做得最出色的中央则是它的可插拔机制，每个大数据框架都能够抉择 Calcite 的整体或局部模块建设本人的 SQL 解决引擎，如 Hive 本人实现了 SQL 解析，只应用了 Calcite 的优化性能，Storm 以及 Flink 则是齐全基于 Calcite 建设了 SQL 引擎，具体如下表所示：

表来自《Apache Calcite》

2.1 四个阶段

图来自 Introduction to Calcite

Calcite 框架的运行次要分四个阶段

1. Parse：应用 JavaCC 生成的解析器进行词法、语法分析，失去 AST；
2. Validate：联合元数据进行校验；
3. Optimize：将 AST 转化为逻辑执行打算（tree of relational expression），并依据特定的规定（heuristic 或 cost-baesd）进行优化；
4. Execute：将逻辑执行打算 转化成引擎特有的执行逻辑，比方 Flink 的 DataStream。

思考到第 4 步是一个和引擎耦合的流程，上面的内容咱们次要聚焦于前三个阶段。

2.2 四大组件

围绕着这个运行流程，Apache Calcite 最外围的框架能够拆分为四个组件

1. SQL Parser：将合乎语法规定的 SQL 转化成 AST（Sql text → SqlNode），Calcite 提供了默认的 parser，但也能够基于 JavaCC 生成自定义的 parser；
2. Catalog：定义记录了 SQL 的 metadata 和 namespace，不便后续的拜访和校验；
3. SQL Validator：联合 Catalog 提供的元数据校验 AST，具体的实现都在 SqlValidatorImpl 中；
4. Query Optimizer：这块概念较多，首先须要将 AST 转化成逻辑执行打算（即 SqlNode → RelNode），其次应用 Rules 优化逻辑执行打算。

3. SQL parser

上文提到，SQL Parser 的作用是将 SQL 文本切割成一个个 token 并生成 AST，每个 token 在 Calcite 中由 SqlNode 示意（即代表 AST 的一个个结点），SqlNode 也能够通过 unparse 办法从新生成 SQL 文本。为了不便阐明，咱们引入一个 SQL 文本，通过观察它在 Calcite 中的变动来摸清 Calcite 的原理，后续的校验、优化咱们也会依据具体场景引入不同的 SQL 文本进行剖析。

INSERT INTO sink_table SELECT s.id, name, age FROM source_table s JOIN dim_table d ON s.id=d.id WHERE s.id>1;

3.1 SqlNode

SqlNode 是 AST 所有结点的形象，它可能具体代表某个运算符、常量或标识符等等，以 SqlNode 基类衍生出许多实现类如下：

INSERT 被 Parser 解析后会转化成一个 SqlInsert，而 SELECT 则转化成 SqlSelect，以上述的 SQL 文本为例，解析后会失去如下构造：

上面依据该图解说 SqlNode 中一些较常见的外围构造。

3.1.1 SqlInsert

首先这是个动作为 INSERT 的 DDL 语句，因而整个 AST root 是一个 SqlInsert，SqlInsert 中有个有许多成员变量别离记录了这个 INSERT 语句的不同组成部分：

• targetTable：记录要插入的表，即 sink_table，在 AST 中示意为 SqlIdentifier
• source：标识了数据源，该 INSERT 语句的数据源是一个 SELECT 子句，在 AST 中示意为 SqlSelect；
• columnList：要插入的列，因为该 Insert 语句未显式指定所以是 null，会在校验阶段动静计算失去。

3.1.2 SqlSelect

SqlSelect 是该 INSERT 语句的数据源局部被 Parser 解析生成的局部，它的外围构造如下：

• selectList：指 SELECT 关键字后紧跟的查问的列，是一个 SqlNodeList，在该例中因为显式指定了列且无任何函数调用，因而 SqlNodeList 中是三个 SqlIdentifier；
• from：指 SELECT 语句的数据源，该例中的数据源是表 source_table 和 dim_table 的连贯，因而这里是一个 SqlJoin；
• where：指 WHERE 子句，是一个对于条件判断的函数调用，SqlBasicCall，它的操作符是一个二元运算符 >，被解析为 SqlBinaryOperator，两个操作数别离是 s.id(SqlIdentifier) 和 1(SqlNumberLiteral)。

3.1.3 SqlJoin

SqlJoin 是该 SqlSelect 语句的 JOIN 局部被 Parser 解析生成的局部：

• left：代表 JOIN 的左表，因为咱们用了别名，因而这里是一个 SqlBasicCall，它的操作符是 AS，被解析为 SqlAsOperator，两个操作数别离是 source_table(SqlIdentifier) 和 s(SqlIdentifier)；
• joinType：代表连贯的类型，所有反对解析的 JOIN 类型都定义在 org.apache.calcite.sql.JoinType 中，joinType 被解析为 SqlLiteral，它的值即是 JoinType.INNER；
• right：代表 JOIN 的右表，因为咱们用了别名，因而这里是一个 SqlBasicCall，它的操作符是 AS，被解析为 SqlAsOperator，两个操作数别离是 dim_table(SqlIdentifier) 和 d(SqlIdentifier)；
• conditionType：代表 ON 关键字，是一个 SqlLiteral；
• condition：与 3.1.2 的 where 类似，是一个对于条件判断的函数调用，SqlBasicCall，它的操作符是一个二元运算符 =，被解析为 SqlBinaryOperator，两个操作数别离是 s.id(SqlIdentifier) 和 d.id(SqlNumberLiteral)。

3.1.4 SqlIdentifier

SqlIdentifier 翻译为标识符，标识 SQL 语句中所有的表名、字段名、视图名（* 也会辨认为一个 SqlIdentifier），根本所有与 SQL 相干的解析校验，最初解析都到 SqlIdentifier 这一层完结，因而也能够认为 SqlIdentifier 是 SqlNode 中最根本的结构单元。SqlIdentifier 有一个字符串列表 names 存储理论的值，用列示意因为思考到全限定名，如 s.id，在 names 会占用两个元素格子，names[0] 存 s，names[1] 存 id。

3.1.5 SqlBasicCall

SqlBasicCall 蕴含所有的函数调用或运算，如 AS、CAST 等关键字和一些运算符，它有两个核心成员变量：operator 和 operands，别离记录这次函数调用 / 运算的操作符和操作数，operator 通过 SqlKind 标识其类型。

3.2 JavaCC

Calcite 没有本人造词法、语法分析的轮子，而是采纳了支流框架 JavaCC，并联合了 Freemarker 模板引擎来生成 LL(k）parser，JavaCC（Java Compiler Compiler）是一个用 Java 语言写的一个 Java 语法分析生成器，它所产生的文件都是纯 Java 代码文件。用户只有依照 JavaCC 的语法标准编写 JavaCC 的源文件，而后应用 JavaCC 插件进行 codegen，就可能生成基于 Java 语言的某种特定语言的分析器。

Freemarker 是一个模板渲染引擎，通过它建设内置模板，联合自定义的拓展语法能够疾速生成咱们想要的语法形容文件。

在 Calcite 中，Parser.jj 是 Calcite 内置的模板文件，.ftl 为自定义拓展模板，config.fmpp 用于申明数据模型，首先 Calcite 通过 fmpp-maven-plugin 插件生成最终的 Parser.jj 文件，再利用 javacc-maven-plugin 插件生成对应的 Java 实现代码，具体的流程图如下：

4. Catalog

Catalog 保留着整个 SQL 的元数据和命名空间，元数据的校验都须要通过 Catalog 组件进行，Catalog 中最要害的几个构造如下：

这些构造大抵能够分为三类：

• 元数据管理模式和命名空间；
• 表元数据信息；
• 类型零碎。

Calcite 的 Catalog 结构复杂，但咱们能够从这个角度来了解 Catalog，它是 Calcite 在不同粒度上对元数据所做的不同级别的形象。首先最细粒度的是 RelDataTypeField，代表某个字段的名字和类型信息，多个 RelDataTypeField 组成了一个 RelDataType，示意某行或某个标量表达式的后果的类型信息。再之后是一个残缺表的元数据信息，即 Table。最初咱们须要把这些元数据组织存储起来进行治理，于是就有了 Schema。

5. SQL validator

Calcite 提供的 validator 流程极为简单，但概括下来次要做了这么一件事，对每个 SqlNode 联合元数据校验是否正确，包含：

• 验证表名是否存在；
• select 的列在对应表中是否存在，且该匹配到的列名是否惟一，比方 join 多表，两个表有雷同名字的字段，如果此时 select 的列不指定表名就会报错；
• 如果是 insert，须要插入列和数据源进行校验，如列数、类型、权限等；
• ……

Calcite 提供的 validator 和后面提到的 Catalog 关系严密，Calcite 定义了一个 CatalogReader 用于在校验过程中拜访元数据 (Table schema)，并对元数据做了运行时的一些封装，最外围的两局部是 SqlValidatorNamespace 和 SqlValidatorScope。

• SqlValidatorNamespace：形容了 SQL 查问返回的关系，一个 SQL 查问能够拆分为多个局部，查问的列组合，表名等等，当中每个局部都有一个对应的 SqlValidatorNamespace。
• SqlValidatorScope：能够认为是校验流程中每个 SqlNode 的工作上下文，当校验表达式时，通过 SqlValidatorScope 的 resolve 办法进行解析，如果胜利的话会返回对应的 SqlValidatorNamespace 形容后果类型。

在此基础上，Calcite 提供了 SqlValidator 接口，该接口提供了所有与校验相干的外围逻辑，并提供了内置的默认实现类 SqlValidatorImpl 定义如下：

public class SqlValidatorImpl implements SqlValidatorWithHints {
    // ...
  
  final SqlValidatorCatalogReader catalogReader;
  
  /**
   * Maps {@link SqlNode query node} objects to the {@link SqlValidatorScope}
   * scope created from them.
   */
  protected final Map<SqlNode, SqlValidatorScope> scopes =
      new IdentityHashMap<>();

  /**
   * Maps a {@link SqlSelect} node to the scope used by its WHERE and HAVING
   * clauses.
   */
  private final Map<SqlSelect, SqlValidatorScope> whereScopes =
      new IdentityHashMap<>();

  /**
   * Maps a {@link SqlSelect} node to the scope used by its GROUP BY clause.
   */
  private final Map<SqlSelect, SqlValidatorScope> groupByScopes =
      new IdentityHashMap<>();

  /**
   * Maps a {@link SqlSelect} node to the scope used by its SELECT and HAVING
   * clauses.
   */
  private final Map<SqlSelect, SqlValidatorScope> selectScopes =
      new IdentityHashMap<>();

  /**
   * Maps a {@link SqlSelect} node to the scope used by its ORDER BY clause.
   */
  private final Map<SqlSelect, SqlValidatorScope> orderScopes =
      new IdentityHashMap<>();

  /**
   * Maps a {@link SqlSelect} node that is the argument to a CURSOR
   * constructor to the scope of the result of that select node
   */
  private final Map<SqlSelect, SqlValidatorScope> cursorScopes =
      new IdentityHashMap<>();

  /**
   * The name-resolution scope of a LATERAL TABLE clause.
   */
  private TableScope tableScope = null;

  /**
   * Maps a {@link SqlNode node} to the
   * {@link SqlValidatorNamespace namespace} which describes what columns they
   * contain.
   */
  protected final Map<SqlNode, SqlValidatorNamespace> namespaces =
      new IdentityHashMap<>();
  
  // ...
}

能够看到 SqlValidatorImpl 当中有许多 scopes 映射 (SqlNode -> SqlValidatorScope) 和 namespaces (SqlNode -> SqlValidatorNamespace)，校验其实就是在一个个 SqlValidatorScope 中校验 SqlValidatorNamespace 的过程，另外 SqlValidatorImpl 有一个成员 catalogReader，也就是下面说到的 SqlValidatorCatalogReader，为 SqlValidatorImpl 提供了拜访元数据的入口。

6. Query optimizer

query optimizer 是最为庞杂的一个组件，波及到的概念多，首先，query optimizer 须要将 SqlNode 转成 RelNode（SqlToRelConverter），并应用一系列关系代数的优化规定（RelOptRule）对其进行优化，最初将其转化成对应引擎可执行的物理打算。

6.1 SqlNode 到 RelNode

SQL 是基于关系代数的一种 DSL，而 RelNode 接口就是 Calcite 对关系代数的一个形象示意，所有关系代数的代码构造都须要实现 RelNode 接口。

SqlNode 是从 sql 语法角度解析进去的一个个节点，而 RelNode 则是一个关系表达式的形象构造，从关系代数这一角度去示意其逻辑构造，并用于之后的优化过程中决定如何执行查问。当 SqlNode 第一次被转化成 RelNode 时，由一系列逻辑节点（LogicalProject、LogicalJoin 等）组成，后续优化器会将这些逻辑节点转化成物理节点，依据不同的计算存储引擎有不同的实现，如 JdbcJoin、SparkJoin 等。下表是一个对于 SQL、关系代数以及 Calcite 构造的映射关系：

注：Calcite 列只列举了较常见的状况，而非和后面两列严格的映射规范。

一个简略的 SQL 例子通过 query optimizer 解决后失去的后果如下：

图来自 Introduction to Calcite

6.2 RelNode 优化

在将 SqlNode 转为 RelNode 后，咱们就能够通过关系代数的一些规定对 RelNode 进行优化，这些“规定”在 Calcite 体现为 RelOptRule。

RelNode 有一些物理特色，这部分特色就由 RelTrait 来示意，其中最重要的一个是 Convention（Calling Convention），能够了解是一个特定数据引擎协定或数据源约定，同数据引擎的 RelNode 能够间接相互连接，而非同引擎的则须要通过 Converter 进行转换（通过 ConverterRule 匹配）。

比拟常见的优化规定如：

• 剪除不必的 fields；
• 合并 projections；
• 将子查问转为 join；
• 对 joins 重排序；
• 下推 projections；
• 下推 filters；
• ……

7. 利用场景

基于 Calcite 良好的可插拔个性，目前有许多基于 Calcite 二次开发的 SQL 解析引擎，如 Flink，该节列举了一些能够基于 Calcite 拓展的工作和思路。

7.1 拓展 SQL 语法解析

基于 JavaCC 实现词法分析器（Lexer）和语法分析器（Parser），比方 Flink 在 Calcite 原生的 Parser.jj 模板之上自定义拓展了 SqlCreateTable 和 SqlCreateView 两种 Parser，反对解析 CREATE TABLE ... 和 CREATE VIEW ... 的 DDL，同时须要拓展对应的 Java 类。。

7.2 拓展元数据校验的自定义数据结构

通过拓展 Schema 和 Table 等接口能够自定义注入元数据的机会以及格局，比方 Flink 通过命令式编程建设嵌套 VIEW 的数据依赖（假如 viewA 依赖 viewB 的数据，则须要先手动调用 API 解析 viewB），有的框架则批量读取，本人建设拓扑图来解决数据依赖问题。对于元数据格式 Flink 基于 Table 接口实现了 QueryOperationCatalogViewTable 来示意表、视图，并为其设计了对立的 TableSchema 收集 RelDataType 信息。

7.3 拓展类型解析

当碰着一些 Calcite 原生不反对的简单类型，能够通过拓展 RelDataTypeFactory 等相干类型接口拓展类型解析。

7.4 拓展具体的规定优化

能够自定义一些非凡的 Rule，调用 HepProgramBuilder 的 addRuleInstance 办法注册到 planner 里，这就能够在 RelNode 的优化过程中匹配到咱们的自定义 Rule，并在胜利匹配的状况下进行优化。

这几种场景从流程复杂度的角度来看是 SQL 语法解析 > 元数据校验 > 类型解析 > 规定优化，但在理论拓展过程中，集体认为难度程序反而是相同的，因为 SQL 语法解析和元数据校验的流程尽管很简单，但封装欠缺，类型解析须要思考的适配点较多是一个难点，而规定优化则须要深厚的 SQL 根底和一些理论知识，理论拓展过程反而 his 最为艰难的。

8. 参考资料

1. Calcite 概念阐明
2. Apache Calcite 解决流程详解
3. https://zhuanlan.zhihu.com/p/…
4. RelNode 和 RexNode
5. Introduction to Apache Calcite
6. Apache Calcite：A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources