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

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

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

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

BEGINTRAN查詢語句END應(yīng)用程序

…CALLAM(參數(shù))…AM依賴因素訪問模塊AM預(yù)編譯編譯和連接目標(biāo)碼執(zhí)行優(yōu)化不占執(zhí)行時間?。τ诔Ｒ姷睦惺聞?wù)，編譯方式可提高性能。對于簡短的即時查詢，解釋方式靈活實(shí)用。解釋方式和編譯方式各適用于什么情況？代數(shù)優(yōu)化對查詢語句進(jìn)行變換不涉及存取路徑物理優(yōu)化根據(jù)存取路徑選擇合理的存取策略進(jìn)行優(yōu)化規(guī)則優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

R.A2S.過

跳過

算法：R按屬性A排序/*設(shè)R有n個元組*/S按屬性B排序/*設(shè)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;}}

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

p個

q個

R.A2S.B2222222

.

.

.

.

.

.

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

散列法：將投影結(jié)果按某一屬性