Introduction

You write a perfectly reasonable SQL query joining a few tables, and it runs in 5 milliseconds. A colleague writes a query that asks the same question and it takes 5 minutes. Same data, same answer — wildly different speed. What happened?

The database had to decide how to compute your query: which table to scan first, what order to join the others, which indexes to use. There are many possible execution plans for the same query, and they can differ in cost by a factor of a thousand or more. Picking a good one is the job of the query optimizer — and it's invisible, automatic, and crucial.

The heart of it is join ordering, and it's NP-hard: as you add tables, the number of possible orders explodes factorially. Every relational database — Postgres, MySQL, SQL Server — wrestles this hard problem millions of times a day, before you even see your results.

Order the Joins

Try it. The query joins four tables — Users, Orders, Products, Reviews — connected in a chain. Click them in the order you'd join them. The demo estimates the intermediate rows at each step and the total cost.

<p class="hint">Join four tables (a chain: Users–Orders–Products–Reviews). Click them in the order you'd join. The demo estimates intermediate rows per step and the total <b>cost</b>. Smart orders stay tiny; bad ones blow up.</p>
<div id="tables" class="tables"></div>
<div class="track-wrap"><span class="lab">Join order:</span><div id="track" class="track"></div></div>
<div id="steps" class="steps"></div>
<div class="meter">Total cost: <b id="cost" class="cost">—</b><span id="cmp" class="cmp"></span></div>
<div class="btns">
  <button id="best" type="button">Best plan</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.tables { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .9rem; }
.tbl { border: 2px solid #457b9d; border-radius: 8px; padding: .45rem .7rem; cursor: pointer; font: 700 13px system-ui; color: #1d3557; background: #fff; text-align: center; }
.tbl small { display: block; font-weight: 600; color: #888; font-size: .82em; }
.tbl.used { opacity: .35; cursor: default; }
.track-wrap { display: flex; align-items: center; gap: .5rem; margin-bottom: .6rem; flex-wrap: wrap; }
.lab { font: 600 13px system-ui; color: #555; }
.track { display: flex; gap: .3rem; flex-wrap: wrap; min-height: 2rem; }
.chip { font: 800 13px ui-monospace, monospace; background: #2a9d8f; color: #fff; border-radius: 6px; padding: .35rem .55rem; cursor: pointer; }
.steps { font: 600 12.5px ui-monospace, monospace; color: #444; line-height: 1.7; margin-bottom: .6rem; min-height: 1.5em; }
.meter { font-size: 1.05rem; margin-bottom: .6rem; }
.cost { color: #1d3557; font-family: ui-monospace, monospace; }
.cmp { margin-left: .6rem; font: 700 .9rem system-ui; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// SQL join-order optimization (NP-hard). Cost = sum of intermediate row counts
// of a left-deep plan. Join order can swing the cost by ~1000x; Best plan
// brute-forces the cheapest of the 4! orders.
const T = { Users: 1000, Orders: 5000, Products: 200, Reviews: 8000 };
const NAMES = ['Users', 'Orders', 'Products', 'Reviews'];
const EDGES = { 'Orders,Users': 0.001, 'Orders,Products': 0.005, 'Products,Reviews': 0.002 };
function sel(t, set) { let s = 1; for (const u of set) { const k = [t, u].sort().join(','); if (EDGES[k] !== undefined) s *= EDGES[k]; } return s; }
function plan(order) { let cur = T[order[0]], set = [order[0]], total = 0, steps = []; for (let i = 1; i < order.length; i++) { const t = order[i]; const sl = sel(t, set); cur = Math.max(1, Math.round(cur * T[t] * sl)); total += cur; steps.push({ join: order.slice(0, i + 1), rows: cur, cartesian: sl === 1 }); set.push(t); } return { total, steps }; }
function perms(a) { if (a.length <= 1) return [a]; const r = []; a.forEach((v, i) => perms(a.slice(0, i).concat(a.slice(i + 1))).forEach(p => r.push([v, ...p]))); return r; }

let order = [];
let BEST = Infinity, WORST = 0, BESTORDER = null;
for (const p of perms(NAMES)) { const c = plan(p).total; if (c < BEST) { BEST = c; BESTORDER = p; } if (c > WORST) WORST = c; }
const fmt = n => n.toLocaleString('en-US');

function render() {
  document.getElementById('tables').innerHTML = NAMES.map(n =>
    i18nFmt('<div class="tbl%v%" data-n="%n%">%n%<small>%fmt% rows</small></div>', { v: order.includes(n) ? ' used' : '', n: n, fmt: fmt(T[n]) })).join('');
  document.querySelectorAll('.tbl').forEach(el => el.addEventListener('click', () => { const n = el.dataset.n; if (!order.includes(n)) { order.push(n); render(); } }));
  document.getElementById('track').innerHTML = order.map((n, i) => '<span class="chip" data-i="' + i + '">' + n + '</span>').join('') || '<span style="color:#aaa;font-size:.85rem">pick tables
</span>';
  document.querySelectorAll('.chip').forEach(el => el.addEventListener('click', () => { order.splice(+el.dataset.i); render(); }));
  const stepsEl = document.getElementById('steps');
  if (order.length >= 2) {
    const pl = plan(order);
    stepsEl.innerHTML = pl.steps.map(s => i18nFmt('⋈ %s% → <b>%fmt%</b> rows%v%', { s: s.join.join(' ⋈ '), fmt: fmt(s.rows), v: s.cartesian ? ' <span style="color:#c0392b">⚠ cartesian!</span>' : '' })).join('<br>');
    document.getElementById('cost').textContent = fmt(pl.total);
    const cmp = document.getElementById('cmp');
    if (order.length === NAMES.length) {
      if (pl.total <= BEST) { cmp.style.color = '#0a7d33'; cmp.textContent = i18nFmt('✓ optimal! (worst order ≈ %fmt%)', { fmt: fmt(WORST) }); }
      else { cmp.style.color = '#b9770e'; cmp.textContent = i18nFmt('%round%× the best plan (%fmt%)', { round: Math.round(pl.total / BEST), fmt: fmt(BEST) }); }
    } else cmp.textContent = '';
  } else { stepsEl.innerHTML = ''; document.getElementById('cost').textContent = '—'; document.getElementById('cmp').textContent = ''; }
}

document.getElementById('best').addEventListener('click', () => { order = BESTORDER.slice(); render(); });
document.getElementById('reset').addEventListener('click', () => { order = []; render(); });
render();
Result
Console

Watch the cost swing enormously: join in a smart order and the intermediate results stay tiny; join in a bad order (or two unrelated tables first) and you get a giant cartesian blow-up. Hit Best plan to see the optimum — often hundreds of times cheaper than the worst. That gap is exactly what the optimizer exists to avoid.

The Hard Part

Under the hood, the optimizer is fighting a famously hard problem:

  • Checking a plan is easy. Estimate each join's output size and add up the work.
  • The orderings explode. For n tables there are factorially many join orders (and even more plan shapes) — brute force is hopeless beyond a handful of tables.
  • Join ordering is NP-hard. Finding the truly cheapest order is intractable in general — and the cost depends on cardinality estimates (how many rows each join produces), which are themselves only guesses.
  • Dynamic programming for small queries. The classic System R optimizer uses DP to find the optimal left-deep join order in O(2n)O(2^{n}) — exact and fast for, say, up to ~10–12 tables.
  • Heuristics and sampling for big ones. Beyond that, optimizers switch to greedy and randomized search (genetic, simulated annealing), guided by a cost model and statistics.
  • The frontier: learned optimizers. Machine-learning models now predict good plans and better cardinality estimates, a hot research area.

So the unsung optimizer in your database is solving an NP-hard problem on a deadline, every single query — and getting it right is the difference between a snappy app and a frozen one.

Where It Matters

This invisible decision runs the data layer of nearly everything:

  • Relational databases: Postgres, MySQL, SQL Server, Oracle — each ships a sophisticated optimizer.
  • Data warehouses and analytics: Snowflake, BigQuery, Spark SQL optimize huge multi-join queries.
  • Web and mobile apps: every page that hits a database depends on the optimizer for snappy responses.
  • Business intelligence: dashboards joining many tables live or die on plan quality.
  • Cost control: in cloud databases, a better plan is literally a smaller bill.

Decades of research go into these optimizers precisely because the underlying join-ordering problem is hard and the payoff is everywhere.

Conclusion

Query optimization is NP-hardness hiding in the most everyday place imaginable: the gap between a fast query and a slow one. The same answer, computed two ways, can differ by a thousandfold — and a piece of software you never think about makes that choice for you, in milliseconds, on every request.

It's a fitting near-final note for this site. The hardest problems aren't only in cryptography labs or quantum computers — one lives inside the database behind your favorite app, quietly running dynamic programming and cost models to dodge a factorial explosion. Most of the time it wins, and your page just loads. That quiet victory, repeated billions of times a day, is applied complexity theory at its most useful.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/sql-optimization/Content licensed under CC BY-NC 4.0.