并行Hash連接算法(數(shù)據(jù)庫)

時間：2022-12-11 20:30:02 | 來源：信息時代

時間：2022-12-11 20:30:02 來源：信息時代

    并行Hash連接算法 : 把Hash連接算法并行化的一種算法。若Hash函數(shù)能把連接關系劃分為大小基本相同的子集合,則并行Hash連接算法具有線性時間復雜性。主要有三種具有代表性的并行Hash連接算法。
1.簡單并行Hash連接算法
簡單Hash連接算法分為兩個階段。第一階段是數(shù)據(jù)劃分階段。這一階段使用Hash函數(shù)把連接關系R和S劃分為P個可獨立連接的子集合對,每對子集合送到唯一一個處理機。第二階段是連接階段。在這一階段,每個處理機執(zhí)行分配給它的可獨立連接子集合對的連接操作,P個處理機并行地完成R和S的連接。簡單Hash連接算法simple-hash-join的輸入為: 處理機個數(shù)P; 分布于P個處理機上的關系R和S;R_i和S_i是處理機P_i上的子集合;Hash函數(shù)H₁和H₂; 每個處理機可用內(nèi)存頁數(shù)m。算法輸出是關系R和S的連接結果。算法主要思想是:首先各處理器P_i并行地用H₁把S_i和R_i劃分為P個子集合,并將Hash值為j的元組送處理機P_j(設處理機P_i上的R_i和S_i的子集合分別記作HR_i和HS_i),同時接收其他處理機發(fā)送來的元組; 完成關系劃分后,各處理器P_i并行地使用H₂,把HR_i和HS_i劃分為k≥|HR_i|/m個子集合,其中HR_i的Hash值為j的元組存入子集合HR_i,j,HS_i的Hash值為j的元組存入子集合HS_i,j;然后各處理器P_i并行地在內(nèi)存中建立HR_i,j的Hash表并使用HS_i,j的每個元組匹配HR_i,j的Hash表,完成HR_i,j和HS_i,j的連接。算法中的k應該充分大,降低Hash表超出P個處理機的可用存儲空間總量的概率。
2.并行Grace-Hash連接算法
并行Grace-Hash連接算法不要求每個處理機都具有一個磁盤存儲器。設并行計算機系統(tǒng)具有P+L個處理機,其中,P個處理機具有磁盤存儲器,L個處理機不具有磁盤存儲器。
該算法分為兩個階段。第一階段,使用同樣的Hash函數(shù)把關系R和S分別劃分為m個可獨立連接的子集合對。第二階段,并行連接R和S的m個可獨立連接子集合,完成R和S的連接。子集合的個數(shù)m的選擇應該足夠大,使得小關系(比如說R)的每個子集合的大小不超過所有處理機的存儲空間總量。這樣可保證在連接每對可獨立連接子集合的時候,Hash表可以建立在存儲器中,減少磁盤讀寫時間。并行Grace-Hash連接算法在關系劃分階段使用Hash函數(shù)H₁在P個有磁盤處理機之間劃分連接關系;在并行連接可獨立連接子集合階段,每個處理機使用Hash函數(shù)H₂在P+L個處理機之間分布連接關系的子集合。算法的輸入為: 分布于P個處理機上的關系R和S,R_i和S_i是處理機P_i上的子集合;Hash函數(shù)H₁和H₂;所有處理機可用內(nèi)存空間的總頁數(shù)M;子集合數(shù)m≥|R|/M(假設R的數(shù)據(jù)量小于S的數(shù)據(jù)量)。算法輸出是關系R和S的連接結果。算法主要思想如下: 首先各處理機P_i并行地使用H₁把R_i劃分為m個子集合,R_i中Hash值為j的元組屬于HR_j分布到P個有磁盤存儲器的處理機; 然后各處理機P_i并行地使用H₁把S_i劃分為m個子集合,S_i中Hash值為j的元組屬于HR_j分布到P個有磁盤存儲器的處理機;對于m個子集合每個分組HR_i和HS_i,P個有磁盤處理機先使用H₂并行地把HR_i分布到P+L個處理機,在P+L個處理機的內(nèi)存中建立HR_i的Hash表,然后P個有磁盤處理機再使用H₂按照流水線并行方式向P+L個處理機發(fā)送HS_i的元組: 最后P+L個處理器以流水線方式接收HS_i的元組,匹配HR_i的Hash表,連接HS_i和HR_i計算連接結果。
3. 并行Hybrid-Hash連接算法
該算法是對并行Grace-Hash連接算法的改進,不把R和S的第一對可獨立連接子集合寫入磁盤,而直接在內(nèi)存中連接。
假定系統(tǒng)具有P個有磁盤處理機和L個無磁盤處理機。并行Hybrid-Hash連接算法首先使用Hash函數(shù)H₁把R劃分成m個子集合,并把第一個子集合使用Hash函數(shù)H₂分布到無磁盤處理機,其他子集合存入有磁盤處理機; 然后使用Hash函數(shù)H₁劃分S,并使用Hash函數(shù)H₂把第一個子集合分布到無磁盤結點,與R的第一個子集合連接,其余子集合存入具有磁盤的處理機。并行Hybrid-Hash連接算法實現(xiàn)了數(shù)據(jù)劃分和第1個子集合對連接的并行執(zhí)行,提高了運行速度。