查詢處理與查詢 優化,目 錄,查詢處理,查詢優化,查詢處理,查詢處理(query processing)是指從數據庫中提取數據時所涉及的一系列活動。 語法分析與翻譯 查詢優化 查詢執行,查詢處理過程,語法分析與翻譯器 查詢處理開始之前，系統必須將查詢語句翻譯成可使用的形式。 語法分析與翻譯階段的主要工作有： 檢查用戶查詢的語法，利用數據字典驗證查詢中出現的關系名、屬性名等是否正確； 構造該查詢語句的語法分析樹表示，并將其翻譯成關系代數表達式。,查詢處理過程,查詢執行計劃與查詢優化器 一個給定的查詢任務，一般都會有多種計算結果的方法 例如，考慮如下查詢 select studentName from Student where classNo=CS0701 and sex=女 該查詢語句可翻譯成如下關系表達式中的任意一個 classNo=CS0701(sex=女(studentName(Student) sex=女(classNo=CS0701(studentName(Student) classNo=CS0701(studentName(sex=女(Student) studentName(sex=女(classNo=CS0701(Student),查詢處理過程,查詢執行計劃與查詢優化器 執行一個查詢，不僅需要提供關系代數表達式，還要對該表達式加上注釋說明如何執行每個操作 加了“如何執行”注釋的關系代數運算稱為執行原語 用于執行一個查詢的原語操作序列稱為查詢執行計劃 不同的查詢執行計劃會有不同的代價 構造具有最小查詢執行代價的查詢執行計劃是DBMS的責任 這項工作稱為查詢優化，由查詢優化器來完成,查詢處理過程,關系數據庫系統和非過程化的SQL語言能夠取得巨大成功關鍵是得益于查詢優化技術的發展 查詢優化是影響RDBMS性能的關鍵因素 查詢執行引擎 根據輸入的查詢執行計劃，調用相關算法實現查詢計算，并將計算結果返回給用戶 有效地對內存緩沖區進行管理是影響查詢執行性能的非常重要的方面,目 錄,查詢處理,查詢優化,查詢優化,處理一個給定的查詢，尤其是復雜的查詢，通常會有許多種策略。 查詢優化(query optimization)就是從這許多策略中找出最有效的查詢執行計劃的處理過程。 RDBMS能夠構造并選擇出一個具有最小查詢執行代價的查詢執行計劃,查詢優化的必要性,不同查詢執行計劃的執行時間分析 Q1 =SN(s.s# = sc.s# sc.c# = c2(SSC) Q2 =SN(sc.c# = c2(S SC) Q3 =SN(S sc.c# = c2(SC),（1）第一種情況 計算廣義笛卡爾積 作選擇操作 作投影操作 執行總時間為105s,（2）第二種情況 計算自然連接 作選擇操作 作投影操作 執行總時間為205s,（3）第三種情況 先對SC作選擇運算 作連接運算 作投影操作 執行總時間為10s,查詢優化概述, 例：找出2008級修讀“數據庫系統概論”課程的學生姓名。初始關系表達式為： studentName(grade=2008courseName=DB(Class Student) (Score Course), 轉換后的關系代數表達式為： studentName(grade=2008(Class) Student) (Score courseName=DB(Course),查詢優化概述, 查詢優化分3步進行 邏輯優化，產生邏輯上與給定關系代數表達式等價的表達式； 代價估計，估計每個執行計劃的代價； 物理優化，對所產生的表達式以不同方式作注釋，產生不同的查詢執行計劃。 查詢優化器中第步和第步是交叉進行的 先產生一些等價的表達式并加以注釋 再進一步產生一些等價表達式并加以注釋，依此類推 第步是基于系統收集的一些統計信息，如關系的大小、屬性值的分布、B+樹索引的深度等，對一個執行計劃的代價進行事先估計,關系表達式轉換, 等價規則 合取選擇運算的級聯分解 選擇運算滿足交換律 系列投影的最后有效性 選擇操作與連接相結合 =E1 E2 ,等價規則,連接運算的結合律 自然連接運算的結合律： (E1 E2) E3 = E1 (E2 E3) 連接運算的結合律：(E1 E2) E3 = E1 (E2 E3) 選擇運算對連接運算的分配律 選擇條件0的所有屬性只涉及連接的表達式之一時，滿足分配律 E2) = E2 當選擇條件1只涉及E1的屬性，且選擇條件2只涉及E2的屬性時滿足分配律 E2) = ,等價規則,投影運算對連接運算的分配律 令A1、A2分別代表E1、E2的屬性，假設連接條件只涉及A1A2中的屬性，則 E2) = 令A1、A2分別代表E1、E2的屬性；令A3是E1中出現在連接條件中但不在A1A2中的屬性；令A4是E2中出現在連接條件中但不在A1A2中的屬性 E2 ) = ,關系表達式轉換, 轉換實例 studentName(grade=2008courseName=DB(Class Student) (Score Course) studentName(grade=2008(Class) Student) Score) courseName=DB(Course) 步驟： 應用等價規劃(1) ，表達式可以轉換為 studentName(grade=2008(courseName=DB(Class Student) (Score Course) 兩次應用等價規劃(7)的第條 ，表達式可以轉換為 studentName(grade=2008(Class Student) courseName=DB(Score Course),轉換實例,studentName(grade=2008courseName=DB(Class Student) (Score Course) studentName(grade=2008(Class) Student) Score) courseName=DB(Course) 步驟： 再應用兩次等價規劃(7)的第條，表達式可以轉換為 studentName(grade=2008(Class) Student) (courseName=DB(Score) Course) 第四，應用等價規劃(5)，表達式可以轉換為 studentName(grade=2008(Class) Student) (Course courseName=DB(Score) 應用等價規劃(6)的第條， 得到