Provide semantics-aware plan comparison (order-insensitive equality)

[nielspardon]

Background

Split out from #203. That issue reported that a proto → POJO → proto roundtrip reorders extension declarations. The conclusion there was that this is not a bug: the Substrait spec doesn't constrain extension ordering, and substrait-java allocates extension anchors in discovery order during POJO → proto conversion (deterministic and harmless). We don't intend to guarantee that an externally-authored plan's extension ordering survives a roundtrip.

However, a distinct and still-open suggestion came out of that discussion (from @vbarua, @vibhatha, and @danepitkin): two plans that differ only in spec-irrelevant details (e.g. extension anchor numbering / declaration ordering) currently compare as not equal, because io.substrait.plan.Plan uses the stock order-sensitive equals/hashCode generated by Immutables.

If we consider these plans to be equal, this would be a good argument for a smarter equals method.

Proposal

Provide a semantics-aware comparison for plans — a way to determine that two plans are equivalent modulo details the spec does not constrain (extension anchor values, extension declaration ordering, etc.). Prior art: substrait-cpp's ReferenceNormalizer (normalize anchors in place, then compare).

Options to consider:

• A normalize() / plan-normalization utility that canonicalizes anchor numbering and declaration ordering, so normalized plans can be compared with ordinary equals.
• A dedicated comparator/equivalence helper rather than overriding Plan.equals (overriding equals on the Immutables POJO is likely too invasive and surprising).

Additional case: associativity of variadic functions

Surfaced while reviewing #1001 (variadic concat conversion in Isthmus). Because Calcite's || (SqlStdOperatorTable.CONCAT) is strictly binary, a flat Substrait concat(a, b, c) is converted to a left-nested CONCAT(CONCAT(a, b), c), and back to Substrait as concat(concat(a, b), c). So a Substrait → Calcite → Substrait pass over an externally-authored flat variadic concat is a non-identity transform, even though the two plans are semantically equivalent (concat is associative).

This is a different — and larger — category than the anchor/ordering cases above:

• Anchor numbering / declaration ordering is spec-irrelevant metadata; normalization is a straightforward canonicalization.
• Variadic-function nesting is expression structure. Treating concat(a, b, c) and concat(concat(a, b), c) as equal requires operator-specific knowledge (associativity, and potentially commutativity / identity / flattening for other operators).

Worth deciding deliberately whether this issue covers it, rather than leaving it implicit:

• Keep this issue scoped to metadata normalization (anchors / ordering), and track associative/commutative operator normalization as a separate follow-up, or
• Broaden the normalize() utility to also flatten associative variadic functions (documenting exactly which operators are normalized).

Scope note

This is about semantic equivalence only; it does not change or guarantee wire-format/roundtrip ordering, which remains unconstrained per the spec.

🤖 Generated with AI