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

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.