[prev] 32 [next]

Simple Hash Join (cont)

Cost for simple hash join ...

Best case: all tuples of R fit in the hash table

  • Cost = bR + bS
  • Same page reads as block nested loop, but less join tests
Good case: refill hash table m times (where m ≥ ceil(bR / (N-3)) )
  • Cost = bR + m.bS
  • More page reads than block nested loop, but less join tests
Worst case: everything hashes to same page
  • Cost = bR + bR.bS