1、關系系統及其查詢優化 第4章 關系系統 關系系統的定義 關系系統的分類 關系系統的查詢優化 關系系統及其查詢優化 查詢優化的一般準則 關系代數等價變換規則 關系代數表達式的優化算法 優化的一般步驟 2022/10/171數據庫原理關系系統及其查詢優化 第4章 關系系統2022/10/1514.1 關系系統支持關系模型的關系數據庫管理系統簡稱關系系統。 下述關系的DBMS不能稱為關系系統 不支持關系數據結構的系統 支持關系數據結構，但無、 運算功能的系統 支持關系數據結構，有、 運算，但要求定義物理 存取路徑的系統可稱為關系系統的DBMS，當且僅當1）支持關系數據結構（關系數據庫）2）支持、 運

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

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

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

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

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

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

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

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

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