并行排序合并連接算法(數(shù)據(jù)庫(kù))

時(shí)間：2022-12-13 02:30:01 | 來源：信息時(shí)代

時(shí)間：2022-12-13 02:30:01 來源：信息時(shí)代

    并行排序合并連接算法 : 對(duì)排序合并算法并行化的連接算法。它的最大優(yōu)點(diǎn)是產(chǎn)生一個(gè)有序的結(jié)果集合。如果被連接關(guān)系已經(jīng)按照連接屬性排序,可以省略算法的排序階段,只用合并操作就可以產(chǎn)生連接結(jié)果。這時(shí),排序合并連接算法的效率相當(dāng)高。并行排序合并連接算法由兩個(gè)階段組成,即排序和連接階段。在排序階段,它按照連接屬性的值排序每個(gè)連接關(guān)系;在連接階段,使用合并算法完成兩個(gè)排序關(guān)系的連接。主要有兩種并行排序合并連接算法。
1. 第一種排序合并算法PSMJ1
首先在多處理機(jī)之間分布連接關(guān)系,然后每個(gè)處理機(jī)對(duì)連接子集合進(jìn)行排序合并連接。設(shè)“R₁,R₂,…,R_P”是R的P個(gè)子集合,“S₁,S₂,…,S_P”是S的P個(gè)子集合,A是關(guān)系R和S的連接屬性。如果對(duì)于所有r∈R_i,所有s∈S_j,r[A]≠s[A],則稱子集合對(duì)(R_i,S_j)是可獨(dú)立連接對(duì)。PSMJ1算法的輸入為:處理機(jī)個(gè)數(shù)P;關(guān)系R和S;連接屬性A。算法的輸出為關(guān)系R和S的連接結(jié)果。算法主要思想如下:首先把R和S分別劃分為P個(gè)可獨(dú)立連接對(duì)(R₁,S₁)…(R_P,S_P),(R_i,S_i)并發(fā)送到各處理機(jī)P_i;然后各處理機(jī)P_i并行地排序R_i和S_i;最后各處理機(jī)P_i并行地用合并算法完成R_i和S_i的連接。算法PSMJ1的數(shù)據(jù)劃分的實(shí)現(xiàn)方法有多種。例如,可以使用Hash方法實(shí)現(xiàn)這一步的數(shù)據(jù)劃分。
2.第二種排序合并算法PSMJ2
該算法首先使用隨機(jī)數(shù)據(jù)劃分方法把R和S劃分為P個(gè)可獨(dú)立連接對(duì)(R₁,S₁)…(R_P,S_P),(R_i,S_i)送處理機(jī)i; 然后,各個(gè)處理機(jī)i完成R_i和S_i連接。PSMJ2算法的輸入為: 處理機(jī)個(gè)數(shù)P;分布于P個(gè)處理機(jī)上的關(guān)系R和S;連接屬性A。算法的輸出為關(guān)系R和S的連接結(jié)果。算法主要思想是: 各處理機(jī)P_i從R_i抽取樣本SAMPLEi并將排序后的樣本SAMPLEi發(fā)送到指定處理機(jī)P₁;處理機(jī)P₁把其他處理機(jī)送來的樣本合并為一個(gè)有序樣本SAMPLE并將其劃分為P個(gè)相等的子序列,分點(diǎn)集合P_v＝〈x₁,…,x_P-1〉作為R和S的劃分向量;然后處理機(jī)P₁把P_v廣播給其他處理機(jī); 隨后各處理機(jī)P_i并行地讀R和S的子集合R_i和S_i并按P_v劃分R_i和S_i為SR_i,1＝{x|x∈R_i,x<x₁},SR_i,j＝{x|x∈R_i,x_j-1≤x<x_j},2≤j≤P-1,SR_i,P＝{x|x∈R_i,x_P-1≤x},SS_i,1＝{x|x∈S_i,x<x₁},SS_i,j＝{x|x∈S_i,x_j-1≤x<x_j},2≤j≤P-1,SS_i,P＝{x|x∈S_i,x_P-1≤x},同時(shí)把(SR_i,j,SS_i,j)送處理機(jī)P_j(1≤j≤P);同時(shí)各處理器接收其他處理機(jī)送來的R和S的子集合,合并成SR_i和SS_i; 最后各處理機(jī)P_i并行地使用順序排序合并算法完成SR_i和SS_i的連接并輸出R和S的連接結(jié)果。