Cost model & cardinality — vì sao planner chọn sai

TL;DR: Optimizer chọn plan bằng cách gán cho mỗi plan ứng viên một con số cost (chi phí ước lượng) rồi chọn cái rẻ nhất. Cost được tính từ statistics — dữ liệu thống kê về bảng mà database thu thập sẵn: số dòng, số giá trị riêng biệt mỗi cột (n_distinct), và phân bố giá trị (histogram). Bước cốt lõi là cardinality estimation: đoán xem mỗi toán tử sẽ trả ra bao nhiêu dòng. Đoán đúng → chọn access path và join algorithm tốt. Đoán sai → chọn nhầm, query chậm hàng chục lần. Sai số đặc biệt nguy hiểm vì nó dồn lại qua nhiều join: lệch ở bảng đầu nhân lên ở các bước sau, dẫn tới bad plan. Hai nguồn sai phổ biến nhất: statistics cũ/lệch (database chưa cập nhật sau khi dữ liệu đổi nhiều) và query viết khiến ước lượng khó (hàm bọc cột, tương quan giữa cột). Hướng xử lý ở mức nguyên lý: giữ statistics tươi và viết điều kiện để optimizer ước lượng dễ.

Một query join ba bảng chạy 20ms suốt nhiều tháng. Một sáng nó đột nhiên mất 12 giây — không ai đổi query, không đổi index, không đổi dữ liệu cấu trúc. Thủ phạm: đêm trước có một đợt nạp 5 triệu dòng vào một bảng, nhưng statistics chưa được cập nhật. Optimizer vẫn tưởng bảng đó có vài nghìn dòng như cũ, ước lượng sai số dòng, chọn nested loop thay vì hash join — và nested loop trên bảng giờ đã khổng lồ thành thảm hoạ. Cập nhật statistics, optimizer ước lượng lại đúng, chọn hash join, query về 20ms.

Đây là một trong những loại sự cố khó hiểu nhất với người mới: query y nguyên mà tốc độ đổi đột ngột. Gốc rễ nằm ở chỗ optimizer không nhìn dữ liệu thật lúc lập plan — nó nhìn thống kê tóm tắt về dữ liệu. Khi thống kê lệch thực tế, mọi ước lượng phía sau lệch theo. Bài này mổ cost model hoạt động ra sao, cardinality estimation là gì, vì sao sai số nhân lên qua join, và cách giữ optimizer ước lượng đúng — tất cả agnostic.

1. Analogy — Lên lộ trình giao hàng bằng bản đồ cũ

Một tài xế giao hàng lên lộ trình tối ưu dựa trên bản đồ và dự báo giao thông, không phải chạy thử mọi con đường. Nếu bản đồ cập nhật (biết đường nào mới mở, đoạn nào kẹt), lộ trình chọn sẽ tốt. Nhưng nếu dùng bản đồ cũ — không biết một con đường tắt vừa bị chặn, hay một khu vừa xây xong gây kẹt — tài xế chọn lộ trình "tối ưu trên giấy" nhưng thực tế tắc cứng. Anh ta không sai về cách tính; anh ta sai vì dữ liệu đầu vào lệch thực tế.

Optimizer y hệt. Nó không chạy thử mọi plan rồi đo — quá đắt. Nó ước lượng cost từ statistics (bản đồ về dữ liệu). Statistics tươi → plan tốt. Statistics cũ → plan "tối ưu trên giấy" nhưng chạy chậm thực tế. Và như tài xế ước lượng sai một đoạn đầu khiến cả lộ trình dài hỏng theo, optimizer ước lượng sai số dòng ở một bước khiến các bước sau chọn nhầm — sai số dồn lại.

2. Cost model — gán giá cho mỗi plan

Ở bài 01 ta thấy optimizer sinh nhiều plan tương đương. Làm sao chọn? Nó gán cho mỗi plan một con số cost — ước lượng tài nguyên phải tiêu để chạy plan đó, rồi chọn plan cost thấp nhất.

Cost không phải thời gian thực mà là một đại lượng tổng hợp, thường gồm:

• I/O cost: số page (khối dữ liệu) phải đọc từ đĩa — thường là thành phần lớn nhất, vì đọc đĩa chậm hơn nhiều so với tính toán trong bộ nhớ.
• CPU cost: số phép so sánh, băm, sắp xếp phải thực hiện.
• (Một số engine thêm chi phí mạng, bộ nhớ...)

cost(plan) ~ (so page doc tu dia) * gia_io
           + (so dong xu ly)      * gia_cpu
           + ...
-- Optimizer so cost giua cac plan, chon thap nhat. Day la UOC LUONG, khong phai do that.

Điểm mấu chốt: mọi thành phần cost đều phụ thuộc vào số dòng. Đọc bao nhiêu page tuỳ bảng bao nhiêu dòng và điều kiện lọc giữ lại bao nhiêu. So sánh bao nhiêu lần tuỳ join ra bao nhiêu dòng. Nên trước khi tính cost, optimizer phải trả lời câu hỏi nền tảng: mỗi toán tử sẽ xử lý bao nhiêu dòng? Đó chính là cardinality estimation — và nó là khâu dễ sai nhất. Như Wikipedia ghi: "ước lượng chi phí của các plan thay thế là một trong những bài toán khó nhất của query optimization", chủ yếu vì cardinality estimation khó.

3. Statistics — dữ liệu optimizer dựa vào

Optimizer không quét dữ liệu thật lúc plan (quá đắt). Nó dựa vào statistics — bản tóm tắt về dữ liệu mà database thu thập định kỳ (qua một lệnh quy ước thường gọi là ANALYZE, hoặc tự động). Ba loại thống kê cốt lõi, agnostic:

• Số dòng bảng (row count / table cardinality): bảng có bao nhiêu dòng. Quyết định chi phí full scan và kích thước mỗi phía join.
• n_distinct (số giá trị riêng biệt): một cột có bao nhiêu giá trị khác nhau. Cột gender có n_distinct = 2; cột user_id có n_distinct = số user. Dùng để đoán một điều kiện bằng nhau giữ lại bao nhiêu dòng.
• Histogram (biểu đồ phân bố): chia khoảng giá trị của cột thành các "thùng" (bucket) ghi mỗi khoảng có bao nhiêu dòng. Cần khi dữ liệu lệch (skew) — ví dụ 90% đơn hàng có status='done', 10% rải các trạng thái khác. Không có histogram, optimizer giả định phân bố đều và đoán sai nặng với dữ liệu lệch.

Từ ba thống kê này, optimizer ước lượng selectivity của một điều kiện. Ví dụ ước lượng đơn giản nhất cho điều kiện bằng nhau, giả định phân bố đều:

-- Uoc luong so dong WHERE col = value tra ra:
selectivity ~ 1 / n_distinct(col)
so dong uoc luong ~ row_count * selectivity

-- Vi du: bang 1,000,000 dong, cot status co n_distinct = 5
-- WHERE status = 'open'  ->  ~ 1,000,000 / 5 = 200,000 dong (gia dinh deu)

Nếu phân bố thực không đều (status open thực ra chỉ 2% chứ không phải 20%), ước lượng "phân bố đều" sai 10 lần — đó là lúc histogram cần thiết để sửa.

4. Cardinality estimation — khâu dễ sai nhất, và sai số dồn qua join

Cardinality estimation là việc đoán số dòng đầu ra của mỗi toán tử trong cây plan. Optimizer làm từ lá lên: ước lượng số dòng mỗi scan trả ra, rồi mỗi join trả ra, lan dần lên gốc.

Vấn đề chí mạng: sai số nhân lên qua mỗi join. Mỗi bước ước lượng dựa trên đầu ra ước lượng của bước dưới — nên lệch ở bảng đầu nhân với lệch ở bước join sau, dồn thành sai số khổng lồ ở các join cuối.

flowchart TB
  S1["Scan A<br/>uoc luong 1000<br/>(that: 10000, lech 10x)"] --> J1["Join A-B<br/>lech tiep 5x"]
  S2["Scan B<br/>uoc luong dung"] --> J1
  J1 --> J2["Join voi C<br/>sai so don: 10 x 5 = 50x"]
  S3["Scan C"] --> J2
  J2 --> R["Plan chon dua tren<br/>uoc luong lech 50 lan<br/>-> BAD PLAN"]

Tình huống cụ thể: optimizer ước lượng join A-B trả 1000 dòng (thực ra 50.000). Dựa vào "chỉ 1000 dòng", nó chọn nested loop để join tiếp với C — hợp lý nếu thật 1000 dòng. Nhưng thực tế 50.000 dòng × tra C mỗi dòng = nested loop biến thành O(n*m) thảm hoạ. Nếu ước lượng đúng 50.000, optimizer đã chọn hash join (bài 02). Một sai số cardinality ở bước giữa làm hỏng lựa chọn thuật toán ở bước sau.

Vì sao cardinality hay sai? Vài nguồn gốc:

• Statistics cũ: dữ liệu đã đổi nhiều (nạp lớn, xoá lớn) nhưng thống kê chưa cập nhật — như đầu bài.
• Giả định phân bố đều sai: dữ liệu lệch mà không có histogram đủ chi tiết.
• Tương quan giữa cột (correlation): optimizer thường giả định các điều kiện độc lập. WHERE city = 'Hanoi' AND district = 'Ba Dinh' — hai điều kiện này tương quan (Ba Dinh chỉ ở Hà Nội), nhưng optimizer nhân hai selectivity như độc lập → ước lượng quá thấp.
• Hàm bọc cột: WHERE UPPER(email) = ... khiến optimizer không tra được histogram của email → rơi về ước lượng mặc định thô.

5. Hướng xử lý — giúp optimizer ước lượng đúng

Vì bad plan gốc ở ước lượng sai, hai hướng khắc phục ở mức nguyên lý (áp dụng mọi engine):

A. Giữ statistics tươi. Đây là biện pháp số một. Sau khi dữ liệu thay đổi lớn (nạp/xoá hàng loạt), chạy cập nhật statistics (lệnh quy ước ANALYZE). Hầu hết database có cơ chế tự động cập nhật khi tỉ lệ dòng thay đổi vượt ngưỡng, nhưng sau một đợt nạp lớn đột biến, cập nhật thủ công ngay là cách chắc chắn nhất. Đầu bài chính là ca này.

-- Sau khi nap/xoa lon, cap nhat statistics de optimizer uoc luong dung
-- (ten lenh khac nhau giua engine; ANALYZE la quy uoc pho bien)
ANALYZE tasks;

B. Viết query để ước lượng dễ. Cách viết điều kiện ảnh hưởng độ chính xác ước lượng:

• Để điều kiện chạm thẳng cột thô (không bọc hàm, không ép kiểu) — optimizer mới tra được histogram/n_distinct của cột đó. Bọc hàm → ước lượng mặc định thô → dễ sai.
• Lọc selective sớm — đưa điều kiện thu hẹp dữ liệu vào sớm để các bước join sau làm việc trên số dòng nhỏ và dễ ước lượng hơn.
• Cảnh giác điều kiện tương quan — khi lọc nhiều cột tương quan (city + district), biết rằng optimizer có thể ước lượng quá thấp; một số engine hỗ trợ khai báo thống kê đa cột (extended statistics) để sửa.

-- WRONG: ham boc cot -> optimizer mat histogram, uoc luong tho
SELECT * FROM users WHERE LOWER(email) = '[email protected]';

-- DUNG: cham thang cot tho -> optimizer tra duoc thong ke -> uoc luong dung
SELECT * FROM users WHERE email = '[email protected]';

6. Pitfall — bad plan do cardinality sai

-- Trieu chung: query nay tung 20ms, dot nhien 12s sau dot nap lon
SELECT o.id, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
JOIN line_items li ON li.order_id = o.id
WHERE o.created_at >= '2026-06-01';

-- DUNG (huong xu ly):
-- 1. Cap nhat statistics sau khi du lieu doi lon:
ANALYZE orders;  ANALYZE line_items;
-- 2. Xem plan, so "uoc luong" vs "thuc te" o moi node de tim cho lech:
--    EXPLAIN ... (dinh dang output tuy engine)

7. 📚 Deep Dive

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

• Bài 01 — Từ SQL đến kế hoạch thực thi: giai đoạn plan sinh nhiều plan ứng viên; bài này giải thích optimizer chấm điểm chúng thế nào để chọn.
• Bài 02 — Thuật toán JOIN: cardinality sai dẫn thẳng tới chọn nhầm nested loop / hash / merge — cost model là cầu nối giữa ước lượng và lựa chọn thuật toán.
• Module 6 — Tại sao cần index: cost model chấm access path dựa trên index — selectivity ước lượng quyết định index có được dùng không.
• Module 3 — INNER JOIN: thứ tự join (do cost quyết định) ảnh hưởng số dòng trung gian — gốc của sai số dồn.
• Module 2 — Pattern matching: LIKE với wildcard khiến selectivity khó ước lượng — một ví dụ điều kiện làm khó cardinality estimation.

9. Tóm tắt

• Optimizer chọn plan bằng cách gán cost (ước lượng I/O + CPU) cho mỗi plan rồi chọn cái thấp nhất — đây là ước lượng, không phải đo thật.
• Cost dựa trên statistics: số dòng bảng, n_distinct (giá trị riêng biệt mỗi cột), histogram (phân bố, cần khi dữ liệu lệch).
• Cardinality estimation — đoán số dòng đầu ra mỗi toán tử — là khâu dễ sai nhất, và mọi thành phần cost đều phụ thuộc nó.
• Sai số cardinality dồn lại qua nhiều join: lệch ở bảng đầu nhân lên ở các bước sau → chọn nhầm thuật toán → bad plan.
• Nguồn sai chính: statistics cũ, dữ liệu lệch không đủ histogram, điều kiện tương quan bị nhân như độc lập, hàm bọc cột.
• Hướng xử lý: giữ statistics tươi (ANALYZE sau nạp/xoá lớn) và viết query để ước lượng dễ (chạm cột thô, lọc selective sớm); khi chậm bất thường, so ước lượng vs thực tế qua EXPLAIN để tìm chỗ lệch.

10. Tự kiểm tra

Bài tiếp theo: Vòng đời dữ liệu