Phần trước đo BRIN và GiST. Còn lại ba kiểu chỉ mục ít gặp: HASH, SP-GiST và bloom. Câu hỏi duy nhất đáng hỏi về chúng là có trường hợp nào chúng thắng B-tree không — và nếu có thì trả giá bằng gì.
HASH với khoá ngắn: thua
Bảng 5 triệu dòng, cột ma là chuỗi md5 32 ký tự:
create table h(id bigserial primary key, ma text, ip inet, so bigint);
insert into h(ma, ip, so)
select md5(i::text),
('10.'||(i/65536%256)||'.'||(i/256%256)||'.'||(i%256))::inet,
i
from generate_series(1, 5000000) i;
| Chỉ mục | Kích thước | Thời gian dựng |
|---|---|---|
| B-tree | 282 MB | 3,38 s |
| HASH | 128 MB | 2,61 s |
HASH nhỏ hơn 2,2 lần. Nhưng tra một dòng theo giá trị chính xác, lặp 5 lần lấy trung vị:
| Chỉ mục | Kế hoạch | Trung vị |
|---|---|---|
| Không có | Seq Scan | 68,374 ms |
| B-tree | Index Scan | 0,039 ms |
| HASH | Index Scan | 0,048 ms |
HASH chậm hơn B-tree, dù lý thuyết nói nó là O(1) còn B-tree là O(log n).
Lý do đã đo ở phần 11: cây B-tree trên 5 triệu dòng chỉ cao 4 tầng. Ba tầng trên nằm sẵn trong shared_buffers sau lần truy cập đầu tiên, nên "log n" thực tế là một lần đọc đĩa duy nhất — đúng bằng HASH. Còn HASH phải tính hàm băm, tìm bucket, rồi có thể đi qua trang tràn nếu bucket bị đầy. O(1) không rẻ hơn O(4) khi cả hai đều là một lần chạm đĩa.
HASH với khoá dài: thắng, và thắng lớn
Thay chuỗi md5 bằng URL thật, trung bình 190 ký tự:
create table hd(id bigserial primary key, url text);
insert into hd(url)
select 'https://vi.example.com/danh-muc/' || md5(i::text) ||
'/bai-viet/' || md5((i*7)::text) ||
'/phien-ban/' || md5((i*13)::text) ||
'?tham-so=' || md5((i*17)::text)
from generate_series(1, 3000000) i;
| Chỉ mục | Kích thước | Thời gian dựng | Tra một dòng |
|---|---|---|---|
| B-tree | 716 MB | 6,59 s | 0,042 ms |
| HASH | 81 MB | 1,82 s | 0,037 ms |
Nhỏ hơn 8,8 lần, dựng nhanh hơn 3,6 lần, và giờ tra cũng nhanh hơn một chút.
Khác biệt nằm ở cái được lưu. B-tree lưu nguyên khoá trong mỗi mục để còn so sánh thứ tự — khoá 190 byte thì mỗi mục 190 byte. HASH chỉ lưu giá trị băm 4 byte, bất kể khoá dài bao nhiêu. Chỉ mục B-tree trên URL còn to hơn cả bảng dữ liệu 403 MB; chỉ mục HASH thì không.
Đây là quy luật, không phải kết quả cá biệt: khoá càng dài, khoảng cách càng rộng. Với khoá 32 byte, HASH nhỏ hơn 2,2 lần. Với khoá 190 byte, 8,8 lần.
Chi phí ghi
Chèn 500.000 dòng khoá dài vào bảng rỗng, lặp ba lần:
| Chỉ mục | Thời gian | WAL | Chỉ mục nặng |
|---|---|---|---|
| Không có | 1,49 / 1,62 / 1,45 s | 133 MB | 0 |
| HASH | 1,71 / 1,74 / 1,97 s | 182 MB | 18 MB |
| B-tree | 3,21 / 2,85 / 3,06 s | 301 MB | 113 MB |
B-tree làm việc chèn chậm gấp đôi và sinh thêm 168 MB WAL cho nửa triệu dòng. HASH thêm khoảng 20% thời gian và 49 MB.
Con số WAL đó cũng trả lời một câu hỏi lịch sử. Trước PostgreSQL 10, chỉ mục HASH không được ghi WAL — nghĩa là không an toàn khi máy chết đột ngột và không được sao chép sang máy dự phòng, nên tài liệu chính thức khuyên đừng dùng. Con số 182 MB đo trên PostgreSQL 16 cho thấy nó đã được ghi WAL đầy đủ. Lời khuyên "đừng dùng HASH" giờ đã hết hạn, nhưng nó vẫn được chép lại trong rất nhiều bài viết trên mạng.
Cái giá: HASH chỉ biết dấu bằng
Giữ đúng chỉ mục HASH trên hd(url), rồi chạy bốn kiểu truy vấn:
| Truy vấn | Kế hoạch |
|---|---|
url = '...' |
Index Scan |
url in ('a','b','c') |
Bitmap Heap Scan |
url > 'https://vi.e' |
Seq Scan |
url like 'https://vi.example.com/d%' |
Seq Scan |
order by url limit 10 |
Seq Scan |
Ba câu cuối không dùng được chỉ mục. Điều này hợp lý — hàm băm phá huỷ thứ tự theo thiết kế, hai chuỗi gần nhau về thứ tự từ điển cho ra hai giá trị băm không liên quan gì nhau — nhưng hậu quả thì đáng nhớ: chỉ mục vẫn nằm đó, vẫn tốn đĩa, vẫn phải cập nhật mỗi lần ghi, và không giúp gì cho ba câu đó.
Ba giới hạn nữa báo lỗi ngay lúc CREATE INDEX, nên ít nhất bạn biết ngay:
create unique index uh on hd using hash(url);
ERROR: access method "hash" does not support unique indexes
create index mh on hd using hash(url, id);
ERROR: access method "hash" does not support multicolumn indexes
create index ih on hd using hash(url) include (id);
ERROR: access method "hash" does not support included columns
Không có unique nghĩa là HASH không dùng làm khoá chính, không làm ràng buộc duy nhất, và không làm đích cho khoá ngoại được. Nó chỉ là chỉ mục phụ để tra cứu.
Tóm lại, HASH đáng dùng khi cả năm điều kiện sau cùng đúng: khoá dài, chỉ tra bằng dấu bằng, không cần sắp xếp, không cần ràng buộc duy nhất, và dung lượng đĩa hoặc tốc độ ghi đang là vấn đề thật. Thiếu một điều là B-tree thắng.
SP-GiST: không tìm được lý do dùng
SP-GiST hay được giới thiệu cho dữ liệu phân cấp — địa chỉ IP là ví dụ kinh điển. Bảng h có sẵn 5 triệu địa chỉ IP:
Chỉ mục trên ip |
Kích thước | Dựng | ip << inet '10.20.0.0/16' |
|---|---|---|---|
| B-tree | 107 MB | 1,20 s | 6,08 ms |
| SP-GiST | 155 MB | 3,30 s | 5,75 ms |
SP-GiST to hơn 45%, dựng lâu hơn 2,7 lần, và nhanh hơn đúng 5%. Trên chính truy vấn mà nó được sinh ra để phục vụ.
Tôi không kết luận SP-GiST vô dụng — tôi kết luận rằng trên phép đo này, với dữ liệu này, tôi không tìm được lý do chọn nó. Nó có thể thắng rõ hơn với dữ liệu phân bố lệch nặng hoặc với kiểu point và truy vấn lân cận, nhưng đó là bài đo khác.
bloom: nhỏ, nhanh dựng, và không được dùng
bloom giải quyết một bài toán cụ thể: bảng nhiều cột, người dùng lọc theo tổ hợp bất kỳ, không đoán trước được tổ hợp nào. Dựng B-tree cho mọi cột thì tốn đĩa; dựng chỉ mục nhiều cột thì phải đoán đúng thứ tự (phần 12 đã đo cái giá của việc đoán sai: chậm 472 lần).
Bảng 3 triệu dòng, 8 cột, mỗi cột 50 giá trị phân biệt. Truy vấn lọc theo 3 cột bất kỳ, khớp 28 dòng:
| Cách | Kích thước | Dựng | Truy vấn |
|---|---|---|---|
| Không chỉ mục | 0 | — | 42,24 ms |
| 8 chỉ mục B-tree | 159 MB | 4,94 s | 8,04 ms |
| 1 chỉ mục bloom | 46 MB | 0,72 s | 40,26 ms |
bloom nhỏ hơn 3,5 lần và dựng nhanh hơn 6,9 lần. Nhưng 40,26 ms là con số của Seq Scan — bộ lập lịch không hề dùng chỉ mục vừa dựng.
Ép nó dùng bằng set enable_seqscan = off:
Bitmap Heap Scan on bl3 11,07 ms kiểm lại loại bỏ 56 dòng
Vậy bloom có tác dụng — 11,07 ms so với 42,24 ms — nhưng vẫn chậm hơn 8 chỉ mục B-tree, và bộ lập lịch từ chối nó. Lý do nằm ở chi phí ước lượng:
Seq Scan song song : cost = 47.899 (Workers Planned: 2)
Bitmap Heap Scan : cost = 61.138
Seq Scan được chia cho 2 tiến trình phụ nên chi phí ước lượng của nó tụt xuống dưới bloom. Chỉ mục bloom không hỗ trợ quét song song, nên càng nhiều lõi CPU thì nó càng khó được chọn.
Đây là kiểu thất bại tệ nhất: bạn cài extension, dựng chỉ mục, thấy nó chiếm 46 MB trên đĩa, và nó không bao giờ được dùng. Không lỗi, không cảnh báo. Cách duy nhất phát hiện là đọc EXPLAIN — hoặc kiểm pg_stat_user_indexes:
select indexrelname, idx_scan
from pg_stat_user_indexes
where relname = 'bl3';
idx_scan = 0 sau vài ngày chạy thật nghĩa là chỉ mục đó chỉ đang tốn tiền của bạn.
Sáu kiểu, một kết luận
| Kiểu | Thắng ở đâu | Trả giá bằng |
|---|---|---|
| B-tree | mọi thứ còn lại | — |
| BRIN | dung lượng, tốc độ ghi | cần correlation gần 1 (phần 17) |
| GIN | tìm kiếm trong mảng và toàn văn | dựng chậm, chỉ mục lớn (phần 16) |
| GiST | kiểu khoảng, hình học, ràng buộc loại trừ | tệ hơn B-tree ở kiểu vô hướng |
| HASH | khoá dài, chỉ tra bằng dấu bằng | mất thứ tự, unique, nhiều cột |
| SP-GiST | (không đo được trường hợp thắng) | to hơn, dựng lâu hơn |
| bloom | nhiều cột lọc tuỳ ý | bộ lập lịch thường không chọn |
Sau mười tám phần đo, kết luận không có gì bất ngờ: B-tree là mặc định đúng, và mặc định đó đúng phần lớn thời gian. Năm kiểu kia đều thắng ở đúng một chiều — thường là dung lượng — và mỗi kiểu đều đòi một điều kiện cụ thể phải đúng trước.
Điểm chung nguy hiểm của cả năm là chúng hỏng lặng lẽ. BRIN mất tương quan, bloom không được chọn, HASH gặp một câu order by — không cái nào báo lỗi. Câu lệnh vẫn chạy, chỉ chậm hơn. pg_stat_user_indexes.idx_scan là cách rẻ nhất để biết chỉ mục nào đang ăn không ngồi rồi.
Thử ba mươi giây
select relname as bang,
indexrelname as chi_muc,
idx_scan as so_lan_dung,
pg_size_pretty(pg_relation_size(indexrelid)) as nang
from pg_stat_user_indexes
where idx_scan = 0
and indexrelid not in (select conindid from pg_constraint where contype in ('p','u'))
order by pg_relation_size(indexrelid) desc
limit 10;
Câu này liệt kê những chỉ mục chưa được dùng lần nào kể từ lần thống kê gần nhất, đã loại các chỉ mục phục vụ khoá chính và ràng buộc duy nhất. Chỉ mục nào nặng vài trăm megabyte mà so_lan_dung bằng 0 thì bạn đang trả tiền đĩa và trả tiền tốc độ ghi cho một thứ không ai hỏi tới.
Phần sau chuyển sang chủ đề khác: giao dịch và mức cô lập.
