一般人不知道｜这样写 Limit 会导致性能骤降

PG 向量搜索优化 | 这样写 Limit 会导致性能骤降

在使用向量搜索时, 通常会取TOP N的相似结果, 例如下面的SQL取limit 10:

SELECT * FROM items ORDER BY embedding <-> '[0, 0, 0]' LIMIT 10;    

这样性能很不错, 走索引, 然后取10条即可.

但是, 如果稍微改动一下SQL, 加一个 where 条件, 限制相似度(比如限制向量距离在xx以内)阈值, 可能导致性能骤降. 如果数据量较大, 性能惨不忍睹!

SELECT * FROM items     
  WHERE embedding <-> '[0, 0, 0]' < 0.1     
  ORDER BY embedding <-> '[0, 0, 0]'     
  LIMIT 10;    

原因是优化器并不知道距离操作符的排序和小于是步调一致的.

满足这个where条件的记录数够Limit指定的10条时, 性能完全没问题.

如果满足这个条件的记录数不足Limit指定的10条, 那么优化器会把整个索引扫描完, 直到最终找不到10条满足条件的记录, 导致性能骤降.

                                  QUERY PLAN                                       
-------------------------------------------------------------------------------    
 Limit    
   ->  Index Scan using items_embedding_idx on items    
         Order By: (embedding <-> '[0,0,0]'::vector)    
         Filter: ((embedding <-> '[0,0,0]'::vector) < '0.1'::double precision)    

在GIST索引中存在同样的问题, 下面有两篇文章进行了详细介绍, 同时提供了解决方案.

《PostgreSQL GiST Order by 距离 + 距离范围判定 + limit 骤变/骤降优化与背景原因》

《GIS附近查找性能优化 - PostGIS long lat geometry distance search tuning using gist knn function》

向量搜索也可以使用以上方法来解决此问题.

但是, 除了使用以上解决方案之外, 还有什么更优雅的解决方案吗?

vectorchord 提供了 similarity filter 的算子, 可解决这个问题, 用起来还比较优雅.

similarity filter

如果你使用vectorchord插件, 为了避免这种性能骤降情况，可以使用特定语法将过滤器下推至向量索引，使其在搜索区域超出指定距离时立即停止搜索。我们将这种可以下推至索引的基于距离的条件称为相似性过滤器。

EXPLAIN (COSTS FALSE)     
SELECT * FROM items WHERE embedding <<->> sphere('[0, 0, 0]'::vector, 0.1) ORDER BY embedding <-> '[0, 0, 0]' LIMIT 10;    
                               QUERY PLAN                                   
------------------------------------------------------------------------    
 Limit    
   ->  Index Scan using items_embedding_idx on items    
         Index Cond: (embedding <<->> '("[0,0,0]",0.1)'::sphere_vector)    
         Order By: (embedding <-> '[0,0,0]'::vector)    

当且仅当两个向量之间的 L2 距离小于 0.1 时，embedding <<->> sphere('[0, 0, 0]'::vector, 0.1) = true。对于负内积使用 <<#>> 运算符，对于余弦距离使用 <<=>> 运算符。

此外，如果仅指定WHERE, 不带ORDER BY，索引仍然可以使用。

EXPLAIN (COSTS FALSE)     
SELECT * FROM items WHERE embedding <<->> sphere('[0, 0, 0]'::vector, 0.1);    
                            QUERY PLAN                                
------------------------------------------------------------------    
 Index Scan using items_embedding_idx on items    
   Index Cond: (embedding <<->> '("[0,0,0]",0.1)'::sphere_vector)    

Similarity Filter的实现原理

"Similarity Filter"实际上是指VectorChord中的球形搜索操作符（sphere search operators），这是一种基于半径的相似性过滤机制。

实现原理

VectorChord实现了三种球形搜索操作符用于相似性过滤：

• <<->>: L2距离球形搜索
• <<#>>: 内积球形搜索
• <<=>>: 余弦距离球形搜索

这些操作符与球形复合类型配合使用，如sphere_vector、sphere_halfvec和sphere_scalar8，每个都包含一个中心向量和半径值 。

CREATE OPERATOR CLASS vector_l2_ops  
    FOR TYPE vector USING vchordrq FAMILY vector_l2_ops AS  
    OPERATOR 1 <-> (vector, vector) FOR ORDER BY float_ops,  
    OPERATOR 2 <<->> (vector, sphere_vector) FOR SEARCH,  
    FUNCTION 1 _vchordrq_support_vector_l2_ops();  

CREATE OPERATOR CLASS vector_ip_ops  
    FOR TYPE vector USING vchordrq FAMILY vector_ip_ops AS  
    OPERATOR 1 <#> (vector, vector) FOR ORDER BY float_ops,  
    OPERATOR 2 <<#>> (vector, sphere_vector) FOR SEARCH,  
    FUNCTION 1 _vchordrq_support_vector_ip_ops();  

CREATE OPERATOR CLASS vector_cosine_ops  
    FOR TYPE vector USING vchordrq FAMILY vector_cosine_ops AS  
    OPERATOR 1 <=> (vector, vector) FOR ORDER BY float_ops,  
    OPERATOR 2 <<=>> (vector, sphere_vector) FOR SEARCH,  
    FUNCTION 1 _vchordrq_support_vector_cosine_ops();  

核心实现机制

在vchordrq索引的搜索过程中，相似性过滤通过DefaultBuilder实现：

当检测到球形搜索时，系统会：

1. 提取球形的中心向量作为查询向量
2. 将半径设置为阈值
3. 启用重新检查机制以确保结果在指定半径内

搜索流程

相似性过滤集成在标准的default_search函数中，该函数执行分层IVF结构的近似最近邻搜索 。

搜索过程包括：

1. 向量预处理: 使用RandomProject::project进行投影
2. 分层遍历: 通过质心导航到叶子节点
3. 距离计算: 计算下界距离 Distance::from_f32(rough - err * epsilon)
4. 结果过滤: 根据球形半径过滤候选结果

重排序集成

相似性过滤与重排序系统紧密集成，通过rerank_index函数提供精确距离计算 。

这确保了在初始近似搜索后，系统能够计算精确距离并应用半径约束，从而实现高质量的相似性过滤。

为什么Similarity Filter（相似性过滤）可以下推到索引扫描阶段进行过滤

根据代码分析，这主要是因为VectorChord在PostgreSQL的索引访问方法层面实现了球形搜索操作符的原生支持 。

PostgreSQL索引访问方法集成

VectorChord通过实现PostgreSQL的IndexAmRoutine接口，将相似性过滤直接集成到索引扫描过程中 。在ambeginscan和amrescan函数中，系统会解析查询条件并构建相应的扫描器。

查询条件解析和下推机制

在amrescan函数中，系统会处理两类查询条件：

• orderByData: ORDER BY子句中的向量相似性条件
• keyData: WHERE子句中的过滤条件

关键在于DefaultBuilder会同时处理这两类条件，将球形搜索的半径约束直接传递给底层的搜索算法 。

索引层面的过滤实现

在default_search执行过程中，相似性过滤通过以下方式实现下推：

1. 阈值传递: 球形搜索的半径直接作为threshold参数传递给搜索算法
2. 早期终止: 搜索过程中使用take_while操作符，当距离超过阈值时立即停止
3. 预过滤支持: 通过prefilter配置参数，可以在重排序之前就应用过滤条件

重排序阶段的过滤

即使在重排序阶段，相似性过滤仍然保持下推特性。系统会在rerank_index函数中继续应用距离阈值，确保只有满足半径约束的结果才会被返回 。

配置参数支持

VectorChord提供了vchordrq_prefilter配置参数来控制预过滤行为 ，这进一步增强了过滤下推的灵活性。

Notes

相似性过滤的下推能力是VectorChord相比传统向量数据库的重要优势。通过在索引访问方法层面实现过滤逻辑，避免了在应用层进行后过滤的性能开销。这种设计充分利用了PostgreSQL的查询优化器和执行引擎，实现了真正的谓词下推。

参考

《PostgreSQL GiST Order by 距离 + 距离范围判定 + limit 骤变/骤降优化与背景原因》

《GIS附近查找性能优化 - PostGIS long lat geometry distance search tuning using gist knn function》

https://docs.vectorchord.ai/vectorchord/usage/range-query.html

https://deepwiki.com/search/similarity-filter_d766f6fb-c08d-495e-be97-ef440b6e6b65