1、機械自動化學院機械自動化學院20152015主講：主講： 顧顧 曦曦 電話：電話：1569718107915697181079EmailEmail：主要內容*2查詢處理查詢處理查詢優化查詢優化*3Profile簡介Profile 是在Mysql5.1以后版本引入，來源于開源社區Jeremy Cole的貢獻。當一條查詢提交給服務器時，此工具會記錄剖析信息到一張臨時表，并且給查詢賦予一個整數標識符。剖析信息包含數據庫對某個查詢的詳細執行情況，對于分析和優化查詢，提高數據庫的性能很有幫助。Profile工具的使用啟動數據庫，登錄客戶端；使用數據庫scoreDBmysql use scoredb；啟動

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

3、達式。為優化查詢而進行的各種轉換以及查詢的實際執行 。查詢處理的主要過程包括： 語法分析與翻譯語法分析與翻譯 查詢優化查詢優化 查詢執行查詢執行1） 語法分析與翻譯器查詢處理開始之前，系統將查詢語句查詢語句翻譯成可使用的形式。 語法分析與翻譯階段的主要工作有：檢查用戶查詢的語法，利用數據字典驗證查詢中出現的關系名、屬性名等是否正確；構造該查詢語句的語法分析樹表示，并將其翻譯成關系代數表達式關系代數表達式。 2） 查詢執行計劃與查詢優化器一個給定的查詢任務，一般都會有多種計算結果的方法 例如，考慮如下查詢 select studentName from Student where classNo

4、=CS0701 and sex=女 該查詢語句可翻譯成如下關系表達式中的任意一個classNo=CS0701(sex=女(studentName(Student)sex=女(classNo=CS0701(studentName(Student)classNo=CS0701(studentName(sex=女(Student)studentName(sex=女(classNo=CS0701(Student)執行一個查詢，不僅需要提供關系代數表達式，還要對該表達式加上注釋來說明如何執行每個操作。加了“如何執行”注釋的關系代數運算稱為執行原語。用于執行一個查詢的原語操作序列操作序列稱為查詢執行計劃。

5、不同的查詢執行計劃會有不同的代價。DBMS通過查詢優化器構造具有最小查詢執行代價的查詢執行計劃，稱為查詢優化查詢優化。 查詢優化是影響RDBMS性能的關鍵因素。關系數據庫系統和非過程化的SQL語言能夠取得巨大成功關鍵是得益于查詢優化技術的發展。3） 查詢執行引擎查詢執行引擎查詢執行引擎根據輸入的查詢執行計劃，調用相關算法實現查詢計算，并將計算結果返回給用戶。 有效地對內存緩沖區內存緩沖區進行管理是影響查詢執行性能的非常重要的方面。 *142.1 概述查詢處理的代價可以通過該查詢對各種資源的使用情況進行度量。主要包括磁盤存取時間磁盤存取時間執行一個查詢所用的執行一個查詢所用的CPU時間、時間、在

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

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

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

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

10、 A3 具有主索引的碼屬性上的等值比較算法，可以通過主索引檢索到指向滿足相應等值條件的唯一唯一記錄的指針，再根據該指針到數據文件中訪問磁盤塊。若使用B+樹索引，則訪問索引塊的數量等于樹高度HTi，訪問文件塊的數量為1；而且每一次I/O操作都需要一次磁盤搜索定位和一次磁盤塊傳輸。因此，算法A3的時間代價為： EA3= HTi+1 *(tT+tS)*22主索引非碼屬性上的等值比較算法 A4 通過主索引檢索到指向滿足相應等值條件的第一條記錄（可能有多條記錄，但它們在物理上順序存放）的指針，再根據該指針到數據文件中訪問磁盤塊。 需要訪問的文件塊的數目可估計為： b= SC(A, r)/fr 算法A4的

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

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

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

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

15、分布、B+樹索引的深度等，對一個執行計劃的代價進行事先估計。物理優化物理優化：對所產生的表達式以不同方式作注釋注釋，產生不同的查詢執行計劃。 在查詢優化器中第1步和第3步是交叉進行的*513.2.1 代數優化定義：基于關系代數等價變換規則的優化方法。方法：關系表達式轉換(參看課本本章和關系代數一章)查詢樹的啟發式優化 優化重點：連接運算的次序 一個好的連接運算次序對于減少中間結果的大小非常重要，也會影響到連接算法的選擇。大部分查詢優化器在連接運算的次序上花了很多功夫。*52例找出2008級修讀“數據庫系統概論”課程的學生姓名。初始關系表達式為：studentName(grade=2008cou

16、rseName=DB(Class Student) (Score Course)轉換后的關系代數表達式為：轉換后的關系代數表達式為： studentName(grade=2008(Class) Student) (Score courseName=DB(Course)3.2.2 代價估計一個運算的代價依賴于它的輸入的大小和其他統計信息。因此，給定一棵查詢樹，要估計上一層某個運算的代價，首先需要估計其下層運算的中間結果集的大小。結果集大小的估計需要用到存儲在數據庫的數據字典中的有關統計信息，現實數據庫系統中需要維護更詳細的統計信息，以提高代價估計的精確度。大多數數據庫系統中將每個屬性的取值分布存

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

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

19、表*60把某些選擇同在它前面要執行的笛卡爾積結合起來成為一個連接運算目的：減少內外存交換的信息量找出公共子表達式目的：減少計算量*61常用的關系代數表達式的啟發式方法常用的關系代數表達式的啟發式方法針對一棵語法樹，有下列常用的啟發式：選擇操作下移投影操作下移選擇和投影的串接合并*623.3 多連接查詢優化*63查詢請求代價最小等價的JOIN樹集合等價的QEPR1R3查詢圖ABR2joinjoinR3R2R1join樹Sort-mergeNested-loopR3R2R1操作樹3.4 一個實例求選修了2號課程的學生姓名。用SQL表達： SELECT Student.Sname FROM Stud

20、ent，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2； 假定學生-課程數據庫中有n1000個學生記錄n10000個選課記錄n其中選修2號課程的選課記錄為50個 可以用多種等價的關系代數表達式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. 計算廣義笛卡爾積計算廣義

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

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