Grace Hash Join

• Partitioning phase: We try to split R and S into partitions. Each partition has $R_i$ and $S_i$ (i.e. partition i of $R$ and partition i of $S$) and make sure either $R_i$ or $S_i\le B-2$ pages. If not, recursively do partition.
  • Make sure records with same hash value are in the same partition.
• Build & Probe Phase: Load the smaller partition into memory and build an in-memory hash table. Perform a Naive Hash Join with the larger partition in the pair.

I/O COST:

• First phase: read + write both relations
  • $2([R]+[S])$ I/Os
• Second phase: read both relations, forward output
  • $[R]+[S]$ I/Os
• Total cost of 2-pass hash join = $3([R]+[S])$