本文介紹了Merge Join，Hash Join，Nested Loop這三種數(shù)據(jù)庫(kù)Join方式的工作原理，并通過(guò)實(shí)驗(yàn)進(jìn)一步說(shuō)明了其適用范圍。

原創(chuàng)文章，轉(zhuǎn)載請(qǐng)務(wù)必將下面這段話置于文章開頭處（保留超鏈接）。
本文轉(zhuǎn)發(fā)自技術(shù)世界，原文鏈接　SQL優(yōu)化（一） Merge Join vs. Hash Join vs. Nested Loop | 技術(shù)世界 | SQL,sql,sql優(yōu)化,數(shù)據(jù)庫(kù),PostgreSQL,postgres,join,merge join,hash join,nested loop,技術(shù)世界,郭俊 Jason,大數(shù)據(jù)架構(gòu)

Nested Loop，Hash Join，Merge Join介紹

• Nested Loop:
  對(duì)于被連接的數(shù)據(jù)子集較小的情況，Nested Loop是個(gè)較好的選擇。Nested Loop就是掃描一個(gè)表（外表），每讀到一條記錄，就根據(jù)Join字段上的索引去另一張表（內(nèi)表）里面查找，若Join字段上沒有索引查詢優(yōu)化器一般就不會(huì)選擇 Nested Loop。在Nested Loop中，內(nèi)表（一般是帶索引的大表）被外表（也叫“驅(qū)動(dòng)表”，一般為小表——不緊相對(duì)其它表為小表，而且記錄數(shù)的絕對(duì)值也較小，不要求有索引）驅(qū)動(dòng)，外表返回的每一行都要在內(nèi)表中檢索找到與它匹配的行，因此整個(gè)查詢返回的結(jié)果集不能太大（大于1 萬(wàn)不適合）。

• Hash Join:
  Hash Join是做大數(shù)據(jù)集連接時(shí)的常用方式，優(yōu)化器使用兩個(gè)表中較小（相對(duì)較小）的表利用Join Key在內(nèi)存中建立散列表，然后掃描較大的表并探測(cè)散列表，找出與Hash表匹配的行。
  這種方式適用于較小的表完全可以放于內(nèi)存中的情況，這樣總成本就是訪問(wèn)兩個(gè)表的成本之和。但是在表很大的情況下并不能完全放入內(nèi)存，這時(shí)優(yōu)化器會(huì)將它分割成若干不同的分區(qū)，不能放入內(nèi)存的部分就把該分區(qū)寫入磁盤的臨時(shí)段，此時(shí)要求有較大的臨時(shí)段從而盡量提高I/O 的性能。它能夠很好的工作于沒有索引的大表和并行查詢的環(huán)境中，并提供最好的性能。大多數(shù)人都說(shuō)它是Join的重型升降機(jī)。Hash Join只能應(yīng)用于等值連接(如WHERE A.COL3 = B.COL4)，這是由Hash的特點(diǎn)決定的。

• Merge Join:
  通常情況下Hash Join的效果都比排序合并連接要好，然而如果兩表已經(jīng)被排過(guò)序，在執(zhí)行排序合并連接時(shí)不需要再排序了，這時(shí)Merge Join的性能會(huì)優(yōu)于Hash Join。Merge join的操作通常分三步：
  　　1. 對(duì)連接的每個(gè)表做table access full;
  　　2. 對(duì)table access full的結(jié)果進(jìn)行排序。
  　　3. 進(jìn)行merge join對(duì)排序結(jié)果進(jìn)行合并。
  在全表掃描比索引范圍掃描再進(jìn)行表訪問(wèn)更可取的情況下，Merge Join會(huì)比Nested Loop性能更佳。當(dāng)表特別小或特別巨大的時(shí)候，實(shí)行全表訪問(wèn)可能會(huì)比索引范圍掃描更有效。Merge Join的性能開銷幾乎都在前兩步。Merge Join可適于于非等值Join（>，<，>=，<=，但是不包含!=，也即<>）

Nested Loop，Hash JOin，Merge Join對(duì)比

類別Nested LoopHash JoinMerge Join

使用條件	任何條件	等值連接（=）	等值或非等值連接(>，<，=，>=，<=)，‘<>’除外
相關(guān)資源	CPU、磁盤I/O	內(nèi)存、臨時(shí)空間	內(nèi)存、臨時(shí)空間
特點(diǎn)	當(dāng)有高選擇性索引或進(jìn)行限制性搜索時(shí)效率比較高，能夠快速返回第一次的搜索結(jié)果。	當(dāng)缺乏索引或者索引條件模糊時(shí)，Hash Join比Nested Loop有效。通常比Merge Join快。在數(shù)據(jù)倉(cāng)庫(kù)環(huán)境下，如果表的紀(jì)錄數(shù)多，效率高。	當(dāng)缺乏索引或者索引條件模糊時(shí)，Merge Join比Nested Loop有效。非等值連接時(shí)，Merge Join比Hash Join更有效
缺點(diǎn)	當(dāng)索引丟失或者查詢條件限制不夠時(shí)，效率很低；當(dāng)表的紀(jì)錄數(shù)多時(shí)，效率低。	為建立哈希表，需要大量?jī)?nèi)存。第一次的結(jié)果返回較慢。	所有的表都需要排序。它為最優(yōu)化的吞吐量而設(shè)計(jì)，并且在結(jié)果沒有全部找到前不返回?cái)?shù)據(jù)。

實(shí)驗(yàn)

本文所做實(shí)驗(yàn)均基于PostgreSQL 9.3.5平臺(tái)

小于萬(wàn)條記錄小表與大表Join

一張記錄數(shù)1萬(wàn)以下的小表nbar.mse_test_test，一張大表165萬(wàn)條記錄的大表nbar.nbar_test，大表上建有索引

Query 1:等值Join

select count(*) from mse_test_test, nbar_test where mse_test_test.client_key = nbar_test.client_key;

Query 1 Test 1： 查詢優(yōu)化器自動(dòng)選擇Nested Loop，耗時(shí)784.845 ms

　　如下圖所示，執(zhí)行器將小表mse_test_test作為外表（驅(qū)動(dòng)表），對(duì)于其中的每條記錄，通過(guò)大表（nbar_test）上的索引匹配相應(yīng)記錄。

Query 1 Test 2：強(qiáng)制使用Hash Join，耗時(shí)1731.836ms

　　如下圖所示，執(zhí)行器選擇一張表將其映射成散列表，再遍歷另外一張表并從散列表中匹配相應(yīng)記錄。

Query 1 Test 3：強(qiáng)制使用Merge Join，耗時(shí)4956.768 ms

　　如下圖所示，執(zhí)行器先分別對(duì)mse_test_test和nbar_test按client_key排序。其中mse_test_test使用快速排序，而nbar_test使用external merge排序，之后對(duì)二者進(jìn)行Merge Join。

Query 1 總結(jié) 1 ：

通過(guò)對(duì)比Query 1 Test 1，Query 1 Test 2，Query 1 Test 3可以看出Nested Loop適用于結(jié)果集很小（一般要求小于一萬(wàn)條），并且內(nèi)表在Join字段上建有索引（這點(diǎn)非常非常非常重要）。

• 在大表上創(chuàng)建聚簇索引

Query 1 Test 4：強(qiáng)制使用Merge Join，耗時(shí)1660.228 ms

　　如下圖所示，執(zhí)行器通過(guò)聚簇索引對(duì)大表（nbar_test）排序，直接通過(guò)快排對(duì)無(wú)索引的小表（mse_test_test）排序，之后對(duì)二才進(jìn)行Merge Join。

Query 1 總結(jié) 2：

通過(guò)對(duì)比Query 1 Test 3和Query 1 Test 4可以看出，Merge Join的主要開銷是排序開銷，如果能通過(guò)建立聚簇索引（如果Query必須顯示排序），可以極大提高M(jìn)erge Join的性能。從這兩個(gè)實(shí)驗(yàn)可以看出，創(chuàng)建聚簇索引后，查詢時(shí)間從4956.768 ms縮減到了1815.238 ms。

• 在兩表上同時(shí)創(chuàng)建聚簇索引

Query 1 Test 5：強(qiáng)制使用Merge Join，耗時(shí)2575.498 ms。

　　如下圖所示，執(zhí)行器通過(guò)聚簇索引對(duì)大表（nbar_test）和小表（mse_test_test）排序，之后才進(jìn)行Merge Join。

Query 1 總結(jié) 3：

對(duì)比Query 1 Test 4和Query 1 Test 5，可以看出二者唯一的不同在于對(duì)小表（mse_test_test）的訪問(wèn)方式不同，前者使用快排，后者因?yàn)榫鄞厮饕拇嬖诙褂肐ndex Only Scan，在表數(shù)據(jù)量比較小的情況下前者比后者效率更高。由此可看出如果通過(guò)索引排序再查找相應(yīng)的記錄比直接在原記錄上排序效率還低，則直接在原記錄上排序后Merge Join效率更高。

• 刪除nbar_test上的索引

  Query 1 Test 6：強(qiáng)制使用Hash Join，耗時(shí)1815.238 ms

  時(shí)間與Query 1 Test 2幾乎相等。

  如下圖所示，與Query 1 Test 2相同，執(zhí)行器選擇一張表將其映射成散列表，再遍歷另外一張表并從散列表中匹配相應(yīng)記錄。

Query 1 總結(jié) 4 ：

通過(guò)對(duì)比Query 1 Test 2，Query 1 Test 6可以看出Hash Join不要求表在Join字段上建立索引。

兩大表Join

mse_test約100萬(wàn)條記錄，nbar_test約165萬(wàn)條記錄

###Query 2:不等值Join

select count(*)from mse_test, nbar_test where mse_test.client_key = nbar_test.client_key andmse_test.client_key between 100000 and 300000;

Query 2 Test 1：強(qiáng)制使用Hash Join，失敗

本次實(shí)驗(yàn)通過(guò)設(shè)置enable_hashjoin=true，enable_nestloop=false，enable_mergejoin=false來(lái)試圖強(qiáng)制使用Hash Join，但是失敗了。

總結(jié)

以上是生活随笔為你收集整理的SQL优化（一） Merge Join vs. Hash Join vs. Nested Loop的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。