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]

Reply via email to