Page 21 - 《软件学报》2026年第2期

500 软件学报 2026 年第 37 卷第 2 期

[5]
总数限制. Tsunami 在学习型网格的基础上对查询负载分布和数据中的二维相关情形做了优化, 由于作者未公开
其用于调优的模型, 无法使用该方法调优索引, 我们按照其论文中说明的另一种迭代方法调优参数, 考虑论文提及
调优模型的训练需在大量不同的数据集反复构建索引, 两种调优方法增加的索引离线构建用时是可比的.
(2) 实验 2: 泛化性能与动态场景. 学习型索引大多使用了查询负载优化索引性能, 因此应评价无查询负载训
练集和查询负载偏移场景的泛化能力. 对于查询负载偏移场景, 索引在每个数据表的 Uniform 查询负载上离线构
建索引, 在线查询 Skew 负载. 此外, 相比其他多维索引方法, LA-tree 以高效的索引自适应增量更新方法拓展了其
更新支持能力, 故我们额外增加 LA-tree 索引更新性能纵向评估, 以朴素的定期重新构建 LA-tree 索引作为基准更
新方法与 LA-tree 索引自适应增量更新方法作纵向比较.
● 读写混合负载. 为增强更新对原索引的影响, 提高实验挑战性, 该负载包含普通查询和新数据插入指令. 其
中包含的普通查询为 TPC-H Lineitem 数据集的 Skew 查询负载, 而考虑到 TPC-H Lineitem 数据集的相关性弱, 我
们新增的 3M 行数据用属性各维度单独排序的方式增强数据相关性. 实验 2 在 TPC-H Lineitem 数据集及对应的
Uniform 查询负载训练集上离线构建 LA-tree 索引, 然后在线运行我们设计的读写混合负载. 基准更新方法将整个
负载分为 10 个区间, 在区间间隔处重新构建 LA-tree 索引而在每个区间中将新增数据保存至缓冲区, 与之前构建
好的索引一起处理查询结果. LA-tree 索引自适应增量更新则将每条新增数据通过中间节点 LM 和叶子节点 PLM
自顶向下地插入到 LA-tree 的正确位置, 再对 LA-tree 做自适应重构.
● 评测环境. 所有的基准方法及 LA-tree 都用 C++ 11 实现. 为公平比较, 各方法的入口函数、计时框架、回归
模型 (如 LM) 等部分代码都尽量一致. 评测环境: 系统 Ubuntu 20.04.6 LTS; 处理器 Dual CPU System: 2×Intel(R)
Xeon(R) Gold 6230 CPU@2.10 GHz (20C40T); 运行内存 1 TB DDR4 ECC; 外存磁盘 4×8 TB HDD (RAID5).
6.3 实验 1: 静态场景索引查询性能评测
我们首先按照在线查询平均用时对索引查询性能做总体比较, 然后通过平均访问单元数量和扫描比两个指标
分析造成索引性能瓶颈的问题所在, 最后比较索引的离线构建用时和索引大小. 其中, LA-tree 使用第 3 节提出的
临近搜索法, 在数据与查询负载 1% 采样率的小样本上确定了超参数 h 和 b. 具体地, 在 Stock 数据集上 h = 8, b = 3;
在 TPC-H Lineitem 数据集上 h = 7, b = 10; 在 DSB Sales 数据集上 h = 9, b = 5.
如表 2 所示, 最优结果用加粗表示. 传统索引整体性能有限, 其中, Clustered 作为单维索引, 整体性能最差. 但
其在 Stock 数据集上表现相对较好, 这是因为 Stock 中“股价”维度的取值重复较少, 使谓词筛选效果较佳, 从而提
升了单维索引性能. KD-tree 与 Octree 作为典型的多维索引, 整体明显优于单维索引. 但二者均缺乏查询感知, 并
在筛选时依赖大量数值比较, 其查询用时仍比学习型索引多 1–2 倍. 相对而言, 多维划分的 KD-tree 性能优于三维
划分的 Octree, 原因在于前者更简洁的节点功能带来的较低算法开销.

表 2 索引在线查询平均每条查询用时比较

Clustered KD-tree Octree Qd-tree Tsunami LA-tree 比SOTA提升 比学习型提升
数据集 查询负载
(ms) (ms) (ms) (ms) (ms) (ms) (%) (%)
Uniform 41 456 468 43 56 31 24 28
Stock
Skew 30 419 338 32 79 26 13 19
TPC-H Uniform 178 23 30 19 31 12 37 37
Lineitem Skew 182 24 29 17 19 12 29 29
Uniform 483 313 442 148 1 109 71 52 52
DSB Sales Skew 429 314 445 134 1 559 74 45 45
HD 901 128 251 256 1 017 84 34 67
平均情况 320.6 240.0 286.1 92.7 552.9 44.3 52 52

相比之下, 学习型索引在大多数场景下更具优势. Qd-tree 在部分查询负载下平均查询用时较短, 但在 DSB
Sales 数据集的高维场景中性能显著下降, 原因在于其非均匀数据划分在高维下劣势凸显. Tsunami 的查询用时整
体偏高, 并在 DSB Sales 上性能退化更为严重. 这些结果表明, 基于网格结构的学习型索引在拟合高维数据分布时
存在局限.
综合来看, LA-tree 在所有测试中均取得最佳结果, 总体性能相比其余现有最优方法提升约 52%. 其优势来自