DataTerminology.comNEW
The process of predicting the number of rows or distinct values an operator will process to guide query optimization decisions.
DESCRIPTION
Cardinality estimation informs cost-based optimizers by predicting row counts for scans, filters, joins, and aggregations. Estimators use statistics such as histograms, distinct counts, and correlation assumptions, sometimes augmented by sampling. Inaccurate estimates cause poor join ordering, wrong indexes, and slow plans. Modern systems explore adaptive techniques and learned estimators to combat data skew and correlations. Regular statistics maintenance and query hints can mitigate pathologies.
ALTERNATIVE DEFINITIONS
Microsoft Learn
Cardinality estimation (CE) is the process of predicting the number of rows processed in each step of a query plan.
Clear tie to query plan operators and SQL Server optimizer.
PostgreSQL Documentation
The planner’s estimates of the number of rows that will be retrieved by each query operation are critical to choosing the most efficient execution plan.
Emphasizes the centrality of row-count estimates in plan choice.
RELATED TERMS
Query Optimizer Selectivity Estimation Query Optimization Histogram Sampling Statistics Collection Join Order Skew Adaptive Query Processing
COMPETING TERMS
Learned Cardinality Estimation Rule-Based Optimization
RELATIONS
- Broader: Query Optimization
KNOWLEDGE AREAS
Data Storage & Operations Data Engineering Data Warehousing & BI Software Engineering
TARGET AUDIENCE
Data Engineer Software Developer Data Architect
EXTERNAL SOURCES
- Wikipedia - Cardinality estimation
- Microsoft Learn - SQL Server CE architecture guide.
- PostgreSQL Documentation - Planner statistics and estimation details.
- ACM - Learned cardinality estimation research.
TOP QUESTIONS
Why is Cardinality Estimation critical for query performance?
Optimizers rely on accurate row estimates to choose join orders, indexes, and algorithms. Errors can cause orders-of-magnitude slowdowns.
Category: Relevancy
What techniques underpin Cardinality Estimation?
Histograms, multi-column stats, sampling, independence assumptions, correlation adjustments, and runtime feedback in adaptive engines.
Category: Methods
How does data skew affect Cardinality Estimation?
Skew breaks independence assumptions, leading to under/overestimates. Multi-dimensional stats and sampling help mitigate skew effects.
Category: Risks
What are signs of poor Cardinality Estimation?
Bad join orders, nested loops on large joins, excessive spills, and warnings about outdated statistics.
Category: Observability
How can I improve Cardinality Estimation?
Refresh statistics, create multi-column stats, use hints judiciously, and reconsider predicates that hide correlations.
Category: Best practices
Do learned models replace traditional Cardinality Estimation?
They can augment or replace parts in some systems, but operational complexity and drift make hybrid approaches practical today.
Category: Opinion
How often should statistics be updated for Cardinality Estimation?
Update stats after significant data changes or periodically based on workload. Many databases automate thresholds for refresh.
Category: Practice
Is Cardinality Estimation relevant in data warehouses?
Yes; even columnar systems with MPP optimizers rely on estimates for distribution, join strategies, and partition pruning.
Category: Relevancy
What’s the relationship between Selectivity and Cardinality Estimation?
Selectivity estimates the fraction of rows matching a predicate; cardinality multiplies selectivity by table size to estimate row counts.
Category: Definitions