Tối ưu 2 — Chỉ mục: B-tree, composite, covering, partial

Chỉ mục (index) là công cụ tăng tốc số một của mọi cơ sở dữ liệu quan hệ. Nhưng nó không phải "phép màu bật lên là nhanh": một index sai thứ tự cột thì planner phớt lờ, một index thừa làm chậm mọi lần ghi, và một index đúng có thể biến truy vấn 30 giây thành 3 mili-giây. Bài này giải thích index hoạt động thế nào và quan trọng hơn — khi nào dùng cái gì.

Trọng tâm là PostgreSQL, có nêu tương đương ở MySQL/Oracle. Nên nắm trước bài EXPLAIN, vì đó là công cụ duy nhất để kiểm chứng index có được dùng hay không thay vì đoán mò.

B-tree: vì sao tra cứu là O(log n)

Index mặc định của PostgreSQL (và của MySQL/InnoDB, Oracle, SQL Server) là B-tree — chính xác là biến thể B+Tree. Đây là cây tìm kiếm nhiều nhánh, luôn cân bằng: mọi đường đi từ gốc xuống lá có cùng độ sâu.

Hãy so với tra danh bạ sắp theo A→Z: muốn tìm "Nguyễn Văn An" bạn lật thẳng đến vùng N, rồi Ng, thu hẹp dần — vài lần lật là ra. B-tree làm đúng điều đó với cấu trúc phân tầng.

Tìm giá trị 55: từ gốc [40 | 80] thấy 40 ≤ 55 < 80 nên đi nhánh giữa; đến [55 | 70] đi tiếp xuống lá; ở lá tìm thấy 55 kèm con trỏ (TID — tuple identifier) tới vị trí dòng thật trong heap (bảng vật lý).

Ba điểm cốt lõi:

• Độ sâu rất thấp. Mỗi nút chứa hàng trăm khoá, nên B-tree 3–4 tầng đã đủ đánh chỉ mục hàng trăm triệu dòng. Tra cứu chỉ tốn vài lần đọc trang — O(log n) với cơ số rất lớn.
• Lá liên kết kép. Các giá trị ở tầng lá nối nhau theo thứ tự, nên ngoài tìm điểm (= 55), B-tree còn phục vụ cực tốt range scan (BETWEEN, >, <) và ORDER BY — tìm điểm đầu rồi đi dọc lá. Đây là lý do index có thể xoá được bước Sort trong plan.
• Tự cân bằng. Khi insert/delete, cây tách hoặc gộp nút để giữ độ sâu đồng đều.

Khi nào planner dùng index — chuyện của độ chọn lọc

Sai lầm phổ biến: nghĩ "có index thì luôn dùng index". Thực tế PostgreSQL chọn giữa Index Scan và Seq Scan dựa trên chi phí ước lượng, mà yếu tố quyết định là độ chọn lọc (selectivity) — phần trăm dòng khớp điều kiện.

Lý do: Index Scan tra index lấy con trỏ rồi nhảy tới heap đọc từng dòng — mỗi cú nhảy có thể là một random I/O. Nếu điều kiện khớp 60% số dòng, hàng triệu cú nhảy random còn đắt hơn đọc tuần tự cả bảng (sequential I/O rẻ hơn random I/O nhiều lần). Vậy nên:

• Điều kiện rất chọn lọc (khớp ít dòng, ví dụ tra một account_no) → Index Scan thắng.
• Điều kiện ít chọn lọc (khớp phần lớn bảng, ví dụ currency = 'VND' khi 95% là VND) → Seq Scan lại rẻ hơn, planner bỏ qua index dù nó tồn tại. Đây là hành vi đúng, không phải lỗi.

Chất lượng ước lượng này phụ thuộc thống kê do ANALYZE cập nhật. Thống kê cũ → ước lượng sai → chọn plan tệ (xem bài Bảo trì/VACUUM).

Lưu ý sandbox: dữ liệu mẫu trong bài này rất nhỏ (vài chục dòng). Với bảng nhỏ, đọc cả bảng chỉ tốn một trang, nên planner gần như luôn chọn Seq Scan dù bạn có tạo index. Điều đó không có nghĩa index vô dụng — chỉ là chi phí ở quy mô nhỏ không đủ để index thắng. Các plan Index Scan chỉ xuất hiện rõ trên dữ liệu lớn.

Composite index và quy tắc left-most prefix

Composite index (chỉ mục nhiều cột) đánh chỉ mục theo tuple có thứ tự, ví dụ (customer_id, created_at): một danh sách sắp trước theo customer_id, và trong cùng một customer_id thì sắp tiếp theo created_at.

Chính vì sắp lồng nhau như vậy, có quy tắc left-most prefix (tiền tố trái): index chỉ dùng hiệu quả khi truy vấn lọc theo một tiền tố liên tục tính từ cột trái nhất.

Với index (a, b, c):

Tương tự sổ danh bạ sắp theo (họ, tên): tra được "họ Nguyễn" hay "họ Nguyễn tên An", nhưng không tra nhanh được "mọi người tên An" — vì cùng tên An nằm rải rác khắp mọi họ.

Hệ quả thực tế:

• Cột lọc bằng (=) đặt trước, cột range đặt sau. Khi gặp cột range (>, <, BETWEEN), B-tree quét đến cột đó nhưng các cột đứng sau range không còn dùng để định vị nữa. Với WHERE a = ? AND b > ? AND c = ?, index (a, b, c) lọc được a và b, nhưng c chỉ được lọc lại trên tập kết quả.
• Cột dùng cho ORDER BY nên khớp thứ tự và chiều trong index để tận dụng lá liên kết, tránh bước Sort.
• Một composite (a, b) thay thế được index đơn (a) cho phần lớn truy vấn lọc theo a — tránh tạo cả hai (index dư thừa, xem phần "Cái giá").

Điểm này áp dụng gần như y hệt ở MySQL/InnoDB và Oracle — quy tắc left-most prefix là chuẩn chung của B-tree.

Covering index / INCLUDE → Index-Only Scan

Index Scan thường gồm hai bước: (1) tra index lấy con trỏ, (2) nhảy vào heap đọc các cột còn lại. Bước (2) là phần đắt (random I/O).

Index-Only Scan bỏ hẳn bước (2): nếu mọi cột truy vấn cần (cả SELECT lẫn WHERE) đều có sẵn trong index, PostgreSQL trả kết quả thẳng từ index, không chạm heap — một trong những tối ưu mạnh nhất cho truy vấn đọc nhiều.

PostgreSQL 11+ có mệnh đề INCLUDE để tạo covering index: đưa thêm cột vào index như "payload" chỉ để trả về, không tham gia vào cây tìm kiếm/sắp xếp. Ví dụ minh hoạ (không chạy trong sandbox):

-- (minh hoạ, không chạy trong sandbox)
-- Truy vấn: SELECT balance FROM accounts WHERE customer_id = ?;
CREATE INDEX idx_acc_cust_incl
  ON accounts (customer_id) INCLUDE (balance);

Ở đây customer_id là khoá tìm kiếm, còn balance là cột include. Truy vấn SELECT balance FROM accounts WHERE customer_id = ? giờ có thể chạy Index-Only Scan: tìm theo customer_id trong cây, đọc balance ngay tại lá.

Điều kiện quan trọng — visibility map. PostgreSQL dùng MVCC, và thông tin "dòng này có hiển thị với giao dịch hiện tại không" chỉ nằm ở heap, không nằm trong index. PostgreSQL duy trì một visibility map đánh dấu trang nào "toàn dòng hiển thị với mọi giao dịch". Index-Only Scan chỉ tránh chạm heap cho dòng nằm trên trang đã đánh dấu all-visible; trang chưa đánh dấu thì vẫn phải kiểm tra heap.

Hệ quả: Index-Only Scan chỉ thật sự "only-index" khi bảng được VACUUM đủ thường xuyên để cập nhật visibility map. Bảng vừa ghi ồ ạt mà chưa vacuum thì plan sẽ có Heap Fetches lớn — vẫn phải chạm heap nhiều. Đây là liên hệ trực tiếp giữa tối ưu đọc và bảo trì.

Partial index và Expression index

Đây là hai kiểu index "thông minh" mà nhiều người bỏ quên.

Partial index — chỉ đánh chỉ mục phần cần

Partial index có mệnh đề WHERE: chỉ index những dòng thoả điều kiện đó. Nó nhỏ hơn, nhanh hơn, và rẻ hơn khi ghi (dòng không thoả điều kiện thì không đụng tới index).

Kịch bản kinh điển: cột trạng thái lệch phân bố. Giả sử 98% giao dịch có kind = 'completed', chỉ 2% là 'pending', và toàn bộ báo cáo vận hành chỉ quan tâm 'pending':

-- (minh hoạ, không chạy trong sandbox)
CREATE INDEX idx_txn_pending
  ON transactions (created_at)
  WHERE kind = 'pending';

Index này chỉ chứa 2% số dòng, cực gọn, và planner dùng nó cho mọi truy vấn có WHERE kind = 'pending' AND ... (điều kiện truy vấn phải bao hàm điều kiện của partial index). Một ứng dụng phổ biến khác: WHERE deleted_at IS NULL để chỉ index các dòng chưa xoá mềm.

Expression index — index trên kết quả hàm

B-tree đánh chỉ mục giá trị cột nguyên bản. Nếu truy vấn lọc theo kết quả một hàm thì index cột thường không dùng được. Ví dụ tìm theo tên không phân biệt hoa/thường:

-- Truy vấn dạng: WHERE lower(full_name) = 'nguyen van an'

Index thường trên full_name lưu 'Nguyen Van An', 'NGUYEN VAN AN'... — không có khoá 'nguyen van an' để tra. Planner buộc phải Seq Scan rồi tính lower() từng dòng. Giải pháp là expression index (index trên biểu thức):

-- (minh hoạ, không chạy trong sandbox)
CREATE INDEX idx_cust_lower_name
  ON customers (lower(full_name));

Giờ index lưu sẵn giá trị đã lower(), và WHERE lower(full_name) = ? khớp trực tiếp — với điều kiện biểu thức trong truy vấn giống hệt biểu thức trong index. Hay dùng expression index cho: lower()/upper() (tìm không phân biệt hoa thường), date_trunc() (gom theo ngày/tháng), hoặc index trên một khoá bên trong cột JSON.

Các loại index khác và khi nào dùng

B-tree phù hợp cho so sánh có thứ tự (=, <, >, range, ORDER BY), nhưng PostgreSQL còn nhiều loại chuyên dụng:

• GIN (Generalized Inverted Index). Cho dữ liệu "một dòng chứa nhiều phần tử": jsonb, mảng, full-text (tsvector). GIN lập chỉ mục ngược từ từng phần tử/khoá về các dòng chứa nó. Dùng khi cần @> (chứa) trên jsonb, tìm phần tử trong mảng, hay tìm kiếm văn bản. Ghi chậm hơn B-tree nhưng truy vấn chứa/khớp cực nhanh.
• GiST (Generalized Search Tree). Khung index cho dữ liệu không gian và phạm vi: kiểu hình học (PostGIS), kiểu range (tstzrange), tìm lân cận. Dùng cho "điểm nào trong bán kính X", "khoảng thời gian nào giao nhau".
• BRIN (Block Range Index). Cực nhỏ, cho bảng rất lớn mà dữ liệu đã sắp theo thứ tự vật lý tương quan với cột — điển hình là cột thời gian trong bảng append-only. BRIN chỉ lưu min/max từng khối trang nên bé hơn B-tree hàng nghìn lần, đổi lại kém chọn lọc hơn. Hợp cho created_at trên bảng transactions khổng lồ chỉ chèn thêm.
• Hash. Chỉ phục vụ bằng (=), không range/sort. Từ PostgreSQL 10 mới ghi WAL đầy đủ (an toàn crash). Thực tế B-tree vẫn thường được chọn cho = vì linh hoạt hơn, nên Hash ít khi cần.

Quy tắc nhanh: mặc định là B-tree; jsonb/mảng/full-text dùng GIN; không gian/range dùng GiST; bảng khổng lồ append-only theo thời gian dùng BRIN.

Cái giá của chỉ mục

Index không miễn phí. Mỗi index bạn thêm là một cái giá phải trả ở phía ghi và dung lượng:

• Chậm INSERT/UPDATE/DELETE. Mỗi lần chèn một dòng, PostgreSQL phải chèn khoá vào mọi index của bảng. Bảng 6 index nghĩa là mỗi INSERT = 1 lần ghi heap + 6 lần cập nhật cây. Đây là write amplification — một thao tác logic thành nhiều thao tác vật lý.
• Tốn dung lượng. Index chiếm ổ đĩa và bộ nhớ đệm; index to đẩy dữ liệu nóng ra khỏi cache.
• Index không dùng → nên bỏ. Index chẳng ai dùng vẫn phải cập nhật mỗi lần ghi — thuần tuý là gánh nặng. Định kỳ rà pg_stat_user_indexes tìm index có idx_scan = 0 và cân nhắc DROP.

HOT updates (Heap-Only Tuple). Một tối ưu quan trọng: nếu UPDATE không đụng tới cột nào được đánh index và trang heap còn chỗ trống, PostgreSQL tạo phiên bản mới ngay trong cùng trang và không cập nhật index nào — index cũ vẫn trỏ đúng qua chuỗi HOT, rẻ hơn nhiều. Hệ quả: đừng đánh index lên cột bị update liên tục (cột đếm, "cập nhật lần cuối"...) nếu không thật cần, vì phá vỡ HOT và tăng cả chi phí ghi lẫn bloat.

Quy tắc gói gọn: index tăng tốc đọc, làm chậm ghi. Hãy đánh index cho những truy vấn thật sự chạy thường xuyên, không phải "đánh cho chắc".

Sandbox: kiểm chứng bằng EXPLAIN

Trên schema mẫu (customers, accounts, transactions, employees, departments), ta có thể chạy một câu EXPLAIN để xem planner chọn gì. Nhớ rằng dữ liệu rất nhỏ nên plan gần như luôn là Seq Scan — điều cần quan sát là cách đọc plan, không phải "phải ra Index Scan".

-- ▶ Chạy được trong SQL Builder (dữ liệu nhỏ → nhiều khả năng Seq Scan)
EXPLAIN
SELECT a.account_no, a.balance
FROM accounts a
WHERE a.customer_id = 1;

Trên bảng nhỏ bạn sẽ thấy Seq Scan on accounts kèm Filter: (customer_id = 1). Ở quy mô lớn, với index (customer_id) INCLUDE (balance), chính truy vấn này sẽ thành Index Only Scan.

-- ▶ Chạy được trong SQL Builder (dữ liệu nhỏ → nhiều khả năng Seq Scan)
EXPLAIN
SELECT t.id, t.amount, t.created_at
FROM transactions t
WHERE t.account_id = 1
ORDER BY t.created_at DESC;

Quan sát: có xuất hiện node Sort không? Ở quy mô lớn, một composite index (account_id, created_at DESC) sẽ vừa lọc account_id vừa trả sẵn thứ tự, xoá luôn bước Sort — minh hoạ trực tiếp cho phần composite + ORDER BY ở trên.

Use case thực tế: tăng tốc báo cáo bằng thứ tự cột đúng

Bối cảnh: báo cáo "sao kê một tài khoản trong khoảng thời gian" chạy hàng nghìn lần mỗi ngày:

-- Truy vấn báo cáo (dạng thật, không phải sandbox)
SELECT id, amount, kind, created_at
FROM transactions
WHERE account_id = :acc
  AND created_at >= :from
  AND created_at <  :to
ORDER BY created_at DESC;

Trước tối ưu: không có index phù hợp → Seq Scan toàn bảng transactions (giả sử 200 triệu dòng) + Sort. Chậm vài giây, ăn CPU/I/O.

Phân tích thứ tự cột:

• account_id lọc bằng (=) → đặt trước để định vị chính xác một tài khoản.
• created_at dùng range → đặt sau cột bằng; B-tree quét được một dải liên tục trong tài khoản đó.
• ORDER BY created_at DESC → cho chiều DESC vào index để đi dọc lá mà không cần Sort.

Index đúng (minh hoạ):

-- (minh hoạ, không chạy trong sandbox)
CREATE INDEX idx_txn_acc_time
  ON transactions (account_id, created_at DESC);

Sau tối ưu, plan trở thành Index Scan trên idx_txn_acc_time: nhảy tới đúng account_id, đi dọc dải created_at trong khoảng cần, đọc sẵn theo thứ tự giảm dần — không Seq Scan, không Sort. Từ vài giây xuống vài mili-giây.

Nếu báo cáo chỉ cần thêm amount/kind, có thể nâng lên covering index để đạt Index-Only Scan:

-- (minh hoạ, không chạy trong sandbox)
CREATE INDEX idx_txn_acc_time_incl
  ON transactions (account_id, created_at DESC) INCLUDE (amount, kind);

Đảo thứ tự cột thì sao? Nếu lỡ tạo (created_at, account_id), index này không phục vụ tốt truy vấn trên — vì cột trái nhất created_at là range, index chỉ thu hẹp được theo khoảng thời gian rồi phải lọc account_id trên toàn bộ giao dịch của mọi tài khoản trong khoảng đó. Đây chính là bài học left-most prefix + "range đặt sau bằng".

Chẩn đoán index

Bốn câu hỏi thường trực khi tối ưu:

1. Index có được dùng không? Chạy EXPLAIN (ANALYZE, BUFFERS) trên truy vấn thật. Index Scan/Index Only Scan là tốt; Seq Scan + Filter trên bảng lớn là dấu hiệu thiếu/sai index. Với Index-Only Scan, để ý Heap Fetches cao — visibility map chưa cập nhật (cần vacuum).
2. Index có thừa/trùng không? (a, b) khiến (a) gần như dư thừa. Rà pg_stat_user_indexes (cột idx_scan) tìm index không ai dùng và cân nhắc bỏ.
3. Truy vấn có "vô hiệu hoá" index không? Bọc cột trong hàm (WHERE lower(col)=...), so sánh khác kiểu (ép kiểu ngầm), hay OR lan man có thể khiến planner không dùng được index — chi tiết ở bài Viết lại truy vấn.
4. Index có bị phình (bloat) không? Sau nhiều update/delete, index tích rác và to bất thường, làm chậm cả đọc lẫn ghi. Cách đo và REINDEX ở bài Bảo trì/VACUUM.

Ghi nhớ

• B-tree là mặc định, tra cứu O(log n), phục vụ tốt cả =, range và ORDER BY. Planner chỉ chọn index khi điều kiện đủ chọn lọc; ít chọn lọc thì Seq Scan rẻ hơn — đó là quyết định đúng.
• Composite index: theo quy tắc left-most prefix, thứ tự cột quyết định query nào dùng được. Cột lọc bằng đặt trước, cột range đặt sau, cho chiều ORDER BY vào index để tránh Sort.
• Covering/INCLUDE cho Index-Only Scan (không chạm heap) — nhưng chỉ hiệu quả khi visibility map được cập nhật (vacuum đều).
• Partial index (WHERE ...) cho dữ liệu lệch phân bố; expression index cho WHERE lower(col)=... và các hàm khác.
• Ngoài B-tree: GIN (jsonb/mảng/full-text), GiST (không gian/range), BRIN (bảng lớn append-only theo thời gian), Hash (=, ít dùng).
• Index tăng tốc đọc, làm chậm ghi (write amplification) và tốn dung lượng; đừng index cột bị update liên tục (giữ HOT updates); index không dùng thì bỏ.
• Luôn kiểm chứng bằng EXPLAIN, đừng đoán.

Đọc tiếp: EXPLAIN — đọc kế hoạch thực thi · Viết lại truy vấn · Bảo trì & VACUUM.