Skip to main content

uqa_sql/semantics/
aggregates.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Aggregate discovery and expression equivalence for SQL grouping.
8
9use crate::plan::{AggregateClassifier, ProjectionPlan, QueryBlockPlan};
10use crate::ScalarExpr;
11use uqa_core::Value;
12
13#[cfg(test)]
14mod tests;
15
16pub fn exprs_match(lhs: &ScalarExpr, rhs: &ScalarExpr) -> bool {
17    match (lhs, rhs) {
18        (ScalarExpr::RetainedLiteral(left), ScalarExpr::RetainedLiteral(right)) => left == right,
19        (ScalarExpr::RetainedLiteral(literal), other)
20        | (other, ScalarExpr::RetainedLiteral(literal)) => literal
21            .materialize()
22            .is_ok_and(|literal| exprs_match(&literal, other)),
23        (ScalarExpr::Collated { .. }, ScalarExpr::Collated { .. }) => {
24            collated_exprs_match(lhs, rhs)
25        }
26        (ScalarExpr::Star, ScalarExpr::Star) => true,
27        (ScalarExpr::QualifiedStar(a), ScalarExpr::QualifiedStar(b)) => a == b,
28        (ScalarExpr::Column(a), ScalarExpr::Column(b)) => a == b,
29        (
30            ScalarExpr::QualifiedColumn {
31                qualifier: aq,
32                column: ac,
33                ..
34            },
35            ScalarExpr::QualifiedColumn {
36                qualifier: bq,
37                column: bc,
38                ..
39            },
40        ) => aq == bq && ac == bc,
41        (ScalarExpr::Column(c), ScalarExpr::QualifiedColumn { column, .. })
42        | (ScalarExpr::QualifiedColumn { column, .. }, ScalarExpr::Column(c)) => c == column,
43        (ScalarExpr::Literal(a), ScalarExpr::Literal(b)) => literals_equal(a, b),
44        (ScalarExpr::TypedLiteral { .. }, ScalarExpr::TypedLiteral { .. }) => {
45            typed_literals_match(lhs, rhs)
46        }
47        (ScalarExpr::Param(a), ScalarExpr::Param(b)) => a == b,
48        (ScalarExpr::Position(a), ScalarExpr::Position(b)) => a == b,
49        (ScalarExpr::InternalColumn(a), ScalarExpr::InternalColumn(b)) => a == b,
50        (ScalarExpr::Func { .. }, ScalarExpr::Func { .. }) => function_exprs_match(lhs, rhs),
51        (
52            ScalarExpr::Binary {
53                op: ao,
54                lhs: al,
55                rhs: ar,
56            },
57            ScalarExpr::Binary {
58                op: bo,
59                lhs: bl,
60                rhs: br,
61            },
62        ) => ao == bo && exprs_match(al, bl) && exprs_match(ar, br),
63        (ScalarExpr::And(a), ScalarExpr::And(b))
64        | (ScalarExpr::Or(a), ScalarExpr::Or(b))
65        | (ScalarExpr::Array(a), ScalarExpr::Array(b))
66        | (ScalarExpr::Row(a), ScalarExpr::Row(b)) => {
67            a.len() == b.len() && a.iter().zip(b.iter()).all(|(x, y)| exprs_match(x, y))
68        }
69        (ScalarExpr::Not(a), ScalarExpr::Not(b))
70        | (ScalarExpr::UnaryMinus(a), ScalarExpr::UnaryMinus(b)) => exprs_match(a, b),
71        (ScalarExpr::CompositeRow { .. }, ScalarExpr::CompositeRow { .. }) => {
72            composite_rows_match(lhs, rhs)
73        }
74        (
75            ScalarExpr::Cast {
76                expr: a, ty: at, ..
77            },
78            ScalarExpr::Cast {
79                expr: b, ty: bt, ..
80            },
81        ) => at == bt && exprs_match(a, b),
82        _ => false,
83    }
84}
85
86fn function_exprs_match(lhs: &ScalarExpr, rhs: &ScalarExpr) -> bool {
87    let (
88        ScalarExpr::Func {
89            order_syntax: aos,
90            name: an,
91            binding: ab,
92            args: aa,
93            distinct: ad,
94            order_by: ao,
95            filter: af,
96        },
97        ScalarExpr::Func {
98            order_syntax: bos,
99            name: bn,
100            binding: bb,
101            args: ba,
102            distinct: bd,
103            order_by: bo,
104            filter: bf,
105        },
106    ) = (lhs, rhs)
107    else {
108        return false;
109    };
110    an.eq_ignore_ascii_case(bn)
111        && ab == bb
112        && ad == bd
113        && aos == bos
114        && aa.len() == ba.len()
115        && aa.iter().zip(ba.iter()).all(|(x, y)| exprs_match(x, y))
116        && ao.len() == bo.len()
117        && ao.iter().zip(bo.iter()).all(|(x, y)| {
118            x.descending == y.descending && x.nulls == y.nulls && exprs_match(&x.expr, &y.expr)
119        })
120        && match (af.as_deref(), bf.as_deref()) {
121            (None, None) => true,
122            (Some(x), Some(y)) => exprs_match(x, y),
123            _ => false,
124        }
125}
126
127fn collated_exprs_match(lhs: &ScalarExpr, rhs: &ScalarExpr) -> bool {
128    let (
129        ScalarExpr::Collated {
130            expr: left,
131            ty: left_type,
132            collation: left_collation,
133        },
134        ScalarExpr::Collated {
135            expr: right,
136            ty: right_type,
137            collation: right_collation,
138        },
139    ) = (lhs, rhs)
140    else {
141        return false;
142    };
143    left_type == right_type && left_collation == right_collation && exprs_match(left, right)
144}
145
146fn composite_rows_match(lhs: &ScalarExpr, rhs: &ScalarExpr) -> bool {
147    let (
148        ScalarExpr::CompositeRow {
149            items: a,
150            binding: ab,
151            bound_type: at,
152        },
153        ScalarExpr::CompositeRow {
154            items: b,
155            binding: bb,
156            bound_type: bt,
157        },
158    ) = (lhs, rhs)
159    else {
160        return false;
161    };
162    ab == bb && at == bt && a.len() == b.len() && a.iter().zip(b).all(|(a, b)| exprs_match(a, b))
163}
164
165fn typed_literals_match(lhs: &ScalarExpr, rhs: &ScalarExpr) -> bool {
166    let (
167        ScalarExpr::TypedLiteral {
168            value: av,
169            ty: at,
170            bound_type: ab,
171            parameter_index: ap,
172            composite_source: ac,
173            collation_oid: ao,
174        },
175        ScalarExpr::TypedLiteral {
176            value: bv,
177            ty: bt,
178            bound_type: bb,
179            parameter_index: bp,
180            composite_source: bc,
181            collation_oid: bo,
182        },
183    ) = (lhs, rhs)
184    else {
185        return false;
186    };
187    at == bt && ab == bb && ap == bp && ac == bc && ao == bo && literals_equal(av, bv)
188}
189
190pub fn literals_equal(a: &Value, b: &Value) -> bool {
191    a.has_same_representation(b)
192}
193
194pub fn has_aggregate(aggregates: &dyn AggregateClassifier, projections: &[ProjectionPlan]) -> bool {
195    projections
196        .iter()
197        .any(|p| contains_aggregate(aggregates, &p.expr))
198}
199
200pub fn is_aggregate(aggregates: &dyn AggregateClassifier, expr: &ScalarExpr) -> bool {
201    is_builtin_aggregate(expr)
202        || matches!(expr, ScalarExpr::Func { name, .. } if aggregates.is_registered_aggregate(name))
203}
204
205pub use super::is_builtin_aggregate;
206
207pub fn aggregate_exprs<'a>(
208    aggregates: &dyn AggregateClassifier,
209    projections: &'a [ProjectionPlan],
210) -> Vec<&'a ScalarExpr> {
211    let mut out = Vec::new();
212    for projection in projections {
213        collect_aggregate_exprs(aggregates, &projection.expr, &mut out);
214    }
215    out
216}
217
218/// Aggregate states needed by a query block, in accumulator order.
219///
220/// Projection aggregates remain first (including repeated expressions) because
221/// projection rewriting consumes them positionally. Aggregates referenced only
222/// by HAVING are appended once as hidden targets, matching `PostgreSQL`'s rule
223/// that HAVING need not expose an aggregate in the SELECT list.
224pub fn aggregate_targets<'a>(
225    aggregates: &dyn AggregateClassifier,
226    statement: &'a QueryBlockPlan,
227) -> Vec<&'a ScalarExpr> {
228    let mut targets = aggregate_exprs(aggregates, &statement.projections);
229    if let Some(having) = statement.having.as_ref() {
230        let mut hidden = Vec::new();
231        collect_aggregate_exprs(aggregates, having, &mut hidden);
232        for aggregate in hidden {
233            if !targets
234                .iter()
235                .any(|existing| exprs_match(existing, aggregate))
236            {
237                targets.push(aggregate);
238            }
239        }
240    }
241    targets
242}
243
244pub fn collect_aggregate_exprs<'a>(
245    aggregates: &dyn AggregateClassifier,
246    expr: &'a ScalarExpr,
247    out: &mut Vec<&'a ScalarExpr>,
248) {
249    if is_aggregate(aggregates, expr) {
250        out.push(expr);
251        return;
252    }
253    match expr {
254        ScalarExpr::Func { args, filter, .. } => {
255            for arg in args {
256                collect_aggregate_exprs(aggregates, arg, out);
257            }
258            if let Some(filter) = filter.as_deref() {
259                collect_aggregate_exprs(aggregates, filter, out);
260            }
261        }
262        ScalarExpr::Array(items)
263        | ScalarExpr::Row(items)
264        | ScalarExpr::CompositeRow { items, .. }
265        | ScalarExpr::And(items)
266        | ScalarExpr::Or(items) => {
267            for item in items {
268                collect_aggregate_exprs(aggregates, item, out);
269            }
270        }
271        ScalarExpr::Binary { lhs, rhs, .. } => {
272            collect_aggregate_exprs(aggregates, lhs, out);
273            collect_aggregate_exprs(aggregates, rhs, out);
274        }
275        ScalarExpr::Not(inner)
276        | ScalarExpr::UnaryMinus(inner)
277        | ScalarExpr::Cast { expr: inner, .. }
278        | ScalarExpr::Collated { expr: inner, .. } => {
279            collect_aggregate_exprs(aggregates, inner, out);
280        }
281        ScalarExpr::IsNull { expr, .. } => collect_aggregate_exprs(aggregates, expr, out),
282        ScalarExpr::Between { expr, low, high } => {
283            collect_aggregate_exprs(aggregates, expr, out);
284            collect_aggregate_exprs(aggregates, low, out);
285            collect_aggregate_exprs(aggregates, high, out);
286        }
287        ScalarExpr::InList { expr, list, .. } => {
288            collect_aggregate_exprs(aggregates, expr, out);
289            for item in list {
290                collect_aggregate_exprs(aggregates, item, out);
291            }
292        }
293        ScalarExpr::Case {
294            base,
295            when,
296            else_branch,
297        } => {
298            if let Some(base) = base.as_deref() {
299                collect_aggregate_exprs(aggregates, base, out);
300            }
301            for (condition, result) in when {
302                collect_aggregate_exprs(aggregates, condition, out);
303                collect_aggregate_exprs(aggregates, result, out);
304            }
305            if let Some(else_branch) = else_branch.as_deref() {
306                collect_aggregate_exprs(aggregates, else_branch, out);
307            }
308        }
309        ScalarExpr::InSubquery { expr, .. } => collect_aggregate_exprs(aggregates, expr, out),
310        ScalarExpr::Default
311        | ScalarExpr::Star
312        | ScalarExpr::QualifiedStar(_)
313        | ScalarExpr::Column(_)
314        | ScalarExpr::Position(_)
315        | ScalarExpr::InternalColumn(_)
316        | ScalarExpr::QualifiedColumn { .. }
317        | ScalarExpr::Literal(_)
318        | ScalarExpr::TypedLiteral { .. }
319        | ScalarExpr::RetainedLiteral(_)
320        | ScalarExpr::Param(_)
321        | ScalarExpr::WindowCall { .. }
322        | ScalarExpr::ScalarSubquery(_)
323        | ScalarExpr::Exists { .. } => {}
324    }
325}
326
327pub fn contains_aggregate(aggregates: &dyn AggregateClassifier, expr: &ScalarExpr) -> bool {
328    let mut found = Vec::new();
329    collect_aggregate_exprs(aggregates, expr, &mut found);
330    !found.is_empty()
331}
332
333/// Collect the top-level column names an expression reads. Returns
334/// `false` when the expression can reach arbitrary fields (`*`,
335/// subqueries, window calls), in which case callers must materialise
336/// whole documents.
337pub fn expr_references_columns(expr: &ScalarExpr) -> bool {
338    match expr {
339        ScalarExpr::Star
340        | ScalarExpr::QualifiedStar(_)
341        | ScalarExpr::Column(_)
342        | ScalarExpr::Position(_)
343        | ScalarExpr::InternalColumn(_)
344        | ScalarExpr::QualifiedColumn { .. } => true,
345        ScalarExpr::Func { args, filter, .. } => {
346            args.iter().any(expr_references_columns)
347                || filter.as_deref().is_some_and(expr_references_columns)
348        }
349        ScalarExpr::Array(items)
350        | ScalarExpr::Row(items)
351        | ScalarExpr::CompositeRow { items, .. }
352        | ScalarExpr::And(items)
353        | ScalarExpr::Or(items) => items.iter().any(expr_references_columns),
354        ScalarExpr::Binary { lhs, rhs, .. } => {
355            expr_references_columns(lhs) || expr_references_columns(rhs)
356        }
357        ScalarExpr::Not(inner)
358        | ScalarExpr::UnaryMinus(inner)
359        | ScalarExpr::Cast { expr: inner, .. }
360        | ScalarExpr::Collated { expr: inner, .. } => expr_references_columns(inner),
361        ScalarExpr::IsNull { expr, .. } => expr_references_columns(expr),
362        ScalarExpr::Between { expr, low, high } => {
363            expr_references_columns(expr)
364                || expr_references_columns(low)
365                || expr_references_columns(high)
366        }
367        ScalarExpr::InList { expr, list, .. } => {
368            expr_references_columns(expr) || list.iter().any(expr_references_columns)
369        }
370        ScalarExpr::WindowCall { args, filter, .. } => {
371            args.iter().any(expr_references_columns)
372                || filter.as_deref().is_some_and(expr_references_columns)
373        }
374        ScalarExpr::Case {
375            base,
376            when,
377            else_branch,
378        } => {
379            base.as_deref().is_some_and(expr_references_columns)
380                || when.iter().any(|(condition, result)| {
381                    expr_references_columns(condition) || expr_references_columns(result)
382                })
383                || else_branch.as_deref().is_some_and(expr_references_columns)
384        }
385        ScalarExpr::InSubquery { expr, .. } => expr_references_columns(expr),
386        ScalarExpr::ScalarSubquery(_) | ScalarExpr::Exists { .. } => true,
387        ScalarExpr::Default
388        | ScalarExpr::Literal(_)
389        | ScalarExpr::TypedLiteral { .. }
390        | ScalarExpr::RetainedLiteral(_)
391        | ScalarExpr::Param(_) => false,
392    }
393}
394
395mod slots;
396pub use slots::{
397    aggregate_slot_index, compile_group_slots, compile_having_aggregate_slots,
398    compile_projection_aggregate_slots, select_grouping_set,
399};