Scan strategies — Seq Scan / Index Scan / Index Only Scan / Bitmap Heap Scan

PostgreSQL có 4 cách đọc data từ table: Seq Scan (full table), Index Scan (index lookup rồi heap fetch), Index Only Scan (index cover, không touch heap), Bitmap Heap Scan (combine multiple index). Khi nào planner chọn cái nào — đó là core của query tuning.

Thêm index không phải lúc nào cũng giúp. Query WHERE status = 'todo' trả về 70% row dù có index trên status vẫn chạy Seq Scan — và đó là quyết định đúng của planner. Hiểu vì sao là bước đầu tiên để optimize đúng chỗ, không phải thêm index vô tội vạ.

1. Analogy — Tìm sách trong thư viện 1 triệu cuốn

Hình dung thư viện có 1 triệu cuốn sách, xếp trên 10.000 kệ. Bạn cần tìm sách theo các tiêu chí khác nhau. Thủ thư có 4 chiến lược:

2. Vì sao 4 strategy — tradeoff sequential vs random I/O

Planner không chọn strategy tùy tiện — nó tính cost dựa trên tradeoff I/O cơ bản:

Sequential I/O: đọc các page liền nhau, prefetch friendly. HDD đạt ~100 MB/s, SSD ~3 GB/s.

Random I/O: đọc page rải rác. HDD seek time ~10 ms, SSD ~0.1 ms. Đắt hơn nhiều so với sequential.

PostgreSQL encode tradeoff này qua tham số random_page_cost:

SHOW random_page_cost;
-- 4 (default)
-- Nghia la: 1 random page read = cost cua 4 sequential page read

Hệ quả trực tiếp:

• Index Scan = nhiều random heap access (1 random seek per row matched).
• Seq Scan = đọc sequential toàn bộ heap, prefetch friendly.
• Khi query return >5–10% row: tổng random seek từ Index Scan vượt qua cost của Seq Scan → planner chọn Seq Scan.
• Trên SSD, có thể set random_page_cost=1.1 để planner ưu tiên index hơn — nhưng đừng làm mù quáng, luôn đo EXPLAIN ANALYZE trước sau.

Cost model (đơn giản hóa):
  Seq Scan cost  = seq_page_cost × N_pages
  Index Scan cost = index_pages + heap_pages × selectivity × random_page_cost

Breakeven: khi heap_pages × selectivity × 4 > N_pages → planner chọn Seq Scan. Với 1 triệu row / 1000 page: breakeven ≈ 1000/(1000×4) = 25% selectivity. Thực tế planner còn tính cả CPU cost — breakeven thường rơi vào 5–15%.

3. Seq Scan — khi full table đọc tuần tự thắng

Seq Scan đọc toàn bộ heap file từ đầu đến cuối, page theo page, theo thứ tự vật lý. Không cần index.

EXPLAIN ANALYZE SELECT * FROM tasks WHERE status = 'todo';

Seq Scan on tasks  (cost=0.00..18334.00 rows=700000 width=64)
                   (actual time=0.020..125.500 rows=700000 loops=1)
  Filter: (status = 'todo'::text)
  Rows Removed by Filter: 300000
Planning Time: 0.8 ms
Execution Time: 128.3 ms

status = 'todo' chiếm 70% row → Seq Scan thắng dù có index trên status.

Khi nào Seq Scan là lựa chọn đúng:

• Selectivity thấp: return >10% row — random I/O từ index đắt hơn sequential.
• Table nhỏ: dưới vài trăm row, overhead index lookup không đáng.
• Không có index match WHERE: không có lựa chọn nào khác.
• VACUUM cần chạy qua: Seq Scan trigger visibility map update cho future Index Only Scan.

Khi thấy Seq Scan trên table lớn, câu hỏi đúng không phải "thêm index ngay" mà là: selectivity của query này là bao nhiêu? Nếu return >10% row thì Seq Scan hợp lý.

4. Index Scan — selective lookup với random heap access

Index Scan dùng khi query rất selective — trả về ít row. Planner traverse B-tree để tìm key → lấy CTID (heap pointer) → random access vào heap page để fetch row.

EXPLAIN ANALYZE SELECT * FROM tasks WHERE id = 42;

Index Scan using tasks_pkey on tasks  (cost=0.42..8.44 rows=1 width=64)
                                      (actual time=0.025..0.027 rows=1 loops=1)
  Index Cond: (id = 42)
Planning Time: 0.5 ms
Execution Time: 0.1 ms

Lifecycle của một Index Scan:

1. Traverse B-tree từ root → internal pages → leaf page — tìm key 42.
2. Đọc CTID = (page_number, offset) từ leaf page.
3. Random seek vào heap page page_number, đọc tuple tại offset.
4. Check visibility: xmin/xmax vs current snapshot (MVCC — bài 4 Module 6 của khoá này).
5. Return row nếu visible.

Mỗi row matched = 1 random heap access. Với 1 row → 1 random seek → nhanh. Với 50.000 row → 50.000 random seeks → chậm hơn Seq Scan.

Cost ước tính:
  = index_pages (B-tree height ~3-4)
  + N_rows_matched × random_page_cost
  = 3 + 1 × 4 = 7   ← rất rẻ cho 1 row
  = 3 + 50000 × 4   ← đắt hơn Seq Scan cho 50k row

Khi nào Index Scan tốt: selectivity rất cao (<1–5%), query point lookup hoặc range hẹp (WHERE id = 42, WHERE email = '[email protected]', WHERE due_at BETWEEN t1 AND t2 với range nhỏ).

5. Index Only Scan — covering index, tránh heap hoàn toàn

Index Only Scan là strategy nhanh nhất khi có thể: không touch heap page chút nào. Điều kiện: index phải chứa tất cả column cần trong SELECT và WHERE (covering index), và visibility map (VM) của heap phải up-to-date.

Tạo covering index với INCLUDE:

-- Cover query: chi can id va status -> tao index INCLUDE status
CREATE INDEX idx_tasks_assignee_cover
ON tasks(assignee_id) INCLUDE (status);

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, status FROM tasks WHERE assignee_id = 5;

Index Only Scan using idx_tasks_assignee_cover on tasks
  (cost=0.42..6.44 rows=2 width=12)
  (actual time=0.020..0.025 rows=2 loops=1)
  Heap Fetches: 0
  Buffers: shared hit=4
Planning Time: 0.4 ms
Execution Time: 0.1 ms

Heap Fetches: 0 là dấu hiệu thành công. Index chứa đủ data, không cần vào heap.

Visibility map (VM) — tại sao cần VACUUM:

VM là bitmap 2-bit per page, lưu trạng thái mỗi heap page:

• all-visible: mọi tuple trên page đều committed và visible cho mọi snapshot hiện tại.
• all-frozen: mọi tuple đã frozen (không cần check xmin/xmax nữa).

Index Only Scan check VM trước khi return row từ index:

• Page là all-visible → trust giá trị từ index, skip heap hoàn toàn.
• Page không phải all-visible → phải fetch heap page để check visibility → Heap Fetches tăng.

VM up-to-date (sau VACUUM):
  Index Only Scan → check VM → page all-visible → return data từ index
  Heap Fetches: 0  ✅

VM stale (table vừa có nhiều UPDATE/DELETE, autovacuum chưa kịp):
  Index Only Scan → check VM → page NOT all-visible → fetch heap page
  Heap Fetches: 15000  ❌ → Index Only Scan thoái hóa thành Index Scan

Fix khi Heap Fetches > 0:

VACUUM ANALYZE tasks;  -- update VM + refresh stats
-- Sau do EXPLAIN lai → Heap Fetches: 0

VM được update bởi bài 5 Module 6 của khoá này (VACUUM internals). Sau VACUUM thành công, autovacuum duy trì VM để Index Only Scan hoạt động liên tục.

6. Bitmap Heap Scan — combine multiple index, giảm random I/O

Bitmap Heap Scan giải quyết bài toán: khi có 2 điều kiện trên 2 column khác nhau, mỗi điều kiện có index riêng, nhưng selectivity mỗi cái vẫn trung bình (1–10%). Dùng Index Scan riêng lẻ cho từng index thì quá nhiều random seek; dùng Seq Scan thì lãng phí.

CREATE INDEX idx_tasks_status ON tasks(status);
CREATE INDEX idx_tasks_due ON tasks(due_at);

EXPLAIN ANALYZE
SELECT * FROM tasks
WHERE status = 'doing' OR due_at < now() - interval '7 days';

Bitmap Heap Scan on tasks  (cost=125.45..2500.50 rows=15000 width=64)
                           (actual time=12.500..45.000 rows=15234 loops=1)
  Recheck Cond: (status = 'doing' OR due_at < now() - '7 days'::interval)
  Heap Blocks: exact=850
  ->  BitmapOr  (cost=125.00..125.00 rows=15000 width=0)
        ->  Bitmap Index Scan on idx_tasks_status
              (cost=0.00..50.00 rows=8000 width=0)
              Index Cond: (status = 'doing')
        ->  Bitmap Index Scan on idx_tasks_due
              (cost=0.00..75.00 rows=7000 width=0)
              Index Cond: (due_at < now() - '7 days'::interval)
Planning Time: 1.2 ms
Execution Time: 47.3 ms

Lifecycle Bitmap Heap Scan:

1. Bitmap Index Scan 1: traverse idx_tasks_status, build bitmap — ghi lại row ID (hoặc page ID) của mọi row có status = 'doing'.
2. Bitmap Index Scan 2: traverse idx_tasks_due, build bitmap riêng — row ID có due_at < now() - 7 days.
3. BitmapOr: combine 2 bitmap (union cho OR, intersection cho AND).
4. Sort by page number: bitmap được sắp xếp theo physical page order.
5. Fetch heap: duyệt heap một lần theo thứ tự page — mỗi page chỉ đọc 1 lần dù có nhiều row matching trên đó. Giảm random I/O đáng kể.
6. Recheck Cond: nếu bitmap chuyển sang lossy mode (memory không đủ lưu row-level bitmap → chuyển sang page-level bitmap), phải recheck condition trên mỗi row fetched.

So sánh với Index Scan riêng lẻ:
  15.000 row matched × random_page_cost=4 = 60.000 cost units (Index Scan thuần)
  850 heap pages × 1 (sequential sau sort) = 850 cost units (Bitmap Heap Scan)
  → Bitmap Heap Scan nhanh hơn ~70x cho medium selectivity

AND condition cũng dùng Bitmap Heap Scan với BitmapAnd thay vì BitmapOr:

EXPLAIN ANALYZE
SELECT * FROM tasks
WHERE status = 'doing' AND due_at < now() - interval '7 days';
-- Plan: BitmapAnd (intersection) -> Bitmap Heap Scan

7. Pitfall — index không guarantee dùng, ANALYZE stale, IOS heap fetches

CREATE INDEX idx_tasks_status ON tasks(status);

EXPLAIN SELECT * FROM tasks WHERE status = 'todo';
-- Seq Scan on tasks  (cost=0.00..18334.00 rows=700000 ...)
-- Index vua tao nhung khong duoc dung!

-- Partial index chi chua row chua hoan thanh (30% data)
CREATE INDEX idx_tasks_active ON tasks(status)
WHERE status IN ('todo', 'doing');

-- Bulk insert 1 trieu row moi
INSERT INTO tasks SELECT ... FROM generate_series(1, 1000000);

-- Stats van dang la 100k row (truoc bulk insert)
EXPLAIN SELECT * FROM tasks WHERE assignee_id = 5;
-- rows=2 (estimate sai qua, thuc te co the la 2000)
-- Planner guess sai selectivity -> chon sai strategy

ANALYZE tasks;  -- cap nhat stats ngay lap tuc

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, status FROM tasks WHERE assignee_id = 5;
-- Index Only Scan ... Heap Fetches: 15000
-- shared hit=15850
-- IOS khong hieu qua vi VM stale

VACUUM ANALYZE tasks;

-- EXPLAIN lai → Heap Fetches: 0
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, status FROM tasks WHERE assignee_id = 5;
-- Index Only Scan ... Heap Fetches: 0, shared hit=4

8. Applied — TaskFlow dashboard với covering index

Dashboard TaskFlow hiển thị danh sách task theo assignee — query chạy hàng nghìn lần mỗi phút. Mục tiêu: Index Only Scan với Heap Fetches: 0.

Bước 1: Xác định query và plan hiện tại:

-- Dashboard query
SELECT id, status, due_at FROM tasks WHERE assignee_id = 5;

-- Plan ban dau (khong co index phu hop):
Seq Scan on tasks  (cost=0.00..18334.00 rows=200 width=28)
                   (actual time=0.020..95.000 rows=200 loops=1)
  Filter: (assignee_id = 5)
  Rows Removed by Filter: 999800
Execution Time: 97.4 ms

Bước 2: Tạo covering index:

-- Covering index: assignee_id la search key, INCLUDE cac column SELECT
CREATE INDEX idx_tasks_dashboard_cover
ON tasks(assignee_id) INCLUDE (status, due_at);

Bước 3: VACUUM ANALYZE để update VM và stats:

VACUUM ANALYZE tasks;

Bước 4: Verify plan:

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, status, due_at FROM tasks WHERE assignee_id = 5;

Index Only Scan using idx_tasks_dashboard_cover on tasks
  (cost=0.42..6.85 rows=200 width=28)
  (actual time=0.018..0.380 rows=200 loops=1)
  Index Cond: (assignee_id = 5)
  Heap Fetches: 0
  Buffers: shared hit=6
Planning Time: 0.3 ms
Execution Time: 0.4 ms

Kết quả: 97 ms → 0.4 ms (~240x). Heap Fetches: 0 — mọi data lấy từ index, không touch heap. 6 buffer hit thay vì hàng ngàn page.

INCLUDE column (status, due_at) không tham gia sort order của B-tree — chỉ được lưu ở leaf page để cover SELECT list. Write overhead thấp hơn so với thêm vào composite key. Chi tiết về INCLUDE vs composite key trong bài 4 Module 5 của khoá này (specialized index).

9. Deep Dive — scan strategy internals

10. Tóm tắt

• PostgreSQL có 4 scan strategy: Seq Scan (full table sequential), Index Scan (B-tree + random heap access), Index Only Scan (index cover, không heap), Bitmap Heap Scan (combine index, fetch heap sorted).
• Planner chọn dựa trên cost model: random_page_cost=4 (mặc định) = 1 random I/O đắt bằng 4 sequential I/O.
• Seq Scan: thắng khi selectivity thấp (>5–15% row) hoặc table nhỏ — sequential I/O rẻ hơn nhiều random seek.
• Index Scan: thắng khi selectivity cao (<1–5%) — ít random seek, overhead tra B-tree nhỏ.
• Index Only Scan: nhanh nhất khi covering index (INCLUDE columns) + VM up-to-date (sau VACUUM). Heap Fetches: 0 là mục tiêu.
• Bitmap Heap Scan: tối ưu cho medium selectivity (1–10%) với 2+ index — build bitmap, sort by page, fetch heap 1 lần per page.
• Thêm index không guarantee được dùng — planner tính selectivity; 70% match → Seq Scan vẫn thắng.
• ANALYZE stale sau bulk insert → planner estimate sai → chọn sai strategy. Chạy ANALYZE sau bulk load.
• IOS với Heap Fetches > 0 → VM stale → chạy VACUUM ANALYZE.

11. Tự kiểm tra

Bài tiếp theo: Join algorithms — Nested Loop / Hash Join / Merge Join