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