第九章 關(guān)系查詢處理及優(yōu)化

數(shù)據(jù)庫系統(tǒng)概論AnIntroductiontoDatabaseSystem

第九章關(guān)系系統(tǒng)及其查詢優(yōu)化12:18:29中國人民大學(xué)信息學(xué)院

數(shù)據(jù)庫系統(tǒng)概論AnIntroductiontoDatabaseSystem第九章關(guān)系查詢處理和查詢優(yōu)化12:18:29第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.5小結(jié)12:18:29關(guān)系系統(tǒng)及其查詢優(yōu)化（續(xù)）本章目的：

RDBMS的查詢處理步驟查詢優(yōu)化的概念基本方法和技術(shù)查詢優(yōu)化分類：代數(shù)優(yōu)化物理優(yōu)化12:18:299.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實現(xiàn)查詢操作的算法示例12:18:299.1.1查詢處理步驟RDBMS查詢處理階段：

1.查詢分析2.查詢檢查3.查詢優(yōu)化4.查詢執(zhí)行

12:18:29查詢處理步驟（續(xù)）查詢處理步驟12:18:291.查詢分析對查詢語句進(jìn)行掃描、詞法分析和語法分析從查詢語句中識別出語言符號進(jìn)行語法檢查和語法分析12:18:292.查詢檢查根據(jù)數(shù)據(jù)字典對合法的查詢語句進(jìn)行語義檢查根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用戶的存取權(quán)限進(jìn)行檢查檢查通過后把SQL查詢語句轉(zhuǎn)換成等價的關(guān)系代數(shù)表達(dá)式RDBMS一般都用查詢樹(語法分析樹)來表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式把數(shù)據(jù)庫對象的外部名稱轉(zhuǎn)換為內(nèi)部表示12:18:293.查詢優(yōu)化查詢優(yōu)化：選擇一個高效執(zhí)行的查詢處理策略查詢優(yōu)化分類：代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化物理優(yōu)化：指存取路徑和底層操作算法的選擇查詢優(yōu)化方法選擇的依據(jù)：基于規(guī)則(rulebased)基于代價(costbased)基于語義(semanticbased)12:18:294.查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計劃代碼生成器(codegenerator)生成執(zhí)行查詢計劃的代碼12:18:299.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實現(xiàn)查詢操作的算法示例

12:18:299.1.2實現(xiàn)查詢操作的算法示例

一、選擇操作的實現(xiàn)二、連接操作的實現(xiàn)12:18:29一、選擇操作的實現(xiàn)［例1］Select*fromstudentwhere<條件表達(dá)式>； 考慮<條件表達(dá)式>的幾種情況：

C1：無條件；

C2：Sno＝'200215121'；

C3：Sage>20；

C4：Sdept＝'CS'ANDSage>20；

12:18:29選擇操作的實現(xiàn)（續(xù)）選擇操作典型實現(xiàn)方法：1.簡單的全表掃描方法

對查詢的基本表順序掃描，逐一檢查每個元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出適合小表，不適合大表2.索引(或散列)掃描方法

適合選擇條件中的屬性上有索引(例如B+樹索引或Hash索引)通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組12:18:29選擇操作的實現(xiàn)（續(xù)）［例1-C2］以C2為例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列碼)使用索引(或散列)得到Sno為‘200215121’

元組的指針通過元組指針在student表中檢索到該學(xué)生［例1-C3］以C3為例，Sage>20，并且Sage上有B+樹索引使用B+樹索引找到Sage＝20的索引項，以此為入口點(diǎn)在B+樹的順序集上得到Sage>20的所有元組指針通過這些元組指針到student表中檢索到所有年齡大于20的學(xué)生。

12:18:29選擇操作的實現(xiàn)（續(xù)）［例1-C4］以C4為例，Sdept＝‘CS’ANDSage>20，如果Sdept和Sage上都有索引：算法一：分別用上面兩種方法分別找到Sdept＝‘CS’的一組元組指針和Sage>20的另一組元組指針求這2組指針的交集到student表中檢索得到計算機(jī)系年齡大于20的學(xué)生算法二：找到Sdept＝‘CS’的一組元組指針，通過這些元組指針到student表中檢索對得到的元組檢查另一些選擇條件(如Sage>20)是否滿足把滿足條件的元組作為結(jié)果輸出。12:18:29二、連接操作的實現(xiàn)連接操作是查詢處理中最耗時的操作之一本節(jié)只討論等值連接(或自然連接)最常用的實現(xiàn)算法［例2］SELECT*FROMStudent，SC WHEREStudent.Sno=SC.Sno；12:18:29連接操作的實現(xiàn)（續(xù)）1.嵌套循環(huán)方法(nestedloop)2.排序-合并方法(sort-mergejoin或mergejoin)3.索引連接(indexjoin)方法4.HashJoin方法12:18:29連接操作的實現(xiàn)（續(xù)）嵌套循環(huán)方法(nestedloop)對外層循環(huán)(Student)的每一個元組(s)，檢索內(nèi)層循環(huán)(SC)中的每一個元組(sc)檢查這兩個元組在連接屬性(sno)上是否相等如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止12:18:29連接操作的實現(xiàn)（續(xù)）2.排序-合并方法(sort-mergejoin或mergejoin)

適合連接的諸表已經(jīng)排好序的情況排序－合并連接方法的步驟：如果連接的表沒有排好序，先對Student表和SC表按連接屬性Sno排序取Student表中第一個Sno，依次掃描SC表中具有相同Sno的元組12:18:29連接操作的實現(xiàn)（續(xù)）200215121200215122200215123200215124...200215121192200215121285200215121388200215122290200215122380...排序-合并連接方法示意圖12:18:29連接操作的實現(xiàn)（續(xù)）排序－合并連接方法的步驟（續(xù)）：當(dāng)掃描到Sno不相同的第一個SC元組時，返回Student表掃描它的下一個元組，再掃描SC表中具有相同Sno的元組，把它們連接起來重復(fù)上述步驟直到Student表掃描完12:18:29連接操作的實現(xiàn)（續(xù)）Student表和SC表都只要掃描一遍如果2個表原來無序，執(zhí)行時間要加上對兩個表的排序時間對于2個大表，先排序后使用sort-mergejoin方法執(zhí)行連接，總的時間一般仍會大大減少

12:18:29連接操作的實現(xiàn)（續(xù)）3.索引連接(indexjoin)方法步驟：①在SC表上建立屬性Sno的索引，如果原來沒有該索引②對Student中每一個元組，由Sno值通過SC的索引查找相應(yīng)的SC元組③把這些SC元組和Student元組連接起來循環(huán)執(zhí)行②③，直到Student表中的元組處理完為止12:18:29連接操作的實現(xiàn)（續(xù)）4.HashJoin方法

把連接屬性作為hash碼，用同一個hash函數(shù)把R和S中的元組散列到同一個hash文件中步驟：劃分階段(partitioningphase)：對包含較少元組的表(比如R)進(jìn)行一遍處理把它的元組按hash函數(shù)分散到hash表的桶中試探階段(probingphase)：也稱為連接階段(joinphase)對另一個表(S)進(jìn)行一遍處理把S的元組散列到適當(dāng)?shù)膆ash桶中把元組與桶中所有來自R并與之相匹配的元組連接起來

12:18:29連接操作的實現(xiàn)（續(xù)）上面hashjoin算法前提：假設(shè)兩個表中較小的表在第一階段后可以完全放入內(nèi)存的hash桶中以上的算法思想可以推廣到更加一般的多個表的連接算法上12:18:29第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.5小結(jié)12:18:299.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素由于關(guān)系表達(dá)式的語義級別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義，提供了執(zhí)行查詢優(yōu)化的可能性12:18:299.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述9.2.2一個實例

12:18:299.2.1查詢優(yōu)化概述關(guān)系系統(tǒng)的查詢優(yōu)化非關(guān)系系統(tǒng)12:18:29查詢優(yōu)化概述（續(xù)）查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則難以獲得這些信息(2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實際應(yīng)用中往往是不太可能的。12:18:29查詢優(yōu)化概述（續(xù)）(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)12:18:29查詢優(yōu)化概述（續(xù)）RDBMS通過某種代價模型計算出各種查詢執(zhí)行策略的執(zhí)行代價，然后選取代價最小的執(zhí)行方案集中式數(shù)據(jù)庫執(zhí)行開銷主要包括：磁盤存取塊數(shù)(I/O代價)處理機(jī)時間(CPU代價)查詢的內(nèi)存開銷I/O代價是最主要的 分布式數(shù)據(jù)庫總代價=I/O代價+CPU代價+內(nèi)存代價＋通信代價12:18:29查詢優(yōu)化概述（續(xù)）查詢優(yōu)化的總目標(biāo)：選擇有效的策略求得給定關(guān)系表達(dá)式的值使得查詢代價最小(實際上是較小)12:18:299.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述9.2.2一個實例12:18:299.2.2一個實例[例3]求選修了2號課程的學(xué)生姓名。用SQL表達(dá)：

SELECTStudent.Sname FROMStudent，SC WHEREStudent.Sno=SC.SnoAND SC.Cno=‘2’；假定學(xué)生-課程數(shù)據(jù)庫中有1000個學(xué)生記錄，10000個選課記錄其中選修2號課程的選課記錄為50個12:18:29一個實例（續(xù)）系統(tǒng)可以用多種等價的關(guān)系代數(shù)表達(dá)式來完成這一查詢Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2'

(Student×SC))Q2=πSname(σSc.Cno='2'(StudentSC))Q3=πSname(StudentσSc.Cno='2'(SC))

12:18:29一個實例（續(xù)）一、第一種情況

Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2'

Student×SC))1.計算廣義笛卡爾積把Student和SC的每個元組連接起來的做法：在內(nèi)存中盡可能多地裝入某個表(如Student表)的若干塊，留出一塊存放另一個表(如SC表)的元組。把SC中的每個元組和Student中每個元組連接，連接后的元組裝滿一塊后就寫到中間文件上從SC中讀入一塊和內(nèi)存中的Student元組連接，直到SC表處理完。再讀入若干塊Student元組，讀入一塊SC元組重復(fù)上述處理過程，直到把Student表處理完12:18:29一個實例（續(xù)）設(shè)一個塊能裝10個Student元組或100個SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為

＋=100+20×100=2100塊其中，讀Student表100塊。讀SC表20遍，每遍100塊。若每秒讀寫20塊，則總計要花105s連接后的元組數(shù)為103×104=107。設(shè)每塊能裝10個元組，則寫出這些塊要用106/20=5×104s

12:18:29一個實例（續(xù)）2.作選擇操作依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄假定內(nèi)存處理時間忽略。讀取中間文件花費(fèi)的時間(同寫中間文件一樣)需5×104s滿足條件的元組假設(shè)僅50個，均可放在內(nèi)存12:18:29一個實例（續(xù)）3.作投影操作把第2步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果第一種情況下執(zhí)行查詢的總時間≈105+2×5×104≈105s所有內(nèi)存處理時間均忽略不計12:18:29一個實例（續(xù)）二、第二種情況

Q2=πSname(σSc.Cno='2'(StudentSC))1.計算自然連接執(zhí)行自然連接，讀取Student和SC表的策略不變，總的讀取塊數(shù)仍為2100塊花費(fèi)105s自然連接的結(jié)果比第一種情況大大減少，為104個寫出這些元組時間為104/10/20=50s，為第一種情況的千分之一2.讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時間也為50s。3.把第2步結(jié)果投影輸出。第二種情況總的執(zhí)行時間≈105+50+50≈205s12:18:29一個實例（續(xù)）三、第三種情況

Q3=πSname(StudentσSc.Cno='2'(SC))1.先對SC表作選擇運(yùn)算，只需讀一遍SC表，存取100塊花費(fèi)時間為5s，因為滿足條件的元組僅50個，不必使用中間文件。2.讀取Student表，把讀入的Student元組和內(nèi)存中的SC元組作連接。也只需讀一遍Student表共100塊，花費(fèi)時間為5s。3.把連接結(jié)果投影輸出第三種情況總的執(zhí)行時間≈5+5≈10s12:18:29一個實例（續(xù)）假如SC表的Cno字段上有索引第一步就不必讀取所有的SC元組而只需讀取Cno=‘2’的那些元組(50個)存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共3～4塊若Student表在Sno上也有索引第二步也不必讀取所有的Student元組因為滿足條件的SC記錄僅50個，涉及最多50個Student記錄讀取Student表的塊數(shù)也可大大減少

總的存取時間將進(jìn)一步減少到數(shù)秒12:18:29一個實例（續(xù)）把代數(shù)表達(dá)式Q1變換為Q2、Q3，即有選擇和連接操作時，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數(shù)優(yōu)化在Q3中SC表的選擇操作算法有全表掃描和索引掃描2種方法，經(jīng)過初步估算，索引掃描方法較優(yōu)對于Student和SC表的連接，利用Student表上的索引，采用indexjoin代價也較小，這就是物理優(yōu)化12:18:29第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

9.3代數(shù)優(yōu)化

9.4物理優(yōu)化9.5小結(jié)12:18:299.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價變換規(guī)則

9.3.2查詢樹的啟發(fā)式優(yōu)化

12:18:299.3.1關(guān)系代數(shù)表達(dá)式等價變換規(guī)則代數(shù)優(yōu)化策略：通過對關(guān)系代數(shù)表達(dá)式的等價變換來提高查詢效率關(guān)系代數(shù)表達(dá)式的等價：指用相同的關(guān)系代替兩個表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的兩個關(guān)系表達(dá)式E1和E2是等價的，可記為E1≡E2

12:18:29關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）常用的等價變換規(guī)則：1.連接、笛卡爾積交換律設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有

E1×E2≡E2×E1

E1

E2≡E2

E1

E1

E2≡E2

E12.連接、笛卡爾積的結(jié)合律設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件，則有

(E1×E2)×E3≡E1×(E2×E3)(E1

E2)E3≡E1(E2

E3)(E1

E2)E3≡E1(E2

E3)12:18:29關(guān)系代數(shù)表達(dá)式等價變換規(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是選擇條件。選擇的串接律說明選擇條件可以合并。這樣一次就可檢查全部條件。12:18:29關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）5.選擇與投影操作的交換律

σF((E))≡(σF(E))

選擇條件F只涉及屬性A1，…，An。 若F中有不屬于A1，…，An的屬性B1，…，Bm則有更一般的規(guī)則：

(σF(E))≡(σF((E)))12:18:29關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）6.選擇與笛卡爾積的交換律 如果F中涉及的屬性都是E1中的屬性，則

(E1×E2)≡(E1)×E2

如果F=F1∧F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價變換規(guī)則1，4，6可推出：

(E1×E2)≡(E1)×(E2)

若F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則仍有

(E1×E2)≡((E1)×E2)

它使部分選擇在笛卡爾積前先做。12:18:29關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）7.選擇與并的分配律 設(shè)E=E1∪E2，E1，E2有相同的屬性名，則

σF(E1∪E2)≡σF(E1)∪σF(E2)8.選擇與差運(yùn)算的分配律 若E1與E2有相同的屬性名，則

σF(E1-E2)≡σF(E1)-σF(E2)9.選擇對自然連接的分配律

σF(E1

E2)≡σF(E1)σF(E2)F只涉及E1與E2的公共屬性

12:18:29關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）10.投影與笛卡爾積的分配律 設(shè)E1和E2是兩個關(guān)系表達(dá)式，A1，…，An是E1的屬性，B1，…，Bm是E2的屬性，則

(E1×E2)≡(E1)×(E2)11.投影與并的分配律 設(shè)E1和E2有相同的屬性名，則

(E1∪E2)≡(E1)∪(E2)12:18:299.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價變換規(guī)則9.3.2查詢樹的啟發(fā)式優(yōu)化12:18:299.3.2查詢樹的啟發(fā)式優(yōu)化典型的啟發(fā)式規(guī)則：1.選擇運(yùn)算應(yīng)盡可能先做。在優(yōu)化策略中這是最重要、最基本的一條2.把投影運(yùn)算和選擇運(yùn)算同時進(jìn)行如有若干投影和選擇運(yùn)算，并且它們都對同一個關(guān)系操作，則可以在掃描此關(guān)系的同時完成所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系12:18:29查詢樹的啟發(fā)式優(yōu)化（續(xù)）3.把投影同其前或其后的雙目運(yùn)算結(jié)合起來4.把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個連接運(yùn)算5.找出公共子表達(dá)式如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系并且從外存中讀入這個關(guān)系比計算該子表達(dá)式的時間少得多，則先計算一次公共子表達(dá)式并把結(jié)果寫入中間文件是合算的當(dāng)查詢的是視圖時，定義視圖的表達(dá)式就是公共子表達(dá)式的情況12:18:29查詢樹的啟發(fā)式優(yōu)化（續(xù)）遵循這些啟發(fā)式規(guī)則，應(yīng)用9.3.1的等價變換公式來優(yōu)化關(guān)系表達(dá)式的算法。 算法：關(guān)系表達(dá)式的優(yōu)化 輸入：一個關(guān)系表達(dá)式的查詢樹 輸出：優(yōu)化的查詢樹 方法：

(1)利用等價變換規(guī)則4把形如σF1∧F2∧…∧Fn(E)變換為σF1(σF2(…(σFn(E))…))。

(2)對每一個選擇，利用等價變換規(guī)則4～9盡可能把它移到樹的葉端。12:18:29查詢樹的啟發(fā)式優(yōu)化（續(xù)） (3)對每一個投影利用等價變換規(guī)則3，5，10，11中的一般形式盡可能把它移向樹的葉端。注意：等價變換規(guī)則3使一些投影消失規(guī)則5把一個投影分裂為兩個，其中一個有可能被移向樹的葉端

(4)利用等價變換規(guī)則3～5把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成12:18:29查詢樹的啟發(fā)式優(yōu)化（續(xù)）(5)把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是(σ，π運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組但當(dāng)雙目運(yùn)算是笛卡爾積(×)，而且后面不是與它組成等值連接的選擇時，則不能把選擇與這個雙目運(yùn)算組成同一組，把這些單目運(yùn)算單獨(dú)分為一組12:18:29查詢樹的啟發(fā)式優(yōu)化（續(xù)）［例4］下面給出［例3］中SQL語句的代數(shù)優(yōu)化示例。

(1)把SQL語句轉(zhuǎn)換成查詢樹，如下圖所示

查詢樹12:18:29查詢樹的啟發(fā)式優(yōu)化（續(xù)）

為了使用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān)系代數(shù)語法樹，則上面的查詢樹如下圖所示。

關(guān)系代數(shù)語法樹

12:18:29查詢樹的啟發(fā)式優(yōu)化（續(xù)）(2)對查詢樹進(jìn)行優(yōu)化利用規(guī)則4、6把選擇σSC.Cno=‘2’移到葉端，查詢樹便轉(zhuǎn)換成下圖所示的優(yōu)化的查詢樹。這就是9.2.2節(jié)中Q3的查詢樹表示優(yōu)化后的查詢樹

12:18:29第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

9.3代數(shù)優(yōu)化

9.4物理優(yōu)化9.5小結(jié)12:18:299.4物理優(yōu)化代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑對于一個查詢語句有許多存取方案，它們的執(zhí)行效率不同，僅僅進(jìn)行代數(shù)優(yōu)化是不夠的物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計劃12:18:29物理優(yōu)化（續(xù)）選擇的方法：基于規(guī)則的啟發(fā)式優(yōu)化基于代價估算的優(yōu)化兩者結(jié)合的優(yōu)化方法12:18:299.4物理優(yōu)化9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2基于代價的優(yōu)化

12:18:299.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化一、選擇操作的啟發(fā)式規(guī)則二、連接操作的啟發(fā)式規(guī)則12:18:29基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))一、選擇操作的啟發(fā)式規(guī)則: 1.對于小關(guān)系，使用全表順序掃描，即使選擇列上有索引 對于大關(guān)系，啟發(fā)式規(guī)則有：

2.對于選擇條件是主碼＝值的查詢查詢結(jié)果最多是一個元組，可以選擇主碼索引一般的RDBMS會自動建立主碼索引。

12:18:29基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))3.對于選擇條件是非主屬性＝值的查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描12:18:29基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 4.對于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描

12:18:29基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 5.對于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引則可以用［例1-C4］中介紹的索引掃描方法否則使用全表順序掃描。

6.對于用OR連接的析取選擇條件，一般使用全表順序掃描12:18:29基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))二、連接操作的啟發(fā)式規(guī)則：

1.如果2個表都已經(jīng)按照連接屬性排序選用排序-合并方法

2.如果一個表在連接屬性上有索引選用索引連接方法

3.如果上面2個規(guī)則都不適用，其中一個表較小選用Hashjoin方法

12:18:29基于啟發(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+(Br/K-1)Bs顯然應(yīng)該選塊數(shù)小的表作為外表12:18:299.4物理優(yōu)化（續(xù)）9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2基于代價的優(yōu)化12:18:299.4.2基于代價的優(yōu)化

啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系統(tǒng)解釋執(zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷之中編譯執(zhí)行的系統(tǒng)中查詢優(yōu)化和查詢執(zhí)行是分開的可以采用精細(xì)復(fù)雜一些的基于代價的優(yōu)化方法12:18:29基于代價的優(yōu)化（續(xù)）一、統(tǒng)計信息二、代價估算示例12:18:29基于代價的優(yōu)化（續(xù)）一、統(tǒng)計信息基于代價的優(yōu)化方法要計算各種操作算法的執(zhí)行代價，與數(shù)據(jù)庫的狀態(tài)密切相關(guān)數(shù)據(jù)字典中存儲的優(yōu)化器需要的統(tǒng)計信息：1.對每個基本表該表的元組總數(shù)(N)元組長度(l)占用的塊數(shù)(B)占用的溢出塊數(shù)(BO)12:18:29基于代價的優(yōu)化（續(xù)） 2.對基表的每個列該列不同值的個數(shù)(m)選擇率(f)如果不同值的分布是均勻的，f＝1/m如果不同值的分布不均勻，則每個值的選擇率＝具有該值的元組數(shù)/N該列最大值該列最小值該列上是否已經(jīng)建立了索引索引類型(B+樹索引、Hash索引、聚集索引)

12:18:29基于代價的優(yōu)化（續(xù)）3.對索引(如B+樹索引)索引