time:2010-08-20
表的连接
表的连接是指在一个SQL语句中通过表与表之间的关联，从一个或多个表检索出相关的数据。如果一个SQL语句的关联表超过两个，
那么连接的顺序如何呢？ORACLE首先连接其中的两个表，产生一个结果集；然后将产生的结果集与下一个表再进行关联；继续这
个过程，直到所有的表都连接完成；最后产生所需的数据。
ORACLE 从6的版本开始，优化器使用4种不同的表的连接方式：
1 嵌套循环连接（NESTED LOOP JOIN）
2 群集连接 (CLUSTER JOIN)
3 排序合并连接（SORT MERGE JOIN）
4 笛卡尔连接 (CARTESIAN JOIN)
ORACLE 7.3中，新增加了
5 哈希连接(HASH JOIN)。
在ORACLE 8中，新增加了
6 索引连接(INDEX JOIN)。
这六种连接方式都有其各自技术特点，在一定的条件下，可以充分发挥高效的性能。但是也都有其局限性，如果使用不当，不仅不
能提高效率，反而会严重影响系统的性能。因此，深入地探讨连接方式的内部 运行机制对于性能优化是必要的。
1 嵌套循环连接
嵌套循环连接的内部处理的流程：
1） Oracle 优化器根据基于规则RBO或基于成本CBO的原则，选择两个表中的一个作为驱动表，并指定其为外部表。
2） Oracle 优化器再将另外一个表指定为内部表。
3） Oracle从外部表中读取第一行,然后和内部表中的数据逐一进行对比，所有匹配的记录放在结果集中。
4） Oracle读取外部表中的第二行，再和内部表中的数据逐一进行对比，所有匹配的记录添加到结果集中。
5） 重复上述步骤，直到外部表中的所有纪录全部处理完。
6） 最后产生满足要求的结果集。
使用嵌套循环连接是一种从结果集中提取第一批记录最快速的方法。在驱动行源表(就是正在查找的记录，外部表)较小、或者内部行
源表已连接的列有惟一的索引或高度可选的非惟一索引时, 嵌套循环连接效果是比较理想的。嵌套循环连接比其他连接方法有优势,它
可以快速地从结果集中提取第一批记录,而不用等待整个结果集完全确定下来。这样,在理想情况下,终端用户就可以通过查询屏幕查看
第一批记录,而在同时读取其他记录。不管如何定义连接的条件或者模式,任何两个行记录源都可以使用嵌套循环连接,所以嵌套循环连
接是非常灵活的。
然而,
如果内部行源表(读取的第二张表)已连接的列上不包含索引,或者索引不是高度可选时,嵌套循环连接效率是很低的。
如果驱动表的记录非常庞大时,其他的连接方法可能更加有效。
可以通过在SQL语句中添加HINTS（use_nl）,强制ORACLE优化器产生嵌套循环连接的执行计划。
2 群集连接（CLUSTER JOIN）
那么ORACLE能够使用群集连接。处理的过程是：ORACLE从第一张行源表中读取第一行，然后在第二张行源表中使用CLUSTER索
引查找能够匹配到的纪录；继续上面的步骤处理行源表中的第二行，直到所有的记录全部处理完。
群集连接的效率极高，因为两个参加连接的行源表实际上处于同一个物理块上。但是，群集连接也有其限制，没有群集的两
个表不可能用群集连接。所以，群集连接实际上很少使用。
3 排序合并连接（SORT MERGE JOIN）
排序合并连接内部处理的流程：
1) 优化器判断第一个行源表是否已经排序，如果已经排序，则到第3步，否则到第2步。
2) 第一个源表排序
3) 优化器判断第二个行源表是否已经排序，如果已经排序，则到第5步，否则到第4步。
4) 第二个源表排序
5) 已经排过序的两个源表进行合并操作，并生成最终的结果集。
在缺乏数据的选择性或者可用的索引时,或者两个行源表都过于庞大(所选的数据超过表记录数的5%)时,排序合并连接将比嵌套
循环连更加高效。排列合并连接需要比较大的临时内存块,以用于排序，这将导致在临时表空间占用更多的内存和磁盘I/O。
可以通过在SQL语句中添加HINTS（use_merge）,强制ORACLE优化器产生排序合并连接的执行计划。
4 笛卡尔连接 (CARTESIAN JOIN)
笛卡尔连接是指在sql语句中没有写出表连接的条件，优化器把第一个表的每一条记录和第二个表的所有纪录相连接。如果第
一个表的纪录数为m, 第二个表的纪录数为m,则会产生m*n条纪录数。
由于笛卡尔连接会导致性能很差的SQL,因此一般也很少用到。
5 哈希连接(Hash Join)
Hash Join 概述
Hash join 算法的一个基本思想就是根据小的row sources(称作build input我们记较小的表为S ，较大的表为B)建立一个可以
存在于 hash area内存中的hash table ，然后用大的 row sources(称作probe input) 来探测前面所建的hash table。如果
hash area 内存不够大， hash table就无法完全存放在hash area内存中。针对这种情况，Oracle在连接键利用一个hash函数将
build input 和 probe input 分割成多个不相连的分区（分别记作 Si 和 Bi ),这个阶段叫做分区阶段；然后各自相应的分区，
即 Si 和 Bi 再做 Hash join ，这个阶段叫做 join 阶段。
如果在分区后，针对某个分区所建的hash table还是太大的话，oracle就采用nested-loops hash join. 所谓的nested-loops hash join就是对部分 Si 建立 hash table ，然后读取所有的 Bi 与所建的 hash table 做连接，然后再对剩余的 Si 建立 hash table ，再
将所有的 Bi 与所建的 hash table 做连接，直至所有的 Si 都连接完了。
Hash Join 算法有一个限制，就是它是在假设两张表在连接键上是均匀的，也就是说每个分区拥有差不多的数据。但是实际当中数据都是不
均匀的，为了很好地解决这个问题， oracle 引进了几种技术，位图向量过滤、角色互换、柱状图，这些术语的具体意义会在后面详细介绍。
Hash Join 原理
我们用一个例子来解释 Hash Join 算法的原理，以及上述所提到的术语。
考虑以下两个数据集。
S={1,1,1,3,3,4,4,4,4,5,8,8,8,8,10}
B={0,0,1,1,1,1,2,2,2,2,2,2,3,8,9,9,9,10,10,11}
oracle优化器根据统计信息,Hash Join 的第一步就是判定小表（即 build input ）是否能完全存放在 hash area 内存中。如果能完全存放在内存中，则在内存中建立 hash table ，这是最简单的 hash join 。
如果不能全部存放在内存中，则 build input 必须分区。分区的个数叫做 fan-out 。 Fan-out 是由 hash_area_size 和 cluster size 来决定的。其中 cluster size 等于 db_block_size * hash_multiblock_io_