Oracle數(shù)據(jù)庫(kù)學(xué)習(xí)-數(shù)據(jù)庫(kù)9_DataBase

1、數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化第九章 關(guān)系查詢處理和查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3 代數(shù)優(yōu)化代數(shù)優(yōu)化9.4 物理優(yōu)化物理優(yōu)化數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理v查詢分析查詢分析v查詢檢查查詢檢查v查詢優(yōu)化查詢優(yōu)化v查詢執(zhí)行查詢執(zhí)

2、行詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析語(yǔ)義轉(zhuǎn)換語(yǔ)義轉(zhuǎn)換符號(hào)名轉(zhuǎn)換符號(hào)名轉(zhuǎn)換安全性檢查安全性檢查完整怍檢查完整怍檢查查詢樹(shù)查詢樹(shù)代數(shù)優(yōu)化代數(shù)優(yōu)化物理優(yōu)化等物理優(yōu)化等執(zhí)行策略描述執(zhí)行策略描述代碼生成代碼生成執(zhí)行查詢計(jì)劃的代碼執(zhí)行查詢計(jì)劃的代碼數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)數(shù)據(jù)字典數(shù)據(jù)字典查詢語(yǔ)句查詢語(yǔ)句查詢分析查詢分析查詢檢查查詢檢查查詢優(yōu)化查詢優(yōu)化查詢執(zhí)行查詢執(zhí)行圖圖9.1 查詢處理步驟查詢處理步驟9.1.1 查詢處理的步驟查詢處理的步驟數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.1.2 實(shí)現(xiàn)查詢操作的算法示例實(shí)現(xiàn)查

3、詢操作的算法示例一、選擇操作的實(shí)現(xiàn)一、選擇操作的實(shí)現(xiàn) 例例1 SELECT * FROM student WHERE C1：無(wú)條件；：無(wú)條件；C2：Sno=200215121;C3:Sage20;C4:Sdept=CS AND Sage20方法方法: :1.1.簡(jiǎn)單的全表掃描簡(jiǎn)單的全表掃描2.2.索引或散列掃描索引或散列掃描二、連接操作的實(shí)現(xiàn)二、連接操作的實(shí)現(xiàn)例例2 SELECT * FROM student，SC WHERE student.Sno=SC.Sno方法：方法：1.1.嵌套循環(huán)方法嵌套循環(huán)方法2.2.排序合并方法排序合并方法3.3.索引連接方法索引連接方法4.Hash Join4

4、.Hash Join方法方法數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述v查詢優(yōu)化的必要性查詢優(yōu)化的必要性查詢優(yōu)化極大地影響查詢優(yōu)化極大地影響RDBMS的性能。的性能。v查詢優(yōu)化的可能性查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語(yǔ)言的關(guān)系數(shù)據(jù)語(yǔ)言的級(jí)別很高級(jí)別很高，使，使DBMS可以從關(guān)系表達(dá)式中分析查可以從關(guān)系表達(dá)式中分析查詢?cè)冋Z(yǔ)義語(yǔ)義。 數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論

5、第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化由由DBMS進(jìn)行查詢優(yōu)化的好處進(jìn)行查詢優(yōu)化的好處用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，系統(tǒng)可以用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，系統(tǒng)可以比用戶程序的比用戶程序的優(yōu)化優(yōu)化做得更好。做得更好。1.優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息獲得這些信息 。2.如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢?nèi)绻麛?shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)重新優(yōu)化化以選擇相適應(yīng)的執(zhí)行計(jì)劃。以選擇相適應(yīng)的執(zhí)行計(jì)劃。3.在非關(guān)系系統(tǒng)中

6、必須重寫(xiě)程序，而重寫(xiě)程序在實(shí)際應(yīng)用中往往是在非關(guān)系系統(tǒng)中必須重寫(xiě)程序，而重寫(xiě)程序在實(shí)際應(yīng)用中往往是不太可能的。不太可能的。4.優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。有限的幾種可能性。5.優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)。優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)。數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化查詢優(yōu)化目標(biāo)查詢優(yōu)化目標(biāo)v查詢優(yōu)化的總目標(biāo)查詢優(yōu)化的總目標(biāo)選擇有效策略，求得給定關(guān)系表達(dá)式選擇有效策略，求得給定

7、關(guān)系表達(dá)式的值的值v實(shí)際系統(tǒng)的查詢優(yōu)化步驟實(shí)際系統(tǒng)的查詢優(yōu)化步驟1. 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語(yǔ)法樹(shù)將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語(yǔ)法樹(shù)2. 根據(jù)一定的等價(jià)變換規(guī)則把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)根據(jù)一定的等價(jià)變換規(guī)則把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn) （優(yōu)化）形式（優(yōu)化）形式3.選擇低層的操作算法選擇低層的操作算法對(duì)于語(yǔ)法樹(shù)中的每一個(gè)操作對(duì)于語(yǔ)法樹(shù)中的每一個(gè)操作 計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià) 選擇代價(jià)小的執(zhí)行算法選擇代價(jià)小的執(zhí)行算法4. 生成查詢計(jì)劃生成查詢計(jì)劃(查詢執(zhí)行方案查詢執(zhí)行方案)查詢計(jì)劃是由一系列內(nèi)部操作組成的。查詢計(jì)劃是由一系列內(nèi)部操作組成的。數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)

8、庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化基于代價(jià)模型的優(yōu)化算法基于代價(jià)模型的優(yōu)化算法v集中式數(shù)據(jù)庫(kù)集中式數(shù)據(jù)庫(kù)單用戶系統(tǒng)單用戶系統(tǒng)總代價(jià)總代價(jià) = I/O代價(jià)代價(jià) + CPU代價(jià)代價(jià)多用戶系統(tǒng)多用戶系統(tǒng)總代價(jià)總代價(jià) = I/O代價(jià)代價(jià) + CPU代價(jià)代價(jià) + 內(nèi)存代價(jià)內(nèi)存代價(jià)v分布式數(shù)據(jù)庫(kù)分布式數(shù)據(jù)庫(kù) 總代價(jià)總代價(jià) = I/O代價(jià)代價(jià) + CPU代價(jià)代價(jià)+ 內(nèi)存代價(jià)內(nèi)存代價(jià) + 通信代價(jià)通信代價(jià) 代價(jià)模型代價(jià)模型數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查

9、詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.2.2 一個(gè)實(shí)例一個(gè)實(shí)例 例例3 求選修了課程求選修了課程2的學(xué)生姓名的學(xué)生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2; 執(zhí)行策略執(zhí)行策略1 name(Student.Sno=SC.Sno SC.Cno=2 (StudentSC)2 name(SC.Cno= 2 (Student SC) 3 name(Student SC.Cno=2 (SC)數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處

10、理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.3 代數(shù)優(yōu)化代數(shù)優(yōu)化v基于關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化方法為基于關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化方法為代數(shù)優(yōu)化代數(shù)優(yōu)化v代數(shù)優(yōu)化策略是通過(guò)對(duì)關(guān)系代數(shù)表達(dá)式的等價(jià)變換來(lái)代數(shù)優(yōu)化策略是通過(guò)對(duì)關(guān)系代數(shù)表達(dá)式的等價(jià)變換來(lái)提高查詢效率提高查詢效率; ;v關(guān)系代數(shù)表達(dá)式的等價(jià)是指用相同的關(guān)系代替兩個(gè)表關(guān)系代數(shù)表達(dá)式的等價(jià)是指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的v兩個(gè)表達(dá)式兩個(gè)表達(dá)式E1E1和和E2E2是等價(jià)的是等價(jià)的, ,記為記為E1 E2E1 E2數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論

11、數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則設(shè)設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式是條件表達(dá)式l. 連接、笛卡爾積交換律連接、笛卡爾積交換律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1 常用的等價(jià)變換規(guī)則常用的等價(jià)變換規(guī)則數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化 2. 連接、笛卡爾積的結(jié)合律連接、笛卡爾積的結(jié)合律 (E1E2) E3 E1 (E2E

12、3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F F數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化3. 投影的串接定律投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E)假設(shè)：假設(shè)：1) E是關(guān)系代數(shù)表達(dá)式是關(guān)系代數(shù)表達(dá)式2) Ai(i=1，2，n), Bj(j=l，2，m)是屬性名是屬性名3) A1, A2, , An構(gòu)成構(gòu)成Bl，B2，Bm的子集的子集 數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)

13、據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化4. 選擇的串接定律選擇的串接定律 F1 （ F2（E） F1 F2(E)選擇的串接律說(shuō)明選擇的串接律說(shuō)明 選擇條件可以合并選擇條件可以合并這樣一次就可檢查全部條件。這樣一次就可檢查全部條件。 5. 選擇與投影的交換律選擇與投影的交換律 (1)假設(shè)假設(shè): 選擇條件選擇條件F只涉及屬性只涉及屬性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E) (2)假設(shè)假設(shè): F中有不屬于中有不屬于A1, ,An的屬性的屬性B1,Bm A1,A2, ,An ( F (E) A1,A2,

14、,An(F (A1,A2, ,An,B1,B2, ,Bm(E)數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化6. 選擇與笛卡爾積的交換律選擇與笛卡爾積的交換律(1) 假設(shè)：假設(shè)：F中涉及的屬性都是中涉及的屬性都是E1中的屬性中的屬性 F (E1E2)F (E1)E2 (2) 假設(shè)：假設(shè)：F=F1F2，并且，并且F1只涉及只涉及E1中的屬性，中的屬性， F2只涉及只涉及E2中的屬性中的屬性 則由上面的等價(jià)變換規(guī)則則由上面的等價(jià)變換規(guī)則1，4，6可推出：可推出： F(E1E2) F1(E1)F2 (E2

15、) (3) 假設(shè)：假設(shè)： F=F1F2，并且，并且 F1只涉及只涉及E1中的屬性，中的屬性， F2涉及涉及E1和和E2兩者的屬性兩者的屬性 F(E1E2) F2(F1(E1)E2) 它使部分選擇在笛卡爾積前先做它使部分選擇在笛卡爾積前先做 數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化7. 選擇與并的分配律選擇與并的分配律假設(shè)：假設(shè)：E=E1E2，E1，E2有相同的屬性名有相同的屬性名F(E1E2) F(E1) F(E2) 8. 選擇與差運(yùn)算的分配律選擇與差運(yùn)算的分配律假設(shè)：假設(shè)：E1與與E2有有相

16、同的屬性名相同的屬性名F(E1-E2) F(E1) - F(E2) 9. 選擇對(duì)自然連接的分配律選擇對(duì)自然連接的分配律F(E1E2) F(E1) F(E2) F只涉及只涉及E1與與E2的的公共屬性公共屬性數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化10. 投影與笛卡爾積的分配投影與笛卡爾積的分配假設(shè)：假設(shè)：E1和和E2是兩個(gè)關(guān)系表達(dá)式，是兩個(gè)關(guān)系表達(dá)式， A1，An是是E1的屬性，的屬性， B1，Bm是是E2的屬性的屬性 A1,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,A

17、n（E1) B1,B2, ,Bm(E2)l1. 投影與并的分配投影與并的分配假設(shè)：假設(shè)：E1和和E2 有有相同的屬性名相同的屬性名 A1,A2, ,An(E1E2)A1,A2, ,An(E1)A1,A2, ,An(E2) 數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.3.2 查詢樹(shù)的啟發(fā)式優(yōu)化查詢樹(shù)的啟發(fā)式優(yōu)化 啟發(fā)式規(guī)則的代數(shù)優(yōu)化啟發(fā)式規(guī)則的代數(shù)優(yōu)化,是對(duì)關(guān)系代數(shù)表達(dá)式的查詢樹(shù)進(jìn)行優(yōu)化是對(duì)關(guān)系代數(shù)表達(dá)式的查詢樹(shù)進(jìn)行優(yōu)化,其典其典型的規(guī)則有型的規(guī)則有:1.選擇運(yùn)算應(yīng)盡可能先做選擇運(yùn)算應(yīng)盡可能先做

18、 目的：減小中間關(guān)系目的：減小中間關(guān)系2.投影運(yùn)算和選擇運(yùn)算同時(shí)做投影運(yùn)算和選擇運(yùn)算同時(shí)做目的：避免重復(fù)掃描關(guān)系目的：避免重復(fù)掃描關(guān)系3.把投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合把投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合目的：減少掃描關(guān)系的遍數(shù)目的：減少掃描關(guān)系的遍數(shù)數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化4.某些選擇運(yùn)算在其前面執(zhí)行的笛卡爾積某些選擇運(yùn)算在其前面執(zhí)行的笛卡爾積= 連接運(yùn)算連接運(yùn)算 例：例：Student.Sno=SC.Sno (StudentSC) Student SC5.提取公共

19、子表達(dá)式提取公共子表達(dá)式數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 算法：關(guān)系表達(dá)式的優(yōu)化。算法：關(guān)系表達(dá)式的優(yōu)化。輸入：一個(gè)關(guān)系表達(dá)式的查詢樹(shù)。輸入：一個(gè)關(guān)系表達(dá)式的查詢樹(shù)。輸出：優(yōu)化的查詢樹(shù)。輸出：優(yōu)化的查詢樹(shù)。方法：方法：(1) 分解選擇運(yùn)算分解選擇運(yùn)算 利用規(guī)則利用規(guī)則4把形如把形如F1 F2 Fn (E)變換為變換為 F1 (F2( (Fn(E) ) (2) 通過(guò)交換選擇運(yùn)算，將其盡可能移到葉端通過(guò)交換選擇運(yùn)算，將其盡可能移到葉端 對(duì)每一

20、個(gè)選擇，利用規(guī)則對(duì)每一個(gè)選擇，利用規(guī)則48盡可能把它移到樹(shù)的葉端。盡可能把它移到樹(shù)的葉端。(3) 通過(guò)交換投影運(yùn)算，將其盡可能移到葉端通過(guò)交換投影運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)投影利用規(guī)則對(duì)每一個(gè)投影利用規(guī)則3、5、l0、11中的一般形式盡可能把它移向樹(shù)的中的一般形式盡可能把它移向樹(shù)的葉端。葉端。數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化(4) 利用規(guī)則利用規(guī)則35把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多個(gè)選擇或投影

21、能同時(shí)執(zhí)行，或在一次掃描中選擇后跟一個(gè)投影。使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成，盡管這種變換似乎違背全部完成，盡管這種變換似乎違背“投影盡可能早做投影盡可能早做”的原則，但這的原則，但這樣做效率更高。樣做效率更高。(5) 對(duì)內(nèi)結(jié)點(diǎn)分組對(duì)內(nèi)結(jié)點(diǎn)分組把上述得到的語(yǔ)法樹(shù)的內(nèi)節(jié)點(diǎn)分組。把上述得到的語(yǔ)法樹(shù)的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算每一雙目運(yùn)算(， ，-)和它所有的直接祖先為一組和它所有的直接祖先為一組(這些直這些直接祖先是接祖先是，運(yùn)算運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積雙目運(yùn)算是笛卡爾

22、積()，而且其后的選擇不能與它結(jié)合為等值，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。 數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化例例4 求選修了課程求選修了課程2的學(xué)生姓名的學(xué)生姓名SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2; Sname Student.Sno=SC.Sno SC.Cno= 2 StudentSC（2）

23、關(guān)系代數(shù)語(yǔ)法樹(shù)）關(guān)系代數(shù)語(yǔ)法樹(shù)Sname Student.Sno=SC.Sno SC.Cno= 2 StudentSC（3）優(yōu)化后的查詢樹(shù)）優(yōu)化后的查詢樹(shù)結(jié)果結(jié)果project(Sname) select(SC.Cno= 2 ) join(Student.Sno=SC.Sno) StudentSC（1）把）把SQL語(yǔ)句轉(zhuǎn)換成查詢樹(shù)語(yǔ)句轉(zhuǎn)換成查詢樹(shù)數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.4 物理優(yōu)化物理優(yōu)化代數(shù)優(yōu)化是改變查詢語(yǔ)句的次序和組合，不涉及底層的存代數(shù)優(yōu)化是改變查詢語(yǔ)句的次序和組合，不涉及底層的存取路徑，取路徑，物理優(yōu)化物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑就