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::{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
37pub 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
47pub 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 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 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 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 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 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}