表连接的原理

当一个查询请求涉及到数据库的多个表时，必须用一定的连接条件或连接谓词将这些表连接起来，才能提供用户需要的信息 。

常用的表连接方式：

a.    嵌套循环连接（Nested Loop ） b. 排序合并连接(Sort Merge) c. 哈希连接（Hash join ）

嵌套循环连接（ Nested Loop ）

代码如下：

	/*
 	* 嵌套循环连接（ Nested Loop ）
 	* tableA :驱动表 (小表) tableB 被驱动表  result结果
 	*/
	public void NestedLoop(List<A> tableA,List<B> tableB,List<Integer> result){
		for(A a :tableA){
			for(B b :tableB){
				if(a.getId().equals(b.getId())){
					result.add(a.getId());
				}
			}
		}
	}

 

 

嵌套循环连接的工作方式是这样的：

1 、Oracle 首先选择一张表作为连接的驱动表，这张表也称为外部表（Outer Table ）。由驱动表进行驱动连接的表或数据源称为内部表（Inner Table ）。

2 、提取驱动表中符合条件的记录，与被驱动表的连接列进行关联查询符合条件的记录。在这个过程中，Oracle 首先提取驱动表中符合条件的第一条记录，再与内部表的连接列进行关联查询相应的记录行。在关联查询的过程中，Oracle 会持续提取驱动表中其他符合条件的记录与内部表关联查询。这两个过程是并行进行的，因此嵌套循环连接返回前几条记录的速度是非常快的。在这里需要说明的是，由于Oracle 最小的IO 单位为单个数据块（BLOCK），因此在这个过程中Oracle 会首先提取驱动表中符合条件的单个数据块中的所有行，再与内部表进行关联连接查询的，然后提取下一个数据块中的记录持续地循环连接下去。当然，如果单行记录跨越多个数据块的话，就是一次单条记录进行关联查询的。

3 、嵌套循环连接里面存在着两个循环，一个是外部循环，提取驱动表中符合条件的每条记录。另外一个是内部循环，根据外循环中提取的每条记录对内部表进行连接查询相应的记录。由于这两个循环是嵌套进行的，故此种连接方法称为嵌套循环连接。

嵌套循环连接适用于查询的选择性强、约束性高并且仅返回小部分记录的结果集。通常要求驱动表的记录（符合条件的记录，通常通过高效的索引访问）较少，且被驱动表连接列有唯一索引或者选择性强的非唯一索引时，嵌套循环连接的效率是比较高的。

嵌套循环连接驱动表的选择也是连接中需要着重注意的一点，有一个常见的误区是驱动表要选择小表，其实这是不对的。假如有两张表A 、B 关联查询，A 表有1000000 条记录，B 表有10000 条记录，但是A 表过滤出来的记录只有10 条，这时候显然用A 表当做驱动表是比较合适的。因此驱动表是由过滤条件限制返回记录最少的那张表，而不是根据表的大小来选择的。

在外连接查询中，如果走嵌套循环连接的话，那么驱动表必然是没有符合条件关联的那张表，也就是 A left join B中的A。这是由于外连接需要提取可能另一张表没符合条件的记录，因此驱动表需要是那张我们要返回所有符合条件记录的表。

嵌套循环连接返回前几行的记录是非常快的，这是因为使用了嵌套循环后，不需要等到全部循环结束再返回结果集，而是不断地将查询出来的结果集返回。在这种情况下，终端用户将会快速地得到返回的首批记录，且同时等待Oracle 内部处理其他记录并返回。如果查询的驱动表的记录数非常多，或者被驱动表的连接列上无索引或索引不是高度可选的情况，嵌套循环连接的效率是非常低的。

 

排序合并连接(Sort Merge)

嵌套循环连接也就是双重FOR循环，对被驱动表（内层表）将重复扫描很多次。为了解决这个问题，可以使用排序合并连接。

/*
	 *  排序合并连接(Sort Merge) 
	 * tableA :表A tableB 表B  result结果
	 */
	public void SortMerge(List<A> tableA,List<B> tableB,List<Integer> result){
		Sort(tableA);
		Sort(tableB);
		for(int i = 0,j = 0;i < tableA.size()&&j < tableB.size();){
			if(tableA.get(i).getId() > tableB.get(j).getId()){
				j++;
			}else if(tableA.get(i).getId() < tableB.get(j).getId()){
				i++;
			}else{
				result.add(tableA.get(i).getId());
				i++;
				j++;
			}
		}
		
	}

 

 

 

由上面的算法可以看出，排序合并连接并没有驱动表和被驱动表的概念。两个互相连接的表按连接列的值先排序，排序完后形成的结果集再互相进行合并连接提取符合条件的记录。这样可以避免多次扫描表。可排序是在内存中进行的，所以排序合并连接需要占用内存，也就是ORALCE中的排序空间（PGA排序区）如果PGA中特定的排序大小（pga_aggregat_target:sort_area_size）不足以进行排序操作，也就是说需要排序分组的数据集合特别大的时候，Oracle需要调用Temp表空间的容量来进行操作。这也就是问题的所在。Temp表空间数据存储位于磁盘中，速度与内存相差很多。所以，当进行排序操作的数据集合很大，会出现性能急剧的下降可能。

在嵌套循环中，对连接列进行索引处理，可以很大程度上提升执行计划效率，减少随机读的数量。而排序合并连接却不能有效的利用索引，即使连接列上存在索引，一般也不会被采用。

总的来说，嵌套循环连接适用于较小的数据量的情况。而排序合并连接适用于较大数据量的情况，而当数据量很大时，排序合并连接会产生排序溢出（sort flow），导致硬盘排序，性能会急剧下降。

  

哈希连接（ Hash join ）

哈希连接类似代码如下：

/*
	 *  哈希连接（ Hash join ） 
	 * tableA :表A tableB 表B  result结果
	 */
	public void HashJoin(List<A> tableA,List<B> tableB,List<Integer> result){
		HashTable hashTable = Hash(tableA);
		Integer[] hashTable = new Integer[];
		for(A a:tableA){
			hashTable.add(Hash(a.getId()));
		}
		
		for(B b:tableB){
			if(hashTable[Hash(b.getId())]!=null){ 
				
			}
		}
	}

 

 

有上面的代码可以看出，哈希连接主要过程如下：

构建阶段：优化器首先选择一张小表做为驱动表，运用哈希函数对连接列进行计算产生一张哈希表。通常这个步骤是在内存（hash_area_size ）里面进行的，因此运算很快。

探测阶段：优化器对被驱动表的连接列运用同样的哈希函数计算得到的结果与前面形成的哈希表进行探测返回符合条件的记录。这个阶段中如果被驱动表的连接列的值没有与驱动表连接列的值相等的话，那么这些记录将会被丢弃

在大数据量时，排序合并连接会产生排序溢出。可是哈希连接只会用小表的连接列构建一个哈希表，所用内存不多，不会发生排序溢出。所以在大数据量时，采用哈希连接会更好。但由于哈希算法所特有的特点，哈希连接只适用于等值连接。