Calcite Lattice物化视图选择

背景

物化视图(Materialized View，简称MV）：是一种特殊的物理表，本质是预计算。通过多个计算过程之间的联系建立，从数据组织层面优化数据访问效率，把某些长耗时的操作结果(例如JOIN、AGGREGATE) 直接保存到物理存储上，可以像表一样被访问，以便在后续查询时直接复用，最终实现加速查询的目标，即空间换时间。与之相对的，普通视图(View) 仅是对用户查询定义的一种简化，并不存储结果数据，无法加速查询。

为实现物化视图加速，需解决以下三个关键问题[1]：

1. 视图选择：如何设计物化视图，选择哪些表和字段构建物化视图，最大化查询收益。
2. 视图维护：如何最小成本的维护和更新物化视图数据，保证视图表与原始表的计算结果数据一致性。
3. 视图改写：如何自动透明化的实现SQL查询改写，改写为通过物化视图的加速查询。

本文仅针对物化视图选择介绍，主要包括两部分：1. 介绍Lattice物化视图选择框架；2. 概述Calcite物化视图选择的实现原理。

Lattice选择框架

框架组成

数据格框架(Lattice Framework)[2]: 1996年由Harinarayan提出，参考数学概念，Lattice是其非空有限子集都有一个上确界和一个下确界的偏序集合。一个Lattice格 $⟨L,⪯⟩$ 由两个部分组成：

1. 元素集合 $L$ : 代表Lattice中所有元素的集合，是数据立方体中所有可能查询$Q$的集合，每个元素可代表一个特定的视图或查询。

2. 偏序关系⪯: 定义在元素集合$L$ 上的偏序关系，用于表示元素之间的表示关系。如果查询$Q1$ 可通过查询$Q2$ 的改写表示，则 $Q1⪯Q2$ ，即$Q1$偏序于$Q2$。例如多维查询中，$(part)$ 可通过查询 $(part, customer)$ 表示，则$(part)$ 偏序于$(part, customer)$ ，表示为 $(part) ⪯ (part, customer)$ 。

在Lattice中，任意两个元素 $a$ 和 $b$ 都有一个最小上界(上确界),记作 $sup(a,b)$ ; 和一个最大下界(下确界)，记作 $inf(a,b)$ 。这意味着对于任意 $a,b∈L$ ，都存在 $u∈L$ 使得 $a⪯u$ 且 $b⪯u$ （即存在 $u$ 是$a$ 和 $b$ 的上确界），并且存在 $l∈L$ 使得 $l⪯a$ 且 $l⪯b$ （即存在 $l$ 是 $a$ 和 $b$ 的下确界）。

偏序关系存在以下特性：

※反对称性：对于任意元素 $a$ 和 $b$ ，如果 $a⪯b$ 且 $b⪯a$ 则 $a=b$

※可传递性：对于任意元素 $a$ , $b$ 和 $c$ ，如果 $a⪯b$ 且 $b⪯c$ ，则 $a⪯c$

以单个时间维度的不同层级为例，有维度层级：Day(天)、Week(周)、Month(月)、Year(年)，可得到如下偏序关系: $(Year) ⪯ (Month) ⪯ (Day)$ 和 $(Week) ⪯ (Day)$ 。

多个维度可表示为组合偏序关系。$(a_1, b_1) ⪯ (a_2, b_2)$ 意味着 $a_1 ⪯ a_2$ 和 $b_1 ⪯ b_2$ ，表示$(a_1, b_1)$ 的结果可通过$(a_2, b_2)$ 计算。例如时间和地域的组合维度存在偏序关系：$(Year, Country) ⪯ (Month, Country) ⪯ (Month, City)$ 。

代价&收益模型

代价模型：为合理评估视图选择的有效性，定义成本代价模型，其中 $C(v)$ 是视图$v$ 预估查询耗时，$N_v$ 是查询扫描数量大小，$c$ 是一个固定代价。

收益模型: 最小化成本代价，尽可能提升查询效率。定义视图$v$ 的代价为$C(v)$ ，选择$k$ 个有效视图，其中集合$S$是当前已被选中的视图集合，则当前$v$的收益定义为$B(v,S)$ ，定义如下:

其中$B_w$ 是$w ⪯ v$ 的收益，计算公式如下，$u$ 是$w$ 在已选择视图集$S$ 中的偏序上确界，即 $u∈S, w ⪯ u$ :

基于贪心算法选择$k$ 个视图，时间复杂度为$O(k\times m^{2})$ ，其中$m$ 为所有候选视图的数量，整体执行过程如下:

视图选择示例：定义Lattice的偏序关系和查询代价，展示$B(f, S(a,b))$ ，选择视图元素$a$ , $b$ 后，元素$f$ 的选择收益。

其中视图$a$ 是顶层视图，默认初始化在选择集合$S$ 中，基于贪心算法选择3个视图执行过程如下: $w ⪯ b$ ，其中偏序集$w$ 共5个，分别为$b, d, e, g, h$ 。第一次选择收益最大的视图$b$ ，第二次选择收益最大的视图$f$ ，第三次选择收益最大的视图$d$ 。

Calcite视图选择

实现说明

基于Calcite Lattice框架实现视图选择的核心流程如下，主要包括两部分：

1. 视图构建：基于LatticeSuggester 将RelNode构建为Lattice对象；
2. 视图选择：基于TileSuggester将构建好的Lattice对象转为算法所需的Schema对象，基于Pentaho 聚合选择算法 计算并选择出合适的视图。
   

LatticeSuggester

基于LatticeSuggester#addQuery 方法实现Lattice构建，自底向上构建Frame对象，遍历关键算子类型(如 TableScan、Filter等)获取计划树的聚合信息并维护在Frame中。基于LatticeSuggester#addFrame方法，将Frame对象转为Lattice对象，填充对应的Aggregate聚合字段和Columns表字段列表。最后，针对相同标识(基表)的Lattice对象支持合并处理，因此多个查询可合并为一个Lattice对象。

TileSuggester

将所有RelNode构建完Lattice对象后，基于TileSuggester#tiles对每个Lattice对象进行视图选择推荐。Calcite利用Pentaho 开源的MonteCarloAlgorithm 蒙特卡洛算法实现视图选择，将Lattice对象转为扩展Pentaho Schema的对象，基于StatisticsProvider 提供收益代价选择所需的基数估计，最后将推荐的聚合字段封装为Tile对象，Tile聚合信息可通过Lattice#sql生成视图SQL。

存在问题

社区Calcite基于Lattice框架和Monte Carlo随机采样算法实现基本的视图选择功能，详情可参考官方文档Lattices。该实现存在以下问题:

1. 搜索空间庞大: 虽然引入Monte Carlo随机采样和超时机制优化，但大宽表的视图选择依然会频繁触发系统OOM异常退出。

2. 未考虑查询行为: 该选择框架仅考虑表结构信息，会对所有表字段进行聚合尝试以寻找理论最优视图选择，但该选择与用户的查询行为没有关联性，在实际查询中，推荐的视图命中率远低于预期值。

3. 代价估计不准确: Lattice是基于COST代价的视图选择框架，COST代价的准确性显著影响选择效果，原生Lattice统计信息缺失和不准确导致选择偏差较大。

附录

1. Optimizing Queries Using Materialized Views: A Practical, Scalable Solution
2. Implementing Data Cubes Efficiently
3. Data profiling with Apache Calcite