菜菜的秘密花园Instance-Optimized Data Layouts for Cloud Analytics Workloads
本文为论文 Instance-Optimized Data Layouts for Cloud Analytics Workloads 的阅读笔记。
ABSTRACT
逐块区域映射是一种常用的通过跳过块来减少I/O的技术，但其有效性取决于如何将记录分配给块，即数据布局。
现有的优化数据布局的方法只针对单个表，在存在基于连接的查询时，它们的性能会受到影响。在本文中，我们提出了MTO(多表优化器)，目标是学习一种实例优化的布局，该布局可以最大化特定数据集和工作负载的块跳转。MTO利用连接传递的横向信息来优化所有表的布局，在基于云的商业数据分析服务上实现了高达93%的块访问减少和75%的端到端查询时间减少。
1 INTRODUCTION
区域映射对于在查询执行期间跳过不相关的块很有用，但是它们的有效性取决于块之间数据的物理布局，即排序顺序。
文章主要贡献：
(1) MTO 是第一个用于优化整个数据集的实例-优化数据布局框架。（常用的优化多表数据集布局的方法是独立的优化每个表的布局，其性能并不高。）
(2) 引入连接诱导谓词，在MTO中用于通过连接传递信息，更好的学习数据布局。
(3) MTO 可以扩展到更大的数据集和工作负载，并适应工作负载转移和数据变化。
2 CURRENT BLOCKING APPROACHES
【Sort Key】
按特定列对每个表的数据进行排序，但只有过滤排序键列的查询才能从块跳过中受益。
【Z-ordering】
同时对多个列上的数据进行排序，但必须仔细调整才能实现高性能。即使经过适当调整，性能也不如 instance-optimized 方法。
【Instance-optimized Layouts】
在特定数据集和工作负载上表现良好，通过有目的地过拟合特定数据集和工作负载的布局，能够在该特定实例上优于现有方法。
【Drawback of Current Approaches】
独立地优化单个表的布局，而不是联合考虑所有表的布局，不能最大限度地提高块跳转性能。
【Qd-tree】
Qd-tree结构。 qd-tree是一棵二叉决策树。每个内部节点包含一个过滤器谓词，即cut，用于将记录子集划分为两个较小的子集，一个满足cut，另一个不满足。qd-tree的叶节点对应数据块。
Qd-tree用法。 我们可以使用qd-tree进行离线块分配和在线查询处理。① 给定一个qd-tree和一个表，通过qd-tree路由表中的每条记录，将其分配到将存储在其中的数据块。② 在查询执行时，使用qd-tree来确定需要访问哪些块。
Qd-tree构造算法。 我们采用贪心方法来构建。在每次迭代中，通过cut将叶节点拆分为两个子节点。从候选cut集合中选择cut中的一个，使结果qd-tree在给定工作负载上跳过的记录数量最大。迭代直至所有叶节点都达到所需的大小。
3 MTO OVERVIEW
MTO由两部分组成：① 记录到块的映射，其中每个块具有大致相同数量的记录，块只能包含来自单个表的记录。② 一个方法来确定哪些块可以被跳过。
3.1 Sideways Information Passing
现有的单表布局方法在多表情况下不是最优的，因为它们没有利用表之间的横向信息传递。
以图3为例。设块大小为1M条记录，表A有1M条记录，表B有8M条记录。表A的所有记录将落在同一个块中，因此表A的排序顺序不会影响块跳转。考虑如下工作负载：
|
|
通过2个过滤器谓词，表A能够跳过基于谓词A.X < 100的块，表B能够跳过B.Y > 200的块。但根据与A的联接是否会产生相关记录，将B的记录分组在一起，可以进一步增加跳块。即B的分块是基于 B.Y > 200 和一个新的连接-诱导谓词 B.KEY IN (SELECT A.KEY FROM A WHERE A.X < 100) 。
3.2 MTO Workflow
离线优化。 MTO优化算法将一个多表数据集和一个查询工作负载作为输入，并为每个表创建一个qd树，它将确定该表记录的数据布局。
1a： 从查询中提取所有简单谓词，并根据它们过滤的表对其进行分组。
1b： 通过提取的简单谓词，创建连接-诱导谓词。一个简单的谓词可以通过多个连接传递到另一个表上。
1c： 对于每个连接引起的谓词，求值所有子查询以获得字面cut。在本例中，运行子查询(SELECT B.key FROM B WHERE B.y > 200)返回集合(1,4,9)，因此表A上的连接诱导切割的字面形式是A.Key In(1,4,9)。
2： 将所有表和总体查询工作负载提供给qd-tree构建算法。在步骤1中提取的表上的谓词（简单谓词和连接-诱导谓词）成为qd树的候选cut。构造的qd树确定表的数据布局。
在线查询执行。 在查询执行时，MTO对每个表使用qd-tree来确定需要访问哪些块。图6显示了可能通过MTO优化算法为表B构建的qd树。
1： 从该表上的查询中识别所有谓词（简单谓词和连接-诱导谓词）
2： 使用谓词路由表构建qd-tree，以确定哪些块需要被访问。
4 MTO ALGORITHMS
4.1 Join-induced Predicates
考虑下面的查询，我们可以从A归纳到B，产生连接诱导谓词 B. key IN (SELECT A. key from A WHERE A.X < 100) ，但不能从B归纳到a。因此我们制定了一组规则，用于确定何时可以在保持语义等效查询的同时归纳谓词。
|
|
4.2 Scalability through Sampling
为了减少在扩展到更大的数据集时优化布局所需的时间，MTO在数据集的统一样本上运行其优化算法，而不是在整个数据集上运行。给定采样率，MTO通过均匀随机地从数据集中的每个表中选择部分记录来创建一个样本。
5 WORKLOAD SHIFT AND DATA CHANGES
5.1 Dynamic Workloads
工作负载特征经常随着时间的推移而变化，完全重组大型数据集可能需要大量的时间和计算资源，而MTO具有部分重组其布局的能力。MTO只重新组织qd-tree子树，从而获得最大的总体性能增益。例如，如果只有Europe的工作负载发生了变化，并且qd-tree根节点具有cut REGION = ' Europe ‘，则MTO只会重新组织左子树。
接下来，我们描述了一个用于确定重组qd-tree子树的价值(即收益减去成本)的奖励函数，然后我们描述了MTO如何使用该奖励函数来确定最佳重组策略。
最小化重组的影响。 MTO启动了一个单独的进程，该进程使用数据的副本执行部分重组。在重组期间，查询仍然在现有数据布局上执行，查询服务不受影响。重组完成后，新的数据布局与现有布局交换，对工作负载的影响最小。
奖励函数。 子树T重组为T’的回报为： $R(T,Q) = (q/w)·B(T,Q)-C(T)$
$B(T,Q)$ 是完全重组 T 后，查询Q可以减少块访问的平均数量；$C(T)$ 是T中块的总数，代表完全重组T’的成本；$w$ 是重组的相对开销（重新压缩写入vs读取的速度比）。 计算奖励并不需要我们实际执行任何物理重组。
寻找最优重组策略。
寻找最优重组策略，即找到具有最大组合奖励的非重叠子树的集合。我们通过动态规划找到qd-tree的最优集：从叶子节点开始，向根节点工作。如果 $R(L,Q)$ > 0，叶子 $L$ 的最优集为 ${L}$ ，否则为空。非叶节点 $T$ 的最优集要么是 ${T}$ ，要么是它的两个子节点的最优集的并集。图8显示了一个qd树，其中最优集有两个子树。
对于大型qd树来说，计算每个子树的奖励是非常昂贵的。主要的瓶颈是将 T 优化为 T’ 来计算 $B(T,Q)$ 。文章使用 【剪枝】 算法，提出了一些帮助MTO淘汰不属于最优集合节点的规则，避免在该节点的子树上计算 B。
5.2 Dynamic Data
6 EVALUATION
6.2 Overall Results
图10a和10b显示，在模拟或实际的 cloud DW场景上，与最佳替代方法相比，MTO的块访问都可以最多减少90%左右。
图10c显示，与最佳替代方法相比，MTO实现了端到端查询运行时间减少20%-75%。
此外，MTO的内存开销（来自每个表的qd树）最多只有几个GB，与数据的大小（约100GB）相比很小。
6.3 Performance Breakdown by Query
为了更好地理解MTO比STO和Baseline提供性能优势的条件，我们从TPC-H工作负载中选择了五个具有不同过滤器/连接特征的查询模板：Q1没有连接；Q14过滤器了列 L_SHIPDATE 但没有在连接表上过滤；Q6在非排序列上过滤但没有连接；Q4在连接表上和排序列相关的列上过滤；Q4在连接表上和排序列不相关的列上过滤。
在连接表（Q4，Q5）上使用选择性过滤器进行查询时，MTO的性能大大优于所有替代方法。
6.5 Dynamic Workloads and Data
在工作负载转换后，MTO 的初期表现较基线差，但在部分重组后的长期表现较佳。
数据插入后，MTO仍保持其优于基线的优势。
尽管在工作负载转移之后，MTO最初执行的查询比Baseline要少，但它能够在重组后迅速弥补损失的时间。
