解读 Implementing data cubes efficiently

概述

论文链接：Implementing data cubes efficiently

预计算基于空间换时间实现查询性能提升，物化视图是数据立方体(data cubes)的一种实现方式。如何有效选择数据立方体进行物化是一个NP难问题，对于n维数据集，有2^n种选择可能。本论文提出基于数据格框架(Lattice Framework)，通过贪心算法高效选择物化视图。

数据格框架

定义

本文创新性提出数据格框架 (Lattice Framework)：一种用于表示和分析多维数据查询依赖关系的数学结构，该框架为工业界物化视图推荐实现提供理论基础，例如，Apache Calcite 物化视图推荐基于Lattice实现。

Lattice定义：一个格 ⟨L,⪯⟩ 由两个部分组成：

• 元素集合 L：代表Lattice中所有元素的集合，是数据立方体中所有可能的查询Q的集合，每个元素可代表一个特定的视图或查询。
• 偏序关系⪯：定义在元素集合 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)

多个维度可以表示为组合偏序关系。(a1, b1) ⪯ (a2, b2) 意味着 a1 ⪯ a2 和 b1 ⪯ b2，表示(a1, b1)的结果可通过(a2, b2) 计算。

示例如下：假设有时间维度和地域维度，每个维度有多个层次结构如下

• 时间维度的层次结构：年（Year）、月（Month）、天（Day）
• 地域维度的层次结构：国家（Country）、城市（City）

组合后的二维层次结构可以表示为：(Year,Country)、(Year,City)、(Month,Country)、(Month,City)、(Day,Country)、(Day,City)，

存在偏序关系：(Year,Country) ⪯ (Month, Country) ⪯ (Month, City)。

贪心算法

执行流程

基于贪心算法在给定限制条件下，选择最优的视图集合进行物化。执行流程主要包括：

1. 初始化：选择顶层视图（即包含所有维度的视图）作为初始物化集合S。
2. 迭代选择：
   1. 对于每个未加入集合的视图 v，计算将其加入集合S后的效益 B(v,S)
   2. 选择效益 B(v,S最大的视图 v 加入集合 S。
3. 终止条件：重复上述迭代选择过程，直到达到预定的视图数量k或没有更多合适的视图可选。

收益公式

收益计算：最小化查询响应时间，即尽可能提升查询效率。

计算视图 v 的查询收益 B(v,S)的步骤如下： 其中v ⪯ u，u是已经选中过的视图

1. 定义子视图的查询成本：
   1. 对于每个视图 w，如果 w⪯v，则 w是 v的子视图。
   2. 设 C(v) 表示视图 v 的查询成本（通常为视图v的行数）
2. 计算成本差异：
   1. 对于每个子视图 w，找到集合S中成本最小的视图v，使得 w⪯v
   2. 如果C(v)<C(u)，则v可以减少 w的查询成本，成本差异为 C(u)−C(v)；否则，成本差异为0
3. 计算总收益：视图 v的总收益 B(v,S) 是所有子视图 w的成本差异之和

成本计算

与维度的数据量级相关，视图成本 C(v)通常表示视图 v的行数，即视图 所包含的数据记录的数量。计算视图成本的具体方法取决于数据的分布和视图的复杂性。

1. 直接计算：如果数据量不大，可以直接计算视图 v的行数。
2. 统计抽样：随机抽样、计算样本视图成本、推算总体视图成本
3. 分析方法：维度量级均匀的话，使用维度组合

各个维度组合的数据量级：groupby 维度，可估算物化视图所需存储空间和计算资源。计算步骤：

• 确定维度层次：确定每个维度的层级结果，如时间维度中，层次可能是天、月、年
• 确定每个层次的基数：即维度的NDV值，如时间维度中月份基数为12
• 计算组合的基数：组合的基数是各个维度基数的乘积，例如，如果零件维度有1000个不同的零件，供应商维度有500个不同的供应商，则组合 (part,supplier)的基数为1000×500=500,000
• 考虑数据的稀疏性：数据立方体通常是稀疏的，即并非所有可能的维度组合都有数据。因此，实际的组合基数通常会小于理论上计算的基数。需要根据实际数据的稀疏性进行调整
• 使用统计方法或采样：如果数据量非常大，无法直接计算所有维度组合的基数，可以使用统计方法或采样技术来估算
• 考虑聚合函数：视图通常会涉及聚合函数，需要考虑聚合后的数据量级，会极大的压缩的数据量级