數(shù)據(jù)庫系統(tǒng)概論：第9章 關(guān)系查詢處理和查詢優(yōu)化

1、An Introduction to Database System數(shù)據(jù)庫系統(tǒng)概論 An Introduction to Database System第九章第九章 關(guān)系查詢處理關(guān)系查詢處理 和查詢優(yōu)化和查詢優(yōu)化An Introduction to Database System第三篇第三篇 系統(tǒng)篇系統(tǒng)篇 v討論數(shù)據(jù)庫管理系統(tǒng)中查詢處理和事務(wù)管理的基討論數(shù)據(jù)庫管理系統(tǒng)中查詢處理和事務(wù)管理的基本概念和基礎(chǔ)知識(shí)本概念和基礎(chǔ)知識(shí)n第第9章章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化n第第10章章 數(shù)據(jù)庫恢復(fù)技術(shù)數(shù)據(jù)庫恢復(fù)技術(shù)n第第11章章 并發(fā)控制并發(fā)控制n第第12章章 數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理

2、系統(tǒng)An Introduction to Database System第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化代數(shù)優(yōu)化 9.4 物理優(yōu)化物理優(yōu)化 *9.5 查詢計(jì)劃的執(zhí)行查詢計(jì)劃的執(zhí)行9.6 小小 結(jié)結(jié) An Introduction to Database System關(guān)系查詢處理和查詢優(yōu)化（續(xù)）關(guān)系查詢處理和查詢優(yōu)化（續(xù)）v本章內(nèi)容：本章內(nèi)容： n關(guān)系數(shù)據(jù)庫管理系統(tǒng)的查詢處理步驟關(guān)系數(shù)據(jù)庫管理系統(tǒng)的查詢處理步驟 n查詢優(yōu)化的概念查詢優(yōu)化的概

3、念 n基本方法和技術(shù)基本方法和技術(shù) v查詢優(yōu)化分類查詢優(yōu)化分類 ：n代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化 n物理優(yōu)化：指存取路徑和底層操作算法的選擇物理優(yōu)化：指存取路徑和底層操作算法的選擇An Introduction to Database System9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1 查詢處理步驟查詢處理步驟9.1.2 實(shí)現(xiàn)查詢操作的算法示例實(shí)現(xiàn)查詢操作的算法示例 An Introduction to Database System9.1.1 查詢處理步驟查詢處理步驟v關(guān)系數(shù)據(jù)庫管理系統(tǒng)查詢處理階段關(guān)系數(shù)據(jù)庫管理系統(tǒng)查詢處理階段

4、 ： 1. 查詢分析查詢分析2. 查詢檢查查詢檢查3. 查詢優(yōu)化查詢優(yōu)化 4. 查詢執(zhí)行查詢執(zhí)行 An Introduction to Database System查詢處理步驟（續(xù)）查詢處理步驟（續(xù)）查詢計(jì)劃的執(zhí)行代碼查詢計(jì)劃的執(zhí)行代碼代數(shù)優(yōu)化代數(shù)優(yōu)化物理優(yōu)化等物理優(yōu)化等查詢語句查詢語句詞法分析詞法分析語法分析語法分析語義分析語義分析符號名轉(zhuǎn)換符號名轉(zhuǎn)換安全性檢查安全性檢查完整性初步檢查完整性初步檢查代碼生成代碼生成查詢執(zhí)行計(jì)劃查詢執(zhí)行計(jì)劃查詢樹查詢樹(query tree)查詢分析查詢分析查詢檢查查詢檢查查詢優(yōu)化查詢優(yōu)化查詢執(zhí)行查詢執(zhí)行數(shù)據(jù)庫數(shù)據(jù)庫數(shù)據(jù)字典數(shù)據(jù)字典An Introducti

5、on to Database System 1. 查詢分析查詢分析v查詢分析的任務(wù)：對查詢語句進(jìn)行掃描、詞法分查詢分析的任務(wù)：對查詢語句進(jìn)行掃描、詞法分析和語法分析析和語法分析n詞法分析：從查詢語句中識(shí)別出正確的語言符號詞法分析：從查詢語句中識(shí)別出正確的語言符號 n語法分析：進(jìn)行語法檢查語法分析：進(jìn)行語法檢查An Introduction to Database System 2. 查詢檢查查詢檢查 v查詢檢查的任務(wù)查詢檢查的任務(wù)n合法權(quán)檢查合法權(quán)檢查n視圖轉(zhuǎn)換視圖轉(zhuǎn)換n安全性檢查安全性檢查n完整性初步檢查完整性初步檢查v根據(jù)數(shù)據(jù)字典中有關(guān)的模式定義檢查語句中的數(shù)根據(jù)數(shù)據(jù)字典中有關(guān)的模式定義檢

6、查語句中的數(shù)據(jù)庫對象，如關(guān)系名、屬性名是否存在和有效據(jù)庫對象，如關(guān)系名、屬性名是否存在和有效 v如果是對視圖的操作，則要用視圖消解方法把對如果是對視圖的操作，則要用視圖消解方法把對視圖的操作轉(zhuǎn)換成對基本表的操作視圖的操作轉(zhuǎn)換成對基本表的操作An Introduction to Database System 2. 查詢檢查查詢檢查 v根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用戶的存取權(quán)限進(jìn)行檢查用戶的存取權(quán)限進(jìn)行檢查v檢查通過后把檢查通過后把SQL查詢語句轉(zhuǎn)換成內(nèi)部表示，即查詢語句轉(zhuǎn)換成內(nèi)部表示，即等價(jià)的等價(jià)的關(guān)系代數(shù)表達(dá)式關(guān)系代數(shù)表達(dá)式。v關(guān)系數(shù)據(jù)

7、庫管理系統(tǒng)一般都用查詢樹，也稱為語關(guān)系數(shù)據(jù)庫管理系統(tǒng)一般都用查詢樹，也稱為語法分析樹法分析樹來表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式。來表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式。An Introduction to Database System 3. 查詢優(yōu)化查詢優(yōu)化v查詢優(yōu)化：選擇一個(gè)高效執(zhí)行的查詢處理策略查詢優(yōu)化：選擇一個(gè)高效執(zhí)行的查詢處理策略 v查詢優(yōu)化分類查詢優(yōu)化分類 n代數(shù)優(yōu)化代數(shù)優(yōu)化/邏輯優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化邏輯優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化n物理優(yōu)化：指存取路徑和底層操作算法的選擇物理優(yōu)化：指存取路徑和底層操作算法的選擇v查詢優(yōu)化的選擇依據(jù)查詢優(yōu)化的選擇依據(jù)n基于規(guī)則基于規(guī)則(rule based)n

8、基于代價(jià)基于代價(jià)(cost based)n基于語義基于語義(semantic based)An Introduction to Database System 4. 查詢執(zhí)行查詢執(zhí)行 v依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢執(zhí)行計(jì)劃依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢執(zhí)行計(jì)劃v代碼生成器代碼生成器(code generator)生成執(zhí)行查詢計(jì)劃生成執(zhí)行查詢計(jì)劃的代碼的代碼 v兩種執(zhí)行方法兩種執(zhí)行方法n自頂向下自頂向下n自底向上自底向上An Introduction to Database System9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1 查詢處理步驟查詢處理步驟9.1.2

9、實(shí)現(xiàn)查詢操作的算法示例實(shí)現(xiàn)查詢操作的算法示例 An Introduction to Database System9.1.2 實(shí)現(xiàn)查詢操作的算法示例實(shí)現(xiàn)查詢操作的算法示例 1. 選擇操作的實(shí)現(xiàn)選擇操作的實(shí)現(xiàn) 2. 連接操作的實(shí)現(xiàn)連接操作的實(shí)現(xiàn) An Introduction to Database System1.選擇操作的實(shí)現(xiàn)選擇操作的實(shí)現(xiàn)v選擇操作典型實(shí)現(xiàn)方法：選擇操作典型實(shí)現(xiàn)方法：（1） 全表掃描方法全表掃描方法 (Table Scan)l對查詢的基本表順序掃描，逐一檢查每個(gè)元組是否滿足對查詢的基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出選擇條件，把滿足

10、條件的元組作為結(jié)果輸出 l適合小表，不適合大表適合小表，不適合大表（2）索引掃描方法）索引掃描方法 (Index Scan)l適合于選擇條件中的屬性上有索引適合于選擇條件中的屬性上有索引(例如例如B+樹索引或樹索引或Hash索引索引) l通過索引先找到滿足條件的元組主碼或元組指針，再通通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組過元組指針直接在查詢的基本表中找到元組 An Introduction to Database System選擇操作的實(shí)現(xiàn)（續(xù)）選擇操作的實(shí)現(xiàn)（續(xù)） v例例9.1 SELECT * FROM Student WHERE 考慮考慮

11、的幾種情況：的幾種情況： C1：無條件；：無條件； C2：Sno201215121； C3：Sage20； C4：SdeptCS AND Sage20； An Introduction to Database System選擇操作的實(shí)現(xiàn)（續(xù)）選擇操作的實(shí)現(xiàn)（續(xù)） v全表掃描算法全表掃描算法n假設(shè)可以使用的內(nèi)存為假設(shè)可以使用的內(nèi)存為M塊，全表掃描算法思想：塊，全表掃描算法思想： 按照物理次序讀按照物理次序讀Student的的M塊到內(nèi)存塊到內(nèi)存 檢查內(nèi)存的每個(gè)元組檢查內(nèi)存的每個(gè)元組t，如果滿足選擇條件，則輸出，如果滿足選擇條件，則輸出t 如果如果student還有其他塊未被處理，重復(fù)和還有其他塊未

12、被處理，重復(fù)和An Introduction to Database System選擇操作的實(shí)現(xiàn)（續(xù)）選擇操作的實(shí)現(xiàn)（續(xù)）v索引掃描算法索引掃描算法v例例9.1-C2 SELECT * FROM Student WHERE Sno=201215121n假設(shè)假設(shè)Sno上有索引上有索引(或或Sno是散列碼是散列碼)n算法：算法：l使用索引使用索引(或散列或散列)得到得到Sno為為201215121 元組的指針元組的指針l通過元組指針在通過元組指針在Student表中檢索到該學(xué)生表中檢索到該學(xué)生An Introduction to Database System選擇操作的實(shí)現(xiàn)（續(xù)）選擇操作的實(shí)現(xiàn)（續(xù)

13、）v例例9.1-C3 SELECT * FROM Student WHERE Sage20n假設(shè)假設(shè)Sage 上有上有B+樹索引樹索引n算法：算法：l使用使用B+樹索引找到樹索引找到Sage=20的索引項(xiàng)，以此為入口點(diǎn)在的索引項(xiàng)，以此為入口點(diǎn)在B+樹的順序集上得到樹的順序集上得到Sage20的所有元組指針的所有元組指針l通過這些元組指針到通過這些元組指針到student表中檢索到所有年齡大于表中檢索到所有年齡大于20的學(xué)生。的學(xué)生。 An Introduction to Database System選擇操作的實(shí)現(xiàn)（續(xù)）選擇操作的實(shí)現(xiàn)（續(xù)）v例例9.1-C4 SELECT * FROM Stu

14、dent WHERE Sdept=CS AND Sage20;n假設(shè)假設(shè)Sdept和和Sage上都有索引上都有索引n算法一：分別用算法一：分別用Index Scan找到找到SdeptCS的一組元組的一組元組指針和指針和Sage20的另一組元組指針的另一組元組指針l求這兩組指針的交集求這兩組指針的交集l到到Student表中檢索表中檢索l得到計(jì)算機(jī)系年齡大于得到計(jì)算機(jī)系年齡大于20的學(xué)生的學(xué)生An Introduction to Database System選擇操作的實(shí)現(xiàn)（續(xù)）選擇操作的實(shí)現(xiàn)（續(xù)）n算法二：找到算法二：找到Sdept=CS的一組元組指針，的一組元組指針，l通過這些元組指針到通過

15、這些元組指針到Student表中檢索表中檢索l并對得到的元組檢查另一些選擇條件并對得到的元組檢查另一些選擇條件(如如Sage20)是否滿足是否滿足l把滿足條件的元組作為結(jié)果輸出。把滿足條件的元組作為結(jié)果輸出。 An Introduction to Database System2.連接操作的實(shí)現(xiàn)連接操作的實(shí)現(xiàn) v連接操作是查詢處理中最耗時(shí)的操作之一連接操作是查詢處理中最耗時(shí)的操作之一 v本節(jié)只討論等值連接本節(jié)只討論等值連接(或自然連接或自然連接)最常用的實(shí)現(xiàn)最常用的實(shí)現(xiàn)算法算法 v例例9.2 SELECT * FROM Student, SC WHERE Student.Sno=SC.Sno;

16、 An Introduction to Database System連接操作的實(shí)現(xiàn)（續(xù)）連接操作的實(shí)現(xiàn)（續(xù)）（1）嵌套循環(huán)算法）嵌套循環(huán)算法(nested loop join) （2）排序）排序-合并算法合并算法(sort-merge join 或或merge join)（3）索引連接）索引連接(index join)算法算法 （4）Hash Join算法算法 An Introduction to Database System連接操作的實(shí)現(xiàn)（續(xù)）連接操作的實(shí)現(xiàn)（續(xù)）（1）嵌套循環(huán)算法）嵌套循環(huán)算法(nested loop join)n對外層循環(huán)對外層循環(huán)(Student表表)的每一個(gè)元組的

17、每一個(gè)元組(s)，檢索內(nèi)層循，檢索內(nèi)層循環(huán)環(huán)(SC表表)中的每一個(gè)元組中的每一個(gè)元組(sc)n檢查這兩個(gè)元組在連接屬性檢查這兩個(gè)元組在連接屬性(Sno)上是否相等上是否相等n如果滿足連接條件，則串接后作為結(jié)果輸出，直到外如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止。層循環(huán)表中的元組處理完為止。v參見愛課程網(wǎng)參見愛課程網(wǎng)9.1節(jié)動(dòng)畫節(jié)動(dòng)畫連接操作的實(shí)現(xiàn)連接操作的實(shí)現(xiàn)(1)-嵌嵌套循環(huán)套循環(huán)An Introduction to Database System連接操作的實(shí)現(xiàn)（續(xù)）連接操作的實(shí)現(xiàn)（續(xù)）（2）排序）排序-合并算法合并算法(sort-merge join 或或m

18、erge join) n如果連接的表沒有排好序，先對如果連接的表沒有排好序，先對Student表和表和SC表按表按連接屬性連接屬性Sno排序排序 n取取Student表中第一個(gè)表中第一個(gè)Sno，依次掃描，依次掃描SC表中具有相表中具有相同同Sno的元組的元組 n當(dāng)掃描到當(dāng)掃描到Sno不相同的第一個(gè)不相同的第一個(gè)SC元組時(shí)，返回元組時(shí)，返回Student表掃描它的下一個(gè)元組，再掃描表掃描它的下一個(gè)元組，再掃描SC表中具有表中具有相同相同Sno的元組，把它們連接起來的元組，把它們連接起來 n重復(fù)上述步驟直到重復(fù)上述步驟直到Student 表掃描完表掃描完An Introduction to Dat

19、abase System連接操作的實(shí)現(xiàn)（續(xù)）連接操作的實(shí)現(xiàn)（續(xù)）201215121 201215122 201215123 201215125 .201215121 1 92201215121 2 85201215121 3 88201215122 2 90201215122 3 80.圖圖9.2 排序排序-合并連接方法示意圖合并連接方法示意圖An Introduction to Database System連接操作的實(shí)現(xiàn)（續(xù)）連接操作的實(shí)現(xiàn)（續(xù)）vStudent表和表和SC表都只要掃描一遍表都只要掃描一遍v如果兩個(gè)表原來無序，執(zhí)行時(shí)間要加上對兩個(gè)表如果兩個(gè)表原來無序，執(zhí)行時(shí)間要加上對兩個(gè)表

20、的排序時(shí)間的排序時(shí)間v對于大表，先排序后使用排序?qū)τ诖蟊恚扰判蚝笫褂门判?合并連接算法執(zhí)行合并連接算法執(zhí)行連接，總的時(shí)間一般仍會(huì)減少連接，總的時(shí)間一般仍會(huì)減少 v參見愛課程網(wǎng)參見愛課程網(wǎng)9.1節(jié)動(dòng)畫節(jié)動(dòng)畫連接操作的實(shí)現(xiàn)（連接操作的實(shí)現(xiàn)（2）-排序合并排序合并 An Introduction to Database System連接操作的實(shí)現(xiàn)（續(xù)）連接操作的實(shí)現(xiàn)（續(xù)）（3）索引連接）索引連接(index join)算法算法n步驟：步驟： 在在SC表上已經(jīng)建立屬性表上已經(jīng)建立屬性Sno的索引。的索引。 對對Student中每一個(gè)元組，由中每一個(gè)元組，由Sno值通過值通過SC的索引查的索引查找相應(yīng)

21、的找相應(yīng)的SC元組。元組。 把這些把這些SC元組和元組和Student元組連接起來元組連接起來 循環(huán)執(zhí)行，直到循環(huán)執(zhí)行，直到Student表中的元組處理完為止表中的元組處理完為止 v參見愛課程網(wǎng)參見愛課程網(wǎng)9.1節(jié)動(dòng)畫節(jié)動(dòng)畫連接操作的實(shí)現(xiàn)連接操作的實(shí)現(xiàn)(4)- 索引連接索引連接 An Introduction to Database System連接操作的實(shí)現(xiàn)（續(xù)）連接操作的實(shí)現(xiàn)（續(xù)）（4）Hash Join算法算法 n 把連接屬性作為把連接屬性作為hash碼，用同一個(gè)碼，用同一個(gè)hash函數(shù)把函數(shù)把Student表和表和SC表表中的元組散列到中的元組散列到hash表中。表中。n 劃分階段劃分

22、階段(building phase, 也稱為也稱為partitioning phase)l對包含較少元組的表對包含較少元組的表(如如Student表表)進(jìn)行一遍處理進(jìn)行一遍處理l把它的元組按把它的元組按hash函數(shù)分散到函數(shù)分散到hash表的桶中表的桶中n 試探階段試探階段(probing phase,也稱為連接階段也稱為連接階段join phase) l對另一個(gè)表對另一個(gè)表(SC表表)進(jìn)行一遍處理進(jìn)行一遍處理l把把SC表的元組也按同一個(gè)表的元組也按同一個(gè)hash函數(shù)（函數(shù)（hash碼是連接屬性）進(jìn)碼是連接屬性）進(jìn)行散列行散列l(wèi)把把SC元組與桶中來自元組與桶中來自Student表并與之相匹配的

23、元組連接起來表并與之相匹配的元組連接起來An Introduction to Database System連接操作的實(shí)現(xiàn)（續(xù)）連接操作的實(shí)現(xiàn)（續(xù)）v上面上面hash join算法前提：假設(shè)兩個(gè)表中較小的表算法前提：假設(shè)兩個(gè)表中較小的表在第一階段后可以完全放入內(nèi)存的在第一階段后可以完全放入內(nèi)存的hash桶中桶中 v參見愛課程網(wǎng)參見愛課程網(wǎng)9.1節(jié)動(dòng)畫節(jié)動(dòng)畫連接操作的實(shí)現(xiàn)連接操作的實(shí)現(xiàn)(3)-散散列連接列連接 An Introduction to Database System第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.

24、2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化代數(shù)優(yōu)化 9.4 物理優(yōu)化物理優(yōu)化 *9.5 查詢計(jì)劃的執(zhí)行查詢計(jì)劃的執(zhí)行9.6 小小 結(jié)結(jié) An Introduction to Database System9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化v查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位 v關(guān)系查詢優(yōu)化是影響關(guān)系數(shù)據(jù)庫管理系統(tǒng)性能的關(guān)關(guān)系查詢優(yōu)化是影響關(guān)系數(shù)據(jù)庫管理系統(tǒng)性能的關(guān)鍵因素鍵因素 v由于關(guān)系表達(dá)式的語義級別很高，使關(guān)系系統(tǒng)可以由于關(guān)系表達(dá)式的語義級別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義

25、，提供了執(zhí)行查詢優(yōu)從關(guān)系表達(dá)式中分析查詢語義，提供了執(zhí)行查詢優(yōu)化的可能性化的可能性 An Introduction to Database System9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述查詢優(yōu)化概述9.2.2一個(gè)實(shí)例一個(gè)實(shí)例An Introduction to Database System9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述v關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢優(yōu)化n是關(guān)系數(shù)據(jù)庫管理系統(tǒng)實(shí)現(xiàn)的關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)是關(guān)系數(shù)據(jù)庫管理系統(tǒng)實(shí)現(xiàn)的關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)的優(yōu)點(diǎn)所在的優(yōu)點(diǎn)所在n減輕了用戶選擇存取路徑的負(fù)擔(dān)減輕了用戶選擇存取路徑的負(fù)擔(dān) An Intro

26、duction to Database System查詢優(yōu)化概述（續(xù)）查詢優(yōu)化概述（續(xù)）v非關(guān)系系統(tǒng)非關(guān)系系統(tǒng)n用戶使用過程化的語言表達(dá)查詢要求，執(zhí)行何種記錄用戶使用過程化的語言表達(dá)查詢要求，執(zhí)行何種記錄級的操作，以及操作的序列是由用戶來決定的級的操作，以及操作的序列是由用戶來決定的 n用戶必須了解存取路徑，系統(tǒng)要提供用戶選擇存取路用戶必須了解存取路徑，系統(tǒng)要提供用戶選擇存取路徑的手段，查詢效率由用戶的存取策略決定徑的手段，查詢效率由用戶的存取策略決定n如果用戶做了不當(dāng)?shù)倪x擇，系統(tǒng)是無法對此加以改進(jìn)如果用戶做了不當(dāng)?shù)倪x擇，系統(tǒng)是無法對此加以改進(jìn)的的An Introduction to Data

27、base System查詢優(yōu)化概述查詢優(yōu)化概述v查詢優(yōu)化的優(yōu)點(diǎn)查詢優(yōu)化的優(yōu)點(diǎn)n用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率n系統(tǒng)可以比用戶程序的系統(tǒng)可以比用戶程序的“優(yōu)化優(yōu)化”做得更好做得更好 （1） 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息。戶程序則難以獲得這些信息。（2）如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)）如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序

28、，而重寫程序在實(shí)際應(yīng)用中往往是不太可中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。能的。An Introduction to Database System查詢優(yōu)化概述（續(xù)）查詢優(yōu)化概述（續(xù)）（3）優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序員一）優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序員一般只能考慮有限的幾種可能性。般只能考慮有限的幾種可能性。（4）優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技）優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)。于使得所有人都擁有

29、這些優(yōu)化技術(shù)。An Introduction to Database System查詢優(yōu)化概述（續(xù)）查詢優(yōu)化概述（續(xù)）v關(guān)系數(shù)據(jù)庫管理系統(tǒng)通過某種代價(jià)模型計(jì)算出各關(guān)系數(shù)據(jù)庫管理系統(tǒng)通過某種代價(jià)模型計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案的執(zhí)行方案n集中式數(shù)據(jù)庫集中式數(shù)據(jù)庫l執(zhí)行開銷主要包括執(zhí)行開銷主要包括磁盤存取塊數(shù)磁盤存取塊數(shù)(I/O代價(jià)代價(jià))處理機(jī)時(shí)間處理機(jī)時(shí)間(CPU代價(jià)代價(jià))查詢的內(nèi)存開銷查詢的內(nèi)存開銷 lI/O代價(jià)是最主要的代價(jià)是最主要的 n分布式數(shù)據(jù)庫分布式數(shù)據(jù)庫l總代價(jià)總代價(jià)=I/O代價(jià)代價(jià)+CPU代價(jià)代價(jià)+內(nèi)存代價(jià)通

30、信代價(jià)內(nèi)存代價(jià)通信代價(jià) An Introduction to Database System查詢優(yōu)化概述（續(xù)）查詢優(yōu)化概述（續(xù)）v查詢優(yōu)化的總目標(biāo)查詢優(yōu)化的總目標(biāo)n選擇有效的策略選擇有效的策略n求得給定關(guān)系表達(dá)式的值求得給定關(guān)系表達(dá)式的值n使得查詢代價(jià)最小使得查詢代價(jià)最小(實(shí)際上是較小實(shí)際上是較小) An Introduction to Database System9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述查詢優(yōu)化概述9.2.2一個(gè)實(shí)例一個(gè)實(shí)例An Introduction to Database System9.2.2 一個(gè)實(shí)例一個(gè)實(shí)例v一個(gè)關(guān)系查詢可以

31、對應(yīng)不同的執(zhí)行方案，其效率一個(gè)關(guān)系查詢可以對應(yīng)不同的執(zhí)行方案，其效率可能相差非常大。可能相差非常大。v例例9.3 求選修了求選修了2號課程的學(xué)生姓名。號課程的學(xué)生姓名。 用用SQL表達(dá)：表達(dá)： SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.Sno AND SC.Cno=2 n假定學(xué)生假定學(xué)生-課程數(shù)據(jù)庫中有課程數(shù)據(jù)庫中有1000個(gè)學(xué)生記錄，個(gè)學(xué)生記錄，10000個(gè)個(gè)選課記錄選課記錄n選修選修2號課程的選課記錄為號課程的選課記錄為50個(gè)個(gè) An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例

32、（續(xù)）v可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這一查詢可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這一查詢nQ1=Sname(Student.Sno=SC.SnoSC.Cno=2 (StudentSC)nQ2=Sname(SC.Cno=2 (Student SC)nQ3=Sname(Student SC.Cno=2(SC) An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）1.第一種情況第一種情況nQ1=Sname(Student.Sno=SC.SnoSC.Cno=2 (StudentSC)An Introduction to Database System

33、一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）（1） 計(jì)算廣義笛卡爾積計(jì)算廣義笛卡爾積 v算法：算法：n在內(nèi)存中盡可能多地裝入某個(gè)表在內(nèi)存中盡可能多地裝入某個(gè)表(如如Student表表)的若干的若干塊，留出一塊存放另一個(gè)表塊，留出一塊存放另一個(gè)表(如如SC表表)的元組。的元組。n把把SC中的每個(gè)元組和中的每個(gè)元組和Student中每個(gè)元組連接，連接中每個(gè)元組連接，連接后的元組裝滿一塊后就寫到中間文件上后的元組裝滿一塊后就寫到中間文件上n從從SC中讀入一塊和內(nèi)存中的中讀入一塊和內(nèi)存中的Student元組連接，直到元組連接，直到SC表處理完。表處理完。n再讀入若干塊再讀入若干塊Student元組，讀入一塊元組，讀入

34、一塊SC元組元組n重復(fù)上述處理過程，直到把重復(fù)上述處理過程，直到把Student表處理完表處理完 An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）v設(shè)一個(gè)塊能裝設(shè)一個(gè)塊能裝10個(gè)個(gè)Student元組或元組或100個(gè)個(gè)SC元組元組，在內(nèi)存中存放，在內(nèi)存中存放5塊塊Student元組和元組和1塊塊SC元組，元組，則讀取總塊數(shù)為則讀取總塊數(shù)為 =100+20100=2100塊塊n讀讀Student表表100塊，讀塊，讀SC表表20遍，每遍遍，每遍100塊，則總塊，則總計(jì)要讀取計(jì)要讀取2100數(shù)據(jù)塊。數(shù)據(jù)塊。n連接后的元組數(shù)為連接后的元組數(shù)為103104

35、=107。設(shè)每塊能裝。設(shè)每塊能裝10個(gè)元個(gè)元組，則寫出組，則寫出106 塊。塊。101000510100010010000An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）（2）作選擇操作）作選擇操作 n依次讀入連接后的元組，按照選擇條件選取滿足要求依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄的記錄n假定內(nèi)存處理時(shí)間忽略。讀取中間文件花費(fèi)的時(shí)間假定內(nèi)存處理時(shí)間忽略。讀取中間文件花費(fèi)的時(shí)間(同同寫中間文件一樣寫中間文件一樣)需讀入需讀入106塊。塊。 n若滿足條件的元組假設(shè)僅若滿足條件的元組假設(shè)僅50個(gè)，均可放在內(nèi)存。個(gè)，均可放在內(nèi)存。 An

36、 Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）（3）作投影操作）作投影操作 n把第（把第（2）步的結(jié)果在）步的結(jié)果在Sname上作投影輸出，得到最終上作投影輸出，得到最終結(jié)果結(jié)果 v第一種情況下執(zhí)行查詢的總讀寫數(shù)據(jù)塊第一種情況下執(zhí)行查詢的總讀寫數(shù)據(jù)塊=2100+106 +106An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）2.第二種情況第二種情況 Q2=Sname(Sc.Cno=2 (Student SC)（1）計(jì)算自然連接）計(jì)算自然連接 l執(zhí)行自然連接，讀取執(zhí)行自然連接，讀取Student和和SC

37、表的策略不變，總的讀表的策略不變，總的讀取塊數(shù)仍為取塊數(shù)仍為2100塊塊l自然連接的結(jié)果比第一種情況大大減少，為自然連接的結(jié)果比第一種情況大大減少，為104個(gè)元組個(gè)元組l寫出數(shù)據(jù)塊寫出數(shù)據(jù)塊= 103 塊塊 An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）2.第二種情況（續(xù)）第二種情況（續(xù)）（2）讀取中間文件塊，執(zhí)行選擇運(yùn)算，讀取的數(shù)據(jù)塊）讀取中間文件塊，執(zhí)行選擇運(yùn)算，讀取的數(shù)據(jù)塊= 103 塊塊（3）把第）把第2步結(jié)果投影輸出。步結(jié)果投影輸出。n第二種情況下執(zhí)行查詢的總讀寫數(shù)據(jù)塊第二種情況下執(zhí)行查詢的總讀寫數(shù)據(jù)塊=2100+ 103 +103n

38、其執(zhí)行代價(jià)大約是第一種情況的其執(zhí)行代價(jià)大約是第一種情況的488分之一分之一 An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）3.第三種情況第三種情況Q3=Sname(Student SC.Cno=2(SC)（1）先對）先對SC表作選擇運(yùn)算，只需讀一遍表作選擇運(yùn)算，只需讀一遍SC表，存取表，存取 100塊，因?yàn)闈M足條件的元組僅塊，因?yàn)闈M足條件的元組僅50個(gè)，不必使用中個(gè)，不必使用中 間文件。間文件。（2）讀?。┳x取Student表，把讀入的表，把讀入的Student元組和內(nèi)存中元組和內(nèi)存中 的的SC元組作連接。也只需讀一遍元組作連接。也只需讀一遍S

39、tudent表共表共100 塊。塊。（3）把連接結(jié)果投影輸出）把連接結(jié)果投影輸出 An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）3.第三種情況（續(xù)）第三種情況（續(xù)）n第三種情況總的讀寫數(shù)據(jù)塊第三種情況總的讀寫數(shù)據(jù)塊=100+100n其執(zhí)行代價(jià)大約是第一種情況的萬分之一，是第二種其執(zhí)行代價(jià)大約是第一種情況的萬分之一，是第二種情況的情況的20分之一分之一An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）v假如假如SC表的表的Cno字段上有索引字段上有索引n第一步就不必讀取所有的第一步就不必讀取所有的SC

40、元組而只需讀取元組而只需讀取Cno=2的那些元組的那些元組(50個(gè)個(gè))n存取的索引塊和存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共中滿足條件的數(shù)據(jù)塊大約總共34塊塊v若若Student表在表在Sno上也有索引上也有索引n不必讀取所有的不必讀取所有的Student元組元組n因?yàn)闈M足條件的因?yàn)闈M足條件的SC記錄僅記錄僅50個(gè)，涉及最多個(gè)，涉及最多50個(gè)個(gè)Student記錄記錄n讀取讀取Student表的塊數(shù)也可大大減少表的塊數(shù)也可大大減少 An Introduction to Database System一個(gè)實(shí)例（續(xù)）一個(gè)實(shí)例（續(xù)）v把代數(shù)表達(dá)式把代數(shù)表達(dá)式Q1變換為變換為Q2、 Q3Q1=Sn

41、ame(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)Q2=Sname(Sc.Cno=2 (Student SC)Q3=Sname(Student SC.Cno=2(SC)n 有選擇和連接操作時(shí)，先做選擇操作，這樣參加連接的元組有選擇和連接操作時(shí)，先做選擇操作，這樣參加連接的元組就可以大大減少，這是就可以大大減少，這是代數(shù)優(yōu)化代數(shù)優(yōu)化 An Introduction to Database System實(shí)例實(shí)例: 小結(jié)小結(jié)v在在Q3中中nSC表的選擇操作算法有全表掃描或索引掃描，經(jīng)過初步表的選擇操作算法有全表掃描或索引掃描，經(jīng)過初步估算，索引掃描方法較優(yōu)。估算，索

42、引掃描方法較優(yōu)。n對于對于Student和和SC表的連接，利用表的連接，利用Student表上的索引，表上的索引，采用索引連接代價(jià)也較小，這就是采用索引連接代價(jià)也較小，這就是物理優(yōu)化物理優(yōu)化。An Introduction to Database System第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化代數(shù)優(yōu)化 9.4 物理優(yōu)化物理優(yōu)化 *9.5 查詢計(jì)劃的執(zhí)行查詢計(jì)劃的執(zhí)行9.6 小小 結(jié)結(jié) An Introduction to Database

43、System9.3 代代 數(shù)數(shù) 優(yōu)優(yōu) 化化9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 9.3.2 查詢樹的啟發(fā)式優(yōu)化查詢樹的啟發(fā)式優(yōu)化 An Introduction to Database System9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 v代數(shù)優(yōu)化策略：通過對關(guān)系代數(shù)表達(dá)式的等價(jià)變代數(shù)優(yōu)化策略：通過對關(guān)系代數(shù)表達(dá)式的等價(jià)變換來提高查詢效率換來提高查詢效率 v關(guān)系代數(shù)表達(dá)式的等價(jià)：指用相同的關(guān)系代替兩關(guān)系代數(shù)表達(dá)式的等價(jià)：指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的v兩個(gè)關(guān)系表達(dá)式兩個(gè)關(guān)

44、系表達(dá)式E1和和E2是等價(jià)的，可記為是等價(jià)的，可記為E1E2 An Introduction to Database System*關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）v常用的等價(jià)變換規(guī)則：常用的等價(jià)變換規(guī)則：1.連接、笛卡爾積交換律連接、笛卡爾積交換律 設(shè)設(shè)E1和和E2是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有是連接運(yùn)算的條件，則有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E12.連接、笛卡爾積的結(jié)合律連接、笛卡爾積的結(jié)合律 設(shè)設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和和F2是連接運(yùn)算的條件是連接運(yùn)算的條件

45、(E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) F1FF2F2F2F An Introduction to Database System*關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）3.投影的串接定律投影的串接定律 ( (E) (E)n E是關(guān)系代數(shù)表達(dá)式是關(guān)系代數(shù)表達(dá)式n Ai(i=1，2，n)，Bj(j=1，2，m)是屬性名是屬性名n A1，A2，An構(gòu)成構(gòu)成B1，B2，Bm的子集的子集4.選擇的串接定律選擇的串接定律 ( (E ) (E)n E是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)1、F2

46、是選擇條件是選擇條件n 選擇的串接律說明選擇條件可以合并選擇的串接律說明選擇條件可以合并,這樣一次就可檢查全這樣一次就可檢查全部條件部條件nAAA,21mBBB,21nAAA,211F2F21FF An Introduction to Database System*關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）5.選擇與投影操作的交換律選擇與投影操作的交換律 F( (E) (F(E)n 選擇條件選擇條件F只涉及屬性只涉及屬性A1，An。n 若若F中有不屬于中有不屬于A1，An的屬性的屬性B1，Bm有更一般規(guī)有更一般規(guī)則：則： (F(E ) (F ( (E)nAAA,21nA

47、AA,21nAAA,21nAAA,21mnBBBAAA,2121An Introduction to Database System*關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）6. 選擇與笛卡爾積的交換律選擇與笛卡爾積的交換律n如果如果F中涉及的屬性都是中涉及的屬性都是E1中的屬性，則中的屬性，則 F(E1E2)F(E1)E2n如果如果F=F1F2，并且，并且F1只涉及只涉及E1中的屬性，中的屬性，F(xiàn)2只涉及只涉及E2中的屬性，則由上面的等價(jià)變換規(guī)則中的屬性，則由上面的等價(jià)變換規(guī)則1，4，6可推出：可推出： F(E1E2) (E1) (E2)n若若F1只涉及只涉及E1中的

48、屬性，中的屬性，F(xiàn)2涉及涉及E1和和E2兩者的屬性，則兩者的屬性，則仍有仍有 F(E1E2) ( (E1)E2) 它使部分選擇在笛卡爾積前先做。它使部分選擇在笛卡爾積前先做。 1F2F2F1FAn Introduction to Database System*關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）7. 選擇與并的分配律選擇與并的分配律 設(shè)設(shè)E=E1E2，E1，E2有相同的屬性名，則有相同的屬性名，則 F(E1E2)F(E1)F(E2)8. 選擇與差運(yùn)算的分配律選擇與差運(yùn)算的分配律 若若E1與與E2有相同的屬性名，則有相同的屬性名，則 F(E1-E2)F(E1)-F(

49、E2)9. 選擇對自然連接的分配律選擇對自然連接的分配律 F(E1 E2)F(E1) F(E2) F只涉及只涉及E1與與E2的公共屬性的公共屬性 An Introduction to Database System*關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）10. 投影與笛卡爾積的分配律投影與笛卡爾積的分配律 設(shè)設(shè)E1和和E2是兩個(gè)關(guān)系表達(dá)式，是兩個(gè)關(guān)系表達(dá)式，A1，An是是E1的屬性，的屬性， B1，Bm是是E2的屬性，則的屬性，則 (E1E2) (E1) (E2)11. 投影與并的分配律投影與并的分配律 設(shè)設(shè)E1和和E2有相同的屬性名，則有相同的屬性名，則 (E1E2

50、) (E1) (E2)mnBBBAAA,2121nAAA,21mBBB,21nAAA,21nAAA,21nAAA,21An Introduction to Database System9.3 代代 數(shù)數(shù) 優(yōu)優(yōu) 化化9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 9.3.2 查詢樹的啟發(fā)式優(yōu)化查詢樹的啟發(fā)式優(yōu)化 An Introduction to Database System9.3.2 查詢樹的啟發(fā)式優(yōu)化查詢樹的啟發(fā)式優(yōu)化 v典型的啟發(fā)式規(guī)則典型的啟發(fā)式規(guī)則（1）選擇運(yùn)算應(yīng)盡可能先做）選擇運(yùn)算應(yīng)盡可能先做 在優(yōu)化策略中這是最重要、最基本的一條。在優(yōu)化策略中這是最重要、最基

51、本的一條。（2）把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行）把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行如有若干投影和選擇運(yùn)算，并且它們都對同一個(gè)關(guān)系如有若干投影和選擇運(yùn)算，并且它們都對同一個(gè)關(guān)系操作，則可以在掃描此關(guān)系的同時(shí)完成所有的這些運(yùn)操作，則可以在掃描此關(guān)系的同時(shí)完成所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系。算以避免重復(fù)掃描關(guān)系。An Introduction to Database System查詢樹的啟發(fā)式優(yōu)化（續(xù)）查詢樹的啟發(fā)式優(yōu)化（續(xù)）（3） 把投影同其前或其后的雙目運(yùn)算結(jié)合起來，沒有把投影同其前或其后的雙目運(yùn)算結(jié)合起來，沒有必要為了去掉某些字段而掃描一遍關(guān)系。必要為了去掉某些字段而掃描一遍關(guān)系。（4） 把某些選擇

52、同在它前面要執(zhí)行的笛卡爾積結(jié)合起把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個(gè)連接運(yùn)算，連接特別是等值連接運(yùn)算要比來成為一個(gè)連接運(yùn)算，連接特別是等值連接運(yùn)算要比同樣關(guān)系上的笛卡爾積省很多時(shí)間。同樣關(guān)系上的笛卡爾積省很多時(shí)間。 An Introduction to Database System查詢樹的啟發(fā)式優(yōu)化（續(xù)）查詢樹的啟發(fā)式優(yōu)化（續(xù)）（5） 找出公共子表達(dá)式找出公共子表達(dá)式l如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系l并且從外存中讀入這個(gè)關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少并且從外存中讀入這個(gè)關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少得多得多l(xiāng)則先計(jì)算一

53、次公共子表達(dá)式并把結(jié)果寫入中間文件是合則先計(jì)算一次公共子表達(dá)式并把結(jié)果寫入中間文件是合算的。算的。l當(dāng)查詢的是視圖時(shí)，定義視圖的表達(dá)式就是公共子表達(dá)當(dāng)查詢的是視圖時(shí)，定義視圖的表達(dá)式就是公共子表達(dá)式的情況式的情況An Introduction to Database System*查詢樹的啟發(fā)式優(yōu)化（續(xù)）查詢樹的啟發(fā)式優(yōu)化（續(xù)）v遵循這些啟發(fā)式規(guī)則，應(yīng)用遵循這些啟發(fā)式規(guī)則，應(yīng)用9.3.1的等價(jià)變換公式的等價(jià)變換公式來優(yōu)化關(guān)系表達(dá)式的算法。來優(yōu)化關(guān)系表達(dá)式的算法。算法：關(guān)系表達(dá)式的優(yōu)化算法：關(guān)系表達(dá)式的優(yōu)化輸入輸入：一個(gè)關(guān)系表達(dá)式的查詢樹：一個(gè)關(guān)系表達(dá)式的查詢樹輸出輸出：優(yōu)化的查詢樹：優(yōu)化的查詢

54、樹方法：方法：（1）利用等價(jià)變換規(guī)則）利用等價(jià)變換規(guī)則4把形如把形如F1F2Fn(E)變換為變換為 F1(F2(Fn(E)。（2）對每一個(gè)選擇，利用等價(jià)變換規(guī)則）對每一個(gè)選擇，利用等價(jià)變換規(guī)則49盡可能把它盡可能把它 移到樹的葉端。移到樹的葉端。規(guī)則規(guī)則4： 合并或分解選擇運(yùn)算合并或分解選擇運(yùn)算規(guī)則規(guī)則5-9： 選擇運(yùn)算與其他運(yùn)算交換選擇運(yùn)算與其他運(yùn)算交換規(guī)則規(guī)則4: 選擇的串接定律選擇的串接定律 ( (E) (E)1F2F21FF An Introduction to Database System*查詢樹的啟發(fā)式優(yōu)化（續(xù)）查詢樹的啟發(fā)式優(yōu)化（續(xù)）（3）對每一個(gè)投影利用等價(jià)變換規(guī)則）對每一個(gè)

55、投影利用等價(jià)變換規(guī)則3，5，10，11中的中的一般形式盡可能把它移向樹的葉端。一般形式盡可能把它移向樹的葉端。n注意：注意： l等價(jià)變換規(guī)則等價(jià)變換規(guī)則3使一些投影消失或使一些投影出現(xiàn)使一些投影消失或使一些投影出現(xiàn)l規(guī)則規(guī)則5把一個(gè)投影分裂為兩個(gè)，其中一個(gè)有可能被移向樹把一個(gè)投影分裂為兩個(gè)，其中一個(gè)有可能被移向樹的葉端的葉端 （4）利用等價(jià)變換規(guī)則）利用等價(jià)變換規(guī)則35，把選擇和投影的串接合并，把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影，使多個(gè)成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影，使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成選擇或投影能同時(shí)執(zhí)行，或在一次掃描中

56、全部完成規(guī)則規(guī)則3： 合并或分解投影運(yùn)算合并或分解投影運(yùn)算規(guī)則規(guī)則5,10,11：投影運(yùn)算與其他運(yùn)算交換：投影運(yùn)算與其他運(yùn)算交換規(guī)則規(guī)則3：合并或分解投影運(yùn)算：合并或分解投影運(yùn)算規(guī)則規(guī)則4：合并或分解選擇運(yùn)算：合并或分解選擇運(yùn)算規(guī)則規(guī)則5：投影運(yùn)算與選擇運(yùn)算交換：投影運(yùn)算與選擇運(yùn)算交換An Introduction to Database System查詢樹的啟發(fā)式優(yōu)化（續(xù)）查詢樹的啟發(fā)式優(yōu)化（續(xù)） （5）把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。）把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。n每一雙目運(yùn)算每一雙目運(yùn)算(， ，-)和它所有的直接祖先為一和它所有的直接祖先為一組組(這些直接祖先是這些直接祖先是(，運(yùn)算

57、運(yùn)算)。n如果其后代直到葉子全是單目運(yùn)算，則也將它們并入如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組該組n但當(dāng)雙目運(yùn)算是笛卡爾積但當(dāng)雙目運(yùn)算是笛卡爾積()，而且后面不是與它組成，而且后面不是與它組成等值連接的選擇時(shí)，則不能把選擇與這個(gè)雙目運(yùn)算組等值連接的選擇時(shí)，則不能把選擇與這個(gè)雙目運(yùn)算組成同一組成同一組 An Introduction to Database System查詢樹的啟發(fā)式優(yōu)化（續(xù)）查詢樹的啟發(fā)式優(yōu)化（續(xù)）v例例9.4下面給出下面給出例例9.3中中 SQL語句的代數(shù)優(yōu)化示例語句的代數(shù)優(yōu)化示例 （1）把）把SQL語句轉(zhuǎn)換成查詢樹，如下圖所示語句轉(zhuǎn)換成查詢樹，如下圖所示圖圖9.

58、3 查詢樹圖查詢樹圖An Introduction to Database System查詢樹的啟發(fā)式優(yōu)化（續(xù)）查詢樹的啟發(fā)式優(yōu)化（續(xù)）為了使用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān)為了使用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān)系代數(shù)語法樹，則上面的查詢樹如圖系代數(shù)語法樹，則上面的查詢樹如圖9.4所示。所示。 圖圖9.4 關(guān)系代數(shù)語法樹圖關(guān)系代數(shù)語法樹圖 An Introduction to Database System查詢樹的啟發(fā)式優(yōu)化（續(xù)）查詢樹的啟發(fā)式優(yōu)化（續(xù)）（2 ）對查詢樹進(jìn)行優(yōu)化）對查詢樹進(jìn)行優(yōu)化n利用規(guī)則利用規(guī)則4、6把選擇把選擇SC.Cno=2移到葉端，圖移到葉端，圖9.

59、4查詢樹查詢樹便轉(zhuǎn)換成下圖優(yōu)化的查詢樹。這就是便轉(zhuǎn)換成下圖優(yōu)化的查詢樹。這就是9.2.2節(jié)中節(jié)中Q3的查的查詢樹表示。詢樹表示。v參見愛課程網(wǎng)參見愛課程網(wǎng)9.3節(jié)動(dòng)畫節(jié)動(dòng)畫查詢樹的啟發(fā)式優(yōu)化查詢樹的啟發(fā)式優(yōu)化 An Introduction to Database System第九章第九章 關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化代數(shù)優(yōu)化 9.4 物理優(yōu)化物理優(yōu)化 *9.5 查詢計(jì)劃的執(zhí)行查詢計(jì)劃的執(zhí)行9.6 小小 結(jié)結(jié) An Introduction to

60、Database System9.4 物理優(yōu)化物理優(yōu)化v代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑涉及底層的存取路徑v對于一個(gè)查詢語句有許多存取方案，它們的執(zhí)行對于一個(gè)查詢語句有許多存取方案，它們的執(zhí)行效率不同，效率不同， 僅僅進(jìn)行代數(shù)優(yōu)化是不夠的僅僅進(jìn)行代數(shù)優(yōu)化是不夠的 v物理優(yōu)化就是要物理優(yōu)化就是要選擇高效合理的操作算法或存取選擇高效合理的操作算法或存取路徑路徑，求得優(yōu)化的查詢計(jì)劃，求得優(yōu)化的查詢計(jì)劃 An Introduction to Database System物理優(yōu)化（續(xù)）物理優(yōu)化（續(xù)）v物理優(yōu)化方法物理優(yōu)化方法n基于規(guī)