本周我們進入join的處理環節，其實在一開始學“連接”這個概念的時候，我感覺最暈菜的事兒是個類Join的區別。。left join?、right join?、outer join、inner join?、cross join?。看起來好暈。

依照慣例，我主要還是希望從原理的角度來介紹一下join的主要處理方式，這篇只會講單機處理方式，多機模式我們會在之后的分布式章節進行介紹。

?

先是場景

TableA(col1)

0

1

2

3

?

?

TableB(col1)

1

2

3

4

?

?

?

OK，讓我們從最常見的inner join開始吧~

Inner join是我們日常最常見的join類型，也是默認的join類型，當我們輸入TableA a join TableB b on a.col1=b.col1，我們會獲得這樣的一個結果：

Inner join result
TableA(col1)	TableB(col1)
1	1
2	2
3	3

可以看到，inner join是一種最容易理解的join類型，也就是“尋找那些在TableA和TableB中符合col1 = col2的數據”

在這基礎之上，我們再來看left outer join?和right outer join。

當我們需要left outer join的時候，我們會使用?TableA a left outer join TableB b on a.col1 = b.col1，我們會獲得如下結果：

Left outer join result
TableA(col1)	TableB(col1)
0	NULL
1	1
2	2
3	3

可以看到，最明顯的變化就是，TableA（左表）中的所有數據都被保留了，而如果這行數據在TableB(右表)中沒有找到對應，這就是left outer join的含義。

同理，Right outer join?自然可以進行知識遷移：保留在TableB(右表)中的所有數據，如果這些數據在左表中沒能找到匹配數據，則用NULL填充。

?

right join result
TableA(col1)	TableB(col1)
1	1
2	2
3	3
NULL	4

?

而full outer join呢？其實就是保留TableA和TableB中的所有數據，并盡可能找到對應表中的匹配行進行對應，如果沒能找到對應的行，則用NULL代替。

Full join result
TableA(col1)	TableB(col1)
0	NULL
1	1
2	2
3	3
NULL	4

?

最后還有一種join的方式，叫cross join .也叫笛卡爾積，一般來說會比較容易和full outer join混淆，但其實不是一個東西。笛卡爾積就是列出所有的可能性的join方式。

cross join result
TableA(col1)	TableB(col1)
0	1
0	2
0	3
0	4
1	1
1	2
1	3
1	4
2	1
2	2
2	3
2	4
3	1
3	2
3	3
3	4

?

好了，在復習一下：

inner join?，最強約束匹配，只有全部符合的數據才會留下。

Left join ,保留左表內所有數據，右表無對應的用NULL代替。

right join?保留右表內所有數據，左表無對應的用NULL代替。

Full join?保留左右表內所有數據，對應表內無對應的用NULL代替。

Cross join?將左表內的每一行數據與右表內的每一行數據進行關聯后輸出。

?

在了解了join語法的基本原理后，我們進入到join算法的部分。其實這方面oracle總結的已經很好了，join的算法主要就三種：nested loop join ,Hash Join?和sort merge join?。理解join的算法后，其實會發現這是一把好錘子，到處都有釘子可以敲~這個我們后面再來八~

?nested loop join?

Nested loop的做法其實就是大家能想到的最簡單，也是最笨的方法：若表A和表B使用nested loop做join,那么就是從A中取一條記錄，然后在右表中用等值查詢的方式進行匹配，當然，為了效率，他會自動選擇B表中的索引進行這種匹配以加速查找。

舉個例子：

TableA(col1)

0

1

2

3

?

TableB(col1)

1

2

3

4

?

如果這兩個表要使用nest loop算法的話，會如何處理呢？

我們假設TableA表是驅動表，那么運算過程如下：

從TableA中取出一行記錄，我們認為是0?這一行，然后，去TableB中查找，是否有col1 = 0的記錄呢？?發現沒有，于是進行下一行，從Table1中找到下一行，也就是1這一行，去B中做查找操作，是否有col1 = 1的記錄呢？發現有，于是就拼成一組記錄后返回。

很容易可以發現，在nested loop join的過程中，驅動表(TableA)是無法使用任何索引的，而目標表(TableB)是可以使用二分查找來加速的，因此，原則上驅動表必須是一個數據量較小的表，被驅動表則最好有針對匹配條件的索引，這樣就可以達到最優查找效率。

?Hash Join

HashJoin的思路則是使用Hash?映射表的方式進行匹配的。

他的假定也是一個大表和一個小表進行join，如果小表能全部的放到內存中，那么，如果能夠將小表以匹配條件作為key，記錄作為value，組成一個hashMap，我們就可以利用Map的contains方法來快速的找到所有符合join要求的結果了。

還是以上面的表格來舉個例子：

假設TableA是小表，TableB是大表，那么先將TableA放到內存Hash表內，然后從B表中取出每一條記錄，去TableA的Hash表內進行匹配即可。

?sort merge join

最后的一種join策略，sort merge join ,若兩個表都能夠按照匹配條件進行排序，那么sort merge?就能夠用很低的內存消耗來完成join的操作了。因為兩張表都是有序的，所以只需要順序的從左表和右表中取出數據，進行拼裝即可。

具體的做法是：首先，如果TableA和TableB沒有按照col1 asc排序，那么先進行排序，然后，重復以下步驟：第一輪1：?從TableA中取一條記錄，0，?從TableB中取出一條記錄，1，發現不匹配，但TableA: 0于是TableA指針下移，獲得下一個數據1?，TableB?不動。第二輪，TableA : 1 = TableB:1?，于是找到一行符合要求的記錄，TableA指針下移，TableB指針也下移。不斷重復，直到找到所有符合要求的記錄。

可以看到，這種方式在處理兩個有序大表join的時候，效率遠遠超過其他方式，并且?Sort merge join是處理full outer join的效率最高的方法之一（當然一般也沒人用這種join方式- -）。。

?

每一種方式，都有其主要的適應場景，因此需要根據表的實際大小來做動態決策~?小表join大表，一般選擇nested loop或hashJoin，而大表join?大表，往往選擇sort merge join的方式。

?

再稍微擴展一點點，不知道大家看到sort merge?算法以后是不是有種似曾相識的感覺~？?我們在列存，倒排索引中，似乎都看到了類似的算法。

沒錯，他們都是一類問題，解決方法也都是類似的~

可以認為，join，尤其是inner join，就是多個集合取公共交集的過程，在倒排索引中是在多個搜索詞中取交集，在列存中是在符合要求的多列中取交集，行存join語法是在多個表格中取交集的過程，在where條件中就是and條件，甚至連使用索引的過程其實都是索引集合和主表數據集合之間取交集的過程。

?

因此，如果我們能了解在各類場景中如何進行取交集的操作，并且了解在各類場景中取交集的過程有什么限制，應該如何進行優化的話，那我們就能夠很輕松的處理數據查詢中的很大一部分場景了~是不是很有吸引力呢？

?

做下簡單的小結吧：

Nested loop?和hash join?，都能夠比較輕松的處理小表和大表的取交集場景，其中nested loop要求大表有索引，如果小表可以完全的被放到內存中，那么hash join是一個比較好的處理大小表join的方式。

Sort merge join?則要求兩張表都需要按照匹配條件排序，這個的構建成本略高，但它的優勢是，排序過程對內存要求較低，并且可以充分的并行執行，因此可以發現，它經常出現在列存，倒排索引等各類條件變化頻繁，數據量非常大的場景中。

轉自:http://blog.sina.com.cn/s/blog_693f08470101rjt0.html

總結

以上是生活随笔為你收集整理的海量数据 - join处理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。