References

[文献阅读] The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds

原文地址： http://learned.di.unipi.it/publication/pgm-index-fully-dynamic-compressed-learned-index/pgm-index-fully-dynamic-compressed-learned-index.pdf 本文提出了一种新型的学习型索引，其支持前任查询…

https://zhuanlan.zhihu.com/p/537075200

经典 Learned Index 结构设计及应用

引言学习索引是一种新型的索引结构，可以帮助数据库更快地查找数据。学习索引的诞生可以追溯到 2017 年，由 Google Brain 团队的 Kraska 等人在论文[1]中首次提出,探讨了使用神经网络替代传统数据结构（如 B-Tree…

https://zhuanlan.zhihu.com/p/625142215

Abstract

• 索引结构是 DBA 用来提高分析和事务性工作负载性能的最重要的工具之一。然而，在大型数据集上构建多个索引通常会令人望而却步，并且会消耗宝贵的系统资源。事实上，最近的一项研究表明，作为 TPC-C 基准测试的一部分创建的索引可以占现代 DBMS 中可用总内存的 55%。这种开销消耗了宝贵且昂贵的内存，并限制了存储新数据或处理现有数据的可用空间量。

• 在本文中，我们提出了一种新的数据感知索引结构，称为拟合树 FITing-Tree，它使用分段线性函数逼近索引，在构造时指定有界误差。这个错误旋涡 error knob 提供了一个可调参数，通过平衡查找性能和空间消耗，DBA 可以将索引适合于数据集和工作负载。为了进行这种权衡，我们提供了一个成本模型，在给定 (1) 查找延迟需求(例如，500ns)或 (2) 存储预算(例如，100MB)的情况下，帮助确定适当的错误参数。通过使用各种真实数据集，我们证明了我们的索引能够提供与完整索引结构相当的性能，同时将存储占用减少了几个数量级。

Introduction

• 事实上，最近的一项研究[47]表明，在最先进的内存 DBMS 中，为典型OLTP工作负载创建的索引最多可以消耗总可用内存的55%。这种开销不仅限制了用于存储新数据的可用空间，而且还减少了用于处理现有数据的中间数据的空间。

• 为了减少 B+ 树的存储开销，已经开发了各种压缩 Compression 方案[7,9,23,48]。这些技术背后的主要思想是消除存在于键之间的冗余和/或减少索引节点内每个键的大小。例如，前缀和后缀截断可以用于每个索引节点只存储一次键的公共部分，从而减小树的总大小。此外，可以在每个节点中应用更昂贵的压缩技术，如 Huffmann 编码，但运行时成本更高，因为必须对页面进行解压缩才能搜索项。
• VLDB’14 BF-tree: Approximate Tree Indexing
• 1977 Prefix B-trees
• ICDE’01 B-Tree Indexes and CPU Caches.
• ICDE’06 Super-Scalar RAM-CPU Cache Compression

• 尽管前面提到的每种压缩方案都减少了索引节点的大小，但这些索引的内存占用仍然随着要索引的不同键的数量线性增长，从而导致索引可能消耗大量内存。对于在各种应用(如自动驾驶汽车、物联网设备)中生成的时间戳或传感器读数等数据，这一观察结果尤其适用。更糟糕的是，为此类数据类型建立索引的惟一键的数量通常会随着时间的推移而增长，从而导致索引不断增长。因此，除了完全删除索引之外，DBA 没有办法限制内存消耗。

• 为了解决这个问题，我们提出了 FITing-Tree，这是一种新的索引结构，它使用分段线性函数紧凑地捕获数据中的趋势。与典型索引在叶级上使用固定大小的页面来指向数据不同，FITing-Tree 使用分段线性函数来快速近似元素的位置。通过利用数据中的趋势，与传统的 B+ 树相比，FITing-Tree 可以将索引的内存消耗降低几个数量级。索引结构的核心是一个参数，它指定了可接受的误差量 (即，一个常量，它是任何键的预测位置和实际位置之间的最大距离)。与现有的索引结构不同，我们的 error 参数允许 DBA 将索引适合给定的场景，并平衡索引的查找性能和空间消耗。为了进行这种权衡，我们还提供了一个成本模型，该模型可以帮助 DBA 在给定 (1) 查找延迟需求(例如，500ns)或 (2) 存储预算(例如，100MB)的情况下选择适当的错误项。

• 在 FITing-Tree 的基本版本中，我们假设要索引的表数据是按索引键(即聚类索引)排序的，但我们也展示了我们的技术如何扩展到二级(即非聚类)索引。通过使用各种真实世界的数据集，我们展示了我们的索引结构提供了与完整和固定大小的页面索引相当的性能(即使对于最坏的数据集)，同时减少了数量级的存储占用。

• 使用线性函数来近似分布使得 FITing-Tree 成为一种学习索引[30]。然而，与最初提出的技术相比，我们的方法允许我们 (1) 限制最坏情况下的查找性能，(2) 有效地支持插入操作，以及 (3) 启用分页(即，整个数据不必驻留在连续的内存区域中)。此外，尽管使用分段函数近似分布的问题也不是什么新问题[10,12,13,16,18,27,33,40,45]，但这些技术都没有应用于索引，因此没有考虑索引必须支持的操作。

• 另一个有趣的观察是，我们在 FITing-Tree 中的压缩方案与节点级压缩技术(如前面提到的前缀/后缀截断)是正交的。换句话说，由于 FITing-Tree 在内部为内部节点使用树结构，因此我们仍然可以应用这些技术来进一步减小索引的大小。

贡献

• 我们提出了一种新的索引结构——FITing-Tree，它利用底层数据分布的属性来减少索引的大小。

• 我们提出并分析了一种有效的分割算法，该算法包含一个可调的错误参数，允许 DBA 平衡查找性能和索引的空间占用。

• 我们提出了一个成本模型，可以帮助 DBA 在给定延迟或存储需求的情况下确定适当的错误阈值。

• 通过使用几个真实的数据集，我们发现与现有索引结构相比，我们的索引提供了类似(在某些情况下甚至更好)的性能，同时消耗的空间更少

Overview

• 在高层次上，索引(特别是排序属性上的 B+ 树)可以用一个函数来表示，该函数将键 (例如，时间戳) 映射到存储位置。使用这种表示，FITing-Tree 将键空间划分为一系列不相交的线性段，这些线性段近似于真实函数，因为(通常)不可能对底层数据分布进行完全建模。这个过程的核心是一个可调的误差阈值，它表示段内任何键的预测位置与其实际位置的最大距离。FITing-Tree 不是将所有值存储在键空间中，而是仅存储 (1) 每个线性段的起始键和 (2) 线性函数的斜率，以便使用线性插值计算键的近似位置

• 下面，我们首先讨论如何使用函数将键值映射到存储位置。然后，我们讨论如何利用这个函数表示法在 B+ 树之上高效地实现索引结构，用于聚集索引。最后，我们将展示如何将我们的想法也应用于压缩二级索引。

函数表示

• 我们的方法的一个关键见解是，我们可以抽象地将索引建模为一个单调递增的函数，该函数将键(即索引属性的值)映射到存储位置(即其页和该页中的偏移量)。为了解释这种直觉，假设所有要索引的键都存储在一个已排序的数组中，允许我们使用元素在数组中的位置作为其存储位置。

• 例如，考虑物联网数据集[1]，其中包含来自整个大学建筑中安装的各种设备(例如，门传感器，运动传感器，电源监视器)的事件。在这个数据集中，数据按事件的时间戳排序，允许我们构造一个函数，将每个时间戳(即键)映射到它在数据集中的位置(即在排序数组中的位置)，如图 1 所示。不出所料，由于安装的物联网设备监控人类活动，记录的操作的时间戳遵循一个模式(例如，周末和晚上几乎没有活动)。

• 由于表示索引的函数可以是任意复杂且依赖于数据的，因此将键映射到位置的精确函数可能无法学习，并且构建和更新的成本很高。因此，我们的目标是近似表示键到位置映射的函数。

• 为了紧凑地捕获数据中存在的趋势，同时能够有效地构建新索引并处理更新，我们使用一系列分段线性函数来近似任意函数。例如，如图 1 所示，我们的分割算法(在第3节中进一步描述)将时间戳值划分为几个线性段，这些线性段能够准确地反映数据中存在的各种趋势(例如，周末期间的活动较少)。由于近似值捕获数据中的趋势，因此它与键密度无关(可以捕获具有稀疏键的趋势以及具有密集键的趋势)。

• 虽然更复杂的函数(例如，高阶多项式)可以用来近似真实的函数，但分段线性近似的计算成本要低得多。这极大地降低了(1) 初始索引构建成本，(2) 改善了新条目的插入延迟(参见第5节)。

• 然而，得到的分段线性近似并不精确 (例如，键的预测位置不一定是它的真实位置)。因此，我们将与近似相关的误差定义为任意键的实际位置和预测位置之间的最大距离，如下所示，其中pred_pos(k) 和 true_pos(k) 分别返回元素 k 的预测位置和实际位置。

• 这个公式允许我们定义 FITing-Tree 的核心构建块，一个分段。段是排序数组的连续区域，其中任何键与插入位置的距离不超过指定的错误阈值。根据数据分布和错误阈值，分割过程将产生不同数量的近似底层数据的段。因此，重要的是，错误阈值使我们能够平衡内存消耗和性能。在分割过程之后，FITing-Tree 将每个段的边界和斜率(而不是每个单独的键) 存储在B+树中，从而减少了索引的总体内存占用。

Design

• 在 FITing-Tree 的基本版本中，我们假设要索引的表数据是按索引键排序的(即聚类索引)，但我们也展示了我们的技术如何扩展到二级(即非聚类)索引。通过使用各种真实世界的数据集，我们展示了我们的索引结构提供了与完整和固定页面索引相当的性能(即使对于最坏的数据集)，同时减少了数量级的存储占用。如前所述，我们的分割过程将属性的键空间划分为不相交的线性段，使得任何键在段内的预测位置与键的真实位置之间的距离不超过有界距离。FITing-Tree 将这些段组织在树中，以有效地支持插入和查找操作。

Clustered Indexes

• 在传统的集群 B+ 树中，表数据存储在固定大小的页中，索引的叶级仅包含每个表页的第一个键。与聚类 B+ 树不同，在 FITing-Tree 中，表数据被划分为满足给定错误阈值的可变大小的段(页)。每个段本质上是一个固定大小的数组，但是连续的段可以独立分配(即，非连续的)。

• 图 2 显示了聚类的 FITing-Tree 索引的结构。如图所示，底层数据被划分为一系列大小可变的段，这些段近似于要索引的键的分布。根据误差参数和数据分布，可以将几个连续的键汇总到一个段中。将表数据划分为可变大小段的分割算法的细节将在第 3 节中讨论。

• 与传统的 B+ 树不同，FITingTree 中的每个叶节点存储段的斜率、起始键和指向段的指针。这允许我们在每个段中使用插值搜索，因为该段内的数据由斜率给出的线性函数近似

• FITing-Tree 的内部节点与B+树相同(即查找和插入操作与普通B+树相同)。然而，一旦查找或插入到达叶级，FITing-Tree 就需要执行额外的工作。对于查找，我们需要使用斜率和到起始键的距离来计算键的近似位置(在段中的偏移量)。由于结果位置是近似的，因此 FITing-Tree 必须执行局部搜索(例如，二分搜索，线性搜索)来查找项目，这将在第 4 节中进一步讨论。

• 插入操作在到达叶级页面时还需要额外的工作，因为我们必须确保始终满足错误阈值。因此，我们提出了两种不同的插入策略(在第 5 节中详细描述)。第一种策略对段执行就地更新(作为基线)，而第二种策略使用更高级的基于缓冲区的策略来保存插入的数据项。

• 最后，与其在内部使用 B+ 树来定位键所在的段，FITing-Tree 可以使用任何其他索引结构。例如，如果工作负载是只读的，则可以使用其他高性能索引结构(例如 FAST[28])。在 7.4 节中，我们将展示在使用不同的内部数据结构(包括 FAST)时，FITing-Tree 是如何执行的

Non-clustered Indexes

• 二级索引可以显著提高涉及非主键属性选择的查询的性能。如果没有二级索引，这些查询必须检查所有元组，这通常是令人望而却步的。与聚集索引不同，非主键属性没有排序，并且可能包含重复项。

• 聚集的和非聚集的 FITing-Tree 之间的主要区别是，非聚集的 FITing-Tree 需要额外的“间接层”(在图 3 中称为“Key Pages”)。该层本质上是一个指针数组，其大小与数据相同，但按索引的键进行排序。例如，这个间接层中的第一个位置将包含一个指向被索引键的最小值的指针。注意，使用固定大小分页的辅助 B+ 树也需要这个间接层。

• 创建非聚集的 FITing-Tree 的第一步是通过按索引键(例如，温度、年龄)对数据进行排序并按排序顺序实现指向每个数据项的指针数组来构建间接层。接下来，与聚类索引情况类似，分割算法扫描间接层并生成一组有效的段，然后将这些段插入到上层树中。

• 非聚类拟合树上的所有操作内部都是在间接层上操作的。例如，对于查找，数据项的返回位置是它在间接层中的位置。然后，为了访问该值，FITing-Tree 沿着间接层中预测位置的指针进行操作。

• 尽管与聚集的 FITing-Tree 索引相比，非聚集的 FITing-Tree 中键页的排序级别引入了额外的开销，但这种开销在任何非聚集的(二级)索引中都会出现。然而，正如我们在实验中所展示的那样，非聚类的 FITing-Tree 明显小于具有固定大小页面的非聚类 B+树，因为它具有更少的叶子和内部节点。

Segmentation

• 下面，我们将描述 FITing-Tree 如何将属性的键空间划分为满足指定错误的可变大小的段。在此过程之后，将每个段插入到 B+ 树中，以实现高效的插入和查找操作，这将在第4节和第5节中进一步介绍。

Design Choices

• 拟合函数时的一个常见目标是最小化最小二乘误差(最小化第二个误差范数E2)。不幸的是，这样的目标并没有提供最大误差的保证，因此没有提供在插入键位置后必须扫描的位置数量的界限。因此，我们的目标是满足最大误差(E∞)，如图 4 所示

• 虽然存在几种最优的分段线性近似算法，但这些技术都非常昂贵(例如，动态规划算法[31]使用O(n) 内存的运行时间为 O(n^3))。其次，大多数现有的在线分段线性逼近算法 [17,27] 具有较高的存储复杂度和/或不能保证最大误差。最后，即使是线性时间算法也可能不够有效，因为乘法常数有显著的影响

• 因此，为了能够高效地(1)构造索引，(2)支持插入，我们需要一个高效的单遍线性算法。这种对效率的关注使我们选择线性分段函数，因为高阶近似通常会产生额外的成本，如前所述

• 在下文中，我们描述了一种类似于 FSW[33,45] 的分段算法，该算法在运行时是线性的，具有较低的恒定内存占用，并保证每个段的最大错误。然而，重要的是，我们解决了(1) 如何将这些技术扩展到索引，包括查找和插入数据项，(2) 证明，在最坏的情况下，段的大小是有限的，(3) 分析算法并将其与最优算法进行比较。

Segment Definition

• 如前所述，段是键空间的一个区域，可以用线性函数表示，其中所有键都在距离其线性插值位置的有界距离内。更具体地说，段由段中的第一个点(第一个键)和最后一个点(最后一个键)表示。使用此定义，我们可以将线性函数拟合到段中键的位置(使用开始键、结束键和位置数量)。

• 尽管对于给定的最大错误，ShrinkingCone 可能比最优分割更差，但在实践中，它的糟糕程度是有限的，因为我们确实可以保证最大分段至少覆盖错误 +1 个位置。

• Theorem 3.1：最大线性线段所覆盖的最小位置数为 error+1

• 这使我们能够量化“最坏情况”的严重程度。(即，数据集和产生最大段数的错误阈值)。由于最大分段所覆盖的最小位置数受到误差的限制，因此拟合树的总大小也受到限制。因此，在最坏的情况下(每个最大段覆盖 错误+1 个位置)，FITing-Tree 不会大于使用固定大小页面的索引的 size error (例如，B树)。

Segmentation Algorithm

• 正如前面提到的，我们需要一个快速有效的算法，而不是一个最优的算法。因此，我们选择使用贪婪流算法 ShrinkingCone (算法1)，给定一个段的起始点(键)，在满足给定错误阈值的情况下，尝试最大化段的长度。ShrinkingCone 类似于 FSW[33]，但只考虑单调递增的函数，并且可以产生不相交的线段。ShrinkingCone 背后的主要思想是，当且仅当新键不违反段中任何先前键的错误约束时，可以将其添加到段中。

• 更具体地说，我们通过三个指标定义 cone：原点(键及其位置)、高斜率(sl_high) 和低斜率(sl_low)。起始点和低斜率的组合给出了 cone 的下界，起始点和高斜率的组合给出了 cone 的上界。直观地说，cone 表示从 cone 原点开始的段的可行线性函数族(高低斜率表示有效斜率的范围)。当一个新的键被添加到一个片段时，高低斜率分别使用键和键的位置加上误差和减去误差来计算。在更新步骤中(算法1的第6-7行)，然后选择最低的高斜率和最高的低斜率值(在新计算的斜率和之前的斜率之间)。因此，cone 要么变窄(高斜率减小和/或低斜率增大)，要么保持不变。如果要添加到段中的新键在 cone 之外，则必须在该段中至少存在一个将违反错误约束的先前键。因此，不在 cone 内的新键不能包含在段中，并成为新段的原点

• 图5说明了如何更新圆锥体:点1是圆锥体的原点。第2点更新了高低坡度。点3在圆锥体内部，但是它只更新圆锥体的上界(点3小于下界以上的误差)。点4在更新后的圆锥体之外，因此将成为新线段的第一个点