NVIDIA / NVIDIA/cudf

[FEA] Add a "dense groupby" implementation

Open
#17,754 1 comment 0 reactions 1 assignee Claimed by @ttnghia View on GitHub
feature request libcudf
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

**Is your feature request related to a problem? Please describe.**
As of 25.02, the implementation for hash-based groupby aggregations tracks partial aggregations in a table that is sized to the double the row count of the input table. Once all of the input rows have been processed, the implementation completes a compaction step to extract the non-empty entries. If the number of distinct groups is smaller than the number of rows, this approach leads to excess memory usage as well as an additional memory copy.

**Describe the solution you'd like**
Introduce a hash table that tracks an output index with a key hash value. When a new group is found, increment a "write counter". When processing the aggregation kinds, update the partial aggregations at the output index for that group.

With this idea, the output data will not require another gather. The output data will be created in contiguously and (probably) available for output column creation without another copy. The cost would be some additional atomics pressure when cardinality is high. It may be that "sparse" partial aggregation are preferred if the cardinality is close to the row count (needs confirmation).

**Additional context**

The current setup for Keys, Values, and Aggregations uses a Struct of Arrays (SoA) format, leading to numerous random memory accesses. Consider exploring a conversion from SoA to Array of Structs (AoS).

There is an internal reference for NVIDIA internal developers [here](https://docs.google.com/presentation/d/1IhXVEazLK2vJAm3MJS-K-PaIqSRW4hFAlFzWhQrrF_E/edit#slide=id.g48a3c73947_0_113). If you an external developer and would like to learn more, please contact gkimball@nvidia.com.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.