Push down sort property to range partition table

[lysu]

Bug Report

Please answer these questions before submitting your issue. Thanks!

1. Minimal reproduce step (Required)

mysql> create table t1(id int primary key, v int) partition by range(id) (partition p1 values less than(10000), partition p2 values less than(20000));
Query OK, 0 rows affected (0.01 sec)

mysql> create table t2(id int primary key, v int);
Query OK, 0 rows affected (0.01 sec)

mysql> explain select * from t1 where id > 20001 order by id limit 1;
+-----------------------------+---------+-----------+----------------+----------------------------------------------------+
| id                          | estRows | task      | access object  | operator info                                      |
+-----------------------------+---------+-----------+----------------+----------------------------------------------------+
| TopN_8                      | 1.00    | root      |                | test.t1.id, offset:0, count:1                      |
| └─TableReader_17            | 1.00    | root      | partition:dual | data:TopN_16                                       |
|   └─TopN_16                 | 1.00    | cop[tikv] |                | test.t1.id, offset:0, count:1                      |
|     └─TableRangeScan_15     | 3333.33 | cop[tikv] | table:t1       | range:(20001,+inf], keep order:false, stats:pseudo |
+-----------------------------+---------+-----------+----------------+----------------------------------------------------+
4 rows in set (0.00 sec)

mysql> explain select * from t2 where id > 20001 order by id limit 1;
+-----------------------------+---------+-----------+---------------+---------------------------------------------------+
| id                          | estRows | task      | access object | operator info                                     |
+-----------------------------+---------+-----------+---------------+---------------------------------------------------+
| Limit_12                    | 1.00    | root      |               | offset:0, count:1                                 |
| └─TableReader_22            | 1.00    | root      |               | data:Limit_21                                     |
|   └─Limit_21                | 1.00    | cop[tikv] |               | offset:0, count:1                                 |
|     └─TableRangeScan_20     | 1.00    | cop[tikv] | table:t2      | range:(20001,+inf], keep order:true, stats:pseudo |
+-----------------------------+---------+-----------+---------------+---------------------------------------------------+
4 rows in set (0.01 sec)

mysql> set tidb_partition_prune_mode='dynamic';
Query OK, 0 rows affected (0.00 sec)

mysql> explain select * from t1 where id > 20001 order by id limit 1;
+-----------------------------+---------+-----------+----------------+----------------------------------------------------+
| id                          | estRows | task      | access object  | operator info                                      |
+-----------------------------+---------+-----------+----------------+----------------------------------------------------+
| TopN_8                      | 1.00    | root      |                | test.t1.id, offset:0, count:1                      |
| └─TableReader_17            | 1.00    | root      | partition:dual | data:TopN_16                                       |
|   └─TopN_16                 | 1.00    | cop[tikv] |                | test.t1.id, offset:0, count:1                      |
|     └─TableRangeScan_15     | 3333.33 | cop[tikv] | table:t1       | range:(20001,+inf], keep order:false, stats:pseudo |
+-----------------------------+---------+-----------+----------------+----------------------------------------------------+
4 rows in set (0.00 sec)

mysql> explain select * from t2 where id > 20001 order by id limit 1;
+-----------------------------+---------+-----------+---------------+---------------------------------------------------+
| id                          | estRows | task      | access object | operator info                                     |
+-----------------------------+---------+-----------+---------------+---------------------------------------------------+
| Limit_12                    | 1.00    | root      |               | offset:0, count:1                                 |
| └─TableReader_22            | 1.00    | root      |               | data:Limit_21                                     |
|   └─Limit_21                | 1.00    | cop[tikv] |               | offset:0, count:1                                 |
|     └─TableRangeScan_20     | 1.00    | cop[tikv] | table:t2      | range:(20001,+inf], keep order:true, stats:pseudo |
+-----------------------------+---------+-----------+---------------+---------------------------------------------------+
4 rows in set (0.00 sec)

2. What did you expect to see? (Required)

t1, t2 be same

3. What did you see instead (Required)

the partition table can not be eliminated as limitN (even with dynamic prune)

4. What is your TiDB version? (Required)

newest master

[winoros]

This needs a MergeSort operator.
It's not a thing that can be solved as a bug.

[time-and-fate]

As stated above, we don't support keep order on partitions like we do on a single table. We need to implement this functionality.
So converting it to an enhancement.

[mjonss]

/component tablepartition

[qw4990]

[qw4990]

Or for this case, we can generate a plan like this:

TopN
  IndexReader
    Limit
      IndexScan

[winoros]

Now the normal partition table cases can have a clean order property push down.