Thứ Hai, bạn tạo index cho bảng orders có 5 triệu dòng. Query WHERE customer_id = ? từ 8 giây xuống 2ms. Merge PR, đi uống cà phê.
Thứ Sáu, sếp gọi: “INSERT mất 500ms, trước chỉ 10ms. Em thay đổi gì vậy hả?”
Bạn kiểm tra lại database: bảng giờ có 7 indexes. Mỗi INSERT phải cập nhật 8 cấu trúc (1 bảng + 7 cây B+Tree). Mỗi cây có thể split node, re-balance. 7 cây nhân lên = thảm họa write.
Bạn chợt nhân ra Index không phải “thêm cho chắc”. Index là sự đánh đổi. Bài này sẽ cho bạn thấy chính xác sự đánh đổi đó nằm ở đâu.
Mọi index lookup dù là tìm 1 email hay lọc 100.000 đơn hàng đều đi qua đúng 3 bước. Hiểu rõ từng bước giúp bạn dự đoán được khi nào index nhanh và khi nào nó trở thành gánh nặng.
Bước 1: Tree Traversal
Từ root node, database so sánh search key với các separator keys để chọn đường đi xuống. Mỗi tầng = 1 disk read. Cây cao 3-4 tầng = 3-4 disk reads. Bảng 10 triệu dòng vẫn chỉ 3-4 bước. Bước này luôn nhanh, O(log n), biết trước được tối đa là bao nhiêu.
Bước 2: Leaf Node Chain
Tại leaf node đầu tiên, database duyệt theo linked list sang các leaf tiếp theo để thu thập tất cả entries khớp. Primary Key lookup → dừng ngay (1 entry) nhưng nếu nó không phải Primary Key thì có thể khớp rất nhiều kết quả nữa → duyệt hàng ngàn leaf nodes. Chi phí phụ thuộc hoàn toàn vào số kết quả.
Bước 3: Table Access
Mỗi entry trong leaf chứa ROWID, con trỏ đến vị trí dòng trong bảng gốc (heap). Database phải nhảy đến heap lấy dữ liệu đầy đủ. Vấn đề: các dòng nằm rải rác trên disk → mỗi lần lấy = 1 random I/O. Đây là bước tốn kém nhất.
| Bước | Tên | Chi phí | Giới hạn? |
|---|---|---|---|
| 1 | Tree Traversal | O(log n) | Có, luôn nhanh (3-4 bước) |
| 2 | Leaf Node Chain | O(k): k = số match | Không, phụ thuộc kết quả |
| 3 | Table Access | O(k) × random I/O | Không, đây là "sát thủ" |
PostgreSQL EXPLAIN cho thấy rõ 3 bước này
Mỗi lần chạy EXPLAIN, PostgreSQL cho biết nó dùng chiến lược scan nào. Dưới đây là 3 chiến lược phổ biến nhất, cùng output thật để bạn nhận diện ngay.
Index Only Scan: Bước 1 + 2, bỏ bước 3
Cột email nằm sẵn trong index, database tìm đến leaf (bước 1), duyệt leaf chain nếu nhiều kết quả (bước 2), rồi trả dữ liệu ngay từ index. Bỏ hoàn toàn bước 3, không cần đọc bảng gốc.
Index Scan: Đầy đủ bước 1 + 2 + 3
Cùng index, cùng WHERE, nhưng SELECT * cần cột name, created_at... không có trong index. Buộc phải nhảy vào heap lấy dữ liệu (bước 3). Cost tăng từ 4.44 → 8.44, width từ 32 → 128, đó là chi phí của Table Access.
Bitmap Scan: Bước 3 được tối ưu thành sequential I/O
12,500 kết quả: Index Scan thường sẽ nhảy ngẫu nhiên 12,500 lần vào heap. PostgreSQL chuyển sang bitmap: Bitmap Index Scan quét index gom tất cả vị trí dòng → Bitmap Heap Scan đọc heap theo thứ tự page vật lý, biến random I/O thành sequential.
Đó là query optimizer, bộ não có trong mọi database. Mỗi khi bạn chạy một câu query, optimizer phân tích cấu trúc query, ước lượng số rows sẽ khớp dựa trên thống kê của bảng, rồi chọn chiến lược scan có chi phí thấp nhất. Ba loại scan ở trên không phải bạn chọn, optimizer tự quyết định. Và đôi khi, nó quyết định... bỏ qua index luôn.
“Index hỏng rồi, REBUILD thôi!” Có đúng không?
Khi một câu truy vấn dùng Index bỗng trở nên chậm chạp, phản xạ đầu tiên của nhiều Developer và DBA là: “Index dùng lâu bị hỏng rồi, cấu trúc lệch hết, phải đập đi xây lại Index thôi!”
Nhưng thực tế thì sao? B-Tree là cấu trúc tự cân bằng (Self-balancing). Dù bạn INSERT hay DELETE hàng tỷ lần, độ cao cây vẫn ổn định ở mức O(log n) - cấu trúc cây không bao giờ bị “lệch” hay “hỏng”. Điều có thể xảy ra là index bloat(index bị “phình” ra, lãng phí dung lượng): page splits (trang dữ liệu bị tách đôi khi chèn thêm) và dead tuples (các bản ghi cũ chưa được dọn dẹp, đặc biệt trong PostgreSQL do cơ chế MVCC) khiến các page bị thưa thớt, tốn I/O hơn cần thiết. Tuy nhiên, nguyên nhân phổ biến nhất khiến index chậm không phải do bloat, mà là do cách ổ đĩa đọc dữ liệu - cụ thể là vấn đề Random I/O mà ta sẽ phân tích ngay sau đây.
Nếu Index không hỏng, tại sao nó chậm? Câu trả lời nằm ở sự kết hợp của 2 nguyên liệu chết người:
Nguyên liệu 1: Cơn ác mộng “Chọn lọc kém” (Low Selectivity)
Hãy tưởng tượng bạn nhờ Index tìm những user có status = 'ACTIVE'. Vấn đề là: 80% user trong bảng 1 triệu dòng đều đang ACTIVE. Thay vì chỉ dẫn bạn đến một vị trí cụ thể, Index bắt bạn đi dọc theo chuỗi Linked List qua 800.000 entries. Bạn phải duyệt qua hàng ngàn Node lá liên tiếp. Đây là một cuộc hành xác, không phải tìm kiếm.
Nguyên liệu 2: Chiếc bẫy Random I/O (Table Access)
Khi nào optimizer bỏ qua index?
Query optimizer thông minh: nó ước tính số rows sẽ khớp dựa trên statistics. Nếu dự đoán >5-10% bảng sẽ khớp → nó chủ động chọn Full Table Scan thay vì dùng index. Đây KHÔNG phải bug, đây là quyết định đúng!
| Tình huống | Selectivity | Optimizer chọn |
|---|---|---|
| Tìm 1 user theo email | Rất cao | Index Scan |
| Tìm 10 orders theo customer_id | Cao | Index Scan |
| Tìm status='ACTIVE' (80% bảng) | Rất thấp | Full Table Scan |
| Tìm gender='M' (50% bảng) | Thấp | Full Table Scan |
Index nhanh khi: ít row khớp (high selectivity). Bước 2+3 gần như không dùng.
Index chậm khi: nhiều row khớp (low selectivity). Chi phí random I/O lớn hơn sequential scan.
Biểu đồ dưới đây cho thấy chi phí của 3 chiến lược scan thay đổi theo tỷ lệ dòng trả về. Chú ý điểm giao: Index Scan chỉ thắng khi tỷ lệ thấp.
Giả sử bạn có bảng transactions với 100 triệu dòng. Bạn đánh tới 12 indexes, query theo cột nào cũng nhanh, mọi thứ trông thật hoàn hảo. Nhưng rồi bạn nhận ra INSERT từ 5ms nhảy vọt lên 200ms. Đến ngày sale lớn, hàng đợi tràn ngập, timeout liên tục, hệ thống gần như đứng hình. Lúc này bạn ngồi lại rà soát, xóa bớt 8 indexes thừa, chỉ giữ đúng 4 cái thực sự cần thiết. INSERT lập tức về 15ms. Vậy bài học ở đây là gì? Index không hề miễn phí.
| Đọc (SELECT) | Ghi (INSERT/UPDATE/DELETE) | Disk Space | |
|---|---|---|---|
| 0 index | Chậm (Full Scan) | Nhanh nhất | Ít nhất |
| 2-3 index (hợp lý) | Nhanh | Chấp nhận được | Vừa phải |
| 10+ index (quá nhiều) | Nhanh | Rất chậm | Rất tốn |
WHERE, JOIN, hoặc ORDER BYthường xuyên. Đừng index “cho chắc”, hãy index “cho đúng”.Bài tập 1: Xây B-Tree (Interactive)
Cho tập dữ liệu: [5, 12, 18, 23, 27, 31, 35, 42, 48, 55, 60, 67] (12 entries), mỗi node chứa tối đa 3 entries.
Bài tập 2: Thực hành trên PostgreSQL
SQL Playground chỉ mở cho học viên đã mua khoá “SQL Nâng Cao”. Khi mua, bạn được chạy trực tiếp query trên PostgreSQL với dataset thật của bài học.
Trả lời các câu hỏi sau:
3 bước của Index Lookup là gì?
1) Tree Traversal (luôn nhanh, O(log n)). 2) Leaf Node Chain (duyệt kết quả). 3) Table Access (random I/O: bước tốn kém nhất).
Bức tranh toàn cảnh (cả 2 bài): Từ Full Table Scan → BST (thất bại trên disk) → B-Tree (nhét đầy page) → B+Tree (data ở leaf + linked list) → 3 bước Index Lookup → Khi nào index phản tác dụng → Trade-offs.
Còn nhớ câu query email 12 giây → 3ms ở đầu bài 1? Bây giờ bạn biết chính xác chuyện gì xảy ra trong 3ms đó: root node (đã nằm sẵn trong RAM) → 1-2 branch node → leaf node chứa email → theo ROWID về bảng gốc. Tổng cộng 2-3 lần đọc disk. Đó là sức mạnh của B+Tree.
Index không phải “thêm một cái gì đó”, bạn đang yêu cầu database xây nguyên một cây B+Tree mới, với hàng triệu node, được tinh chỉnh để mỗi lần đọc disk đều xứng đáng. Hiểu được điều này, bạn sẽ thiết kế schema tốt hơn, chọn Primary Key thông minh hơn, và debug những query chậm hiệu quả hơn.
WHERE email = ? khác gì WHERE last_name = ?? Tại sao cùng toán tử = mà một cái tốn 0.01ms, cái kia tốn 12ms? Bài 3 sẽ đi sâu vào Primary Key Lookup, Unique Scan vs Range Scan, và cách đọc EXPLAIN Plan để phân biệt, kỹ năng bạn sẽ dùng mỗi ngày khi debug slow queries.