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

文章副标题是 A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources 为各种异构数据源做实现一套查询优化框架。

问题的背景是下面这样的:查询语言多种多样并不受限于SQL,还可能是LINQ或者是其他DSL甚至是表达式;而数据源可以是ES, Spark, Druid等等

As organizations have invested in data processing systems tai- lored towards their specific needs, two overarching problems have arisen:


  1. 多种数据模型,主要还是支持时序
  2. 灵活的查询优化器,扩展优化策略和算法
  3. 各种异构数据源,允许在上面做查询优化
  4. 支持SQL以及其他查询语言扩展,最重要的是一套公共接口

不太明白这两种算法之间的差别,从后面的内容看上去,multi-stage optimization是第一种的扩展来减少探索量,将优化分为多个阶段,每个阶段只使用部分规则进行探索。

> In the current version of Calcite, the query optimizer architecture uses dynamic programming-based planning based on Volcano [20] with exten- sions for multi-stage optimizations as in Orca [45].




逻辑计划和物理计划并没有显著的差别,如果不做任何优化,拿到一个逻辑计划基本上也可以去执行。他们之间的差别可能在于,物理计划上存在某些traits(特征), 这些特征是和数据源系统,数据分析以及某些假设相关的(比如CPU, network costs)等等。一个逻辑计划上也可以增加上不同的traits, 最终得到多个物理计划。一个重要的traits是calling convention, 这个词最开始函数调用之间的约定,我觉得放在这里也听恰当的:表明在访问某个数据源的时候可以什么假设和约定。为了对接 不同的数据源,用户需要定义不同的Adapters,并且上面实现各种calling conventions.

Calcite includes common traits that describe the physical proper- ties of the data produced by a relational expression, such as ordering, grouping, and partitioning. Similar to the SCOPE optimizer [57], the Calcite optimizer can reason about these properties and exploit them to find plans that avoid unnecessary operations. For exam- ple, if the input to the sort operator is already correctly ordered— possibly because this is the same order used for rows in the backend system—then the sort operation can be removed.

In addition to these properties, one of the main features of Calcite is the calling convention trait. Essentially, the trait represents the data processing system where the expression will be executed. Including the calling convention as a trait allows Calcite to meet its goal of optimizing transparently queries whose execution might span over different engines i.e., the convention will be treated as any other physical property.

This table scan operator contains the necessary information the adapter requires to issue the scan to the adapter’s backend database. To extend the functionality provided by adapters, Calcite defines an enumerable calling convention. Relational operators with the enumerable calling convention simply operate over tuples via an iterator interface. This calling convention allows Calcite to im- plement operators which may not be available in each adapter’s backend. For example, the EnumerableJoin operator implements joins by collecting rows from its child nodes and joining on the desired attributes.

Query Processing and Optimization里面中几个部分:

  1. Planner Rules 规则重写,除了通常的逻辑规则重写之外,还需要考虑与数据源结合的规则重写
  2. Metadata Providers 没有太明白为什么需要使用Janino这样的编译器,metadata result是需要缓存的因为可能会被多次访问
  3. Planner engines. 其中使用DP和multi-stage optimization算法都是CBO的,而穷举算法(exhaustive planner)则是不断地使用规则是RBO的
  4. Materialized virews 不太明白里面的具体细节,提到两种方式 view substitution 和 lattices, 但是第二种方式有许多限制。

Extending Calcite:

  1. Semi-structured Data 比如要查询MongoDB的话,可以使用map+隐式cast变为schema模型
  2. Streaming 支持流式数据查询,需要在SQL里面有first-citizen support.
  3. Geospatial Queries 支持地理空间查询
  4. Language-Integrated Query for Java. LINQ/LINQ4J 是不是这类查询语言对于在内存数据结构上做复杂查询很有效果?