第6章-查詢處理和優(yōu)化word版本

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

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

3、1RRcccc2.nlistlistlistlistlistlistlistRRn.),().)(.(211213.,.,2, 1)() )()(,.,2, 1,.,2, 1AnAACAttrRRAnAAccAnAA4.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.LcAttrSJNRSJNRSAttrBBRAttrBBBmBcAnAcLmnmn)()()() ()(,.,),(A,

4、.,A,.,A,.,AL,.,1,.,11111式中則其中，屬性集8.)( )() (,SRSRccc則9.)( )() (,SRSRLLL則10.) (S ) (,TRTSRJN則11.范例范例p118p118例例6-16-1 設有設有S(S(供應商供應商) )，P(P(零件零件) )，SP(SP(供應關系供應關系) )三個關系，關系模三個關系，關系模式如下：式如下： S(SNUM,SNAME,CITY) S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) P(PNUM,PNAME,WEIGHT,SIZE) SP(SNUM,PNUM,DEPT,QUAN)

5、 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 10000 AND SP.QUAN 10000 nSQLSQL語句

6、轉(zhuǎn)化為原始查詢樹語句轉(zhuǎn)化為原始查詢樹 Select Select From From Where Where 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原始查詢樹原始查詢樹SNAMECSpSPPNUMPPNUMSP.SNUMSPSNUMS.NANJINGCITYS10000.QUANSP.BOLTPNAMEPSNAMESSPp選擇操作盡量下壓選擇操作盡量下壓

7、.NANJINGCITYSSNUMSPSNUMS.10000.QUANSP.BOLTPNAMEPPNUMPPNUMSP.原始查詢樹原始查詢樹先連接小關系先連接小關系 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) 設設| |S S|P|P|, |SP|, |SP|P|,S(j)B then jj+1 else if R(i)AS(j)B then ii+1 else /* R(i)A=S(j)B，輸出連接元組輸出連接元組*/

8、 輸出輸出至至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; 問題：等值匹配對使用排序問題：等值匹配對使用排序歸并法進行連接操作的效率歸并法進行連接操作的效率有什么影響？有什么影響？ p個個 q個個 R.A 2 2

9、S.B 2 2 2 2 2 2 2 2 2 2 2 2 2 2 . . . . . . 注意等值的掃描次數(shù)（假設注意等值的掃描次數(shù)（假設p q）：）： 1+( 1+(q-1)+(p-1)+1+(q-2)+(p-2)+q-1)+(p-1)+1+(q-2)+(p-2)+ +1+( +1+(q-p)+(p-p)q-p)+(p-p)=(p+q-1)+(p+q-2q+1)/2=(p+q-1)+(p+q-2q+1)/2* *p p=p=p* *q q O(pq)O(pq)4).4).散列連接法散列連接法 關鍵在于建立一個供連接用的散列文件。關鍵在于建立一個供連接用的散列文件。 可以在桶（散列文件）中不填入

10、可以在桶（散列文件）中不填入R R、S S的實際元組，的實際元組，而是代之以元組的而是代之以元組的tidtid，從而大大的縮小散列文件，從而大大的縮小散列文件，使其有可能在內(nèi)存中建立，而僅需對使其有可能在內(nèi)存中建立，而僅需對R R、S S各掃描一次。各掃描一次。 建立散列文件需要對建立散列文件需要對R R、S S各掃描一次，且關系各掃描一次，且關系R R和和S S一般不會對連接屬性進行簇集。故而，每向散列文一般不會對連接屬性進行簇集。故而，每向散列文件加入一個元組，都需要一次件加入一個元組，都需要一次I/OI/O操作。操作。如何減少如何減少I/OI/O次數(shù)次數(shù)? ? 掃描掃描R R和和S S時

11、，取出時，取出 A A(R)(R)、 B B(S)(S)，附在相應的附在相應的tidtid后，連接時以桶為單位，按后，連接時以桶為單位，按 A A(R)=(R)= B B(S)(S)找出匹配元組找出匹配元組的的tidtid對。對。 問題：問題：似乎多此一舉！匹配元組的似乎多此一舉！匹配元組的tidtid一定在同一一定在同一桶中！為什么還要按桶中！為什么還要按 A A(R)=(R)= B B(S)(S)找出匹配元組？這找出匹配元組？這么做有必要么？么做有必要么？ 注意：注意：A=B A=B h(A)=h(B) h(A)=h(B)，但不一定有：但不一定有： h(A)=h(B) h(A)=h(B)

12、A=B A=B 在取實際元組時，為減少物理塊訪問，可將各在取實際元組時，為減少物理塊訪問，可將各桶中，匹配元組的桶中，匹配元組的tidtid按塊分類，一次集中取出同按塊分類，一次集中取出同一塊中所需的所有元組，當然這需要較大的內(nèi)存一塊中所需的所有元組，當然這需要較大的內(nèi)存開銷。開銷。用排序法消除重復元組用排序法消除重復元組 對關系對關系R R的每個元組的每個元組t t，生成生成tt，并，并存于存于T T中；中；/ /* * T T 是未消除重復元組的投影結(jié)果是未消除重復元組的投影結(jié)果* */ /If If 含有含有R R的主鍵的主鍵 then Tthen TT T elseT elseT按所有

13、屬性排序；按所有屬性排序； i i1,j1,j2;2; while(i while(i n)n) do do輸出元組輸出元組T T(i)(i)到到T;T; while Twhile T(i)= T(i)= T(j) do j(j) do jj+1;j+1;/ /* *消除重復元組，設有偽元組消除重復元組，設有偽元組T Tn+1n+1 T Tnn* */ /i ij,jj,ji+1;i+1; 常用集合操作：笛卡爾乘積、并、交、差等。常用集合操作：笛卡爾乘積、并、交、差等。 設關系設關系R、S并兼容，對并兼容，對R、S進行并（交、差）操作，進行并（交、差）操作，可以先將可以先將R和和S按同一屬性（

14、通常選用主鍵）排序，然后按同一屬性（通常選用主鍵）排序，然后掃描兩個關系，選出所需的元組。掃描兩個關系，選出所需的元組。 笛卡爾乘積將兩個關系的元組無條件地互相拼接，笛卡爾乘積將兩個關系的元組無條件地互相拼接，一一般用嵌套循環(huán)法實現(xiàn)，做起來很費時，結(jié)果要比參與運般用嵌套循環(huán)法實現(xiàn)，做起來很費時，結(jié)果要比參與運算的關系大的多。應盡量少用！算的關系大的多。應盡量少用！ 散列是上述并交差操作的另一種求解方法散列是上述并交差操作的另一種求解方法： 將關系將關系R散列到一個散列文件中，再將散列到一個散列文件中，再將S散列到同一文散列到同一文件中。同時檢查桶中有無重復元組。對于并，不再插入件中。同時檢查桶

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