Join order optimization: dynamic programming over subsets
Why join order changes query cost by orders of magnitude, and how optimizers find the best order with dynamic programming over subsets (System R).
Part of Query optimization.
Read first
- Size estimation: how optimizers guess row counts
How query optimizers estimate result sizes (cardinality estimation) from T(R) and V(R,a): selectivity, the join-size formula, and when independence fails.
Read next
- Join algorithms: nested loop, hash join, sort-merge
How block nested loop, hash, Grace hash and sort-merge joins differ in page I/Os, and why memory M decides which one wins: once, 3 trips, or up to M² pages.