Cardinality Estimation
What you'll learn: How databases predict result set sizes to choose the fastest query execution plan.
Why Estimate Cardinality?
When a database optimizer considers multiple ways to execute a query, it needs to predict which plan will be fastest. The key metric? Cardinality—the estimated number of rows a query operation will produce.
Think of cardinality estimation like planning a road trip: you estimate traffic on different routes to pick the fastest one. A database does the same with query plans, but it estimates "row traffic" through each operation.
How It Works
The query optimizer uses statistics stored about your tables and indexes:
- Table cardinality: Total row count in each table
- Column histograms: Distribution of values (how many rows have each value)
- Index statistics: Unique value counts, min/max values
- Null counts: How many rows contain NULL in each column
For a filter like WHERE age > 30, the optimizer checks the histogram for the age column. If 40% of values are above 30, and the table has 1,000 rows, the estimated cardinality is ~400 rows.
Why It Matters for Cost-Based Optimization
Cost-based optimization (from the previous lesson) relies entirely on accurate cardinality estimates. Poor estimates lead to bad plan choices:
- Underestimate → optimizer might choose nested loops when hash join would be faster
- Overestimate → optimizer might allocate too much memory or pick overly complex strategies
Multi-table joins compound estimation errors—if each join estimate is 20% off, the final estimate can be wildly inaccurate.
Key Takeaway: Cardinality estimation uses table statistics to predict result set sizes, enabling the query optimizer to calculate operation costs and select the most efficient execution plan.