Skip to main content

uqa_sql/plan/
subqueries.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Compact scalar-subquery arenas after expression rewrites discard inputs.
8
9use crate::ScalarExpr;
10use std::collections::BTreeMap;
11
12use super::{CommandPlan, QueryPlan, RelationalPlan, SourcePlan};
13
14mod transfer;
15pub use transfer::transfer_expression;
16
17mod transform;
18pub(crate) use transform::{
19    copy_occurrences, query_nodes as rewrite_query_with_arenas, rewrite_expression_with_arena,
20    rewrite_with_arenas,
21};
22
23/// Drop unreferenced query children and remap local command expressions without evaluating them.
24pub fn prune_command(command: &mut CommandPlan) {
25    let Some(arena) = command_arena(command) else {
26        return;
27    };
28    let arena = std::mem::take(arena);
29    let arena = compact(arena, |visitor| {
30        for expression in command.expressions_mut() {
31            super::rewrite_scalar_expression(expression, visitor);
32        }
33        if let Some(source) = command.source_input_mut() {
34            visit_source(source, visitor);
35        }
36    });
37    if let Some(target) = command_arena(command) {
38        *target = arena;
39    }
40}
41
42fn command_arena(command: &mut CommandPlan) -> Option<&mut Vec<QueryPlan>> {
43    match command {
44        CommandPlan::Insert(plan) => Some(&mut plan.subqueries),
45        CommandPlan::Update(plan) => Some(&mut plan.subqueries),
46        CommandPlan::Delete(plan) => Some(&mut plan.subqueries),
47        CommandPlan::Merge(plan) => Some(&mut plan.subqueries),
48        _ => None,
49    }
50}
51
52/// Drop unreferenced query children and remap local query expressions, including canonical window definitions.
53pub fn prune_query(query: &mut QueryPlan) {
54    let arena = std::mem::take(query_arena(&mut query.root));
55    let arena = compact(arena, |visitor| visit_root(&mut query.root, visitor));
56    *query_arena(&mut query.root) = arena;
57}
58
59/// Retain only query children actually referenced by one scalar expression.
60pub fn prune_expression(plan: &mut super::ExpressionPlan) {
61    let arena = std::mem::take(&mut plan.subqueries);
62    plan.subqueries = compact(arena, |visitor| {
63        super::rewrite_scalar_expression(&mut plan.scalar, visitor);
64    });
65}
66
67fn query_arena(root: &mut RelationalPlan) -> &mut Vec<QueryPlan> {
68    match root {
69        RelationalPlan::QueryBlock(block) => &mut block.subqueries,
70        RelationalPlan::Values { subqueries, .. } | RelationalPlan::SetOp { subqueries, .. } => {
71            subqueries
72        }
73    }
74}
75
76fn compact(
77    arena: Vec<QueryPlan>,
78    mut visit: impl FnMut(&mut dyn FnMut(&mut ScalarExpr)),
79) -> Vec<QueryPlan> {
80    if arena.is_empty() {
81        return arena;
82    }
83    let mut remap = BTreeMap::new();
84    visit(&mut |expression| {
85        if let Some(id) = subquery_id(expression) {
86            remap.insert(*id, 0);
87        }
88    });
89    // Invalid references retain their original diagnostic rather than aliasing
90    // a surviving entry after compaction.
91    if remap.keys().any(|id| *id >= arena.len()) || remap.len() == arena.len() {
92        return arena;
93    }
94    for (position, value) in remap.values_mut().enumerate() {
95        *value = position;
96    }
97    visit(&mut |expression| {
98        if let Some(id) = subquery_id(expression) {
99            *id = remap[id];
100        }
101    });
102    arena
103        .into_iter()
104        .enumerate()
105        .filter_map(|(id, query)| remap.contains_key(&id).then_some(query))
106        .collect()
107}
108
109fn subquery_id(expression: &mut ScalarExpr) -> Option<&mut usize> {
110    match expression {
111        ScalarExpr::ScalarSubquery(id)
112        | ScalarExpr::Exists { subquery: id, .. }
113        | ScalarExpr::InSubquery { subquery: id, .. } => Some(id),
114        _ => None,
115    }
116}
117
118pub(crate) fn visit_root(root: &mut RelationalPlan, visitor: &mut dyn FnMut(&mut ScalarExpr)) {
119    match root {
120        RelationalPlan::QueryBlock(block) => visit_block(block, visitor),
121        RelationalPlan::Values { rows, .. } => {
122            for expression in rows.iter_mut().flatten() {
123                super::rewrite_scalar_expression(expression, visitor);
124            }
125        }
126        RelationalPlan::SetOp {
127            order_by,
128            limit,
129            offset,
130            ..
131        } => {
132            for expression in order_by
133                .iter_mut()
134                .map(|order| &mut order.expr)
135                .chain(limit.as_deref_mut())
136                .chain(offset.as_deref_mut())
137            {
138                super::rewrite_scalar_expression(expression, visitor);
139            }
140        }
141    }
142}
143
144fn visit_source(source: &mut SourcePlan, visitor: &mut dyn FnMut(&mut ScalarExpr)) {
145    match source {
146        crate::plan::SourcePlan::RetainedRows(_) => {}
147        SourcePlan::Join {
148            left, right, on, ..
149        } => {
150            visit_source(left, visitor);
151            visit_source(right, visitor);
152            if let Some(on) = on {
153                super::rewrite_scalar_expression(on, visitor);
154            }
155        }
156        SourcePlan::Values { rows, .. } => {
157            for expression in rows.iter_mut().flatten() {
158                super::rewrite_scalar_expression(expression, visitor);
159            }
160        }
161        SourcePlan::Function { args, .. } => {
162            for argument in args {
163                super::rewrite_scalar_expression(argument, visitor);
164            }
165        }
166        SourcePlan::FunctionGroup { functions, .. } => {
167            for argument in functions.iter_mut().flat_map(|function| &mut function.args) {
168                super::rewrite_scalar_expression(argument, visitor);
169            }
170        }
171        // A derived query owns its own scalar-subquery arena.
172        SourcePlan::Subquery { .. } | SourcePlan::Table { .. } => {}
173    }
174}
175
176fn visit_block(block: &mut super::QueryBlockPlan, visitor: &mut dyn FnMut(&mut ScalarExpr)) {
177    if let Some(source) = &mut block.from {
178        visit_source(source, visitor);
179    }
180    for expression in block
181        .projections
182        .iter_mut()
183        .map(|projection| &mut projection.expr)
184        .chain(block.r#where.iter_mut())
185        .chain(block.group_by.iter_mut())
186        .chain(block.grouping_sets.iter_mut().flatten())
187        .chain(block.having.iter_mut())
188        .chain(block.order_by.iter_mut().map(|order| &mut order.expr))
189        .chain(block.limit.iter_mut())
190        .chain(block.offset.iter_mut())
191        .chain(block.distinct_on.iter_mut())
192        .chain(
193            block
194                .windows
195                .iter_mut()
196                .flat_map(|window| window.spec.expressions_mut()),
197        )
198    {
199        super::rewrite_scalar_expression(expression, visitor);
200    }
201}