cypherlite_query/planner/
optimize.rs

1// Rule-based optimization: index scan selection, limit pushdown, constant folding,
2// projection pruning.
3
4use super::LogicalPlan;
5use crate::parser::ast::*;
6
7/// Apply optimization rules to a logical plan.
8///
9/// Rules are applied bottom-up (children optimized first):
10/// 1. Index scan selection: Filter(NodeScan) -> IndexScan when applicable
11/// 2. Limit pushdown: Limit(NodeScan) -> NodeScan with limit annotation
12/// 3. Constant folding: simplify constant expressions
13/// 4. Projection pruning: merge consecutive Projects
14pub fn optimize(plan: LogicalPlan) -> LogicalPlan {
15    apply_rules(plan)
16}
17
18/// Recursively apply optimization rules bottom-up.
19fn apply_rules(plan: LogicalPlan) -> LogicalPlan {
20    // First, recursively optimize children
21    let plan = optimize_children(plan);
22    // Then apply rules at the current node
23    let plan = push_index_scan(plan);
24    let plan = push_limit_down(plan);
25    let plan = fold_constants_in_plan(plan);
26    prune_projections(plan)
27}
28
29/// Recursively optimize child plans.
30fn optimize_children(plan: LogicalPlan) -> LogicalPlan {
31    match plan {
32        LogicalPlan::Filter { source, predicate } => LogicalPlan::Filter {
33            source: Box::new(apply_rules(*source)),
34            predicate,
35        },
36        LogicalPlan::Project {
37            source,
38            items,
39            distinct,
40        } => LogicalPlan::Project {
41            source: Box::new(apply_rules(*source)),
42            items,
43            distinct,
44        },
45        LogicalPlan::Sort { source, items } => LogicalPlan::Sort {
46            source: Box::new(apply_rules(*source)),
47            items,
48        },
49        LogicalPlan::Skip { source, count } => LogicalPlan::Skip {
50            source: Box::new(apply_rules(*source)),
51            count,
52        },
53        LogicalPlan::Limit { source, count } => LogicalPlan::Limit {
54            source: Box::new(apply_rules(*source)),
55            count,
56        },
57        LogicalPlan::Aggregate {
58            source,
59            group_keys,
60            aggregates,
61        } => LogicalPlan::Aggregate {
62            source: Box::new(apply_rules(*source)),
63            group_keys,
64            aggregates,
65        },
66        LogicalPlan::Expand {
67            source,
68            src_var,
69            rel_var,
70            target_var,
71            rel_type_id,
72            direction,
73            temporal_filter,
74        } => LogicalPlan::Expand {
75            source: Box::new(apply_rules(*source)),
76            src_var,
77            rel_var,
78            target_var,
79            rel_type_id,
80            direction,
81            temporal_filter,
82        },
83        LogicalPlan::CreateOp { source, pattern } => LogicalPlan::CreateOp {
84            source: source.map(|s| Box::new(apply_rules(*s))),
85            pattern,
86        },
87        LogicalPlan::DeleteOp {
88            source,
89            exprs,
90            detach,
91        } => LogicalPlan::DeleteOp {
92            source: Box::new(apply_rules(*source)),
93            exprs,
94            detach,
95        },
96        LogicalPlan::SetOp { source, items } => LogicalPlan::SetOp {
97            source: Box::new(apply_rules(*source)),
98            items,
99        },
100        LogicalPlan::RemoveOp { source, items } => LogicalPlan::RemoveOp {
101            source: Box::new(apply_rules(*source)),
102            items,
103        },
104        LogicalPlan::With {
105            source,
106            items,
107            where_clause,
108            distinct,
109        } => LogicalPlan::With {
110            source: Box::new(apply_rules(*source)),
111            items,
112            where_clause,
113            distinct,
114        },
115        LogicalPlan::Unwind {
116            source,
117            expr,
118            variable,
119        } => LogicalPlan::Unwind {
120            source: Box::new(apply_rules(*source)),
121            expr,
122            variable,
123        },
124        LogicalPlan::MergeOp {
125            source,
126            pattern,
127            on_match,
128            on_create,
129        } => LogicalPlan::MergeOp {
130            source: source.map(|s| Box::new(apply_rules(*s))),
131            pattern,
132            on_match,
133            on_create,
134        },
135        LogicalPlan::VarLengthExpand {
136            source,
137            src_var,
138            rel_var,
139            target_var,
140            rel_type_id,
141            direction,
142            min_hops,
143            max_hops,
144            temporal_filter,
145        } => LogicalPlan::VarLengthExpand {
146            source: Box::new(apply_rules(*source)),
147            src_var,
148            rel_var,
149            target_var,
150            rel_type_id,
151            direction,
152            min_hops,
153            max_hops,
154            temporal_filter,
155        },
156        LogicalPlan::OptionalExpand {
157            source,
158            src_var,
159            rel_var,
160            target_var,
161            rel_type_id,
162            direction,
163        } => LogicalPlan::OptionalExpand {
164            source: Box::new(apply_rules(*source)),
165            src_var,
166            rel_var,
167            target_var,
168            rel_type_id,
169            direction,
170        },
171        LogicalPlan::AsOfScan {
172            source,
173            timestamp_expr,
174        } => LogicalPlan::AsOfScan {
175            source: Box::new(apply_rules(*source)),
176            timestamp_expr,
177        },
178        LogicalPlan::TemporalRangeScan {
179            source,
180            start_expr,
181            end_expr,
182        } => LogicalPlan::TemporalRangeScan {
183            source: Box::new(apply_rules(*source)),
184            start_expr,
185            end_expr,
186        },
187        // Leaf nodes: no children to optimize
188        plan @ LogicalPlan::NodeScan { .. }
189        | plan @ LogicalPlan::IndexScan { .. }
190        | plan @ LogicalPlan::EmptySource
191        | plan @ LogicalPlan::CreateIndex { .. }
192        | plan @ LogicalPlan::CreateEdgeIndex { .. }
193        | plan @ LogicalPlan::DropIndex { .. } => plan,
194        #[cfg(feature = "subgraph")]
195        plan @ LogicalPlan::SubgraphScan { .. } => plan,
196        #[cfg(feature = "hypergraph")]
197        plan @ LogicalPlan::HyperEdgeScan { .. } => plan,
198        #[cfg(feature = "hypergraph")]
199        LogicalPlan::CreateHyperedgeOp {
200            source,
201            variable,
202            labels,
203            sources,
204            targets,
205        } => LogicalPlan::CreateHyperedgeOp {
206            source: source.map(|s| Box::new(apply_rules(*s))),
207            variable,
208            labels,
209            sources,
210            targets,
211        },
212        #[cfg(feature = "subgraph")]
213        LogicalPlan::CreateSnapshotOp {
214            variable,
215            labels,
216            properties,
217            temporal_anchor,
218            sub_plan,
219            return_vars,
220        } => LogicalPlan::CreateSnapshotOp {
221            variable,
222            labels,
223            properties,
224            temporal_anchor,
225            sub_plan: Box::new(apply_rules(*sub_plan)),
226            return_vars,
227        },
228    }
229}
230
231// ============================================================================
232// TASK-112: Index scan selection
233// ============================================================================
234
235/// Transform Filter(NodeScan { variable, label_id: Some(lid) }, predicate)
236/// into IndexScan when the predicate matches `variable.prop == literal`.
237fn push_index_scan(plan: LogicalPlan) -> LogicalPlan {
238    match plan {
239        LogicalPlan::Filter { source, predicate } => {
240            if let LogicalPlan::NodeScan {
241                ref variable,
242                label_id: Some(lid),
243                ..
244            } = *source
245            {
246                match try_extract_index_predicate(&predicate, variable) {
247                    Some((prop_key, lookup_value, remaining)) => {
248                        let index_scan = LogicalPlan::IndexScan {
249                            variable: variable.clone(),
250                            label_id: lid,
251                            prop_key,
252                            lookup_value,
253                        };
254                        match remaining {
255                            Some(rest) => LogicalPlan::Filter {
256                                source: Box::new(index_scan),
257                                predicate: rest,
258                            },
259                            None => index_scan,
260                        }
261                    }
262                    None => LogicalPlan::Filter { source, predicate },
263                }
264            } else {
265                LogicalPlan::Filter { source, predicate }
266            }
267        }
268        other => other,
269    }
270}
271
272/// Try to extract an index-suitable predicate from an expression.
273///
274/// Returns (prop_key, lookup_value, remaining_predicate) if found.
275/// The remaining_predicate is Some if there were additional AND conditions.
276fn try_extract_index_predicate(
277    expr: &Expression,
278    variable: &str,
279) -> Option<(String, Expression, Option<Expression>)> {
280    // Check for direct equality: variable.prop == literal or literal == variable.prop
281    if let Some((prop, val)) = try_extract_eq_predicate(expr, variable) {
282        return Some((prop, val, None));
283    }
284
285    // Check for AND expressions: try to extract one index predicate from conjuncts
286    if let Expression::BinaryOp(BinaryOp::And, left, right) = expr {
287        // Try left side
288        if let Some((prop, val)) = try_extract_eq_predicate(left, variable) {
289            return Some((prop, val, Some(*right.clone())));
290        }
291        // Try right side
292        if let Some((prop, val)) = try_extract_eq_predicate(right, variable) {
293            return Some((prop, val, Some(*left.clone())));
294        }
295    }
296
297    None
298}
299
300/// Try to match `variable.property == literal_value` or `literal_value == variable.property`.
301fn try_extract_eq_predicate(expr: &Expression, variable: &str) -> Option<(String, Expression)> {
302    if let Expression::BinaryOp(BinaryOp::Eq, left, right) = expr {
303        // Case 1: variable.property == literal
304        if let Some((prop, val)) = match_property_eq_literal(left, right, variable) {
305            return Some((prop, val));
306        }
307        // Case 2: literal == variable.property (reversed)
308        if let Some((prop, val)) = match_property_eq_literal(right, left, variable) {
309            return Some((prop, val));
310        }
311    }
312    None
313}
314
315/// Check if prop_side is `variable.property` and val_side is a literal.
316fn match_property_eq_literal(
317    prop_side: &Expression,
318    val_side: &Expression,
319    variable: &str,
320) -> Option<(String, Expression)> {
321    if let Expression::Property(var_expr, prop_name) = prop_side {
322        if let Expression::Variable(var_name) = var_expr.as_ref() {
323            if var_name == variable && is_literal(val_side) {
324                return Some((prop_name.clone(), val_side.clone()));
325            }
326        }
327    }
328    None
329}
330
331/// Check if an expression is a literal value (suitable for index lookup).
332fn is_literal(expr: &Expression) -> bool {
333    matches!(expr, Expression::Literal(_))
334}
335
336// ============================================================================
337// TASK-114: LIMIT pushdown
338// ============================================================================
339
340/// Push LIMIT into NodeScan when the source is a simple NodeScan (no Sort in between).
341/// Pattern: Limit(NodeScan { variable, label_id, limit: None }, count)
342///       -> NodeScan { variable, label_id, limit: Some(count) }
343///
344/// Does NOT push limit through Sort (sort needs all data).
345fn push_limit_down(plan: LogicalPlan) -> LogicalPlan {
346    match plan {
347        LogicalPlan::Limit { source, count } => {
348            if let Some(limit_val) = try_eval_limit_count(&count) {
349                match *source {
350                    LogicalPlan::NodeScan {
351                        variable,
352                        label_id,
353                        limit: existing_limit,
354                    } => {
355                        // Merge limits: take the smaller one
356                        let new_limit = match existing_limit {
357                            Some(existing) => Some(existing.min(limit_val)),
358                            None => Some(limit_val),
359                        };
360                        return LogicalPlan::NodeScan {
361                            variable,
362                            label_id,
363                            limit: new_limit,
364                        };
365                    }
366                    // Don't push through Sort (needs all data for sorting)
367                    other => {
368                        return LogicalPlan::Limit {
369                            source: Box::new(other),
370                            count,
371                        };
372                    }
373                }
374            }
375            LogicalPlan::Limit { source, count }
376        }
377        other => other,
378    }
379}
380
381/// Try to evaluate a LIMIT count expression at optimization time.
382/// Only works for literal integers.
383fn try_eval_limit_count(expr: &Expression) -> Option<usize> {
384    if let Expression::Literal(Literal::Integer(n)) = expr {
385        if *n >= 0 {
386            return Some(*n as usize);
387        }
388    }
389    None
390}
391
392// ============================================================================
393// TASK-115: Constant folding
394// ============================================================================
395
396/// Fold constant expressions in a plan node's expressions.
397fn fold_constants_in_plan(plan: LogicalPlan) -> LogicalPlan {
398    match plan {
399        LogicalPlan::Filter { source, predicate } => {
400            let folded = fold_expr(predicate);
401            // If predicate folds to true, eliminate the filter entirely
402            if folded == Expression::Literal(Literal::Bool(true)) {
403                return *source;
404            }
405            LogicalPlan::Filter {
406                source,
407                predicate: folded,
408            }
409        }
410        LogicalPlan::Project {
411            source,
412            items,
413            distinct,
414        } => {
415            let items = items
416                .into_iter()
417                .map(|item| ReturnItem {
418                    expr: fold_expr(item.expr),
419                    alias: item.alias,
420                })
421                .collect();
422            LogicalPlan::Project {
423                source,
424                items,
425                distinct,
426            }
427        }
428        LogicalPlan::Sort { source, items } => {
429            let items = items
430                .into_iter()
431                .map(|item| OrderItem {
432                    expr: fold_expr(item.expr),
433                    ascending: item.ascending,
434                })
435                .collect();
436            LogicalPlan::Sort { source, items }
437        }
438        other => other,
439    }
440}
441
442/// Recursively fold constant sub-expressions.
443fn fold_expr(expr: Expression) -> Expression {
444    match expr {
445        Expression::BinaryOp(op, left, right) => {
446            let left = fold_expr(*left);
447            let right = fold_expr(*right);
448            fold_binary_op(op, left, right)
449        }
450        Expression::UnaryOp(op, inner) => {
451            let inner = fold_expr(*inner);
452            fold_unary_op(op, inner)
453        }
454        other => other,
455    }
456}
457
458/// Fold a binary operation if both sides are literals.
459fn fold_binary_op(op: BinaryOp, left: Expression, right: Expression) -> Expression {
460    match (&left, &right) {
461        // Arithmetic: Int op Int -> Int
462        (Expression::Literal(Literal::Integer(a)), Expression::Literal(Literal::Integer(b))) => {
463            match op {
464                BinaryOp::Add => return Expression::Literal(Literal::Integer(a + b)),
465                BinaryOp::Sub => return Expression::Literal(Literal::Integer(a - b)),
466                BinaryOp::Mul => return Expression::Literal(Literal::Integer(a * b)),
467                BinaryOp::Div => {
468                    if *b != 0 {
469                        return Expression::Literal(Literal::Integer(a / b));
470                    }
471                }
472                BinaryOp::Mod => {
473                    if *b != 0 {
474                        return Expression::Literal(Literal::Integer(a % b));
475                    }
476                }
477                _ => {}
478            }
479        }
480        // Arithmetic: Float op Float -> Float
481        (Expression::Literal(Literal::Float(a)), Expression::Literal(Literal::Float(b))) => {
482            match op {
483                BinaryOp::Add => return Expression::Literal(Literal::Float(a + b)),
484                BinaryOp::Sub => return Expression::Literal(Literal::Float(a - b)),
485                BinaryOp::Mul => return Expression::Literal(Literal::Float(a * b)),
486                BinaryOp::Div => {
487                    if *b != 0.0 {
488                        return Expression::Literal(Literal::Float(a / b));
489                    }
490                }
491                _ => {}
492            }
493        }
494        _ => {}
495    }
496
497    // Boolean short-circuit folding: AND / OR with known operands
498    match op {
499        BinaryOp::And => {
500            // false AND x -> false
501            if left == Expression::Literal(Literal::Bool(false)) {
502                return Expression::Literal(Literal::Bool(false));
503            }
504            // x AND false -> false
505            if right == Expression::Literal(Literal::Bool(false)) {
506                return Expression::Literal(Literal::Bool(false));
507            }
508            // true AND x -> x
509            if left == Expression::Literal(Literal::Bool(true)) {
510                return right;
511            }
512            // x AND true -> x
513            if right == Expression::Literal(Literal::Bool(true)) {
514                return left;
515            }
516        }
517        BinaryOp::Or => {
518            // true OR x -> true
519            if left == Expression::Literal(Literal::Bool(true)) {
520                return Expression::Literal(Literal::Bool(true));
521            }
522            // x OR true -> true
523            if right == Expression::Literal(Literal::Bool(true)) {
524                return Expression::Literal(Literal::Bool(true));
525            }
526            // false OR x -> x
527            if left == Expression::Literal(Literal::Bool(false)) {
528                return right;
529            }
530            // x OR false -> x
531            if right == Expression::Literal(Literal::Bool(false)) {
532                return left;
533            }
534        }
535        _ => {}
536    }
537
538    Expression::BinaryOp(op, Box::new(left), Box::new(right))
539}
540
541/// Fold a unary operation if the operand is a literal.
542fn fold_unary_op(op: UnaryOp, inner: Expression) -> Expression {
543    match (&op, &inner) {
544        (UnaryOp::Not, Expression::Literal(Literal::Bool(b))) => {
545            Expression::Literal(Literal::Bool(!b))
546        }
547        (UnaryOp::Neg, Expression::Literal(Literal::Integer(n))) => {
548            Expression::Literal(Literal::Integer(-n))
549        }
550        (UnaryOp::Neg, Expression::Literal(Literal::Float(f))) => {
551            Expression::Literal(Literal::Float(-f))
552        }
553        _ => Expression::UnaryOp(op, Box::new(inner)),
554    }
555}
556
557// ============================================================================
558// TASK-116: Projection pruning
559// ============================================================================
560
561/// Merge consecutive Project nodes into a single Project.
562fn prune_projections(plan: LogicalPlan) -> LogicalPlan {
563    match plan {
564        LogicalPlan::Project {
565            source,
566            items: outer_items,
567            distinct: outer_distinct,
568        } => {
569            if let LogicalPlan::Project {
570                source: inner_source,
571                items: _inner_items,
572                distinct: _inner_distinct,
573            } = *source
574            {
575                // Merge: the outer projection determines the final columns.
576                // The inner projection is redundant if the outer one re-selects.
577                LogicalPlan::Project {
578                    source: inner_source,
579                    items: outer_items,
580                    distinct: outer_distinct,
581                }
582            } else {
583                LogicalPlan::Project {
584                    source,
585                    items: outer_items,
586                    distinct: outer_distinct,
587                }
588            }
589        }
590        other => other,
591    }
592}
593
594#[cfg(test)]
595mod tests {
596    use super::*;
597
598    // ========================================================================
599    // TASK-112: Index scan selection tests
600    // ========================================================================
601
602    #[test]
603    fn test_index_scan_simple_eq() {
604        // Filter(NodeScan(n, label=1), n.name == 'Alice')
605        // -> IndexScan(n, label=1, prop_key='name', lookup='Alice')
606        let plan = LogicalPlan::Filter {
607            source: Box::new(LogicalPlan::NodeScan {
608                variable: "n".into(),
609                label_id: Some(1),
610                limit: None,
611            }),
612            predicate: Expression::BinaryOp(
613                BinaryOp::Eq,
614                Box::new(Expression::Property(
615                    Box::new(Expression::Variable("n".into())),
616                    "name".into(),
617                )),
618                Box::new(Expression::Literal(Literal::String("Alice".into()))),
619            ),
620        };
621
622        let optimized = optimize(plan);
623        assert_eq!(
624            optimized,
625            LogicalPlan::IndexScan {
626                variable: "n".into(),
627                label_id: 1,
628                prop_key: "name".into(),
629                lookup_value: Expression::Literal(Literal::String("Alice".into())),
630            }
631        );
632    }
633
634    #[test]
635    fn test_index_scan_reversed_eq() {
636        // Filter(NodeScan(n, label=1), 'Alice' == n.name)
637        // -> IndexScan(n, label=1, prop_key='name', lookup='Alice')
638        let plan = LogicalPlan::Filter {
639            source: Box::new(LogicalPlan::NodeScan {
640                variable: "n".into(),
641                label_id: Some(1),
642                limit: None,
643            }),
644            predicate: Expression::BinaryOp(
645                BinaryOp::Eq,
646                Box::new(Expression::Literal(Literal::String("Alice".into()))),
647                Box::new(Expression::Property(
648                    Box::new(Expression::Variable("n".into())),
649                    "name".into(),
650                )),
651            ),
652        };
653
654        let optimized = optimize(plan);
655        assert_eq!(
656            optimized,
657            LogicalPlan::IndexScan {
658                variable: "n".into(),
659                label_id: 1,
660                prop_key: "name".into(),
661                lookup_value: Expression::Literal(Literal::String("Alice".into())),
662            }
663        );
664    }
665
666    #[test]
667    fn test_index_scan_integer_literal() {
668        // Filter(NodeScan(n, label=2), n.age == 30)
669        let plan = LogicalPlan::Filter {
670            source: Box::new(LogicalPlan::NodeScan {
671                variable: "n".into(),
672                label_id: Some(2),
673                limit: None,
674            }),
675            predicate: Expression::BinaryOp(
676                BinaryOp::Eq,
677                Box::new(Expression::Property(
678                    Box::new(Expression::Variable("n".into())),
679                    "age".into(),
680                )),
681                Box::new(Expression::Literal(Literal::Integer(30))),
682            ),
683        };
684
685        let optimized = optimize(plan);
686        assert_eq!(
687            optimized,
688            LogicalPlan::IndexScan {
689                variable: "n".into(),
690                label_id: 2,
691                prop_key: "age".into(),
692                lookup_value: Expression::Literal(Literal::Integer(30)),
693            }
694        );
695    }
696
697    #[test]
698    fn test_index_scan_no_label() {
699        // Filter(NodeScan(n, label=None), n.name == 'Alice')
700        // -> NOT converted (no label_id)
701        let plan = LogicalPlan::Filter {
702            source: Box::new(LogicalPlan::NodeScan {
703                variable: "n".into(),
704                label_id: None,
705                limit: None,
706            }),
707            predicate: Expression::BinaryOp(
708                BinaryOp::Eq,
709                Box::new(Expression::Property(
710                    Box::new(Expression::Variable("n".into())),
711                    "name".into(),
712                )),
713                Box::new(Expression::Literal(Literal::String("Alice".into()))),
714            ),
715        };
716
717        let optimized = optimize(plan);
718        // Should remain a Filter over NodeScan
719        assert!(matches!(optimized, LogicalPlan::Filter { .. }));
720    }
721
722    #[test]
723    fn test_index_scan_non_eq_predicate() {
724        // Filter(NodeScan(n, label=1), n.age > 30)
725        // -> NOT converted (not an equality predicate)
726        let plan = LogicalPlan::Filter {
727            source: Box::new(LogicalPlan::NodeScan {
728                variable: "n".into(),
729                label_id: Some(1),
730                limit: None,
731            }),
732            predicate: Expression::BinaryOp(
733                BinaryOp::Gt,
734                Box::new(Expression::Property(
735                    Box::new(Expression::Variable("n".into())),
736                    "age".into(),
737                )),
738                Box::new(Expression::Literal(Literal::Integer(30))),
739            ),
740        };
741
742        let optimized = optimize(plan);
743        assert!(matches!(optimized, LogicalPlan::Filter { .. }));
744    }
745
746    #[test]
747    fn test_index_scan_wrong_variable() {
748        // Filter(NodeScan(n, label=1), m.name == 'Alice')
749        // -> NOT converted (variable doesn't match)
750        let plan = LogicalPlan::Filter {
751            source: Box::new(LogicalPlan::NodeScan {
752                variable: "n".into(),
753                label_id: Some(1),
754                limit: None,
755            }),
756            predicate: Expression::BinaryOp(
757                BinaryOp::Eq,
758                Box::new(Expression::Property(
759                    Box::new(Expression::Variable("m".into())),
760                    "name".into(),
761                )),
762                Box::new(Expression::Literal(Literal::String("Alice".into()))),
763            ),
764        };
765
766        let optimized = optimize(plan);
767        assert!(matches!(optimized, LogicalPlan::Filter { .. }));
768    }
769
770    #[test]
771    fn test_index_scan_non_literal_value() {
772        // Filter(NodeScan(n, label=1), n.name == m.name)
773        // -> NOT converted (RHS is not a literal)
774        let plan = LogicalPlan::Filter {
775            source: Box::new(LogicalPlan::NodeScan {
776                variable: "n".into(),
777                label_id: Some(1),
778                limit: None,
779            }),
780            predicate: Expression::BinaryOp(
781                BinaryOp::Eq,
782                Box::new(Expression::Property(
783                    Box::new(Expression::Variable("n".into())),
784                    "name".into(),
785                )),
786                Box::new(Expression::Property(
787                    Box::new(Expression::Variable("m".into())),
788                    "name".into(),
789                )),
790            ),
791        };
792
793        let optimized = optimize(plan);
794        assert!(matches!(optimized, LogicalPlan::Filter { .. }));
795    }
796
797    #[test]
798    fn test_index_scan_and_predicate_extracts_one() {
799        // Filter(NodeScan(n, label=1), n.name == 'Alice' AND n.age > 25)
800        // -> Filter(IndexScan(n, name='Alice'), n.age > 25)
801        let plan = LogicalPlan::Filter {
802            source: Box::new(LogicalPlan::NodeScan {
803                variable: "n".into(),
804                label_id: Some(1),
805                limit: None,
806            }),
807            predicate: Expression::BinaryOp(
808                BinaryOp::And,
809                Box::new(Expression::BinaryOp(
810                    BinaryOp::Eq,
811                    Box::new(Expression::Property(
812                        Box::new(Expression::Variable("n".into())),
813                        "name".into(),
814                    )),
815                    Box::new(Expression::Literal(Literal::String("Alice".into()))),
816                )),
817                Box::new(Expression::BinaryOp(
818                    BinaryOp::Gt,
819                    Box::new(Expression::Property(
820                        Box::new(Expression::Variable("n".into())),
821                        "age".into(),
822                    )),
823                    Box::new(Expression::Literal(Literal::Integer(25))),
824                )),
825            ),
826        };
827
828        let optimized = optimize(plan);
829        match optimized {
830            LogicalPlan::Filter {
831                source, predicate, ..
832            } => {
833                assert!(matches!(*source, LogicalPlan::IndexScan { .. }));
834                // Remaining predicate should be n.age > 25
835                assert!(matches!(predicate, Expression::BinaryOp(BinaryOp::Gt, ..)));
836            }
837            _ => panic!("expected Filter(IndexScan, ...)"),
838        }
839    }
840
841    #[test]
842    fn test_index_scan_and_reversed_extracts_right() {
843        // Filter(NodeScan(n, label=1), n.age > 25 AND n.name == 'Bob')
844        // -> Filter(IndexScan(n, name='Bob'), n.age > 25)
845        let plan = LogicalPlan::Filter {
846            source: Box::new(LogicalPlan::NodeScan {
847                variable: "n".into(),
848                label_id: Some(1),
849                limit: None,
850            }),
851            predicate: Expression::BinaryOp(
852                BinaryOp::And,
853                Box::new(Expression::BinaryOp(
854                    BinaryOp::Gt,
855                    Box::new(Expression::Property(
856                        Box::new(Expression::Variable("n".into())),
857                        "age".into(),
858                    )),
859                    Box::new(Expression::Literal(Literal::Integer(25))),
860                )),
861                Box::new(Expression::BinaryOp(
862                    BinaryOp::Eq,
863                    Box::new(Expression::Property(
864                        Box::new(Expression::Variable("n".into())),
865                        "name".into(),
866                    )),
867                    Box::new(Expression::Literal(Literal::String("Bob".into()))),
868                )),
869            ),
870        };
871
872        let optimized = optimize(plan);
873        match optimized {
874            LogicalPlan::Filter { source, .. } => {
875                assert!(matches!(*source, LogicalPlan::IndexScan { .. }));
876            }
877            _ => panic!("expected Filter(IndexScan, ...)"),
878        }
879    }
880
881    #[test]
882    fn test_index_scan_source_not_nodescan() {
883        // Filter(Expand(...), n.name == 'Alice')
884        // -> NOT converted (source is not NodeScan)
885        let plan = LogicalPlan::Filter {
886            source: Box::new(LogicalPlan::Expand {
887                source: Box::new(LogicalPlan::NodeScan {
888                    variable: "m".into(),
889                    label_id: Some(1),
890                    limit: None,
891                }),
892                src_var: "m".into(),
893                rel_var: None,
894                target_var: "n".into(),
895                rel_type_id: None,
896                direction: RelDirection::Outgoing,
897                temporal_filter: None,
898            }),
899            predicate: Expression::BinaryOp(
900                BinaryOp::Eq,
901                Box::new(Expression::Property(
902                    Box::new(Expression::Variable("n".into())),
903                    "name".into(),
904                )),
905                Box::new(Expression::Literal(Literal::String("Alice".into()))),
906            ),
907        };
908
909        let optimized = optimize(plan);
910        assert!(matches!(optimized, LogicalPlan::Filter { .. }));
911    }
912
913    // ========================================================================
914    // ========================================================================
915    // TASK-114: LIMIT pushdown tests
916    // ========================================================================
917
918    #[test]
919    fn test_limit_pushdown_into_nodescan() {
920        // Limit(NodeScan(n, label=1), 5) -> NodeScan(n, label=1, limit=5)
921        let plan = LogicalPlan::Limit {
922            source: Box::new(LogicalPlan::NodeScan {
923                variable: "n".into(),
924                label_id: Some(1),
925                limit: None,
926            }),
927            count: Expression::Literal(Literal::Integer(5)),
928        };
929        let optimized = optimize(plan);
930        assert_eq!(
931            optimized,
932            LogicalPlan::NodeScan {
933                variable: "n".into(),
934                label_id: Some(1),
935                limit: Some(5),
936            }
937        );
938    }
939
940    #[test]
941    fn test_limit_pushdown_no_label() {
942        // Limit(NodeScan(n, None), 3) -> NodeScan(n, None, limit=3)
943        let plan = LogicalPlan::Limit {
944            source: Box::new(LogicalPlan::NodeScan {
945                variable: "n".into(),
946                label_id: None,
947                limit: None,
948            }),
949            count: Expression::Literal(Literal::Integer(3)),
950        };
951        let optimized = optimize(plan);
952        assert_eq!(
953            optimized,
954            LogicalPlan::NodeScan {
955                variable: "n".into(),
956                label_id: None,
957                limit: Some(3),
958            }
959        );
960    }
961
962    #[test]
963    fn test_limit_not_pushed_through_sort() {
964        // Limit(Sort(NodeScan, items), 5) -> Limit(Sort(NodeScan, items), 5)
965        let plan = LogicalPlan::Limit {
966            source: Box::new(LogicalPlan::Sort {
967                source: Box::new(LogicalPlan::NodeScan {
968                    variable: "n".into(),
969                    label_id: Some(1),
970                    limit: None,
971                }),
972                items: vec![OrderItem {
973                    expr: Expression::Variable("n".into()),
974                    ascending: true,
975                }],
976            }),
977            count: Expression::Literal(Literal::Integer(5)),
978        };
979        let optimized = optimize(plan);
980        // Should remain Limit(Sort(...))
981        assert!(matches!(optimized, LogicalPlan::Limit { .. }));
982    }
983
984    #[test]
985    fn test_limit_pushdown_non_literal() {
986        // Limit(NodeScan, $param) -> no pushdown
987        let plan = LogicalPlan::Limit {
988            source: Box::new(LogicalPlan::NodeScan {
989                variable: "n".into(),
990                label_id: Some(1),
991                limit: None,
992            }),
993            count: Expression::Parameter("count".into()),
994        };
995        let optimized = optimize(plan);
996        assert!(matches!(optimized, LogicalPlan::Limit { .. }));
997    }
998
999    #[test]
1000    fn test_limit_pushdown_merges_existing() {
1001        // Limit(NodeScan(n, label=1, limit=10), 5) -> NodeScan(n, limit=5)
1002        let plan = LogicalPlan::Limit {
1003            source: Box::new(LogicalPlan::NodeScan {
1004                variable: "n".into(),
1005                label_id: Some(1),
1006                limit: Some(10),
1007            }),
1008            count: Expression::Literal(Literal::Integer(5)),
1009        };
1010        let optimized = optimize(plan);
1011        assert_eq!(
1012            optimized,
1013            LogicalPlan::NodeScan {
1014                variable: "n".into(),
1015                label_id: Some(1),
1016                limit: Some(5),
1017            }
1018        );
1019    }
1020
1021    #[test]
1022    fn test_limit_pushdown_keeps_smaller_existing() {
1023        // Limit(NodeScan(n, label=1, limit=3), 10) -> NodeScan(n, limit=3)
1024        let plan = LogicalPlan::Limit {
1025            source: Box::new(LogicalPlan::NodeScan {
1026                variable: "n".into(),
1027                label_id: Some(1),
1028                limit: Some(3),
1029            }),
1030            count: Expression::Literal(Literal::Integer(10)),
1031        };
1032        let optimized = optimize(plan);
1033        assert_eq!(
1034            optimized,
1035            LogicalPlan::NodeScan {
1036                variable: "n".into(),
1037                label_id: Some(1),
1038                limit: Some(3),
1039            }
1040        );
1041    }
1042
1043    #[test]
1044    fn test_limit_pushdown_nested_in_project() {
1045        // Project(Limit(NodeScan, 2), [n]) -> after optimization, limit pushes into NodeScan
1046        let plan = LogicalPlan::Project {
1047            source: Box::new(LogicalPlan::Limit {
1048                source: Box::new(LogicalPlan::NodeScan {
1049                    variable: "n".into(),
1050                    label_id: Some(1),
1051                    limit: None,
1052                }),
1053                count: Expression::Literal(Literal::Integer(2)),
1054            }),
1055            items: vec![ReturnItem {
1056                expr: Expression::Variable("n".into()),
1057                alias: None,
1058            }],
1059            distinct: false,
1060        };
1061        let optimized = optimize(plan);
1062        match optimized {
1063            LogicalPlan::Project { source, .. } => {
1064                assert_eq!(
1065                    *source,
1066                    LogicalPlan::NodeScan {
1067                        variable: "n".into(),
1068                        label_id: Some(1),
1069                        limit: Some(2),
1070                    }
1071                );
1072            }
1073            _ => panic!("expected Project"),
1074        }
1075    }
1076
1077    #[test]
1078    fn test_limit_pushdown_zero() {
1079        // Limit(NodeScan, 0) -> NodeScan(limit=0)
1080        let plan = LogicalPlan::Limit {
1081            source: Box::new(LogicalPlan::NodeScan {
1082                variable: "n".into(),
1083                label_id: Some(1),
1084                limit: None,
1085            }),
1086            count: Expression::Literal(Literal::Integer(0)),
1087        };
1088        let optimized = optimize(plan);
1089        assert_eq!(
1090            optimized,
1091            LogicalPlan::NodeScan {
1092                variable: "n".into(),
1093                label_id: Some(1),
1094                limit: Some(0),
1095            }
1096        );
1097    }
1098
1099    // ========================================================================
1100    // TASK-115: Constant folding tests
1101    // ========================================================================
1102
1103    #[test]
1104    fn test_fold_int_add() {
1105        let expr = Expression::BinaryOp(
1106            BinaryOp::Add,
1107            Box::new(Expression::Literal(Literal::Integer(1))),
1108            Box::new(Expression::Literal(Literal::Integer(2))),
1109        );
1110        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Integer(3)));
1111    }
1112
1113    #[test]
1114    fn test_fold_int_sub() {
1115        let expr = Expression::BinaryOp(
1116            BinaryOp::Sub,
1117            Box::new(Expression::Literal(Literal::Integer(10))),
1118            Box::new(Expression::Literal(Literal::Integer(3))),
1119        );
1120        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Integer(7)));
1121    }
1122
1123    #[test]
1124    fn test_fold_int_mul() {
1125        let expr = Expression::BinaryOp(
1126            BinaryOp::Mul,
1127            Box::new(Expression::Literal(Literal::Integer(4))),
1128            Box::new(Expression::Literal(Literal::Integer(5))),
1129        );
1130        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Integer(20)));
1131    }
1132
1133    #[test]
1134    fn test_fold_int_div() {
1135        let expr = Expression::BinaryOp(
1136            BinaryOp::Div,
1137            Box::new(Expression::Literal(Literal::Integer(10))),
1138            Box::new(Expression::Literal(Literal::Integer(3))),
1139        );
1140        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Integer(3)));
1141    }
1142
1143    #[test]
1144    fn test_fold_int_div_by_zero_no_fold() {
1145        let expr = Expression::BinaryOp(
1146            BinaryOp::Div,
1147            Box::new(Expression::Literal(Literal::Integer(10))),
1148            Box::new(Expression::Literal(Literal::Integer(0))),
1149        );
1150        // Should not fold (would cause runtime error)
1151        assert!(matches!(expr, Expression::BinaryOp(BinaryOp::Div, ..)));
1152    }
1153
1154    #[test]
1155    fn test_fold_float_add() {
1156        let expr = Expression::BinaryOp(
1157            BinaryOp::Add,
1158            Box::new(Expression::Literal(Literal::Float(1.5))),
1159            Box::new(Expression::Literal(Literal::Float(2.5))),
1160        );
1161        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Float(4.0)));
1162    }
1163
1164    #[test]
1165    fn test_fold_and_true_x() {
1166        let expr = Expression::BinaryOp(
1167            BinaryOp::And,
1168            Box::new(Expression::Literal(Literal::Bool(true))),
1169            Box::new(Expression::Variable("x".into())),
1170        );
1171        assert_eq!(fold_expr(expr), Expression::Variable("x".into()));
1172    }
1173
1174    #[test]
1175    fn test_fold_and_false_x() {
1176        let expr = Expression::BinaryOp(
1177            BinaryOp::And,
1178            Box::new(Expression::Literal(Literal::Bool(false))),
1179            Box::new(Expression::Variable("x".into())),
1180        );
1181        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Bool(false)));
1182    }
1183
1184    #[test]
1185    fn test_fold_or_true_x() {
1186        let expr = Expression::BinaryOp(
1187            BinaryOp::Or,
1188            Box::new(Expression::Literal(Literal::Bool(true))),
1189            Box::new(Expression::Variable("x".into())),
1190        );
1191        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Bool(true)));
1192    }
1193
1194    #[test]
1195    fn test_fold_or_false_x() {
1196        let expr = Expression::BinaryOp(
1197            BinaryOp::Or,
1198            Box::new(Expression::Literal(Literal::Bool(false))),
1199            Box::new(Expression::Variable("x".into())),
1200        );
1201        assert_eq!(fold_expr(expr), Expression::Variable("x".into()));
1202    }
1203
1204    #[test]
1205    fn test_fold_not_true() {
1206        let expr = Expression::UnaryOp(
1207            UnaryOp::Not,
1208            Box::new(Expression::Literal(Literal::Bool(true))),
1209        );
1210        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Bool(false)));
1211    }
1212
1213    #[test]
1214    fn test_fold_not_false() {
1215        let expr = Expression::UnaryOp(
1216            UnaryOp::Not,
1217            Box::new(Expression::Literal(Literal::Bool(false))),
1218        );
1219        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Bool(true)));
1220    }
1221
1222    #[test]
1223    fn test_fold_nested() {
1224        // (1 + 2) * 3 -> 9
1225        let expr = Expression::BinaryOp(
1226            BinaryOp::Mul,
1227            Box::new(Expression::BinaryOp(
1228                BinaryOp::Add,
1229                Box::new(Expression::Literal(Literal::Integer(1))),
1230                Box::new(Expression::Literal(Literal::Integer(2))),
1231            )),
1232            Box::new(Expression::Literal(Literal::Integer(3))),
1233        );
1234        assert_eq!(fold_expr(expr), Expression::Literal(Literal::Integer(9)));
1235    }
1236
1237    #[test]
1238    fn test_fold_filter_true_eliminates() {
1239        // Filter(source, true) -> source
1240        let source = LogicalPlan::NodeScan {
1241            variable: "n".into(),
1242            label_id: Some(1),
1243            limit: None,
1244        };
1245        let plan = LogicalPlan::Filter {
1246            source: Box::new(source.clone()),
1247            predicate: Expression::Literal(Literal::Bool(true)),
1248        };
1249        let optimized = optimize(plan);
1250        assert_eq!(optimized, source);
1251    }
1252
1253    #[test]
1254    fn test_fold_in_filter_predicate() {
1255        // Filter(source, 1 + 2 == 3) -> after folding predicate becomes 3 == 3
1256        // The fold doesn't evaluate comparison, but folds the arithmetic
1257        let plan = LogicalPlan::Filter {
1258            source: Box::new(LogicalPlan::NodeScan {
1259                variable: "n".into(),
1260                label_id: Some(1),
1261                limit: None,
1262            }),
1263            predicate: Expression::BinaryOp(
1264                BinaryOp::Add,
1265                Box::new(Expression::Literal(Literal::Integer(1))),
1266                Box::new(Expression::Literal(Literal::Integer(2))),
1267            ),
1268        };
1269        let optimized = optimize(plan);
1270        // The predicate should be folded to 3
1271        match optimized {
1272            LogicalPlan::Filter { predicate, .. } => {
1273                assert_eq!(predicate, Expression::Literal(Literal::Integer(3)));
1274            }
1275            _ => panic!("expected Filter"),
1276        }
1277    }
1278
1279    // ========================================================================
1280    // TASK-116: Projection pruning tests
1281    // ========================================================================
1282
1283    #[test]
1284    fn test_prune_consecutive_projects() {
1285        // Project(Project(source, inner), outer) -> Project(source, outer)
1286        let source = LogicalPlan::NodeScan {
1287            variable: "n".into(),
1288            label_id: Some(1),
1289            limit: None,
1290        };
1291        let inner_items = vec![
1292            ReturnItem {
1293                expr: Expression::Variable("n".into()),
1294                alias: None,
1295            },
1296            ReturnItem {
1297                expr: Expression::Property(
1298                    Box::new(Expression::Variable("n".into())),
1299                    "name".into(),
1300                ),
1301                alias: Some("name".into()),
1302            },
1303        ];
1304        let outer_items = vec![ReturnItem {
1305            expr: Expression::Variable("name".into()),
1306            alias: None,
1307        }];
1308
1309        let plan = LogicalPlan::Project {
1310            source: Box::new(LogicalPlan::Project {
1311                source: Box::new(source.clone()),
1312                items: inner_items,
1313                distinct: false,
1314            }),
1315            items: outer_items.clone(),
1316            distinct: false,
1317        };
1318
1319        let optimized = optimize(plan);
1320        match optimized {
1321            LogicalPlan::Project {
1322                source: inner_source,
1323                items,
1324                ..
1325            } => {
1326                // Should be Project(source, outer_items) - inner project eliminated
1327                assert_eq!(*inner_source, source);
1328                assert_eq!(items, outer_items);
1329            }
1330            _ => panic!("expected Project"),
1331        }
1332    }
1333
1334    #[test]
1335    fn test_no_prune_single_project() {
1336        let source = LogicalPlan::NodeScan {
1337            variable: "n".into(),
1338            label_id: Some(1),
1339            limit: None,
1340        };
1341        let items = vec![ReturnItem {
1342            expr: Expression::Variable("n".into()),
1343            alias: None,
1344        }];
1345        let plan = LogicalPlan::Project {
1346            source: Box::new(source.clone()),
1347            items: items.clone(),
1348            distinct: false,
1349        };
1350
1351        let optimized = optimize(plan);
1352        match optimized {
1353            LogicalPlan::Project {
1354                source: s,
1355                items: i,
1356                ..
1357            } => {
1358                assert_eq!(*s, source);
1359                assert_eq!(i, items);
1360            }
1361            _ => panic!("expected Project"),
1362        }
1363    }
1364
1365    #[test]
1366    fn test_prune_three_consecutive_projects() {
1367        // Project(Project(Project(source, a), b), c) -> Project(source, c)
1368        let source = LogicalPlan::NodeScan {
1369            variable: "n".into(),
1370            label_id: Some(1),
1371            limit: None,
1372        };
1373        let items_a = vec![ReturnItem {
1374            expr: Expression::Variable("a".into()),
1375            alias: None,
1376        }];
1377        let items_b = vec![ReturnItem {
1378            expr: Expression::Variable("b".into()),
1379            alias: None,
1380        }];
1381        let items_c = vec![ReturnItem {
1382            expr: Expression::Variable("c".into()),
1383            alias: None,
1384        }];
1385
1386        let plan = LogicalPlan::Project {
1387            source: Box::new(LogicalPlan::Project {
1388                source: Box::new(LogicalPlan::Project {
1389                    source: Box::new(source.clone()),
1390                    items: items_a,
1391                    distinct: false,
1392                }),
1393                items: items_b,
1394                distinct: false,
1395            }),
1396            items: items_c.clone(),
1397            distinct: false,
1398        };
1399
1400        let optimized = optimize(plan);
1401        match optimized {
1402            LogicalPlan::Project {
1403                source: s, items, ..
1404            } => {
1405                // After bottom-up optimization, all three should collapse
1406                assert_eq!(*s, source);
1407                assert_eq!(items, items_c);
1408            }
1409            _ => panic!("expected Project"),
1410        }
1411    }
1412
1413    #[test]
1414    fn test_prune_project_with_distinct_preserved() {
1415        let source = LogicalPlan::NodeScan {
1416            variable: "n".into(),
1417            label_id: Some(1),
1418            limit: None,
1419        };
1420        let items = vec![ReturnItem {
1421            expr: Expression::Variable("n".into()),
1422            alias: None,
1423        }];
1424
1425        let plan = LogicalPlan::Project {
1426            source: Box::new(LogicalPlan::Project {
1427                source: Box::new(source.clone()),
1428                items: items.clone(),
1429                distinct: false,
1430            }),
1431            items: items.clone(),
1432            distinct: true, // outer has distinct
1433        };
1434
1435        let optimized = optimize(plan);
1436        match optimized {
1437            LogicalPlan::Project { distinct, .. } => {
1438                assert!(distinct); // outer's distinct is preserved
1439            }
1440            _ => panic!("expected Project"),
1441        }
1442    }
1443
1444    // ========================================================================
1445    // Passthrough tests
1446    // ========================================================================
1447
1448    #[test]
1449    fn test_optimize_passthrough_nodescan() {
1450        let plan = LogicalPlan::NodeScan {
1451            variable: "n".into(),
1452            label_id: Some(1),
1453            limit: None,
1454        };
1455        assert_eq!(optimize(plan.clone()), plan);
1456    }
1457
1458    #[test]
1459    fn test_optimize_passthrough_empty_source() {
1460        let plan = LogicalPlan::EmptySource;
1461        assert_eq!(optimize(plan.clone()), plan);
1462    }
1463
1464    #[test]
1465    fn test_optimize_nested_filter_in_project() {
1466        // Project(Filter(NodeScan(n, label=1), n.name == 'Alice'), [n])
1467        // -> Project(IndexScan(n, name='Alice'), [n])
1468        let plan = LogicalPlan::Project {
1469            source: Box::new(LogicalPlan::Filter {
1470                source: Box::new(LogicalPlan::NodeScan {
1471                    variable: "n".into(),
1472                    label_id: Some(1),
1473                    limit: None,
1474                }),
1475                predicate: Expression::BinaryOp(
1476                    BinaryOp::Eq,
1477                    Box::new(Expression::Property(
1478                        Box::new(Expression::Variable("n".into())),
1479                        "name".into(),
1480                    )),
1481                    Box::new(Expression::Literal(Literal::String("Alice".into()))),
1482                ),
1483            }),
1484            items: vec![ReturnItem {
1485                expr: Expression::Variable("n".into()),
1486                alias: None,
1487            }],
1488            distinct: false,
1489        };
1490
1491        let optimized = optimize(plan);
1492        match optimized {
1493            LogicalPlan::Project { source, .. } => {
1494                assert!(matches!(*source, LogicalPlan::IndexScan { .. }));
1495            }
1496            _ => panic!("expected Project(IndexScan)"),
1497        }
1498    }
1499}
cypherlite_query/planner/optimize.rs

cypherlite_query/planner/
optimize.rs
