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

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

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

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

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

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

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

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

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

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

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

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

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';9第九頁，共36頁。假設(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)法

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

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

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

②б

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

③П總時間=105＋50000＋50000秒=100105秒=27.8小時12第十二頁，共36頁。2.Ｑ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分

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

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

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

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

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

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

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

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

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

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

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

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

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

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

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

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

SC.Cno=’2’

Student.Sno=SC.S

×

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

πSname

Student.Sno=SC.Sno

SC.Cno=2

×

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

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

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

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