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

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