Vector Database: HNSW, IVF, dan Trade-off Akurasi–Kecepatan

Sesi: 10:00 Technical Exploration · Level: Advanced · Tanggal: 17 Okt 2026

Tujuan Belajar

Setelah sesi ini kamu bisa: menjelaskan kenapa exact k-NN tidak dipakai di produksi, cara kerja HNSW dan IVF secara struktural, memilih parameter (M, efSearch, efConstruction, lists, probes) berdasarkan angka recall/latency nyata, dan tahu mode kegagalan yang bikin vector search jebol setelah masuk produksi.

Kenapa ANN dan Bukan Exact k-NN

Exact k-NN = hitung jarak query ke semua N vektor. Kompleksitas O(N·d).

Angka nyata: 1 juta vektor 1536-dim (embedding text-embedding-3-large). Sequential scan di pgvector pada ~58k baris saja ≈ 650 ms per query [[1]]. Naikkan ke 10 juta baris → praktis tak terpakai. Ini yang disebut curse of dimensionality: begitu dimensi > ~20, struktur partitioning pohon tradisional (kd-tree, R-tree) kehilangan pruning power karena hampir semua titik jadi "jauh" satu sama lain.

Solusinya ANN (Approximate Nearest Neighbor): tukar sedikit recall untuk lompatan kecepatan. Yang diukur: - Recall@k = fraksi tetangga ground-truth yang benar-benar dikembalikan. Target umum 95–99%. - QPS / latency p50–p99. - Memory index (sering jadi pembatas biaya, bukan CPU).

Arsitektur & Alur Teknis

1. HNSW — Hierarchical Navigable Small World

Paper asal: Malkov & Yashunin, arXiv:1603.09320 [[2]].

Ide: graf small-world berlapis. Lapisan atas jarang (long-range hop), lapisan bawah padat (fine-grained). Query masuk dari puncak, greedily turun.

Layer 2 (sparse):   A ──────────────── F
                    │                 │
Layer 1 (medium):   A ── C ── D ─────── F
                    │    │    │        │
Layer 0 (dense,     A ─ B ─ C ─ D ─ E ─ F ─ G ─ H
ALL vectors)         │   │   │   │   │   │   │   │
                    ... (setiap titik punya ≤ M tetangga)

SEARCH:
  entry_point = root Layer 2
  for layer in [top .. 0]:
      greedy_walk: ambil tetangga terdekat, pindah sampai lokal minimum
      (Layer 0: pakai candidate queue ukuran efSearch, kandidat baru
       masuk hanya jika jaraknya < kandidat terjauh di queue)

INSERT:
  p = random level (distribusi eksponensial, mL = 1/ln(M))
  cari entry point turun dari atas → dapat kandidat tetangga
  pilih ≤ M tetangga terdekat (efConstruction untuk seleksi kandidat)
  buat edge dua arah; kalau tetangga sudah punya M edge → pruning heuristik

Parameter kunci [[2]][[3]]: - M — max edge per node. Kontrol memori + recall. Satu-satunya parameter yang nambah memori index. efConstruction dan efSearch tidak mengubah ukuran index (terverifikasi di Pinecone, SIFT1M: M=2 → ~0.5 GB, M=512 → ~5 GB) [[2]]. - efConstruction — lebar kandidat saat build. Lebih tinggi = index lebih baik, build lebih lama. - efSearch / hnsw.ef_search — lebar kandidat saat query. Ini yang kamu tuning di produksi (runtime, per-query, tidak perlu rebuild).

Default wajar: M=16, ef_construction=200. OpenSearch menyediakan portofolio konfigurasi hasil transfer-learning lintas 15 dataset, dievaluasi berurutan sampai recall cukup [[3]]:

{'M': 16,  'efConstruction': 128, 'efSearch': 32}
{'M': 32,  'efConstruction': 128, 'efSearch': 32}
{'M': 16,  'efConstruction': 128, 'efSearch': 128}
{'M': 64,  'efConstruction': 128, 'efSearch': 128}
{'M': 128, 'efConstruction': 256, 'efSearch': 256}

2. IVF — Inverted File (k-means clustering)

• Build: jalankan k-means pada sampel vektor → lists centroid. Assign tiap vektor ke centroid terdekat.
• Query: hitung jarak ke semua centroid → pilih probes list terdekat → scan hanya list itu.
• Kecepatan build jauh lebih tinggi, cocok sebagai coarse quantizer untuk dataset raksasa (>1G vektor, lihat FAISS). Trade-off: kalau centroid tidak ideal, recall bisa jatuh drastis pada probes rendah.

3. Perbandingan Head-to-Head

Data dari pgvector, 58.634 baris [[1]]:

Trade-off & Pendekatan Alternatif

Catatan penting: untuk dataset kecil (< ~10k vektor), sequential scan bisa lebih cepat dari index — planner sering benar memilihnya. pgvector 0.8.0 justru memperbaiki estimasi cost agar planner bisa memilih B-tree dan mendapat recall 100% tanpa ANN [[4]].

Quantization — cara memangkas memori: scalar (FP32→INT8), binary (1 bit/dimensi), product quantization, dan di Qdrant 1.18 ada TurboQuant (~8x kompresi, klaim recall tidak turun) [[5]]. Teknik umum: search di representasi terkuantisasi dulu, lalu rerank kandidat teratas dengan vektor asli.

Use Case Produksi

pgvector 0.8.0 (rilis 30 Okt 2024, sekarang 0.8.7 per Okt 2026) [[4]][[6]] memperkenalkan iterative index scans — ini fitur produksi paling penting untuk RAG berfilter:

-- masalah lama: filter WHERE dijalankan SETELAH ANN scan → "overfiltering"
-- bisa kembali 0 hasil walau data ada
SET hnsw.iterative_scan = relaxed_order;  -- atau strict_order / off
SET hnsw.max_scan_tuples = 20000;
SELECT * FROM items
WHERE category = 'dress'
ORDER BY embedding <=> '[0.1,0.2,...]'
LIMIT 10;

AWS melaporkan hingga 100x peningkatan result completeness untuk query sangat selektif dengan iterative scan di 0.8.0 (dibanding 0.7.4) [[7]].

Pilihan sistem (2026) [[5]][[8]]: - pgvector — sudah pakai Postgres, <50–100M vektor, butuh transaksi ACID + JOIN. Yang paling sedikit moving parts. - Qdrant (Rust) — filtering champion, ACORN menyatukan filter ke traversal HNSW; 1 GB gratis selamanya; degradasi >50M vektor. - Milvus — ratusan juta ke miliar vektor; DiskANN di NVMe; kompleksitas operasional tinggi. - Weaviate — hybrid search (vector + BM25) native, built-in vectorizer, GraphRAG; boros resource >100M vektor.

Kasus nyata: Open WebUI pindah dari Qdrant ke pgvector karena arsitektur "collection-per-file" tidak terkelola di ~1.400 file [[9]].

Failure Mode Umum

1. Overfiltering (pre-0.8.0) — filter metadata dijalankan setelah ANN scan. Solusi: iterative scan (hnsw.iterative_scan). Ini #1 penyebab query RAG "tiba-tiba kosong".
2. Memori membengkak — M naik → index naik linear. 1M vektor 1536-dim FP32 = ~6 GB data mentah; HNSW menambah 2–5x. Lupa hitung ini = OOM saat build.
3. Build index memakan RAM berlebih — maintenance_work_mem terlalu kecil membuat build spill ke disk (81 s → 30 s hanya dengan menaikkannya ke 5 GB) [[1]].
4. Recall regresi diam-diam — ganti embedding model tapi index lama masih dipakai → vektor dimensi beda / distribusi beda → recall hancur tanpa error.
5. Delete/update churn — pgvector HNSW mendukung update & delete, tapi tumpukan dead tuple + fragmentasi graf menurunkan recall seiring waktu. Butuh REINDEX periodik.
6. ef_search terlalu rendah ditekan untuk mengejar latency → jawaban LLM mulai halusinasi karena konteks yang di-retrieve salah.
7. Filter tinggi-selektif di IVF — probes rendah + filter ketat → hasil < k. Sama seperti overfiltering.
8. Hot key / single_node — semua query masuk satu partisi; sharding tidak menyelamatkan.

Latihan Praktis Kecil

Ukur kurva recall–latency sendiri, jangan percaya default:

# butuh: pip install pgvector psycopg numpy
# asumsi tabel items(embedding vector(1536)) + ground truth dari exact scan
import numpy as np, psycopg

def recall_at_k(cur, q, k=10, ef=None):
    if ef: cur.execute(f"SET hnsw.ef_search = {ef}")
    cur.execute("""
        SELECT id FROM items ORDER BY embedding <=> %s LIMIT %s
    """, (q, k))
    got = {r[0] for r in cur.fetchall()}
    cur.execute("SET enable_indexscan = off")      # paksa exact
    cur.execute("SELECT id FROM items ORDER BY embedding <=> %s LIMIT %s", (q, k))
    truth = {r[0] for r in cur.fetchall()}
    cur.execute("SET enable_indexscan = on")
    return len(got & truth) / k

# sapu ef_search: 10, 32, 64, 128, 256 → plot recall vs p50 latency
# pilih ef_search terkecil yang mencapai recall target (mis. 0.95)

Poin: ef_search bisa diubah per query tanpa rebuild index — server workload bisa pakai nilai beda dari batch job.

Poin Kunci

• Exact k-NN = O(N·d), tak skalabel. ANN tukar ≤5% recall untuk 100–400x speedup.
• HNSW: graf berlapis, recall default 95%+, M satu-satunya yang nambah memori (2–5x). ef_search = tuas runtime utama.
• IVF: k-means, build cepat, murah memori, recall sangat sensitif ke lists/probes.
• pgvector 0.8.0+ iterative scan memperingan masalah overfiltering hingga 100x result completeness.
• Pilihan engine mengikuti skala + kebutuhan filter, bukan benchmark mentah. <50M dan sudah pakai Postgres → pgvector biasanya menang karena nol moving parts.
• Quantization (scalar/binary/product/TurboQuant) adalah kunci biaya memori, tapi wajib rerank dengan vektor asli.

DIKETAHUI (terverifikasi dari sumber): angka latency pgvector (1.5 ms HNSW / 2.4 ms IVFFlat / 650 ms seq scan), build 81→30 s, rilis pgvector 0.8.0 = 30 Okt 2024 & 0.8.7 = 1 Okt 2026, sifat memori HNSW vs M. | DIINFERENSI: peta "kapan pilih engine mana" dari artikel perbandingan 2026 — bergantung pada workload, bukan angka mutlak. | BELUM PASTI: klaim Qdrant TurboQuant "8x kompresi tanpa penalti recall" berasal dari satu blog vendor, belum ada benchmark independen.

Eksplorasi Lanjut

• Baca paper asli HNSW: arXiv:1603.09320 — fokus ke bagian probabilistic level assignment & heuristic neighbor selection.
• Pelajari ACORN (filtered HNSW di Qdrant) — kenapa filter inline mengalahkan post-filter.
• Uji DiskANN/Vamana untuk skenario vektor >RAM.
• Coba binary quantization + rerank dan ukur trade-off memori/recall di dataset kecil Anda.
• Topik sesi berikut: pgvectorscale (StreamingDiskANN) — bagaimana Postgres mendekati Pinecone di 50M+ vektor.

Sumber

[1] AWS Database Blog. "Optimize generative AI applications with pgvector indexing" — aws.amazon.com · [2] Pinecone. "Hierarchical Navigable Small Worlds (HNSW)" — pinecone.io · [3] Shen, Mazanec, Kolchina (OpenSearch), 10 Apr 2025. "A practical guide to selecting HNSW hyperparameters" — opensearch.org · [4] PostgreSQL News, 11 Nov 2024. "pgvector 0.8.0 Released!" — postgresql.org · [5] Elest.io, Jun 2026. "Qdrant vs Weaviate vs Milvus" — blog.elest.io · [6] pgvector GitHub, tag v0.8.7 (1 Okt 2026) — github.com/pgvector · [7] AWS. "Supercharging vector search ... pgvector 0.8.0 on Aurora" — aws.amazon.com · [8] Firecrawl. "Best Vector Databases in 2026" — firecrawl.dev · [9] Wasowski, J. "I Benchmarked 6 Vector Databases for RAG" — medium.com