复合索引：向量搜索的高级策略
在向量搜索领域，我们拥有多种索引方法和向量处理技术，它们使我们能够在召回率、响应时间和内存使用之间做出权衡。虽然单独使用特定技术如倒排文件（IVF）、乘积量化（PQ）或分层导航小世界（HNSW）通常能够带来满意的结果，但为了实现最佳性能，我们往往采用复合索引。
复合索引可以被视为一系列向量转换的逐步过程，它结合了一种或多种索引方法来构建出“理想”的索引。例如，我们可以先使用IVF索引来缩小搜索范围，加速搜索过程，然后引入如PQ的压缩技术，以在维持较大索引的同时，控制其大小在合理的范围内。
虽然自定义索引提供了极大的灵活性，但也存在风险，可能会导致召回率不必要地降低、延迟增高或内存使用增加。因此，为了构建一个健壮且高效的向量相似性搜索应用，理解复合索引的工作原理至关重要。了解何时何地应用不同的索引或向量转换技术，以及何时避免使用它们，对于优化搜索性能至关重要。
在本文中，我们将深入探讨如何利用Facebook AI的相似性搜索工具（Faiss）来构建高性能的复合索引。Faiss是一个广受推崇的强大库，用于创建快速且精确的向量相似性搜索索引。我们还将介绍Faiss的index_factory，这是一个能够以更清晰、更优雅的方式构建复合索引的工具。
什么是复合索引
复合索引的概念可以通过一个有趣的类比来理解：就像乐高积木，每一块都能堆叠在另一块之上，创造出从精美的艺术品到混乱的结构的各种可能性。在Faiss中，复合索引的构建也是类似的，它的各个组件可以自由组合，但并非所有组合都能达到最优效果。
在Faiss中构建复合索引，可以通过以下元素的任意组合来实现：
- 向量变换：这是在索引之前对向量进行的预处理步骤，例如主成分分析（PCA）或优化的量化（OPQ），旨在改善向量的质量或分布。
- 粗量化器：这一步通过将向量分配到不同的子空间，从而初步组织它们。常见的粗量化方法包括倒排文件（IVF）、倒排多索引（IMI）和分层导航小世界（HNSW），它们有助于通过缩小搜索范围来提高搜索效率。
- 细量化器：在粗量化的基础上，细量化器如乘积量化（PQ）进一步压缩向量到更小的域，以减少索引的内存占用，同时尽量保持搜索的准确性。
- 精炼：在搜索过程中，精炼步骤使用原始非压缩向量的距离计算来重新排序搜索结果，以提高搜索的精度。这一步骤也可以通过另一种索引方法来实现。
粗量化的关键优势在于它通过向量“聚类”来实现非详尽搜索，例如IVF中的倒排索引，这可以显著提高搜索效率。而细量化则关注于通过编码技术减少向量的存储需求，同时最小化对搜索准确性的影响。
通过精心选择和组合这些组件，我们可以构建出既高效又精确的复合索引，以满足特定的搜索需求。
索引组件
可以使用以下组件构建复合索引：
| 向量变换 | 粗量化器 | 细量化器 | 精炼 |
|---|---|---|---|
| PCA, OPQ, RR, L2norm, ITQ, Pad | IVF,Flat, IMI, IVF,HNSW, IVF,PQ, IVF,RCQ, HNSW,Flat, HNSW,SQ, HNSW,PQ | Flat, PQ, SQ, Residual, RQ, LSQ, ZnLattice, LSH | RFlat, Refine* |
例如，可以构建一个索引，步骤如下：
- 使用
OPQ对输入向量进行变换； - 利用倒排文件（IVF）进行向量的粗量化，以实现高效的搜索；
- 在每个IVF单元内应用乘积量化（PQ）来压缩向量，减少内存使用；
- 搜索后，使用原始扁平向量（RFlat）重新排序结果，以确保准确性；
在构建复合索引时，由于涉及多种Faiss类，过程可能会显得复杂。为了简化这一过程，Faiss index_factory提供了一种更清晰、更简洁的方法来组合不同的索引组件。
通过合并IVF和PQ索引，可以将PQ量化后的向量存储在IVF结构中，实现更高效的搜索
Faiss Index Factory：简化索引构建流程
Faiss 的 index_factory 函数提供了一种极为简洁的方法来构建复合索引，仅需通过一个字符串参数即可实现。以下是使用 index_factory 替代传统索引构建方法的示例：
传统构建方式：
import faiss
quantizer = faiss.IndexFlatL2(128) # 创建一个128维的L2距离的Flat量化器
index = faiss.IndexIVFFlat(quantizer, 128, 256) # 创建一个使用IVF和Flat的索引
使用 index_factory 的简化方式：
index_f = faiss.index_factory(128, "IVF256,Flat") # 通过字符串参数创建复合索引
注意：在
index_factory示例中，L2 距离没有被明确指定，因为index_factory默认采用 L2 距离。如果需要使用内积距离（IndexFlatIP），可以在index_factory参数中加入faiss.METRIC_INNER_PRODUCT。
性能比较：要验证两种方法构建的索引是否具有相同的性能，首先需要确保它们返回相同��最近邻结果：
k = 100
D, I = index.search(xq, k) # 使用传统方法的索引搜索
D_f, I_f = index_f.search(xq, k) # 使用 `index_factory` 方法的索引搜索
assert I_f.tolist() == I.tolist() # 确保两种方法输出相同的结果
# True
如果两种方法的搜索结果相同，可以进一步比较它们的搜索速度和内存使用情况：
def get_memory(index):
# 将索引写入文件，然后获取文件大小，最后删除文件
faiss.write_index(index, './temp.index')
file_size = os.path.getsize('./temp.index')
os.remove('./temp.index')
return file_size
%%timeit
index.search(xq, k)
# 153 µs ± 7.47 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%%timeit
index_f.search(xq, k)
# 148 µs ± 5.79 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
get_memory(index)
# 520133259
get_memory(index_f)
# 520133259
可以看到，两种方法的搜索速度非常接近，index_factory 版本的搜索速度略快约 5 微秒，这个差异几乎可以忽略不计。在内存使用方面，两种方法也表现出了相同的效率。
召回率计算：召回率是衡量搜索性能的一个重要指标，它表示在顶部 k 个结果中返回的匹配项所占的比例。在文献中，通常使用 recall@k 来表示在顶部 k 个返回记录中，查询的最近邻被返回的百分比。例如，如果以 100 为 k 值，并且在 50% 的查询中返回了正确的最近邻，那么可以说 recall@100 的性能是 0.5。
为什么使用Index Factory
尽管测试结果表明两种索引构建方法在性能上是一致的，但掌握如何使用 index_factory 仍然具有其独特的价值和优势。以下是选择使用 index_factory 的几个关键理由：
- 个人偏好：如果您更倾向于传统的基于类的索引构建方法，完全可以继续使用它。
- 代码简洁性：
index_factory显著提高了代码的简洁性和可读性。原本需要多行代码实现的功能，现在可以用一行简洁的代码来完成。
以下是一个使用 index_factory 构建复合索引的例子：
使用传统方法构建复合索引：
- 使用 OPQ 对向量进行预处理
- 利用 IVF 对向量进行聚类
- 应用 PQ 量化以减少索引大小
- 使用扁平索引对最终结果进行重新排序
d = xb.shape[1] # 向量的维度
m = 32 # OPQ的子空间数量
nbits = 8 # PQ量化的位数
nlist = 256 # IVF的列表数量
# 初始化OPQ和粗量化+细量化步骤
opq = faiss.OPQMatrix(d, m)
vecs = faiss.IndexFlatL2(d) # 扁平量化器
sub_index = faiss.IndexIVFPQ(vecs, d, nlist, m, nbits) # IVF + PQ
# 将预处理、粗量化、细量化步骤合并
index = faiss.IndexPreTransform(opq, sub_index)
# 添加最终的精炼步骤
index = faiss.IndexRefineFlat(index)
# 训练索引并添加向量
index.train(xb)
index.add(xb)
使用 index_factory 简化后的代码：
d = xb.shape[1] # 默认参数：m=32, nlist=256, nbits=8
# 使用index_factory构建相同功能的索引
index = faiss.index_factory(d, "OPQ32,IVF256,PQ32,RFlat")
# 训练索引并添加向量
index.train(xb)
index.add(xb)
性能对比：
| 方法 | 召回率 | 搜索时间 | 内存使用 |
|---|---|---|---|
| 传统方法 | 31% | 181µs | 552MB |
| index_factory | 31% | 174µs | 552MB |
使用 index_factory 构建的索引在搜索时间上通常会略快一些，尽管这种差异非常微小。两种方法在召回率和内存使用方面表现一致。
流行的复合索引
IVFADC
在掌握了使用 index_factory 快速构建复合索引的方法后，让我们探索一些流行且性能卓越的索引组合。其中，IVFADC 是一个值得关注的索引类型。
IVFADC 索引简介： IVFADC，即倒排文件量化异构距离计算，是一个自2010年引入以来广泛使用的索引。它结合了倒排文件（IVF）和乘积量化（PQ）技术，以其合理的召回率、快速的搜索速度和高效的内存使用而受到青睐。尽管召回性能不是最优，但IVFADC 在最小化内存使用的同时，仍能保持快速的搜索速度。
IVFADC 索引构建步骤：
- 向量被分配到 IVF 结构中的不同列表（或 Voronoi 单元）。
- 使用 PQ 压缩这些向量。
IVFADC 的索引过程
在索引构建完成后，对查询向量 xq 和已索引、量化的向量之间进行不对称距离计算（ADC）。这种搜索被称为不对称，因为它比较未压缩的 xq 与之前压缩的 PQ 向量。
通过对称距离计算（SDC，左），在将
xq与之前量化的xb向量进行比较之前对其进行量化。 ADC（右）跳过xq的量化，并将其直接与量化的xb向量进行比较。
通过 index_factory 实现 IVFADC 索引的代码如下：
index = faiss.index_factory(d, "IVF256,PQ32x8")
index.train(xb)
index.add(xb)
D, I = index.search(xq, k)
recall(I) # 30
在这个示例中，创建了一个具有 256 个 IVF 单元的 IVFADC 索引，每个向量都使用 PQ 压缩，其中 m 和 nbits 的值分别为 32 和 8。PQ 默认使用 nbits == 8，因此可以简写为 "IVF256,PQ32"。这里：
m：原始向量分割成的子向量数量。nbits：每个子量化器使用的位数，它决定了每个子量化器的中心点数量为 2nbits2^{nbits}2nbits。
通过调整 nbits，可以减少索引的内存使用或提高召回率和搜索速度。然而，当前版本的 Faiss 限制了 IVF,PQ 的 nbits 必须大于或等于 8。此外，通过增加 index.nprobe 值，可以搜索更多的 IVF 单元（默认值为 1）。
index.nprobe = 8
D, I = index.search(xq, k)
recall(I) # 74
不同 nbits 和 nprobe 值对索引性能的影响如下：
| 索引 | nprobe | 召回率 | 搜索时间 | 内存使用 |
|---|---|---|---|---|
| IVF256,PQ32x4 | 1 | 27% | 329µs | 25MB |
| IVF256,PQ32x4 | 6 | 45% | 975µs | 25MB |
| IVF256,PQ32x8 | 1 | 30% | 136µs | 40MB |
| IVF256,PQ32x8 | 8 | 74% | 729µs | 40MB |
优化的 PQ 量化：提升 IVFADC 索引性能
优化的乘积量化（OPQ）技术能显著提升采用乘积量化（PQ）的索引，如 IVFADC。OPQ 通过旋转向量来优化 PQ 中子空间的值分布，特别适合处理数据分布不均匀的情况。
在 Faiss 中，OPQ 作为一个预处理步骤，可以轻松地整合到 IVFADC 中：
# 使用 OPQ 改进 PQ 步骤的分布
index = faiss.index_factory(d, "OPQ32,IVF256,PQ32x8")
index.train(xb)
index.add(xb)
D, I = index.search(xq, k)
recall(I) # 31
%%timeit
index.search(xq, k)
# 142 µs ± 2.25 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
这里的 OPQ32 和 PQ32 中的数字 32 指的是 PQ 编码的位数 m。在 Faiss 中，OPQ 仅包含旋转部分，必须结合后续的 PQ 步骤才能实现完整的 OPQ 功能。索引在初始化时进行训练。
对于像 Sift1M 这样数据分布已经相对均衡的数据集，使用 OPQ 也能观察到轻微的召回性能提升。例如，当 nprobe == 1 时，召回率可以从 30% 提高到 31%。
为了进一步提高召回率，可以增加 nprobe 的值，但这可能会牺牲一些搜索速度。由于添加了预处理步骤，不能直接通过 index.nprobe 访问 nprobe，因为索引不再直接对应于 IVF 部分。要修改 nprobe 值，需要先提取 IVF 索引：
ivf = faiss.extract_index_ivf(index)
ivf.nprobe = 13
D, I = index.search(xq, k)
recall(I) # 74
%%timeit
index.search(xq, k)
# 1.08 ms ± 21.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
当 nprobe 值设置为 13 时，召回率可以达到 74%，但搜索时间从 729μs 增加到 1060μs。
不同 nprobe 值下的索引性能对比：
| 索引 | nprobe | 召回率 | 搜索时间 | 内存使用 |
|---|---|---|---|---|
| OPQ32,IVF256,PQ32x4 | 1 | 30% | 136µs | 40.2MB |
| OPQ32,IVF256,PQ32x4 | 1 | 31% | 143µs | 40.3MB |
| OPQ32,IVF256,PQ32x8 | 8 | 74% | 729µs | 40.2MB |
| OPQ32,IVF256,PQ32x8 | 13 | 74% | 1060µs | 40.3MB |
各种
nprobe值的搜索时间（上）和召回率（下）
此外，OPQ 还可以用来降低预处理步骤中向量的维度。维度 D 必须是 M 的倍数，理想情况下 D==4M。例如，要将维度减少到 64，可以使用以下索引字符串：
index = faiss.index_factory(64, "OPQ16_64,IVF256,PQ16")
多维ADC：提升搜索效率的索引技术
多维ADC（Asymmetric Distance Computation）是一种先进的索引技术，它融合了多维索引结构和搜索过程中的不对称距离计算（特别是乘积量化PQ）。这种索引技术基于倒排多索引（IMI），是倒排文件（IVF）技术的扩展。与IVF相比，IMI在召回率和搜索速度上都有显著提升，但这需要以增加内存使用为代价。
IMI索引非常适合于那些需要高召回率和快速搜索，同时可以容忍较高内存消耗的应用场景。IMI的工作方式与IVF相似，但它在向量的不同维度上分割了Voronoi单元，形成了一种多级Voronoi单元结构，这有助于更精细地组织数据。
Voronoi细胞在多个向量子空间上被分割，给定一个查询向量
xq，将比较每个xq子向量到其相应的子空间细胞
当PQ压缩技术应用于IMI时，就形成了多维ADC索引。在这种索引中，ADC指的是在查询向量与量化后的向量比较时进行的对称距离计算。使用Faiss的index_factory可以方便地创建此类索引：
index = faiss.index_factory(d, "IMI2x8,PQ32")
index.train(xb)
index.add(xb)
# 提取 IMI 索引并设置 nprobe
imi = faiss.extract_index_ivf(index)
imi.nprobe = 620
D, I = index.search(xq, k)
recall(I) # 72
%%timeit
index.search(xq, k)
# 1.35 ms ± 60.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
尽管多维ADC索引能提供72%的召回率，但搜索时间增加到了1.35毫秒，相对较慢。然而，通过将优化的乘积量化（OPQ）整合到索引中，可以显著提高性能：
index = faiss.index_factory(d, "OPQ32,IMI2x8,PQ32")
index.train(xb)
index.add(xb)
# 增加nprobe
imi = faiss.extract_index_ivf(index)
imi.nprobe = 100
D, I = index.search(xq, k)
recall(I) # 74
%%timeit
index.search(xq, k)
# 461 µs ± 30 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
通过这种方式，OPQ multi-D-ADC 索引在保持 74% 召回率的同时，将平均搜索时间降低到了 461 微秒。
| 索引 | 召回率 | 搜索时间 | 内存使用 |
|---|---|---|---|
| IVF256,PQ32 | 74% | 729µs | 40.2MB |
| IMI2x8,PQ32 | 72% | 1350µs | 40.8MB |
| OPQ32,IMI2x8,PQ32 | 74% | 461µs | 40.7MB |
通过调整nprobe的值，可以在召回率和搜索速度之间取得平衡。
各种
nprobe值的搜索时间（顶部）和召回率（底部）
HNSW索引：结合速度与召回率的强有力复合索引
层次可导航的小世界（HNSW）图与倒排文件（IVF）的结合，构成了一种功能强大的复合索引。这种组合不仅在速度上与先前的索引方法相媲美，还在提高召回率方面表现突出，尽管这需要更多的内存使用。
HNSW基于小世界网络理论，该理论指出，无论网络规模大小，所有顶点都可以在少数几步内相互到达。这一特性使得HNSW在构建索引时能够实现快速搜索，同时保持高精度。
HNSW图将典型包含长程和短程链接的图分解成多个层（层次结构）。在搜索过程中，从最高层开始，这一层由长程链接组成。当穿过每一层时，链接变得更加细致。
HNSW图将包含长程和短程链接的图分解成多个层，每一层由不同类型的链接组成。搜索从高层的长程链接开始，随着向下移动，逐渐增加短程链接，使得搜索过程既快速又精确。
将HNSW与IVF结合，可以通过IVF快速识别出近似最近的单元格中心点，然后将详尽搜索限制在这些单元格内。这种策略最小化了搜索时间，同时保持了高召回率。
HNSW可以快速使用IVF单元格中心点找到近似最近邻
为了实现这一目标，需要调整IVF的参数，使用更多的中心点和更小的单元格。例如，对于一个1M的索引，建议将nlist设置为65536，并提供至少1.97M的向量给index.train。实践中，较小的nlist值如4096可能更适合，并且能够提供更高的召回率。
使用 index_factory 可以构建标准的 IVF+HNSW 索引：
index = faiss.index_factory(d, "IVF4096_HNSW32,Flat")
index.train(xb)
index.add(xb)
D, I = index.search(xq, k)
recall(I) # 25
%%timeit
index.search(xq, k)
# 58.9 µs ± 3.25 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
index.nprobe = 146
D, I = index.search(xq, k)
recall(I) # 100
%%timeit
index.search(xq, k)
# 916 µs ± 9.23 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
通过调整nprobe的值，可以在搜索时间和召回率之间进行权衡。例如，将nprobe设置为146可以将召回率提高到100%，但搜索时间会相应增加。
各种
nprobe值的搜索时间（顶部）和召回率（底部）
尽管IVF+HNSW索引在内存使用上较高，但它提供了惊人的召回率和快速的搜索速度。如果需要减少内存使用，可以考虑使用PQ或OPQ来压缩向量，但这可能会降低召回率并增加搜索时间。
| 索引 | 召回率 | 搜索时间 | 内存使用 |
|---|---|---|---|
| IVF4096_HNSW,Flat | 90% | 550µs | 523MB |
| IVF4096_HNSW,PQ32 (PQ) | 69% | 550µs | 43MB |
| OPQ32,IVF4096_HNSW,PQ32 (OPQ) | 74% | 364µs | 43MB |
在选择索引时，需要根据具体的应用场景和性能需求来权衡召回率、搜索时间和内存使用。如果可以接受较低的召回率以减少搜索时间和内存使用，带有OPQ的IVF+HNSW索引可能是一个理想的选择。
| 名称 | 索引 | 召回率 | 搜索时间 | 内存 |
|---|---|---|---|---|
| IVFADC | IVF256,PQ32 | 74% | 729µs | 40MB |
| Multi-D-ADC | OPQ32,IMI2x8,PQ32 | 74% | 461µs | 41MB |
总结
在本文中，我们深入探讨了复合索引的概念，并展示了如何使用 Faiss 强大的 index_factory 工具来构建高效、定制化的索引结构。重点介绍了三种业界广泛认可的复合索引类型：
- IVFADC：这种索引类型结合了倒排文件（IVF）和乘积量化（PQ），在内存使用合理的前提下，提供了均衡的召回率和搜索速度。
- Multi-D-ADC：基于倒排多索引（IMI），它在召回率和搜索速度上超越了传统的 IVF，尽管这需要更多的内存。
- IVF-HNSW：通过将 IVF 与层次可导航的小世界（HNSW）图结合，这种索引实现了高召回率和快速搜索，但代价是更高的内存使用。
通过对 Sift1M 数据集进行索引和搜索的实践，学习了如何调整各个索引参数，以适应不同的业务需求。这包括在召回率、搜索速度和内存使用之间找到合适的平衡点。
希望本文的介绍能够帮助读者深入理解复合索引的内部机制，并掌握如何设计和测试适合自己特定业务场景的索引结构。
参考
- Composite Indexes in Faiss
- Product Quantization Explained (Video)
- Advanced Faiss Indexing (Video)
- Approximate Nearest Neighbor Search by Residual Vector Quantization
- A Survey of Product Quantization
- Optimized Product Quantization
- Product quantization for nearest neighbor search
- Searching in One Billion Vectors: Re-rank with Source Coding
- Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors
- Guidelines to choose an index
- The Index Factory
转载自:https://juejin.cn/post/7390341683601047592