我們繼續討論外鍵JOIN，并延用上一篇的例子。

當數據量大到無法全部放進內存時，前述的指針化方法就不再有效了，因為在外存無法保存事先算好的指針。

一般來講，外鍵指向的維表容量較小，而不斷增長的事實表要大得多。如果內存還能把維表放下的話，我們可以采用臨時指向的方法來處理外鍵。

1. P=file("products.txt").import()：讀入商品信息表P

2. P.index(id)：為P的主鍵id建立索引方便查找

3. S=file("sales.txt").cursor()：建立商品銷售記錄的游標S，逐步讀入數據

4. S.switch(productid,P:id)：在流入數據時將S中的productid字段根據P的主鍵轉換成P的記錄

5. S.sum(quantity*productid.price)：計算銷售額

前兩步與全內存時相同，第4步的指針轉換是邊讀入邊進行的，而且轉換結果無法保留復用，下次再做關聯時還要再計算HASH和比對，性能要比全內存的方案差。計算量方面，比HASH分段方案少了一次維表的HASH值計算，這個維表如果經常被復用時會占些便宜，但因為維表相對較小，總體優勢并不算大。不過，這個算法同樣具有全內存算法可以一次解析全部外鍵以及易于并行的特點，在實際場景下比HASH分段算法仍有較大的性能優勢。

一

在這個算法基礎上，我們還可以做個變種：外鍵序號化。

如果我們能把維表的主鍵都轉換成從1開始的自然數，那么我們就可以用序號直接定位維表記錄，就不需要計算和比對HASH值，這樣就可以獲得類似全內存下指針化的性能了。

1. P=file("products.txt").import()：讀入商品信息表P，其主鍵id都是序號

2. S=file("sales.txt").cursor()：建立商品銷售記錄的游標S，逐步讀入數據

3. S.switch(productid,P:#)：在流入數據時將S中的productid字段轉換成P中相應序號的記錄

4. S.sum(quantity*productid.price)：計算銷售額

序號主鍵的維表不再需要原來建HASH索引的第2步。

外鍵序號化本質上相當于在外存實現指針化。這種方案需要把事實表中的外鍵字段轉換成序號，這類似在全內存運算時建立指針的過程，這個預計算也可以得到復用。需要注意的事，維表發生重大變化時，需要同步整理事實表的外鍵字段，否則可能對應錯位。不過一般維表變化頻度低，而且大多數動作是追加和修改而非刪除，需要重整事實表的情況并不多。

SQL使用了無序集合的概念，即使我們事先把外鍵序號化了，數據庫也無法利用這個特點，不能在無序集合上提供用序號快速定位的機制，只能使用索引查找，而且數據庫并不知道外鍵被序號化了，仍然會去計算HASH值和比對。

二

如果維表也大到內存裝不下呢?

我們仔細分析上面的算法會發現，過程中對于事實表的訪問是連續的，但對于維表的訪問是隨機的。我們以前討論硬盤的性能特征時談到過，外存不適合隨機訪問。如果把維表放在外存中再執行上面的算法，那性能會差到遠不如HASH分段算法的地步，甚至趕不上把兩個表排序后再做歸并的性能。

這時候我們要借助集群的力量了。

一臺機器的內存裝不下，可以多搞幾臺機器來裝下，把維表分段放在多臺機器上形成集群維表，然后就可以繼續使用上面的算法并獲得一次解析多個外鍵和易于并行的好處。同樣地，集群維表h 也可以使用序號化的技術。

需要注意的是，內存不僅適合隨機訪問，還適合小量頻繁訪問。而集群維表雖然是內存存儲的，但中間多了網絡傳輸，而網絡卻不適合小量頻繁訪問。這時，在遍歷事實表時就不能象單機時那樣每次只處理一條記錄，而需要批量讀取一批記錄，把它們需要JOIN的鍵值聚集起來再發送到目標集群節點去獲取維表的相關字段。

保證維表的內存化是提高性能的關鍵因素。對于現代計算機的內存容量而言，大部分維表在單臺機器的內存都可以放下，少量巨大維表則采用集群維表來處理，這樣可以確保對維表的高性能隨機訪問。如果真地出現連集群也裝不下的維表，那可能還是只能回到低效的HASH分段算法了。