數(shù)據(jù)庫(kù)上課 第十三講 查詢處理、優(yōu)化

1、機(jī)械自動(dòng)化學(xué)院機(jī)械自動(dòng)化學(xué)院20152015主講：主講： 顧顧 曦曦 電話：電話：1569718107915697181079EmailEmail：主要內(nèi)容*2查詢處理查詢處理查詢優(yōu)化查詢優(yōu)化*3Profile簡(jiǎn)介Profile 是在Mysql5.1以后版本引入，來(lái)源于開源社區(qū)Jeremy Cole的貢獻(xiàn)。當(dāng)一條查詢提交給服務(wù)器時(shí)，此工具會(huì)記錄剖析信息到一張臨時(shí)表，并且給查詢賦予一個(gè)整數(shù)標(biāo)識(shí)符。剖析信息包含數(shù)據(jù)庫(kù)對(duì)某個(gè)查詢的詳細(xì)執(zhí)行情況，對(duì)于分析和優(yōu)化查詢，提高數(shù)據(jù)庫(kù)的性能很有幫助。Profile工具的使用啟動(dòng)數(shù)據(jù)庫(kù)，登錄客戶端；使用數(shù)據(jù)庫(kù)scoreDBmysql use scoredb；啟動(dòng)

2、查詢刨析工具：mysql set profiling = 1;執(zhí)行查詢mysql select * from student;查看執(zhí)行時(shí)間信息（單位：秒）mysql show profiles；*5查看詳細(xì)信息*6 推薦書目高性能高性能MySQL（第（第3版）版）Baron Schwartz，Peter Zaitsev，Vadim Tkachenko 著寧海元，周振興，彭立勛，等 譯電子工業(yè)出版社 2013-5*7*81.1 概述查詢處理(query processing)是指從數(shù)據(jù)庫(kù)中提取數(shù)據(jù)時(shí)所涉及的一系列活動(dòng)。用高層數(shù)據(jù)庫(kù)語(yǔ)言(如SQL)表示的查詢語(yǔ)句翻譯成能在文件系統(tǒng)的物理層上使用的表

3、達(dá)式。為優(yōu)化查詢而進(jìn)行的各種轉(zhuǎn)換以及查詢的實(shí)際執(zhí)行 。查詢處理的主要過程包括： 語(yǔ)法分析與翻譯語(yǔ)法分析與翻譯 查詢優(yōu)化查詢優(yōu)化 查詢執(zhí)行查詢執(zhí)行1） 語(yǔ)法分析與翻譯器查詢處理開始之前，系統(tǒng)將查詢語(yǔ)句查詢語(yǔ)句翻譯成可使用的形式。 語(yǔ)法分析與翻譯階段的主要工作有：檢查用戶查詢的語(yǔ)法，利用數(shù)據(jù)字典驗(yàn)證查詢中出現(xiàn)的關(guān)系名、屬性名等是否正確；構(gòu)造該查詢語(yǔ)句的語(yǔ)法分析樹表示，并將其翻譯成關(guān)系代數(shù)表達(dá)式關(guān)系代數(shù)表達(dá)式。 2） 查詢執(zhí)行計(jì)劃與查詢優(yōu)化器一個(gè)給定的查詢?nèi)蝿?wù)，一般都會(huì)有多種計(jì)算結(jié)果的方法 例如，考慮如下查詢 select studentName from Student where classNo

4、=CS0701 and sex=女 該查詢語(yǔ)句可翻譯成如下關(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í)行一個(gè)查詢，不僅需要提供關(guān)系代數(shù)表達(dá)式，還要對(duì)該表達(dá)式加上注釋來(lái)說(shuō)明如何執(zhí)行每個(gè)操作。加了“如何執(zhí)行”注釋的關(guān)系代數(shù)運(yùn)算稱為執(zhí)行原語(yǔ)。用于執(zhí)行一個(gè)查詢的原語(yǔ)操作序列操作序列稱為查詢執(zhí)行計(jì)劃。

5、不同的查詢執(zhí)行計(jì)劃會(huì)有不同的代價(jià)。DBMS通過查詢優(yōu)化器構(gòu)造具有最小查詢執(zhí)行代價(jià)的查詢執(zhí)行計(jì)劃，稱為查詢優(yōu)化查詢優(yōu)化。 查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素。關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)和非過程化的SQL語(yǔ)言能夠取得巨大成功關(guān)鍵是得益于查詢優(yōu)化技術(shù)的發(fā)展。3） 查詢執(zhí)行引擎查詢執(zhí)行引擎查詢執(zhí)行引擎根據(jù)輸入的查詢執(zhí)行計(jì)劃，調(diào)用相關(guān)算法實(shí)現(xiàn)查詢計(jì)算，并將計(jì)算結(jié)果返回給用戶。 有效地對(duì)內(nèi)存緩沖區(qū)內(nèi)存緩沖區(qū)進(jìn)行管理是影響查詢執(zhí)行性能的非常重要的方面。 *142.1 概述查詢處理的代價(jià)可以通過該查詢對(duì)各種資源的使用情況進(jìn)行度量。主要包括磁盤存取時(shí)間磁盤存取時(shí)間執(zhí)行一個(gè)查詢所用的執(zhí)行一個(gè)查詢所用的CPU時(shí)間、時(shí)間、在

6、并行在并行/分布式數(shù)據(jù)庫(kù)系統(tǒng)中的通信開銷等分布式數(shù)據(jù)庫(kù)系統(tǒng)中的通信開銷等對(duì)于大型數(shù)據(jù)庫(kù)系統(tǒng)而言，在磁盤上存取數(shù)據(jù)的代價(jià)在磁盤上存取數(shù)據(jù)的代價(jià)通常是最重要的代價(jià) ，可以通過傳輸磁盤塊數(shù)以及搜索磁盤次數(shù)來(lái)度量。 在代價(jià)估算時(shí)，通常假定是最壞的情形。 大型數(shù)據(jù)庫(kù)系統(tǒng)最重要的代價(jià)通常是在磁盤上存取數(shù)據(jù)的代價(jià)，通過傳輸磁盤塊數(shù)以及搜索磁盤次數(shù)來(lái)度量。 例如：一個(gè)傳輸b塊并作s次磁盤搜索的操作將耗時(shí)btT+stS （毫秒（毫秒(ms)）其中：tT：傳輸一塊數(shù)據(jù)的平均耗時(shí) tS：搜索一次磁盤的平均定位時(shí)間(包括搜索時(shí)間加旋轉(zhuǎn)時(shí)間)*16查詢優(yōu)化器利用存儲(chǔ)在DBMS的數(shù)據(jù)字典中的統(tǒng)計(jì)信息統(tǒng)計(jì)信息來(lái)估算查詢執(zhí)行

7、計(jì)劃的代價(jià)，相關(guān)的統(tǒng)計(jì)信息主要包括： nr：關(guān)系r中的元組數(shù)目。 br：用于存儲(chǔ)關(guān)系r所有元組的塊數(shù)目。 lr：關(guān)系r中一個(gè)元組的大小。 fr：關(guān)系r的塊因子，即一個(gè)物理塊中能存放的關(guān)系r的元組數(shù)目。 V(A, r)：關(guān)系r中屬性A所具有的不同值的數(shù)目，該數(shù)目與A(r)的大小相同。若A為關(guān)系r的碼，則V(A, r)=nr。 SC(A, r)：關(guān)系r關(guān)于屬性A的選擇度，表示在屬性A上滿足某個(gè)等值條件（假設(shè)至少有一條記錄滿足該等值條件）的平均記錄數(shù)平均記錄數(shù)。若A為關(guān)系r的碼，則SC(A, r)=1；若A為非碼屬性，并假定V(A, r)上不同的值在所有元組中平均分配，則SC(A, r)=nr/V(

8、A, r)。 HTi：索引i的層數(shù)，即高度。2.2 選擇運(yùn)算用于選擇運(yùn)算的搜索算法： 1) 文件掃描：不用索引的搜索算法線性搜索算法 A1二分搜索算法 A2 2) 索引掃描：使用索引的搜索算法在主索引的碼屬性上的等值比較算法 A3在主索引的非碼屬性上的等值比較算法 A4在輔助索引上的等值比較算法 A5在主索引上的范圍比較算法 A6在輔助索引上的范圍比較算法 A71)選擇運(yùn)算文件掃描文件掃描：用于定位、檢索滿足選擇條件的記錄線性搜索算法A1 線性搜索中，系統(tǒng)掃描每一個(gè)文件塊，對(duì)所有記錄進(jìn)行測(cè)試，看它們是否滿足選擇條件。開始時(shí)需作一次磁盤搜索來(lái)定位文件的第一個(gè)塊。 線性搜索的代價(jià)為EA1=br*t

9、T+tS，其中br代表文件中的磁盤塊數(shù)。 *19線性搜索算法A1 的優(yōu)缺點(diǎn)*20二分搜索算法A2關(guān)于搜索碼物理有序存儲(chǔ)，搜索過程是針對(duì)文件的磁盤塊進(jìn)行，而不是針對(duì)記錄進(jìn)行最壞情況下，找到包含所需記錄的磁盤塊所需訪問和檢查的磁盤塊數(shù)目為log2(br) ，而且每一個(gè)這樣的磁盤塊都需要一次磁盤搜索定位，因此算法A2的時(shí)間代價(jià)為 EA2= log2(br) *(tT+tS)如果是在非碼屬性上的選擇操作，那么可能會(huì)有多個(gè)塊包含所需記錄，這樣還需順序讀取包含選擇結(jié)果的額外塊，估計(jì)有 SC(A, r)/fr -1個(gè)額外塊 。*212）選擇運(yùn)算索引掃描主索引碼屬性上的等值比較算法主索引碼屬性上的等值比較算法

10、 A3 具有主索引的碼屬性上的等值比較算法，可以通過主索引檢索到指向滿足相應(yīng)等值條件的唯一唯一記錄的指針，再根據(jù)該指針到數(shù)據(jù)文件中訪問磁盤塊。若使用B+樹索引，則訪問索引塊的數(shù)量等于樹高度HTi，訪問文件塊的數(shù)量為1；而且每一次I/O操作都需要一次磁盤搜索定位和一次磁盤塊傳輸。因此，算法A3的時(shí)間代價(jià)為： EA3= HTi+1 *(tT+tS)*22主索引非碼屬性上的等值比較算法 A4 通過主索引檢索到指向滿足相應(yīng)等值條件的第一條記錄（可能有多條記錄，但它們?cè)谖锢砩享樞虼娣牛┑闹羔?，再根?jù)該指針到數(shù)據(jù)文件中訪問磁盤塊。 需要訪問的文件塊的數(shù)目可估計(jì)為： b= SC(A, r)/fr 算法A4的

11、時(shí)間代價(jià)為 EA4= HTi+1 *(tT+tS)+( SC(A, r)/fr -1)*tT*23輔助索引的等值比較算法A5 如果是碼屬性上的等值條件，算法A5的時(shí)間代價(jià)與算法A3相同。 如果是非碼屬性上的等值條件，則通過輔助索引可以檢索到存放滿足相應(yīng)等值條件的多條記錄的指針桶的指針，再根據(jù)該指針桶中的每一個(gè)指針分別到數(shù)據(jù)文件中訪問包含相應(yīng)記錄的文件塊。 最壞情況下，算法A5的時(shí)間代價(jià)為： EA5= HTi+1+SC(A, r) *(tT+tS) 其中的加1是表示訪問指針桶的代價(jià)。 *24主索引上的范圍比較算法A6 對(duì)于形如Av或Av的比較條件，首先通過主索引（如B+樹索引）搜索，定位在滿足A

12、v或Av條件的第一個(gè)索引項(xiàng)第一個(gè)索引項(xiàng)，該索引項(xiàng)中的指針指向滿足查詢條件的所有記錄中的第一條。然后通過該指針到文件中搜索磁盤塊，并從該磁盤塊開始順序訪問所有的磁盤塊，直到文件結(jié)束。其時(shí)間代價(jià)可估算為（SC(P(A), r)表示滿足謂詞P(A)的選擇度） EA6= HTi+1 *(tT+tS)+ ( SC(P(A), r)/fr -1)*tT 對(duì)于形如Av或Av的比較條件A=90(Score) classNo=CS0701(Student)*442.5 其他運(yùn)算排序外部排序歸并(external sort-merge，ESM)算法 去除重復(fù)元組 投影集合運(yùn)算聚集運(yùn)算 *45*463.1 概述查詢

13、優(yōu)化(query optimization):處理一個(gè)給定的查詢，尤其是復(fù)雜的查詢，通常會(huì)有許多種策略。從這許多策略中找出最有效的查詢執(zhí)行計(jì)劃的處理過程。 由于關(guān)系表達(dá)式的語(yǔ)義級(jí)別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義，提供了執(zhí)行查詢優(yōu)化的可能性 關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素;查詢優(yōu)化的特點(diǎn)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，可以考慮數(shù)百種不同的執(zhí)行計(jì)劃優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可

14、能的。3.1.2 查詢優(yōu)化器作用：通過某種代價(jià)模型計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案。代價(jià)包括集中式數(shù)據(jù)庫(kù)磁盤存取塊數(shù)磁盤存取塊數(shù)(I/O代價(jià)代價(jià))（主要）（主要）處理機(jī)時(shí)間處理機(jī)時(shí)間(CPU代價(jià)代價(jià))查詢的內(nèi)存開銷查詢的內(nèi)存開銷 分布式數(shù)據(jù)庫(kù)總代價(jià)總代價(jià)=I/O代價(jià)代價(jià)+CPU代價(jià)代價(jià)+內(nèi)存代價(jià)內(nèi)存代價(jià)通信代價(jià)通信代價(jià) 3.1.3查詢優(yōu)化的總目標(biāo)：選擇有效的策略求得給定關(guān)系表達(dá)式的值使得查詢代價(jià)最小(實(shí)際上是較小) 3.2 查詢優(yōu)化的類型邏輯優(yōu)化邏輯優(yōu)化：產(chǎn)生邏輯上與給定關(guān)系代數(shù)表達(dá)式等價(jià)的表達(dá)式；代價(jià)估計(jì)代價(jià)估計(jì)：基于系統(tǒng)收集的一些統(tǒng)計(jì)信息，如關(guān)系的大小、屬性值的

15、分布、B+樹索引的深度等，對(duì)一個(gè)執(zhí)行計(jì)劃的代價(jià)進(jìn)行事先估計(jì)。物理優(yōu)化物理優(yōu)化：對(duì)所產(chǎn)生的表達(dá)式以不同方式作注釋注釋，產(chǎn)生不同的查詢執(zhí)行計(jì)劃。 在查詢優(yōu)化器中第1步和第3步是交叉進(jìn)行的*513.2.1 代數(shù)優(yōu)化定義：基于關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化方法。方法：關(guān)系表達(dá)式轉(zhuǎn)換(參看課本本章和關(guān)系代數(shù)一章)查詢樹的啟發(fā)式優(yōu)化 優(yōu)化重點(diǎn)：連接運(yùn)算的次序 一個(gè)好的連接運(yùn)算次序?qū)τ跍p少中間結(jié)果的大小非常重要，也會(huì)影響到連接算法的選擇。大部分查詢優(yōu)化器在連接運(yùn)算的次序上花了很多功夫。*52例找出2008級(jí)修讀“數(shù)據(jù)庫(kù)系統(tǒng)概論”課程的學(xué)生姓名。初始關(guān)系表達(dá)式為：studentName(grade=2008cou

16、rseName=DB(Class Student) (Score Course)轉(zhuǎn)換后的關(guān)系代數(shù)表達(dá)式為：轉(zhuǎn)換后的關(guān)系代數(shù)表達(dá)式為： studentName(grade=2008(Class) Student) (Score courseName=DB(Course)3.2.2 代價(jià)估計(jì)一個(gè)運(yùn)算的代價(jià)依賴于它的輸入的大小和其他統(tǒng)計(jì)信息。因此，給定一棵查詢樹，要估計(jì)上一層某個(gè)運(yùn)算的代價(jià)，首先需要估計(jì)其下層運(yùn)算的中間結(jié)果集的大小。結(jié)果集大小的估計(jì)需要用到存儲(chǔ)在數(shù)據(jù)庫(kù)的數(shù)據(jù)字典中的有關(guān)統(tǒng)計(jì)信息，現(xiàn)實(shí)數(shù)據(jù)庫(kù)系統(tǒng)中需要維護(hù)更詳細(xì)的統(tǒng)計(jì)信息，以提高代價(jià)估計(jì)的精確度。大多數(shù)數(shù)據(jù)庫(kù)系統(tǒng)中將每個(gè)屬性的取值分布存

17、儲(chǔ)成一張直方圖。 選擇和連接運(yùn)算的估計(jì)選擇運(yùn)算結(jié)果大小的估計(jì)選擇運(yùn)算結(jié)果大小的估計(jì)依賴于選擇謂詞。等值謂詞選擇運(yùn)算A=a比較謂詞選擇運(yùn)算Av連接運(yùn)算結(jié)果大小的估計(jì)*553.2.3 物理優(yōu)化物理優(yōu)化就是要選擇高效合理的操作算法操作算法或存取路徑存取路徑，求得優(yōu)化的執(zhí)行計(jì)劃。主要方法：主要方法： 基于代價(jià)估算的優(yōu)化基于規(guī)則的啟發(fā)式優(yōu)化兩者結(jié)合的優(yōu)化方法例：*571）基于代價(jià)的優(yōu)化 基于代價(jià)的優(yōu)化器(cost-based optimizer，CBO)通過使用等價(jià)規(guī)劃從給定的查詢語(yǔ)句產(chǎn)生一系列查詢執(zhí)行計(jì)劃，并選擇代價(jià)最小的一個(gè)。對(duì)于一個(gè)復(fù)雜的查詢，等價(jià)于給定查詢的不同執(zhí)行計(jì)劃可能很多?；诖鷥r(jià)的優(yōu)化器

18、在實(shí)際應(yīng)用中，不可能也沒必要對(duì)所有可能的執(zhí)行計(jì)劃進(jìn)行窮舉搜索(這樣將會(huì)導(dǎo)致不可接受的優(yōu)化代價(jià)，即為了尋找最佳執(zhí)行計(jì)劃而花費(fèi)的代價(jià)過高)通常都是采用各種剪枝的技術(shù)進(jìn)行局部搜索，以尋找接近接近最優(yōu)最優(yōu)的執(zhí)行計(jì)劃。 *582）基于規(guī)則的啟發(fā)式優(yōu)化目標(biāo)：減少中間結(jié)果的大小減少不相關(guān)的數(shù)據(jù)運(yùn)算 減少掃描表的次數(shù)減少不相關(guān)元組的讀取 *59一般準(zhǔn)則選擇操作盡可能先做目的：大大減少中間結(jié)果的大小執(zhí)行連接前對(duì)關(guān)系適當(dāng)?shù)仡A(yù)處理兩種預(yù)處理方法：在連接屬性上建立索引和對(duì)關(guān)系排序目的：減少掃描表的次數(shù)減少不相關(guān)元組的讀取投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行目的：避免重復(fù)掃描表投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái)目的：避免重復(fù)掃描

19、表*60把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算目的：減少內(nèi)外存交換的信息量找出公共子表達(dá)式目的：減少計(jì)算量*61常用的關(guān)系代數(shù)表達(dá)式的啟發(fā)式方法常用的關(guān)系代數(shù)表達(dá)式的啟發(fā)式方法針對(duì)一棵語(yǔ)法樹，有下列常用的啟發(fā)式：選擇操作下移投影操作下移選擇和投影的串接合并*623.3 多連接查詢優(yōu)化*63查詢請(qǐng)求代價(jià)最小等價(jià)的JOIN樹集合等價(jià)的QEPR1R3查詢圖ABR2joinjoinR3R2R1join樹Sort-mergeNested-loopR3R2R1操作樹3.4 一個(gè)實(shí)例求選修了2號(hào)課程的學(xué)生姓名。用SQL表達(dá)： SELECT Student.Sname FROM Stud

20、ent，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2； 假定學(xué)生-課程數(shù)據(jù)庫(kù)中有n1000個(gè)學(xué)生記錄n10000個(gè)選課記錄n其中選修2號(hào)課程的選課記錄為50個(gè) 可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式1）Q1=sname(student.Sno=sc.Snosc.Cno=2 (studentsc)2）Q2=sname(sc.Cno=2 (student SC)3）Q3=sname(student sc.Cno=2(sc)1) 第一種情況第一種情況Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)1. 計(jì)算廣義笛卡爾積計(jì)算廣義

21、笛卡爾積 把Student和SC的每個(gè)元組連接起來(lái)的做法：在內(nèi)存中盡可能多地裝入某個(gè)表(如Student表)的若干塊，留出一塊存放另一個(gè)表(如SC表)的元組。把SC中的每個(gè)元組和Student中每個(gè)元組連接，連接后的元組裝滿一塊后就寫到中間文件上從SC中讀入一塊和內(nèi)存中的Student元組連接，直到SC表處理完。再讀入若干塊Student元組，讀入一塊SC元組重復(fù)上述處理過程，直到把Student表處理完設(shè)一個(gè)塊能裝10個(gè)Student元組或100個(gè)SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為 =100+20100=2100塊其中，讀Student表100塊。讀S

22、C表20遍，每遍100塊。若每秒讀寫20塊，則總計(jì)要花105s 連接后的元組數(shù)為103104=107。設(shè)每塊能裝10個(gè)元組，則寫出這些塊要用106/20=5104s 1010005101000100100002. 作選擇操作作選擇操作 依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄 假定內(nèi)存處理時(shí)間忽略。讀取中間文件花費(fèi)的時(shí)間(同寫中間文件一樣)需5104s 滿足條件的元組假設(shè)僅50個(gè)，均可放在內(nèi)存 3. 作投影操作作投影操作 把第2步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果 第一種情況下執(zhí)行查詢的總時(shí)間105+25104105s所有內(nèi)存處理時(shí)間均忽略不計(jì) 2) 第二種情況第二種情況 Q2=Sname(Sc.Cno=2 (Student SC)1. 計(jì)算自然連接 執(zhí)行自然連接，讀取Student和SC表的策略不變，總的讀取塊數(shù)仍為2100塊花費(fèi)105 s 自然連接的結(jié)果比第一種情況大大減少，為104個(gè) 寫出這些元組時(shí)間為104/10/20=50s，為第一種情況的千分之一 2. 讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時(shí)間也為50s。3. 把第2步結(jié)果投影輸出。 第二種情況總的執(zhí)行時(shí)間105+50+50205s 3) 第三種情況第三種情況Q3=Sname(Student Sc.Cno=2(SC)1. 先對(duì)SC表作選