第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語句表達查詢：選修了“c02”課程的學(xué)生姓名。用多種等價的關(guān)系代數(shù)表達式來完成這一查詢。分析該查詢在不同存儲結(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這樣的高級查詢語言表示的查詢，并進行詞法分析和語法分析。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ù)字典對合法的查詢語句進行語義檢查。檢查語句中的數(shù)據(jù)庫對象在所查詢的特定數(shù)據(jù)庫模式中是否為有效且有語義含義的名字。檢查所有屬性的類型是否與其使用相對應(yīng)，以及根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用戶的存取權(quá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條記錄進行操作，忽略不計。

查詢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ù)進行選擇和投影操作，時間忽略不計。滿足條件的中間結(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個選課元組進行連接操作后投影，時間忽略不計。查詢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ù)表達式（查詢樹），其操作的次序不同，查詢效率不同，查詢時間相差很大。有必要對查詢預(yù)處理器產(chǎn)生的關(guān)系代數(shù)初始查詢樹進行優(yōu)化，得到較優(yōu)的邏輯查詢計劃，而不管用戶書寫的SQL查詢是什么形式。代數(shù)優(yōu)化如何改變關(guān)系代數(shù)表達式的操作次序，提高其查詢效率？25代數(shù)優(yōu)化

關(guān)系代數(shù)表達式（查詢樹）的優(yōu)化就是指按照一定的規(guī)則，改變關(guān)系代數(shù)表達式中操作的次序和組合，將其轉(zhuǎn)換為一個可以更高效執(zhí)行的關(guān)系代數(shù)表達式（查詢樹）?；诖鷶?shù)等價的啟發(fā)式優(yōu)化代數(shù)優(yōu)化26基于代數(shù)等價的啟發(fā)式優(yōu)化通過利用一些啟發(fā)式規(guī)則，將一個代數(shù)表達式轉(zhuǎn)換為另一個不同的但等價的代數(shù)表達式，產(chǎn)生可被進一步優(yōu)化的查詢執(zhí)行計劃。關(guān)系代數(shù)表達式等價：指用相同的關(guān)系實例代替兩個表達式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的。代數(shù)優(yōu)化27基于代數(shù)等價的啟發(fā)式優(yōu)化常用的等價變換規(guī)則設(shè)E、E1、E2等是關(guān)系代數(shù)表達式，F(xiàn)、F1、F2是條件表達式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)盡可能先做投影運算和選擇運算同時進行將投影運算與其前面或后面的雙目運算結(jié)合某些選擇運算同在其前面執(zhí)行的笛卡爾積結(jié)合成為一個連接運算提取公共子表達式

代數(shù)優(yōu)化34基于代數(shù)等價的啟發(fā)式優(yōu)化啟發(fā)式代數(shù)優(yōu)化算法輸入：一個關(guān)系代數(shù)查詢樹輸出：計算關(guān)系代數(shù)表達式的一個優(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的查詢樹進行優(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ù)表達式，并畫出對應(yīng)的關(guān)系代數(shù)查詢樹。

39

物理優(yōu)化物理優(yōu)化從一個邏輯查詢計劃產(chǎn)生物理查詢計劃時，為邏輯查詢計劃的每一個操作符選擇實現(xiàn)算法并選擇這些操作符的執(zhí)行順序，還包括許多實現(xiàn)細節(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是聚集的，不使用索引，則需進行全表掃描，那么代價是1000次磁盤I/O。②如果R不是聚集的，而且不使用索引，則需進行全表掃描，那么代價是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)存中的所有塊中的所有元組進行比較。對于那些能連接的元組，輸出連接得到的元組。⑤重復(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進行緩沖。計算采用基于塊的嵌套循環(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)需進行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ā)地進行物理順序掃描，把關(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中的記錄進行連接，將連接的結(jié)果進行輸出。③重復(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個磁盤塊。遠遠小于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)細節(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)查詢的邏輯查詢運算符，例如進行乘積運算還是連接運算。中間關(guān)系的大小。用于實現(xiàn)邏輯查詢運算符的物理查詢運算符，例如連接運算算法的選擇，對給定關(guān)系是否加以排序等其他運算。由一個物理運算符向下一個物理運算符傳遞參數(shù)的方式，例如，通過在磁盤上保存中間結(jié)果還是通過使用迭代算子每次傳送一個參數(shù)的一個元組或一個主存緩沖區(qū)。

物理優(yōu)化69基于代價的物理優(yōu)化方法查詢計劃的代價因素在對由給定的邏輯查詢計劃導(dǎo)出可能的物理查詢計劃進行評價時，我們需要知道各個物理計劃的代價是多少。在不執(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)化方法物理查詢計劃的選擇方法

由給定的邏輯查詢計劃可有多個可能的物理查詢計劃，要窮盡所有的查詢計劃進行代價估算往往是不可行的，會造成查詢優(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，可采用簡單的全表掃描方法，即使選擇列上有索引。如果邏輯計劃需要進行σa=v(R)操作，且關(guān)系R在屬性a上有索引，則使用索引掃描法。對于更一般的選擇操作，如選擇涉及a=v那樣的一個條件以及其他條件，可以先進行一次索引掃描，然后對選中的元組作進一步選擇（也稱過濾）。

物理優(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)化器可通過估計每一個可能的物理查詢計劃的代價，比較并選擇估計代價最小的查詢計劃。以選擇操作為例說明在邏輯查詢計劃到物