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