DiskANN索引

原理介绍

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

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

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

索引的构建

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

DiskANN索引的构建过程如下：

1. 计算全局质心，以距离全局质心最近的点作为搜索算法的起始节点。
2. 从步骤1得到的起始点开始对每个点做贪婪搜索，将搜索路径上所有的点作为候选邻居集。执行 occlusion_factor = 1 的 RobustPrune，消除大部分不必要的边，在确保图的连通性的前提下初步构建图。
3. 指定索引构建参数 occlusion_factor（推荐使用默认值 1.2）并再次执行步骤2的过程。通过上述过程，我们能够获得直径比 HNSW 更小的图索引，从而使 DiskANN 能够最大限度地减少顺序磁盘读取的次数。

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

通过索引检索

1. 遍历当前节点的邻居节点，计算它们与查询向量的距离。
   同大多数基于图的ANN算法一样，DiskANN 在搜索时采用贪婪搜索 （GreedySearch）。通过不断地在候选集中选择距离查询点最近的点并探索其邻居，直到找不到更近的点为止。
2. 结果筛选。
   在贪婪搜索的过程中，始终维护一个大小为K的动态结果队列，用于存储当前找到的最近邻节点。每次找到更近的节点时，更新这个队列。 搜索结束后，返回队列中的 Top-K 作为最近邻结果。

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

索引参数

索引构建参数

GUC查询参数

索引构建操作符

使用建议

• 当需要提升索引构建速度， 可以适当增大 parallel_workers, 建议设置为 机器 CPU核数的 75%，最大值 64。
• enable_quantization 参数，目前无优势场景，不推荐开启。
• occlusion_factor 越小图索引连接度越小，部分场景适当下调该参数可以大 幅度缩短索引构建和插入速度，但过小的参数设置会造成召回精度丢失。
• enable_subgraph 设置为 true 时相较于使用磁盘和缓存速度更快，但会大 幅度牺牲索引的召回精度，不推荐使用。
• diskann_search_list_size，提高该参数可以提高召回率；相应的，也会消耗更多计算和内存资源，使查询性能降低。
• diskann_query_with_pq 参数，只有当参数开启且进行检索的 DiskANN索引使用 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;