Dandandan opened a new pull request, #24313: URL: https://github.com/apache/datafusion/pull/24313
## Which issue does this PR close? - Related to #15961. ## Rationale for this change Single column primitive `GROUP BY` hashes every row. When the keys are integers over a narrow range — ids, dates, small enums, dictionary codes — the group index can be found by indexing a vector with `value - min`, with no hashing at all. Micro-benchmark, `UInt64` keys, 8192 row batches, 3 paired runs alternated with the baseline to cancel machine drift (M-series laptop): | distinct groups | main | this PR | speedup | |---|---|---|---| | 128 | 282 µs | 203 µs | 1.39x | | 16k | 630 µs | 221 µs | 2.85x | | 131k | 2.30 ms | 0.48 ms | 4.80x | | 131k, ascending | 2.32 ms | 0.48 ms | 4.83x | | 1M | 21.0 ms | 4.51 ms | 4.66x | | 4M (over the slot cap) | 100 ms | 81 ms | 1.23x | | 131k, values 64 apart | 2.27 ms | 2.38 ms | 0.95x | The last row is the cost of watching the range while hashing, paid until the values are known to be too sparse. Memory is lower whenever the table is used: 4 bytes per slot against 16 bytes per hash table bucket. ## What changes are included in this PR? `GroupValuesPrimitive` gains a direct mapped store next to the existing hash table: - Values are hashed as before while their range is tracked. The direct mapped table is built once the groups fill at least 1/8 of the range they span, capped at 2M slots; tables under 64k slots are built whatever the fill rate. Deciding from the first batch alone would be wrong in both directions, as a batch of a dense column looks sparse simply because it holds a fraction of the values. - Values outside the range grow the table while it stays dense enough, otherwise the groups move back to the hash table for good. - Slot lookup is one wrapping subtraction on a bias-mapped `u64`, so values below the table are rejected by the same bounds check as values above it. - Group values stay in `values` in group index order, so `emit` is unchanged. - Only integer types are direct mapped; floats, decimals and intervals always hash. The hash path itself is untouched, so anything that does not qualify behaves exactly as before. Two spill tests were retuned: they assert that a fixed memory limit forces a spill, and the direct mapped table reports less memory than the hash table it replaces. ## Are these changes tested? Yes — 10 unit tests in `primitive.rs` covering direct mapped interning, growth upwards and downwards, rejection of wide ranges, sparse values staying hashed, a column that only looks sparse until enough values are seen, falling back mid-stream without renumbering groups, nulls, `EmitTo::First` re-indexing and `clear_shrink`. Each asserts that every input row maps to a group holding that row's value, so it holds whichever store was used. Full `datafusion-physical-plan` suite passes (1689 tests). ## Are there any user-facing changes? No API changes. Aggregations on integer keys report lower memory use, so a query near a memory limit may now succeed where it previously spilled. -- 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]
