Module 3 · Query execution

Episode 22 Joins I: Nested Loops

8 min · SQL · Postgres

Title card of Episode 22: Joins I: Nested Loops

▶ This video is coming to YouTube soon.

A nested loop join of our orders and customers costs 8,400,651 page reads done naively and 735 done well. This episode animates simple, block and index nested loops, derives their I/O formulas, picks the outer table, and checks every formula against EXPLAIN (ANALYZE, BUFFERS) in Postgres, including its unique-inner shortcut, Materialize and Memoize.

Chapters

  1. 0:00Intro
  2. 0:13Same join, very different bills
  3. 0:30Simple nested loop: the inner, once per row
  4. 1:22Block nested loop: once per page, or per block
  5. 2:24Index nested loop: probe, don't scan
  6. 3:12Which table goes outside?
  7. 4:00The code: rows, then pages
  8. 4:25The code: index nested loop
  9. 4:39Proof: the textbook loop in Postgres
  10. 5:15Proof: where Postgres beats the textbook
  11. 5:54Proof: index probes, and Memoize
  12. 6:30Trade-offs
  13. 7:05Recap
  14. 7:34Next: Joins II: Sort-Merge and Hash