關(guān)系查詢處理和其查詢優(yōu)化課件

第九章關(guān)系查詢處理和其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化第九章關(guān)系查詢處理和其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢19.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1查詢處理步驟分4個階段：查詢分析，查詢檢查，查詢優(yōu)化，查詢執(zhí)行9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1查詢處理步驟21查詢分析對查詢語句進行掃描、詞法分析和語法分析。2查詢檢查根據(jù)數(shù)據(jù)字典對合法的查詢語句進行語義檢查，即檢查語句中的數(shù)據(jù)庫對象，如屬性名、關(guān)系名，是否存在和是否有效。權(quán)限和完整性檢查，轉(zhuǎn)換為查詢樹1查詢分析33查詢優(yōu)化在許多的執(zhí)行策略中選擇一個高效的查詢處理策略。分為代數(shù)優(yōu)化和物力優(yōu)化。4查詢執(zhí)行生成查詢計劃，由代碼生成器生成執(zhí)行查詢的代碼。3查詢優(yōu)化4查詢語句詞法分析語法分析語義分析符號名轉(zhuǎn)換安全性檢查完整性檢查查詢樹代數(shù)優(yōu)化物理優(yōu)化等執(zhí)行策略描述代碼生成查詢計劃的執(zhí)行代碼查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行查詢語句詞法分析安全性檢查查詢樹代數(shù)優(yōu)化執(zhí)行策略描述代碼生成59.1.2實現(xiàn)查詢操作的算法示例一、選擇操作的實現(xiàn)例select*fromstudentwhere<條件表達式>;條件為：C1：無條件 C2:sno=‘200215121’C3:sage>20C4:sdept=‘CS’ANDsage>20;9.1.2實現(xiàn)查詢操作的算法示例61.簡單的全表掃描對小表簡單有效，對大表費時，效率低snoSnameSsexSagesdept20021513220021512220021512120021525…….1.簡單的全表掃描snoSnameSsexSagesdept72.索引掃描方法如果選擇條件中的屬性上有索引，用索引掃描法。通過索引先找到滿足條件的元組主碼或指針，再通過指針找基表中的數(shù)據(jù)2.索引掃描方法8snoSnameSsexSagesdept20021513220021512220021512120021525…….索引地址200215121200215122200215125200215132……snoSnameSsexSagesdept2002151329二、連接操作的實現(xiàn)連接操作是最費時的操作例： select* fromstudent,sc wherestudent.sno=sc.sno二、連接操作的實現(xiàn)101.嵌套循環(huán)方法Snosname5837……snocno757838……1.嵌套循環(huán)方法Snosname5837……snocno75112.排序-合并方法適合于連接的諸表已經(jīng)排序的情況步驟：1）先對待連接的表在連接屬性上排序2）取左表的第一個元組，一次掃描右表，找連接屬性相等的元組，把他們連接起來3）當(dāng)在右表中找到第一個與左表提供的值不相等時，返回左表取下一個元組再往下掃描右表。重復(fù)這一過程，直到左表掃描完畢。2.排序-合并方法12Snosname5837……snocno757838……sno357788…sno3578…Snosname5837……snocno757838……sn133.索引連接方法步驟：1）在sc表上建立屬性sno的索引2）對student中的每一個sno,通過sc的索引找相應(yīng)的sc元組3）把這些元組與student中的當(dāng)前元組連接起來4）重復(fù)2）3）直到student表處理完畢3.索引連接方法149.2關(guān)系系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述9.2關(guān)系系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述159.2.1查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。

查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語言的級別很高，使DBMS可以從關(guān)系表達式中分析查詢語義。9.2.1查詢優(yōu)化概述查詢優(yōu)化的必要性16由DBMS進行查詢優(yōu)化的好處用戶不必考慮如何最好地表達查詢以獲得較好的效率系統(tǒng)可以比用戶程序的優(yōu)化做得更好(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則難以獲得這些信息

由DBMS進行查詢優(yōu)化的好處用戶不必考慮如何最好地表達查詢以17由DBMS進行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實際應(yīng)用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)由DBMS進行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改18查詢優(yōu)化目標(biāo)查詢優(yōu)化的總目標(biāo)選擇有效策略，求得給定關(guān)系表達式的值實際系統(tǒng)的查詢優(yōu)化步驟1.將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹2.根據(jù)一定的等價變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式查詢優(yōu)化目標(biāo)查詢優(yōu)化的總目標(biāo)19實際系統(tǒng)的查詢優(yōu)化步驟3.選擇低層的操作算法對于語法樹中的每一個操作計算各種執(zhí)行算法的執(zhí)行代價選擇代價小的執(zhí)行算法4.生成查詢計劃(查詢執(zhí)行方案)查詢計劃是由一系列內(nèi)部操作組成的。實際系統(tǒng)的查詢優(yōu)化步驟3.選擇低層的操作算法20

代價模型

集中式數(shù)據(jù)庫單用戶系統(tǒng)

總代價=I/O代價+CPU代價多用戶系統(tǒng)

總代價=I/O代價+CPU代價+內(nèi)存代價分布式數(shù)據(jù)庫 總代價=I/O代價+CPU代價[+內(nèi)存代價]+通信代價

代價模型

集中式數(shù)據(jù)庫219.2.2一個實例例：求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';9.2.2一個實例例：求選修了課程Ｃ2的學(xué)生姓名22假設(shè)1：外存： Student:1000條,SC:10000條,選修2號課程:50條假設(shè)2：一個內(nèi)存塊裝元組:10個Student,或100個SC, 內(nèi)存中一次可以存放:5塊Student元組,1塊SC元組和若干塊連接結(jié)果元組假設(shè)3：讀寫速度：20塊/秒假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法

假設(shè)1：外存：233種執(zhí)行策略Q1＝ПSname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))

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

3種執(zhí)行策略Q1＝ПSname(бStudent.Sn24執(zhí)行策略1Q1＝ПSname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))

①Student×SC讀取總塊數(shù)=讀Student表塊數(shù)+讀SC表遍數(shù)*每遍塊數(shù)

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100

讀數(shù)據(jù)時間=2100/20=105秒執(zhí)行策略1Q1＝ПSname(бStudent.Sno=SC25不同的執(zhí)行策略,考慮I/O時間

中間結(jié)果大小=1000*10000=107(1千萬條元組)

寫中間結(jié)果時間=10000000/10/20=50000秒

②б

讀數(shù)據(jù)時間=50000秒

③П總時間=105＋50000＋50000秒=100105秒=27.8小時不同的執(zhí)行策略,考慮I/O時間

中間結(jié)果大小=1000262.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))

① 讀取總塊數(shù)=2100塊 讀數(shù)據(jù)時間=2100/20=105秒 中間結(jié)果大小=10000（減少1000倍） 寫中間結(jié)果時間=10000/10/20=50秒

②б

讀數(shù)據(jù)時間=50秒

③П

總時間＝105＋50＋50秒＝205秒=3.4分

2.Ｑ2＝ПＳname(бSC.Cno='2'(St273.Ｑ3＝ПSname(StudentбSC.Cno='2'(SC))

①б 讀SC表總塊數(shù)=10000/100=100塊

讀數(shù)據(jù)時間=100/20=5秒

中間結(jié)果大小=50條不必寫入外存

② 讀Student表總塊數(shù)=1000/10=100塊

讀數(shù)據(jù)時間=100/20=5秒

③П

總時間＝5＋5秒＝10秒3.Ｑ3＝ПSname(StudentбS284.Ｑ3＝ПＳname(StudentбSC.Cno='2'(SC))假設(shè)SC表在Cno上有索引，Student表在Sno上有索引

①б 讀SC表索引 讀SC表總塊數(shù)=50/100<1塊 讀數(shù)據(jù)時間

中間結(jié)果大小=50條不必寫入外存4.Ｑ3＝ПＳname(StudentбSC.29② 讀Student表索引 讀Student表總塊數(shù)=50/10=5塊 讀數(shù)據(jù)時間③П總時間<10秒②309.3代數(shù)優(yōu)化關(guān)系代數(shù)表達式等價指用相同的關(guān)系代替兩個表達式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的上面的優(yōu)化策略大部分都涉及到代數(shù)表達式的變換9.3代數(shù)優(yōu)化關(guān)系代數(shù)表達式等價31

9.3.1常用的等價變換規(guī)則

設(shè)E1、E2等是關(guān)系代數(shù)表達式，F(xiàn)是條件表達式

l.連接、笛卡爾積交換律 E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

9.3.1常用的等價變換規(guī)則

32關(guān)系代數(shù)等價變換規(guī)則（續(xù)）

2.連接、笛卡爾積的結(jié)合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F

F

F

F

關(guān)系代數(shù)等價變換規(guī)則（續(xù)）

33關(guān)系代數(shù)等價變換規(guī)則（續(xù)）3.投影的串接定律

π

A1,A2,

,An(π

B1,B2,

,Bm(E))≡π

A1,A2,

,An(E)假設(shè)：1) E是關(guān)系代數(shù)表達式2) Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名3){A1,A2,…,An}構(gòu)成{Bl，B2，…，Bm}的子集關(guān)系代數(shù)等價變換規(guī)則（續(xù)）3.投影的串接定律34關(guān)系代數(shù)等價變換規(guī)則（續(xù)）4.選擇的串接定律

бF1（б

F2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件。關(guān)系代數(shù)等價變換規(guī)則（續(xù)）4.選擇的串接定律35關(guān)系代數(shù)等價變換規(guī)則（續(xù)）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)))關(guān)系代數(shù)等價變換規(guī)則（續(xù)）5.選擇與投影的交換律36關(guān)系代數(shù)等價變換規(guī)則（續(xù)）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)

關(guān)系代數(shù)等價變換規(guī)則（續(xù)）6.選擇與笛卡爾積的交換律37關(guān)系代數(shù)等價變換規(guī)則（續(xù)）(3)假設(shè)：F=F1∧F2，

F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性 бF(E1×E2)≡бF2(бF1(E1)×E2)

它使部分選擇在笛卡爾積前先做

關(guān)系代數(shù)等價變換規(guī)則（續(xù)）(3)假設(shè)：F=F1∧F2，38關(guān)系代數(shù)等價變換規(guī)則（續(xù)）7.選擇與并的交換 假設(shè)：E=E1∪E2，E1，E2有相同的屬性名 бF(E1∪E2)≡бF(E1)∪бF(E2)

8.選擇與差運算的交換 假設(shè)：E1與E2有相同的屬性名 бF(E1-E2)≡бF(E1)-бF(E2)關(guān)系代數(shù)等價變換規(guī)則（續(xù)）7.選擇與并的交換399.選擇對自然連接的分配律бF(E1E2)≡бF(E1)бF(E2)

F只涉及E1與E2的公共屬性9.選擇對自然連接的分配律40關(guān)系代數(shù)等價變換規(guī)則（續(xù)）10.投影與笛卡爾積的交換

假設(shè)：E1和E2是兩個關(guān)系表達式，

A1，…，An是E1的屬性，

B1，…，Bm是E2的屬性πA1,A2,…,An,B1,B2,…,Bm（E1×E2)≡ πA1,A2,…,An（E1)×πB1,B2,…,Bm(E2)關(guān)系代數(shù)等價變換規(guī)則（續(xù)）10.投影與笛卡爾積的交換41關(guān)系代數(shù)等價變換規(guī)則（續(xù)）l1.投影與并的交換

假設(shè)：E1和E2有相同的屬性名 πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)關(guān)系代數(shù)等價變換規(guī)則（續(xù)）l1.投影與并的交換42小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律3：合并或分解投影運算4：合并或分解選擇運算5-9：選擇運算與其他運算交換5，10，11：投影運算與其他運算交換小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律439.3.2查詢樹的啟發(fā)式優(yōu)化選擇運算應(yīng)盡可能先做

目的：減小中間關(guān)系在執(zhí)行連接操作前對關(guān)系適當(dāng)進行預(yù)處理按連接屬性排序在連接屬性上建立索引

投影運算和選擇運算同時做目的：避免重復(fù)掃描關(guān)系將投影運算與其前面或后面的雙目運算結(jié)合目的：減少掃描關(guān)系的遍數(shù)9.3.2查詢樹的啟發(fā)式優(yōu)化選擇運算應(yīng)盡可能先做44查詢優(yōu)化的一般準(zhǔn)則（續(xù)）某些選擇運算＋在其前面執(zhí)行的笛卡爾積===>連接運算例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC提取公共子表達式查詢優(yōu)化的一般準(zhǔn)則（續(xù)）某些選擇運算＋在其前面執(zhí)行的笛卡爾45關(guān)系代數(shù)表達式的優(yōu)化算法

算法：關(guān)系表達式的優(yōu)化輸入：一個關(guān)系表達式的語法樹。輸出：計算該表達式的程序。方法：（1）分解選擇運算利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為бF1(бF2(…(бFn(E))…))關(guān)系代數(shù)表達式的優(yōu)化算法算法：關(guān)系表達式的優(yōu)化46關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（2）通過交換選擇運算，將其盡可能移到葉端對每一個選擇，利用規(guī)則4～9盡可能把它移到樹的葉端。

（3）通過交換投影運算，將其盡可能移到葉端

對每一個投影利用規(guī)則3，10，l1，5中的一般形式盡可能把它移向樹的葉端。

關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（2）通過交換選擇運算，將其47關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（4）合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成利用規(guī)則3～5把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。

關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（4）合并串接的選擇和投影，48關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（5）對內(nèi)結(jié)點分組把上述得到的語法樹的內(nèi)節(jié)點分組。每一雙目運算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是б，π運算)。如果其后代直到葉子全是單目運算，則也將它們并入該組，但當(dāng)雙目運算是笛卡爾積(×)，而且其后的選擇不能與它結(jié)合為等值連接時除外。把這些單目運算單獨分為一組。

關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（5）對內(nèi)結(jié)點分組49關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（6）生成程序生成一個程序，每組結(jié)點的計算是程序中的一步。各步的順序是任意的，只要保證任何一組的計算不會在它的后代組之前計算。

關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（6）生成程序50優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示2．代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3．物理優(yōu)化：選擇低層的存取路徑4．生成查詢計劃，選擇代價最小的優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示51優(yōu)化的一般步驟(續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示例：求選修了課程Ｃ2的學(xué)生姓名 SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';優(yōu)化的一般步驟(續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示52（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示語法樹結(jié)果project(Sname)

select(SC.Cno=

2

)

join(Student.Sno=SC.Sno)

StudentSC（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示語法樹結(jié)果project(S53關(guān)系代數(shù)語法樹πSname

SC.Cno=’2’

Student.Sno=SC.S

×

StudentSC關(guān)系代數(shù)語法樹πSnameSC.Cno=’2’Stu54（2）代數(shù)優(yōu)化利用優(yōu)化算法把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式

πSname

Student.Sno=SC.Sno

SC.Cno=

2

×

StudentSC（2）代數(shù)優(yōu)化利用優(yōu)化算法把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式πS55例:對于如下數(shù)據(jù)庫：

S(S＃,SNAME,AGE，SEX) SC(S#,C#,GRADE) C(C＃,CNAME,TEACHER)現(xiàn)有一個查詢語句：查詢至少學(xué)習(xí)LIU老師所授一門課程的女學(xué)生學(xué)號和姓名。該查詢語句的關(guān)系代數(shù)表達式為：ΠS#，SNAME(σTEACHER=‘LIU’

SEX=‘F’(SSCC))例:對于如下數(shù)據(jù)庫：ΠS#，SNAME(σTEACHER=‘56自然聯(lián)接的計算過程如下：計算R×S；--計算笛卡爾積設(shè)R和S的公共屬性是A1,A2…Ak,挑選R×S中滿足R.A1=S.A1,…R.AK=S.AK的那些元組；--選擇公共屬性值相等的元組。去掉S.A1,…S.AK這些列。--做投影操作。則此查詢語句的關(guān)系代數(shù)表達式為：ΠS#，SNAME(σTEACHER=‘LIU’

SEX=‘F’(ΠL(σSC.C#=C.C#

SC.S#=S.S#(S×SC×C))))這里L(fēng)為S＃,SNAME,AGE，SEX，C#,GRADE,CNAME,TEACHER自然聯(lián)接的計算過程如下：則此查詢語句的關(guān)系代數(shù)表達式為：ΠS57ΠσΠσS#,SNAMETEACHER=‘LIU’

SEX=‘F’SC.C#=C.C#

SC.S#=S.S#S＃,SNAME,AGE，SEX，C#,GRADE,CNAME,TEACHER×S×CSCΠσΠσS#,SNAMETEACHER=‘LIU’SE58下面使用優(yōu)化算法對語法樹進行優(yōu)化1）將每個選擇操作分裂成兩個選擇運算。共得到四個選擇操作σteacher=‘liu’σsex=‘f’σc.c#=sc.c#σsc.s#=s.s#下面使用優(yōu)化算法對語法樹進行優(yōu)化592)使用等價變換規(guī)則，把四個選擇操作盡可能的向樹的葉端靠攏。根據(jù)規(guī)則4和5可以把σteacher=‘liu’和σsex=‘f’移到投影和另外兩個選擇操作下面，得到表達式σteacher=‘liu’（σsex=‘f’（C

×SC)×S)) 其中，外層選擇僅涉及到關(guān)系C，內(nèi)層選擇僅涉及到關(guān)系S，所以上式又可變化為

σteacher=‘liu’（C

）×

SC）×σsex=‘f’（S) σsc.s#=s.s#不能再往葉端移動了，因為他的屬性涉及到兩個關(guān)系Sc和S，但σc.c#=sc.c#還可以向下移，與迪卡爾積交換位置2)使用等價變換規(guī)則，把四個選擇操作盡可能的向樹的葉端靠攏。60然后根據(jù)規(guī)則3，把兩個投影合并為一個，這樣，原來的語法樹變成了如下形式。然后根據(jù)規(guī)則3，把兩個投影合