Skip to main content

uqa_sql/plan/
query.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! SELECT, source, projection, order, CTE, and mutation-child lowering.
8
9use super::rewrite::rewrite_query_scalars;
10use super::scalar::lower_scalar_expression;
11use super::{
12    AccessPathPlan, AggregateClassifier, AssignmentPlan, ComputePlan, CteCyclePlan, CtePlan,
13    CteSearchPlan, Expr, ExpressionPlan, FromClause, JoinExecutionStrategy, MergeWhenPlan,
14    NoRegisteredAggregates, OrderBy, OrderPlan, Projection, ProjectionPlan, QueryBlockPlan,
15    QueryPlan, RelationalPlan, ScalarExpr, SelectStmt, SourcePlan, TableFunctionPlan, CTE,
16};
17
18mod computation;
19
20impl QueryBlockPlan {
21    /// One scalar SELECT with no relational clauses or subplans. The caller must also reject set-returning routines using its selected catalog.
22    pub fn is_single_expression(&self) -> bool {
23        self.deferred_outer_rewrites.is_empty()
24            && matches!(self.compute, ComputePlan::Project)
25            && self.from.is_none()
26            && self.r#where.is_none()
27            && self.group_by.is_empty()
28            && self.grouping_sets.is_empty()
29            && self.having.is_none()
30            && self.windows.is_empty()
31            && !self.distinct
32            && self.distinct_on.is_empty()
33            && self.order_by.is_empty()
34            && self.limit.is_none()
35            && self.offset.is_none()
36            && self.locking.is_empty()
37            && self.subqueries.is_empty()
38            && self.projections.len() == 1
39            && {
40                let mut window = false;
41                self.projections[0]
42                    .expr
43                    .visit(&mut |node| window |= matches!(node, ScalarExpr::WindowCall { .. }));
44                !window
45            }
46    }
47}
48
49impl QueryPlan {
50    /// Rewrite every physical scalar node owned by this query exactly once,
51    /// including CTEs, relational sources, and scalar-subquery plans.
52    pub fn rewrite_scalar_expressions(&mut self, rewrite: &mut dyn FnMut(&mut ScalarExpr)) {
53        rewrite_query_scalars(self, rewrite);
54    }
55
56    /// Visit every `FROM` item this query owns, including those of nested queries.
57    pub fn visit_sources_mut(&mut self, visit: &mut dyn FnMut(&mut SourcePlan)) {
58        super::rewrite::visit_query_sources(self, visit);
59    }
60
61    #[must_use]
62    pub fn lower(statement: SelectStmt) -> Self {
63        Self::lower_with(statement, &NoRegisteredAggregates)
64    }
65
66    #[must_use]
67    pub fn lower_with(mut statement: SelectStmt, aggregates: &dyn AggregateClassifier) -> Self {
68        let ctes = lower_ctes(&statement.with, aggregates);
69        statement.with.clear();
70        let root = lower_relational_root(statement, aggregates);
71        let mut plan = Self {
72            analyzed_output: None,
73            analyzed_source: None,
74            analyzed_grouping: None,
75            relation_privilege_subject: None,
76            relations_bound: false,
77            ctes,
78            root,
79        };
80        plan.normalize_window_definitions()
81            .expect("compiler windows belong to their query block");
82        plan
83    }
84}
85
86pub(super) fn lower_ctes(ctes: &[CTE], aggregates: &dyn AggregateClassifier) -> Vec<CtePlan> {
87    ctes.iter()
88        .map(|cte| CtePlan {
89            name: cte.name.clone(),
90            columns: cte.columns.clone(),
91            recursive: cte.recursive,
92            materialization: cte.materialization,
93            search: cte.search.as_ref().map(|search| CteSearchPlan {
94                columns: search.columns.clone(),
95                breadth_first: search.breadth_first,
96                sequence_column: search.sequence_column.clone(),
97            }),
98            cycle: cte.cycle.as_ref().map(|cycle| CteCyclePlan {
99                columns: cycle.columns.clone(),
100                mark_column: cycle.mark_column.clone(),
101                mark_value: lower_scalar_expression(
102                    cycle.mark_value.clone(),
103                    aggregates,
104                    &mut Vec::new(),
105                ),
106                mark_default: lower_scalar_expression(
107                    cycle.mark_default.clone(),
108                    aggregates,
109                    &mut Vec::new(),
110                ),
111                path_column: cycle.path_column.clone(),
112            }),
113            body: super::CtePlanBody::from(super::UnifiedPlan::lower_with(
114                cte.body.clone().into_statement(),
115                aggregates,
116            )),
117        })
118        .collect()
119}
120
121pub(super) fn lower_assignments(
122    assignments: Vec<(crate::ast::AssignmentTargets, Expr)>,
123    aggregates: &dyn AggregateClassifier,
124    subqueries: &mut Vec<QueryPlan>,
125) -> Vec<AssignmentPlan> {
126    assignments
127        .into_iter()
128        .map(|(target, expression)| AssignmentPlan {
129            target: target
130                .map(|expression| lower_scalar_expression(expression, aggregates, subqueries)),
131            value: lower_scalar_expression(expression, aggregates, subqueries),
132        })
133        .collect()
134}
135
136pub(super) fn lower_targets(
137    targets: Vec<crate::ast::AssignmentTarget>,
138    aggregates: &dyn AggregateClassifier,
139    subqueries: &mut Vec<QueryPlan>,
140) -> Vec<crate::ast::AssignmentTarget<ScalarExpr>> {
141    targets
142        .into_iter()
143        .map(|target| {
144            target.map(|expression| lower_scalar_expression(expression, aggregates, subqueries))
145        })
146        .collect()
147}
148
149pub(super) fn lower_merge_when(
150    clause: crate::ast::MergeWhen,
151    aggregates: &dyn AggregateClassifier,
152    subqueries: &mut Vec<QueryPlan>,
153) -> MergeWhenPlan {
154    let mut lower_optional = |expression: Option<Expr>| {
155        expression.map(|expression| lower_scalar_expression(expression, aggregates, subqueries))
156    };
157    match clause {
158        crate::ast::MergeWhen::UpdateMatched {
159            condition,
160            assignments,
161        } => {
162            let condition = lower_optional(condition);
163            let assignments = lower_assignments(assignments, aggregates, subqueries);
164            MergeWhenPlan::UpdateMatched {
165                condition,
166                assignments,
167            }
168        }
169        crate::ast::MergeWhen::DeleteMatched { condition } => MergeWhenPlan::DeleteMatched {
170            condition: lower_optional(condition),
171        },
172        crate::ast::MergeWhen::UpdateNotMatchedBySource {
173            condition,
174            assignments,
175        } => {
176            let condition = lower_optional(condition);
177            let assignments = lower_assignments(assignments, aggregates, subqueries);
178            MergeWhenPlan::UpdateNotMatchedBySource {
179                condition,
180                assignments,
181            }
182        }
183        crate::ast::MergeWhen::DeleteNotMatchedBySource { condition } => {
184            MergeWhenPlan::DeleteNotMatchedBySource {
185                condition: lower_optional(condition),
186            }
187        }
188        crate::ast::MergeWhen::InsertNotMatched {
189            condition,
190            columns,
191            overriding,
192            values,
193        } => {
194            let condition = lower_optional(condition);
195            let values = values
196                .into_iter()
197                .map(|value| lower_scalar_expression(value, aggregates, subqueries))
198                .collect();
199            MergeWhenPlan::InsertNotMatched {
200                condition,
201                columns: lower_targets(columns, aggregates, subqueries),
202                overriding,
203                values,
204            }
205        }
206        crate::ast::MergeWhen::NothingMatched { condition } => MergeWhenPlan::NothingMatched {
207            condition: lower_optional(condition),
208        },
209        crate::ast::MergeWhen::NothingNotMatched { condition } => {
210            MergeWhenPlan::NothingNotMatched {
211                condition: lower_optional(condition),
212            }
213        }
214        crate::ast::MergeWhen::NothingNotMatchedBySource { condition } => {
215            MergeWhenPlan::NothingNotMatchedBySource {
216                condition: lower_optional(condition),
217            }
218        }
219    }
220}
221pub(super) fn lower_relational_root(
222    mut statement: SelectStmt,
223    aggregates: &dyn AggregateClassifier,
224) -> RelationalPlan {
225    if statement.set_op.is_none() && !statement.values.is_empty() {
226        let mut subqueries = Vec::new();
227        let rows = statement
228            .values
229            .into_iter()
230            .map(|row| {
231                row.into_iter()
232                    .map(|expr| lower_scalar_expression(expr, aggregates, &mut subqueries))
233                    .collect()
234            })
235            .collect();
236        return RelationalPlan::Values { rows, subqueries };
237    }
238    let Some(set_op) = statement.set_op.take() else {
239        return RelationalPlan::QueryBlock(Box::new(QueryBlockPlan::lower_with(
240            statement, aggregates,
241        )));
242    };
243
244    let left = if let Some(left) = set_op.left {
245        QueryPlan::lower_with(*left, aggregates)
246    } else {
247        QueryPlan {
248            analyzed_output: None,
249            analyzed_source: None,
250            analyzed_grouping: None,
251            relation_privilege_subject: None,
252            relations_bound: false,
253            ctes: Vec::new(),
254            root: RelationalPlan::QueryBlock(Box::new(QueryBlockPlan::lower_with(
255                statement, aggregates,
256            ))),
257        }
258    };
259    let right = QueryPlan::lower_with(set_op.right, aggregates);
260    let mut subqueries = Vec::new();
261    RelationalPlan::SetOp {
262        kind: set_op.kind,
263        all: set_op.all,
264        left: Box::new(left),
265        right: Box::new(right),
266        order_by: set_op
267            .combined_order_by
268            .into_iter()
269            .map(|order| OrderPlan::lower_with(order, aggregates, &mut subqueries))
270            .collect(),
271        limit: set_op
272            .combined_limit
273            .map(|expr| Box::new(lower_scalar_expression(expr, aggregates, &mut subqueries))),
274        with_ties: set_op.combined_with_ties,
275        offset: set_op
276            .combined_offset
277            .map(|expr| Box::new(lower_scalar_expression(expr, aggregates, &mut subqueries))),
278        subqueries,
279    }
280}
281
282impl QueryBlockPlan {
283    fn lower_with(statement: SelectStmt, aggregates: &dyn AggregateClassifier) -> Self {
284        debug_assert_eq!(statement.with.len(), 0);
285        debug_assert!(statement.set_op.is_none());
286        let mut subqueries = Vec::new();
287        let projections: Vec<ProjectionPlan> = statement
288            .projections
289            .into_iter()
290            .map(|projection| ProjectionPlan::lower_with(projection, aggregates, &mut subqueries))
291            .collect();
292        let windows: Vec<_> = statement
293            .windows
294            .into_iter()
295            .map(|definition| crate::ast::WindowDefinition {
296                name: definition.name,
297                inherited: definition.inherited,
298                spec: super::scalar::lower_window_spec(
299                    definition.spec,
300                    aggregates,
301                    &mut subqueries,
302                ),
303            })
304            .collect();
305        let mut block = Self {
306            deferred_outer_rewrites: Vec::new(),
307            windows,
308            projections,
309            privilege_columns: uqa_core::memory::OwnedSet::new(),
310            from: statement
311                .from
312                .map(|source| SourcePlan::lower_with(source, aggregates, &mut subqueries)),
313            r#where: statement
314                .r#where
315                .map(|expr| lower_scalar_expression(expr, aggregates, &mut subqueries)),
316            compute: ComputePlan::Project,
317            group_by: statement
318                .group_by
319                .into_iter()
320                .map(|expr| lower_scalar_expression(expr, aggregates, &mut subqueries))
321                .collect(),
322            grouping_sets: statement
323                .grouping_sets
324                .into_iter()
325                .map(|set| {
326                    set.into_iter()
327                        .map(|expr| lower_scalar_expression(expr, aggregates, &mut subqueries))
328                        .collect()
329                })
330                .collect(),
331            group_distinct: statement.group_distinct,
332            having: statement
333                .having
334                .map(|expr| lower_scalar_expression(expr, aggregates, &mut subqueries)),
335            order_by: statement
336                .order_by
337                .into_iter()
338                .map(|order| OrderPlan::lower_with(order, aggregates, &mut subqueries))
339                .collect(),
340            limit: statement
341                .limit
342                .map(|expr| lower_scalar_expression(expr, aggregates, &mut subqueries)),
343            with_ties: statement.with_ties,
344            offset: statement
345                .offset
346                .map(|expr| lower_scalar_expression(expr, aggregates, &mut subqueries)),
347            distinct: statement.distinct,
348            distinct_on: statement
349                .distinct_on
350                .into_iter()
351                .map(|expr| lower_scalar_expression(expr, aggregates, &mut subqueries))
352                .collect(),
353            subqueries,
354            access: AccessPathPlan::Row,
355            locking: statement.locking,
356        };
357        block.compute = block.compute_kind(aggregates);
358        block
359    }
360
361    /// Expression nodes evaluated while executing this query block. Query
362    /// bodies under `FROM (SELECT ...)` are excluded because their child plan
363    /// installs its own expression scope when it executes.
364    #[must_use]
365    pub fn expressions(&self) -> Vec<&ScalarExpr> {
366        let mut expressions = Vec::new();
367        self.visit_expressions(&mut |expression| expressions.push(expression));
368        expressions
369    }
370
371    /// Borrow direct source roots followed by this query's own roots. Derived-query bodies and scalar-query arenas keep their separate namespaces.
372    pub fn visit_expressions<'a>(&'a self, visit: &mut dyn FnMut(&'a ScalarExpr)) {
373        self.try_visit_expressions(&mut |expression| {
374            visit(expression);
375            Ok::<_, std::convert::Infallible>(true)
376        })
377        .unwrap_or_else(|never| match never {});
378    }
379
380    /// Visit direct expression roots in initialization order. Return false when the callback stops successfully; an error also stops before the next root.
381    pub fn try_visit_expressions<'a, E>(
382        &'a self,
383        visit: &mut dyn FnMut(&'a ScalarExpr) -> Result<bool, E>,
384    ) -> Result<bool, E> {
385        if let Some(source) = &self.from {
386            if !source.try_visit_expressions(visit)? {
387                return Ok(false);
388            }
389        }
390        for expression in self.query_expressions() {
391            if !visit(expression)? {
392                return Ok(false);
393            }
394        }
395        Ok(true)
396    }
397
398    /// Expressions at this query level, excluding FROM-item inputs and join conditions, which have their own namespaces.
399    pub fn query_expressions(&self) -> impl Iterator<Item = &ScalarExpr> {
400        // Scan projections precede scan qualifications; aggregate and window outputs follow their input scan.
401        let (before, after): (&[ProjectionPlan], &[ProjectionPlan]) =
402            if matches!(self.compute, ComputePlan::Project) {
403                (&self.projections, &[])
404            } else {
405                (&[], &self.projections)
406            };
407        before
408            .iter()
409            .map(|projection| &projection.expr)
410            .chain(self.r#where.as_ref())
411            .chain(after.iter().map(|projection| &projection.expr))
412            .chain(&self.group_by)
413            .chain(self.grouping_sets.iter().flatten())
414            .chain(self.having.as_ref())
415            .chain(self.order_by.iter().map(|order| &order.expr))
416            .chain(self.limit.as_ref())
417            .chain(self.offset.as_ref())
418            .chain(&self.distinct_on)
419            .chain(
420                self.windows
421                    .iter()
422                    .flat_map(|window| window.spec.expressions()),
423            )
424    }
425}
426
427impl SourcePlan {
428    /// SQL-visible relation qualifier for a non-join FROM item. `PostgreSQL` uses the local function name, not its schema-qualified lookup identity, when a table function has no explicit alias.
429    #[must_use]
430    pub fn visible_qualifier(&self) -> Option<&str> {
431        match self {
432            crate::plan::SourcePlan::RetainedRows(_) => None,
433            Self::Table {
434                qualifier, alias, ..
435            } => Some(alias.as_deref().unwrap_or(qualifier)),
436            Self::Function {
437                output_name, alias, ..
438            } => Some(alias.as_deref().unwrap_or(output_name)),
439            Self::FunctionGroup {
440                functions, alias, ..
441            } => alias.as_deref().or_else(|| {
442                functions
443                    .first()
444                    .map(|function| function.output_name.as_str())
445            }),
446            Self::Values {
447                alias,
448                internal_relation,
449                ..
450            } => internal_relation
451                .is_none()
452                .then_some(alias.as_deref())
453                .flatten(),
454            Self::Subquery { alias, .. } => alias.as_deref(),
455            Self::Join { alias, .. } => alias.as_deref(),
456        }
457    }
458
459    #[expect(
460        clippy::too_many_lines,
461        reason = "plan lowering preserves exhaustive variants and structural identities"
462    )]
463    pub(super) fn lower_with(
464        source: FromClause,
465        aggregates: &dyn AggregateClassifier,
466        subqueries: &mut Vec<QueryPlan>,
467    ) -> Self {
468        match source {
469            FromClause::RetainedRows(source) => Self::RetainedRows(source),
470            FromClause::Table {
471                name,
472                qualifier,
473                alias,
474                column_aliases,
475                bound_columns,
476                include_descendants,
477            } => Self::Table {
478                executable_query: None,
479                name,
480                qualifier,
481                alias,
482                column_aliases,
483                bound_columns,
484                include_descendants,
485            },
486            FromClause::Join {
487                comma,
488                left,
489                right,
490                kind,
491                on,
492                using,
493                natural,
494                alias,
495                column_aliases,
496                lateral,
497            } => Self::Join {
498                comma,
499                left: Box::new(Self::lower_with(*left, aggregates, subqueries)),
500                right: Box::new(Self::lower_with(*right, aggregates, subqueries)),
501                kind,
502                on: on.map(|expr| lower_scalar_expression(expr, aggregates, subqueries)),
503                using,
504                natural,
505                alias,
506                column_aliases,
507                lateral,
508                strategy: JoinExecutionStrategy::Auto,
509            },
510            FromClause::Values {
511                lateral,
512                rows,
513                alias,
514                column_aliases,
515                internal_relation,
516                internal_column_types,
517                internal_column_collations,
518            } => Self::Values {
519                lateral,
520                rows: rows
521                    .into_iter()
522                    .map(|row| {
523                        row.into_iter()
524                            .map(|expr| lower_scalar_expression(expr, aggregates, subqueries))
525                            .collect()
526                    })
527                    .collect(),
528                alias,
529                column_aliases,
530                internal_relation,
531                internal_column_types,
532                internal_column_collations,
533            },
534            FromClause::Function {
535                name,
536                binding,
537                output_name,
538                relations,
539                args,
540                alias,
541                column_aliases,
542                ordinality,
543                column_types,
544            } => Self::Function {
545                name,
546                binding,
547                output_name,
548                relations,
549                args: args
550                    .into_iter()
551                    .map(|expr| lower_scalar_expression(expr, aggregates, subqueries))
552                    .collect(),
553                alias,
554                column_aliases,
555                ordinality,
556                column_types,
557            },
558            FromClause::FunctionGroup {
559                functions,
560                alias,
561                column_aliases,
562                ordinality,
563            } => Self::FunctionGroup {
564                functions: functions
565                    .into_iter()
566                    .map(|function| TableFunctionPlan {
567                        name: function.name,
568                        binding: function.binding,
569                        output_name: function.output_name,
570                        relations: function.relations,
571                        args: function
572                            .args
573                            .into_iter()
574                            .map(|expr| lower_scalar_expression(expr, aggregates, subqueries))
575                            .collect(),
576                        column_aliases: function.column_aliases,
577                        column_types: function.column_types,
578                    })
579                    .collect(),
580                alias,
581                column_aliases,
582                ordinality,
583            },
584            FromClause::Subquery {
585                lateral,
586                body,
587                alias,
588                column_aliases,
589            } => Self::Subquery {
590                captured_output: None,
591                lateral,
592                body: Box::new(QueryPlan::lower_with(*body, aggregates)),
593                alias,
594                column_aliases,
595            },
596        }
597    }
598
599    /// Visit scalar roots in this source's expression namespace. Derived-query bodies retain their own scope. Return false on a successful callback stop; an error also stops before the next root.
600    pub fn try_visit_expressions<'a, E>(
601        &'a self,
602        visit: &mut dyn FnMut(&'a ScalarExpr) -> Result<bool, E>,
603    ) -> Result<bool, E> {
604        match self {
605            Self::RetainedRows(_) | Self::Table { .. } | Self::Subquery { .. } => {}
606            Self::Join {
607                left, right, on, ..
608            } => {
609                if !left.try_visit_expressions(visit)? || !right.try_visit_expressions(visit)? {
610                    return Ok(false);
611                }
612                if let Some(on) = on {
613                    if !visit(on)? {
614                        return Ok(false);
615                    }
616                }
617            }
618            Self::Values { rows, .. } => {
619                for expression in rows.iter().flatten() {
620                    if !visit(expression)? {
621                        return Ok(false);
622                    }
623                }
624            }
625            Self::Function { args, .. } => {
626                for expression in args {
627                    if !visit(expression)? {
628                        return Ok(false);
629                    }
630                }
631            }
632            Self::FunctionGroup { functions, .. } => {
633                for expression in functions.iter().flat_map(|function| &function.args) {
634                    if !visit(expression)? {
635                        return Ok(false);
636                    }
637                }
638            }
639        }
640        Ok(true)
641    }
642
643    /// Append scalar inputs owned by this source, including JOIN predicates; nested query bodies retain their own expression scope.
644    pub fn push_expressions<'a>(&'a self, output: &mut Vec<&'a ScalarExpr>) {
645        self.try_visit_expressions(&mut |expression| {
646            output.push(expression);
647            Ok::<_, std::convert::Infallible>(true)
648        })
649        .unwrap_or_else(|never| match never {});
650    }
651
652    pub fn collect_tables(&self, output: &mut Vec<(String, Option<String>)>) {
653        match self {
654            crate::plan::SourcePlan::RetainedRows(_) => {}
655            Self::Table {
656                name,
657                qualifier,
658                alias,
659                ..
660            } => output.push((
661                name.clone(),
662                Some(alias.as_ref().unwrap_or(qualifier).clone()),
663            )),
664            Self::Join { left, right, .. } => {
665                left.collect_tables(output);
666                right.collect_tables(output);
667            }
668            Self::Values { .. }
669            | Self::Function { .. }
670            | Self::FunctionGroup { .. }
671            | Self::Subquery { .. } => {}
672        }
673    }
674}
675
676impl ProjectionPlan {
677    pub(super) fn lower_with(
678        projection: Projection,
679        aggregates: &dyn AggregateClassifier,
680        subqueries: &mut Vec<QueryPlan>,
681    ) -> Self {
682        Self {
683            expr: lower_scalar_expression(projection.expr, aggregates, subqueries),
684            alias: projection.alias,
685        }
686    }
687}
688
689impl OrderPlan {
690    fn lower_with(
691        order: OrderBy,
692        aggregates: &dyn AggregateClassifier,
693        subqueries: &mut Vec<QueryPlan>,
694    ) -> Self {
695        Self {
696            expr: lower_scalar_expression(order.expr, aggregates, subqueries),
697            descending: order.descending,
698            nulls: order.nulls,
699        }
700    }
701}
702
703impl ExpressionPlan {
704    /// Normalize predecessor range nodes while retaining bindings and assigning independent subquery slots to repeated operands.
705    pub fn upgrade_legacy_range_predicates(&mut self) -> Result<bool, crate::SQLError> {
706        crate::type_resolution::between::restore_expression(self)
707    }
708
709    #[must_use]
710    pub fn lower(expression: Expr) -> Self {
711        Self::lower_with(expression, &NoRegisteredAggregates)
712    }
713
714    pub fn lower_with(expression: Expr, aggregates: &dyn AggregateClassifier) -> Self {
715        let mut subqueries = Vec::new();
716        let scalar = lower_scalar_expression(expression, aggregates, &mut subqueries);
717        Self { scalar, subqueries }
718    }
719}