feat(optimizer): condition && join predicate #367
There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,149 @@ | ||
| use fixedbitset::FixedBitSet; | ||
|
|
||
| use crate::expr::{get_inputs_col_index, Expr, ExprImpl, ExprType, FunctionCall, InputRef}; | ||
| use crate::utils::Condition; | ||
| #[derive(Debug, Clone)] | ||
| /// the join predicate used in optimizer | ||
| pub struct EqJoinPredicate { | ||
| /// other conditions, linked with AND conjunction. | ||
| other_cond: Condition, | ||
|
|
||
| /// the equal columns indexes(in the input schema) both sides, | ||
| /// the first is from the left table and the second is from the right table. | ||
| /// now all are normal equal(not null-safe-equal), | ||
| eq_keys: Vec<(InputRef, InputRef)>, | ||
| } | ||
| #[allow(dead_code)] | ||
| impl EqJoinPredicate { | ||
| /// the new method for `JoinPredicate` without any analysis, check or rewrite. | ||
| pub fn new(other_cond: Condition, eq_keys: Vec<(InputRef, InputRef)>) -> Self { | ||
| Self { | ||
| other_cond, | ||
| eq_keys, | ||
| } | ||
| } | ||
|
|
||
| /// `create` will analyze the on clause condition and construct a `JoinPredicate`. | ||
| /// e.g. | ||
| /// ```sql | ||
| /// select a.v1, a.v2, b.v1, b.v2 from a,b on a.v1 = a.v2 and a.v1 = b.v1 and a.v2 > b.v2 | ||
| /// ``` | ||
| /// will call the `create` function with left_colsnum = 2 and on_clause is (supposed input_ref | ||
| /// count start from 0) | ||
| /// ```sql | ||
|
Contributor
Author
There was a problem hiding this comment. (it is just pass the doc test |
||
| /// input_ref(0) = input_ref(1) and input_ref(0) = input_ref(2) and input_ref(1) > input_ref(3) | ||
| /// ``` | ||
| /// And the `create funcitons` should return `JoinPredicate` | ||
| /// ```sql | ||
| /// other_conds = Vec[input_ref(1) = input_ref(1), input_ref(1) > input_ref(3)], | ||
| /// keys= Vec[(1,1)] | ||
| /// ``` | ||
| #[allow(unused_variables)] | ||
| pub fn create(left_cols_num: usize, right_cols_num: usize, on_clause: Condition) -> Self { | ||
| let mut other_cond = Condition::true_cond(); | ||
| let mut eq_keys = vec![]; | ||
|
|
||
| for cond_expr in on_clause.conjunctions { | ||
| let mut cols = FixedBitSet::with_capacity(left_cols_num + right_cols_num); | ||
| get_inputs_col_index(&cond_expr, &mut cols); | ||
| let from_left = cols | ||
| .ones() | ||
| .min() | ||
| .map(|mx| mx < left_cols_num) | ||
| .unwrap_or(false); | ||
| let from_right = cols | ||
| .ones() | ||
| .max() | ||
| .map(|mx| mx >= left_cols_num) | ||
| .unwrap_or(false); | ||
| match (from_left, from_right) { | ||
| (true, true) => { | ||
| // TODO: refactor with if_chain | ||
| let mut is_eq_cond = false; | ||
| if let ExprImpl::FunctionCall(function_call) = cond_expr.clone() { | ||
| if function_call.get_expr_type() == ExprType::Equal { | ||
| if let (_, ExprImpl::InputRef(x), ExprImpl::InputRef(y)) = | ||
| function_call.decompose_as_binary() | ||
| { | ||
| is_eq_cond = true; | ||
| if x.index() < y.index() { | ||
| eq_keys.push((*x, *y)); | ||
| } else { | ||
| eq_keys.push((*y, *x)); | ||
| } | ||
| } | ||
| } | ||
| } | ||
| if !is_eq_cond { | ||
| other_cond.conjunctions.push(cond_expr) | ||
| } | ||
| } | ||
| (true, false) => other_cond.conjunctions.push(cond_expr), | ||
| (false, true) => other_cond.conjunctions.push(cond_expr), | ||
| (false, false) => other_cond.conjunctions.push(cond_expr), | ||
| } | ||
| } | ||
| Self::new(other_cond, eq_keys) | ||
| } | ||
|
|
||
| /// Get join predicate's eq conds. | ||
| pub fn eq_cond(&self) -> Condition { | ||
| Condition { | ||
| conjunctions: self | ||
| .eq_keys | ||
| .iter() | ||
| .cloned() | ||
| .map(|(l, r)| { | ||
| FunctionCall::new(ExprType::Equal, vec![l.bound_expr(), r.bound_expr()]) | ||
| .unwrap() | ||
| .bound_expr() | ||
| }) | ||
| .collect(), | ||
| } | ||
| } | ||
|
|
||
| pub fn non_eq_cond(&self) -> Condition { | ||
| self.other_cond.clone() | ||
| } | ||
|
|
||
| pub fn all_cond(&self) -> Condition { | ||
| let mut cond = self.eq_cond(); | ||
| cond.and(self.non_eq_cond()); | ||
| cond | ||
| } | ||
|
|
||
| pub fn has_eq(&self) -> bool { | ||
| !self.eq_keys.is_empty() | ||
| } | ||
|
|
||
| pub fn has_non_eq(&self) -> bool { | ||
| !self.other_cond.always_true() | ||
| } | ||
|
|
||
| /// Get a reference to the join predicate's other cond. | ||
| pub fn other_cond(&self) -> &Condition { | ||
| &self.other_cond | ||
| } | ||
|
|
||
| /// Get a reference to the join predicate's eq keys. | ||
| pub fn eq_keys(&self) -> &[(InputRef, InputRef)] { | ||
| self.eq_keys.as_ref() | ||
| } | ||
|
|
||
| pub fn eq_indexes(&self) -> Vec<(usize, usize)> { | ||
| self.eq_keys | ||
| .iter() | ||
| .map(|(left, right)| (left.index(), right.index())) | ||
| .collect() | ||
| } | ||
|
|
||
| pub fn left_eq_indexes(&self) -> Vec<usize> { | ||
| self.eq_keys.iter().map(|(left, _)| left.index()).collect() | ||
| } | ||
| pub fn right_eq_indexes(&self) -> Vec<usize> { | ||
| self.eq_keys | ||
| .iter() | ||
| .map(|(_, right)| right.index()) | ||
| .collect() | ||
| } | ||
| } | ||
Oops, something went wrong.
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Why this is called
EqJoinPredicate? So at least it contains one equal preidcate?Do we have
NeqJoinPredicate? etc.There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
this is just for equal join which has equal join and used for hashjoin and sortMergeJoin to easily get the eq and noneq condition. for the non eq join, the condition is enough.