[prev] 16 [next]

Hybrid Hash Join

A variant of grace join if we have √bR < N < bR+2
  • create k≪N partitions,  m in memory,  k-m on disk
  • buffers: 1 input, k-m output, p = N-(k-m)-1 in-memory partitions
When we come to scan and partition S relation
  • any tuple with hash in range 0..m-1 can be resolved
  • 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 m (memory) + k (disk) partitions