第9章數(shù)據(jù)庫查詢優(yōu)化課件

第9章數(shù)據(jù)庫查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3基于半聯(lián)接的查詢優(yōu)化9.4基于枚舉法的查詢優(yōu)化第9章數(shù)據(jù)庫查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。

查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語言的級別很高，使DBMS可以從關(guān)系表達式中分析查詢語義。9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的必要性9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化用戶不必考慮如何最好地表達查詢以獲得較好的效率系統(tǒng)可以比用戶程序的優(yōu)化做得更好(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則難以獲得這些信息

9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化用戶不必考慮如何最好地表達查9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化(2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實際應(yīng)用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化(2)如果數(shù)據(jù)庫的物理統(tǒng)計信9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的總目標選擇有效策略，求得給定關(guān)系表達式的值實際系統(tǒng)的查詢優(yōu)化步驟1.將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹2.根據(jù)一定的等價變換規(guī)則把語法樹轉(zhuǎn)換成標準（優(yōu)化）形式9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的總目標例：有查詢Q1：查詢北部地區(qū)（AREA=‘North’）所屬部門發(fā)出訂單的供應(yīng)商號。這里涉及兩個全局關(guān)系Dept(D#,DNAME,MGTRSSN,AREA)和Sp(S#,P#,D#,QUAN)，SQL表達式為：

SelectS＃

FromDept,SpWhereSp?D＃=Dept.?D＃AndAREA=‘North’;其相應(yīng)的代數(shù)表達式為：

πS#σAREA=‘North’（Sp

∞

Dept）

D＃=D＃其相應(yīng)的查詢樹如下：

πs#

бAREA=‘Nouth’

∞

D＃=D＃

SpDept查詢樹顯然，邊為E1（∞，Sp）

D＃=D＃時，則Sp是非葉節(jié)點∞的分量。例：有查詢Q1：查詢北部地區(qū)（AREA=‘North’）所屬查詢表達式的等價性[例]：對關(guān)系Emp,有如下SQL查詢表達式

SelectENAME,DNOFromEmpWhereDNO=‘15’;（4-1）

其相應(yīng)的代數(shù)操作表達式為：

πENAME，DNO（σDNO=’15’

Emp）（4-2）

或

σDNO=‘15’（πENAME，DNOEmp）

（4-3）本例表示了不同的操作順序仍可獲得相同的結(jié)果。這就是等價的概念。[定義4.2]：兩個查詢表達式E1和E2是等價的，如果其查詢的結(jié)果是相同的，記為E1≡E2。查詢表達式的等價性[例]：對關(guān)系Emp,有如下SQL查詢表9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化3.選擇低層的操作算法對于語法樹中的每一個操作計算各種執(zhí)行算法的執(zhí)行代價選擇代價小的執(zhí)行算法4.生成查詢計劃(查詢執(zhí)行方案)查詢計劃是由一系列內(nèi)部操作組成的查詢樹可以理解為全局查詢樹根據(jù)等價定義，可用三種方式描述查詢：SQL表達式（查詢語句）

代數(shù)表達式

查詢樹9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化3.選擇低層的操作算法查詢代價模型集中式數(shù)據(jù)庫單用戶系統(tǒng)

總代價=I/O代價+CPU代價多用戶系統(tǒng)

總代價=I/O代價+CPU代價+內(nèi)存代價分布式數(shù)據(jù)庫 總代價

=I/O代價+CPU代價[+內(nèi)存代價]+通信代價代價模型集中式數(shù)據(jù)庫9.3基于半聯(lián)接的查詢優(yōu)化4.5.1聯(lián)接操作重要性4.5.2聯(lián)接操作4.5.3半聯(lián)接操作原理和不對稱性4.5.4半聯(lián)接操作的縮減作用4.5.5半聯(lián)接程序的作用4.5.6半聯(lián)接程序的具體過程4.5.7半聯(lián)接技術(shù)的不足9.3基于半聯(lián)接的查詢優(yōu)化4.5.1聯(lián)接操作重要性9.3.1聯(lián)接操作重要性關(guān)系數(shù)據(jù)庫由許多關(guān)系組成，關(guān)系與關(guān)系之間的聯(lián)系主要通過聯(lián)接操作表現(xiàn)出來，因而在二元操作中，聯(lián)接操作遠比其它操作用得多。討論聯(lián)接，其實包括了“選擇——投影——聯(lián)接”的綜合問題，即二元操作和一元操作的綜合優(yōu)化問題。分布式查詢處理的聯(lián)接操作，更是影響分布式查詢效率的最關(guān)鍵因素。在DDB中，聯(lián)接操作的大量數(shù)據(jù)會引起場地間的傳輸，它直接影響整個系統(tǒng)性能。當前對聯(lián)接操作的優(yōu)化有兩種趨向：一種是采用半聯(lián)接技術(shù)來減少聯(lián)接操作的操作數(shù)，以降低通訊費用；另一種是直接進行聯(lián)接操作的代價計算9.3.1聯(lián)接操作重要性關(guān)系數(shù)據(jù)庫由許多關(guān)系組成，關(guān)系與9.3.2聯(lián)接操作聯(lián)接操作是從兩個關(guān)系的笛卡爾積中選取屬性間滿足一定條件的元組。記作：

其中A和B分別為R和S上可比的屬性組。

自然聯(lián)接（Naturaljoin）是一種特殊的等值聯(lián)接，它要求兩個關(guān)系中進行比較的分量必須是相同的屬性組，并且要在結(jié)果中把重復(fù)的屬性去掉。即若R和S具有相同的屬性組B，則自然連接可記作：等值連接（equi-join），θ為“＝”的連接運算稱為等值連接。它是從關(guān)系R與S的笛卡爾積中選取A、B屬性值相等的那些元組。即等值連接為：9.3.2聯(lián)接操作聯(lián)接操作是從兩個關(guān)系的笛卡爾積中選取屬（回顧）自然聯(lián)接圖自然聯(lián)接實例自然聯(lián)接的結(jié)果是在R和S中的在它們的公共屬性名字上相等的所有元組的組合。例如下面是表格“雇員”和“部門”和它們的自然聯(lián)接:（回顧）自然聯(lián)接圖自然聯(lián)接實例自然聯(lián)接的結(jié)果是在R和（回顧）等值聯(lián)接圖θ-聯(lián)接實例θ-聯(lián)接和等值聯(lián)接如果我們要組合來自兩個關(guān)系的元組，而組合條件不是簡單的共享屬性上的相等，則有一種更一般形式的連接算子才方便，這就是θ-聯(lián)接(或theta-聯(lián)接)。θ是在集合{<,≤,=,>,≥}中的二元關(guān)系。θ的結(jié)果由在R

和S

中滿足關(guān)系θ的元素的所有組合構(gòu)成。只有S

和R

的表頭是不相交的，即不包含公共屬性的情況下，θ-連接的結(jié)果才是有定義的。實例：考慮分別列出車模和船模的價格的表“車”和“船”。假設(shè)一個顧客要購買一個車模和一個船模，但不想為船花費比車更多的錢。在關(guān)系上的θ-聯(lián)接CarPrice≥BoatPrice

生成所有可能選項的一個表。（回顧）等值聯(lián)接圖θ-聯(lián)接實例θ-聯(lián)接和等值聯(lián)接9.3.3半聯(lián)接操作原理和不對稱性半聯(lián)接操作是關(guān)系代數(shù)操作中聯(lián)接（JOIN）操作的一種縮減，關(guān)系R和S的半聯(lián)接記為R∝S。其結(jié)果關(guān)系是R和S的自然聯(lián)接（NaturalJOIN）后，在R的屬性上的投影，可用下述表達式表示：

R∝S=πR（R∞S）

等價方法：將S中與R有相同屬性名的屬性集投影出來，然后與R完成自然聯(lián)接，其等價公式為：R∝S=R∞

（πBS）

具不對稱操作性：R∝S≠S∝R。

9.3.3半聯(lián)接操作原理和不對稱性半聯(lián)接操作是關(guān)系代數(shù)操（回顧）半聯(lián)接圖半聯(lián)接實例半聯(lián)接的結(jié)果只是在S

中有在公共屬性名字上相等的元組所有的R

中的元組。實例：“雇員”和“部門”和它們的半聯(lián)接的表:

（回顧）半聯(lián)接圖半聯(lián)接實例半聯(lián)接的結(jié)果只是在S中有在9.3.4半聯(lián)接操作的縮減作用例4.17

有R（A,B）和S（B,C），根據(jù)半聯(lián)接計算公式有：和。如果有圖4.21（a）的實例，則RS的結(jié)果如4.21（b）所示，SR的結(jié)果如圖4.21（C）所示。圖4.12半聯(lián)接操作的不對稱性與縮減作用

從圖4.21（b）、（c）可得出結(jié)論：半聯(lián)接操作對操作數(shù)R或S有縮減作用，且由于其不對稱性則各自縮減的程度不一樣。半聯(lián)接操作的縮減性與在聯(lián)接操作前先對操作數(shù)關(guān)系做選擇和投影有相似的效果。特別在分布式環(huán)境中，可用半聯(lián)接操作減少網(wǎng)上數(shù)據(jù)的傳送量。

9.3.4半聯(lián)接操作的縮減作用例4.17有R（A,B9.3.5半聯(lián)接程序的作用半聯(lián)接程序是用半聯(lián)接技術(shù)實現(xiàn)聯(lián)接操作的程序，即用一組具有半聯(lián)接與聯(lián)接的操作，映射出具有與等值聯(lián)接相同結(jié)果的過程。

(4-11a)(4-11b)（4－11a）、（4－11b）式說明半聯(lián)接程序與兩個關(guān)系的直接等值聯(lián)接等價。

同樣，在分布式數(shù)據(jù)庫中，當R，S兩個關(guān)系不在相同場地上時，用（4－11a）公式或（4－11b）公式處理，可以減少聯(lián)接操作的數(shù)據(jù)傳送量，并且半聯(lián)接程序的技術(shù)可以縮減它的操作數(shù)。

9.3.5半聯(lián)接程序的作用半聯(lián)接程序是用半聯(lián)接技術(shù)實現(xiàn)聯(lián)9.3.6半聯(lián)接程序的具體過程以式（4-11a）為例，且假定R和S不在同一場地：①在s場地對S關(guān)系做投影操作，使S關(guān)系縮減為S′：

②將S′送往r場地；

③在r場地上完成R與S′的半聯(lián)接操作，使R關(guān)系縮減為R′：④將R’關(guān)系送回S場地；

⑤在S場地完成R’與S的聯(lián)接操作。

圖4.22半聯(lián)接程序操作

圖4.22的核心技術(shù)思想是只將聯(lián)接操作有關(guān)的操作分量在網(wǎng)上進行傳輸。R與S關(guān)系在A=B條件下聯(lián)接，R、S關(guān)系只有公共屬性值相等的那些元組才有意義。

9.3.6半聯(lián)接程序的具體過程以式（4-11a）為例，且半聯(lián)接技術(shù)是通過局部縮減操作關(guān)系的數(shù)據(jù)量，發(fā)送縮減的關(guān)系到執(zhí)行場地，在執(zhí)行場地對縮減后的關(guān)系進行查詢處理。采用該技術(shù)大大降低了場地間傳遞的信息量，從而減少了整個系統(tǒng)的傳輸代價。但是，半聯(lián)接技術(shù)使傳輸代價降低的同時，也增加了系統(tǒng)的局部處理代價。因此，半聯(lián)接技術(shù)有如下不足：（1）沒有考慮局部代價。（2）當選擇度較低時，半聯(lián)接技術(shù)才能夠達到減少傳輸代價的效果。9.3.7半聯(lián)接技術(shù)的不足半聯(lián)接技術(shù)是通過局部縮減操作關(guān)系的數(shù)據(jù)量，發(fā)送縮減的關(guān)系到執(zhí)9.4.1概述9.4.2嵌套循環(huán)聯(lián)接算法9.4.3基于排序的聯(lián)接算法9.4.4散列連接算法9.4基于枚舉法的查詢優(yōu)化9.4.1概述9.4基于枚舉法的查詢優(yōu)化半聯(lián)接優(yōu)化方法能夠減少查詢執(zhí)行的通信代價，但是同時會導(dǎo)致通信次數(shù)的增加和局部執(zhí)行代價的增加。當系統(tǒng)環(huán)境為高速局域網(wǎng)時，查詢執(zhí)行代價主要考慮的是局部處理代價，半聯(lián)接優(yōu)化方法則不再適用。在這種情況下，分布式數(shù)據(jù)庫系統(tǒng)通常使用基于直接聯(lián)接技術(shù)的枚舉法優(yōu)化技術(shù)。所謂枚舉法優(yōu)化，就是枚舉聯(lián)接操作所有可行的直接聯(lián)接算法，通過對每種方法的查詢執(zhí)行代價估計，從中選擇一種代價最小的算法作為聯(lián)接操作的執(zhí)行算法。直接聯(lián)接算法廣泛應(yīng)用于集中式數(shù)據(jù)庫系統(tǒng)中，包括：嵌套循環(huán)連接算法、歸并排序連接算法、散列連接算法和基于索引的連接算法。9.4.1概述半聯(lián)接優(yōu)化方法能夠減少查詢執(zhí)行的通信代價，但是同時會導(dǎo)致通信9.4.2.1基于元組的嵌套循環(huán)聯(lián)接9.4.2.2基于塊的嵌套循環(huán)聯(lián)接9.4.2.3嵌套循環(huán)聯(lián)接方法的代價估計9.4.2嵌套循環(huán)聯(lián)接算法9.4.2.1基于元組的嵌套循環(huán)聯(lián)接9.4.2嵌套循環(huán)聯(lián)嵌套循環(huán)連接算法是一種最簡單的聯(lián)接算法，其原理是對聯(lián)接操作的兩個關(guān)系對象中的一個僅讀取其元組一次，而對另一個關(guān)系對象中元組將重復(fù)讀取。嵌套循環(huán)聯(lián)接算法的特點是可以用于任何大小的關(guān)系間的連接操作，不必受連接操作所分配的內(nèi)存空間大小的限制。對于嵌套循環(huán)連接算法，可根據(jù)每次操作的對象大小分為基于元組的嵌套循環(huán)連接和基于塊的嵌套循環(huán)連接。9.4.2.1基于元組的嵌套循環(huán)聯(lián)接圖4.13兩個聯(lián)接關(guān)系假設(shè)有關(guān)系R(A,B)和關(guān)系S(B,C)，分別有Card(R)=n和Card(S)=m，現(xiàn)在要執(zhí)行兩個關(guān)系在屬性B上的連接操作，如圖4.13所示。嵌套循環(huán)連接算法是一種最簡單的聯(lián)接算法，其原理是對聯(lián)接操作的基于元組的嵌套循環(huán)連接Result={};/*初始化結(jié)果集合*/ForeachtuplesinSForeachtuplerinRIfr.B=s.Bthen/*元組r和元組s滿足連接條件*/Joinrandsastuplet;OutputtintoResult;/*輸出連接結(jié)果元組*/EndifEndforEndforReturnResult9.4.2.1基于元組的嵌套循環(huán)聯(lián)接基于元組的嵌套循環(huán)連接9.4.2.1基于元組的嵌套循環(huán)聯(lián)接上面基于元組的嵌套循環(huán)連接算法中，對于循環(huán)外層的關(guān)系，通常稱為外關(guān)系，而對循環(huán)內(nèi)層的關(guān)系稱為內(nèi)關(guān)系。在執(zhí)行嵌套循環(huán)連接時，僅對外關(guān)系進行1次讀取操作，而對內(nèi)關(guān)系則需要進行反復(fù)讀取操作。如果不進行優(yōu)化的話，這種基于元組的執(zhí)行代價很大，以磁盤IO計算最多可能達到Card(R)*Card(S)。因此，通常對這種算法進行修改，以減少嵌套循環(huán)連接的磁盤IO代價。一種方法是使用連接屬性上的索引，以減少參與連接元組的數(shù)量；另一種方法是通過盡可能多地使用內(nèi)存以減少磁盤IO數(shù)目（由此產(chǎn)生了基于塊的嵌套循環(huán)聯(lián)接算法）。9.4.2.1基于元組的嵌套循環(huán)聯(lián)接上面基于元組的嵌套循環(huán)連接算法中，對于循環(huán)外層的關(guān)系，通常稱基于塊的嵌套循環(huán)連接方法是通過盡可能多地使用內(nèi)存，減少讀取元組所需的I/O次數(shù)。其中，對連接操作的兩個關(guān)系的訪問均按塊進行組織，同時使用盡可能多的內(nèi)存來存儲嵌套循環(huán)中的外關(guān)系的塊。與基于元組的方法類似，將連接操作中的一個對象作為外關(guān)系，每次讀取部分元組到內(nèi)存中，整個關(guān)系只讀取一次，而另一個對象作為內(nèi)關(guān)系，反復(fù)讀取到內(nèi)存中執(zhí)行連接。對于每個邏輯操作符，數(shù)據(jù)庫系統(tǒng)都會分配一個有限的內(nèi)存緩沖區(qū)。假設(shè)為連接操作分配的內(nèi)存緩沖區(qū)大小為M個塊，同時有Block(R)≥Block(S)≥M，即連接的兩個關(guān)系都不能完全讀取到內(nèi)存中。為此，首先選擇較小的關(guān)系作為外關(guān)系，這里選擇關(guān)系S。將1到M-1塊分配給關(guān)系S，而第M塊分配給關(guān)系R。將外關(guān)系S按照M-1個塊的大小分為多個子表，并將這些子表依次讀取到內(nèi)存緩沖區(qū)中，關(guān)系R的每個塊會被重復(fù)地讀入內(nèi)存和關(guān)系S的子表進行連接。對于內(nèi)存緩沖區(qū)中元組的連接操作，先在M-1個塊的外關(guān)系S元組的連接屬性上構(gòu)建查找結(jié)構(gòu)，再從內(nèi)關(guān)系R在內(nèi)存中的塊中讀取元組，通過查找結(jié)構(gòu)與S中的元組連接。9.4.2.2基于塊的嵌套循環(huán)聯(lián)接基于塊的嵌套循環(huán)連接方法是通過盡可能多地使用內(nèi)存，減少讀取元Result={};/*初始化結(jié)果集合*/Buffer=M;/*內(nèi)存緩沖區(qū)*/ForeachM-1inBlock(S)/*每次從外關(guān)系S中讀取M-1個塊到內(nèi)存緩沖區(qū)中*/ReadM-1ofBlock(S)intoBuffer;ForeachblockinBlock(R)/*每次從內(nèi)關(guān)系R中讀取1個塊到內(nèi)存緩沖區(qū)*/JoinM-1ofBlock(S)and1ofBlock(R)inBuffer;/*在內(nèi)存中對塊中元組執(zhí)行連接*/OutputtintoResult;EndforEndforReturnResult;9.4.2.2基于塊的嵌套循環(huán)聯(lián)接圖4.14基于塊的嵌套循環(huán)連接算法示意圖Result={};/*初始化結(jié)果集合*/9.4.2.2基對于兩個關(guān)系R和S，如果使用基于元組的嵌套循環(huán)連接方法，則需要對每個元組的讀取產(chǎn)生1次磁盤IO。因此，假設(shè)兩個關(guān)系的元組數(shù)量分別為Card(R)和Card(S)，則基于元組的嵌套循環(huán)連接方法的執(zhí)行代價為Card(R)*Card(S)，即兩個關(guān)系大小的乘積。如果使用基于塊的嵌套循環(huán)連接方法，假設(shè)兩個連接關(guān)系R和S占用的塊分別為Block(R)和Block(S)，M為內(nèi)存緩沖區(qū)大小。在嵌套過程中使用S作為外關(guān)系，每次迭代時首先讀取M-1塊S的內(nèi)容到內(nèi)存緩沖區(qū)中，再每次讀取R的Block(R)中的1個塊的內(nèi)容到內(nèi)存中與M-1塊的S內(nèi)容進行連接。因此，連接的代價可以用以下公式計算： Cjoin=(Block(S)/(M-1))*(M-1+Block(R))

公式可以進一步簡化為： Cjoin=Block(S)+(Block(S)/(M-1))*Block(R)從上面公式可以看出，在選擇較小的關(guān)系作為連接的外關(guān)系時，可以獲得最小的執(zhí)行代價，因此，通常選擇較小的關(guān)系作為外關(guān)系。9.4.2.3嵌套循環(huán)聯(lián)接方法的代價估計對于兩個關(guān)系R和S，如果使用基于元組的嵌套循環(huán)連接方法，則需9.4.3.1概述9.4.3.2歸并排序算法9.4.3.3簡單的基于排序的連接算法9.4.3.4歸并排序連接算法9.4.3基于排序的聯(lián)接算法9.4.3.1概述9.4.3基于排序的聯(lián)接算法基于排序的連接算法，首先將兩個關(guān)系按照連接屬性進行排序，然后按照連接屬性的順序掃描兩個關(guān)系，同時，對兩個關(guān)系中的元組執(zhí)行連接操作。由于數(shù)據(jù)庫中關(guān)系的大小往往大于連接操作可用內(nèi)存緩沖區(qū)的大小，因此，對關(guān)系的排序通常采用外存排序算法，即歸并排序算法?？梢詫⒒谂判虻倪B接算法的執(zhí)行過程與歸并排序算法結(jié)合的算法，可以節(jié)省更多的磁盤IO，通常稱為歸并排序連接算法。9.4.3.1概述基于排序的連接算法，首先將兩個關(guān)系按照連接屬性進行排序，然后簡單的歸并排序算法的執(zhí)行可以分為兩個階段：第一階段：對關(guān)系進行分段排序，即首先將需要排序的關(guān)系R劃分為大小為M個塊的子表，其中，M是可用于排序的內(nèi)存空間的個數(shù)，以塊為單位，再將每個子表放入內(nèi)存中采用快速排序等主存排序算法執(zhí)行排序操作，這樣可以獲得一組內(nèi)部已排序的子表。第二階段：對關(guān)系的子表執(zhí)行歸并操作，即按照順序從每個排序的子表中讀取一個塊的內(nèi)容放入內(nèi)存，在內(nèi)存中統(tǒng)一對這些塊中的記錄執(zhí)行歸并操作，每次選擇最大（最?。┑挠涗浄湃胼敵鼍彌_區(qū)中，同時刪除子表中相應(yīng)的記錄。當子表在內(nèi)存中的塊被取空時，從子表中順序讀取一個新的塊放入到內(nèi)存中繼續(xù)執(zhí)行歸并操作。9.4.3.2歸并排序算法簡單的歸并排序算法的執(zhí)行可以分為兩個階段：9.4.3.2歸圖4.15簡單的歸并排序算法的執(zhí)行9.4.3.2歸并排序算法歸并排序的過程如圖4.15所示，其中同時對多個子表執(zhí)行歸并操作，因此，也稱為兩階段多路歸并排序。需要說明的是，第二階段的歸并操作執(zhí)行的條件是關(guān)系的子表數(shù)量小于排序操作可用的內(nèi)存的塊數(shù)M，這樣才能保證同時對所有子表進行歸并操作。因此，兩階段歸并執(zhí)行的條件是關(guān)系的大小Block(R)≤M2。如果關(guān)系的大小大于M2，則需要嵌套執(zhí)行歸并排序算法，使用三階段或更多次的歸并操作。圖4.15簡單的歸并排序算法的執(zhí)行9.4.3.2歸并基于排序的連接算法，主要是對已經(jīng)按照連接屬性排序的兩個關(guān)系，按照順序讀取關(guān)系中的塊到內(nèi)存中執(zhí)行連接操作。*代價計算*假設(shè)在排序階段使用的是兩階段多路歸并排序，關(guān)系的大小滿足條件Block(R)≤M2，Block(S)≤M2。這樣，算法在排序階段的執(zhí)行代價包括對關(guān)系的子表執(zhí)行排序所需的一次讀（讀子表數(shù)據(jù)）和一次寫（子表排序結(jié)果寫入磁盤）的代價2(Block(R)+Block(S))，以及多路歸并時的讀寫代價2(Block(R)+Block(S))，而在歸并連接階段還需要對關(guān)系執(zhí)行一次讀操作，代價為Block(R)+Block(S)。因此，簡單的基于排序的連接算法的執(zhí)行代價為：Cjoin=5(Block(R)+Block(S))。9.4.3.3簡單的基于排序的連接算法圖4.16簡單的排序連接算法基于排序的連接算法，主要是對已經(jīng)按照連接屬性排序的兩個關(guān)系，在簡單的基于排序的連接算法中，歸并連接階段僅僅使用了內(nèi)存緩沖區(qū)的兩個塊的空間，還有大量的空閑內(nèi)存沒有使用。因此，一種更加有效的歸并排序連接算法被提出，其思想是將排序的第二階段與歸并連接階段合并，即直接使用兩個關(guān)系的排序子表執(zhí)行歸并連接操作，這樣可以節(jié)省一次對關(guān)系的讀寫操作。假設(shè)可用內(nèi)存緩存區(qū)為M個塊，算法首先對兩個關(guān)系劃分成大小為M個塊的子表并排序，再從每個子表中順序讀取一個塊調(diào)入內(nèi)存緩沖區(qū)執(zhí)行連接操作。這里要求兩個關(guān)系的子表總數(shù)不超過M個。9.4.3.4歸并排序連接算法圖4.17歸并排序連接算