1use 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
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<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 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}