1、第5章 查詢處理和查詢優化第5章 關系查詢處理和查詢優化查詢是數據庫管理系統中使用最頻繁、最基本的操作，對系統性能有很大影響。查詢優化技術是關系數據庫的關鍵技術。對于同一個SQL查詢，通常可以有多個等價的關系代數表達式，由于存取路徑的不同，每個關系代數表達式的查詢代價和效率也是不同的。 本章目的： RDBMS的查詢處理步驟 查詢優化的概念 基本方法和技術 2022/7/182第5章 關系查詢處理和查詢優化5.1關系數據庫系統的查詢處理5.2關系數據庫系統的查詢優化5.3代數優化5.4基于存取路徑的優化5.5基于代價估算的優化5.6小結2022/7/1835.1.1查詢處理過程對查詢語句進行掃描

2、、詞法分析和語法分析 1根據數據字典中的用戶權限和完整性約束定義對用戶的存取權限進行檢查2把SQL查詢語句轉換成等價的關系代數表達式一般都用查詢樹(語法分析樹)來表示擴展的關系代數表達式3選擇一個高效執行的查詢處理策略 用關系代數優化法，利用一些等價變換規則進行代數優化。結合索引、數據值的分布等數據存儲特征，進一步改善查詢效率。在若干查詢計劃中選擇代價最低的4生成查詢計劃，其中包括如何訪問數據庫文件和如何存儲中間結果等52022/7/1845.1.1查詢處理過程數據庫查詢語的具體處理過程可以分為：解釋方式DBMS不保留可執行代碼，每一次都重新解釋執行查詢語句，事務完成后返回查詢結果。這種方法具

3、有靈活、應變性強的特點，但是開銷比較大、效率比較低，主要適用于不重復使用的偶然查詢。編譯方式先進行編譯處理，生成可執行代碼。運行時，直接執行可執行代碼。當數據庫中某些數據發生改變，再重新編譯。編譯的方法主要優點是執行效率高、系統開銷小2022/7/1855.1.2執行查詢操作的基本算法1.選擇操作的實現2.連接操作的實現3.投影操作的實現4.集合運算的實現2022/7/1861.選擇操作的實現【例 51】Select * from student where ，其中條件表達式可以有以下幾種情況：C1：無條件C2：Sno = 200636C3：Sage 18C4：Sdept = 計算機 and

4、Sno = 200636C5：Sdept = 計算機 and Sage 18C6：Sage 18 or Sdept = 計算機 2022/7/1871.選擇操作的實現（1）順序掃描方法實現選擇操作最簡單的一種方法。該方法按照關系中元組的物理順序掃描每個元組，檢查該元組是否滿足選擇條件，如果滿足則輸出這種方法不需要特殊的存取路徑，簡單、有效，適用于任何關系，尤其適用于被選中的元組數占有較大比例或元組數較少的關系 代價估算如下：如果關系R的元組占用的塊數為BR（塊是數據在磁盤和內存之間傳遞的單位 ），順序掃描方法的代價cost=BR。如果選擇條件是主鍵上的相等比較操作，那么平均搜索一半的文件塊才能

5、找到滿足條件的元組，因此平均搜索代價cost=BR/2。2022/7/1881.選擇操作的實現（2）二分查找法如果選擇條件涉及相等比較，并且物理文件是按照選擇字段有序組織的，可以使用二分查找來定位二分查找法比順序掃描方法有效。例如，字段Sno是排序屬性，可以用二分查找法實現C2中的選擇條件如果選擇是作用在非排序屬性上,代價也會相應增加代價估算如下：二分查找法是針對文件的物理塊進行的，平均搜索代價為 。如果選擇是作用在非排序屬性上，那么將會有多個塊包含所需的元組，代價也會相應增加。查詢條件 C2：Sno = 2006362022/7/1891.選擇操作的實現（3）使用索引（或散列）的掃描方法適合

6、選擇條件中的屬性上有索引(例如B+樹索引或Hash索引) 通過索引先找到滿足條件的元組指針，然后通過該指針繼續檢索滿足查詢條件的元組。 2022/7/1810檢索Sno=60的元組使用索引(或散列)得到Sno為60 元組的指針通過元組指針檢索符合查詢條件的元組1檢索Sno78的元組找到78的索引項，以此為入口點在B+樹的順序集上得到18的所有元組指針，通過這些元組指針檢索18的所有元組22022/7/1811（3）使用索引（或散列）的掃描方法索引掃描算法的代價估算公式：如果選擇條件是相等比較操作，需要存取索引樹中從根結點到葉結點L塊，再加上基本表中該元組所在的那一塊，所以cost=L+1 如果

7、選擇條件涉及非主鍵屬性的相等比較，若為B+樹索引，如果有S個元組滿足條件，若每個滿足條件的元組可能會保存在不同塊上，最壞情況下cost=L+S。如果比較條件是，操作，而且假設有一半的元組滿足條件就要存取一半的葉結點，則代價估計cost=L+索引的葉結點數/2+元組占用的塊數 /2 2022/7/1812（4）復合選擇邏輯合取AND邏輯合取（AND）使用組合索引如果合取條件中的相等條件包含兩個或兩個以上的屬性，且在組合字段上存在組合索引(或散列),可以直接使用這個組合索引以C4：Sdept = 計算機 and Sno = 200636為例,如果在（Sdept，Sno）上建立了組合索引，通過這個組

8、合索引可以直接找到滿足條件的元組 使用單獨索引使用多個索引2022/7/1813（4）復合選擇邏輯合取AND邏輯合取（AND）（續）使用單獨索引 通過索引找到符合與該屬性有關的查詢條件的元組 檢查其余的查詢條件是否滿足以C5：Sdept = 計算機 and Sage 18為例，如果Sdept上有索引，先找到Sdept=計算機的一組元組指針，通過這些元組指針到student表中檢索，對得到的元組檢查另一些選擇條件（如Sage18）是否滿足，最后把滿足條件的元組作為結果輸出 2022/7/1814（4）復合選擇邏輯合取AND邏輯合?。ˋND）（續）使用多個索引分別檢索滿足單個條件的元組指針集，這些

9、元組指針集的交集就提供了滿足合取條件的指針。以C5 :Sdept = 計算機 and Sage 18為例，假設Sdept和Sage上都有索引。分別使用索引（或散列）的掃描方法找到Sdept=計算機的一組元組指針和Sage18的另一組元組指針然后求這兩組指針的交集，再到student表中檢索2022/7/1815（4）復合選擇邏輯合取AND在合取選擇條件的多個簡單條件中進行選擇時，通常要考慮每個條件的選擇率或選擇性（selectivity）。所謂選擇率，就是滿足條件的元組（記錄）數占關系中元組（記錄）總數的比例 一般地，如果選擇條件的選擇率為s，滿足該條件的元組數則可以估計為（s元組數）。所估計

10、的值越小，就越有必要首先使用這個條件來檢索元組 2022/7/1816（4）復合選擇邏輯析取OR析取條件就是用邏輯連接符OR連接的查詢條件，處理和優化的難度就大得多。以C6為例，Sage 18 or Sdept = 計算機，如果Sdept上有索引，而Sage上沒有索引，基本上無法進行優化。只要任意一個條件沒有索引，就只能使用順序掃描方法。對于條件中涉及的屬性都具有索引時，才能通過優化檢索滿足條件的元組，然后再通過合并操作消除重復元組 2022/7/18172.連接操作的實現連接操作是查詢處理中最耗時的操作之一，操作本身開銷大，并且可能產生很大的中間結果。（1）嵌套循環法（2）索引嵌套循環法（3

11、）排序合并法（4）散列連接（Hash Join）法2022/7/1818（1）嵌套循環法嵌套循環法是最簡單、最直接的連接算法，與選擇操作中的順序掃描法類似，不需要特別的存取路徑 ABCa1b1c1a1b2c2a2b2c1ABCa1b1c1a1b1c1a1b1c1a1b2c2a1b2c2a1b2c2a2b2c1a2b2c1a2b2c1ABCa1b2c2a1b3c2a2b2c1RSR S ABCa1b2c2a1b3c2a2b2c1a1b2c2a1b3c2a2b2c1a1b2c2a1b3c2a2b2c1 選擇哪一個關系用于外循環、哪一個關系用于內循環會給連接的性能帶來比較大的差異 一般使用較少塊的文

12、件作為外循環文件連接代價較小。 嵌套循環法適用于任何條件的連接 2022/7/1819（2）索引嵌套循環法在嵌套循環法中，如果兩個連接屬性中的一個屬性上存在索引（或散列），可以使用索引掃描代替順序掃描。例如，在關系S中的屬性B上存在索引，則對于R中的每個元組，可以通過S的索引查找滿足tBsA的所有元組，而不必掃描S中的所有元組，以減少掃描時間。2022/7/1820ABCa1b15a1b26a2b38a2b412BEb13b27b310b32b52AR.BCS.BEa1b15b13a1b26b27a2b38b310a2b38b32 等值連接 R S R.B=S.B 在一般情況下，索引嵌套循環法

13、和嵌套循環法相比，查詢的代價可以降低很多。 2022/7/1821（3）排序合并法適合連接的諸表已經排好序的情況 排序合并法的步驟：如果連接的表沒有排好序，先對Student表和SC表按連接屬性Sno排序 取Student表中第一個Sno，依次掃描SC表中具有相同Sno的元組 200215121200215122200215123200215124.200215121 1 92200215121 2 85200215121 3 88200215122 2 90200215122 3 80當掃描到Sno不相同的第一個SC元組時，返回Student表掃描它的下一個元組，再掃描SC表中具有相同Sno

14、的元組，把它們連接起來 重復上述步驟直到Student 表掃描完 Student表和SC表都只要掃描一遍 如果兩個表原來無序，執行時間要加上對兩個表的排序時間 對于兩個大表，先排序后使用排序合并法執行連接，總的時間一般仍會大大減少 2022/7/1822（4）散列連接（Hash Join）法把連接屬性作為hash碼，用同一個hash函數把R和S中的元組散列到同一個hash文件中劃分階段(partitioning phase)：對包含較少元組的表(比如R)進行一遍處理把它的元組按hash函數分散到hash表的桶中散列連接法原理：如果屬性值相等，散列值必然相等；而散列值相等，屬性值未必相等。 20

15、22/7/1823（4）散列連接（Hash Join）法試探階段(probing phase)：也稱為連接階段(join phase) 對另一個表(S)進行一遍處理把S的元組散列到適當的hash桶中把元組與桶中所有來自R并與之相匹配的元組連接起來 散列連接法前提：假設兩個表中較小的表在第一階段后可以完全放入內存的hash桶中 以上的算法思想可以推廣到更加一般的多個表的連接算法上2022/7/18243.投影操作的實現投影操作選取關系的某些列，從垂直的方向減小關系的大小。 如果投影屬性列包括了關系R的主鍵，那么操作可以直接執行，操作的結果將與R中的元組個數相同 否則，需要消除重復元組 通常的做法

16、是先對操作結果進行排序， 去掉多余的副本 用散列法來消除重復元組，即把投影結果中的每條元組散列到相應的桶中然后檢查是否與該桶中已存在的元組重復，如果該元組是重復的，則不把這個元組插入桶中,否則把該元組插入桶中 2022/7/18254.集合運算的實現傳統的集合運算是二元的，包括并、差、交、笛卡爾積四種運算。 并、差、交運算實現的常用方法類似排序合并法 ，首先對參加運算的兩個關系分別按照主鍵屬性排序，排序后只需同時對兩個關系執行一次掃描就可以生成計算結果 笛卡爾積的實現通常使用嵌套循環法，由于笛卡爾積的操作結果中包含了R和S中每個元組的組合，其結果集會比參與運算的關系大得多,操作代價非常高 20

17、22/7/1826第5章 關系查詢處理和查詢優化5.1關系數據庫系統的查詢處理5.2關系數據庫系統的查詢優化5.3代數優化5.4基于存取路徑的優化5.5基于代價估算的優化5.6小結2022/7/18275.2 關系數據庫系統的查詢優化查詢優化的必要性查詢優化極大地影響RDBMS的性能。查詢優化的可能性關系數據語言的級別很高，使DBMS可以從關系表達式中分析查詢語義。 關系系統的查詢優化的優點用戶不必考慮如何最好地表達查詢系統可以比用戶程序的“優化”做的更好2022/7/18285.2 關系數據庫系統的查詢優化由DBMS進行查詢優化的好處(1) 優化器可以從數據字典中獲取許多統計信息，而用戶程序

18、則難以獲得這些信息 (2)如果數據庫的物理統計信息改變了，系統可以自動對查詢重新優化以選擇相適應的執行計劃。 在非關系系統中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。(3)優化器可以考慮數百種不同的執行計劃，而程序員一般只能考慮有限的幾種可能性。(4)優化器中包括了很多復雜的優化技術2022/7/18295.2.1查詢優化技術查詢優化的總目標：選擇有效策略，求得給定關系表達式的值，使查詢代價最小(實際上是較小) （1）代數優化是關系代數表達式的優化按照一定的規則，改變代數表達式中操作的次序和組合，使查詢執行更高效。只改變查詢語句中操作的次序和組合，不涉及底層的存取路徑 2022/7

19、/18305.2.1查詢優化技術（2）基于存取路徑的優化合理選擇各種操作的存取路徑以獲得優化效果，需要考慮數據的物理組織和訪問路徑，以及底層操作算法的選擇，涉及數據文件的組織方法、數據值的分布情況等，也稱為物理優化 （3）基于代價估算的優化對于多個可選的查詢策略, 通過估算執行策略的代價, 從中選擇代價最小的作為執行策略在實際的關系數據庫中，查詢優化的具體實現不完全相同，但往往都綜合運用了這些優化技術，以獲得較好的查詢優化效果2022/7/18315.2.2查詢優化實例【例 52】查詢選修“DataBase”課程的學生成績。用SQL表達如下SELECT SC.Grade FROM Course

20、，SC WHERE Course.Cno=SC.Cno and Course.Cname=DataBase;等價關系代數表達式2022/7/18325.2.2查詢優化實例CourseSC首先在內存中盡可能多地裝入Course表，留出一塊存放SC的元組然后，把SC中的每個元組和Course中的每個元組連接, 完成之后，繼續讀入下一塊SC的元組，同樣和內存中Course的每個元組連接，依此類推，直到SC表的元組全部處理完畢。接下來，再把Course表中沒有裝入的元組盡可能多地裝入內存，同樣逐塊裝入SC表的元組去作元組的連接，直到Course表的所有元組全部進行完連接。 2022/7/18335.2

21、.2查詢優化實例 SC:10000條，Course:100條,滿足條件的元組為100個 假設內存被劃分為6塊，每塊能裝10個Course元組或100個SC元組。每次在內存中放5塊Course元組和1塊SC元組 CourseSC 讀取總塊數=讀Course表的塊數讀SC表的塊數組成讀Course表的塊數+ 讀SC表遍數*每遍塊數 102100 210塊 讀數據時間=210/20=10.5秒 讀寫速度：20塊/秒中間結果大小 = 10000*100 = 106 (條元組)寫中間結果時間= 106 /10/20=5000秒每塊裝10個元組2022/7/18345.2.2查詢優化實例CourseSC

22、讀數據時間=10.5秒 讀寫速度：20塊/秒寫中間結果時間=5000秒每塊裝10個元組 需要將上一步已經連接好的106個元組重新讀入內存，按照選擇條件選取滿足條件的元組。 假定內存處理時間忽略，讀數據時間=5000秒 與寫文件一樣,忽略內存處理時間。 滿足條件的元組為100個，可以全部放在內存 仍為100個元組，可以放在內存中，不需要作I/O操作，同樣忽略內存處理時間 總時間 =10.550005000 = 10010.5秒= 2.78小時2022/7/18355.2.2查詢優化實例 Grade( Course.Cname=DataBase (Course SC) 讀取總塊數= 210塊讀數據

23、時間=210/20=10.5秒中間結果大小=10000 （減少100倍） SC:10000條寫中間結果時間=10000/10/20=50秒 這一步需要將上一步已經連接好的10000個元組重新讀入內存，檢查是否滿足選擇條件，產生一個100個元組的結果集 讀數據時間=50秒 在屬性Grade上作投影操作，不需要作I/O操作 總時間10.55050秒110.5秒=2分2022/7/18365.2.2查詢優化實例 Sname(SC Course.Cname=DataBase(Course) 對Course表進行選擇運算，需要先裝入Course表元組讀Course表總塊數= 100/10=10塊讀數據時

24、間=10/20=0.5秒選擇滿足條件的元組，產生滿足條件的結果集為1個，不必寫入外存 這一步包括將10000個SC的元組依次讀入內存，和內存中的1個Course元組作自然連接。只需讀一遍SC表總塊數= 10000/100=100塊讀數據時間=100/20=5秒 ，不需要作I/O操作 總時間0.555.5秒 2022/7/18375.2.2查詢優化實例 Grade( Course.Cname=DataBase (Course SC) Sname(SC Course.Cname=DataBase(Course)在第一個表達式中，用笛卡爾積實現兩個關系的查詢選擇條件Course.Cno = SC.C

25、no與笛卡爾積組合成連接操作條件Course.Cname =DataBase 移到連接操作中的關系Course中每一次變換都使參加連接的元組大大減少,這就是代數優化2022/7/18385.2.2查詢優化實例 Sname(SC Course.Cname=DataBase(Course)假設SC表在Cno上有索引， 讀Course表總塊數= 100/10=10塊讀數據時間 =10/20=0.5秒中間結果大小1條 不必寫入外存 不用讀取全部的SC元組，而只需要讀入與課程名“DataBase”相對應的課程代碼Cno相同的那些元組，那么讀入SC的元組數將從10000降到100， 總塊數= 100/10

26、01塊 讀數據時間 =1/20=0.05秒 基于索引掃描的方法能進一步提高查詢的性能，這就是物理優化2022/7/1839第5章 關系查詢處理和查詢優化5.1關系數據庫系統的查詢處理5.2關系數據庫系統的查詢優化5.3代數優化5.4基于存取路徑的優化5.5基于代價估算的優化5.6小結2022/7/18405.3 代數優化代數優化策略：通過對關系代數表達式的等價變換提高查詢效率 關系代數表達式等價是指用相同的關系代替兩個表達式中相應的關系所得到的結果是相同的，兩個關系表達式E1和E2是等價的，可記為E1E2 5.3.1 關系代數表達式的等價變換規則設E1、E2等是關系代數表達式，F是條件表達式l

27、. 連接、笛卡爾積交換律E1 E2 E2 E1E1 E2E2 E1 E1 F E2E2 F E1系統可以選擇小關系作為外關系進行連接,提高執行效率 2022/7/18415.3.1 關系代數表達式的等價變換規則2. 連接、笛卡爾積的結合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F1 F2 F1 F23. 投影的串接定律 A1,A2,An ( B1,B2,Bm (E) A1,A2,An (E) E是關系代數表達式Ai(i=1，2，n), Bj(j=l，2，m)是屬性名A1, A2, , An構成Bl，B2，

28、Bm的子集 對同一關系代數表達式的多個投影可以轉換成其中最小的屬性集的投影 2022/7/18425.3.1 關系代數表達式的等價變換規則4. 選擇的串接定律 ( (E) (E)選擇的串接定律說明 選擇條件可以合并這樣一次就可檢查全部條件。 5. 選擇與投影的交換律(1)假設: 選擇條件F只涉及屬性A1，An ( (E) ( (E)(2)假設: F中有不屬于A1, ,An的屬性B1,Bm ( F(E) ( F( (E)投影操作后的選擇操作可以轉換為選擇操作后的投影操作 2022/7/18435.3.1 關系代數表達式的等價變換規則6. 選擇與笛卡爾積的交換律(1) 假設：F中涉及的屬性都是E1

29、中的屬性 F (E1E2) F (E1)E2(2) 假設：F=F1F2，并且F1只涉及E1中的屬性，F2只涉及E2中的屬性， 則由上面的等價變換規則1，4，6可推出： F(E1E2) F1(E1) F2 (E2)(3) 假設： F=F1F2，F1只涉及E1中的屬性，F2涉及E1和E2兩者的屬性 F(E1E2) F2( F1(E1)E2) 它使部分選擇在笛卡爾積前先做 根據選擇條件的不同情況，可以考慮使部分選擇在笛卡爾積之前先做 2022/7/18445.3.1 關系代數表達式的等價變換規則7. 選擇與并的分配律假設：E=E1E2，E1，E2有相同的屬性名 F(E1E2) F(E1) F(E2)

30、8. 選擇與差運算的分配律假設：E1與E2有相同的屬性名 F(E1-E2) F(E1) - F(E2) 9. 選擇對自然連接的分配律 F(E1 E2) F(E1) F(E2) F只涉及E1與E2的公共屬性2022/7/18455.3.1 關系代數表達式的等價變換規則10. 投影與笛卡爾積的分配律假設：E1和E2是兩個關系表達式，A1，An是E1的屬性， B1，Bm是E2的屬性 (E1E2) (E1) (E2)l1. 投影與并的分配律假設：E1和E2 有相同的屬性名 (E1E2) (E1) (E2) 2022/7/18465.3.2代數優化策略典型的啟發式規則(1)在關系代數表達式中盡可能早地執

31、行選擇操作。 目的：減小中間關系 在優化策略中這是最重要、最基本的一條(2) 投影運算和選擇運算同時進行 目的：避免重復掃描關系如有若干投影和選擇運算，并且它們都對同一個關系操作，則可以在掃描此關系的同時完成所有的這些運算以避免重復掃描關系(3)將投影運算與其前面或后面的雙目運算結合目的：減少掃描關系的遍數2022/7/18475.3.2代數優化策略典型的啟發式規則（續）(4) 把某些選擇同在它前面要執行的笛卡爾積結合起來成為一個連接運算例： Student.Sno=SC.Sno (StudentSC) Student SC在執行連接操作前對關系適當進行預處理按連接屬性排序在連接屬性上建立索引

32、2022/7/18485.3.2代數優化策略典型的啟發式規則（續）(5) 找出公共子表達式如果這種重復出現的子表達式的結果不是很大的關系并且從外存中讀入這個關系比計算該子表達式的時間少得多，則先計算一次公共子表達式并把結果寫入中間文件是合算的當查詢的是視圖時，定義視圖的表達式就是公共子表達式的情況2022/7/18495.3.3代數優化算法 遵循這些啟發式規則，應用關系代數等價變換公式來優化關系表達式的算法。算法：關系表達式的優化輸入：一個關系表達式的查詢樹。輸出：優化的查詢樹。方法：(1) 利用等價變換規則4把形如 F1F2Fn(E)變換為 F1( F2( Fn(E)。(2) 對每一個選擇，

33、利用等價變換規則49盡可能把它移到樹的葉端。2022/7/18505.3.3代數優化算法(3) 對每一個投影利用等價變換規則3，5，10，11中的一般形式盡可能把它移向樹的葉端。注意： 等價變換規則3使一些投影消失規則5把一個投影分裂為兩個，其中一個有可能被移向樹的葉端 (4) 利用等價變換規則35把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。 使多個選擇或投影能同時執行，或在一次掃描中全部完成 2022/7/18515.3.3代數優化算法(5) 把上述得到的語法樹的內節點分組。每一雙目運算(， ，)和它所有的直接祖先為一組(這些直接祖先是, 運算)。如果其后代直到葉子全是

34、單目運算，則也將它們并入該組但當雙目運算是笛卡爾積()，而且后面不是與它組成等值連接的選擇時，則不能把選擇與這個雙目運算組成同一組，把這些單目運算單獨分為一組 2022/7/18525.3.3代數優化算法【例 53】查詢選修了“DataBase”這門課程的計算機學院的學生姓名。用SQL語句表達如下SELECT Student.Sname FROM Student，SC， Course WHERE Student.Sno=SC.Sno and Course.Cno= SC.Cno and Student.Dept=計算機學院 and Course.Cname=DataBase2022/7/185

35、35.3.3代數優化算法(1) 把SQL語句轉換成查詢樹，如下左圖所示SELECT Student.Sname FROM Student，SC， Course WHERE Student.Sno=SC.Sno and Course.Cno= SC.Cno and Student.Dept=計算機學院 and Course.Cname=DataBase2022/7/1854(2) 轉換成關系代數語法樹 SELECT Student.Sname FROM Student，SC， Course WHERE Student.Sno=SC.Sno and Course.Cno= SC.Cno and S

36、tudent.Dept=計算機學院 and Course.Cname=DataBase2022/7/18555.3.3代數優化算法（3）對查詢樹進行優化 變換選擇運算 ,得到單獨的4個選擇操作 .盡可能將選擇操作移到樹的葉端 2022/7/18565.3.3代數優化算法（3）對查詢樹進行優化(續)根據算法5.1中的(5)，每一雙目運算(， ,)和它所有的直接祖先為一組(這些直接祖先是, 運算)如果其后代直到葉子全是單目運算，則也將它們并入該組把上述得到的語法樹的內節點分組，得到優化后的查詢樹 2022/7/1857第5章 關系查詢處理和查詢優化5.1關系數據庫系統的查詢處理5.2關系數據庫系統

37、的查詢優化5.3代數優化5.4基于存取路徑的優化5.5基于代價估算的優化5.6小結2022/7/18585.4 基于存取路徑的優化代數優化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑對于一個查詢語句有許多存取方案，它們的執行效率不同， 僅僅進行代數優化是不夠的 物理優化就是要選擇高效合理的操作算法或存取路徑,求得優化的查詢計劃 2022/7/18591.選擇操作的啟發式規則(1) 對于小關系，使用全表順序掃描，即使選擇列上有索引 對于大關系，啟發式規則有：(2)對于選擇條件是“主鍵=值”的查詢，查詢結果最多是一個元組，可以選擇主鍵索引 (3) 對于選擇條件是“非主屬性=值”的查詢，并且

38、選擇列上有索引要估算查詢結果的元組數目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描(4)對于選擇條件是屬性上的非等值查詢或者范圍查詢,并且選擇列上有索引， 與(3)類似2022/7/18601.選擇操作的啟發式規則(5) 對于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引優先采用組合索引掃描方法如果某些屬性上有一般的索引則可以用索引掃描方法否則使用全表順序掃描。(6) 對于用OR連接的析取選擇條件，一般使用全表順序掃描2022/7/18612.連接操作的啟發式規則(1) 如果兩個表都已經按照連接屬性排序選用排序-合并方法(2) 如果一個表在連接屬性上有索引 選用索

39、引連接方法(3) 如果上面兩個規則都不適用，其中一個表較小 選用Hash join方法2022/7/18622.連接操作的啟發式規則(4) 可以選用嵌套循環方法，并選擇其中較小的表，確切地講是占用存儲塊數較少的表，作為外表（外循環的表）。理由：設連接表R與S分別占用的塊數為Br與Bs連接操作使用的內存緩沖區塊數為K分配K-1塊給外表如果R為外表，則嵌套循環法存取的塊數為 顯然應該選塊數小的表作為外表 2022/7/18635.5 基于代價估算的優化啟發式規則優化是定性的選擇，適合解釋執行的系統解釋執行的系統，優化開銷包含在查詢總開銷之中 編譯執行的系統中查詢優化和查詢執行是分開的可以采用精細復

40、雜一些的基于代價的優化方法 影響查詢執行代價的因素主要有：訪問存儲器的代價：搜索、讀和寫二級存儲器（主要是磁盤）上的數據庫的代價存儲代價：存儲在查詢執行時生成的中間文件的代價計算代價：在查詢執行時對內存操作的代價，包括搜索元組、排序元組、合并元組、計算等。內存使用代價：查詢執行需要的內存緩沖區數目。通信代價：查詢過程中數據在不同數據庫節點傳送的代價 2022/7/1864統計信息基于代價的優化方法要計算各種操作算法的執行代價，與數據庫的狀態密切相關 數據字典中存儲的優化器需要的統計信息： 1. 對每個基本表該表的元組總數(N)元組長度(l)占用的塊數(B)占用的溢出塊數(BO)2022/7/1865統計信息數據字典中存儲的優化器需要的統計信息(續)： 2. 對基表的每個列該列不同值的個數(m)選擇率(f)如果不同值的分布是均勻的，f1/m如果不同值的分布不均勻，則每個值的選擇率f 具有該值的元組數/N該列最大值該列最小值該列上是否已經建立了索引索引類型(B+樹索引、Hash索引、聚集索引)2022/7/1866統計信息數據字典中存儲的優化器需要的統計信息(續)： 3. 對索引(如