一.连接算法
1.连接的基本概念
（1）内连接：只保留两张表之中能够匹配的内容
（2）外连接：即使一方没有数据，也保留该侧数据，用NULL填充
内连接：只取两边都能匹配上的部分。
左外连接：左表全部保留，右表匹配不上就补NULL。
右外连接：右表全部保留，左表匹配不上就补NULL。
全外连接：左右表都尽量保留，匹配不上的一边补NULL。
（3）连接基数：连接结果的行数可能远大于任意一张输入表。
如果某个键在A中出现3次，在B中出现4次，那么该键连接后会产生：
3 × 4 = 12 行2.常见算法
嵌套循环连接 索引嵌套循环连接 哈希连接 排序归并连接二.嵌套循环
1.简单嵌套循环
若R有M行，S有N行，则比较次数为O（MN）
2.页面嵌套循环：数据库通常按页面读写，而不是每次只处理一行。
（1）读取外表的一个页面；
（2）读取内表的所有页面；
（3）比较两个页面中的所有记录；
（4）对外表的下一个页面重复。
设外表有R个页面，内表S个页面，比较次数O（R+R*S）
3.块嵌套循环：
4.索引嵌套循环：按顺序逐行读取驱动表，每读一行，就去被驱动表的索引里查匹配，真正用到索引的是被驱动表
适用
一张表较小 另一张表在连接键上有索引三.哈希连接
1.基本思路：
对一张表建立哈希表 对另一张表进行查找（1）build阶段：对较小的关系R建立哈希表
R.key → R中的记录（2）probe阶段：扫描另一张表S
对S中的键计算哈希值；查找哈希表；找到匹配记录后输出连接结果。
2.为什么哈希连接需要选择build表
Build表必须建立哈希表，因此尽量选择较小的表：
小表 → Build 大表 → Probe为什么不把大表作为Build表？
需要更多内存；更容易溢写磁盘；哈希表构建成本更高；缓存效率更差。
3.内存不足时的grace hash join
（1）第一阶段：分区，使用相同的哈希函数，将R和S分别划分成多个磁盘分区
（2）第二阶段：逐分区连接 ，对每一对分区分别执行内存哈希连接
4.递归分区：如果某一个分区仍然太大无法进入内存，就需要继续分区
5.哈希连接的限制：最适用于等值连接，不直接适用于比较
四.排序归并连接
1.Sort-Merge Join通常也用于等值连接，但还能支持部分有序条件。
基本流程
- 分别对R和S按连接键排序；
- 使用两个指针扫描两个有序输入；
- 比较当前键值；
- 移动键值较小的一侧；
- 相等时输出匹配组合。
2.重复键在归并连接中的处理：排序归并连接遇到相同键时，需要保存或回溯同一键对应的记录组，然后输出笛卡尔积。
3.优点：
- 输入已经排序时非常高效；
- 可以边扫描边输出；
- 顺序访问磁盘，I/O友好；
- 可处理重复键；
- 适合后续还需要排序的算子；
- 某些非等值连接也可以利用有序性。
4.缺点：
- 如果输入没有排序，需要先执行外部排序；
- 排序可能产生大量临时I/O；
- 处理不等值条件时实现更复杂。
连接算法的对比
五.连接算法选择实例
1.小表连接大表，且大表有索引
适用：索引嵌套循环连接
2.两张大表，等值连接，没有索引
适用：哈希连接
3.两张表已经按连接键排序
适用：排序归并连接
4.连接条件是小于，大于
适用：哈希连接通常不适合，可能考虑其他方式
附
