ITPub博客

首页 > Linux操作系统 > Linux操作系统 > How Nested Loop JOIN Works [ID 263517.1]

How Nested Loop JOIN Works [ID 263517.1]

原创 Linux操作系统 作者:spider0283 时间:2012-09-11 22:43:36 0 删除 编辑

Applies To

Oracle Server - Enterprise Edition - Version: 8.1.7 to 9.2.0.4
Information in this document applies to any platform.

Goal

This article explains how a nested loop join works.

Fix

A nested loop join is the simplest join technique.

Let R and S be the two relations (tables) to be joined.
And R is designated as outer table and S is inner table.

For each row 'r' of the outer table, all rows 's' of inner table are read and compared with the row from the outer table. Whenever the join condition is satisfied, the two rows are concatenated to form. a row which is placed in an output relation.

In simplest words, each row of the cartesian product R x S is tested on the join condition. If it it satisfied then it is included into the join result.

Hence, for a nested loop join to occur, a where clause is not always needed.

The algorithm for the same is as follows:

for each row r belongs to R
for each row s belongs to S
if r and s satisfy C then 
put (r concatenate s) in the output table
endif
end for
end for


Instead of retrieving one row each time, an entire block of tuples (rows) is read from disk and cached in main memory. This is more efficient because this way, several random accesses are replaced by sequential rows accesses which is faster. A further performance improving measure is to use the relation with the lowest cardinality as the outer relation in order to reduce the I/O costs which will be given by :

size of outer table + (size of outer table)*(size of the inner relation)

And this can be minimized if :

size of outer table <= size of inner table.

Furthermore, we can switch the direction in which the inner relation is read each time. This has the advantage that the last block read by the previous inner loop is the first block of the oncoming inner loop. It still is in a memory buffer and therefore doesn't need to read from disk.

返回页首返回页首

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/38267/viewspace-743198/,如需转载,请注明出处,否则将追究法律责任。

下一篇: 11113
请登录后发表评论 登录
全部评论

注册时间:2011-03-29

  • 博文量
    194
  • 访问量
    622756