PostgreSQL向量数据库pgvector之ivfflat实践

前言

ChatGPT、OpenAI和大型语言模型（LLM）应用的不断普及，将近似近邻搜索（ANN）的概念推向了前沿，并由于嵌入的使用，引发了人们对向量数据库的重新关注。嵌入是短语的数学表示，它将语义捕捉为数值的向量量，鉴于嵌入通常由一千多个维度组成--OpenAI的维度为1,536，因此必须开发新的技术。目前还没有已知的精确算法可以在这样的高维空间中有效搜索。然而，有一些很好的近似算法，属于近似近邻算法的范畴。pgvector提供的ivfflat算法就是其中之一。该文将介绍如何利用postgresql和pgvector存储向量嵌入提高搜索速度的方法

工作原理

ivfflat空间划分

我们在一个二维空间中表示为以下几点的一组向量

在ivfflat算法中，第一步是对向量进行k-means聚类，找到聚类中心点。在给定向量的情况下，让我们假设我们进行k-means聚类并确定四个聚类，其中心点如下。

计算完中心点后，下一步是将每个向量分配给其最近的中心点。这是通过计算向量与每个中心点之间的距离，并选择距离最小的中心点作为最近的中心点来完成的。这个过程在概念上是将空间中的每一个点映射到基于接近度的最近的中心点，通过建立这种映射，空间被划分为围绕每个中心点的不同区域（技术上，这种划分被称为Voronoi图）。每个区域都代表一个表现出类似特征或语义接近的向量集群，这种划分能够在随后的搜索操作中有效地组织和检索近似近邻，因为同一区域的向量可能比不同区域的向量更相似。

将每个向量分配给其最接近的中心点的过程，在概念上将空间划分为围绕每个中心点的不同区域

构建ivfflat索引

Ivfflat创建一个倒排的索引，将每个中心点映射到相应区域内的向量集合。在伪代码中，该索引可以表示为

i_index = {
  c_a: [1, 2, ...],
  c_b: [3, 4, ...],
  c_c: [5, 6, ...],
  ...
}

每个中心点作为倒排索引的一个键，相应的值是属于与该中心点相关的区域的向量列表。这种索引结构允许在进行相似性搜索时有效地检索一个区域的向量

搜索ivfflat索引

想象一下，我们有一个查询，是一个黄色圈圈所代表的向量的最近的邻居，如下图所示

采用ivfflat找到近似的近邻，该算法的操作假设是：最近的向量将位于与查询向量相同的区域。ivfflat采用了以下步骤

1. 计算查询向量（黄色圈圈）与索引中每个中心点之间的距离
2. 选择距离最小的中心点作为离查询最近的中心点
3. 从倒排索引中检索与最近中心点对应的区域关联的向量
4. 计算查询向量与检索集中每个向量之间的距离
5. 选择距离最小的K个向量作为查询的近似最近的邻居

ivfflat 中索引的使用将搜索限制在与最近中心点相关的区域，从而加速了搜索过程。这导致搜索过程中需要检查的向量数量显着减少。具体来说，如果我们有 C 个聚类（中心点），平均而言，我们可以将要搜索的向量数量减少 1/C

搜索边界

假设最近的向量将在与查询向量相同的区域被找到，这可能会在ivfflat中引入召回误差

很明显，其中黄色区域的一个向量比任何比浅绿色区域的向量更接近查询向量，尽管查询向量位于浅绿色区域内。这说明了一个潜在的误差，即假设最近的向量总是在与查询向量相同的区域内找到。为了减少这种类型的误差，采用的一种方法是不仅搜索最接近的中心点的区域，而且搜索接下来最接近的中心点的区域。这种方法扩大了搜索范围，提高了找到真正近邻的几率，在pgvector中，这个功能是通过`probes`参数实现的，它指定了搜索过程中要考虑的中心点数量

ivfflat参数

在pgvector中实现ivfflat时，两个关键参数：列表和探针

列表（list）

列表参数决定了在建立索引时创建的聚类数量（之所以称为列表，是因为每个中心点在其区域内有一个向量列表）。增加这个参数可以减少每个列表中的向量数量，从而使区域更小

• 较高的列表值可通过减少查询期间的搜索空间来加快查询速度
• 它也会减小区域大小，这可能会因排除某些点而导致更多召回错误
• 在查询过程的第一步中，需要进行更多的距离比较来找到最接近的中心点

列表参数优化

对于少于一百万行的数据集，使用 lists =  rows / 1000

对于超过一百万行的数据集，使用lists = sqrt(rows)

探针(probes)

probes 参数是一个查询时参数，用于确定查询期间要考虑的区域数量。默认情况下，仅搜索与最近中心点对应的区域。通过增加probes参数，可以搜索更多的区域来提高召回率，但代价是查询速度

参数的建议值为: probes = sqrt(lists)

使用实践

创建索引

当创建一个索引时，表中最好有的数据，因为它将被K-means利用来得出聚类的中心点，pgvector中的索引提供了三种不同的方法来计算向量之间的距离： L2，内积，和余弦。在创建索引和查询操作中，必须选择相同的方法

Note:OpenAI 建议使用余弦距离进行嵌入

使用ivfflat在pgvector中创建一个索引

CREATE INDEX ON <table name> USING ivfflat (<column name> <index method>) WITH (lists = <lists parameter>);

查询

只要存在列 <查询运算符> <某些伪常量向量> 形式的 ORDER BY 以及 LIMIT k ，就可以使用索引

例如：

获取最接近常数向量的两个向量

SELECT * FROM vector_table ORDER BY embedding_column <=> '[1,2]' LIMIT 2;

数据影响

随着数据随着插入、更新和删除而变化，ivfflat 索引将相应更新。新的向量将被添加到索引中，而不再使用的向量将被删除，然而，聚类的中心点将不会被更新。随着时间的推移，这可能会导致在创建索引时建立的初始聚类不再准确地代表数据的情况 解决此问题的唯一版本就是重建索引

• 当有数据后，才构建索引，区别于传统索引
• 定期重建索引

重建索引时，可以使用 CONCURRENTLY 

REINDEX INDEX CONCURRENTLY <index name>;

总结

pgvector中的ivfflat算法为嵌入高维数据的近似近邻搜索提供了一个有效的解决方案。它的工作原理是将相似的向量聚类为区域，并建立一个倒排索引，将每个区域映射到其向量。这使得查询可以集中在数据的一个子集上，从而实现快速搜索。通过调整列表和探针参数，ivfflat可以平衡数据集的速度和准确性，使PostgreSQL有能力对复杂数据进行快速的语义相似性搜索。通过简单的查询，应用程序可以在数百万个高维向量中找到与查询向量最近的邻居。对于自然语言处理、信息检索等，ivfflat是一个比较好的解决方案。