[發明專利]使用并行處理執行哈希連接

有效

• 申請號: 201880047106.3
• 申請日: 2018-07-16
• 公開（公告）號: CN111095193B
• 公開（公告）日: 2022-03-25
• 發明（設計）人: E·P·哈丁;A·D·賴利;C·H·金斯利;S·威斯納
• 申請（專利權）人: 奧特瑞克斯股份有限公司
• 主分類號: G06F7/00
• 分類號: G06F7/00;G06F12/02;G06F16/22
• 代理公司: 永新專利商標代理有限公司 72002
• 代理人: 張立達

本發明公開了使用計算機連接數據記錄。對第一多個數據記錄和第二多個數據記錄中的數據記錄進行哈希處理。基于哈希，將第一多個數據記錄和第二多個數據記錄分別分配給第一分組和第二分組。來自第一分組和第二分組的關聯的分組對被提供給在計算機處理器上執行的線程，并且不同的對被提供給不同的線程。線程對分組對并行操作，以確定是否要連接分組中的記錄。如果與數據記錄關聯的哈希匹配，則線程將考慮中的兩個數據記錄連接在一起。輸出經連接的數據記錄。

技術領域

本說明書一般地涉及數據處理技術，并且更具體地，涉及以針對并行處理計算機系統(例如，多核處理器)優化的方式執行哈希連接。

背景技術

數據分析平臺(例如，大數據分析)的發展已經將數據處理擴展為用于處理大量數據以提取具有商業價值的信息的工具。為此，需要高效的數據處理技術來訪問、處理、和分析來自不同數據源的大的數據集。例如，一家小型企業可以利用第三方數據分析環境，該環境采用專用的計算和人力資源來收集、處理、和分析來自各種來源(例如，外部數據提供者、內部數據源(例如，本地計算機上的文件)、大數據存儲單元、和基于云的數據(例如，社交媒體信息)。以提取有用的定量和定性信息的方式處理如在數據分析中使用的大數據集通常需要在強大的計算機設備上實現的復雜軟件工具。

連接(join)算法是當處理例如上述那些的多個數據集時采用的數據處理技術。現有的數據處理系統可以利用多個連接算法(每個連接算法具有相應的性能折衷)來執行兩個集合的數據之間的邏輯連接(例如，哈希連接、嵌套循環、排序歸并連接)。例如，哈希連接的預期復雜度為O(M+N)，其中，N和M是被連接的兩個表的元組數。然而，哈希連接算法可能具有不利的存儲器存取模式(例如，隨機磁盤存取)，并且執行起來也可能很慢。因此，當處理連接算法時，現有的數據處理系統遭受性能問題。

發明內容

通過用于連接數據記錄的方法、計算機、和非暫時性計算機可讀存儲器解決了以上問題和其他問題。使用計算機來連接數據記錄的方法的實施例包括：識別第一多個數據記錄和第二多個數據記錄；以及為第一多個數據記錄和第二多個數據記錄中的每個數據記錄計算哈希。該方法還包括基于所計算的哈希，將第一多個數據記錄中的數據記錄分配給來自第一集合的分組的分組，并且基于所計算的哈希，將第二多個數據記錄中的數據記錄分配給來自第二集合的分組的分組。其中，第二集合的分組中的每個分組與第一集合的分組中的相應分組相關聯。該方法還包括：基于哈希值，確定是否要將來自第一集合的分組的分組中的相應數據記錄與來自第二集合的分組的相關聯的分組中的相應數據記錄進行連接，以及響應于確定要將來自第一集合的分組的分組中的相應數據記錄與來自第二集合的分組的相關聯的分組中的相應數據記錄進行連接，連接相應數據記錄。該方法還包括輸出經連接的數據記錄。

用于連接數據記錄的計算機的實施例包括至少一個計算機處理器和存儲計算機程序指令的非暫時性計算機可讀存儲器，該計算機程序指令可由處理器執行以執行操作。所述操作包括：識別第一多個數據記錄和第二多個數據記錄；以及為第一多個數據記錄和第二多個數據記錄中的每個數據記錄計算哈希。該操作還包括基于所計算的哈希，將第一多個數據記錄中的數據記錄分配給來自第一集合的分組的分組，并且基于所計算的哈希，將第二多個數據記錄中的數據記錄分配給來自第二集合的分組的分組。其中，第二集合的分組中的每個分組與第一集合的分組中的相應分組相關聯。該操作還包括：基于哈希值，確定是否要將來自第一集合的分組的分組中的相應數據記錄與來自第二集合的分組的相關聯的分組中的相應數據記錄進行連接，以及響應于確定要將來自第一集合的分組的分組中的相應數據記錄與來自第二集合的分組的相關聯的分組中的相應數據記錄進行連接，連接相應數據記錄。該操作還包括輸出經連接的數據記錄。