Change Expr PartialOrd to not rely on comparing hash values #8932

Activity

1. alamb

   added

   bugSomething isn't workingSomething isn't working

   on Jan 21, 2024
2. alamb commented on Jan 21, 2024

   

   alamb

   on Jan 21, 2024

   ContributorAuthor

   More actions

   @tustvold notes on #8908 (comment):

   Edit: as suspected it looks like PartialEq is being derived using a proc macro, and is therefore inconsistent with this implementation of PartialOrd - https://github.com/apache/arrow-datafusion/blob/main/datafusion/expr/src/expr.rs#L87. In particular PartialOrd could claim things to be equal due to a hash collision, when PartialEq would indicate they are not

   So my conclusion is that this is a latent bug waiting to happen (that will be very hard to track down if/when it does strike)

   👍React with 👍3Reacted by Raphael Taylor-Davies, Liang-Chi Hsieh and Oleks V
3. alamb

   added

   help wantedExtra attention is neededExtra attention is needed

   on Jan 21, 2024
4. alamb

   changed the title [-]Change Expr ordering so it does not rely on `PartialOrd`[/-] [+]Change Expr `PartialOrd` to not rely on comparing hash values[/+] on Jan 21, 2024
5. ngli-me commented on Sep 8, 2024

   

   ngli-me

   on Sep 8, 2024

   Contributor

   More actions

   Hi, I'm new to this project and was poking through the issues, can I try working this one out?

   It looks like, to remove the hash we would need to first compare by enum variant (it looks like based on the test that the declaration order determines the Ord). I see two solutions for this, either implementing a "discriminant" function to determine the variant ordering, or by having a lot of match arms.

   In the case of equivalent variant, we can then compare by fields, looks like it should work for the majority of them.

   Is that the right track?
6. alamb commented on Sep 9, 2024

   

   alamb

   on Sep 9, 2024

   ContributorAuthor

   More actions

   Hi, I'm new to this project and was poking through the issues, can I try working this one out?

   It looks like, to remove the hash we would need to first compare by enum variant (it looks like based on the test that the declaration order determines the Ord). I see two solutions for this, either implementing a "discriminant" function to determine the variant ordering, or by having a lot of match arms.

   In the case of equivalent variant, we can then compare by fields, looks like it should work for the majority of them.

   Is that the right track?

   I think so . I don't think the actual relative order of Exprs is important, only that it is consistent

   It might be worth figuring out how to break this work into some smaller PRs (rather than one large one) -- perhaps by implementing partial ord for sub fields / structs that are used in Expr before trying to do so for the whole thing.
7. ngli-me commented on Sep 9, 2024

   

   ngli-me

   on Sep 9, 2024

   Last edited by ngli-me

   Contributor

   More actions

   Good idea! I went back through to check all the DF sub fields/structs, will start the work + breaking it down.

   PartialOrd Status

   • Expr
   • Alias -> requires Expr, otherwise can derive
     • TableReference -> derives PartialOrd
   • Column
     • TableReference -> derives PartialOrd
   • DataType -> derives PartialOrd
   • ScalarValue -> has (manual implementation)
   • BinaryExpr -> depends on Expr
   • Like -> depends on Expr
   • Between -> depends on Expr
   • Case -> depends on Expr
   • Cast -> depends on Expr
   • TryCast -> depends on Expr
   • ScalarFunction -> depends on Expr
     • ScalarUDF (doable)
   • AggregateFunction -> similar to WindowFunction, but also requires Expr
     • Sort -> depends on Expr
   • WindowFunction (also uses Sort)
     • WindowFunctionDefinition (Add PartialOrd for the DF subfields/structs for the WindowFunction expr #12421)
     • WindowFrame
       • WindowFrameUnits
       • WindowFrameBound
         • ScalarValue (actually, it already has it implemented, somehow missed it on first go through)
     • NullTreatment
   • Inlist -> depends on Expr
   • Exists -> depends on Subquery
   • InSubquery -> depends on Expr and Subquery
   • Subquery -> also depends on Expr
     • LogicalPlan -> the subtypes of these require Expr and LogicalPlan, looks like this should be done near last
   • Wildcard
     • TableReference -> derives PartialOrd
     • WildcardOptions
       • PlannedReplaceSelectItem -> depends on expr
   • GroupingSet -> depends on Expr
   • Placeholder
   • OuterReferenceColumn
     • Datatype -> derives PartialOrd
     • Column -> derives PartialOrd
   • Unnest -> depends on Expr

   ❤️React with ❤️1Reacted by Andrew Lamb
8. ngli-me commented on Sep 14, 2024

   

   ngli-me

   on Sep 14, 2024

   Contributor

   More actions

   I was going through the remaining subtypes/structs, and saw an issue that I wasn't sure how to resolve. While most of the remaining can derive PartialOrd, it looks like DFSchema can't, and since it has a dependency on a Hashmap. A similar problem happens in CreateExternalTable, which uses two Hashmaps. Not sure how to approach this, any advice would be appreciated!
9. alamb commented on Sep 14, 2024

   

   alamb

   on Sep 14, 2024

   ContributorAuthor

   More actions

   I would personally suggest trying to simply ignore the contents of the schema for partial ord -- I think in general the other fields in structs should be enough to compute equality and ordering
10. alamb

    closed this as completedin #12481on Sep 21, 2024