Bài giảng Các hệ cơ sở dữ liệu: Tối ưu hóa truy vấn - Lương Trần Hy Hiến

Chia sẻ: Gió Biển | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

172
lượt xem 27
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Các hệ cơ sở dữ liệu: Tối ưu hóa truy vấn" cung cấp cho người đọc các kiến thức: Giới thiệu, bộ biên dịch câu truy vấn, phân tích cú pháp, chuyển cây phân tích sang ĐSQH, qui tắc tối ưu cây truy vấn, ước lượng chi phí. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Các hệ cơ sở dữ liệu: Tối ưu hóa truy vấn - Lương Trần Hy Hiến

5.1 Xử lý câu truy vấn Nội dung chi tiết Giới thiệu Giới thiệu R(A, B, C) Bộ biên dịch câu truy vấn (query compiler) S(C, D, E) Phân tích cú pháp Cây phân tích (parse tree) Chuyển cây phân tích sang ðSQH SELECT B, D Câu truy vấn ñơn giản FROM R, S Câu truy vấn lồng - lồng tương quan Qui tắc tối ưu cây truy vấn WHERE R.A=‘c’ AND S.E=2 AND R.C=S.C Ước lượng chi phí DBMS05 – Slides 3 DBMS05 – Slides 4
Giới thiệu (tt) Giới thiệu (tt) Câu truy vấn ñược thực hiện như thế nào? R A B C S C D E a 1 10 10 x 2 Cách 1 b 1 10 20 y 2 Tích cartesian c 2 10 30 z 2 Phép chọn (selection) Phép chiếu (projection) d 2 10 40 x 1 e 3 10 Kết quả 50 y 3 ΠB,D [ σR.A=‘c’ ∧ S.E=2 ∧ R.C = S.C (RxS)] B D 2 x DBMS05 – Slides 5 DBMS05 – Slides 6 Giới thiệu (tt) Giới thiệu (tt) Cách 2 RxS A B C C D E Phép chọn (selection) a 1 10 10 x 2 a 1 10 20 y 2 Phép kết (natural join) .. Phép chiếu (projection) . c 2 10 10 x 2 c 2 10 20 y 2 ΠB,D [ σR.A=‘c’ (R) σS.E=2 (S)] c 2 10 30 z 2 .. . DBMS05 – Slides 7 DBMS05 – Slides 8
Giới thiệu (tt) Giới thiệu (tt) R A B C S C D E a 1 10 10 x 2 Cách 3 - sử dụng chỉ mục trên R.A và S.C b 1 10 20 y 2 Tìm các bộ trong R thỏa R.A=‘c’ c 2 10 30 z 2 d 2 10 40 x 1 Với mỗi bộ tìm thấy, tìm tiếp các bộ trong S e 3 10 50 y 3 thỏa R.C=S.C Bỏ ñi những bộ S.E ≠ 2 σR A B C σS C D E Kết các bộ phù hợp của R và S c 2 10 10 x 2 Chiếu trên thuộc tính B và D 20 y 2 30 z 2 DBMS05 – Slides 9 DBMS05 – Slides 10 Giới thiệu (tt) Câu hỏi R S A =‘c’ C A B C I1 I2 C D E a 1 10 10 x 2 b 1 10 20 y 2 c 2 10 30 z 2 d 2 10 Kiểm tra 40 x 1 e 3 10 Kết quả E=2? 50 y 3 Bộ có A=‘c’ kế tiếp DBMS05 – Slides 11 DBMS05 – Slides 12
Bộ biên dịch Giới thiệu (tt) SQL Query Tập trung vào RDBMS Parse query Query expression tree DBMS thực hiện cách nào Select logical query plan Query optimization Logical query plan tree Select physical plan Physical query plan tree Execute plan DBMS05 – Slides 13 DBMS05 – Slides 14 Quá trình biên dịch Cây phân tích Query Parse Parse tree Answer Convert Logical query plan Execute statistics SELECT FROM WHERE Apply laws Pi Improve logical query plan Pick the best = Estimate IN {(P1,C1), (P2,C2) … } result sizes LIKE Logical query plan + sizes Estimate costs AND … Consider physical plans {P1, P2, … } DBMS05 – Slides 15 DBMS05 – Slides 16
Ví dụ 1 Ví dụ 1 (tt) Customer(cusID, cusNm, cusStreet, cusCity) Account(accID, cusID, balance) SELECT FROM WHERE SELECT cusNm IN FROM Customer cusNm Customer WHERE cusID IN ( cusID SELECT cusID FROM Account SELECT FROM WHERE WHERE balance > 100) = cusID Account balance 100 DBMS05 – Slides 17 DBMS05 – Slides 18 Ví dụ 2 Ví dụ 2 (tt) Customer(cusID, cusNm, cusStreet, cusCity) Account(accID, cusID, balance) SELECT FROM WHERE SELECT cusNm FROM Customer, Account , WHERE Customer.cusID = Account.cusID cusNm Customer Account AND balance = 100 AND = = Customer.cusID Account.cusID balance 100 DBMS05 – Slides 19 DBMS05 – Slides 20
Nhận xét Câu hỏi Giới hạn Vẽ cấu trúc cây của câu truy GROUP BY vấn sau: HAVING SELECT * FROM Customers ORDER BY DISTINCT SELECT CustomerID, CustomerName FROM Customers WHERE CustomerID Aggregation function (Max, Min, Count, Sum, in (SELECT CustomersID FROM Invoices Avg) WHERE TotalCost > 1000) Alias name DBMS05 – Slides 21 DBMS05 – Slides 22 Tiền xử lý (preprocessing) Quá trình biên dịch Query Kiểm tra ngữ nghĩa Parse Quan hệ Parse tree Answer Thuộc tính Convert Select Logical query plan Execute From statistics Apply laws Pi Kiểu dữ liệu Improve logical query plan Pick the best Where Estimate {(P1, C1), (P2,C2) … } result sizes Logical query plan + sizes Estimate costs Consider physical plans {P1, P2, … } DBMS05 – Slides 23 DBMS05 – Slides 24
Biến ñổi sang ðSQH Truy vấn ñơn Xét ví dụ 2 Xét câu trúc Thay thế thành các biến quan hệ πcusNm Sử dụng phép tích cartesian cho các biến quan hệ Thay thế thành phép chọn σC σCustomer.cusID=Account.cusID ∧ balance=100 Thay thế thành phép chiếu πL π L x σ C Cây truy vấn Customer Account x R S T … DBMS05 – Slides 25 DBMS05 – Slides 26 Biến ñổi sang ðSQH (tt) Xét ví dụ 1 Truy vấn lồng Tồn tại câu truy vấn con S trong πcusNm Áp dụng qui tắc cho truy vấn con Phép chọn 2 biến (two-argument selection) σ Nút là phép chọn không có tham số Customer Nhánh con trái là biến quan hệ R Nhánh con phải là áp dụng cho mỗi bộ trong R σ IN ΠcusID R σbalance=100 Tuple Operator S cusID Account DBMS05 – Slides 27 DBMS05 – Slides 28
Biến ñổi sang ðSQH (tt) Xét ví dụ 1 (tt) Truy vấn lồng πcusNm Biến ñổi phép chọn 2 biến σCustomer.cusID=Account.cusID Thay thế bằng 1 cây có gốc là S Nếu S có các bộ trùng nhau thì phải lược bỏ bớt bộ trùng nhau ñi Sử dụng phép δ X Thay thế phép chọn 2 biến thành σC σC là kết quả của phép cartesian của R và S σ C Customer δ σ x πcusID R R δ σbalance=10 Tuple Operator S Account S DBMS05 – Slides 29 DBMS05 – Slides 30 Xét ví dụ 1 (tt) Ví dụ 3 πcusNm Customer(cusID, cusNm, cusStreet, cusCity) Account(accID, cusID, balance) Customer.cusID=Account.cusID SELECT c.cusNm Truy vấn lồng tương quan Customer δ FROM Customer c WHERE 10000 >= ( πcusID SELECT SUM(a.balance) σbalance=10 FROM Account a WHERE a.cusID=c.cusID) Account DBMS05 – Slides 31 DBMS05 – Slides 32
Ví dụ 3 (tt) Ví dụ 3 (tt) πcusNm πc.cusNm σ σ10000 ≥ SoB X Customer c c.cusID = a.cusID ≥ γSUM(a.balance) γa.custID, SUM(a.balance) Customer c SoB 10000 σc.custID=a.cusID Account a Account a DBMS05 – Slides 33 DBMS05 – Slides 34 Câu hỏi Quá trình biên dịch Query Biến ñổi câu truy vấn sau sang ñại số Parse quan hệ: Parse tree Answer Select custID, CustomerName, InvoieID Convert From Customers, Invoices Logical query plan Execute statistics Apply laws Where Customers.custID = Pi Improve logical query plan Invoices.custID Estimate Pick the best {(P1, C1), (P2,C2) … } result sizes Logical query plan + sizes Estimate costs Consider physical plans {P1, P2, … } DBMS05 – Slides 35 DBMS05 – Slides 36
Qui tắc: Kết tự nhiên, tích cartesian, hội Qui tắc: Phép chọn σ R S = S R Cho p là vị từ chỉ có các thuộc tính của R (R S) T = R (S T) q là vị từ chỉ có các thuộc tính của S RxS=SxR m là vị từ có các thuộc tính của R và S Pushing selections (R x S) x T = R x (S x T) σp1∧∧p2(R) = σp1 [ σp2 (R)] R∪S=S∪R σp1vp2(R) = [ σp1 (R)] ∪ [ σp2 (R)] R ∪ (S ∪ T) = (R ∪ S) ∪ T Quan hệ R là tập hợp DBMS05 – Slides 37 ∪S là phép hội trên tập hợp DBMS05 – Slides 38 Qui tắc: σ, Qui tắc: σ, (tt) σp∧q (R S) = [ σp (R)] [ σq (S)] σp (R S) = [ σp (R)] S σq (R S) = R [σq (S)] σp∧q∧m (R S) = σm [σp(R) σq (S)] σp∨q (R S) = [ σp (R) S] ∪ [R σq (S)] DBMS05 – Slides 39 DBMS05 – Slides 40
Qui tắc: σ, ∪ và σ, – Qui tắc: Phép chiếu π Cho X = tập thuộc tính con của R σc (R ∪ S) = σc (R) ∪ σc (S) Y = tập thuộc tính con của R Ta có σc (R – S) = σc (R) – S = σc (R) – σc (S)] XY = X ∪ Y πXY (R) = πX [πY (R)] DBMS05 – Slides 41 DBMS05 – Slides 42 Qui tắc: π, Qui tắc: σ, π Cho Cho X = tập thuộc tính con của R X = tập thuộc tính con của R Y = tập thuộc tính con của S Z = tập thuộc tính con của R xuất hiện trong vị Z = tập giao thuộc tính của R và S từ p Pushing projections πXZ πX [σp (R)] = πX {σp [πX (R)]} πXY (R S) = πXY [ πXZ(R) πYZ(S)] Except intersection and difference DBMS05 – Slides 43 DBMS05 – Slides 44
Qui tắc: σ, π, Nhận xét: σ, π Cho Ví dụ X = tập thuộc tính con của R R(A, B, C, D, E) Y = tập thuộc tính con của S X={E} Z = tập giao thuộc tính của R và S p: A=3 ∧ B=‘a’ Z’ = Z ∪ {các thuộc tính xuất hiện trong vị từ p} πXY [σp (R S)] = πx [σp (R)] πE {σp [πABE(R)]} πXY {σp [πXZ’ (R) πYZ’ (S)]} Chọn trước Chiếu trước tốt hơn??? tốt hơn??? DBMS05 – Slides 45 DBMS05 – Slides 46 Nhận xét: σ, π (tt) Qui tắc: ×, Bình thường Chiếu trước Nhưng σC (R S) = R C S Giả sử A và B ñược cài ñặt chỉ mục (index) Physical query plan dùng chỉ mục ñể chọn ra những bộ có A=3 và B=‘a’ trước R×S = π [σC (R × S)] L Nếu thực hiện chiếu trước πAB(R) thì chỉ mục trên A và B là vô ích Chọn trước →Thông thường chọn trước tốt hơn DBMS05 – Slides 47 DBMS05 – Slides 48
Qui tắc: δ Qui tắc: γ δ(R S) = δ(R) δ(S) Cho X = tập thuộc tính trong R ñược gom nhóm δ(R × S) = δ(R) × δ(S) Y = X ∪ {một số thuộc tính khác của R} σC (R)] δ[ = σC [δ(R)] δ[γX(R)] = γX(R) δ(R ∩B S) = δ(R) ∩B S = R ∩B δ(S) γX(R) = γX [πY (R)] = δ(R) ∩B δ(S) Except: ∪B , −B , π DBMS05 – Slides 49 DBMS05 – Slides 50 Xét ví dụ 2 Xét ví dụ 2 πcusNm πcusNm Qui tắc σ σCustomer.cusID=Account.cusID ∧ balance=100 σbalance=100 x σCustomer.cusID=Account.cusID Customer Account x Customer Account DBMS05 – Slides 51 DBMS05 – Slides 52
Xét ví dụ 2 (tt) Xét ví dụ 2 (tt) Qui tắc σ, πcusNm Pushing σ πcusNm σbalance=100 Customer.cusID=Account.cusID Customer.cusID=Account.cusID Customer σbalance=100 Customer Account Account DBMS05 – Slides 53 DBMS05 – Slides 54 Xét ví dụ 2 (tt) Quá trình biên dịch Query πcusNm Parse Pushing π Parse tree Answer Convert Customer.cusID=Account.cusID Logical query plan Execute statistics Apply laws πcusNm, cusID πcusID Improve logical query plan Pi Pick the best Estimate {(P1, C1), (P2,C2) … } Customer σbalance=100 result sizes Logical query plan + sizes Estimate costs Account Consider physical plans {P1, P2, … } DBMS05 – Slides 55 DBMS05 – Slides 56
Ước lượng chi phí Ước lượng kích thước Ước lượng kích thước cây truy vấn Thống kê quan hệ R Quan hệ T(R): số bộ trong R Các phép toán S(R): tổng số byte của 1 bộ trong R B(R): tổng số block chứa tất cả các bộ của R Ước lượng số lần truy xuất IOs V(R, A): số giá trị khác nhau mà thuộc tính A Số blocks ñược ñọc hoặc ghi ñể thực hiện cây trong R có thể có truy vấn DBMS05 – Slides 57 DBMS05 – Slides 58 Ví dụ Ước lượng: W = R1 × R2 R A B C D A: chuỗi 20 bytes x 1 10 a B: số nguyên 4 bytes x 1 20 b C: ngày 8 bytes S(W) = S(T1) + S(T2) y 1 30 a D: chuỗi 68 bytes y 1 40 c 1 block = 1024 bytes z 1 50 d T(W) = T(R1) x T(T2) (block header: 24 bytes) T(R) = 5 V(R, A) = 3 V(R, B) = 1 S(R) = 100 V(R, C) = 5 V(R, D) = 4 B(R) = 1 DBMS05 – Slides 59 DBMS05 – Slides 60
Ước lượng: W = σZ = val (R) Ước lượng: W = σZ ≥ val (R) T(W) = ??? S(W) = S(R) T(R) Cách 1 T(W) = T(R) 2 T(W) = V(R, Z) Số bộ trung bình thỏa ñiều kiện Z=val T(R) Cách 2 T(W) = 3 DBMS05 – Slides 61 DBMS05 – Slides 62 Ví dụ Ví dụ (tt) Cho Ước lượng kích thước biểu thức R(A, B, C) σ S = A=10 ∨ B
Ước lượng: W = R1 R2 Ước lượng: W = R1 R2 (tt) Cho Xét trường hợp X ∩ Y = A X = tập thuộc tính của R1 R1 A B C R2 A D Y = tập thuộc tính của R2 Giả sử Xét trường hợp X ∩ Y = ∅ V(R1, A) ≤ V(R2, A) T(W) = ? Mọi giá trị của A trong R1 thì có trong R2 V(R2, A) ≤ V(R1, A) Tương tự R1 × R2 Mọi giá trị của A có trong R2 thì có trong R1 DBMS05 – Slides 65 DBMS05 – Slides 66 Ước lượng: W = R1 R2 (tt) Ước lượng: W = R1 R2 (tt) R1 A B C R2 A D V(R1, A) ≤ V(R2, A) T(W) = T(R1) x T(R2) Chọn 1 bộ V(R2, A) Tìm V(R2, A) ≤ V(R1, A) T(W) = T(R2) x T(R1) 1 bộ trong R1 sẽ thỏa với T(R2) bộ trong R2 V(R1, A) V(R2, A) Tổng quát T(R2) T(T1) T(R2) T(W) = T(R1) x T(W) = V(R2, A) max{V(R1, A), V(R2, A)} DBMS05 – Slides 67 DBMS05 – Slides 68
Ước lượng: W = R1 R2 (tt) Ví dụ Xét trường hợp X ∩ Y = A R1 A B C R2 A D Z = R1(A, B) R2(B, C) R3(C, D) W(A, B, C, D) Các thuộc tính không tham gia vào phép kết thì R1 R2 R3 số lượng các giá trị vẫn giữ nguyên T(R1) = 1000 T(R2) = 2000 T(R3) = 3000 V(W, A) = min {V(R1, A), V(R2, A)} V(R1, A) = 50 V(R2, B) = 200 V(R3, C) = 90 V(W, B) = V(R1, B) V(R1, B) = 100 V(R3, C) = 300 V(R3, D) = 500 V(W, C) = V(R1, C) V(W, D) = V(R2, D) DBMS05 – Slides 69 DBMS05 – Slides 70 Ví dụ (tt) Ví dụ (tt) U = R1(A, B) R2(B, C) Z=U R3(C, D) V(Z, A) = 50 V(U, A) = 50 T(U) = 1000 x 2000 V(U, B) = 100 T(Z) = 1000 x 2000 x 3000 V(Z, B) = 100 200 200 x 300 V(Z, C) = 90 V(U, C) = 300 V(Z, D) = 500 DBMS05 – Slides 71 DBMS05 – Slides 72
Nhận xét Ước lượng: W = R1 ∪ R2 Phép chiếu R1 và R2 là bag Ước lượng chính xác Phép tích T(W) = T(R1) + T(R2) Phép chọn Ước lượng tương ñối hợp lý - số lượng bộ của các quan hệ tương ñối lớn R1 và R2 là set Phép kết - giá trị của các thuộc tính phân bố ñồng ñều T’(W) = T(R1) + T(R2) Phép toán khác T’’(W) ≤ T(R1) + T(R2) Hội Giao T’(W) + T’’(W) Trừ →T(W) = Lược bỏ trùng lắp 2 Gom nhóm DBMS05 – Slides 73 DBMS05 – Slides 74 Ước lượng: W = R1 ∩ R2 Ước lượng: W = R1 − R2 Cách 1 R1 R2 TH1: T(W) = T(R1) TH1: T’(W)=0 TH2: T(W) = T(R1) – T(R2) TH2: T’’(W)= T(R1) hoặc T’’(W)=T(R2) T’(W) + T’’(W) Cách 2 →T(W) = → T(W) = T(R1) − 1 T(R2) 2 2 Trường hợp ñặc biệt của phép kết tự nhiên Chỉ áp dụng cho ∩S T(R1) T(R2) T(W) = max{V(R1, Z), V(R2, Z)} DBMS05 – Slides 75 DBMS05 – Slides 76
Ước lượng: W = δ(R) Ước lượng: W = γ (R) TH1: T(W) = 1 γL(R) Nếu trong R không có bộ nào thì T(W)=0 Số lượng bộ trong W và cũng là số lượng nhóm TH2: T(W) = T(R) TH1: T(W) = 1 R(a1, a2, …, an) Số bộ phân biệt tối ña của R là tích các V(R, ai), TH2: T(W) = T(R) i=1..n R(a1, a2, …, an) → T(W) = min{ 1 T(R1), tích các V(R, ai)} 1 ña 2 T(W) Số → lượng=nhóm min{ tối T(Rlà1), tíchtích cáccác V(R,V(R, ai)} ai), i=1..n 2 DBMS05 – Slides 77 DBMS05 – Slides 78 Ví dụ Ví dụ (tt) R(a, b) 250 500 δ T(R)=5000 δ V(R, a)=50 σa =10 V(R, b)=100 50 δ δ 1000 1000 100 σa =10 S 100 σa =10 S S(b, c) 2000 2000 R S R T(S)=2000 R 5000 5000 V(S, b)=200 V(S, c)=100 (1) (2) DBMS05 – Slides 79 DBMS05 – Slides 80