數(shù)據(jù)庫(kù)系統(tǒng)原理-8

數(shù)據(jù)庫(kù)系統(tǒng)原理---8第一頁(yè)，共36頁(yè)?！窘虒W(xué)目標(biāo)】

了解數(shù)據(jù)庫(kù)管理系統(tǒng)的查詢步驟，了解查詢優(yōu)化的概念、基本方法和技術(shù)，為提高查詢效率和系統(tǒng)性能打下基礎(chǔ)。

【教學(xué)重點(diǎn)】查詢處理的基本步驟、查詢的代數(shù)優(yōu)化與物理優(yōu)化方法。

【教學(xué)難點(diǎn)】查詢優(yōu)化方案的選擇與效率評(píng)估，優(yōu)化算法的代價(jià)估算。2第二頁(yè)，共36頁(yè)。第一節(jié)、關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理【教學(xué)目標(biāo)】了解數(shù)據(jù)庫(kù)執(zhí)行查詢操作的過(guò)程了解選擇、連接操作的過(guò)程比較不同方法的時(shí)空效率3第三頁(yè)，共36頁(yè)。查詢處理步驟查詢分析對(duì)查詢語(yǔ)句進(jìn)行掃描、詞法和語(yǔ)法分析。

查詢檢查檢查語(yǔ)句中對(duì)象有效性，檢查權(quán)限和約束。

查詢優(yōu)化對(duì)可供選擇的執(zhí)行策略和操作算法進(jìn)行挑選。

查詢執(zhí)行根據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計(jì)劃。

4第四頁(yè)，共36頁(yè)。查詢操作算法示例選擇操作的實(shí)現(xiàn)簡(jiǎn)單全表掃描方法索引(或散列)掃描方法

連接操作的實(shí)現(xiàn)嵌套循環(huán)方法排序-合并方法索引連接方法HashJoin方法5第五頁(yè)，共36頁(yè)。第二節(jié)、關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化【教學(xué)目標(biāo)】了解數(shù)據(jù)庫(kù)查詢優(yōu)化技術(shù)概況通過(guò)一個(gè)實(shí)例了解優(yōu)化的有效性6第六頁(yè)，共36頁(yè)。查詢優(yōu)化概述查詢優(yōu)化的可行性關(guān)系代數(shù)的表達(dá)式語(yǔ)義級(jí)別高。系統(tǒng)實(shí)現(xiàn)優(yōu)化的可行性1.優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息2.物理統(tǒng)計(jì)信息改變后能自動(dòng)重新優(yōu)3.優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃4.優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)7第七頁(yè)，共36頁(yè)。代價(jià)模型集中式數(shù)據(jù)庫(kù)單用戶系統(tǒng)

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

總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)分布式數(shù)據(jù)庫(kù) 總代價(jià)=I/O代價(jià)+CPU代價(jià)[+內(nèi)存代價(jià)]+通信代價(jià)8第八頁(yè)，共36頁(yè)。查詢優(yōu)化必要性的一個(gè)例子例：求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';9第九頁(yè)，共36頁(yè)。假設(shè)1：外存： Student:1000條,SC:10000條,選修2號(hào)課程:50條假設(shè)2：一個(gè)內(nèi)存塊裝元組:10個(gè)Student,或100個(gè)SC, 內(nèi)存中一次可以存放:5塊Student元組,1塊SC元組和若干塊連接結(jié)果元組假設(shè)3：讀寫速度：20塊/秒假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法

10第十頁(yè)，共36頁(yè)。執(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秒11第十一頁(yè)，共36頁(yè)。不同的執(zhí)行策略,考慮I/O時(shí)間

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

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

②б

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

③П總時(shí)間=105＋50000＋50000秒=100105秒=27.8小時(shí)12第十二頁(yè)，共36頁(yè)。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秒=3.4分

13第十三頁(yè)，共36頁(yè)。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秒14第十四頁(yè)，共36頁(yè)。4.Ｑ2＝ПＳname(StudentбSC.Cno='2'(SC))假設(shè)SC表在Cno上有索引，Student表在Sno上有索引

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

中間結(jié)果大小=50條不必寫入外存15第十五頁(yè)，共36頁(yè)。②

讀Student表索引= 讀Student表總塊數(shù)=50/10=5塊 讀數(shù)據(jù)時(shí)間③П總時(shí)間<10秒算法掃Student表掃SC次數(shù)連接假設(shè)記錄總耗時(shí)Q120遍20遍1千萬(wàn)Student:1千條Sc:1萬(wàn)條Cno=2:50條。一次讀一塊入內(nèi)存。10萬(wàn)秒Q220遍20遍1萬(wàn)205秒Q31遍1遍5010秒16第十六頁(yè)，共36頁(yè)。第三節(jié)、代數(shù)優(yōu)化【教學(xué)目標(biāo)】了解關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則了解查詢樹(shù)的啟發(fā)式優(yōu)化方法17第十七頁(yè)，共36頁(yè)。關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的上面的優(yōu)化策略大部分都涉及到代數(shù)表達(dá)式的變換18第十八頁(yè)，共36頁(yè)。選擇運(yùn)算應(yīng)盡可能先做

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

投影運(yùn)算和選擇運(yùn)算同時(shí)做目的：避免重復(fù)掃描關(guān)系將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合目的：減少掃描關(guān)系的遍數(shù)典型的啟發(fā)式規(guī)則19第十九頁(yè)，共36頁(yè)。某些選擇運(yùn)算＋在其前面執(zhí)行的笛卡爾積===>連接運(yùn)算例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC提取公共子表達(dá)式20第二十頁(yè)，共36頁(yè)。關(guān)系代數(shù)表達(dá)式的優(yōu)化算法

算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的語(yǔ)法樹(shù)。輸出：計(jì)算該表達(dá)式的程序。方法：（1）分解選擇運(yùn)算利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為бF1(бF2(…(бFn(E))…))21第二十一頁(yè)，共36頁(yè)。（2）通過(guò)交換選擇運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)選擇，利用規(guī)則4～8盡可能把它移到樹(shù)的葉端。

（3）通過(guò)交換投影運(yùn)算，將其盡可能移到葉端

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

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

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

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

25第二十五頁(yè)，共36頁(yè)。優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示2．代數(shù)優(yōu)化：把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3．物理優(yōu)化：選擇低層的存取路徑4．生成查詢計(jì)劃，選擇代價(jià)最小的26第二十六頁(yè)，共36頁(yè)。（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示例：求選修了課程Ｃ2的學(xué)生姓名 SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';27第二十七頁(yè)，共36頁(yè)。（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示語(yǔ)法樹(shù)結(jié)果project(Sname)

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

StudentSC28第二十八頁(yè)，共36頁(yè)。關(guān)系代數(shù)語(yǔ)法樹(shù)πSname

SC.Cno=’2’

Student.Sno=SC.S

×

StudentSC29第二十九頁(yè)，共36頁(yè)。（2）代數(shù)優(yōu)化利用優(yōu)化算法把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式

πSname

Student.Sno=SC.Sno

SC.Cno=2

×

StudentSC30第三十頁(yè)，共36頁(yè)。（3）物理優(yōu)化：選擇低層的存取路徑-優(yōu)化器查找數(shù)據(jù)字典獲得當(dāng)前數(shù)據(jù)庫(kù)狀態(tài)信息選擇字段上是否有索引連接的兩個(gè)表是否有序連接字段上是否有索引然后根據(jù)一定的優(yōu)化規(guī)則選擇存取路徑

如本例中若SC表上建有Cno的索引，則應(yīng)該利用這個(gè)索引，而不必順序掃描SC表。31第三十一頁(yè)，共36頁(yè)。（4）生成查詢計(jì)劃，選擇代價(jià)最小的在作連接運(yùn)算時(shí)，若兩個(gè)表(設(shè)為R1，R2)均無(wú)序，連接屬性上也沒(méi)有索引，則可以有下面幾種查詢計(jì)劃：

對(duì)兩個(gè)表作排序預(yù)處理對(duì)R1在連接屬性上建索引對(duì)R2在連接屬性上建索引在R1，R2的連接屬性上均建索引對(duì)不同的查詢計(jì)劃計(jì)算代價(jià)，選擇代價(jià)最小的一個(gè)。在計(jì)算代價(jià)時(shí)主要考慮磁盤讀寫的I/O數(shù)，內(nèi)存CPU處理時(shí)間在粗略計(jì)算時(shí)可不考慮。

32第三十二頁(yè)，共36頁(yè)。第四節(jié)、物理優(yōu)化【教學(xué)目標(biāo)】了解物理優(yōu)化可選方案了解基于代價(jià)的優(yōu)化33第三十三頁(yè)，共36頁(yè)。物理優(yōu)化可選方案