Concepts and theorems · Intermediate

Cardinality estimation: predict row counts at each plan stage

Trace filter and join estimates and explain how row-count errors affect physical execution choices.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Plans need estimated input sizes
  2. Calculate a filter before a join
  3. Underestimates can amplify repeated work
  4. Find the first substantial divergence
  5. Ask Logeia about this articleCheck your understanding

Plans need estimated input sizes

Cardinality estimation predicts how many rows an operation such as a scan, filter or join will produce. Before execution, the planner cannot run every candidate plan to discover its true cost. It uses statistics and predicate information to estimate sizes, then chooses access and join methods using those estimates. The word cardinality can also refer to the number of distinct values in a column, so identify what is being counted. Here the main concern is the rows produced by each plan node, which can become the input volume for another operation higher in the plan.

Calculate a filter before a join

Start with one million rows in A and an estimated matching fraction of 0.02, giving 20,000 rows after filtering. If each retained row joins to exactly one unique key in B and every row has a match, the inner join still produces 20,000 rows. Without uniqueness on B, multiple matches can increase the output. The calculation therefore needs key and matching assumptions, not just a filter fraction. Distinct values, nulls and unmatched rows matter too. An estimate is intelligible only when its assumptions correspond to the actual join and data constraints.

Underestimates can amplify repeated work

A plan chosen for an outer input of ten rows may perform an inner lookup per row. If the actual outer input is 100,000 rows, that inner work repeats much more often than expected. This does not make nested loops inherently bad; sufficiently cheap inner lookups can still be attractive. Overestimates can also select unnecessary setup work or memory use. Ask how an error propagates into a particular cost. Relate row counts and loop counts instead of judging a plan by its operator names alone. The same physical method can behave well or poorly for different input sizes.

Find the first substantial divergence

When comparing estimates and measurements, locate the first substantial divergence rather than only the large error at the top of the plan. Candidate explanations include stale statistics, skew, predicate correlation, expression handling and parameter-dependent distributions. Some displayed actual row counts are per-loop averages, so interpret them together with loops rather than treating them as a total. Updating statistics is a useful experiment, not a guaranteed cure. Constraints and query meaning can matter as well. After a change, compare the correct result and execution under the same representative inputs to assess whether the proposed explanation was supported.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 12

Choose a learning path