本文是学习总结，有错误处欢迎交流。

背景

index 是查询处理系统中性能影响的关键部分，DBMS 广泛采用 B-tree、trie、hash table，特别是 OLTP 系统的索引的存储开销非常大（一些场景下，一半以上的内存是由索引结构消耗的）。内存在现代数据库上加速效果非常明显，但很多场景下将所有数据放入内存已不可能。AWS 提供 24 TB 的 RAM 实例，每小时消耗 $120；即使 SSDs、NVME 被大量应用，但 IO 操作效率远慢于内存。

作者把索引优化技术按介入的时间分为三个阶段：

development-time：单类型数据结构

设计 state-of-the-art 数据结构满足 CRUD 操作，整体均衡，重点对主要操作做优化。
compact index 技术，减少内存空间，通常比 state-of-the-art index 要慢。例如 succinct index 通过减少数据结构上的 pointer 并在运行时计算 offset，在 lookup、scan、udpate 上性能差一些。

build-time：在一个 index（不同的数据块）上使用多种 encoding 组合，根据数据特征，在写入时选择数据结构。
run-time：build-time 是一种静态组合，单不考虑动态的 workload（工况），run-time 时可以拿到更多的工况信息帮助优化索引结构。

论文提出一个框架：workload-adaptive hybrid index，将 encoding 决策时机延后到 run-time 进行。

思路

"The RUM conjecture" 描述了一个数据结构不能同时做到对读、写、存储空间的最优化。但在实际业务场景下，可以观察到一些 skewed workload（query pattern、key pattern、数据特征）情况，此时 RUM 冲突被弱化了。

现有的一些针对 skewed worklaod 优化的研究，主要的方法是把访问频度数据放在内存上。受限于数据大、内存有限，提出 hot-cold 分类问题，也即 top-k 频繁集挖掘问题，在一个大的数据集合上：

过小的抽样率，导致分类错误率上升。
过大的抽样率，收集、分析采样数据的开销会很大。

论文贡献是提出利用 skewed workload pattern 来设定索引数据结构（tree node layout）的方法：

基于自适应、运行时抽样方法记录访问频率等统计信息。
hybrid index 思路，对于每一块数据，根据细粒度统计信息判定 tree node 为 hot/cold，动态选择合适的 encoding。
目标是在性能牺牲不大的同时有效降低内存开销（结果：相比 state-of-the-art index，减少 82% 空间，保留 90% 性能）。

Adaptive Hybrid Indexs

架构设计

数据库传统的索引在所有叶子节点上编码方式相同，预分配固定的 key/value slot 支持高效读、写操作，缺点就是内存占用大。

比较 lookup、insert 两项操作在压缩和非压缩 B+ 树：

70% 叶子节点时，LZ4 压缩后存储量减少 47%。
不同存储介质间比较，内存有极大性能优势。
以内存为例，压缩数据上操作相比非压缩数据上操作，效率大幅降低。

因此，论文在架构设计的关键点有两个：混合多种索引优势，运行时优化分支选择。

包括两个阶段（两阶段会一直交替、重复）：

Sample：给 index 中不同部分块的访问操作做抽样、聚合统计。
Adaptation：运行一个启发式分类算法做 hot、cold 节点判定，hot 使用性能优化格式，cold 则使用高压缩格式。

接口设计

两个概念：

adaptation manager：框架的控制器。
basic unit：收集统计信息和进行 encoding 转换的基本单元。用唯一标识符（identifiers）表示，例如 B+ tree 使用指针，succinct index 使用位置 offset。

代码接口清晰，这里稍作解读：

为降低采样跟踪的消耗，因此限定在一个子集上，引入一个是否需要被抽样的判断标准（下文即将提到的 skip length、sample size）。
bloomfilter 是对 hashmap 的一次前置操作（优化性能），identifier 必须先在 bloomfilter 中出现，才有可能被加入 hashmap（防止 cold 节点被意外地加入采样跟踪）。
采样可支持 thread_local 进行，进一步降低其并发开销。
通过 C++ 模版可变参数、完美转发，框架可以方便地将上下文信息（例如父子节点）转发给 adaptation manager。

Sample 过程

收集统计信息分两类：

decentralized schema：存储跟踪到的信息到索引结构自身，引入额外存储空间消耗。比如为索引的每一段增加元数据，包括：最近访问时间，读、写次数。
centralized schema：即论文采用的方法，只对被访问到的数据段存储统计信息，将它与轻量级的抽样结合起来，有效降低跟踪带来的开销。

索引在处理 query 时，从上到下遍历内部结构。作者的方法是：基于预设参数（skip length）每隔 N 个（叶子节点）会被记录访问信息；考虑到最近经常的访问模式，系统在做抽样节点信息聚合统计时，把最近访问时间 epoch 也存储下来。

这里有两个重要参数：

skip length（决定抽样频率）：下图的实验数据表明，蓝线（直接抽样）、红线（bloomfilter 过滤后再抽样）两组数据随着 skip length 的降低，附加了更多的计算消耗。取阈值 20 时，性能损失 1.6% 是可接受的。

sample size（决定抽样节点集合的大小）：根据下面等式计算（n 是叶子节点大小，还包括分类错误率、信任度等一些参数，细节可参考原文）。

由于是 run-time 方案，采样在动态调整。adaptation manager 在下一个抽样阶段开始前将调整参数（skip length、sample size）；同时也会参考 workload 稳定度信息，例如频繁发生 encoding 转变时，将减少 skip length 来实现更好的工况跟踪。

Adaptation 过程

基于聚合后的统计信息，所有的抽样节点被分类为 hot（top-k）、cold。根据 epoch 信息可将最近没被采样到的节点判定为 cold。hot 节点的数量也要参考内存上限的阈值。

通过 context-sensitive heuristic functions (CSHF) 做决策，并在必要时执行 encoding 转换。

分类的计算代价集中在优先队列（top-k）和 hashmap 访问、修改统计信息上。

分类算法如下图描述（Compr：压缩存储结构；Optimized：基于内存的性能优化结构）：

除此之外，每个 node 上增加一个字节，保留最近八次分类结果作为历史数据。有些周期性场景可以使用离线模型，通过历史数据和预测值计算 node hot/cold 分类。

实现

文章基于以上方法，给出了在 B+ 树、前缀树上的两种实现。

Hybrid B+ Tree

一个背景：采用 B+ 树的系统在长期运行中，由于经常做 insert/delete，可能产生一些未使用的 slot，使得空间利用率低于 70%。

encoding 类型

Hybrid B+ index 对叶子节点有如下三种编码方式，混合索引将根据场景选择适合的存储类型：

Gapped：传统的，可能有空的 slot，内存有一定浪费。
Packed：只对使用到的 slot 分配内存空间。read、update、delete（墓碑）操作友好，但 insert 效率极低。
Succinct：bit packing 方式存储 key、value，相当于一种压缩，增加了访问延迟。但紧凑的数据排列减少了 CPU cache miss。

encoding 转换

从实验数据上看，涉及到 succinct 的转换都会产升较大开销。

在实现上，由于 insert/delete 可能导致 node 的split/merge，如果一个叶子节点转移到了新的父节点下，该信息必须在跟踪框架中传递，使得 adaptation manager 的上下文信息也做到更新。

Hybrid Trie

trie tree 常用于变长 key、前缀匹配，有两种改进型：

Adaptive Radix Tree（ART）：指针方案，引入四种类型的 node 改进传统 trie tree 缓存命中率低的问题。其每一种类型有不同 lookup 性能，但 node 类型只由 key 决定，不考虑实际 workload。
Fast Succinct Tree（FST）：没有孩子节点指针，通过两个 bitmap 来计算位置。大体上是其中一个维护了已存在的 label，另一个维护 path 是否终止的标记。