數據庫系統概論AnIntroductiontoDatabaseSystem第九章關系系統及其查詢優化AnIntroductiontoDatabaseSystem第九章

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

AnIntroductiontoDatabaseSystem關系系統的分類（續）

數據結構數據操作完整性表式系統表(最小)關系系統表選擇、投影、連接關系完備的系統表全關系系統AnIntroductiontoDatabaseSystem第四章關系系統及其查詢優化9.1關系系統9.2關系系統的查詢優化9.3小結AnIntroductiontoDatabaseSystem9.2關系系統的查詢優化9.2.1查詢優化概述9.2.2查詢優化的必要性9.2.3查詢優化的一般準則9.2.4關系代數等價變換規則9.2.5關系代數表達式的優化算法9.2.6優化的一般步驟AnIntroductiontoDatabaseSystem9.2.1查詢優化概述查詢優化的必要性查詢優化極大地影響RDBMS的性能。

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

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

代價模型

集中式數據庫單用戶系統

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

總代價=I/O代價+CPU代價+內存代價分布式數據庫 總代價=I/O代價+CPU代價[+內存代價]+通信代價AnIntroductiontoDatabaseSystem9.2.2查詢優化的必要性例：求選修了課程Ｃ2的學生姓名

SELECTS.Sname FROMS,SC WHERES.Sno=SC.Sno ANDSC.Cno='C2';AnIntroductiontoDatabaseSystem查詢優化的必要性（續）假設1：外存： S:1000條,SC:10000條,選修C2號課程:50條假設2：一個內存塊裝元組:10條S,或100條SC, 內存中一次可以存放:5塊S元組,1塊SC元組和若干塊連接結果元組假設3：讀寫速度：20塊/秒假設4：連接方法：基于數據塊的嵌套循環法

AnIntroductiontoDatabaseSystem執行策略1Ｑ1＝Пs,name(бS.Sno=SC.Sno

∧SC.Cno='2'

(S×SC))

①S×SC讀取總塊數=讀S表塊數+讀SC表遍數*每遍塊數

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

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

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

寫中間結果時間=10000000/10/20=50000秒

②б

讀數據時間=50000秒

③П總時間=105＋50000＋50000秒=100105秒=27.8小時AnIntroductiontoDatabaseSystem查詢優化的必要性（續）2.Ｑ2＝ПＳ,name(бSC.Cno='2'(SSC))

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

②б

讀數據時間=50秒

③П

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

AnIntroductiontoDatabaseSystem查詢優化的必要性（續）3.Ｑ2＝ПSname(SбSC.Cno='2'(SC))

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

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

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

② 讀S表總塊數=1000/10=100塊

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

③П

總時間＝5＋5秒＝10秒AnIntroductiontoDatabaseSystem9.2.3查詢優化的一般準則選擇運算應盡可能先做

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

投影運算和選擇運算同時做目的：避免重復掃描關系將投影運算與其前面或后面的雙目運算結合目的：減少掃描關系的遍數AnIntroductiontoDatabaseSystem查詢優化的一般準則（續）某些選擇運算＋在其前面執行的笛卡爾積===>連接運算例：бS.Sno=SC.Sno(S×SC)

SSC提取公共子表達式AnIntroductiontoDatabaseSystem9.2.4關系代數等價變換規則關系代數表達式等價指用相同的關系代替兩個表達式中相應的關系所得到的結果是相同的上面的優化策略大部分都涉及到代數表達式的變換AnIntroductiontoDatabaseSystem

常用的等價變換規則

設E1、E2等是關系代數表達式，F是條件表達式

l.連接、笛卡爾積交換律 E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

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

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

F

F

F

FAnIntroductiontoDatabaseSystem關系代數等價變換規則（續）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}的子集AnIntroductiontoDatabaseSystem關系代數等價變換規則（續）4.選擇的串接定律

бF1（б

F2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件。AnIntroductiontoDatabaseSystem關系代數等價變換規則（續）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)))AnIntroductiontoDatabaseSystem關系代數等價變換規則（續）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)

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

F1只涉及E1中的屬性，F2涉及E1和E2兩者的屬性 бF(E1×E2)≡бF2(бF1(E1)×E2)

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

AnIntroductiontoDatabaseSystem關系代數等價變換規則（續）7.選擇與并的交換 假設：E=E1∪E2，E1，E2有相同的屬性名 бF(E1∪E2)≡бF(E1)∪бF(E2)

8.選擇與差運算的交換 假設：E1與E2有相同的屬性名 бF(E1-E2)≡бF(E1)-бF(E2)AnIntroductiontoDatabaseSystem關系代數等價變換規則（續）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)AnIntroductiontoDatabaseSystem關系代數等價變換規則（續）l0.投影與并的交換

假設：E1和E2有相同的屬性名 πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)AnIntroductiontoDatabaseSystem9.2關系系統的查詢優化9.2.1查詢優化概述9.2.2查詢優化的必要性9.2.3查詢優化的一般準則9.2.4關系代數等價變換規則9.2.5關系代數表達式的優化算法9.2.6優化的一般步驟AnIntroductiontoDatabaseSystem語法分析、轉換、優化、形成訪問路徑（執行計劃）、計算結果對S（供應商），P（零件），SP（供應關系）三個關系查詢供應一個部門10000個螺栓以上，且供應商位于南京的供應商名字。Selectsnamefroms,p,spwheres.snum=sp.snumandsp.pnum=p.pnumands.city=‘南京’andp.pname=‘螺栓’andsp.quan>10000原始查詢樹（一種查詢語句的內部表示法）語法分析優化的查詢樹優化執行計劃（見下一頁）AnIntroductiontoDatabaseSystem代數優化完全基于關系代數，把由查詢語句生成代數表達式（查詢樹）中的操作次序進行等價變換。例如：先做選擇和投影，再做連接先做小關系上的連接，再做大關系上的連接變換原則：盡量減少查詢過程中的中間結果的大小。AnIntroductiontoDatabaseSystem代數優化一般步驟1.

將合取選擇分解成一組單選擇操作2.

在查詢樹上把選擇操作下移，讓其盡早執行3.

先執行能夠產生最小的關系的操作4.

將有選擇條件的笛卡兒集操作替換成連接操作5.

將投影屬性分解并在操作樹中盡量下移，必要時生成新的投影運算AnIntroductiontoDatabaseSystem基于代數優化的一個例子對于關系模式： S（SNUM，SNAME，CITY） P（PNUM，PNAME，WEIGHT，SIZE） SP（SNUM，PNUM，DEPT，QUAN）執行查詢Q：SELECTSNAMEFROMS，P，SPWHERE