Posted inDatabase

Recursive CTE trong SQL: Xử lý Dữ liệu Cây và Phân cấp trong PostgreSQL và MySQL

Database tutorial - IT technology blog
Database tutorial - IT technology blog

Vấn đề: Truy vấn Dữ liệu Tự Tham chiếu

Đến một lúc nào đó, mọi backend developer đều gặp phải dữ liệu phân cấp. Bảng nhân viên mà mỗi dòng có manager_id trỏ đến một nhân viên khác. Bảng danh mục mà mỗi danh mục có parent_id. Luồng bình luận với các reply lồng nhau. Cây thư mục. Danh sách nguyên vật liệu.

Sai lầm kinh điển — và bản thân tôi cũng từng mắc — là cố xử lý việc này ở tầng ứng dụng. Lấy root, lấy con của nó, lấy con của con, lặp lại cho đến hết. Cách đó vẫn chạy được. Nhưng nó tra tấn database với N+1 truy vấn và trở thành ác mộng bảo trì ngay khi cấu trúc phân cấp vượt quá ba tầng.

Đó là lúc recursive Common Table Expression (CTE) phát huy tác dụng. Pattern này chỉ mất khoảng một tiếng để quen. Sau đó, bạn sẽ nghĩ đến nó mỗi khi gặp bài toán tương tự.

Khái niệm Cốt lõi: Recursive CTE Hoạt động như thế nào

CTE thông thường là một subquery được đặt tên — cách viết SQL gọn hơn bằng cách đặt nhãn cho subquery để tham chiếu lại sau. Recursive CTE tiến xa hơn: nó cho phép truy vấn tham chiếu chính nó, mở rộng từng tầng một cho đến khi không còn gì để mở rộng nữa.

Mọi recursive CTE đều có ba phần:

  • Anchor member — truy vấn cơ sở trả về các dòng khởi đầu (node gốc)
  • Recursive member — truy vấn join ngược lại với chính CTE, thêm một tầng mỗi lần lặp
  • Điều kiện dừng — ngầm định: khi recursive member trả về không dòng nào, vòng lặp dừng lại

Cú pháp trông như sau:

WITH RECURSIVE cte_name AS (
    -- Anchor: điểm bắt đầu
    SELECT ...
    UNION ALL
    -- Recursive: join CTE với bảng nguồn
    SELECT ... FROM source_table JOIN cte_name ON ...
)
SELECT * FROM cte_name;

RECURSIVE là bắt buộc trong PostgreSQL. MySQL 8.0+ dùng cú pháp tương tự — hỗ trợ recursive CTE có từ MySQL 8.0, nên các phiên bản cũ hơn sẽ không chạy được.

Một Điều Cần Lưu ý

Dữ liệu bẩn có thể tạo ra vòng lặp: A là cha của B, B là cha của A. Recursive CTE sẽ lặp vô tận trong trường hợp đó. PostgreSQL cho phép thêm cột đếm độ sâu và giới hạn tường minh. MySQL có cte_max_recursion_depth (mặc định: 1000 lần lặp) như một lưới an toàn ở tầng hệ thống.

Thực hành

Tạo Cấu trúc Phân cấp Mẫu

Điểm khởi đầu kinh điển: bảng nhân viên tự tham chiếu qua manager_id. Schema này hoạt động giống nhau trong PostgreSQL và MySQL 8.0+.

CREATE TABLE employees (
    id       INT PRIMARY KEY,
    name     VARCHAR(100),
    role     VARCHAR(100),
    manager_id INT REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Alice',   'CEO',        NULL),
    (2, 'Bob',     'VP Eng',     1),
    (3, 'Carol',   'VP Sales',   1),
    (4, 'Dave',    'Lead Dev',   2),
    (5, 'Eve',     'Developer',  4),
    (6, 'Frank',   'Developer',  4),
    (7, 'Grace',   'Sales Rep',  3);

Truy vấn 1: Sơ đồ Tổ chức Đầy đủ, từ Trên xuống Dưới

Truy vấn này duyệt toàn bộ cây bắt đầu từ CEO và trả về mọi nhân viên kèm theo tầng độ sâu của họ:

WITH RECURSIVE org_chart AS (
    -- Anchor: node gốc (không có manager)
    SELECT
        id,
        name,
        role,
        manager_id,
        0 AS depth,
        name::TEXT AS path
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    -- Recursive: join từng nhân viên với manager của họ
    SELECT
        e.id,
        e.name,
        e.role,
        e.manager_id,
        oc.depth + 1,
        oc.path || ' > ' || e.name
    FROM employees e
    JOIN org_chart oc ON e.manager_id = oc.id
)
SELECT
    repeat('  ', depth) || name AS indented_name,
    role,
    depth,
    path
FROM org_chart
ORDER BY path;

Cột path tạo ra chuỗi breadcrumb dạng Alice > Bob > Dave > Eve. Hữu ích cho cả việc debug lẫn hiển thị — dán thẳng vào UI là xong.

Truy vấn 2: Tìm Tất cả Cấp dưới của Một Người Cụ thể

Giả sử bạn cần tất cả những người báo cáo cho Bob — trực tiếp hoặc gián tiếp — để áp dụng thay đổi quyền hoặc tính số đầu người trong nhóm.

WITH RECURSIVE subordinates AS (
    -- Anchor: bắt đầu từ Bob (id = 2)
    SELECT id, name, role, manager_id
    FROM employees
    WHERE id = 2

    UNION ALL

    SELECT e.id, e.name, e.role, e.manager_id
    FROM employees e
    JOIN subordinates s ON e.manager_id = s.id
)
SELECT * FROM subordinates;

Kết quả: Bob, Dave, Eve, Frank. Bốn dòng. Không cần vòng lặp ở tầng ứng dụng, không N+1.

Truy vấn 3: Đi Ngược Lên Cây (Tìm Chuỗi Quản lý)

Đôi khi bạn cần chiều ngược lại. Cho trước Eve, tìm toàn bộ chuỗi quản lý của cô ấy lên đến CEO — hữu ích cho kiểm tra phân quyền hoặc audit trail.

WITH RECURSIVE chain_of_command AS (
    -- Anchor: bắt đầu từ Eve (id = 5)
    SELECT id, name, role, manager_id
    FROM employees
    WHERE id = 5

    UNION ALL

    SELECT e.id, e.name, e.role, e.manager_id
    FROM employees e
    JOIN chain_of_command c ON e.id = c.manager_id
)
SELECT * FROM chain_of_command;

Trả về Eve → Dave → Bob → Alice. Lưu ý join đệ quy bị đảo ngược: thay vì khớp con (e.manager_id = oc.id), ta khớp cha (e.id = c.manager_id). Chỉ một sự đảo ngược đó là toàn bộ thủ thuật.

Mẹo Thực tế: Ngăn Vòng Lặp Vô hạn

Thêm bộ đếm độ sâu và giới hạn tường minh nếu dữ liệu của bạn có thể có vòng lặp:

WITH RECURSIVE safe_tree AS (
    SELECT id, name, manager_id, 0 AS depth
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    SELECT e.id, e.name, e.manager_id, st.depth + 1
    FROM employees e
    JOIN safe_tree st ON e.manager_id = st.id
    WHERE st.depth < 10  -- Giới hạn an toàn: dừng ở độ sâu 10
)
SELECT * FROM safe_tree;

Pattern Thực tế: Cây Danh mục

Cây danh mục thương mại điện tử liên tục gặp bài toán này. Bảng categories với parent_id có cấu trúc giống hệt ví dụ nhân viên. Lấy đường dẫn đầy đủ cho breadcrumb SEO chỉ mất khoảng hai phút với recursive CTE:

WITH RECURSIVE category_path AS (
    SELECT id, name, parent_id, name::TEXT AS full_path
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    SELECT c.id, c.name, c.parent_id,
           cp.full_path || ' / ' || c.name
    FROM categories c
    JOIN category_path cp ON c.parent_id = cp.id
)
SELECT id, full_path FROM category_path ORDER BY full_path;

Ghi chú về Chuẩn bị Dữ liệu

Khi tôi đang làm prototype các truy vấn này với dữ liệu mẫu từ file CSV xuất ra — chẳng hạn, danh mục xuất từ một nền tảng thương mại điện tử — tôi thường cần chuyển đổi CSV đó thành câu lệnh SQL INSERT hoặc JSON có cấu trúc trước khi nạp vào database test. Tôi dùng toolcraft.app/vi/tools/data/csv-to-json cho bước chuyển CSV sang JSON. Công cụ này chạy hoàn toàn trên trình duyệt, nên dữ liệu không rời khỏi máy bạn — rất tiện khi file xuất chứa dữ liệu khách hàng hoặc sản phẩm mà bạn không muốn gửi lên dịch vụ bên thứ ba.

Mẹo Tối ưu Hiệu năng

Recursive CTE có thể tốn kém trên các bảng lớn. Một số điều giúp ích trong thực tế:

  • Đánh index cột khóa ngoại. Trong ví dụ này, manager_id cần có index. PostgreSQL không tự động đánh index khóa ngoại — bạn phải thêm thủ công bằng CREATE INDEX. Với bảng hơn 100 nghìn dòng, chỉ riêng việc này có thể giảm thời gian truy vấn từ vài giây xuống còn vài mili giây.
  • Chỉ SELECT những gì cần thiết bên trong CTE. Recursive member chạy một lần mỗi tầng. Kéo vào các cột văn bản rộng mà bạn không dùng đồng nghĩa với việc đọc lại dữ liệu đó qua mỗi lần lặp. Chỉ SELECT tối thiểu bên trong CTE; join thêm cột ở truy vấn ngoài.
  • Dùng UNION ALL, không dùng UNION. UNION loại trùng lặp, thêm bước sort. Trừ khi bạn thực sự cần loại trùng lặp, luôn dùng UNION ALL bên trong recursive CTE.
  • Kiểm tra EXPLAIN ANALYZE. Query planner của PostgreSQL không phải lúc nào cũng tối ưu recursive CTE tích cực như các truy vấn thông thường. Chạy EXPLAIN ANALYZE trên toàn bộ câu lệnh — nó chỉ rõ thời gian đang tốn ở đâu.

Khi nào Nên Dùng — và Khi nào Không Nên

Recursive CTE phù hợp khi:

  • Độ sâu phân cấp chưa biết trước hoặc thay đổi theo từng dòng
  • Bạn cần toàn bộ cây hoặc phần lớn cây
  • Bạn muốn một lần round-trip đến database thay vì N+1 truy vấn

Phân cấp cố định độ sâu — luôn luôn đúng hai hoặc ba tầng theo thiết kế — thì dùng self-join thông thường đơn giản hơn. Recursive CTE tỏa sáng ngay khi độ sâu trở nên động.

Một lựa chọn thay thế đáng biết: extension ltree của PostgreSQL lưu trữ materialized path dưới dạng kiểu dữ liệu native với các toán tử chuyên biệt nhanh. Trên các cây rất sâu hoặc được truy vấn rất thường xuyên, ltree có thể vượt trội đáng kể so với recursive CTE. Đánh đổi là logic INSERT và UPDATE trở nên phức tạp hơn. Recursive CTE không cần thay đổi schema, điều đó khiến nó là điểm khởi đầu đúng đắn cho hầu hết mọi dự án — chỉ chuyển sang ltree khi bạn đã đo được vấn đề hiệu năng thực sự.

Tóm tắt Pattern

Anchor member, recursive member, điều kiện dừng. Chỉ vậy thôi. Pattern này cảm giác lạ lẫm lần đầu tiên bạn viết. Đến truy vấn thứ ba, nó đọc tự nhiên như thở.

Bốn thói quen cần xây dựng ngay: đánh index cột cha/khóa ngoại, dùng UNION ALL thay vì UNION, thêm giới hạn độ sâu với dữ liệu bạn không kiểm soát hoàn toàn, và chạy EXPLAIN ANALYZE khi hiệu năng là vấn đề. Với những thứ đó, bạn sẽ xử lý được hầu hết bài toán dữ liệu phân cấp trong một câu lệnh SQL duy nhất — không cần vòng lặp ở tầng ứng dụng.

Share:
Tags: