Bộ tối ưu hóa câu hỏi

Tổng quan

Quy trình xử lí truy vấn: Câu lệnh SQL --(Phân tích cú pháp)--> biểu thức đại số quan hệ --(bộ tối ưu)--> Bộ sinh mã --> Chương trình tối ưu
Tối ưu hóa là biến đổi biểu thức đại số quan hệ để tìm một biểu thức hiệu quả hơn
Tối ưu hóa dựa trên cấu trúc và nội dung của dữ liệu
2 kỹ thuật chính:
- Tối ưu logic
- Tối ưu vật lý
Mục đích:
- Giảm số bản ghi
- Giảm kích thước bản ghi

Mục đích:
- Dựa trên ràng buộc dữ liệu để xác định biểu thức tương đương
- Viết lại truy vấn dựa trên khung nhìn với các định nghĩa của khung nhìn

σ_{F_{1} \land F_{2} \land \dots \land F_{n}} (R) = σ_{F_{1}} (σ_{F_{2}} (\dots (σ_{F_{n}} (R))))

Hoán vị phép chọn với phép tích Descartes, hợp, trừ, với mục đích đẩy phép chọn thực hiện trước nhằm giảm số bản ghi từ sớm:

σ_{F (X)} (Π_{Y} (R)) = Π_{Y} (σ_{F (X)} (R)) (X \subseteq Y)

σ_{F (Z)} (R (X) \times S (Y)) = σ_{F (Z)} (R (X)) \times S (Y) (Z \subseteq X)

σ_{F_{1} (Z_{1}) \land F_{2} (Z_{2})} (R (X) \times S (Y)) = σ_{F_{1} (Z_{1})} (R (X)) \times σ_{F_{2} (Z_{2})} (S (Y)) (Z_{1} \subseteq X, Z_{2} \subseteq Y)

σ_{F} (R \cup S) = σ_{F} (R) \cup σ_{F} (S)

σ_{F} (R ∖ S) = σ_{F} (R) ∖ σ_{F} (S)

Hoán vị phép chiếu với tích Descartes, hợp với mục đích giảm kích thước bản ghi:

Π_{Z} (Π_{Y} (R)) = Π_{Z} (R) (Z \subseteq Y)

Π_{Y} (σ_{F (X)} (R)) = Π_{Y} (σ_{F (X)} (Π_{X \cup Y} (R))) X ⊈ Y

Π_{Z} (R (X) \times S (Y)) = Π_{X \cap Z} (R) \times Π_{Y \cap Z} (S)

Π_{Z} (R \cup S) = Π_{Z} (R) \cup Π_{Z} (S)

Lựa chọn với điều kiện phức AND:
- Ưu tiên điều kiện với thuộc tính có index
- Sử dụng composite index
- Sử dụng phép giao nếu có nhiều index
Lựa chọn với điều kiện phức OR:
- Không có nhiều khả năng tối ưu
- Sử dụng nếu có index trên tất cả các thuộc tính
Phép kết nối
- Nested-loop JOIN: chi phí thời gian cao
- Single-loop JOIN: sử dụng khi tồn tại index cho một hoặc cả hai thuộc tính trong điều kiện JOIN
- Sort-merge JOIN: sử dụng khi hai bảng được lưu trữ dưới dạng sorted file, sắp xếp theo thuộc tính điều kiện kết nối
- Partition-hash JOIN: chia bảng thành các giỏ (buckets) và join các giỏ tương ứng