ベクターインデックス
このトピックでは、StarRocks のベクターインデックス機能とそれを使用した近似最近傍探索 (ANNS) の方法について紹介します。
ベクターインデックス機能は、v3.4 以降の共有なしクラスタでのみサポートされています。
概要
現在、StarRocks はセグメントファイルレベルでのベクターインデックスをサポートしています。インデックスは各検索項目をセグメントファイル内の行 ID にマッピングし、ベクトル距離の計算を行わずに対応するデータ行を直接特定することで高速なデータ取得を可能にします。システムは現在、Inverted File with Product Quantization (IVFPQ) と Hierarchical Navigable Small World (HNSW) の 2 種類のベクターインデックスを提供しており、それぞれ独自の組織構造を持っています。
Inverted File with Product Quantization (IVFPQ)
Inverted File with Product Quantization (IVFPQ) は、大規模な高次元ベクトルにおける近似最近傍探索の手法であり、ディープラーニングや機械学習のベクトル検索タスクで一般的に使用されます。IVFPQ は、インバーテッドファイルとプロダクト量子化の 2 つの主要なコンポーネントで構成されています。
- インバーテッドファイル: これはインデックス作成方法です。データセットを複数のクラスタ(またはボロノイセル)に分割し、各クラスタにセントロイド(シードポイント)を持たせ、各データポイント(ベクトル)を最も近いクラスタセンターに割り当てます。ベクトル検索では、IVFPQ は最も近いクラスタのみを検索するため、検索範囲と複雑さが大幅に削減されます。
- プロダクト量子化: これはデータ圧縮技術です。高次元ベクトルをサブベクトルに分割し、各サブベクトルを量子化して、事前定義されたセット内の最も近いポイントにマッピングします。これにより、ストレージと計算コストを削減しつつ、高精度を維持します。
インバーテッドファイルとプロダクト量子化を組み合わせることで、IVFPQ は大規模で高次元のデータセットにおける効率的な近似最近傍探索を可能にします。
Hierarchical Navigable Small World (HNSW)
Hierarchical Navigable Small World (HNSW) は、高次元最近傍探索のためのグラフベースのアルゴリズムであり、ベクトル検索タスクでも広く使用されています。
HNSW は階層的なグラフ構造を構築し、各層がナビゲーブルスモールワールド (NSW) グラフです。グラフ内では、各頂点がデータポイントを表し、エッジが頂点間の類似性を示します。グラフの上位層は少ない頂点と疎な接続を持ち、迅速なグローバル検索を可能にし、下位層はすべての頂点と密な接続を持ち、正確なローカル検索を可能にします。
ベクトル検索では、HNSW は最初に最上層で検索を行い、近似最近傍領域を迅速に特定し、その後層を下っていき、最下層で正確な最近傍を見つけます。
HNSW は効率性と精度の両方を提供し、さまざまなデータとクエリの分布に適応します。
IVFPQ と HNSW の比較
- データ圧縮率: IVFPQ はより高い圧縮率(約 1:0.15)を持ちます。インデックス計算は、PQ がベクトルを圧縮するため、粗いランク付けの後に予備的なソート結果を提供するだけです。最終的なソート結果には追加の詳細なランク付けが必要であり、計算と遅延が増加します。HNSW はより低い圧縮率(約 1:0.8)を持ち、追加の処理なしで正確なランク付けを提供し、計算コストと遅延が低く、ストレージコストが高くなります。
- リコール調整: 両方のイン デックスは、パラメータ調整を通じてリコール率の調整をサポートしていますが、IVFPQ は同様のリコール率でより高い計算コストがかかります。
- キャッシング戦略: IVFPQ はインデックスブロックのキャッシュ割合を調整することでメモリコストと計算遅延をバランスさせることができますが、HNSW は現在、フルファイルキャッシングのみをサポートしています。
使用方法
各テーブルは 1 つのベクターインデックスのみをサポートします。
前提条件
ベクターインデックスを作成する前に、FE 設定項目 enable_experimental_vector
を true
に設定して有効にする必要があります。
次のステートメントを実行して動的に有効にします。
ADMIN SET FRONTEND CONFIG ("enable_experimental_vector" = "true");
永続的に有効にするには、FE 設定ファイル fe.conf
に enable_experimental_vector = true
を追加し、FE を再起動する必要があります。
ベクターインデックスの作成
このチュートリアルでは、テーブルを作成しながらベクターインデックスを作成します。既存のテーブルにベクターインデックスを追加することもできます。詳細な手順については、Append vector index を参照してください。
-
次の例では、テーブル
hnsw
のカラムvector
に HNSW ベクターインデックスhnsw_vector
を作成します。CREATE TABLE hnsw (
id BIGINT(20) NOT NULL COMMENT "",
vector ARRAY<FLOAT> NOT NULL COMMENT "",
INDEX hnsw_vector (vector) USING VECTOR (
"index_type" = "hnsw",
"dim"="5",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"M" = "16",
"efconstruction" = "40"
)
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1; -
次の例では、テーブル
ivfpq
のカラムvector
に IVFPQ ベクターインデックスivfpq_vector
を作成します。CREATE TABLE ivfpq (
id BIGINT(20) NOT NULL COMMENT "",
vector ARRAY<FLOAT> NOT NULL COMMENT "",
INDEX ivfpq_vector (vector) USING VECTOR (
"index_type" = "ivfpq",
"dim"="5",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"nbits" = "16",
"nlist" = "40"
)
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1;
インデックス構築パラメータ
USING VECTOR
- デフォルト: N/A
- 必須: はい
- 説明: ベクターインデックスを作成します。
index_type
- デフォルト: N/A
- 必須: はい
- 説明: ベクターインデックスタイプ。 有効な値:
hnsw
とivfpq
。
dim
- デフォルト: N/A
- 必須: はい
- 説明: インデックスの次元。インデックスが構築された後、次元要件を満たさないベクトルはベースカラムへのロードが拒否されます。
1
以上の整数である必要があります。
metric_type
- デフォルト: N/A
- 必須: はい
- 説明: ベクターインデックスのメトリックタイプ(測定関数)。有効な値:
l2_distance
: ユークリッド距離。値が小さいほど、類似性が高くなります。cosine_similarity
: コサイン類似度。値が大きいほど、類似性が高くなります。
is_vector_normed
- デフォルト: false
- 必須: いいえ
- 説明: ベクトルが正規化されているかどうか。 有効な値は
true
とfalse
です。metric_type
がcosine_similarity
の場合にのみ有効です。ベクトルが正規化されている場合、計算された距離の値は [-1, 1] の範囲内になります。ベクトルは平方和が1
である必要があります。そうでない場合、エラーが返されます。
M
- デフォルト: 16
- 必須: いいえ
- 説明: HNSW 固有のパラメータ。グラフ構築中に新しい要素ごとに作成される双方向接続の数。
2
以上の整数である必要があります。M
の値は、グラフ構築と検索の効率と精度に直接影響します。グラフ構築中、各頂点は最も近いM
個の頂点との接続を確立しようとします。頂点がすでにM
個の接続を持っている場合でも、より近い頂点が見つかった場合、最も遠い接続が削除され、より近い頂点との新しい接続が確立されます。ベクトル検索はエントリーポイントから開始し、それに接続された頂点に沿って最も近い隣接点を見つけます。したがって、M
の値が大きいほど、各頂点の検索範囲が広がり、検索効率が向上しますが、グラフ構築とストレ ージのコストも増加します。
efconstruction
- デフォルト: 40
- 必須: いいえ
- 説明: HNSW 固有のパラメータ。最も近い隣接点を含む候補リストのサイズ。
1
以上の整数である必要があります。グラフ構築プロセス中の検索深度を制御するために使用されます。具体的には、efconstruction
はグラフ構築プロセス中の各頂点の検索リスト(候補リストとも呼ばれる)のサイズを定義します。この候補リストは、現在の頂点の隣接候補を格納するために使用され、リストのサイズはefconstruction
です。efconstruction
の値が大きいほど、グラフ構築プロセス中に頂点の隣接候補として考慮される候補が増え、その結果、グラフの品質(接続性の向上など)が向上しますが、グラフ構築の時間消費と計算の複雑さも増加します。
nbits
- デフォルト: 16
- 必須: いいえ
- 説明: IVFPQ 固有のパラメータ。プロダクト量子化 (PQ) の精度。
8
の倍数である必要があります。IVFPQ では、各ベクトルが複数のサブベクトルに分割され、各サブベクトルが量子化されます。Nbits
は量子化の精度を定義し、各サブベクトルが何ビットに量子化されるかを示します。nbits
の値が大きいほど、量子化の精度が高くなりますが、ストレージと計算コストも増加します。
nlist
- デフォルト: 16
- 必須: いいえ
- 説明: IVFPQ 固有のパラメータ。クラスタの数、またはインバーテッドリストの数。
1
以上の整数である必要があります。IVFPQ では、データセットがクラスタに分割され、各クラスタのセントロイドがインバーテッドリストに対応します。ベクトル検索は、最初にデータポイントに最も近いクラスタセントロイドを見つけ、その後、対応するインバーテッドリスト内で最も近い隣接点を取得します。したがって、nlist
の値は検索の精度と効率に影響を与えます。nlist
の値が大きいほど、クラスタリングの粒度が細かくなり、検索精度が向上しますが、検索の複雑さも増加します。
M_IVFPQ
- 必須: はい
- 説明: IVFPQ 固有のパラメータ。元のベクトルが分割されるサブベクトルの数。IVFPQ インデックスは、
dim
次元のベクトルをM_IVFPQ
等長のサブベクトルに分割します。したがって、dim
の値の因数である必要があります。
ベクターインデックスの追加
既存のテーブルにベクターインデックスを追加するには、CREATE INDEX または ALTER TABLE ADD INDEX を使用します。
例:
CREATE INDEX ivfpq_vector
ON ivfpq (vector)
USING VECTOR (
"index_type" = "ivfpq",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"dim"="5",
"nlist" = "256",
"nbits"="10"
);
ALTER TABLE ivfpq
ADD INDEX ivfpq_vector (vector)
USING VECTOR (
"index_type" = "ivfpq",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"dim"="5",
"nlist" = "256",
"nbits"="10"
);
ベクターインデックスの管理
ベクターインデックスの表示
SHOW CREATE TABLE ステートメントを使用して、ベクターインデックスの定義を表示できま す。
例:
mysql> SHOW CREATE TABLE hnsw \G
*************************** 1. row ***************************
Table: hnsw
Create Table: CREATE TABLE hnsw (
id bigint(20) NOT NULL COMMENT "",
vector array<float> NOT NULL COMMENT "",
INDEX index_vector (vector) USING VECTOR("dim" = "5", "efconstruction" = "40", "index_type" = "hnsw", "is_vector_normed" = "false", "M" = "512", "metric_type" = "l2_distance") COMMENT ''
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1
PROPERTIES (
"compression" = "LZ4",
"fast_schema_evolution" = "true",
"replicated_storage" = "false",
"replication_num" = "3"
);
1 row in set (0.00 sec)
ベクターインデックスの削除
DROP INDEX または ALTER TABLE DROP INDEX を使用してベクターインデックスを削除できます。
DROP INDEX ivfpq_vector ON ivfpq;
ALTER TABLE ivfpq DROP INDEX ivfpq_vector;
ベクターインデックスを使用した ANNS の実行
ベクター検索を実行する前に、FE 設定項目 enable_experimental_vector
が true
に設定されていることを確認してください。