9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理第九章關(guān)系查詢處理和查詢優(yōu)化9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.5小結(jié)9.1.1查詢處理的步驟RDBMS查詢處理可以分為4個(gè)階段：查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理查詢處理的任務(wù)是把用戶提交給RDBMS的查詢語句轉(zhuǎn)換為高效的執(zhí)行計(jì)劃。1、查詢分析對查詢語句進(jìn)行掃描、詞法分析和語法分析，

即判斷查詢語句是否符合SQL的語法規(guī)則。2、查詢檢查（1）根據(jù)數(shù)據(jù)字典對合法的查詢語句進(jìn)行語義檢查。檢查語句中的數(shù)據(jù)庫對象（如屬性名、關(guān)系名）

是否存在和是否有效。（2）根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用戶的存取權(quán)限進(jìn)行檢查。（3）將檢查通過的查詢語句轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)

表達(dá)式。（語法分析樹）3、查詢優(yōu)化(QueryOptimization)每個(gè)查詢都會有許多可供選擇的執(zhí)行策略和操作算法，查詢優(yōu)化就是選擇一個(gè)高效執(zhí)行的查詢策略。查詢優(yōu)化有多種途徑：（1）代數(shù)優(yōu)化將查詢語句轉(zhuǎn)換成為相應(yīng)的關(guān)系代數(shù)表達(dá)式，然后按照一定的規(guī)則，改變關(guān)系代數(shù)表達(dá)式的操作次序和組合進(jìn)行優(yōu)化，借此來改變基本操作的次序，使查詢語句執(zhí)行起來更有效。這種查詢優(yōu)化僅涉及查詢語句本身，而不涉及存取路徑，是獨(dú)立于存取路徑的優(yōu)化。（2）物理優(yōu)化根據(jù)系統(tǒng)提供的存取路徑，選擇合理的存取路徑

和底層操作算法(例如選用順序搜索或索引進(jìn)行查找)，

是依賴于存取路徑的優(yōu)化。（3）規(guī)則優(yōu)化查詢的優(yōu)化僅根據(jù)啟發(fā)式規(guī)則選擇執(zhí)行的策略。（4）代價(jià)估算優(yōu)化對各種可供選擇的策略進(jìn)行代價(jià)估算，從中選用代價(jià)最小的執(zhí)行策略。實(shí)際RDBMS中的查詢優(yōu)化器都綜合運(yùn)用了這些優(yōu)化技術(shù)，以獲得最好的查詢優(yōu)化效果。4、查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計(jì)劃，由代碼生成器（codegenerator）生成執(zhí)行這個(gè)查詢計(jì)劃的代碼。9.1.2實(shí)現(xiàn)查詢操作的算法示例本節(jié)簡單介紹實(shí)現(xiàn)選擇操作和連接操作的幾種主要算法。一、選擇操作的實(shí)現(xiàn)[例１]

Select*fromstudentwhere<條件表達(dá)式>考慮<條件表達(dá)式>的幾種情況：

C1:

無條件；

C2:Sno=‘200215121’；

C3:Sage>20;

C4:Sdept=‘CS’ANDSage>20;對查詢的基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出。對于小表，這種方法簡單有效。對于大表，順序掃描十分費(fèi)時(shí)，效率很低。1、簡單的全表掃描方法如果選擇條件中的屬性上有索引（例如Ｂ＋樹索引或者Ｈash索引），可以用索引掃描方法。通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組。2、索引（或散列）掃描方法[例1-C3]以C3為例，Sage>20,并且Sage上有B+樹

索引。可以使用B+樹索引找到Sage＝20的索引項(xiàng)，以此為入口點(diǎn)在B+樹的順序集上得到Sage>20的所有元組指針，然后通過這些元組指針到student表中檢索所有年齡大于20的學(xué)生。[例1-C2]以C2為例，Sno=‘200215121’，并且Sno

上有索引?？梢允褂盟饕玫絊no為‘200215121’元組的指針，然后通過元組指針在student表中檢索到該學(xué)生。[例1-C4]以C4為例，Sdept=‘CS’ANDSage>20,

假設(shè)Sdept和Sage上都有索引。算法1：分別用上面兩種方法分別找到Sdept=‘CS’

的一組元組指針和Sage>20的另一組元組指

針，求這２組指針的交集，再到student表中

檢索。算法2：找到Sdept=‘CS’的一組元組的指針，通

過這些元組指針到student表中檢索，并

對得到的元組檢查另一個(gè)選擇條件

（Sage>20）是否滿足，把滿足條件的元組作

為結(jié)果輸出。二、連接操作的實(shí)現(xiàn)連接操作是查詢處理中最耗時(shí)的操作之一。不失一般性，這里只討論等值連接（或自然連接）最常用的實(shí)現(xiàn)算法。[例２]SELECT*FROMStudent,SC

WHEREStudent.Sno＝SC.Sno算法１：嵌套循環(huán)方法這是最簡單可行的算法。對外層循環(huán)（Student）

的每一個(gè)元組（s），檢索內(nèi)層循環(huán)（SC）中的每一

個(gè)元組（sc），并檢查這兩個(gè)元組在連接屬性（Sno）上是否相等。如果滿足連接條件，則串接后作為結(jié)果輸，直到外層循環(huán)表中的元組處理完畢為止。算法２：排序－合并方法這也是常用的算法，尤其適合連接的諸表已經(jīng)排好序的情況。步驟如下：（１）如果連接的表沒有排好序，首先對兩個(gè)表都按

連接屬性Sno排序。（２）取Student表中第一個(gè)Sno，依次掃描SC表中具

有相同Sno的元組；把它們連接起來（如圖）；95001…95002…95003……9500119295001285950013889500229095002380…（３）當(dāng)掃描到Sno不相同的第一個(gè)SC元組時(shí)，返回到Student表掃描它的下一個(gè)元組，再掃描SC表中具有相同Sno的元組，把它們連接起來。95001…95002…95003……9500119295001285950013889500229095002380…重復(fù)上述步驟直到Student表掃描完畢。這樣Student表和SC表只要掃描一遍。當(dāng)然，如果２個(gè)表原來無序，執(zhí)行時(shí)間還要加上對兩個(gè)表的排序時(shí)間。即使這樣，對于２個(gè)大表，先排序后使用sort-mergejoin方法執(zhí)行連接，總的時(shí)間一般仍會大大減少。算法３：索引連接方法（１）在SC表上建立屬性Sno的索引（沒有的話）；（２）對Student表中每一個(gè)元組，由Sno值通過SC的索引查找相應(yīng)的SC元組；（３）把這些SC元組和Student表中的元組連接起來。循環(huán)執(zhí)行（２）（３），直到Student表中的元組處理完為止。算法4：HashJoin方法把連接屬性Sno作為Hash碼，用同一個(gè)hash函數(shù)

把R和S中的元組散列到同一個(gè)hash文件中。第一步，劃分階段，對包含較少元組的表（比如

R）進(jìn)行一遍處理，把它的元組按hash函數(shù)分散到

hash表的桶中；第二步，試探階段，也稱為連接階段，對另一個(gè)

表（S）進(jìn)行一遍處理，把S的元組散列到適當(dāng)?shù)膆ash

桶中，并把元組與桶中所有來自R并與之相匹配的元

組連接起來。備注：上述hash

join算法假設(shè)兩個(gè)表中較小的表在第一階段后完全放入內(nèi)存的hash桶中。9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

9.2.1查詢優(yōu)化概述■關(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)化”做得更好。關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2一、由RDBMS進(jìn)行查詢優(yōu)化的好處：(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而

用戶程序則難以獲得這些信息。(2)如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員

一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)。關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2二、查詢優(yōu)化目標(biāo)及步驟１、查詢優(yōu)化的總目標(biāo)選擇有效策略，求得給定關(guān)系表達(dá)式的值，使得查詢代價(jià)最?。ㄝ^?。?。２、實(shí)際系統(tǒng)的查詢優(yōu)化步驟1）

將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹。2）根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)

（優(yōu)化）形式。3）選擇低層的操作算法對于語法樹中的每一個(gè)操作：（１）計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)；（２）選擇代價(jià)小的執(zhí)行算法；關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.24）生成查詢計(jì)劃(查詢執(zhí)行方案)查詢計(jì)劃是由一系列內(nèi)部操作組成的。代價(jià)計(jì)算公式如下：▄集中式數(shù)據(jù)庫

?單用戶系統(tǒng)總代價(jià)=I/O代價(jià)+CPU代價(jià)

?多用戶系統(tǒng)總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)一般地，集中式數(shù)據(jù)庫中I/O代價(jià)是最主要的。▄分布式數(shù)據(jù)庫總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)+通信代價(jià)關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化一個(gè)實(shí)例通過一個(gè)簡單的例子，說明為什么要進(jìn)行查詢優(yōu)化?！纠场浚呵筮x修了2號課程的學(xué)生姓名。

用SQL語言實(shí)現(xiàn)如下：

SELECTSnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’;假設(shè)學(xué)生－課程庫中有：1000條Student記錄

10000條SC記錄

其中，50條選修2號課程記錄。關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2系統(tǒng)可用下列3種等價(jià)的關(guān)系代數(shù)表達(dá)式來實(shí)現(xiàn)這一查詢操作。到底哪一種策略效率最優(yōu)？關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2假設(shè)1、外存：

Student：1000條

SC：10000條

其中，選修2號課程：50條2、一個(gè)內(nèi)存塊可以裝元組:

10個(gè)Student,或100個(gè)SC

內(nèi)存中一次可以存放:5塊Student元組,1塊SC元組,

10塊連接結(jié)果元組3、讀寫速度：20塊/秒4、連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2①Student×SC

讀取總塊數(shù)=讀Student表塊數(shù)+讀SC表遍數(shù)*每遍塊數(shù)

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100塊

讀數(shù)據(jù)時(shí)間=2100/20=105秒關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2②中間結(jié)果寫入內(nèi)存時(shí)間（處理時(shí)間忽略不計(jì)）中間結(jié)果大小=1000*10000=107寫中間結(jié)果時(shí)間

=107/10/20=50000秒③бStudent.Sno=SC.Sno∧SC.Cno=‘2’時(shí)間讀入中間結(jié)果時(shí)間

（處理時(shí)間忽略不計(jì)）

讀數(shù)據(jù)時(shí)間

=50000秒（結(jié)果為50條元組，直接放在內(nèi)存，不消耗存取時(shí)間）④時(shí)間：處理時(shí)間忽略不計(jì)，為０。關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2⑤總時(shí)間

=105＋50000＋50000

=100105秒=27.8小時(shí)關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2①StudentSC時(shí)間讀取總塊數(shù)=1000/10+(1000/(10×5))×(10000/100)=2100塊讀數(shù)據(jù)時(shí)間=2100/20=105秒②中間結(jié)果寫入內(nèi)存時(shí)間（處理時(shí)間忽略不計(jì)）中間結(jié)果大小=10000（減少1000倍）寫中間結(jié)果時(shí)間=10000/10/20=50秒

關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2③бSC.Cno=‘2’時(shí)間讀入中間結(jié)果時(shí)間

（處理時(shí)間忽略不計(jì)）

讀數(shù)據(jù)時(shí)間

=50秒（結(jié)果為50條元組，直接放在內(nèi)存，不消耗存取時(shí)間）④時(shí)間：處理時(shí)間忽略不計(jì)，為０。⑤總時(shí)間

=105＋50＋50

=205秒=3.4分鐘關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2①б時(shí)間

讀SC表總塊數(shù)（一遍）=10000/100=100塊

讀數(shù)據(jù)時(shí)間=100/20=5秒

（中間結(jié)果大小=50條不必寫入外存，不耗時(shí)

）②自然連接時(shí)間 讀Student表總塊數(shù)（一遍）=1000/10=100塊

讀數(shù)據(jù)時(shí)間=100/20=5秒

③總時(shí)間＝5＋5秒＝10秒

關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2三種執(zhí)行策略中，第三種最優(yōu)！?。∵@充分說明了查詢優(yōu)化的必要性?。。槭裁?？從中我們可以發(fā)現(xiàn)什么規(guī)律？？？關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2把代數(shù)表達(dá)式Q1變化成Q2、Q3，即有選擇和連接操作時(shí)，應(yīng)當(dāng)先做選擇操作，這樣連接的元組就可以大大減少，這就是代數(shù)優(yōu)化。在Q3中，SC表的選擇操作算法有全表掃描和索引掃描2種方法，經(jīng)過初步估算，索引掃描方法較優(yōu)。同樣對于Student和SC的連接，利用Student表上的索引，采用indexjoin代價(jià)也較小，這就是物理優(yōu)化。SQL查詢語句代數(shù)表達(dá)式代數(shù)優(yōu)化物理優(yōu)化執(zhí)行轉(zhuǎn)換關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2（局限性）9.3代數(shù)優(yōu)化

9.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則代數(shù)優(yōu)化9.3關(guān)系代數(shù)表達(dá)式等價(jià)：用相同的關(guān)系代替兩個(gè)表達(dá)式

中相應(yīng)的關(guān)系所得到的結(jié)果相同。兩個(gè)關(guān)系表達(dá)式E1、E2等價(jià)，記為：E1≡E2下面介紹常用的關(guān)系代數(shù)等價(jià)變換規(guī)則常用的關(guān)系代數(shù)等價(jià)變換規(guī)則代數(shù)優(yōu)化—

等價(jià)變化規(guī)則9.31.連接、笛卡爾積交換律

設(shè)E1、E2為關(guān)系代數(shù)表達(dá)式，F(xiàn)為連接運(yùn)算的條件。

E1×E2≡E2×E1

E1∞E2≡E2∞E1

E1∞E2≡E2∞E1FF2.連接、笛卡爾積的結(jié)合律

設(shè)E1、E2、E3為關(guān)系代數(shù)表達(dá)式，F(xiàn)1、F2為連接運(yùn)

算的條件。(E1×E2)×E3≡E1×(E2×E3)(E1∞E2)∞E3≡E1∞(E2∞E3)(E1∞E2)∞E3≡E1∞(E2∞E3)F1F2F1F2

3.投影的串接定律

πA1,A2,…,An(πB1,B2,…,Bm(E))≡πA1,A2,…,An(E)這里，E是關(guān)系代數(shù)表達(dá)式。屬性組{A1,A2,…,An}是屬性組{B1,B2,…,Bm}的子集。如：πsno(πsno,sname(Stuent))≡πsno(Stuent)代數(shù)優(yōu)化—

等價(jià)變化規(guī)則9.34.選擇的串接定律

σF1(σF2(E))≡σF1∧F2(E)如：σJNO=‘J1’(σPNO=‘P1’(SPJ))≡σJNO=‘J1’∧PNO=‘P1’(SPJ)5.選擇與投影的交換律

σF(πA1,A2,…,An(E))≡πA1,A2,…,An

(σF(E))這里，選擇條件F只涉及屬性A1,A2,…,An。代數(shù)優(yōu)化—

等價(jià)變化規(guī)則9.3若F中有不屬于A1,A2,…,An的屬性B1,B2,…,Bm,則πA1,A2,…,An(σF(E))

≡πA1,A2,…,An(σF(πA1,A2,…,An,B1,B2,…,Bm(E)))

6.選擇與笛卡爾積的交換律

1）若F中涉及的屬性都是E1中的屬性,則

σF(E1×E2)≡σF(E1)×E2

2）若F=F1∧F2，且F1只涉及E1中的屬性，F(xiàn)2只涉及E2

中的屬性，則

σF(E1×E2)≡σF1(E1)×σF2(E2)

代數(shù)優(yōu)化—

等價(jià)變化規(guī)則9.3

σF(E1×E2)≡σF2(σF1(E1)×E2)

它使部分笛卡爾積先做。3）若F=F1∧F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則7.選擇與并的分配律

設(shè)E=E1∪E2，E1、E2有相同的屬性名

σF(E1∪E2)≡σF(E1)∪σF(E2)8.選擇與差的分配律

設(shè)E1與E2有相同的屬性名

σF(E1-E2)≡σF(E1)-σF(E2)代數(shù)優(yōu)化—

等價(jià)變化規(guī)則9.39.選擇對自然連接的分配律

σF(E1∞E2)≡σF(E1)∞σF(E2)10.投影與笛卡爾積的分配律

設(shè)A1,…,An是關(guān)系表達(dá)式E1的屬性，B1,…,Bm是關(guān)系表達(dá)式E2的屬性

πA1,…,An,B1,…,Bm

(E1×E2)≡πA1,…,An(E1)×πB1,…,Bm(E2)代數(shù)優(yōu)化—

等價(jià)變化規(guī)則9.311.投影與并的分配律

設(shè)E1和E2具有相同的屬性名

πA1,…,An(E1∪E2)≡πA1,…,An(E1)∪πA1,…,An(E2)9.3.2查詢樹的啟發(fā)式優(yōu)化代數(shù)優(yōu)化—啟發(fā)式規(guī)則9.3本節(jié)討論應(yīng)用啟發(fā)式規(guī)則的代數(shù)優(yōu)化。這是對關(guān)系代數(shù)表達(dá)式的查詢樹進(jìn)行優(yōu)化的方法。典型的啟發(fā)式優(yōu)化規(guī)則有：一、選擇運(yùn)算應(yīng)盡可能先做。

在優(yōu)化策略中這是最重要、最基本的一條。因?yàn)檫x擇運(yùn)算一般能使計(jì)算的中間結(jié)果大大減少，所以常?？墒箞?zhí)行查詢的時(shí)間降低幾個(gè)數(shù)量級。二、將投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。三、將投影同其前或其后的雙目運(yùn)算結(jié)合起來，

沒有必要為了去掉某些字段而掃描一遍關(guān)系四、將某些選擇運(yùn)算同在其前面要執(zhí)行的笛

卡爾積運(yùn)算結(jié)合起來成為一個(gè)連接運(yùn)算。五、找出公共子表達(dá)式。先求出公共子表達(dá)式的值，然后將此值存入中間文件中。代數(shù)優(yōu)化—啟發(fā)式規(guī)則9.3σStudent.Sno=SC.Sno(Student×SC)Student∞SC代數(shù)優(yōu)化—

等價(jià)變化規(guī)則9.3【例３】：求選修了2號課程的學(xué)生姓名。

用SQL語言實(shí)現(xiàn)如下：

SELECTSnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’;代數(shù)優(yōu)化示例一、將查詢轉(zhuǎn)換成某種內(nèi)部表示“內(nèi)部表示”一般采用語法樹。結(jié)果Project(Sname)Select(SC.Cno=‘2’)join(Student.Sno=SC.Sno)StudentSC

為了進(jìn)一步使用關(guān)系代數(shù)表達(dá)式的優(yōu)化準(zhǔn)則，須將以上語法樹轉(zhuǎn)換成關(guān)系代數(shù)語法樹。πSnameσSC.Cno=‘2’σStudent.Sno=SC.Sno×StudentSC二、將語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)優(yōu)化形式πSnameσSC.Cno=‘2’σStudent.Sno=SC.Sno×StudentSCπSname(Student∞σSC.Cno=‘2’(SC)）9.4物理優(yōu)化代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑對于一個(gè)查詢語句有許多存取方案，它們的執(zhí)行效率不同，僅僅進(jìn)行代數(shù)優(yōu)化是不夠的物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計(jì)劃選擇的方法：基于規(guī)則的啟發(fā)式優(yōu)化基于代價(jià)估算的優(yōu)化兩者結(jié)合的優(yōu)化方法9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化一、選擇操作的啟發(fā)式規(guī)則:1.對于小關(guān)系，使用全表順序掃描，即使選

擇列上有索引對于大關(guān)系，啟發(fā)式規(guī)則有：2.對于選擇條件是主碼＝值的查詢查詢結(jié)果最多是一個(gè)元組，可以選擇主碼索引一般的RDBMS會自動建立主碼索引。3.對于選擇條件是非主屬性＝值的查詢，并且選擇列

上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描4.對于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描

5.對于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引,則優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引，則可以用［例1-C4］中介紹的索引掃描方法，否則使用全表順序掃描。

6.對于用OR連接的析取選擇條件，一般使用全表順序掃描二、連接操作的啟發(fā)式規(guī)則：

1.如果2個(gè)表都已經(jīng)按照連接屬性排序選用排序-合并方法

2.如果一個(gè)表在連接屬性上有索引選用索引連接方法

3.如果上面2個(gè)規(guī)則都不適用，其中一個(gè)表較小選用Hashjoin方法

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+(Br/K-1)Bs顯然應(yīng)該選塊數(shù)小的表作為外表9.4.2基于代價(jià)的優(yōu)化

啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系統(tǒng)解釋執(zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷之中編譯執(zhí)行的系統(tǒng)中查詢優(yōu)化和查詢執(zhí)行是分開的可以采用精細(xì)復(fù)雜一些的基于代價(jià)的優(yōu)化方法一、統(tǒng)計(jì)信息基于代價(jià)的優(yōu)化方法要計(jì)算各種操作算法的執(zhí)行代價(jià)，與數(shù)據(jù)庫的狀態(tài)密切相關(guān)數(shù)據(jù)字典中存儲的優(yōu)化器需要的統(tǒng)計(jì)信息：1.對每個(gè)基本表該表的元組總數(shù)(N)元組長度(l)占用的塊數(shù)(B)占用的溢出塊數(shù)(BO)

2.對基表的每個(gè)列該列不同值的個(gè)數(shù)(m)選擇率(f)如果不同值的分布是均