You write what you want; the database decides how to get it. The same four-table join can run in 210 units or 1200 — a 5.7× gap that turns on nothing but the order the tables are joined. Selinger’s System R optimizer searches that space by dynamic programming over subsets and returns the cheapest plan. Down the center, data flows: the query goes in, the optimizer chooses, the plan comes out. The blue team builds and defends it; the red team tries to break it.
source Selinger, Astrahan, Chamberlin, Lorie & Price, Access Path Selection in a Relational Database Management System (1979), ACM SIGMOD, pp.23–34 — DOI 10.1145/582095.582099. Rendered, not quoted.
A join result’s estimated size is the product of the base rows times the selectivity of every predicate inside the set:
card(S) = ∏r∈S rows(r) · ∏edge(i,j)⊂S sel(i,j)
Cost is output rows × per-row cost (here per-row = 1), summed over every join. The optimum obeys a recurrence over subsets — a left-deep plan for S is some cheapest plan for S minus one relation, then that relation joined last:
best(S) = card(S) + minr∈S best(S−r), best({r})=0
Live pairwise join sizes for the current query — note the two small pairs and the huge cross products:
| pair | rows | pair | rows |
|---|
Selinger’s move is the dynamic programming applied to join order: reuse the best plan for each subset instead of re-deriving it inside every full ordering. That collapses n! orderings into 2n subproblems.
It is the reason SQL is declarative. You never write the join order; the optimizer’s DP chooses it from statistics. Held & Karp built the same subset-DP for the travelling salesman in 1962 — each sphere is the next one’s premise.
The blue team’s live check: run the optimizer, then brute-force all 24 orders, and confirm the optimizer’s cost equals the true minimum. If red swaps the DP for greedy, the two disagree and this badge turns red.
Four tables, joined along a chain — a declarative request that says nothing about order:
| table | rows | predicate | selectivity |
|---|---|---|---|
| A | 1000 | A.x = B.x | 1/100 |
| B | 10 | B.y = C.y | 1/100 |
| C | 1000 | C.z = D.z | 1/100 |
| D | 10 | — | — |
The join graph is a chain A—B—C—D. Every join order returns the same rows; only the intermediate sizes — and the cost — differ. That is what you feed the panel below.
DP: the minimum-cost left-deep order by dynamic programming over subsets.
The chosen plan’s cost is recomputed live from the cost model — never looked up.
| step: join | set | rows | running cost |
|---|
Live DP table — best cost for every subset of size ≥2 (the 11 subproblems the DP solves once each):
| subset | card | best cost | subset | card | best cost |
|---|
What the machine proves, exactly: the minimum-cost left-deep plan is (((B⋈C)⋈D)⋈A) at cost 210 — matched by brute force over all 24 orders. The naive textual order (((A⋈B)⋈C)⋈D) costs 1200, and so does greedy: both build a 1000-row intermediate {A,B,C} where the optimum builds a 10-row {B,C,D}.
The blue team’s witness (left) confirms 210 against brute force live; the red team (right) tries to make the optimizer settle for 1200.
And the DP is exponential: 2n subsets, and Selinger only keeps left-deep, cross-product-pruned plans — bushy trees that can win are never seen. Past ~10–15 relations the DP is abandoned for heuristics (Postgres GEQO, genetic search) — exactly the greedy shortcut the tamper installs. “Optimal” means optimal for the cost model, not fastest on the clock.
“The optimizer finds the fastest plan.” Cut. It finds the minimum-estimated-cost plan. With wrong statistics the estimate and the wall-clock diverge; it is optimal against its model, not reality.
“Dynamic programming makes optimization cheap.” Cut. DP is 2n — only cheap relative to n! and only tractable for a handful of relations.
“Greedy join ordering is good enough.” Kept, corrected. Fast and often fine — but provably suboptimal: on the panel’s query it returns 1200 where the optimum is 210. That is the tamper.
“System R enumerated every plan.” Cut. It pruned cross products and kept only the cheapest plan per subset (and per interesting sort order) — the DP prune, not exhaustion.
The red team’s move: replace the dynamic program with a greedy join order — always join the next-cheapest pair. On this query greedy chooses A⋈B first and gets trapped in the 1000-row intermediate. The witness (window 7) is watching.
Swap in greedy and the optimizer returns a plan costing 1200 — the witness brute-forces all 24 orders, finds the true minimum is 210, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.