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