Vì sao nhiều dòng khớp thì Index Scan có thể chậm?

Ở bài trước, PostgreSQL tìm được một chiếc xe qua index, sau đó truy cập heap để lấy dữ liệu.

Nếu cần tìm nhiều xe cùng lúc thì sao?

Thử tìm tất cả xe có biển số bắt đầu bằng 47P-6:

SELECT * FROM vehicles
WHERE plate >= '47P-600' AND plate < '47P-700';

Kết quả có 214 chiếc xe.

Trong index trên cột plate, 214 biển số này nằm gần nhau, chỉ trải trên hai page lá. PostgreSQL có thể tìm được địa chỉ của chúng khá nhanh.

Nhưng khi dùng những địa chỉ đó để đọc dữ liệu trong bảng, một vấn đề xuất hiện.

Biển số nằm gần nhau trong index, nhưng xa nhau trong heap

Index sắp xếp các biển số theo thứ tự. Còn heap không sắp xếp dữ liệu theo biển số.

Trong bảng vehicles của chúng ta, các xe được thêm vào theo thời gian đăng bán. Vì vậy, hai chiếc xe có biển số gần nhau chưa chắc nằm gần nhau trong heap.

Kết quả là 214 chiếc xe nằm rải rác trên 172 heap page khác nhau, từ đầu đến cuối bảng.

214 biển số liền nhau trong index nằm ở đâu trong heap

WHERE plate >= '47P-600' AND plate < '47P-700'

Các page heap chứa 214 biển số đó

page 0page 192.307

page heap khác nhau

172

Với Index Scan thông thường, PostgreSQL lấy địa chỉ từ index rồi truy cập heap để tìm dòng tương ứng. Sau đó tiếp tục với địa chỉ tiếp theo.

Nếu các địa chỉ nằm rải rác, PostgreSQL phải liên tục truy cập những page ở các vị trí khác nhau trong bảng. Có khi nó còn phải quay lại một page vừa truy cập để lấy dòng khác.

Một page đã có trong bộ nhớ đệm thì không phải đọc lại từ ổ đĩa, nhưng việc truy cập dữ liệu rải rác vẫn có thể tốn kém.

Với 214 xe thì chưa phải vấn đề lớn. Nhưng nếu tìm vài chục nghìn xe nằm khắp bảng, chi phí này có thể tăng đáng kể.

Có cách nào gom các dòng nằm chung page lại, thay vì đọc từng địa chỉ theo thứ tự index không?

Bitmap Scan: Gom địa chỉ trước, đọc bảng sau

PostgreSQL có một cách khác.

Thay vì tìm được một địa chỉ rồi lập tức truy cập heap, nó thu thập các địa chỉ khớp trước. Sau đó tổ chức chúng theo số heap page và đọc những page cần thiết theo thứ tự.

Cách này gồm hai bước:

Bước 1: Bitmap Index Scan

PostgreSQL đọc index để tìm các dòng khớp điều kiện. Nhưng thay vì lấy dữ liệu từ heap ngay, nó tạo một bitmap trong bộ nhớ để ghi nhận vị trí các dòng cần đọc.

Bước 2: Bitmap Heap Scan

Dựa vào bitmap vừa tạo, PostgreSQL truy cập các heap page theo thứ tự page, rồi lấy những dòng cần thiết bên trong.

Quay lại 214 chiếc xe nằm trên 172 page. Với Bitmap Heap Scan, PostgreSQL có thể đọc từng page trong số 172 page đó một lần, kể cả khi một page chứa nhiều xe khớp điều kiện.

Nhờ vậy, nó tránh việc đọc heap theo một chuỗi địa chỉ rải rác do index trả về.

Đổi lại, PostgreSQL phải tốn thêm thời gian và bộ nhớ để tạo bitmap. Dòng trả về cũng không còn theo thứ tự của index.

Vì vậy, PostgreSQL không phải lúc nào cũng chọn Bitmap Scan. Nó sẽ ước tính cách nào ít tốn kém hơn: Index Scan, Bitmap Scan hay thậm chí đọc toàn bộ bảng bằng Sequential Scan.

Thử xem PostgreSQL dùng Bitmap Scan như thế nào

Tạo một index trên cột province, rồi tìm tất cả xe ở Lai Châu:

CREATE INDEX vehicles_province_idx ON vehicles (province);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM vehicles WHERE province = 'Lai Châu';

Trong dữ liệu thử nghiệm, có 24.912 xe ở Lai Châu.

PostgreSQL chọn Bitmap Scan. Kết quả EXPLAIN rút gọn như sau:

Đọc kết quả EXPLAIN của câu Lai Châu

1. Bitmap Heap Scan on vehicles (actual rows=24912.00 loops=1) Đọc dữ liệu từ heap và trả về 24.912 dòng. Bước này sử dụng các vị trí đã được bước Bitmap Index Scan tìm ra.
2. Recheck Cond: (province = 'Lai Châu'::text) Điều kiện PostgreSQL có thể dùng để kiểm tra lại dòng. Không có nghĩa mọi dòng đều được kiểm tra lại. Việc này cần thiết khi bitmap chỉ còn nhớ page nào khớp mà không nhớ chính xác từng vị trí dòng, hoặc khi index trả về kết quả chưa chắc chắn.
3. Heap Blocks: exact=23402 PostgreSQL đã truy cập 23.402 heap page. Chữ exact nghĩa là bitmap vẫn giữ được chính xác vị trí các dòng cần tìm trong những page đó. Đây không phải số lần đọc từ ổ đĩa.
4. -> Bitmap Index Scan on vehicles_province_idx Bước chạy trước: tìm những dòng khớp trong index và ghi nhận vị trí của chúng vào bitmap.
5. Index Cond: (province = 'Lai Châu'::text) Điều kiện dùng để tìm trong index: chỉ lấy những địa chỉ thuộc tỉnh Lai Châu.

Đọc từ dưới lên, PostgreSQL làm hai việc:

Đầu tiên, Bitmap Index Scan tìm các xe ở Lai Châu và ghi nhận vị trí của chúng.

Sau đó, Bitmap Heap Scan truy cập những page chứa các xe này để lấy dữ liệu thật.

Hai con số đáng chú ý là:

• actual rows=24912: tìm được 24.912 xe.
• Heap Blocks: exact=23402: phải truy cập 23.402 heap page.

Như vậy, gần 25.000 chiếc xe nằm trên hơn 23.000 page khác nhau. Dù PostgreSQL đã gom địa chỉ và đọc theo thứ tự page, nó vẫn phải truy cập rất nhiều page để lấy đủ dữ liệu.

Còn dòng Recheck Cond thì sao?

Thông thường, bitmap nhớ chính xác những dòng cần đọc trong từng page. Nhưng nếu bitmap quá lớn so với bộ nhớ dành cho nó, PostgreSQL có thể chỉ giữ thông tin page nào chứa dòng khớp. Khi đó, lúc đọc page, nó phải kiểm tra lại điều kiện để biết chính xác dòng nào cần lấy.

Trong kết quả này, exact=23402 cho thấy bitmap vẫn giữ được vị trí dòng chính xác. Vì vậy, với index B-tree trên province, không cần kiểm tra lại điều kiện cho từng dòng chỉ vì có dòng Recheck Cond trong kế hoạch.

Bitmap Scan giúp giảm chi phí truy cập heap bằng cách gom các địa chỉ và đọc theo thứ tự page. Nhưng nó vẫn phải vào heap để lấy dữ liệu.

Nếu câu SQL chỉ cần một vài cột và tất cả đã có sẵn trong index, liệu PostgreSQL có thể bỏ qua heap hoàn toàn không?

Index đã có đủ cột, sao vẫn phải vào heap?