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

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

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

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

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

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

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

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