Masalah Performa Indexing pada Data Acak

Saat melakukan bulk insert ke SQLite pada tabel yang memiliki indeks (atau saat mengisi data sebelum menjalankan CREATE INDEX), urutan data mentah menentukan efisiensi operasi B-Tree. SQLite menyusun tabel dan indeks menggunakan struktur B-Tree berbasis halaman (default ukuran halaman adalah 4096 byte).

Ketika data dimasukkan dalam urutan acak:

  • B-Tree Page Splits: SQLite harus membagi halaman indeks yang penuh ke halaman baru secara terus-menerus di berbagai level hierarki pohon.
  • Disk I/O Churn: Halaman yang baru dimodifikasi dikeluarkan dari cache memori jika kapasitas cache_size tidak cukup menampung seluruh working tree, menyebabkan pembacaan dan penulisan ulang halaman disk (thrashing).
  • Database Fragmentation: Struktur fisik berkas menjadi terfragmentasi, yang memperlambat query berurutan (range scans) di kemudian hari.

Mekanisme Kerja Teknik Pre-Sort Data

Teknik pre-sort mengurutkan data mentah terlebih dahulu di memori atau via temporary storage sesuai urutan kolom indeks komposit atau primary key sebelum data ditulis ke tabel target atau diindeks.

Ketika baris masuk secara berurutan:

  1. Penyisipan elemen baru selalu mengarah ke halaman B-Tree paling kanan (leaf page paling akhir).
  2. Halaman sebelumnya langsung diisi hingga kapasitas maksimum tanpa perlu dibagi kembali di tengah pohon (meminimalisasi page splits).
  3. Pola I/O berubah dari random writes menjadi sequential writes, memaksimalkan efisiensi kernel cache dan sistem file underlying.

Konfigurasi PRAGMA Esensial

Sebelum menjalankan proses bulk data atau re-indexing, sesuaikan konfigurasi internal SQLite untuk memindahkan alokasi proses sortir ke RAM:

-- Matikan synchronous disk flush selama proses batch
PRAGMA synchronous = OFF;

-- Simpan temporary tables dan temporary indices di RAM, bukan disk
PRAGMA temp_store = MEMORY;

-- Alokasikan cache memori (misal: -64000 = ~64MB memory)
PRAGMA cache_size = -64000;

-- Gunakan mode WAL untuk efisiensi transaksi penulisan
PRAGMA journal_mode = WAL;

Implementasi Benchmark: Data Acak vs Pre-Sorted

Berikut implementasi pengujian komparasi menggunakan skrip SQLite. Skenario menguji penyisipan 1.000.000 baris data acak vs data yang telah diurutkan terlebih dahulu.

1. Schema dan Data Acak (Unsorted Insert)

CREATE TABLE raw_events (
    id INTEGER PRIMARY KEY,
    user_id INTEGER,
    event_time INTEGER,
    payload TEXT
);

-- Simulasi 1 juta baris data dengan ID acak
BEGIN TRANSACTION;
WITH RECURSIVE generate_series(value) AS (
    SELECT 1
    UNION ALL
    SELECT value + 1 FROM generate_series WHERE value < 1000000
)
INSERT INTO raw_events (id, user_id, event_time, payload)
SELECT 
    abs(random() % 10000000),
    abs(random() % 50000),
    strftime('%s', 'now') - abs(random() % 86400),
    'event_payload_hash_' || value
FROM generate_series;
COMMIT;

-- Membuat index pada data acak (Memaksa disk I/O tinggi dan page splits)
CREATE INDEX idx_raw_user_time ON raw_events(user_id, event_time);

2. Pendekatan Pre-Sorted Bulk Insert

Daripada langsung mengindeks data acak, salin data ke tabel target menggunakan urutan ORDER BY yang selaras dengan indeks tujuan:

CREATE TABLE target_events (
    id INTEGER PRIMARY KEY,
    user_id INTEGER,
    event_time INTEGER,
    payload TEXT
);

CREATE INDEX idx_target_user_time ON target_events(user_id, event_time);

-- Masukkan data dengan pre-sort langsung melalui temporary sort SQLite
BEGIN TRANSACTION;
INSERT INTO target_events (id, user_id, event_time, payload)
SELECT id, user_id, event_time, payload
FROM raw_events
ORDER BY user_id ASC, event_time ASC;
COMMIT;

Hasil operasional menunjukkan waktu eksekusi yang berbeda signifikan pada dataset besar. Pada dataset jutaan baris, memasukkan data yang telah di-sort langsung ke tabel berindeks mengurangi waktu eksekusi hingga 40-60% dibanding mengindeks dataset acak, serta menghasilkan ukuran berkas database akhir yang lebih kecil karena halaman B-Tree terisi padat tanpa banyak slack space.

Analisis Query Plan

Gunakan perintah EXPLAIN QUERY PLAN untuk memverifikasi apakah SQLite melakukan sorting internal saat eksekusi:

EXPLAIN QUERY PLAN
SELECT id, user_id, event_time, payload
FROM raw_events
ORDER BY user_id ASC, event_time ASC;

Output tipikal:

QUERY PLAN
|--SCAN raw_events
`--USE TEMP B-TREE FOR ORDER BY

Log di atas menunjukkan SQLite menggunakan B-Tree sementara di memori (sesuai setting PRAGMA temp_store = MEMORY) untuk menyortir data sebelum menyimpannya ke tabel target.

Trade-offs dan Keterbatasan

  • Beban Memori: Sorting jutaan baris di RAM membutuhkan kapasitas memori yang cukup. Jika data melebihi ukuran memori yang dialokasikan pada PRAGMA cache_size, SQLite akan menulis temporary files ke disk, menurunkan efisiensi.
  • Banyak Indeks (Multiple Indexes): Teknik pre-sort hanya optimal untuk satu urutan indeks utama. Jika tabel memiliki beberapa indeks dengan kolom yang saling bertolak belakang (misal: idx_user dan idx_created_at), data hanya dapat dioptimasi untuk salah satu struktur B-Tree.
  • Rekomendasi Alternatif: Untuk data yang sangat masif, pendekatan standar yang tetap disarankan adalah: drop index → bulk insert data → create index. Namun, jika pipeline streaming atau batch ETL mengharuskan indeks tetap aktif, pre-sorting data sebelum operasi INSERT merupakan solusi tercepat.