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            QueryExpr::Explain(mut explain) => {
185                explain.inner = Box::new(self.apply(*explain.inner, ctx));
186                QueryExpr::Explain(explain)
187            }
188            // DML/DDL/Command statements pass through without normalization
189            other @ (QueryExpr::Insert(_)
190            | QueryExpr::Update(_)
191            | QueryExpr::Delete(_)
192            | QueryExpr::CreateTable(_)
193            | QueryExpr::CreateCollection(_)
194            | QueryExpr::CreateVector(_)
195            | QueryExpr::DropTable(_)
196            | QueryExpr::DropGraph(_)
197            | QueryExpr::DropVector(_)
198            | QueryExpr::DropDocument(_)
199            | QueryExpr::DropKv(_)
200            | QueryExpr::DropCollection(_)
201            | QueryExpr::Truncate(_)
202            | QueryExpr::AlterTable(_)
203            | QueryExpr::CreateVcsRef(_)
204            | QueryExpr::DropVcsRef(_)
205            | QueryExpr::ForkStore(_)
206            | QueryExpr::PromoteFork(_)
207            | QueryExpr::DropFork(_)
208            | QueryExpr::GraphCommand(_)
209            | QueryExpr::SearchCommand(_)
210            | QueryExpr::CreateIndex(_)
211            | QueryExpr::DropIndex(_)
212            | QueryExpr::ProbabilisticCommand(_)
213            | QueryExpr::Ask(_)
214            | QueryExpr::SetConfig { .. }
215            | QueryExpr::ShowConfig { .. }
216            | QueryExpr::SetSecret { .. }
217            | QueryExpr::DeleteSecret { .. }
218            | QueryExpr::ShowSecrets { .. }
219            | QueryExpr::SetKv { .. }
220            | QueryExpr::DeleteKv { .. }
221            | QueryExpr::SetTenant(_)
222            | QueryExpr::ShowTenant
223            | QueryExpr::CreateTimeSeries(_)
224            | QueryExpr::CreateMetric(_)
225            | QueryExpr::AlterMetric(_)
226            | QueryExpr::CreateSlo(_)
227            | QueryExpr::DropTimeSeries(_)
228            | QueryExpr::CreateQueue(_)
229            | QueryExpr::AlterQueue(_)
230            | QueryExpr::DropQueue(_)
231            | QueryExpr::QueueSelect(_)
232            | QueryExpr::QueueCommand(_)
233            | QueryExpr::KvCommand(_)
234            | QueryExpr::ConfigCommand(_)
235            | QueryExpr::CreateTree(_)
236            | QueryExpr::DropTree(_)
237            | QueryExpr::TreeCommand(_)
238            | QueryExpr::ExplainAlter(_)
239            | QueryExpr::TransactionControl(_)
240            | QueryExpr::MaintenanceCommand(_)
241            | QueryExpr::VcsCommand(_)
242            | QueryExpr::CreateSchema(_)
243            | QueryExpr::DropSchema(_)
244            | QueryExpr::CreateSequence(_)
245            | QueryExpr::DropSequence(_)
246            | QueryExpr::CopyFrom(_)
247            | QueryExpr::CreateView(_)
248            | QueryExpr::DropView(_)
249            | QueryExpr::RefreshMaterializedView(_)
250            | QueryExpr::CreatePolicy(_)
251            | QueryExpr::DropPolicy(_)
252            | QueryExpr::CreateServer(_)
253            | QueryExpr::DropServer(_)
254            | QueryExpr::CreateForeignTable(_)
255            | QueryExpr::DropForeignTable(_)
256            | QueryExpr::Grant(_)
257            | QueryExpr::Revoke(_)
258            | QueryExpr::AlterUser(_)
259            | QueryExpr::CreateUser(_)
260            | QueryExpr::CreateIamPolicy { .. }
261            | QueryExpr::DropIamPolicy { .. }
262            | QueryExpr::AttachPolicy { .. }
263            | QueryExpr::DetachPolicy { .. }
264            | QueryExpr::ShowPolicies { .. }
265            | QueryExpr::ShowEffectivePermissions { .. }
266            | QueryExpr::RankOf(_)
267            | QueryExpr::ApproxRankOf(_)
268            | QueryExpr::RankRange(_)
269            | QueryExpr::SimulatePolicy { .. }
270            | QueryExpr::LintPolicy { .. }
271            | QueryExpr::MigratePolicyMode { .. }
272            | QueryExpr::CreateMigration(_)
273            | QueryExpr::ApplyMigration(_)
274            | QueryExpr::RollbackMigration(_)
275            | QueryExpr::ExplainMigration(_)
276            | QueryExpr::EventsBackfill(_)
277            | QueryExpr::EventsBackfillStatus { .. }) => other,
278        }
279    }
280
281    fn is_applicable(&self, _query: &QueryExpr) -> bool {
282        true
283    }
284}
285
286/// Simplify filter expressions
287struct SimplifyFiltersRule;
288
289impl RewriteRule for SimplifyFiltersRule {
290    fn name(&self) -> &str {
291        "SimplifyFilters"
292    }
293
294    fn apply(&self, query: QueryExpr, ctx: &mut RewriteContext) -> QueryExpr {
295        match query {
296            QueryExpr::Table(mut tq) => {
297                if let Some(filter) = effective_table_filter(&tq) {
298                    tq.filter = Some(simplify_filter(filter, ctx));
299                }
300                QueryExpr::Table(tq)
301            }
302            QueryExpr::Graph(mut gq) => {
303                if let Some(filter) = effective_graph_filter(&gq) {
304                    gq.filter = Some(simplify_filter(filter, ctx));
305                }
306                QueryExpr::Graph(gq)
307            }
308            QueryExpr::Join(mut jq) => {
309                let join_filter = effective_join_filter(&jq);
310                let left = self.apply(*jq.left, ctx);
311                let right = self.apply(*jq.right, ctx);
312                if let Some(filter) = join_filter {
313                    jq.filter = Some(simplify_filter(filter, ctx));
314                }
315                jq.left = Box::new(left);
316                jq.right = Box::new(right);
317                QueryExpr::Join(jq)
318            }
319            QueryExpr::Path(pq) => QueryExpr::Path(pq),
320            QueryExpr::Vector(vq) => {
321                // Vector queries have MetadataFilter, not AstFilter
322                // Pass through for now
323                QueryExpr::Vector(vq)
324            }
325            QueryExpr::Hybrid(mut hq) => {
326                // Simplify filters in the structured part
327                hq.structured = Box::new(self.apply(*hq.structured, ctx));
328                QueryExpr::Hybrid(hq)
329            }
330            QueryExpr::Explain(mut explain) => {
331                explain.inner = Box::new(self.apply(*explain.inner, ctx));
332                QueryExpr::Explain(explain)
333            }
334            // DML/DDL/Command statements pass through without filter simplification
335            other @ (QueryExpr::Insert(_)
336            | QueryExpr::Update(_)
337            | QueryExpr::Delete(_)
338            | QueryExpr::CreateTable(_)
339            | QueryExpr::CreateCollection(_)
340            | QueryExpr::CreateVector(_)
341            | QueryExpr::DropTable(_)
342            | QueryExpr::DropGraph(_)
343            | QueryExpr::DropVector(_)
344            | QueryExpr::DropDocument(_)
345            | QueryExpr::DropKv(_)
346            | QueryExpr::DropCollection(_)
347            | QueryExpr::Truncate(_)
348            | QueryExpr::AlterTable(_)
349            | QueryExpr::CreateVcsRef(_)
350            | QueryExpr::DropVcsRef(_)
351            | QueryExpr::ForkStore(_)
352            | QueryExpr::PromoteFork(_)
353            | QueryExpr::DropFork(_)
354            | QueryExpr::GraphCommand(_)
355            | QueryExpr::SearchCommand(_)
356            | QueryExpr::CreateIndex(_)
357            | QueryExpr::DropIndex(_)
358            | QueryExpr::ProbabilisticCommand(_)
359            | QueryExpr::Ask(_)
360            | QueryExpr::SetConfig { .. }
361            | QueryExpr::ShowConfig { .. }
362            | QueryExpr::SetSecret { .. }
363            | QueryExpr::DeleteSecret { .. }
364            | QueryExpr::ShowSecrets { .. }
365            | QueryExpr::SetKv { .. }
366            | QueryExpr::DeleteKv { .. }
367            | QueryExpr::SetTenant(_)
368            | QueryExpr::ShowTenant
369            | QueryExpr::CreateTimeSeries(_)
370            | QueryExpr::CreateMetric(_)
371            | QueryExpr::AlterMetric(_)
372            | QueryExpr::CreateSlo(_)
373            | QueryExpr::DropTimeSeries(_)
374            | QueryExpr::CreateQueue(_)
375            | QueryExpr::AlterQueue(_)
376            | QueryExpr::DropQueue(_)
377            | QueryExpr::QueueSelect(_)
378            | QueryExpr::QueueCommand(_)
379            | QueryExpr::KvCommand(_)
380            | QueryExpr::ConfigCommand(_)
381            | QueryExpr::CreateTree(_)
382            | QueryExpr::DropTree(_)
383            | QueryExpr::TreeCommand(_)
384            | QueryExpr::ExplainAlter(_)
385            | QueryExpr::TransactionControl(_)
386            | QueryExpr::MaintenanceCommand(_)
387            | QueryExpr::VcsCommand(_)
388            | QueryExpr::CreateSchema(_)
389            | QueryExpr::DropSchema(_)
390            | QueryExpr::CreateSequence(_)
391            | QueryExpr::DropSequence(_)
392            | QueryExpr::CopyFrom(_)
393            | QueryExpr::CreateView(_)
394            | QueryExpr::DropView(_)
395            | QueryExpr::RefreshMaterializedView(_)
396            | QueryExpr::CreatePolicy(_)
397            | QueryExpr::DropPolicy(_)
398            | QueryExpr::CreateServer(_)
399            | QueryExpr::DropServer(_)
400            | QueryExpr::CreateForeignTable(_)
401            | QueryExpr::DropForeignTable(_)
402            | QueryExpr::Grant(_)
403            | QueryExpr::Revoke(_)
404            | QueryExpr::AlterUser(_)
405            | QueryExpr::CreateUser(_)
406            | QueryExpr::CreateIamPolicy { .. }
407            | QueryExpr::DropIamPolicy { .. }
408            | QueryExpr::AttachPolicy { .. }
409            | QueryExpr::DetachPolicy { .. }
410            | QueryExpr::ShowPolicies { .. }
411            | QueryExpr::ShowEffectivePermissions { .. }
412            | QueryExpr::RankOf(_)
413            | QueryExpr::ApproxRankOf(_)
414            | QueryExpr::RankRange(_)
415            | QueryExpr::SimulatePolicy { .. }
416            | QueryExpr::LintPolicy { .. }
417            | QueryExpr::MigratePolicyMode { .. }
418            | QueryExpr::CreateMigration(_)
419            | QueryExpr::ApplyMigration(_)
420            | QueryExpr::RollbackMigration(_)
421            | QueryExpr::ExplainMigration(_)
422            | QueryExpr::EventsBackfill(_)
423            | QueryExpr::EventsBackfillStatus { .. }) => other,
424        }
425    }
426
427    fn is_applicable(&self, query: &QueryExpr) -> bool {
428        match query {
429            QueryExpr::Table(tq) => effective_table_filter(tq).is_some(),
430            QueryExpr::Graph(gq) => effective_graph_filter(gq).is_some(),
431            QueryExpr::Join(_) => true,
432            QueryExpr::Path(_) => false,
433            QueryExpr::Vector(vq) => effective_vector_filter(vq).is_some(),
434            QueryExpr::Hybrid(_) => true, // May have filters in structured part
435            QueryExpr::Explain(explain) => self.is_applicable(&explain.inner),
436            // DML/DDL/Command statements are not applicable for filter simplification
437            QueryExpr::Insert(_)
438            | QueryExpr::Update(_)
439            | QueryExpr::Delete(_)
440            | QueryExpr::CreateTable(_)
441            | QueryExpr::CreateCollection(_)
442            | QueryExpr::CreateVector(_)
443            | QueryExpr::DropTable(_)
444            | QueryExpr::DropGraph(_)
445            | QueryExpr::DropVector(_)
446            | QueryExpr::DropDocument(_)
447            | QueryExpr::DropKv(_)
448            | QueryExpr::DropCollection(_)
449            | QueryExpr::Truncate(_)
450            | QueryExpr::AlterTable(_)
451            | QueryExpr::CreateVcsRef(_)
452            | QueryExpr::DropVcsRef(_)
453            | QueryExpr::ForkStore(_)
454            | QueryExpr::PromoteFork(_)
455            | QueryExpr::DropFork(_)
456            | QueryExpr::GraphCommand(_)
457            | QueryExpr::SearchCommand(_)
458            | QueryExpr::CreateIndex(_)
459            | QueryExpr::DropIndex(_)
460            | QueryExpr::ProbabilisticCommand(_)
461            | QueryExpr::Ask(_)
462            | QueryExpr::SetConfig { .. }
463            | QueryExpr::ShowConfig { .. }
464            | QueryExpr::SetSecret { .. }
465            | QueryExpr::DeleteSecret { .. }
466            | QueryExpr::ShowSecrets { .. }
467            | QueryExpr::SetKv { .. }
468            | QueryExpr::DeleteKv { .. }
469            | QueryExpr::SetTenant(_)
470            | QueryExpr::ShowTenant
471            | QueryExpr::CreateTimeSeries(_)
472            | QueryExpr::CreateMetric(_)
473            | QueryExpr::AlterMetric(_)
474            | QueryExpr::CreateSlo(_)
475            | QueryExpr::DropTimeSeries(_)
476            | QueryExpr::CreateQueue(_)
477            | QueryExpr::AlterQueue(_)
478            | QueryExpr::DropQueue(_)
479            | QueryExpr::QueueSelect(_)
480            | QueryExpr::QueueCommand(_)
481            | QueryExpr::KvCommand(_)
482            | QueryExpr::ConfigCommand(_)
483            | QueryExpr::CreateTree(_)
484            | QueryExpr::DropTree(_)
485            | QueryExpr::TreeCommand(_)
486            | QueryExpr::ExplainAlter(_)
487            | QueryExpr::TransactionControl(_)
488            | QueryExpr::MaintenanceCommand(_)
489            | QueryExpr::VcsCommand(_)
490            | QueryExpr::CreateSchema(_)
491            | QueryExpr::DropSchema(_)
492            | QueryExpr::CreateSequence(_)
493            | QueryExpr::DropSequence(_)
494            | QueryExpr::CopyFrom(_)
495            | QueryExpr::CreateView(_)
496            | QueryExpr::DropView(_)
497            | QueryExpr::RefreshMaterializedView(_)
498            | QueryExpr::CreatePolicy(_)
499            | QueryExpr::DropPolicy(_)
500            | QueryExpr::CreateServer(_)
501            | QueryExpr::DropServer(_)
502            | QueryExpr::CreateForeignTable(_)
503            | QueryExpr::DropForeignTable(_)
504            | QueryExpr::Grant(_)
505            | QueryExpr::Revoke(_)
506            | QueryExpr::AlterUser(_)
507            | QueryExpr::CreateUser(_)
508            | QueryExpr::CreateIamPolicy { .. }
509            | QueryExpr::DropIamPolicy { .. }
510            | QueryExpr::AttachPolicy { .. }
511            | QueryExpr::DetachPolicy { .. }
512            | QueryExpr::ShowPolicies { .. }
513            | QueryExpr::ShowEffectivePermissions { .. }
514            | QueryExpr::RankOf(_)
515            | QueryExpr::ApproxRankOf(_)
516            | QueryExpr::RankRange(_)
517            | QueryExpr::SimulatePolicy { .. }
518            | QueryExpr::LintPolicy { .. }
519            | QueryExpr::MigratePolicyMode { .. }
520            | QueryExpr::CreateMigration(_)
521            | QueryExpr::ApplyMigration(_)
522            | QueryExpr::RollbackMigration(_)
523            | QueryExpr::ExplainMigration(_)
524            | QueryExpr::EventsBackfill(_)
525            | QueryExpr::EventsBackfillStatus { .. } => false,
526        }
527    }
528}
529
530/// Push predicates down to data sources
531struct PushdownPredicatesRule;
532
533impl RewriteRule for PushdownPredicatesRule {
534    fn name(&self) -> &str {
535        "PushdownPredicates"
536    }
537
538    fn apply(&self, query: QueryExpr, ctx: &mut RewriteContext) -> QueryExpr {
539        match query {
540            QueryExpr::Join(mut jq) => {
541                // Try to push join predicates down to children
542                // This is a simplified version - real implementation would analyze
543                // which predicates can be pushed to which child
544
545                // For now, just recursively apply to children
546                jq.left = Box::new(self.apply(*jq.left, ctx));
547                jq.right = Box::new(self.apply(*jq.right, ctx));
548                ctx.stats.predicates_pushed += 1;
549                QueryExpr::Join(jq)
550            }
551            other => other,
552        }
553    }
554
555    fn is_applicable(&self, query: &QueryExpr) -> bool {
556        matches!(query, QueryExpr::Join(_))
557    }
558}
559
560/// Eliminate dead code branches
561struct EliminateDeadCodeRule;
562
563impl RewriteRule for EliminateDeadCodeRule {
564    fn name(&self) -> &str {
565        "EliminateDeadCode"
566    }
567
568    fn apply(&self, query: QueryExpr, _ctx: &mut RewriteContext) -> QueryExpr {
569        match query {
570            QueryExpr::Table(mut tq) => {
571                // Remove always-true filters
572                if let Some(filter) = effective_table_filter(&tq).as_ref() {
573                    if is_always_true(filter) {
574                        tq.filter = None;
575                    }
576                }
577                QueryExpr::Table(tq)
578            }
579            other => other,
580        }
581    }
582
583    fn is_applicable(&self, query: &QueryExpr) -> bool {
584        matches!(query, QueryExpr::Table(_))
585    }
586}
587
588/// Fold constant expressions
589struct FoldConstantsRule;
590
591impl RewriteRule for FoldConstantsRule {
592    fn name(&self) -> &str {
593        "FoldConstants"
594    }
595
596    fn apply(&self, query: QueryExpr, _ctx: &mut RewriteContext) -> QueryExpr {
597        // Constant folding is complex - for now just pass through
598        // A real implementation would evaluate constant expressions at compile time
599        query
600    }
601
602    fn is_applicable(&self, _query: &QueryExpr) -> bool {
603        true
604    }
605}
606
607// =============================================================================
608// Helper Functions
609// =============================================================================
610
611fn projection_name(proj: &Projection) -> String {
612    match proj {
613        Projection::All => "*".to_string(),
614        Projection::Column(name) => name.clone(),
615        Projection::Alias(_, alias) => alias.clone(),
616        Projection::Function(name, _) => name
617            .split_once(':')
618            .map(|(_, alias)| alias.to_string())
619            .unwrap_or_else(|| name.clone()),
620        Projection::Expression(expr, alias) => {
621            alias.clone().unwrap_or_else(|| format!("{:?}", expr))
622        }
623        Projection::Field(field, alias) => alias.clone().unwrap_or_else(|| format!("{:?}", field)),
624        Projection::Window { name, alias, .. } => alias.clone().unwrap_or_else(|| name.clone()),
625    }
626}
627
628fn simplify_filter(filter: AstFilter, ctx: &mut RewriteContext) -> AstFilter {
629    match filter {
630        AstFilter::And(left, right) => {
631            let left = simplify_filter(*left, ctx);
632            let right = simplify_filter(*right, ctx);
633
634            // AND with TRUE -> other side
635            if is_always_true(&left) {
636                ctx.stats.filters_simplified += 1;
637                return right;
638            }
639            if is_always_true(&right) {
640                ctx.stats.filters_simplified += 1;
641                return left;
642            }
643
644            // AND with FALSE -> FALSE
645            if is_always_false(&left) || is_always_false(&right) {
646                ctx.stats.filters_simplified += 1;
647                return AstFilter::Compare {
648                    field: FieldRef::TableColumn {
649                        table: String::new(),
650                        column: "1".to_string(),
651                    },
652                    op: CompareOp::Eq,
653                    value: Value::Integer(0),
654                };
655            }
656
657            AstFilter::And(Box::new(left), Box::new(right))
658        }
659        AstFilter::Or(left, right) => {
660            let left = simplify_filter(*left, ctx);
661            let right = simplify_filter(*right, ctx);
662
663            // OR with FALSE -> other side
664            if is_always_false(&left) {
665                ctx.stats.filters_simplified += 1;
666                return right;
667            }
668            if is_always_false(&right) {
669                ctx.stats.filters_simplified += 1;
670                return left;
671            }
672
673            // OR with TRUE -> TRUE
674            if is_always_true(&left) || is_always_true(&right) {
675                ctx.stats.filters_simplified += 1;
676                return AstFilter::Compare {
677                    field: FieldRef::TableColumn {
678                        table: String::new(),
679                        column: "1".to_string(),
680                    },
681                    op: CompareOp::Eq,
682                    value: Value::Integer(1),
683                };
684            }
685
686            AstFilter::Or(Box::new(left), Box::new(right))
687        }
688        AstFilter::Not(inner) => {
689            let inner = simplify_filter(*inner, ctx);
690
691            // NOT NOT x -> x
692            if let AstFilter::Not(double_inner) = inner {
693                ctx.stats.filters_simplified += 1;
694                return *double_inner;
695            }
696
697            AstFilter::Not(Box::new(inner))
698        }
699        other => other,
700    }
701}
702
703fn is_always_true(filter: &AstFilter) -> bool {
704    match filter {
705        AstFilter::Compare { field, op, value } => {
706            // 1 = 1 is always true
707            matches!(field, FieldRef::TableColumn { column, .. } if column == "1")
708                && matches!(op, CompareOp::Eq)
709                && matches!(value, Value::Integer(1))
710        }
711        _ => false,
712    }
713}
714
715fn is_always_false(filter: &AstFilter) -> bool {
716    match filter {
717        AstFilter::Compare { field, op, value } => {
718            // 1 = 0 is always false
719            matches!(field, FieldRef::TableColumn { column, .. } if column == "1")
720                && matches!(op, CompareOp::Eq)
721                && matches!(value, Value::Integer(0))
722        }
723        _ => false,
724    }
725}
726
727#[cfg(test)]
728mod tests {
729    use super::*;
730    use crate::ast::{JoinCondition, TableQuery, WindowSpec};
731
732    fn make_field(name: &str) -> FieldRef {
733        FieldRef::TableColumn {
734            table: String::new(),
735            column: name.to_string(),
736        }
737    }
738
739    #[test]
740    fn test_simplify_and_with_true() {
741        let mut ctx = RewriteContext::default();
742
743        let filter = AstFilter::And(
744            Box::new(AstFilter::Compare {
745                field: make_field("1"),
746                op: CompareOp::Eq,
747                value: Value::Integer(1),
748            }),
749            Box::new(AstFilter::Compare {
750                field: make_field("x"),
751                op: CompareOp::Eq,
752                value: Value::Integer(5),
753            }),
754        );
755
756        let simplified = simplify_filter(filter, &mut ctx);
757
758        match simplified {
759            AstFilter::Compare { field, .. } => {
760                assert!(matches!(field, FieldRef::TableColumn { column, .. } if column == "x"));
761            }
762            _ => panic!("Expected Compare filter"),
763        }
764    }
765
766    #[test]
767    fn test_simplify_double_not() {
768        let mut ctx = RewriteContext::default();
769
770        let filter = AstFilter::Not(Box::new(AstFilter::Not(Box::new(AstFilter::Compare {
771            field: make_field("x"),
772            op: CompareOp::Eq,
773            value: Value::Integer(5),
774        }))));
775
776        let simplified = simplify_filter(filter, &mut ctx);
777
778        match simplified {
779            AstFilter::Compare { field, .. } => {
780                assert!(matches!(field, FieldRef::TableColumn { column, .. } if column == "x"));
781            }
782            _ => panic!("Expected Compare filter"),
783        }
784    }
785
786    #[test]
787    fn projection_name_uses_visible_output_name_for_all_projection_shapes() {
788        assert_eq!(projection_name(&Projection::All), "*");
789        assert_eq!(
790            projection_name(&Projection::Column("raw".to_string())),
791            "raw"
792        );
793        assert_eq!(
794            projection_name(&Projection::Alias("raw".to_string(), "alias".to_string())),
795            "alias"
796        );
797        assert_eq!(
798            projection_name(&Projection::Function(
799                "LOWER:display".to_string(),
800                Vec::new()
801            )),
802            "display"
803        );
804        assert_eq!(
805            projection_name(&Projection::Expression(
806                Box::new(AstFilter::Compare {
807                    field: make_field("x"),
808                    op: CompareOp::Eq,
809                    value: Value::Integer(1),
810                }),
811                Some("expr_alias".to_string()),
812            )),
813            "expr_alias"
814        );
815        assert_eq!(
816            projection_name(&Projection::Field(
817                FieldRef::node_prop("n", "name"),
818                Some("node_name".to_string()),
819            )),
820            "node_name"
821        );
822        assert_eq!(
823            projection_name(&Projection::Window {
824                name: "ROW_NUMBER".to_string(),
825                args: Vec::new(),
826                window: Box::new(WindowSpec::default()),
827                alias: Some("rn".to_string()),
828            }),
829            "rn"
830        );
831    }
832
833    #[test]
834    fn normalize_rule_sorts_table_columns_by_output_name() {
835        let mut table = TableQuery::new("users");
836        table.columns = vec![
837            Projection::Column("z".to_string()),
838            Projection::Function("LOWER:a_alias".to_string(), Vec::new()),
839            Projection::Alias("name".to_string(), "m".to_string()),
840        ];
841
842        let mut ctx = RewriteContext::default();
843        let normalized = NormalizeRule.apply(QueryExpr::Table(table), &mut ctx);
844        let QueryExpr::Table(table) = normalized else {
845            panic!("expected table query");
846        };
847
848        assert_eq!(ctx.stats.expressions_normalized, 1);
849        assert_eq!(
850            table
851                .columns
852                .iter()
853                .map(projection_name)
854                .collect::<Vec<_>>(),
855            vec!["a_alias", "m", "z"]
856        );
857    }
858
859    #[test]
860    fn simplify_filter_covers_or_true_false_and_not_paths() {
861        let mut ctx = RewriteContext::default();
862        let truth = AstFilter::Compare {
863            field: make_field("1"),
864            op: CompareOp::Eq,
865            value: Value::Integer(1),
866        };
867        let falsehood = AstFilter::Compare {
868            field: make_field("1"),
869            op: CompareOp::Eq,
870            value: Value::Integer(0),
871        };
872        let predicate = AstFilter::Compare {
873            field: make_field("x"),
874            op: CompareOp::Eq,
875            value: Value::Integer(5),
876        };
877
878        assert_eq!(
879            simplify_filter(
880                AstFilter::Or(Box::new(falsehood.clone()), Box::new(predicate.clone())),
881                &mut ctx,
882            ),
883            predicate
884        );
885        assert!(is_always_true(&simplify_filter(
886            AstFilter::Or(Box::new(truth), Box::new(falsehood.clone())),
887            &mut ctx,
888        )));
889        assert!(is_always_false(&simplify_filter(
890            AstFilter::And(
891                Box::new(falsehood),
892                Box::new(AstFilter::IsNotNull(make_field("x")))
893            ),
894            &mut ctx,
895        )));
896        assert!(ctx.stats.filters_simplified >= 3);
897    }
898
899    #[test]
900    fn query_rewriter_runs_rules_until_fixed_point_and_exposes_context() {
901        let mut table = TableQuery::new("users");
902        table.filter = Some(AstFilter::And(
903            Box::new(AstFilter::Compare {
904                field: make_field("1"),
905                op: CompareOp::Eq,
906                value: Value::Integer(1),
907            }),
908            Box::new(AstFilter::Compare {
909                field: make_field("age"),
910                op: CompareOp::Ge,
911                value: Value::Integer(18),
912            }),
913        ));
914
915        let mut ctx = RewriteContext::default();
916        let rewritten =
917            QueryRewriter::default().rewrite_with_context(QueryExpr::Table(table), &mut ctx);
918        let QueryExpr::Table(table) = rewritten else {
919            panic!("expected table query");
920        };
921
922        assert!(matches!(
923            table.filter,
924            Some(AstFilter::Compare {
925                field: FieldRef::TableColumn { column, .. },
926                op: CompareOp::Ge,
927                value: Value::Integer(18),
928            }) if column == "age"
929        ));
930        assert!(ctx.stats.filters_simplified >= 1);
931    }
932
933    #[test]
934    fn query_rewriter_recurses_into_join_children_and_tracks_pushdown() {
935        let mut left = TableQuery::new("users");
936        left.columns = vec![
937            Projection::Column("z".to_string()),
938            Projection::Column("a".to_string()),
939        ];
940        left.filter = Some(AstFilter::And(
941            Box::new(AstFilter::Compare {
942                field: make_field("1"),
943                op: CompareOp::Eq,
944                value: Value::Integer(1),
945            }),
946            Box::new(AstFilter::Compare {
947                field: make_field("age"),
948                op: CompareOp::Ge,
949                value: Value::Integer(18),
950            }),
951        ));
952
953        let join = JoinQuery::new(
954            QueryExpr::Table(left),
955            QueryExpr::Table(TableQuery::new("orders")),
956            JoinCondition::new(make_field("id"), make_field("user_id")),
957        );
958
959        let mut ctx = RewriteContext::default();
960        let rewritten =
961            QueryRewriter::default().rewrite_with_context(QueryExpr::Join(join), &mut ctx);
962        let QueryExpr::Join(join) = rewritten else {
963            panic!("expected join query");
964        };
965        let QueryExpr::Table(left) = join.left.as_ref() else {
966            panic!("expected table on left side");
967        };
968
969        assert_eq!(
970            left.columns.iter().map(projection_name).collect::<Vec<_>>(),
971            vec!["a", "z"]
972        );
973        assert!(matches!(
974            &left.filter,
975            Some(AstFilter::Compare {
976                field: FieldRef::TableColumn { ref column, .. },
977                op: CompareOp::Ge,
978                value: Value::Integer(18),
979            }) if column == "age"
980        ));
981        assert!(ctx.stats.predicates_pushed >= 1);
982    }
983
984    #[test]
985    fn query_rewriter_eliminates_always_true_table_filters() {
986        let mut table = TableQuery::new("users");
987        table.filter = Some(AstFilter::Compare {
988            field: make_field("1"),
989            op: CompareOp::Eq,
990            value: Value::Integer(1),
991        });
992
993        let rewritten = QueryRewriter::default().rewrite(QueryExpr::Table(table));
994        let QueryExpr::Table(table) = rewritten else {
995            panic!("expected table query");
996        };
997
998        assert!(table.filter.is_none());
999    }
1000
1001    struct CountingRule;
1002
1003    impl RewriteRule for CountingRule {
1004        fn name(&self) -> &str {
1005            "CountingRule"
1006        }
1007
1008        fn apply(&self, query: QueryExpr, ctx: &mut RewriteContext) -> QueryExpr {
1009            ctx.warnings.push(self.name().to_string());
1010            query
1011        }
1012
1013        fn is_applicable(&self, query: &QueryExpr) -> bool {
1014            matches!(query, QueryExpr::Table(_))
1015        }
1016    }
1017
1018    #[test]
1019    fn custom_rules_can_be_added_after_defaults() {
1020        let mut rewriter = QueryRewriter::new();
1021        rewriter.add_rule(Box::new(CountingRule));
1022
1023        let mut ctx = RewriteContext::default();
1024        let rewritten =
1025            rewriter.rewrite_with_context(QueryExpr::Table(TableQuery::new("users")), &mut ctx);
1026
1027        assert!(matches!(rewritten, QueryExpr::Table(_)));
1028        assert!(ctx.warnings.iter().any(|warning| warning == "CountingRule"));
1029    }
1030}
reddb_rql/planner/rewriter.rs

reddb_rql/planner/
rewriter.rs
