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    match expression {
142        ScalarExpr::Literal(Value::Int(position)) => {
143            let index = uqa_sql::semantics::query_output_position(
144                *position,
145                output_columns.len(),
146                "ORDER BY",
147            )?;
148            Ok(output_columns[index].1.clone())
149        }
150        ScalarExpr::Column(name) => {
151            let mut matches = output_columns.iter().filter(|(output, _)| output == name);
152            let Some((_, physical)) = matches.next() else {
153                return Ok(expression.clone());
154            };
155            if matches.next().is_some() {
156                return Err(SQLError::AmbiguousColumn(name.to_string()));
157            }
158            Ok(physical.clone())
159        }
160        _ => Ok(expression.clone()),
161    }
162}
163
164#[derive(Clone, Copy)]
165pub struct OutputTarget {
166    pub position: usize,
167    pub direct: bool,
168}
169
170pub fn output_target_position(
171    statement: &QueryBlockPlan,
172    expression: &ScalarExpr,
173    output: &[OutputColumnMapping],
174) -> Result<Option<OutputTarget>, SQLError> {
175    output_target_position_for(statement, expression, output, "ORDER BY")
176}
177
178pub fn distinct_output_target_position(
179    statement: &QueryBlockPlan,
180    expression: &ScalarExpr,
181    output: &[OutputColumnMapping],
182) -> Result<Option<OutputTarget>, SQLError> {
183    output_target_position_for(statement, expression, output, "DISTINCT ON")
184}
185
186fn output_target_position_for(
187    statement: &QueryBlockPlan,
188    expression: &ScalarExpr,
189    output: &[OutputColumnMapping],
190    clause: &str,
191) -> Result<Option<OutputTarget>, SQLError> {
192    match expression {
193        ScalarExpr::Literal(Value::Int(position)) => {
194            let position =
195                uqa_sql::semantics::query_output_position(*position, output.len(), clause)?;
196            return Ok(Some(OutputTarget {
197                position,
198                direct: true,
199            }));
200        }
201        ScalarExpr::Column(name) => {
202            let mut matches = output
203                .iter()
204                .enumerate()
205                .filter(|(_, (label, _))| label == name);
206            if let Some((position, _)) = matches.next() {
207                if matches.next().is_some() {
208                    return Err(SQLError::AmbiguousColumn(name.to_string()));
209                }
210                return Ok(Some(OutputTarget {
211                    position,
212                    direct: true,
213                }));
214            }
215        }
216        _ => {}
217    }
218    if statement.projections.len() != output.len() {
219        return Ok(None);
220    }
221    Ok(statement
222        .projections
223        .iter()
224        .position(|projection| {
225            uqa_sql::semantics::aggregates::exprs_match(&projection.expr, expression)
226        })
227        .map(|position| OutputTarget {
228            position,
229            direct: false,
230        }))
231}
232
233pub fn one_based_output_position(position: usize) -> Result<ScalarExpr, SQLError> {
234    let position = position
235        .checked_add(1)
236        .and_then(|position| i64::try_from(position).ok())
237        .ok_or_else(|| SQLError::Internal("SELECT output position exceeds i64".into()))?;
238    Ok(ScalarExpr::Literal(Value::Int(position)))
239}
240
241fn distinct_key_expressions_match(
242    statement: &QueryBlockPlan,
243    left: &ScalarExpr,
244    right: &ScalarExpr,
245    output: &[OutputColumnMapping],
246    right_is_order_by: bool,
247) -> Result<bool, SQLError> {
248    let left_target = distinct_output_target_position(statement, left, output)?;
249    let right_target = if right_is_order_by {
250        output_target_position(statement, right, output)?
251    } else {
252        distinct_output_target_position(statement, right, output)?
253    };
254    match (left_target, right_target) {
255        (Some(left), Some(right)) => Ok(left.position == right.position),
256        (None, None) => Ok(uqa_sql::semantics::aggregates::exprs_match(
257            &resolve_order_expression(left, output)?,
258            &resolve_order_expression(right, output)?,
259        )),
260        _ => Ok(false),
261    }
262}
263
264pub fn prior_distinct_key_index(
265    statement: &QueryBlockPlan,
266    index: usize,
267    expression: &ScalarExpr,
268    output: &[OutputColumnMapping],
269) -> Result<Option<usize>, SQLError> {
270    for (prior, candidate) in statement.distinct_on[..index].iter().enumerate() {
271        if distinct_key_expressions_match(statement, candidate, expression, output, false)? {
272            return Ok(Some(prior));
273        }
274    }
275    Ok(None)
276}
277
278pub fn validate_distinct_ordering(statement: &QueryBlockPlan) -> Result<(), SQLError> {
279    if !statement.distinct || statement.order_by.is_empty() {
280        return Ok(());
281    }
282    let output = identity_order_columns(&projection_columns(&statement.projections));
283    if statement.distinct_on.is_empty() {
284        if statement
285            .order_by
286            .iter()
287            .try_fold(false, |invalid, order| {
288                Ok::<_, SQLError>(
289                    invalid || output_target_position(statement, &order.expr, &output)?.is_none(),
290                )
291            })?
292        {
293            return Err(SQLError::Routine {
294                sqlstate: "42P10".into(),
295                message: "for SELECT DISTINCT, ORDER BY expressions must appear in select list"
296                    .into(),
297            });
298        }
299        return Ok(());
300    }
301    let mut matched = vec![false; statement.distinct_on.len()];
302    let mut encountered_non_distinct = false;
303    for order in &statement.order_by {
304        let mut order_is_distinct = false;
305        for (index, expression) in statement.distinct_on.iter().enumerate() {
306            if distinct_key_expressions_match(statement, expression, &order.expr, &output, true)? {
307                order_is_distinct = true;
308                matched[index] = true;
309            }
310        }
311        if order_is_distinct {
312            if encountered_non_distinct {
313                return Err(distinct_on_ordering_error());
314            }
315        } else {
316            encountered_non_distinct = true;
317        }
318    }
319    if encountered_non_distinct && matched.iter().any(|matched| !matched) {
320        return Err(distinct_on_ordering_error());
321    }
322    Ok(())
323}
324
325fn distinct_on_ordering_error() -> SQLError {
326    SQLError::Routine {
327        sqlstate: "42P10".into(),
328        message: "SELECT DISTINCT ON expressions must match initial ORDER BY expressions".into(),
329    }
330}
331
332pub fn split_locking_order_projections(
333    statement: &QueryBlockPlan,
334    output: &[OutputColumnMapping],
335    physical: Vec<PhysicalProjection>,
336) -> Result<
337    (
338        QueryBlockPlan,
339        Vec<PhysicalProjection>,
340        Vec<PhysicalProjection>,
341    ),
342    SQLError,
343> {
344    let (sort_statement, required) = order_projection_targets(statement, output, &physical)?;
345    let (before_sort, after_sort) = physical
346        .into_iter()
347        .partition(|(target, _)| required.contains(target));
348    Ok((sort_statement, before_sort, after_sort))
349}
350
351pub fn order_projection_targets(
352    statement: &QueryBlockPlan,
353    output: &[OutputColumnMapping],
354    physical: &[PhysicalProjection],
355) -> Result<(QueryBlockPlan, HashSet<ProjectionTarget>), SQLError> {
356    let mut sort_statement = statement.clone();
357    let mut required = HashSet::new();
358    for (index, order) in statement.order_by.iter().enumerate() {
359        let expression = resolve_order_expression(&order.expr, output)?;
360        if let Some((target, _)) = physical.iter().find(|(target, _)| {
361            uqa_sql::semantics::aggregates::exprs_match(
362                &projection_target_expression(target),
363                &expression,
364            )
365        }) {
366            required.insert(target.clone());
367            sort_statement.order_by[index].expr = projection_target_expression(target);
368            continue;
369        }
370        if let ScalarExpr::Column(column) = &expression {
371            let target = ProjectionTarget::Column(column.to_string());
372            if physical.iter().any(|(candidate, _)| candidate == &target) {
373                required.insert(target);
374                continue;
375            }
376        }
377        if let Some((target, _)) = physical.iter().find(|(_, projected)| {
378            uqa_sql::semantics::aggregates::exprs_match(projected, &expression)
379        }) {
380            required.insert(target.clone());
381            sort_statement.order_by[index].expr = projection_target_expression(target);
382        }
383    }
384    Ok((sort_statement, required))
385}
386
387pub fn append_row_at_time_projection<'a>(
388    operator: Box<dyn crate::PhysicalOperator + 'a>,
389    projections: Vec<PhysicalProjection>,
390    evaluator: SharedExpressionEvaluator<'a>,
391) -> Box<dyn crate::PhysicalOperator + 'a> {
392    if projections.is_empty() {
393        return operator;
394    }
395    Box::new(
396        crate::Project::appending_target_evaluator(operator, projections, evaluator)
397            .with_row_at_a_time_input(),
398    )
399}
400
401#[cfg(test)]
402mod tests;