數據庫：Join算法

Join操作是一種常見的數據庫操作，通過Join可以將多個表關聯起來，根據用戶的條件共同提供數據。一般情況，在數據庫中都會內置多種Join算法，優化器在優化的時候會根據SQL語句和表的統計信息選擇合適的算法。

Hash Join

Hash Join

在執行Hash Join時，1. 會根據Join條件將一張表進行Hash運算加載到內存中的一張Hash表中。Hash表類似與Java中的HashTable；2.遍歷另外一張表，進行Hash運算後在內存中查找滿足條件的記錄。

select * from t1 join t2 on t1.a = t2.b；在執行這個SQL的時候，先加載表t1的數據，然後根據表t1的a字段作為key構造Hash表。之後，從表t2中逐條取出記錄，計算字段b的Hash值，去Hash表中查找是否存在滿足條件的記錄。

Hash Join的性能很高，但是前提條件是內存中能夠存放下其中一張表的Hash表。所以一般適用於大小表Join。在一些大數據分析的數據查詢引擎中，當內存放不下這種Hash表的時候，會將小表進行分區保存到磁盤上，之後再執行Join。

嵌套循環Join

嵌套循環Join

嵌套循環Join中，至少一張表存在索引，且Join的條件是對索引列的比對。帶有索引的表作為被檢索表，對不帶有索引或者兩張都帶有索引的表中較小的那張表進行遍歷。這個算法充分利用了索引的優勢，讓Join的時間複雜度從O(m*n)變成了O(n)，其中m為被檢索表的行數，n為遍歷表的行數。

Merge Hash

相對於上述兩個算法，這個算法的性能差些，但是使用範圍更廣些。在這個算法中，相對兩張表中的數據進行排序，之後再分別取一段進行Join。

Semi Join

半連接，對於左邊的表輸出滿足條件的記錄，而對於右邊的表則不管是否滿足條件都不會被輸出，也就是，最終的結果是左邊表數據記錄的一個子集，類似於in、exists。Semi Join本身就是Join的一種。在大數據跨數據源的查詢中，Semi Join是對inner join、left join、right join的一種優化。查詢跨數據源時，儘量減少從每個數據源出來的數據量是一種很有效的優化方式，畢竟網絡傳輸是要花費時間的。將Join轉化成Semi Join是一種有效減小數據量的方式。

對於：select * from t1 join t2 where t1.a = t2.b，Semi Join的過程如下：

1.將表t1的數據加載到內存；

2.根據t1的數據，改寫加載表t2的條件，即將SQL語句改寫成in、exists等。假設表t1中，全部記錄的a字段只有兩個值：aa和bb，那麼SQL將被改寫為select * from t2 in ('aa','bb');

3.對從表t1和t2加載的數據做Join；

第2步中對加載t2數據的SQL的改寫，使原本需要加載整個t2表改為僅加載t2中滿足條件的數據。