tustvold opened a new pull request, #5851:
URL: https://github.com/apache/arrow-datafusion/pull/5851
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and
enhancements and this helps us generate change logs for our releases. You can
link an issue to this PR using the GitHub syntax. For example `Closes #123`
indicates that this PR will close issue #123.
-->
Closes #.
# Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in
the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your
changes and offer better suggestions for fixes.
-->
Investigating https://github.com/apache/arrow-datafusion/pull/5292 and
thought I would try to break it into smaller pieces to make it easier to see
what is going on. In particular this PR just switches `ExternalSorter` to using
`SortPreservingMerge`.
This results in better performance, apart from in the case of a single sort
column. This is not hugely surprising, as lexsort_to_indices has optimised
kernels for when sorting by a single column.
```
Compiling datafusion v21.0.0
(/home/raphael/repos/external/arrow-datafusion/datafusion/core)
Finished release-nonlto [optimized] target(s) in 22.59s
Running benches/sort.rs
(/home/raphael/repos/external/arrow-datafusion/target/release-nonlto/deps/sort-16eed48ca15554e0)
sort i64 time: [7.6330 ms 7.6510 ms 7.6683 ms]
change: [+42.367% +42.983% +43.644%] (p = 0.00 <
0.05)
Performance has regressed.
Found 3 outliers among 100 measurements (3.00%)
1 (1.00%) low severe
2 (2.00%) low mild
Benchmarking sort i64 preserve partitioning: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase
target time to 9.3s, enable flat sampling, or reduce sample count to 50.
sort i64 preserve partitioning
time: [1.8267 ms 1.8308 ms 1.8348 ms]
change: [-5.5979% -5.0486% -4.4890%] (p = 0.00 <
0.05)
Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
1 (1.00%) high mild
4 (4.00%) high severe
sort f64 time: [8.0650 ms 8.0818 ms 8.0983 ms]
change: [+27.214% +27.725% +28.212%] (p = 0.00 <
0.05)
Performance has regressed.
Found 7 outliers among 100 measurements (7.00%)
5 (5.00%) low mild
2 (2.00%) high mild
sort f64 preserve partitioning
time: [2.2920 ms 2.2987 ms 2.3053 ms]
change: [-4.0517% -3.4908% -3.0237%] (p = 0.00 <
0.05)
Performance has improved.
Found 12 outliers among 100 measurements (12.00%)
9 (9.00%) low mild
2 (2.00%) high mild
1 (1.00%) high severe
sort utf8 low cardinality
time: [8.4322 ms 8.4522 ms 8.4707 ms]
change: [-9.3807% -8.9870% -8.6128%] (p = 0.00 <
0.05)
Performance has improved.
Found 16 outliers among 100 measurements (16.00%)
7 (7.00%) low severe
2 (2.00%) low mild
7 (7.00%) high mild
sort utf8 low cardinality preserve partitioning
time: [4.5490 ms 4.5611 ms 4.5723 ms]
change: [-9.4824% -9.0677% -8.6905%] (p = 0.00 <
0.05)
Performance has improved.
Found 24 outliers among 100 measurements (24.00%)
11 (11.00%) low severe
7 (7.00%) low mild
5 (5.00%) high mild
1 (1.00%) high severe
sort utf8 high cardinality
time: [13.918 ms 13.945 ms 13.972 ms]
change: [-25.221% -24.973% -24.715%] (p = 0.00 <
0.05)
Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
3 (3.00%) low severe
1 (1.00%) low mild
1 (1.00%) high mild
2 (2.00%) high severe
sort utf8 high cardinality preserve partitioning
time: [7.4030 ms 7.4190 ms 7.4343 ms]
change: [-9.2608% -8.8695% -8.4917%] (p = 0.00 <
0.05)
Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
1 (1.00%) low severe
5 (5.00%) low mild
2 (2.00%) high mild
sort utf8 tuple time: [14.899 ms 14.924 ms 14.950 ms]
change: [-55.867% -55.718% -55.570%] (p = 0.00 <
0.05)
Performance has improved.
Found 6 outliers among 100 measurements (6.00%)
2 (2.00%) low mild
2 (2.00%) high mild
2 (2.00%) high severe
sort utf8 tuple preserve partitioning
time: [3.4615 ms 3.4720 ms 3.4857 ms]
change: [-18.031% -17.508% -17.055%] (p = 0.00 <
0.05)
Performance has improved.
Found 17 outliers among 100 measurements (17.00%)
4 (4.00%) low severe
9 (9.00%) low mild
3 (3.00%) high mild
1 (1.00%) high severe
sort utf8 dictionary time: [4.2060 ms 4.2164 ms 4.2269 ms]
change: [+106.17% +106.95% +107.78%] (p = 0.00 <
0.05)
Performance has regressed.
Found 3 outliers among 100 measurements (3.00%)
1 (1.00%) low mild
2 (2.00%) high mild
sort utf8 dictionary preserve partitioning
time: [666.64 µs 668.92 µs 671.60 µs]
change: [-16.850% -12.080% -9.1385%] (p = 0.00 <
0.05)
Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
2 (2.00%) high mild
2 (2.00%) high severe
sort utf8 dictionary tuple
time: [10.505 ms 10.523 ms 10.542 ms]
change: [-68.282% -68.190% -68.095%] (p = 0.00 <
0.05)
Performance has improved.
Found 14 outliers among 100 measurements (14.00%)
1 (1.00%) low severe
6 (6.00%) low mild
4 (4.00%) high mild
3 (3.00%) high severe
sort utf8 dictionary tuple preserve partitioning
time: [2.2596 ms 2.2680 ms 2.2768 ms]
change: [+1.9579% +2.5266% +3.0875%] (p = 0.00 <
0.05)
Performance has regressed.
Found 3 outliers among 100 measurements (3.00%)
2 (2.00%) low mild
1 (1.00%) high severe
sort mixed utf8 dictionary tuple
time: [11.538 ms 11.565 ms 11.590 ms]
change: [-66.047% -65.860% -65.706%] (p = 0.00 <
0.05)
Performance has improved.
Found 19 outliers among 100 measurements (19.00%)
8 (8.00%) low severe
7 (7.00%) low mild
2 (2.00%) high mild
2 (2.00%) high severe
sort mixed utf8 dictionary tuple preserve partitioning
time: [2.3764 ms 2.3824 ms 2.3884 ms]
change: [+0.8246% +1.2743% +1.6849%] (p = 0.00 <
0.05)
Change within noise threshold.
Found 2 outliers among 100 measurements (2.00%)
1 (1.00%) low mild
1 (1.00%) high mild
sort mixed tuple time: [12.027 ms 12.081 ms 12.151 ms]
change: [-30.336% -29.962% -29.490%] (p = 0.00 <
0.05)
Performance has improved.
Found 12 outliers among 100 measurements (12.00%)
9 (9.00%) low mild
2 (2.00%) high mild
1 (1.00%) high severe
Benchmarking sort mixed tuple preserve partitioning: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase
target time to 8.0s, enable flat sampling, or reduce sample count to 50.
sort mixed tuple preserve partitioning
time: [1.5646 ms 1.5663 ms 1.5680 ms]
change: [-30.915% -30.601% -30.228%] (p = 0.00 <
0.05)
Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
1 (1.00%) low mild
1 (1.00%) high mild
5 (5.00%) high severe
```
I think the next step is to find a way to make single-column sort
expressions perform better in SortPreservingMerge, likely by providing
specialized implementations of `SortPreservingMergeStream`'s inner cursor loop
# What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is
sometimes worth providing a summary of the individual changes in this PR.
-->
# Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are
they covered by existing tests)?
-->
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api
change` label.
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
