✅原文
Learned Index: A Comprehensive Experimental Evaluation
https://doi.org/10.14778/3594512.3594528

简介

目前学习索引的问题：

• 没有在相同的实验框架下进行评估
• 没有与不同的设置进行全面的比较

本文贡献：

• 回顾目前的学习索引
• 讨论学习索引中的关键组件的设计选择
• 提供了一个测试平台供研究人员设计和测试新的学习索引

introduction

一个典型的learned index的架构如下，虚线框表示有的设计中，内部节点不存储有key

key查找

如果预测正确，则可以轻松识别key，否则调用后一步根据预测的大概位置继续搜索关键位置
模型设计方面主要是采用多级机构，中间模型预测叶子节点的位置，叶子节点预测key的具体位置

key插入

插入新的key可能导致索引结构改变或者增加节点（比如节点分裂）
现在的学习索引都有了可变特性

1. 就地插入，并且保持gapped array来推迟索引结构的更改，之后再进行节点分裂统一更改
2. delta缓冲区的插入索引，使用缓冲区允许插入【没太懂】

key删除

和插入类似
【不过很多情况下的索引都采用了删除不会导致节点合并的情况】

并发

为了支持并发操作：

1. 采用不同粒度的缓冲区提高吞吐量
2. 如果要实现节点内部的并发查询，则为每个key维护一个缓冲区
3. 如果要实现不同节点的并发查询，则为每个节点维护一个缓冲区，可以使得在使用该节点的时候
   1. 在节点拆分和合并期间支持并发操作
   2. 在节点拆分和合并期间将缓冲区与新结点合并
4. 批量装载
   1. 自上而下地初始化根，然后将其中的key-v对拆分为子节点然后递归
   2. 自上而下地将kv对拆分为叶子节点，从每个节点中提取最小的或者最大的密钥，然后递归处理【有点不太懂】

本文（作者）的动机和贡献

动机（目前的问题）

1. 现如今地learned index没有在同一个框架下进行评估，作者做了
2. 没有一个指南可以帮助从业者更好的选择特定情况下该使用的leaned index
3. 没有测试平台来设计新的learned index

为了解决以上问题（贡献）

1. 构建了一个评估框架并且比较了当前较为先进的一些learned index
2. 对比了大量的研究结果。以指导从业者在实际场景下选择合适的索引系统
   1. 对于简单的数据分布（cdf较为平滑）和大量读取，一些learned index可以优于传统index；但是对于复杂地数据分布（机器学习模型不好适应）和写入繁重地工作负载，没有优势
   2. 范围查询上，learned index没有显著的优势
   3. 学习索引在字符串key上没有优势
   4. 学习索引在批量加载方面没有优势
   5. 非线性模型地预测精度更高，可以通过学习索引获得更少的查找延迟，但是训练开销更大以及在结构修改期间会减慢写入操作
   6. 可能需要额外的空间来支持并发操作，这会减慢插入和查找操作的速度，因为这会导致搜索涉及索引和缓冲区两部分
   7. 【没看懂】
   8. 学习索引在并发查找/写入方面可能不如传统索引，因为其需要
      1. 搜索索引和增量缓冲区
      2. 在结构修改期间重新训练模型
         但是学习索引在范围查询方面可以和传统索引差不多
   9. 对于非并发场景，DPGM对于只写工作负载有更好的性能；对于没有范围查询的工作负载，LIPP 是更好的选择； ALEX 对于混合插入/查找/范围工作负载具有更好的性能。
3. 构建了一个统一的测试平台，可以帮助研究人员以较低的设计评估和实现开销来设计和测试新的学习索引的结构

学习索引

定义部分就不说了

查找的设计

基础设计

• 大致可以分为线性模型设计和非线性模型设计
  • 线性轻量，应用更广泛
  • 非线性对可以对大型节点有更高的预测准确度【节点里的key或者下层节点更多】，目标是降低索引高度
  • 使用线性的相对更多
  • 非线性又分为多项式拟合模型【从名字就可以看懂，y=kx+b变成了y=ax^n+bx^(n-1)+…+ex+f】和神经网络模型
  • 混合模型，一般可能在每层用处不太一样的情况下用，比如XIndex第一层包含许多下层节点，就适合在第一层用这个
• 线性没那么准但是训练和预测更快
• 非线性可以让内部所包含下层【key或者下层节点】更多，使得树深度更小

位置查找设计

这部分主要在于如何在预测错误的情况下查找

1. 预测一定正确【这么牛？例子是LIPP】
2. 内部节点预测正确，在叶子节点内搜索【ALEX，上次讲了，不细说】

支持范围查询和重复的key【看起来是可选功能】

插入设计

主要分为两种插入策略

1. delta缓冲区，插入到delta缓冲区中并且定期合并到索引结构中
   • 缓冲粒度分为索引级，节点级和kv对级【分别有不同的learned index方法实施】
   • 对级别更为细粒度，所以并发更高但是存储开销更大【空间换时间】
2. 就地插入，但是一般这里使用gapped array【alex】
   • 以ALEX为主
   • LIPP【就是刚才那个一定可以预测正确的】会在目标位置创建一个新节点，指向节点的指针替换掉目标位置的【感觉像是：→old，改成→new→old这种？】

结构修改

如果节点无法容纳则跟新索引结构比如节点分裂，主要有四种

1. 节点或者缓冲区中得到kv对超过阈值（大多数都用）
2. 模型预测的误差过大
   • XIndex
3. 基于成本考虑【感觉其实也是考虑误差，但是加了些成本函数啥的】
   • ALEX
4. 基于冲突的的方法映射到同一个位置的数量过大
   • LIPP也考虑这个

删除设计

有的设计了如果节点内部kv对含量太少会合并节点（XIndex），其他的好像没

并发设计

插入或者删除kv对的时候会锁定对应的对象以实现并发

1. 节点内并发
2. 节点间并发

为了支持并发操作：

1. 采用不同粒度的缓冲区提高吞吐量
2. 如果要实现节点内部的并发查询，则为每个key维护一个缓冲区
3. 如果要实现不同节点的并发查询，则为每个节点维护一个缓冲区，可以使得在使用该节点的时候
   1. 在节点拆分和合并期间支持并发操作
   2. 在节点拆分和合并期间将缓冲区与新结点合并
4. 批量装载
   1. 自上而下地初始化根，然后将其中的key-v对拆分为子节点然后递归
   2. 自下而上地将kv对拆分为叶子节点，从每个节点中提取最小的或者最大的密钥，然后递归处理【有点不太懂】

批量加载

批量加载的目的是为一批kv对建构学习索引

1. 自上而下的批量加载。首先将所有对作为根节点。然后决定是否拆分这些对以生成多个子节点。如果决定不分裂，则该节点将成为叶节点，并训练一个模型来预测该叶节点中的键到位置映射；否则，它会在此内部节点中训练key到子节点的模型，并根据模型预测将kv拆分为多个子节点。接下来递归地处理子节点。
2. 自底到顶的批量加载。首先将这些对分成不同的叶节点，并训练模型来预测每个叶节点中每个键的位置。然后，提取每个叶节点中的最小或最大键，并使用这些选定的键生成对的子集。接下来，它决定是否进一步分割这些选定对的子集。如果决定不分裂，用这些对构造一个根节点，并为该节点训练一个键到子节点的模型，该模型预测键所属的子节点；否则，将这些对分割到不同的节点。

• 两种方法的比较：自下而上的方法在内部节点中存在预测误差但是自上而下没有；但是自上而下分割的方式采用的是单一模型，

分割结点的方式：

1. 贪婪分割
2. Even分割
3. 基于成本的分割
4. 基于冲突的分割

其他方法：
RMI使用非树（两层）的方式进行批量加载。首先将所有对作为根，叶子节点的数量是一个超参数。然后，RMI 使用模型预测将根拆分为叶节点。接下来，它通过随机梯度下降为每个叶节点训练一个模型，预测叶节点中每个键的位置。

工作负载生成

工作负载生成器为静态动态和并发场景生成不同的工作负载

超参数调整器

为每个learned index探索更为合适的参数设置，来让评估更为公平

作者还提供了一些API来供选用

负载生成

• 静态：查找和范围操作
• 动态：查找和范围和插入操作
• 并发场景：并行查找、范围和插入操作

静态

静态测试中，空key率被设置为50%

动态

动态存在插入，其中又分为

1. 均匀，插入的kv对是从数据集中均匀采样的
2. 增量，一开始批量载入较少的数据，然后大批插入新的kv对
3. 热点（hotpot）模式，从数据集的一小部分中随机均匀抽取key进行插入，定义：hotpot比率=样本范围/总key量，所以此参数越小说明插入越倾斜

并发

并发设计并发插入和查找，设计类似于动态

实验

实验设置

• 在具有128GB RAM和两个10核Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz的Linux服务器上进行所有实验。
  在具有不同累积分布函数（CDF）曲线的五个真实数据集上测试学习索引
• Amazon：亚马图书ID及其销量热度的集合，200M，不重复，int key
• Face：Facebook用户ID集合，200M，不重复，int key
• Wiki：维基百科ID及其编辑时间戳，2亿，21026个重复，int key
• Osmc：OpenStreetMap的小区ID集合，200M不重复int key
• Url：来自Memetracker的URL集合，90M不重复，string key，仅用于评估可以使用字符串key的系统
• 下图里考虑了learned index的谱系：【不在里面的就是传统index流派了】

实验进程

作者设置了超参数协调器，这个系统会通过根据内容给所有参与测试的learned index方法设置最好的参数，以保证评估公平。【具体是如果自带调优工具就用调优工具，否则通过网格搜索的方法列举（暴力）】

静态场景评估

对于点查询的性能，对于每个数据集，先考虑使用200M个key来初始化索引，然后查找20M个key，通过结果来评估效果。
P50和P99延迟值如图【P50值意味着50%的key查找所消耗的时间低于此值，P99同理】：

虚线和实线将图表分为(i)没有位置搜索的学习索引;(ii)只搜索叶节点的学习索引;(iii)同时搜索内部节点和叶节点的学习索引;(iv)传统指标(从左至右列出)。

这一部分的结论：

首先，对于每个数据集，至少有一个学习索引优于传统索引;但是没有学习索引在所有数据集上都优于传统索引。在face /Osmc/ amazon数据集上，LIPP表现最好，因为它不进行位置搜索;而在Wiki数据集上，ALEX表现最好，因为ALEX只在叶节点上进行位置搜索(LIPP不支持Wiki数据中的重复键)。其次，P99延迟接近P50延迟，这表明大多数键的查找具有相似的延迟。

数据拟合模型

有两个观察结果。
评估了位置搜索延迟和预测误差。
首先，在大多数情况下，学习索引的预测误差小于b +树的搜索距离，这验证了数据拟合模型可以通过适当拟合键到位置映射来减小搜索距离。其次，在模型设计方面，我们发现在face数据集上，使用非线性/混合模型的索引(XIndex除外)比使用线性模型的索引具有更小的预测误差，使用学习索引可以减少位置搜索并获得更低的查找延迟。

延时【紫色是搜索延迟占查找延迟的比率】：【黑线指的是B+树所需要的延时】

结论：

对于仅查找场景，学习索引LIPP和ALEX在四个数据集上表现最好。在位置搜索方面，不搜索的学习索引和只搜索叶节点的学习索引性能更好。在模型设计上，非线性模型在简单数据集(如相对平滑的CDP，没有突变)上的预测误差比线性模型更低，从而获得更好的查找性能。

范围查询

1. 不可变索引通常比可变索引性能更好，因为不可变索引将键位对的原始列表存储在索引之外，并且可以直接扫描对列表以进行范围查询；相反，可变索引将原始数据分割到不同的索引节点，这限制了扫描吞吐量。
2. 在可变索引中，传统索引B+树和学习索引ALEX、MAB+树在两个数据集上的表现最好。因为它们都链接了一个叶节点间的有序列表。
3. LIPP具有最差的范围查询吞吐量。虽然LIPP的查找性能最好，但LIPP对在内部节点和叶节点中都是分散的，并且LIPP之间没有链表。

作者的结论：

仅对于范围查询，学习索引的性能并不优于传统索引。维护键位置对排序列表的索引可以有效地处理范围查询，而其他索引则不能，因为它们不能顺序地获得键位置对。

动态场景评估：

（动态即有插入的）

上图是延迟
结果发现：
大多数索引具有相似的P99插入延迟，这反映了它们具有相似的结构修改开销

不同的插入类型的效果：

uniform：均匀；delta：增量；hotspot：热点
在热点类插入中，传统索引ART在Osmc上表现最好。
有两个原因：

1. Osmc数据具有更复杂的CDF，这降低了学习索引的插入吞吐量。
2. 由于许多对插入到一个小区域，学习索引在插入期间触发更多的结构修改，这进一步降低了插入吞吐量。

性能和索引大小之间的权衡：

图中是不同的索引权衡

结论：

对于uniform插入模式，学习索引获得了较高的插入吞吐量;而对于hotspot模式或delta插入，学习索引没有传统索引的优势。就插入策略而言，使用就地插入的学习索引具有更高的查找性能，而使用增量缓冲区插入的索引可以获得最高的插入性能。对于结构修改，大多数索引(DPGM除外)都有类似的开销；索引通常使用额外的结构来减少插入/查找延迟，因此涉及较大的索引大小。

混合查找/范围/插入计算

对于只读{0%写)和读重工作负载{5%写)，ALEX在所有数据集上都表现最好。有两个原因。

1. ALEX只在叶节点上搜索，减少了插入和查找的位置搜索开销。
2. ALEX以排序的顺序链接叶节点，以方便范围查询。

结论：

学习索引对于繁重的读工作负载是有效的，但是传统索引在繁重的写工作负载中更好地平衡查找/范围/插入的吞吐量。此外，retiring(指令计数)、不良预测(分支指令错误预测)、前端绑定(指令获取/编码)、DRAM绑定(缓存丢失)等微架构指标【感觉像是cpu那边的东西，比较内核？】可以指示学习索引的读/写性能(例如，通过仅在叶节点上搜索来减少分支指令错误预测)。

并发：

评估了四种支持并发的索引：【 XIndex FINEdex Wormhole ART 后面两个是传统的】
作者还是选择了0 5 50 100 insert进行测试
作者发现并不是所有的情况下learned index都比传统index要好，作者认为主要有以下原因：

1. 学习索引采用数据缓冲区插入，这可能会减慢查找速度，因为搜索同时涉及索引和缓冲区。
2. 对于插入期间的结构修改，学习到的索引重新训练模型，这会降低插入吞吐量。此外，结构修改应该锁定涉及的节点，并且会发生更多的线程冲突。
3. 学习索引FINEdex没有采用先进的锁机制，这会对其插入/查找吞吐量产生负面影响。

在范围查询阶段：

传统索引Wormhole在Osmc数据集上表现最好，而xindex和传统索引ART在Face数据集上表现最好

倾斜插入：

不如传统，原因之前也说了：插入的键在一个很小的范围内(几个缓冲区)，并且会导致频繁的线程冲突。其次，倾斜插入的数据会迅速占用缓冲区，并触发频繁的结构修改。

批量载入：

1. 学习索引在批量加载时间上并不优于传统索引，毕竟需要进行训练啥的
2. 使用贪婪分割的学习索引的批量加载时间比其他索引短，这是因为贪婪分割具有最小的时间复杂度，比如alex没有用贪婪就需要更长时间
3. 回想一下之前查找实验的的那个结果，不使用贪婪分割的学习索引比其他索引具有更高的查找吞吐量

结论：

在批量加载时间方面，学习索引的性能并不优于传统索引。在学习索引中，使用贪婪分割方法的索引可以获得更快的批量加载，但代价是查找性能较差。
因为贪婪分割是比较简单的。相反，如果考虑节点的成本和对冲突，则可以构建更有效的索引结构。

字符串做key：

直接上结论：
学习索引在字符串键上的性能不能超过传统索引，因为字符串键的长度很长，分布难以预测。

实验结论

一些对于要点的总结

• 累积概率分布函数更复杂（应该是更屈折不够平滑）的情况下，学习索引吞吐量会被降低
• 对于热点插入类，学习索引会触发更多的结构修改，会降低插入的吞吐量
• 对于插入较为平均的，学习索引的插入吞吐量会更高；但是对于插入不平均的（倾斜插入），没有传统索引好【这些都是只插入的吞吐量方面】
• 使用就地插入的学习索引可以获得更高的查找性能
• 学习索引对于繁重的读工作负载是有效的，但是传统索引在繁重的写工作负载中更好地平衡查找/范围/插入的吞吐量
• 对于并发查找/写入，学习索引的性能不能超过传统索引，因为学习索引需要
  • (i)同时搜索索引和增量缓冲区
  • (ii)在结构修改期间重新训练模型。
• 对于范围查询，学习索引和传统索引实现了相似的并发性能

关于如何选择learned index

作者给出了一个选择指导图

并且作者认为：在CDF增长较为平滑的数据集中，learned index可以替代传统的index系统，但是对于复杂的数据集、倾斜度较高的插入模式和具有许多范围查询和大量写入以及并发操作或者字符串key的工作负载，learned index与传统的index系统没什么优势。
【也就是说适用范围比较有限】
【图里可以看到很多情况下都是适合trad（传统index系统】，