3/28/14
Tối ưu truy vấn 1
Chương 9
TỐI ƯU TRUY VẤN
3/28/14
Tối ưu truy vấn
2
Giới thiệu

Các ngôn ngữ bậc cao nói chung khi xử lý trong máy đều rất tốn nhiều thời gian.

Tối ưu câu hỏi: là quá trình biến đổi câu hỏi sang một câu hỏi tương đương(nghĩa là cho
cùng một kết quả) để giảm thiểu thời gian tính toán.

Việc tối ưu không nhất thiết phải trên mọi khả năng có thể của các cách cài đặt của các
câu hỏi. Chúng ta có thể thỏa hiệp giữa giải thuật phức tạp hoặc/và tốn kém không gian
lưu trữ với việc tiết kiệm thời gian xử lý.
3/28/14
Tối ưu truy vấn
3
Giới thiệu

Giả sử để xử lý 1000 bản ghi mất 1 giây → để xử lý 4.850.000 bản ghi chúng ta mất 4.850
giây: đây quả là một thời gian khó chấp nhận cho việc chờ đợi kết quả của một câu truy
vấn !

Khi tối ưu hóa xử lý thông tin người ta ưu tiên tối ưu hóa về thời gian hơn là tối ưu hóa lưu
trữ dữ liệu, thậm chí “hy sinh” luôn cả dạng chuẩn để đạt được tốc độ xử lý nhanh hơn.

Dung lượng đĩa cứng ngày nay đã đạt được một mức độ khá lớn, tuy nhiên cũng có khả
năng thiếu không gian tính toán cho máy nếu chúng ta không lưu tâm đến việc tối ưu hóa

5
Giới thiệu
SELECT B, D
FROM R, S
WHERE R.A=‘c’ AND S.E=2 AND R.C=S.C

R(A, B, C)

S(C, D, E)
Tối ưu truy vấn
6
Giới thiệu (tt)
10 x 2
C D ES
20 y 2
30 z 2
40 x 1
50 y 3
c 2 10
A B CR
a 1 10
b 1 10
d 2 10
e 3 10
Kết quả
B D
2 x

Câu truy vấn được thực hiện như thế nào?
Tối ưu truy vấn

.
.
Tối ưu truy vấn
9
Giới thiệu (tt)

Cách 2
-
Phép chọn (selection)
-
Phép kết (natural join)
-
Phép chiếu (projection)
Π
B,D
[ σ
R.A=‘c’
(R) σ
S.E=2
(S)]
Tối ưu truy vấn
10
Giới thiệu (tt)
C D E
10 x 2
20 y 2
30 z 2
40 x 1
50 y 3
SA B C

Chiếu trên thuộc tính B và D
Tối ưu truy vấn
12
Giới thiệu (tt)
C D E
10 x 2
20 y 2
30 z 2
40 x 1
50 y 3
S
A B C
a 1 10
b 1 10
c 2 10
d 2 10
e 3 10
R
I2
I1
=‘c’
<c, 2, 10>
A
C
<10, x, 2>
Kiểm tra E=2?
Kết quả <2, x>
Bộ có A=‘c’ kế tiếp
<c, 5, 20>
Tối ưu truy vấn

Pick the best
Execute
Answer
Parse tree
Logical query plan
Improve logical query plan
Logical query plan + sizes
{P1, P2, … }
{(P1,C1), (P2,C2) … }
Pi
statistics
Tối ưu truy vấn
16
Cây phân tích
<Query>
<SFW>
SELECT <SelectList> FROM <FromList> WHERE
<Condition>
<Attribute>
<SelectList>
<Relation>
<FromList>
<Attribute> = <Attribute>
<Tuple> IN <Query>
<Attribute> LIKE <pattern>
<Condition> AND <Condition>
…
Tối ưu truy vấn
17


balance
= <pattern>
100
Tối ưu truy vấn
19

Customer(cusID, cusNm, cusStreet, cusCity)

Account(accID, cusID, balance)
Ví dụ 2
SELECT cusNm
FROM Customer, Account
WHERE Customer.cusID = Account.cusID
AND balance = 100
Tối ưu truy vấn
20
Ví dụ 2 (tt)
<Query>
<SFW>
SELECT <SelectList> FROM <FromList> WHERE
<Condition>
<Attribute>
<Relation>
cusNm Customer
<Relation>
Account
,
<Condition> <Condition>AND
<Attribute> <Pattern>=<Attribute> <Attribute>=
Customer.cusID Account.cusID balance 100

Execute
Answer
Parse tree
Logical query plan
Improve logical query plan
Logical query plan + sizes
{P1, P2, … }
{(P1, C1), (P2,C2) … }
Pi
statistics
Tối ưu truy vấn
23
Biến đổi sang ĐSQH

Truy vấn đơn
-
Xét câu trúc <SFW>

Thay thế <FromList> 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ế <Condition> thành phép chọn σ
C

Thay thế <SelectList> thành phép chiếu π
L
R S T
…
x

σ
R <Condition>
STuple Operator
Tối ưu truy vấn