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

當(dāng)數(shù)據(jù)量大到無(wú)法全部放進(jìn)內(nèi)存時(shí)，前述的指針化方法就不再有效了，因?yàn)樵谕獯鏌o(wú)法保存事先算好的指針。

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

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

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

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

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

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

前兩步與全內(nèi)存時(shí)相同，第4步的指針轉(zhuǎn)換是邊讀入邊進(jìn)行的，而且轉(zhuǎn)換結(jié)果無(wú)法保留復(fù)用，下次再做關(guān)聯(lián)時(shí)還要再計(jì)算HASH和比對(duì)，性能要比全內(nèi)存的方案差。計(jì)算量方面，比HASH分段方案少了一次維表的HASH值計(jì)算，這個(gè)維表如果經(jīng)常被復(fù)用時(shí)會(huì)占些便宜，但因?yàn)榫S表相對(duì)較小，總體優(yōu)勢(shì)并不算大。不過(guò)，這個(gè)算法同樣具有全內(nèi)存算法可以一次解析全部外鍵以及易于并行的特點(diǎn)，在實(shí)際場(chǎng)景下比HASH分段算法仍有較大的性能優(yōu)勢(shì)。

一

在這個(gè)算法基礎(chǔ)上，我們還可以做個(gè)變種：外鍵序號(hào)化。

如果我們能把維表的主鍵都轉(zhuǎn)換成從1開(kāi)始的自然數(shù)，那么我們就可以用序號(hào)直接定位維表記錄，就不需要計(jì)算和比對(duì)HASH值，這樣就可以獲得類似全內(nèi)存下指針化的性能了。

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

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

3. S.switch(productid,P:#)：在流入數(shù)據(jù)時(shí)將S中的productid字段轉(zhuǎn)換成P中相應(yīng)序號(hào)的記錄

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

序號(hào)主鍵的維表不再需要原來(lái)建HASH索引的第2步。

外鍵序號(hào)化本質(zhì)上相當(dāng)于在外存實(shí)現(xiàn)指針化。這種方案需要把事實(shí)表中的外鍵字段轉(zhuǎn)換成序號(hào)，這類似在全內(nèi)存運(yùn)算時(shí)建立指針的過(guò)程，這個(gè)預(yù)計(jì)算也可以得到復(fù)用。需要注意的事，維表發(fā)生重大變化時(shí)，需要同步整理事實(shí)表的外鍵字段，否則可能對(duì)應(yīng)錯(cuò)位。不過(guò)一般維表變化頻度低，而且大多數(shù)動(dòng)作是追加和修改而非刪除，需要重整事實(shí)表的情況并不多。

SQL使用了無(wú)序集合的概念，即使我們事先把外鍵序號(hào)化了，數(shù)據(jù)庫(kù)也無(wú)法利用這個(gè)特點(diǎn)，不能在無(wú)序集合上提供用序號(hào)快速定位的機(jī)制，只能使用索引查找，而且數(shù)據(jù)庫(kù)并不知道外鍵被序號(hào)化了，仍然會(huì)去計(jì)算HASH值和比對(duì)。

二

如果維表也大到內(nèi)存裝不下呢?

我們仔細(xì)分析上面的算法會(huì)發(fā)現(xiàn)，過(guò)程中對(duì)于事實(shí)表的訪問(wèn)是連續(xù)的，但對(duì)于維表的訪問(wèn)是隨機(jī)的。我們以前討論硬盤的性能特征時(shí)談到過(guò)，外存不適合隨機(jī)訪問(wèn)。如果把維表放在外存中再執(zhí)行上面的算法，那性能會(huì)差到遠(yuǎn)不如HASH分段算法的地步，甚至趕不上把兩個(gè)表排序后再做歸并的性能。

這時(shí)候我們要借助集群的力量了。

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

需要注意的是，內(nèi)存不僅適合隨機(jī)訪問(wèn)，還適合小量頻繁訪問(wèn)。而集群維表雖然是內(nèi)存存儲(chǔ)的，但中間多了網(wǎng)絡(luò)傳輸，而網(wǎng)絡(luò)卻不適合小量頻繁訪問(wèn)。這時(shí)，在遍歷事實(shí)表時(shí)就不能象單機(jī)時(shí)那樣每次只處理一條記錄，而需要批量讀取一批記錄，把它們需要JOIN的鍵值聚集起來(lái)再發(fā)送到目標(biāo)集群節(jié)點(diǎn)去獲取維表的相關(guān)字段。

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