|
| 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