ApsaraDB RDS:PASE を使用した効率的なベクトル検索

IVFFlat

IVFFlat は IVFADC アルゴリズムの簡易版です。

1. IVFFlat は k-means を使用してベクトルをクラスターに分割します。各クラスターには重心があります。

2. クエリベクトルに最も近い n 個の重心を見つけます。

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

遠いクラスターをスキップすることでクエリは高速化されますが、再現率が低下する可能性があります。クエリに類似したベクトルが、選択されたクラスターの外に存在する可能性があるためです。n を大きくすると、計算コストは増加しますが再現率は向上します。

IVFFlat が IVFADC と異なるのは第 2 フェーズです。IVFADC はプロダクト量子化を使用して力まかせ探索をスキップするため、より高速ですが精度は低くなります。IVFFlat は選択されたクラスター内で力まかせ探索を使用するため、精度と速度のトレードオフを直接コントロールできます。

HNSW

HNSW はグラフベースの ANN アルゴリズムです。

1. HNSW はレイヤー (グラフ) の階層構造を構築します。各レイヤーは、その下のレイヤーをより粗く表現したビューです。

2. 検索は最上位レイヤーのランダムな要素から開始されます。

3. HNSW は現在の要素の近傍を見つけ、それらを距離でソートされた固定長の候補リストに追加し、近傍の展開を続けます。リストが安定すると、最上位の要素が次のレイヤーへのエントリポイントになります。

4. このプロセスは、最下層が検索されるまで繰り返されます。

HNSW は、もともと単層グラフ用に設計された Navigable Small World (NSW) アルゴリズムを使用して各レイヤーを構築し、クラスタリングベースのメソッドよりも高速な走査を可能にします。

このトピック全体を通して、機械学習と ANN 検索アルゴリズムに関する基本的な知識があることを前提としています。

ステップ 1：拡張機能の有効化

CREATE EXTENSION pase;

ステップ 2：ベクトル類似度の計算 (オプションのクイックテスト)

インデックスを作成する前に、<?> 演算子を使用して 2 つのベクトル間の類似度を計算します。

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;

文字列による構築:

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;

<?> 演算子は、左辺に float4[] を、右辺に PASE 値を取ります。両方のベクターは、同じ数のディメンションを持つ必要があります。さもないと、PASE は類似度計算エラーを返します。

PASE コンストラクター (float4[], second_param, similarity_method) では：

• 2 番目のパラメーター：予約済みです。0 に設定します。

• 類似度メソッド：0 = ユークリッド距離、1 = ドットプロダクト (内積)

ドットプロダクトまたは余弦類似度メソッドを使用する場合は、まず入力ベクターを正規化します。 正規化されたベクターは を満たします。 正規化されたベクターの場合、ドットプロダクトは余弦値と等しくなります。 ApsaraDB RDS for PostgreSQL は、ユークリッド距離メソッドを直接サポートしています。ドットプロダクトメソッドは、ベクターを正規化した後にのみ使用してください。

ステップ 3：インデックスの作成

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

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

ステップ 4：ベクトルのクエリ

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

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

ドット積またはコサイン類似度の計算

正規化されたベクトルのドット積は、そのコサイン値と等しくなります。この関数は HNSW インデックスを使用して、ドット積による上位 k 個の結果を取得します。

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 のときに clustering_params で参照します。ファイル形式は次のとおりです。

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

例：

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