優化Join運算的系列方法（1）

JOIN是關系數據庫中常用運算，用于把多個表進行關聯，關聯條件一般是判斷某個關聯字段的值是否相等。隨著關聯表的增多或者關聯條件越來越復雜，無論理解查詢含義、實現查詢語句，還是在查詢的性能方面，可以說JOIN都是最具挑戰的SQL運算，沒有之一。

特別是JOIN的性能，一直是個老大難問題。下面我們將基于數據計算中間件（DCM）——集算器，來提供一些提升運算性能的方法。

當然，我們不是介紹如何在寫SQL語句時怎么寫JOIN，也就是我們假設已經對查詢需求有了正確的理解并且能正確地實現SQL。這種情況下，要提升性能，就必須從最基本的提升數據IO配合算法及并行等手段做起。正因如此，如果數據仍然存儲在數據庫中，那也沒什么好辦法提速，因為數據庫的IO效率很低，又幾乎無法并行，即使把運算寫得再精巧也無濟于事。所以，要提高性能，一定要把數據搬出數據庫，我們下面的討論都是基于這個思路，而集算器正是實現這個思路的利器，甚至神器！

把數據表搬出數據庫存儲到集算器的集文件中很簡單，只要用兩行代碼：

這兩行代碼把數據庫里訂單表的數據導出到集文件Order.btx。

因為數據庫IO性能不佳，而且數據量也可能很大，所以這個“搬家”動作可能時間也不短，但還好是一次性的。后面我們的計算都將從集文件中取數。

1 判斷 JOIN 的類型

在將數據搬出數據庫后，我們需要首先判斷JOIN的類型，然后才能采取有針對性的優化措施。

JOIN運算大家都很熟悉，按照SQL的語法定義劃分，包括INNER JOIN(內連接)、LEFT JOIN(左連接)、RIGHT JOIN（右連接）、FULL JOIN（全連接）幾個類型，這是根據在運算中對空值的處理規則進行劃分的。而我們的分析和優化，則會從更貼近需求的語義角度出發，根據各個表的主鍵參與關聯的情況進行劃分，總體來說有這么三種：外鍵表、同維表、主子表。

外鍵表

當表A的某些字段與表B的主鍵關聯，B稱為A的外鍵表，A表中與B表主鍵關聯的字段稱為A指向B的外鍵。此時A表也稱為事實表，B表也稱為維表。

這是一個典型的例子，訂單表的客戶編號與客戶表的主鍵客戶編號進行關聯，此時A指向B是多對一的關系，即A表有可能存在多條記錄指向B表的同一條記錄。

這種情況，我們可以把外鍵字段（例子中的“CustomerID”）的值理解成指向外鍵表中對應記錄的“指針”，而外鍵表中對應的記錄就可以理解成一個對象，而外鍵表的字段就可以理解為對象的屬性， “指針”的作用只是用于找到外鍵表中對應那條記錄。例子中對表A和表B做關聯，一定是想獲得某些訂單的客戶的姓名或所在區域等詳細信息，這樣，如果能寫成customerID.name和customerID.area就會更容易理解，這種語法在集算器中也得到了完美的支持。

同時，表A還可以有多個外鍵表，例如表A的銷售編號（SellerID）可以指向一個銷售人員信息表C，從而獲得該訂單銷售人員的屬性信息。

同維表

表A的主鍵與表B的主鍵關聯，A和B相互稱為同維表。同維表是一對一的關系，JOIN、LEFT JOIN和FULL JOIN的情況都會有，例如：員工表和經理表。

這兩個表的主鍵都是員工編號ID，也就是經理也是員工之一，不過因為經理比普通員工多了一些屬性，所以需要另用一個經理表來保存。對于這種一對一的情況，邏輯上可以簡單地看成一個表來對待。同維表JOIN時兩個表都是按主鍵關聯，相應記錄是唯一對應的。

主子表

表A的主鍵與表B的部分主鍵關聯，A稱為主表，B稱為子表。主子表是一對多的關系，只有JOIN和LEFT JOIN，不會有FULL JOIN，如：訂單和訂單明細。

表A的主鍵是ID，表B的主鍵是ID和NO，表A里的一條記錄會對應表B里的多條記錄。此時，可以把訂單明細表里的相關記錄看成是訂單表的一條記錄的屬性，該屬性的取值是一個集合，而且常常需要使用聚合運算把集合值計算成單值。例如查詢每個訂單的總金額，可以描述為：

        SELECT ID, SUM(OrderDetail.Price) FROM Order

顯然，主子表關系是不對等的，而且從兩個方向的引用都有意義。從主表引用子表的情況就是通過聚合運算得到一個單值，而從子表引用主表則和外鍵表類似。

那么，這樣劃分三種JOIN運算，外鍵表、同維表、主子表，有什么用處呢？當然是為了優化性能！對于需要優化的JOIN運算，在準確判斷是哪種類型基礎上，后面的優化才會更加有效。另外，有必要說明一下，這里提到的表A和表B不要求必須是一個實體表，也可能是一個子查詢產生的“邏輯表”。

下面我們就開始針對這三種類型以及實際的業務情況進行分析和提速。

2 全內存時的外鍵表

如果所有參與運算的數據都能裝入內存，那么就可以使用“外鍵指針化”技術來實現外鍵式JOIN運算的優化。

2.1 單個外鍵

以上面的訂單表和客戶表為例，要查詢每一筆訂單的客戶名稱和所在地區：

我們需要查詢所有訂單的訂單編號、用戶名、用戶級別和下單時間， SQL是這么寫的：

SELECT 訂單編號,用戶名,VIP級別,下單時間 FROM 訂單表,用戶信息表 WHERE 訂單表.用戶編號 = 用戶信息表.用戶編號

用集算器實現則是這樣：

A1，從集文件中查詢用戶數據；

A2，設置用戶信息表的鍵為用戶編號；

A3，以用戶編碼字段建立索引；

A4，從集文件中查詢訂單數據；

A5，關聯，在A4訂單表的用戶編碼字段上建立指向用戶信息表記錄的指針；

A6，外鍵指針化之后，將外鍵表字段作為用戶名、用戶級別屬性使用。

實際有效運算的也就是A5和A6這兩格，別的都是數據準備。

再來看一個例子，這次需要計算各個VIP級別用戶的訂單的總數，SQL是這么寫的：

SELECT VIP級別,count(訂單編號) 訂單數 FROM 訂單表,用戶信息表 WHERE 訂單表.用戶編號 = 用戶信息表.用戶編號 GROUP BY VIP級別

使用集算器則是這樣的：

這個計算跟上一個例子的處理步驟大部分都一樣，只是在上一個例子的計算后接著再執行一下A7，對關聯的結果進行匯總，能這么做是因為外鍵的指針關聯在上一次計算里已經完成，這里可以對A5的結果進行復用。實際使用中這兩個計算放在一個DFX文件里執行，所以整個過程只需要進行一次關聯。

這也是集算器的另一大特點，可以對中間計算結果進行復用，從而提高整體查詢性能。復用的次數越多，性能的優化就越明顯。這一點在SQL中就做不到，兩個查詢要執行兩次SQL語句，每次執行都要做一次關聯，整體性能自然就差了。

此外，還可能存在多字段外鍵的情況，事實表的多個字段關聯到一個維表，這種情況略有些復雜，在以后的篇章中再做詳細介紹。

2.2 一層多個外鍵

下面再看一個多外鍵的例子，假設數據庫中有訂單表、用戶信息表、賣家信息表三個表：

我們需要按照用戶級別和賣家信用等級來匯總訂單數量，SQL是這么寫的：

SELECT VIP級別 用戶級別, 信用等級 賣家等級,count(訂單編號) 訂單數

FROM 訂單表,用戶信息表,賣家信息表

WHERE 訂單表.用戶編號 = 用戶信息表.用戶編號 AND 訂單表.賣家編號 = 賣家信息表.賣家編號

GROUP BY VIP級別, 信用等級

使用集算器則是這樣：

A1，中查詢訂單數據；

A2，中查詢用戶數據；

A3，中查詢賣家數據；

A4，一次性關聯用戶信息表、賣家信息表這兩個維表；

A5，對關聯的結果進行匯總。

2.3 多層外鍵

外鍵表還可能會有多層的情況，下面這個例子中，假設數據庫中有訂單明細表、商品信息表、類別信息表三個表：

我們要查詢按照商品的大類名稱匯總的售出商品數量，SQL是這么寫的：

SELECT 大類名稱, SUM (商品編號) 商品數

FROM 訂單明細表,商品信息表,類別信息表

WHERE 訂單明細表.商品編號 = 商品信息表.商品編號 AND 商品信息表.類別編號 = 類別信息表.類別編號

GROUP BY 大類名稱

使用集算器則是這樣：

A1，查詢訂單明細數據；

A2，查詢商品信息數據；

A3，查詢類別信息數據；

A4，通過switch函數在A2建立指向類別信息記錄的指針，實現關聯；

A5，通過switch函數在A1建立指向商品信息記錄的指針，實現關聯，這樣就得到了一個三層關聯；

A6，對關聯的結果進行匯總。

用外鍵指針化的辦法解決JOIN，對事實表遍歷一次就可以解析所有外鍵。而數據庫的HASH JOIN算法每執行一次（意味著遍歷一次數據）只能解析掉一個JOIN。

同時，如果全部使用內存，這個指針一旦建立后就可以復用，如果我們還要針對這個關聯情況再次計算 ，就不需要再去建立關聯了。而數據庫SQL則不行，還要再做HASH JOIN，即便是基于SQL體系的內存數據庫，在這方面也做不快。

2.4 并行計算

外鍵指針化之后，還可以通過并行方式進一步優化性能。對已經裝入內存的事實表，我們可以對它進行分段訪問，從而以并行計算的方式明顯地提升計算的性能。

還是用上面多外鍵的情形為例，仍然是按照用戶級別和賣家信用等級匯總訂單數量，我們來看看如何用集算器實現并行訪問事實表：

這段代碼和前面的基本一樣，只是對訂單表這個事實表的訪問方式有所不同。A2使用@m選項把訂單表數據分為了4段，得到一個多路游標，后面的計算都是基于這個多路游標進行的。groups函數內部會自動判斷，如果A2是多路游標那么就會自動進行計算。這里分為4段游標，是假定CPU的個數是4個，實際使用中可以根據CPU的數量來決定分幾段。

并行在單任務時有很明顯的效果，主要是因為充分利用了CPU資源，如果并發較多時沒有太多空閑的CPU可用，那么意義就不大了。