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;
11
12use uqa_core::Value;
13use uqa_sql::ast::{ColumnType, SetOpKind};
14use uqa_sql::expr::RowLookup;
15
16#[cfg(test)]
17use uqa_sql::ResultRow;
18
19use crate::batch::DEFAULT_BATCH_SIZE;
20use crate::{
21    BackwardScanSupport, Batch, ExecError, ExecResult, ExpressionEvaluator, PhysicalOperator,
22    PhysicalRow, PhysicalScanDirection, RowProjectionValue, RowSchema, ScalarExpr,
23    SharedExpressionEvaluator,
24};
25
26mod construction;
27
28struct ColumnEvaluator;
29
30impl ExpressionEvaluator for ColumnEvaluator {
31    fn evaluate(&self, expression: &ScalarExpr, row: &dyn RowLookup) -> ExecResult<Value> {
32        let ScalarExpr::Column(column) = expression else {
33            return Err(ExecError::Other(
34                "set-operation sort key must be a column".into(),
35            ));
36        };
37        Ok(row.column(column).cloned().unwrap_or(Value::Null))
38    }
39}
40
41fn set_operation_types(left: &RowSchema, right: &RowSchema) -> ExecResult<Vec<Option<ColumnType>>> {
42    if left.len() != right.len() {
43        return Err(ExecError::Other(format!(
44            "set-operation inputs have different widths: {} and {}",
45            left.len(),
46            right.len()
47        )));
48    }
49    left.column_types()
50        .iter()
51        .zip(right.column_types())
52        .map(|(left, right)| match (left, right) {
53            (None, None) => Ok(None),
54            (Some(ty), None) | (None, Some(ty)) => Ok(Some(ty.clone())),
55            (Some(left), Some(right)) => uqa_execution_common_type(left, right).map(Some),
56        })
57        .collect()
58}
59
60fn uqa_execution_common_type(left: &ColumnType, right: &ColumnType) -> ExecResult<ColumnType> {
61    crate::common_type(left, right).map_err(ExecError::from)
62}
63
64fn coerce_set_value(
65    value: Value,
66    source_type: Option<&ColumnType>,
67    target_type: &ColumnType,
68) -> ExecResult<Value> {
69    let cast_target = match target_type {
70        ColumnType::Domain { base, .. } => base.as_ref(),
71        target => target,
72    };
73    let source_name = source_type.map(ColumnType::sql_name);
74    uqa_sql::expr::cast_value_from(&value, &cast_target.sql_name(), source_name.as_deref())
75        .map_err(ExecError::from)
76}
77
78struct AlignSchema<'a> {
79    input_pending: crate::physical::demand::PendingRows,
80    child: Box<dyn PhysicalOperator + 'a>,
81    schema: RowSchema,
82    coercions: Vec<Option<ColumnType>>,
83}
84
85impl PhysicalOperator for AlignSchema<'_> {
86    fn row_schema(&self) -> &RowSchema {
87        &self.schema
88    }
89
90    fn backward_scan_support(&self) -> BackwardScanSupport {
91        self.child.backward_scan_support()
92    }
93
94    fn open(&mut self) -> ExecResult<()> {
95        self.input_pending.clear();
96        self.child.open()
97    }
98
99    fn next(&mut self) -> ExecResult<Option<Batch>> {
100        let Some(batch) = self.input_pending.pull(self.child.as_mut(), None)? else {
101            return Ok(None);
102        };
103        self.align_batch(batch).map(Some)
104    }
105
106    fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
107        self.input_pending
108            .pull(self.child.as_mut(), Some(rows))?
109            .map(|batch| self.align_batch(batch))
110            .transpose()
111    }
112
113    fn next_direction(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<Batch>> {
114        let Some(batch) = self.child.next_direction(direction)? else {
115            return Ok(None);
116        };
117        self.align_batch(batch).map(Some)
118    }
119
120    fn rewind(&mut self) -> ExecResult<()> {
121        self.input_pending.clear();
122        self.child.rewind()
123    }
124
125    fn close(&mut self) -> ExecResult<()> {
126        self.input_pending.clear();
127        self.child.close()
128    }
129}
130
131impl AlignSchema<'_> {
132    fn align_batch(&self, batch: Batch) -> ExecResult<Batch> {
133        let identity_layout = batch.schema.physical_width() == self.schema.physical_width()
134            && (0..batch.schema.len())
135                .all(|position| batch.schema.slot(position) == Some(position));
136        if self.coercions.iter().all(Option::is_none) && identity_layout {
137            let rows = batch
138                .rows
139                .into_iter()
140                .map(PhysicalRow::without_lock_origins)
141                .collect();
142            return Ok(Batch::from_physical_rows(self.schema.clone(), rows));
143        }
144        if self.coercions.iter().all(Option::is_none) {
145            let slots = (0..batch.schema.len())
146                .map(|position| {
147                    batch.schema.slot(position).ok_or_else(|| {
148                        ExecError::Other(format!(
149                            "set-operation input column {position} has no physical slot"
150                        ))
151                    })
152                })
153                .collect::<ExecResult<Vec<_>>>()?;
154            let rows = batch
155                .rows
156                .into_iter()
157                .map(|row| row.project_slots(&slots).without_lock_origins())
158                .collect();
159            return Ok(Batch::from_physical_rows(self.schema.clone(), rows));
160        }
161        let mut rows = Vec::with_capacity(batch.rows.len());
162        for row in batch.rows {
163            let view = batch.schema.view(&row);
164            let values = self
165                .coercions
166                .iter()
167                .enumerate()
168                .map(|(position, target)| match target {
169                    Some(target) => coerce_set_value(
170                        view.value_at(position).cloned().unwrap_or(Value::Null),
171                        batch.schema.column_type(position),
172                        target,
173                    )
174                    .map(RowProjectionValue::Owned),
175                    None => Ok(batch.schema.slot(position).map_or(
176                        RowProjectionValue::Owned(Value::Null),
177                        RowProjectionValue::InputSlot,
178                    )),
179                })
180                .collect::<ExecResult<Vec<_>>>()?;
181            rows.push(row.project_with_values(values).without_lock_origins());
182        }
183        Ok(Batch::from_physical_rows(self.schema.clone(), rows))
184    }
185}
186
187struct RowGroup {
188    row: PhysicalRow,
189    count: usize,
190}
191
192struct RowCursor<'a> {
193    operator: Box<dyn PhysicalOperator + 'a>,
194    batch: std::vec::IntoIter<PhysicalRow>,
195    lookahead: Option<PhysicalRow>,
196    exhausted: bool,
197}
198
199impl<'a> RowCursor<'a> {
200    fn new(operator: Box<dyn PhysicalOperator + 'a>) -> Self {
201        Self {
202            operator,
203            batch: Vec::new().into_iter(),
204            lookahead: None,
205            exhausted: false,
206        }
207    }
208
209    fn open(&mut self) -> ExecResult<()> {
210        self.batch = Vec::new().into_iter();
211        self.lookahead = None;
212        self.exhausted = false;
213        self.operator.open()
214    }
215
216    fn next_row(&mut self) -> ExecResult<Option<PhysicalRow>> {
217        self.pull_row(false)
218    }
219
220    fn pull_row(&mut self, demanded: bool) -> ExecResult<Option<PhysicalRow>> {
221        loop {
222            if let Some(row) = self.batch.next() {
223                return Ok(Some(row));
224            }
225            let Some(batch) = (if demanded {
226                self.operator
227                    .next_with_demand(crate::physical::demand::ONE)?
228            } else {
229                self.operator.next()?
230            }) else {
231                self.exhausted = true;
232                return Ok(None);
233            };
234            self.batch = batch.rows.into_iter();
235        }
236    }
237
238    fn backward_scan_support(&self) -> BackwardScanSupport {
239        self.operator.backward_scan_support()
240    }
241
242    fn next_direction_row(
243        &mut self,
244        direction: PhysicalScanDirection,
245    ) -> ExecResult<Option<PhysicalRow>> {
246        if self.batch.len() != 0 || self.lookahead.is_some() {
247            return Err(ExecError::Other(
248                "set-operation input cannot mix batched and directional pulls".into(),
249            ));
250        }
251        let Some(batch) = self.operator.next_direction(direction)? else {
252            self.exhausted = true;
253            return Ok(None);
254        };
255        let mut rows = batch.rows.into_iter();
256        let row = rows.next();
257        if rows.next().is_some() {
258            return Err(ExecError::Other(
259                "directional set-operation input returned more than one row".into(),
260            ));
261        }
262        self.exhausted = row.is_none();
263        Ok(row)
264    }
265
266    fn rewind(&mut self) -> ExecResult<()> {
267        self.batch = Vec::new().into_iter();
268        self.lookahead = None;
269        self.exhausted = false;
270        self.operator.rewind()
271    }
272
273    fn take_group(
274        &mut self,
275        schema: &RowSchema,
276        enums: Option<&dyn uqa_sql::expr::enums::EnumLabelCatalog>,
277    ) -> ExecResult<Option<RowGroup>> {
278        let first = match self.lookahead.take() {
279            Some(row) => row,
280            None => match self.next_row()? {
281                Some(row) => row,
282                None => return Ok(None),
283            },
284        };
285        let mut count = 1_usize;
286        while let Some(row) = self.next_row()? {
287            if compare_rows(&first, &row, schema, enums)? == Ordering::Equal {
288                count = count
289                    .checked_add(1)
290                    .ok_or_else(|| ExecError::Other("set-operation group count overflow".into()))?;
291            } else {
292                self.lookahead = Some(row);
293                break;
294            }
295        }
296        Ok(Some(RowGroup { row: first, count }))
297    }
298
299    fn close(&mut self) -> ExecResult<()> {
300        self.batch = Vec::new().into_iter();
301        self.lookahead = None;
302        self.exhausted = true;
303        self.operator.close()
304    }
305}
306
307#[derive(Clone, Copy)]
308enum DirectionalAppendPosition {
309    BeforeFirst,
310    Left,
311    Right,
312    AfterLast,
313}
314
315fn compare_rows(
316    left: &PhysicalRow,
317    right: &PhysicalRow,
318    schema: &RowSchema,
319    enums: Option<&dyn uqa_sql::expr::enums::EnumLabelCatalog>,
320) -> ExecResult<Ordering> {
321    let left = schema.view(left);
322    let right = schema.view(right);
323    let null = Value::Null;
324    for position in 0..schema.len() {
325        let left = left.value_at(position).unwrap_or(&null);
326        let right = right.value_at(position).unwrap_or(&null);
327        let ordering = match (left, right) {
328            (Value::Null, Value::Null) => Ordering::Equal,
329            (Value::Null, _) => Ordering::Less,
330            (_, Value::Null) => Ordering::Greater,
331            _ => uqa_sql::expr::compare_selected_grouping_values_with_catalog(
332                left,
333                right,
334                schema.column_type(position),
335                &uqa_core::memory::ProductionControl::uncontrolled(),
336                enums,
337            )?,
338        };
339        if ordering != Ordering::Equal {
340            return Ok(ordering);
341        }
342    }
343    Ok(Ordering::Equal)
344}
345
346/// `UNION` / `INTERSECT` / `EXCEPT` physical operator.
347///
348/// `UNION ALL` streams its children without sorting. Other forms sort both
349/// inputs through byte-bounded external runs and merge adjacent multiplicity
350/// counts, avoiding whole-input materialisation and quadratic row scans.
351pub struct ExternalSetOperation<'a> {
352    left: RowCursor<'a>,
353    right: RowCursor<'a>,
354    evaluator: SharedExpressionEvaluator<'a>,
355    kind: SetOpKind,
356    all: bool,
357    schema: RowSchema,
358    left_group: Option<RowGroup>,
359    right_group: Option<RowGroup>,
360    pending_row: Option<PhysicalRow>,
361    pending_count: usize,
362    output_bytes: usize,
363    union_all_left_done: bool,
364    incremental_union_all: bool,
365    directional_position: DirectionalAppendPosition,
366}
367
368impl ExternalSetOperation<'_> {
369    fn next_union_all(&mut self, count: usize, demanded: bool) -> ExecResult<Option<Batch>> {
370        let mut rows = Vec::with_capacity(count);
371        let mut size = crate::spill::EncodedBatchSizer::new(&self.schema)?;
372        while rows.len() < count {
373            let next = if self.union_all_left_done {
374                self.right.pull_row(demanded)?
375            } else if let Some(row) = self.left.pull_row(demanded)? {
376                Some(row)
377            } else {
378                self.union_all_left_done = true;
379                self.right.pull_row(demanded)?
380            };
381            let Some(row) = next else {
382                break;
383            };
384            let row = row.without_lock_origins();
385            size.append(&row)?;
386            rows.push(row);
387            if size.bytes() >= self.output_bytes {
388                break;
389            }
390        }
391        if rows.is_empty() {
392            Ok(None)
393        } else {
394            Ok(Some(Batch::from_physical_rows(self.schema.clone(), rows)))
395        }
396    }
397
398    fn next_union_all_row(&mut self) -> ExecResult<Option<Batch>> {
399        let row = if self.union_all_left_done {
400            self.right.pull_row(true)?
401        } else if let Some(row) = self.left.pull_row(true)? {
402            Some(row)
403        } else {
404            self.union_all_left_done = true;
405            self.right.pull_row(true)?
406        };
407        Ok(row.map(|row| self.directional_row_batch(row)))
408    }
409
410    fn directional_row_batch(&self, row: PhysicalRow) -> Batch {
411        Batch::from_physical_rows(self.schema.clone(), vec![row.without_lock_origins()])
412    }
413
414    fn next_union_all_direction(
415        &mut self,
416        direction: PhysicalScanDirection,
417    ) -> ExecResult<Option<Batch>> {
418        let mut position = match (self.directional_position, direction) {
419            (DirectionalAppendPosition::BeforeFirst, PhysicalScanDirection::Backward)
420            | (DirectionalAppendPosition::AfterLast, PhysicalScanDirection::Forward) => {
421                return Ok(None)
422            }
423            (DirectionalAppendPosition::BeforeFirst, PhysicalScanDirection::Forward)
424            | (DirectionalAppendPosition::Left, _) => DirectionalAppendPosition::Left,
425            (DirectionalAppendPosition::AfterLast, PhysicalScanDirection::Backward)
426            | (DirectionalAppendPosition::Right, _) => DirectionalAppendPosition::Right,
427        };
428        loop {
429            let row = match position {
430                DirectionalAppendPosition::Left => self.left.next_direction_row(direction)?,
431                DirectionalAppendPosition::Right => self.right.next_direction_row(direction)?,
432                DirectionalAppendPosition::BeforeFirst | DirectionalAppendPosition::AfterLast => {
433                    unreachable!()
434                }
435            };
436            if let Some(row) = row {
437                self.directional_position = position;
438                return Ok(Some(self.directional_row_batch(row)));
439            }
440            position = match (position, direction) {
441                (DirectionalAppendPosition::Left, PhysicalScanDirection::Forward) => {
442                    DirectionalAppendPosition::Right
443                }
444                (DirectionalAppendPosition::Right, PhysicalScanDirection::Backward) => {
445                    DirectionalAppendPosition::Left
446                }
447                (DirectionalAppendPosition::Left, PhysicalScanDirection::Backward) => {
448                    self.directional_position = DirectionalAppendPosition::BeforeFirst;
449                    return Ok(None);
450                }
451                (DirectionalAppendPosition::Right, PhysicalScanDirection::Forward) => {
452                    self.directional_position = DirectionalAppendPosition::AfterLast;
453                    return Ok(None);
454                }
455                (
456                    DirectionalAppendPosition::BeforeFirst | DirectionalAppendPosition::AfterLast,
457                    _,
458                ) => unreachable!(),
459            };
460        }
461    }
462
463    fn load_groups(&mut self) -> ExecResult<()> {
464        if self.left_group.is_none() && !self.left.exhausted {
465            self.left_group = self
466                .left
467                .take_group(&self.schema, self.evaluator.enum_labels())?;
468        }
469        if self.right_group.is_none() && !self.right.exhausted {
470            self.right_group = self
471                .right
472                .take_group(&self.schema, self.evaluator.enum_labels())?;
473        }
474        Ok(())
475    }
476
477    fn take_left_group(&mut self) -> ExecResult<RowGroup> {
478        self.left_group
479            .take()
480            .ok_or_else(|| ExecError::Other("set-operation selected a missing left group".into()))
481    }
482
483    fn take_right_group(&mut self) -> ExecResult<RowGroup> {
484        self.right_group
485            .take()
486            .ok_or_else(|| ExecError::Other("set-operation selected a missing right group".into()))
487    }
488
489    fn choose_group(&mut self) -> ExecResult<Option<(PhysicalRow, usize)>> {
490        self.load_groups()?;
491        let ordering = match (&self.left_group, &self.right_group) {
492            (Some(left), Some(right)) => Some(compare_rows(
493                &left.row,
494                &right.row,
495                &self.schema,
496                self.evaluator.enum_labels(),
497            )?),
498            (Some(_), None) => Some(Ordering::Less),
499            (None, Some(_)) => Some(Ordering::Greater),
500            (None, None) => None,
501        };
502        let Some(ordering) = ordering else {
503            return Ok(None);
504        };
505
506        let selected = match (self.kind, ordering) {
507            (SetOpKind::Union, Ordering::Less) => {
508                let group = self.take_left_group()?;
509                Some((group.row, 1))
510            }
511            (SetOpKind::Union, Ordering::Greater) => {
512                let group = self.take_right_group()?;
513                Some((group.row, 1))
514            }
515            (SetOpKind::Union, Ordering::Equal) => {
516                let group = self.take_left_group()?;
517                self.right_group = None;
518                Some((group.row, 1))
519            }
520            (SetOpKind::Intersect, Ordering::Less) => {
521                self.left_group = None;
522                None
523            }
524            (SetOpKind::Intersect | SetOpKind::Except, Ordering::Greater) => {
525                self.right_group = None;
526                None
527            }
528            (SetOpKind::Intersect, Ordering::Equal) => {
529                let left = self.take_left_group()?;
530                let right = self.take_right_group()?;
531                Some((
532                    left.row,
533                    if self.all {
534                        left.count.min(right.count)
535                    } else {
536                        1
537                    },
538                ))
539            }
540            (SetOpKind::Except, Ordering::Less) => {
541                let left = self.take_left_group()?;
542                Some((left.row, if self.all { left.count } else { 1 }))
543            }
544            (SetOpKind::Except, Ordering::Equal) => {
545                let left = self.take_left_group()?;
546                let right = self.take_right_group()?;
547                let count = if self.all {
548                    left.count.saturating_sub(right.count)
549                } else {
550                    0
551                };
552                Some((left.row, count))
553            }
554        };
555        Ok(selected.filter(|(_, count)| *count > 0))
556    }
557}
558
559impl PhysicalOperator for ExternalSetOperation<'_> {
560    fn row_schema(&self) -> &RowSchema {
561        &self.schema
562    }
563
564    fn backward_scan_support(&self) -> BackwardScanSupport {
565        if matches!((self.kind, self.all), (SetOpKind::Union, true))
566            && self.left.backward_scan_support() == BackwardScanSupport::Native
567            && self.right.backward_scan_support() == BackwardScanSupport::Native
568        {
569            BackwardScanSupport::Native
570        } else {
571            BackwardScanSupport::Unsupported
572        }
573    }
574
575    fn open(&mut self) -> ExecResult<()> {
576        self.left_group = None;
577        self.right_group = None;
578        self.pending_row = None;
579        self.pending_count = 0;
580        self.union_all_left_done = false;
581        self.directional_position = DirectionalAppendPosition::BeforeFirst;
582        self.left.open()?;
583        self.right.open()
584    }
585
586    fn next(&mut self) -> ExecResult<Option<Batch>> {
587        if matches!((self.kind, self.all), (SetOpKind::Union, true)) {
588            return if self.incremental_union_all {
589                self.next_union_all_row()
590            } else {
591                self.next_union_all(DEFAULT_BATCH_SIZE, false)
592            };
593        }
594        let mut rows = Vec::with_capacity(DEFAULT_BATCH_SIZE);
595        let mut size = crate::spill::EncodedBatchSizer::new(&self.schema)?;
596        while rows.len() < DEFAULT_BATCH_SIZE {
597            if self.pending_count > 0 {
598                let row = self.pending_row.as_ref().ok_or_else(|| {
599                    ExecError::Other(
600                        "set-operation has pending multiplicity without a pending row".into(),
601                    )
602                })?;
603                size.append(row)?;
604                rows.push(row.clone());
605                self.pending_count -= 1;
606                if self.pending_count == 0 {
607                    self.pending_row = None;
608                }
609                if size.bytes() >= self.output_bytes {
610                    break;
611                }
612                continue;
613            }
614            match self.choose_group()? {
615                Some((row, count)) => {
616                    self.pending_row = Some(row.without_lock_origins());
617                    self.pending_count = count;
618                }
619                None if self.left.exhausted && self.right.exhausted => break,
620                None => {}
621            }
622        }
623        if rows.is_empty() {
624            Ok(None)
625        } else {
626            Ok(Some(Batch::from_physical_rows(self.schema.clone(), rows)))
627        }
628    }
629
630    fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
631        if matches!((self.kind, self.all), (SetOpKind::Union, true)) {
632            self.next_union_all(rows.get().min(DEFAULT_BATCH_SIZE), true)
633        } else {
634            self.next()
635        }
636    }
637
638    fn next_direction(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<Batch>> {
639        if self.backward_scan_support() == BackwardScanSupport::Native {
640            return self.next_union_all_direction(direction);
641        }
642        if direction == PhysicalScanDirection::Forward {
643            return if matches!((self.kind, self.all), (SetOpKind::Union, true)) {
644                self.next_union_all_row()
645            } else {
646                self.next()
647            };
648        }
649        Err(ExecError::Other(
650            "set operation does not support backwards scanning".into(),
651        ))
652    }
653
654    fn rewind(&mut self) -> ExecResult<()> {
655        if self.backward_scan_support() != BackwardScanSupport::Native {
656            return Err(ExecError::Other(
657                "set operation does not support rewind".into(),
658            ));
659        }
660        self.left.rewind()?;
661        self.right.rewind()?;
662        self.directional_position = DirectionalAppendPosition::BeforeFirst;
663        Ok(())
664    }
665
666    fn close(&mut self) -> ExecResult<()> {
667        self.left_group = None;
668        self.right_group = None;
669        self.pending_row = None;
670        self.pending_count = 0;
671        self.directional_position = DirectionalAppendPosition::BeforeFirst;
672        let left = self.left.close();
673        let right = self.right.close();
674        crate::physical::with_cleanup(left, right, "close right set-operation input")
675    }
676}
677
678#[cfg(test)]
679mod tests {
680    mod enums;
681    mod memory;
682    mod ranges;
683    use super::*;
684    use crate::physical::run_to_rows;
685    use crate::scan::TableScan;
686    use crate::RowSchemaExecution;
687
688    fn row(value: i64) -> ResultRow {
689        [("v".into(), Value::Int(value))].into_iter().collect()
690    }
691
692    fn execute(kind: SetOpKind, all: bool, left: &[i64], right: &[i64]) -> Vec<i64> {
693        let left = TableScan::from_rows(vec!["v".into()], left.iter().copied().map(row).collect());
694        let right = TableScan::from_rows(
695            vec!["other".into()],
696            right
697                .iter()
698                .copied()
699                .map(|value| [("other".into(), Value::Int(value))].into_iter().collect())
700                .collect(),
701        );
702        let mut set =
703            ExternalSetOperation::new(Box::new(left), Box::new(right), kind, all, 1).unwrap();
704        run_to_rows(&mut set)
705            .unwrap()
706            .1
707            .into_iter()
708            .map(|row| match row.get("v") {
709                Some(Value::Int(value)) => *value,
710                value => panic!("unexpected set value: {value:?}"),
711            })
712            .collect()
713    }
714
715    #[test]
716    fn external_set_semantics_include_bag_multiplicity() {
717        assert_eq!(
718            execute(SetOpKind::Union, false, &[2, 1, 1], &[3, 2]),
719            vec![1, 2, 3]
720        );
721        assert_eq!(
722            execute(SetOpKind::Union, true, &[2, 1, 1], &[3, 2]),
723            vec![2, 1, 1, 3, 2]
724        );
725        assert_eq!(
726            execute(SetOpKind::Intersect, true, &[1, 1, 1, 2], &[1, 1, 3]),
727            vec![1, 1]
728        );
729        assert_eq!(
730            execute(SetOpKind::Except, true, &[1, 1, 1, 2], &[1, 1, 3]),
731            vec![1, 2]
732        );
733        assert_eq!(
734            execute(SetOpKind::Except, false, &[1, 1, 2], &[1, 3]),
735            vec![2]
736        );
737    }
738
739    #[test]
740    fn set_inputs_compact_schema_only_projections_before_alignment() {
741        let left = TableScan::from_rows(
742            vec!["v".into(), "hidden".into()],
743            vec![[
744                ("v".into(), Value::Int(1)),
745                ("hidden".into(), Value::Int(99)),
746            ]
747            .into_iter()
748            .collect()],
749        );
750        let left: Box<dyn PhysicalOperator> = Box::new(crate::ColumnSelection::with_positions(
751            Box::new(left),
752            vec![("v".into(), 0)],
753        ));
754        let right = TableScan::from_rows(vec!["v".into()], vec![row(2)]);
755        let mut set =
756            ExternalSetOperation::new(left, Box::new(right), SetOpKind::Union, true, 1).unwrap();
757        let rows = run_to_rows(&mut set).unwrap().1;
758        assert_eq!(rows, vec![row(1), row(2)]);
759    }
760
761    fn directional_value(batch: Option<Batch>) -> Option<i64> {
762        let batch = batch?;
763        let row = batch.rows.first()?;
764        match batch.schema.view(row).value_at(0) {
765            Some(Value::Int(value)) => Some(*value),
766            value => panic!("unexpected directional set value: {value:?}"),
767        }
768    }
769
770    #[test]
771    fn union_all_scans_children_in_reverse_order_across_the_boundary() {
772        let left: Box<dyn PhysicalOperator> = Box::new(crate::ScrollMaterialize::new(Box::new(
773            TableScan::from_rows(vec!["v".into()], vec![row(1), row(2)]),
774        )));
775        let right: Box<dyn PhysicalOperator> = Box::new(crate::ScrollMaterialize::new(Box::new(
776            TableScan::from_rows(vec!["v".into()], vec![row(3), row(4)]),
777        )));
778        let mut set = ExternalSetOperation::new(left, right, SetOpKind::Union, true, 1).unwrap();
779        assert_eq!(set.backward_scan_support(), BackwardScanSupport::Native);
780        set.open().unwrap();
781        for (direction, expected) in [
782            (PhysicalScanDirection::Forward, 1),
783            (PhysicalScanDirection::Forward, 2),
784            (PhysicalScanDirection::Forward, 3),
785            (PhysicalScanDirection::Backward, 2),
786            (PhysicalScanDirection::Forward, 3),
787        ] {
788            assert_eq!(
789                directional_value(set.next_direction(direction).unwrap()),
790                Some(expected)
791            );
792        }
793        set.rewind().unwrap();
794        assert_eq!(
795            directional_value(set.next_direction(PhysicalScanDirection::Forward).unwrap()),
796            Some(1)
797        );
798        set.close().unwrap();
799    }
800
801    #[test]
802    fn directional_union_all_materialization_pulls_one_row_at_a_time() {
803        let left: Box<dyn PhysicalOperator> =
804            Box::new(TableScan::from_rows(vec!["v".into()], vec![row(1), row(2)]));
805        let right: Box<dyn PhysicalOperator> =
806            Box::new(TableScan::from_rows(vec!["v".into()], vec![row(3)]));
807        let mut set = ExternalSetOperation::new_directional_with_types(
808            left,
809            right,
810            SetOpKind::Union,
811            true,
812            vec![None],
813            1,
814        )
815        .unwrap();
816        assert_eq!(
817            set.backward_scan_support(),
818            BackwardScanSupport::Unsupported
819        );
820        set.open().unwrap();
821        for expected in [1, 2, 3] {
822            let batch = set.next().unwrap().unwrap();
823            assert_eq!(batch.rows.len(), 1);
824            assert_eq!(directional_value(Some(batch)), Some(expected));
825        }
826        assert!(set.next().unwrap().is_none());
827        set.close().unwrap();
828    }
829}