Optimasi Query Embedding Skala Besar: Indexing HNSW vs IVFFlat pada pgvector

Pencarian vektor skala jutaan baris pada basis data relasional sering mengalami degradasi performa drastis akibat sequential scan (flat search). Masalah ini berakar pada kompleksitas komputasi nearest-neighbor: menghitung jarak (distance metrics seperti L2 atau Cosine) untuk vektor berdimensi tinggi menuntut throughput komputasi intensif dan akses memori acak yang masif. Menggunakan ekstensi pgvector pada PostgreSQL memungkinkan penerapan Approximate Nearest Neighbor (ANN) guna menekan latensi query dari skala detik menjadi milidetik.

Bottleneck Komputasi Nearest-Neighbor

Komputasi exact nearest-neighbor memiliki kompleksitas waktu O(N × d), di mana N adalah jumlah row dan d adalah dimensi vektor. Tanpa indeks, sistem membaca seluruh vektor dari disk ke RAM dan mengevaluasi kalkulasi float (serupa operasi kernel dot-product tanpa akselerasi SIMD/CUDA dedicated). Bottleneck utama terletak pada:

• Memory Bandwidth: Membaca jutaan array float32 membebani cache L3 dan bus RAM.
• CPU Overhead: Perhitungan jarak berulang tanpa struktur pemangkas ruang pencarian (pruning).

ANN menyelesaikan masalah ini dengan menukar sedikit tingkat akurasi (recall) demi pemangkasan ruang komputasi drastis melalui dua algoritma utama: IVFFlat dan HNSW.

Arsitektur Index: HNSW vs IVFFlat

1. IVFFlat (Inverted File Flat)

IVFFlat membagi ruang vektor menjadi beberapa partisi (clusters/Voronoi cells) menggunakan k-means clustering saat index dibangun. Saat query dijalankan, sistem hanya mencari vektor di dalam cluster yang centroid-nya paling dekat dengan query vector.

• Build Time: Cepat. Menggunakan k-means clustering sederhana.
• Memory Footprint: Rendah. Hanya menyimpan daftar pemetaan centroid dan vektor referensi asli.
• Kelemahan: Recall menurun drastis pada data dengan distribusi tidak merata; performa menurun jika data baru ditambahkan tanpa re-index (centroid menjadi usang).

2. HNSW (Hierarchical Navigable Small World)

HNSW membangun graf multi-layer dengan struktur skip-list. Layer atas memiliki edge panjang untuk melintasi graf secara cepat, sedangkan layer bawah memiliki edge rapat untuk pencarian presisi lokal.

• Latensi Query: Sangat rendah dengan recall tinggi (biasanya >95%).
• Memory Footprint: Sangat tinggi. Membutuhkan penyimpanan graf di RAM (pointer edges antar-node).
• Build Time: Signifikan lebih lambat karena harus membangun koneksi graf untuk setiap node yang masuk.

Implementasi Skema DDL dan Indexing

Berikut implementasi tabel embedding 1536 dimensi (standar OpenAI text-embedding-3-small / ada-002) pada PostgreSQL:

CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE document_embeddings (
    id BIGSERIAL PRIMARY KEY,
    document_id BIGINT NOT NULL,
    embedding vector(1536) NOT NULL
);

-- Opsi A: Index IVFFlat
-- lists = rows / 1000 untuk data < 1M; sqrt(rows) untuk data > 1M
CREATE INDEX idx_embeddings_ivfflat 
ON document_embeddings 
USING ivfflat (embedding vector_cosine_ops) 
WITH (lists = 1000);

-- Opsi B: Index HNSW
-- m = maksimum koneksi per node; ef_construction = ukuran dynamic candidate list saat build
CREATE INDEX idx_embeddings_hnsw 
ON document_embeddings 
USING hnsw (embedding vector_cosine_ops) 
WITH (m = 16, ef_construction = 64);

Tuning Parameter Query dan Runtime

Kedua algoritma menyediakan runtime knobs untuk menyeimbangkan latensi dan akurasi (recall) per session query.

Tuning IVFFlat (ivfflat.probes)

Default probes adalah 1. Meningkatkan nilai ini memaksa query memeriksa lebih banyak cluster tetangga terdekat.

-- Naikkan probes untuk meningkatkan recall dengan latensi sedikit lebih tinggi
SET ivfflat.probes = 10;

SELECT id, document_id, embedding <=> '[0.012, -0.023, ...]'::vector AS distance
FROM document_embeddings
ORDER BY distance ASC
LIMIT 5;

Tuning HNSW (hnsw.ef_search)

Default ef_search adalah 40. Parameter ini menentukan ukuran antrean prioritas kandidat selama traversal graf saat query.

-- Default ef_search = 40. Naikkan jika recall target di atas 98%
SET hnsw.ef_search = 100;

SELECT id, document_id, embedding <=> '[0.012, -0.023, ...]'::vector AS distance
FROM document_embeddings
ORDER BY distance ASC
LIMIT 5;

Analisis Query Plan dengan EXPLAIN ANALYZE

Evaluasi efisiensi index HNSW pada query pencarian kemiripan:

EXPLAIN ANALYZE
SELECT id, document_id
FROM document_embeddings
ORDER BY embedding <=> '[0.012, -0.023, ...]'::vector
LIMIT 5;

/* Output yang diharapkan:
Limit  (cost=12.45..38.12 rows=5 width=24) (actual time=1.234..1.240 rows=5 loops=1)
  ->  Index Scan using idx_embeddings_hnsw on document_embeddings  (cost=12.45..25710.00 rows=5000000 width=24) (actual time=1.232..1.237 rows=5 loops=1)
        Order By: (embedding <=> '[...]'::vector)
Planning Time: 0.125 ms
Execution Time: 1.280 ms
*/

Jika output menunjukkan Seq Scan, periksa parameter maintenance_work_mem saat pembangunan index atau pastikan enable_seqscan = off untuk memverifikasi apakah cost model PostgreSQL menganggap pembacaan sequential lebih murah akibat setting buffer cache yang tidak proporsional.

Trade-off Resource dan Matriks Keputusan

Rekomendasi Arsitektur: Gunakan HNSW jika workload membutuhkan latensi sub-10ms dan sistem memiliki kapasitas RAM yang cukup untuk memuat seluruh struktur index di shared_buffers. Gunakan IVFFlat jika constraint memori ketat, dataset sangat dinamis dengan batch training periodik, atau biaya RAM server menjadi limitasi operasional utama.