《數(shù)據(jù)庫原理與應(yīng)用》第10章數(shù)據(jù)庫查詢優(yōu)化1第十章內(nèi)容提要關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理10.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化10.2代數(shù)優(yōu)化10.32邏

物理優(yōu)化輯數(shù)據(jù)10.4內(nèi)容導(dǎo)學(xué)3學(xué)習(xí)目標(biāo)掌握數(shù)據(jù)庫系統(tǒng)的基本概念了解數(shù)據(jù)管理技術(shù)的發(fā)展過程理解數(shù)據(jù)庫系統(tǒng)的特點和組成學(xué)習(xí)數(shù)據(jù)獨立性內(nèi)容學(xué)習(xí)重點查詢優(yōu)化的處理步驟查詢優(yōu)化的必要性用等價變換規(guī)則將SQL語句轉(zhuǎn)換為優(yōu)化的查詢樹存取路徑的優(yōu)化方法思政導(dǎo)學(xué)4關(guān)鍵詞：查詢優(yōu)化，代數(shù)優(yōu)化，物理優(yōu)化，等價變換規(guī)則。內(nèi)容要意：查詢處理是關(guān)系數(shù)據(jù)庫管理系統(tǒng)的核心，而查詢優(yōu)化又是查詢處理的關(guān)鍵技術(shù)，同時也是關(guān)系數(shù)據(jù)庫系統(tǒng)的優(yōu)點所在，它的總目標(biāo)是選擇有效的策略，得到給定的SQL查詢結(jié)果，使得查詢代價最小，達到優(yōu)化系統(tǒng)性能的目標(biāo)。查詢優(yōu)化可分為代數(shù)優(yōu)化和物理優(yōu)化，代數(shù)優(yōu)化是按照等價變換規(guī)則，改變代數(shù)表達式中操作的次序和組合，使查詢執(zhí)行更高效；物理優(yōu)化是指存取路徑和底層操作算法的選擇。思政點播：結(jié)合具體實例，通過介紹查詢優(yōu)化的步驟及優(yōu)化處理過程，使學(xué)生具有提高效率、節(jié)約資源的意識，培養(yǎng)學(xué)生精益求精的精神。思政目標(biāo)：通過對查詢實例的具體優(yōu)化過程的講解，使學(xué)生具有提高工作效率的意識，培養(yǎng)學(xué)生精益求精的工匠精神；培養(yǎng)學(xué)生問題意識和提升信息素養(yǎng)。10.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理10.1.1查詢處理步驟10.1.2實現(xiàn)查詢操作的算法示例10.1.1查詢處理步驟關(guān)系數(shù)據(jù)庫管理系統(tǒng)查詢處理階段：1.查詢分析2.查詢檢查3.查詢優(yōu)化4.查詢執(zhí)行查詢處理步驟（續(xù)）1.查詢分析查詢分析的任務(wù)：對查詢語句進行掃描、詞法分析和語法分析詞法分析：從查詢語句中識別出正確的語言符號語法分析：進行語法檢查

2.查詢檢查查詢檢查的任務(wù)合法權(quán)檢查視圖轉(zhuǎn)換安全性檢查完整性初步檢查根據(jù)數(shù)據(jù)字典中有關(guān)的模式定義檢查語句中的數(shù)據(jù)庫對象，如關(guān)系名、屬性名是否存在和有效如果是對視圖的操作，則要用視圖消解方法把對視圖的操作轉(zhuǎn)換成對基本表的操作

2.查詢檢查根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用戶的存取權(quán)限進行檢查檢查通過后把SQL查詢語句轉(zhuǎn)換成內(nèi)部表示，即等價的關(guān)系代數(shù)表達式。關(guān)系數(shù)據(jù)庫管理系統(tǒng)一般都用查詢樹，也稱為語法分析樹來表示擴展的關(guān)系代數(shù)表達式。

3.查詢優(yōu)化查詢優(yōu)化：選擇一個高效執(zhí)行的查詢處理策略查詢優(yōu)化分類代數(shù)優(yōu)化/邏輯優(yōu)化：指關(guān)系代數(shù)表達式的優(yōu)化物理優(yōu)化：指存取路徑和底層操作算法的選擇查詢優(yōu)化的選擇依據(jù)基于規(guī)則(rulebased)基于代價(costbased)基于語義(semanticbased)

4.查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢執(zhí)行計劃代碼生成器(codegenerator)生成執(zhí)行查詢計劃的代碼兩種執(zhí)行方法自頂向下自底向上10.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理10.1.1查詢處理步驟10.1.2實現(xiàn)查詢操作的算法示例10.1.2實現(xiàn)查詢操作的算法示例選擇操作的實現(xiàn)連接操作的實現(xiàn)1.選擇操作的實現(xiàn)選擇操作典型實現(xiàn)方法：（1）全表掃描方法(TableScan)對查詢的基本表順序掃描，逐一檢查每個元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出適合小表，不適合大表（2）索引掃描方法(IndexScan)適合于選擇條件中的屬性上有索引(例如B+樹索引或Hash索引)通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組選擇操作的實現(xiàn)（續(xù)）[例10.1]SELECT*FROMStudentWHERE<條件表達式>

考慮<條件表達式>的幾種情況：

C1：無條件；

C2：Sno＝'S202301012'；

C3：Sage>20；

C4："Ssex=‘男’ANDSage>20；

選擇操作的實現(xiàn)（續(xù)）全表掃描算法假設(shè)可以使用的內(nèi)存為M塊，全表掃描算法思想：按照物理次序讀Student的M塊到內(nèi)存檢查內(nèi)存的每個元組t，如果滿足選擇條件，則輸出t如果student還有其他塊未被處理，重復(fù)①和②選擇操作的實現(xiàn)（續(xù)）索引掃描算法[例10.1-C2]SELECT*FROMStudentWHERESno='S202301012'假設(shè)Sno上有索引(或Sno是散列碼)算法：使用索引(或散列)得到Sno為‘S202301012’元組的指針通過元組指針在Student表中檢索到該學(xué)生選擇操作的實現(xiàn)（續(xù)）[例10.1-C3]SELECT*FROMStudentWHERESage>20假設(shè)Sage上有B+樹索引算法：使用B+樹索引找到Sage=20的索引項，以此為入口點在B+樹的順序集上得到Sage>20的所有元組指針通過這些元組指針到student表中檢索到所有年齡大于20的學(xué)生。選擇操作的實現(xiàn)（續(xù)）[例10.1-C4]SELECT*FROMStudentWHERESsex='男’ANDSage>20;假設(shè)Sdept和Sage上都有索引算法一：分別用索引掃描找到Ssex='男’的一組元組指針和Sage>20的另一組元組指針求這兩組指針的交集到Student表中檢索得到年齡大于20的男學(xué)生的信息選擇操作的實現(xiàn)（續(xù)）算法二：找到Ssex='男’的一組元組指針，通過這些元組指針到Student表中檢索并對得到的元組檢查另一些選擇條件(如Sage>20)是否滿足把滿足條件的元組作為結(jié)果輸出。2.連接操作的實現(xiàn)連接操作是查詢處理中最耗時的操作之一本節(jié)只討論等值連接(或自然連接)最常用的實現(xiàn)算法[例10.2]SELECT*FROMStudent,SP WHEREStudent.Sno=SP.Sno;連接操作的實現(xiàn)（續(xù)）（1）嵌套循環(huán)算法（2）排序-合并算法（3）索引連接算法（4）哈希連接算法連接操作的實現(xiàn)（續(xù)）（1）嵌套循環(huán)算法對外層循環(huán)(Student表)的每一個元組，檢索內(nèi)層循環(huán)(SP表)中的每一個元組檢查這兩個元組在連接屬性(Sno)上是否相等如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止。連接操作的實現(xiàn)（續(xù)）（2）排序-合并算法如果連接的表沒有排好序，先對Student表和SP表按連接屬性Sno排序取Student表中第一個Sno，依次掃描SP表中具有相同Sno的元組當(dāng)掃描到Sno不相同的第一個SP元組時，返回Student表掃描它的下一個元組，再掃描SP表中具有相同Sno的元組，把它們連接起來重復(fù)上述步驟直到Student表掃描完連接操作的實現(xiàn)（續(xù)）圖10.2排序-合并連接方法示意圖連接操作的實現(xiàn)（續(xù)）Student表和SP表都只要掃描一遍如果兩個表原來無序，執(zhí)行時間要加上對兩個表的排序時間對于大表，先排序后使用排序-合并連接算法執(zhí)行連接，總的時間一般仍會減少連接操作的實現(xiàn)（續(xù)）（3）索引連接算法步驟：①在SP表上已經(jīng)建立屬性Sno的索引。②對Student中每一個元組，由Sno值通過SP的索引查找相應(yīng)的SP元組。③把這些SP元組和Student元組連接起來循環(huán)執(zhí)行②③，直到Student表中的元組處理完為止連接操作的實現(xiàn)（續(xù)）（4）哈希連接算法把連接屬性作為hash碼，用同一個hash函數(shù)把Student表和SP表中的元組散列到hash表中。第一步創(chuàng)建階段，即創(chuàng)建hash表對包含較少元組的表(如Student表)進行一遍處理把它的元組按hash函數(shù)分散到hash表的桶中第二步連接階段對另一個表(SC表)進行一遍處理把SP表的元組也按同一個hash函數(shù)（hash碼是連接屬性）進行散列把SP元組與桶中來自Student表并與之相匹配的元組連接連接操作的實現(xiàn)（續(xù)）上面哈希連接算法前提：假設(shè)兩個表中較小的表在第一階段后可以完全放入內(nèi)存的hash桶中第十章

關(guān)系查詢處理和查詢優(yōu)化10.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理10.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化10.3代數(shù)優(yōu)化10.4物理優(yōu)化10.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位關(guān)系查詢優(yōu)化是影響關(guān)系數(shù)據(jù)庫管理系統(tǒng)性能的關(guān)鍵因素由于關(guān)系表達式的語義級別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達式中分析查詢語義，提供了執(zhí)行查詢優(yōu)化的可能性10.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化10.2.1查詢優(yōu)化概述10.2.2一個實例10.2.1查詢優(yōu)化概述關(guān)系系統(tǒng)的查詢優(yōu)化是關(guān)系數(shù)據(jù)庫管理系統(tǒng)實現(xiàn)的關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)的優(yōu)點所在減輕了用戶選擇存取路徑的負擔(dān)，用戶只要提出“干什么”，而不必指出“怎么干”。查詢優(yōu)化概述（續(xù)）非關(guān)系系統(tǒng)用戶使用過程化的語言表達查詢要求，執(zhí)行何種記錄級的操作，以及操作的序列是由用戶來決定的用戶必須了解存取路徑，系統(tǒng)要提供用戶選擇存取路徑的手段，查詢效率由用戶的存取策略決定如果用戶做了不當(dāng)?shù)倪x擇，系統(tǒng)是無法對此加以改進的查詢優(yōu)化概述查詢優(yōu)化的優(yōu)點用戶不必考慮如何最好地表達查詢以獲得較好的效率系統(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)用中往往是不太可能的。查詢優(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ù)。查詢優(yōu)化概述（續(xù)）關(guān)系數(shù)據(jù)庫管理系統(tǒng)通過某種代價模型計算出各種查詢執(zhí)行策略的執(zhí)行代價，然后選取代價最小的執(zhí)行方案集中式數(shù)據(jù)庫執(zhí)行開銷主要包括磁盤存取塊數(shù)(I/O代價)處理機時間(CPU代價)查詢的內(nèi)存開銷I/O代價是最主要的 分布式數(shù)據(jù)庫總代價=I/O代價+CPU代價+內(nèi)存代價＋通信代價查詢優(yōu)化概述（續(xù)）查詢優(yōu)化的總目標(biāo)選擇有效的策略求得給定關(guān)系表達式的值使得查詢代價最小(實際上是較小)10.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化10.2.1查詢優(yōu)化概述10.2.2查詢優(yōu)化實例10.2.2查詢優(yōu)化實例一個關(guān)系查詢可以對應(yīng)不同的執(zhí)行方案，其效率可能相差非常大。[例10.3查詢參與了P1002號項目的學(xué)生姓名。用SQL表達：

SELECTStudent.Sname FROMStudent,SP WHEREStudent.Sno=SP.SnoAND SP.Pno=’P1002’假定學(xué)生-課程數(shù)據(jù)庫中有1000個學(xué)生記錄，5000個SP記錄參與P1002號項目的記錄為50個。查詢優(yōu)化實例（續(xù)）可以用多種等價的關(guān)系代數(shù)表達式來完成這一查詢Q1=πSname(σStudent.Sno=SP.Sno∧SP.Pno=‘P1002'(Student×SP))Q2=πSname(σSP.Pno=‘P1002'(StudentSP))Q3=πSname(StudentσSP.Pno=‘P1002’(SP))

查詢優(yōu)化實例（續(xù)）1.第一種情況Q1=πSname(σStudent.Sno=SP.Sno∧SP.Pno=‘P1002'(Student×SP))查詢優(yōu)化實例（續(xù)）（1）計算廣義笛卡爾積算法：在內(nèi)存中盡可能多地裝入某個表(如Student表)的若干塊，留出一塊存放另一個表(如SP表)的元組。把SP中的每個元組和Student中每個元組連接，連接后的元組裝滿一塊后就寫到中間文件上從SP中讀入一塊和內(nèi)存中的Student元組連接，直到SP表處理完。再讀入若干塊Student元組，讀入一塊SP元組重復(fù)上述處理過程，直到把Student表處理完查詢優(yōu)化實例（續(xù)）

（2）作選擇操作依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄假定內(nèi)存處理時間忽略。讀取中間文件花費的時間(同寫中間文件一樣)需讀入106塊。若滿足條件的元組假設(shè)僅50個，均可放在內(nèi)存。查詢優(yōu)化實例（續(xù)）（3）作投影操作把第（2）步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果第一種情況下執(zhí)行查詢的總讀寫數(shù)據(jù)塊=2100+106+106查詢優(yōu)化實例（續(xù)）2.第二種情況

Q2=πSname(σSP.Pno=‘P1002'(StudentSP))（1）計算自然連接執(zhí)行自然連接，讀取Student和SP表的策略不變，總的讀取塊數(shù)仍為2100塊自然連接的結(jié)果比第一種情況大大減少，為5X103個元組寫出數(shù)據(jù)塊=103

塊

查詢優(yōu)化實例（續(xù)）2.第二種情況（續(xù)）（2）讀取中間文件塊，執(zhí)行選擇運算，讀取的數(shù)據(jù)塊=103

塊（3）把第2步結(jié)果投影輸出。第二種情況下執(zhí)行查詢的總讀寫數(shù)據(jù)塊=2100+103+103查詢優(yōu)化實例（續(xù)）3.第三種情況Q3=πSname(StudentσSP.Pno=‘P1002’(SP))（1）先對SP表作選擇運算，只需讀一遍SP表，存100塊，因為滿足條件的元組僅50個，不必使用中間文件。（2）讀取Student表，把讀入的Student元組和內(nèi)存的SP元組作連接。也只需讀一遍Student表共100塊。（3）把連接結(jié)果投影輸出

查詢優(yōu)化實例（續(xù)）3.第三種情況（續(xù)）第三種情況總的讀寫數(shù)據(jù)塊=100+100查詢優(yōu)化實例（續(xù)）假如SP表的Pno字段上有索引第一步就不必讀取所有的SP元組而只需讀取Pno=‘P1002’的那些元組(50個)存取的索引塊和SP中滿足條件的數(shù)據(jù)塊大約總共3～4塊若Student表在Sno上也有索引不必讀取所有的Student元組因為滿足條件的SP記錄僅50個，涉及最多50個Student記錄讀取Student表的塊數(shù)也可大大減少查詢優(yōu)化實例（續(xù)）把代數(shù)表達式Q1變換為Q2、Q3Q1=πSname(σStudent.Sno=SP.Sno∧SP.Pno=‘P1002'(Student×SP))Q2=πSname(σSP.Pno=‘P1002'(StudentSP))Q3=πSname(StudentσSP.Pno=‘P1002’(SP))有選擇和連接操作時，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數(shù)優(yōu)化

查詢優(yōu)化實例（續(xù)）實例:小結(jié)在Q3中SP表的選擇操作算法有全表掃描或索引掃描，經(jīng)過初步估算，索引掃描方法較優(yōu)。對于Student和SP表的連接，利用Student表上的索引，采用索引連接代價也較小，這就是物理優(yōu)化。第十章

關(guān)系查詢處理和查詢優(yōu)化10.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理10.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化10.3代數(shù)優(yōu)化10.4物理優(yōu)化10.3代數(shù)優(yōu)化10.3.1關(guān)系代數(shù)表達式等價變換規(guī)則10.3.2查詢樹的啟發(fā)式優(yōu)化10.3.1關(guān)系代數(shù)表達式等價變換規(guī)則代數(shù)優(yōu)化策略：通過對關(guān)系代數(shù)表達式的等價變換來提高查詢效率關(guān)系代數(shù)表達式的等價：指用相同的關(guān)系代替兩個表達式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的兩個關(guān)系表達式E1和E2是等價的，可記為E1≡E2

*關(guān)系代數(shù)表達式等價變換規(guī)則（續(xù)）

*

關(guān)系代數(shù)表達式等價變換規(guī)則（續(xù)）*

關(guān)系代數(shù)表達式等價變換規(guī)則（續(xù)）*

關(guān)系代數(shù)表達式等價變換規(guī)則（續(xù)）*關(guān)系代數(shù)表達式等價變換規(guī)則（續(xù)）

*關(guān)系代數(shù)表達式等價變換規(guī)則（續(xù)）

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

算法：關(guān)系表達式的優(yōu)化

輸入：一個關(guān)系表達式的查詢樹

輸出：優(yōu)化的查詢樹 方法： （1）利用等價變換規(guī)則4把形如σF1∧F2∧…∧Fn(E)變換為

σF1(σF2(…(σFn(E))…))。 （2）對每一個選擇，利用等價變換規(guī)則4～9盡可能把它移到樹的葉端。

規(guī)則4：合并或分解選擇運算規(guī)則5-9：選擇運算與其他運算交換規(guī)則4:選擇的串接定律

((E))≡(E)*查詢樹的啟發(fā)式優(yōu)化（續(xù)）

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

（5）把上述得到的語法樹的內(nèi)節(jié)點分組。每一雙目運算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是(σ，π運算)。如果其后代直到葉子全是單目運算，則也將它們并入該組。但當(dāng)雙目運算是笛卡爾積(×)，而且后面不是與它組成等值連接的選擇時，則不能把選擇與這個雙目運算組成同一組。

查詢樹的啟發(fā)式優(yōu)化（續(xù)）[例10.4]下面給出[例10.3]中SQL語句的代數(shù)優(yōu)化示例（1）把SQL語句轉(zhuǎn)換成查詢樹，如下圖所示

圖10.3查詢樹圖查詢樹的啟發(fā)式優(yōu)化（續(xù)）為了使用關(guān)系代數(shù)表達式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān)系代數(shù)語法樹，則上面的查詢樹如圖10.4所示。

圖10.4關(guān)系代數(shù)語法樹圖查詢樹的啟發(fā)式優(yōu)化（續(xù)）（2）對查詢樹進行優(yōu)化利用規(guī)則4、6把選擇σSP.Pno=‘P1002’移到葉端，圖10.4查詢樹便轉(zhuǎn)換成下圖優(yōu)化的查詢樹。這就是10.2.2節(jié)中Q3的查詢樹表示。圖10.5優(yōu)化后的查詢樹第十章

關(guān)系查詢處理和查詢優(yōu)化10.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理10.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化10.3代數(shù)優(yōu)化10.4物理優(yōu)化10.4物理優(yōu)化代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑對于一個查詢語句有許多存取方案，它們的執(zhí)行效率不同，僅僅進行代數(shù)優(yōu)化是不夠的物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計劃物理優(yōu)化（續(xù)）物理優(yōu)化方法基于規(guī)則的啟發(fā)式優(yōu)化啟發(fā)式規(guī)則是指那些在大多數(shù)情況下都適用，但不是在每種情況下都是適用的規(guī)則?；诖鷥r估算的優(yōu)化優(yōu)化器估算不同執(zhí)行策略的代價，并選出具有最小代價的執(zhí)行計劃。物理優(yōu)化（續(xù)）物理優(yōu)化方法（續(xù)）兩者結(jié)合的優(yōu)化方法：常常先使用啟發(fā)式規(guī)則，選取若干較優(yōu)的候選方案，減少代價估算的工作量然后分別計算這些候選方案的執(zhí)行代價，較快地選出最終的優(yōu)化方案10.4物理優(yōu)化10.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化10.4.2基于代價的優(yōu)化10.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化1.選擇操作的啟發(fā)式規(guī)則2.連接操作的啟發(fā)式規(guī)則基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）1.選擇操作的啟發(fā)式規(guī)則對于小關(guān)系，使用全表順序掃描，即使選擇列上有索引對于大關(guān)系，啟發(fā)式規(guī)則有：（1）對于選擇條件是“主碼＝值”的查詢查詢結(jié)果最多是一個元組，可以選擇主碼索引一般的關(guān)系數(shù)據(jù)庫管理系統(tǒng)會自動建立主碼索引基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）（2）對于選擇條件是“非主屬性＝值”的查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）（3）對于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）（4）對于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引，可以用索引掃描方法通過分別查找滿足每個條件的指針，求指針的交集通過索引查找滿足部分條件的元組，然后在掃描這些元組時判斷是否滿足剩余條件其他情況：使用全表順序掃描（5）對于用OR連接的析取選擇條件，一般使用全表順序掃描基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化（續(xù)）2.連接操作的啟發(fā)式規(guī)則（1）如果2個表都已經(jīng)按照連接屬性排序選用排序-合并算法（2）如果一個表在連接屬性上有索引選用索引連接算法（3）如果上面2個規(guī)則都不適用，其中一個表較小選用哈希連接算法基于啟發(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ù)小的表作為外表10.4物理優(yōu)化10.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化10.4.2基于代價的優(yōu)化10.4.2基于代價的優(yōu)化啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系統(tǒng)解釋執(zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷之中編譯執(zhí)行的系統(tǒng)中查詢優(yōu)化和查詢執(zhí)行是分開的可以采用精細復(fù)雜一些的基于代價的優(yōu)化方法基于代價的優(yōu)化（續(xù)）1.統(tǒng)計信息2.代價估算示例3.優(yōu)化方法基于代價的優(yōu)化（續(xù)）1.統(tǒng)計信息基于代價的優(yōu)化方法要計算查詢的各種不同執(zhí)行方案的執(zhí)行代價，它與數(shù)據(jù)庫的狀態(tài)密切相關(guān)優(yōu)化器需要的統(tǒng)計信息（1）對每個基本表該表的元組總數(shù)(N)元組長度(A)占用的塊數(shù)(B)占用的溢出塊數(shù)(BO)基于代價的優(yōu)化（續(xù)）（2）對基表的每個列該列不同值的個數(shù)(m)列最大值最小值列上是否已經(jīng)建立了索引哪種索引(B+樹索引、Hash索引、聚集索引)可以計算選擇率(f)如果不同值的分布是均勻的，f＝1/m如果不同值的分布不均勻，則要計算每個值的選擇率，f＝具有該值的元組數(shù)/N基于代價的優(yōu)化（續(xù)）（3）對索引索引的層數(shù)(L)不同索引值的個數(shù)索引的選擇基數(shù)S(有S個元組具有某個索引值)索引的葉結(jié)點數(shù)(Y)基于代價的優(yōu)化（續(xù)）2.代價估算示例（1）全表掃描算法的代價估算公式如果基本表大小為B塊，全表掃描算法的代價cost＝B如果選擇條件是“碼＝值”，那么平均搜索代價cost＝B/2基于代價的優(yōu)化（續(xù)）（2）索引掃描算法的代價估算公式如果選擇條件是“碼＝值”則采用該表的主索引若為B+樹，層數(shù)為L，需要存取B+樹中從根結(jié)點到葉結(jié)點L塊，再加上基本表中該元組所在的那一塊，所以cost=L+1基于代價的優(yōu)化（續(xù)）（2）索引掃描算法的代價估算公式（續(xù)）如果選擇條件涉及非碼屬性若為B+樹索引，選擇條件是相等比較，S是索引的選擇基數(shù)(有S個元組滿足條件)滿足條件的元組可能會保存在不同的塊上，所以(最壞的情況)cost=L+S基于代價的優(yōu)化（續(xù)）（2）索引掃描算法的代價估算公式（續(xù)）如果比較條件是＞，＞＝，＜，＜＝操作假設(shè)有一半的元組滿足條件就要存取一半的葉結(jié)點通過索引訪問一半的表存儲塊cost=L+Y/2+B/2如果可以獲得更準(zhǔn)確的選擇