我們?cè)賮?lái)看重新定義JOIN后如何能夠提高運(yùn)算性能，先看外鍵式JOIN的情況。

設(shè)有兩個(gè)表：

其中sales表中的productid是指向products表中id字段的外鍵，id是products表的主鍵。

現(xiàn)在我們想計(jì)算銷售額有多少(為簡(jiǎn)化討論，就不再設(shè)定條件了)，用SQL寫出來(lái)：

SELECT SUM(sales.quantity*products.price) FROM sales JOIN products ON sales.productid=products.id 

基于笛卡爾積定義的JOIN，原則上只能兩層循環(huán)全遍歷來(lái)計(jì)算，不過(guò)這個(gè)計(jì)算量實(shí)在太大，關(guān)系數(shù)據(jù)庫(kù)一般采用HASH分段方法優(yōu)化，即分別計(jì)算兩表關(guān)聯(lián)字段的HASH值，將HASH同值記錄拼到一起再做小范圍遍歷。網(wǎng)上有很多文章介紹這個(gè)算法，這里就不詳述了。這樣做后的復(fù)雜度能顯著降低，但仍然要做多次HASH值計(jì)算和比對(duì)。

一

我們?cè)儆们笆龅暮?jiǎn)化的JOIN語(yǔ)法寫出這個(gè)運(yùn)算：

SELECT SUM(quantity*productid.price) FROM sales 

而這個(gè)寫法其實(shí)也就預(yù)示了它還可以有更好的優(yōu)化方案，下面來(lái)看看怎樣實(shí)現(xiàn)。

二

我們先考慮全內(nèi)存的情況，如果所有數(shù)據(jù)都能夠裝入內(nèi)存，我們可以實(shí)現(xiàn)外鍵指針化。

將事實(shí)表sales中的外鍵字段productid，轉(zhuǎn)換成指向維表products記錄的指針，即productid的取值就已經(jīng)是某個(gè)products表中的記錄，那么就可以直接引用記錄的字段進(jìn)行計(jì)算了。

用SQL不方便描述這個(gè)運(yùn)算的細(xì)節(jié)過(guò)程了，我們采用過(guò)程式語(yǔ)法、并用文件作為數(shù)據(jù)源來(lái)說(shuō)明計(jì)算過(guò)程：

1. P=file("products.txt").import()

讀入商品信息表P

2. P.index(id)

為P的主鍵id建立索引方便查找

3. S=file("sales.txt").import()

讀入商品銷售記錄S

4. S.switch(productid,P:id)

將S中的productid字段根據(jù)P的主鍵轉(zhuǎn)換成P的記錄

5. S.sum(quantity*productid.price)

計(jì)算銷售額。productid字段取值已經(jīng)轉(zhuǎn)換為對(duì)象，可以直接引用其price字段

上面算法中，第2步建主鍵索引一般也是用HASH辦法，對(duì)id計(jì)算HASH值，第4步轉(zhuǎn)換指針還是計(jì)算productid的HASH值與P的HASH索引表對(duì)比。這樣的話，如果只做一次關(guān)聯(lián)運(yùn)算，指針化的方案和傳統(tǒng)HASH分段方案的計(jì)算量基本上一樣，沒有根本優(yōu)勢(shì)。

但不同的是，如果數(shù)據(jù)能在內(nèi)存中放下，這個(gè)指針一旦建立起來(lái)之后可以復(fù)用，也就是說(shuō)第2和第4步只要做一次，下次再做關(guān)于這兩個(gè)字段的關(guān)聯(lián)運(yùn)算時(shí)就不必再計(jì)算HASH值和比對(duì)了，性能就能大幅提高。而關(guān)系代數(shù)體系下沒有對(duì)象指針這個(gè)概念，并且基于笛卡爾積定義的JOIN運(yùn)算也無(wú)法假定外鍵指向記錄的***性，沒辦法使用外鍵指針化的方法，每次關(guān)聯(lián)時(shí)都要計(jì)算HASH值并比對(duì)。

而且，如果事實(shí)表中有多個(gè)外鍵分別指向多個(gè)維表，傳統(tǒng)的HASH分段JOIN方案每次只能解析掉一個(gè)，有N個(gè)JOIN要執(zhí)行N遍動(dòng)作，每次關(guān)聯(lián)后都需要保持中間結(jié)果供下一輪使用，計(jì)算過(guò)程復(fù)雜得多，數(shù)據(jù)也會(huì)被遍歷多次。而外鍵指針化方案在面對(duì)多個(gè)外鍵時(shí)，只要對(duì)事實(shí)表遍歷一次， 沒有中間結(jié)果，計(jì)算過(guò)程要清晰很多。

還有一點(diǎn)，內(nèi)存本來(lái)應(yīng)當(dāng)是很適合并行計(jì)算的，但HASH分段JOIN算法卻不容易并行。即使把數(shù)據(jù)分段并行計(jì)算HASH值，但要把相同HASH值的記錄歸聚到一起供下一輪比對(duì)，就會(huì)發(fā)生共享資源沖突的事情，這會(huì)把并行計(jì)算的優(yōu)勢(shì)完全抵消掉。而外鍵式JOIN模型下，關(guān)聯(lián)兩表的地位不對(duì)等，明確區(qū)分出維表和事實(shí)表后，只要簡(jiǎn)單地將事實(shí)表分段就可以并行計(jì)算。

將HASH分段技術(shù)參照外鍵屬性方案進(jìn)行改造后，也能一定程度地改善多外鍵一次解析和并行能力，有些數(shù)據(jù)庫(kù)能在工程層面上實(shí)施這種優(yōu)化。不過(guò)，這種優(yōu)化在只有兩個(gè)表JOIN時(shí)問(wèn)題不大，在有很多表及各種JOIN混在一起時(shí)，數(shù)據(jù)庫(kù)并不容易識(shí)別出應(yīng)當(dāng)把哪個(gè)表當(dāng)作事實(shí)表去并行遍歷、而把其它表當(dāng)作維表建立HASH索引，這時(shí)優(yōu)化并不總是有效的。所以我們經(jīng)常會(huì)發(fā)現(xiàn)當(dāng)JOIN的表變多時(shí)性能會(huì)急劇下降的現(xiàn)象(常常到四五個(gè)表時(shí)就會(huì)發(fā)生，結(jié)果集并無(wú)顯著增大)。而從JOIN模型上引入外鍵概念后，將這種JOIN專門處理時(shí)，就總能分清事實(shí)表和維表，更多的JOIN表只會(huì)導(dǎo)致性能的線性下降。

內(nèi)存數(shù)據(jù)庫(kù)是當(dāng)前比較火熱的技術(shù)，但上述分析表明，采用SQL模型的內(nèi)存數(shù)據(jù)庫(kù)在JOIN運(yùn)算上是很難快起來(lái)的!