Hash Join

Naive Hash Join

Naive Hash Join

Naive Hash Join performs an in-memory hash table build and then join.

Prerequisite: Relation $R$ can fit into memory (that is, having $R\text{ being }\le B-2\text{ pages big}$). And this often not going to be possible, so solution is Grace Hash Join.

It’s basic idea is that we read all pages of relation $R$, building an in-memory hash table, and then read in each records of $S$ to look it up in $R^{\prime }s$ table.

Link to original

Grace Hash Join

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])$

Link to original