linkrs_query/optimizer/heuristic/join_optimization/
left_join_to_inner_join.rs

1//! Rules for converting LeftJoin to InnerJoin
2//!
3//! When the right table column has a non-NULL filter condition, LeftJoin can be converted to InnerJoin.
4//! This optimization reduces unnecessary NULL row processing.
5//!
6//! # Conversion example
7//!
8//! Before:
9//! ```text
10//!   Filter(b.col IS NOT NULL)
11//!           |
12//!   LeftJoin(A, B)
13//! ```
14//!
15//! After:
16//! ```text
17//!   InnerJoin(A, B)
18//! ```
19//!
20//! # Applicable Conditions
21//!
22//! The LeftJoin node has a Filter node above it.
23//! The filter condition contains a non-NULL constraint on the right table column.
24//! The filter condition can be safely pushed down.
25
26use crate::optimizer::heuristic::context::RewriteContext;
27use crate::optimizer::heuristic::pattern::Pattern;
28use crate::optimizer::heuristic::result::{RewriteError, RewriteResult, TransformResult};
29use crate::optimizer::heuristic::rule::{PushDownRule, RewriteRule};
30use crate::planning::plan::core::nodes::base::plan_node_traits::SingleInputNode;
31use crate::planning::plan::core::nodes::join::join_node::{InnerJoinNode, LeftJoinNode};
32use crate::planning::plan::core::nodes::operation::filter_node::FilterNode;
33use crate::planning::plan::PlanNodeEnum;
34use linkrs_core::types::expr::contextual::ContextualExpression;
35use linkrs_core::types::operators::BinaryOperator;
36use linkrs_core::Expression;
37
38/// Rules for converting LeftJoin to InnerJoin
39///
40/// When the right table column has a non-NULL filter condition, convert LeftJoin to InnerJoin.
41#[derive(Debug)]
42pub struct LeftJoinToInnerJoinRule;
43
44impl LeftJoinToInnerJoinRule {
45    pub fn new() -> Self {
46        Self
47    }
48
49    fn check_is_not_null_condition(&self, expr: &Expression, right_col_names: &[String]) -> bool {
50        match expr {
51            Expression::Function { name, args } if name == "is_not_null" && args.len() == 1 => {
52                if let Expression::Variable(var_name) = args[0].as_expr() {
53                    right_col_names.contains(var_name)
54                } else {
55                    false
56                }
57            }
58            Expression::Binary { left, op, right } if *op == BinaryOperator::And => {
59                self.check_is_not_null_condition(left, right_col_names)
60                    || self.check_is_not_null_condition(right, right_col_names)
61            }
62            Expression::Binary { left, op, right } if *op == BinaryOperator::Or => {
63                self.check_is_not_null_condition(left, right_col_names)
64                    && self.check_is_not_null_condition(right, right_col_names)
65            }
66            Expression::Binary { left, op, right } => {
67                if *op == BinaryOperator::NotEqual {
68                    if let (
69                        Expression::Variable(var_name),
70                        Expression::Literal(linkrs_core::Value::Null(_)),
71                    ) = (left.as_ref(), right.as_ref())
72                    {
73                        return right_col_names.contains(var_name);
74                    }
75                    if let (
76                        Expression::Literal(linkrs_core::Value::Null(_)),
77                        Expression::Variable(var_name),
78                    ) = (left.as_ref(), right.as_ref())
79                    {
80                        return right_col_names.contains(var_name);
81                    }
82                }
83                false
84            }
85            _ => false,
86        }
87    }
88
89    fn has_not_null_on_right(
90        &self,
91        expr: &ContextualExpression,
92        right_col_names: &[String],
93    ) -> bool {
94        if let Some(expr_meta) = expr.expression() {
95            self.check_is_not_null_condition(expr_meta.inner(), right_col_names)
96        } else {
97            false
98        }
99    }
100
101    fn remove_not_null_conditions(
102        &self,
103        expr: &Expression,
104        right_col_names: &[String],
105    ) -> Option<Expression> {
106        match expr {
107            Expression::Function { name, args } if name == "is_not_null" && args.len() == 1 => {
108                if let Expression::Variable(var_name) = args[0].as_expr() {
109                    if right_col_names.contains(var_name) {
110                        return None;
111                    }
112                }
113                Some(expr.clone())
114            }
115            Expression::Binary { left, op, right } if *op == BinaryOperator::And => {
116                let left_result = self.remove_not_null_conditions(left, right_col_names);
117                let right_result = self.remove_not_null_conditions(right, right_col_names);
118                match (left_result, right_result) {
119                    (Some(l), Some(r)) => Some(Expression::and(l, r)),
120                    (Some(l), None) => Some(l),
121                    (None, Some(r)) => Some(r),
122                    (None, None) => None,
123                }
124            }
125            Expression::Binary { left, op, right } if *op == BinaryOperator::Or => {
126                let left_result = self.remove_not_null_conditions(left, right_col_names);
127                let right_result = self.remove_not_null_conditions(right, right_col_names);
128                match (left_result, right_result) {
129                    (Some(l), Some(r)) => Some(Expression::or(l, r)),
130                    (Some(l), None) => Some(l),
131                    (None, Some(r)) => Some(r),
132                    (None, None) => None,
133                }
134            }
135            Expression::Binary { left, op, right } => {
136                if *op == BinaryOperator::NotEqual {
137                    if let (
138                        Expression::Variable(var_name),
139                        Expression::Literal(linkrs_core::Value::Null(_)),
140                    ) = (left.as_ref(), right.as_ref())
141                    {
142                        if right_col_names.contains(var_name) {
143                            return None;
144                        }
145                    }
146                    if let (
147                        Expression::Literal(linkrs_core::Value::Null(_)),
148                        Expression::Variable(var_name),
149                    ) = (left.as_ref(), right.as_ref())
150                    {
151                        if right_col_names.contains(var_name) {
152                            return None;
153                        }
154                    }
155                }
156                Some(expr.clone())
157            }
158            _ => Some(expr.clone()),
159        }
160    }
161
162    fn apply_to_left_join(
163        &self,
164        filter: &FilterNode,
165        join: &LeftJoinNode,
166    ) -> RewriteResult<Option<TransformResult>> {
167        let right_col_names = join.right_input().col_names().to_vec();
168        let filter_condition = filter.condition();
169
170        if !self.has_not_null_on_right(filter_condition, &right_col_names) {
171            return Ok(None);
172        }
173
174        let new_join = InnerJoinNode::new(
175            join.left_input().clone(),
176            join.right_input().clone(),
177            join.hash_keys().to_vec(),
178            join.probe_keys().to_vec(),
179        )
180        .map_err(|e| {
181            RewriteError::rewrite_failed(format!("Failed to create InnerJoinNode: {:?}", e))
182        })?;
183
184        if let Some(expr_meta) = filter_condition.expression() {
185            let remaining = self.remove_not_null_conditions(expr_meta.inner(), &right_col_names);
186
187            let mut result = TransformResult::new();
188
189            if let Some(rem_expr) = remaining {
190                let ctx = filter_condition.context().clone();
191                let meta = linkrs_core::types::expr::ExpressionMeta::new(rem_expr);
192                let id = ctx.register_expression(meta);
193                let new_ctx_expr = ContextualExpression::new(id, ctx);
194
195                let new_filter = FilterNode::new(PlanNodeEnum::InnerJoin(new_join), new_ctx_expr)
196                    .map_err(|e| {
197                    RewriteError::rewrite_failed(format!("Failed to create FilterNode: {:?}", e))
198                })?;
199
200                result.erase_curr = true;
201                result.add_new_node(PlanNodeEnum::Filter(new_filter));
202            } else {
203                result.erase_curr = true;
204                result.add_new_node(PlanNodeEnum::InnerJoin(new_join));
205            }
206
207            return Ok(Some(result));
208        }
209
210        Ok(None)
211    }
212}
213
214impl Default for LeftJoinToInnerJoinRule {
215    fn default() -> Self {
216        Self::new()
217    }
218}
219
220impl RewriteRule for LeftJoinToInnerJoinRule {
221    fn name(&self) -> &'static str {
222        "LeftJoinToInnerJoinRule"
223    }
224
225    fn pattern(&self) -> Pattern {
226        Pattern::new_with_name("Filter")
227    }
228
229    fn apply(
230        &self,
231        _ctx: &mut RewriteContext,
232        node: &PlanNodeEnum,
233    ) -> RewriteResult<Option<TransformResult>> {
234        let filter = match node {
235            PlanNodeEnum::Filter(n) => n,
236            _ => return Ok(None),
237        };
238
239        let input = filter.input();
240
241        match input {
242            PlanNodeEnum::LeftJoin(join) => self.apply_to_left_join(filter, join),
243            _ => Ok(None),
244        }
245    }
246}
247
248impl PushDownRule for LeftJoinToInnerJoinRule {
249    fn can_push_down(&self, node: &PlanNodeEnum, target: &PlanNodeEnum) -> bool {
250        matches!(node, PlanNodeEnum::Filter(_)) && matches!(target, PlanNodeEnum::LeftJoin(_))
251    }
252
253    fn push_down(
254        &self,
255        ctx: &mut RewriteContext,
256        node: &PlanNodeEnum,
257        _target: &PlanNodeEnum,
258    ) -> RewriteResult<Option<TransformResult>> {
259        self.apply(ctx, node)
260    }
261}
262
263#[cfg(test)]
264mod tests {
265    use super::*;
266
267    #[test]
268    fn test_rule_name() {
269        let rule = LeftJoinToInnerJoinRule::new();
270        assert_eq!(rule.name(), "LeftJoinToInnerJoinRule");
271    }
272
273    #[test]
274    fn test_rule_pattern() {
275        let rule = LeftJoinToInnerJoinRule::new();
276        let pattern = rule.pattern();
277        assert!(pattern.node.is_some());
278    }
279
280    #[test]
281    fn test_check_is_not_null_condition() {
282        let rule = LeftJoinToInnerJoinRule::new();
283        let right_cols = vec!["b_col".to_string()];
284
285        let expr = Expression::function("is_not_null", vec![Expression::variable("b_col")]);
286        assert!(rule.check_is_not_null_condition(&expr, &right_cols));
287
288        let expr2 = Expression::function("is_not_null", vec![Expression::variable("a_col")]);
289        assert!(!rule.check_is_not_null_condition(&expr2, &right_cols));
290    }
291}
linkrs_query/optimizer/heuristic/join_optimization/left_join_to_inner_join.rs

linkrs_query/optimizer/heuristic/join_optimization/
left_join_to_inner_join.rs
