1. Join的基本原理

大家都知道，Hive會將所有的SQL查詢轉(zhuǎn)化為Map/Reduce作業(yè)運(yùn)行于Hadoop集群之上。在這里簡要介紹Hive將Join轉(zhuǎn)化為Map/Reduce的基本原理（其它查詢的原理請參考這里）。

假定有user和order兩張表，分別如下：

user表：

order表：

現(xiàn)在想做student和sc兩張表上的連接操作：

SELECT  u.name,  o.orderidFROM user uJOIN order o ON u.uid = o.uid;

Hive是利用hadoop的Map/Reduce計算框架執(zhí)行上述查詢的呢？？

Hive會將出現(xiàn)在連接條件ON之后的所有字段作為Map輸出的key，將所需的字段作為value，構(gòu)建(key, value)，同時為每張表打上不同的標(biāo)記tag，輸出到Reduce端。在Reduce端，根據(jù)tag區(qū)分參與連接的表，實現(xiàn)連接操作。

我們使用下圖來模擬這個過程：

在Map端分別掃描user和order的兩張表。對于user表，在連接條件ON之后的字段為uid，所以以uid作為Map輸出的key，在SELECT語句中還需要name字段，所以name字段作為value的一部分，同時為user表賦予標(biāo)記tag=1，這樣處理user表的mapper地輸出形式為：(uid, “1” + name)。類似的，處理order表的mapper地輸出形式為：(uid, “2” + orderid)，注意，order表的標(biāo)記為2。

具有相同uid的地(key, value)字段在reduce端“集合”，根據(jù)value中tag字段區(qū)分來自不同表的數(shù)據(jù)，使用兩層循環(huán)完成連接操作。

上面就是將Join操作轉(zhuǎn)換為Map/Reduce作業(yè)的基本原理： 在map端掃描表，在reduce端完成連接操作。

2. Hive中的各種Join

寫在前面的話：”Hive不支持非等值連接”

我們使用例子講述各種Join的區(qū)別。假設(shè)my_user和my_order兩張表的數(shù)據(jù)變?yōu)椋?/p>

my_user表：

my_order表：

注意，my_order中有一條重復(fù)記錄。

“不要考慮例子在現(xiàn)實中的意義，這里這是為了演示各種JOIN的區(qū)別”

2.1 INNER JOIN

INNER JOIN，又稱“內(nèi)連接”，執(zhí)行INNER JOIN時，只有兩個表中都有滿足連接條件的記錄時才會保留數(shù)據(jù)。執(zhí)行以下語句：

SELECT  u.name,  o.orderidFROM my_user uJOIN my_order o ON u.uid = o.uid;

結(jié)果為：

因為表my_order中又重復(fù)記錄，所以結(jié)果中也有重復(fù)記錄。

2.2 LEFT OUTER JOIN

LEFT OUTER JOIN（左外連接），JOIN操作符左邊表中符合WHERE條件的所有記錄都會被保留，JOIN操作符右邊表中如果沒有符合ON后面連接條件的記錄，則從右邊表中選出的列為NULL。

執(zhí)行以下語句：

SELECT  u.name,  o.orderidFROM my_user uLEFT OUTER JOIN my_order o ON u.uid = o.uid;

結(jié)果為：

這里由于沒有WHERE條件，所以左邊表my_user中的記錄都被保留，對于uid=3的記錄，在右邊表my_order中沒有相應(yīng)記錄，所以orderid為NULL。

2.3 RIGHT OUTER JOIN

RIGHT OUTER JOIN（右外連接），LEFT OUTER JOIN相對，JOIN操作符右邊表中符合WHERE條件的所有記錄都會被保留，JOIN操作符左邊表中如果沒有符合ON后面連接條件的記錄，則從左邊表中選出的列為NULL。

SELECT  u.name,  o.orderidFROM my_user uRIGHT OUTER JOIN my_order o ON u.uid = o.uid;

執(zhí)行上面SQL語句的結(jié)果為：

由于左表my_user中不存在uid=4的記錄，所以orderid=2001的記錄對應(yīng)的name為NULL。

2.3 FULL OUTER JOIN

結(jié)合上面的LEFT OUTER JOIN和RIGHT OUTER JOIN，很容易想到FULL OUTER JOIN的運(yùn)行機(jī)制：保留滿足WHERE條件的兩個表的數(shù)據(jù)，沒有符合連接條件的字段使用NULL填充。來看一個例子：

SELECT  u.name,  o.orderidFROM my_user uFULL OUTER JOIN my_order o ON u.uid = o.uid;

執(zhí)行結(jié)果為：

原因不再解釋，請自行思考。

2.4 LEFT SMEI JOIN

在早期的Hive版本中，不是IN關(guān)鍵字，可以使用LEFT SEMI JOIN實現(xiàn)類似的功能。

LEFT SEMI JOIN（左半開連接）返回左邊表的記錄，前提是右邊表具有滿足ON連接條件的記錄。

先來看一個例子：

SELECT  *FROM my_user uLEFT SEMI JOIN my_order o ON u.uid = o.uid;

執(zhí)行結(jié)果為：

雖然SELECT中使用’*‘，但是只返回了左表my_user的列，而且重復(fù)的記錄沒有返回（重復(fù)記錄在my_order表中）

需要強(qiáng)調(diào)的是：

• 在LEFT SEMI JOIN中，SELECT中不允許出現(xiàn)右表中的列
• 對于左表中的一條記錄，在右表表中一旦找到匹配記錄就停止掃描

3. JOIN 優(yōu)化

現(xiàn)實環(huán)境中會進(jìn)行大量的表連接操作，而且表連接操作通常會耗費(fèi)很懂時間。因此掌握一些基本的JOIN優(yōu)化方法成為熟練運(yùn)用Hive、提高工作效率的基本手段。下面討論一些常用的JOIN優(yōu)化方法。

3.1 MAP-JOIN

本文一開始介紹了Hive中JOIN的基本原理，這種JOIN沒有數(shù)據(jù)大小的限制，理論上可以用于任何情形。但缺點(diǎn)是：需要map端和reduce端兩個階段，而且JOIN操作是在reduce端完成的，稱為reduce side join。

那么，能否省略reduce端，直接在map端執(zhí)行的“map side join”操作呢？？答案是，可以的。

但有個條件，就是：連接的表中必須有一個小表足以放到每個mapper所在的機(jī)器的內(nèi)存中。

下圖展示了map side join的原理。

從上圖中可以看出，每個mapper都會拿到小表的一個副本，然后每個mapper掃描大表中的一部分?jǐn)?shù)據(jù)，與各自的小表副本完成連接操作，這樣就可以在map端完成連接操作。

那多大的表才算是“小表”呢？？

默認(rèn)情況下，25M以下的表是“小表”，該屬性由hive.smalltable.filesize決定。

有兩種方法使用map side join:

• 直接在SELECT語句中指定“小表”，語法是/*+MAPJOIN (tbl)*/，其中tbl就是要復(fù)制到每個mapper中去的小表。例如：

SELECT  /*+ MAPJOIN(my_order)*/  u.name,  o.orderidFROM my_user uLEFT OUTER JOIN my_order o ON u.uid = o.uid;

• 設(shè)置hive.auto.convert.join = true，這樣hive會自動判斷當(dāng)前的join操作是否合適做map join，主要是找join的兩個表中有沒有小表。

但JOIN的兩個表都不是“小表”的時候該怎么辦呢？？這就需要BUCKET MAP JOIN上場了。

3.2 BUCKET MAP JOIN

Map side join固然得人心，但終會有“小表”條件不滿足的時候。這就需要bucket map join了。

Bucket map join需要待連接的兩個表在連接字段上進(jìn)行分桶（每個分桶對應(yīng)hdfs上的一個文件），而且小表的桶數(shù)需要時大表桶數(shù)的倍數(shù)。建立分桶表的例子：

CREATE TABLE my_user(  uid INT,  name STRING)CLUSTERED BY (uid) into 32 bucketsSTORED AS TEXTFILE;

這樣，my_user表就對應(yīng)32個桶，數(shù)據(jù)根據(jù)uid的hash value 與32取余，然后被分發(fā)導(dǎo)不同的桶中。

如果兩個表在連接字段上分桶，則可以執(zhí)行bucket map join了。具體的：

1. 設(shè)置屬性hive.optimize.bucketmapjoin= true控制hive 執(zhí)行bucket map join；
2. 對小表的每個分桶文件建立一個hashtable，并分發(fā)到所有做連接的map端；
3. map端接受了N（N為小表分桶的個數(shù)） 個小表的hashtable，做連接 操作的時候，只需要將小表的一個hashtable 放入內(nèi)存即可，然后將大表的對應(yīng)的split 拿出來進(jìn)行連接，所以其內(nèi)存限制為小表中最大的那個hashtable 的大小

3.3 SORT MERGE BUCKET MAP JOIN

對于bucket map join中的兩個表，如果每個桶內(nèi)分區(qū)字段也是有序的，則還可以進(jìn)行sort merge bucket map join。對于那個的建表語句為：

CREATE TABLE my_user(  uid INT,  name STRING)CLUSTERED BY (uid) SORTED BY (uid) into 32 bucketsSTORED AS TEXTFILE;

這樣一來當(dāng)兩邊bucket要做局部join的時候，只需要用類似merge sort算法中的merge操作一樣把兩個bucket順序遍歷一遍即可完成，這樣甚至都不用把一個bucket完整的加載成hashtable，而且可以做全連接操作。

進(jìn)行sort merge bucket map join時，需要設(shè)置的屬性為：

set hive.optimize.bucketmapjoin= true;set hive.optimize.bucketmapjoin.sortedmerge = true;set hive.input.format = org.apache.hadoop.hive.ql.io.BucketizedHiveInputFormat;

4.各種JOIN對比

參考資料

[1]. Hive SQL的編譯過程: http://tech.meituan.com/hive-sql-to-mapreduce.html [2]. 《Hive變成指南》 [3]. 數(shù)據(jù)倉庫中的SQL性能優(yōu)化（Hive篇）:http://sunyi514.github.io/2013/09/01/%E6%95%B0%E6%8D%AE%E4%BB%93%E5%BA%93%E4%B8%AD%E7%9A%84sql%E6%80%A7%E8%83%BD%E4%BC%98%E5%8C%96%EF%BC%88hive%E7%AF%87%EF%BC%89/ [4]. Join Strategies in Hive:https://www.google.com.hk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CBoQFjAAahUKEwim2badkOTIAhXmxqYKHTw9BfA&url=https%3A%2F%2Fcwiki.apache.org%2Fconfluence%2Fdownload%2Fattachments%2F27362054%2FHive%2BSummit%2B2011-join.pdf&usg=AFQjCNFiPLtjhwezbqYQT_aRYo4wOAmSIA&sig2=RJDLWMpElXYjQvhqV9rocA [5]. Hadoop 中的兩表join: http://www.lxway.net/29500604.html