• <menu id="gyiem"><menu id="gyiem"></menu></menu>
  • <menu id="gyiem"><code id="gyiem"></code></menu>

    SQL優化(一) Merge Join vs. Hash Join vs. Nested Loop

    原創文章,轉載請務必將下面這段話置于文章開頭處(保留超鏈接)。
    本文轉發自技術世界原文鏈接 http://www.luozeyang.com/2015/03/07/Join1/

    Nested Loop,Hash Join,Merge Join介紹

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

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

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

    Nested Loop,Hash JOin,Merge Join對比

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

    實驗

    本文所做實驗均基于PostgreSQL 9.3.5平臺

    小于萬條記錄小表與大表Join

    一張記錄數1萬以下的小表nbar.mse_test_test,一張大表165萬條記錄的大表nbar.nbar_test,大表上建有索引

    Query 1:等值Join

    1
    2
    3
    4
    5
    6
    7
    select 
    count(*)
    from
    mse_test_test,
    nbar_test
    where
    mse_test_test.client_key = nbar_test.client_key;

    Query 1 Test 1: 查詢優化器自動選擇Nested Loop,耗時784.845 ms

    Nested loop

      如下圖所示,執行器將小表mse_test_test作為外表(驅動表),對于其中的每條記錄,通過大表(nbar_test)上的索引匹配相應記錄。

    Nested loop

    Query 1 Test 2:強制使用Hash Join,耗時1731.836ms

    Nested loop join

      如下圖所示,執行器選擇一張表將其映射成散列表,再遍歷另外一張表并從散列表中匹配相應記錄。
    Hash join

    Query 1 Test 3:強制使用Merge Join,耗時4956.768 ms

    Merge join plan

      如下圖所示,執行器先分別對mse_test_test和nbar_test按client_key排序。其中mse_test_test使用快速排序,而nbar_test使用external merge排序,之后對二者進行Merge Join。
    Merge join

    Query 1 總結 1 :

    通過對比Query 1 Test 1Query 1 Test 2Query 1 Test 3可以看出Nested Loop適用于結果集很小(一般要求小于一萬條),并且內表在Join字段上建有索引(這點非常非常非常重要)。

    • 在大表上創建聚簇索引

    Query 1 Test 4:強制使用Merge Join,耗時1660.228 ms

    Merge join

      如下圖所示,執行器通過聚簇索引對大表(nbar_test)排序,直接通過快排對無索引的小表(mse_test_test)排序,之后對二才進行Merge Join。
    Merge join

    Query 1 總結 2:

    通過對比Query 1 Test 3Query 1 Test 4可以看出,Merge Join的主要開銷是排序開銷,如果能通過建立聚簇索引(如果Query必須顯示排序),可以極大提高Merge Join的性能。從這兩個實驗可以看出,創建聚簇索引后,查詢時間從4956.768 ms縮減到了1815.238 ms。

    • 在兩表上同時創建聚簇索引

    Query 1 Test 5:強制使用Merge Join,耗時2575.498 ms。

    Merge join with cluster index

      如下圖所示,執行器通過聚簇索引對大表(nbar_test)和小表(mse_test_test)排序,之后才進行Merge Join。
    Merge join

    Query 1 總結 3:

    對比Query 1 Test 4Query 1 Test 5,可以看出二者唯一的不同在于對小表(mse_test_test)的訪問方式不同,前者使用快排,后者因為聚簇索引的存在而使用Index Only Scan,在表數據量比較小的情況下前者比后者效率更高。由此可看出如果通過索引排序再查找相應的記錄比直接在原記錄上排序效率還低,則直接在原記錄上排序后Merge Join效率更高。

    • 刪除nbar_test上的索引

      Query 1 Test 6:強制使用Hash Join,耗時1815.238 ms

      時間與Query 1 Test 2幾乎相等。
      Hash join without index

      如下圖所示,與Query 1 Test 2相同,執行器選擇一張表將其映射成散列表,再遍歷另外一張表并從散列表中匹配相應記錄。
      Hash join

    Query 1 總結 4 :

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

    兩大表Join

    mse_test約100萬條記錄,nbar_test約165萬條記錄

    ###Query 2:不等值Join

    1
    2
    3
    4
    5
    6
    7
    8
    9
       select 
    count(*)
    from
    mse_test,
    nbar_test
    where
    mse_test.client_key = nbar_test.client_key
    and
    mse_test.client_key between 100000 and 300000;

    Query 2 Test 1:強制使用Hash Join,失敗

    本次實驗通過設置enable_hashjoin=trueenable_nestloop=falseenable_mergejoin=false來試圖強制使用Hash Join,但是失敗了。
    Nested loop

    SQL優化系列

    郭俊 Jason wechat
    歡迎關注作者微信公眾號【大數據架構】
    您的贊賞將支持作者繼續原創分享
    速赢彩app 日喀则 | 澄迈 | 长葛 | 和田 | 松原 | 慈溪 | 江西南昌 | 商丘 | 迪庆 | 包头 | 山南 | 黑龙江哈尔滨 | 鹤岗 | 石狮 | 海门 | 吉林 | 澳门澳门 | 赣州 | 大理 | 海丰 | 资阳 | 延安 | 黄冈 | 锡林郭勒 | 新乡 | 大庆 | 诸暨 | 五家渠 | 普洱 | 河南郑州 | 崇左 | 怀化 | 赤峰 | 马鞍山 | 凉山 | 昌吉 | 姜堰 | 长治 | 公主岭 | 固原 | 喀什 | 德阳 | 海门 | 曲靖 | 邢台 | 大连 | 保定 | 白城 | 吉林 | 温州 | 宜都 | 克孜勒苏 | 永新 | 濮阳 | 陇南 | 龙岩 | 山南 | 邹城 | 咸宁 | 陇南 | 黑龙江哈尔滨 | 广汉 | 长兴 | 六安 | 金坛 | 常州 | 无锡 | 宜宾 | 九江 | 厦门 | 固原 | 偃师 | 漯河 | 天长 | 三河 | 通辽 | 雅安 | 荆门 | 梅州 | 济宁 | 常德 | 深圳 | 安岳 | 长兴 | 新疆乌鲁木齐 | 靖江 | 昌吉 | 鄂州 | 偃师 | 六安 | 徐州 | 阿克苏 | 恩施 | 贺州 | 曲靖 | 宣城 | 伊犁 | 鞍山 | 潜江 | 安顺 | 溧阳 | 鄂尔多斯 | 迪庆 | 湖南长沙 | 永州 | 深圳 | 秦皇岛 | 馆陶 | 汕头 | 武安 | 寿光 | 宜春 | 澳门澳门 |