Apache Calcite

前言

之前的名称叫做 optiq，optiq 起初在 Hive 项目中，为 Hive 提供基于成本模型的优化，2014 年 5 月 optiq 独立出来，成为 社区的孵化项目，主要作用是提供标准的SQL语言查询底层各种数据源的一个工具，可以将各种SQL语句解析成抽象语法术AST( Tree)， 之后通过操作AST就可以把SQL中所要表达的算法与关系体现在具体代码之中。

的目标是"one size fits all "（一种方案适应所有需求场景），希望能为不同计算平台和数据源提供统一的查询引擎，成为动态的数据管理系统（其实并没有数据库，需要我们在代码里告诉，虚拟出来的表是什么、字段是什么、字段类型是什么等，整体抽象为一个个，对于我们来说就查虚拟出来东西，不用关心底层真正对接了哪些数据源），并以类似传统数据库的访问方式（SQL 和高级查询优化）来访问数据。

使用作为SQL解析与处理引擎有Hive、Drill、Flink、和Storm，可以肯定的是还会有越来越多的数据处理引擎采用作为SQL解析工具。

特性及功能 架构

2种常用场景：

场景2是 最受欢迎的和最擅长的场景， 相比查询执行、连接数据源， 更擅长的是制造查询语言，解析查询， 和查询优化 。为什么这么说呢 , 那就要看看它的架构了：

1、SQL and 是的SQL 语言的解释器，它将用户用SQL语言编写的查询解析城 ，并验证它的合法性 。

2、Query （优化器）是 的核心，它接受查询计划，输出优化的查询计划 ，主要包含三个部分：

这三个组件是 可扩展部分，因此与外部系统有连接 。

3、黄色框框Data （ 简称DPS)与蓝色框框有虚线连接，是DPS 对 的扩展部分。 这里的Data 所指的就是场景2里的查询引擎。它通过扩展 和 rules , 向优化器提供更准确的元数据信息，更适合的代价模型， 更高效的优化规则， 利用 优化器产生最优化查询计划。

4、 是一种绕过SQL解析，直接生成关系表达式的工具。 这种方式适用于单元测试。

用数据流图的方式描述一下 和Data 的交互， 更容易理解：

解析 SQL， 把 SQL 转换成为 AST （ Tree，抽象语法树），在 中用 来表示；

语法检查，根据数据库的元数据信息进行语法验证，验证之后还是用 表示 AST 语法树；

语义分析，根据 及元信息构建 树，也就是最初版本的逻辑计划（ Plan）；

逻辑计划优化，优化器的核心，根据前面生成的逻辑计划按照相应的规则（Rule）进行优化；

物理执行，生成物理计划，物理执行计划执行。

中的概念

1、关系代数表达式：SQL 形式化语言——关系代数的博客-CSDN博客_sql关系代数

2、等价交换原理：「 数据库原理 」查询优化（关系代数表达式优化） - - 猫既吾命

3、两种优化方式：

基于规则的优化器（Rule-Based ，RBO）：根据优化规则对关系表达式进行转换，这里的转换是说一个关系表达式经过优化规则后会变成另外一个关系表达式，同时原有表达式会被裁剪掉，经过一系列转换后生成最终的执行计划。

RBO 中包含了一套有着严格顺序的优化规则，同样一条 SQL，无论读取的表中数据是怎么样的，最后生成的执行计划都是一样的。同时，在 RBO 中 SQL 写法的不同很有可能影响最终的执行计划，从而影响执行计划的性能。

基于成本优化（CBO）：

基于代价的优化器(Cost-Based ，CBO)：根据优化规则对关系表达式进行转换，这里的转换是说一个关系表达式经过优化规则后会生成另外一个关系表达式，同时原有表达式也会保留，经过一系列转换后会生成多个执行计划，然后 CBO 会根据统计信息和代价模型 (Cost Model) 计算每个执行计划的 Cost，从中挑选 Cost 最小的执行计划。

CBO 中有两个依赖：统计信息和代价模型。统计信息的准确与否、代价模型的合理与否都会影响 CBO 选择最优计划。 从上述描述可知，CBO 是优于 RBO 的，原因是 RBO 是一种只认规则，对数据不敏感的呆板的优化器，而在实际过程中，数据往往是有变化的，通过 RBO 生成的执行计划很有可能不是最优的。事实上目前各大数据库和大数据计算引擎都倾向于使用 CBO，但是对于流式计算引擎来说，使用 CBO 还是有很大难度的，因为并不能提前预知数据量等信息，这会极大地影响优化效果，CBO 主要还是应用在离线的场景。

执行流程

sql：

select u.id as user_id, u.name as user_name, j.company as user_company, u.age as user_age 
from users u join jobs j on u.name=j.name
where u.age > 30 and j.id>10
order by user_id

Step 1: SQL parse（SQL -> ）

使用 进行 Sql 解析的代码如下：

SqlParser parser = SqlParser.create(sql);
SqlNode sqlNode = parser.parseStmt();

Calcite 使用 JavaCC 做 SQL 解析，JavaCC 根据 Calcite 中定义的 Parser.jj 文件，生成一系列的 java 代码，生成的 Java 代码会把 SQL 转换成 AST 的数据结构（这里是 SqlNode 类型）。与 Javacc 相似的工具还有 ANTLR，JavaCC 中的 jj 文件也跟 ANTLR 中的 G4文件类似。
​
Javacc 这里要实现一个 SQL Parser，它的功能有以下两个，这里都是需要在 jj 文件中定义的。
1. 设计词法和语义，定义 SQL 中具体的元素；
2. 实现词法分析器（Lexer）和语法分析器（Parser），完成对 SQL 的解析，完成相应的转换。

SQL 经过前面的解析之后，会生成一个 ：

Step 2: （–>）

经过上面的第一步，会生成一个 对象，它是一个未经验证的抽象语法树，下面就进入了一个语法检查阶段，我们知道 本身是不管理和存储元数据的，在检查之前，需要先把元信息注册到 中；这个检查会包括表名、字段名、函数名、数据类型的检查。进行语法检查的实现如下：

它的处理逻辑主要分为三步：

，将其标准化，便于后面的逻辑计划优化；

//rewrite 前
select u.id as user_id, u.name as user_name, j.company as user_company, u.age as user_age 
from users u join jobs j on u.name=j.name
where u.age > 30 and j.id>10
order by user_id
​
//rewrite 后
SELECT `U`.`ID` AS `USER_ID`, `U`.`NAME` AS `USER_NAME`, `J`.`COMPANY` AS `USER_COMPANY`, `U`.`AGE` AS `USER_AGE` 
FROM `TEST`.`USERS` AS `U` INNNER JOIN `TEST`.`JOBS` AS `J` ON `U`.`NAME`=`J`.`NAME`
WHERE `U`.`AGE` > 30 AND `J`.`ID`>10
ORDER BY `USER_ID`

注册这个 和 （这两个对象代表了其元信息）；

进行相应的验证，这里会依赖第二步注册的 和 信息。

Step3: 语义分析（–>）

经过上面的sql 解析，会生成一个 对象， 是抽象语法树AST的节点， 而 Rel 代表关系代数表达式( )， 所以这是一个AST节点变为关系表达式的过程，进过转化后生成的关系表达式为：

LogicalSort(sort0=[$0], dir0=[ASC])LogicalProject(USER_ID=[$0], USER_NAME=[$1], USER_COMPANY=[$5], USER_AGE=[$2])LogicalFilter(condition=[AND(>($2, 30), >($3, 10))])LogicalJoin(condition=[=($1, $4)], joinType=[inner])LogicalTableScan(table=[[USERS]])LogicalTableScan(table=[[JOBS]])

Step4: 优化阶段（–>）

第四阶段，也就是 的核心所在，优化器进行优化的地方，前面 sql 中有一个明显可以优化的地方就是过滤条件的下压，在进行 join 操作前，先进行 操作，这样的话就不需要在 join 时进行全量 join，减少参与 join 的数据量，优化后：

LogicalSort(sort0=[$0], dir0=[ASC])LogicalProject(USER_ID=[$0], USER_NAME=[$1], USER_COMPANY=[$5], USER_AGE=[$2])LogicalJoin(condition=[=($1, $4)], joinType=[inner])LogicalFilter(condition=[>($2, 30)])EnumerableTableScan(table=[[USERS]])LogicalFilter(condition=[>($0, 10)])EnumerableTableScan(table=[[JOBS]])