[發明專利]基于FPGA的并行哈希連接加速方法及系統

有效

• 申請號: 202110792999.8
• 申請日: 2021-07-14
• 公開（公告）號: CN113468181B
• 公開（公告）日: 2022-10-11
• 發明（設計）人: 方健;徐實;張擁軍;張光達;王會權;黃安文;溫家輝;張鴻云
• 申請（專利權）人: 中國人民解放軍軍事科學院國防科技創新研究院
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/27;G06F16/23
• 代理公司: 北京奧文知識產權代理事務所(普通合伙) 11534
• 代理人: 張文

本發明公開了一種基于FPGA的并行哈希連接加速方法及系統，包括：在哈希連接的構建階段的每個設定周期，從第一數據表中讀取多個元組數據，利用預劃分函數計算每個元組數據對應的分區號，將每個元組數據引導到對應的分區中，從每個分區中讀取一個元組數據構建哈希表和鏈表；在哈希連接的探測階段的每個設定周期，從第二數據表中讀取多個元組數據，利用預劃分函數計算每個元組數據對應的分區號，將每個元組數據引導到對應的分區中，從每個分區中讀取一個元組數據探測匹配構建階段構建的哈希表和鏈表，其中，哈希連接的構建階段和探測階段均在FPGA內部完成。本發明能夠使得各個分區之間的元組對哈希表的訪問不存在地址沖突，實現并行處理多個元組的能力。

技術領域

本發明涉及數據庫技術領域，尤其涉及一種基于FPGA的并行哈希連接加速方法及系統。

背景技術

連接操作是數據庫中一個常用的操作，其性能常常影響著數據庫系統的整體性能，常見的連接操作包括嵌套循環連接、排序合并連接、以及哈希連接三種。其中，哈希連接被認為是一種高效的連接操作實現方式，但常規的哈希連接雖然只有線性的時間復雜度，但是依然占用較多的CPU計算資源。

為解決常規哈希連接存在的占用較多的CPU計算資源的問題，目前在數據庫系統中引入FPGA(Field Programmable Gate Array)，通過將哈希連接操作以FPGA電路的方式實現，以達到加速的目的。但是，由于在構建和探測哈希表的過程中，同時處理多個元組數據時需要處理多個對哈希表訪問的讀寫請求，若這些訪問需要訪問同一個存儲體，則會造成地址訪問沖突，此時需處理完一個元組之后才能處理另一個元組，導致現有的以FPGA電路的方式實現的哈希連接操作并行度較低，在一個時鐘周期內通常只能處理一個元組，性能較低。

發明內容

為解決上述現有技術中存在的部分或全部技術問題，本發明提供一種基于FPGA的并行哈希連接加速方法及系統。

本發明的技術方案如下：

第一方面，提供了一種基于FPGA的并行哈希連接加速方法，所述方法包括：

在哈希連接的構建階段的每個設定周期，從第一數據表中讀取多個元組數據，利用預設的預劃分函數計算每個元組數據對應的分區號，將每個元組數據引導到分區號對應的分區中，從每個分區中讀取一個元組數據構建哈希表和鏈表，直至處理完第一數據表的所有元組數據；

在哈希連接的探測階段的每個設定周期，從第二數據表中讀取多個元組數據，利用預設的預劃分函數計算每個元組數據對應的分區號，將每個元組數據引導到分區號對應的分區中，從每個分區中讀取一個元組數據探測匹配構建階段構建的哈希表和鏈表，若存在匹配，則進行連接操作并輸出連接結果，直至處理完第二數據表的所有元組數據；

其中，第一數據表和第二數據表為待進行哈希連接的兩個數據表，一個分區號對應一個分區，分區數不小于同時處理的元組數據數，哈希表和鏈表采用分區的形式組織，哈希表包括多個不同的哈希表分區，鏈表包括多個不同的鏈表分區，不同的哈希表分區和不同的鏈表分區存儲在FPGA內部設置的不同的存儲體中，不同的存儲體具有獨立的讀寫端口，哈希連接的構建階段和探測階段均在FPGA內部完成。

在一種可能的實現方式中，預劃分函數采用哈希函數實現，哈希函數用于將元組數據映射到分區對應的分區號。

在一種可能的實現方式中，每個分區設置有分區隊列，根據元組數據對應的分區號，每個元組數據被引導到對應分區的分區隊列中，分區隊列用于對元組數據進行緩存。

在一種可能的實現方式中，從分區中讀取一個元組數據構建哈希表和鏈表，包括：