第6章查詢處理和優(yōu)化

第6章查詢處理和優(yōu)化例如：12+64+88=？

查詢優(yōu)化是相對而言的，可能的執(zhí)行策略很多，窮盡代價很大，不能片面追求絕對的最優(yōu)。（12+88）+64=164數據庫查詢語言的處理過程:（1）解釋方式執(zhí)行解釋執(zhí)行查詢語句DBMS

BEGINTRAN查詢語句END應用程序查詢請求查詢結果優(yōu)化占執(zhí)行時間?。〔樵冋Z句(2)編譯方式

BEGINTRAN查詢語句END應用程序

…CALLAM(參數)…AM依賴因素訪問模塊AM預編譯編譯和連接目標碼執(zhí)行優(yōu)化不占執(zhí)行時間??！對于常見的例行事務，編譯方式可提高性能。對于簡短的即時查詢，解釋方式靈活實用。解釋方式和編譯方式各適用于什么情況？代數優(yōu)化對查詢語句進行變換不涉及存取路徑物理優(yōu)化根據存取路徑選擇合理的存取策略進行優(yōu)化規(guī)則優(yōu)化

僅根據啟發(fā)式規(guī)則選擇執(zhí)行的策略進行優(yōu)化代價估算優(yōu)化

6.2代數優(yōu)化代數優(yōu)化對查詢進行等效變換，以減少執(zhí)行開銷。代數優(yōu)化的原則是盡量減小查詢過程中間結果的大小。選擇、投影操作通常能夠有效地減小關系的大小。連接、迪卡爾乘積和并操作容易生成較大的查詢中間結果。因此，先做選擇、投影；先做小關系間的連接，再做大關系的連接；甚至需要先找出查詢中的公共表達式，以避免重復運算。常用變換規(guī)則1.2.3.4.5.RJNS=SJNR6.7.8.9.10.注意：規(guī)則11中，對于連接運算，可能出現S與T之間無連接條件的情況，此時的連接運算成為迪卡爾乘積。例如：(RJNc1S)JNc2T,式中，Attr.(c1)Attr.(R)Attr.(S)Attr.(c2)Attr.(R)Attr.(T)而S和T之間沒有連接條件?？筛膶憺椋篟JNc1ANDc2(ST)11.范例p118例6-1設有S(供應商)，P(零件)，SP(供應關系)三個關系，關系模式如下：S(SNUM,SNAME,CITY)P(PNUM,PNAME,WEIGHT,SIZE)SP(SNUM,PNUM,DEPT,QUAN)有如下查詢Q:SELECTSNAMEFROMS,P,SPWHERES.SNUM=SP.SNUMANDSP.PNUM=P.PNUMANDS.CITY=‘NANJING’ANDP.PNAME=‘BOLT’ANDSP.QUAN>10000

SQL語句轉化為原始查詢樹SelectFromWhereQ可用右圖所示的原始查詢樹表示：Q:SELECTSNAMEFROMS,P,SPWHERES.SNUM=SP.SNUMANDSP.PNUM=P.PNUMANDS.CITY=‘NANJING’ANDP.PNAME=‘BOLT’ANDSP.QUAN>10000原始查詢樹選擇操作下壓選擇操作盡量下壓原始查詢樹先連接小關系S,P,SP經選擇后得S’、P’、SP’，估算大小：

|S’|=|S|/NCITY|P’|=|P|/NPNAME|SP’|=|SP|×(Vmax-10000)/(Vmax-Vmin)

設|S’|<|P’|,|SP’|<|P’|消除對查詢無用的屬性消除對查詢無用的屬性代數優(yōu)化的基本步驟：1.以SELECT子句對應投影操作，以FROM字句對應迪卡爾乘積，以WHERE子句對應選擇操作，生成原始查詢樹。2.應用變換規(guī)則2)、6)、7)、9)、10)，盡可能將選擇條件移向樹葉方向。3.應用連接、迪卡爾乘積的結合律，按照小關系優(yōu)先做的原則，重新安排連接（笛卡爾乘積）的順序。4.如果笛卡爾乘積后還須按連接條件進行選擇操作可將兩者組合成連接操作。5.對每個葉節(jié)點加必要的投影操作，以消除對查詢無用的屬性。以上所討論的都是非嵌套查詢。嵌套查詢比較復雜，分如下兩種情況：1.嵌入的查詢塊與上層查詢無關

從最低層查詢開始，用上述步驟和規(guī)則，逐層計算各查詢快所等效的關系，直至求出查詢結果。2.嵌入的查詢塊與上層查詢有關

一般用代入法。例如：SELECTA1FROMR1WHERER1.A2比較符CONST1ANDR1.A3IN(SELECTA4FROMR2WHERER2.A5比較符R1.A1)將第一層查詢所涉及R1表中的每條記錄，代入虛線框所標出查詢體，此時R1.A1為一個常量值，判斷該記錄是否滿足查詢條件。存在什么問題？能否再進行優(yōu)化？

注意：采用代入法時，盡可能作“部分選擇”！SELECTA1FROMR1WHERER1.A2比較符CONST1AND

R1.A3IN(SELECTA4FROMR2WHERER2.A5比較符R1.A1)FROMR1WHERER1.A2比較符CONST1ANDFROMR1’WHERER1’.A3看作臨時表R1’將R1’的每個元組逐個代入，檢查限制條件是否滿足，以減少需檢查的上層查詢所涉及表的元組數目！有些DBMS將嵌套查詢轉換為等效的非嵌套查詢，但是這種方法不一定在所有情況下都可行。6.3依賴于存取路徑的規(guī)則優(yōu)化代數優(yōu)化不涉及存取路徑，對各種操作的執(zhí)行策略無從選擇。只能在操作的次序和組合上做一些變換和調整。單靠代數優(yōu)化比較粗糙，優(yōu)化效果有限，合理選擇存取路徑，往往能收到顯著的效果。本節(jié)結合存取路徑的分析，討論各種基本操作執(zhí)行的策略及其選擇原則。6.3.1選擇操作的實現和優(yōu)化

選擇條件：等值=范圍>,<集合IN,EXISTS,NOTEXISTS復合AND,OR

選擇操作的執(zhí)行策略與選擇條件、可用的存取路徑以及選取的元組數在整個關系中所占的比例有關。實現方法：順序掃描、盡量利用散列索引等方法。選擇操作選擇存取路徑的啟發(fā)式規(guī)則：（1）對于小關系，順序掃描。（2）若無索引、散列等存取路徑可用，或估計選取的元組數占關系的比例較大（大于20%）且有關屬性上無簇集索引，順序掃描。（3）對于主鍵的等值選擇，優(yōu)先選用主鍵的索引或散列。（4）對于非主鍵的等值選擇，若選取的元組數占關系的比例較?。ㄐ∮?0%），可以用無序索引；否則只能用簇集索引或順序掃描。（為什么？）（5）.對于范圍條件，先通過索引找到范圍的邊界，再通過索引的順序集沿相應方向搜索，如中選的元組數在關系中所占比例較大，宜采用簇集索引或順序掃描。（6）對于用AND連接的合取選擇條件：優(yōu)先選用多屬性索引若有多個可用的次索引，可用預查找處理，最后做其余條件檢查個別條件可用（3）（4）（5）之一，求得相應組，再將這些元組用其它條件篩選順序掃描（7）用OR連接的析取選擇條件，尚無好的方法。只能按其中各個條件分別選出一個元組集，再求這些元組集的并。在OR連接的諸條件中，只要有一個條件無合適的存取路徑，就只能用順序掃描！6.3.2連接操作的實現和優(yōu)化連接開銷較大，為查詢優(yōu)化的重點，這里主要討論二元連接（TwoWayJoin）。實現方法1.嵌套循環(huán)法（nestedloop）2.利用索引或散列尋找匹配元組法3.排序歸并4.散列連接法1).嵌套循環(huán)關系R與S進行連接操作，最原始的辦法是取R的一個元組，與S的所有元組比較，凡是滿足連接條件的元組就進行連接并且作為結果輸出。然后再取R的下一個元組，和S的所有元組比較，直到R的所有元組比較完為止。RSR.A=S.BR(n個)S(m個)ij嵌套循環(huán)算法/*設R有n個元組，S有m個元組*/i:=1,j:=1;while(i≤n)do{while(j≤m)do{ifR(i)[A]=S(j)[B]then輸出<R(i),S(j)>至T;j:=j+1}j:=1,i:=i+1}T為R和S連接的結果R為外關系（outerrelation）,S為內關系（innerrelation）。事實上，關系是以物理塊為單位取到內存，設R和S各有一緩沖塊，PR為R的塊因子（每塊中所含的元組數）。則R每次I/O取PR個元組，可改進上述算法，使S掃描一次可以與R的PR個元組比較，那么S的掃描次數為bR=[n/PR]。RS物理塊物理塊

假設，bR和bS分別為關系R和關系S占用物理塊的數目(bR=[n/PR])，nB為可供連接使用的緩沖塊數。若將其中的nB-1塊作為外關系緩沖塊，1塊作為內關系緩沖塊。則以R為外關系、S為內關系，用嵌套循環(huán)法進行連接所需訪問的物理塊數為bR+[bR/(nB-1)]*bS，對應最小I/O值。

問題：增加外關系R的緩沖塊（每次多取幾塊R的數據）或增加內關系S的緩沖塊都能減少I/O次數。為什么將nB-1塊作為外關系緩沖塊，1塊作為內關系緩沖塊，是最優(yōu)分配策略？問題：嵌套循環(huán)法進行連接操作，以R為外關系、S為內關系;還是以S為外關系、R為內關系所需I/O次數更少？作為外層循環(huán)的關系，有什么要求？應將占用物理塊少的關系，作為外關系！2).利用索引或散列尋找匹配元組法

在嵌套循環(huán)法中，內關系上要做多次順序掃描，若內關系上有合適的存取路徑（連接屬性上的索引散列等），可以避免內關系上的順序掃描，以減少I/O次數。

問題：若在內關系的連接屬性上建有索引？是否一定能夠提高內關系和外關系的匹配效率？當每次循環(huán)所選的匹配元組數在內關系中占有較大比例（例如超過15%）時，用無序索引甚至還不如用順序掃描的方法。內關系的連接屬性上有簇集索引時，索引對減少連接所需I/O次數的作用最明顯。3).排序歸并如果R和S按連接屬性排序，可按序比較R.A和S.B以找出匹配元組。跳過

R.A2S.過

跳過

算法：R按屬性A排序/*設R有n個元組*/S按屬性B排序/*設S有m個元組*/i1,j1;While(in)and(jm)do{ifR(i)[A]>S(j)[B]thenjj+1elseifR(i)[A]<S(j)[B]thenii+1else{/*R(i)[A]=S(j)[B]，輸出連接元組*/

輸出<R(i),S(j)>至T;/*輸出R(i)和S中除S(j)外的其他元組所組成的連接元組*/lj+1;While(lm)and(R(i)[A]=S(l)[B])do{輸出<R(i),S(l)>至T;ll+1;}/*輸出S(j)和R中除R(i)外的其他元組所組成的連接元組*/ki+1;While(kn)and(R(k)[A]=S(j)[B])do{輸出<R(k),S(j)>至T;kk+1;}ii+1,jj+1;}}

問題：等值匹配對使用排序歸并法進行連接操作的效率有什么影響？

p個

q個

R.A2S.B2222222

.

.

.

.

.

.

注意等值的掃描次數（假設pq）：[1+(q-1)+(p-1)]+[1+(q-2)+(p-2)]+…+[1+(q-p)+(p-p)]=[(p+q-1)+(p+q-2q+1)]/2*p=p*qO(pq)4).散列連接法連接屬性R.A和S.B應具有相同的值域，用相同的散列函數，把R和S散列到同一散列文件中。符合連接條件的元組必然在同一通中（注意：同一桶中的元組未必都滿足連接條件）。只需把桶中的匹配元組取出即可獲得連接結果。關鍵在于建立一個供連接用的散列文件。可以在桶（散列文件）中不填入R、S的實際元組，而是代之以元組的tid，從而大大的縮小散列文件，使其有可能在內存中建立，而僅需對R、S各掃描一次。建立散列文件需要對R、S各掃描一次，且關系R和S一般不會對連接屬性進行簇集。故而，每向散列文件加入一個元組，都需要一次I/O操作。如何減少I/O次數?掃描R和S時，取出A(R)、B(S)，附在相應的tid后，連接時以桶為單位，按A(R)=B(S)找出匹配元組的tid對。問題：似乎多此一舉！匹配元組的tid一定在同一桶中！為什么還要按A(R)=B(S)找出匹配元組？這么做有必要么？注意：A=Bh(A)=h(B)，但不一定有：h(A)=h(B)A=B在取實際元組時，為減少物理塊訪問，可將各桶中，匹配元組的tid按塊分類，一次集中取出同一塊中所需的所有元組，當然這需要較大的內存開銷。連接方法的啟發(fā)式規(guī)則 1）兩個關系都已按連接屬性排序，則優(yōu)先用排序歸并法；兩個關系中已有一個關系按連接屬性排序，另一個關系較小，也可先對未排序關系按連接屬性排序，再用排序歸并法。2）兩個關系中有一個關系在連接屬性上有索引（特別是簇集索引）或散列，可以另一關系為外關系，順序掃描，并利用內關系上的索引或散列尋找其匹配元組，以代替多遍掃描。3）不具備上述條件且關系較小，可用嵌套循環(huán)法。4）不具備1，2，3規(guī)則，可用散列連接法。6.3.3投影操作的實現一般與選擇、連接同時進行，無需附加的I/O開銷。若投影屬性集中不包含主鍵，則投影結果中可能出現重復元組。消除重復元組可以用排序或散列等方法。

散列法：將投影結果按某一屬性