Archive for 七月, 2018

Apache Calcite是一个框架,主要提供了SQL相关语法解析(parse)和优化(optimazation)的功能。但其设计非常灵活,解析、优化可以拆分使用,从而将针对语法树的优化功能扩展至非SQL领域。2018年相关team在SIGMOD发表了一篇论文:https://arxiv.org/pdf/1802.10233。本文是该论文的学习笔记,非翻译,主要是自己读完之后的一些总结和思考。

为什么需要一个SQL相关的语法解析和优化库呢?

首先,从一个计算框架的研发者视角来看。SQL语法解析背后需要对关系代数的深刻理解,本身存在一定技术门槛,而且需要保证SQL解析的结果与ANSI-SQL等主流SQL流派的语义一致,还是需要下不少功夫的。而更重要的是,尤其在大数据量的分布式计算场景,一条SQL可以parse为多颗语义对等的语法叔,但彼此间的执行效率可能相差甚远,且在不同的数据结构、量级和计算逻辑上,优劣选择也不同。于是,如何优化就成为一个很重要且需要长期积累的topic。这两个方面,在分布式批量计算、流式计算、交互式查询等领域,都或多或少的存在共性,尤其是当把优化算法抽象为可插拔的Rules之后,就更加可能孵化出一个通用的框架来。

其次,从数据应用者的视角看,他/她需要整合多个计算框架,很可能需要跨平台的查询分发和优化(Calcite给出的例子是,当你的数据pipeline里既包含ES,又包含Spark、druid时),如何集成

于是,Apache Calcite应运而生,虽然论文将其定义为一个完整的query processing system,但我更倾向于认为它是一个非常灵活的编程框架或瑞士军刀一样的lib库。说他是编程框架,是从可插拔的优化Rules角度,以及Calcite提供的用于对接底层数据源的Adaptor模式而言;而lib库的方式则是针对大多数使用者,例如Apache Flink,将其作为工具库,嵌入在自身sql处理的流程当中。

Calcite由以下框图中的组件组成:
  • query parser and validator,将输入的字符串类型的SQL翻译为关系操作符(relational operators)树。在validate过程中,Calcite需要了解相关table/view的schema,最简单的方式是直接通过tutorial里的json格式定义schema,此外其还提供了org.apache.calcite.prepare.CalciteCatalogReader等方式,使用者可以自行传入table schema等catalog信息。
  • query optimizer,顾名思义,它会优化关系操作符树。Optimizer依赖一个静态的planner engine、一组可插拔的planner rules,以及通过metadata providers提供的动态元数据。Calcite提供了两个内置的planner engines,Cost-Based Planner Engine,以及Exhaustive Planner,用户也可以自行实现自己的规则引擎。引擎按照某种规则遍历planner rules,直到满足停止条件;而rule可能使用metadata作为决策参数。

屏幕快照 2018-07-26 下午5.09.33

Calcite的灵活之处在于parser和optimizer可以分开单独使用,从而满足以下场景:
  • SqlParser,某些成熟计算平台可能希望支持SQL以降低接入门槛,此时可以将calcite作为lib库使用,构造schema metadata,调用SqlParser::parseStmt()和SqlValidator::validate(SqlNode )即可
  • SqlParser + Optimizer,不但托管了SQL翻译过程,也将优化步骤交给Calcite处理
  • Optimizer,单独使用Calcite作为逻辑计划的优化器,可以参考Cost-based Query Optimization in Apache Phoenix using Apache Calcite
从上面可以看到由于optimizer的输入被抽象为逻辑计划,从而使其可以脱离SQL而独立使用。
在深入各个组件之前,需要先明确两个概念:
  • Operators:数据处理的行为。包括传统的行为,例如filter、project、join等,分别对应标准SQL的where、select、join等。以及Calcite扩展的一些行为,例如用于流式SQL的window operator
  • Traits:Operator上可以附带traits,用于描述一些与数据处理无关的行为。包括传统的行为,例如ordering、grouping、partitioning;以及Calcite为了处理跨计算引擎而引入的calling convention traits
我的理解是(没有读源码,不敢100%确定),在优化过程中,operators可以被调整顺序或合并,但不太可能被消除。而traits是可以被消除的,例如paper里举的例子,如果order by的字段就是底层存储排序的字段,则order可以被忽略。
Paper没有对parse过程做过多解释,可能也是由于这块是比较标准的实现方式。Optimizer则花了较大篇幅描述,包括3个彼此作用的元件,每个都支持用户扩展:
  • planner rules:优化expression树的规则,会保证语义一致性。看起来Calcite除了会提供通用的优化规则外,也会针对不同的底层计算、存储平台定制规则,例如Cassandra相关的优化规则,一个常用的规则是尽量下推计算逻辑(所谓的谓词下推)、以降低需要读出的数据量
  • metadata providers:SQL解析是否成功依赖元数据,如何优化也需要元数据,metadata providers就承担了给Calcite核心组件提供元数据的功能。常见的优化所需元数据包括一些数据分布的统计信息,例如paper中提到的cardinality, average row size, and selectivity for a give join,这可能帮助Calcite决定是使用broadcast join还是sort join等
  • planner engines:engine将rules和meta结合起来、执行。Calcite提供了2种engines:
    • Cost-Based Planner Engine,尽量找到最低开销的plan,直到达到配置的停止点,例如完成所有的搜索空间,或相邻的两次迭代间cost没有明显降低(即所谓的启发式)
    • Exhaustive Planner,反复遍历所有rules,直到plan稳定不变、而不考虑是否找到最低开销
Paper没有给出何种场景使用哪个engine,用户需要自行尝试。如果两个engines都不合适,用户也可以实现自己的engine。
Paper最后给出了工业界和学术界对Calcite的使用情况:
  • Embedded Calcite,将Calcite作为lib库嵌入在自己的框架里,包括Flink、Drill、Hive等
  • Calcite Adapters,反过来将自己作为一种特定数据源嵌入到Calcite里,例如Cassandra、ES等
  • 此外还有学术界的一些尝新用法
总而言之,Calcite应用较广,值得了解。但就Paper而言,它没有提出理论上的改进,更像着力在工程实现的抽象和优化方面。而如果要达到实际工业级使用中,较好的优化效果,用户还需要在元数据种类下较大的工夫,甚至需要针对自己的计算、存储介质开发合适的插件实现。