VexDB DiskANN 图索引原理与实践

VexDB DiskANN 图索引原理与实践

之前分享了VexDB的ivfpq 聚集点向量索引 和 graph_index图向量索引原理

• 《容器体验VexDB! 》
• 这家国产向量数据库说他们的图索引超越HNSW，是不是真的？

这篇将继续分享VexDB的 DiskANN 图向量索引, 这个接口主要是通过量化和压缩来降低图向量索引内存消耗、计算量. 实际上DiskANN图索引在PG生态中已有2个类似插件, 如需了解可阅读如下文章:

• 《VectorChord新版本发布: 支持图(DiskANN和HNSW)索引、召回率评估》
• 《TimescaleDB 发布基于DiskANN的增强向量索引》

DiskANN的论文解读可参考如下文章:

• 《AI论文解读 | Filtered − DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters》
• 《AI论文解读 | FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search》
• 《AI论文解读 | DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node》
• 《一种新的向量检索索引 DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node》

下面的内容主要来自VexDB官方文档和个人的理解.

• https://vexdb.com/docs/user-guide/diskann

原理介绍

随着数据规模的快速增长，向量检索的计算和存储成本成为了不可忽视的问题。DiskANN 索引是一种结合内存与磁盘存储的高效向量检索结构，通过图算法和量化技术优化大规模高维数据的近似最近邻搜索（ANNS，Approximate Nearest Neighbor Search），在查询速度、准确性与存储成本之间实现了兼顾。

DiskANN 支持将大规模的图索引以及数据集的全量向量存储在磁盘上，同时，为了节省存储空间，采用乘积量化（PQ）将每个数据点压缩，从而大幅降低存储空间的消耗。 压缩向量存储在内存中，原始向量和图存储在 SSD 上 。

搜索时，需要访问某个点的邻居，就从 SSD 中读取并载入主存， 查询向量同样被压缩，通过计算压缩向量之间的距离得到近似距离 。最终仍使用原始向量计算其精确距离( 搜索过程使用压缩向量节省运算量和内存, reranking时使用原始向量精排得到更好的召回效果 ) ，以此决定是否将该向量放入结果队列。

索引的构建

RobustPrune 是一种用于优化图结构的算法，它计算每条边的重要性，根据边的权重或重要性决定保留还是移除边。通过修剪图中不必要的边来降低图的密度，减少搜索时需要遍历的节点数量，同时保留足够的信息以保证查询的准确性。 其中 occlusion_factor 是一个大于 1的修剪参数，决定了在修建过程中保留多少边。occlusion_factor 越大，裁剪的条件越宽松，更多的边会被保留下来。合理的裁剪方式确保了图的持续可导航性和在多次修改后保持稳定召回率的能力。

RobustPrune 剪枝算法可参考论文:

• https://arxiv.org/abs/2002.08797
• https://arxiv.org/abs/2103.06002
• https://arxiv.org/abs/2210.04311
• https://arxiv.org/abs/2310.13191

DiskANN索引的构建过程如下：

1、计算全局质心，以距离全局质心最近的点作为搜索算法的起始节点。

2、从步骤1得到的起始点开始对每个点做贪婪搜索，将搜索路径上所有的点作为候选邻居集。执行 occlusion_factor = 1 的 RobustPrune，消除大部分不必要的边，在确保图的连通性的前提下初步构建图。

3、指定索引构建参数 occlusion_factor（推荐使用默认值 1.2）并再次执行步骤2的过程。

通过上述过程，我们能够获得 直径比 HNSW 更小的图索引 ，从而使 DiskANN 能够最大限度地减少顺序磁盘读取的次数。

通过索引检索

1、遍历当前节点的邻居节点，计算它们与查询向量的距离。

同大多数基于图的ANN算法一样，DiskANN 在搜索时采用贪婪搜索 （GreedySearch）。通过不断地在候选集中选择距离查询点最近的点并探索其邻居，直到找不到更近的点为止。

2、结果筛选。

在贪婪搜索的过程中，始终维护一个大小为K的动态结果队列，用于存储当前找到的最近邻节点。每次找到更近的节点时，更新这个队列。 搜索结束后，返回队列中的 Top-K 作为最近邻结果。

DiskANN索引通过图结构和贪婪搜索策略，能够在庞大数据集的向量搜索中起到显著作用。

索引参数

索引构建参数

查询参数

索引构建操作符

使用建议

1、当需要提升索引构建速度， 可以适当增大 parallel_workers, 建议设置为 机器 CPU核数的 75%，最大值 64。

2、enable_quantization 参数，目前无优势场景，不推荐开启。( 个人理解可能当前的实现还不够优, 所以不推荐开启, 正常来讲量化后可减少计算量, 如果不影响召回率的前提下开启可提高效率, 节省内存和IO. )

3、occlusion_factor 越小图索引连接度越小，部分场景适当下调该参数可以大幅度缩短索引构建时间, 提升插入速度，但过小的参数设置会造成召回精度丢失。

4、enable_subgraph 设置为 true 时相较于使用磁盘和缓存速度更快，但会大幅度牺牲索引的召回精度，不推荐使用。 可理解为分区索引, 搜索时可能会通过某些算法丢弃一些分区的搜索, 导致搜索精度下降.

5、diskann_search_list_size，提高该参数可以提高召回率；相应的，也会消耗更多计算和内存资源，使查询性能降低。

6、diskann_query_with_pq 参数，只有当参数开启且索引已使用参数 enable_quantization 构建才会生效，不推荐开启。

使用示例

1、数据准备：创建用于生成随机向量的函数。

CREATE OR REPLACE FUNCTION random_array(dim integer,min_value int, max_value int)  
RETURNS text  
AS $$  
SELECT REGEXP_REPLACE(REGEXP_REPLACE(array_agg(round(random()* (max_value - min_value + 1) + min_value,3))::text,'{','['),'}',']')  
FROM generate_series(1, dim);  
$$  
LANGUAGE SQL  
VOLATILE  
COST 1;  

2、创建包含向量字段的表并插入测试数据。

drop table t_1194690;  
CREATE TABLE t_1194690(id BIGINT, v floatVECTOR(15));  
INSERT INTO t_1194690 SELECT i, random_array(15,1,3)::floatvector(15) FROM generate_series(1, 10000) AS i;  

3、根据查询需要选择与之匹配的操作符创建 DiskANN 索引。

• 按余弦距离构建索引：

CREATE INDEX idx_1194690a ON t_1194690 USING diskann(v floatvector_cosine_ops)  
WITH(parallel_workers=1,enable_quantization=on,enable_subgraph=on);  

• 按欧几里得距离构建索引:

CREATE INDEX idx_1194690b ON t_1194690 USING diskann(v floatvector_l2_ops)  
WITH(parallel_workers=1,enable_quantization=on,enable_subgraph=on);  

• 按内积构建索引:

CREATE INDEX idx_1194690c ON t_1194690 USING diskann(v floatvector_ip_ops)  
WITH(parallel_workers=1,enable_quantization=on,enable_subgraph=on);  

参数也可省略，此时参数设置为默认值

CREATE INDEX idx_1194690d ON t_1194690 USING diskann(v floatvector_ip_ops);  

4、进行向量相似性搜索。

设置查询参数：

set ef_search=10;  

• 按余弦距离排序：

SELECT * FROM t_1194690   
ORDER BY v <=> '[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]'::floatvector  
LIMIT 10;  

• 按欧几里得距离排序：

SELECT * FROM t_1194690   
ORDER BY v <-> '[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]'::floatvector  
LIMIT 10;  

• 按内积排序：

SELECT * FROM t_1194690   
ORDER BY v <#> '[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]'::floatvector  
LIMIT 10;