第15講數(shù)據(jù)庫查詢處理與優(yōu)化

第15講關(guān)系查詢與優(yōu)化1實例應(yīng)用實例假設(shè)學(xué)生-課程數(shù)據(jù)庫中有1000個學(xué)生，10000個選課記錄，其中選修“c02”課程的記錄為50個。一個磁盤塊能存儲10個S元組，或100個SC元組。用SQL語句表達(dá)查詢：選修了“c02”課程的學(xué)生姓名。用多種等價的關(guān)系代數(shù)表達(dá)式來完成這一查詢。分析該查詢在不同存儲結(jié)構(gòu)和索引結(jié)構(gòu)的磁盤I/O次數(shù)。2實例【例】查詢選修了“c02”課程的學(xué)生姓名

Q1:SELECTSN

FROMS，SC WHERES.Sno=SC.Sno ANDSC.Cno='c02';Q2:SELECTSNFROMS WHERESnoIN（SELECTSno

FROMSCWHERECno=‘c02’）；3實例【例】查詢選修了“c02”課程的學(xué)生姓名

π

Sn

(бS.Sno=SC.Sno∧SC.Cno='2'(S×SC))

πSn

(бSC.Cno='2'(S?SC))πSn

(S?бSC.Cno='2'(SC))

4關(guān)系查詢與優(yōu)化查詢處理步驟查詢優(yōu)化技術(shù)代數(shù)優(yōu)化物理優(yōu)化5查詢語句查詢解析器查詢分析

查詢預(yù)處理器關(guān)系代數(shù)查詢樹查詢優(yōu)化器查詢計劃的執(zhí)行代碼執(zhí)行引擎執(zhí)行結(jié)果查詢預(yù)處理

查詢優(yōu)化查詢執(zhí)行數(shù)據(jù)字典數(shù)據(jù)庫系統(tǒng)的查詢處理步驟

SELECTSnFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';語法分析樹關(guān)系代數(shù)優(yōu)化查詢樹查詢代碼生成器生成執(zhí)行代碼查詢處理器的組成和查詢處理的典型步驟6查詢分析與預(yù)處理

查詢分析接受類似SQL這樣的高級查詢語言表示的查詢，并進(jìn)行詞法分析和語法分析。7【例】在“學(xué)生-課程”數(shù)據(jù)庫中查詢選修了課程號為“c02”課程的學(xué)生姓名。查詢分析與預(yù)處理

Q1:SELECTSN FROMS，SC WHERES.Sno=SC.SnoANDSC.Cno='c02';

Q2:SELECTSN

FROMSWHERESnoIN（SELECTSno

FROMSCWHERECno=‘c02’）8【例】在“學(xué)生-課程”數(shù)據(jù)庫中查詢選修了課程號為“c02”課程的學(xué)生姓名。查詢分析與預(yù)處理用查詢語句Q1實現(xiàn)兩個關(guān)系的連接查詢的語法分析樹9【例】在“學(xué)生-課程”數(shù)據(jù)庫中查詢選修了課程號為“c02”課程的學(xué)生姓名。查詢分析與預(yù)處理用查詢語句Q2實現(xiàn)兩個關(guān)系的嵌套查詢的語法分析樹10查詢分析與預(yù)處理查詢有效性檢查根據(jù)數(shù)據(jù)字典對合法的查詢語句進(jìn)行語義檢查。檢查語句中的數(shù)據(jù)庫對象在所查詢的特定數(shù)據(jù)庫模式中是否為有效且有語義含義的名字。檢查所有屬性的類型是否與其使用相對應(yīng)，以及根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用戶的存取權(quán)限進(jìn)行檢查。11查詢分析與預(yù)處理生成關(guān)系代數(shù)初始查詢樹查詢預(yù)處理器采用一些相應(yīng)的規(guī)則，用一個或多個關(guān)系代數(shù)運算符替換語法樹上的結(jié)點與結(jié)構(gòu)，生成一個對應(yīng)于SQL查詢的關(guān)系代數(shù)初始查詢樹。關(guān)系代數(shù)查詢樹是一個樹數(shù)據(jù)結(jié)構(gòu)，在查詢樹中，查詢的輸入關(guān)系表示為葉結(jié)點，關(guān)系代數(shù)操作表示為內(nèi)部結(jié)點，一元關(guān)系操作符只有一個子結(jié)點，二元關(guān)系操作符有兩個子結(jié)點。

12查詢分析與預(yù)處理每個內(nèi)部節(jié)點用關(guān)系操作符來標(biāo)記，每個葉子結(jié)點用關(guān)系名來標(biāo)記。一元關(guān)系操作符只有一個孩子，二元操作符有兩個孩子。

Q1查詢的關(guān)系代數(shù)查詢樹【例】在“學(xué)生-課程”數(shù)據(jù)庫中查詢選修了課程號為“c02”課程的學(xué)生姓名。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))13查詢分析與預(yù)處理

Q2查詢的關(guān)系代數(shù)查詢樹【例】在“學(xué)生-課程”數(shù)據(jù)庫中查詢選修了課程號為“c02”課程的學(xué)生姓名。Q2：πSN(S?πSno(бSC.Cno='c02'(SC)))14查詢語句查詢解析器

查詢預(yù)處理器關(guān)系代數(shù)查詢樹查詢優(yōu)化器查詢計劃的執(zhí)行代碼執(zhí)行引擎執(zhí)行結(jié)果數(shù)據(jù)字典查詢分析與預(yù)處理SELECTSnFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';語法分析樹關(guān)系代數(shù)優(yōu)化查詢樹查詢代碼生成器πSn(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))

15由查詢優(yōu)化器將查詢預(yù)處理器所生成的關(guān)系代數(shù)初始查詢樹轉(zhuǎn)換成一個預(yù)期所需執(zhí)行時間較小的等價的關(guān)系代數(shù)查詢樹，得到一個可被轉(zhuǎn)換成最有效的物理查詢計劃的一個“優(yōu)化”的邏輯查詢計劃。代數(shù)優(yōu)化16代數(shù)優(yōu)化的必要性

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

【例】分析實現(xiàn)“查詢選修了課程號為‘c02’課程的學(xué)生姓名”的兩種關(guān)系代數(shù)查詢樹的執(zhí)行效率。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))Q2：πSN(S?πSno(бSC.Cno='c02'(SC)))17代數(shù)優(yōu)化的必要性

代數(shù)優(yōu)化在衡量代價時，需要使用如下一些參數(shù)：操作符使用的內(nèi)存大小M。假設(shè)內(nèi)存被分成緩沖區(qū)，緩沖區(qū)的大小與磁盤塊的大小相同。M表示一個特定的操作符執(zhí)行時可以獲得的內(nèi)存緩沖區(qū)的數(shù)目。關(guān)系R所占磁盤塊的大小B(R)通常假設(shè)R聚集存儲在B個塊或近似B個塊中。關(guān)系R中元組的數(shù)目T(R)一個塊中能容納的R的元組數(shù)可表示為T/B。關(guān)系R的一個屬性列上不同值的數(shù)目V(R,a)。18代數(shù)優(yōu)化【例】分析實現(xiàn)“查詢選修了課程號為‘c02’課程的學(xué)生姓名”的兩種關(guān)系代數(shù)查詢樹的執(zhí)行效率。（1）T(S)=1000，T(SC)=10000。選修“c02”課程的元組為50個。（2）假設(shè)數(shù)據(jù)記錄均為定長記錄，一個磁盤塊能存儲10個S元組記錄，或100個SC元組記錄。則B(S)=100，B(SC)=100。（3）對關(guān)系S和關(guān)系SC的連接采用嵌套循環(huán)方法，選擇關(guān)系S作為外循環(huán)關(guān)系。內(nèi)存的磁盤緩沖區(qū)M=7，可同時容納5塊關(guān)系S的磁盤塊、1塊關(guān)系SC的磁盤塊，1塊用于存放中間結(jié)果。（4）關(guān)系S和SC的運算結(jié)果裝滿一個緩沖區(qū)塊后需及時地由緩沖區(qū)存儲到磁盤上的中間文件中，一個緩沖區(qū)塊能存儲10個運算結(jié)果記錄。（5）假設(shè)緩沖區(qū)管理器每秒讀寫20個磁盤塊。代數(shù)優(yōu)化的必要性

191.計算廣義笛卡爾積S×SC

代數(shù)優(yōu)化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))20…

10個S元組……100個SC元組……10個SC×S元組……10個S元組…

100個SC元組

…

10個SC×S元組…磁盤B(S)=100塊B(SC)=100塊T(S)*T(SC)/105塊1塊1塊內(nèi)存20次100次106次代數(shù)優(yōu)化211.計算廣義笛卡爾積S×SC

讀取關(guān)系S和關(guān)系SC的總的磁盤塊數(shù)=讀取關(guān)系S的磁盤塊數(shù)+讀取關(guān)系SC的遍數(shù)×每遍讀取的關(guān)系SC的磁盤塊數(shù)=B(S)+(100/5)×B(SC)=100+20×100=2100（塊）

讀數(shù)據(jù)時間=2100/20=105秒運算中間結(jié)果元組數(shù)=1000*10000=107

運算中間結(jié)果需占用的磁盤塊數(shù)=107/10=106（塊）

運算中間結(jié)果寫入磁盤時間=107/10/20=5×104秒

代數(shù)優(yōu)化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))222.選擇操作бS.Sno=SC.Sno∧SC.Cno='c02'

選擇操作執(zhí)行時間=中間結(jié)果文件讀取時間=運算中間結(jié)果寫入磁盤時間=5×104（s）

運算結(jié)果只有50條記錄，可駐留內(nèi)存。3.投影操作πSN

對內(nèi)存的50條記錄進(jìn)行操作，忽略不計。

查詢Q1所需總時間=105＋5×104

＋5×104

=100105（s）≈27.8（h）代數(shù)優(yōu)化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))231.讀SC作選擇和投影πSno(бSC.Cno='c02'(SC))

讀取關(guān)系SC的磁盤塊數(shù)=B(SC)=100（塊）讀數(shù)據(jù)時間=100/20=5（s）在內(nèi)存中，對讀取的數(shù)據(jù)進(jìn)行選擇和投影操作，時間忽略不計。滿足條件的中間結(jié)果元組數(shù)=50，駐留內(nèi)存，不必用中間文件。2.讀S作連接和投影πSN(S?πSno(бSC.Cno='c02'(SC)

))

讀取關(guān)系S的磁盤塊數(shù)=B(S)=100（塊）讀數(shù)據(jù)時間=100/20=5（s）在內(nèi)存中，對讀取的S元組與50個選課元組進(jìn)行連接操作后投影，時間忽略不計。查詢Q2所需總時間=5＋5=10（s）

代數(shù)優(yōu)化≈Q2：πSN(S?πSno(бSC.Cno='c02'(SC)))24代數(shù)優(yōu)化的必要性

對于實現(xiàn)同一查詢的不同的關(guān)系代數(shù)表達(dá)式（查詢樹），其操作的次序不同，查詢效率不同，查詢時間相差很大。有必要對查詢預(yù)處理器產(chǎn)生的關(guān)系代數(shù)初始查詢樹進(jìn)行優(yōu)化，得到較優(yōu)的邏輯查詢計劃，而不管用戶書寫的SQL查詢是什么形式。代數(shù)優(yōu)化如何改變關(guān)系代數(shù)表達(dá)式的操作次序，提高其查詢效率？25代數(shù)優(yōu)化

關(guān)系代數(shù)表達(dá)式（查詢樹）的優(yōu)化就是指按照一定的規(guī)則，改變關(guān)系代數(shù)表達(dá)式中操作的次序和組合，將其轉(zhuǎn)換為一個可以更高效執(zhí)行的關(guān)系代數(shù)表達(dá)式（查詢樹）。基于代數(shù)等價的啟發(fā)式優(yōu)化代數(shù)優(yōu)化26基于代數(shù)等價的啟發(fā)式優(yōu)化通過利用一些啟發(fā)式規(guī)則，將一個代數(shù)表達(dá)式轉(zhuǎn)換為另一個不同的但等價的代數(shù)表達(dá)式，產(chǎn)生可被進(jìn)一步優(yōu)化的查詢執(zhí)行計劃。關(guān)系代數(shù)表達(dá)式等價：指用相同的關(guān)系實例代替兩個表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的。代數(shù)優(yōu)化27基于代數(shù)等價的啟發(fā)式優(yōu)化常用的等價變換規(guī)則設(shè)E、E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)、F1、F2是條件表達(dá)式1.連接、笛卡爾積交換律

E1×E2≡E2×E1 E1?E2≡E2?E1 E1?FE2≡E2?FE12.連接、笛卡爾積的結(jié)合律

(E1×E2)×E3≡E1×(E2×E3)(E1?E2)?E3≡E1?(E2?E3)(E1?F1E2)?F2E3≡E1?F1(E2?F2E3)代數(shù)優(yōu)化28基于代數(shù)等價的啟發(fā)式優(yōu)化常用的等價變換規(guī)則3.投影的串接定律

π

A1,A2,

…,An(πB1,B2,…,Bm(E))≡πA1,A2,…,An(E){A1,A2,…,An}構(gòu)成{B1，B2，…，Bm}的子集

4.選擇的串接定律

бF1(бF2(E))≡бF1∧F2(E)代數(shù)優(yōu)化29基于代數(shù)等價的啟發(fā)式優(yōu)化常用的等價變換規(guī)則5.選擇與投影的交換律

бF

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

F只涉及屬性A1，…，An

πA1,A2,…,An

(

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

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

F中有不屬于A1,…,An的屬性B1,…,Bm代數(shù)優(yōu)化30基于代數(shù)等價的啟發(fā)式優(yōu)化常用的等價變換規(guī)則6.選擇與笛卡爾積的交換律

бF(E1×E2)≡бF(E1)×E2

F中涉及的屬性都是E1中的屬性

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

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

бF(E1×E2)≡бF2(бF1(E1)×E2)F=F1∧F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性代數(shù)優(yōu)化31基于代數(shù)等價的啟發(fā)式優(yōu)化常用的等價變換規(guī)則7.選擇對自然連接的分配律

бF(E1?E2)≡бF(E1)?бF(E2)

F是只涉及E1和E2的公共屬性8.選擇對并的分配律

бF(E1∪E2)≡бF(E1)∪бF(E2)

E1與E2有相同的屬性或?qū)傩杂袑?yīng)性

9.選擇對差運算的分配律

бF(E1-E2)≡бF(E1)-бF(E2)

E1、E2有相同的屬性或?qū)傩杂袑?yīng)性代數(shù)優(yōu)化32基于代數(shù)等價的啟發(fā)式優(yōu)化常用的等價變換規(guī)則10.投影對笛卡爾積的分配律

πA1,A2,…,An,B1,B2,…,Bm(E1×E2)≡πA1,A2,…,An(E1)×πB1,B2,…,Bm(E2)A1，…，An是E1的屬性，B1，…，Bm是E2的屬性11.投影對并的分配律

πA1,A2,…,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)12.選擇與連接運算的結(jié)合бF(E1×E2)≡E1?FE2

бF1(E1?F2E2)≡E1?F1∧F2E2代數(shù)優(yōu)化33基于代數(shù)等價的啟發(fā)式優(yōu)化主要的啟發(fā)式規(guī)則

選擇運算應(yīng)盡可能先做投影運算和選擇運算同時進(jìn)行將投影運算與其前面或后面的雙目運算結(jié)合某些選擇運算同在其前面執(zhí)行的笛卡爾積結(jié)合成為一個連接運算提取公共子表達(dá)式

代數(shù)優(yōu)化34基于代數(shù)等價的啟發(fā)式優(yōu)化啟發(fā)式代數(shù)優(yōu)化算法輸入：一個關(guān)系代數(shù)查詢樹輸出：計算關(guān)系代數(shù)表達(dá)式的一個優(yōu)化序列步驟：（1）分解選擇運算（2）交換選擇運算，將其盡可能移到葉端（3）交換投影運算，將其盡可能移到葉端（4）合并串接的選擇和投影運算（5）對內(nèi)結(jié)點分組每個二元運算(×，?，∪，-)和它所有的直接祖先為一組。如果其后代直到葉子全是單目運算，則也將它們并入該組。（6）生成優(yōu)化序列代數(shù)優(yōu)化35代數(shù)優(yōu)化基于代數(shù)等價的啟發(fā)式優(yōu)化【例】利用優(yōu)化算法對執(zhí)行效率較低的查詢Q1的查詢樹進(jìn)行優(yōu)化。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))

πSN(бS.Sno=SC.Sno(

б

SC.Cno=‘c02’(S×SC)))

πSN(бS.Sno=SC.Sno(

б

SC.Cno=‘c02’(SC×S)))

πSN(бS.Sno=SC.Sno(

б

SC.Cno=‘c02’(SC)×S))

πSN

(

б

SC.Cno=‘c02’(SC)?S))

36代數(shù)優(yōu)化基于代數(shù)等價的啟發(fā)式優(yōu)化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))37代數(shù)優(yōu)化基于代數(shù)等價的啟發(fā)式優(yōu)化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'

(S×SC))

38代數(shù)優(yōu)化基于代數(shù)等價的啟發(fā)式優(yōu)化【例7-5】供應(yīng)商零件數(shù)據(jù)庫中有供應(yīng)商、零件、項目和供應(yīng)四個基本關(guān)系：供應(yīng)商關(guān)系S(Sno，Sname，Status，City)零件關(guān)系P(Pno，Pname，Color，Weight)工程項目關(guān)系J(Jno，Jname，City)供應(yīng)情況關(guān)系SPJ(Sno，Pno，Jno，Qty)查詢：檢索使用上海供應(yīng)商生產(chǎn)的紅色零件的工程號。試寫出該查詢盡可能優(yōu)化的關(guān)系代數(shù)表達(dá)式，并畫出對應(yīng)的關(guān)系代數(shù)查詢樹。

39

物理優(yōu)化物理優(yōu)化從一個邏輯查詢計劃產(chǎn)生物理查詢計劃時，為邏輯查詢計劃的每一個操作符選擇實現(xiàn)算法并選擇這些操作符的執(zhí)行順序，還包括許多實現(xiàn)細(xì)節(jié)。被查詢的關(guān)系是怎樣被訪問的，即獲得所存儲數(shù)據(jù)的方式以及一個關(guān)系何時或是否應(yīng)當(dāng)被排序等；必須估計每個可能選項的執(zhí)行代價，使用代價估計來評價一個查詢計劃。40

物理優(yōu)化操作符的實現(xiàn)算法

每一個操作符實現(xiàn)算法的選擇是將邏輯查詢計劃轉(zhuǎn)變?yōu)槲锢聿樵冇媱澾^程中的一個必不可少的部分。針對各種操作符，已提出了很多算法，大體上分為三類：基于排序的方法基于散列的方法基于索引的方法41

物理優(yōu)化操作符的實現(xiàn)算法

對算法的描述仍使用磁盤I/O的次數(shù)作為衡量每個查詢的代價的標(biāo)準(zhǔn)和使用如下參數(shù)：操作符使用的內(nèi)存大小M。關(guān)系R所占磁盤塊的大小B(R)關(guān)系R中元組的數(shù)目T(R)關(guān)系R的一個屬性列上不同值的數(shù)目V(R,a)。42

物理優(yōu)化操作符的實現(xiàn)算法

選擇操作的實現(xiàn)算法

選擇操作σc(R)是讀取關(guān)系R中那些滿足謂詞條件C的元組，定位這些元組的基本方法有兩種：簡單的全表掃描方法索引掃描法43

物理優(yōu)化操作符的實現(xiàn)算法

選擇操作的實現(xiàn)算法簡單的全表掃描方法如果R是聚集的，那么全表掃描的代價近似為B(R)。如果R不是聚集的，那么全表掃描所需的I/O代價為T(R)。44

物理優(yōu)化操作符的實現(xiàn)算法

選擇操作的實現(xiàn)算法索引掃描法假設(shè)條件C是a=v

的形式，a是一個存在著索引的屬性，v是一個值。如果R.a上的索引是聚集的，具有某一a值的元組平均聚集分布在B(R)/V(R,a)個磁盤塊中，讀取σa=v(R)所需的磁盤I/O的次數(shù)將大約是B(R)/V(R,a)。如果a是R的一個關(guān)鍵字，那么V(R,a)=T(R)，至少需要一次磁盤I/O去讀取具有關(guān)鍵字值為v的元組。如果R.a上的索引是非聚集的，大約訪問T(R)/V(R,a)個元組。T(R)/V(R,a)是估計的磁盤I/O次數(shù)。45

物理優(yōu)化【例7-6】假設(shè)B(R)=1000，T(R)=20000，即R有20000個元組可存放在1000個磁盤塊中。假設(shè)a是R的一個屬性，且在a上有一個索引，估計σa=0(R)的代價。①如果R是聚集的，不使用索引，則需進(jìn)行全表掃描，那么代價是1000次磁盤I/O。②如果R不是聚集的，而且不使用索引，則需進(jìn)行全表掃描，那么代價是20000次磁盤I/O。③如果V(R,a)=100并且索引是聚集的，那么相同a值的元組聚集存儲在平均B(R)/V(R,a)塊磁盤塊中，因此基于索引的算法需要1000/100=10次磁盤I/O。④如果V(R,a)=100并且索引是非聚集的，那么相同a值的元組可能隨機存儲在T(R)/V(R,a)塊磁盤塊中，因此基于索引的算法需要20000/100=200次磁盤I/O。⑤如果V(R,a)=20000，即a是一個關(guān)鍵字，那么基于索引的算法，不管索引是聚集的或是非聚集的，都將需要1次磁盤I/O。46

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法在下面的連接算法中，將R(X,Y)與S(Y,Z)連接，Y表示R和S的所有公共屬性，X是R的所有不在S模式中的屬性，Z是S的所有不在R模式中的屬性。假設(shè)S是較小的關(guān)系。

47

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法一趟連接運算假設(shè)較小的關(guān)系S，可存入內(nèi)存的M-1塊中。讀取S的所有元組，并且構(gòu)造一個以Y屬性為查找關(guān)鍵字的內(nèi)存查找結(jié)構(gòu)。將R的每一磁盤塊中的元組讀到內(nèi)存中剩下的那一個緩沖區(qū)中。對于R的每一個元組t，利用查找結(jié)構(gòu)找到S中與t在Y的所有屬性上相符合的元組。對于S中每一個匹配的元組，將它與t配對后形成一個元組，并且將結(jié)果元組移到輸出文件中。讀取操作對象需要B(S)+B(R)次磁盤I/O，僅從磁盤讀取一次數(shù)據(jù)。48…S元組……R元組……R×S元組……S元組…R元組

…R×S元組…磁盤B(S)≤M-1

M-1塊1塊1塊緩沖區(qū)一趟連接運算

物理優(yōu)化1次1次B(R)49

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法嵌套循環(huán)連接嵌套循環(huán)連接算法是對外層循環(huán)關(guān)系（如S）中的每條元組，檢查內(nèi)層循環(huán)關(guān)系（如R）中的每個元組是否滿足連接條件，如果滿足條件，則連接后作為結(jié)果輸出，直到外層循環(huán)關(guān)系中的元組處理完為止?；趬K的嵌套循環(huán)連接算法對作為操作對象的兩個關(guān)系的訪問均按塊組織，假定B(S)≤B(R)，并且B(S)＞M。使用盡可能多的內(nèi)存來存儲屬于較小關(guān)系S的元組，S是外層循環(huán)中的關(guān)系。

50

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法基于塊的嵌套循環(huán)連接算法①讀取關(guān)系S的M-1個磁盤塊中的元組到內(nèi)存緩沖區(qū)中。②為S在內(nèi)存中的元組創(chuàng)建一個查找結(jié)構(gòu)，它的查找關(guān)鍵字是R和S的公共屬性。③瀏覽R的所有塊，依次讀取每一塊到內(nèi)存M塊中的最后一塊中。④在讀入R的一個塊后，將塊中所有元組與S在內(nèi)存中的所有塊中的所有元組進(jìn)行比較。對于那些能連接的元組，輸出連接得到的元組。⑤重復(fù)執(zhí)行前面的步驟，直到處理完S中所有磁盤塊中的數(shù)據(jù)。讀取數(shù)據(jù)的磁盤I/O次數(shù)是B(S)+(B(S)B(R))/(M-1)。

51…S元組…S元組…R元組……R×S元組……S元組…R元組

…R×S元組…磁盤B(S)＞M

B(R)M-1塊1塊緩沖區(qū)基于塊的嵌套循環(huán)連接算法

物理優(yōu)化1次B(S)/(M-1)次52

物理優(yōu)化【例7-7】假定B(R)=1000，B(S)=500，M=101。使用100個內(nèi)存塊的緩沖區(qū)來對S進(jìn)行緩沖。計算采用基于塊的嵌套循環(huán)連接算法代價。算法中的外層循環(huán)需循環(huán)5次。在每次外循環(huán)中，用100次磁盤I/O讀取S的數(shù)據(jù)塊組。在內(nèi)循環(huán)中用1000次磁盤I/O來讀取R。因此，運算中讀取數(shù)據(jù)需要5×(100+1000)=5500次磁盤I/O。如果交換內(nèi)外循環(huán)中的關(guān)系，外循環(huán)需執(zhí)行10次。每次外循環(huán)需進(jìn)行100+500=600次磁盤I/O，總共6000次。所以，在外循環(huán)中使用較小的關(guān)系，算法使用的磁盤I/O要略少一些，略有優(yōu)勢。53

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法排序-歸并連接關(guān)系R和S按照連接屬性Y有序聚集存儲。兩個緩沖區(qū)，一個給R的當(dāng)前塊，另一個給S的當(dāng)前塊。①按照連接屬性的順序?qū)﹃P(guān)系R和S并發(fā)地進(jìn)行物理順序掃描，把關(guān)系R和S的首個磁盤塊中的元組讀入內(nèi)存緩沖區(qū)。②在讀入內(nèi)存的當(dāng)前R和S的元組中順序查找連接屬性Y的最小匹配值y。如果需要，從排序的R和/或S中繼續(xù)讀取下一個磁盤塊，直到找到最小匹配值y。③連接內(nèi)存中R和S的具有相同y值的所有元組。如果一個關(guān)系在內(nèi)存中已沒有未考慮的元組，就順序讀取該文件的下一個磁盤塊，直到處理完兩個關(guān)系中具有相同y值的所有元組。④在內(nèi)存R和S的元組中順序查找連接屬性Y的下一個匹配值y，從步驟3開始重復(fù)執(zhí)行。直到處理完某一關(guān)系的所有磁盤塊中的元組。54…S元組……R元組……R×S元組……S元組R元組

…R×S元組…磁盤B(S)B(R)1塊1塊緩沖區(qū)排序-歸并連接算法

物理優(yōu)化1次1次讀取操作對象需要B(S)+B(R)次磁盤I/O，僅從磁盤讀取一次數(shù)據(jù)。55

物理優(yōu)化【例7-8】假定B(R)=1000，B(S)=500，M=101。假設(shè)R和S均已按屬性Y排序，計算采用排序歸并連接算法代價。用1500次磁盤I/O來讀取R和S的每一個塊，僅需要101個內(nèi)存塊中的兩個。如果需要可以使用所有101塊來容納具有公共Y值的R和S的元組。56

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法基于散列的連接算法的基本思想是如果數(shù)據(jù)量太大以至于不能存入內(nèi)存緩沖區(qū)中，可使用一個合適的散列鍵散列一個或多個操作對象的所有元組。然后通過一次處理具有相同散列值的一對桶的方式執(zhí)行操作。假設(shè)h是散列函數(shù)，用連接屬性Y作散列鍵，來散列兩個關(guān)系R和S的元組，將元組散列到適當(dāng)?shù)纳⒘型爸?。如果R與S的元組能連接，那么它們必然出現(xiàn)在具有某個i值的對應(yīng)的桶Ri和Si中。57

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法基于散列的連接算法每一個桶對中有一個能全部裝入M-1個緩沖區(qū)中。

①可按桶號i的大小將包含較少磁盤塊的桶（Si中的桶）讀入到內(nèi)存的緩沖區(qū)中，構(gòu)造內(nèi)存中的一個散列查找結(jié)構(gòu)。②讀入另一關(guān)系R中的與Si對應(yīng)的桶Ri，將讀入的Ri中的元組與內(nèi)存中Si中的記錄進(jìn)行連接，將連接的結(jié)果進(jìn)行輸出。③重復(fù)以上步驟，直到S中的所有桶處理完。連接操作讀取操作對象需要B(S)+B(R)次磁盤I/O，僅從磁盤讀取一次數(shù)據(jù)。

58…S元組……R元組……R×S元組……S(Ki)元組…R(Ki)元組

…R×S元組…磁盤B(S)B(R)M-1塊1塊緩沖區(qū)基于散列的連接算法

物理優(yōu)化1次1次S(Ki)S(Ki)R(Ki)R(Ki)59

物理優(yōu)化【例7-9】假定B(R)=1000，B(S)=500，M=101。假設(shè)R和S均已按屬性Y排序，計算采用基于散列的連接算法代價。假設(shè)以連接屬性Y作為散列鍵將R和S分別散列到100個桶中，則一個桶的平均大小對于R占10個磁盤塊，對于S占5個磁盤塊。遠(yuǎn)遠(yuǎn)小于101塊可用的緩沖區(qū)數(shù)量。所以在每一個桶對上執(zhí)行一趟連接即可完成運算。執(zhí)行對應(yīng)桶的一次連接需1500次磁盤I/O。60

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法基于索引的連接運算如果一個關(guān)系（如S）有一個屬性Y上的索引。①讀入R的一個磁盤塊，考慮塊中每一個元組t，令ty是元組t中y屬性的值。②使用S上的索引，來找到S中所有在Y屬性上具有相同ty的那些元組所在的磁盤塊，將這些元組（所在的磁盤塊）讀入內(nèi)存與R中的元組t連接起來，作為結(jié)果輸出。③重復(fù)以上步驟，直到R中的所有元組處理完。61…S元組…S元組…R元組

…R×S元組……S(ty)元組…R(ty)元組

…R×S元組…磁盤B(S)B(R)1塊1塊緩沖區(qū)基于索引的連接算法

物理優(yōu)化tyty

S的索引62

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法基于索引的連接運算如果R是聚集的，將需要讀取B(R)個塊來得到R的所有元組。如果R是非聚集的，那么可能會需要將近T(R)個磁盤I/O來讀取R的所有元組。對于R的每一個元組，將平均讀取S的T(S)/V(S,Y)個元組。如果S在Y上有一個非聚集的索引，那么讀取S所需的磁盤I/O的次數(shù)是T(R)T(S)/V(S,Y)。如果S上的索引是聚集的，那么僅T(R)B(S)/V(S,Y)次磁盤I/O就夠了。對于算法中的每一個Y值，可能需要增加幾次磁盤I/O，用于讀取相關(guān)索引文件。63

物理優(yōu)化【例7-10】假定B(R)=1000，B(S)=500，M=101。假設(shè)一個塊可以容納每個關(guān)系的10個元組，即T(R)=10000，T(S)=5000，同時假設(shè)V(S,Y)=100。計算采用基于索引的連接算法代價。如果R是聚集的，需要1000次磁盤I/O用來讀取R的所有元組。S在Y上有一個聚集索引，需要10000×500/100=50000次磁盤I/O讀取S。如果R是非聚集的或S上的索引是非聚集的，代價會更高。64

物理優(yōu)化操作符的實現(xiàn)算法

連接操作的實現(xiàn)算法基于索引的連接運算常見的連接查詢的情況是與S相比，R是很小的，V(S,Y)是很大的。在這種情況下，S的大多數(shù)元組的Y值根本不出現(xiàn)在R中，這些元組將無需被算法檢查，即不需要讀入內(nèi)存。但是，不論基于排序的還是基于散列的連接方法都需檢查S的每一個元組至少一次。所以，在實際的應(yīng)用中，索引選擇算法仍是一種常用的方法。65【例】分析實現(xiàn)“查詢選修了課程號為‘c02’課程的學(xué)生姓名”（1）T(S)=1000，T(SC)=10000。選修“c02”課程的元組為50個。（2）一個磁盤塊能存儲10個S元組記錄，或100個SC元組記錄。則B(S)=100，B(SC)=100。

Q1:SELECTSN FROMS，SC WHERES.Sno=SC.SnoANDSC.Cno='c02';

Q1：πSN((бSC.Cno='c02'(SC)?S))——————————R

物理優(yōu)化66

物理優(yōu)化物理優(yōu)化從一個邏輯查詢計劃產(chǎn)生物理查詢計劃時，為邏輯查詢計劃的每一個操作符選擇實現(xiàn)算法并選擇這些操作符的執(zhí)行順序，還包括許多實現(xiàn)細(xì)節(jié)。被查詢的關(guān)系是怎樣被訪問的，即獲得所存儲數(shù)據(jù)的方式以及一個關(guān)系何時或是否應(yīng)當(dāng)被排序等；必須估計每個可能選項的執(zhí)行代價，使用代價估計來評價一個查詢計劃。67基于代價的物理優(yōu)化方法查詢計劃的代價因素一個查詢的實際執(zhí)行所需的代價包括:磁盤訪問代價：讀寫記錄所在磁盤數(shù)據(jù)塊的代價。存儲代價：存儲由查詢執(zhí)行計劃產(chǎn)生的中間結(jié)果文件的代價。計算代價：在查詢執(zhí)行過程中對數(shù)據(jù)緩沖區(qū)完成內(nèi)存操作的代價。內(nèi)存使用代價：與執(zhí)行查詢所需內(nèi)存緩沖區(qū)數(shù)相關(guān)的代價。通信代價：將查詢與查詢結(jié)果從一個數(shù)據(jù)庫站點傳送到另一個站點（或發(fā)出查詢的終端）的代價。

物理優(yōu)化68基于代價的物理優(yōu)化方法查詢計劃的代價因素代價用的磁盤I/O次數(shù)受以下因素影響：在選擇邏輯查詢計劃時所選取的用于實現(xiàn)查詢的邏輯查詢運算符，例如進(jìn)行乘積運算還是連接運算。中間關(guān)系的大小。用于實現(xiàn)邏輯查詢運算符的物理查詢運算符，例如連接運算算法的選擇，對給定關(guān)系是否加以排序等其他運算。由一個物理運算符向下一個物理運算符傳遞參數(shù)的方式，例如，通過在磁盤上保存中間結(jié)果還是通過使用迭代算子每次傳送一個參數(shù)的一個元組或一個主存緩沖區(qū)。

物理優(yōu)化69基于代價的物理優(yōu)化方法查詢計劃的代價因素在對由給定的邏輯查詢計劃導(dǎo)出可能的物理查詢計劃進(jìn)行評價時，我們需要知道各個物理計劃的代價是多少。在不執(zhí)行查詢計劃的情況下，我們不能準(zhǔn)確知道其代價。由于執(zhí)行一個查詢計劃比查詢編譯器選擇一個計劃所做的工作要多得多，我們需要不執(zhí)行查詢計劃而估計該計劃的代價。要準(zhǔn)確估計不同查詢計劃的代價，查詢優(yōu)化器需要從數(shù)據(jù)庫中有效地獲得某些重要的參數(shù)信息，即從數(shù)據(jù)字典中獲取代價估計所需的各種信息。

物理優(yōu)化70基于代價的物理優(yōu)化方法代價估計基于的數(shù)據(jù)信息對每個關(guān)系表文件，該表的記錄總數(shù)（T）、記錄長度、占用的塊數(shù)（B）、占用的溢出塊數(shù)（BO）；對關(guān)系表文件的每個屬性，該屬性不同值的個數(shù)（V）、選擇率（具有該值的記錄數(shù)/T）、該屬性最大值、最小值，該屬性上是否已建索引，何種索引（B+樹索引、散列索引、聚集索引）；對于索引，比如B+樹索引，該索引的層數(shù)（L）、不同索引值的個數(shù)、索引的選擇基數(shù)S（有S個元組有某個索引值）、索引的葉結(jié)點數(shù)（Y）等等。

物理優(yōu)化優(yōu)化器可以根據(jù)這些信息作出正確的估算，選擇高效的執(zhí)行計劃。

71基于代價的物理優(yōu)化方法物理查詢計劃的選擇方法

由給定的邏輯查詢計劃可有多個可能的物理查詢計劃，要窮盡所有的查詢計劃進(jìn)行代價估算往往是不可行的，會造成查詢優(yōu)化本身付出的代價大于獲得的益處。常常先使用啟發(fā)式規(guī)則，選取若干較優(yōu)的候選方案，減少代價估算的工作量；然后分別計算這些候選方案的執(zhí)行代價，較快地選出最終的優(yōu)化方案。

物理優(yōu)化72基于代價的物理優(yōu)化方法物理查詢計劃的選擇方法

啟發(fā)式選擇某些操作（如選擇和連接操作）可以有多種執(zhí)行這個操作的算法，可以根據(jù)一些啟發(fā)式規(guī)則來選擇代價較小的實現(xiàn)操作的算法。

物理優(yōu)化73基于代價的物理優(yōu)化方法物理查詢計劃的選擇方法

常用的啟發(fā)式規(guī)則（1）選擇操作若關(guān)系R的元組數(shù)較小，比如T(R)<M，可采用簡單的全表掃描方法，即使選擇列上有索引。如果邏輯計劃需要進(jìn)行σa=v(R)操作，且關(guān)系R在屬性a上有索引，則使用索引掃描法。對于更一般的選擇操作，如選擇涉及a=v那樣的一個條件以及其他條件，可以先進(jìn)行一次索引掃描，然后對選中的元組作進(jìn)一步選擇（也稱過濾）。

物理優(yōu)化74基于代價的物理優(yōu)化方法物理查詢計劃的選擇方法

常用的啟發(fā)式規(guī)則（2）連接操作如果兩個關(guān)系都已經(jīng)按照連接屬性排序，則選用排序-歸并算法。如果一個關(guān)系在連接屬性上有索引，則選用索引連接方法，其中該關(guān)系在算法內(nèi)層循環(huán)中（即算法中的關(guān)系S，可通過連接運算的交換律來滿足）。如果前兩個規(guī)則不適用，而其中一個關(guān)系較小，則可以選用散列連接方法。最后可以選用嵌套循環(huán)方法，并選擇其中較小的關(guān)系，即占用的磁盤塊數(shù)較小的關(guān)系作為算法的外循環(huán)中的關(guān)系（即算法中的關(guān)系S）。

物理優(yōu)化75基于代價的物理優(yōu)化方法物理查詢計劃的選擇方法

基于代價估算的選擇查詢優(yōu)化器可通過估計每一個可能的物理查詢計劃的代價，比較并選擇估計代價最小的查詢計劃。以選擇操作為例說明在邏輯查詢計劃到物