merge sort for partition table

[eurekaka]

Feature Request

Is your feature request related to a problem? Please describe:

MySQL [test]> create table t(a int, b int) partition by range (a) (
    -> partition p0 values less than (5),
    -> partition p1 values less than (10),
    -> partition p2 values less than maxvalue
    -> );
Query OK, 0 rows affected (0.01 sec)

MySQL [test]> explain select * from t order by _tidb_rowid;
+--------------------------------+----------+-----------+-----------------------+--------------------------------+
| id                             | estRows  | task      | access object         | operator info                  |
+--------------------------------+----------+-----------+-----------------------+--------------------------------+
| Projection_10                  | 30000.00 | root      |                       | test.t.a, test.t.b             |
| └─Sort_11                      | 30000.00 | root      |                       | test.t._tidb_rowid             |
|   └─PartitionUnion_13          | 30000.00 | root      |                       |                                |
|     ├─TableReader_15           | 10000.00 | root      |                       | data:TableFullScan_14          |
|     │ └─TableFullScan_14       | 10000.00 | cop[tikv] | table:t, partition:p0 | keep order:false, stats:pseudo |
|     ├─TableReader_17           | 10000.00 | root      |                       | data:TableFullScan_16          |
|     │ └─TableFullScan_16       | 10000.00 | cop[tikv] | table:t, partition:p1 | keep order:false, stats:pseudo |
|     └─TableReader_19           | 10000.00 | root      |                       | data:TableFullScan_18          |
|       └─TableFullScan_18       | 10000.00 | cop[tikv] | table:t, partition:p2 | keep order:false, stats:pseudo |
+--------------------------------+----------+-----------+-----------------------+--------------------------------+
9 rows in set (0.00 sec)

MySQL [test]> drop table t;
Query OK, 0 rows affected (0.03 sec)

MySQL [test]> create table t(a int, b int);
Query OK, 0 rows affected (0.02 sec)

MySQL [test]> explain select * from t order by _tidb_rowid;
+--------------------------+----------+-----------+---------------+-------------------------------+
| id                       | estRows  | task      | access object | operator info                 |
+--------------------------+----------+-----------+---------------+-------------------------------+
| Projection_5             | 10000.00 | root      |               | test.t.a, test.t.b            |
| └─TableReader_11         | 10000.00 | root      |               | data:TableFullScan_10         |
|   └─TableFullScan_10     | 10000.00 | cop[tikv] | table:t       | keep order:true, stats:pseudo |
+--------------------------+----------+-----------+---------------+-------------------------------+
3 rows in set (0.00 sec)

Describe the feature you'd like:

For sort on partition tables, we can sort each partition first, and merge sort those ordered inputs. Then for each partition, it may be able to utilize an index to provide the required order. That would accelerate the execution a lot and reduce memory / cpu usages.

Describe alternatives you've considered:

No.

Teachability, Documentation, Adoption, Migration Strategy:

This can accelerate the execution a lot and reduce memory / cpu usages for TiDB. Besides, this kind of query is supposed to be common in backup tools, this feature would benefit them as well.

[zz-jason]

not a SQL feature request, moved it out of the feature-request kanban.

[mjonss]

/component tablepartition

[Defined2014]

I think we already supported it, ref link https://github.com/pingcap/tidb/issues/26166