Join Ordering

You write a tidy SQL query: join Customers to Orders to Products to Reviews, add a filter, ask for a result. To you it reads as one sentence. To the database it is a question with a thousand answers, because joins can be performed in any order — and the order changes everything.

Join two small tables first and you carry a tiny intermediate result through the rest of the work. Join two huge tables first and you build a monster that every later step has to drag along. Same answer at the end, wildly different cost in between — often a difference of thousands of times in time and memory.

Deciding the cheapest order is the single most important job of the query optimizer, the piece of every database that turns your SQL into an actual plan. And it turns out that finding the truly cheapest order is one of the hard problems of computer science.

Here is a query over four tables. Each table has a size, and each join only keeps a fraction of the rows (its selectivity). Drag the tables to choose the order in which they get joined, left to right, and watch the estimated cost update live.

<p class="hint">{{hint}}</p>
<div id="chain" class="chain"></div>
<div class="cost">{{estimated_cost}} <span id="cost">—</span></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</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; }
.chain { display: flex; flex-wrap: wrap; align-items: center; gap: .35rem; margin: .5rem 0; }
.node { display: flex; flex-direction: column; align-items: center; gap: .25rem; }
.tbl { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; border-radius: 8px;
       padding: .4rem .6rem; font-weight: 700; min-width: 92px; text-align: center; }
.tbl small { display: block; font-weight: 500; color: #5a7088; font-size: .72rem; }
.arrows { display: flex; gap: .2rem; }
.arrows button { font: 700 12px system-ui; padding: .1rem .4rem; border: 1px solid #1d3557;
                 background: #fff; color: #1d3557; border-radius: 6px; cursor: pointer; min-width: 0; }
.join { color: #adb1b8; font-size: 1.3rem; padding: 0 .1rem; }
.cost { font-size: 1.15rem; font-weight: 700; margin: .6rem 0 .2rem; }
.cost span { color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.3em; margin: .2rem 0 .6rem; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice how violently the number moves. Putting the most selective joins first keeps the intermediate results tiny; getting it wrong builds a huge intermediate table that every later join must process. Press Find the cheapest order and the optimizer tries every ordering and reports the best one — easy here with four tables, hopeless once there are twenty.

How hard is it to find the cheapest order? Not running the query — choosing the plan.

• Evaluating one order is cheap: multiply sizes and selectivities down the chain to estimate its cost.
• Counting the orders is the problem. With n tables there are already n! ways to line them up, and once you allow the joins to be grouped into different tree shapes (so-called bushy plans) the count grows even faster — into the Catalan-number range. Twelve tables already give billions of plans.
• It's NP-hard. In 1984 Ibaraki and Kameda proved that finding an optimal join order is NP-hard in general; even nice special cases stay intractable. There is no known way to always find the cheapest plan without, in the worst case, searching an exponential number of them.
• So databases don't insist on optimal. They use dynamic programming (the classic System R approach) to handle a dozen or so tables exactly, then switch to greedy and randomized heuristics for bigger queries, accepting a good plan instead of the best one.

That is the punchline: the moment your query touches enough tables, the optimizer stops searching for the perfect order and starts gambling intelligently. Like the traveling salesman, join ordering is a search over an exploding space of orderings — and like SAT, nobody knows a shortcut that always wins.

"Find the cheapest order to combine these things" is everywhere data lives, and join ordering is where you meet it most directly:

• Every relational database: PostgreSQL, Oracle, SQL Server and MySQL all spend real effort on join ordering before they run a single byte of your query.
• Analytics and data warehouses: a dashboard joining a dozen fact and dimension tables lives or dies by the plan — the difference between a one-second refresh and a timeout.
• Cardinality estimation: the optimizer must guess how many rows each join produces, and bad guesses lead to bad orders. This estimation is famously the weakest link in real systems.
• ORMs and query builders: the SQL your framework generates still gets ordered by the database, which is why an innocent-looking change to a query can suddenly make it slow.

Understand join ordering and you understand why two queries that return the same answer can differ by a factor of a thousand — and why P vs NP quietly shapes the speed of the software you use every day.

Join ordering hides a quiet truth: the same query, answered in different orders, can cost a second or an hour. Estimating one order's cost is instant; finding the cheapest among the factorially many is NP-hard, proven impossible to always do quickly (Ibaraki & Kameda, 1984) unless P equals NP.

So the next time a database returns your result in the blink of an eye, give a little credit to the optimizer that searched a vast space of plans and made a smart bet. It almost certainly did not find the perfect order — but it dodged the disastrous ones, and that is the best anyone knows how to do. Behind the friendly word JOIN sits a genuine instance of P vs NP.