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_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
367/// `UNION` / `INTERSECT` / `EXCEPT` physical operator.
368///
369/// `UNION ALL` streams its children without sorting. Other forms sort both
370/// inputs through byte-bounded external runs and merge adjacent multiplicity
371/// counts, avoiding whole-input materialisation and quadratic row scans.
372pub 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    /// Construct a set operation whose ordinary forward pulls remain one-row incremental when a scroll materialization boundary wraps the complete operation.
440    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            // Both merge inputs are live concurrently. Split the configured
480            // budget so their encoded in-memory runs cannot each claim it.
481            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}