SQL Recursive CTE: Mô hình hóa và Truy vấn Dữ liệu Phân cấp cho Cây Danh mục và Phân quyền Vai trò

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

Khi JOIN Đơn giản Là Chưa Đủ

Bạn đang xây dựng một nền tảng thương mại điện tử. Danh mục sản phẩm trông như thế này:

Điện tử
  └── Điện thoại
        ├── Android
        └── iPhone
  └── Laptop
        └── Laptop Gaming

Phản xạ đầu tiên của bạn là dùng self-join. Bạn viết một JOIN cho cấp đầu, thêm một JOIN cho cấp hai — rồi nhận ra dữ liệu có thể sâu tới năm cấp. Bỗng nhiên bạn đang viết tám cái JOIN cho một truy vấn đáng lẽ chỉ cần ba dòng.

Đây là bài toán dữ liệu phân cấp kinh điển. Nó xuất hiện trong danh mục sản phẩm, sơ đồ tổ chức, hệ thống file, kế thừa phân quyền, luồng bình luận — bất cứ nơi nào cấu trúc lồng bên trong cấu trúc khác. SQL quan hệ truyền thống vốn không được thiết kế cho các cấu trúc đệ quy, nhưng các cơ sở dữ liệu hiện đại đã giải quyết vấn đề này gọn gàng với Recursive CTE.

Khái niệm Cơ bản

Mô hình Danh sách Liền kề

Cách phổ biến nhất để lưu trữ dữ liệu phân cấp là mô hình danh sách liền kề: mỗi hàng lưu một tham chiếu đến nút cha của nó. Đây là bảng categories sử dụng pattern này:

CREATE TABLE categories (
    id        INT PRIMARY KEY,
    name      VARCHAR(100) NOT NULL,
    parent_id INT REFERENCES categories(id)  -- NULL nghĩa là nút gốc
);

Dễ hiểu và dễ chèn các nút mới. Thách thức nằm ở việc đọc lại dữ liệu dưới dạng cây — đó là lúc phần đệ quy phát huy tác dụng.

Recursive CTE Là Gì?

CTE (Common Table Expression) là một subquery có tên mà bạn định nghĩa ở đầu câu SQL bằng từ khóa WITH. Recursive CTE là loại tự tham chiếu chính nó, cho phép truy vấn lặp từng cấp cho đến khi không còn gì để xử lý.

Cấu trúc luôn có hai phần được nối bằng UNION ALL:

  • Phần anchor: Điểm bắt đầu — trường hợp cơ sở (nút gốc, hoặc bất kỳ nút nào bạn muốn bắt đầu từ đó)
  • Phần recursive: Join ngược lại chính CTE, tiến sâu thêm một cấp mỗi lần lặp

Cơ sở dữ liệu tiếp tục chạy phần recursive cho đến khi không còn hàng mới nào được trả về. Không cần vòng lặp ở phía ứng dụng.

Thực Hành: Cây Danh mục

Bước 1: Chuẩn bị Dữ liệu

Hãy tạo một cây danh mục và chèn dữ liệu test. Tôi dùng cú pháp PostgreSQL — MySQL 8+ dùng cùng từ khóa WITH RECURSIVE; SQL Server cũng hỗ trợ recursive CTE nhưng bỏ hoàn toàn từ RECURSIVE:

INSERT INTO categories (id, name, parent_id) VALUES
    (1, 'Điện tử',       NULL),
    (2, 'Điện thoại',    1),
    (3, 'Laptop',        1),
    (4, 'Android',       2),
    (5, 'iPhone',        2),
    (6, 'Laptop Gaming', 3),
    (7, 'Samsung',       4),
    (8, 'Pixel',         4);

Bước 2: Lấy Tất cả Hậu duệ của một Nút

Giả sử bạn muốn lấy mọi danh mục thuộc “Điện tử” (id = 1). Đây là recursive CTE:

WITH RECURSIVE category_tree AS (
    -- Anchor: bắt đầu từ nút gốc
    SELECT id, name, parent_id, 0 AS depth
    FROM categories
    WHERE id = 1

    UNION ALL

    -- Recursive: join các nút con với tập kết quả hiện tại
    SELECT c.id, c.name, c.parent_id, ct.depth + 1
    FROM categories c
    INNER JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT id, name, depth
FROM category_tree
ORDER BY depth, name;

Kết quả:

 id | name             | depth
----+------------------+-------
  1 | Điện tử          |   0
  2 | Điện thoại       |   1
  3 | Laptop           |   1
  4 | Android          |   2
  5 | iPhone           |   2
  6 | Laptop Gaming    |   2
  7 | Pixel            |   3
  8 | Samsung          |   3

Cột depth được tính miễn phí — không tốn thêm chi phí gì và cho bạn biết chính xác mỗi nút nằm ở bao nhiêu cấp sâu.

Bước 3: Xây dựng Đường dẫn Breadcrumb Đầy đủ

Chuỗi breadcrumb như “Điện tử > Điện thoại > Android” là yêu cầu phổ biến. Điều chỉnh CTE để tích lũy đường dẫn dưới dạng chuỗi trong khi duyệt cây:

WITH RECURSIVE category_path AS (
    -- Anchor: nút gốc, đường dẫn bắt đầu chỉ với tên của chúng
    SELECT id, name, parent_id, name::TEXT AS path
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    -- Recursive: thêm tên nút con vào đường dẫn hiện có
    SELECT c.id, c.name, c.parent_id, cp.path || ' > ' || c.name
    FROM categories c
    INNER JOIN category_path cp ON c.parent_id = cp.id
)
SELECT id, name, path
FROM category_path
ORDER BY path;

Câu này tạo ra chuỗi breadcrumb gọn gàng cho mọi nút trong cây — không cần vòng lặp ở tầng ứng dụng, không cần thêm query.

Ứng dụng Thực tế: Phân quyền Vai trò Đa cấp

Kế thừa phân quyền là nơi khác mà pattern này tỏ ra hữu ích. Hãy xem xét một cấp bậc vai trò trong đó mỗi vai trò mở rộng từ một cơ sở đơn giản hơn:

Viewer        (cơ sở: có thể xem)
  └── Editor  (thêm: có thể chỉnh sửa)
        └── Manager  (thêm: có thể xuất bản)
              └── Admin  (thêm: xóa, quản lý người dùng)

Mỗi vai trò chỉ sở hữu những quyền riêng của mình. Một Manager khi đăng nhập cần tự động có được mọi thứ mà Editor và Viewer có thể làm. Bạn cần leo lên chuỗi kế thừa để thu thập tất cả những gì họ đã tích lũy.

Thiết lập Bảng Roles và Permissions

CREATE TABLE roles (
    id        INT PRIMARY KEY,
    name      VARCHAR(50) NOT NULL,
    parent_id INT REFERENCES roles(id)  -- trỏ đến vai trò cơ sở đơn giản hơn
);

CREATE TABLE role_permissions (
    role_id    INT REFERENCES roles(id),
    permission VARCHAR(100) NOT NULL
);

INSERT INTO roles VALUES
    (4, 'Viewer',  NULL),  -- vai trò cơ sở, không kế thừa gì
    (3, 'Editor',  4),     -- mở rộng từ Viewer
    (2, 'Manager', 3),     -- mở rộng từ Editor
    (1, 'Admin',   2);     -- mở rộng từ Manager, kế thừa tất cả

INSERT INTO role_permissions VALUES
    (1, 'delete_posts'),
    (1, 'manage_users'),
    (2, 'publish_posts'),
    (3, 'edit_posts'),
    (4, 'view_posts');

Truy vấn Tất cả Quyền Kế thừa

Để lấy mọi quyền mà Manager (id = 2) có — bao gồm cả những quyền kế thừa từ Editor và Viewer — leo lên chuỗi để tìm tất cả vai trò tổ tiên, rồi join với bảng permissions:

WITH RECURSIVE role_ancestors AS (
    -- Anchor: bắt đầu với vai trò mục tiêu
    SELECT id, name, parent_id
    FROM roles
    WHERE id = 2  -- Manager

    UNION ALL

    -- Recursive: leo LÊN đến vai trò cơ sở
    SELECT r.id, r.name, r.parent_id
    FROM roles r
    INNER JOIN role_ancestors ra ON r.id = ra.parent_id
)
SELECT DISTINCT rp.permission
FROM role_ancestors ra
JOIN role_permissions rp ON rp.role_id = ra.id
ORDER BY rp.permission;

Kết quả:

permission
-----------
edit_posts
publish_posts
view_posts

Truy vấn bắt đầu từ Manager, leo lên Editor (parent_id = 3), rồi Viewer (parent_id = NULL) — thu thập quyền của từng vai trò dọc đường. Điểm khác biệt duy nhất về cấu trúc so với truy vấn cây danh mục là hướng join: r.id = ra.parent_id thay vì c.parent_id = ct.id. Chỉ một sự thay đổi đó đã lật hướng duyệt từ tìm nút con sang tìm nút tổ tiên. Mọi thứ còn lại hoàn toàn giống nhau.

Mẹo Thực tế và Những Điểm Cần Lưu ý

Luôn Đánh Index cho parent_id

Nếu không có index trên parent_id, mỗi bước đệ quy sẽ phải quét toàn bộ bảng. Với vài nghìn hàng thì ổn; với hàng trăm nghìn hàng thì sẽ rất chậm:

CREATE INDEX idx_categories_parent ON categories(parent_id);
CREATE INDEX idx_roles_parent ON roles(parent_id);

Bảo vệ Khỏi Vòng lặp Vô hạn

Tham chiếu vòng tròn vô tình — một nút mà chuỗi cha của nó cuối cùng lại trỏ về chính nó — sẽ khiến recursive CTE chạy mãi cho đến khi cơ sở dữ liệu chạm giới hạn đệ quy. Thêm giới hạn độ sâu như một lưới an toàn:

WITH RECURSIVE category_tree AS (
    SELECT id, name, parent_id, 0 AS depth
    FROM categories WHERE id = 1

    UNION ALL

    SELECT c.id, c.name, c.parent_id, ct.depth + 1
    FROM categories c
    INNER JOIN category_tree ct ON c.parent_id = ct.id
    WHERE ct.depth < 20  -- dừng sau 20 cấp
)
SELECT * FROM category_tree;

PostgreSQL 14+ cũng có mệnh đề CYCLE tích hợp sẵn để phát hiện vòng tròn đúng cách mà không cần thủ thuật depth thủ công.

Nhập Dữ liệu Test từ Bảng tính

Khi thiết lập cấu trúc phân cấp để test, tôi thường bắt đầu từ bảng tính xuất ra CSV. Khi cần chuyển nhanh CSV sang JSON để nhập dữ liệu, tôi dùng toolcraft.app/vi/tools/data/csv-to-json — 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. Nhanh hơn nhiều so với việc viết script chuyển đổi một lần rồi thôi.

Nâng Cao Hơn

Recursive CTE được tạo ra cho những truy vấn mà nếu không có nó sẽ đòi hỏi nhiều lần gọi đến cơ sở dữ liệu hoặc phải triển khai logic cây trong code ứng dụng. Cấu trúc luôn nhất quán: một anchor chọn nút bắt đầu, một phần recursive tiến từng cấp một — đi xuống để lấy hậu duệ, hoặc đi lên để thu thập tổ tiên.

Hai ví dụ ở đây bao phủ cả hai hướng. Duyệt cây danh mục đi xuống; kế thừa phân quyền leo lên. Khi pattern cốt lõi đó đã nằm trong bộ công cụ của bạn, hầu hết các bài toán phân cấp sẽ rút gọn thành “tôi cần duyệt theo hướng nào?”

Khi hiệu suất đọc cần mở rộng hơn nữa, pattern Closure Table đáng để tìm hiểu. Nó pre-materialize mọi cặp tổ tiên-hậu duệ vào một bảng riêng, đánh đổi chi phí ghi lấy khả năng đọc cấu trúc phân cấp O(1) — xứng đáng khi cây của bạn đạt hàng chục nghìn nút và tải truy vấn cao.

Share: