ApsaraDB RDS:Gunakan PASE untuk pencarian vektor yang efisien

IVFFlat

IVFFlat adalah versi yang disederhanakan dari algoritma IVFADC.

1. IVFFlat menggunakan k-means untuk membagi vektor ke dalam kluster. Setiap kluster memiliki pusat (centroid).

2. Algoritma ini menemukan n centroid terdekat dengan vektor kueri.

3. Algoritma ini mencari semua vektor dalam n kluster tersebut dan mengembalikan k hasil terdekat.

Mengabaikan kluster yang jauh mempercepat kueri tetapi dapat mengurangi recall — vektor yang mirip dengan kueri mungkin berada di luar kluster yang dipilih. Nilai n yang lebih besar meningkatkan recall dengan biaya komputasi yang lebih tinggi.

IVFFlat berbeda dari IVFADC pada fase kedua. IVFADC menggunakan kuantisasi produk untuk menghindari traversal brute-force, yang lebih cepat tetapi kurang presisi. IVFFlat menggunakan pencarian brute-force dalam kluster yang dipilih, memberi Anda kendali langsung atas pertukaran antara presisi dan kecepatan.

HNSW

HNSW adalah algoritma ANN berbasis graf.

1. HNSW membangun struktur hierarkis berupa lapisan (graf). Setiap lapisan merupakan representasi kasar dari lapisan di bawahnya.

2. Pencarian dimulai dari elemen acak di lapisan paling atas.

3. HNSW menemukan tetangga elemen saat ini, menambahkannya ke daftar kandidat berukuran tetap yang diurutkan berdasarkan jarak, lalu terus memperluas tetangga. Ketika daftar stabil, elemen teratas menjadi titik masuk untuk lapisan berikutnya di bawahnya.

4. Proses ini diulang hingga lapisan paling bawah dicari.

HNSW menggunakan algoritma Navigable Small World (NSW) — awalnya dirancang untuk graf satu lapis — untuk membangun setiap lapisan, sehingga memungkinkan traversal lebih cepat dibanding metode berbasis pengelompokan.

Pengetahuan dasar tentang pembelajaran mesin dan algoritma pencarian ANN diasumsikan telah dimiliki pembaca dalam seluruh topik ini.

Langkah 1: Aktifkan ekstensi

CREATE EXTENSION pase;

Langkah 2: Hitung kemiripan vektor (uji coba cepat opsional)

Gunakan operator <?> untuk menghitung kemiripan antara dua vektor sebelum membuat indeks.

Konstruksi tipe 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;

Konstruksi berbasis string:

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;

Operator <?> menerima float4[] di sisi kiri dan nilai PASE di sisi kanan. Kedua vektor harus memiliki jumlah dimensi yang sama, atau PASE akan mengembalikan error perhitungan kemiripan.

Dalam konstruktor PASE (float4[], second_param, similarity_method):

• Parameter kedua: dicadangkan; atur ke 0

• Metode kemiripan: 0 = Jarak Euclidean, 1 = dot product (juga disebut inner product)

Jika menggunakan metode dot product atau cosine similarity, normalisasi vektor input terlebih dahulu. Vektor yang dinormalisasi memenuhi sehingga . Untuk vektor yang dinormalisasi, dot product sama dengan nilai cosinus. ApsaraDB RDS for PostgreSQL mendukung metode Jarak Euclidean secara langsung; gunakan metode dot product hanya setelah menormalisasi vektor.

Langkah 3: Buat indeks

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

Langkah 4: Kueri vektor

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;

Hitung dot product atau cosine similarity

Dot product dari vektor yang dinormalisasi sama dengan nilai cosinusnya. Fungsi ini menggunakan indeks HNSW untuk mengambil hasil top-k berdasarkan dot product:

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;

Gunakan file centroid eksternal untuk IVFFlat

Ini adalah opsi lanjutan. Unggah file centroid eksternal ke direktori server, lalu referensikan dalam clustering_params saat clustering_type = 0. Format file tersebut adalah:

Jumlah dimensi|Jumlah centroid|Dataset vektor centroid

Contoh:

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