如何讓JSON跑得更快？

JOIN 一直是資料庫效能優化的老大難問題，本來挺快的查詢，一旦涉及了幾個 JOIN，效能就會陡降。而且，參與 JOIN 的表越大越多，效能就越難提上來。

其實，讓 JOIN 跑得快的關鍵是要對 JOIN 分類，分類之後，就能利用各種型別 JOIN 的特徵來做效能優化了。

JOIN 分類

有 SQL 開發經驗的同學都知道，絕大多數 JOIN 都是等值 JOIN，也就是關聯條件為等式的 JOIN。非等值 JOIN 要少見得多，而且多數情況也可以轉換成等值 JOIN 來處理，所以我們可以只討論等值 JOIN。

等值 JOIN 主要又可以分為兩大類：外來鍵關聯和主鍵關聯。

外來鍵關聯是指用一個表的非主鍵欄位，去關聯另一個表的主鍵，前者稱為事實表，後者為維表。比如下圖中，訂單表是事實表，客戶表、產品表、僱員表是維表。

外來鍵表是多對一關係，而且是不對稱的，事實表和維表的位置不能互換。需要說明的是，這裡說的主鍵是指邏輯上的主鍵，也就是在表中取值唯一、可以用於唯一確定某條記錄的欄位（或欄位組），不一定在資料庫表上建立過主鍵。

主鍵關聯是指用一個表的主鍵關聯另一個表的主鍵或部分主鍵。比如下圖中客戶和 VIP 客戶、訂單表和訂單明細表的關聯。

客戶和 VIP 客戶按照主鍵關聯，這兩個表互為同維表。訂單則是用主鍵去關聯明細的部分主鍵，我們稱訂單表是主表，明細表是子表。

同維表是一對一關係。且同維表之間是對稱的，兩個表的地位相同。主子表則是一對多關係，而且是不對稱的，有明確的方向。

仔細觀察會發現，這兩類 JOIN 都涉及到主鍵了。而不涉及主鍵的 JOIN 會導致多對多關係，大多數情況都沒有業務意義。換句話說，上述這兩大類 JOIN 涵蓋了幾乎全部有業務意義的 JOIN。如果我們能利用 JOIN 總會涉及主鍵這個特徵做效能優化，能解決掉這兩大類 JOIN，其實也就意味著解決了大部分 JOIN 效能問題。

但是，SQL 對 JOIN 的定義並不涉及主鍵，只是兩個表做笛卡爾積後再按某種條件過濾。這個定義很簡單也很寬泛，幾乎可以描述一切。但是，如果嚴格按這個定義去實現 JOIN，也就沒辦法在效能優化時利用主鍵的特徵了。

SPL 改變了 JOIN 的定義，專門針對這兩大類 JOIN 分別處理，利用了主鍵的特徵減少運算量，從而實現效能優化的目標。

下面我們來看看 SPL 具體是怎麼做的。

外來鍵關聯

如果事實表和維表都不太大，可以全部裝入記憶體，SPL 提供了外來鍵地址化方法：先把事實表中的外來鍵欄位值轉換為對應維表記錄的地址，之後引用維表字段時，就可以用地址直接取出了。

以前面的訂單表、僱員表為例，假定這兩個表已經被讀入記憶體。外來鍵地址化的工作機制是這樣的：對於訂單表某記錄 r 的 eid 欄位，到僱員表中找到這個 eid 欄位值對應的記錄，得到其記憶體地址 a，再將 r 的 eid 欄位值替換成 a。對訂單表的所有記錄都做好這樣的轉換，就完成了外來鍵地址化。這時候，訂單表記錄 r 要引用僱員表字段時，直接用 eid 欄位儲存的地址 a 取出僱員表記錄和欄位就可以了，相當於常數時間內就能取得僱員表的欄位，不需要再到僱員表做查詢。

可以在系統啟動時把事實表和維表讀入記憶體，並一次性做好外來鍵地址化，即預關聯。這樣，在後續關聯計算時就能直接用事實表外來鍵欄位中的地址去取維表記錄，完成高效能的 JOIN 計算。

外來鍵地址化和預關聯的詳細原理請參考：【效能優化】6.1 [外來鍵關聯] 外來鍵地址化

SQL 通常使用 HASH 演算法來做記憶體連線，需要計算 HASH 值和比對，效能會比直接用地址讀取差很多。

SPL 之所以能實現外來鍵地址化，是利用了維表的關聯欄位是主鍵這一特徵。上面例子中，關聯欄位 eid 是僱員表的主鍵，具有唯一性。訂單表中的每個 eid 只會唯一對應一條僱員記錄，所以才能把每個 eid 轉換成它唯一對應的那條僱員記錄的地址。

而 SQL 對 JOIN 的定義中沒有主鍵的約定，就不能認定與事實表中外來鍵關聯的維表記錄有唯一性，有可能發生與多條記錄關聯的情況。對於訂單表的記錄來講，eid 值沒有辦法唯一對應一條僱員記錄，就無法做到外來鍵地址化了。而且 SQL 也沒有記錄地址這種資料型別，結果會導致每次關聯時還是要計算 HASH 值並比對。

只是兩個表 JOIN 時，外來鍵地址化和 HASH 關聯的差別還不是非常明顯。這是因為 JOIN 並不是最終目的，JOIN 之後還會有其它很多運算，JOIN 本身運算消耗時間的佔比相對不大。但事實表常常會有多個維表，甚至維表還會有很多層。比如訂單關聯產品，產品關聯供應商，供應商關聯城市，城市關聯國家等等。在關聯表很多時，外來鍵地址化的效能優勢會更明顯。

下面的測試，在關聯表個數不同的情況下對比 SPL 與 Oracle 的效能差異，可以看出在表很多時，外來鍵地址化的優勢相當明顯：

測試的詳細情況請參考：效能優化技巧：預關聯。

對於只有維表能裝入記憶體，而事實表很大需要外存的情況，SPL 提供了外來鍵序號化方法：預先將事實表中的外來鍵欄位值轉換為維表對應記錄的序號。關聯計算時，分批讀入新事實表記錄，再用序號取出對應維表記錄。

以上述訂單表、產品表為例，假定產品表已經裝入記憶體，訂單表儲存在外存中。外來鍵序號化的過程是這樣：先讀入一批訂單資料，設其中某記錄 r 中的 pid 對應的是記憶體中產品表的第 i 條記錄。我們要將 r 中的 pid 欄位值轉換為 i。對這批訂單記錄都完成這樣的轉換後，再做關聯計算時，從外存中分批讀入訂單資料。對於其中的記錄 r，就可以直接根據 pid 值，去記憶體中的產品表裡用位置取出相應的記錄，也避免了查詢動作。

外來鍵序號化原理更詳細的介紹參考：【效能優化】6.3 [外來鍵關聯] 外來鍵序號化。

資料庫通常會把小表讀入記憶體，再分批讀入大表資料，用雜湊演算法做記憶體連線，需要計算雜湊值和比對。而 SPL 使用序號定位是直接讀取，不需要進行任何比對，效能優勢比較明顯。雖然預先把事實表的外來鍵欄位轉換成序號需要一定成本，但這個預計算只需要做一次，而且可以在多次外來鍵關聯中得到複用。

SPL 外來鍵序號化同樣利用了維表關聯欄位是主鍵的特徵。如前所述，SQL 對 JOIN 的定義沒有主鍵的約定，無法利用這一特徵做到外來鍵序號化。另外，SQL 使用無序集合的概念，即使我們事先把外來鍵序號化了，資料庫也無法利用這個特點，不能在無序集合上使用序號快速定位的機制，最快也就是用索引查詢。而且，資料庫並不知道外來鍵被序號化了，仍然會去計算 HASH 值和比對。

下面這個測試，在不同並行數情況下，對比 SPL 和 Oracle 完成大事實表、小維表關聯計算的速度，SPL 跑的比 Oracle 快 3 到 8 倍。測試結果見下圖：

這個測試更詳細的資訊請參考：效能優化技巧：外來鍵序號化。

如果維表很大也需要外存，而事實表較小能裝入記憶體，SPL 則提供了大維表查詢機制。如果維表和事實表都很大，SPL 則使用單邊分堆演算法。對於維表過濾後再關聯的情況，SPL 提供了索引複用方法及對位序列等方法。

資料量大到需要分散式計算時，如果維表較小，SPL 採用複寫維表機制，將維表在叢集節點上覆制多份；如果維表很大，則採用叢集維表方法以保證隨機訪問。這兩種方法都可以有效的避免 Shuffle 動作。相比而言，SQL 體系下不能區分出維表，HASH 拆分方法要將兩個表都做 Shuffle 動作，網路傳輸量要大得多。

主鍵關聯

主鍵關聯涉及的表一般都比較大，需要儲存在外存中。SPL 為此提供了有序歸併方法：預先將外存表按照主鍵有序儲存，關聯時順序取出資料做歸併計算。

以客戶和 VIP 客戶兩個表做內連線為例，假設已經預先將兩個表按照主鍵 cid 有序儲存在外存中。關聯時，從兩個表的遊標中讀取記錄，逐條比較 cid 值。如果 cid 相等，則將兩表的記錄合併成結果遊標的一條記錄返回。如果不相等，則 cid 小的那個遊標再讀取記錄，繼續判斷。重複這些動作直到任何一個表的資料被取完，返回的遊標就是 JOIN 的結果。

對於兩個大表關聯，資料庫通常使用雜湊分堆演算法，複雜度是乘法級的。而有序歸併演算法複雜度是加法級，效能會好很多。而且，資料庫做大資料的外存運算時，雜湊分堆會產生快取檔案的讀寫動作。有序歸併演算法則只需要對兩個表依次遍歷，不必藉助外存快取，可以大幅降低 IO 量，有巨大的效能優勢。

預先按照主鍵排序的成本雖高，但是一次性做好即可，以後就總能使用歸併演算法實現 JOIN，效能可以提高很多。同時，SPL 也提供了在有追加資料時仍然保持資料整體有序的方案。

這類 JOIN 的特徵在於關聯欄位是主鍵或部分主鍵，有序歸併演算法正是根據這個特徵來設計的。因為不管是同維表還是主子表，關聯欄位都不會是主鍵之外的其他欄位，所以我們將關聯表按照主鍵有序這一種方式排序儲存就可以了，不會出現冗餘。而外來鍵關聯就不具備這個特徵，不能使用有序歸併。具體來說，是因為事實表的關聯欄位不是主鍵，會存在多個要參與關聯的外來鍵欄位，我們不可能讓同一個事實表同時按多個欄位都有序。

SQL 對 JOIN 的定義不區分 JOIN 型別，不假定某些 JOIN 總是針對主鍵的，就沒辦法從演算法層面上利用主鍵關聯的特徵。而且，前面說過 SQL 基於無序集合概念，資料庫不會刻意保證資料的物理有序性，很難實施有序歸併演算法。

有序歸併演算法的優勢還在於易於分段並行。以訂單和訂單明細按 oid 關聯為例，假如將兩表都按照記錄數大致平均分為 4 段，訂單第 2 段的 oid 有可能會出現在明細第 3 段，類似的錯位會導致錯誤的計算結果。SPL 再次利用主鍵 oid 的有序性，提供同步分段機制，解決了這個問題：先將有序的訂單表分為 4 段，再找到每一段起止記錄的 oid 值形成 4 個區間，將明細表也分成同步的 4 段。這樣，在平行計算時兩表對應分段就不會出現錯位了。由於明細表也對 oid 有序，可以迅速地按照起止 oid 定位，不會降低有序歸併的效能。

有序歸併和同步分段並行的原理，詳見：SPL 有序歸併關聯。

傳統的 HASH 分堆技術實現並行就比較困難了，多執行緒做 HASH 分堆時需要同時向某個分堆寫出資料，造成共享資源衝突；而下一步實現某組分堆關聯時又會消費大量記憶體，無法實施較大的並行數量。

實際測試證明，在相同情況下，我們對兩個大表做主鍵關聯測試（詳情參見效能優化技巧：有序歸併），結果是 SPL 比 Oracle 快了近 3 倍：

除了有序歸併，SPL 還提供了很多高效能演算法，全面提高主鍵關聯 JOIN 的計算速度。包括：附表機制，可以將多表一體化儲存，減少儲存資料量的同時，還相當於預先完成了關聯，不需要再比對了；關聯定位演算法，實現先過濾再關聯，可以避免全表遍歷，獲得更好的效能等等。

當資料量繼續增加，需要多臺伺服器叢集時，SPL 提供復組表機制，將需要關聯的大表按照主鍵分佈到叢集節點上。相同主鍵的資料在同一節點，避免分機之間的資料傳輸，也不會出現 Shuffle 動作。

回顧與總結

回顧上面兩大類、各場景 JOIN，採用 SPL 分情況提供的高效能演算法，可以利用不同型別 JOIN 的特徵提速，讓 JOIN 跑得更快。SQL 對上述這麼多種 JOIN 場景籠統的處理，就沒辦法針對不同 JOIN 的特徵來實施這些高效能演算法。比如：事實表和維表都裝入記憶體時，SQL 只能按照鍵值計算 HASH 和比對，無法利用地址直接對應；SQL 資料表無序，在大表按照主鍵關聯時無法做到有序歸併，只能使用 HASH 分堆，有可能會出現多次快取的現象，效能有一定的不可控性。

平行計算方面，SQL 單表計算時還容易做到分段並行，多表關聯運算時一般就只能事先做好固定分段，很難做到同步動態分段，這就難以根據機器的負載臨時決定並行數量。

對於叢集運算也是這樣，SQL 在理論上不區分維表和事實表，要實現大表 JOIN 就會不可避免地產生佔用大量網路資源的 HASH Shuffle 動作，在叢集節點數太多時，網路傳輸造成的延遲會超過節點多帶來的好處。

SPL 設計並應用了新的運算和儲存模型，可以在原理和實現上解決 SQL 的這些問題。對於 JOIN 的不同分類和場景，程式設計師有針對性的採取上述高效能演算法，就能獲得更快的計算速度，讓 JOIN 跑得更快。

SPL資料

• SPL官網
• SPL下載
• SPL原始碼