[BUG] DECIMAL128 groupby has a performance cliff when per-block cardinality crosses 128

[devavret]

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 describes the related global-atomic hot-key contention problem, but at much higher cardinality and with a smaller slowdown.
• #19511 tracks the longer-term effort to merge hash- and sort-based groupby pipelines, which may eventually improve automatic selection.
• #19564 previously proposed an explicit use_sort_groupby option to replace the nth_element forcing workaround, but was closed without implementation.
• #22154 added DECIMAL128 coverage to groupby benchmarks but did not address runtime algorithm selection.