Repository navigation
Commit 6c1727f
authored
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
- physical-plan/src/aggregates/group_values/multi_group_by
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
17 | 17 | | |
18 | 18 | | |
19 | 19 | | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
20 | 24 | | |
21 | 25 | | |
| 26 | + | |
22 | 27 | | |
23 | | - | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
24 | 31 | | |
25 | 32 | | |
26 | 33 | | |
| |||
330 | 337 | | |
331 | 338 | | |
332 | 339 | | |
333 | | - | |
| 340 | + | |
| 341 | + | |
| 342 | + | |
| 343 | + | |
| 344 | + | |
| 345 | + | |
| 346 | + | |
| 347 | + | |
| 348 | + | |
| 349 | + | |
| 350 | + | |
| 351 | + | |
| 352 | + | |
| 353 | + | |
| 354 | + | |
| 355 | + | |
| 356 | + | |
| 357 | + | |
| 358 | + | |
| 359 | + | |
| 360 | + | |
| 361 | + | |
| 362 | + | |
| 363 | + | |
| 364 | + | |
| 365 | + | |
| 366 | + | |
| 367 | + | |
| 368 | + | |
| 369 | + | |
| 370 | + | |
| 371 | + | |
| 372 | + | |
| 373 | + | |
| 374 | + | |
| 375 | + | |
| 376 | + | |
| 377 | + | |
| 378 | + | |
| 379 | + | |
| 380 | + | |
| 381 | + | |
| 382 | + | |
| 383 | + | |
| 384 | + | |
| 385 | + | |
| 386 | + | |
| 387 | + | |
| 388 | + | |
| 389 | + | |
| 390 | + | |
| 391 | + | |
| 392 | + | |
| 393 | + | |
| 394 | + | |
| 395 | + | |
| 396 | + | |
| 397 | + | |
| 398 | + | |
| 399 | + | |
| 400 | + | |
| 401 | + | |
| 402 | + | |
| 403 | + | |
| 404 | + | |
| 405 | + | |
| 406 | + | |
| 407 | + | |
| 408 | + | |
| 409 | + | |
| 410 | + | |
| 411 | + | |
| 412 | + | |
| 413 | + | |
| 414 | + | |
| 415 | + | |
| 416 | + | |
| 417 | + | |
| 418 | + | |
| 419 | + | |
| 420 | + | |
| 421 | + | |
| 422 | + | |
| 423 | + | |
| 424 | + | |
| 425 | + | |
| 426 | + | |
| 427 | + | |
| 428 | + | |
| 429 | + | |
| 430 | + | |
| 431 | + | |
| 432 | + | |
| 433 | + | |
| 434 | + | |
| 435 | + | |
| 436 | + | |
| 437 | + | |
| 438 | + | |
| 439 | + | |
| 440 | + | |
| 441 | + | |
| 442 | + | |
| 443 | + | |
| 444 | + | |
| 445 | + | |
| 446 | + | |
| 447 | + | |
| 448 | + | |
| 449 | + | |
| 450 | + | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
| 454 | + | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
| 460 | + | |
| 461 | + | |
| 462 | + | |
| 463 | + | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
| 470 | + | |
| 471 | + | |
| 472 | + | |
| 473 | + | |
| 474 | + | |
| 475 | + | |
| 476 | + | |
| 477 | + | |
| 478 | + | |
| 479 | + | |
| 480 | + | |
| 481 | + | |
| 482 | + | |
| 483 | + | |
| 484 | + | |
| 485 | + | |
| 486 | + | |
| 487 | + | |
| 488 | + | |
| 489 | + | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
| 505 | + | |
| 506 | + | |
| 507 | + | |
| 508 | + | |
| 509 | + | |
| 510 | + | |
| 511 | + | |
| 512 | + | |
| 513 | + | |
| 514 | + | |
| 515 | + | |
| 516 | + | |
| 517 | + | |
| 518 | + | |
| 519 | + | |
| 520 | + | |
| 521 | + | |
| 522 | + | |
| 523 | + | |
| 524 | + | |
| 525 | + | |
| 526 | + | |
| 527 | + | |
| 528 | + | |
| 529 | + | |
| 530 | + | |
| 531 | + | |
| 532 | + | |
| 533 | + | |
| 534 | + | |
| 535 | + | |
| 536 | + | |
| 537 | + | |
| 538 | + | |
| 539 | + | |
| 540 | + | |
| 541 | + | |
| 542 | + | |
| 543 | + | |
| 544 | + | |
| 545 | + | |
| 546 | + | |
| 547 | + | |
| 548 | + | |
| 549 | + | |
| 550 | + | |
| 551 | + | |
| 552 | + | |
| 553 | + | |
| 554 | + | |
| 555 | + | |
| 556 | + | |
| 557 | + | |
| 558 | + | |
| 559 | + | |
| 560 | + | |
| 561 | + | |
| 562 | + | |
| 563 | + | |
| 564 | + | |
| 565 | + | |
334 | 566 | | |
0 commit comments