Bài giảng Các hệ cơ sở dữ liệu - 5. Tối ưu hóa truy vấ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.