[prev] 20 [next]

Hybrid Hash Join (cont)

Some observations:
  • with k partitions, each partition has expected size bR/k
  • holding m partitions in memory needs ceil(mbR/k) buffers
  • with k-m output buffers, must have ceil(mbR/k) + (k-m) + 1 = N
Other notes:
  • if N = bR+2, using block nested loop join is simpler
  • cost depends on N (but less than grace hash join)
Best-cost scenario:
  • m = 1,   k ≅ ceil(bR/N)    (satisfying above constraint)