Đã đăng vào Thứ Hai, 11:25 CH 6 phút đọc

PostgreSQL Bài 20: DQL Nâng cao: Recursive CTE và Ứng dụng Xử lý Dữ liệu Cây (Tree/Graph structures)

(Lưu ý thuật ngữ: Kỹ thuật đệ quy WITH RECURSIVE thuộc nhóm DQL - Data Query Language, chuyên trị các bài toán truy vấn phân cấp phức tạp).

Trong thiết kế cơ sở dữ liệu quan hệ, một trong những thách thức lớn nhất là biểu diễn và truy vấn các cấu trúc dữ liệu dạng cây (Tree) hoặc đồ thị (Graph):

Danh mục sản phẩm lồng nhau vô hạn cấp (E-commerce Categories).
Cây sơ đồ tổ chức phòng ban và nhân sự (Manager - Subordinate).
Mạng xã hội hoặc mạng lưới bạn bè (Đồ thị kết nối).
Danh mục nguyên vật liệu sản xuất đa tầng (BOM - Bill of Materials).

Với các câu lệnh JOIN thông thường, bạn chỉ có thể duyệt cố định 1, 2 hoặc 3 tầng. Nếu cây có độ sâu không xác định ( $N$ tầng), SQL truyền thống hoàn toàn bất lực và buộc bạn phải gọi hàng chục request đệ quy từ backend (gây ra lỗi kinh điển N+1 queries).

PostgreSQL giải quyết bài toán này ở cấp độ cơ sở dữ liệu bằng Recursive CTE (WITH RECURSIVE).

1. Cơ chế thực thi của Recursive CTE

Cú pháp của một truy vấn đệ quy luôn gồm hai phần nối với nhau bởi toán tử UNION (hoặc UNION ALL):

SQL

WITH RECURSIVE cte_name AS (
    -- 1. ANCHOR MEMBER (Điểm neo ban đầu - không đệ quy)
    SELECT ...
    
    UNION ALL
    
    -- 2. RECURSIVE MEMBER (Phần đệ quy - tham chiếu lại chính cte_name)
    SELECT ... FROM cte_name JOIN ...
)
SELECT * FROM cte_name;

QUY TRÌNH THỰC THI NỘI BỘ (EVALUATION ALGORITHM):

Bước 1: Chạy Anchor Member
  └── Ghi kết quả vào [Working Table] và [Intermediate Result Table]

Bước 2: Vòng lặp đệ quy (Lặp lại cho đến khi Working Table RỖNG):
  ├── Chạy Recursive Member (lấy dữ liệu từ Working Table JOIN với bảng thực tế)
  ├── Kết quả mới sinh ra:
  │     ├── Thay thế nội dung của [Working Table] cho vòng lặp tiếp theo
  │     └── Bổ sung (Append) vào [Intermediate Result Table]
  └── Nếu không còn dòng nào sinh ra ──► DỪNG VÒNG LẶP

Bước 3: Trả về toàn bộ [Intermediate Result Table] cho câu lệnh ngoài cùng.

Lưu ý hiệu năng: Luôn ưu tiên dùng UNION ALL thay vì UNION. UNION sẽ thực hiện thêm bước loại bỏ các bản ghi trùng lặp (Duplicate Elimination / Sort Hash) ở mỗi vòng lặp, gây tiêu tốn CPU không cần thiết trừ khi cấu trúc dữ liệu của bạn có các nhánh lặp lại.

2. Dữ liệu thực hành: Cây sơ đồ tổ chức công ty

Tạo một bảng lưu trữ cấu trúc quản lý nhân sự với mô hình Adjacency List (danh sách kề: mỗi nhân viên trỏ tới một manager_id):

SQL

CREATE SCHEMA IF NOT EXISTS hierarchy_lab;

CREATE TABLE hierarchy_lab.employees (
    id INT PRIMARY KEY,
    name TEXT NOT NULL,
    title TEXT NOT NULL,
    manager_id INT REFERENCES hierarchy_lab.employees(id)
);

INSERT INTO hierarchy_lab.employees VALUES
(1,  'Nguyễn Tổng',    'CEO',                 NULL),
(2,  'Trần Giám Đốc',  'CTO',                 1),
(3,  'Lê Giám Đốc',    'CFO',                 1),
(4,  'Phạm Trưởng Tech','Lead Backend',       2),
(5,  'Hoàng Trưởng AI', 'Lead Data/AI',       2),
(6,  'Vũ Dev 1',       'Senior Go/Postgres',  4),
(7,  'Đặng Dev 2',     'Junior Backend',      4),
(8,  'Bùi Data Eng',   'Data Pipeline Dev',   5),
(9,  'Kế Toán Viên',   'Accountant',          3);

3. Duyệt cây từ trên xuống (Top-Down Search): Tìm toàn bộ cấp dưới

Bài toán: Tìm toàn bộ cấp dưới trực tiếp và gián tiếp của CTO (id = 2), kèm theo thông tin về Cấp độ (Depth Level) và Đường dẫn phân cấp (Breadcrumb Path).

SQL

WITH RECURSIVE employee_hierarchy AS (
    -- 1. ANCHOR: Điểm xuất phát là nhân viên có id = 2 (CTO)
    SELECT 
        id, 
        name, 
        title, 
        manager_id,
        1 AS depth_level,
        ARRAY[name] AS path_breadcrumb
    FROM hierarchy_lab.employees
    WHERE id = 2

    UNION ALL

    -- 2. RECURSIVE: Tìm nhân viên nào có manager_id nằm trong tập kết quả trước đó
    SELECT 
        e.id, 
        e.name, 
        e.title, 
        e.manager_id,
        h.depth_level + 1,
        h.path_breadcrumb || e.name
    FROM hierarchy_lab.employees e
    JOIN employee_hierarchy h ON e.manager_id = h.id
)
SELECT 
    depth_level,
    -- Thụt đầu dòng trực quan hóa cây thư mục
    repeat('   │', depth_level - 1) || '── ' || name AS visual_tree,
    title,
    array_to_string(path_breadcrumb, ' > ') AS reporting_line
FROM employee_hierarchy
ORDER BY path_breadcrumb;

Kết quả trả về:

Plaintext

 depth_level |       visual_tree       |       title        |                 reporting_line                 
-------------+-------------------------+--------------------+------------------------------------------------
           1 | ── Trần Giám Đốc        | CTO                | Trần Giám Đốc
           2 |    │── Hoàng Trưởng AI  | Lead Data/AI       | Trần Giám Đốc > Hoàng Trưởng AI
           3 |    │   │── Bùi Data Eng | Data Pipeline Dev  | Trần Giám Đốc > Hoàng Trưởng AI > Bùi Data Eng
           2 |    │── Phạm Trưởng Tech | Lead Backend       | Trần Giám Đốc > Phạm Trưởng Tech
           3 |    │   │── Đặng Dev 2   | Junior Backend     | Trần Giám Đốc > Phạm Trưởng Tech > Đặng Dev 2
           3 |    │   │── Vũ Dev 1     | Senior Go/Postgres | Trần Giám Đốc > Phạm Trưởng Tech > Vũ Dev 1

Điểm sáng giá: Chỉ với 1 câu query duy nhất, engine đã duyệt qua toàn bộ các nhánh con bất kể cây sâu bao nhiêu tầng, định dạng luôn visual thụt dòng và đường dẫn breadcrumb mà backend không tốn một dòng code xử lý nào.

4. Duyệt cây từ dưới lên (Bottom-Up Search): Tìm chuỗi phê duyệt

Bài toán: Khi một nhân viên cấp dưới (ví dụ: Vũ Dev 1, id = 6) nộp đơn xin nghỉ phép, hệ thống cần truy vết ngược lên toàn bộ các cấp quản lý trực tiếp chịu trách nhiệm phê duyệt đơn đó cho đến tận vị trí CEO.

SQL

WITH RECURSIVE approval_chain AS (
    -- 1. ANCHOR: Xuất phát từ chính nhân viên gửi yêu cầu
    SELECT 
        id, 
        name, 
        title, 
        manager_id,
        1 AS step
    FROM hierarchy_lab.employees
    WHERE id = 6

    UNION ALL

    -- 2. RECURSIVE: Tìm người quản lý của người hiện tại
    SELECT 
        mgr.id, 
        mgr.name, 
        mgr.title, 
        mgr.manager_id,
        ac.step + 1
    FROM hierarchy_lab.employees mgr
    JOIN approval_chain ac ON ac.manager_id = mgr.id
)
SELECT 
    step,
    name,
    title
FROM approval_chain
ORDER BY step;

Kết quả:

Plaintext

 step |       name       |      title       
------+------------------+------------------
    1 | Vũ Dev 1         | Senior Go/Postgres
    2 | Phạm Trưởng Tech | Lead Backend
    3 | Trần Giám Đốc    | CTO
    4 | Nguyễn Tổng      | CEO

5. Phòng chống Vòng lặp vô tận (Cycle Detection in Graph)

Trong cấu trúc cây chuẩn (Strict Tree), một node chỉ có 1 cha và không bao giờ có chu trình lặp. Tuy nhiên, trong mô hình đồ thị mạng lưới hoặc khi dữ liệu bị lỗi nghiệp vụ (ví dụ: A quản lý B, B quản lý C, nhưng C lại được chỉ định quản lý A), câu truy vấn Recursive CTE sẽ chạy vô tận cho đến khi cạn kiệt RAM hoặc tràn đĩa đệm.

PostgreSQL hỗ trợ 2 giải pháp để nhận diện và ngắt chu trình lặp:

Cách 1: Giải pháp mảng Path Tracking (Tương thích mọi phiên bản)

Sử dụng mảng id[] để ghi lại những node đã đi qua; nếu node hiện tại đã nằm trong mảng, lập tức ngắt đệ quy:

SQL

-- Giả sử vô tình tạo một vòng lặp: Nguyễn Tổng (id=1) lại báo cáo cho Vũ Dev (id=6)
UPDATE hierarchy_lab.employees SET manager_id = 6 WHERE id = 1;

WITH RECURSIVE graph_traverse AS (
    SELECT 
        id, 
        name, 
        manager_id,
        ARRAY[id] AS visited_nodes,
        FALSE AS is_cycle
    FROM hierarchy_lab.employees
    WHERE id = 1

    UNION ALL

    SELECT 
        e.id, 
        e.name, 
        e.manager_id,
        gt.visited_nodes || e.id,
        -- Kiểm tra xem ID mới đã từng xuất hiện trong mảng hay chưa:
        e.id = ANY(gt.visited_nodes)
    FROM hierarchy_lab.employees e
    JOIN graph_traverse gt ON e.manager_id = gt.id
    WHERE NOT gt.is_cycle -- DỪNG LẠI NGAY LẬP TỨC NẾU PHÁT HIỆN VÒNG LẶP!
)
SELECT id, name, manager_id, visited_nodes, is_cycle 
FROM graph_traverse;

Cách 2: Mệnh đề `CYCLE` chuẩn SQL (Tích hợp từ PostgreSQL 14+)

Từ PostgreSQL 14, chuẩn SQL đã cung cấp cú pháp CYCLE nguyên bản cực kỳ ngắn gọn mà không cần tự tạo mảng kiểm tra thủ công:

SQL

WITH RECURSIVE graph_traverse AS (
    SELECT id, name, manager_id
    FROM hierarchy_lab.employees
    WHERE id = 1

    UNION ALL

    SELECT e.id, e.name, e.manager_id
    FROM hierarchy_lab.employees e
    JOIN graph_traverse gt ON e.manager_id = gt.id
)
-- Khai báo phát hiện lặp trên cột id:
CYCLE id SET is_cycle USING path_trace
SELECT id, name, manager_id, path_trace, is_cycle 
FROM graph_traverse;

CYCLE id: Chỉ định cột cần giám sát tính duy nhất.
SET is_cycle: Tên cột boolean sẽ tự động bật TRUE khi chạm phải node đã duyệt qua.
USING path_trace: Tự động sinh mảng danh sách đường đi nội bộ.

6. Tổng kết Phần 3 & Chuẩn bị bước sang Phần 4

Chúng ta đã chính thức hoàn thành toàn bộ Phần 3: Kỹ thuật truy vấn từ cơ bản đến nâng cao (Bài 14 – 20):

Bài 14: Cơ chế 3 thuật toán JOIN vật lý: Nested Loop, Hash Join, Merge Join.
Bài 15: Subqueries và CTEs: Tối ưu với MATERIALIZED vs NOT MATERIALIZED.
Bài 16: Window Functions: ROW_NUMBER, RANK, DENSE_RANK, LEAD, LAG và Window Frames.
Bài 17: Tổng hợp đa chiều OLAP: GROUPING SETS, ROLLUP, CUBE.
Bài 18: Full-Text Search: tsvector, tsquery, weights và GIN Index.
Bài 19: Fuzzy search và tối ưu LIKE '%...%' với extension pg_trgm.
Bài 20: DQL nâng cao: Xử lý cây và đồ thị với Recursive CTE (WITH RECURSIVE).

Bước sang Phần 4: Indexing & Tối ưu hóa truy vấn chuyên sâu

Bài 21 xem tiếp: Cơ chế lưu trữ đĩa: Page, Tuple, Page Header và Fillfactor — chúng ta sẽ xuống thẳng tầng vật lý thấp nhất của PostgreSQL để giải mã: một block 8KB được chia như thế nào, cấu trúc 23-byte header của từng dòng (Tuple Header), hiện tượng phân mảnh trang và kỹ thuật tinh chỉnh fillfactor để tối ưu các bảng có tần suất UPDATE liên tục.

PostgreSQL