Skip to main content

uqa_execution/join/
nested_loop.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Nested-loop physical join execution.
8
9use uqa_sql::ast::JoinKind;
10use uqa_sql::ResultRow;
11
12use super::{output_schema, HybridRowStore, MatchFlags, SpillState, DEFAULT_JOIN_WORK_MEM_BYTES};
13
14mod iteration;
15use crate::{
16    Batch, ExecError, ExecResult, PhysicalOperator, PhysicalRow, RowSchema, ScalarExpr,
17    SharedExpressionEvaluator,
18};
19
20/// Nested-loop implementation for arbitrary join predicates and every SQL
21/// outer-join shape. Predicate evaluation happens against the merged row, so
22/// qualified columns and engine-provided scalar/subquery semantics remain
23/// available through the shared expression evaluator.
24pub struct NestedLoopJoin<'a> {
25    left: Box<dyn PhysicalOperator + 'a>,
26    right: Box<dyn PhysicalOperator + 'a>,
27    kind: JoinKind,
28    predicate: Option<crate::scalar::PreparedExpressions<ScalarExpr>>,
29    evaluator: SharedExpressionEvaluator<'a>,
30    left_nulls: PhysicalRow,
31    right_nulls: PhysicalRow,
32    schema: RowSchema,
33    work_mem_bytes: usize,
34    output: Option<crate::spill::SpillDrain>,
35    left_pending: crate::physical::demand::PendingRows,
36    right_pending: crate::physical::demand::PendingRows,
37    right_rows: Option<HybridRowStore>,
38    matched_right: Option<MatchFlags>,
39    current_left: Option<PhysicalRow>,
40    right_position: u64,
41    unmatched_position: u64,
42    matched_left: bool,
43    left_finished: bool,
44    right_state: RightInputState,
45    output_spilled: SpillState,
46    right_input_spilled: SpillState,
47}
48
49#[derive(Clone, Copy, Eq, PartialEq)]
50enum RightInputState {
51    Unopened,
52    Open,
53    Exhausted,
54}
55
56impl<'a> NestedLoopJoin<'a> {
57    pub fn new(
58        left: Box<dyn PhysicalOperator + 'a>,
59        right: Box<dyn PhysicalOperator + 'a>,
60        kind: JoinKind,
61        predicate: Option<ScalarExpr>,
62        evaluator: SharedExpressionEvaluator<'a>,
63        left_nulls: ResultRow,
64        right_nulls: ResultRow,
65    ) -> Self {
66        Self::new_with_work_mem(
67            left,
68            right,
69            kind,
70            predicate,
71            evaluator,
72            left_nulls,
73            right_nulls,
74            DEFAULT_JOIN_WORK_MEM_BYTES,
75        )
76    }
77
78    #[expect(
79        clippy::too_many_arguments,
80        reason = "keeps join keys and schema aligned"
81    )]
82    pub fn new_with_work_mem(
83        left: Box<dyn PhysicalOperator + 'a>,
84        right: Box<dyn PhysicalOperator + 'a>,
85        kind: JoinKind,
86        predicate: Option<ScalarExpr>,
87        evaluator: SharedExpressionEvaluator<'a>,
88        left_nulls: ResultRow,
89        right_nulls: ResultRow,
90        work_mem_bytes: usize,
91    ) -> Self {
92        let left = super::presence::input(left, matches!(kind, JoinKind::Right | JoinKind::Full));
93        let right = super::presence::input(right, matches!(kind, JoinKind::Left | JoinKind::Full));
94        let schema = output_schema(
95            left.row_schema(),
96            right.row_schema(),
97            &left_nulls,
98            &right_nulls,
99        );
100        let left_nulls = PhysicalRow::nulls(left.row_schema().physical_width());
101        let right_nulls = PhysicalRow::nulls(right.row_schema().physical_width());
102        Self {
103            left,
104            right,
105            kind,
106            predicate: predicate.map(crate::scalar::PreparedExpressions::scalar),
107            evaluator,
108            left_nulls,
109            right_nulls,
110            schema,
111            work_mem_bytes,
112            output: None,
113            left_pending: crate::physical::demand::PendingRows::default(),
114            right_pending: crate::physical::demand::PendingRows::default(),
115            right_rows: None,
116            matched_right: None,
117            current_left: None,
118            right_position: 0,
119            unmatched_position: 0,
120            matched_left: false,
121            left_finished: false,
122            right_state: RightInputState::Unopened,
123            output_spilled: SpillState::InMemory,
124            right_input_spilled: SpillState::InMemory,
125        }
126    }
127
128    pub fn output_has_spilled(&self) -> bool {
129        self.output_spilled.is_spilled()
130    }
131
132    /// Whether the repeatable nested-loop build input exceeded its memory
133    /// budget and migrated to an indexed temporary row store.
134    pub fn right_input_has_spilled(&self) -> bool {
135        self.right_input_spilled.is_spilled()
136    }
137}
138
139impl PhysicalOperator for NestedLoopJoin<'_> {
140    fn row_schema(&self) -> &RowSchema {
141        &self.schema
142    }
143
144    fn open(&mut self) -> ExecResult<()> {
145        self.output = None;
146        self.output_spilled = SpillState::InMemory;
147        self.right_input_spilled = SpillState::InMemory;
148        self.left_pending.clear();
149        self.right_pending.clear();
150        self.current_left = None;
151        self.right_position = 0;
152        self.unmatched_position = 0;
153        self.matched_left = false;
154        self.left_finished = false;
155        self.right_state = RightInputState::Unopened;
156        self.right_rows = Some(HybridRowStore::new(
157            self.right.row_schema().clone(),
158            self.work_mem_bytes / 2,
159        ));
160        self.matched_right = matches!(self.kind, JoinKind::Right | JoinKind::Full)
161            .then(|| MatchFlags::new(0, "join"))
162            .transpose()?;
163        self.left.open()
164    }
165
166    fn next(&mut self) -> ExecResult<Option<Batch>> {
167        self.pull(crate::batch::DEFAULT_BATCH_SIZE, false)
168    }
169
170    fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
171        self.pull(rows.get().min(crate::batch::DEFAULT_BATCH_SIZE), true)
172    }
173
174    fn close(&mut self) -> ExecResult<()> {
175        self.output = None;
176        self.current_left = None;
177        self.right_rows = None;
178        self.matched_right = None;
179        self.left_pending.clear();
180        self.right_pending.clear();
181        let left = self.left.close();
182        let right = if self.right_state == RightInputState::Open {
183            self.right.close()
184        } else {
185            Ok(())
186        };
187        self.right_state = RightInputState::Exhausted;
188        crate::physical::with_cleanup(left, right, "close right nested-loop join input")
189    }
190}