Chỉ mục B-tree

B-tree là kiểu chỉ mục mặc định và chiếm phần lớn chỉ mục trong mọi hệ thống. Bài này đo hai vế của nó: đọc nhanh tới đâu, và ghi tốn thêm bao nhiêu.

Đọc: kích thước tăng 5.000 lần, thời gian gần như đứng yên

Chỉ mục lớn hơn 5.350 lần, thời gian tìm chỉ tăng 7%.

Lý do nằm ở cấu trúc. Ở mức 10 triệu dòng:

tang = 3    trang la = 27.323    khoa moi trang la ~366

Mỗi trang 8 kB chứa khoảng 366 khoá, nên chỉ cần ba lần đọc trang — gốc, tầng giữa, trang lá — là tới nơi. Muốn cây cao thêm một tầng, bảng phải lớn thêm khoảng 366 lần.

Đây là lý do "bảng của tôi lớn quá nên truy vấn chậm" gần như luôn sai khi truy vấn có chỉ mục phù hợp. Cái chậm không phải việc tìm, mà là số dòng phải lấy về.

Quét khoảng: chi phí tỉ lệ với số dòng trả về

Từ 1 tới 100 dòng gần như không đắt thêm — vẫn nằm trong một vài trang lá. Từ đó trở đi, chi phí đi gần tuyến tính với số dòng.

Đây cũng là câu trả lời cho câu hỏi "chỉ mục có giúp không": nó giúp tìm, không giúp đọc. Nếu truy vấn của bạn trả về một triệu dòng, chỉ mục không cứu được — như phần 10 đã đo.

Ghi: mỗi chỉ mục là một khoản thuế

Chèn 1.000.000 dòng vào cùng một bảng, chỉ khác số chỉ mục phụ:

Bốn chỉ mục phụ làm việc chèn chậm 3,5 lần, và chỉ mục chiếm hơn nửa dung lượng của bảng.

Con số +36% cho chỉ mục đầu tiên là mức bạn nên quen: một chỉ mục thêm vào không miễn phí, nhưng cũng không thảm hoạ. Cái thảm hoạ là bảng có mười chỉ mục mà tám cái chưa từng được dùng — phần 19 sẽ đo cách tìm chúng.

UPDATE: cột có chỉ mục làm mất cơ chế HOT

PostgreSQL có một tối ưu tên HOT (heap-only tuple): khi bạn cập nhật một dòng mà không đụng tới cột nào có chỉ mục, và trang còn chỗ trống, nó ghi phiên bản mới ngay trong trang đó và không phải sửa chỉ mục nào cả.

Cập nhật 200.000 dòng, bảng đặt fillfactor=70 để trang còn chỗ:

HOT làm đúng việc của nó: lượng WAL giảm 47%.

Nhưng thời gian lại ngược, và tôi chỉ giải thích được một nửa

Cột không có chỉ mục cho ít WAL hơn hẳn mà chạy chậm hơn — 0,74–0,90 s so với 0,55–0,64 s. Tôi chạy ba lần mỗi bên, xen kẽ thứ tự, và kết quả lặp lại ổn định.

Điều tôi giải thích được: phép đo này chạy hoàn toàn trong bộ nhớ, nên 45 MB WAL chênh lệch không phải trả bằng lần ghi đĩa nào. Cái còn lại — vì sao đường HOT tốn thêm thời gian CPU tới mức đó — tôi không giải thích được và không đoán.

Điều chắc chắn có ích: trên máy chủ thật, nơi WAL phải ghi xuống đĩa và truyền sang bản sao, 45 MB chênh lệch cho mỗi 200.000 lần cập nhật là con số đáng kể. Đó là lý do vẫn nên tránh đánh chỉ mục lên cột bị cập nhật liên tục.

Và lưu ý điều kiện: HOT chỉ xảy ra khi trang còn chỗ trống. Lần đo đầu tôi chạy VACUUM FULL trước, nó nén mọi trang đầy 100%, và số HOT ra 0 ở cả hai bên — phép đo vô nghĩa. Phải đặt fillfactor=70 thì cơ chế mới có chỗ hoạt động.

Khi nào B-tree không phải lựa chọn đúng

B-tree phục vụ tốt =, <, >, BETWEEN, IN, IS NULL, và cả LIKE 'tien to%'. Nó không giúp cho:

• LIKE '%duoi' — không có tiền tố để đi xuống cây
• Tìm kiếm toàn văn — cần GIN, phần 16
• Truy vấn theo khoảng không gian hoặc thời gian phức tạp — cần GiST, phần 17
• Bảng rất lớn chỉ lọc theo khoảng thời gian tăng dần — BRIN nhỏ hơn nhiều, cũng ở phần 17

Thử ba mươi giây

Xem chỉ mục của bạn cao mấy tầng và mỗi trang chứa bao nhiêu khoá:

CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT level + 1 AS so_tang FROM bt_metap('ten_chi_muc');

Và xem chỉ mục chiếm bao nhiêu phần dung lượng bảng:

SELECT relname,
       pg_size_pretty(pg_relation_size(relid)) AS bang,
       pg_size_pretty(pg_indexes_size(relid)) AS chi_muc,
       round(100.0 * pg_indexes_size(relid) / nullif(pg_relation_size(relid),0)) AS phan_tram
FROM pg_stat_user_tables
ORDER BY pg_indexes_size(relid) DESC
LIMIT 10;

Chỉ mục lớn hơn chính bảng không phải lúc nào cũng sai — nhưng đó là lúc nên xem lại có cái nào thừa không.

Phần sau đo chỉ mục nhiều cột: đặt cột nào trước, và vì sao thứ tự quan trọng hơn bạn nghĩ.