HairstonE opened a new pull request, #24420: URL: https://github.com/apache/datafusion/pull/24420
## Which issue does this PR close? - Closes #19938. (Maybe Part Of) This implements the dynamic switching approach for `GROUP BY` on single integer columns, rather than sizing from known column statistics. Improving on this with known stats will be a follow up. ## Rationale for this change Grouped aggregation interns every row's key into a dense group id. For a single integer column, the current path hashes and probes a hash table once per row. When the keys fall in a small range, you don't need any of that. Direct array indexing skips the hash and the probe entirely. We already do something similar with hash joins (#19411). This brings the same idea to grouping. It sizes the window from the first batch, falls back to the hash grouper when the range is wide or sparse, and spills out-of-window keys to an overflow map. Because of the fallback it never performs worse than the current main branch. The main win is memory and interning cost. Dense integer groups use a third to a half the memory of the hash grouper, and isolated interning runs ~2.5–2.7× faster. There's no whole-query speedup. The operator numbers below show the gain when grouping is the bottleneck. The broad benchmarks show we didn't regress anywhere. Benchmarks run on a Mac mini. **Isolated intern — criterion, 8192-row steady-state batch, Int64:** | card | hash | flat | speedup | |---|---|---|---| | 100 | 14.91 µs | 5.62 µs | **2.65×** | | 1000 | 15.99 µs | 6.00 µs | **2.67×** | | 10000 | 19.18 µs | 7.63 µs | **2.51×** | **End-to-end `aggregation_time` — 50M rows `(value*7)%card`, min of 5:** | card | hash | flat | speedup | |---|---|---|---| | 100 | 131.61 ms | 92.33 ms | 1.43× | | 1000 | 142.65 ms | 94.39 ms | 1.51× | | 10000 | 176.12 ms | 103.51 ms | 1.70× | **Memory — `GroupValues::size()` bytes, steady state:** | shape | groups | hash | flat | flat/hash | |---|---|---|---|---| | dense-100 | 100 | 4 608 | 1 424 | **0.31×** | | dense-1000 | 1000 | 36 864 | 12 192 | **0.33×** | | dense-10000 | 10000 | 360 448 | 171 072 | **0.47×** | | sparse / sparse-inwin / wide | — | = | = | **1.00×** (fallback parity) | No regression(or at least within the range of noise) on the broad benchmark wall time measurements: h2o 10/10 (q4 engages this PR's path and is -1.5%), ClickBench 43/43 (+1.5%), external_aggr 8/8 spilling under 16 MB–512 MB pools (+0.4%). ## What changes are included in this PR? The core is a new flat grouper for single integer columns. There are three modes: Uninit, Flat, and Fallback. It starts in Uninit. The first batch sets the window. Takes the min and max of the keys and turns that into an offset and a range. If the range is small enough, it enters Flat mode and interns by direct array indexing. Keys that land outside the window go to an overflow map instead. If the first batch shows the range is too wide or too sparse, it enters Fallback and hands everything to the existing hash grouper. In Flat mode the window grows on demand, but only when it's helping. An occupied-slot counter checks the growth. Dense windows expand. Sparse windows overflow instead of allocating unused slots. On a partial emit, the grouper releases the dead window and the overflow it no longer needs. ## Are these changes tested? Yes. Sixteen unit tests in `flat::tests` cover dense-id assignment, nulls, overflow above and below the window, wide and sparse fallback, `emit(First)` renumbering across slots/overflow/null, equivalence with the hash implementation, density-gated growth, and dead-window plus overflow release on partial emit. For sqllogictest, the full `aggregate*.slt` suite is unchanged, `aggregate_memory_spill.slt` and the memory-constrained spilling fuzz test are green, and `explain_analyze.slt` carries updated `AggregateExec` metrics. I also used cargo-mutants to check that the tests are robust. ## Are there any user-facing changes? No. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
