uqa_execution/relational/
sort.rs1use 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 pub nulls_first: Option<bool>,
22}
23
24const 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 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
118pub 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#[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
229pub(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 output_ordering(&self) -> &[crate::PhysicalOrder] {
278 self.inner.output_ordering()
279 }
280
281 fn backward_scan_support(&self) -> crate::BackwardScanSupport {
282 crate::BackwardScanSupport::Materialize
283 }
284
285 fn open(&mut self) -> ExecResult<()> {
286 self.inner.open()
287 }
288
289 fn next(&mut self) -> ExecResult<Option<Batch>> {
290 self.inner.next()
291 }
292
293 fn close(&mut self) -> ExecResult<()> {
294 self.inner.close()
295 }
296}
297
298