第 查詢處理和優(yōu)化PPT課件

1、數(shù)據(jù)庫查詢語言的處理過程數(shù)據(jù)庫查詢語言的處理過程: :（1）解釋方式執(zhí)行）解釋方式執(zhí)行應(yīng)用程序優(yōu)化占執(zhí)行時(shí)間！第1頁/共48頁(2)(2)編譯方式編譯方式優(yōu)化不占執(zhí)行時(shí)間！第2頁/共48頁對(duì)于常見的例行事務(wù)，編譯方式可提高性能。對(duì)于常見的例行事務(wù)，編譯方式可提高性能。對(duì)于簡(jiǎn)短的即時(shí)查詢，解釋方式靈活實(shí)用。對(duì)于簡(jiǎn)短的即時(shí)查詢，解釋方式靈活實(shí)用。解釋方式和編譯方式各適用于什么情況？解釋方式和編譯方式各適用于什么情況？第3頁/共48頁第4頁/共48頁6.2 6.2 代數(shù)優(yōu)化代數(shù)優(yōu)化 代數(shù)優(yōu)化對(duì)查詢進(jìn)行等效變換，以減少執(zhí)行開銷。代數(shù)優(yōu)化對(duì)查詢進(jìn)行等效變換，以減少執(zhí)行開銷。 代數(shù)優(yōu)化的原則是代數(shù)優(yōu)化的原

2、則是盡量減小查詢過程中間結(jié)果的盡量減小查詢過程中間結(jié)果的大小大小。 選擇、投影操作通常能夠有效地減小關(guān)系的大小。選擇、投影操作通常能夠有效地減小關(guān)系的大小。連接、迪卡爾乘積和并操作容易生成較大的查詢中連接、迪卡爾乘積和并操作容易生成較大的查詢中間結(jié)果。間結(jié)果。 因此，因此，先做選擇、投影先做選擇、投影；先做小關(guān)系間的連接，先做小關(guān)系間的連接，再做大關(guān)系的連接再做大關(guān)系的連接；甚至需要先找出查詢中的公共表甚至需要先找出查詢中的公共表達(dá)式達(dá)式，以避免重復(fù)運(yùn)算。，以避免重復(fù)運(yùn)算。第5頁/共48頁常用變換規(guī)則常用變換規(guī)則).)(.()(21 .2 1RRcncccnANDcANDc1.)()(1221

3、RRcccc2.nlistlistlistlistlistlistlistRRn.),().)(.(211213.,.,2, 1)() )()(,.,2, 1,.,2, 1AnAACAttrRRAnAAccAnAA4.第6頁/共48頁5.R JN S = S JN RR JN S = S JN RAttr(R)Attr(c)S JN (R)(S) JN (，ccR6.)()2(),() 1(),()() (212 1SAttrcAttrRAttrcAttrSJNRSJNRcccANDc7.第7頁/共48頁LcAttrSJNRSJNRSAttrBBRAttrBBBmBcAnAcLmnmn)()(

4、)() ()(,.,),(A,.,A,.,A,.,AL,.,1,.,11111式中則其中，屬性集8.)( )() (,SRSRccc則9.)( )() (,SRSRLLL則10.第8頁/共48頁) (S ) (,TRTSRJN則11.第9頁/共48頁范例范例p118p118例例6-16-1 設(shè)有設(shè)有S(S(供應(yīng)商供應(yīng)商) )，P(P(零件零件) )，SP(SP(供應(yīng)關(guān)系供應(yīng)關(guān)系) )三個(gè)關(guān)系，關(guān)系模三個(gè)關(guān)系，關(guān)系模式如下：式如下： S(SNUM,SNAME,CITY) S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) P(PNUM,PNAME,WEIGH

5、T,SIZE) SP(SNUM,PNUM,DEPT,QUAN) SP(SNUM,PNUM,DEPT,QUAN)有如下查詢有如下查詢Q : Q : SELECTSELECT SNAME SNAME FROMFROM S,P,SP S,P,SP WHEREWHERE S.SNUM = SP.SNUM S.SNUM = SP.SNUM AND SP.PNUM = P.PNUM AND SP.PNUM = P.PNUM AND S.CITY = AND S.CITY = NANJINGNANJING AND P.PNAME = AND P.PNAME = BOLTBOLT AND SP.QUAN 10

6、000 AND SP.QUAN 10000 第10頁/共48頁 SQLSQL語句轉(zhuǎn)化為原始查詢樹語句轉(zhuǎn)化為原始查詢樹 Select Select From From Where Where 第11頁/共48頁Q : SELECT SNAME FROM S,P,SP WHERE S.SNUM = SP.SNUM AND SP.PNUM = P.PNUM AND S.CITY = NANJING AND P.PNAME = BOLT AND SP.QUAN 10000 CSpSPSNAME原始查詢樹原始查詢樹第12頁/共48頁SNAMECSpSPPNUMPPNUMSP.SNUMSPSNUMS.NA

7、NJINGCITYS10000.QUANSP.BOLTPNAMEPSNAMESSPp選擇操作盡量下壓選擇操作盡量下壓.NANJINGCITYSSNUMSPSNUMS.10000.QUANSP.BOLTPNAMEPPNUMPPNUMSP.原始查詢樹原始查詢樹第13頁/共48頁先連接小關(guān)系先連接小關(guān)系 S,P,SP S,P,SP經(jīng)選擇后得經(jīng)選擇后得S S、P P、SPSP，估算大?。汗浪愦笮。?|S|=|S|/NCITY |P|=|P|/NPNAME |SP|=|SP|(Vmax-10000)/(Vmax-Vmin) 設(shè)設(shè)| |S S|P|P|, |SP|, |SP|P|,S(j)B then j

8、j+1 else if R(i)AS(j)B then ii+1 else /* R(i)A=S(j)B，輸出連接元組輸出連接元組*/ 第33頁/共48頁輸出輸出至至T;/*輸出輸出R(i)和和S中除中除S(j)外外的其他元組所組成的連接元組的其他元組所組成的連接元組 */lj+1;While(l m) and (R(i)A=S(l)B) do輸出輸出至至T; ll+1;/*輸出輸出S(j)和和R中除中除R(i)外外的其他元組所組成的連接元組的其他元組所組成的連接元組 */ki+1;While(k n) and (R(k)A=S(j)B) do輸出輸出至至T; kk+1;ii+1,jj+1;

9、第34頁/共48頁4).4).散列連接法散列連接法第35頁/共48頁 關(guān)鍵在于建立一個(gè)供連接用的散列文件。關(guān)鍵在于建立一個(gè)供連接用的散列文件。 可以在桶（散列文件）中不填入可以在桶（散列文件）中不填入R R、S S的實(shí)際元組，的實(shí)際元組，而是代之以元組的而是代之以元組的tidtid，從而大大的縮小散列文件，從而大大的縮小散列文件，使其有可能在內(nèi)存中建立，而僅需對(duì)使其有可能在內(nèi)存中建立，而僅需對(duì)R R、S S各掃描一次。各掃描一次。 建立散列文件需要對(duì)R、S各掃描一次，且關(guān)系R和S一般不會(huì)對(duì)連接屬性進(jìn)行簇集。故而，每向散列文件加入一個(gè)元組，都需要一次I/O操作。如何減少I/O次數(shù)?第36頁/共4

10、8頁 掃描R和S時(shí)，取出A(R)、B(S)，附在相應(yīng)的tid后，連接時(shí)以桶為單位，按A(R)=B(S)找出匹配元組的tid對(duì)。第37頁/共48頁 在取實(shí)際元組時(shí)，為減少物理塊訪問，可將各桶中，匹配元組的tid按塊分類，一次集中取出同一塊中所需的所有元組，當(dāng)然這需要較大的內(nèi)存開銷。第38頁/共48頁第39頁/共48頁第40頁/共48頁用排序法消除重復(fù)元組用排序法消除重復(fù)元組 對(duì)關(guān)系對(duì)關(guān)系R R的每個(gè)元組的每個(gè)元組t t，生成生成tt，并，并存于存于T T中；中；/ /* * T T 是未消除重復(fù)元組的投影結(jié)果是未消除重復(fù)元組的投影結(jié)果* */ /If If 含有含有R R的主鍵的主鍵 then

11、Tthen TT T elseT elseT按所有屬性排序；按所有屬性排序； i i1,j1,j2;2; while(i while(i n)n) do do輸出元組輸出元組T T(i)(i)到到T;T; 第41頁/共48頁while T(i)= T(j) do jj+1;/*消除重復(fù)元組，設(shè)有偽元組Tn+1Tn*/ij,ji+1; 第42頁/共48頁常用集合操作：笛卡爾乘積、并、交、差等。常用集合操作：笛卡爾乘積、并、交、差等。 設(shè)關(guān)系設(shè)關(guān)系R、S并兼容，對(duì)并兼容，對(duì)R、S進(jìn)行并（交、差）操作，進(jìn)行并（交、差）操作，可以先將可以先將R和和S按同一屬性（通常選用主鍵）排序，然后按同一屬性（通常

12、選用主鍵）排序，然后掃描兩個(gè)關(guān)系，選出所需的元組。掃描兩個(gè)關(guān)系，選出所需的元組。 笛卡爾乘積將兩個(gè)關(guān)系的元組無條件地互相拼接，笛卡爾乘積將兩個(gè)關(guān)系的元組無條件地互相拼接，一一般用嵌套循環(huán)法實(shí)現(xiàn)，做起來很費(fèi)時(shí)，結(jié)果要比參與運(yùn)般用嵌套循環(huán)法實(shí)現(xiàn)，做起來很費(fèi)時(shí)，結(jié)果要比參與運(yùn)算的關(guān)系大的多。應(yīng)盡量少用！算的關(guān)系大的多。應(yīng)盡量少用！第43頁/共48頁 散列是上述并交差操作的另一種求解方法散列是上述并交差操作的另一種求解方法： 將關(guān)系將關(guān)系R散列到一個(gè)散列文件中，再將散列到一個(gè)散列文件中，再將S散列到同一文散列到同一文件中。同時(shí)檢查桶中有無重復(fù)元組。對(duì)于并，不再插入件中。同時(shí)檢查桶中有無重復(fù)元組。對(duì)于并

13、，不再插入重復(fù)元組；對(duì)于交，選取重復(fù)元組；對(duì)于差，從桶中取重復(fù)元組；對(duì)于交，選取重復(fù)元組；對(duì)于差，從桶中取消與消與S重復(fù)的元組。重復(fù)的元組。第44頁/共48頁 有時(shí)，多個(gè)操作組合起來同時(shí)進(jìn)行，如投影和選擇操有時(shí)，多個(gè)操作組合起來同時(shí)進(jìn)行，如投影和選擇操作組合起來執(zhí)行（消除重復(fù)元組另外單獨(dú)進(jìn)行），可提作組合起來執(zhí)行（消除重復(fù)元組另外單獨(dú)進(jìn)行），可提高效益。高效益。 還可以在更大范圍內(nèi)，將多個(gè)操作組合起來執(zhí)行。還可以在更大范圍內(nèi)，將多個(gè)操作組合起來執(zhí)行。RS1212第45頁/共48頁 假設(shè)連接用嵌套循環(huán)法，假設(shè)連接用嵌套循環(huán)法，R為外關(guān)系，為外關(guān)系，S為內(nèi)關(guān)系，為內(nèi)關(guān)系，R的選擇、投影可在掃描的選擇、投影可在掃描R時(shí)執(zhí)行，時(shí)執(zhí)行，S的選擇、投影可的選擇、投影可在首次掃描在首次掃描S時(shí)執(zhí)行，并將選擇、投影的結(jié)果存入臨時(shí)執(zhí)行，并將選擇、投影的結(jié)果存入臨時(shí)文件，之后各輪只需掃描臨時(shí)文件即可。時(shí)文件，之后各輪只需掃描臨時(shí)文件即可。 最后一個(gè)投影操作，可在生成連接結(jié)果的同時(shí)進(jìn)最后一個(gè)投影操作，可在生成連接結(jié)果的同時(shí)進(jìn)行。行。第46頁/共48頁 在執(zhí)行前進(jìn)行優(yōu)化稱為在執(zhí)行前進(jìn)行優(yōu)化稱為靜態(tài)優(yōu)化靜態(tài)優(yōu)化，只能利用統(tǒng)計(jì)，只能利用統(tǒng)計(jì)數(shù)據(jù)，有時(shí)不一定準(zhǔn)。數(shù)據(jù)，有時(shí)不一定準(zhǔn)。 在查詢執(zhí)行時(shí)進(jìn)行優(yōu)化稱為在查詢執(zhí)行時(shí)進(jìn)行優(yōu)化稱為動(dòng)態(tài)優(yōu)化動(dòng)態(tài)優(yōu)化，用實(shí)際執(zhí)，用實(shí)際執(zhí)行結(jié)果估算代價(jià)，比較符合實(shí)際，但每次執(zhí)行都