はじめに
Elasticsearchで密ベクトル検索を行う場合、Elasticsearch 9.1.0からbbq_hnswを使った検索がデフォルトになりました。
このブログでは、bbq_hnswの基礎について解説します。
対象読者
- Elasticsearchでベクトル検索を始める予定の方
- Elasticsearchの初心者～中級者
対象バージョン
- Elasticsearch 8.x（8.18.0以降、bbqとrescore_vectorが利用可能なバージョン）
- Elasticsearch 9.x
量子化を利用しない密ベクトル検索
まず、量子化を行わない密ベクトル検索について考えてみましょう。
Elasticsearchで密ベクトル検索を行う場合、通常は検索対象となるテキストのfloat32ベクトルを格納します。
量子化を行わない場合のストレージ
密ベクトルの量子化を行わない場合、Elasticsearchのストレージには、主に以下のデータが格納されます。
- ドキュメントのテキストデータ（text、keyword、longなど）
- ドキュメントをキーワード検索するための転置インデックス
- float32型の密ベクトル
（上記は簡略化した内容です）
超概略図（細かい部分は省略しています）
ベクトル検索に必要なメモリ量
量子化を行わない密ベクトル検索では、全ベクトルのデータをメモリ上に保持して検索を行います。これにより、高速なベクトル検索が可能になります。
では、float32型の密ベクトルを使う場合に、どのくらいのメモリが必要になるか概算してみましょう。
例：検索対象の密ベクトルの総数 = 1億個、次元数 = 2048の場合
ベクトルの1要素は、4バイト(float32)なので、
必要なメモリサイズ（概算）=1億個 * 2048 * 4バイト = 1億個 * 8192バイト = 約800GB
この場合、密ベクトル検索には約800GBのRAMが必要となります。これは非常に大きなメモリ量です。
量子化を利用した密ベクトル検索
次に、ベクトルを量子化して密ベクトル検索を行う場合を考えます。
量子化を一言で説明すると、ベクトルの圧縮 です。
量子化の種類
圧縮の度合いに応じて、いくつかの量子化手法があります。Elasticsearchでは数種類の量子化を利用可能です。
詳細は、Elasticsearchの公式ドキュメント をご覧ください。
- int8: 1つのベクトル要素を1バイトで表現します。（Elasticsearch 9.0.x までのデフォルト）
- int4: 1つのベクトル要素を1/2バイトで表現します。
- bbq: 1つのベクトル要素を1ビット（1/8バイト）で表現します。（Elasticsearch 9.1.0以降のデフォルト）
bbqについての詳細は、Better Binary Quantization in Lucene and Elasticsearch をご覧ください。
量子化のデフォルトについては、Elasticsearch の公式ドキュメント (Dense vector field type) を参照してください。
量子化を行う場合のストレージ
量子化を行う場合、Elasticsearchのストレージには、元のデータに加えて量子化された密ベクトルが追加で格納されます。
- ドキュメントのテキストデータ（text、keyword、longなど）
- ドキュメントをキーワード検索するための転置インデックス
- float32型の密ベクトル
- 量子化された密ベクトル
超概略図（細かい部分は省略しています）
このため、量子化された密ベクトルの分だけストレージサイズは大きくなりますが、このデメリットを上回る大きなメリットが得られます（後述）。
ベクトル検索に必要なメモリ量
量子化を行った場合、元のベクトルデータをすべてメモリ上に保持する必要はありません。その代わりに、圧縮された全ベクトルデータをメモリ上に保持します。
量子化の種類によって必要なメモリサイズは異なりますが、ここではbbqを使った場合で計算してみましょう。
bbq量子化を行った場合のメモリサイズは、以下の計算式で求められます（条件は、前述と同じく1億件で2048次元とします）。
メモリサイズ=1億個 * (2048/8 + 14) + 1億個 * 4 * 16 = 334億バイト = 約 32.6GB
この計算式は Elasticsearchの公式ドキュメント に記載されています。
量子化しない場合に必要なメモリが800GBだったのに対し、bbqを使えばわずか32.6GBに抑えられます。これは驚くべき削減効果です。
量子化のメリット・デメリット
メリット
- 検索に必要なメモリ量を大幅に削減できます。
- 検索処理に必要なCPUリソースも削減できます。
デメリット
- 量子化されたベクトルの分だけ、ストレージの消費量が増えます。
- ベクトルを圧縮するため、検索精度がわずかに低下する可能性があります。
この検索精度の低下を抑えるために、Elasticsearchでは、量子化されたベクトルで検索を行った後、検索結果の上位n件に対して量子化前のfloat32ベクトルを使って再検索を行う機能を提供しています。（複数のシャードに分かれて格納されている場合は、シャードごとに再検索された後、マージされます。）
詳細は、Dense Vector kNN Search Rescoring をご覧ください。
bbq量子化を利用する場合、再検索は本来取得したい件数の3〜5倍の検索結果に対して行うことが推奨されています。
なお、int8量子化の場合、再検索の必要性はそれほど高くないとされています。
まとめ
ここまでの内容を整理しましょう。
- Elasticsearchは、密ベクトル検索において量子化によるメモリ削減を推奨しています。
- Elasticsearch 9.1.0からは、密ベクトル検索のデフォルトとしてbbqによる量子化が採用されました。
- Elasticsearchで検索用に密ベクトルを保持する場合、ストレージにはfloat32ベクトルと量子化されたベクトル（bbqなど）の両方が格納されます。
- bbqで量子化されたベクトルを使って検索する場合、必要なメモリ量は、元のベクトルをそのまま使う場合に比べて大幅に削減されます。
- bbqで量子化されたベクトルを使う場合、検索精度の低下を防ぐために、上位n件に対して元のベクトルを使った再検索を行うことが推奨されます。推奨されるnの値は、取得したい件数の3〜5倍です。
次回予告
次回は、実際にbbqベクトルを使った密ベクトル検索を試してみましょう。
