Graph_Index 索引

Graph_Index索引通过构建一个多层次的图结构，利用图中节点的邻近关系，快速定位到离查询向量最近的向量节点。

Graph_Index是基于传统HNSW索引优化后得到的一种图索引，它解决了原生HNSW索引内存占用过高的问题。使用图索引的场景下，更推荐选择Graph_Index。

Graph_Index与原生HNSW

传统的HNSW索引为了获得更好的查询性能，用更多的内存来存储额外的结构和信息，以实现快速且准确的近似最近邻搜索。例如：对于1000w数据量1024维索引，最低存储空间占用大小甚至高达150GB到300GB，因此，过高的内存占用是原生HNSW索引最显著的缺点。

为了解决这一问题，Graph_Index从以下角度对原生HNSW进行了改良：

• 引入缓存机制，大幅度降低了对机器规格的内存要求。
  使用vector_buffers存储向量部分的缓存数据，使用shared_buffers存储邻边关系和元数据等信息。向量索引上的增删改查操作均直接与缓存交互，不产生任何额外的内存申请消耗。
  在同时使用多个向量索引的情况下，Graph_Index能够根据使用情况分配不同大小的缓存给各个索引，有助于进一步减少资源占用。
• 动态获取距离计算函数，根据当前机器架构选择最优计算指令集，不强制要求机器规格的指令集支持。
  并且，由于采取了向量的缓存措施，所有向量都有专门的内存对齐适配，进一步优化计算指令集使用，加速索引操作。

原理介绍

Graph_Index通过构造多层图结构来近似表示数据的分布。每个节点代表一个数据点，节点间连接的线表示数据点之间的相似性或距离。通过遍历这个图，我们可以快速找到与给定数据相似的邻居。在图结构中进行最近邻查找，可以实现比聚类算法更高的查询加速比。

搜索过程

在创建索引时构建一个初始的图，然后随着向量数据的插入不断完善优化这个多层图结构，使得相似的数据点在图中更加接近。

在搜索阶段，算法从顶层的起始点开始沿着图中的边逐步扩散，直到找到足够多的近似最近邻。

1. 顶层是查询的开始层，包含较少的节点，包含最长的链接。上层充当快速到达（接近）目标位置的导航，在深入更密集的更低层进行细致搜索之前，将搜索引导到更接近目标的位置。随着搜索向下层移动，链接长度变得越来越短，顶点数量越来越多。
2. 第一次搜索其邻居点，把它们按距离目标的远近顺序存储在定长的动态列表中。之后的每一次查找，依次取出动态列表中的点，搜索其邻居点，将这些新探索的邻居点插入动态列表，每次插入动态列表时需要重新排序，保留前 N 个。如果列表有变化则继续查找，不断迭代直至达到稳态，然后以动态列表中的第一个点作为下一层的入口点，进入下一层。
3. 重复上述过程，在每一层使用贪心算法遍历完候选列表中的顶点以及它们的邻居点后，达到最底层。我们将找不到比当前顶点更近的顶点，这是一个局部最小值，也是搜索的停止条件。

多层图的构建过程

1. 在图的构建过程中，向量逐个进行插入。向量在每一层的插入的概率由一个函数决定，对于每个层（除了第 0 层），概率函数都会重复一次。将向量添加到其插入层以及下面的每一层。
2. 图的构建从顶层开始。在进入图之后，通过贪心算法遍历图，找到与我们插入的向量最近的 ef 个最近邻顶点，此时 ef = 1。
3. 在找到局部最小值（距离插入向量最近的连接顶点）之后，它转移到下一层（与搜索过程中所做的一样）。重复这个过程，直到到达我们选择的插入层。这里开始了第二阶段的构建。
4. ef 值增加到 ef_Construction（索引构建参数），意味着将返回更多的最近邻顶点。在第二阶段，这些最近邻顶点成为与新插入的元素 q 的链接的候选顶点，也是下一层的入口点。从这些候选顶点中选择M个最近邻作为链接顶点。
5. 经过多次迭代之后，当添加链接时，还会考虑参数 m（定义一个顶点可以拥有的最大链接数）。需要设置合适的 m 值以平衡搜索的召回率和性能。
6. 插入的停止条件是在第 0 层中找到局部最小值。

索引参数

索引构建参数

GUC查询参数

索引构建操作符

上述参数在索引构建阶段和向量查询阶段的具体使用方式，可参考使用示例。

使用建议

• 设置合适的 maintenance_work_mem 和 max_process_memory 值有利于索引构建速度的增快，当 maintenance_work_mem 不合适时会出现如下提示：

  NOTICE: hnsw graph no longer fits into maintenance_work_mem after XXXXX tuples  
  DETAIL: Building will take significantly more time.  
  HINT: Increase maintenance_work_mem to speed up builds
  

• 注意不要将 maintenance_work_mem 设置得太高，以免耗尽服务器的内存。
• max_process_memory 参数必须大于 maintenance_work_mem。
• 建立索引后如果数据变化（删除、更新）较多， 死元组数大于候选队列数，可能导致查询结果变少，建议每更新 40%~60% 数据重建一次索引。
• 当需要提升索引构建速度， 可以适当增大 parallel_workers，建议设置为机器CPU核数的 75% ，最大值 64。
• 当需要提升查询召回率时， 可考虑以下措施：
  • 适当增大 m，m 越大越有利于提高召回率，构建索引越慢，查询越慢，插入索引速度越慢。
  • 增大 ef_construction，ef_construction 越大越有利于提高召回率，构建索引越慢，插入索引速度越慢。
  • 增大 hnsw_ef_search，hnsw_ef_search越大，召回率越高但相应的查询延时会变高。
• 如果向量检索时，查询未按照预期走索引，请参考向量查询不走索引中介绍的内容进行排查，确认查询是否满足走索引的条件。

使用示例

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 if exists 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. 创建graph_index索引。
   • 按余弦距离构建索引：

     CREATE INDEX idx_1194690a ON t_1194690 USING graph_index(v floatvector_cosine_ops)
     WITH(m=16,ef_construction=64, parallel_workers=1);
     

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

     CREATE INDEX idx_1194690b ON t_1194690 USING graph_index(v floatvector_l2_ops)
     WITH(m=16,ef_construction=64, parallel_workers=1);
     

   • 按内积构建索引：

     CREATE INDEX idx_1194690c ON t_1194690 USING graph_index(v floatvector_ip_ops)
     WITH(m=16,ef_construction=64, parallel_workers=1);
     

     
     索引构建参数也可省略，此时参数设置为默认值：

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

4. 进行向量相似性搜索。
   设置查询参数：

   set hnsw_ef_search = 100;
   

   • 按余弦距离排序：

     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;