1. 摘要（Abstract）

VEGA提出了一种全新的只读型（immutable）学习索引，旨在同时实现最先进的经验查询性能和严格的理论查询复杂度保证。现有最快的不变学习索引（如RMI）虽在实际查询吞吐量上表现突出，但缺乏非平凡的最坏情况查询界限；相反，提供紧致界限的索引（如PGM）虽理论上可靠，却在平均查询性能上显著落后。这种理论与实践的脱节成为学习索引领域长期悬而未决的核心问题。VEGA通过引入两大在线模型构建策略彻底解决了这一难题：一是采用合适的粒度（group-wise learning granularity）简化数据分布，即将多个连续键打包成组，仅用组内首键进行模型训练，从而大幅减少所需模型数量；二是主动调优分布（active distribution tuning），通过键重定位（key repositioning）将简化后的分布调整为更易拟合的形式，使单层模型数量进一步降低至1。

系统进一步提出一个通用框架，在给定内存预算下动态组合F1（Fitting model to simplified distribution）和F2（Fitting tuned distribution to model）两种策略，实现查询性能的最优权衡。VEGA采用多层桶数组结构，底层为紧凑桶（compact bucket），上层混合紧凑桶与稀疏桶（sparse bucket），并引入快速路径（fast path）机制利用稀疏桶中的空槽绕过中间层。向量化的桶内搜索（SIMD-based in-bucket search）进一步弥补了因粒度放宽带来的预测误差。

大量实验在SOSD和updatable learned index基准的多个最难真实数据集上验证了VEGA的有效性：相比RMI和PGM等最先进方法，VEGA在查询吞吐量和构建吞吐量上均取得显著领先，同时保持了与全通信、无缓存框架相当的精度。该工作不仅填补了学习索引在理论界限与经验性能之间的空白，还为只读型学习索引的设计提供了可扩展、可理论保证的系统框架，具有重要的学术创新价值和工程实用意义。

2. 引言（Introduction）

近年来，机器学习在构建索引结构上的应用取得了显著成功，学习索引通过用模型拟合键值映射关系，大幅提升了查询效率。然而，不变学习索引（immutable learned index）在实际部署中面临一个长期存在的理论与实践脱节问题：最快的RMI虽在经验查询性能上领先，却缺乏非平凡的最坏情况查询界限，可能在对抗性或长尾分布下出现性能退化；相反，提供严格理论界限的PGM虽保证了查询复杂度，却在平均查询吞吐量上落后于RMI。这种“要么快但无界限、要么有界限但慢”的困境，使得学习索引在与经典B树等结构竞争时始终难以同时兼顾理论保证与实际性能。

论文首先通过SOSD-osmc数据集上的对比实验清晰展示了这一性能差距：RMI在查询延迟上显著优于PGM，但PGM的索引高度更高，导致最坏情况查询复杂度较差。作者进一步指出，造成这一差距的核心原因在于传统学习索引采用的“per-key learning granularity”：每个键独立参与模型训练，导致模型数量过多、索引高度过高，同时真实世界分布的非均匀性和复杂性进一步放大了这一问题。

VEGA的创新点在于首次提出“group-wise learning granularity”与“active distribution tuning”两大策略。前者通过将连续键打包成固定大小的组，仅用组内首键构建模型，实现了模型数量从O(n)到O(n/k)的降低；后者则通过键重定位主动调优简化后的分布，使单层模型数量进一步降至1，同时将空间开销控制在可接受范围内。两者结合的通用框架在给定内存预算下动态优化分区策略，确保VEGA在理论查询复杂度上达到O(log(n/3k) + log k)，在经验性能上超越现有最优方法。该工作不仅为只读学习索引提供了理论与实践统一的解决方案，也为后续动态学习索引的设计奠定了重要基础。

3. 背景与动机（Background and Motivation）

学习索引可分为可变型（mutable）和不变型（immutable）两大类。可变型索引（如ALEX、LIPP）重点支持动态更新，牺牲空间效率换取操作吞吐量；不变型索引则专注于只读场景，通过极致压缩空间和优化查询路径实现高性能，广泛应用于键值存储、网络包分类、区块链查询等读密集型负载。RMI作为不变型索引的代表，采用自顶向下的递归划分策略，在经验性能上领先，但理论上缺乏非平凡最坏情况界限；PGM则采用自底向上的分段线性逼近，提供了O(log M_pla-1 + log k)的查询复杂度，却因模型数量过多导致实际查询延迟较高。

现有方法的局限主要体现在两个方面：一是per-key学习粒度导致索引高度过高，查询路径变长；二是真实世界分布的复杂性使单纯放松粒度难以有效减少模型数量。论文通过SOSD基准数据集的实验进一步证实，PGM在最难数据集上的索引高度可达6层，而RMI仅为2层，直接导致查询性能差异。VEGA的动机正是填补这一理论-实践鸿沟，通过group-wise粒度简化分布、active tuning调优分布，以及F1/F2策略的动态组合，在严格理论界限下实现最优经验性能。该设计不仅解决了现有索引的根本矛盾，也为学习索引在实际系统中的大规模部署提供了可行路径。

4. VEGA系统架构与高层设计（VEGA Architecture and High-level Idea）

VEGA采用多层桶数组结构，每层由固定大小的桶组成，底层为叶数据层（leaf data layer），上层为非叶索引层（non-leaf index layer）。每个桶大小等于当前层的学习粒度k，桶内键按SIMD宽度对齐以支持向量搜索。VEGA的构建采用自底向上的递归方式，每层通过F1或F2策略构建误差有界线性模型，用于预测下一层的桶位置。

高层设计的核心在于紧凑桶（compact bucket）与稀疏桶（sparse bucket）的混合使用：F1策略下每个组精确填充一个紧凑桶，无空槽；F2策略下通过键重定位将组映射到更大桶数组，产生稀疏桶并利用空槽实现快速路径。快速路径机制通过直接复制下层模型到稀疏桶空槽，可绕过中间层，进一步缩短查询路径。向量搜索部分采用LS-SIMD（小桶）或BS-LS-SIMD（大桶）混合策略，有效补偿因粒度放宽带来的预测误差。

这种架构既保证了紧致空间占用（小于原始数据集的3%），又通过动态组合F1/F2实现了索引高度的最小化，为VEGA在理论界限与经验性能上的双重优势奠定了基础。

5. F1与F2模型构建策略（F1 and F2 Model Building Policies）

VEGA的核心创新在于F1和F2两大在线模型构建策略。F1（Fitting model to simplified distribution）采用group-wise粒度，将连续k个键打包成组，仅用组内首键参与模型训练。通过扩展误差有界分段线性逼近（PLA），F1证明组内非首键的预测误差仍可被界限（放宽至2·k），从而将模型数量从O(n)降低至O(n/3k)，构建复杂度降至O(n/k)。同时，F1生成的紧凑桶精确填充，无空槽浪费。

F2（Fitting tuned distribution to model）则进一步调优分布：通过键重定位将简化后的组映射到更大桶数组，使单层仅需1个线性模型。F2将重定位问题形式化为优化问题，仅用组内首键构建模型，证明最优斜率和截距可在线性时间内求解，构建复杂度同样为O(n/k)。生成的稀疏桶虽引入空槽，但通过快速路径机制可有效利用。

两者结合的通用框架在给定内存预算下采用贪心或动态规划算法动态选择分区策略，实现模型数量的最小化。该策略既保证了误差界限，又显著降低了索引高度，是VEGA实现理论与实践统一的关键。

6. 构建与查询流程（Construction and Query Procedures）

VEGA的单层构建采用FastConstructOneLayer算法：以桶每键数B为参数，贪心判断当前组是否可用F1或F2容纳，优先使用F2以提升查询效率，同时严格控制空间开销。整体构建通过递归调用该算法完成多层索引，复杂度为O(n log n)。

查询流程分为点查询和范围查询。点查询从顶层开始，利用模型预测下一层桶位置，结合向量搜索定位前驱键，快速路径可跳过中间层；范围查询先通过点查询定位起点桶，再顺序扫描。向量搜索采用LS-SIMD与BS-LS-SIMD混合策略，充分利用SIMD指令有效补偿预测误差。快速路径通过偏移标记区分正常路径与快速路径，无需额外标志位。

这些设计确保了VEGA在实际查询中的高效性和鲁棒性，同时保持了严格的理论复杂度保证。

7. 实验评估与性能分析（Evaluation）

实验在Intel Xeon Gold 6226R CPU + 32GB RAM环境下进行，使用SOSD和updatable learned index基准中最难的四个真实数据集（amzn、face、osmc、genome），并扩展至更多补充数据集、重复数据集和偏斜分布数据集。基线包括RMI、PGM、RS、ALEX、LIPP、NFL、DILI、FAST、ART、BTree等10种最先进索引。

点查询结果显示，VEGA在单线程和多线程下均取得最高吞吐量，相比RMI平均提升1.5倍，相比PGM提升3倍以上；范围查询吞吐量同样领先。构建时间上，VEGA与最快的RS相当，远优于RMI和PGM。参数评估证实粒度k=8时性能最优，向量指令（AVX-512）带来显著延迟降低。快速路径评估显示，当快速路径比例达80%时，查询延迟可降低30%。

消融实验和更广泛数据集验证进一步证实VEGA在不同分布下的鲁棒性，即使在内存栅栏约束下仍保持领先。该结果充分证明了VEGA在理论界限与经验性能上的双重优势。

8. 贡献与结论（Contributions and Conclusion）

VEGA的主要贡献包括：（1）提出group-wise学习粒度范式，实现无需逐键访问的模型构建，将构建复杂度降至O(n/k)；（2）设计轻量级分布调优方法F2，在最小空间开销下将模型数量进一步降至1；（3）提出F1/F2动态组合框架，在给定内存预算下实现查询性能最优；（4）通过理论分析证明查询复杂度达到或优于现有最优方法；（5）大规模实验验证VEGA在查询和构建性能上的全面领先。

论文结论指出，VEGA成功桥接了学习索引理论界限与经验性能之间的长期鸿沟，为只读型学习索引提供了完整、可理论保证的系统解决方案。尽管当前主要针对只读场景，但VEGA的框架为未来增量更新等扩展提供了坚实基础。该工作不仅具有重要的学术价值，也为键值存储、网络分类等实际系统中的学习索引部署提供了可落地的技术参考。