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

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

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

SELECTS.Sname

FROMStudentS，SC

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

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

Q2=πSname(σ

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

Q3=πSname(Student|><|σ

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

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

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

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

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

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

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

(1)選擇的串接

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

σF1(σF2(R))≡σF2(σF1(R))關(guān)系代數(shù)等價變換規(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ù)等價變換規(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ù)等價變換規(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)投影和選擇操作同時進行(3)選擇和其前執(zhí)行的笛卡兒積合并成一個連接操作(4)找出表達式中公共子表達式(5)投影和其前后的二元運算結(jié)合起來(6)適當(dāng)?shù)念A(yù)處理關(guān)系代數(shù)表達式優(yōu)化算法算法：關(guān)系表達式的優(yōu)化輸入：一個關(guān)系表達式的語法樹輸出：計算該表達式的程序步驟：利用規(guī)則(1)把形如σ

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

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

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

ANDShop.S#＝

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

Shop.S#＝

SC.S#∧

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

實例分析圖7-2原始查詢樹實例分析

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

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

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

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

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

連接操作的實現(xiàn)和優(yōu)化實現(xiàn)連接操作一般有4種方法：嵌套循環(huán)法(nestedloop)利用索引或散列尋找匹配元組法排序歸并(sort-merge)法散列連接法(hashjoin)連接操作的實現(xiàn)和優(yōu)化嵌套循環(huán)法(nestedloop)順序掃描外關(guān)系的每一個元組，然后與內(nèi)關(guā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)法進行連接需要訪問的物理塊數(shù)為：

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

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

CI/O=D0+x*D1

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

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

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

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

PR

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

NA：

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

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

；

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

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

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

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

CINK=L+s

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

選擇操作的代價估算例：設(shè)有關(guān)系STUDENT，其統(tǒng)計數(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)試用代價估算優(yōu)化選取存取策略，并估算其執(zhí)行代價

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

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

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

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

s=10000/25=400

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

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

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

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

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

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

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

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

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

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

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