Estimating Query Result Cardinality

The Cost-Based Optimization Framework

Before we can choose the "best" plan, we need a way to define what "best" means. Database systems use a cost model to assign a numerical score to a physical query plan. This cost is an estimate of the resources required for execution, primarily driven by I/O, but also considering CPU, memory, and network usage.

A critical input to this cost model is the estimated number of rows, or cardinality, that flows through each operator in the plan. After all, the cost of joining two tables depends heavily on how many rows are in each one.

The query optimizer's job is to explore the space of possible plans, estimate the cost of each one using cardinality estimates, and pick the one with the lowest cost.

This process, however, is notoriously difficult. The optimizer can't run parts of the query to get exact counts, as that would be too slow. It must rely on estimates, and errors in these estimates can cascade up the query plan, leading to poor plan choices.

The Foundation: Database Statistics

As you just heard, the optimizer's estimates are based on statistical information about the data. The DBMS collects and stores these statistics in its internal catalog. This process is often triggered automatically when data changes significantly, or it can be manually invoked by a DBA using a command like ANALYZE or UPDATE STATISTICS.

For any given relation R, the catalog typically stores:

• |R|: The total number of tuples (rows) in the relation.
• s(R): The average size of a tuple in bytes.
• For each attribute A in R:
  • V(A, R): The number of distinct values of attribute A.
  • Low(A, R) and High(A, R): The minimum and maximum values of attribute A.

These simple statistics are the building blocks for everything that follows.

Estimating Cardinality with Selectivity

To estimate the cardinality of an operation like σ_p(R), the optimizer calculates the selectivity of the predicate p, denoted sel(p).

Selectivity is the fraction of tuples that are expected to satisfy a predicate.

The estimated cardinality of the selection is then simply:

The challenge lies in calculating sel(p). For this, the optimizer uses a set of formulas that rely on the catalog statistics and two major, simplifying assumptions:

1. Uniform Distribution: The values of an attribute are spread evenly across their range.
2. Predicate Independence: The values of different attributes are not correlated with each other.

Let's see how this works in practice.

Summary of Selectivity Formulas

To solidify what you just watched, here is a summary of the core formulas. This reference material from the University of Antwerp is a great, concise guide.

The independence assumption is particularly important from an engineering perspective. As the video noted with the make='Honda' and model='Accord' example, attributes are often correlated. Assuming they are independent can lead the optimizer to grossly underestimate the selectivity and make a poor plan choice. Modern commercial databases have ways to detect and store statistics on correlated columns, but it adds significant complexity.

SELECT * FROM Products
WHERE category = 'electronics' AND price > 800;

Dealing with Reality: The Problem of Skew

The uniformity assumption simplifies calculations, but real-world data is rarely uniform. It's often skewed, with some values appearing much more frequently than others. Using a simple formula like 1 / V(A, R) would be highly inaccurate in such cases.

To handle skew, optimizers use histograms. A histogram is a data structure that approximates the distribution of values in a column by grouping them into buckets. Instead of assuming every value is equally likely, the optimizer can look up a value in the histogram to get a much better estimate of its frequency.

Histograms represent a classic engineering trade-off: they consume more memory in the catalog and take time to compute, but they drastically improve the accuracy of cardinality estimates, leading to better query plans.

Conclusion

Today you've taken a crucial step into the world of cost-based optimization. You've learned how optimizers predict the size of data flowing through a query plan, a process that is part science and part art.

Key Takeaways:

• Cardinality estimation is the process of predicting the number of rows an operator will return, which is a fundamental input for cost-based optimization.
• Estimates are based on statistics (like tuple counts and distinct value counts) stored in the database's catalog.
• Selectivity is the fraction of tuples that a predicate will match. Simple formulas exist for common predicates, but they rely on assumptions of uniform distribution and predicate independence.
• These assumptions are often violated by real-world data, which can lead to large estimation errors.
• Histograms are a key technique to combat data skew by storing a more detailed approximation of the data's distribution.

Preview of the Next Lesson

We've just scratched the surface of histograms. They are so critical to modern optimizers that they deserve their own lesson. In our next session, we will dive deeper, addressing the learning outcome: Describe how equi-width and equi-depth histograms are used to estimate predicate selectivity. We will look at their data structures, how they are constructed, and precisely how they are used to calculate more accurate selectivity for both equality and range predicates.