1use uqa_core::memory::{MemoryReservation, ProductionControl};
10use uqa_sql::ast::JoinKind;
11use uqa_sql::{ResultRow, SQLError};
12
13use crate::batch::DEFAULT_BATCH_SIZE;
14use crate::{
15 Batch, ExecError, ExecResult, OwnedPhysicalRow, PhysicalOperator, PhysicalRow, RowSchema,
16};
17
18pub type LateralRows<'a> = crate::SQLRowStream<'a, OwnedPhysicalRow>;
22
23pub trait LateralSource<'a>: Send {
24 fn rows_for(&mut self, left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>>;
25
26 fn admits(&mut self, right: &OwnedPhysicalRow) -> ExecResult<bool>;
28
29 fn matches(&mut self, joined: &OwnedPhysicalRow) -> ExecResult<bool>;
30
31 fn close(&mut self) -> ExecResult<()> {
34 Ok(())
35 }
36}
37
38pub struct LateralJoin<'a> {
44 left: Box<dyn PhysicalOperator + 'a>,
45 source: Box<dyn LateralSource<'a> + 'a>,
46 kind: JoinKind,
47 schema: RowSchema,
48 left_schema: RowSchema,
49 right_presence: crate::join::presence::NullableRow,
50 left_rows: std::vec::IntoIter<OwnedPhysicalRow>,
51 current_left: Option<OwnedPhysicalRow>,
52 right_rows: Option<LateralRows<'a>>,
53 matched_left: bool,
54 exhausted: bool,
55 memory: Option<MemoryReservation>,
56}
57
58impl<'a> LateralJoin<'a> {
59 pub fn new(
60 left: Box<dyn PhysicalOperator + 'a>,
61 source: Box<dyn LateralSource<'a> + 'a>,
62 kind: JoinKind,
63 left_nulls: ResultRow,
64 right_nulls: ResultRow,
65 ) -> Self {
66 let right_schema = RowSchema::new(right_nulls.keys().cloned().collect());
67 Self::new_with_right_schema(left, source, kind, left_nulls, right_nulls, right_schema)
68 }
69
70 pub fn new_with_right_schema(
71 left: Box<dyn PhysicalOperator + 'a>,
72 source: Box<dyn LateralSource<'a> + 'a>,
73 kind: JoinKind,
74 left_nulls: ResultRow,
75 right_nulls: ResultRow,
76 right_schema: RowSchema,
77 ) -> Self {
78 Self::with_right_schema_with_control(
79 left,
80 source,
81 kind,
82 left_nulls,
83 right_nulls,
84 right_schema,
85 &ProductionControl::uncontrolled(),
86 )
87 .expect("ordinary lateral join construction")
88 }
89
90 pub fn with_right_schema_with_control(
91 left: Box<dyn PhysicalOperator + 'a>,
92 mut source: Box<dyn LateralSource<'a> + 'a>,
93 kind: JoinKind,
94 left_nulls: ResultRow,
95 right_nulls: ResultRow,
96 right_schema: RowSchema,
97 control: &ProductionControl<'_>,
98 ) -> Result<Self, SQLError> {
99 let built = crate::physical::construction::OperatorBuild::run(left, |left| {
100 left.attach(|input| {
101 crate::join::presence::input_with_control(
102 input,
103 matches!(kind, JoinKind::Right | JoinKind::Full),
104 control,
105 )
106 })?;
107 let right_presence = crate::join::presence::NullableRow::with_control(
108 &right_schema,
109 matches!(kind, JoinKind::Left | JoinKind::Full),
110 control,
111 )?;
112 let schema = RowSchema::join_borrowed_columns_with_control(
113 left.row_schema(),
114 &right_presence.schema,
115 left_nulls
116 .keys()
117 .chain(right_nulls.keys())
118 .map(String::as_str),
119 control,
120 )?;
121 Ok((right_presence, schema))
122 });
123 let (left, (right_presence, schema)) = match built {
124 Ok(output) => output,
125 Err(error) => {
126 return Err(match source.close() {
127 Ok(()) => error,
128 Err(cleanup) => error.with_cleanup(
129 crate::physical::physical_exec_error(cleanup),
130 "close lateral source after construction failure",
131 ),
132 })
133 }
134 };
135 let left_schema = left.row_schema().clone();
136 Ok(Self {
137 left,
138 source,
139 kind,
140 schema,
141 left_schema,
142 right_presence,
143 left_rows: Vec::new().into_iter(),
144 current_left: None,
145 right_rows: None,
146 matched_left: false,
147 exhausted: false,
148 memory: None,
149 })
150 }
151
152 pub fn into_boxed(mut self, control: &ProductionControl<'_>) -> Result<Box<Self>, SQLError> {
153 match control.reserve(size_of::<Self>()) {
154 Ok(memory) => {
155 self.memory = memory;
156 Ok(Box::new(self))
157 }
158 Err(error) => Err(match self.close() {
159 Ok(()) => error.into(),
160 Err(cleanup) => SQLError::from(error).with_cleanup(
161 crate::physical::physical_exec_error(cleanup),
162 "close lateral join after wrapper admission failure",
163 ),
164 }),
165 }
166 }
167
168 fn next_left(&mut self) -> ExecResult<Option<OwnedPhysicalRow>> {
169 loop {
170 if let Some(row) = self.left_rows.next() {
171 return Ok(Some(row));
172 }
173 let Some(batch) = self.left.next_with_demand(crate::physical::demand::ONE)? else {
174 return Ok(None);
175 };
176 self.left_rows = batch.into_owned_rows().into_iter();
177 }
178 }
179
180 fn begin_left_row(&mut self, left: OwnedPhysicalRow) -> ExecResult<()> {
181 self.right_rows = Some(self.source.rows_for(&left)?);
182 self.current_left = Some(left);
183 self.matched_left = false;
184 Ok(())
185 }
186}
187
188impl LateralJoin<'_> {
189 fn close_right(&mut self) -> ExecResult<()> {
190 self.right_rows
191 .take()
192 .map_or(Ok(()), |mut rows| rows.close().map_err(Into::into))
193 }
194
195 fn pull(&mut self, batch_size: usize) -> ExecResult<Option<Batch>> {
196 if self.exhausted && self.current_left.is_none() {
197 return Ok(None);
198 }
199
200 let mut output = Vec::with_capacity(batch_size);
201 while output.len() < batch_size {
202 if self.current_left.is_none() {
203 match self.next_left()? {
204 Some(left) => self.begin_left_row(left)?,
205 None => {
206 self.exhausted = true;
207 break;
208 }
209 }
210 }
211
212 let next_right = self
213 .right_rows
214 .as_mut()
215 .and_then(Iterator::next)
216 .transpose()?;
217 if let Some(right) = next_right {
218 if !self.source.admits(&right)? {
219 continue;
220 }
221 let right = self.right_presence.owned_row(right)?;
222 let left = self.current_left.as_ref().ok_or_else(|| {
223 ExecError::Other(
224 "lateral join produced a right row without a current left row".into(),
225 )
226 })?;
227 let joined = OwnedPhysicalRow::new(
228 self.schema.clone(),
229 PhysicalRow::concat(&left.row, &right),
230 );
231 let matched =
232 matches!(self.kind, JoinKind::Cross) || self.source.matches(&joined)?;
233 if matched {
234 self.matched_left = true;
235 output.push(joined.row);
236 } else if matches!(self.kind, JoinKind::Right | JoinKind::Full) {
237 output.push(PhysicalRow::concat(
238 &PhysicalRow::nulls(self.left_schema.physical_width()),
239 &right,
240 ));
241 }
242 continue;
243 }
244
245 self.close_right()?;
246 if !self.matched_left && matches!(self.kind, JoinKind::Left | JoinKind::Full) {
247 let left = self.current_left.take().ok_or_else(|| {
248 ExecError::Other(
249 "lateral join completed a right stream without a current left row".into(),
250 )
251 })?;
252 output.push(PhysicalRow::concat(
253 &left.row,
254 &PhysicalRow::nulls(self.right_presence.schema.physical_width()),
255 ));
256 } else {
257 self.current_left = None;
258 }
259 }
260
261 if output.is_empty() {
262 return Ok(None);
263 }
264 Ok(Some(Batch::from_physical_rows(self.schema.clone(), output)))
265 }
266}
267
268impl PhysicalOperator for LateralJoin<'_> {
269 fn row_schema(&self) -> &RowSchema {
270 &self.schema
271 }
272
273 fn open(&mut self) -> ExecResult<()> {
274 self.left_rows = Vec::new().into_iter();
275 self.current_left = None;
276 self.close_right()?;
277 self.matched_left = false;
278 self.exhausted = false;
279 self.left.open()
280 }
281
282 fn next(&mut self) -> ExecResult<Option<Batch>> {
283 self.pull(DEFAULT_BATCH_SIZE)
284 }
285
286 fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
287 self.pull(rows.get().min(DEFAULT_BATCH_SIZE))
288 }
289
290 fn close(&mut self) -> ExecResult<()> {
291 self.left_rows = Vec::new().into_iter();
292 self.current_left = None;
293 let right = self.close_right();
294 let right =
295 crate::physical::with_cleanup(right, self.source.close(), "close lateral source");
296 self.matched_left = false;
297 self.exhausted = true;
298 crate::physical::with_cleanup(right, self.left.close(), "close lateral left input")
299 }
300}
301
302#[cfg(test)]
303mod tests {
304 use super::*;
305 use crate::physical::run_to_rows;
306 use crate::scan::TableScan;
307 use uqa_core::Value;
308
309 fn row(values: &[(&str, Value)]) -> ResultRow {
310 values
311 .iter()
312 .map(|(column, value)| ((*column).to_string(), value.clone()))
313 .collect()
314 }
315
316 fn right_row(value: i64) -> OwnedPhysicalRow {
317 let schema = RowSchema::new(vec!["r.n".into()]);
318 let row = PhysicalRow::from_values(vec![Value::Int(value)]);
319 OwnedPhysicalRow::new(schema, row)
320 }
321
322 struct RangeSource;
323
324 impl<'a> LateralSource<'a> for RangeSource {
325 fn rows_for(&mut self, left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>> {
326 let Value::Int(end) = left.get("l.n").cloned().unwrap_or(Value::Null) else {
327 return Ok(crate::SQLRowStream::new(std::iter::empty()));
328 };
329 Ok(crate::SQLRowStream::new(
330 (1..=end).map(|value| Ok(right_row(value))),
331 ))
332 }
333
334 fn admits(&mut self, _right: &OwnedPhysicalRow) -> ExecResult<bool> {
335 Ok(true)
336 }
337
338 fn matches(&mut self, joined: &OwnedPhysicalRow) -> ExecResult<bool> {
339 Ok(joined.get("r.n") == Some(&Value::Int(2)))
340 }
341 }
342
343 #[test]
344 fn left_lateral_preserves_a_left_row_without_an_on_match() {
345 let left = TableScan::from_rows(
346 vec!["l.n".into()],
347 vec![
348 row(&[("l.n", Value::Int(1))]),
349 row(&[("l.n", Value::Int(2))]),
350 ],
351 );
352 let mut join = LateralJoin::new(
353 Box::new(left),
354 Box::new(RangeSource),
355 JoinKind::Left,
356 row(&[("l.n", Value::Null)]),
357 row(&[("r.n", Value::Null)]),
358 );
359 let (_, rows) = run_to_rows(&mut join).unwrap();
360 assert_eq!(rows.len(), 2);
361 assert_eq!(rows[0].get("l.n"), Some(&Value::Int(1)));
362 assert_eq!(rows[0].get("r.n"), Some(&Value::Null));
363 assert_eq!(rows[1].get("l.n"), Some(&Value::Int(2)));
364 assert_eq!(rows[1].get("r.n"), Some(&Value::Int(2)));
365 }
366
367 struct RejectingRangeSource;
369
370 impl<'a> LateralSource<'a> for RejectingRangeSource {
371 fn rows_for(&mut self, left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>> {
372 RangeSource.rows_for(left)
373 }
374
375 fn admits(&mut self, right: &OwnedPhysicalRow) -> ExecResult<bool> {
376 Ok(right.get("r.n") != Some(&Value::Int(2)))
377 }
378
379 fn matches(&mut self, joined: &OwnedPhysicalRow) -> ExecResult<bool> {
380 RangeSource.matches(joined)
381 }
382 }
383
384 #[test]
386 fn rejected_right_rows_are_absent_from_inner_and_left_lateral_joins() {
387 let n = |value: i64| Value::Int(value);
388 for (kind, expected) in [
389 (JoinKind::Cross, vec![(n(1), n(1)), (n(2), n(1))]),
390 (JoinKind::Inner, Vec::new()),
391 (
392 JoinKind::Left,
393 vec![(n(1), Value::Null), (n(2), Value::Null)],
394 ),
395 ] {
396 let left = TableScan::from_rows(
397 vec!["l.n".into()],
398 vec![
399 row(&[("l.n", Value::Int(1))]),
400 row(&[("l.n", Value::Int(2))]),
401 ],
402 );
403 let mut join = LateralJoin::new(
404 Box::new(left),
405 Box::new(RejectingRangeSource),
406 kind,
407 row(&[("l.n", Value::Null)]),
408 row(&[("r.n", Value::Null)]),
409 );
410 let (_, rows) = run_to_rows(&mut join).unwrap();
411 let actual = rows
412 .iter()
413 .map(|row| (row["l.n"].clone(), row["r.n"].clone()))
414 .collect::<Vec<_>>();
415 assert_eq!(actual, expected, "{kind:?}");
416 }
417 }
418
419 struct LargeRangeSource;
420
421 impl<'a> LateralSource<'a> for LargeRangeSource {
422 fn rows_for(&mut self, _left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>> {
423 Ok(crate::SQLRowStream::new(
424 (0..10_000).map(|value| Ok(right_row(value))),
425 ))
426 }
427
428 fn admits(&mut self, _right: &OwnedPhysicalRow) -> ExecResult<bool> {
429 Ok(true)
430 }
431
432 fn matches(&mut self, _joined: &OwnedPhysicalRow) -> ExecResult<bool> {
433 Ok(true)
434 }
435 }
436
437 #[test]
438 fn large_correlated_relation_is_pulled_one_output_batch_at_a_time() {
439 let left = TableScan::from_rows(vec!["l.n".into()], vec![row(&[("l.n", Value::Int(1))])]);
440 let mut join = LateralJoin::new(
441 Box::new(left),
442 Box::new(LargeRangeSource),
443 JoinKind::Cross,
444 row(&[("l.n", Value::Null)]),
445 row(&[("r.n", Value::Null)]),
446 );
447 join.open().unwrap();
448 assert_eq!(join.next().unwrap().unwrap().len(), DEFAULT_BATCH_SIZE);
449 assert_eq!(join.next().unwrap().unwrap().len(), DEFAULT_BATCH_SIZE);
450 join.close().unwrap();
451 }
452
453 struct FailingSource;
454
455 impl<'a> LateralSource<'a> for FailingSource {
456 fn rows_for(&mut self, _left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>> {
457 Ok(crate::SQLRowStream::new(
458 vec![
459 Ok(right_row(1)),
460 Err(uqa_sql::SQLError::Internal(
461 "injected lateral failure".into(),
462 )),
463 ]
464 .into_iter(),
465 ))
466 }
467
468 fn admits(&mut self, _right: &OwnedPhysicalRow) -> ExecResult<bool> {
469 Ok(true)
470 }
471
472 fn matches(&mut self, _joined: &OwnedPhysicalRow) -> ExecResult<bool> {
473 Ok(true)
474 }
475 }
476
477 #[test]
478 fn late_correlated_source_error_is_propagated() {
479 let left = TableScan::from_rows(vec!["l.n".into()], vec![row(&[("l.n", Value::Int(1))])]);
480 let mut join = LateralJoin::new(
481 Box::new(left),
482 Box::new(FailingSource),
483 JoinKind::Cross,
484 row(&[("l.n", Value::Null)]),
485 row(&[("r.n", Value::Null)]),
486 );
487 join.open().unwrap();
488 let error = join.next().unwrap_err();
489 assert!(error.to_string().contains("injected lateral failure"));
490 }
491}
492
493#[cfg(test)]
494mod production_tests;