The Case for Learned Index Structures
作者：Tim Kraska kraska@mit.edu Alex Beutel abeutel@google.com Ed H. Chi edchi@google.com Jeffrey Dean jeff@google.com Neoklis Polyzotis
时间：2018
单位：MIT，Google, Inc
解决问题：
概述和评估一种建立索引的新方法的潜力，B-tree，hash，bloom filter
原理：
即许多数据结构可以被分解为一个学习模型和一个辅助结构，以提供相同的语义保证。描述数据分布的连续函数，可以用来建立更有效的数据结构或算法。
方案：
RANGE INDEX：key映射到排序数组中的记录位置，它将一个键映射到一个有最小和最大误差的位置（最小误差为0，最大误差为页面大小）。
对于单调的模型，我们唯一需要做的是对每个key进行运算，并记住对一个位置最差的过度和不足的预测，以计算最小和最大误差。
Page：一个节点中所包含的key的数量
其中P是位置估计值，F(Key)是数据的估计累积分布函数，即X ≤ Key的概率，N是键的总数
令人惊讶的是，学习key分布的CDF是学习更好的散列函数的一种潜在方法。然而，与范围索引相反，我们的目标不是紧凑地存储记录或者按照严格排序的顺序存储记录。相反，我们可以通过哈希映射的目标大小M来缩放CDF，并使用h(K)= F(K)*M，密钥K作为我们的哈希函数。如果模型F(K)完美地学习了key的经验CDF，就不会存在冲突。
EXISTENCE INDEX
# 摘要
索引是一种模型：B-Tree-Index可以看作是将key映射到排序数组中的记录位置的模型，Hash-Index是将key映射到未排序数组中的记录位置的模型，而BitMap-Index是指示数据记录是否存在的模型。在这篇探索性的研究论文中，我们从这个前提出发，认为所有现有的索引结构都可以被其他类型的模型所取代，包括深度学习模型，我们称之为学习索引。
我们从理论上分析了在哪些条件下，学习型索引的性能优于传统索引结构，并描述了设计学习型索引结构的主要挑战。我们的初步结果显示，我们的学习型索引可以比传统索引有明显的优势。更重要的是，我们相信通过学习模型来取代数据管理系统的核心组件的想法对未来的系统设计有深远的影响，这项工作只是提供了可能的一瞥。
# 1 INTRODUCTION
值得注意的是，我们并不主张用学习型索引完全取代传统的索引结构。相反，本文的主要贡献是概述和评估一种建立索引的新方法的潜力，它补充了现有的工作，可以说为一个已有几十年历史的领域开辟了一个全新的研究方向。
这基于一个关键的观察，即许多数据结构可以被分解为一个学习模型和一个辅助结构，以提供相同的语义保证。
这种方法的潜在力量来自于描述数据分布的连续函数，可以用来建立更有效的数据结构或算法。
当在合成和真实世界的数据集上评估我们的方法时，我们在经验上得到了非常有希望的结果，用于只读分析工作负载。然而，许多开放性的挑战仍然存在，例如如何处理大量写入的工作负载，我们概述了未来工作的许多可能方向。此外，我们相信，我们可以用同样的原理来取代（数据库）系统中常用的其他组件和操作。如果成功的话，将学习到的模型深深嵌入到算法和数据结构中的核心思想可能会导致与目前开发系统的方式的彻底不同。
# 2 RANGE INDEX
范围索引结构，像B-Tree，已经是模型了：给定一个key，它们 "预测 "一个值在一个排好序的key集合中的位置。要看到这一点，请考虑图1(a)所示的分析型内存数据库（即只读）中的B-Tree索引，它覆盖了排序后的主键列。
在这种情况下，B-Tree提供了一个从查询键到排序后的记录数组内某一位置的映射，并保证该位置的记录的键是第一个等于或高于查询键的键。
数据必须被排序以允许有效的范围请求。同样的一般概念也适用于二级索引，数据将是<key,record_pointer>对的列表，key是索引值，pointer是对记录的引用
出于效率的考虑，通常不对排序后的记录的每一个键进行索引，而只对每n个记录的键进行索引，即一个页面的第一个键。这里我们只假设固定长度的记录和连续内存区域的逻辑分页，即单个阵列，而不是位于不同内存区域的物理页（物理页和可变长度记录在附录D.2中讨论）。只对每一页的第一个键进行索引，有助于大大减少索引所要存储的键的数量，而不会有任何明显的性能损失。
因此，B-Tree是一个模型，或者用ML术语来说，是一个回归树：它将一个键映射到一个有最小和最大误差的位置（最小误差为0，最大误差为页面大小），并保证如果该键存在，就可以在该区域找到。
乍一看，似乎很难用其他类型的ML模型提供同样的保证，但实际上却出奇地简单。首先，B-Tree只对存储的key提供强大的最小和最大错误保证，而不是对所有可能的钥匙。
对于新的数据，B-Tree需要重新平衡，或者用机器学习的术语说，重新训练，以便仍然能够提供同样的错误保证。
也就是说，对于单调的模型，我们唯一需要做的是对每个键执行模型，并记住对一个位置最差的过度和不足的预测，以计算最小和最大误差。
数据必须被分类以支持范围请求，所以任何错误都可以通过预测周围的局部搜索（例如，使用指数搜索）轻松纠正，因此，甚至允许非单调模型。因此，我们能够用任何其他类型的回归模型取代B-Trees，包括线性回归或神经网络（见图1（b））。
机器学习，尤其是神经网络的魅力在于，它们能够学习各种数据分布、混合物和其他数据的特殊性和模式。挑战在于如何平衡模型的复杂性和其准确性
# 2.2 Range Index Models are CDF Models
首先，这意味着索引实际上需要了解数据分布。B树通过构建回归树来“学习”数据分布。线性回归模型将通过最小化线性函数的(平方)误差来学习数据分布。第二，估计数据集的分布是一个众所周知的问题，经过几十年的研究，已经掌握的指数可以从中受益。第三，学习CDF在优化其他类型的索引结构和潜在算法方面也起着关键作用，我们将对此进行概述
在这种设置下，我们实现了每秒约1250次预测，即在没有搜索时间(从预测位置找到实际记录的时间)的情况下，使用Tensorflow执行模型需要约80，000纳秒(ns)。作为比较，对相同数据的B树遍历需要大约300纳秒，对整个数据的二分搜索法大约需要大约900纳秒。通过仔细观察，我们发现我们的方法在几个关键方面受到限制:(1) Tensorflow被设计为有效地运行较大的模型，而不是小模型，因此具有显著的调用开销，尤其是使用Python作为前端。(2) B树，或者一般的决策树，在用一些操作过度拟合数据方面确实很好，因为它们使用简单的if语句递归地划分空间。
相比之下，其他模型可以更有效地近似CDF的一般形状，但在单个数据实例级别的准确性方面存在问题。为了看到这一点，再次考虑图2。该图表明，从顶层来看，CDF函数显得非常平滑和规则。然而，如果放大到单个记录，会显示出越来越多的不规则性；众所周知的统计效应。因此，像神经网络、多项式回归等模型。将项目的位置从整个数据集缩小到数千个区域可能会更有效地利用CPU和空间，但是单个神经网络通常需要更多的空间和CPU时间用于“最后一英里”,以将误差从数千进一步减少到数百。(3) B树具有极高的缓存和操作效率，因为它们将顶部节点始终保存在缓存中，并在需要时访问其他页面。相比之下，标准神经网络需要所有权重来计算预测，这在乘法次数上具有高成本。
# 3.2 The Recursive Model Index
这种模型架构有几个好处:
它将模型大小和复杂性与执行成本分开。
它利用了易于了解数据分布的整体形状的事实。
它有效地将空间划分成更小的子范围，像B树一样，以更少的操作更容易实现所需的“最后一英里”精度。
在阶段之间不需要搜索过程。例如，模型1.1的输出直接用于挑选下一阶段的模型。这不仅减少了管理结构的指令数量，还允许将整个索引表示TPU/GPU的稀疏矩阵乘法。
# 3.3 Hybrid Indexes
递归模型索引的另一个优点是，我们能够构建混合模型。例如，在顶层，小型ReLU神经网络可能是最佳选择，因为它们通常能够学习各种复杂的数据分布，而在模型层次结构底部的模型可能是数千个简单的线性回归模型，因为它们在空间和执行时间上是廉价的。如果数据很难学习，甚至可以在底层使用传统的B树。
在本文中，我们关注两种类型的模型，简单的神经网络，具有零到两个完全连接的隐藏层和ReLU激活函数，层宽高达32个神经元和B树(也称为决策树)。请注意，零隐藏层神经网络相当于线性回归。给定一个索引配置，它将阶段数和每个阶段的模型数指定为一个大小数组，混合索引的端到端训练如算法1所示
学习索引与B树性能:主要结果如图4所示。请注意，B树的页面大小表示每页的键数，而不是以字节为单位的大小，后者实际上更大。作为主要指标，我们以MB为单位显示了大小，以纳秒为单位显示了总查找时间，以纳秒为单位显示了执行模型(B树遍历或ML模型)的时间，并显示了与paranthesis中的总时间相比的百分比。此外，作为大小和查找列的一部分，我们在括号中显示了与页面大小为128的B树相比的加速和空间节省。我们选择128的页面大小作为固定参考点，因为它为B树提供了最佳的查找性能(注意，通过简单地没有索引，总是很容易以牺牲查找性能为代价来节省空间)。加速和大小列中的颜色编码表示索引相对于参考点的快慢程度(大或小)。
然而，无论哈希映射架构如何，冲突都会对性能和/或存储需求产生重大影响，并且机器学习模型可以提供减少冲突数量的替代方案。虽然将模型作为哈希函数来学习的想法并不新鲜，但是现有的技术并没有利用底层的数据分布。例如，各种完美的散列技术[26]也试图避免冲突，但是用作散列函数一部分的数据结构随着数据大小而增长；学习模型可能没有的属性(回想一下，索引1到100M之间的所有键的例子)。据我们所知，还没有探索是否有可能学习产生更有效的点指数的模型。
总之，我们已经证明，机器学习模型有可能提供比最先进的索引更多的好处，我们相信这是未来研究的一个富有成效的方向