關(guān)系查詢和查詢優(yōu)化第一頁，共二十四頁，2022年，8月28日9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行詞法分析語法分析語義轉(zhuǎn)換符號名轉(zhuǎn)換安全性檢查完整性檢查查詢樹代數(shù)優(yōu)化物理優(yōu)化等執(zhí)行策略描述代碼生成執(zhí)行查詢計劃的代碼數(shù)據(jù)庫數(shù)據(jù)字典查詢語句查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行圖9.1查詢處理步驟9.1.1查詢處理的步驟第二頁，共二十四頁，2022年，8月28日9.1.2實現(xiàn)查詢操作的算法示例一、選擇操作的實現(xiàn)

[例1]SELECT*FROMstudentWHERE<條件>C1：無條件；C2：Sno=‘200215121’;C3:Sage>20;C4:Sdept=‘CS’ANDSage>20方法:1.簡單的全表掃描2.索引或散列掃描二、連接操作的實現(xiàn)[例2]SELECT*FROMstudent，SC

WHEREstudent.Sno=SC.Sno方法：1.嵌套循環(huán)方法2.排序合并方法3.索引連接方法4.HashJoin方法第三頁，共二十四頁，2022年，8月28日9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語言的級別很高，使DBMS可以從關(guān)系表達(dá)式中分析查詢語義。第四頁，共二十四頁，2022年，8月28日由DBMS進(jìn)行查詢優(yōu)化的好處用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，系統(tǒng)可以比用戶程序的優(yōu)化做得更好。優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則難以獲得這些信息。如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實際應(yīng)用中往往是不太可能的。優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，而程序員一般只能考慮有限的幾種可能性。優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)。這些技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化相當(dāng)于使的所有人都擁有這些優(yōu)化技術(shù)。第五頁，共二十四頁，2022年，8月28日查詢優(yōu)化目標(biāo)查詢優(yōu)化的總目標(biāo)——選擇有效策略，求得給定關(guān)系表達(dá)式的值實際系統(tǒng)的查詢優(yōu)化步驟1.

將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹2.

根據(jù)一定的等價變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3.選擇低層的操作算法對于語法樹中的每一個操作計算各種執(zhí)行算法的執(zhí)行代價選擇代價小的執(zhí)行算法4.

生成查詢計劃(查詢執(zhí)行方案)查詢計劃是由一系列內(nèi)部操作組成的。第六頁，共二十四頁，2022年，8月28日基于代價模型的優(yōu)化算法集中式數(shù)據(jù)庫單用戶系統(tǒng)總代價=I/O代價+CPU代價多用戶系統(tǒng)總代價=I/O代價+CPU代價+內(nèi)存代價分布式數(shù)據(jù)庫 總代價

=I/O代價+CPU代價[+內(nèi)存代價]+通信代價代價模型第七頁，共二十四頁，2022年，8月28日9.2.2一個實例[例3]求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.SnameFROMStudent,SC WHEREStudent.Sno=SC.SnoANDSC.Cno='2';執(zhí)行策略Ｑ1＝ПＳname(бStudent.Sno=SC.Sno∧SC.Cno='2'

(Student×SC))Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))

Ｑ3＝ПＳname(StudentбSC.Cno='2'(SC))第八頁，共二十四頁，2022年，8月28日9.3代數(shù)優(yōu)化基于關(guān)系代數(shù)等價變換規(guī)則的優(yōu)化方法為代數(shù)優(yōu)化；代數(shù)優(yōu)化策略是通過對關(guān)系代數(shù)表達(dá)式的等價變換來提高查詢效率；關(guān)系代數(shù)表達(dá)式的等價是指用相同的關(guān)系代替兩個表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的；兩個表達(dá)式E1和E2是等價的,記為E1≡E2。第九頁，共二十四頁，2022年，8月28日9.3.1關(guān)系代數(shù)表達(dá)式等價變換規(guī)則設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式l.連接、笛卡爾積交換律

E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1常用的等價變換規(guī)則第十頁，共二十四頁，2022年，8月28日

2.連接、笛卡爾積的結(jié)合律

(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F

F

F

F第十一頁，共二十四頁，2022年，8月28日3.投影的串接定律

πA1,A2,

,An(πB1,B2,,Bm(E))≡πA1,A2,,An(E)假設(shè)：1)E是關(guān)系代數(shù)表達(dá)式2) Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名3){A1,A2,…,An}構(gòu)成{Bl，B2，…，Bm}的子集第十二頁，共二十四頁，2022年，8月28日4.選擇的串接定律

бF1

（бF2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件。5.選擇與投影的交換律

(1)假設(shè):選擇條件F只涉及屬性A1，…，AnбF(πA1,A2,,An(E))≡πA1,A2,,An(бF(E))(2)假設(shè):F中有不屬于A1,…,An的屬性B1,…,BmπA1,A2,,An

(

бF(E))≡πA1,A2,,An(бF

(πA1,A2,,An,B1,B2,,Bm(E)))第十三頁，共二十四頁，2022年，8月28日6.選擇與笛卡爾積的交換律(1)假設(shè)：F中涉及的屬性都是E1中的屬性

бF(E1×E2)≡бF(E1)×E2

(2)假設(shè)：F=F1∧F2，并且F1只涉及E1中的屬性，

F2只涉及E2中的屬性 則由上面的等價變換規(guī)則1，4，6可推出：

бF(E1×E2)≡бF1(E1)×бF2(E2)

(3)假設(shè)：F=F1∧F2，并且F1只涉及E1中的屬性，

F2涉及E1和E2兩者的屬性

бF(E1×E2)≡бF2(бF1(E1)×E2)

它使部分選擇在笛卡爾積前先做第十四頁，共二十四頁，2022年，8月28日7.選擇與并的分配律 假設(shè)：E=E1∪E2，E1，E2有相同的屬性名

бF(E1∪E2)≡бF(E1)∪бF(E2)

8.選擇與差運(yùn)算的分配律 假設(shè)：E1與E2有相同的屬性名

бF(E1-E2)≡бF(E1)-бF(E2)9.選擇對自然連接的分配律бF(E1E2)≡бF(E1)бF(E2)

F只涉及E1與E2的公共屬性第十五頁，共二十四頁，2022年，8月28日10.投影與笛卡爾積的分配 假設(shè)：E1和E2是兩個關(guān)系表達(dá)式，

A1，…，An是E1的屬性，

B1，…，Bm是E2的屬性πA1,A2,…,An,B1,B2,…,Bm

（E1×E2)≡ πA1,A2,…,An（E1)×πB1,B2,…,Bm(E2)l1.投影與并的分配 假設(shè)：E1和E2有相同的屬性名

πA1,A2,…,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)第十六頁，共二十四頁，2022年，8月28日9.3.2查詢樹的啟發(fā)式優(yōu)化啟發(fā)式規(guī)則的代數(shù)優(yōu)化,是對關(guān)系代數(shù)表達(dá)式的查詢樹進(jìn)行優(yōu)化,其典型的規(guī)則有:選擇運(yùn)算應(yīng)盡可能先做

目的：減小中間關(guān)系投影運(yùn)算和選擇運(yùn)算同時做目的：避免重復(fù)掃描關(guān)系把投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合目的：減少掃描關(guān)系的遍數(shù)第十七頁，共二十四頁，2022年，8月28日某些選擇運(yùn)算＋在其前面執(zhí)行的笛卡爾積===>連接運(yùn)算例：бStudent.Sno=SC.Sno

(Student×SC)

StudentSC提取公共子表達(dá)式第十八頁，共二十四頁，2022年，8月28日關(guān)系代數(shù)表達(dá)式的優(yōu)化算法算法：關(guān)系表達(dá)式的優(yōu)化。輸入：一個關(guān)系表達(dá)式的查詢樹。輸出：優(yōu)化的查詢樹。方法：(1)分解選擇運(yùn)算利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為

бF1(бF2(…(бFn(E))…))(2)通過交換選擇運(yùn)算，將其盡可能移到葉端對每一個選擇，利用規(guī)則4～8盡可能把它移到樹的葉端。(3)通過交換投影運(yùn)算，將其盡可能移到葉端 對每一個投影利用規(guī)則3、5、l0、11中的一般形式盡可能把它移向樹的葉端。第十九頁，共二十四頁，2022年，8月28日(4)利用規(guī)則3～5把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成，盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。(5)對內(nèi)結(jié)點(diǎn)分組把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是б，π運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積(×)，而且其后的選擇不能與它結(jié)合為等值連接時除外。把這些單目運(yùn)算單獨(dú)分為一組。第二十頁，共二十四頁，2022年，8月28日例[4]求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.SnameFROMStudent,SC WHEREStudent.Sno=SC.SnoANDSC.Cno='2';πSname

Student.Sno=SC.Sno

SC.Cno=2

×

StudentSC（2）關(guān)系代數(shù)語法樹πSname

Student.Sno=SC.Sno

SC.Cno=2

×

StudentSC（3）優(yōu)化后的查詢樹結(jié)果project(Sname)

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

StudentSC（1）把SQL語句轉(zhuǎn)換成查詢樹第二十一頁，共二十四頁，2022年，8月28日9.4物理優(yōu)化代數(shù)優(yōu)化是改變查詢語句的次序和組合，不涉及底層的存取路徑，物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求的優(yōu)化的查詢計劃，達(dá)到查詢優(yōu)化的目標(biāo)。具體方法有：基于規(guī)則的啟發(fā)式優(yōu)化基于代價估算的優(yōu)化兩者結(jié)合的優(yōu)化方法第二十二頁，共二十四頁，2022