梦想有多远

http://www.cnblogs.com/RookieStar/archive/2007/01/16/621260.html

三类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   r_i == s_j   then   add <r,s> to result

(全文…)