查詢處理與優(yōu)化課件

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