Tối ưu hóa truy vấn trong các hệ thống tập trung

Khi các đường dẫn truy cập thay thế để tính toán biểu thức đại số quan hệ được bắt nguồn, thì đường dẫn truy cập tối ưu được xác định. Trong chương này, chúng ta sẽ xem xét tối ưu hóa truy vấn trong hệ thống tập trung trong khi trong chương tiếp theo chúng ta sẽ nghiên cứu tối ưu hóa truy vấn trong hệ thống phân tán.

Trong một hệ thống tập trung, xử lý truy vấn được thực hiện với mục đích sau:

Giảm thiểu thời gian phản hồi của truy vấn (thời gian cần thiết để tạo ra kết quả cho truy vấn của người dùng).
Tối đa hóa thông lượng hệ thống (số lượng yêu cầu được xử lý trong một khoảng thời gian nhất định).
Giảm dung lượng bộ nhớ và dung lượng lưu trữ cần thiết để xử lý.
Tăng tính song song.

Phân tích cú pháp và dịch truy vấn

Ban đầu, truy vấn SQL được quét. Sau đó, nó được phân tích cú pháp để tìm kiếm các lỗi cú pháp và tính đúng đắn của các kiểu dữ liệu. Nếu truy vấn vượt qua bước này, truy vấn được phân tách thành các khối truy vấn nhỏ hơn. Mỗi khối sau đó được dịch sang biểu thức đại số quan hệ tương đương.

Các bước để tối ưu hóa truy vấn

Tối ưu hóa truy vấn bao gồm ba bước, đó là tạo cây truy vấn, tạo kế hoạch và tạo mã kế hoạch truy vấn.

Step 1 − Query Tree Generation

Cây truy vấn là một cấu trúc dữ liệu dạng cây biểu diễn một biểu thức đại số quan hệ. Các bảng của truy vấn được biểu diễn dưới dạng các nút lá. Các phép toán đại số quan hệ được biểu diễn dưới dạng các nút bên trong. Gốc đại diện cho toàn bộ truy vấn.

Trong quá trình thực thi, một nút bên trong được thực thi bất cứ khi nào các bảng toán hạng của nó có sẵn. Sau đó, nút được thay thế bằng bảng kết quả. Quá trình này tiếp tục cho tất cả các nút bên trong cho đến khi nút gốc được thực thi và được thay thế bởi bảng kết quả.

Ví dụ, chúng ta hãy xem xét các lược đồ sau:

NHÂN VIÊN

EmpID	EName	Tiền lương	DeptNo	Ngày tham gia

PHÒNG BAN

DNo	DName	Vị trí

ví dụ 1

Chúng ta hãy xem xét truy vấn như sau.

$$ \ pi_ {EmpID} (\ sigma_ {EName = \ small "ArunKumar"} {(EMPLOYEE)}) $$

Cây truy vấn tương ứng sẽ là:

Ví dụ 2

Hãy để chúng tôi xem xét một truy vấn khác liên quan đến một phép nối.

$ \ pi_ {EName, Salary} (\ sigma_ {DName = \ small "Tiếp thị"} {(DEPARTMENT)}) \ bowtie_ {DNo = DeptNo} {(EMPLOYEE)} $

Sau đây là cây truy vấn cho truy vấn trên.

Step 2 − Query Plan Generation

Sau khi cây truy vấn được tạo, một kế hoạch truy vấn sẽ được thực hiện. Kế hoạch truy vấn là một cây truy vấn mở rộng bao gồm các đường dẫn truy cập cho tất cả các thao tác trong cây truy vấn. Các đường dẫn truy cập chỉ định cách thực hiện các phép toán quan hệ trong cây. Ví dụ, một thao tác lựa chọn có thể có một đường dẫn truy cập cung cấp thông tin chi tiết về việc sử dụng chỉ mục cây B + để lựa chọn.

Bên cạnh đó, một kế hoạch truy vấn cũng nêu rõ cách các bảng trung gian nên được chuyển từ toán tử này sang toán tử tiếp theo, cách bảng tạm thời nên được sử dụng và cách hoạt động nên được kết hợp / kết hợp.

Step 3− Code Generation

Tạo mã là bước cuối cùng trong tối ưu hóa truy vấn. Nó là dạng thực thi của truy vấn, có dạng phụ thuộc vào loại hệ điều hành cơ bản. Khi mã truy vấn được tạo, Trình quản lý thực thi sẽ chạy nó và tạo ra kết quả.

Các cách tiếp cận để tối ưu hóa truy vấn

Trong số các cách tiếp cận để tối ưu hóa truy vấn, các thuật toán dựa trên tìm kiếm toàn diện và dựa trên kinh nghiệm thường được sử dụng nhiều nhất.

Tối ưu hóa Tìm kiếm Hoàn toàn

Trong các kỹ thuật này, đối với một truy vấn, ban đầu tất cả các kế hoạch truy vấn có thể được tạo và sau đó kế hoạch tốt nhất được chọn. Mặc dù các kỹ thuật này cung cấp giải pháp tốt nhất, nhưng nó có độ phức tạp về không gian và thời gian theo cấp số nhân do không gian giải pháp lớn. Ví dụ, kỹ thuật lập trình động.

Tối ưu hóa Dựa trên Heuristic

Tối ưu hóa dựa trên heuristic sử dụng các phương pháp tối ưu hóa dựa trên quy tắc để tối ưu hóa truy vấn. Các thuật toán này có độ phức tạp về thời gian và không gian đa thức, thấp hơn độ phức tạp theo cấp số nhân của các thuật toán dựa trên tìm kiếm toàn diện. Tuy nhiên, các thuật toán này không nhất thiết phải tạo ra kế hoạch truy vấn tốt nhất.

Một số quy tắc heuristic phổ biến là:

Thực hiện các hoạt động chọn và dự án trước khi tham gia các hoạt động. Điều này được thực hiện bằng cách di chuyển các hoạt động chọn và dự án xuống cây truy vấn. Điều này làm giảm số lượng bộ giá trị có sẵn để tham gia.
Thực hiện các hoạt động chọn / dự án hạn chế nhất lúc đầu trước các hoạt động khác.
Tránh thao tác chéo sản phẩm vì chúng tạo ra các bảng trung gian có kích thước rất lớn.