Recursive CTE — duyệt cây comment, breadcrumb, và hierarchy trong SQL

TaskFlow lưu comment của mỗi task trong bảng comments. Một comment có thể reply vào comment khác — tạo ra thread lồng nhau nhiều cấp. Để lưu quan hệ parent–child đó, bảng comments được mở rộng với một cột parent_id tự tham chiếu:

-- Schema goc cua comments (TaskFlow canonical)
-- id BIGSERIAL, task_id, user_id, body, created_at

-- Extend them parent_id de ho tro thread (giai thich trong bai)
ALTER TABLE comments ADD COLUMN parent_id BIGINT REFERENCES comments(id);
-- NULL = root comment (khong phai reply)
-- parent_id = X = reply cua comment X

Bây giờ yêu cầu thực tế xuất hiện: "Lấy toàn bộ replies của comment #100, bao gồm replies của replies." Hay ngược lại: "Trace từ comment #250 lên root để render breadcrumb." Đây là bài toán traversal trên cây — không thể giải bằng JOIN đơn hay subquery tĩnh vì độ sâu không biết trước. SQL có câu trả lời: WITH RECURSIVE.

1. Analogy — Cây gia đình

Hình dung bạn đang vẽ cây gia phả. Bạn là điểm xuất phát (anchor). Để tìm mọi tổ tiên, bạn làm từng bước:

Mỗi vòng lặp chỉ nhìn thấy kết quả của vòng trước — không phải toàn bộ CTE tích lũy. PostgreSQL UNION ALL toàn bộ lại sau.

2. Cú pháp WITH RECURSIVE — anatomy

WITH RECURSIVE cte_name AS (
  -- Anchor: base case, khong duoc reference cte_name
  SELECT col1, col2, ...
  FROM source_table
  WHERE <dieu_kien_bat_dau>

  UNION ALL

  -- Recursive part: reference cte_name (ket qua vong truoc)
  SELECT s.col1, s.col2, ...
  FROM source_table s
  JOIN cte_name c ON <dieu_kien_lien_ket>
  -- WHERE <termination condition nham tranh infinite loop>
)
SELECT * FROM cte_name;

Cơ chế thực thi (PostgreSQL):

1. Eval anchor → kết quả ban đầu gọi là working table (cte_name = anchor result).
2. Eval recursive part, thay cte_name bằng working table hiện tại → new rows.
3. UNION ALL append new rows vào result set tích lũy; working table = new rows.
4. Lặp lại bước 2–3 đến khi recursive part trả về 0 row → dừng.
5. Trả toàn bộ result set tích lũy về SELECT * FROM cte_name.

Lưu ý quan trọng:

• Phải dùng UNION ALL, không phải UNION. UNION dedup mỗi vòng — tốn kém và có thể kết thúc sớm sai logic.
• Cột trong recursive part phải khớp kiểu với anchor (số lượng và thứ tự cột).
• WITH RECURSIVE khai báo intention — PostgreSQL sẽ không báo lỗi nếu CTE thực sự không recursive; chỉ cần có từ khóa khi bạn định dùng self-reference.

3. Demo 1 — comment thread tree

Lấy toàn bộ comment trong thread của comment #100, kèm độ sâu để render indent:

-- Recursive: lay full thread cua root comment id = 100
WITH RECURSIVE thread AS (
  -- Anchor: comment goc
  SELECT id, parent_id, body, user_id, created_at, 0 AS depth
  FROM comments
  WHERE id = 100

  UNION ALL

  -- Recursive: con cua comment vong truoc
  SELECT c.id, c.parent_id, c.body, c.user_id, c.created_at, t.depth + 1
  FROM comments c
  JOIN thread t ON c.parent_id = t.id
)
SELECT
  depth,
  repeat('  ', depth) || body AS indented_body,
  created_at
FROM thread
ORDER BY depth, created_at;

-- depth | indented_body                              | created_at
--   0   | Root comment: "Deploy API thi bi loi 500?" | 2024-01-10 09:00
--   1   |   "Loi o middleware auth, toi se fix"      | 2024-01-10 09:15
--   1   |   "Co log khong, cho toi xem"              | 2024-01-10 09:20
--   2   |     "Day: [stack trace...]"                 | 2024-01-10 09:22
--   2   |     "Da fix, deploy lai di"                 | 2024-01-10 09:45

Vòng 1 (anchor): lấy comment id=100, depth=0. Vòng 2 (recursive): tìm mọi comment có parent_id = 100, gán depth=1. Vòng 3: tìm mọi comment có parent_id trong tập id của depth=1, gán depth=2. Tiếp tục đến khi không còn reply nào mới.

4. Demo 2 — breadcrumb path từ leaf lên root

Hướng ngược lại: từ một comment lá, trace lên root để render breadcrumb Root > Level1 > Level2 > Leaf:

-- Tu comment id = 250, trace nguoc len root
WITH RECURSIVE breadcrumb AS (
  -- Anchor: comment la (bat dau tu day)
  SELECT id, parent_id, body, 0 AS level
  FROM comments
  WHERE id = 250

  UNION ALL

  -- Recursive: cha cua comment vong truoc
  SELECT c.id, c.parent_id, c.body, b.level + 1
  FROM comments c
  JOIN breadcrumb b ON c.id = b.parent_id
  -- Dieu kien noi: c.id = b.parent_id (nguoc chieu voi demo 1)
)
SELECT level, body
FROM breadcrumb
ORDER BY level DESC;
-- level=N la root (to tiên xa nhat tim duoc)
-- level=0 la comment ban dau (id=250)

-- Render breadcrumb: dao nguoc thu tu (ORDER BY level DESC)
-- "Deploy discussion" > "Auth bug" > "Log request" > "Here is the trace"

Demo 1 đi xuống (tìm con): JOIN thread t ON c.parent_id = t.id. Demo 2 đi lên (tìm cha): JOIN breadcrumb b ON c.id = b.parent_id. Chỉ thay đổi điều kiện JOIN — cùng một pattern.

5. Cycle prevention — path array và CYCLE clause

Dữ liệu sai (typo, bug import) có thể tạo cycle: comment A là cha của B, B là cha của A. Không có cycle prevention, recursive CTE sẽ chạy mãi cho đến khi hết memory (PostgreSQL không có depth cap mặc định).

Cách 1: Track path array (mọi version PG):

WITH RECURSIVE thread AS (
  SELECT id, parent_id, body,
         ARRAY[id]  AS path,    -- path = danh sach id da di qua
         false      AS is_cycle
  FROM comments
  WHERE id = 100

  UNION ALL

  SELECT c.id, c.parent_id, c.body,
         t.path || c.id,              -- them id moi vao path
         c.id = ANY(t.path)           -- TRUE neu id nay da xuat hien
  FROM comments c
  JOIN thread t ON c.parent_id = t.id
  WHERE NOT t.is_cycle  -- dung lai khi gap cycle, khong expand tiep
)
SELECT id, body, path, is_cycle
FROM thread
WHERE NOT is_cycle;  -- loc bo row cycle neu can

Cách 2: CYCLE clause — SQL standard, PG 14+:

WITH RECURSIVE thread AS (
  SELECT id, parent_id, body
  FROM comments
  WHERE id = 100

  UNION ALL

  SELECT c.id, c.parent_id, c.body
  FROM comments c
  JOIN thread t ON c.parent_id = t.id
)
CYCLE id SET is_cycle USING path
-- is_cycle: boolean, TRUE khi id da xuat hien trong path
-- path: array tracking duong di (tu dong quan ly boi PG)
SELECT * FROM thread WHERE NOT is_cycle;

CYCLE id SET is_cycle USING path yêu cầu PostgreSQL tự động track cột id để phát hiện cycle — gọn hơn cách 1 và đúng SQL standard. Nếu đang dùng PG 14+, ưu tiên cách này.

6. Termination — depth limit để tránh infinite loop

Ngay cả không có cycle trong dữ liệu, tree rất sâu (hoặc dữ liệu bất ngờ) có thể khiến recursive CTE chạy lâu. Thêm điều kiện depth limit là safety cap nên có ở production:

WITH RECURSIVE thread AS (
  SELECT id, parent_id, body, 0 AS depth
  FROM comments
  WHERE id = 100

  UNION ALL

  SELECT c.id, c.parent_id, c.body, t.depth + 1
  FROM comments c
  JOIN thread t ON c.parent_id = t.id
  WHERE t.depth < 50  -- safety cap: khong di sau qua 50 cap
  -- Khi depth = 50, dieu kien WHERE fail, recursive part tra 0 row -> dung
)
SELECT * FROM thread;

WHERE t.depth < 50 nằm trong recursive part — khi depth của vòng trước đã là 50, điều kiện fail, không có row mới, CTE tự dừng. Nếu đặt ở query cuối (SELECT * FROM thread WHERE depth < 50) thì vẫn chạy vô tận — chỉ filter kết quả, không dừng recursion.

7. Performance — khi nào nên dùng alternative

Recursive CTE hoạt động tốt với cây nông (dưới 10–15 cấp). Với tree sâu hơn, mỗi vòng là một JOIN giữa recursive part và toàn bộ CTE tích lũy — chi phí tăng tuyến tính theo độ sâu.

Nguyên tắc thực tế: recursive CTE đủ dùng cho 95% trường hợp trong TaskFlow (comment thread thường không quá 10 cấp, query không cực kỳ hot). Cân nhắc chuyển sang ltree hoặc closure table khi:

• Tree vượt 50 cấp thường xuyên.
• Endpoint query tree chạy hơn 1000 lần/giây.
• Cần query tất cả descendant của nhiều node cùng lúc hiệu quả.

Với graph workload thực sự (shortest path, transitive closure trên đồ thị tổng quát), recursive SQL có thể làm được nhưng không tối ưu — đây là domain của graph database (Neo4j, Memgraph) hoặc PG extension age (Apache AGE).

8. Pitfall

-- WRONG: WHERE o cuoi chi filter ket qua, khong dung recursion
WITH RECURSIVE thread AS (
  SELECT id, parent_id, body, 0 AS depth FROM comments WHERE id = 100
  UNION ALL
  SELECT c.id, c.parent_id, c.body, t.depth + 1
  FROM comments c JOIN thread t ON c.parent_id = t.id
  -- Khong co WHERE depth < N trong recursive part -> chay vo tan neu co cycle
)
SELECT * FROM thread WHERE depth < 50;  -- chi filter output, khong dung recursion!

-- CORRECT: WHERE trong recursive part
WITH RECURSIVE thread AS (
  SELECT id, parent_id, body, 0 AS depth FROM comments WHERE id = 100
  UNION ALL
  SELECT c.id, c.parent_id, c.body, t.depth + 1
  FROM comments c JOIN thread t ON c.parent_id = t.id
  WHERE t.depth < 50  -- nam TRONG recursive part -> thuc su dung
)
SELECT * FROM thread;

9. Applied — TaskFlow comment thread API

Endpoint GET /threads/:id cần trả toàn bộ comment trong một thread, kèm tên tác giả, sắp xếp theo thứ tự render tự nhiên (depth-first, chronological trong mỗi cấp):

-- Endpoint: GET /threads/100
-- $1 = root comment id (bind parameter)
WITH RECURSIVE thread AS (
  -- Anchor: root comment
  SELECT id, parent_id, user_id, body, created_at, 0 AS depth
  FROM comments
  WHERE id = $1

  UNION ALL

  -- Recursive: lay con cua comment vong truoc
  SELECT c.id, c.parent_id, c.user_id, c.body, c.created_at, t.depth + 1
  FROM comments c
  JOIN thread t ON c.parent_id = t.id
  WHERE t.depth < 50  -- safety cap cho production
)
SELECT
  t.id,
  t.parent_id,
  t.body,
  u.name  AS author,
  t.depth,
  t.created_at
FROM thread t
LEFT JOIN users u ON u.id = t.user_id
ORDER BY t.depth, t.created_at;

Truy vấn này:

• Lấy đúng 1 thread (anchor lọc theo root id = $1).
• Kết hợp với users bên ngoài CTE — không cần JOIN users bên trong recursive part (tốn kém hơn).
• LEFT JOIN để không mất comment nếu user đã bị xoá.
• ORDER BY depth, created_at giữ thứ tự đọc tự nhiên.
• depth < 50 bảo vệ production khỏi data bất thường.

Render breadcrumb (đường dẫn từ comment lá lên root) dùng Demo 2 ở mục 4, thay $1 bằng id của comment lá cần trace.

10. Deep Dive

11. Tóm tắt

• WITH RECURSIVE = anchor + recursive part + implicit termination: anchor cung cấp dữ liệu ban đầu, recursive part mở rộng từ kết quả vòng trước, tự dừng khi recursive part trả 0 row.
• parent_id self-reference là pattern đơn giản nhất để lưu tree — recursive CTE là cách tự nhiên để traversal nó mà không cần schema thêm.
• Đi xuống (subtree): JOIN thread t ON c.parent_id = t.id. Đi lên (breadcrumb): JOIN breadcrumb b ON c.id = b.parent_id. Chỉ đổi chiều JOIN.
• Cycle prevention: path array (ARRAY[id] + NOT (id = ANY(path))) cho mọi version PG; CYCLE id SET is_cycle USING path cho PG 14+ gọn hơn.
• Safety cap bắt buộc trong production: WHERE t.depth < N phải nằm trong recursive part, không phải ở query ngoài — chỉ trong recursive part mới thực sự dừng CTE.
• UNION ALL không phải UNION: UNION dedup mỗi vòng, chi phí cao và có thể terminate sai. Luôn dùng UNION ALL trừ khi cố ý dedup.
• Hiệu năng: ổn với tree dưới 10–15 cấp. Tree sâu hơn hoặc query rất hot → cân nhắc ltree (GIST index) hoặc closure table. Graph workload nặng → graph DB hoặc PG extension age.

12. Tự kiểm tra

WITH RECURSIVE sub_projects AS (
SELECT id, parent_project_id, name, 0 AS depth
FROM projects WHERE id = 5
UNION ALL
SELECT p.id, p.parent_project_id, p.name, s.depth + 1
FROM projects p
JOIN sub_projects s ON p.parent_project_id = s.id
WHERE s.depth < 20
)
SELECT * FROM sub_projects ORDER BY depth, name;

Bài tiếp theo: Window functions nâng cao — frame clause, NTILE, và gap-and-island