Course contentsShow
← Computer Science
Lesson 1700 of 2,87238. Database Transactions and IndexingFree lesson

Cardinality Estimation

Techniques for estimating result set sizes to predict query costs and choose optimal plans.

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.