Skip to content

Commit 6c1727f

Browse files
perf: extend fully ordered aggregation to more scalar types (#26370)
## Which issue does this PR close? Closes #26369. Follow-up to #25150. ## Rationale for this change Fully ordered multi-column `GROUP BY` still hashes temporal, decimal, and fixed-size binary keys. These types can use the existing adjacent-run grouping path because Arrow's adjacent equality agrees with the grouping builders. In our production usecases, we are especially interested in #26369's optimization extending to `Timestamp`s (timeseries data) and `FixedSizeBinary(16)` (for UUIDs). ## What changes are included in this PR? - **Only production code change is 12 new types** added to the `match` under `supports_schema`: the rest are tests and benches. - Enable timestamps with all units and timezone metadata, dates, valid time units, durations, intervals, Decimal32/64/128/256, and every valid fixed-size binary width. - Preserve type metadata and the existing selection of single-column specializations. - Add a `fully_ordered` group to the existing SQL aggregation Criterion benchmark, with integer/string controls, timestamp run-length variants, and a timestamp `SUM(v)` case. The first two commits contain only benchmarks, followed by the type expansion and regression tests, including the UUID coverage. ## What is the testing strategy for this PR? Differential tests compare ordered and hash grouping across nulls, units/timezones, decimal metadata, sliced batches, and group emission. Dedicated tests cover zero-width binary and 16-byte binary keys that share their first 15 bytes, including cross-batch continuation and keys that differ only in the last byte. SQL regression tests cover single-stage and partial/final aggregation, mixed sort directions, null ordering, and aggregate filters. The benchmarks check input types, row and group counts, and fully clustered aggregation without sorting or repartitioning in the measured query. The timestamp `SUM(v)` case also checks every group's sum before timing. <details> <summary>SQL benchmark results</summary> [Latest benchmark bot report](#26370 (comment)), comparing the benchmark-only baseline `dc6a10cf3c8` with `a398f8768ca`. Both refs contain the same 17 benchmark cases. The table shows rounded speedups from the report. The controls are roughly unchanged; the small differences may be benchmark noise. Values below 1× mean slower. | Second grouping key / query | Rows per group | Approx. speedup | | --- | ---: | ---: | | Int64 (control) | 31 | ~0.95× | | Utf8View (control) | 31 | ~0.99× | | Timestamp (ns) | 31 | ~7.0× | | Timestamp (µs, UTC) | 31 | ~6.9× | | Date32 | 31 | ~7.5× | | Time32 (ms) | 31 | ~7.5× | | Time64 (ns) | 31 | ~7.0× | | Duration (ns) | 31 | ~7.0× | | Interval (day/time) | 31 | ~6.4× | | Interval (month/day/ns) | 31 | ~5.3× | | Decimal128(30, 4) | 31 | ~6.1× | | Decimal256(60, 4) | 31 | ~5.2× | | FixedSizeBinary(16) | 31 | ~4.6× | | FixedSizeBinary(7) | 31 | ~4.4× | | Timestamp (ns), singleton groups | 1 | ~2.9× | | Timestamp (ns), long groups | 512 | ~7.7× | | Timestamp (ns), `SUM(v)` | 31 | ~4.0× | The 16 key-only cases use the same two-key deduplication query: ```sql SELECT k1, k2 FROM ordered_input GROUP BY k1, k2 ``` The additional timestamp case includes accumulator work: ```sql SELECT k1, k2, SUM(v) FROM ordered_input GROUP BY k1, k2 ``` Here `v` is the nonconstant source row number. The timestamp `SUM(v)` case improved from approximately 43.9 ms to 11.0 ms (~4.0×). - **Input:** about 2.1 million rows. `k1` is an Int32 prefix that advances every 32 groups; nullable `k2` cycles through 32 values, including one null, using the type listed above. Both keys vary. - **Group sizes:** normally 31 rows per key pair, so runs cross the 8,192-row batch boundaries. The additional timestamp cases use one or 512 rows per group to vary cardinality. - **Before timing:** generate the data, sort by both keys, and materialize it into one in-memory partition with its ordering declared to the planner. - **Measured work:** SQL planning, query execution, and collection of all results. The key-only cases focus on grouping the keys; the timestamp `SUM(v)` case also updates an accumulator. - **Setup checks:** verify input type, row count, and output group count; require fully clustered aggregation and fail if the measured plan adds sorting or repartitioning. The `SUM(v)` case verifies every group's result, including null timestamp keys and the final short group, before timing. </details> ## Are there any user-facing changes? Already-sorted multi-column aggregations can use lower-overhead key storage for these types. Query results stay the same. Developed with AI assistance.
1 parent 16c0755 commit 6c1727f

3 files changed

Lines changed: 770 additions & 107 deletions

File tree

‎datafusion/core/benches/aggregate_query_sql.rs‎

Lines changed: 234 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,10 +17,17 @@
1717

1818
mod data_utils;
1919

20+
use arrow::array::{Array, AsArray};
21+
use arrow::datatypes::{
22+
DataType, Int32Type, Int64Type, IntervalUnit, TimeUnit, TimestampNanosecondType,
23+
};
2024
use criterion::{Criterion, criterion_group, criterion_main};
2125
use data_utils::create_table_provider;
26+
use datafusion::datasource::MemTable;
2227
use datafusion::error::Result;
23-
use datafusion::execution::context::SessionContext;
28+
use datafusion::execution::context::{SessionConfig, SessionContext};
29+
use datafusion::physical_plan::{collect, displayable};
30+
use datafusion_expr::col;
2431
use parking_lot::Mutex;
2532
use std::hint::black_box;
2633
use std::sync::Arc;
@@ -330,5 +337,230 @@ fn criterion_benchmark(c: &mut Criterion) {
330337
});
331338
}
332339

333-
criterion_group!(benches, criterion_benchmark);
340+
/// Measure the multi-column fully ordered grouping path, with data generation
341+
/// and sorting outside timing. Both keys vary, and the nullable second key
342+
/// changes type while the shape of the input stays the same.
343+
fn fully_ordered(c: &mut Criterion) {
344+
use DataType::*;
345+
use IntervalUnit::{DayTime, MonthDayNano};
346+
use TimeUnit::{Microsecond, Millisecond, Nanosecond};
347+
348+
let cases = [
349+
("int64", "signed_key", Int64, 31),
350+
(
351+
"utf8_view",
352+
"arrow_cast(lpad(CAST(key_value AS VARCHAR), 4, '0'), 'Utf8View')",
353+
Utf8View,
354+
31,
355+
),
356+
(
357+
"timestamp_ns",
358+
"arrow_cast(signed_key, 'Timestamp(Nanosecond)')",
359+
Timestamp(Nanosecond, None),
360+
31,
361+
),
362+
(
363+
"timestamp_us_utc",
364+
"arrow_cast(signed_key, 'Timestamp(Microsecond, Some(\"UTC\"))')",
365+
Timestamp(Microsecond, Some("UTC".into())),
366+
31,
367+
),
368+
(
369+
"date32",
370+
"arrow_cast(CAST(signed_key AS INTEGER), 'Date32')",
371+
Date32,
372+
31,
373+
),
374+
(
375+
"time32_ms",
376+
"arrow_cast(CAST(key_value AS INTEGER), 'Time32(Millisecond)')",
377+
Time32(Millisecond),
378+
31,
379+
),
380+
(
381+
"time64_ns",
382+
"arrow_cast(key_value, 'Time64(Nanosecond)')",
383+
Time64(Nanosecond),
384+
31,
385+
),
386+
(
387+
"duration_ns",
388+
"arrow_cast(signed_key, 'Duration(Nanosecond)')",
389+
Duration(Nanosecond),
390+
31,
391+
),
392+
(
393+
"interval_day_time",
394+
"arrow_cast(concat(CAST(signed_key AS VARCHAR), ' days'), 'Interval(DayTime)')",
395+
Interval(DayTime),
396+
31,
397+
),
398+
(
399+
"interval_month_day_nano",
400+
"arrow_cast(arrow_cast(signed_key, 'Duration(Nanosecond)'), 'Interval(MonthDayNano)')",
401+
Interval(MonthDayNano),
402+
31,
403+
),
404+
(
405+
"decimal128",
406+
"arrow_cast(concat('123456789012345678901', lpad(CAST(key_value AS VARCHAR), 4, '0'), '.1250'), 'Decimal128(30, 4)')",
407+
Decimal128(30, 4),
408+
31,
409+
),
410+
(
411+
"decimal256",
412+
"arrow_cast(concat('123456789012345678901234567890123456789012345678901', lpad(CAST(key_value AS VARCHAR), 4, '0'), '.1250'), 'Decimal256(60, 4)')",
413+
Decimal256(60, 4),
414+
31,
415+
),
416+
(
417+
"fixed_binary16",
418+
"arrow_cast(decode(lpad(to_hex(key_value), 32, '0'), 'hex'), 'FixedSizeBinary(16)')",
419+
FixedSizeBinary(16),
420+
31,
421+
),
422+
(
423+
"fixed_binary7",
424+
"arrow_cast(decode(lpad(to_hex(key_value), 14, '0'), 'hex'), 'FixedSizeBinary(7)')",
425+
FixedSizeBinary(7),
426+
31,
427+
),
428+
(
429+
"timestamp_ns_singleton",
430+
"arrow_cast(signed_key, 'Timestamp(Nanosecond)')",
431+
Timestamp(Nanosecond, None),
432+
1,
433+
),
434+
(
435+
"timestamp_ns_long_runs",
436+
"arrow_cast(signed_key, 'Timestamp(Nanosecond)')",
437+
Timestamp(Nanosecond, None),
438+
512,
439+
),
440+
];
441+
442+
let rt = Runtime::new().unwrap();
443+
let mut group = c.benchmark_group("fully_ordered");
444+
for (name, key_expr, key_type, run_length) in cases {
445+
let ctx = rt
446+
.block_on(fully_ordered_context(
447+
key_expr, &key_type, run_length, false,
448+
))
449+
.unwrap();
450+
group.bench_function(name, |b| {
451+
b.iter(|| query(ctx.clone(), &rt, FULLY_ORDERED_QUERY))
452+
});
453+
}
454+
// Add accumulator work for one representative timestamp case without
455+
// multiplying every key type and run length by the aggregate expression.
456+
let ctx = rt
457+
.block_on(fully_ordered_context(
458+
"arrow_cast(signed_key, 'Timestamp(Nanosecond)')",
459+
&Timestamp(Nanosecond, None),
460+
31,
461+
true,
462+
))
463+
.unwrap();
464+
group.bench_function("timestamp_ns_sum", |b| {
465+
b.iter(|| query(ctx.clone(), &rt, FULLY_ORDERED_SUM_QUERY))
466+
});
467+
group.finish();
468+
}
469+
470+
const FULLY_ORDERED_QUERY: &str = "SELECT k1, k2 FROM ordered_input GROUP BY k1, k2";
471+
const FULLY_ORDERED_SUM_QUERY: &str =
472+
"SELECT k1, k2, SUM(v) FROM ordered_input GROUP BY k1, k2";
473+
474+
async fn fully_ordered_context(
475+
key_expr: &str,
476+
key_type: &DataType,
477+
run_length: usize,
478+
with_sum: bool,
479+
) -> Result<Arc<Mutex<SessionContext>>> {
480+
const ROWS: usize = 2_097_152;
481+
// Use source row numbers as nonconstant values for the aggregate case.
482+
let (value_projection, input_value, sql) = if with_sum {
483+
(", v", ", value AS v", FULLY_ORDERED_SUM_QUERY)
484+
} else {
485+
("", "", FULLY_ORDERED_QUERY)
486+
};
487+
let config = SessionConfig::new()
488+
.with_target_partitions(1)
489+
.with_batch_size(8192)
490+
.with_prefer_existing_sort(true);
491+
let ctx = SessionContext::new_with_config(config);
492+
// Runs of 31 cross batch boundaries; singleton and long-run cases vary
493+
// cardinality without multiplying every type by every input shape.
494+
let input = ctx
495+
.sql(&format!(
496+
"SELECT CAST(group_id / 32 AS INTEGER) AS k1, \
497+
CASE WHEN key_value = 0 THEN NULL ELSE {key_expr} END AS k2{value_projection} \
498+
FROM (SELECT value / {run_length} AS group_id, \
499+
value / {run_length} % 32 AS key_value, \
500+
value / {run_length} % 32 - 16 AS signed_key{input_value} \
501+
FROM range({ROWS})) \
502+
ORDER BY k1 ASC NULLS FIRST, k2 ASC NULLS FIRST"
503+
))
504+
.await?
505+
.create_physical_plan()
506+
.await?;
507+
let schema = input.schema();
508+
assert_eq!(schema.field(1).data_type(), key_type);
509+
let batches = collect(input, ctx.task_ctx()).await?;
510+
assert_eq!(
511+
batches.iter().map(|batch| batch.num_rows()).sum::<usize>(),
512+
ROWS
513+
);
514+
// The setup query sorts both keys before materialization. Retain that
515+
// known ordering explicitly when registering its results as a table.
516+
let table = MemTable::try_new(schema, vec![batches])?.with_sort_order(vec![vec![
517+
col("k1").sort(true, true),
518+
col("k2").sort(true, true),
519+
]]);
520+
ctx.register_table("ordered_input", Arc::new(table))?;
521+
522+
let plan = ctx.sql(sql).await?.create_physical_plan().await?;
523+
let description = displayable(plan.as_ref()).indent(true).to_string();
524+
assert!(
525+
description.contains("group_clustering_mode=Full"),
526+
"{description}"
527+
);
528+
// Input is already sorted in one partition. Fail if the planner adds
529+
// sorting or repartitioning to the measured query.
530+
assert!(!description.contains("SortExec"), "{description}");
531+
assert!(!description.contains("RepartitionExec"), "{description}");
532+
let result = collect(plan, ctx.task_ctx()).await?;
533+
assert_eq!(
534+
result.iter().map(|batch| batch.num_rows()).sum::<usize>(),
535+
ROWS.div_ceil(run_length)
536+
);
537+
if with_sum {
538+
let rows = i64::try_from(ROWS).unwrap();
539+
let run_length = i64::try_from(run_length).unwrap();
540+
for batch in &result {
541+
let k1 = batch.column(0).as_primitive::<Int32Type>();
542+
let k2 = batch.column(1).as_primitive::<TimestampNanosecondType>();
543+
let sums = batch.column(2).as_primitive::<Int64Type>();
544+
assert_eq!(sums.null_count(), 0);
545+
for row in 0..batch.num_rows() {
546+
// Each input group covers a contiguous range of source row
547+
// numbers. Recover it from the keys, independently of output
548+
// order, and check the arithmetic-series sum, including the
549+
// final short group and groups with a NULL timestamp key.
550+
let key_offset = if k2.is_null(row) {
551+
0
552+
} else {
553+
k2.value(row) + 16
554+
};
555+
let group_id = i64::from(k1.value(row)) * 32 + key_offset;
556+
let start = group_id * run_length;
557+
let end = (start + run_length).min(rows);
558+
assert_eq!(sums.value(row), (start + end - 1) * (end - start) / 2);
559+
}
560+
}
561+
}
562+
Ok(Arc::new(Mutex::new(ctx)))
563+
}
564+
565+
criterion_group!(benches, criterion_benchmark, fully_ordered);
334566
criterion_main!(benches);

0 commit comments

Comments
 (0)