第9章 9.3 代數(shù)優(yōu)化.ppt

1、第九章 關(guān)系查詢處理及其查詢優(yōu)化,9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 9.5 小 結(jié),RDBMS查詢處理步驟,9.3 代 數(shù) 優(yōu) 化,要解決兩個(gè)問題： 如何構(gòu)造查詢樹（語法分析樹）？ 如何進(jìn)行代數(shù)優(yōu)化？依據(jù)（規(guī)則）是什么？ 代數(shù)優(yōu)化： 是指關(guān)系代數(shù)表達(dá)式的優(yōu)化。各種關(guān)系查詢語言都可以等價(jià)地 轉(zhuǎn)換為關(guān)系代數(shù)表達(dá)式，因此關(guān)系代數(shù)表達(dá)式的優(yōu)化是查詢優(yōu) 化的基本課題 代數(shù)優(yōu)化策略：通過對關(guān)系代數(shù)表達(dá)式的等價(jià)變換來提高查詢效率,9.3.1 查詢優(yōu)化的一般準(zhǔn)則,選擇運(yùn)算應(yīng)盡可能先做 在優(yōu)化策略中這是最重要、最基本的一條。 在執(zhí)行連接前對關(guān)

2、系適當(dāng)?shù)仡A(yù)處理（建立索引，排序） 預(yù)處理方法主要有兩種： 第一種稱為索引連接方法。在連接屬性上建立索引，然后執(zhí)行連接。 第二種稱為排序合并連接方法。將關(guān)系中元組按某個(gè)值排序，然后執(zhí)行連接 將投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行 如有若干投影和選擇運(yùn)算，并且它們都對同一個(gè)關(guān)系操作，則可以在掃描此關(guān)系的同時(shí)完成所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系,9.3.1 查詢優(yōu)化的一般準(zhǔn)則,將投影同其前或其后的雙目運(yùn)算結(jié)合起來，減少掃描關(guān)系的次數(shù) 將某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個(gè)連接運(yùn)算，連接運(yùn)算比笛卡爾積省很多時(shí)間 找出公共子表達(dá)式： 如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系并且從外存中讀入這個(gè)

3、關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少得多，則先計(jì)算一次公共子表達(dá)式并把結(jié)果寫入中間文件是合算的 定義視圖的表達(dá)式就是公共子表達(dá)式的情況,9.3.2 關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則,關(guān)系代數(shù)表達(dá)式的等價(jià)：指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的 兩個(gè)關(guān)系表達(dá)式E1和E2是等價(jià)的，可記為E1E2 常用的等價(jià)變換規(guī)則： 1）連接、笛卡爾積的交換律 設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式 F是連接運(yùn)算的條件 2）連接、笛卡爾積的結(jié)合,9.3.2 關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則,3）投影的串接 4）選擇的串接 5）選擇與投影的交換 6）選擇與笛卡爾積的交換,9.3.2 關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則,7)選

4、擇與并的交換 8）選擇與差的交換 9）投影與笛卡爾積的交換 10）投影與并的交換,9.3.3 關(guān)系代數(shù)表達(dá)式的優(yōu)化步驟,1、構(gòu)造查詢樹 第一步：把用高級語言定義的查詢轉(zhuǎn)換為關(guān)系代數(shù)表達(dá)式。 以SELECT子句對應(yīng)投影操作，以FROM字句對應(yīng)笛卡爾積，以WHERE子句對應(yīng)選擇操作，生成原始查詢樹。 SQL語句轉(zhuǎn)化為原始查詢樹,9.3.3 關(guān)系代數(shù)表達(dá)式的優(yōu)化步驟,第二步：把關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換為查詢樹。 查詢樹是一種表示關(guān)系代數(shù)表達(dá)式的樹形結(jié)構(gòu)。在一個(gè)查詢樹中，葉子結(jié)點(diǎn)表示關(guān)系，內(nèi)結(jié)點(diǎn)表示關(guān)系代數(shù)操作。查詢樹以自底向上的方式執(zhí)行：當(dāng)一個(gè)內(nèi)結(jié)點(diǎn)的操作分量可用時(shí)，這個(gè)內(nèi)結(jié)點(diǎn)所表示的操作啟動(dòng)執(zhí)行，執(zhí)行結(jié)

5、束后用結(jié)果關(guān)系代替這個(gè)內(nèi)結(jié)點(diǎn)。 例 給定一個(gè)用SQL語言定義的查詢： SELECT A FROM R1,R2,R3 WHERE P=15 AND N=“User”,A(P=15 AND N=User(R1R2R3),9.3.3 關(guān)系代數(shù)表達(dá)式的優(yōu)化步驟,2、利用等價(jià)轉(zhuǎn)換規(guī)則反復(fù)地對查詢表達(dá)式進(jìn)行嘗試性轉(zhuǎn)換，將原始的語法樹轉(zhuǎn)換成“優(yōu)化”的形式 利用等價(jià)變換規(guī)則4把形如F1F2Fn(E)變換為 F1(F2(Fn(E)。目的是使選擇操作可以靈活方便地沿查詢樹下移 對每一個(gè)選擇，利用等價(jià)變換規(guī)則49盡可能把它移到樹的葉端。目的是使選擇操作盡早執(zhí)行 對每一個(gè)投影利用等價(jià)變換規(guī)則3，9等的一般形式盡可能把

6、它移向樹的葉端。目的是使投影操作盡早執(zhí)行 對每個(gè)葉節(jié)點(diǎn)加必要的投影操作，以消除對查詢無用的屬性。 如果笛卡爾乘積后還須按連接條件進(jìn)行選擇操作可將兩者組 合成連接操作。,9.3.3 關(guān)系代數(shù)表達(dá)式的優(yōu)化步驟,把上述得到的“優(yōu)化”后的語法樹的內(nèi)節(jié)點(diǎn)分組。 每一雙目運(yùn)算（，-）和它所有的直接祖先為一組（這些直接祖先是，運(yùn)算）。 如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組。 生成一個(gè)查詢代碼，每組結(jié)點(diǎn)的計(jì)算是程序中的一步(即每一步計(jì)算一個(gè)子樹)。各步的順序是任意的，只要保證任何一組的計(jì)算不會(huì)在它的后代組之前計(jì)算。,9.3.4 查詢優(yōu)化實(shí)例,設(shè)有S(供應(yīng)商)，P(零件)，SP(供應(yīng)關(guān)系)三個(gè)關(guān)系

7、，關(guān)系模式如下： S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) SP(SNUM,PNUM,DEPT,QUAN),有如下語義查詢：查詢來自南京的供應(yīng)數(shù)量大于10000的bolt零件的供應(yīng)商的名稱。 1、SQL語句： 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,9.3.4 查詢優(yōu)化實(shí)例,2、構(gòu)造查詢樹,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,9.3.4 查詢優(yōu)化實(shí)例,選擇操作盡量下移,原始查詢樹,9.3.4 查詢優(yōu)化實(shí)例,消除對查詢無用的屬性,優(yōu)化算法練習(xí),學(xué)生-課程關(guān)系數(shù)據(jù)庫中包括以下關(guān)系模式： S（S#，Sname，Age，Sex） SC（S#，C#，