Index giúp truy vấn nhanh hơn bằng cách nào?

Ở bài trước, PostgreSQL phải quét 192.308 page để tìm một chiếc xe theo biển số trong bảng có 5 triệu xe.

Nhưng nếu tìm chính chiếc xe đó bằng id thì sao?

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM vehicles WHERE id = 5000;

Kết quả:

Đọc kết quả EXPLAIN

1. Index Scan using vehicles_pkey on vehicles (actual rows=1.00 loops=1) PostgreSQL sử dụng index vehicles_pkey thay vì quét toàn bộ bảng. Truy vấn tìm được 1 dòng.
2. Index Cond: (id = 5000) Điều kiện id = 5000 được dùng để tìm trong index.
3. Index Searches: 1 PostgreSQL thực hiện một lượt tìm kiếm trong index.
4. Buffers: shared hit=4 Chỉ có 4 lượt truy cập page trong shared buffers, tất cả đều tìm thấy trong RAM.

Dòng Buffers: shared hit=4 cho biết truy vấn này chỉ cần 4 lượt truy cập page trong bộ đệm của PostgreSQL. Trong ví dụ này, đó là 3 page của index và 1 page của bảng.

Cùng một bảng, cùng một chiếc xe 25F-950.00, nhưng số page cần truy cập khác nhau rất lớn.

Lý do là cột id có index, còn cột plate thì chưa.

id là khoá chính (primary key), nên PostgreSQL tự tạo index cho cột này khi tạo bảng. Nhờ đó, nó có thể xác định vị trí chiếc xe mà không cần kiểm tra lần lượt cả 5 triệu dòng.

Tạo index cho biển số

Thử tạo một index cho cột plate:

CREATE INDEX vehicles_plate_idx ON vehicles (plate);

Sau đó chạy lại câu truy vấn của bài trước:

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM vehicles WHERE plate = '25F-950.00';

Đọc kết quả EXPLAIN

1. Index Scan using vehicles_plate_idx on vehicles (actual rows=1.00 loops=1) PostgreSQL dùng index vehicles_plate_idx để tìm xe thay vì quét toàn bộ bảng.
2. Index Cond: (plate = '25F-950.00'::text) Điều kiện biển số được dùng để tìm trong index, thay vì kiểm tra từng dòng bằng Filter như bài trước.
3. Index Searches: 1 Một lượt tìm kiếm trong index.
4. Buffers: shared hit=4 Truy vấn cần 4 lượt truy cập page trong shared buffers, gồm 3 page của index và 1 page của bảng trong ví dụ này.

Kế hoạch thực thi đã chuyển từ Seq Scan sang Index Scan. Số lượt truy cập page trong lần đo này giảm từ 192.308 xuống còn 4.

Tạo thêm một index đã tạo ra sự khác biệt lớn như vậy. Nhưng index làm điều đó bằng cách nào?

Bên trong index có gì?

Khi tạo index cho plate, PostgreSQL xây dựng một cấu trúc riêng, trong đó các biển số được sắp xếp theo thứ tự. Mỗi biển số còn đi kèm thông tin để xác định dòng dữ liệu tương ứng nằm ở đâu trong bảng.

Nhưng nếu index chứa tới 5 triệu biển số, PostgreSQL có phải đọc lần lượt 5 triệu mục đó để tìm một biển số không?

Không. PostgreSQL tổ chức index thành một cây B-tree.

Cây này có nhiều tầng. Những tầng phía trên chứa các giá trị mốc giúp PostgreSQL xác định cần đi xuống nhánh nào. Tầng cuối chứa các biển số cùng vị trí của những dòng tương ứng.

Với index trên bảng 5 triệu xe trong ví dụ này, cây B-tree có 3 tầng.

Khi tìm 25F-950.00, PostgreSQL đi qua các tầng theo thứ tự:

1. Page thứ nhất: đọc tầng trên cùng, so sánh biển số cần tìm với các mốc và chọn nhánh phù hợp.
2. Page thứ hai: đọc tầng tiếp theo, tiếp tục thu hẹp phạm vi tìm kiếm.
3. Page thứ ba: đến tầng cuối, tìm thấy 25F-950.00 cùng vị trí dòng dữ liệu trong bảng.
4. Page thứ tư: dùng vị trí vừa tìm được để truy cập page của bảng chứa chiếc xe và lấy toàn bộ thông tin của nó.

Đó là 4 page chúng ta thấy trong kết quả EXPLAIN ở trên.

PostgreSQL không cần duyệt qua 5 triệu biển số. Nó chỉ đi qua những page nằm trên đường dẫn đến biển số cần tìm, rồi truy cập thêm page chứa dữ liệu thật.

B-tree là kiểu index mặc định của PostgreSQL. Khi chạy CREATE INDEX mà không chỉ định kiểu khác, PostgreSQL sẽ sử dụng B-tree.

Nhưng có một chi tiết vẫn chưa được giải thích: index lưu vị trí của mỗi dòng dữ liệu như thế nào, và PostgreSQL dựa vào vị trí đó để tìm đúng dòng bằng cách nào?

Muốn trả lời, trước tiên cần biết một dòng dữ liệu thực sự được lưu như thế nào bên trong file của PostgreSQL.

Một dòng dữ liệu nằm ở đâu trong file?