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::expr::truthy;
11use uqa_sql::ResultRow;
12
13use super::{
14    output_schema, push_output_row, HybridRowStore, MatchFlags, DEFAULT_JOIN_WORK_MEM_BYTES,
15};
16use crate::{
17    Batch, ExecError, ExecResult, PhysicalOperator, PhysicalRow, RowSchema, ScalarExpr,
18    SharedExpressionEvaluator, SpillBuffer,
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<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    output_spilled: bool,
37    right_input_spilled: bool,
38}
39
40impl<'a> NestedLoopJoin<'a> {
41    pub fn new(
42        left: Box<dyn PhysicalOperator + 'a>,
43        right: Box<dyn PhysicalOperator + 'a>,
44        kind: JoinKind,
45        predicate: Option<ScalarExpr>,
46        evaluator: SharedExpressionEvaluator<'a>,
47        left_nulls: ResultRow,
48        right_nulls: ResultRow,
49    ) -> Self {
50        Self::new_with_work_mem(
51            left,
52            right,
53            kind,
54            predicate,
55            evaluator,
56            left_nulls,
57            right_nulls,
58            DEFAULT_JOIN_WORK_MEM_BYTES,
59        )
60    }
61
62    #[expect(
63        clippy::too_many_arguments,
64        reason = "keeps join keys and schema aligned"
65    )]
66    pub fn new_with_work_mem(
67        left: Box<dyn PhysicalOperator + 'a>,
68        right: Box<dyn PhysicalOperator + 'a>,
69        kind: JoinKind,
70        predicate: Option<ScalarExpr>,
71        evaluator: SharedExpressionEvaluator<'a>,
72        left_nulls: ResultRow,
73        right_nulls: ResultRow,
74        work_mem_bytes: usize,
75    ) -> Self {
76        let schema = output_schema(
77            left.row_schema(),
78            right.row_schema(),
79            &left_nulls,
80            &right_nulls,
81        );
82        let left_nulls = PhysicalRow::nulls(left.row_schema().physical_width());
83        let right_nulls = PhysicalRow::nulls(right.row_schema().physical_width());
84        Self {
85            left,
86            right,
87            kind,
88            predicate: predicate.map(crate::scalar::PreparedExpressions::scalar),
89            evaluator,
90            left_nulls,
91            right_nulls,
92            schema,
93            work_mem_bytes,
94            output: None,
95            output_spilled: false,
96            right_input_spilled: false,
97        }
98    }
99
100    pub fn output_has_spilled(&self) -> bool {
101        self.output_spilled
102    }
103
104    /// Whether the repeatable nested-loop build input exceeded its memory
105    /// budget and migrated to an indexed temporary row store.
106    pub fn right_input_has_spilled(&self) -> bool {
107        self.right_input_spilled
108    }
109
110    fn matches(&self, row: &PhysicalRow) -> ExecResult<bool> {
111        match self.predicate.as_ref() {
112            None => Ok(true),
113            Some(predicate) => Ok(truthy(
114                &self.evaluator.evaluate_physical_with_function_states(
115                    predicate,
116                    &self.schema,
117                    row,
118                    predicate.calls(),
119                )?,
120            )),
121        }
122    }
123}
124
125impl PhysicalOperator for NestedLoopJoin<'_> {
126    fn row_schema(&self) -> &RowSchema {
127        &self.schema
128    }
129
130    fn open(&mut self) -> ExecResult<()> {
131        self.output = None;
132        self.output_spilled = false;
133        self.right_input_spilled = false;
134
135        let right_budget = self.work_mem_bytes / 2;
136        let output_budget = self.work_mem_bytes.saturating_sub(right_budget);
137        let right_schema = self.right.row_schema().clone();
138        let mut right = HybridRowStore::new(right_schema, right_budget);
139        self.right.open()?;
140        while let Some(batch) = self.right.next()? {
141            for row in batch.rows {
142                right.push(row)?;
143            }
144        }
145        self.right_input_spilled = right.has_spilled();
146        let mut matched_right = matches!(self.kind, JoinKind::Right | JoinKind::Full)
147            .then(|| MatchFlags::new(right.len()))
148            .transpose()?;
149        let mut output = SpillBuffer::new(output_budget);
150        let mut pending = Vec::with_capacity(crate::batch::DEFAULT_BATCH_SIZE);
151
152        self.left.open()?;
153        while let Some(batch) = self.left.next()? {
154            for left_row in batch.rows {
155                let mut matched_left = false;
156                for right_index in 0..right.len() {
157                    right.with_row(right_index, |right_row| {
158                        let merged = PhysicalRow::concat(&left_row, right_row);
159                        if self.matches(&merged)? {
160                            push_output_row(&mut output, &mut pending, &self.schema, merged)?;
161                            matched_left = true;
162                            if let Some(flags) = matched_right.as_mut() {
163                                flags.mark(right_index)?;
164                            }
165                        }
166                        Ok(())
167                    })?;
168                }
169                if !matched_left && matches!(self.kind, JoinKind::Left | JoinKind::Full) {
170                    push_output_row(
171                        &mut output,
172                        &mut pending,
173                        &self.schema,
174                        PhysicalRow::concat_left_owned(left_row, &self.right_nulls),
175                    )?;
176                }
177            }
178        }
179
180        if matches!(self.kind, JoinKind::Right | JoinKind::Full) {
181            let matched_right = matched_right.as_mut().ok_or_else(|| {
182                ExecError::Other("right/full nested-loop join has no match flags".into())
183            })?;
184            for right_index in 0..right.len() {
185                if !matched_right.is_marked(right_index)? {
186                    right.with_row(right_index, |right_row| {
187                        push_output_row(
188                            &mut output,
189                            &mut pending,
190                            &self.schema,
191                            PhysicalRow::concat(&self.left_nulls, right_row),
192                        )
193                    })?;
194                }
195            }
196        }
197        if !pending.is_empty() {
198            output.push(Batch::from_physical_rows(self.schema.clone(), pending))?;
199        }
200        self.output_spilled = output.has_spilled();
201        self.output = Some(output.drain()?);
202        Ok(())
203    }
204
205    fn next(&mut self) -> ExecResult<Option<Batch>> {
206        self.output
207            .as_mut()
208            .map_or(Ok(None), |output| output.next().transpose())
209    }
210
211    fn close(&mut self) -> ExecResult<()> {
212        self.output = None;
213        let left = self.left.close();
214        let right = self.right.close();
215        crate::physical::with_cleanup(left, right, "close right nested-loop join input")
216    }
217}