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_grouping_values_with_enum_catalog(
353 left,
354 right,
355 &uqa_core::memory::ProductionControl::uncontrolled(),
356 enums,
357 )?,
358 };
359 if ordering != Ordering::Equal {
360 return Ok(ordering);
361 }
362 }
363 Ok(Ordering::Equal)
364}
365
366pub struct ExternalSetOperation<'a> {
372 left: RowCursor<'a>,
373 right: RowCursor<'a>,
374 evaluator: SharedExpressionEvaluator<'a>,
375 kind: SetOpKind,
376 all: bool,
377 schema: RowSchema,
378 left_group: Option<RowGroup>,
379 right_group: Option<RowGroup>,
380 pending_row: Option<PhysicalRow>,
381 pending_count: usize,
382 union_all_left_done: bool,
383 incremental_union_all: bool,
384 directional_position: DirectionalAppendPosition,
385}
386
387impl<'a> ExternalSetOperation<'a> {
388 pub fn new(
389 left: Box<dyn PhysicalOperator + 'a>,
390 right: Box<dyn PhysicalOperator + 'a>,
391 kind: SetOpKind,
392 all: bool,
393 work_mem_bytes: usize,
394 ) -> ExecResult<Self> {
395 let output_types = set_operation_types(left.row_schema(), right.row_schema())?;
396 Self::new_with_types(left, right, kind, all, output_types, work_mem_bytes)
397 }
398
399 pub fn new_with_evaluator(
400 left: Box<dyn PhysicalOperator + 'a>,
401 right: Box<dyn PhysicalOperator + 'a>,
402 kind: SetOpKind,
403 all: bool,
404 work_mem_bytes: usize,
405 evaluator: SharedExpressionEvaluator<'a>,
406 ) -> ExecResult<Self> {
407 let output_types = set_operation_types(left.row_schema(), right.row_schema())?;
408 Self::new_with_types_and_evaluator(
409 left,
410 right,
411 kind,
412 all,
413 output_types,
414 work_mem_bytes,
415 evaluator,
416 )
417 }
418
419 pub fn new_with_types(
420 left: Box<dyn PhysicalOperator + 'a>,
421 right: Box<dyn PhysicalOperator + 'a>,
422 kind: SetOpKind,
423 all: bool,
424 output_types: Vec<Option<ColumnType>>,
425 work_mem_bytes: usize,
426 ) -> ExecResult<Self> {
427 Self::new_with_types_and_evaluator(
428 left,
429 right,
430 kind,
431 all,
432 output_types,
433 work_mem_bytes,
434 Arc::new(ColumnEvaluator),
435 )
436 }
437
438 pub fn new_directional_with_types(
440 left: Box<dyn PhysicalOperator + 'a>,
441 right: Box<dyn PhysicalOperator + 'a>,
442 kind: SetOpKind,
443 all: bool,
444 output_types: Vec<Option<ColumnType>>,
445 work_mem_bytes: usize,
446 ) -> ExecResult<Self> {
447 let mut operation =
448 Self::new_with_types(left, right, kind, all, output_types, work_mem_bytes)?;
449 operation.incremental_union_all = true;
450 Ok(operation)
451 }
452
453 pub fn new_with_types_and_evaluator(
454 left: Box<dyn PhysicalOperator + 'a>,
455 right: Box<dyn PhysicalOperator + 'a>,
456 kind: SetOpKind,
457 all: bool,
458 output_types: Vec<Option<ColumnType>>,
459 work_mem_bytes: usize,
460 evaluator: SharedExpressionEvaluator<'a>,
461 ) -> ExecResult<Self> {
462 let output = left.schema().to_vec();
463 let left: Box<dyn PhysicalOperator + 'a> =
464 Box::new(AlignSchema::new(left, output.clone(), &output_types)?);
465 let right: Box<dyn PhysicalOperator + 'a> =
466 Box::new(AlignSchema::new(right, output.clone(), &output_types)?);
467 let (left, right) = if matches!((kind, all), (SetOpKind::Union, true)) {
468 (left, right)
469 } else {
470 let keys = output
471 .iter()
472 .map(|column| SortKey {
473 expr: ScalarExpr::Column(column.clone()),
474 descending: false,
475 nulls_first: Some(true),
476 })
477 .collect::<Vec<_>>();
478 let per_input = (work_mem_bytes / 2).max(1);
481 (
482 Box::new(
483 ExternalSort::new(left, keys.clone(), evaluator.clone(), None, per_input)
484 .with_equality_keys(),
485 ) as Box<dyn PhysicalOperator + 'a>,
486 Box::new(
487 ExternalSort::new(right, keys, Arc::clone(&evaluator), None, per_input)
488 .with_equality_keys(),
489 ) as Box<dyn PhysicalOperator + 'a>,
490 )
491 };
492 Ok(Self {
493 left: RowCursor::new(left),
494 right: RowCursor::new(right),
495 evaluator,
496 kind,
497 all,
498 schema: RowSchema::with_types(output, output_types),
499 left_group: None,
500 right_group: None,
501 pending_row: None,
502 pending_count: 0,
503 union_all_left_done: false,
504 incremental_union_all: false,
505 directional_position: DirectionalAppendPosition::BeforeFirst,
506 })
507 }
508
509 fn next_union_all(&mut self) -> ExecResult<Option<Batch>> {
510 let mut rows = Vec::with_capacity(DEFAULT_BATCH_SIZE);
511 while rows.len() < DEFAULT_BATCH_SIZE {
512 let next = if self.union_all_left_done {
513 self.right.next_row()?
514 } else if let Some(row) = self.left.next_row()? {
515 Some(row)
516 } else {
517 self.union_all_left_done = true;
518 self.right.next_row()?
519 };
520 let Some(row) = next else {
521 break;
522 };
523 rows.push(row.without_lock_origins());
524 }
525 if rows.is_empty() {
526 Ok(None)
527 } else {
528 Ok(Some(Batch::from_physical_rows(self.schema.clone(), rows)))
529 }
530 }
531
532 fn next_union_all_row(&mut self) -> ExecResult<Option<Batch>> {
533 let row = if self.union_all_left_done {
534 self.right.next_row()?
535 } else if let Some(row) = self.left.next_row()? {
536 Some(row)
537 } else {
538 self.union_all_left_done = true;
539 self.right.next_row()?
540 };
541 Ok(row.map(|row| self.directional_row_batch(row)))
542 }
543
544 fn directional_row_batch(&self, row: PhysicalRow) -> Batch {
545 Batch::from_physical_rows(self.schema.clone(), vec![row.without_lock_origins()])
546 }
547
548 fn next_union_all_direction(
549 &mut self,
550 direction: PhysicalScanDirection,
551 ) -> ExecResult<Option<Batch>> {
552 let mut position = match (self.directional_position, direction) {
553 (DirectionalAppendPosition::BeforeFirst, PhysicalScanDirection::Backward)
554 | (DirectionalAppendPosition::AfterLast, PhysicalScanDirection::Forward) => {
555 return Ok(None)
556 }
557 (DirectionalAppendPosition::BeforeFirst, PhysicalScanDirection::Forward)
558 | (DirectionalAppendPosition::Left, _) => DirectionalAppendPosition::Left,
559 (DirectionalAppendPosition::AfterLast, PhysicalScanDirection::Backward)
560 | (DirectionalAppendPosition::Right, _) => DirectionalAppendPosition::Right,
561 };
562 loop {
563 let row = match position {
564 DirectionalAppendPosition::Left => self.left.next_direction_row(direction)?,
565 DirectionalAppendPosition::Right => self.right.next_direction_row(direction)?,
566 DirectionalAppendPosition::BeforeFirst | DirectionalAppendPosition::AfterLast => {
567 unreachable!()
568 }
569 };
570 if let Some(row) = row {
571 self.directional_position = position;
572 return Ok(Some(self.directional_row_batch(row)));
573 }
574 position = match (position, direction) {
575 (DirectionalAppendPosition::Left, PhysicalScanDirection::Forward) => {
576 DirectionalAppendPosition::Right
577 }
578 (DirectionalAppendPosition::Right, PhysicalScanDirection::Backward) => {
579 DirectionalAppendPosition::Left
580 }
581 (DirectionalAppendPosition::Left, PhysicalScanDirection::Backward) => {
582 self.directional_position = DirectionalAppendPosition::BeforeFirst;
583 return Ok(None);
584 }
585 (DirectionalAppendPosition::Right, PhysicalScanDirection::Forward) => {
586 self.directional_position = DirectionalAppendPosition::AfterLast;
587 return Ok(None);
588 }
589 (
590 DirectionalAppendPosition::BeforeFirst | DirectionalAppendPosition::AfterLast,
591 _,
592 ) => unreachable!(),
593 };
594 }
595 }
596
597 fn load_groups(&mut self) -> ExecResult<()> {
598 if self.left_group.is_none() && !self.left.exhausted {
599 self.left_group = self
600 .left
601 .take_group(&self.schema, self.evaluator.enum_labels())?;
602 }
603 if self.right_group.is_none() && !self.right.exhausted {
604 self.right_group = self
605 .right
606 .take_group(&self.schema, self.evaluator.enum_labels())?;
607 }
608 Ok(())
609 }
610
611 fn take_left_group(&mut self) -> ExecResult<RowGroup> {
612 self.left_group
613 .take()
614 .ok_or_else(|| ExecError::Other("set-operation selected a missing left group".into()))
615 }
616
617 fn take_right_group(&mut self) -> ExecResult<RowGroup> {
618 self.right_group
619 .take()
620 .ok_or_else(|| ExecError::Other("set-operation selected a missing right group".into()))
621 }
622
623 fn choose_group(&mut self) -> ExecResult<Option<(PhysicalRow, usize)>> {
624 self.load_groups()?;
625 let ordering = match (&self.left_group, &self.right_group) {
626 (Some(left), Some(right)) => Some(compare_rows(
627 &left.row,
628 &right.row,
629 &self.schema,
630 self.evaluator.enum_labels(),
631 )?),
632 (Some(_), None) => Some(Ordering::Less),
633 (None, Some(_)) => Some(Ordering::Greater),
634 (None, None) => None,
635 };
636 let Some(ordering) = ordering else {
637 return Ok(None);
638 };
639
640 let selected = match (self.kind, ordering) {
641 (SetOpKind::Union, Ordering::Less) => {
642 let group = self.take_left_group()?;
643 Some((group.row, 1))
644 }
645 (SetOpKind::Union, Ordering::Greater) => {
646 let group = self.take_right_group()?;
647 Some((group.row, 1))
648 }
649 (SetOpKind::Union, Ordering::Equal) => {
650 let group = self.take_left_group()?;
651 self.right_group = None;
652 Some((group.row, 1))
653 }
654 (SetOpKind::Intersect, Ordering::Less) => {
655 self.left_group = None;
656 None
657 }
658 (SetOpKind::Intersect | SetOpKind::Except, Ordering::Greater) => {
659 self.right_group = None;
660 None
661 }
662 (SetOpKind::Intersect, Ordering::Equal) => {
663 let left = self.take_left_group()?;
664 let right = self.take_right_group()?;
665 Some((
666 left.row,
667 if self.all {
668 left.count.min(right.count)
669 } else {
670 1
671 },
672 ))
673 }
674 (SetOpKind::Except, Ordering::Less) => {
675 let left = self.take_left_group()?;
676 Some((left.row, if self.all { left.count } else { 1 }))
677 }
678 (SetOpKind::Except, Ordering::Equal) => {
679 let left = self.take_left_group()?;
680 let right = self.take_right_group()?;
681 let count = if self.all {
682 left.count.saturating_sub(right.count)
683 } else {
684 0
685 };
686 Some((left.row, count))
687 }
688 };
689 Ok(selected.filter(|(_, count)| *count > 0))
690 }
691}
692
693impl PhysicalOperator for ExternalSetOperation<'_> {
694 fn row_schema(&self) -> &RowSchema {
695 &self.schema
696 }
697
698 fn backward_scan_support(&self) -> BackwardScanSupport {
699 if matches!((self.kind, self.all), (SetOpKind::Union, true))
700 && self.left.backward_scan_support() == BackwardScanSupport::Native
701 && self.right.backward_scan_support() == BackwardScanSupport::Native
702 {
703 BackwardScanSupport::Native
704 } else {
705 BackwardScanSupport::Unsupported
706 }
707 }
708
709 fn open(&mut self) -> ExecResult<()> {
710 self.left_group = None;
711 self.right_group = None;
712 self.pending_row = None;
713 self.pending_count = 0;
714 self.union_all_left_done = false;
715 self.directional_position = DirectionalAppendPosition::BeforeFirst;
716 self.left.open()?;
717 self.right.open()
718 }
719
720 fn next(&mut self) -> ExecResult<Option<Batch>> {
721 if matches!((self.kind, self.all), (SetOpKind::Union, true)) {
722 return if self.incremental_union_all {
723 self.next_union_all_row()
724 } else {
725 self.next_union_all()
726 };
727 }
728 let mut rows = Vec::with_capacity(DEFAULT_BATCH_SIZE);
729 while rows.len() < DEFAULT_BATCH_SIZE {
730 if self.pending_count > 0 {
731 let row = self.pending_row.as_ref().ok_or_else(|| {
732 ExecError::Other(
733 "set-operation has pending multiplicity without a pending row".into(),
734 )
735 })?;
736 rows.push(row.clone());
737 self.pending_count -= 1;
738 if self.pending_count == 0 {
739 self.pending_row = None;
740 }
741 continue;
742 }
743 match self.choose_group()? {
744 Some((row, count)) => {
745 self.pending_row = Some(row.without_lock_origins());
746 self.pending_count = count;
747 }
748 None if self.left.exhausted && self.right.exhausted => break,
749 None => {}
750 }
751 }
752 if rows.is_empty() {
753 Ok(None)
754 } else {
755 Ok(Some(Batch::from_physical_rows(self.schema.clone(), rows)))
756 }
757 }
758
759 fn next_direction(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<Batch>> {
760 if self.backward_scan_support() == BackwardScanSupport::Native {
761 return self.next_union_all_direction(direction);
762 }
763 if direction == PhysicalScanDirection::Forward {
764 return if matches!((self.kind, self.all), (SetOpKind::Union, true)) {
765 self.next_union_all_row()
766 } else {
767 self.next()
768 };
769 }
770 Err(ExecError::Other(
771 "set operation does not support backwards scanning".into(),
772 ))
773 }
774
775 fn rewind(&mut self) -> ExecResult<()> {
776 if self.backward_scan_support() != BackwardScanSupport::Native {
777 return Err(ExecError::Other(
778 "set operation does not support rewind".into(),
779 ));
780 }
781 self.left.rewind()?;
782 self.right.rewind()?;
783 self.directional_position = DirectionalAppendPosition::BeforeFirst;
784 Ok(())
785 }
786
787 fn close(&mut self) -> ExecResult<()> {
788 self.left_group = None;
789 self.right_group = None;
790 self.pending_row = None;
791 self.pending_count = 0;
792 self.directional_position = DirectionalAppendPosition::BeforeFirst;
793 let left = self.left.close();
794 let right = self.right.close();
795 crate::physical::with_cleanup(left, right, "close right set-operation input")
796 }
797}
798
799#[cfg(test)]
800mod tests {
801 mod enums;
802 use super::*;
803 use crate::physical::run_to_rows;
804 use crate::scan::TableScan;
805 use crate::RowSchemaExecution;
806
807 fn row(value: i64) -> ResultRow {
808 [("v".into(), Value::Int(value))].into_iter().collect()
809 }
810
811 fn execute(kind: SetOpKind, all: bool, left: &[i64], right: &[i64]) -> Vec<i64> {
812 let left = TableScan::from_rows(vec!["v".into()], left.iter().copied().map(row).collect());
813 let right = TableScan::from_rows(
814 vec!["other".into()],
815 right
816 .iter()
817 .copied()
818 .map(|value| [("other".into(), Value::Int(value))].into_iter().collect())
819 .collect(),
820 );
821 let mut set =
822 ExternalSetOperation::new(Box::new(left), Box::new(right), kind, all, 1).unwrap();
823 run_to_rows(&mut set)
824 .unwrap()
825 .1
826 .into_iter()
827 .map(|row| match row.get("v") {
828 Some(Value::Int(value)) => *value,
829 value => panic!("unexpected set value: {value:?}"),
830 })
831 .collect()
832 }
833
834 #[test]
835 fn external_set_semantics_include_bag_multiplicity() {
836 assert_eq!(
837 execute(SetOpKind::Union, false, &[2, 1, 1], &[3, 2]),
838 vec![1, 2, 3]
839 );
840 assert_eq!(
841 execute(SetOpKind::Union, true, &[2, 1, 1], &[3, 2]),
842 vec![2, 1, 1, 3, 2]
843 );
844 assert_eq!(
845 execute(SetOpKind::Intersect, true, &[1, 1, 1, 2], &[1, 1, 3]),
846 vec![1, 1]
847 );
848 assert_eq!(
849 execute(SetOpKind::Except, true, &[1, 1, 1, 2], &[1, 1, 3]),
850 vec![1, 2]
851 );
852 assert_eq!(
853 execute(SetOpKind::Except, false, &[1, 1, 2], &[1, 3]),
854 vec![2]
855 );
856 }
857
858 #[test]
859 fn set_inputs_compact_schema_only_projections_before_alignment() {
860 let left = TableScan::from_rows(
861 vec!["v".into(), "hidden".into()],
862 vec![[
863 ("v".into(), Value::Int(1)),
864 ("hidden".into(), Value::Int(99)),
865 ]
866 .into_iter()
867 .collect()],
868 );
869 let left: Box<dyn PhysicalOperator> = Box::new(crate::ColumnSelection::with_positions(
870 Box::new(left),
871 vec![("v".into(), 0)],
872 ));
873 let right = TableScan::from_rows(vec!["v".into()], vec![row(2)]);
874 let mut set =
875 ExternalSetOperation::new(left, Box::new(right), SetOpKind::Union, true, 1).unwrap();
876 let rows = run_to_rows(&mut set).unwrap().1;
877 assert_eq!(rows, vec![row(1), row(2)]);
878 }
879
880 fn directional_value(batch: Option<Batch>) -> Option<i64> {
881 let batch = batch?;
882 let row = batch.rows.first()?;
883 match batch.schema.view(row).value_at(0) {
884 Some(Value::Int(value)) => Some(*value),
885 value => panic!("unexpected directional set value: {value:?}"),
886 }
887 }
888
889 #[test]
890 fn union_all_scans_children_in_reverse_order_across_the_boundary() {
891 let left: Box<dyn PhysicalOperator> = Box::new(crate::ScrollMaterialize::new(Box::new(
892 TableScan::from_rows(vec!["v".into()], vec![row(1), row(2)]),
893 )));
894 let right: Box<dyn PhysicalOperator> = Box::new(crate::ScrollMaterialize::new(Box::new(
895 TableScan::from_rows(vec!["v".into()], vec![row(3), row(4)]),
896 )));
897 let mut set = ExternalSetOperation::new(left, right, SetOpKind::Union, true, 1).unwrap();
898 assert_eq!(set.backward_scan_support(), BackwardScanSupport::Native);
899 set.open().unwrap();
900 for (direction, expected) in [
901 (PhysicalScanDirection::Forward, 1),
902 (PhysicalScanDirection::Forward, 2),
903 (PhysicalScanDirection::Forward, 3),
904 (PhysicalScanDirection::Backward, 2),
905 (PhysicalScanDirection::Forward, 3),
906 ] {
907 assert_eq!(
908 directional_value(set.next_direction(direction).unwrap()),
909 Some(expected)
910 );
911 }
912 set.rewind().unwrap();
913 assert_eq!(
914 directional_value(set.next_direction(PhysicalScanDirection::Forward).unwrap()),
915 Some(1)
916 );
917 set.close().unwrap();
918 }
919
920 #[test]
921 fn directional_union_all_materialization_pulls_one_row_at_a_time() {
922 let left: Box<dyn PhysicalOperator> =
923 Box::new(TableScan::from_rows(vec!["v".into()], vec![row(1), row(2)]));
924 let right: Box<dyn PhysicalOperator> =
925 Box::new(TableScan::from_rows(vec!["v".into()], vec![row(3)]));
926 let mut set = ExternalSetOperation::new_directional_with_types(
927 left,
928 right,
929 SetOpKind::Union,
930 true,
931 vec![None],
932 1,
933 )
934 .unwrap();
935 assert_eq!(
936 set.backward_scan_support(),
937 BackwardScanSupport::Unsupported
938 );
939 set.open().unwrap();
940 for expected in [1, 2, 3] {
941 let batch = set.next().unwrap().unwrap();
942 assert_eq!(batch.rows.len(), 1);
943 assert_eq!(directional_value(Some(batch)), Some(expected));
944 }
945 assert!(set.next().unwrap().is_none());
946 set.close().unwrap();
947 }
948}