Jeff Dean在SystemML会议上的论文解读：学习索引结构的一些案例

难易
学习索引结构的一些案例The Case for Learned Index Structures
Tim Kraska1 MIT Cambridge, MA kraska@mit.edu
Alex Beutel Google, Inc. Mountain View, CA alexbeutel@google.com
Ed H. Chi Google, Inc. Mountain View, CA edchi@google.com
Jeffrey Dean Google, Inc. Mountain View, CA jeff@google.com
Neoklis Polyzotis Google, Inc. Mountain View, CA npolyzotis@google.com
译注原文： https://www.arxiv-vanity.com/papers/1712.01208/
视频：https://www.youtube.com/watch?v=PWv4ROEvqmk
如果想下载 PDF 或者进一步讨论的可以到这里： https://gitee.com/hardysimpson/sysML
1. 摘要索引是模型：B 树索引可以被看作是一个模型，用于将键 (Key) 映射到排序数组中的值记录 (Value) 位置，Hash 索引作为模型将键 (Key) 映射到未排序数组的值记录 (Value) 位置，BitMap 索引作为模型来指示值记录 (Value) 是否存在。 在这个探索性研究论文中，我们从这个前提开始，并假定所有现有的索引结构都可以用其他类型的模型取代，包括我们称为学习索引的深度学习模型。关键的想法是，模型可以学习查找键 (Key) 的排序顺序或结构，并使用这个信息来有效地预测值记录 (Value) 的位置或存在。 我们从理论上分析了在哪些条件下，学习索引优于传统索引结构，并描述了设计一个好的学习索引的主要挑战。 我们的初步结果表明，通过使用神经网络，学习索引能达到比高速缓存优化的 B-Tree 快 70% 的速度，并且节省几个数量级的内存，来索引几个真实世界的数据集。 更重要的是，我们相信通过深度学习模型取代数据管理系统的核心组件对于未来的系统设计有着深远的影响，而且这项工作只是提供了一些可能的一瞥。
2. 介绍无论何时需要有效的数据访问，索引结构都是答案，并且存在各种各样的选择来满足各种访问模式的不同需求。 例如，B 树是范围查找的最佳选择（例如，在特定时间范围内检索一段值记录 (Value)）; HashMap 在单 Key 查找这个领域是无敌的 ; 而 Bloom-filter 通常用于检查值记录 (Value) 是否存在。 由于数据库和许多其他应用的索引非常重要，因此在过去的几十年里，它们已经得到了广泛的优化，以获得更高的内存、缓存和 CPU 效率[ 28,48,22,11]。
然而，所有这些索引仍然是通用数据结构，假设数据的最坏情况分布，并没有利用现实世界数据中存在的更常见模式。 例如，如果目标是建立高度特定的系统，用来存储和查询具有连续整数键 (Key) 的固定长度值记录 (Value)（例如，键 (Key) 从 1 到 100M），那么设计者就不会使用常规的 B 树索引，因为键 (Key) 本身可以用作偏移量来作查找或者范围查询，达到 O(1) 而不是 O(long n) 的时间复杂度。 而且，索引内存大小将从 O(n) 减小到 O(1) 。也许令人惊讶的是，对于其他数据结构，相同的优化仍然是可能的。 换句话说，了解确切的数据分布可以高度优化数据库系统使用的几乎所有索引。
当然，在大多数现实世界的用例中，数据并不完全遵循已知的模式，为每个用例构建专门解决方案的代价都太高了。 然而，我们认为机器学习为挖掘数据里面的模式和相关性提供了一个机会，从而能够以低工程成本，自动合成我们称为学习索引的索引结构。
在本文中，我们探讨了学习模型（包括神经网络）在多大程度上可以用来代替传统的 B 树到 Bloom-filter 的索引结构。 这似乎与直觉相反，因为机器学习并不提供传统的索引数据结构的输入输出，并且因为最强大的机器学习模型，神经网络的计算一般认为是非常昂贵的。 然而，我们认为，这些明显的障碍都不像它们看起来那么坑爹。 相反，我们使用学习模型的方式可能会带来巨大的好处，特别是在下一代硬件上。
就输入输出的语义来说，索引在很大程度上已经是学习模型，使得用神经网络等其他类型的模型取代它们变得非常简单。 例如，B 树可以被看作是一个模型，它将一个键 (Key) 字作为输入并预测数据值记录 (Value) 的位置。 Bloom-Filter 是一个二元分类器，它基于一个键 (Key) 来预测键 (Key) 是否存在于一个集合中。 显然，这就存在微妙但重要的差异。 例如，Bloom-filter 可能有假阳性 (false positives)，但没有假阴性 (false negatives)。然而，正如我们将在本文中展示的那样，可以通过新颖的学习技术和 / 或简单的辅助数据结构解决这些差异。
在性能方面，我们观察到每个 CPU 都具有强大的 SIMD 功能，并且我们推测许多笔记本电脑和手机很快将拥有图形处理单元（GPU）或张量处理单元（TPU）。 推测 CPU-SIMD / GPU / TPU 的功能将越来越强大，这是合理的，因为比通用指令集更容易扩展神经网络使用的有限的（并行）数学运算。 这样，今后执行神经网络的高成本在未来可能实际上可以忽略不计。例如，Nvidia 和 Google 的 TPU 已经能够在单个指令周期中执行数千次（如果不是数万次）神经网络操作[ 3 ] 。 此外，有人表示，到 2025 年，GPU 的性能将提高 1000 倍 ，而 CPU 发展已经停滞，不按摩尔定律发展[ 5 ] 。通过用神经网络取代重分支的索引结构，数据库可以从这些硬件趋势中受益。
重要的是要指出，我们并不主张用学习索引结构来完全取代传统的索引结构。 相反，我们概述了一种建立索引的新方法，它补充了现有的工作，并且可以说为一个有数十年历史的领域开辟了一个全新的研究方向。 虽然我们专注于分析只读工作负载，但我们还概述了如何将这种想法扩展到对写入频繁工作负载的索引做加速。 此外，我们简要概述如何使用相同的原则来替换数据库及其他组件的操作，包括排序和联表 (join)。 如果成功，这可能导致未来数据库的开发方式和现在彻底不同。
本文的其余部分概述如下：在下一节中，我们以 B 树为例介绍学习索引的总体思路。 在第 4 节中，我们将这个想法扩展到 Hash 索引，并在第 5 节中扩展到 Bloom-Filters。 所有部分都包含单独的评估和列出未解决的挑战。最后在第 6 部分我们讨论相关的工作，并在第 7 部分结束。
图 1：为什么 B 树是模型## 3. 范围索引索引结构已经是模型，因为它们可以 “ 预测 ” 给定键 (Key) 的值的位置。 要看到这一点，请在主键 (Key) 已排序的分析内存数据库（即只读）中考虑一个 B 树索引，如图[1]（a）所示。 在这种情况下，B-Tree 提供从查找键 (Key) 到排序的值记录 (Value) 阵列内的位置的映射，并保证值记录 (Value) 位置大于等于查找到的位置。 请注意，必须对数据进行排序以允许范围请求。 还要注意，这个相同的一般概念适用于次级索引，其中底层将是 <key，pointer> 对的列表，其中键 (Key) 是索引属性的值，指针是对值记录 (Value) 的引用。出于效率的原因，通常不会对已排序值记录 (Value) 的每个关键 (Key) 字进行索引，而只是每个 n 个值记录 (Value) 的一个键 (Key)，即每页面的第一个键 (Key)。 [2] 这有助于显着减少索引必须存储的键 (Key) 数量，而不会有任何显着的性能损失。 因此，B 树是一个模型，在 ML 术语中是回归树：它将键 (Key) 映射到具有最小和最大误差的位置之间（最小误差 0，最大误差页面大小）并保证可以在该地区找到该键 (Key) 锁对应的值记录 (Value)（如果存在）。 因此，我们可以用其他类型的机器学习模型（包括深度学习模型）取代 B 树索引，只要它们也能够提供类似的有关最小误差和最大误差的有力保证。乍一看，可能很难为其他类型的 ML 模型提供相同的错误保证，但它实际上非常简单。 B-Tree 仅为存储的数据提供这种保证，而不是针对所有可能的数据。 对于新数据，B 树需要重新平衡，或者在机器学习的术语里面叫重新训练，通过训练来提供相同的误差保证。 这就极大地简化了问题：最小误差和最大误差是经过训练的（即存储的）数据的最大误差。 也就是说，我们唯一需要做的就是对每个键 (Key) 执行训练，并记住一个位置的最好和最差的位置预测。 给定一个键 (Key)，该模型预测哪里能找到相应的值记录 (Value); 如果键 (Key) 存在，则保证处于由最小和最大误差定义的预测范围内。 因此，我们能够用任何其他类型的回归模型（包括线性回归或神经网络）代替 B 树（见图[1]（b））。现在，我们需要解决其他技术挑战，然后才能使用学习好的索引替代 B 树。 例如，B 树具有插入和查找的有限成本，并且在利用缓存方面特别好。 此外，B 树可以将键 (Key) 映射到未连续映射到内存或磁盘的页面。 此外，如果查找关键 (Key) 字不存在于集合中，某些模型可能会返回最小 / 最大错误范围之外的位置，如果它们不是单调递增的模型。所有这些都是有趣的挑战 / 研究问题，会在本节中与潜在解决方案一起详细解释。同时，使用其他类型的模型，特别是深度学习模型作为索引可以提供巨大的好处。 最重要的是，它有可能把 B 树 log n 查找成本为一个常数。 例如，假定数据集具有 1M 个唯一键 (Key)，大小在 1M 和 2M 之间（因此 1,000,009 存储在第 10 个位置上）。 在这种情况下，一个简单的线性模型，由一个单一的乘法和加法组成，可以完美地预测任何键 (Key) 的位置，而 B 树会需要做一个 log n 操作。 机器学习，尤其是神经网络的优点在于，他们能够学习各种各样的数据分布 / 混合和其他数据特征和模式。 显然，挑战在于平衡模型的复杂性与准确性。### 3.1 我们可以承受模型有多复杂？ 来做个估算吧为了更好地理解模型的复杂性，需要知道同样的一段时间内，遍历 B 树可以执行多少操作，以及学习索引需要达到什么样的精度来超过 B 树的精度。考虑一个 B 树索引 100M 值记录 (Value)，页面大小为 100（译注：也就是单个节点的子节点数量，国内有翻译为阶的）。我们可以将每个 B-Tree 节点视为划分空间的一种方式，减少 “ 误差 ” 并缩小区域以查找数据。 因此，我们说 B-Tree 的页面大小为 100，每个节点的查找精度为 1/100 ，所以我们需要遍历 log(100, N) 个节点。 因此，第一个节点将查找空间从 100 M 缩小到 100 M / 100 = 1 M ，第二个节点从 1 M 到 1 M / 100 = 10 k 等等，直到找到值记录 (Value) 为止。 同时，遍历单个 B-Tree 页面需要大约 50 个时钟周期（我们测量了对超过 100 个缓存驻留记录的二分查找与遍历查找具有大致相同的性能），并且非常难以并行化 [3]。 相比之下，现代 CPU 可以在每个周期执行 8-16 个 SIMD 操作。 因此，只要学习索引模型的 查找精度 / 运算数 超过 (1/100) / 50  8 = 400 个算术运算，学习索引模型就会更快（译注：这里隐含了一个公式，查找速度 = 查找精度 / 运算数，也就是单位时间内的 查找概率）。 请注意，这个估算仍假定所有 B 数的页都在缓存中。 单个缓存未命中花费 50-100 个额外的周期，因此可以允许更复杂一些的模型。此外，机器学习的快速发展正在彻底改变游戏。 它们允许在相同的时间内运行更复杂的模型，并从 CPU 中卸载计算（到 GPU 或 TPU 上）。 例如，NVIDIA 最新的 Tesla V100 GPU 能够实现 120 TeraFlops 的低精度的深度学习算术运算（每个时钟周期 ≈60,000 次运算） [ 7 ]。 假设整个学习索引都载入了 GPU 的内存（我们在 3.6 节中展示这是一个非常合理的假设），在 30 个时钟周期内，我们可以执行 100 万次神经网络操作。 当然，传输输入和从 GPU 获取结果的延迟仍然明显较高，大约为 2 微秒或数千个时钟周期，但这个问题并非不可克服，可以通过批处理方式，或者更加紧密的集成 CPU/ GPU / TPU [ 4 ] 。 最后，可以预期，GPU / TPU 每秒的浮点 / 整型操作的能力和数量将继续增加，而提高 CPU 执行 if 语句性能的进展基本上停滞不前[ 5 ]。 尽管我们认为 GPU / TPU 是实践中采用* 学习索引的主要原因，但本文中我们将重点放在有限的 CPU 能力上，以便更好地研究通过机器学习取代 / 增强索引的影响，排除硬件更改的因素。
图 2：作为 CDF 的索引
3.2 范围索引模型是 CDF 模型正如本节开头所述，索引是一个模型，它将一个键 (Key) 字作为输入并预测值记录 (Value) 的位置。 而对于单点查询，值记录 (Value) 的顺序并不重要，对于范围查询，必须根据查找关键 (Key) 字对数据进行排序，以便可以有效地检索范围内（例如，时间范围内）的所有数据项。 这导致了一个有趣的观察：预测给定排序数组内键 (Key) 的位置的模型有效地近似于累积分布函数（CDF）。 我们可以建模数据的 CDF 来预测位置：
其中 p 是位置估计， F (Key) 是小于或等于查找键 (Key) 的数据出现的概率，也就是累积分布函数 (CDF, estimated cumulative distribution function, 详见这篇)，N 是键 (Key) 的总数量（另见图[2]）。 这个观察开辟了一套全新的有趣方向：首先，它意味着任何一种索引字面上都需要学习数据分布。 B 树通过构建回归树来 “ 学习 ” 数据分布。 线性回归模型将通过最小化线性函数的 (平方) 误差来学习数据分布。 其次，估计数据集的分布是一个众所周知的问题，学习索引可以从之前数十年的研究中受益。 第三，学习 CDF 对优化其他类型的索引结构和潜在算法也起着关键作用，我们将在本文后面概述。
3.3 第一个，粗糙的学习索引为了更好地理解用学习索引取代传统 B 树有哪些技术要求，我们使用了 200M Web 服务器日志值记录，目标是使用 Tensorflow [ 9 ]在时间戳上建立二级索引。 我们使用 ReLU 激活函数训练了每层 32 个神经元（即 32 个宽度）的双层全连接神经网络 ; 时间戳是输入要素，位置是标签。
之后，我们使用 Tensorflow 和 Python 作为前端，测量随机选择的键的查找时间 (排除一开始跑的一些数据)。 在这种情况下，我们实现了每秒 ≈1250 次预测，即，使用 Tensorflow 执行模型需要 ≈80,000 纳秒 (ns)，甚至没算搜索时间。 预测对全量遍历几乎没有什么帮助。 作为比较，B 树遍历同样数据只需要 ≈300 ns， 小两个数量级，搜索键 (Key) 空间时，并且快 2-3 倍 。 其原因是多方面的：
Tensorflow 旨在有效地运行较大的模型，而不是小型模型，因此具有显着的调用开销，尤其是在 Python 作为前端时。
一般来说，B 树，或者一般意义上的决策树，使用少量的操作就能过拟合数据，因为它们使用简单的 if 语句递归地分割空间。 相比之下，其他模型可以更有效地估计 CDF 的总体形状，但在单个数据实例级别的精确定位上有障碍。 要看到这个，请再次看看图[2] 。 该图表明，从大的视图看，CDF 函数看起来非常平滑和规则。 但是，如果放大单个值记录 (Value)，越来越多的非规律显示出来 ; 一个众所周知的统计效应。 许多数据集恰恰具有这种行为：从大局看，数据分布显得非常平滑，而越放大越难接近 CDF，由于个体层面上的 “ 随机性 ”。 因此，像神经网络，多项式回归等模型可能需要更多的 CPU 和空间从整个数据集缩小到到数千项中选择单个（译注，这里也就是在上文中指的预测误差，min/max error），单个神经网络通常需要更多的空间和 CPU 时间为 “ 最后一公里 ” 减少从数千到数百的误差。
典型的 ML 优化目标是最小化平均误差。 但是，对于索引，我们不仅需要猜测项目的最佳位置，而且还需要实际找到它，但前面讨论的最小和最大误差率更重要。
B- 树的缓存效率非常高，因为它们始终将顶层节点保存在缓存中，并在需要时访问其他页面。 但是，其他模型并不像缓存和操作高效。 例如，标准神经网络需要所有权重参数来做预测，这种预测需要大量的乘法和权重参数，必须从内存中读入到缓存 (译注，这里和上面的缓存都是指 CPU 高速缓存)。
4. RM 索引 (Recursive-model，递归模型)为了克服挑战并探索模型作为索引替代或丰富的潜力，我们开发了学习索引框架 （LIF），递归模型索引（RMI）和基于标准误差的搜索策略。 我们主要关注简单的全连接神经网络，因为它们的简单性，但其他许多类型模型也是可能的。
4.1 学习索引框架（LIF）LIF 可以看作是一个索引合成系统或者说索引工厂 ; 给定一个索引规范， LIF 生成不同的索引配置，优化它们并自动化测试它们。 虽然 LIF 可以即时学习简单模型（例如，线性回归模型），但它依赖于更复杂模型（例如 NN）的 Tensorflow。 但是，它从不使用 Tensorflow 进行推理。 相反，给定一个经过训练的 Tensorflow 模型， LIF 会自动从模型中提取所有权重，并根据模型规范在 C ++ 中生成高效的索引结构。 虽然使用 XLA 的 Tensorflow 已经支持代码编译，但其重点主要放在大规模计算上，其中模型的执行时间量级是微秒或毫秒。 相比之下，我们的代码生成专注于小型模型，因此必须消除 Tensorflow 管理大模型的开销。 这里我们利用来自[ 21 ]的想法，它已经展示了如何避免 Spark 运行时不必要的开销。 因此，我们能够执行 30 纳秒级的简单模型。
4.2 递归模型索引如第 2.3 节所述，构建替代 B 树的替代学习模型的关键挑战之一是最后一英里的准确性。 例如，使用单个模型把误差从 100M 减少到几百这个数量级是非常困难的。 同时，将误差从 100M 降低到 10K，例如 100 * 100 = 10000 的精度实现起来还简单些，这样就可以用简单模型替换 B-Tree 的前两层。 同样的，将误差从 10k 降低到 100 是一个更简单的问题，因为模型只需要关注数据的一个子集。
基于这种观察并受到专家们的共同努力[ 51]的启发，我们提出了递归回归模型（参见图[3]）。 也就是说，我们构建了一个模型层次结构，其中模型的每个阶段都将键 (Key) 作为输入，并基于它选择另一个模型，直到最终预测到位置。 更正式地说，对于我们的模型 f(x) ，其中 x 是键， y∈ [ 0 ， N ) 位置，我们假设在阶段ℓ有 M 个模型。 我们在阶段 0 训练模型， (f0(x) ≈y)。 因此，阶段ℓ中的模型 k，可以写成由(fℓ^{(k)})表示 ，并且被损失地训练，整个误差可以表示为如下公式：
注意，我们在这里使用这里的符号(f_{ℓ-1}(x))递归执行，这样
总而言之，我们用迭代地训练每个阶段，误差为(L_ℓ)，以建立完整的模型。
图 3：分阶段模型
理解多个不同模型的一种方法是，每个模型都会对关键位置进行一定的预测误差，并使用预测来选择下一个模型，该模型负责将键 (Key) 空间的某个区域以较低的误差做出更好的预测。 然而，要注意，递归模型索引不是树 。 如图[ 3 ]所示，一个阶段的不同模型可能会在下面的阶段选择相同的模型。 此外，每个模型并不一定像 B-Tree 那样包括同样数量的记录（即页面大小为 100 的 B 树覆盖 100 个或更少的记录）。 4 最后，取决于所使用的模型，不同阶段之间的预测不一定会被解释为位置估计，而应该被视为挑选对某些键有更多认知的专家（另见[ 51 ] ）。
这种模型体系结构有几个好处：(1) 它利用了这一事实，即易于学习数据分布的整体形状。(2) 它的体系结构有效地将空间划分为更小的子空间，就像 B 树 / 决策树那样，通过更少的操作更容易地实现所需的 “ 最后一英里 ” 精度。 (3) 在阶段之间不需要搜索过程。 例如， 模型 1.1 的输出 y 是一个偏移量，它可以直接用于在下一阶段中选择模型。 这不仅减少了管理数据结构的指令数量，而且还允许将整个索引表示为稀疏矩阵乘法跑到 TPU / GPU 上。
4.3 混合索引递归模型索引的另一个优点是，我们能够建立模型的混合。 例如，在顶层，一个小的 ReLU 神经网络可能是最好的选择，因为它们通常能够学习大范围的复杂数据分布，模型层次结构底部的模型可能有数千个简单的线性回归模型，因为它们在空间和执行时间都不贵。 此外，如果数据特别难以学习，我们甚至可以在最后阶段使用传统的 B 树。
对于本文，我们只关注 2 种模型，简单的神经网络，具有 0 到 2 个完全连接的隐藏层和 ReLU 激活函数，以及多达 32 个神经元和 B 树（也就是决策树）的层宽度。 给定一个索引配置，它指定阶段的数量和每个阶段的模型数量作为一个数组，混合索引的端到端训练按照算法 1 完成
<strong>`
    Algorithm 1: Hybrid End-To-End Training
    Input: int threshold, int stages[], NN complexity
    Data: record data[], Model index[][]
    Result: trained index
     1 M = stages.size;
     2 tmp records[][];
     3 tmp records[1][1] = all data;
     4 for i  <- 1 to M do
     5    for j <- 1 to stages[i] do
     6        index[i][j] = new NN trained on tmp records[i][j];
     7        if i < M then
     8             for r ∈ tmp records[i][j] do
     9                 p = f(r.key) / stages[i + 1];
    10                 tmp records[i + 1][p].add(r);
    11 for j <- 1 to index[M].size do
    12         index[M][j].calc_err(tmp records[M][j]);
    13         if index[M][j].max abs err > threshold then
    14             index[M][j] = new B-Tree trained on tmp records[M][j];
    15 return index;
`</strong>
从整个数据集（第 3 行）开始，它首先训练顶级节点模型。 根据这个顶级节点模型的预测，它会从下一阶段（第 9 行和第 10 行）中选取模型，并添加属于该模型的所有键（第 10 行）。 最后，在混合指标的情况下，如果绝对最小 / 最大误差高于预定义阈值（第 11-14 行），则通过用 B 树代替 NN 模型来优化指数。
请注意，我们在最后阶段为每个模型存储标准误差和最小误差和最大误差。 这样做的好处是，我们可以根据每个键 (Key) 的使用模型单独限制搜索空间。 此外，人们可能会想知道具体如何设置混合端到端训练的各种参数，包括阶段的数量和宽度，神经网络配置（即隐藏层数和宽度）以及何时替换节点的阈值为一棵 B 树。 通常，这些参数可以使用简单的网格搜索进行优化。 此外，可以根据时间来限制搜索空间（找到这些参数）。 例如，我们发现阈值为 128 或 256（B 树的典型页面大小）效果很好。 此外，对于 CPU，我们基本负担不起 1 或 2 个完全连接的隐藏层以及每层 8 至 128 个神经元的神经网络。 最后，考虑到模型的容量较低，可以用较小的数据样本训练较高层的阶段的模型，这显然加快了培训过程。
请注意，混合索引允许我们将学习索引的最差情况性能与 B 树的性能相关联。 也就是说，在学习不到数据分布的情况下，所有模型都会被 B-Trees 自动替换，实际上是一个完整的 B-Tree（阶段之间有一些额外的开销等等，但是性能是总体相似）。
4.4 搜索策略要在叶页中查找实际记录，对于小数据量，无论是二进制搜索还是全量扫描通常都是最快的策略 ; 尽管（业内）作出了许多尝试，但反复的结果表明， 其他搜索策略由于其额外的复杂性而没有提供什么（如果有的话）益处[ 8 ]) ] 。 再一次，学习索引在这里也可能具有优势：模型实际上预测了键 (Key) 的位置，这可能更接近值记录 (Value) 的实际位置，而用最小 / 最大误差会差的更远些。 这就是说，如果我们可以利用这样一个事实，即在位置估计最小误差和最大误差范围内，我们对位置进行了良好估计，那么我们可能能够找到记录（或 <= 查找键的键）比传统的二进制搜索更快。 因此我们制定了几种搜索策略。
模型二进制搜索：我们的默认搜索策略，和传统的二分搜索策略的唯一区别在于，把第一个中间点设为模型预测的值。
偏见搜索：这种搜索策略修改了我们的模型二分搜索，在每次迭代中不会平均分割从中间点到左侧和右侧的距离。 相反，新中间值取决于最后阶段的模型的输出的标准偏差 σ 。 例如，如果确定键 (Key) 大于中间值 ，则将新中间值设置为 min(middle+σ,(middle+right)/2)。
偏见四元搜索：最后，我们开发了一种新的搜索策略，在任何迭代中都不会选择一个新的中间值来进行二分搜索，而是用了三个新的数据点，即所谓的四元搜索。 研究人员过去尝试四元搜索的主要原因是因为它可以提供更好的预取行为。 也就是说，首先计算三个 “ 中间 ” 点，由使用 CPU intrinsics 来计算。 之后才会测试不同的 “ 中间 ” 点，并根据结果进行搜索的下一次迭代，非常类似于二分查找。 如果 CPU 能够从主存储器 (Memory) 中并行获取多个数据地址，那么这种策略可能更好，但据报道实际上这种策略大部分与二进制搜索相同[ 8 ] 。 然而，再次有一个更好的位置估计可能会有所帮助：也就是说，我们将我们最初的三个四元搜索中点定义为 pos - σ ， pos ， pos + σ 。 我们假设，大部分预测都是准确的，首先关注位置估计，然后继续传统的四元搜索。
4.5 索引字符串我们主要关注索引真正有值记录 (Value) 的键 (Key)，但许多数据库依赖索引字符串，幸运的是，有不少重要的机器学习研究聚焦在字符串建模上。 和以前一样，我们需要设计一个高效但有表现力的字符串模型。 对字符串做好这个设计会带来许多独特的挑战。
第一个设计考虑是如何将字符串转换为模型的特征，通常称为标记化。 为了简单和高效，我们认为 n 长度的字符串是长度为(x∈\mathbb{R}^n)的特征向量，其中(x_i)是第 i 位的字符的 ASCII 十进制值（或者取决于字符串的 Unicode 十进制值）。 此外，如果所有输入的尺寸相同，大多数 ML 模型的运行效率会更高。 因此，我们将设置最大输入长度 N。 由于数据按字典顺序排序，我们将在标记化之前将键截断为长度 N. 对于长度为 n < N 的字符串，我们为 i > n 设置(x_i = 0) 。
为了提高效率，我们通常采用与我们针对数据特征相似的建模方法。 我们学习了一个相对较小的前馈神经网络的层次结构。 一个区别是输入不是一个单一的实数值 x，而是一个向量 x 。 线性模型 w⋅x + b 随着输入长度 N 线性地增加乘法和加法的计算数量。 前馈神经网络，带有一个宽度为 h 的隐藏层，也会扩展到 O(hN) 乘法和加法计算数量。（在与 N 无关的更深层网络中可能会有额外的复杂性）。
这种方法有一些有趣的特性，表明了设计字符串 CDF 的一般 ML 模型的困难。 如果我们考虑长度为三的八个字符串，字符串里面的字符是[0,8) ，那么我们可以容易地对位置建模为 (4 x_0 + 2 x_1 + x _2^5) 。 但是，如果我们看看 Unix 字典的编码，我们会发现数据更加的复杂。 以 “s” 以 “e” 开头的单词是其他单词的三倍，这样甚至对单词里面的第一个字符就没法线性建模。 此外，字符之间存在相互作用 - 大约 10％以 “s” 开头的单词以 “sh” 开头，而以 “e” 开头的单词只有 0.1％以 “eh” 开头. DNN 算法，如果足够宽或足够深，可以成功地对这些相互作用进行建模，更常见的是，递归神经网络（RNN）在建模文本中显示出非常成功。
最终，我们相信未来会有相当好的研究可以优化字符串的学习索引。 例如，我们可以轻松想象其他标记化算法。 在字符串标记化的自然语言处理方面有大量研究将字符串分解为 ML 模型中更有用的部分，例如机器翻译中的字词[ 59] 。 此外，还有大量关于特征选择的研究选择最有用的特征子集，从而限制模型需要处理的特征的数量。 此外，GPU 和 TPU 需要相对较大的模型，因此可以无缝扩展字符串长度增加的场景，及许多更复杂的模型体系结构（例如递归和卷积神经网络）中。
4.6 结果为了将学习指标与 B 树进行比较，我们在 3 个实际数据集上创建了 4 个二级索引：（1）Weblogs，（2）地图数据集[ 46]和（3）web 文档以及 1 个合成数据集（4）正态对数。 Weblogs 数据集包含 200 M 日志条目，是多年来对主要大学网站的每个 web 请求，并对唯一时间戳进行主索引。 该数据集对于学习索引来说几乎是一种最坏的情况，因为它包含由课程安排，周末假期，午餐休息，部门活动，学期休息等引起的非常复杂的时间模式，这是众所周知的难以学习的。 对于地图数据集，我们将世界各地 ≈200M 用户维护特征（例如道路，博物馆，咖啡店）的经度编入索引。 不出所料，位置的经度相对线性，并且比 weblog 数据集的不规则性更少。 web 文档数据集由大型互联网公司的真实产品组成部分的大型网络索引的 10 M 个非连续文档 ID 组成。 最后，为了测试索引如何处理重尾分布，我们生成了一个从 μ = 0 和 σ = 2 的对数正态分布中抽取的 190M 独特值的综合数据集。 这些值被放大到整数 1Billon。 这些数据当然是高度非线性的，这使得 CDF 使用神经网络学习更加困难。
对于所有数据集，我们使用不同页面大小的 B 树和不同的第二阶段大小（即 10k，50k，100k 和 200k 模型数量）的 RMI学习索引进行比较。 我们的 B 树实现类似于 stx :: btree，但做了进一步的行缓存优化，在一个针对 FAST 的微基准[ 36]对比测试中性能很强，在这个测试中把我们的 B- 树和一个把 SIMD 优化用的出神入化的 B 树作比较，跑起来差不多。我们使用简单的网格搜索，基于简单模型来调整两阶段模型。 也就是说，我们只尝试了具有零到两个隐藏层的神经网络和层数为 4 到 32 个节点的神经网络。 一般而言，我们发现，对于第一阶段而言，简单的（0 隐藏层）到半复杂（2 隐藏层，8 或 16 宽）模型效果最好。 对于第二阶段来说，它变成了我们的简单（0 隐藏层），它们基本上是线性模型，具有最佳性能。 这并不令人惊讶，因为对于最后一英里来说，执行复杂模型往往是不值得的，线性模型可以被最优学习。最后，我们所有学习的索引模型都使用 LIF 进行编译，并且我们只显示具有 32GB RAM 的 Intel-E5 CPU 上性能最佳的模型的数字， 而不使用 GPU / TPU，进行超过 30M 次的查找，重复 4 次。