How Cardinality Estimation Affects SQL Performance

Have you ever run an SQL query that should have taken a few seconds but instead took several minutes? You may have checked your indexes, reviewed your joins, and rewritten parts of the query without finding a clear explanation for the slow performance.

One possible cause is inaccurate cardinality estimation.

Database engines do more than execute SQL statements. Before running a query, they usually evaluate different execution strategies and select a plan they estimate will be efficient. To make that decision, the query optimizer predicts how many rows each operation will process. These predictions are called cardinality estimates.

When those estimates are accurate, the database has a better chance of selecting an efficient execution plan. When they are significantly wrong, the optimizer may choose an inefficient join algorithm, allocate inappropriate resources, or perform unnecessary scans and sorts.

In this guide, you will learn what cardinality estimation means in SQL, how it influences query performance, why estimation errors occur, and how to diagnose and improve them using practical examples.

What Is Cardinality Estimation in SQL?

Cardinality estimation is the process a database query optimizer uses to predict the number of rows produced or processed by an operation in a query execution plan.

The word cardinality can refer to different things in database terminology. It may describe the number of distinct values in a column, the number of rows in a table, or the number of rows produced by a particular query operation.

In query optimization, cardinality estimation generally focuses on predicting row counts at different stages of query execution.

Consider this query:

SELECT *
FROM orders
WHERE status = 'completed';

Suppose the orders table contains 1,000,000 rows, and 600,000 of them have a status of completed.

A cardinality estimator attempts to predict how many rows will satisfy the filter.

If it estimates 580,000 rows, its prediction is relatively close to the actual result. If it estimates only 2,000 rows, the error could influence the optimizer’s choice of execution plan.

The optimizer uses this estimate alongside other information, including available indexes, estimated I/O, CPU costs, memory requirements, and the costs of alternative operations.

The important distinction is that cardinality estimation predicts row counts; the query optimizer uses those predictions to choose an execution plan.

Why Cardinality Estimation Matters for SQL Performance

Cardinality estimates influence several important database operations. A mistake early in a query plan can affect multiple operations that depend on its output.

1. Choosing the Right Join Algorithm

SQL databases commonly use nested-loop joins, hash joins, and merge joins, although the available algorithms depend on the database engine and query.

The best algorithm often depends on how many rows each input contains, the available indexes, the ordering of the data, and the cost of producing each input.

For example, a nested-loop join can work well when one input contains a small number of rows and the other input can be searched efficiently using an index.

However, if the optimizer expects 20 rows and the operation actually processes 200,000, repeated lookups can become expensive.

A hash join may be more efficient for larger inputs, depending on the available resources and data distribution.

Incorrect cardinality estimates can therefore lead to a join strategy that performs poorly for the actual data.

2. Selecting Between Table Scans and Index Scans

An index can help a database locate specific rows without reading an entire table. However, using an index is not always the cheapest option.

Suppose a query returns only 50 rows from a table containing one million rows. An index seek or index scan may allow the database to access the required records efficiently.

If the query returns 800,000 rows, reading a large portion of the table through an index may involve many additional lookups. A sequential table scan can sometimes be cheaper.

The optimizer estimates how many rows a filter will return before comparing these alternatives.

If the estimate is inaccurate, it may select an access method that is poorly suited to the actual number of qualifying rows.

3. Managing Memory for Hashing and Sorting

Operations such as hash joins, hash aggregation, and sorting may require substantial memory.

An underestimated row count can contribute to insufficient memory allocation or execution strategies that spill intermediate results to disk. Spilling can increase query latency significantly.

Overestimation can also be harmful. Depending on the engine and workload, it can result in excessive memory reservations, reduced concurrency, or less efficient plan choices.

The precise consequences depend on the database’s memory-management and execution mechanisms.

4. Optimizing Aggregations

Consider a query that groups transactions by customer:

SELECT
    customer_id,
    SUM(order_amount) AS total_spent
FROM orders
GROUP BY customer_id;

The optimizer needs to estimate how many groups the query will produce.

If the table contains one million transactions from 10,000 customers, the output might contain approximately 10,000 groups.

If the optimizer incorrectly expects only 100 groups or nearly one million groups, that estimate can influence its choice of aggregation strategy and resource requirements.

Accurate estimates help the optimizer make better decisions about processing and grouping data.

5. Optimizing Multi-Table Joins

Cardinality estimation becomes especially important when a query joins several tables.

Suppose an analytics query joins customers, orders, products, and payments. Each join produces an intermediate result that becomes an input to later operations.

If the optimizer significantly underestimates an early join, it may underestimate the size of subsequent results as well.

These errors can accumulate across the plan, potentially leading to an inefficient join order and expensive intermediate operations.

For complex analytical queries, a cardinality estimation error can therefore have a greater impact than an isolated mistake in a simple filter.

How SQL Databases Estimate Cardinality

Database engines use statistics and estimation models to predict the number of rows that operations will produce.

The exact methods differ between PostgreSQL, SQL Server, MySQL, Oracle, and other systems.

Table Statistics

The database may maintain statistics about the number of rows in a table, the number of pages it occupies, and the distribution of values in particular columns.

These statistics help the optimizer estimate how much data an operation will process.

If statistics are outdated after substantial data changes, the optimizer may make decisions using an inaccurate picture of the table.

Distinct Value Counts

The number of distinct values in a column can help the optimizer estimate the selectivity of equality predicates.

For example, suppose a table has one million rows and approximately 100 distinct customer segments.

A simplified uniform-distribution assumption might estimate that filtering for one segment returns about 10,000 rows.

However, this prediction may be inaccurate if one segment accounts for 40% of the records while several others are rare.

Distinct value counts are useful, but they do not describe the complete distribution of values.

Histograms

Histograms describe how values are distributed across a column. Depending on the database engine, statistics may capture value frequencies, ranges, or other distribution information.

Suppose an orders table contains these values:

Order status	Number of rows
Completed	600,000
Pending	250,000
Cancelled	100,000
Refunded	50,000

A database with sufficiently informative statistics can estimate the number of rows for a predicate such as status = 'completed' more accurately than one relying only on a uniform distribution assumption.

Histograms are particularly useful when values are unevenly distributed.

Correlated Columns

Two columns are correlated when knowing the value of one provides information about the value of the other.

Consider a sales table containing country and currency.

A query that filters for country = 'Nigeria' and currency = 'NGN' may return a large number of rows. These predicates are related because Nigerian transactions commonly use the Nigerian naira.

An optimizer that assumes the predicates are independent may estimate the result incorrectly.

Some database engines support extended or multicolumn statistics that help model certain relationships between columns. The available capabilities and the conditions under which they are used vary by engine.

Predicate Selectivity

Selectivity describes the proportion of rows that satisfy a condition.

A highly selective predicate returns a small fraction of the available rows. A less selective predicate returns a larger fraction.

A simplified estimate can be expressed as:

[
\text{Estimated Rows} =
\text{Input Rows} \times \text{Estimated Selectivity}
]

If a table contains 500,000 rows and the optimizer estimates that 2% satisfy a filter, it predicts:

[
500{,}000 \times 0.02 = 10{,}000
]

The actual result may differ because the selectivity estimate depends on the quality of the statistics and the assumptions used by the optimizer.

Practical Example: How Incorrect Cardinality Estimates Affect a Query

Imagine an e-commerce database with the following tables:

• customers: one million customer records.
• orders: five million order records.
• payments: five million payment records.

An analyst wants to identify completed orders associated with a particular customer segment.

SELECT
    c.customer_id,
    o.order_id,
    p.payment_id
FROM customers AS c
JOIN orders AS o
    ON c.customer_id = o.customer_id
JOIN payments AS p
    ON o.order_id = p.order_id
WHERE c.segment = 'enterprise'
  AND o.status = 'completed';

Suppose enterprise customers account for 30% of the customer table, but the optimizer estimates that they represent only 1%.

The estimated number of matching customers would be much smaller than the actual number.

That discrepancy can affect the optimizer’s choice of join order and join algorithm. It might choose a strategy that works well for a small number of customers but performs poorly when the query returns many more rows.

The issue is not necessarily the SQL syntax. The query may be logically correct, and the relevant indexes may already exist.

The problem may be that the optimizer is working with inaccurate estimates.

How to Investigate the Problem

The next step is to inspect the execution plan.

In PostgreSQL, for example, you can run:

EXPLAIN ANALYZE
SELECT
    c.customer_id,
    o.order_id,
    p.payment_id
FROM customers AS c
JOIN orders AS o
    ON c.customer_id = o.customer_id
JOIN payments AS p
    ON o.order_id = p.order_id
WHERE c.segment = 'enterprise'
  AND o.status = 'completed';

EXPLAIN ANALYZE executes the query and reports actual execution measurements alongside the plan’s estimates.

Look for operations where the estimated number of rows differs substantially from the actual number.

For example, a plan node might show an estimate of 5,000 rows but produce 500,000 rows. That is a 100-fold underestimation.

The example is illustrative rather than a prediction of what a particular database will produce.

When investigating real queries, also examine execution time, loops, buffer activity, sorts, hash operations, and disk spills where the engine reports them.

Important: EXPLAIN ANALYZE executes the query. Use care with statements that modify data, expensive production workloads, and queries that may have side effects.

How to Improve Cardinality Estimation

When a query is slow because of inaccurate estimates, the goal is to identify the source of the error rather than change the query blindly.

1. Update Database Statistics

Stale statistics can cause the optimizer to misunderstand the current data distribution.

In PostgreSQL, you can update statistics using:

ANALYZE customers;
ANALYZE orders;
ANALYZE payments;

PostgreSQL also supports:

VACUUM ANALYZE orders;

This combines vacuuming and statistics collection. Choose the appropriate maintenance operation for your workload rather than running it automatically whenever a query is slow.

Other database systems have their own statistics-maintenance commands and scheduling mechanisms.

2. Investigate Skewed Data

A column may contain a few very common values and many rare ones.

For example, 80% of all orders might have a completed status. An estimate based on an assumption of evenly distributed values could be inaccurate.

Inspect the actual distribution:

SELECT
    status,
    COUNT(*) AS order_count
FROM orders
GROUP BY status
ORDER BY order_count DESC;

Comparing the distribution with the optimizer’s estimates can help identify whether data skew is contributing to the problem.

3. Consider Multicolumn Statistics

When predicates involve related columns, single-column statistics may not provide enough information.

In PostgreSQL, extended statistics can help with certain correlations and combinations of values:

CREATE STATISTICS customer_region_stats
    (dependencies, mcv)
ON country, currency
FROM customers;

ANALYZE customers;

This is useful only when those columns exist in the specified table and the chosen statistics match the data relationship. Extended statistics do not solve every estimation problem, and their use depends on the query and PostgreSQL version.

Other database engines provide different approaches to multicolumn statistics.

4. Review Join Conditions and Data Types

Unexpected casts, expressions applied to columns, mismatched join keys, and complicated predicates can make estimation more difficult or prevent the optimizer from using available information effectively.

Check that join conditions reflect the intended relationships and that key columns use compatible data types.

Avoid changing data types or simplifying expressions without verifying that the changes preserve the query’s meaning.

5. Use Indexes Based on the Actual Workload

Indexes can improve filtering and joins, but adding indexes does not automatically fix cardinality estimation.

First, determine whether the problem comes from a poor row-count estimate, an unsuitable access path, expensive lookups, or another bottleneck.

Then evaluate appropriate indexes against the query workload. Additional indexes consume storage and can slow down inserts, updates, and deletes.

6. Compare Estimated and Actual Rows

A practical diagnostic process is to inspect the execution plan, identify the earliest major estimation error, check the underlying statistics, and rerun the query after making a justified change.

Fixing an error near the beginning of a plan can improve later estimates and may be more effective than attempting to optimise every downstream operation separately.

Best Practices for Monitoring Cardinality Estimation

Database administrators and data engineers can reduce estimation-related performance problems by building a consistent monitoring process.

• Keep table and column statistics sufficiently current.
• Monitor queries whose execution times increase unexpectedly.
• Investigate large differences between estimated and actual row counts.
• Pay particular attention to skewed data and correlated predicates.
• Review execution plans after major data growth or schema changes.
• Test tuning changes against representative data and workloads.
• Track performance improvements rather than assuming that a different plan is automatically better.

A useful starting point is to prioritise high-impact queries: expensive joins, frequently executed reports, large aggregations, and workloads with unpredictable execution times.

Cardinality estimation is a fundamental part of SQL query optimization. It helps database engines predict how many rows different operations will process and influences decisions about joins, indexes, aggregations, memory, and execution order.

When estimates are accurate, the optimizer has better information for selecting an efficient execution plan. When estimates are significantly wrong, even a well-written query with suitable indexes can perform poorly.

To diagnose these problems, compare estimated and actual row counts in execution plans, inspect data distributions, maintain statistics, and investigate correlated predicates. Apply changes based on evidence and test them against realistic workloads.

Understanding cardinality estimation gives data engineers a practical way to explain why a query is slow and identify improvements beyond simply rewriting SQL.

Frequently Asked Questions