mysql支援的join演算法Nested Loop JoinIndex Nested-Loop JoinBlock Nested-Loop Join

Index Nested-Loop Join 和 Block Nested-Loop Join是在Nested-Loop Join基礎上做了最佳化。

Nested Loop Join

Nested-Loop Join的思想就是透過雙層迴圈比較資料來獲得結果； 其中左表為外迴圈，右表為內迴圈，左表為驅動表。其實現邏輯簡單粗暴，可以理解為兩層for迴圈，小表在外環，大表在內環，資料比較的次數 = 小表記錄數 * 大表記錄數。

//select * from t1 inner join t2 on t1.a= t2.a;List<結果> lists = new ArrayList<>();for(t2 t2 : t2){  //外層迴圈    for(t1 t1 : t1){  //內迴圈        if(t2.a().equals(t1.a())){  //條件匹配            //存放結果到結果集            結果 = t1的欄位 + t2的欄位            lists.add(結果集);        }    }}

索引巢狀迴圈連線 Index Nested-Loop Join

Index Nested-Loop Join

最佳化思路：內表為大表，可在join欄位上建立索引，減少內表資料的掃描次數。

執行流程：0.前置條件：外表 t2 已在連線用的 a 欄位以建立索引；1.從外表 t1 中讀取一行資料 R；2.使用 R 中的a 欄位和內表 t2 的 a 欄位進行索引關聯查詢；3.根據索引到的記錄取出表 t2 中滿足條件的行，跟 R 組成一行，作為結果集的一部分；4.重複執行步驟 1 到 3，直到表 t1 迴圈結束。

可見，透過索引的建立，避免了對大表進行全表掃描，加快了查詢速度。

快取塊巢狀迴圈連線 Block Nested-Loop Join

Block Nested-Loop Join

最佳化思路：透過一次性快取多條資料，減少外層表的迴圈次數。

t1為小表時的執行流程：1.把t1 表查詢的欄位資料整個讀入執行緒記憶體 join_buffer 中；2.掃描表 t2，把表 t2 中的每一行取出來，跟 join_buffer 中的 資料做對比，滿足 join 條件的，作為結果集的一部分返回。

t1為大表時的執行流程： 1.掃描表 t1，順序讀取一定長度的資料行放入 join_buffer 中；2.掃描表 t2，把 t2 中的每一行取出來，跟 join_buffer 中的資料做對比，滿足 join 條件的，作為結果集的一部分返回；3.清空 join_buffer；4.順序讀取 t1表下一批次資料放入 join_buffer 中，重複步驟2

Oracle的join演算法Nested Loop Join，巢狀迴圈Hash Join，將兩個表中較小的一個在記憶體中構造一個 Hash 表（對JoinKey），掃描另一個表Sort Merge Join，將兩個表排序，然後再進行join

DB2和SQL Server也使用這三種方式join演算法。

Hash Join

Hash Join的使用場景：

適合於小表與大表連線、返回大型結果集的連線只能用於等值連線，且只能在CBO最佳化器模式下

在inner/left/right join，以及union/group by等 都會使用hash join進行操作。

實現原理:

Hash Join

Hash Join中的小表稱之為hash表，大表稱為探查表，以小表作為驅動表。

兩個輸入：

– build input（也叫做outer input），小表

– probe input（也叫做inner input），大表

兩個階段：

– Build（構造）階段，處理build input

– Probe（探測）階段，探測probe input

build 階段，主要是構造雜湊表(hash table)：

在inner/left/right join等操作中，表關聯欄位作為hash key在group by操作中，group by的欄位作為hash key；在union或其它去重操作中，hash key包括所有的select欄位。

一個hash值對應到hash table中的hash buckets。多個hash buckets可以使用連結串列資料結構連線起來。

Probe 階段，從probe input中取出每一行記錄，根據key值生成hash值，從build階段構造的hash table中搜索對應的hash bucket。

Grace Hash join