学习型索引在查询分布偏移下的鲁棒性：基于 SOSD 基准的双成本口径尾延迟测定

1 · 研究问题

在 SOSD（Search On Sorted Data）标准数据集上，学习型索引（learned index：RMI、RadixSpline、PGM-Index）相对传统索引（ART、STX B+ 树、二分查找）的查找延迟优势，在查询键分布由均匀随机偏移为偏斜分布（Zipf 热点、范围局部性）时是否仍然成立？若优势衰减，衰减幅度能否由各结构的"最后一英里"（last-mile）搜索区间宽度定量预测？

2 · 研究背景与空白

技术背景。 学习型索引把"有序数组上的键 → 位置"映射视为累积分布函数（CDF）的回归问题：先用一个小模型（分段线性、样条、两层递归模型）预测目标位置，再在预测位置附近的一个有界区间内做局部搜索定位精确下标。这个"预测 + 最后一英里搜索"的两阶段结构，把传统 B 树的 O(log n) 次指针追逐（pointer chasing，每一次都可能是一次缓存缺失）换成了若干次算术运算加一次局部扫描。因此它的性能优势本质上是内存局部性优势，而不是渐进复杂度优势——纯 CPU 环境下，一次末级缓存（LLC）缺失约合 200–300 个时钟周期，这才是真正的成本主项。这一点使该课题天然绕开算力墙：它测的是缓存行为，不是浮点吞吐，一台普通笔记本与一台服务器在"每次查找的缺失次数"这个口径上是可比的。

已有工作到哪一步。 Kipf 等人的 SOSD 基准（arXiv:1911.13014，及 Marcus 等人 VLDB 2021《Benchmarking Learned Indexes》）建立了公开的数据集与实现框架，覆盖 books / fb / osm / wiki 等真实与合成键集（每个 200M 条 64 位键，另有 32 位变体），统一比较 RMI、PGM、RadixSpline 与 STX B+ 树、插值 B 树（IBTree）、ART。已发表的定量结论包括：RMI 的构建时间显著慢于 PGM 与 RadixSpline，且没有任何学习型结构的构建速度能追上面向插入优化的传统结构；在 32 位数据集上 ART 表现极好，在 face32 上甚至优于全部对手；RMI 与 RadixSpline 都需要针对数据集手工调参。SOSD 还内置了分支误预测与指令数的自动分析。Crotty 的 Hist-Tree（CIDR 2021）进一步指出，一个朴素的直方图结构在同样基准上就能逼近学习型索引。

空白在于：SOSD 及其后续工作的查询负载几乎全部是"从键集中均匀随机抽取"的查找。而真实系统里的查询分布是重度偏斜的（热点键、时间局部性、范围扫描起点聚集）。偏斜会让传统结构的上层节点常驻缓存（ART 的前几层、B+ 树的内节点），而学习型索引的模型本来就小、本来就常驻，其增益空间反而可能被压缩——但这个方向没有被系统测量过。这个空白属于"评价维度的转换"，可靠性高：数据、代码、基线数值全部公开，实验成本是笔记本级的，且结论正负都成立（优势保持是对学习型索引普适性的一次独立支持；优势消失则是一条对系统设计有用的负面结论）。

3 · 可检验假设

• H1：在 Zipf(s≈1.1) 偏斜查询负载下，RMI 相对 ART 的中位查找延迟优势，比均匀随机负载下缩小 ≥ 30%（相对量）；在极端偏斜（前 1% 键承担 90% 查询）下优势完全消失或反转。
• H2：各结构在同一负载下的 p99/p50 延迟比，与其"最后一英里"搜索区间宽度的对数 log₂(ε) 呈单调正相关，跨 4 个数据集 × 5 个结构的 20 个数据点上线性拟合决定系数 R² ≥ 0.7。若 R² < 0.7，说明尾延迟主要由分支误预测而非区间宽度决定——这同样是有效结论。

4 · 量化验收标准

1. 方法学校验（硬门槛）：用自行编译的 SOSD 管线，在 books / fb / osm / wiki 四个数据集（若内存不足则用官方 200M 集的前 100M 切片，并同时报告切片对结论的影响）上、对至少 5 种索引结构，重现原基准的均匀随机查找结果。因跨硬件绝对延迟不可比，判据定为微架构计数器口径：每次查找的末级缓存缺失数与退休指令数，与 SOSD 公开数值的偏差 ≤ 15%；同时要求各结构的相对排序与原文完全一致。这一步不过关，后续全部结论无效。
2. 基准测试方法学：每个（结构 × 数据集 × 负载）组合至少重复 30 次独立运行，每次 10M 次查找；运行前固定 CPU 频率（Linux cpupower frequency-set --governor performance，禁用 Turbo 与 SMT）、每次运行前显式冲刷缓存（遍历一块 ≥ LLC 两倍的哑数组）、绑核（taskset）、关闭后台进程。报中位数与四分位距（IQR），不报均值与标准差，并给出全部 30 次的分布图；跨组比较用 Mann–Whitney U 检验而非 t 检验。
3. 双成本口径：与已发表实现的对照必须同时报两种口径——等工作量（相同查询条数下的墙钟时间与缺失数）与等墙钟时间预算（固定 5 秒内完成的查询条数）。两种口径的结论若不一致，必须在正文中明确讨论。
4. 构建成本单列：报告每种结构的构建时间与内存占用（含峰值），并给出"构建成本需多少次查询摊销回本"的交叉点，按偏斜与均匀两种负载分别给出。
5. 负载覆盖：至少 4 种查询分布（均匀、Zipf s=0.8、Zipf s=1.1、范围局部性），每种给出明确、可复现的生成脚本与固定随机种子。
6. 可复现性：全部代码、负载生成器、原始计时数据（CSV）与绘图脚本开源；提供 make reproduce 一键重跑脚本；随机种子写死在配置文件中。

5 · 数据与工具

用途	来源 / 工具
基准框架与索引实现	SOSD 开源仓库（GitHub learnedsystems/SOSD），含 RMI、RadixSpline、PGM、STX B+ 树、ART、二分/插值搜索的统一封装。仅用于校验与对比，不计入本项目的数据贡献。
键数据集	SOSD 官方数据集（books / fb / osm / wiki，200M × 64 位；另有 32 位变体），由仓库脚本自动下载（托管站点为 Harvard Dataverse，需核实当前链接是否仍有效；若失效则用仓库提供的合成生成器 + 公开 OSM 导出自建等价集，并声明差异）
RMI 生成器	独立的 Rust 工具 learnedsystems/RMI，需安装 Rust 工具链后代码生成再编译。依赖链较重，列为风险项
微架构计数器	Linux perf stat（需真机，虚拟机/WSL2 通常无 PMU 访问权限，需核实）；退路为 Valgrind cachegrind（模拟计数，非真实计数，须在正文标注口径）
计时	rdtsc / clock_gettime(CLOCK_MONOTONIC)；校准 TSC 频率
统计与作图	Python + NumPy / SciPy（Mann–Whitney U、自助法置信区间）+ Matplotlib
算力	纯 CPU；200M × 8 字节键 = 1.6 GB，加索引结构峰值约 4–6 GB，16 GB 笔记本可容纳；单次完整扫（5 结构 × 4 数据集 × 4 负载 × 30 重复）估计 6–12 小时，可夜间批跑

6 · 方法路径

1. 装 Linux 真机环境与工具链，编译 SOSD，跑通仓库自带算例，确认 perf 可读 PMU；完成验收标准第 1 条的重现校验并归档原始数据。
2. 核实工具能力边界：RMI 生成器是否能在本机成功产出并编译；PGM 与 RadixSpline 的误差参数 ε 是否可外部配置；SOSD 的计时循环是否已做防编译器优化（DoNotOptimize 类屏障）——若没有，须自行加入并在正文说明。
3. 实现查询负载生成器：给定键集与分布参数产出查询序列，写明每种分布的精确定义与种子；对"范围局部性"给出明确、可复现的判据（例如按滑动窗口从键空间的 0.1% 区间内抽取）。
4. 实现基准测试骨架：频率锁定、绑核、缓存冲刷、30 次重复、原始逐次结果落盘为 CSV（不做在线聚合，保留全部分布信息）。
5. 执行主扫描（结构 × 数据集 × 负载 × 重复），同步采集 perf 计数器；对每个结构额外记录"最后一英里"搜索区间宽度的经验分布（需在各实现中插桩）。
6. 分析：按第 4 块口径出中位数/IQR、Mann–Whitney 检验、双成本口径对照表、构建成本摊销交叉点；拟合 H2 的 log₂(ε) 关系并给自助法置信区间。
7. 独立交叉校验：用 cachegrind 模拟计数复算至少一个（结构 × 数据集）组合的缓存缺失，与 perf 真实计数比对；再用一台不同微架构的机器（同学的笔记本即可）重跑关键组合，验证结论的排序不随硬件改变。

7 · 新颖性边界

本课题不声称：不提出新的索引结构，不声称学习型索引在任何意义上"更好"或"更差"，不声称任何新的复杂度界。SOSD 框架、全部索引实现与数据集均为他人工作，明确标注为对照基准，不计入本项目贡献。

已有工作完成了什么：Kipf 等的 SOSD（arXiv:1911.13014）与 Marcus 等（VLDB 2021）在均匀随机查找负载下，对 RMI / PGM / RadixSpline / STX B+ 树 / IBTree / ART 给出了查找延迟、构建时间、内存占用与分支误预测的系统比较；Crotty（CIDR 2021）用 Hist-Tree 说明简单直方图即可逼近学习型索引。这些结论本项目不重复声称。

本项目的贡献：把评价维度从"平均查找延迟"转换为"查询分布偏移下的延迟分布（含尾部）"，并给出偏斜负载下的双成本口径对照与构建成本摊销交叉点。这是主结论，不是附加内容。

为什么有价值：真实数据库负载是重度偏斜的，而现有基准只测均匀负载。若优势保持，学习型索引的实用价值获得一次独立支持；若优势在偏斜下消失，则说明现有基准系统性高估了这类结构——两个方向都是可发表的判断。

风险提示：若各结构在偏斜负载下差异不显著，"差异不显著"同样是有效结论，但必须给出 30 次重复的 IQR 误差棒，证明本实验有能力分辨题设中 30% 这一量级的差异。

8 · 决策门槛（go / no-go）

• 第 6 周：环境与编译门槛。若 SOSD 无法在本机编译通过、或数据集下载链接失效，立即降级路径 A：放弃 RMI（Rust 依赖最重），只保留全部 header-only 的 RadixSpline、PGM、STX B+ 树、ART、二分与插值搜索五种结构；数据集改用仓库合成生成器 + 公开 OSM 节点 ID 导出自建。主结论框架（偏斜负载下的延迟分布对照）完全不受影响。
• 第 10 周：方法学校验硬门槛。若微架构计数器偏差 > 15% 或相对排序与原文不一致，先排查是否为频率漂移/SMT/编译器优化屏障问题；到第 12 周仍不过关则降级路径 B：把口径整体改为 cachegrind 模拟计数（确定性、跨机器可比），全文统一声明为"模拟计数口径"，放弃绝对延迟的跨文献对照，保留组间相对比较。主结论不变。
• 第 14 周：perf PMU 可用性必须已核实清楚——这是需要提前确认而非边做边发现的事项。若学生只有 macOS 机器，须在第 4 周前解决 Linux 真机（双系统或旧机器重装），否则整条路线的计数器口径不成立。
• 第 26 周：主扫描完成且 H1 有明确结论（成立或否证）。若此时仍在调试基准骨架，降级路径 C：把数据集从 4 个减为 2 个（books + fb，一真实一合成）、负载从 4 种减为 3 种，用省下的时间保证重复次数与统计口径完整。宁可少扫参数点，不可减少重复次数——统计口径是本课题的核心卖点。
• 预算裁剪顺序：数据集数量 → 结构数量 → 负载种类 → （绝不裁剪）重复次数与频率控制。
• 选择前提：适合已能独立写 C++、愿意花时间处理构建系统与 Linux 环境的学生。若学生只会 Python，这条路线的第 1 步就会卡死，应改选 K02 或 K06。

---