Advanced SQL: Recursive CTEs

Dữ liệu phân cấp (hierarchical data) xuất hiện khắp nơi: Cây danh mục sản phẩm, sơ đồ tổ chức, hệ thống comment lồng nhau. Recursive CTE là vũ khí tối thượng để xử lý chúng.

---

1️⃣ Concept: CTE tự gọi chính nó

Cấu trúc Recursive CTE

WITH RECURSIVE cte_name AS (
    -- 1. Anchor Member: Điểm bắt đầu (không recursive)
    SELECT columns FROM table WHERE condition
    
    UNION ALL
    
    -- 2. Recursive Member: Tự gọi lại cte_name
    SELECT columns FROM table 
    JOIN cte_name ON relationship
    WHERE termination_condition
)
SELECT * FROM cte_name;

Cơ chế hoạt động:

1. Vòng 1: Chạy Anchor Member, lấy kết quả gốc.
2. Vòng 2: Chạy Recursive Member, JOIN với kết quả vòng 1.
3. Vòng 3, 4, ...: Tiếp tục cho đến khi Recursive Member không trả về dòng mới.
4. Kết thúc: UNION ALL tất cả kết quả.

Ví dụ đơn giản: Đếm từ 1 đến 5

WITH RECURSIVE counter AS (
    -- Anchor: Bắt đầu từ 1
    SELECT 1 AS n
    
    UNION ALL
    
    -- Recursive: Cộng 1 cho đến khi n >= 5
    SELECT n + 1 
    FROM counter 
    WHERE n < 5
)
SELECT * FROM counter;

-- Kết quả:
-- n
-- ---
-- 1
-- 2
-- 3
-- 4
-- 5

---

2️⃣ Use Case 1: Organizational Chart (Manager -> Employee)

Schema

CREATE TABLE employees (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    manager_id INT REFERENCES employees(id),  -- Self-reference
    title VARCHAR(100)
);

-- Sample data
INSERT INTO employees (id, name, manager_id, title) VALUES
    (1, 'CEO Nguyễn', NULL, 'CEO'),
    (2, 'CTO Trần', 1, 'CTO'),
    (3, 'CFO Lê', 1, 'CFO'),
    (4, 'Tech Lead Phạm', 2, 'Tech Lead'),
    (5, 'Senior Dev Hoàng', 4, 'Senior Developer'),
    (6, 'Junior Dev An', 5, 'Junior Developer'),
    (7, 'Accountant Mai', 3, 'Accountant');

Hierarchy:
CEO Nguyễn
├── CTO Trần
│   └── Tech Lead Phạm
│       └── Senior Dev Hoàng
│           └── Junior Dev An
└── CFO Lê
    └── Accountant Mai

Query: Tìm tất cả nhân viên dưới quyền một manager

-- Tìm tất cả nhân viên dưới quyền CTO Trần (id=2)
WITH RECURSIVE subordinates AS (
    -- Anchor: Bắt đầu từ CTO
    SELECT id, name, manager_id, title, 1 AS level
    FROM employees
    WHERE id = 2
    
    UNION ALL
    
    -- Recursive: Tìm những người có manager_id = nhân viên ở vòng trước
    SELECT e.id, e.name, e.manager_id, e.title, s.level + 1
    FROM employees e
    JOIN subordinates s ON e.manager_id = s.id
)
SELECT * FROM subordinates;

-- Kết quả:
-- id |       name       | manager_id |      title       | level
-- ---+------------------+------------+------------------+-------
--  2 | CTO Trần         |          1 | CTO              |     1
--  4 | Tech Lead Phạm   |          2 | Tech Lead        |     2
--  5 | Senior Dev Hoàng |          4 | Senior Developer |     3
--  6 | Junior Dev An    |          5 | Junior Developer |     4

Query: Xây dựng đường dẫn (Path)

WITH RECURSIVE org_path AS (
    SELECT 
        id, 
        name, 
        manager_id,
        name AS path,  -- Path bắt đầu bằng tên
        1 AS depth
    FROM employees
    WHERE manager_id IS NULL  -- Bắt đầu từ root (CEO)
    
    UNION ALL
    
    SELECT 
        e.id, 
        e.name, 
        e.manager_id,
        p.path || ' > ' || e.name,  -- Nối thêm vào path
        p.depth + 1
    FROM employees e
    JOIN org_path p ON e.manager_id = p.id
)
SELECT path, depth FROM org_path ORDER BY depth;

-- Kết quả:
-- path                                             | depth
-- -------------------------------------------------+-------
-- CEO Nguyễn                                       |     1
-- CEO Nguyễn > CTO Trần                            |     2
-- CEO Nguyễn > CFO Lê                              |     2
-- CEO Nguyễn > CTO Trần > Tech Lead Phạm           |     3
-- CEO Nguyễn > CFO Lê > Accountant Mai             |     3
-- CEO Nguyễn > CTO Trần > Tech Lead Phạm > Senior...|     4

---

3️⃣ Use Case 2: Category Tree (E-commerce)

Schema

CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_id INT REFERENCES categories(id),
    slug VARCHAR(100) UNIQUE
);

INSERT INTO categories (id, name, parent_id, slug) VALUES
    (1, 'Electronics', NULL, 'electronics'),
    (2, 'Computers', 1, 'computers'),
    (3, 'Laptops', 2, 'laptops'),
    (4, 'MacBook', 3, 'macbook'),
    (5, 'MacBook Pro', 4, 'macbook-pro'),
    (6, 'MacBook Air', 4, 'macbook-air'),
    (7, 'Desktop', 2, 'desktop'),
    (8, 'Phones', 1, 'phones'),
    (9, 'iPhone', 8, 'iphone');

Category Tree:
Electronics
├── Computers
│   ├── Laptops
│   │   └── MacBook
│   │       ├── MacBook Pro
│   │       └── MacBook Air
│   └── Desktop
└── Phones
    └── iPhone

Query: Tìm tất cả category con (Descendants)

-- Tìm tất cả subcategories của "Computers" (id=2)
WITH RECURSIVE subcategories AS (
    SELECT id, name, parent_id, slug, 0 AS level
    FROM categories
    WHERE id = 2
    
    UNION ALL
    
    SELECT c.id, c.name, c.parent_id, c.slug, s.level + 1
    FROM categories c
    JOIN subcategories s ON c.parent_id = s.id
)
SELECT * FROM subcategories;

-- Kết quả bao gồm: Computers, Laptops, MacBook, MacBook Pro, MacBook Air, Desktop

Query: Tìm tất cả category cha (Ancestors)

-- Tìm breadcrumb cho "MacBook Pro" (id=5)
WITH RECURSIVE ancestors AS (
    -- Anchor: Bắt đầu từ node hiện tại
    SELECT id, name, parent_id, 1 AS level
    FROM categories
    WHERE id = 5
    
    UNION ALL
    
    -- Recursive: Đi ngược lên parent
    SELECT c.id, c.name, c.parent_id, a.level + 1
    FROM categories c
    JOIN ancestors a ON c.id = a.parent_id  -- JOIN ngược: c.id = a.parent_id
)
SELECT * FROM ancestors ORDER BY level DESC;

-- Kết quả:
-- id |     name     | parent_id | level
-- ---+--------------+-----------+-------
--  1 | Electronics  |      NULL |     4
--  2 | Computers    |         1 |     3
--  3 | Laptops      |         2 |     2
--  4 | MacBook      |         3 |     1  <-- Không có MacBook Pro vì đó là chính nó

-- Version hoàn chỉnh cho Breadcrumb
WITH RECURSIVE breadcrumb AS (
    SELECT id, name, parent_id, ARRAY[name] AS path
    FROM categories
    WHERE id = 5  -- MacBook Pro
    
    UNION ALL
    
    SELECT c.id, c.name, c.parent_id, c.name || b.path
    FROM categories c
    JOIN breadcrumb b ON c.id = b.parent_id
)
SELECT path FROM breadcrumb WHERE parent_id IS NULL;

-- Kết quả:
-- {Electronics,Computers,Laptops,MacBook,"MacBook Pro"}

---

4️⃣ Production Code: Utility Functions

Function: Get All Descendants

CREATE OR REPLACE FUNCTION get_category_descendants(root_id INT)
RETURNS TABLE (
    id INT,
    name VARCHAR,
    parent_id INT,
    level INT,
    path TEXT
) AS $$
BEGIN
    RETURN QUERY
    WITH RECURSIVE tree AS (
        SELECT 
            c.id, c.name, c.parent_id, 
            0 AS level, 
            c.name::TEXT AS path
        FROM categories c
        WHERE c.id = root_id
        
        UNION ALL
        
        SELECT 
            c.id, c.name, c.parent_id, 
            t.level + 1,
            t.path || ' > ' || c.name
        FROM categories c
        JOIN tree t ON c.parent_id = t.id
    )
    SELECT * FROM tree;
END;
$$ LANGUAGE plpgsql;

-- Usage
SELECT * FROM get_category_descendants(1);  -- All under Electronics

Function: Get Breadcrumb

CREATE OR REPLACE FUNCTION get_breadcrumb(node_id INT)
RETURNS TEXT[] AS $$
DECLARE
    result TEXT[];
BEGIN
    WITH RECURSIVE ancestors AS (
        SELECT id, name, parent_id
        FROM categories
        WHERE id = node_id
        
        UNION ALL
        
        SELECT c.id, c.name, c.parent_id
        FROM categories c
        JOIN ancestors a ON c.id = a.parent_id
    )
    SELECT ARRAY_AGG(name ORDER BY level DESC) INTO result
    FROM (
        SELECT name, ROW_NUMBER() OVER () AS level
        FROM ancestors
    ) sub;
    
    RETURN result;
END;
$$ LANGUAGE plpgsql;

-- Usage
SELECT get_breadcrumb(5);
-- Result: {Electronics,Computers,Laptops,MacBook,"MacBook Pro"}

---

5️⃣ Performance & Safety

Ngăn chặn Infinite Loop

-- NGUY HIỂM: Nếu data có cycle (A -> B -> A), query chạy vô hạn!
-- Giải pháp: Thêm điều kiện dừng

WITH RECURSIVE safe_tree AS (
    SELECT id, name, parent_id, ARRAY[id] AS visited, 1 AS depth
    FROM categories
    WHERE id = 1
    
    UNION ALL
    
    SELECT c.id, c.name, c.parent_id, 
           s.visited || c.id,
           s.depth + 1
    FROM categories c
    JOIN safe_tree s ON c.parent_id = s.id
    WHERE NOT c.id = ANY(s.visited)  -- Không visit lại node đã đi qua
      AND s.depth < 100              -- Giới hạn độ sâu tối đa
)
SELECT * FROM safe_tree;

Index cho Hierarchical Data

-- Index cơ bản
CREATE INDEX idx_categories_parent ON categories(parent_id);

-- Materialized Path (nếu denormalize)
ALTER TABLE categories ADD COLUMN path_array INT[];
CREATE INDEX idx_categories_path ON categories USING GIN(path_array);

⚠️ Recursive CTE và Performance

Recursive CTE không nhanh cho cây lớn (>10,000 nodes). Các giải pháp thay thế:

1. Nested Set Model: Pre-compute left/right values cho range query.
2. Materialized Path: Lưu đường dẫn như string/array (VD: 1/2/3/5).
3. Closure Table: Lưu tất cả các cặp ancestor-descendant.

---

Tổng kết

Pattern	Mô tả	Query Direction
Find Descendants	Từ root đi xuống	JOIN ON c.parent_id = tree.id
Find Ancestors	Từ leaf đi lên	JOIN ON c.id = tree.parent_id
Build Path	Tạo breadcrumb	Dùng `

-- Template tổng quát
WITH RECURSIVE tree AS (
    SELECT *, 0 AS level FROM table WHERE [start_condition]
    UNION ALL
    SELECT t.*, tree.level + 1 FROM table t
    JOIN tree ON [relationship]
    WHERE [termination_condition]
)
SELECT * FROM tree;

💡 HPN Pro Tip: Đừng sợ Recursive CTE

Nhiều developer tránh recursive CTE vì "phức tạp". Thực tế:

1. Nó là giải pháp SQL standard, portable giữa PostgreSQL, MySQL 8+, SQL Server.
2. Query optimizer của PostgreSQL xử lý tốt với proper index.
3. Với cây <1000 nodes, performance hoàn toàn acceptable (< 10ms).