Skip to main content

uqa_execution/
external_sort.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Byte-bounded external merge sort.
8//!
9//! Input is divided into stable sorted runs whose exact spill encoding stays
10//! within `work_mem_bytes` (except for one indivisible oversized row). This is
11//! a hard bound on retained encoded row/run bytes, not Rust allocator resident
12//! bytes. Runs are written through [`crate::spill::SpillBuffer`], then merged
13//! with a fixed fan-in. Merge reader/heap overhead is therefore constant: at
14//! most [`EXTERNAL_SORT_MERGE_FAN_IN`] decoded rows plus one byte-bounded output
15//! buffer, independent of the total run count.
16
17use std::cmp::Ordering;
18use std::path::PathBuf;
19
20use uqa_core::Value;
21use uqa_sql::expr::enums::{EnumComparisonState, EnumLabelCatalog};
22
23use crate::batch::{Batch, PhysicalRow, RowSchema};
24use crate::physical::{
25    order_expression_position, ExecError, ExecResult, PhysicalOperator, PhysicalOrder,
26};
27use crate::relational::SortComparison;
28use crate::relational::{SharedExpressionEvaluator, SortKey};
29use crate::spill::{EncodedBatchSizer, SpillBuffer, SpillDrain, SpillFileArena};
30
31mod comparison;
32mod top_k;
33use comparison::compare_records;
34
35/// Maximum number of input runs opened by one merge operation.
36pub const EXTERNAL_SORT_MERGE_FAN_IN: usize = 16;
37
38fn run_schema(source_width: usize, key_count: usize) -> RowSchema {
39    RowSchema::with_internal_relation_types(
40        uqa_sql::ast::InternalRelationId::allocate(),
41        vec![None; source_width + key_count + 1],
42    )
43}
44
45/// Physical external sort with stable SQL ordering and optional global top-K.
46pub struct ExternalSort<'a> {
47    child: Box<dyn PhysicalOperator + 'a>,
48    keys: crate::scalar::PreparedExpressions<Vec<SortKey>>,
49    evaluator: SharedExpressionEvaluator<'a>,
50    comparison_states: Vec<EnumComparisonState>,
51    key_types: Vec<Option<uqa_sql::ColumnType>>,
52    equality_keys: bool,
53    keep: Option<usize>,
54    work_mem_bytes: usize,
55    spill_directory: Option<PathBuf>,
56    schema: RowSchema,
57    input_slots: Vec<usize>,
58    run_schema: RowSchema,
59    ordering: Vec<PhysicalOrder>,
60    output: Option<SpillDrain>,
61    initial_run_count: usize,
62    merge_pass_count: usize,
63}
64
65impl<'a> ExternalSort<'a> {
66    /// Sort keys are bound against the child's declared row types, as projections and filters bind their expressions, so a key that nests a catalog function resolves it by its argument types rather than by the runtime values.
67    pub fn new(
68        child: Box<dyn PhysicalOperator + 'a>,
69        mut keys: Vec<SortKey>,
70        evaluator: SharedExpressionEvaluator<'a>,
71        keep: Option<usize>,
72        work_mem_bytes: usize,
73    ) -> Self {
74        for key in &mut keys {
75            let expression =
76                std::mem::replace(&mut key.expr, uqa_sql::ir::ScalarExpr::Literal(Value::Null));
77            key.expr = evaluator.bind_type_introspection(expression, child.row_schema());
78        }
79        let (schema, input_slots) = child.row_schema().canonical_projection();
80        let run_schema = run_schema(input_slots.len(), keys.len());
81        let ordering = keys
82            .iter()
83            .map(|key| {
84                order_expression_position(&schema, &key.expr).map(|position| PhysicalOrder {
85                    position,
86                    descending: key.descending,
87                    nulls_first: Some(key.nulls_first.unwrap_or(key.descending)),
88                    nullable: true,
89                })
90            })
91            .collect::<Option<Vec<_>>>()
92            .unwrap_or_default();
93        Self {
94            child,
95            comparison_states: if evaluator
96                .enum_labels()
97                .is_some_and(EnumLabelCatalog::has_enum_types)
98            {
99                (0..keys.len())
100                    .map(|_| EnumComparisonState::default())
101                    .collect()
102            } else {
103                Vec::new()
104            },
105            keys: crate::scalar::PreparedExpressions::sort_keys(keys),
106            evaluator,
107            equality_keys: false,
108            key_types: Vec::new(),
109            keep,
110            work_mem_bytes,
111            spill_directory: None,
112            schema,
113            input_slots,
114            run_schema,
115            ordering,
116            output: None,
117            initial_run_count: 0,
118            merge_pass_count: 0,
119        }
120    }
121
122    /// Internal set grouping requires equality classes, without exposing this identity order as SQL ORDER BY.
123    pub(crate) fn with_equality_keys(mut self) -> Self {
124        self.equality_keys = true;
125        self.comparison_states = Vec::new();
126        self.ordering.clear();
127        self
128    }
129
130    /// Place sort runs in a caller-selected temporary-data directory.
131    pub fn with_spill_directory(mut self, directory: impl Into<PathBuf>) -> Self {
132        self.spill_directory = Some(directory.into());
133        self
134    }
135
136    pub fn initial_run_count(&self) -> usize {
137        self.initial_run_count
138    }
139
140    pub fn merge_pass_count(&self) -> usize {
141        self.merge_pass_count
142    }
143
144    fn create_run_buffer(&self, arena: &SpillFileArena) -> SpillBuffer {
145        self.spill_directory
146            .as_ref()
147            .map_or_else(
148                || SpillBuffer::new(self.work_mem_bytes),
149                |directory| SpillBuffer::new_in(self.work_mem_bytes, directory),
150            )
151            .with_arena(arena)
152    }
153
154    fn build_initial_runs(&mut self) -> ExecResult<Vec<SortedRun>> {
155        let arena = SpillFileArena::new(self.spill_directory.clone());
156        let mut sequence = 0_u64;
157        let mut pending = Vec::new();
158        let mut pending_size = EncodedBatchSizer::new(&self.run_schema)?;
159        let mut top_k_heap = false;
160        let mut runs = Vec::new();
161
162        while let Some(batch) = self.child.next()? {
163            for row in batch.rows {
164                let mut key_values = Vec::with_capacity(self.keys.len());
165                for key in self.keys.iter() {
166                    key_values.push(self.evaluator.evaluate_physical_with_function_states(
167                        &key.expr,
168                        &batch.schema,
169                        &row,
170                        self.keys.calls(),
171                    )?);
172                }
173                let record_sequence = sequence;
174                key_values.push(Value::Bytes(record_sequence.to_be_bytes().to_vec()));
175                let record = DecoratedRow {
176                    row: row
177                        .project_slots(&self.input_slots)
178                        .append_values(key_values),
179                    sequence,
180                };
181                sequence = sequence.checked_add(1).ok_or_else(|| {
182                    ExecError::Other("external sort input sequence overflow".into())
183                })?;
184                if !top_k_heap
185                    && self
186                        .keep
187                        .is_some_and(|keep| keep > 0 && pending.len() == keep)
188                {
189                    top_k::heapify(&mut pending, &self.comparison(), self.input_slots.len())?;
190                    top_k_heap = true;
191                }
192                if self.retain_top_candidate(&mut pending, &mut pending_size, &record)? {
193                    continue;
194                }
195                let mut candidate_size = pending_size;
196                candidate_size.append(&record.row)?;
197                let would_exceed = candidate_size.bytes() > self.work_mem_bytes;
198
199                if would_exceed && !pending.is_empty() {
200                    if let Some(run) =
201                        self.finish_run(std::mem::take(&mut pending), true, &arena)?
202                    {
203                        runs.push(run);
204                    }
205                    pending_size = EncodedBatchSizer::new(&self.run_schema)?;
206                    top_k_heap = false;
207                    candidate_size = pending_size;
208                    candidate_size.append(&record.row)?;
209                }
210
211                pending.push(record);
212                pending_size = candidate_size;
213
214                // One row is indivisible. Flush it immediately when it alone is
215                // larger than work_mem so no additional row joins it in memory.
216                if pending_size.bytes() > self.work_mem_bytes {
217                    if let Some(run) =
218                        self.finish_run(std::mem::take(&mut pending), true, &arena)?
219                    {
220                        runs.push(run);
221                    }
222                    pending_size = EncodedBatchSizer::new(&self.run_schema)?;
223                    top_k_heap = false;
224                }
225            }
226        }
227
228        let force_spill = !runs.is_empty();
229        if let Some(run) = self.finish_run(pending, force_spill, &arena)? {
230            runs.push(run);
231        }
232        Ok(runs)
233    }
234
235    fn finish_run(
236        &self,
237        records: Vec<DecoratedRow>,
238        force_spill: bool,
239        arena: &SpillFileArena,
240    ) -> ExecResult<Option<SortedRun>> {
241        let mut records = records;
242        uqa_core::ordering::sort_by_with_control(
243            &mut records,
244            &mut || Ok(()),
245            |left, right, _| {
246                compare_records(&self.comparison(), self.input_slots.len(), left, right)
247            },
248        )?;
249        if let Some(keep) = self.keep {
250            records.truncate(keep);
251        }
252        if records.is_empty() {
253            return Ok(None);
254        }
255
256        let mut buffer = self.create_run_buffer(arena);
257        let mut writer = RunBatchWriter::new(self.run_schema.clone())?;
258        for record in records {
259            writer.push(&mut buffer, record.row)?;
260        }
261        writer.finish(&mut buffer)?;
262        if force_spill {
263            buffer.spill_pending()?;
264        }
265        Ok(Some(SortedRun { buffer }))
266    }
267
268    fn collapse_runs(&mut self, mut runs: Vec<SortedRun>) -> ExecResult<Option<SortedRun>> {
269        while runs.len() > 1 {
270            let arena = SpillFileArena::new(self.spill_directory.clone());
271            self.merge_pass_count = self.merge_pass_count.checked_add(1).ok_or_else(|| {
272                ExecError::Other("external sort merge-pass count overflow".into())
273            })?;
274            let mut inputs = runs.into_iter();
275            let mut merged = Vec::new();
276            loop {
277                let group: Vec<_> = inputs.by_ref().take(EXTERNAL_SORT_MERGE_FAN_IN).collect();
278                if group.is_empty() {
279                    break;
280                }
281                merged.push(merge_group(
282                    group,
283                    &self.comparison(),
284                    self.keep,
285                    self.create_run_buffer(&arena),
286                    &self.run_schema,
287                    self.input_slots.len(),
288                )?);
289            }
290            runs = merged;
291        }
292        Ok(runs.pop())
293    }
294}
295
296impl PhysicalOperator for ExternalSort<'_> {
297    fn row_schema(&self) -> &RowSchema {
298        &self.schema
299    }
300
301    fn output_ordering(&self) -> &[PhysicalOrder] {
302        &self.ordering
303    }
304
305    fn backward_scan_support(&self) -> crate::BackwardScanSupport {
306        crate::BackwardScanSupport::Materialize
307    }
308
309    fn open(&mut self) -> ExecResult<()> {
310        self.output = None;
311        self.key_types = self
312            .keys
313            .iter()
314            .map(|key| self.evaluator.expression_type(&key.expr, &self.schema))
315            .collect::<Result<_, _>>()?;
316        for state in &mut self.comparison_states {
317            *state = EnumComparisonState::default();
318        }
319        self.initial_run_count = 0;
320        self.merge_pass_count = 0;
321        self.child.open()?;
322
323        let runs = self.build_initial_runs()?;
324        self.initial_run_count = runs.len();
325        let Some(mut final_run) = self.collapse_runs(runs)? else {
326            return Ok(());
327        };
328        self.output = Some(final_run.buffer.drain()?);
329        Ok(())
330    }
331
332    fn next(&mut self) -> ExecResult<Option<Batch>> {
333        let Some(output) = self.output.as_mut() else {
334            return Ok(None);
335        };
336        loop {
337            let Some(batch) = output.next().transpose()? else {
338                return Ok(None);
339            };
340            validate_run_batch(&batch, &self.run_schema)?;
341            if batch.rows.is_empty() {
342                continue;
343            }
344            let rows = batch
345                .rows
346                .into_iter()
347                .map(|row| row.into_prefix(self.input_slots.len()))
348                .collect();
349            return Ok(Some(Batch::from_physical_rows(self.schema.clone(), rows)));
350        }
351    }
352
353    fn close(&mut self) -> ExecResult<()> {
354        self.output = None;
355        self.child.close()
356    }
357}
358
359struct SortedRun {
360    buffer: SpillBuffer,
361}
362
363struct DecoratedRow {
364    row: PhysicalRow,
365    sequence: u64,
366}
367
368fn decode_record(
369    schema: &RowSchema,
370    row: PhysicalRow,
371    source_width: usize,
372    expected_key_count: usize,
373) -> ExecResult<DecoratedRow> {
374    let sequence_position = source_width
375        .checked_add(expected_key_count)
376        .ok_or_else(|| ExecError::Other("external sort run width overflow".into()))?;
377    if schema.physical_width() != sequence_position.saturating_add(1) {
378        return Err(ExecError::Other(format!(
379            "invalid external sort run key count: expected {expected_key_count}"
380        )));
381    }
382    for index in source_width..sequence_position {
383        if row.value(index).is_none() {
384            return Err(ExecError::Other(format!(
385                "external sort run is missing key {}",
386                index - source_width
387            )));
388        }
389    }
390    let sequence = match row.value(sequence_position) {
391        Some(Value::Bytes(bytes)) if bytes.len() == std::mem::size_of::<u64>() => {
392            let bytes: [u8; 8] = bytes
393                .as_slice()
394                .try_into()
395                .map_err(|_| ExecError::Other("invalid external sort run sequence width".into()))?;
396            u64::from_be_bytes(bytes)
397        }
398        _ => {
399            return Err(ExecError::Other(
400                "invalid external sort run sequence".into(),
401            ))
402        }
403    };
404    Ok(DecoratedRow { row, sequence })
405}
406
407fn validate_run_batch(batch: &Batch, expected: &RowSchema) -> ExecResult<()> {
408    if &batch.schema == expected {
409        Ok(())
410    } else {
411        Err(ExecError::Other(format!(
412            "invalid external sort run schema: expected {:?}, got {:?}",
413            expected.columns(),
414            batch.schema.columns()
415        )))
416    }
417}
418
419struct RunBatchWriter {
420    schema: RowSchema,
421    pending: Vec<PhysicalRow>,
422    pending_size: EncodedBatchSizer,
423}
424
425impl RunBatchWriter {
426    fn new(schema: RowSchema) -> ExecResult<Self> {
427        let pending_size = EncodedBatchSizer::new(&schema)?;
428        Ok(Self {
429            schema,
430            pending: Vec::new(),
431            pending_size,
432        })
433    }
434
435    fn push(&mut self, output: &mut SpillBuffer, record: PhysicalRow) -> ExecResult<()> {
436        let mut candidate_size = self.pending_size;
437        candidate_size.append(&record)?;
438        let exceeds_budget = candidate_size.bytes() > output.budget_bytes();
439        if exceeds_budget && !self.pending.is_empty() {
440            self.flush(output)?;
441            candidate_size = self.pending_size;
442            candidate_size.append(&record)?;
443        }
444        self.pending.push(record);
445        self.pending_size = candidate_size;
446        if self.pending_size.bytes() > output.budget_bytes() {
447            self.flush(output)?;
448        }
449        Ok(())
450    }
451
452    fn finish(mut self, output: &mut SpillBuffer) -> ExecResult<()> {
453        self.flush(output)
454    }
455
456    fn flush(&mut self, output: &mut SpillBuffer) -> ExecResult<()> {
457        if self.pending.is_empty() {
458            return Ok(());
459        }
460        output.push(Batch::from_physical_rows(
461            self.schema.clone(),
462            std::mem::take(&mut self.pending),
463        ))?;
464        self.pending_size = EncodedBatchSizer::new(&self.schema)?;
465        Ok(())
466    }
467}
468
469struct MergeCursor {
470    batches: SpillDrain,
471    rows: std::vec::IntoIter<PhysicalRow>,
472    schema: RowSchema,
473    source_width: usize,
474    key_count: usize,
475}
476
477impl MergeCursor {
478    fn new(
479        mut buffer: SpillBuffer,
480        schema: RowSchema,
481        source_width: usize,
482        key_count: usize,
483    ) -> ExecResult<Self> {
484        Ok(Self {
485            batches: buffer.drain()?,
486            rows: Vec::new().into_iter(),
487            schema,
488            source_width,
489            key_count,
490        })
491    }
492
493    fn next_record(&mut self) -> ExecResult<Option<DecoratedRow>> {
494        loop {
495            if let Some(row) = self.rows.next() {
496                return decode_record(&self.schema, row, self.source_width, self.key_count)
497                    .map(Some);
498            }
499            let Some(batch) = self.batches.next().transpose()? else {
500                return Ok(None);
501            };
502            validate_run_batch(&batch, &self.schema)?;
503            self.rows = batch.rows.into_iter();
504        }
505    }
506}
507
508struct HeapItem {
509    record: DecoratedRow,
510    cursor: usize,
511}
512
513fn merge_group(
514    runs: Vec<SortedRun>,
515    keys: &SortComparison<'_>,
516    keep: Option<usize>,
517    mut output: SpillBuffer,
518    run_schema: &RowSchema,
519    source_width: usize,
520) -> ExecResult<SortedRun> {
521    debug_assert!(!runs.is_empty());
522    debug_assert!(runs.len() <= EXTERNAL_SORT_MERGE_FAN_IN);
523    let mut cursors = Vec::with_capacity(runs.len());
524    let mut heap = Vec::with_capacity(runs.len());
525
526    for run in runs {
527        cursors.push(MergeCursor::new(
528            run.buffer,
529            run_schema.clone(),
530            source_width,
531            keys.keys.len(),
532        )?);
533        let cursor = cursors.len() - 1;
534        if let Some(record) = cursors[cursor].next_record()? {
535            heap_push(&mut heap, HeapItem { record, cursor }, keys, source_width)?;
536        }
537    }
538
539    let mut writer = RunBatchWriter::new(run_schema.clone())?;
540    let mut emitted = 0_usize;
541    while !heap.is_empty() && keep.is_none_or(|keep| emitted < keep) {
542        let item = heap_pop(&mut heap, keys, source_width)?
543            .ok_or_else(|| ExecError::Other("external sort merge heap became empty".into()))?;
544        let cursor = item.cursor;
545        writer.push(&mut output, item.record.row)?;
546        emitted = emitted
547            .checked_add(1)
548            .ok_or_else(|| ExecError::Other("external sort emitted-row count overflow".into()))?;
549        if let Some(record) = cursors[cursor].next_record()? {
550            heap_push(&mut heap, HeapItem { record, cursor }, keys, source_width)?;
551        }
552    }
553    writer.finish(&mut output)?;
554    output.spill_pending()?;
555    Ok(SortedRun { buffer: output })
556}
557
558fn compare_heap_items(
559    keys: &SortComparison<'_>,
560    source_width: usize,
561    left: &HeapItem,
562    right: &HeapItem,
563) -> ExecResult<Ordering> {
564    compare_records(keys, source_width, &left.record, &right.record)
565}
566
567fn heap_push(
568    heap: &mut Vec<HeapItem>,
569    item: HeapItem,
570    keys: &SortComparison<'_>,
571    source_width: usize,
572) -> ExecResult<()> {
573    heap.push(item);
574    let mut child = heap.len() - 1;
575    while child > 0 {
576        let parent = (child - 1) / 2;
577        if compare_heap_items(keys, source_width, &heap[child], &heap[parent])? != Ordering::Less {
578            break;
579        }
580        heap.swap(child, parent);
581        child = parent;
582    }
583    Ok(())
584}
585
586fn heap_pop(
587    heap: &mut Vec<HeapItem>,
588    keys: &SortComparison<'_>,
589    source_width: usize,
590) -> ExecResult<Option<HeapItem>> {
591    if heap.is_empty() {
592        return Ok(None);
593    }
594    let smallest = heap.swap_remove(0);
595    let mut parent = 0;
596    loop {
597        let left = parent * 2 + 1;
598        if left >= heap.len() {
599            break;
600        }
601        let right = left + 1;
602        let child = if right < heap.len()
603            && compare_heap_items(keys, source_width, &heap[right], &heap[left])? == Ordering::Less
604        {
605            right
606        } else {
607            left
608        };
609        if compare_heap_items(keys, source_width, &heap[child], &heap[parent])? != Ordering::Less {
610            break;
611        }
612        heap.swap(parent, child);
613        parent = child;
614    }
615    Ok(Some(smallest))
616}
617
618#[cfg(test)]
619mod tests {
620    mod files;
621
622    mod enums;
623    mod legacy_vectors;
624    mod top_k;
625    use crate::RowSchemaExecution;
626    use std::collections::BTreeMap;
627    use std::io::Write as _;
628    use std::sync::Arc;
629
630    use super::*;
631    use crate::physical::{run_to_batches, run_to_rows};
632    use crate::scalar::ScalarExpr;
633    use crate::scan::TableScan;
634    use uqa_sql::expr::RowLookup as _;
635    use uqa_sql::ResultRow;
636
637    struct Columns;
638
639    struct PhysicalRowsScan {
640        schema: RowSchema,
641        rows: Option<Vec<PhysicalRow>>,
642    }
643
644    impl PhysicalOperator for PhysicalRowsScan {
645        fn row_schema(&self) -> &RowSchema {
646            &self.schema
647        }
648
649        fn open(&mut self) -> ExecResult<()> {
650            Ok(())
651        }
652
653        fn next(&mut self) -> ExecResult<Option<Batch>> {
654            Ok(self
655                .rows
656                .take()
657                .map(|rows| Batch::from_physical_rows(self.schema.clone(), rows)))
658        }
659
660        fn close(&mut self) -> ExecResult<()> {
661            Ok(())
662        }
663    }
664
665    impl crate::relational::ExpressionEvaluator for Columns {
666        fn evaluate(
667            &self,
668            expression: &ScalarExpr,
669            row: &dyn uqa_sql::expr::RowLookup,
670        ) -> ExecResult<Value> {
671            match expression {
672                ScalarExpr::Column(name) => Ok(row.column(name).cloned().unwrap_or(Value::Null)),
673                _ => Err(ExecError::Other(
674                    "test evaluator only supports columns".into(),
675                )),
676            }
677        }
678    }
679
680    fn row(key: i64, input: i64) -> ResultRow {
681        BTreeMap::from([
682            ("key".into(), Value::Int(key)),
683            ("input".into(), Value::Int(input)),
684        ])
685    }
686
687    fn sort(rows: Vec<ResultRow>, budget: usize, keep: Option<usize>) -> ExternalSort<'static> {
688        ExternalSort::new(
689            Box::new(TableScan::from_rows(
690                vec!["key".into(), "input".into()],
691                rows,
692            )),
693            vec![SortKey {
694                expr: ScalarExpr::Column("key".into()),
695                descending: false,
696                nulls_first: None,
697            }],
698            Arc::new(Columns),
699            keep,
700            budget,
701        )
702    }
703
704    fn int_column(rows: &[ResultRow], column: &str) -> Vec<i64> {
705        rows.iter()
706            .map(|row| match row.get(column) {
707                Some(Value::Int(value)) => *value,
708                value => panic!("unexpected {column} value: {value:?}"),
709            })
710            .collect()
711    }
712
713    #[test]
714    fn tiny_budget_builds_many_runs_and_multi_pass_merge() {
715        let rows = (0..(EXTERNAL_SORT_MERGE_FAN_IN as i64 * 2 + 5))
716            .rev()
717            .map(|value| row(value, value))
718            .collect();
719        let mut operator = sort(rows, 1, None);
720        operator.open().unwrap();
721        assert!(operator.initial_run_count() > EXTERNAL_SORT_MERGE_FAN_IN);
722        assert!(operator.merge_pass_count() >= 2);
723        let mut output = Vec::new();
724        while let Some(batch) = operator.next().unwrap() {
725            output.extend(batch.into_result_rows());
726        }
727        operator.close().unwrap();
728        assert_eq!(
729            int_column(&output, "key"),
730            (0..(EXTERNAL_SORT_MERGE_FAN_IN as i64 * 2 + 5)).collect::<Vec<_>>()
731        );
732    }
733
734    #[test]
735    fn equal_keys_keep_original_input_order_across_runs() {
736        let rows = (0..40).map(|input| row(7, input)).collect();
737        let mut operator = sort(rows, 1, None);
738        let (_, output) = run_to_rows(&mut operator).unwrap();
739        assert_eq!(int_column(&output, "input"), (0..40).collect::<Vec<_>>());
740    }
741
742    #[test]
743    fn keep_is_global_top_k_across_multiple_runs() {
744        let rows = (0..100).rev().map(|value| row(value, value)).collect();
745        let mut operator = sort(rows, 1, Some(7));
746        let (_, output) = run_to_rows(&mut operator).unwrap();
747        assert_eq!(int_column(&output, "key"), (0..7).collect::<Vec<_>>());
748    }
749
750    #[test]
751    fn spill_creation_error_is_propagated() {
752        let not_a_directory = tempfile::NamedTempFile::new().unwrap();
753        let mut operator = sort(vec![row(1, 0)], 0, None)
754            .with_spill_directory(not_a_directory.path().to_path_buf());
755        let error = operator.open().unwrap_err();
756        assert!(error.to_string().contains("failed to create spill file"));
757    }
758
759    #[test]
760    fn large_budget_single_run_does_not_create_a_spill_file() {
761        let not_a_directory = tempfile::NamedTempFile::new().unwrap();
762        let rows = (0..20).rev().map(|value| row(value, value)).collect();
763        let mut operator =
764            sort(rows, 1_000_000, None).with_spill_directory(not_a_directory.path().to_path_buf());
765        let (_, output) = run_to_rows(&mut operator).unwrap();
766        assert_eq!(int_column(&output, "key"), (0..20).collect::<Vec<_>>());
767        assert_eq!(operator.initial_run_count(), 1);
768        assert_eq!(operator.merge_pass_count(), 0);
769    }
770
771    #[test]
772    fn spill_batch_schema_overhead_is_amortized_across_sort_rows() {
773        let rows = (0..20_000).rev().map(|value| row(value, value)).collect();
774        let mut operator = sort(rows, 4 * 1024 * 1024, None);
775
776        operator.open().unwrap();
777        assert_eq!(operator.initial_run_count(), 1);
778        assert_eq!(operator.merge_pass_count(), 0);
779        operator.close().unwrap();
780    }
781
782    #[test]
783    fn mixed_lock_origins_add_metadata_for_origin_free_rows_to_the_batch_budget() {
784        let schema = RowSchema::new(vec!["value".into()]);
785        let plain = PhysicalRow::from_values(vec![Value::Int(1)]);
786        let locked = PhysicalRow::from_values(vec![Value::Int(2)])
787            .with_lock_origin(crate::RowLockOrigin::new("source", "public.source", 2));
788        let overhead = EncodedBatchSizer::new(&schema).unwrap().bytes();
789        let mut plain_size = EncodedBatchSizer::new(&schema).unwrap();
790        plain_size.append(&plain).unwrap();
791        let plain_record_bytes = plain_size.bytes() - overhead;
792        let mut locked_size = EncodedBatchSizer::new(&schema).unwrap();
793        locked_size.append(&locked).unwrap();
794        let locked_record_bytes = locked_size.bytes() - overhead;
795        let mut size = EncodedBatchSizer::new(&schema).unwrap();
796        size.append(&plain).unwrap();
797        let without_retroactive_metadata = overhead + plain_record_bytes + locked_record_bytes;
798        size.append(&locked).unwrap();
799        let batch = Batch::from_physical_rows(schema, vec![plain, locked]);
800
801        assert_eq!(size.bytes(), SpillBuffer::encoded_size(&batch).unwrap());
802        assert_eq!(size.bytes(), without_retroactive_metadata + 8);
803    }
804
805    #[test]
806    fn corrupt_run_read_error_is_propagated() {
807        let keys = vec![SortKey {
808            expr: ScalarExpr::Column("key".into()),
809            descending: false,
810            nulls_first: None,
811        }];
812        let schema = run_schema(2, 1);
813        let record = PhysicalRow::from_values(vec![
814            Value::Int(1),
815            Value::Int(0),
816            Value::Int(1),
817            Value::Bytes(0_u64.to_be_bytes().to_vec()),
818        ]);
819        let mut buffer = SpillBuffer::new(0);
820        buffer
821            .push(Batch::from_physical_rows(schema.clone(), vec![record]))
822            .unwrap();
823        let path = buffer.spill_path().unwrap().to_path_buf();
824        let mut corrupt = std::fs::OpenOptions::new().append(true).open(path).unwrap();
825        corrupt.write_all(&1_u64.to_le_bytes()).unwrap();
826        corrupt.write_all(&[0xff]).unwrap();
827        corrupt.flush().unwrap();
828
829        let result = merge_group(
830            vec![SortedRun { buffer }],
831            &SortComparison {
832                keys: &keys,
833                types: &[],
834                enums: None,
835                states: &[],
836                equality_keys: false,
837            },
838            None,
839            SpillBuffer::new(0),
840            &schema,
841            2,
842        );
843        let error = match result {
844            Ok(_) => panic!("corrupt run unexpectedly merged"),
845            Err(error) => error,
846        };
847        assert!(error
848            .to_string()
849            .contains("invalid authenticated temporary file length"));
850    }
851
852    #[test]
853    fn corrupt_run_key_width_is_reported_before_comparison() {
854        let schema = run_schema(2, 0);
855        let record = PhysicalRow::from_values(vec![
856            Value::Int(1),
857            Value::Int(0),
858            Value::Bytes(0_u64.to_be_bytes().to_vec()),
859        ]);
860        let error = match decode_record(&schema, record, 2, 1) {
861            Ok(_) => panic!("corrupt run record unexpectedly decoded"),
862            Err(error) => error,
863        };
864        assert!(error
865            .to_string()
866            .contains("invalid external sort run key count"));
867    }
868
869    #[test]
870    fn forced_spill_preserves_hidden_alias_and_public_column_slots() {
871        let base = RowSchema::new(vec!["value".into(), "key".into()]);
872        let aliased = RowSchema::with_identity_aliases(
873            &base,
874            &[(crate::ColumnIdentity::qualified("source", "value"), 0)],
875        );
876        let schema = RowSchema::append(&aliased, &["value".into()]);
877        let rows = vec![
878            PhysicalRow::from_values(vec![Value::Str("source-b".into()), Value::Int(2)])
879                .append_values(vec![Value::Str("projected-b".into())]),
880            PhysicalRow::from_values(vec![Value::Str("source-a".into()), Value::Int(1)])
881                .append_values(vec![Value::Str("projected-a".into())]),
882        ];
883        let scan = PhysicalRowsScan {
884            schema,
885            rows: Some(rows),
886        };
887        let mut operator = ExternalSort::new(
888            Box::new(scan),
889            vec![SortKey {
890                expr: ScalarExpr::Column("key".into()),
891                descending: false,
892                nulls_first: None,
893            }],
894            Arc::new(Columns),
895            None,
896            1,
897        );
898
899        let batches = run_to_batches(&mut operator).unwrap();
900        assert!(operator.initial_run_count() > 1);
901        let values = batches
902            .iter()
903            .flat_map(|batch| {
904                batch.rows.iter().map(|row| {
905                    let view = batch.schema.view(row);
906                    (
907                        view.get("value").cloned(),
908                        view.qualified_column("source", "value").cloned(),
909                    )
910                })
911            })
912            .collect::<Vec<_>>();
913        assert_eq!(
914            values,
915            vec![
916                (
917                    Some(Value::Str("projected-a".into())),
918                    Some(Value::Str("source-a".into()))
919                ),
920                (
921                    Some(Value::Str("projected-b".into())),
922                    Some(Value::Str("source-b".into()))
923                ),
924            ]
925        );
926    }
927
928    #[test]
929    fn forced_spill_preserves_duplicate_logical_columns_positionally() {
930        let schema = RowSchema::new(vec!["value".into(), "value".into(), "key".into()]);
931        let scan = PhysicalRowsScan {
932            schema,
933            rows: Some(vec![
934                PhysicalRow::from_values(vec![
935                    Value::Str("left-b".into()),
936                    Value::Str("right-b".into()),
937                    Value::Int(2),
938                ]),
939                PhysicalRow::from_values(vec![
940                    Value::Str("left-a".into()),
941                    Value::Str("right-a".into()),
942                    Value::Int(1),
943                ]),
944            ]),
945        };
946        let mut operator = ExternalSort::new(
947            Box::new(scan),
948            vec![SortKey {
949                expr: ScalarExpr::Column("key".into()),
950                descending: false,
951                nulls_first: None,
952            }],
953            Arc::new(Columns),
954            None,
955            1,
956        );
957
958        let batches = run_to_batches(&mut operator).unwrap();
959        assert!(operator.initial_run_count() > 1);
960        assert_eq!(operator.schema(), ["value", "value", "key"]);
961        let values = batches
962            .iter()
963            .flat_map(|batch| {
964                batch.rows.iter().map(|row| {
965                    let view = batch.schema.view(row);
966                    (view.value_at(0).cloned(), view.value_at(1).cloned())
967                })
968            })
969            .collect::<Vec<_>>();
970        assert_eq!(
971            values,
972            vec![
973                (
974                    Some(Value::Str("left-a".into())),
975                    Some(Value::Str("right-a".into()))
976                ),
977                (
978                    Some(Value::Str("left-b".into())),
979                    Some(Value::Str("right-b".into()))
980                ),
981            ]
982        );
983    }
984
985    #[test]
986    fn empty_input_and_zero_keep_are_empty() {
987        let mut empty = sort(Vec::new(), 1, None);
988        assert_eq!(run_to_rows(&mut empty).unwrap().1.len(), 0);
989
990        let rows = (0..10).map(|value| row(value, value)).collect();
991        let mut zero = sort(rows, 1, Some(0));
992        assert_eq!(run_to_rows(&mut zero).unwrap().1.len(), 0);
993    }
994}