雜湊表放不進記憶體時
記憶體內的雜湊連接先為左表建立雜湊表,再用右表逐筆查找。若左表太大,整張表就放不進記憶體。分割法把問題拆小:將兩個檔案中相同鍵的記錄送往同一個編號的分割區;第二趟再逐對連接分割區。這常稱為 Grace 雜湊連接。其優點取決於分割區是否真的放得下;熱門鍵或不均勻分佈都可能使某區過大。
我們研究有限的內等值連接,採用多重集語義;鍵不為空值,且比較精確。
定義 20.3.1
(多重集等值連接與分割函數)
檔案中每個位置都是一個不同的記錄實例,即使兩筆記錄看起來完全相同。 與 的多重集內等值連接,對每個鍵相等的左記錄實例 與右記錄實例 恰好含一對有序對 ,此外沒有其他配對;輸出無須排序。分割函數是把鍵映到 ()的映射 ,在整次執行中固定不變;因此相同鍵必有相同雜湊值,而不同鍵可以碰撞。
概念視角代數
把連接大小看成內積
以 、 表示鍵 在 、 中的實例數。多重集等值連接是對所有鍵 ,把鍵為 的 對作不相交聯集,所以 正是兩個重數向量的內積。分割函數把鍵集分成各類 ,這個和式也隨之分成每個分割一項;這就是對應分割可以各自獨立連接的原因。在下面第一個例題中,。
兩趟算法與記憶體條件
設檔案 分別佔 個區塊。讀取或寫入一個區塊均算一次傳輸。分割時使用一個輸入緩衝區及 個輸出緩衝區;每筆記錄送往其分割區,最後把每個非空的未滿緩衝區寫出。各分割檔分別緊密儲存、保留全部記錄實例,並寫往新的儲存空間。設兩側第 個分割檔各佔 個區塊,令 、。由於各分割檔須各自寫出最後的未滿區塊, 可以大於 , 也可以大於 ;空分割區不佔區塊。
第二趟將每個 的全部記錄實例讀入記憶體雜湊表,然後讀取 一次。每次查找都將實際鍵與相應表桶中的所有候選記錄比較,並對每個相等的左記錄實例輸出一對。表可用第二個雜湊函數組織;它同樣必須把相同鍵送往同一表桶,而表內碰撞必須以鍵的相等比較處理。所有分割區共用一個輸出緩衝區,只在滿載或最後結束時寫出。
每個 的表連同索引開銷都必須放進 個記憶體區塊,另留一區讀取 、一區輸出。因此本模型的預算至少是 區塊;小型控制描述數據不計。此處沒有假設分割檔仍在快取,也不計壓縮、索引存取或跨趟沿用輸入緩衝區。
定理 20.3.2
(多重集語義下的正確性)
在上述條件下,若兩個檔案使用同一分割函數,算法的輸出恰為多重集等值連接:每對鍵相等的記錄實例恰好輸出一次,此外沒有其他配對。
證明
(每對鍵相等的配對恰好相遇一次)
每個輸入記錄實例恰好送進一個分割區,並被保留。對任意鍵相等的 ,由固定函數及相同鍵有相同值,兩者均進入同一個區 。建立表時 被讀入一次;查找時 被讀取一次,並檢查相應表桶的所有候選。實際鍵比較接受 ,故這一對被輸出一次。每個記錄實例只有一個分割區,每個查找記錄實例只處理一次,因此不會在別處再輸出同一對。反過來,輸出前必須通過實際鍵比較,所以不同鍵的碰撞不會產生錯誤配對。此論證逐一計算記錄實例,而非只計不同值。
這個證明用了兩種不同機制,各自處理對方無法處理的失誤。
證明透視
兩種檢查各有用途
分割函數決定哪些記錄可以相遇;實際鍵的相等比較決定哪次相遇會產生輸出。完整性只用前者:由於兩個檔案使用同一個固定的 ,相同鍵必落在同一分割區,所以沒有相配的一對會被分開。可靠性只用後者:雜湊可能碰撞,同在一區或一桶只算候選,鍵比較會剔除跨鍵配對。恰好輸出一次則依賴第三個較隱蔽的事實:每個記錄實例只送往一個分割區,每個查找記錄實例只讀一次。正因如此,論證計算的是記錄實例而非不同鍵,重複項會相乘而非合併。
命題 20.3.3
(區塊傳輸次數)
若每張建立表都放得下,輸出共有 對,每個輸出區塊可放 對,則算法的傳輸次數恰為
當 時最後一項為零。此數包括寫出輸出及所指定分割檔的傳輸,不包括計算、尋道、故障或刪除儲存數據的成本。
證明
(把互不重疊的傳輸階段相加)
原始檔掃描需 次讀取;寫入分割檔需 次,再讀取建立表及查找需同樣次數,包括全部非空分割區。緊密打包的輸出需 次寫入。把這些互不重疊的傳輸相加便得到公式。表能放入記憶體是必要條件:若某區放不下,所述第二趟便不能照此執行,公式也不是該情況下的成本。
例題 20.3.4
(重複、碰撞及未滿區塊)
設輸入及分割區塊各可放兩筆記錄,,且
按奇偶分割。左側奇數檔為 、偶數檔為 ,分別需 區塊;右側奇數檔為 、偶數檔為 ,分別需 區塊。所以 、、。假設兩張左表都放得下,鍵 1 產生兩對、鍵 2 產生兩對、鍵 4 產生一對;鍵 3 沒有配對。偶數區中的不同鍵 2 與 4 雖同區,相等比較仍會拒絕跨鍵配對。因此 ,傳輸次數為 。 中兩個 2 不可合併成一個。
常見錯誤
(把同區當作配對)
上例的偶數區中,鍵 與 同在一區,也可能同在一個表桶。若輸出桶內所有候選,便會加入跨鍵配對 與 ,共 對錯誤配對( 有一個 和一個 ; 有兩個 和一個 )。分割區及表桶的碰撞只產生候選;令輸出正確的是最後的鍵相等檢查。
常見錯誤
(合併重複的記錄實例)
在多重集語義下, 中的兩個 是不同的記錄實例。若在連接前把 去重,或在建立側每個不同鍵只保留一個表項,上例便得 而非 。若需要的是集合語義,那是另一種輸出契約,必須明確說明。
計數公式在沒有任何配對時同樣適用;這個邊界情況顯示哪些項仍然保留。
例題 20.3.5
(帶空分割區的空連接)
沿用同樣的區塊大小及奇偶分割,取 、,故 。左側奇數檔以一個區塊存放 ,左側偶數檔為空;右側奇數檔為空,右側偶數檔以一個區塊存放 。所以 。奇數區建立表但沒有查找;偶數區建立空表,仍讀取其一個 區塊,找不到配對。因此 ,不寫出輸出區塊,傳輸次數為 。
記憶體預算必須同時照顧兩趟,由較大的需求決定。
例題 20.3.6
(核查記憶體預算)
設有 個分割緩衝區,且最大建立表需 區塊。分割趟需 區塊,查找趟需 區塊,故預算至少為 區塊。若只有 區塊,分割趟仍可執行,但最大分割區無法以所述第二趟連接;必須先再分割或改用其他方法,上述計數才適用。數字 也不說明另一份輸入的情況,其最大表必須另行檢查。
反例模式
平均分割區小,不代表每區都放得下
聲稱:若平均分割區放得下,每區都放得下。假設 有 100 個同鍵記錄實例,而表只能容納 20 個。分成十區時平均每區十個,但相同鍵必須送往同一區,所以這一區仍有 100 個。只改變鍵雜湊函數,不能在保留上述簡單算法的前提下拆開這一組。同樣,整體區塊數看似平均,也不足以保證最大一區連索引開銷都能放入記憶體。修正後的假設就是條件中的那一條:最大的建立表放得下。
條件失效時怎辦
若一區過大,可以用另一函數再次分割,但必須對兩側使用同一函數。若過大是由許多不同鍵造成,這可能有幫助;若全是同一個重複鍵,只依鍵分割就不能拆開它。另一做法是對該區使用區塊巢狀迴圈,或明確拆分熱門鍵並複製或重掃另一側的配對數據。這些都是不同算法,有額外傳輸及記憶體條件。宣稱兩趟成本前要先偵測溢出,並把失敗嘗試及後續處理一併計入實際成本。
輸出龐大是另一個問題。若一個鍵在左、右各出現 次,它就產生 對。需要實體化結果時,分割函數無法消除輸出這些配對的工作。分割也不保證輸出順序;若下游要求排序,須另做處理。輸入記錄、暫存分割及輸出配對的大小可以不同,因此應計算實際區塊數,不應直接假設 。
練習與解答
快速檢查
(鍵 在左側出現三次、右側出現四次,輸出多少對?)
數出記錄實例的有序對。
解答 · 答案
每個左記錄實例都與每個右記錄實例配對,共 對。外觀相同的記錄仍是不同記錄實例。
快速檢查
(設 、、、、、,且所有左表均放得下。按所述程序計算傳輸次數。)
把輸入掃描、分割寫入與讀取,以及打包輸出相加。
解答 · 答案
原始讀取需 次,分割寫入及讀取需 次,打包輸出需 次,合共 次。
快速檢查
(設 、。若 按奇數鍵 、偶數鍵 分割, 卻按相反規則分割,第二趟輸出甚麼?哪個假設失效?)
找出每個 的記錄實例落在哪一區。
解答 · 答案
左側的 送往分割區 ,右側的 送往分割區 ,兩者從不在對應分割區中相遇,所以輸出為空,但正確的連接有一對。正確性定理要求兩個檔案使用同一分割函數;兩個函數各自固定,但兩檔之間的相同鍵已不再相遇。