VectorChord重磅发布: 支持图(DiskANN和HNSW)索引、召回率评估

VectorChord重磅发布: 支持图(DiskANN和HNSW)索引、召回率评估

VectorChord 更新了, 这次更新迎来了2个大特性:

• 基于图(DiskANN和HNSW)的索引, 索引可超越内存大小
• 内置召回率评估函数

如果你还不太了解VectorChord, 也可以先翻一翻我之前写的文章

• 《VectorChord 向量插件学习心得》
• 《向量插件新贵 VectorChord(IVF+ RaBitQ量化), pgvector 和 milvus 都被秒杀了》

或者直接看其开源项目或文档

• https://github.com/tensorchord/VectorChord
• https://docs.vectorchord.ai/vectorchord/usage/graph-index.html
• https://deepwiki.com/tensorchord/VectorChord

以及一些图索引相关的论文和原理介绍文章

• 《数据库筑基课 - 向量索引之 HNSW》
• 《pgvector hnsw高频更新场景的坑》
• 《AI论文解读 | Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs》
• 《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》
• 《pgvectorscale: pgvector diskann 向量索引扩展与优化》
• 《TimescaleDB 发布基于DiskANN的增强向量索引》
• 《一种新的向量检索索引 DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node》

本文来看看 VectorChord 基于图(DiskANN和HNSW)的索引与pgvector有什么不一样?

内置召回率评估函数如何使用?

一、VectorChord graph index for vector type

VectorChord 的索引类型vchordg是基于磁盘的图索引，内存消耗较低。

创建一个名为items的索引, embedding的列类型为vector(n)。

要创建vchordg索引，可以使用以下 SQL。

CREATE INDEX ON items USING vchordg (embedding vector_l2_ops);  

注意: vchordg索引功能目前处于预览阶段。

调优

建立索引时，通常需要调整两个选项：m和ef_construction。m是每个顶点的最大邻居数，ef_construction是插入数据期间顶点包含最近邻居的动态列表的大小(通常比m大, 随着插入过程更新这个动态列表, 以构建更好的图.)。

在搜索(query)时，您需要调整ef_search。ef_search是搜索期间包含最近邻居的动态列表的大小。

CREATE INDEX ON items USING vchordg (embedding vector_l2_ops) WITH (options = $$  
m = 64  
ef_construction = 128  
$$);  

SET vchordg.ef_search TO '128';  
SELECT * FROM items ORDER BY embedding <-> '[3,1,2]' LIMIT 10;  

作为基于磁盘的索引，vchordg通常只需要将量化向量保留在buffer池中即可保持性能。默认情况下，vchordg量化D维向量为2D位。设行数为N。那么，索引所需的总内存为2DN位。如果你的内存非常有限，并且正在使用超高维向量，可以考虑将向量量化为D位。那么，索引所需的总内存为DN位。

CREATE INDEX ON items USING vchordg (embedding vector_l2_ops) WITH (options = $$  
bits = 1  
m = 64  
ef_construction = 128  
$$);  

可以使用多个进程来加速索引构建。请参阅调优( https://docs.vectorchord.ai/vectorchord/usage/performance-tuning.html#indexing )。

参考

操作符类(ops)

下表列出了vchordg所支持的所有可用运算符类。

<<->>，<<#>>，<<=>>是VectorChord插件定义的运算符。

有关<<->>、<<#>>、<<=>>的更多信息，请参阅( https://docs.vectorchord.ai/vectorchord/usage/range-query.html )。

索引选项

bits

• 描述：RaBitQ量化后的比特与维度的比率。bits = 2提供更好的召回率，bits = 1消耗更少的内存, 提供更高的QPS。
• 类型：整数
• 默认：2
• 例子：
• bits = 2意味着D维向量量化为2D位(bit)。
• bits = 1意味着D维向量量化为D位(bit)。

m

• 描述：每个顶点的最大邻居数。m值越大，召回率越好，但存储需求也越高。
• 类型：整数
• 默认：32
• 例子：
• m = 32意味着每个顶点的邻居最多有32个。
• m = 64意味着每个顶点的邻居最多有64个。

ef_construction

• 描述：插入过程中包含最近邻居的动态列表的大小。ef_construction值越大，召回率越好，但插入速度越慢。
• 类型：整数
• 默认：64
• 例子：
• ef_construction = 64意味着插入过程中包含最近邻居的动态列表的大小是64。
• ef_construction = 128意味着插入过程中包含最近邻居的动态列表的大小是128。

alpha

• 描述：alpha是剪枝期间选择的值。此选项必须是一个升序列表，其中第一个元素为1.0，最后一个元素小于2.0。
• 类型：浮点数列表
• 默认：[1.0, 1.2]
• 例子：
• alpha = [1.0, 1.2]相当于在DiskANN中设置alpha = 1.2。
• alpha = [1.0]相当于HNSW中的默认剪枝策略。
• 注意：当距离度量为负内积(negative inner product)时此选项无效。

beam_construction

• 描述：插入期间使用的束宽度。束宽度指的是一次访问的顶点数量。由于从 SSD 随机读取少量扇区的时间与读取单个扇区的时间几乎相同，因此较大的束宽度可以有效减少往返 SSD 的次数，从而提高性能。由于这会增加计算量，因此对于已完全加载到内存中的索引而言是不利的。
• 类型：整数
• 默认：1
• 例子：
• beam_construction = 8表示索引在插入时一次访问 8 个顶点。
• beam_construction = 1表示索引在插入过程中一次访问 1 个顶点。

搜索参数

vchordg.ef_search

• 描述：搜索时最近邻居的动态列表的大小。vchordg.ef_search值越大，召回率越高，但 QPS 越低。
• 类型：整数
• 默认：64
• 领域：[1, 65535]
• 例子：
• SET vchordg.ef_search = 64表示在搜索过程中包含最近邻居的动态列表的大小是64
• SET vchordg.ef_search = 128表示在搜索过程中包含最近邻居的动态列表的大小是128

vchordg.beam_search

• 描述：搜索过程中使用的束宽度。束宽度指的是一次访问的顶点数量。由于从 SSD 随机读取少量扇区的时间与读取单个扇区的时间几乎相同，因此较大的束宽度可以有效减少往返 SSD 的次数，从而提高性能。由于这会增加计算量，因此对于已完全加载到内存中的索引而言是不利的。
• 类型：整数
• 默认：1
• 领域：[1, 65535]
• 例子：
• SET vchordg.beam_search = 8表示索引在搜索时一次访问 8 个顶点。
• SET vchordg.beam_search = 1表示索引在搜索时一次访问 1 个顶点。

二、内置召回率评估函数

在向量搜索的语境中，召回率是指索引返回的真实最近邻与近似最近邻的比率。例如，如果索引检索到100个近似最近邻, 其中97个是真正的最近邻，那么召回率就是97/100。

召回率衡量的是相关结果占搜索结果总数的比例。使用索引时，您可能希望了解不同参数对应的召回率和每秒查询次数 (QPS)。函数vchordrq_evaluate_query_recall旨在评估召回率。它接收一个返回行标识符的查询，并返回相应的召回率。

SET vchordrq.probes = '100';  
SET vchordrq.epsilon = 1.0;  
SELECT vchordrq_evaluate_query_recall(query => $$  
  SELECT ctid FROM items ORDER BY embedding <-> '[3,1,2]' LIMIT 10);  
$$);  

默认情况下，该函数通过使用索引扫描生成估计的 ground truth 来评估召回率。如果您想通过 table seq scan 生成 ground truth 来评估召回率，请将函数exact_search参数设置为true。

SET vchordrq.probes = '100';  
SET vchordrq.epsilon = 1.0;  
SELECT vchordrq_evaluate_query_recall(query => $$  
  SELECT ctid FROM items ORDER BY embedding <-> '[3,1,2]' LIMIT 10  
$$, exact_search => true);  

参考

vchordg 索引暂时不支持此功能。

vchordrq 索引 vchordrq_evaluate_query_recall 函数说明

• 描述：评估给定vchordrq索引扫描查询的召回率。
• 结果：real
• 参数：
• query: text，评估召回率的query
• exact_search: boolean，使用真实情况而不是估计的真实情况
• accu_probes: text，vchordrq.probes 的估计真实值
• accu_epsilon: real，vchordrq.epsilon 的估计真实值
• 例子：
• SELECT vchordrq_evaluate_query_recall(query => $$ SELECT ctid FROM t ORDER BY val <-> '[0.5, 0.25, 1.0]' LIMIT 10 $$);
• SELECT vchordrq_evaluate_query_recall(query => $$ SELECT ctid FROM t ORDER BY val <-> '[0.5, 0.25, 1.0]' LIMIT 10 $$, exact_search => true);
• SELECT vchordrq_evaluate_query_recall(query => $$ SELECT ctid FROM t ORDER BY val <-> '[0.5, 0.25, 1.0]' LIMIT 10 $$, accu_probes => '9999', accu_epsilon => 4.0);

参考

https://docs.vectorchord.ai/vectorchord/usage/graph-index.html

https://docs.vectorchord.ai/vectorchord/usage/measure-recall.html