Skip to main content

uqa_execution/
set_operation.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Byte-bounded physical SQL set operations.
8
9use 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
366/// `UNION` / `INTERSECT` / `EXCEPT` physical operator.
367///
368/// `UNION ALL` streams its children without sorting. Other forms sort both
369/// inputs through byte-bounded external runs and merge adjacent multiplicity
370/// counts, avoiding whole-input materialisation and quadratic row scans.
371pub 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    /// Construct a set operation whose ordinary forward pulls remain one-row incremental when a scroll materialization boundary wraps the complete operation.
439    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            // Both merge inputs are live concurrently. Split the configured
479            // budget so their encoded in-memory runs cannot each claim it.
480            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}