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    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    /// Construct a set operation whose ordinary forward pulls remain one-row incremental when a scroll materialization boundary wraps the complete operation.
441    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            // Both merge inputs are live concurrently. Split the configured
481            // budget so their encoded in-memory runs cannot each claim it.
482            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}