planner: duplicate expression indexes bind ORDER BY to an arbitrary hidden generated column, causing unstable plans and missed index selection
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Bug Report
When a table defines several expression indexes that repeat the **same** expression, TiDB creates one hidden generated column per index. The optimizer then binds an `ORDER BY` (or `WHERE`) occurrence of that expression to an **arbitrary** one of those hidden columns, chosen by Go map iteration order. The choice changes from one plan build to the next, so:
- the same query alternates between a good index plan and a full scan + `TopN` across executions, and
- when the arbitrary choice is not the index the optimizer wants to use, no access path can satisfy the ordering, so the index is silently not selected.
Adding `FORCE INDEX` makes the query fast again, which is what makes this look like a costing problem when it is not.
This was reported by a customer running [Temporal](https://github.com/temporalio/temporal) on TiDB. Temporal's `executions_visibility` schema repeats
```sql
COALESCE(close_time, CAST('9999-12-31 23:59:59' AS DATETIME))
```
in **30 different indexes**, so the query has roughly a 1-in-30 chance of binding to `default_idx`'s hidden column.
### 1. Minimal reproduce step (Required)
Requires `allow-expression-index = true` in the TiDB config.
```sql
drop table if exists t;
create table t (
ns char(64) not null,
run char(64) not null,
st datetime(6) not null,
ct datetime(6) null,
status int not null,
memo blob null,
primary key (ns, run)
);
-- five indexes repeating the SAME expression
create index default_idx on t (ns, (coalesce(ct, cast('9999-12-31 23:59:59' as datetime))), st, run);
create index by_a on t (ns, status, (coalesce(ct, cast('9999-12-31 23:59:59' as datetime))), st, run);
create index by_b on t (ns, memo(10), (coalesce(ct, cast('9999-12-31 23:59:59' as datetime))), st, run);
create index by_c on t (ns, st, (coalesce(ct, cast('9999-12-31 23:59:59' as datetime))), run);
create index by_d on t (ns, run, (coalesce(ct, cast('9999-12-31 23:59:59' as datetime))), st);
-- ~500 rows spread over 5 values of ns, then:
analyze table t;
```
Run this **repeatedly** — the plan is not stable:
```sql
explain format='brief'
select ns, run, st, ct, memo from t where ns = 'ns0'
order by coalesce(ct, cast('9999-12-31 23:59:59' as datetime)) desc, st desc, run desc
limit 20;
```
Over 200 plan builds on master (`052084c303`), the same statement produced:
```
127 IndexRangeScan on default_idx (keep order:true, desc) <- good
73 TableRangeScan + TopN <- bad
```
### 2. What did you expect to see? (Required)
A stable plan. `default_idx` is a prefix match for `ns` and then supplies exactly the requested ordering, so the query should consistently produce:
```
Projection
└─IndexLookUp 20.00 limit embedded(offset:0, count:20)
├─Limit(Build) 20.00 offset:0, count:20
│ └─IndexRangeScan 20.00 range:["ns0","ns0"], keep order:true, desc
└─TableRowIDScan(Probe) 20.00 keep order:false
```
This is exactly what `FORCE INDEX (default_idx)` produces today, on every run.
### 3. What did you see instead (Required)
Roughly a third of the time the plan degrades to a full scan of the `ns` range followed by a root `TopN`, reading every row for that namespace instead of 20:
```
TopN 20.00 coalesce(...)::desc, st:desc, run:desc, offset:0, count:20
└─TableReader 1000.00 data:TableRangeScan
└─TableRangeScan 1000.00 range:["ns0","ns0"], keep order:false
```
Root cause analysis
`collectGenerateColumn` in `pkg/planner/core/rule_generate_column_substitute.go` builds
```go
type ExprColumnMap map[expression.Expression]*expression.Column
```
keyed by the `expression.Expression` **interface value**, i.e. pointer identity. Each expression index owns its own hidden generated column (`_V$_default_idx_1`, `_V$_by_a_2`, …), and each of those has its own distinct `VirtualExpr` pointer even when the expressions are semantically identical. So N duplicate-expression indexes produce N separate map entries.
`GcSubstituter.substitute` (the `*logicalop.LogicalSort` case) then iterates that map in Go's randomized order and rewrites the sort item with whichever candidate matches first:
```go
for candidateExpr, column := range exprToColumn {
tryToSubstituteExpr(&x.ByItems[i].Expr, lp, candidateExpr, tp, x.Schema(), column)
}
```
Once substituted, the sort item is a `*expression.Column` and no longer matches any remaining candidate, so the first hit wins.
`matchProperty` (`pkg/planner/core/find_best_task.go`) compares the sort item against index columns with `sortItem.Col.EqualColumn(idxCols[colIdx])`, i.e. by `UniqueID`. If the sort item was bound to a different index's hidden column, no path matches the ordering and the plan falls back to a root `TopN`.
Instrumenting the substitution over 300 plan builds of the customer's real query (30 duplicate-expression indexes, map size 31) showed the choice spread across all candidates, with `default_idx`'s column selected only 23 times.
`FORCE INDEX` avoids the problem because index hints filter `PossibleAccessPaths` before this rule runs, so the map holds exactly one entry.
Deduplicating the map by expression equality makes the choice deterministic and restores the good plan for this query shape. That is only a partial fix, though: it binds the expression to a single canonical hidden column, so a query like `... where ns = ? and status = ? order by coalesce(...)` still cannot use `by_a` and instead gets `default_idx` plus a probe-side `Selection`. A complete fix likely needs #68032 (one hidden column per distinct expression at DDL time) and/or making property matching and range building treat virtual columns with equal `VirtualExpr` as interchangeable.
Same underlying cause as #67552 (wrong hidden column resolved, fixed by #67692) and #67055 (nil-pointer panic when the sort item is not available from the scanned index, fixed by #67319). Those two fixed the hard failures; this issue is the remaining plan-quality and plan-stability half, which is still present on master.
### 4. What is your TiDB version? (Required)
Reproduced on:
- `master` at `052084c303` — 73/200 plan builds degraded
- `release-8.5` at `679bbc290e` — 75/200 degraded
- `release-9.0-beta.2` at `339f07ae8f` — 25/200 degraded
Contributor guide
Research direction
Start in pkg/planner/core/rule_generate_column_substitute.go and trace collectGenerateColumn into GcSubstituter.substitute for LogicalSort. Use the supplied CREATE INDEX and EXPLAIN reproduction with allow-expression-index enabled; done means repeated plan builds are stable, the appropriate matching index is selected, and duplicate-expression access paths retain correct behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100