Filter Bersama Vektor

Klausa WHERE dapat digabungkan dengan pencarian vektor dalam satu pernyataan SQL, sehingga baris yang dibandingkan dapat dibatasi menurut kolom relasional sekaligus menurut kemiripan vektor. Topik ini membahas bentuk query terfilter, masalah pasca-filter yang membuat hasil kurang dari k, simulasi angka yang memperlihatkan perbedaannya, dan jawaban pgvector 0.8 melalui pemindaian iteratif.

Filter dalam satu pernyataan SQL#

Tabel vektor pada praktiknya hampir selalu menemani vektornya dengan kolom relasional, misalnya kategori arsip, status, atau tanggal pembuatan. pgvector menjalankan kedua jenis pembatasan itu dalam satu pernyataan. Contoh berikut membuat tabel dokumen, lalu mencari lima baris kategori 2 yang vektornya paling dekat dari vektor query:

-- tidak-dijalankan
CREATE TABLE dokumen (
    id          bigserial PRIMARY KEY,
    judul       text NOT NULL,
    kategori_id integer NOT NULL,
    embedding   vector(3)
);

SELECT id, judul
FROM dokumen
WHERE kategori_id = 2
ORDER BY embedding <=> '[3,1,2]'
LIMIT 5;

Satu pernyataan menggabungkan dua jenis pencarian, yaitu pembatasan baris menurut kategori dan pengurutan menurut jarak vektor. Kemampuan ini menjadi salah satu alasan utama menyimpan vektor di dalam Postgres, karena pencarian pada sistem terpisah menuntut dua permintaan dan penggabungan hasil secara manual di kode aplikasi. Pernyataan tersebut juga tetap berbentuk SQL biasa, sehingga filter yang lebih kompleks dapat disusun dengan klausa SQL yang sudah lazim digunakan.

Cara planner mengeksekusi query terfilter menentukan hasilnya, dan perbedaan pra-filter (pre-filtering) dan pasca-filter (post-filtering) berada pada urutan tahapnya. Pada pra-filter, baris disaring lebih dahulu, lalu pencarian vektor dijalankan pada baris yang lolos. Pada pasca-filter, pencarian vektor dijalankan lebih dahulu, lalu filter diterapkan pada kandidat yang dikembalikan indeks. Diagram berikut menyandingkan kedua urutan tersebut.

Kedua urutan menghasilkan jawaban yang berbeda ketika baris yang lolos filter sedikit. Kelemahan pasca-filter terletak pada ketidaktahuan indeksnya, karena indeks aproksimatif tidak mengetahui isi kolom kategori sama sekali dan strukturnya disusun menurut jarak vektor semata.

Masalah pasca-filter#

Indeks HNSW dan IVFFlat mengembalikan k baris terdekat menurut vektornya tanpa memandang filter, dan klausa WHERE baru diterapkan pada k kandidat tersebut. Apabila sedikit kandidat yang lolos, hasil yang dikembalikan kurang dari k. Pada kasus ekstrem, hasilnya kosong padahal baris yang cocok tersedia di dalam tabel, hanya saja tidak ada satu pun yang muncul di antara k kandidat terdekat. Bentuk kegagalannya sulit dideteksi karena pernyataannya tetap berhasil dieksekusi tanpa error, dan pengujian yang hanya memeriksa keberhasilan pernyataan tidak menangkap pergeseran ini.

Masalah ini tidak muncul pada pencarian eksak tanpa indeks, karena seluruh baris difilter dan dibandingkan sebelum k terbaik diambil. Harganya berupa pemindaian penuh pada setiap query, yang mahal pada data besar. Pilihan yang realistis berada di antara keduanya, yaitu meminta indeks menyerahkan kandidat lebih banyak daripada nilai k.

Simulasi pasca-filter dan pra-filter#

Skrip berikut menyimulasikan ketiga strategi pada 40 baris dua dimensi, yaitu 30 baris kategori 1 dan 10 baris kategori 2, dengan permintaan 5 baris dari kategori 2. Strategi pasca-filter mengambil 5 kandidat terdekat tanpa melihat kategori, strategi iteratif mengikuti urutan jarak hingga 5 baris lolos filter, dan pra-filter menyaring baris sebelum mencari. Angka yang dicetak adalah jumlah baris, bukan waktu.

"""Simulasi pasca-filter dan pra-filter pada pencarian vektor terfilter."""
import numpy as np

rng = np.random.default_rng(10)

# Kategori 1: 30 baris yang tersebar di sekitar area pencarian
X_a = rng.uniform(-1.4, 1.4, (30, 2))
# Kategori 2: 10 baris yang tersebar pada area yang tumpang tindih
X_b = rng.uniform(-1.4, 1.4, (10, 2))
X = np.vstack([X_a, X_b])
kategori = np.array([1] * 30 + [2] * 10)

q = np.array([0.0, 0.0])
k = 5
jarak = np.linalg.norm(X - q, axis=1)
urutan = np.argsort(jarak)

# Pasca-filter: indeks ANN menyerahkan k kandidat terdekat tanpa melihat filter,
# lalu klausa WHERE menyaring kandidat itu
kandidat = urutan[:k]
pasca = kandidat[kategori[kandidat] == 2]

# Pemindaian iteratif: kandidat diambil mengikuti urutan jarak hingga k baris
# lolos filter, sehingga lebih banyak kandidat dipindai
terpilih = []
posisi = 0
while len(terpilih) < k:
    idx = urutan[posisi]
    posisi += 1
    if kategori[idx] == 2:
        terpilih.append(idx)

# Pra-filter: baris disaring lebih dahulu, lalu pencarian dijalankan pada sisanya
mask_b = kategori == 2
pra = np.flatnonzero(mask_b)[np.argsort(jarak[mask_b])][:k]

print(f"permintaan    : {k} baris dari kategori 2")
print(f"pasca-filter  : {pasca.size} dari {k} kandidat lolos filter")
print(f"iteratif      : {posisi} kandidat dipindai, {len(terpilih)} lolos filter")
print(f"pra-filter    : {pra.size} dari {k} baris ditemukan")

permintaan    : 5 baris dari kategori 2
pasca-filter  : 2 dari 5 kandidat lolos filter
iteratif      : 13 kandidat dipindai, 5 lolos filter
pra-filter    : 5 dari 5 baris ditemukan

Pasca-filter mengembalikan 2 dari 5 baris yang diminta, tanpa peringatan apa pun. Strategi iteratif memindai 13 kandidat mengikuti urutan jarak untuk menemukan 5 baris yang lolos, dengan biaya pemindaian yang naik dibandingkan dengan 5 kandidat. Pra-filter menemukan 5 baris seketika karena pencariannya hanya berjalan pada baris kategori 2, dengan harga berupa pemindaian seluruh baris kategori tersebut. Selisih antara 2 dan 5 baris pada permintaan yang sama menunjukkan bahwa hasil pencarian terfilter tidak dapat dianggap lengkap sebelum strategi eksekusinya diketahui. Ketiga angka tersebut juga memperlihatkan hubungan antara biaya dan kelengkapan, yaitu strategi yang lebih murah menghasilkan keluaran yang kurang lengkap, sedangkan strategi yang memindai lebih banyak baris memulihkan kelengkapannya. Angka-angka ini menggambarkan perilaku ketiga strategi pada skala kecil, bukan keluaran Postgres yang sesungguhnya.

Pemindaian iteratif pada pgvector 0.8#

pgvector 0.8.0 menyediakan jawaban resmi untuk masalah pasca-filter berupa iterative scan, yaitu mode pemindaian yang mengambil lebih banyak kandidat dari indeks selama hasil yang lolos filter masih kurang dari k. Mode ini diaktifkan per sesi melalui hnsw.iterative_scan yang memiliki dua nilai:

-- tidak-dijalankan
SET hnsw.iterative_scan = strict_order;

SELECT id, judul
FROM dokumen
WHERE kategori_id = 2
ORDER BY embedding <=> '[3,1,2]'
LIMIT 5;

Nilai strict_order menjaga hasil tetap terurut persis menurut jarak yang dipindai, sedangkan nilai relaxed_order memindai dengan lebih murah tetapi urutan hasilnya dapat sedikit melenceng. Keduanya menukar kecepatan dengan keakuratan, sehingga pengukuran latensi tetap diperlukan setelah mode ini diaktifkan. Parameter sesi berlaku pada koneksi yang menjalankannya, dan bentuk SET LOCAL di dalam transaksi juga sah, sehingga koneksi yang dipinjam singkat dari pool tetap dapat mengatur mode ini per transaksi.

Alternatif yang lebih sederhana tersedia ketika pemindaian iteratif belum diaktifkan. Menaikkan hnsw.ef_search dari nilai defaultnya 40 membuat indeks HNSW mempertimbangkan kandidat lebih banyak pada setiap query, dan menaikkan ivfflat.probes dari nilai defaultnya 1 membuat IVFFlat menyapu klaster lebih banyak, sehingga peluang kandidat lolos filter naik pada keduanya. Untuk filter yang nilainya tetap dan himpunan barisnya kecil, indeks parsial Postgres juga menyelesaikan masalah dengan jalan berbeda, yaitu indeks yang hanya memuat baris yang lolos kriteria WHERE saat dibangun.

Kesalahan umum#

• Menganggap LIMIT k menjamin k baris pada query terfilter membuat aplikasi menampilkan hasil yang tidak lengkap. Perilaku pasca-filter default mengembalikan jumlah yang bergantung pada data, bukan k. Perbaikannya, aktifkan pemindaian iteratif, perbesar ef_search atau probes, lalu periksa jumlah hasilnya di kode aplikasi.
• Mengaktifkan hnsw.iterative_scan pada satu koneksi lalu mengharapkan pengaturannya berlaku di koneksi lain menimbulkan kekeliruan yang tidak terlihat, karena parameter sesi hanya berlaku pada koneksi yang menjalankannya. Perbaikannya, jalankan SET pada koneksi yang berumur panjang, atau gunakan SET LOCAL di dalam transaksi yang menjalankan query.
• Mengaktifkan pemindaian iteratif tanpa mengukur ulang latensi membuat anggaran waktu per query meleset, karena mode ini memindai lebih banyak kandidat. Perbaikannya, ukur latensi sebelum dan sesudah pada data yang menyerupai produksi, lalu pilih strict_order atau relaxed_order sesuai kebutuhan urutan hasilnya.
• Mencampur kedua nilai pemindaian iteratif tanpa mempertimbangkan kebutuhan aplikasi membuat urutan hasil tidak menentu. Antarmuka yang menampilkan urutan jarak membutuhkan strict_order, sedangkan kasus yang hanya membutuhkan himpunan hasil dapat menggunakan relaxed_order yang lebih murah. Perbaikannya, tetapkan satu nilai yang sesuai kebutuhan peringkat aplikasi dan catat pilihannya.

Ringkasan#

• Klausa WHERE dan pencarian vektor digabung dalam satu pernyataan SQL, sehingga filter relasional dan peringkat kemiripan dijawab bersama.
• Pasca-filter default membuat query terfilter mengembalikan kurang dari k baris, karena filter diterapkan setelah indeks ANN menyerahkan k kandidatnya.
• pgvector 0.8.0 menyediakan pemindaian iteratif melalui hnsw.iterative_scan = strict_order atau relaxed_order, dengan kompromi antara kecepatan dan keakuratan.
• Alternatifnya berupa menaikkan hnsw.ef_search atau ivfflat.probes, pencarian eksak pada data kecil, dan indeks parsial untuk filter yang tetap.

Referensi#

• pgvector — GitHub — Bagian filtering dan iterative index scans pada dokumentasi resmi yang menjadi dasar pembahasan query terfilter.
• Dokumentasi PostgreSQL — PostgreSQL — Rujukan pernyataan SET, SET LOCAL, dan indeks parsial (partial index).