[FEA] Enable structs of lists in the new row lexicographic comparator

[vyasr]

Is your feature request related to a problem? Please describe.
#11129 enables comparisons of list dtypes with the new comparator. In principle, this code should (in conjunction with prior work like #10164) be sufficient to enable structs of lists (but not lists of structs) via the struct decomposition approach used to preprocess structs. Currently, we forbid comparison of lists of structs in the comparator. During development of #11129 I attempted to remove this restriction, but I observed that this led to unexpected test failures of groupby_structs_test/lists_are_unsupported. These failures were not caused by a failure of EXPECT_THROW (which would be natural since I removed a restriction), but were actual failures in the computed outputs. I was unable to reproduce these failures locally, indicating that there is perhaps some unknown indeterminacy in the ordering of some step in the comparison.

Describe the solution you'd like
The struct of list restriction in check_lex_compatibility should be removed and the failing test should be fixed such that structs of lists are properly supported.

[ttnghia]

For comparing lists, we need to generate dremel data. However:

• Dremel data is generated only for lists columns that are not children of any other column:

  cudf/cpp/src/table/row_operators.cu

  Lines 265 to 270 in 9c9dd54

  	for (auto const& col : table) {
  	if (col.type().id() == type_id::LIST) {
  	dremel_data.push_back(detail::get_comparator_data(col, {}, false, stream));
  	dremel_device_views.push_back(dremel_data.back());
  	}
  	}

• On device, dremel data is considered for comparison only in the same situation:

  cudf/cpp/include/cudf/table/experimental/row_operators.cuh

  Lines 559 to 567 in 9c9dd54

  	auto [l_dremel_i, r_dremel_i] = [&]() {
  	if (_lhs.column(i).type().id() == type_id::LIST) {
  	auto idx = list_column_index++;
  	return std::make_tuple(optional_dremel_view(_l_dremel[idx]),
  	optional_dremel_view(_r_dremel[idx]));
  	} else {
  	return std::make_tuple(optional_dremel_view{}, optional_dremel_view{});
  	}
  	}();

• Even that, structs column cannot have lists children. Otherwise, we will encounter compiler stack overflow with device code due to type dispatcher with inline device code. The current code only processes child structs iteratively while ignoring lists (dispatch_void_if_nested):

  cudf/cpp/include/cudf/table/experimental/row_operators.cuh

  Lines 409 to 413 in 9c9dd54

  	return cudf::type_dispatcher<dispatch_void_if_nested>(
  	lcol.type(),
  	element_comparator{_check_nulls, lcol, rcol, _null_precedence, depth, _comparator},
  	lhs_element_index,
  	rhs_element_index);

So in order to fix this completely, we need both to generate+consider dremel data for nested lists columns as well as fixing the issue with type dispatcher above.

[ttnghia]

Fixing dremel issue is easy, just a few LOC. For fixing the type dispatcher, I can't find any way to avoid using such dispatch_void_if_nested that does not lead to compiler stack overflow. Thus, I turned to a different approach: Keep using dispatch_void_if_nested as currently but change decompose_structs such that:

• For structs-of-lists column, instead of always output a structs column with only one child (such as struct<list>), the function will output a structs column having 0 child (struct<>). This structs column still has the same null mask as the original input.
• The change above will be applied only for the input structs column with the first child is lists column.

By doing so, we can avoid dispatching element_comparator for lists comparison inside device kernel for structs comparison. I've finished implementation for this which can produce correct results with simple input. I'll test more and will post a complete PR with benchmark later when I have time.