PolarDB:高次元ベクトル検索（PASE）

IVFFlat

IVFFlat は IVFADC アルゴリズムの簡略化版です。k 平均法（k-means）を用いてベクトルをクラスタリングし、クエリベクトルに最も近いクラスターのみを検索することで、遠方のクラスターをスキップして検索を高速化します。精度は検索対象となるクラスター数に比例するため、直接チューニング可能です。

IVFFlat の動作原理：

1. IVFFlat は k 平均法を適用してベクトルをクラスターにグループ化し、各クラスターに重心（centroid）を割り当てます。

2. クエリベクトルに最も近い n 個の重心を特定します。

3. これらの n 個のクラスター内のすべてのベクトルを走査・順位付けし、最も近い k 個のベクトルを返します。

n の値を大きくすると精度は向上しますが、計算負荷も増加します。IVFADC とは異なり、IVFFlat はフェーズ 2 で積量子化（product quantization）を用いず、力まかせ探索（brute-force search）を採用するため、精度とパフォーマンスのトレードオフを直接制御できます。

HNSW

HNSW は、ナビゲーブル・スモールワールド（NSW）アルゴリズムを用いて階層的なマルチレイヤーグラフを構築します。各レイヤーは下位レイヤー全体を俯瞰する「パノラマ」および「スキップリスト」として機能し、大規模データセットにおける高速な走査を可能にします。

HNSW の動作原理：

1. HNSW は複数のレイヤー（グラフ）からなる構造を構築します。各レイヤーはその直下のレイヤーのパノラマおよびスキップリストです。

2. 最上位レイヤーのランダムな要素から開始し、HNSW は隣接ノードを特定し、距離に基づいてソートされた固定長の動的リストに追加します。

3. 隣接ノードの拡張を継続し、各追加後にリストを再ソートし、上位 k 個のみを保持します。リストが安定したら、上位要素を起点として次のレイヤーへ降下します。

4. 最下位レイヤーでの検索が完了するまでこの処理を繰り返します。

精度がある一定レベルに達すると、パラメーターの再構成によってさらに向上させることはできません。また、HNSW は近接グラフの隣接ノードを永続化するために追加のストレージを必要とします。

PASE 型構築

<?> オペレーターはベクトル間の類似度を算出します。PASE データ型は最大 3 つのパラメーターを受け入れます。

• パラメーター 1: 右側ベクトル（float4[]）

• パラメーター 2: 予約済み；0 を指定してください

• パラメーター 3: 類似度算出方式 — 0：ユークリッド距離、1：ドット積（内積）

SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[]) AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[], 0) AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[], 0, 1) AS distance;

文字列ベース構築

文字列ベース構築では、関数引数ではなくコロン（:）を用いてパラメーターを区切ります。

SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1'::pase AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1:0'::pase AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1:0:1'::pase AS distance;

'3,1,1:0:1' では、最初のセグメントがベクトル、2 番目が予約済みパラメーター（0）、3 番目が類似度算出方式（0 = ユークリッド距離、1 = ドット積）です。

正規化の要件

• ユークリッド距離: 正規化は不要です。

• ドット積またはコサイン類似度: 元のベクトルを事前に正規化してください。正規化済みベクトルでは、ドット積の値はコサイン値と等しくなります。たとえば、元のベクトルが の場合、 を満たす必要があります。

IVFFlat インデックス

CREATE INDEX ivfflat_idx ON vectors_table
USING
  pase_ivfflat(vector)
WITH
  (clustering_type = 1, distance_type = 0, dimension = 256, base64_encoded = 0, clustering_params = "10,100");

パラメーター

内部クラスタリング（clustering_type = 1）向け clustering_params

形式：clustering_sample_ratio,k

• clustering_sample_ratio：分母が 1,000 のサンプリング比率。範囲：(0, 1000]。たとえば 1 は 1/1000 のサンプリング比率を意味します。値が大きいほど精度は向上しますが、インデックス作成時間が長くなります。サンプリング対象レコード総数は 100,000 未満に保ってください。

• k：重心の数。値が大きいほど精度は向上しますが、インデックス作成時間が長くなります。推奨範囲：[100, 1000]。

HNSW インデックス

CREATE INDEX hnsw_idx ON vectors_table
USING
  pase_hnsw(vector)
WITH
  (dim = 256, base_nb_num = 16, ef_build = 40, ef_search = 200, base64_encoded = 0);

パラメーター

IVFFlat インデックスを用いたクエリ

IVFFlat インデックスのクエリには <#> オペレーターを使用します。ORDER BY 句が必須であり、インデックスが有効になるための条件です。結果は距離の昇順でソートされます。

SELECT id, vector <#> '1,1,1'::pase AS distance
FROM vectors_ivfflat
ORDER BY
  vector <#> '1,1,1:10:0'::pase
ASC LIMIT 10;

クエリ文字列 '1,1,1:10:0' はコロンで区切られた 3 つのパラメーターで構成されます。

HNSW インデックスを用いたクエリ

HNSW インデックスのクエリには <?> オペレーターを使用します。ORDER BY 句が必須であり、インデックスが有効になるための条件です。結果は距離の昇順でソートされます。

SELECT id, vector <?> '1,1,1'::pase AS distance
FROM vectors_ivfflat
ORDER BY
  vector <?> '1,1,1:100:0'::pase
ASC LIMIT 10;

クエリ文字列 '1,1,1:100:0' はコロンで区切られた 3 つのパラメーターで構成されます。

ドット積（内積）の算出

正規化済みベクトルのドット積はコサイン値と等しいため、以下の関数はドット積およびコサイン類似度の両方の検索に使用できます。HNSW インデックスを用います。

CREATE OR REPLACE FUNCTION inner_product_search(query_vector text, ef integer, k integer, table_name text) RETURNS TABLE (id integer, uid text, distance float4) AS $$
BEGIN
    RETURN QUERY EXECUTE format('
    select a.id, a.vector <?> pase(ARRAY[%s], %s, 1) AS distance from
    (SELECT id, vector FROM %s ORDER BY vector <?> pase(ARRAY[%s], %s, 0) ASC LIMIT %s) a
    ORDER BY distance DESC;', query_vector, ef,  table_name,  query_vector, ef, k);
END
$$
LANGUAGE plpgsql;

外部重心ファイルからの IVFFlat インデックス作成

これは高度な機能です。外部重心ファイルを指定されたサーバーのディレクトリにアップロードし、clustering_params で参照してください。ファイル形式は以下のとおりです。

ディメンション数|重心数|重心ベクトルデータセット

例：

3|2|1,1,1,2,2,2