Skip to content

Commit 676c003

Browse files
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/sort_query_fuzz.rs‎

Lines changed: 35 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ use std::fmt::Write as _;
99
use std::sync::Arc;
1010

1111
use arrow::array::RecordBatch;
12+
use arrow::compute::concat_batches;
1213
use arrow_schema::SchemaRef;
1314
use datafusion::datasource::MemTable;
1415
use datafusion::prelude::{SessionConfig, SessionContext};
@@ -24,8 +25,6 @@ use rand::Rng;
2425
use rand::prelude::IndexedRandom;
2526
use rand::{SeedableRng, rngs::StdRng};
2627

27-
use crate::fuzz_cases::aggregation_fuzzer::check_equality_of_batches;
28-
2928
use super::aggregation_fuzzer::ColumnDescr;
3029
use super::record_batch_generator::{RecordBatchGenerator, get_supported_types_columns};
3130

@@ -186,7 +185,7 @@ impl SortQueryFuzzer {
186185
let init_seed = self.runner_rng.random();
187186
for query_i in 0..self.queries_per_round {
188187
let query_seed = self.runner_rng.random();
189-
let mut expected_results: Option<Vec<RecordBatch>> = None; // use first config's result as the expected result
188+
let mut expected_results: Option<RecordBatch> = None; // use first config's result as the expected result
190189
for config_i in 0..self.config_variations_per_query {
191190
if self.should_stop_due_to_time_limit(start_time, round, query_i) {
192191
return Ok(());
@@ -204,18 +203,16 @@ impl SortQueryFuzzer {
204203

205204
let results = self
206205
.test_gen
207-
.fuzzer_run(init_seed, query_seed, config_seed)
206+
.fuzzer_run(init_seed, query_seed, config_seed, config_i == 0)
208207
.await?;
209208
println!("\n"); // Separator between tested runs
210209

211210
if expected_results.is_none() {
212211
expected_results = Some(results);
213212
} else if let Some(ref expected) = expected_results {
214-
// `fuzzer_run` might append `LIMIT k` to either the
215-
// expected or actual query. The number of results is
216-
// checked inside `fuzzer_run()`. Here we only check
217-
// that the first k rows of each result are consistent.
218-
check_equality_of_batches(expected, &results).unwrap();
213+
// Every projected column is an ORDER BY key, so tied
214+
// rows have identical output and can be compared in order.
215+
assert_eq!(expected, &results);
219216
} else {
220217
unreachable!();
221218
}
@@ -467,6 +464,7 @@ impl SortFuzzerTestGenerator {
467464
&self,
468465
rng_seed: u64,
469466
with_memory_limit: bool,
467+
sort_in_place_threshold_override: Option<usize>,
470468
) -> Result<SessionContext> {
471469
let mut rng = StdRng::seed_from_u64(rng_seed);
472470
let init_state = self.dataset_state.as_ref().unwrap();
@@ -495,6 +493,8 @@ impl SortFuzzerTestGenerator {
495493
let dataset_size = self.dataset_state.as_ref().unwrap().dataset_size;
496494
rng.random_range(0..=dataset_size * 2_usize)
497495
};
496+
let sort_in_place_threshold_bytes =
497+
sort_in_place_threshold_override.unwrap_or(sort_in_place_threshold_bytes);
498498

499499
// Set up strings for printing
500500
let memory_limit_str = if with_memory_limit {
@@ -526,6 +526,8 @@ impl SortFuzzerTestGenerator {
526526
let config = SessionConfig::new()
527527
.with_target_partitions(num_partitions)
528528
.with_batch_size(init_state.approx_batch_num_rows / 2)
529+
// Keep small input batches separate when comparing the two sort paths.
530+
.with_coalesce_batches(sort_in_place_threshold_override.is_none())
529531
.with_sort_spill_reservation_bytes(sort_spill_reservation_bytes)
530532
.with_sort_in_place_threshold_bytes(sort_in_place_threshold_bytes);
531533

@@ -556,7 +558,8 @@ impl SortFuzzerTestGenerator {
556558
dataset_seed: u64,
557559
query_seed: u64,
558560
config_seed: u64,
559-
) -> Result<Vec<RecordBatch>> {
561+
compare_sort_paths: bool,
562+
) -> Result<RecordBatch> {
560563
self.init_partitioned_staggered_batches(dataset_seed);
561564
let (query_str, limit) = self.generate_random_query(query_seed);
562565
println!(" Query:");
@@ -569,19 +572,35 @@ impl SortFuzzerTestGenerator {
569572
// 2. Memory limiting is enabled in the test generator config
570573
let with_mem_limit = !query_str.contains("LIMIT") && self.set_memory_limit;
571574

572-
let ctx = self.generate_random_config(config_seed, with_mem_limit)?;
575+
let ctx = self.generate_random_config(config_seed, with_mem_limit, None)?;
573576
let df = ctx.sql(&query_str).await.unwrap();
574-
let results = df.collect().await.unwrap();
577+
let schema = Arc::clone(df.schema().inner());
578+
let results = concat_batches(&schema, &df.collect().await?)?;
575579

576580
// ==== Check the result size is consistent with the limit ====
577-
let result_num_rows = results.iter().map(|batch| batch.num_rows()).sum::<usize>();
581+
let result_num_rows = results.num_rows();
578582
let dataset_size = self.dataset_state.as_ref().unwrap().dataset_size;
579583

580584
if let Some(limit) = limit {
581585
let expected_num_rows = min(limit, dataset_size);
582586
assert_eq!(result_num_rows, expected_num_rows);
583587
}
584588

589+
if compare_sort_paths && limit.is_none() && !with_mem_limit {
590+
// Run the same query inline and with bounded parallel preparation.
591+
// An unbounded memory pool allows the inline path to concatenate all runs.
592+
for threshold in [usize::MAX, 0] {
593+
let ctx =
594+
self.generate_random_config(config_seed, false, Some(threshold))?;
595+
let actual = ctx.sql(&query_str).await?.collect().await?;
596+
assert_eq!(
597+
results,
598+
concat_batches(&schema, &actual)?,
599+
"sort_in_place_threshold_bytes={threshold}"
600+
);
601+
}
602+
}
603+
585604
Ok(results)
586605
}
587606
}
@@ -603,8 +622,8 @@ mod test {
603622
gen_seed,
604623
);
605624

606-
let res1 = test_generator.fuzzer_run(1, 2, 3).await.unwrap();
607-
let res2 = test_generator.fuzzer_run(1, 2, 3).await.unwrap();
608-
check_equality_of_batches(&res1, &res2).unwrap();
625+
let res1 = test_generator.fuzzer_run(1, 2, 3, false).await.unwrap();
626+
let res2 = test_generator.fuzzer_run(1, 2, 3, false).await.unwrap();
627+
assert_eq!(res1, res2);
609628
}
610629
}

0 commit comments

Comments
 (0)