Page 360 - 《软件学报》2025年第8期

郭娜 等: DRAMA: 更新分布感知的学习型索引 3783

此外, DRAMA 的内存占用并不随插入比例的增加而持续增加, 这个结果主要归功于 DRAMA 使用缓冲区处
理更新. 当没有查询操作时, 节点缓冲区越大, 其处理插入的性能就越好. 然而, 在个别工作负载下, DRAMA 的索
引大小会略高于其他索引结构, 尤其是与 PGM 相比较. 一方面是因为 PGM 参数压缩策略是有损的; 另外一方面
是因为 PGM 使用贪心策略构建索引, 只要在误差阈值内就无须创建新的段. 这种贪心构建方式可以减少段的数
量, 但由于每段的范围不固定, 同样会导致查询过程中的多次修正. 这也是为什么 PGM 的查询性能低于 DRAMA、
ALEX 和 LIPP. 在个别工作负载下, DRAMA 的索引大小高于 ALEX , 这是由于虽然二者都采用启发式构建策略,
但开销模型的设计不同会导致选择不同的扇出值, 进而导致不同的索引结构和索引大小.

4.3.4 压缩策略分析
用户可根据实际需求有选择地使用压缩策略, 通过调节有损压缩系数 ε 选择不同程度的有损压缩效果. 为了
对比分析 HPC 中 LLPC 和 LPC 对内存占用和查询性能的影响, 本节采用消融实验的形式进行评估, 对比项包括:
(1) 无任何压缩策略 (DRAMA); (2) 在 (1) 的基础上对内部节点使用 LLPC 策略 (DRAMA+LLPC); (3) 在 (2) 的基
础上对叶子节点使用压缩系数为 0.5 的 LPC 策略 (DRAMA+LLPC+LPC ε=0.5 ); (4) 在 (2) 的基础上对叶子节点使用
压缩系数为 1.0 的 LPC 策略 (DRAMA+LLPC+LPC ε=1.0 ). 图 8 显示了在不同数据集下, 内存占用与查询吞吐量随
插入比变化的动态对比关系. 结果表明, DRAMA+LLPC 可以在不影响查询性能的情况下 (最低只损失了 0.46%,
最高损失了 5.68%), 轻量级地减少模型参数的内存占用. 如图 8(a) 所示, DRAMA+LLPC 的内存占用在 0 和 1 的
插入比例下分别压缩了 20.75% 与 24.45%, 同时吞吐量只比 DRAMA 降低了 1.77% 与 3.21%. 这是因为 Osmc 数
据集的数据分布更倾斜, 需要更多内部节点进行划分, 此时 DRAMA 内部节点占节点总数的比例较高, 所以
LLPC 压缩的目标节点更多, 可压缩空间更大. 因为 DRAMA+LLPC 只针对内部节点进行无损压缩, 不会破坏内部
节点模型精准预测的特性, 因此并不影响查询性能. 综上所述, LLPC 在非均匀数据集上, 以及在零 bulkload 或全
bulkload 的负载环境下效果最佳.

DRAMA DRAMA+LLPC DRAMA+LLPC+LPCε=0.5 DRAMA+LLPC+LPCε=1.0 内存占用
DRAMA DRAMA+LLPC DRAMA+LLPC+LPCε=0.5 DRAMA+LLPC+LPCε=1.0 吞吐量
6 30 10 40 0.03 35 0.03 30 3 60
5 24 8 30 30
索引大小 (MB) 4 3 2 18 12 6 20 0.02 20 10 0.02 20 10 2 1 40 20 吞吐量 (10 6 ops/s)
0.01
0 1 6 0 4 2 10 0 0 0 0.01 0 0 0
0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0
插入比例 插入比例 插入比例 插入比例 插入比例
(a) Osmc 数据集 (b) Lat 数据集 (c) Uniform 数据集 (d) Amzn 数据集 (e) Wiki 数据集
图 8 压缩策略消融实验

图 8 中, 与 DRAMA+LLPC 相比, DRAMA+LLPC+LPC ε=0. 和 5 DRAMA+LLPC+LPC ε=1. 可以显著降低模型参
0
数的内存占用, 但同时查询性能的损失也会随之升高. 如图 8(c) 所示, 在 Uniform 数据集上, 当 workload 的插入比
是 1.0 时, DRAMA+LLPC+LPC ε=0. 在 5 DRAMA+LLPC 的基础上进一步压缩了 38.70% 的内存占用, 同时也多损失
了 14.16% 的查询性能. 这是因为叶子节点占节点总数的比例更大, 在叶子节点使用 LPC 会导致叶子节点模型更
大的预测误差, 查询时延相应地有所升高. 与 DRAMA+LLPC+LPC ε=0. 相比, 当 DRAMA+LLPC+LPC ε=1. 时, 在
5
0
Uniform 数据集上进一步压缩了 10.89% 的内存占用, 同时也多损失了 17.07% 的查询性能. 这是因为当 ε=0.5 时,
只合并斜率的区间重叠度更高的叶子节点, 即参数的选择更接近最小二乘法拟合的结果, 模型预测误差更低. 当
ε=1.0 时, 只要叶子节点的斜率区间重叠就执行合并, 偏离最小二乘法拟合结果的叶子节点更多, 导致整个索引的
模型预测误差更大. 但因为合并了更多的叶子节点, 实现了更低的内存占用.
结合表 3 的数据可以分析出, DRAMA 的结构本身就很紧凑, 如果叠加有损压缩策略, 压缩效果会更好.

4.3.5 查询时延比较
图 9(a)–(j) 展示了处理不同工作负载以及不同查询分布的查找时延. 根据图 9(a)–(e) 可以观察到, DRAMA 的
平均查询时间比其他索引结构更稳定, 且对数据插入频率不敏感. 例如, 在 Uniform 数据集下, DRAMA 的 Zipf
(α=0) 查询时延分别比 ALEX、LIPP、PGM 和 B+Tree 最高减少了 21.87%、28.05%、94.83% 和 89.52%.
DRAMA 的 Zipf (α=40) 查询时延分别比 ALEX、LIPP、PGM 和 B+Tree 最高减少了 21.88%、25.92%、93.71%