Use 2-stage sort to optimize performance of window function with `order by` and without `partition by`
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
```
mysql> desc test;
+-------+---------+------+------+---------+-------+
| Field | Type | Null | Key | Default | Extra |
+-------+---------+------+------+---------+-------+
| id | int(11) | YES | | NULL | |
| value | date | YES | | NULL | |
+-------+---------+------+------+---------+-------+
2 rows in set (0.00 sec)
mysql> explain select *, row_number() over (order by value) from test;
+----------------------------------+---------+--------------+---------------+------------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+----------------------------------+---------+--------------+---------------+------------------------------------------------------------------------------------------------+
| TableReader_23 | 2.00 | root | | data:ExchangeSender_22 |
| └─ExchangeSender_22 | 2.00 | mpp[tiflash] | | ExchangeType: PassThrough |
| └─Window_21 | 2.00 | mpp[tiflash] | | row_number()->Column#5 over(order by test.test.value rows between current row and current row) |
| └─Sort_13 | 2.00 | mpp[tiflash] | | test.test.value |
| └─ExchangeReceiver_12 | 2.00 | mpp[tiflash] | | |
| └─ExchangeSender_11 | 2.00 | mpp[tiflash] | | ExchangeType: PassThrough |
| └─TableFullScan_10 | 2.00 | mpp[tiflash] | table:test | keep order:false, stats:pseudo |
+----------------------------------+---------+--------------+---------------+------------------------------------------------------------------------------------------------+
```
Consider a query including window function with order by clause and without partition by clause, current plan is to use exchange operator to send all the data into one TiFlash node, and do a global sort before calculating the window function. The performance bottleneck is `Sort_13`, since it is done in one Node and in the merge stage, only 1 thread can be used. A straightforward enhancement is we can convert `Sort_13` into 2 stage sort, after `TableFullScan_10`, every node itself sort the output data, so `Sort_13` just need a merge sort.
In order to support this, we need
- TiDB generates 2-stage sort plan for window function with order by clause and without partition by clause.
- TiFlash supports for the 2 stage sort.
Contributor guide
Assessment
This issue has not been assessed yet.