Sử dụng các chỉ mục và quét bảng thực hiện là hai cách tiếp cận cơ bản để truy cập dữ liệu trong cơ sở dữ liệu, mỗi phương pháp có sự đánh đổi riêng biệt tùy thuộc vào tình huống.
Một chỉ mục trong cơ sở dữ liệu là cấu trúc dữ liệu cho phép tra cứu nhanh hơn bằng cách cho phép hệ thống nhanh chóng định vị các hàng mà không cần quét mỗi hàng trong bảng. Hầu hết các cơ sở dữ liệu quan hệ sử dụng các cấu trúc cây B+ cho các chỉ mục, tổ chức các phím và con trỏ ở dạng cây. Điều này cho phép tìm kiếm, chèn và xóa trong độ phức tạp thời gian logarit $$ O (\ log n) $$, thường nhanh hơn nhiều so với quét toàn bộ bảng với độ phức tạp của $$ O (n) $$. Các chỉ mục có thể được phân cụm hoặc không phân cụm, với các chỉ mục được phân cụm lưu trữ dữ liệu theo thứ tự được sắp xếp vật lý, cải thiện hiệu suất quét phạm vi với chi phí chi phí thêm về sửa đổi dữ liệu. Các chỉ mục cũng có thể là tổng hợp, một phần, được lọc hoặc dựa trên băm, được điều chỉnh cho các mẫu truy vấn cụ thể.
Ngược lại, quét bảng (hoặc quét bảng đầy đủ) đọc từng hàng trong bảng tuần tự, bất kể tính chọn lọc của truy vấn. Điều này liên quan đến việc quét tất cả các khối dữ liệu của bảng và thường được coi là phương thức truy cập đắt nhất vì nó xử lý nhiều dữ liệu hơn mức cần thiết. Tuy nhiên, quét bảng có thể hoạt động tốt trong một số trường hợp nhất định. Ví dụ: khi các truy vấn lấy một tỷ lệ lớn các hàng, chi phí sử dụng chỉ mục (thường yêu cầu tra cứu thêm cho các hàng thực tế) có thể vượt quá chi phí quét toàn bộ bảng một lần. Quét bảng có thể sử dụng các lần đọc đa khối, cho phép đọc các khối dữ liệu lớn với ít hoạt động I/O hơn, do đó giảm độ trễ so với đọc nhiều khối riêng lẻ theo yêu cầu ngẫu nhiên bằng cách quét chỉ mục.
Một sự đánh đổi chính liên quan đến tính chọn lọc và kích thước của tập dữ liệu được trả về bởi truy vấn. Nếu truy vấn lọc xuống một số lượng nhỏ hàng (độ chọn lọc cao), các chỉ mục thường vượt trội so với các lần quét bảng vì chúng chỉ cần truy cập dữ liệu liên quan. Nhưng khi tỷ lệ phần trăm của các hàng được trả lại tăng, chi phí của chỉ số quét tăng do có thể yêu cầu nhiều lần tra cứu chính và công cụ cơ sở dữ liệu phải thực hiện các hoạt động I/O ngẫu nhiên bổ sung. Ở một số ngưỡng, thường khoảng 10-20% các hàng của bảng nhưng phụ thuộc vào độ rộng dữ liệu và phần cứng, việc quét bảng đầy đủ trở nên hiệu quả hơn. Điều này là do chi phí quét vẫn không đổi bất kể tính chọn lọc, chỉ cần đọc bảng tuần tự một lần.
Các lần quét chỉ mục thường đọc ít trang hơn so với quét bảng khi các cột được bảo hiểm ít hoặc nhỏ gọn hơn so với các hàng bảng đầy đủ. Chẳng hạn, một chỉ mục có thể chỉ bao gồm các cột được lập chỉ mục mà không có dữ liệu hàng bảng đầy đủ, làm cho nó mỏng hơn và cho phép nhiều hàng hơn phù hợp với mỗi trang cơ sở dữ liệu. Điều này làm giảm chi phí I/O khi quét chỉ mục so với quét toàn bộ dữ liệu bảng. Ngoài ra, một số chỉ mục có thể được lọc (chỉ mục một phần) để loại trừ các hàng không liên quan, tiếp tục giảm dấu chân quét.
Mặt khác, quét bảng đầy đủ viết ít gánh nặng hơn về phía bảo trì cơ sở dữ liệu. Các chỉ mục giới thiệu chi phí trong các hoạt động sửa đổi dữ liệu như chèn, cập nhật và xóa. Mọi thay đổi đối với bảng đều yêu cầu cập nhật các chỉ mục, đôi khi dẫn đến tăng độ trễ ghi và chi phí lưu trữ đặc biệt nếu nhiều chỉ mục tồn tại trên bảng. Chi phí này cũng có thể ảnh hưởng đến sự đồng thời và dẫn đến sự tranh chấp trong môi trường viết nặng. Do đó, quét bảng, chỉ cần đọc dữ liệu theo thứ tự tự nhiên mà không cần bảo trì cấu trúc bổ sung, hãy tránh chi phí này.
Một xem xét quan trọng khác là ảnh hưởng của bộ nhớ đệm và đặc tính phần cứng. Quét bảng được hưởng lợi từ I/O tuần tự và việc tìm nạp trước, cho phép hệ thống đọc nhiều khối liền kề một cách hiệu quả, thường là từ bộ nhớ nếu được lưu trữ. Ngược lại, chỉ mục quét I/O ngẫu nhiên để tìm nạp các khối dữ liệu khác nhau, đặc biệt là nếu việc quét chỉ mục phải tra cứu các con trỏ hàng vào lưu trữ heap. Điều này có thể làm cho chỉ số quét chậm hơn trên các hệ thống với hiệu suất I/O ngẫu nhiên chậm hơn, mặc dù SSD và nhóm bộ nhớ lớn thu hẹp khoảng cách này. Tình huống cũng có thể phụ thuộc vào các chi tiết cụ thể như tính song song và khả năng đa luồng của công cụ cơ sở dữ liệu, trong đó quét bảng song song có thể tăng đáng kể thông lượng.
Ngoài ra, sự phân mảnh nội bộ và bố cục lưu trữ vật lý ảnh hưởng đến sự đánh đổi hiệu suất. Các lần quét bảng trên các bảng được tổ chức bởi Heap có thể bị ảnh hưởng bởi các bản ghi được chuyển tiếp, trong đó các hàng đã chuyển sang các trang khác nhau do cập nhật, hiệu quả quét ngày càng tồi tệ. Các chỉ mục được phân cụm, lưu trữ dữ liệu được sắp xếp theo khóa, có thể tránh được vấn đề này và đôi khi tạo ra "quét bảng" tương đương với quét chỉ mục cụm. Tuy nhiên, các lợi ích đi kèm với chi phí của việc sắp xếp lại hàng đắt tiền trong quá trình khuấy dữ liệu nặng.
Từ góc độ tối ưu hóa truy vấn, quyết định giữa quét chỉ mục và quét bảng thường được thực hiện bởi các mô hình ước tính dựa trên chi phí, có tính đến số liệu thống kê về phân phối dữ liệu, số lượng hàng và chi phí phần cứng. Trình tối ưu hóa cân bằng CPU, I/O và chi phí bộ nhớ để chọn đường dẫn truy cập hiệu quả nhất. Những quyết định này có thể bị ảnh hưởng bởi các yếu tố như bộ nhớ có sẵn, trạng thái bộ nhớ đệm và các mẫu truy vấn. Không có ngưỡng cố định giữa khi nào nên sử dụng cái này hay cái kia; Điểm chéo thay đổi trên mỗi hệ thống và khối lượng công việc.
Tóm lại, sự đánh đổi giữa việc sử dụng các chỉ mục và quét bảng bao gồm:
- Hiệu suất so với khối lượng dữ liệu: Chỉ số vượt trội hơn khi lọc đến một vài hàng; Quét bảng có thể tốt hơn để truy xuất dữ liệu lớn.
- Các mẫu I/O: Quét chỉ mục gây ra các lần đọc I/O ngẫu nhiên; Quét bảng được hưởng lợi từ I/O tuần tự và các lần đọc đa khối.
- Chi phí bảo trì: Các chỉ mục tăng chi phí hoạt động ghi do cập nhật về cấu trúc chỉ mục; Quét bảng không phát sinh điều này.
- Hiệu quả lưu trữ: Các chỉ mục có thể nhỏ gọn bằng cách bao gồm ít cột hơn; Bảng quét xử lý các hàng đầy đủ và có khả năng nhiều dữ liệu hơn.
- Hiệu ứng bộ đệm: Quét bảng có thể sử dụng bộ nhớ đệm dữ liệu một cách hiệu quả, đặc biệt là với các lần đọc tuần tự lớn; Quét chỉ mục có thể không được hưởng lợi nhiều do truy cập ngẫu nhiên.
- Quyết định tối ưu hóa: Trình tối ưu hóa truy vấn dựa trên chi phí Lựa chọn tự động giữa các tùy chọn này dựa trên số liệu thống kê truy vấn và chi tiết khối lượng công việc.
- Tác động của bố cục dữ liệu: Bảng HEAP có thể phải chịu các hình phạt như hồ sơ được chuyển tiếp trong quá trình quét; Các chỉ mục cụm tổ chức dữ liệu về thể chất nhưng tăng chi phí cập nhật.