[發(fā)明專利]一種基于流水線的分布式多表連接方法及系統(tǒng)

有效

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

技術領域

本發(fā)明涉及分布式數(shù)據(jù)計算技術，尤其涉及一種基于流水線的分布式多表連接方法及系統(tǒng)。

背景技術

大數(shù)據(jù)時代的到來，帶動了數(shù)據(jù)量的迅猛增長，急需一種技術來存儲和處理如此龐大的數(shù)據(jù)量，由此，谷歌的DFS(分布式文件系統(tǒng))和分布式計算模型MapReduce(映射和規(guī)約)應運而生，如今分布式計算技術已成為海量數(shù)據(jù)存儲分析的主流技術。對于海量數(shù)據(jù)分析，連接查詢是一種重要的操作，并且在實際應用時，所需的數(shù)據(jù)可能不僅僅局限于某一個表，而是涉及到多個表，這給連接操作帶來了一定的難度。

在執(zhí)行連接查詢之前，首先要對相應數(shù)據(jù)進行分割，通常的做法是對數(shù)據(jù)進行哈希分割或范圍分割。現(xiàn)有技術中提出了一種自適應的分割方法。此方法使用了一種雙階段的分割算法對數(shù)據(jù)進行了基于屬性的分割：第一階段，依據(jù)連接屬性對最頂層數(shù)據(jù)進行分割；第二階段，依據(jù)數(shù)據(jù)規(guī)模和規(guī)約器(reduce)個數(shù)對底層數(shù)據(jù)進行進一步的分割。這樣的分割算法保證了每一個分割樹都包含單一的連接屬性。當這種自適應的分割算法檢測到一個包含著新的連接屬性的輸入查詢時，它將以同樣的雙階段方法生成一個新的分割樹，該分割樹以新的查詢操作包含的連接屬性為劃分依據(jù)，并且初始狀態(tài)為空。隨著查詢操作的進行，這種分割算法將隨機地從舊的分割樹中選取適當規(guī)模的數(shù)據(jù)進行重分割，并逐漸地將數(shù)據(jù)移動到新的分割樹中，直至新的分割樹中包含的數(shù)據(jù)滿足新的查詢操作。這種基于雙階段的自適應分割算法可以有效地對數(shù)據(jù)進行基于連接屬性的分割，并且避免了出現(xiàn)包含新的連接屬性的查詢操作時，全部數(shù)據(jù)的重新分割，實現(xiàn)了自適應。

然而，這種自適應分割算法主要針對兩表連接的情況，如將其應用于多表連接上，則需要首先執(zhí)行前兩個表的連接操作，再把連接的結果看作一個新的表，和下一個表進行連接，以此類推，直到完成所有表的連接。顯然這會產生大量的中間結果，造成很大的I/O開銷，是一種效率極低的方法，而在實際應用中，多表連接又是非常常見的操作。

發(fā)明內容

本發(fā)明要解決的技術問題是，針對現(xiàn)有的數(shù)據(jù)分割方法在應用于對多表進行連接時效率低的缺陷，提供一種基于流水線的分布式多表連接方法及系統(tǒng)。

為了解決上述技術問題，本發(fā)明提供了一種基于流水線的分布式多表連接方法，該方法包括并行執(zhí)行的以下步驟：

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

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

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

在根據(jù)本發(fā)明所述的基于流水線的分布式多表連接方法中，所述步驟A包括以下步驟：

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

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

在根據(jù)本發(fā)明所述的基于流水線的分布式多表連接方法中，所述步驟B包括以下步驟：在t_i時刻，其中i＝2,3,…,j；第二規(guī)約處理單元讀取第i組表的數(shù)據(jù)塊B_2i-1至B_2i進行哈希連接后得到第i組表的兩表連接結果H_i。