資料庫的表連接配接方式詳解

資料庫的連接配接方式：

Nested loop join

Hash join

Merge join

Nested loop join:

Nested loop join的思路：

将Outer relation的每一行資料和Inner relation的每一行做對比，如果符合關聯條件的話才會傳回關聯的資料集。

僞代碼：

nested_loop_join(array outer, array inner)
  for each row a in outer
    for each row b in inner
      if (match_join_condition(a,b))
        write_result_in_output(a,b)
      end if
    end for
   end for
           

是以這是一個兩層的循環，它的算法時間複雜度是 O(N*M)。

根據磁盤的I/O,Outer relation有N行資料，Inner relation有M行資料。那麼根據這個算法就需要從磁盤上讀N+N*M行資料。但是如果Inner relation的資料量足夠小可以存在記憶體裡面，那麼磁盤的I/O就隻有N+M了。

總結：

如果Inner relation小的話比較合适使用這樣方式。

合理的在關聯字段上面建索引也能減少I/O。

Hash join：

Hash join的算法實作比Nested loop會更加複雜，但是更多的情況下面消耗更小成本。

Hash join的思路：

1、從Inner relation取出所有的元素

2、将取出的元素在記憶體裡建立哈希表

3、從outer relation一行一行的取出所有的元素

4、計算從outer relation取出的元素的哈希值，跟據哈希值去找到哈希表裡面想對應的桶

5、然後在桶裡面再找是否有比對元素

桶（bucket）

在算法時間複雜度方面我們作出下面的假設：

1、Inner relation的元素分别放到了X個桶裡

2、哈希值是均衡的，是以桶裡面的資料應該也是相當的

3、outer relation需要到桶裡面比對到一個元素

是以算法的時間複雜度是

(M/X) * N + cost_to_create_hash_table(M) + cost_of_hash_function*N

Merge join:

Merge join的實作思路：

Merge join沒有區分Inner table或者Outer table，對于兩個資料集都用了相同的規則去處理。

1、将兩個資料集都按關聯join的條件排序

2、将兩個排序好的資料集歸并到一起

Merge join僞碼：

mergeJoin(relation a, relation b)
  relation output
  integer a_key:=0;
  integer b_key:=0;
 
  while (a[a_key]!=null or b[b_key]!=null)
    if (a[a_key] < b[b_key])
      a_key++;
    else if (a[a_key] > b[b_key])
      b_key++;
    else //Join predicate satisfied
	//i.e. a[a_key] == b[b_key]

      //count the number of duplicates in relation a
      integer nb_dup_in_a = 1:
      while (a[a_key]==a[a_key+nb_dup_in_a])
        nb_dup_in_a++;
		
      //count the number of duplicates in relation b
      integer dup_in_b = 1:
      while (b[b_key]==b[b_key+nb_dup_in_b])
        nb_dup_in_b++;
		
	  //write the duplicates in output
	   for (int i = 0 ; i< nb_dup_in_a ; i++)
	     for (int j = 0 ; i< nb_dup_in_b ; i++)	   
	       write_result_in_output(a[a_key+i],b[b_key+j])
		   
      a_key=a_key + nb_dup_in_a-1;
      b_key=b_key + nb_dup_in_b-1;

    end if
  end while
           

怎麼選擇合适的算法：

    如果沒有足夠的記憶體就不要考慮hash join（或者說是full in-memory的hash join）

    兩個不同size的資料集，如果一個資料集大一個資料集很小，使用nested loop會比hash join達到更高的效率，如果是兩個都很大的資料集使用nested loop的話會需要更多的cpu和磁盤開銷。

   如果存在索引的話，如果關聯條件上面有B+ Tree的話就可以考慮是用merge join

   如果你需要排序好的資料集，那麼你也可以使用merge join,因為merge join的結果集就是一個排序後的結果。