第九章關(guān)系的查詢及優(yōu)化_第1頁(yè)
第九章關(guān)系的查詢及優(yōu)化_第2頁(yè)
第九章關(guān)系的查詢及優(yōu)化_第3頁(yè)
第九章關(guān)系的查詢及優(yōu)化_第4頁(yè)
第九章關(guān)系的查詢及優(yōu)化_第5頁(yè)
已閱讀5頁(yè),還剩70頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第九章關(guān)系查詢處理和查詢優(yōu)化關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化代數(shù)優(yōu)化物理優(yōu)化第九章關(guān)系系統(tǒng)及其優(yōu)化查詢本章介紹關(guān)系數(shù)據(jù)庫(kù)的查詢優(yōu)化技術(shù)。為此首先介紹RDBMS的查詢處理步驟,然后介紹詢優(yōu)化技術(shù)。查詢優(yōu)化一般可分為代數(shù)優(yōu)化和物理優(yōu)化。代數(shù)優(yōu)化是指關(guān)系代數(shù)表達(dá)式的優(yōu)化;物理優(yōu)化則是指存取路徑和底層操作算法的選擇,所以本章講解了實(shí)現(xiàn)查詢操作的主要算法。本章的目的是便讀者初步了解RDBMS查詢處理的基本步驟,查詢優(yōu)化的概念、基本方法和技術(shù),為數(shù)據(jù)庫(kù)應(yīng)用開發(fā)中利用查詢優(yōu)化技術(shù)提高查詢效率和系統(tǒng)性能打下基礎(chǔ)。查詢處理的任務(wù)是把用戶提交給RDBMS的查詢語(yǔ)句轉(zhuǎn)換為高效的執(zhí)行計(jì)劃。9.1.1查詢處理步驟RDBMS查詢處理可以分為4個(gè)階段:查詢分析、查詢檢查、查詢優(yōu)化和查詢執(zhí)行,如圖9.1所示。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理1、查詢分析首先,對(duì)查詢語(yǔ)句進(jìn)行掃描、詞法分析和語(yǔ)法分析。從查詢語(yǔ)句中識(shí)別出語(yǔ)言符號(hào),如SQL關(guān)鍵字、屬性名和關(guān)系名等,進(jìn)行語(yǔ)法檢查和語(yǔ)法分析,即判斷查詢語(yǔ)句是否符合SQL語(yǔ)法規(guī)則。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理2、查詢檢查根據(jù)數(shù)據(jù)字典對(duì)合法的查詢語(yǔ)句進(jìn)行語(yǔ)義檢查,即檢查語(yǔ)句中的數(shù)據(jù)庫(kù)對(duì)象,如屬性名、關(guān)系名,是否存在和是否有效。還要根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對(duì)用戶的存取權(quán)限進(jìn)行檢查。如果該用戶沒(méi)有相應(yīng)的訪問(wèn)權(quán)限或違反了完整性約束,就拒絕執(zhí)行該查詢。檢查通過(guò)后便把SQL查詢語(yǔ)句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式。RDBMS一般都用查詢樹(querytree),也稱為語(yǔ)法分析樹(syntaxtree),來(lái)表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式。這個(gè)過(guò)程中要把數(shù)據(jù)庫(kù)對(duì)象的外部名稱轉(zhuǎn)換為內(nèi)部表示。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理3、查詢優(yōu)化每個(gè)查詢都會(huì)有許多可供選擇的執(zhí)行策略和操作算法,查詢優(yōu)化(queryoptimization)就是選擇一個(gè)高效執(zhí)行的查詢處理策略。查詢優(yōu)化有多種方法。按照優(yōu)化的層次一般可分為代數(shù)優(yōu)化和物理優(yōu)化。代數(shù)優(yōu)化是指關(guān)系代數(shù)表達(dá)式的優(yōu)化,即按照一定的規(guī)則,改變代數(shù)表達(dá)式中操作的次序和組合,使查詢執(zhí)行更高效;9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理物理優(yōu)化則是指存取路徑和底層操作算法的選擇。選擇的依據(jù)可以是基于規(guī)則(rulebased)的,也可以是基于代價(jià)(costbased)的,還可以是基于語(yǔ)義(semanticbased)的。實(shí)際RDBMS中的查詢優(yōu)化器都綜合運(yùn)用了這些優(yōu)化技術(shù),以獲得最好的查詢優(yōu)化效果。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理4、查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計(jì)劃,由代碼生成器[codegenerator)生成執(zhí)行這個(gè)查詢計(jì)劃的代碼。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1.2實(shí)現(xiàn)查詢操作的算法示例本節(jié)簡(jiǎn)單介紹選擇操作和連接操作的實(shí)現(xiàn)算法,確切地說(shuō)是算法思想。每一種操作有多種執(zhí)行這個(gè)操作的算法,這里僅僅介紹最主要的幾個(gè)算法。對(duì)于其他重要操作的詳細(xì)實(shí)現(xiàn)算法,有興趣的讀者請(qǐng)參考有關(guān)RDBMS實(shí)現(xiàn)技術(shù)的書。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理一、選擇操作的實(shí)現(xiàn)第三章中已經(jīng)講解了SELECT語(yǔ)句功能十分強(qiáng)大,有許多選項(xiàng),因此實(shí)現(xiàn)的算法和優(yōu)化策略也很復(fù)雜。不失一般性,下面以簡(jiǎn)單的選擇操作為例介紹典型的實(shí)現(xiàn)方法。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理[例l]Select*fromstudentwhere<條件表達(dá)式>;考慮<條件表達(dá)式>的幾種情況:C1:無(wú)條件;C2:Sno=‘200215121’;C3:Sage=20;C4:Sdept='CS‘ANDSage>20;9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理1、簡(jiǎn)單的全表掃描方法對(duì)查詢的基本表順序掃描,逐一檢查每個(gè)元組是否滿足選擇條件,把滿足條件的元組作為結(jié)果輸出。對(duì)于小表,這種方法簡(jiǎn)單有效。對(duì)于大表順序掃描十分費(fèi)時(shí),效率很低。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理2、索引(或散列)掃描方法如果選擇條件中的屬性上有索引(例如B+樹索引或Hash索引),可以用索引掃描方法。通過(guò)索引先找到滿足條件的元組主碼或元組指針,再通過(guò)元組指針直接在查詢的基本表中找到元組。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理[例1-C2]以C2為例,Sno=‘200215121’,并且Sno上有索引(或Sno是散列碼),則可以使用索引(或散列)得到Sno為‘200215121’元組的指針,然后通過(guò)元組指針在student表中檢索到該學(xué)生。[例1-C3]以C3為例,Sage>20,并且Sage上有B+樹索引,則可以使用B+樹索引找到Sage=20的索引項(xiàng),以此為入口點(diǎn)在B+樹的順序集上得到Sage>20的所有元組指針,然后通過(guò)這些元組指針到student表中檢索到所有年齡大于20的學(xué)生。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理[例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é)果輸出。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理二、連接操作的實(shí)現(xiàn)接操作是查詢處理中最耗時(shí)的操作之一。不失一般性,這里只討論等值連接(或自然連接)最常用的實(shí)現(xiàn)算法。例2SELECT*FROMStudent,SC

WHEREStudent.Sno=SC.Sno9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理1、嵌套循環(huán)方法[nestedloop]這是最簡(jiǎn)單可行的算法。對(duì)外層循環(huán)(Student)的每一個(gè)元組(s),檢索內(nèi)層循環(huán)(SC)中的每一個(gè)元組(SC),并檢查這兩個(gè)元組在連接屬性(Sno)上是否相等。如果滿足連接條件,則串接后作為結(jié)果輸出,直到外層循環(huán)表中的元組處理完為止。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理2、排序-合并方法(Sort-mergejoin或mergejoin)這也是常用的算法,尤其適合連接的諸表已經(jīng)排好序的情況。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理用排序-合并連接方法的步驟是:①如果連接的表沒(méi)有排好序,首先對(duì)Student表和SC表按連接屬性Sno排序;

②取Student表中第一個(gè)Sno,依次掃描SC表中具有相同Sno的元組;把它們連接起來(lái)如圖9.2所示);

③當(dāng)掃描到Sno不相同的第一個(gè)SC元組時(shí),返回Student表掃描它的下一個(gè)元組,再掃描SC表中具有相同Sno的元組,把它們連接起來(lái)。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理95001…95002…95003…95004…┇┇9500119295001285950013889500229095002380

┇┇圖9.2排序-合并連接方法示意圖重復(fù)上述步驟直到Student表掃描完。這樣Student表和SC表都只要掃描一遍。當(dāng)然,如果2個(gè)表原來(lái)無(wú)序,執(zhí)行時(shí)間要加上對(duì)兩個(gè)表的排序時(shí)間。即使這樣,對(duì)于2個(gè)大表。先排序后使用Sort-mergejoin方法執(zhí)行連接,總的時(shí)間一般仍會(huì)大大減少。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理3、索引連接(indexjion)方法·用索引連接方法的步驟是:

①在SC表上建立屬性Sno的索引,如果原來(lái)沒(méi)有的話。

②對(duì)Student中每一個(gè)元組,由Sno值通過(guò)SC的索引查找相應(yīng)的SC元組;

③把這些SC元組和Student元組連接起來(lái)。循環(huán)執(zhí)行②③,直到Student表中的元組處理完為止。

9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理4、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)。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理上面HashJoin算法假設(shè)兩個(gè)表中較小的表在第一階段后可以完全放入內(nèi)存的hash桶中。不需要這個(gè)前提條件的hashjoin算法以及許多改進(jìn)的算法這里就不介紹了。以上的算法思想可以推廣到更加一般的多個(gè)表的連接算法上。9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理查詢優(yōu)化在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中有著非常重要的地位。關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)和非過(guò)程化的SQL之所以能夠取得巨大的成功,關(guān)鍵是得益于查詢優(yōu)化技術(shù)的發(fā)展。關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素。優(yōu)化對(duì)關(guān)系系統(tǒng)來(lái)說(shuō)既是挑戰(zhàn)又是機(jī)遇。所謂挑戰(zhàn)是指關(guān)系系統(tǒng)為了達(dá)到用戶可接受的性能必須進(jìn)行查詢優(yōu)化。由于關(guān)系表達(dá)式的語(yǔ)義級(jí)別很高,使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義,提供了執(zhí)行查詢優(yōu)化的可能性。這就為關(guān)系系統(tǒng)在性能上接近甚至超過(guò)非關(guān)系系統(tǒng)提供了機(jī)遇。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.2.1關(guān)系及其查詢優(yōu)化關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素。關(guān)系系統(tǒng)的查詢優(yōu)化既是RDBMS實(shí)現(xiàn)的關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)的優(yōu)點(diǎn)所在。它減輕了用戶選擇存取路徑的負(fù)擔(dān)。用戶只要提出‘干什么’,不必指出‘怎么干’。查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率,而且在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化這是因?yàn)椋?/p>

(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息,例如關(guān)系中的元組數(shù)、關(guān)系中每個(gè)屬性值的分布情況等。優(yōu)化器可以根據(jù)這些信息選擇有效的執(zhí)行計(jì)劃,而用戶程序則難以獲得這些信息。

(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了,系統(tǒng)可以自動(dòng)對(duì)查詢進(jìn)行重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序,而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。

9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化(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ù)。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化關(guān)系數(shù)據(jù)庫(kù)查詢優(yōu)化的總目標(biāo)是:選擇有效的策略,求得給定關(guān)系表達(dá)式的值。實(shí)際系統(tǒng)對(duì)查詢優(yōu)化的具體實(shí)現(xiàn)一般可以歸納為四個(gè)步驟:1、將查詢轉(zhuǎn)換成某種內(nèi)部表示,通常是語(yǔ)法樹。2、根據(jù)一定的等價(jià)變換規(guī)則把語(yǔ)法樹轉(zhuǎn)換成標(biāo)準(zhǔn)(優(yōu)化)形式。3、選擇低層的操作算法。對(duì)于語(yǔ)法樹中的每一個(gè)操作需要根據(jù)存取路徑、數(shù)據(jù)的存儲(chǔ)分布、存儲(chǔ)數(shù)據(jù)的聚簇等信息來(lái)選擇具體的執(zhí)行算法。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化4、生成查詢計(jì)劃。查詢計(jì)劃也稱查詢執(zhí)行方案,是由一系列內(nèi)部操作組成的。這些內(nèi)部操作按一定的次序構(gòu)成查詢的一個(gè)執(zhí)行方案。通常這樣的執(zhí)行方案有多個(gè),需要對(duì)每個(gè)執(zhí)行計(jì)劃計(jì)算代價(jià),從中選擇代價(jià)最小的一個(gè)。在集中式數(shù)據(jù)庫(kù)中,查詢的執(zhí)行開銷主要包括:總代價(jià)=I/O代價(jià)+CPU代價(jià)在多用戶環(huán)境下:總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)

在分布式系統(tǒng)中:總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)+通訊代價(jià)9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.2.2一個(gè)實(shí)例我們首先來(lái)看一個(gè)簡(jiǎn)單的例子,說(shuō)明為什么要進(jìn)行查詢優(yōu)化。[例3]求選修了2號(hào)課程的學(xué)生姓名。用SQL語(yǔ)言表達(dá):

SELECTStudent.Sname

FROMStudent,SC

WHEREStudent.Sno=SC.SnoANDSC.Cno='2';假定學(xué)生-課程數(shù)據(jù)庫(kù)中有l(wèi)000個(gè)學(xué)生記錄,l0000個(gè)選課記錄,其中選修2號(hào)課程的選課記錄為50個(gè)。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化

系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來(lái)完成這一查詢1.Q1=ΠSname(σStudent.sno=sc.sno∧o='2’(Student×SC))

2.Q2=ΠSname(σo='2'(StudentSC))3.Q3=ΠSname(Studentσo='2'(SC))還可以寫出幾種等價(jià)的關(guān)系代數(shù)表達(dá)式,但分析這三種就足以說(shuō)明問(wèn)題了.我們將看到由于查詢執(zhí)行的策略不同,查詢時(shí)間相差很大。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化一、第一種情況l.計(jì)算廣義笛卡爾積把S和SC的每個(gè)元組連接起來(lái)。一般連接的做法是:在內(nèi)存中盡可能多地裝入某個(gè)表(如Student表)的若干塊元組,留出一塊存放另一個(gè)表(如SC表)的元組。然后把SC中的每個(gè)元組和Student中每個(gè)元組連接,連接后的元組裝滿一塊后就寫到中間文件上,再?gòu)腟C中讀入一塊和內(nèi)存中的S元組連接,直到SC表處理完。這時(shí)再一次讀入若干塊Student元組,讀入一塊SC元組,量復(fù)上述處理過(guò)程,直到把Student表處理完。設(shè)一個(gè)塊能裝l0個(gè)Student元組或l00個(gè)SC元組,在內(nèi)存中存放5塊Student元組和l塊SC元組,則讀取總塊數(shù)為:9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化

其中讀Student表l00塊。讀SC表20遍,每遍l00塊。若每秒讀寫20塊,則總計(jì)要花105秒。

9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化塊連接后的元組數(shù)為103104=107。設(shè)每塊能裝l0個(gè)元組,則寫出這些塊要用106/20=5104秒。2.作選擇操作依次讀入連接后的元組,按照選擇條件選取滿足要求的的記錄。假定內(nèi)存處理時(shí)間忽略。這一步讀取中間文件花費(fèi)的時(shí)間(同寫中間文件一樣)需5104秒。滿足條件的元組假設(shè)僅50個(gè),均可放在內(nèi)存。3.作投影把第2步的結(jié)果在Sname上作投影輸出,得到最終結(jié)果。因此第一種情況下執(zhí)行查詢的總時(shí)間105+25104

105秒。這里,所有內(nèi)存處理時(shí)間均忽略不計(jì)。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化二、第二種情況l.計(jì)算自然連接為了執(zhí)行自然連接,讀取Student和SC表的策略不變,總的讀取塊數(shù)仍為2100塊花費(fèi)l05秒。但自然連接的結(jié)果比第一種情況大大減少,為104個(gè)。因此寫出這些元組時(shí)間為104/10/20=50秒。僅為第一種情況的千分之一。2.讀取中間文件塊,執(zhí)行選擇運(yùn)算,花費(fèi)時(shí)間也為50秒。3.杷第2步結(jié)果投影輸出。第二種情況總的執(zhí)行時(shí)間≈105+50+50≈205秒。

9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化三、第三種情況1.先對(duì)SC表作選擇運(yùn)算,只需讀一遍SC表,存取l00塊花費(fèi)時(shí)間為5秒,因?yàn)闈M足條件的元組僅50個(gè),不必使用中間文件。2.讀取STUDENT表,把讀入的STUDENT元組和內(nèi)存中的SC元組作連接。也只需讀一遍STUDENT表共l00塊花費(fèi)時(shí)間為5秒。3.把連接結(jié)果投影輸出。

第三種情況總的執(zhí)行時(shí)間≈5+5≈10秒。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化假如SC表的Cno字段上有索引,第l步就不必讀取所有的SC元組而只需讀取Cno=‘2’的那些元組(50個(gè))。存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共3~4塊。若STUDENT表在Sno上也有索引,則第2步也不必讀取所有的STUDENT元組,因?yàn)闈M足條件的SC記錄僅50個(gè),涉及最多50個(gè)STUDENT記錄,因此讀取STUDENT表的塊數(shù)也可大大減少??偟拇嫒r(shí)間將進(jìn)一步減少到數(shù)秒。

這個(gè)簡(jiǎn)單的例子充分說(shuō)明了查詢優(yōu)化的必要性,同時(shí)也給了我們一些查詢優(yōu)化方法的初步概念。如當(dāng)有選擇和連接操作時(shí),應(yīng)當(dāng)先做選擇操作,這樣參加連接的元組就可以大大減少。下面給出優(yōu)化的一般策略。9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化

代數(shù)優(yōu)化:是基于關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化方法。9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式的優(yōu)化是查詢優(yōu)化的基本課題。而研究關(guān)系代數(shù)表達(dá)式的優(yōu)化最好從研究關(guān)系表達(dá)式的等價(jià)變換規(guī)則開始。

所謂關(guān)系代數(shù)的等價(jià)是指相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的。兩個(gè)關(guān)系表達(dá)式El和E2是等價(jià)的,可記為E1≡E2。

常用的等價(jià)變換規(guī)則有:9.3代數(shù)優(yōu)化l.連接、笛卡爾積交換律設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式,F(xiàn)是連接運(yùn)算的條件,則有:E1×E2≡E2×E1E1E2≡E2E1E1E2≡E2El

F

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

F1

F2

F1

F29.3代數(shù)優(yōu)化3.投影的串接定律

A1,A2,...,An(B1,B2,...,Bm(E))≡A1,A2,...,An(E) 這里,E是關(guān)系代數(shù)表達(dá)式,Ai(i=1,2,...,n),Bj(j=l,2,...,m)是屬性名且{A1,A2,...,An}構(gòu)成{Bl,B2,...,Bm}的子集。4.選擇的串接定律σF1(σF2(E))≡σF1∧F2(E)這里,E是關(guān)系代數(shù)表達(dá)式,F(xiàn)l,F(xiàn)2是選擇條件。選擇的串接律說(shuō)明選擇條件可以合并。這樣一次就可檢查全部條件。9.3代數(shù)優(yōu)化5.選擇與投影的交換律σF(A1,A2,...,An(E))≡A1,A2,...,An(σF(E))這里,選擇條件F只涉及屬性A1,...,An。若F中有不屬于Al,...,An的屬性B1,…,Bm則有更一般的規(guī)則:

A1,A2,...,An(σF(E))≡A1,A2,...,An(σF(A1,A2,...,An,B1,B2,...,Bm(E))9.3代數(shù)優(yōu)化6.選擇與笛卡爾積的交換律如果F中涉及的屬性都是El中的屬性,則σF(El×E2)≡σF(El)×E2如果F=F1∧F2,并且F1只涉及E1中的屬性,F(xiàn)2只涉及E2中的屬性,則由上面的等價(jià)變換規(guī)則1,4,6可推出:σF(E1×E2)≡σF1(El)×σF2(E2) 若F1只涉及E1中的屬性,F(xiàn)2涉及E1和E2兩者的屬性,則仍有σF(El×E2)≡σF2(σF1(E1)×E2)它使部分選擇在笛卡爾積前先做。9.3代數(shù)優(yōu)化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.3代數(shù)優(yōu)化9.選擇對(duì)自然連接的分配律σF(E1E2)≡σF(El)σF(E2)

F只涉及E1和E2中的公共屬性9.3代數(shù)優(yōu)化10.投影與笛卡爾積的分配律設(shè)E1和E2是兩個(gè)關(guān)系表達(dá)式,A1,...,An是E1的屬性,B1,...,Bm是E2的屬性,則A1,A2,...,An,B1,B2,...,Bm(E1×E2)≡A1,A2,...,An(E1)×B1,B2,...,Bm(E2)l1.投影與并的分配律設(shè)E1和E2有相同的屬性名,則A1,A2,...,An(E1∪E2)≡A1,A2,...,An(E1)∪A1,A2,...,An(E2)9.3代數(shù)優(yōu)化9.3.2查詢樹的啟發(fā)式優(yōu)化(關(guān)系代數(shù)表達(dá)式的優(yōu)化規(guī)則)

下面的優(yōu)化策略一般能提高查詢效率,但不一定是所有策略中最優(yōu)的。其實(shí)‘優(yōu)化’一詞并不確切,也許‘改進(jìn)’或‘改善’更恰當(dāng)些。l.選擇運(yùn)算應(yīng)盡可能先做。在優(yōu)化策略中這是最重要、最基本的一條。它常??墒箞?zhí)行時(shí)間節(jié)約幾個(gè)數(shù)量級(jí),因?yàn)檫x擇運(yùn)算一般使計(jì)算的中間結(jié)果大大變小。9.3代數(shù)優(yōu)化2.把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。如有若干投影和選擇運(yùn)算,并且它們都對(duì)同一個(gè)關(guān)系操作,則可以在掃描此關(guān)系的同時(shí)完戌所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系。3.把投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái),沒(méi)有必要為了去掉某些字段而掃描一遍關(guān)系。9.3代數(shù)優(yōu)化4.杷某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算,連接特別是等值連接運(yùn)算要比同樣關(guān)系上的笛卡爾積省很多時(shí)間。5.找出公共子表達(dá)式。如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系,并且從外存中讀入這個(gè)關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少得多,則先計(jì)算一次公共子表達(dá)式并把結(jié)果寫入中間文件是合算的。當(dāng)查詢的是視圖時(shí),定義視圖的表達(dá)式就是公共子表達(dá)式的情況。9.3代數(shù)優(yōu)化9.3.3關(guān)系代數(shù)表達(dá)式的優(yōu)化算法我們可以應(yīng)用上面的變換法則來(lái)優(yōu)化關(guān)系表達(dá)式,使優(yōu)化后的表達(dá)式能遵循9.3.2中的一般原則。例如把選擇和投影盡可能地早做(即把它們移到表達(dá)式語(yǔ)法樹的下部)。下面給出關(guān)系表達(dá)式的優(yōu)化算法。算法:關(guān)系表達(dá)式的優(yōu)化。

輸入:一個(gè)關(guān)系表達(dá)式的查詢樹。

輸出:優(yōu)化查詢樹(計(jì)算該表達(dá)式的程序)。9.3代數(shù)優(yōu)化方法:1.利用規(guī)則(4)把形如σF1F2...Fn(E)變換為

σF1(σF2(...(σFn(E))...))2.對(duì)每一個(gè)選擇,利用規(guī)則4-9盡可能把它移到樹的葉端。3.對(duì)每一個(gè)投影利用規(guī)則3,5,l0,11中的一般形式盡可能把它移向樹的葉端。注意:等價(jià)變換規(guī)則3使一些投影消失,而一般形式的規(guī)則5把一個(gè)投影分裂為兩個(gè),其中一個(gè)有可能被移向樹的葉端。9.3代數(shù)優(yōu)化4.利用規(guī)則3~5把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多個(gè)選擇或投影能同時(shí)執(zhí)行,或在一次掃描中全部完成,盡管這種變換似乎違背‘投影盡可能早做’的原則,但這樣做效率更高。9.3代數(shù)優(yōu)化5.把上述得到的語(yǔ)法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(×,,,-)和它所有的直接祖先為一組(這些直接祖先是σ、運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算,則也將它們并入該組,但當(dāng)雙目運(yùn)算是笛卡爾積(×),而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。9.3代數(shù)優(yōu)化[例4]下面給出[例3]中SQL語(yǔ)句的代數(shù)優(yōu)化實(shí)例.

①把SQL語(yǔ)句轉(zhuǎn)換為查詢樹

②為了使用關(guān)系代數(shù)的優(yōu)化方法,把查詢樹轉(zhuǎn)換成關(guān)系代數(shù)語(yǔ)法樹

③進(jìn)行優(yōu)化9.3代數(shù)優(yōu)化結(jié)果Project(Sname)Select(SC.Cno=‘2’)Join(Student.Sno=SC.Sno)StudentSC圖9.3查詢樹×StudentSC圖9.4關(guān)系代數(shù)語(yǔ)法樹SnameσStudent.Sno=SC.SnoσSC.Cno=‘2’圖9.5優(yōu)化后的語(yǔ)法樹×StudentSCSnameσStudent.Sno=SC.SnoσSC.Cno=‘2’代數(shù)優(yōu)化改變查詢語(yǔ)句中操作的次序和組合,不涉及底層的存取路徑。物理優(yōu)化是要選擇高效合理的操作算法或存取路徑,求得優(yōu)化的查詢計(jì)劃,達(dá)到優(yōu)化的查詢目標(biāo)。選擇的方法是:9.4物理優(yōu)化基于規(guī)則的啟發(fā)式優(yōu)化。啟發(fā)式規(guī)則是指那些在大多數(shù)情況下都適用,但不是在每種情況下都是適用的規(guī)則?;诖鷥r(jià)估算的優(yōu)化。優(yōu)化器估算不同執(zhí)行策略的代價(jià),并選出具有最小代價(jià)的執(zhí)行計(jì)劃。9.4物理優(yōu)化兩者結(jié)合的優(yōu)化方法。查詢優(yōu)化器通常會(huì)把這兩種技術(shù)結(jié)合在一起使用。因?yàn)榭赡艿膱?zhí)行策略很多,要窮盡所有的策略進(jìn)行代價(jià)估算往往是不可行的,會(huì)造成查詢優(yōu)化本身付出的代價(jià)大于獲得的益處。為此,常常先使用啟發(fā)式規(guī)則,選取若干較優(yōu)的候選方案,減少代價(jià)估算的工作量;然后分別計(jì)算這些候選方案的執(zhí)行代價(jià),較快地選出最終的優(yōu)化方案。9.4物理優(yōu)化9·4·1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化一、選擇操作的啟發(fā)式規(guī)則有:1.對(duì)于小關(guān)系,使用全表順序掃描,即使選擇列上有索引。對(duì)于大關(guān)系,啟發(fā)式規(guī)則有:2.對(duì)于選擇條件是“主碼=值”的查詢,查詢結(jié)果最多是一個(gè)元組,可以選擇主碼索引。一般的RDBMS會(huì)自動(dòng)建立主碼索引。9.4物理優(yōu)化3.對(duì)于選擇條件是“非主屬性=值”的查詢,并且選擇列上有索引,則要估算查詢結(jié)果的元組數(shù)目,如果比例較小(<10%)可以使用索引掃描方法,否則還是使用全表順序掃描。4.對(duì)于選擇條件是屬性上的非等值查詢或者范圍查詢,并且選擇列上有索引,同樣要估算查詢結(jié)果的元組數(shù)目,如果比例較小(<10%)可以使用索引掃描方法,否則還是使用全表順序掃描。9.4物理優(yōu)化5.對(duì)于用AND連接的合取選擇條件,如果有涉及這些屬性的組合索引,則優(yōu)先采用組合索引掃描方法;如果某些屬性上有一般的索引,則可以用[例l-C4]中介紹的索引掃描方法,否則使用全表順序掃描。6.對(duì)于用OR連接的析取選擇條件,一般使用全表順序掃描。9.4物理優(yōu)化二、連接操作的啟發(fā)式規(guī)則有:1.如果2個(gè)表都已經(jīng)按照連接屬性排序,則選用排序-合并方法。2.如果一個(gè)表在連接屬性上有索引,則可以選用索引連接方法。3.如果上面2個(gè)規(guī)則都不適用,其中一個(gè)表較小,則可以選用Hashjoin方法。9.4物理優(yōu)化4.最后可以選用嵌套循環(huán)方法,并選擇其中較小的表,確切地講是占用的塊數(shù)(b)較少的表,作為外表(外循環(huán)的表)。理由如下:設(shè)連接表R與S分別占用的塊數(shù)為Br與Bs,連接操作使用的內(nèi)存緩沖區(qū)塊數(shù)為K,分配K-l塊給外表。如果R為外表,則嵌套循環(huán)法存取的塊數(shù)為Br+(Br/K-l)Bs,顯然應(yīng)該選塊數(shù)小的表作為外表。上面列出了一些主要的啟發(fā)式規(guī)則,在實(shí)際的RDBMS中啟發(fā)式規(guī)則要多得多。9.4物理優(yōu)化9·4·2基于代價(jià)的優(yōu)化啟發(fā)式規(guī)則優(yōu)化是定性的選擇,比較粗糙,但是實(shí)現(xiàn)簡(jiǎn)單而且優(yōu)化本身的代價(jià)較小,適合解釋執(zhí)行的系統(tǒng)。因?yàn)榻忉寛?zhí)行的系統(tǒng),優(yōu)化開銷包含在查詢總開銷之中。在編譯執(zhí)行的系統(tǒng)中,一次編譯優(yōu)化,多次執(zhí)行,查詢優(yōu)化和查詢執(zhí)行是分開的。因此,可以采用精細(xì)復(fù)雜一些的基于代價(jià)的優(yōu)化方法。9.4物理優(yōu)化一、統(tǒng)計(jì)信息基于代價(jià)的優(yōu)化方法要計(jì)算各種操作算法的執(zhí)行代價(jià),它與數(shù)據(jù)庫(kù)的狀態(tài)密切相關(guān)。為此在數(shù)據(jù)字典中存儲(chǔ)了優(yōu)化器需要的統(tǒng)計(jì)信息(databasestatistics),主要包括如下幾個(gè)方面。1.對(duì)每個(gè)基本表,該表的元組總數(shù)(N)、元組長(zhǎng)度(1)、占用的塊數(shù)(B)、占用的溢出塊數(shù)(B0);9.4物理優(yōu)化2.對(duì)基表的每個(gè)列,該列不同值的個(gè)數(shù)(m)、選擇率(f)(如果不同值的分布是均勻的,f=l/m;如果不同值的分布不均勻,則每個(gè)值的選擇率=具有該值的元組數(shù)/N)、該列最大值、最小值,該列上是否已經(jīng)建立了索引,是哪種索引(B+樹索引、Hash索引、聚集索引);3.對(duì)索引,例如B+樹索引,該索引的層數(shù)(L)、不同索引值的個(gè)數(shù)、索引的選擇基數(shù)S(有S個(gè)元組具有某個(gè)索引值)、索引的葉結(jié)點(diǎn)數(shù)(Y);等等。9.4物理優(yōu)化二、代價(jià)估算示例下面給出若干操作算

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論