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 output_ordering(&self) -> &[PhysicalOrder] {
312        &self.ordering
313    }
314
315    fn backward_scan_support(&self) -> crate::BackwardScanSupport {
316        crate::BackwardScanSupport::Materialize
317    }
318
319    fn open(&mut self) -> ExecResult<()> {
320        self.output = None;
321        if let Some(cancellation) = &self.cancellation {
322            cancellation.check().map_err(uqa_sql::SQLError::Cancelled)?;
323        }
324        self.key_types = if self.comparison_domain == SortComparisonDomain::Physical {
325            Vec::new()
326        } else {
327            self.keys
328                .iter()
329                .map(|key| self.evaluator.expression_type(&key.expr, &self.schema))
330                .collect::<Result<_, _>>()?
331        };
332        for state in &mut self.comparison_states {
333            *state = EnumComparisonState::default();
334        }
335        self.initial_run_count = 0;
336        self.merge_pass_count = 0;
337        self.child.open()?;
338
339        let runs = self.build_initial_runs()?;
340        self.initial_run_count = runs.len();
341        let Some(mut final_run) = self.collapse_runs(runs)? else {
342            return Ok(());
343        };
344        self.output = Some(final_run.buffer.drain()?);
345        Ok(())
346    }
347
348    fn next(&mut self) -> ExecResult<Option<Batch>> {
349        let Some(output) = self.output.as_mut() else {
350            return Ok(None);
351        };
352        loop {
353            let Some(batch) = output.next().transpose()? else {
354                return Ok(None);
355            };
356            validate_run_batch(&batch, &self.run_schema)?;
357            if batch.rows.is_empty() {
358                continue;
359            }
360            let rows = batch
361                .rows
362                .into_iter()
363                .map(|row| row.into_prefix(self.input_slots.len()))
364                .collect();
365            return Ok(Some(Batch::from_physical_rows(self.schema.clone(), rows)));
366        }
367    }
368
369    fn close(&mut self) -> ExecResult<()> {
370        self.output = None;
371        self.child.close()
372    }
373}
374
375struct SortedRun {
376    buffer: SpillBuffer,
377}
378
379struct DecoratedRow {
380    row: PhysicalRow,
381    sequence: u64,
382}
383
384fn decode_record(
385    schema: &RowSchema,
386    row: PhysicalRow,
387    source_width: usize,
388    expected_key_count: usize,
389) -> ExecResult<DecoratedRow> {
390    let sequence_position = source_width
391        .checked_add(expected_key_count)
392        .ok_or_else(|| ExecError::Other("external sort run width overflow".into()))?;
393    if schema.physical_width() != sequence_position.saturating_add(1) {
394        return Err(ExecError::Other(format!(
395            "invalid external sort run key count: expected {expected_key_count}"
396        )));
397    }
398    for index in source_width..sequence_position {
399        if row.value(index).is_none() {
400            return Err(ExecError::Other(format!(
401                "external sort run is missing key {}",
402                index - source_width
403            )));
404        }
405    }
406    let sequence = match row.value(sequence_position) {
407        Some(Value::Bytes(bytes)) if bytes.len() == std::mem::size_of::<u64>() => {
408            let bytes: [u8; 8] = bytes
409                .as_slice()
410                .try_into()
411                .map_err(|_| ExecError::Other("invalid external sort run sequence width".into()))?;
412            u64::from_be_bytes(bytes)
413        }
414        _ => {
415            return Err(ExecError::Other(
416                "invalid external sort run sequence".into(),
417            ))
418        }
419    };
420    Ok(DecoratedRow { row, sequence })
421}
422
423fn validate_run_batch(batch: &Batch, expected: &RowSchema) -> ExecResult<()> {
424    if &batch.schema == expected {
425        Ok(())
426    } else {
427        Err(ExecError::Other(format!(
428            "invalid external sort run schema: expected {:?}, got {:?}",
429            expected.columns(),
430            batch.schema.columns()
431        )))
432    }
433}
434
435struct MergeCursor {
436    batches: SpillDrain,
437    rows: std::vec::IntoIter<PhysicalRow>,
438    schema: RowSchema,
439    source_width: usize,
440    key_count: usize,
441}
442
443impl MergeCursor {
444    fn new(
445        mut buffer: SpillBuffer,
446        schema: RowSchema,
447        source_width: usize,
448        key_count: usize,
449    ) -> ExecResult<Self> {
450        Ok(Self {
451            batches: buffer.drain()?,
452            rows: Vec::new().into_iter(),
453            schema,
454            source_width,
455            key_count,
456        })
457    }
458
459    fn next_record(&mut self) -> ExecResult<Option<DecoratedRow>> {
460        loop {
461            if let Some(row) = self.rows.next() {
462                return decode_record(&self.schema, row, self.source_width, self.key_count)
463                    .map(Some);
464            }
465            let Some(batch) = self.batches.next().transpose()? else {
466                return Ok(None);
467            };
468            validate_run_batch(&batch, &self.schema)?;
469            self.rows = batch.rows.into_iter();
470        }
471    }
472}
473
474struct HeapItem {
475    record: DecoratedRow,
476    cursor: usize,
477}
478
479fn merge_group(
480    runs: Vec<SortedRun>,
481    keys: &SortComparison<'_>,
482    keep: Option<usize>,
483    mut output: SpillBuffer,
484    run_schema: &RowSchema,
485    source_width: usize,
486) -> ExecResult<SortedRun> {
487    debug_assert!(!runs.is_empty());
488    debug_assert!(runs.len() <= EXTERNAL_SORT_MERGE_FAN_IN);
489    let mut cursors = Vec::with_capacity(runs.len());
490    let mut heap = Vec::with_capacity(runs.len());
491
492    for run in runs {
493        cursors.push(MergeCursor::new(
494            run.buffer,
495            run_schema.clone(),
496            source_width,
497            keys.keys.len(),
498        )?);
499        let cursor = cursors.len() - 1;
500        if let Some(record) = cursors[cursor].next_record()? {
501            heap_push(&mut heap, HeapItem { record, cursor }, keys, source_width)?;
502        }
503    }
504
505    let mut writer = SpillBatchWriter::new(run_schema.clone())?;
506    let mut emitted = 0_usize;
507    while !heap.is_empty() && keep.is_none_or(|keep| emitted < keep) {
508        let item = heap_pop(&mut heap, keys, source_width)?
509            .ok_or_else(|| ExecError::Other("external sort merge heap became empty".into()))?;
510        let cursor = item.cursor;
511        writer.push(&mut output, item.record.row)?;
512        emitted = emitted
513            .checked_add(1)
514            .ok_or_else(|| ExecError::Other("external sort emitted-row count overflow".into()))?;
515        if let Some(record) = cursors[cursor].next_record()? {
516            heap_push(&mut heap, HeapItem { record, cursor }, keys, source_width)?;
517        }
518    }
519    writer.finish(&mut output)?;
520    output.spill_pending()?;
521    Ok(SortedRun { buffer: output })
522}
523
524fn compare_heap_items(
525    keys: &SortComparison<'_>,
526    source_width: usize,
527    left: &HeapItem,
528    right: &HeapItem,
529) -> ExecResult<Ordering> {
530    compare_records(keys, source_width, &left.record, &right.record)
531}
532
533fn heap_push(
534    heap: &mut Vec<HeapItem>,
535    item: HeapItem,
536    keys: &SortComparison<'_>,
537    source_width: usize,
538) -> ExecResult<()> {
539    heap.push(item);
540    let mut child = heap.len() - 1;
541    while child > 0 {
542        let parent = (child - 1) / 2;
543        if compare_heap_items(keys, source_width, &heap[child], &heap[parent])? != Ordering::Less {
544            break;
545        }
546        heap.swap(child, parent);
547        child = parent;
548    }
549    Ok(())
550}
551
552fn heap_pop(
553    heap: &mut Vec<HeapItem>,
554    keys: &SortComparison<'_>,
555    source_width: usize,
556) -> ExecResult<Option<HeapItem>> {
557    if heap.is_empty() {
558        return Ok(None);
559    }
560    let smallest = heap.swap_remove(0);
561    let mut parent = 0;
562    loop {
563        let left = parent * 2 + 1;
564        if left >= heap.len() {
565            break;
566        }
567        let right = left + 1;
568        let child = if right < heap.len()
569            && compare_heap_items(keys, source_width, &heap[right], &heap[left])? == Ordering::Less
570        {
571            right
572        } else {
573            left
574        };
575        if compare_heap_items(keys, source_width, &heap[child], &heap[parent])? != Ordering::Less {
576            break;
577        }
578        heap.swap(parent, child);
579        parent = child;
580    }
581    Ok(Some(smallest))
582}
583
584#[cfg(test)]
585mod tests {
586    mod files;
587    mod physical_keys;
588
589    mod enums;
590    mod legacy_vectors;
591    mod top_k;
592    use crate::RowSchemaExecution;
593    use std::collections::BTreeMap;
594    use std::io::Write as _;
595    use std::sync::Arc;
596
597    use super::*;
598    use crate::physical::{run_to_batches, run_to_rows};
599    use crate::scalar::ScalarExpr;
600    use crate::scan::TableScan;
601    use uqa_sql::expr::RowLookup as _;
602    use uqa_sql::ResultRow;
603
604    struct Columns;
605
606    struct PhysicalRowsScan {
607        schema: RowSchema,
608        rows: Option<Vec<PhysicalRow>>,
609    }
610
611    impl PhysicalOperator for PhysicalRowsScan {
612        fn row_schema(&self) -> &RowSchema {
613            &self.schema
614        }
615
616        fn open(&mut self) -> ExecResult<()> {
617            Ok(())
618        }
619
620        fn next(&mut self) -> ExecResult<Option<Batch>> {
621            Ok(self
622                .rows
623                .take()
624                .map(|rows| Batch::from_physical_rows(self.schema.clone(), rows)))
625        }
626
627        fn close(&mut self) -> ExecResult<()> {
628            Ok(())
629        }
630    }
631
632    impl crate::relational::ExpressionEvaluator for Columns {
633        fn evaluate(
634            &self,
635            expression: &ScalarExpr,
636            row: &dyn uqa_sql::expr::RowLookup,
637        ) -> ExecResult<Value> {
638            match expression {
639                ScalarExpr::Column(name) => Ok(row.column(name).cloned().unwrap_or(Value::Null)),
640                _ => Err(ExecError::Other(
641                    "test evaluator only supports columns".into(),
642                )),
643            }
644        }
645    }
646
647    fn row(key: i64, input: i64) -> ResultRow {
648        BTreeMap::from([
649            ("key".into(), Value::Int(key)),
650            ("input".into(), Value::Int(input)),
651        ])
652    }
653
654    fn sort(rows: Vec<ResultRow>, budget: usize, keep: Option<usize>) -> ExternalSort<'static> {
655        ExternalSort::new(
656            Box::new(TableScan::from_rows(
657                vec!["key".into(), "input".into()],
658                rows,
659            )),
660            vec![SortKey {
661                expr: ScalarExpr::Column("key".into()),
662                descending: false,
663                nulls_first: None,
664            }],
665            Arc::new(Columns),
666            keep,
667            budget,
668        )
669    }
670
671    fn int_column(rows: &[ResultRow], column: &str) -> Vec<i64> {
672        rows.iter()
673            .map(|row| match row.get(column) {
674                Some(Value::Int(value)) => *value,
675                value => panic!("unexpected {column} value: {value:?}"),
676            })
677            .collect()
678    }
679
680    #[test]
681    fn tiny_budget_builds_many_runs_and_multi_pass_merge() {
682        let rows = (0..(EXTERNAL_SORT_MERGE_FAN_IN as i64 * 2 + 5))
683            .rev()
684            .map(|value| row(value, value))
685            .collect();
686        let mut operator = sort(rows, 1, None);
687        operator.open().unwrap();
688        assert!(operator.initial_run_count() > EXTERNAL_SORT_MERGE_FAN_IN);
689        assert!(operator.merge_pass_count() >= 2);
690        let mut output = Vec::new();
691        while let Some(batch) = operator.next().unwrap() {
692            output.extend(batch.into_result_rows());
693        }
694        operator.close().unwrap();
695        assert_eq!(
696            int_column(&output, "key"),
697            (0..(EXTERNAL_SORT_MERGE_FAN_IN as i64 * 2 + 5)).collect::<Vec<_>>()
698        );
699    }
700
701    #[test]
702    fn equal_keys_keep_original_input_order_across_runs() {
703        let rows = (0..40).map(|input| row(7, input)).collect();
704        let mut operator = sort(rows, 1, None);
705        let (_, output) = run_to_rows(&mut operator).unwrap();
706        assert_eq!(int_column(&output, "input"), (0..40).collect::<Vec<_>>());
707    }
708
709    #[test]
710    fn keep_is_global_top_k_across_multiple_runs() {
711        let rows = (0..100).rev().map(|value| row(value, value)).collect();
712        let mut operator = sort(rows, 1, Some(7));
713        let (_, output) = run_to_rows(&mut operator).unwrap();
714        assert_eq!(int_column(&output, "key"), (0..7).collect::<Vec<_>>());
715    }
716
717    #[test]
718    fn spill_creation_error_is_propagated() {
719        let not_a_directory = tempfile::NamedTempFile::new().unwrap();
720        let mut operator = sort(vec![row(1, 0)], 0, None)
721            .with_spill_directory(not_a_directory.path().to_path_buf());
722        let error = operator.open().unwrap_err();
723        assert!(error.to_string().contains("failed to create spill file"));
724    }
725
726    #[test]
727    fn large_budget_single_run_does_not_create_a_spill_file() {
728        let not_a_directory = tempfile::NamedTempFile::new().unwrap();
729        let rows = (0..20).rev().map(|value| row(value, value)).collect();
730        let mut operator =
731            sort(rows, 1_000_000, None).with_spill_directory(not_a_directory.path().to_path_buf());
732        let (_, output) = run_to_rows(&mut operator).unwrap();
733        assert_eq!(int_column(&output, "key"), (0..20).collect::<Vec<_>>());
734        assert_eq!(operator.initial_run_count(), 1);
735        assert_eq!(operator.merge_pass_count(), 0);
736    }
737
738    #[test]
739    fn spill_batch_schema_overhead_is_amortized_across_sort_rows() {
740        let rows = (0..20_000).rev().map(|value| row(value, value)).collect();
741        let mut operator = sort(rows, 4 * 1024 * 1024, None);
742
743        operator.open().unwrap();
744        assert_eq!(operator.initial_run_count(), 1);
745        assert_eq!(operator.merge_pass_count(), 0);
746        operator.close().unwrap();
747    }
748
749    #[test]
750    fn mixed_lock_origins_add_metadata_for_origin_free_rows_to_the_batch_budget() {
751        let schema = RowSchema::new(vec!["value".into()]);
752        let plain = PhysicalRow::from_values(vec![Value::Int(1)]);
753        let locked = PhysicalRow::from_values(vec![Value::Int(2)])
754            .with_lock_origin(crate::RowLockOrigin::new("source", "public.source", 2));
755        let overhead = EncodedBatchSizer::new(&schema).unwrap().bytes();
756        let mut plain_size = EncodedBatchSizer::new(&schema).unwrap();
757        plain_size.append(&plain).unwrap();
758        let plain_record_bytes = plain_size.bytes() - overhead;
759        let mut locked_size = EncodedBatchSizer::new(&schema).unwrap();
760        locked_size.append(&locked).unwrap();
761        let locked_record_bytes = locked_size.bytes() - overhead;
762        let mut size = EncodedBatchSizer::new(&schema).unwrap();
763        size.append(&plain).unwrap();
764        let without_retroactive_metadata = overhead + plain_record_bytes + locked_record_bytes;
765        size.append(&locked).unwrap();
766        let batch = Batch::from_physical_rows(schema, vec![plain, locked]);
767
768        assert_eq!(size.bytes(), SpillBuffer::encoded_size(&batch).unwrap());
769        assert_eq!(size.bytes(), without_retroactive_metadata + 8);
770    }
771
772    #[test]
773    fn corrupt_run_read_error_is_propagated() {
774        let keys = vec![SortKey {
775            expr: ScalarExpr::Column("key".into()),
776            descending: false,
777            nulls_first: None,
778        }];
779        let schema = run_schema(2, 1);
780        let record = PhysicalRow::from_values(vec![
781            Value::Int(1),
782            Value::Int(0),
783            Value::Int(1),
784            Value::Bytes(0_u64.to_be_bytes().to_vec()),
785        ]);
786        let mut buffer = SpillBuffer::new(0);
787        buffer
788            .push(Batch::from_physical_rows(schema.clone(), vec![record]))
789            .unwrap();
790        let path = buffer.spill_path().unwrap().to_path_buf();
791        let mut corrupt = std::fs::OpenOptions::new().append(true).open(path).unwrap();
792        corrupt.write_all(&1_u64.to_le_bytes()).unwrap();
793        corrupt.write_all(&[0xff]).unwrap();
794        corrupt.flush().unwrap();
795
796        let result = merge_group(
797            vec![SortedRun { buffer }],
798            &SortComparison {
799                keys: &keys,
800                types: &[],
801                enums: None,
802                states: &[],
803                domain: SortComparisonDomain::SqlOrdering,
804                cancellation: None,
805            },
806            None,
807            SpillBuffer::new(0),
808            &schema,
809            2,
810        );
811        let error = match result {
812            Ok(_) => panic!("corrupt run unexpectedly merged"),
813            Err(error) => error,
814        };
815        assert!(error
816            .to_string()
817            .contains("invalid authenticated temporary file length"));
818    }
819
820    #[test]
821    fn corrupt_run_key_width_is_reported_before_comparison() {
822        let schema = run_schema(2, 0);
823        let record = PhysicalRow::from_values(vec![
824            Value::Int(1),
825            Value::Int(0),
826            Value::Bytes(0_u64.to_be_bytes().to_vec()),
827        ]);
828        let error = match decode_record(&schema, record, 2, 1) {
829            Ok(_) => panic!("corrupt run record unexpectedly decoded"),
830            Err(error) => error,
831        };
832        assert!(error
833            .to_string()
834            .contains("invalid external sort run key count"));
835    }
836
837    #[test]
838    fn forced_spill_preserves_hidden_alias_and_public_column_slots() {
839        let base = RowSchema::new(vec!["value".into(), "key".into()]);
840        let aliased = RowSchema::with_identity_aliases(
841            &base,
842            &[(crate::ColumnIdentity::qualified("source", "value"), 0)],
843        );
844        let schema = RowSchema::append(&aliased, &["value".into()]);
845        let rows = vec![
846            PhysicalRow::from_values(vec![Value::Str("source-b".into()), Value::Int(2)])
847                .append_values(vec![Value::Str("projected-b".into())]),
848            PhysicalRow::from_values(vec![Value::Str("source-a".into()), Value::Int(1)])
849                .append_values(vec![Value::Str("projected-a".into())]),
850        ];
851        let scan = PhysicalRowsScan {
852            schema,
853            rows: Some(rows),
854        };
855        let mut operator = ExternalSort::new(
856            Box::new(scan),
857            vec![SortKey {
858                expr: ScalarExpr::Column("key".into()),
859                descending: false,
860                nulls_first: None,
861            }],
862            Arc::new(Columns),
863            None,
864            1,
865        );
866
867        let batches = run_to_batches(&mut operator).unwrap();
868        assert!(operator.initial_run_count() > 1);
869        let values = batches
870            .iter()
871            .flat_map(|batch| {
872                batch.rows.iter().map(|row| {
873                    let view = batch.schema.view(row);
874                    (
875                        view.get("value").cloned(),
876                        view.qualified_column("source", "value").cloned(),
877                    )
878                })
879            })
880            .collect::<Vec<_>>();
881        assert_eq!(
882            values,
883            vec![
884                (
885                    Some(Value::Str("projected-a".into())),
886                    Some(Value::Str("source-a".into()))
887                ),
888                (
889                    Some(Value::Str("projected-b".into())),
890                    Some(Value::Str("source-b".into()))
891                ),
892            ]
893        );
894    }
895
896    #[test]
897    fn forced_spill_preserves_duplicate_logical_columns_positionally() {
898        let schema = RowSchema::new(vec!["value".into(), "value".into(), "key".into()]);
899        let scan = PhysicalRowsScan {
900            schema,
901            rows: Some(vec![
902                PhysicalRow::from_values(vec![
903                    Value::Str("left-b".into()),
904                    Value::Str("right-b".into()),
905                    Value::Int(2),
906                ]),
907                PhysicalRow::from_values(vec![
908                    Value::Str("left-a".into()),
909                    Value::Str("right-a".into()),
910                    Value::Int(1),
911                ]),
912            ]),
913        };
914        let mut operator = ExternalSort::new(
915            Box::new(scan),
916            vec![SortKey {
917                expr: ScalarExpr::Column("key".into()),
918                descending: false,
919                nulls_first: None,
920            }],
921            Arc::new(Columns),
922            None,
923            1,
924        );
925
926        let batches = run_to_batches(&mut operator).unwrap();
927        assert!(operator.initial_run_count() > 1);
928        assert_eq!(operator.schema(), ["value", "value", "key"]);
929        let values = batches
930            .iter()
931            .flat_map(|batch| {
932                batch.rows.iter().map(|row| {
933                    let view = batch.schema.view(row);
934                    (view.value_at(0).cloned(), view.value_at(1).cloned())
935                })
936            })
937            .collect::<Vec<_>>();
938        assert_eq!(
939            values,
940            vec![
941                (
942                    Some(Value::Str("left-a".into())),
943                    Some(Value::Str("right-a".into()))
944                ),
945                (
946                    Some(Value::Str("left-b".into())),
947                    Some(Value::Str("right-b".into()))
948                ),
949            ]
950        );
951    }
952
953    #[test]
954    fn empty_input_and_zero_keep_are_empty() {
955        let mut empty = sort(Vec::new(), 1, None);
956        assert_eq!(run_to_rows(&mut empty).unwrap().1.len(), 0);
957
958        let rows = (0..10).map(|value| row(value, value)).collect();
959        let mut zero = sort(rows, 1, Some(0));
960        assert_eq!(run_to_rows(&mut zero).unwrap().1.len(), 0);
961    }
962}