CƠ SỞ DỮ LIỆU Chương 5,6,7 1 Chương 5 - Tối ưu hóa câu truy vấn NỘI DUNG: • Tổng quan về xử lý truy vấn • Tối ưu hóa các biểu thức đại số quan hệ 2 5. Tổng quan về xử lý truy vấn • Xử lý một truy vấn bao gồm 3 bước chính: – Phân tích và Biên dịch câu truy vấn: dịch câu truy vấn từ dạng ngôn ngữ bậc cao thành một ngôn ngữ biểu diễn dữ liệu bên trong để máy tính có thể thao tác trên đó. Một biểu diễn thích hợp là bằng ngôn ngữ đại số quan hệ – Tối ưu hóa câu truy vấn: Mục tiêu của bước tối ưu hóa là chọn ra một kế hoạch thực hiện câu truy vấn có chi phí thấp nhất. – Thực hiện đánh giá truy vấn: Từ một kế hoạch thực hiện có được do Trình tối ưu hóa cung cấp, hệ thống sẽ tiến hành thực hiện các thao tác trên dữ liệu trong CSDL và đưa ra câu trả lời cho truy vấn đó.
3 4 Tối ưu hóa câu truy vấn Mục tiêu của bước tối ưu hóa là chọn ra một kế hoạch thực hiện câu truy vấn có chi phí thấp nhất. • Để thực hiện được điều này, trước tiên cần biến đổi một biểu thức ĐSQH đầu vào thành một biểu thức ĐSQH tương đương nhưng có thể xử lý được một cách hiệu quả và ít tốn kém hơn. Bước này gọi là tối ưu hóa đại số. • Tiếp theo đó, cần phải đặc tả các thuật toán đặc biệt tiến hành thực thi các phép toán , chọn một chỉ dẫn cụ thể nào đó để sử dụng.
• Các dữ liệu thống kê về CSDL sẽ giúp ta trong quá trình xem xét và lựa chọn. Ví dụ như: Số bộ trong quan hệ; Kích thước của một bộ; Số khối (block) chứa các bộ của quan hệ; Số bộ của quan hệ mà một khối có thể chứa; Các thông tin về cơ chế truy nhập, chỉ dẫn trên quan hệ • Chi phí cho việc thực hiện một truy vấn được đo bởi chi phí sử dụng tài nguyên như: việc truy cập đĩa, thời gian CPU dùng để thực hiện truy vấn. • Chương này tập trung vào việc đánh giá các biểu thức đại số quan hệ chứ không đi vào chi tiết tính toán chi phí cho việc thực hiện đánh giá truy vấn. 5 Đánh giá biểu thức ĐSQH • Sau bước phân tích và biên dịch, ta có một truy vấn được biểu diễn bằng một biểu thức đại số quan hệ bao gồm nhiều phép toán và tác động lên nhiều quan hệ khác nhau, cần tiến hành đánh giá biểu thức này.
Có 2 hướng tiếp cận: (i) Vật chất hóa (Materialize), và (ii) Đường ống (Pipeline). • Vật chất hóa: lần lượt đánh giá các phép toán theo một thứ tự thích hợp. Kết quả của việc đánh giá mỗi phép toán sẽ được lưu trong một quan hệ trung gian tạm thời để sử dụng làm đầu vào cho các phép toán tiếp theo. Điểm bất lợi là cần các quan hệ trung gian (ghi ra đĩa có chi phí khá lớn).
• Đường ống: kết hợp một vài phép toán quan hệ vào một đường ống của các phép toán. Trong đường ống thì kết quả của một phép toán được chuyển trực tiếp cho phép toán tiếp theo mà không cần phải lưu lại trong quan hệ trung gian. Cách tiếp cận thứ hai sẽ hạn chế được nhược điểm của cách tiếp cận đầu tiên, nhưng có những trường hợp, ta bắt buộc phải vật chất hóa chứ không dùng đường ống được. 6 Đánh giá biểu thức ĐSQH (tiếp) • Ví dụ: Chúng ta có một biểu thức đại số quan hệ gồm 2 phép toán: kết nối và chiếu.
• Trong cách tiếp cận vật chất hóa, xuất phát từ phép toán ở mức thấp nhất là phép kết nối tự nhiên, kết quả của phép kết nối này sẽ được lưu trong một quan hệ trung gian. Sau đó , đọc từ quan hệ trung gian này để tiến hành chiếu lấy kết quả mong muốn. • Trong cách tiếp cận đường ống, khi một bộ được sinh ra trong phép kết nối 2 quan hệ, bộ này sẽ được chuyển trực tiếp đến phép chiếu để xử lý và kết quả được ghi vào quan hệ đầu ra. Quan hệ kết quả sẽ được tạo lập một cách trực tiếp.
Tối ưu hóa các biểu thức ĐSQH • Mục tiêu là tổ chức lại trình tự thực hiện các phép toán trong biểu thức để giảm chi phí thực hiện đánh giá biểu thức đó. • Trong quá trình tối ưu hóa, ta biểu diễn một biểu thức ĐSQH dưới dạng một cây toán tử. Trong cây thì các nút lá là các quan hệ có mặt trong biểu thức, các nút trong là các phép toán trong biểu thức • Ví dụ : Đưa ra tên hãng cung ứng mặt hàng có mã là 'P1': Select sname From S, SP Where S.sid And pid = 'P1' • Biểu thức ĐSQH tương ứng là ? • Cây toán tử tương ứng là ? 8 Ví dụ Cho CSDL gồm các quan hệ: S (sid, sname, size, city) P (pid, pname, colour, weight, city) SP (sid, pid, quantity) • Đưa ra tên hãng cung ứng mặt hàng có mã là 'P1‘ Select sname From S, SP Where S.sid and pid = 'P1‘ ➔ Biểu thức đại số quan hệ và cây toán tử: 9 Các chiến lược tối ưu tổng quát 1. Đẩy phép chọn và phép chiếu xuống thực hiện sớm nhất có thể: vì hai phép toán này giúp làm giảm kích thước của quan hệ trước khi thực hiện các phép toán 2 ngôi 2.
Nhóm dãy các phép chọn và chiếu: Sử dụng chiến lược này nếu như có một dãy các phép chọn hoặc dãy các phép chiếu trên cùng một quan hệ 3. Kết hợp phép chọn và tích Đề các thành phép kết nối: Nếu kết quả của một phép tích Đề các là đối số của 1 phép chọn có điều kiện chọn là phép so sánh giữa các thuộc tính trên 2 quan hệ tham gia tích Đề các thì ta nên kết hợp 2 phép toán thành phép kết nối. Tìm các biểu thức con chung trong biểu thức đại số quan hệ để đánh giá chỉ một lần 5. Xác định các phép toán có thể được đưa vào đường ống và thực hiện đánh giá chúng theo đường ống 6.
Xử lý các tệp dữ liệu trước khi tiến hành tính toán: Tạo lập chỉ dẫn hay sắp xếp tệp dữ liệu có thể góp phần làm giảm chi phí của các phép tính trung gian 7. Ước lượng chi phí và lựa chọn thứ tự thực hiện: Do với mỗi câu truy vấn có thể có nhiều cách khác nhau để thực hiện, với việc ước lượng chi phí (số phép tính, tài nguyên sử dụng, dung tích bộ nhớ, thời gian thực hiện .) ta có thể chọn cách đánh giá biểu thức ĐSQH có chi phí nhỏ nhất. 10 Các phép biến đổi tương đương biểu thức ĐSQH • Hai biểu thức ĐSQH E1 và E2 là tương đương nếu chúng cho cùng một kết quả khi áp dụng trên cùng một tập các quan hệ • Trong phần này, ta có các ký hiệu dạng sau: E1, E2, E3, … là các biểu thức đại số quan hệ; F1, F2, F3, … là các điều kiện chọn hoặc là các điều kiện kết nối; X1, X2, … Y, Z, U1, U2, … là các tập thuộc tính 1. Quy tắc kết hợp của phép tích Đề các và kết nối ( E1 E 2 ) E3 E1 ( E 2 E3 ) ( E1 * E 2 ) * E3 E1 * ( E 2 * E3 ) ( E1 E 2 ) E3 E1 ( E 2 E3 ) F1 F2 F1 F2 • Qui tắc này sử dụng cho chiến lược số 7.
Thứ tự thực hiện các phép kết nối hay tích Đề các là rất quan trọng vì kích thước của quan hệ trung gian có thể rất lớn. Lựa chọn thứ tự tùy thuộc vào kích thước của các quan hệ tham gia phép toán và cả ngữ nghĩa của quan hệ (mối liên hệ) 11 • Ví dụ: S* SP * P có thể được thực hiện theo 3 thứ tự như sau 1) (S*SP)*P 2) (S*P)*SP 3) S*(SP*P) Xét theo ngữ nghĩa S, P không kết nối được nên (1) và (3) là tốt hơn (2). Xét về kích thước thì (3) tốt hơn (1) vì S có 4 thuộc tính còn P có 3 thuộc tính, tuy nhiên, cũng còn tùy thuộc vào lực lượng của 2 quan hệ S và P nữa 12 Các phép biến đổi tương đương biểu thức ĐSQH 2. Quy tắc giao hoán trong phép tích Đề các và kết nối E1 E 2 E 2 E1 E1 * E 2 E 2 * E1 E1 E 2 E 2 E1 F F 3.
Quy tắc đối với dãy các phép chiếu X 1 ( X 2. Quy tắc đối với dãy các phép chọn F1 ( F 2. Quy tắc giao hoán phép chọn và phép chiếu X ( F ( E )) F ( X ( E )) Quy tắc này áp dụng khi F là điều kiện xác định được trên tập thuộc tính X. Tổng quát hơn ta có: X ( F ( E )) X ( F ( XY ( E ))) 6.
Quy tắc đối với phép chọn và phép tích Đề các: Ký hiệu: E1(U1) có nghĩa là biểu thức E1 xác định trên tập thuộc tính U1; F1(U1) có nghĩa là điều kiện chọn F1 xác định trên tập thuộc tính U1. Quy tắc biến đổi liên quan đến phép chọn và tích Đề các được phát biểu như sau: F ( E1 (U 1 ) E 2 (U 2 )) tương đương với: – F 1 ( E1 ) E 2 trong trường hợp F = F1(U1) – F 1 ( E1 ) F 2 ( E 2 ) trong trường hợp F = F1(U1) F2(U2) – F 2 ( F 1 ( E1 ) E 2 ) trong trường hợp F = F1(U1) F2(U1U2) 14 7. Quy tắc đối với phép chọn và phép hợp: F ( E1 E 2 ) F ( E1 ) F ( E 2 ) 8. Quy tắc đối với phép chọn và phép trừ: F ( E1 − E 2 ) F ( E1 ) − F ( E 2 ) 9.
Quy tắc đối với phép chiếu và tích Đề các: X ( E1 (U 1 ) E 2 (U 2 )) Y ( E1 ) Z ( E 2 ) X = YZ , Y U 1 , Z U 2 10.