Push down limit on IndexLookUp operator may improve performance in some scene

[tiancaiamao]

Performance Questions

• What version of TiDB are you using?

3.0-rc2

• What's the observed and your expected performance respectively?

Given a table like this:

mysql> create table t (id int, status int, c int, index u(id, status));
Query OK, 0 rows affected (0.00 sec)

and a query:

mysql> explain select * from t where id = 57894365 and status <> 2 limit 2000000, 10;
+--------------------------+-------+------+-------------------------------------------------------------------------------------------------------------------------+
| id                       | count | task | operator info                                                                                                           |
+--------------------------+-------+------+-------------------------------------------------------------------------------------------------------------------------+
| Limit_9                  | 10.00 | root | offset:2000000, count:10                                                                                                |
| └─IndexLookUp_18         | 10.00 | root |                                                                                                                         |
|   ├─Limit_17             | 10.00 | cop  | offset:0, count:2000010                                                                                                 |
|   │ └─IndexScan_15       | 66.57 | cop  | table:t, index:id, status, range:[57894365 -inf,57894365 2), (57894365 2,57894365 +inf], keep order:false, stats:pseudo |
|   └─TableScan_16         | 10.00 | cop  | table:t, keep order:false, stats:pseudo                                                                                 |
+--------------------------+-------+------+-------------------------------------------------------------------------------------------------------------------------+
5 rows in set (0.00 sec)

We can observe from the explain result that:

First, the value of the count column of Limit_17 is misleading, it should not be 10.00.
Actually, the Limit_17 operator would scan 2000010 keys and return it to IndexLookUp_18

Then, IndexLookUp_18 would get more than 2000010 index values to double read the table data, this process could be quite slow since it takes many network roundtrip.

Finally the Limit_9 would read from IndexLookUp_18 and drop the first 2000000 records.

There's room for improvement.
If we let the limit operator work on the aggregated index data, we can avoid reading 2000010 records in TableScan_16 (and drop most of them).

mysql> explain select * from t where id = 57894365 and status <> 2 limit 2000000, 10;
+--------------------------+-------+------+-------------------------------------------------------------------------------------------------------------------------+
| id                       | count | task | operator info                                                                                                           |
+--------------------------+-------+------+-------------------------------------------------------------------------------------------------------------------------+
| IndexLookUp_18         | 10.00 | root | offset:2000000, count:10
| ├─Limit_17             | 10.00 | cop  | offset:0, count:2000010                                                                                                 |
| │ └─IndexScan_15       | 66.57 | cop  | table:t, index:id, status, range:[57894365 -inf,57894365 2), (57894365 2,57894365 +inf], keep order:false, stats:pseudo |
| └─TableScan_16         | 10.00 | cop  | table:t, keep order:false, stats:pseudo                                                                                 |
+--------------------------+-------+------+-------------------------------------------------------------------------------------------------------------------------+
5 rows in set (0.00 sec)