關(guān)系查詢處理和查詢優(yōu)化ppt課件

1、中國人民大學(xué)信息學(xué)院中國人民大學(xué)信息學(xué)院 數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論 An Introduction to An Introduction to Database SystemDatabase System 第九章第九章 關(guān)系查詢處置和查詢優(yōu)關(guān)系查詢處置和查詢優(yōu) 化化 第九章第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(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 小小 結(jié)結(jié) 關(guān)系系統(tǒng)及其查詢優(yōu)化續(xù)關(guān)系系統(tǒng)及其查詢優(yōu)化續(xù) v本章目的：本章目的： vRDBMS的

2、查詢處置步驟的查詢處置步驟 v查詢優(yōu)化的概念查詢優(yōu)化的概念 v根本方法和技術(shù)根本方法和技術(shù) v查詢優(yōu)化分類查詢優(yōu)化分類 ： v代數(shù)優(yōu)化代數(shù)優(yōu)化 v物理優(yōu)化物理優(yōu)化 9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處置關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處置 v9.1.1 查詢處置步驟查詢處置步驟 v9.1.2 實(shí)現(xiàn)查詢操作的算法例如實(shí)現(xiàn)查詢操作的算法例如 9.1.1 查詢處置步驟查詢處置步驟 vRDBMS查詢處置階段查詢處置階段 ： v1. 查詢分析查詢分析 v2. 查詢檢查查詢檢查 v3. 查詢優(yōu)化查詢優(yōu)化 v4. 查詢執(zhí)行查詢執(zhí)行 查詢處置步驟續(xù)查詢處置步驟續(xù) 查詢處置步驟 1. 查詢分析查詢分析 v對(duì)查詢語句進(jìn)展掃描、詞法

3、分析和語法分析 v從查詢語句中識(shí)別出言語符號(hào) v進(jìn)展語法檢查和語法分析 2. 查詢檢查查詢檢查 v 根據(jù)數(shù)據(jù)字典對(duì)合法的查詢語句進(jìn)展語義檢查 v 根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完好性約束定義對(duì)用戶的存 取權(quán)限進(jìn)展檢查 v 檢查經(jīng)過后把SQL查詢語句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式 v RDBMS普通都用查詢樹(語法分析樹)來表示擴(kuò)展的關(guān)系 代數(shù)表達(dá)式 v 把數(shù)據(jù)庫對(duì)象的外部稱號(hào)轉(zhuǎn)換為內(nèi)部表示 3. 查詢優(yōu)化查詢優(yōu)化 v查詢優(yōu)化：選擇一個(gè)高效執(zhí)行的查詢處置戰(zhàn)略 v查詢優(yōu)化分類 ： v代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化 v物理優(yōu)化：指存取途徑和底層操作算法的選擇 v查詢優(yōu)化方法選擇的根據(jù)： v基于規(guī)那么(ru

4、le based) v基于代價(jià)(cost based) v基于語義(semantic based) 4. 查詢執(zhí)行查詢執(zhí)行 v根據(jù)優(yōu)化器得到的執(zhí)行戰(zhàn)略生成查詢方案 v代碼生成器(code generator)生成執(zhí)行查詢方案的 代碼 9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處置關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處置 v9.1.1 查詢處置步驟查詢處置步驟 v9.1.2 實(shí)現(xiàn)查詢操作的算法例如實(shí)現(xiàn)查詢操作的算法例如 9.1.2 實(shí)現(xiàn)查詢操作的算法例如實(shí)現(xiàn)查詢操作的算法例如 v一、 選擇操作的實(shí)現(xiàn) v二、 銜接操作的實(shí)現(xiàn) 一、一、 選擇操作的實(shí)現(xiàn)選擇操作的實(shí)現(xiàn) v例1Select * from student where

5、； v思索的幾種情況： v C1：無條件； v C2：Sno200215121； v C3：Sage20； v C4：SdeptCS AND Sage20； 選擇操作的實(shí)現(xiàn)續(xù)選擇操作的實(shí)現(xiàn)續(xù) v選擇操作典型實(shí)現(xiàn)方法：選擇操作典型實(shí)現(xiàn)方法： v1. 簡單的全表掃描方法簡單的全表掃描方法 v對(duì)查詢的根本表順序掃描，逐一檢查每個(gè)元組能對(duì)查詢的根本表順序掃描，逐一檢查每個(gè)元組能 否滿足選擇條件，把滿足條件的元組作為結(jié)果輸否滿足選擇條件，把滿足條件的元組作為結(jié)果輸 出出 v適宜小表，不適宜大表適宜小表，不適宜大表 v2. 索引索引(或散列或散列)掃描方法掃描方法 v適宜選擇條件中的屬性上有索引適宜選擇條

6、件中的屬性上有索引(例如例如B+樹索引樹索引 或或Hash索引索引) v經(jīng)過索引先找到滿足條件的元組主碼或元組指針，經(jīng)過索引先找到滿足條件的元組主碼或元組指針， 再經(jīng)過元組指針直接在查詢的根本表中找到元組再經(jīng)過元組指針直接在查詢的根本表中找到元組 選擇操作的實(shí)現(xiàn)續(xù)選擇操作的實(shí)現(xiàn)續(xù) v 例1-C2 以C2為例，Sno200215121，并且Sno上 有索引(或Sno是散列碼) v 運(yùn)用索引(或散列)得到Sno為200215121 元組的指針 v 經(jīng)過元組指針在student表中檢索到該學(xué)生 v 例1-C3 以C3為例，Sage20，并且Sage 上有B+樹 索引 v 運(yùn)用B+樹索引找到Sage2

7、0的索引項(xiàng)，以此為入口點(diǎn)在 B+樹的順序集上得到Sage20的一切元組指針 v 經(jīng)過這些元組指針到student表中檢索到一切年齡大于20 的學(xué)生。 選擇操作的實(shí)現(xiàn)續(xù)選擇操作的實(shí)現(xiàn)續(xù) v例1-C4 以C4為例，SdeptCS AND Sage20，假設(shè)Sdept和Sage上都有索引： v算法一：分別用上面兩種方法分別找到Sdept CS的一組元組指針和Sage20的另一組元組指 針 v求這2組指針的交集 v到student表中檢索 v得到計(jì)算機(jī)系年齡大于20的學(xué)生 v算法二：找到SdeptCS的一組元組指針， v經(jīng)過這些元組指針到student表中檢索 v對(duì)得到的元組檢查另一些選擇條件(如Sa

8、ge20) 能否滿足 v把滿足條件的元組作為結(jié)果輸出。 二、二、 銜接操作的實(shí)現(xiàn)銜接操作的實(shí)現(xiàn) v銜接操作是查詢處置中最耗時(shí)的操作之一 v本節(jié)只討論等值銜接(或自然銜接)最常用的實(shí)現(xiàn)算 法 v例2 SELECT * FROM Student，SC v WHERE Student.Sno=SC.Sno； 銜接操作的實(shí)現(xiàn)續(xù)銜接操作的實(shí)現(xiàn)續(xù) v1. 嵌套循環(huán)方法(nested loop) v2. 排序-合并方法(sort-merge join 或merge join) v3. 索引銜接(index join)方法 v4. Hash Join方法 銜接操作的實(shí)現(xiàn)續(xù)銜接操作的實(shí)現(xiàn)續(xù) v嵌套循環(huán)方法嵌套循

9、環(huán)方法(nested loop) v對(duì)外層循環(huán)對(duì)外層循環(huán)(Student)的每一個(gè)元組的每一個(gè)元組(s)，檢索內(nèi)層循環(huán)，檢索內(nèi)層循環(huán) (SC)中的每一個(gè)元組中的每一個(gè)元組(sc) v檢查這兩個(gè)元組在銜接屬性檢查這兩個(gè)元組在銜接屬性(sno)上能否相等上能否相等 v假設(shè)滿足銜接條件，那么串接后作為結(jié)果輸出，直到外假設(shè)滿足銜接條件，那么串接后作為結(jié)果輸出，直到外 層循環(huán)表中的元組處置完為止層循環(huán)表中的元組處置完為止 銜接操作的實(shí)現(xiàn)續(xù)銜接操作的實(shí)現(xiàn)續(xù) 2. 排序排序-合并方法合并方法(sort-merge join 或或merge join) 適宜銜接的諸表曾經(jīng)排好序的情況適宜銜接的諸表曾經(jīng)排好序的

10、情況 排序合并銜接方法的步驟：排序合并銜接方法的步驟： 假設(shè)銜接的表沒有排好序，先對(duì)假設(shè)銜接的表沒有排好序，先對(duì)Student表和表和SC表按銜接屬表按銜接屬 性性Sno排序排序 取取Student表中第一個(gè)表中第一個(gè)Sno，依次掃描，依次掃描SC表中具有一樣表中具有一樣Sno 的元組的元組 銜接操作的實(shí)現(xiàn)續(xù)銜接操作的實(shí)現(xiàn)續(xù) 200215121 200215122 200215123 200215124 . . . 200215121 1 92 200215121 2 85 200215121 3 88 200215122 2 90 200215122 3 80 . . . 排序-合并銜接方法

11、表示圖 銜接操作的實(shí)現(xiàn)續(xù)銜接操作的實(shí)現(xiàn)續(xù) 排序合并銜接方法的步驟續(xù)： 當(dāng)掃描到Sno不一樣的第一個(gè)SC元組時(shí)，前往Student 表掃描它的下一個(gè)元組，再掃描SC表中具有一樣Sno 的元組，把它們銜接起來 反復(fù)上述步驟直到Student 表掃描完 銜接操作的實(shí)現(xiàn)續(xù)銜接操作的實(shí)現(xiàn)續(xù) v Student表和SC表都只需掃描一遍 v 假設(shè)2個(gè)表原來無序，執(zhí)行時(shí)間要加上對(duì)兩個(gè)表的排序時(shí) 間 v 對(duì)于2個(gè)大表，先排序后運(yùn)用sort-merge join方法執(zhí)行銜接， 總的時(shí)間普通仍會(huì)大大減少 銜接操作的實(shí)現(xiàn)續(xù)銜接操作的實(shí)現(xiàn)續(xù) 3. 索引銜接索引銜接(index join)方法方法 步驟：步驟： 在在SC

12、表上建立屬性表上建立屬性Sno的索引，假設(shè)原來沒有該索引的索引，假設(shè)原來沒有該索引 對(duì)對(duì)Student中每一個(gè)元組，由中每一個(gè)元組，由Sno值經(jīng)過值經(jīng)過SC的索引查找相的索引查找相 應(yīng)的應(yīng)的SC元組元組 把這些把這些SC元組和元組和Student元組銜接起來元組銜接起來 循環(huán)執(zhí)行，直到循環(huán)執(zhí)行，直到Student表中的元組處置完為止表中的元組處置完為止 銜接操作的實(shí)現(xiàn)續(xù)銜接操作的實(shí)現(xiàn)續(xù) 4. Hash Join方法方法 把銜接屬性作為把銜接屬性作為hash碼，用同一個(gè)碼，用同一個(gè)hash函數(shù)把函數(shù)把R和和S中的元組中的元組 散列到同一個(gè)散列到同一個(gè)hash文件中文件中 步驟：步驟： 劃分階段劃

13、分階段(partitioning phase)： 對(duì)包含較少元組的表對(duì)包含較少元組的表(比如比如R)進(jìn)展一遍處置進(jìn)展一遍處置 把它的元組按把它的元組按hash函數(shù)分散到函數(shù)分散到hash表的桶中表的桶中 試探階段試探階段(probing phase)：也稱為銜接階段：也稱為銜接階段(join phase) 對(duì)另一個(gè)表對(duì)另一個(gè)表(S)進(jìn)展一遍處置進(jìn)展一遍處置 把把S的元組散列到適當(dāng)?shù)牡脑M散列到適當(dāng)?shù)膆ash桶中桶中 把元組與桶中一切來自把元組與桶中一切來自R并與之相匹配的元組銜接起來并與之相匹配的元組銜接起來 銜接操作的實(shí)現(xiàn)續(xù)銜接操作的實(shí)現(xiàn)續(xù) v上面hash join算法前提：假設(shè)兩個(gè)表中較小

14、的表 在第一階段后可以完全放入內(nèi)存的hash桶中 v以上的算法思想可以推行到更加普通的多個(gè)表的 銜接算法上 第九章第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(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ù)數(shù) 優(yōu)優(yōu) 化化 9.4 物物 理理 優(yōu)優(yōu) 化化 9.5 小小 結(jié)結(jié) 9.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)中有著非常重要的位置 v關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵要素 v由于關(guān)系表達(dá)式的語義級(jí)別很高，使關(guān)系系統(tǒng)可以 從關(guān)系表達(dá)式中分析查詢語義，提供了執(zhí)

15、行查詢優(yōu) 化的可以性 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 v9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述 v9.2.2 一個(gè)實(shí)例一個(gè)實(shí)例 9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述 v關(guān)系系統(tǒng)的查詢優(yōu)化 v非關(guān)系系統(tǒng) 查詢優(yōu)化概述續(xù)查詢優(yōu)化概述續(xù) v 查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不用思索如何最好地表達(dá)查 詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的 “優(yōu)化做得更好 v (1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶 程序那么難以獲得這些信息 v (2)假設(shè)數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改動(dòng)了，系統(tǒng)可以自動(dòng)對(duì)查 詢重新優(yōu)化以選擇相順應(yīng)的執(zhí)行方案。在非關(guān)系系統(tǒng)中必 需重寫程序，而重寫程序在

16、實(shí)際運(yùn)用中往往是不太可以的。 查詢優(yōu)化概述續(xù)查詢優(yōu)化概述續(xù) (3)優(yōu)化器可以思索數(shù)百種不同的執(zhí)行方案，程序員普通只 能思索有限的幾種可以性。 (4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往 往只需最好的程序員才干掌握。系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)于使得 一切人都擁有這些優(yōu)化技術(shù) 查詢優(yōu)化概述續(xù)查詢優(yōu)化概述續(xù) v RDBMS經(jīng)過某種代價(jià)模型計(jì)算出各種查詢執(zhí)行戰(zhàn)略的執(zhí) 行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案 v 集中式數(shù)據(jù)庫 v 執(zhí)行開銷主要包括： v 磁盤存取塊數(shù)(I/O代價(jià)) v 處置機(jī)時(shí)間(CPU代價(jià)) v 查詢的內(nèi)存開銷 v I/O代價(jià)是最主要的 v 分布式數(shù)據(jù)庫 v 總代價(jià)=I/O代價(jià)+CPU

17、代價(jià)+內(nèi)存代價(jià)通訊代價(jià) 查詢優(yōu)化概述續(xù)查詢優(yōu)化概述續(xù) v查詢優(yōu)化的總目的： v選擇有效的戰(zhàn)略 v求得給定關(guān)系表達(dá)式的值 v使得查詢代價(jià)最小(實(shí)際上是較小) 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 v9.2.1 查詢優(yōu)化概述查詢優(yōu)化概述 v9.2.2 一個(gè)實(shí)例一個(gè)實(shí)例 9.2.2 一個(gè)實(shí)例一個(gè)實(shí)例 例3 求選修了2號(hào)課程的學(xué)生姓名。用SQL表達(dá)： SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SCo=2； 假定學(xué)生-課程數(shù)據(jù)庫中有1000個(gè)學(xué)生記錄，10000 個(gè)選課記錄 其中選修2號(hào)課程的選

18、課記錄為50個(gè) 一個(gè)實(shí)例續(xù)一個(gè)實(shí)例續(xù) v系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這 一查詢 vQ1=Sname(Student.Sno=SC.SnoSco=2 (StudentSC) vQ2=Sname(Sco=2 (Student SC) vQ3=Sname(Student Sco=2(SC) v 一個(gè)實(shí)例續(xù)一個(gè)實(shí)例續(xù) v 一、第一種情況一、第一種情況 v Q1=Sname(Student.Sno=SC.SnoSco=2 StudentSC) v 1. 計(jì)算廣義笛卡爾積計(jì)算廣義笛卡爾積 v 把把Student和和SC的每個(gè)元組銜接起來的做法：的每個(gè)元組銜接起來的做法： v 在內(nèi)存中盡可以多地

19、裝入某個(gè)表在內(nèi)存中盡可以多地裝入某個(gè)表(如如Student表表)的假設(shè)干塊，留出一塊的假設(shè)干塊，留出一塊 存放另一個(gè)表存放另一個(gè)表(如如SC表表)的元組。的元組。 v 把把SC中的每個(gè)元組和中的每個(gè)元組和Student中每個(gè)元組銜接，銜接后的元組裝滿一中每個(gè)元組銜接，銜接后的元組裝滿一 塊后就寫到中間文件上塊后就寫到中間文件上 v 從從SC中讀入一塊和內(nèi)存中的中讀入一塊和內(nèi)存中的Student元組銜接，直到元組銜接，直到SC表處置完。表處置完。 v 再讀入假設(shè)干塊再讀入假設(shè)干塊Student元組，讀入一塊元組，讀入一塊SC元組元組 v 反復(fù)上述處置過程，直到把反復(fù)上述處置過程，直到把Stude

20、nt表處置完表處置完 一個(gè)實(shí)例續(xù)一個(gè)實(shí)例續(xù) v 設(shè)一個(gè)塊能裝10個(gè)Student元組或100個(gè)SC元組，在內(nèi)存 中存放5塊Student元組和1塊SC元組，那么讀取總塊數(shù) 為 v v v =100+20100=2100塊 v 其中，讀Student表100塊。讀SC表20遍，每遍100塊。 假設(shè)每秒讀寫20塊，那么總計(jì)要花105s v 銜接后的元組數(shù)為103104=107。設(shè)每塊能裝10個(gè)元組， 那么寫出這些塊要用106/20=5104s 10 1000 510 1000 100 10000 一個(gè)實(shí)例續(xù)一個(gè)實(shí)例續(xù) 2. 作選擇操作 依次讀入銜接后的元組，按照選擇條件選取滿足要 求的記錄 假定內(nèi)

21、存處置時(shí)間忽略。讀取中間文件破費(fèi)的時(shí)間 (同寫中間文件一樣)需5104s 滿足條件的元組假設(shè)僅50個(gè)，均可放在內(nèi)存 一個(gè)實(shí)例續(xù)一個(gè)實(shí)例續(xù) 3. 作投影操作 把第2步的結(jié)果在Sname上作投影輸出，得到最終 結(jié)果 第一種情況下執(zhí)行查詢的總時(shí)間 105+25104105s 一切內(nèi)存處置時(shí)間均忽略不計(jì) 一個(gè)實(shí)例續(xù)一個(gè)實(shí)例續(xù) v二、二、 第二種情況第二種情況 v Q2=Sname(Sco=2 (Student SC) v1. 計(jì)算自然銜接計(jì)算自然銜接 v執(zhí)行自然銜接，讀取執(zhí)行自然銜接，讀取Student和和SC表的戰(zhàn)略不變，表的戰(zhàn)略不變， 總的讀取塊數(shù)仍為總的讀取塊數(shù)仍為2100塊破費(fèi)塊破費(fèi)105 s

22、 v自然銜接的結(jié)果比第一種情況大大減少，為自然銜接的結(jié)果比第一種情況大大減少，為104個(gè)個(gè) v寫出這些元組時(shí)間為寫出這些元組時(shí)間為104/10/20=50s，為第一種情況，為第一種情況 的千分之一的千分之一 v2. 讀取中間文件塊，執(zhí)行選擇運(yùn)算，破費(fèi)時(shí)間也為讀取中間文件塊，執(zhí)行選擇運(yùn)算，破費(fèi)時(shí)間也為 50s。 v3. 把第把第2步結(jié)果投影輸出。步結(jié)果投影輸出。 v 第二種情況總的執(zhí)行時(shí)間第二種情況總的執(zhí)行時(shí)間105+50+50205s 一個(gè)實(shí)例續(xù)一個(gè)實(shí)例續(xù) v三、三、 第三種情況第三種情況 v Q3=Sname(Student Sco=2(SC) v1. 先對(duì)先對(duì)SC表作選擇運(yùn)算，只需讀一遍表

23、作選擇運(yùn)算，只需讀一遍SC表，存表，存 取取100塊破費(fèi)時(shí)間為塊破費(fèi)時(shí)間為5s，由于滿足條件的元組僅，由于滿足條件的元組僅 50個(gè)，不用運(yùn)用中間文件。個(gè)，不用運(yùn)用中間文件。 v2. 讀取讀取Student表，把讀入的表，把讀入的Student元組和內(nèi)存元組和內(nèi)存 中的中的SC元組作銜接。也只需讀一遍元組作銜接。也只需讀一遍Student表共表共 100塊，破費(fèi)時(shí)間為塊，破費(fèi)時(shí)間為5s。 v3. 把銜接結(jié)果投影輸出把銜接結(jié)果投影輸出 v 第三種情況總的執(zhí)行時(shí)間第三種情況總的執(zhí)行時(shí)間5+510s 一個(gè)實(shí)例續(xù)一個(gè)實(shí)例續(xù) v 假設(shè)SC表的Cno字段上有索引 v 第一步就不用讀取一切的SC元組而只需讀取

24、Cno=2的那 些元組(50個(gè)) v 存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共34塊 v 假設(shè)Student表在Sno上也有索引 v 第二步也不用讀取一切的Student元組 v 由于滿足條件的SC記錄僅50個(gè)，涉及最多50個(gè)Student記 錄 v 讀取Student表的塊數(shù)也可大大減少 v 總的存取時(shí)間將進(jìn)一步減少到數(shù)秒 一個(gè)實(shí)例續(xù)一個(gè)實(shí)例續(xù) v把代數(shù)表達(dá)式Q1變換為Q2、 Q3， v即有選擇和銜接操作時(shí)，先做選擇操作，這樣參 與銜接的元組就可以大大減少，這是代數(shù)優(yōu)化 v在Q3中 vSC表的選擇操作算法有全表掃描和索引掃描2種 方法，經(jīng)過初步估算，索引掃描方法較優(yōu) v對(duì)于Student

25、和SC表的銜接，利用Student表上的 索引，采用index join代價(jià)也較小，這就是物理優(yōu) 化 第九章第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(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 小小 結(jié)結(jié) 9.3 代代 數(shù)數(shù) 優(yōu)優(yōu) 化化 v9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么 v9.3.2 查詢樹的啟發(fā)式優(yōu)化查詢樹的啟發(fā)式優(yōu)化 9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么 v代數(shù)優(yōu)化戰(zhàn)略：經(jīng)過對(duì)關(guān)系代

26、數(shù)表達(dá)式的等價(jià)變 換來提高查詢效率 v關(guān)系代數(shù)表達(dá)式的等價(jià)：指用一樣的關(guān)系替代兩 個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是一樣的 v兩個(gè)關(guān)系表達(dá)式E1和E2是等價(jià)的，可記為E1E2 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù)關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù) v 常用的等價(jià)變換規(guī)那么：常用的等價(jià)變換規(guī)那么： v 1. 銜接、笛卡爾積交換律銜接、笛卡爾積交換律 v 設(shè)設(shè)E1和和E2是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)是銜接運(yùn)算的條件，那是銜接運(yùn)算的條件，那 么有么有 v E1 E2E2 E1 v E1 E2E2 E1 v E1 E2E2 E1 v 2. 銜接、笛卡爾積的結(jié)合律銜接、笛卡爾積的結(jié)合律 v 設(shè)設(shè)E1，E

27、2，E3是關(guān)系代數(shù)表達(dá)式，是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和和F2是銜接運(yùn)算是銜接運(yùn)算 的條件，那么有的條件，那么有 v (E1 E2) E3E1 (E2 E3) v (E1 E2) E3E1 (E2 E3) v (E1 E2) E3E1 (E2 E3) 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù)關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù) 3. 投影的串接定律 ( (E) (E) 這里，E是關(guān)系代數(shù)表達(dá)式，Ai(i=1，2，n)，Bj(j=1，2，m) 是屬性名且A1，A2，An構(gòu)成B1，B2，Bm的子集。 4. 選擇的串接定律 ( (E) (E) 這里，E是關(guān)系代數(shù)表達(dá)式，F(xiàn)1、F2是選擇條件。 選擇的串接律闡明選擇條件可以

28、合并。這樣一次就可檢查全部條件。 n AAA, 21 m BBB, 21 n AAA, 21 1 F 2 F 2 1 FF 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù)關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù) 5. 選擇與投影操作的交換律 F( (E) (F(E) 選擇條件F只涉及屬性A1，An。 假設(shè)F中有不屬于A1，An的屬性B1， Bm那么有更普通的規(guī)那么： (F(E) (F( (E) n AAA, 21 n AAA, 21 n AAA, 21 n AAA, 21 mn BBBAAA, 2121 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù)關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù) 6. 選擇與笛卡爾積的交換律 假設(shè)F中涉及的屬性都是E

29、1中的屬性，那么 (E1E2) (E1)E2 假設(shè)F=F1F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及 E2中的屬性，那么由上面的等價(jià)變換規(guī)那么1，4，6可推 出： (E1E2) (E1) (E2) 假設(shè)F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性， 那么仍有 (E1E2) ( (E1)E2) 它使部分選擇在笛卡爾積前先做。 1 F 2 F 2 F 1 F F F F F 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù)關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù) 7. 選擇與并的分配律 設(shè)E=E1E2，E1，E2有一樣的屬性名，那么 F(E1E2)F(E1)F(E2) 8. 選擇與差運(yùn)算的分配律 假設(shè)E1與E2有一

30、樣的屬性名，那么 F(E1-E2)F(E1)-F(E2) 9. 選擇對(duì)自然銜接的分配律 F(E1 E2)F(E1) F(E2) F只涉及E1與E2的公共屬性 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù)關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么續(xù) 10. 投影與笛卡爾積的分配律 設(shè)E1和E2是兩個(gè)關(guān)系表達(dá)式，A1，An是E1的屬性， B1，Bm是E2的屬性，那么 (E1E2) (E1) (E2) 11. 投影與并的分配律 設(shè)E1和E2有一樣的屬性名，那么 (E1E2) (E1) (E2) mn BBBAAA, 2121 n AAA, 21 m BBB, 21 n AAA, 21 n AAA, 21 n AAA, 21 9

31、.3 代代 數(shù)數(shù) 優(yōu)優(yōu) 化化 v9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)那么 v9.3.2 查詢樹的啟發(fā)式優(yōu)化查詢樹的啟發(fā)式優(yōu)化 9.3.2 查詢樹的啟發(fā)式優(yōu)化查詢樹的啟發(fā)式優(yōu)化 v典型的啟發(fā)式規(guī)那么：典型的啟發(fā)式規(guī)那么： v1. 選擇運(yùn)算應(yīng)盡可以先做。在優(yōu)化戰(zhàn)略中這是最重選擇運(yùn)算應(yīng)盡可以先做。在優(yōu)化戰(zhàn)略中這是最重 要、最根本的一條要、最根本的一條 v2. 把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)展把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)展 v如有假設(shè)干投影和選擇運(yùn)算，并且它們都對(duì)同一個(gè)如有假設(shè)干投影和選擇運(yùn)算，并且它們都對(duì)同一個(gè) 關(guān)系操作，那么可以在掃描此關(guān)系的同時(shí)完成一切關(guān)系操作，那么可以在掃

32、描此關(guān)系的同時(shí)完成一切 的這些運(yùn)算以防止反復(fù)掃描關(guān)系的這些運(yùn)算以防止反復(fù)掃描關(guān)系 查詢樹的啟發(fā)式優(yōu)化續(xù)查詢樹的啟發(fā)式優(yōu)化續(xù) 3. 把投影同其前或其后的雙目運(yùn)算結(jié)合起來 4. 把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成 為一個(gè)銜接運(yùn)算 5. 找出公共子表達(dá)式 假設(shè)這種反復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系并 且從外存中讀入這個(gè)關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少 得多，那么先計(jì)算一次公共子表達(dá)式并把結(jié)果寫入中 間文件是合算的 當(dāng)查詢的是視圖時(shí)，定義視圖的表達(dá)式就是公共子表達(dá) 式的情況 查詢樹的啟發(fā)式優(yōu)化續(xù)查詢樹的啟發(fā)式優(yōu)化續(xù) v 遵照這些啟發(fā)式規(guī)那么，運(yùn)用9.3.1的等價(jià)變換公式來優(yōu)化 關(guān)系表達(dá)式的

33、算法。 v算法：關(guān)系表達(dá)式的優(yōu)化 v輸入：一個(gè)關(guān)系表達(dá)式的查詢樹 v輸出：優(yōu)化的查詢樹 v方法： v(1) 利用等價(jià)變換規(guī)那么4把形如F1F2Fn(E) 變換為F1(F2(Fn(E)。 v(2) 對(duì)每一個(gè)選擇，利用等價(jià)變換規(guī)那么49盡可以 把它移到樹的葉端。 查詢樹的啟發(fā)式優(yōu)化續(xù)查詢樹的啟發(fā)式優(yōu)化續(xù) (3) 對(duì)每一個(gè)投影利用等價(jià)變換規(guī)那么3，5，10，11中的普通 方式盡可以把它移向樹的葉端。 留意： 等價(jià)變換規(guī)那么3使一些投影消逝 規(guī)那么5把一個(gè)投影分裂為兩個(gè)，其中一個(gè)有可以被移向樹的葉端 (4) 利用等價(jià)變換規(guī)那么35把選擇和投影的串接合并成單個(gè) 選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多

34、個(gè)選擇或投影 能同時(shí)執(zhí)行，或在一次掃描中全部完成 查詢樹的啟發(fā)式優(yōu)化續(xù)查詢樹的啟發(fā)式優(yōu)化續(xù) (5) 把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算 (， ，-)和它一切的直接祖先為一組(這些直接祖先 是(，運(yùn)算)。 假設(shè)其后代直到葉子全是單目運(yùn)算，那么也將它們并入該組 但當(dāng)雙目運(yùn)算是笛卡爾積()，而且后面不是與它組成等值銜 接的選擇時(shí)，那么不能把選擇與這個(gè)雙目運(yùn)算組成同一組， 把這些單目運(yùn)算單獨(dú)分為一組 查詢樹的啟發(fā)式優(yōu)化續(xù)查詢樹的啟發(fā)式優(yōu)化續(xù) 例4 下面給出例3中 SQL語句的代數(shù)優(yōu)化例如。 (1) 把SQL語句轉(zhuǎn)換成查詢樹，如以以下圖所示 查詢樹 查詢樹的啟發(fā)式優(yōu)化續(xù)查詢樹的啟發(fā)式優(yōu)化續(xù) 為

35、了運(yùn)用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān)系 代數(shù)語法樹，那么上面的查詢樹如以以下圖所示。 關(guān)系代數(shù)語法樹 查詢樹的啟發(fā)式優(yōu)化續(xù)查詢樹的啟發(fā)式優(yōu)化續(xù) (2) 對(duì)查詢樹進(jìn)展優(yōu)化 利用規(guī)那么4、6把選擇SCo=2移到葉端，查詢樹便轉(zhuǎn)換 成以以下圖所示的優(yōu)化的查詢樹。這就是9.2.2節(jié)中Q3的查詢樹表 示 優(yōu)化后的查詢樹 第九章第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(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 小小 結(jié)結(jié) 9.4 物理優(yōu)化物理優(yōu)化 v代數(shù)優(yōu)

36、化改動(dòng)查詢語句中操作的次序和組合，不 涉及底層的存取途徑 v對(duì)于一個(gè)查詢語句有許多存取方案，它們的執(zhí)行 效率不同， 僅僅進(jìn)展代數(shù)優(yōu)化是不夠的 v物理優(yōu)化就是要選擇高效合理的操作算法或存取 途徑，求得優(yōu)化的查詢方案 物理優(yōu)化續(xù)物理優(yōu)化續(xù) v選擇的方法：選擇的方法： v基于規(guī)那么的啟發(fā)式優(yōu)化基于規(guī)那么的啟發(fā)式優(yōu)化 v基于代價(jià)估算的優(yōu)化基于代價(jià)估算的優(yōu)化 v兩者結(jié)合的優(yōu)化方法兩者結(jié)合的優(yōu)化方法 9.4 物理優(yōu)化物理優(yōu)化 v9.4.1 基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化 v9.4.2 基于代價(jià)的優(yōu)化基于代價(jià)的優(yōu)化 9.4.1 基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化基于啟發(fā)

37、式規(guī)那么的存取途徑選擇優(yōu)化 v一、 選擇操作的啟發(fā)式規(guī)那么 v二、 銜接操作的啟發(fā)式規(guī)那么 基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化 (續(xù)續(xù)) v一、一、 選擇操作的啟發(fā)式規(guī)那么選擇操作的啟發(fā)式規(guī)那么: v1. 對(duì)于小關(guān)系，運(yùn)用全表順序掃描，即使選對(duì)于小關(guān)系，運(yùn)用全表順序掃描，即使選 擇列上有索引擇列上有索引 v對(duì)于大關(guān)系，啟發(fā)式規(guī)那么有：對(duì)于大關(guān)系，啟發(fā)式規(guī)那么有： v2. 對(duì)于選擇條件是主碼值的查詢對(duì)于選擇條件是主碼值的查詢 v查詢結(jié)果最多是一個(gè)元組，可以選擇主碼索引查詢結(jié)果最多是一個(gè)元組，可以選擇主碼索引 v普通的普通的RDBMS會(huì)自動(dòng)建立主碼索引。會(huì)自動(dòng)建立

38、主碼索引。 v 基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化 (續(xù)續(xù)) 3. 對(duì)于選擇條件是非主屬性值的查詢，并且選擇 列上有索引 要估算查詢結(jié)果的元組數(shù)目 假設(shè)比例較小(10%)可以運(yùn)用索引掃描方法 否那么還是運(yùn)用全表順序掃描 基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化 (續(xù)續(xù)) 4. 對(duì)于選擇條件是屬性上的非等值查詢或者范圍 查詢，并且選擇列上有索引 要估算查詢結(jié)果的元組數(shù)目 假設(shè)比例較小(10%)可以運(yùn)用索引掃描方法 否那么還是運(yùn)用全表順序掃描 基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化 (續(xù)續(xù)) 5. 對(duì)于用A

39、ND銜接的合取選擇條件 假設(shè)有涉及這些屬性的組合索引 優(yōu)先采用組合索引掃描方法 假設(shè)某些屬性上有普通的索引 那么可以用例1-C4中引見的索引掃描方法 否那么運(yùn)用全表順序掃描。 6. 對(duì)于用OR銜接的析取選擇條件，普通運(yùn)用全表 順序掃描 基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化 (續(xù)續(xù)) v 二、二、 銜接操作的啟發(fā)式規(guī)那么：銜接操作的啟發(fā)式規(guī)那么： v1. 假設(shè)假設(shè)2個(gè)表都曾經(jīng)按照銜接屬性排序個(gè)表都曾經(jīng)按照銜接屬性排序 v 選用排序選用排序-合并方法合并方法 v2. 假設(shè)一個(gè)表在銜接屬性上有索引假設(shè)一個(gè)表在銜接屬性上有索引 v 選用索引銜接方法選用索引銜接方法 v3

40、. 假設(shè)上面假設(shè)上面2個(gè)規(guī)那么都不適用，其中一個(gè)表較小個(gè)規(guī)那么都不適用，其中一個(gè)表較小 v 選用選用Hash join方法方法 v 基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化 (續(xù)續(xù)) 4. 可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講 是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表) 。 理由： 設(shè)銜接表R與S分別占用的塊數(shù)為Br與Bs 銜接操作運(yùn)用的內(nèi)存緩沖區(qū)塊數(shù)為K 分配K-1塊給外表 假設(shè)R為外表，那么嵌套循環(huán)法存取的塊數(shù)為Br+( Br/K-1)Bs 顯然應(yīng)該選塊數(shù)小的表作為外表 9.4 物理優(yōu)化續(xù)物理優(yōu)化續(xù) v9.4.1 基于啟發(fā)式規(guī)那么的存取途徑

41、選擇優(yōu)化基于啟發(fā)式規(guī)那么的存取途徑選擇優(yōu)化 v9.4.2 基于代價(jià)的優(yōu)化基于代價(jià)的優(yōu)化 9.4.2 基于代價(jià)的優(yōu)化基于代價(jià)的優(yōu)化 v啟發(fā)式規(guī)那么優(yōu)化是定性的選擇，適宜解釋執(zhí)行 的系統(tǒng) v解釋執(zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷之 中 v編譯執(zhí)行的系統(tǒng)中查詢優(yōu)化和查詢執(zhí)行是分開的 v可以采用精細(xì)復(fù)雜一些的基于代價(jià)的優(yōu)化方法 基于代價(jià)的優(yōu)化續(xù)基于代價(jià)的優(yōu)化續(xù) v一、 統(tǒng)計(jì)信息 v二、 代價(jià)估算例如 基于代價(jià)的優(yōu)化續(xù)基于代價(jià)的優(yōu)化續(xù) 一、一、 統(tǒng)計(jì)信息統(tǒng)計(jì)信息 基于代價(jià)的優(yōu)化方法要計(jì)算各種操作算基于代價(jià)的優(yōu)化方法要計(jì)算各種操作算 法的執(zhí)行代價(jià)，與數(shù)據(jù)庫的外形親密法的執(zhí)行代價(jià)，與數(shù)據(jù)庫的外形親密 相關(guān)

42、相關(guān) 數(shù)據(jù)字典中存儲(chǔ)的優(yōu)化器需求的統(tǒng)計(jì)信數(shù)據(jù)字典中存儲(chǔ)的優(yōu)化器需求的統(tǒng)計(jì)信 息：息： 1. 對(duì)每個(gè)根本表對(duì)每個(gè)根本表 該表的元組總數(shù)該表的元組總數(shù)(N) 元組長度元組長度(l) 占用的塊數(shù)占用的塊數(shù)(B) 占用的溢出塊數(shù)占用的溢出塊數(shù)(BO) 基于代價(jià)的優(yōu)化續(xù)基于代價(jià)的優(yōu)化續(xù) 2. 對(duì)基表的每個(gè)列 該列不同值的個(gè)數(shù)(m) 選擇率(f) 假設(shè)不同值的分布是均勻的，f1/m 假設(shè)不同值的分布不均勻，那么每個(gè)值的選擇率 具有該值的元組數(shù)/N 該列最大值 該列最小值 該列上能否曾經(jīng)建立了索引 索引類型(B+樹索引、Hash索引、聚集索引) 基于代價(jià)的優(yōu)化續(xù)基于代價(jià)的優(yōu)化續(xù) 3. 對(duì)索引(如B+樹索引) 索引的層數(shù)(L) 不同索引值的個(gè)數(shù) 索引的選擇基數(shù)S(有S個(gè)元組具有某個(gè)索引值) 索引的葉結(jié)點(diǎn)數(shù)(Y) 基于代價(jià)的優(yōu)化續(xù)基于代價(jià)的優(yōu)化續(xù) 二、二、 代價(jià)估算例如代價(jià)估算例如 全表掃描算法的代價(jià)估算公式全表掃描算法的代價(jià)估算公式 假設(shè)根本表大小為假設(shè)根本表大小為B塊，全表掃描算法的代價(jià)塊，全表掃描算法的代價(jià) cost B 假設(shè)選擇條件是碼值，那么平均搜索代價(jià)假