w wyl123ly 的博客
MD

向量数据库

34 KB 2026.10.18 原文件

向量数据库

定义

向量检索系统(vector search system)是一个四元组 : 是嵌入函数,把对象映射为 维向量; 是索引结构,把 个向量组织为支持近邻查询的数据结构; 是元数据存储与过滤条件求值; 是对外查询接口,接受查询向量、、过滤条件与一致性要求。

精确最近邻(exact nearest neighbor)返回真实的前 个最近向量;近似最近邻(approximate nearest neighbor,ANN)返回候选集合 ,只保证以较高概率覆盖真实结果。召回率定义为

其中 是精确检索结果, 是查询集合。工程上同时报告召回率与延迟分位数,二者构成一条权衡曲线。

符号约定如下。

符号含义
向量总数
向量维度
返回条数
HNSW 每个节点在每层的邻居数上限
HNSW 第 0 层的邻居数上限,通常取
HNSW 构建时的候选队列长度
HNSW 查询时的候选队列长度
HNSW 层数分布的尺度参数,
IVF 的聚类桶数
IVF 查询时扫描的桶数
PQ 的子向量个数,每个子向量编码 1 字节
PQ 每个子向量的比特数,通常为 8
过滤条件的选择率,满足条件的向量占比

其余术语在首次出现处定义:HNSW(Hierarchical Navigable Small World)指分层可导航小世界图;IVF(inverted file)指倒排文件索引,用聚类把向量分桶;PQ(product quantization)指乘积量化,把向量切段后分别编码;ADC(asymmetric distance computation)指查询保持原始向量、库中向量用码字近似时的距离计算;选择率指过滤条件命中的向量比例。

为什么重要

暴力检索的代价随规模线性增长。、 时,向量本身占 GB,单次查询要读取全部向量;按 50 GB/s 的有效内存带宽估算,单查询约 0.6 秒,且这一时间与查询难度无关。 时向量占 307 GB,单机内存无法容纳,必须压缩或分片。ANN 索引把“扫描全部向量”改为“访问少量候选”,使查询延迟与 近似对数关系,这是检索系统能够在线服务的前提。

但 ANN 用召回率换延迟,召回率下降会直接传导到生成质量。检索未命中时,生成器只能依据参数化知识作答,答案不可归因;检索返回错误文档时,生成器获得干扰证据。这两类错误无法在生成阶段修复,只能回到索引层解决,失效分析见 RAG原理与流程。因此向量数据库的核心指标不是“单查询多快”,而是“在目标召回率下的延迟与内存”。

系统层面还有三个不可回避的问题。第一,元数据过滤:业务查询通常带租户、时间、权限、文档类型等条件,过滤与 ANN 的组合会改变召回率。第二,更新与删除:嵌入模型升级需要全量重编码,删除需要处理图结构与倒排表的残留。第三,容量规划:原始向量、图结构、量化码、副本与索引构建的临时空间共同决定单机上限。这三项在原型阶段不可见,在数据量超过内存后才暴露。

在本库中,本篇承接 Embedding与向量检索 的度量与训练,向下接入 RAG原理与流程 的检索阶段,并与 检索优化与重排Rerank 构成“召回—重排”两级结构;工程侧的延迟与成本约束见 模型推理优化。学习目标是能根据数据规模、召回要求与过滤比例选择索引类型与参数,并能用可复现的实验报告召回率与延迟。

原理与推导

1 系统组成与数据流

一个完整的向量检索系统包含五个部分,缺一不可。

组件职责关键设计点
嵌入服务把文本编码为向量模型版本、维度、归一化、批量吞吐
索引结构支持近邻查询Flat、HNSW、IVF、PQ 及其组合
元数据存储保存 id、来源、权限、时间等标量字段与向量 id 对齐、过滤下推
过滤执行在候选集上应用布尔条件预过滤、后过滤、分区
查询接口参数校验、超时、一致性、监控top-k、nprobe、efSearch、重试

离线与在线两条链路共用同一套 id 与元数据。

flowchart LR
    DOC[原始文档] --> CH[分块]
    CH --> ENC[嵌入编码]
    ENC --> IDX[索引构建]
    ENC --> META[(元数据与标量字段)]
    Q[查询文本] --> QENC[查询编码]
    QENC --> ANN[ANN 检索]
    IDX --> ANN
    META --> FIL[过滤条件]
    FIL --> ANN
    ANN --> CAND[候选集]
    CAND --> RER[精算或重排]
    RER --> TOP[Top-k 结果]

图中的关键约束是两侧必须使用同一嵌入模型与同一归一化方式。模型版本不一致时,查询向量与文档向量位于不同空间,内积失去意义;这类错误不会报错,只会表现为召回率整体下降。

2 精确检索的代价与 ANN 的定义

精确检索计算查询与全部向量的内积并取前 :

时间复杂度为 ,空间复杂度为 。矩阵乘法可以把常数压得很低,但无法改变必须读取全部向量的性质:计算量 在 GPU 上约需毫秒级,而读取 字节受内存带宽限制。、 时数据量为 30.72 GB,超过多数单卡的显存,也超过 CPU 缓存的三个数量级。

ANN 的做法是只访问可能包含近邻的一小部分向量。设访问的候选数为 ,则查询代价近似为 ,加速比约为 。代价是可能漏掉真实近邻:若真实近邻不在被访问的候选集中,无论后续如何计算都无法找回。因此 ANN 的评估必须同时给出召回率 与延迟,单独报告其中一个没有意义。

高维空间使问题更难。维度增大时,最近邻与较远点的距离差异变小,索引用来剪枝的几何条件变弱,这是维度灾难在检索上的表现;HNSW 与 IVF 在高维数据上仍可用,但需要更多候选才能达到相同召回率。

3 HNSW:多层图、插入与搜索

HNSW 把向量组织为一张分层图。第 0 层包含全部 个节点,越往上节点越少;每个节点出现在从第 0 层到其最高层的一段连续层中。层数按指数分布采样:

因此第 层的期望节点数为 ,最高层的期望高度为 。上层边少而长,负责快速接近目标区域;下层边多而短,负责精确收敛。这一结构使搜索的期望跳数为 。

插入一个节点 的过程如下。

  1. 采样层数 , 为 上的均匀随机数。
  2. 从当前最高层 向下到第 层,在每层用贪心策略移动到一个距离 更近的邻居,直到无法改进;这是 的搜索。
  3. 从 层向下到第 0 层,在每层用长度为 的候选队列搜索,得到候选邻居集合。
  4. 用启发式规则从候选中选出不超过 (第 0 层为 )个邻居,建立双向边。
  5. 若某邻居的边数超过上限,按同一启发式规则裁剪其邻接表。
  6. 若 ,更新最高层。

第 4 步的启发式规则是 HNSW 与普通近邻图的关键区别。设候选 已按到 的距离升序排列,已选邻居集合为 ,则仅当

成立时才把 加入 。该条件要求新邻居与已选邻居之间保持一定间隔,避免所有边都指向同一局部方向。若只取最近的 个邻居,图会在密集区域形成团簇,缺少通往其他区域的边,搜索容易陷入局部最优;启发式规则牺牲部分近邻精度,换取图的连通性与可导航性。

搜索过程分两段。

  1. 从最高层开始,在每层执行贪心搜索,直到当前层无法再靠近查询。
  2. 到达第 0 层后,用长度为 的候选队列执行束搜索:维护候选堆与结果堆,每次取出最近的候选,遍历其邻居,若邻居比结果堆中最远元素更近或结果堆未满,则加入并按 裁剪。

最终从结果堆中取前 个。,且 越大,候选覆盖越充分、召回越高、延迟越大。查询阶段可在线调整该参数,无需重建索引。

参数作用增大时的效果典型范围
每层邻居数上限图更密,召回上升,内存与构建时间线性增长16 到 64
第 0 层邻居上限底层连通性更好,内存增加
构建候选队列图质量上升,构建变慢100 到 400
查询候选队列召回上升,延迟上升32 到 256

内存由邻接表主导。每个节点在第 0 层保存至多 个邻居 id,上层合计约 个,故

、 时约 2.42 GiB,与原始向量(28.61 GiB)相比很小;若同时保存原始向量用于精算,总内存约为二者之和。删除在 HNSW 中代价高:删除节点会破坏双向边与连通性,FAISS 的 HNSW 索引不实现 remove_ids,常见做法是维护有效位掩码并在查询时扩大 ,或定期重建索引。

4 IVF:聚类分桶与 nprobe

IVF 用一个粗量化器把向量空间划分为 个区域。训练阶段对样本做 k-means,得到质心 ;写入阶段把每个向量分配到最近质心所属的倒排表:

查询阶段先计算查询到全部质心的距离,选出最近的 个桶,只扫描这些桶内的向量:

若各桶大小均衡,候选数为 ,相对暴力检索的加速比约为 ,另需 的质心比较开销。、、 时候选数约为 2500,实测为 2470,与估算一致。

召回率取决于真实近邻是否落在被探测的桶中。若真实近邻所在桶的质心不是查询的最近 个质心之一,该近邻就无法被找回。桶的划分由 k-means 在训练样本上决定,因此训练样本必须代表线上分布:样本偏斜会使部分区域缺少质心,落在这些区域的查询召回率显著下降。

参数作用增大时的效果经验取值
桶数单桶更小,扫描更快,但质心比较与训练成本上升 到
探测桶数召回上升,延迟线性上升 的 1% 到 10%
训练样本量质心质量更接近真实分布,训练更慢至少 ,推荐

IVF 的结构简单,插入只需一次质心比较后追加到对应桶,删除只需从桶中移除,更新成本低于 HNSW。它的弱点是查询时要访问多个桶,且桶的边界由质心决定,对分布漂移敏感;数据分布随时间变化时需要重新训练质心并重建索引。

5 PQ:乘积量化、压缩率与精度损失

PQ 把 维向量切成 段,每段 维,对每段独立做 k-means,得到 个码本,每个码本含 个码字。一个向量被编码为 个编号:

原始向量占 字节,编码后占 字节(),压缩比为

、 时压缩比为 32, 条向量从 28.61 GiB 降到 0.89 GiB。查询时预先计算查询各段到对应码本全部码字的距离,得到 的查找表:

则与编码向量的近似平方距离为 ,只需 次查表与加法,不再做浮点乘加。这就是 ADC。

精度损失来自分段独立量化:每段单独选择码字,段间相关性被丢弃。 越大,每段维度越低、码本越容易拟合,误差越小,但压缩比下降; 越小,压缩比越高,距离估计偏差越大。 必须整除 ,且每段维度不宜低于 4,否则码本难以覆盖该子空间。

配置()每段维度压缩比内存( 条)精度
4161.79 GiB较高
8320.89 GiB中等
16640.45 GiB较低

PQ 通常与 IVF 组合为 IVFADC:先用 IVF 选桶,再在桶内用 PQ 码计算近似距离,最后可用原始向量对前若干条精算。只依赖 PQ 码排序会引入系统性偏差,精算阶段能挽回部分召回,代价是需要保存原始向量或回表读取,内存与 IO 随之上升。

6 度量类型与归一化一致性

索引的度量必须与写入、查询时的处理一致。三种常见组合如下。

目标写入处理索引度量查询处理
余弦相似度L2 归一化内积或余弦L2 归一化
欧氏距离不归一化L2不归一化
内积不归一化内积不归一化

向量归一化后,内积排序与 L2 排序一致(),因此在归一化数据上把余弦检索实现为内积索引是等价的,且内积计算少一次除法。若写入时归一化、查询时未归一化,内积会引入查询模长因子,虽然对同一查询的所有文档是同一常数、不改变排序,但混合了未归一化文档时排序就会改变。若写入未归一化、查询归一化,则文档模长进入排序,长文档占优。

各系统的接口对度量有显式声明。pgvector 用操作符与索引类绑定:<-> 对应 L2 距离、<#> 返回负内积、<=> 返回余弦距离,索引必须用匹配的 vector_l2_ops、vector_ip_ops、vector_cosine_ops,否则查询不会使用该索引。Milvus 在集合级别声明 metric_type,Chroma 在集合创建时指定 hnsw:space。更换度量意味着重建索引,不能只改查询参数。

量化索引还要求训练与查询使用同一度量。IVF 的 k-means 以 L2 分配样本,PQ 的码本也以 L2 训练;若最终按内积排序,归一化后二者一致,未归一化时近似误差会偏向模长大的向量。

7 元数据过滤:预过滤与后过滤

过滤条件把查询限制在满足布尔表达式的子集上,选择率 表示命中比例。两种执行顺序的代价不同。

后过滤(post-filter)先做 ANN 取 条,再按条件过滤,若不足 条则扩大 重试。若过滤与向量分布独立,留下的条数近似服从二项分布,期望为 。要得到 条,需 : 时为了 10 条结果要取 1000 条候选,延迟与 成正比,且极端情况下重试多次仍不足。

预过滤(pre-filter)先计算满足条件的 id 集合,再在该集合内检索。若集合很小,直接暴力扫描子集的代价为 ,可能低于 ANN;若集合较大,可以把过滤条件交给索引做过滤式遍历。问题在于图索引的连通性:HNSW 的边跨越不同元数据分区,过滤掉大量节点后,从入口到目标区域的路径可能被切断,召回率骤降。工程上的折中包括按过滤字段分区(每个租户或时间段一个集合)、在遍历时跳过不满足条件的节点但保留其边、以及用位图加速条件判断。

策略做法优点缺点适用
后过滤ANN 取 再过滤实现简单,索引不变低选择率时延迟放大
预过滤暴力取 id 子集后扫描召回精确子集大时慢
过滤式遍历遍历时跳过不合格节点兼顾召回与延迟依赖系统支持
分区按租户/时间建独立集合过滤变为路由集合数量与运维成本上升强分区语义

选择率不是唯一因素,过滤字段与向量的相关性同样重要。若某类文档的向量本身聚集,过滤后候选区域变窄,ANN 更容易漏召回;此时应优先分区而不是后过滤。

8 系统选型对比

系统形态索引过滤更新与删除适用规模
Chroma嵌入式库,也提供服务模式HNSWwhere 元数据过滤支持按 id 删除与更新原型到百万级
FAISSC++/Python 库Flat、IVF、PQ、HNSW、OPQ 等无内置元数据,需自建掩码HNSW 不支持原地删除,IVF 可移除百万到十亿级,需自行分片
Milvus分布式服务HNSW、IVF、PQ、DiskANN、GPU 索引标量过滤与混合查询支持删除与 compaction亿级,多租户
pgvectorPostgreSQL 扩展IVFFlat、HNSWSQL WHERE,与事务一致支持 DELETE 与 UPDATE百万到千万级,单机为主

选型从约束出发,而不是从基准测试排名出发。已有 PostgreSQL 且数据量在千万级以内时,pgvector 复用事务、备份与权限体系,运维成本最低;需要十亿级向量与多副本时,Milvus 的存算分离与分区能力更合适;只做离线实验或需要 GPU 暴力检索时,FAISS 提供最完整的索引组合;原型阶段需要最少配置时,Chroma 的嵌入式模式可以省去服务部署。

需要核对三个细节。第一,维度上限:pgvector 的 HNSW 索引对 vector 类型支持到 2000 维,更高维需改用 halfvec 或降维。第二,删除语义:FAISS 的 HNSW 不提供原地删除,删除比例上升后必须重建。第三,过滤下推能力:部分系统只能后过滤,低选择率查询会退化。

9 容量、删除与重建

容量由四部分构成:原始向量 字节、图或倒排结构、量化码与码本、副本与临时构建空间。以 、、HNSW 为例:

部分计算大小
原始向量28.61 GiB
HNSW 邻接2.42 GiB
PQ 码()0.89 GiB
构建临时空间约为原始向量的 1 到 2 倍30 到 60 GiB

原始向量与索引同时驻留时,单机需要 32 GiB 以上的常驻内存,构建阶段还需额外空间;若保存副本,按副本数线性增加。容量规划应保留 30% 余量,用于重建、合并与流量峰值。

删除在两类索引中的代价不同。IVF 与 PQ 的删除是定位 id 所在桶后移除,代价 到 ;HNSW 的删除会破坏双向边,通常用墓碑标记,查询时过滤,等到墓碑比例超过阈值(常见 10% 到 20%)再重建。墓碑比例上升会同时降低召回率与有效容量,因为被标记的节点仍占用图结构与遍历预算。

重建由三类事件触发:嵌入模型更换、数据分布显著漂移、删除与更新累积。模型更换必须全量重编码,不能只重建索引,因为新旧向量不在同一空间;迁移应采用双写策略,新索引构建完成并通过离线评估后切换别名,保留旧索引一段时间用于回滚。重建期间的服务能力需要提前规划,常见做法是按分片滚动重建。

10 参数选择建议

  1. 先固定度量与归一化,再选索引。度量不一致造成的召回损失无法通过调参弥补。
  2. HNSW 起步取 到 、,在 1000 条查询的样本上把 从 32 扫到 256,记录召回率与 p99 延迟,选择满足召回目标的最小值。
  3. 目标召回率高于 0.98 时,优先增大 与 重建,而不是只增大 ;后者只能改善查询侧,无法修复图结构缺陷。
  4. IVF 取 到 , 从 1% 起调;训练样本至少 条,且必须来自线上分布。
  5. 内存不足时引入 PQ, 取 左右并保证整除;压缩后务必用原始向量对前 50 到 100 条精算,否则排序偏差会传导到生成阶段。
  6. 过滤选择率低于 1% 时改用预过滤或分区;1% 到 10% 时确认系统支持过滤式遍历;高于 10% 时后过滤通常可接受。
  7. 每次更换模型、调整参数或数据分布变化后,重跑同一套查询与标注,报告召回率、p50/p99 延迟、内存占用与构建时间,四项同时记录。

关键直觉

HNSW 是“分层图 + 束搜索”:上层负责快速接近目标区域,下层负责精确收敛, 是用候选数量换取召回率的查询期预算;IVF 用聚类把全量扫描变成“只扫 个桶”,加速比约为 ;PQ 用分段码本把向量压缩为 字节,并用查表把距离计算变成 次加法。

与严格定义的关系:召回率 定义了 ANN 的“近似”程度,所有参数只在这条曲线上移动工作点;HNSW 的边选择启发式 解释了为什么图能保持可导航性而不是退化为局部团簇;IVF 的候选数 与 PQ 的压缩比 把“召回—延迟—内存”三者写成可计算的量,选型就是在这三个量之间取满足约束的点。

例子与代码

例 1:NumPy 实现 IVF 并与精确检索对比

以下代码在合成的聚类数据上构建 IVF 索引,扫描 并报告 Recall@10 与单查询延迟。运行环境为 Python 3.12 与 NumPy 2.3,不依赖 faiss。

import time

import numpy as np

rng = np.random.default_rng(20261018)
N, dim, C, NQ, K = 20000, 64, 20, 200, 10
centers = rng.normal(size=(C, dim))
labels = rng.integers(0, C, N)
X = centers[labels] + rng.normal(scale=0.75, size=(N, dim))
Q = centers[rng.integers(0, C, NQ)] + rng.normal(scale=0.75, size=(NQ, dim))
X = X.astype(np.float32)
Q = Q.astype(np.float32)

def kmeans(data, k, iters=12, seed=7):
    r = np.random.default_rng(seed)
    cent = data[r.choice(len(data), k, replace=False)].copy()
    for _ in range(iters):
        d2 = (data ** 2).sum(1)[:, None] - 2 * data @ cent.T + (cent ** 2).sum(1)[None, :]
        assign = d2.argmin(1)
        for j in range(k):
            m = assign == j
            if m.any():
                cent[j] = data[m].mean(0)
    return cent, assign

t0 = time.perf_counter()
cent, assign = kmeans(X, 64)
print(f"k-means 训练 64 个聚类中心耗时 {time.perf_counter() - t0:.2f} s")

# 精确检索:一次矩阵乘法得到全部查询的 top-10
t0 = time.perf_counter()
exact = np.argsort(-(Q @ X.T), axis=1)[:, :K]
exact_ms = (time.perf_counter() - t0) * 1000 / NQ

# 倒排表:每个簇保存成员下标
lists = [np.where(assign == j)[0] for j in range(64)]

def ivf_search(q, nprobe):
    csim = cent @ q
    cells = np.argsort(-csim)[:nprobe]
    cand = np.concatenate([lists[c] for c in cells])
    scores = X[cand] @ q
    return cand[np.argsort(-scores)[:K]]

print(f"\n精确检索:Recall@10=1.0000,平均每查询 {exact_ms:.2f} ms,扫描 {N} 条向量")
print("nprobe  候选数  Recall@10   每查询 ms")
for nprobe in (1, 2, 4, 8, 16, 32, 64):
    t0 = time.perf_counter()
    approx = np.array([ivf_search(Q[i], nprobe) for i in range(NQ)])
    ms = (time.perf_counter() - t0) * 1000 / NQ
    hits = sum(len(set(map(int, approx[i])) & set(map(int, exact[i]))) for i in range(NQ))
    cand_avg = np.mean([sum(len(lists[c]) for c in np.argsort(-(cent @ Q[i]))[:nprobe])
                        for i in range(NQ)])
    print(f"{nprobe:>6}  {cand_avg:>7.0f}  {hits / (NQ * K):>9.4f}  {ms:>9.3f}")
k-means 训练 64 个聚类中心耗时 0.17 s

精确检索:Recall@10=1.0000,平均每查询 0.91 ms,扫描 20000 条向量
nprobe  候选数  Recall@10   每查询 ms
     1      476     0.6070      0.042
     2      785     0.7965      0.053
     4     1340     0.9665      0.113
     8     2470     1.0000      0.279
    16     4751     1.0000      0.683
    32     9688     1.0000      1.687
    64    20000     1.0000      3.893

上表中的毫秒数是单次运行的记录,随机器负载与实现语言波动;候选数与召回率由数据与参数决定,可以复现。曲线给出三个可复用的结论。第一, 从 1 增到 4 时召回从 0.607 升到 0.967,候选数只增加约 2.8 倍,这是 IVF 的主要收益区间。第二, 时召回达到 1.000 并饱和,原因是合成数据的簇间分离明显,真实语料的近邻会跨越桶边界,召回通常不会饱和。第三, 时单查询 3.893 ms 反而高于精确检索的 0.91 ms:精确检索把 200 个查询合并为一次矩阵乘法,IVF 的 Python 循环与候选收集开销在小规模下占主导,而真实系统的索引由 C++ 或 GPU 实现,常数不同但趋势一致。因此延迟数字只能在同一实现内比较,不能跨实现引用。

例 2:FAISS 的 IndexFlatIP 与 IndexIVFFlat

FAISS 需要单独安装(pip install faiss-cpu 或 faiss-gpu)。以下脚本在缺少 faiss 时自动退化为 NumPy 精确检索,在安装后执行完整分支。

import numpy as np

try:
    import faiss
except ImportError:
    faiss = None

rng = np.random.default_rng(7)
C, d, per, nq, k = 20, 64, 1000, 200, 10
centers = rng.normal(size=(C, d))
xb = centers[rng.integers(0, C, C * per)] + rng.normal(scale=0.75, size=(C * per, d))
xq = centers[rng.integers(0, C, nq)] + rng.normal(scale=0.75, size=(nq, d))
xb = (xb / np.linalg.norm(xb, axis=1, keepdims=True)).astype("float32")
xq = (xq / np.linalg.norm(xq, axis=1, keepdims=True)).astype("float32")
print("xb", xb.shape, "xq", xq.shape)

def recall_at_k(approx, exact, k):
    return float(np.mean([len(set(map(int, a)) & set(map(int, e))) / k
                          for a, e in zip(approx, exact)]))

exact = np.argsort(-(xq @ xb.T), axis=1)[:, :k]
print(f"精确检索基线 Recall@10 = 1.0000,I 形状 {exact.shape}")

if faiss is None:
    print("未安装 faiss:跳过 FAISS 分支,安装 faiss-cpu 后同一脚本会打印两行召回率")
else:
    flat = faiss.IndexFlatIP(d)
    flat.add(xb)
    D_flat, I_flat = flat.search(xq, k)
    print("IndexFlatIP Recall@10 =", round(recall_at_k(I_flat, exact, k), 4),
          "I 形状", I_flat.shape)

    quantizer = faiss.IndexFlatIP(d)
    ivf = faiss.IndexIVFFlat(quantizer, d, 64, faiss.METRIC_INNER_PRODUCT)
    print("训练前 is_trained =", ivf.is_trained)
    ivf.train(xb)
    ivf.add(xb)
    ivf.nprobe = 8
    D_ivf, I_ivf = ivf.search(xq, k)
    print("训练后 is_trained =", ivf.is_trained, "ntotal =", ivf.ntotal)
    print("IndexIVFFlat(nprobe=8) Recall@10 =", round(recall_at_k(I_ivf, exact, k), 4))
xb (20000, 64) xq (200, 64)
精确检索基线 Recall@10 = 1.0000,I 形状 (200, 10)
未安装 faiss:跳过 FAISS 分支,安装 faiss-cpu 后同一脚本会打印两行召回率

这段代码演示 FAISS 的三条契约。第一,向量必须是 float32 且内存连续,np.linalg.norm 的归一化在 float64 上完成后要显式转换。第二,IVF 必须先 train 再 add,训练前 is_trained 为 False,直接 add 会抛出异常;训练样本不足时 FAISS 给出警告,质心质量下降。第三,nprobe 是查询期参数,可在每次查询前修改,IndexFlatIP 没有该参数。search 返回两个数组:D 为得分(内积),I 为下标,形状均为 (nq, k);越界位置以 -1 填充。

由于本机未安装 faiss,输出块只包含 NumPy 基线。安装后同一脚本会多打印 IndexFlatIP 与 IndexIVFFlat 的召回率,二者都应接近 1.0000,因为数据只有 20 个分离良好的簇且已归一化;差异出现在更大规模或更难的数据上。

例 3:内存与压缩估算

n, d = 10 ** 7, 768
raw = n * d * 4
print(f"{n:.0e} 条 {d} 维 float32 向量:{raw / 2**30:.2f} GiB")
print(f"PQ m=96:{n * 96 / 2**30:.2f} GiB,压缩比 {raw / (n * 96):.1f}")
for M in (16, 32, 64):
    graph = n * (2 * M + 1) * 4
    print(f"HNSW M={M}:邻接表 {graph / 2**30:.2f} GiB,合计 {(raw + graph) / 2**30:.2f} GiB")
1e+07 条 768 维 float32 向量:28.61 GiB
PQ m=96:0.89 GiB,压缩比 32.0
HNSW M=16:邻接表 1.23 GiB,合计 29.84 GiB
HNSW M=32:邻接表 2.42 GiB,合计 31.03 GiB
HNSW M=64:邻接表 4.81 GiB,合计 33.42 GiB

估算用于容量规划,不用于精确计费。实际内存还要加上索引对象开销、id 映射、元数据、副本与构建临时空间;HNSW 的邻接表在删除后保留墓碑,实际占用会高于公式值。

易错点

以下六条均可在索引日志、召回实验或内存监控中直接检验。

1. 训练与查询的度量不一致:IVF 用 L2 训练、查询按内积排序,或写入未归一化而查询归一化。检验方法是比较同一批查询在精确内积与索引结果上的前 10 条重合率,若显著低于基线,先检查归一化。

2. 用不具代表性的样本训练 IVF 或 PQ:训练集若来自旧数据或某个租户,其他区域的查询召回率会系统性偏低。训练样本应随机抽取且覆盖线上分布,样本量至少为 的 30 倍。

3. 低选择率下使用后过滤: 时要取 条候选才能得到 10 条结果,延迟放大百倍且可能不足 。应改为预过滤、分区或过滤式遍历。

4. 删除后不重建:墓碑比例上升后,HNSW 的有效节点减少、路径变长,召回率与吞吐同时下降。应在墓碑比例超过 10% 到 20% 时重建,并监控该比例。

5. 只调 而不重建:图结构本身缺少连通边时,增大查询预算只能遍历更多局部节点,召回率不会恢复到目标值。应先增大 与 重建。

6. 跨实现比较延迟:NumPy、faiss-cpu、GPU 实现的常数差异可达两个数量级,用论文或博客的延迟数字做容量规划会严重偏离。所有延迟必须在目标硬件与目标实现上实测。

关联笔记

  • 前置 Embedding与向量检索:本篇的索引以该篇的度量与归一化为前提,内积、余弦与 L2 的等价关系决定了索引度量能否替换。
  • 后续 RAG原理与流程:索引只是检索阶段的一半,召回结果如何进入提示词、如何与生成器配合,在该篇展开。
  • 后续 检索优化与重排Rerank:ANN 返回的候选通常还要经交叉编码器重排,本篇的召回率决定重排的上限。
  • 对照 模型推理优化:两者都在延迟、内存与质量之间取舍,区别在于前者优化检索,后者优化生成。
  • 后续 RAG评估:召回率、延迟与内存的报告方式应与该篇的评估协议一致,否则跨版本比较没有意义。

达标检测

  • [ ] 写出精确检索的时间与空间复杂度,并估算 、 时向量占用的字节数。
  • [ ] 描述 HNSW 的插入过程,说明启发式邻居选择条件 的作用;解释去掉该条件后图结构会如何退化。
  • [ ] 给定 、、,估算 IVF 的候选数与相对暴力检索的加速比。
  • [ ] 计算 、、 时的 PQ 压缩比与 条向量的码大小,并说明 减半的代价。
  • [ ] 用本篇代码把 固定为 4,改变数据簇间间隔,记录召回率变化并解释原因。
  • [ ] 设计一个过滤选择率为 0.5% 的查询场景,比较后过滤与分区的延迟与召回,给出选择依据。

参考来源

  • Malkov & Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs", arXiv:1603.09320, 2018 —— 对应第 3 节的多层图结构、插入与搜索算法、启发式邻居选择与参数分析。
  • Jégou, Douze & Schmid, "Product Quantization for Nearest Neighbor Search", IEEE TPAMI 33(1), 2011 —— 对应第 5 节的分段量化、ADC 距离计算与压缩率分析。
  • Johnson, Douze & Jégou, "Billion-scale similarity search with GPUs", arXiv:1702.08734, 2017 —— 对应 FAISS 的索引组织方式与 GPU 实现,第 8 节的选型对比以其为背景。
  • FAISS 官方文档与 wiki(github.com/facebookresearch/faiss/wiki)—— 对应第 3、4、5 节的索引参数、训练要求与 IndexFlatIP、IndexIVFFlat 的接口。
  • Milvus 官方文档(milvus.io/docs)—— 对应第 8 节的分布式架构、索引类型与标量过滤能力。
  • pgvector 官方仓库(github.com/pgvector/pgvector)—— 对应第 6 节的操作符与索引类绑定、第 8 节的维度上限与事务语义。