fix: Fix EquivalenceClass calculation for Union queries
#16185
Conversation
github-actions
bot
added
physical-expr
There was a problem hiding this comment.
Thank you @chenkovsky
FYI @mustafasrepo I wonder if you have a few minutes to review this PR
| @@ -422,6 +423,32 @@ impl EquivalenceGroup { | |||
| self.bridge_classes() | |||
| } | |||
|
|
|||
| #[allow(clippy::type_complexity)] | |||
| fn adjacent_set(&self) -> HashSet<(&Arc<dyn PhysicalExpr>, &Arc<dyn PhysicalExpr>)> { | |||
There was a problem hiding this comment.
Can we please add documentation to these functions about what they do and what the returned structure represents?
| set | ||
| } | ||
|
|
||
| pub fn intersect(&self, other: &Self) -> Self { |
There was a problem hiding this comment.
Likewise here, can we please add documentation
There was a problem hiding this comment.
Thanks @chenkovsky -- I worry about the expoenential time of this algorithm
| /// two equivalence groups. | ||
| #[allow(clippy::type_complexity)] | ||
| fn adjacent_set(&self) -> HashSet<(&Arc<dyn PhysicalExpr>, &Arc<dyn PhysicalExpr>)> { | ||
| let mut set = HashSet::new(); |
There was a problem hiding this comment.
this algorithm is O(N^2) in the number of items in the equivalence class, right?
We have hit other really long planning times when using such algorithms, for example
Is there some way to make this more efficient? Maybe by creating an 2x boolean array to represent the intersections?
There was a problem hiding this comment.
@alamb now time complexity is O(nlogn)
There was a problem hiding this comment.
I think Equivalence System Overhaul is better way, so I closed that PR.
There was a problem hiding this comment.
GTHanks @chenkovsky -- I am sorry I didn't have enough time to review this PR in more detail
alamb
changed the title
EquivalenceClass calculation for Union queries
|
Which issue does this PR close?
Rationale for this change
equivalence is not set.
What changes are included in this PR?
compute intersect of equivalence for union
Are these changes tested?
UT
Are there any user-facing changes?
No