9 月 29 日，咱们邀请到开务数据库研发工程师邹彤老师与大家一起研读大咖论文，主题为 《学习型索引在数据库中的利用实际》。
索引是数据库引擎的重要组成部分，在当下数据井喷式暴发的阶段，如何高效精确地在海量数据中疾速检索某条或某个特定范畴的数据就显得尤为要害。
通用的数据库系统为不同的利用需要与数据类型提供了对立的解决形式，在获得了巨大成功的同时，也暴露出肯定的局限性：因为没有联合具体利用的数据分布与工作负载，零碎往往难以保障性能的最优。
为了解决这一问题，“学习式数据库系统”成为了目前数据库畛域的钻研热点，它利用机器学习技术无效捕捉负载与数据的个性，从而对数据库系统进行优化。
学习式数据库系统当中，呈现了一个对数据库索引构造产生颠覆性影响的畛域—学习型索引构造 Learned Index。
论文重点回顾
01
2018 年 Jeff Dean 等人在 SIGMOD 发表了 《The Case for Learned Index Structures》，成为 Learned Index 的开山之作。近年来，SIGMOD 每年都有肯定数目的论文聚焦此畛域，论证学习型索引在各种存储构造中的合理性和可行性，也逐步拓宽了学习型索引的实用场景，反对增删改操作、多维索引、数据歪斜负载等。
索引是实现数据高效拜访的重要途径，有助于疾速失去键的相干信息，如地址、存在与否等。学习型索引应用机器学习中的回归模型建设起键值与数据之间的对应关系，或建设分类模型判断键值是否存在，从而利用数据分布或特色对索引构造进行优化，使索引变得专用。
在《The Case for Learned Index Structures》论文中，咱们解读了机器学习模型如何与传统的 B 树、布隆过滤器等构造联合，优化索引构造。该文章的根本观点：索引就是模型。
Range Index（以 B-Tree 为代表）能够看做是从给定 key 到一个排序数组 position 的预测过程；Point Index（以 Hash 为代表）能够看做是从给定 key 到一个未排序数组的 position 的预测过程；Existence Index（Bloom Filter）能够看做是预测一个给定 key 是否存在。因而，索引零碎是能够用机器学习模型去替换的。
索引个别是通用构造，对数据分布不做任何假如，也没有利用利用负载中实在数据的模式。形容数据分布的连续函数，能够用来构建更无效的数据结构或算法（机器学习模型）。假如用于 Range Index 的 key 的范畴是 1-100M，那么能够用非凡的函数或者模型（间接把 key 自身当成是 offset）做索引而不用再用 B-Tree。
以 B-Tree 为例，它能够被看做 Regression Tree。B-Tree 的建设过程也是依赖数据的，只不过它不是通过梯度降落失去，而是依赖事后定义的法令。查问时给定一个 key，B-Tree 会索引到蕴含该 key 的对应范畴的叶子节点，在叶子节点内对 key 进行搜寻。
如果该 key 在索引中存在，就会失去其对应的 position（position 为指向逻辑页的一个 pointer）。出于效率思考，个别在一个逻辑页内的 records 会用首 key 来 index。如图，输出一个 key，输入是对应要查问 record 的 position 的区间 [pos, pos + pagesize]。
仿照 B-Tree 建设模型，输出是键值和数据地位形成的元组 (key, pos)，模型将预测键值的地位 pospred，输入为 [pos – min_err, pos + max_err]，其中 min_err 和 max_err 别离为每一组 pos 和 pospred 的正负差中的最小负差和最大正差。如果 key 存在，就能够在 [pos – min_err, pos + max_err] 内通过二分搜寻查找到。而此处所用的模型为数据的累积散布函数（Cumulative Distribution Function，简称 CDF）。
为了管制误差，解决 Last Mile Accuracy 问题，建设 RMI（Recursive-Model Indexes）。RMI 次要利用了分段函数的思维，举个例子：要通过繁多模型预测 100M 个 key 的地位产生的最小和最大误差是很大的。但如果采纳两层模型，第一层模型将 100M 个 key 映射到 10k 个地位上，第二层将 10k 个 key 映射到 1 个地位上，则最小和最大误差会升高很多。
RMI 的根本构造是树，个别 2~3 层。根结点和两头结点的模型起疏导作用，始终疏导输出 k 到叶结点。叶结点模型依据其输出得出地址。RMI 的层数的递增示意数据范畴的放大，直至叶结点能够拟合最小范畴的数据分布。
B-Tree 的复杂度为 O (log N)；如果思考数据分布，ML 会得出相似于 Pos=20 * key (id) 的线性模型，复杂度间接变成了 O (1)。同时在测试集上证实了 Learned Index 比 B-Tree 查找更快，索引 Size 更小。
然而目前仍然存在 3 点局限性：
（1）仅反对只读场景；
（2）线性模型不实用更简单的数据分布；
（3）不反对多维索引。
这些问题将在后续系列论文中提出解决方案。
02
首篇 Learned Index 只反对只读的 Workload，给事实环境中部署 Learned Index 带来挑战。《ALEX: An Updatable Adaptive Learned Index》 解决了这个难题。ALEX 是一种可更新的内存性索引，它联合 Learned Index 的要害洞察以及曾经证实的存储与索引技术，在动静的 Workload 上实现了高性能和低存储空间占用。接下来咱们将依照下图逐个解说常识要点：
数据节点布局— 数据节点存储以下内容：
（1）线性回归模型；
（2）存储 key 和 payload 的 Gapped Array；
（3）Bitmap。
外部节点布局— 外部节点存储以下内容：
（1）线性回归模型；
（2）蕴含子节点指针的指针数组。
相比于 Learned Index，ALEX 的外部节点可能更灵便的划分 key 空间。依照散布将线性空间调配给数据节点，非线性空间调配给外部节点。
查找算法： 从根节点开始，应用模型向下遍历树，直到达到数据节点。在数据节点利用模型，并联合指数搜寻，找到理论地位。
插入到未满节点：ALEX 采纳一种 model-based 插入方式，通过模型预测新元素的插入地位，确保模型的准确性。
插入到已满节点：
（1）节点扩大机制：将蕴含 n 个 key 的数据节点扩大为长度为更长的 Gapped Array，对模型进行缩放或重训练，再利用该模型进行 model-base 插入；
（2）节点决裂机制：节点决裂会将数据节点划分为两个，均匀划分 key space，并为每个新节点调配指针。有两种决裂办法：程度决裂和垂直决裂。
Cost model： 当插入到一个已满节点中时，ALEX 利用 2 类 cost model 决定插入机制：
（1）节点内 cost model；
（2）遍历到叶子结点的 cost model。
插入算法— 联合 cost model 和插入机制，插入算法如下：
（1）一个节点在初始创立时，依据简略假如，利用节点内 cost model，计算 expected cost；
（2）结合实际统计信息，利用节点 cost model，计算 empirical cost；
（3）根据上述 cost 抉择插入机制。
劣势与挑战：
（1）劣势：相比于之前的 Learned Index 和 B-Tree，查找时间更快，模型更小；反对更新。
（2）挑战：多并发；多数据类型；离群值影响；参数调优等。
03
以上均以 B-Tree 为主论述了 Learned Index 的实现，RadixSpline 的呈现使得 Learned Index 在 LSM Tree 存储构造中成为可能。接下来让咱们一起回顾 《RadixSpline: A Single-pass Learned Index》。
RS 索引的组成：Spline points 样条点和 Radix table。样条点是 key 的子集，通过抉择后能够对任何查找键进行样条插值，从而在预设的误差范畴内得出预测的查找地位。Radix table 有助于为给定的查找 key 疾速定位正确的样条点。
在查找时，Radix table 用于确定要查看的样条点的范畴。搜寻这些样条点，直到找到围绕 key 的两个样条点。而后，应用线性插值来预测查找 key 在根底数据中的地位（索引）。因为样条插值是误差有界的，所以只须要搜寻（小）范畴的数据。
构建 Spline：构建模型 S (ki) = pi ± e，一种映射关系。
构建 Radix table：相似基树 /trie，一个 uint32_t 数组，它将固定长度的 key 前缀（“radix bits”）映射到带有该前缀的第一个样条点。key 的前缀是基表中的偏移量，而样条点被示意为存储在基表中的 uint32_t 值（图中指针）。
首先调配一个长度为的数组，而后遍历所有样条点，每当遇到一个新的 r 位前缀 b，就将样条点的偏移量（uint32_t 值）插入基表中偏移量 b 处的槽中。因为样条点是有序的，基数表是从左到右间断填充的。
Single Pass：构建 CDF、Spline 和基表都能够在运行中进行，只需一次遍历已排序的数据点。当遇到新的 CDF 点时（即 key 扭转时），将该点传递给 Spline 结构算法。在同一过程中填充事后调配的基表也很简略：每当在选定的 Spline 点遇到新的 r 位前缀时，就在表中新增一条记录。
查找过程：首先提取查找 key 的 r 位前缀 b（例中为 101）。而后，应用提取的位 b 对基表进行偏移拜访，检索存储在地位 b 和 b +1（图中 5 和 6）的两个指针。这些指针在样条点上放大了搜寻范畴。用二分搜寻查找键四周的两个样条点，在这两个点之间进行线性插值，取得 key 的预计地位 p。最初，在误差范畴内进行一次二分搜寻法运算，以找到第一个呈现的键。
三篇论文总结
本次 Paper Reading 的系列文章论证了学习型索引在不同索引构造中的合理性和可行性，利用工作负载的数据分布，对数据键值进行拟合，构建键值和地位的映射关系。
在 ALEX 中，学习型索引在反对写入操作的同时，查问更快，索引占用空间更小。RadixSpline 做到了在 LSM Tree 存储构造中一次性构建索引，大大缩短了索引构建工夫。然而，这些办法仍存在机器学习模型的 3 大通病：
（1）因为预计存在误差，很难保障语义正确性。数据库的索引通常须要满足严格的限度条件，例如 Bloom Filter 的劣势之一就是不会把存在的判断为不存在（False Negative），但学习型索引就无奈齐全保障这一点；
（2）普适性问题。如果新数据呈现了数据偏移，将不再合乎原来的模型；另一种状况是，数据遵从其余的分布模式，或者数据无奈通过散布形容，则很难对其构建模型；
（3）Inference 代价问题。模型实现后，新数据的加载模型 Inference 的代价个别要比显式的索引数据结构的计算低廉。
综上所述，如果要利用工作负载的数据分布，则须要在线模仿一个工作负载样本，并在样本数据上做增量拟合或训练；在学习型索引构建方面，能够聚焦 LSM Tree 的某个阶段，例如 Compaction 阶段；另外，最新的论文《From Wisckey to Bourbon：A Learned Index for Log-Structured Merge Trees》中提到了如何在 LevelDB 中构建索引，并且减速 SSTable 的查找。将来，咱们也将持续关注并摸索在开务数据库中更多的利用可能。