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