planner: keep min/max row estimates aligned after correlated column split (#70793)

Project: pingcap/tidb | Language: Go | Concepts: query-optimization, algorithmic-optimization, data-structures | Difficulty: senior
Link: https://github.com/pingcap/tidb/pull/70861

The problem

When the TiDB query planner handles correlated columns in index access (e.g., in subqueries), it splits correlated equality conditions out of static filters and re-derives row count estimates by dividing by the number of distinct values (NDV) of the correlated columns. However, it failed to update the minimum and maximum row estimates (MinCountAfterAccess and MaxCountAfterAccess) to match the new CountAfterAccess. This mismatch could cause the planner's skyline pruning logic to wrongly consider correlated index paths as "risky" and prune them, even when they are optimal, leading to suboptimal query plans.

Why it's non-trivial

A naive fix might only update the main row count estimate (CountAfterAccess) after splitting correlated conditions, but leave the min/max estimates untouched. Because skyline pruning compares all three values, leaving the min/max at their pre-split (possibly much larger) values introduces a false sense of risk, causing the planner to discard good plans. The fix must ensure all three estimates are updated in a consistent way, preserving any real estimation uncertainty contributed by other predicates.

The approach

1. Introduce a scaling function to align min/max counts with the new estimate:

+// scaleCorColCountAfterAccess scales the min/max row estimates by the same factor that
+// the correlated equalities applied to CountAfterAccess. Those equalities cannot be
+// turned into ranges at plan time, so CountAfterAccess is re-derived by dividing by the
+// NDV of each correlated column instead of being estimated from ranges, while the min/max
+// still describe the pre-split ranges. Leaving them means a path that started from a full
+// range keeps a table-sized max next to a one-row estimate, and the risk comparison in
+// skyline pruning drops it for phantom risk before cost is considered.
+//
+// Scaling rather than collapsing onto CountAfterAccess keeps whatever spread the
+// remaining (non-correlated) predicates contributed, so a path whose other predicates
+// carry genuine estimation risk is still reported as risky.
+func scaleCorColCountAfterAccess(path *util.AccessPath, countBeforeSplit float64) {
+	if countBeforeSplit <= 0 {
+		path.MinCountAfterAccess = path.CountAfterAccess
+		path.MaxCountAfterAccess = path.CountAfterAccess
+		return
+	}
+	scale := path.CountAfterAccess / countBeforeSplit
+	path.MinCountAfterAccess *= scale
+	path.MaxCountAfterAccess *= scale
+}

This function rescales the min and max count estimates by the same ratio as the main count estimate was changed by splitting correlated conditions. If the pre-split count is zero or negative, it collapses min/max to the new estimate.

2. Apply the scaling after splitting correlated columns in both index and common handle path stats:

@@ -224,6 +246,7 @@ func deriveIndexPathStats(ds *logicalop.DataSource, path *util.AccessPath, _ []e
 		accesses, remained := path.SplitCorColAccessCondFromFilters(ds.SCtx(), path.EqOrInCondCount)
 		path.AccessConds = append(path.AccessConds, accesses...)
 		path.TableFilters = remained
+		countBeforeSplit := path.CountAfterAccess
 		if len(accesses) > 0 && ds.StatisticTable.Pseudo {
 			path.CountAfterAccess = cardinality.PseudoAvgCountPerValue(ds.StatisticTable)
 		} else {
@@ -238,6 +261,9 @@ func deriveIndexPathStats(ds *logicalop.DataSource, path *util.AccessPath, _ []e
 				path.CountAfterAccess = path.CountAfterAccess / ndv
 			}
 		}
+		if len(accesses) > 0 {
+			scaleCorColCountAfterAccess(path, countBeforeSplit)
+		}

After correlated conditions are split and CountAfterAccess is updated, the scaling function is called to update min/max counts as well. The same logic is applied in deriveCommonHandleTablePathStats.

3. Add a regression test to ensure correlated index paths are not wrongly pruned:

+func TestCorrelatedColumnPathNotPrunedByRisk(t *testing.T) {
+	// ...setup omitted...
+	rows := tk.MustQuery(`explain format = 'brief'
+		select o.id, (select t.v from t where t.a = o.id and t.b = lpad(5,36,'0') limit 1) from t_outer o`).Rows()
+	plan := make([]string, 0, len(rows))
+	for _, row := range rows {
+		cols := make([]string, 0, len(row))
+		for _, col := range row {
+			cols = append(cols, fmt.Sprintf("%v", col))
+		}
+		plan = append(plan, strings.Join(cols, " "))
+	}
+	joined := strings.Join(plan, "\n")
+	require.Contains(t, joined, "index:idx_a(a) range: decided by [eq(test.t.a, test.t_outer.id)]", joined)
+	require.NotContains(t, joined, "index:idx_b(b)", joined)
+	// ...result check omitted...
+}

This test sets up a scenario where only the correlated index path (idx_a) should be chosen. It verifies that the planner does not prune it due to phantom risk and that the alternative (idx_b) is not selected.

From the review thread

No notable review discussion on this PR.

Takeaways

• When updating statistical estimates in query planning, always keep all related values (mean, min, max) consistent after transformations or splits.
• If a process changes the basis for an estimate (e.g., by splitting correlated conditions and re-deriving counts), propagate that change to all dependent statistics to avoid introducing phantom risks or inconsistencies.
• Regression tests for subtle planner behaviors should check not just results but also the chosen plan structure to guard against silent regressions.