学习索引结构的一些案例——Jeff Dean在SystemML会议上发布的论文(中)

摘要: 原文： https://www.arxiv-vanity.com/papers/1712.01208/ 视频：https://www.youtube.com/watch?v=PWv4ROEvqmk 本文是Google的Fellow，Jeff Dean，把机器学习应用到系统设计的论文，原文发布在SystemML会议上，我做了翻译。

第一篇请参见：学习索引结构的一些案例——Jeff Dean在SystemML会议上发布的论文(上)

3. RM索引(Recursive-model，递归模型)

为了克服挑战并探索模型作为索引替代或丰富的潜力，我们开发了学习索引框架 （LIF），递归模型索引（RMI）和基于标准误差的搜索策略。 我们主要关注简单的全连接神经网络，因为它们的简单性，但其他许多类型模型也是可能的。

3.1 学习索引框架（LIF）

LIF可以看作是一个索引合成系统或者说索引工厂; 给定一个索引规范， LIF生成不同的索引配置，优化它们并自动化测试它们。 虽然LIF可以即时学习简单模型（例如，线性回归模型），但它依赖于更复杂模型（例如NN）的Tensorflow。 但是，它从不使用Tensorflow进行推理。 相反，给定一个经过训练的Tensorflow模型， LIF会自动从模型中提取所有权重，并根据模型规范在C ++中生成高效的索引结构。 虽然使用XLA的Tensorflow已经支持代码编译，但其重点主要放在大规模计算上，其中模型的执行时间量级是微秒或毫秒。 相比之下，我们的代码生成专注于小型模型，因此必须消除Tensorflow管理大模型的开销。 这里我们利用来自[ 21 ]的想法，它已经展示了如何避免Spark运行时不必要的开销。 因此，我们能够执行30纳秒级的简单模型。

3.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训练模型， $$f_0(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上。

3.3 混合索引

递归模型索引的另一个优点是，我们能够建立模型的混合。 例如，在顶层，一个小的ReLU神经网络可能是最好的选择，因为它们通常能够学习大范围的复杂数据分布，模型层次结构底部的模型可能有数千个简单的线性回归模型，因为它们在空间和执行时间都不贵。 此外，如果数据特别难以学习，我们甚至可以在最后阶段使用传统的B树。

对于本文，我们只关注2种模型，简单的神经网络，具有0到2个完全连接的隐藏层和ReLU激活函数，以及多达32个神经元和B树（也就是决策树）的层宽度。 给定一个索引配置，它指定阶段的数量和每个阶段的模型数量作为一个数组，混合索引的端到端训练按照算法1完成

    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;

从整个数据集（第3行）开始，它首先训练顶级节点模型。 根据这个顶级节点模型的预测，它会从下一阶段（第9行和第10行）中选取模型，并添加属于该模型的所有键（第10行）。 最后，在混合指标的情况下，如果绝对最小/最大误差高于预定义阈值（第11-14行），则通过用B树代替NN模型来优化指数。

请注意，我们在最后阶段为每个模型存储标准误差和最小误差和最大误差。 这样做的好处是，我们可以根据每个键(Key)的使用模型单独限制搜索空间。 此外，人们可能会想知道具体如何设置混合端到端训练的各种参数，包括阶段的数量和宽度，神经网络配置（即隐藏层数和宽度）以及何时替换节点的阈值为一棵B树。 通常，这些参数可以使用简单的网格搜索进行优化。 此外，可以根据时间来限制搜索空间（找到这些参数）。 例如，我们发现阈值为128或256（B树的典型页面大小）效果很好。 此外，对于CPU，我们基本负担不起1或2个完全连接的隐藏层以及每层8至128个神经元的神经网络。 最后，考虑到模型的容量较低，可以用较小的数据样本训练较高层的阶段的模型，这显然加快了培训过程。

请注意，混合索引允许我们将学习索引的最差情况性能与B树的性能相关联。 也就是说，在学习不到数据分布的情况下，所有模型都会被B-Trees自动替换，实际上是一个完整的B-Tree（阶段之间有一些额外的开销等等，但是性能是总体相似）。

3.4 搜索策略

要在叶页中查找实际记录，对于小数据量，无论是二进制搜索还是全量扫描通常都是最快的策略; 尽管（业内）作出了许多尝试，但反复的结果表明， 其他搜索策略由于其额外的复杂性而没有提供什么（如果有的话）益处[ 8 ]) ] 。 再一次，学习索引在这里也可能具有优势：模型实际上预测了键(Key)的位置，这可能更接近值记录(Value)的实际位置，而用最小/最大误差会差的更远些。 这就是说，如果我们可以利用这样一个事实，即在位置估计最小误差和最大误差范围内，我们对位置进行了良好估计，那么我们可能能够找到记录（或<=查找键的键）比传统的二进制搜索更快。 因此我们制定了几种搜索策略。

模型二进制搜索：我们的默认搜索策略，和传统的二分搜索策略的唯一区别在于，把第一个中间点设为模型预测的值。

偏见搜索：这种搜索策略修改了我们的模型二分搜索，在每次迭代中不会平均分割从中间点到左侧和右侧的距离。 相反，新中间值取决于最后阶段的模型的输出的标准偏差σ 。 例如，如果确定键(Key)大于中间值 ，则将新中间值设置为 min(middle+σ,(middle+right)/2)。

偏见四元搜索：最后，我们开发了一种新的搜索策略，在任何迭代中都不会选择一个新的中间值来进行二分搜索，而是用了三个新的数据点，即所谓的四元搜索。 研究人员过去尝试四元搜索的主要原因是因为它可以提供更好的预取行为。 也就是说，首先计算三个“中间”点，由使用CPU intrinsics来计算。 之后才会测试不同的“中间”点，并根据结果进行搜索的下一次迭代，非常类似于二分查找。 如果CPU能够从主存储器(Memory)中并行获取多个数据地址，那么这种策略可能更好，但据报道实际上这种策略大部分与二进制搜索相同[ 8 ] 。 然而，再次有一个更好的位置估计可能会有所帮助：也就是说，我们将我们最初的三个四元搜索中点定义为pos - σ ， pos ， pos + σ 。 我们假设，大部分预测都是准确的，首先关注位置估计，然后继续传统的四元搜索。

3.5 索引字符串

我们主要关注索引真正有值记录(Value)的键(Key)，但许多数据库依赖索引字符串，幸运的是，有不少重要的机器学习研究聚焦在字符串建模上。 和以前一样，我们需要设计一个高效但有表现力的字符串模型。 对字符串做好这个设计会带来许多独特的挑战。

第一个设计考虑是如何将字符串转换为模型的特征，通常称为标记化。 为了简单和高效，我们认为n长度的字符串是长度为$$x∈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需要相对较大的模型，因此可以无缝扩展字符串长度增加的场景，及许多更复杂的模型体系结构（例如递归和卷积神经网络）中。

3.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次。

加载时间：虽然本文的重点不在加载或插入时间，但应该注意的是，大多数模型可以训练得相当快。 例如，如果在C ++中实现，那么无需隐藏层的模型可以在几秒钟内在超过200M条记录上进行训练。 但是，对于更复杂的模型，我们选择使用Tensorflow，由于其开销，花费了更长的时间。然而，我们相信我们可以相对较快地对超参数空间进行网格搜索，大约需要分钟数量级跑简单模型。 此外，可以使用诸如[ 52 ]之类的自动调整技术来进一步缩短查找最佳索引配置所需的时间。

3.6.1 整数数据集

图4：地图数据：学习索引与B-Tree

图5： Web日志数据：学习索引与B-Tree

图6：正态分布的对数数据集：学习索引与B-Tree

图[4]，图[5]和图[6]分别显示了两个真实世界整数数据集（地图和博客）和合成数据（对数正态数据）的结果。 作为主要指标，我们将总查找时间分解为模型执行（B树遍历或ML模型）和本地搜索时间（例如，在B树叶子页面中查找键(Key)）。 另外，我们记录了索引结构的大小（不包括排序数组的大小），空间节省和模型误差及其误差方差。 模型误差是最后阶段所有模型的平均标准误差，而误差方差则表明这些标准误差在模型之间有多大变化。 请注意，对于B-Tree而言，由于没有阶段，所以它始终是一个取决于页面大小的固定误差。 加速和大小列中的颜色编码指示索引相对于页面大小为128的高速缓存优化的B树索引的基线有多快或多慢（更大或更小）。

可以看出，在几乎所有配置中，学习索引比B树要快，速度提高了3 倍 ，并且达到了数量级的更小。 当然，B树可以以CPU时间为代价进一步压缩以进行解压缩。 然而，大多数优化不仅是正交的（可以用在神经网络上），而且对于神经网络来说，存在更多的压缩潜力。 例如，神经网络可以通过使用4或8位整数而不是32或64位浮点值来表示模型参数（一种称为量化的过程）进行压缩。 与B树压缩技术相反，这实际上可以进一步加速计算。

有趣的是，四元搜索仅对某些数据集有帮助。 例如，它对weblog和log-normal数据集有一点帮助，但对地图数据集没有帮助。 我们没有报告偏见搜索和B树，或者不同搜索策略的结果差异，因为它们没有为数字数据集提供任何好处。 值得注意的是，模型的准确性也有很大差异。 对于合成数据集和博客数据的来说，误差要高得多，这会影响搜索时间。 作为比较，我们搞了一个学习索引，有更复杂的第一阶段模型（“学习索引复合体”），该索引有2层完全连通的隐藏层和每层16个神经元，可以大幅的减少误差。 然而，在CPU上，模型的复杂性并没有得到回报（例如，模型执行时间太长，无法证明搜索时间较短）。 然而，正如前面提到了GPU / TPU的发展，这种trade-off会被改变，我们推测下一代硬件对更复杂的模型有利。

可以观察到，第二阶段大小（模型数量）对索引大小和查找性能具有显着影响。 这并不奇怪，因为第二阶段决定了需要存储多少个模型。 值得注意的是，我们的第二阶段使用了10,000或更多的模型。 这在第[2.1]节的分析中特别令人印象深刻，因为它表明我们的第一阶段模型可以比B树中的单个节点在精度上有更大的提高。

最后，我们没有提到整数数据集的上跑任何混合模型，因为它们像偏见搜索一样没有提供任何好处。

3.6.2 字符串数据集

图7：字符串数据：学习索引与B-Tree

图8：使用不同搜索策略的学习字符串索引

图[7]显示了不同的搜索策略。 但是，我们确实在表格中看到最佳模型是一个非混合RMI模型索引，使用四元搜索策略，名为“Learned QS”（表格底部）。 所有RMI索引在第二阶段使用10,000个模型，对于混合索引，我们使用两个阈值128和64，作为模型在用B-Tree替换自己之前的最大容许绝对误差。

可以看出，用于字符串的B-Trees学习索引的加速不再那么突出。 这因为一个事实——模型执行相当昂贵，这是GPU / TPU可以解决的问题。 此外，搜索字符串要昂贵得多，因此更高的精确度通常会得到更好的结果。 这就导致了混合索引通过B树取代表现不佳的模型，有助于提高性能。

最后，由于搜索成本的不同，如图[8]所示，对于具有一个或两个隐藏层的2级神经网络模型，不同的搜索策略会产生更大的差异。 请注意，我们没有为B树显示不同的搜索策略，因为它们没有提高性能。 偏见搜索和四元搜索性能更好的原因是他们可以将标准误差考虑在内。

3.7未来的研究挑战

到目前为止，我们的结果集中在只读内存数据库系统的索引结构上。 正如我们已经指出的那样，即使没有任何重大修改，当前的设计已经可以替代数据仓库中使用的索引结构，这些索引结构可能每天只更新一次，或者BigTable [ 18 ] ，其中创建B树批量作为SStable合并过程的一部分。 在本节中，我们将概述如何将学习型索引结构的概念扩展到频繁插入的工作负载场景下。

3.7.1 插入和更新

初看起来，由于学习模型潜在的高成本，插入似乎是学习索引的致命弱点，但是再次，学习索引对于某些工作负载可能具有显着的优势。 一般来说，我们可以区分两种类型的插入：（1）appends 和（2） inserts in the middle，例如在订单表上更新客户id上的二级索引。 现在我们关注后者，并考虑在我们的已排序数据集中引入额外空间的方法，类似于B树通过其每个页面的最小和最大填充因子在已有页面中引入额外空间。 但是，与B树相反，假设我们不会均匀地分散空间，而是依赖于学习的累积密度函数。 最后，假设插页大致遵循与学习的CDF相似的模式; 这并不是一个不合理的假设，就像在顾客id的二级索引的例子中，顾客大致会保持购物行为。在这些假设下，模型可能根本不需要再培训。 这样，对新项目的插入，学习索引可以“概括”成为O(1) 操作，因为它们可以直接放入可用空间中，并且空间可用于最常用位置。 相反，B-树需要O (log n)用于查找和重新平衡树的插入操作（特别是插入某个区域比其他区域更普遍）。 类似的，对于追加插入，如果模型能够学习新数据的关键趋势，模型也可能不需要重新学习。

显然，这一观察结果也提出了几个问题。 首先，模型的普遍性和“最后一英里”表现似乎有一个有趣的折衷; “最后一英里”预测越好，可以说，模型过度拟合的能力越强，而且对新数据项的适应能力也越低。

其次，如果分布发生变化会发生什么？ 它是否可以被检测到，并且是否有可能提供与B树一样的强力保证，它总是能够保证O(log n) 的查找和插入成本？ 虽然回答这个问题已经超出了本文的范围，但我们相信某些模型有可能实现它。 考虑一个简单的线性模型：在这种情况下，插入的项目绝不会将误差增加超过max_abs_error + 1 。 此外，重新训练线性模型的成本为$$O(K_{M + 1})$$ ，其中$$K_{M + 1}$$是模型在数据中覆盖的项目数。如果线性模型不足以实现可接受的误差，我们可以将范围分成两个模型，并在上层的那个阶段重新训练模型。 这个模型可能需要重新训练$$O(K_{M})$$，其中$$K_{M}$$是在重新训练第一个模型之后的最后一个阶段的模型数M等等。因此，基于第一个模型的再训练，容易限制绝对误差。 但是，为了给第一个模型提供一个很好的误差，我们可能需要增加模型的容量，例如通过添加一个多项式或一个额外的隐藏层。 这里有可能通过诸如VC维度的技术再次限制所需的复杂度增加。 研究这些影响，尤其是对于其他类型的模型，包括神经网络，留待未来的人们的工作。

处理插入的另一种更简单的方法是构建一个增量索引[ 49 ]和许多其他系统中，并且还具有如下优点：对于大型再训练操作，可以使用诸如GPU / TPU的专用硬件，这将显着加速，即使需要对整个模型重新训练也是如此。

最后，通过使用先前的解决方案作为起点，可以对每个模型的训练进行热启动。 特别是依赖梯度下降优化的模型可以从这种优化中获益[ 33 ] 。

3.7.2 分页

在本节中，我们假定数据（实际记录或<key，pointer>对）存储在一个连续的块中。 但是，特别是对于存储在磁盘上的数据的索引，将数据分区为存储在磁盘上的不同区域中的较大页面是相当常见的。 为此，我们观察到一个模型学习CDF不再成立，因为$$p = F （ X < Key ） * N$$被违反。 下面我们概述几个可以解决这个问题的方法：

利用RMI结构：RMI结构已经将空间划分为区域。 通过对学习过程的小修改，我们可以最大限度地减少它们覆盖的区域中模型的重叠程度。 此外，可能会复制任何可能被多个模型访问的记录。 这样我们可以简单地将偏移量存储到模型中，也就是数据存储在磁盘上的位置。

另一种选择是以<first_key，disk-position>的形式提供额外的转换表。 通过转换表，索引结构的其余部分保持不变。 但是，这个想法只有在磁盘页面非常大的情况下才会起作用，如果不是千兆字节，则可能在几百兆字节，翻译表格就会太大。 同时，可以使用带有最小和最大错误的预测位置来减少必须从大页面读取的字节数，这样页面大小的影响可以忽略不计。

使用更复杂的模型，实际上可以学习页面的实际指针位置。 特别是如果使用文件系统来确定磁盘上的页面，并且在磁盘上有系统编号的块（例如， block1，...，block100 ），则学习过程可以保持不变。

显然，需要更多的研究来更好地理解基于磁盘的系统的学习索引的影响。与此同时，节省的大量空间以及速度优势，会让这个工作的未来很有趣。