CMU Database Systems — Lecture 13: Query Optimization (Selection)

Key takeaways

• Cost-based optimization is only as good as your cardinality estimates — and estimates lie because they assume uniform data and independence between predicates.
• The optimizer explores plans bottom-up (System R style): keep the cheapest plan per (relation set, join order), prune everything else. Bushy plans rarely win in practice for OLTP-ish workloads.
• Modern systems cache compiled plans; a bad estimate poisons the cache for hours. This is why plan invalidation on stats change exists.
• Pairs well with the DDIA replication chapters — same theme: the hard part is never the mechanism, it’s the assumptions underneath it.