Repository navigation
Commit 676c003
authored
fix: bound parallel batch sorting in SortExec (apache#26242)
## Which issue does this PR close?
Addresses the unbounded local-sort task population discussed in
[apache#23174](apache#23174).
## Rationale for this change
`SortExec` sorts pieces of buffered input into independent **runs**,
then merges them. On multithreaded Tokio runtimes, it currently creates
one buffered producer task per run.
A one-batch channel limits each producer's output, but the number of
tasks still grows with the number of runs. With many input batches, this
task buildup can stall unrelated queries on the same runtime. Large
inputs can trigger this buildup even with normal-sized batches.
## What changes are included in this PR?
Use bounded preparation for both final in-memory sorting and sorting
before a spill:
1. **Wait before spawning.** Preparations acquire a shared permit before
creating a Tokio task. All partitions of one `SortExec` share a budget
capped by both the runtime's worker count and DataFusion's estimate of
available CPU parallelism. Each partition also bounds its pending
preparations.
2. **Sort, return, exit.** Each job sorts one run, reserves its complete
output, and returns a stream holding the batches and their reservations.
The job then exits and releases its permit.
3. **Merge the prepared streams.** Output stays reserved until its
batches are read. The merge receives the streams in their original run
order, keeping its output independent of task completion order.
**Memory handoff:** during merging, one-batch lookahead returns
workspace for the merge's batches and cursors. Each run may hold one
prefetched batch whose sort-side reservation has already been released,
preserving the previous buffering bound.
Cancellation aborts outstanding jobs. Resetting execution state gives
the new plan a fresh concurrency limit.
Single-batch and concatenate-and-sort paths continue inline, as do
current-thread runtimes and execution outside Tokio. TopK is unchanged.
`SortExec` rustdoc describes the limit and its lifetime.
## What is the testing strategy for this PR?
- **Memory and output:** a competing-consumer regression checks that
prepared output stays reserved while released scratch space can be
reused. Tight-workspace tests check complete merging and cleanup when
unread output is dropped.
- **Task lifetime and timing:** focused tests cover permit ownership,
cancellation, errors, the shared limit and its reset, and compute
recording before output consumption.
- **SQL benchmarks:** at `416c2d6`, the benchmark bot classified all 11
queries in each of [sort_tpch
(SF1)](apache#26242 (comment))
and [sort_tpch10
(SF10)](apache#26242 (comment))
as "no change". These Parquet-based suites use the default 8,192-row
batch target.
A local TPC-H SF1 test uses **32-row batches** to stress task growth
with a modest dataset. With 4 Tokio workers and 4 partitions, two runs
per revision gave:
| Measurement | [Upstream
base](apache@fbf7737)
| [PR
head](apache@416c2d6)
|
| --- | ---: | ---: |
| Sampled peak live Tokio tasks | ~187k | 9 |
| Slowest `SELECT 1` probe | 2.83–2.89 s | 155–165 ms |
## Are there any user-facing changes?
Sorts with many runs have a bounded population of batch-sort jobs across
partitions. Public configuration and API signatures are unchanged.
`SortExec`'s **`elapsed_compute` now includes local batch sorting and
its memory accounting** on both inline and spawned paths, while
excluding waits for a permit or another task. `EXPLAIN ANALYZE` can
therefore report larger values.
Durations from concurrent sort jobs are added together and can exceed
the query's wall-clock duration.
This PR was prepared with AI assistance.1 parent da3cb0a commit 676c003
3 files changed
Lines changed: 594 additions & 72 deletions
File tree
- datafusion
- core/tests/fuzz_cases
- physical-plan/src/sorts
- sort
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
9 | 9 | | |
10 | 10 | | |
11 | 11 | | |
| 12 | + | |
12 | 13 | | |
13 | 14 | | |
14 | 15 | | |
| |||
24 | 25 | | |
25 | 26 | | |
26 | 27 | | |
27 | | - | |
28 | | - | |
29 | 28 | | |
30 | 29 | | |
31 | 30 | | |
| |||
186 | 185 | | |
187 | 186 | | |
188 | 187 | | |
189 | | - | |
| 188 | + | |
190 | 189 | | |
191 | 190 | | |
192 | 191 | | |
| |||
204 | 203 | | |
205 | 204 | | |
206 | 205 | | |
207 | | - | |
| 206 | + | |
208 | 207 | | |
209 | 208 | | |
210 | 209 | | |
211 | 210 | | |
212 | 211 | | |
213 | 212 | | |
214 | | - | |
215 | | - | |
216 | | - | |
217 | | - | |
218 | | - | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
219 | 216 | | |
220 | 217 | | |
221 | 218 | | |
| |||
467 | 464 | | |
468 | 465 | | |
469 | 466 | | |
| 467 | + | |
470 | 468 | | |
471 | 469 | | |
472 | 470 | | |
| |||
495 | 493 | | |
496 | 494 | | |
497 | 495 | | |
| 496 | + | |
| 497 | + | |
498 | 498 | | |
499 | 499 | | |
500 | 500 | | |
| |||
526 | 526 | | |
527 | 527 | | |
528 | 528 | | |
| 529 | + | |
| 530 | + | |
529 | 531 | | |
530 | 532 | | |
531 | 533 | | |
| |||
556 | 558 | | |
557 | 559 | | |
558 | 560 | | |
559 | | - | |
| 561 | + | |
| 562 | + | |
560 | 563 | | |
561 | 564 | | |
562 | 565 | | |
| |||
569 | 572 | | |
570 | 573 | | |
571 | 574 | | |
572 | | - | |
| 575 | + | |
573 | 576 | | |
574 | | - | |
| 577 | + | |
| 578 | + | |
575 | 579 | | |
576 | 580 | | |
577 | | - | |
| 581 | + | |
578 | 582 | | |
579 | 583 | | |
580 | 584 | | |
581 | 585 | | |
582 | 586 | | |
583 | 587 | | |
584 | 588 | | |
| 589 | + | |
| 590 | + | |
| 591 | + | |
| 592 | + | |
| 593 | + | |
| 594 | + | |
| 595 | + | |
| 596 | + | |
| 597 | + | |
| 598 | + | |
| 599 | + | |
| 600 | + | |
| 601 | + | |
| 602 | + | |
| 603 | + | |
585 | 604 | | |
586 | 605 | | |
587 | 606 | | |
| |||
603 | 622 | | |
604 | 623 | | |
605 | 624 | | |
606 | | - | |
607 | | - | |
608 | | - | |
| 625 | + | |
| 626 | + | |
| 627 | + | |
609 | 628 | | |
610 | 629 | | |
0 commit comments