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