关系系统及其查询优化课件

關係系統及其查詢優化

關係系統能夠在一定程度上支持關係模型的資料庫管理系統是關係系統。由於關係模型中並非每一部分都是同等重要的並不苛求一個實際的關係系統必須完全支持關係模型。關係系統與關係模型關係數據結構域及域上定義的關係關係操作並、交、差、廣義笛卡爾積、選擇、投影、連接、除等關係完整性實體完整性、參照完整性、用戶自己定義的完整性關係系統的定義一個資料庫管理系統可定義為關係系統，當且僅當它至少支持：1.關係資料庫（即關係數據結構）系統中只有表這種結構2.支持選擇、投影和（自然）連接運算對這些運算不要求用戶定義任何物理存取路徑對關係系統的最低要求關係系統的定義不支持關係數據結構的系統顯然不能稱為關係系統僅支持關係數據結構，但沒有選擇、投影和連接運算功能的系統仍不能算作關係系統。原因：不能提高用戶的生產率支持選擇、投影和連接運算，但要求定義物理存取路徑，這種系統也不能算作真正的關係系統原因：就降低或喪失了數據的物理獨立性選擇、投影、連接運算是最有用的運算4.1.2關係系統的分類分類依據：支持關係模型的程度分類⒈表式系統：支持關係數據結構(即表)⒉(最小)關係系統支持：關係數據結構 選擇、投影、連接關係操作⒊關係完備的系統支持：關係數據結構 所有的關係代數操作⒋全關係系統支持：關係模型的所有特徵特別是:數據結構中域的概念

關係系統的分類（續）

數據結構數據操作完整性表式系統表

(最小)關係系統表選擇、投影、連接

關係完備的系統表

全關係系統

第四章關係系統及其查詢優化4.1關係系統4.2關係系統的查詢優化4.3小結4.2關係系統的查詢優化4.2.1查詢優化概述4.2.2查詢優化的必要性4.2.3查詢優化的一般準則4.2.4關係代數等價變換規則4.2.5關係代數運算式的優化演算法4.2.6優化的一般步驟4.2.1查詢優化概述查詢優化的必要性查詢優化極大地影響RDBMS的性能。

查詢優化的可能性關係數據語言的級別很高，使DBMS可以從關係運算式中分析查詢語義。由DBMS進行查詢優化的好處用戶不必考慮如何最好地表達查詢以獲得較好的效率系統可以比用戶程式的優化做得更好(1)優化器可以從數據字典中獲取許多統計資訊，而用戶程式則難以獲得這些資訊

由DBMS進行查詢優化的好處(2)如果資料庫的物理統計資訊改變了，系統可以自動對查詢重新優化以選擇相適應的執行計畫。在非關係系統中必須重寫程式，而重寫程式在實際應用中往往是不太可能的。(3)優化器可以考慮數百種不同的執行計畫，而程式員一般只能考慮有限的幾種可能性。(4)優化器中包括了很多複雜的優化技術查詢優化目標查詢優化的總目標選擇有效策略，求得給定關係運算式的值實際系統的查詢優化步驟1.將查詢轉換成某種內部表示，通常是語法樹2.根據一定的等價變換規則把語法樹轉換成標準（優化）形式實際系統的查詢優化步驟3.選擇低層的操作演算法對於語法樹中的每一個操作計算各種執行演算法的執行代價選擇代價小的執行演算法4.生成查詢計畫(查詢執行方案)查詢計畫是由一系列內部操作組成的。

代價模型

集中式資料庫單用戶系統

總代價=I/O代價+CPU代價多用戶系統

總代價=I/O代價+CPU代價+記憶體代價分佈式資料庫 總代價

=I/O代價+CPU代價[+記憶體代價]+通信代價4.2.2查詢優化的必要性例：求選修了課程Ｃ2的學生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';查詢優化的必要性（續）假設1：外存：

Student:1000條,SC:10000條,選修2號課程:50條假設2：一個記憶體塊裝元組:10個Student,或100個SC, 記憶體中一次可以存放:5塊Student元組,1塊SC元組和若干塊連接結果元組假設3：讀寫速度：20塊/秒假設4：連接方法：基於數據塊的嵌套迴圈法

執行策略1Ｑ1＝ПＳname(бStudent.Sno=SC.Sno

∧SC.Cno='2'

(Student×SC))

①Student×SC

讀取總塊數=讀Student表塊數+讀SC表遍數

*每遍塊數

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100

讀數據時間=2100/20=105秒不同的執行策略,考慮I/O時間

中間結果大小=1000*10000=107(1千萬條元組)

寫中間結果時間

=10000000/10/20=50000秒

②б

讀數據時間

=50000秒

③П總時間=105＋50000＋50000秒=100105秒

=27.8小時查詢優化的必要性（續）2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))

①

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

②б

讀數據時間=50秒

③П

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

查詢優化的必要性（續）3.Ｑ2＝ПSname(Student

бSC.Cno='2'(SC))

①б

讀SC表總塊數=10000/100=100塊

讀數據時間=100/20=5秒

中間結果大小=50條不必寫入外存

②

讀Student表總塊數=1000/10=100塊

讀數據時間=100/20=5秒

③П

總時間＝5＋5秒＝10秒查詢優化的必要性（續）4.Ｑ2＝ПＳname(Student

бSC.Cno='2'(SC))假設SC表在Cno上有索引，Student表在Sno上有索引

①б

讀SC表索引=

讀SC表總塊數=50/100<1塊 讀數據時間

中間結果大小=50條不必寫入外存查詢優化的必要性（續）②

讀Student表索引=

讀Student表總塊數=50/10=5塊 讀數據時間③П總時間<10秒4.2.3查詢優化的一般準則選擇運算應盡可能先做

目的：減小中間關係在執行連接操作前對關係適當進行預處理按連接屬性排序在連接屬性上建立索引

投影運算和選擇運算同時做目的：避免重複掃描關係將投影運算與其前面或後面的雙目運算結合目的：減少掃描關係的遍數查詢優化的一般準則（續）某些選擇運算＋在其前面執行的笛卡爾積

===>連接運算例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC提取公共子運算式4.2.4關係代數等價變換規則關係代數運算式等價指用相同的關係代替兩個運算式中相應的關係所得到的結果是相同的上面的優化策略大部分都涉及到代數運算式的變換

常用的等價變換規則

設E1、E2等是關係代數運算式，F是條件運算式

l.連接、笛卡爾積交換律

E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

關係代數等價變換規則（續）

2.連接、笛卡爾積的結合律

(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F

F

F

F關係代數等價變換規則（續）3.投影的串接定律

π

A1,A2,

,An(π

B1,B2,

,Bm(E))≡π

A1,A2,

,An(E)假設：1) E是關係代數運算式2) Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名3){A1,A2,…,An}構成{Bl，B2，…，Bm}的子集關係代數等價變換規則（續）4.選擇的串接定律

бF1

（б

F2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合併這樣一次就可檢查全部條件。關係代數等價變換規則（續）5.選擇與投影的交換律(1)假設:選擇條件F只涉及屬性A1，…，AnбF(πA1,A2,

,An(E))≡πA1,A2,

,An(бF(E))

(2)假設:F中有不屬於A1,…,An的屬性B1,…,Bmπ

A1,A2,

,An

(

бF

(E))≡

πA1,A2,

,An(бF

(πA1,A2,

,An,B1,B2,

,Bm(E)))關係代數等價變換規則（續）6.選擇與笛卡爾積的交換律(1)假設：F中涉及的屬性都是E1中的屬性

бF(E1×E2)≡бF(E1)×E2

(2)假設：F=F1∧F2，並且F1只涉及E1中的屬性，

F2只涉及E2中的屬性 則由上面的等價變換規則1，4，6可推出：

бF(E1×E2)≡бF1(E1)×бF2(E2)

關係代數等價變換規則（續）(3)假設：F=F1∧F2，

F1只涉及E1中的屬性，

F2涉及E1和E2兩者的屬性

бF(E1×E2)≡бF2(бF1(E1)×E2)

它使部分選擇在笛卡爾積前先做

關係代數等價變換規則（續）7.選擇與並的交換 假設：E=E1∪E2，E1，E2有相同的屬性名

бF(E1∪E2)≡бF(E1)∪бF(E2)

8.選擇與差運算的交換 假設：E1與E2有相同的屬性名

бF(E1-E2)≡бF(E1)-бF(E2)關係代數等價變換規則（續）9.投影與笛卡爾積的交換

假設：E1和E2是兩個關係運算式，

A1，…，An是E1的屬性，

B1，…，Bm是E2的屬性

πA1,A2,…,An,B1,B2,…,Bm

（E1×E2)≡ πA1,A2,…,An（E1)×πB1,B2,…,Bm(E2)關係代數等價變換規則（續）l0.投影與並的交換

假設：E1和E2有相同的屬性名

πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)小結1-2:連接、笛卡爾積的交換律、結合律3：合併或分解投影運算4：合併或分解選擇運算5-8：選擇運算與其他運算交換5，9，10：投影運算與其他運算交換4.2關係系統的查詢優化4.2.1查詢優化概述4.2.2查詢優化的必要性4.2.3查詢優化的一般準則4.2.4關係代數等價變換規則4.2.5關係代數運算式的優化演算法4.2.6優化的一般步驟4.2.5關係代數運算式的優化演算法

演算法：關係運算式的優化輸入：一個關係運算式的語法樹。輸出：計算該運算式的程式。方法：（1）分解選擇運算利用規則4把形如бF1∧F2∧…∧Fn(E)變換為

бF1(бF2(…(бFn(E))…))關係代數運算式的優化演算法

(續)（2）通過交換選擇運算，將其盡可能移到葉端對每一個選擇，利用規則4～8盡可能把它移到樹的葉端。

（3）通過交換投影運算，將其盡可能移到葉端

對每一個投影利用規則3，9，l0，5中的一般形式盡可能把它移向樹的葉端。

關係代數運算式的優化演算法

(續)（4）合併串接的選擇和投影，以便能同時執行或在一次掃描中完成利用規則3～5把選擇和投影的串接合並成單個選擇、單個投影或一個選擇後跟一個投影。使多個選擇或投影能同時執行，或在一次掃描中全部完成儘管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。

關係代數運算式的優化演算法

(續)（5）對內結點分組把上述得到的語法樹的內節點分組。每一雙目運算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是б，π運算)。如果其後代直到葉子全是單目運算，則也將它們併入該組，但當雙目運算是笛卡爾積(×)，而且其後的選擇不能與它結合為等值連接時除外。把這些單目運算單獨分為一組。

關係代數運算式的優化演算法

(續)（6）生成程式生成一個程式，每組結點的計算是程式中的一步。各步的順序是任意的，只要保證任何一組的計算不會在它的後代組之前計算。

4.2關係系統的查詢優化4.2.1查詢優化概述4.2.2查詢優化的必要性4.2.3查詢優化的一般準則4.2.4關係代數等價變換規則4.2.5關係代數運算式的優化演算法4.2.6優化的一般步驟

4.2.6優化的一般步驟1．把查詢轉換成某種內部表示2．代數優化：把語法樹轉換成標準（優化）形式3．物理優化：選擇低層的存取路徑4．生成查詢計畫，選擇代價最小的優化的一般步驟(續)（1）把查詢轉換成某種內部表示例：求選修了課程Ｃ2的學生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';（1）把查詢轉換成某種內部表示語法樹結果project(Sname)

select(SC.Cno=

2

)

join(Student.Sno=SC.Sno)

StudentSC關係代數語法樹πSname

SC.Cno=’2’