linkrs_query/optimizer/decision/
types.rs

1//! Optimize the definition of decision types
2//!
3//! Defining the intermediate representation that converts from the AST (Abstract Syntax Tree) to the physical execution plan – the basis for optimization decisions.
4//! These decisions are based on cost-optimized choices, but they do not include the specific structure of the plan tree.
5
6use std::time::Instant;
7
8/// The complete optimization decision
9#[derive(Debug, Clone, PartialEq)]
10pub struct OptimizationDecision {
11    /// Traverse the starting point and make a decision
12    pub traversal_start: TraversalStartDecision,
13    /// Index selection decision
14    pub index_selection: IndexSelectionDecision,
15    /// Decision on the order of connections
16    pub join_order: JoinOrderDecision,
17    /// Sequence of applicable rewriting rules
18    pub rewrite_rules: Vec<RewriteRuleId>,
19    /// Statistical information version for decision-making
20    pub stats_version: u64,
21    /// Index version used during decision-making
22    pub index_version: u64,
23    /// Decision Timestamp
24    pub created_at: Instant,
25}
26
27impl OptimizationDecision {
28    /// Create new optimization decisions
29    pub fn new(
30        traversal_start: TraversalStartDecision,
31        index_selection: IndexSelectionDecision,
32        join_order: JoinOrderDecision,
33        stats_version: u64,
34        index_version: u64,
35    ) -> Self {
36        Self {
37            traversal_start,
38            index_selection,
39            join_order,
40            rewrite_rules: Vec::new(),
41            stats_version,
42            index_version,
43            created_at: Instant::now(),
44        }
45    }
46
47    /// Check whether the decision is still valid.
48    pub fn is_valid(&self, current_stats_version: u64, current_index_version: u64) -> bool {
49        self.stats_version == current_stats_version && self.index_version == current_index_version
50    }
51
52    /// Obtain the decision-making age (in seconds)
53    pub fn age_secs(&self) -> u64 {
54        self.created_at.elapsed().as_secs()
55    }
56}
57
58/// Iterative Starting Point Selection Decision
59#[derive(Debug, Clone, PartialEq, Eq, Hash)]
60pub struct TraversalStartDecision {
61    /// Name of the starting node variable
62    pub start_variable: String,
63    /// Access path type
64    pub access_path: AccessPath,
65    /// Estimated selectivity (represented as an integer to avoid issues with floating-point precision)
66    pub estimated_selectivity_scaled: u64, // Actual value = This value / 1,000,000
67    /// Estimated cost (expressed as an integer)
68    pub estimated_cost_scaled: u64, // Actual value = This value / 1,000,000
69}
70
71impl TraversalStartDecision {
72    /// Making a decision to establish a new starting point for the traversal process
73    pub fn new(
74        start_variable: String,
75        access_path: AccessPath,
76        estimated_selectivity: f64,
77        estimated_cost: f64,
78    ) -> Self {
79        Self {
80            start_variable,
81            access_path,
82            estimated_selectivity_scaled: (estimated_selectivity * 1_000_000.0) as u64,
83            estimated_cost_scaled: (estimated_cost * 1_000_000.0) as u64,
84        }
85    }
86
87    /// Obtain an estimate of the selectivity
88    pub fn estimated_selectivity(&self) -> f64 {
89        self.estimated_selectivity_scaled as f64 / 1_000_000.0
90    }
91
92    /// Obtain the estimated cost
93    pub fn estimated_cost(&self) -> f64 {
94        self.estimated_cost_scaled as f64 / 1_000_000.0
95    }
96}
97
98/// Access Path Type
99#[derive(Debug, Clone, PartialEq, Eq, Hash)]
100pub enum AccessPath {
101    /// Explicit VID specification
102    ExplicitVid {
103        /// Description of the VID expression (simplified representation)
104        vid_description: String,
105    },
106    /// Index scan
107    IndexScan {
108        /// Index name
109        index_name: String,
110        /// Attribute name
111        property_name: String,
112        /// Predicate description
113        predicate_description: String,
114    },
115    /// Tag Index
116    TagIndex {
117        /// Tag name
118        tag_name: String,
119    },
120    /// Full table scan
121    FullScan {
122        /// Entity type
123        entity_type: EntityType,
124    },
125    /// Variable binding
126    VariableBinding {
127        /// Name of the source variable
128        source_variable: String,
129    },
130}
131
132/// Entity type
133#[derive(Debug, Clone, PartialEq, Eq, Hash)]
134pub enum EntityType {
135    /// vertex
136    Vertex {
137        /// Tag name (optional)
138        tag_name: Option<String>,
139    },
140    /// edge
141    Edge {
142        /// Edge type (optional)
143        edge_type: Option<String>,
144    },
145}
146
147/// Index Selection Decision
148#[derive(Debug, Clone, PartialEq, Eq, Hash)]
149pub struct IndexSelectionDecision {
150    /// Index selection for each entity type
151    pub entity_indexes: Vec<EntityIndexChoice>,
152}
153
154impl IndexSelectionDecision {
155    /// Create an empty index selection decision
156    pub fn empty() -> Self {
157        Self {
158            entity_indexes: Vec::new(),
159        }
160    }
161
162    /// Add entity index selection option
163    pub fn add_choice(&mut self, choice: EntityIndexChoice) {
164        self.entity_indexes.push(choice);
165    }
166}
167
168/// Entity index selection
169#[derive(Debug, Clone, PartialEq, Eq, Hash)]
170pub struct EntityIndexChoice {
171    /// Entity type (label or edge type)
172    pub entity_name: String,
173    /// Selected index
174    pub selected_index: IndexChoice,
175    /// Estimated selectiveivity (scaling values)
176    pub selectivity_scaled: u64,
177}
178
179impl EntityIndexChoice {
180    /// Option to create a new entity index
181    pub fn new(entity_name: String, selected_index: IndexChoice, selectivity: f64) -> Self {
182        Self {
183            entity_name,
184            selected_index,
185            selectivity_scaled: (selectivity * 1_000_000.0) as u64,
186        }
187    }
188
189    /// Obtain selectivity
190    pub fn selectivity(&self) -> f64 {
191        self.selectivity_scaled as f64 / 1_000_000.0
192    }
193}
194
195/// Index selection
196#[derive(Debug, Clone, PartialEq, Eq, Hash)]
197pub enum IndexChoice {
198    /// Primary key index
199    PrimaryKey,
200    /// Attribute index
201    PropertyIndex {
202        /// attribute name
203        property_name: String,
204        /// Index name
205        index_name: String,
206    },
207    /// Composite index
208    CompositeIndex {
209        /// List of attribute names
210        property_names: Vec<String>,
211        /// Index name
212        index_name: String,
213    },
214    /// No available index.
215    None,
216}
217
218/// Connection Sequential Decision Making
219#[derive(Debug, Clone, PartialEq, Eq, Hash)]
220pub struct JoinOrderDecision {
221    /// Connection order (sequence of variable names)
222    pub join_order: Vec<String>,
223    /// The choice of algorithm for each connection
224    pub join_algorithms: Vec<JoinAlgorithm>,
225}
226
227impl JoinOrderDecision {
228    /// Create an empty decision-making process for determining the order of connections.
229    pub fn empty() -> Self {
230        Self {
231            join_order: Vec::new(),
232            join_algorithms: Vec::new(),
233        }
234    }
235
236    /// Add the connection steps
237    pub fn add_join_step(&mut self, variable: String, algorithm: JoinAlgorithm) {
238        self.join_order.push(variable);
239        self.join_algorithms.push(algorithm);
240    }
241}
242
243/// Connection algorithms
244#[derive(Debug, Clone, PartialEq, Eq, Hash)]
245pub enum JoinAlgorithm {
246    /// Hash link
247    HashJoin {
248        /// Constructing the names for the side variables
249        build_side: String,
250        /// Variable name on the detection side
251        probe_side: String,
252    },
253    /// Nested loop connection
254    NestedLoopJoin {
255        /// Variable name for the appearance
256        outer: String,
257        /// Internal table variable name
258        inner: String,
259    },
260    /// Index join
261    IndexJoin {
262        /// Variable name on the side with the index
263        indexed_side: String,
264    },
265}
266
267/// Rewrite Rule ID
268#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
269pub enum RewriteRuleId {
270    /// Predicate Pushdown
271    PushFilterDown,
272    /// Projection pushdown
273    PushProjectDown,
274    /// LIMIT push-down
275    PushLimitDown,
276    /// Operation merge
277    MergeOperations,
278    /// Redundancy elimination
279    EliminateRedundancy,
280    /// Aggregation optimization
281    AggregateOptimization,
282}
283
284#[cfg(test)]
285mod tests {
286    use super::*;
287
288    #[test]
289    fn test_traversal_start_decision() {
290        let decision = TraversalStartDecision::new(
291            "n".to_string(),
292            AccessPath::TagIndex {
293                tag_name: "Person".to_string(),
294            },
295            0.1,
296            100.0,
297        );
298
299        assert_eq!(decision.start_variable, "n");
300        assert!((decision.estimated_selectivity() - 0.1).abs() < 0.0001);
301        assert!((decision.estimated_cost() - 100.0).abs() < 0.0001);
302    }
303
304    #[test]
305    fn test_optimization_decision_validity() {
306        let decision = OptimizationDecision::new(
307            TraversalStartDecision::new(
308                "n".to_string(),
309                AccessPath::FullScan {
310                    entity_type: EntityType::Vertex { tag_name: None },
311                },
312                1.0,
313                1000.0,
314            ),
315            IndexSelectionDecision::empty(),
316            JoinOrderDecision::empty(),
317            1,
318            1,
319        );
320
321        assert!(decision.is_valid(1, 1));
322        assert!(!decision.is_valid(2, 1));
323        assert!(!decision.is_valid(1, 2));
324    }
325}
linkrs_query/optimizer/decision/types.rs

linkrs_query/optimizer/decision/
types.rs
