Introduction

Every time you run a SQL query, the database does something remarkable before it touches a single row: it plans the query. It decides which table to scan first, which indexes to use, and in what order to join the tables. These choices can make a query run in milliseconds or hours — and they all depend on a single, surprisingly fragile question: how many rows will this step produce?

That count is called the cardinality of an intermediate result. Estimating it accurately is the job of the cardinality estimator, a component that every relational database has had since the 1970s. The first serious version appeared in IBM's System R (Selinger et al., 1979), and the core ideas — histograms and independence assumptions — have barely changed since.

The problem is that accurate cardinality estimation is open and hard. Not open in the sense that researchers haven't tried — thousands of papers have been written — but open in the sense that no system reliably gets it right. Errors compound exponentially through joins, turning a 2×2\times mistake into a 106×10^6\times catastrophe by the fifth table. This is the quiet crisis at the heart of every database engine.

Watch the Error Cascade

The demo below lets you build a chain of joins and see the gap between what the optimizer estimates and what the query would actually return. Each join multiplies the previous result by a selectivity factor — the optimizer assumes independence, which is almost never true in real data.

<!-- Cardinality estimation demo: compare true vs estimated row counts through join chains -->
<div class="panel">
  <div class="controls">
    <label class="ctrl-label">
      Number of joins:
      <input type="range" id="numJoins" min="1" max="8" value="4" />
      <span id="joinsVal">4</span>
    </label>
    <label class="ctrl-label">
      True selectivity:
      <input type="range" id="trueSel" min="1" max="50" value="10" />
      <span id="trueSelVal">0.10</span>
    </label>
    <label class="ctrl-label">
      Estimated selectivity:
      <input type="range" id="estSel" min="1" max="50" value="15" />
      <span id="estSelVal">0.15</span>
    </label>
    <button id="btnReset" type="button" class="ghost">Reset</button>
  </div>
  <div id="chartWrap" class="chart-wrap" aria-label="Bar chart comparing true versus estimated row counts per join"></div>
  <div id="summary" class="summary"></div>
</div>

/* Demo styles — bar chart, controls, summary panel */
*, *::before, *::after { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.panel { display: flex; flex-direction: column; gap: .75rem; }
.controls { display: flex; flex-direction: column; gap: .4rem; }
.ctrl-label { display: flex; align-items: center; gap: .5rem; font-size: .85rem; flex-wrap: wrap; }
.ctrl-label input[type=range] { flex: 1; min-width: 120px; max-width: 220px; }
.ctrl-label span { font-variant-numeric: tabular-nums; min-width: 3.5ch; font-weight: 600; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; align-self: flex-start; }
.chart-wrap { width: 100%; overflow-x: auto; }
.chart-wrap svg { display: block; }
.summary { font-size: .9rem; line-height: 1.55; background: #f3f6f9;
           border-left: 3px solid #1d3557; padding: .5rem .75rem; border-radius: 0 6px 6px 0; }
.summary .err { color: #c92f3c; font-weight: 700; }
.summary .ok { color: #0a7d33; font-weight: 700; }
.bar-true { fill: #1d3557; }
.bar-est  { fill: #e63946; opacity: .75; }
text.axis-label { font: 11px system-ui; fill: #555; }
text.bar-val    { font: 10px ui-monospace, monospace; fill: #333; }
text.legend-txt { font: 12px system-ui; fill: #333; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Cardinality estimation demo: the optimizer starts from BASE_ROWS and applies
// a selectivity factor at each join. The true selectivity and the estimated
// selectivity differ, so errors compound with each join.

const BASE_ROWS = 1000000; // starting table size (1 million rows)

const slJoins  = document.getElementById('numJoins');
const slTrue   = document.getElementById('trueSel');
const slEst    = document.getElementById('estSel');
const spJoins  = document.getElementById('joinsVal');
const spTrue   = document.getElementById('trueSelVal');
const spEst    = document.getElementById('estSelVal');
const divChart = document.getElementById('chartWrap');
const divSum   = document.getElementById('summary');

function fmt2(n) {
  // format large numbers as K / M for readability
  if (n >= 1e6) return (n / 1e6).toFixed(2) + 'M';
  if (n >= 1e3) return (n / 1e3).toFixed(1) + 'K';
  return Math.round(n).toString();
}

function build() {
  const k    = parseInt(slJoins.value, 10);
  const ts   = parseInt(slTrue.value, 10)  / 100;
  const es   = parseInt(slEst.value,  10)  / 100;

  spJoins.textContent = k;
  spTrue.textContent  = ts.toFixed(2);
  spEst.textContent   = es.toFixed(2);

  // apply true and estimated selectivities step by step through each join
  const trueRows = [];
  const estRows  = [];
  let tCur = BASE_ROWS;
  let eCur = BASE_ROWS;
  for (let i = 1; i <= k; i++) {
    tCur = Math.max(1, Math.round(tCur * ts));
    eCur = Math.max(1, Math.round(eCur * es));
    trueRows.push(tCur);
    estRows.push(eCur);
  }

  // build an SVG bar chart on a log scale so small values remain visible
  const W = 520, H = 220, PAD = { t: 18, b: 40, l: 56, r: 10 };
  const innerW = W - PAD.l - PAD.r;
  const innerH = H - PAD.t - PAD.b;

  const allVals = [...trueRows, ...estRows];
  const maxVal  = Math.max(...allVals, 1);

  const barW    = Math.floor(innerW / k / 2.4);
  const gap     = Math.floor(innerW / k);
  const yScale  = (v) => innerH - (Math.log1p(v) / Math.log1p(maxVal)) * innerH;

  let svgInner = '';

  // horizontal axis baseline
  svgInner += `<line x1="0" y1="${innerH}" x2="${innerW}" y2="${innerH}" stroke="#ccc" stroke-width="1"/>`;

  for (let i = 0; i < k; i++) {
    const cx = Math.round((i + 0.5) * gap);
    const yT = yScale(trueRows[i]);
    const yE = yScale(estRows[i]);
    const bw = barW;

    // true result bar (dark blue)
    svgInner += `<rect class="bar-true" x="${cx - bw - 1}" y="${yT}" width="${bw}" height="${innerH - yT}" rx="2"/>`;
    svgInner += `<text class="bar-val" x="${cx - bw/2 - 1}" y="${yT - 3}" text-anchor="middle">${fmt2(trueRows[i])}</text>`;

    // estimated result bar (red, semi-transparent)
    svgInner += `<rect class="bar-est" x="${cx + 1}" y="${yE}" width="${bw}" height="${innerH - yE}" rx="2"/>`;
    svgInner += `<text class="bar-val" x="${cx + bw/2 + 1}" y="${yE - 3}" text-anchor="middle">${fmt2(estRows[i])}</text>`;

    // join label below each group
    svgInner += `<text class="axis-label" x="${cx}" y="${innerH + 14}" text-anchor="middle">J${i + 1}</text>`;
  }

  // legend top-right
  svgInner += `<rect class="bar-true" x="${innerW - 140}" y="0" width="10" height="10" rx="1"/>`;
  svgInner += `<text class="legend-txt" x="${innerW - 126}" y="9">True rows</text>`;
  svgInner += `<rect class="bar-est" x="${innerW - 140}" y="16" width="10" height="10" rx="1"/>`;
  svgInner += `<text class="legend-txt" x="${innerW - 126}" y="25">Estimated rows</text>`;

  const svg = `<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 ${W} ${H}" width="${W}" height="${H}">
    <g transform="translate(${PAD.l},${PAD.t})">${svgInner}</g>
  </svg>`;
  divChart.innerHTML = svg;

  // compute final error ratio and write summary message
  const lastTrue = trueRows[k - 1];
  const lastEst  = estRows[k - 1];
  const ratio    = lastEst > 0 ? lastTrue / lastEst : 0;
  const errMag   = ratio >= 1 ? ratio : (lastEst / lastTrue);
  const underOver = lastEst > lastTrue ? 'overestimate' : 'underestimate';

  let cls, msg;
  if (errMag < 1.5) {
    cls = 'ok';
    msg = i18nFmt('Good estimate — error factor %x%×.', { x: errMag.toFixed(2) });
  } else if (errMag < 10) {
    cls = 'err';
    msg = i18nFmt('Error factor %x%× (%dir%) after the last join.', { x: errMag.toFixed(1), dir: underOver });
  } else {
    cls = 'err';
    msg = i18nFmt('Catastrophic %dir% by %x%×!', { x: Math.round(errMag), dir: underOver });
  }
  divSum.innerHTML = `<span class="${cls}">${msg}</span> ${i18nFmt('True: %t% rows  |  Estimated: %e% rows.', { t: fmt2(lastTrue), e: fmt2(lastEst) })}`;
}

slJoins.addEventListener('input', build);
slTrue.addEventListener('input',  build);
slEst.addEventListener('input',   build);
document.getElementById('btnReset').addEventListener('click', () => {
  slJoins.value = '4'; slTrue.value = '10'; slEst.value = '15';
  build();
});
build();
Result
Console

Notice how a modest 2×2\times error at join 1 becomes a 32×32\times error by join 5 if each step is off by the same factor. Real optimizers face correlated columns, data skew, and out-of-date statistics — making errors far larger. A plan that looks optimal to the optimizer can be millions of times slower to execute.

The Real Complexity

Why is cardinality estimation so hard? The optimizer faces three compounding problems:

  • Attribute independence. Classic estimators multiply per-column selectivities: Pr⁡[A∧B]=Pr⁡[A]⋅Pr⁡[B]\Pr[A \wedge B] = \Pr[A] \cdot \Pr[B]. In real tables, columns are correlated (city and zip code; age and salary). The independence assumption can be off by orders of magnitude.
  • Error propagation through joins. If each join estimate has a relative error of ε\varepsilon, the error after kk joins grows as (1+ε)k(1+\varepsilon)^{k}. With five joins and a modest 2×2\times per-step error, the final estimate can be off by 32×32\times. With ten joins: more than 1000×1000\times.
  • Data skew and out-of-date statistics. Histograms summarize the data at collection time. Heavy-tailed distributions and recent inserts mean the statistics the optimizer uses may not reflect reality at all.

Is there an efficient exact solution? No tractable one is known. Computing the exact size of a join result is #P-hard in general — as hard as counting the satisfying assignments of a boolean formula. Approximation algorithms exist, but they require assumptions (bounded treewidth, independence) that real queries routinely violate.

The result: every major database engine (PostgreSQL, MySQL, SQL Server, Oracle) ships with estimators that are known to fail badly on multi-join queries. A 2015 study by Leis et al. measured errors exceeding 104×10^4\times on standard benchmarks — and that is not a bug, it is the state of the art.

Where It Matters

Bad cardinality estimates do not just slow down queries — they cascade into wrong join orders, wrong index choices, and wrong parallelism decisions. The same core problem appears everywhere data is queried at scale:

  • Join ordering: with nn tables there are n!n! possible join orders. The optimizer picks the cheapest one using estimated sizes. A bad estimate flips the ordering and the cost explodes.
  • Index selection: a scan is cheaper than an index lookup when the result is large. Underestimate the count and the optimizer picks index lookups on millions of rows — slower than a full scan.
  • Distributed SQL: systems like BigQuery, Snowflake and Spark must decide how to shuffle data across machines. A 10×10\times underestimate means the chosen broadcast join runs out of memory on the receiver.
  • Adaptive query execution: modern engines (Spark AQE, PostgreSQL 14+ re-planning) re-estimate mid-query when the first estimate is clearly wrong. This is a workaround for bad cardinality estimation, not a solution.

The cardinality problem is also a driver of learned query optimizers — systems that replace histograms with neural networks trained on past query results. Early results are promising, but generalization to unseen data remains an open research challenge closely related to PAC learning.

Conclusion

Cardinality estimation is one of those problems that looks simple from the outside — just count the rows — but turns out to touch some of the deepest questions in data management. The exact version is #P-hard. The approximate version fails in practice whenever columns are correlated, data is skewed, or enough joins pile up. And the errors compound: a small mistake early in the plan can multiply into a slowdown of six or seven orders of magnitude.

After fifty years and countless papers, no one has a reliable general solution. That is not a failure of engineering; it is a sign that the problem is genuinely hard. Until it is solved — if it ever is — every query optimizer in the world will keep making its best guess, and sometimes that guess will be catastrophically wrong.

Share this article

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

Comments

Loading comments...

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