SQL 6 — Index & Tối ưu truy vấn

Một truy vấn có thể chạy trong 3 mili-giây hoặc 30 giây — cùng dữ liệu, cùng kết quả, chỉ khác cách database đi tìm dữ liệu. Khác biệt đó hầu hết nằm ở hai chữ: index (chỉ mục) và cách bạn viết câu truy vấn để tận dụng nó.

Bài này đi từ "index là cái gì" đến "vì sao nó nhanh", "khi nào nó vô dụng", và cách đọc EXPLAIN để tự mình kiểm chứng thay vì đoán mò. Trọng tâm là tối ưu: hiểu nguyên lý rồi áp dụng vào mẫu thực tế.

Index là gì và vì sao nó nhanh

Hãy tưởng tượng bảng accounts có 10 triệu dòng và bạn muốn tìm tài khoản có account_number = 'ACC-9921'. Không có index, database không còn cách nào khác ngoài đọc tuần tự (sequential scan): mở từng dòng, so sánh, bỏ qua hoặc giữ lại — cho đến hết 10 triệu dòng. Đây là độ phức tạp O(n).

Index giải quyết vấn đề này giống hệt danh bạ điện thoại. Danh bạ không lưu người theo thứ tự bạn quen biết họ; nó sắp xếp theo tên (A → Z). Muốn tìm "Nguyễn Văn An", bạn không đọc từ trang đầu — bạn lật đến vùng chữ N, rồi Ng, rồi thu hẹp dần. Vài lần lật là tìm ra. Đó là tìm kiếm O(log n).

Index trong database là một cấu trúc dữ liệu sắp xếp riêng, lưu giá trị của (các) cột cùng với con trỏ tới vị trí dòng thật trong bảng. Database tra index trước, lấy con trỏ, rồi nhảy thẳng tới dòng cần — không phải quét toàn bảng.

Cấu trúc B-Tree

Index mặc định trong hầu hết database (PostgreSQL, MySQL/InnoDB, SQL Server, Oracle) là B-Tree (Balanced Tree, cụ thể thường là B+Tree). Đây là một cây nhiều nhánh, luôn cân bằng: mọi nhánh từ gốc xuống lá đều có cùng độ sâu.

Cách nó hoạt động khi tìm giá trị 55:

1. Bắt đầu ở nút gốc [40 | 80]. Vì 40 ≤ 55 < 80, đi xuống nhánh giữa.
2. Đến nút [55 | 70], tiếp tục đi xuống vùng chứa 55.
3. Đến nút lá, tìm thấy 55 cùng con trỏ tới dòng thật.

Vài điểm cốt lõi:

• Độ sâu rất thấp. Mỗi nút chứa hàng trăm khoá. Một B-Tree 3-4 tầng đã đủ index cho hàng trăm triệu dòng. Vì thế tra cứu chỉ tốn vài lần đọc trang đĩa — O(log n) với cơ số rất lớn.
• Lá được liên kết kép (trong B+Tree). Các giá trị ở tầng lá nối vớ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 cho range scan (BETWEEN, >, <, >=) và ORDER BY — chỉ cần tìm điểm bắt đầu rồi đi dọc lá.
• Tự cân bằng. Khi insert/delete, cây tách hoặc gộp nút để giữ độ sâu đồng đều, đảm bảo hiệu năng ổn định.

Các loại index

Giải thích nhanh các loại đáng chú ý:

• Hash index chỉ tốt cho so sánh bằng tuyệt đối (=). Nó không hỗ trợ >, <, hay ORDER BY vì băm phá vỡ thứ tự. Trong thực tế ít dùng vì B-Tree vừa đủ nhanh cho = vừa làm thêm được range.
• Composite index đánh trên nhiều cột, ví dụ (account_id, created_at). Cực hữu ích nhưng phụ thuộc thứ tự cột — sẽ bàn kỹ ở cuối bài.
• Partial index chỉ index những dòng thoả một điều kiện, ví dụ WHERE status = 'active'. Nếu 95% truy vấn chỉ quan tâm dòng active, index này nhỏ hơn và nhanh hơn nhiều.
• Covering index chứa luôn các cột mà query cần đọc (qua INCLUDE trong PostgreSQL/SQL Server). Khi đó database trả lời hoàn toàn từ index — gọi là index-only scan, không cần lật về bảng.

Khi nào index KHÔNG được dùng

Đây là phần quan trọng nhất mà nhiều người bỏ qua: tạo index không bảo đảm nó được dùng. Optimizer chỉ dùng index khi câu truy vấn cho phép. Các tình huống index bị "vô hiệu hoá":

1. Bọc hàm quanh cột được index

-- Index trên created_at KHÔNG dùng được:
WHERE EXTRACT(YEAR FROM created_at) = 2026

-- Viết lại để index dùng được (SARGable):
WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'

Khi cột bị bọc trong hàm (EXTRACT, LOWER, UPPER, phép tính...), giá trị trong index không còn khớp với biểu thức nữa, nên database phải tính hàm trên từng dòng → quét toàn bảng. (Cách cứu: viết lại điều kiện, hoặc tạo expression index trên chính LOWER(email).)

2. LIKE với ký tự đại diện đứng đầu

WHERE name LIKE 'Nguyen%'   -- DÙNG được index (prefix cố định)
WHERE name LIKE '%Nguyen'   -- KHÔNG dùng được (mở đầu là %)
WHERE name LIKE '%Nguyen%'  -- KHÔNG dùng được

B-Tree sắp theo thứ tự từ trái sang. Có tiền tố cố định thì thu hẹp được vùng tìm; bắt đầu bằng % thì không biết bắt đầu từ đâu → phải quét. (Tìm kiếm chứa-chuỗi cần công cụ khác như full-text index hoặc trigram.)

3. Kiểu dữ liệu không khớp (implicit cast)

-- account_number là VARCHAR nhưng so với số:
WHERE account_number = 9921   -- có thể ép kiểu ngầm → bỏ qua index
WHERE account_number = '9921' -- đúng kiểu → dùng index

Ép kiểu ngầm khiến database phải convert cột trước khi so sánh, tương đương bọc hàm lên cột.

4. Cột có độ chọn lọc thấp

Nếu cột gender chỉ có 2 giá trị và mỗi giá trị chiếm ~50% bảng, optimizer thường cố tình bỏ index vì quét tuần tự còn rẻ hơn (lý do sẽ rõ ở phần selectivity).

Đánh đổi của index

Index không miễn phí. Phải hiểu cái giá để không "rải index khắp nơi":

• Đọc nhanh, ghi chậm. Mỗi INSERT, UPDATE (lên cột được index), DELETE đều phải cập nhật mọi index liên quan. Bảng có 8 index thì mỗi lần insert là 1 ghi bảng + 8 ghi index.
• Tốn dung lượng. Index là bản sao sắp xếp của dữ liệu cột + con trỏ. Nhiều index có thể chiếm dung lượng ngang hoặc hơn dữ liệu gốc.
• Tốn bộ nhớ & bảo trì. Index cạnh tranh RAM (buffer cache) và cần được giữ "khoẻ" (vacuum/rebuild khi phân mảnh).

Nguyên tắc: index cho cột hay xuất hiện trong WHERE, JOIN, ORDER BY và có độ chọn lọc cao; tránh index thừa, trùng lặp, hoặc trên bảng ghi cực nặng mà ít đọc.

Selectivity và Cardinality

Hai khái niệm này quyết định optimizer có thèm dùng index hay không.

• Cardinality: số lượng giá trị phân biệt trong cột. email có cardinality cao (gần như mỗi dòng một giá trị); status có cardinality thấp (vài giá trị).
• Selectivity (độ chọn lọc): tỷ lệ dòng mà một điều kiện lọc ra. selectivity = số dòng phân biệt / tổng số dòng. Càng gần 1 (lọc ra ít dòng) → index càng đáng dùng.

Vì sao điều này quan trọng? Truy index rồi nhảy về bảng để lấy dòng (random I/O) tốn kém theo từng dòng. Nếu điều kiện trả về 90% bảng, làm việc đó 9 triệu lần còn chậm hơn đọc tuần tự 10 triệu dòng một mạch (sequential I/O rẻ hơn random I/O nhiều). Vì thế:

Index hiệu quả nhất khi lọc ra một phần nhỏ của bảng. Lọc ra phần lớn bảng → seq scan thắng.

Đây là lý do optimizer đôi khi "phớt lờ" index bạn vừa tạo — và nó thường đúng.

Đọc EXPLAIN và EXPLAIN ANALYZE

EXPLAIN cho bạn xem kế hoạch thực thi (execution plan) mà optimizer dự định dùng — không chạy thật. EXPLAIN ANALYZE chạy thật và báo cáo thời gian + số dòng thực tế. Cả hai đều an toàn với SELECT (read-only).

▶ Chạy được trong SQL Builder

EXPLAIN
SELECT id, balance
FROM accounts
WHERE account_no = 'ACC-9921';

Một kế hoạch điển hình của PostgreSQL:

Index Scan using idx_accounts_number on accounts  (cost=0.42..8.44 rows=1 width=20)
  Index Cond: (account_number = 'ACC-9921'::text)

Cách đọc các con số và thuật ngữ:

• Seq Scan vs Index Scan: Seq Scan = quét toàn bảng; Index Scan = đi qua index rồi lật về bảng; Index Only Scan = trả lời hoàn toàn từ index (covering). Bitmap Heap Scan = dùng index gom nhiều dòng rồi đọc bảng theo lô (tốt khi trả về số dòng trung bình).
• cost=0.42..8.44: hai số là chi phí khởi động (tới dòng đầu tiên) và chi phí tổng (tới dòng cuối). Đơn vị là ước lượng tương đối, không phải mili-giây. Optimizer chọn kế hoạch có cost tổng nhỏ nhất.
• rows=1: số dòng ước lượng trả về. Khi chạy EXPLAIN ANALYZE, bạn sẽ thấy thêm actual rows. Nếu ước lượng lệch xa thực tế (vd ước 1 nhưng thực 50000), đó là dấu hiệu statistics lỗi thời → cần ANALYZE.
• width=20: kích thước trung bình mỗi dòng (byte).

So sánh kiểu JOIN trong kế hoạch

Khi nối bảng, optimizer chọn một trong các thuật toán:

• Nested Loop: với mỗi dòng bảng ngoài, tra bảng trong (lý tưởng khi bảng trong nhỏ hoặc có index hỗ trợ điều kiện join). Tốt cho kết quả ít dòng.
• Hash Join: xây bảng băm từ bảng nhỏ hơn rồi quét bảng lớn dò vào. Tốt cho join hai bảng lớn không có index phù hợp, điều kiện =.
• Merge Join: cả hai phía đã sắp theo khoá join thì "khoá kéo" hai luồng. Tốt khi dữ liệu đã sắp sẵn (vd nhờ index).

Nhìn kế hoạch để biết nó chọn cái gì:

▶ Chạy được trong SQL Builder

EXPLAIN ANALYZE
SELECT a.account_no, COUNT(t.id) AS so_giao_dich, SUM(t.amount) AS tong_tien
FROM accounts a
JOIN transactions t ON t.account_id = a.id
WHERE t.created_at >= '2026-01-01'
GROUP BY a.account_no;

Nếu thấy Seq Scan on transactions kèm actual rows lớn và thời gian cao, đó là ứng viên cần một index trên transactions(created_at) hoặc composite (account_id, created_at).

Quy trình tối ưu tuần tự dòng optimizer:

Statistics và ANALYZE

Optimizer ra quyết định dựa trên statistics — bảng thống kê về phân bố dữ liệu (số dòng, cardinality từng cột, histogram giá trị). Nếu thống kê cũ (vd sau khi import 5 triệu dòng mới nhưng chưa cập nhật), optimizer ước lượng sai → chọn kế hoạch tệ.

-- Cập nhật thống kê cho một bảng (minh hoạ, không chạy trong sandbox):
ANALYZE transactions;

PostgreSQL thường tự chạy autovacuum/auto-analyze, nhưng sau khi nạp dữ liệu lớn hoặc thấy EXPLAIN ANALYZE lệch ước lượng nhiều, hãy ANALYZE thủ công. Trong MySQL là ANALYZE TABLE.

Composite index và leftmost prefix

Đây là cái bẫy phổ biến nhất. Giả sử có index:

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

Index này sắp dữ liệu theo account_id trước, rồi mới đến created_at trong mỗi nhóm account_id — y như danh bạ sắp theo Họ rồi mới đến Tên.

Quy tắc leftmost prefix (tiền tố trái): index composite chỉ dùng được khi truy vấn lọc theo các cột từ trái sang, liên tục:

Tương tự danh bạ: tìm theo "Họ" rất nhanh; tìm chỉ theo "Tên" (bỏ qua Họ) thì danh bạ vô dụng vì các tên rải rác khắp mọi họ.

Hệ quả thực tế: thứ tự cột trong composite index phải đặt cột hay lọc bằng = lên trước, cột lọc range/sort xuống sau. Nếu cần cả hai chiều truy vấn (đôi khi lọc theo created_at đơn lẻ), có thể phải tạo index thứ hai.

Các mẫu tối ưu truy vấn

SARGable predicate

SARGable = "Search ARGument-able" — điều kiện viết sao cho index dùng được. Nguyên tắc: để cột đứng một mình một vế, đừng bọc hàm hay tính toán lên nó (xem lại phần "khi nào index không dùng").

Tránh SELECT *

SELECT * kéo mọi cột, làm tăng I/O, băng thông, và phá hỏng index-only scan (nếu lấy cột không nằm trong index, database buộc phải lật về bảng). Chỉ chọn cột cần.

Phân trang: Keyset thay vì OFFSET

OFFSET tệ dần khi trang lớn vì database vẫn phải đọc rồi bỏ đi toàn bộ dòng trước offset:

-- Chậm ở trang sâu: vẫn quét 100000 dòng trước rồi bỏ
SELECT * FROM transactions ORDER BY created_at LIMIT 20 OFFSET 100000;

-- Keyset pagination: nhảy thẳng nhờ index, O(log n)
SELECT * FROM transactions
WHERE created_at < '2026-03-01 10:00:00'   -- mốc cuối của trang trước
ORDER BY created_at DESC
LIMIT 20;

Keyset (còn gọi seek method) dùng giá trị cuối của trang trước làm mốc, tận dụng index để "seek" thẳng tới điểm đó — thời gian không đổi dù ở trang 1 hay trang 10000.

Tránh N+1 query

N+1 xảy ra khi code lấy danh sách N tài khoản (1 query) rồi lặp từng tài khoản gọi thêm 1 query lấy giao dịch (N query nữa). Tổng N+1 vòng tới database — thảm hoạ về latency. Thay bằng một JOIN hoặc WHERE account_id IN (...):

▶ Chạy được trong SQL Builder

SELECT a.account_no, t.id AS transaction_id, t.amount, t.created_at
FROM accounts a
JOIN transactions t ON t.account_id = a.id
WHERE a.id IN (1, 2, 3, 4, 5)
ORDER BY a.account_no, t.created_at DESC;

Checklist mẹo tối ưu

• Index cột dùng trong WHERE, JOIN, ORDER BY — ưu tiên cột độ chọn lọc cao.
• Viết điều kiện SARGable: cột đứng riêng một vế, không bọc hàm, không tính toán.
• Tránh ép kiểu ngầm — so sánh đúng kiểu dữ liệu ('9921' thay vì 9921 cho cột text).
• Với composite index, tuân thủ leftmost prefix; đặt cột lọc = trước, range/sort sau.
• Không SELECT *; chỉ lấy cột cần để mở đường cho index-only scan.
• Dùng keyset pagination cho trang sâu thay vì OFFSET lớn.
• Gộp N+1 thành một JOIN / IN.
• Đừng over-index bảng ghi nặng; xoá index trùng/thừa.
• Dùng EXPLAIN ANALYZE để kiểm chứng chứ không đoán; soi lệch ước lượng vs thực tế.
• Chạy ANALYZE sau khi nạp dữ liệu lớn để thống kê chính xác.
• Cân nhắc partial index khi đa số query lọc cùng một điều kiện.

Tóm tắt

Index là cấu trúc sắp xếp riêng (thường là B-Tree) giúp database tìm dữ liệu theo O(log n) thay vì quét tuần tự O(n), giống cách danh bạ giúp tra tên nhanh. B-Tree phục vụ cả tìm điểm lẫn range/sort nhờ tầng lá liên kết. Có nhiều loại index (Hash, composite, partial, covering, unique), mỗi loại hợp một kiểu truy vấn. Quan trọng: index không tự động được dùng — bọc hàm lên cột, LIKE '%x', ép kiểu ngầm, hoặc cột chọn lọc thấp đều làm optimizer bỏ index. Index đánh đổi đọc-nhanh lấy ghi-chậm và dung lượng, nên chỉ index nơi cần. EXPLAIN/EXPLAIN ANALYZE là công cụ để kiểm chứng kế hoạch (seq vs index scan, cost, rows, kiểu join). Cuối cùng, viết truy vấn SARGable, tránh SELECT *, dùng keyset pagination, diệt N+1, giữ statistics tươi, và tôn trọng leftmost prefix của composite index.

Tự kiểm tra

1. Vì sao B-Tree cho phép tìm kiếm O(log n), và đặc điểm "tầng lá liên kết" giúp ích gì cho BETWEEN / ORDER BY?
2. Tại sao WHERE EXTRACT(YEAR FROM created_at) = 2026 không dùng được index, và viết lại thế nào cho SARGable?
3. Một cột có cardinality rất thấp (vd status 2 giá trị) — vì sao optimizer thường bỏ qua index trên nó? Liên hệ với khái niệm selectivity và random vs sequential I/O.
4. Với composite index (account_id, created_at), điều kiện WHERE created_at > '2026-01-01' (không có account_id) có dùng được index không? Giải thích bằng leftmost prefix.
5. Trong EXPLAIN ANALYZE, nếu rows (ước lượng) lệch xa actual rows, điều đó gợi ý vấn đề gì và bạn làm gì để khắc phục?
6. So sánh phân trang OFFSET 100000 với keyset pagination về chi phí — vì sao keyset không đổi theo độ sâu trang?

Đọc tiếp

SQL 7 — Transaction & ACID