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

關(guān)系查詢處理和查詢優(yōu)化第九章

關(guān)系查詢處理及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化

---關(guān)系代數(shù)表達(dá)式的優(yōu)化9.4物理優(yōu)化

---存取路徑和底層操作算法的選擇關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理查詢處理的任務(wù)：是把用戶提交給RDBMS的查詢語(yǔ)句轉(zhuǎn)換為高效的執(zhí)行計(jì)劃.查詢處理步驟查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行查詢處理步驟：詞法分析語(yǔ)法分析語(yǔ)義分析符號(hào)名轉(zhuǎn)換安全性檢查完整性檢查查詢樹代數(shù)優(yōu)化物理優(yōu)化等執(zhí)行策略描述代碼生成查詢計(jì)劃的執(zhí)行代碼查詢語(yǔ)句數(shù)據(jù)庫(kù)數(shù)據(jù)字典查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行實(shí)現(xiàn)查詢操作的算法示例一、選擇操作的實(shí)現(xiàn)例1SELECT*FROMStudentWHERE<條件表達(dá)式>；

<條件表達(dá)式>：C1：無(wú)條件

C2：Sno=‘200215121’；

C3：Sage>20；

C4：Sdept=‘CS’ANDSage>20；1、簡(jiǎn)單的全表掃描方法順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出。適合：小表2、索引（或散列）掃描方法如果條件表達(dá)式的屬性上有索引（如B+樹索引或Hash索引）,通過(guò)索引先找到滿足條件的元組主碼或元組指針，再通過(guò)元組指針直接在查詢的基本表中找到元組。如C2：二、連接操作的實(shí)現(xiàn)例2SELECT*FROMStudent，SCWHEREStudent.Sno=SC.Sno；1、嵌套循環(huán)方法(nestedloop)簡(jiǎn)單。對(duì)外層循環(huán)Student的每一個(gè)元組，檢查內(nèi)層循環(huán)SC中的每一個(gè)元組，并檢查連接屬性是否相等2、排序-合并方法(sort-mergejoin)常用，適合有序表步驟：若沒排序，首先對(duì)Student、SC按連接屬性Sno排序；取Student第一個(gè)Sno，一次掃描SC中具有相同Sno元組，連接起來(lái)；當(dāng)掃描到SC中第一個(gè)不相同Sno元組時(shí)，返回Student掃描下一個(gè)元組，在掃描SC中具有相同Sno元組，把它們連接起來(lái)；重復(fù)上述步驟，直到Student掃描完。二、連接操作的實(shí)現(xiàn)3、索引連接法在SC上建立屬性Sno索引；對(duì)Student的每一個(gè)元組，由Sno值通過(guò)索引查找相應(yīng)SC元組；把這些SC元組和Student元組連接起來(lái)；循環(huán)執(zhí)行②③，直到Student元組處理完。4、HashJoin方法把連接屬性作為Hash碼，用同一個(gè)Hash函數(shù)把R和S中的元組散列到同一個(gè)Hash文件中；第一步，劃分階段，對(duì)小表R進(jìn)行一遍處理，把它的元組按Hash函數(shù)分散到Hash表的桶中；（假設(shè)：R完全裝入內(nèi)存）第二步，試探階段（連接階段），對(duì)表S進(jìn)行一遍處理，把它的元組散列到適當(dāng)?shù)腍ash桶中，并把元組與來(lái)自R并與之匹配的元組連接起來(lái)。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。查詢優(yōu)化是RDBMS關(guān)鍵技術(shù)、關(guān)系系統(tǒng)的優(yōu)點(diǎn)（關(guān)系系統(tǒng)：支持表結(jié)構(gòu)、選擇連接（自然）操作）查詢優(yōu)化的可能性關(guān)系表達(dá)式語(yǔ)義的級(jí)別很高，使DBMS可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義。由DBMS進(jìn)行查詢優(yōu)化的好處用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率系統(tǒng)可以比用戶程序的優(yōu)化做得更好(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)

代價(jià)模型

集中式數(shù)據(jù)庫(kù) 總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)分布式數(shù)據(jù)庫(kù) 總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)+通信代價(jià)

查詢優(yōu)化的總目標(biāo)：選擇有效策略,求得給定關(guān)系表達(dá)式的值,使得查詢代價(jià)最小。9.2.2一個(gè)實(shí)例例：求選修了課程Ｃ2的學(xué)生姓名

FROMStudent,SC WHEREStudent.Sno=SC.SnoANDSC.Cno='2';假設(shè)1：外存：

Student:1000條,SC:10000條,選修2號(hào)課程:50條假設(shè)2：一個(gè)內(nèi)存塊裝元組:10個(gè)Student,或100個(gè)SC或10個(gè)連接結(jié)果元組;內(nèi)存中一次可以存放:5塊Student元組,1塊SC元組假設(shè)3：讀寫速度：20塊/秒假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法執(zhí)行策略1Ｑ1＝ПＳname(б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ù)時(shí)間=2100/20=105秒中間結(jié)果大小=1000*10000=107(1千萬(wàn)條元組)

寫中間結(jié)果時(shí)間

=10000000/10/20=50000秒

②б

讀數(shù)據(jù)時(shí)間

=50000秒

③П

總時(shí)間=105＋50000＋50000秒=100105秒小時(shí)例1SELECT*FROMStudentWHERE<條件表達(dá)式>；把這些單目運(yùn)算單獨(dú)分為一組。總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)+通信代價(jià)讀取總塊數(shù)=讀Student表塊數(shù)+讀SC表遍數(shù)總時(shí)間＝5＋5秒＝10秒(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。啟發(fā)式規(guī)則優(yōu)化：定性選擇、比較粗糙FROMStudent,SC生成查詢計(jì)劃(查詢執(zhí)行方案)將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合join(Student.輸入：一個(gè)關(guān)系表達(dá)式的查詢樹。WHEREStudent.第二步，試探階段（連接階段），對(duì)表S進(jìn)行一遍處理，把它的元組散列到適當(dāng)?shù)腍ash桶中，并把元組與來(lái)自R并與之匹配的元組連接起來(lái)。2、排序-合并方法(sort-mergejoin)執(zhí)行策略2Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))①

讀取總塊數(shù)=2100塊 讀數(shù)據(jù)時(shí)間=2100/20=105秒 中間結(jié)果大小

=10000（減少1000倍） 寫中間結(jié)果時(shí)間

=10000/10/20=50秒

②б

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

③П

總時(shí)間＝105＋50＋50秒＝205秒分

E1E2≡E2E1關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))C3：Sage>20；SnoANDSC.連接、笛卡爾積的結(jié)合律假設(shè)：1)E是關(guān)系代數(shù)表達(dá)式2、排序-合并方法(sort-mergejoin)代數(shù)優(yōu)化：基于關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化方法讀數(shù)據(jù)時(shí)間=100/20=5秒5、對(duì)于用AND的合取選擇條件，如果有涉及這些屬性的組合索引，則優(yōu)先采用組合索引掃描法，否則使用全表掃描；讀數(shù)據(jù)時(shí)間=2100/20=105秒二、連接操作的啟發(fā)式規(guī)則投影運(yùn)算和選擇運(yùn)算同時(shí)做如果一個(gè)表在連接屬性上有索引，則選用索引連接方法；假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法執(zhí)行策略3Ｑ2＝ПSname(StudentбSC.Cno='2'(SC))

①б

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

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

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

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

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

③П

總時(shí)間＝5＋5秒＝10秒執(zhí)行策略4Ｑ2＝ПＳname(StudentбSC.Cno='2'(SC))假設(shè)SC表在Cno上有索引，Student表在Sno上有索引

①б

讀SC表索引 讀SC表總塊數(shù)

=50/100<1塊 讀數(shù)據(jù)時(shí)間

中間結(jié)果大小=50條不必寫入外存② 讀Student表索引=讀Student表總塊數(shù)=50/10=5塊 讀數(shù)據(jù)時(shí)間③П

總時(shí)間<10秒9.3代數(shù)優(yōu)化代數(shù)優(yōu)化：基于關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化方法關(guān)系代數(shù)表達(dá)式等價(jià)指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的關(guān)系代數(shù)等價(jià)變換規(guī)則設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式

l.連接、笛卡爾積交換律

E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

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

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

F1

F2

F1

F23.投影的串接定律

π

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}的子集0把連接屬性作為Hash碼，用同一個(gè)Hash函數(shù)把R和S中的元組散列到同一個(gè)Hash文件中；選擇低層的操作算法，對(duì)于語(yǔ)法樹中的每一個(gè)操作Cno='2'(SC))join(Student.*每遍塊數(shù)(3)假設(shè)：F=F1∧F2，一、選擇操作的啟發(fā)式規(guī)則SnoANDSC.關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))FROMStudent,SC第一步，劃分階段，對(duì)小表R進(jìn)行一遍處理，把它的元組按Hash函數(shù)分散到Hash表的桶中；бF(E1∪E2)≡бF(E1)∪бF(E2)讀數(shù)據(jù)時(shí)間=100/20=5秒讀數(shù)據(jù)時(shí)間=2100/20=105秒例：求選修了課程Ｃ2的學(xué)生姓名關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）4.選擇的串接定律

бF1

（б

F2（E））≡бF1∧F2(E)選擇的串接律說(shuō)明選擇條件可以合并這樣一次就可檢查全部條件。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ù)等價(jià)變換規(guī)則（續(xù)）6.選擇與笛卡爾積的交換律(1)假設(shè)：F中涉及的屬性都是E1中的屬性

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

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

F2只涉及E2中的屬性 則由上面的等價(jià)變換規(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)

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

關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）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.投影與笛卡爾積的交換

假設(shè)：E1和E2是兩個(gè)關(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)l0.投影與并的交換

假設(shè)：E1和E2有相同的屬性名

πA1,A2,…,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)1、嵌套循環(huán)方法(nestedloop)SnoANDSC.2、對(duì)于選擇條件是主碼=值的查詢，查詢結(jié)果最多是一個(gè)元組，可選擇主碼索引；例1SELECT*FROMStudentWHERE<條件表達(dá)式>；讀數(shù)據(jù)時(shí)間=100/20=5秒如果上面2個(gè)規(guī)則都不適用，其中一個(gè)表較小，則選用HashJoin方法；在SC上建立屬性Sno索引；(3)假設(shè)：F=F1∧F2，（假設(shè)：R完全裝入內(nèi)存）5、對(duì)于用AND的合取選擇條件，如果有涉及這些屬性的組合索引，則優(yōu)先采用組合索引掃描法，否則使用全表掃描；循環(huán)執(zhí)行②③，直到Student元組處理完。πA1,A2,,An(πB1,B2,,Bm(E))≡πA1,A2,,An(E)如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積(×)，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。代數(shù)優(yōu)化：基于關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化方法將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語(yǔ)法樹查詢樹的啟發(fā)式優(yōu)化啟發(fā)式規(guī)則：選擇運(yùn)算應(yīng)盡可能先做

目的：減小中間關(guān)系投影運(yùn)算和選擇運(yùn)算同時(shí)做目的：避免重復(fù)掃描關(guān)系將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合目的：減少掃描關(guān)系的遍數(shù)某些選擇運(yùn)算＋在其前面執(zhí)行的笛卡爾積==>連接運(yùn)算例：б(Student×SC)

StudentSC

找出公共子表達(dá)式（如：視圖定義表達(dá)式）關(guān)系代數(shù)表達(dá)式的優(yōu)化算法算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的查詢樹。輸出：優(yōu)化的查詢樹。方法：（1）分解選擇運(yùn)算利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為

бF1(бF2(…(бFn(E))…))（2）通過(guò)交換選擇運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)選擇，利用規(guī)則4～8盡可能把它移到樹的葉端。（3）通過(guò)交換投影運(yùn)算，將其盡可能移到葉端

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

關(guān)系代數(shù)表達(dá)式的優(yōu)化算法

(續(xù))（4）合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成利用規(guī)則3～5把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。

（5）對(duì)內(nèi)結(jié)點(diǎn)分組把上述得到的語(yǔ)法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是б，π運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積(×)，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。

（6）生成程序生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。各步的順序是任意的，只要保證任何一組的計(jì)算不會(huì)在它的后代組之前計(jì)算。

例題例：求選修了課程Ｃ2的學(xué)生姓名

FROMStudent,SC WHEREStudent.Sno=SC.SnoANDSC.Cno='2';語(yǔ)法樹結(jié)果project(Sname)

select(SC.Cno=

2

)

join(Student.Sno=SC.Sno)

StudentSC關(guān)系代數(shù)語(yǔ)法樹πSname

SC.Cno=’2’

Student.Sno=SC.S

×

StudentSC利用優(yōu)化算法把語(yǔ)法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式πSname

Student.Sno=SC.Sno

SC.Cno=

2

×

StudentSCπSname

SC.Cno=

2

Stude