Hình dung cuốn danh bạ sắp theo họ, rồi trong mỗi họ sắp tiếp theo tên. Tìm "mọi người họ Nguyễn" rất nhanh — lật tới khối Nguyễn là xong. Tìm "Nguyễn Văn An" cũng nhanh — vào khối Nguyễn rồi dò tiếp theo tên. Nhưng thử tìm "mọi người tên Văn" mà xem: cuốn sổ không sắp theo tên, nên bạn phải đọc từ đầu tới cuối. Cái khoá thứ hai chỉ giúp bên trong một giá trị cố định của khoá thứ nhất. Chỉ mục nhiều cột của PostgreSQL sắp xếp đúng kiểu cuốn danh bạ ấy, và toàn bộ chuyện thứ tự cột nằm ở nhận xét này. CREATE INDEX ON don (a, b) và CREATE INDEX ON don (b, a) chiếm cùng dung lượng, chứa cùng dữ liệu, và phục vụ hai tập truy vấn khác hẳn nhau. Bài này đo khác biệt đó trên 2.000.000 dòng.
Quy tắc thứ nhất: cột dẫn đầu phải có trong điều kiện
Hai bảng giống hệt nhau, mỗi bảng một chỉ mục khác thứ tự. Truy vấn chỉ lọc theo kh_id:
SELECT count(*) FROM ... WHERE kh_id = 12345;
| Chỉ mục | Thời gian | Số trang |
|---|---|---|
(trang_thai, kh_id) |
37,80 ms | 5.194 |
(kh_id, trang_thai) |
0,08 ms | 4 |
Chênh 472 lần, và chỉ mục sai đọc gấp 1.300 lần số trang.
Lý do nằm ở cách B-tree hoạt động. Khoá trong chỉ mục được xếp theo (trang_thai, kh_id) — tức là xếp theo trang_thai trước. Không biết trang_thai thì không có cách nào đi xuống đúng nhánh, nên PostgreSQL phải đọc toàn bộ chỉ mục và lọc từng khoá. Đúng chuyện tìm "tên Văn" trong cuốn sổ sắp theo họ.
Chỉ mục vẫn được dùng, EXPLAIN vẫn ghi Index Only Scan, và nó vẫn chậm gấp 472 lần. Đây là lý do "thấy Index Scan là yên tâm" không đủ — phải xem Index Cond có chứa điều kiện của bạn không.
Khi lọc cả hai cột thì hai chỉ mục tương đương: 0,07 và 0,04 ms.
Quy tắc rút ra: cột xuất hiện trong nhiều truy vấn nhất đặt trước. Một chỉ mục (a, b) phục vụ được truy vấn lọc theo a, và truy vấn lọc theo a và b. Nó không phục vụ truy vấn chỉ lọc theo b.
Quy tắc thứ hai: cột so bằng trước, cột so khoảng sau
WHERE kh = 500 AND ngay BETWEEN current_date - 30 AND current_date
| Chỉ mục | Thời gian | Số trang | Index Cond chứa gì |
|---|---|---|---|
(kh, ngay) — bằng trước |
0,07 ms | 4 | cả kh lẫn ngay |
(ngay, kh) — khoảng trước |
0,64 ms | 82 | chỉ ngay |
Chậm 9 lần, đọc gấp 20 lần số trang.
Cột cuối cùng của bảng giải thích tất cả. Với (ngay, kh), PostgreSQL quét toàn bộ khoảng 30 ngày rồi mới lọc kh bên trong khoảng đó. Với (kh, ngay), nó đi thẳng tới nhánh kh = 500 rồi chỉ đọc đúng 30 ngày trong nhánh ấy.
Điều kiện khoảng "chặn" mọi cột đứng sau nó — chúng chỉ còn dùng để lọc, không dùng để định vị. Nên mọi cột so bằng phải đứng trước cột so khoảng.
Quy tắc thứ ba: một chỉ mục phức hợp thắng hai chỉ mục riêng
Cùng truy vấn WHERE kh = 500 AND loai = 3:
| Cách đánh chỉ mục | Thời gian | Số trang | Dung lượng |
|---|---|---|---|
Một chỉ mục (kh, loai) |
0,11 ms | 4 | 14 MB |
Hai chỉ mục (kh) và (loai) |
7,39 ms | 781 | 27 MB |
Nhanh hơn 67 lần và tốn một nửa dung lượng.
PostgreSQL có thể kết hợp hai chỉ mục riêng bằng BitmapAnd — nó dựng bitmap từ mỗi chỉ mục rồi giao nhau. Nhưng việc đó phải đọc phần lớn cả hai chỉ mục trước khi giao, nên đắt hơn nhiều so với đi thẳng một lần.
Hai chỉ mục riêng vẫn có chỗ dùng: khi bạn có truy vấn chỉ lọc kh, và truy vấn khác chỉ lọc loai. Còn nếu hai cột luôn đi cùng nhau trong WHERE, hãy gộp thành một.
Chỉ mục cũng phục vụ được ORDER BY
SELECT id FROM ... WHERE kh = 500 ORDER BY ngay;
| Chỉ mục | Thời gian | Có bước Sort? |
|---|---|---|
(kh, ngay) |
3,55 ms | không |
(ngay, kh) |
6,38 ms | không |
Cả hai đều bỏ được bước sắp xếp, nhưng vì lý do khác nhau: (kh, ngay) đọc đúng nhánh kh=500 mà nhánh đó vốn đã xếp theo ngay; (ngay, kh) quét theo thứ tự ngay rồi lọc kh. Cách sau đúng thứ tự nhưng đọc nhiều hơn, nên chậm gần gấp đôi.
Một chi tiết làm tôi mất thời gian
Lần đo đầu, cả hai đều có bước Sort và tôi không hiểu vì sao. Nhìn kế hoạch đầy đủ mới thấy:
Sort
Sort Key: ngay
-> Bitmap Heap Scan on n1
Bộ tối ưu chọn Bitmap Heap Scan, và kiểu quét đó làm mất thứ tự — nó gom các trang cần đọc rồi đọc theo thứ tự vật lý để giảm số lần nhảy. Muốn giữ thứ tự phải là Index Scan thường.
Nên câu "chỉ mục phục vụ ORDER BY" có một điều kiện ẩn: chỉ khi bộ tối ưu chọn Index Scan. Với truy vấn trả nhiều dòng, nó thường chọn Bitmap Heap Scan và bạn vẫn phải sắp xếp.
Cách chọn thứ tự trong thực tế
Với mỗi truy vấn quan trọng, viết ra các cột theo ba nhóm:
- Cột so bằng (
=,IN) — đặt trước, cột nào chọn lọc cao hơn thì đứng trước hơn - Cột so khoảng (
<,>,BETWEEN) — đặt sau nhóm trên, và chỉ một cột có tác dụng - Cột trong
ORDER BY— đặt sau cùng, cùng chiều sắp xếp
Ví dụ cho WHERE tinh = ? AND trang_thai = ? AND ngay > ? ORDER BY ngay:
CREATE INDEX ON don (tinh, trang_thai, ngay);
Và một mẹo kiểm tra nhanh: nếu bạn đã có chỉ mục (a, b, c) thì không cần thêm (a) hay (a, b) — chỉ mục dài đã phục vụ mọi tiền tố của nó. Đây là nguồn chỉ mục thừa phổ biến nhất.
Mẫu số chung
Cuốn danh bạ sắp theo (họ, tên) ở đầu bài là hình ảnh của một sự thật đúng với mọi thứ tự nhiều tầng: một khoá phức hợp sắp xếp theo cấp bậc — nó định vị bạn theo trường đầu, rồi trường thứ hai bên trong một giá trị cố định của trường đầu, và cứ thế. Nên nó trả lời rất nhanh câu "ghim một tiền tố, rồi quét khoảng ở trường kế tiếp", nhưng vô dụng với truy vấn bỏ qua trường dẫn, hoặc quét khoảng ở một trường trước khi tới trường cuối — vì mọi thứ sau một khoảng đều không còn được định vị nữa.
Cùng nguyên lý ấy, đổi ngăn xếp:
- Trong Java, một
TreeMaphay danh sách sắp bằngComparator.comparing(a).thenComparing(b)cho bạn tìm-nhị-phân theoa(hay tiền tốarồi rangeb), nhưng không theobmột mình. Sắp nhân viên theo(phòng, lương)thì tra được "người của phòng X, lương trong khoảng" — chứ không tra được "mọi người lương > X trên khắp các phòng" mà không quét hết. - Các kho khoá-giá-trị gọi thẳng đây là luật thiết kế khoá: Cassandra và DynamoDB tách partition key (so bằng) và sort key (khoảng), HBase/Bigtable dùng khoá dòng từ điển — và lời khuyên "đặt trường so bằng trước, trường khoảng sau" giống hệt từng chữ quy tắc thứ hai ở trên. Cả một môn nghề mô hình hoá dữ liệu DynamoDB gói trong đúng chuyện này.
Nên câu hỏi đúng khi thiết kế một khoá phức hợp — chỉ mục, sort key, hay comparator — không phải "gồm những cột nào" mà là "truy vấn của tôi ghim trường nào và quét khoảng trường nào": trường so bằng lên trước (trường hay dùng nhất trước hơn), đúng một trường khoảng đặt cuối. Muốn dọn chỉ mục thừa do đã có chỉ mục dài hơn bắt đầu bằng cùng các cột, soát nhanh:
SELECT a.indexrelid::regclass AS thua,
b.indexrelid::regclass AS da_bao_phu
FROM pg_index a
JOIN pg_index b ON a.indrelid = b.indrelid
AND a.indexrelid <> b.indexrelid
AND array_to_string(b.indkey,' ') LIKE array_to_string(a.indkey,' ') || ' %'
WHERE NOT a.indisunique AND NOT a.indisprimary;
Mỗi dòng in ra là một chỉ mục có thể xoá — nó đang làm chậm mọi lần ghi mà không phục vụ truy vấn nào mà chỉ mục dài hơn không phục vụ được. Và với một truy vấn cụ thể, chạy EXPLAIN (ANALYZE) rồi xem dòng Index Cond: điều kiện nào nằm trong đó là được dùng để đi xuống cây, điều kiện rơi xuống Filter nghĩa là PostgreSQL đã đọc dòng lên rồi mới loại.
Phần sau đo chỉ mục một phần: bỏ bớt dòng khỏi chỉ mục tiết kiệm được bao nhiêu.
