TopN can be evaluated inside IndexLookUpReader sometimes if there's no filter on table side
- 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
Assessment
This issue has not been assessed yet.