向量数据库主要用于支持高效的向量检索场景(以图搜图、以文搜图等),通过本次培训可以掌握向量数据库的核心理论以及两种向量索引技术的特点、场景与算法原理,并通过实战案例掌握向量数据库的应用与性能优化策略。
一、原理篇:向量数据库基础理论
简介
在现实世界中,绝大多数的数据都是以非结构化数据的形式存在的,如图片,音频,视频,文本等。为了能够处理这些非结构化数据,通常会使用人工智能技术提取这些非结构化数据的特征,并将其转化为特征向量,再对这些特征向量进行分析和检索以实现对非结构化数据的处理。因此,将能存储、分析和检索特征向量的数据库称之为向量数据库。
向量数据库使用向量索引技术来实现对特征向量的快速检索。向量索引通常属于近似最近邻搜索(Approximate Nearest Neighbors Search,ANNS)范畴。其核心思想是不是仅仅返回最精确的结果项,而是只搜索可能是近邻的数据项,以提高检索效率。通过在可接受范围内牺牲一定的精确度,实现了向量数据库与传统数据库的显著区别。
功能
- 存储向量类型数据(特征向量)。
- 高维向量相似度匹配搜索。
应用场景
- 以图搜图服务,即通过图片检索图片的应用服务。
- 视频检索服务,即通过视频中的某些帧图片进行视频图片检索,来实现视频检索。
- 声纹检索服务,即通过音频匹配音频的应用服务。
- 推荐系统服务,即通过用户特征匹配实现推荐匹配的功能。
- 基于语义的文本检索和推荐,通过文本检索近似文本。
- 问答机器人,通过与大模型结合搭建高效的问答机器人服务。
- 文件去重,通过文件指纹特征来去除重复文件。
概念
相似度与距离
- 余弦距离,使用
vector_cosine_ops
<=>
余弦距离+余弦相似度=1
- 欧氏距离,使用
vector_l2_ops
<->
- 内积相似,使用
vector_ip_ops
<#>
在 PostgreSQL 中,当使用基于索引的查询时,索引扫描的方向通常只能按照升序(ASC)进行。这是因为大多数索引类型(如 B-tree)默认支持升序排序,而降序(DESC)扫描通常需要反向遍历索引树,这在效率上不如升序扫描。
内积越大表示越相似,所以使用负的内积(negative inner product)作为索引查询的依据,更小的(更相似)排在前面。
嵌入
嵌入(embedding)是指将高维数据映射为低维表示的过程。在机器学习和自然语言处理中,嵌入通常用于将离散的符号或对象表示为连续的向量空间中的点。
在自然语言处理中,词嵌入(word embedding)是一种常见的技术,它将单词映射到实数向量,以便计算机可以更好地理解和处理文本。通过词嵌入,单词之间的语义和语法关系可以在向量空间中得到反映,如Word2Vec。
Word2Vec:https://code.google.com/archive/p/word2vec/
召回率
召回率衡量的是模型识别出的真正例(True Positives, TP)占所有实际正例(Actual Positives, AP)的比例。换句话说,召回率反映了模型识别出所有相关项目的能力。
召回率不同,在图像检索中体现方式是返回的图像不一样:
a.
b.
精确检索/近似索引检索
精确检索
完全按照相似度距离排序的暴力搜索。此方式需要比较每一个向量,因此它的搜索速度较慢,但是召回率可以达到百分之百。
近似的索引检索
通过使用索引的方式进行搜索,此方式搜索速度较快,但得到的结果是一个近似的结果。
近似最近邻(Approximate Nearest Neighbor,简称ANN)搜索算法
在机器学习领域,语义检索,图像识别,推荐系统等方向常涉及到的一个问题是:给定一个向量X=[x1,x2,x3...xn],需要从海量的向量库中找到最相似的前K个向量。通常这些向量的维度很高,对于在线服务,用传统的方法查找是非常耗时的,容易使得时延上成为瓶颈,因此业界通用的方式就是将最相似的查找转换成Ann问题。
这样查找返回的前K个向量并不一定是最相似的K个向量,衡量Ann算法好不好的一个依据是召回,每次Ann请求返回的K个结果与使用暴力查找的K个结果去比较,如果完全一致,说明是最好的。因为省了搜索时间却没有影响效果。
目前的Ann算法有基于图的,基于树的,基于哈希等,并且有很多关于Ann算法的实现。
- 树方法,如 KD-tree
- 哈希方法,如 Local Sensitive Hashing (LSH)
- 图方法,如 Hierarchical Navigable Small World (HNSW)
向量索引
HNSW(Hierarchical Navigable Small World)
HNSW 索引会创建多层图。它的查询性能比 IVFFlat 更好,但构建时间较慢且占用更多内存。此外,由于没有像 IVFFlat 那样的训练步骤,因此可以在没有任何数据的情况下创建索引。
m,ef_search |
16,64(原始) |
32,250 |
32,500 |
1536维随机向量 10万条数据 max_parallel_maintenance_workers = 4 maintenance_work_mem = '7GB' |
3min 26s 415ms |
22min 11s 192ms |
33min 16s 110ms |
HNSW算法适合超大规模的向量数据集(千万级别以上),并且对查询延时有严格要求(10ms级别)的场景。
HNSW基于近邻图的算法,通过在近邻图快速迭代查找得到可能的相近点。在大数据量的情况下,使用HNSW算法的性能提升相比其他算法更加明显,但邻居点的存储会占用一部分存储空间,同时召回精度达到一定水平后难以通过简单的参数控制来提升。
HNSW的算法原理请参见下图:
算法流程说明:
- 构造多层图,每层图都是下层图的一个缩略,同时构成下层图的跳表,类似高速公路。
- 从顶层随机选中一个点开始查询。
- 第一次搜索其邻居点,把它们按距离目标的远近顺序存储在定长的动态列表中,以后每一次查找,依次取出动态列表中的点,搜索其邻居点,再把这些新探索的邻居点插入动态列表,每次插入动态列表需要重新排序,保留前k个。如果列表有变化则继续查找,不断迭代直至达到稳态,然后以动态列表中的第一个点作为下一层的入口点,进入下一层。
- 循环执行第3步,直到进入最底层。
原理
SW:
同质性:同质性也就是相似的点会聚集到一起,相互连接具有邻接边。
弱连接:弱连接是指从每一个节点上,会有一些随机的边随机连接到网络中的节点上,这些节点是随机均匀的。
NSW:
在NSW算法中通过构建一个小世界网络,希望通过黑色相似的近邻边来检索最近邻节点, 通过红色长边(高速公路)来实现不同类节点之间的快速检索
NSW的局部节点之间的在距离上具有同质性(也就是近邻节点能够相互连接)。从而使得当我们检索到一个近邻节点时,其大部分近邻节点都是近邻节点。同时也希望保留一些随机边,能够在不同区域之间快速跳转
近似kNN搜索
执行m次贪婪搜索,在每次搜索过程中随机选择一个进入点遍历,最后从m次搜索选出距离查询点最近的k个结果。
- 随机选择1个元素,放入到candidates当中
- 从candidates中选取最近邻节点c,将这些元素的邻居节点放置到q当中
- 从candidates中移除最近邻节点c
- 如果c的距离远大于result中的第k个节点,跳出循环
- 否则,对于c的每个邻居节点,遍历其邻居,如果没有在visited set里面。
- 将e加入到visited set, candidates, tempRes
- 遍历完成candidate中所有的节点后,把tempRes的结果传入到result
- 重复执行上述步骤m遍, 返回result中最优的k个近邻结果。
数据插入算法
通过逐个插入元素方式进行构图,对于每个待插入元素,通过近似kNN算法查找与其最近的f个元素,然后与其相连。
HNSW:
继承NSW基于long link快速检索,short link具有聚类特性的思想。怎么样能够使得查找更为稳定, 或者怎么样能够把long link的查找和short link查找有效区分。在此基础上引入了分层图的思想。
将节点划分成不同层级,贪婪地遍历来自上层的元素,直到达到局部最小值,然后切换到下一层,以上一层中的局部最小值作为新元素重新开始遍历,直到遍历完最低一层。
与NSW相比,HNSW的改进方法:
- 使用分层的结构
- 使用了一种启发式方法选择某节点的邻居。
建图
上图为HNSW算法的建图流程,其中红色节点代表待插节点,绿色表示已插入节点。
(1)输入建立索引所需的参数,设M=2,即每个元素最大连接2个结点;
(2)获取用于建图的所有图片,并依次传入算法中建立索引;
(3)对输入的图片提取特征;
(4)将特征当作节点,并获取节点的层次l(随机分配);
(5)插入节点,对于第一个插入的节点,不做任何操作
(6)插入第二个节点:
① 在L层找到距离待插节点最近的节点ep,并作为下一层的输入;
② 该层及以下为待插元素的插入层,从ep开始查找距离待插元素最近的ef个节点,从ef节点中选出M个与待插节点连接,并将这M个节点作为下一层的输入;
③从M个节点开始搜索,找到距离与待插节点最近的ef个节点,并选出M个与待插元素连接;
④ 同③。
(7)插入第三个节点:
① 在L层找到距离待插节点最近的节点ep,并作为下一层的输入;
② 在l=2层找到距离待插节点最近的节点ep,并作为下一层的输入;
③ 该层及以下为待插元素的插入层,从ep开始查找距离待插元素最近的ef个节点,从ef节点中选出M个与待插节点连接,并将这M个节点作为下一层的输入;
④同③。
搜索
其中红色的节点表示搜索节点q(可以是非图中的节点),绿色节点表示图中已建立的节点,黄色的节点表示搜索结果。
(a)输入索引路径和图片;
(b)根据索引路径加载索引,并对图片提取特征;
(c)获取需要搜索的近邻数K,并将图片特征作为节点输入搜索算法;
(d)在L层找到距离q最近的一个节点ep,并作为下一层的输入;
(e)在l=2层中,从ep开始,在ep的邻居中找到距离q最近的一个邻居,作为新的ep,并作为下一层的输入;
(f)在l=1层中,从ep开始,在ep的邻居中找到距离q最近的一个邻居,作为新的ep,并作为下一层的输入;
(g)在最底层中,从ep开始,搜索距离q最近的K个节点;
(h)输出节点q和K个近邻。
参考资料:
https://zhuanlan.zhihu.com/p/441470968
https://zhuanlan.zhihu.com/p/264832755
IVFFlat(Inverted File Flat)
IVFFlat 索引将向量划分为列表,然后搜索最接近查询向量的列表子集。与 HNSW 相比,它的构建时间更快,占用的内存更少,但查询性能较低。
lists参数表示将数据集分成的列表数,该值越大,表示数据集被分割得越多,每个子集的大小相对较小,索引查询速度越快。但随着lists值的增加,查询的召回率可能会下降。
IVFFlat是IVFADC(Asymmetric Distance Computation, 不对称距离计算)的简化版本,适合于召回精度要求高,但对查询耗时要求不严格(100ms级别)的场景。相比其他算法,IVFFlat算法具有以下优点:
- 如果查询向量是候选数据集中的一员,那么IVFFlat可以达到100%的召回率。
- 算法简单,因此索引构建更快,存储空间更小。
- 聚类中心点可以由使用者指定,通过简单的参数调节就可以控制召回精度。
- 算法参数可解释性强,用户能够完全地控制算法的准确性。
算法流程说明:
- 高维空间中的点基于隐形的聚类属性,按照kmeans等聚类算法对向量进行聚类处理,使得每个类簇有一个中心点。
- 检索向量时首先遍历计算所有类簇的中心点,找到与目标向量最近的n个类簇中心。
- 遍历计算n个类簇中心所在聚类中的所有元素,经过全局排序得到距离最近的k个向量。
注:
- 在查询类簇中心点时,会自动排除远离的类簇,加速查询过程,但是无法保证最优的前k个向量全部在这n个类簇中,因此会有精度损失。可以通过类簇个数n来控制IVFFlat算法的准确性,n值越大,算法精度越高,但计算量会越大。
- IVFFlat和IVFADC的第一阶段完全一样,主要区别是第二阶段计算。IVFADC通过积量化来避免遍历计算,但是会导致精度损失,而IVFFlat是暴力计算,避免精度损失,并且计算量可控。
参考资料:
https://blog.51cto.com/molu2013/6655707
https://www.modb.pro/db/1694305431241969664
二、源码分析篇:深入pgvector
待补充
三、实战篇:案例与性能优化
图像检索系统开发
- 下载CIFAR100数据集并预处理
- 包括调整大小、中心裁剪、转换为张量和归一化
import torch import torchvision from torchvision.transforms import ( Compose, Resize, CenterCrop, ToTensor, Normalize ) preprocess = Compose([ Resize(256), CenterCrop(224), ToTensor(), Normalize(mean=[0.485, 0.456, 0.406], std=[0.229, 0.224, 0.225]), ]) DATA_DIRECTORY = "/Users/shangwenkai/Desktop/vector/CIFAR" datasets = { "CIFAR100": torchvision.datasets.CIFAR100(DATA_DIRECTORY, transform=preprocess, download=True) }
- 使用SqueezeNet1_1模型生成特征向量
- 预训练模型,置为评估模式。
# 准备数据。 BATCH_SIZE = 100 dataloader = torch.utils.data.DataLoader(dataset, batch_size=BATCH_SIZE) # 下载模型。 # 预训练的SqueezeNet1_1模型,并将其设置为评估模式。在评估模式下,模型不进行梯度计算,这对于特征提取是必要的,因为不需要反向传播 model = torchvision.models.squeezenet1_1(pretrained=True).eval() # 提取特征向量,写入features_file_path。 features_file_path = "/Users/shangwenkai/Desktop/vector/features" feature_file = open(features_file_path, 'w') img_id = 0 for batch_number, batch in enumerate(dataloader): #每次处理100 with torch.no_grad(): #禁用梯度 batch_imgs = batch[0] # 0: images batch_labels = batch[1] # 1: labels vector_values = model(batch_imgs).tolist() #对batch_imgs进行前向传播,得到每个图像的特征向量,然后将这些特征向量从Tensor转换为Python列表。 #SqueezeNet模型的输出是一个形状为(batch_size, output_dim)的二维Tensor for i in range(len(vector_values)): img_label = dataset.classes[batch_labels[i].item()] # print(img_label) feature_file.write(str(img_id) + "|" + img_label + "|") vector_value = vector_values[i] assert len(vector_value) == 1000 for j in range(len(vector_value)): if j == 0: feature_file.write("{") feature_file.write(str(vector_value[j]) + ",") elif j == len(vector_value) - 1: feature_file.write(str(vector_value[j])) feature_file.write("}") else: feature_file.write(str(vector_value[j]) + ",") feature_file.write("\n") img_id = img_id + 1 print("finished extract feature vector for batch: ", batch_number) feature_file.close()
- RDS PostgreSQL配置扩展pgvector
- 建表,导入特征向量到数据库,建索引
PostgreSQL 提供了多种存储方式来处理大字段,包括向量列。对于向量列,可以选择以下几种存储方式之一:
PLAIN
防止压缩或行外存储。这是对不可TOAST数据类型的列唯一可行的策略。EXTENDED
允许压缩和行外存储。这是大多数可TOAST数据类型的默认设置。将首先尝试压缩,如果行仍然太大,则尝试行外存储。EXTERNAL
允许行外存储但不允许压缩。使用EXTERNAL
将使宽text
和bytea
列上的子字符串操作更快(但会增加存储空间),因为这些操作经过优化,在未压缩时仅获取行外值的所需部分。MAIN
允许压缩但不允许行外存储。(实际上,对于此类列,仍将执行行外存储,但只有在没有其他方法使行足够小以适合页面时才作为最后的手段。)
对于1500维的向量,如果每个维度的数据类型不是特别大,可以考虑使用 PLAIN
存储方式。这种方式可以提高查询性能,因为数据直接存储在行中,无需额外的 TOAST 指针解析。
import os import psycopg2cffi connection = psycopg2cffi.connect( host=os.environ.get("PGHOST", "pgm-bp16r2431088910yno.pg.rds.aliyuncs.com"), port=os.environ.get("PGPORT", "5432"), database=os.environ.get("PGDATABASE", "face_ai"), user=os.environ.get("PGUSER", "zhongchi"), password=os.environ.get("PGPASSWORD", "Ssaa1776") ) cursor = connection.cursor() drop_table_sql = """ drop TABLE IF EXISTS public.image_search ; """ # 用于创建表的SQL语句。 create_table_sql = """ CREATE TABLE IF NOT EXISTS public.image_search ( id INTEGER NOT NULL, class TEXT, image_vector vector(1000), PRIMARY KEY(id) ) ; """ # 修改向量列的存储格式为PLAIN。 alter_vector_storage_sql = """ ALTER TABLE public.image_search ALTER COLUMN image_vector SET STORAGE PLAIN; """ # 执行上述SQL语句。 #cursor.execute(drop_table_sql) cursor.execute(create_table_sql) cursor.execute(alter_vector_storage_sql) connection.commit() print("rds pg connect over!")
import io # 定义一个生成器函数,逐行处理文件中的数据。 def process_file(file_path): with open(file_path, 'r') as file: for line in file: modified_line = line.replace('{', '[').replace('}', ']') yield modified_line # 导入数据的SQL。 copy_command = """ COPY public.image_search (id, class, image_vector) FROM STDIN WITH (DELIMITER '|'); """ # 图片特征向量文件。 features_file_path = "/Users/shangwenkai/Desktop/vector/features" # 执行COPY命令。 modified_lines = io.StringIO(''.join(list(process_file(features_file_path)))) print("uploadeing") cursor.copy_expert(copy_command, modified_lines) connection.commit() print("uploaded")
#CREATE INDEX ON vtest USING ivfflat(v vector_cosine_ops) WITH(lists = 100); #CREATE INDEX ON vtest USING ivfflat(v vector_cosine_ops) WITH(lists = 200); #CREATE INDEX ON vtest USING ivfflat(v vector_cosine_ops) WITH(lists = 500); #CREATE INDEX ON vtest USING hnsw (v vector_cosine_ops) #CREATE INDEX ON vtest USING hnsw (v vector_cosine_ops) with(m = 32, ef_construction = 250); #CREATE INDEX ON vtest USING hnsw (v vector_cosine_ops) with(m = 32, ef_construction = 500); create_indexes_sql = """ CREATE INDEX ON image_search USING ivfflat(image_vector vector_l2_ops) WITH(lists = 100); """ print("creating index!") cursor.execute(create_indexes_sql) connection.commit() print("rds pg index over!")
- 执行cosine相似度查询,输出最相似的图片
- 关闭自动提交模式,设置事务参数 ivfflat 索引的探针数量设置为 100。此参数影响向量相似度搜索的性能和准确度。
import os import psycopg2cffi def show_images_from_full_dataset(dset, num_rows, num_cols, indices): im_arrays = np.take(dset.data, indices, axis=0) labels = map(dset.classes.__getitem__, np.take(dset.targets, indices)) indices = np.array(indices) fig = plt.figure(figsize=(18, 18)) grid = ImageGrid( fig, 111, nrows_ncols=(num_rows, num_cols), axes_pad=0.3) for i, (ax, im_array, label, idx) in enumerate(zip(grid, im_arrays, labels, indices)): ax.imshow(im_array) # 在标题中显示编号和标签 ax.set_title(f"{idx}: {label}") ax.axis("off") def query_analyticdb(collection_name, vector_name, query_embedding, top_k=50): # 创建查询SQL,返回与查询向量最相近的图片,同时计算与查询向量的相似度。 query_sql = f""" SELECT id, class, ({vector_name} <=> '{query_embedding}') AS cosine_distance FROM {collection_name} ORDER BY cosine_distance LIMIT {top_k}; """ #print(query_sql) # 执行查询。 connection = psycopg2cffi.connect( host=os.environ.get("PGHOST", "pgm-bp16r2431088910yno.pg.rds.aliyuncs.com"), port=os.environ.get("PGPORT", "5432"), database=os.environ.get("PGDATABASE", "face_ai"), user=os.environ.get("PGUSER", "zhongchi"), password=os.environ.get("PGPASSWORD", "Ssaa1776") ) cursor = connection.cursor() connection.autocommit = False cursor.execute("SET LOCAL ivfflat.probes = 100;") cursor.execute(query_sql) results = cursor.fetchall() connection.commit() return results # 选择一条数据作为query。 def select_feature(file_path, expect_id): with open(file_path, 'r') as file: for line in file: datas = line.split('|') if datas[0] == str(expect_id): vec = '[' + datas[2][1:-2] + ']' return vec raise ValueError(f"没有对应id= {expect_id}的数据") file_path = "/Users/shangwenkai/Desktop/vector/features" # 选取id为4999的图片。 num=1 query_vector = select_feature(file_path, num) # 查看这张图片。 show_images_from_full_dataset(dataset, 1, 1, [num]) #print(query_vector) # 执行查询。 results = query_analyticdb("image_search", "image_vector", query_vector) # 将查询结果对应的图片显示出来 # 获取上一步返回结果中的图片id。 indices = [] for item in results: indices.append(item[0]) print(indices) # 显示图片。 show_images_from_full_dataset(dataset, 5, 10, indices)
性能优化
测试数据:
- 1536维随机向量、10万条数据
CREATE TABLE vtest(id BIGINT, v VECTOR(1536));
- 生成随机向量进行查询:
- 防止缓存影响: 使用随机变量可以确保每次运行查询时,都有不同的输入值。这意味着查询结果和计算过程中的中间结果每次都会改变,从而防止数据库利用查询缓存来快速返回结果。
- 评估平均性能: 通过多次运行测试,每次使用不同的随机向量,可以评估算法或系统的平均性能和稳定性。
WITH tmp AS ( SELECT random_array(1536)::VECTOR(1536) AS vec ) SELECT id, 1 - (v <=> (SELECT vec FROM tmp)) AS cosine_similarity FROM vtest ORDER BY v <=> (SELECT vec FROM tmp) LIMIT FLOOR(RANDOM() * 50);
- 执行计划如下
QUERY PLAN Limit (cost=743.55..885.11 rows=10000 width=24) (actual time=13.342..13.788 rows=38 loops=1) CTE tmp -> Result (cost=0.00..0.01 rows=1 width=32) (actual time=0.340..0.340 rows=1 loops=1) InitPlan 2 (returns $1) -> CTE Scan on tmp (cost=0.00..0.02 rows=1 width=32) (actual time=0.002..0.002 rows=1 loops=1) InitPlan 3 (returns $2) -> CTE Scan on tmp tmp_1 (cost=0.00..0.02 rows=1 width=32) (actual time=0.343..0.344 rows=1 loops=1) -> Index Scan using vtest_v_idx on vtest (cost=743.50..2159.10 rows=100000 width=24) (actual time=13.302..13.744 rows=38 loops=1) Order By: (v <=> $2) Planning Time: 0.413 ms Execution Time: 13.919 ms
评估指标:
变量:索引类型、创建索引参数、运行时参数
指标:查询时间、召回率
测试程序:
- 初始化随机向量: 调用数据库预定义的函数生成随机向量,作为本次查询的基线向量。
- 配置查询性能参数: 动态设置
hnsw.ef_search
或ivfflat.probes
等参数,以控制向量搜索算法的性能表现,这些参数直接影响搜索的速度和精度。 - 分析使用索引的查询计划:
- 选择使用的索引类型、参数
- 执行
EXPLAIN
命令来获取带有索引的查询计划,记录所使用的索引、规划时间和执行时间。 - 进行向量检索,收集结果中的ID并存储在一个哈希集合中,以便后续比较(近似检索)。
- 禁用索引的查询计划分析:
- 在事务中临时禁用索引使用,重新执行
EXPLAIN
命令,记录没有索引时的规划时间和执行时间。 - 再次执行向量检索,获取结果ID并存储在另一个哈希集合中(精确检索)。
- 计算召回率: 比较近似检索与精确检索的结果集,确定召回率,即近似检索结果中正确识别的比例。
- 汇总统计:
- 在所有迭代完成后,计算平均召回率、平均使用索引的执行时间以及平均不使用索引的执行时间。
- 分析结果,评估索引对查询性能和召回率的影响。
索引
ivfflat
- 影响参数:
- List (倒排列表):
- 在构建索引的过程中,数据集被划分成若干个聚类(clusters),每个聚类形成一个倒排列表。每个倒排列表包含了一组向量,这些向量在高维空间中彼此接近。
- 每个倒排列表与一个中心点(centroid)相关联,这个中心点是该聚类中向量的平均值或代表值。构建索引时,每个向量都被分配到最接近它的中心点所在的倒排列表中。
- 倒排列表的数量(
list
参数)决定了索引的粒度。较大的list
可以提高搜索精度,但会增加存储需求和构建索引的时间。
- Probe (探查):
- 在搜索阶段,
IVFFlat
算法会计算查询向量与所有中心点的距离,然后选择最接近的中心点(或一组中心点)对应的倒排列表进行精确搜索。 probe
参数决定了搜索时要检查多少个倒排列表。较高的probe
数值会提高搜索的召回率(召回更多的相关结果),但也会增加搜索的时间成本。probe
数值可以从 1 到list
之间的任意整数。- 例如,如果
probe
设定为 10,那么算法将检查与查询向量最接近的 10 个中心点的倒排列表,从中找到最接近的邻居。
- 测试结果:
第一行是召回率,第二行是使用索引的查询时间,第三行是禁用索引的查询时间
特别的,当list=100时,当probe设置为60,召回率达到了100,但是执行时间与不使用索引差不多甚至更慢!
probe/list |
50 |
100 |
200 |
500 |
10 |
55.35% 69.65365ms 632.72895ms |
53.500000000000014% 190.91120000000004ms 634.9751500000001ms |
47.39999999999999% 57.68634999999999ms 629.3890999999999ms |
25.3% 31.07309999999999ms 627.63795ms |
30 |
100.0% 634.8525500000003ms 632.0416500000001ms |
90.70000000000003% 367.2775499999999ms 633.07945ms |
88.35000000000001% 129.38224999999997ms 632.0462999999997ms |
58.699999999999996% 73.99605ms 628.78475ms |
60 |
100.0% 638.90615ms 634.8017499999999ms |
98.4% 147.06294999999997ms 631.46215ms |
82.1% 117.12119999999997ms 630.0801ms |
- 建议参数:
- lists的值对索引占用的存储空间影响微乎其微,和表中的数据量有直接的关系。
- lists和probes对查询效率以及召回率起着相反的作用,因此合理地设置这两个值可以在查询效率以及召回率上达到一个平衡。
- 小于等于100万行:
lists = rows / 1000
、probes = lists / 10
- 大于100万行:
lists = sqrt(rows)
、probes = sqrt(lists)
hnsw
- M (Maximum number of connections):
- 这个参数定义了在 HNSW 图中的每个节点最多能有多少个连接到其他节点的边。较高的
M
值会增加索引的构建时间,但可能会提高查询准确性。
- ef_construction (Construction efficiency):
- 这个参数控制着索引构建过程中的“效率”,实际上是在构建过程中搜索邻居的数量。较高的
ef_construction
值会使得索引构建更加耗时,但通常也会产生更高质量的索引,从而在查询时获得更好的结果。
- ef_search (Search efficiency):
- 这个参数控制着查询时搜索邻居的数量。较高的
ef_search
值会增加查询时间,但可以提高查询的准确性。
ef_construction/m,ef_search |
16,64(原始) |
32,250 |
32,500 |
建索引时间 |
3min 26s 415ms |
22min 11s 192ms |
33min 16s 110ms |
100 |
25.050000000000004% 7.2226ms 648.6943000000001ms |
40.449999999999996% 12.6573ms 646.3129000000001ms |
39.30000000000001% 12.188649999999999ms 649.1184ms |
500 |
15.350000000000003% 3.6442500000000004ms 634.7538999999999ms |
76.95% 40.16015ms 646.6358499999999ms |
74.25% 40.7359ms 652.56025ms |
1000 |
65.80000000000001% 37.420500000000004ms 648.8227999999999ms |
86.19999999999997% 65.57425ms 647.3207ms |
85.2% 67.35210000000002ms 651.17415ms |
总结
- 对于
ivfflat
索引,均衡list
和probe
关系来达到查询效率和召回率的平衡。 - 对于
hnsw
索引,增加M
、ef_construction
和ef_search
可以提高召回率,但会增加索引构建时间;需要根据实际应用场景进行权衡。
综上所述,在本测试案例中,对于较小的数据集(如10万条1536维向量),ivfflat
索引在适当配置下可以提供较好的性能;而 hnsw
索引则更适合追求更高召回率的应用场景,尽管它可能需要更长的索引构建时间。
遇到的问题汇总
为什么查询不使用索引?
查询需要有ORDER BY、LIMIT,并且ORDER BY必须是距离运算符(而不是表达式)按升序排列的结果。
-- 可以 ORDER BY embedding <=> '[3,1,2]' LIMIT 5; -- 不可以 ORDER BY 1 - (embedding <=> '[3,1,2]') DESC LIMIT 5;
举例:
可以索引加速 |
不能利用索引 |
-- 查询距离 按距离升序 EXPLAIN ANALYSE WITH tmp AS ( SELECT random_array(1536)::VECTOR(1536) AS vec ) SELECT id,(v <=> (SELECT vec FROM tmp)) AS cosine_distance FROM vtest ORDER BY cosine_distance LIMIT FLOOR(RANDOM() * 50) ; |
-- 查询距离 按距离逆序 EXPLAIN ANALYSE WITH tmp AS ( SELECT random_array(1536)::VECTOR(1536) AS vec ) SELECT id,(v <=> (SELECT vec FROM tmp)) AS cosine_distance FROM vtest ORDER BY cosine_distance desc LIMIT FLOOR(RANDOM() * 50) ; |
-- 查询相似度 按距离升序 EXPLAIN ANALYSE WITH tmp AS ( SELECT random_array(1536)::VECTOR(1536) AS vec ) SELECT id, 1 - (v <=> (SELECT vec FROM tmp)) AS cosine_similarity FROM vtest ORDER BY v <=> (SELECT vec FROM tmp) LIMIT FLOOR(RANDOM() * 50); |
-- 查询相似度 按相似度升序 EXPLAIN ANALYSE WITH tmp AS ( SELECT random_array(1536)::VECTOR(1536) AS vec ) SELECT id, 1 - (v <=> (SELECT vec FROM tmp)) AS cosine_similarity FROM vtest ORDER BY cosine_similarity LIMIT FLOOR(RANDOM() * 50); |
-- 查询相似度 按相似度降序 EXPLAIN ANALYSE WITH tmp AS ( SELECT random_array(1536)::VECTOR(1536) AS vec ) SELECT id, 1 - (v <=> (SELECT vec FROM tmp)) AS cosine_similarity FROM vtest ORDER BY cosine_similarity desc LIMIT FLOOR(RANDOM() * 50); |
|
-- 查询相似度 按距离降序 EXPLAIN ANALYSE WITH tmp AS ( SELECT random_array(1536)::VECTOR(1536) AS vec ) SELECT id, 1 - (v <=> (SELECT vec FROM tmp)) AS cosine_similarity FROM vtest ORDER BY v <=> (SELECT vec FROM tmp) desc LIMIT FLOOR(RANDOM() * 50); |
为什么添加 HNSW 索引后查询结果变少了?
结果受hnsw.ef_search大小限制。设置hnsw.ef_search为查询的至少两倍LIMIT。如果需要超过 500 个结果,改用 IVFFlat 索引。
为什么添加 IVFFlat 索引后查询结果变少了?
- 索引可能创建时包含的数据量相对于列表数量而言太少。删除索引,直到表包含更多数据。
- 过少的list:如果
list
设置得过大,而实际数据量不足以填充这么多的list,那么一些list可能包含很少的向量,甚至为空。这会导致查询时,某些list的搜索结果可能不够丰富,从而减少总的候选结果数量。 - 不均匀的list分布:数据分布不均也可能导致某些list过于拥挤,而其他list则相对空旷。这同样会影响查询结果的质量,因为查询可能错过某些可能的相关向量。
- 结果也受到ivfflat.probes的限制。
HNSW建索引时间太长
可以设置参数加速
SET max_parallel_maintenance_workers = 4; SET maintenance_work_mem = '7GB';
可以查看构建进度
SELECT phase, round(100.0 * blocks_done / nullif(blocks_total, 0), 1) AS "%" FROM pg_stat_progress_create_index;
进阶
半精度Half-Precision
每个半向量占用2 * dimensions + 8字节的存储空间。每个元素都是半精度浮点数,并且所有元素都必须是有限的(无NaN、Infinity或-Infinity)。半向量最多可以有 16,000 个维度。
CREATE TABLE items (id bigserial PRIMARY KEY, embedding halfvec(3)); CREATE INDEX ON items USING hnsw ((embedding::halfvec(3)) halfvec_l2_ops); SELECT * FROM items ORDER BY embedding::halfvec(3) <-> '[1,2,3]' LIMIT 5;
稀疏向量Sparse
格式为{index1:value1,index2:value2}/dimensions,索引从 1 开始,类似 SQL 数组
CREATE TABLE items (id bigserial PRIMARY KEY, embedding sparsevec(5)); INSERT INTO items (embedding) VALUES ('{1:1,3:2,5:3}/5'), ('{1:4,3:5,5:6}/5'); SELECT * FROM items ORDER BY embedding <-> '{1:3,3:1,5:2}/5' LIMIT 5;
子向量
在向量数据库中,向量通常具有高维,例如几百或几千维。直接对高维向量建立索引可能会导致索引变得非常庞大,影响性能。为此,可以采用“子向量”(subvectors)的概念,即仅对向量的子集维度建立索引,以降低索引的复杂性和存储需求。
subvector
函数用于从一个高维向量中提取一个子向量。这里的参数 embedding
是一个向量列,1
和 3
分别是起始和结束的维度索引。因此,subvector(embedding, 1, 3)
提取了 embedding
向量的前三个维度。
CREATE INDEX ON items USING hnsw ((subvector(embedding, 1, 3)::vector(3)) vector_cosine_ops); SELECT * FROM items ORDER BY subvector(embedding, 1, 3)::vector(3) <=> subvector('[1,2,3,4,5]'::vector, 1, 3) LIMIT 5;
按全向量重新排序以获得更好的召回率:
SELECT * FROM ( SELECT * FROM items ORDER BY subvector(embedding, 1, 3)::vector(3) <=> subvector('[1,2,3,4,5]'::vector, 1, 3) LIMIT 20 ) ORDER BY embedding <=> '[1,2,3,4,5]' LIMIT 5;
SQL优化(实际表现与初始想法不一样)
当需要返回向量距离的score值时,可以利用向量索引返回的排序值进行二次计算得到真实的向量距离score,而避免做完整的向量距离计算
SELECT id, 1 - (v <=> '目标向量') AS cosine_similarity FROM vtest ORDER BY v <=> '目标向量' LIMIT 50;
执行计划:
Limit (cost=89.70..90.98 rows=50 width=24) (actual time=1.720..2.044 rows=40 loops=1) -> Index Scan using vtest_v_idx3 on vtest (cost=89.70..2649.30 rows=100000 width=24) (actual time=1.719..2.039 rows=40 loops=1) Order By: (v <=> '目标向量'::vector) Planning Time: 0.080 ms Execution Time: 2.081 ms
SELECT t.id as id, (1.0 - t.score) as score FROM ( SELECT id, (v <=> '目标向量') AS score FROM vtest ORDER BY score LIMIT 50 ) t;
执行计划:
Subquery Scan on t (cost=89.70..90.85 rows=50 width=16) (actual time=1.616..1.845 rows=40 loops=1) -> Limit (cost=89.70..90.73 rows=50 width=16) (actual time=1.615..1.839 rows=40 loops=1) -> Index Scan using vtest_v_idx3 on vtest (cost=89.70..2149.30 rows=100000 width=16) (actual time=1.614..1.834 rows=40 loops=1) Order By: (v <=> '目标向量'::vector) Planning Time: 0.088 ms Execution Time: 1.880 ms
关于第二个查询能否减少计算耗时的问题:
不能减少计算耗时的原因在于:
- 计算距离:在子查询中,即使使用了向量索引进行排序,仍然需要计算每个向量与目标向量之间的距离。
- 排序和限制:排序操作本身就需要一定的计算资源,特别是当数据量较大时。
- 额外的计算:外层查询还需要额外计算
1.0 - score
,这虽然简单,但仍然是额外的操作。
总结:
- 第一个查询直接计算了余弦相似度,并利用了向量索引进行排序,这是比较高效的方法。
- 第二个查询虽然试图通过子查询来减少计算,但实际上并没有减少计算向量距离的操作,而且引入了额外的步骤。
当需要根据score的范围进行过滤并返回结果时,可以利用了向量索引的排序值进行计算得到最终的score
SELECT id, 1 - (v <=> '目标向量') AS cosine_similarity FROM vtest WHERE v <=> '目标向量' <=0.3 ORDER BY v <=> '目标向量' LIMIT 50 ;
执行计划:
Limit (cost=89.70..93.54 rows=50 width=24) (actual time=1.699..2.152 rows=40 loops=1) -> Index Scan using vtest_v_idx3 on vtest (cost=89.70..2649.30 rows=33333 width=24) (actual time=1.698..2.147 rows=40 loops=1) Order By: (v <=> '目标向量'::vector) Filter: ((v <=> '目标向量'::vector) <= '0.3'::double precision) Planning Time: 0.107 ms Execution Time: 2.187 ms
SELECT t.id as id, (1.0 - t.score) as score FROM ( SELECT id, (v <=> '目标向量') AS score FROM vtest ORDER BY score LIMIT 50 ) t WHERE score<=0.3;
执行计划:
Subquery Scan on t (cost=89.70..91.40 rows=17 width=16) (actual time=1.767..2.007 rows=40 loops=1) Filter: (t.score <= '0.3'::double precision) -> Limit (cost=89.70..90.73 rows=50 width=16) (actual time=1.766..1.999 rows=40 loops=1) -> Index Scan using vtest_v_idx3 on vtest (cost=89.70..2149.30 rows=100000 width=16) (actual time=1.765..1.994 rows=40 loops=1) Order By: (v <=> '目标向量'::vector) Planning Time: 0.433 ms Execution Time: 2.078 ms
关于第二个查询能否减少计算耗时的问题:
第二个查询实际上无法减少计算耗时的原因在于:
- 计算距离:在子查询中,需要计算每个向量与目标向量之间的距离。
- 排序和限制:尽管使用了向量索引进行排序,但是排序操作本身需要计算所有记录的距离。
- 额外的过滤:外层查询还需要根据
score <= 0.3
再次过滤结果。
总结:
- 第一个查询通过使用
WHERE
子句直接过滤了距离大于等于0.3的记录,然后排序并返回结果。这种方式更加高效,因为它减少了不必要的计算和排序。 - 第二个查询虽然试图通过子查询来减少计算,但是在子查询中就已经计算了所有记录的距离,然后排序和限制,最后在外层查询中再进行过滤。这种方式实际上增加了计算负担。
混合搜索
混合查询具体可以划分为三类:
- 向量查询和结构化字段过滤组成的混合查询。BTREE索引进行加速。
- 向量查询和半结构化字段过滤组成的混合查询。GIN索引进行加速。
- 向量查询和全文检索组成的双路召回。
SELECT id, content FROM items, plainto_tsquery('hello search') query WHERE textsearch @@ query ORDER BY ts_rank_cd(textsearch, query) DESC LIMIT 5;