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

*數(shù)據(jù)庫原理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ù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式的優(yōu)化算法優(yōu)化的一般步驟*數(shù)據(jù)庫原理24.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)算，且不要求用戶定義任何物理存取路徑4.1.1關(guān)系系統(tǒng)的定義*數(shù)據(jù)庫原理34.1.2關(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)，不支持集合級(jí)的操作。（不能算關(guān)系系統(tǒng)）2．（最?。╆P(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,…屬于這一類。*數(shù)據(jù)庫原理4關(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)√√√*數(shù)據(jù)庫原理54.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ù)*數(shù)據(jù)庫原理64.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ù)*數(shù)據(jù)庫原理7系統(tǒng)優(yōu)化優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，從而選擇有效的執(zhí)行計(jì)劃；如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢進(jìn)行重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃；優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃；優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)。*數(shù)據(jù)庫原理8實(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í)行方案)*數(shù)據(jù)庫原理9

常用查詢優(yōu)化技術(shù)用啟發(fā)式規(guī)則來縮減查詢計(jì)劃的搜索空間利用統(tǒng)計(jì)信息估算執(zhí)行代價(jià)基于代價(jià)（目前商品化RDBMS大都采用）代價(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à)*數(shù)據(jù)庫原理104.2.2一個(gè)實(shí)例例.求選2號(hào)課程的學(xué)生姓名SELECTStudent.SnameFROM Student，SCWHEREStudent.Sno=SC.SnoANDCno=‘2’；數(shù)據(jù)量：Student:1000條；SC:10000條；選修2號(hào)課程:50條一個(gè)內(nèi)存塊裝元組:10個(gè)Student或100個(gè)SC，內(nèi)存中可以存放:5塊Student元組和1塊SC元組讀寫速度：20塊/秒假設(shè)：*數(shù)據(jù)庫原理111.Ｑ1＝ПSname(бStudent.Sno=SC.Sno∧SC.Cno=‘c2‘

(Student×SC))

①計(jì)算廣義笛卡爾積(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í)*數(shù)據(jù)庫原理121.Ｑ1＝ПSname(бStudent.Sno=SC.Sno∧SC.Cno=‘c2‘

(Student×SC))

①計(jì)算廣義笛卡爾積(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í)*數(shù)據(jù)庫原理132.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))①自然連接()

讀取總塊數(shù)=2100塊 讀數(shù)據(jù)時(shí)間=2100/20=105秒 中間結(jié)果大小=10000（即SC表中記錄條數(shù)，減少1000倍） 寫中間結(jié)果時(shí)間=10000/10/20=50秒

②選擇操作(б)

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

③投影(П)

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

*數(shù)據(jù)庫原理143.Ｑ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秒

*數(shù)據(jù)庫原理154.2.3查詢優(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é)合（等值連接比笛卡兒積省時(shí)間）提取公共子表達(dá)式（例如，定義視圖的表達(dá)式）*數(shù)據(jù)庫原理164.2.4關(guān)系代數(shù)等價(jià)變換規(guī)則l.連接、笛卡爾積交換律2.連接、笛卡爾積的結(jié)合律3.投影的串接定律4.選擇的串接定律5.選擇與投影的交換律6.選擇與笛卡爾積的交換律7.選擇與并的交換8.選擇與差運(yùn)算的交換9.投影與笛卡爾積的交換l0.投影與并的交換*數(shù)據(jù)庫原理174.2.5關(guān)系代數(shù)表達(dá)式的優(yōu)化算法分解選擇運(yùn)算通過交換選擇運(yùn)算，將其盡可能移到葉端通過交換投影運(yùn)算，將其盡可能移到葉端合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成對(duì)內(nèi)結(jié)點(diǎn)分組生成程序*數(shù)據(jù)庫原理184.2.5關(guān)系代數(shù)表達(dá)式的優(yōu)化算法分解選擇運(yùn)算通過交換選擇運(yùn)算，將其盡可能移到葉端通過交換投影運(yùn)算，將其盡可能移到葉端合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成對(duì)內(nèi)結(jié)點(diǎn)分組生成程序*數(shù)據(jù)庫原理194.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ì)劃，選擇代價(jià)最小的*數(shù)據(jù)庫原理20StudentSCJoin(Student.Sno=SC.Sno)Select(SC.Cno=‘2’)Project(Sname)結(jié)果

Student.Sno=Sc.Sno

S