嵌套循環連接

嵌套循環連接（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>

這種算法將會從硬盤中讀取 n_r*b_s+ b_r 個頁， b_r 和 b_s 是R和S表所占用的頁的個數， n_r 是R表中的記錄數。

這種算法的IO次數為 $O(|R||S|)$，$|R|$$|S|$

改進方法

這種算法可以通過更改循環的嵌套方式減少硬盤的訪問次數到 b_r*b_s+ b_r 次。 對於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>