1/30/2012
1
Tối ưu hóa câu truy vấnTối ưu hóa câu truy vấn
Ng ễnNg ễn
HồngHồng
PhươngPhương
1
Ng
uy
ễnNg
uy
ễn
HồngHồng
PhươngPhương
phuongnh@soict.hut.edu.vnphuongnh@soict.hut.edu.vn
http://is.hut.edu.vn/~phuongnhhttp://is.hut.edu.vn/~phuongnh
BộBộmônmôn HệHệthốngthống thôngthông tintin
ViệnViệnCôngCông nghệnghệthôngthông tin tin vàvà TruyềnTruyền thôngthông
ĐạiĐạihọchọcBáchBách KhoaKhoa HàHà NộiNội
Nội dungNộ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ệ
NHP
2
Tổng quan về xử lý truy vấnTổng quan về xử lý truy vấn
•Xửlý mộttruyvấnbaogồm3
bước chính:
–PhântíchvàBiêndịch câu truy vấn:
Trong bướcnày,hệthống phảidịch câu
t
ấ
từ
d
ô
bậ
NHP
3
t
ruy v
ấ
n
từ
d
ạng ng
ô
nng
bậ
ccao
thành mộtngônngữbiểudiễndữllệu
bên trong để máy tính có thểthao tác
trên đó. Mộtbiểudiễnbêntrongthích
hợpvàhỗtrợcho bướctốiưuhóatiếp
theo là biểudiễnbằng ngôn ngữđạisố
quan hệ
Tổng quan về xử lý truy vấn (tiTổng quan về xử lý truy vấn (tiếp)ếp)
–Tốiưuhóacâutruyvấn: Mụctiêucủabước
tốiưu hóa là chọnramộtkếhoạch thựchiện
câu truy vấn có chi phí thấpnhất.
•Để thựchiệnđượcđiềunày,trướctiêntacầnbiếnđổi
1biểuthứcĐSQH đầu vào thành mộtbiểuthức
ĐSQH tương đương nhưng có thểxửlý được 1 cách
NHP
4
hiệuquảvà ít tốnkémhơn. Bướcconđầutiênnày
đượcgọilàtốiưuhóađạisố.
•Tiếptheođó, ta cầnphảiđặctảcác thuậttoánđặc
biệttiếnhànhthựcthicácphéptoán,chọn1chỉdẫn
cụthểnào đóđể sửdụng.
•Các dữliệuthống kê vềCSDL sẽgiúp ta trong quá
trình xem xét và lựachọn. Ví dụnhư:
Tổng quan về xử lý truy vấn (tiTổng quan về xử lý truy vấn (tiếp)ếp)
–Sốbộtrong quan hệ
–Kíchthướccủamộtbộ
–Sốkhối(block)chứacácbộcủaquanhệ
–Sốbộcủaquanhệmà mộtkhốicóthểchứa
–Các thông tin vềcơchếtruy nhập, chỉdẫntrên
quan hệ
Chi
phí
cho
iệc
thực
hiện
một
t
ấn
được
NHP
5
•
Chi
phí
cho
v
iệc
thực
hiện
một
t
ruy v
ấn
được
đobởichiphísửdụng tài nguyên nhưviệc
truy cậpđĩa, thờigian CPUdùngđể thực
hiệnmộttruyvấn.
•Trong chương này, chúng ta sẽtập trung vào
việcđánh giá các biểuthứcđạisốquan hệ
chứkhông đivàochitiếtviệctínhtoánchi
phí cho việcthựchiệnđánh giá mộttruy
vấn.
Tổng quan về xử lý truy vấn (tiTổng quan về xử lý truy vấn (tiếp)ếp)
–Thựchiệnđánh giá truy vấn:Từmộtkế
hoạch thựchiệncóđượcdoTrìnhtốiưuhóa
cung cấp, hệthống sẽtiếnhànhthựchiệncác
thao tác trên dữliệu trong CSDL và đưaracâu
trảlời cho truy vấnđó.
NHP
6
Truy vaán ñaàu vaøo Bieåu thöùc ÑSQH
Keá hoaïch thöïc hieänCaâu tra û lôøi tr uy vaán
Bie â n d òch
truy vaán
Toái öu hoùa
truy vaán
Th ö ï c h i eä n
tìm kieám dl
CSDL
Thoáng keâ veà dl
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012
2
Đánh giá biểu thức ĐSQHĐánh giá biểu thức ĐSQH
•Sau bướcphântíchvàbiêndịch, ta có
mộttruyvấnđượcbiểudiễnbằng một
biểuthứcđạisốquan hệbao gồm
nhiềuphéptoánvàtácđộng lên nhiều
quan
hệ
khác
nhau
Ta
sẽ
phải
tiến
NHP
7
quan
hệ
khác
nhau
.
Ta
sẽ
phải
tiến
hành đánh giá biểuthứcnày.Có2
hướng tiếpcậnđể thực thi quá trình
đánh giá biểuthứcĐSQH:
–Vậtchất hóa (Materialize)
–Đường ống (Pipeline)
Đánh giá biểu thức ĐSQH (tiếp)Đánh giá biểu thức ĐSQH (tiếp)
•Vậtchấthóa:Trong cách tiếpcậnnàythì
ta lầnlượtđánhgiácácphéptoántheo
mộtthứtựthích hợp. Kếtquảcủaviệc
đánh giá mỗiphéptoánsẽđượclưutrong
mộtquanhệtrung gian tạmthờiđể sử
dụng làm đầu vào cho các phép toán tiếp
theo
NHP
8
theo
.
•Điểmbấtlợicủacáchtiếpcậnnàylàviệc
cầnthiếtphảixâydựng các quan hệtrung
gian tạmthờinhấtlàkhicácquanhệnày
thường phảiđượcghirađĩa(trừkhi chúng
có kích thướcrấtnhỏ). Mà việcđọcvàghi
ra đĩa có chi phí khá lớn.
Đánh giá biểu thức ĐSQH (tiếp)Đánh giá biểu thức ĐSQH (tiếp)
•Đường ống: Chúng ta có thểcảithiệnhiệuquả
đánh giá truy vấnbằng cách làm giảmbớtsố
lượng các quan hệtrung gian tạmthờiđượctạo
ra. Điềunàycóthểđạtđượcnhờviệckếthợpmộ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ếtquảcủa
một
phép
toán
được
chuyển
trực
tiếp
cho
phép
NHP
9
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ầnphảilưulạitrong
quan hệtrung gian.
•Rõràng,cáchtiếpcậnthứhai sẽhạnchếđược
nhượcđiểmcủacáchtiếpcậnđầutiên,nhưng có
những trường hợp, ta bắtbuộcphảivậtchấthóa
chứkhông dùng đường ống được.
Đánh giá biểu thức ĐSQH (tiếp)Đánh giá biểu thức ĐSQH (tiếp)
•Vídụ: Chúng ta có mộtbiểuthứcđạisốquan hệ
gồm2phéptoán:kếtnốivàchiếu.
• Trong cách tiếpcậnvậtchấthóa,xuấtpháttừ
phép toán ởmứcthấpnhấtlàphépkếtnốitự
nhiên, kếtquảcủaphépkếtnốinàysẽđượclưu
trong mộtquanhệtrung gian. Sau đó,đọctừ
qan
hệ
tng
gian
nà
để
tiến
hành
chiế
lấ
kết
NHP
10
q
u
an
hệ
t
ru
ng
gian
nà
y
để
tiến
hành
chiế
u
lấ
y
kết
quảmong muốn.
• Trong cách tiếpcậnđường ống, khi mộtbộđược
sinh ra trong phép kếtnối2quanhệ,bộnày sẽ
được chuyểntrựctiếpđếnphépchiếuđể xửlý và
kếtquảđượcghivàoquanhệđầu ra. Quan hệ
kếtquảsẽđượctạolậpmộtcáchtrựctiếp.
Tối ưu hóa các biểu thức ĐSQHTối ưu hóa các biểu thức ĐSQH
•Mụctiêulàtổchứclạitrìnhtựthựchiệncác
phép toán trong biểuthứcđể giảmchiphí
thựchiệnđánh giá biểuthứcđó.
• Trong quá trình tốiưuhóa,tabiểudiễnmột
biểuthứcĐSQH dướidạng mộtcâytoántử.
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
NHP
11
mặt
trong
biểu
thức
,
các
nút
trong
là
các
phép toán trong biểuthức
•Vídụ:Đưa ra tên hãng cung ứng mặthàng
có mã là 'P1':
Select sname From S, SP Where S.sid =
SP.sid And pid = 'P1'
•BiểuthứcĐSQH tương ứng là?
• Cây toán tửtương ứng là?
Các chiến lược tối ưu tổng quátCác chiến lược tối ưu tổng quát
1. Đẩyphépchọnvàphépchiếuxuống thựchiện
sớmnhấtcóthể: vì hai phép toán này giúp làm
giảmkíchthướccủaquanhệtrướckhithựchiện
các phép toán 2 ngôi
2. Nhóm dãy các phép chọnvàchiếu: Sửdụng chiến
lượcnàynếunhưcó mộtdãycácphépchọnhoặc
dãy
các
phép
chiến
trên
cùng
một
quan
hệ
NHP
12
dãy
các
phép
chiến
trên
cùng
một
quan
hệ
3. KếthợpphépchọnvàtíchĐề các thành phép kết
nối: NếukếtquảcủamộtphéptíchĐề các là đối
sốcủa1phépchọncóđiềukiệnchọnlàphépso
sánh giữacácthuộctínhtrên2quanhệtham gia
tích Đề các thì ta nên kếthợp 2 phép toán thành
phép kếtnối.
4. Tìm các biểuthứcconchungtrongbiểuthứcđại
sốquan hệđểđánh giá chỉmộtlần
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012
3
Các chiến lược tối ưu tổng quát (tiếp)Các chiến lược tối ưu tổng quát (tiếp)
5. Xác định các phép toán có thểđượcđưa
vào đường ống và thựchiệnđánh giá
chúng theo đường ống
6. Xửlý các tệpdữliệutrướckhitiếnhành
tính toán: Tạolậpchỉdẫnhaysắpxếptệp
dữliệucóthểgóp phầnlàmgiảmchiphí
của
các
phép
tính
trung
gian
NHP
13
của
các
phép
tính
trung
gian
7. Ướclượng chi phí và lựachọnthứtựthực
hiện: Do vớimỗicâutruyvấncóthểcó
nhiềucáchkhácnhauđể thựchiện, với
việcướng 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ựchiện ..) ta có thểchọncáchđánh
giá biểuthứcĐSQH có chi phí nhỏnhất.
Các phép biến đổi tương đương Các phép biến đổi tương đương
biểu thức biểu thức ĐSQHĐSQH
•HaibiểuthứcĐSQH E1và E2là tương đương
nếu chúng cho cùng mộtkếtquảkhi áp
dụng trên cùng mộttập các quan hệ
•Trongphần này, ta có các ký hiệudạng sau:
à
á
ể
ứ
ố
ệ
NHP
14
–E
1,E
2,E
3,…l
à
c
á
cbi
ể
uth
ứ
cđạis
ố
quan h
ệ
–F
1,F
2,F
3,…làcácđiềukiệnchọnhoặclàcác
điềukiệnkếtnối
–X
1,X
2,…Y,Z,U
1,U
2,…làcáctậpthuộctính
Các phép biến đổi tương đương Các phép biến đổi tương đương
biểu thức biểu thức ĐSQHĐSQH (ti(tiếp)ếp)
1. Quy tắckếthợpcủaphéptíchĐề các và kếtnối
)()(
)*(**)*(
)()(
3
2
2
1
13
2
2
1
1
321321
321321
EEEEEE
EEEEEE
EEEEEE
F
F
F
F

NHP
15
•Quitắcnàysửdụng cho chiếnlượcsố7. Thứtự
thựchiệncácphépkếtnốihaytíchĐề các là rất
quan trọng vì kích thướccủaquanhệtrung gian
có thểrấtlớnnếu không cân nhắckỹ.Lựachọn
thứtựthựchiện các phép toán này thì tùy thuộc
vào kích thướccủa các quan hệtham gia phép
toán và cảngữnghĩacủaquanhệ(mối liên hệ)
2
1
2
1
F
F
F
F
Các phép biến đ
ổ
i tươn
g
đươn
g
Các phép biến đ
ổ
i tươn
g
đươn
g
biểu thức biểu thức ĐSQHĐSQH (ti(tiếp)ếp)
• VD: S* SP * P có thểđượcthựchiệntheo
3thứtựnhưsau
1)(S*SP)*P
2)(S*P)*SP
3)S*(SP*P)
Xét
th
ữ
hĩ
S
P
khô
kết
ối
NHP
16
Xét
th
eo ng
ữ
ng
hĩ
a
S
,
P
khô
ng
kết
n
ối
đượcnên(1)và(3)làtốthơn(2).Xét
vềkích thướcthì(3)tốthơn(1)vìScó
4thuộc tính còn P có 3 thuộc tính, tuy
nhiên, cũng còn tùy thuộcvàolực
lượng của2quanhệSvàPnữa
Các phép biến đổi tương đương Các phép biến đổi tương đương
biểu thức biểu thức ĐSQHĐSQH (ti(tiếp)ếp)
2. Quy tắc giao hoán trong phép tích Đề
các và kết nối
1221
1221
1221
**
EEEE
EEEE
EEEE
FF 
NHP
17
3. Quy tắc đối với dãy các phép chiếu
4. Quy tắc đối với dãy các phép chọn
n
XXXX
XXX
EE
n
...
)()...)(...(
21
121
)()...)(....( ...2121 EE FnFFFnFF
Các phép biến đổi tươn
g
đươn
g
Các phép biến đổi tươn
g
đươn
g
biểu thức biểu thức ĐSQHĐSQH (ti(tiếp)ếp)
5. Quy tắc giao hoán phép chọn
và phép chiếu
Q tắc nà áp d ng khi F là điề
))(())(( EE XFFX
NHP
18
Q
uy
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ó: )))((())(( EE XYFXFX
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012
4
Các phép biến đổi tươn
g
đươn
g
Các phép biến đổi tươn
g
đươn
g
biểu thức biểu thức ĐSQHĐSQH (ti(tiếp)ếp)
6. Quy tắc đối với phép chọn và phép
tích Đề các
• Ta ký hiệu:
–E
1(U1) có nghĩa là biểu thức E1 xác định trên tập thuộc
tính U1
–F
1(U1) có nghĩa là điều kiện chọn F1 xác định trên tập
thuộc tính U
1
NHP
19
thuộc tính U
1
–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:
–trong trường hợp F = F1(U1)
–trong trường hợp F = F1(U1)
F2(U2)
–trong trường hợp F = F1(U1)
F2(U1U2)
))()(( 2211 UEUE
F
211 )( EE
F
)()( 2211 EE FF
))(( 2112 EE
FF
Các phép biến đổi tươn
g
đươn
g
Các phép biến đổi tươn
g
đươn
g
biểu thức biểu thức ĐSQHĐSQH (ti(tiếp)ếp)
7. Quy tắc đối với phép chọn và
phép hợp:
8
Quy tắc đối với phép chọn và
)()()( 2121 EEEE FFF
NHP
20
8
.
Quy tắc đối với phép chọn và
phép trừ:
)()()( 2121 EEEE FFF
Các phép biến đổi tươn
g
đươn
g
Các phép biến đổi tươn
g
đươn
g
biểu thức biểu thức ĐSQHĐSQH (ti(tiếp)ếp)
9. Quy tắc đối với phép chiếu và tích Đề
các:
21
212211
,,
)()())()((
UZUYYZX
EEUEUE ZYX
NHP
21
10.Quy tắc đối với phép chiếu và phép
hợp:
)()()( 2121 EEEE XXX
VVí dụí dụ
• Tìm tên hãng cung ứng ít nhất1mặt
hàng màu đỏ hoặcmàuxanh
SELECTsnameFROMS,P,SP
WHERE S.sid = SP.sid AND P.pid = SP.pid
AND
(colour
=
‘Red’
OR
colour
=
‘Green
’
)
;
NHP
22
AND
(colour
=
Red
OR
colour
=
Green )
;
•Biểuthứcđạisốquan hệtương đương với
câu truy vấntrênlà:
))(( )'''Re'(.... PSPS
GreencolourdcolourpidSPpidPsidSPsidSsname
NHP
23
Lời hay ý đẹpLời hay ý đẹp
"Phẩm cách chân chính củaconngườilàở
trong cách họsống chứkhông phảiởcái họ
có
"
NHP
24
có
Blackie
CuuDuongThanCong.com https://fb.com/tailieudientucntt