linkrs_query/optimizer/heuristic/join_optimization/
join_elimination.rs

1//! Rules for eliminating redundant JOIN operations
2//!
3//! This rule eliminates JOINs that don't contribute to the query result,
4//! such as JOINs with always-true conditions (CrossJoin with no filter)
5//! or JOINs where one side is a single-row constant table.
6//!
7//! # Conversion examples
8//!
9//! ## Case 1: JOIN with always-true condition
10//! Before:
11//! ```text
12//!   InnerJoin(ON true) → Left → Right
13//! ```
14//! After:
15//! ```text
16//!   CrossJoin → Left → Right
17//! ```
18//!
19//! ## Case 2: JOIN with self (redundant)
20//! Before:
21//! ```text
22//!   InnerJoin(ON a.id = a.id) → ScanVertices(a) → ScanVertices(a)
23//! ```
24//! After:
25//! ```text
26//!   ScanVertices(a)
27//! ```
28
29use crate::optimizer::heuristic::context::RewriteContext;
30use crate::optimizer::heuristic::pattern::Pattern;
31use crate::optimizer::heuristic::result::{RewriteResult, TransformResult};
32use crate::optimizer::heuristic::rule::RewriteRule;
33use crate::planning::plan::core::nodes::join::join_node::{
34    CrossJoinNode, InnerJoinNode, LeftJoinNode,
35};
36use crate::planning::plan::PlanNodeEnum;
37use linkrs_core::types::expr::contextual::ContextualExpression;
38
39/// Rules for eliminating redundant JOIN operations
40#[derive(Debug)]
41pub struct JoinEliminationRule;
42
43impl JoinEliminationRule {
44    pub fn new() -> Self {
45        Self
46    }
47
48    fn is_always_true_condition(
49        &self,
50        hash_keys: &[ContextualExpression],
51        probe_keys: &[ContextualExpression],
52    ) -> bool {
53        if hash_keys.is_empty() && probe_keys.is_empty() {
54            return true;
55        }
56        false
57    }
58
59    fn is_self_join(&self, left: &PlanNodeEnum, right: &PlanNodeEnum) -> bool {
60        match (left, right) {
61            (PlanNodeEnum::ScanVertices(l), PlanNodeEnum::ScanVertices(r)) => {
62                l.space_id() == r.space_id() && l.tag() == r.tag()
63            }
64            (PlanNodeEnum::ScanEdges(l), PlanNodeEnum::ScanEdges(r)) => {
65                l.space_id() == r.space_id() && l.edge_type() == r.edge_type()
66            }
67            _ => false,
68        }
69    }
70
71    fn apply_to_inner_join(&self, join: &InnerJoinNode) -> RewriteResult<Option<TransformResult>> {
72        let left = join.left_input();
73        let right = join.right_input();
74
75        if self.is_self_join(left, right) {
76            let mut result = TransformResult::new();
77            result.erase_curr = true;
78            result.add_new_node(left.clone());
79            return Ok(Some(result));
80        }
81
82        if self.is_always_true_condition(join.hash_keys(), join.probe_keys()) {
83            match CrossJoinNode::new(left.clone(), right.clone()) {
84                Ok(cross_join) => {
85                    let mut result = TransformResult::new();
86                    result.erase_curr = true;
87                    result.add_new_node(PlanNodeEnum::CrossJoin(cross_join));
88                    return Ok(Some(result));
89                }
90                Err(_) => return Ok(None),
91            }
92        }
93
94        Ok(None)
95    }
96
97    fn apply_to_left_join(&self, join: &LeftJoinNode) -> RewriteResult<Option<TransformResult>> {
98        let _left = join.left_input();
99        let _right = join.right_input();
100
101        Ok(None)
102    }
103}
104
105impl Default for JoinEliminationRule {
106    fn default() -> Self {
107        Self::new()
108    }
109}
110
111impl RewriteRule for JoinEliminationRule {
112    fn name(&self) -> &'static str {
113        "JoinEliminationRule"
114    }
115
116    fn pattern(&self) -> Pattern {
117        Pattern::new_with_name("Join")
118    }
119
120    fn apply(
121        &self,
122        _ctx: &mut RewriteContext,
123        node: &PlanNodeEnum,
124    ) -> RewriteResult<Option<TransformResult>> {
125        match node {
126            PlanNodeEnum::InnerJoin(join) => self.apply_to_inner_join(join),
127            PlanNodeEnum::LeftJoin(join) => self.apply_to_left_join(join),
128            _ => Ok(None),
129        }
130    }
131}
132
133#[cfg(test)]
134mod tests {
135    use super::*;
136
137    #[test]
138    fn test_rule_name() {
139        let rule = JoinEliminationRule::new();
140        assert_eq!(rule.name(), "JoinEliminationRule");
141    }
142
143    #[test]
144    fn test_rule_pattern() {
145        let rule = JoinEliminationRule::new();
146        let pattern = rule.pattern();
147        assert!(pattern.node.is_some());
148    }
149}
linkrs_query/optimizer/heuristic/join_optimization/join_elimination.rs

linkrs_query/optimizer/heuristic/join_optimization/
join_elimination.rs
