Postgres recursive CTE untuk tree traversal

Kategori produk Tokopedia bisa nested 5 level: Elektronik > HP & Tablet > Smartphone > Android > Sub-brand. Query “semua produk di kategori X dan keturunannya” butuh tree traversal. Recursive CTE handle ini elegan, native, no extension. Snippet ini pattern lengkap dengan cycle detection.

Kode

-- ==========================================
-- Schema kategori multi-level
-- ==========================================
CREATE TABLE kategori (
    id        BIGSERIAL PRIMARY KEY,
    nama      TEXT NOT NULL,
    parent_id BIGINT REFERENCES kategori(id),
    created_at TIMESTAMPTZ DEFAULT now()
);

CREATE INDEX idx_kategori_parent ON kategori(parent_id);

INSERT INTO kategori (id, nama, parent_id) VALUES
(1, 'Elektronik', NULL),
(2, 'HP & Tablet', 1),
(3, 'Komputer', 1),
(4, 'Smartphone', 2),
(5, 'Tablet', 2),
(6, 'Android', 4),
(7, 'iPhone', 4),
(8, 'Samsung', 6),
(9, 'Xiaomi', 6),
(10, 'Fashion', NULL),
(11, 'Pria', 10),
(12, 'Wanita', 10);

-- ==========================================
-- Pattern 1: TOP-DOWN — semua descendant kategori
-- ==========================================
-- Cari semua sub-kategori dari "HP & Tablet" (id=2)
WITH RECURSIVE descendant AS (
    -- Anchor: node root
    SELECT id, nama, parent_id, 1 AS depth,
           ARRAY[id] AS path,
           nama::TEXT AS full_path
    FROM kategori
    WHERE id = 2

    UNION ALL

    -- Recursive: anak dari node sebelumnya
    SELECT k.id, k.nama, k.parent_id, d.depth + 1,
           d.path || k.id,
           d.full_path || ' > ' || k.nama
    FROM kategori k
    JOIN descendant d ON k.parent_id = d.id
    WHERE NOT k.id = ANY(d.path)  -- CYCLE PROTECTION
      AND d.depth < 20             -- DEPTH LIMIT untuk safety
)
SELECT id, nama, depth, full_path
FROM descendant
ORDER BY path;

-- Output:
--  id |   nama     | depth | full_path
-- ----+------------+-------+-----------------------------------------
--   2 | HP & Tablet|     1 | HP & Tablet
--   4 | Smartphone |     2 | HP & Tablet > Smartphone
--   6 | Android    |     3 | HP & Tablet > Smartphone > Android
--   8 | Samsung    |     4 | HP & Tablet > Smartphone > Android > Samsung
--   9 | Xiaomi     |     4 | HP & Tablet > Smartphone > Android > Xiaomi
--   7 | iPhone     |     3 | HP & Tablet > Smartphone > iPhone
--   5 | Tablet     |     2 | HP & Tablet > Tablet

-- ==========================================
-- Pattern 2: BOTTOM-UP — breadcrumb dari node ke root
-- ==========================================
-- Tampilkan breadcrumb untuk kategori "Samsung" (id=8)
WITH RECURSIVE ancestor AS (
    SELECT id, nama, parent_id, 1 AS level
    FROM kategori
    WHERE id = 8

    UNION ALL

    SELECT k.id, k.nama, k.parent_id, a.level + 1
    FROM kategori k
    JOIN ancestor a ON k.id = a.parent_id
)
SELECT string_agg(nama, ' > ' ORDER BY level DESC) AS breadcrumb
FROM ancestor;

-- Output:
--                       breadcrumb
-- ------------------------------------------------
--  Elektronik > HP & Tablet > Smartphone > Android > Samsung

-- ==========================================
-- Pattern 3: COUNT descendants per node
-- ==========================================
-- Jumlah sub-kategori per root
WITH RECURSIVE tree AS (
    SELECT id AS root_id, id, nama, parent_id, 0 AS depth
    FROM kategori
    WHERE parent_id IS NULL

    UNION ALL

    SELECT t.root_id, k.id, k.nama, k.parent_id, t.depth + 1
    FROM kategori k
    JOIN tree t ON k.parent_id = t.id
)
SELECT k.id, k.nama,
       (SELECT COUNT(*) - 1 FROM tree WHERE root_id = k.id) AS total_descendant,
       (SELECT MAX(depth) FROM tree WHERE root_id = k.id) AS max_depth
FROM kategori k
WHERE k.parent_id IS NULL;

-- Output:
--  id |    nama    | total_descendant | max_depth
-- ----+------------+------------------+-----------
--   1 | Elektronik |                8 |         4
--  10 | Fashion    |                2 |         1

-- ==========================================
-- Pattern 4: JOIN dengan produk — semua produk di kategori + descendant
-- ==========================================
CREATE TABLE produk (
    id           BIGSERIAL PRIMARY KEY,
    nama         TEXT NOT NULL,
    kategori_id  BIGINT NOT NULL REFERENCES kategori(id),
    harga        BIGINT NOT NULL
);

INSERT INTO produk (nama, kategori_id, harga) VALUES
('Samsung Galaxy S24', 8, 14000000),
('Samsung Galaxy A15', 8, 2500000),
('Xiaomi Redmi 13', 9, 1800000),
('iPhone 15 Pro', 7, 22000000);

-- Cari semua produk di kategori "Smartphone" (id=4) DAN sub-nya
WITH RECURSIVE sub_kategori AS (
    SELECT id FROM kategori WHERE id = 4
    UNION ALL
    SELECT k.id FROM kategori k JOIN sub_kategori s ON k.parent_id = s.id
)
SELECT p.id, p.nama, p.harga, k.nama AS kategori
FROM produk p
JOIN kategori k ON p.kategori_id = k.id
WHERE p.kategori_id IN (SELECT id FROM sub_kategori)
ORDER BY p.harga DESC;

Pemakaian

-- Use case: org chart — siapa atasan dari atasan
WITH RECURSIVE atasan AS (
    SELECT employee_id, manager_id, nama, 1 AS level
    FROM employee
    WHERE employee_id = 12345

    UNION ALL

    SELECT e.employee_id, e.manager_id, e.nama, a.level + 1
    FROM employee e
    JOIN atasan a ON e.employee_id = a.manager_id
)
SELECT * FROM atasan WHERE level > 1;

-- Use case: file system path
WITH RECURSIVE folder_path AS (
    SELECT id, nama, parent_id, nama::TEXT AS path
    FROM folder WHERE parent_id IS NULL
    UNION ALL
    SELECT f.id, f.nama, f.parent_id, fp.path || '/' || f.nama
    FROM folder f JOIN folder_path fp ON f.parent_id = fp.id
)
SELECT id, path FROM folder_path WHERE path LIKE '/docs/%';

Kapan dipakai

• Kategori produk multi-level di e-commerce.
• Org chart untuk approval workflow.
• Threaded comment (Reddit/HN style).
• Bill of Material (BOM) di manufaktur.
• File system folder hierarchy.
• Graph traversal sederhana (depth-limited).

Catatan

• Cycle protection wajib — kalau ada bug di data (parent_id refer ke descendant), recursive CTE infinite loop sampai work_mem habis. Pakai array path + NOT id = ANY(path).
• Depth limit sebagai safety net — kasus realistis depth jarang > 10.
• UNION ALL bukan UNION — UNION dedupe tiap iterasi, hilangkan performance. UNION ALL hanya append.
• Anchor harus minimal — kalau anchor return juta-an row, recursive part eksekusi juta kali. Filter ketat di anchor.
• Closure table alternatif — untuk read-heavy tree, materialize ancestor-descendant pair di tabel terpisah. Faster query, slower write.
• ltree extension — kalau path traversal jadi bottleneck, ltree pakai GiST index untuk pattern matching. Worth migrate.

Recursive CTE hanya optimized di Postgres 14+. Sebelumnya, planner bisa misestimate row count dan generate plan jelek. Profile dengan EXPLAIN ANALYZE.