第九章關(guān)系系統(tǒng)及其查詢優(yōu)化

第九章關(guān)系系統(tǒng)及其查詢優(yōu)化第1頁，共19頁，2023年，2月20日，星期三9.1關(guān)系系統(tǒng)關(guān)系系統(tǒng)定義支持關(guān)系模型的關(guān)系數(shù)據(jù)庫管理系統(tǒng)簡稱關(guān)系系統(tǒng)。1．下述關(guān)系的DBMS不能稱為關(guān)系系統(tǒng)1）不支持關(guān)系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)2）支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，但無δ、π、運(yùn)算功能的系統(tǒng)3）支持關(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頁，共19頁，2023年，2月20日，星期三9.1關(guān)系系統(tǒng)關(guān)系系統(tǒng)分類4．全關(guān)系系統(tǒng)：支持關(guān)系模型的所有特征。在關(guān)系完備系統(tǒng)的基礎(chǔ)上，進(jìn)一步支持實(shí)體完整性和參照完整性等。

DBⅡ,ORACLE,SYBASE,…已接近這個(gè)目標(biāo)。目前尚無全關(guān)系系統(tǒng)。1．表式系統(tǒng)： 僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，不支持關(guān)系操作。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ù)等價(jià)）。 DBⅡ,ORACLE,SYBASE,…屬于這一類第3頁，共19頁，2023年，2月20日，星期三9.1關(guān)系系統(tǒng)關(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)√√√第4頁，共19頁，2023年，2月20日，星期三9.1關(guān)系系統(tǒng)全關(guān)系系統(tǒng)12條準(zhǔn)則0.一個(gè)關(guān)系型的DBMS必須能完全通過它的關(guān)系能力來管理數(shù)據(jù)庫準(zhǔn)則1：信息準(zhǔn)則。關(guān)系型DBMS的所有信息都應(yīng)在邏輯一級(jí)上用一種方法即表中的值顯式地表示準(zhǔn)則2：保證訪問準(zhǔn)則。依表名、主碼、列名的組合，保證能以邏輯方式訪問關(guān)系數(shù)據(jù)庫中的每個(gè)數(shù)據(jù)項(xiàng)。（獨(dú)立于物理結(jié)構(gòu)）準(zhǔn)則3：空值的系統(tǒng)化處理。支持NULL的概念準(zhǔn)則4：基于關(guān)系模型的動(dòng)態(tài)的聯(lián)機(jī)數(shù)據(jù)字典。（以關(guān)系的形式存儲(chǔ)元數(shù)據(jù)）準(zhǔn)則5：統(tǒng)一的數(shù)據(jù)子語言準(zhǔn)則。一體化的統(tǒng)一的數(shù)據(jù)子語言第5頁，共19頁，2023年，2月20日，星期三9.1關(guān)系系統(tǒng)全關(guān)系系統(tǒng)12條準(zhǔn)則準(zhǔn)則6：視圖準(zhǔn)則。所有理論上可更新的視圖也應(yīng)該允許由系統(tǒng)更新。準(zhǔn)則7：高級(jí)的插入、修改、刪除操作。以關(guān)系為對(duì)象進(jìn)行操作準(zhǔn)則8：數(shù)據(jù)物理獨(dú)立性準(zhǔn)則9：數(shù)據(jù)邏輯獨(dú)立性準(zhǔn)則10：數(shù)據(jù)完整性的獨(dú)立性。用DDL定義并存儲(chǔ)在數(shù)據(jù)字典中，獨(dú)立于應(yīng)用程序準(zhǔn)則11：分布獨(dú)立性準(zhǔn)則12：無破壞準(zhǔn)則第6頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

查詢處理的過程查詢語句查詢輸出關(guān)系代數(shù)表達(dá)式執(zhí)行計(jì)劃語法分析與翻譯執(zhí)行引擎優(yōu)化器數(shù)據(jù)有關(guān)數(shù)據(jù)的統(tǒng)計(jì)信息第7頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

實(shí)際系統(tǒng)的查詢優(yōu)化步驟1.將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹2.根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3.選擇低層的操作算法對(duì)于語法樹中的每一個(gè)操作根據(jù)存取路徑、數(shù)據(jù)的尺寸、數(shù)據(jù)的存儲(chǔ)分布、存儲(chǔ)數(shù)據(jù)的聚簇等信息來計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)選擇代價(jià)小的執(zhí)行算法4.生成查詢計(jì)劃(查詢執(zhí)行方案)第8頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

常用查詢優(yōu)化技術(shù)用啟發(fā)式規(guī)則來縮減查詢計(jì)劃的搜索空間利用統(tǒng)計(jì)信息估算執(zhí)行代價(jià)基于代價(jià)

●代價(jià)模型集中式數(shù)據(jù)庫單用戶系統(tǒng)：總代價(jià)=I/O代價(jià)+CPU代價(jià)多用戶系統(tǒng)：總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)分布式數(shù)據(jù)庫 總代價(jià)=I/O代價(jià)+CPU代價(jià)[+內(nèi)存代價(jià)]+通信代價(jià)第9頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

一個(gè)實(shí)例:求選C2課程的學(xué)生名SELECTSNAMEFROM Student，SCWHEREStudent.Sno=SC.Sno

ANDCno=‘C2’；外存： Student:1000條,SC:10000條,選修2號(hào)課程:50條一個(gè)內(nèi)存塊裝元組:10個(gè)Student,或100個(gè)SC,內(nèi)存中一次可以存放:5塊Student元組,1塊SC元組和若干塊連接結(jié)果元組讀寫速度：20塊/秒連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法假設(shè)第10頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

一個(gè)實(shí)例1.Ｑ1＝ПSname(бStudent.Sno=SC.Sno∧SC.Cno=‘c2‘(Student×SC))

①Student×SC讀取總塊數(shù)=讀Student表塊數(shù)+讀SC表遍數(shù)*每遍塊數(shù) =1000/10+(1000/(10×5))×(10000/100)=2100讀數(shù)據(jù)時(shí)間=2100/20=105秒 中間結(jié)果大小=1000*10000=107(1千萬條元組)寫中間結(jié)果時(shí)間=10000000/10/20=50000秒

②б 讀數(shù)據(jù)時(shí)間=50000秒

③П總時(shí)間=105＋50000＋50000秒=100105秒=27.8小時(shí)第11頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))① 讀取總塊數(shù)=2100塊 讀數(shù)據(jù)時(shí)間=2100/20=105秒 中間結(jié)果大小=10000（減少1000倍） 寫中間結(jié)果時(shí)間=10000/10/20=50秒

②б

讀數(shù)據(jù)時(shí)間=50秒

③П

總時(shí)間＝105＋50＋50秒＝205秒=3.4分

●

一個(gè)實(shí)例第12頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述3.Ｑ2＝ПSname(StudentбSC.Cno='2'(SC))

①б 讀SC表總塊數(shù)=10000/100=100塊 讀數(shù)據(jù)時(shí)間=100/20=5秒

中間結(jié)果大小=50條不必寫入外存

② 讀Student表總塊數(shù)=1000/10=100塊 讀數(shù)據(jù)時(shí)間=100/20=5秒

③П

總時(shí)間＝5＋5秒＝10秒

●

一個(gè)實(shí)例第13頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的一般準(zhǔn)則選擇運(yùn)算應(yīng)盡可能先做

在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理投影運(yùn)算和選擇運(yùn)算同時(shí)做將投影運(yùn)算與其前后的雙目運(yùn)算結(jié)合選擇運(yùn)算和笛卡爾積運(yùn)算結(jié)合提取公共子表達(dá)式第14頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)等價(jià)變換規(guī)則l.連接、笛卡爾積交換律2.連接、笛卡爾積的結(jié)合律3.投影的串接定律4.選擇的串接定律5.選擇與投影的交換律6.選擇與笛卡爾積的交換律7.選擇與并的交換8.選擇與差運(yùn)算的交換9.投影與笛卡爾積的交換l0.投影與并的交換第15頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達(dá)式的優(yōu)化算法分解選擇運(yùn)算通過交換選擇運(yùn)算，將其盡可能移到葉端通過交換投影運(yùn)算，將其盡可能移到葉端合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成對(duì)內(nèi)結(jié)點(diǎn)分組生成程序第16頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示2．代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3．物理優(yōu)化：選擇低層的存取路徑4．生成查詢計(jì)劃，選擇代價(jià)最小的第17頁，共19頁，2023年，2月20日，星期三9.2關(guān)系系統(tǒng)的查詢優(yōu)化優(yōu)化的一般步驟student.Sno=Sc.SnoSc.Sno=‘2’XStudentSCSnamexstudent.Sno=Sc.SnoSc.Sno=‘2’SnameSCStudentstudentSCJoin(student.Sno=SC.Sno)Selec