linkrs_query/optimizer/heuristic/join_optimization/
join_condition_simplify.rs

1//! Rules for simplifying JOIN conditions
2//!
3//! This rule simplifies JOIN conditions, including eliminating redundant conditions
4//! and converting InnerJoin with ON true to CrossJoin.
5//!
6//! # Conversion examples
7//!
8//! ## Eliminate redundant conditions
9//! Before:
10//! ```text
11//!   InnerJoin ON a.id = b.id AND b.id = a.id
12//! ```
13//!
14//! After:
15//! ```text
16//!   InnerJoin ON a.id = b.id
17//! ```
18//!
19//! ## Convert ON true to CrossJoin
20//! Before:
21//! ```text
22//!   InnerJoin ON true
23//! ```
24//!
25//! After:
26//! ```text
27//!   CrossJoin
28//! ```
29//!
30//! # Applicable Conditions
31//!
32//! JOIN conditions contain redundant expressions.
33//! JOIN condition is a constant true.
34//! JOIN conditions can be simplified.
35
36use crate::optimizer::heuristic::context::RewriteContext;
37use crate::optimizer::heuristic::pattern::Pattern;
38use crate::optimizer::heuristic::result::{RewriteError, RewriteResult, TransformResult};
39use crate::optimizer::heuristic::rule::RewriteRule;
40use crate::planning::plan::core::nodes::join::join_node::{CrossJoinNode, InnerJoinNode};
41use crate::planning::plan::PlanNodeEnum;
42use linkrs_core::{Expression, Value};
43
44/// Rules for simplifying JOIN conditions
45///
46/// Simplify JOIN conditions by removing redundant expressions and converting trivial conditions.
47#[derive(Debug)]
48pub struct JoinConditionSimplifyRule;
49
50impl JoinConditionSimplifyRule {
51    pub fn new() -> Self {
52        Self
53    }
54
55    fn is_true_expression(&self, expr: &Expression) -> bool {
56        matches!(expr, Expression::Literal(Value::Bool(true)))
57    }
58
59    fn apply_to_inner_join(&self, join: &InnerJoinNode) -> RewriteResult<Option<TransformResult>> {
60        let hash_keys = join.hash_keys();
61        let probe_keys = join.probe_keys();
62
63        if hash_keys.len() != probe_keys.len() || hash_keys.is_empty() {
64            return Ok(None);
65        }
66
67        let all_true = hash_keys.iter().all(|k| {
68            k.expression()
69                .map(|m| self.is_true_expression(m.inner()))
70                .unwrap_or(false)
71        }) && probe_keys.iter().all(|k| {
72            k.expression()
73                .map(|m| self.is_true_expression(m.inner()))
74                .unwrap_or(false)
75        });
76
77        if all_true {
78            let cross_join = CrossJoinNode::new(
79                join.left_input().clone(),
80                join.right_input().clone(),
81            )
82            .map_err(|e| {
83                RewriteError::rewrite_failed(format!("Failed to create CrossJoinNode: {:?}", e))
84            })?;
85
86            let mut result = TransformResult::new();
87            result.erase_curr = true;
88            result.add_new_node(PlanNodeEnum::CrossJoin(cross_join));
89            return Ok(Some(result));
90        }
91
92        Ok(None)
93    }
94}
95
96impl Default for JoinConditionSimplifyRule {
97    fn default() -> Self {
98        Self::new()
99    }
100}
101
102impl RewriteRule for JoinConditionSimplifyRule {
103    fn name(&self) -> &'static str {
104        "JoinConditionSimplifyRule"
105    }
106
107    fn pattern(&self) -> Pattern {
108        Pattern::multi(vec!["InnerJoin", "InnerJoin"])
109    }
110
111    fn apply(
112        &self,
113        _ctx: &mut RewriteContext,
114        node: &PlanNodeEnum,
115    ) -> RewriteResult<Option<TransformResult>> {
116        match node {
117            PlanNodeEnum::InnerJoin(join) => self.apply_to_inner_join(join),
118            _ => Ok(None),
119        }
120    }
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126
127    #[test]
128    fn test_rule_name() {
129        let rule = JoinConditionSimplifyRule::new();
130        assert_eq!(rule.name(), "JoinConditionSimplifyRule");
131    }
132
133    #[test]
134    fn test_rule_pattern() {
135        let rule = JoinConditionSimplifyRule::new();
136        let pattern = rule.pattern();
137        assert!(pattern.node.is_some());
138    }
139
140    #[test]
141    fn test_is_true_expression() {
142        let rule = JoinConditionSimplifyRule::new();
143        assert!(rule.is_true_expression(&Expression::bool(true)));
144        assert!(!rule.is_true_expression(&Expression::bool(false)));
145        assert!(!rule.is_true_expression(&Expression::int(1)));
146    }
147}
linkrs_query/optimizer/heuristic/join_optimization/join_condition_simplify.rs

linkrs_query/optimizer/heuristic/join_optimization/
join_condition_simplify.rs
