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