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

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

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

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

SelectS＃

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

πS#σAREA=‘North’（Sp

∞

Dept）

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

πs#

бAREA=‘Nouth’

∞

D＃=D＃

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

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

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

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

πENAME，DNO（σDNO=’15’

Emp）（4-2）

或

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

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

代數(shù)表達(dá)式

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

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

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

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

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

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

和S

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

和R

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

生成所有可能選項(xiàng)的一個(gè)表。（回顧）等值聯(lián)接圖θ-聯(lián)接實(shí)例θ-聯(lián)接和等值聯(lián)接9.3.3半聯(lián)接操作原理和不對(duì)稱性半聯(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的屬性上的投影，可用下述表達(dá)式表示：

R∝S=πR（R∞S）

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

（πBS）

具不對(duì)稱操作性：R∝S≠S∝R。

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

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

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

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

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

從圖4.21（b）、（c）可得出結(jié)論：半聯(lián)接操作對(duì)操作數(shù)R或S有縮減作用，且由于其不對(duì)稱性則各自縮減的程度不一樣。半聯(lián)接操作的縮減性與在聯(lián)接操作前先對(duì)操作數(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ù)實(shí)現(xiàn)聯(lián)接操作的程序，即用一組具有半聯(lián)接與聯(lián)接的操作，映射出具有與等值聯(lián)接相同結(jié)果的過(guò)程。

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

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

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

②將S′送往r場(chǎng)地；

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

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

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

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

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

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

DepartmentofComputerScience,XiamenUniversity,2017實(shí)時(shí)主動(dòng)數(shù)據(jù)倉(cāng)庫(kù)相關(guān)問(wèn)題研究DepartmentofC第9章數(shù)據(jù)庫(kù)查詢優(yōu)化課件第9章數(shù)據(jù)庫(kù)查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3基于半聯(lián)接的查詢優(yōu)化9.4基于枚舉法的查詢優(yōu)化第9章數(shù)據(jù)庫(kù)查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。

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

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

SelectS＃

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

πS#σAREA=‘North’（Sp

∞

Dept）

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

πs#

бAREA=‘Nouth’

∞

D＃=D＃

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

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

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

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

πENAME，DNO（σDNO=’15’

Emp）（4-2）

或

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

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

代數(shù)表達(dá)式

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

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

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

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

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

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

和S

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

和R

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

生成所有可能選項(xiàng)的一個(gè)表。（回顧）等值聯(lián)接圖θ-聯(lián)接實(shí)例θ-聯(lián)接和等值聯(lián)接9.3.3半聯(lián)接操作原理和不對(duì)稱性半聯(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的屬性上的投影，可用下述表達(dá)式表示：

R∝S=πR（R∞S）

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

（πBS）

具不對(duì)稱操作性：R∝S≠S∝R。

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

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

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

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

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

從圖4.21（b）、（c）可得出結(jié)論：半聯(lián)接操作對(duì)操作數(shù)R或S有縮減作用，且由于其不對(duì)稱性則各自縮減的程度不一樣。半聯(lián)接操作的縮減性與在聯(lián)接操作前先對(duì)操作數(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ù)實(shí)現(xiàn)聯(lián)接操作的程序，即用一組具有半聯(lián)接與聯(lián)接的操作，映射出具有與等值聯(lián)接相同結(jié)果的過(guò)程。

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

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

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

②將S′送往r場(chǎng)地；

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

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

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

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

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

公式可以進(jìn)一步簡(jiǎn)化為： Cjoin=Block(S)+(Block(S)/(M-1))*Block(R)從上面公式可以看出，在選擇較小的關(guān)系作為連接的外關(guān)系時(shí)，可以獲得最小的執(zhí)行代價(jià)，因此，通常選擇較小的關(guān)系作為外關(guān)系。9.4.2.3嵌套循環(huán)聯(lián)接方法的代價(jià)估計(jì)對(duì)于兩個(gè)關(guān)系R和S，如果使用基于元組的嵌套循環(huán)連接方法，則需9.4.3.1概述9.4.3.2歸并排序算法9.4.3.3簡(jiǎn)單的基于排序的連接算法9.4.3.4歸并排序連接算法9.4.3基于排序的聯(lián)接算法9.4.3.1概述9.4.3基于排序的聯(lián)接算法基于排序的連接算法，首先將兩個(gè)關(guān)系按照連接屬性進(jìn)行排序，然后按照連接屬性的順序掃描兩個(gè)關(guān)系，同時(shí)，對(duì)兩個(gè)關(guān)系中的元組執(zhí)行連接操作。由于數(shù)據(jù)庫(kù)中關(guān)系的大小往往大于連接操作可用內(nèi)存緩沖區(qū)的大小，因此，對(duì)關(guān)系的排序通常采用外存排序算法，即歸并排序算法?？梢詫⒒谂判虻倪B接算法的執(zhí)行過(guò)程與歸并排序算法結(jié)合的算法，可以節(jié)省更多的磁盤IO，通常稱為歸并排序連接算法。9.4.3.1概述基于排序的連接算法，首先將兩個(gè)關(guān)系按照連接屬性進(jìn)行排序，然后簡(jiǎn)單的歸并排序算法的執(zhí)行可以分為兩個(gè)階段：第一階段：對(duì)關(guān)系進(jìn)行分段排序，即首先將需要排序的關(guān)系R劃分為大小為M個(gè)塊的子表，其中，M是可用于排序的內(nèi)存空間的個(gè)數(shù)，以塊為單位，再將每個(gè)子表放入內(nèi)存中采用快速排序等主存排序算法執(zhí)行排序操作，這樣可以獲得一組內(nèi)部已排序的子表。第二階段：對(duì)關(guān)系的子表執(zhí)