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

*數(shù)據(jù)庫原理1關系系統(tǒng)及其查詢優(yōu)化第4章

關系系統(tǒng)

關系系統(tǒng)的定義關系系統(tǒng)的分類

關系系統(tǒng)的查詢優(yōu)化關系系統(tǒng)及其查詢優(yōu)化查詢優(yōu)化的一般準則關系代數(shù)等價變換規(guī)則關系代數(shù)表達式的優(yōu)化算法優(yōu)化的一般步驟*數(shù)據(jù)庫原理24.1關系系統(tǒng)支持關系模型的關系數(shù)據(jù)庫管理系統(tǒng)簡稱關系系統(tǒng)。下述關系的DBMS不能稱為關系系統(tǒng)不支持關系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)支持關系數(shù)據(jù)結(jié)構(gòu)，但無δ、π、運算功能的系統(tǒng)支持關系數(shù)據(jù)結(jié)構(gòu)，有δ、π、運算，但要求定義物理存取路徑的系統(tǒng)可稱為關系系統(tǒng)的DBMS，當且僅當1）支持關系數(shù)據(jù)結(jié)構(gòu)（關系數(shù)據(jù)庫）2）支持δ、π、運算，且不要求用戶定義任何物理存取路徑4.1.1關系系統(tǒng)的定義*數(shù)據(jù)庫原理34.1.2關系系統(tǒng)的分類4．全關系系統(tǒng)：

支持關系模型的所有特征。在關系完備系統(tǒng)的基礎上，進一步支持實體完整性和參照完整性等。DBⅡ,ORACLE,SYBASE,…已接近這個目標。目前尚無全關系系統(tǒng)。1．表式系統(tǒng)：僅支持關系數(shù)據(jù)結(jié)構(gòu)，不支持集合級的操作。（不能算關系系統(tǒng)）2．（最?。╆P系系統(tǒng)：

支持關系數(shù)據(jù)結(jié)構(gòu)，支持δ、π、運算，且不定義物理路徑。3．關系完備系統(tǒng)：

支持關系數(shù)據(jù)結(jié)構(gòu)和所有關系代數(shù)操作（或功能上與關系代數(shù)等價）。DBⅡ,ORACLE,SYBASE,…屬于這一類。*數(shù)據(jù)庫原理4關系系統(tǒng)分類數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作完整性約束表式系統(tǒng)表××(最小)關系系統(tǒng)表選擇、投影、連接×關系完備的系統(tǒng)表√×全關系系統(tǒng)√√√*數(shù)據(jù)庫原理54.2關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化4.2.1關系系統(tǒng)及其查詢優(yōu)化查詢處理的過程查詢語句查詢輸出關系代數(shù)表達式執(zhí)行計劃語法分析與翻譯執(zhí)行引擎優(yōu)化器有關數(shù)據(jù)的統(tǒng)計信息數(shù)據(jù)*數(shù)據(jù)庫原理64.2關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化4.2.1關系系統(tǒng)及其查詢優(yōu)化查詢處理的過程查詢語句查詢輸出關系代數(shù)表達式執(zhí)行計劃語法分析與翻譯執(zhí)行引擎優(yōu)化器有關數(shù)據(jù)的統(tǒng)計信息數(shù)據(jù)*數(shù)據(jù)庫原理7系統(tǒng)優(yōu)化優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，從而選擇有效的執(zhí)行計劃；如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢進行重新優(yōu)化以選擇相適應的執(zhí)行計劃；優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃；優(yōu)化器中包括了很多復雜的優(yōu)化技術(shù)。*數(shù)據(jù)庫原理8實際系統(tǒng)的查詢優(yōu)化步驟1.將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹2.根據(jù)一定的等價變換規(guī)則把語法樹轉(zhuǎn)換成標準（優(yōu)化）形式3.選擇低層的操作算法對于語法樹中的每一個操作根據(jù)存取路徑、數(shù)據(jù)的尺寸、數(shù)據(jù)的存儲分布、存儲數(shù)據(jù)的聚簇等信息來計算各種執(zhí)行算法的執(zhí)行代價選擇代價小的執(zhí)行算法4.生成查詢計劃(查詢執(zhí)行方案)*數(shù)據(jù)庫原理9

常用查詢優(yōu)化技術(shù)用啟發(fā)式規(guī)則來縮減查詢計劃的搜索空間利用統(tǒng)計信息估算執(zhí)行代價基于代價（目前商品化RDBMS大都采用）代價模型

集中式數(shù)據(jù)庫單用戶系統(tǒng)：總代價=I/O代價+CPU代價多用戶系統(tǒng)：總代價=I/O代價+CPU代價+內(nèi)存代價分布式數(shù)據(jù)庫 總代價=I/O代價+CPU代價[+內(nèi)存代價]+通信代價*數(shù)據(jù)庫原理104.2.2一個實例例.求選2號課程的學生姓名SELECTStudent.SnameFROM Student，SCWHEREStudent.Sno=SC.SnoANDCno=‘2’；數(shù)據(jù)量：Student:1000條；SC:10000條；選修2號課程:50條一個內(nèi)存塊裝元組:10個Student或100個SC，內(nèi)存中可以存放:5塊Student元組和1塊SC元組讀寫速度：20塊/秒假設：*數(shù)據(jù)庫原理111.Ｑ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ù)時間=2100/20=105秒 中間結(jié)果大小=1000*10000=107(1千萬條元組)

寫中間結(jié)果時間=10000000/10/20=50000秒

②選擇操作(б) 讀數(shù)據(jù)時間=50000秒

③投影(П)總時間=105＋50000＋50000秒=100105秒=27.8小時*數(shù)據(jù)庫原理121.Ｑ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ù)時間=2100/20=105秒 中間結(jié)果大小=1000*10000=107(1千萬條元組)

寫中間結(jié)果時間=10000000/10/20=50000秒

②選擇操作(б) 讀數(shù)據(jù)時間=50000秒

③投影(П)總時間=105＋50000＋50000秒=100105秒=27.8小時*數(shù)據(jù)庫原理132.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))①自然連接()

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

②選擇操作(б)

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

③投影(П)

總時間＝105＋50＋50秒＝205秒=3.4分

*數(shù)據(jù)庫原理143.Ｑ2＝ПSname(StudentбSC.Cno='2'(SC))

①選擇操作(б)

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

中間結(jié)果大小=50條（不必使用中間文件）

②自然連接（） 讀Student表總塊數(shù)=1000/10=100塊 讀數(shù)據(jù)時間=100/20=5秒

③投影(П)

總時間＝5＋5秒＝10秒

*數(shù)據(jù)庫原理154.2.3查詢優(yōu)化的一般準則選擇運算應盡可能先做

在執(zhí)行連接操作前對關系適當進行預處理（索引連接方法和排序合并連接方法）投影運算和選擇運算同時做將投影運算與其前后的雙目運算結(jié)合（連接、并、差、交等）選擇運算和笛卡爾積運算結(jié)合（等值連接比笛卡兒積省時間）提取公共子表達式（例如，定義視圖的表達式）*數(shù)據(jù)庫原理164.2.4關系代數(shù)等價變換規(guī)則l.連接、笛卡爾積交換律2.連接、笛卡爾積的結(jié)合律3.投影的串接定律4.選擇的串接定律5.選擇與投影的交換律6.選擇與笛卡爾積的交換律7.選擇與并的交換8.選擇與差運算的交換9.投影與笛卡爾積的交換l0.投影與并的交換*數(shù)據(jù)庫原理174.2.5關系代數(shù)表達式的優(yōu)化算法分解選擇運算通過交換選擇運算，將其盡可能移到葉端通過交換投影運算，將其盡可能移到葉端合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成對內(nèi)結(jié)點分組生成程序*數(shù)據(jù)庫原理184.2.5關系代數(shù)表達式的優(yōu)化算法分解選擇運算通過交換選擇運算，將其盡可能移到葉端通過交換投影運算，將其盡可能移到葉端合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成對內(nèi)結(jié)點分組生成程序*數(shù)據(jù)庫原理194.2.6優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示2．代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標準（優(yōu)化）形式3．物理優(yōu)化：選擇低層的存取路徑4．生成查詢計劃，選擇代價最小的*數(shù)據(jù)庫原理20StudentSCJoin(Student.Sno=SC.Sno)Select(SC.Cno=‘2’)Project(Sname)結(jié)果

Student.Sno=Sc.Sno

S