インデックスの説明

インデックスはデータの上に構築される付加的な構造である。その内部構造は、使用する近似最近傍探索アルゴリズムに依存する。インデックスは検索を高速化しますが、検索中の前処理時間、スペース、RAMが追加されます。さらに、インデックスを使用すると一般的に想起率が低下する（その影響は無視できるほど小さいが、それでも重要である）。そこで、この記事では、インデックスを使用するコストを最小化しつつ、メリットを最大化する方法について説明する。

概要

Milvusでは、インデックスはフィールドに固有のものであり、対象フィールドのデータ型によって適用可能なインデックスタイプが異なります。Milvusはプロフェッショナルなベクトルデータベースとして、ベクトル検索とスカラーフィルタリングの両方のパフォーマンスを向上させることに重点を置いており、そのために様々なインデックスタイプを提供しています。

以下の表はフィールドデータ型と適用可能なインデックス型の対応関係です。

フィールドデータ型	適用可能なインデックス・タイプ
FLOAT_VECTOR FLOAT16_VECTOR BLOAT16_VECTOR INT8_VECTOR	フラット IVF_FLAT IVF_SQ8 IVF_PQ IVF_RABITQ HNSW HNSW_SQ HNSW_PQ HNSW_PRQ DISKANN SCANN AISAQ GPU_CAGRA GPU_IVF_FLAT GPU_IVF_PQ GPU_ブルートフォース
バイナリベクトル	BIN_FLAT BIN_IVF_FLAT MINHASH_LSH
スパースフロートベクトル	スパース・インバーテッド・インデックス
VARCHAR	INVERTED（推奨） ビットマップ トライ
論理	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

この記事では、適切なベクトル・インデックスの選択方法を中心に説明します。スカラー・フィールドでは、常に推奨されるインデックス・タイプを使用できます。

ベクトル検索に適切なインデックス型を選択することは、パフォーマンスやリソース使用量に大きな影響を与えます。ベクトルフィールドのインデックスタイプを選択する際には、基礎となるデータ構造、メモリ使用量、パフォーマンス要件など、さまざまな要因を考慮することが不可欠です。

ベクトル・インデックスの解剖

下図に示すように、Milvusのインデックスタイプは、データ構造、量子化、リファイナーという3つのコアコンポーネントから構成されています。量子化とリファイナーはオプションですが、コストよりも利益が大きいため、広く使用されています。

ベクトルインデックスの解剖

インデックス作成時、milvusは選択されたデータ構造と量子化方法を組み合わせ、最適な展開率を決定する。クエリ時には、topK × expansion rate 候補ベクトルを検索し、リファイナーを適用してより高い精度で距離を再計算し、最終的に最も正確なtopK 結果を返す。このハイブリッド・アプローチは、リソースを大量に消費する精密化を、フィルタリングされた候補のサブセットに制限することで、速度と精度のバランスをとっている。

データ構造

データ構造はインデックスの基礎となるレイヤーを形成する。一般的なタイプは以下の通り：

• 転置ファイル（IVF）

  IVFシリーズのインデックスタイプは、Milvusがセントロイドベースのパーティショニングによってベクトルをバケットにクラスタリングすることを可能にします。一般に、バケットの重心がクエリベクトルに近ければ、バケット内のすべてのベクトルはクエリベクトルに近いと仮定しても安全です。この前提に基づき、milvusはデータセット全体を調べるのではなく、重心がクエリベクトルに近いバケット内のベクトルの埋め込みのみをスキャンする。この戦略により、許容できる精度を維持しながら計算コストを削減することができる。

  この種のインデックスデータ構造は、高速スループットを必要とする大規模データセットに最適である。

• グラフベース構造

  HNSW（Hierarchical Navigable Small World）のような、ベクトル検索用のグラフベースのデータ構造は、各ベクトルが最近傍のベクトルに接続する階層グラフを構築する。クエリーはこの階層をナビゲートし、粗い上層から始めて下層を切り替えることで、効率的な対数時間の検索複雑性を実現する。

  このタイプのインデックス・データ構造は、高次元空間や低レイテンシーのクエリを必要とするシナリオに優れている。

量子化

量子化は、より粗い表現によってメモリフットプリントと計算コストを削減します：

• スカラー量子化（SQ8など）により、milvusは各ベクトル次元を1バイト（8ビット）に圧縮し、32ビット浮動小数点数と比較してメモリ使用量を75%削減することができます。

• 積量子化(PQ)は、Milvusがベクトルをサブベクトルに分割し、コードブックベースのクラスタリングを用いて符号化することを可能にします。これにより、高い圧縮率（例：4～32倍）が達成され、その代償として再現性がわずかに低下するため、メモリに制約のある環境に適しています。

リファイナー

量子化は本質的に損失が大きい。リコール率を維持するために、量子化は一貫して必要以上のトップK候補を生成するため、リファイナーはより高い精度を使用してこれらの候補からトップK結果をさらに選択し、リコール率を向上させることができます。

例えば、FP32リファイナーは、量子化によって返された検索結果候補に対して、量子化された値ではなくFP32の精度を用いて距離を再計算する操作を行います。

これは、セマンティック検索や推薦システムなど、検索効率と精度のトレードオフを必要とするアプリケーションにおいて重要であり、わずかな距離の変動が結果の品質に大きく影響する。

まとめ

データ構造による粗いフィルタリング、量子化による効率的な計算、そして洗練による精度チューニングという階層化されたアーキテクチャにより、Milvusは精度と性能のトレードオフを適応的に最適化することができる。

性能のトレードオフ

パフォーマンスを評価する場合、ビルド時間、1秒あたりのクエリー数（QPS）、リコール率のバランスが非常に重要です。一般的なルールは以下の通りである：

• グラフベースのインデックスタイプは通常、QPSの点でIVFの亜種を上回る。

• IVFバリアントは特に大きなtopK（例えば2,000以上）のシナリオに適している。

• PQは通常、SQと比較して、同程度の圧縮率でより優れた想起率を提供するが、後者の方がより高速なパフォーマンスを提供する。

• DiskANNのように）インデックスの一部にハードディスクを使用することは、大きなデータセットの管理に役立つが、IOPSのボトルネックになる可能性もある。

容量

容量は通常、データサイズと利用可能なRAMの関係を含む。容量を扱う場合、次のように考える：

• 生データの4分の1がメモリに収まるなら、安定したレイテンシーを持つDiskANNを検討する。

• 生データの4分の1がメモリに収まるなら、安定したレイテンシーを持つDiskANNを検討する。生データがすべてメモリに収まるなら、メモリベースのインデックスタイプとmmapを検討する。

• 量子化を適用したインデックスタイプとmmapを使用することで、精度と最大容量を交換することができます。

リコール

リコールは通常フィルター比率に関係し、検索前にフィルターで除外されるデータを指す。リコールを扱う場合、以下を考慮してください：

• フィルター比率が85%未満の場合、グラフベースのインデックスタイプはIVFの亜種を凌駕する。

• フィルタ比率が 85% から 95% の場合は、IVF variant を使う。

• フィルター比率が 98% 以上なら、最も正確な検索結果を得るために Brute-Force (FLAT) を使う。

パフォーマンス

検索のパフォーマンスには通常、検索が返すレコード数を意味する top-K が含まれます。パフォーマンスを扱う場合、以下のことを考慮してください：

• 高い想起率を必要とする小さなトップK（例えば2,000）の検索では、グラフベースのインデックスタイプはIVFバリアントよりも優れている。

• ベクトル埋め込み総数と比較して）大きなトップKを持つ検索では、グラフベースのインデックスタイプよりもIVFバリアントが良い選択となる。

• top-Kが中程度でフィルタ比率が高い検索では、IVF変種がより良い選択となる。

決定マトリクス最適なインデックスタイプの選択

以下の表は、適切なインデックスタイプを選択する際に参照する決定マトリクスです。

シナリオ	推奨インデックス	備考
生データがメモリに収まる	HNSW、IVF＋リファインメント	低k/高リコールにはHNSWを使用。
ディスク上の生データ、SSD	ディスクANN	レイテンシを重視するクエリに最適。
ディスク上の生データ、限られたRAM	IVFPQ/SQ + mmap	メモリアクセスとディスクアクセスのバランス
高いフィルター比率（95%以上）	ブルートフォース（FLAT）	小さな候補集合のインデックス・オーバーヘッドを回避。
大規模k (データセットの1%以上)	IVF	クラスタ刈り込みにより計算量を削減。
極めて高い想起率 (>99%)	ブルートフォース (FLAT) + GPUs	--

メモリ使用量の推定

インデックスのメモリ消費量は、そのデータ構造、量子化による圧縮率、使用するリファイナーに影響される。一般的に言って、グラフベースのインデックスは、グラフの構造（HNSW など）によりメモリフットプリントが大きくなる。対照的に、IVFとその亜種は、ベクトル毎の空間オーバヘッドが少ないため、メモリ効率が高い。しかし、DiskANNのような高度な技術では、グラフやリファイナーといったインデックスの一部をディスクに常駐させることができるため、性能を維持しながらメモリ負荷を軽減することができる。

具体的には、インデックスのメモリ使用量は以下のように計算できる：

IVFインデックスのメモリ使用量

IVFインデックスは、データをクラスタに分割することで、メモリ効率と検索性能のバランスをとっています。以下は、IVF バリアントを使用してインデックスを作成した 128 次元ベクトル 100 万個が使用するメモリの内訳です。

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を使用し、メモリ使用量は以下のように見積もることができる：

   • PQと8個の副量子化器を使用した場合。

     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 バリアントはしばしばリファイナーとペアになって候補を再ランク付けする。上位10件を検索する検索で、拡張率が5の場合、絞り込みのオーバーヘッドは以下のように見積もられる：

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

グラフベースのインデックスのメモリ使用量

HNSWのようなグラフベースのインデックス・タイプは、グラフ構造と生のベクトル埋め込みを保存するために大きなメモリを必要とします。以下は、HNSWインデックスタイプを使用してインデックス付けされた128次元ベクトル100万個が消費するメモリの詳細な内訳です。

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  
   

   100万個の128次元ベクトル埋め込みをHNSWでインデックス化する場合、使用される総メモリは128 MB (グラフ) + 512 MB (ベクトル) = 640 MBとなります。

3. 量子化による圧縮を計算する。

   量子化はベクトルサイズを縮小します。例えば、8つのサブ量子化器（1ベクトルあたり8バイト）でPQを使用すると、劇的な圧縮につながります。圧縮されたベクトル埋め込みが消費するメモリは以下のように計算できる：

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

   これにより、生のベクトル埋め込みと比較して64倍の圧縮率が達成され、HNSWPQインデックスタイプが使用する総メモリは128MB（グラフ）＋8MB（圧縮ベクトル）＝136MBとなる。

4. 精密化のオーバーヘッドを計算する。

   生のベクトルによる再ランク付けのような絞り込みは、高精度データを一時的にメモリにロードする。上位 10 件を検索する検索で、拡張率が 5 の場合、リファインメントのオーバーヘッドは以下のように見積もることができる：

   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 はメモリに収まらないような大きなデータセットも扱うことができます。これは特に10億ポイントのデータセットに有効です。

メモリ マップ ファイル (mmap)

メモリマッピング(Mmap)により、ディスク上の大容量ファイルへの直接メモリアクセスが可能になり、Milvusはインデックスとデータをメモリとハードディスクの両方に格納することができます。このアプローチは、アクセス頻度に基づくI/Oコールのオーバーヘッドを削減することでI/Oオペレーションを最適化し、検索パフォーマンスに大きな影響を与えることなくコレクションのストレージ容量を拡張します。

具体的には、Milvusは特定のフィールドの生データを完全にメモリにロードするのではなく、メモリマップするように設定することができます。こうすることで、メモリの問題を心配することなくフィールドに直接メモリアクセスすることができ、コレクション容量を拡張することができます。