查詢處理和優(yōu)化.ppt

第6章 查詢處理和優(yōu)化,6.1 引言,查詢處理,查詢優(yōu)化,查詢優(yōu)化是查詢處理中的重要一環(huán)，對(duì)關(guān)系 DB尤其如此。, 從查詢語(yǔ)句出發(fā)，到獲得查詢結(jié)果的處理過(guò)程。, DBMS對(duì)描述性語(yǔ)言表達(dá)的查 詢語(yǔ)句進(jìn)行分析，為其確定合理、有效的執(zhí)行 策略和步驟的過(guò)程。,例如：12+64+88=？,查詢優(yōu)化是相對(duì)而言的，可能的執(zhí)行策略很多，窮盡代價(jià)很大，不能片面追求絕對(duì)的最優(yōu)。,（12+88）+64=164,數(shù)據(jù)庫(kù)查詢語(yǔ)言的處理過(guò)程:,（1）解釋方式執(zhí)行,優(yōu)化占執(zhí)行時(shí)間！,查詢語(yǔ)句,(2)編譯方式, CALL AM(參數(shù)) ,優(yōu)化不 占執(zhí)行時(shí)間！,對(duì)于常見(jiàn)的例行事務(wù)，編譯方式可提高性能。,對(duì)于簡(jiǎn)短的即時(shí)查詢，解釋方式靈活實(shí)用。,解釋方式和編譯方式各適用于什么情況？,代數(shù)優(yōu)化 對(duì)查詢語(yǔ)句進(jìn)行變換不涉及存取路徑 物理優(yōu)化 根據(jù)存取路徑選擇合理的存取策略進(jìn)行優(yōu)化 規(guī)則優(yōu)化 僅根據(jù)啟發(fā)式規(guī)則選擇執(zhí)行的策略進(jìn)行優(yōu)化 代價(jià)估算優(yōu)化,6.2 代數(shù)優(yōu)化,代數(shù)優(yōu)化對(duì)查詢進(jìn)行等效變換，以減少執(zhí)行開銷。,代數(shù)優(yōu)化的原則是盡量減小查詢過(guò)程中間結(jié)果的大小。,選擇、投影操作通常能夠有效地減小關(guān)系的大小。 連接、迪卡爾乘積和并操作容易生成較大的查詢中間結(jié)果。,因此，先做選擇、投影；先做小關(guān)系間的連接，再做大關(guān)系的連接；甚至需要先找出查詢中的公共表達(dá)式，以避免重復(fù)運(yùn)算。,常用變換規(guī)則,1.,2.,3.,4.,6.,7.,8.,9.,10.,注意：規(guī)則11中，對(duì)于連接運(yùn)算，可能出現(xiàn)S與T之間無(wú)連接條件的情況，此時(shí)的連接運(yùn)算成為迪卡爾乘積。,11.,范例p118例6-1,設(shè)有S(供應(yīng)商)，P(零件)，SP(供應(yīng)關(guān)系)三個(gè)關(guān)系，關(guān)系模式如下： S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) SP(SNUM,PNUM,DEPT,QUAN),有如下查詢 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,SQL語(yǔ)句轉(zhuǎn)化為原始查詢樹 Select From Where,Q可用右圖所示的原始查詢樹表示：,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,選擇操作下壓,選擇操作盡量下壓,原始查詢樹,先連接小關(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|,消除對(duì)查詢無(wú)用的屬性,消除對(duì)查詢無(wú)用的屬性,代數(shù)優(yōu)化的基本步驟： 1.以SELECT子句對(duì)應(yīng)投影操作，以FROM字句對(duì)應(yīng)迪卡爾乘積， 以WHERE子句對(duì)應(yīng)選擇操作，生成原始查詢樹。 2.應(yīng)用變換規(guī)則2)、6)、7)、9)、10)，盡可能將選擇條件移向樹葉方向。 3.應(yīng)用連接、迪卡爾乘積的結(jié)合律，按照小關(guān)系優(yōu)先做的原則， 重新安排連接（笛卡爾乘積）的順序。 4.如果笛卡爾乘積后還須按連接條件進(jìn)行選擇操作可將兩者組 合成連接操作。 5.對(duì)每個(gè)葉節(jié)點(diǎn)加必要的投影操作，以消除對(duì)查詢無(wú)用的屬性。,以上所討論的都是非嵌套查詢。嵌套查詢比較復(fù)雜， 分如下兩種情況： 1.嵌入的查詢塊與上層查詢無(wú)關(guān),從最低層查詢開始，用上述步驟和規(guī)則，逐層計(jì)算各查詢快所等效的關(guān)系，直至求出查詢結(jié)果。,2.嵌入的查詢塊與上層查詢有關(guān),一般用代入法。,例如： SELECT A1 FROM R1 WHERE R1.A2 比較符 CONST1 AND R1.A3 IN (SELECT A4 FROM R2 WHERE R2.A5 比較符 R1.A1),存在什么問(wèn)題？能否再進(jìn)行優(yōu)化？,注意：采用代入法時(shí)，盡可能作“部分選擇”！,SELECT A1,FROM R1 WHERE R1.A2 比較符 CONST1 AND,R1.A3 IN (SELECT A4 FROM R2 WHERE R2.A5 比較符 R1.A1),FROM R1 WHERE R1.A2 比較符 CONST1 AND,看作臨時(shí)表R1,將R1的每個(gè)元組逐個(gè)代入，檢查限制條件是否滿足，以減少需檢查的上層查詢所涉及表的元組數(shù)目！,有些DBMS將嵌套查詢轉(zhuǎn)換為等效的非嵌套查詢，但是這種方法不一定在所有情況下都可行。,6.3 依賴于存取路徑的規(guī)則優(yōu)化,代數(shù)優(yōu)化不涉及存取路徑，對(duì)各種操作的執(zhí) 行策略無(wú)從選擇。只能在操作的次序和組合上做 一些變換和調(diào)整。 單靠代數(shù)優(yōu)化比較粗糙，優(yōu)化效果有限，合 理選擇存取路徑，往往能收到顯著的效果。,本節(jié)結(jié)合存取路徑的分析，討論各種基本操作執(zhí)行的策略及其選擇原則。,6.3.1 選擇操作的實(shí)現(xiàn)和優(yōu)化,選擇條件： 等值 = 范圍 , 集合 IN,EXISTS,NOT EXISTS 復(fù)合 AND,OR,選擇操作的執(zhí)行策略與選擇條件、可用的存取路徑以及選取的元組數(shù)在整個(gè)關(guān)系中所占的比例有關(guān)。,實(shí)現(xiàn)方法：順序掃描、盡量利用散列索引等方法。,選擇操作選擇存取路徑的啟發(fā)式規(guī)則：,（1） 對(duì)于小關(guān)系，順序掃描。,（2） 若無(wú)索引、散列等存取路徑可用，或估計(jì)選取的元組數(shù)占關(guān)系的比例較大（大于20%）且有關(guān)屬性上無(wú)簇集索引，順序掃描。,（3） 對(duì)于主鍵的等值選擇，優(yōu)先選用主鍵的索引或散列。,（4） 對(duì)于非主鍵的等值選擇，若選取的元組數(shù)占關(guān)系的比例較小（小于20%），可以用無(wú)序索引；否則只能用簇集索引或順序掃描。（為什么？）,（5）.對(duì)于范圍條件，先通過(guò)索引找到范圍的邊界，再通過(guò)索引的順序集沿相應(yīng)方向搜索，如中選的元組數(shù)在關(guān)系中所占比例較大，宜采用簇集索引或順序掃描。,（6）對(duì)于用AND連接的合取選擇條件：,優(yōu)先選用多屬性索引,若有多個(gè)可用的次索引，可用預(yù)查找處理，最后做其余條件檢查,個(gè)別條件可用（3）（4）（5）之一，求得相應(yīng)組，再將這些元組用其它條件篩選,順序掃描,（7）用OR連接的析取選擇條件，尚無(wú)好的方法。只能按其中各個(gè)條件分別選出一個(gè)元組集，再求這些元組集的并。,在OR連接的諸條件中，只要有一個(gè)條件無(wú)合適的存取路徑，就只能用順序掃描！,6.3.2 連接操作的實(shí)現(xiàn)和優(yōu)化,連接開銷較大，為查詢優(yōu)化的重點(diǎn)，這里主要討論二元連接（Two Way Join）。,實(shí)現(xiàn)方法 1.嵌套循環(huán)法（nested loop） 2.利用索引或散列尋找匹配元組法 3.排序歸并 4.散列連接法,1).嵌套循環(huán),關(guān)系R與S進(jìn)行連接操作，最原始的辦法是取R的一個(gè)元組，與S的所有元組比較，凡是滿足連接條件的元組就進(jìn)行連接并且作為結(jié)果輸出。然后再取R的下一個(gè)元組，和S的所有元組比較，直到R的所有元組比較完為止。,i,j,嵌套循環(huán)算法,/*設(shè)R有n個(gè)元組，S有m個(gè)元組*/ i:=1,j:=1; while(in) dowhile(jm) doif R(i)A = S(j)B then 輸出至T; j := j + 1 j:=1,i:=i+1 ,T為R和S連接的結(jié)果,R為外關(guān)系（outer relation）,S為內(nèi)關(guān)系（inner relation）。,事實(shí)上，關(guān)系是以物理塊為單位取到內(nèi)存，設(shè)R和S各有一緩沖塊， PR為R的塊因子（每塊中所含的元組數(shù)）。則R每次I/O取PR個(gè)元組，可改進(jìn)上述算法，使S掃描一次可以與R的PR個(gè)元組比較，那么S的掃描次數(shù)為bR=n/PR 。,物理塊,物理塊,假設(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)行連接所需訪問(wèn)的物理塊數(shù)為bR+bR/(nB-1)*bS，對(duì)應(yīng)最小I/O值。,問(wèn)題：增加外關(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)分配策略？,問(wèn)題：嵌套循環(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ù)。,問(wèn)題：若在內(nèi)關(guān)系的連接屬性上建有索引？是否一定能夠提高內(nèi)關(guān)系和外關(guān)系的匹配效率？,當(dāng)每次循環(huán)所選的匹配元組數(shù)在內(nèi)關(guān)系中占有較大比例（例如超過(guò)15%）時(shí)，用無(wú)序索引甚至還不如用順序掃描的方法。內(nèi)關(guān)系的連接屬性上有簇集索引時(shí)，索引對(duì)減少連接所需I/O次數(shù)的作用最明顯。,3).排序歸并,如果R和S按連接屬性排序，可按序比較R.A和S.B以找出匹配元組。,跳過(guò),跳過(guò),跳過(guò),算法：,R按屬性A排序 /*設(shè)R有n個(gè)元組*/ S按屬性B排序 /*設(shè)S有m個(gè)元組*/,i1,j1; While(in)and(j m) doif R(i)AS(j)B then jj+1 else if R(i)AS(j)B then ii+1 else /* R(i)A=S(j)B，輸出連接元組*/,輸出至T; /*輸出R(i)和S中除S(j)外的其他元組所組成的連接元組 */ lj+1; While(lm) and (R(i)A=S(l)B) do輸出至T; ll+1; /*輸出S(j)和R中除R(i)外的其他元組所組成的連接元組 */ ki+1; While(kn) and (R(k)A=S(j)B) do輸出至T; kk+1; ii+1,jj+1; ,注意等值的掃描次數(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*q O(pq),4).散列連接法,連接屬性R.A和S.B應(yīng)具有相同的值域，用相同的散列函數(shù)，把R和S散列到同一散列文件中。符合連接條件的元組必然在同一通中（注意：同一桶中的元組未必都滿足連接條件）。只需把桶中的匹配元組取出即可獲得連接結(jié)果。,關(guān)鍵在于建立一個(gè)供連接用的散列文件。,可以在桶（散列文件）中不填入R、S的實(shí)際元組，而是代之以元組的tid，從而大大的縮小散列文件，使其有可能在內(nèi)存中建立，而僅需對(duì)R、S各掃描一次。,建立散列文件需要對(duì)R、S各掃描一次，且關(guān)系R和S一般不會(huì)對(duì)連接屬性進(jìn)行簇集。故而，每向散列文件加入一個(gè)元組，都需要一次I/O操作。,如何減少I/O次數(shù)?,掃描R和S時(shí)，取出A(R)、B(S)，附在相應(yīng)的tid后，連接時(shí)以桶為單位，按A(R)=B(S)找出匹配元組的tid對(duì)。,問(wèn)題：似乎多此一舉！匹配元組的tid一定在同一桶中！為什么還要按A(R)=B(S)找出匹配元組？這么做有必要么？,注意：A=B h(A)=h(B)，但不一定有： h(A)=h(B) A=B,在取實(shí)際元組時(shí)，為減少物理塊訪問(wèn)，可將各桶中，匹配元組的tid按塊分類，一次集中取出同一塊中所需的所有元組，當(dāng)然這需要較大的內(nèi)存開銷。,連接方法的啟發(fā)式規(guī)則,1）兩個(gè)關(guān)系都已按連接屬性排序，則優(yōu)先用排序歸并法； 兩個(gè)關(guān)系中已有一個(gè)關(guān)系按連接屬性排序，另一個(gè)關(guān)系較 小，也可先對(duì)未排序關(guān)系按連接屬性排序，再用排序歸并 法。 2）兩個(gè)關(guān)系中有一個(gè)關(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),一般與選擇、連接同時(shí)進(jìn)行，無(wú)需附加的 I/O開銷。,若投影屬性集中不包含主鍵，則投影結(jié)果中 可能出現(xiàn)重復(fù)元組。,消除重復(fù)元組可以用排序或散列等方法。,散列法：將投影結(jié)果按某一屬性或多個(gè)屬性散列成一個(gè)文件，當(dāng)一個(gè)元組被散列到一個(gè)桶中時(shí)，可檢查是否與桶中已有元組重復(fù)。,用排序法消除重復(fù)元組,對(duì)關(guān)系R的每個(gè)元組t，生成t，并存于T中；/* T 是未消除重復(fù)元組的投影結(jié)果*/ If 含有R的主鍵 then TT elseT按所有屬性排序； i1,j2; while(in) do輸出元組T(i)到T;,while T(i)= T(j) do jj+1; /*消除重復(fù)元組，設(shè)有偽元組Tn+1Tn*/ ij,ji+1; ,6.3.4 集合操作,常用集合操作：笛卡爾乘積、并、交、差等。,設(shè)關(guān)系R、S并兼容，對(duì)R、S進(jìn)行并（交、差）操作，可以先將R和S按同一屬性（通常選用主鍵）排序，然后掃描兩個(gè)關(guān)系，選出所需的元組。,笛卡爾乘積將兩個(gè)關(guān)系的元組無(wú)條件地互相拼接，一般用嵌套循環(huán)法實(shí)現(xiàn)，做起來(lái)很費(fèi)時(shí)，結(jié)果要比參與運(yùn)算的關(guān)系大的多。應(yīng)盡量少用！,散列是上述并交差操作的另一種求解方法： 將關(guān)系R散列到一個(gè)散列文件中，再將S散列到同一文件中。同時(shí)檢查桶中有無(wú)重復(fù)元組。對(duì)于并，不再插入重復(fù)元組；對(duì)于交，選取重復(fù)元組；對(duì)于差，從桶中取消與S重復(fù)的元組。,6.3.5 組合操作,有時(shí)，多個(gè)操作組合起來(lái)同時(shí)進(jìn)行，如投影和選擇操作組合起來(lái)執(zhí)行（消除重復(fù)元組另外單獨(dú)進(jìn)行），可提高效益。 還