第九講查詢處理與優(yōu)化

第九講查詢處理和查詢優(yōu)化沈明玉查詢處理與查詢優(yōu)化一、查詢處理查詢處理RDBMS查詢處理階段1.查詢分析2.查詢檢查3.查詢優(yōu)化4.查詢執(zhí)行

查詢處理（續(xù)）查詢分析對查詢語句進(jìn)行掃描、詞法分析和語法分析；從查詢語句中識別出語言符號。查詢檢查根據(jù)數(shù)據(jù)字典對合法的查詢語句進(jìn)行語義檢查；檢查用戶存取權(quán)限、完整性約束等；將SQL語句轉(zhuǎn)換成等價的關(guān)系代數(shù)表達(dá)式（語法分析樹）；把數(shù)據(jù)庫對象的外部名稱轉(zhuǎn)換為內(nèi)部表示。查詢處理（續(xù)）查詢優(yōu)化查詢優(yōu)化：選擇一個高效的查詢處理策略查詢優(yōu)化分類：代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化物理優(yōu)化：指存取路徑和底層操作算法的選擇查詢優(yōu)化方法選擇的依據(jù)：基于規(guī)則(rulebased)基于代價(costbased)基于語義(semanticbased)查詢處理（續(xù)）查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計劃；代碼生成器(codegenerator)生成執(zhí)行查詢計劃的代碼。二、查詢優(yōu)化查詢優(yōu)化查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素由于關(guān)系表達(dá)式的語義級別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義，提供了執(zhí)行查詢優(yōu)化的可能性查詢優(yōu)化（續(xù)）查詢優(yōu)化的必要性[例]求選修了2號課程的學(xué)生姓名。用SQL表達(dá)：SELECTStudent.SnameFROMStudent，SCWHEREStudent.Sno=SC.SnoANDo=‘2’；假定學(xué)生-課程數(shù)據(jù)庫中有1000個學(xué)生記錄，10000個選課記錄其中選修2號課程的選課記錄為50個有多種等價的關(guān)系代數(shù)表達(dá)式來完成這一查詢：Q1=πSname(σStudent.Sno=SC.Sno∧o='2'(Student×SC))Q2=πSname(σo='2'(StudentSC))Q3=πSname(Studentσo='2'(SC))查詢優(yōu)化（續(xù)）設(shè)一個塊能裝10個Student元組或100個SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，每秒讀寫20塊，內(nèi)存處理時間忽略。第一種情況Q1=πSname(σStudent.Sno=SC.Sno∧o='2'Student×SC))1.計算廣義笛卡爾積讀取總塊數(shù)為:=>105s連接后的元組數(shù)為103×104=107。設(shè)每塊能裝10個元組，則寫出這些塊要用106/20=5×104s2.選擇操作讀取中間文件花費(fèi)的時間(同寫中間文件一樣)需5×104s滿足條件的元組假設(shè)僅50個，均可放在內(nèi)存總耗時（投影處理時間忽略）：105+2×5×104≈105s（27.8天）查詢優(yōu)化（續(xù)）第二種情況1.計算自然連接執(zhí)行自然連接，讀取Student和SC表的策略不變，總的讀取塊數(shù)仍為2100塊花費(fèi)105s自然連接的結(jié)果比第一種情況大大減少，為104個寫出這些元組時間為104/10/20=50s，為第一種情況的千分之一2.讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時間也為50s。3.把第2步結(jié)果投影輸出。第二種情況總的執(zhí)行時間≈105+50+50≈205s查詢優(yōu)化（續(xù)）第三種情況1.先對SC表作選擇運(yùn)算，只需讀一遍SC表，存取100塊花費(fèi)時間為5s，因為滿足條件的元組僅50個，不必使用中間文件。2.讀取Student表，把讀入的Student元組和內(nèi)存中的SC元組作連接。也只需讀一遍Student表共100塊，花費(fèi)時間為5s。3.把連接結(jié)果投影輸出

第三種情況總的執(zhí)行時間≈5+5≈10s查詢優(yōu)化（續(xù)）11代數(shù)優(yōu)化代數(shù)優(yōu)化策略：通過關(guān)系代數(shù)表達(dá)式的等價變換來提高查詢效率關(guān)系代數(shù)表達(dá)式的等價：指用相同的關(guān)系代替兩個表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的兩個關(guān)系表達(dá)式E1和E2是等價的，可記為E1≡E2

查詢優(yōu)化（續(xù)）典型的啟發(fā)式優(yōu)化規(guī)則：1.選擇運(yùn)算應(yīng)盡可能先做。在優(yōu)化策略中這是最重要、最基本的一條；2.把投影運(yùn)算和選擇運(yùn)算同時進(jìn)行；3.把投影同其前或其后的雙目運(yùn)算結(jié)合起來；4.把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個連接運(yùn)算；5.找出公共子表達(dá)式。查詢優(yōu)化（續(xù)）物理優(yōu)化代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑；對于一個查詢語句有許多存取方案，它們的執(zhí)行效率不同，僅僅進(jìn)行代數(shù)優(yōu)化是不夠的；物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計劃。基于規(guī)則的啟發(fā)式優(yōu)化基于代價估算的優(yōu)化兩者結(jié)合的優(yōu)化方法查詢優(yōu)化（續(xù)）選擇操作的啟發(fā)式規(guī)則:1.小關(guān)系，使用全表順序掃描，即使選擇列上有索引。2.大關(guān)系，啟發(fā)式規(guī)則有：

1）選擇條件是主碼＝值的查詢，可以選擇主碼索引。2）選擇條件是非主屬性＝值的查詢，且選擇列上有索引：估算查詢結(jié)果的元組數(shù)目，若比例較小(<10%)可以使用索引，否則全表掃描3）選擇條件是非等值查詢或者范圍查詢，且選擇列上有索引：方法同上！查詢優(yōu)化（續(xù)）

4）對于使用AND的組合條件如果有涉及這些屬性的組合索引，優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引，則可以采用索引掃描方法（具體介紹），否則使用全表順序掃描。

5）對于使用OR的組合條件，一般使用全表順序掃描。查詢優(yōu)化（續(xù)）連接操作的啟發(fā)式規(guī)則：

1.如果2個表都已經(jīng)按照連接屬性排序：選用排序-合并方法

2.如果一個表在連接屬性上有索引：選用