BRIN, GiST và tương quan vật lý

B-tree là chỉ mục mặc định và trong mười sáu phần trước nó luôn thắng. PostgreSQL còn năm kiểu chỉ mục nữa. Phần này đo hai kiểu hay được nhắc tới nhất cho dữ liệu theo thời gian — BRIN và GiST — trên cùng một bảng 10 triệu dòng, và tìm ra điều kiện duy nhất khiến BRIN đáng dùng.

Bảng đo

Mười triệu bản ghi sự kiện, mỗi bản ghi cách nhau 15 giây, trải từ tháng 1/2024 đến tháng 10/2028:

create table sk(
  id  bigserial primary key,
  luc timestamptz,
  may int,
  muc text,
  so  int
);

insert into sk(luc, may, muc, so)
select timestamptz '2024-01-01' + (i * interval '15 seconds'),
       (i % 50) + 1,
       (array['info','warn','error'])[1 + (i % 3)],
       i % 10000
from generate_series(1, 10000000) i;

Bảng chiếm 574 MB, tức 73.530 trang. Vì dữ liệu được chèn đúng thứ tự thời gian, pg_stats.correlation của cột luc bằng 1,000 — con số này sẽ quyết định toàn bộ phần còn lại của bài.

Dựng ba chỉ mục

create index ix_bt   on sk (luc);
create index ix_brin on sk using brin (luc);
create index ix_gist on sk using gist (luc);

Câu thứ ba không chạy:

ERROR:  data type timestamp with time zone has no default operator class
        for access method "gist"

GiST không biết so sánh timestamptz. Phải cài btree_gist trước — chính cái tên đó đã nói ra mục đích thật của nó: mượn ngữ nghĩa B-tree để nhét kiểu vô hướng vào một chỉ mục GiST, thường là để dùng chung với một cột kiểu khoảng trong ràng buộc loại trừ. Nó không sinh ra để thay B-tree.

BRIN nhỏ hơn B-tree 6.850 lần và nhỏ hơn bảng dữ liệu 18.000 lần. GiST thì to hơn cả bảng nó đánh chỉ mục, và mất 42,79 giây — chậm gấp 29 lần B-tree cho một kết quả tệ hơn về mọi mặt.

Con số 32 kB không phải lỗi đánh máy. BRIN không lưu từng dòng. Nó chia bảng thành các vùng 128 trang liên tiếp rồi chỉ ghi lại giá trị nhỏ nhất và lớn nhất trong mỗi vùng. 73.530 trang chia 128 ra 575 vùng, mỗi vùng vài chục byte.

Truy vấn: B-tree thắng cả ba mức

Lọc một ngày (5.760 dòng, 0,06% bảng):

Lọc một tháng (172.800 dòng, 1,7%):

Lọc một năm (2.102.400 dòng, 21%):

B-tree nhanh hơn ở cả ba mức. BRIN chậm hơn 2,2 lần ở một ngày, 2,7 lần ở một tháng, và gần như hoà ở một năm. Đó là cái giá của việc chỉ nhớ min–max: BRIN không chỉ ra dòng nào khớp, nó chỉ loại được những vùng chắc chắn không khớp, rồi PostgreSQL phải đọc hết các vùng còn lại và kiểm lại từng dòng. Ở phép lọc một ngày, BRIN đọc 148 trang để lấy về 5.760 dòng và loại bỏ 11.648 dòng trong bước kiểm lại.

Vậy tại sao còn dùng BRIN? Vì cột "kích thước".

Chi phí ghi

Chèn một triệu dòng vào bảng rỗng, lặp ba lần:

BRIN nằm gọn trong dải nhiễu của bảng không có chỉ mục nào, và chỉ sinh thêm 1 MB WAL. B-tree đắt hơn 63 MB WAL cho cùng một triệu dòng. GiST tốn gấp bốn lần thời gian và gấp ba lần WAL.

Đây mới là chỗ BRIN có nghĩa. Trên một bảng log 500 GB ghi liên tục, B-tree sẽ ngốn 180 GB đĩa và làm mỗi lần ghi chậm thêm 15%; BRIN tốn vài megabyte và gần như miễn phí lúc ghi. Đổi lại truy vấn chậm hơn hai, ba lần — nhưng chậm hơn ba lần vẫn tốt hơn Seq Scan 260 ms rất nhiều.

Vách đá: tương quan vật lý

Toàn bộ lợi thế trên đứng trên một giả định — các dòng gần nhau về thời gian thì cũng nằm gần nhau trên đĩa. Xoá giả định đó đi:

create table sk_xao as select * from sk order by random();
create index xb on sk_xao using brin (luc);

Bảng mới có cùng số dòng, cùng dữ liệu, cùng kích thước chỉ mục 32 kB. Chỉ khác thứ tự vật lý:

Chậm 234 lần. Cùng một chỉ mục, cùng một câu lệnh, cùng một lượng dữ liệu.

Lý do nằm trong định nghĩa của BRIN. Khi các dòng được xáo trộn, mỗi vùng 128 trang chứa mẫu ngẫu nhiên từ toàn bộ dải thời gian, nên min–max của vùng nào cũng bao trùm cả 4 năm. Không vùng nào bị loại. PostgreSQL đọc hết 73.556 trang rồi kiểm lại 3,3 triệu dòng để giữ đúng 5.760 dòng.

Và tệ hơn: nó chậm hơn cả khi không có chỉ mục.

BRIN vô dụng ở đây tốn thêm 50% thời gian so với việc bỏ hẳn nó đi — đó là chi phí dựng bitmap và kiểm lại, làm thêm mà không loại được gì.

Điều đáng sợ là kiểu chết này hoàn toàn im lặng. EXPLAIN vẫn ghi Bitmap Heap Scan using xb, không có cảnh báo, không có log. Chỉ số duy nhất báo trước là pg_stats.correlation:

select correlation from pg_stats where tablename = 'sk_xao' and attname = 'luc';

Phần 10 đã dùng chính con số này để giải thích vì sao bộ lập lịch ước lượng sai; ở đây nó quyết định thẳng một chỉ mục có tác dụng hay không.

Sai lầm khi đo: hai chỉ mục cùng tồn tại

Tôi định đo xem chỉnh pages_per_range có đáng không, nên tạo lần lượt sáu chỉ mục BRIN với sáu giá trị khác nhau. Kết quả bốn dòng đầu:

  ppr=1     2472 kB   1,15 ms   148 trang   kiem lai bo 11.648
  ppr=8      320 kB   1,00 ms   148 trang   kiem lai bo 11.648
  ppr=32      88 kB   1,06 ms   148 trang   kiem lai bo 11.648
  ppr=128     32 kB   1,03 ms   148 trang   kiem lai bo 11.648

Kích thước chênh nhau 77 lần mà số trang đọc và số dòng kiểm lại giống hệt tới từng đơn vị. Không có cách nào một chỉ mục 2.472 kB và một chỉ mục 32 kB lại chọn ra đúng cùng một tập trang.

ix_brin từ phần đo trước vẫn còn trên bảng. Bộ lập lịch nhìn thấy hai chỉ mục BRIN, chọn cái rẻ hơn, và mọi số đo của tôi đều là số đo của cùng một chỉ mục mặc định. Đây đúng cái bẫy đã vấp ở phần 12 — khi có nhiều chỉ mục dùng được, bộ lập lịch chọn cái nhỏ nhất, và cái bạn tưởng đang đo thì không hề được đụng tới.

Dấu hiệu nhận ra không phải là con số sai, mà là con số giống nhau quá mức. Hai cấu hình khác nhau cho ra kết quả lệch nhau vài phần trăm thì còn tin được; cho ra 11.648 y hệt bốn lần thì chỉ có thể là chúng chạy cùng một thứ.

Bỏ hết chỉ mục cũ, mỗi lần chỉ giữ đúng một:

Giờ mới ra đường cong chữ U thật. Hai đầu đều tệ vì hai lý do trái ngược nhau:

Vùng quá nhỏ cho độ chính xác cao nhất — ppr=1 chỉ loại nhầm 88 dòng thay vì 11.648 — nhưng chỉ mục phồng lên 2.472 kB và PostgreSQL phải quét toàn bộ chỉ mục đó trước khi chạm vào bảng. Trong 889 trang đọc được, phần lớn là chính chỉ mục. Nó vừa mất lợi thế dung lượng vừa chậm hơn.

Vùng quá lớn thì mỗi vùng ôm một khoảng thời gian rộng, nên hầu như vùng nào cũng giao với điều kiện lọc. ppr=2048 đọc 2.066 trang và loại bỏ 90.923 dòng để lấy 5.760 dòng.

Mặc định 128 nằm ở phía phải của điểm tối ưu trong trường hợp này. Chỉnh xuống 32 nhanh hơn 15% và vẫn chỉ tốn 88 kB. Nhưng điểm tối ưu phụ thuộc vào mật độ dữ liệu và độ rộng khoảng lọc — không có con số đúng cho mọi bảng, chỉ có cách đo trên chính bảng của bạn.

Chọn kiểu nào

Một lưu ý về correlation: nó không cố định. Bảng log hôm nay có correlation 1,000 vẫn có thể tụt xuống sau vài tháng UPDATE, hoặc sau một lần CLUSTER theo cột khác. BRIN không hỏng ngay — nó chậm dần, mỗi ngày một ít, không kèm bất kỳ tín hiệu nào.

Thử ba mươi giây

Trên bảng lớn nhất mà bạn đang có:

select attname, round(correlation::numeric, 3) as tuong_quan
from pg_stats
where tablename = 'ten_bang_cua_ban'
  and correlation is not null
order by abs(correlation) desc
limit 5;

Cột nào gần 1,000 hoặc gần −1,000 là ứng viên BRIN. Cột nào quanh 0 thì đừng thử — bạn sẽ dựng ra một chỉ mục 32 kB làm mọi truy vấn chậm hơn cả việc không có gì.

Phần sau đo HASH và các kiểu chỉ mục còn lại, để xem chúng có chỗ đứng nào không.