sql 三大物理连接

超、凢脫俗 2022-12-28 13:00 13阅读 0赞

### **排序合并连接** ###

排序合并连接（Sort Merge Join）是一种两个表在做表连接时用排序操作（Sort）和合并操作（Merge）来得到连接结果集的表连接方法。

如果两个表（这里将它们分别命名为表T1和表T2）在做表连接时使用的是排序合并连接，则会依次顺序执行如下步骤。

（1）首先以目标SQL中指定的谓词条件（如果有的话）去访问表T1，然后对访问结果按照表T1中的连接列来排序，排好序后的结果集我们记为结果集1。

（2）接着以目标SQL中指定的谓词条件（如果有的话）去访问表T2，然后对访问结果按照表T2中的连接列来排序，排好序后的结果集我们记为结果集2。

（3）最后对结果集1和结果集2执行合并操作，从中取出匹配记录来作为排序合并连接的最终执行结果。

我个人认为这个合并操作的具体执行步骤是这样的：首先遍历结果集1，即先取出结果集1中的第1条记录，然后去结果集2中按照连接条件判断是否存在匹配记录，然后再取出结果集1中的第2条记录，按照同样的连接条件再去结果集2中判断是否存在匹配的记录，直到最后遍历完结果集1中所有的记录。注意，这里去结果集2中判断是否存在匹配记录时会存在一个过滤的过程。因为结果集2已经按照表T2中的连接列排好序了，所以取出结果集1中的记录然后去找结果集2中的匹配记录时，只需要遍历结果集2中满足上述连接条件的那部分数据就可以了（这部分数据在结果集2中的存储位置肯定是在一起的），也就是说此时并不需要遍历结果集2中所有的记录，并且一旦在结果集2中找到匹配记录，就可以把该匹配记录从结果集2中删除，或者不删除但记录下其位置（这样下次再从结果集2中找匹配记录时就可以从这个位置开始了）。最后，结果集1和结果集2中所有的匹配结果就是上述排序合并连接的最终执行结果（注意，这个合并过程的具体执行步骤是我猜的，我不确定是否正确）。

对于排序合并连接的优缺点及适用场景，我们有如下总结。

通常情况下，排序合并连接的执行效率会远不如哈希连接，但前者的使用范围更广，因为哈希连接通常只能用于等值连接条件，而排序合并连接还能用于其他连接条件（例如<、<=、>、>=）。

通常情况下，排序合并连接并不适合OLTP类型的系统，其本质原因是因为对于OLTP类型的系统而言，排序是非常昂贵的操作，当然，如果能避免排序操作，那么即使是OLTP类型的系统，也还是可以使用排序合并连接的。比如两个表虽然是做排序合并连接，但实际上它们并不需要排序，因为这两个表在各自的连接列上都存在索引。

使用条件:排序合并连接比较适用于返回大数据量的结果,也比较 **适用于非等值连接的情况，比如** **>** **、>=** **、<=** **等情况下的连接** （哈希连接只适用于等值连接）

### **嵌套循环连接** ###

嵌套循环连接（Nested Loops Join）是一种两个表在做表连接时依靠两层嵌套循环（分别为外层循环和内层循环）来得到连接结果集的表连接方法。

如果两个表（这里将它们分别命名为表T1和表T2）在做表连接时使用的是嵌套循环连接，则Oracle会依次顺序执行如下步骤。

（1）首先，优化器会按照一定的规则来决定表T1和T2中谁是驱动表（外部表）、谁是被驱动表。驱动表用于外层循环，被驱动表用于内层循环。这里假设驱动表是T1，被驱动表是T2。

（2）接着以目标SQL中指定的谓词条件（如果有的话）去访问驱动表T1，访问驱动表T1后得到的结果集我们记为驱动结果集1。

（3）然后遍历驱动结果集1并同时遍历被驱动表T2（内部表），即先取出驱动结果集1中的第1条记录，接着遍历被驱动表T2并按照连接条件去判断T2中是否存在匹配的记录，然后再取出驱动结果集1中的第2条记录，按照同样的连接条件再去遍历被驱动表T2并判断T2中是否还存在匹配的记录，直到遍历完驱动结果集1中所有的记录为止。这里的外层循环是指遍历驱动结果集1所对应的循环，内层循环是指遍历被驱动表T2所对应的循环。显然，外层循环所对应的驱动结果集1有多少条记录，遍历被驱动表T2的内层循环就要做多少次，这就是所谓的"嵌套循环"的含义。

对于嵌套循环连接的优缺点及适用场景，我们有如下总结。

从上述嵌套循环连接的具体执行过程可以看出：如果驱动表所对应的驱动结果集的记录数较少，同时在被驱动表的连接列上又存在唯一性索引（或者在被驱动表的连接列上存在选择性很好的非唯一性索引），那么此时使用嵌套循环连接的执行效率就会非常高；但如果驱动表所对应的驱动结果集的记录数很多，即便在被驱动表的连接列上存在索引，此时使用嵌套循环连接的执行效率也不会高。

只要驱动结果集的记录数较少，那就具备了做嵌套循环连接的前提条件，而驱动结果集是在对驱动表应用了目标SQL中指定的谓词条件（如果有的话）后所得到的结果集，所以大表也可以作为嵌套循环连接的驱动表，关键看目标SQL中指定的谓词条件（如果有的话）能否将驱动结果集的数据量降下来。

嵌套循环连接有其他连接方法所没有的一个优点：嵌套循环连接可以实现快速响应，即它可以第一时间先返回已经连接过且满足连接条件的记录，而不必等待所有的连接操作全部做完后才返回连接结果。虽然排序合并连接和哈希连接也可以先返回已经连接过且满足连接条件的记录，而不必等待所有的连接操作都做完，但是它们并不是第一时间返回，因为排序合并连接要等到排完序后做合并操作时才能开始返回数据，而哈希连接则要等到驱动结果集所对应的Hash Table全部建完后才能开始返回数据。

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

### 哈希连接 ###

连接（join)是数据库表之间的常用操作，通过把多个表之间某列相等的元组提取出来组成新的表。两个表若是元组数目过多，逐个遍历开销就很大，哈希连接就是一种提高连接效率的方法。

哈希连接主要分为两个阶段：建立阶段（build phase)和探测阶段（probe phase)

**Bulid Phase**

选择一个表（一般情况下是较小的那个表，以减少建立哈希表的时间和空间），对其中每个元组上的连接属性（join attribute)采用哈希函数得到哈希值，从而建立一个哈希表。

**Probe Phase**

对另一个表，扫描它的每一行并计算连接属性的哈希值，与bulid phase建立的哈希表对比，若有落在同一个bucket的，如果满足连接谓词（predicate)则连接成新的表。

在内存足够大的情况下建立哈希表的过程时整个表都在内存中，完成连接操作后才放到磁盘里。但这个过程也会带来很多的I/O操作。

另一种哈希连接：**Grace hash join**

这个方法适合用于内存不足的情况，核心在于分块处理

第一阶段分块阶段(Partition Phase)：把每个关系（relation）分别用同一个哈希函数h(x)在连接属性上进行分块（partition）。分块后每个元组分配到对应的bucket，然后分别把这些buckets写到磁盘当中。