Slalom Coasting Through Raw Data via Adaptive Partitioning and Indexing

本文为论文 Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing 的阅读笔记。

🟠 Slalom

• 一个通过监视用户访问模式来适应工作负载变化的原位查询引擎。

🟡 关键组件

• 在线分区和索引方案
• 为原位查询引擎量身定制的分区和索引调优器。

🟢 性能优势

• 对原始数据文件进行逻辑分区；为每个分区构建轻量级分区特定的索引

1 简介

🟠 加载、索引和调优的成本

考虑到所涉及的数据大小，对数据的任何转换、复制和准备步骤都会在查询数据前引入大量延迟。缺乏对工作负载的先验知识使得物理设计决策几乎不可能。

🟡 自适应分区和细粒度索引

• 使用第一次表扫描来生成分区和轻量级索引提示
• 数据集以动态方式部分索引，以适应三个关键工作负载特征：数据分布；查询类型；投影属性。
• 调优器通过以下方式降低数据访问成本:
  • 对原始数据集进行逻辑分区，在不进行物理重构的情况下将其虚拟地分解为更易于管理的块
  • 在每个逻辑分区上选择适当的索引策略，以提供有效的数据访问。（细粒度的索引决策）

🟢 基于Slalom的高效 In-Situ Query

• 将在线分区和索引调谐器集成到原位查询处理原型系统Slalom中
• Slalom在逻辑上将原始数据划分为分区，并根据每个分区的“热度”(访问频率)、针对每个分区的查询类型来选择构建哪个细粒度的分区索引。
• Slalom填充二进制缓存(从原始数据转换为二进制数据的缓存)以进一步提高性能
• Slalom使用基于随机成本的决策算法调整当前分区和索引方案来适应工作负载的变化

🔵 贡献

• 我们提出了原始数据文件的逻辑分区方案，该方案支持在每个分区级别上进行细粒度的索引决策。
• 好处：带来了原位查询处理索引的好处；索引构建成本低；内存占用小。
• 我们将分区和索引调谐器集成到我们最先进的原型原位查询引擎Slalom中。

2 相关工作

🟣 对原始数据的查询

• Slalom使用的技术可以通过减少索引的大小、为每个文件分区构建内存效率高的索引来提高系统的可伸缩性。
• Slalom不加载所有数据，而是利用工作负载局域性自适应地为原始数据创建细粒度索引方案，并逐渐减少I/O和访问成本，同时在适度的内存预算下运行。

🔵 数据库分区

• Slalom提供了一种非侵入式的灵活分区方案，通过利用数据倾斜创建逻辑水平分区。
• Slalom在查询处理期间不断地改进其分区，而不需要先验的工作负载知识。

🟠 数据库索引

• 本文采用了value-position索引和value-existence索引两类具有代表性的索引结构。
• Slalom构建主存辅助结构时 速度快、占用空间小、不需要先验的工作负载知识。可以实现较低的从数据到洞察的延迟，并且不会影响长时间运行的工作负载。

🟡 在线索引

• Slalom根据分区粒度构建索引。
• Slalom在查询执行期间以流水线方式填充索引，而不是触发独立的索引构建阶段。
• Slalom的目标是最小化索引构建决策的成本和成本计算算法的复杂性。

🟢 自适应索引

• 不预先为数据建立索引，而是在查询处理期间逐步改进索引。

3 Slalom系统

3.1 架构

• Partition Manager：负责在数据文件上创建逻辑分区
• Index Manager：负责在分区上创建和维护索引
  • 每个索引对应一个数据分区，每个分区可能有多个索引
  • 从两类索引中选择：value-existence(返回数据集中是否存在一个值)；value-position(返回值在文件中的位置)
  • 使用在线随机算法决定构建哪些索引 & 何时构建，考虑：全扫描的成本；构建索引的成本；分区访问频率
• Online Tuner：收集有关数据和查询访问模式的统计信息，并将其存储在Statistics Store中
• Structure Refiner：根据统计信息评估分区和索引的备选配置
• Positional Maps & Caches：用来最小化原始数据访问成本
• Query Executor：利用可用的数据访问路径并编排其他组件的执行
• Update Monitor：检查数据文件是否被修改（更新的分区和位置映射），并相应地调整Slalom的数据结构

3.2 实现

• Slalom通过使用向量化解析器、二进制缓存和位置映射，降低原始数据访问成本。
• Slalom为访问的每个CSV文件填充一个PM。为了减少内存占用，PM只存储每个元组和字段的增量距离。

3.3 查询执行

🟠 状态(a)

Slalom没有数据或查询工作负载信息。Slalom构建一个PM，随后的每次查询中，收集有关访问属性的数据分布和平均查询选择性的统计信息，以确定逻辑分区是否会提高性能。

🟡 状态(b)

Slalom已经执行了一些查询，并在访问的属性上建立了二进制缓存和PM。在逻辑上将文件划分为两个分区，其中分区1处于稳定状态。检查稳定分区是否存在索引；若不存在索引，则使用随机化算法决定是否建立。

🔵 状态(c)

Slalom执行了更多查询，并且根据查询访问模式确定了分区1。分区2被进一步分割成多个分区。

4 连续分区和索引调优

4.1 原始数据分区

• Slalom使用逻辑分区将文件虚拟地分解为更易于管理的块，而无需进行物理重构。目标：

  • 启用分区过滤，即尝试将相关数据值分组在一起，以便在某些查询中可以跳过它们
  • 允许更细粒度的索引调优。

• 分区策略

  • 基于查询的分区：对于候选键属性(所有元组都有不同的值)
  • 同构分区：对于其他值分布
    • 计算连续均匀分布分区的最优集合具有指数级的复杂性，因此不适合在线执行。

• 理想分区：每个分区包含均匀分布的值；分区是成对不相交的

• 分区管理器逐步拆分分区，直到达到稳定状态(调优器估计进一步拆分无法获得更多收益的状态)。判断条件：

  • 新分区中，值的方差和值分布的超额峰度是否小于父分区中的方差和峰度
  • 不同值的数量是否减少（分区的数据分布更加均匀，不相交的概率增加）

• 调谐器的目标是在每个新分区中最大化选择性。我们将分区问题建模为从分区中随机选择元组，目标是至少有50%的新分区比原始分区具有更高的选择性。

4.2 Slalom中的自适应索引

🟠 Value-Existence 索引

• Value-Existence 索引是 Slalom 分区的基础。一旦将分区设置为稳定，索引管理器就会在其上构建一个 Value-Existence 索引。
• 索引管理器仅在索引布尔属性时使用 位图 ，因为它们比其他数据类型的Bloom 过滤器需要更大的内存预算。
• 索引管理器还在所有分区上使用 区域映射 ，因为它们具有较小的内存开销。
• 对于所有其他数据类型，索引管理器倾向于 Bloom过滤器 ，因为它们具有高性能和较小的内存占用。（布隆过滤器的内存占用有一个常数因子）

🔵 Value-Position 索引

• 与 Value-Existence 索引相比，该索引的构建成本更高。
• 索引的性能很大程度上取决于查询的类型、数据集中值的分布。

🟡 何时建立 Value-Position 索引

• 如果索引管理器估计后续将有足够多的查询访问该分区，以偿还建立成本，则它会在该分区上构建一个 Value-Position 索引。

5 实验评估

5.1 适应工作负载变化

🟣 Slalom 收敛

• Slalom第一次查询的运行时间比它的平均查询时间慢20倍，因为在查询期间它建立了一个位置映射和一个二进制缓存。
• 在初始查询集(查询1-6)之后，处理完全索引的数据时，Slalom的性能与PostgreSQL相当。
• 当Slalom收敛到最终状态时，其性能可与索引DBMS-X相媲美。
• DBMS-X将所有数据保存在内存中，并使用内存友好型数据结构，因此它的性能平均比PostgreSQL好3倍以上。

🟤 执行分解

• 图5显示了与前面相同实验的查询执行的细分。为了清晰起见，只显示查询Q1-15和Q31-45，因为Q16-30与Q11-15模式相同。
• 在Q1期间，Slalom扫描原始文件并创建缓存。
• 在Q2-Q3期间，Slalom会主动对文件进行分区，并收集每个分区的统计数据。Slalom基于这些统计信息进行进一步的分区和索引决策，构建Bloom过滤器和Btree。
• Q3是使用完整分区扫描执行的最后一个查询，由于它还会产生索引构建成本，因此在执行时间上存在一个局部峰值。
• 在Q4-Q8期间，Slalom通过构建新的索引不断提高性能。
• 在Q31之后，查询使用谓词中关系的第二个属性，因此Slalom重复了分区和索引构建的过程。

🟠 执行时间&内存消耗

• 图6 显示了1000个查询的完整工作负载，纵轴为总的执行时间，包括PostgreSQL和DBMS-X的加载和索引成本。
• PostgresRaw、Slalom和crack不会产生加载和索引成本，并且在其他DBMS加载数据和索引方法完成索引构建之前就开始查询。
• 图7 绘制了三种方法的内存消耗。
• 访问一个新属性时，crack会立即构建它的cracker列，因此内存占用很大。
• Slalom在查询性能和内存利用率之间取得了平衡。

🟡 最小化数据访问

• 随着Slalom的分区和索引方案收敛，访问的多余元组数量减少。
• Slalom将所有索引存储在内存中，因此通过跳过一个分区，Slalom避免了对分区的完全访问。

5.2 在内存限制下工作

图10显示了给定三种不同内存预算的工作负载的查询执行时间。对于10GB和12GB内存预算，没有足够的空间来构建所有必要的索引，因此这些配置会出现性能下降。

图11显示了当给Slalom提供12GB内存预算时，相同查询序列的内存分配。我们考虑存储缓存、B+树和Bloom过滤器所需的空间。

在查询Q3、Q4和Q5时，Slalom开始构建Btree，并在查询Q7时收敛到稳定状态。

实验表明，Slalom可以在有限的内存预算下优雅地管理可用资源，以提高查询执行性能。

6 总结

🟠 Slalom考虑用户查询模式，通过逻辑地对原始数据文件进行分区，并在需要时为每个分区构建轻量级分区特定索引，从而减少对原始数据的查询时间。

🔵 调优器进一步动态调整其决策，以跟踪任何工作负载变化，并在潜在的性能增益、构建索引所需的工作量和构建索引的总体内存消耗之间保持平衡。