Module 3 · Query execution

Episode 23 Joins II: Sort-Merge and Hash

10 min · SQL · Postgres

Title card of Episode 23: Joins II: Sort-Merge and Hash

▶ This video is coming to YouTube soon.

How does a database join 100,000 orders to 10,000 customers without a billion comparisons? We animate sort-merge join (with mark and restore for duplicate keys), hash join's build and probe, and the Grace hash join that partitions to disk at 3(M + N) I/O, then check it all in Postgres: Batches: 1, Batches: 8 at 64 kB, and two merge joins.

Chapters

  1. 0:00Intro
  2. 0:15A billion pairs, or 735 pages
  3. 0:32Why comparing pairs doesn't scale
  4. 1:11Sort-merge: sort, then one pass
  5. 2:22Duplicates on both sides: mark and restore
  6. 3:15The code: merge join
  7. 3:46Hash join: build, then probe
  8. 5:00The code: hash join
  9. 5:28Too big for memory: partition both inputs
  10. 6:31Then join each pair of partitions
  11. 7:12Proof: hash and merge joins in Postgres
  12. 8:51Trade-offs
  13. 9:21Recap
  14. 9:52Next: Aggregation