Bài giảng Cơ sở dữ liệu - Chương 6: Tối ưu hoá câu hỏi

Nội dung text: Bài giảng Cơ sở dữ liệu - Chương 6: Tối ưu hoá câu hỏi

1. Tối ưu hoá câu hỏi
2. Xử lý câu hỏi truy vấn Câu lệnh SQL Phân tích Biểu thức cú pháp ĐSQH Biểu thức (parser) Bộ tối ưu ĐSQH (optimizer) tối ưu Bộ sinh mã (code generator) Chương trình tối ưu
3. Tối ưu hoá Biến đổi biểu thức ĐSQH để tìm 1 biểu thức hiệu quả Tối ưu dựa trên cấu trúc và nội dung của dữ liệu Nâng cao hiệu quả thực hiện câu hỏi trên 1 hay nhiều tiêu chí: thời gian, sử dụng bộ nhớ, Lưu ý:  Không nhất thiết phải tìm biểu thức tối ưu nhất  Chú ý tới tài nguyên sử dụng cho tối ưu
4. Kỹ thuật tối ưu hoá 2 kỹ thuật chính TYPE  Tối ưu logic (rewriting)  Tối ưu vật lý (access methods) Mục đích của các kỹ thuật tối ưu  Giảm số bản ghi  Giảm kích thước bản ghi NW Ví dụ WAGON WAGON (NW, TYPE, COND, STATION, (NW, TYPE ) CAPACITY, WEIGHT) NT = 4002 TRAIN (NT, NW) TRAIN (NT, NW)
5. Nội dung Giới thiệu chung  Tối ưu vật lý Mô hình giá Tối ưu logic
6. Lựa chọn cách truy nhập dữ liệu Giả thiết TYPE  TRAIN : có chỉ số trên NT  WAGON : có chỉ số trên NW Thực hiện phép kết nối  Lựa chọn 1 giải thuật.  Lựa chọn cách truy nhập các NW quan hệ WAGON (NW, TYPE ) NT = 4002 TRAIN (NT, NW)
7. Relation S Nested-loop-join (NLJ) Nguyên tắc  Duyệt 1 lần trên quan hệ Matching ngoài R & lặp trên quan hệ trong S Tuple R Các mở rộng của thuật toán  Tuple-based NLJ, block- based NLJ, index-based NLJ Tuple R Tuple S SOURCE SOURCE R S
8. Mô hình giá Chi phí thực hiện câu hỏi truy vấn phụ thuộc:  Đọc/ghi bộ nhớ ngoài (số trang nhớ)  Kích thước dữ liệu phải xử lý Chi phí :  Đọc/ghi dữ liệu  Xử lý  Truyền thông giữa các trạm CTA =  * NBPAGES +  * NBNUPLETS (+  * NBMESSAGES) Trọng số:  = trọng số đọc/ghi dữ liệu (ví dụ = 1)  = trọng số xử lý của CPU (ví dụ = 1/3)  = trọng số truyền dữ liệu
9. Tối ưu hoá dựa trên mô hình giá Mục đích: Chọn phương án thực hiện câu hỏi với chi phí thấp nhất Nhận xét:  Chi phí cho liệt kê các phương án trả lời câu hỏi  Chi phí cho lượng hoá các phương án theo mô hình giá  Có thể sử dụng các « mẹo » (heuristics) để giảm không gian tìm kiếm của câu hỏi
10. Đánh giá các biểu thức ĐSQH Vật chất hóa:  Ghi các kết quả trung gian  Chi phí đánh giá câu hỏi: + thời gian đọc/ghi DL trung gian Đường ống (pipelining):  Tổ chức các phép toán trong 1 đường ống  Kết quả ra của phép toán này được lấy ngay làm đầu vào cho phép toán kế tiếp  Không mất thời gian đọc/ghi DL trung gian  Không phải trường hợp nào cũng có thể thực hiện được
11. Nội dung Giới thiệu chung Tối ưu vật lý Mô hình giá  Tối ưu logic
12. Tối ưu hoá logic Sử dụng các phép biến đổi tương đương để tìm ra biểu thức ĐSQH tốt Gồm 2 giai đoạn  Biến đổi dựa trên ngữ nghĩa  Biến đổi dựa trên tính chất của các phép toán ĐSQH
13. Biến đổi dựa trên ngữ nghĩa Mục đích:  Dựa trên các ràng buộc dữ liệu để xác định các biểu thức tương đương  Viết lại câu hỏi trên khung nhìn dựa trên các định nghĩa của khung nhìn Ví dụ: EMPLOYEE (FirstName, LastName, SSN, Birthday, Adrresse, NoDept) DEPARTEMENT (DNO, DName, SSNManager) PROJECT (PNO, PName, PLocation, DNo) WORK-IN (ESSN, PNO, Heures)
14. EMPLOYEE (Name, SSN, Birthday, Adrresse, NoDept) DEPARTEMENT (DNO, DName, SSNManager) PROJECT (PNO, PName, PLocation, DNo) WORK-IN (ESSN, NoProj, Heures) Tên của các nhân viên sinh sau ngày 30/01/70 và làm việc cho dự án "Esprit" Result WORK-IN.ESSN = EMPLOYEE. Name SSN WORK-IN = PROJECT.PNO WORK-IN. NoProj = PNO PNO ESSN=SSN = PROJECT PROJECT.PName “Esprit” PName = “Esprit” EMPLOYEE. > EMPLOYE Birthday > “30/01/70 “30/01/70” Birthday Đồ thị kết nối các quan hệ Đồ thị kết nối các thuộc tính
15. Biến đổi dựa trên ngữ nghĩa Định nghĩa khung nhìn: V = R * S Câu truy vấn của client : Q = V * (T * U) Viết lại câu truy vấn dựa trên định nghĩa khung nhìn: Q = (R * S) * (T * U)
16. Biến đổi dựa trên t/chất của ĐSQH
17. Tính chất của phép toán ĐSQH A ~ tập các thuộc tính, F ~ biểu thức điều kiện 1. Phép chiếu và phép chọn  A (R)  A ( A1(R)) if A  A1  F (R)  F1( F 2 (R)) if F F1^ F2
18. Tính chất của phép toán ĐSQH (2) A ~ tập các thuộc tính, F ~ biểu thức điều kiện 2. Tính giao hoán đối với phép chọn và chiếu  F1( F 2 (R))  F 2 ( F1(R))  F1( A2 (R))  A2 ( F1(R)) Nếu các thuộc tính của F2 thuộc A1 :  A1( F 2 (R))  F 2 ( A1(R)) Nếu A1  A2 :  A1( A2 (R))  A1(R)
19. Tính chất của phép toán ĐSQH (3) 3. Tính giao hoán và kết hợp của các phép toán R S S R R*S S * R R  S S  R R  S S  R (R S) T R (S T ) (R  S) T R  (S T ) (R  S) T R  (S T ) chỉ nếu (R S) T R (S T) Attr(F2)  Attr(S) U Attr(T) F1 F 2 F1 F 2
20. Tính chất của phép toán ĐSQH (4) 4. Tính phân phối  và  trên các phép toán *, , , -, X Nếu F = (FR ^ FS) và nếu Attr(FR)  R và Attr(FS)  S thì :  F (R S)  FR (R)  FS (S) JC JC  F (R S)  FR (R)  FS (S)  F (R  S)  F (R)   F (S) ___  F (R - S)  F (R) –  F (S) ___ ΠZ ( R(X) x S(Y) ) Π X  Z (R) x Π Y  Z(S) ___ ΠZ (R  S) ΠZ (R)  ΠZ (S) ___
21. Biến đổi biểu thức ĐSQH T1  F1  F2  Fn (R)  F1( F2 ( Fn (R) ) ) ___ T2 ΠZ (ΠY (R)) ΠZ (R) nếu Z  Y ___ T3  F(X) (ΠY (R)) ΠY ( F(X) (R)) nếu X  Y T3’ ΠY ( F(X) (R)) ΠY ( F(X) (ΠX  Y (R))) nếu X  Y ___ T4  F(Z) (R(X) x S(Y))  F(Z) (R(X)) x S(Y) nếu Z  X  F(Z1) F(Z2) (R(X) x S(Y))  F(Z1) (R(X)) x  F(Z2) (S(Y)) nếu Z1  X và Z2  Y ___ T5  F (R  S)  F (R)   F (S) ___ T6  F (R - S)  F (R) –  F (S) ___ T7 ΠZ ( R(X) x S(Y) ) Π X  Z (R) x Π Y  Z(S) ___ T8 ΠZ (R  S) ΠZ (R)  ΠZ (S) ___
22. Trình tự áp dụng Khai triển phép lựa chọn dựa trên nhiều điều kiện: T1 Hoán vị phép chọn với tích đề-các, hợp, trừ: T3, T4, T5, T6 : đẩy phép chọn để có thể thực hiện sớm nhất có thể Hoán vị phép chiếu với tích đề-các, hợp : T2, T3’,T7, T8 Nhóm các điều kiện chọn bởi T1 và áp dụng T2 để loại các phép chiếu dư thừa
23. Biểu diễn dạng cây của ĐSQH A1  A1( F 2 (R*S)) F2  A1( F 2 R.B S.B (R S)) R.B=S.B x S R
24. Bài tập EMPLOYEE (FirstName, LastName, SSN, Birthday, Adrresse, NoDept) DEPARTEMENT (DNO, DName, SSNManager) PROJECT (PNO, PName, PLocation, DNo) WORK (ESSN, PNO, Heures) Tên của các nhân viên sinh sau ngày 30/01/70 và làm việc cho dự án "Esprit"  Birthday '30/ 01/70'PName 'Esprit'   (EMPLOYEE WORK ) FirstName,LastName Employee.SSN Work.ESSN * PROJECT  ( (EMPLOYEE) WORK )  Employee.SSN Work.ESSN Birthday '30/01/70' FirstName,LastName * PName 'Esprit' (PROJECT)
25. Kết luận Tối ưu hoá nhằm tìm phương án tốt nhất để thực hiện một câu hỏi  Cần lưu ý: chí phí thực hiện tối ưu hoá và chi phí thực hiện câu hỏi Các kỹ thuật tối ưu  Logic : kiểm tra điều kiện ràng buộc của các thuộc tính/quan hệ và điều kiện lựa chọn trong câu hỏi, biến đổi tương đương các biểu thức ĐSQH  Vật lý : tổ chức vật lý của dữ liệu trên đĩa, mô hình giá  Không nhất thiết phải áp dụng tất cả các kỹ thuật trên khi thực hiện tối ưu hoá 1 câu hỏi