Menghitung median pada SQL tidak sesederhana fungsi agregat AVG() atau SUM(). Median adalah nilai tengah dari kumpulan data terurut, yang secara teknis membutuhkan proses sortasi penuh dengan kompleksitas waktu minimal O(N log N). Pada dataset berisi puluhan juta baris, kalkulasi median naif memicu pemakaian memori masif (spill to disk pada work_mem) dan latensi tinggi.

Problem Operasional: Mengapa Median Memicu Memory Blowup?

Fungsi standar ANSI SQL untuk menghitung median eksak adalah PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY column). Masalah utama muncul ketika engine database harus membaca seluruh baris yang memenuhi kondisi filter ke dalam memori kerja sebelum melakukan pengurutan.

Jika alokasi memori query engine (seperti work_mem di PostgreSQL) lebih kecil dari ukuran set data terurut, engine beralih menggunakan algoritma External Merge Sort berbasis disk swap. Operasi I/O disk sekunder ini memicu bottleneck performa.

Metode 1: Kalkulasi Eksak dengan Optimasi Index B-Tree

B-Tree menyimpan data dalam struktur daun berurutan secara logis. Jika query median dapat memanfaatkan index scan langsung tanpa external sort, beban komputasi CPU dan memori berkurang drastis.

Implementasi PostgreSQL: PERCENTILE_CONT vs Limit-Offset Scan

Secara default, implementasi PERCENTILE_CONT pada PostgreSQL belum sepenuhnya memanfaatkan ordered index scan secara optimal untuk melewati tahap sortasi agregat. Pendekatan alternatif menggunakan subquery berbasis ROW_NUMBER() atau OFFSET memanfaatkan index B-Tree secara deterministik.

-- Setup Index Komposit
CREATE INDEX idx_transactions_status_amount ON transactions (status, amount);

-- Query Median Eksak Menggunakan Ordered Offset
WITH ordered_data AS (
    SELECT amount,
           ROW_NUMBER() OVER (ORDER BY amount) as row_id,
           COUNT(*) OVER () as total_rows
    FROM transactions
    WHERE status = 'settled'
)
SELECT AVG(amount) AS median_value
FROM ordered_data
WHERE row_id IN (FLOOR((total_rows + 1) / 2.0), CEIL((total_rows + 1) / 2.0));

Analisis EXPLAIN ANALYZE

Eksekusi query di atas terhadap tabel dengan 10 juta baris menghasilkan perbedaan rencana eksekusi berikut:

-- Tanpa Index Komposit:
Sort (cost=1254320.00..1279320.00 rows=10000000)
  Sort Key: amount
  Sort Method: external merge  Disk: 185420kB
  ->  Seq Scan on transactions (cost=0.00..179060.00 rows=10000000)
        Filter: (status = 'settled')

-- Dengan Index Komposit (status, amount):
Subquery Scan on ordered_data
  ->  WindowAgg (cost=0.56..345210.20 rows=10000000)
        ->  Index Only Scan using idx_transactions_status_amount on transactions
              Index Cond: (status = 'settled')

Penggunaan index komposit (status, amount) mengeliminasi operasi Sort Method: external merge menjadi Index Only Scan, menghilangkan I/O disk swap sepenuhnya.

Metode 2: Kalkulasi Eksak pada MySQL

MySQL (versi 8.0+) tidak memiliki fungsi bawaan PERCENTILE_CONT. Eksekusi median dilakukan melalui window function:

WITH ranked AS (
    SELECT amount,
           ROW_NUMBER() OVER (ORDER BY amount) as rnk,
           COUNT(*) OVER () as cnt
    FROM orders
    WHERE store_id = 42
)
SELECT AVG(amount) AS median
FROM ranked
WHERE rnk IN (FLOOR((cnt + 1) / 2), CEIL((cnt + 2) / 2));

Pastikan index (store_id, amount) aktif agar engine mengeksekusi pipeline ranking secara stream tanpa alokasi temporary table di disk.

Metode 3: Algoritma Aproksimasi untuk Skala Besar

Ketika volume data mencapai ratusan juta baris, pembacaan index terurut tetap membutuhkan waktu I/O tinggi karena random read traversal pada B-Tree. Solusinya adalah beralih dari kalkulasi eksak ke estimasi aproksimasi dengan toleransi eror rendah (< 1%).

t-digest vs HyperLogLog

  • HyperLogLog (HLL): Dirancang untuk cardinality estimation (menghitung distinct count). HLL tidak mempertahankan distribusi nilai numerik, sehingga tidak dapat digunakan untuk menghitung median atau persentil.
  • t-digest: Algoritma clustering berbasis centroid yang dirancang khusus untuk mengestimasi kuantil/rank pada stream data besar. t-digest mempertahankan akurasi tinggi pada nilai ekstrem (p99, p99.9) maupun median (p50) dengan konsumsi memori konstan (beberapa kilobyte).

Implementasi PostgreSQL dengan TimescaleDB Toolkit

Jika menggunakan PostgreSQL, ekstensi timescaledb_toolkit menyediakan implementasi native t-digest:

-- Menghitung Aproksimasi Median
SELECT 
    approx_percentile(0.5, percentile_agg(amount)) AS median_approx
FROM transactions
WHERE status = 'settled';

Keunggulan algoritma t-digest:

  • Dapat diparalelisasi penuh (Parallel Worker scan).
  • Data centroid dapat disimpan parsial secara berkala (Continuous Aggregates) lalu digabungkan (rollup) tanpa re-scanning raw table.
  • Beban memori tetap berada pada kisaran kilobyte terlepas dari jumlah baris data.

Panduan Pemilihan Strategi

  1. Data < 5 Juta Baris + Kebutuhan Finansial/Audit: Gunakan metode eksak PERCENTILE_CONT atau ranking subquery dengan index B-Tree komposit yang mencakup predikat filter dan sort key.
  2. Data > 10 Juta Baris + Kebutuhan Monitoring/Dashboard: Gunakan aproksimasi t-digest. Mengorbankan akurasi fraksional demi latensi respon query sub-detik tanpa risiko memory blowup.
  3. B-Tree Indexing Rule: Susun index mengikuti pola Equality-First: CREATE INDEX idx_name ON table (equality_filter_column, metric_column ASC).