第 34 期：JOIN 提速 – 外來鍵指標的衍生
我們繼續討論外來鍵 JOIN，並延用上一篇的例子。
當資料量大到無法全部放進記憶體時，前述的指標化方法就不再有效了，因為在外存無法儲存事先算好的指標。
一般來講，外來鍵指向的維表容量較小，而不斷增長的事實表要大得多。如果記憶體還能把維表放下的話，我們可以採用臨時指向的方法來處理外來鍵。
- P=file(“products.txt”).import() 讀入商品資訊表 P
- P.index(id) 為 P 的主鍵 id 建立索引方便查詢
- S=file(“sales.txt”).cursor() 建立商品銷售記錄的遊標 S，逐步讀入資料
- S.switch(productid,P:id) 在流入資料時將 S 中的 productid 欄位根據 P 的主鍵轉換成 P 的記錄
- S.sum(quantity*productid.price) 計算銷售額
前兩步與全記憶體時相同，第 4 步的指標轉換是邊讀入邊進行的，而且轉換結果無法保留複用，下次再做關聯時還要再計算 HASH 和比對，效能要比全記憶體的方案差。計算量方面，比 HASH 分段方案少了一次維表的 HASH 值計算，這個維表如果經常被複用時會佔些便宜，但因為維表相對較小，總體優勢並不算大。不過，這個演算法同樣具有全記憶體演算法可以一次解析全部外來鍵以及易於並行的特點，在實際場景下比 HASH 分段演算法仍有較大的效能優勢。
在這個演算法基礎上，我們還可以做個變種：外來鍵序號化。
如果我們能把維表的主鍵都轉換成從 1 開始的自然數，那麼我們就可以用序號直接定位維表記錄，就不需要計算和比對 HASH 值，這樣就可以獲得類似全記憶體下指標化的效能了。
- P=file(“products.txt”).import() 讀入商品資訊表 P，其主鍵 id 都是序號
- S=file(“sales.txt”).cursor() 建立商品銷售記錄的遊標 S，逐步讀入資料
- S.switch(productid,P:#) 在流入資料時將 S 中的 productid 欄位轉換成 P 中相應序號的記錄
- S.sum(quantity*productid.price) 計算銷售額
序號主鍵的維表不再需要原來建 HASH 索引的第 2 步。
外來鍵序號化本質上相當於在外存實現指標化。這種方案需要把事實表中的外來鍵欄位轉換成序號，這類似在全記憶體運算時建立指標的過程，這個預計算也可以得到複用。需要注意的事，維表發生重大變化時，需要同步整理事實表的外來鍵欄位，否則可能對應錯位。不過一般維表變化頻度低，而且大多數動作是追加和修改而非刪除，需要重整事實表的情況並不多。
SQL 使用了無序集合的概念，即使我們事先把外來鍵序號化了，資料庫也無法利用這個特點，不能在無序集合上提供用序號快速定位的機制，只能使用索引查詢，而且資料庫並不知道外來鍵被序號化了，仍然會去計算 HASH 值和比對。
如果維表也大到記憶體裝不下呢？
我們仔細分析上面的演算法會發現，過程中對於事實表的訪問是連續的，但對於維表的訪問是隨機的。我們以前討論硬碟的效能特徵時談到過，外存不適合隨機訪問。如果把維表放在外存中再執行上面的演算法，那效能會差到遠不如 HASH 分段演算法的地步，甚至趕不上把兩個表排序後再做歸併的效能。
這時候我們要藉助叢集的力量了。
一臺機器的記憶體裝不下，可以多搞幾臺機器來裝下，把維表分段放在多臺機器上形成叢集維表，然後就可以繼續使用上面的演算法並獲得一次解析多個外來鍵和易於並行的好處。同樣地，叢集維表 h 也可以使用序號化的技術。
需要注意的是，記憶體不僅適合隨機訪問，還適合小量頻繁訪問。而叢集維表雖然是記憶體儲存的，但中間多了網路傳輸，而網路卻不適合小量頻繁訪問。這時，在遍歷事實表時就不能象單機時那樣每次只處理一條記錄，而需要批量讀取一批記錄，把它們需要 JOIN 的鍵值聚集起來再發送到目標叢集節點去獲取維表的相關欄位。
保證維表的記憶體化是提高效能的關鍵因素。對於現代計算機的記憶體容量而言，大部分維表在單臺機器的記憶體都可以放下，少量巨大維表則採用叢集維表來處理，這樣可以確保對維表的高效能隨機訪問。如果真地出現連叢集也裝不下的維表，那可能還是隻能回到低效的 HASH 分段演算法了。
作者：279400248
連結：ofollow,noindex" target="_blank">http://c.raqsoft.com.cn/article/1533880519883
來源：乾學院
著作權歸作者所有。商業轉載請聯絡作者獲得授權，非商業轉載請註明出處。