Module 4 · Query optimization

Episode 29 Join Ordering

10 min · SQL · Postgres

Title card of Episode 29: Join Ordering

▶ This video is coming to YouTube soon.

The same four-table query took 112 ms in the order we wrote it and 8 ms in the order Postgres chose. This episode shows why join order matters, counts how fast the search space explodes, runs System R's dynamic programme with interesting orders, compares left-deep and bushy trees, and proves each step on a real Postgres with join_collapse_limit, from_collapse_limit and geqo_threshold.

Chapters

  1. 0:00Intro
  2. 0:14Same 30 rows, 14× slower
  3. 0:38Same answer, very different work
  4. 1:34All 24 orders of four tables
  5. 2:15The search space explodes
  6. 2:56Dynamic programming: one best plan per subset
  7. 4:13The code: System R's dynamic programme
  8. 4:53Interesting orders: keep the sorted plan too
  9. 5:53Left-deep or bushy
  10. 6:37Where Postgres stops searching
  11. 7:16Proof: Postgres rewrites the join order
  12. 7:42Proof: join_collapse_limit = 1 keeps the written order
  13. 8:13Proof: the sorted plan wins under ORDER BY
  14. 8:35Trade-offs
  15. 9:15Recap
  16. 9:47Next: Reading EXPLAIN