Groupby hash aggregations use sort-based implementation if nested-type columns are used as values

[divyegala]

We should be able to use nested-type columns as values and still be able to invoke a hash-based groupby, as hash-based is generally faster so we do not want to be silently using sort-based.

cudf/cpp/src/groupby/hash/groupby.cu

Lines 654 to 656 in abc0d41

	// Currently, input values (not keys) of STRUCT and LIST types are not supported in any of
	// hash-based aggregations. For those situations, we fallback to sort-based aggregations.
	if (v_type.id() == type_id::STRUCT or v_type.id() == type_id::LIST) { return false; }

Reference thread: #13795 (comment)

[bdice]

This code block is the piece in question:

cudf/cpp/src/groupby/hash/groupby.cu

Lines 654 to 656 in b446a6f

	// Currently, input values (not keys) of STRUCT and LIST types are not supported in any of
	// hash-based aggregations. For those situations, we fallback to sort-based aggregations.
	if (v_type.id() == type_id::STRUCT or v_type.id() == type_id::LIST) { return false; }

@ttnghia, you added this in #13676. Do you know if this fallback is still required, or why?

We discussed this a bit here: #13676 (comment)

Side note, I'm punching my past self -- I asked this question on that PR, and never submitted my review:

[ttnghia]

@ttnghia, you added this in #13676. Do you know if this fallback is still required, or why?

Because hash-based aggregations are implemented for plain type only, using the operator such as < instead of user-provided comparator. See struct update_target_element in cpp/include/cudf/detail/aggregation/aggregation.cuh.

If we want to support hash-based aggregates for nested types, we need to rewrite such struct update_target_element such that we can compare rows using a row comparator instead.

[bdice]

Great, that was helpful. I think we can do this. I think the rough plan would be to preprocess the table so we have device comparators that can be used, pass the preprocessed table info through all the aggregation machinery, and use the device comparator where needed in update_target_element. Does that sound right to you?

[ttnghia]

Yes that sounds good. Note that we only need to rework for ARGMIN and ARGMAX (other aggregations are SUM, PRODUCT etc that can't support nested types), not for everything thus the amount of work should not be very heavy.

[PointKernel]

To clarify, the reason we cannot use hash-based groupby for nested types is that there is currently no way to atomically update nested data on the device due to the lack of direct hardware support for such operations. A possible solution is to use an atomic lock table, which CCCL is expected to support in the future NVIDIA/cccl#990.

We should backlog this for now until the atomic lock table becomes available.