PaperReading | Apache Calcite A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources

简述

Calcite Paper 地址: https://arxiv.org/pdf/1802.10233.pdf

Apache Calcite 是一个基础的软件框架，能够为许多流行的开源数据处理系统提供查询处理、优化和查询语言的能力支持，例如：Apache Hive，Apache Storm，Apache Flink，Druid Calcite 包含查询优化器、查询处理器以及适配器等组件，模块化的查询优化器可支持扩展，其内置上百种优化规则；查询处理器，能够支持各种各样的查询语言；而适配器的设计，可以支持各种异质数据模型或存储的适配，诸如：关系型、半结构化、流式以及地理空间数据等。这种灵活（Flexible）、可嵌入（Embeddable）且可扩展的架构设计使得 Apache Calcite 在大数据处理框架上，成为一个很好的选择
Calcite 主要是为了解决 在数据处理领域中专用的存储计算引擎在查询优化和语言支持重复的问题，提供数据管理系统中通用的查询执行、优化的功能. 其本身没有实现 数据存储和数据管理功能 比如Hive是构建在Hadoop上的数据仓库 随着Hive的批处理转向SQL的交互式查询其最需要解决的就是查询优化器 所以很多框架使用Apache Calcite作为其优化器且集成度越来越高. Calcite 基于Hadoop生态 提供了跨系统的支持，灵活的查询优化器 从规则到成本模型 每一个优化器组件都是可插拔可扩展的.

整体架构

Calcite架构中 核心在于Optimizer 优化器 一个Optimizer Engine包含三个组成部分. rule 匹配规则 Calcite内置了上百种Rules 来优化relational expression 也支持自定义的rules; metadata providers 向优化器提供信息 有助于指导优化器向着目标(减少整体cost)进行优化, 信息主要是行数、table 哪一列 也包含RelNode树中执行的subexpression cost 函数; planner engines 主要是触发rules 来达到指定目标 比如 cost-based optimizer (CBO) 的目标来减少Cost.

查询代数

操作符（Operators）

关系代数是 Calcite 的核心部分。除了最常见的诸如过滤（filter）、映射（project）、关联（join）等，Calcite 提供了额外的操作符来满足不同的需求，比如能够简单表示复杂操作或者更有效识别优化时机。举例来说，对于 OLAP，决策支持和流应用来说，使用窗口函数来表达复杂分析功能已经变得很常见（例如，按时间段、数值或行数进行窗口滑动）。为此，Calcite 引入了窗口（window）操作符来封装窗口的定义（上下限，分区等）以及窗口上执行的聚合函数。

特质（Traits)

Calcite 没有使用不同的实体来表示逻辑和物理操作符。相反，其使用特质来描述与操作相关的物理属性。这些特质能够帮助优化器来评估不同替代计划的执行成本。修改特质的值并不会改变需要评估的逻辑表达式，即，指定操作符生成的行仍然是一样的

在优化过程中，Calcite 会尝试在一些关系表达式上强制执行指定的特质，例如，某些列的排序顺序。关系操作符实现了一个转换接口，用来标识如何将将表达式的特质从一个值转换为另一个值。
Calcite 包含了常用的一些特质，这些特质描述了关系表达式生成的数据物理属性，例如排序（ordering），分组（grouping）和分区（partitioning），和 SCOPE 优化器类似，Calcite 优化器可以推理这些属性，并且利用这些推理来找到不必要的操作计划。例如，若排序操作符的输入已经正确排序（行排序与后台系统的行排序相同），那么排序操作就可以移除。
除了这些特性，Caclite 还包括一个重要的特质，即调用约定（calling convention）。本质上，特质表示表达式执行的数据处理系统。将调用约定当作特质，可以使 Calcite 能够保持透明的优化查询，对于跨引擎执行而言，该约定被看作是其他物理属性。

如图所示，做 Products 和 Orders 的跨存储关联， Products 保存在 MySQL 中，而 Orders 表则保存在 Splunk 中。首先， 在 Splunk 中扫描 Orders表，在 Mysql 中扫描 Products表，而关联操作在逻辑上没有选择具体的执行引擎。而且，图 2 上的 SQL 查询包含过滤操作，该操作通过适配器具体的规则， 将过滤操作下推至 splunk 中执行。对于关联操作，一种可行的解决方案是将关联操作转成 Spark 实现，且将 MySQL 和 Splunk 的输入也转换至 Spark 实现。还一种更有效的实现方式，Splunk 利用 ODBC 方式执行 MySQL 表的查询，如此就可以实现整个操作在 Splunk 引擎中执行

适配器

Calcite 中的适配器一种架构模式，其定义了对各种数据源如何进行访问。图 3 描绘了适配器的组件，从图上我们可以看出，适配器主要由模型(model)，Schema 和 SchemaFactory 组成。模型定义了访问数据源所需要属性的结构，Schema 则是模型中数据的定义，包括数据格式和布局。数据本身则是通过表进行访问，Calcite 借助适配器中关于表的定义来读取数据，查询的执行都会依赖表的定义。另外，适配器可以向计划器中添加自己的一组规则，例如如何从将各种类型的逻辑关系表达式向具体适配器约定的关系表达式转换。SchemaFactory 则从模型中获取元数据信息并生成 schema。

查询处理与优化

查询优化器是 Calcite 框架中的主要组件，通过重复应用计划规则于关系表达式上来达到优化查询的目的。Calcite 成本模型指导整个流程，而计划引擎尝试生成与原表达式相同语义且成本更低的可替代表达式。优化器中每个组件都是可扩展的，用户可以添加关系操作、规则、成本模型和统计。

计划规则（Planner rules）

Calcite 包含一系列计划规则用于转换表达式树。特别地，规则匹配表达式树的指定模式并执行表达式的转换，该转换过程会保留原有表达式的语义。Calcite 内置了数百个优化规则，对于依赖 Calcite 进行优化的数据处理系统来说，也可以定制或重写已有的规则。例如，Calcite 为 Apache Cassandra 提供了一个适配器，Cassandra 是一个宽列式存储，其按表中列的子集对数据进行分区，然后在每个分区中根据其余列的子集进行排序

元数据（Metadata providers）

元数据是 Calcite 优化器的重要组成部分，其有两个主要目的：1、指导优化器如何降低整体查询开销成本；2、当应用优化规则时，元数据为这些规则提供相应的信息。元数据主要职责是为优化器提供相应的信息。特别是，Caclite 中默认元数据提供了函数实现，包括：操作树中执行子表达式的成本开销、执行行数、执行表达式结果数据的大小以及执行的最大并行度。反过来，其还可以提供有关计划结构的信息，例如，存在具体树结点下的过滤条件。
Calcite 为数据处理系统提供了注入自定义元数据的接口。这些系统可以重写 Calcite 原有的元数据提供者(providers)，或是提供自定义的新元数据函数以用于优化阶段。然而，对于大多数人而言，提供输入数据统计信息就已经足够，包括表的行数、表的大小以及给定列的值是否唯一。其余工作交给 Calcite 来完成即可。
由于元数据提供是可插拔的，所以其编译和执行是使用 janino 来完成，janino 是 Java 的一个轻量级编译器。该实现包括可显著提高性能的元数据结果缓存。例如当我们需要计算多种类型的元数据（指定关联的基数、平均行大小以及可选择性）时，，且这些计算需要依赖其输入

计划引擎（Planner engines）

计划引擎的主要功能是不断触发优化规则，直至达到最优结果。当前，Calcite 默认提供了两种计划引擎，用户也可以按照 Calcite 规范，自定义计划引擎。
第一种是基于成本的计划引擎，该计划引擎以降低整个查询的执行成本为目标。该计划引擎使用的动态编程算法，类似于 Volcanno，可以创建和跟踪不同可选计划，这些计划由规则触发而生成。首先，需要向计划引擎注册表达式以及基于表达式的属性和输入摘要。当在表达式 e1上触发某规则，那么该规则会生成新的表达式 e2 ，然后计划引擎会将 e2 添加至 e1 所属的等价表达式集合 Sa中。此外，计划引擎会为该新的表达式生成一个摘要，该摘要将会与之前注册的其他表达式摘要进行比较。如果发现与一个 e3 的表达式摘要相似，而这个表达式 e3属于 Sb集合，那么计划引擎会合并 Sa和 Sb两个集合。该过程直至达可配置的固定点才会停止。需要指出的是，计划引擎会搜索所有的规则空间以保证所有的规则都应用至整个表达式，或者采用启发式的方法来停止优化，当再进行计划迭代时，所花的成本不超过指定阈值。借助元数据提供的信息，成本函数可以判定选择使用哪个优化规则。Calciter 提供的默认成本函数实现，将给定表达式所需要 CPU、IO 以及内存资源也考虑进来。
第二种计划引擎是一个穷举计划引擎，该计划引擎穷举计划规则直至生成一个不再发生变化的表达式。这种计划引擎有助于快速执行规则，不需要考虑每个表达式的执行成本。
用户可以根据具体的需求场景来选择采用哪种计划引擎，当需求发生变化时，也可以在两个计划引擎之间进行切换。或者，用户可以选择生成多个阶段优化逻辑，并将之应用到优化过程中的衔接阶段。重要的是，该两种计划引擎通过检索不同查询计划，能够帮助 Calcite 用户减少整体的优化时间

物化视图（Materialized views）

数据仓库中加速查询速度的最强大技术之一就是相关摘要的预计算或物化视图。Calcite 的适配器以及依赖 Calcite 的项目在物化视图上也有相应的解决方案。例如，Cassandra 允许用户基于已有表自定义物化视图，且物化视图由系统自动来维护。类似 Cassandra 的引擎，将其视图暴露给 Calcite。Calcite 的优化器可以使用这些视图来重写查询语句，而不是查询原始表。且 Calcite 提供了两种物化视图重写算法的实现。第一种方法是基于视图替换算法。该算法的目的是利用了物化视图表达式来替代关系代数树中的等价部分。算法过程如下：1、将物化视图的 scan 操作符以及物化视图定义计划注册到计划引擎中；2、尽量统一计划中触发的转换规则。视图不需要与被替换的查询表达式完成匹配，因为该替换算法可以实现部分重写，其中包括额外的操作符来计算所需的表达式，例如：残留谓词条件过滤器。另外一种算法是基于 lattices。一旦数据源被声明为 lattice，Calcite 会将每一个物化表示为一个 tile，优化器能够利用tile来优化查询。一方面，在星型模式组织的数据源上，该重写算法匹配表达式非常有效，星型模式组织的数据源在 OLAP 中则很常见。另一方面，因其对底层架构有限制，导致其比视图替换的限制性更高。

下篇文章将会深入分析其优化器具体实现原理.