Masalah Skalabilitas B-Tree pada Data Append-Only

Tabel audit log dan event streaming memiliki sifat append-only dengan pertumbuhan volume data yang konstan. Pendekatan standar menggunakan index B-Tree pada kolom timestamp (seperti created_at) cepat menimbulkan masalah performa saat data menembus puluhan hingga ratusan juta baris.

B-Tree mencatat pointer ke setiap baris data secara individual. Pada tabel berskala 200 juta baris, index B-Tree dapat menghabiskan ruang disk puluhan gigabyte. Konsekuensi langsungnya adalah:

  • RAM Thrashing: Ukuran index melebihi alokasi shared_buffers. Setiap eksekusi query memaksa PostgreSQL melakukan page eviction berulang kali.
  • Tingginya Write Amplification: Setiap operasi INSERT memicu pembaruan pohon B-Tree beserta penyeimbangan node (page splits), meningkatkan I/O write secara drastis.
  • Cold Cache Penalty: Pembacaan data historis memicu random disk reads yang lambat karena index tidak lagi muat di memory.

Mekanisme BRIN (Block Range Index)

BRIN didesain khusus untuk tabel berukuran masif di mana nilai kolom target berkorelasi linier dengan posisi fisiknya di disk. Alih-alih memetakan setiap baris, BRIN membagi heap tabel menjadi rentang blok fisik (block ranges) dan hanya menyimpan nilai minimum serta maksimum untuk setiap rentang tersebut.

Ketika query dengan filter rentang waktu dieksekusi, perencana query PostgreSQL memeriksa metadata ringkas ini. Blok data fisik yang berada di luar rentang min/max akan langsung dilewati (block skipping), dan hanya blok yang relevan yang dibaca menggunakan Bitmap Heap Scan.

Prasyarat: Validasi Korelasi Fisik via pg_stats

BRIN tidak efektif jika urutan fisik data pada disk acak. Kolom harus memiliki korelasi fisik mendekati 1.0 (atau -1.0). Jalankan query berikut pada target tabel:

SELECT 
    attname, 
    correlation 
FROM 
    pg_stats 
WHERE 
    tablename = 'audit_logs' 
    AND attname = 'created_at';

Nilai korelasi yang ideal berada di atas 0.95. Data append-only dengan timestamp default CURRENT_TIMESTAMP atau NOW() secara alami memiliki korelasi mendekati 1.0 karena baris baru selalu ditulis di blok akhir tabel.

Implementasi Skrip DDL dan Pengujian

Gunakan skema simulasi audit log berikut untuk menguji efisiensi ruang dan kecepatan eksekusi query:

-- Skema tabel audit log
CREATE TABLE audit_logs (
    id BIGSERIAL,
    user_id INT NOT NULL,
    action VARCHAR(64) NOT NULL,
    payload JSONB,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

-- Pengisian data simulasi 20 juta baris berurutan secara temporal
INSERT INTO audit_logs (user_id, action, payload, created_at)
SELECT 
    (random() * 10000)::INT,
    'AUTH_LOGIN',
    '{"ip": "192.168.1.1"}'::jsonb,
    g
FROM generate_series(
    NOW() - INTERVAL '180 days',
    NOW(),
    INTERVAL '0.7776 seconds'
) AS g;

Pembuatan Index: B-Tree vs BRIN

-- Index B-Tree konvensional
CREATE INDEX idx_audit_btree_created ON audit_logs(created_at);

-- Index BRIN dengan parameter pages_per_range yang disesuaikan
CREATE INDEX idx_audit_brin_created ON audit_logs USING brin(created_at) 
WITH (pages_per_range = 32, autosummarize = on);

Perbandingan Ukuran dan Efisiensi Memory

Periksa perbandingan konsumsi ruang disk antara kedua index:

SELECT 
    c.relname AS index_name,
    pg_size_pretty(pg_relation_size(c.oid)) AS index_size
FROM pg_class c
JOIN pg_namespace n ON n.oid = c.relnamespace
WHERE c.relname IN ('idx_audit_btree_created', 'idx_audit_brin_created');

Hasil representatif pada dataset 20 juta baris:

  • B-Tree (idx_audit_btree_created): ~430 MB
  • BRIN (idx_audit_brin_created): ~320 KB

BRIN mereduksi ukuran index hingga lebih dari 99%. Penurunan drastis ini memungkinkan seluruh struktur index tetap berada di dalam L1/L2 cache sistem operasi dan shared_buffers, mengeliminasi RAM thrashing sepenuhnya.

Evaluasi Query via EXPLAIN ANALYZE

Uji query pencarian rentang audit log 1 jam:

EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*)
FROM audit_logs
WHERE created_at BETWEEN NOW() - INTERVAL '10 days' AND NOW() - INTERVAL '10 days' + INTERVAL '1 hour';

Karakteristik Eksekusi

  • Dengan B-Tree: Waktu eksekusi berkisar antara 1-3 ms. Seluruh page index diakses melalui Index Scan atau Bitmap Index Scan. Konsumsi buffer index tinggi jika pencarian rentang meluas.
  • Dengan BRIN: Waktu eksekusi berkisar antara 4-12 ms. Perencana query melakukan Bitmap Index Scan pada index BRIN yang sangat kecil, lalu memfilter heap data. Sedikit peningkatan CPU time dikompensasi oleh penghematan I/O memory yang masif.

Tuning Parameter pages_per_range dan Pemeliharaan

Parameter pages_per_range mengontrol berapa blok tabel 8KB yang dimasukkan ke dalam satu rentang metadata. Nilai default PostgreSQL adalah 128 (setara 1 MB data heap per rentang ringkasan).

Menentukan Nilai pages_per_range

  • Nilai Kecil (16 - 32): Meningkatkan presisi filtering. Mengurangi pembacaan blok yang tidak perlu di level heap (mengurangi false positive rows). Ukuran index sedikit lebih besar, ideal untuk query dengan filter rentang waktu sempit.
  • Nilai Besar (64 - 128): Ukuran index sangat minimal, tetapi rentang blok lebih longgar. Cocok untuk reporting analitik yang membaca rentang data mingguan atau bulanan.

Otomasi Summarization

Pada data yang terus masuk secara streaming, rentang blok baru tidak langsung diringkas sampai terisi penuh. Parameter autosummarize = on memastikan background worker memperbarui index secara mandiri. Alternatif manual dapat dijalankan melalui cron job:

SELECT brin_summarize_new_values('idx_audit_brin_created');

Kapan BRIN Harus Dihindari

BRIN bukan pengganti general-purpose untuk B-Tree. Hindari implementasi BRIN pada skenario berikut:

  1. Data Out-of-Order: Data dikirim dari distributed client dengan latency jaringan bervariasi, menyebabkan timestamp masa lalu tertulis di blok fisik paling baru (korelasi fisik anjlok < 0.8).
  2. Operasi UPDATE/DELETE Intensif: Menghapus atau memperbarui baris menyebabkan PostgreSQL menulis tuple baru di heap page berbeda, memperluas batas min/max pada rentang blok dan merusak selektivitas BRIN.
  3. Point Query Selektivitas Ekstrem: Query yang mencari satu record spesifik (misal berdasarkan uuid unik) memerlukan latensi sub-milidetik yang hanya dapat dipenuhi oleh B-Tree atau Hash index.