Deduplikasi kode non-exact menggunakan representasi embedding sering menghadapi kendala performa saat dataset mencapai jutaan baris fungsi atau potongan kode. Algoritma exact matching seperti hashing SHA-256 gagal mendeteksi kode yang memiliki perubahan nama variabel atau pemformatan ulang sintaksis. Pendekatan semantik berbasis vector embeddings menyelesaikan masalah akurasi tersebut, namun query cosine distance (<=>) pada PostgreSQL tanpa konfigurasi terarah dapat memicu full sequential scan yang menghabiskan CPU dan memori I/O.

Artikel ini membahas arsitektur deduplikasi kode skala besar menggunakan ekstensi pgvector di PostgreSQL. Fokus utama mencakup pemilihan dan penyetelan indeks Hierarchical Navigable Small World (HNSW), pemanfaatan metadata code-filtering, partisi tabel, serta penulisan query batch similarity yang efisien.

Akar Masalah Bottleneck Similaritas Cosine

Pencarian exact nearest neighbor (k-NN) menghitung jarak cosine terhadap setiap vektor dalam tabel. Pada vektor 768 dimensi (umum pada model code embedding seperti CodeBERT atau StarCoder) dengan 5 juta baris, satu kalkulasi memerlukan iterasi miliaran operasi floating point. Tanpa indeks perkiraan (ANN / Approximate Nearest Neighbor), latensi query meningkat secara linear seiring pertumbuhan dataset.

Dua kendala teknis mendasar pada deduplikasi kode:

  • High Dimensionality Overhead: Kalkulasi cosine distance membutuhkan transfer buffer data besar dari storage ke RAM jika indeks atau tabel melampaui alokasi shared_buffers.
  • Overfiltering Trap: Melakukan filter relational biasa (misal: WHERE language = 'python') bersamaan dengan pencarian vektor tanpa perancangan indeks yang tepat sering menyebabkan PostgreSQL mengabaikan indeks vektor atau mengalami iterasi post-filter yang lambat.

Strategi Indexing Vector: HNSW vs IVFFlat

Ekstensi pgvector mendukung dua tipe indeks ANN: IVFFlat (Inverted File Flat) dan HNSW (Hierarchical Navigable Small World). Untuk deteksi duplikasi kode skala repositori, HNSW adalah pilihan yang lebih unggul.

  • IVFFlat: Mengelompokkan vektor ke dalam list centroid. Membutuhkan waktu pembuatan indeks lebih cepat dan konsumsi RAM lebih rendah. Namun, IVFFlat memerlukan rebuild berkala saat data baru dimasukkan agar cluster tidak bias, serta memiliki recall yang rendah pada volume data jutaan baris jika parameter probes disetel terlalu kecil.
  • HNSW: Membangun graf bertingkat (multi-layer graph). HNSW memberikan recall tinggi, latensi query sangat rendah, dan performa stabil meskipun data terus bertambah secara dinamis tanpa perlu rebuild ulang dari nol. Kelemahannya adalah waktu indexing yang lebih lama dan kebutuhan memori lebih besar.

Konfigurasi pembuatan indeks HNSW untuk cosine distance (vector_cosine_ops):

CREATE EXTENSION IF NOT EXISTS vector;

-- Meningkatkan maintenance_work_mem agar proses pembuatan graf berjalan di RAM
SET maintenance_work_mem = '4GB';

CREATE INDEX idx_code_embeddings_hnsw ON code_snippets 
USING hnsw (embedding vector_cosine_ops) 
WITH (m = 16, ef_construction = 128);

Dua parameter utama HNSW:

  • m: Jumlah koneksi dua arah maksimal per node dalam graf. Nilai 16 memadai untuk representasi embeddings kode. Menaikkan nilai ke 32 atau 64 sedikit meningkatkan recall tetapi melipatgandakan ukuran indeks di RAM.
  • ef_construction: Batas eksplorasi kandidat saat membangun graf. Nilai 128 memberikan rasio optimal antara akurasi graf dan waktu build.

Pra-Filtering Metadata dan Partisi Relasional

Dua potongan kode hampir mustahil merupakan duplikat fungsional murni jika ditulis dalam bahasa pemrograman berbeda, atau memiliki perbedaan panjang token yang ekstrem (misalnya fungsi 5 baris vs class 200 baris). Membatasi pencarian graf hanya pada subset yang relevan menghemat beban komputasi vektor.

Daripada menggabungkan filter langsung ke dalam query HNSW tunggal yang besar, terapkan deklaratif partitioning berdasarkan bahasa pemrograman:

CREATE TABLE code_snippets (
    id BIGSERIAL,
    repo_id INT NOT NULL,
    file_path TEXT NOT NULL,
    language VARCHAR(32) NOT NULL,
    token_length INT NOT NULL,
    content_hash CHAR(64) NOT NULL,
    embedding vector(768) NOT NULL,
    PRIMARY KEY (id, language)
) PARTITION BY LIST (language);

-- Buat partisi per bahasa utama
CREATE TABLE code_snippets_python PARTITION OF code_snippets FOR VALUES IN ('python');
CREATE TABLE code_snippets_typescript PARTITION OF code_snippets FOR VALUES IN ('typescript');
CREATE TABLE code_snippets_go PARTITION OF code_snippets FOR VALUES IN ('go');

-- Buat indeks HNSW pada masing-masing partisi secara spesifik
CREATE INDEX idx_python_hnsw ON code_snippets_python USING hnsw (embedding vector_cosine_ops);
CREATE INDEX idx_typescript_hnsw ON code_snippets_typescript USING hnsw (embedding vector_cosine_ops);
CREATE INDEX idx_go_hnsw ON code_snippets_go USING hnsw (embedding vector_cosine_ops);

Partisi tabel memastikan ukuran graf HNSW per partisi tetap muat di dalam RAM, mengisolasi memory working set, dan memungkinkan parallel execution plan saat query dijalankan terhadap partisi spesifik.

Query Batch Deduplication Teroptimasi

Untuk mendeteksi duplikat pada fungsi-fungsi baru terhadap database repositori utama, hindari mengeksekusi query N+1 per fungsi secara berulang. Gunakan batch query via LATERAL JOIN dengan filter toleransi panjang token (misal: selisih panjang token tidak lebih dari 20%):

SET hnsw.ef_search = 40;

WITH new_incoming_batch AS (
    SELECT id, language, token_length, embedding 
    FROM incoming_code_buffer
    WHERE processed_at IS NULL
    LIMIT 100
)
SELECT 
    b.id AS input_snippet_id,
    matches.id AS duplicate_snippet_id,
    matches.file_path,
    matches.cosine_distance
FROM new_incoming_batch b
CROSS JOIN LATERAL (
    SELECT 
        c.id,
        c.file_path,
        (c.embedding <=> b.embedding) AS cosine_distance
    FROM code_snippets c
    WHERE c.language = b.language
      AND c.token_length BETWEEN (b.token_length * 0.8)::INT AND (b.token_length * 1.2)::INT
      AND (c.embedding <=> b.embedding) < 0.15 -- Threshold cosine distance (85% kemiripan)
    ORDER BY c.embedding <=> b.embedding
    LIMIT 1
) matches;

Catatan penting pada parameter query:

  • hnsw.ef_search: Menentukan ukuran dynamic candidate list saat query dieksekusi. Nilai default adalah 40. Nilai lebih tinggi meningkatkan recall tetapi menambah runtime kueri.
  • Threshold 0.15: Cosine distance bernilai 0 identik, dan nilai mendekati 0 menunjukkan kemiripan tinggi. Nilai batas ini perlu disesuaikan dengan distribusi normal model embedding yang digunakan.

Verifikasi Index Usage via EXPLAIN ANALYZE

Pastikan planner PostgreSQL menggunakan indeks vektor dengan memeriksa eksekusi query:

EXPLAIN ANALYZE
SELECT id, (embedding <=> '[0.012, -0.043, ...]'::vector) AS dist
FROM code_snippets_python
ORDER BY embedding <=> '[0.012, -0.043, ...]'::vector
LIMIT 5;

Perhatikan bagian output:

  • Jika output memuat Index Scan using idx_python_hnsw, indeks berfungsi dengan benar.
  • Jika terlihat Seq Scan, periksa kembali apakah nilai enable_seqscan aktif, pastikan dimension vector cocok, atau pastikan data pada tabel partisi cukup signifikan agar planner menganggap indeks lebih murah dibanding full table scan.