[發明專利]哈希連接方法、計算節點、存儲介質及程序產品

在審

• 申請號: 202210825987.5
• 申請日: 2022-07-13
• 公開（公告）號: CN115062027A
• 公開（公告）日: 2022-09-16
• 發明（設計）人: 吳宇昊;李飛飛;魏闖先
• 申請（專利權）人: 阿里云計算有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2455
• 代理公司: 北京同鈞律師事務所 16037
• 代理人: 柴海平;許懷遠

本申請提供一種哈希連接方法、計算節點、存儲介質及程序產品，該哈希連接方法包括：基于第一哈希函數，對第一數據表進行哈希運算，得到哈希表；基于所述哈希表，生成布隆過濾器；根據所述布隆過濾器對第二數據表進行過濾；對所述哈希表以及過濾后的第二數據表進行哈希連接，得到并輸出哈希連接表。實現了在哈希連接之前，通過動態生成的布隆過濾器對數據表進行過濾，從而減少了數據表的數據量，進而減少了所需傳輸以及探測的數據量，提高了哈希連接的效率，降低了哈希連接的成本。

技術領域

本申請涉及數據庫技術領域，尤其涉及一種哈希連接方法、計算節點、存儲介質及程序產品。

背景技術

哈希連接(hash join)，是在數據庫中建立多張表之間的關系的常用操作。哈希連接對一個表構建哈希表，掃描另一個表的元組與該哈希表進行比對，從而探測處兩者之間的連接。

對于分布式數據庫，尤其是大規模分布式數據庫，如數據倉庫，由于數據被重分布至多個節點中，在進行哈希連接時，需要通過網絡傳輸各節點存儲的數據表中的元組，以當元組與哈希表中對應元組滿足等值連接條件時，將它們來進行連接并輸出。哈希連接的網絡開銷會隨集群規模增加而成倍增加，導致哈希連接效率低下，無法滿足需求。

發明內容

本申請提供一種哈希連接方法、計算節點、存儲介質及程序產品，基于動態布隆過濾器對數據表中的元組進行過濾，從而減少需傳輸和探測的數據量，提高了哈希連接的效率。

第一方面，本申請提供一種哈希連接方法，包括：

基于第一哈希函數，對第一數據表進行哈希運算，得到哈希表；基于所述哈希表，生成布隆過濾器；根據所述布隆過濾器對第二數據表進行過濾；對所述哈希表以及過濾后的第二數據表，進行哈希連接，得到并輸出哈希連接表。

可選的，基于所述哈希表，生成布隆過濾器，包括：

根據計算節點對應的哈希表，生成所述計算節點對應的子布隆過濾器；獲取各個其他計算節點對應的子布隆過濾器；根據各個所述計算節點對應的子布隆過濾器，生成所述布隆過濾器。

可選的，基于所述哈希表，生成布隆過濾器，包括：

根據計算節點對應的哈希表，生成所述計算節點對應的子布隆過濾器；獲取各個其他計算節點對應的子布隆過濾器的置位信息；根據所述置位信息以及所述計算節點對應的子布隆過濾器，生成所述布隆過濾器；其中，置位信息用于描述對應的子布隆過濾器被置位的比特位。

可選的，在根據所述計算節點對應的哈希表，生成所述計算節點對應的子布隆過濾器之后，所述方法還包括：

分別計算以第一傳輸方式和第二傳輸方式傳輸子布隆過濾器所需的數據量；根據傳輸所需的數據量，從第一傳輸方式和第二傳輸方式中確定所述子布隆過濾器的目標傳輸方式；基于所述目標傳輸方式，廣播所述計算節點對應的子布隆過濾器至其他計算節點；其中，基于第一傳輸方式廣播所述計算節點對應的子布隆過濾器，包括：廣播所述計算節點對應的子布隆過濾器至其他計算節點；基于第二傳輸方式廣播所述計算節點對應的子布隆過濾器，包括：廣播所述計算節點對應的子布隆過濾器的置位信息至其他計算節點；其中，置位信息用于描述對應的子布隆過濾器被置位的位置。

可選的，根據所述哈希表，生成所述計算節點對應的子布隆過濾器，包括：

獲取至少一個第二哈希函數；根據至少一個第二哈希函數，計算所述第一數據表中各元組的第二哈希值；根據第一哈希值以及所述第二哈希值，構建所述計算節點對應的子布隆過濾器；其中，所述第一哈希值為所述哈希表中的哈希值。

可選的，所述方法還包括：

根據所述第一數據表，確定哈希代價；根據所述哈希代價以及所述連接代價，確定所述計算節點對應的子布隆過濾器的哈希函數的個數，以根據所述哈希函數的個數，獲取對應數量的第二哈希函數。