程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 數據庫知識 >> SqlServer數據庫 >> 關於SqlServer >> 淺談查詢優化器中的JOIN算法

淺談查詢優化器中的JOIN算法

編輯:關於SqlServer

查詢優化器都是支持JOIN操作的,而SQL Server 中主要有以下三類JOIN算法:Nested Loop、Sort-Merge以及Hash Join。盡管每種算法都並不是很復雜,但考慮到性能優化,在產品級的優化器實現時往往使用的是改進過的變種算法。譬如SQL Server 支持block nested loops、index nexted loops、sort-merge、hash join以及hash team。我們在這裡只對上述三種基本算法的原型做一個簡單的介紹。

【假設】有兩張表R和S,R共占有M頁,S共占有N頁。r 和 s 分別代表元組,而 i 和 j 分別代表第i或者第 j 個字段,也就是後文提到的JOIN字段。

1. Nested Loop Join(嵌套循環聯結)

算法:

其思路相當的簡單和直接:對於關系R的每個元組 r 將其與關系S的每個元組 s 在JOIN條件的字段上直接比較並篩選出符合條件的元組。寫成偽代碼就是:

foreach tuple r Î R do
foreach tuple s Î S do
if ri==sj then add to result

代價:

被聯結的表所處內層或外層的順序對磁盤I/O開銷有著非常重要的影響。而CPU開銷相對來說影響較小,主要是元組讀入內存以後(in-memory)的開銷,是 O (n * m)

對於I/O開銷,根據 page-at-a-time 的前提條件,I/O cost = M + M * N,翻譯一下就是 I/O的開銷 = 讀取M頁的I/O開銷 + M次讀取N頁的I/O開銷。

使用小結:

• 適用於一個集合大而另一個集合小的情況(將小集合做為外循環),I/O性能不錯。

• 當外循環輸入相當小而內循環非常大且有索引建立在JOIN字段上時,I/O性能相當不錯。

• 當兩個集合中只有一個在JOIN字段上建立索引時,一定要將該集合作為內循環。

• 對於一對一的匹配關系(兩個具有唯一約束字段的聯結),可以在找到匹配元組後跳過該次內循環的剩余部分(類似於編程語言循環語句中的continue)。

2. Sort-Merge Join (排序合並聯結)

Nested Loop一般在兩個集合都很大的情況下效率就相當差了,而Sort-Merge在這種情況下就比它要高效不少,尤其是當兩個集合的JOIN字段上都有聚集索引(clustered index)存在時,Sort-Merge性能將達到最好。

算法:

基本思路也很簡單(復習一下數據結構中的合並排序吧),主要有兩個步驟:

(1) 按JOIN字段進行排序

(2) 對兩組已排序集合進行合並排序,從來源端各自取得數據列後加以比較(需要根據是否在JOIN字段有重復值做特殊的“分區”處理)

代價:(主要是I/O開銷)

有兩個因素左右Sort-Merge的開銷:JOIN字段是否已排序 以及 JOIN字段上的重復值有多少。

• 最好情況下(兩列都已排序且至少有一列沒有重復值):O (n + m) 只需要對兩個集合各掃描一遍

• 最差情況下(兩列都未排序且兩列上的所有值都相同):O (n * log n + m * log m + n * m) 兩次排序以及一次全部元組間的笛卡爾乘積

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved