[BUG] DECIMAL128 groupby has a performance cliff when per-block cardinality crosses 128
- Dominant language
- C++
- Stars
- 9.8k
- Forks
- 1.1k
- Avg merge
- 3d 6m
- Merged PRs (30d)
- 278
Description
### Problem
Velox's cuDF aggregation path currently relies on libcudf's automatic choice between hash and sort groupby. A low-cardinality `DECIMAL128` `SUM` can be pathologically slow when hash groupby is selected and the per-block key cardinality is just above the shared-memory aggregation threshold.
This is a general algorithm-selection issue. TPC-H Q9 on decimal columns is one example that exposed it, but the problem is not specific to TPC-H, Q9, or its query plan.
### Example profile
The timeline below shows repeated groupby calls (green nvtx ranges titled CudfGroupbyPARTIAL) taking roughly 1.2-1.4 seconds each for this case:
### Minimal reproduction shape
Using cuDF commit `5beaa5954688fcb12236ffb434e192ea2c77db30`:
- Approximately 30.6 million input rows per batch.
- Fixed-seed, randomly ordered keys.
- Low output cardinality.
- `DECIMAL128(32,4)` values.
- One groupby request containing `SUM` and `COUNT_VALID`.
- Input creation, allocation, and one warm-up aggregation excluded from timing.
The cardinality sweep showed a sharp discontinuity:
| Cardinality | Hash groupby median |
|---:|---:|
| 64 | 6.75 ms |
| 128 | 9.21 ms |
| 129 | 1.554 s |
| 175 | 1.033 s |
| 256 | 555 ms |
| 1,024 | 103 ms |
At cardinality 175, adding an otherwise-unused `nth_element(0)` aggregation to the request forces libcudf's sort implementation, following the workaround used by libcudf's groupby tests:
- Normal hash selection: 1.101 s median.
- Forced sort selection: 10.68 ms median.
- Approximately 103x faster for the isolated groupby.
The same forcing experiment was also tested end to end through Velox on the query that originally exposed the issue. The hot query mean improved from 17.976 seconds to 9.660 seconds (46.3%), and the result checksum was unchanged.
### Why this happens
`DECIMAL128` `SUM` is accepted by `can_use_hash_groupby()`. Hash groupby's per-block shared-memory cardinality threshold is 128. Once a block exceeds that threshold, the aggregation falls back to the global-memory path. With a small number of groups and many input rows, many updates target the same 128-bit decimal accumulator locations.
The profile for the slow case selects the sparse hash aggregation kernel. The threshold cliff and forced-sort comparison establish the algorithm-selection problem; detailed instruction-level stall attribution would require a separate Nsight Compute experiment.
### Possible fixes
Some options worth considering:
1. Select sort groupby for low-cardinality `DECIMAL128 SUM` when hash groupby would use the global-memory aggregation path.
2. Make the shared-memory cardinality threshold or accumulator layout more adaptive for `DECIMAL128` aggregation.
3. Expose a supported implementation-selection hint so callers such as Velox can choose sort for known-problematic request shapes without adding a dummy aggregation.
Any Velox-side policy must remain selective: a separate four-key-group aggregation-heavy query was substantially faster with shared-memory hash groupby and regressed when sort was forced.
### Related issues
- [#23256](https://github.com/NVIDIA/cudf/issues/23256) describes the related global-atomic hot-key contention problem, but at much higher cardinality and with a smaller slowdown.
- [#19511](https://github.com/NVIDIA/cudf/issues/19511) tracks the longer-term effort to merge hash- and sort-based groupby pipelines, which may eventually improve automatic selection.
- [#19564](https://github.com/NVIDIA/cudf/issues/19564) previously proposed an explicit `use_sort_groupby` option to replace the `nth_element` forcing workaround, but was closed without implementation.
- [#22154](https://github.com/NVIDIA/cudf/issues/22154) added `DECIMAL128` coverage to groupby benchmarks but did not address runtime algorithm selection.
Contributor guide
Research direction
Start with libcudf's can_use_hash_groupby() decision and the groupby tests referenced in the issue, then reproduce the DECIMAL128 SUM/COUNT_VALID cardinality sweep around 128. Compare hash and sort paths through the isolated benchmark and the Velox query; done means a selective algorithm choice or supported mechanism removes the performance cliff without regressing the shared-memory case or changing the checksum.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- data, performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100