Index (a,b) tăng tốc WHERE a nhưng bỏ rơi WHERE b — vì sao thứ tự cột quyết định tất cả

Một cuốn danh bạ sắp theo họ trước, rồi trong mỗi họ mới sắp theo tên. Tra "họ Nguyễn" thì nhanh — lật tới khu chữ N là thấy cả cụm. Tra "họ Nguyễn tên An" còn nhanh hơn — trong khu Nguyễn, tên đã sắp sẵn. Nhưng tra "tất cả những người tên An bất kể họ"? Chịu. Các tên An nằm rải rác khắp cuốn: An họ Bùi ở đầu, An họ Nguyễn ở giữa, An họ Vũ ở cuối — bạn phải lật cả cuốn. Chỉ mục ghép nhiều cột trong cơ sở dữ liệu xếp y hệt cuốn danh bạ này, và bài này là lần tôi tưởng đánh một index (a, b) là lo được cả tra theo a lẫn tra theo b, rồi ngã ngửa khi tra theo b quét sạch cả bảng.

Truy vấn thật hiếm khi lọc trên đúng một cột — thường là WHERE khach_hang = ? AND ngay = ?. Câu hỏi tự nhiên: đánh một chỉ mục ghép trên nhiều cột thì nó phục vụ được những truy vấn nào? Đây là chỗ nhiều người — kể cả tôi — mang một giả định sai và trả giá bằng những truy vấn chậm bí ẩn. Bài này đo chính xác một chỉ mục ghép (a, b) giúp được truy vấn nào và bỏ rơi truy vấn nào.

Một cây, sắp theo cột đầu trước

Một chỉ mục ghép (a, b) không phải hai chỉ mục riêng cho a và cho b. Nó là một cây B-tree, sắp xếp theo a trước, rồi trong mỗi nhóm cùng a mới sắp theo b. Giống hệt cuốn danh bạ sắp theo họ trước rồi tên: bạn tra nhanh "họ Nguyễn", hoặc "họ Nguyễn tên An", nhưng không tra nhanh được "mọi người tên An" — vì các tên An nằm rải rác khắp cuốn, dưới mọi họ.

Từ đó ra quy tắc tiền tố trái nhất (leftmost prefix): một chỉ mục ghép chỉ dùng được khi truy vấn ràng buộc các cột từ trái sang, liên tiếp. Index (a, b) phục vụ WHERE a = ? (chỉ cột trái) và WHERE a = ? AND b = ? (cả hai) — nhưng không phục vụ WHERE b = ? một mình, vì bỏ qua cột trái nhất là mất luôn thứ tự để tìm.

Đo: cùng một index, ba số phận

Tôi tạo bảng một triệu hàng, cột a và b mỗi cột 1000 giá trị, đánh chỉ mục ghép (a, b), rồi chạy EXPLAIN (ANALYZE, BUFFERS) cho ba truy vấn:

Dòng một: WHERE a = 42 dùng chỉ mục (Index Cond trên a), đọc ~1006 trang để lấy 1000 hàng khớp. Dòng hai: WHERE a = 42 AND b = 7 dùng cả hai cột của chỉ mục (Index Cond (a = 42) AND (b = 7)), khoanh vùng chính xác tới đúng một hàng — chỉ 4 trang. Đó là chỉ mục ghép phát huy đúng sức: càng ràng buộc nhiều cột từ trái, càng khoanh hẹp. So sánh 4 trang với ~1006 trang cho thấy giá trị của cột thứ hai: ràng buộc thêm b giúp index đi thẳng tới đúng một hàng thay vì gom cả nghìn hàng cùng a rồi mới lọc — đúng lý do người ta ghép nhiều cột vào một chỉ mục thay vì chỉ đánh cột đầu.

Dòng ba là cú sốc: WHERE b = 7 — chỉ ràng buộc cột thứ hai — cho Seq Scan, quét toàn bộ 5406 trang của bảng, Rows Removed by Filter khổng lồ. Chỉ mục (a, b) gần như vô hình với truy vấn này, dù b rõ ràng nằm trong nó.

Tưởng (a,b) là hai index

Cái bẫy tôi bước vào rất phổ biến. Sau khi tạo (a, b), tôi tin chắc mình đã "đánh index cho cả a lẫn b" — nên mọi truy vấn lọc trên a hoặc b đều sẽ nhanh. Hai truy vấn đầu củng cố niềm tin đó: a = 42 nhanh, a = 42 AND b = 7 nhanh. Tôi định dừng ở đó và kết luận "index ghép lo hết".

Nhưng khi thử WHERE b = 7, kết quả là Seq Scan quét cả bảng — chậm y như không có chỉ mục nào. Theo kỷ luật, tôi không đổ cho "planner dở"; tôi kiểm lại giả định. Và giả định sai của tôi lộ ra: tôi coi (a, b) như hai chỉ mục độc lập, một cho a, một cho b. Nó không phải vậy. Nó là một cây sắp theo a trước, nên b = 7 nằm rải rác ở khắp nơi — dưới a = 0, dưới a = 1, ..., dưới a = 999, đúng như các tên An rải khắp cuốn danh bạ. Không có cách nào "nhảy thẳng tới mọi hàng b = 7" mà không duyệt gần hết cây; planner tính ra quét tuần tự còn rẻ hơn, nên bỏ chỉ mục.

Điều rút ra: một chỉ mục ghép (a, b) chỉ phục vụ các truy vấn ràng buộc một tiền tố trái của nó (a, hoặc a và b), không phải mọi cột trong nó. Đừng đoán "cột nằm trong index thì được tăng tốc" — với chỉ mục ghép, vị trí của cột trong danh sách mới quyết định. Cách duy nhất biết chắc là chạy EXPLAIN cho từng dạng truy vấn thật, như tôi vừa làm — con số Seq Scan 5406 trang nói thẳng rằng b một mình không được chỉ mục giúp.

Về đến code hằng ngày

Điều đầu tiên: thứ tự cột trong chỉ mục ghép là một quyết định thiết kế, không phải chuyện tùy tiện. Đặt cột nào trước quyết định index phục vụ được truy vấn nào. Quy tắc thực dụng: đặt cột bạn hay lọc bằng = (đẳng thức) lên trước, cột lọc bằng khoảng (<, >, BETWEEN) ra sau. Vì một điều kiện khoảng "mở toang" phần còn lại: index (ngay, trang_thai) với WHERE ngay > X AND trang_thai = Y chỉ dùng được ngay rồi phải lọc trang_thai thủ công, trong khi (trang_thai, ngay) với cùng truy vấn khoanh trang_thai = Y chính xác rồi mới quét khoảng ngay — hiệu quả hơn nhiều.

Điều thứ hai: đừng tạo chỉ mục ghép rồi tưởng đã phủ mọi cột con của nó. Nếu bạn thật sự cần tra nhanh cả WHERE a = ? lẫn WHERE b = ? riêng lẻ, bạn cần hai chỉ mục (hoặc một (a, b) cộng một (b)), không phải một (a, b) duy nhất. Ngược lại, một (a, b) đã bao gồm khả năng của (a) đơn — nên nếu đã có (a, b) thì thường không cần thêm (a) riêng, tránh index thừa. Biết điều này giúp bạn thiết kế đúng bộ chỉ mục tối thiểu.

Và cái nguyên tắc "khóa ghép chỉ tra được theo tiền tố trái" này không đóng khung trong CSDL — nó xuất hiện ở mọi cấu trúc dữ liệu sắp-theo-thứ-tự-từ-điển. Một TreeMap (hay bất kỳ sorted map nào) với khóa là cặp (a, b) tra được "mọi khóa có a=X" (một khoảng liên tục) nhưng không tra được "mọi khóa có b=Y" mà không duyệt hết — đúng quy tắc tiền tố trái. Cùng lý do, muốn query một HashMap theo hai chiều khác nhau bạn cần hai map (hoặc hai index), giống hệt cần hai index CSDL. Ngay cả sắp xếp đa khóa trong code (sort by a then b) cũng cho bạn tìm nhị phân theo a nhưng không theo b. Mẫu số chung đáng mang theo: mọi cấu trúc "sắp theo nhiều khóa" chỉ cho tra cứu nhanh theo tiền tố của thứ tự sắp — nên khi thiết kế khóa ghép (index, sort key, composite map key), thứ tự các thành phần phải khớp cách bạn sẽ truy vấn, và một cột không ở tiền tố trái coi như không được đánh index cho truy vấn đó. Gói lại bằng số: chỉ mục ghép (a, b) là một cây sắp theo a trước, nên phục vụ WHERE a=? (~1006 trang) và WHERE a=? AND b=? (4 trang) nhưng bỏ rơi WHERE b=? một mình (Seq Scan 5406 trang) — quy tắc tiền tố trái nhất, và thứ tự cột là thiết kế.

Muốn tự thấy thì nếu bạn có một chỉ mục ghép trong cơ sở dữ liệu (xem bằng \d ten_bang trong psql, cột index liệt kê (cot1, cot2, ...)), thử EXPLAIN ba truy vấn: lọc theo cột đầu tiên một mình, lọc theo cả hai cột, và lọc chỉ theo cột thứ hai một mình. Bạn sẽ thấy hai cái đầu dùng Index Scan còn cái cuối rơi về Seq Scan — đúng quy tắc tiền tố trái nhất. Rồi nhìn lại các truy vấn thật hay chạy trong ứng dụng của bạn: cột chúng lọc bằng = có nằm ở đầu chỉ mục ghép không? Nếu một truy vấn nóng lọc theo cột nằm giữa hay cuối chỉ mục, nó có thể đang âm thầm quét cả bảng — và đảo thứ tự cột (hoặc thêm một chỉ mục khác) là cách sửa.