ParadeDB Balik Benchmark TIN: Fieldnorm, MAXSCORE, dan Dense-Term Elision

Dua minggu setelah PlanetScale memperkenalkan TIN, ekstensi full-text search untuk PostgreSQL, ParadeDB menjawab dengan satu kalimat yang jarang muncul di post benchmark: bahwa angka pesaing itu benar, dan bahwa mereka perlu waktu dua minggu untuk menutupinya. Klaim peluncuran TIN menyatakan minimal delapan kali lebih cepat dibanding ParadeDB 0.25 di seluruh benchmark PlanetScale. Dua minggu kemudian, pada dataset StackExchange yang sama dengan harness dan tipe mesin yang sama, ParadeDB melaporkan 81,9 QPS sementara TIN 33 QPS untuk pencarian Top K dengan ranking BM25 exact.

Yang membuat post ini layak dibaca bukan angka akhirnya, melainkan isi diagnosa. ParadeDB tidak menutup jarak itu dengan mengganti desain dokumen identifier seperti yang diklaim PlanetScale, tapi dengan beberapa optimization pass dan perubahan konfigurasi. Detail dari pass-pass itu adalah materi yang biasanya hilang di balik slide performa.

Konteks: Postings List dan Dua Cara Menamai Dokumen

Jantung dari indeks teks adalah postings list, yaitu daftar identifier dokumen per term. Kalau indeks punya dokumen satu sampai sepuluh dan kata database muncul di dokumen dua dan empat, postings list untuk database hanyalah [2, 4]. Struktur sederhana ini yang memungkinkan pencarian melompat langsung ke kandidat, alih-alih memindai seluruh baris.

Masalahnya, istilah dokumen tidak punya satu definisi universal di pertemuan dua dunia. Tantivy, pustaka pencarian yang jadi mesin ParadeDB, memakai DocId berupa u32 berurutan yang internal dan ditetapkan hanya berdasarkan urutan masuk. PostgreSQL mengidentifikasi baris dengan ctid, sebuah tuple yang menunjuk lokasi fisik di penyimpanan berbasis blok, misalnya pasangan 190 dan 17 yang berarti baris itu kini berada di slot 17 pada blok 190.

Karena ParadeDB adalah indeks PostgreSQL yang ditenagai Tantivy, harus ada peta antara DocId dan ctid. Inti post PlanetScale adalah bahwa memakai ctid langsung sebagai identifier dokumen menghapus kebutuhan peta itu dan memungkinkan operasi bitmap serta pengecekan visibilitas yang lebih efisien. PlanetScale attribution ke perbedaan arsitektur tersebut.

Dugaan yang Salah, dan Pengukuran yang Membenarkannya

ParadeDB awalnya skeptis pada penjelasan itu untuk query BM25 Top K. Alasan mereka teknis: ParadeDB menunda lookup ctid sampai Top K dokumen terakhir terkumpul, sehingga query ambil sepuluh hanya melakukan sepuluh lookup. Bukan nol, tapi kecil di profil, dan tidak menjelaskan jurang satu orde besaran.

Mereka mulai dari query sederhana: sepuluh dokumen paling relevan yang memuat satu term, diurutkan dengan skor BM25, memakai dataset Hacker News berisi 28,7 juta dokumen agar iterasi lokal cepat.

EXPLAIN (ANALYZE, BUFFERS) SELECT id, title, by FROM hn_items WHERE title === 'database' ORDER BY pdb.score(id) DESC LIMIT 10;

Hasilnya langsung menunjuk sesuatu yang tidak terduga. Saat dibedah, distribusinya begini: fieldnorms menyumbang 1.513 akses halaman, sekitar 83 persen, sementara semua sisanya, postings dan metadata, hanya 311 akses atau 17 persen.

Optimasi 1: Fieldnorm dan Harga dari Akses Acak

Fieldnorms menyimpan panjang field dari sebuah dokumen, dipakai BM25 untuk menormalkan skor. Ukurannya sangat kecil, satu byte per dokumen yang sudah dikuantisasi menjadi fieldnorm id. Karena itu kontradiksinya terasa aneh: bagaimana sesuatu sekecil ini bisa menghasilkan sebagian besar pembacaan halaman?

Jawabannya adalah lokalisasi, bukan ukuran. Tantivy menyimpan fieldnorms terpisah dari postings, sebagai array yang diindeks oleh DocId. Membaca postings satu term bersifat sekuensial, tapi mengambil fieldnorm yang cocok bisa melompat ke mana-mana di array itu. Pada penyimpanan memory-mapped yang biasa dipakai Tantivy, pola seperti ini umumnya aman karena halaman yang sama dipakai ulang sering. Di di atas block storage PostgreSQL, lompatan itu berarti satu halaman dibaca per akses.

Perbaikannya sederhana secara konsep: menyimpan array fieldnorm di samping setiap postings list, dalam urutan yang sama dengan nilai DocId pada postings itu. Setelah ini, pembacaan fieldnorm berjalan sekuensial bersama postings. Dampaknya mereka tulis terang-terangan: akses fieldnorm turun dari 1.500 halaman menjadi hanya 30.

Trade-off-nya adalah storage, karena fieldnorm sebuah dokumen kini berulang untuk setiap term berbeda yang dikandungnya. ParadeDB mencatat bahwa ini tidak selalu berarti perkalian ruang yang naïve, tapi tetap merupakan pertukaran yang harus disadari: ruang ditukar dengan lokalisasi baca.

Optimasi 2: Memilih Algoritma Pruning Blockmax yang Tepat

Perbaikan fieldnorm sangat membantu query dengan sedikit term, tapi disjunction dengan banyak term masih mengecewakan. Contoh yang mereka pakai adalah query yang mencari dokumen berisi salah satu dari sepuluh term sekaligus.

EXPLAIN (ANALYZE, BUFFERS) SELECT id, title, by FROM hn_items WHERE text ||| 'rust arc clone memory safety borrow checker ownership lifetime rules' ORDER BY pdb.score(id) DESC LIMIT 10;

Setelah optimasi pertama, buffer read turun sekitar 80 persen, tapi waktu query tidak ikut turun. Profil menunjukkan mayoritas waktu habis di loop Blockmax WAND.

Blockmax adalah algoritma standar yang dipakai mesin pencari untuk melewati blok postings ketika menjalankan query disjunction. Idanya: postings dipecah menjadi blok, dan tiap blok menyimpan skor maksimum yang mungkin disumbang term dari blok itu. Blok bisa dilewati kalau skor maksimumnya tidak mungkin melewati ambang Top K saat ini. Ada dua keluarga, WAND dan MAXSCORE, dan bedanya adalah cara melewati.

Trade-off antara keduanya adalah jumlah kerja yang dikeluarkan untuk memutuskan apa yang dilewati. WAND melewati lebih banyak, tapi membakar lebih banyak siklus CPU untuk memutuskannya. MAXSCORE melewati lebih sedikit, dengan overhead lebih kecil. Ketika query mengandung banyak term, overhead WAND tumbuh dan bisa melampaui pekerjaan yang berhasil ia lewati.

Tantivy memakai WAND. Lucene juga memakai WAND sampai tahun 2023, ketika mereka memperkenalkan MAXSCORE untuk query tertentu, dan hari ini Lucene memilih dinamis di antara keduanya tergantung bentuk query. ParadeDB menambahkan jalur MAXSCORE dengan heuristik sederhana: pakai MAXSCORE untuk disjunction dengan minimal tiga term dan postings yang cukup padat, pakai WAND untuk sisanya. Pada query sepuluh term di atas, p50 turun sekitar enam kali dan p95 sekitar delapan kali.

Konfigurasi Benchmark: Tempat Angka Saling Menipu

Bagian paling jujur dari post ini adalah pengakuan bahwa benchmark PlanetScale disusun secara fair, dengan dua anomali yang tidak sengaja menguntungkan TIN. Yang pertama adalah oversight sintaksis: kueri benchmark memakai query string parser ParadeDB melalui operator @@@ tanpa nama field. Padahal di StackExchange dataset, kolom id dan body sama-sama terindeks, sehingga ParadeDB mencari di dua kolom sementara TIN hanya satu. ParadeDB memindahkan semua kueri ke operator native mereka, yaitu ||| untuk disjunction, &&& untuk conjunction, dan ### untuk phrase.

Anomali kedua lebih konseptual dan namanya dense-term elision, sebuah shortcut pemeringkatan untuk term umum yang diaktifkan TIN secara default. Term seperti the dan is punya postings list sangat besar dan mahal dibaca, sementara bobot BM25 untuk term itu rendah sampai hampir tidak menggeser ranking akhir. Kebanyakan mesin mencari ini dengan stopword dictionary, dan kedua engine mendukungnya, tapi elision memotong di waktu query.

Biayanya adalah kebenaran hasil. Dengan elision aktif, TIN tidak menghitung BM25 sejati dan urutan hasil bisa berbeda. Saat benchmark StackExchange dibedah, mereka menemukan bahwa sebagian kueri justru terdiri dari kata-kata umum itu, karena kueri dibuat dengan mengambil rentang kata berurutan dari korpus, menghasilkan pertanyaan seperti is it, to a, dan is to. Dengan dense_ratio 0.1, yang berarti elision aktif, hasilnya:

Gaya kueri TIN dengan elision aktif	Masuk minimal satu hasil di luar Top 10 sejati
Conjunction	39,9 persen
Disjunction	88,2 persen
Phrase	13,8 persen
Seluruh kueri	47,8 persen

Lebih tajam lagi, 6,4 persen kueri menghasilkan Top 10 yang tidak satu pun masuk ke Top 10 sejati. ParadeDB menambahkan nuansa yang penting: berbeda dari BM25 exact tidak otomatis berarti lebih buruk, karena term yang di-elide memang berbobot rendah dan menilai relevansi butuh judgment manusia yang tidak ada di benchmark ini. Tapi kalau workload-nya didefinisikan sebagai BM25 Top K, maka dengan elision aktif kedua engine tidak menghitung hal yang sama.

Karena itu perbandingan utama mereka memakai BM25 exact untuk dua engine, dengan TIN disetel dense_ratio=2 yang mematikan elision. Saat elision diizinkan, gambarnya berubah: ParadeDB 81,9 QPS naik ke 161,9 QPS dengan stopwords aktif, sementara TIN bergerak dari 35,5 QPS ke 114,4 QPS dengan dense_ratio 0.1. Empat angka itu berada di satu dataset campuran berisi 150 juta dokumen dengan delapan klien konkuren dan durasi lima menit.

Apakah Ada Identifier Dokumen yang Lebih Superior

ParadeDB melihat ctid versus u32 DocId sebagai trade-off, bukan pemenang. Argumen mereka: tidak ada yang mengompresi lebih baik dari integer padat, terurut, dan unik, sehingga kebanyakan sistem pencarian memakai u32 DocId. Pindah ke identifier 48 bit bukan otomatis lebih efisien, apalagi karena 48 bit ctid adalah gabungan dari dua domain angka yang berbeda, nomor blok yang bisa mencapai jutaan dan offset tuple yang paling besar 291.

DocId padat juga punya keuntungan kedua, yaitu mudah disambungkan ke penyimpanan kolom. Postings memberi tahu dokumen mana yang cocok, kolom memberi akses efisien ke atribut metadata dokumen seperti nilai numerik atau label kategori. Untuk query pencarian yang butuh filter dan agregasi, jembatan ini penting.

Yang Bisa Dipakai Ulang oleh Tim Lain

Pelajaran pertama: profil akses halaman lebih informatif daripada profil CPU ketika engine berjalan di atas block storage. Satu byte per dokumen bisa menjadi penyebab 83 persen pembacaan kalau letaknya tersebar. Pelajaran kedua: algoritma skipping yang menang bergantung bentuk kueri, dan mesin yang memilih dinamis akan mengalahkan mesin yang terpaku satu jalur. Pelajaran ketiga, dan ini yang paling sering diabaikan saat membandingkan angka vendor: pastikan kedua sisi menghitung fungsi yang sama sebelum berdebat soal kecepatan, karena konfigurasi yang terlihat sepele seperti shortcut term umum bisa memindahkan podium.

Untuk reproduksi, ParadeDB sudah menerbitkan release candidate 0.26.0-rc.2 dan menargetkan rilis stabil 0.26.0 pada pekan berikutnya, dengan catatan bahwa perbaikan ini akan digulirkan ke pengguna yang sudah berjalan. Yang ingin membandingkan sendiri bisa membaca post asli PlanetScale tentang TIN dan operator pencariannya di PostgreSQL sebelum benchmark ulang, dan yang sedang memilih mesin penyimpanan bisa mulai dari perbandingan SQLite versus PostgreSQL yang membahas batas masing-masing di beban kecil.