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

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

Q1:SELECTSN

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

FROMSCWHERECno=‘c02’）；3實(shí)例【例】查詢選修了“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)化器查詢計(jì)劃的執(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í)查詢語言表示的查詢，并進(jìn)行詞法分析和語法分析。7【例】在“學(xué)生-課程”數(shù)據(jù)庫中查詢選修了課程號(hào)為“c02”課程的學(xué)生姓名。查詢分析與預(yù)處理

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

Q2:SELECTSN

FROMSWHERESnoIN（SELECTSno

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

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

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

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

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

查詢預(yù)處理器關(guān)系代數(shù)查詢樹查詢優(yōu)化器查詢計(jì)劃的執(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)換成一個(gè)預(yù)期所需執(zhí)行時(shí)間較小的等價(jià)的關(guān)系代數(shù)查詢樹，得到一個(gè)可被轉(zhuǎn)換成最有效的物理查詢計(jì)劃的一個(gè)“優(yōu)化”的邏輯查詢計(jì)劃。代數(shù)優(yōu)化16代數(shù)優(yōu)化的必要性

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

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

191.計(jì)算廣義笛卡爾積S×SC

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

(S×SC))20…

10個(gè)S元組……100個(gè)SC元組……10個(gè)SC×S元組……10個(gè)S元組…

100個(gè)SC元組

…

10個(gè)SC×S元組…磁盤B(S)=100塊B(SC)=100塊T(S)*T(SC)/105塊1塊1塊內(nèi)存20次100次106次代數(shù)優(yōu)化211.計(jì)算廣義笛卡爾積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ù)時(shí)間=2100/20=105秒運(yùn)算中間結(jié)果元組數(shù)=1000*10000=107

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

運(yùn)算中間結(jié)果寫入磁盤時(shí)間=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í)行時(shí)間=中間結(jié)果文件讀取時(shí)間=運(yùn)算中間結(jié)果寫入磁盤時(shí)間=5×104（s）

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

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

查詢Q1所需總時(shí)間=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ù)時(shí)間=100/20=5（s）在內(nèi)存中，對(duì)讀取的數(shù)據(jù)進(jìn)行選擇和投影操作，時(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ù)時(shí)間=100/20=5（s）在內(nèi)存中，對(duì)讀取的S元組與50個(gè)選課元組進(jìn)行連接操作后投影，時(shí)間忽略不計(jì)。查詢Q2所需總時(shí)間=5＋5=10（s）

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

對(duì)于實(shí)現(xiàn)同一查詢的不同的關(guān)系代數(shù)表達(dá)式（查詢樹），其操作的次序不同，查詢效率不同，查詢時(shí)間相差很大。有必要對(duì)查詢預(yù)處理器產(chǎn)生的關(guān)系代數(shù)初始查詢樹進(jìn)行優(yōu)化，得到較優(yōu)的邏輯查詢計(jì)劃，而不管用戶書寫的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)換為一個(gè)可以更高效執(zhí)行的關(guān)系代數(shù)表達(dá)式（查詢樹）?；诖鷶?shù)等價(jià)的啟發(fā)式優(yōu)化代數(shù)優(yōu)化26基于代數(shù)等價(jià)的啟發(fā)式優(yōu)化通過利用一些啟發(fā)式規(guī)則，將一個(gè)代數(shù)表達(dá)式轉(zhuǎn)換為另一個(gè)不同的但等價(jià)的代數(shù)表達(dá)式，產(chǎn)生可被進(jìn)一步優(yōu)化的查詢執(zhí)行計(jì)劃。關(guān)系代數(shù)表達(dá)式等價(jià)：指用相同的關(guān)系實(shí)例代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的。代數(shù)優(yōu)化27基于代數(shù)等價(jià)的啟發(fā)式優(yōu)化常用的等價(jià)變換規(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ù)等價(jià)的啟發(fā)式優(yōu)化常用的等價(jià)變換規(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ù)等價(jià)的啟發(fā)式優(yōu)化常用的等價(jià)變換規(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ù)等價(jià)的啟發(fā)式優(yōu)化常用的等價(jià)變換規(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ù)等價(jià)的啟發(fā)式優(yōu)化常用的等價(jià)變換規(guī)則7.選擇對(duì)自然連接的分配律

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

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

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

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

9.選擇對(duì)差運(yùn)算的分配律

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

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

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

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

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

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

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

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

(S×SC))

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

39

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47

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

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

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

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

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

50

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

連接操作的實(shí)現(xiàn)算法基于塊的嵌套循環(huán)連接算法①讀取關(guān)系S的M-1個(gè)磁盤塊中的元組到內(nèi)存緩沖區(qū)中。②為S在內(nèi)存中的元組創(chuàng)建一個(gè)查找結(jié)構(gòu)，它的查找關(guān)鍵字是R和S的公共屬性。③瀏覽R的所有塊，依次讀取每一塊到內(nèi)存M塊中的最后一塊中。④在讀入R的一個(gè)塊后，將塊中所有元組與S在內(nèi)存中的所有塊中的所有元組進(jìn)行比較。對(duì)于那些能連接的元組，輸出連接得到的元組。⑤重復(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個(gè)內(nèi)存塊的緩沖區(qū)來對(duì)S進(jìn)行緩沖。計(jì)算采用基于塊的嵌套循環(huán)連接算法代價(jià)。算法中的外層循環(huán)需循環(huán)5次。在每次外循環(huán)中，用100次磁盤I/O讀取S的數(shù)據(jù)塊組。在內(nèi)循環(huán)中用1000次磁盤I/O來讀取R。因此，運(yùn)算中讀取數(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)勢(shì)。53

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

連接操作的實(shí)現(xiàn)算法排序-歸并連接關(guān)系R和S按照連接屬性Y有序聚集存儲(chǔ)。兩個(gè)緩沖區(qū)，一個(gè)給R的當(dāng)前塊，另一個(gè)給S的當(dāng)前塊。①按照連接屬性的順序?qū)﹃P(guān)系R和S并發(fā)地進(jìn)行物理順序掃描，把關(guān)系R和S的首個(gè)磁盤塊中的元組讀入內(nèi)存緩沖區(qū)。②在讀入內(nèi)存的當(dāng)前R和S的元組中順序查找連接屬性Y的最小匹配值y。如果需要，從排序的R和/或S中繼續(xù)讀取下一個(gè)磁盤塊，直到找到最小匹配值y。③連接內(nèi)存中R和S的具有相同y值的所有元組。如果一個(gè)關(guān)系在內(nèi)存中已沒有未考慮的元組，就順序讀取該文件的下一個(gè)磁盤塊，直到處理完兩個(gè)關(guān)系中具有相同y值的所有元組。④在內(nèi)存R和S的元組中順序查找連接屬性Y的下一個(gè)匹配值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次讀取操作對(duì)象需要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排序，計(jì)算采用排序歸并連接算法代價(jià)。用1500次磁盤I/O來讀取R和S的每一個(gè)塊，僅需要101個(gè)內(nèi)存塊中的兩個(gè)。如果需要可以使用所有101塊來容納具有公共Y值的R和S的元組。56

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

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

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

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

①可按桶號(hào)i的大小將包含較少磁盤塊的桶（Si中的桶）讀入到內(nèi)存的緩沖區(qū)中，構(gòu)造內(nèi)存中的一個(gè)散列查找結(jié)構(gòu)。②讀入另一關(guān)系R中的與Si對(duì)應(yīng)的桶Ri，將讀入的Ri中的元組與內(nèi)存中Si中的記錄進(jìn)行連接，將連接的結(jié)果進(jìn)行輸出。③重復(fù)以上步驟，直到S中的所有桶處理完。連接操作讀取操作對(duì)象需要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排序，計(jì)算采用基于散列的連接算法代價(jià)。假設(shè)以連接屬性Y作為散列鍵將R和S分別散列到100個(gè)桶中，則一個(gè)桶的平均大小對(duì)于R占10個(gè)磁盤塊，對(duì)于S占5個(gè)磁盤塊。遠(yuǎn)遠(yuǎn)小于101塊可用的緩沖區(qū)數(shù)量。所以在每一個(gè)桶對(duì)上執(zhí)行一趟連接即可完成運(yùn)算。執(zhí)行對(duì)應(yīng)桶的一次連接需1500次磁盤I/O。60

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

連接操作的實(shí)現(xiàn)算法基于索引的連接運(yùn)算如果一個(gè)關(guān)系（如S）有一個(gè)屬性Y上的索引。①讀入R的一個(gè)磁盤塊，考慮塊中每一個(gè)元組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)化操作符的實(shí)現(xiàn)算法

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

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

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

連接操作的實(shí)現(xiàn)算法基于索引的連接運(yùn)算常見的連接查詢的情況是與S相比，R是很小的，V(S,Y)是很大的。在這種情況下，S的大多數(shù)元組的Y值根本不出現(xiàn)在R中，這些元組將無需被算法檢查，即不需要讀入內(nèi)存。但是，不論基于排序的還是基于散列的連接方法都需檢查S的每一個(gè)元組至少一次。所以，在實(shí)際的應(yīng)用中，索引選擇算法仍是一種常用的方法。65【例】分析實(shí)現(xiàn)“查詢選修了課程號(hào)為‘c02’課程的學(xué)生姓名”（1）T(S)=1000，T(SC)=10000。選修“c02”課程的元組為50個(gè)。（2）一個(gè)磁盤塊能存儲(chǔ)10個(gè)S元組記錄，或100個(gè)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)化從一個(gè)邏輯查詢計(jì)劃產(chǎn)生物理查詢計(jì)劃時(shí)，為邏輯查詢計(jì)劃的每一個(gè)操作符選擇實(shí)現(xiàn)算法并選擇這些操作符的執(zhí)行順序，還包括許多實(shí)現(xiàn)細(xì)節(jié)。被查詢的關(guān)系是怎樣被訪問的，即獲得所存儲(chǔ)數(shù)據(jù)的方式以及一個(gè)關(guān)系何時(shí)或是否應(yīng)當(dāng)被排序等；必須估計(jì)每個(gè)可能選項(xiàng)的執(zhí)行代價(jià)，使用代價(jià)估計(jì)來評(píng)價(jià)一個(gè)查詢計(jì)劃。67基于代價(jià)的物理優(yōu)化方法查詢計(jì)劃的代價(jià)因素一個(gè)查詢的實(shí)際執(zhí)行所需的代價(jià)包括:磁盤訪問代價(jià)：讀寫記錄所在磁盤數(shù)據(jù)塊的代價(jià)。存儲(chǔ)代價(jià)：存儲(chǔ)由查詢執(zhí)行計(jì)劃產(chǎn)生的中間結(jié)果文件的代價(jià)。計(jì)算代價(jià)：在查詢執(zhí)行過程中對(duì)數(shù)據(jù)緩沖區(qū)完成內(nèi)存操作的代價(jià)。內(nèi)存使用代價(jià)：與執(zhí)行查詢所需內(nèi)存緩沖區(qū)數(shù)相關(guān)的代價(jià)。通信代價(jià)：將查詢與查詢結(jié)果從一個(gè)數(shù)據(jù)庫站點(diǎn)傳送到另一個(gè)站點(diǎn)（或發(fā)出查詢的終端）的代價(jià)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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