Database: Query Planner và ACID

6. Query Planner & Optimizer

6.1 Vòng đời một SQL Query

SQL là ngôn ngữ declarative — bạn chỉ nói muốn gì, không phải làm thế nào. Query optimizer là thứ quyết định plan thực thi tốt nhất.

flowchart TB
  S["SQL String"] --> P["Lexer + Parser"]
  P --> A["AST (Abstract Syntax Tree)"]
  A --> SA["Semantic Analysis"]
  SA --> L["Logical Plan (what to do)"]
  L --> O["Optimizer (quan trọng nhất)"]
  O --> PP["Physical Plan (how to do it)"]
  PP --> E["Executor"]
  E --> R["Result"]

SQL String
    │
    ▼ Lexer + Parser
AST (Abstract Syntax Tree)
    │
    ▼ Semantic Analysis
Logical Plan (what to do)
    │
    ▼ Optimizer ← quan trọng nhất!
Physical Plan (how to do it)
    │
    ▼ Executor
Result

6.2 Statistics — Nền tảng của Optimizer

Optimizer không chạy query để biết có bao nhiêu rows — nó ước tính dựa trên statistics đã thu thập. Statistics càng chính xác, plan càng tốt.

DB thu thập:
  - n_distinct: số unique values trong column
  - histogram: phân phối values
  - null_frac: tỉ lệ NULL
  - correlation: thứ tự vật lý vs logical

Ví dụ histogram:
  Column: age
  Buckets: [18-25: 20%] [25-35: 35%] [35-50: 30%] [50+: 15%]

  Query: WHERE age BETWEEN 25 AND 35
  → Optimizer ước tính 35% rows → quyết định dùng index hay seq scan

Nếu statistics lỗi thời (chưa ANALYZE), optimizer có thể chọn plan tệ. Đây là nguyên nhân phổ biến của "query chạy chậm đột ngột sau khi data thay đổi nhiều".

6.3 Join Algorithms

Optimizer chọn join algorithm dựa trên kích thước tables, available memory, và loại join:

Nested Loop Join: duyệt từng row của outer table, với mỗi row tìm match trong inner table. Tốt khi outer table nhỏ và inner table có index. Tệ khi cả hai table lớn vì O(M × N).

Hash Join: build hash table từ table nhỏ hơn, rồi probe với table lớn. O(M + N) — lý tưởng cho large tables với equality joins. Cần đủ memory để giữ hash table; nếu không đủ thì phải spill to disk (chậm hơn nhiều).

Sort-Merge Join: sort cả hai tables theo join key, rồi merge. Tốt khi data đã có index (đã sorted) hoặc cho range joins. Tệ nếu phải sort từ đầu.

Optimizer chọn dựa trên:
  - Table sizes (từ statistics)
  - Available memory (work_mem trong PostgreSQL)
  - Index availability
  - Join type (equality, range)

6.4 EXPLAIN ANALYZE — Đọc Query Plan

EXPLAIN ANALYZE là công cụ số một để debug slow queries. Nó thực thi query thật sự và so sánh estimated vs actual.

EXPLAIN ANALYZE
SELECT u.name, COUNT(o.id)
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE u.created_at > '2024-01-01'
GROUP BY u.name;

Output (PostgreSQL):
HashAggregate (cost=1234..1256 rows=1000 width=40)
               actual time=45.2..46.1 rows=892 loops=1)
  → Hash Join (cost=500..1200 rows=5000 width=32)
               actual time=12.3..40.1 rows=4821 loops=1)
      → Seq Scan on orders o (cost=0..300 rows=50000)
      → Hash (cost=400..400 rows=8000)
            → Index Scan using idx_users_created on users u
               (cost=0.43..400 rows=8000)
               Index Cond: (created_at > '2024-01-01')

Đọc từ TRONG ra NGOÀI (leaf nodes trước):
  1. Index Scan on users (filtered by created_at)
  2. Seq Scan on orders (toàn bộ)
  3. Hash Join
  4. HashAggregate (GROUP BY)

cost=X..Y: X = startup cost, Y = total cost
rows=N: estimated rows — nếu khác actual nhiều → statistics lỗi thời

Dấu hiệu cần chú ý: rows=8000 nhưng actual rows=50000 → optimizer underestimate → có thể chọn plan sai.

6.5 Common Query Optimization Techniques

Optimizer tự động áp dụng các kỹ thuật này, nhưng biết chúng giúp bạn viết query tốt hơn:

Predicate Pushdown: filter càng sớm càng tốt để giảm rows cần join.

-- Optimizer tự convert:
SELECT * FROM orders o JOIN users u ON o.user_id = u.id WHERE u.country = 'VN'
-- Thành: chỉ load users WHERE country='VN' trước khi join

Projection Pushdown: chỉ đọc columns cần thiết, không đọc toàn bộ row.

Constant Folding: WHERE price * 2 > 100 → WHERE price > 50 (tính lúc compile).

Join Reordering: với N tables, optimizer thử nhiều thứ tự join. N tables có N! thứ tự → dùng dynamic programming hoặc heuristics khi N lớn.

7. ACID — Chi tiết kỹ thuật

7.1 Atomicity

"All or nothing" — transaction hoặc commit hoàn toàn hoặc rollback hoàn toàn. Không có trạng thái "commit một nửa".

InnoDB implement bằng Undo Log: trước khi modify row, ghi giá trị cũ vào undo log. Nếu rollback → đọc undo log → khôi phục. Undo log cũng được tái sử dụng cho MVCC (xem section 9).

7.2 Consistency

"DB luôn ở trạng thái hợp lệ theo rules đã định." Rules bao gồm: constraints (NOT NULL, UNIQUE, FK, CHECK), triggers, cascades, và application-level invariants.

Ví dụ: transfer $100 từ A sang B — tổng balance trước và sau phải bằng nhau. Nếu A không đủ tiền → vi phạm CHECK constraint → rollback.

Lưu ý: Consistency trong ACID ≠ C trong CAP theorem. ACID C là về data validity; CAP C là về tất cả nodes thấy cùng data tại cùng thời điểm.

7.3 Isolation

"Transactions không ảnh hưởng lẫn nhau." Implement qua locking và/hoặc MVCC.

Có spectrum từ lỏng đến chặt:

Read Uncommitted ← (loosest, thực tế không ai dùng)
Read Committed
Repeatable Read
Serializable     ← (strictest)

7.4 Durability

"Committed transaction tồn tại mãi mãi, kể cả sau crash."

InnoDB implement: commit phải đợi WAL fsync to disk trước khi return. Nếu crash sau commit, WAL đảm bảo có thể redo transaction. innodb_flush_method = O_DIRECT bypass OS page cache để write thẳng to disk — tránh double-buffering.

Replication tăng cường durability hơn nữa: MySQL semi-synchronous replication chỉ return commit sau khi ít nhất 1 replica confirm nhận WAL.

8. Isolation Levels & Anomalies

8.1 Các Anomaly (hiện tượng bất thường)

Dirty Read: đọc data chưa commit của transaction khác. Transaction kia rollback → bạn đã dùng data không bao giờ tồn tại.

Non-Repeatable Read: đọc cùng row 2 lần trong transaction, kết quả khác nhau vì transaction khác đã UPDATE và COMMIT ở giữa.

Phantom Read: đọc cùng một tập rows 2 lần, số lượng rows khác nhau vì transaction khác đã INSERT/DELETE rows thỏa điều kiện.

Lost Update: hai transactions cùng đọc rồi update cùng giá trị → update của transaction đầu bị ghi đè.

T1: read counter=10 → write counter=11
T2: read counter=10 → write counter=11
→ Kết quả: 11 (đúng ra phải là 12!)

Write Skew: hai transactions cùng đọc rồi update khác nhau dựa trên điều kiện đọc được → vi phạm constraint toàn cục.

Rule: ít nhất 1 doctor phải on-call
T1: thấy 2 doctors → tự off-call
T2: thấy 2 doctors → tự off-call
Kết quả: 0 doctors on-call!

8.2 Isolation Levels

                    Dirty   Non-Rep  Phantom  Lost    Write
                    Read    Read     Read     Update  Skew
─────────────────────────────────────────────────────────────
Read Uncommitted     ✅      ✅       ✅       ✅      ✅
Read Committed       ❌      ✅       ✅       ✅      ✅
Repeatable Read      ❌      ❌       ✅*      ❌**    ✅
Serializable         ❌      ❌       ❌       ❌      ❌

✅ = anomaly có thể xảy ra
* MySQL InnoDB Repeatable Read ngăn Phantom Read bằng gap locks
** Tùy implementation

8.3 Chi tiết từng level

Read Uncommitted: không lock gì khi read. Thực tế không ai dùng vì Dirty Read là không thể chấp nhận.

Read Committed (PostgreSQL default): mỗi statement thấy snapshot tại thời điểm statement bắt đầu (không phải thời điểm transaction bắt đầu). Non-repeatable read vẫn có thể xảy ra.

Repeatable Read (MySQL InnoDB default): mỗi transaction thấy snapshot tại thời điểm transaction bắt đầu. Tất cả reads trong transaction nhìn thấy cùng data. InnoDB dùng gap locks để ngăn phantom reads thêm.

Serializable: transactions được thực thi như thể chạy tuần tự. PostgreSQL 9.1+ implement bằng SSI (Serializable Snapshot Isolation) — optimistic approach, ít blocking hơn 2PL truyền thống.