數(shù)據(jù)庫(kù)原理 第4章 關(guān)系查詢處理和查詢優(yōu)化

第四章關(guān)系查詢處理和查詢優(yōu)化1本章目的：

掌握RDBMS的查詢處理步驟理解查詢優(yōu)化的概念了解基本方法和技術(shù)2本章主要內(nèi)容4.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理

4.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化4.3代數(shù)優(yōu)化34.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理4.1.1查詢處理步驟4.1.2實(shí)現(xiàn)查詢操作的算法示例44.1.1查詢處理步驟RDBMS查詢處理階段：

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

5查詢處理步驟（續(xù)）查詢語(yǔ)句詞法分析語(yǔ)法分析語(yǔ)義分析符號(hào)名轉(zhuǎn)換安全性檢查完整性檢查代數(shù)優(yōu)化物理優(yōu)化等查詢樹(shù)（querytree）執(zhí)行策略描述代碼生成查詢計(jì)劃的執(zhí)行代碼查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行數(shù)據(jù)庫(kù)數(shù)據(jù)字典61.查詢分析對(duì)查詢語(yǔ)句進(jìn)行掃描、詞法分析和語(yǔ)法分析從查詢語(yǔ)句中識(shí)別出語(yǔ)言符號(hào)進(jìn)行語(yǔ)法檢查和語(yǔ)法分析72.查詢檢查根據(jù)數(shù)據(jù)字典對(duì)合法的查詢語(yǔ)句進(jìn)行語(yǔ)義檢查根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對(duì)用戶的存取權(quán)限進(jìn)行檢查

檢查通過(guò)后把SQL查詢語(yǔ)句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式RDBMS一般都用查詢樹(shù)(語(yǔ)法分析樹(shù))來(lái)表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式把數(shù)據(jù)庫(kù)對(duì)象的外部名稱轉(zhuǎn)換為內(nèi)部表示

83.查詢優(yōu)化查詢優(yōu)化：選擇一個(gè)高效執(zhí)行的查詢處理策略查詢優(yōu)化分類：代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化物理優(yōu)化：指存取路徑和底層操作算法的選擇查詢優(yōu)化方法選擇的依據(jù)：基于規(guī)則(rulebased)基于代價(jià)(costbased)基于語(yǔ)義(semanticbased)94.查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計(jì)劃代碼生成器(codegenerator)生成執(zhí)行查詢計(jì)劃的代碼104.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理4.1.1查詢處理步驟4.1.2實(shí)現(xiàn)查詢操作的算法示例

114.1.2實(shí)現(xiàn)查詢操作的算法示例

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

C1：無(wú)條件； C2：Sno＝'200215121'； C3：Sage>20； C4：Sdept＝'CS'ANDSage>20；

13選擇操作典型實(shí)現(xiàn)方法：1.簡(jiǎn)單的全表掃描方法

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

適合選擇條件中的屬性上有索引(例如B+樹(shù)索引或Hash索引)通過(guò)索引先找到滿足條件的元組主碼或元組指針，再通過(guò)元組指針直接在查詢的基本表中找到元組14［例1-C2］以C2為例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列碼)使用索引(或散列)得到Sno為‘200215121’元組的指針通過(guò)元組指針在student表中檢索到該學(xué)生［例1-C3］以C3為例，Sage>20，并且Sage上有B+樹(shù)索引使用B+樹(shù)索引找到Sage＝20的索引項(xiàng)，以此為入口點(diǎn)在B+樹(shù)的順序集上得到Sage>20的所有元組指針通過(guò)這些元組指針到student表中檢索到所有年齡大于20的學(xué)生。

15［例1-C4］以C4為例，Sdept＝‘CS’ANDSage>20，如果Sdept和Sage上都有索引：算法一：分別用上面兩種方法分別找到Sdept＝‘CS’的一組元組指針和Sage>20的另一組元組指針求這2組指針的交集到student表中檢索得到計(jì)算機(jī)系年齡大于20的學(xué)生算法二：找到Sdept＝‘CS’的一組元組指針，通過(guò)這些元組指針到student表中檢索對(duì)得到的元組檢查另一些選擇條件(如Sage>20)是否滿足把滿足條件的元組作為結(jié)果輸出。

16二、連接操作的實(shí)現(xiàn)連接操作是查詢處理中最耗時(shí)的操作之一本節(jié)只討論等值連接(或自然連接)最常用的實(shí)現(xiàn)算法［例2］SELECT*FROMStudent，SC WHEREStudent.Sno=SC.Sno；17連接操作的實(shí)現(xiàn)方法1.嵌套循環(huán)方法(nestedloop)2.排序-合并方法(sort-mergejoin或mergejoin)3.索引連接(indexjoin)方法4.HashJoin方法18嵌套循環(huán)方法(nestedloop)對(duì)外層循環(huán)(Student)的每一個(gè)元組(s)，檢索內(nèi)層循環(huán)(SC)中的每一個(gè)元組(sc)檢查這兩個(gè)元組在連接屬性(sno)上是否相等如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止192.排序-合并方法(sort-mergejoin或mergejoin)

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

233.索引連接(indexjoin)方法

①在SC表上建立屬性Sno的索引，如果原來(lái)沒(méi)有該索引②對(duì)Student中每一個(gè)元組，由Sno值通過(guò)SC的索引查找相應(yīng)的SC元組③把這些SC元組和Student元組連接起來(lái)循環(huán)執(zhí)行②③，直到Student表中的元組處理完為止244.HashJoin方法

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

25上面hashjoin算法前提：假設(shè)兩個(gè)表中較小的表在第一階段后可以完全放入內(nèi)存的hash桶中以上的算法思想可以推廣到更加一般的多個(gè)表的連接算法上26本章主要內(nèi)容4.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理4.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化4.3代數(shù)優(yōu)化274.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化查詢優(yōu)化在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中有著非常重要的地位關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素由于關(guān)系表達(dá)式的語(yǔ)義級(jí)別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義，提供了執(zhí)行查詢優(yōu)化的可能性284.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化4.2.1查詢優(yōu)化概述4.2.2一個(gè)實(shí)例29查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好

(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫(xiě)程序，而重寫(xiě)程序在實(shí)際應(yīng)用中往往是不太可能的。4.2.1查詢優(yōu)化概述30(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)31RDBMS通過(guò)某種代價(jià)模型計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案集中式數(shù)據(jù)庫(kù)執(zhí)行開(kāi)銷(xiāo)主要包括：磁盤(pán)存取塊數(shù)(I/O代價(jià))處理機(jī)時(shí)間(CPU代價(jià))查詢的內(nèi)存開(kāi)銷(xiāo)I/O代價(jià)是最主要的 分布式數(shù)據(jù)庫(kù)總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)+通信代價(jià)

32查詢優(yōu)化的總目標(biāo)：選擇有效的策略求得給定關(guān)系表達(dá)式的值使得查詢代價(jià)最小(實(shí)際上是較小)334.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化4.2.1查詢優(yōu)化概述4.2.2一個(gè)實(shí)例344.2.2一個(gè)實(shí)例[例3]求選修了2號(hào)課程的學(xué)生姓名。用SQL表達(dá)：

SELECTSname FROMStudent，SC WHEREStudent.Sno=SC.SnoAND SC.Cno=‘2’；假定學(xué)生-課程數(shù)據(jù)庫(kù)中有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄其中選修2號(hào)課程的選課記錄為50個(gè)35系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來(lái)完成這一查詢：Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2'

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

σCno='2'(SC))

36一、第一種情況

Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2'(Student×SC))1.計(jì)算廣義笛卡爾積把Student和SC的每個(gè)元組連接起來(lái)的做法：在內(nèi)存中盡可能多地裝入某個(gè)表(如Student表)的若干塊，留出一塊存放另一個(gè)表(如SC表)的元組。把SC中的每個(gè)元組和Student中每個(gè)元組連接，連接后的元組裝滿一塊后就寫(xiě)到中間文件上從SC中讀入一塊和內(nèi)存中的Student元組連接，直到SC表處理完。再讀入若干塊Student元組，讀入一塊SC元組重復(fù)上述處理過(guò)程，直到把Student表處理完37設(shè)一個(gè)塊能裝10個(gè)Student元組或100個(gè)SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為

1000/10＋1000/(10×5)×10000/100

=100+20×100=2100塊其中，讀Student表100塊。讀SC表20遍，每遍100塊。若每秒讀寫(xiě)20塊，則總計(jì)要花105s連接后的元組數(shù)為