为什么VectorChord比pgvector更好?
digoal约 10 分钟为什么VectorChord比pgvector更好?
这是我用deepwiki读完的第三个开源项目，逐渐有种文档工程师已死的感觉！
进入正文。
回顾这篇文章提到pgvector的hnsw坑: 《pgvector hnsw高频更新场景的坑》
VectorChord 采用了另一种类ivfflat的结构, 解决了hnsw在高频更新后的维护难、召回下降、内存消耗多问题, 同时解决了ivfflat召回精度低的问题.
如果你要在PostgreSQL中使用向量存储和搜索, 并且你的场景不适合hnsw的话, 不妨考虑 VectorChord.
最近使用把deepwiki的VectorChord仔细的看了一遍, 总结以下学习心得. 同时也非常感谢VectorChord CEO CTO以及几位创始团队成员的答疑解惑. 期待这个插件的最新进展.
VectorChord 的架构和特性
架构类似ivfflat. 需要先根据已有数据算出聚集中心点, 然后把向量插入最近的聚集中心点. 搜索时也是先找到离被搜索向量最近的若干聚集中心点, 然后以这些聚集点下的所有向量作为候选向量, 再进行rank或返回.
改进之处在于:
聚集分层, 类似分区表. 但是聚集点不多的话, 从所有聚集点提取TOP N最近聚集点并不是瓶颈, 所以分区可能对性能提升不明显. 非平衡聚集. 这个可能不算改进点, k-means都是非平衡聚集, 也就是不是按标准距离划网格来生成聚集点. build 阶段, 可配置聚集层数、聚集点数以及每个聚集点采样多少条, 可配置k-means迭代次数. 非常灵活, 有利于构造召回率、性能平衡的索引. 支持采用外部计算的聚集点build index, 可利用GPU提升聚集点计算效率、可扩展聚集点算法(采用相较k-means更优的聚集算法). 残差量化. 聚集点采用原始向量存储, 叶子结点采用tuple vector与聚集点的残差, 并对残差进行量化存储. 更加节省内存, 并在保证召回率的情况下提升性能. rerank, 支持index rerank和table rerank. index rerank采用残差和聚集点回溯后rank(提供优秀的召回率和性能), table rerank回表使用tuple vector进行rank(提供最好的召回率). prefilter, 这个pgvector新版本也支持了, 在返回result前使用filter条件进行过滤. 注意需要回表获取其他filter字段值进行过滤. 保证更好的return. 限制召回. 通过参数控制最多选择多少条候选向量, 从而在保证召回率的情况下, 提升查询效率. 更适合SIMD的紧凑存储结构. 采用更适合现代CPU批量值运算指令集的数据结构, 对残差量化值进行compact存储. 在build index的最后阶段进行compact.
同时增加了以下功能
相比32bit vec和16bit halfvec, 增加8bit scalar vector类型. 在相比binary保留更好精度的同时压缩存储. vec array @#query vec arr操作符. 适合多向量数组近似搜索.预热, 支持预热向量表到内存中. 在内存足够, 并且需要进行高频且大范围的向量搜索时可以先进行预热.
更多细节请自行发现.
https://deepwiki.com/tensorchord/VectorChord/
VectorChord 的核心
来自 https://blog.vectorchord.ai/why-hnsw-is-not-the-answer
量化：游戏规则改变者
量化将高维向量压缩为紧凑的表示。例如：
RaBitQ：利用测量现象的集中来增强二进制和标量量化精度，将每个维度量化为 1 位，实现 32 倍压缩比。 乘积量化 (PQ)：通过将向量空间划分为子空间，并独立量化每个子空间以最小化近似误差。该方法在 FAISS 中提供从 4 倍到 64 倍的灵活压缩比，从而实现更精细的压缩和更快的近似搜索。 标量量化（SQ）：通过将向量范围划分为离散级别来独立量化每个向量维度，通常通过从浮点数转换为 int8 来实现 4 倍压缩比。 ScaNN：使用各向异性矢量量化来优化内积准确率，通过惩罚影响高内积的方向的错误，实现卓越的召回率和速度。
量化显著减少了内存和磁盘空间的使用——在将浮点数转换为位时，通常可节省 32 倍——同时大幅降低计算开销。尽管会损失一些精度，但量化使向量比较更加高效。例如，通过将浮点数压缩为位，复杂度可降低 32 倍。此外，二进制运算通常比浮点运算更高效，从而进一步提升性能。借助快速扫描优化，这些计算可以通过高效的 CPU 寄存器查找得到进一步加速。结合 IVF，许多量化方法在速度和可扩展性方面均优于 HNSW。典型的工作流程包括：
初始搜索：利用压缩表示快速识别候选向量。 重新排序：使用全精度距离计算对较小的候选子集进行优化结果。
VectorChord 的一些细节解答
1、build index时, 如何控制聚集点的层级、每层聚集点的数量.
lists是个数组, 控制层次以及每一层的中心点个数: [22,100,2000]，第一层是22，第二层是100，第三层是2000.
CREATE INDEX ON items USING vchordrq (embedding vector_l2_ops) WITH (options = $$
residual_quantization = true
[build.internal]
lists = [22,100,2000]
build_threads = 4
$$);
-- 只有一层就写一个值, 例如:
lists = [2000]
2、查询时, 如何控制每个层级搜索的聚集点数量?
SET vchordrq.probes = '4,8,16'; -- Try multiple probe counts
表示每个层级搜索的top-n 聚集点数量. 最终叶子结点里的vec作为候选vec.
该参数控制每一层搜索的 cluster 数量，数值越大，搜索越全面但性能可能降低；数值越小，搜索越快但可能影响结果质量。在实际应用中，可以根据需要平衡查询速度和结果质量来设置这个参数。
最初我误以为是先搜索4个叶子cluster, 如果候选vec满足limit数就不继续, 否则将继续扩搜到8个cluster. 这个思路我在gin索引的相似阈值搜索场景优化中使用过, 非常有效:
《PostgreSQL 相似搜索设计与性能 - 地址、QA、POI等文本 毫秒级相似搜索实践》
3、查询时, 限制候选条数.
除了采用probes控制聚集点数, 还可以通过vchordrq.max_scan_tuples控制候选向量数, 最多扫描这么多个向量. 在数据量特别大时可以使用, 提升性能, 牺牲召回率.
4、maxsim 搜索操作（使用 @# 操作符）算法
对于向量数组中的每个向量, 计算与tuple vec arry中的最小相似度. 可以理解为2个数组的笛卡尔乘机运算.
将最小相似度相加得到maxsim.
order by maxsim. 得到集合相似度top-n.
5、查询时, 向量数组搜索(maxsim 搜索)中的 限制候选条数.
vchordrq.maxsim_refine , Number of candidates to refine when using maximum similarity searches.
vchordrq.maxsim_refine 是一个配置参数，用于控制在使用最大相似度（maxsim）搜索时要精确重排的候选项数量。具体来说，它指定了对于查询数组中的每个查询元素，从索引中召回的候选元组（tuples）中有多少个需要进行精确重排（refine）。
在 VectorChord 中，maxsim 搜索是一种特殊的搜索方法，用于计算多个向量之间的最大相似度。当执行 maxsim 搜索时，系统会：
对查询数组中的每个向量元素执行搜索 从索引中召回一批候选元组 根据 vchordrq.maxsim_refine参数，选择前 N 个候选元组进行精确重排
默认值为 0，表示不进行精确重排
当 maxsim_refine 不为 0 且结果不为空时，系统会：
使用 algorithm::rerank_index 创建一个重排器 从重排器中取出前 maxsim_refine 个结果进行精确重排 剩余的结果保持原始排序
这个参数的作用是在保持搜索效率的同时提高结果的准确性。通过只对前 N 个候选项进行精确重排，可以在性能和准确性之间取得平衡。
vchordrq.maxsim_threshold 在搜索过程中，该参数作为阈值使用，用于过滤掉相似度低于此阈值的结果。当两个向量集合之间的最大相似度（maxsim）低于设定的阈值时，这些结果将被排除。
当执行 maxsim 搜索时，系统会：
从查询中获取 maxsim_threshold 参数值 计算向量集合之间的最大相似度 使用 maxsim_threshold 过滤结果，只返回相似度高于阈值的结果
使用场景, vchordrq.maxsim_threshold 参数在以下场景特别有用：
过滤低相关性结果：设置较高的阈值可以过滤掉相似度较低的结果，只保留高度相关的匹配项 性能优化：通过设置适当的阈值，可以减少需要处理的结果数量，提高查询性能 精度控制：根据应用需求调整阈值，在召回率和精确度之间取得平衡
注意事项
maxsim_threshold 的值应根据您的数据分布和应用需求进行调整 设置过高的阈值可能会过滤掉太多结果，导致召回率下降 设置过低的阈值可能会返回太多不相关的结果，影响精确度 该参数的最佳值通常需要通过实验确定
6、build index时 residual_quantization = true 这个参数的意思是启用残差量化.
centerID 存原始精度向量值, 对应聚集的叶子结点里存储与centerID的偏移量之后的量化值.
减少内存使用, 同时精度几乎无损.
CTO的解答:
residual quantization是指对每个向量d，对应的centroid c，我们针对 (d-c)这个向量做quantize，而不是针对 d 这个向量.
这个我们也还在做实验，rabitq原始论文是用residual quantization的，但是我们之前实验是不开这个选项性能也差不多或者更快，最近有个新的实现，会再测试一下.
关注进展, 期待新的实现.
7、build index的最后一个阶段 Compacting Index: Optimizing storage, 这个过程怎么理解呢?
CTO的解答:
compacting index是一个实现的细节，在批量计算quantized向量距离的时候，有个fastscan的技术，能比一个一个bit 向量算距离快4-5x，但是需要32个bit向量一组，整理成一个特殊的格式
https://github.com/facebookresearch/faiss/wiki/Fast-accumulation-of-PQ-and-AQ-codes-(FastScan
所以我们在插入的时候会先在page中简单的append每个bit向量，然后在compacting index/vacuum的时候，把这部分向量重整成fastscan需要的格式
8、使用external build index时( python script/index.py -n laion -i laion-5m-test-ip.hdf5 -c centroids.npy -m dot -d 768 --url postgresql://postgres:password@localhost:5432/postgres ), 是外部工具直接写索引文件吗? 然后修改PG的元数据挂载到相应索引下? 建立索引时是否会使用锁? 是和currently一样的吗? 如何保证增量的正确性?
使用外部脚本build index, 还是会封装成create index的SQL来创建索引.
外部工具只是生成cluster point更灵活、高效、有效. 因为可以选择更好的算法, 可以使用GPU.
build index时, 使用导入到数据库中的center id table. 免去在数据库中使用k-means算center id的过程.
9、vchordrq.epsilon Controls the approximation factor. 请问vchordrq.epsilon的含义和详细算法.
vchordrq.epsilon 是 VectorChord 中的一个重要配置参数，用于控制向量搜索的近似因子。
vchordrq.epsilon 控制向量搜索的近似程度，它影响搜索结果的精确度和性能之间的平衡。较大的 epsilon 值会使搜索更快但可能降低结果的准确性，而较小的值会提高准确性但可能降低性能。
在代码中，vchordrq.epsilon 被定义为一个浮点型 GUC (Grand Unified Configuration) 参数，默认值为 1.9
在 VectorChord 的搜索算法中，epsilon 参数被用于控制搜索的近似程度。它通过 gucs.rs 中的 epsilon() 函数暴露给搜索算法
算法原理:
VectorChord 使用的是基于残差量化 (Residual Quantization) 的近似最近邻搜索算法。在这种算法中，epsilon 参数控制搜索空间的扩展程度。
具体来说，epsilon 值越大，算法会探索更广泛的搜索空间，可能会找到更多的候选结果，但也会增加计算开销。相反，较小的 epsilon 值会限制搜索空间，提高搜索速度，但可能会错过一些潜在的好结果。
在实际应用中，epsilon 参数需要根据具体的数据集和应用需求进行调整，以在搜索质量和性能之间找到最佳平衡。
10、vchordrq.prewarm_dim '64,128,256,384,512,768,1024,1536' Vector dimensions to prewarm when the extension loads.
When VectorChord loads, it reads the comma-separated list of dimensions from vchordrq.prewarm_dim, parses each value into an integer, and uses these values to determine which indexes to prewarm.
The prewarming process itself is implemented in crates/algorithm/src/prewarm.rs and is exposed through the vchordrq_prewarm function, which loads index data into memory to improve initial query performance.
The prewarming functionality is especially important for vector search applications where cold-start latency can be problematic.
The default dimensions (64, 128, 256, 384, 512, 768, 1024, 1536) cover common embedding dimensions used in various machine learning models.
Usage
You can modify this parameter in your PostgreSQL configuration:
-- In postgresql.conf
vchordrq.prewarm_dim = '128,256,512,1024'
-- Or at runtime
SET vchordrq.prewarm_dim = '128,256,512,1024';
This is particularly useful for:
Services that need low latency from the start After database restarts Before running batch operations
参考
https://deepwiki.com/tensorchord/VectorChord/
https://blog.vectorchord.ai/why-hnsw-is-not-the-answer
《向量插件新贵 VectorChord(IVF+ RaBitQ量化), pgvector 和 milvus 都被秒杀了》