跳到主要内容

Index 说明

Index 是建立在数据之上的附加结构。其内部结构取决于所使用的近似最近邻搜索算法。Index 可以加速搜索，但会在搜索期间产生额外的预处理时间、空间和 RAM。此外，使用 index 通常会降低召回率（尽管影响可以忽略不计，但仍然很重要）。因此，本文解释了如何在最大化收益的同时最小化使用 index 的成本。

概述​

在 Milvus 中，index 是针对特定 field 的，适用的 index 类型根据目标 field 的数据类型而有所不同。作为专业的向量数据库，Milvus 专注于提高向量搜索和标量过滤的性能，这就是为什么它提供各种 index 类型的原因。

下表列出了 field 数据类型与适用 index 类型之间的映射关系。

Field 数据类型

适用的 Index 类型

  • FLOAT_VECTOR

  • FLOAT16_VECTOR

  • BFLOAT16_VECTOR

  • FLAT

  • IVF_FLAT

  • IVF_SQ8

  • IVF_PQ

  • GPU_IVF_FLAT

  • GPU_IVF_PQ

  • HNSW

  • DISKANN

BINARY_VECTOR

  • BIN_FLAT
  • BIN_IVF_FLAT

SPARSE_FLOAT_VECTOR

SPARSE_INVERTED_INDEX

VARCHAR

  • INVERTED（推荐）

  • BITMAP

  • Trie

BOOL

  • BITMAP（推荐）
  • INVERTED

  • INT8

  • INT16

  • INT32

  • INT64

  • INVERTED
  • STL_SORT
  • FLOAT
  • DOUBLE

INVERTED

ARRAY （BOOL、INT8/16/32/64 和 VARCHAR 类型的元素）

BITMAP（推荐）

ARRAY （BOOL、INT8/16/32/64、FLOAT、DOUBLE 和 VARCHAR 类型的元素）

INVERTED

JSON

INVERTED

本文重点介绍如何选择合适的向量 index。对于标量 field，您始终可以使用推荐的 index 类型。

为向量搜索选择合适的 index 类型可以显著影响性能和资源使用。选择向量 field 的 index 类型时，必须考虑各种因素，包括底层数据结构、内存使用情况和性能要求。

向量 Index 结构​

如下图所示，Milvus 中的 index 类型由三个核心组件组成，即 数据结构、量化 和 细化器。量化和细化器是可选的，但由于收益成本比显著，因此被广泛使用。

Vector Index Anatomy

在 index 创建过程中，Milvus 结合所选的数据结构和量化方法来确定最佳的 扩展率。在查询时，系统检索 topK × 扩展率 个候选向量，应用细化器以更高精度重新计算距离，最后返回最准确的 topK 结果。这种混合方法通过将资源密集型细化限制在经过过滤的候选子集上来平衡速度和精度。

数据结构​

数据结构构成了 index 的基础层。常见类型包括：

  • 倒排文件（IVF）

    IVF 系列 index 类型允许 Milvus 通过基于质心的分区将向量聚类到桶中。通常可以安全地假设，如果桶质心接近查询向量，则桶中的所有向量都可能接近查询向量。基于这一前提，Milvus 仅扫描那些质心靠近查询向量的桶中的向量嵌入，而不是检查整个数据集。这种策略降低了计算成本，同时保持了可接受的准确性。

    这种类型的 index 数据结构非常适合需要快速吞吐量的大规模数据集。

  • 基于图的结构

    用于向量搜索的基于图的数据结构，如分层可导航小世界（HNSW），构建一个分层图，其中每个向量连接到其最近的邻居。查询在这个层次结构中导航，从粗糙的上层开始，然后切换到下层，实现高效的对数时间搜索复杂度。

    这种类型的 index 数据结构在高维空间和要求低延迟查询的场景中表现出色。

量化​

量化通过粗糙表示减少内存占用和计算成本：

  • 标量量化（例如 SQ8）使 Milvus 能够将每个向量维度压缩为单个字节（8位），与 32 位浮点数相比，内存使用量减少 75%，同时保持合理的准确性。

  • 乘积量化（PQ）使 Milvus 能够将向量分割为子向量，并使用基于码本的聚类对其进行编码。这实现了更高的压缩比（例如，4-32倍），代价是召回率略有降低，使其适用于内存受限的环境。

细化器​

量化本质上是有损的。为了保持召回率，量化始终产生比必要数量更多的 top-K 候选，允许细化器使用更高的精度从这些候选中进一步选择 top-K 结果，提高召回率。

例如，FP32 细化器对量化返回的搜索结果候选进行操作，使用 FP32 精度而不是量化值重新计算距离。

这对于需要在搜索效率和精度之间进行权衡的应用程序至关重要，例如语义搜索或推荐系统，其中微小的距离变化显著影响结果质量。

总结​

这种分层架构——通过数据结构进行粗略过滤，通过量化进行高效计算，通过细化进行精度调整——允许 Milvus 自适应地优化准确性-性能权衡。

性能权衡​

评估性能时，平衡 构建时间、每秒查询数（QPS） 和 召回率 至关重要。一般规则如下：

  • 基于图的 index 类型 在 QPS 方面通常优于 IVF 变体。

  • IVF 变体 特别适合 大 topK（例如，超过 2,000） 的场景。

  • PQ 在类似压缩率下通常比 SQ 提供更好的召回率，尽管后者提供更快的性能。

  • 使用硬盘存储部分 index（如 DiskANN）有助于管理大型数据集，但也会引入潜在的 IOPS 瓶颈。

容量​

容量通常涉及数据大小与可用 RAM 之间的关系。处理容量时，请考虑以下几点：

  • 如果四分之一的原始数据适合内存，考虑使用 DiskANN 以获得稳定的延迟。

  • 如果所有原始数据都适合内存，考虑基于内存的 index 类型和 mmap。

  • 您可以使用应用量化的 index 类型和 mmap 来以准确性换取最大容量。

Mmap 并非总是解决方案。当大部分数据在磁盘上时，DiskANN 提供更好的延迟。

召回率​

召回率通常涉及过滤比率，即在搜索前被过滤掉的数据。处理召回率时，请考虑以下几点：

  • 如果过滤比率小于 85%，基于图的 index 类型优于 IVF 变体。

  • 如果过滤比率在 85% 到 95% 之间，使用 IVF 变体。

  • 如果过滤比率超过 98%，使用暴力搜索（FLAT）以获得最准确的搜索结果。

上述条件并非总是正确的。建议您使用不同的 index 类型调整召回率，以确定哪种 index 类型有效。

性能​

搜索的性能通常涉及 top-K，即搜索返回的记录数。处理性能时，请考虑以下几点：

  • 对于需要高召回率的小 top-K（例如 2,000）搜索，基于图的 index 类型优于 IVF 变体。

  • 对于大 top-K（与向量嵌入总数相比）的搜索，IVF 变体是比基于图的 index 类型更好的选择。

  • 对于中等大小的 top-K 和高过滤比率的搜索，IVF 变体是更好的选择。

决策矩阵：选择最合适的 index 类型​

下表是您在选择合适的 index 类型时可以参考的决策矩阵。

场景

推荐 Index

注释

原始数据适合内存

HNSW，IVF + 细化

对于低 k/高召回率使用 HNSW。

原始数据在磁盘上，SSD

DiskANN

对延迟敏感的查询最优。

原始数据在磁盘上，RAM 有限

IVFPQ/SQ + mmap

平衡内存和磁盘访问。

高过滤比率（>95%）

暴力搜索（FLAT）

避免小候选集的 index 开销。

大 k（≥数据集的 1%）

IVF

集群剪枝减少计算。

Memory usage estimation​

内存使用估算​

本节重点介绍如何计算特定索引类型的内存消耗，包含许多技术细节。如果不符合您的兴趣，您可以安全地跳过本节。

索引的内存消耗受其数据结构、通过量化的压缩率以及所使用的细化器影响。一般来说，基于图的索引由于图结构（例如 HNSW）通常具有更高的内存占用，这通常意味着每个向量的显著空间开销。相比之下，IVF 及其变体更节省内存，因为每个向量的空间开销较少。然而，DiskANN 等先进技术允许索引的部分（如图或细化器）驻留在磁盘上，在保持性能的同时减少内存负载。

具体来说，索引的内存使用量可以按如下方式计算：

IVF 索引内存使用​

IVF 索引通过将数据分区为聚类来平衡内存效率和搜索性能。以下是使用 IVF 变体对 100 万个 128 维向量进行索引所使用的内存分解。

  1. 计算质心使用的内存。

    IVF 系列索引类型使 Milvus 能够使用基于质心的分区将向量聚类到桶中。每个质心都以原始向量嵌入的形式包含在索引中。当您将向量分为 2,000 个聚类时，内存使用量可以计算如下：

    2,000 clusters × 128 dimensions × 4 bytes = 1.0 MB

  2. 计算聚类分配使用的内存。

    每个向量嵌入都被分配到一个聚类并存储为整数 ID。对于 2,000 个聚类，2 字节整数就足够了。内存使用量可以计算如下：

    1,000,000 vectors × 2 bytes = 2.0 MB

  3. 计算量化导致的压缩。

    IVF 变体通常使用 PQ 和 SQ8，内存使用量可以估算如下：

    • 使用 8 个子量化器的 PQ

      1,000,000 vectors × 8 bytes = 8.0 MB

    • 使用 SQ8

      1,000,000 vectors × 128 dimensions × 1 byte = 128 MB

    下表列出了不同配置的估计内存使用量：

    配置

    内存估算

    总内存

    IVF-PQ (无细化)

    1.0 MB + 2.0 MB + 8.0 MB

    11.0 MB

    IVF-PQ + 10% 原始细化

    1.0 MB + 2.0 MB + 8.0 MB + 51.2 MB

    62.2 MB

    IVF-SQ8 (无细化)

    1.0 MB + 2.0 MB + 128 MB

    131.0 MB

    IVF-FLAT (完整原始向量)

    1.0 MB + 2.0 MB + 512 MB

    515.0 MB

  4. 计算细化开销。

    IVF 变体通常与细化器配对以重新排序候选项。对于扩展率为 5 的检索前 10 个结果的搜索，细化开销可以估算如下：

    10 (topK) x 5 (expansion rate) = 50 candidates
    50 candidates x 128 dimensions x 4 bytes = 25.6 KB

基于图的索引内存使用​

基于图的索引类型（如 HNSW）需要大量内存来存储图结构和原始向量嵌入。以下是使用 HNSW 索引类型对 100 万个 128 维向量进行索引所消耗内存的详细分解。

  1. 计算图结构使用的内存。

    HNSW 中的每个向量都与其邻居保持连接。图度数（每个节点的边数）为 32 时，消耗的内存可以计算如下：

    1,000,000 vectors × 32 links × 4 bytes (for 32-bit integer storage) = 128 MB

  2. 计算原始向量嵌入使用的内存。

    存储未压缩 FP32 向量消耗的内存可以计算如下：

    1,000,000 vectors × 128 dimensions × 4 bytes = 512 MB

    当您使用 HNSW 对 100 万个 128 维向量嵌入进行索引时，使用的总内存为 128 MB（图）+ 512 MB（向量）= 640 MB。

  3. 计算量化导致的压缩。

    量化减少了向量大小。例如，使用具有 8 个子量化器的 PQ（每个向量 8 字节）会导致急剧压缩。压缩向量嵌入消耗的内存可以计算如下：

    1,000,000 vectors × 8 bytes = 8 MB

    与原始向量嵌入相比，这实现了 64 倍的压缩率，HNSWPQ 索引类型使用的总内存为 128 MB（图）+ 8 MB（压缩向量）= 136 MB。

  4. 计算细化开销。

    细化（如使用原始向量重新排序）会临时将高精度数据加载到内存中。对于扩展率为 5 的检索前 10 个结果的搜索，细化开销可以估算如下：

    10 (topK) x 5 (expansion rate) = 50 candidates
    50 candidates x 128 dimensions x 4 bytes = 25.6 KB

其他考虑因素​

虽然 IVF 和基于图的索引通过量化优化内存使用，但内存映射文件（mmap）和 DiskANN 解决了数据集超过可用随机存取内存（RAM）的场景。

DiskANN​

DiskANN 是一种基于 Vamana 图的索引，它连接数据点以在搜索期间进行高效导航，同时应用 PQ 来减少向量的大小并实现向量之间的快速近似距离计算。

Vamana 图存储在磁盘上，这使 DiskANN 能够处理原本太大而无法放入内存的大型数据集。这对于十亿点数据集特别有用。

内存映射文件（mmap）​

内存映射（Mmap）允许直接内存访问磁盘上的大文件，使 Milvus 能够在内存和硬盘驱动器中存储索引和数据。这种方法通过基于访问频率减少 I/O 调用的开销来帮助优化 I/O 操作，从而在不显著影响搜索性能的情况下扩展 collection 的存储容量。

具体来说，您可以配置 Milvus 对某些字段中的原始数据进行内存映射，而不是将它们完全加载到内存中。这样，您可以获得对字段的直接内存访问，而不必担心内存问题，并扩展 collection 容量。