planner: improve cardinality estimation for composite-index IndexRangeScan
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
### Motivation
TiDB’s cost-based optimizer may overestimate the cardinality of a composite-index `IndexRangeScan` when multiple predicates are applied to indexed columns together with additional index or table filters.
For example:
```sql
CREATE INDEX idx_a_b_c ON t(a, b, c);
SELECT *
FROM t
WHERE a = ?
AND b IN (?, ?, ?)
AND c BETWEEN ? AND ?
AND d = ?;
```
When the indexed columns are correlated, or when residual filters are highly selective, estimating each predicate independently may produce an overly large row count for the index access path. This can affect access path comparison and subsequent cost-based plan selection.
### Proposed enhancement
Improve composite-index cardinality estimation by considering:
- Correlations among columns in a composite index;
- The selectivity of residual index filters;
- Correlations between index columns and table filters;
- The distinction between index access rows, rows after index filters, and final rows after table filters.
The estimator should provide more robust estimates for multi-column predicates instead of relying primarily on independent selectivity assumptions.
### Expected outcome
Improve the accuracy of `IndexRangeScan` cardinality and cost estimation, leading to more reliable access path selection for queries involving composite indexes and correlated predicates.
A plan replayer bundle with the schema, statistics, optimizer trace, and `EXPLAIN ANALYZE` output is available as a supporting artifact.
### Environment
TiDB v8.5.x
Contributor guide
Research direction
Start with the available plan replayer bundle, including its schema, statistics, optimizer trace, and EXPLAIN ANALYZE output, then trace the IndexRangeScan estimate through the composite-index predicates and residual filters. Done means the estimator produces more accurate access, post-index-filter, and final row estimates for the supplied correlated-predicate case and improves access-path selection.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100