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

關係系統及其查詢優化

§4.1關係系統關係系統的定義 一個系統可定義為關係系統，當且僅當它：支持關係資料庫（關係數據結構）支持選擇、投影和連接運算，對這些運算不必定義任何存取路徑關係系統的分類表式系統(最小)關係系統關係完備系統全關係系統§4.1關係系統表式系統僅支持關係(即表)數據結構，不支持集合級的操作。(最小)關係系統即前面定義的關係系統。它們僅支持關係數據結構和三種關係搡作。許多微機關係資料庫系統如FoxPro等就屬於這一類關係上完備的系統這類系統支持關係數據結構和所有的關係代數操作(功能上與關係代數等價)。90年代初的許多關係資料庫管理系統屬於這一類全關係系統這類系統支持關係模型的所有特徵查詢優化問題的提出查詢優化策略關係代數等價變換查詢優化演算法查詢優化步驟和示例§4.2資料庫查詢優化一個用戶查詢，系統實現時均使用一個與之相應的關係代數運算式去求解，同一查詢等價關係代數運算式的不同，就會出現不同的求解路線。如：求選修了2號課程的學生姓名，SQL語句

Selectsnamefroms,scwheres.sno=sc.snoANDo=‘2’等價關係代數運算式如下：Q1=Пsname(σs.sno=sc.sno^o=‘2’(SXSC))Q2=Пsname(σo=‘2’(S|><|SC))Q3=Пsname(S|><|σo=‘2’(SC))§4.2.1查詢優化問題提出§4.2.1查詢優化問題提出假設1：外存：

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

§4.2.1查詢優化問題提出讀取Student和SC表的策略Student表SC表100個SC元組記憶體緩衝區中間檔10個Student元組10個連接後的元組第一個五塊第二個五塊……

共一千個學生記錄…

共一萬個選課記錄第1－100個元組第101－200個元組第1－10個元組第11－20個元組第一塊第二塊…第n塊§4.2.1查詢優化問題提出Q1=Пsname(σs.sno=sc.sno^o=‘2’(SXSC))①Student×SC

讀取總塊數=讀S表塊數+讀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小時Q2=Пsname(σo=‘2’(S|><|SC))①

讀取總塊數=2100塊

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

寫中間結果時間=10000/10/20=50秒

②б: 讀數據時間=50秒

③П

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

§4.2.1查詢優化問題提出Q3=Пsname(S|><|σo=‘2’(SC))①б

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

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

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

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

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

③П

總時間＝5＋5秒＝10秒§4.2.1查詢優化問題提出Q3=Пsname(S|><|σo=‘2’(SC))假設SC表在Cno上有索引，S表在Sno上有索引

①б:讀SC表索引= 讀SC表總塊數=50/100<1塊 讀數據時間

中間結果大小=50條不必寫入外存②:讀Student表索引= 讀Student表總塊數=50/10=5塊 讀數據時間③П總時間<10秒§4.2.1查詢優化問題提出通過分析可知：採用不同的等價關係運算式其存取時間差別很大，因而必須優化。♦儘早進行選擇運算♦儘早進行投影運算♦避免進行笛卡爾積運算，把笛卡爾積與其後的選擇運算合併成一個連接運算♦同时计算一串选择和投影的操作，以免分开运算造成多次扫描文件。§4.2.2查詢優化策略♦進行連接運算前，對關係適當預處理♦提取公共運算式，儲存中間結果，減少重複計算。(適合於結果數據量少、但計算量大的公共運算式，對此公共運算式的調用越頻繁，效益就越大)。§4.2.2查詢優化策略§4.2.3關係代數運算式等價變換關係代數運算式等價指用相同的關係代替兩個運算式中相應的關係所得到的結果是相同的上面的優化策略大部分都涉及到代數運算式的變換設E1、E2等是關係代數運算式，F是條件運算式

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

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

§4.2.3關係代數運算式等價變換

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

F1

F2

F1

F2§4.2.3關係代數運算式等價變換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.2.3關係代數運算式等價變換4.選擇的串接定律

бF1（б

F2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合併這樣一次就可檢查全部條件。§4.2.3關係代數運算式等價變換選擇運算滿足交換律σF1(σF2(E))=σF2(σF1(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)))§4.2.3關係代數運算式等價變換6.選擇對笛卡爾積的分配律(1)假設：F中涉及的屬性都是E1中的屬性

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

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

F2只涉及E2中的屬性

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

§4.2.3關係代數運算式等價變換(3)假設：F=F1∧F2，

F1只涉及E1中的屬性，

F2涉及E1和E2兩者的屬性

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

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

§4.2.3關係代數運算式等價變換7.選擇對並的分配律 假設：E=E1∪E2，E1，E2有相同的屬性名

бF(E1∪E2)≡бF(E1)∪бF(E2)8.選擇對差運算的分配律 假設：E1與E2有相同的屬性名

бF(E1-E2)≡бF(E1)-бF(E2)

§4.2.3關係代數運算式等價變換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)§4.2.3關係代數運算式等價變換l0.投影對並的分配律 假設：E1和E2有相同的屬性名

πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)§4.2.3關係代數運算式等價變換§4.2.4關係代數運算式的優化演算法演算法：關係運算式的優化的非形式描述輸入：一個關係運算式的語法樹。輸出：計算該運算式的程式。方法：（1）分解選擇運算

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

бF1(бF2(…(бFn(E))…))

（2）通過交換選擇運算，將其盡可能移到葉端

對每一個選擇，利用規則4～8盡可能把它移到樹的葉端。

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

對每一個投影利用規則3，9，l0，5中的一般形式尽可能把它移向树的叶端。§4.2.4關係代數運算式的優化演算法（4）合併串接的選擇和投影，以便能同時執行或在一次掃描中完成利用規則3～5把選擇和投影的串接合並成單個選擇、單個投影或一個選擇後跟一個投影。使多個選擇或投影能同時執行，或在一次掃描中全部完成§4.2.4關係代數運算式的優化演算法（5）對內結點分組把上述得到的語法樹的內節點分組。每一雙目運算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是б，π运算)。如果其後代直到葉子全是單目運算，則也將它們併入該組，但當雙目運算是笛卡爾積(×)，而且其後的選擇不能與它結合為等值連接時除外。把這些單目運算單獨分為一組。

§4.2.4關係代數運算式的優化演算法（6）生成程式生成一個程式，每組結點的計算是程式中的一步。各步的順序是任意的，只要保證任何一組的計算不會在它的後代組之前計算。

§4.2.4關係代數運算式的優化演算法求選修了2號課程的學生姓名S（SNO，SNAME，AGE，SEX）SC（SNO，CNO，GRADE）用關係代數運算式Q1=Пsname(σo=‘2’(S|><|SC))轉換為只含有選擇、投影、並、差和笛卡爾積五種基本運算關係代數運算式

Q1=Пsname(σo=‘2’

ПL(σs.sno=sc.sno(SXSC)))L=SNO，SNAME，AGE，SEX，CNO，GRADE§4.2.5關係代數查詢優化實例

Sname

S.sno=SC.sno

SSC

Cno=‘2’

L§4.2.5關係代數查詢優化實例1將合取選擇運算可分解為單個選擇運算的序列。

σs.sno=sc.snoσo=‘2’2利用規則將選擇運算儘量向樹的葉端靠近σθ1∧θ2(E)=σθ1(σθ2(E))σo=‘2’

ПL(σs.sno=sc.sno(SXSC))=ПL(σs.sno=sc.sno(σo=‘2’(SXSC)))

§4.2.5關係代數查詢優化實例當選擇條件θ0的所有屬性只涉及參與連接運算的運算式之一(E1)時：σθ0(E1XE2)=(σθ0(E1))X

E2ПL(σs.sno=sc.sno(σo=‘2’(SXSC)))=ПL(σs.sno=sc.sno(SXσo=‘2’(SC)))投影運算的級聯：∏L1(∏L2(…(∏Ln(E))…))=∏L1(E)Пsname(ПL(σs.sno=sc.sno(SXσo=‘2’(SC))))ПSNAME(σs.sno=sc.sno(SXσo=‘2’(SC)))§4.2.5關係代數查詢優化實例3利用規則將投影運算儘量向樹的葉端靠近利用選擇與投影交換，

F中涉及不在L中屬性L1ПL(σF(E

)=ПL(σF(ПLUL1(E

)))ПSNAME(σs.sno=sc.sno(SXσo=‘2’(SC)))=ПSNAME(σs.sno=sc.snoПSNAME，s.sno，sc.sno((SXσo=‘2’(SC))))=ПSNAME(σs.sno=sc.sno(ПSNAME，s.sno(S)XПsC.sno(

σo=‘2’(SC))))4將上述步驟得到的語法樹的內結點分組，每個二元運算結點與其直接祖先的一元運算結點分為一組，執行時從葉端依次向上執行，每組運算對關係進行一次運算§4.2.5關係代數查詢優化實例

Sname

S.sno=SC.sno

SSC

Cno=‘2’

Sname

S.sno=SC.sno

SSC

Cno=‘2’

L§4.2.5關係代數查詢優化實例

Sname

S.sno=SC.sno

SSC

Cno=‘2’

Sname，s.sno

sc.sno§4.2.5關係代數查詢優化實例把查詢轉換成某種內部表示代數優化：把語法樹轉換成標準（優化）形式物理優化：選擇低層的存取路徑生成查詢計畫，選擇代價最小的§4.2.6優化的一般步驟物理優化：選擇低層的存取路徑優化器查找數據字典獲得當前資料庫狀態資訊選擇字段上是否有索引連接的兩個表是否有序連接字段上是否有索引然後根據一定的優化規則選擇存取路徑

如本例中若SC表上建有Cno的索引，則應該利用這個索引，而不必順序掃描SC表。§4.2.6優化的一般步驟生成查詢計畫，選擇代價最小的-在作連接運算時，若兩個表(設為R1，R2)均无序，连接属性上也没有索引，则可以有下面几种查询计划：

對兩個表作排序預處理對R1在連接屬性上建索引對R2在連接屬性上建索引在R1，R2的連接屬性上均建索引對不同的查詢計畫計算代價，選擇代價最小的一個。在計算代價時主要考慮磁片讀寫的I/O數，記憶體CPU處理時間在粗略計算時可不考慮。

§4.2.6優化的一般步驟S(S#,SNAME,AGE,SEX)C