Introduction

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.

Try It: Reorder the Joins

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">Four tables, joined left to right. Each join keeps only a fraction of the rows (its <b>selectivity</b>). Use the arrows to reorder the chain and watch the <b>estimated cost</b> change. Checking one order is instant — finding the cheapest is the hard part.</p>
<div id="chain" class="chain"></div>
<div class="cost">Estimated cost: <span id="cost">—</span></div>
<div class="status" id="status">Reorder the tables, then find the best.</div>
<div class="btns">
  <button id="find" type="button">Find the cheapest order</button>
  <button id="reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Join ordering: a query joins several tables. Joins are commutative/associative,
// so the same result can be computed in any order — but the cost differs wildly.
// We model a left-deep plan: join the first two tables, then fold in the next,
// and so on. The running intermediate size is multiplied by each new table size
// and the join's selectivity. Cost = sum of the intermediate sizes produced.
// Evaluating ONE order is a quick scan; finding the cheapest among all n! orders is NP-hard in general (Ibaraki & Kameda, 1984), so here we brute-force n=4.

// Each table: name + base row count. Selectivity of joining tables i and j
// (per matching key) is given in SEL[i][j]; an intermediate joined with a table
// uses the min selectivity over the tables already in the intermediate set.
const TABLES = [
  { id: 0, name: 'Customers', rows: 100000 },
  { id: 1, name: 'Orders',    rows: 500000 },
  { id: 2, name: 'Products',  rows: 2000 },
  { id: 3, name: 'Reviews',   rows: 800000 },
];
// Pairwise join selectivity (fraction of the cross-product that survives the join).
const SEL = [
  [1,    1e-4, 1,    1   ],  // Customers
  [1e-4, 1,    1,    1e-5],  // Orders
  [1,    1,    1,    5e-4],  // Products
  [1,    1e-5, 5e-4, 1   ],  // Reviews
];
let order = [0,1,2,3]; // current left-to-right join order

// Cost of a left-deep order: fold tables in, tracking the intermediate size.
// Joining the running set S with table t multiplies the size by t.rows and by
// the best (smallest) selectivity between t and any table already in S.
function planCost(ord){
  let size = TABLES[ord[0]].rows;
  let inSet = [ord[0]];
  let cost = 0;
  for(let i=1;i<ord.length;i++){
    const t = ord[i];
    let sel = 1;
    for(const s of inSet) sel = Math.min(sel, SEL[s][t]);
    size = size * TABLES[t].rows * sel;
    cost += size;          // cost of materializing this intermediate
    inSet.push(t);
  }
  return cost;
}
function fmt(n){
  if(n>=1e9) return i18nFmt('%v%B rows', { v: (n/1e9).toFixed(2) });
  if(n>=1e6) return i18nFmt('%v%M rows', { v: (n/1e6).toFixed(2) });
  if(n>=1e3) return i18nFmt('%v%K rows', { v: (n/1e3).toFixed(1) });
  return i18nFmt('%round% rows', { round: Math.round(n) });
}

function render(){
  const c = document.getElementById('chain'); c.innerHTML='';
  order.forEach((t,i)=>{
    if(i>0){ const j=document.createElement('span'); j.className='join'; j.textContent='⋈'; c.appendChild(j); }
    const node=document.createElement('div'); node.className='node';
    const box=document.createElement('div'); box.className='tbl';
    box.innerHTML = TABLES[t].name + '<small>'+fmt(TABLES[t].rows)+'</small>';
    const ar=document.createElement('div'); ar.className='arrows';
    const left=document.createElement('button'); left.textContent='◀'; left.disabled=(i===0);
    left.addEventListener('click',()=>{ [order[i-1],order[i]]=[order[i],order[i-1]]; render(); clearStatus(); });
    const right=document.createElement('button'); right.textContent='▶'; right.disabled=(i===order.length-1);
    right.addEventListener('click',()=>{ [order[i+1],order[i]]=[order[i],order[i+1]]; render(); clearStatus(); });
    ar.appendChild(left); ar.appendChild(right);
    node.appendChild(box); node.appendChild(ar); c.appendChild(node);
  });
  document.getElementById('cost').textContent = fmt(planCost(order));
}
function clearStatus(){ const s=document.getElementById('status'); s.textContent='Reorder the tables, then find the best.'; s.className='status'; }

// Brute force: try every permutation, keep the cheapest. 4! = 24 orders here.
function permutations(arr){
  if(arr.length<=1) return [arr];
  const out=[];
  arr.forEach((v,i)=>{ const rest=arr.slice(0,i).concat(arr.slice(i+1));
    for(const p of permutations(rest)) out.push([v,...p]); });
  return out;
}
function find(){
  let best=null, bestCost=Infinity, tried=0;
  for(const p of permutations([0,1,2,3])){ tried++;
    const c=planCost(p); if(c<bestCost){ bestCost=c; best=p; } }
  order = best; render();
  const s=document.getElementById('status');
  s.textContent=i18nFmt('Cheapest of %tried% orders: %fmt%.', { tried: tried, fmt: fmt(bestCost) });
  s.className='status ok';
  console.log('Best order:', best.map(t=>TABLES[t].name).join(' ⋈ '), '| cost', bestCost, '| tried', tried);
}
document.getElementById('find').addEventListener('click',find);
document.getElementById('reset').addEventListener('click',()=>{ order=[0,1,2,3]; render(); clearStatus(); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

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