pingcap / pingcap/tidb

TopN can be evaluated inside IndexLookUpReader sometimes if there's no filter on table side

Open
#57,941 1 comment 0 reactions 1 assignee Claimed by @King-Dylan View on GitHub
sig/execution sig/planner sig/sql-infra type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement

Suppose we have the table
```sql
create table t(
a int primary key,
b int,
c int,
d int,
index idx(b, c)
);
```

Then we run sqls like
```
mysql> explain select /*+ limit_to_cop() */ d from t use index(idx) order by a limit 9000, 1000;
+------------------------------------+----------+-----------+--------------------------+-----------------------------------+
| id | estRows | task | access object | operator info |
+------------------------------------+----------+-----------+--------------------------+-----------------------------------+
| Projection_7 | 1000.00 | root | | test.t.d |
| └─TopN_9 | 1000.00 | root | | test.t.a, offset:9000, count:1000 |
| └─IndexLookUp_16 | 10000.00 | root | | |
| ├─TopN_15(Build) | 10000.00 | cop[tikv] | | test.t.a, offset:0, count:10000 |
| │ └─IndexFullScan_13 | 10000.00 | cop[tikv] | table:t, index:idx(b, c) | keep order:false, stats:pseudo |
| └─TableRowIDScan_14(Probe) | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
+------------------------------------+----------+-----------+--------------------------+-----------------------------------+
6 rows in set (0.01 sec)

mysql> explain select /*+ limit_to_cop() */ d from t use index(idx) order by c limit 9000, 1000;
+------------------------------------+----------+-----------+--------------------------+-----------------------------------+
| id | estRows | task | access object | operator info |
+------------------------------------+----------+-----------+--------------------------+-----------------------------------+
| Projection_7 | 1000.00 | root | | test.t.d |
| └─TopN_9 | 1000.00 | root | | test.t.c, offset:9000, count:1000 |
| └─IndexLookUp_16 | 10000.00 | root | | |
| ├─TopN_15(Build) | 10000.00 | cop[tikv] | | test.t.c, offset:0, count:10000 |
| │ └─IndexFullScan_13 | 10000.00 | cop[tikv] | table:t, index:idx(b, c) | keep order:false, stats:pseudo |
| └─TableRowIDScan_14(Probe) | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
+------------------------------------+----------+-----------+--------------------------+-----------------------------------+
6 rows in set (0.01 sec)
```
The TopN can be pushed down. But the offset is eliminated. This is because that we can not guarantee the offset in partial TopN executed in each region.

But we actually can evaluate the TopN on the TiDB side inside the IndexLookUpReader and before the table executor is triggered. In This way, the table side will only need to read the needed rows, instead of fetching a lot of rows to do the TopN later.

It's something like
```
mysql> explain select /*+ limit_to_cop() */ d from t use index(idx) order by a limit 9000, 1000;
+------------------------------------+----------+-----------+--------------------------+-------------------------------------------------+
| id | estRows | task | access object | operator info |
+------------------------------------+----------+-----------+--------------------------+-------------------------------------------------+
| Projection_7 | 1000.00 | root | | test.t.d |
| └─IndexLookUp_16 | 10000.00 | root | | embeded topn(test.t.a, offset: 9000, limit 1000 |
| ├─TopN_15(Build) | 10000.00 | cop[tikv] | | test.t.a, offset:0, count:10000 |
| │ └─IndexFullScan_13 | 10000.00 | cop[tikv] | table:t, index:idx(b, c) | keep order:false, stats:pseudo |
| └─TableRowIDScan_14(Probe) | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
+------------------------------------+----------+-----------+--------------------------+-------------------------------------------------+
6 rows in set (0.01 sec)

mysql> explain select /*+ limit_to_cop() */ d from t use index(idx) order by c limit 9000, 1000;
+------------------------------------+----------+-----------+--------------------------+-------------------------------------------------+
| id | estRows | task | access object | operator info |
+------------------------------------+----------+-----------+--------------------------+-------------------------------------------------+
| Projection_7 | 1000.00 | root | | test.t.d |
| └─IndexLookUp_16 | 10000.00 | root | | embeded topn(test.t.c, offset: 9000, limit 1000 |
| ├─TopN_15(Build) | 10000.00 | cop[tikv] | | test.t.c, offset:0, count:10000 |
| │ └─IndexFullScan_13 | 10000.00 | cop[tikv] | table:t, index:idx(b, c) | keep order:false, stats:pseudo |
| └─TableRowIDScan_14(Probe) | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
+------------------------------------+----------+-----------+--------------------------+-------------------------------------------------+
6 rows in set (0.01 sec)
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.