Skip to content

Commit 0a54cfb

Browse files
QinXi-aikosiew
authored andcommitted
perf(aggregate): specialize fully ordered group keys without hashing (apache#25150)
## Which issue does this PR close? Closes apache#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 apache#9662, particularly its single-column regression and requests for repeatable measurements and cross-batch tests. It is distinct from apache#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 <[email protected]> Co-authored-by: kosiew <[email protected]>
1 parent e7bf356 commit 0a54cfb

7 files changed

Lines changed: 779 additions & 2 deletions

File tree

‎datafusion-examples/examples/custom_data_source/file_stream_provider.rs‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,13 @@
2828
/// with DataFusion without needing to reload the entire dataset each time.
2929
///
3030
/// This example does not work on Windows.
31+
#[cfg_attr(
32+
target_os = "windows",
33+
expect(
34+
clippy::unused_async,
35+
reason = "keep the same async entry point on all platforms"
36+
)
37+
)]
3138
pub async fn file_stream_provider() -> datafusion::error::Result<()> {
3239
#[cfg(target_os = "windows")]
3340
{

‎datafusion/common/src/rounding.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -254,7 +254,7 @@ where
254254
}
255255
}
256256
_ => {}
257-
};
257+
}
258258
Ok(result)
259259
}
260260

‎datafusion/physical-plan/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -203,3 +203,7 @@ name = "range_repartition"
203203
[[bench]]
204204
harness = false
205205
name = "unnest"
206+
207+
[[bench]]
208+
harness = false
209+
name = "ordered_group_values"
Lines changed: 265 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,265 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Fully ordered grouping: compare the selected implementation with the
19+
//! existing streaming hash table on identical batches. Include emission and
20+
//! cross-batch continuation, not just lookup. Input preparation is untimed.
21+
//! The physical-plan benchmark includes aggregation but excludes SQL planning,
22+
//! sorting and I/O; the data already has a proven ordering.
23+
24+
use std::hint::black_box;
25+
use std::sync::Arc;
26+
use std::time::Duration;
27+
28+
use arrow::array::{ArrayRef, Int32Array, Int64Array, StringArray};
29+
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
30+
use arrow::record_batch::RecordBatch;
31+
use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
32+
use datafusion_execution::TaskContext;
33+
use datafusion_expr::EmitTo;
34+
use datafusion_functions_aggregate::sum::sum_udaf;
35+
use datafusion_physical_expr::aggregate::AggregateExprBuilder;
36+
use datafusion_physical_expr::expressions::col;
37+
use datafusion_physical_expr::{LexOrdering, PhysicalSortExpr};
38+
use datafusion_physical_plan::aggregates::group_values::multi_group_by::GroupValuesColumn;
39+
use datafusion_physical_plan::aggregates::group_values::{GroupValues, new_group_values};
40+
use datafusion_physical_plan::aggregates::order::GroupOrdering;
41+
use datafusion_physical_plan::aggregates::{
42+
AggregateExec, AggregateMode, PhysicalGroupBy,
43+
};
44+
use datafusion_physical_plan::test::TestMemoryExec;
45+
use datafusion_physical_plan::{ExecutionPlan, InputOrderMode, collect};
46+
use tokio::runtime::Runtime;
47+
48+
const ROWS: usize = 131_072;
49+
50+
fn inputs(
51+
run_length: usize,
52+
batch_size: usize,
53+
strings: bool,
54+
) -> (SchemaRef, Vec<Vec<ArrayRef>>) {
55+
let schema = Arc::new(Schema::new(vec![
56+
Field::new("a", DataType::Int32, false),
57+
Field::new(
58+
"b",
59+
if strings {
60+
DataType::Utf8
61+
} else {
62+
DataType::Int32
63+
},
64+
false,
65+
),
66+
]));
67+
let batches = (0..ROWS)
68+
.step_by(batch_size)
69+
.map(|start| {
70+
let end = (start + batch_size).min(ROWS);
71+
let first: ArrayRef = Arc::new(Int32Array::from_iter_values(
72+
(start..end).map(|row| ((row / run_length) / 4) as i32),
73+
));
74+
let second: ArrayRef = if strings {
75+
Arc::new(StringArray::from_iter_values((start..end).map(|row| {
76+
format!("key-{}-a-longer-than-inline-string", (row / run_length) % 4)
77+
})))
78+
} else {
79+
Arc::new(Int32Array::from_iter_values(
80+
(start..end).map(|row| ((row / run_length) % 4) as i32),
81+
))
82+
};
83+
vec![first, second]
84+
})
85+
.collect();
86+
(schema, batches)
87+
}
88+
89+
fn grouping(c: &mut Criterion) {
90+
let mut group = c.benchmark_group("fully_ordered_grouping");
91+
group.sample_size(10);
92+
group.warm_up_time(Duration::from_millis(250));
93+
group.measurement_time(Duration::from_secs(1));
94+
for strings in [false, true] {
95+
for batch_size in [127, 8192] {
96+
for run_length in [1, 8, 128, 8192] {
97+
let (schema, batches) = inputs(run_length, batch_size, strings);
98+
let case = format!(
99+
"{}_batch{batch_size}_run{run_length}",
100+
if strings { "string" } else { "int" }
101+
);
102+
let (hashed_bytes, selected_bytes) = check_case(&schema, &batches);
103+
eprintln!(
104+
"group_state_bytes {case} hashed={hashed_bytes} selected={selected_bytes}"
105+
);
106+
for selected in [false, true] {
107+
let name = if selected { "selected" } else { "hashed" };
108+
group.bench_function(BenchmarkId::new(name, &case), |b| {
109+
b.iter_batched_ref(
110+
|| {
111+
let values: Box<dyn GroupValues> = if selected {
112+
new_group_values(
113+
Arc::clone(&schema),
114+
&GroupOrdering::try_new(&InputOrderMode::Sorted)
115+
.unwrap(),
116+
)
117+
.unwrap()
118+
} else {
119+
Box::new(
120+
GroupValuesColumn::<true>::try_new(Arc::clone(
121+
&schema,
122+
))
123+
.unwrap(),
124+
)
125+
};
126+
(values, Vec::new())
127+
},
128+
|(values, ids)| {
129+
for batch in &batches {
130+
values.intern(batch, ids).unwrap();
131+
black_box(&*ids);
132+
let completed = values.len().saturating_sub(1);
133+
if completed > 0 {
134+
black_box(
135+
values
136+
.emit(EmitTo::First(completed))
137+
.unwrap(),
138+
);
139+
}
140+
}
141+
black_box(values.emit(EmitTo::All).unwrap());
142+
},
143+
criterion::BatchSize::LargeInput,
144+
);
145+
});
146+
}
147+
}
148+
}
149+
}
150+
group.finish();
151+
}
152+
153+
// Validate the benchmark input and report retained grouping-state memory.
154+
// These counters exclude the shared input and transient kernel allocations;
155+
// they are not process RSS measurements. Neither validation nor reporting is timed.
156+
fn check_case(schema: &SchemaRef, batches: &[Vec<ArrayRef>]) -> (usize, usize) {
157+
let mut hashed = GroupValuesColumn::<true>::try_new(Arc::clone(schema)).unwrap();
158+
let mut selected = new_group_values(
159+
Arc::clone(schema),
160+
&GroupOrdering::try_new(&InputOrderMode::Sorted).unwrap(),
161+
)
162+
.unwrap();
163+
let mut expected = Vec::new();
164+
let mut actual = Vec::new();
165+
let mut hashed_peak = 0;
166+
let mut selected_peak = 0;
167+
for batch in batches {
168+
hashed.intern(batch, &mut expected).unwrap();
169+
selected.intern(batch, &mut actual).unwrap();
170+
assert_eq!(actual, expected);
171+
hashed_peak = hashed_peak.max(hashed.size());
172+
selected_peak = selected_peak.max(selected.size());
173+
let completed = hashed.len().saturating_sub(1);
174+
assert_eq!(
175+
selected.emit(EmitTo::First(completed)).unwrap(),
176+
hashed.emit(EmitTo::First(completed)).unwrap()
177+
);
178+
}
179+
assert_eq!(
180+
selected.emit(EmitTo::All).unwrap(),
181+
hashed.emit(EmitTo::All).unwrap()
182+
);
183+
(hashed_peak, selected_peak)
184+
}
185+
186+
fn aggregate_plan(
187+
schema: &SchemaRef,
188+
keys: Vec<Vec<ArrayRef>>,
189+
) -> Arc<dyn ExecutionPlan> {
190+
let mut fields = schema.fields().to_vec();
191+
fields.push(Arc::new(Field::new("v", DataType::Int64, false)));
192+
let schema = Arc::new(Schema::new(fields));
193+
let batches = keys
194+
.into_iter()
195+
.map(|mut cols| {
196+
cols.push(Arc::new(Int64Array::from(vec![1; cols[0].len()])));
197+
RecordBatch::try_new(Arc::clone(&schema), cols).unwrap()
198+
})
199+
.collect::<Vec<_>>();
200+
let ordering = LexOrdering::new(vec![
201+
PhysicalSortExpr::new_default(col("a", &schema).unwrap()),
202+
PhysicalSortExpr::new_default(col("b", &schema).unwrap()),
203+
])
204+
.unwrap();
205+
let input =
206+
TestMemoryExec::try_new_exec(&[batches], Arc::clone(&schema), None).unwrap();
207+
let input = Arc::new(
208+
input
209+
.as_ref()
210+
.clone()
211+
.try_with_sort_information(vec![ordering])
212+
.unwrap(),
213+
);
214+
let expr = AggregateExprBuilder::new(sum_udaf(), vec![col("v", &schema).unwrap()])
215+
.schema(Arc::clone(&schema))
216+
.alias("sum_v")
217+
.build()
218+
.unwrap();
219+
let plan = AggregateExec::try_new(
220+
AggregateMode::Single,
221+
PhysicalGroupBy::new_single(vec![
222+
(col("a", &schema).unwrap(), "a".into()),
223+
(col("b", &schema).unwrap(), "b".into()),
224+
]),
225+
vec![Arc::new(expr)],
226+
vec![None],
227+
input,
228+
schema,
229+
)
230+
.unwrap();
231+
assert_eq!(plan.input_order_mode(), &InputOrderMode::Sorted);
232+
Arc::new(plan)
233+
}
234+
235+
fn aggregation(c: &mut Criterion) {
236+
let runtime = Runtime::new().unwrap();
237+
let mut group = c.benchmark_group("fully_ordered_aggregate_exec");
238+
group.sample_size(10);
239+
group.warm_up_time(Duration::from_millis(250));
240+
group.measurement_time(Duration::from_secs(1));
241+
for strings in [false, true] {
242+
for run_length in [1, 8, 128, 8192] {
243+
let (schema, keys) = inputs(run_length, 8192, strings);
244+
let plan = aggregate_plan(&schema, keys);
245+
let name =
246+
format!("{}_run{run_length}", if strings { "string" } else { "int" });
247+
group.bench_function(name, |b| {
248+
b.iter(|| {
249+
black_box(
250+
runtime
251+
.block_on(collect(
252+
Arc::clone(&plan),
253+
Arc::new(TaskContext::default()),
254+
))
255+
.unwrap(),
256+
)
257+
});
258+
});
259+
}
260+
}
261+
group.finish();
262+
}
263+
264+
criterion_group!(benches, grouping, aggregation);
265+
criterion_main!(benches);

‎datafusion/physical-plan/src/aggregates/group_values/mod.rs‎

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@ mod row;
2929
pub use row::GroupValuesRows;
3030
mod single_group_by;
3131
use datafusion_physical_expr::binary_map::OutputType;
32-
use multi_group_by::GroupValuesColumn;
32+
use multi_group_by::{GroupValuesColumn, GroupValuesOrdered};
3333

3434
pub(crate) use single_group_by::primitive::HashValue;
3535

@@ -139,6 +139,9 @@ pub trait GroupValues: Send {
139139
///
140140
/// [`GroupValues`] implementations choosing logic:
141141
///
142+
/// - Fully ordered multi-column keys with supported scalar types use adjacent
143+
/// comparisons and column builders, without a hash table.
144+
///
142145
/// - If group by single column, and type of this column has
143146
/// the specific [`GroupValues`] implementation, such implementation
144147
/// will be chosen.
@@ -155,6 +158,11 @@ pub fn new_group_values(
155158
schema: SchemaRef,
156159
group_ordering: &GroupOrdering,
157160
) -> Result<Box<dyn GroupValues>> {
161+
if matches!(group_ordering, GroupOrdering::Full(_))
162+
&& GroupValuesOrdered::supports_schema(&schema)
163+
{
164+
return Ok(Box::new(GroupValuesOrdered::try_new(schema)?));
165+
}
158166
if schema.fields.len() == 1 {
159167
let d = schema.fields[0].data_type();
160168

‎datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,8 @@ pub mod bytes_view;
2323
mod dictionary;
2424
mod fixed_size_binary;
2525
mod list;
26+
mod ordered;
27+
pub(super) use ordered::GroupValuesOrdered;
2628
pub mod primitive;
2729
pub mod row_backed;
2830

0 commit comments

Comments
 (0)