Skip to main content

uqa_sql/semantics/
input_values.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Input-value traversal for output liveness, distinct from row-count demand.
8
9use crate::{SQLError, ScalarExpr};
10use uqa_core::memory::ProductionControl;
11
12/// Traverse values observed by an expression. COUNT(*) consumes rows, while its FILTER and ORDER BY still consume their own input values.
13pub fn visit_input_values(expression: &ScalarExpr, visitor: &mut impl FnMut(&ScalarExpr)) {
14    try_visit_input_values(expression, &mut |node| {
15        visitor(node);
16        Ok::<_, std::convert::Infallible>(())
17    })
18    .unwrap_or_else(|never| match never {});
19}
20
21/// Lend observed input values in traversal order and stop on the first callback error. COUNT(*) keeps its row demand separate from the values used by its FILTER and ORDER BY.
22pub fn try_visit_input_values<'a, E>(
23    expression: &'a ScalarExpr,
24    visitor: &mut impl FnMut(&'a ScalarExpr) -> Result<(), E>,
25) -> Result<(), E> {
26    visit_inputs(expression, &mut || Ok(()), visitor)
27}
28
29/// Preserve both cancellation owners at every visited node, including COUNT(*) nodes that contribute no input-value callback.
30pub fn try_visit_input_values_with_control<'a>(
31    expression: &'a ScalarExpr,
32    control: &ProductionControl<'_>,
33    visitor: &mut impl FnMut(&'a ScalarExpr) -> Result<(), SQLError>,
34) -> Result<(), SQLError> {
35    visit_inputs(
36        expression,
37        &mut || control.check().map_err(Into::into),
38        visitor,
39    )?;
40    control.check()?;
41    Ok(())
42}
43
44fn visit_inputs<'a, E>(
45    expression: &'a ScalarExpr,
46    checkpoint: &mut impl FnMut() -> Result<(), E>,
47    visitor: &mut impl FnMut(&'a ScalarExpr) -> Result<(), E>,
48) -> Result<(), E> {
49    expression.try_visit(&mut |node| {
50        checkpoint()?;
51        if let ScalarExpr::Func {
52            name,
53            binding,
54            args,
55            order_by,
56            filter,
57            ..
58        } = node
59        {
60            let selected = binding
61                .as_ref()
62                .map_or(name.as_str(), |binding| &binding.name);
63            if matches!(args.as_slice(), [ScalarExpr::Star])
64                && crate::semantics::is_builtin_aggregate(node)
65                && selected
66                    .rsplit('.')
67                    .next()
68                    .is_some_and(|name| name.eq_ignore_ascii_case("count"))
69            {
70                for expression in order_by
71                    .iter()
72                    .map(|order| &order.expr)
73                    .chain(filter.as_deref())
74                {
75                    visit_inputs(expression, checkpoint, visitor)?;
76                }
77                return Ok(false);
78            }
79        }
80        visitor(node)?;
81        Ok(true)
82    })
83}
84
85#[cfg(test)]
86mod tests {
87    use super::visit_input_values as visit;
88    use super::*;
89
90    fn expression(sql: &str) -> ScalarExpr {
91        let crate::plan::UnifiedPlan::Query(query) =
92            crate::plan::UnifiedPlan::lower(crate::compile(sql).unwrap().remove(0))
93        else {
94            panic!("query");
95        };
96        let crate::plan::RelationalPlan::QueryBlock(mut block) = query.root else {
97            panic!("block");
98        };
99        block.projections.remove(0).expr
100    }
101
102    #[test]
103    fn row_count_star_does_not_demand_values_but_keeps_filter_and_ordering() {
104        for sql in [
105            "SELECT count(*)",
106            "SELECT pg_catalog.count(*)",
107            "SELECT 2+count(*)",
108        ] {
109            let mut stars = 0;
110            visit(&expression(sql), &mut |node| {
111                stars += usize::from(matches!(node, ScalarExpr::Star));
112            });
113            assert_eq!(stars, 0, "{sql}");
114        }
115        let mut count = expression("SELECT count(*) FILTER (WHERE keep > 0)");
116        let ScalarExpr::Func { order_by, .. } =
117            expression("SELECT count(value ORDER BY rank DESC)")
118        else {
119            panic!("call");
120        };
121        if let ScalarExpr::Func {
122            order_by: target, ..
123        } = &mut count
124        {
125            *target = order_by;
126        }
127        let mut names = Vec::new();
128        visit(&count, &mut |node| {
129            if let ScalarExpr::Column(name) = node {
130                names.push(name.clone());
131            }
132        });
133        assert_eq!(names, ["rank", "keep"]);
134    }
135
136    #[test]
137    fn selected_user_routine_and_whole_row_keep_their_value_demand() {
138        let mut count = expression("SELECT count(*)");
139        if let ScalarExpr::Func { binding, .. } = &mut count {
140            let mut user = crate::ast::FunctionBinding::builtin_by_name("count", None);
141            user.builtin = false;
142            user.object_id = Some([7; 16]);
143            *binding = Some(user);
144        }
145        let mut stars = 0;
146        visit(&count, &mut |node| {
147            stars += usize::from(matches!(node, ScalarExpr::Star));
148        });
149        assert_eq!(stars, 1);
150        for sql in ["SELECT count(q)", "SELECT count(q.*)"] {
151            let mut reads = 0;
152            visit(&expression(sql), &mut |node| {
153                reads += usize::from(matches!(
154                    node,
155                    ScalarExpr::Column(_) | ScalarExpr::QualifiedStar(_)
156                ));
157            });
158            assert_eq!(reads, 1, "{sql}");
159        }
160    }
161
162    fn ordered_count() -> ScalarExpr {
163        let mut count = expression("SELECT count(*) FILTER (WHERE keep > 0)");
164        let ScalarExpr::Func { order_by, .. } =
165            expression("SELECT count(value ORDER BY rank DESC)")
166        else {
167            panic!("call");
168        };
169        let ScalarExpr::Func {
170            order_by: target, ..
171        } = &mut count
172        else {
173            panic!("count");
174        };
175        *target = order_by;
176        ScalarExpr::Row(vec![count, ScalarExpr::Column("later".into())])
177    }
178
179    #[test]
180    fn input_value_observation_lends_names_without_copying_or_demanding_count_star() {
181        let expression = ordered_count();
182        let mut names = [None; 3];
183        let mut index = 0;
184        let allocation = allocation_counter::measure(|| {
185            try_visit_input_values(&expression, &mut |node| {
186                assert!(!matches!(node, ScalarExpr::Star));
187                if let ScalarExpr::Column(name) = node {
188                    names[index] = Some(name.as_str());
189                    index += 1;
190                }
191                Ok::<_, std::convert::Infallible>(())
192            })
193            .unwrap();
194        });
195        assert_eq!(names, [Some("rank"), Some("keep"), Some("later")]);
196        assert_eq!(allocation.bytes_total, 0, "{allocation:?}");
197        let ScalarExpr::Row(items) = &expression else {
198            panic!("row");
199        };
200        let ScalarExpr::Column(last) = &items[1] else {
201            panic!("column");
202        };
203        assert_eq!(names[2].unwrap().as_ptr(), last.as_ptr());
204    }
205
206    #[test]
207    fn input_value_observation_stops_at_the_first_callback_failure() {
208        let expression = ordered_count();
209        let mut names = Vec::new();
210        let error = try_visit_input_values(&expression, &mut |node| {
211            if let ScalarExpr::Column(name) = node {
212                names.push(name.as_str());
213                if name == "keep" {
214                    return Err("filter observation failed");
215                }
216            }
217            Ok(())
218        })
219        .unwrap_err();
220        assert_eq!(error, "filter observation failed");
221        assert_eq!(names, ["rank", "keep"]);
222    }
223
224    #[test]
225    fn unobserved_row_count_nodes_still_preserve_cancellation_checkpoints() {
226        use uqa_core::{memory::MemoryBudget, CancellationToken};
227        let expression = ScalarExpr::Row(vec![expression("SELECT count(*)"); 4096]);
228        for cancel_original in [false, true] {
229            let budget = MemoryBudget::new(0);
230            let original = CancellationToken::new();
231            let invoking = CancellationToken::new();
232            let control = ProductionControl::new(&budget, &original, &invoking);
233            let mut checkpoints = 0;
234            let mut observed = 0;
235            let error = visit_inputs(
236                &expression,
237                &mut || {
238                    checkpoints += 1;
239                    if checkpoints == 3 {
240                        if cancel_original {
241                            original.cancel();
242                        } else {
243                            invoking.cancel();
244                        }
245                    }
246                    control.check().map_err(SQLError::from)
247                },
248                &mut |node| {
249                    assert!(matches!(node, ScalarExpr::Row(_)));
250                    observed += 1;
251                    Ok(())
252                },
253            )
254            .unwrap_err();
255            assert_eq!(error.sqlstate(), Some("57014"));
256            assert_eq!(checkpoints, 3);
257            assert_eq!(observed, 1);
258            let error = try_visit_input_values_with_control(&expression, &control, &mut |_| {
259                panic!("cancelled traversal must not observe an input")
260            })
261            .unwrap_err();
262            assert_eq!(error.sqlstate(), Some("57014"));
263            assert_eq!(budget.peak(), 0);
264        }
265    }
266}