嵌套循環(huán)連接(數(shù)據(jù)庫)

時(shí)間：2022-11-07 06:30:01 | 來源：信息時(shí)代

時(shí)間：2022-11-07 06:30:01 來源：信息時(shí)代

    嵌套循環(huán)連接 : 用雙層循環(huán)來實(shí)現(xiàn)連接的算法,包括基于元組的連接方法和基于塊的連接方法。它對(duì)內(nèi)存要求較小。
1.基于元組的嵌套循環(huán)連接方法
對(duì)于R(X,Y)和S(Y,Z)的基于元組的嵌套循環(huán)連接方法(假設(shè)連接屬性為Y),其連接過程為:
首先在外層循環(huán)表(R)中找到第一條元組,然后從頭開始掃描內(nèi)層循環(huán)表(S)中的每一條元組,逐一查找滿足連接條件的元組,找到后就將外層循環(huán)表中的第一條元組與該元組拼接起來,形成結(jié)果表中的一條元組。
內(nèi)層循環(huán)表(S)全部查找完后,再找外層循環(huán)表(R)中第二條元組,然后再從頭開始掃描內(nèi)層循環(huán)表(S),逐一查找滿足連接條件的元組,找到后就將外層循環(huán)表(R)中的第二條元組與該元組拼接起來,形成結(jié)果表中一條元組。
重復(fù)上述操作,直到外層循環(huán)表(R)中的全部元組都處理完畢為止。
具體算法如下:
FOR each tuple r in R DO
FOR each tuple s in S DO
IF s and r join to make a tuple t THEN
output t;
很明顯,基于元組的嵌套循環(huán)連接方法其I/O代價(jià)很大,對(duì)于外層關(guān)系R的每條元組,都要從頭讀一遍內(nèi)層關(guān)系,即內(nèi)層關(guān)系讀取的遍數(shù)等于外層關(guān)系的元組個(gè)數(shù)。假設(shè)B(R)和B(S)分別代表關(guān)系R和S占用的磁盤塊數(shù),T(R)和T(S)分別代表關(guān)系R和S的元組數(shù),假設(shè)R是較小的關(guān)系,即B(R)≤B(S),則基于元組的嵌套循環(huán)連接方法的磁盤I/O次數(shù)為:T(R)+T(R)*B(S)。
2.基于塊的嵌套循環(huán)連接方法
如果對(duì)作為操作對(duì)象的兩個(gè)關(guān)系的訪問均以塊為單位,并用盡可能多的內(nèi)存來存儲(chǔ)外層循環(huán)表(R)的元組,將S的每一條元組與能裝入內(nèi)存的盡可能多的R元組連接,則可以減少讀取R表的遍數(shù),從而節(jié)省連接操作的代價(jià)。假設(shè)有M塊內(nèi)存緩沖區(qū),其連接過程為:
(1)把外層循環(huán)表(R)盡可能多地讀入內(nèi)存(比如讀入M-1塊),讀入一塊內(nèi)層循環(huán)表(S)。①對(duì)于R在內(nèi)存中的第一條元組,從頭開始掃描內(nèi)層循環(huán)表(S)在內(nèi)存中的每一條元組,逐一查找滿足連接條件的元組,找到后就將外層循環(huán)表中的第一條元組與該元組拼接起來,形成結(jié)果表中一條元組。②內(nèi)層循環(huán)表(S)在內(nèi)存中的部分全部查找完后,再找外層循環(huán)表(R)在內(nèi)存中第二條元組,然后再從頭開始掃描內(nèi)層循環(huán)表(S),逐一查找滿足連接條件的元組,找到后就將外層循環(huán)表(R)中的第二條元組與該元組拼接起來,形成結(jié)果表中一條元組。③重復(fù)上述操作,直到外層循環(huán)表(R)在內(nèi)存部分的全部元組都處理完畢為止。
(2) 內(nèi)層表S的在內(nèi)存中的數(shù)據(jù)塊淘汰,讀入S的下一塊數(shù)據(jù),重復(fù)操作1,直到內(nèi)層循環(huán)表(S)全部處理完畢為止。
(3)外層表R的M-1塊數(shù)據(jù)全部淘汰,再讀入M—1塊數(shù)據(jù)進(jìn)來,重復(fù)操作1和2,直到外層循環(huán)表(R)的全部元組都處理完畢為止。
假設(shè)B(R)和B(S)分別代表關(guān)系R和S占用的磁盤塊數(shù),其中R是較小的關(guān)系,即B(R)≤B(S),則基于塊的嵌套循環(huán)連接方法的磁盤I/O次數(shù)為

B(R)/M-1(M-1+B(S))或B(R)+B(R)B(S)/M-1。

例如,對(duì)于R(X,Y)和S(Y,Z)的基于塊的嵌套循環(huán)連接,假定B(S)=5000,B(R)=300,M=51。如果使用50個(gè)內(nèi)存塊對(duì)R進(jìn)行緩沖,則算法中的外層循環(huán)需迭代6次。每一次迭代中,用50個(gè)磁盤I/O讀取R,在第二層循環(huán)中用5000個(gè)磁盤I/O讀取S。因此,磁盤I/O的總數(shù)量是: 300+6×5000=30300。如果交換R和S的位置,則磁盤I/O總數(shù)為: 5000+100×300=35000。顯然,應(yīng)該在外層循環(huán)中使用較小的關(guān)系。