1、1數據庫系統設計與原理第部分DBMS的內核(第章第11章)2第9章查詢處理講課內容：查詢處理是指從數據庫中提取數據的一系列活動。這一系列活動包括：將用高層數據庫語言表示的查詢語句，如SQL，翻譯成能在文件系統這一物理層上實現的表達式，如關系代數；為優化查詢進行的各種轉換；以及查詢的實際執行。查詢處理的過程表達式的求值方法關系代數表達式的轉換查詢優化的方法查詢代價的度量查詢優化器的構造實現關系運算的算法代價本章總結3DBMS總體結構回顧：查詢處理器用戶應用界面索引統計數據數據文件數據字典應用程序交互查詢數據庫模式應用程序目標碼嵌入式DML預編譯器DML編譯器DDL解釋器查詢計算引擎事務管理器緩沖

2、區管理器文件管理器查詢處理器存儲管理器數據庫管理系統磁盤存儲器權限及完整性管理器日志4查詢處理的過程查詢處理是指對最終用戶提交的查詢進行：解析優化執行 并最終給出查詢結果的處理過程。5查詢處理的過程查詢優化器問題的提出：一個查詢用SQL語言可以有多種表達方式；而每個SQL語句又可以翻譯成多個等價的關系代數表達式。例如：select student_number from student where student_number “s000003” 可以翻譯成下面兩個關系代數表達式：student_number”s000003”(student_number(student)student_nu

3、mber(student_number”s000003”(student)表達式中的關系運算又可以用不同的算法和索引去實現。因此，查詢優化器的任務就是要找出代價最小的計算給定查詢的處理過程。6查詢處理的過程查詢優化器輸入？輸出？查詢執行計劃？帶注釋！注釋用于說明：如何具體實施每個關系操作。例如：關系運算所采用的算法將要使用的索引執行原語：加上了有關“如何執行”的注釋的關系代數運算查詢執行(計算)計劃：用于計算一個查詢的原語序列。7查詢優化器查詢優化為給定查詢選擇最有效的查詢執行計劃的過程：在關系代數級進行優化，力圖找出與給定表達式等價、但執行效率更高(?)的一個表達式；查詢語句處理的詳細策略的

4、選擇。例如，確定算法與索引等。本章的主要內容什么是查詢執行計劃的代價？如何估計查詢執行計劃的代價？如何進行有效的查詢優化？查詢處理的過程8查詢處理的過程執行引擎輸入是查詢執行計劃輸出則是具體的查詢結果還需要將實現關系運算的算法與底層的文件操作指令結合起來！9關系代數表達式的轉換等價的關系代數表達式它們的執行結果相同，但代價不同。例如：“請給出計算機系的教師所講課程的課程名稱和教師姓名”，就可以用如下兩個等價的關系代數表達式來求值：course_name, teacher_name(department_name = “計算機系”(teacherteaching)course_name, tea

5、cher_name(department_name = “計算機系”(teacher)teaching)從感覺上講，哪個關系代數表達式的計算效率更高一些？為什么？10關系代數表達式的轉換關系代數表達式樹為了更明顯地看出上述兩個表達式的差別，還可以用關系代數表達式樹來描述它們：11關系代數表達式的轉換表達式的轉換與等價通過等價規則進行關系代數表達式的轉換；等價規則顧名思義就是指兩種不同形式的表達式可以相互轉換，而又保持等價；所謂保持等價是指兩個表達式產生的結果關系具有相同的屬性集和相同的元組集，但屬性出現的次序可以不同。等價規則在下面的等價規則中，用、1、2等表示謂詞；用L、L1、L2等表示屬性

6、列表；用E、E1、E2等表示關系代數表達式。12關系代數表達式的轉換等價規則合取選擇運算可分解為單個選擇運算的序列，該變換稱為的級聯：12(E) = 1(2(E)選擇運算滿足交換律：1(2(E) = 2(1(E)投影運算序列中只有最后一個運算是需要的，其余可省略。該轉換稱為的級聯：L1(L2(Ln(E) = L1(E)13關系代數表達式的轉換等價規則選擇可與笛卡兒積以及theta連接相結合：(E1E2) = E1E21(E12E2) = E112E2 theta連接(包括自然連接)運算滿足交換律：E1E2 = E2E1 自然連接運算滿足結合律：(E1E2)E3 = E1(E2E3)theta連

7、接具有以下方式的結合律：(E11E2)23E3 = E113(E22E3)2只涉及E2與E3的屬性；由于任意一個條件都可為空，因此笛卡兒積運算也滿足結合率！14關系代數表達式的轉換等價規則選擇運算在下面兩個條件下對theta連接運算具有分配律：當選擇條件0的所有屬性只涉及E1時：0(E1E2) = (0(E1)E2當選擇條件1只涉及E1的屬性，2只涉及E2時：12(E1E2) = (1(E1)(2(E2)投影運算對theta連接運算具有分配律：令L1、L2分別是E1、E2的屬性，而連接條件只涉及L1L2中的屬性，則：L1L2(E1E2) = (L1(E1)(L2(E2)15關系代數表達式的轉換

8、等價規則投影運算對theta連接運算具有分配律：令L1、L2分別是E1、E2的屬性，L3是E1里出現 在連接條件中但不在L1L2中的屬性，而L4 是E2里出現在連接條件中但不在L1L2中的 屬性，那么：L1L2(E1E2) = L1L2(L1L3(E1)(L2L4(E2)集合運算并與交滿足交換律：E1E2 = E2E1；E1E2 = E2E1 但是集合差運算不滿足交換律！16關系代數表達式的轉換等價規則集合運算并與交滿足結合律：(E1E2)E3 = E1(E2E3)(E1E2)E3 = E1(E2E3)選擇運算對并、交、差運算具有分配律：(E1E2) = (E1)(E2)(E1E2) = (E

9、1)(E2)(E1-E2) = (E1)-(E2)投影運算對并運算具有分配率：L(E1E2) = (L(E1)(L(E2)17關系代數表達式的轉換表達式轉換舉例假設student和selecting是以下關系模式上的關系：Student_schema = (student_number,student_name, department_name)Selecting_schema = (student_number,course_name)對于關系代數表達式：student_name(department_name = “計算機系”(studentselecting) )18關系代數表達式的轉換

10、表達式轉換舉例利用前面介紹的規則，可以得到如下的等價表達式：student_name(department_name=“計算機系”(student)selecting)如果將上述查詢修改為：student_name(department_name=“計算機系”course_name like ”數據庫%”(studentselecting) )那么，如何對上述表達式進行等價變換呢？19關系代數表達式的轉換表達式轉換舉例由于選擇條件中屬性department_name只涉及到關系student，而屬性course_name只涉及到關系selecting，因此利用規則將表達式變換為：student

11、_name(department_name=“計算機系”(student)(course_name like ”數據庫%”(selecting) )20表達式轉換舉例用關系代數表達式樹可以更明顯地看出上述兩個表達式的差別：關系代數表達式的轉換21查詢代價的度量查詢處理的代價查詢處理的代價可以通過該查詢對各種資源的使用情況進行衡量。資源包括：磁盤存取(磁盤I/O)執行查詢所用的CPU時間并行/分布式數據庫系統中的通信開銷磁盤訪問通常是最主要的代價，這是因為：磁盤存取比內存操作(CPU)要慢得多；CPU速度的提升要比磁盤速度的提升快的多。結論：磁盤存取代價是查詢執行計劃代價的合理度量。22查詢代價

12、的度量代價模型為了簡化磁盤存取代價的計算，需要構造一個簡單的代價模型：存取代價用從磁盤向主存傳送的物理塊數來度量假定所有塊傳送的代價相同。該假定忽略了：尋道時間(搜索時間)：將磁頭移動到所期望的磁道或柱面的時間；旋轉等待時間：等待所需要的數據(扇區)旋轉到讀寫頭下的時間延遲。忽略了將查詢的最終結果寫回磁盤的代價；實現關系運算的算法代價是最壞情形下的代價：即主存中緩沖區只能容納數目不多的數據塊，需要不斷地訪問外存。23查詢代價的度量用于估計代價的統計信息查詢優化器利用存儲在DBMS的系統目錄中的統計信息來估計查詢執行計劃的代價，相關的統計信息包括：nr：關系r中元組的數目；br：關系r的元組所占

13、用的塊數目；sr：關系r中一個元組的大??；fr：關系r的塊因子，即一個物理塊中能存放的關系r的元組數目；V(A,r)：關系r中屬性A所具有的不同值的數目：該數目與A(r)的大小相同。若A為關系r的碼，則V(A,r)=nr。24查詢代價的度量用于估計代價的統計信息查詢優化器利用存儲在DBMS的系統目錄中的統計信息來估計查詢執行計劃的代價，相關的統計信息包括：SC(A,r)：關系r的屬性A的選擇基數。給定關系r及其屬性A，假定至少有一條記錄滿足等值條件，那么SC(A,r)表示在屬性A上滿足某個等值條件的平均記錄數：若A為r的碼，則SC(A,r)=1；若A為非碼屬性，并假定V(A,r)個不同的值在多

14、個元組中平均分配，則SC(A,r)=(nr/V(A,r)。HTi：索引i的層數，即索引i的高度；對于散列索引，HTi=1。25查詢代價的度量統計信息的維護與使用這里提到的統計信息是經過簡化的，實際系統的查詢優化器通常包含更多的統計信息。這些統計信息：在適當的時候，比如系統負載比較輕的時候，進行更新，而不是實時更新。利用這些統計信息來估計實現各種關系代數運算的算法代價，并把算法A的代價估計記為EA。26實現關系運算的算法代價概述在關系代數中，不同的關系運算有：、和運算等等；這些運算的實現都離不開對文件的掃描！實現這些運算的不同算法是數據結構這門課要講的內容，包括算法的時間復雜性和空間復雜性分析；

15、本節的主要內容是以前面介紹的代價模型為基礎，根據系統目錄中的統計信息來分析實現關系運算的具體算法的磁盤存取代價，即在磁盤和主存儲器之間傳送的數據塊數！27實現關系運算的算法代價選擇運算在查詢處理中，實現選擇運算的算法通常是文件掃描。文件掃描是用于定位、檢索滿足選擇條件的記錄的搜索算法：不用索引的搜索算法：文件掃描線性搜索算法A1二分法搜索算法A2使用索引的搜索算法：索引文件掃描有主索引的碼屬性上的等值比較算法A3有主索引的非碼屬性上的等值比較算法A4其他搜索算法28實現關系運算的算法代價文件掃描線性搜索算法A1：每個數據塊均被掃描算法代價：EA1=br效率低但可用于任何文件，且不管是否有索引。

16、二分法搜索算法A2：文件按照某一屬性A排序選擇條件是屬性A上的等值比較二分法搜索針對文件的數據塊進行EA2=log2(br) + SC(A,r)/fr - 1找到符合條件的第一個數據塊的代價滿足選擇條件的記錄數因為有一塊已被檢索到29實現關系運算的算法代價索引文件掃描有主索引的碼屬性上的等值比較算法A3：選擇條件是碼屬性上的等值比較利用在碼屬性上建立的主索引找到一條記錄算法代價為：EA3 = HTi + 1有主索引的非碼屬性上的等值比較算法A4：選擇條件是非碼屬性A上的等值比較利用在非碼屬性A上建立的主索引找到多條記錄算法代價為：EA4 = HTi + SC(A,r)/fr索引文件掃描算法增加

17、了訪問索引的代價。30實現關系運算的算法代價連接運算連接運算是RDBMS要著重解決的關系代數運算之一；數據庫的很多查詢都涉及到連接運算，因此連接運算的效率就成為衡量DBMS性能的一個主要指標。實現連接運算的各種算法有：嵌套循環連接算法索引嵌套循環連接算法歸并連接算法散列連接算法其他連接算法31實現關系運算的算法代價嵌套循環連接以theta連接rs為例：32實現關系運算的算法代價嵌套循環連接算法分析：與文件的線性掃描算法類似，關系文件的每個數據塊都必須被訪問；不要求有任何索引，任何連接條件都能適應；對關系r的每一條記錄都必須對關系s做一次完整的掃描，因此算法代價為：最壞情況下：緩沖區只能容納每個

18、關系的一個數據塊，因而EJ=nr*bs+br 最好情況下：兩個關系都能放到內存里，因而算法代價為EJ=bs+br第一節課的問題：誰將作為連接的內關系？33實現關系運算的算法代價索引嵌套循環連接將嵌套循環連接算法中的文件掃描用索引掃描來代替：算法分析：在給定元組tr的情況下，在關系s中查找滿足連接條件的元組本質上是在s上做選擇運算。因此該算法的代價為：EJ = br + nr * c其中c是使用連接條件并利用索引對關系s進行單個選擇運算的代價。索引該建在什么地方？34表達式的求值方法概述：關系代數表達式的代價估計前面討論的都是實現單個關系運算的算法與算法分析；實際上在一個關系代數表達式里常常含有

19、多個不同或相同的關系運算，那么如何估計整個表達式的計算代價呢？這主要與整個表達式的計算方法有關：實體化計算方法流水線計算方法上述兩種方法的相互結合(參見9.6)35表達式的求值方法實體化計算方法以適當的順序每次執行表達式里的一個關系運算，每次計算的結果都被保存(實體化)到一個臨時關系中以備后面的運算使用。如：course_name(student_number”s000003”(student)selecting)36表達式的求值方法實體化計算方法實體化計算方法的缺點是需要構造臨時關系，這些臨時關系除非很小(可以放在內存里)，否則就必須寫到磁盤上(tempdb)；實體化計算方法的代價不僅僅是表

20、達式中所涉及的關系運算的代價總和，還應該加上把中間結果寫回磁盤的代價；在估計單個關系運算的代價時，忽略了將運算結果回寫到磁盤的代價。但對由多個關系運算構成的表達式，就不能簡單地忽略掉回寫磁盤的代價！37表達式的求值方法流水線計算方法將表達式中的多個關系運算組合成一個操作流水線來實現，即將一個運算的結果作為輸入直接傳送到下一個運算。例如：course_name(student_number”s000003”(student)selecting)38表達式的求值方法兩種計算方法的比較實體化計算方法需要產生臨時關系、回寫中間結果，這可能會影響查詢的執行效率。但該方法可以直接利用各個關系運算的算法實現

21、(即操作代碼)；而流水線計算方法雖然具有減少產生臨時關系、提高查詢執行效率的優點，但它需要對流水線中的每一關系運算建模，以便能夠重用各個關系運算的操作代碼。39表達式的求值方法流水線計算方法模型最簡單的模型就是：每一關系運算都作為系統內獨立的進程或線程；獨立的線程從流水化的輸入中接受元組流，并產生一個元組流作為其輸出；對于流水線中的每對相鄰運算，都創建一個緩沖區來保存從一個運算傳送到另一個運算的元組。40表達式的求值方法流水線計算方法的執行需求者驅動：“拉”的過程系統不停地向位于流水線頂端的操作發出需要元組的請求；每當一個運算收到需要元組的請求時，它就計算下一個或多個元組并返回它們。生產者驅動

22、：“推”的過程流水線上的各個關系運算并不等待元組請求，而是不停地產生元組；流水線底端的每個操作不斷地產生元組并將它們放在輸出緩沖區中，直到緩沖區滿為止。41查詢優化的方法為什么查詢優化器是必須的？查詢優化器可以從數據字典中獲取許多統計信息，根據這些信息選擇有效的執行計劃，而用戶和應用程序則難以獲得這些信息；如果數據庫的統計信息改變了，系統可以自動地對查詢重新進行優化以選擇相適應的執行計劃。如果讓用戶或應用程序去跟蹤數據庫統計信息的變化往往是不太可能的；查詢優化器可以同時考慮數百種不同的查詢執行計劃，而數據庫程序員一般只能考慮有限的幾種可能性。42查詢優化的方法查詢優化的步驟與方式查詢優化器的任

23、務就是要產生一個代價最小的查詢執行計劃。這要分兩步走：產生邏輯上與給定表達式等價的表達式；對表達式做不同方式的注釋，產生后選計劃：實現算法的選擇索引的選擇執行方法的選擇在查詢優化器中，這兩步是交叉進行的，產生一部分表達式并注釋，然后又產生一部分表達式并注釋43查詢優化的方法查詢執行計劃舉例44查詢優化的方法由于產生了很多后選的查詢執行計劃，并且這些計劃是表達式與注釋交叉產生的，因此如何對整個表達式進行優化，產生代價最小的執行計劃是一個問題；一般來說，簡單地為每個關系運算選擇一個代價最小的算法，整個表達式的代價可能最小。但這樣做往往是事與愿違！因此，必須采用一定的查詢優化策略才能滿足需要：基于代價的優化啟發式優化查詢優化的方法45查詢優化的方法基于代價的優化方法將各種可能的查詢執行計劃全部產生出來，然后從中估