Join Cardinality and Where the Containment Assumption Fails

A single-table estimate has a clear meaning: what fraction of rows satisfy this predicate. A join estimate is different in kind, because the answer depends on the relationship between two distributions, and the catalog stores those distributions separately, one column at a time. The standard formula bridges that gap with an assumption about uniformity that is stated nowhere in the query and is almost never true of the data. Every downstream decision, from join order to join algorithm, is built on the resulting number.

The formula is worth writing down because it explains both the successes and the failures. For an equijoin between relations A and B on columns with V distinct values, the estimate is:

$$|A \bowtie B| = \frac{|A| \cdot |B|}{V}$$

where V is taken as the larger of the two columns’ distinct-value counts. The reasoning is that each row of A matches the fraction $1/V$ of B that carries its key value. That reasoning is exactly right when every key value appears equally often in both relations and both relations draw from the same set of values. It is wrong in every other case, and the size of the error depends on which assumption is violated.

Why the divisor is the larger distinct count

Choosing the larger of the two counts follows from the containment assumption: the smaller set of distinct values is assumed to be contained in the larger. If table A has 1,000 distinct customer identifiers and table B has 50,000, the assumption is that A’s thousand customers are among B’s fifty thousand, so each of A’s rows finds a match in B and the divisor should be B’s count.

When the assumption holds, the estimate is a straightforward application of uniform frequency. When it fails, the formula overestimates by however much of A is missing from B. A foreign-key relationship is the common case where the containment holds exactly, which is why estimates across a well-formed schema are usually reasonable: the referenced table’s key set contains the referencing table’s values by construction.

The failure case is a join on a column that is not a foreign key, or a join across tables loaded from different sources. If A’s distinct values are entirely disjoint from B’s, the true result is empty and the formula still predicts millions of rows. The optimizer then treats a join that produces nothing as the most expensive step in the plan, and orders the remaining joins around a phantom intermediate result. Nothing in the statistics detects this, because each column’s histogram describes its own values and nothing compares the two sets.

Skew defeats the uniform-frequency premise

Even with containment satisfied, the formula assumes each key value appears the same number of times in both relations. Consider a fact table of orders joined to a customer table on customer_id, where one customer accounts for a large share of the orders. The orders table’s histogram lists that customer as a most-common value, but the join formula does not consult per-value frequencies at all. It divides the whole product by the distinct count.

The consequence is that the estimate for the join is a global average and is correct only in aggregate. It does not matter that the average is right when the query adds a predicate selecting the skewed customer: WHERE customer_id = 42 on the orders side makes the join selectivity that of a single value, and the correct estimate is the frequency of that value in the orders table times the frequency in the customers table, not the global average. An estimator that applies the per-column most-common-value list to each side before the join gets this case right, which is why the order in which predicates are pushed down matters to the estimate and not only to the execution.

The harder case is skew that is not extreme enough to make a most-common-value list. A distribution where the top hundred values each appear a thousand times and the remaining million appear once has a flat-looking histogram inside its buckets and a most-common-value list that holds only a fraction of the heavy hitters. Joins on those values are underestimated, sometimes by a factor in the hundreds, and the resulting plan chooses a nested loop where a hash join was needed. The reverse skew, where a few values dominate a dimension table, produces the opposite error.

A partial mitigation is to compare the distinct counts of the two join columns. When they differ by orders of magnitude, the assumption that one contains the other is strained, and some estimators reduce the estimate accordingly. That correction is a heuristic, not a derivation, and it trades one error for another.

Compounding across a chain of joins

A three-way join is estimated by joining the first two and then joining the result to the third, which means the second estimate consumes the first estimate’s output size. If the first estimate is off by a factor of ten, the second inherits that factor, and the third inherits it again. The error does not average out; it multiplies.

This compounding is why a query that joins five tables can have a final estimate that is wrong by six orders of magnitude even when each individual step is only modestly off. It also explains an asymmetry in how errors hurt: an overestimate early in the chain inflates every subsequent intermediate, which pushes the optimizer toward hash joins and large memory grants, while an underestimate pushes it toward nested loops that then execute far more iterations than planned. The second failure is usually the more damaging, because a nested loop whose inner side is re-executed per outer row turns a linear cost into a product.

Because the search described in join order search and the plan space scores every candidate order with these estimates, an error early in the chain does not merely misprice one plan, it reorders the candidates. A plan that is genuinely cheapest can be discarded because its intermediate was estimated as huge, and a plan that is genuinely expensive can win because its intermediate was estimated as tiny.

Filters above joins and the selectivity of the result

Predicates applied after a join are estimated by multiplying the join’s output by the predicate’s selectivity, which requires assuming that the predicate’s column is independent of the join keys. That assumption fails whenever a filter constrains the same dimension the join traverses: a join between orders and customers followed by a filter on customer country restricts rows that the join already grouped, and multiplying treats the two as independent events.

The result is the familiar correlated-predicate error, now at the level of a join output rather than a base table. Estimates too low by a factor of ten or more are common for queries of the form “join to a dimension, filter on two attributes of that dimension”. Extended statistics over the dimension’s column pair fix the base estimate, and the join’s output then inherits a better number.

A second subtlety is that the join’s output row width affects the cost of everything above it, not just the row count. A hash join that produces a wide intermediate result consumes memory proportional to rows times width, so an underestimated row count with an underestimated width can understate the memory needed by a large factor, and the plan that the optimizer believed would stay in memory spills to disk instead.

The estimates that survive contact with reality

Two properties make some join estimates trustworthy and others not. First, a join on a primary key to foreign key with a declared constraint is estimated well, because the containment holds by definition and the key’s distinct count equals the referenced table’s row count. Second, a join where both sides have histograms over the join column and the estimator compares bucket boundaries can detect disjoint ranges and return zero; implementations that do this comparison avoid the worst failure mode above.

For everything else, the practical approach is empirical rather than theoretical. The estimated and actual row counts at each join node in EXPLAIN ANALYZE show where the chain first diverges, and that node is where the statistics need attention. Fixing the fifth join’s estimate when the second join was already off by a hundred is wasted work, because the numbers above it were computed from a wrong input.

Some engines respond to the problem structurally rather than statistically. Instead of trusting the estimate, they measure the actual cardinality at a blocking point in the plan and re-plan the remainder with the measured value. That mechanism is the subject of adaptive re-optimization during execution, and it trades planning-time certainty for a second planning pass that only pays off when the first estimate was wrong.