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

10/11/2019

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ệ

Tối ưu hóa câu truy vấn

Nguyễn Hồng Phương

phuongnh@soict.hust.edu.vn

http://is.hust.edu.vn/~phuongnh

Bộ môn Hệ thống thông tin

Viện Công nghệ thông tin và Truyền thông

Đại học Bách Khoa Hà Nội

1

2

NHP

Tổng quan về xử lý truy vấn

Tổng quan về xử lý truy vấn (tiếp)

–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.

•Xử lý một truy vấn bao gồm 3

bước chính:

• Để thực hiện được điều này, trước tiên ta cần biến đổi

–Phân tích và Biên dịch câu truy vấn:

Trong bước này, hệ thống phải 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 bên trong thích

hợp và hỗ trợ cho bước tối ưu hóa tiếp

theo là biểu diễn bằng ngôn ngữ đại số

1

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 1 cách

hiệu quả và ít tốn kém hơn. Bước con đầu tiên này

được gọi là tối ưu hóa đại số.

• Tiếp theo đó, ta 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 1 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ư:

quan hệ

3

4

NHP

1

10/11/2019

Tổng quan về xử lý truy vấn (tiếp)

– 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ệ

–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 đó.

Bieân dòch

truy vaán

•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 một truy vấn.

Truy vaán ñaàu vaøo

Bieåu thöùc ÑSQH

Toái öu hoùa

truy vaán

Thoáng keâ veà dl

•Trong chương này, chúng ta sẽ 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 việc tính toán chi

phí cho việc thực hiện đánh giá một truy

Thöïc hieän

tìm kieám dl

Caâu traû lôøi truy vaán

Keá hoaïch thöïc hieän

vấn.

CSDL

5

6

NHP

Đánh giá biểu thức ĐSQH

Đánh giá biểu thức ĐSQH (tiếp)

• Vật chất hóa: Trong cách tiếp cận này thì

ta 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 của cách tiếp cận này là việc

cần thiết phải xây dựng các quan hệ trung

gian tạm thời nhất là khi các quan hệ này

thường phải được ghi ra đĩa (trừ khi chúng

có kích thước rất nhỏ). Mà việc đọc và ghi

ra đĩa có chi phí khá lớn.

• 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. Ta sẽ phải tiến

hành đánh giá biểu thức này. Có 2

hướng tiếp cận để thực thi quá trình

đánh giá biểu thức ĐSQH:

–Vật chất hóa (Materialize)

–Đường ống (Pipeline)

7

8

NHP

2

10/11/2019

Đá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.

• Đường ống: Chúng ta có thể cải thiện hiệu quả

đánh giá truy vấn bằng cách làm giảm bớt số

lượng các quan hệ trung gian tạm thời được tạo

ra. Điều này có thể đạt được nhờ việc 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.

• Rõ ràng, 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.

• 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.

9

10

NHP

Tối ưu hóa các biểu thức ĐSQH

Các chiến lược tối ưu tổng quát

• 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

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.

• 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 =

SP.sid And pid = 'P1'

• Biểu thức ĐSQH tương ứng là?

4. 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

• Cây toán tử tương ứng là?

11

12

NHP

3

10/11/2019

Các phép biến đổi tương đương

Các chiến lược tối ưu tổng quát (tiếp)

biểu thức ĐSQH

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

• Hai biểu thức ĐSQH E₁và E₂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:

– E₁, E₂, E₃, … là các biểu thức đại số quan hệ

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.

– F₁, F₂, F₃, … là các điều kiện chọn hoặc là các

điều kiện kết nối

– X₁, X₂, … Y, Z, U₁, U₂, … là các tập thuộc tính

13

14

NHP

Các phép biến đổi tương đương

biểu thức ĐSQH (tiếp)

Các phép biến đổi tương đương

biểu thức ĐSQH (tiếp)

1. Quy tắc kết hợp của phép tích Đề các và kết nối

• VD: S* SP * P có thể được thực hiện theo 3

thứ tự như sau

1)(S*SP)*P

(E₁ E₂) E₃ E₁ (E₂ E₃)

(E₁* E₂)* E₃ E₁*(E₂* E₃)

2)(S*P)*SP

3)S*(SP*P)

(E₁E₂)E₃ E₁(E₂E₃)

F1

F 2

F1

F 2

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

•

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 nếu không cân nhắc kỹ. Lựa chọn

thứ tự thực hiện các phép toán này thì 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ệ)

15

16

NHP

4

10/11/2019

Các phép biến đổi tương đương

biểu thức ĐSQH (tiếp)

2. Quy tắc giao hoán trong phép tích Đề

5. Quy tắc giao hoán phép chọn

và phép chiếu

các và kết nối

E₁ E₂ E₂ E₁

E₁* E₂ E₂* E₁

E₁ E₂ E₂ E₁

 _X( _F(E))   _F( _X(E))

F

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)))

3. Quy tắc đối với dãy các phép chiếu

 _X( _X...  _X(E)...)   _X(E)

1

2

n

1

X ₁ X ₂ ...  X _n

4. Quy tắc đối với dãy các phép chọn

_F1( _{F 2}.... _Fn(E)...)   _{F1F 2...Fn}(E)



17

18

NHP

Các phép biến đổi tương đương

biểu thức ĐSQH (tiếp)

Các phép biến đổi tương đương

biểu thức ĐSQH (tiếp)

6. Quy tắc đối với phép chọn và phép

tích Đề các

7. Quy tắc đối với phép chọn và

phép hợp:

 _F(E₁ E₂)   _F(E₁)   _F(E₂)

8. Quy tắc đối với phép chọn và

phép trừ:

•

Ta ký hiệu:

–

E₁(U₁) có nghĩa là biểu thức E₁xác định trên tập thuộc

tính U₁

F₁(U₁) có nghĩa là điều kiện chọn F₁xác định trên tập

thuộc tính U₁

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:

•

tương đương với:



_F(E₁(U₁)  E₂(U ₂))

_F1(E₁)  E₂

 _F(E₁ E₂)   _F(E₁)   _F(E₂)



–

trong trường hợp F = F₁(U₁)

_F1(E₁) _{F 2}(E₂)

trong trường hợp F = F₁(U₁)



F₂(U₂)



( (E₁) E₂)

trong trường hợp F = F₁(U₁)

–

F₂(U^F₁²U₂)^F1

19

20

NHP

5

10/11/2019

Các phép biến đổi tương đương

biểu thức ĐSQH (tiếp)

Ví dụ

9. Quy tắc đối với phép chiếu và tích Đề

các:

• Tìm tên hãng cung ứng ít nhất 1 mặt

hàng màu đỏ hoặc màu xanh

SELECT sname FROM S, P, SP

WHERE S.sid = SP.sid AND P.pid = SP.pid

AND (colour = ‘Red’ OR colour = ‘Green’);

 _X(E₁(U₁)  E₂(U ₂))  _Y(E₁)   _Z(E₂)

X  YZ ,Y  U₁, Z  U ₂

10.Quy tắc đối với phép chiếu và phép

hợp:

• Biểu thức đại số quan hệ tương đương với

câu truy vấn trên là:

 _X(E₁ E₂)   _X(E₁)   _X(E₂)



_sname( _{S.sid SP.sid P. pid SP. pid(colour'Re d'colour'Green')}(S  SP P))

21

22

NHP

Lời hay ý đẹp

"Phẩm cách chân chính của con người là ở

trong cách họ sống chứ không phải ở cái họ

có"

Blackie

23

24

NHP

6

Bài giảng Cơ sở dữ liệu - Chương 5: Tối ưu hóa câu truy vấn - Nguyễn Hồng Phương