CMU 15445 10. 连接

为什么我们需要连接？

我们规范化关系数据库中的表，以避免不必要的信息重复。
我们使用join操作来重建原始元组而不会丢失任何信息。

不同算法的成本分析

image.png

下面一共会介绍5种连接算法。
分别是

• simple loop join
• block loop join
• index loop join
• sort-merge join
• hash join

simple loop join

image.png image.png

block loop join

优化1，读取整块，2变各读取整块后，开始循环这2个整块 然后JOIN。

image.png
image.png

利用全BUFFER 提速

我们假设有B个BUFFER， B-2个用来扫描外层表。一个扫描内层表，一个用来存储OUTPUT。

image.png
image.png

利用INDEX提速

image.png
Assume the cost of each index probe is some
constant C per tuple.
Cost: M + (m ∙ C)

Sort-Merge Join

分为2个阶段，

1. 使用外排序算法对2个TABLE做排序

2. 使用MERGE，找到MATCHING的元组

   
   image.png
   image.png
   image.png

什么时候使用SORT-MERGE JOIN比较好？

当一个或者2个TABLE已经按照JOIN KEY 排好序了。
输出必须要在JOIN KEY上排好序的。

Hash join

Hash Join 的思想就是2边都按JOIN KEY 做HASH，那么JOIN KEY相等的肯定在一个HASH分块里。

image.png
image.png
image.png image.png

总结

image.png