Hash & Sort-Merge Joins

Joins in column stores follow the same algorithms as row stores, but vectorized:

Hash join:

Vectorized: hash whole vector at once, look up in batch, output matching pairs.

Sort-merge join:

• Sort both sides by join key.
• Walk both with two pointers.
• Output matches.

When inputs are already sorted (or partitioned), sort-merge wins (no build hash table).

Broadcast hash join:

• Build side small enough to fit in memory.
• Replicate build side to each worker.
• Each worker probes its partition independently.

Shuffle hash join:

• Both sides large.
• Hash-partition by join key.
• Same key ends up at same worker.
• Each worker does local hash join.

In Spark/Snowflake/BigQuery, the optimizer picks based on table sizes + statistics.

Vectorized hash table:

• Hash 1024 keys at once.
• Probe 1024 entries in parallel.
• Output mask of matches → materialize columns.

Late join: keep join keys cheap, defer heavy column materialization to after joining + filtering. Saves I/O.

Bloom filter joins: build side computes bloom of its join keys. Probe side filters out non-matches before shuffle. Reduces network traffic.

Modern OLAP engines have ~5-10 join algorithms. Picking is cost-based optimization.