Comparison for nested type

[jayzhan211]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

Ref #9252

I want to be able to compare ListArray. The comparison order is left to right and if the prefix is the same then it is considered.
lesser.

For example,

• List(1,2,3) < List(1,2,3,4)
• List(List(1,2,3), List(10)) < List(List(1,2,4), List(1))
• List(List(1,2,3), List(1)) > List(List(1,2,2), List(2))

The behavior takes Duckdb's array sort as a reference.

Describe the solution you'd like

Support nested types in compare_op, currently failed on this line.

    if l_t != r_t || l_t.is_nested() {
        return Err(ArrowError::InvalidArgumentError(format!(
            "Invalid comparison operation: {l_t} {op} {r_t}"
        )));
    }

Describe alternatives you've considered

Additional context

We can support most of the ops in the future, lt and eq are two that I would like to work on first

[tustvold]

I'm not sure we want to support this within these kernels, in particular the null behaviour is not well-defined. I added support to the comparator for this, which will allow systems like DataFusion to define an ordering for nulls based on a config setting, as Spark and Postgres use different ordering.

There is an example of this here - https://docs.rs/arrow-ord/latest/arrow_ord/ord/fn.make_comparator.html#postgres-compatible-nested-comparison

This will also make it more obvious that the nested comparison is not vectorised

Edit: Filed #5942 to make this more discoverable

[jayzhan211]

I'm not sure we want to support this within these kernels, in particular the null behaviour is not well-defined. I added support to the comparator for this, which will allow systems like DataFusion to define an ordering for nulls based on a config setting, as Spark and Postgres use different ordering.

There is an example of this here - https://docs.rs/arrow-ord/latest/arrow_ord/ord/fn.make_comparator.html#postgres-compatible-nested-comparison

This will also make it more obvious that the nested comparison is not vectorised

Edit: Filed #5942 to make this more discoverable

Are you suggesting that if datafusion requires nested comparison, we could implement them in datafusion with make_comparator like what I had done? Arrow-rs only support the make_comparator kernel for nested type?

https://github.com/apache/datafusion/blob/d32747d09add5e1c670aa32fbe3294ecee15e3b7/datafusion/physical-expr/src/expressions/datum.rs#L28-L58

This is the code that utilize compare_op, and nested type is missing

[tustvold]

Yes, DataFusion should decide what null semantics it wants / make this configurable, and implement it using make_comparator if appropriate