Cardinality Estimation

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\times$ mistake into a $10^6\times$ catastrophe by the fifth table. This is the quiet crisis at the heart of every database engine.

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.

<!-- {{c_html_comment}} -->
<div class="panel">
  <div class="controls">
    <label class="ctrl-label">
      {{label_joins}}
      <input type="range" id="numJoins" min="1" max="8" value="4" />
      <span id="joinsVal">4</span>
    </label>
    <label class="ctrl-label">
      {{label_true_sel}}
      <input type="range" id="trueSel" min="1" max="50" value="10" />
      <span id="trueSelVal">0.10</span>
    </label>
    <label class="ctrl-label">
      {{label_est_sel}}
      <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">{{btn_reset}}</button>
  </div>
  <div id="chartWrap" class="chart-wrap" aria-label="{{aria_chart}}"></div>
  <div id="summary" class="summary"></div>
</div>

/* {{c_css_comment}} */
*, *::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; }

// Code not found

Notice how a modest $2\times$ error at join 1 becomes a $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.

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

• Attribute independence. Classic estimators multiply per-column selectivities: $\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 $k$ joins grows as $(1+\varepsilon)^{k}$. With five joins and a modest $2\times$ per-step error, the final estimate can be off by $32\times$. With ten joins: more than $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 $10^4\times$ on standard benchmarks — and that is not a bug, it is the state of the art.

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 $n$ tables there are $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\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.

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.