jayzhan211 opened a new pull request, #25247: URL: https://github.com/apache/datafusion/pull/25247
## Which issue does this PR close? - Part of #24704 (first of three small PRs toward blocked group state; the plan and measurements are in the discussion there). ## Rationale for this change `GroupValuesPrimitive` stores `(group_index, hash)` in its hash table and compares a probe against `values[group_index]`. At high cardinality that is two dependent cache misses per row: the bucket, then the value it points at. Keeping the key in the entry instead — `(group_index, key)` — lets the probe compare against the bucket it already loaded and never touch `values`. The hash is recomputed on resize; for primitive keys that is cheaper than the wider entry a stored hash would need (#15961 stored the hash to make rehashing cheap while the compare still went through `values`; with the key in the entry the compare is free and the entry stays 16 bytes for 8-byte keys). Standalone probe loop, random `i64` keys, ns/row including the table build (M4 Pro): | groups | today `(g, hash)` + `values[g]` | `(g, key)` | |---|---|---| | 100k | 4.1 | **3.3 (0.80x)** | | 1M | 14.3 | **11.0 (0.77x)** | | 10M | 16.2 | **11.5 (0.71x)** | End to end (`datafusion-cli`, TPC-H `lineitem`, 12 partitions, interleaved rounds, median): `GROUP BY l_partkey` SF1 (200k groups) **0.93x**, SF10 (2M groups) **0.90x**; `GROUP BY l_orderkey` (clustered, cache-hot probes) 0.98–1.03x. TPC-H SF10 total 0.98x (with the two follow-up PRs applied). ## What changes are included in this PR? - `GroupValuesPrimitive::map` is `HashTable<(usize, T::Native)>`; the probe closure compares the stored key, the rehash closure recomputes its hash. `size()` accounts the new entry width. No behavior change. Trade-off for natives wider than 8 bytes (`i128`/Decimal128, `i256`, intervals): the entry grows from 16 to 32 bytes, so the hash index doubles — measured +13% process RSS on `GROUP BY <Decimal128>` with 10M groups, at unchanged time (1.01x). The alternative, keeping `(group_index, hash)` and comparing `values[group_index]` for those types, measured +14% time on the same query (the dependent value load on the probe path), so the wider entry is the better trade for a key type this rare; it still saves one cache miss per probe. ## What is the testing strategy for this PR? Existing `GroupValuesPrimitive` unit tests and the aggregate sqllogictests cover the behavior (results are unchanged); `force_hash_collisions` still passes since the compare is by key. ## 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]
