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

無效

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

技術領域

本發明屬于數據庫技術領域，涉及的是一種哈希連接算法，算法思想是使用歸并連接來實現優美哈希連接。

背景技術

哈希連接是在數據庫數據處理應用中，對多表數據進行連接處理的一種常用方法。如果數據量較大的表進行連接，連接條件中的列無序或沒有索引、且連接為等值連接時，哈希連接是最佳策略。

哈希連接算法主要有簡單哈希連接方法(Simple?hash?join)、優美哈希連接方法(GRACE?hash?join)和混合哈希連接算法(Hybrid?hash?join)。

簡單哈希連接算法在左邊數據量較大、內存不能將左邊數據全部緩存時，只能分批對其建立哈希，這樣右邊的數據需要多次讀取，次數為左邊數據需要建立的哈希的次數。故導致I/O讀取次數較多，花費非常大。優美哈希連接在處理左邊數據時，是選擇一個哈希函數(hash函數)，把左邊和右邊數據同時劃分到不同的子分區中，且左邊與右邊數據的分區個數一致，然后分別對左邊與右邊數據對應的子分區進行連接。一般情況下，由于避免了多次掃描右邊數據，優美哈希連接的性能優于簡單哈希連接。但是在建立左邊與右邊數據的相應子分區時，花費的時間代價也相對較大。混合哈希連接算法是簡單哈希連接和優美哈希連接算法的結合，在處理數據時，類似優美哈希連接把數據分成N個子分區，只是在分成子分區過程中，借鑒了簡單哈希連接思想，對第一個子分區建立哈希時，把這部分數據全部存放在內存中，然后再對其他各對應的子分區進行簡單哈希連接處理，這樣當大多數數據在第一子分區時，就減少了這部分數據的I/O讀取次數。

綜上所述，傳統算法仍有較大缺點。簡單哈希連接算法在處理大數據量時，右邊數據需要掃描多次，I/O讀取代價太高；優美哈希連接算法在建立子分區過程時，時間代價較大，如果某分區中的數據量依然較大，還需要對該分區中的數據繼續進行哈希處理，使得該分區可以劃分為更小的分區，如果進行多次哈希之后，分區依然較大，則只能終止哈希處理，采用其他方法進行處理，如嵌套循環連接；混合哈希連接算法雖然結合了前兩者優點，但效率仍然與優美哈希連接相當，并沒有較大提高，只有當數據能大部分存在放內存中時，效率才有較大提高。

發明內容

本發明的目的在于提供一種計算效率高、適用于大數據量的哈希連接方法。雖然本發明主要目的是解決大數據量情況下哈希算法效率低的問題，但對小數據的情況也同樣適用。

本發明提供的哈希連接方法，是把哈希連接轉化為歸并連接(Merge?join)進行處理，而不是使用常見的優美哈希連接算法。具體步驟如下：

(1)對左邊輸入數據(左表數據)根據其鍵值(KEY?VALUE)進行哈希求值，按照得到的哈希值把數據插入到哈希表中，如有沖突，哈希值相同的數據則按照鍵值進行排序插入。當內存中不能容納所有數據即哈希表滿時，需要把所有數據刷入磁盤。刷入的方法是根據哈希表的哈希值即槽號大小順序地把每個槽號里的所有數據與該槽號(nth_cell)一起組成新的數據有序地刷入磁盤，每一次刷入的所有數據都當作一個分片。然后把原始數據的鍵值(key1、key2、…、keyn)與槽號一起組成新的鍵值(key0(即nth_cell)、key1、key2、…、keyn)。當下一批數據再來時，進行同樣形式的處理，并刷入另一個分片。依次類推，直至對左邊數據處理完畢；這樣每個分片數據都是有序的，然后根據新的鍵值對左邊所有分片數據進行排序。

本步驟中，為了使發明具有更好的效果，在進行臨時存儲數據時，對原始數據進行了改造，每條記錄都增加了一列，哈希值(nth_cell)列，即槽號，然后再刷入磁盤。哈希表中的所有數據刷入磁盤的過程，是掃描整個哈希表，把0號槽到最后一個槽中的數據依次全部刷入到磁盤，這樣就可以確保刷入的所有數據的有序性，這是由于經過哈希處理后的數據在每個槽中已經是有序的，增加哈希值后，將此哈希值作為一新鍵值，新的數據根據新生成的鍵值(key0、key1、…、keyn)是有序的，與其他排序方法相比，就省去了對數據的排序操作。

(2)對右表數據也進行類似于上述左表數據的處理。

(3)從左、右邊兩邊分別取出各自分片數據中最小的一組分組數據，根據新生成的鍵值進行大小比較。