1use 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
21pub 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 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(), "join"))
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}