Repository navigation
Commit 8f279e1
perf(aggregate): reuse dictionary hashes and group mappings (apache#26826)
## Which issue does this PR close?
Closes apache#26812.
## Rationale for this change
Dictionary batches often share one values array while only their keys
change. Partial aggregation was rehashing the same dictionary values for
every batch.
## What changes are included in this PR?
The non-streaming group table now caches dictionary value hashes while
the values `Arc` is unchanged. A single dictionary group key can also
map known keys directly to group indices.
```text
Dictionary batch
|
v
single dictionary column + complete cached mapping?
| yes | no
v v
keys -> cached group IDs per-column hashing
| |
eligible dictionary fallback
| |
cached value hashes hash column
| |
scatter through keys -----+
|
v
hash/equality group lookup
```
New keys, changed or oversized dictionaries, and partial emission use
the normal fallback. Multi-column hashing keeps the same semantics as
`create_hashes`. The benchmark fixtures are split into apache#27246.
## What is the testing strategy for this PR?
Unit tests cover cached and uncached hash consistency, unseen keys,
changed dictionaries, null groups, partial emission, and forced
collisions.
Hosted cases from apache#27246 show [alternating
dictionary-only](apache#26826 (comment))
1.30× faster; [alternating dictionary +
Int32](apache#26826 (comment))
and [fresh
dictionaries](apache#26826 (comment))
flat; and [shared dictionary +
Int32](apache#26826 (comment))
1.14× faster at 32K values and 1.28× at 100K.
Exact-head hosted suites with RLE dictionary reads enabled on both
sides:
-
[TPC-H](apache#27249 (comment)):
796.01 → 799.79 ms (0.5% higher).
-
[TPC-DS](apache#27249 (comment)):
9.02 → 8.88 s (1.6% lower).
-
[ClickBench](apache#27249 (comment)):
38.26 → 38.16 s (0.3% lower).
## Are there any user-facing changes?
No.
---------
Co-authored-by: Jay Zhan <[email protected]>1 parent adffd19 commit 8f279e1
3 files changed
Lines changed: 509 additions & 42 deletions
File tree
- datafusion
- common/src
- physical-plan/src/aggregates/group_values/multi_group_by
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
670 | 670 | | |
671 | 671 | | |
672 | 672 | | |
| 673 | + | |
| 674 | + | |
| 675 | + | |
| 676 | + | |
| 677 | + | |
| 678 | + | |
| 679 | + | |
| 680 | + | |
| 681 | + | |
| 682 | + | |
| 683 | + | |
| 684 | + | |
| 685 | + | |
| 686 | + | |
| 687 | + | |
| 688 | + | |
| 689 | + | |
| 690 | + | |
| 691 | + | |
| 692 | + | |
| 693 | + | |
| 694 | + | |
| 695 | + | |
| 696 | + | |
| 697 | + | |
| 698 | + | |
| 699 | + | |
| 700 | + | |
| 701 | + | |
| 702 | + | |
| 703 | + | |
| 704 | + | |
| 705 | + | |
| 706 | + | |
| 707 | + | |
| 708 | + | |
| 709 | + | |
| 710 | + | |
| 711 | + | |
| 712 | + | |
| 713 | + | |
| 714 | + | |
| 715 | + | |
| 716 | + | |
| 717 | + | |
673 | 718 | | |
674 | 719 | | |
675 | 720 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
54 | 54 | | |
55 | 55 | | |
56 | 56 | | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
57 | 62 | | |
58 | 63 | | |
59 | 64 | | |
| |||
71 | 76 | | |
72 | 77 | | |
73 | 78 | | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
74 | 82 | | |
75 | 83 | | |
76 | 84 | | |
| |||
157 | 165 | | |
158 | 166 | | |
159 | 167 | | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
160 | 172 | | |
161 | 173 | | |
162 | 174 | | |
| |||
171 | 183 | | |
172 | 184 | | |
173 | 185 | | |
174 | | - | |
| 186 | + | |
| 187 | + | |
175 | 188 | | |
176 | 189 | | |
177 | 190 | | |
| |||
192 | 205 | | |
193 | 206 | | |
194 | 207 | | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
195 | 219 | | |
196 | 220 | | |
197 | 221 | | |
| |||
331 | 355 | | |
332 | 356 | | |
333 | 357 | | |
334 | | - | |
| 358 | + | |
335 | 359 | | |
336 | 360 | | |
337 | 361 | | |
338 | 362 | | |
339 | 363 | | |
340 | 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 | + | |
341 | 413 | | |
342 | 414 | | |
343 | 415 | | |
| |||
452 | 524 | | |
453 | 525 | | |
454 | 526 | | |
455 | | - | |
456 | | - | |
457 | | - | |
458 | | - | |
459 | | - | |
| 527 | + | |
460 | 528 | | |
461 | 529 | | |
462 | 530 | | |
| |||
472 | 540 | | |
473 | 541 | | |
474 | 542 | | |
475 | | - | |
476 | | - | |
477 | | - | |
478 | | - | |
479 | | - | |
| 543 | + | |
480 | 544 | | |
481 | 545 | | |
482 | 546 | | |
| |||
571 | 635 | | |
572 | 636 | | |
573 | 637 | | |
574 | | - | |
575 | | - | |
| 638 | + | |
| 639 | + | |
576 | 640 | | |
577 | 641 | | |
578 | 642 | | |
579 | | - | |
580 | 643 | | |
581 | | - | |
582 | | - | |
583 | | - | |
584 | | - | |
585 | | - | |
586 | | - | |
587 | 644 | | |
588 | 645 | | |
589 | 646 | | |
590 | 647 | | |
591 | 648 | | |
592 | | - | |
593 | | - | |
594 | | - | |
595 | | - | |
596 | 649 | | |
597 | 650 | | |
598 | 651 | | |
599 | 652 | | |
600 | 653 | | |
601 | | - | |
| 654 | + | |
| 655 | + | |
| 656 | + | |
| 657 | + | |
| 658 | + | |
| 659 | + | |
602 | 660 | | |
603 | 661 | | |
604 | 662 | | |
| |||
610 | 668 | | |
611 | 669 | | |
612 | 670 | | |
613 | | - | |
614 | | - | |
615 | | - | |
616 | | - | |
617 | | - | |
| 671 | + | |
| 672 | + | |
| 673 | + | |
| 674 | + | |
| 675 | + | |
| 676 | + | |
| 677 | + | |
618 | 678 | | |
619 | 679 | | |
620 | 680 | | |
| |||
0 commit comments