pingcap / pingcap/tidb

planner: prefer bounded ordered IndexLookUp for TopN under incomplete stats

Open
#69,405 1 comment 0 reactions 0 assignees View on GitHub
component/statistics epic/cost-model sig/planner type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement

### Summary

For very large OLTP tables, statistics TopN may not include every high-frequency equality value that is still large enough to matter for query planning. In that case, TiDB can underestimate a range scan under `TopN` and choose a table reader, even though there is an ordered index lookup candidate whose work is bounded by `LIMIT + OFFSET`.

The planner should consider preferring a pure bounded ordered `IndexLookUp` for narrow `ORDER BY ... LIMIT` cases when the final plan shape proves that:

- the index scan keeps the required order,
- all filters are covered by index access conditions,
- the table side is only row lookup without residual filters,
- and the lookup work is bounded by a small `LIMIT + OFFSET` threshold.

### Anonymized query shape

The original report involved a production table and values. The following schema and query are anonymized and keep only the relevant optimizer shape:

```sql
CREATE TABLE edge_like (
id BIGINT PRIMARY KEY,
source_id BIGINT NOT NULL,
is_active TINYINT NOT NULL,
score BIGINT NOT NULL,
target_id BIGINT NOT NULL,
payload_type INT,
KEY ordered_edge_idx (source_id, is_active, score, target_id),
KEY source_idx (source_id)
);

SELECT score, target_id, is_active, payload_type, source_id
FROM edge_like
WHERE source_id = AND is_active = 1
ORDER BY source_id DESC, score DESC, target_id DESC
LIMIT 26;
```

### Observed behavior

Without an index hint, the optimizer may choose a table reader plan similar to:

```text
Projection
└─TopN
└─TableReader
└─TopN
└─Selection(is_active = 1)
└─TableRangeScan range:[, ]
```

This can be bad when `source_id = ` is much larger in reality than the stats estimate. The table reader has to scan the whole matching table range before returning the top rows.

### Expected behavior

The optimizer should allow the following bounded ordered index lookup shape to win in this narrow case:

```text
Projection
└─IndexLookUp limit embedded(offset:0, count:26)
├─Limit(Build)
│ └─IndexRangeScan index:ordered_edge_idx(source_id, is_active, score, target_id), keep order:true, desc
└─TableRowIDScan(Probe)
```

The key difference is that the build side can stop after reading a small ordered window, and the probe side only looks up those rows. There is no table-side residual filter that could make "limit before lookup" semantically unsafe.

### Why this is not just a statistics TopN issue

Increasing analyze TopN size does not reliably solve this for very large OLTP tables because there may be many long-tail values that are still large enough to make a table range scan expensive. The safer signal is the final physical plan shape: if TiDB has a pure ordered `Limit -> IndexRangeScan -> TableRowIDScan` candidate, the execution work is bounded even when stats underestimate the equality value.

### Suggested scope

This should be a narrow planner enhancement, not a global discount for all index lookups:

- only for normal `ORDER BY ... LIMIT` / `TopN` cases,
- only when `LIMIT + OFFSET` is under a session/global threshold,
- only when the final `IndexLookUp` has `PushedLimit`,
- only when the index side is ordered and the table side is a pure table row lookup,
- do not apply to table-side selection, root residual selection, IndexMerge, TiFlash/MPP, partition merge-sort, partial-order prefix index, or large offsets.

### Related notes

An implementation design was prepared locally under `.codexpotter` and can be summarized in a follow-up comment.

Contributor guide

Open the contributing guide

Research direction

Start with the anonymized edge_like schema and query, then inspect the planner's final physical plan for the table reader and ordered IndexLookUp alternatives. Read the implementation design referenced under .codexpotter if available. Done means the narrow bounded ordered IndexLookUp case is preferred while the listed exclusions remain unchanged.

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
32/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.