Skip to main content

uqa_execution/
lateral_join.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Correlated physical join operator.
8
9use 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
18/// Execution source for a correlated right-hand relation.
19///
20/// The physical operator owns join iteration, `ON` filtering, and outer-row preservation. The source only evaluates the right relation, the predicates placed on that relation, and the scalar join predicate in the current correlated scope.
21pub 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    /// Whether a produced right row satisfies the predicates placed on the right relation itself. A rejected row is absent from the join input: it neither matches a left row nor produces a NULL-extended row.
27    fn admits(&mut self, right: &OwnedPhysicalRow) -> ExecResult<bool>;
28
29    fn matches(&mut self, joined: &OwnedPhysicalRow) -> ExecResult<bool>;
30
31    /// Release a source prepared while binding its runtime descriptor, even
32    /// when the consumer never requests the first joined row.
33    fn close(&mut self) -> ExecResult<()> {
34        Ok(())
35    }
36}
37
38/// Streaming physical implementation of a SQL `LATERAL` join.
39///
40/// The left child is pulled in batches. The correlated right relation is
41/// evaluated once per left row, and produced rows are drained in bounded
42/// output batches instead of materialising the complete join result.
43pub 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    /// The right relation `1..=l.n` with `r.n <> 2` placed on it, joined on `r.n = 2`.
368    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    /// The planner places conjuncts on the right relation of inner and cross joins, and propagates join-key constants into the right relation of a left join, whose left rows then lose every rejected match.
385    #[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;