Query Optimizer: Join-Order Cost Search

Query Size

Tables in the join 4

Join Cost Model

Plan Shown

Result

(T0 ⋈ T1)

Optimal cost

—

Naive cost

—

Speedup

—

Result rows

—

DP subproblems

—

Left-deep orders

—

Tables in this query

How it works

A SQL engine's cost-based optimizer decides the join order before running a multi-table query — the result is the same set of rows however the tables are joined, but the cost can differ by orders of magnitude. For n tables there are up to n! left-deep orderings (and even more bushy ones), so brute force is impossible past a handful of tables.

The classic fix (System R, Selinger 1979 — still the core of PostgreSQL/MySQL/Oracle planners) is dynamic programming over subsets of tables:

cost({t})     = scan_cost(t) = rows(t)
cost(S)       = min over T⊂S, T≠∅,S of
                  cost(T) + cost(S\T) + joinCost(T, S\T)
rows(T ⋈ U)   = rows(T) × rows(U) × selectivity(T,U)

nested loop:  joinCost = rows(outer) × rows(inner)
hash join:    joinCost = rows(left) + rows(right)

Every non-trivial subset of tables is solved once and cached — that's the "DP subproblems" count, roughly 2ⁿ instead of n! orderings.
Nested Loop punishes joining two large tables directly — the optimizer routes through small intermediate results first. Hash Join is closer to linear, so join order matters less but is still not free.
Naive Left-Deep just joins the tables in the order they were typed in the query — the gap between it and the optimizer's plan is exactly the win a real cost-based optimizer buys you.
Past ~12–15 tables even 2ⁿ subsets get expensive — real databases fall back to greedy or genetic search (e.g. Postgres's join_collapse_limit / GEQO) beyond a threshold.

Drag to orbit · leaves = tables · height = join order

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.