1、2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理1關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(yōu)化 第第4章章n n 關(guān)系系統(tǒng)的定義關(guān)系系統(tǒng)的定義n 關(guān)系系統(tǒng)的分類關(guān)系系統(tǒng)的分類n n 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(yōu)化n 查詢優(yōu)化的一般準(zhǔn)則查詢優(yōu)化的一般準(zhǔn)則n 關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)等價(jià)變換規(guī)則n 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法n 優(yōu)化的一般步驟優(yōu)化的一般步驟 2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理24.1 4.1 關(guān)系系統(tǒng)關(guān)系系統(tǒng)支持關(guān)系模型的關(guān)系數(shù)據(jù)庫管理系統(tǒng)簡(jiǎn)稱關(guān)系系統(tǒng)。支持關(guān)系模型的關(guān)系數(shù)據(jù)庫管理系統(tǒng)簡(jiǎn)稱關(guān)系系統(tǒng)。n 下述關(guān)系的下述關(guān)系的DBMSDBMS不能稱為關(guān)

2、系系統(tǒng)不能稱為關(guān)系系統(tǒng)n 不支持關(guān)系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)不支持關(guān)系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)n 支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，但無支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，但無、 運(yùn)算功能的系統(tǒng)運(yùn)算功能的系統(tǒng)n 支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，有支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，有、 運(yùn)算，但要求定義物理運(yùn)算，但要求定義物理 存取路徑的系統(tǒng)存取路徑的系統(tǒng)可稱為關(guān)系系統(tǒng)的可稱為關(guān)系系統(tǒng)的DBMSDBMS，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)1）支持關(guān)系數(shù)據(jù)結(jié)構(gòu)（關(guān)系數(shù)據(jù)庫）支持關(guān)系數(shù)據(jù)結(jié)構(gòu)（關(guān)系數(shù)據(jù)庫）2）支持）支持、 運(yùn)算，且不要求用戶定義任何物理存取路徑運(yùn)算，且不要求用戶定義任何物理存取路徑4.1.1 4.1.1 關(guān)系系統(tǒng)的定義關(guān)系系統(tǒng)的定義2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理34.1.

3、2 4.1.2 關(guān)系系統(tǒng)的分類關(guān)系系統(tǒng)的分類 支持關(guān)系模型的所有特征。在關(guān)系完備系統(tǒng)的基礎(chǔ)上，進(jìn)一步支支持關(guān)系模型的所有特征。在關(guān)系完備系統(tǒng)的基礎(chǔ)上，進(jìn)一步支持實(shí)體完整性和參照完整性等。持實(shí)體完整性和參照完整性等。DB,ORACLE,SYBASE, DB,ORACLE,SYBASE, 已接近這個(gè)已接近這個(gè)目標(biāo)。目前尚無全關(guān)系系統(tǒng)。目標(biāo)。目前尚無全關(guān)系系統(tǒng)。 僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，不支持集合級(jí)的操作。僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，不支持集合級(jí)的操作。 支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，支持支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，支持、 運(yùn)算，且不定義物理路徑。運(yùn)算，且不定義物理路徑。 支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和所有關(guān)系代數(shù)操作（或功能上與關(guān)系代數(shù)等支持

4、關(guān)系數(shù)據(jù)結(jié)構(gòu)和所有關(guān)系代數(shù)操作（或功能上與關(guān)系代數(shù)等價(jià)）。價(jià)）。DB,ORACLE,SYBASE,DB,ORACLE,SYBASE,屬于這一類。屬于這一類。2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理4 關(guān)系系統(tǒng)分類關(guān)系系統(tǒng)分類數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)操作完整性約束完整性約束表表表表選擇、投選擇、投影、連接影、連接表表2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理54.2 4.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化4.2.1 4.2.1 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(yōu)化l 查詢處理的過程查詢處理的過程查詢語句查詢語句查詢輸出查詢輸出關(guān)系代數(shù)表達(dá)式關(guān)系代數(shù)表達(dá)式執(zhí)行計(jì)劃執(zhí)行計(jì)

5、劃語法分析與語法分析與翻譯翻譯執(zhí)行引擎執(zhí)行引擎優(yōu)化器優(yōu)化器有關(guān)數(shù)據(jù)的有關(guān)數(shù)據(jù)的統(tǒng)計(jì)信息統(tǒng)計(jì)信息數(shù)據(jù)數(shù)據(jù)2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理6n 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，從而選擇優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，從而選擇有效的執(zhí)行計(jì)劃；有效的執(zhí)行計(jì)劃；n 如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢進(jìn)行重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃；詢進(jìn)行重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃；n 優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃；優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃；n 優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)。優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)

6、。2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理71. 1. 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹2. 2. 根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3. 3. 選擇低層的操作算法選擇低層的操作算法n 對(duì)于語法樹中的每一個(gè)操作對(duì)于語法樹中的每一個(gè)操作n 根據(jù)存取路徑、數(shù)據(jù)的尺寸、數(shù)據(jù)的存儲(chǔ)分布、存儲(chǔ)根據(jù)存取路徑、數(shù)據(jù)的尺寸、數(shù)據(jù)的存儲(chǔ)分布、存儲(chǔ)數(shù)據(jù)的聚簇等信息來計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)數(shù)據(jù)的聚簇等信息來計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)n 選擇代價(jià)小的執(zhí)行算法選擇代價(jià)小的執(zhí)行算法4. 4. 生成查詢計(jì)

7、劃生成查詢計(jì)劃( (查詢執(zhí)行方案查詢執(zhí)行方案) )2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理8n 常用查詢優(yōu)化技術(shù)常用查詢優(yōu)化技術(shù)n 用啟發(fā)式規(guī)則來縮減查詢計(jì)劃的搜索空間用啟發(fā)式規(guī)則來縮減查詢計(jì)劃的搜索空間n 利用統(tǒng)計(jì)信息估算執(zhí)行代價(jià)利用統(tǒng)計(jì)信息估算執(zhí)行代價(jià)n 基于代價(jià)（目前商品化基于代價(jià)（目前商品化RDBMSRDBMS大都采用）大都采用）n 代價(jià)模型代價(jià)模型n 集中式數(shù)據(jù)庫集中式數(shù)據(jù)庫n 單用戶系統(tǒng)：總代價(jià)單用戶系統(tǒng)：總代價(jià) = I/O= I/O代價(jià)代價(jià) + CPU+ CPU代價(jià)代價(jià)n 多用戶系統(tǒng)：總代價(jià)多用戶系統(tǒng)：總代價(jià) = I/O= I/O代價(jià)代價(jià) + CPU+ CPU代價(jià)代價(jià) + +

8、內(nèi)存代價(jià)內(nèi)存代價(jià)n 分布式數(shù)據(jù)庫分布式數(shù)據(jù)庫 總代價(jià)總代價(jià) = I/O= I/O代價(jià)代價(jià) + CPU+ CPU代價(jià)代價(jià) + + 內(nèi)存代價(jià)內(nèi)存代價(jià) + + 通信代價(jià)通信代價(jià) 2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理94.2.2 4.2.2 一個(gè)實(shí)例一個(gè)實(shí)例SELECTSELECT Student.SnameStudent.Sname FROM FROM Student Student，SCSCWHEREWHERE Student.SnoStudent.Sno = = SC.SnoSC.Sno ANDAND CnoCno = 2 = 2；u 數(shù)據(jù)量：數(shù)據(jù)量：Student:1000Student

9、:1000條；條；SC:10000SC:10000條；選修條；選修2 2號(hào)課程號(hào)課程:50:50條條u 一個(gè)內(nèi)存塊裝元組一個(gè)內(nèi)存塊裝元組:10:10個(gè)個(gè)StudentStudent或或100100個(gè)個(gè)SCSC，內(nèi)存中可以，內(nèi)存中可以 存放存放:5:5塊塊StudentStudent元組和元組和1 1塊塊SCSC元組元組u 讀寫速度：讀寫速度：2020塊塊/ /秒秒2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理101. 1. 1 1 SnameSname(Student.SnoStudent.Sno= =SC.SnoSC.Sno SC.CnoSC.Cno=c2 =c2 (Student(Studen

10、tSC)SC) 計(jì)算廣義笛卡爾積計(jì)算廣義笛卡爾積( (StudentStudentSCSC) ) 讀取總塊數(shù)讀取總塊數(shù) = = 讀讀StudentStudent表塊數(shù)表塊數(shù) + + 讀讀SCSC表遍數(shù)表遍數(shù) * * 每遍塊數(shù)每遍塊數(shù) = 1000/10+(1000/(10= 1000/10+(1000/(105) 5) (10000/100) = 2100(10000/100) = 2100 讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=2100/20=105=2100/20=105秒秒 中間結(jié)果大小中間結(jié)果大小 = 1000= 1000* *10000 = 1010000 = 107 7 (1 (1千萬條元組千萬條

11、元組) ) 寫中間結(jié)果時(shí)間寫中間結(jié)果時(shí)間 = 10000000/10/20 = 50000= 10000000/10/20 = 50000秒秒 選擇操作選擇操作( () ) 讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間 = 50000= 50000秒秒 投影投影( () ) 總時(shí)間總時(shí)間 =105=10550000500005000050000秒秒 = 100105= 100105秒秒 = 27.8= 27.8小時(shí)小時(shí)2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理112. 2. 2 2 namename(SC.CnoSC.Cno= 2= 2 (Student SC) (Student SC)自然連接自然連接( )( )

12、讀取總塊數(shù)讀取總塊數(shù)= 2100= 2100塊塊 讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=2100/20=105=2100/20=105秒秒 中間結(jié)果大小中間結(jié)果大小=10000=10000（即（即SCSC表中記錄條數(shù)，減少表中記錄條數(shù)，減少10001000倍）倍） 寫中間結(jié)果時(shí)間寫中間結(jié)果時(shí)間=10000/10/20=50=10000/10/20=50秒秒 選擇操作選擇操作( () ) 讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=50=50秒秒 投影投影( () ) 總時(shí)間總時(shí)間10510550505050秒秒205205秒秒=3.4=3.4分分 2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理123. 3. 2 2 SnameSnam

13、e(Student(Student SC.CnoSC.Cno= 2= 2 (SC) (SC) 選擇操作選擇操作( () )讀讀SCSC表總塊數(shù)表總塊數(shù)= 10000/100=100= 10000/100=100塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=100/20=5=100/20=5秒秒 中間結(jié)果大小中間結(jié)果大小=50=50條條 （不必使用中間文件）（不必使用中間文件） 自然連接（自然連接（ ）讀讀StudentStudent表總塊數(shù)表總塊數(shù)= 1000/10=100= 1000/10=100塊塊讀數(shù)據(jù)時(shí)間讀數(shù)據(jù)時(shí)間=100/20=5=100/20=5秒秒 投影投影( () ) 總時(shí)間總時(shí)間5 55 5秒秒

14、1010秒秒 2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理134.2.3 4.2.3 查詢優(yōu)化的一般準(zhǔn)則查詢優(yōu)化的一般準(zhǔn)則1.1. 選擇運(yùn)算應(yīng)盡可能先做選擇運(yùn)算應(yīng)盡可能先做 2.2. 在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理 （索引連接方法和排序合并連接方法）（索引連接方法和排序合并連接方法）3.3. 投影運(yùn)算和選擇運(yùn)算同時(shí)做投影運(yùn)算和選擇運(yùn)算同時(shí)做4.4. 將投影運(yùn)算與其前后的雙目運(yùn)算結(jié)合（連接、并、差、交等）將投影運(yùn)算與其前后的雙目運(yùn)算結(jié)合（連接、并、差、交等）5.5. 選擇運(yùn)算和笛卡爾積運(yùn)算結(jié)合（等值連接比笛卡兒積省時(shí)間）選擇運(yùn)算和笛卡爾積運(yùn)算結(jié)合（等值連接

15、比笛卡兒積省時(shí)間）6.6. 提取公共子表達(dá)式（例如，定義視圖的表達(dá)式）提取公共子表達(dá)式（例如，定義視圖的表達(dá)式）2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理144.2.4 4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)等價(jià)變換規(guī)則l. l. 連接、笛卡爾積交換律連接、笛卡爾積交換律2. 2. 連接、笛卡爾積的結(jié)合律連接、笛卡爾積的結(jié)合律3. 3. 投影的串接定律投影的串接定律4. 4. 選擇的串接定律選擇的串接定律5. 5. 選擇與投影的交換律選擇與投影的交換律6. 6. 選擇與笛卡爾積的交換律選擇與笛卡爾積的交換律7. 7. 選擇與并的交換選擇與并的交換8. 8. 選擇與差運(yùn)算的交換選擇與差運(yùn)算的交

16、換9. 9. 投影與笛卡爾積的交換投影與笛卡爾積的交換l0. l0. 投影與并的交換投影與并的交換2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理154.2.5 4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)表達(dá)式的優(yōu)化算法1. 分解選擇運(yùn)算分解選擇運(yùn)算2. 通過交換選擇運(yùn)算，將其盡可能移到葉端通過交換選擇運(yùn)算，將其盡可能移到葉端3. 通過交換投影運(yùn)算，將其盡可能移到葉端通過交換投影運(yùn)算，將其盡可能移到葉端4. 合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成中完成5. 對(duì)內(nèi)結(jié)點(diǎn)分組對(duì)內(nèi)結(jié)點(diǎn)分組6. 生成程序生成程序2022年3月23日10時(shí)10分

17、數(shù)據(jù)庫原理164.2.6 4.2.6 優(yōu)化的一般步驟優(yōu)化的一般步驟1 1把查詢轉(zhuǎn)換成某種內(nèi)部表示把查詢轉(zhuǎn)換成某種內(nèi)部表示2 2代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3 3物理優(yōu)化：選擇低層的存取路徑物理優(yōu)化：選擇低層的存取路徑4 4生成查詢計(jì)劃，選擇代價(jià)最小的生成查詢計(jì)劃，選擇代價(jià)最小的 2022年3月23日10時(shí)10分?jǐn)?shù)據(jù)庫原理17StudentStudentSCSCJoin(Student.SnoJoin(Student.Sno= =SC.SnoSC.Sno) )Select(SC.CnoSelect(SC.Cno=2)=2)Project(SnameProject(Sname) )結(jié)結(jié) 果果 Student.SnoStudent.Sno= =Sc.SnoSc.Sno Sc.SnoSc.Sno=2=2Student SCSt