Composite index ordering — leftmost prefix rule + INCLUDE covering

Team TaskFlow tạo composite index để tăng tốc dashboard:

CREATE INDEX ON tasks(project_id, status, due_at);

Một tuần sau, dev thêm query mới:

SELECT * FROM tasks WHERE status = 'done';

EXPLAIN báo Seq Scan — index không được dùng. Tại sao? Index (project_id, status, due_at) sort theo project_id trước, status bên trong mỗi nhóm project_id, due_at bên trong mỗi nhóm (project_id, status). Query WHERE status = 'done' bỏ qua project_id — giống tra mục lục sách mà không biết chương nào, phải đọc toàn bộ. Không deterministic, không dùng được index.

Bài này giải thích leftmost prefix rule, 3 query pattern equality vs range, INCLUDE covering cho Index Only Scan, và decision matrix chọn thứ tự column theo workload thực tế.

1. Analogy — Mục lục đa cấp

Hình dung một cuốn sách kỹ thuật có mục lục 3 cấp: chủ đề → tiêu đề con → ngày xuất bản. Mục lục được sắp xếp theo thứ tự đó.

Muốn tìm tài liệu ngày 2026-05-01 mà không biết chủ đề hay tiêu đề con — bạn phải đọc toàn bộ mục lục vì ngày được sort trong từng nhóm (chủ đề, tiêu đề con), không có thứ tự toàn cục. Nhưng nếu biết chủ đề là "Database" — bạn đến đúng section, rồi tìm tiếp theo tiêu đề con hoặc ngày.

2. Composite index — cơ chế sort bên trong B-tree

CREATE INDEX idx_tasks_psd ON tasks(project_id, status, due_at);

B-tree lưu entry theo thứ tự từ điển trên tất cả 3 column:

-- Entry order (sort by all 3 columns lexicographically):
(1, 'doing', 2026-05-01)
(1, 'doing', 2026-05-03)
(1, 'done',  2026-04-28)
(1, 'todo',  2026-05-02)
(2, 'doing', 2026-05-01)
(2, 'done',  2026-05-05)
(2, 'todo',  2026-04-30)
...

Tree navigate: B-tree tìm project_id = 1 đến subtree project 1, rồi trong đó tìm status = 'done' đến sub-subtree, rồi trong đó range scan due_at. Mỗi bước thu hẹp phạm vi đọc.

Nếu bỏ qua project_id — B-tree không biết subtree nào chứa status = 'done' (mỗi project đều có status = 'done', phân tán khắp tree). Planner phải đọc toàn index — tốn kém như Seq Scan, nên planner chọn Seq Scan thẳng.

3. Leftmost prefix rule — query nào dùng được index

-- INDEX (project_id, status, due_at)

-- DUNG INDEX:
SELECT * FROM tasks WHERE project_id = 5;
-- prefix col 1 -> B-tree navigate den subtree project=5

SELECT * FROM tasks WHERE project_id = 5 AND status = 'done';
-- prefix col 1+2 -> subtree project=5, sub-subtree status='done'

SELECT * FROM tasks WHERE project_id = 5 AND status = 'done'
  AND due_at > '2026-05-01';
-- full 3 column -> narrow xuong range due_at

-- KHONG DUNG INDEX (skip col 1):
SELECT * FROM tasks WHERE status = 'done';
-- skip col 1 -> khong xac dinh duoc subtree nao

SELECT * FROM tasks WHERE due_at > '2026-05-01';
-- skip col 1 + col 2 -> khong navigate duoc

SELECT * FROM tasks WHERE status = 'done' AND due_at > '2026-05-01';
-- skip col 1 -> van khong dung duoc du co col 2+3

Quy tắc: WHERE phải bao gồm column 1 (leftmost prefix). Có thể thêm column 2, column 3 theo thứ tự liên tục. Nhảy qua column 1 thì index không dùng được — không phụ thuộc vào thứ tự viết trong WHERE clause, chỉ phụ thuộc vào cấu trúc index.

4. Ba pattern equality vs range — thứ tự column tối ưu

Quy tắc thumb: đặt equality column trước range column. Range column "ngắt" khả năng navigate tiếp — B-tree chỉ dùng range scan từ column range trở đi, các column sau không còn selective nữa.

-- DUNG INDEX OPTIMAL: equality truoc, range sau
CREATE INDEX ON tasks(status, due_at);

SELECT * FROM tasks WHERE status = 'done' AND due_at > '2026-05-01';
-- Plan: Index Scan
-- B-tree narrow den status='done' subtree, range scan due_at trong subtree do

-- KHONG OPTIMAL: range truoc, equality sau
CREATE INDEX ON tasks(due_at, status);

SELECT * FROM tasks WHERE status = 'done' AND due_at > '2026-05-01';
-- Plan: Index Scan (range tren due_at) + Filter (status='done')
-- Doc nhieu row hon vi status filter khong dung duoc index sau range column

Ví dụ thực tế TaskFlow — query "task cần làm trong 3 ngày tới":

-- Composite (assignee_id, status, due_at): equality assignee + status, range due_at
CREATE INDEX ON tasks(assignee_id, status, due_at);

SELECT * FROM tasks
WHERE assignee_id = 5
  AND status IN ('todo', 'doing')
  AND due_at BETWEEN now() AND now() + INTERVAL '3 days';
-- B-tree: assignee_id=5 subtree -> status IN subtree -> range scan due_at
-- Optimal: filter thu hep tu trai sang phai

5. INCLUDE covering — Index Only Scan

Composite index chỉ chứa các sort column. Nếu SELECT cần thêm column không trong index, planner phải fetch heap cho mỗi row match — Index Scan thay vì Index Only Scan.

-- Without INCLUDE: heap fetch sau index scan
CREATE INDEX ON tasks(status, due_at);

SELECT id, title FROM tasks WHERE status = 'done' AND due_at > '2026-05-01';
-- Plan: Index Scan -> Heap Fetch (id, title khong co trong index)
-- Moi row match can 1 random heap I/O

-- With INCLUDE: cover moi column SELECT
CREATE INDEX ON tasks(status, due_at) INCLUDE (id, title);

SELECT id, title FROM tasks WHERE status = 'done' AND due_at > '2026-05-01';
-- Plan: Index Only Scan (no heap fetch neu visibility map allow)
-- Toan bo data lay tu index leaf, khong can mo heap page

INCLUDE column có 3 đặc điểm quan trọng:

• Không tham gia sort — không ảnh hưởng tree structure, không dùng được trong WHERE.
• Stored at leaf — lưu cùng leaf entry, fetch không cần I/O thêm.
• PG 11+ feature — không có trong PG 10 trở về trước.

Tradeoff: index size lớn hơn vì mang thêm column data. Đổi lại: read query bỏ qua random heap I/O — đặc biệt quan trọng khi heap lớn hoặc cold (buffer cache miss thường xuyên).

6. Decision matrix — chọn thứ tự column

Query: WHERE col1 = X [AND col2 OP Y [AND col3 OP Z]]

Heuristic chon thu tu column:
1. Equality column truoc range column
2. Trong equality column: high cardinality truoc
   (narrow subtree som, it row can scan o level sau)
3. Range column o cuoi sort key
4. ORDER BY column cuoi neu trung range column -> planner skip sort step
5. SELECT-only column -> INCLUDE (khong sort, chi stored at leaf)

Áp dụng cho TaskFlow dashboard query:

-- Query: dashboard assignee
SELECT id, title FROM tasks
WHERE assignee_id = 5
  AND status IN ('todo', 'doing')
  AND due_at BETWEEN now() AND now() + INTERVAL '3 days'
ORDER BY due_at;

-- Equality: assignee_id (cardinality cao: nhieu assignee)
--           status (cardinality thap: 3 gia tri)
-- Range:    due_at
-- ORDER BY: due_at (cung range column -> bonus: planner skip sort)
-- SELECT:   id, title -> INCLUDE

-- Optimal index:
CREATE INDEX idx_tasks_dashboard
  ON tasks(assignee_id, status, due_at)
  INCLUDE (id, title);

Giải thích từng quyết định:

• assignee_id trước status: cardinality cao hơn (nhiều assignee vs 3 status value) → narrow subtree sớm hơn.
• status trước due_at: equality trước range.
• due_at là range column → cuối; trùng ORDER BY → planner không cần Sort node.
• id, title vào INCLUDE → Index Only Scan, không fetch heap.

7. Pitfall — column order khác nhau phá vỡ một trong nhiều query

-- Q1: dashboard assignee
-- WHERE assignee_id = 5 AND status = 'done'

-- Q2: global status report (common)
-- WHERE status = 'done'

-- Index (assignee_id, status): Q1 OK, Q2 skip col 1 -> Seq Scan
CREATE INDEX ON tasks(assignee_id, status);

-- Option A: doi thu tu -> Q2 OK nhung Q1 van OK (prefix status)
CREATE INDEX ON tasks(status, assignee_id);
-- Q1: WHERE assignee_id=5 AND status='done'
--     -> prefix status (col 1), narrow them assignee_id (col 2) -> OK
-- Q2: WHERE status='done'
--     -> prefix status (col 1) -> OK

-- Option B: tach 2 index rieng
CREATE INDEX ON tasks(assignee_id, status);  -- Q1
CREATE INDEX ON tasks(status);               -- Q2 dedicated
-- Tradeoff: write cost tang them 1 index, nhung moi query co index toi uu rieng

8. PG-specific — index skip scan

PostgreSQL chỉ có index skip scan cho B-tree từ bản 18 (2025). Trên PG 17 trở về trước, query bỏ qua column 1 luôn dẫn đến Seq Scan hoặc cần index riêng — nếu cluster còn chạy bản cũ thì workaround dưới đây vẫn là cách xử lý chính.

-- Index (a, b)
-- Query WHERE b = X (skip a) -> Seq Scan tren PG <= 17

-- Co che skip scan: DB tu dong enumerate distinct gia tri cua a,
-- chay scan cho moi gia tri. Oracle co tu lau, MySQL co tu 8.0.13,
-- PostgreSQL co tu PG 18.

-- Workaround cho PG <= 17: tao index thu 2
CREATE INDEX ON tasks(status);  -- serve WHERE status = X

Một workaround khác là "loose index scan" qua recursive CTE — nhưng phức tạp và thường chậm hơn index riêng. Forward: Module 8 của khoá này giải thích recursive CTE pattern.

9. Applied — TaskFlow dashboard: iterate 4 version index

Dashboard query từ Module 2 bài 7 của khoá này:

SELECT id, title FROM tasks
WHERE assignee_id = $1 AND status IN ('todo','doing')
  AND due_at BETWEEN now() AND now() + INTERVAL '3 days'
ORDER BY due_at NULLS LAST, id LIMIT 20;

Iterate 4 version index từ naive đến optimal:

-- v1: single column - poor selectivity
CREATE INDEX ON tasks(assignee_id);
-- Plan: Index Scan (lots of rows for assignee=5) + Filter status + Filter due_at + Sort
-- Estimated: ~200ms (filter hang ngan row tren heap)

-- v2: composite assignee + status
CREATE INDEX ON tasks(assignee_id, status);
-- Plan: Index Scan narrow assignee+status, then Filter due_at + Sort due_at
-- Estimated: ~30ms (it row hom nhung van can sort)

-- v3: composite full (equality + range, ORDER BY aligned)
CREATE INDEX ON tasks(assignee_id, status, due_at);
-- Plan: Index Scan narrow all 3, Sort skipped (due_at sorted in index)
-- Estimated: ~5ms (no sort step)

-- v4: voi INCLUDE - Index Only Scan
CREATE INDEX ON tasks(assignee_id, status, due_at) INCLUDE (id, title);
-- Plan: Index Only Scan - no heap fetch, sort skipped
-- Estimated: ~1ms (pure index read)

Module 5 bài 5 của khoá này sẽ measure 4 version với EXPLAIN ANALYZE thực tế và so sánh Buffers, actual time, Heap Fetches.

10. Deep Dive — Composite index

11. Liên kết khoá học khác

• Khoá Thuật toán — bài 07.7 B-tree & B+tree — leaf chain ordering trong B+tree giải thích vì sao leftmost prefix rule tồn tại: sort theo concat key, bỏ qua column đầu là mất định hướng trong tree.

12. Tóm tắt

• Composite (a, b, c) sort theo a → b trong group a → c trong group (a, b).
• Leftmost prefix rule: WHERE phải bao gồm column 1; có thể thêm column 2, 3 liên tục — bỏ qua column 1 thì index không dùng được.
• Equality column đặt trước range column trong index — range column "ngắt" tree navigation.
• INCLUDE column stored at leaf, không tham gia sort — cover SELECT column cho Index Only Scan (PG 11+).
• ORDER BY trùng range column cuối → planner skip Sort node.
• 2 query có leftmost prefix khác nhau → cần 2 index hoặc đổi thứ tự column với tradeoff rõ ràng.
• PG không có index skip scan native — workaround: tạo index thứ 2 với column order phù hợp.
• Forward: Module 5 bài 5 của khoá này (mini-challenge measure 4 index version với EXPLAIN thực tế), Module 7 của khoá này (EXPLAIN deep dive — cost model, planner statistics).

13. Tự kiểm tra

Bài tiếp theo: Specialized GIN/BRIN/partial/expression index