Cardinality Estimation Explained: Why the Query Optimizer Sometimes Guesses Wrong

Quick Answer

Cardinality estimation is the query optimizer's guess at how many rows a condition like WHERE status='closed' will actually match, before it runs the query — and that guess decides whether it picks an index lookup or a full table scan. We built a real skewed table (99,900 'closed' rows versus 100 'escalated' rows out of 100,000) and caught the optimizer's own statistics underestimating the common value's row count by roughly 2x, then proved the real-world cost of trusting a wrong estimate: forcing an index-based plan on the under-estimated common value ran 4x slower than simply scanning the table.

What the Optimizer Is Actually Guessing

Before a database runs a query, its optimizer has to choose between competing plans — use this index, use that one, or just scan the whole table — and it makes that choice based on estimated cost, which in turn depends heavily on how many rows it expects a condition to match. This estimate is called cardinality estimation, and it's built from statistics the database keeps about each column: roughly how many distinct values exist, and (in more advanced implementations) roughly how those values are distributed.

The optimizer never actually counts the matching rows before choosing a plan — that would mean running the query twice. It estimates, using whatever statistics it has on hand, and then commits to a plan based on that estimate. When the estimate is close to reality, you get a sensible plan. When it's badly wrong, you can end up with the database confidently executing a plan that's objectively worse than the alternative it didn't pick — which is exactly what we reproduced below.

It's worth being clear about where these statistics actually come from, because that's the root of every failure mode this article covers. They aren't computed on the fly for every query. A command like ANALYZE TABLE samples the table's actual data at a specific point in time and stores a summary — not a live, continuously updated count — which means the statistics the optimizer consults can be stale the moment the underlying data changes, and can be structurally too coarse to capture certain patterns even immediately after being refreshed. Both of those limitations show up directly in the demo below.

Demo: A Table Where One Value Dominates

We built a tickets table with 100,000 rows and a status column deliberately skewed: 99,900 rows set to 'closed' and only 100 rows set to 'escalated' — a 999-to-1 ratio. After adding an index on status and running ANALYZE TABLE to refresh statistics, here's what the database's own index statistics reported:

SHOW INDEX FROM tickets WHERE Key_name='idx_status';

Cardinality: 2

That's correct, as far as it goes — there really are exactly 2 distinct values in the column. But 'cardinality' here only means distinct-value count, not how evenly those 2 values are spread across the 100,000 rows. Here's where that gap shows up. We ran EXPLAIN for the heavily skewed value:

EXPLAIN SELECT * FROM tickets WHERE status='closed';

type: ref   key: idx_status   rows: 49622

The optimizer estimated 49,622 matching rows. The real number, which we know because we built the data, is 99,900 — the estimate is off by roughly a factor of 2. This isn't a bug; it's the predictable consequence of the statistics available: with only a distinct-value count of 2 and no further distribution information, the optimizer's default assumption is that rows are split roughly evenly across those 2 values, landing near 100,000 / 2 = 50,000. Reality — a 999-to-1 skew — is about as far from 'roughly even' as two values can get.

Notice what the database got right and what it got wrong here, because the distinction matters for diagnosing this in your own systems. The cardinality figure (2 distinct values) was completely accurate — it's genuinely a 2-value column. The failure is entirely in the next inferential step: going from 'there are 2 distinct values' to 'therefore each value has roughly 50,000 matching rows,' which is a reasonable default assumption in the absence of better information, but a wrong one for this specific, heavily skewed dataset.

Demo: Proving the Wrong Estimate Has a Real Cost

A wrong estimate only matters if it changes which plan actually gets picked, and whether that plan is worse. To isolate that, we forced both plans explicitly for the dominant value and timed each one — a query that needs the filler column, which lives outside the index, forcing a real row lookup whenever the index path is taken:

-- forced through the secondary index (needs a lookup per row):
SELECT SUM(LENGTH(filler)) FROM tickets USE INDEX (idx_status) WHERE status='closed';

10 runs, real    0m3.135s

-- forced to a full table scan instead:
SELECT SUM(LENGTH(filler)) FROM tickets IGNORE INDEX (idx_status) WHERE status='closed';

10 runs, real    0m0.764s

3.135 seconds through the index versus 0.764 seconds for a plain full scan — the index-based plan was roughly 4.1x slower for matching 99.9% of the table, because every one of those nearly 100,000 matches triggered its own separate lookup back into the table to fetch filler, on top of the index traversal itself. A full scan, by contrast, just reads every page once, in order, with no extra lookups — which is cheaper precisely when a condition matches most of the table rather than a small slice of it.

This is the concrete, measured version of a piece of advice every experienced engineer eventually learns the hard way: an index is not automatically faster. It is faster specifically when the condition is selective — matching a small fraction of the table — and can actively be slower than a full scan when it isn't, which is exactly why getting the cardinality estimate right (or wrong) has a real, measurable, multi-second consequence, not just a theoretical one.

The USE INDEX and IGNORE INDEX hints used to force each plan in this demo exist precisely for situations like this one, where you need to directly compare two candidate plans rather than trust whichever one the optimizer happens to pick by default. They aren't meant for permanent use in production queries — a hint locks in a decision that may stop being correct as the data changes — but they're a genuinely useful diagnostic tool for exactly the kind of investigation this article walks through.

Why This Happens, and How Newer Engines Fix It

The specific failure mode demonstrated above — a column with very few distinct values, wildly uneven in how often each one appears — is one of the most common ways cardinality estimates go wrong, because basic statistics (distinct value count plus total row count) simply can't represent skew. The fix, where it exists, is a histogram: a statistic that records not just how many distinct values a column has, but roughly how many rows fall into specific value ranges or buckets.

MySQL 8.0 added exactly this capability with ANALYZE TABLE ... UPDATE HISTOGRAM ON column_name, which builds either a 'singleton' histogram (one bucket per distinct value, appropriate for low-cardinality columns like our status example) or an 'equi-height' histogram (buckets spanning ranges of values, for high-cardinality columns), specifically so the optimizer can see that 'closed' represents 99.9% of rows instead of assuming a 50/50 split. The MariaDB version used for the demos in this article (10.1) predates that specific feature — it only had the basic distinct-value cardinality shown above, which is exactly why the 2x misestimate was reproducible here. If you're running MySQL 8.0 or newer and have a column like this in production, building a histogram on it is the direct, documented fix for the exact problem this article measured.

Not every misestimate is fixable by adding a histogram, though. Statistics on any engine are necessarily samples or summaries, not a live recount, and they go stale the moment the underlying data distribution shifts — a column that was evenly distributed when you last ran ANALYZE TABLE can become skewed in production without anyone refreshing the statistics. If a query's performance suddenly degrades with no code change, checking whether EXPLAIN's row estimate still matches reality, the same way we checked it against our known 99,900 real matches above, is one of the fastest ways to find out whether stale or insufficient statistics are the actual cause.

What to Actually Do With This

Three habits follow directly from everything demonstrated above. First, when a query that touches an indexed column is unexpectedly slow, run EXPLAIN and look at the rows estimate specifically — if it's wildly different from a quick SELECT COUNT(*) with the same condition, you've found a statistics problem, not necessarily a missing-index problem. Second, remember that an index being present doesn't mean the optimizer should or will use it for every value in that column — a highly skewed column can legitimately need a full scan for its common values and an index lookup for its rare ones, and a good optimizer with good statistics will correctly choose differently depending on which value you're filtering by. Third, if you're on an engine and version that supports histograms (MySQL 8.0+, and equivalent features in Postgres and other engines), building one on a known-skewed, frequently-filtered column is a targeted, low-risk fix, rather than guessing at index changes that won't actually address a statistics problem. You can practice writing and reading EXPLAIN output against real schemas in the SQL course on Priodemy.

A fourth, less technical habit is just as important: when a colleague proposes 'adding an index' as the fix for a slow query, ask what the actual selectivity of the filtered column looks like in production, not just in a small local test table. The entire failure mode demonstrated in this article only shows up once the real data is skewed enough, and a local development database seeded with small, evenly-distributed sample data will often hide the exact problem that only appears once real, skewed production data is involved.

Frequently Asked Questions