數據庫系統原理第四章關系系統的查詢優化4.1關系系統4.2查詢優化處理數據庫系統原理

第四章關系系統的查詢優化學習要求

了解關系系統的基本概念及分類標準，初步了解查詢處理的基本步驟，理解查詢優化的意義，掌握關系代數優化的算法及相應的等價變換。學習重點

利用關系優化規則對關系語法樹進行優化。

數據庫系統原理第四章關系系統的查詢優化

4.1關系系統4.2查詢優化處理數據庫系統原理第一節關系系統關系模型關系數據結構域及域上定義的關系關系操作關系代數：并、交、差、廣義笛卡爾積、選擇、投影、連接、除等關系完整性實體完整性、參照完整性、用戶自己定義的完整性關系系統的查詢優化關系系統(續)關系系統的定義能夠在一定程度上支持關系模型的數據庫管理系統是關系系統。定義4.1

一個系統是關系系統當且僅當它：支持關系數據庫（即關系數據結構）。從用戶觀點看，數據庫是由表構成的，并且系統中只有表這種結構。支持選擇、投影和（自然）連接運算。對這些運算不要求用戶定義任何物理存取路徑。關系系統的查詢優化二、關系系統的分類分類依據─依據關系系統支持關系模型的程度不同。分類S：結構I：完整性M：數據操縱關系系統的查詢優化數據結構數據操縱數據完整性表式結構表××最小關系系統表選擇、投影、連接×關系完備的系統表全部×全關系系統全部全部完全支持關系系統的分類（續）關系系統的查詢優化第二節關系系統的查詢優化關系系統的查詢處理查詢優化概述查詢優化問題的提出關系代數的優化規則關系代數的優化算法查詢優化的一般步驟關系系統的查詢優化一、關系系統的查詢處理1、查詢處理步驟關系系統的查詢優化查詢語句轉化成關系代數表達式關系系統的查詢處理（續）2、實現查詢操作的算法示例例4.1選擇操作的實現Select*FromStudentWhere<條件表達式>;<條件表達式>的幾種情況：C1:Sno=‘95001’C2:Sage<20C3:Sdept=‘CS’AndSage>20①簡單的全表掃描方法對查詢的基本表順序掃描，逐一檢查每個元組是否滿足選擇條件，把滿足條件的元組作為結果輸出。關系系統的查詢優化

選擇操作的實現示例（續）②索引掃描方法

通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組。

【C1例】Sno=’95001’，并且在Sno上有索引，則可以使用索引得到Sno為’95001’元組的指針，然后通過元組指針在Student表中檢索到該學生。

【C2例】Sage>20，并且Sage上有B+樹索引，則可以使用B+樹索引找到Sage=20的索引項，以此為入口點在B+樹的順序集上得到Sage>20的所有元組指針，然后通過這些元組指針到Student表中檢索到所有年齡大于20的學生。關系系統的查詢優化Sage>20的一組元組指針【C3例】Sdept=‘CS’AndSage>20，如果Sdept和Sage上都有索引，則：

另一種算法：關系系統的查詢優化

選擇操作的實現示例（續）Sdept=‘CS’的一組元組指針Sdept=‘CS’的一組元組指針Sdept=‘CS’的一組元組指針Sage>20的一組元組指針指針交集滿足條件的學生信息Student表Student表Sage>20的一組元組指針滿足條件的學生信息滿足Sdept=‘CS’條件的元組信息實現查詢操作的算法示例（續）例4.2連接操作的實現

Select*FromStudent,SCWhereStudent.Sno=SC.Sno①嵌套循環方法

關系系統的查詢優化學號Sno姓名Sname性別Ssex年齡Sage所在系Sdept95002950019500395004李勇劉晨王敏張立男女女男20191819CSISMAISStudent學號Sno課程號Cno成績Grade9500195002950019500295002123239290888580SC對Student中的每一個元組，檢查SC中的每一個元組，若在連接屬性上相等，則連接輸出，直到Student中的元組處理完為止。連接操作的實現（續）②排序-合并方法學號Sno姓名Sname性別Ssex年齡Sage所在系Sdept95001950029500395004李勇劉晨王敏張立男女女男20191819CSISMAISStudent學號Sno課程號Cno成績Grade9500195001950019500295002123239285889080SC關系系統的查詢優化取Student表中第一個Sno，依次掃描SC表中具有相同Sno的元組，把他們連接起來；當掃描到Sno不相同的第一個SC元組時，返回Student表掃描它的下一個元組，再掃描SC表中具有相同Sno的元組，把它們連接起來。二、查詢優化概述

查詢優化是從眾多可供選擇的執行策略和操作算法中，選擇一個高效執行的查詢處理策略。

按照優化的層次可以分為代數優化和物理優化。代數優化：是指關系代數表達式的優化，按照一定的規則，改變代數表達式中操作的次序和組合，使查詢執行效率更高。物理優化：則是指存取路徑和底層操作算法的選擇。關系系統的查詢優化查詢優化概述（續）目前RDBMS通過某種代價模型計算出各種查詢執行策略的執行代價，然后選取代價最小的執行方案。查詢的執行開銷主要包括集中式數據庫磁盤存取塊數（I/O代價）處理機時間（CPU代價）查詢的內存開銷分布式數據庫I/O代價+CPU代價+內存代價+通信代價查詢優化的總目標選擇有效策略，求得給定關系表達式的值，使得查詢代價最小。關系系統的查詢優化三、查詢優化問題的提出例4.3：求選修了2號課程的學生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.SnoANDSC.Cno='2';系統可以用多種等價的關系代數表達式來完成這一查詢。

關系系統的查詢優化查詢優化問題的提出（續）假設1外存：

Student表中有1000條學生記錄

SC表中有10000條選課記錄 其中選修2號課程的選課記錄為50條假設2內存： 一個內存塊可以裝10個Student元組或100個SC元組 一個內存塊可以裝10個Student和SC的連接結果元組 內存中一次可以存放5塊Student元組、1塊SC元組和若干塊連接結果元組假設3讀寫速度：20塊/秒假設4連接方法：基于數據塊的嵌套循環法關系系統的查詢優化1、第一種方法關系系統的查詢優化查詢優化問題的提出（續）

內存塊100Student表SC表…………內存塊1內存塊2內存塊3內存塊4內存塊5一般連接的方法：內存塊1內存塊2內存塊100讀Student表100塊，讀SC表20遍，每遍100塊。①計算廣義笛卡爾集Student×SC讀取總塊數=讀Student表塊數+讀SC表遍數*每遍塊數

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100讀數據時間=2100/20=105秒中間結果大小（連接后的元組數）=1000*10000=107

(1千萬條元組)寫中間結果時間=10000000/10/20=50000秒②選擇操作讀數據時間=50000秒

③投影操作

總時間=105＋50000＋50000秒=100105秒=27.8小時關系系統的查詢優化第一種方法（續）2、第二種方法①計算自然連接

讀取總塊數=2100塊

讀數據時間=2100/20=105秒 中間結果大小=10000（減少1000倍） 寫中間結果時間=10000/10/20=50秒

②選擇操作

讀取中間文件塊，執行選擇運算，花費時間50秒

③投影操作

把第二步的結果投影輸出

總時間＝(105＋50＋50)秒＝205秒=3.4分

關系系統的查詢優化查詢優化問題的提出（續）3、第三種方法Q3=πSname(Student

SC.Cno=‘2’(SC))①選擇操作

讀SC表總塊數=10000/100=100塊 讀數據時間=100/20=5秒

中間結果大小=50條（滿足條件的元組只有50個），不必使用中間文件。②自然連接操作 讀Student表總塊數=1000/10=100塊（只需讀一遍該表） 讀數據時間=100/20=5秒

③投影操作

把連接結果投影輸出。

總時間＝5＋5秒＝10秒關系系統的查詢優化查詢優化問題的提出（續）四、關系代數的優化規則關系代數優化策略是通過對關系代數表達式的等價變換來提高查詢效率。關系代數表達式等價指把相同的關系代入兩個關系代數表達式所得到的結果是相同的。兩個關系表達式E1和E2是等價的，記為E1≡E2。關系系統的查詢優化關系代數的優化規則（續）1、常用的等價變換規則設E1、E2是關系代數表達式，F是條件表達式。（1）連接、笛卡爾積交換律E1×E2≡E2×E1

E1E2≡E2E1E1E2≡E2E1（2）連接、笛卡爾積的結合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

關系系統的查詢優化FFF1F1F2F2常用的等價變換規則（續）（3）投影的級聯（串接定律）假設：

1)E是關系代數表達式

2)Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名

3){A1,A2,…,An}是{Bl，B2，…，Bm}的子集。則：（4）選擇的級聯（串接定律）選擇的串接律說明選擇條件可以合并。關系系統的查詢優化關系代數等價變換規則（續）（5）選擇與投影的交換律假設:選擇條件F只涉及屬性A1，…，An假設:F中有不屬于A1,…,An的屬性B1,…,Bm

關系系統的查詢優化關系代數等價變換規則（續）（6）選擇與笛卡爾積的交換律假設：F中涉及的屬性都是E1中的屬性，則

假設：F=F1∧F2，并且F1只涉及E1中的屬性，F2只涉及E2中的屬性，則由上面的等價變換規則1，4，6可推出 假設：F=F1∧F2，F1只涉及E1中的屬性，F2涉及E1和E2兩者的屬性，則

關系系統的查詢優化F

(

E1×E2)≡F1∧F2(E1×E2)≡F2

(F1

(E1×E2))

≡F2

(F1

(E1)×E2)F

(

E1×E2)≡F1∧F2(E1×E2)≡F1

(F2

(E1×E2))

≡F1

(F2

(E2)×E1)

≡F1

(E1)×F2

(E2)

關系代數等價變換規則（續）（7）選擇與并的分配律 假設：E=E1∪E2，E1，E2有相同的屬性名

（8）選擇與差運算的分配律 假設：E1與E2有相同的屬性名（9）選擇對自然連接的分配律

假設：F只涉及E1和E2的公共屬性

F(E1

E2)≡F(E1)F(E2)

關系系統的查詢優化關系代數等價變換規則（續）（10）投影與笛卡爾積的分配律 假設：E1和E2是兩個關系表達式，A1，…，An是E1的屬性，B1，…，Bm是E2的屬性，則（11）投影與并的分配 假設：E1和E2

有相同的屬性名，則

關系系統的查詢優化關系代數等價變換規則小結1-2:連接、笛卡爾積的交換律、結合律3：投影運算的合并或分解4：選擇運算的合并或分解5-6：選擇運算與其他運算的交換律7-9：選擇運算與其他運算的分配律10-11：投影運算與其他運算的分配律關系系統的查詢優化2、關系代數的優化規則（1）選擇運算應盡可能先做。目的：減少中間結果大小（2）投影運算和選擇運算同時做。目的：避免重復掃描關系（3）將投影運算與其前面或后面的雙目運算結合。目的：減少掃描關系的遍數。關系系統的查詢優化關系代數等價變換規則（續）查詢優化的一般準則（續）（4）把某些選擇同在它前面執行的笛卡兒積結合起來成為一個連接運算。例：Student.Sno=SC.Sno

(Student×SC)

StudentSC

例4.3中：關系系統的查詢優化（5）提取公共子表達式。一個關系表達式如果包含多個相同的子表達式，那么只需計算一次公共表達式，把所得的中間結果存起來，以后每遇到這種子表達式，只需檢索中間結果而無須重新計算。關系系統的查詢優化查詢優化的一般準則（續）五、關系代數的優化算法1、查詢樹在查詢優化過程中，查詢語句被轉換為更適合處理的內部表示，通常這種內部表示表現為查詢樹的形式，它的構造方法如下:（1）每一個葉節點對應于查詢中的基本關系;（2）非葉節點是關系代數運算產生的中間關系;（3）樹的根節點代表查詢結果;（4）運算按照從葉到根的順序執行。關系系統的查詢優化查詢樹（續）例4.3中的關系代數表達式：轉化為查詢樹：關系系統的查詢優化關系代數的優化算法（續）2、關系表達式的優化算法輸入：一個關系表達式的查詢樹。輸出：優化的查詢樹。方法：1．分解選擇運算。2．通過交換選擇運算，將其盡可能移到葉端。3．通過交換投影運算，將其盡可能移到葉端。4．合并串接的選擇和投影，以便能同時執行或在一次掃描中完成。5．對內結點分組。6．生成程序。關系系統的查詢優化關系代數的優化算法(續)（1）分解選擇運算。

利用規則4把形如F1∧F2∧…∧Fn(E)變換為

F1(F2(…(Fn(E))…))（2）通過交換選擇運算，將其每個選擇盡可能移到葉端。對每一個選擇，利用規則4～9盡可能把它移到樹的葉端。（3）通過交換投影運算，將其盡可能移到葉端。

對每一個投影利用規則3，5，l0，11中的一般形式盡可能把它移向樹的葉端。關系系統的查詢優化關系代數表達式的優化算法(續)（4）合并串接的選擇和投影，以便能同時執行或在一次掃描中完成。利用規則3～5把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執行,或在一次掃描中全部完成。盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。關系系統的查詢優化關系代數表達式的優化算法(續)（5）對內結點分組把上述得到的語法樹的內節點分組。每一雙目運算(×,,∪,-)和它所有的直接祖先（,π運算）為一組。如果其后代直到葉子全是單目運算，則也將它們并入該組，但當雙目運算是笛卡爾積(×)而且其后的選擇不能與它結合為等值連接時除外。把這些單目運算單獨分為一組。關系系統的查詢優化關系代數表達式的優化算法(續)（6）生成程序生成一個程序，每組結點的計算是程序中的一步。各步的順序是任意的，只要保證任何一組的計算不會在它的后代組之前計算。

關系系統的查詢優化例4.4給出例4.3中SQL語句的代數優化算法。（1）把SQL語句轉換成查詢樹，對應的關系表達式為：

關系系統的查詢優化關系代數表達式的優化算法(續)關系代數查詢樹關系系統的查詢優化關系代數表達式的優化算法(續)πSname

Student.Sno=SC.Sno

∧SC.Cno=2

×

StudentSC（2）對查詢樹進行優化①分解選擇運算，對應的關系代數表達式為:

Sname(σ

Student.Sno=SC.Sno(σ

SC.Cno=2

(Student×SC)));關系系統的查詢優化關系代數表達式的優化算法(續)πSname

SC.Cno=2

×

Stud