1、An Introduction to Database Systems數據庫系統概論數據庫系統概論An Introduction to Database System第九章第九章 關系查詢處理和查詢優化關系查詢處理和查詢優化An Introduction to Database Systems第九章第九章 關系系統及其查詢優化關系系統及其查詢優化9.1 關系數據庫系統的查詢處理關系數據庫系統的查詢處理 9.2 關系數據庫系統的查詢優化關系數據庫系統的查詢優化 9.3 代數優化代數優化9.4 物理優化物理優化 9.5 小小 結結 An Introduction to Database Syste

2、ms關系系統及其查詢優化（續）關系系統及其查詢優化（續）v本章目的：本章目的： RDBMS的查詢處理步驟 查詢優化的概念 基本方法和技術 v查詢優化分類 ： 代數優化 物理優化An Introduction to Database Systems9.1 關系數據庫系統的查詢處理關系數據庫系統的查詢處理v9.1.1 查詢處理步驟查詢處理步驟v9.1.2 實現查詢操作的算法示例實現查詢操作的算法示例 An Introduction to Database Systems9.1.1 查詢處理步驟查詢處理步驟vRDBMS查詢處理階段查詢處理階段 ： 1. 查詢分析2. 查詢檢查3. 查詢優化 4. 查

3、詢執行 An Introduction to Database Systems查詢處理步驟（續）查詢處理步驟（續）查詢處理步驟An Introduction to Database Systems1. 查詢分析查詢分析v對查詢語句進行掃描、詞法分析和語法分析 v從查詢語句中識別出語言符號 v進行語法檢查和語法分析 An Introduction to Database Systems2. 查詢檢查查詢檢查 v 根據數據字典對合法的查詢語句進行語義檢查 v 根據數據字典中的用戶權限和完整性約束定義對用戶的存取權限進行檢查 v 檢查通過后把SQL查詢語句轉換成等價的關系代數表達式 v RDBMS一

4、般都用查詢樹(語法分析樹)來表示擴展的關系代數表達式 v 把數據庫對象的外部名稱轉換為內部表示 An Introduction to Database Systems3. 查詢優化查詢優化v查詢優化：選擇一個高效執行的查詢處理策略 v查詢優化分類 ： 代數優化：指關系代數表達式的優化 物理優化：指存取路徑和底層操作算法的選擇v查詢優化方法選擇的依據： 基于規則(rule based) 基于代價(cost based) 基于語義(semantic based)An Introduction to Database Systems4. 查詢執行查詢執行 v依據優化器得到的執行策略生成查詢計劃v代碼

5、生成器(code generator)生成執行查詢計劃的代碼 An Introduction to Database Systems9.1 關系數據庫系統的查詢處理關系數據庫系統的查詢處理v9.1.1 查詢處理步驟查詢處理步驟v9.1.2 實現查詢操作的算法示例實現查詢操作的算法示例 An Introduction to Database Systems9.1.2 實現查詢操作的算法示例實現查詢操作的算法示例 v一、 選擇操作的實現 v二、 連接操作的實現 An Introduction to Database Systems一、一、 選擇操作的實現選擇操作的實現 v例1Select * fr

6、om student where ；考慮的幾種情況： C1：無條件； C2：Sno200215121； C3：Sage20； C4：SdeptCS AND Sage20； An Introduction to Database Systems選擇操作的實現（續）選擇操作的實現（續）v選擇操作典型實現方法：選擇操作典型實現方法： 1. 簡單的全表掃描方法簡單的全表掃描方法 對查詢的基本表順序掃描，逐一檢查每個元組是否滿足選擇條件，把滿足條件的元組作為結果輸出 適合小表，不適合大表 2. 索引索引(或散列或散列)掃描方法掃描方法 適合選擇條件中的屬性上有索引(例如B+樹索引或Hash索引) 通過索

7、引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組 An Introduction to Database Systems選擇操作的實現（續）選擇操作的實現（續）v 例1-C2 以C2為例，Sno200215121，并且Sno上有索引(或Sno是散列碼) 使用索引(或散列)得到Sno為200215121 元組的指針 通過元組指針在student表中檢索到該學生v 例1-C3 以C3為例，Sage20，并且Sage 上有B+樹索引 使用B+樹索引找到Sage20的索引項，以此為入口點在B+樹的順序集上得到Sage20的所有元組指針 通過這些元組指針到student表

8、中檢索到所有年齡大于20的學生。 An Introduction to Database Systems選擇操作的實現（續）選擇操作的實現（續）v例1-C4 以C4為例，SdeptCS AND Sage20，如果Sdept和Sage上都有索引： 算法一：分別用上面兩種方法分別找到SdeptCS的一組元組指針和Sage20的另一組元組指針求這2組指針的交集到student表中檢索得到計算機系年齡大于20的學生 算法二：找到SdeptCS的一組元組指針，通過這些元組指針到student表中檢索對得到的元組檢查另一些選擇條件(如Sage20)是否滿足把滿足條件的元組作為結果輸出。 An Introd

9、uction to Database Systems二、二、 連接操作的實現連接操作的實現 v連接操作是查詢處理中最耗時的操作之一 v本節只討論等值連接(或自然連接)最常用的實現算法 v 例2 SELECT * FROM Student，SC WHERE Student.Sno=SC.Sno； An Introduction to Database Systems連接操作的實現（續）連接操作的實現（續）v1. 嵌套循環方法(nested loop) v2. 排序-合并方法(sort-merge join 或merge join)v3. 索引連接(index join)方法 v4. Hash J

10、oin方法 An Introduction to Database Systems連接操作的實現（續）連接操作的實現（續）1.嵌套循環方法嵌套循環方法(nested loop)對外層循環(Student)的每一個元組(s)，檢索內層循環(SC)中的每一個元組(sc)檢查這兩個元組在連接屬性(sno)上是否相等如果滿足連接條件，則串接后作為結果輸出，直到外層循環表中的元組處理完為止 An Introduction to Database Systems連接操作的實現（續）連接操作的實現（續）2. 排序排序-合并方法合并方法(sort-merge join 或或merge join) 適合連接的諸

11、表已經排好序的情況 排序合并連接方法的步驟：如果連接的表沒有排好序，先對Student表和SC表按連接屬性Sno排序 取Student表中第一個Sno，依次掃描SC表中具有相同Sno的元組 An Introduction to Database Systems連接操作的實現（續）連接操作的實現（續）200215121200215122200215123200215124.200215121 1 92200215121 2 85200215121 3 88200215122 2 90200215122 3 80.排序-合并連接方法示意圖An Introduction to Database Sy

12、stems連接操作的實現（續）連接操作的實現（續） 排序合并連接方法的步驟（續）：當掃描到Sno不相同的第一個SC元組時，返回Student表掃描它的下一個元組，再掃描SC表中具有相同Sno的元組，把它們連接起來 重復上述步驟直到Student 表掃描完An Introduction to Database Systems連接操作的實現（續）連接操作的實現（續）v Student表和SC表都只要掃描一遍v 如果2個表原來無序，執行時間要加上對兩個表的排序時間v 對于2個大表，先排序后使用sort-merge join方法執行連接，總的時間一般仍會大大減少 An Introduction to

13、Database Systems連接操作的實現（續）連接操作的實現（續）3. 索引連接索引連接(index join)方法方法v 步驟： 在SC表上建立屬性Sno的索引，如果原來沒有該索引 對Student中每一個元組，由Sno值通過SC的索引查找相應的SC元組 把這些SC元組和Student元組連接起來 循環執行，直到Student表中的元組處理完為止 An Introduction to Database Systems連接操作的實現（續）連接操作的實現（續）4. Hash Join方法方法 把連接屬性作為hash碼，用同一個hash函數把R和S中的元組散列到同一個hash文件中 步驟：步

14、驟： 劃分階段(partitioning phase)： 對包含較少元組的表(比如R)進行一遍處理 把它的元組按hash函數分散到hash表的桶中 試探階段(probing phase)：也稱為連接階段(join phase) 對另一個表(S)進行一遍處理 把S的元組散列到適當的hash桶中 把元組與桶中所有來自R并與之相匹配的元組連接起來 An Introduction to Database Systems連接操作的實現（續）連接操作的實現（續）v上面hash join算法前提：假設兩個表中較小的表在第一階段后可以完全放入內存的hash桶中 v以上的算法思想可以推廣到更加一般的多個表的連接

15、算法上 An Introduction to Database Systems第九章第九章 關系系統及其查詢優化關系系統及其查詢優化9.1 關系數據庫系統的查詢處理關系數據庫系統的查詢處理 9.2 關系數據庫系統的查詢優化關系數據庫系統的查詢優化 9.3 代代 數數 優優 化化 9.4 物物 理理 優優 化化 9.5 小小 結結 An Introduction to Database Systems9.2 關系數據庫系統的查詢優化關系數據庫系統的查詢優化v查詢優化在關系數據庫系統中有著非常重要的地位 v關系查詢優化是影響RDBMS性能的關鍵因素 v由于關系表達式的語義級別很高，使關系系統可以從

16、關系表達式中分析查詢語義，提供了執行查詢優化的可能性 An Introduction to Database Systems9.2 關系數據庫系統的查詢優化關系數據庫系統的查詢優化v9.2.1 查詢優化概述查詢優化概述v9.2.2 一個實例一個實例 An Introduction to Database Systems9.2.1 查詢優化概述查詢優化概述v關系系統的查詢優化v非關系系統An Introduction to Database Systems查詢優化概述（續）查詢優化概述（續）v 查詢優化的優點不僅在于用戶不必考慮如何最好地表達查詢以獲得較好的效率，而且在于系統可以比用戶程序的“優

17、化”做得更好 (1) 優化器可以從數據字典中獲取許多統計信息，而用戶程序則難以獲得這些信息 (2)如果數據庫的物理統計信息改變了，系統可以自動對查詢重新優化以選擇相適應的執行計劃。在非關系系統中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。An Introduction to Database Systems查詢優化概述（續）查詢優化概述（續） (3)優化器可以考慮數百種不同的執行計劃，程序員一般只能考慮有限的幾種可能性。 (4)優化器中包括了很多復雜的優化技術，這些優化技術往往只有最好的程序員才能掌握。系統的自動優化相當于使得所有人都擁有這些優化技術An Introduction t

18、o Database Systems查詢優化概述（續）查詢優化概述（續）v RDBMS通過某種代價模型計算出各種查詢執行策略的執行代價，然后選取代價最小的執行方案 集中式數據庫執行開銷主要包括： 磁盤存取塊數(I/O代價) 處理機時間(CPU代價) 查詢的內存開銷 I/O代價是最主要的 分布式數據庫總代價=I/O代價+CPU代價+內存代價通信代價 An Introduction to Database Systems查詢優化概述（續）查詢優化概述（續）v查詢優化的總目標： 選擇有效的策略 求得給定關系表達式的值 使得查詢代價最小(實際上是較小) An Introduction to Datab

19、ase Systems9.2 關系數據庫系統的查詢優化關系數據庫系統的查詢優化v9.2.1 查詢優化概述查詢優化概述v9.2.2 一個實例一個實例 An Introduction to Database Systems9.2.2 一個實例一個實例例3 求選修了2號課程的學生姓名。用SQL表達： SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2； n假定學生-課程數據庫中有1000個學生記錄，10000個選課記錄n其中選修2號課程的選課記錄為50個 An Introduction to Datab

20、ase Systems一個實例（續）一個實例（續）v系統可以用多種等價的關系代數表達式來完成這一查詢Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)Q2=Sname(Sc.Cno=2 (Student SC)Q3=Sname(Student Sc.Cno=2(SC)An Introduction to Database Systems一個實例（續）一個實例（續）v 一、第一種情況一、第一種情況 Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 StudentSC)1. 計算廣義笛卡爾積 v 把Student和SC的每個元組連接

21、起來的做法： 在內存中盡可能多地裝入某個表(如Student表)的若干塊，留出一塊存放另一個表(如SC表)的元組。 把SC中的每個元組和Student中每個元組連接，連接后的元組裝滿一塊后就寫到中間文件上 從SC中讀入一塊和內存中的Student元組連接，直到SC表處理完。 再讀入若干塊Student元組，讀入一塊SC元組 重復上述處理過程，直到把Student表處理完An Introduction to Database Systems一個實例（續）一個實例（續）v 設一個塊能裝10個Student元組或100個SC元組，在內存中存放5塊Student元組和1塊SC元組，則讀取總塊數為 =1

22、00+20100=2100塊v 其中，讀Student表100塊。讀SC表20遍，每遍100塊。若每秒讀寫20塊，則總計要花105s v 連接后的元組數為103104=107。設每塊能裝10個元組，則寫出這些塊要用106/20=5104s 101000510100010010000An Introduction to Database Systems一個實例（續）一個實例（續）2. 作選擇操作 依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄 假定內存處理時間忽略。讀取中間文件花費的時間(同寫中間文件一樣)需5104s 滿足條件的元組假設僅50個，均可放在內存 An Introductio

23、n to Database Systems一個實例（續）一個實例（續）3. 作投影操作 把第2步的結果在Sname上作投影輸出，得到最終結果 第一種情況下執行查詢的總時間105+25104105s 所有內存處理時間均忽略不計 An Introduction to Database Systems一個實例（續）一個實例（續）v二、二、 第二種情況第二種情況 Q2=Sname(Sc.Cno=2 (Student SC)1. 計算自然連接 執行自然連接，讀取Student和SC表的策略不變，總的讀取塊數仍為2100塊花費105 s 自然連接的結果比第一種情況大大減少，為104個 寫出這些元組時間為1

24、04/10/20=50s，為第一種情況的千分之一 2. 讀取中間文件塊，執行選擇運算，花費時間也為50s。3. 把第2步結果投影輸出。 第二種情況總的執行時間105+50+50205s An Introduction to Database Systems一個實例（續）一個實例（續）v三、三、 第三種情況第三種情況 Q3=Sname(Student Sc.Cno=2(SC)1. 先對SC表作選擇運算，只需讀一遍SC表，存取100塊花費時間為5s，因為滿足條件的元組僅50個，不必使用中間文件。2. 讀取Student表，把讀入的Student元組和內存中的SC元組作連接。也只需讀一遍Studen

25、t表共100塊，花費時間為5s。3. 把連接結果投影輸出 第三種情況總的執行時間5+510s An Introduction to Database Systems一個實例（續）一個實例（續）v 假如SC表的Cno字段上有索引 第一步就不必讀取所有的SC元組而只需讀取Cno=2的那些元組(50個) 存取的索引塊和SC中滿足條件的數據塊大約總共34塊v 若Student表在Sno上也有索引 第二步也不必讀取所有的Student元組 因為滿足條件的SC記錄僅50個，涉及最多50個Student記錄 讀取Student表的塊數也可大大減少 v 總的存取時間將進一步減少到數秒 An Introduct

26、ion to Database Systems一個實例（續）一個實例（續）v把代數表達式Q1變換為Q2、 Q3， 即有選擇和連接操作時，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數優化v在Q3中 SC表的選擇操作算法有全表掃描和索引掃描2種方法，經過初步估算，索引掃描方法較優 對于Student和SC表的連接，利用Student表上的索引，采用index join代價也較小，這就是物理優化 An Introduction to Database Systems第九章第九章 關系系統及其查詢優化關系系統及其查詢優化9.1 關系數據庫系統的查詢處理關系數據庫系統的查詢處理 9.2 關系

27、數據庫系統的查詢優化關系數據庫系統的查詢優化 9.3 代數優化代數優化 9.4 物理優化物理優化 9.5 小小 結結 An Introduction to Database Systems9.3 代代 數數 優優 化化v9.3.1 關系代數表達式等價變換規則關系代數表達式等價變換規則 v9.3.2 查詢樹的啟發式優化查詢樹的啟發式優化 An Introduction to Database Systems9.3.1 關系代數表達式等價變換規則關系代數表達式等價變換規則 v代數優化策略：通過對關系代數表達式的等價變換來提高查詢效率 v關系代數表達式的等價：指用相同的關系代替兩個表達式中相應的關系

28、所得到的結果是相同的v兩個關系表達式E1和E2是等價的，可記為E1E2 An Introduction to Database Systems關系代數表達式等價變換規則（續）關系代數表達式等價變換規則（續）v 常用的等價變換規則：常用的等價變換規則：1. 連接、笛卡爾積交換律 設E1和E2是關系代數表達式，F是連接運算的條件，則有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E12. 連接、笛卡爾積的結合律 設E1，E2，E3是關系代數表達式，F1和F2是連接運算的條件，則有 (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E

29、3E1 (E2 E3) An Introduction to Database Systems關系代數表達式等價變換規則（續）關系代數表達式等價變換規則（續）3. 投影的串接定律 ( (E) (E)這里，E是關系代數表達式，Ai(i=1，2，n)，Bj(j=1，2，m)是屬性名且A1，A2，An構成B1，B2，Bm的子集。4. 選擇的串接定律 ( (E) (E)這里，E是關系代數表達式，F1、F2是選擇條件。 選擇的串接律說明選擇條件可以合并。這樣一次就可檢查全部條件。nAAA,21mBBB,21nAAA,211F2F21FF An Introduction to Database Syste

30、ms關系代數表達式等價變換規則（續）關系代數表達式等價變換規則（續）5. 選擇與投影操作的交換律 F( (E) (F(E)選擇條件F只涉及屬性A1，An。若F中有不屬于A1，An的屬性B1，Bm則有更一般的規則： (F(E) (F( (E)nAAA,21nAAA,21nAAA,21nAAA,21mnBBBAAA,2121An Introduction to Database Systems關系代數表達式等價變換規則（續）關系代數表達式等價變換規則（續）6. 選擇與笛卡爾積的交換律如果F中涉及的屬性都是E1中的屬性，則 (E1E2) (E1)E2如果F=F1F2，并且F1只涉及E1中的屬性，F2

31、只涉及E2中的屬性，則由上面的等價變換規則1，4，6可推出： (E1E2) (E1) (E2)若F1只涉及E1中的屬性，F2涉及E1和E2兩者的屬性，則仍有 (E1E2) ( (E1)E2)它使部分選擇在笛卡爾積前先做。 1F2F2F1FFFFFAn Introduction to Database Systems關系代數表達式等價變換規則（續）關系代數表達式等價變換規則（續）7. 選擇與并的分配律設E=E1E2，E1，E2有相同的屬性名，則 F(E1E2)F(E1)F(E2)8. 選擇與差運算的分配律若E1與E2有相同的屬性名，則 F(E1-E2)F(E1)-F(E2)9. 選擇對自然連接的

32、分配律 F(E1 E2)F(E1) F(E2) F只涉及E1與E2的公共屬性 An Introduction to Database Systems關系代數表達式等價變換規則（續）關系代數表達式等價變換規則（續）10. 投影與笛卡爾積的分配律設E1和E2是兩個關系表達式，A1，An是E1的屬性，B1，Bm是E2的屬性，則 (E1E2) (E1) (E2)11. 投影與并的分配律設E1和E2有相同的屬性名，則 (E1E2) (E1) (E2)mnBBBAAA,2121nAAA,21mBBB,21nAAA,21nAAA,21nAAA,21An Introduction to Database Sy

33、stems9.3 代代 數數 優優 化化v9.3.1 關系代數表達式等價變換規則關系代數表達式等價變換規則 v9.3.2 查詢樹的啟發式優化查詢樹的啟發式優化 An Introduction to Database Systems9.3.2 查詢樹的啟發式優化查詢樹的啟發式優化 v典型的啟發式規則：典型的啟發式規則：1. 選擇運算應盡可能先做。在優化策略中這是最重要、最基本的一條2. 把投影運算和選擇運算同時進行如有若干投影和選擇運算，并且它們都對同一個關系操作，則可以在掃描此關系的同時完成所有的這些運算以避免重復掃描關系An Introduction to Database Systems查

34、詢樹的啟發式優化（續）查詢樹的啟發式優化（續）3. 把投影同其前或其后的雙目運算結合起來4. 把某些選擇同在它前面要執行的笛卡爾積結合起來成為一個連接運算5. 找出公共子表達式如果這種重復出現的子表達式的結果不是很大的關系并且從外存中讀入這個關系比計算該子表達式的時間少得多，則先計算一次公共子表達式并把結果寫入中間文件是合算的當查詢的是視圖時，定義視圖的表達式就是公共子表達式的情況An Introduction to Database Systems查詢樹的啟發式優化（續）查詢樹的啟發式優化（續）v 遵循這些啟發式規則，應用9.3.1的等價變換公式來優化關系表達式的算法。算法：關系表達式的優化

35、輸入：一個關系表達式的查詢樹輸出：優化的查詢樹方法：(1) 利用等價變換規則4把形如F1F2Fn(E)變換為F1(F2(Fn(E)。(2) 對每一個選擇，利用等價變換規則49盡可能把它移到樹的葉端。An Introduction to Database Systems查詢樹的啟發式優化（續）查詢樹的啟發式優化（續）(3) 對每一個投影利用等價變換規則3，5，10，11中的一般形式盡可能把它移向樹的葉端。 注意： 等價變換規則3使一些投影消失規則5把一個投影分裂為兩個，其中一個有可能被移向樹的葉端 (4) 利用等價變換規則35把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多

36、個選擇或投影能同時執行，或在一次掃描中全部完成 An Introduction to Database Systems查詢樹的啟發式優化（續）查詢樹的啟發式優化（續） (5) 把上述得到的語法樹的內節點分組。每一雙目運算(， ，-)和它所有的直接祖先為一組(這些直接祖先是(，運算)。 如果其后代直到葉子全是單目運算，則也將它們并入該組 但當雙目運算是笛卡爾積()，而且后面不是與它組成等值連接的選擇時，則不能把選擇與這個雙目運算組成同一組，把這些單目運算單獨分為一組 An Introduction to Database Systems查詢樹的啟發式優化（續）查詢樹的啟發式優化（續）例4 下面給

37、出例3中 SQL語句的代數優化示例。 (1) 把SQL語句轉換成查詢樹，如下圖所示查詢樹An Introduction to Database Systems查詢樹的啟發式優化（續）查詢樹的啟發式優化（續）為了使用關系代數表達式的優化法，假設內部表示是關系代數語法樹，則上面的查詢樹如下圖所示。 關系代數語法樹 An Introduction to Database Systems查詢樹的啟發式優化（續）查詢樹的啟發式優化（續）(2) 對查詢樹進行優化利用規則4、6把選擇SC.Cno=2移到葉端，查詢樹便轉換成下圖所示的優化的查詢樹。這就是9.2.2節中Q3的查詢樹表示優化后的查詢樹 An In

38、troduction to Database Systems第九章第九章 關系系統及其查詢優化關系系統及其查詢優化9.1 關系數據庫系統的查詢處理關系數據庫系統的查詢處理 9.2 關系數據庫系統的查詢優化關系數據庫系統的查詢優化 9.3 代數優化代數優化 9.4 物理優化物理優化 9.5 小小 結結 An Introduction to Database Systems9.4 物理優化物理優化v代數優化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑v對于一個查詢語句有許多存取方案，它們的執行效率不同， 僅僅進行代數優化是不夠的 v物理優化就是要選擇高效合理的操作算法或存取路徑，求得優化的

39、查詢計劃 An Introduction to Database Systems物理優化（續）物理優化（續）v選擇的方法：選擇的方法： 基于規則的啟發式優化 基于代價估算的優化 兩者結合的優化方法An Introduction to Database Systems9.4 物理優化物理優化v9.4.1 基于啟發式規則的存取路徑選擇優化基于啟發式規則的存取路徑選擇優化v9.4.2 基于代價的優化基于代價的優化 An Introduction to Database Systems9.4.1 基于啟發式規則的存取路徑選擇優化基于啟發式規則的存取路徑選擇優化v一、 選擇操作的啟發式規則 v二、 連接

40、操作的啟發式規則 An Introduction to Database Systems基于啟發式規則的存取路徑選擇優化基于啟發式規則的存取路徑選擇優化(續續)v一、一、 選擇操作的啟發式規則選擇操作的啟發式規則:1. 對于小關系，使用全表順序掃描，即使選擇列上有索引 對于大關系，啟發式規則有：對于大關系，啟發式規則有：2. 對于選擇條件是主碼值的查詢查詢結果最多是一個元組，可以選擇主碼索引一般的RDBMS會自動建立主碼索引。An Introduction to Database Systems基于啟發式規則的存取路徑選擇優化基于啟發式規則的存取路徑選擇優化(續續)3. 對于選擇條件是非主屬性

41、值的查詢，并且選擇列上有索引n要估算查詢結果的元組數目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描An Introduction to Database Systems基于啟發式規則的存取路徑選擇優化基于啟發式規則的存取路徑選擇優化(續續)4. 對于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引n要估算查詢結果的元組數目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描 An Introduction to Database Systems基于啟發式規則的存取路徑選擇優化基于啟發式規則的存取路徑選擇優化(續續)5. 對于用AND連接的合取選擇

42、條件n如果有涉及這些屬性的組合索引優先采用組合索引掃描方法n如果某些屬性上有一般的索引則可以用例1-C4中介紹的索引掃描方法否則使用全表順序掃描。6. 對于用OR連接的析取選擇條件，一般使用全表順序掃描An Introduction to Database Systems基于啟發式規則的存取路徑選擇優化基于啟發式規則的存取路徑選擇優化(續續)v 二、二、 連接操作的啟發式規則：連接操作的啟發式規則：1. 如果2個表都已經按照連接屬性排序n 選用排序-合并方法2. 如果一個表在連接屬性上有索引n 選用索引連接方法3. 如果上面2個規則都不適用，其中一個表較小n 選用Hash join方法An I

43、ntroduction to Database Systems基于啟發式規則的存取路徑選擇優化基于啟發式規則的存取路徑選擇優化(續續)4. 可以選用嵌套循環方法，并選擇其中較小的表，確切地講是占用的塊數(b)較少的表，作為外表(外循環的表) 。 理由： 設連接表R與S分別占用的塊數為Br與Bs 連接操作使用的內存緩沖區塊數為K 分配K-1塊給外表 如果R為外表，則嵌套循環法存取的塊數為Br+( Br/K-1)Bs 顯然應該選塊數小的表作為外表 An Introduction to Database Systems9.4 物理優化（續）物理優化（續）v9.4.1 基于啟發式規則的存取路徑選擇優化

44、基于啟發式規則的存取路徑選擇優化v9.4.2 基于代價的優化基于代價的優化 An Introduction to Database Systems9.4.2 基于代價的優化基于代價的優化 v啟發式規則優化是定性的選擇，適合解釋執行的系統 解釋執行的系統，優化開銷包含在查詢總開銷之中 v編譯執行的系統中查詢優化和查詢執行是分開的 可以采用精細復雜一些的基于代價的優化方法 An Introduction to Database Systems基于代價的優化（續）基于代價的優化（續）v一、 統計信息 v二、 代價估算示例 An Introduction to Database Systems基于代價

45、的優化（續）基于代價的優化（續）一、一、 統計信息統計信息v基于代價的優化方法要計算各種操作算法的執行代價，與數據庫的狀態密切相關 v數據字典中存儲的優化器需要的統計信息： 1. 對每個基本表n該表的元組總數(N)n元組長度(l)n占用的塊數(B)n占用的溢出塊數(BO)An Introduction to Database Systems基于代價的優化（續）基于代價的優化（續）2. 對基表的每個列n該列不同值的個數(m)n選擇率(f)如果不同值的分布是均勻的，f1/m如果不同值的分布不均勻，則每個值的選擇率具有該值的元組數/Nn該列最大值n該列最小值n該列上是否已經建立了索引n索引類型(B+樹索引、Hash索引、聚集索引)An Introduction to Database Systems基于代價的優化（續）基于代價的優化（續）3. 對索引(如B+樹索引)n索引的層數(