數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)孫杰查詢優(yōu)化技術(shù)課件

1、數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)第11章 查詢優(yōu)化技術(shù)生物醫(yī)學(xué)軟件工程教研室數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)查詢優(yōu)化的必要性查詢優(yōu)化的必要性v 例：查詢選修了課程例：查詢選修了課程c031的學(xué)生的姓名的學(xué)生的姓名sc)(student(osc.snoostudent.snsname)scstudent(031cno.sc csname)(031.scstudentccnoscsname數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 為了對(duì)查詢的效率進(jìn)行比較，我們進(jìn)行如為了對(duì)查詢的效率進(jìn)行比較，我們進(jìn)行如下的假設(shè)：下的假設(shè)：v 外存：外存：student

2、：1000條；條；sc：10000條；條；選修選修2號(hào)課程：號(hào)課程：50條；條；v 一個(gè)內(nèi)存塊裝元組：一個(gè)內(nèi)存塊裝元組：10個(gè)個(gè)student或或100個(gè)個(gè)sc，內(nèi)存中一次可以存放：，內(nèi)存中一次可以存放：5塊塊student元元組，組，1塊塊sc元組和若干塊連接結(jié)果元組；元組和若干塊連接結(jié)果元組；v 讀寫速度：讀寫速度：20塊塊/秒；秒；數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v studentsc讀取時(shí)間讀取時(shí)間=讀取總塊數(shù)讀取總塊數(shù)讀取速度讀取速度讀取總塊數(shù)讀取總塊數(shù)=讀讀student表塊數(shù)表塊數(shù)+讀讀sc表遍數(shù)表遍數(shù)*每遍塊數(shù)每遍塊數(shù)=1000/10+(1000/(105)

3、(10000/100) =100+20100=2100寫中間結(jié)果的時(shí)間寫中間結(jié)果的時(shí)間=中間結(jié)果的大小磁中間結(jié)果的大小磁盤塊容量讀寫速度盤塊容量讀寫速度中間結(jié)果大小中間結(jié)果大小 = 1000*10000 = 107(1千萬(wàn)千萬(wàn)條元組條元組)sc)(student(osc.snoostudent.snsname讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=2100/20=105秒秒寫中間結(jié)果時(shí)間寫中間結(jié)果時(shí)間 = 10000000/10/20 = 50000秒秒數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 運(yùn)算需讀取中間結(jié)果運(yùn)算需讀取中間結(jié)果讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間 = 50000秒秒 v v 總時(shí)間總時(shí)間 =10

4、55000050000秒秒 v = 100105秒秒v = 27.8小時(shí)小時(shí)數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 讀取總塊數(shù)讀取總塊數(shù)= 2100塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=2100/20=105秒秒中間結(jié)果大小中間結(jié)果大小=10000 （減少（減少1000倍）倍）寫中間結(jié)果時(shí)間寫中間結(jié)果時(shí)間=10000/10/20=50秒秒 v 讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=50秒秒v v 總時(shí)間總時(shí)間1055050秒秒205秒秒=3.4分分 )scstudent(031cno.sc csname數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 讀讀sc表總塊數(shù)表總塊數(shù)= 10000/100=10

5、0塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=100/20=5秒秒 中間結(jié)果大小中間結(jié)果大小=50條條 不必寫入外存不必寫入外存讀讀student表總塊數(shù)表總塊數(shù)= 1000/10=100塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=100/20=5秒秒v 總時(shí)間總時(shí)間55秒秒10秒秒)(031.scstudentccnoscsname數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 讀讀sc表索引表索引=讀讀sc表總塊數(shù)表總塊數(shù)= 50/1001塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間 中間結(jié)果大小中間結(jié)果大小=50條條 不必寫入外存不必寫入外存v 讀讀student表索引表索引=讀讀student表總塊數(shù)表總塊數(shù)= 50/10=5塊塊讀數(shù)

6、據(jù)時(shí)間讀數(shù)據(jù)時(shí)間v 總時(shí)間總時(shí)間10秒秒假設(shè)假設(shè) sc 表在表在 cno上有索引上有索引student 表在表在 sno上有索引上有索引)(031.scstudentccnoscsname數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)查詢優(yōu)化的一般規(guī)則查詢優(yōu)化的一般規(guī)則v 規(guī)則規(guī)則1：選擇和投影操作盡早執(zhí)行：選擇和投影操作盡早執(zhí)行v 減少中間結(jié)果減少中間結(jié)果數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)查詢優(yōu)化的一般規(guī)則查詢優(yōu)化的一般規(guī)則v 規(guī)則規(guī)則2：把某些選擇操作與鄰接笛卡爾積相：把某些選擇操作與鄰接笛卡爾積相結(jié)合，形成一個(gè)連接操作結(jié)合，形成一個(gè)連接操作v 連接操作比笛卡爾積節(jié)省時(shí)

7、間，特別是等值連接操作比笛卡爾積節(jié)省時(shí)間，特別是等值連接連接。v student.son=sc.sno(studentsc)sc)v student studentsc數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)查詢優(yōu)化的一般規(guī)則查詢優(yōu)化的一般規(guī)則v 規(guī)則規(guī)則3：同時(shí)執(zhí)行相同關(guān)系上的多個(gè)選擇和：同時(shí)執(zhí)行相同關(guān)系上的多個(gè)選擇和投影操作投影操作v 避免重復(fù)掃描關(guān)系避免重復(fù)掃描關(guān)系數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)查詢優(yōu)化的一般規(guī)則查詢優(yōu)化的一般規(guī)則v 規(guī)則規(guī)則4：把投影操作與鄰接操作結(jié)合起來(lái)執(zhí)：把投影操作與鄰接操作結(jié)合起來(lái)執(zhí)行行v 減少掃描關(guān)系的遍數(shù)減少掃描關(guān)系的遍數(shù)數(shù)據(jù)庫(kù)原

8、理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)查詢優(yōu)化的一般規(guī)則查詢優(yōu)化的一般規(guī)則v 規(guī)則規(guī)則5：在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行：在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理預(yù)處理v 按連接屬性排序按連接屬性排序v 在連接屬性上建立索引在連接屬性上建立索引數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)查詢優(yōu)化的一般規(guī)則查詢優(yōu)化的一般規(guī)則v 規(guī)則規(guī)則6：提取公共表達(dá)式：提取公共表達(dá)式數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)關(guān)系代數(shù)等價(jià)變換規(guī)律關(guān)系代數(shù)等價(jià)變換規(guī)律v 等價(jià)的概念等價(jià)的概念：設(shè)：設(shè)e1和和e2是兩個(gè)關(guān)系代謝表是兩個(gè)關(guān)系代謝表達(dá)式。如果達(dá)式。如果e1和和e2中表示相同的關(guān)系，則中表示

9、相同的關(guān)系，則稱稱e1和和e2等價(jià)。等價(jià)。數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律1：選擇串接律：選擇串接律v 其中其中e是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，ci是選擇條件是選擇條件.v 選擇條件可以合并，一次可以檢查多個(gè)條件選擇條件可以合并，一次可以檢查多個(gè)條件)()(211eennccccandandc數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律2：選擇交換律：選擇交換律v 其中其中e是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，ci是選擇條件是選擇條件.)()(1221eecccc數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律

10、等價(jià)規(guī)律3：投影串接律：投影串接律v 其中，其中，e是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，li是投影屬性集是投影屬性集合，且合，且l1 l2 ln)()(121eelllln數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律4：選擇投影交換律：選擇投影交換律v 其中，其中，e是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，l是投影屬性集是投影屬性集合，合，c是選擇條件，是選擇條件，c值設(shè)計(jì)值設(shè)計(jì)l中屬性中屬性)()(eelccl數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律5：連接和笛卡爾積交換律：連接和笛卡爾積交換律v 其中，其中，e1 和和e2 是關(guān)系代數(shù)表達(dá)

11、式，是關(guān)系代數(shù)表達(dá)式，c是連是連接條件。接條件。12211221eeeeeeeecc數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律6：集合操作的交換律：集合操作的交換律v 其中，其中，e1和和e2是關(guān)系代數(shù)表達(dá)式是關(guān)系代數(shù)表達(dá)式12211221eeeeeeee數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律7：連接、笛卡爾積和集合操作的：連接、笛卡爾積和集合操作的結(jié)合律結(jié)合律)()()()()()()()(3213213213213213213213212121eeeeeeeeeeeeeeeeeeeeeeeecccc數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第1

12、1章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律8：選擇、連接和笛卡爾積的分配：選擇、連接和笛卡爾積的分配律律v 部分的選擇可以在笛卡爾積部分的選擇可以在笛卡爾積(或連接或連接)前先做；前先做；)()()()()()()()()()(2121212121212121121111112211212121eeeeeeeeeeeeeeeecccccccccccccc數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律9：投影、連接和笛卡爾積的分配：投影、連接和笛卡爾積的分配律律)()()()()()()()()()()()(212121212121212121212121eeeeeeeeee

13、eeeeeellllllllcllcllclcl數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律10：選擇與集合操作的分配律：選擇與集合操作的分配律)()()()()()()()()(212121212121eeeeeeeeeeeeccccccccc數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 等價(jià)規(guī)律等價(jià)規(guī)律11：投影與集合操作的分配律：投影與集合操作的分配律)()()()()()()()()(212121212121eeeeeeeeeeeelllllllll數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)關(guān)系代數(shù)優(yōu)化算法關(guān)系代數(shù)優(yōu)化算法查詢樹查詢樹v 查詢樹

14、查詢樹是一種表示關(guān)系代數(shù)表達(dá)式的樹形是一種表示關(guān)系代數(shù)表達(dá)式的樹形結(jié)構(gòu)。結(jié)構(gòu)。葉子節(jié)點(diǎn)表示關(guān)系葉子節(jié)點(diǎn)表示關(guān)系內(nèi)節(jié)點(diǎn)表示關(guān)系代數(shù)操作內(nèi)節(jié)點(diǎn)表示關(guān)系代數(shù)操作自底向上執(zhí)行自底向上執(zhí)行數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 處理一個(gè)查詢需要構(gòu)造該查詢的內(nèi)部表示處理一個(gè)查詢需要構(gòu)造該查詢的內(nèi)部表示查詢樹查詢樹v 高級(jí)查詢語(yǔ)言定義的查詢語(yǔ)句高級(jí)查詢語(yǔ)言定義的查詢語(yǔ)句v 關(guān)系代數(shù)表達(dá)式關(guān)系代數(shù)表達(dá)式(查詢樹查詢樹)v 優(yōu)化算法優(yōu)化算法最終的結(jié)果查詢樹最終的結(jié)果查詢樹數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)例例v select a from r1, r2, r3 v where p=

15、15 and n=user;v 關(guān)系代數(shù)表達(dá)式關(guān)系代數(shù)表達(dá)式v a(p=15and n=user (r1r2r3)r1r2r3p=15 and n=usera數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)查詢優(yōu)化算法的描述查詢優(yōu)化算法的描述v 算法輸入算法輸入：關(guān)系代數(shù)表達(dá)式：關(guān)系代數(shù)表達(dá)式v 算法輸出算法輸出：計(jì)算輸入關(guān)系代數(shù)表達(dá)式的程序：計(jì)算輸入關(guān)系代數(shù)表達(dá)式的程序(1)使用規(guī)律使用規(guī)律1，把每個(gè)選擇操作，把每個(gè)選擇操作 變換為變換為)(1encandandc)(21enccc使得選使得選擇操作擇操作可以靈可以靈活方便活方便地言查地言查詢樹下詢樹下移移數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11

16、章 查詢優(yōu)化技術(shù)(2)使用規(guī)律使用規(guī)律2,4,8和和10，把查詢樹上的每，把查詢樹上的每個(gè)選擇操作移動(dòng)到盡可能靠近葉子節(jié)點(diǎn)個(gè)選擇操作移動(dòng)到盡可能靠近葉子節(jié)點(diǎn)(3)使用規(guī)律使用規(guī)律3,4,9和和11，把查詢樹上的每，把查詢樹上的每個(gè)投影操作移動(dòng)到盡可能靠近葉子節(jié)點(diǎn)個(gè)投影操作移動(dòng)到盡可能靠近葉子節(jié)點(diǎn)數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)(4)使用規(guī)律使用規(guī)律1,3和和4，把串接的多個(gè)選擇，把串接的多個(gè)選擇或多個(gè)投影操作組合為但個(gè)選擇或投影或多個(gè)投影操作組合為但個(gè)選擇或投影操作操作(5)使用規(guī)律使用規(guī)律7重新安排葉節(jié)點(diǎn)，使具有最重新安排葉節(jié)點(diǎn)，使具有最小選擇操作的葉子節(jié)點(diǎn)最先執(zhí)行。小選擇

17、操作的葉子節(jié)點(diǎn)最先執(zhí)行。數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)(6)組合笛卡爾積和相繼的選擇操作形成組合笛卡爾積和相繼的選擇操作形成連接操作連接操作(7)把最后的查詢樹劃分為多個(gè)子樹，使把最后的查詢樹劃分為多個(gè)子樹，使每個(gè)子樹上的操作可以由單個(gè)存取程序每個(gè)子樹上的操作可以由單個(gè)存取程序一次完成。一次完成。數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v (8)產(chǎn)生一個(gè)計(jì)算最后查詢樹的程序，每一產(chǎn)生一個(gè)計(jì)算最后查詢樹的程序，每一步計(jì)算一個(gè)子樹步計(jì)算一個(gè)子樹數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)例例v 考慮一個(gè)具有如下關(guān)系的圖書館數(shù)據(jù)庫(kù)考慮一個(gè)具有如下關(guān)系的圖書館數(shù)據(jù)庫(kù)

18、 書目：書目：boo(ti, au, pn, nc) 借閱者：借閱者：bor(na, ad, ci, cn) 出版社：出版社：pub(pn, pa, pc) 借閱登記：借閱登記：loa(cn, nc, da)v 設(shè)有一個(gè)由已借出圖書信息構(gòu)成的視圖設(shè)有一個(gè)由已借出圖書信息構(gòu)成的視圖lbi, create view lbi as select ti, au, boo.pn, boo.nc, na, ad, ci, bor.cn, da from boo, bor, loa where boo.nc=loa.nc and bor.cn=loa.cn;數(shù)據(jù)庫(kù)原理與程序設(shè)計(jì)（孫杰）第11章 查詢優(yōu)化技術(shù)v 了解了解1994年年2月月1日前借出的所有書籍的名字。日前借出的所有書籍的名