Optimizers typically estimate the combined selectivity of two AND-ed predicates by multiplying their individual selectivities. Explain the assumption behind that, describe a realistic case where it fails badly, and how you would address it.

## Why independence is assumed at all Statistics are stored per column: row count, distinct-value count, null fraction, a histogram, a most-common-value list. From those, the optimizer can estimate any single predicate. But a query with several predicates needs the *joint* distribution, and storing joint distributions is infeasible — a table with 30 columns has 435 pairs, and higher-order combinations explode from there. So optimizers make the only tractable default assumption: the columns are statistically independent, and `sel(A AND B) = sel(A) × sel(B)` with the analogous inclusion–exclusion form for OR. This is not laziness; it is the one assumption that makes per-column statistics sufficient. It happens to be right often enough — genuinely unrelated attributes such as an account's balance and its country really are close to independent. ## The failure mode It breaks whenever the predicates restrict overlapping information. Take a 10-million-row address table: - `city = 'Springfield'` matches 10,000 rows → selectivity 0.001 - `state = 'IL'` matches 200,000 rows → selectivity 0.02 Independence gives combined selectivity `0.001 × 0.02 = 0.00002` → an estimate of **200 rows**. But the vast majority of Springfield rows in this data are in Illinois, so the true count is close to 10,000 — a **50× under-estimate**. The optimizer double-counted a restriction that had already been applied: knowing the city almost determines the state. The general rule: when a **functional dependency** or a strong statistical association exists between columns, independence under-estimates, and the error scales with the strength of the association and the number of correlated predicates. Three correlated predicates can under-estimate by several orders of magnitude. The same trap appears across joins. If a filter on one table correlates with the join key distribution, join cardinality estimates inherit the error and it compounds upward. Note the direction: correlated AND-ed predicates almost always *under*-estimate, which is the dangerous direction. Under-estimation selects fragile plans — a nested loop whose inner side gets probed once per outer row, an index seek plus row lookups where a scan was right, a hash table sized far too small. Those are exactly the plans that degrade catastrophically rather than gracefully when the real row count shows up. ## Recognizing it in the wild Signals: - An executed plan where a base-table access or a filter shows estimated rows in the tens or hundreds and actual rows in the hundreds of thousands, with **multiple predicates on the same table**. - The estimate is approximately the product of what each predicate alone would give — a quick sanity check that the independence assumption is the culprit rather than stale statistics. - Predicate column names that hint at a hierarchy: city/state/country, product/category, model/make, postcode/region, service/datacenter. - Refreshing statistics does not help, because each individual column's statistics were already accurate. This is the tell that distinguishes correlation from staleness. ## Remedies in order of preference **1. Multi-column / extended statistics.** All major engines offer a way to record joint information about a column set: functional dependency degree, joint distinct counts, and in some cases multivariate MCV lists. Creating them on the correlated set lets the optimizer stop multiplying and use the recorded joint behaviour. This is targeted, cheap, and does not change the query or the schema — the default first move. The costs are extra maintenance on statistics collection and the fact that you must know which column sets to declare, which is why it is reactive rather than automatic. **2. Remove the redundancy.** A hard functional dependency like city→state usually means the schema stores derived data. Normalizing it away — the city row carries the state, and queries join — eliminates both the estimation problem and a class of data-integrity bugs. Not always the right call for a denormalized read path, but worth naming, because the estimation problem is a symptom of the modeling choice. **3. Materialize the combination.** A generated/computed column holding the combined key, indexed and analyzed, gives the optimizer a single column with accurate statistics for the predicate that matters. Useful when the correlated predicates always appear together. **4. Reshape the query.** Sometimes the redundant predicate can simply be dropped — if city already implies state, the state predicate adds nothing but estimation error. This requires the dependency to be a real invariant, not merely usual. **5. Robustness over optimality.** Where the workload cannot tolerate a plan flip, hints, plan baselines, or forced plans pin a known-good plan. Treat this as a containment measure with an expiry: it freezes behaviour, including freezing out better plans as the data changes. **6. Execution-time adaptivity.** Some engines can re-plan or switch operators when observed cardinalities diverge from estimates, or feed observed counts back for the next compile. Where available, this addresses the general problem rather than the one query. ## What a strong answer includes Name the assumption, explain *why* it exists (per-column statistics cannot represent joint distributions), give a concrete correlated example with numbers, state that the error direction is under-estimation and that under-estimation selects fragile plans, and offer multi-column statistics as the first tool while acknowledging that the deeper issue is often a functional dependency stored in the schema.