1use 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
35pub 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
45pub 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 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 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 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 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}