1.1 Mục tiêu — code dễ đọc và mở khóa lớp bài mới

Sau tuần 6 bạn đã có vũ khí mạnh nhất (window function). Tuần này có hai mục tiêu khác hẳn:

1. CTE — không thêm khả năng mới, chỉ làm code đẹp và đọc được. Sẽ thấy LC 1321 từ tuần 6 ngắn lại 30%.
2. Recursive CTE — mở khóa lớp bài hierarchy (cây tổ chức), path finding, sinh chuỗi, gaps and islands.

Sau tuần 7 bạn cần làm được

• Refactor mọi query phức tạp thành chuỗi CTE rõ ràng — viết và đọc đều dễ hơn nhiều.
• Viết recursive CTE cho hierarchy traversal (manager — direct report — report của report).
• Sinh chuỗi số/ngày on-the-fly bằng recursive CTE.
• Áp dụng pattern gaps and islands cho bài "chuỗi đăng nhập liên tiếp", "khoảng giá ổn định".

1.2 CTE = derived table có tên

CTE (Common Table Expression) là cú pháp WITH ... AS (...) đặt ở đầu query. Mỗi CTE giống một bảng tạm chỉ tồn tại trong query đó.

SELECT t.dept, t.avg_sal
FROM (
    SELECT dept, AVG(salary) AS avg_sal
    FROM employees
    GROUP BY dept
) t
WHERE t.avg_sal > 80000;

WITH dept_avg AS (
    SELECT dept, AVG(salary) AS avg_sal
    FROM employees
    GROUP BY dept
)
SELECT dept, avg_sal
FROM dept_avg
WHERE avg_sal > 80000;

Cùng kết quả. CTE thắng ở:

• Đặt tên có nghĩa (dept_avg tốt hơn t).
• Đọc top-down — định nghĩa trước, dùng sau, giống đọc paragraph.
• Tái sử dụng — một CTE có thể được dùng nhiều lần trong query chính.
• Recursive — derived table không làm được.

2.1 Cú pháp WITH

WITH cte_name [(col1, col2, ...)] AS (
    SELECT ...
)
SELECT ... FROM cte_name ...;

Cột phần [(col1, col2, ...)] tùy chọn — nếu không khai báo, dùng tên cột từ SELECT bên trong.

WITH top_customers (id, total_spent) AS (
    SELECT customer_id, SUM(total)
    FROM orders
    GROUP BY customer_id
    ORDER BY 2 DESC
    LIMIT 10
)
SELECT c.name, tc.total_spent
FROM top_customers tc
JOIN customers c ON c.customer_id = tc.id;

2.2 CTE vs subquery vs derived table

2.3 Multiple CTEs — chuỗi nhiều bước

CTE thứ hai có thể tham chiếu CTE thứ nhất. Đây là điểm mạnh chính.

WITH
    daily_revenue AS (
        SELECT order_date, SUM(total) AS revenue
        FROM orders GROUP BY order_date
    ),
    revenue_with_avg AS (
        SELECT
            order_date,
            revenue,
            AVG(revenue) OVER (
                ORDER BY order_date
                ROWS BETWEEN 6 PRECEDING AND CURRENT ROW
            ) AS ma_7d
        FROM daily_revenue
    ),
    flagged AS (
        SELECT *,
               CASE WHEN revenue > ma_7d * 1.5 THEN 'spike' END AS flag
        FROM revenue_with_avg
    )
SELECT * FROM flagged WHERE flag = 'spike';

Đọc từ trên xuống: mỗi CTE là một bước biến đổi rõ ràng. Cùng yêu cầu viết bằng nested subquery sẽ là 3 tầng SELECT lồng nhau — đọc ngược, debug khó.

2.4 Refactor — LC 1321 với CTE

Lấy bài Restaurant Growth (Hard) tuần 6, viết lại với CTE.

Tuần 6 — 2 tầng subquery

SELECT visited_on, amount, ROUND(amount/7.0, 2) AS average_amount
FROM (
    SELECT
        visited_on,
        SUM(daily) OVER (ORDER BY visited_on
                         ROWS BETWEEN 6 PRECEDING AND CURRENT ROW) AS amount,
        ROW_NUMBER() OVER (ORDER BY visited_on) AS rn
    FROM (
        SELECT visited_on, SUM(amount) AS daily
        FROM Customer GROUP BY visited_on
    ) daily_t
) t
WHERE rn >= 7
ORDER BY visited_on;

Tuần 7 — CTE

WITH
    daily_total AS (
        SELECT visited_on, SUM(amount) AS daily
        FROM Customer
        GROUP BY visited_on
    ),
    moving AS (
        SELECT
            visited_on,
            SUM(daily) OVER (ORDER BY visited_on
                             ROWS BETWEEN 6 PRECEDING AND CURRENT ROW) AS amount,
            ROW_NUMBER() OVER (ORDER BY visited_on) AS rn
        FROM daily_total
    )
SELECT visited_on, amount, ROUND(amount/7.0, 2) AS average_amount
FROM moving
WHERE rn >= 7
ORDER BY visited_on;

Cùng số dòng, nhưng tinh thần khác: hai bước có tên rõ ràng — "tổng theo ngày" rồi "moving sum". Code đọc tự nhiên top-down.

3.1 Pattern: chia bài lớn thành các CTE bước

Đây là kỹ năng tư duy quan trọng nhất cho mock interview SQL ở level Medium/Hard. Quy trình 4 bước:

1. Đọc đề — xác định bảng input, output mong muốn.
2. Phân rã — đặt tên cho mỗi bước biến đổi (động từ + đối tượng):
   • "Lọc đơn paid" → CTE paid_orders
   • "Tổng theo customer" → CTE customer_totals
   • "Rank theo region" → CTE ranked_customers
3. Viết stub — khung WITH với từng CTE rỗng, ghi comment yêu cầu mỗi CTE.
4. Điền chi tiết — từng CTE một, test nhỏ trước khi viết CTE tiếp.

3.2 Worked example — 4 bước CTE

Yêu cầu: với mỗi quốc gia, tìm 3 customer có tổng chi tiêu cao nhất (đã chi trả) và % của họ trên tổng chi tiêu quốc gia.

Phân rã

1. Lọc đơn paid → paid_orders
2. Tổng chi tiêu mỗi customer → customer_spend (kèm country)
3. Rank trong country + tổng country → ranked
4. Lọc top 3 và tính % → output

WITH
    paid_orders AS (
        SELECT customer_id, total
        FROM orders
        WHERE status = 'paid'
    ),
    customer_spend AS (
        SELECT
            c.country,
            c.customer_id,
            c.name,
            SUM(po.total) AS spent
        FROM customers c
        JOIN paid_orders po ON po.customer_id = c.customer_id
        GROUP BY c.country, c.customer_id, c.name
    ),
    ranked AS (
        SELECT *,
               ROW_NUMBER() OVER (PARTITION BY country ORDER BY spent DESC) AS rk,
               SUM(spent)  OVER (PARTITION BY country)                       AS country_total
        FROM customer_spend
    )
SELECT
    country, name, spent,
    ROUND(100.0 * spent / country_total, 2) AS pct_of_country
FROM ranked
WHERE rk <= 3
ORDER BY country, rk;

Mỗi CTE có thể test riêng — chạy SELECT * FROM customer_spend để debug giữa chừng.

3.3 Quy tắc sạch khi viết CTE

1. Đặt tên động từ + đối tượng. filtered_orders, customer_spend, top_3_per_dept. Tránh t1, t2, x, q.
2. Một CTE = một mục đích. Đừng dồn 3 phép biến đổi vào 1 CTE để "ngắn lại" — chia ra.
3. Comment khi cần. Một dòng -- gộp các đơn paid theo customer trên đầu CTE giúp người đọc.
4. Không lạm dụng. Query đơn giản 5 dòng không cần CTE — đọc thẳng dễ hơn.
5. CTE cho debug. Khi bug, comment câu chính, viết SELECT * FROM cte_name để inspect output trung gian.

4.1 Cấu trúc — Anchor + Recursive

WITH RECURSIVE cte_name AS (
    -- Anchor: dòng khởi đầu
    SELECT ...
    
    UNION ALL
    
    -- Recursive: từ output trước, sinh dòng mới
    SELECT ...
    FROM cte_name JOIN ... 
    WHERE ...    -- điều kiện dừng (rất quan trọng!)
)
SELECT * FROM cte_name;

Engine xử lý

1. Chạy anchor → tập kết quả \(R_0\).
2. Chạy recursive với \(R_0\) → \(R_1\) (dòng mới).
3. Lặp với \(R_1\) → \(R_2\), v.v.
4. Dừng khi recursive query trả 0 dòng.
5. Output cuối = \(R_0 \cup R_1 \cup R_2 \cup \ldots\).

Lưu ý phương ngữ: PostgreSQL/MySQL/SQLite cần keyword RECURSIVE. SQL Server không cần (nhưng vẫn hoạt động nếu thêm).

4.2 Sinh chuỗi số / ngày

Một use case đơn giản nhất — sinh chuỗi mà không cần bảng có sẵn.

-- Sinh số 1..10
WITH RECURSIVE seq AS (
    SELECT 1 AS n              -- anchor: bắt đầu từ 1
    UNION ALL
    SELECT n + 1 FROM seq      -- recursive: thêm 1
    WHERE n < 10               -- dừng khi đạt 10
)
SELECT * FROM seq;

-- Sinh chuỗi ngày trong năm 2024
WITH RECURSIVE dates AS (
    SELECT DATE '2024-01-01' AS d
    UNION ALL
    SELECT d + INTERVAL 1 DAY FROM dates
    WHERE d < '2024-12-31'
)
SELECT * FROM dates;

WITH RECURSIVE dates AS (...)
SELECT d.d, COALESCE(SUM(o.total), 0) AS revenue
FROM dates d
LEFT JOIN orders o ON o.order_date = d.d
GROUP BY d.d ORDER BY d.d;

PostgreSQL có hàm tắt generate_series('2024-01-01'::date, '2024-12-31', '1 day') — đẹp hơn. MySQL không có, phải recursive CTE.

4.3 Hierarchy traversal — cây tổ chức

Yêu cầu: tất cả nhân viên trực tiếp/gián tiếp report cho manager 5 (LC 1270 dạng tổng quát)

WITH RECURSIVE subordinates AS (
    -- Anchor: nhân viên trực tiếp report manager 5
    SELECT id, name, manager_id, 1 AS level
    FROM Employee
    WHERE manager_id = 5
    
    UNION ALL
    
    -- Recursive: nhân viên report cho người đã trong subordinates
    SELECT e.id, e.name, e.manager_id, s.level + 1
    FROM Employee e
    JOIN subordinates s ON e.manager_id = s.id
)
SELECT * FROM subordinates ORDER BY level, id;

Recursive CTE leo xuống từng tầng cho đến khi không còn nhân viên report cho ai trong tập hiện tại.

4.4 Path tracking và termination safety

Track path đi qua

Có thể tích lũy đường đi như chuỗi:

WITH RECURSIVE org_path AS (
    SELECT id, name, manager_id, CAST(name AS CHAR(500)) AS path
    FROM Employee WHERE manager_id IS NULL  -- CEO
    UNION ALL
    SELECT e.id, e.name, e.manager_id,
           CONCAT(p.path, ' > ', e.name)
    FROM Employee e
    JOIN org_path p ON e.manager_id = p.id
)
SELECT * FROM org_path;

Output: "CEO > VP Eng > Director > Manager > IC".

-- Track visited bằng path string
WHERE NOT FIND_IN_SET(e.id, p.path)  -- MySQL
WHERE p.path NOT LIKE '%' || e.id || '%'  -- PostgreSQL

5.1 Pattern gaps and islands — định nghĩa

Yêu cầu interview thường là: "tìm island dài nhất" hoặc "đếm số island" hoặc "list start/end của mỗi island".

5.2 Trick ROW_NUMBER — chìa khóa vàng

Pattern đẹp nhất cho gaps and islands sử dụng tính chất:

Nếu các dòng liên tiếp (theo date) có ROW_NUMBER liên tiếp (1, 2, 3, ...), thì date − ROW_NUMBER là hằng số trên cùng một island.

Cột diff hoạt động như "island ID" — group theo cột này để aggregate mỗi island.

WITH islands AS (
    SELECT
        user_id, login_date,
        DATE_SUB(login_date, INTERVAL ROW_NUMBER() OVER (
            PARTITION BY user_id ORDER BY login_date
        ) DAY) AS island_id
    FROM logins
)
SELECT user_id,
       MIN(login_date) AS start_date,
       MAX(login_date) AS end_date,
       COUNT(*)        AS streak_length
FROM islands
GROUP BY user_id, island_id
ORDER BY user_id, start_date;

5.3 Variant — gaps and islands trên giá trị

Pattern tổng quát hơn: tìm chuỗi liên tiếp dòng có cùng "trạng thái".

Trick: 2 ROW_NUMBER trừ nhau

WITH numbered AS (
    SELECT
        time, status,
        ROW_NUMBER() OVER (ORDER BY time) AS rn_all,
        ROW_NUMBER() OVER (PARTITION BY status ORDER BY time) AS rn_status
    FROM server_status
)
SELECT
    status,
    MIN(time) AS island_start,
    MAX(time) AS island_end,
    COUNT(*) AS duration
FROM numbered
GROUP BY status, rn_all - rn_status
HAVING status = 'up'
ORDER BY island_start;

6.1 LeetCode 180 — Consecutive Numbers (Medium)

Schema

Yêu cầu

Tìm các số xuất hiện ít nhất 3 lần liên tiếp (theo id tăng dần).

Cách 1 — LAG (gọn nhất)

WITH window_3 AS (
    SELECT
        num,
        LAG(num, 1) OVER (ORDER BY id) AS prev1,
        LAG(num, 2) OVER (ORDER BY id) AS prev2
    FROM Logs
)
SELECT DISTINCT num AS ConsecutiveNums
FROM window_3
WHERE num = prev1 AND num = prev2;

Cách 2 — gaps and islands

WITH islands AS (
    SELECT num,
           id - ROW_NUMBER() OVER (PARTITION BY num ORDER BY id) AS island
    FROM Logs
)
SELECT DISTINCT num AS ConsecutiveNums
FROM islands
GROUP BY num, island
HAVING COUNT(*) >= 3;

Cách 2 tổng quát hơn — đổi 3 thành 5 chỉ là sửa HAVING. Cách 1 phải thêm LAG(num, 3), LAG(num, 4)...

6.2 LeetCode 1270 — All People Report to Given Manager (Medium)

Schema

Yêu cầu

Tìm tất cả nhân viên report (trực tiếp/gián tiếp) cho manager employee_id = 1, với độ sâu tối đa 3 cấp.

Lời giải — recursive CTE

WITH RECURSIVE subordinates AS (
    -- Anchor: nhân viên trực tiếp report cho 1 (loại trừ chính 1)
    SELECT employee_id, manager_id, 1 AS depth
    FROM Employees
    WHERE manager_id = 1 AND employee_id <> 1
    
    UNION ALL
    
    -- Recursive: từ subordinates, leo xuống tầng tiếp
    SELECT e.employee_id, e.manager_id, s.depth + 1
    FROM Employees e
    JOIN subordinates s ON e.manager_id = s.employee_id
    WHERE s.depth < 3   -- giới hạn tối đa 3 cấp
)
SELECT employee_id FROM subordinates;

6.3 LeetCode 601 — Human Traffic of Stadium (Hard)

Schema

Yêu cầu

Tìm các dòng có ít nhất 3 ngày liên tiếp với people ≥ 100. Trả tất cả các dòng trong các chuỗi đó.

Phân rã

1. Lọc chỉ ngày có ≥ 100 → popular.
2. Trên popular, tính island theo trick id − ROW_NUMBER → tagged.
3. Đếm size mỗi island, giữ island ≥ 3 → output.

Lời giải

WITH
    popular AS (
        SELECT * FROM Stadium WHERE people >= 100
    ),
    tagged AS (
        SELECT *,
               id - ROW_NUMBER() OVER (ORDER BY id) AS island
        FROM popular
    ),
    big_islands AS (
        SELECT island
        FROM tagged
        GROUP BY island
        HAVING COUNT(*) >= 3
    )
SELECT id, visit_date, people
FROM tagged
WHERE island IN (SELECT island FROM big_islands)
ORDER BY visit_date;

Bài Hard trong 15 dòng nhờ kết hợp CTE multi-step + trick gaps and islands. Không có CTE, code lồng 3 tầng subquery — gần như không debug được.

Knowledge Check — Tuần 7

8.1 Bài tập LeetCode (5 problem)

1. 180. Consecutive Numbers (Medium) — đã giải tại lớp; viết cả hai cách (LAG và gaps-islands), so sánh.
2. 1270. All People Report to the Given Manager (Medium) — đã giải tại lớp.
3. 601. Human Traffic of Stadium (Hard) — đã giải tại lớp.
4. 1454. Active Users (Medium) — gaps and islands variant: tìm user có ≥ 5 ngày login liên tiếp.
5. 262. Trips and Users (Hard) — JOIN + filter phức tạp; viết bằng CTE multi-step (3-4 CTE).

Bonus — recursive challenge

Cho schema cây tổ chức Employee(id, name, manager_id):

1. Liệt kê toàn bộ subtree dưới một manager bất kỳ kèm depth (đã làm).
2. Mở rộng: tính path từ CEO đến mỗi nhân viên dưới dạng "CEO > VP > Director > Manager".
3. Mở rộng: với mỗi nhân viên, đếm số subordinates (trực tiếp + gián tiếp).

Đây là bài tập nền cho graph traversal trong system design interview — không chỉ SQL.

8.2 Đọc thêm và tự kiểm tra

Đọc

• SQL Cookbook (Anthony Molinaro) — Chương 9 (Date Arithmetic) phần "Gaps in Series".
• PostgreSQL docs — 7.8 WITH Queries (Common Table Expressions): tutorial chính thức.
• Markus Winand — modern-sql.com/feature/with phần CTE và recursive.
• Itzik Ben-Gan — T-SQL Querying, chương 5 về CTE và recursive (concept áp dụng đa dialect).

Tự kiểm tra (không nhìn slide)

• Bạn refactor được query 3-tầng-subquery thành chuỗi CTE trong 5 phút?
• Bạn nhớ cấu trúc anchor + recursive với UNION ALL?
• Bạn giải thích được vì sao date − ROW_NUMBER tạo island ID?
• Bạn nói được khi nào CTE là chọn lựa đúng vs khi nào nên viết thẳng subquery?
• Bạn nhớ điều kiện dừng và phòng infinite loop trong recursive?