pgvector项目中的迭代式索引扫描技术解析

在pgvector项目中，开发者们正在探索一种创新的索引扫描方式——迭代式索引扫描（Iterative Index Scans），这项技术有望显著提升向量搜索的性能和灵活性。本文将深入解析这项技术的实现原理、优势特点以及在实际应用中的表现。

技术背景

pgvector作为PostgreSQL的向量搜索扩展，目前支持HNSW和IVFFlat两种索引类型。传统索引扫描方式在遇到带有过滤条件的查询时，往往无法高效处理，特别是当需要满足"ORDER BY ... LIMIT"语义时。迭代式索引扫描技术应运而生，旨在解决这一痛点。

实现原理

迭代式索引扫描的核心思想是将搜索过程分解为多个批次进行：

1. HNSW索引实现：

   • 在搜索过程中保留被丢弃的候选节点
   • 当需要更多结果时，以这些候选节点为入口点进行批次搜索
   • 搜索终止条件包括：获取足够结果、达到ef_stream限制或耗尽work_mem

2. IVFFlat索引实现：

   • 按批次扫描最近的列表组
   • 每次扫描probes个列表
   • 最多扫描max_probes个列表

开发者提供了两种启用方式：

SET hnsw.streaming = on;
SET ivfflat.streaming = on;

技术挑战与解决方案

在实现过程中，开发团队遇到了几个关键挑战：

1. 带距离过滤的查询终止问题：

   • 当实际匹配结果少于LIMIT数量时，扫描会不必要地继续
   • 尝试使用xs_orderbyvals等方法未获成功

2. 结果排序问题：

   • 迭代式扫描可能导致结果不完全有序
   • 严格排序会降低召回率(从95.8%降至91.8%)
   • 批次大小影响结果顺序性(大批次可减少乱序)

3. 空表处理问题：

   • 初始实现中TRUNCATE后搜索会崩溃
   • 通过正确初始化discarded队列解决

性能表现

在实际测试中，迭代式索引扫描展现出良好的性能：

1. 在arxiv数据集(210万向量，384维)上：

   • hnsw-filtering分支：108秒，召回率95.8%
   • hnsw_iterator实现：167秒，召回率95.9%
   • relaxed实现：221秒，召回率95.5%

2. 批次大小(ef_search)对召回率的影响：

   • 较小批次(ef_search=10)严格模式召回率91.3%
   • 较大批次(ef_search=1000)严格模式召回率可达94.4%
   • relaxed模式始终维持较高召回率(95.6%-97.2%)

未来方向

基于当前成果，开发团队正在考虑以下发展方向：

1. 提供多种搜索模式选择：

   SET hnsw.iterative_search = off; -- 传统模式
   SET hnsw.iterative_search = on;  -- 严格模式
   SET hnsw.iterative_search = relaxed; -- 宽松模式
   

2. 优化距离过滤查询的处理，可能需要调整查询编写方式

3. 进一步平衡排序严格性与召回率的关系

这项技术的引入将使pgvector在复杂查询场景下表现更加出色，特别是对于需要结合精确过滤与近似搜索的应用场景。随着持续优化，迭代式索引扫描有望成为pgvector的核心功能之一。