1use crate::RowSchemaExecution;
10use std::cmp::Ordering;
11use std::sync::Arc;
12
13use uqa_core::Value;
14use uqa_sql::ast::{ColumnType, SetOpKind};
15use uqa_sql::expr::RowLookup;
16
17#[cfg(test)]
18use uqa_sql::ResultRow;
19
20use crate::batch::DEFAULT_BATCH_SIZE;
21use crate::{
22 BackwardScanSupport, Batch, ExecError, ExecResult, ExpressionEvaluator, ExternalSort,
23 PhysicalOperator, PhysicalRow, PhysicalScanDirection, RowProjectionValue, RowSchema,
24 ScalarExpr, SharedExpressionEvaluator, SortKey,
25};
26
27struct ColumnEvaluator;
28
29impl ExpressionEvaluator for ColumnEvaluator {
30 fn evaluate(&self, expression: &ScalarExpr, row: &dyn RowLookup) -> ExecResult<Value> {
31 let ScalarExpr::Column(column) = expression else {
32 return Err(ExecError::Other(
33 "set-operation sort key must be a column".into(),
34 ));
35 };
36 Ok(row.column(column).cloned().unwrap_or(Value::Null))
37 }
38}
39
40fn set_operation_types(left: &RowSchema, right: &RowSchema) -> ExecResult<Vec<Option<ColumnType>>> {
41 if left.len() != right.len() {
42 return Err(ExecError::Other(format!(
43 "set-operation inputs have different widths: {} and {}",
44 left.len(),
45 right.len()
46 )));
47 }
48 left.column_types()
49 .iter()
50 .zip(right.column_types())
51 .map(|(left, right)| match (left, right) {
52 (None, None) => Ok(None),
53 (Some(ty), None) | (None, Some(ty)) => Ok(Some(ty.clone())),
54 (Some(left), Some(right)) => uqa_execution_common_type(left, right).map(Some),
55 })
56 .collect()
57}
58
59fn uqa_execution_common_type(left: &ColumnType, right: &ColumnType) -> ExecResult<ColumnType> {
60 crate::common_type(left, right).map_err(ExecError::from)
61}
62
63fn coerce_set_value(
64 value: Value,
65 source_type: Option<&ColumnType>,
66 target_type: &ColumnType,
67) -> ExecResult<Value> {
68 let cast_target = match target_type {
69 ColumnType::Domain { base, .. } => base.as_ref(),
70 target => target,
71 };
72 let source_name = source_type.map(ColumnType::sql_name);
73 uqa_sql::expr::cast_value_from(&value, &cast_target.sql_name(), source_name.as_deref())
74 .map_err(ExecError::from)
75}
76
77struct AlignSchema<'a> {
78 child: Box<dyn PhysicalOperator + 'a>,
79 schema: RowSchema,
80 coercions: Vec<Option<ColumnType>>,
81}
82
83impl<'a> AlignSchema<'a> {
84 fn new(
85 child: Box<dyn PhysicalOperator + 'a>,
86 output: Vec<String>,
87 output_types: &[Option<ColumnType>],
88 ) -> ExecResult<Self> {
89 let source = child.schema().to_vec();
90 if source.len() != output.len() {
91 return Err(ExecError::Other(format!(
92 "set-operation inputs have different widths: {} and {}",
93 output.len(),
94 source.len()
95 )));
96 }
97 if output.len() != output_types.len() {
98 return Err(ExecError::Other(format!(
99 "set-operation output type width {} does not match input width {}",
100 output_types.len(),
101 output.len()
102 )));
103 }
104 let coercions = child
105 .row_schema()
106 .column_types()
107 .iter()
108 .zip(output_types)
109 .map(|(source, target)| {
110 target
111 .as_ref()
112 .filter(|target| source.as_ref() != Some(*target))
113 .cloned()
114 })
115 .collect();
116 let schema = RowSchema::with_types(output, output_types.to_vec());
117 Ok(Self {
118 child,
119 schema,
120 coercions,
121 })
122 }
123}
124
125impl PhysicalOperator for AlignSchema<'_> {
126 fn row_schema(&self) -> &RowSchema {
127 &self.schema
128 }
129
130 fn backward_scan_support(&self) -> BackwardScanSupport {
131 self.child.backward_scan_support()
132 }
133
134 fn open(&mut self) -> ExecResult<()> {
135 self.child.open()
136 }
137
138 fn next(&mut self) -> ExecResult<Option<Batch>> {
139 let Some(batch) = self.child.next()? else {
140 return Ok(None);
141 };
142 self.align_batch(batch).map(Some)
143 }
144
145 fn next_direction(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<Batch>> {
146 let Some(batch) = self.child.next_direction(direction)? else {
147 return Ok(None);
148 };
149 self.align_batch(batch).map(Some)
150 }
151
152 fn rewind(&mut self) -> ExecResult<()> {
153 self.child.rewind()
154 }
155
156 fn close(&mut self) -> ExecResult<()> {
157 self.child.close()
158 }
159}
160
161impl AlignSchema<'_> {
162 fn align_batch(&self, batch: Batch) -> ExecResult<Batch> {
163 let identity_layout = batch.schema.physical_width() == self.schema.physical_width()
164 && (0..batch.schema.len())
165 .all(|position| batch.schema.slot(position) == Some(position));
166 if self.coercions.iter().all(Option::is_none) && identity_layout {
167 let rows = batch
168 .rows
169 .into_iter()
170 .map(PhysicalRow::without_lock_origins)
171 .collect();
172 return Ok(Batch::from_physical_rows(self.schema.clone(), rows));
173 }
174 if self.coercions.iter().all(Option::is_none) {
175 let slots = (0..batch.schema.len())
176 .map(|position| {
177 batch.schema.slot(position).ok_or_else(|| {
178 ExecError::Other(format!(
179 "set-operation input column {position} has no physical slot"
180 ))
181 })
182 })
183 .collect::<ExecResult<Vec<_>>>()?;
184 let rows = batch
185 .rows
186 .into_iter()
187 .map(|row| row.project_slots(&slots).without_lock_origins())
188 .collect();
189 return Ok(Batch::from_physical_rows(self.schema.clone(), rows));
190 }
191 let mut rows = Vec::with_capacity(batch.rows.len());
192 for row in batch.rows {
193 let view = batch.schema.view(&row);
194 let values = self
195 .coercions
196 .iter()
197 .enumerate()
198 .map(|(position, target)| match target {
199 Some(target) => coerce_set_value(
200 view.value_at(position).cloned().unwrap_or(Value::Null),
201 batch.schema.column_type(position),
202 target,
203 )
204 .map(RowProjectionValue::Owned),
205 None => Ok(batch.schema.slot(position).map_or(
206 RowProjectionValue::Owned(Value::Null),
207 RowProjectionValue::InputSlot,
208 )),
209 })
210 .collect::<ExecResult<Vec<_>>>()?;
211 rows.push(row.project_with_values(values).without_lock_origins());
212 }
213 Ok(Batch::from_physical_rows(self.schema.clone(), rows))
214 }
215}
216
217struct RowGroup {
218 row: PhysicalRow,
219 count: usize,
220}
221
222struct RowCursor<'a> {
223 operator: Box<dyn PhysicalOperator + 'a>,
224 batch: std::vec::IntoIter<PhysicalRow>,
225 lookahead: Option<PhysicalRow>,
226 exhausted: bool,
227}
228
229impl<'a> RowCursor<'a> {
230 fn new(operator: Box<dyn PhysicalOperator + 'a>) -> Self {
231 Self {
232 operator,
233 batch: Vec::new().into_iter(),
234 lookahead: None,
235 exhausted: false,
236 }
237 }
238
239 fn open(&mut self) -> ExecResult<()> {
240 self.batch = Vec::new().into_iter();
241 self.lookahead = None;
242 self.exhausted = false;
243 self.operator.open()
244 }
245
246 fn next_row(&mut self) -> ExecResult<Option<PhysicalRow>> {
247 loop {
248 if let Some(row) = self.batch.next() {
249 return Ok(Some(row));
250 }
251 let Some(batch) = self.operator.next()? else {
252 self.exhausted = true;
253 return Ok(None);
254 };
255 self.batch = batch.rows.into_iter();
256 }
257 }
258
259 fn backward_scan_support(&self) -> BackwardScanSupport {
260 self.operator.backward_scan_support()
261 }
262
263 fn next_direction_row(
264 &mut self,
265 direction: PhysicalScanDirection,
266 ) -> ExecResult<Option<PhysicalRow>> {
267 if self.batch.len() != 0 || self.lookahead.is_some() {
268 return Err(ExecError::Other(
269 "set-operation input cannot mix batched and directional pulls".into(),
270 ));
271 }
272 let Some(batch) = self.operator.next_direction(direction)? else {
273 self.exhausted = true;
274 return Ok(None);
275 };
276 let mut rows = batch.rows.into_iter();
277 let row = rows.next();
278 if rows.next().is_some() {
279 return Err(ExecError::Other(
280 "directional set-operation input returned more than one row".into(),
281 ));
282 }
283 self.exhausted = row.is_none();
284 Ok(row)
285 }
286
287 fn rewind(&mut self) -> ExecResult<()> {
288 self.batch = Vec::new().into_iter();
289 self.lookahead = None;
290 self.exhausted = false;
291 self.operator.rewind()
292 }
293
294 fn take_group(
295 &mut self,
296 schema: &RowSchema,
297 enums: Option<&dyn uqa_sql::expr::enums::EnumLabelCatalog>,
298 ) -> ExecResult<Option<RowGroup>> {
299 let first = match self.lookahead.take() {
300 Some(row) => row,
301 None => match self.next_row()? {
302 Some(row) => row,
303 None => return Ok(None),
304 },
305 };
306 let mut count = 1_usize;
307 while let Some(row) = self.next_row()? {
308 if compare_rows(&first, &row, schema, enums)? == Ordering::Equal {
309 count = count
310 .checked_add(1)
311 .ok_or_else(|| ExecError::Other("set-operation group count overflow".into()))?;
312 } else {
313 self.lookahead = Some(row);
314 break;
315 }
316 }
317 Ok(Some(RowGroup { row: first, count }))
318 }
319
320 fn close(&mut self) -> ExecResult<()> {
321 self.batch = Vec::new().into_iter();
322 self.lookahead = None;
323 self.exhausted = true;
324 self.operator.close()
325 }
326}
327
328#[derive(Clone, Copy)]
329enum DirectionalAppendPosition {
330 BeforeFirst,
331 Left,
332 Right,
333 AfterLast,
334}
335
336fn compare_rows(
337 left: &PhysicalRow,
338 right: &PhysicalRow,
339 schema: &RowSchema,
340 enums: Option<&dyn uqa_sql::expr::enums::EnumLabelCatalog>,
341) -> ExecResult<Ordering> {
342 let left = schema.view(left);
343 let right = schema.view(right);
344 let null = Value::Null;
345 for position in 0..schema.len() {
346 let left = left.value_at(position).unwrap_or(&null);
347 let right = right.value_at(position).unwrap_or(&null);
348 let ordering = match (left, right) {
349 (Value::Null, Value::Null) => Ordering::Equal,
350 (Value::Null, _) => Ordering::Less,
351 (_, Value::Null) => Ordering::Greater,
352 _ => uqa_sql::expr::compare_selected_grouping_values_with_catalog(
353 left,
354 right,
355 schema.column_type(position),
356 &uqa_core::memory::ProductionControl::uncontrolled(),
357 enums,
358 )?,
359 };
360 if ordering != Ordering::Equal {
361 return Ok(ordering);
362 }
363 }
364 Ok(Ordering::Equal)
365}
366
367pub struct ExternalSetOperation<'a> {
373 left: RowCursor<'a>,
374 right: RowCursor<'a>,
375 evaluator: SharedExpressionEvaluator<'a>,
376 kind: SetOpKind,
377 all: bool,
378 schema: RowSchema,
379 left_group: Option<RowGroup>,
380 right_group: Option<RowGroup>,
381 pending_row: Option<PhysicalRow>,
382 pending_count: usize,
383 union_all_left_done: bool,
384 incremental_union_all: bool,
385 directional_position: DirectionalAppendPosition,
386}
387
388impl<'a> ExternalSetOperation<'a> {
389 pub fn new(
390 left: Box<dyn PhysicalOperator + 'a>,
391 right: Box<dyn PhysicalOperator + 'a>,
392 kind: SetOpKind,
393 all: bool,
394 work_mem_bytes: usize,
395 ) -> ExecResult<Self> {
396 let output_types = set_operation_types(left.row_schema(), right.row_schema())?;
397 Self::new_with_types(left, right, kind, all, output_types, work_mem_bytes)
398 }
399
400 pub fn new_with_evaluator(
401 left: Box<dyn PhysicalOperator + 'a>,
402 right: Box<dyn PhysicalOperator + 'a>,
403 kind: SetOpKind,
404 all: bool,
405 work_mem_bytes: usize,
406 evaluator: SharedExpressionEvaluator<'a>,
407 ) -> ExecResult<Self> {
408 let output_types = set_operation_types(left.row_schema(), right.row_schema())?;
409 Self::new_with_types_and_evaluator(
410 left,
411 right,
412 kind,
413 all,
414 output_types,
415 work_mem_bytes,
416 evaluator,
417 )
418 }
419
420 pub fn new_with_types(
421 left: Box<dyn PhysicalOperator + 'a>,
422 right: Box<dyn PhysicalOperator + 'a>,
423 kind: SetOpKind,
424 all: bool,
425 output_types: Vec<Option<ColumnType>>,
426 work_mem_bytes: usize,
427 ) -> ExecResult<Self> {
428 Self::new_with_types_and_evaluator(
429 left,
430 right,
431 kind,
432 all,
433 output_types,
434 work_mem_bytes,
435 Arc::new(ColumnEvaluator),
436 )
437 }
438
439 pub fn new_directional_with_types(
441 left: Box<dyn PhysicalOperator + 'a>,
442 right: Box<dyn PhysicalOperator + 'a>,
443 kind: SetOpKind,
444 all: bool,
445 output_types: Vec<Option<ColumnType>>,
446 work_mem_bytes: usize,
447 ) -> ExecResult<Self> {
448 let mut operation =
449 Self::new_with_types(left, right, kind, all, output_types, work_mem_bytes)?;
450 operation.incremental_union_all = true;
451 Ok(operation)
452 }
453
454 pub fn new_with_types_and_evaluator(
455 left: Box<dyn PhysicalOperator + 'a>,
456 right: Box<dyn PhysicalOperator + 'a>,
457 kind: SetOpKind,
458 all: bool,
459 output_types: Vec<Option<ColumnType>>,
460 work_mem_bytes: usize,
461 evaluator: SharedExpressionEvaluator<'a>,
462 ) -> ExecResult<Self> {
463 let output = left.schema().to_vec();
464 let left: Box<dyn PhysicalOperator + 'a> =
465 Box::new(AlignSchema::new(left, output.clone(), &output_types)?);
466 let right: Box<dyn PhysicalOperator + 'a> =
467 Box::new(AlignSchema::new(right, output.clone(), &output_types)?);
468 let (left, right) = if matches!((kind, all), (SetOpKind::Union, true)) {
469 (left, right)
470 } else {
471 let keys = output
472 .iter()
473 .map(|column| SortKey {
474 expr: ScalarExpr::Column(column.clone()),
475 descending: false,
476 nulls_first: Some(true),
477 })
478 .collect::<Vec<_>>();
479 let per_input = (work_mem_bytes / 2).max(1);
482 (
483 Box::new(
484 ExternalSort::new(left, keys.clone(), evaluator.clone(), None, per_input)
485 .with_equality_keys(),
486 ) as Box<dyn PhysicalOperator + 'a>,
487 Box::new(
488 ExternalSort::new(right, keys, Arc::clone(&evaluator), None, per_input)
489 .with_equality_keys(),
490 ) as Box<dyn PhysicalOperator + 'a>,
491 )
492 };
493 Ok(Self {
494 left: RowCursor::new(left),
495 right: RowCursor::new(right),
496 evaluator,
497 kind,
498 all,
499 schema: RowSchema::with_types(output, output_types),
500 left_group: None,
501 right_group: None,
502 pending_row: None,
503 pending_count: 0,
504 union_all_left_done: false,
505 incremental_union_all: false,
506 directional_position: DirectionalAppendPosition::BeforeFirst,
507 })
508 }
509
510 fn next_union_all(&mut self) -> ExecResult<Option<Batch>> {
511 let mut rows = Vec::with_capacity(DEFAULT_BATCH_SIZE);
512 while rows.len() < DEFAULT_BATCH_SIZE {
513 let next = if self.union_all_left_done {
514 self.right.next_row()?
515 } else if let Some(row) = self.left.next_row()? {
516 Some(row)
517 } else {
518 self.union_all_left_done = true;
519 self.right.next_row()?
520 };
521 let Some(row) = next else {
522 break;
523 };
524 rows.push(row.without_lock_origins());
525 }
526 if rows.is_empty() {
527 Ok(None)
528 } else {
529 Ok(Some(Batch::from_physical_rows(self.schema.clone(), rows)))
530 }
531 }
532
533 fn next_union_all_row(&mut self) -> ExecResult<Option<Batch>> {
534 let row = if self.union_all_left_done {
535 self.right.next_row()?
536 } else if let Some(row) = self.left.next_row()? {
537 Some(row)
538 } else {
539 self.union_all_left_done = true;
540 self.right.next_row()?
541 };
542 Ok(row.map(|row| self.directional_row_batch(row)))
543 }
544
545 fn directional_row_batch(&self, row: PhysicalRow) -> Batch {
546 Batch::from_physical_rows(self.schema.clone(), vec![row.without_lock_origins()])
547 }
548
549 fn next_union_all_direction(
550 &mut self,
551 direction: PhysicalScanDirection,
552 ) -> ExecResult<Option<Batch>> {
553 let mut position = match (self.directional_position, direction) {
554 (DirectionalAppendPosition::BeforeFirst, PhysicalScanDirection::Backward)
555 | (DirectionalAppendPosition::AfterLast, PhysicalScanDirection::Forward) => {
556 return Ok(None)
557 }
558 (DirectionalAppendPosition::BeforeFirst, PhysicalScanDirection::Forward)
559 | (DirectionalAppendPosition::Left, _) => DirectionalAppendPosition::Left,
560 (DirectionalAppendPosition::AfterLast, PhysicalScanDirection::Backward)
561 | (DirectionalAppendPosition::Right, _) => DirectionalAppendPosition::Right,
562 };
563 loop {
564 let row = match position {
565 DirectionalAppendPosition::Left => self.left.next_direction_row(direction)?,
566 DirectionalAppendPosition::Right => self.right.next_direction_row(direction)?,
567 DirectionalAppendPosition::BeforeFirst | DirectionalAppendPosition::AfterLast => {
568 unreachable!()
569 }
570 };
571 if let Some(row) = row {
572 self.directional_position = position;
573 return Ok(Some(self.directional_row_batch(row)));
574 }
575 position = match (position, direction) {
576 (DirectionalAppendPosition::Left, PhysicalScanDirection::Forward) => {
577 DirectionalAppendPosition::Right
578 }
579 (DirectionalAppendPosition::Right, PhysicalScanDirection::Backward) => {
580 DirectionalAppendPosition::Left
581 }
582 (DirectionalAppendPosition::Left, PhysicalScanDirection::Backward) => {
583 self.directional_position = DirectionalAppendPosition::BeforeFirst;
584 return Ok(None);
585 }
586 (DirectionalAppendPosition::Right, PhysicalScanDirection::Forward) => {
587 self.directional_position = DirectionalAppendPosition::AfterLast;
588 return Ok(None);
589 }
590 (
591 DirectionalAppendPosition::BeforeFirst | DirectionalAppendPosition::AfterLast,
592 _,
593 ) => unreachable!(),
594 };
595 }
596 }
597
598 fn load_groups(&mut self) -> ExecResult<()> {
599 if self.left_group.is_none() && !self.left.exhausted {
600 self.left_group = self
601 .left
602 .take_group(&self.schema, self.evaluator.enum_labels())?;
603 }
604 if self.right_group.is_none() && !self.right.exhausted {
605 self.right_group = self
606 .right
607 .take_group(&self.schema, self.evaluator.enum_labels())?;
608 }
609 Ok(())
610 }
611
612 fn take_left_group(&mut self) -> ExecResult<RowGroup> {
613 self.left_group
614 .take()
615 .ok_or_else(|| ExecError::Other("set-operation selected a missing left group".into()))
616 }
617
618 fn take_right_group(&mut self) -> ExecResult<RowGroup> {
619 self.right_group
620 .take()
621 .ok_or_else(|| ExecError::Other("set-operation selected a missing right group".into()))
622 }
623
624 fn choose_group(&mut self) -> ExecResult<Option<(PhysicalRow, usize)>> {
625 self.load_groups()?;
626 let ordering = match (&self.left_group, &self.right_group) {
627 (Some(left), Some(right)) => Some(compare_rows(
628 &left.row,
629 &right.row,
630 &self.schema,
631 self.evaluator.enum_labels(),
632 )?),
633 (Some(_), None) => Some(Ordering::Less),
634 (None, Some(_)) => Some(Ordering::Greater),
635 (None, None) => None,
636 };
637 let Some(ordering) = ordering else {
638 return Ok(None);
639 };
640
641 let selected = match (self.kind, ordering) {
642 (SetOpKind::Union, Ordering::Less) => {
643 let group = self.take_left_group()?;
644 Some((group.row, 1))
645 }
646 (SetOpKind::Union, Ordering::Greater) => {
647 let group = self.take_right_group()?;
648 Some((group.row, 1))
649 }
650 (SetOpKind::Union, Ordering::Equal) => {
651 let group = self.take_left_group()?;
652 self.right_group = None;
653 Some((group.row, 1))
654 }
655 (SetOpKind::Intersect, Ordering::Less) => {
656 self.left_group = None;
657 None
658 }
659 (SetOpKind::Intersect | SetOpKind::Except, Ordering::Greater) => {
660 self.right_group = None;
661 None
662 }
663 (SetOpKind::Intersect, Ordering::Equal) => {
664 let left = self.take_left_group()?;
665 let right = self.take_right_group()?;
666 Some((
667 left.row,
668 if self.all {
669 left.count.min(right.count)
670 } else {
671 1
672 },
673 ))
674 }
675 (SetOpKind::Except, Ordering::Less) => {
676 let left = self.take_left_group()?;
677 Some((left.row, if self.all { left.count } else { 1 }))
678 }
679 (SetOpKind::Except, Ordering::Equal) => {
680 let left = self.take_left_group()?;
681 let right = self.take_right_group()?;
682 let count = if self.all {
683 left.count.saturating_sub(right.count)
684 } else {
685 0
686 };
687 Some((left.row, count))
688 }
689 };
690 Ok(selected.filter(|(_, count)| *count > 0))
691 }
692}
693
694impl PhysicalOperator for ExternalSetOperation<'_> {
695 fn row_schema(&self) -> &RowSchema {
696 &self.schema
697 }
698
699 fn backward_scan_support(&self) -> BackwardScanSupport {
700 if matches!((self.kind, self.all), (SetOpKind::Union, true))
701 && self.left.backward_scan_support() == BackwardScanSupport::Native
702 && self.right.backward_scan_support() == BackwardScanSupport::Native
703 {
704 BackwardScanSupport::Native
705 } else {
706 BackwardScanSupport::Unsupported
707 }
708 }
709
710 fn open(&mut self) -> ExecResult<()> {
711 self.left_group = None;
712 self.right_group = None;
713 self.pending_row = None;
714 self.pending_count = 0;
715 self.union_all_left_done = false;
716 self.directional_position = DirectionalAppendPosition::BeforeFirst;
717 self.left.open()?;
718 self.right.open()
719 }
720
721 fn next(&mut self) -> ExecResult<Option<Batch>> {
722 if matches!((self.kind, self.all), (SetOpKind::Union, true)) {
723 return if self.incremental_union_all {
724 self.next_union_all_row()
725 } else {
726 self.next_union_all()
727 };
728 }
729 let mut rows = Vec::with_capacity(DEFAULT_BATCH_SIZE);
730 while rows.len() < DEFAULT_BATCH_SIZE {
731 if self.pending_count > 0 {
732 let row = self.pending_row.as_ref().ok_or_else(|| {
733 ExecError::Other(
734 "set-operation has pending multiplicity without a pending row".into(),
735 )
736 })?;
737 rows.push(row.clone());
738 self.pending_count -= 1;
739 if self.pending_count == 0 {
740 self.pending_row = None;
741 }
742 continue;
743 }
744 match self.choose_group()? {
745 Some((row, count)) => {
746 self.pending_row = Some(row.without_lock_origins());
747 self.pending_count = count;
748 }
749 None if self.left.exhausted && self.right.exhausted => break,
750 None => {}
751 }
752 }
753 if rows.is_empty() {
754 Ok(None)
755 } else {
756 Ok(Some(Batch::from_physical_rows(self.schema.clone(), rows)))
757 }
758 }
759
760 fn next_direction(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<Batch>> {
761 if self.backward_scan_support() == BackwardScanSupport::Native {
762 return self.next_union_all_direction(direction);
763 }
764 if direction == PhysicalScanDirection::Forward {
765 return if matches!((self.kind, self.all), (SetOpKind::Union, true)) {
766 self.next_union_all_row()
767 } else {
768 self.next()
769 };
770 }
771 Err(ExecError::Other(
772 "set operation does not support backwards scanning".into(),
773 ))
774 }
775
776 fn rewind(&mut self) -> ExecResult<()> {
777 if self.backward_scan_support() != BackwardScanSupport::Native {
778 return Err(ExecError::Other(
779 "set operation does not support rewind".into(),
780 ));
781 }
782 self.left.rewind()?;
783 self.right.rewind()?;
784 self.directional_position = DirectionalAppendPosition::BeforeFirst;
785 Ok(())
786 }
787
788 fn close(&mut self) -> ExecResult<()> {
789 self.left_group = None;
790 self.right_group = None;
791 self.pending_row = None;
792 self.pending_count = 0;
793 self.directional_position = DirectionalAppendPosition::BeforeFirst;
794 let left = self.left.close();
795 let right = self.right.close();
796 crate::physical::with_cleanup(left, right, "close right set-operation input")
797 }
798}
799
800#[cfg(test)]
801mod tests {
802 mod enums;
803 mod ranges;
804 use super::*;
805 use crate::physical::run_to_rows;
806 use crate::scan::TableScan;
807 use crate::RowSchemaExecution;
808
809 fn row(value: i64) -> ResultRow {
810 [("v".into(), Value::Int(value))].into_iter().collect()
811 }
812
813 fn execute(kind: SetOpKind, all: bool, left: &[i64], right: &[i64]) -> Vec<i64> {
814 let left = TableScan::from_rows(vec!["v".into()], left.iter().copied().map(row).collect());
815 let right = TableScan::from_rows(
816 vec!["other".into()],
817 right
818 .iter()
819 .copied()
820 .map(|value| [("other".into(), Value::Int(value))].into_iter().collect())
821 .collect(),
822 );
823 let mut set =
824 ExternalSetOperation::new(Box::new(left), Box::new(right), kind, all, 1).unwrap();
825 run_to_rows(&mut set)
826 .unwrap()
827 .1
828 .into_iter()
829 .map(|row| match row.get("v") {
830 Some(Value::Int(value)) => *value,
831 value => panic!("unexpected set value: {value:?}"),
832 })
833 .collect()
834 }
835
836 #[test]
837 fn external_set_semantics_include_bag_multiplicity() {
838 assert_eq!(
839 execute(SetOpKind::Union, false, &[2, 1, 1], &[3, 2]),
840 vec![1, 2, 3]
841 );
842 assert_eq!(
843 execute(SetOpKind::Union, true, &[2, 1, 1], &[3, 2]),
844 vec![2, 1, 1, 3, 2]
845 );
846 assert_eq!(
847 execute(SetOpKind::Intersect, true, &[1, 1, 1, 2], &[1, 1, 3]),
848 vec![1, 1]
849 );
850 assert_eq!(
851 execute(SetOpKind::Except, true, &[1, 1, 1, 2], &[1, 1, 3]),
852 vec![1, 2]
853 );
854 assert_eq!(
855 execute(SetOpKind::Except, false, &[1, 1, 2], &[1, 3]),
856 vec![2]
857 );
858 }
859
860 #[test]
861 fn set_inputs_compact_schema_only_projections_before_alignment() {
862 let left = TableScan::from_rows(
863 vec!["v".into(), "hidden".into()],
864 vec![[
865 ("v".into(), Value::Int(1)),
866 ("hidden".into(), Value::Int(99)),
867 ]
868 .into_iter()
869 .collect()],
870 );
871 let left: Box<dyn PhysicalOperator> = Box::new(crate::ColumnSelection::with_positions(
872 Box::new(left),
873 vec![("v".into(), 0)],
874 ));
875 let right = TableScan::from_rows(vec!["v".into()], vec![row(2)]);
876 let mut set =
877 ExternalSetOperation::new(left, Box::new(right), SetOpKind::Union, true, 1).unwrap();
878 let rows = run_to_rows(&mut set).unwrap().1;
879 assert_eq!(rows, vec![row(1), row(2)]);
880 }
881
882 fn directional_value(batch: Option<Batch>) -> Option<i64> {
883 let batch = batch?;
884 let row = batch.rows.first()?;
885 match batch.schema.view(row).value_at(0) {
886 Some(Value::Int(value)) => Some(*value),
887 value => panic!("unexpected directional set value: {value:?}"),
888 }
889 }
890
891 #[test]
892 fn union_all_scans_children_in_reverse_order_across_the_boundary() {
893 let left: Box<dyn PhysicalOperator> = Box::new(crate::ScrollMaterialize::new(Box::new(
894 TableScan::from_rows(vec!["v".into()], vec![row(1), row(2)]),
895 )));
896 let right: Box<dyn PhysicalOperator> = Box::new(crate::ScrollMaterialize::new(Box::new(
897 TableScan::from_rows(vec!["v".into()], vec![row(3), row(4)]),
898 )));
899 let mut set = ExternalSetOperation::new(left, right, SetOpKind::Union, true, 1).unwrap();
900 assert_eq!(set.backward_scan_support(), BackwardScanSupport::Native);
901 set.open().unwrap();
902 for (direction, expected) in [
903 (PhysicalScanDirection::Forward, 1),
904 (PhysicalScanDirection::Forward, 2),
905 (PhysicalScanDirection::Forward, 3),
906 (PhysicalScanDirection::Backward, 2),
907 (PhysicalScanDirection::Forward, 3),
908 ] {
909 assert_eq!(
910 directional_value(set.next_direction(direction).unwrap()),
911 Some(expected)
912 );
913 }
914 set.rewind().unwrap();
915 assert_eq!(
916 directional_value(set.next_direction(PhysicalScanDirection::Forward).unwrap()),
917 Some(1)
918 );
919 set.close().unwrap();
920 }
921
922 #[test]
923 fn directional_union_all_materialization_pulls_one_row_at_a_time() {
924 let left: Box<dyn PhysicalOperator> =
925 Box::new(TableScan::from_rows(vec!["v".into()], vec![row(1), row(2)]));
926 let right: Box<dyn PhysicalOperator> =
927 Box::new(TableScan::from_rows(vec!["v".into()], vec![row(3)]));
928 let mut set = ExternalSetOperation::new_directional_with_types(
929 left,
930 right,
931 SetOpKind::Union,
932 true,
933 vec![None],
934 1,
935 )
936 .unwrap();
937 assert_eq!(
938 set.backward_scan_support(),
939 BackwardScanSupport::Unsupported
940 );
941 set.open().unwrap();
942 for expected in [1, 2, 3] {
943 let batch = set.next().unwrap().unwrap();
944 assert_eq!(batch.rows.len(), 1);
945 assert_eq!(directional_value(Some(batch)), Some(expected));
946 }
947 assert!(set.next().unwrap().is_none());
948 set.close().unwrap();
949 }
950}