planner: fix countAfterAccess for IndexJoin in Skyline Pruning Comparison

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

The problem

When TiDB chooses an index for the inner side of an IndexJoin, it uses a process called skyline pruning to compare candidate indexes. The comparison uses the CountAfterAccess value, which estimates the number of rows accessed by the index. However, if the index access uses a join key (like i.k = o.id), this value can be misleading: at planning time, the join key's value is unknown, so the estimate is too high (like a full scan), even though at runtime the join key is used as a lookup key. This can cause the optimizer to pick a suboptimal index.

Why it's non-trivial

A naive fix would just use the original CountAfterAccess for all comparisons, but this doesn't account for the fact that, in an IndexJoin, the join key will be used for lookups, and the actual accessed rows should be divided by the number of distinct values (NDV) of the join key. However, adjusting by NDV is only safe when statistics are available and reliable; otherwise, the adjustment could be incorrect and lead to worse plans.

The approach

1. Add new fields to candidatePath to track adjusted row count and its reliability:

-type candidatePath struct {
-	partialPathMatchResults []property.PhysicalPropMatchResult
-	indexJoinCols           int  // how many index columns are used in access conditions in this IndexJoin.
-	isFullRange             bool // cached result of whether this path covers the full scan range.
-	eqOrInCount             int  // cached result of equalPredicateCount().
+type candidatePath struct {
+	partialPathMatchResults      []property.PhysicalPropMatchResult
+	indexJoinCols                int     // how many index columns are used in access conditions in this IndexJoin.
+	countAfterAccess4IndexJoin   float64 // adjusted CountAfterAccess used only by index join candidate comparison.
+	countAfterAccess4IndexJoinOK bool    // whether countAfterAccess4IndexJoin is stable enough for skyline pruning.
+	isFullRange                  bool    // cached result of whether this path covers the full scan range.
+	eqOrInCount                  int     // cached result of equalPredicateCount().
 }

This change lets each candidate track both the adjusted row count for IndexJoin and whether that adjustment is trustworthy.

2. Use adjusted count in skyline pruning comparison if available and reliable:

-func compareCandidates(sctx base.PlanContext, statsTbl *statistics.Table, prop *
-	if lhs.path.CountAfterAccess > 100 && rhs.path.CountAfterAccess > 100 && // to prevent some extreme cases, e.g. 0.01 : 10
+	lhsCountAfterAccess, lhsCountAfterAccessOK := lhs.getCountAfterAccess4SkylinePruning()
+	rhsCountAfterAccess, rhsCountAfterAccessOK := rhs.getCountAfterAccess4SkylinePruning()
+	if lhsCountAfterAccessOK && rhsCountAfterAccessOK &&
+		lhsCountAfterAccess > 100 && rhsCountAfterAccess > 100 && // to prevent some extreme cases, e.g. 0.01 : 10

Now, skyline pruning uses the NDV-adjusted count for comparison, but only if both candidates have a trustworthy adjustment.

3. Calculate the NDV-adjusted count only when safe:

+func indexJoinPathCountAfterAccess4Compare(
+	indexJoinInfo *indexJoinPathInfo,
+	path *util.AccessPath,
+	idxOff2KeyOff []int,
+	usedColsLen int,
+) (countAfterAccess4IndexJoin float64, countAfterAccess4IndexJoinOK bool) {
+	if path.CountAfterAccess <= 0 ||
+		indexJoinInfo.innerTableStats == nil ||
+		indexJoinInfo.innerTableStats.StatsVersion == statistics.PseudoVersion ||
+		indexJoinInfo.innerTableStats.HistColl == nil {
+		return path.CountAfterAccess, false
+	}
+	// ... (logic to ensure only one join key, stats are initialized, etc.)
+	return path.CountAfterAccess / float64(colStats.NDV), true
+}

This function performs the NDV adjustment only if statistics are reliable, and only for a single, non-prefix join key.

4. Pass the NDV-adjusted value into candidate creation:

-func getIndexCandidateForIndexJoin(sctx planctx.PlanContext, path *util.AccessPath, indexJoinCols int) *candidatePath {
-	candidate := &candidatePath{path: path, indexJoinCols: indexJoinCols}
+func getIndexCandidateForIndexJoin(sctx planctx.PlanContext, path *util.AccessPath, indexJoinCols int, countAfterAccess4IndexJoin float64, countAfterAccess4IndexJoinOK bool) *candidatePath {
+	candidate := &candidatePath{
+		path:                         path,
+		indexJoinCols:                indexJoinCols,
+		countAfterAccess4IndexJoin:   countAfterAccess4IndexJoin,
+		countAfterAccess4IndexJoinOK: countAfterAccess4IndexJoinOK,
+	}

This ensures that the candidate's adjusted count and its reliability are set at creation.

5. Add a regression test to verify the fix:

+func TestIssue70757IndexJoinInnerIndexSelection(t *testing.T) {
+	// ... setup code ...
+	query := `select /*+ inl_join(i) */ * from t_outer o join t_inner i on i.k = o.id and i.c = o.c where o.c = 'cust-1'`
+	plan := tk.MustQuery("explain format='plan_tree' " + query)
+	plan.CheckContain("outer key:test.t_outer.id, inner key:test.t_inner.k")
+	plan.CheckContain("table:i, index:idx_k(k)")
+	plan.CheckNotContain("table:i, index:idx_c(c)")
+}

This test ensures that the optimizer now prefers the correct index (idx_k) for the join, not the misleadingly small idx_c.

From the review thread

No notable review discussion on this PR.

Takeaways

• When comparing query plans, always adjust row count estimates to reflect how runtime values (like join keys) will restrict access, but only if statistics are reliable.
• Avoid applying aggressive pruning or heuristics when the underlying data statistics are missing, pseudo, or ambiguous.
• Regression tests are critical to lock in subtle optimizer behaviors and prevent future regressions in plan selection.