數(shù)據(jù)庫原理與技術(shù)課件

第六章查詢處理6.1查詢處理概述6.2代價估算

6.3基本運算的實現(xiàn)6.4表達式計算6.5關(guān)系表達式轉(zhuǎn)換6.6選擇執(zhí)行計劃

第六章查詢處理6.1查詢處理概述16.1查詢處理概述查詢處理是指從數(shù)據(jù)庫中提取數(shù)據(jù)的一系列活動。主要包括：

將用高層數(shù)據(jù)庫語言表示的查詢語句翻譯為能在文件系統(tǒng)這一物理層次上實現(xiàn)的表達式

為優(yōu)化查詢而進行各種轉(zhuǎn)換

查詢的實際執(zhí)行

輸入：SQL語句輸出：滿足查詢條件的數(shù)據(jù)

6.1查詢處理概述查詢處理是指從數(shù)據(jù)庫中提取數(shù)據(jù)的一系列26.1查詢處理概述（2）查詢處理的基本步驟：1語法分析與翻譯2優(yōu)化3執(zhí)行語法分析與翻譯關(guān)系代數(shù)表達式執(zhí)行計劃優(yōu)化器查詢語句執(zhí)行引擎查詢結(jié)果有關(guān)數(shù)據(jù)的統(tǒng)計值數(shù)據(jù)6.1查詢處理概述（2）查詢處理的基本步驟：語法分析與翻36.1查詢處理概述（3）查詢優(yōu)化是為關(guān)系代數(shù)表達式的計算選擇最有效的查詢計劃的過程。查詢執(zhí)行計劃：用于計算一個查詢的原語序列。執(zhí)行原語：加了“如何執(zhí)行”注釋的關(guān)系代數(shù)運算。6.1查詢處理概述（3）查詢優(yōu)化是為關(guān)系代數(shù)表達式的計算46.1查詢處理概述（4）查詢優(yōu)化的過程：代數(shù)優(yōu)化：力圖找出與給定關(guān)系代數(shù)表達式等價的但執(zhí)行效率更高的一個表達式。

查詢語句處理的詳細策略的選擇，例如選擇執(zhí)行運算所采用的具體算法，選擇將使用的特定索引等等。

6.1查詢處理概述（4）查詢優(yōu)化的過程：56.1查詢處理概述（5）對于關(guān)系數(shù)據(jù)庫系統(tǒng)，查詢優(yōu)化是：挑戰(zhàn)：必須進行好的優(yōu)化，才有可接受的性能機會：關(guān)系表達式的語義層次高，提供了優(yōu)化的可能性。優(yōu)化器有理由比程序員做得更好：＊優(yōu)化器具有豐富的可使用的信息＊當(dāng)數(shù)據(jù)庫發(fā)生變化時優(yōu)化器容易再次進行優(yōu)化＊優(yōu)化器能夠?qū)Χ喾N實現(xiàn)策略逐一進行考慮＊優(yōu)化器集中了最優(yōu)秀的程序員的智慧和經(jīng)驗

6.1查詢處理概述（5）對于關(guān)系數(shù)據(jù)庫系統(tǒng)，查詢優(yōu)化是：66.2代價估算

6.2.1用于估計代價的目錄信息

6.2.2查詢代價的度量6.2代價估算6.2.1用于估計代價的目錄信息7

6.2.1用于估計代價的目錄信息

有關(guān)關(guān)系的統(tǒng)計信息nr：關(guān)系r中的元組數(shù)目br：含有關(guān)系r的元組的塊數(shù)目sr：關(guān)系r中一個元組的大小fr：關(guān)系r的塊因子，即一個塊中能存放的關(guān)系r的元組數(shù)若假定關(guān)系r的元組物理上存于同一文件中，則：br=nr/fr

6.2.1用于估計代價的目錄信息有關(guān)關(guān)系的統(tǒng)計信息8

6.2.1用于估計代價的目錄信息（2）有關(guān)關(guān)系的統(tǒng)計信息（續(xù)）V(A,r)：關(guān)系r中屬性A所具有的不同值的數(shù)目。V(A,r)等于ПA（r）的大小若A為關(guān)系r的碼，則V(A,r)=nrSC(A,r)：關(guān)系r的屬性A的選擇基數(shù)。表示關(guān)系r中滿足屬性A上的一個等值條件的平均元組數(shù)。若A為r的碼屬性，則SC(A,r)＝1若A為非碼屬性，并假定V(A,r)個不同的值在元組上均勻分布，則SC(A,r)＝(nr/V(A,r))。說明：V(A,r)與SC(A,r)中的A可以是屬性組。

6.2.1用于估計代價的目錄信息（2）有關(guān)關(guān)系的統(tǒng)計信息96.2.1用于估計代價的目錄信息（3）有關(guān)索引的統(tǒng)計信息：

fi：樹形結(jié)構(gòu)(如B＋樹)索引i的內(nèi)部結(jié)點的平均扇出。

HTi：索引i的層數(shù)。對于關(guān)系r的屬性A上所建的平衡樹索引（如B＋樹），HTi＝logfi(V(A,r))

對于散列索引，HTi＝1

LBi：索引i中最低層索引塊數(shù)目，即索引葉層的塊數(shù)。對于散列索引，Lbi就是索引中的塊數(shù)。

算法A的代價估計記為EA。

6.2.1用于估計代價的目錄信息（3）有關(guān)索引的統(tǒng)計信息106.2.2查詢代價的度量查詢代價：查詢處理對各種資源的使用情況

磁盤存取（簡化為磁盤塊傳送數(shù)）CPU時間

通信開銷

一個重要的影響因素：主存中緩沖區(qū)的大小M＊最好的情形，所有的數(shù)據(jù)可以讀入到緩沖區(qū)中＊最壞的情形，緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊——大約每個關(guān)系一塊。6.2.2查詢代價的度量查詢代價：查詢處理對各種資源的使用116.3基本運算的實現(xiàn)每一個基本的代數(shù)運算都有多種不同的實現(xiàn)算法。

?適用于不同的情況

等值條件，范圍條件數(shù)據(jù)是聚集的，數(shù)據(jù)是非聚集的相關(guān)屬性上有索引，相關(guān)屬性上沒有索引

?執(zhí)行代價不同

6.3基本運算的實現(xiàn)每一個基本的代數(shù)運算都有多種不126.3基本運算的實現(xiàn)（2）6.3.1選擇運算

6.3.2排序運算

6.3.3連接運算

6.3.4其他運算

6.3基本運算的實現(xiàn)（2）6.3.1選擇運算136.3.1選擇運算全表掃描

方法：依次訪問表的每一個塊，對于每一個元組，測試它是否滿足選擇條件。代價：E=br

缺點：效率低

優(yōu)點：

對關(guān)系的存儲方式?jīng)]有要求，不需要索引。適用于任何選擇條件。

6.3.1選擇運算全表掃描146.3.1選擇運算（2）索引掃描

條件：表在選擇條件的屬性上建有索引。方法：訪問索引，根據(jù)索引項的指示去訪問數(shù)據(jù)元組。無序索引：訪問滿足等值條件的元組有序索引：訪問滿足范圍查找條件的一系列元組。

6.3.1選擇運算（2）索引掃描156.3.1選擇運算.（3）代價：利用主索引，等值比較：E=HTi+SC(A，r)/fr

利用輔助索引，等值比較：

E=HTi+SC（A，r）利用主索引，非等值比較：

E=HTi+br/2（假設(shè)大約一半的元組滿足比較條件）利用輔助索引，非等值比較：

E=HTi+LBi/2+nr/2

6.3.1選擇運算.（3）代價：166.3.1選擇運算（4）復(fù)雜條件的選擇合取：σθ1∧θ2∧…∧θn（r）析?。害姚?∨θ2∨…∨θn（r）

方法：利用一個索引進行合取選擇。利用組合索引進行合取選擇。利用多維索引進行合取選擇。通過標識符的交集進行合取選擇。通過標識符的并集進行析取選擇。

6.3.1選擇運算（4）復(fù)雜條件的選擇176.3.2排序運算排序運算在數(shù)據(jù)庫中的重要意義：SQL查詢可能要求有序的查詢結(jié)果。

事先對于作為運算對象的關(guān)系進行排序，可以提高某些關(guān)系運算（例如連接）的執(zhí)行效率。

內(nèi)排序：文件較小，整個排序過程都能在內(nèi)存中進行。

外排序：文件較大，排序過程需要使用外存。

6.3.2排序運算排序運算在數(shù)據(jù)庫中的重要意義：186.3.2排序運算（2）外部排序-歸并算法：（設(shè)內(nèi)存中用于排序的緩沖區(qū)頁面數(shù)為M）第一階段，建立多個已排序的子表。

每次讀入M塊，進行內(nèi)排序，將長度為M塊的已排序子表（共br/M個）寫到外存中。

第二階段，對已排序子表進行歸并（可能需進行若干趟）。6.3.2排序運算（2）外部排序-歸并算法：196.3.2排序運算（3）第二階段，對已排序子表進行歸并。

第一趟：將頭M-1個已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出。將下M-1個已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出?！?/p>

已排序子表數(shù)目減少到原來的1/（M-1）

第二趟：以第一趟的輸出作為輸入，重復(fù)過程。第三趟：以第二趟的輸出作為輸入，重復(fù)歸并過程……直至歸并為一個已排序文件。6.3.2排序運算（3）第二階段，對已排序子表進行歸并。206.3.2排序運算（4）

第二階段第一趟：

將頭M-1個已排序子表的每一個的第一塊讀入內(nèi)存的一個緩沖頁repeat 在所有緩沖頁中的第一個元組中挑選排序碼值最小的元組； 把該元組寫到第M個緩沖頁，并將其從原緩沖頁中刪除； if任何一個歸并段文件Ri的緩沖頁為空并且沒有到達Ri末尾 then讀入Ri的下一塊到相應(yīng)的緩沖頁；if第M個緩沖頁滿then將第M個緩沖頁寫到磁盤，并清空該緩沖頁；until 所有的緩沖頁均空將下M-1個已排序子表的每一個的第一塊讀入內(nèi)存，歸并。…….6.3.2排序運算（4）第二階段第一趟：216.3.2排序運算（5）

初始關(guān)系

歸并段文件歸并段文件

排序結(jié)果第一階段第二階段第二階段創(chuàng)建歸并段文件第一趟歸并第二趟歸并6.3.2排序運算（5）初始關(guān)系226.3.2排序運算（6）代價估算：趟數(shù)=logM-1(br/M)E=br(2logM-1(br/M)+1)

6.3.2排序運算（6）代價估算：236.3.3連接運算二元運算，涉及兩個關(guān)系。r|><|s,r|><|s重要的運算，多種不同的實現(xiàn)算法。

6.3.3連接運算二元運算，涉及兩個關(guān)系。246.3.3連接運算（2）自然連接結(jié)果集大小的估計：

基于主碼、外碼連接的情況：結(jié)果集的元組數(shù)等于外碼所在關(guān)系的元組數(shù)。

一般情況：（假設(shè)連接屬性A的每個值在關(guān)系的元組中等概率出現(xiàn)），結(jié)果集的元組數(shù)為：nr*(ns/V(A,s))或ns*(

nr/V(A,r))說明：

當(dāng)V(A,s)與V(A,r)不同時，取兩個估計值中較小者。若兩個關(guān)系中的元組在連接屬性上的取值能匹配上的很少時，上述估計值太高。但實際上這種情況很少發(fā)生。6.3.3連接運算（2）自然連接結(jié)果集大小的估計：256.3.3連接運算（3）嵌套循環(huán)連接塊嵌套循環(huán)連接索引嵌套循環(huán)連接排序-歸并連接散列連接復(fù)雜連接的實現(xiàn)

6.3.3連接運算（3）嵌套循環(huán)連接266.3.3連接運算（4）嵌套循環(huán)連接foreach元組trinrdobeginforeach元組tsinsdobegin測試元組對(tr,ts)是否滿足連接條件θ如果滿足，把tr

ts加到結(jié)果中endend6.3.3連接運算（4）嵌套循環(huán)連接276.3.3連接運算（5）嵌套循環(huán)連接（續(xù)）優(yōu)點：對參加運算的關(guān)系沒有要求，適合于任何連接條件。代價：最壞情況（緩沖區(qū)只能夠容納每個關(guān)系的一個塊）：nrbs+br或nsbr+bs

最好情況（內(nèi)層關(guān)系s能完全放在內(nèi)存中）：bs+br

6.3.3連接運算（5）嵌套循環(huán)連接（續(xù)）286.3.3連接運算（6）塊嵌套循環(huán)連接：以塊的方式循環(huán)，以減少塊讀寫次數(shù)。

foreach塊Brofrdobeginforeach塊Bsofsdobeginforeach元組trinBrdobeginforeach元組tsinBsdo

begin測試元組對(tr,ts)是否滿足連接條件θ如果滿足，把trts加到結(jié)果中endendendend6.3.3連接運算（6）塊嵌套循環(huán)連接：以塊的方式循環(huán)，以296.3.3連接運算（7）塊嵌套循環(huán)連接（續(xù)）優(yōu)點：對參加運算的關(guān)系沒有要求，適合于任何連接條件。代價：最壞情況（緩沖區(qū)只能夠容納每個關(guān)系的一個塊）：br*bs+br或bs*br+bs

最好情況（內(nèi)層關(guān)系s能完全放在內(nèi)存中）：bs+br

6.3.3連接運算（7）塊嵌套循環(huán)連接（續(xù)）306.3.3連接運算（8）塊嵌套循環(huán)連接（續(xù)）一些改進：

連接屬性是內(nèi)層關(guān)系的碼時，內(nèi)層循環(huán)可中途跳出。內(nèi)層循環(huán)輪流做正、反向掃描，重用緩沖區(qū)中的數(shù)據(jù)，以減少磁盤讀取。內(nèi)層循環(huán)利用索引。

6.3.3連接運算（8）塊嵌套循環(huán)連接（續(xù)）316.3.3連接運算（9）索引嵌套循環(huán)連接：在內(nèi)層循環(huán)中利用連接屬性上的索引。

foreach元組trinrdobeginforeach與元組tr滿足連接條件的索引項ins關(guān)系在連接屬性上的索引dobegin利用索引取到相應(yīng)的ts

把trts加到結(jié)果中endend

6.3.3連接運算（9）索引嵌套循環(huán)連接：在內(nèi)層循環(huán)中利用326.3.3連接運算（10）索引嵌套循環(huán)連接（續(xù)）代價：最壞情況（緩沖區(qū)只能夠容納關(guān)系r的一個塊和索引的一個塊）：br+nr*c

或bs+ns*c最好情況不必考慮，因為不必采用索引嵌套循環(huán)連接方法。對關(guān)系S使用連接條件利用索引進行選擇操作的代價6.3.3連接運算（10）索引嵌套循環(huán)連接（續(xù)）對關(guān)系S使336.3.3連接運算（11）排序-歸并連接類似于外排序的歸并算法的思路，進行連接運算。前提：兩個關(guān)系的元組都已按連接屬性排好序。適用于自然連接和等值連接。a3b1d8d13f7m5q6aAaGcLdNmB

rsa1a2a1a3在歸并連接中使用的已排序關(guān)系rs6.3.3連接運算（11）排序-歸并連接a3b1d8d1346.3.3連接運算（12）pr:=r的第一個元組的地址ps:=s的第一個元組的地址；while(ps≠nullandpr≠null)dobegints:=ps所指向的元組；Ss:={ts}； 讓ps指向關(guān)系s的下一個元組；done:=false; while(notdoneandps≠null)dobegints’:=ps所指向的元組；if(ts’[JoinAttrs]=ts[JoinAttrs])thenbeginSs:=Ss∪{ts’}； 讓ps指向關(guān)系s的下一個元組；endelsedone:=true；end在連接屬性上具有相同值的S元組被加入到了Ss中。Ps指向在連接屬性上具有另一個值的S元組。6.3.3連接運算（12）pr:=r的第一個元組的地址356.3.3連接運算（13）tr:=pr所指向的元組； while(pr≠nullandtr[JoinAttrs]<ts[JoinAttrs])do begin

讓pr指向關(guān)系r的下一個元組； tr:=pr所指向的元組； end while(pr≠nullandtr[JoinAttrs]=ts[JoinAttrs])do beginforeachtsinSsdo begin將tstr加入結(jié)果中；end讓pr指向關(guān)系r的下一個元組； tr:=pr所指向的元組； endend在r中跳過中不能與Ss中的s元組匹配的r元組。在r中前進，將r元組與Ss中的每個s元組連接，直至r元組中的連接屬性值大于s元組的連接屬性值。

6.3.3連接運算（13）tr:366.3.3連接運算（14）

在歸并連接中使用的已排序關(guān)系

a3b1d8d13f7m5q6aAaGcLdNmBprpsa1a2a1a3在歸并連接中使用的已排序關(guān)系rs6.3.3連接運算（14）在歸并連接中使用的已排序關(guān)系376.3.3連接運算（15）排序-歸并連接（續(xù)）代價：br+bs6.3.3連接運算（15）排序-歸并連接（續(xù)）386.3.3連接運算（16）排序-歸并連接（續(xù)）---混合歸并連接思想：利用有序索引，對未排序的關(guān)系采用排序-歸并連接。前提：一個關(guān)系（r）按連接屬性排好序，另一個關(guān)系（S）未排序，但在連接屬性上有B+樹索引。方法：r的元組與s的B+樹葉結(jié)點進行“連接”，（結(jié)果的“元組”為r元組與s元組地址）按s元組地址排序，

訪問s的塊，完成連接。

6.3.3連接運算（16）排序-歸并連接（續(xù)）---混合396.3.3連接運算（17）散列連接適用于自然連接和等值連接。

基本思想:將兩個關(guān)系按連接屬性值劃分成有相同散列函數(shù)值的元組集合。關(guān)系r在一個散列劃分中的元組只需要與關(guān)系s在對應(yīng)的劃分中的元組相比較。在r和s的每一對劃分中進行索引嵌套循環(huán)連接（散列索引）。6.3.3連接運算（17）散列連接406.3.3連接運算（18）散列連接方法：確定連接屬性上的散列函數(shù)h，用于對s元組和r元組進行劃分。確定連接屬性上的散列函數(shù)h’，用于逐個對每一劃分中的s元組構(gòu)造散列索引，再對同一劃分中的r元組查找散列索引，同時進行連接。

6.3.3連接運算（18）散列連接416.3.3連接運算（19）關(guān)系的散列劃分rs關(guān)系r的劃分關(guān)系s的劃分01234012346.3.3連接運算（19）關(guān)系的散列劃分rs關(guān)系r的劃分426.3.3連接運算（20）

/*對關(guān)系s進行劃分*/置Hs0,

Hs1…,Hsmax為空 foreach元組tsinsdobegini:=h(ts[JoinAttrs])； Hsi

:=Hsi

∪{ts}； end/*對關(guān)系r進行劃分*/置Hr0,

Hr1…,Hrmax為空 foreach元組trinrdobegini:=h(tr[JoinAttrs])； Hri

:=Hri

∪{tr}； end6.3.3連接運算（20）/*對關(guān)系s進行劃分*/436.3.3連接運算（21）/*對每一分劃進行索引嵌套循環(huán)連接*/ fori:=0tomaxdobegin讀Hsi

，在內(nèi)存中建立其散列索引； foreach元組trinHri

dobegin檢索Hsi的散列索引，定位所有滿足ts[JoinAttrs]=tr[JoinAttrs]的元組ts foreach匹配的元組tsinHsi

dobegintrts加入結(jié)果中；end end end構(gòu)造用輸入關(guān)系查找用輸入關(guān)系6.3.3連接運算（21）/*對每一分劃進行索引嵌套循環(huán)連446.3.3連接運算（22）散列連接（續(xù)）

代價：最基本的情況為3（br+bs）+2*max

討論：

max的值應(yīng)選得足夠大，使內(nèi)存中能容納構(gòu)造用輸入關(guān)系的任一分劃以及其上的散列索引，max至少應(yīng)為bs/M。顯然最好用較小的關(guān)系作為構(gòu)造用輸入關(guān)系。當(dāng)bs>M2時，關(guān)系的劃分不可能一趟完成，需要遞歸劃分。當(dāng)對于某個i，Hsi中的元組數(shù)大于內(nèi)存容量時，需要進行溢出處理，想辦法使Hsi變小。改進：混合散列連接當(dāng)M

2>

>bs時，充分利用內(nèi)存空間，減少磁盤I/O的方法。前提：讀每個關(guān)系一遍就能完成散列劃分，構(gòu)造用輸入關(guān)系的每一個分劃都能完全放入內(nèi)存。6.3.3連接運算（22）散列連接（續(xù)）前提：讀每個關(guān)系一456.3.3連接運算（23）復(fù)雜連接的實現(xiàn)合取式：r|><|1∧2∧…∧ns用一種高效技術(shù)計算某一條件下的連接r|><|1s，在生成結(jié)果元組時測試其他條件。析取式：r|><|1∨2∨…∨ns==>r|><|1sr|><|2s…r|><|ns6.3.3連接運算（23）復(fù)雜連接的實現(xiàn)46

6.3.4其他運算

消除重復(fù)

投影

并、交、差

外連接

聚集

6.3.4其他運算消除重復(fù)476.3.4其他運算（2）消除重復(fù)用排序的方法用散列的方法投影投影，消除重復(fù)并、交、差排序的方法

散列的方法6.3.4其他運算（2）消除重復(fù)486.3.4其他運算（3）外連接計算連接，然后將適當(dāng)?shù)脑M加到結(jié)果中。例r]><|θs計算r|><|θS==>q1計算r-∏R(q1)，在s對應(yīng)的分量填上空值，加到q1中。

6.3.4其他運算（3）外連接496.3.4其他運算（4）外連接（續(xù)）修改連接算法修改嵌套循環(huán)連接算法進行左外連接、右外連接。修改排序-歸并連接算法進行全外連接、左外連接、右外連接。修改散列連接算法進行全外連接、左外連接、右外連接。6.3.4其他運算（4）外連接（續(xù)）506.3.4其他運算（5）聚集排序的方法散列的方法6.3.4其他運算（5）聚集516.4表達式計算例Пcustomer_name（σbalance<2500(account)|><|customer）

Пcustomer_nameσbalance<2500customeraccount|><|6.4表達式計算例Пcustomer_name（σ526.4表達式計算（2）實體化的方法—建立臨時關(guān)系代價：各個運算的代價加上中間結(jié)果寫到磁盤的代價。(nr/fr)流水線的方法—不建臨時關(guān)系，一個操作的結(jié)果傳給下一個操作作為輸入。6.4表達式計算（2）實體化的方法—建立臨時關(guān)系536.4表達式計算（3）流水線的實現(xiàn)：需求驅(qū)動—在操作樹的頂端將數(shù)據(jù)往上拉。生產(chǎn)者驅(qū)動—將數(shù)據(jù)從操作樹的底層往上推需求驅(qū)動的流水線方法比生產(chǎn)者驅(qū)動的流水線方法使用更廣泛，因為它更容易實現(xiàn)。6.4表達式計算（3）流水線的實現(xiàn)：546.4表達式計算（4）說明：流水線技術(shù)限制了實現(xiàn)操作的可用算法。

例若連接運算的左端輸入來自流水線，則不可用排序-歸并連接算法，

可用索引嵌套循環(huán)連接算法。若連接運算的兩端輸入均來自流水線，則限制更大。并非所有情況下都是流水線方法的代價小于實體化方法的代價，因為流水線方法對于運算的實現(xiàn)算法有限制。

6.4表達式計算（4）說明：556.5關(guān)系表達式轉(zhuǎn)換查詢優(yōu)化是為關(guān)系代數(shù)表達式的計算選擇最有效的查詢計劃的過程。

查詢優(yōu)化的過程：代數(shù)優(yōu)化：力圖找出與給定關(guān)系代數(shù)表達式等價的但執(zhí)行效率更高的一個表達式。

查詢語句處理的詳細策略的選擇，例如選擇執(zhí)行運算所采用的具體算法，選擇將使用的特定索引等等。6.5關(guān)系表達式轉(zhuǎn)換查詢優(yōu)化是為關(guān)系代數(shù)表達式566.5.1表達式的等價性兩個表達式等價：產(chǎn)生的結(jié)果關(guān)系具有相同的屬性集和相同的元組集。

例

Пcustomer_name

(σbranch-city=”Brooklyn”(branch|><|(account|><|depositor)))

等價于

Пcustomer_name

((σbranch-city=”Brooklyn”(branch))|><|(account|><|depositor))

6.5.1表達式的等價性兩個表達式等價：產(chǎn)生的結(jié)果576.5.1表達式的等價性（2）

Пcustomer_nameσbranch_city=”Brooklyn”branchaccountdepositorПcustomer_nameσbranch_city=”Brooklyn”branchaccountdepositor6.5.1表達式的等價性（2）Пcust586.5.2等價規(guī)則等價規(guī)則

將一個表達式轉(zhuǎn)換為與之等價的另一個表達式的規(guī)則。符號：θ、θ1、θ2等表示謂詞，L1、L2、L3等表示屬性列表，E、E1、E2等表示關(guān)系代數(shù)表達式。關(guān)系名r是關(guān)系代數(shù)表達式的特例，在E可以出現(xiàn)的地方它就可以出現(xiàn)。

6.5.2等價規(guī)則等價規(guī)則596.5.2等價規(guī)則（2）1.選擇運算的級聯(lián)：合取選擇運算可分解為單個選擇運算的序列。σθ1∧θ2(E)=σθ1(σθ2(E))2.選擇運算滿足交換律σθ1(σθ2(E))=σθ2(σθ1(E))3.投影運算的級聯(lián)：投影運算序列中只有最后一個運算是需要的，其余的可省略?！荓1(∏L2(…(∏Ln(E))…))=∏L1(E)

6.5.2等價規(guī)則（2）1.選擇運算的級聯(lián)：合取選擇606.5.2等價規(guī)則（3）

4.選擇與笛卡爾積以及theta連接相結(jié)合a.σθ(E1×E2)=E1|><|θE2

b.σθ1(E1|><|θ2

E2)=E1|><|θ1∧θ2

E25.theta連接運算滿足交換律：E1|><|θE2=E2|><|θE1自然連接也滿足交換律E1|><|

E2=E2|><|

E16.5.2等價規(guī)則（3）4.選擇與笛卡爾積以及the616.5.2等價規(guī)則（4）6.連接運算的結(jié)合律

a.自然連接運算滿足結(jié)合律：(E1|><|

E2)

|><|

E3=E1

|><|

(E2|><|

E3)

b.theta連接具有以下方式的結(jié)合律： (E1|><|θ1

E2)|><|θ2∧θ3E3

=E1|><|θ1∧θ3(E2|><|θ2E3)其中θ2只涉及E2與E3的屬性。由于任意一個條件都可為空，因此笛卡爾積運算也具有結(jié)合律。6.5.2等價規(guī)則（4）6.連接運算的結(jié)合律b.th626.5.2等價規(guī)則（5）

7.選擇運算在下面兩個條件下對theta連接運算具有分配律：a.當(dāng)選擇條件θ0的所有屬性只涉及參與連接運算的表達式之一(E1)時：σθ0(E1|><|θE2)=(σθ0(E1))|><|θE2b.當(dāng)選擇條件θ1只涉及E1的屬性，選擇條件θ2只涉及E2的屬性時： σθ1∧θ2(E1|><|θE2)=(σθ1(E1))|><|θ(σθ2(E2))6.5.2等價規(guī)則（5）7.選擇運算在下面兩個條件636.5.2等價規(guī)則（6）8.投影運算對theta連接運算具有分配律：a.令L1、L2分別是E1、E2的屬性。假設(shè)連接條件θ只涉及L1∪L2中的屬性，則：∏L1∪L2

(E1|><|θE2)=(∏L1(E1))

|><|θ(∏L2(E2))b.考慮連接E1|><|θE2。令L1、L2分別是E1、E2的屬性；令L3是E1中出現(xiàn)在連接條件θ中但不在L1∪L2中的屬性；令L4是E2中出現(xiàn)在連接條件θ中但不在L1∪L2中的屬性。那么：∏L1∪L2

(E1|><|θE2)=∏L1∪L2

((∏L1∪L3(E1))

|><|θ(∏L2∪L4(E2)))

6.5.2等價規(guī)則（6）8.投影運算對theta連接646.5.2等價規(guī)則（7）

9.集合運算并與交滿足交換律E1∪E2=E2∪E1E1∩E2=E2∩E1集合差運算不滿足交換律10.集合運算并與交滿足結(jié)合律(E1∪E2)∪E3=E1∪(E2∪E3)(E1∩E2)∩E3=E1∩(E2∩E3)

集合差運算不滿足結(jié)合律6.5.2等價規(guī)則（7）9.集合運算并與交滿足交換律656.5.2等價規(guī)則（8）

11.選擇運算對并、交、差運算具有分配律：σp（E1-E2）=σp（E1）-σp（E2）σp（E1∪E2）=σp（E1）∪σp（E2）σp（E1∩E2）=σp（E1）∩σp（E2）

進一步有：σp（E1-E2）=σp（E1）-E2σp（E1∩E2）=σp（E1）∩E2但對于∪不成立。

6.5.2等價規(guī)則（8）11.選擇運算對并、交、差運666.5.2等價規(guī)則（9）

12.投影運算對并運算具有分配律∏L(E1∪E2)=(∏L(E1))∪(∏L(E2))

最小的等價規(guī)則集：若一個等價規(guī)則集中的任何一條規(guī)則都不能由其它規(guī)則結(jié)合起來導(dǎo)出，則稱該等價規(guī)則集為最小的等價規(guī)則集。

6.5.2等價規(guī)則（9）12.投影運算對并運算具有分676.5.2等價規(guī)則（10）

例Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000

(branch|><|(account|><|depositor)))

規(guī)則6a==>Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000

((branch|><|account)|><|depositor))規(guī)則7a==>Пcustomer-name((σbranch_city=”Brooklyn”∧balance>1000

(branch|><|account))|><|depositor)6.5.2等價規(guī)則（10）例Пcustomer-686.5.2等價規(guī)則（11）Пcustomer-name((σbranch-city=”Brooklyn”∧balance>1000(branch|><|account))|><|depositor)規(guī)則7b==>Пcustomer-name((σbranch-city=”Brooklyn”(branch)|><|σbalance>1000(account))|><|depositor)規(guī)則8b==>Пcustomer-name(Пaccount-number(σbranch-city=”Brooklyn”(branch)|><|σbalance>1000(account))|><|depositor)

6.5.2等價規(guī)則（11）Пcustomer-name(696.5.2等價規(guī)則（12）說明：

規(guī)則只說明兩個表達式等價，并不說明哪一個更好。

連接的次序很重要，好的連接次序序列產(chǎn)生小的中間結(jié)果。

規(guī)則的使用會產(chǎn)生大量的等價表達式，優(yōu)化器要采用適當(dāng)?shù)募夹g(shù)來減少所產(chǎn)生的表達式的數(shù)量。

6.5.2等價規(guī)則（12）說明：706.6選擇執(zhí)行計劃關(guān)系代數(shù)表達式的基礎(chǔ)上，執(zhí)行計劃進一步說明：

每個運算的實現(xiàn)算法各運算的執(zhí)行順序是否采用流水線技術(shù)注意：每個運算的最小代價算法組合起來不一定是整個表達式的最佳算法，必須考慮各個運算之間的相互作用。6.6選擇執(zhí)行計劃關(guān)系代數(shù)表達式的基礎(chǔ)上，執(zhí)行計劃進一步716.6選擇執(zhí)行計劃（2）兩類主要的優(yōu)化算法：基于代價的方法啟發(fā)式方法6.6選擇執(zhí)行計劃（2）兩類主要的優(yōu)化算法：726.6.1基于代價的優(yōu)化

通過使用等價規(guī)則為給定的查詢語句產(chǎn)生一系列查詢執(zhí)行計劃，并選擇其中代價最小或接近最小的。

等價于給定查詢的不同查詢計劃可能很多，因此優(yōu)化的代價太大，所以：

采用一些巧妙的技術(shù)來減少需要考慮的表達式的數(shù)目。

采用啟發(fā)式方法來減少需考慮的表達式的數(shù)目。

6.6.1基于代價的優(yōu)化通過使用等價規(guī)則為給定的查詢736.6.1基于代價的優(yōu)化（2）減少需要考慮的表達式數(shù)目的技術(shù)只考慮左深連接次序

r1r2r3r4r5左深連接樹r1r2r3r4r5非左深連接樹6.6.1基于代價的優(yōu)化（2）減少需要考慮的表達式數(shù)目的技術(shù)746.6.1基于代價的優(yōu)化（3）找多個關(guān)系的最佳連接順序時，不是簡單地考慮所有的可能順序，而是為每個子集找出最佳連接順序，這樣能大大減少需要檢查的連接順序的總數(shù)。如果檢查一個表達式的某部分后發(fā)現(xiàn)這一部分的最小代價已經(jīng)比先前已檢查過的整個表達式的執(zhí)行計劃的最小代價要大，則可以終止對這個表達式的檢查。如果發(fā)現(xiàn)計算一個子表達式的代價最小的方法所用的代價比先前已檢查過的整個表達式的最小代價執(zhí)行計劃所需代價還大，則沒有必要對包含該子表達式的任何完整表達式進行檢查。6.6.1基于代價的優(yōu)化（3）找多個關(guān)系的最佳連接順序時，不756.6.2啟發(fā)式優(yōu)化運用啟發(fā)式規(guī)則，對關(guān)系代數(shù)表達式進行等價變換。常用的規(guī)則：盡早進行選擇運算盡早進行投影運算避免進行笛卡爾積運算

………..

6.6.2啟發(fā)式優(yōu)化運用啟發(fā)式規(guī)則，對關(guān)系代數(shù)表達式進行等766.6.2啟發(fā)式優(yōu)化（2）

啟發(fā)式優(yōu)化的步驟:

1.將合取選擇分解為單個選擇運算的序列。這有助于將選擇運算往查詢樹下層移。

2.把選擇運算在查詢樹上下推到最早可能執(zhí)行的地方。

例如，盡可能將σθ(r|><|s)轉(zhuǎn)換成σθ(

r)|><|s或r|><|σθ(s)

3.通過使用|><|的結(jié)合律，重新組織查詢樹，使得具有限制比較嚴格的選擇運算的葉結(jié)點關(guān)系首先執(zhí)行。

4.將跟有選擇條件的笛卡爾積運算替換成連接運算。

5.將投影屬性加以分解并在查詢樹上盡可能往下推。必要時可以引入新的投影運算。

6.識別那些可用流水方式執(zhí)行其運算的子樹，并采用流水線方法執(zhí)行之。

6.6.2啟發(fā)式優(yōu)化（2）啟發(fā)式優(yōu)化的步驟:776.6.3嵌套子查詢的優(yōu)化

復(fù)雜嵌套子查詢的優(yōu)化相當(dāng)困難，許多優(yōu)化器對于嵌套子查詢的優(yōu)化僅做了少量的工作。

例selectcustomer-name from

borrower whereexists(select*

from

depositor

where

depositor.customer-name =borrower.customer-name)SQL概念上按以下方式執(zhí)行查詢：計算外層查詢的from子句中的關(guān)系的笛卡爾積，然后對該笛卡爾積的每個元組用位于where子句中的謂詞進行測試。本例中，即測試子查詢運算結(jié)果是否為空。6.6.3嵌套子查詢的優(yōu)化復(fù)雜嵌套子查詢的優(yōu)化相當(dāng)786.6.3嵌套子查詢的優(yōu)化（2）相關(guān)執(zhí)行:概念上將位于where子句中的嵌套子查詢處理成獲取參數(shù)并且返回單獨值或值的集合（可能為空集）的函數(shù)。參數(shù)是嵌套子查詢中用到的外層查詢的變量（稱作相關(guān)變量）。相關(guān)執(zhí)行效率不高，因為對于外層查詢的每一個元組都要進行一次內(nèi)層子查詢的運算，從而可能導(dǎo)致大量的隨機磁盤I/O操作。去除相關(guān)：用一個具有連接的查詢（可能使用臨時關(guān)系）去替代嵌套子查詢。有效的連接算法有助于避免昂貴的隨機I/O操作。6.6.3嵌套子查詢的優(yōu)化（2）相關(guān)執(zhí)行:概念上將位于796.6.3嵌套子查詢的優(yōu)化（3）例selectcustomer-name from

borrower whereexists(select*

from

depositor

where

depositor.customer-name =borrower.customer-name)selectcustomer-name fromborrower,depositor wheredepositor.customer-name =borrower.customer-name6.6.3嵌套子查詢的優(yōu)化（3）例select806.6.3嵌套子查詢的優(yōu)化（4）更復(fù)雜的情況：不能將嵌套子查詢關(guān)系直接移入外層查詢的from子句里，需要先建立一個包含嵌套查詢結(jié)果（但沒有用取自外層查詢的相關(guān)變量進行選擇操作）的臨時關(guān)系，然后將這個臨時表與外層查詢進行連接。

6.6.3嵌套子查詢的優(yōu)化（4）更復(fù)雜的情況：不能816.6.3嵌套子查詢的優(yōu)化（5）例

selectcustomer-name from

borrower whereloan-number>1000 andexists(select*

from

depositor

where

depositor.customer-name =borrower.customer-name andaccount-number<1000)==〉createtablet1as selectdistinctcustomer-namefromdepositorwhere

account-number<1000selectcustomer-nameformborrower,t1whereloan-number>1000andt1.customer-name=borrower.customer-name

6.6.3嵌套子查詢的優(yōu)化（5）例select826.6.3嵌套子查詢的優(yōu)化（6）當(dāng)嵌套子查詢使用聚集、或嵌套子查詢的結(jié)果用于等值測試、或嵌套子查詢與外部查詢的關(guān)聯(lián)條件是notexists時，去除相關(guān)操作會更復(fù)雜。

6.6.3嵌套子查詢的優(yōu)化（6）當(dāng)嵌套子查詢使用聚集、83課程實習(xí)目的：1.了解數(shù)據(jù)庫管理系統(tǒng)底層的存儲管理與數(shù)據(jù)管理部件，它所提供的接口。2.進行查詢處理系統(tǒng)設(shè)計與實現(xiàn)的實際訓(xùn)練。任務(wù)：1.設(shè)計與實現(xiàn)一個簡化的查詢處理系統(tǒng)，對SQL語句進行分析處理，優(yōu)化，產(chǎn)生執(zhí)行結(jié)果。2.分析、比較不同的查詢執(zhí)行計劃的執(zhí)行性能。

課程實習(xí)目的：84課程實習(xí)（2）基礎(chǔ)環(huán)境：COBASE核心——存儲管理和數(shù)據(jù)管理子系統(tǒng)SQL語言翻譯處理存儲管理與數(shù)據(jù)管理單元組接口SQL語句課程實習(xí)（2）基礎(chǔ)環(huán)境：SQL語言存儲管理單元組接口SQL語85課程實習(xí)（3）說明：1．二至三人一組，自由結(jié)合。2．適當(dāng)控制系統(tǒng)的規(guī)模和難度，只處理有限形式的SQL查詢。3．集中做與查詢處理密切相關(guān)的工作，簡化其他部分。4．注意中間結(jié)果，和比較、分析結(jié)果的輸出，充分展示你的工作的特色。

課程實習(xí)（3）說明：86課程實習(xí)（4）提交：1．查詢處理系統(tǒng)規(guī)格定義2．設(shè)計說明書3．使用說明書4．比較分析和總結(jié)報告5．可運行的系統(tǒng)課程實習(xí)（4）提交：87第六章查詢處理6.1查詢處理概述6.2代價估算

6.3基本運算的實現(xiàn)6.4表達式計算6.5關(guān)系表達式轉(zhuǎn)換6.6選擇執(zhí)行計劃

第六章查詢處理6.1查詢處理概述886.1查詢處理概述查詢處理是指從數(shù)據(jù)庫中提取數(shù)據(jù)的一系列活動。主要包括：

將用高層數(shù)據(jù)庫語言表示的查詢語句翻譯為能在文件系統(tǒng)這一物理層次上實現(xiàn)的表達式

為優(yōu)化查詢而進行各種轉(zhuǎn)換

查詢的實際執(zhí)行

輸入：SQL語句輸出：滿足查詢條件的數(shù)據(jù)

6.1查詢處理概述查詢處理是指從數(shù)據(jù)庫中提取數(shù)據(jù)的一系列896.1查詢處理概述（2）查詢處理的基本步驟：1語法分析與翻譯2優(yōu)化3執(zhí)行語法分析與翻譯關(guān)系代數(shù)表達式執(zhí)行計劃優(yōu)化器查詢語句執(zhí)行引擎查詢結(jié)果有關(guān)數(shù)據(jù)的統(tǒng)計值數(shù)據(jù)6.1查詢處理概述（2）查詢處理的基本步驟：語法分析與翻906.1查詢處理概述（3）查詢優(yōu)化是為關(guān)系代數(shù)表達式的計算選擇最有效的查詢計劃的過程。查詢執(zhí)行計劃：用于計算一個查詢的原語序列。執(zhí)行原語：加了“如何執(zhí)行”注釋的關(guān)系代數(shù)運算。6.1查詢處理概述（3）查詢優(yōu)化是為關(guān)系代數(shù)表達式的計算916.1查詢處理概述（4）查詢優(yōu)化的過程：代數(shù)優(yōu)化：力圖找出與給定關(guān)系代數(shù)表達式等價的但執(zhí)行效率更高的一個表達式。

查詢語句處理的詳細策略的選擇，例如選擇執(zhí)行運算所采用的具體算法，選擇將使用的特定索引等等。

6.1查詢處理概述（4）查詢優(yōu)化的過程：926.1查詢處理概述（5）對于關(guān)系數(shù)據(jù)庫系統(tǒng)，查詢優(yōu)化是：挑戰(zhàn)：必須進行好的優(yōu)化，才有可接受的性能機會：關(guān)系表達式的語義層次高，提供了優(yōu)化的可能性。優(yōu)化器有理由比程序員做得更好：＊優(yōu)化器具有豐富的可使用的信息＊當(dāng)數(shù)據(jù)庫發(fā)生變化時優(yōu)化器容易再次進行優(yōu)化＊優(yōu)化器能夠?qū)Χ喾N實現(xiàn)策略逐一進行考慮＊優(yōu)化器集中了最優(yōu)秀的程序員的智慧和經(jīng)驗

6.1查詢處理概述（5）對于關(guān)系數(shù)據(jù)庫系統(tǒng)，查詢優(yōu)化是：936.2代價估算

6.2.1用于估計代價的目錄信息

6.2.2查詢代價的度量6.2代價估算6.2.1用于估計代價的目錄信息94

6.2.1用于估計代價的目錄信息

有關(guān)關(guān)系的統(tǒng)計信息nr：關(guān)系r中的元組數(shù)目br：含有關(guān)系r的元組的塊數(shù)目sr：關(guān)系r中一個元組的大小fr：關(guān)系r的塊因子，即一個塊中能存放的關(guān)系r的元組數(shù)若假定關(guān)系r的元組物理上存于同一文件中，則：br=nr/fr

6.2.1用于估計代價的目錄信息有關(guān)關(guān)系的統(tǒng)計信息95

6.2.1用于估計代價的目錄信息（2）有關(guān)關(guān)系的統(tǒng)計信息（續(xù)）V(A,r)：關(guān)系r中屬性A所具有的不同值的數(shù)目。V(A,r)等于ПA（r）的大小若A為關(guān)系r的碼，則V(A,r)=nrSC(A,r)：關(guān)系r的屬性A的選擇基數(shù)。表示關(guān)系r中滿足屬性A上的一個等值條件的平均元組數(shù)。若A為r的碼屬性，則SC(A,r)＝1若A為非碼屬性，并假定V(A,r)個不同的值在元組上均勻分布，則SC(A,r)＝(nr/V(A,r))。說明：V(A,r)與SC(A,r)中的A可以是屬性組。

6.2.1用于估計代價的目錄信息（2）有關(guān)關(guān)系的統(tǒng)計信息966.2.1用于估計代價的目錄信息（3）有關(guān)索引的統(tǒng)計信息：

fi：樹形結(jié)構(gòu)(如B＋樹)索引i的內(nèi)部結(jié)點的平均扇出。

HTi：索引i的層數(shù)。對于關(guān)系r的屬性A上所建的平衡樹索引（如B＋樹），HTi＝logfi(V(A,r))

對于散列索引，HTi＝1

LBi：索引i中最低層索引塊數(shù)目，即索引葉層的塊數(shù)。對于散列索引，Lbi就是索引中的塊數(shù)。

算法A的代價估計記為EA。

6.2.1用于估計代價的目錄信息（3）有關(guān)索引的統(tǒng)計信息976.2.2查詢代價的度量查詢代價：查詢處理對各種資源的使用情況

磁盤存?。ê喕癁榇疟P塊傳送數(shù)）CPU時間

通信開銷

一個重要的影響因素：主存中緩沖區(qū)的大小M＊最好的情形，所有的數(shù)據(jù)可以讀入到緩沖區(qū)中＊最壞的情形，緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊——大約每個關(guān)系一塊。6.2.2查詢代價的度量查詢代價：查詢處理對各種資源的使用986.3基本運算的實現(xiàn)每一個基本的代數(shù)運算都有多種不同的實現(xiàn)算法。

?適用于不同的情況

等值條件，范圍條件數(shù)據(jù)是聚集的，數(shù)據(jù)是非聚集的相關(guān)屬性上有索引，相關(guān)屬性上沒有索引

?執(zhí)行代價不同

6.3基本運算的實現(xiàn)每一個基本的代數(shù)運算都有多種不996.3基本運算的實現(xiàn)（2）6.3.1選擇運算

6.3.2排序運算

6.3.3連接運算

6.3.4其他運算

6.3基本運算的實現(xiàn)（2）6.3.1選擇運算1006.3.1選擇運算全表掃描

方法：依次訪問表的每一個塊，對于每一個元組，測試它是否滿足選擇條件。代價：E=br

缺點：效率低

優(yōu)點：

對關(guān)系的存儲方式?jīng)]有要求，不需要索引。適用于任何選擇條件。

6.3.1選擇運算全表掃描1016.3.1選擇運算（2）索引掃描

條件：表在選擇條件的屬性上建有索引。方法：訪問索引，根據(jù)索引項的指示去訪問數(shù)據(jù)元組。無序索引：訪問滿足等值條件的元組有序索引：訪問滿足范圍查找條件的一系列元組。

6.3.1選擇運算（2）索引掃描1026.3.1選擇運算.（3）代價：利用主索引，等值比較：E=HTi+SC(A，r)/fr

利用輔助索引，等值比較：

E=HTi+SC（A，r）利用主索引，非等值比較：

E=HTi+br/2（假設(shè)大約一半的元組滿足比較條件）利用輔助索引，非等值比較：

E=HTi+LBi/2+nr/2

6.3.1選擇運算.（3）代價：1036.3.1選擇運算（4）復(fù)雜條件的選擇合?。害姚?∧θ2∧…∧θn（r）析取：σθ1∨θ2∨…∨θn（r）

方法：利用一個索引進行合取選擇。利用組合索引進行合取選擇。利用多維索引進行合取選擇。通過標識符的交集進行合取選擇。通過標識符的并集進行析取選擇。

6.3.1選擇運算（4）復(fù)雜條件的選擇1046.3.2排序運算排序運算在數(shù)據(jù)庫中的重要意義：SQL查詢可能要求有序的查詢結(jié)果。

事先對于作為運算對象的關(guān)系進行排序，可以提高某些關(guān)系運算（例如連接）的執(zhí)行效率。

內(nèi)排序：文件較小，整個排序過程都能在內(nèi)存中進行。

外排序：文件較大，排序過程需要使用外存。

6.3.2排序運算排序運算在數(shù)據(jù)庫中的重要意義：1056.3.2排序運算（2）外部排序-歸并算法：（設(shè)內(nèi)存中用于排序的緩沖區(qū)頁面數(shù)為M）第一階段，建立多個已排序的子表。

每次讀入M塊，進行內(nèi)排序，將長度為M塊的已排序子表（共br/M個）寫到外存中。

第二階段，對已排序子表進行歸并（可能需進行若干趟）。6.3.2排序運算（2）外部排序-歸并算法：1066.3.2排序運算（3）第二階段，對已排序子表進行歸并。

第一趟：將頭M-1個已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出。將下M-1個已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出?！?/p>

已排序子表數(shù)目減少到原來的1/（M-1）

第二趟：以第一趟的輸出作為輸入，重復(fù)過程。第三趟：以第二趟的輸出作為輸入，重復(fù)歸并過程……直至歸并為一個已排序文件。6.3.2排序運算（3）第二階段，對已排序子表進行歸并。1076.3.2排序運算（4）

第二階段第一趟：

將頭M-1個已排序子表的每一個的第一塊讀入內(nèi)存的一個緩沖頁repeat 在所有緩沖頁中的第一個元組中挑選排序碼值最小的元組； 把該元組寫到第M個緩沖頁，并將其從原緩沖頁中刪除； if任何一個歸并段文件Ri的緩沖頁為空并且沒有到達Ri末尾 then讀入Ri的下一塊到相應(yīng)的緩沖頁；if第M個緩沖頁滿then將第M個緩沖頁寫到磁盤，并清空該緩沖頁；until 所有的緩沖頁均空將下M-1個已排序子表的每一個的第一塊讀入內(nèi)存，歸并?！?6.3.2排序運算（4）第二階段第一趟：1086.3.2排序運算（5）

初始關(guān)系

歸并段文件歸并段文件

排序結(jié)果第一階段第二階段第二階段創(chuàng)建歸并段文件第一趟歸并第二趟歸并6.3.2排序運算（5）初始關(guān)系1096.3.2排序運算（6）代價估算：趟數(shù)=logM-1(br/M)E=br(2logM-1(br/M)+1)

6.3.2排序運算（6）代價估算：1106.3.3連接運算二元運算，涉及兩個關(guān)系。r|><|s,r|><|s重要的運算，多種不同的實現(xiàn)算法。

6.3.3連接運算二元運算，涉及兩個關(guān)系。1116.3.3連接運算（2）自然連接結(jié)果集大小的估計：

基于主碼、外碼連接的情況：結(jié)果集的元組數(shù)等于外碼所在關(guān)系的元組數(shù)。

一般情況：（假設(shè)連接屬性A的每個值在關(guān)系的元組中等概率出現(xiàn)），結(jié)果集的元組數(shù)為：nr*(ns/V(A,s))或ns*(

nr/V(A,r))說明：

當(dāng)V(A,s)與V(A,r)不同時，取兩個估計值中較小者。若兩個關(guān)系中的元組在連接屬性上的取值能匹配上的很少時，上述估計值太高。但實際上這種情況很少發(fā)生。6.3.3連接運算（2）自然連接結(jié)果集大小的估計：1126.3.3連接運算（3）嵌套循環(huán)連接塊嵌套循環(huán)連接索引嵌套循環(huán)連接排序-歸并連接散列連接復(fù)雜連接的實現(xiàn)

6.3.3連接運算（3）嵌套循環(huán)連接1136.3.3連接運算（4）嵌套循環(huán)連接foreach元組trinrdobeginforeach元組tsinsdobegin測試元組對(tr,ts)是否滿足連接條件θ如果滿足，把tr

ts加到結(jié)果中endend6.3.3連接運算（4）嵌套循環(huán)連接1146.3.3連接運算（5）嵌套循環(huán)連接（續(xù)）優(yōu)點：對參加運算的關(guān)系沒有要求，適合于任何連接條件。代價：最壞情況（緩沖區(qū)只能夠容納每個關(guān)系的一個塊）：nrbs+br或nsbr+bs

最好情況（內(nèi)層關(guān)系s能完全放在內(nèi)存中）：bs+br

6.3.3連接運算（5）嵌套循環(huán)連接（續(xù)）1156.3.3連接運算（6）塊嵌套循環(huán)連接：以塊的方式循環(huán)，以減少塊讀寫次數(shù)。

foreach塊Brofrdobeginforeach塊Bsofsdobeginforeach元組trinBrdobeginforeach元組tsinBsdo

begin測試元組對(tr,ts)是否滿足連接條件θ如果滿足，把trts加到結(jié)果中endendendend6.3.3連接運算（6）塊嵌套循環(huán)連接：以塊的方式循環(huán)，以1166.3.3連接運算（7）塊嵌套循環(huán)連接（續(xù)）優(yōu)點：對參加運算的關(guān)系沒有要求，適合于任何連接條件。代價：最壞情況（緩沖區(qū)只能夠容納每個關(guān)系的一個塊）：br*bs+br或bs*br+bs

最好情況（內(nèi)層關(guān)系s能完全放在內(nèi)存中）：bs+br

6.3.3連接運算（7）塊嵌套循環(huán)連接（續(xù)）1176.3.3連接運算（8）塊嵌套循環(huán)連接（續(xù)）一些改進：

連接屬性是內(nèi)層關(guān)系的碼時，內(nèi)層循環(huán)可中途跳出。內(nèi)層循環(huán)輪流做正、反向掃描，重用緩沖區(qū)中的數(shù)據(jù)，以減少磁盤讀取。內(nèi)層循環(huán)利用索引。

6.3.3連接運算（8）塊嵌套循環(huán)連接（續(xù)）1186.3.3連接運算（9）索引嵌套循環(huán)連接：在內(nèi)層循環(huán)中利用連接屬性上的索引。

foreach元組trinrdobeginforeach與元組tr滿足連接條件的索引項ins關(guān)系在連接屬性上的索引dobegin利用索引取到相應(yīng)的ts

把trts加到結(jié)果中endend

6.3.3連接運算（9）索引嵌套循環(huán)連接：在內(nèi)層循環(huán)中利用1196.3.3連接運算（10）索引嵌套循環(huán)連接（續(xù)）代價：最壞情況（緩沖區(qū)只能夠容納關(guān)系r的一個塊和索引的一個塊）：br+nr*c

或bs+ns*c最好情況不必考慮，因為不必采用索引嵌套循環(huán)連接方法。對關(guān)系S使用連接條件利用索引進行選擇操作的代價6.3.3連接運算（10）索引嵌套循環(huán)連接（續(xù)）對關(guān)系S使1206.3.3連接運算（11）排序-歸并連接類似于外排序的歸并算法的思路，進行連接運算。前提：兩個關(guān)系的元組都已按連接屬性排好序。適用于自然連接和等值連接。a3b1d8d13f7m5q6aAaGcLdNmB

rsa1a2a1a3在歸并連接中使用的已排序關(guān)系rs6.3.3連接運算（11）排序-歸并連接a3b1d8d11216.3.3連接運算（12）pr:=r的第一個元組的地址ps:=s的第一個元組的地址；while(ps≠nul