數(shù)據(jù)庫課件：第4章 數(shù)據(jù)庫查詢優(yōu)化

數(shù)據(jù)庫優(yōu)化查詢查詢優(yōu)化2代數(shù)優(yōu)化3物理優(yōu)化4優(yōu)化步驟51查詢處理1查詢處理幾種數(shù)據(jù)庫的體系結(jié)構(gòu)查詢處理步驟查詢操作算法示例WebFormsApplicationFrontEndsSQLInterfacesUnsophisticatedusers(customers,travelagents,etc.)Sophisticatedusers,applicationprogrammers,DBadministratorsSQLCOMMANDSPlanExecutorOperatorEvaluatorParserOptimizerQueryEvaluationEngineTransactionManagerLockManagerConcurrencyControlFilesandAccessMethodsBufferManagerDiskSpaceManagerRecoveryManagerIndexFilesDataFilesSystemCatalogDatabase數(shù)據(jù)庫通用體系結(jié)構(gòu)SQLSever體系結(jié)構(gòu)MySQL體系結(jié)構(gòu)1查詢處理幾種數(shù)據(jù)庫的體系結(jié)構(gòu)查詢處理步驟查詢操作算法示例查詢處理階段及主要內(nèi)容查詢分析查詢檢查查詢優(yōu)化

查詢執(zhí)行

查詢處理步驟關(guān)系代數(shù)表達(dá)式查詢語句執(zhí)行計(jì)劃執(zhí)行引擎查詢輸出數(shù)據(jù)有關(guān)數(shù)據(jù)統(tǒng)計(jì)信息語法分析與翻譯優(yōu)化器數(shù)據(jù)1）

查詢分析對(duì)查詢語句進(jìn)行掃描、詞法分析和語法分析從查詢語句中識(shí)別出語言符號(hào)進(jìn)行語法檢查和語法分析SELECTe.ename,e.sal,s.gradeFROM empe,salgradesWHERE e.salBETWEENs.losalANDs.hisal2）查詢檢查根據(jù)數(shù)據(jù)字典對(duì)合法的查詢語句進(jìn)行語義檢查根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對(duì)用戶的存取權(quán)限進(jìn)行檢查檢查通過后把SQL查詢語句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式RDBMS一般都用查詢樹(語法分析樹)來表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式把數(shù)據(jù)庫對(duì)象的外部名稱轉(zhuǎn)換為內(nèi)部表示3）查詢優(yōu)化查詢優(yōu)化：選擇一個(gè)高效執(zhí)行的查詢處理策略查詢優(yōu)化分類：代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化物理優(yōu)化：指存取路徑和底層操作算法的選擇查詢優(yōu)化方法選擇的依據(jù)：基于規(guī)則(rulebased)基于代價(jià)(costbased)基于語義(semanticbased)4）查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計(jì)劃代碼生成器(codegenerator)生成執(zhí)行查詢計(jì)劃的代碼1查詢處理幾種數(shù)據(jù)庫的體系結(jié)構(gòu)查詢處理步驟查詢操作算法示例

一、選擇操作的實(shí)現(xiàn)例：Select*fromstudentwhere<條件表達(dá)式>；考慮<條件表達(dá)式>的幾種情況：

C1：無條件；

C2：Sno＝'200433103046'；

C3：Sage>20；

C4：Sdept＝'CS'ANDSage>20；

SnoSNameSSexSageSdept

200333103213蔡立雄男19CS200333103222陳宇鋒男21IS200333103231崔繼明男20ES200333103240鄧小忻女22IS200333103277郭冠鴻男19CS200333103286何英煒男23ES200433103019張彬彬男22IS200433103028張勝超男18CS200433103046張佳祺女24CS……Innodb邏輯存儲(chǔ)結(jié)構(gòu)InnoDBtablespacesfileheaderpageheaderInfimum&supermumuserrecordsfreespacepagedirectoryfiletrailer16KB16KBNoneleafsegmentleafsegmentB-Treepage存儲(chǔ)了整個(gè)表行數(shù)據(jù)，有序數(shù)據(jù)無順序插入表中，UID是主鍵PK選擇操作的實(shí)現(xiàn)方法簡(jiǎn)單的全表掃描方法對(duì)查詢的基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出

適合小表，不適合大表SnoSNameSSexSageSdept

200333103213蔡立雄男19CS200333103222陳宇鋒男21IS200333103231崔繼明男20ES200333103240鄧小忻女22CS200333103277郭冠鴻男19CS200333103286何英煒男23ES200433103019張彬彬男22IS200433103028張勝超男18CS200433103046張佳祺女24CS……選擇操作的實(shí)現(xiàn)索引(或散列)掃描方法適合選擇條件中的屬性上有索引(例如B+樹索引或Hash索引)通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組選擇操作的實(shí)現(xiàn)（續(xù)）［例-C2］以C2為例，Sno＝‘200433103046’，并且Sno上有索引(或Sno是散列碼)使用索引(或散列)得到Sno為‘200333103240’元組的指針通過元組指針在student表中檢索到該學(xué)生［例-C3］以C3為例，Sage>20，并且Sage上有B+樹索引使用B+樹索引找到Sage＝20的索引項(xiàng)，以此為入口點(diǎn)在B+樹的順序集上得到Sage>20的所有元組指針通過這些元組指針到student表中檢索到所有年齡大于20的學(xué)生。選擇操作的實(shí)現(xiàn)（續(xù)）［例-C4］以C4為例，Sdept＝‘CS’ANDSage>20，如果Sdept和Sage上都有索引：算法一：分別用上面兩種方法分別找到Sdept＝‘CS’的一組元組指針和Sage>20的另一組元組指針求這2組指針的交集到student表中檢索得到計(jì)算機(jī)系年齡大于20的學(xué)生算法二：找到Sdept＝‘CS’的一組元組指針通過這些元組指針到student表中檢索對(duì)得到的元組檢查另一些選擇條件(如Sage>20)是否滿足把滿足條件的元組作為結(jié)果輸出。二、連接操作的實(shí)現(xiàn)連接操作是查詢處理中最耗時(shí)的操作之一，本節(jié)只討論等值連接(或自然連接)最常用的實(shí)現(xiàn)算法。［例2］SELECT*FROMStudent，SC WHEREStudent.Sno=SC.Sno；連接操作的實(shí)現(xiàn)方法嵌套循環(huán)方法(nestedloop)排序-合并方法(sort-mergejoin)索引連接(indexjoin)方法HashJoin方法嵌套循環(huán)方法(nestedloop)對(duì)外層循環(huán)(Student)的每一個(gè)元組(s)，檢索內(nèi)層循環(huán)(SC)中的每一個(gè)元組(sc)檢查這兩個(gè)元組在連接屬性(sno)上是否相等如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止

排序-合并方法(sort-mergejoin）適合連接的諸表已經(jīng)排好序的情況如果連接的表沒有排好序，先對(duì)Student表和SC表按連接屬性Sno排序取Student表中第一個(gè)Sno，依次掃描SC表中具有相同Sno的元組排序-合并方法當(dāng)掃描到Sno不相同的第一個(gè)SC元組時(shí)，返回Student表掃描它的下一個(gè)元組，再掃描SC表中具有相同Sno的元組，把它們連接起來重復(fù)上述步驟直到Student表掃描完200215121200215122200215123200215124...200215121192200215121285200215121388200215122290200215122380...排序-合并連接方法示意圖排序-合并方法Student表和SC表都只要掃描一遍如果2個(gè)表原來無序，執(zhí)行時(shí)間要加上對(duì)兩個(gè)表的排序時(shí)間對(duì)于2個(gè)大表，先排序后使用sort-mergejoin方法執(zhí)行連接，總的時(shí)間一般仍會(huì)大大減少索引連接(indexjoin)方法在SC表上建立屬性Sno的索引，如果原來沒有該索引對(duì)Student中每一個(gè)元組，由Sno值通過SC的索引查找相應(yīng)的SC元組把這些SC元組和Student元組連接起來循環(huán)執(zhí)行a)b)，直到Student表中的元組處理完為止HashJoin方法把連接屬性作為hash碼，用同一個(gè)hash函數(shù)把R和S中的元組散列到同一個(gè)hash文件中步驟：劃分階段(partitioningphase)：對(duì)包含較少元組的表(比如R)進(jìn)行一遍處理把它的元組按hash函數(shù)分散到hash表的桶中試探階段(probingphase)：也稱為連接階段(joinphase)對(duì)另一個(gè)表(S)進(jìn)行一遍處理把S的元組散列到適當(dāng)?shù)膆ash桶中把元組與桶中所有來自R并與之相匹配的元組連接起來HashJoin方法上面hashjoin算法前提：假設(shè)兩個(gè)表中較小的表在第一階段后可以完全放入內(nèi)存的hash桶中以上的算法思想可以推廣到更加一般的多個(gè)表的連接算法上查詢優(yōu)化2代數(shù)優(yōu)化3物理優(yōu)化4優(yōu)化步驟51查詢處理查詢優(yōu)化的目的和意義查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素由于關(guān)系表達(dá)式的語義級(jí)別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義，提供了執(zhí)行查詢優(yōu)化的可能性由DBMS進(jìn)行查詢優(yōu)化的好處用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率系統(tǒng)可以比用戶程序的優(yōu)化做得更好優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)各種數(shù)據(jù)庫查詢優(yōu)化的執(zhí)行代價(jià)評(píng)估策略RDBMS通過某種代價(jià)模型計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案集中式數(shù)據(jù)庫執(zhí)行開銷：磁盤存取塊數(shù)(I/O代價(jià))處理機(jī)時(shí)間(CPU代價(jià))查詢的內(nèi)存開銷分布式數(shù)據(jù)庫總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)＋通信代價(jià)I/O代價(jià)是最主要的查詢優(yōu)化的必要性論證舉例例：求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2'查詢過程的假設(shè)條件假設(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)法執(zhí)行策略1Ｑ1＝ПSname(б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秒不同的執(zhí)行策略，考慮I/O時(shí)間中間結(jié)果大小=1000*10000=107(1千萬條元組)寫中間結(jié)果時(shí)間=10000000/10/20=50000秒

②б

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

③П

總時(shí)間=105＋50000＋50000秒=100105秒

=27.8小時(shí)執(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秒

③П：忽略不計(jì)總時(shí)間＝105＋50＋50秒＝205秒=3.4分鐘

執(zhí)行策略3Ｑ3＝П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秒

③П

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

①б

讀SC表索引=

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

中間結(jié)果大小=50條，不必寫入外存查詢優(yōu)化的必要性（續(xù)）②

讀Student表索引=

讀Student表總塊數(shù)=50/10=5塊 讀數(shù)據(jù)時(shí)間③П

總時(shí)間<0.4秒查詢優(yōu)化2代數(shù)優(yōu)化3物理優(yōu)化4優(yōu)化步驟51查詢處理查詢優(yōu)化的一般準(zhǔn)則選擇運(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ù)查詢優(yōu)化的一般準(zhǔn)則某些選擇運(yùn)算＋在其前面執(zhí)行的笛卡爾積

===>連接運(yùn)算例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC提取公共子表達(dá)式關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的上面的優(yōu)化策略大部分都涉及到代數(shù)表達(dá)式的變換常用的等價(jià)變換規(guī)則設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式連接、笛卡爾積交換律

E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1連接、笛卡爾積的結(jié)合律

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

F

F

F

F關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）投影的串接定律

πA1,A2,

,An(πB1,B2,,Bm(E))≡πA1,A2,,An(E)假設(shè)：E是關(guān)系代數(shù)表達(dá)式Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名{A1,A2,…,An}構(gòu)成{Bl，B2，…，Bm}的子集選擇的串接定律

бF1（бF2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件。

關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）選擇與投影的交換律(a)假設(shè):選擇條件F只涉及屬性A1，…，AnбF(πA1,A2,,An(E))≡πA1,A2,,An(бF(E))

(b)假設(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ù)）選擇與笛卡爾積的交換律(a)假設(shè)：F中涉及的屬性都是E1中的屬性

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

(b)假設(shè)：F=F1∧F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性 則由上面的等價(jià)變換規(guī)則1，4，6可推出：

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

關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）(c)假設(shè)：F=F1∧F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性

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

它使部分選擇在笛卡爾積前先做關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）選擇與并的交換 假設(shè)：E=E1∪E2，E1，E2有相同的屬性名

бF(E1∪E2)≡бF(E1)∪бF(E2)

選擇與差運(yùn)算的交換 假設(shè)：E1與E2有相同的屬性名

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

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

πA1,A2,…,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律3：合并或分解投影運(yùn)算4：合并或分解選擇運(yùn)算5-8：選擇運(yùn)算與其他運(yùn)算交換5，9，10：投影運(yùn)算與其他運(yùn)算交換關(guān)系代數(shù)表達(dá)式的優(yōu)化算法（1）分解選擇運(yùn)算利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為бF1

(бF2(…(бFn(E))…))（2）通過交換選擇運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)選擇，利用規(guī)則4～8盡可能把它移到樹的葉端。（3）通過交換投影運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)投影利用規(guī)則3，9，l0，5中的一般形式盡可能把它移向樹的葉端。關(guān)系代數(shù)表達(dá)式的優(yōu)化算法（4）合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成利用規(guī)則3～5把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。關(guān)系代數(shù)表達(dá)式的優(yōu)化算法（5）對(duì)內(nèi)結(jié)點(diǎn)分組把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是б，π運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積(×)，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。關(guān)系代數(shù)表達(dá)式的優(yōu)化算法（6）生成程序生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。各步的順序是任意的，只要保證任何一組的計(jì)算不會(huì)在它的后代組之前計(jì)算。查詢優(yōu)化2代數(shù)優(yōu)化3物理優(yōu)化4優(yōu)化步驟51查詢處理物理優(yōu)化代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑對(duì)于一個(gè)查詢語句有許多存取方案，它們的執(zhí)行效率不同，僅僅進(jìn)行代數(shù)優(yōu)化是不夠的物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計(jì)劃物理優(yōu)化的方法：基于啟發(fā)式規(guī)則的優(yōu)化基于代價(jià)估算的優(yōu)化兩者結(jié)合的優(yōu)化方法一、基于啟發(fā)式規(guī)則的優(yōu)化選擇操作的啟發(fā)式規(guī)則連接操作的啟發(fā)式規(guī)則選擇操作的啟發(fā)式規(guī)則對(duì)于小關(guān)系，使用全表順序掃描，即使選擇列上有索引 對(duì)于大關(guān)系，啟發(fā)式規(guī)則有：對(duì)于選擇條件是主碼＝值的查詢，查詢結(jié)果最多是一個(gè)元組，可以選擇主碼索引一般的RDBMS會(huì)自動(dòng)建立主碼索引對(duì)于選擇條件是非主屬性＝值的查詢，并且選擇列上有索引，要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描對(duì)于選擇條件是非等值查詢或者范圍查詢，并且選擇列上有索引，要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描基于啟發(fā)式規(guī)則優(yōu)化(續(xù))對(duì)于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引則可以用索引掃描方法否則使用全表順序掃描。對(duì)于用OR連接的析取選擇條件，一般使用全表順序掃描連接操作的啟發(fā)式規(guī)則如果2個(gè)表都已經(jīng)按照連接屬性排序選用排序-合并方法如果一個(gè)表在連接屬性上有索引選用索引連接方法如果上面2個(gè)規(guī)則都不適用，其中一個(gè)表較小選用Hashjoin方法基于啟發(fā)式規(guī)則優(yōu)化(續(xù))可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表)。

理由：設(shè)連接表R與S分別占用的塊數(shù)為Br與Bs連接操作使用的內(nèi)存緩沖區(qū)塊數(shù)為K分配K-1塊給外表如果R為外表，則嵌套循環(huán)法存取的塊數(shù)為Br+Bs/(K-1)Br顯然應(yīng)該選塊數(shù)小的表作為外表二、基于代價(jià)的優(yōu)化啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系統(tǒng)解釋執(zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷之中編譯執(zhí)行的系統(tǒng)中查詢優(yōu)化和查詢執(zhí)行是分開的可以采用精細(xì)復(fù)雜一些的基于代價(jià)的優(yōu)化方法基于代價(jià)的優(yōu)化一、統(tǒng)計(jì)信息基于代價(jià)的優(yōu)化方法要計(jì)算各種操作算法的執(zhí)行代價(jià)，與數(shù)據(jù)庫的狀態(tài)密切相關(guān)數(shù)據(jù)字典中存儲(chǔ)的優(yōu)化器需要的統(tǒng)計(jì)信息：對(duì)每個(gè)基本表該表的元組總數(shù)(N)元組長(zhǎng)度(l)占用的塊數(shù)(B)占用的溢出塊數(shù)(BO)基于代價(jià)的優(yōu)化（續(xù)）對(duì)基表的每個(gè)列該列不同值的個(gè)數(shù)(m)選擇率(f)如果不同值的分布是均勻的，f＝1/m如果不同值的分布不均勻，則每個(gè)值的選擇率＝具有該值的元組數(shù)/N該列最大值該列最小值該列上是否已經(jīng)建立了索引索引類型(B+樹索引、Hash索引、聚集索引)基于代價(jià)的優(yōu)化（續(xù)）對(duì)索引(如B+樹索引)索引的層數(shù)(L)不同索引值的個(gè)數(shù)索引的選擇基數(shù)S(有S個(gè)元組具有某個(gè)索引值)索引的葉結(jié)點(diǎn)數(shù)(Y)基于代價(jià)的優(yōu)化（續(xù)）二、代價(jià)估算示例全表掃描算法的代價(jià)估算公式如果基本表大小為B塊，全表掃描算法的代價(jià)cost＝B如果選擇條件是碼＝值，那么平均搜索代價(jià)cost＝B/2基于代價(jià)的優(yōu)化（續(xù)）2.索引掃描算法的代價(jià)估算公式如果選擇條件是碼＝值如［例1-C2］，則采用該表的主索引若為B+樹，層數(shù)為L(zhǎng)，需要存取B+樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)L塊，再加上基本表中該元組所在的那一塊，所以cost=L+1如果選擇條件涉及非碼屬性如［例1-C3］，若為B+樹索引，選擇條件是相等比較，S是索引的選擇基數(shù)(有S個(gè)元組滿足條件)最壞的情況下，滿足條件的元組可能會(huì)保存在不同的塊上，此時(shí)，cost=L+S基于代價(jià)的優(yōu)化（續(xù)）如果比較條件是＞，＞＝，＜，＜＝操作假設(shè)有一半的元組滿足條件就要存取一半的葉結(jié)點(diǎn)通過索引訪問一半的表存儲(chǔ)塊cost=L+Y/2+B/2如果可以獲得更準(zhǔn)確的選擇基數(shù)，可以進(jìn)一步修正Y/2與B/2基于代價(jià)的優(yōu)化（續(xù)）3.嵌套循環(huán)連接算法的代價(jià)估算公式嵌套循環(huán)連接算法的代價(jià)

cost＝Br+Bs/(K-1)Br如果需要把連接結(jié)果寫回磁盤，

cost＝Br+Bs/(K-1)Br+(Frs*Nr*Ns)/Mrs其中Frs為連接選擇性(joinselectivity)，表示連接結(jié)果元組數(shù)的比例Mrs是存放連接結(jié)果的塊因子，表示每塊中可以存放的結(jié)果元組數(shù)目?；诖鷥r(jià)的優(yōu)化（續(xù)）4.排序-合并連接算法的代價(jià)估算公式如果連接表已經(jīng)按照連接屬性排好序，則

cost＝Br+Bs+(Frs*Nr*Ns)/Mrs。如果必須對(duì)文件排序需要在代價(jià)函數(shù)中加上排序的代價(jià)對(duì)于包含B個(gè)塊的文件排序的代價(jià)大約是(2*B)+(2*B*log2B)查詢優(yōu)化2代數(shù)優(yōu)化3物理優(yōu)化4優(yōu)化步驟51查詢處理優(yōu)化的一般步驟把查詢轉(zhuǎn)換成某種內(nèi)部表示代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式物理優(yōu)化：選擇低層的存取路徑生成查詢計(jì)劃，選擇代價(jià)最小的優(yōu)化的一般步驟(續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示例：求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';把查詢轉(zhuǎn)換成內(nèi)部表示語法樹結(jié)果project(Sname)

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

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

SC.Cno=’2’

Student.Sno=SC.S

×

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

πSname

Student.Sno=SC.Sno

SC.Cno=2

×

StudentSC（3）物理優(yōu)化選擇低層的存取路徑優(yōu)化器查找數(shù)據(jù)字典獲得當(dāng)前數(shù)據(jù)庫狀態(tài)信息選擇字段上是否有索引連接的兩個(gè)表是否有序連接字段上是否有索引然后根據(jù)一定的優(yōu)化規(guī)則選擇存取路徑如本例中若SC表上建有Cno的索引，則應(yīng)該利用這個(gè)索引，而不必順序掃描SC表。（4）選擇代價(jià)最小生成查詢計(jì)劃在作連接運(yùn)算時(shí)，若兩個(gè)表(設(shè)為R1，R2)均無序，連接屬性上也沒有索引，則可以有下面幾種查詢計(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í)可不考慮。SQL語句優(yōu)化IN操作符優(yōu)化但是用IN的SQL性能總是比較低的，從執(zhí)行的步驟來分析用IN的SQL與不用IN的SQL有以下區(qū)別：DB試圖將其轉(zhuǎn)換成多個(gè)表的連接，如果轉(zhuǎn)換不成功則先執(zhí)行IN里面的子查詢，再查詢外層的表記錄，如果轉(zhuǎn)換成功則直接采用多個(gè)表的連接方式查詢。由此可見用IN的SQL至少多了一個(gè)轉(zhuǎn)換的過程。一般的SQL都可以轉(zhuǎn)換成功，但對(duì)于含有分組統(tǒng)計(jì)等方面的SQL就不能轉(zhuǎn)換了。推薦方案：在業(yè)務(wù)密集的SQL當(dāng)中盡量不采用IN操作符。

NOTIN操作符優(yōu)化此操作是強(qiáng)列推薦不使用的，因?yàn)樗荒軕?yīng)用表的索引。推薦方案：用NOTEXISTS或（外連接+判斷為空）方案代替<>操作符優(yōu)化不等于操作符是永遠(yuǎn)不會(huì)用到索引的，因此對(duì)它的處理只會(huì)產(chǎn)生全表掃描。推薦方案：用其它相同功能的操作運(yùn)算代替，如

a<>0改為a>0ora<0

a<>’’改為a>’’NULL優(yōu)化ISNULL判斷字段是否為空一般是不會(huì)應(yīng)用索引的，因?yàn)锽樹索引是不索引空值的。推薦方案：用其它相同功能的操作運(yùn)算代替，如aisnotnull改為a>0或a>’’等。不允許字段為空，而用一個(gè)缺省值代替空值，如申請(qǐng)狀態(tài)字段不允許為空，缺省為申請(qǐng)。>及<操作符優(yōu)化大于或小于操作符一般情況下是不用調(diào)整的，因?yàn)樗兴饕蜁?huì)采用索引查找特殊情況：如右表的數(shù)據(jù)分布執(zhí)行A>2與A>=3的效果就有很大的區(qū)別了，因?yàn)锳>2時(shí)ORACLE會(huì)先找出為2的記錄索引再進(jìn)行比較，而A>=3時(shí)DB則直接找到=3的記錄索引。0…01…12…23…330萬條30萬條39萬條1萬條LIKE操作符優(yōu)化LIK