Cardinality Estimation

Cardinality estimation predicts how many rows query operations will produce. These predictions shape plan selection, and errors can lead to inefficient execution.

Cardinality estimation is the optimizer's prediction of how many rows a query operation will produce. It applies to operations such as scans, filters, joins, and grouping. These predictions help the database compare alternative execution plans before running the query.

For a filter, the estimate depends on the expected fraction of rows that satisfy its predicate. For a join, the estimate depends on factors including input row counts, matching values, and value distributions. Optimizers commonly draw on table and column statistics, such as row counts and histograms; the exact statistics and estimation methods vary by database.

Estimates affect decisions such as join order, join algorithm, and whether to use an index or scan a table. A plan that expects few rows may favor an index lookup, while a plan that expects many rows may favor a scan. The cheapest-looking choice depends on the optimizer's estimates and cost model.

When estimates are far from actual row counts, the chosen plan can perform poorly. Causes include stale or limited statistics, skewed values, correlated predicates, and complex expressions. Comparing estimated and actual row counts in an execution plan helps locate where predictions begin to diverge; collecting fresher or more informative statistics may help, but is not a universal fix.

Key points

• Cardinality estimation predicts rows produced by scans, filters, joins, and other query operations.
• Optimizers use estimates when comparing execution plans.
• Statistics about table size and value distributions can inform estimates.
• Skew, correlation, and stale statistics can lead to large estimation errors.
• Execution plans can expose estimated and actual row counts for diagnosis.

Interview questions

What does cardinality estimation mean in a database?

Cardinality estimation is the optimizer's prediction of how many rows an operation will return. The optimizer uses these predictions when comparing plans, including join orders and access methods. If the prediction is substantially wrong, a plan that looked inexpensive may be slow in practice. I would compare estimated and actual rows in the execution plan to find where the discrepancy starts.

How can cardinality estimates change the execution plan?

The optimizer uses estimated row counts as inputs to its cost model. For example, the expected number of rows can influence whether it chooses an index lookup or a table scan, and which join order or join algorithm it prefers. The cost model also considers factors beyond cardinality, so row count alone does not determine the plan. A badly underestimated intermediate result can make later operations much more expensive than expected.

A query has a poor plan. How would you investigate a cardinality-estimation problem?

I would inspect the query plan with the database's appropriate EXPLAIN facility and compare estimated rows with actual rows, paying particular attention to the earliest large divergence. Then I would check whether relevant statistics are current and whether the data has skew or correlations the estimator may not capture. I would also verify that the query predicates and joins are expressed as intended. Any statistics or query change should be tested against representative data and workload, since changing a plan can help one query while affecting others.

Why can estimates be wrong when a query filters on multiple correlated columns?

Suppose a table has predicates on two columns that are strongly correlated. An estimator that treats the predicates as independent may multiply their selectivities and predict far fewer matching rows than actually exist. The resulting underestimate can influence join order or the choice of access method. Multi-column or dependency statistics can help in some databases, but support and effectiveness are database-specific.