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            Self::Table {
418                qualifier, alias, ..
419            } => Some(alias.as_deref().unwrap_or(qualifier)),
420            Self::Function {
421                output_name, alias, ..
422            } => Some(alias.as_deref().unwrap_or(output_name)),
423            Self::FunctionGroup {
424                functions, alias, ..
425            } => alias.as_deref().or_else(|| {
426                functions
427                    .first()
428                    .map(|function| function.output_name.as_str())
429            }),
430            Self::Values {
431                alias,
432                internal_relation,
433                ..
434            } => internal_relation
435                .is_none()
436                .then_some(alias.as_deref())
437                .flatten(),
438            Self::Subquery { alias, .. } => alias.as_deref(),
439            Self::Join { alias, .. } => alias.as_deref(),
440        }
441    }
442
443    #[expect(
444        clippy::too_many_lines,
445        reason = "plan lowering preserves exhaustive variants and structural identities"
446    )]
447    pub(super) fn lower_with(
448        source: FromClause,
449        aggregates: &dyn AggregateClassifier,
450        subqueries: &mut Vec<QueryPlan>,
451    ) -> Self {
452        match source {
453            FromClause::Table {
454                name,
455                qualifier,
456                alias,
457                column_aliases,
458                bound_columns,
459                include_descendants,
460            } => Self::Table {
461                name,
462                qualifier,
463                alias,
464                column_aliases,
465                bound_columns,
466                include_descendants,
467            },
468            FromClause::Join {
469                left,
470                right,
471                kind,
472                on,
473                using,
474                natural,
475                alias,
476                column_aliases,
477                lateral,
478            } => Self::Join {
479                left: Box::new(Self::lower_with(*left, aggregates, subqueries)),
480                right: Box::new(Self::lower_with(*right, aggregates, subqueries)),
481                kind,
482                on: on.map(|expr| lower_scalar_expression(expr, aggregates, subqueries)),
483                using,
484                natural,
485                alias,
486                column_aliases,
487                lateral,
488                strategy: JoinExecutionStrategy::Auto,
489            },
490            FromClause::Values {
491                rows,
492                alias,
493                column_aliases,
494                internal_relation,
495                internal_column_types,
496                internal_column_collations,
497            } => Self::Values {
498                rows: rows
499                    .into_iter()
500                    .map(|row| {
501                        row.into_iter()
502                            .map(|expr| lower_scalar_expression(expr, aggregates, subqueries))
503                            .collect()
504                    })
505                    .collect(),
506                alias,
507                column_aliases,
508                internal_relation,
509                internal_column_types,
510                internal_column_collations,
511            },
512            FromClause::Function {
513                name,
514                binding,
515                output_name,
516                relations,
517                args,
518                alias,
519                column_aliases,
520                ordinality,
521                column_types,
522            } => Self::Function {
523                name,
524                binding,
525                output_name,
526                relations,
527                args: args
528                    .into_iter()
529                    .map(|expr| lower_scalar_expression(expr, aggregates, subqueries))
530                    .collect(),
531                alias,
532                column_aliases,
533                ordinality,
534                column_types,
535            },
536            FromClause::FunctionGroup {
537                functions,
538                alias,
539                column_aliases,
540                ordinality,
541            } => Self::FunctionGroup {
542                functions: functions
543                    .into_iter()
544                    .map(|function| TableFunctionPlan {
545                        name: function.name,
546                        binding: function.binding,
547                        output_name: function.output_name,
548                        relations: function.relations,
549                        args: function
550                            .args
551                            .into_iter()
552                            .map(|expr| lower_scalar_expression(expr, aggregates, subqueries))
553                            .collect(),
554                        column_aliases: function.column_aliases,
555                        column_types: function.column_types,
556                    })
557                    .collect(),
558                alias,
559                column_aliases,
560                ordinality,
561            },
562            FromClause::Subquery {
563                body,
564                alias,
565                column_aliases,
566            } => Self::Subquery {
567                body: Box::new(QueryPlan::lower_with(*body, aggregates)),
568                alias,
569                column_aliases,
570            },
571        }
572    }
573
574    /// Append scalar inputs owned by this source, including JOIN predicates; nested query bodies retain their own expression scope.
575    pub fn push_expressions<'a>(&'a self, output: &mut Vec<&'a ScalarExpr>) {
576        match self {
577            Self::Table { .. } | Self::Subquery { .. } => {}
578            Self::Join {
579                left, right, on, ..
580            } => {
581                left.push_expressions(output);
582                right.push_expressions(output);
583                if let Some(on) = on {
584                    output.push(on);
585                }
586            }
587            Self::Values { rows, .. } => {
588                for row in rows {
589                    output.extend(row);
590                }
591            }
592            Self::Function { args, .. } => output.extend(args),
593            Self::FunctionGroup { functions, .. } => {
594                for function in functions {
595                    output.extend(&function.args);
596                }
597            }
598        }
599    }
600
601    pub fn collect_tables(&self, output: &mut Vec<(String, Option<String>)>) {
602        match self {
603            Self::Table {
604                name,
605                qualifier,
606                alias,
607                ..
608            } => output.push((
609                name.clone(),
610                Some(alias.as_ref().unwrap_or(qualifier).clone()),
611            )),
612            Self::Join { left, right, .. } => {
613                left.collect_tables(output);
614                right.collect_tables(output);
615            }
616            Self::Values { .. }
617            | Self::Function { .. }
618            | Self::FunctionGroup { .. }
619            | Self::Subquery { .. } => {}
620        }
621    }
622}
623
624impl ProjectionPlan {
625    pub(super) fn lower_with(
626        projection: Projection,
627        aggregates: &dyn AggregateClassifier,
628        subqueries: &mut Vec<QueryPlan>,
629    ) -> Self {
630        Self {
631            expr: lower_scalar_expression(projection.expr, aggregates, subqueries),
632            alias: projection.alias,
633        }
634    }
635}
636
637impl OrderPlan {
638    fn lower_with(
639        order: OrderBy,
640        aggregates: &dyn AggregateClassifier,
641        subqueries: &mut Vec<QueryPlan>,
642    ) -> Self {
643        Self {
644            expr: lower_scalar_expression(order.expr, aggregates, subqueries),
645            descending: order.descending,
646            nulls: order.nulls,
647        }
648    }
649}
650
651impl ExpressionPlan {
652    /// Normalize predecessor range nodes while retaining bindings and assigning independent subquery slots to repeated operands.
653    pub fn upgrade_legacy_range_predicates(&mut self) -> Result<bool, crate::SQLError> {
654        crate::type_resolution::between::restore_expression(self)
655    }
656
657    #[must_use]
658    pub fn lower(expression: Expr) -> Self {
659        Self::lower_with(expression, &NoRegisteredAggregates)
660    }
661
662    pub fn lower_with(expression: Expr, aggregates: &dyn AggregateClassifier) -> Self {
663        let mut subqueries = Vec::new();
664        let scalar = lower_scalar_expression(expression, aggregates, &mut subqueries);
665        Self { scalar, subqueries }
666    }
667}