Cardinality Estimation

Cardinality estimation predicts how many rows each part of a SQL query will produce. The database optimizer uses these estimates to choose execution strategies such as join order, join algorithms, scans, and index access.

A query optimizer needs row-count estimates before it can compare alternative execution plans. Cardinality is the number of rows produced by a relation, filter, join, or other relational operation. Accurate estimates help the optimizer distinguish inexpensive plans from expensive ones.

For a filter, the optimizer estimates selectivity: the fraction of rows expected to satisfy a predicate. For example, if a table has 1,000,000 rows and a predicate is estimated to have 1% selectivity, the estimated cardinality is about 10,000 rows. Statistics such as value distributions, distinct-value counts, null information, and histograms can support these estimates.

Joins make estimation more difficult because the optimizer must reason about relationships between columns. It may use statistics on join keys and assumptions about value distributions or independence. When those assumptions are wrong, the estimated row count can differ dramatically from reality.

Cardinality errors can cause poor plan choices. An optimizer that expects a tiny result may favor an index lookup or nested-loop join, while a large actual result may make a sequential scan or hash join more appropriate. A major estimation error early in a plan can also propagate into later operators and distort their costs.

For backend engineers, cardinality estimation is especially relevant when diagnosing slow SQL. Comparing estimated versus actual row counts in an execution plan can reveal whether the optimizer's assumptions are contributing to the problem. Updating statistics, improving predicates or indexes, or restructuring a query may help, depending on the database and workload.

Key points

• Cardinality is the estimated or actual number of rows produced by an operation.
• Selectivity represents the fraction of rows expected to satisfy a predicate.
• Optimizers use statistics to estimate cardinalities and compare execution plans.
• Join cardinality is difficult because estimates depend on distributions and correlations between columns.
• Large estimation errors can lead to inappropriate join algorithms, access paths, or join orders.

Interview questions

What is cardinality estimation and why does a database optimizer need it?

Cardinality estimation predicts the number of rows produced by query operators. The optimizer uses those predictions when comparing possible execution plans. They influence decisions such as join order, join algorithm, and whether an index access path is worthwhile. If the estimates are badly wrong, the optimizer can choose a plan that performs poorly on the actual data.

How does selectivity relate to cardinality estimation?

Selectivity is the expected fraction of input rows that satisfy a predicate. If a table contains one million rows and a predicate has an estimated selectivity of 2%, the optimizer may estimate about 20,000 matching rows. That estimated output becomes the cardinality of the filter operation. Statistics help the optimizer derive selectivity for many predicates.

Why are joins difficult for cardinality estimation?

The optimizer must estimate how many rows will match across two inputs, which depends on the distributions of their join keys. Simple assumptions about independence or uniform distributions can be inaccurate for real data. Correlated columns, skewed values, and stale statistics can therefore create large errors. Those errors can then affect join order and join algorithm selection.

What happens when cardinality is severely underestimated?

The optimizer may believe an operator will process very few rows when it will actually process many. That can make plans favor strategies suited to small inputs, such as repeated nested-loop lookups, when a larger-input strategy could be more appropriate. The mistake can also propagate to downstream operators and distort their estimated costs. Diagnosing the issue usually involves comparing estimated and actual row counts in an execution plan.

How would you diagnose a query whose execution plan has poor cardinality estimates?

I would inspect the execution plan and compare estimated rows with actual rows at each major operator. I would look for large discrepancies near filters and joins, then examine the relevant column statistics, data distribution, predicate selectivity, and possible correlations. I would also check whether statistics are stale or whether the query contains expressions that make estimation difficult. After making a targeted change, I would recheck the plan and actual behavior rather than assuming the change improved performance.