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