Join algorithm

  • Simple Nested Loop Join
  • Block Nested Loop Join
  • Index Nested Loop Join
  • Sort-Merge Join
  • Hash Join

下面以这两张表为例

Simple Nested Loop Join

即简单的双重循环。对每一个外层table中的tuple都要scan一遍内层table

Cost: M + (m*N)

Block Nested Loop Join

对上面的算法做了简单的优化,从tuple扩大到block。也就是对每一个外层table的block都要scan一遍内层table。减少了一些io次数

Cost: M + (M·N)

若memory比较大,其实可以先一次性将B-2个block都读进来,剩下两个block,一个用来scan内层表,另一个用来join。这样又大幅减少io。

Index Nested Loop Join

同样是nested loop的优化,上面两个算法,在做内循环的时候都是通过顺序scan来查找match。如果有index的话,可以直接通过index来查找。

Cost: M + (m·C)

C代表index查找的代价。

Sort-Merge Join

这个算法核心思想和归并排序类似。分两步,先排序再合并。

  1. 根据join的key对两个表排序(sort phase)
  2. 通过两个指针索引两张表,都只扫一遍,遇到相同的key则输出,算法类似归并排序的归并阶段(merge phase)

Cost: M + N + (sort cost)

但是要是两张表有很多相同的key,重复的key在merge的时候会变成nested loop join。不过这种情况比较少。

这个算法比较时候有一张表或者两张都已经有序的情况。

Hash Join

分为两种情况。

  • basic hash join 整个table可以fit进memory
  • Grace Hash Join 内存不够,table不能fit进memory

hash join 只能在等值join的情况下使用

basic hash join

核心思想也较为简单,就是通过对两张表hash以后,比较相同值的tuple进行连接。

  1. 先使用一个较小的表,扫描一遍,建立hash table (build phase)
  2. 扫描另一个表,使用相同的hash函数,定位到相同的bucket,进行match比较 (probe phase)

注意若hash冲突过于严重,就又变成nested loop join了

Grace Hash Join

当memory不够大时,则需要将table分片,分到足够小能塞进内存,再在内存中使用basic hash join或者其他join算法。

  1. 采用同一个hash函数,对两张表进行hash计算且分片输出 (build phase)
  2. 对于相应分片的内容,已经可以fit入内存,即可直接用上述的join算法进行输出 (probe phase)

若单个分片还是不能塞入内存,可以递归的换一个hash函数继续分片。

Cost of hash join is 3(M + N)

  • Partitioning phase 2(M + N) 读一遍,写一遍所以乘2
  • Probing Phase: M + N

Summary