Hộp phiếu của thư viện giúp tìm sách nhanh hơn khoảng 79 lần, nhưng không phải lúc nào cũng vậy. Đo thật trên 100.000 cuốn sách.
Mở từng cuốn trong 100.000 cuốn xem có đúng tác giả không. Chậm, nhưng không cần chuẩn bị gì.
Phiếu đã xếp sẵn theo tác giả, mỗi phiếu ghi sách nằm ở kệ nào. Nhanh, nhưng phải làm và giữ đúng mỗi khi nhập sách.
Cả kho sách xếp thành hàng. Mỗi hàng là một cuốn, các cột là tên sách, tác giả, năm.
Đi dọc mọi kệ, mở từng cuốn để xem có phải thứ cần tìm không.
Hộp phiếu tra cứu xếp sẵn theo tác giả, mỗi phiếu ghi sách nằm ở đâu.
Lời thủ thư nói trước: sẽ tra hộp phiếu hay sẽ đi dọc mọi kệ.
Một điều kiện loại bỏ được bao nhiêu hàng. “Còn hàng” gần như không loại gì.
Hộp phiếu hai tầng: trước theo thể loại, trong mỗi thể loại theo năm.
100.000 cuốn, mỗi tác giả khoảng 50 cuốn, 200 lần đo lấy trung vị, SQLite 3.53.4 trong bộ nhớ.
nhanh hơn (4 lần chạy cho 75 đến 82 lần)
Đi qua mọi hàng. Chậm dần khi bảng lớn lên.
Dùng chỉ mục. Dấu ngoặc cho biết điều kiện nào được dùng.
WHERE in_stock = 1: 89.966 hàng kết quả, khoảng 90% bảng.
Truy vấn vẫn phải lấy gần cả bảng. Việc chính là đọc và chuyển 89.966 hàng, tra chỉ mục không bớt được phần đó. Đây là cách giải thích của tôi, chưa tách riêng từng bước.
Với in_stock = 0 (10% số hàng): 5,55 ms so với 5,03 ms, chỉ nhanh hơn khoảng 9%.
| Chỉ mục | Truy vấn A: genre và year | Truy vấn B: chỉ year |
|---|---|---|
| (genre, year) | 0,437 ms · SEARCH | 2,067 ms · SCAN |
| (year, genre) | 0,561 ms · SEARCH | 0,694 ms · SEARCH |
Không có chỉ mục nhiều cột thì truy vấn A quét 3,124 ms.
Hộp phiếu hai tầng, trước thể loại rồi tới năm. Hỏi “tech, từ 2020” thì đi thẳng tới ngăn tech. Hỏi “mọi sách năm 2015” thì năm 2015 rải rác ở mọi ngăn.
Nếu cả hai điều kiện là dấu bằng, cả hai thứ tự đều dùng đủ hai cột: 0,07 ms so với 1,6 ms khi quét.
Thêm 20.000 hàng vào bảng 100.000 hàng, trung vị 7 lần, trong bộ nhớ.
Chậm hơn 2,2 lần và 5 lần. Hãy dùng số này để thấy hướng, không để dự báo.
Minh họa: giả định thời gian quét tăng đều theo số hàng. Đây là phép nhân, không phải số đo.
Một lượt tìm tác giả trên 5 triệu sách có thể mất khoảng 110 ms thay vì 2,2 ms.
Tra chỉ mục đi qua vài tầng của một cây tìm kiếm (theo tài liệu PostgreSQL), nên tăng rất chậm theo số hàng.
Chỉ mục là hộp phiếu: rất nhanh khi câu hỏi khớp cách xếp, vô dụng khi không khớp, và luôn tốn công giữ. Với truy vấn do AI viết, hãy đòi chính kế hoạch đó làm bằng chứng.