读《DB2数据库性能调整和优化》札记--join的几种方式

weiliwei

　　以下是部分引用《DB2数据库性能调整和优化》,对于oracle也是这三种方式，这三种方式出现在执行计划中，因此十分有必要搞清楚内在算法原理。
　　对于多表的join一般是采取先join2张表，然后在join下一张表。
　　1、NestLoops
　　相当于2个循环，通常是在有索引时进行。
在嵌套循环连接中，将扫描第一个(或外部)表，以查找满足查询规则的行。对于在外部表中找到的每一行，数据库服务器将在第二个(或内部)表中搜索其相应的行。是通过索引扫描还是通过表扫描来访问外部表则取决于该表。如果有过滤条件，数据库服务器首先会应用它们。（也就是说where或者on条件和join方式谁先执行不一定，如果是where后执行那么执行filter操作，如果先where那么是带条件的结果集去join）如果内部表没有索引，那么数据库服务器就会将在表上构建索引的成本与连续扫描的成本进行比较（也就是索引不见得是成本低），然后选择成本最低的那一种方法。总成本取决于连接列上是否有索引。如果连接列上有一个索引，那么其成本会相当低；否则，数据库服务器就必须对所有表(外部和内部表)执行表扫描。
　　2、MergeJoin
　　2个表都将相同的项进行分组，然后比对，扫描将跳跃进行，虽然相同项不必扫描2次了但是因为有排序所以成本很高
　　 
当连接表的连接列上没有可用索引时，通常使用该连接方法。连接开始之前，如果有过滤条件，那么数据库服务器首先会应用它们，然后对连接列上每个表中的行进行分类。一旦实现了对行的分类，连接两个表的算法就十分容易：数据库服务器仅仅连续地读取两个已分类表，并合并所有相匹配的行。因为该方法在进行表连接之前，必须将所有的连接表分类，所以其成本通常极其高。
 
下面是我结合其他资料，所理解的MergeJoin的过程，请大家批评指正，仿照了《HTML渲染过程》博客的风格，呵呵。具体标题忘了，
 
 

 
 
　　    先对2表分别进行排序（正序），然后分别取出2表中的一个，两者比较，淘汰其中小的（因为是正序，小的不可能有匹配项），然后以大的为标准继续向下搜索，所以基准项会在两张表轮替。这是示意图。 
　　3、HashJoin
　　先扫描小表在内存中构建出出hash值，然后对大表进行扫描。
当一个或多个连接表上没有索引时，或者当数据库服务器必须从所有连接表中读取大量行时，就使用这种方法。在该方法中，需要扫描其中的一个表，通常扫描较小的那个表，用它在内存中创建一个哈希表。通过哈希函数，将具有相同哈希值的行放在一个内存中。在扫描完第一个表并将它放在哈希表中之后，就扫描第二个表，并在哈希表中查找该表中的每一行，看是否可以进行连接。如果连接中有更多表，那么数据库服务器将对每个连接表执行相同的操作。
哈希连接包含两个动作：构建哈希(或者是我们所称的构建阶段)，以及探测哈希表(或探测阶段)。在构建阶段，数据库服务器读取一个表，并在应用所有现有过滤条件之后，在内存中创建一个哈希表。可以在概念上将哈希表认为是一系列的内存bucket，每个bucket所拥有的地址是通过应用哈希函数从键值导出的。数据库服务器不会在特定的哈希bucket中对键进行分类。在探测阶段，数据库服务器将读取连接中的其他表，如果存在连接谓词，就应用它们。在满足连接谓词限定条件的每个行中，数据库服务器将对键应用哈希函数，并探测哈希表以查找匹配的键值。哈希连接通常比分类合并连接快，因为它没有涉及分类操作。