1、第八章 關(guān)系數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化學(xué)習(xí)內(nèi)容容8.1查詢(xún)處理理概述8.2基本運(yùn)算算實(shí)現(xiàn)舉舉例8.3查詢(xún)優(yōu)化化的選擇擇執(zhí)行8.4sql語(yǔ)句優(yōu)化化參考：B3第十二章章學(xué)習(xí)目標(biāo)標(biāo)了解查詢(xún)?cè)兲幚淼牡倪^(guò)程了解查詢(xún)?cè)儍?yōu)化的的步驟掌握關(guān)系系代數(shù)等等價(jià)變換換規(guī)則了解啟發(fā)發(fā)式優(yōu)化化的方法法8.1查詢(xún)處理理概述8.1.1查詢(xún)處理理的定義義8.1.2查詢(xún)處理理的執(zhí)行行步驟8.1.3相關(guān)基本本概念8.1.1查詢(xún)處理理的定義義1.定定義從數(shù)據(jù)庫(kù)庫(kù)中提取取數(shù)據(jù)的的一系列列活動(dòng)2.包包括的主主要內(nèi)容容表達(dá)式轉(zhuǎn)換執(zhí)行3.輸入、輸輸出8.1.2查詢(xún)處理理的執(zhí)行行步驟語(yǔ)法分析析與翻譯譯優(yōu)化執(zhí)行語(yǔ)法分析與翻譯關(guān)系代數(shù)表達(dá)式執(zhí)行計(jì)劃優(yōu)化器查詢(xún)

2、語(yǔ)句執(zhí)行引擎查詢(xún)結(jié)果有關(guān)數(shù)據(jù)的統(tǒng)計(jì)值數(shù)據(jù)8.1.3相關(guān)基本本概念查詢(xún)代價(jià)價(jià)查詢(xún)處理理對(duì)各種種資源的的使用情情況磁盤(pán)存取取 （簡(jiǎn)簡(jiǎn)化為磁磁盤(pán)塊傳傳送數(shù)）CPU時(shí)間通信開(kāi)銷(xiāo)銷(xiāo)內(nèi)存開(kāi)銷(xiāo)銷(xiāo)COSTCPU(PLAN)COSTI/O(PLAN)PLAN19.2 CPU seconds103 readsPLAN21.7CPU seconds890 reads8.1.3相關(guān)基本本概念(續(xù))部分用于于估計(jì)代代價(jià)的目目錄信息息有關(guān)關(guān)系系的統(tǒng)計(jì)計(jì)信息nr：關(guān)系R中的元組組數(shù)目br：含有關(guān)系系R的元組的的塊數(shù)目目sr：關(guān)系R中一個(gè)元元組的大大小fr：關(guān)系R的塊因子子，即一一個(gè)塊中中能存放放的關(guān)系系R的元組數(shù)數(shù)若假定關(guān)

3、關(guān)系R的元組物物理上存存于同一一文件中中，則：br=nr/ fr一個(gè)重要要的影響響因素：主存中中緩沖區(qū)區(qū)的大小小M最好的情情形最壞的情情形8.1.3相關(guān)基本本概念(續(xù))查詢(xún)優(yōu)化化為關(guān)系代代數(shù)表達(dá)達(dá)式的計(jì)計(jì)算選擇擇最有效效的查詢(xún)?cè)冇?jì)劃的的過(guò)程。查詢(xún)執(zhí)行行計(jì)劃用于計(jì)算算一個(gè)查查詢(xún)的原原語(yǔ)序列列。執(zhí)行原語(yǔ)語(yǔ)加了“如如何執(zhí)行行”注釋釋的關(guān)系系代數(shù)運(yùn)運(yùn)算。查詢(xún)優(yōu)化化的過(guò)程程代數(shù)優(yōu)化化物理優(yōu)化化詳細(xì)策略略的選擇擇優(yōu)化器8.1.4查詢(xún)優(yōu)化化概述例：求選選修了2號(hào)課程程的學(xué)生生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno

4、=2;1 查詢(xún)?cè)儍?yōu)化的的必要性性（續(xù)）假設(shè)1：外存：Student:1000條,SC:10000條,選選修2號(hào)號(hào)課程:50條條一個(gè)硬盤(pán)盤(pán)塊放10個(gè)student或者100個(gè)SC假設(shè)2：一次I/O交換元組組:10個(gè)Student,或100個(gè)SC,內(nèi)存中一一次可以以存放:5塊Student元組（即即50個(gè)個(gè)Student）,1塊SC元組（即即100個(gè)SC）和若干塊塊連接結(jié)結(jié)果元組組假設(shè)3：讀寫(xiě)速速度：20塊/秒假設(shè)4：連接方方法：基于數(shù)據(jù)據(jù)塊的嵌套循循環(huán)法8.1.4查詢(xún)優(yōu)化化概述1 查詢(xún)?cè)儍?yōu)化的的必要性性(續(xù))8.1.4查詢(xún)優(yōu)化化概述1 查詢(xún)?cè)儍?yōu)化的的必要性性(續(xù))幾種不同同的實(shí)現(xiàn)現(xiàn)方法：1）Q1

5、Sname(Student.Sno=SC.SnoSC.Cno=2(StudentSC)2）2name(SC.Cno=2(StudentSC)3）3Sname(StudentSC.Cno=2(SC)1Q1Sname(Student.Sno=SC.SnoSC.Cno=2(StudentSC) StudentSC讀取總塊塊數(shù)=讀讀Student表塊數(shù)+讀讀SC表遍數(shù)*每遍塊塊數(shù)(讀SC表遍數(shù)=Student表的總元元組數(shù)/在內(nèi)存存中的元元組數(shù))=1000/10+(1000/(105) (10000/100)=100+20100=2100讀數(shù)據(jù)時(shí)時(shí)間=2100/20=105秒秒1 查詢(xún)?cè)儍?yōu)化的的必要性

6、性(續(xù))8.1.4查詢(xún)優(yōu)化化概述中間結(jié)果果大小=1000*10000 =107(1千萬(wàn)萬(wàn)條元組組)寫(xiě)中間結(jié)結(jié)果時(shí)間間= 10000000/10/20 =50000秒秒（設(shè)每塊能能裝10個(gè)中間間結(jié)果元元組）讀數(shù)據(jù)時(shí)時(shí)間= 50000秒總時(shí)間=1055000050000秒= 100105秒= 27.8小小時(shí)8.1.4查詢(xún)優(yōu)化化概述1 查詢(xún)?cè)儍?yōu)化的的必要性性(續(xù))2.2name(SC.Cno=2(StudentSC)讀取總塊塊數(shù)=2100塊（Q1的結(jié)果）讀數(shù)據(jù)時(shí)時(shí)間=2100/20=105秒秒因?yàn)橹挥杏蠸C只有10000條元組組，故等等值連接接的結(jié)果果,即:中間結(jié)果果大小=10000（減減少1000

7、倍倍）寫(xiě)中間結(jié)結(jié)果時(shí)間間=10000/10/20=50秒秒讀數(shù)據(jù)時(shí)時(shí)間=50秒秒總時(shí)間1055050秒205秒秒=3.4分（減少了了中間結(jié)結(jié)果）8.1.4查詢(xún)優(yōu)化化概述1 查詢(xún)?cè)儍?yōu)化的的必要性性(續(xù))3.3Sname(StudentSC.Cno=2(SC)讀SC表總塊數(shù)數(shù)=10000/100=100塊讀數(shù)據(jù)時(shí)時(shí)間=100/20=5秒秒中間結(jié)果果大小=50條條不不必寫(xiě)入入外存讀Student表總塊數(shù)數(shù)=1000/10=100塊讀數(shù)據(jù)時(shí)時(shí)間=100/20=5秒秒總時(shí)間55秒10秒（減少少中間結(jié)結(jié)果,且且全部在在內(nèi)存）1 查詢(xún)?cè)儍?yōu)化的的必要性性(續(xù))8.1.4查詢(xún)優(yōu)化化概述8.4name(Stude

8、ntSC.Cno=2(SC)假設(shè)SC表在Cno上有索引引，Student表在Sno上有索引引讀SC表索引=（發(fā)現(xiàn)現(xiàn)2號(hào)課課程只有有50條條元組）讀SC表總塊數(shù)數(shù)=50/1001塊讀數(shù)據(jù)時(shí)時(shí)間:1/20=0.5中間結(jié)果果大小=50條條不不必寫(xiě)入入外存1 查詢(xún)?cè)儍?yōu)化的的必要性性(續(xù))8.1.4查詢(xún)優(yōu)化化概述讀Student表索引=(根據(jù)據(jù)索引發(fā)發(fā)現(xiàn)只有有50個(gè)個(gè)學(xué)生)讀Student表總塊數(shù)數(shù)=50/10=5塊讀數(shù)據(jù)時(shí)時(shí)間：5/20=0.5秒秒 總時(shí)間12秒（不不必遍歷歷所有的的元組記記錄）1 查詢(xún)?cè)儍?yōu)化的的必要性性(續(xù))8.1.4查詢(xún)優(yōu)化化概述用戶(hù)不必必考慮如如何最好好地表達(dá)達(dá)查詢(xún)以以獲得較較好

9、的效效率。關(guān)系數(shù)據(jù)據(jù)語(yǔ)言的的級(jí)別很高高，使DBMS可以從關(guān)關(guān)系表達(dá)達(dá)式中分分析查詢(xún)?cè)冋Z(yǔ)義。系統(tǒng)可以以比用戶(hù)戶(hù)程序的的優(yōu)化做得更好好。2 查詢(xún)?cè)儍?yōu)化的的可能性性8.1.4查詢(xún)優(yōu)化化概述StudentSC（做SCStudent）讀取總塊塊數(shù)=讀讀SC表塊數(shù)+讀讀Student表遍數(shù)*每遍塊塊數(shù)(讀Student表遍數(shù)=SC表的總元元組數(shù)/在內(nèi)存存中的元元組數(shù))=10000/100+(10000/(1001)(1000/10)=100+100100=10100讀數(shù)據(jù)時(shí)時(shí)間=10100/20=505秒2 查詢(xún)?cè)儍?yōu)化的的可能性性(續(xù))8.1.4查詢(xún)優(yōu)化化概述8.1.4查詢(xún)優(yōu)化化概述2 查詢(xún)?cè)儍?yōu)化的的可能

10、性性(續(xù))優(yōu)化器可可以從數(shù)數(shù)據(jù)字典典中獲取取許多信信息(包包括統(tǒng)計(jì)計(jì)信息和和索引信信息)，而用戶(hù)戶(hù)程序則則難以獲獲得這些些信息。如果數(shù)據(jù)據(jù)庫(kù)的物物理統(tǒng)計(jì)計(jì)信息改改變了，系統(tǒng)可可以自動(dòng)動(dòng)對(duì)查詢(xún)?cè)冎匦聝?yōu)化化以選擇相相適應(yīng)的的執(zhí)行計(jì)計(jì)劃。在在非關(guān)關(guān)系系統(tǒng)統(tǒng)中必須須重寫(xiě)程程序，而而重寫(xiě)程程序在實(shí)實(shí)際應(yīng)用用中往往往是不太太可能的的。優(yōu)化器可可以考慮慮數(shù)百種種不同的的執(zhí)行計(jì)計(jì)劃，而而程序員員一般只只能考慮慮有限的的幾種可可能性。優(yōu)化器中中包括了了很多復(fù)復(fù)雜的優(yōu)優(yōu)化技術(shù)術(shù)查詢(xún)優(yōu)化化的總目目標(biāo)選擇有效效策略，求得給給定關(guān)系系表達(dá)式式的值8.1.4查詢(xún)優(yōu)化化概述3 查詢(xún)?cè)儍?yōu)化的的目標(biāo)代價(jià)模型型：集中式數(shù)數(shù)據(jù)庫(kù)單

11、用戶(hù)系系統(tǒng)總代價(jià)=I/O代價(jià)+CPU代價(jià)多用戶(hù)系系統(tǒng)總代價(jià)=I/O代價(jià)+CPU代價(jià)+ 內(nèi)存存代價(jià)分布式數(shù)數(shù)據(jù)庫(kù)總代價(jià)=I/O代價(jià)+CPU代價(jià)+ 內(nèi)存存代價(jià) +通通信代代價(jià)8.1.4查詢(xún)優(yōu)化化概述3 查詢(xún)?cè)儍?yōu)化的的目標(biāo)（續(xù)）8.2基本運(yùn)算算實(shí)現(xiàn)舉舉例1.運(yùn)運(yùn)算特點(diǎn)點(diǎn)每一個(gè)基基本的代代數(shù)運(yùn)算算都有多多種不同同的實(shí)現(xiàn)現(xiàn)算法適用于不不同的情情況執(zhí)行代價(jià)價(jià)不同2.選選擇運(yùn)算算的實(shí)現(xiàn)現(xiàn)3.連連接運(yùn)算算的實(shí)現(xiàn)現(xiàn)8.2基本運(yùn)算算實(shí)現(xiàn)舉舉例(續(xù)續(xù))2.選選擇運(yùn)算算的實(shí)現(xiàn)現(xiàn)全表掃描描方法：依依次訪問(wèn)問(wèn)表的每每一個(gè)塊塊，對(duì)于于每一個(gè)個(gè)元組，測(cè)試它它是否滿(mǎn)滿(mǎn)足選擇擇條件。代價(jià)：E =br索引掃描描條件：表表在選擇擇條

12、件的的屬性上上建有索索引。方法：訪訪問(wèn)索引引，根據(jù)據(jù)索引項(xiàng)項(xiàng)的指示示去訪問(wèn)問(wèn)數(shù)據(jù)元元組。代價(jià)：8.2基本運(yùn)算算實(shí)現(xiàn)舉舉例(續(xù)續(xù))3.連連接運(yùn)算算的實(shí)現(xiàn)現(xiàn)嵌套循環(huán)環(huán)連接塊嵌套循循環(huán)連接接索引嵌套套循環(huán)連連接排序-歸歸并連接接散列連接接8.2基本運(yùn)算算實(shí)現(xiàn)舉舉例(續(xù)續(xù))3.連連接運(yùn)算算的實(shí)現(xiàn)現(xiàn)嵌套循環(huán)環(huán)連接foreach元組trinR dobeginforeach元組tsinS dobegin測(cè)試元組組對(duì)(tr,ts)是否滿(mǎn)足足連接條條件如果滿(mǎn)足足，把tr ts加到結(jié)果果中endend8.2基本運(yùn)算算實(shí)現(xiàn)舉舉例(續(xù)續(xù))3.連連接運(yùn)算算的實(shí)現(xiàn)現(xiàn)嵌套循環(huán)環(huán)連接優(yōu)點(diǎn)：對(duì)對(duì)參加運(yùn)運(yùn)算的關(guān)關(guān)系沒(méi)有有要求，適

13、合于于任何連連接條件件。代價(jià)：最壞情況況（緩沖沖區(qū)只能能夠容納納每個(gè)關(guān)關(guān)系的一一個(gè)塊）最好情況況（內(nèi)層層關(guān)系S能完全放放在內(nèi)存存中）bs+ br8.2基本運(yùn)算算實(shí)現(xiàn)舉舉例(續(xù)續(xù))3.連連接運(yùn)算算的實(shí)現(xiàn)現(xiàn)排序-歸歸并連接接類(lèi)似于外外排序的的歸并算算法的思思路，進(jìn)進(jìn)行連接接運(yùn)算。前提：兩兩個(gè)關(guān)系系的元組組已按連連接屬性性排好序序。適用于自自然連接接和等值值連接。排序-歸歸并連接接a3b1d8d13f7m5q6aAaGcLdNmB r sa1a2a1a3 在歸并連接中使用的已排序關(guān)系rs8.3查詢(xún)優(yōu)化化的選擇擇執(zhí)行8.3.1表達(dá)式等等價(jià)S#(C#= 001C#= 002(SC)S#(C#= 001(

14、SC)S#(C#= 002(SC)8.3.2兩類(lèi)主要要的優(yōu)化化算法8.3.3啟發(fā)式優(yōu)優(yōu)化8.3.4查詢(xún)優(yōu)化化的一般般步驟8.3.1表達(dá)式等等價(jià)1.語(yǔ)語(yǔ)法樹(shù)2.表表達(dá)式等等價(jià)的定定義3.表表達(dá)式的的等價(jià)規(guī)規(guī)則8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))語(yǔ)法樹(shù)（查詢(xún)樹(shù)樹(shù)）葉子節(jié)點(diǎn)點(diǎn)：關(guān)系系內(nèi)節(jié)點(diǎn)：關(guān)系代代數(shù)操作作執(zhí)行方式式：自底底向上 customer_namebalance |關(guān)系代數(shù)數(shù)表達(dá)式式的語(yǔ)法法樹(shù)：customer_name（balance |depositor)8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))3.常常用等價(jià)價(jià)變換規(guī)規(guī)則說(shuō)明：E、E1、E2等表示關(guān)關(guān)系代數(shù)數(shù)表達(dá)式式連接、笛笛卡爾積積交換律律連接、笛笛卡

15、爾積積的結(jié)合合律投影的串串接定律律選擇的串串接定律律選擇與投投影的交交換律選擇與笛笛卡爾積積的交換換律選擇與并并的交換換選擇與差差運(yùn)算的的交換投影與笛笛卡爾積積的交換換投影與并并的交換換關(guān)系代數(shù)數(shù)表達(dá)式式等價(jià)指用相同同的關(guān)系系代替兩兩個(gè)表達(dá)達(dá)式中相相應(yīng)的關(guān)關(guān)系所得得到的結(jié)結(jié)果是相相同的上面的優(yōu)優(yōu)化策略略大部分分都涉及及到代數(shù)數(shù)表達(dá)式式的變換換8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))設(shè)E1、E2等是關(guān)系系代數(shù)表表達(dá)式，F(xiàn)是條件表表達(dá)式 l.連接、笛笛卡爾積積交換律律E1E2 E2E1E1E2E2E1E1FE2E2FE18.3.1表達(dá)式等等價(jià)(續(xù)續(xù))2.連連接、笛笛卡爾積積的結(jié)合合律(E1E2)E3 E1

16、(E2E3)(E1E2)E3 E1(E2E3)(E1E2)E3 E1(E2E3)FFFF8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))3. 投影影的串接接定律A1,A2,An(B1,B2,Bm(E)A1,A2,An(E)假設(shè)：1)E是關(guān)系代代數(shù)表達(dá)達(dá)式2)Ai(i=1，2，n),Bj(j=l，2，m)是屬性名名3)A1, A2, , An構(gòu)成Bl，B2，Bm的子集8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))8.選擇的串串接定律律F1（F2（E）F1F2(E)選擇的串串接律說(shuō)說(shuō)明選選擇擇條件可可以合并并這樣一次次就可檢檢查全部部條件。8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))5.選選擇與投投影的交交換律(1)假假設(shè):選選擇條條件F只涉及

17、屬屬性A1，AnF(A1,A2,An(E)A1,A2,An(F(E)(2)假設(shè):F中有不屬屬于A1,An的屬性B1,BmA1,A2,An(F(E)A1,A2,An(F(A1,A2,An,B1,B2,Bm(E)8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))6.選選擇與笛笛卡爾積積的交換換律(1)假設(shè)：F中涉及的的屬性都都是E1中的屬性性F(E1E2)F(E1)E2(2)假設(shè)：F=F1F2，并且F1只涉及E1中的屬性性，F(xiàn)2只涉及E2中的屬性性則由上面面的等價(jià)價(jià)變換規(guī)規(guī)則1，4，6可推出出：F(E1E2) F1(E1)F2(E2)8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))(3)假假設(shè)：F=F1F2，F(xiàn)1只涉及E1中的屬性性，

18、F2涉及E1和E2兩者的屬屬性F(E1E2)F2(F1(E1)E2)它使部分分選擇在在笛卡爾爾積前先先做8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))7.選選擇與并并的交換換假設(shè)：E=E1E2，E1，E2有相同的的屬性名名F(E1E2)F(E1)F(E2)8.選擇與差差運(yùn)算的的交換假設(shè)：E1與E2有相同的的屬性名名F(E1-E2)F(E1) -F(E2)8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))9.投投影與笛笛卡爾積積的交換換假設(shè)：E1和E2是兩個(gè)關(guān)關(guān)系表達(dá)達(dá)式，A1，An是E1的屬性，B1，Bm是E2的屬性A1,A2,An,B1,B2,Bm（E1E2)A1,A2,An（E1)B1,B2,Bm(E2)8.3.1表達(dá)式等等

19、價(jià)(續(xù)續(xù))l0.投影與并并的交換換假設(shè)：E1和E2有相同的的屬性名名A1,A2,An(E1E2)A1,A2,An(E1)A1,A2,An(E2)8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))l0.投影與并并的交換換假設(shè)：E1和E2有相同的的屬性名名A1,A2,An(E1E2)A1,A2,An(E1)A1,A2,An(E2)8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))8.3.1表達(dá)式等等價(jià)(續(xù)續(xù))3.常常用等價(jià)價(jià)變換規(guī)規(guī)則說(shuō)明：規(guī)則只說(shuō)說(shuō)明兩個(gè)個(gè)表達(dá)式式等價(jià)，并不說(shuō)說(shuō)明哪一一個(gè)更好好。連接的次次序很重重要，好好的連接接次序序序列產(chǎn)生生小的中中間結(jié)果果。8.3.2兩類(lèi)主要要的優(yōu)化化算法1.兩兩類(lèi)主要要的優(yōu)化化算法基于代價(jià)價(jià)的方

20、法法通過(guò)使用用等價(jià)規(guī)規(guī)則為給給定的查查詢(xún)語(yǔ)句句產(chǎn)生一一系列查查詢(xún)執(zhí)行行計(jì)劃，并選擇擇其中代代價(jià)最小小或接近近最小的的啟發(fā)式方方法運(yùn)用啟發(fā)發(fā)式規(guī)則則，對(duì)關(guān)關(guān)系代數(shù)數(shù)表達(dá)式式進(jìn)行等等價(jià)變換換8.3.3啟發(fā)式優(yōu)優(yōu)化1.啟啟發(fā)式優(yōu)優(yōu)化的常常用規(guī)則則選擇運(yùn)算算應(yīng)盡可可能先做做投影運(yùn)算算應(yīng)盡可可能先做做在執(zhí)行連連接前對(duì)對(duì)關(guān)系適適當(dāng)?shù)仡A(yù)預(yù)處理把投影運(yùn)運(yùn)算和選選擇運(yùn)算算同時(shí)進(jìn)進(jìn)行把投影同同其前或或其后的的雙目運(yùn)運(yùn)算結(jié)合合起來(lái)找出公共共子表達(dá)達(dá)式8.3.4關(guān)系代數(shù)數(shù)表達(dá)式式的優(yōu)化化算法算法：關(guān)關(guān)系表達(dá)達(dá)式的優(yōu)優(yōu)化輸入：一一個(gè)關(guān)系系表達(dá)式式的語(yǔ)法法樹(shù)。輸出：計(jì)計(jì)算該表表達(dá)式的的程序。方法：（1）分分解選擇擇運(yùn)算利

21、用規(guī)則則4把形形如F1F2 Fn(E)變換為F1(F2(Fn(E)8.3.4關(guān)系代數(shù)數(shù)表達(dá)式式的優(yōu)化化算法（2）通通過(guò)交換換選擇運(yùn)運(yùn)算，將將其盡可可能移到到葉端對(duì)每一個(gè)個(gè)選擇，利用規(guī)規(guī)則48盡可可能把它它移到樹(shù)樹(shù)的葉端端。（3）通通過(guò)交換換投影運(yùn)運(yùn)算，將將其盡可可能移到到葉端對(duì)每一個(gè)個(gè)投影利利用規(guī)則則3，9，l0，5中的一般般形式盡盡可能把把它移向向樹(shù)的葉葉端。8.3.4關(guān)系代數(shù)數(shù)表達(dá)式式的優(yōu)化化算法（4）合合并串接接的選擇擇和投影影，以便便能同時(shí)時(shí)執(zhí)行或或在一次次掃描中中完成利用規(guī)則則35把選擇擇和投影影的串接接合并成成單個(gè)選選擇、單單個(gè)投影影或一個(gè)個(gè)選擇后后跟一個(gè)個(gè)投影。使多個(gè)選選擇或投投

22、影能同同時(shí)執(zhí)行行，或在在一次掃掃描中全全部完成成盡管這種種變換似似乎違背背“投影影盡可能能早做”的原則則，但這這樣做效效率更高高。8.3.4關(guān)系代數(shù)數(shù)表達(dá)式式的優(yōu)化化算法（5）對(duì)對(duì)內(nèi)結(jié)點(diǎn)點(diǎn)分組把上述得得到的語(yǔ)語(yǔ)法樹(shù)的的內(nèi)節(jié)點(diǎn)點(diǎn)分組。每一雙目目運(yùn)算(，-)和它所所有的直直接祖先先為一組組(這些些直接祖祖先是，運(yùn)算)。如果其后后代直到到葉子全全是單目目運(yùn)算，則也將將它們并并入該組組，但當(dāng)當(dāng)雙目運(yùn)運(yùn)算是笛笛卡爾積積()，而且且其后的的選擇不不能與它它結(jié)合為為等值連連接時(shí)除除外。把把這些單單目運(yùn)算算單獨(dú)分分為一組組。8.3.4關(guān)系代數(shù)數(shù)表達(dá)式式的優(yōu)化化算法（6）生生成程序序生成一個(gè)個(gè)程序，每組結(jié)結(jié)點(diǎn)的

23、計(jì)計(jì)算是程程序中的的一步。各步的順順序是任任意的，只要保保證任何何一組的的計(jì)算不不會(huì)在它它的后代代組之前前計(jì)算。例子考慮應(yīng)用用：Books(title,author,pname,lc-no)Publishers(pname,paddr,pcity)Borrowers(name,addr,city,card-no)Loans(card-no,lc-no,date)查詢(xún)：列列出1992年年1月1日以前前借出的的所有書(shū)書(shū)名，title(date960101(Xloans)例子例子（1）選選擇運(yùn)算算有三個(gè)選選擇運(yùn)算算，分解解（2）使使用定律律48把三個(gè)個(gè)選擇運(yùn)運(yùn)算盡量量移向樹(shù)樹(shù)的葉端端（3）由由于選擇

24、擇和投影影的可交交換，把把條件date960101移到最下下端title(date960101(loans)borrowers)books)例子例子（4）分分組查詢(xún)?cè)儤?shù)8.3.4查詢(xún)優(yōu)化化的一般般步驟1.把把查詢(xún)轉(zhuǎn)轉(zhuǎn)換成某某種內(nèi)部部表示2.把語(yǔ)語(yǔ)法樹(shù)轉(zhuǎn)轉(zhuǎn)換成標(biāo)標(biāo)淮(優(yōu)優(yōu)化)形形式3.選擇擇低層的的存取路路徑8.生成查詢(xún)?cè)冇?jì)劃，選擇代代價(jià)最小小的舉例求選修了了2號(hào)課程的的學(xué)生姓姓名。8.4sql語(yǔ)句優(yōu)優(yōu)化目標(biāo)有利于DBMS選擇代價(jià)價(jià)最小的的查詢(xún)執(zhí)執(zhí)行計(jì)劃劃依據(jù)DBMS優(yōu)化器支支持的優(yōu)優(yōu)化策略略 8.4sql語(yǔ)句優(yōu)優(yōu)化Sql語(yǔ)句一般般優(yōu)化策策略充分利用索引引盡量避免免表搜索索減少不必必要的運(yùn)運(yùn)算8

25、.4sql語(yǔ)句優(yōu)優(yōu)化1.搜搜索參數(shù)數(shù)化帶有=、=、=等操作作符的條條件查詢(xún)?cè)兙涂梢砸灾苯邮故褂盟饕?。如：id= T0001,salary30000,a=1 andc =7。下列則不不是搜索索參數(shù)：salary=commission,dept!=10,salary *12=30000,age218.4sql語(yǔ)句優(yōu)優(yōu)化在查詢(xún)中中可以提提供一些些冗余的的搜索參參數(shù),使使優(yōu)化器器有更多多的選擇擇余地。如title和titleauthor兩張表是是一對(duì)多多的關(guān)系系,同樣樣的查詢(xún)?cè)儣l件我我們有以以下三種種表現(xiàn)方方法:SELECTtitle_id, title FROMtitles,titleauthor

26、WHEREtitle.title_id= titleauthor.title_idANDtitleauthor.title_id=T81002SELECT title_id,titleFROM titles,titleauthorWHEREtitle.title_id= titleauthor.title_idANDtitle.title_id=T81002SELECT title_id,titleFROM titles,titleauthorWHEREtitle.title_id= titleauthor.title_idANDtitle.title_id=T81002ANDtitleaut

27、hor.title_id=T81002三種方法法一種比比一種要要好,因因?yàn)楹笳哒邽閮?yōu)化化器提供供了更多多的選擇擇機(jī)會(huì)。8.4sql語(yǔ)句優(yōu)優(yōu)化2.避免使用用不兼容容的數(shù)據(jù)據(jù)類(lèi)型SELECTnameFROM employee WHERE salary 600003.ISNULL與ISNOTNULL在where子句中使使用isnull或isnotnull的語(yǔ)句優(yōu)優(yōu)化器是是不允許許使用索索引的8.在海量查查詢(xún)時(shí)盡盡量少用用格式轉(zhuǎn)轉(zhuǎn)換wherecast(salaryaschar(2)= 905.避免不不同數(shù)據(jù)據(jù)類(lèi)型間間的連接接運(yùn)算 8.4sql語(yǔ)句優(yōu)優(yōu)化6.避免免where子句中的的“=”左邊進(jìn)進(jìn)行函數(shù)

28、數(shù)、算術(shù)術(shù)運(yùn)算或或其他表表達(dá)式運(yùn)運(yùn)算，否否則系統(tǒng)統(tǒng)將可能能無(wú)法正正確使用用索引。whereLeft(xsbh,2)=01wherexsbh =like01%SQL優(yōu)優(yōu)化實(shí)例例oracle例1：RLWT(STCD,TM,LV)水位表表查詢(xún)當(dāng)前前時(shí)間前前一個(gè)小小時(shí)的時(shí)時(shí)刻的水水位記錄錄SELECT*FROMRLWTWHERETM+1 =SYSDATE;SELECT*FROMRLWTWHERETM=SYSDATE1;SELECT*FROMRLWTWHERETM= TO_DATE(2006-04-267:00:00,YY-MM-DDHH24:MI:SS)SELECTSTCD,TM,LVFROMRLWTWHERETM= TO_DATE(2006-04-267:00:00,YY-MM-DDHH24:MI:SS)例2：查查選修了了01號(hào)課程程的學(xué)生生姓名。SELECTSNAMEFROMSTUDENTWHERE01IN(SELECT CNOFROM SCWHERESNO=STUDENT.SNO);SELECTSNAMEFROMSTUDENT,SCWHERESC.SNO=STUDENT.SNOANDSC.CNO=01例3：