Implement `Eq`, `PartialEq`, `Hash` for `dyn PhysicalExpr` #13005

peter-toth · 2024-10-18T13:25:09Z

Which issue does this PR close?

Part of #12599.

Rationale for this change

Common subexpression elimination will require Arc<dyn PhysicalExpr> tree nodes to implement Eq, PartialEq, Hash.

What changes are included in this PR?

This PR:

Refactors PhysicalExpr trait and moves dyn_hash() to a new DynHash trait.
Adds blanket implementation of DynHash for types that implement Hash. This enables us to drop most of the previous dyn_hash() boilerplate implementations.
Introduces DynEq trait with dyn_eq().
Adds blanket implementation of DynEq for types that implement Eq.

Please note that:

This PR contains an API breaking change that dyn_hash() is moved from PhysicalExpr to separate DynHash trait.

This PR contains manual implementation of PartialEq and Hash for some dyn PhysicalExpr types (e.g. BinaryExpr) where adding just #[derive(PartialEq, Hash)] would be straightforward at first glance.
This is due to a Rust bug: Error on deriving PartialEq on Foo and then implementing it for dyn Foo rust-lang/rust#78808 that the derive macro would generate code with the following issue:

   error[E0507]: cannot move out of `other.left` which is behind a shared reference
  --> datafusion/physical-expr/src/expressions/binary.rs:53:5
   |
51 | #[derive(Debug, Hash, Clone, Eq, PartialEq)]
   |                                  --------- in this derive macro expansion
52 | pub struct BinaryExpr {
53 |     left: Arc<dyn PhysicalExpr>,
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^ move occurs because `other.left` has type `Arc<dyn PhysicalExpr>`, which does not implement the `Copy` trait

Are these changes tested?

Yes, with existing tests.

Are there any user-facing changes?

No.

peter-toth · 2024-10-18T13:31:17Z

cc @alamb

alamb · 2024-10-21T20:58:32Z

On my list for review tomorrow

alamb

Thank you @peter-toth -- this PR is a pretty nice improvement in its own right (even without the improved CSE).

Let's see if we can avoid making BinaryExpr generic

alamb · 2024-10-24T19:28:25Z

datafusion/physical-expr/src/expressions/binary.rs

@@ -525,20 +519,6 @@ impl PhysicalExpr for BinaryExpr {
    }
 }

-impl PartialEq<dyn Any> for BinaryExpr {


removing this is great

alamb · 2024-10-24T19:28:36Z

datafusion/physical-expr/src/expressions/binary.rs

-pub struct BinaryExpr {
-    left: Arc<dyn PhysicalExpr>,
+#[derive(Debug, Hash, Clone, Eq, PartialEq)]
+pub struct BinaryExpr<DynPhysicalExpr: ?Sized = dyn PhysicalExpr> {


The removal of the boiler plate in this PR is great ❤️

I feel like this additional trait / workaround is non ideal as it makes understanding the BinaryExpr very unobvious (there is now a level of indirection that is irrelevant for most of users of BinaryExpr).

I am playing around with it to see if I can avoid it somehow

Here is one way that seems to work: peter-toth#5

More verbose, but I think it keeps the structs simpler to understand

Sure, we don't need to keep the generic parameter workaround. I agree that those params look a bit weird.
peter-toth#5 looks good to me, if you extend it to other expressions I can merge it tomorrow and amend my PR description.

Github copilot and I banged out the code. However, I think I accidentally push the commits to your branch 😬 -- hopefully that is ok

No problem. 😁 I've just updated the PR description.

alamb · 2024-10-24T20:55:15Z

datafusion/physical-expr-common/src/physical_expr.rs

@@ -183,6 +151,39 @@ pub trait PhysicalExpr: Send + Sync + Display + Debug + PartialEq<dyn Any> {
    }
 }

+pub trait DynEq {


Maybe we can add some documentation here explaining why this is needed and what it is used for

Added in f1917fa.

alamb

Thank you @peter-toth

I think this is an improvement in my mind, even outside the context of CSE improvements, as it permits PhysicalExpr to implement the standard PartialEq rather than a more special DynEq / any pattern

Perhaps @akurmustafa / @mustafasrepo may have some additonal thoughts as I think they added the original dyn hash work

cc @berkaysynnada

berkaysynnada

I believe this PR brings significant improvements to the API, enhancing both code readability and usability. The clarity of the trait has increased, making it more intuitive to work with. LGTM, Thank you @peter-toth.

berkaysynnada · 2024-10-31T07:10:09Z

datafusion/physical-expr/src/expressions/case.rs

@@ -80,7 +79,7 @@ enum EvalMethod {
 ///     [WHEN ...]
 ///     [ELSE result]
 /// END
-#[derive(Debug, Hash)]
+#[derive(Debug, Hash, PartialEq, Eq)]


How can it permit auto derivation of PartialEq for CaseExpr 🤔 -- we need manual impl's for others

Yeah, this is probably the strangest part of the bug. If you have double wrappers around dyn Trait then there is no issue: rust-lang/rust#78808 (comment)
CaseExpr doesn't have any dyn Trait fields with a single wrapper so the derive macro has no problem.

Should we create a ticket to remove those impl's once the bug is resolved?

How about #13196?

# Conflicts: # datafusion/physical-expr/src/expressions/not.rs

alamb · 2024-10-31T18:51:56Z

What I would like to propose for this PR is wait until we have made the next release: #12470 and then we can merge it after that

I am thinking of how we can spread out the API upgrade pain

alamb · 2024-11-05T18:19:03Z

The 43.0.0 release candidate has been made and we have started voting on it. I merged this branch up from main locally to ensure everything still compiles. It looks good so this is ready to go 🏁

THanks again @peter-toth and @berkaysynnada

peter-toth · 2024-11-05T18:34:05Z

Thanks for review @alamb and @berkaysynnada.

Implement Eq, PartialEq, Hash for PhysicalExpr

4181cb2

github-actions bot added physical-expr Physical Expressions core Core DataFusion crate proto Related to proto crate labels Oct 18, 2024

peter-toth mentioned this pull request Oct 18, 2024

Implement physical optimizer rule for common subexpression elimination #12599

Open

peter-toth mentioned this pull request Oct 21, 2024

Add Common Subexpression Elimination for PhysicalExpr trees #13046

Open

alamb added the api change Changes the API exposed to users of the crate label Oct 24, 2024

alamb reviewed Oct 24, 2024

View reviewed changes

Manually implement PartialEq and Hash for BinaryExpr

5e9257c

alamb mentioned this pull request Oct 24, 2024

Manually implement PartialEq and Hash for BinaryExpr peter-toth/datafusion#5

Merged

alamb added 3 commits October 24, 2024 16:49

Port more

1aa787d

Complete manual derivations

8b4ef56

fmt

66fdd18

alamb reviewed Oct 24, 2024

View reviewed changes

add and fix docs

f1917fa

alamb approved these changes Oct 25, 2024

View reviewed changes

berkaysynnada approved these changes Oct 31, 2024

View reviewed changes

Merge branch 'main' into physicalexpr-eq-partialeq-hash

4a69b2c

# Conflicts: # datafusion/physical-expr/src/expressions/not.rs

peter-toth mentioned this pull request Oct 31, 2024

Remove manual PartialEq and Hash implementations of some PhysicalExprs added in https://github.com/apache/datafusion/pull/13005 #13196

Open

alamb merged commit cc43766 into apache:main Nov 5, 2024
24 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implement `Eq`, `PartialEq`, `Hash` for `dyn PhysicalExpr` #13005

Implement `Eq`, `PartialEq`, `Hash` for `dyn PhysicalExpr` #13005

peter-toth commented Oct 18, 2024 •

edited

Loading

peter-toth commented Oct 18, 2024

alamb commented Oct 21, 2024

alamb left a comment

alamb Oct 24, 2024

alamb Oct 24, 2024

alamb Oct 24, 2024

alamb Oct 24, 2024

peter-toth Oct 24, 2024

alamb Oct 24, 2024 •

edited

Loading

peter-toth Oct 25, 2024

alamb Oct 24, 2024

peter-toth Oct 25, 2024

alamb left a comment

berkaysynnada left a comment

berkaysynnada Oct 31, 2024

peter-toth Oct 31, 2024

berkaysynnada Oct 31, 2024

peter-toth Oct 31, 2024

alamb commented Oct 31, 2024

alamb commented Nov 5, 2024

peter-toth commented Nov 5, 2024

Implement Eq, PartialEq, Hash for dyn PhysicalExpr #13005

Implement Eq, PartialEq, Hash for dyn PhysicalExpr #13005

Conversation

peter-toth commented Oct 18, 2024 • edited Loading

Which issue does this PR close?

Rationale for this change

What changes are included in this PR?

Are these changes tested?

Are there any user-facing changes?

peter-toth commented Oct 18, 2024

alamb commented Oct 21, 2024

alamb left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

alamb Oct 24, 2024 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

alamb left a comment

Choose a reason for hiding this comment

berkaysynnada left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

alamb commented Oct 31, 2024

alamb commented Nov 5, 2024

peter-toth commented Nov 5, 2024

Implement `Eq`, `PartialEq`, `Hash` for `dyn PhysicalExpr` #13005

Implement `Eq`, `PartialEq`, `Hash` for `dyn PhysicalExpr` #13005

peter-toth commented Oct 18, 2024 •

edited

Loading

alamb Oct 24, 2024 •

edited

Loading