1、關(guān)系系統(tǒng)及其查詢優(yōu)化 第4章 關(guān)系系統(tǒng) 關(guān)系系統(tǒng)的定義 關(guān)系系統(tǒng)的分類 關(guān)系系統(tǒng)的查詢優(yōu)化 關(guān)系系統(tǒng)及其查詢優(yōu)化 查詢優(yōu)化的一般準(zhǔn)則 關(guān)系代數(shù)等價變換規(guī)則 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 優(yōu)化的一般步驟 2022/10/171數(shù)據(jù)庫原理關(guān)系系統(tǒng)及其查詢優(yōu)化 第4章 關(guān)系系統(tǒng)2022/10/1514.1 關(guān)系系統(tǒng)支持關(guān)系模型的關(guān)系數(shù)據(jù)庫管理系統(tǒng)簡稱關(guān)系系統(tǒng)。 下述關(guān)系的DBMS不能稱為關(guān)系系統(tǒng) 不支持關(guān)系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng) 支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，但無、 運(yùn)算功能的系統(tǒng) 支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，有、 運(yùn)算，但要求定義物理 存取路徑的系統(tǒng)可稱為關(guān)系系統(tǒng)的DBMS，當(dāng)且僅當(dāng)1）支持關(guān)系數(shù)據(jù)結(jié)構(gòu)（關(guān)系數(shù)據(jù)庫）2）支持、 運(yùn)

2、算，且不要求用戶定義任何物理存取路徑4.1.1 關(guān)系系統(tǒng)的定義2022/10/172數(shù)據(jù)庫原理4.1 關(guān)系系統(tǒng)支持關(guān)系模型的關(guān)系數(shù)據(jù)庫管理系統(tǒng)簡稱關(guān)系系統(tǒng)4.1.2 關(guān)系系統(tǒng)的分類4全關(guān)系系統(tǒng)： 支持關(guān)系模型的所有特征。在關(guān)系完備系統(tǒng)的基礎(chǔ)上，進(jìn)一步支持實(shí)體完整性和參照完整性等。DB,ORACLE,SYBASE, 已接近這個目標(biāo)。目前尚無全關(guān)系系統(tǒng)。1表式系統(tǒng)： 僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，不支持集合級的操作。（不能算關(guān)系系統(tǒng)）2（最小）關(guān)系系統(tǒng)： 支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，支持、 運(yùn)算，且不定義物理路徑。3關(guān)系完備系統(tǒng)： 支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和所有關(guān)系代數(shù)操作（或功能上與關(guān)系代數(shù)等價）。DB,ORACLE,SY

3、BASE,屬于這一類。2022/10/173數(shù)據(jù)庫原理4.1.2 關(guān)系系統(tǒng)的分類4全關(guān)系系統(tǒng)：1表式系統(tǒng)：2 關(guān)系系統(tǒng)分類數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作完整性約束表式系統(tǒng)表(最小)關(guān)系系統(tǒng)表選擇、投影、連接關(guān)系完備的系統(tǒng)表全關(guān)系系統(tǒng)2022/10/174數(shù)據(jù)庫原理 關(guān)系系統(tǒng)分類數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作完整性約束表式系統(tǒng)表(最4.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化4.2.1 關(guān)系系統(tǒng)及其查詢優(yōu)化 查詢處理的過程查詢語句查詢輸出關(guān)系代數(shù)表達(dá)式執(zhí)行計(jì)劃語法分析與翻譯執(zhí)行引擎優(yōu)化器有關(guān)數(shù)據(jù)的統(tǒng)計(jì)信息數(shù)據(jù)2022/10/175數(shù)據(jù)庫原理4.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化4.2.1 關(guān)系系統(tǒng)及其查詢系統(tǒng)優(yōu)化 優(yōu)化器可以從數(shù)據(jù)字典中獲取

4、許多統(tǒng)計(jì)信息，從而選擇有效的執(zhí)行計(jì)劃； 如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動對查詢進(jìn)行重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃； 優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃； 優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)。2022/10/176數(shù)據(jù)庫原理系統(tǒng)優(yōu)化 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，從而選擇 實(shí)際系統(tǒng)的查詢優(yōu)化步驟1. 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹2. 根據(jù)一定的等價變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3. 選擇低層的操作算法 對于語法樹中的每一個操作 根據(jù)存取路徑、數(shù)據(jù)的尺寸、數(shù)據(jù)的存儲分布、存儲數(shù)據(jù)的聚簇等信息來計(jì)算各種執(zhí)行算法的執(zhí)行代價 選擇代價小的執(zhí)行算法4. 生成查詢計(jì)劃(

5、查詢執(zhí)行方案)2022/10/177數(shù)據(jù)庫原理 實(shí)際系統(tǒng)的查詢優(yōu)化步驟1. 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通 常用查詢優(yōu)化技術(shù) 用啟發(fā)式規(guī)則來縮減查詢計(jì)劃的搜索空間 利用統(tǒng)計(jì)信息估算執(zhí)行代價 基于代價（目前商品化RDBMS大都采用） 代價模型 集中式數(shù)據(jù)庫 單用戶系統(tǒng)：總代價 = I/O代價 + CPU代價 多用戶系統(tǒng)：總代價 = I/O代價 + CPU代價 + 內(nèi)存代價 分布式數(shù)據(jù)庫 總代價 = I/O代價 + CPU代價 + 內(nèi)存代價 + 通信代價 2022/10/178數(shù)據(jù)庫原理 常用查詢優(yōu)化技術(shù) 代價模型2022/10/158數(shù)據(jù)庫4.2.2 一個實(shí)例 例. 求選2號課程的學(xué)生姓名SELE

6、CT Student.Sname FROM Student，SCWHERE Student.Sno = SC.Sno AND Cno = 2； 數(shù)據(jù)量：Student:1000條；SC:10000條；選修2號課程:50條 一個內(nèi)存塊裝元組:10個Student或100個SC，內(nèi)存中可以 存放:5塊Student元組和1塊SC元組 讀寫速度：20塊/秒假設(shè)：2022/10/179數(shù)據(jù)庫原理4.2.2 一個實(shí)例 例. 求選2號課程的學(xué)生姓名SELEC1. 1 Sname(Student.Sno=SC.Sno SC.Cno=c2 (StudentSC) 計(jì)算廣義笛卡爾積(StudentSC) 讀取總

7、塊數(shù) = 讀Student表塊數(shù) + 讀SC表遍數(shù) * 每遍塊數(shù) = 1000/10+(1000/(105) (10000/100) = 2100 讀數(shù)據(jù)時間=2100/20=105秒 中間結(jié)果大小 = 1000*10000 = 107 (1千萬條元組) 寫中間結(jié)果時間 = 10000000/10/20 = 50000秒 選擇操作() 讀數(shù)據(jù)時間 = 50000秒 投影() 總時間 =1055000050000秒 = 100105秒 = 27.8小時2022/10/1710數(shù)據(jù)庫原理1. 1 Sname(Student.Sno=SC2. 2 name(SC.Cno= 2 (Student SC

8、)自然連接( ) 讀取總塊數(shù)= 2100塊 讀數(shù)據(jù)時間=2100/20=105秒 中間結(jié)果大小=10000（即SC表中記錄條數(shù)，減少1000倍） 寫中間結(jié)果時間=10000/10/20=50秒選擇操作() 讀數(shù)據(jù)時間=50秒投影() 總時間1055050秒205秒=3.4分2022/10/1711數(shù)據(jù)庫原理2. 2 name(SC.Cno= 2 (St3. 2 Sname(Student SC.Cno= 2 (SC)選擇操作()讀SC表總塊數(shù)= 10000/100=100塊讀數(shù)據(jù)時間=100/20=5秒中間結(jié)果大小=50條 （不必使用中間文件）自然連接（ ）讀Student表總塊數(shù)= 1000

9、/10=100塊讀數(shù)據(jù)時間=100/20=5秒 投影()總時間55秒10秒 2022/10/1712數(shù)據(jù)庫原理3. 2 Sname(Student SC.C4.2.3 查詢優(yōu)化的一般準(zhǔn)則選擇運(yùn)算應(yīng)盡可能先做 在執(zhí)行連接操作前對關(guān)系適當(dāng)進(jìn)行預(yù)處理 （索引連接方法和排序合并連接方法）投影運(yùn)算和選擇運(yùn)算同時做將投影運(yùn)算與其前后的雙目運(yùn)算結(jié)合（連接、并、差、交等）選擇運(yùn)算和笛卡爾積運(yùn)算結(jié)合（等值連接比笛卡兒積省時間）提取公共子表達(dá)式（例如，定義視圖的表達(dá)式）2022/10/1713數(shù)據(jù)庫原理4.2.3 查詢優(yōu)化的一般準(zhǔn)則選擇運(yùn)算應(yīng)盡可能先做 4.2.4 關(guān)系代數(shù)等價變換規(guī)則l. 連接、笛卡爾積交換律2

10、. 連接、笛卡爾積的結(jié)合律3. 投影的串接定律4. 選擇的串接定律5. 選擇與投影的交換律6. 選擇與笛卡爾積的交換律7. 選擇與并的交換8. 選擇與差運(yùn)算的交換9. 投影與笛卡爾積的交換l0. 投影與并的交換2022/10/1714數(shù)據(jù)庫原理4.2.4 關(guān)系代數(shù)等價變換規(guī)則l. 連接、笛卡爾積交換律24.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法分解選擇運(yùn)算通過交換選擇運(yùn)算，將其盡可能移到葉端通過交換投影運(yùn)算，將其盡可能移到葉端合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成對內(nèi)結(jié)點(diǎn)分組生成程序2022/10/1715數(shù)據(jù)庫原理4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法分解選擇運(yùn)算2022/14.2.6 優(yōu)化的一般步驟1把查詢轉(zhuǎn)換成某種內(nèi)部表示2代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3物理優(yōu)化：選擇低層的存取路徑4生成查詢計(jì)劃，選擇代價最小的 2022/10/1716數(shù)據(jù)庫原理4.2.6 優(yōu)化的一般步驟1把查詢轉(zhuǎn)換成某種內(nèi)部表示202StudentSCJoin(Student.Sno=SC.Sno)Select(SC.Cno=2)Project(Sname)結(jié) 果Student.Sno=Sc.SnoSc.Sno=2Student SCSnameStudent.Sno=Sc.SnoSc.Sno=2SnameSCStudent2022/