Skip to content

Commit 924a4a7

Browse files
committed
feat(bench): add benchmark for fully ordered grouping implementation
1 parent 423df6f commit 924a4a7

2 files changed

Lines changed: 269 additions & 0 deletions

File tree

‎datafusion/physical-plan/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -169,3 +169,7 @@ name = "window_filter"
169169
[[bench]]
170170
harness = false
171171
name = "range_repartition"
172+
173+
[[bench]]
174+
harness = false
175+
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);

0 commit comments

Comments
 (0)