Câu hỏi phỏng vấn SQL index (B-tree, composite, covering)
Bộ đề này harvest từ khoá SQL & Database và PostgreSQL Internals — mỗi câu link bài học đào sâu cơ chế, để bạn giải thích được vì sao chứ không chỉ đọc thuộc đáp án.
01
Vì sao index làm truy vấn nhanh hơn? Cơ chế thật sự là gì?
JuniorHeap — nơi lưu row thật — không có thứ tự: row được ghi vào bất kỳ page nào còn chỗ, nên không có index thì database phải quét tuần tự mọi page từ đầu đến cuối. Index là một cấu trúc riêng đã sắp xếp theo cột được index, mỗi leaf entry giữ giá trị cột cộng pointer
(heap_page, offset)trỏ về row gốc. Tra một khoá chỉ cần đi từ root xuống leaf theo O(log N) rồi fetch đúng một heap page — với bảng 10 triệu row đó là khoảng 4 page đọc (3 node B-tree cộng 1 heap page) thay vì hàng chục nghìn page. Cùng một queryWHERE id = 12345vì thế chạy 800ms khi full scan và 0.2ms khi có index. Hầu hết database tự tạo B-tree index choPRIMARY KEYvàUNIQUE, còn cột khác phảiCREATE INDEXtường minh.Dừng ở ví von 'index như mục lục sách' mà không nói được index lưu gì (giá trị đã sắp xếp cộng pointer về heap) và cái giá phải trả lúc ghi.02
Index làm chậm ghi như thế nào? Đánh nhiều index có sao không?
JuniorMỗi index là một cấu trúc riêng phải được cập nhật ngay trong thao tác ghi: bảng có 7 index thì mỗi INSERT phải sửa 7 B-tree, chưa kể storage phồng lên khoảng 2–5 lần dữ liệu. Với B-tree, chi phí không chỉ là thêm một entry — nếu leaf page đã đầy, engine phải page split: cấp page mới, chuyển 50% entry sang, cập nhật pointer ở node cha, nên một insert logic thành hai page write. Vì vậy bảng write-heavy kiểu
logs,events,metricsphải tối thiểu hoá số index, còn bảng read-heavy như catalog sản phẩm thì chịu được nhiều index hơn. Nguyên tắc là đo query chậm trước rồi mới thêm index, và sau khi chạy thật đủ lâu thì kiểm tra index nào chưa từng được dùng để drop.Trả lời chung chung 'index tốn thêm bộ nhớ' mà không nói được page split và việc mỗi index là một B-tree phải sửa trên mọi INSERT/UPDATE/DELETE.03
Phân biệt full scan, index scan và index-only scan.
JuniorFull scan (sequential scan) đọc toàn bộ heap từ page đầu tới page cuối và kiểm tra từng row — planner chọn nó khi không có index phù hợp, khi bảng quá nhỏ, hoặc khi query trả về quá nhiều row. Index scan đi xuống B-tree lấy pointer rồi fetch heap page cho từng row khớp, nên chi phí tỉ lệ với số row trả về: càng ít row càng vượt trội. Index-only scan là trường hợp index đã chứa mọi cột query cần, cả trong WHERE lẫn SELECT, nên engine lấy dữ liệu thẳng từ index leaf và không chạm heap. Riêng PostgreSQL còn cần visibility map xác nhận page đã all-visible;
EXPLAINbáoHeap Fetches: 0mới là index-only scan thật sự hiệu quả.Kể được tên ba loại nhưng không nói được điều kiện của index-only scan — index phải cover cả cột trong SELECT, không riêng cột filter.04
Đã tạo index mà query vẫn chậm, plan vẫn full scan — vì sao?
JuniorBốn nguyên nhân kinh điển. Thứ nhất là selectivity thấp: query trả về hơn khoảng 5–10% số row thì random I/O của index scan đắt hơn đọc tuần tự, planner chọn full scan và đó là quyết định đúng. Thứ hai là hàm bọc cột — index lưu giá trị gốc nên điều kiện
LOWER(email) = '[email protected]'không dùng được index trênemail, muốn dùng phải tạo expression index trên chínhLOWER(email). Thứ ba là ép kiểu trong điều kiện, kiểuCAST(id AS VARCHAR) = '12345'làm index trênidmất tác dụng. Thứ tư là wildcard đầu chuỗi:LIKE '%@gmail.com'không tận dụng được B-tree vì B-tree chỉ hỗ trợ prefix, tìm chữ giữa chuỗi phải dùng inverted index (full-text). Ngoài ra statistics cũ sau một đợt nạp lớn cũng khiến planner ước lượng sai số dòng và chọn nhầm plan.Kết luận 'index bị hỏng' rồi tạo thêm index nữa, thay vì đọc query plan để biết planner đang từ chối index vì lý do gì.05
Hash index khác B-tree thế nào? Vì sao B-tree vẫn là mặc định?
JuniorHash index băm khoá thành vị trí bucket nên tra equality gần như O(1) — một bước, không duyệt cây. Cái giá là hàm hash cố tình phân tán khoá để tránh dồn cục, nên hai giá trị liền kề rơi vào hai bucket cách xa nhau và index không giữ bất kỳ thứ tự nào:
BETWEEN,ORDER BY,LIKE 'admin%'đều bó tay. Hash còn hai giới hạn thực tế nữa: collision làm lookup suy biến thành duyệt chuỗi khi phân bố lệch, và bảng băm tràn khỏi RAM thì mỗi lookup thành một random I/O. B-tree tuy chậm hơn hash một chút ở equality nhưng phục vụ được equality, range, prefix và sắp xếp bằng một cấu trúc duy nhất — index đa năng đủ nhanh cho nhiều hình dạng truy vấn thường thắng index chỉ giỏi đúng một việc.Trả lời 'hash nhanh hơn nên tốt hơn' mà quên rằng mất thứ tự là mất luôn range, prefix và ORDER BY — phần lớn truy vấn thật nằm ở đó.06
Query trả về 70% số row, có index vẫn Seq Scan — planner sai hay đúng?
MidPlanner đúng, và nó quyết định bằng cost model chứ không đoán. Index scan sinh random I/O (mỗi row khớp là một lần seek vào heap page) còn seq scan đọc tuần tự và prefetch-friendly; PostgreSQL mã hoá chênh lệch đó bằng
random_page_costmặc định 4, nghĩa là một random page read đắt bằng bốn sequential page read. Với bảng 1 triệu row nằm trên 1000 page, index scan cho 700.000 row tốn cỡ 2,8 triệu đơn vị cost trong khi seq scan chỉ khoảng 1000 — chênh vài nghìn lần. Điểm hoà vốn thực tế thường rơi vào khoảng 5–15% selectivity. Hướng sửa đúng không phải thêm index mà là thêm điều kiện lọc để giảm selectivity, hoặc tạo partial index cho đúng subset cần đọc.Nghĩ 'có index thì phải dùng index' rồi tìm cách ép planner, thay vì hiểu random I/O của index scan có thể đắt hơn hẳn một lần quét tuần tự.07
B-tree cao bao nhiêu tầng với 1 tỷ row? Vì sao không phải 30 tầng?
MidB-tree không phải binary tree: nó multi-way, mỗi node là một page trên đĩa và chứa hàng trăm khoá. Ở PostgreSQL page 8 KB, mỗi entry chiếm khoảng 22 byte (key trung bình 16 byte cộng con trỏ CTID 6 byte) nên branching factor rơi vào khoảng 400. Height bằng log cơ số 400 của N: với 1 tỷ row là khoảng 4 cấp, tức 4–5 lần đọc page mỗi lookup, so với khoảng 30 cấp của một binary search tree cùng số row. Mỗi page read tốn cỡ 10 μs khi hit buffer cache và cỡ 100 μs khi phải xuống SSD, nên lookup vẫn nằm dưới một mili-giây. Nếu
bt_metapbáo level cao bất thường so với công thức thì thường là do key quá lớn hoặc index bloat kéo branching factor thực tế tụt xuống.Nhầm B-tree với binary tree rồi kết luận height log2(N) — bỏ mất ý cốt lõi là mỗi node bằng một page đĩa, fanout lớn mới giữ số lần I/O ở mức 4–5.08
So sánh B-tree và LSM-tree — mỗi họ hợp với workload nào?
MidB-tree cập nhật tại chỗ: tìm đúng leaf page rồi ghi đè, page đầy thì split — random I/O kèm write-ahead log, nhưng đọc luôn đi thẳng từ root xuống một leaf nên độ trễ thấp và ổn định, range query nhanh nhờ các leaf được liên kết. LSM-tree không bao giờ sửa tại chỗ: ghi nối vào memtable trong RAM cộng một dòng WAL tuần tự, memtable đầy thì flush thành SSTable bất biến, rồi compaction merge sort các SSTable để dọn bản cũ và tombstone. Hệ quả là LSM nuốt được throughput ghi rất cao vì mọi lần chạm đĩa đều tuần tự, đổi lại đọc phải gộp memtable với nhiều SSTable theo luật newest-wins nên read amplification cao hơn, bloom filter chỉ cắt bớt được phần lớn lần đọc vô ích. Đánh đổi cốt lõi: B-tree write amplification thấp và đọc ổn định, LSM ghi đến rẻ nhưng trả giá ở compaction nền. Chọn theo từng bảng — dashboard đọc nhiều cần độ trễ ổn định nghiêng B-tree, log hay telemetry ingest liên tục nghiêng LSM.
Học thuộc 'LSM ghi nhanh, B-tree đọc nhanh' mà không nói được cơ chế: ghi tuần tự so với random I/O tại chỗ, và compaction chính là chỗ LSM trả giá.09
Index (a, b, c) có dùng được cho điều kiện chỉ lọc theo b không?
MidKhông. Composite index sắp entry theo thứ tự từ điển:
atrước,bchỉ sorted bên trong từng nhóm cùnga,csorted bên trong từng nhóm(a, b). Bỏ quaanghĩa là không biết bắt đầu từ subtree nào — giá trịbcần tìm nằm rải khắp mọi nhóma, nên đọc index cũng tốn ngang quét bảng và planner chọn Seq Scan thẳng. Đây chính là leftmost prefix rule: WHERE phải phủ cột đầu tiên rồi mới mở rộng liên tục sang cột 2, cột 3; thứ tự viết trong mệnh đề WHERE không quan trọng, chỉ thứ tự trong định nghĩa index mới quan trọng. Khi engine không tối ưu được kiểu skip scan cho tình huống này, cách xử lý thực tế là tạo thêm một index riêng cho cột đó, hoặc đổi thứ tự cột nếu query kia quan trọng hơn.Nói 'index composite dùng được cho mọi cột nằm trong nó' — hoặc tưởng thứ tự viết trong WHERE quyết định, trong khi thứ tự khai báo index mới quyết định.10
Chọn thứ tự cột trong composite index theo nguyên tắc nào?
MidNguyên tắc số một là cột equality đặt trước cột range, vì cột range ngắt khả năng navigate tiếp — từ cột range trở đi B-tree chỉ quét dải, các cột sau không còn dùng để thu hẹp nữa. Trong nhóm equality thì đặt cột cardinality cao lên trước để thu hẹp subtree sớm. Cột range nên trùng với cột
ORDER BYvà nằm cuối, khi đó index đã trả row đúng thứ tự cần nên planner bỏ luôn bước Sort. Ví dụ dashboard lọcassignee_idbằng một giá trị,status IN ('todo','doing')vàdue_attrong một khoảng rồi sắp theodue_atthì index đúng là(assignee_id, status, due_at). Đo thực tế trên một triệu row: index một cột(assignee_id)cho khoảng 250ms, còn composite ba cột xuống khoảng 5ms — chênh lệch đến từ việc đẩy cả ba điều kiện vào index thay vì lọc trên heap.Đặt cột range trước rồi tưởng vẫn tối ưu — plan thành index scan trên range cộng một Filter, đọc nhiều row hơn hẳn mức cần thiết.11
Covering index là gì? INCLUDE khác thêm cột vào index thế nào?
MidCovering index là index chứa đủ mọi cột mà query cần, để engine trả kết quả thẳng từ index leaf mà không fetch heap — plan hiện Index Only Scan. Cú pháp
INCLUDE (col)(PostgreSQL 11 trở lên, SQL Server cũng có) thêm cột vào leaf nhưng không đưa vào sort key: cột đó không dùng được để filter hay sort, chỉ để cover danh sách SELECT, đổi lại không làm phức tạp tree structure và rẻ hơn khi ghi. Nên đưa vào sort key những cột xuất hiện trong WHERE hoặc ORDER BY, còn cột chỉ xuất hiện trong SELECT thì để INCLUDE. Ở PostgreSQL, Index Only Scan còn phụ thuộc visibility map: sau một đợt UPDATE lớn mà chưa VACUUM thìHeap Fetcheslớn hơn 0 và hiệu năng tụt về gần Index Scan thường.Nghĩ INCLUDE tương đương thêm cột vào index, rồi thắc mắc vì sao điều kiện WHERE trên cột INCLUDE lại không dùng được index.12
Partial index dùng khi nào, và vì sao có lúc planner không dùng nó?
MidPartial index thêm mệnh đề
WHEREvàoCREATE INDEXnên chỉ index subset row thoả điều kiện — index nhỏ hơn, nằm gọn trong cache hơn, và maintenance rẻ hơn vì bỏ qua những row không liên quan. Nó chỉ được dùng khi WHERE của query bao hàm điều kiện của index; query thiếu điều kiện đó thì planner không thể bảo đảm index phủ đủ dữ liệu nên quay về full index hoặc Seq Scan. Điểm ngọt là khi subset chiếm dưới 50% (lý tưởng 20–30%) và điều kiện đó có mặt trong hầu hết query thật, kiểuWHERE deleted_at IS NULLhayWHERE status IN ('todo','doing'). Đo thực tế trên dashboard 1 triệu row: đổi sang partial index kéo kích thước từ khoảng 80 MB xuống khoảng 25 MB mà tốc độ không đổi. Không đáng làm khi subset quá nhỏ (dưới vài phần trăm) hoặc khi điều kiện hay đổi theo business logic.Tạo partial index rồi viết query không nhắc lại điều kiện partial — index nằm im, plan vẫn Seq Scan mà không ai hiểu vì sao.13
GIN và BRIN dùng cho loại dữ liệu nào? Cái giá của mỗi loại?
MidGIN là inverted index cho cột đa phần tử — JSONB, array, tsvector: nó map mỗi element sang danh sách row chứa element đó, nên truy vấn containment
metadata @> '{"priority":"high"}'tra được thay vì quét bảng. Giá của GIN là ghi chậm hơn B-tree khoảng 5–10 lần, vì một row nhiều cặp key-value phải cập nhật nhiều inverted list, cộng thêm cơ chế pending list phải merge ở nền. BRIN đi hướng ngược lại: chỉ lưu min/max cho từng block range (mặc định 128 page) nên index nhỏ hơn B-tree tới cả nghìn lần, rất hợp bảng time-series append-only cực lớn. Nhưng BRIN chỉ loại trừ được block chắc chắn không chứa dữ liệu, và nó thành vô dụng khipg_stats.correlationthấp — bảng bị UPDATE nhiều làm thứ tự vật lý xáo trộn thì block range nào cũng có thể khớp. Quy tắc: kiểm tra correlation trước khi chọn BRIN, và đừng dùng GIN cho cột scalar equality vì đó là đất của B-tree.Dùng GIN cho cột TEXT scalar hoặc BRIN cho bảng bị UPDATE nhiều — index tạo ra chỉ tốn chi phí ghi mà planner gần như không dùng tới.14
Khi nào KHÔNG nên đánh index?
MidKhi cột có selectivity thấp: điều kiện trả về phần lớn bảng thì planner sẽ chọn full scan, index nằm im mà vẫn phải trả phí ghi. Khi bảng nhỏ, chỉ vài trăm page trở xuống, vì overhead tra index không bù lại được. Khi bảng write-heavy kiểu
eventshaymetrics— mỗi index thêm là một B-tree phải sửa trên mọi thao tác ghi, và với ingest hàng chục nghìn dòng mỗi giây thì đó là bottleneck thật. Khi index mới trùng lặp với index đã có: index(status, assignee_id)đã phục vụ được điều kiện chỉ lọcstatusnhờ leftmost prefix, thêm(status)nữa là dư. Và khi chưa đo gì cả — quy trình đúng là tìm query chậm trước, thêm index sau, rồi sau một thời gian chạy thật thì drop những index có số lượt dùng bằng 0.Đánh index mọi cột 'cho chắc' — bảng bảy index nghĩa là mỗi INSERT sửa bảy B-tree và storage phồng vài lần, trong khi phần lớn index không bao giờ được chọn.Học sâu hơn
Tại sao cần index — full scan 800ms vs index scan 0.2msStorage & indexing — nguyên lý · ~20 phútB-tree vs LSM-tree — hai triết lý lưu trữ indexStorage & indexing — nguyên lý · ~20 phútComposite index ordering — leftmost prefix rule + INCLUDE coveringIndexing internals · ~22 phútMini-challenge M05 — TaskFlow dashboard 2.1s → 50ms qua index strategyIndexing internals · ~30 phút15
Vì sao UUID v4 làm primary key lại hại B-tree?
MidVới khoá tăng dần kiểu
BIGSERIAL, khoá mới luôn lớn hơn mọi khoá cũ nên rơi vào leaf page cuối cùng; page đó thường còn chỗ (fill factor mặc định 90%) nên phần lớn insert chỉ ghi một page, đầy thì split một lần rồi page mới lại nhận tiếp. UUID v4 ngẫu nhiên nên rơi vào bất kỳ leaf nào trong cây, xác suất trúng leaf đã đầy cao, page split xảy ra liên tục — trung bình 2–3 page write cho mỗi insert. Benchmark trong bài: 1 triệu row mất khoảng 5 giây vớiBIGSERIALvà khoảng 12 giây với UUID v4, index tương ứng khoảng 22 MB so với 50 MB. Bloat đó không chỉ hại lúc ghi — index to hơn thì chiếm nhiều buffer cache hơn, kéo tụt cả những query chỉ đọc. Hai cách sửa là chuyển sang UUID v7 (có prefix timestamp nên sequential) hoặc giữBIGSERIALlàm khoá nội bộ và thêm một cột UUID public cho URL.Chỉ nói 'UUID tốn 16 byte nên chậm' — vấn đề thật là tính ngẫu nhiên gây page split rải khắp cây, chứ không phải kích thước khoá.
Topic kế cùng track: Câu hỏi phỏng vấn SQL transaction & isolation →
Trả lời trôi chảy bắt đầu từ hiểu cơ chế
Mỗi câu ở trên đều có bài học đứng sau. Học tuần tự cả khoá SQL & Database — Tư tưởng & Nguyên lý để không chỉ trả lời được, mà giải thích được vì sao.