sunchao commented on code in PR #7696: URL: https://github.com/apache/datafusion-comet/pull/7696#discussion_r4645579015
########## native/operators/src/sort_input_coalesce.rs: ########## @@ -0,0 +1,1160 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Combines small input batches before a native sort. +//! +//! On its spill path DataFusion's sort merges one stream per buffered batch, so thousands of +//! tiny shuffle blocks make it very slow. Below the in-place threshold the sort concatenates its +//! input itself, so batches pass through until a partition's input reaches that threshold. The +//! gate never closes again, so a sort whose share is below the threshold gets a copy it does not +//! need. +//! +//! This sits in front of the sort rather than in the shuffle reader because only the sort's merge +//! cost grows with the number of batches. Arrow's `BatchCoalescer` has no byte limit and copies +//! as batches arrive, and `DecodedBatchCoalescer` takes only flat types, so neither lets the held +//! memory be reserved exactly for any input. + +use std::fmt::Formatter; +use std::sync::Arc; + +use arrow::compute::concat_batches; +use arrow::datatypes::DataType; +use arrow::record_batch::RecordBatch; +use datafusion::common::tree_node::TreeNodeRecursion; +use datafusion::common::utils::memory::get_record_batch_memory_size; +use datafusion::common::{DataFusionError, Result}; +use datafusion::execution::memory_pool::{MemoryConsumer, MemoryReservation}; +use datafusion::execution::{async_try_stream, TaskContext}; +use datafusion::physical_expr::PhysicalExpr; +use datafusion::physical_plan::execution_plan::CardinalityEffect; +use datafusion::physical_plan::metrics::{ + BaselineMetrics, Count, ExecutionPlanMetricsSet, MetricBuilder, MetricsSet, +}; +use datafusion::physical_plan::stream::RecordBatchStreamAdapter; +use datafusion::physical_plan::{ + DisplayAs, DisplayFormatType, ExecutionPlan, PlanProperties, SendableRecordBatchStream, +}; +use futures::TryStreamExt; + +/// The cap is half the in-place threshold because the sort reserves about twice a batch's size. +/// The bounds also keep string and binary offsets far below the i32 limit. +const MIN_GROUP_BYTES: usize = 64 * 1024; +const MAX_GROUP_BYTES: usize = 4 * 1024 * 1024; + +/// In `sort_small_batches`, combining 512-row batches made a spilling single-key sort slower, +/// while 384 rows or fewer was never slower. +const MAX_SMALL_BATCH_ROWS: usize = 512; + +/// Small batches passed through after a refusal, so a pool under pressure is not asked again for +/// each one. +const REFUSED_BACKOFF_BATCHES: usize = 64; + +#[derive(Debug)] +pub struct SortInputCoalesceExec { + input: Arc<dyn ExecutionPlan>, + target_rows: usize, + gate_bytes: usize, + max_bytes: usize, + metrics: ExecutionPlanMetricsSet, +} + +impl SortInputCoalesceExec { + /// `gate_bytes` is the sort's in-place threshold. + pub fn new(input: Arc<dyn ExecutionPlan>, target_rows: usize, gate_bytes: usize) -> Self { + Self { + input, + target_rows: target_rows.max(1), + gate_bytes, + max_bytes: (gate_bytes / 2).clamp(MIN_GROUP_BYTES, MAX_GROUP_BYTES), + metrics: ExecutionPlanMetricsSet::new(), + } + } + + #[cfg(test)] + fn with_max_bytes(mut self, max_bytes: usize) -> Self { + self.max_bytes = max_bytes; + self + } + + pub fn input(&self) -> &Arc<dyn ExecutionPlan> { + &self.input + } + + /// The plan below a coalescer, or `plan` itself when it is not one. + pub fn unwrap_input(plan: &Arc<dyn ExecutionPlan>) -> &Arc<dyn ExecutionPlan> { + plan.downcast_ref::<Self>().map_or(plan, Self::input) + } +} + +impl DisplayAs for SortInputCoalesceExec { + fn fmt_as(&self, _t: DisplayFormatType, f: &mut Formatter) -> std::fmt::Result { + write!( + f, + "CometSortInputCoalesceExec: target_rows={}, gate_bytes={}, max_bytes={}", + self.target_rows, self.gate_bytes, self.max_bytes + ) + } +} + +impl ExecutionPlan for SortInputCoalesceExec { + fn name(&self) -> &str { + "CometSortInputCoalesceExec" + } + + fn properties(&self) -> &Arc<PlanProperties> { + self.input.properties() + } + + fn maintains_input_order(&self) -> Vec<bool> { + vec![true] + } + + fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> { + vec![&self.input] + } + + fn apply_expressions( + &self, + _f: &mut dyn FnMut(&Arc<dyn PhysicalExpr>) -> Result<TreeNodeRecursion>, + ) -> Result<TreeNodeRecursion> { + Ok(TreeNodeRecursion::Continue) + } + + fn cardinality_effect(&self) -> CardinalityEffect { + CardinalityEffect::Equal + } + + fn with_new_children( + self: Arc<Self>, + children: Vec<Arc<dyn ExecutionPlan>>, + ) -> Result<Arc<dyn ExecutionPlan>> { + let [input]: [_; 1] = children.try_into().map_err(|_| { + DataFusionError::Internal("Sort input coalescing requires one child".into()) + })?; + Ok(Arc::new(Self { + input, + target_rows: self.target_rows, + gate_bytes: self.gate_bytes, + max_bytes: self.max_bytes, + // Shared, so the copy reports through the node the Spark plan registered for its + // metrics if a rewrite rebuilds the sort's input. + metrics: self.metrics.clone(), + })) + } + + fn execute( + &self, + partition: usize, + context: Arc<TaskContext>, + ) -> Result<SendableRecordBatchStream> { + let mut input = self.input.execute(partition, Arc::clone(&context))?; + let reservation = MemoryConsumer::new(format!("SortInputCoalesceExec[{partition}]")) Review Comment: The pool can grant this unspillable consumer a group that exceeds `ExternalSorter`’s fair share. That can fail a task even when **24 raw batches fit at once**. [Fair-pool checks](https://github.com/apache/datafusion-comet/blob/d1819fd7fe1024fdc0fe7ae8ff7113e9c00e0587/native/core/src/execution/memory_pools/fair_pool.rs#L247-L279) · [Sort retry](https://github.com/apache/datafusion/blob/55.2.0/datafusion/physical-plan/src/sorts/sort.rs#L799-L820) A regression case for the new fair-pool test would be an 11.5 MiB pool, a second active spillable consumer, and the default 10 MiB merge reservation, 1 MiB threshold and 8,192-row target. Feed it 64 batches of 256 rows with eight separately allocated, non-null `Int64` columns. Each batch holds 16 KiB and costs the sort 32 KiB. Tracing the reservations through 55.2 gives the following sequence. - With coalescing off, the 768 KiB sort share admits runs of 24, 24 and 16 batches. Their spill files fit in the merge workspace. - With coalescing on, the gate opens after batch 32. The sort holds 256 KiB at that point. The pool grants the coalescer 1 MiB for batches 33–64 and their copy. Once emitted, that single 512 KiB batch costs the sort 1 MiB. The sort spills its 256 KiB and retries with an empty buffer, where the limit is still 768 KiB. The backoff only sees refusals on the coalescer's reservation. Could we add this case and keep the feature opt-in until an oversized group can fall back to the original batches under the sort's own reservation? ########## native/operators/src/sort_input_coalesce.rs: ########## @@ -0,0 +1,1160 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Combines small input batches before a native sort. +//! +//! On its spill path DataFusion's sort merges one stream per buffered batch, so thousands of +//! tiny shuffle blocks make it very slow. Below the in-place threshold the sort concatenates its +//! input itself, so batches pass through until a partition's input reaches that threshold. The +//! gate never closes again, so a sort whose share is below the threshold gets a copy it does not +//! need. +//! +//! This sits in front of the sort rather than in the shuffle reader because only the sort's merge +//! cost grows with the number of batches. Arrow's `BatchCoalescer` has no byte limit and copies +//! as batches arrive, and `DecodedBatchCoalescer` takes only flat types, so neither lets the held +//! memory be reserved exactly for any input. + +use std::fmt::Formatter; +use std::sync::Arc; + +use arrow::compute::concat_batches; +use arrow::datatypes::DataType; +use arrow::record_batch::RecordBatch; +use datafusion::common::tree_node::TreeNodeRecursion; +use datafusion::common::utils::memory::get_record_batch_memory_size; +use datafusion::common::{DataFusionError, Result}; +use datafusion::execution::memory_pool::{MemoryConsumer, MemoryReservation}; +use datafusion::execution::{async_try_stream, TaskContext}; +use datafusion::physical_expr::PhysicalExpr; +use datafusion::physical_plan::execution_plan::CardinalityEffect; +use datafusion::physical_plan::metrics::{ + BaselineMetrics, Count, ExecutionPlanMetricsSet, MetricBuilder, MetricsSet, +}; +use datafusion::physical_plan::stream::RecordBatchStreamAdapter; +use datafusion::physical_plan::{ + DisplayAs, DisplayFormatType, ExecutionPlan, PlanProperties, SendableRecordBatchStream, +}; +use futures::TryStreamExt; + +/// The cap is half the in-place threshold because the sort reserves about twice a batch's size. +/// The bounds also keep string and binary offsets far below the i32 limit. +const MIN_GROUP_BYTES: usize = 64 * 1024; +const MAX_GROUP_BYTES: usize = 4 * 1024 * 1024; + +/// In `sort_small_batches`, combining 512-row batches made a spilling single-key sort slower, +/// while 384 rows or fewer was never slower. +const MAX_SMALL_BATCH_ROWS: usize = 512; + +/// Small batches passed through after a refusal, so a pool under pressure is not asked again for +/// each one. +const REFUSED_BACKOFF_BATCHES: usize = 64; + +#[derive(Debug)] +pub struct SortInputCoalesceExec { + input: Arc<dyn ExecutionPlan>, + target_rows: usize, + gate_bytes: usize, + max_bytes: usize, + metrics: ExecutionPlanMetricsSet, +} + +impl SortInputCoalesceExec { + /// `gate_bytes` is the sort's in-place threshold. + pub fn new(input: Arc<dyn ExecutionPlan>, target_rows: usize, gate_bytes: usize) -> Self { + Self { + input, + target_rows: target_rows.max(1), + gate_bytes, + max_bytes: (gate_bytes / 2).clamp(MIN_GROUP_BYTES, MAX_GROUP_BYTES), + metrics: ExecutionPlanMetricsSet::new(), + } + } + + #[cfg(test)] + fn with_max_bytes(mut self, max_bytes: usize) -> Self { + self.max_bytes = max_bytes; + self + } + + pub fn input(&self) -> &Arc<dyn ExecutionPlan> { + &self.input + } + + /// The plan below a coalescer, or `plan` itself when it is not one. + pub fn unwrap_input(plan: &Arc<dyn ExecutionPlan>) -> &Arc<dyn ExecutionPlan> { + plan.downcast_ref::<Self>().map_or(plan, Self::input) + } +} + +impl DisplayAs for SortInputCoalesceExec { + fn fmt_as(&self, _t: DisplayFormatType, f: &mut Formatter) -> std::fmt::Result { + write!( + f, + "CometSortInputCoalesceExec: target_rows={}, gate_bytes={}, max_bytes={}", + self.target_rows, self.gate_bytes, self.max_bytes + ) + } +} + +impl ExecutionPlan for SortInputCoalesceExec { + fn name(&self) -> &str { + "CometSortInputCoalesceExec" + } + + fn properties(&self) -> &Arc<PlanProperties> { + self.input.properties() + } + + fn maintains_input_order(&self) -> Vec<bool> { + vec![true] + } + + fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> { + vec![&self.input] + } + + fn apply_expressions( + &self, + _f: &mut dyn FnMut(&Arc<dyn PhysicalExpr>) -> Result<TreeNodeRecursion>, + ) -> Result<TreeNodeRecursion> { + Ok(TreeNodeRecursion::Continue) + } + + fn cardinality_effect(&self) -> CardinalityEffect { + CardinalityEffect::Equal + } + + fn with_new_children( + self: Arc<Self>, + children: Vec<Arc<dyn ExecutionPlan>>, + ) -> Result<Arc<dyn ExecutionPlan>> { + let [input]: [_; 1] = children.try_into().map_err(|_| { + DataFusionError::Internal("Sort input coalescing requires one child".into()) + })?; + Ok(Arc::new(Self { + input, + target_rows: self.target_rows, + gate_bytes: self.gate_bytes, + max_bytes: self.max_bytes, + // Shared, so the copy reports through the node the Spark plan registered for its + // metrics if a rewrite rebuilds the sort's input. + metrics: self.metrics.clone(), + })) + } + + fn execute( + &self, + partition: usize, + context: Arc<TaskContext>, + ) -> Result<SendableRecordBatchStream> { + let mut input = self.input.execute(partition, Arc::clone(&context))?; + let reservation = MemoryConsumer::new(format!("SortInputCoalesceExec[{partition}]")) + .register(context.memory_pool()); + let baseline = BaselineMetrics::new(&self.metrics, partition); + let mut grouper = Grouper::new(self, reservation, partition); + let stream = async_try_stream(|mut out| async move { + while let Some(batch) = input.try_next().await? { + // A group that has to go out first is emitted before the new batch is held, so + // the sort reserves it while this operator holds nothing. + let (step, flushed) = { + let _timer = baseline.elapsed_compute().timer(); + grouper.prepare(&batch)? + }; + if let Some(batch) = flushed { + baseline.record_output(batch.num_rows()); + out.emit(batch).await; + } + let ready = { + let _timer = baseline.elapsed_compute().timer(); + grouper.add(batch, step)? + }; + for batch in ready.into_iter().flatten() { + baseline.record_output(batch.num_rows()); + out.emit(batch).await; + } + } + let last = { + let _timer = baseline.elapsed_compute().timer(); + grouper.flush()? + }; + if let Some(batch) = last { + baseline.record_output(batch.num_rows()); + out.emit(batch).await; + } + Ok(()) + }); + Ok(Box::pin(RecordBatchStreamAdapter::new( + self.schema(), + stream, + ))) + } + + fn metrics(&self) -> Option<MetricsSet> { + Some(self.metrics.clone_inner()) + } +} + +/// Concatenating dictionaries merges their values, which can overflow a small key type where +/// the batches on their own fit. Dictionaries nested in structs, lists and maps count too. +fn has_small_dictionary_keys(batch: &RecordBatch) -> bool { + fn small(data_type: &DataType) -> bool { + match data_type { + DataType::Dictionary(key, value) => { + key.primitive_width().is_some_and(|width| width < 4) || small(value) + } + DataType::Struct(fields) => fields.iter().any(|f| small(f.data_type())), + DataType::List(f) + | DataType::LargeList(f) + | DataType::ListView(f) + | DataType::LargeListView(f) + | DataType::FixedSizeList(f, _) + | DataType::Map(f, _) => small(f.data_type()), + // Run ends count rows, so a small run-end type can overflow too. + DataType::RunEndEncoded(run_ends, values) => { + run_ends + .data_type() + .primitive_width() + .is_some_and(|width| width < 4) + || small(values.data_type()) + } + _ => false, + } + } + batch.schema().fields().iter().any(|f| small(f.data_type())) +} + +/// The bytes the batch's rows take, without unused buffer capacity, as DataFusion's sort counts +/// it. +fn sliced_size(batch: &RecordBatch) -> Result<usize> { + batch.columns().iter().try_fold(0usize, |total, column| { + Ok(total + column.to_data().get_slice_memory_size()?) + }) +} + +enum Step { + Skip, + PassThrough, + /// Size in bytes. + Hold(usize), +} + +/// Groups whole input batches in arrival order and concatenates each group. Inputs are never +/// split, so the reservation always covers the batches being held. +struct Grouper { + target_rows: usize, + small_rows: usize, + gate_bytes: usize, + max_bytes: usize, + seen_bytes: usize, + past_gate: bool, + pending: Vec<RecordBatch>, + rows: usize, + bytes: usize, + reservation: MemoryReservation, + backoff: usize, + input_batches: Count, + output_batches: Count, +} + +impl Grouper { + fn new(exec: &SortInputCoalesceExec, reservation: MemoryReservation, partition: usize) -> Self { + let metrics = MetricBuilder::new(&exec.metrics); + Self { + target_rows: exec.target_rows, + small_rows: exec.target_rows.div_ceil(2).min(MAX_SMALL_BATCH_ROWS), + gate_bytes: exec.gate_bytes, + max_bytes: exec.max_bytes, + seen_bytes: 0, + past_gate: exec.gate_bytes == 0, + pending: Vec::new(), + rows: 0, + bytes: 0, + reservation, + backoff: 0, + input_batches: metrics + .clone() + .counter("coalesced_input_batches", partition), + output_batches: metrics.counter("coalesced_output_batches", partition), + } + } + + /// Decides what `add` does with `batch`. Returns the held group too when it has to go out + /// first: before a batch that passes through, or before one that does not fit in the group. + fn prepare(&mut self, batch: &RecordBatch) -> Result<(Step, Option<RecordBatch>)> { + let rows = batch.num_rows(); + if rows == 0 { + return Ok((Step::Skip, None)); + } + // A held batch is sized by every buffer it keeps alive, so a small slice of a large batch + // counts as large and passes through. + let bytes = if !self.past_gate { + // Counted as DataFusion's `get_reserved_bytes_for_record_batch` counts it, which the + // sort compares with the threshold. + self.seen_bytes = self + .seen_bytes + .saturating_add(get_record_batch_memory_size(batch) + sliced_size(batch)?); + self.past_gate = self.seen_bytes >= self.gate_bytes; + None + } else if rows >= self.small_rows || has_small_dictionary_keys(batch) { + None + } else if self.backoff > 0 { + self.backoff -= 1; + None + } else { + Some(get_record_batch_memory_size(batch)) Review Comment: Could we budget retained input and materialized output separately here? `get_record_batch_memory_size` counts each buffer address once. A projection such as `named_struct('a', s, 'b', s, ...)` can reuse the same string array for several fields. Arrow concatenates each field into a separate array. [Struct evaluation](https://github.com/apache/datafusion-comet/blob/d1819fd7fe1024fdc0fe7ae8ff7113e9c00e0587/native/spark-expr/src/struct_funcs/create_named_struct.rs#L69-L93) · [Input accounting](https://github.com/apache/datafusion/blob/55.2.0/datafusion/common/src/utils/memory.rs#L166-L211) · [Arrow concatenation](https://github.com/apache/arrow-rs/blob/59.3.2/arrow-select/src/concat.rs#L355-L404) For example, after the gate, take two 256-row batches, each with a 128 KiB string buffer shared by eight fields. Together the inputs fit the 512 KiB cap. We reserve about 512 KiB, then allocate 2 MiB for the strings alone while retaining the inputs. The sort then needs about 4 MiB to admit the result. Counting the output per field before concatenating would let us cap the copy and reserve for both allocations. A test with repeated `Arc::clone`s of one `StringArray` would catch this. ########## native/operators/benches/sort_small_batches.rs: ########## @@ -0,0 +1,171 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Micro-benchmarks for `SortInputCoalesceExec` in front of DataFusion's `SortExec`. +//! +//! A reduce task that reads a shuffle from many map tasks gets one small batch per block. The +//! sort merges one stream per buffered batch, so its cost grows with the number of batches. +//! This compares the sort with and without combining its input, over a range of input batch +//! sizes, with enough memory to sort in memory and with a memory limit that forces spills, and +//! with one sort key and with two. DataFusion combines runs itself only for one key in memory. +//! Keys arrive either scattered, so every batch spans the whole key range, or already in order, +//! the most predictable merge. Keys have a fixed length and no value is null. + +use std::sync::Arc; + +use arrow::array::{ArrayRef, Int64Array, StringArray, StructArray}; +use arrow::compute::SortOptions; +use arrow::datatypes::{DataType, Field, Fields}; +use arrow::record_batch::RecordBatch; +use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion}; +use datafusion::datasource::memory::MemorySourceConfig; +use datafusion::execution::runtime_env::RuntimeEnvBuilder; +use datafusion::physical_expr::expressions::col; +use datafusion::physical_expr::{LexOrdering, PhysicalSortExpr}; +use datafusion::physical_plan::sorts::sort::SortExec; +use datafusion::physical_plan::{common::collect, ExecutionPlan}; +use datafusion::prelude::{SessionConfig, SessionContext}; +use datafusion_comet_operators::SortInputCoalesceExec; +use tokio::runtime::Runtime; + +const ROWS: usize = 200_000; +/// The session batch size, which is also the combined batch's row target. +const BATCH_SIZE: usize = 8192; +/// About a fifth of the input, so the sort spills several times. +const SPILL_MEMORY_LIMIT: usize = 24 * 1024 * 1024; + +/// A string key, a low-cardinality group key, and wide rows: eight longs and a struct, like an +/// aggregate's state. +fn batches(rows_per_batch: usize, scattered: bool) -> Vec<RecordBatch> { + let fields = Fields::from(vec![ + Field::new("a", DataType::Int64, true), + Field::new("b", DataType::Utf8, true), + ]); + (0..ROWS) + .step_by(rows_per_batch) + .map(|start| { + let rows = rows_per_batch.min(ROWS - start); + let ids: Vec<usize> = (start..start + rows) + .map(|i| { + if scattered { + i.wrapping_mul(2_654_435_761) % ROWS + } else { + i + } + }) + .collect(); + let mut columns: Vec<(String, ArrayRef)> = vec![( + "key".into(), + Arc::new(StringArray::from_iter_values( + ids.iter().map(|i| format!("https://example.com/{i:08}")), + )), + )]; + columns.push(( + "g".into(), + Arc::new(Int64Array::from_iter_values( + ids.iter().map(|&i| (i % 64) as i64), Review Comment: The `two_keys/in_order` case sorts by `(g, key)`, so the leading key wraps from 63 to 0 at `i = 64`. At 64 rows per batch every run spans all 64 groups, and at 1,024 rows even a single batch wraps repeatedly. The reported 18% slowdown therefore measures a cyclic leading key. Could we generate contiguous groups with `i * 64 / ROWS`, check lexicographic order across batch boundaries outside the timed loop, and refresh the two-key numbers? ########## native/operators/src/sort_input_coalesce.rs: ########## @@ -0,0 +1,1160 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Combines small input batches before a native sort. +//! +//! On its spill path DataFusion's sort merges one stream per buffered batch, so thousands of +//! tiny shuffle blocks make it very slow. Below the in-place threshold the sort concatenates its +//! input itself, so batches pass through until a partition's input reaches that threshold. The +//! gate never closes again, so a sort whose share is below the threshold gets a copy it does not +//! need. +//! +//! This sits in front of the sort rather than in the shuffle reader because only the sort's merge +//! cost grows with the number of batches. Arrow's `BatchCoalescer` has no byte limit and copies +//! as batches arrive, and `DecodedBatchCoalescer` takes only flat types, so neither lets the held +//! memory be reserved exactly for any input. + +use std::fmt::Formatter; +use std::sync::Arc; + +use arrow::compute::concat_batches; +use arrow::datatypes::DataType; +use arrow::record_batch::RecordBatch; +use datafusion::common::tree_node::TreeNodeRecursion; +use datafusion::common::utils::memory::get_record_batch_memory_size; +use datafusion::common::{DataFusionError, Result}; +use datafusion::execution::memory_pool::{MemoryConsumer, MemoryReservation}; +use datafusion::execution::{async_try_stream, TaskContext}; +use datafusion::physical_expr::PhysicalExpr; +use datafusion::physical_plan::execution_plan::CardinalityEffect; +use datafusion::physical_plan::metrics::{ + BaselineMetrics, Count, ExecutionPlanMetricsSet, MetricBuilder, MetricsSet, +}; +use datafusion::physical_plan::stream::RecordBatchStreamAdapter; +use datafusion::physical_plan::{ + DisplayAs, DisplayFormatType, ExecutionPlan, PlanProperties, SendableRecordBatchStream, +}; +use futures::TryStreamExt; + +/// The cap is half the in-place threshold because the sort reserves about twice a batch's size. +/// The bounds also keep string and binary offsets far below the i32 limit. +const MIN_GROUP_BYTES: usize = 64 * 1024; +const MAX_GROUP_BYTES: usize = 4 * 1024 * 1024; + +/// In `sort_small_batches`, combining 512-row batches made a spilling single-key sort slower, +/// while 384 rows or fewer was never slower. +const MAX_SMALL_BATCH_ROWS: usize = 512; + +/// Small batches passed through after a refusal, so a pool under pressure is not asked again for +/// each one. +const REFUSED_BACKOFF_BATCHES: usize = 64; + +#[derive(Debug)] +pub struct SortInputCoalesceExec { + input: Arc<dyn ExecutionPlan>, + target_rows: usize, + gate_bytes: usize, + max_bytes: usize, + metrics: ExecutionPlanMetricsSet, +} + +impl SortInputCoalesceExec { + /// `gate_bytes` is the sort's in-place threshold. + pub fn new(input: Arc<dyn ExecutionPlan>, target_rows: usize, gate_bytes: usize) -> Self { + Self { + input, + target_rows: target_rows.max(1), + gate_bytes, + max_bytes: (gate_bytes / 2).clamp(MIN_GROUP_BYTES, MAX_GROUP_BYTES), + metrics: ExecutionPlanMetricsSet::new(), + } + } + + #[cfg(test)] + fn with_max_bytes(mut self, max_bytes: usize) -> Self { + self.max_bytes = max_bytes; + self + } + + pub fn input(&self) -> &Arc<dyn ExecutionPlan> { + &self.input + } + + /// The plan below a coalescer, or `plan` itself when it is not one. + pub fn unwrap_input(plan: &Arc<dyn ExecutionPlan>) -> &Arc<dyn ExecutionPlan> { + plan.downcast_ref::<Self>().map_or(plan, Self::input) + } +} + +impl DisplayAs for SortInputCoalesceExec { + fn fmt_as(&self, _t: DisplayFormatType, f: &mut Formatter) -> std::fmt::Result { + write!( + f, + "CometSortInputCoalesceExec: target_rows={}, gate_bytes={}, max_bytes={}", + self.target_rows, self.gate_bytes, self.max_bytes + ) + } +} + +impl ExecutionPlan for SortInputCoalesceExec { + fn name(&self) -> &str { + "CometSortInputCoalesceExec" + } + + fn properties(&self) -> &Arc<PlanProperties> { + self.input.properties() + } + + fn maintains_input_order(&self) -> Vec<bool> { + vec![true] + } + + fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> { + vec![&self.input] + } + + fn apply_expressions( + &self, + _f: &mut dyn FnMut(&Arc<dyn PhysicalExpr>) -> Result<TreeNodeRecursion>, + ) -> Result<TreeNodeRecursion> { + Ok(TreeNodeRecursion::Continue) + } + + fn cardinality_effect(&self) -> CardinalityEffect { + CardinalityEffect::Equal + } + + fn with_new_children( + self: Arc<Self>, + children: Vec<Arc<dyn ExecutionPlan>>, + ) -> Result<Arc<dyn ExecutionPlan>> { + let [input]: [_; 1] = children.try_into().map_err(|_| { + DataFusionError::Internal("Sort input coalescing requires one child".into()) + })?; + Ok(Arc::new(Self { + input, + target_rows: self.target_rows, + gate_bytes: self.gate_bytes, + max_bytes: self.max_bytes, + // Shared, so the copy reports through the node the Spark plan registered for its + // metrics if a rewrite rebuilds the sort's input. + metrics: self.metrics.clone(), + })) + } + + fn execute( + &self, + partition: usize, + context: Arc<TaskContext>, + ) -> Result<SendableRecordBatchStream> { + let mut input = self.input.execute(partition, Arc::clone(&context))?; + let reservation = MemoryConsumer::new(format!("SortInputCoalesceExec[{partition}]")) + .register(context.memory_pool()); + let baseline = BaselineMetrics::new(&self.metrics, partition); + let mut grouper = Grouper::new(self, reservation, partition); + let stream = async_try_stream(|mut out| async move { + while let Some(batch) = input.try_next().await? { + // A group that has to go out first is emitted before the new batch is held, so + // the sort reserves it while this operator holds nothing. + let (step, flushed) = { + let _timer = baseline.elapsed_compute().timer(); + grouper.prepare(&batch)? + }; + if let Some(batch) = flushed { + baseline.record_output(batch.num_rows()); Review Comment: Could we record the emitted batch with `(&batch).record_output(&baseline)` on all three emission paths, as `ExplodeExec` does? Passing the row count updates only `output_rows`. The native plan then reports zero `output_batches` and `output_bytes` even when `coalesced_output_batches` is positive. The total batch count is particularly useful here because it includes the blocks passed through before the gate and tells us how many batches actually reached the sort. [DataFusion counters](https://github.com/apache/datafusion/blob/55.2.0/datafusion/physical-expr-common/src/metrics/baseline.rs#L323-L348) · [Comet example](https://github.com/apache/datafusion-comet/blob/d1819fd7fe1024fdc0fe7ae8ff7113e9c00e0587/native/operators/src/explode.rs#L644-L648) ########## native/core/src/execution/planner/join.rs: ########## @@ -220,7 +220,8 @@ fn reduce_before_sort( let Some(sort) = params.right.native_plan.downcast_ref::<SortExec>() else { return Ok(None); }; - let input = sort.input(); + // The reducer packs its own output, so it replaces any input coalescer. + let input = SortInputCoalesceExec::unwrap_input(sort.input()); Review Comment: Could we keep the coalescer between the reducer and the sort when both options are enabled? The reducer only packs the output of a successful reduction. For the 62-row shuffle blocks described in the PR, every block is below its 1,024-row minimum, so the reducer forwards each one separately. Enabling right-key reduction on an eligible left-semi join would therefore restore the original merge fan-in on the right sort. A test with both flags and a long stream of short blocks could check that bypassed rows still reach the sort in combined batches. [Reducer decision and forwarding](https://github.com/apache/datafusion-comet/blob/d1819fd7fe1024fdc0fe7ae8ff7113e9c00e0587/native/operators/src/membership_key_reduction.rs#L121-L159) ########## native/operators/src/sort_input_coalesce.rs: ########## @@ -0,0 +1,1160 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Combines small input batches before a native sort. +//! +//! On its spill path DataFusion's sort merges one stream per buffered batch, so thousands of +//! tiny shuffle blocks make it very slow. Below the in-place threshold the sort concatenates its +//! input itself, so batches pass through until a partition's input reaches that threshold. The +//! gate never closes again, so a sort whose share is below the threshold gets a copy it does not +//! need. +//! +//! This sits in front of the sort rather than in the shuffle reader because only the sort's merge +//! cost grows with the number of batches. Arrow's `BatchCoalescer` has no byte limit and copies +//! as batches arrive, and `DecodedBatchCoalescer` takes only flat types, so neither lets the held +//! memory be reserved exactly for any input. + +use std::fmt::Formatter; +use std::sync::Arc; + +use arrow::compute::concat_batches; +use arrow::datatypes::DataType; +use arrow::record_batch::RecordBatch; +use datafusion::common::tree_node::TreeNodeRecursion; +use datafusion::common::utils::memory::get_record_batch_memory_size; +use datafusion::common::{DataFusionError, Result}; +use datafusion::execution::memory_pool::{MemoryConsumer, MemoryReservation}; +use datafusion::execution::{async_try_stream, TaskContext}; +use datafusion::physical_expr::PhysicalExpr; +use datafusion::physical_plan::execution_plan::CardinalityEffect; +use datafusion::physical_plan::metrics::{ + BaselineMetrics, Count, ExecutionPlanMetricsSet, MetricBuilder, MetricsSet, +}; +use datafusion::physical_plan::stream::RecordBatchStreamAdapter; +use datafusion::physical_plan::{ + DisplayAs, DisplayFormatType, ExecutionPlan, PlanProperties, SendableRecordBatchStream, +}; +use futures::TryStreamExt; + +/// The cap is half the in-place threshold because the sort reserves about twice a batch's size. +/// The bounds also keep string and binary offsets far below the i32 limit. +const MIN_GROUP_BYTES: usize = 64 * 1024; +const MAX_GROUP_BYTES: usize = 4 * 1024 * 1024; + +/// In `sort_small_batches`, combining 512-row batches made a spilling single-key sort slower, +/// while 384 rows or fewer was never slower. +const MAX_SMALL_BATCH_ROWS: usize = 512; + +/// Small batches passed through after a refusal, so a pool under pressure is not asked again for +/// each one. +const REFUSED_BACKOFF_BATCHES: usize = 64; + +#[derive(Debug)] +pub struct SortInputCoalesceExec { + input: Arc<dyn ExecutionPlan>, + target_rows: usize, + gate_bytes: usize, + max_bytes: usize, + metrics: ExecutionPlanMetricsSet, +} + +impl SortInputCoalesceExec { + /// `gate_bytes` is the sort's in-place threshold. + pub fn new(input: Arc<dyn ExecutionPlan>, target_rows: usize, gate_bytes: usize) -> Self { + Self { + input, + target_rows: target_rows.max(1), + gate_bytes, + max_bytes: (gate_bytes / 2).clamp(MIN_GROUP_BYTES, MAX_GROUP_BYTES), + metrics: ExecutionPlanMetricsSet::new(), + } + } + + #[cfg(test)] + fn with_max_bytes(mut self, max_bytes: usize) -> Self { + self.max_bytes = max_bytes; + self + } + + pub fn input(&self) -> &Arc<dyn ExecutionPlan> { + &self.input + } + + /// The plan below a coalescer, or `plan` itself when it is not one. + pub fn unwrap_input(plan: &Arc<dyn ExecutionPlan>) -> &Arc<dyn ExecutionPlan> { + plan.downcast_ref::<Self>().map_or(plan, Self::input) + } +} + +impl DisplayAs for SortInputCoalesceExec { + fn fmt_as(&self, _t: DisplayFormatType, f: &mut Formatter) -> std::fmt::Result { + write!( + f, + "CometSortInputCoalesceExec: target_rows={}, gate_bytes={}, max_bytes={}", + self.target_rows, self.gate_bytes, self.max_bytes + ) + } +} + +impl ExecutionPlan for SortInputCoalesceExec { + fn name(&self) -> &str { + "CometSortInputCoalesceExec" + } + + fn properties(&self) -> &Arc<PlanProperties> { + self.input.properties() + } + + fn maintains_input_order(&self) -> Vec<bool> { + vec![true] + } + + fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> { + vec![&self.input] + } + + fn apply_expressions( + &self, + _f: &mut dyn FnMut(&Arc<dyn PhysicalExpr>) -> Result<TreeNodeRecursion>, + ) -> Result<TreeNodeRecursion> { + Ok(TreeNodeRecursion::Continue) + } + + fn cardinality_effect(&self) -> CardinalityEffect { + CardinalityEffect::Equal + } + + fn with_new_children( + self: Arc<Self>, + children: Vec<Arc<dyn ExecutionPlan>>, + ) -> Result<Arc<dyn ExecutionPlan>> { + let [input]: [_; 1] = children.try_into().map_err(|_| { + DataFusionError::Internal("Sort input coalescing requires one child".into()) + })?; + Ok(Arc::new(Self { + input, + target_rows: self.target_rows, + gate_bytes: self.gate_bytes, + max_bytes: self.max_bytes, + // Shared, so the copy reports through the node the Spark plan registered for its + // metrics if a rewrite rebuilds the sort's input. + metrics: self.metrics.clone(), + })) + } + + fn execute( + &self, + partition: usize, + context: Arc<TaskContext>, + ) -> Result<SendableRecordBatchStream> { + let mut input = self.input.execute(partition, Arc::clone(&context))?; + let reservation = MemoryConsumer::new(format!("SortInputCoalesceExec[{partition}]")) + .register(context.memory_pool()); + let baseline = BaselineMetrics::new(&self.metrics, partition); + let mut grouper = Grouper::new(self, reservation, partition); + let stream = async_try_stream(|mut out| async move { + while let Some(batch) = input.try_next().await? { + // A group that has to go out first is emitted before the new batch is held, so + // the sort reserves it while this operator holds nothing. + let (step, flushed) = { + let _timer = baseline.elapsed_compute().timer(); + grouper.prepare(&batch)? + }; + if let Some(batch) = flushed { + baseline.record_output(batch.num_rows()); + out.emit(batch).await; + } + let ready = { + let _timer = baseline.elapsed_compute().timer(); + grouper.add(batch, step)? + }; + for batch in ready.into_iter().flatten() { + baseline.record_output(batch.num_rows()); + out.emit(batch).await; + } + } + let last = { + let _timer = baseline.elapsed_compute().timer(); + grouper.flush()? + }; + if let Some(batch) = last { + baseline.record_output(batch.num_rows()); + out.emit(batch).await; + } + Ok(()) + }); + Ok(Box::pin(RecordBatchStreamAdapter::new( + self.schema(), + stream, + ))) + } + + fn metrics(&self) -> Option<MetricsSet> { + Some(self.metrics.clone_inner()) + } +} + +/// Concatenating dictionaries merges their values, which can overflow a small key type where +/// the batches on their own fit. Dictionaries nested in structs, lists and maps count too. +fn has_small_dictionary_keys(batch: &RecordBatch) -> bool { + fn small(data_type: &DataType) -> bool { + match data_type { + DataType::Dictionary(key, value) => { + key.primitive_width().is_some_and(|width| width < 4) || small(value) + } + DataType::Struct(fields) => fields.iter().any(|f| small(f.data_type())), + DataType::List(f) + | DataType::LargeList(f) + | DataType::ListView(f) + | DataType::LargeListView(f) + | DataType::FixedSizeList(f, _) + | DataType::Map(f, _) => small(f.data_type()), + // Run ends count rows, so a small run-end type can overflow too. + DataType::RunEndEncoded(run_ends, values) => { + run_ends + .data_type() + .primitive_width() + .is_some_and(|width| width < 4) + || small(values.data_type()) + } + _ => false, + } + } + batch.schema().fields().iter().any(|f| small(f.data_type())) +} + +/// The bytes the batch's rows take, without unused buffer capacity, as DataFusion's sort counts +/// it. +fn sliced_size(batch: &RecordBatch) -> Result<usize> { + batch.columns().iter().try_fold(0usize, |total, column| { + Ok(total + column.to_data().get_slice_memory_size()?) + }) +} + +enum Step { + Skip, + PassThrough, + /// Size in bytes. + Hold(usize), +} + +/// Groups whole input batches in arrival order and concatenates each group. Inputs are never +/// split, so the reservation always covers the batches being held. +struct Grouper { + target_rows: usize, + small_rows: usize, + gate_bytes: usize, + max_bytes: usize, + seen_bytes: usize, + past_gate: bool, + pending: Vec<RecordBatch>, + rows: usize, + bytes: usize, + reservation: MemoryReservation, + backoff: usize, + input_batches: Count, + output_batches: Count, +} + +impl Grouper { + fn new(exec: &SortInputCoalesceExec, reservation: MemoryReservation, partition: usize) -> Self { + let metrics = MetricBuilder::new(&exec.metrics); + Self { + target_rows: exec.target_rows, + small_rows: exec.target_rows.div_ceil(2).min(MAX_SMALL_BATCH_ROWS), + gate_bytes: exec.gate_bytes, + max_bytes: exec.max_bytes, + seen_bytes: 0, + past_gate: exec.gate_bytes == 0, + pending: Vec::new(), + rows: 0, + bytes: 0, + reservation, + backoff: 0, + input_batches: metrics + .clone() + .counter("coalesced_input_batches", partition), + output_batches: metrics.counter("coalesced_output_batches", partition), + } + } + + /// Decides what `add` does with `batch`. Returns the held group too when it has to go out + /// first: before a batch that passes through, or before one that does not fit in the group. + fn prepare(&mut self, batch: &RecordBatch) -> Result<(Step, Option<RecordBatch>)> { + let rows = batch.num_rows(); + if rows == 0 { + return Ok((Step::Skip, None)); + } + // A held batch is sized by every buffer it keeps alive, so a small slice of a large batch + // counts as large and passes through. + let bytes = if !self.past_gate { + // Counted as DataFusion's `get_reserved_bytes_for_record_batch` counts it, which the + // sort compares with the threshold. + self.seen_bytes = self + .seen_bytes + .saturating_add(get_record_batch_memory_size(batch) + sliced_size(batch)?); + self.past_gate = self.seen_bytes >= self.gate_bytes; + None + } else if rows >= self.small_rows || has_small_dictionary_keys(batch) { + None + } else if self.backoff > 0 { + self.backoff -= 1; + None + } else { + Some(get_record_batch_memory_size(batch)) + }; + match bytes.filter(|&bytes| bytes <= self.max_bytes) { + Some(bytes) => { + // A batch with another schema starts a new group, since the concat needs one. + let fits = rows <= self.target_rows - self.rows + && bytes <= self.max_bytes - self.bytes + && self + .pending + .first() + .is_none_or(|held| held.schema() == batch.schema()); + let flushed = if fits { None } else { self.flush()? }; + Ok((Step::Hold(bytes), flushed)) + } + None => Ok((Step::PassThrough, self.flush()?)), + } + } + + /// Returns what is ready, in input order: a flushed group, then `batch` when it is not held. + fn add(&mut self, batch: RecordBatch, step: Step) -> Result<[Option<RecordBatch>; 2]> { + let bytes = match step { + Step::Skip => return Ok([None, None]), + Step::PassThrough => return Ok([None, Some(batch)]), + Step::Hold(bytes) => bytes, + }; + let rows = batch.num_rows(); + if !self.reserve(bytes)? { + // The sort can spill and this cannot, so hand it everything. + self.backoff = REFUSED_BACKOFF_BATCHES; + return Ok([self.flush()?, Some(batch)]); + } + self.pending.push(batch); + self.rows += rows; + self.bytes += bytes; + if self.rows == self.target_rows || self.bytes == self.max_bytes { + return Ok([self.flush()?, None]); + } + Ok([None, None]) + } + + #[cfg(test)] + fn push(&mut self, batch: RecordBatch) -> Result<Vec<RecordBatch>> { + let (step, flushed) = self.prepare(&batch)?; + let mut ready: Vec<_> = flushed.into_iter().collect(); + ready.extend(self.add(batch, step)?.into_iter().flatten()); + Ok(ready) + } + + /// Reserves the held bytes plus `bytes`, twice over for the combined copy, and no more: a + /// consumer that cannot spill is checked only against the whole pool, so asking ahead could + /// make Spark spill another consumer for memory never used. Returns false when refused. + fn reserve(&mut self, bytes: usize) -> Result<bool> { + let needed = 2 * (self.bytes + bytes); + let size = self.reservation.size(); + if needed <= size { + return Ok(true); + } + match self.reservation.try_grow(needed - size) { Review Comment: This request can spill a JVM operator before we know whether there is a second batch to combine. With `fair_unified` and the sort at its share, the original sort request hits the local limit and triggers a native spill. The unspillable coalescer goes straight to Spark, which can spill a resident `UnsafeExternalSorter` to grant the request. That disk write has already happened even if the next batch forces a one-batch flush. We measured this behavior with a temporary reservation in #7190. [Prior spill measurement](https://github.com/apache/datafusion-comet/pull/7190#discussion_r4366212677) Could we apply the same resident-memory guard used for semi-join reduction, or charge this request against the sort's remaining share before calling Spark? The existing admission test could exercise this with small blocks and a sibling that counts spill calls. [Planner guard](https://github.com/apache/datafusion-comet/blob/d1819fd7fe1024fdc0fe7ae8ff7113e9c00e0587/native/core/src/execution/planner/join.rs#L238-L265) · [Spark test](https://github.com/apache/datafusion-comet/blob/d1819fd7fe1024fdc0fe7ae8ff7113e9c00e0587/spark/src/test/scala/org/apache/comet/exec/CometJoinSuite.scala#L1828) ########## native/operators/src/sort_input_coalesce.rs: ########## @@ -0,0 +1,1160 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Combines small input batches before a native sort. +//! +//! On its spill path DataFusion's sort merges one stream per buffered batch, so thousands of +//! tiny shuffle blocks make it very slow. Below the in-place threshold the sort concatenates its +//! input itself, so batches pass through until a partition's input reaches that threshold. The +//! gate never closes again, so a sort whose share is below the threshold gets a copy it does not +//! need. +//! +//! This sits in front of the sort rather than in the shuffle reader because only the sort's merge +//! cost grows with the number of batches. Arrow's `BatchCoalescer` has no byte limit and copies +//! as batches arrive, and `DecodedBatchCoalescer` takes only flat types, so neither lets the held +//! memory be reserved exactly for any input. + +use std::fmt::Formatter; +use std::sync::Arc; + +use arrow::compute::concat_batches; +use arrow::datatypes::DataType; +use arrow::record_batch::RecordBatch; +use datafusion::common::tree_node::TreeNodeRecursion; +use datafusion::common::utils::memory::get_record_batch_memory_size; +use datafusion::common::{DataFusionError, Result}; +use datafusion::execution::memory_pool::{MemoryConsumer, MemoryReservation}; +use datafusion::execution::{async_try_stream, TaskContext}; +use datafusion::physical_expr::PhysicalExpr; +use datafusion::physical_plan::execution_plan::CardinalityEffect; +use datafusion::physical_plan::metrics::{ + BaselineMetrics, Count, ExecutionPlanMetricsSet, MetricBuilder, MetricsSet, +}; +use datafusion::physical_plan::stream::RecordBatchStreamAdapter; +use datafusion::physical_plan::{ + DisplayAs, DisplayFormatType, ExecutionPlan, PlanProperties, SendableRecordBatchStream, +}; +use futures::TryStreamExt; + +/// The cap is half the in-place threshold because the sort reserves about twice a batch's size. +/// The bounds also keep string and binary offsets far below the i32 limit. +const MIN_GROUP_BYTES: usize = 64 * 1024; +const MAX_GROUP_BYTES: usize = 4 * 1024 * 1024; + +/// In `sort_small_batches`, combining 512-row batches made a spilling single-key sort slower, +/// while 384 rows or fewer was never slower. +const MAX_SMALL_BATCH_ROWS: usize = 512; + +/// Small batches passed through after a refusal, so a pool under pressure is not asked again for +/// each one. +const REFUSED_BACKOFF_BATCHES: usize = 64; + +#[derive(Debug)] +pub struct SortInputCoalesceExec { + input: Arc<dyn ExecutionPlan>, + target_rows: usize, + gate_bytes: usize, + max_bytes: usize, + metrics: ExecutionPlanMetricsSet, +} + +impl SortInputCoalesceExec { + /// `gate_bytes` is the sort's in-place threshold. + pub fn new(input: Arc<dyn ExecutionPlan>, target_rows: usize, gate_bytes: usize) -> Self { + Self { + input, + target_rows: target_rows.max(1), + gate_bytes, + max_bytes: (gate_bytes / 2).clamp(MIN_GROUP_BYTES, MAX_GROUP_BYTES), + metrics: ExecutionPlanMetricsSet::new(), + } + } + + #[cfg(test)] + fn with_max_bytes(mut self, max_bytes: usize) -> Self { + self.max_bytes = max_bytes; + self + } + + pub fn input(&self) -> &Arc<dyn ExecutionPlan> { + &self.input + } + + /// The plan below a coalescer, or `plan` itself when it is not one. + pub fn unwrap_input(plan: &Arc<dyn ExecutionPlan>) -> &Arc<dyn ExecutionPlan> { + plan.downcast_ref::<Self>().map_or(plan, Self::input) + } +} + +impl DisplayAs for SortInputCoalesceExec { + fn fmt_as(&self, _t: DisplayFormatType, f: &mut Formatter) -> std::fmt::Result { + write!( + f, + "CometSortInputCoalesceExec: target_rows={}, gate_bytes={}, max_bytes={}", + self.target_rows, self.gate_bytes, self.max_bytes + ) + } +} + +impl ExecutionPlan for SortInputCoalesceExec { + fn name(&self) -> &str { + "CometSortInputCoalesceExec" + } + + fn properties(&self) -> &Arc<PlanProperties> { + self.input.properties() + } + + fn maintains_input_order(&self) -> Vec<bool> { + vec![true] + } + + fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> { + vec![&self.input] + } + + fn apply_expressions( + &self, + _f: &mut dyn FnMut(&Arc<dyn PhysicalExpr>) -> Result<TreeNodeRecursion>, + ) -> Result<TreeNodeRecursion> { + Ok(TreeNodeRecursion::Continue) + } + + fn cardinality_effect(&self) -> CardinalityEffect { + CardinalityEffect::Equal + } + + fn with_new_children( + self: Arc<Self>, + children: Vec<Arc<dyn ExecutionPlan>>, + ) -> Result<Arc<dyn ExecutionPlan>> { + let [input]: [_; 1] = children.try_into().map_err(|_| { + DataFusionError::Internal("Sort input coalescing requires one child".into()) + })?; + Ok(Arc::new(Self { + input, + target_rows: self.target_rows, + gate_bytes: self.gate_bytes, + max_bytes: self.max_bytes, + // Shared, so the copy reports through the node the Spark plan registered for its + // metrics if a rewrite rebuilds the sort's input. + metrics: self.metrics.clone(), + })) + } + + fn execute( + &self, + partition: usize, + context: Arc<TaskContext>, + ) -> Result<SendableRecordBatchStream> { + let mut input = self.input.execute(partition, Arc::clone(&context))?; + let reservation = MemoryConsumer::new(format!("SortInputCoalesceExec[{partition}]")) + .register(context.memory_pool()); + let baseline = BaselineMetrics::new(&self.metrics, partition); + let mut grouper = Grouper::new(self, reservation, partition); + let stream = async_try_stream(|mut out| async move { + while let Some(batch) = input.try_next().await? { + // A group that has to go out first is emitted before the new batch is held, so + // the sort reserves it while this operator holds nothing. + let (step, flushed) = { + let _timer = baseline.elapsed_compute().timer(); + grouper.prepare(&batch)? + }; + if let Some(batch) = flushed { + baseline.record_output(batch.num_rows()); + out.emit(batch).await; + } + let ready = { + let _timer = baseline.elapsed_compute().timer(); + grouper.add(batch, step)? + }; + for batch in ready.into_iter().flatten() { + baseline.record_output(batch.num_rows()); + out.emit(batch).await; + } + } + let last = { + let _timer = baseline.elapsed_compute().timer(); + grouper.flush()? + }; + if let Some(batch) = last { + baseline.record_output(batch.num_rows()); + out.emit(batch).await; + } + Ok(()) + }); + Ok(Box::pin(RecordBatchStreamAdapter::new( + self.schema(), + stream, + ))) + } + + fn metrics(&self) -> Option<MetricsSet> { + Some(self.metrics.clone_inner()) + } +} + +/// Concatenating dictionaries merges their values, which can overflow a small key type where +/// the batches on their own fit. Dictionaries nested in structs, lists and maps count too. +fn has_small_dictionary_keys(batch: &RecordBatch) -> bool { + fn small(data_type: &DataType) -> bool { + match data_type { + DataType::Dictionary(key, value) => { + key.primitive_width().is_some_and(|width| width < 4) || small(value) + } + DataType::Struct(fields) => fields.iter().any(|f| small(f.data_type())), + DataType::List(f) + | DataType::LargeList(f) + | DataType::ListView(f) + | DataType::LargeListView(f) + | DataType::FixedSizeList(f, _) + | DataType::Map(f, _) => small(f.data_type()), + // Run ends count rows, so a small run-end type can overflow too. + DataType::RunEndEncoded(run_ends, values) => { + run_ends + .data_type() + .primitive_width() + .is_some_and(|width| width < 4) + || small(values.data_type()) + } + _ => false, + } + } + batch.schema().fields().iter().any(|f| small(f.data_type())) +} + +/// The bytes the batch's rows take, without unused buffer capacity, as DataFusion's sort counts +/// it. +fn sliced_size(batch: &RecordBatch) -> Result<usize> { + batch.columns().iter().try_fold(0usize, |total, column| { + Ok(total + column.to_data().get_slice_memory_size()?) + }) +} + +enum Step { + Skip, + PassThrough, + /// Size in bytes. + Hold(usize), +} + +/// Groups whole input batches in arrival order and concatenates each group. Inputs are never +/// split, so the reservation always covers the batches being held. +struct Grouper { + target_rows: usize, + small_rows: usize, + gate_bytes: usize, + max_bytes: usize, + seen_bytes: usize, + past_gate: bool, + pending: Vec<RecordBatch>, + rows: usize, + bytes: usize, + reservation: MemoryReservation, + backoff: usize, + input_batches: Count, + output_batches: Count, +} + +impl Grouper { + fn new(exec: &SortInputCoalesceExec, reservation: MemoryReservation, partition: usize) -> Self { + let metrics = MetricBuilder::new(&exec.metrics); + Self { + target_rows: exec.target_rows, + small_rows: exec.target_rows.div_ceil(2).min(MAX_SMALL_BATCH_ROWS), + gate_bytes: exec.gate_bytes, + max_bytes: exec.max_bytes, + seen_bytes: 0, + past_gate: exec.gate_bytes == 0, + pending: Vec::new(), + rows: 0, + bytes: 0, + reservation, + backoff: 0, + input_batches: metrics + .clone() + .counter("coalesced_input_batches", partition), + output_batches: metrics.counter("coalesced_output_batches", partition), + } + } + + /// Decides what `add` does with `batch`. Returns the held group too when it has to go out + /// first: before a batch that passes through, or before one that does not fit in the group. + fn prepare(&mut self, batch: &RecordBatch) -> Result<(Step, Option<RecordBatch>)> { + let rows = batch.num_rows(); + if rows == 0 { + return Ok((Step::Skip, None)); + } + // A held batch is sized by every buffer it keeps alive, so a small slice of a large batch + // counts as large and passes through. + let bytes = if !self.past_gate { + // Counted as DataFusion's `get_reserved_bytes_for_record_batch` counts it, which the + // sort compares with the threshold. + self.seen_bytes = self + .seen_bytes + .saturating_add(get_record_batch_memory_size(batch) + sliced_size(batch)?); + self.past_gate = self.seen_bytes >= self.gate_bytes; + None + } else if rows >= self.small_rows || has_small_dictionary_keys(batch) { + None + } else if self.backoff > 0 { + self.backoff -= 1; + None + } else { + Some(get_record_batch_memory_size(batch)) + }; + match bytes.filter(|&bytes| bytes <= self.max_bytes) { + Some(bytes) => { + // A batch with another schema starts a new group, since the concat needs one. + let fits = rows <= self.target_rows - self.rows + && bytes <= self.max_bytes - self.bytes + && self + .pending + .first() + .is_none_or(|held| held.schema() == batch.schema()); + let flushed = if fits { None } else { self.flush()? }; + Ok((Step::Hold(bytes), flushed)) + } + None => Ok((Step::PassThrough, self.flush()?)), + } + } + + /// Returns what is ready, in input order: a flushed group, then `batch` when it is not held. + fn add(&mut self, batch: RecordBatch, step: Step) -> Result<[Option<RecordBatch>; 2]> { + let bytes = match step { + Step::Skip => return Ok([None, None]), + Step::PassThrough => return Ok([None, Some(batch)]), + Step::Hold(bytes) => bytes, + }; + let rows = batch.num_rows(); + if !self.reserve(bytes)? { + // The sort can spill and this cannot, so hand it everything. + self.backoff = REFUSED_BACKOFF_BATCHES; + return Ok([self.flush()?, Some(batch)]); + } + self.pending.push(batch); + self.rows += rows; + self.bytes += bytes; + if self.rows == self.target_rows || self.bytes == self.max_bytes { + return Ok([self.flush()?, None]); + } + Ok([None, None]) + } + + #[cfg(test)] + fn push(&mut self, batch: RecordBatch) -> Result<Vec<RecordBatch>> { + let (step, flushed) = self.prepare(&batch)?; + let mut ready: Vec<_> = flushed.into_iter().collect(); + ready.extend(self.add(batch, step)?.into_iter().flatten()); + Ok(ready) + } + + /// Reserves the held bytes plus `bytes`, twice over for the combined copy, and no more: a + /// consumer that cannot spill is checked only against the whole pool, so asking ahead could + /// make Spark spill another consumer for memory never used. Returns false when refused. + fn reserve(&mut self, bytes: usize) -> Result<bool> { + let needed = 2 * (self.bytes + bytes); + let size = self.reservation.size(); + if needed <= size { + return Ok(true); + } + match self.reservation.try_grow(needed - size) { + Ok(()) => Ok(true), + Err(DataFusionError::ResourcesExhausted(_)) => Ok(false), + Err(error) => Err(error), + } + } + + fn flush(&mut self) -> Result<Option<RecordBatch>> { + let out = match self.pending.len() { + 0 => None, + 1 => self.pending.pop(), + n => { + // The inputs' own schema, which a batch that passes through also keeps. + let combined = concat_batches(&self.pending[0].schema(), &self.pending)?; + self.pending.clear(); + self.input_batches.add(n); + self.output_batches.add(1); + Some(combined) + } + }; + // The sort reserves what it buffers, so hold nothing between groups. + self.reservation.free(); + self.rows = 0; + self.bytes = 0; + Ok(out) + } +} + +#[cfg(test)] +mod tests { + use super::*; + use arrow::array::{ + Array, ArrayRef, AsArray, Date32Array, Decimal128Array, Int32Array, Int64Array, ListArray, + MapArray, StringArray, StringDictionaryBuilder, StructArray, TimestampMicrosecondArray, + }; + use arrow::datatypes::{DataType, Field, Fields, Int32Type, Int64Type, Schema, SchemaRef}; + use datafusion::datasource::memory::MemorySourceConfig; + use datafusion::execution::memory_pool::{GreedyMemoryPool, MemoryPool}; + use datafusion::execution::runtime_env::RuntimeEnvBuilder; + use datafusion::physical_plan::common::collect; + use datafusion::prelude::{SessionConfig, SessionContext}; + + fn ints(values: std::ops::Range<i32>) -> RecordBatch { + RecordBatch::try_from_iter([( + "k", + Arc::new(Int32Array::from_iter_values(values)) as ArrayRef, + )]) + .unwrap() + } + + fn ten_row_batches(n: i32) -> Vec<RecordBatch> { + (0..n).map(|i| ints(i * 10..i * 10 + 10)).collect() + } + + fn run_with( + input: Vec<RecordBatch>, + schema: SchemaRef, + exec: impl FnOnce(Arc<dyn ExecutionPlan>) -> SortInputCoalesceExec, + ctx: SessionContext, + ) -> (Vec<RecordBatch>, MetricsSet) { + let source = MemorySourceConfig::try_new_exec(&[input], schema, None).unwrap(); + let exec = exec(source); + let rt = tokio::runtime::Builder::new_current_thread() + .build() + .unwrap(); + let output = rt + .block_on(collect(exec.execute(0, ctx.task_ctx()).unwrap())) + .unwrap(); + (output, exec.metrics().unwrap()) + } + + fn run( + input: Vec<RecordBatch>, + target_rows: usize, + gate_bytes: usize, + max_bytes: usize, + ) -> (Vec<RecordBatch>, MetricsSet) { + let schema = input[0].schema(); + run_with( + input, + schema, + |source| { + SortInputCoalesceExec::new(source, target_rows, gate_bytes) + .with_max_bytes(max_bytes) + }, + SessionContext::new(), + ) + } + + fn row_counts(batches: &[RecordBatch]) -> Vec<usize> { + batches.iter().map(|b| b.num_rows()).collect() + } + + fn same_rows(output: &[RecordBatch], input: &[RecordBatch]) { + let schema = input[0].schema(); + assert_eq!( + concat_batches(&schema, output).unwrap(), + concat_batches(&schema, input).unwrap() + ); + } + + fn metric(metrics: &MetricsSet, name: &str) -> usize { + metrics.sum_by_name(name).map(|v| v.as_usize()).unwrap_or(0) + } + + #[test] + fn small_partitions_pass_through_without_a_copy() { + let input = ten_row_batches(10); + let (output, _) = run(input.clone(), 1024, usize::MAX, MAX_GROUP_BYTES); + assert_eq!(output, input); + for (out, inp) in output.iter().zip(&input) { + assert!(Arc::ptr_eq(out.column(0), inp.column(0))); + } + } + + #[test] + fn combines_small_batches_after_the_gate_in_input_order() { + let input = ten_row_batches(10); + // A zero gate starts combining with the first batch. + let (output, metrics) = run(input.clone(), 40, 0, MAX_GROUP_BYTES); + assert_eq!(row_counts(&output), [40, 40, 20]); + same_rows(&output, &input); + assert_eq!(metric(&metrics, "coalesced_input_batches"), 10); + assert_eq!(metric(&metrics, "coalesced_output_batches"), 3); + assert_eq!(metrics.output_rows(), Some(100)); + } + + #[test] + fn a_rebuilt_coalescer_reports_through_the_original() { + let input = ten_row_batches(10); + let schema = input[0].schema(); + let source = MemorySourceConfig::try_new_exec(&[input], schema, None).unwrap(); + let original = Arc::new(SortInputCoalesceExec::new( + Arc::clone(&source) as Arc<dyn ExecutionPlan>, + 40, + 0, + )); + let rebuilt = (Arc::clone(&original) as Arc<dyn ExecutionPlan>) + .replace_children( + vec![source], + datafusion::physical_plan::ReplaceChildrenOptions::new( + datafusion::physical_plan::ChildrenPropertiesMode::Recompute, + ), + ) + .unwrap(); + let rt = tokio::runtime::Builder::new_current_thread() + .build() + .unwrap(); + rt.block_on(collect( + rebuilt + .execute(0, SessionContext::new().task_ctx()) + .unwrap(), + )) + .unwrap(); + let metrics = original.metrics().unwrap(); + assert_eq!(metric(&metrics, "coalesced_input_batches"), 10); + } + + #[test] + fn the_gate_counts_bytes_before_combining() { + let input = ten_row_batches(10); + // The gate counts each batch as the sort does: memory size plus sliced size. + let one = get_record_batch_memory_size(&input[0]) + sliced_size(&input[0]).unwrap(); + // The first three batches pass through; the third one crosses the gate. + let (output, _) = run(input.clone(), 40, one * 2 + 1, MAX_GROUP_BYTES); + assert_eq!(row_counts(&output), [10, 10, 10, 40, 30]); + same_rows(&output, &input); + } + + #[test] + fn byte_cap_flushes_before_the_row_target() { + let input = ten_row_batches(6); + let one = get_record_batch_memory_size(&input[0]); + let (output, _) = run(input.clone(), 1000, 0, one * 2); + assert_eq!(row_counts(&output), [20, 20, 20]); + same_rows(&output, &input); + } + + #[test] + fn large_batches_pass_through_after_flushing_the_group() { + let small = ints(0..10); + let large = ints(100..150); + let input = vec![small.clone(), small.clone(), large.clone(), small.clone()]; + let (output, _) = run(input.clone(), 100, 0, MAX_GROUP_BYTES); + assert_eq!(row_counts(&output), [20, 50, 10]); + assert!(Arc::ptr_eq(output[1].column(0), large.column(0))); + same_rows(&output, &input); + } + + #[test] + fn batches_of_512_rows_or_more_pass_through_at_the_default_target() { + let mid = ints(0..MAX_SMALL_BATCH_ROWS as i32); + let small = ints(0..(MAX_SMALL_BATCH_ROWS - 1) as i32); + let input = vec![mid.clone(), mid.clone(), small.clone(), small.clone()]; + let (output, _) = run(input.clone(), 8192, 0, MAX_GROUP_BYTES); + assert_eq!(row_counts(&output), [512, 512, 1022]); + assert!(Arc::ptr_eq(output[0].column(0), mid.column(0))); + same_rows(&output, &input); + } + + #[test] + fn empty_input_and_empty_batches() { + let schema = ints(0..1).schema(); + let (output, _) = run_with( + vec![], + Arc::clone(&schema), + |source| SortInputCoalesceExec::new(source, 8, 0), + SessionContext::new(), + ); + assert!(output.is_empty()); + + let input = vec![ints(0..0), ints(0..3), ints(0..0), ints(3..5)]; + let (output, _) = run(input.clone(), 8, 0, MAX_GROUP_BYTES); + assert_eq!(row_counts(&output), [5]); + same_rows(&output, &input); + } + + #[test] + fn passes_through_when_memory_is_short() { + let input = ten_row_batches(4); + let schema = input[0].schema(); + let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1)); + let runtime = RuntimeEnvBuilder::new() + .with_memory_pool(Arc::clone(&pool)) + .build_arc() + .unwrap(); + let ctx = SessionContext::new_with_config_rt(SessionConfig::new(), runtime); + let (output, _) = run_with( + input.clone(), + schema, + |source| SortInputCoalesceExec::new(source, 40, 0), + ctx, + ); + assert_eq!(output, input); + assert_eq!(pool.reserved(), 0); + } + + #[test] + fn the_group_cap_is_half_the_in_place_threshold() { + let cap = |gate| { + let source = + MemorySourceConfig::try_new_exec(&[vec![]], ints(0..1).schema(), None).unwrap(); + SortInputCoalesceExec::new(source, 8192, gate).max_bytes + }; + assert_eq!(cap(1024 * 1024), 512 * 1024); + assert_eq!(cap(0), MIN_GROUP_BYTES); + assert_eq!(cap(usize::MAX), MAX_GROUP_BYTES); + } + + #[test] + fn reservation_covers_a_group_and_is_released_after_it() { + let input = ten_row_batches(3); + let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 30)); + let source = MemorySourceConfig::try_new_exec(&[vec![]], input[0].schema(), None).unwrap(); + let exec = SortInputCoalesceExec::new(source, 1000, 0); + let mut grouper = Grouper::new(&exec, MemoryConsumer::new("test").register(&pool), 0); + // The reservation covers exactly the held batches and their copy. + let mut held = 0; + for batch in &input { + held += get_record_batch_memory_size(batch); + assert!(grouper.push(batch.clone()).unwrap().is_empty()); + assert_eq!(pool.reserved(), 2 * held); + } + let combined = grouper.flush().unwrap().unwrap(); + assert_eq!( + combined, + concat_batches(&input[0].schema(), &input).unwrap() + ); + // The sort reserves the combined batch itself. + assert_eq!(pool.reserved(), 0); + assert!(grouper.flush().unwrap().is_none()); + } + + fn run_in_pool( + input: Vec<RecordBatch>, + target_rows: usize, + pool_bytes: usize, + ) -> Vec<RecordBatch> { + let schema = input[0].schema(); + let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(pool_bytes)); + let runtime = RuntimeEnvBuilder::new() + .with_memory_pool(Arc::clone(&pool)) + .build_arc() + .unwrap(); + let ctx = SessionContext::new_with_config_rt(SessionConfig::new(), runtime); + let (output, _) = run_with( + input, + schema, + |source| SortInputCoalesceExec::new(source, target_rows, 0), + ctx, + ); + assert_eq!(pool.reserved(), 0); + output + } + + #[test] + fn combines_when_the_pool_holds_the_group_but_not_a_full_one() { + let input = ten_row_batches(3); + let one = get_record_batch_memory_size(&input[0]); + // Room for these three batches and their copy, far less than a full group. + let output = run_in_pool(input.clone(), 30, 2 * 3 * one); + assert_eq!(row_counts(&output), [30]); + same_rows(&output, &input); + } + + #[test] + fn a_refused_reservation_flushes_the_held_group_first() { + let input = ten_row_batches(4); + let one = get_record_batch_memory_size(&input[0]); + // Room for two batches and their copy. The third is refused, so the first two go out + // combined and the third passes through. The fourth starts a new group. + let output = run_in_pool(input.clone(), 1000, 2 * 2 * one); + assert_eq!(row_counts(&output), [20, 10, 10]); + same_rows(&output, &input); + } + + #[tokio::test] + async fn holds_no_memory_while_the_sort_takes_a_batch() { + let input = ten_row_batches(10); + let schema = input[0].schema(); + let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 30)); + let runtime = RuntimeEnvBuilder::new() + .with_memory_pool(Arc::clone(&pool)) + .build_arc() + .unwrap(); + let ctx = SessionContext::new_with_config_rt(SessionConfig::new(), runtime); + let source = MemorySourceConfig::try_new_exec(&[input], schema, None).unwrap(); + // A 25-row target makes every third batch overflow the group. + let exec = SortInputCoalesceExec::new(source, 25, 0); + let mut stream = exec.execute(0, ctx.task_ctx()).unwrap(); + let mut rows = vec![]; + while let Some(batch) = stream.try_next().await.unwrap() { + assert_eq!(pool.reserved(), 0, "held memory while handing on a batch"); + rows.push(batch.num_rows()); + } + assert_eq!(rows, [20, 20, 20, 20, 20]); + } + + #[test] + fn after_a_refusal_the_next_batches_pass_through() { + let input = ten_row_batches(6); + let one = get_record_batch_memory_size(&input[0]); + // Room for two batches and their copy, so the third is refused. The ones after it pass + // through without asking the pool again. + let output = run_in_pool(input.clone(), 1000, 2 * 2 * one); + assert_eq!(row_counts(&output), [20, 10, 10, 10, 10]); + same_rows(&output, &input); + } + + #[test] + fn combining_resumes_after_the_backoff() { + let input = ten_row_batches(70); + let one = get_record_batch_memory_size(&input[0]); + // Room for two batches and their copy. The third is refused, it and the next 64 pass + // through, and then two more are combined before the next refusal. + let output = run_in_pool(input.clone(), 1000, 2 * 2 * one); + let mut expected = vec![20]; + expected.extend([10; 1 + REFUSED_BACKOFF_BATCHES]); + expected.extend([20, 10]); + assert_eq!(row_counts(&output), expected); + same_rows(&output, &input); + } + + #[test] + fn a_small_slice_of_a_large_batch_passes_through() { + // The size counts the whole buffer the slice shares, which is over the cap. + let slice = ints(0..100_000).slice(0, 10); + let input = vec![slice.clone(), slice.clone()]; + let output = run_in_pool(input.clone(), 1000, 1 << 30); + assert_eq!(row_counts(&output), [10, 10]); + assert!(Arc::ptr_eq(output[0].column(0), slice.column(0))); + } + + #[test] + fn a_schema_change_starts_a_new_group() { + let nullable = |values: std::ops::Range<i32>| { + let schema = Arc::new(Schema::new(vec![Field::new("k", DataType::Int32, true)])); + RecordBatch::try_new(schema, vec![Arc::new(Int32Array::from_iter_values(values))]) + .unwrap() + }; + let input = vec![ + ints(0..10), + ints(10..20), + nullable(20..30), + nullable(30..40), + ]; + let (output, _) = run(input.clone(), 1000, 0, MAX_GROUP_BYTES); + assert_eq!(row_counts(&output), [20, 20]); + assert_eq!(output[0].schema(), input[0].schema()); + assert_eq!(output[1].schema(), input[2].schema()); + } + + #[test] + fn batches_with_small_dictionary_keys_pass_through() { + use arrow::datatypes::Int8Type; + let batch = |start: usize| { + let mut dict = StringDictionaryBuilder::<Int8Type>::new(); + for i in start..start + 10 { + dict.append_value(format!("v{i}")); + } + RecordBatch::try_from_iter([("d", Arc::new(dict.finish()) as ArrayRef)]).unwrap() + }; + let input: Vec<_> = (0..20).map(|i| batch(i * 10)).collect(); + let (output, _) = run(input.clone(), 1000, 0, MAX_GROUP_BYTES); + assert_eq!(output, input); + } + + #[test] + fn batches_with_small_dictionary_keys_in_a_struct_pass_through() { + use arrow::datatypes::Int8Type; + let batch = |start: usize| { + let mut dict = StringDictionaryBuilder::<Int8Type>::new(); + for i in start..start + 10 { + dict.append_value(format!("v{i}")); + } + let dict: ArrayRef = Arc::new(dict.finish()); + let field = Field::new("d", dict.data_type().clone(), false); + let column = StructArray::new(Fields::from(vec![field]), vec![dict], None); + RecordBatch::try_from_iter([("s", Arc::new(column) as ArrayRef)]).unwrap() + }; + // Combined, the 200 distinct values would overflow the Int8 keys. + let input: Vec<_> = (0..20).map(|i| batch(i * 10)).collect(); + let (output, _) = run(input.clone(), 1000, 0, MAX_GROUP_BYTES); + assert_eq!(output, input); + } + + #[test] + fn batches_with_small_dictionary_keys_in_a_list_pass_through() { + use arrow::array::ListBuilder; + use arrow::datatypes::Int8Type; + let batch = |start: usize| { + let mut list = ListBuilder::new(StringDictionaryBuilder::<Int8Type>::new()); + for i in start..start + 10 { + list.values().append_value(format!("v{i}")); + list.append(true); + } + RecordBatch::try_from_iter([("l", Arc::new(list.finish()) as ArrayRef)]).unwrap() + }; + let input: Vec<_> = (0..20).map(|i| batch(i * 10)).collect(); + let (output, _) = run(input.clone(), 1000, 0, MAX_GROUP_BYTES); + assert_eq!(output, input); + } + + #[tokio::test] + async fn an_input_error_reaches_the_sort_and_releases_memory() { + use datafusion::physical_plan::streaming::{PartitionStream, StreamingTableExec}; + + #[derive(Debug)] + struct FailsAfterTwo(SchemaRef); + impl PartitionStream for FailsAfterTwo { + fn schema(&self) -> &SchemaRef { + &self.0 + } + fn execute(&self, _ctx: Arc<TaskContext>) -> SendableRecordBatchStream { + let items = vec![ + Ok(ints(0..10)), + Ok(ints(10..20)), + Err(DataFusionError::Execution("input failed".into())), + ]; + Box::pin(RecordBatchStreamAdapter::new( + Arc::clone(&self.0), + futures::stream::iter(items), + )) + } + } + + let schema = ints(0..1).schema(); + let source = Arc::new( + StreamingTableExec::try_new( + Arc::clone(&schema), + vec![Arc::new(FailsAfterTwo(Arc::clone(&schema)))], + None, + vec![], + false, + None, + ) + .unwrap(), + ); + let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 30)); + let runtime = RuntimeEnvBuilder::new() + .with_memory_pool(Arc::clone(&pool)) + .build_arc() + .unwrap(); + let ctx = SessionContext::new_with_config_rt(SessionConfig::new(), runtime); + let exec = SortInputCoalesceExec::new(source, 1000, 0); + let error = collect(exec.execute(0, ctx.task_ctx()).unwrap()) + .await + .unwrap_err(); + assert!(error.to_string().contains("input failed"), "{error}"); + assert_eq!(pool.reserved(), 0); + } + + #[tokio::test] + async fn dropping_the_stream_early_releases_the_reservation() { + let input = ten_row_batches(10); + let schema = input[0].schema(); + let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 30)); + let runtime = RuntimeEnvBuilder::new() + .with_memory_pool(Arc::clone(&pool)) + .build_arc() + .unwrap(); + let ctx = SessionContext::new_with_config_rt(SessionConfig::new(), runtime); + let source = MemorySourceConfig::try_new_exec(&[input], schema, None).unwrap(); + let exec = SortInputCoalesceExec::new(source, 40, 0); + let mut stream = exec.execute(0, ctx.task_ctx()).unwrap(); + // The first group is out and the second is being held. + assert_eq!(stream.try_next().await.unwrap().unwrap().num_rows(), 40); Review Comment: At this point `flush()` has freed the first group's reservation and the stream is suspended in `emit().await`, before it has pulled the next group. The pool is already at zero before `drop(stream)`. Could we have the input yield two short batches and then return `Poll::Pending`? Polling the coalescer once and asserting `pool.reserved() > 0` before dropping it would exercise cancellation with a live reservation. ########## spark/src/test/resources/sql-tests/operators/sort_coalesce_input.sql: ########## @@ -0,0 +1,124 @@ +-- Licensed to the Apache Software Foundation (ASF) under one +-- or more contributor license agreements. See the NOTICE file +-- distributed with this work for additional information +-- regarding copyright ownership. The ASF licenses this file +-- to you under the Apache License, Version 2.0 (the +-- "License"); you may not use this file except in compliance +-- with the License. You may obtain a copy of the License at +-- +-- http://www.apache.org/licenses/LICENSE-2.0 +-- +-- Unless required by applicable law or agreed to in writing, +-- software distributed under the License is distributed on an +-- "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +-- KIND, either express or implied. See the License for the +-- specific language governing permissions and limitations +-- under the License. + +-- CometSort combines small input batches before sorting them once the input passes the +-- in-place sort threshold. These queries give each sort task many tiny shuffle blocks and +-- check that the result matches Spark. + +-- Many small scan partitions, so each sort task reads small blocks from many map tasks. +-- Config: spark.sql.files.maxPartitionBytes=1024 +-- Config: spark.sql.files.openCostInBytes=1 +-- Config: spark.sql.shuffle.partitions=4 +-- Config: spark.sql.adaptive.coalescePartitions.enabled=false +-- A combined batch holds at most this many rows. +-- Config: spark.comet.batchSize=64 +-- Config: spark.comet.exec.respectDataFusionConfigs=true +-- 0 starts combining with the first batch and makes the sort merge instead of sorting in +-- place. The default, 1 MiB, lets the first part of each sort task's input pass through. +-- ConfigMatrix: spark.comet.datafusion.execution.sort_in_place_threshold_bytes=0,1048576 +-- Write year 1 and year 9999 values without the legacy calendar rebase. +-- Config: spark.sql.parquet.datetimeRebaseModeInWrite=CORRECTED +-- Config: spark.sql.parquet.int96RebaseModeInWrite=CORRECTED +-- Config: spark.comet.exec.sort.coalesceInput.enabled=true +-- The second run gives the sort a tiny memory pool and merge reservation so that it spills. +-- Config: spark.comet.datafusion.execution.sort_spill_reservation_bytes=65536 +-- ConfigMatrix: spark.comet.exec.memoryPool.fraction=1.0,0.002 +-- ConfigMatrix: spark.sql.session.timeZone=UTC,America/Los_Angeles Review Comment: Could we keep this file focused on Spark parity for nested values with one configuration and a smaller input? The three matrix dimensions rerun the 200-file setup and six queries eight times. The test durations on this commit sum to **5m58s on Spark 4.1** and **26m56s across the five profiles**. [Spark 4.1 timings](https://github.com/parthchandra/datafusion-comet/actions/runs/44620261571/job/135996331049#step:7:6412) · [Other profiles](https://github.com/apache/datafusion-comet/actions/runs/44621692095) The new `CometTaskMetricsSuite` test already verifies that the sort combines batches after the default gate, spills, and honors the toggle. Setting the threshold to zero here would let a handful of small files exercise concatenation from the first block. One time zone and one pool size should cover the nested copy. [Metrics test](https://github.com/apache/datafusion-comet/blob/d1819fd7fe1024fdc0fe7ae8ff7113e9c00e0587/spark/src/test/scala/org/apache/spark/sql/comet/CometTaskMetricsSuite.scala#L356-L381) -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
