[發明專利]一種使用歸并連接實現優美哈希連接的方法

無效

• 申請號: 201110375112.1
• 申請日: 2011-11-22
• 公開（公告）號: CN102508924A
• 公開（公告）日: 2012-06-20
• 發明（設計）人: 汪龍重;宋鑫;陳福榮
• 申請（專利權）人: 上海達夢數據庫有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海東創專利代理事務所(普通合伙) 31245
• 代理人: 曹立維

1.一種使用歸并連接來實現優美哈希連接的方法，其特征在于：

(1)首先對左表數據根據其鍵值進行哈希求值，按照哈希值把數據插入到哈希表中，如有沖突，把相同哈希值的數據按照鍵值大小進行排序插入；如果內存中不能容納所有數據，即哈希表滿，需要把哈希表中的數據全部刷入磁盤；刷入的方法是根據哈希表的哈希值即槽號從小到大進行刷入；把哈希表的每個槽中的所有數據與該槽號(nth_cell)一起組成新的元組，有序地刷入磁盤，每一次刷入的數據作為一個數據分片；然后把原始數據的鍵值：key1、key2、…、keyn與槽號一起組成新的鍵值：nth_cell、key1、key2、…、keyn；依次對下一批數據進行同樣形式的處理，并記為下一個分片；直至對左表數據處理完畢；此時，每個分片中的數據都井然有序，然后再根據新的鍵值對左邊所有分片中的數據進行排序；

(2)對右表數據進行與左表數據同樣的處理；

(3)從左邊、右邊所有分片數據中取出最小的一組分組數據，并根據新生成的鍵值對這兩組數據進行大小比較；

(4)如果左邊數據小于右邊數據，則根據哈希連接類型，判斷是否需要輸出左邊數據；如果是，則輸出左邊數據，對輸出數據的右邊部分用空值填充；否則不輸出；然后繼續取出左邊下一組的分組數據；如果左邊數據大于右邊數據，根據哈希連接類型，判斷是否需要輸出右邊數據，如果需要，則輸出右邊數據，對輸出數據的左邊部分用空值填充；否則不輸出；然后繼續取出右邊下一組的分組數據；如果左邊數據等于右邊數據，則對兩邊數據進行笛卡爾積計算，并輸出計算結果；然后同時取出左邊與右邊的下一組數據；

(5)反復執行步驟(4)，直到左邊或右邊數據處理完畢；

(6)如果左邊數據處理完畢，則根據哈希連接類型，判斷是否需要輸出左邊數據，如果需要，則輸出剩下的左邊數據，并置輸出數據的右邊部分為空值；

如果右邊數據處理完畢，則根據哈希連接類型，判斷是否需要輸出右邊數據，如果需要，則輸出剩下的右邊數據，并置輸出數據的左邊部分為空值；

(7)左邊與右邊數據都處理完畢，則哈希連接處理完畢。