找到相同鍵之後,工作還未完
兩個已排序檔案可以一起掃描:若目前鍵不同,較小的鍵不可能與另一檔案中之後的記錄匹配。但鍵相同時,兩個游標各前進一次並不足夠。一邊的鍵出現三次,另一邊出現兩次,便有六對記錄。群組可能大於記憶體,因此只會在記憶體內做笛卡兒(Cartesian)積的做法並不是完整的外部算法。
我們研究一個明確而簡單的算法,其輸出由以下定義確定。
定義 20.2.1
(已排序檔案的多重集等值連接)
設 、 是有限檔案,記錄的鍵取自一個全序集,而該次序與相等關係一致;兩個檔案均依鍵遞增排序。檔案中某一位置上的記錄稱為一次出現;即使記錄內容相同,不同位置仍是不同的出現。不考慮空值鍵,並假設比較精確。 與 的多重集等值連接,是由 的一次出現 與 的一次出現 組成、且兩者鍵相等的全部有序對 ,每對計一次,此外不含其他記錄對;不保證輸出順序。
因此,若鍵 在 中出現 次、在 中出現 次,它恰好貢獻 對;只在一個檔案出現的鍵不貢獻任何記錄對。
儲存模型與算法
設 、 分別佔 、 個輸入區塊。每個 區塊可放 筆記錄,每個 區塊可放 筆;最後輸入區塊可以未滿。順序掃描把每個已佔用區塊恰好讀取一次。每次讀或寫一個區塊算一次傳輸。暫存 群組與 群組的區塊容量分別為 、,輸出區塊可放 對。暫存群組和最終輸出均緊密存放,非空但未滿的最後區塊寫入一次;空檔案不需區塊傳輸。讀取未滿的輸入或暫存區塊時,以有效記錄數識別其內容。
同時預留足夠記憶體,放兩個輸入目前區塊、兩個暫存群組寫入緩衝區、 個暫存 群組區塊、一個暫存 群組讀取區塊及一個輸出緩衝區。各類緩衝區大小可以不同;少量描述資訊及比較工作空間另計。處理匹配群組時保留輸入區塊,包括下一個鍵的首筆預讀記錄;輸出緩衝區跨群組保留。暫存檔是新建的,重讀時沒有快取;此模型不計刪除、定位、比較、配置、故障或延遲的成本。
兩個游標始終指向下一筆未消耗記錄:
- 若其中一個輸入結束,掃完另一輸入而不輸出,然後轉到步驟 4。否則比較目前鍵;若不同,消耗較小鍵的整個群組,再比較。
- 若兩鍵同為 ,把兩邊完整的 群組分別複製至緊密存放的暫存檔 、,保留每次出現;把各邊下一筆記錄留作預讀。各群組最後非空的部分區塊也要寫出。
- 依次讀取每批至多 個 區塊。對每批完整掃描一次 的所有區塊,輸出該批每筆 記錄與每筆 記錄的配對。寫出已滿的輸出區塊,但將未滿緩衝區留給下一群組。處理完畢後刪除兩個暫存檔,再回到步驟 1。
- 兩個輸入都掃完後,如輸出緩衝區非空便寫出。
即使一邊較早結束,掃完另一邊的規則仍令以下成本恰好成立。實作亦可提早停止,但此時基礎掃描成本取決於另一游標已走到哪裏。
定理 20.2.2
(正確性與精確傳輸次數)
對每個共同鍵 ,設兩邊出現次數為 ,並令 、,以及 。算法恰好輸出多重集等值連接,並進行
次傳輸。沒有共同鍵時,求和為零; 時輸出項為零。
證明
(先按鍵劃分,再按批劃分,每次傳輸只計一次)
若目前 鍵較小, 剩餘的鍵都不小於其目前鍵,因此不可能匹配這個較小群組;它也不會匹配已消耗的 群組,因為兩個游標從不跳過可能的匹配,該共同鍵在當時已被處理。交換兩邊亦然,所以跳過較小群組不會遺漏記錄對。鍵相等時,排序保證每個完整群組連續,複製保留每次出現且只保留一次。每筆 記錄恰屬一批,而該批的完整 掃描恰好訪問每筆右邊記錄一次,故每對恰好輸出一次;不同鍵不會配對。重複內容位於不同位置時也一樣。
兩個完整輸入掃描需 次讀取。對鍵 ,寫入暫存群組需 次;讀取全部左邊批次需 次, 批各要讀取 個右邊區塊。輸出緩衝區不會在群組之間提前寫出,因此 對恰需 次寫入。相加得式。這是此指定實作的成本,並非所有連接的下界;其他合併連接也不一定要暫存兩個群組。
證明透視
兩層劃分與三項計數約定
正確性部分依靠兩層劃分。排序把所有匹配記錄對按共同鍵劃分,而且只在一處用到:目前鍵不同時,另一檔案之後的鍵都不小於其目前鍵,所以可以丟棄較小的群組;沒有排序,這一步便沒有根據,會遺漏記錄對。對固定的鍵,分批劃分左邊的出現,每批都與右邊群組的一次完整掃描相遇;因此每對恰在一批、一個右邊區塊中產生。成本部分之所以是精確計數,全靠模型中的三項約定。掃完另一邊的規則令基礎掃描恰為 ,不論哪個檔案先結束。預讀記錄保留在記憶體中,所以群組邊界落在區塊內部時,沒有輸入區塊被讀兩次。未滿的輸出區塊跨群組保留,使各群組上取整之和變為單一的 。去掉任何一項約定,正確性仍然成立,但公式會變成不等式。
第一個例子在一個小檔案上逐項核對公式,其中有一個群組需要兩批。
例題 20.2.3
(群組超出一批的容量)
設 、,輸入區塊為
故 、。鍵 1 的 ,;鍵 2 對應 和 。鍵 4 沒有匹配。記錄對總數 。鍵 1 的暫存寫入需 次,重讀需 次;鍵 2 則分別需 次和 次。七對輸出佔四個區塊。加上五次輸入讀取,總計 次傳輸。鍵 1 雖跨越輸入與暫存區塊邊界,六對仍全部輸出。
概念視角幾何
把每個配對群組看成區塊對的網格
對一個配對的鍵 ,設想一個 網格,其格子 裝著 第 個暫存區塊與 第 個區塊之間的配對; 的每一對恰好落在一格。第 3 步用至多 行的橫條覆蓋網格:每條只讀一次,共 次讀取,而 條中的每一條都掃過全部 列。因此在一個群組內,這個程序就是區塊巢狀迴圈連接,而 正是這種鋪排的成本。上例中鍵 1 給出 網格,被切成兩條。
例題 20.2.4
(邊界情況:沒有共同鍵)
設 ,輸入區塊為
故 、。游標依次比較 (消耗鍵 的群組)、(消耗 )、(消耗 )、(消耗 )及 (消耗 )。此時 已結束,步驟 1 掃完 餘下的記錄 ,完成 的讀取而不輸出任何記錄對。沒有共同鍵,所以匹配群組的求和為空,;步驟 4 發現輸出緩衝區為空,不寫任何區塊。公式給出 ,正是兩次順序掃描的五次區塊讀取。若沒有掃完另一邊的規則,實作可以在讀了 的兩個區塊後停止,計數便取決於數據,而不是 。
例題 20.2.5
(許多小群組:暫存的代價)
設 、、,並且
則 ,鍵 均有 ,故 、。每個鍵需 次暫存寫入和 次暫存讀取,三個群組共 次傳輸。輸出共 對,放得進一個輸出區塊。總計 次。若在記憶體內直接連接這些單筆群組,只需 次輸入讀取和 次輸出寫入。暫存令算法對任何大小的群組都正確,但遇到許多微小群組時,成本會成倍增加。
下面的反例說明,為甚麼步驟 2 要複製完整群組,而不是逐對推進游標。
反例模式
兩個游標同時前進會遺漏配對
令 、。每次匹配後兩游標同時前進,可能只輸出 和 。多重集連接卻有六對,包括 和 。只保留同鍵的一筆記錄亦會丟失重複次數。
如何理解和比較成本
上述公式以已排序並已寫入儲存裝置的檔案為起點。若需要排序,應加上所採用的外部排序實際傳輸量,包括最後寫入,並避免重複計算同一次讀取。若排序器把最後合併結果以串流方式直接送入連接,模型和計數都須修改。同樣地,若輸出串流至下游而非寫入儲存裝置,只有在另計下游成本時才可移除上述輸出寫入項。
每個匹配群組都暫存令做法容易描述,但小群組可能因此浪費傳輸。其他實作可以把群組放在記憶體、交換分批的方向,或利用可倒回的排序輸入;這些選擇會改變記憶體假設和傳輸量。尤其是重複鍵群組可能需要多次掃描,所以排序不保證連接成本為線性;寫出的結果本身也可隨兩邊頻數的乘積增長。區塊計數不能直接證明實際耗時或普遍最優性。
常見錯誤
常見錯誤
(輸出成本按群組逐一上取整再相加)
把輸出成本寫成 ,等於假設每個群組後都寫出輸出緩衝區。上述算法把未滿的輸出區塊留給下一群組,所以成本是單一項 。兩個共同鍵各產生一對而 時,逐組相加得 ,算法實際只寫一個區塊。
常見錯誤
(以群組跨越的輸入區塊數代替緊密存放的大小)
與 計的是緊密存放的暫存檔區塊數,而不是群組碰巧跨越的輸入區塊數。在 的 中,鍵 的兩次出現跨越兩個輸入區塊,卻只填滿 個暫存區塊。用跨越數計算,會高估暫存寫入以及每次重讀。
練習與解答
練習 20.2.6
(設 、、、、,唯一共同鍵滿足 、。求精確傳輸次數。)
核心
解答(3)
- 1
計算緊密存放的群組大小與批數
、、,左邊有 批。
- 2
計算暫存傳輸
暫存寫入需 次;重讀需 次。
- 3
加上基礎掃描與輸出
輸出需 次,輸入掃描需 次,總計 次傳輸。
快速檢查
(兩個共同鍵各產生一對,。為何必須跨群組保留輸出緩衝區,定理才精確?)
比較每組後寫出與不寫出時所寫的輸出區塊數。
解答 · 答案
兩對可共用一個輸出區塊,定理把它計為 次寫入。若每組後都寫出,便會寫兩個未滿區塊,一次輸出寫入的計數不再精確。
快速檢查
(已排序輸入的鍵頻數為 、。求 並指出跳過的群組。)
只有兩個檔案都有的鍵才有貢獻。
解答 · 答案
共同鍵是 和 ,所以 。 的鍵 2 和 的鍵 3 沒有匹配而被跳過。不同位置的相同值仍貢獻不同記錄對。
快速檢查
(某匹配群組的 、、。指定方向需多少次暫存讀取?若交換兩邊,且新外層仍可每批放兩個區塊,又是多少?)
把 中 、 的角色交換。
解答 · 答案
指定方向需 次;交換後需 次。暫存和輸出寫入次數不變。比較依賴記憶體足以支援兩個方向,並不能證明交換後總是更好。