[FEA] Add support for shallow lists in cudf::merge

[jlowe]

Is your feature request related to a problem? Please describe.
Spark supports sorting on BinaryType which is represented as a libcudf LIST column which a child column of non-nullable UINT8. The RAPIDS Accelerator leverages cudf::merge to perform out-of-core sort algorithms. cudf::sorted_order supports sorting on the LIST column directly, but cudf::merge does not, failing with the error:

CUDF failure at:/..../cudf/cpp/src/merge/merge.cu:236: Unsupported type for merge.

Describe the solution you'd like
cudf::merge should support the same ordering types as supported by cudf::sorted_order

Describe alternatives you've considered
Applications would need to concatenate the tables to be merged together into one big table and then call cudf::sorted_order which is suboptimal to being able to perform the merged sort directly via cudf::merge.

[bdice]

This should be covered by #13347. I believe this is targeting 23.08. cc: @divyegala

[jlowe]

Thanks, @bdice! I just discovered that cudf::merge is not only unhappy with a shallow list as an ordering column, but it's also unhappy even if a shallow list is not an ordering column which is surprising. Will #13347 address that as well given it's focused on columns for comparison?

[bdice]

I bet the logic for raising an error is incorrect (too aggressive, fails even on non-ordering columns which seems unnecessary). We should definitely add a test for that. @jlowe Does it help you if the non-ordering columns issue is fixed sooner than #13347? Otherwise we should just add a test there.

[jlowe]

Does it help you if the non-ordering columns issue is fixed sooner than #13347?

Slightly but may not be worth it. We can work around the issue by concatenating the tables and calling cudf::sorted_order as mentioned above which is slower but should hold us over until cudf::merge for lists is properly fixed.

[jlowe]

I noticed that the mishandling of non-key nested types in cudf::merge is already tracked by #8050.

[chenya-zhang]

Thank you @jlowe @bdice for inputs on this issue.

+1 on "the logic for raising an error is incorrect (too aggressive, fails even on non-ordering columns which seems unnecessary)".

If possible, we hope users do not experience unexpected job failure when moving Spark jobs from CPU to GPU. It may be helpful to give them a clear message to check on unsupported operations or be aware of any fallback. We don't seem to find more information for this one besides the exception (and stack trace):

Caused by: ai.rapids.cudf.CudfException: CUDF failure at:/home/jenkins/agent/workspace/jenkins-spark-rapids-jni_nightly-dev-426-cuda11/thirdparty/cudf/cpp/src/merge/merge.cu:236: Unsupported type for merge.

FYI: There are messages on other unsupported operations which fall back as expected. We will help to share more on them.

[GregoryKimball]

@bdice @divyegala are #13514 and #8050 closed by #14250?

[divyegala]

@GregoryKimball thanks. Yes, they should be

[vyasr]

Closing as resolved by #14250.