pingcap / pingcap/tidb

Use 2-stage sort to optimize performance of window function with `order by` and without `partition by`

Open
#39,779 2 comments 0 reactions 0 assignees View on GitHub
sig/planner type/enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.