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

1、數(shù)據(jù)庫(kù)系統(tǒng)概論 An Introduction to Database System第九章 關(guān)系查詢(xún)處理 和查詢(xún)優(yōu)化第三篇 系統(tǒng)篇 討論數(shù)據(jù)庫(kù)管理系統(tǒng)中查詢(xún)處理和事務(wù)管理的基本概念和基礎(chǔ)知識(shí)第9章 關(guān)系查詢(xún)處理和查詢(xún)優(yōu)化第10章 數(shù)據(jù)庫(kù)恢復(fù)技術(shù)第11章 并發(fā)控制第12章 數(shù)據(jù)庫(kù)管理系統(tǒng)第九章 關(guān)系查詢(xún)處理和查詢(xún)優(yōu)化9.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理 9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 *9.5 查詢(xún)計(jì)劃的執(zhí)行9.6 小 結(jié) 關(guān)系查詢(xún)處理和查詢(xún)優(yōu)化（續(xù)）本章內(nèi)容： 關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)的查詢(xún)處理步驟 查詢(xún)優(yōu)化的概念 基本方法和技術(shù) 查詢(xún)優(yōu)化分類(lèi) ：代數(shù)優(yōu)化：指關(guān)系代

2、數(shù)表達(dá)式的優(yōu)化 物理優(yōu)化：指存取路徑和底層操作算法的選擇9.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理9.1.1 查詢(xún)處理步驟9.1.2 實(shí)現(xiàn)查詢(xún)操作的算法示例 9.1.1 查詢(xún)處理步驟關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)查詢(xún)處理階段 ： 1. 查詢(xún)分析2. 查詢(xún)檢查3. 查詢(xún)優(yōu)化 4. 查詢(xún)執(zhí)行 查詢(xún)處理步驟（續(xù)）查詢(xún)計(jì)劃的執(zhí)行代碼代數(shù)優(yōu)化物理優(yōu)化等查詢(xún)語(yǔ)句詞法分析語(yǔ)法分析語(yǔ)義分析符號(hào)名轉(zhuǎn)換安全性檢查完整性初步檢查代碼生成查詢(xún)執(zhí)行計(jì)劃查詢(xún)樹(shù)(query tree)查詢(xún)分析查詢(xún)檢查查詢(xún)優(yōu)化查詢(xún)執(zhí)行數(shù)據(jù)庫(kù)數(shù)據(jù)字典 1. 查詢(xún)分析查詢(xún)分析的任務(wù)：對(duì)查詢(xún)語(yǔ)句進(jìn)行掃描、詞法分析和語(yǔ)法分析詞法分析：從查詢(xún)語(yǔ)句中識(shí)別出正確的語(yǔ)言符號(hào) 語(yǔ)

3、法分析：進(jìn)行語(yǔ)法檢查 2. 查詢(xún)檢查 查詢(xún)檢查的任務(wù)合法權(quán)檢查視圖轉(zhuǎn)換安全性檢查完整性初步檢查根據(jù)數(shù)據(jù)字典中有關(guān)的模式定義檢查語(yǔ)句中的數(shù)據(jù)庫(kù)對(duì)象，如關(guān)系名、屬性名是否存在和有效 如果是對(duì)視圖的操作，則要用視圖消解方法把對(duì)視圖的操作轉(zhuǎn)換成對(duì)基本表的操作 2. 查詢(xún)檢查 根據(jù)數(shù)據(jù)字典中的用戶(hù)權(quán)限和完整性約束定義對(duì)用戶(hù)的存取權(quán)限進(jìn)行檢查檢查通過(guò)后把SQL查詢(xún)語(yǔ)句轉(zhuǎn)換成內(nèi)部表示，即等價(jià)的關(guān)系代數(shù)表達(dá)式。關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)一般都用查詢(xún)樹(shù)，也稱(chēng)為語(yǔ)法分析樹(shù)來(lái)表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式。 3. 查詢(xún)優(yōu)化查詢(xún)優(yōu)化：選擇一個(gè)高效執(zhí)行的查詢(xún)處理策略 查詢(xún)優(yōu)化分類(lèi) 代數(shù)優(yōu)化/邏輯優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化物理優(yōu)化：

4、指存取路徑和底層操作算法的選擇查詢(xún)優(yōu)化的選擇依據(jù)基于規(guī)則(rule based)基于代價(jià)(cost based)基于語(yǔ)義(semantic based) 4. 查詢(xún)執(zhí)行 依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢(xún)執(zhí)行計(jì)劃代碼生成器(code generator)生成執(zhí)行查詢(xún)計(jì)劃的代碼 兩種執(zhí)行方法自頂向下自底向上9.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理9.1.1 查詢(xún)處理步驟9.1.2 實(shí)現(xiàn)查詢(xún)操作的算法示例 9.1.2 實(shí)現(xiàn)查詢(xún)操作的算法示例 選擇操作的實(shí)現(xiàn) 連接操作的實(shí)現(xiàn) 1.選擇操作的實(shí)現(xiàn)選擇操作典型實(shí)現(xiàn)方法：（1） 全表掃描方法 (Table Scan)對(duì)查詢(xún)的基本表順序掃描，逐一檢查每個(gè)元組是否滿(mǎn)足選

5、擇條件，把滿(mǎn)足條件的元組作為結(jié)果輸出 適合小表，不適合大表（2）索引掃描方法 (Index Scan)適合于選擇條件中的屬性上有索引(例如B+樹(shù)索引或Hash索引) 通過(guò)索引先找到滿(mǎn)足條件的元組主碼或元組指針，再通過(guò)元組指針直接在查詢(xún)的基本表中找到元組 選擇操作的實(shí)現(xiàn)（續(xù)） 例9.1 SELECT * FROM Student WHERE 考慮的幾種情況： C1：無(wú)條件； C2：Sno201215121； C3：Sage20； C4：SdeptCS AND Sage20； 選擇操作的實(shí)現(xiàn)（續(xù)） 全表掃描算法假設(shè)可以使用的內(nèi)存為M塊，全表掃描算法思想：按照物理次序讀Student的M塊到內(nèi)存檢查

6、內(nèi)存的每個(gè)元組t，如果滿(mǎn)足選擇條件，則輸出t如果student還有其他塊未被處理，重復(fù)和選擇操作的實(shí)現(xiàn)（續(xù)）索引掃描算法例9.1-C2 SELECT * FROM Student WHERE Sno=201215121假設(shè)Sno上有索引(或Sno是散列碼)算法：使用索引(或散列)得到Sno為201215121 元組的指針通過(guò)元組指針在Student表中檢索到該學(xué)生選擇操作的實(shí)現(xiàn)（續(xù)）例9.1-C3 SELECT * FROM Student WHERE Sage20假設(shè)Sage 上有B+樹(shù)索引算法：使用B+樹(shù)索引找到Sage=20的索引項(xiàng)，以此為入口點(diǎn)在B+樹(shù)的順序集上得到Sage20的所有元

7、組指針通過(guò)這些元組指針到student表中檢索到所有年齡大于20的學(xué)生。 選擇操作的實(shí)現(xiàn)（續(xù)）例9.1-C4 SELECT * FROM Student WHERE Sdept=CS AND Sage20;假設(shè)Sdept和Sage上都有索引算法一：分別用Index Scan找到SdeptCS的一組元組指針和Sage20的另一組元組指針求這兩組指針的交集到Student表中檢索得到計(jì)算機(jī)系年齡大于20的學(xué)生選擇操作的實(shí)現(xiàn)（續(xù)）算法二：找到Sdept=CS的一組元組指針，通過(guò)這些元組指針到Student表中檢索并對(duì)得到的元組檢查另一些選擇條件(如Sage20)是否滿(mǎn)足把滿(mǎn)足條件的元組作為結(jié)果輸出。

8、 2.連接操作的實(shí)現(xiàn) 連接操作是查詢(xún)處理中最耗時(shí)的操作之一 本節(jié)只討論等值連接(或自然連接)最常用的實(shí)現(xiàn)算法 例9.2 SELECT * FROM Student, SC WHERE Student.Sno=SC.Sno; 連接操作的實(shí)現(xiàn)（續(xù)）（1）嵌套循環(huán)算法(nested loop join) （2）排序-合并算法(sort-merge join 或merge join)（3）索引連接(index join)算法 （4）Hash Join算法 連接操作的實(shí)現(xiàn)（續(xù)）（1）嵌套循環(huán)算法(nested loop join)對(duì)外層循環(huán)(Student表)的每一個(gè)元組(s)，檢索內(nèi)層循環(huán)(SC表)中

9、的每一個(gè)元組(sc)檢查這兩個(gè)元組在連接屬性(Sno)上是否相等如果滿(mǎn)足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止。參見(jiàn)愛(ài)課程網(wǎng)9.1節(jié)動(dòng)畫(huà)連接操作的實(shí)現(xiàn)(1)-嵌套循環(huán)連接操作的實(shí)現(xiàn)（續(xù)）（2）排序-合并算法(sort-merge join 或merge join) 如果連接的表沒(méi)有排好序，先對(duì)Student表和SC表按連接屬性Sno排序 取Student表中第一個(gè)Sno，依次掃描SC表中具有相同Sno的元組 當(dāng)掃描到Sno不相同的第一個(gè)SC元組時(shí)，返回Student表掃描它的下一個(gè)元組，再掃描SC表中具有相同Sno的元組，把它們連接起來(lái) 重復(fù)上述步驟直到Student

10、 表掃描完連接操作的實(shí)現(xiàn)（續(xù)）201215121 201215122 201215123 201215125 .201215121 1 92201215121 2 85201215121 3 88201215122 2 90201215122 3 80.圖9.2 排序-合并連接方法示意圖連接操作的實(shí)現(xiàn)（續(xù)）Student表和SC表都只要掃描一遍如果兩個(gè)表原來(lái)無(wú)序，執(zhí)行時(shí)間要加上對(duì)兩個(gè)表的排序時(shí)間對(duì)于大表，先排序后使用排序-合并連接算法執(zhí)行連接，總的時(shí)間一般仍會(huì)減少 參見(jiàn)愛(ài)課程網(wǎng)9.1節(jié)動(dòng)畫(huà)連接操作的實(shí)現(xiàn)（2）-排序合并 連接操作的實(shí)現(xiàn)（續(xù)）（3）索引連接(index join)算法步驟： 在S

11、C表上已經(jīng)建立屬性Sno的索引。 對(duì)Student中每一個(gè)元組，由Sno值通過(guò)SC的索引查找相應(yīng)的SC元組。 把這些SC元組和Student元組連接起來(lái) 循環(huán)執(zhí)行，直到Student表中的元組處理完為止 參見(jiàn)愛(ài)課程網(wǎng)9.1節(jié)動(dòng)畫(huà)連接操作的實(shí)現(xiàn)(4)- 索引連接 連接操作的實(shí)現(xiàn)（續(xù)）（4）Hash Join算法 把連接屬性作為hash碼，用同一個(gè)hash函數(shù)把Student表和SC表中的元組散列到hash表中。劃分階段(building phase, 也稱(chēng)為partitioning phase)對(duì)包含較少元組的表(如Student表)進(jìn)行一遍處理把它的元組按hash函數(shù)分散到hash表的桶中試探

12、階段(probing phase,也稱(chēng)為連接階段join phase) 對(duì)另一個(gè)表(SC表)進(jìn)行一遍處理把SC表的元組也按同一個(gè)hash函數(shù)（hash碼是連接屬性）進(jìn)行散列把SC元組與桶中來(lái)自Student表并與之相匹配的元組連接起來(lái)連接操作的實(shí)現(xiàn)（續(xù)）上面hash join算法前提：假設(shè)兩個(gè)表中較小的表在第一階段后可以完全放入內(nèi)存的hash桶中 參見(jiàn)愛(ài)課程網(wǎng)9.1節(jié)動(dòng)畫(huà)連接操作的實(shí)現(xiàn)(3)-散列連接 第九章 關(guān)系查詢(xún)處理和查詢(xún)優(yōu)化9.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理 9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 *9.5 查詢(xún)計(jì)劃的執(zhí)行9.6 小 結(jié) 9.2 關(guān)系數(shù)據(jù)庫(kù)系

13、統(tǒng)的查詢(xún)優(yōu)化查詢(xún)優(yōu)化在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中有著非常重要的地位 關(guān)系查詢(xún)優(yōu)化是影響關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)性能的關(guān)鍵因素 由于關(guān)系表達(dá)式的語(yǔ)義級(jí)別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢(xún)語(yǔ)義，提供了執(zhí)行查詢(xún)優(yōu)化的可能性 9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化9.2.1查詢(xún)優(yōu)化概述9.2.2一個(gè)實(shí)例9.2.1 查詢(xún)優(yōu)化概述關(guān)系系統(tǒng)的查詢(xún)優(yōu)化是關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)實(shí)現(xiàn)的關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)的優(yōu)點(diǎn)所在減輕了用戶(hù)選擇存取路徑的負(fù)擔(dān) 查詢(xún)優(yōu)化概述（續(xù)）非關(guān)系系統(tǒng)用戶(hù)使用過(guò)程化的語(yǔ)言表達(dá)查詢(xún)要求，執(zhí)行何種記錄級(jí)的操作，以及操作的序列是由用戶(hù)來(lái)決定的 用戶(hù)必須了解存取路徑，系統(tǒng)要提供用戶(hù)選擇存取路徑的手段，查詢(xún)效率由用戶(hù)的存

14、取策略決定如果用戶(hù)做了不當(dāng)?shù)倪x擇，系統(tǒng)是無(wú)法對(duì)此加以改進(jìn)的查詢(xún)優(yōu)化概述查詢(xún)優(yōu)化的優(yōu)點(diǎn)用戶(hù)不必考慮如何最好地表達(dá)查詢(xún)以獲得較好的效率系統(tǒng)可以比用戶(hù)程序的“優(yōu)化”做得更好 （1） 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶(hù)程序則難以獲得這些信息。（2）如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢(xún)重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫(xiě)程序，而重寫(xiě)程序在實(shí)際應(yīng)用中往往是不太可能的。查詢(xún)優(yōu)化概述（續(xù)）（3）優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序員一般只能考慮有限的幾種可能性。（4）優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)于

15、使得所有人都擁有這些優(yōu)化技術(shù)。查詢(xún)優(yōu)化概述（續(xù)）關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)通過(guò)某種代價(jià)模型計(jì)算出各種查詢(xún)執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案集中式數(shù)據(jù)庫(kù)執(zhí)行開(kāi)銷(xiāo)主要包括磁盤(pán)存取塊數(shù)(I/O代價(jià))處理機(jī)時(shí)間(CPU代價(jià))查詢(xún)的內(nèi)存開(kāi)銷(xiāo) I/O代價(jià)是最主要的 分布式數(shù)據(jù)庫(kù)總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)通信代價(jià) 查詢(xún)優(yōu)化概述（續(xù)）查詢(xún)優(yōu)化的總目標(biāo)選擇有效的策略求得給定關(guān)系表達(dá)式的值使得查詢(xún)代價(jià)最小(實(shí)際上是較小) 9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化9.2.1查詢(xún)優(yōu)化概述9.2.2一個(gè)實(shí)例9.2.2 一個(gè)實(shí)例一個(gè)關(guān)系查詢(xún)可以對(duì)應(yīng)不同的執(zhí)行方案，其效率可能相差非常大。例9.3 求選修了2號(hào)課程

16、的學(xué)生姓名。 用SQL表達(dá)： SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.Sno AND SC.Cno=2 假定學(xué)生-課程數(shù)據(jù)庫(kù)中有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄選修2號(hào)課程的選課記錄為50個(gè) 一個(gè)實(shí)例（續(xù)）可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來(lái)完成這一查詢(xún)Q1=Sname(Student.Sno=SC.SnoSC.Cno=2 (StudentSC)Q2=Sname(SC.Cno=2 (Student SC)Q3=Sname(Student SC.Cno=2(SC) 一個(gè)實(shí)例（續(xù)）1.第一種情況Q1=Sname(Stud

17、ent.Sno=SC.SnoSC.Cno=2 (StudentSC)一個(gè)實(shí)例（續(xù)）（1） 計(jì)算廣義笛卡爾積 算法：在內(nèi)存中盡可能多地裝入某個(gè)表(如Student表)的若干塊，留出一塊存放另一個(gè)表(如SC表)的元組。把SC中的每個(gè)元組和Student中每個(gè)元組連接，連接后的元組裝滿(mǎn)一塊后就寫(xiě)到中間文件上從SC中讀入一塊和內(nèi)存中的Student元組連接，直到SC表處理完。再讀入若干塊Student元組，讀入一塊SC元組重復(fù)上述處理過(guò)程，直到把Student表處理完 一個(gè)實(shí)例（續(xù)）設(shè)一個(gè)塊能裝10個(gè)Student元組或100個(gè)SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為

18、 =100+20100=2100塊讀Student表100塊，讀SC表20遍，每遍100塊，則總計(jì)要讀取2100數(shù)據(jù)塊。連接后的元組數(shù)為103104=107。設(shè)每塊能裝10個(gè)元組，則寫(xiě)出106 塊。一個(gè)實(shí)例（續(xù)）（2）作選擇操作 依次讀入連接后的元組，按照選擇條件選取滿(mǎn)足要求的記錄假定內(nèi)存處理時(shí)間忽略。讀取中間文件花費(fèi)的時(shí)間(同寫(xiě)中間文件一樣)需讀入106塊。 若滿(mǎn)足條件的元組假設(shè)僅50個(gè)，均可放在內(nèi)存。 一個(gè)實(shí)例（續(xù)）（3）作投影操作 把第（2）步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果 第一種情況下執(zhí)行查詢(xún)的總讀寫(xiě)數(shù)據(jù)塊=2100+106 +106一個(gè)實(shí)例（續(xù)）2.第二種情況 Q2=S

19、name(Sc.Cno=2 (Student SC)（1）計(jì)算自然連接 執(zhí)行自然連接，讀取Student和SC表的策略不變，總的讀取塊數(shù)仍為2100塊自然連接的結(jié)果比第一種情況大大減少，為104個(gè)元組寫(xiě)出數(shù)據(jù)塊= 103 塊 一個(gè)實(shí)例（續(xù)）2.第二種情況（續(xù)）（2）讀取中間文件塊，執(zhí)行選擇運(yùn)算，讀取的數(shù)據(jù)塊= 103 塊（3）把第2步結(jié)果投影輸出。第二種情況下執(zhí)行查詢(xún)的總讀寫(xiě)數(shù)據(jù)塊=2100+ 103 +103其執(zhí)行代價(jià)大約是第一種情況的488分之一 一個(gè)實(shí)例（續(xù)）3.第三種情況Q3=Sname(Student SC.Cno=2(SC)（1）先對(duì)SC表作選擇運(yùn)算，只需讀一遍SC表，存取 100

20、塊，因?yàn)闈M(mǎn)足條件的元組僅50個(gè)，不必使用中 間文件。（2）讀取Student表，把讀入的Student元組和內(nèi)存中 的SC元組作連接。也只需讀一遍Student表共100 塊。（3）把連接結(jié)果投影輸出 一個(gè)實(shí)例（續(xù)）3.第三種情況（續(xù)）第三種情況總的讀寫(xiě)數(shù)據(jù)塊=100+100其執(zhí)行代價(jià)大約是第一種情況的萬(wàn)分之一，是第二種情況的20分之一一個(gè)實(shí)例（續(xù)）假如SC表的Cno字段上有索引第一步就不必讀取所有的SC元組而只需讀取Cno=2的那些元組(50個(gè))存取的索引塊和SC中滿(mǎn)足條件的數(shù)據(jù)塊大約總共34塊若Student表在Sno上也有索引不必讀取所有的Student元組因?yàn)闈M(mǎn)足條件的SC記錄僅50個(gè)

21、，涉及最多50個(gè)Student記錄讀取Student表的塊數(shù)也可大大減少 一個(gè)實(shí)例（續(xù)）把代數(shù)表達(dá)式Q1變換為Q2、 Q3Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)Q2=Sname(Sc.Cno=2 (Student SC)Q3=Sname(Student SC.Cno=2(SC)有選擇和連接操作時(shí)，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數(shù)優(yōu)化 實(shí)例: 小結(jié)在Q3中SC表的選擇操作算法有全表掃描或索引掃描，經(jīng)過(guò)初步估算，索引掃描方法較優(yōu)。對(duì)于Student和SC表的連接，利用Student表上的索引，采用索引連接代價(jià)也較小，這

22、就是物理優(yōu)化。第九章 關(guān)系查詢(xún)處理和查詢(xún)優(yōu)化9.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理 9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 *9.5 查詢(xún)計(jì)劃的執(zhí)行9.6 小 結(jié) 9.3 代 數(shù) 優(yōu) 化9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 9.3.2 查詢(xún)樹(shù)的啟發(fā)式優(yōu)化 9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 代數(shù)優(yōu)化策略：通過(guò)對(duì)關(guān)系代數(shù)表達(dá)式的等價(jià)變換來(lái)提高查詢(xún)效率 關(guān)系代數(shù)表達(dá)式的等價(jià)：指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的兩個(gè)關(guān)系表達(dá)式E1和E2是等價(jià)的，可記為E1E2 *關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）常用的等價(jià)變換規(guī)則：1.連接、笛卡爾積交換律 設(shè)E1

23、和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E12.連接、笛卡爾積的結(jié)合律 設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件 (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) *關(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是選擇條件選

24、擇的串接律說(shuō)明選擇條件可以合并,這樣一次就可檢查全部條件*關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）5.選擇與投影操作的交換律 F( (E) (F(E)選擇條件F只涉及屬性A1，An。若F中有不屬于A1，An的屬性B1，Bm有更一般規(guī)則： (F(E ) (F ( (E)*關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）6. 選擇與笛卡爾積的交換律如果F中涉及的屬性都是E1中的屬性，則 F(E1E2)F(E1)E2如果F=F1F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價(jià)變換規(guī)則1，4，6可推出： F(E1E2) (E1) (E2)若F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則仍有

25、F(E1E2) ( (E1)E2) 它使部分選擇在笛卡爾積前先做。 *關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）7. 選擇與并的分配律 設(shè)E=E1E2，E1，E2有相同的屬性名，則 F(E1E2)F(E1)F(E2)8. 選擇與差運(yùn)算的分配律 若E1與E2有相同的屬性名，則 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ù)）10. 投影與笛卡爾積的分配律 設(shè)E1和E2是兩個(gè)關(guān)系表達(dá)式，A1，An是E1的屬性， B1，Bm是E2的屬性，則 (E1E2) (E1) (E2)11. 投影與

26、并的分配律 設(shè)E1和E2有相同的屬性名，則 (E1E2) (E1) (E2)9.3 代 數(shù) 優(yōu) 化9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 9.3.2 查詢(xún)樹(shù)的啟發(fā)式優(yōu)化 9.3.2 查詢(xún)樹(shù)的啟發(fā)式優(yōu)化 典型的啟發(fā)式規(guī)則（1）選擇運(yùn)算應(yīng)盡可能先做 在優(yōu)化策略中這是最重要、最基本的一條。（2）把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行如有若干投影和選擇運(yùn)算，并且它們都對(duì)同一個(gè)關(guān)系操作，則可以在掃描此關(guān)系的同時(shí)完成所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系。查詢(xún)樹(shù)的啟發(fā)式優(yōu)化（續(xù)）（3） 把投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái)，沒(méi)有必要為了去掉某些字段而掃描一遍關(guān)系。（4） 把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來(lái)成為一

27、個(gè)連接運(yùn)算，連接特別是等值連接運(yùn)算要比同樣關(guān)系上的笛卡爾積省很多時(shí)間。 查詢(xún)樹(shù)的啟發(fā)式優(yōu)化（續(xù)）（5） 找出公共子表達(dá)式如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系并且從外存中讀入這個(gè)關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少得多則先計(jì)算一次公共子表達(dá)式并把結(jié)果寫(xiě)入中間文件是合算的。當(dāng)查詢(xún)的是視圖時(shí)，定義視圖的表達(dá)式就是公共子表達(dá)式的情況*查詢(xún)樹(shù)的啟發(fā)式優(yōu)化（續(xù)）遵循這些啟發(fā)式規(guī)則，應(yīng)用9.3.1的等價(jià)變換公式來(lái)優(yōu)化關(guān)系表達(dá)式的算法。算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的查詢(xún)樹(shù)輸出：優(yōu)化的查詢(xún)樹(shù)方法：（1）利用等價(jià)變換規(guī)則4把形如F1F2Fn(E)變換為 F1(F2(Fn(E)。（2）對(duì)每一個(gè)選擇，

28、利用等價(jià)變換規(guī)則49盡可能把它 移到樹(shù)的葉端。規(guī)則4： 合并或分解選擇運(yùn)算規(guī)則5-9： 選擇運(yùn)算與其他運(yùn)算交換規(guī)則4: 選擇的串接定律 ( (E) (E)*查詢(xún)樹(shù)的啟發(fā)式優(yōu)化（續(xù)）（3）對(duì)每一個(gè)投影利用等價(jià)變換規(guī)則3，5，10，11中的一般形式盡可能把它移向樹(shù)的葉端。注意： 等價(jià)變換規(guī)則3使一些投影消失或使一些投影出現(xiàn)規(guī)則5把一個(gè)投影分裂為兩個(gè)，其中一個(gè)有可能被移向樹(shù)的葉端 （4）利用等價(jià)變換規(guī)則35，把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影，使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成規(guī)則3： 合并或分解投影運(yùn)算規(guī)則5,10,11：投影運(yùn)算與其他運(yùn)算交換規(guī)則3：

29、合并或分解投影運(yùn)算規(guī)則4：合并或分解選擇運(yùn)算規(guī)則5：投影運(yùn)算與選擇運(yùn)算交換查詢(xún)樹(shù)的啟發(fā)式優(yōu)化（續(xù)） （5）把上述得到的語(yǔ)法樹(shù)的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(， ，-)和它所有的直接祖先為一組(這些直接祖先是(，運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組但當(dāng)雙目運(yùn)算是笛卡爾積()，而且后面不是與它組成等值連接的選擇時(shí)，則不能把選擇與這個(gè)雙目運(yùn)算組成同一組 查詢(xún)樹(shù)的啟發(fā)式優(yōu)化（續(xù)）例9.4下面給出例9.3中 SQL語(yǔ)句的代數(shù)優(yōu)化示例 （1）把SQL語(yǔ)句轉(zhuǎn)換成查詢(xún)樹(shù)，如下圖所示圖9.3 查詢(xún)樹(shù)圖查詢(xún)樹(shù)的啟發(fā)式優(yōu)化（續(xù)）為了使用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān)系代數(shù)語(yǔ)法樹(shù)，則上面的

30、查詢(xún)樹(shù)如圖9.4所示。 圖9.4 關(guān)系代數(shù)語(yǔ)法樹(shù)圖 查詢(xún)樹(shù)的啟發(fā)式優(yōu)化（續(xù)）（2 ）對(duì)查詢(xún)樹(shù)進(jìn)行優(yōu)化利用規(guī)則4、6把選擇SC.Cno=2移到葉端，圖9.4查詢(xún)樹(shù)便轉(zhuǎn)換成下圖優(yōu)化的查詢(xún)樹(shù)。這就是9.2.2節(jié)中Q3的查詢(xún)樹(shù)表示。參見(jiàn)愛(ài)課程網(wǎng)9.3節(jié)動(dòng)畫(huà)查詢(xún)樹(shù)的啟發(fā)式優(yōu)化 第九章 關(guān)系查詢(xún)處理和查詢(xún)優(yōu)化9.1 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理 9.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 *9.5 查詢(xún)計(jì)劃的執(zhí)行9.6 小 結(jié) 9.4 物理優(yōu)化代數(shù)優(yōu)化改變查詢(xún)語(yǔ)句中操作的次序和組合，不涉及底層的存取路徑對(duì)于一個(gè)查詢(xún)語(yǔ)句有許多存取方案，它們的執(zhí)行效率不同， 僅僅進(jìn)行代數(shù)優(yōu)化是不夠的 物

31、理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢(xún)計(jì)劃 物理優(yōu)化（續(xù)）物理優(yōu)化方法基于規(guī)則的啟發(fā)式優(yōu)化啟發(fā)式規(guī)則是指那些在大多數(shù)情況下都適用，但不是在每種情況下都是適用的規(guī)則?；诖鷥r(jià)估算的優(yōu)化優(yōu)化器估算不同執(zhí)行策略的代價(jià)，并選出具有最小代價(jià)的執(zhí)行計(jì)劃。物理優(yōu)化（續(xù)）物理優(yōu)化方法（續(xù)）兩者結(jié)合的優(yōu)化方法：常常先使用啟發(fā)式規(guī)則，選取若干較優(yōu)的候選方案，減少代價(jià)估算的工作量然后分別計(jì)算這些候選方案的執(zhí)行代價(jià)，較快地選出最終的優(yōu)化方案 9.4 物理優(yōu)化9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2 基于代價(jià)的優(yōu)化 9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化1.選擇操作的啟發(fā)式規(guī)則

32、 2.連接操作的啟發(fā)式規(guī)則 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）1.選擇操作的啟發(fā)式規(guī)則對(duì)于小關(guān)系，使用全表順序掃描，即使選擇列上有索引 對(duì)于大關(guān)系，啟發(fā)式規(guī)則有： （1）對(duì)于選擇條件是“主碼值”的查詢(xún)查詢(xún)結(jié)果最多是一個(gè)元組，可以選擇主碼索引一般的關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)會(huì)自動(dòng)建立主碼索引基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）（2）對(duì)于選擇條件是“非主屬性值”的查詢(xún)，并且選擇列上有索引要估算查詢(xún)結(jié)果的元組數(shù)目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）（3）對(duì)于選擇條件是屬性上的非等值查詢(xún)或者范圍查詢(xún)，并且選擇列上有索引要估算查詢(xún)結(jié)果的元

33、組數(shù)目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）（4）對(duì)于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引，可以用索引掃描方法通過(guò)分別查找滿(mǎn)足每個(gè)條件的指針，求指針的交集通過(guò)索引查找滿(mǎn)足部分條件的元組，然后在掃描這些元組時(shí)判斷是否滿(mǎn)足剩余條件其他情況：使用全表順序掃描（5）對(duì)于用OR連接的析取選擇條件，一般使用全表順序掃描基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）2.連接操作的啟發(fā)式規(guī)則 （1）如果2個(gè)表都已經(jīng)按照連接屬性排序選用排序-合并算法 （2）如果一個(gè)表在連接屬性上有索引

34、選用索引連接算法 （3）如果上面2個(gè)規(guī)則都不適用，其中一個(gè)表較小選用Hash join算法基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）（4）可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表) 。 理由：設(shè)連接表R與S分別占用的塊數(shù)為Br與Bs連接操作使用的內(nèi)存緩沖區(qū)塊數(shù)為K分配K-1塊給外表如果R為外表，則嵌套循環(huán)法存取的塊數(shù)為Br+BrBs/(K-1)顯然應(yīng)該選塊數(shù)小的表作為外表 9.4 物理優(yōu)化9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2 基于代價(jià)的優(yōu)化 9.4.2 基于代價(jià)的優(yōu)化 啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系統(tǒng)解釋執(zhí)行

35、的系統(tǒng)，優(yōu)化開(kāi)銷(xiāo)包含在查詢(xún)總開(kāi)銷(xiāo)之中 編譯執(zhí)行的系統(tǒng)中查詢(xún)優(yōu)化和查詢(xún)執(zhí)行是分開(kāi)的可以采用精細(xì)復(fù)雜一些的基于代價(jià)的優(yōu)化方法 基于代價(jià)的優(yōu)化（續(xù)）1.統(tǒng)計(jì)信息 2.代價(jià)估算示例 3.優(yōu)化方法基于代價(jià)的優(yōu)化（續(xù)）1.統(tǒng)計(jì)信息基于代價(jià)的優(yōu)化方法要計(jì)算查詢(xún)的各種不同執(zhí)行方案的執(zhí)行代價(jià)，它與數(shù)據(jù)庫(kù)的狀態(tài)密切相關(guān) 優(yōu)化器需要的統(tǒng)計(jì)信息 （1）對(duì)每個(gè)基本表該表的元組總數(shù)(N)元組長(zhǎng)度(l)占用的塊數(shù)(B)占用的溢出塊數(shù)(BO)基于代價(jià)的優(yōu)化（續(xù)）（2）對(duì)基表的每個(gè)列該列不同值的個(gè)數(shù)(m)列最大值最小值列上是否已經(jīng)建立了索引哪種索引(B+樹(shù)索引、Hash索引、聚集索引)可以計(jì)算選擇率(f)如果不同值的分布是均勻的，f1/m如果不同值的分布不均勻，則要計(jì)算每個(gè)值的選擇率，f具有該值的元組數(shù)/N基于代價(jià)的優(yōu)化（續(xù)）（3）對(duì)索引索引的層數(shù)(L)不同索引值的個(gè)數(shù)索引的選擇基數(shù)S(有S個(gè)元組具有某個(gè)索引值)索引的葉結(jié)點(diǎn)數(shù)(Y) 基于代價(jià)的優(yōu)化（續(xù)） 2.代價(jià)估算示例 （1）全表掃描算法的代價(jià)估算公式如果基本表大小為B塊，全表掃描算法的代價(jià) costB如果選擇條件是“碼值”，那么平均搜索代價(jià) costB/2基于代價(jià)的優(yōu)化（續(xù)）（2）