PolarDB:高次元ベクトル検索 (PASE)

IVFFlat

IVFFlat は、IVFADC アルゴリズムの簡易版です。k 平均法を使用してベクターをクラスターに分割し、クエリ時には検索範囲をクエリベクターに最も近いクラスターに絞り込みます。

1. IVFFlat は k 平均法を使用してすべてのベクターをクラスタリングします。各クラスターには重心があります。

2. クエリ時、IVFFlat はクエリベクターに最も近い *n* 個の重心を見つけます。

3. IVFFlat は、それらの *n* 個のクラスター内のすべてのベクターを検索し、最も近い *k* 個を返します。

*n* 個のクラスターのみを検索することでクエリは高速化されますが、スキップされたクラスター内の類似ベクターを見逃す可能性があり、再現率が低下します。再現率を向上させるには *n* を増やしますが、その分計算量が増加します。完全な走査を避けるためにプロダクト量子化を使用する IVFADC とは異なり、IVFFlat は各クラスター内で力まかせ探索を使用して精度を維持します。

HNSW

HNSW は、NSW (Navigable Small World) アルゴリズムを使用して多層グラフを構築します。各レイヤーは、その下のレイヤーをより粗くしたビューです。

1. HNSW は、複数のレイヤーを持つ階層グラフを構築します。

2. 検索は、最上位レイヤーのランダムなエントリポイントから開始されます。

3. HNSW は、現在の要素の近傍を特定し、それらを距離でランク付けされた固定長の動的リストに追加します。次に、それらの近傍の近傍へと展開し、リストを継続的に再ソートして上位 *k* 個の候補のみを保持します。これはリストが安定するまで続き、その後、最上位の要素が次の下位レイヤーのエントリポイントになります。

4. 最下位レイヤーが最終的な最近傍を返します。

HNSW の近傍選択アプローチは、大規模なデータセットにおいてクラスタリングベースのアルゴリズムよりも優れたクエリパフォーマンスを発揮しますが、近接グラフを格納する必要があるため、追加のメモリを消費します。

距離計算メソッドの選択

ドット積またはコサインメソッドを使用する場合は、まずベクターを正規化する必要があります。ベクター の場合、 を満たす必要があります。正規化後、ドット積はコサイン値と等しくなります。

PolarDB はネイティブではユークリッド距離のみをサポートしています。ドット積を使用するには、ベクターを正規化し、「付録」のアプローチに従ってください。

インデックスの作成

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) を使用するには、インデックスを作成する前にテーブルにデータを挿入してください。

IVFFlat インデックスのパラメーター

内部クラスタリングのための `clustering_params` の設定：

• clustering_sample_ratio：分母を 1000 としたサンプリング率。有効値：(0, 1000]。例えば、1 は 1/1000 のサンプリング比率を意味します。サンプリングされるレコードの合計は 100,000 未満にしてください。

• k：重心の数。有効値：[100, 1000]。値を大きくすると再現率が向上しますが、インデックスの作成が遅くなります。

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;

クエリ文字列 'vector:probe_count:distance_type' は、コロンで区切られた 3 つのパラメーターを受け入れます。

インデックスの作成

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
);

HNSW インデックスのパラメーター

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;

クエリ文字列 'vector:ef_search:distance_type' は、コロンで区切られた 3 つのパラメーターを受け入れます。

PASE 型構造

<?> 演算子は、左側に float4[]、右側に PASE 型を取ります。

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;

PASE コンストラクターは、最大 3 つの引数 pase(vector, unused_param, distance_method) を受け入れます。2 番目の引数には特別な目的はありません。0 に設定してください。3 番目の引数は距離計算メソッドを設定します：0 はユークリッド距離、1 はドット積です。

両方のベクターは同じ次元数でなければなりません。不一致の場合はエラーが発生します。

文字列による構築

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;

文字列フォーマットは 'vector:unused_param:distance_method' で、区切り文字としてコロンを使用します。パラメーターの意味は PASE 型コンストラクターと同じです。

HNSW を使用したドット積の計算

PolarDB はネイティブでドット積距離をサポートしていないため、ベクターを正規化した後、この関数を使用してドット積で検索します。

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_type = 0 を設定します。

重心ファイルのフォーマットは次のとおりです。

次元数|重心数|重心ベクターデータセット

例：

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