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

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.