Model data hierarkis berbasis adjacency list sering kali menjadi sumber bottleneck performa di SQL. Pola traversal standar menggunakan WITH RECURSIVE (Common Table Expression / CTE) memproses data tingkat demi tingkat secara iteratif. Pada dataset pohon dengan kedalaman tinggi atau ratusan ribu baris, pendekatan ini menyebabkan alokasi memori kerja (work_mem) melonjak dan memicu spill to disk.

Artikel ini mengulas cara mengeliminasi kelemahan CTE rekursif dengan menerapkan konsep dekomposisi fungsional: memisahkan penyimpanan relasi graf via closure table dan mengalihkan kalkulasi agregasi hierarkis ke window function.

Bottleneck pada Native Recursive CTE

Secara internal, engine PostgreSQL menjalankan WITH RECURSIVE menggunakan node eksekusi WorkTable Scan. Pada setiap iterasi hierarki, basis data harus membaca relasi intermediate, melakukan join ke tabel asli, dan menulis hasilnya kembali ke memori kerja.

-- Skema Adjacency List Standar
CREATE TABLE categories (
    id INT PRIMARY KEY,
    parent_id INT REFERENCES categories(id),
    name VARCHAR(100),
    amount NUMERIC(12, 2)
);
CREATE INDEX idx_categories_parent ON categories(parent_id);

Query rekursif untuk menghitung total akumulasi nilai per cabang:

WITH RECURSIVE tree AS (
    SELECT id, parent_id, amount, ARRAY[id] AS path
    FROM categories
    WHERE parent_id IS NULL
    UNION ALL
    SELECT c.id, c.parent_id, c.amount, t.path || c.id
    FROM categories c
    JOIN tree t ON c.parent_id = t.id
)
SELECT id, amount, path FROM tree;

Kelemahan teknis dari pola di atas:

  • I/O Buffer Bloat: Setiap level hierarki menciptakan buffer baru. Engine tidak dapat memparalelkan loop rekursif ini.
  • Performa Degradasi O(N * Depth): Semakin dalam hierarki data, semakin banyak operasi scan berulang pada WorkTable.

Dekomposisi Fungsional: Pemisahan Relasi dan Komputasi

Dalam functional programming, perulangan rekursif diubah menjadi operasi reduksi data set (map/reduce). Di SQL, konsep ini dicapai dengan mendekomposisi relasi hierarki statis ke dalam skema Closure Table, lalu menerapkan window function untuk kalkulasi analitik satu kali jalan (single-pass).

Skema Closure Table

CREATE TABLE category_paths (
    ancestor_id INT NOT NULL REFERENCES categories(id),
    descendant_id INT NOT NULL REFERENCES categories(id),
    depth INT NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id)
);
CREATE INDEX idx_closure_descendant ON category_paths(descendant_id);

Closure table memetakan seluruh relasi leluhur-keturunan secara persisten. Read query tidak lagi memerlukan loop rekursif.

Optimasi Query Rekursif SQL Menggunakan Window Function

Setelah hierarki didekomposisi, komputasi agregat hierarkis (seperti rolling metrics, ranking cabang, dan perhitungan bobot hierarki) dapat dihitung langsung tanpa iterasi menggunakan kombinasi join flat dan window function.

SELECT 
    cp.ancestor_id,
    c.id AS node_id,
    cp.depth,
    c.amount,
    -- Agregasi partisi hierarkis via window function
    SUM(c.amount) OVER(
        PARTITION BY cp.ancestor_id
    ) AS total_subtree_amount,
    DENSE_RANK() OVER(
        PARTITION BY cp.ancestor_id 
        ORDER BY cp.depth ASC, c.amount DESC
    ) AS rank_in_subtree
FROM category_paths cp
JOIN categories c ON cp.descendant_id = c.id
WHERE cp.ancestor_id = 1;

Eksekusi ini berjalan secara linier: data ditarik melalui Index Scan pada primary key tabel closure, lalu dialirkan langsung ke operator WindowAgg tanpa loop stateful.

Analisis Eksekusi dan Buffer I/O

Hasil perbandingan menggunakan EXPLAIN (ANALYZE, BUFFERS) pada dataset pengujian dengan 50.000 baris dan kedalaman pohon maksimum 18 tingkat:

1. Recursive CTE (Adjacency List)

CTE Scan on tree  (cost=1205.40..2510.80 rows=50000 width=48) (actual time=0.082..124.310 rows=50000 loops=1)
  Buffers: shared hit=4812 read=1240, temp read=1820 written=1824
  CTE tree
    ->  Recursive Union
          ->  Index Scan using idx_categories_parent ...
          ->  Hash Join
                ->  WorkTable Scan on tree t ...

Evaluasi: Terjadi temp read dan temp written. PostgreSQL kehabisan memori internal di node rekursif sehingga menulis status parsial ke disk storage.

2. Closure Table + Window Function

WindowAgg  (cost=210.15..890.30 rows=5000 width=40) (actual time=0.045..14.210 rows=5000 loops=1)
  Buffers: shared hit=342 read=0
  ->  Sort  (cost=210.15..222.65 rows=5000 width=20)
        Sort Key: cp.depth, c.amount DESC
        Sort Method: quicksort  Memory: 412kB
        ->  Nested Loop ...
              ->  Index Scan using category_paths_pkey ...

Evaluasi: Eliminasi I/O disk secara penuh (temp read/written: 0). Waktu eksekusi turun drastis dari 124 ms menjadi 14 ms karena engine cukup melakukan traversal indeks flat B-Tree dan operasi WindowAgg berbasis memori.

Trade-off dan Implementasi Praktis

Pola optimasi ini bukan solusi tanpa konsekuensi:

  • Overhead Tulis: Closure Table memerlukan trigger atau penanganan logika di repository layer untuk menyisipkan path setiap kali ada baris baru. Biaya write naik dari O(1) menjadi O(Depth).
  • Kapasitas Storage: Tabel closure memerlukan ruang disk tambahan untuk menyimpan pemetaan N:N seluruh kedalaman relasi.
  • Rekomendasi Pemilihan: Gunakan WITH RECURSIVE murni untuk write-heavy graph dengan struktur dangkal (depth < 4). Gunakan Closure Table dikombinasikan dengan window function untuk sistem analitik read-heavy, organisasi multi-level, atau katalog produk berkedalaman tinggi.