1. 问题与动机
带过滤条件的向量搜索 (Filtered Vector Search, FVS) 是支撑语义搜索和 GenAI 应用的关键能力。然而，现有研究绝大多数在 HNSWLib 等独立向量库中评估算法性能，这些环境做出了乐观假设——连续内存布局、裸指针直接解引用、无页面管理开销。当同样的算法部署到生产级数据库系统（如 PostgreSQL）中时，性能特征发生根本性变化。作者通过实证表明，独立库与数据库的系统延迟差距可达 10 倍，更关键的是，算法间的优劣关系（即不同选择率下哪个算法更优的交叉点）也会完全改变。
这一差距的根源在于：数据库系统使用基于元组的存储（8KB 页面）、需要通过 buffer manager 进行散落页面访问、过滤条件验证需要额外的 TID（Tuple ID）间接寻址。这些系统级开销使得传统以"最小化距离计算次数"为优化目标的假设不再成立——在 PostgreSQL 中，页面访问和数据检索的系统开销才是主导因素。
2. 方法详解
评估的算法族
论文系统评估了两大类五种 filter-agnostic 向量搜索算法：
图方法（基于 HNSW）：
- ACORN (Filter-First)：在 HNSW 图上执行谓词子图遍历，每步收集 1-hop 和 2-hop 邻居，先过滤再计算距离。
- NaviX (Filter-First + 自适应)：提供 Blind、Directed、Onehop-s 三种启发式，根据运行时观察到的过滤选择率动态切换。Directed 模式从最近的 1-hop 节点出发优先探索 2-hop 邻居。
- Sweeping (Traversal-First)：先按近邻关系遍历，仅在加入结果集时检查过滤条件。
- Iterative Scan (Traversal-First)：可恢复的后过滤方式，维护被丢弃候选的队列以支持暂停节点的恢复。
聚类方法：
- Filtered ScaNN：三层树结构（根质心→分支质心→叶向量），仅对满足过滤条件的叶向量计算距离，天然支持 SIMD 向量化和量化压缩。
关键系统优化
论文在 PostgreSQL 中实现了两个关键优化：
- Translation Map：在索引构建时预计算一个内存哈希表，将 indextid 直接映射到 heaptid，消除了 2-hop 邻居解析时的整类页面访问。
- 自适应 2-hop 扩展：当 1-hop 邻居已通过过滤条件时，跳过该分支的 2-hop 扩展，在高选择率下显著减少页面访问。
工作负载生成
设计了支持指定选择率 (1%-90%) 和相关性类型（高/中/低正相关、负相关、无相关）的工作负载生成器，通过 softmax 偏置采样从距离排序的向量中生成满足条件的行 ID，无需合成结构化数据。
3. 核心技术贡献
贡献一：揭示系统开销主导性。 即使在单线程执行中，系统开销（页面访问、buffer manager 查找、TID 间接寻址）占总 CPU 周期的 55.9%-84.4%。在 16 线程并发下，系统开销比例进一步上升至 73.5%-91.0%。这证明高开销是算法内在架构成本，而非并发争用导致。
贡献二：发现选择率交叉点的系统依赖性。 Filter-first 方法（NaviX/ACORN）在低选择率（1%-5%）下表现更优，traversal-first 方法在高选择率（≥50%）下反转优势。NaviX-Directed 在 5%-30% 的中间选择率区间一致优于 ACORN（跳数分别为 12.8 vs 21.9 at 10% 选择率）。
贡献三：图方法与聚类方法的系统级权衡。 ScaNN 在低维数据上有 2-3 倍优势（得益于顺序访问和 SIMD），在高维数据上优势缩小。图方法在结果集 k 值增大时更鲁棒（NaviX 跳数增长 86% vs ScaNN 叶访问增长 220%）。ScaNN 在负相关场景下表现稳健（性能仅降 6%），而图方法可降 53%。
贡献四：量化对不同架构的差异化影响。 HNSW 的 halfvec/binary 量化在 PostgreSQL 中几乎无加速效果（0.75-1.04×），因为瓶颈在随机页面访问而非距离计算。而 ScaNN 的 PCA+SQ8 量化可获得 7-50 倍加速，因为顺序扫描模式天然兼容量化。
4. 实验结果分析
实验在四个数据集上进行：sift10M (10M×128D)、openai5M (5M×1536D)、cohere10M (10M×768D)、text2image10M (10M×200D)，使用 95% Recall@10 为目标，16 并发连接。
关键数据对比（OpenAI-5M, 10% 选择率）：
| 算法 | 距离计算 | 过滤检查 | 跳数/叶数 | 页面访问 |
|---|---|---|---|---|
| NaviX | 627 | 36.2K | 13.0 | 1.1K |
| ACORN | 614 | 34.9K | 23.0 | 1.4K |
| Sweeping | 5.0K | 910 | 197 | 5.2K |
| ScaNN | 3.8K | 76.9K | 80 | 2.8K |
NaviX 以更少的跳数（13.0 vs ACORN 的 23.0）和更少的页面访问（1.1K vs 1.4K）取得优势。Sweeping 的距离计算高出 8 倍，但过滤检查仅为 NaviX 的 1/40。
非单调性能现象： 自适应算法在 10%-30% 选择率区间出现性能凹陷，原因是启发式策略的相变：激进过滤期（1%-5%）→过渡区（5%-30%，过滤检查仍高但距离计算已增加）→收敛期（≥50%，切换到标准 1-hop 遍历）。
CPU 周期分解分析揭示： 在 1% 选择率下，Sweeping 的向量数据检索系统开销超过 3 亿 CPU 周期，远超距离计算本身。ScaNN 的主要开销来自重排序步骤需要从堆中检索全精度向量（OpenAI-5M 的 32× 压缩意味着每个向量约需 1 页）。
5. 局限与未来方向
作者明确指出的局限：(1) 研究聚焦于内存场景（使用 pg_prewarm），未涉及磁盘 I/O 变异性；(2) 实验假设过滤条件为"低开销过滤"（通过预计算 bitmap 评估），未覆盖过滤评估本身成为瓶颈的场景；(3) HNSW 使用固定构建参数（M=32, ef_construction=200），未做全面的参数调优；(4) 结果基于 AMD EPYC 7B13 CPU，在不同缓存层次或 SIMD 能力的硬件上行为可能不同；(5) 聚类方法仅用 ScaNN 代表，其他聚类变体可能有不同表现。
6. 工业实践意义
直接可借鉴的工程决策：
- 选型建议：如果搜索系统使用 PostgreSQL 兼容数据库（如许多社区产品），不应盲目选择 HNSW——在低维 embedding 或低选择率场景下，ScaNN 类聚类索引可能更优。
- 量化策略：在数据库系统中，HNSW 的向量量化几乎无法带来延迟收益（因瓶颈在页面访问），应优先考虑 Translation Map 等系统级优化。ScaNN 可从 PCA+量化获得数量级加速。
- 选择率感知路由：生产系统应根据查询的预估过滤选择率动态选择算法——低选择率用 NaviX-Directed，高选择率用 Sweeping 或标准 HNSW。
- 负相关防御：当过滤条件与向量相似度呈负相关时（如搜索"最近发布的相似内容"，时效性与相似度可能负相关），ScaNN 比图方法更鲁棒。
- Benchmark 警示：团队在评估向量搜索方案时，必须在实际数据库环境而非独立向量库中进行，否则选型结论可能完全错误。
部署考量： 论文使用的 Translation Map 优化已在 PostgreSQL 中实现，额外内存开销可控。论文作者团队来自 Google，系统设计具有工业级水准。PACMMOD 2026 录用进一步验证了工作的学术严谨性。