時間：2022-12-12 08:30:01 | 來源：信息時代
時間：2022-12-12 08:30:01 來源：信息時代
并行嵌套循環(huán)連接算法 : 采用嵌套循環(huán)連接的方法所構(gòu)成的一種并行算法,該算法首先把兩個被連接關(guān)系中的小關(guān)系均勻地分布到多個處理機(jī),然后把大關(guān)系的元組以流水線方式向各處理機(jī)廣播,各處理機(jī)并行地完成連接操作。傳統(tǒng)的嵌套循環(huán)連接算法必須存取兩個關(guān)系的笛卡兒乘積,在順序計算機(jī)環(huán)境中一直被認(rèn)為是效率較低的連接算法。然而,嵌套循環(huán)連接算法很容易并行化,而且可通過附加的計算減少多處理機(jī)間的通信開銷。并行嵌套循環(huán)連接算法的輸入為:處理機(jī)個數(shù)P; 分布在P個處理機(jī)上的關(guān)系R、S,其初始數(shù)據(jù)偏斜度分別為sR和sS; 連接屬性A。算法輸出為關(guān)系R和S的連接結(jié)果。算法主要思想如下: 首先將關(guān)系S均勻地分布到多個處理機(jī),設(shè)Si是S在結(jié)點i上的子集合; 各處理機(jī)Pi并行地按照連接屬性值排序Si: 然后各處理機(jī)以流水線方式向P個處理機(jī)廣播R的元組; 最后各處理機(jī)Pi以流水線方式并行地接收并按連接屬性值排序其他處理機(jī)發(fā)來的R元組,對磁盤上的Si和內(nèi)存中的R元組做合并連接。
在具有大量處理機(jī)的系統(tǒng)中或在R和S的大小差別非常大的情況下,并行嵌套循環(huán)連接算法的效率高于其他并行連接算法。
微信公眾號
版權(quán)所有? 億企邦 1997-2022 保留一切法律許可權(quán)利。
在線咨詢