Skip to main content

uqa_execution/relational/
sort.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! External sort wrapper and SQL key comparison.
8
9use super::{
10    Batch, DefaultExpressionEvaluator, ExecResult, PhysicalOperator, SQLParam, ScalarExpr,
11    SharedExpressionEvaluator, Value,
12};
13
14#[derive(Debug, Clone)]
15pub struct SortKey {
16    pub expr: ScalarExpr,
17    pub descending: bool,
18    /// `Some(true)` forces NULLS FIRST, `Some(false)` forces NULLS
19    /// LAST. `None` falls back to the SQL-standard default - NULLS
20    /// LAST for ASC and NULLS FIRST for DESC.
21    pub nulls_first: Option<bool>,
22}
23
24/// Byte-bounded blocking sort backed by the external merge-sort implementation.
25/// Compatibility constructors use a 64 MiB budget; engine callers should pass
26/// the active session's `work_mem` through [`Self::with_evaluator_and_work_mem`].
27const DEFAULT_SORT_WORK_MEM_BYTES: usize = 64 * 1024 * 1024;
28
29pub struct Sort<'a> {
30    inner: crate::external_sort::ExternalSort<'a>,
31}
32
33impl Sort<'static> {
34    pub fn with_work_mem(
35        child: Box<dyn PhysicalOperator>,
36        keys: Vec<SortKey>,
37        params: Vec<SQLParam>,
38        work_mem_bytes: usize,
39    ) -> Self {
40        Self::with_evaluator_and_work_mem(
41            child,
42            keys,
43            DefaultExpressionEvaluator::shared(params),
44            work_mem_bytes,
45        )
46    }
47
48    pub fn new(
49        child: Box<dyn PhysicalOperator>,
50        keys: Vec<SortKey>,
51        params: Vec<SQLParam>,
52    ) -> Self {
53        Self::with_evaluator(child, keys, DefaultExpressionEvaluator::shared(params))
54    }
55
56    /// Top-K variant: retain only the first `keep` rows of the sorted
57    /// order. Uses a partial selection, so the cost is `O(n + k log k)`
58    /// instead of `O(n log n)`.
59    pub fn with_keep(
60        child: Box<dyn PhysicalOperator>,
61        keys: Vec<SortKey>,
62        params: Vec<SQLParam>,
63        keep: usize,
64    ) -> Self {
65        Self::with_evaluator_and_keep(
66            child,
67            keys,
68            DefaultExpressionEvaluator::shared(params),
69            keep,
70        )
71    }
72}
73
74impl<'a> Sort<'a> {
75    pub fn with_evaluator(
76        child: Box<dyn PhysicalOperator + 'a>,
77        keys: Vec<SortKey>,
78        evaluator: SharedExpressionEvaluator<'a>,
79    ) -> Self {
80        Self::with_evaluator_and_work_mem(child, keys, evaluator, DEFAULT_SORT_WORK_MEM_BYTES)
81    }
82
83    pub fn with_evaluator_and_work_mem(
84        child: Box<dyn PhysicalOperator + 'a>,
85        keys: Vec<SortKey>,
86        evaluator: SharedExpressionEvaluator<'a>,
87        work_mem_bytes: usize,
88    ) -> Self {
89        Self {
90            inner: crate::external_sort::ExternalSort::new(
91                child,
92                keys,
93                evaluator,
94                None,
95                work_mem_bytes,
96            ),
97        }
98    }
99
100    pub fn with_evaluator_and_keep(
101        child: Box<dyn PhysicalOperator + 'a>,
102        keys: Vec<SortKey>,
103        evaluator: SharedExpressionEvaluator<'a>,
104        keep: usize,
105    ) -> Self {
106        Self {
107            inner: crate::external_sort::ExternalSort::new(
108                child,
109                keys,
110                evaluator,
111                Some(keep),
112                DEFAULT_SORT_WORK_MEM_BYTES,
113            ),
114        }
115    }
116}
117
118/// Compare two pre-computed sort-key vectors under `keys` semantics:
119/// per-key direction plus `PostgreSQL` NULLS placement (default NULLS
120/// LAST for ascending, NULLS FIRST for descending).
121pub fn compare_sort_key_values(
122    keys: &[SortKey],
123    av: &[Value],
124    bv: &[Value],
125) -> ExecResult<std::cmp::Ordering> {
126    compare_sort_key_values_by(keys, |index| (&av[index], &bv[index]))
127}
128
129pub(crate) fn compare_sort_key_values_by<'a>(
130    keys: &[SortKey],
131    values: impl FnMut(usize) -> (&'a Value, &'a Value),
132) -> ExecResult<std::cmp::Ordering> {
133    SortComparison {
134        keys,
135        types: &[],
136        enums: None,
137        states: &[],
138        domain: SortComparisonDomain::SqlOrdering,
139        cancellation: None,
140    }
141    .compare_by(values)
142}
143
144/// One ordering support call per key, retained across run generation, top-K selection and merge passes.
145#[derive(Clone, Copy, PartialEq, Eq)]
146pub(crate) enum SortComparisonDomain {
147    SqlOrdering,
148    Grouping,
149    Physical,
150}
151
152#[derive(Clone, Copy)]
153pub(crate) struct SortComparison<'a> {
154    pub(crate) keys: &'a [SortKey],
155    pub(crate) types: &'a [Option<uqa_sql::ColumnType>],
156    pub(crate) enums: Option<&'a dyn uqa_sql::expr::enums::EnumLabelCatalog>,
157    pub(crate) states: &'a [uqa_sql::expr::enums::EnumComparisonState],
158    pub(crate) domain: SortComparisonDomain,
159    pub(crate) cancellation: Option<&'a uqa_core::CancellationToken>,
160}
161
162impl SortComparison<'_> {
163    pub(crate) fn compare_by<'v>(
164        &self,
165        mut values: impl FnMut(usize) -> (&'v Value, &'v Value),
166    ) -> ExecResult<std::cmp::Ordering> {
167        use std::cmp::Ordering;
168        if let Some(cancellation) = self.cancellation {
169            cancellation.check().map_err(uqa_sql::SQLError::Cancelled)?;
170        }
171        for (i, k) in self.keys.iter().enumerate() {
172            let (a, b) = values(i);
173            if self.domain == SortComparisonDomain::Physical {
174                let order = a.cmp(b);
175                if !order.is_eq() {
176                    return Ok(order);
177                }
178                continue;
179            }
180            let a_null = matches!(a, Value::Null);
181            let b_null = matches!(b, Value::Null);
182            let nulls_first = k.nulls_first.unwrap_or(k.descending);
183            if a_null || b_null {
184                let null_cmp = if a_null == b_null {
185                    Ordering::Equal
186                } else if a_null {
187                    if nulls_first {
188                        Ordering::Less
189                    } else {
190                        Ordering::Greater
191                    }
192                } else if nulls_first {
193                    Ordering::Greater
194                } else {
195                    Ordering::Less
196                };
197                if null_cmp != Ordering::Equal {
198                    return Ok(null_cmp);
199                }
200                continue;
201            }
202            let ord = if self.domain == SortComparisonDomain::Grouping {
203                uqa_sql::expr::compare_selected_grouping_values_with_catalog(
204                    a,
205                    b,
206                    self.types.get(i).and_then(Option::as_ref),
207                    &uqa_core::memory::ProductionControl::uncontrolled(),
208                    self.enums,
209                )?
210            } else {
211                uqa_sql::expr::compare_selected_values_with_catalog(
212                    a,
213                    b,
214                    self.types.get(i).and_then(Option::as_ref),
215                    &uqa_core::memory::ProductionControl::uncontrolled(),
216                    self.enums,
217                    self.states.get(i),
218                )?
219            };
220            let ord = if k.descending { ord.reverse() } else { ord };
221            if ord != Ordering::Equal {
222                return Ok(ord);
223            }
224        }
225        Ok(Ordering::Equal)
226    }
227}
228
229/// DISTINCT and WITH TIES use equality, without invoking a scalar ordering support function.
230pub(crate) fn equal_typed_sort_key_values(
231    left: &[Value],
232    right: &[Value],
233    types: &[Option<uqa_sql::ColumnType>],
234    enums: Option<&dyn uqa_sql::expr::SQLValueCatalog>,
235) -> ExecResult<bool> {
236    if left.len() != right.len() {
237        return Ok(false);
238    }
239    for (index, (left, right)) in left.iter().zip(right).enumerate() {
240        if !uqa_sql::expr::equal_selected_values_with_catalog(
241            left,
242            right,
243            types.get(index).and_then(Option::as_ref),
244            &uqa_core::memory::ProductionControl::uncontrolled(),
245            enums,
246        )? {
247            return Ok(false);
248        }
249    }
250    Ok(true)
251}
252
253pub(super) fn compare_values(
254    a: &Value,
255    b: &Value,
256) -> Result<std::cmp::Ordering, uqa_sql::SQLError> {
257    use std::cmp::Ordering::*;
258    Ok(match (a, b) {
259        (Value::Null, Value::Null) => Equal,
260        (Value::Null, _) => Less,
261        (_, Value::Null) => Greater,
262        (Value::Temporal(x), Value::Str(y)) => x
263            .parse_same_kind(y)
264            .map_or_else(|| a.cmp(b), |parsed| x.cmp(&parsed)),
265        (Value::Str(x), Value::Temporal(y)) => y
266            .parse_same_kind(x)
267            .map_or_else(|| a.cmp(b), |parsed| parsed.cmp(y)),
268        _ => crate::aggregation::compare_extrema(a, b)?,
269    })
270}
271
272impl PhysicalOperator for Sort<'_> {
273    fn row_schema(&self) -> &super::RowSchema {
274        self.inner.row_schema()
275    }
276
277    fn supports_batched_consumption(&self) -> bool {
278        self.inner.supports_batched_consumption()
279    }
280
281    fn output_ordering(&self) -> &[crate::PhysicalOrder] {
282        self.inner.output_ordering()
283    }
284
285    fn backward_scan_support(&self) -> crate::BackwardScanSupport {
286        crate::BackwardScanSupport::Materialize
287    }
288
289    fn open(&mut self) -> ExecResult<()> {
290        self.inner.open()
291    }
292
293    fn next(&mut self) -> ExecResult<Option<Batch>> {
294        self.inner.next()
295    }
296
297    fn close(&mut self) -> ExecResult<()> {
298        self.inner.close()
299    }
300}
301
302// -------------------------------------------------------------------------
303// Limit / Offset
304// -------------------------------------------------------------------------