[發明專利]基于哈希連接的探測方法、裝置、設備及存儲介質

在審

• 申請號: 202110077395.5
• 申請日: 2021-01-20
• 公開（公告）號: CN112765174A
• 公開（公告）日: 2021-05-07
• 發明（設計）人: 朱仲穎;扈天陽
• 申請（專利權）人: 上海達夢數據庫有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/242;G06F16/25
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 孟金喆

本申請公開了一種基于哈希連接的探測方法、裝置、設備及存儲介質，具體包括創建第一表格的哈希表，哈希表包括哈希槽；確定第一表格中各參考列數據在哈希表中對應的哈希槽；根據各參考列數據的哈希槽是否沖突選擇相應的存儲方式依次將各參考列數據所屬的整行數據存儲至對應的哈希槽，并根據存儲結果設置各哈希槽的沖突標記；根據沖突標記和第二表格中的數據進行哈希探測，第二表格與第一表格哈希連接。在本方案中，根據哈希槽沖突與否選擇不同的存儲方式存儲數據，并基于沖突標記進行哈希探測，可以解決現有技術中哈希連接存在的問題，提高哈希連接的性能。

技術領域

本申請實施例涉及關系型數據庫領域，尤其涉及一種基于哈希連接的探測方法、裝置、設備及存儲介質。

背景技術

連接操作是數據庫中的基本操作，用于從兩個關系的笛卡爾積中選取屬性之間滿足一定條件的元組，現有的連接技術有很多，比如，嵌套循環連接算法、基于歸并排序的連接算法、基于哈希的連接算法、基于索引的連接算法等，不同的算法在不同應用場景下有不同的性能。當兩個表做連接查詢，且有等值連接條件時，哈希連接是實現兩個表連接的一種高效的實現方式。例如，通過SELECT*FROM T1,T2 WHERE T1.C1＝T2.D2；語句查詢哈希連接，可以選用數據較少的表作為左表，比如，T1作為左表，有C1和C2兩個列，T2作為右表，有D1和D2兩個列。T1表的數據如下：

表1

基于T1構造哈希表，采用T2表進行探測，輸出滿足條件(T1.C1＝T2.D2)的結果。其中，構造哈希表的過程如下：

1、根據配置參數創建一張固定大小的哈希表；

2、使用數據庫內部函數(比如bfd_int64、bfd_dec、bfd_time等)將T1.C1的實際值value計算得到哈希鍵值key；

3、通過哈希函數計算鍵值key在哈希表中的位置，并在該位置插入對應的實際值value；

4、循環執行步驟2、3，直至處理完T1表中的數據。

但是，若多個哈希鍵值映射到哈希表中相同的位置，則會成為哈希沖突，具體包括以下三種情況：

第一種，相同的原始值。即計算得到相同的哈希鍵值key，通過哈希函數映射到哈希表同一個位置；第二種，不同的原始值。通過多個值組合、字符串等類型計算得到相同的哈希鍵值key，通過哈希函數映射到哈希表的同一個位置；第三種，原始值和哈希鍵值key均不同。當原始值個數超過哈希表大小，有些不同的哈希鍵值會映射到哈希表同一個位置，或者哈希算法也會決定哈希沖突的概率。

基于上述哈希沖突的原因，哈希探測時需要比較原始數據，該過程如下：

(1)獲取哈希連接中右表連接的原始數據(例如T2.D2)，計算哈希鍵值并通過哈希函數定位到哈希表的具體位置(即哈希槽)；

(2)將連接列的原始數據(如T2.D2)和哈希槽上的數據進行一一比較，如果相等，說明該行數據符合要求，并輸出查詢項的數據(例如，以上述查詢語句為例，設T2此時的數據為(1,4)，匹配到T1(1,2)，那么輸出查詢結果為(1,2,1,4))。

(3)重復上述步驟(1)、(2)，直至右表中的數據處理完畢。

可以看出，上述哈希探測過程中存在以下問題：1、右表數據需要與定位到的哈希槽上每條數據進行比較；2、相同的數據存在重復比較；3、哈希表不存在沖突，并且右表數據為左表數據的子集時，工業應用上通常仍然需要一一比較原始數據。

發明內容

為了解決上述至少一個技術問題，本申請實施例提供了以下方案。

第一方面，本申請實施例提供了一種基于哈希連接的探測方法，該方法包括：