跳至內容

嵌套循環連接

維基百科,自由的百科全書

嵌套循環連接(Nested loop join)是通過嵌套的循環語句把多個表連接起來的簡單算法SQL中的連接操作是資料庫管理中重要的一環,

算法內容

兩個關係資料庫表R和S通過如下的方法連接在一起:

  For each tuple r in R do
     For each tuple s in S do
        If r and s satisfy the join condition
           Then output the tuple <r,s>

這種算法將會從硬碟中讀取 nr*bs+ br 個頁, br 和 bs 是R和S表所占用的頁的個數, nr 是R表中的記錄數。

這種算法的IO次數為 

改進方法

這種算法可以通過更改循環的嵌套方式減少硬碟的訪問次數到 br*bs+ br 次。 對於R表的每一頁,S的每一個記錄只需要被讀一次。

  For each block block_r in R do
     For each tuple s in S do
        For each tuple r in block_r do
           If r and s satisfy the join condition
              Then output the tuple <r,s>