數(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í)行

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

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

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

C1：無條件；

C2：Sno＝'200433103046'；

C3：Sage>20；

C4：Sdept＝'CS'ANDSage>20；

SnoSNameSSexSageSdept

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

適合小表，不適合大表SnoSNameSSexSageSdept

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

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

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2'查詢過程的假設條件假設1：外存：（Student:1000條,SC:10000條,選修2號課程:50條）假設2：一個內(nèi)存塊裝元組:10個Student,或100個SC,內(nèi)存中一次可以存放:5塊Student元組,1塊SC元組和若干塊連接結(jié)果元組假設3：讀寫速度：20塊/秒假設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ù)時間=2100/20=105秒不同的執(zhí)行策略，考慮I/O時間中間結(jié)果大小=1000*10000=107(1千萬條元組)寫中間結(jié)果時間=10000000/10/20=50000秒

②б

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

③П

總時間=105＋50000＋50000秒=100105秒

=27.8小時執(zhí)行策略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分鐘

執(zhí)行策略3Ｑ3＝П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秒執(zhí)行策略4Ｑ4＝ПＳname(StudentбSC.Cno='2'(SC))假設SC表在Cno上有索引，Student表在Sno上有索引

①б

讀SC表索引=

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

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

讀Student表索引=

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

總時間<0.4秒查詢優(yōu)化2代數(shù)優(yōu)化3物理優(yōu)化4優(yōu)化步驟51查詢處理查詢優(yōu)化的一般準則選擇運算應盡可能先做

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

投影運算和選擇運算同時做目的：避免重復掃描關系將投影運算與其前面或后面的雙目運算結(jié)合目的：減少掃描關系的遍數(shù)查詢優(yōu)化的一般準則某些選擇運算＋在其前面執(zhí)行的笛卡爾積

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

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

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關系代數(shù)等價變換規(guī)則（續(xù)）投影的串接定律

πA1,A2,

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

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

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

(b)假設:F中有不屬于A1,…,An的屬性B1,…,BmπA1,A2,,An

(

бF

(E))≡ πA1,A2,,An(бF

(πA1,A2,,An,B1,B2,,Bm(E)))關系代數(shù)等價變換規(guī)則（續(xù)）選擇與笛卡爾積的交換律(a)假設：F中涉及的屬性都是E1中的屬性

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

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

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

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

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

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

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

選擇與差運算的交換 假設：E1與E2有相同的屬性名

бF(E1-E2)≡бF(E1)-бF(E2)關系代數(shù)等價變換規(guī)則（續(xù)）投影與笛卡爾積的交換 假設：E1和E2是兩個關系表達式，A1，…，An是E1的屬性，B1，…，Bm是E2的屬性

πA1,A2,…,An,B1,B2,…,Bm

（E1×E2)≡

πA1,A2,…,An（E1)×πB1,B2,…,Bm(E2)關系代數(shù)等價變換規(guī)則（續(xù)）投影與并的交換

假設：E1和E2有相同的屬性名

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

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

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

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的優(yōu)化（續(xù)）4.排序-合并連接算法的代價估算公式如果連接表已經(jīng)按照連接屬性排好序，則

cost＝Br+Bs+(Frs*Nr*Ns)/Mrs。如果必須對文件排序需要在代價函數(shù)中加上排序的代價對于包含B個塊的文件排序的代價大約是(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)換成標準（優(yōu)化）形式物理優(yōu)化：選擇低層的存取路徑生成查詢計劃，選擇代價最小的優(yōu)化的一般步驟(續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示例：求選修了課程Ｃ2的學生姓名

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關系代數(shù)語法樹πSname

SC.Cno=’2’

Student.Sno=SC.S

×

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

πSname

Student.Sno=SC.Sno

SC.Cno=2

×

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

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

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

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