Cardinality Estimation: How Databases Guess Query Costs

WHY IT EXISTS: A database can often execute a query in many different ways, known as query plans. For example, joining tables A and B could be done by scanning A then looking up matches in B, or vice-versa. The cost of these plans can differ by orders of magnitude. To pick a good plan, the database must estimate the cost of each one, and that cost depends heavily on how much data is being processed at each step.

THE MENTAL MODEL: Think of it like planning a road trip with multiple stops. To find the fastest route, you need to estimate the travel time for each leg of the journey. Cardinality estimation is the database's way of estimating "traffic" (number of rows) on each "road" (operator in the query plan). A bad traffic estimate for one leg can lead you to choose a terrible overall route.

HOW IT WORKS: Databases maintain statistics about the data in tables and columns. This includes the total number of rows, the number of distinct values in a column, and often histograms describing the data's distribution. When a query like SELECT * FROM users WHERE country = 'USA' arrives, the optimizer uses these statistics to guess how many rows will match. It might use a histogram to estimate the percentage of users from the USA and multiply that by the total number of users. For joins, it gets more complex, estimating how many rows from one table will find a match in the other.

WHEN TO USE IT: This isn't a tool you "use" directly. It's a core, automatic function of any cost-based query optimizer in systems like PostgreSQL, MySQL, and SQL Server. You interact with it indirectly by ensuring your database has up-to-date statistics, often by running commands like ANALYZE or relying on auto-vacuum processes.

WHEN NOT TO USE IT: You can't turn it off, but you can override it. If you know the optimizer is making a bad choice due to a poor cardinality estimate, you can use query hints to force a specific plan (e.g., force a join order). This is a power tool for experts and should be used cautiously, as hints can make queries brittle if the underlying data changes. The better long-term solution is to fix the statistics so the estimate becomes accurate.

ONE CANONICAL EXAMPLE: A query joins a huge events table with a small users table on user_id. The optimizer estimates that only a few users will be selected, so it decides to loop through those users and look up their events (a nested loop join). But if a WHERE clause was unexpectedly unselective and millions of users are actually chosen, this plan becomes catastrophic. A hash join would have been much faster, but the bad cardinality estimate prevented the optimizer from seeing that. This is a classic performance issue solved by updating statistics.