KAL
Menu

Vektor plus Filter

Masalah pencarian ANN terfilter dan cara mesin khusus menyelesaikannya.

Daftar isi

Filter yang menyertai pencarian vektor sering menghasilkan jumlah hasil yang lebih sedikit daripada yang diminta. Topik ini menjelaskan penyebabnya pada pencarian ANN terfilter, mengukur efeknya dengan simulasi kecil yang benar-benar dijalankan, lalu menunjukkan cara mesin khusus seperti Qdrant dan pgvector menyelesaikannya dengan menerapkan filter di dalam traversal indeks.

Masalah pasca-filter#

Pencarian ANN menjawab satu pertanyaan sederhana, yaitu k vektor terdekat dari seluruh collection tanpa memandang atribut lain. Apabila aplikasi meminta lima dokumen berkategori panduan, cara yang paling mudah dipikirkan adalah mengambil lima terdekat terlebih dahulu, kemudian menyisakan yang memenuhi kategorinya. Pola ini disebut pasca-filter, karena filter diterapkan setelah hasil pencarian dikumpulkan.

Masalahnya muncul ketika sebagian besar kandidat terdekat tidak memenuhi syarat. Apabila dari lima kandidat terdekat hanya dua yang berkategori panduan, hasil akhirnya hanya dua dokumen padahal aplikasi meminta lima. Pencarian ANN tidak mengetahui kategori sama sekali, sehingga tidak berusaha mencari kandidat panduan yang sedikit lebih jauh. Hasil yang kurang dari k bukan error dan tidak menimbulkan pesan kesalahan apa pun.

Masalah ini memburuk seiring selektivitas filter meningkat, yaitu semakin kecil porsi data yang memenuhi syaratnya. Filter yang hanya menyisakan satu persen data hampir pasti menghasilkan sedikit atau nol hasil bila diterapkan setelah pencarian, sebab kemungkinan kelima kandidat terdekat berasal dari porsi itu sangat kecil.

Akar masalahnya ada pada struktur indeks ANN itu sendiri. Indeks HNSW dan IVF hanya menyimpan geometri vektor, yaitu tautan antartitik atau pembagian klaster, dan tidak menyimpan kategori sama sekali, sehingga traversal tidak dapat menghindari titik yang tidak memenuhi filter. Filter kategori memang dapat dijalankan cepat pada basis data relasional, tetapi menjalankannya setelah pencarian berarti menerima peringkat yang telah terpilih tanpa mengetahui syaratnya.

Simulasi pasca-filter dan filter di dalam indeks#

Simulasi berikut meniru kedua pendekatan pada dataset dua dimensi yang berisi dua kategori. Delapan titik berkategori arsip menumpuk di sekitar query, sedangkan dua belas titik berkategori panduan berada lebih jauh, dengan permintaan lima hasil yang wajib berkategori panduan.

python simulasi-filter.py 
"""Simulasi kecil: pasca-filter versus filter di dalam indeks."""
import numpy as np

rng = np.random.default_rng(37)

# Dua kelompok dokumen dua dimensi. Kelompok arsip menumpuk di sekitar
# origin, kelompok panduan tergeser ke kanan sejauh 2 satuan.
arsip = rng.standard_normal((8, 2))
panduan = rng.standard_normal((12, 2)) + [2.0, 0.0]

vektor = np.vstack([arsip, panduan])
kategori = np.array(["arsip"] * 8 + ["panduan"] * 12)
q = np.array([0.0, 0.0])
k = 5

jarak = np.linalg.norm(vektor - q, axis=1)
urutan = np.argsort(jarak)

# Pasca-filter: lima terdekat diambil lebih dahulu, filter baru diterapkan.
top_k = urutan[:k]
lolos = top_k[kategori[top_k] == "panduan"]
print(f"pasca-filter        : {lolos.size} dokumen panduan dari {k} kandidat")

# Filter di dalam indeks: hanya subhimpunan kategori panduan yang dipindai.
idx_panduan = np.flatnonzero(kategori == "panduan")
hasil = idx_panduan[np.argsort(jarak[idx_panduan])[:k]]
print(f"filter dalam indeks : {hasil.size} dokumen panduan dari {k} kandidat")
print(f"titik dipindai      : {idx_panduan.size} dari {vektor.shape[0]} titik")
text Keluaran 
pasca-filter        : 2 dokumen panduan dari 5 kandidat
filter dalam indeks : 5 dokumen panduan dari 5 kandidat
titik dipindai      : 12 dari 20 titik

Angka pada keluaran menunjukkan perbedaannya secara langsung. Pasca-filter mengambil lima titik terdekat terlebih dahulu, lalu menyisakan dua dokumen panduan, sehingga permintaan lima hasil hanya terjawab oleh dua dokumen. Pendekatan kedua menerapkan filter sebelum peringkat disusun, yaitu hanya dua belas titik panduan yang dipindai, sehingga lima hasil yang diminta seluruhnya terpenuhi. Biaya tambahannya terlihat pada baris ketiga, karena pemindaian yang seharusnya lima titik melebar menjadi dua belas titik.

Simulasi ini memindai seluruh subhimpunan yang lolos filter, yang pada data kecil masih murah. Pada jutaan titik, pemindaian penuh subhimpunan juga menjadi mahal, dan pada saat itulah peran indeks vektor serta indeks payload kembali diperlukan, kali ini dengan filter yang disertakan di dalamnya.

Cara mesin khusus menerapkan filter#

Mesin vektor menyelesaikan masalah ini dengan prinsip yang sama, yaitu filter berpindah dari tahap setelah pencarian menjadi bagian dari pencarian itu sendiri. Pada Qdrant, parameter query_filter dikirim bersama pencarian, dan kandidat yang tidak memenuhi filter dilewati di dalam traversal HNSW sehingga hasil top-k semuanya memenuhi syarat. Apabila hasil yang benar-benar akurat diperlukan, SearchParams(exact=True) memaksa pencarian eksak pada seluruh kandidat yang lolos filter sebagai jalan keluar yang pasti.

pgvector menempuh jalan serupa melalui opsi iterative_scan untuk indeks HNSW maupun IVFFlat. Ketika filter menyisakan kandidat yang terlalu sedikit, pemindaian indeks diulang dengan kumpulan kandidat yang lebih besar hingga cukup banyak baris yang lolos filter, sehingga jumlah hasil kembali terpenuhi. Mekanismenya menyerupai menaikkan parameter recall seperti ef_search atau probes secara bertahap di dalam satu pencarian. Kedua pendekatan membayar biaya yang sama, yaitu lebih banyak kandidat diproses per query sehingga latensi naik seiring selektivitas filter meningkat.

Pencarian eksak pada SearchParams(exact=True) menempati posisi khusus. Perbandingan dilakukan terhadap seluruh kandidat yang lolos filter tanpa aproksimasi, sehingga hasilnya tidak bergantung pada arah traversal graf. Biayanya paling besar, tetapi cocok untuk collection yang kecil atau kebutuhan yang menuntut jawaban pasti, misalnya pemeriksaan ulang hasil ANN.

Karena itu, jumlah hasil pencarian terfilter selalu diperlakukan sebagai data yang diukur, bukan angka yang diasumsikan selalu penuh. Parameter pencarian yang lebih longgar dan indeks payload yang tepat menjadi dua pengatur yang disesuaikan ketika hasilnya sering kurang dari yang diminta.

Pemilihan pendekatan mengikuti ukuran data dan selektivitas filternya. Filter yang menyisakan porsi besar cukup dilayani traversal biasa dengan filter di dalamnya, sedangkan filter yang sangat selektif menuntut pemindaian lebih dalam atau pencarian eksak. Kombinasi keduanya diuji dengan pengukuran recall dan latensi pada data nyata, bukan dengan intuisi.

Ringkasan#

  • Pasca-filter menerapkan filter setelah top-k dikumpulkan, sehingga hasil yang dikembalikan dapat kurang dari k tanpa pesan kesalahan apa pun.
  • Pada simulasi dua kategori, pasca-filter menyisakan 2 dari 5 hasil yang diminta, sedangkan filter di dalam pemindaian menyisakan 5 dengan memindai 12 dari 20 titik.
  • Qdrant menerapkan filter di dalam traversal HNSW melalui query_filter, sedangkan pgvector menggunakan iterative_scan untuk mengulang pemindaian hingga kandidat yang lolos filter cukup.

Referensi#