2008年（239）
分类：
2008-06-17 23:46:39
在SQL语句的查询处理中，可能需要从多个表中返回数据，这就需要表的连接。在表的连接时，系统需要考虑的问题有：
（1）多个表之间，按照什么样的顺序执行表的连接。
（2）采用什么样的方式，实现两个表之间的连接。
例如，下列SQL语句返回部门中所有员工的帐户余额：
SELECT b.dept_company,a.empy_name,c.acct_balance
FROM employee a, department b, account c
WHERE a.dept_no=b.dept_no and a.empy_no=c.empy_no
在执行表的连接时，可以使用以下八种表连接顺序：
((employee,department),account)、(account,(employee,department))
((department,employee),account)、(account,(department,employee))
((employee,account),department)、(department,(employee,account))
((account,employee),department)、(department,(account,employee))
此外，两个表之间的连接可以使用以下的连接方式：嵌套循环连接、排序合并连接、散列连接。对这个SQL语句，优化器应当选用那种表连接顺序、表和表之间使用什么样的连接方式呢？
我们知道，一个SQL语句有很多种不同的执行方式，这些表连接顺序、连接方式的不同编排和组合，就包含在不同的执行方式中。优化器通过估算获取的最终执行计划，就给出了该SQL语句最合适的表连接顺序和连接方式。对两个表以上的表连接，由于要产生中间结果集，优化器在估算时还要考虑它所消耗的内存、磁盘空间资源。
下面我们将对表和表之间的连接方式进行简单介绍。
1. 嵌套循环连接
嵌套循环连接，由两个嵌套的循环语句组成。处于外层循环中的表称为外层表，处于内层循环中的表称为内层表。系统顺序地读取外层表中的每一条记录，将它和内层表中的每一条记录进行比较，如果满足条件就放入结果集。整个连接的处理过程见图5-2。
for 表1中的每一条记录 do
begin
for 表2中的每一条记录 do
begin
测试表1和表2当前的记录是否满足连接条件
如果满足，就加入结果集
end
end
图 5-2 嵌套循环连接
嵌套循环连接不要求表中存在索引，并且不管是什么条件，该算法都可以使用。然而嵌套循环连接算法的代价很大，因为该算法要逐一检查两个表中的每一条记录。对外层表中任一记录的处理，都要对内层表扫描一次。如果内层表能够存放在内存中，将极大地减少磁盘的操作次数。优化器在使用嵌套循环连接时，会考虑表中的记录数，将记录数较小的表作为内层表使用。
由于嵌套循环连接的处理效率比较低，人们已经对此算法进行了改进，这就是：块嵌套循环连接和索引嵌套循环连接。
2. 块嵌套循环连接
对于块嵌套循环连接，系统以块的方式而不是以记录的方式处理表的连接（所谓块，就是数据库系统的数据页，是对磁盘I/O操作的最小单位）。系统顺序地读取外层表中的每一个数据块，将块中每一条记录和外层表所有块中的每一条记录进行比较，如果满足条件就放入结果集。整个连接的处理过程见图5-3。
for 表1中的每一数据块 do
begin
for 表2中的每一数据块 do
begin
for 表1当前块中的每一条记录 do
begin
for 表2当前块中的每一条记录 do
begin
测试表1和表2当前的记录是否满足连接条件
如果满足，就加入结果集
end
end
end
end
图 5-3 块嵌套循环连接
在要连接的两个表都不能放入内存时，表连接的处理不可避免要不停地以块为单位进行磁盘的读写。使用块嵌套循环连接，将极大地减少对磁盘的I/O操作。
3. 索引嵌套循环连接
在嵌套循环连接中，如果内层表在连接属性（表的属性也就是表的字段）上存在索引，系统就可以使用此索引访问内层表，从而取消内层循环对内层表的扫描，这种方法就称为索引嵌套循环连接。
使用表上的索引进行嵌套循环连接，一般来说会好于表的扫描。优化器在优化处理时，如果选用了嵌套循环连接，一般会把连接属性上存在索引的表作为内层表来处理，从而可以提高SQL语句的处理性能。
如果内层表的连接属性上不存在索引，但是优化器经过估算后，发现在连接属性上建立临时索引，将会降低SQL语句的执行成本。在这种情况下，优化器会在该SQL语句的最终执行计划中，要求首先建立内层表连接属性上的索引，然后再进行索引嵌套循环连接。
4. 排序归并连接
将参与连接的两个表按照连接属性，分别在相同的方向上进行排序，然后将两个表排序后的记录从上到下，一一进行比较，将满足条件的记录存放到结果集中，这种连接方式就称为排序归并连接。
如果参与连接的表已经按照连接属性排序，则该表就不用排序。当两个表的连接属性上存在索引时，这些索引可能会在排序归并连接中被使用。
5. 散列连接
散列连接要使用散列函数。如果一个表中的记录与另一个表中的记录满足连接条件，那么它们在连接属性上有相同的取值、相同的散列值。基于此原理，散列连接的基本思想是使用散列函数，把两个表分别按照连接属性，划分成一系列有相同散列值的记录集合。然后把具有相同散列值的记录集合，进行排序归并连接，最后将所有的中间结果集进行合并，形成最后的结果集。
我们知道，对大数据量表的排序，由于无法将数据全部装入内存，不能在内存中完成排序操作，整个排序过程分阶段进行，需要磁盘空间存放排序的中间结果，降低了排序的效率。而且随着数据量的增长，排序的效率将大幅度下降。因此对大数据量表之间的连接，直接使用排序归并连接，处理的效率会很低。
相对于排序归并连接，散列连接首先将大数据量表划分成许多小表，这些小表的排序可以在内存中完成，然后再执行排序归并连接，其连接的效率会得到提高。因此散列连接适合于大数据量表之间的连接处理。
