Skip to main content

uqa_execution/query/
ordering.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Physical output positions and ordering expression identities.
8
9use crate::query::projection::{projection_target_expression, visible_projection_source_position};
10use crate::query::{OutputColumnMapping, PhysicalProjection};
11use crate::{ProjectionTarget, ScalarExpr, SharedExpressionEvaluator};
12use std::collections::HashSet;
13use uqa_core::Value;
14use uqa_sql::{
15    plan::{ProjectionPlan, QueryBlockPlan},
16    semantics::projection_columns,
17    SQLError,
18};
19
20pub use uqa_sql::semantics::output_position_error;
21
22/// Build collision-free physical target columns for a plain SELECT whose ORDER BY must be able to see both input columns and SELECT-list aliases. Public aliases cannot safely be appended directly: `SELECT x + 1 AS x ... ORDER BY x` must order by the output alias, while `ORDER BY x + 1` still resolves `x` against the input namespace. Each non-star target is therefore computed once under an opaque internal attribute and assigned its public label only after Sort/Limit has consumed it.
23pub fn order_projection(
24    projections: &[ProjectionPlan],
25    input_schema: &crate::RowSchema,
26) -> Result<(Vec<PhysicalProjection>, Vec<OutputColumnMapping>), SQLError> {
27    let labels = projection_columns(projections);
28    let mut physical = Vec::new();
29    let mut output = Vec::new();
30    let internal_relation = uqa_sql::ast::InternalRelationId::allocate();
31    let mut next_internal_attribute = 0usize;
32
33    for (index, projection) in projections.iter().enumerate() {
34        if matches!(projection.expr, ScalarExpr::Star) {
35            for (position, column) in input_schema.columns().iter().enumerate() {
36                if visible_projection_source_position(input_schema, position) {
37                    output.push((
38                        input_schema
39                            .public_name(position)
40                            .unwrap_or(column)
41                            .to_string(),
42                        ScalarExpr::Position(position),
43                    ));
44                }
45            }
46            continue;
47        }
48        if let ScalarExpr::QualifiedStar(qualifier) = &projection.expr {
49            let columns = input_schema.qualified_star_position_layout(qualifier);
50            if columns.is_empty() {
51                return Err(SQLError::UnknownTable(qualifier.to_string()));
52            }
53            for (column, logical, _, _) in columns {
54                if logical.is_some_and(|position| {
55                    !visible_projection_source_position(input_schema, position)
56                }) {
57                    continue;
58                }
59                if let Some(logical) = logical {
60                    output.push((column, ScalarExpr::Position(logical)));
61                    continue;
62                }
63                let internal = internal_relation.column(next_internal_attribute);
64                next_internal_attribute += 1;
65                physical.push((
66                    ProjectionTarget::Internal(internal),
67                    ScalarExpr::qualified_column(qualifier, &column),
68                ));
69                output.push((column, ScalarExpr::InternalColumn(internal)));
70            }
71            continue;
72        }
73
74        if let ScalarExpr::Column(source) = &projection.expr {
75            if &labels[index] == source {
76                if let Some(position) = input_schema.unqualified_position(source) {
77                    output.push((labels[index].clone(), ScalarExpr::Position(position)));
78                    continue;
79                }
80            }
81        }
82        if let ScalarExpr::QualifiedColumn { qualifier, column } = &projection.expr {
83            if &labels[index] == column {
84                if let Some(position) = input_schema.qualified_position(qualifier, column) {
85                    output.push((labels[index].clone(), ScalarExpr::Position(position)));
86                    continue;
87                }
88            }
89        }
90
91        let internal = internal_relation.column(next_internal_attribute);
92        next_internal_attribute += 1;
93        physical.push((
94            ProjectionTarget::Internal(internal),
95            projection.expr.clone(),
96        ));
97        output.push((labels[index].clone(), ScalarExpr::InternalColumn(internal)));
98    }
99    Ok((physical, output))
100}
101
102pub fn identity_order_columns(columns: &[String]) -> Vec<OutputColumnMapping> {
103    columns
104        .iter()
105        .enumerate()
106        .map(|(position, column)| (column.clone(), ScalarExpr::Position(position)))
107        .collect()
108}
109
110pub fn output_selection_positions(
111    schema: &crate::RowSchema,
112    output: Vec<OutputColumnMapping>,
113) -> Result<Vec<(String, usize)>, SQLError> {
114    output
115        .into_iter()
116        .map(|(label, source)| {
117            let position = match source {
118                ScalarExpr::Position(position) if position < schema.len() => {
119                    schema.physical_slot(position)
120                }
121                ScalarExpr::Column(column) => schema
122                    .position(&column)
123                    .and_then(|logical| schema.physical_slot(logical)),
124                ScalarExpr::InternalColumn(column) => schema.internal_slot(column),
125                _ => None,
126            }
127            .ok_or_else(|| {
128                SQLError::Internal(format!(
129                    "bound output column `{label}` is unavailable in the physical row"
130                ))
131            })?;
132            Ok((label, position))
133        })
134        .collect()
135}
136
137pub fn resolve_order_expression(
138    expression: &ScalarExpr,
139    output_columns: &[OutputColumnMapping],
140) -> Result<ScalarExpr, SQLError> {
141    resolve_order_expression_ref(expression, output_columns).cloned()
142}
143
144pub fn resolve_order_expression_ref<'a>(
145    expression: &'a ScalarExpr,
146    output_columns: &'a [OutputColumnMapping],
147) -> Result<&'a ScalarExpr, SQLError> {
148    match expression {
149        ScalarExpr::Literal(Value::Int(position)) => {
150            let index = uqa_sql::semantics::query_output_position(
151                *position,
152                output_columns.len(),
153                "ORDER BY",
154            )?;
155            Ok(&output_columns[index].1)
156        }
157        ScalarExpr::Column(name) => {
158            let mut matches = output_columns.iter().filter(|(output, _)| output == name);
159            let Some((_, physical)) = matches.next() else {
160                return Ok(expression);
161            };
162            if matches.next().is_some() {
163                return Err(SQLError::AmbiguousColumn(name.to_string()));
164            }
165            Ok(physical)
166        }
167        _ => Ok(expression),
168    }
169}
170
171#[derive(Clone, Copy)]
172pub struct OutputTarget {
173    pub position: usize,
174    pub direct: bool,
175}
176
177pub fn output_target_position(
178    statement: &QueryBlockPlan,
179    expression: &ScalarExpr,
180    output: &[OutputColumnMapping],
181) -> Result<Option<OutputTarget>, SQLError> {
182    output_target_position_for(statement, expression, output, "ORDER BY")
183}
184
185pub fn distinct_output_target_position(
186    statement: &QueryBlockPlan,
187    expression: &ScalarExpr,
188    output: &[OutputColumnMapping],
189) -> Result<Option<OutputTarget>, SQLError> {
190    output_target_position_for(statement, expression, output, "DISTINCT ON")
191}
192
193fn output_target_position_for(
194    statement: &QueryBlockPlan,
195    expression: &ScalarExpr,
196    output: &[OutputColumnMapping],
197    clause: &str,
198) -> Result<Option<OutputTarget>, SQLError> {
199    match expression {
200        ScalarExpr::Literal(Value::Int(position)) => {
201            let position =
202                uqa_sql::semantics::query_output_position(*position, output.len(), clause)?;
203            return Ok(Some(OutputTarget {
204                position,
205                direct: true,
206            }));
207        }
208        ScalarExpr::Column(name) => {
209            let mut matches = output
210                .iter()
211                .enumerate()
212                .filter(|(_, (label, _))| label == name);
213            if let Some((position, _)) = matches.next() {
214                if matches.next().is_some() {
215                    return Err(SQLError::AmbiguousColumn(name.to_string()));
216                }
217                return Ok(Some(OutputTarget {
218                    position,
219                    direct: true,
220                }));
221            }
222        }
223        _ => {}
224    }
225    if statement.projections.len() != output.len() {
226        return Ok(None);
227    }
228    Ok(statement
229        .projections
230        .iter()
231        .position(|projection| {
232            uqa_sql::semantics::aggregates::exprs_match(&projection.expr, expression)
233        })
234        .map(|position| OutputTarget {
235            position,
236            direct: false,
237        }))
238}
239
240pub fn one_based_output_position(position: usize) -> Result<ScalarExpr, SQLError> {
241    let position = position
242        .checked_add(1)
243        .and_then(|position| i64::try_from(position).ok())
244        .ok_or_else(|| SQLError::Internal("SELECT output position exceeds i64".into()))?;
245    Ok(ScalarExpr::Literal(Value::Int(position)))
246}
247
248fn distinct_key_expressions_match(
249    statement: &QueryBlockPlan,
250    left: &ScalarExpr,
251    right: &ScalarExpr,
252    output: &[OutputColumnMapping],
253    right_is_order_by: bool,
254) -> Result<bool, SQLError> {
255    let left_target = distinct_output_target_position(statement, left, output)?;
256    let right_target = if right_is_order_by {
257        output_target_position(statement, right, output)?
258    } else {
259        distinct_output_target_position(statement, right, output)?
260    };
261    match (left_target, right_target) {
262        (Some(left), Some(right)) => Ok(left.position == right.position),
263        (None, None) => Ok(uqa_sql::semantics::aggregates::exprs_match(
264            &resolve_order_expression(left, output)?,
265            &resolve_order_expression(right, output)?,
266        )),
267        _ => Ok(false),
268    }
269}
270
271pub fn prior_distinct_key_index(
272    statement: &QueryBlockPlan,
273    index: usize,
274    expression: &ScalarExpr,
275    output: &[OutputColumnMapping],
276) -> Result<Option<usize>, SQLError> {
277    for (prior, candidate) in statement.distinct_on[..index].iter().enumerate() {
278        if distinct_key_expressions_match(statement, candidate, expression, output, false)? {
279            return Ok(Some(prior));
280        }
281    }
282    Ok(None)
283}
284
285pub fn validate_distinct_ordering(statement: &QueryBlockPlan) -> Result<(), SQLError> {
286    if !statement.distinct || statement.order_by.is_empty() {
287        return Ok(());
288    }
289    let output = identity_order_columns(&projection_columns(&statement.projections));
290    if statement.distinct_on.is_empty() {
291        if statement
292            .order_by
293            .iter()
294            .try_fold(false, |invalid, order| {
295                Ok::<_, SQLError>(
296                    invalid || output_target_position(statement, &order.expr, &output)?.is_none(),
297                )
298            })?
299        {
300            return Err(SQLError::Routine {
301                sqlstate: "42P10".into(),
302                message: "for SELECT DISTINCT, ORDER BY expressions must appear in select list"
303                    .into(),
304            });
305        }
306        return Ok(());
307    }
308    let mut matched = vec![false; statement.distinct_on.len()];
309    let mut encountered_non_distinct = false;
310    for order in &statement.order_by {
311        let mut order_is_distinct = false;
312        for (index, expression) in statement.distinct_on.iter().enumerate() {
313            if distinct_key_expressions_match(statement, expression, &order.expr, &output, true)? {
314                order_is_distinct = true;
315                matched[index] = true;
316            }
317        }
318        if order_is_distinct {
319            if encountered_non_distinct {
320                return Err(distinct_on_ordering_error());
321            }
322        } else {
323            encountered_non_distinct = true;
324        }
325    }
326    if encountered_non_distinct && matched.iter().any(|matched| !matched) {
327        return Err(distinct_on_ordering_error());
328    }
329    Ok(())
330}
331
332fn distinct_on_ordering_error() -> SQLError {
333    SQLError::Routine {
334        sqlstate: "42P10".into(),
335        message: "SELECT DISTINCT ON expressions must match initial ORDER BY expressions".into(),
336    }
337}
338
339pub fn split_locking_order_projections(
340    statement: &QueryBlockPlan,
341    output: &[OutputColumnMapping],
342    physical: Vec<PhysicalProjection>,
343) -> Result<
344    (
345        QueryBlockPlan,
346        Vec<PhysicalProjection>,
347        Vec<PhysicalProjection>,
348    ),
349    SQLError,
350> {
351    let (sort_statement, required) = order_projection_targets(statement, output, &physical)?;
352    let (before_sort, after_sort) = physical
353        .into_iter()
354        .partition(|(target, _)| required.contains(target));
355    Ok((sort_statement, before_sort, after_sort))
356}
357
358pub fn order_projection_targets(
359    statement: &QueryBlockPlan,
360    output: &[OutputColumnMapping],
361    physical: &[PhysicalProjection],
362) -> Result<(QueryBlockPlan, HashSet<ProjectionTarget>), SQLError> {
363    let mut sort_statement = statement.clone();
364    let mut required = HashSet::new();
365    for (index, order) in statement.order_by.iter().enumerate() {
366        let expression = resolve_order_expression(&order.expr, output)?;
367        if let Some((target, _)) = physical.iter().find(|(target, _)| {
368            uqa_sql::semantics::aggregates::exprs_match(
369                &projection_target_expression(target),
370                &expression,
371            )
372        }) {
373            required.insert(target.clone());
374            sort_statement.order_by[index].expr = projection_target_expression(target);
375            continue;
376        }
377        if let ScalarExpr::Column(column) = &expression {
378            let target = ProjectionTarget::Column(column.to_string());
379            if physical.iter().any(|(candidate, _)| candidate == &target) {
380                required.insert(target);
381                continue;
382            }
383        }
384        if let Some((target, _)) = physical.iter().find(|(_, projected)| {
385            uqa_sql::semantics::aggregates::exprs_match(projected, &expression)
386        }) {
387            required.insert(target.clone());
388            sort_statement.order_by[index].expr = projection_target_expression(target);
389        }
390    }
391    Ok((sort_statement, required))
392}
393
394pub fn append_row_at_time_projection<'a>(
395    operator: Box<dyn crate::PhysicalOperator + 'a>,
396    projections: Vec<PhysicalProjection>,
397    evaluator: SharedExpressionEvaluator<'a>,
398) -> Box<dyn crate::PhysicalOperator + 'a> {
399    if projections.is_empty() {
400        return operator;
401    }
402    Box::new(
403        crate::Project::appending_target_evaluator(operator, projections, evaluator)
404            .with_row_at_a_time_input(),
405    )
406}
407
408#[cfg(test)]
409mod tests;