Bài giảng Các hệ cơ sở dữ liệu - 5. Tối ưu hóa truy vấn

Các quy tắc tối ưu hóa • Bảng (table): – có khóa chính (Primary Key) – có ít nhất 01 clustered indextable – có số lượng non-clustered index phù hợp. – Non-clustered index phải ñược tạo trên các cột (column) của bảng (table) dựa vào nhu cầu truy vấn. • Dựa theo sự sắp xếp thứ tự như sau khi có bất kỳ index ñược tạo: a) WHERE clause, b) JOIN clause, c) ORDER BY clause, d) SELECT clause • Không nên dùng Views thay cho bảng (table) gốc. • Triggers không nên sử dụng nếu không cần thiết, nên nhập những xử lý từ trigger vào trong thủ tục (stored procedure). • Gỡ bỏ những câu lệnh query trực tiếp và thay bằng thủ tục (stored procedure). • Phải có ít nhất 30% không gian ñĩa cứng trên phân vùng chứa database. • Nếu có thể hãy chuyển UDF (user defined function) sang SP (stored procedure) • Chỉ SELECT những cột cần thiết, không nên SELECT * • Gỡ bỏ các joins từ các bảng (table) không cần thiết • Hạn chế sử dụng con trỏ (cursor) • ðảm bảo phần cứng ñáp ứng nhu cầu của hệ thống.

pdf32 trang | Chia sẻ: vutrong32 | Ngày: 19/10/2018 | Lượt xem: 11 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Bài giảng Các hệ cơ sở dữ liệu - 5. Tối ưu hóa truy vấn, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
5.1 Xử lý câu truy vấn  Giới thiệu  Bộ biên dịch câu truy vấn (query compiler)  Phân tích cú pháp Nội dung chi tiết DBMS05 – Slides 3  Cây phân tích (parse tree)  Chuyển cây phân tích sang ðSQH  Câu truy vấn ñơn giản  Câu truy vấn lồng - lồng tương quan  Qui tắc tối ưu cây truy vấn  Ước lượng chi phí Giới thiệu  R(A, B, C)  S(C, D, E) DBMS05 – Slides 4 SELECT B, D FROM R, S WHERE R.A=‘c’ AND S.E=2 AND R.C=S.C Giới thiệu (tt) 10 x 2 C D ES 20 y 2 A B CR a 1 10 b 1 10  Câu truy vấn ñược thực hiện như thế nào? DBMS05 – Slides 5 30 z 2 40 x 1 50 y 3 c 2 10 d 2 10 e 3 10 Kết quả B D 2 x Giới thiệu (tt)  Cách 1  Tích cartesian DBMS05 – Slides 6  Phép chọn (selection)  Phép chiếu (projection) ΠB,D [ σR.A=‘c’ ∧ S.E=2 ∧ R.C = S.C (RxS)] Giới thiệu (tt) A B CRxS a 1 10 C D E 10 x 2 a 1 10 20 y 2 DBMS05 – Slides 7 c 2 10 x 210 c 2 10 y 220 ... c 2 10 z 230 ... Giới thiệu (tt)  Cách 2  Phép chọn (selection)  Phép kết (natural join) DBMS05 – Slides 8  Phép chiếu (projection) ΠB,D [ σR.A=‘c’ (R) σS.E=2 (S)] Giới thiệu (tt) C D E 10 x 2 20 y 2 30 z 2 40 x 1 SA B C a 1 10 b 1 10 c 2 10 d 2 10 R DBMS05 – Slides 9 50 y 3e 3 10 A B C c 2 10 σR C D E 10 x 2 σS 20 y 2 30 z 2 Giới thiệu (tt)  Cách 3 - sử dụng chỉ mục trên R.A và S.C  Tìm các bộ trong R thỏa R.A=‘c’  Với mỗi bộ tìm thấy, tìm tiếp các bộ trong S DBMS05 – Slides 10 thỏa R.C=S.C  Bỏ ñi những bộ S.E ≠ 2  Kết các bộ phù hợp của R và S  Chiếu trên thuộc tính B và D Giới thiệu (tt) C D E 10 x 2 S A B C a 1 10 R I2I1 =‘c’A C DBMS05 – Slides 11 20 y 2 30 z 2 40 x 1 50 y 3 b 1 10 c 2 10 d 2 10 e 3 10 Kiểm tra E=2?Kết quả Bộ có A=‘c’ kế tiếp Câu hỏi DBMS05 – Slides 12 Giới thiệu (tt) DBMS thực hiện cách nào DBMS05 – Slides 13 Bộ biên dịch SQL Query Parse query Select logical Query expression tree Tập trung vào RDBMS DBMS05 – Slides 14 query plan Select physical plan Execute plan Logical query plan tree Physical query plan tree Query optimization Quá trình biên dịch Parse Query Convert Execute AnswerParse tree Logical query plan DBMS05 – Slides 15 Apply laws Estimate result sizes Consider physical plans Estimate costs Pick the bestImprove logical query plan Logical query plan + sizes {P1, P2, } {(P1,C1), (P2,C2) } Pi statistics Cây phân tích DBMS05 – Slides 16 SELECT FROM WHERE = IN LIKE AND  Customer(cusID, cusNm, cusStreet, cusCity)  Account(accID, cusID, balance) Ví dụ 1 SELECT cusNm FROM Customer DBMS05 – Slides 17 WHERE cusID IN ( SELECT cusID FROM Account WHERE balance > 100) Ví dụ 1 (tt) SELECT FROM WHERE IN DBMS05 – Slides 18 cusNm Customer cusID SELECT FROM WHERE cusID Account balance = 100  Customer(cusID, cusNm, cusStreet, cusCity)  Account(accID, cusID, balance) Ví dụ 2 SELECT cusNm FROM Customer, Account DBMS05 – Slides 19 WHERE Customer.cusID = Account.cusID AND balance = 100 Ví dụ 2 (tt) SELECT FROM WHERE DBMS05 – Slides 20 cusNm Customer Account , AND = = Customer.cusID Account.cusID balance 100  Giới hạn  GROUP BY  HAVING  ORDER BY Nhận xét DBMS05 – Slides 21  DISTINCT  Aggregation function (Max, Min, Count, Sum, Avg)  Alias name Câu hỏi  Vẽ cấu trúc cây của câu truy vấn sau: SELECT * FROM Customers DBMS05 – Slides 22 SELECT CustomerID, CustomerName FROM Customers WHERE CustomerID in (SELECT CustomersID FROM Invoices WHERE TotalCost > 1000) Tiền xử lý (preprocessing)  Kiểm tra ngữ nghĩa  Quan hệ  Thuộc tính  Select DBMS05 – Slides 23  From  Kiểu dữ liệu  Where Quá trình biên dịch Convert Query Parse Execute AnswerParse tree Logical query plan DBMS05 – Slides 24 Apply laws Estimate result sizes Consider physical plans Estimate costs Pick the bestImprove logical query plan Logical query plan + sizes {P1, P2, } {(P1, C1), (P2,C2) } Pi statistics Biến ñổi sang ðSQH  Truy vấn ñơn  Xét câu trúc  Thay thế thành các biến quan hệ  Sử dụng phép tích cartesian cho các biến quan hệ  Thay thế thành phép chọn σC DBMS05 – Slides 25  Thay thế thành phép chiếu πL R S T x σC πL Cây truy vấn Xét ví dụ 2 πcusNm σCustomer.cusID=Account.cusID ∧ balance=100 DBMS05 – Slides 26 Customer Account x Biến ñổi sang ðSQH (tt)  Truy vấn lồng  Tồn tại câu truy vấn con S trong  Á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ố Nhánh con trái là biến quan hệ R DBMS05 – Slides 27   Nhánh con phải là áp dụng cho mỗi bộ trong R σ R STuple Operator Xét ví dụ 1 πcusNm σ Customer DBMS05 – Slides 28 IN ΠcusID cusID σbalance=100 Account Biến ñổi sang ðSQH (tt)  Truy vấn lồng  Biến ñổi phép chọn 2 biến  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 δ Thay thế phép chọn 2 biến thành σ DBMS05 – Slides 29  C  σC là kết quả của phép cartesian của R và S σ R STuple Operator σC R S x δ Xét ví dụ 1 (tt) πcusNm σCustomer.cusID=Account.cusID X DBMS05 – Slides 30 Customer πcusID σbalance=10 Account δ Xét ví dụ 1 (tt) πcusNm Customer.cusID=Account.cusID DBMS05 – Slides 31 Customer πcusID σbalance=10 Account δ  Customer(cusID, cusNm, cusStreet, cusCity)  Account(accID, cusID, balance) Ví dụ 3 SELECT c.cusNm FROM Customer c Truy vấn lồng tương quan DBMS05 – Slides 32 WHERE 10000 >= ( SELECT SUM(a.balance) FROM Account a WHERE a.cusID=c.cusID) Ví dụ 3 (tt) πcusNm σ X DBMS05 – Slides 33 Customer c ≥ 10000 γSUM(a.balance) σc.custID=a.cusID Account a Ví dụ 3 (tt) πc.cusNm σ10000 ≥ SoB DBMS05 – Slides 34 Customer c γa.custID, SUM(a.balance) Account a SoB c.cusID = a.cusID Câu hỏi  Biến ñổi câu truy vấn sau sang ñại số quan hệ: Select custID, CustomerName, InvoieID From Customers, Invoices DBMS05 – Slides 35 Where Customers.custID = Invoices.custID Quá trình biên dịch Convert Query Parse Execute AnswerParse tree Logical query plan DBMS05 – Slides 36 Apply laws Estimate result sizes Consider physical plans Estimate costs Pick the bestImprove logical query plan Logical query plan + sizes {P1, P2, } {(P1, C1), (P2,C2) } Pi statistics Qui tắc: Kết tự nhiên, tích cartesian, hội R S = S R (R S) T = R (S T) R x S = S x R DBMS05 – Slides 37 (R x S) x T = R x (S x T) R ∪ S = S ∪ R R ∪ (S ∪ T) = (R ∪ S) ∪ T Qui tắc: Phép chọn σ  Cho  p là vị từ chỉ có các thuộc tính của R  q là vị từ chỉ có các thuộc tính của S  m là vị từ có các thuộc tính của R và S DBMS05 – Slides 38 σp1∧p2(R) = σp1vp2(R) = σp1 [σp2 (R)] [σp1 (R)] ∪ [σp2 (R)] Quan hệ R là tập hợp ∪S là phép hội trên tập hợp Pushing selections Qui tắc: σ, σp (R S) = [σp (R)] S σσ DBMS05 – Slides 39 R [ q (S)]q (R S) = Qui tắc: σ, (tt) σp∧q (R S) = σ (R S) = [σp (R)] [σq (S)] σ [σ (R) σ (S)] DBMS05 – Slides 40 p∧q∧m σp∨q (R S) = m p q [σp (R) S] ∪ [R σq (S)] Qui tắc: σ, ∪ và σ, – σc (R ∪ S) = σ σσ σc (R) ∪ σc (S) σ DBMS05 – Slides 41 = c (R) – c (S)]c (R – S) = c (R) – S Qui tắc: Phép chiếu π  Cho  X = tập thuộc tính con của R  Y = tập thuộc tính con của R  Ta có DBMS05 – Slides 42  XY = X ∪ Y πXY (R) = πX [πY (R)] Qui tắc: π,  Cho  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 giao thuộc tính của R và S DBMS05 – Slides 43 Pushing projections πXY (R S) = πXY [ πXZ(R) πYZ(S)] Except intersection and difference Qui tắc: σ, π  Cho  X = tập thuộc tính con của R  Z = tập thuộc tính con của R xuất hiện trong vị từ p π DBMS05 – Slides 44 πX [σp (R)] = {σp [πX (R)]} πX XZ Qui tắc: σ, π,  Cho  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 giao thuộc tính của R và S DBMS05 – Slides 45  Z’ = Z ∪ {các thuộc tính xuất hiện trong vị từ p}πXY [σp (R S)] = πXY {σp [πXZ’ (R) πYZ’ (S)]} Nhận xét: σ, π  Ví dụ  R(A, B, C, D, E)  X={E}  p: A=3 ∧ B=‘a’ DBMS05 – Slides 46 πx [σp (R)] πE {σp [πABE(R)]} Chọn trước tốt hơn??? Chiếu trước tốt hơn??? Nhận xét: σ, π (tt)  Bình thường  Chiếu trước  Nhưng  Giả sử A và B ñược cài ñặt chỉ mục (index) DBMS05 – Slides 47  Physical query plan dùng chỉ mục ñể chọn ra những bộ có A=3 và B=‘a’ trước  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 Qui tắc: ×, σC (R S) = R C S π σ DBMS05 – Slides 48 R × S = L [ C (R × S)] Qui tắc: δ δ(R S) = δ(R) δ(S) δ(R × S) = δ(R) × δ(S) δ[σ (R)] = σ [δ(R)] DBMS05 – Slides 49 C C δ(R ∩B S) = δ(R) ∩B S = R ∩B δ(S) = δ(R) ∩B δ(S) Except: ∪B , −B , π Qui tắc: δ[γ (R)] = γ (R) γ  Cho  X = tập thuộc tính trong R ñược gom nhóm  Y = X ∪ {một số thuộc tính khác của R} DBMS05 – Slides 50 X X γX(R) = γX [πY (R)] Xét ví dụ 2 πcusNm σCustomer.cusID=Account.cusID ∧ balance=100 DBMS05 – Slides 51 Customer Account x Xét ví dụ 2 πcusNm σbalance=100 Qui tắc σ DBMS05 – Slides 52 Customer Account x σCustomer.cusID=Account.cusID Xét ví dụ 2 (tt) πcusNm σbalance=100 Qui tắc σ, DBMS05 – Slides 53 Customer Account Customer.cusID=Account.cusID Xét ví dụ 2 (tt) πcusNmPushing σ DBMS05 – Slides 54 σbalance=100Customer Account Customer.cusID=Account.cusID Xét ví dụ 2 (tt) πcusNm Customer.cusID=Account.cusID Pushing π DBMS05 – Slides 55 σbalance=100Customer Account πcusNm, cusID πcusID Quá trình biên dịch Convert Query Parse Execute AnswerParse tree Logical query plan DBMS05 – Slides 56 Apply laws Estimate result sizes Consider physical plans Estimate costs Pick the bestImprove logical query plan Logical query plan + sizes {P1, P2, } {(P1, C1), (P2,C2) } Pi statistics Ước lượng chi phí  Ước lượng kích thước cây truy vấn  Quan hệ  Các phép toán DBMS05 – Slides 57  Ước lượng số lần truy xuất IOs  Số blocks ñược ñọc hoặc ghi ñể thực hiện cây truy vấn Ước lượng kích thước  Thống kê quan hệ R  T(R): số bộ trong R  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 DBMS05 – Slides 58  V(R, A): số giá trị khác nhau mà thuộc tính A trong R có thể có Ví dụ A B CR x 1 10 D a x 1 20 b 1 1 30 40 a c y y A: chuỗi 20 bytes B: số nguyên 4 bytes C: ngày 8 bytes D: chuỗi 68 bytes 1 block = 1024 bytes DBMS05 – Slides 59 1 50 dz T(R) = 5 S(R) = 100 B(R) = 1 V(R, A) = 3 V(R, B) = 1 V(R, C) = 5 V(R, D) = 4 (block header: 24 bytes) Ước lượng: W = R1 × R2 S(W) = S(T1) + S(T2) DBMS05 – Slides 60 T(W) = T(R1) x T(T2) Ước lượng: W = S(W) = S(R) σZ = val (R) T(R) DBMS05 – Slides 61 T(W) = V(R, Z) Số bộ trung bình thỏa ñiều kiện Z=val Ước lượng: W = T(W) = ??? σZ ≥ val (R)  Cách 1 T(W) = T(R) 2 DBMS05 – Slides 62  Cách 2 T(W) = T(R) 3 Ví dụ S = σ (R)  Cho  R(A, B, C)  T(R) = 10000  V(R, A) = 50 DBMS05 – Slides 63 A=10 ∧ B<20  Ước lượng kích thước biểu thức T(S) = T(R) V(R, A) x 3 = 10000 50 x 3 = 67 Ví dụ (tt) S = σA=10 ∨ B<20 (R)  Ước lượng kích thước biểu thức  Giả sử  n là T(R) DBMS05 – Slides 64  m1 là số bộ thỏa A=10 trong R  m2 là số bộ thỏa B<20 trong R T(S) = n(1 – (1 – m1 n m2 n )(1 – )) Ước lượng: W = R1 R2  Cho  X = tập thuộc tính của R1  Y = tập thuộc tính của R2 DBMS05 – Slides 65  Xét trường hợp X ∩ Y = ∅ T(W) = ? Tương tự R1 × R2 Ước lượng: W = R1 R2 (tt)  Xét trường hợp X ∩ Y = A  Giả sử A B CR1 A DR2 DBMS05 – Slides 66  V(R1, A) ≤ V(R2, A)  Mọi giá trị của A trong R1 thì có trong R2  V(R2, A) ≤ V(R1, A)  Mọi giá trị của A có trong R2 thì có trong R1 Ước lượng: W = R1 R2 (tt) A B CR1 A DR2 Chọn 1 bộ Tìm DBMS05 – Slides 67 1 bộ trong R1 sẽ thỏa với T(R2) V(R2, A) bộ trong R2 T(W) = T(R1) x T(R2) V(R2, A) Ước lượng: W = R1 R2 (tt)  V(R1, A) ≤ V(R2, A)  V(R2, A) ≤ V(R1, A) T(W) = T(R1) x T(R2) V(R2, A) DBMS05 – Slides 68 T(W) = T(T1) T(R2) max{V(R1, A), V(R2, A)}  Tổng quát T(W) = T(R2) x T(R1) V(R1, A) Ước lượng: W = R1 R2 (tt)  Xét trường hợp X ∩ Y = A  W(A, B, C, D)  Các thuộc tính không tham gia vào phép kết thì A B CR1 A DR2 DBMS05 – Slides 69 số lượng các giá trị vẫn giữ nguyên  V(W, A) = min {V(R1, A), V(R2, A)}  V(W, B) = V(R1, B)  V(W, C) = V(R1, C)  V(W, D) = V(R2, D) Ví dụ Z = R1(A, B) R2(B, C) R3(C, D) R R R DBMS05 – Slides 70 1 T(R1) = 1000 V(R1, A) = 50 V(R1, B) = 100 2 T(R2) = 2000 V(R2, B) = 200 V(R3, C) = 300 3 T(R3) = 3000 V(R3, C) = 90 V(R3, D) = 500 Ví dụ (tt) U = R1(A, B) R2(B, C) 1000 x 2000 V(U, A) = 50 DBMS05 – Slides 71 T(U) = 200 V(U, B) = 100 V(U, C) = 300 Ví dụ (tt) Z = U R3(C, D) 1000 x 2000 x 3000 V(Z, A) = 50 V(Z, B) = 100 DBMS05 – Slides 72 T(Z) = 200 x 300 V(Z, C) = 90 V(Z, D) = 500 Nhận xét  Phép chiếu  Phép tích  Phép chọn Ước lượng chính xác Ước lượng tương ñối hợp lý DBMS05 – Slides 73  Phép kết  Phép toán khác  Hội  Giao  Trừ  Lược bỏ trùng lắp  Gom nhóm - số lượng bộ của các quan hệ tương ñối lớn - giá trị của các thuộc tính phân bố ñồng ñều Ước lượng: W = R1 ∪ R2  R1 và R2 là bag R và R là set T(W) = T(R1) + T(R2) DBMS05 – Slides 74  1 2 T’(W) = T(R1) + T(R2) T’’(W) ≤ T(R1) + T(R2) →T(W) = T’(W) + T’’(W) 2 Ước lượng: W = R1 ∩ R2  Cách 1  TH1: T’(W)=0  TH2: T’’(W)= T(R1) hoặc T’’(W)=T(R2) R1 R2 DBMS05 – Slides 75  Cách 2  Trường hợp ñặc biệt của phép kết tự nhiên  Chỉ áp dụng cho ∩S →T(W) = T’(W) + T’’(W) 2 T(W) = T(R1) T(R2) max{V(R1, Z), V(R2, Z)} Ước lượng: W = R1 − R2  TH1: T(W) = T(R1)  TH2: T(W) = T(R1) – T(R2) DBMS05 – Slides 76 → T(W) = T(R1) − 1 2 T(R2) Ước lượng: W = δ(R)  TH1: T(W) = 1  Nếu trong R không có bộ nào thì T(W)=0  TH2: T(W) = T(R) DBMS05 – Slides 77  R(a1, a2, , an)  Số bộ phân biệt tối ña của R là tích các V(R, ai), i=1..n → T(W) = min{ 1 2 T(R1), tích các V(R, ai)} Ước lượng: W = (R)  γL(R)  Số lượng bộ trong W và cũng là số lượng nhóm  TH1: T(W) = 1 γ DBMS05 – Slides 78  TH2: T(W) = T(R)  R(a1, a2, , an)  Số lượng nhóm tối ña là tích các V(R, ai), i=1..n→ T(W) = min{ 12 T(R1), tí h các V(R, ai)}  R(a, b)  T(R)=5000  V(R, a)=50  V(R, b)=100 Ví dụ δ σa =10 DBMS05 – Slides 79  S(b, c)  T(S)=2000  V(S, b)=200  V(S, c)=100 R S Ví dụ (tt) δ δ δ 100050 250 1000 500 DBMS05 – Slides 80 σa =10 R Sσa =10 R S 5000 100 2000 5000 2000 100 (1) (2) Ví dụ (tt)  Cộng kích thước sau khi thực hiện các phép toán, ngoại trừ  Các nút lá  Nút gốc DBMS05 – Slides 81  (1): 100+50+1000=1150  (2): 100+1000=1100  Phép lược bỏ trùng lắp thực hiện sau thì tốt hơn Ước lượng số lần truy xuất IOs  Các tham số thống kê  B(R): tổng số block chứa tất cả các bộ của R  f(R): số bộ tối ña trong mỗi block  M: số block trống trên bộ nhớ DBMS05 – Slides 82  Quan tâm  Quan hệ R có ñược gom thành cụm không (clustered)?  Thuộc tính trong các phép toán có chỉ mục không (index)?  Chỉ mục có gom cụm không (clustering index)?  Kết quả cần ñược sắp thứ tự không? Clustering  Clustered-file  Clustered relation R R S S S S R R S T T T U U DBMS05 – Slides 83  Clustering index R R S T r1 r1 r1 r1 r1 r1 r1 r1 r1 r1 r2 r2 r2 r2 r2 r2 r1 r1 r1 r1 r1 r1 r1 r1 r2 r2 r2r1 r1 Ví dụ  R1 R2  T(R1) = 10000  T(R2) = 5000  S(R1) = S(R2) = 1/10 block DBMS05 – Slides 84  M=101 blocks  Số block ñược ñọc (bỏ qua việc ghi) ñể thực hiện phép kết tự nhiên trên là bao nhiêu? Nhận xét  Ước lượng số lần truy xuất IOs không là cách tốt nhất  Bỏ qua chi phí CPU  Bỏ qua tham số thời gian DBMS05 – Slides 85  Xét trường hợp M ñủ hoặc thiếu DBMS05 – Slides 86 5.2 Tối ưu hóa các câu truy vấn  Giới thiệu  Kế hoạch truy vấn  Duyệt bảng  Iterator Nội dung chi tiết DBMS05 – Slides 88  Kế hoạch cho phép chọn  Kế hoạch cho phép kết  Tối ưu hóa câu truy vấn  Phát sinh các kế hoạch truy vấn  So sánh các kế hoạch truy vấn Giới thiệu Câu truy vấn Kế hoạch DBMS05 – Slides 89 Phát sinh Tỉa cành X X Ước lượng chi phí Chi phí Chọn chi phí bé nhất  Ước lượng chi phí và chọn chi phí bé nhất  Ước lượng trước và sau khi chuyển ñổi từ cây truy vấn này sang cây truy vấn khác  Tính toán chi phí (tìm min) Loại bỏ ñi những trường hợp chuyển ñổi có chi phí Giới thiệu (tt) DBMS05 – Slides 90  lớn hơn min  Chú ý  Ước lượng kết quả trung gian  Chưa quyết ñịnh chọn cách thực hiện các phép toán  Ước lượng chi phí không dựa vào việc truy xuất ñĩa  Giải thuật và thuật toán  Exhaustive search  Branch and Bound search  Greedy Giới thiệu (tt) DBMS05 – Slides 91  Hill Climbing  Dynamic programming Quá trình biên dịch Convert Query Parse Execute AnswerParse tree Logical query plan DBMS05 – Slides 92 Apply laws Estimate result sizes Consider physical plans Estimate costs Pick the bestImprove logical query plan Logical query plan + sizes {P1, P2, } {(P1, C1), (P2,C2) } Pi statistics Kế hoạch truy vấn  Chọn phép toán thích hợp  Duyệt bảng  Table-scan  Index-scan Sort-scan DBMS05 – Slides 93   Iterators  Gồm 3 hàm Open(), GetNext() và Close() cho phép lấy ra 1 bộ trong quan hệ R  Chọn thuật toán thích hợp cho phép toán  Ước lượng chi phí Phương pháp duyệt bảng  Table-scan R R R ðọc từng block DBMS05 – Slides 94  Index-scan ðọc thông qua chỉ mục Ind A A R R R Phương pháp duyệt bảng (tt)  Sort-scan  Sắp thứ tự trong lúc ñọc  Cách 1  Nếu quan hệ R có thuộc tính a ñược sắp thứ tự, và a có chỉ mục DBMS05 – Slides 95  B-tree index  Indexed-sequencial  Duyệt trên chỉ mục Phương pháp duyệt bảng (tt)  Sort-scan  Sắp thứ tự trong lúc ñọc  Cách 2  Nếu quan hệ R không quá lớn  ðọc R bằng phương pháp table-scan hoặc index-scan DBMS05 – Slides 96  Dùng thuật toán sắp thứ tự  Cách 3  Nếu R quá lớn  Dùng phương pháp trộn (multiway-merging) Iterators  Open()  Chuẩn bị các cấu trúc dữ liệu phù hợp với quan hệ R  GetNext() DBMS05 – Slides 97  Trả về bộ kế tiếp  Trả về giá trị NotFound  Close()  Dừng việc ñọc sau khi ñã ñọc hết các bộ trong R Iterators và table-scan Open(){ b := the first block of R; t := the first tuple of block b; } GetNext(){ if(t is past the last tuple on block b){ increment b to the next block; if(there is no next block) DBMS05 – Slides 98 return NotFound; else /*b is a new block*/ t := first tuple on block b } /*return t and increment*/ tmp := t; increment t to the next tuple of b; return tmp; } Close(){ } Phép chọn - σC(R)  (1) Cho Aθc là dạng so sánh  A là thuộc tính có chỉ mục  θ là toán tử so sánh =, >, <  c là hằng số (2) Sử dụng phương pháp index-scan DBMS05 – Slides 99  ñể truy xuất các bộ thỏa ñiều kiện ở (1)  (3) Với mỗi bộ thỏa (2), xét tiếp các ñiều kiện còn lại trong C (gọi là bước Filter) Ước lượng chi phí  Cho R(a, b) và σC(R)  Dùng table-scan + filter  Nếu R clustered: B(R)  Nếu R non-clustered: T(R)  Dùng index-scan ñể chọn ra những bộ thỏa ñiều kiện a=val + filter DBMS05 – Slides 100  Nếu a clustering index: B(R) / V(R,a)  Nếu a non-clustering index: T(R) / V(R, a)  Dùng index-scan ñể chọn ra những bộ thỏa ñiều kiện b<val + filter  Nếu b clustering index: B(R) / 3  Nếu b non-clustering index: T(R) / 3 Ví dụ R(x, y, z) R là clustered x, y, z có chỉ mục (z là clustering index) DBMS05 – Slides 101 T(R) = 5000 B(R) = 200 V(R, x) = 100 V(R, y) = 500 σx=1∧y=20∧z<5 (R) Ví dụ (tt)  (1) Dùng table-scan + filter  Cần B(R) = 200  (2) Dùng chỉ mục trên x tìm những bộ thỏa x=1 Sau ñó filter ñể kiểm tra y=2 và z<5  Cần T(R) / V(R, x) = 50 DBMS05 – Slides 102  (3) Dùng chỉ mục trên y tìm những bộ thỏa y=1 Sau ñó filter ñể kiểm tra x=1 và z<5  Cần T(R) / V(R, y) = 10  (4) Dùng chỉ mục cụm trên z tìm những bộ thỏa z<5 Sau ñó filter ñể kiểm tra x=1 và y=1  Cần B(R) / 3 = 67 Phép kết - R1 R2  Nested loops  Merge join  Index join  Hash join DBMS05 – Slides 103 Nested loops for each r ∈ R1 do for each s ∈ R2 do DBMS05 – Slides 104 if r.C =s.C then output the join of r and s Merge join (1) If R1 và R2 chưa ñược sắp thứ tự then sắp thứ tự (2) i=1; j=1 DBMS05 – Slides 105 While i<T(R1) và j<T(R2) do If R1[i].C = R2[j].C then xuất-kết-quả Else If R1[i].C > R2[j].C then j=j+1 Else If R1[i].C < R2[j].C then i=i+1 Ví dụ i R1{i}.C R2{j}.C j 1 10 5 1 2 20 20 2 3 20 20 3 DBMS05 – Slides 106 4 30 30 4 5 40 30 5 50 6 52 7 Index join Giả sử R2.C có chỉ mụcFor each r ∈ R1 { Dùng index trên R2.C chọn những bộ thỏa R2.C = r.C và ñưa vào X DBMS05 – Slides 107 For each s ∈ X output the join of r and s } Hash join  Hàm băm H, giá trị từ 0 ñến k  Buckets của R1: A0, A1, ..., Ak  Buckets của R2: B0, B1, ..., Bk (1) Băm các bộ của R1 và ñưa vào A buckets DBMS05 – Slides 108 (2) Băm các bộ của R2 và ñưa vào B buckets (3) For i=0 to k Tìm các bộ trong bucket Ai và Bi thỏa R1.C = R2.C Ví dụ 2 4 3 5 4 12 R1 R2 Hàm băm theo qui tắc chẵn / lẻ Chẵn 2 4 8 4 12 8 14 DBMS05 – Slides 109 5 8 9 3 13 8 11 14 Lẻ 3 5 9 5 3 13 11 R1 R2 Ước lượng chi phí  Xét thêm các ñiều kiện  Các bộ trong 1 quan hệ có ñược lưu trữ tại các block liên tiếp nhau không?  Các thuộc tính tham gia vào phép kết có DBMS05 – Slides 110 ñược sắp thứ tự hay không?  Có tồn tại chỉ mục không? Ví dụ T(R1) = 10000 T(R2) = 5000 R1 R2 DBMS05 – Slides 111 S(R1) = S(R2) = 1/10 block M = 101 blocks Nested loops Chi phí cho một bộ trong R1: ðọc 1 bộ R + ðọc hết R Giả sử R1 và R2 lưu trữ không liên tiếp DBMS05 – Slides 112 1 2 Tổng cộng: 10000 (1 + 5000) = 50010000 Nested loops (tt) Chi phí cho một chunk trong R1: ðọc 1000 bộ R1 + ðọc hết R2 Giả sử 1 chunk = 100 block DBMS05 – Slides 113 Tổng cộng: (1000 + 5000) = 6000010000 1000 Nested loops (tt) Chi phí cho một chunk trong R2: ðọc 1000 bộ R + ðọc hết R R2 R1 DBMS05 – Slides 114 2 1 Tổng cộng: Giả sử 1 chunk = 100 block (1000 + 10000) = 550005000 1000 Nested loops (tt) Chi phí cho một chunk trong R2: ðọc 1 chunk R + ðọc hết R R2 R1 Giả sử R1 và R2 lưu trữ liên tiếp DBMS05 – Slides 115 2 1 Tổng cộng: Giả sử 1 chunk = 100 block (100 + 1000) = 55005000 1000 Merge join Giả sử R1 và R2 lưu trữ liên tiếp R1.C và R2.C ñã ñược sắp thứ tự R1 R1 DBMS05 – Slides 116 Chi phí: ðọc R1 + ðọc R2 1000 + 500 = 1500 R2 R2 Merge join (tt) Giả sử R1 và R2 lưu trữ liên tiếp R1.C và R2.C chưa sắp thứ tự Sắp thứ tự cho R1.C và R2.C DBMS05 – Slides 117 Tổng chi phí: Merge sort + Merge join Merger Sort Merge sort (1) For each chunk - ðọc chunk - Sắp thứ tự - Ghi chunk DBMS05 – Slides 118 R1 R2 . . . Memory Sorted chunk Merge sort (tt) (2) ðọc tất cả chunks + merge + ghi Sorted file DBMS05 – Slides 119 . . . . . . Memory Sorted chunks Merge sort (tt) Chi phí merge sort: Mỗi bộ ñược ñọc, ghi, ñọc, ghi DBMS05 – Slides 120 R1: 4 × 1000 = 4000 R2: 4 × 500 = 2000 Merge join (tt) Tổng chi phí: Giả sử R1 và R2 lưu trữ liên tiếp R1.C và R2.C chưa sắp thứ tự DBMS05 – Slides 121 Merge sort + Merge join 6000 + 1500 = 7500 Chi phí của nested loops = 5500 TH này merge join không hơn nested loops Index join  Giả sử  R1.C có chỉ mục  R2 lưu trữ liên tiếp và không ñược sắp thứ tự  ðọc R2  Với mỗi bộ trong R2, dùng index trên C tìm DBMS05 – Slides 122 trong R1 các bộ thỏa ñiều kiện  (a) R2.C là khóa ngoại tham chiếu ñến khóa chính R1.C  Chỉ có 1 bộ thỏa ñiều kiện  (b) Giả sử V(R1, C)=5000 và ñược phân bố ñều trong R1  Có T(R1) / V(R1, C) = 10000/5000 = 2 bộ thỏa ñiều kiện Index join (tt) Chi phí (a) 500 + 5000(1) = 5500 (b) 500 + 5000(2) = 10500 DBMS05 – Slides 123 Hash join Giả sử R1 và R2 lưu trữ liên tiếp R1.C và R2.C chưa sắp thứ tự Sử dụng 100 buckets (1) ðọc R1 + hash + ghi xuống bucket DBMS05 – Slides 124 (2) Tương tự cho R2 . . . . . . 10 blocks 100R1 Memory Hash join (tt) (3) ðọc 1 bucket của R1 (4) ðọc 1 bucket tương ứng của R2, dò tìm (5) Lặp ñến khi hết bucket DBMS05 – Slides 125 R2 . . . R1 Memory. . . R1 Hash join (tt) Chi phí: Tạo bucket: ðọc R1 + ghi bucket ðọc R2 + ghi bucket DBMS05 – Slides 126 Kết: ðọc R1 + ðọc R2 3 × (1000 + 500) = 4500 Tổng kết  Nested loops tốt khi các quan hệ không quá lớn  Nếu phép kết bằng (quan hệ không ñược sắp thứ tự và không có chỉ mục) thì hash join luôn luôn tốt nhất Merge + sort tốt khi thực hiện phép kết so sánh DBMS05 – Slides 127  hơn  Nếu quan hệ ñã ñược sắp thứ tự thì nên dùng merge join  Nếu tồn tại chỉ mục trên các thuộc tính thì luôn có ích Các quy tắc tối ưu hóa • Bảng (table): – có khóa chính (Primary Key) – có ít nhất 01 clustered indextable – có số lượng non-clustered index phù hợp. – Non-clustered index phải ñược tạo trên các cột (column) của bảng (table) dựa vào nhu cầu truy vấn. • Dựa theo sự sắp xếp thứ tự như sau khi có bất kỳ index ñược tạo: a) WHERE clause, b) JOIN clause, c) ORDER BY clause, d) SELECT clause • Không nên dùng Views thay cho bảng (table) gốc. • Triggers không nên sử dụng nếu không cần thiết, nên nhập những xử lý từ trigger vào trong thủ tục (stored procedure). • Gỡ bỏ những câu lệnh query trực tiếp và thay bằng thủ tục (stored procedure). • Phải có ít nhất 30% không gian ñĩa cứng trên phân vùng chứa database. • Nếu có thể hãy chuyển UDF (user defined function) sang SP (stored procedure) • Chỉ SELECT những cột cần thiết, không nên SELECT * • Gỡ bỏ các joins từ các bảng (table) không cần thiết • Hạn chế sử dụng con trỏ (cursor) • ðảm bảo phần cứng ñáp ứng nhu cầu của hệ thống.

Các file đính kèm theo tài liệu này:

  • pdfdbms05_6734.pdf