一条 SQL 的查询优化之旅【下】
当一条 SQL 语句到达引擎，首先通过的是 SQL 解析器，SQL 解析器将用户输入的 SQL 语句转换为一棵抽象语法树，同时在这个过程里，它还会对SQL进行词法和语法校验，如果输入的 SQL 有词法或语法问题，会在这个阶段收到错误提示。
在 Calcite 中，一棵抽象语法树通常用SqlNode来表示。以下面这条 SQL 为例：
这条SQL在经过 Calcite 解析后，形成的 AST 抽象语法树如下：
图中的每一个节点都是一个 SqlNode，SqlNode作为抽象语法树的顶级抽象，相互关联组成了一颗大的抽象语法树。
Calcite 支持通过两种方式进行 SQL 解析：即基于 Java CC（Java Compiler Compiler）的 SQL 解析以及基于 Anltr 的 SQL 解析。Calcite 默认基于 Java CC 来做 SQL 解析：Calcite 能够基于Parser.jj 文件，使用 Java CC 技术，动态生成 SQL 解析实现类（XXXParserImpl），Calcite 本身内置有一个 Parser.jj 文件，如果我们需要自定义 SQL 语法的时候，我们也可以使用 FMPP 技术，自定义 ftl和 config.fmpp 文件的内容，来控制最终需要生成的Parser.jj 的内容，从而实现自定义 SQL 语法。
config.fmpp 主要定义 SQL 语法中的关键字、外部引入的类（如自定义的 SqlNode）、以及一些 SQL 解析方法定义等等，具体的实现一般会在 ftl 文件中。以 Apahce Flink 项目举例，组成其 SQL 解析器模块的主要文件如下：
3.2 Calcite SQL 校验和关系代数转换流程
3.2.1 Calcite SQL 元数据校验
上文我们提到：SQL 解析后会形成一棵 SqlNode 的抽象语法树，下一步我们需要对这棵树进行元数据验证，以校验SQL的合法性。这里需要注意，经过元数据验证之后的SqlNode，其本质还是一棵SqlNode 树，之后依然需要经过 SqlNode 到RelNode关系代数的转换，才会形成一棵由RelNode组成的关系代数节点树。
在 Calcite 元数据验证阶段，其主要验证三个点：
- 对 SQL 语句中的 Table Schema 进行校验，如 Table 存不存在，Column 存不存在
- 对 SQL 语句中函数进行校验，如函数是否存在
- 针对数据类型的校验，如函数中的参数数据类型和函数定义是否匹配
Calcite 中元数据验证源码的核心方法入口为：SqlValidatorImpl.validate()，SqlValidatorImpl的使用，需要配合SqlOperatorTable，SqlValidatorCatalogReader，RelDataTypeFactory三个类使用。SqlValidatorImpl 的初始化构造器的源码如下：
初始化 SqlValidatorImpl 需要传入三类参数：
- SqlOperatorTable-生产函数和 SQL Operator 的工厂，为SqlValidatorImpl 提供函数、SQL 操作符（比如 >，=，<）的元数据相关信息
- SqlValidatorCatalogReader - 提供 Table Schema 和 Rowcount 等相关信息，其中CatalogReader 封装了从底层的元数据存储中读取 Table Schema 的数据接口
- RelDataTypeFactory 和RelDataTypeSystem – 为SqlValidatorImpl 提供所有需要识别的数据类型，以及精度相关的信息。
要验证一个 SQL 中用到的函数，我们可以从自定义实现的SqlOperatorTable中进行查找， 一般有两种方法：lookupOperatorOverloads 和getOperatorList ，lookupOperatorOverloads主要逻辑是将某类函数的具体信息查找出来，并添加到输入参数operatorList 集合中。
对于数据类型以及默认的精度等信息，在Calcite中可以从RelDataTypeFactory和RelDataTypeSystem 中获取，一般这两个接口需要自定义扩展实现。 虽然 Calcite 中已经有这两个接口的默认实现，但一般我们需要的类型以及精度信息，不会和 Calcite 内置实现完全一样，所以还是需要自己复写这两个接口中的部分方法。
SqlValidatorCatalogReader对上层元数据验证提供了 Table 信息获取接口，同时屏蔽了底层获取具体 Table 元数据的实现细节。根据 SQL 查询语句中 From 后面表的 paths，调用该接口，可获取 Table 的 Schema Table 的 RowCount ，以及PreparingTable等信息。
3.2.2 Calcite 关系代数转换流程
进行元数据校验之后，我们得到的还是一棵SqlNode 抽象语法树，接下来我们需要将其转换为RelNode 关系代数 Tree，后续才能基于关系代数优化理论对其进行优化。
关系代数转化阶段和元数据验证阶段是紧密在一起的，经过元数据验证阶段后，每个SqlNode输出的字段和数据类型信息都被添加至SqlValidatorImpl 中的nodeToTypeMap 集合中，这样从SqlNode转到相应的RelNode时，每个RelNode 的数据类型，也都能够被 bind 上。
Calcite 使用SqlToRelConverter将SqlNode 转换为RelNode ，其入口方法是convertQuery()，之后会调用convertQueryRecursive方法，底层最终调用 convertXXX 方法（如下图所示），递归遍历抽象语法树将SqlNode 转换为RelNode ，至此，SqlNode 转 RelNode 转换完毕。
四、Calcite SQL 执行计划生成与优化
4.1 Calcite RBO 启发式优化
SqlNode转换为RelNode关系代数节点树后，Calcite会对其分别进行 RBO（Rule-Based Optimization）和 CBO （Cost-Based Optimization）优化。RBO 优化一般会结合一些预定且的逻辑优化规则，一般发生在 CBO 优化之前。RBO 改变的是计划的逻辑，而不是物理实现，这里只是对逻辑计划做等价转换。如果需要更改计划的物理实现（Convention），需要结合ConverterRule来进行实现。
下面以 Calcite FilterIntoJoinRule 优化规则进行举例，FilterIntoJoinRule 规则主要尝试将 Join 之上的 Filter 过滤条件，下推到 Join RelNode 下面，这样的好处是能够提前对数据进行过滤，减少进入 Join RelNode 的数据量，从而降低计算成本。 下图左边部分是输入的原始计划，右边部分是经过FilterIntoJoinRule 优化后的计划，可以看到，Filter RelNode 已经下推到 Join 之下了。
在Calcite 中，RBO 优化主要使用 HepPlanner 来实现，在HepPlanner 优化之前，会将 SQL Query 计划 Tree 中的每一个 RelNode，先转换为 HepRelVertex 节点， 通过 HepPlanner 的 setRoot 方法，从根节点，递归的将所有 RelNode 加入到图中，同时根据每个 RelNode 以及输入信息，构建图的边，在这个过程中，构建 HepRelVertex，再构建出一个 DAG（有向无环图），从设置的根节点的 RelNode，按照预设定遍历顺序，进行 RBO 优化。
那么 Calicte 为什么会将RelNode 转换为HepRelVertex 呢？ 因为在进行 RBO 的时候，需要记录RelNode转换前与转换后的相关信息，而RelNode本身只能记录其输入信息，无法记录其输出的节点信息，所以这里引入 HepRelVertex 。CalciteHepPlanner节点优化遍历方式有以下四种：
- ARBITRARY，DEPTH-FIRST -- 本质上两者底层都是从深度优先遍历和优化，核心区别在于：当一个规则作用于计划时，两者都会从新产生的节点进行遍历，顺序为 DEPTH-FIRST 时，如果之前已经应用过某个规则，那么在之后转换的新的计划 Tree 中，不会再使用该规则，所以它比 ARBITRARY 效率更高。
- BOTTOM-UP -- 从叶子节点到根节点，自低向上进行遍历和适用规则优化。
- TOP-DOWN -- 从根节点到叶子阶段，自顶向下进行遍历优化。
最终经过 RBO 优化，会产生一棵优化后的逻辑计划的关系代数Tree。当然，RBO 优化也有一定的缺陷性，因为 RBO 优化阶段更倾向于一定益的优化规则，往往会导致可运用的优化规则是有限的，其适用场景相对有限。同时 RBO 由于只是根据先验经验来选择适用一定的规则集合，没有结合计划实际适用的计算资源来进行判定，可能在某些场景下，RBO 优化会适得其反。
4.2 Calcite 物化视图改写
在 RBO 优化之后，可以使用物化视图来对查询进行优化。物化视图本质是特定逻辑下的预计算结果。 Calcite 中支持两种物化视图改写方式：基于 UnifyRule 的局部匹配替换改写和基于MaterializedViewRule 结构化信息改写。前者可以在 CBO 优化之前单独进行优化，配合可用的物化RelOptMaterialization 集合，使用SubstitutionVisitor 来进行改写。基于MaterializedViewRule结构化信息改写，从本质上来讲，它就是优化规则的一种实现，需要添加到VolcanoPlanner 优化规则集合中，和 CBO 优化一起来进行配合使用。
使用基于UnifyRule 进行局部匹配替换的物化改写时，需要传入三类信息：物化视图的计算逻辑 A、SQL 查询计算逻辑 B、代替物化视图计算逻辑的 C，其原理概括来说，是在 SQL 查询计划中，自顶向下找到和物化视图计算计划中相等的子集顶层的RelNode E，然后从 E 之上，使用UnifyRule，自低向上变换 Query 的计划结构，最终在 SQL 查询计划中，使用计划 C 来替换 B 。
