为什么我们需要连接？
我们规范化关系数据库中的表，以避免不必要的信息重复。
我们使用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个阶段，
- 使用外排序算法对2个TABLE做排序
-
使用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
