Hybrid Hash Join
A variant of grace hash join if we have √bR < N < bR+2
- create k≪N partitions, 1 in memory, k-1 on disk
- buffers: 1 input, k-1 output, p = N-k-2 for in-memory partition
When we come to scan and partition S relation
- any tuple with hash 0 can be resolved (using in-memory partition)
- other tuples are written to one of k partition files for S
Final phase is same as grace join, but with only k partitions.
Comparison:
- grace hash join creates N-1 partitions on disk
- hybrid hash join creates 1 (memory) + k-1 (disk) partitions
|