refactor: use arrow make_comparator for nested structural equality in arrays_overlap and array_position

[peterxcli]

Which issue does this PR close?

Closes #5101.

Rationale for this change

The nested fallback paths in arrays_overlap and array_position duplicate comparison behavior already provided by Arrow. arrays_overlap recursively compares nested elements and dispatches an equality kernel for each leaf pair, while array_position materializes a ScalarValue for every candidate element. Arrow's reusable make_comparator supports the same nested structural comparison without this per-element dispatch and allocation overhead.

What changes are included in this PR?

• Build and reuse an Arrow comparator for nested arrays_overlap probe/search pairs, while retaining the existing flat fast paths and outer null handling.
• Build one comparator for the flattened values and search arrays in array_position instead of allocating ScalarValues in the inner loop.
• Remove the hand-written list/struct structural equality helpers.
• Add focused coverage for nested NaN, signed-zero, and inner-null comparisons. The tests preserve the existing Arrow/ScalarValue total-order behavior.

How are these changes tested?

• cargo test -p datafusion-comet-spark-expr --lib (568 passed)
• cargo clippy -p datafusion-comet-spark-expr --lib --tests -- -D warnings

[andygrove]

Thanks for picking this up. Swapping the hand-written recursion for make_comparator is the right call, and the nested semantics do line up with Spark. Arrow's compare_list walks elements with null equal to null, treats a null as less than any value, and falls back to comparing lengths, which is exactly what PhysicalArrayType.interpretedOrdering does in Spark, and compare_struct lines up with PhysicalStructType the same way. I also appreciate that the test comments quietly correct the premise in #5101. The old leaf comparison went through Arrow's eq kernel, and ArrowNativeTypeOp::is_eq for floats is to_bits() == to_bits(), so total order was already in play and NaN already matched itself. Deleting structural_eq, list_structural_eq, and struct_structural_eq is a real simplification.

Three things I would like to work through before this goes in.

1. The comparator is now built once per row

native/spark-expr/src/array_funcs/arrays_overlap.rs, in arrays_overlap_list_generic.

make_comparator now sits inside the row loop, because probe and search are per-row slices from list.value(i). So every row pays for a fresh recursive comparator build: a boxed closure per nesting level, a logical_nulls() clone per level, and the offset buffer clones underneath. For short nested arrays, which I would expect to be the common shape, that setup can dominate, and the code being replaced had no per-row setup at all.

Could this be hoisted above the loop? A comparator built over the unsliced left.values() and right.values() gives the same answers when indexed with absolute offsets, which is how flat_row_overlap already works. Since we only ever test for Ordering::Equal, argument order does not matter, so one comparator covers both sides of the probe/search swap: call it as cmp(left_index, right_index) no matter which side is probing. needs_comparator can be hoisted as well, since a row slice has the same data type as its child array. The case to keep in mind is the mismatched-child-type entry into the generic path, so gating the hoisted build on left_values.data_type() == right_values.data_type() would leave that behavior as it is today.

2. No measurement for the path being changed

The commit is titled perf: and the rationale is about per-element dispatch and allocation, but the evidence given is cargo test and clippy. native/spark-expr/benches/arrays_overlap.rs covers int32 and utf8 lists only, and those are the flat fast paths this PR does not touch, so nothing in the repo measures the nested path today.

Could you add nested cases to that bench, say array<array<int>> and array<struct<..>> at short and long lengths, and post before and after numbers? For a refactor justified on performance grounds I think we need to see the win, and it would also settle whether the per-row build in point 1 matters.

3. The new float tests pin behavior that does not match Spark

test_nested_float_total_order and test_nested_float_and_null_position.

You are right that the signed-zero behavior is preserved rather than introduced, so this is not something the PR breaks. My concern is that both tests now assert it with comments that read as though it is the intended answer, and I do not think it is.

Spark's arrays_overlap picks its evaluation path on TypeUtils.typeWithProperEquals. For atomic element types it uses fastEval, which is a java.util.HashSet, so Double.equals applies and -0.0 does not match 0.0. For nested element types it uses bruteForceEval with ordering.equiv, which bottoms out in SQLOrderingUtil.compareDoubles. That is if (x == y) 0 else java.lang.Double.compare(x, y), and its doc comment spells out -0.0 == 0.0. So Spark is itself split. The flat case distinguishes signed zeros and the nested case does not. Our flat fast path happens to match Spark because it keys on bits, and the nested path does not.

array_position has no such split. It always uses ordering.equiv, so -0.0 matches 0.0 at every level. That leaves us inconsistent inside a single function, because position_float uses v == search_val and gets Spark's answer while position_fallback does not:

CREATE TABLE t(arr array<array<double>>, val array<double>) USING parquet;
INSERT INTO t VALUES (array(array(0.0D)), array(-0.0D));
SELECT array_position(arr, val) FROM t;
-- Spark returns 1, we return 0

The same shape applies to arrays_overlap on two array<array<double>> columns holding array(array(0.0D)) and array(array(-0.0D)), where Spark returns true and we return false. Worth noting the (array(0.0), array(-0.0)) row in arrays_overlap.sql does not cover this, because -0.0 there parses as a decimal literal and negating decimal zero gives positive zero, so both columns end up holding 0.0.

Could you file an issue for the nested signed-zero case and reference it in both test comments, so the asserted values do not read as deliberate? If you would rather fix it here, normalizing negative zero in the float leaves before building the comparator would do it, and I am fine with that being separate work as long as it is tracked.

One part of those tests I do want to keep: total order gives NaN equal to NaN, which is what Spark does in both of its paths, so that half is correct.

[andygrove]

Thanks for addressing the feedback @peterxcli. LGTM.

[peterxcli]

@andygrove thanks for the review!