Từ SQL đến kế hoạch thực thi — declarative, planner và access path

TL;DR: SQL là ngôn ngữ declarative (khai báo) — bạn mô tả kết quả mong muốn, không mô tả cách lấy. Cùng một câu SELECT, database có hàng chục cách thực thi khác nhau, và bộ phận query optimizer (planner) chọn một cách rồi giao cho executor chạy. Quá trình đó là một pipeline: parse (phân tích cú pháp) → rewrite (viết lại logic) → plan/optimize (chọn kế hoạch rẻ nhất) → execute (chạy). Kết quả của bước plan là một cây toán tử (operator tree) gồm các phép scan, join, sort, aggregate. Một quyết định cốt lõi trong cây đó là access path — đọc dữ liệu bằng full table scan hay index scan — chọn theo độ chọn lọc (selectivity) của điều kiện lọc. Mọi RDBMS đều theo nguyên lý này dù tên gọi và output khác nhau.

Một dev viết SELECT * FROM tasks WHERE assignee_id = 7 và thấy nó chạy 5ms. Cũng câu đó, đổi điều kiện thành WHERE assignee_id > 0 (gần như khớp mọi dòng), lại chạy 900ms. Cú pháp gần như y hệt — nhưng database thực thi hai cách hoàn toàn khác: câu đầu nhảy thẳng vào index lấy vài dòng, câu sau quét cả bảng vì lọc gần hết. Dev không hề ra lệnh "dùng index" hay "quét bảng" — database tự quyết.

Điểm mấu chốt: bạn không lập trình cách lấy dữ liệu. Bạn khai báo cái cần lấy, và một engine bên trong dịch nó thành các bước cụ thể. Bài này mở nắp engine đó: vì sao SQL là declarative, pipeline biến câu lệnh thành kế hoạch, hình dạng cây toán tử, và quyết định access path đầu tiên — tất cả ở mức nguyên lý dùng được cho mọi database.

1. Analogy — Đặt món ở nhà hàng, không vào bếp nấu

Khi bạn gọi "cho tôi một phần cơm gà", bạn nói kết quả mong muốn, không chỉ đạo bếp từng bước: vo gạo trước hay luộc gà trước, dùng nồi nào, lửa to hay nhỏ. Người bếp trưởng (chef) tự lên quy trình nấu dựa trên nguyên liệu sẵn có, số đầu bếp rảnh, và bếp nào đang trống — rồi giao cho phụ bếp thực hiện.

SQL hoạt động y hệt. Bạn khai báo món (SELECT ... WHERE ...), database đóng vai bếp trưởng: nhìn vào dữ liệu sẵn có (bảng, index, thống kê), lập một kế hoạch thực thi rẻ nhất, rồi giao cho executor chạy. Hai khách gọi cùng món vào hai thời điểm khác nhau có thể được nấu theo hai quy trình khác — vì nguyên liệu và bếp thay đổi. Database cũng vậy: cùng câu SQL, plan có thể đổi khi dữ liệu lớn lên hoặc index mới được thêm.

2. Declarative vs imperative — vì sao SQL không nói "cách làm"

Hầu hết ngôn ngữ lập trình bạn quen là imperative (mệnh lệnh): bạn viết từng bước — mở file, lặp qua từng dòng, so sánh, gom kết quả. Bạn kiểm soát thuật toán.

SQL thì declarative: bạn mô tả quan hệ kết quả mong muốn, để database tự chọn thuật toán.

-- Declarative: chi mo ta KET QUA mong muon
SELECT u.name, COUNT(t.id) AS open_tasks
FROM users u
JOIN tasks t ON t.assignee_id = u.id
WHERE t.status = 'open'
GROUP BY u.name;

Câu trên không nói: "lặp qua bảng users, với mỗi user tìm task của họ, đếm cái nào status open". Nó chỉ mô tả cái cần. Database tự do chọn: quét tasks trước rồi nhóm theo user, hay quét users trước rồi với mỗi user tra index tasks; dùng nested loop hay hash để join. Tất cả đều cho cùng kết quả — chỉ khác tốc độ.

Vì sao thiết kế declarative? Ba lý do nền tảng:

• Database biết dữ liệu, bạn không. Optimizer có thống kê (bảng bao nhiêu dòng, một cột có bao nhiêu giá trị riêng biệt) để chọn cách rẻ nhất. Một dev viết imperative không thể đoán đúng điều này cho mọi dữ liệu.
• Plan tự thích nghi. Hôm nay bảng 1000 dòng, plan này tốt; năm sau 10 triệu dòng, optimizer tự đổi plan — bạn không phải viết lại query.
• Tách logic khỏi thực thi. Bạn diễn đạt ý định một lần; cùng câu chạy tối ưu trên engine khác nhau, phần cứng khác nhau.

3. Pipeline — từ chuỗi SQL đến kế hoạch chạy được

Câu SQL bạn gửi đi là một chuỗi ký tự. Database biến nó thành các bước thực thi qua một pipeline bốn giai đoạn. Tên cụ thể khác nhau giữa các engine, nhưng nguyên lý đồng nhất:

flowchart LR
  SQL["Cau SQL<br/>(chuoi ky tu)"] --> P["1. PARSE<br/>cu phap -> cay"]
  P --> R["2. REWRITE<br/>viet lai logic"]
  R --> O["3. PLAN / OPTIMIZE<br/>chon ke hoach re nhat"]
  O --> E["4. EXECUTE<br/>chay plan, tra ket qua"]
  E --> RES["Ket qua"]

Giai đoạn 1 — Parse (phân tích cú pháp). Database kiểm tra câu lệnh đúng ngữ pháp SQL không, các bảng/cột có tồn tại không, kiểu dữ liệu hợp lệ không. Kết quả là một cây cú pháp (parse tree) biểu diễn cấu trúc câu lệnh. Sai chính tả SLECT hay tham chiếu cột không tồn tại bị bắt ngay ở đây.

Giai đoạn 2 — Rewrite (viết lại). Database biến đổi câu lệnh thành dạng tương đương nhưng dễ tối ưu hơn — không đổi kết quả. Ví dụ: thay view bằng định nghĩa của nó, đẩy điều kiện lọc xuống gần nguồn dữ liệu (predicate pushdown), đơn giản hoá biểu thức hằng. Đây là biến đổi logic, chưa quyết định thuật toán.

Giai đoạn 3 — Plan / Optimize (lập kế hoạch). Đây là trái tim. Optimizer sinh ra nhiều plan tương đương về mặt logic — khác nhau ở access path (đọc bảng kiểu gì), join algorithm (ghép bảng kiểu gì), thứ tự join — rồi ước lượng chi phí từng plan và chọn cái rẻ nhất. Cách ước lượng chi phí dựa trên cost model + statistics, mổ kỹ ở bài 03.

Giai đoạn 4 — Execute (thực thi). Executor chạy plan đã chọn: đọc dữ liệu theo access path, áp các toán tử (join, sort, aggregate) theo đúng cây, trả kết quả về client.

4. Query plan là một cây toán tử

Kết quả của giai đoạn plan là một cây toán tử (operator tree). Mỗi node là một phép xử lý cơ bản; dữ liệu chảy từ lá lên gốc. Lá là các phép đọc dữ liệu (scan); các node trên ghép, lọc, sắp xếp, tổng hợp; gốc trả kết quả cuối.

Hình dung plan cho câu join + group ở section 2:

                 [Aggregate: COUNT, GROUP BY u.name]   <- goc: tong hop
                              |
                      [Join: t.assignee_id = u.id]     <- ghep hai nguon
                       /                      \
        [Scan users u]            [Scan tasks t WHERE status='open']
        (doc bang users)          (doc tasks, loc status)
              ^                              ^
              la                             la (access path quyet dinh o day)

Mỗi toán tử nhận đầu vào từ node con và sinh đầu ra cho node cha — giống các trạm trong dây chuyền. Các toán tử phổ biến:

Cùng một câu SQL, optimizer có thể dựng nhiều cây khác nhau cho cùng kết quả: đổi thứ tự hai nhánh join, đổi scan từ full sang index, chèn/bỏ node sort. Mỗi cây là một plan ứng viên; optimizer chấm chi phí rồi chọn.

5. Access path — quyết định đọc dữ liệu ở các lá

Quyết định quan trọng nhất ở mỗi node scan (lá) là access path: lấy dữ liệu từ bảng bằng cách nào. Ở mức nguyên lý có ba lựa chọn cốt lõi:

• Full table scan (quét toàn bảng): đọc tuần tự mọi dòng từ đầu đến cuối, kiểm tra điều kiện trên từng dòng. Không cần index. Tối ưu khi query lấy phần lớn bảng — vì dù sao cũng phải chạm gần hết, đọc tuần tự rẻ hơn nhảy lung tung.
• Index scan (quét qua index): dùng cấu trúc index đã sắp xếp để nhảy thẳng tới các dòng khớp, rồi với mỗi mục index, lấy dòng đầy đủ từ bảng (heap). Tối ưu khi query lấy ít dòng — index giúp bỏ qua phần lớn bảng.
• Index-only scan (chỉ đọc index): trường hợp đặc biệt khi mọi cột query cần đều đã nằm trong index — database trả kết quả thẳng từ index, không chạm bảng. Nhanh nhất vì tiết kiệm hẳn bước fetch dòng gốc. (Nền tảng heap vs index ở Module 6 — Tại sao cần index.)

Optimizer chọn access path nào? Dựa trên selectivity (độ chọn lọc) của điều kiện lọc — tức tỉ lệ dòng mà điều kiện giữ lại:

Đây là nghịch lý nhiều người mới ngạc nhiên: có index không có nghĩa database sẽ dùng index. Nếu điều kiện lọc giữ lại phần lớn bảng, full scan đọc tuần tự rẻ hơn index scan — vì index scan với nhiều dòng phải nhảy qua lại giữa index và bảng (random I/O), tốn hơn đọc tuần tự cả khối. Quay lại ví dụ đầu bài: assignee_id = 7 selective cao (ít dòng) → index scan, 5ms; assignee_id > 0 giữ gần hết bảng → full scan, 900ms. Cùng cột, cùng index có sẵn — khác access path vì khác selectivity.

-- Selective cao -> optimizer thuong chon index scan
SELECT * FROM tasks WHERE id = 12345;            -- 1 dong / 10M

-- Selective thap (giu gan het) -> optimizer thuong chon full scan
SELECT * FROM tasks WHERE id > 0;                -- ~10M / 10M dong

6. Pitfall — index không được dùng dù đã tạo

-- WRONG: ham boc cot -> index tren email co the bi bo qua
SELECT * FROM users WHERE UPPER(email) = '[email protected]';

-- DUNG (huong tiep can): chuan hoa du lieu khi luu, so sanh truc tiep cot
SELECT * FROM users WHERE email = '[email protected]';

-- WRONG: ep kieu ngam (cot so so voi chuoi)
SELECT * FROM tasks WHERE id = '12345';

-- DUNG: so sanh dung kieu
SELECT * FROM tasks WHERE id = 12345;

7. 📚 Deep Dive

8. Liên hệ các bài khác

• Bài 02 — Thuật toán JOIN: node Join trong cây toán tử thực ra chạy bằng một trong ba thuật toán; optimizer chọn cái nào và vì sao.
• Bài 03 — Cost model & cardinality: giai đoạn plan chấm chi phí thế nào, và vì sao ước lượng sai dẫn tới chọn nhầm access path/join.
• Module 6 — Tại sao cần index: nền tảng heap vs index, full scan vs index scan vs index-only — access path ở bài này xây trực tiếp trên đó.
• Module 3 — INNER JOIN: cú pháp JOIN khai báo mà bài 02 sẽ giải thích cơ chế thực thi bên dưới.
• Module 2 — Pattern matching: vì sao LIKE '%x' (wildcard đầu chuỗi) thường không dùng được index — một ví dụ điển hình của access path bị giới hạn bởi cách viết điều kiện.

9. Tóm tắt

• SQL là declarative: bạn khai báo kết quả, database tự chọn thuật toán lấy dữ liệu — vì nó biết dữ liệu (statistics + index) còn bạn thì không.
• Pipeline biến SQL thành plan: parse (cú pháp) → rewrite (biến đổi logic giữ nguyên kết quả) → plan/optimize (chọn plan rẻ nhất) → execute.
• Kết quả của giai đoạn plan là một cây toán tử: lá là scan, các node trên là filter/join/sort/aggregate; dữ liệu chảy từ lá lên gốc.
• Access path là quyết định ở mỗi lá: full scan (đọc cả bảng) vs index scan (nhảy thẳng) vs index-only (không chạm bảng) — chọn theo selectivity của điều kiện lọc.
• Có index không bảo đảm dùng index: điều kiện không selective, bọc cột trong hàm, hoặc ép kiểu ngầm đều có thể khiến optimizer bỏ qua index.
• Mọi RDBMS đều có lệnh xem plan (quy ước EXPLAIN) nhưng output khác nhau — nên học khái niệm cây/access path, rồi ánh xạ sang output của engine cụ thể.

10. Tự kiểm tra

Bài tiếp theo: Thuật toán JOIN — nested loop, hash, merge