reddb_rql/planner/
rewriter.rs

1//! Query Rewriter
2//!
3//! Multi-pass AST transformation system inspired by Neo4j's query rewriting.
4//!
5//! # Rewrite Passes
6//!
7//! 1. **Normalize**: Standardize AST structure
8//! 2. **InjectCachedProperties**: Cache property lookups at compile time
9//! 3. **SimplifyFilters**: Combine and simplify filter expressions
10//! 4. **PushdownPredicates**: Move filters closer to data source
11//! 5. **ValidateFunctions**: Check function calls against schema
12
13use crate::ast::{CompareOp, FieldRef, Filter as AstFilter, JoinQuery, Projection, QueryExpr};
14use crate::sql_lowering::{
15    effective_graph_filter, effective_join_filter, effective_table_filter, effective_vector_filter,
16};
17use reddb_types::Value;
18
19/// Context for rewrite operations
20#[derive(Debug, Clone, Default)]
21pub struct RewriteContext {
22    /// Property cache for compile-time lookups
23    pub property_cache: Vec<CachedProperty>,
24    /// Validation errors encountered
25    pub errors: Vec<String>,
26    /// Warnings generated
27    pub warnings: Vec<String>,
28    /// Statistics about rewrites
29    pub stats: RewriteStats,
30}
31
32/// A cached property lookup
33#[derive(Debug, Clone)]
34pub struct CachedProperty {
35    /// Source alias (table or node)
36    pub source: String,
37    /// Property name
38    pub property: String,
39    /// Cached value if known at compile time
40    pub cached_value: Option<String>,
41}
42
43/// Statistics about rewrite passes
44#[derive(Debug, Clone, Default)]
45pub struct RewriteStats {
46    /// Number of filters simplified
47    pub filters_simplified: u32,
48    /// Number of predicates pushed down
49    pub predicates_pushed: u32,
50    /// Number of properties cached
51    pub properties_cached: u32,
52    /// Number of expressions normalized
53    pub expressions_normalized: u32,
54}
55
56/// A rewrite rule that transforms query expressions
57pub trait RewriteRule: Send + Sync {
58    /// Rule name for debugging
59    fn name(&self) -> &str;
60
61    /// Apply the rule to a query expression
62    fn apply(&self, query: QueryExpr, ctx: &mut RewriteContext) -> QueryExpr;
63
64    /// Check if this rule is applicable to the query
65    fn is_applicable(&self, query: &QueryExpr) -> bool;
66}
67
68/// Query rewriter with pluggable rules
69pub struct QueryRewriter {
70    /// Ordered list of rewrite rules
71    rules: Vec<Box<dyn RewriteRule>>,
72    /// Maximum number of rewrite iterations
73    max_iterations: usize,
74}
75
76impl QueryRewriter {
77    /// Create a new rewriter with default rules
78    pub fn new() -> Self {
79        let rules: Vec<Box<dyn RewriteRule>> = vec![
80            Box::new(NormalizeRule),
81            Box::new(SimplifyFiltersRule),
82            Box::new(PushdownPredicatesRule),
83            Box::new(EliminateDeadCodeRule),
84            Box::new(FoldConstantsRule),
85        ];
86
87        Self {
88            rules,
89            max_iterations: 10,
90        }
91    }
92
93    /// Add a custom rewrite rule
94    pub fn add_rule(&mut self, rule: Box<dyn RewriteRule>) {
95        self.rules.push(rule);
96    }
97
98    /// Rewrite a query expression
99    pub fn rewrite(&self, query: QueryExpr) -> QueryExpr {
100        let mut ctx = RewriteContext::default();
101        self.rewrite_with_context(query, &mut ctx)
102    }
103
104    /// Rewrite with access to context
105    pub fn rewrite_with_context(
106        &self,
107        mut query: QueryExpr,
108        ctx: &mut RewriteContext,
109    ) -> QueryExpr {
110        // Apply rules iteratively until fixed point
111        for _iteration in 0..self.max_iterations {
112            let original = format!("{:?}", query);
113
114            for rule in &self.rules {
115                if rule.is_applicable(&query) {
116                    query = rule.apply(query, ctx);
117                }
118            }
119
120            // Check for fixed point
121            if format!("{:?}", query) == original {
122                break;
123            }
124        }
125
126        query
127    }
128}
129
130impl Default for QueryRewriter {
131    fn default() -> Self {
132        Self::new()
133    }
134}
135
136// =============================================================================
137// Built-in Rewrite Rules
138// =============================================================================
139
140/// Normalize AST structure
141struct NormalizeRule;
142
143impl RewriteRule for NormalizeRule {
144    fn name(&self) -> &str {
145        "Normalize"
146    }
147
148    fn apply(&self, query: QueryExpr, ctx: &mut RewriteContext) -> QueryExpr {
149        match query {
150            QueryExpr::Table(mut tq) => {
151                // Normalize column order
152                tq.columns.sort_by(|a, b| {
153                    let a_name = projection_name(a);
154                    let b_name = projection_name(b);
155                    a_name.cmp(&b_name)
156                });
157                ctx.stats.expressions_normalized += 1;
158                QueryExpr::Table(tq)
159            }
160            QueryExpr::Graph(gq) => {
161                // Graph queries don't need normalization currently
162                QueryExpr::Graph(gq)
163            }
164            QueryExpr::Join(jq) => {
165                // Recursively normalize children
166                let left = self.apply(*jq.left, ctx);
167                let right = self.apply(*jq.right, ctx);
168                QueryExpr::Join(JoinQuery {
169                    left: Box::new(left),
170                    right: Box::new(right),
171                    ..jq
172                })
173            }
174            QueryExpr::Path(pq) => QueryExpr::Path(pq),
175            QueryExpr::Vector(vq) => {
176                // Vector queries don't need normalization currently
177                QueryExpr::Vector(vq)
178            }
179            QueryExpr::Hybrid(mut hq) => {
180                // Normalize the structured part
181                hq.structured = Box::new(self.apply(*hq.structured, ctx));
182                QueryExpr::Hybrid(hq)
183            }
184            // DML/DDL/Command statements pass through without normalization
185            other @ (QueryExpr::Insert(_)
186            | QueryExpr::Update(_)
187            | QueryExpr::Delete(_)
188            | QueryExpr::CreateTable(_)
189            | QueryExpr::CreateCollection(_)
190            | QueryExpr::CreateVector(_)
191            | QueryExpr::DropTable(_)
192            | QueryExpr::DropGraph(_)
193            | QueryExpr::DropVector(_)
194            | QueryExpr::DropDocument(_)
195            | QueryExpr::DropKv(_)
196            | QueryExpr::DropCollection(_)
197            | QueryExpr::Truncate(_)
198            | QueryExpr::AlterTable(_)
199            | QueryExpr::CreateVcsRef(_)
200            | QueryExpr::DropVcsRef(_)
201            | QueryExpr::GraphCommand(_)
202            | QueryExpr::SearchCommand(_)
203            | QueryExpr::CreateIndex(_)
204            | QueryExpr::DropIndex(_)
205            | QueryExpr::ProbabilisticCommand(_)
206            | QueryExpr::Ask(_)
207            | QueryExpr::SetConfig { .. }
208            | QueryExpr::ShowConfig { .. }
209            | QueryExpr::SetSecret { .. }
210            | QueryExpr::DeleteSecret { .. }
211            | QueryExpr::ShowSecrets { .. }
212            | QueryExpr::SetKv { .. }
213            | QueryExpr::DeleteKv { .. }
214            | QueryExpr::SetTenant(_)
215            | QueryExpr::ShowTenant
216            | QueryExpr::CreateTimeSeries(_)
217            | QueryExpr::CreateMetric(_)
218            | QueryExpr::AlterMetric(_)
219            | QueryExpr::CreateSlo(_)
220            | QueryExpr::DropTimeSeries(_)
221            | QueryExpr::CreateQueue(_)
222            | QueryExpr::AlterQueue(_)
223            | QueryExpr::DropQueue(_)
224            | QueryExpr::QueueSelect(_)
225            | QueryExpr::QueueCommand(_)
226            | QueryExpr::KvCommand(_)
227            | QueryExpr::ConfigCommand(_)
228            | QueryExpr::CreateTree(_)
229            | QueryExpr::DropTree(_)
230            | QueryExpr::TreeCommand(_)
231            | QueryExpr::ExplainAlter(_)
232            | QueryExpr::TransactionControl(_)
233            | QueryExpr::MaintenanceCommand(_)
234            | QueryExpr::VcsCommand(_)
235            | QueryExpr::CreateSchema(_)
236            | QueryExpr::DropSchema(_)
237            | QueryExpr::CreateSequence(_)
238            | QueryExpr::DropSequence(_)
239            | QueryExpr::CopyFrom(_)
240            | QueryExpr::CreateView(_)
241            | QueryExpr::DropView(_)
242            | QueryExpr::RefreshMaterializedView(_)
243            | QueryExpr::CreatePolicy(_)
244            | QueryExpr::DropPolicy(_)
245            | QueryExpr::CreateServer(_)
246            | QueryExpr::DropServer(_)
247            | QueryExpr::CreateForeignTable(_)
248            | QueryExpr::DropForeignTable(_)
249            | QueryExpr::Grant(_)
250            | QueryExpr::Revoke(_)
251            | QueryExpr::AlterUser(_)
252            | QueryExpr::CreateUser(_)
253            | QueryExpr::CreateIamPolicy { .. }
254            | QueryExpr::DropIamPolicy { .. }
255            | QueryExpr::AttachPolicy { .. }
256            | QueryExpr::DetachPolicy { .. }
257            | QueryExpr::ShowPolicies { .. }
258            | QueryExpr::ShowEffectivePermissions { .. }
259            | QueryExpr::RankOf(_)
260            | QueryExpr::ApproxRankOf(_)
261            | QueryExpr::RankRange(_)
262            | QueryExpr::SimulatePolicy { .. }
263            | QueryExpr::LintPolicy { .. }
264            | QueryExpr::MigratePolicyMode { .. }
265            | QueryExpr::CreateMigration(_)
266            | QueryExpr::ApplyMigration(_)
267            | QueryExpr::RollbackMigration(_)
268            | QueryExpr::ExplainMigration(_)
269            | QueryExpr::EventsBackfill(_)
270            | QueryExpr::EventsBackfillStatus { .. }) => other,
271        }
272    }
273
274    fn is_applicable(&self, _query: &QueryExpr) -> bool {
275        true
276    }
277}
278
279/// Simplify filter expressions
280struct SimplifyFiltersRule;
281
282impl RewriteRule for SimplifyFiltersRule {
283    fn name(&self) -> &str {
284        "SimplifyFilters"
285    }
286
287    fn apply(&self, query: QueryExpr, ctx: &mut RewriteContext) -> QueryExpr {
288        match query {
289            QueryExpr::Table(mut tq) => {
290                if let Some(filter) = effective_table_filter(&tq) {
291                    tq.filter = Some(simplify_filter(filter, ctx));
292                }
293                QueryExpr::Table(tq)
294            }
295            QueryExpr::Graph(mut gq) => {
296                if let Some(filter) = effective_graph_filter(&gq) {
297                    gq.filter = Some(simplify_filter(filter, ctx));
298                }
299                QueryExpr::Graph(gq)
300            }
301            QueryExpr::Join(mut jq) => {
302                let join_filter = effective_join_filter(&jq);
303                let left = self.apply(*jq.left, ctx);
304                let right = self.apply(*jq.right, ctx);
305                if let Some(filter) = join_filter {
306                    jq.filter = Some(simplify_filter(filter, ctx));
307                }
308                jq.left = Box::new(left);
309                jq.right = Box::new(right);
310                QueryExpr::Join(jq)
311            }
312            QueryExpr::Path(pq) => QueryExpr::Path(pq),
313            QueryExpr::Vector(vq) => {
314                // Vector queries have MetadataFilter, not AstFilter
315                // Pass through for now
316                QueryExpr::Vector(vq)
317            }
318            QueryExpr::Hybrid(mut hq) => {
319                // Simplify filters in the structured part
320                hq.structured = Box::new(self.apply(*hq.structured, ctx));
321                QueryExpr::Hybrid(hq)
322            }
323            // DML/DDL/Command statements pass through without filter simplification
324            other @ (QueryExpr::Insert(_)
325            | QueryExpr::Update(_)
326            | QueryExpr::Delete(_)
327            | QueryExpr::CreateTable(_)
328            | QueryExpr::CreateCollection(_)
329            | QueryExpr::CreateVector(_)
330            | QueryExpr::DropTable(_)
331            | QueryExpr::DropGraph(_)
332            | QueryExpr::DropVector(_)
333            | QueryExpr::DropDocument(_)
334            | QueryExpr::DropKv(_)
335            | QueryExpr::DropCollection(_)
336            | QueryExpr::Truncate(_)
337            | QueryExpr::AlterTable(_)
338            | QueryExpr::CreateVcsRef(_)
339            | QueryExpr::DropVcsRef(_)
340            | QueryExpr::GraphCommand(_)
341            | QueryExpr::SearchCommand(_)
342            | QueryExpr::CreateIndex(_)
343            | QueryExpr::DropIndex(_)
344            | QueryExpr::ProbabilisticCommand(_)
345            | QueryExpr::Ask(_)
346            | QueryExpr::SetConfig { .. }
347            | QueryExpr::ShowConfig { .. }
348            | QueryExpr::SetSecret { .. }
349            | QueryExpr::DeleteSecret { .. }
350            | QueryExpr::ShowSecrets { .. }
351            | QueryExpr::SetKv { .. }
352            | QueryExpr::DeleteKv { .. }
353            | QueryExpr::SetTenant(_)
354            | QueryExpr::ShowTenant
355            | QueryExpr::CreateTimeSeries(_)
356            | QueryExpr::CreateMetric(_)
357            | QueryExpr::AlterMetric(_)
358            | QueryExpr::CreateSlo(_)
359            | QueryExpr::DropTimeSeries(_)
360            | QueryExpr::CreateQueue(_)
361            | QueryExpr::AlterQueue(_)
362            | QueryExpr::DropQueue(_)
363            | QueryExpr::QueueSelect(_)
364            | QueryExpr::QueueCommand(_)
365            | QueryExpr::KvCommand(_)
366            | QueryExpr::ConfigCommand(_)
367            | QueryExpr::CreateTree(_)
368            | QueryExpr::DropTree(_)
369            | QueryExpr::TreeCommand(_)
370            | QueryExpr::ExplainAlter(_)
371            | QueryExpr::TransactionControl(_)
372            | QueryExpr::MaintenanceCommand(_)
373            | QueryExpr::VcsCommand(_)
374            | QueryExpr::CreateSchema(_)
375            | QueryExpr::DropSchema(_)
376            | QueryExpr::CreateSequence(_)
377            | QueryExpr::DropSequence(_)
378            | QueryExpr::CopyFrom(_)
379            | QueryExpr::CreateView(_)
380            | QueryExpr::DropView(_)
381            | QueryExpr::RefreshMaterializedView(_)
382            | QueryExpr::CreatePolicy(_)
383            | QueryExpr::DropPolicy(_)
384            | QueryExpr::CreateServer(_)
385            | QueryExpr::DropServer(_)
386            | QueryExpr::CreateForeignTable(_)
387            | QueryExpr::DropForeignTable(_)
388            | QueryExpr::Grant(_)
389            | QueryExpr::Revoke(_)
390            | QueryExpr::AlterUser(_)
391            | QueryExpr::CreateUser(_)
392            | QueryExpr::CreateIamPolicy { .. }
393            | QueryExpr::DropIamPolicy { .. }
394            | QueryExpr::AttachPolicy { .. }
395            | QueryExpr::DetachPolicy { .. }
396            | QueryExpr::ShowPolicies { .. }
397            | QueryExpr::ShowEffectivePermissions { .. }
398            | QueryExpr::RankOf(_)
399            | QueryExpr::ApproxRankOf(_)
400            | QueryExpr::RankRange(_)
401            | QueryExpr::SimulatePolicy { .. }
402            | QueryExpr::LintPolicy { .. }
403            | QueryExpr::MigratePolicyMode { .. }
404            | QueryExpr::CreateMigration(_)
405            | QueryExpr::ApplyMigration(_)
406            | QueryExpr::RollbackMigration(_)
407            | QueryExpr::ExplainMigration(_)
408            | QueryExpr::EventsBackfill(_)
409            | QueryExpr::EventsBackfillStatus { .. }) => other,
410        }
411    }
412
413    fn is_applicable(&self, query: &QueryExpr) -> bool {
414        match query {
415            QueryExpr::Table(tq) => effective_table_filter(tq).is_some(),
416            QueryExpr::Graph(gq) => effective_graph_filter(gq).is_some(),
417            QueryExpr::Join(_) => true,
418            QueryExpr::Path(_) => false,
419            QueryExpr::Vector(vq) => effective_vector_filter(vq).is_some(),
420            QueryExpr::Hybrid(_) => true, // May have filters in structured part
421            // DML/DDL/Command statements are not applicable for filter simplification
422            QueryExpr::Insert(_)
423            | QueryExpr::Update(_)
424            | QueryExpr::Delete(_)
425            | QueryExpr::CreateTable(_)
426            | QueryExpr::CreateCollection(_)
427            | QueryExpr::CreateVector(_)
428            | QueryExpr::DropTable(_)
429            | QueryExpr::DropGraph(_)
430            | QueryExpr::DropVector(_)
431            | QueryExpr::DropDocument(_)
432            | QueryExpr::DropKv(_)
433            | QueryExpr::DropCollection(_)
434            | QueryExpr::Truncate(_)
435            | QueryExpr::AlterTable(_)
436            | QueryExpr::CreateVcsRef(_)
437            | QueryExpr::DropVcsRef(_)
438            | QueryExpr::GraphCommand(_)
439            | QueryExpr::SearchCommand(_)
440            | QueryExpr::CreateIndex(_)
441            | QueryExpr::DropIndex(_)
442            | QueryExpr::ProbabilisticCommand(_)
443            | QueryExpr::Ask(_)
444            | QueryExpr::SetConfig { .. }
445            | QueryExpr::ShowConfig { .. }
446            | QueryExpr::SetSecret { .. }
447            | QueryExpr::DeleteSecret { .. }
448            | QueryExpr::ShowSecrets { .. }
449            | QueryExpr::SetKv { .. }
450            | QueryExpr::DeleteKv { .. }
451            | QueryExpr::SetTenant(_)
452            | QueryExpr::ShowTenant
453            | QueryExpr::CreateTimeSeries(_)
454            | QueryExpr::CreateMetric(_)
455            | QueryExpr::AlterMetric(_)
456            | QueryExpr::CreateSlo(_)
457            | QueryExpr::DropTimeSeries(_)
458            | QueryExpr::CreateQueue(_)
459            | QueryExpr::AlterQueue(_)
460            | QueryExpr::DropQueue(_)
461            | QueryExpr::QueueSelect(_)
462            | QueryExpr::QueueCommand(_)
463            | QueryExpr::KvCommand(_)
464            | QueryExpr::ConfigCommand(_)
465            | QueryExpr::CreateTree(_)
466            | QueryExpr::DropTree(_)
467            | QueryExpr::TreeCommand(_)
468            | QueryExpr::ExplainAlter(_)
469            | QueryExpr::TransactionControl(_)
470            | QueryExpr::MaintenanceCommand(_)
471            | QueryExpr::VcsCommand(_)
472            | QueryExpr::CreateSchema(_)
473            | QueryExpr::DropSchema(_)
474            | QueryExpr::CreateSequence(_)
475            | QueryExpr::DropSequence(_)
476            | QueryExpr::CopyFrom(_)
477            | QueryExpr::CreateView(_)
478            | QueryExpr::DropView(_)
479            | QueryExpr::RefreshMaterializedView(_)
480            | QueryExpr::CreatePolicy(_)
481            | QueryExpr::DropPolicy(_)
482            | QueryExpr::CreateServer(_)
483            | QueryExpr::DropServer(_)
484            | QueryExpr::CreateForeignTable(_)
485            | QueryExpr::DropForeignTable(_)
486            | QueryExpr::Grant(_)
487            | QueryExpr::Revoke(_)
488            | QueryExpr::AlterUser(_)
489            | QueryExpr::CreateUser(_)
490            | QueryExpr::CreateIamPolicy { .. }
491            | QueryExpr::DropIamPolicy { .. }
492            | QueryExpr::AttachPolicy { .. }
493            | QueryExpr::DetachPolicy { .. }
494            | QueryExpr::ShowPolicies { .. }
495            | QueryExpr::ShowEffectivePermissions { .. }
496            | QueryExpr::RankOf(_)
497            | QueryExpr::ApproxRankOf(_)
498            | QueryExpr::RankRange(_)
499            | QueryExpr::SimulatePolicy { .. }
500            | QueryExpr::LintPolicy { .. }
501            | QueryExpr::MigratePolicyMode { .. }
502            | QueryExpr::CreateMigration(_)
503            | QueryExpr::ApplyMigration(_)
504            | QueryExpr::RollbackMigration(_)
505            | QueryExpr::ExplainMigration(_)
506            | QueryExpr::EventsBackfill(_)
507            | QueryExpr::EventsBackfillStatus { .. } => false,
508        }
509    }
510}
511
512/// Push predicates down to data sources
513struct PushdownPredicatesRule;
514
515impl RewriteRule for PushdownPredicatesRule {
516    fn name(&self) -> &str {
517        "PushdownPredicates"
518    }
519
520    fn apply(&self, query: QueryExpr, ctx: &mut RewriteContext) -> QueryExpr {
521        match query {
522            QueryExpr::Join(mut jq) => {
523                // Try to push join predicates down to children
524                // This is a simplified version - real implementation would analyze
525                // which predicates can be pushed to which child
526
527                // For now, just recursively apply to children
528                jq.left = Box::new(self.apply(*jq.left, ctx));
529                jq.right = Box::new(self.apply(*jq.right, ctx));
530                ctx.stats.predicates_pushed += 1;
531                QueryExpr::Join(jq)
532            }
533            other => other,
534        }
535    }
536
537    fn is_applicable(&self, query: &QueryExpr) -> bool {
538        matches!(query, QueryExpr::Join(_))
539    }
540}
541
542/// Eliminate dead code branches
543struct EliminateDeadCodeRule;
544
545impl RewriteRule for EliminateDeadCodeRule {
546    fn name(&self) -> &str {
547        "EliminateDeadCode"
548    }
549
550    fn apply(&self, query: QueryExpr, _ctx: &mut RewriteContext) -> QueryExpr {
551        match query {
552            QueryExpr::Table(mut tq) => {
553                // Remove always-true filters
554                if let Some(filter) = effective_table_filter(&tq).as_ref() {
555                    if is_always_true(filter) {
556                        tq.filter = None;
557                    }
558                }
559                QueryExpr::Table(tq)
560            }
561            other => other,
562        }
563    }
564
565    fn is_applicable(&self, query: &QueryExpr) -> bool {
566        matches!(query, QueryExpr::Table(_))
567    }
568}
569
570/// Fold constant expressions
571struct FoldConstantsRule;
572
573impl RewriteRule for FoldConstantsRule {
574    fn name(&self) -> &str {
575        "FoldConstants"
576    }
577
578    fn apply(&self, query: QueryExpr, _ctx: &mut RewriteContext) -> QueryExpr {
579        // Constant folding is complex - for now just pass through
580        // A real implementation would evaluate constant expressions at compile time
581        query
582    }
583
584    fn is_applicable(&self, _query: &QueryExpr) -> bool {
585        true
586    }
587}
588
589// =============================================================================
590// Helper Functions
591// =============================================================================
592
593fn projection_name(proj: &Projection) -> String {
594    match proj {
595        Projection::All => "*".to_string(),
596        Projection::Column(name) => name.clone(),
597        Projection::Alias(_, alias) => alias.clone(),
598        Projection::Function(name, _) => name
599            .split_once(':')
600            .map(|(_, alias)| alias.to_string())
601            .unwrap_or_else(|| name.clone()),
602        Projection::Expression(expr, alias) => {
603            alias.clone().unwrap_or_else(|| format!("{:?}", expr))
604        }
605        Projection::Field(field, alias) => alias.clone().unwrap_or_else(|| format!("{:?}", field)),
606        Projection::Window { name, alias, .. } => alias.clone().unwrap_or_else(|| name.clone()),
607    }
608}
609
610fn simplify_filter(filter: AstFilter, ctx: &mut RewriteContext) -> AstFilter {
611    match filter {
612        AstFilter::And(left, right) => {
613            let left = simplify_filter(*left, ctx);
614            let right = simplify_filter(*right, ctx);
615
616            // AND with TRUE -> other side
617            if is_always_true(&left) {
618                ctx.stats.filters_simplified += 1;
619                return right;
620            }
621            if is_always_true(&right) {
622                ctx.stats.filters_simplified += 1;
623                return left;
624            }
625
626            // AND with FALSE -> FALSE
627            if is_always_false(&left) || is_always_false(&right) {
628                ctx.stats.filters_simplified += 1;
629                return AstFilter::Compare {
630                    field: FieldRef::TableColumn {
631                        table: String::new(),
632                        column: "1".to_string(),
633                    },
634                    op: CompareOp::Eq,
635                    value: Value::Integer(0),
636                };
637            }
638
639            AstFilter::And(Box::new(left), Box::new(right))
640        }
641        AstFilter::Or(left, right) => {
642            let left = simplify_filter(*left, ctx);
643            let right = simplify_filter(*right, ctx);
644
645            // OR with FALSE -> other side
646            if is_always_false(&left) {
647                ctx.stats.filters_simplified += 1;
648                return right;
649            }
650            if is_always_false(&right) {
651                ctx.stats.filters_simplified += 1;
652                return left;
653            }
654
655            // OR with TRUE -> TRUE
656            if is_always_true(&left) || is_always_true(&right) {
657                ctx.stats.filters_simplified += 1;
658                return AstFilter::Compare {
659                    field: FieldRef::TableColumn {
660                        table: String::new(),
661                        column: "1".to_string(),
662                    },
663                    op: CompareOp::Eq,
664                    value: Value::Integer(1),
665                };
666            }
667
668            AstFilter::Or(Box::new(left), Box::new(right))
669        }
670        AstFilter::Not(inner) => {
671            let inner = simplify_filter(*inner, ctx);
672
673            // NOT NOT x -> x
674            if let AstFilter::Not(double_inner) = inner {
675                ctx.stats.filters_simplified += 1;
676                return *double_inner;
677            }
678
679            AstFilter::Not(Box::new(inner))
680        }
681        other => other,
682    }
683}
684
685fn is_always_true(filter: &AstFilter) -> bool {
686    match filter {
687        AstFilter::Compare { field, op, value } => {
688            // 1 = 1 is always true
689            matches!(field, FieldRef::TableColumn { column, .. } if column == "1")
690                && matches!(op, CompareOp::Eq)
691                && matches!(value, Value::Integer(1))
692        }
693        _ => false,
694    }
695}
696
697fn is_always_false(filter: &AstFilter) -> bool {
698    match filter {
699        AstFilter::Compare { field, op, value } => {
700            // 1 = 0 is always false
701            matches!(field, FieldRef::TableColumn { column, .. } if column == "1")
702                && matches!(op, CompareOp::Eq)
703                && matches!(value, Value::Integer(0))
704        }
705        _ => false,
706    }
707}
708
709#[cfg(test)]
710mod tests {
711    use super::*;
712    use crate::ast::{JoinCondition, TableQuery, WindowSpec};
713
714    fn make_field(name: &str) -> FieldRef {
715        FieldRef::TableColumn {
716            table: String::new(),
717            column: name.to_string(),
718        }
719    }
720
721    #[test]
722    fn test_simplify_and_with_true() {
723        let mut ctx = RewriteContext::default();
724
725        let filter = AstFilter::And(
726            Box::new(AstFilter::Compare {
727                field: make_field("1"),
728                op: CompareOp::Eq,
729                value: Value::Integer(1),
730            }),
731            Box::new(AstFilter::Compare {
732                field: make_field("x"),
733                op: CompareOp::Eq,
734                value: Value::Integer(5),
735            }),
736        );
737
738        let simplified = simplify_filter(filter, &mut ctx);
739
740        match simplified {
741            AstFilter::Compare { field, .. } => {
742                assert!(matches!(field, FieldRef::TableColumn { column, .. } if column == "x"));
743            }
744            _ => panic!("Expected Compare filter"),
745        }
746    }
747
748    #[test]
749    fn test_simplify_double_not() {
750        let mut ctx = RewriteContext::default();
751
752        let filter = AstFilter::Not(Box::new(AstFilter::Not(Box::new(AstFilter::Compare {
753            field: make_field("x"),
754            op: CompareOp::Eq,
755            value: Value::Integer(5),
756        }))));
757
758        let simplified = simplify_filter(filter, &mut ctx);
759
760        match simplified {
761            AstFilter::Compare { field, .. } => {
762                assert!(matches!(field, FieldRef::TableColumn { column, .. } if column == "x"));
763            }
764            _ => panic!("Expected Compare filter"),
765        }
766    }
767
768    #[test]
769    fn projection_name_uses_visible_output_name_for_all_projection_shapes() {
770        assert_eq!(projection_name(&Projection::All), "*");
771        assert_eq!(
772            projection_name(&Projection::Column("raw".to_string())),
773            "raw"
774        );
775        assert_eq!(
776            projection_name(&Projection::Alias("raw".to_string(), "alias".to_string())),
777            "alias"
778        );
779        assert_eq!(
780            projection_name(&Projection::Function(
781                "LOWER:display".to_string(),
782                Vec::new()
783            )),
784            "display"
785        );
786        assert_eq!(
787            projection_name(&Projection::Expression(
788                Box::new(AstFilter::Compare {
789                    field: make_field("x"),
790                    op: CompareOp::Eq,
791                    value: Value::Integer(1),
792                }),
793                Some("expr_alias".to_string()),
794            )),
795            "expr_alias"
796        );
797        assert_eq!(
798            projection_name(&Projection::Field(
799                FieldRef::node_prop("n", "name"),
800                Some("node_name".to_string()),
801            )),
802            "node_name"
803        );
804        assert_eq!(
805            projection_name(&Projection::Window {
806                name: "ROW_NUMBER".to_string(),
807                args: Vec::new(),
808                window: Box::new(WindowSpec::default()),
809                alias: Some("rn".to_string()),
810            }),
811            "rn"
812        );
813    }
814
815    #[test]
816    fn normalize_rule_sorts_table_columns_by_output_name() {
817        let mut table = TableQuery::new("users");
818        table.columns = vec![
819            Projection::Column("z".to_string()),
820            Projection::Function("LOWER:a_alias".to_string(), Vec::new()),
821            Projection::Alias("name".to_string(), "m".to_string()),
822        ];
823
824        let mut ctx = RewriteContext::default();
825        let normalized = NormalizeRule.apply(QueryExpr::Table(table), &mut ctx);
826        let QueryExpr::Table(table) = normalized else {
827            panic!("expected table query");
828        };
829
830        assert_eq!(ctx.stats.expressions_normalized, 1);
831        assert_eq!(
832            table
833                .columns
834                .iter()
835                .map(projection_name)
836                .collect::<Vec<_>>(),
837            vec!["a_alias", "m", "z"]
838        );
839    }
840
841    #[test]
842    fn simplify_filter_covers_or_true_false_and_not_paths() {
843        let mut ctx = RewriteContext::default();
844        let truth = AstFilter::Compare {
845            field: make_field("1"),
846            op: CompareOp::Eq,
847            value: Value::Integer(1),
848        };
849        let falsehood = AstFilter::Compare {
850            field: make_field("1"),
851            op: CompareOp::Eq,
852            value: Value::Integer(0),
853        };
854        let predicate = AstFilter::Compare {
855            field: make_field("x"),
856            op: CompareOp::Eq,
857            value: Value::Integer(5),
858        };
859
860        assert_eq!(
861            simplify_filter(
862                AstFilter::Or(Box::new(falsehood.clone()), Box::new(predicate.clone())),
863                &mut ctx,
864            ),
865            predicate
866        );
867        assert!(is_always_true(&simplify_filter(
868            AstFilter::Or(Box::new(truth), Box::new(falsehood.clone())),
869            &mut ctx,
870        )));
871        assert!(is_always_false(&simplify_filter(
872            AstFilter::And(
873                Box::new(falsehood),
874                Box::new(AstFilter::IsNotNull(make_field("x")))
875            ),
876            &mut ctx,
877        )));
878        assert!(ctx.stats.filters_simplified >= 3);
879    }
880
881    #[test]
882    fn query_rewriter_runs_rules_until_fixed_point_and_exposes_context() {
883        let mut table = TableQuery::new("users");
884        table.filter = Some(AstFilter::And(
885            Box::new(AstFilter::Compare {
886                field: make_field("1"),
887                op: CompareOp::Eq,
888                value: Value::Integer(1),
889            }),
890            Box::new(AstFilter::Compare {
891                field: make_field("age"),
892                op: CompareOp::Ge,
893                value: Value::Integer(18),
894            }),
895        ));
896
897        let mut ctx = RewriteContext::default();
898        let rewritten =
899            QueryRewriter::default().rewrite_with_context(QueryExpr::Table(table), &mut ctx);
900        let QueryExpr::Table(table) = rewritten else {
901            panic!("expected table query");
902        };
903
904        assert!(matches!(
905            table.filter,
906            Some(AstFilter::Compare {
907                field: FieldRef::TableColumn { column, .. },
908                op: CompareOp::Ge,
909                value: Value::Integer(18),
910            }) if column == "age"
911        ));
912        assert!(ctx.stats.filters_simplified >= 1);
913    }
914
915    #[test]
916    fn query_rewriter_recurses_into_join_children_and_tracks_pushdown() {
917        let mut left = TableQuery::new("users");
918        left.columns = vec![
919            Projection::Column("z".to_string()),
920            Projection::Column("a".to_string()),
921        ];
922        left.filter = Some(AstFilter::And(
923            Box::new(AstFilter::Compare {
924                field: make_field("1"),
925                op: CompareOp::Eq,
926                value: Value::Integer(1),
927            }),
928            Box::new(AstFilter::Compare {
929                field: make_field("age"),
930                op: CompareOp::Ge,
931                value: Value::Integer(18),
932            }),
933        ));
934
935        let join = JoinQuery::new(
936            QueryExpr::Table(left),
937            QueryExpr::Table(TableQuery::new("orders")),
938            JoinCondition::new(make_field("id"), make_field("user_id")),
939        );
940
941        let mut ctx = RewriteContext::default();
942        let rewritten =
943            QueryRewriter::default().rewrite_with_context(QueryExpr::Join(join), &mut ctx);
944        let QueryExpr::Join(join) = rewritten else {
945            panic!("expected join query");
946        };
947        let QueryExpr::Table(left) = join.left.as_ref() else {
948            panic!("expected table on left side");
949        };
950
951        assert_eq!(
952            left.columns.iter().map(projection_name).collect::<Vec<_>>(),
953            vec!["a", "z"]
954        );
955        assert!(matches!(
956            &left.filter,
957            Some(AstFilter::Compare {
958                field: FieldRef::TableColumn { ref column, .. },
959                op: CompareOp::Ge,
960                value: Value::Integer(18),
961            }) if column == "age"
962        ));
963        assert!(ctx.stats.predicates_pushed >= 1);
964    }
965
966    #[test]
967    fn query_rewriter_eliminates_always_true_table_filters() {
968        let mut table = TableQuery::new("users");
969        table.filter = Some(AstFilter::Compare {
970            field: make_field("1"),
971            op: CompareOp::Eq,
972            value: Value::Integer(1),
973        });
974
975        let rewritten = QueryRewriter::default().rewrite(QueryExpr::Table(table));
976        let QueryExpr::Table(table) = rewritten else {
977            panic!("expected table query");
978        };
979
980        assert!(table.filter.is_none());
981    }
982
983    struct CountingRule;
984
985    impl RewriteRule for CountingRule {
986        fn name(&self) -> &str {
987            "CountingRule"
988        }
989
990        fn apply(&self, query: QueryExpr, ctx: &mut RewriteContext) -> QueryExpr {
991            ctx.warnings.push(self.name().to_string());
992            query
993        }
994
995        fn is_applicable(&self, query: &QueryExpr) -> bool {
996            matches!(query, QueryExpr::Table(_))
997        }
998    }
999
1000    #[test]
1001    fn custom_rules_can_be_added_after_defaults() {
1002        let mut rewriter = QueryRewriter::new();
1003        rewriter.add_rule(Box::new(CountingRule));
1004
1005        let mut ctx = RewriteContext::default();
1006        let rewritten =
1007            rewriter.rewrite_with_context(QueryExpr::Table(TableQuery::new("users")), &mut ctx);
1008
1009        assert!(matches!(rewritten, QueryExpr::Table(_)));
1010        assert!(ctx.warnings.iter().any(|warning| warning == "CountingRule"));
1011    }
1012}
reddb_rql/planner/rewriter.rs

reddb_rql/planner/
rewriter.rs
