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

reddb_rql/planner/
rewriter.rs
