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/70884
The problem
When planning an IndexJoin, the optimizer sometimes compares access paths unfairly in skyline pruning. Specifically, if a candidate access path uses a column-to-column join equality as its lookup key (e.g., i.k = o.id), the estimated row count (CountAfterAccess) can be much higher than reality, because the join key's selectivity is not reflected at plan time. This can cause the planner to pick a suboptimal index.
Why it's non-trivial
A naive fix would just use the original CountAfterAccess for all comparisons, but this ignores the fact that, at runtime, the join key acts as a filter (with selectivity equal to the NDV of the join key). Not accounting for this leads to underestimating the efficiency of certain indexes. However, blindly adjusting for NDV can also be unsafe if statistics are missing, unstable, or if there are multiple join keys.
The approach
1. Add join-aware access count fields to candidatePath
+ countAfterAccess4IndexJoin float64 // adjusted CountAfterAccess used only by index join candidate comparison.
+ countAfterAccess4IndexJoinOK bool // whether countAfterAccess4IndexJoin is stable enough for skyline pruning.
What it does:
Adds fields to store an adjusted row count for IndexJoin scenarios and a flag indicating if the adjustment is reliable.
2. Compute join-aware row count for IndexJoin
+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 find single join key col, check stats, etc ...
+ if !needNDVAdjust || colStats.NDV == 1 {
+ return path.CountAfterAccess, true
+ }
+ return path.CountAfterAccess / float64(colStats.NDV), true
+}
What it does:
If possible, divides the original access count by the NDV of the join key column, but only if statistics are available, the join key is a single column, and other safety checks pass. Otherwise, falls back to the original count and marks the adjustment as unreliable.
3. Use the join-aware count in candidate construction
+ countAfterAccess4IndexJoin, countAfterAccess4IndexJoinOK := indexJoinPathCountAfterAccess4Compare(indexJoinInfo, path, idxOff2KeyOff, usedColsLen)
+ return &indexJoinPathResult{
+ chosenPath: path,
+ candidate: getIndexCandidateForIndexJoin(sctx, path, usedColsLen, countAfterAccess4IndexJoin, countAfterAccess4IndexJoinOK),
What it does:
Passes the computed join-aware count and its reliability flag into the candidate.
4. Use the adjusted count in skyline pruning comparison
+func (c *candidatePath) getCountAfterAccess4SkylinePruning() (float64, bool) {
+ if c.indexJoinCols > 0 {
+ if !c.countAfterAccess4IndexJoinOK {
+ return 0, false
+ }
+ return c.countAfterAccess4IndexJoin, true
+ }
+ return c.path.CountAfterAccess, true
+}
What it does:
Provides the correct count for skyline pruning: the adjusted count for IndexJoin candidates (if reliable), otherwise the original.
- if lhs.path.CountAfterAccess > 100 && rhs.path.CountAfterAccess > 100 && // ...
+ if lhsCountAfterAccessOK && rhsCountAfterAccessOK &&
+ lhsCountAfterAccess > 100 && rhsCountAfterAccess > 100 && // ...
What it does:
Only uses the empirical row-count rule if both candidates have reliable counts.
5. Add regression test
+func TestIssue70757IndexJoinInnerIndexSelection(t *testing.T) {
+ // ... setup tables, insert data ...
+ 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)")
+}
What it does:
Verifies that the planner now prefers the correct index (idx_k) for the IndexJoin, as expected.
From the review thread
No notable review discussion on this PR.
Takeaways
- When estimating row counts for join operations, adjust for the selectivity of join keys if statistics are available and stable.
- Only apply aggressive pruning or comparison rules when you are confident in the reliability of your cost estimates.
- Always add regression tests for subtle planner bugs to ensure future changes do not reintroduce them.