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_core::memory::{Produced, ProductionControl};
10use uqa_sql::ast::JoinKind;
11use uqa_sql::{ResultRow, SQLError};
12
13use super::{HybridRowStore, MatchFlags, SpillState, DEFAULT_JOIN_WORK_MEM_BYTES};
14
15mod iteration;
16use crate::{
17    Batch, ExecError, ExecResult, PhysicalOperator, PhysicalRow, RowSchema, ScalarExpr,
18    SharedExpressionEvaluator,
19};
20
21/// Nested-loop implementation for arbitrary join predicates and every SQL
22/// outer-join shape. Predicate evaluation happens against the merged row, so
23/// qualified columns and engine-provided scalar/subquery semantics remain
24/// available through the shared expression evaluator.
25pub struct NestedLoopJoin<'a> {
26    left: Box<dyn PhysicalOperator + 'a>,
27    right: Box<dyn PhysicalOperator + 'a>,
28    kind: JoinKind,
29    predicate: Option<crate::scalar::PreparedExpressions<Produced<ScalarExpr>>>,
30    evaluator: SharedExpressionEvaluator<'a>,
31    left_nulls: PhysicalRow,
32    right_nulls: PhysicalRow,
33    schema: RowSchema,
34    work_mem_bytes: usize,
35    output: Option<crate::spill::SpillDrain>,
36    left_pending: crate::physical::demand::PendingRows,
37    right_pending: crate::physical::demand::PendingRows,
38    right_rows: Option<HybridRowStore>,
39    matched_right: Option<MatchFlags>,
40    current_left: Option<PhysicalRow>,
41    right_position: u64,
42    unmatched_position: u64,
43    matched_left: bool,
44    left_finished: bool,
45    right_state: RightInputState,
46    output_spilled: SpillState,
47    right_input_spilled: SpillState,
48    memory: Option<uqa_core::memory::MemoryReservation>,
49}
50
51#[derive(Clone, Copy, Eq, PartialEq)]
52enum RightInputState {
53    Unopened,
54    Open,
55    Exhausted,
56}
57
58impl<'a> NestedLoopJoin<'a> {
59    pub fn new(
60        left: Box<dyn PhysicalOperator + 'a>,
61        right: Box<dyn PhysicalOperator + 'a>,
62        kind: JoinKind,
63        predicate: Option<ScalarExpr>,
64        evaluator: SharedExpressionEvaluator<'a>,
65        left_nulls: ResultRow,
66        right_nulls: ResultRow,
67    ) -> Self {
68        Self::new_with_work_mem(
69            left,
70            right,
71            kind,
72            predicate,
73            evaluator,
74            left_nulls,
75            right_nulls,
76            DEFAULT_JOIN_WORK_MEM_BYTES,
77        )
78    }
79
80    #[expect(
81        clippy::too_many_arguments,
82        reason = "keeps join keys and schema aligned"
83    )]
84    pub fn new_with_work_mem(
85        left: Box<dyn PhysicalOperator + 'a>,
86        right: Box<dyn PhysicalOperator + 'a>,
87        kind: JoinKind,
88        predicate: Option<ScalarExpr>,
89        evaluator: SharedExpressionEvaluator<'a>,
90        left_nulls: ResultRow,
91        right_nulls: ResultRow,
92        work_mem_bytes: usize,
93    ) -> Self {
94        let control = ProductionControl::uncontrolled();
95        Self::with_owned_predicate(
96            left,
97            right,
98            kind,
99            predicate.map(|predicate| {
100                control
101                    .finish(predicate, None)
102                    .expect("ordinary join predicate")
103            }),
104            evaluator,
105            left_nulls,
106            right_nulls,
107            work_mem_bytes,
108            &control,
109        )
110        .expect("ordinary nested-loop construction")
111    }
112
113    #[expect(
114        clippy::too_many_arguments,
115        reason = "retains both join inputs and the admitted predicate"
116    )]
117    pub fn with_owned_predicate(
118        left: Box<dyn PhysicalOperator + 'a>,
119        right: Box<dyn PhysicalOperator + 'a>,
120        kind: JoinKind,
121        predicate: Option<Produced<ScalarExpr>>,
122        evaluator: SharedExpressionEvaluator<'a>,
123        left_nulls: ResultRow,
124        right_nulls: ResultRow,
125        work_mem_bytes: usize,
126        control: &ProductionControl<'_>,
127    ) -> Result<Self, SQLError> {
128        let (left, right, (schema, predicate)) =
129            crate::physical::construction::OperatorBuild::pair(left, right, |left, right| {
130                control.check()?;
131                super::presence::join_inputs(left, right, kind, control)?;
132                let schema = RowSchema::join_borrowed_columns_with_control(
133                    left.row_schema(),
134                    right.row_schema(),
135                    left_nulls
136                        .keys()
137                        .chain(right_nulls.keys())
138                        .map(String::as_str),
139                    control,
140                )?;
141                let predicate = predicate
142                    .map(|predicate| {
143                        crate::scalar::PreparedExpressions::produced_scalar(predicate, control)
144                    })
145                    .transpose()?;
146                Ok((schema, predicate))
147            })?;
148        let left_nulls = PhysicalRow::nulls(left.row_schema().physical_width());
149        let right_nulls = PhysicalRow::nulls(right.row_schema().physical_width());
150        Ok(Self {
151            left,
152            right,
153            kind,
154            predicate,
155            evaluator,
156            left_nulls,
157            right_nulls,
158            schema,
159            work_mem_bytes,
160            output: None,
161            left_pending: crate::physical::demand::PendingRows::default(),
162            right_pending: crate::physical::demand::PendingRows::default(),
163            right_rows: None,
164            matched_right: None,
165            current_left: None,
166            right_position: 0,
167            unmatched_position: 0,
168            matched_left: false,
169            left_finished: false,
170            right_state: RightInputState::Unopened,
171            output_spilled: SpillState::InMemory,
172            right_input_spilled: SpillState::InMemory,
173            memory: None,
174        })
175    }
176
177    pub fn into_boxed(mut self, control: &ProductionControl<'_>) -> Result<Box<Self>, SQLError> {
178        match control.reserve(size_of::<Self>()) {
179            Ok(memory) => {
180                self.memory = memory;
181                Ok(Box::new(self))
182            }
183            Err(error) => {
184                let left = self.left.close();
185                let right = self.right.close();
186                let cleanup = crate::physical::with_cleanup(
187                    left,
188                    right,
189                    "close right nested-loop input after construction failure",
190                );
191                Err(match cleanup {
192                    Ok(()) => error.into(),
193                    Err(cleanup) => SQLError::from(error).with_cleanup(
194                        crate::physical::physical_exec_error(cleanup),
195                        "close nested-loop join after wrapper admission failure",
196                    ),
197                })
198            }
199        }
200    }
201
202    pub fn output_has_spilled(&self) -> bool {
203        self.output_spilled.is_spilled()
204    }
205
206    /// Whether the repeatable nested-loop build input exceeded its memory
207    /// budget and migrated to an indexed temporary row store.
208    pub fn right_input_has_spilled(&self) -> bool {
209        self.right_input_spilled.is_spilled()
210    }
211}
212
213impl PhysicalOperator for NestedLoopJoin<'_> {
214    fn row_schema(&self) -> &RowSchema {
215        &self.schema
216    }
217
218    fn open(&mut self) -> ExecResult<()> {
219        self.output = None;
220        self.output_spilled = SpillState::InMemory;
221        self.right_input_spilled = SpillState::InMemory;
222        self.left_pending.clear();
223        self.right_pending.clear();
224        self.current_left = None;
225        self.right_position = 0;
226        self.unmatched_position = 0;
227        self.matched_left = false;
228        self.left_finished = false;
229        self.right_state = RightInputState::Unopened;
230        self.right_rows = Some(HybridRowStore::new(
231            self.right.row_schema().clone(),
232            self.work_mem_bytes / 2,
233        ));
234        self.matched_right = matches!(self.kind, JoinKind::Right | JoinKind::Full)
235            .then(|| MatchFlags::new(0, "join"))
236            .transpose()?;
237        self.left.open()
238    }
239
240    fn next(&mut self) -> ExecResult<Option<Batch>> {
241        self.pull(crate::batch::DEFAULT_BATCH_SIZE, false)
242    }
243
244    fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
245        self.pull(rows.get().min(crate::batch::DEFAULT_BATCH_SIZE), true)
246    }
247
248    fn close(&mut self) -> ExecResult<()> {
249        self.output = None;
250        self.current_left = None;
251        self.right_rows = None;
252        self.matched_right = None;
253        self.left_pending.clear();
254        self.right_pending.clear();
255        let left = self.left.close();
256        let right = if self.right_state == RightInputState::Open {
257            self.right.close()
258        } else {
259            Ok(())
260        };
261        self.right_state = RightInputState::Exhausted;
262        crate::physical::with_cleanup(left, right, "close right nested-loop join input")
263    }
264}