[FEA] Refactors and next steps for segmented reductions

[bdice]

This is issue contains a few proposals for improving the segmented reduction code introduced in #9621.

Investigate sort-groupby aggregations

(Idea from @ttnghia)

With the ability to perform segmented reductions, sort-based groupby may be able to use group_offsets to define its segments, rather than materializing a full column of sorted/monotonic group_labels. In effect, this allows us to replace a call to thrust::reduce_by_key algorithm with a call to cub::DeviceSegmentedReduce::Reduce, while eliminating the need to compute the group_labels column. I think this should be a more efficient algorithm, and also will require less intermediate memory allocation. Benchmarks should be performed when making this change.

Refactor internal use of indices to 2N style (match CUB)

The indexing scheme used for segmented reduction is currently "N+1", like how list offsets are indexed. We want to refactor this to use "2N" indexing. This would align with cub::DeviceSegmentedReduce::Reduce and permit greater flexibility in the API internals. See discussion here for details.

• @bdice: After discussion with @davidwendt, we decided this is not necessary in the short term. We can resolve this issue without changing the current implementation. The current implementation of N+1 aligns with segmented sort behavior. If there is a compelling need to change this in the future for expanded functionality, we can revisit.

Compound reductions like mean

The segmented reduction code currently supports "simple" reductions. Support for "compound" reductions is needed. This includes multi-step calculations like mean, standard deviation, or sum of squares. Non-segmented compound reductions are defined here: https://github.com/rapidsai/cudf/blob/c1638869116aae2c6dde6024394279a2fb79e685/cpp/src/reductions/compound.cuh

Fixes for output_type precision

@isVoid and I filed #9988 while working on #9621 because the documentation doesn't align with the implementation for when data is cast to the output dtype relative to when the reduction is performed. This affects segmented reduction as well.

Explore rewriting get_null_replacing_element_transformer with nullate

It may be possible to clean up the implementation of null element handling here by using nullate.

• @bdice: After discussion with @davidwendt, we decided this is not worth changing. It might eliminate one or two lines of duplicate code but doesn't offer any benefits to compile time.

Extend to more data types

We need to review the types supported by non-segmented reductions and ensure that segmented reductions support the same types. Decimal support has been requested here: #10417

[jrhemstad]

Support for "compound" reductions is needed.

I'd suggest moving segmented (and regular) reductions to use a scheme like in groupby/rolling where every aggregation has a preprocessing/finalization steps:

cudf/cpp/include/cudf/detail/aggregation/aggregation.hpp

Lines 161 to 166 in b1ea304

	std::vector<std::unique_ptr<aggregation>> get_simple_aggregations(
	data_type col_type, simple_aggregations_collector& collector) const override
	{
	return collector.visit(col_type, *this);
	}
	void finalize(aggregation_finalizer& finalizer) const override { finalizer.visit(*this); }

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[isVoid]

Still in development.

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[github-actions]

This issue has been labeled inactive-90d due to no recent activity in the past 90 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed.

[bdice]

After merging #12573, we can update this to use segmented reductions detail APIs like cudf::reduction::detail::segmented_reduce:

cudf/cpp/include/cudf/detail/null_mask.cuh

Line 299 in 3fa081a

CUDF_CUDA_TRY(cub::DeviceSegmentedReduce::Sum(nullptr,