數(shù)據(jù)庫課件：第7章 查詢處理與查詢優(yōu)化

第7章查詢處理與查詢優(yōu)化(10/13)7.1引言7.2代數(shù)優(yōu)化7.3物理優(yōu)化7.4代價(jià)估算優(yōu)化*7.1引言查詢是數(shù)據(jù)庫系統(tǒng)中最基本、最常見和最復(fù)雜的操作

從用戶給出的查詢請求開始，直到得到查詢結(jié)果，這一過程稱為查詢處理對于一個(gè)給定的查詢，通常會有許多種可能的執(zhí)行策略，查詢優(yōu)化就是從眾多策略中找出高效執(zhí)行策略的處理過程查詢處理和優(yōu)化是DBMS實(shí)現(xiàn)的關(guān)鍵技術(shù)，對系統(tǒng)性能有很大影響查詢處理查詢處理是指從數(shù)據(jù)庫中查詢數(shù)據(jù)的一個(gè)處理過程這一過程包括將用戶的查詢語句轉(zhuǎn)變?yōu)閿?shù)據(jù)庫的查詢計(jì)劃，并且執(zhí)行計(jì)劃獲得查詢結(jié)果查詢處理的步驟實(shí)際系統(tǒng)對查詢優(yōu)化的具體實(shí)現(xiàn)一般可以歸納為四個(gè)步驟：將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式選擇低層的操作算法。對于語法樹中的每一個(gè)操作需要根據(jù)存取路徑、數(shù)據(jù)的存儲分布、存儲數(shù)據(jù)的聚簇等信息來選擇具體的執(zhí)行算法生成查詢計(jì)劃。查詢計(jì)劃也稱查詢執(zhí)行方案，由一系列內(nèi)部操作組成。這些內(nèi)部操作按一定的次序構(gòu)成查詢的一個(gè)執(zhí)行方案。通常這樣的執(zhí)行方案有多個(gè)，需要對每個(gè)執(zhí)行計(jì)劃計(jì)算代價(jià)，從中選擇代價(jià)最小的一個(gè)查詢處理的步驟查詢處理的實(shí)現(xiàn)方式解釋：DBMS接到查詢語句，創(chuàng)建相應(yīng)的事務(wù)，解釋執(zhí)行查詢語句，且在事務(wù)完成后返回查詢結(jié)果，一般不保留可執(zhí)行代碼查詢處理的實(shí)現(xiàn)方式編譯：應(yīng)用程序經(jīng)預(yù)編譯處理，將嵌入的查詢語句分出，進(jìn)行語法、詞法分析和查詢優(yōu)化，生成一個(gè)可執(zhí)行的訪問模塊（AM），存于磁盤中。查詢優(yōu)化關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢語言一般是“非過程語言”，它減輕了用戶選擇存取路徑的負(fù)擔(dān)。即用戶只要提出“做什么?”(What)，不必指出“怎么做”(How)。用戶不必關(guān)心查詢的具體執(zhí)行過程由DBMS確定合理的、有效的執(zhí)行策略這方面的功能稱為查詢優(yōu)化對于使用非過程查詢語言的RDBMS，查詢優(yōu)化是查詢處理中非常重要的一環(huán)查詢優(yōu)化的必要性查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好,這是因?yàn)椋簝?yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對查詢進(jìn)行重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握，系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)查詢優(yōu)化的途徑對查詢語句進(jìn)行等價(jià)變換（如改變基本操作的順序）使查詢執(zhí)行起來更加有效。這種優(yōu)化只涉及查詢語句本身，而不涉及存取路徑，故稱為獨(dú)立于存取路徑的優(yōu)化，或代數(shù)優(yōu)化根據(jù)系統(tǒng)提供的查詢路徑，選擇合理的存取策略（例如是選擇順序掃描還是選擇索引），這稱為依賴于存取路徑的優(yōu)化，或稱物理優(yōu)化有些查詢可根據(jù)啟發(fā)式規(guī)則選擇執(zhí)行策略，這稱為規(guī)則優(yōu)化根據(jù)可供選擇的執(zhí)行策略進(jìn)行代價(jià)估算，并從中選擇代價(jià)最小的執(zhí)行策略，這稱為代價(jià)估算優(yōu)化此外，還可以通過應(yīng)用數(shù)據(jù)庫的語義信息對查詢進(jìn)行優(yōu)化，這稱為語義優(yōu)化查詢處理的代價(jià)在集中式數(shù)據(jù)庫中，查詢的執(zhí)行代價(jià)主要包括總代價(jià)=I/O代價(jià)+CPU代價(jià)在多用戶環(huán)境下:總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)在網(wǎng)絡(luò)分布環(huán)境下:總代價(jià)=I/O代價(jià)+CPU代價(jià)+網(wǎng)絡(luò)傳輸代價(jià)實(shí)例分析例：求選修了2號課程的學(xué)生姓名。用SQL語言表達(dá)：

SELECTS.Sname

FROMStudentS，SC

WHERES.SNO=SC.SNOANDSC.CNO='2'；假定學(xué)生-課程數(shù)據(jù)庫中有l(wèi)000個(gè)學(xué)生記錄,l0000個(gè)選課記錄，其中選修2號課程的選課記錄為50個(gè)。系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這一查詢

Q1=πSname(σStudent.sno=sc.sno∧o='2'(Student×SC))

Q2=πSname(σ

o='2'(Student|><|SC))

Q3=πSname(Student|><|σ

o='2‘(SC))實(shí)例分析查詢執(zhí)行策略Q1代價(jià)分析計(jì)算廣義笛卡爾積的代價(jià)把S和SC的每個(gè)元組連接起來。一般連接的做法是：在內(nèi)存中盡可能多地裝人某個(gè)表(如Student表)的若干塊元組，留出一塊存放另一個(gè)表(如SC表)的元組。然后把SC中的每個(gè)元組和Student中每個(gè)元組連接，連接后的元組裝滿一塊后就寫到中間文件上，再從SC中讀入一塊和內(nèi)存中的S元組連接，直到SC表處理完。這時(shí)再一次讀入若干塊S元組，讀入一塊SC元組，量復(fù)上述處理過程，直到把S表處理完設(shè)一個(gè)塊能裝l0個(gè)Student元組或l00個(gè)SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為：

1000/10+1000/(10X5)X(10000/100)=2100塊其中讀Student表l00塊。讀SC表20遍，每遍l00塊。若每秒讀寫20塊，則總計(jì)要花105(秒)

連接后的元組數(shù)為1000X10000,設(shè)每塊能裝l0個(gè)元組，則寫出這些塊要花1000000/20=50000(秒)實(shí)例分析查詢執(zhí)行策略Q1代價(jià)分析(續(xù))選擇操作的代價(jià)依次讀入連接后的元組，按照選擇條件選取滿足要求的的記錄。假定內(nèi)存處理時(shí)間忽略。這一步讀取中間文件花費(fèi)的時(shí)間(同寫中間文件一樣)需50000秒。滿足條件的元組假設(shè)僅50個(gè)，均可放在內(nèi)存投影操作的代價(jià)把第2步的結(jié)果在Sname上作投影輸出,得到最終結(jié)果

Q1查詢的總時(shí)間約為105+2X5X10000秒這里，所有內(nèi)存處理時(shí)間均忽略不計(jì)實(shí)例分析查詢執(zhí)行策略Q2代價(jià)分析計(jì)算自然連接的代價(jià)

為了執(zhí)行自然連接，讀取Student和SC表的策略不變,總的讀取塊數(shù)仍為2100塊，花費(fèi)l05秒。但自然連接的結(jié)果比第一種情況大大減少，為10000個(gè)。因此寫出這些元組時(shí)間為/10/20=50秒,僅為第一種情況的千分之一讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時(shí)間也為50秒將第2步結(jié)果投影輸出Q2總的執(zhí)行時(shí)間≈105+50+50＝205秒

實(shí)例分析查詢執(zhí)行策略Q3代價(jià)分析先對SC表作選擇運(yùn)算，只需讀一遍SC表，存取l00塊花費(fèi)時(shí)間為5秒，因?yàn)闈M足條件的元組僅50個(gè)，不必使用中間文件讀取STUDENT表，把讀入的STUDENT元組和內(nèi)存中的SC元組作連接。也只需讀一遍STUDENT表共l00塊花費(fèi)時(shí)間為5秒把連接結(jié)果投影輸出

Q3總的執(zhí)行時(shí)間≈5+5＝10秒實(shí)例分析假如SC表的Cno字段上有索引，第1步就不必讀取所有的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ù)也可大大減少。總的存取時(shí)間將進(jìn)一步減少到數(shù)秒實(shí)例分析這個(gè)簡單的例子充分說明了查詢優(yōu)化的必要性，同時(shí)也給了我們一些查詢優(yōu)化方法的初步概念。如當(dāng)有選擇和連接操作時(shí)，應(yīng)當(dāng)先做選擇操作，這樣參加連接的元組就可以大大減少。7.2代數(shù)優(yōu)化(10/18)代數(shù)優(yōu)化使用等價(jià)變換規(guī)則來優(yōu)化關(guān)系代數(shù)表達(dá)式，使優(yōu)化后的表達(dá)式滿足原來的查詢?nèi)缓髨?zhí)行一系列已經(jīng)證明能夠優(yōu)化的策略，而不必考慮實(shí)際數(shù)據(jù)的值以及數(shù)據(jù)庫的存取路徑，從而減少執(zhí)行的開銷代數(shù)優(yōu)化的基本原則代數(shù)優(yōu)化的基本原則是盡量減小查詢處理的中間結(jié)果大小投影、選擇等一元操作對關(guān)系進(jìn)行水平或垂直分割，減小了關(guān)系的大小而并、連接等二元操作對兩個(gè)關(guān)系按條件組合，操作費(fèi)時(shí)且結(jié)果集比較大在變換查詢時(shí)，盡量先安排執(zhí)行投影、選擇，后進(jìn)行連接、笛卡兒積關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式的優(yōu)化是查詢優(yōu)化的基本課題上面的代數(shù)優(yōu)化原則大部分都涉及到代數(shù)表達(dá)式等價(jià)的變換因此，研究關(guān)系代數(shù)表達(dá)式的優(yōu)化應(yīng)當(dāng)從研究關(guān)系表達(dá)式的等價(jià)變換規(guī)則開始關(guān)系代數(shù)等價(jià)變換規(guī)則兩個(gè)關(guān)系表達(dá)式El和E2是等價(jià)的，可記為E1≡E2常用的等價(jià)變換規(guī)則有：

(1)選擇的串接

σF1(σF2(R))≡σF1∧F2(R)(2)選擇的交換

σF1(σF2(R))≡σF2(σF1(R))關(guān)系代數(shù)等價(jià)變換規(guī)則(3)投影的串接.

ΠL1(ΠL2(…ΠLn

(R)…))≡ΠL1(R)

條件：L1L2…Ln(4)選擇與投影的交換.

ΠL(σF(R))≡σF(ΠL(R))

條件：Attr(F)L(5)連接／笛卡兒積的交換律

R|><|S≡S|><|R R×S≡S×R關(guān)系代數(shù)等價(jià)變換規(guī)則(6)選擇對連接／笛卡兒積的分配律

σF(R|><|S)≡(σF(R))|><|S

條件：Attr(F)∩Attr(S)=NULL σF1∧F2(R|><|S)≡σF1(R)|><|σF2(S)

條件：

Attr(F1)∩Attr(S)=NULL,Attr(F2)∩Attr(R)=NULL(7)投影對連接／笛卡兒積的分配律

ΠL1∪L2(R|><|S)≡ΠL1(R)|><|ΠL2(S)FF

條件：

Attr(L1)∩Attr(S)=NULL,Attr(L2)∩Attr(R)=NULL

Attr(F)Attr(L1∪L2)關(guān)系代數(shù)等價(jià)變換規(guī)則(8)選擇對∪、∩、－的分配律

σF(R∪S)≡σF(R)∪σF(S)

σF(R∩S)≡σF(R)∩σF(S)

σF(R－S)≡σF(R)－σF(S)(9)投影對∪的分配律

ΠL(R∪S)≡ΠL(R)∪ΠL(S)(10)|><|、×、∪、∩的結(jié)合律

(R|><|S)|><|T≡R|><|(S|><|T)代數(shù)優(yōu)化的策略(1)盡可能早地執(zhí)行選擇操作(2)投影和選擇操作同時(shí)進(jìn)行(3)選擇和其前執(zhí)行的笛卡兒積合并成一個(gè)連接操作(4)找出表達(dá)式中公共子表達(dá)式(5)投影和其前后的二元運(yùn)算結(jié)合起來(6)適當(dāng)?shù)念A(yù)處理關(guān)系代數(shù)表達(dá)式優(yōu)化算法算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的語法樹輸出：計(jì)算該表達(dá)式的程序步驟：利用規(guī)則(1)把形如σ

F1∧F2...∧Fn(E)的表達(dá)式變換為

σF1(σF2(...(σFn(E))...))對每一個(gè)選擇，利用規(guī)則(4)－(8)盡可能把它移到樹的葉端關(guān)系代數(shù)表達(dá)式優(yōu)化算法對每一個(gè)投影利用規(guī)則(3)，(9)，(l0)，(5)中的一般形式盡可能把它移向樹的葉端利用規(guī)則(3)～(5)把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成，盡管這種變換以乎違背‘投影盡可能早做’的原則，但這樣做效率更高把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(×,∩|,∪，-)和它所有的直接祖先(包括σ,Π運(yùn)算)為一組。如果其后代直到葉子全是單目運(yùn)算則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積(×)，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外,把這些單目運(yùn)算單獨(dú)分為一組生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。各步的順序是任意的，只要保證任何一組的計(jì)算不會在它的后代組之前計(jì)算

實(shí)例分析例7-2設(shè)有Shop(商店)，Customer(顧客)，SC(購物關(guān)系)三個(gè)關(guān)系，查詢語句是“找出西安銷售給顧客“張立”彩電的商店編號和名稱”，用SQL語句表達(dá)如下：SELECTS#,SnameFROMShop，Customer，SCWHEREShop.Address=’西安’ANDCname=’張立’ANDItem=’彩電’

ANDShop.S#＝

SC.S#ANDCustomer.C#=SC.C#實(shí)例分析假設(shè)該查詢變換成的關(guān)系代數(shù)表達(dá)式如下：ΠS#,Sname(σShop.Address=’西安’∧Cname=’張立’∧Item=’彩電’∧

Shop.S#＝

SC.S#∧

Customer.C#=SC.C#(Shop×SC×Customer))該表達(dá)式可轉(zhuǎn)換為圖7-2所示的原始查詢樹表示。以SELECT子句對應(yīng)投影操作，F(xiàn)ROM子句對應(yīng)笛卡兒積操作，WHERE子句對應(yīng)選擇操作，生成原始查詢樹。

實(shí)例分析圖7-2原始查詢樹實(shí)例分析

圖7-3選擇操作盡量下移實(shí)例分析圖7-4投影操作下移

實(shí)例分析圖7-5連接條件和笛卡兒積組合成連接操作

7.3物理優(yōu)化根據(jù)系統(tǒng)所提供的存取路徑，選擇合理的存取策略(例如選用順序搜索或索引進(jìn)行查詢)稱為物理優(yōu)化物理優(yōu)化又稱為依賴于存取路徑的優(yōu)化，而代數(shù)優(yōu)化則屬于不依賴于存取路徑的優(yōu)化選擇操作的實(shí)現(xiàn)和優(yōu)化選擇操作是從關(guān)系中選擇滿足給定條件的元組，從水平方向減小關(guān)系的大小，查詢優(yōu)化中的一條基本原則就是選擇盡量先做其執(zhí)行策略，與選擇條件、可用的存取路徑以及選取的元組數(shù)在整個(gè)關(guān)系中所占的比例有關(guān)，分成下列幾種情況來實(shí)現(xiàn)

選擇操作的實(shí)現(xiàn)和優(yōu)化選擇條件可分為：等值(=)范圍(<,<=,>,>=,Between)集合(IN)等復(fù)合選擇條件由簡單選擇條件通過AND、OR連接而成

選擇操作的實(shí)現(xiàn)和優(yōu)化選擇操作的實(shí)現(xiàn)方法包括：(1)順序掃描：適用于“小”的關(guān)系，滿足條件的元組比例較大或無其他存取路徑。(2)利用各種存取路徑：包括索引（B+樹），動(dòng)態(tài)散列選擇操作的啟發(fā)式規(guī)則(10/18)(1)對于小關(guān)系，不必考慮其他存取路徑，直接用順序掃描(2)如果無索引或散列等存取路徑可用，或估計(jì)中選的元組數(shù)在關(guān)系中占有較大的比例(例如大于15％)，且有關(guān)屬性上無族集索引，則用順序掃描(3)對于主鍵的等值條件查詢，最多只有一個(gè)元組可以滿足此條件，應(yīng)優(yōu)先采用主鍵的索引或散列(4)對于非主鍵的等值條件查詢，要估計(jì)中選的元組數(shù)在關(guān)系中所占的比例。如果比例較小(例如小于15％)，可用無序索引，否則只能用族集索引或順序掃描選擇操作的啟發(fā)式規(guī)則(5)對于范圍條件．一般先通過索引找到范圍的邊界，再通過索引的順序集沿相應(yīng)方向搜索(6)對于用AND連接的合取選擇條件，若有相應(yīng)的多屬性索引，則優(yōu)先采用多屬性索引(7)對于用OR連接的析取選擇條件，只能按其中各個(gè)條件分別選出一個(gè)元組集，再求這些元組集的并。眾所周知，并是開銷大的操作，而且在OR連接的諸條件中，只要有一個(gè)條件無合適的存取路徑，就不得不采用順序掃描來處理這種查詢。因此，在查詢語句中，應(yīng)盡量避免采用析取選擇條件(8)有些選擇操作只要訪問索引就可得到結(jié)果，例如查詢索引屬性的最大值、最小值、平均值等。在此情況下，應(yīng)優(yōu)先利用索引，避免訪問數(shù)據(jù)連接操作的實(shí)現(xiàn)和優(yōu)化連接是從兩個(gè)關(guān)系的笛卡兒積中選擇滿足連接條件的元組，操作本身開銷大，并且可能產(chǎn)生大的中間結(jié)果為了更深入的了解連接操作的優(yōu)化技術(shù)，下面對主要的幾個(gè)算法分別進(jìn)行簡單描述，并分析各種算法的代價(jià)

連接操作的實(shí)現(xiàn)和優(yōu)化實(shí)現(xiàn)連接操作一般有4種方法：嵌套循環(huán)法(nestedloop)利用索引或散列尋找匹配元組法排序歸并(sort-merge)法散列連接法(hashjoin)連接操作的實(shí)現(xiàn)和優(yōu)化嵌套循環(huán)法(nestedloop)順序掃描外關(guān)系的每一個(gè)元組，然后與內(nèi)關(guān)系的每一個(gè)元組進(jìn)行匹配設(shè)bR

，bS分別表示R和S的物理塊數(shù)，nB為可用的內(nèi)存緩沖塊數(shù)，并以其中nB–1塊存放外關(guān)系，剩余的1塊存放內(nèi)關(guān)系。若以R為外關(guān)系，S為內(nèi)關(guān)系，用嵌套循環(huán)法進(jìn)行連接需要訪問的物理塊數(shù)為：

bR+[bR/(nB-1)]XbS若以S為外關(guān)系，R為內(nèi)關(guān)系，用嵌套循環(huán)法進(jìn)行連接需要訪問的物理塊數(shù)為：bS+[bS/(nB-1)]XbR比較上面2個(gè)式子，可以看出應(yīng)選擇占用物理塊少的關(guān)系作為外關(guān)系連接操作的實(shí)現(xiàn)和優(yōu)化2)利用索引或散列尋找匹配元組法如果內(nèi)關(guān)系有合適的存取路徑（例如索引或散列），可以考慮使用這些存取路徑代替順序掃描?？捎行p少I/O次數(shù)連接操作的實(shí)現(xiàn)和優(yōu)化排序歸并(sort-merge)法首先按連接屬性對關(guān)系排序，然后進(jìn)行歸并連接連接操作的實(shí)現(xiàn)和優(yōu)化散列連接法(hashjoin)首先用散列函數(shù)將連接屬性散列至文件中然后對散列到同一個(gè)桶中的元組進(jìn)行匹配連接的啟發(fā)式規(guī)則(1)如果兩個(gè)關(guān)系都已按連接屬性排序，則優(yōu)先用排序歸并法。如果兩個(gè)關(guān)系中已有一個(gè)關(guān)系按連接屬性排序，另一個(gè)關(guān)系很小，可考慮對此關(guān)系按連接屬性排序，再用排序歸并法連接(2)如果兩個(gè)關(guān)系中有一個(gè)關(guān)系在連接屬性上有索引(特別是簇集索引)或散列，則可令另一關(guān)系為外關(guān)系，順序掃描，并利用內(nèi)關(guān)系上的索引或散列尋找其匹配元組，以代替多遍掃描(3)如果應(yīng)用上述兩規(guī)則的條件都不具備，且兩個(gè)關(guān)系都比較小，可以應(yīng)用嵌套循環(huán)法(4)如果(1)、(2)、(3)規(guī)則都不適用，可用散列連接法投影操作的實(shí)現(xiàn)投影操作選取關(guān)系的某些列，從垂直的方向減小關(guān)系的大小投影操作一般可與選擇、連接等操作同時(shí)進(jìn)行，不再需要附加的I/O開銷但是，投影結(jié)果可能會出現(xiàn)重復(fù)元組，應(yīng)消除這些完全相同的元組投影操作的實(shí)現(xiàn)如果關(guān)系已經(jīng)經(jīng)過排序，等值的元組相鄰存儲，很容易只留一個(gè)元組副本去掉多余的副本也可使用和散列方法來實(shí)現(xiàn)消除重復(fù)元組，整個(gè)關(guān)系按建立在某一屬性或多個(gè)屬性上的散列函數(shù)進(jìn)行劃分集合操作的實(shí)現(xiàn)對于笛卡兒積(×)一般可采用嵌套循環(huán)法；對于∪、∩、－等操作需要發(fā)現(xiàn)共同元組；7.4代價(jià)估算優(yōu)化代價(jià)估算優(yōu)化：對可供選擇的執(zhí)行策略進(jìn)行代價(jià)估算，從中選用代價(jià)最小的執(zhí)行策略在小型和解釋執(zhí)行的DBMS中，規(guī)則優(yōu)化用得比較多。因?yàn)樵诮忉寛?zhí)行的數(shù)據(jù)庫系統(tǒng)中，優(yōu)化時(shí)間包含在事務(wù)的執(zhí)行時(shí)間中，不宜采用開銷太大的優(yōu)化方法在編譯實(shí)現(xiàn)的數(shù)據(jù)庫系統(tǒng)中，一次編譯，可供多次執(zhí)行，編譯時(shí)間不包括在事務(wù)的執(zhí)行時(shí)間中，值得采用較復(fù)雜的優(yōu)化方法一般先用規(guī)則優(yōu)化，選擇幾個(gè)可取的執(zhí)行策略，然后對它們進(jìn)行代價(jià)比較，從中擇優(yōu)查詢執(zhí)行代價(jià)主要包括3個(gè)方面：

I/O代價(jià)(*)CPU代價(jià)通信代價(jià)訪問磁盤1次所需的代價(jià)可表示為：

CI/O=D0+x*D1

其中：x－－存取數(shù)據(jù)的大小，以字節(jié)表示

D0－－與x無關(guān)的I/O代價(jià)，包括尋道時(shí)間和等待時(shí)間

D1－－每個(gè)字節(jié)所需的傳輸時(shí)間一般D0>>XD1故I/O代價(jià)=I/O次數(shù)XD0查詢執(zhí)行代價(jià)的組成與代價(jià)統(tǒng)計(jì)參數(shù)查詢執(zhí)行代價(jià)的組成與代價(jià)統(tǒng)計(jì)參數(shù)下面給出進(jìn)行代價(jià)估算時(shí)將要用到的統(tǒng)計(jì)參數(shù)

nR：R中的元組數(shù)；

PR

：R塊因子，即每個(gè)物理塊中包含的元組數(shù)；

NA：

屬性A在一個(gè)關(guān)系中出現(xiàn)的不同值的個(gè)數(shù)；

FA：屬性A的選擇因子，即屬性A為某一個(gè)值的概率，一般假定屬性值均勻分布，F(xiàn)A=1/NA

；

MA：屬性A的值域大小|DOM(A)|；

Li：索引i的級數(shù)；

選擇操作的代價(jià)估算(1)順序掃描最多選取一個(gè)元組的I/O代價(jià)：Csa=0.5┌n/p┐=0.5b選取多個(gè)元組的I/O代價(jià)：Csa=b(2)利用主鍵上的索引或散列進(jìn)行等值查詢通過索引訪問的I/O代價(jià)：CIk=L+1通過散列訪問的I/O代價(jià)：Chk=1(假定散列沒有溢出)

選擇操作的代價(jià)估算(3)利用非主鍵上的無序索引進(jìn)行等值查詢分析表明幾乎每取一個(gè)元組都需要訪問一個(gè)物理塊，故

CINK=L+s

其中s為滿足選擇條件的元組數(shù)(4)利用聚簇索引進(jìn)行等值查詢CCI=L+[s/p](5)利用聚簇索引進(jìn)行范圍查詢CCIR=L+[b/2]

選擇操作的代價(jià)估算例：設(shè)有關(guān)系STUDENT，其統(tǒng)計(jì)數(shù)據(jù)及存取路徑如下：

n=10000b=2000即p=5在屬性DEPT上建有聚簇索引：NDEPT=25，L=2在屬性SNO上建有主鍵索引：NSNO=10000，L=4在屬性DNO上建有輔助索引：NDNO=20，L=2在屬性AGE上建有輔助索引：NAGE=15，L=2設(shè)有下列查詢：Q1：σSNO=‘992311’(STUDENT)Q2：σDEPT=‘CS’(STUDENT)Q3：σAGE>=20(STUDENT)Q4：σDEPT=‘CS’ANDDNO=‘108’ANDAGE>=20(STUDENT)試用代價(jià)估算優(yōu)化選取存取策略，并估算其執(zhí)行代價(jià)

選擇操作的代價(jià)估算解：Q1：σSNO=‘992311’(STUDENT)

由于SNO上建有主索引，應(yīng)優(yōu)先采用主索引，其執(zhí)行代價(jià)可估算為：

CQ1=L+1=4+1=5Q2：σDEPT=‘CS’(STUDENT)

由于DEPT上建有聚簇索引，故可不考慮順序掃描，滿足Q2的元組數(shù)s估計(jì)為：

s=10000/25=400

由于STUDENT關(guān)系對DEPT是聚簇的，故I/O代價(jià)可估算為：

CQ2=L+[s/p]=2+[400/5]=82

選擇操作的代價(jià)估算解：Q3：σAGE>=20(STUDENT)

是范圍查詢，雖然在AGE上建有輔助索引，但不是聚簇索引，如果取一半元組，則使用索引還不如使用順序掃描，故：

CQ3=b=2000Q4：σDEPT=‘CS’ANDDNO=‘108’ANDAGE>=20(STUDENT)

查詢條件是合取式，由于沒有適當(dāng)?shù)亩鄬傩运饕捎茫挥?種可能的策略：

選擇操作的代價(jià)估算策略1：預(yù)查詢法滿足條件DNO=‘108’的元組數(shù)估算為：

n/NDNO=10000/20=500。設(shè)順序集每塊可容納200個(gè)tid，則從DNO輔助索引的順序集中取500個(gè)tid所需的I/O代價(jià)為：CDNO=L+[500/200]=3+3=6滿足條件AGE>=20的元組數(shù)估算為：n/2=10000/2=5000則從AGE輔助索引的順序集中取5000個(gè)tid所需的I/O代價(jià)為：CAGE=L+[5000/200]=2+25=272個(gè)tid集的交集的大小應(yīng)小于或等于500。由于取500個(gè)隨機(jī)存放的元組一般需要500次I/O，故預(yù)查詢法的I/O代價(jià)估算為：Ca=CDNO+CAGE+500=533

選擇操作的代價(jià)估算策略2：用其中代價(jià)最小的一個(gè)條件選出元組，再用其他條件對這些元組進(jìn)行篩選應(yīng)從3個(gè)條件中選出I/O代價(jià)最小的條件：σDEPT=‘CS’：同Q2，CQ2=82σDNO=‘108’：s=10000/20=500CDNO=‘108’=CDNO+500=6+500=506σAGE>=20：同Q3，CQ3=2000在3個(gè)條件中，以σDEPT=‘CS’的代價(jià)最小，故可先按此條件選取出滿足條件DEPT=‘CS’的學(xué)生的元組并同時(shí)檢查每個(gè)元組是否滿足其他2個(gè)條件，其I/O代價(jià)為

Cb=82由于Ca>Cb，故CQ4=Cb=82連接操作的代價(jià)估算連接結(jié)果大小的估算為估算連接操作的代價(jià)，首先需要估算連接結(jié)果的大小。為此，引入連接選擇因子(joinselectivity)

js=|R|><|CS|/|RXS|=|R|><|