linkrs_query/planning/statements/paths/
match_path_planner.rs

1//! MATCH Route Planner
2//!
3//! Responsible for planning the path patterns in MATCH queries and generating the traversal plans.
4
5use crate::optimizer::cost::CostModelConfig;
6use crate::planning::statements::seeks::seek_strategy_base::{
7    NodePattern, SeekStrategyContext, SeekStrategySelector, SeekStrategyType,
8};
9use linkrs_core::types::graph_schema::EdgeDirection;
10use linkrs_core::{StorageError, Value};
11use std::sync::Arc;
12
13pub type PlannerError = StorageError;
14
15#[derive(Debug, Clone)]
16pub struct VariableLengthPathPattern<'a> {
17    pub start: &'a NodePattern,
18    pub edge: &'a EdgePattern,
19    pub end: &'a NodePattern,
20    pub lower: Option<usize>,
21    pub upper: Option<usize>,
22}
23
24#[derive(Debug)]
25pub struct MatchPathPlanner;
26
27impl Default for MatchPathPlanner {
28    fn default() -> Self {
29        Self::new()
30    }
31}
32
33impl MatchPathPlanner {
34    pub fn new() -> Self {
35        Self
36    }
37
38    pub fn plan_path_pattern(
39        &self,
40        pattern: &PathPattern,
41        space_id: u64,
42    ) -> Result<PathPlan, PlannerError> {
43        match &pattern.kind {
44            PathPatternKind::Simple { start, edge, end } => {
45                self.plan_simple_pattern(start, edge, end, space_id)
46            }
47            PathPatternKind::VariableLength {
48                start,
49                edge,
50                end,
51                lower,
52                upper,
53            } => {
54                let pattern = VariableLengthPathPattern {
55                    start,
56                    edge,
57                    end,
58                    lower: *lower,
59                    upper: *upper,
60                };
61                self.plan_variable_length_pattern(&pattern, space_id)
62            }
63            PathPatternKind::Named { name, inner } => {
64                let inner_plan = self.plan_path_pattern(inner, space_id)?;
65                Ok(PathPlan::Named {
66                    name: name.clone(),
67                    inner: Box::new(inner_plan),
68                })
69            }
70        }
71    }
72
73    fn plan_simple_pattern(
74        &self,
75        start: &NodePattern,
76        edge: &EdgePattern,
77        end: &NodePattern,
78        space_id: u64,
79    ) -> Result<PathPlan, PlannerError> {
80        let start_finder = self.plan_start_finder(start, space_id)?;
81        let edge_traversal = self.plan_edge_traversal(edge)?;
82        let end_finder = self.plan_end_finder(end)?;
83
84        Ok(PathPlan::Simple {
85            start: Box::new(start_finder),
86            edge: edge_traversal,
87            end: end_finder,
88        })
89    }
90
91    fn plan_variable_length_pattern(
92        &self,
93        pattern: &VariableLengthPathPattern,
94        space_id: u64,
95    ) -> Result<PathPlan, PlannerError> {
96        let start_finder = self.plan_start_finder(pattern.start, space_id)?;
97        let edge_types = self.extract_edge_types(pattern.edge)?;
98        let direction = self.extract_direction(pattern.edge)?;
99        let end_finder = self.plan_end_finder(pattern.end)?;
100
101        Ok(PathPlan::VariableLength {
102            start: Box::new(start_finder),
103            edge_types,
104            direction,
105            end: end_finder,
106            lower: pattern.lower,
107            upper: pattern.upper,
108        })
109    }
110
111    fn plan_start_finder(
112        &self,
113        pattern: &NodePattern,
114        space_id: u64,
115    ) -> Result<StartVidFinder, PlannerError> {
116        let context = SeekStrategyContext::new(space_id, pattern.clone(), vec![]);
117        let selector = SeekStrategySelector::new(CostModelConfig::default());
118        let strategy_type = selector.select_strategy(&context);
119
120        let finder = match strategy_type {
121            SeekStrategyType::VertexSeek => StartVidFinder::VertexSeek {
122                pattern: pattern.clone(),
123            },
124            SeekStrategyType::IndexSeek => StartVidFinder::IndexScan {
125                pattern: pattern.clone(),
126            },
127            SeekStrategyType::PropIndexSeek => StartVidFinder::PropIndexScan {
128                pattern: pattern.clone(),
129            },
130            SeekStrategyType::VariablePropIndexSeek => StartVidFinder::VariablePropIndexScan {
131                pattern: pattern.clone(),
132            },
133            SeekStrategyType::EdgeSeek => StartVidFinder::EdgeScan {
134                pattern: pattern.clone(),
135            },
136            SeekStrategyType::ScanSeek => StartVidFinder::FullScan {
137                pattern: pattern.clone(),
138            },
139        };
140
141        Ok(finder)
142    }
143
144    fn plan_end_finder(&self, pattern: &NodePattern) -> Result<EndCondition, PlannerError> {
145        Ok(EndCondition {
146            pattern: pattern.clone(),
147        })
148    }
149
150    fn plan_edge_traversal(&self, edge: &EdgePattern) -> Result<EdgeTraversal, PlannerError> {
151        let direction = self.extract_direction(edge)?;
152        let edge_types = self.extract_edge_types(edge)?;
153        let properties = edge.properties.clone();
154
155        Ok(EdgeTraversal {
156            direction,
157            edge_types,
158            properties,
159        })
160    }
161
162    fn extract_direction(&self, edge: &EdgePattern) -> Result<EdgeDirection, PlannerError> {
163        Ok(match edge.direction {
164            Some(ref dir) => *dir,
165            None => EdgeDirection::Both,
166        })
167    }
168
169    fn extract_edge_types(&self, edge: &EdgePattern) -> Result<Vec<String>, PlannerError> {
170        Ok(edge.types.clone().unwrap_or_default())
171    }
172}
173
174#[derive(Debug, Clone, PartialEq)]
175pub struct PathPattern {
176    pub kind: PathPatternKind,
177}
178
179#[derive(Debug, Clone, PartialEq)]
180pub enum PathPatternKind {
181    Simple {
182        start: NodePattern,
183        edge: EdgePattern,
184        end: NodePattern,
185    },
186    VariableLength {
187        start: NodePattern,
188        edge: EdgePattern,
189        end: NodePattern,
190        lower: Option<usize>,
191        upper: Option<usize>,
192    },
193    Named {
194        name: String,
195        inner: Box<PathPattern>,
196    },
197}
198
199#[derive(Debug, Clone, PartialEq)]
200pub struct EdgePattern {
201    pub types: Option<Vec<String>>,
202    pub direction: Option<EdgeDirection>,
203    pub properties: Vec<(Arc<str>, Value)>,
204}
205
206#[derive(Debug)]
207pub enum StartVidFinder {
208    VertexSeek { pattern: NodePattern },
209    IndexScan { pattern: NodePattern },
210    PropIndexScan { pattern: NodePattern },
211    VariablePropIndexScan { pattern: NodePattern },
212    EdgeScan { pattern: NodePattern },
213    FullScan { pattern: NodePattern },
214}
215
216#[derive(Debug, Clone, PartialEq)]
217pub struct EndCondition {
218    pub pattern: NodePattern,
219}
220
221#[derive(Debug)]
222pub enum PathPlan {
223    Simple {
224        start: Box<StartVidFinder>,
225        edge: EdgeTraversal,
226        end: EndCondition,
227    },
228    VariableLength {
229        start: Box<StartVidFinder>,
230        edge_types: Vec<String>,
231        direction: EdgeDirection,
232        end: EndCondition,
233        lower: Option<usize>,
234        upper: Option<usize>,
235    },
236    Named {
237        name: String,
238        inner: Box<PathPlan>,
239    },
240}
241
242#[derive(Debug)]
243pub struct EdgeTraversal {
244    pub direction: EdgeDirection,
245    pub edge_types: Vec<String>,
246    pub properties: Vec<(Arc<str>, Value)>,
247}
248
249impl PathPattern {
250    pub fn simple(start: NodePattern, edge: EdgePattern, end: NodePattern) -> Self {
251        Self {
252            kind: PathPatternKind::Simple { start, edge, end },
253        }
254    }
255
256    pub fn variable_length(
257        start: NodePattern,
258        edge: EdgePattern,
259        end: NodePattern,
260        lower: Option<usize>,
261        upper: Option<usize>,
262    ) -> Self {
263        Self {
264            kind: PathPatternKind::VariableLength {
265                start,
266                edge,
267                end,
268                lower,
269                upper,
270            },
271        }
272    }
273}
274
275#[cfg(test)]
276mod tests {
277    use super::*;
278
279    #[test]
280    fn test_match_path_planner_new() {
281        let _planner = MatchPathPlanner::new();
282        // If the test is successful and you have reached this point, it means that everything has gone as planned.
283    }
284
285    #[test]
286    fn test_path_pattern_simple() {
287        let _pattern = PathPattern::simple(
288            NodePattern {
289                vid: Some(Value::string("start")),
290                labels: vec![],
291                properties: vec![],
292            },
293            EdgePattern {
294                types: Some(vec!["follows".to_string()]),
295                direction: Some(EdgeDirection::Out),
296                properties: vec![],
297            },
298            NodePattern {
299                vid: Some(Value::string("end")),
300                labels: vec![],
301                properties: vec![],
302            },
303        );
304        // If the test is successful and you have reached this point, it means that everything has gone as planned.
305    }
306
307    #[test]
308    fn test_path_pattern_variable_length() {
309        let _pattern = PathPattern::variable_length(
310            NodePattern {
311                vid: None,
312                labels: vec!["person".to_string()],
313                properties: vec![],
314            },
315            EdgePattern {
316                types: Some(vec!["follows".to_string()]),
317                direction: Some(EdgeDirection::Out),
318                properties: vec![],
319            },
320            NodePattern {
321                vid: None,
322                labels: vec!["person".to_string()],
323                properties: vec![],
324            },
325            Some(1),
326            Some(5),
327        );
328        // If the test is successful and you have reached this point, it means that everything has gone well.
329    }
330}
linkrs_query/planning/statements/paths/match_path_planner.rs

linkrs_query/planning/statements/paths/
match_path_planner.rs
