[發明專利]一種基于流水線的分布式多表連接方法及系統

有效

• 申請號: 201710361245.0
• 申請日: 2017-05-19
• 公開（公告）號: CN107229692B
• 公開（公告）日: 2018-05-01
• 發明（設計）人: 王宏志;孫旭冉;趙志強
• 申請（專利權）人: 哈工大大數據產業有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京格允知識產權代理有限公司11609
• 代理人: 周嬌嬌,譚輝

1.一種基于流水線的分布式多表連接方法，其特征在于，該方法包括并行執行的以下步驟：

A、映射處理單元從分布式文件系統讀取待連接表，將所述待連接表進行映射處理后得到對應的數據塊，并以每兩個待連接表為一組，將第一組表的數據塊輸出至第一規約處理單元，將第二組至末尾組表的數據塊按序輸出至第二規約處理單元；

B、第二規約處理單元按序讀取第二組至末尾組表的數據塊，并對每組表的兩個數據塊進行哈希連接得到每組表的兩表連接結果；

C、第一規約處理單元讀取第一組表的兩個數據塊進行哈希連接后作為初始的多表連接結果，并在等待第二規約處理單元完成一組表的哈希連接后，將當前的多表連接結果與該組表的兩表連接結果進行順序連接以更新多表連接結果，直至所有組表完成連接后輸出多表連接結果；

所述步驟A包括以下步驟：

在t₁時刻，映射處理單元讀取待連接表T₁至T₄，對所述待連接表T₁至T₄進行映射處理后得到對應的數據塊B₁至B₄，并將第一組表的數據塊B₁和B₂輸出至所述第一規約處理單元，將第二組表的數據塊B₃和B₄輸出至所述第二規約處理單元；

在t_i時刻，其中i＝2,3,…,j-1，j為待連接表的組數；映射處理單元讀取待連接表T_2i+1和T_2i+2，對所述待連接表T_2i+1和T_2i+2進行映射處理后得到第i+1組表的數據塊B_2i+1至B_2i+2，并輸出至第二規約處理單元；

且該步驟A的映射處理為自適應的雙階段分割；

所述步驟B包括以下步驟：

在t_i時刻，其中i＝2,3,…,j；第二規約處理單元讀取第i組表的數據塊B_2i-1至B_2i進行哈希連接后得到第i組表的兩表連接結果H_i；

所述步驟C包括以下步驟：

在t₂時刻，第一規約處理單元讀取第一組表的數據塊B₁至B₂進行哈希連接后作為初始的多表連接結果S₁；

在t_i時刻，其中i＝3,4,…,j+1；第一規約處理單元在等待第二規約處理單元完成第i-1組表的哈希連接后，將當前的多表連接結果S_i-2與第i-1組表的兩表連接結果H_i-1進行順序連接得到更新的多表連接結果S_i-1。

2.根據權利要求1所述的基于流水線的分布式多表連接方法，其特征在于，所述步驟A中還包括：

在判斷待連接表的總數n為奇數時，在待連接表中增加一個空表，且待連接表的組數

在判斷待連接表的總數n為偶數時，待連接表的組數

3.根據權利要求1所述的基于流水線的分布式多表連接方法，其特征在于，所述自適應的雙階段分割包括：

在第一階段依據連接屬性對頂層數據進行分割；

在第二階段依據數據規模和規約器的個數對底層數據進行分割。