You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/10/01 11:13:45 UTC

(datafusion) branch main updated: perf(aggregate): specialize fully ordered group keys without hashing (#25150)

This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git


The following commit(s) were added to refs/heads/main by this push:
     new 5635e5c196 perf(aggregate): specialize fully ordered group keys without hashing (#25150)
5635e5c196 is described below

commit 5635e5c1965fcb8b52201ebdfc6b3748f25ff139
Author: QinXi <36...@qq.com>
AuthorDate: Thu Oct 1 11:03:04 2026 +0000

    perf(aggregate): specialize fully ordered group keys without hashing (#25150)
    
    ## Which issue does this PR close?
    
    Closes #14574 for supported fully ordered multi-column keys.
    Single-column specializations and additional key types remain on their
    existing paths.
    
    ## Rationale for this change
    
    When input is already sorted by all grouping expressions, DataFusion can
    emit completed groups early, but its multi-column group-key mapping
    still hashes each row and maintains a hash table. This adds CPU and
    retained state even though equal keys must be consecutive.
    
    ## What changes are included in this PR?
    
    - Add an internal columnar `GroupValuesOrdered` selected only for
    `GroupOrdering::Full` and supported multi-column schemas. Arrow's
    partition kernel identifies adjacent runs; existing column builders
    retain representatives and compare the boundary key across batches.
    Dense IDs, partial emission, preserving selections, and reset behavior
    follow the existing contracts.
    - Support boolean, integer, string, and binary keys, including their
    large/view variants. Keep single-column, float, nested, dictionary,
    partially ordered, and unordered inputs on established paths.
    - Add differential correctness tests and a reproducible benchmark
    covering two key schemas, batch sizes 127/8192, and run lengths
    1/8/128/8192. Include both grouping with emission and complete ordered
    `AggregateExec` execution.
    - Include two small Windows lint compatibility fixes needed to run the
    repository's full Clippy command: remove a redundant semicolon in
    rounding and add a Windows-only `unused_async` expectation to the
    unsupported FIFO example's uniform async entry point.
    
    This builds on the problem and review in #9662, particularly its
    single-column regression and requests for repeatable measurements and
    cross-batch tests. It is distinct from #23986's consecutive-key cache
    for clustered input, which retains the general hash path. This PR
    optimizes existing streaming aggregation; it does not introduce
    streaming aggregation or change whole-query asymptotic complexity.
    
    ## What is the testing strategy for this PR?
    
    `ordered_keys_match_hash_grouping_across_batches_and_emits` compares
    group IDs and emitted/preserved keys with `GroupValuesColumn<true>` for
    15 key types, ascending/descending runs, NULLs, long strings, six batch
    sizes, and four emission limits. It also exercises empty batches and
    reset/reuse. A schema gate test covers excluded types.
    
    `ordered_single_and_partial_final_match_unordered_execution` compares
    actual `AggregateExec` results with unordered execution for Single and
    Partial→Final with FILTER, using four batch sizes and asserted sorted
    execution.
    
    Validation after the September 26 conflict-resolution rebase onto `main`
    at `6a792c6` (Windows, Rust 1.98.1): `cargo fmt --all -- --check`, `git
    diff --check`, `cargo test --offline --locked -p
    datafusion-physical-plan --lib` (**2,323 passed, 0 failed**), focused
    physical-plan library Clippy with `-D warnings`, and `cargo check
    --offline --locked -p datafusion-physical-plan --bench
    ordered_group_values` passed. Full `cargo clippy --all-targets
    --all-features -- -D warnings` was attempted but stopped while linking
    `protobuf-src`'s `protoc` on this Windows machine (`LNK2019`/`LNK1120`);
    it is not a passing full lint result. Fresh Linux CI remains to be seen
    for the rebased head.
    
    Earlier local validation on Windows, before this rebase:
    
    - Rust 1.97.0: full `cargo clippy --all-targets --all-features -- -D
    warnings` and formatting checks pass.
    - Rust 1.98.1, CI profile, extended workspace features: 11,333 tests
    passed across recorded runs, including all 2,050 physical-plan tests,
    120 fuzz tests, and the two 5M-row SMJ low-memory runners. Eight tests
    are ignored, with no pending test programs. Seven baseline-reproduced
    failures remain, so this is not a full-workspace pass.
    - Seven failures reproduce with the same assertion differences on
    unmodified baseline `423df6f4`: two datasource path tests, four
    floating-point interval/statistics tests, and the xtask CI command
    snapshot. These remain recorded failures.
    - Windows library backtrace capture was disabled for the extended run
    because it made error-path tests exceptionally slow. The common crate's
    650 tests, including backtrace behavior, pass separately with capture
    enabled. A CRLF checkout of the Q15 fixture was normalized to its
    original LF contents so the existing multi-statement skip works as
    intended; no test assertion was changed.
    - An external process interruption required resuming missing tests from
    Cargo's compiled artifact list. Completed suite summaries and unique
    individual test results were retained; this does not represent one
    successful full-workspace Cargo invocation. Linux CI passed on the
    pre-rebase head `a62b640`.
    
    The following benchmark measurements predate the September 26 rebase and
    have not been rerun against `6a792c6`. They were collected on an Intel
    Core Ultra 7 258V / Windows, Rust 1.98.1, `release-nonlto`, pinned to
    logical CPU 0, with no concurrent task builds/tests. Baseline and
    candidate were built from separate source directories with identical
    lockfiles. The run order was baseline, candidate, candidate, baseline;
    each case used 250 ms warmup, 10 samples, and at least 1 second of
    measurement.
    
    The complete ordered `AggregateExec` benchmark uses 8,192-row batches.
    Speedup ranges below are `min(baseline) / max(candidate)` through
    `max(baseline) / min(candidate)` across the two repetitions; they are
    not confidence intervals for the ratio.
    
    | Keys / rows per group | Baseline ms (two runs) | Candidate ms (two
    runs) | Speedup range |
    |---|---:|---:|---:|
    | int / 1 | 6.086, 5.269 | 1.609, 1.857 | 2.84–3.78x |
    | int / 8 | 2.434, 2.296 | 0.480, 0.609 | 3.77–5.07x |
    | int / 128 | 2.112, 1.949 | 0.549, 0.598 | 3.26–3.85x |
    | int / 8192 | 2.162, 2.059 | 0.545, 0.553 | 3.73–3.97x |
    | string / 1 | 9.616, 9.665 | 4.793, 5.521 | 1.74–2.02x |
    | string / 8 | 4.333, 4.422 | 1.697, 1.660 | 2.55–2.66x |
    | string / 128 | 3.723, 3.464 | 1.747, 1.638 | 1.98–2.27x |
    | string / 8192 | 3.907, 3.745 | 1.613, 1.607 | 2.32–2.43x |
    
    All 16 selected grouping microbenchmark cases also have faster point
    estimates in both repetitions; the weakest cross-repetition ratio is
    approximately 1.06x for long strings in 127-row batches. Small
    differences on one machine should not be generalized across platforms.
    At batch size 8192 / run length 1, peak retained group state drops from
    425,792 to 196,608 bytes for integer keys and from 950,080 to 720,896
    bytes for integer/long-string keys.
    
    The benchmark pre-generates 131,072 rows and excludes input generation,
    sorting, SQL planning, and I/O. The grouping benchmark includes
    partial/final emission; the execution benchmark includes SUM and output
    collection on already ordered input. `group_state_bytes` reports peak
    retained `GroupValues::size()`, excluding shared inputs and transient
    kernel allocations; it is not process RSS.
    
    ## Are there any user-facing changes?
    
    Eligible fully ordered multi-column aggregations use less grouping state
    and avoid hashing. No SQL syntax, result semantics, configuration, or
    public API changes.
    
    This contribution is AI-assisted.
    
    ---------
    
    Co-authored-by: hushen <19...@users.noreply.github.com>
    Co-authored-by: kosiew <ko...@gmail.com>
---
 .../custom_data_source/file_stream_provider.rs     |   7 +
 datafusion/common/src/rounding.rs                  |   2 +-
 datafusion/physical-plan/Cargo.toml                |   4 +
 .../physical-plan/benches/ordered_group_values.rs  | 265 +++++++++++
 .../src/aggregates/group_values/mod.rs             |  10 +-
 .../aggregates/group_values/multi_group_by/mod.rs  |   2 +
 .../group_values/multi_group_by/ordered.rs         | 491 +++++++++++++++++++++
 7 files changed, 779 insertions(+), 2 deletions(-)

diff --git a/datafusion-examples/examples/custom_data_source/file_stream_provider.rs b/datafusion-examples/examples/custom_data_source/file_stream_provider.rs
index 5b43072d43..49be4469c3 100644
--- a/datafusion-examples/examples/custom_data_source/file_stream_provider.rs
+++ b/datafusion-examples/examples/custom_data_source/file_stream_provider.rs
@@ -28,6 +28,13 @@
 /// with DataFusion without needing to reload the entire dataset each time.
 ///
 /// This example does not work on Windows.
+#[cfg_attr(
+    target_os = "windows",
+    expect(
+        clippy::unused_async,
+        reason = "keep the same async entry point on all platforms"
+    )
+)]
 pub async fn file_stream_provider() -> datafusion::error::Result<()> {
     #[cfg(target_os = "windows")]
     {
diff --git a/datafusion/common/src/rounding.rs b/datafusion/common/src/rounding.rs
index 1796143d7c..b3b514e863 100644
--- a/datafusion/common/src/rounding.rs
+++ b/datafusion/common/src/rounding.rs
@@ -254,7 +254,7 @@ where
             }
         }
         _ => {}
-    };
+    }
     Ok(result)
 }
 
diff --git a/datafusion/physical-plan/Cargo.toml b/datafusion/physical-plan/Cargo.toml
index 73b20f422b..82a2215581 100644
--- a/datafusion/physical-plan/Cargo.toml
+++ b/datafusion/physical-plan/Cargo.toml
@@ -203,3 +203,7 @@ name = "range_repartition"
 [[bench]]
 harness = false
 name = "unnest"
+
+[[bench]]
+harness = false
+name = "ordered_group_values"
diff --git a/datafusion/physical-plan/benches/ordered_group_values.rs b/datafusion/physical-plan/benches/ordered_group_values.rs
new file mode 100644
index 0000000000..ae0e44a859
--- /dev/null
+++ b/datafusion/physical-plan/benches/ordered_group_values.rs
@@ -0,0 +1,265 @@
+// 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.
+
+//! Fully ordered grouping: compare the selected implementation with the
+//! existing streaming hash table on identical batches. Include emission and
+//! cross-batch continuation, not just lookup. Input preparation is untimed.
+//! The physical-plan benchmark includes aggregation but excludes SQL planning,
+//! sorting and I/O; the data already has a proven ordering.
+
+use std::hint::black_box;
+use std::sync::Arc;
+use std::time::Duration;
+
+use arrow::array::{ArrayRef, Int32Array, Int64Array, StringArray};
+use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
+use arrow::record_batch::RecordBatch;
+use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
+use datafusion_execution::TaskContext;
+use datafusion_expr::EmitTo;
+use datafusion_functions_aggregate::sum::sum_udaf;
+use datafusion_physical_expr::aggregate::AggregateExprBuilder;
+use datafusion_physical_expr::expressions::col;
+use datafusion_physical_expr::{LexOrdering, PhysicalSortExpr};
+use datafusion_physical_plan::aggregates::group_values::multi_group_by::GroupValuesColumn;
+use datafusion_physical_plan::aggregates::group_values::{GroupValues, new_group_values};
+use datafusion_physical_plan::aggregates::order::GroupOrdering;
+use datafusion_physical_plan::aggregates::{
+    AggregateExec, AggregateMode, PhysicalGroupBy,
+};
+use datafusion_physical_plan::test::TestMemoryExec;
+use datafusion_physical_plan::{ExecutionPlan, InputOrderMode, collect};
+use tokio::runtime::Runtime;
+
+const ROWS: usize = 131_072;
+
+fn inputs(
+    run_length: usize,
+    batch_size: usize,
+    strings: bool,
+) -> (SchemaRef, Vec<Vec<ArrayRef>>) {
+    let schema = Arc::new(Schema::new(vec![
+        Field::new("a", DataType::Int32, false),
+        Field::new(
+            "b",
+            if strings {
+                DataType::Utf8
+            } else {
+                DataType::Int32
+            },
+            false,
+        ),
+    ]));
+    let batches = (0..ROWS)
+        .step_by(batch_size)
+        .map(|start| {
+            let end = (start + batch_size).min(ROWS);
+            let first: ArrayRef = Arc::new(Int32Array::from_iter_values(
+                (start..end).map(|row| ((row / run_length) / 4) as i32),
+            ));
+            let second: ArrayRef = if strings {
+                Arc::new(StringArray::from_iter_values((start..end).map(|row| {
+                    format!("key-{}-a-longer-than-inline-string", (row / run_length) % 4)
+                })))
+            } else {
+                Arc::new(Int32Array::from_iter_values(
+                    (start..end).map(|row| ((row / run_length) % 4) as i32),
+                ))
+            };
+            vec![first, second]
+        })
+        .collect();
+    (schema, batches)
+}
+
+fn grouping(c: &mut Criterion) {
+    let mut group = c.benchmark_group("fully_ordered_grouping");
+    group.sample_size(10);
+    group.warm_up_time(Duration::from_millis(250));
+    group.measurement_time(Duration::from_secs(1));
+    for strings in [false, true] {
+        for batch_size in [127, 8192] {
+            for run_length in [1, 8, 128, 8192] {
+                let (schema, batches) = inputs(run_length, batch_size, strings);
+                let case = format!(
+                    "{}_batch{batch_size}_run{run_length}",
+                    if strings { "string" } else { "int" }
+                );
+                let (hashed_bytes, selected_bytes) = check_case(&schema, &batches);
+                eprintln!(
+                    "group_state_bytes {case} hashed={hashed_bytes} selected={selected_bytes}"
+                );
+                for selected in [false, true] {
+                    let name = if selected { "selected" } else { "hashed" };
+                    group.bench_function(BenchmarkId::new(name, &case), |b| {
+                        b.iter_batched_ref(
+                            || {
+                                let values: Box<dyn GroupValues> = if selected {
+                                    new_group_values(
+                                        Arc::clone(&schema),
+                                        &GroupOrdering::try_new(&InputOrderMode::Sorted)
+                                            .unwrap(),
+                                    )
+                                    .unwrap()
+                                } else {
+                                    Box::new(
+                                        GroupValuesColumn::<true>::try_new(Arc::clone(
+                                            &schema,
+                                        ))
+                                        .unwrap(),
+                                    )
+                                };
+                                (values, Vec::new())
+                            },
+                            |(values, ids)| {
+                                for batch in &batches {
+                                    values.intern(batch, ids).unwrap();
+                                    black_box(&*ids);
+                                    let completed = values.len().saturating_sub(1);
+                                    if completed > 0 {
+                                        black_box(
+                                            values
+                                                .emit(EmitTo::First(completed))
+                                                .unwrap(),
+                                        );
+                                    }
+                                }
+                                black_box(values.emit(EmitTo::All).unwrap());
+                            },
+                            criterion::BatchSize::LargeInput,
+                        );
+                    });
+                }
+            }
+        }
+    }
+    group.finish();
+}
+
+// Validate the benchmark input and report retained grouping-state memory.
+// These counters exclude the shared input and transient kernel allocations;
+// they are not process RSS measurements. Neither validation nor reporting is timed.
+fn check_case(schema: &SchemaRef, batches: &[Vec<ArrayRef>]) -> (usize, usize) {
+    let mut hashed = GroupValuesColumn::<true>::try_new(Arc::clone(schema)).unwrap();
+    let mut selected = new_group_values(
+        Arc::clone(schema),
+        &GroupOrdering::try_new(&InputOrderMode::Sorted).unwrap(),
+    )
+    .unwrap();
+    let mut expected = Vec::new();
+    let mut actual = Vec::new();
+    let mut hashed_peak = 0;
+    let mut selected_peak = 0;
+    for batch in batches {
+        hashed.intern(batch, &mut expected).unwrap();
+        selected.intern(batch, &mut actual).unwrap();
+        assert_eq!(actual, expected);
+        hashed_peak = hashed_peak.max(hashed.size());
+        selected_peak = selected_peak.max(selected.size());
+        let completed = hashed.len().saturating_sub(1);
+        assert_eq!(
+            selected.emit(EmitTo::First(completed)).unwrap(),
+            hashed.emit(EmitTo::First(completed)).unwrap()
+        );
+    }
+    assert_eq!(
+        selected.emit(EmitTo::All).unwrap(),
+        hashed.emit(EmitTo::All).unwrap()
+    );
+    (hashed_peak, selected_peak)
+}
+
+fn aggregate_plan(
+    schema: &SchemaRef,
+    keys: Vec<Vec<ArrayRef>>,
+) -> Arc<dyn ExecutionPlan> {
+    let mut fields = schema.fields().to_vec();
+    fields.push(Arc::new(Field::new("v", DataType::Int64, false)));
+    let schema = Arc::new(Schema::new(fields));
+    let batches = keys
+        .into_iter()
+        .map(|mut cols| {
+            cols.push(Arc::new(Int64Array::from(vec![1; cols[0].len()])));
+            RecordBatch::try_new(Arc::clone(&schema), cols).unwrap()
+        })
+        .collect::<Vec<_>>();
+    let ordering = LexOrdering::new(vec![
+        PhysicalSortExpr::new_default(col("a", &schema).unwrap()),
+        PhysicalSortExpr::new_default(col("b", &schema).unwrap()),
+    ])
+    .unwrap();
+    let input =
+        TestMemoryExec::try_new_exec(&[batches], Arc::clone(&schema), None).unwrap();
+    let input = Arc::new(
+        input
+            .as_ref()
+            .clone()
+            .try_with_sort_information(vec![ordering])
+            .unwrap(),
+    );
+    let expr = AggregateExprBuilder::new(sum_udaf(), vec![col("v", &schema).unwrap()])
+        .schema(Arc::clone(&schema))
+        .alias("sum_v")
+        .build()
+        .unwrap();
+    let plan = AggregateExec::try_new(
+        AggregateMode::Single,
+        PhysicalGroupBy::new_single(vec![
+            (col("a", &schema).unwrap(), "a".into()),
+            (col("b", &schema).unwrap(), "b".into()),
+        ]),
+        vec![Arc::new(expr)],
+        vec![None],
+        input,
+        schema,
+    )
+    .unwrap();
+    assert_eq!(plan.input_order_mode(), &InputOrderMode::Sorted);
+    Arc::new(plan)
+}
+
+fn aggregation(c: &mut Criterion) {
+    let runtime = Runtime::new().unwrap();
+    let mut group = c.benchmark_group("fully_ordered_aggregate_exec");
+    group.sample_size(10);
+    group.warm_up_time(Duration::from_millis(250));
+    group.measurement_time(Duration::from_secs(1));
+    for strings in [false, true] {
+        for run_length in [1, 8, 128, 8192] {
+            let (schema, keys) = inputs(run_length, 8192, strings);
+            let plan = aggregate_plan(&schema, keys);
+            let name =
+                format!("{}_run{run_length}", if strings { "string" } else { "int" });
+            group.bench_function(name, |b| {
+                b.iter(|| {
+                    black_box(
+                        runtime
+                            .block_on(collect(
+                                Arc::clone(&plan),
+                                Arc::new(TaskContext::default()),
+                            ))
+                            .unwrap(),
+                    )
+                });
+            });
+        }
+    }
+    group.finish();
+}
+
+criterion_group!(benches, grouping, aggregation);
+criterion_main!(benches);
diff --git a/datafusion/physical-plan/src/aggregates/group_values/mod.rs b/datafusion/physical-plan/src/aggregates/group_values/mod.rs
index e03db633e6..32eabfe8dc 100644
--- a/datafusion/physical-plan/src/aggregates/group_values/mod.rs
+++ b/datafusion/physical-plan/src/aggregates/group_values/mod.rs
@@ -29,7 +29,7 @@ mod row;
 pub use row::GroupValuesRows;
 mod single_group_by;
 use datafusion_physical_expr::binary_map::OutputType;
-use multi_group_by::GroupValuesColumn;
+use multi_group_by::{GroupValuesColumn, GroupValuesOrdered};
 
 pub(crate) use single_group_by::primitive::HashValue;
 
@@ -139,6 +139,9 @@ pub trait GroupValues: Send {
 ///
 /// [`GroupValues`] implementations choosing logic:
 ///
+///   - Fully ordered multi-column keys with supported scalar types use adjacent
+///     comparisons and column builders, without a hash table.
+///
 ///   - If group by single column, and type of this column has
 ///     the specific [`GroupValues`] implementation, such implementation
 ///     will be chosen.
@@ -155,6 +158,11 @@ pub fn new_group_values(
     schema: SchemaRef,
     group_ordering: &GroupOrdering,
 ) -> Result<Box<dyn GroupValues>> {
+    if matches!(group_ordering, GroupOrdering::Full(_))
+        && GroupValuesOrdered::supports_schema(&schema)
+    {
+        return Ok(Box::new(GroupValuesOrdered::try_new(schema)?));
+    }
     if schema.fields.len() == 1 {
         let d = schema.fields[0].data_type();
 
diff --git a/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs b/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
index 07b825e95a..9497d521e6 100644
--- a/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
+++ b/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
@@ -23,6 +23,8 @@ pub mod bytes_view;
 mod dictionary;
 mod fixed_size_binary;
 mod list;
+mod ordered;
+pub(super) use ordered::GroupValuesOrdered;
 pub mod primitive;
 pub mod row_backed;
 
diff --git a/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/ordered.rs b/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/ordered.rs
new file mode 100644
index 0000000000..9e34ac7aea
--- /dev/null
+++ b/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/ordered.rs
@@ -0,0 +1,491 @@
+// 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.
+
+use std::mem;
+
+use arrow::array::ArrayRef;
+use arrow::datatypes::{DataType, Schema, SchemaRef};
+use arrow_ord::partition::partition;
+use datafusion_common::{Result, not_impl_err};
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_expr::{EmitTo, GroupSelection};
+
+use super::{GroupColumn, GroupValuesColumn};
+use crate::aggregates::group_values::GroupValues;
+
+/// Columnar group keys for input fully ordered by all grouping expressions.
+///
+/// Equal keys must be contiguous across input batches. Within a batch Arrow's
+/// partition kernel finds those runs. Only the first run can continue the last
+/// buffered group; compare it with the stored columns, without retaining the
+/// input batch. New group representatives use the existing column builders.
+///
+/// This removes hashing and hash-table storage, but does not change the dense
+/// group-id or emission contracts. In particular, `First(n)` shifts the remaining
+/// keys and their ids together. Partially ordered inputs must use a hash table.
+pub(crate) struct GroupValuesOrdered {
+    schema: SchemaRef,
+    columns: Vec<Box<dyn GroupColumn>>,
+    new_groups: Vec<usize>,
+}
+
+impl GroupValuesOrdered {
+    /// Types for which adjacent Arrow equality agrees with GROUP BY equality.
+    /// Keep single-column specializations and floats/nested/encoded keys on the
+    /// established path until their semantics and performance are validated.
+    pub(crate) fn supports_schema(schema: &Schema) -> bool {
+        schema.fields().len() > 1
+            && schema.fields().iter().all(|field| {
+                matches!(
+                    field.data_type(),
+                    DataType::Boolean
+                        | DataType::Int8
+                        | DataType::Int16
+                        | DataType::Int32
+                        | DataType::Int64
+                        | DataType::UInt8
+                        | DataType::UInt16
+                        | DataType::UInt32
+                        | DataType::UInt64
+                        | DataType::Utf8
+                        | DataType::LargeUtf8
+                        | DataType::Utf8View
+                        | DataType::Binary
+                        | DataType::LargeBinary
+                        | DataType::BinaryView
+                )
+            })
+    }
+
+    pub(crate) fn try_new(schema: SchemaRef) -> Result<Self> {
+        if !Self::supports_schema(&schema) {
+            return not_impl_err!(
+                "Unsupported schema for fully ordered group values: {schema}"
+            );
+        }
+        let columns = GroupValuesColumn::<true>::build_group_columns(&schema)?;
+        Ok(Self {
+            schema,
+            columns,
+            new_groups: Vec::new(),
+        })
+    }
+}
+
+impl GroupValues for GroupValuesOrdered {
+    fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+        groups.clear();
+        let ranges = partition(cols)?.ranges();
+        if ranges.is_empty() {
+            return Ok(());
+        }
+
+        let old_len = self.len();
+        let continues = old_len > 0
+            && self
+                .columns
+                .iter()
+                .zip(cols)
+                .all(|(stored, input)| stored.equal_to(old_len - 1, input, 0));
+
+        self.new_groups.clear();
+        self.new_groups.extend(
+            ranges
+                .iter()
+                .skip(usize::from(continues))
+                .map(|range| range.start),
+        );
+        for (stored, input) in self.columns.iter_mut().zip(cols) {
+            stored.vectorized_append(input, &self.new_groups)?;
+        }
+
+        let first_group = old_len - usize::from(continues);
+        for (index, range) in ranges.iter().enumerate() {
+            groups.resize(range.end, first_group + index);
+        }
+        Ok(())
+    }
+
+    fn size(&self) -> usize {
+        self.columns
+            .iter()
+            .map(|column| column.size())
+            .sum::<usize>()
+            + self.new_groups.allocated_size()
+    }
+
+    fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    fn len(&self) -> usize {
+        self.columns[0].len()
+    }
+
+    fn emit(&mut self, emit_to: EmitTo) -> Result<Vec<ArrayRef>> {
+        Ok(match emit_to {
+            EmitTo::All => {
+                let fresh = GroupValuesColumn::<true>::build_group_columns(&self.schema)?;
+                mem::replace(&mut self.columns, fresh)
+                    .into_iter()
+                    .map(|column| column.build())
+                    .collect()
+            }
+            EmitTo::First(n) => self
+                .columns
+                .iter_mut()
+                .map(|column| column.take_n(n))
+                .collect(),
+        })
+    }
+
+    fn values_preserving(
+        &mut self,
+        selection: GroupSelection<'_>,
+    ) -> Result<Vec<ArrayRef>> {
+        selection.validate_num_groups(self.len())?;
+        self.columns
+            .iter()
+            .map(|column| column.values_preserving(selection))
+            .collect()
+    }
+
+    fn supports_values_preserving(&self) -> bool {
+        true
+    }
+
+    fn clear_shrink(&mut self, num_rows: usize) {
+        self.columns = GroupValuesColumn::<true>::build_group_columns(&self.schema)
+            .expect("schema validated by GroupValuesOrdered::try_new");
+        self.new_groups.clear();
+        self.new_groups.shrink_to(num_rows);
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use std::sync::Arc;
+
+    use arrow::array::UInt32Array;
+    use arrow::array::{Array, BooleanArray, Int32Array, Int64Array, StringArray};
+    use arrow::compute::{cast, take};
+    use arrow::datatypes::Field;
+    use datafusion_expr::GroupSelection;
+
+    use super::*;
+
+    // Compare with the existing hash implementation, changing actual input
+    // boundaries and removing completed groups between batches. This checks the
+    // semantic contract rather than duplicating the adjacent-run algorithm.
+    #[test]
+    fn ordered_keys_match_hash_grouping_across_batches_and_emits() -> Result<()> {
+        for key_type in [
+            DataType::Boolean,
+            DataType::Int8,
+            DataType::Int16,
+            DataType::Int32,
+            DataType::Int64,
+            DataType::UInt8,
+            DataType::UInt16,
+            DataType::UInt32,
+            DataType::UInt64,
+            DataType::Utf8,
+            DataType::LargeUtf8,
+            DataType::Utf8View,
+            DataType::Binary,
+            DataType::LargeBinary,
+            DataType::BinaryView,
+        ] {
+            let rows = 1025;
+            let first: ArrayRef = Arc::new(Int32Array::from_iter((0..rows).map(|row| {
+                let group = row / 7;
+                (group >= 4).then_some(group / 4)
+            })));
+            let second: ArrayRef = match key_type {
+                DataType::Boolean => {
+                    Arc::new(BooleanArray::from_iter((0..rows).map(|row| {
+                        let key = (row / 7) % 4;
+                        (key != 0).then_some(key >= 2)
+                    })))
+                }
+                DataType::Utf8
+                | DataType::LargeUtf8
+                | DataType::Utf8View
+                | DataType::Binary
+                | DataType::LargeBinary
+                | DataType::BinaryView => {
+                    let strings = StringArray::from_iter((0..rows).map(|row| {
+                        let key = (row / 7) % 4;
+                        (key != 0).then(|| {
+                            format!(
+                                "key-{key}-{}",
+                                "x".repeat(if key == 3 { 128 } else { 0 })
+                            )
+                        })
+                    }));
+                    cast(&strings, &key_type)?
+                }
+                _ => {
+                    let values = Int32Array::from_iter((0..rows).map(|row| {
+                        let key = (row / 7) % 4;
+                        (key != 0).then_some(key)
+                    }));
+                    cast(&values, &key_type)?
+                }
+            };
+            for descending in [false, true] {
+                let mut input = vec![Arc::clone(&first), Arc::clone(&second)];
+                if descending {
+                    let reverse = UInt32Array::from_iter_values((0..rows as u32).rev());
+                    input = input
+                        .iter()
+                        .map(|array| take(array, &reverse, None))
+                        .collect::<std::result::Result<_, _>>()?;
+                }
+                let schema = Arc::new(Schema::new(vec![
+                    Field::new("a", DataType::Int32, true),
+                    Field::new("b", key_type.clone(), true),
+                ]));
+                for batch_size in [1, 2, 7, 8, 63, 1024] {
+                    for emit_limit in [0, 1, 17, usize::MAX] {
+                        let mut ordered =
+                            GroupValuesOrdered::try_new(Arc::clone(&schema))?;
+                        let mut hashed =
+                            GroupValuesColumn::<true>::try_new(Arc::clone(&schema))?;
+                        let mut actual = Vec::new();
+                        let mut expected = Vec::new();
+                        for offset in (0..rows as usize).step_by(batch_size) {
+                            let length = batch_size.min(rows as usize - offset);
+                            let batch = input
+                                .iter()
+                                .map(|array| array.slice(offset, length))
+                                .collect::<Vec<_>>();
+                            ordered.intern(&batch, &mut actual)?;
+                            hashed.intern(&batch, &mut expected)?;
+                            assert_eq!(
+                                actual, expected,
+                                "{key_type:?}, batch={batch_size}, offset={offset}, descending={descending}"
+                            );
+                            assert_eq!(ordered.len(), hashed.len());
+                            let selection = GroupSelection::all(ordered.len());
+                            assert_eq!(
+                                ordered.values_preserving(selection)?,
+                                hashed.values_preserving(selection)?
+                            );
+                            // A zero-row batch must neither forget the boundary
+                            // key nor leave stale group ids in the output buffer.
+                            let empty = batch
+                                .iter()
+                                .map(|array| array.slice(0, 0))
+                                .collect::<Vec<_>>();
+                            ordered.intern(&empty, &mut actual)?;
+                            assert!(actual.is_empty());
+                            let emit = emit_limit.min(ordered.len().saturating_sub(1));
+                            assert_eq!(
+                                ordered.emit(EmitTo::First(emit))?,
+                                hashed.emit(EmitTo::First(emit))?
+                            );
+                        }
+                        assert_eq!(ordered.emit(EmitTo::All)?, hashed.emit(EmitTo::All)?);
+                        assert!(ordered.is_empty());
+                        // All and clear_shrink reset the cross-batch state.
+                        ordered.clear_shrink(0);
+                        hashed.clear_shrink(0);
+                        ordered.intern(&input, &mut actual)?;
+                        hashed.intern(&input, &mut expected)?;
+                        assert_eq!(actual, expected);
+                        assert_eq!(ordered.emit(EmitTo::All)?, hashed.emit(EmitTo::All)?);
+                    }
+                }
+            }
+        }
+        Ok(())
+    }
+
+    #[test]
+    fn ordered_schema_gate_keeps_unvalidated_types_on_existing_paths() {
+        for data_type in [
+            DataType::Float32,
+            DataType::Float64,
+            DataType::Null,
+            DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8)),
+            DataType::List(Arc::new(Field::new("item", DataType::Int32, true))),
+        ] {
+            let schema = Schema::new(vec![
+                Field::new("a", DataType::Int32, false),
+                Field::new("b", data_type, true),
+            ]);
+            assert!(!GroupValuesOrdered::supports_schema(&schema));
+        }
+        assert!(!GroupValuesOrdered::supports_schema(&Schema::new(vec![
+            Field::new("a", DataType::Int32, false)
+        ])));
+    }
+
+    #[tokio::test]
+    async fn ordered_single_and_partial_final_match_unordered_execution() -> Result<()> {
+        use crate::aggregates::{AggregateExec, AggregateMode, PhysicalGroupBy};
+        use crate::test::TestMemoryExec;
+        use crate::{ExecutionPlan, InputOrderMode, collect};
+        use arrow::compute::{SortOptions, take_record_batch};
+        use arrow::record_batch::RecordBatch;
+        use arrow::row::{RowConverter, SortField};
+        use datafusion_execution::TaskContext;
+        use datafusion_functions_aggregate::sum::sum_udaf;
+        use datafusion_physical_expr::aggregate::AggregateExprBuilder;
+        use datafusion_physical_expr::expressions::col;
+        use datafusion_physical_expr::{LexOrdering, PhysicalSortExpr};
+
+        let schema = Arc::new(Schema::new(vec![
+            Field::new("a", DataType::Int32, true),
+            Field::new("b", DataType::Utf8, false),
+            Field::new("v", DataType::Int64, false),
+            Field::new("include", DataType::Boolean, false),
+        ]));
+        let source = RecordBatch::try_new(
+            Arc::clone(&schema),
+            vec![
+                Arc::new(Int32Array::from_iter(
+                    (0..257).map(|row| (row >= 28).then_some(row / 28)),
+                )),
+                Arc::new(StringArray::from_iter_values(
+                    (0..257).map(|row| format!("key-{}", (row / 7) % 4)),
+                )),
+                Arc::new(Int64Array::from_iter_values(0..257)),
+                Arc::new(BooleanArray::from_iter(
+                    (0..257).map(|row| Some(row % 3 != 0)),
+                )),
+            ],
+        )?;
+        let aggregate = Arc::new(
+            AggregateExprBuilder::new(sum_udaf(), vec![col("v", &schema)?])
+                .schema(Arc::clone(&schema))
+                .alias("sum_v")
+                .build()?,
+        );
+
+        for descending in [false, true] {
+            let source = if descending {
+                let reverse = UInt32Array::from_iter_values((0..257).rev());
+                take_record_batch(&source, &reverse)?
+            } else {
+                source.clone()
+            };
+            for input_batch_size in [1, 7, 31, 128] {
+                let batches = (0..257)
+                    .step_by(input_batch_size)
+                    .map(|offset| {
+                        source.slice(offset, input_batch_size.min(257 - offset))
+                    })
+                    .collect::<Vec<_>>();
+                for two_stage in [false, true] {
+                    let mut results = Vec::new();
+                    for sorted in [false, true] {
+                        let input = TestMemoryExec::try_new_exec(
+                            std::slice::from_ref(&batches),
+                            Arc::clone(&schema),
+                            None,
+                        )?;
+                        let input: Arc<dyn ExecutionPlan> = if sorted {
+                            let options = if descending {
+                                SortOptions::default().desc().nulls_last()
+                            } else {
+                                SortOptions::default()
+                            };
+                            let ordering = LexOrdering::new(vec![
+                                PhysicalSortExpr::new(col("a", &schema)?, options),
+                                PhysicalSortExpr::new(col("b", &schema)?, options),
+                            ])
+                            .unwrap();
+                            Arc::new(
+                                input
+                                    .as_ref()
+                                    .clone()
+                                    .try_with_sort_information(vec![ordering])?,
+                            )
+                        } else {
+                            input
+                        };
+                        let group_by = PhysicalGroupBy::new_single(vec![
+                            (col("a", &schema)?, "a".into()),
+                            (col("b", &schema)?, "b".into()),
+                        ]);
+                        let plan = AggregateExec::try_new(
+                            if two_stage {
+                                AggregateMode::Partial
+                            } else {
+                                AggregateMode::Single
+                            },
+                            group_by.clone(),
+                            vec![Arc::clone(&aggregate)],
+                            vec![Some(col("include", &schema)?)],
+                            input,
+                            Arc::clone(&schema),
+                        )?;
+                        if sorted {
+                            assert_eq!(plan.input_order_mode(), &InputOrderMode::Sorted);
+                        }
+                        let plan: Arc<dyn ExecutionPlan> = if two_stage {
+                            let plan = AggregateExec::try_new(
+                                AggregateMode::Final,
+                                group_by,
+                                vec![Arc::clone(&aggregate)],
+                                vec![None],
+                                Arc::new(plan),
+                                Arc::clone(&schema),
+                            )?;
+                            if sorted {
+                                assert_eq!(
+                                    plan.input_order_mode(),
+                                    &InputOrderMode::Sorted
+                                );
+                            }
+                            Arc::new(plan)
+                        } else {
+                            Arc::new(plan)
+                        };
+                        let converter = RowConverter::new(
+                            plan.schema()
+                                .fields()
+                                .iter()
+                                .map(|field| SortField::new(field.data_type().clone()))
+                                .collect(),
+                        )?;
+                        let output =
+                            collect(plan, Arc::new(TaskContext::default())).await?;
+                        let mut rows = Vec::new();
+                        for batch in output {
+                            rows.extend(
+                                converter
+                                    .convert_columns(batch.columns())?
+                                    .iter()
+                                    .map(|row| row.as_ref().to_vec()),
+                            );
+                        }
+                        rows.sort();
+                        results.push(rows);
+                    }
+                    assert_eq!(
+                        results[0], results[1],
+                        "batch_size={input_batch_size}, two_stage={two_stage}, descending={descending}"
+                    );
+                }
+            }
+        }
+        Ok(())
+    }
+}


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org