JOIN的类型及语法
    连接的意义在于，在水平方向上合并两个数据集合（通常是表），并产生一个新的数据集合。其方法是将一个数据源中的行与另一个数据源中和他匹配的行进行组合，形成一个新的元组。ORACLE提供了多种类型的连接方式，连接的SQL基本语法是：
    1. ORACLE标准
       数据集1 [连接类型] JOIN 数据集2 [连接条件]
       如： a left join b on a.id = b.id
    2. SQL999标准
       数据集1 , 数据集2 WHERE [连接条件]
       如： a , b where a.id = b.id(+)
    连接类型主要分为以下几种：
    1. Inner join
        内连接，只连接匹配的行，首先对两个表做笛卡尔积运算，再满足选取A.id= B.id的行。
    2. Left join
        左外连接，选取左边集合的全部数据作为结果，并选取右边集合的满足条件的行作为结果，对于左边不等于右边的记录，则用NULL补齐。
    3. Right join
        右外连接，与左外连接对称。
    4. Full outer join
        全外连接，相当于取左外连接与右外连接的并集。
    5. Cross join
        交叉连接，相当于没有连接条件的自然连接。用的较少。
  JOIN的实现机制
    数据库的JOIN操作实现主要有三种：
    1. 嵌套循环连接(Nested Loop Join)
        嵌套循环，即使用两个FOR循环来实现。假设，要连接的两个关系称为R和S，连接条件为P。则嵌套循环会将其中一个(R)作为外层循环，另外一个(S)作为内层循环。取R中的一条记录，与S中的所有记录进行对比，如果找到满足条件P的记录，则将Rx和Sx进行合并，加入结果中。算法公式如下：
1        For each tuple X in R do
1.1        For each tuple Y in S do
1.1.1        If (X, Y) 满足连接条件
1.1.2        Then 将(X, Y)加入结果中
1.2        End
2        End

        嵌套循环是最通用的一个算法，它与线性扫描一样，不需要任何索引，而且不管是什么类型的连接条件，该算法都适合。但是，嵌套循环的代价是最大的，因为该算法需要逐一比对R和S中的每一个元组。如果数据量较大，则无法全部放入内存，而引起磁盘与内存的交互非常频繁。及时能够全部载入内存，也会引起CPU的CACHE命中率低下，从而影响性能。

        嵌套循环连接分为两种。
        a) 块嵌套循环(Nested Block Loop Join)
            块嵌套循环采用了分块策略，但是却增加了两层循环，他由4个FOR循环组成，外面两个进行块与块之前的循环，里面两个进行块内循环。假设有R和S两个集合，A是R中的块，B是S中的块，X是A中的元组，Y是B中的元组，连接条件为P。则块嵌套循环每次都将R和S分割成若干个A和B，每次取出一个块A和块B，再循环块A和B中的每一个元组(tuple)，如果符合P(X,Y)，则将记录连接起来，写入结果集。相比嵌套循环，块嵌套循环在时间复杂度上并无改进，但是由于每次以块为单位进行磁盘交互，减少了磁盘交换次数。算法公式如下：
1        For each block A in R do
1.1        For each block B in S do
1.1.1        For each tuple X in A do
1.1.1.1        For each tuple Y in B do
1.1.1.1.1        If P(X, Y)
1.1.1.1.2        Then Result=Result+(X, Y)
1.1.1.2        End
1.1.2        End
1.2        End
2        End
        b) 索引嵌套循环(Nested Index Loop Join)
            对于R和S以及连接条件P，如果S中存在一种索引，使得R中的任意一个元组X，能够通过该索引找到S中满足条件P的元组Y，则可以利用索引查找替代文件扫描。这样就只需要扫描一个表，然后根据索引查找另外一个表，大大减少了时间复杂度。算法公式如下：
1        For each tuple T X in R do
1.1        Find all tuples {Y} in S that P(X, Y)
1.2        For each y in {Y} do
1.2.1        Result=Result+(X,y)
1.3        End
2        End
    2. 归并连接(Merge Join)
        归并连接又叫排序归并连接，主要用于自然连接和等值连接。假设有R和S两个集合，连接条件为P，则在进行连接之前需要先让R和S是有序的(Order By)，然后分别对两个表扫描一遍即可完成。算法公式如下：
1        将R和S中元组都按连接属性从小到大排序
2        令i=j=0
3        While i3.1        While S[j]<>R[i] do
3.1.1        While S[j]3.1.1.1        j=j+1
3.1.2        End
3.1.3        While S[j]>R[i] do
3.1.3.1        i=i+1
3.1.4        End
3.2        End
3.3        m=i, n=j
3.4        While S[m]=S[i] do
3.4.1        M=m+1
3.5        End
3.6        While R[n]=R[j] do
3.6.1        N=n+1
3.7        End
3.8        For each tuple X from R[i] to R[m - 1] do
3.8.1        For each tuple Y from S[j] to S[n-1] do
3.8.1.1        Result=Result+(X, Y)
3.8.2        End
3.9        End
4        End
        归并连接执行起来效率非常高，但是他只能进行等值连接和自然连接，对于其他谓词的连接显得力不从心。并且还要求连接之前对数据进行排序。

    3. 散列连接(Hash Join)
        散列连接类似于归并连接，也只适合于自然连接和等值连接。在散列连接算法中，散列函数H用于对两个关系进行划分。HASH算法的基本思想是把两个关系按连接的属性划分成具有相同散列值的元组集合。散列连接不需要索引，并且与循环嵌套连接相比，散列连接更容易处理大结果集，唯一的缺点是他只能作用等值连接。
        假设H是将JoinAttrs值映射到{0，1，2…，max}的散列函数，并且具有良好的随机性和均匀性，其中JoinAttrs表示关系R与S中的公共属性组，或者连接属性组。Hr1，Hr2，…，Hrmax表示关系R的元组划分，Hs1，Hs2，…，Hsmax表示关系S的元组划分，则散列连接算法的思想如下：如果关系R的一个元组与关系S的一个元组满足连接条件，那么它们在连接属性上有相同的值。若该元组在函数H中映射为i，则关系R的那个元组必在Hri中，关系S的那个元组必在His中。因此，Hri中的元组只需与His中的元组进行比较，而无需与S中其它元组进行比较。

  ORACLE数据库对以上三种连接都有实现。
    1. 嵌套循环连接是最慢的算法，只有在不得已才使用。索引能够有效的提高其速度。
    2. 归并连接比嵌套循环快的多，但是它也不是Oracle优先选择的算法。
    3. Oracle Hash Join是一种非常高效的JOIN算法，主要以CPU(Hash计算)和内存空间(创建Hash Table)为代价，获得最高效率。Hash Join一般适应于大表和小表之间的连接，这样能够直接将小表构建到内存中，并且cache住，这称为Hash Cluster,大表称为Probe表。

参考资料：http://avatar0411.blog.sohu.com/148264302.html