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