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_sql::ast::JoinKind;
10use uqa_sql::ResultRow;
11
12use crate::batch::DEFAULT_BATCH_SIZE;
13use crate::{
14    Batch, ExecError, ExecResult, OwnedPhysicalRow, PhysicalOperator, PhysicalRow, RowSchema,
15};
16
17/// Execution source for a correlated right-hand relation.
18///
19/// 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.
20pub type LateralRows<'a> = crate::SQLRowStream<'a, OwnedPhysicalRow>;
21
22pub trait LateralSource<'a>: Send {
23    fn rows_for(&mut self, left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>>;
24
25    /// 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.
26    fn admits(&mut self, right: &OwnedPhysicalRow) -> ExecResult<bool>;
27
28    fn matches(&mut self, joined: &OwnedPhysicalRow) -> ExecResult<bool>;
29
30    /// Release a source prepared while binding its runtime descriptor, even
31    /// when the consumer never requests the first joined row.
32    fn close(&mut self) -> ExecResult<()> {
33        Ok(())
34    }
35}
36
37fn output_schema(
38    left: &RowSchema,
39    right: &RowSchema,
40    left_nulls: &ResultRow,
41    right_nulls: &ResultRow,
42) -> RowSchema {
43    RowSchema::join(
44        left,
45        right,
46        left_nulls.keys().chain(right_nulls.keys()).cloned(),
47    )
48}
49
50/// Streaming physical implementation of a SQL `LATERAL` join.
51///
52/// The left child is pulled in batches. The correlated right relation is
53/// evaluated once per left row, and produced rows are drained in bounded
54/// output batches instead of materialising the complete join result.
55pub struct LateralJoin<'a> {
56    left: Box<dyn PhysicalOperator + 'a>,
57    source: Box<dyn LateralSource<'a> + 'a>,
58    kind: JoinKind,
59    schema: RowSchema,
60    left_schema: RowSchema,
61    right_presence: crate::join::presence::NullableRow,
62    left_rows: std::vec::IntoIter<OwnedPhysicalRow>,
63    current_left: Option<OwnedPhysicalRow>,
64    right_rows: Option<LateralRows<'a>>,
65    matched_left: bool,
66    exhausted: bool,
67}
68
69impl<'a> LateralJoin<'a> {
70    pub fn new(
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    ) -> Self {
77        let right_schema = RowSchema::new(right_nulls.keys().cloned().collect());
78        Self::new_with_right_schema(left, source, kind, left_nulls, right_nulls, right_schema)
79    }
80
81    pub fn new_with_right_schema(
82        left: Box<dyn PhysicalOperator + 'a>,
83        source: Box<dyn LateralSource<'a> + 'a>,
84        kind: JoinKind,
85        left_nulls: ResultRow,
86        right_nulls: ResultRow,
87        right_schema: RowSchema,
88    ) -> Self {
89        let left =
90            crate::join::presence::input(left, matches!(kind, JoinKind::Right | JoinKind::Full));
91        let right_presence = crate::join::presence::NullableRow::new(
92            &right_schema,
93            matches!(kind, JoinKind::Left | JoinKind::Full),
94        );
95        let schema = output_schema(
96            left.row_schema(),
97            &right_presence.schema,
98            &left_nulls,
99            &right_nulls,
100        );
101        let left_schema = left.row_schema().clone();
102        Self {
103            left,
104            source,
105            kind,
106            schema,
107            left_schema,
108            right_presence,
109            left_rows: Vec::new().into_iter(),
110            current_left: None,
111            right_rows: None,
112            matched_left: false,
113            exhausted: false,
114        }
115    }
116
117    fn next_left(&mut self) -> ExecResult<Option<OwnedPhysicalRow>> {
118        loop {
119            if let Some(row) = self.left_rows.next() {
120                return Ok(Some(row));
121            }
122            let Some(batch) = self.left.next_with_demand(crate::physical::demand::ONE)? else {
123                return Ok(None);
124            };
125            self.left_rows = batch.into_owned_rows().into_iter();
126        }
127    }
128
129    fn begin_left_row(&mut self, left: OwnedPhysicalRow) -> ExecResult<()> {
130        self.right_rows = Some(self.source.rows_for(&left)?);
131        self.current_left = Some(left);
132        self.matched_left = false;
133        Ok(())
134    }
135}
136
137impl LateralJoin<'_> {
138    fn close_right(&mut self) -> ExecResult<()> {
139        self.right_rows
140            .take()
141            .map_or(Ok(()), |mut rows| rows.close().map_err(Into::into))
142    }
143
144    fn pull(&mut self, batch_size: usize) -> ExecResult<Option<Batch>> {
145        if self.exhausted && self.current_left.is_none() {
146            return Ok(None);
147        }
148
149        let mut output = Vec::with_capacity(batch_size);
150        while output.len() < batch_size {
151            if self.current_left.is_none() {
152                match self.next_left()? {
153                    Some(left) => self.begin_left_row(left)?,
154                    None => {
155                        self.exhausted = true;
156                        break;
157                    }
158                }
159            }
160
161            let next_right = self
162                .right_rows
163                .as_mut()
164                .and_then(Iterator::next)
165                .transpose()?;
166            if let Some(right) = next_right {
167                if !self.source.admits(&right)? {
168                    continue;
169                }
170                let right = self.right_presence.owned_row(right)?;
171                let left = self.current_left.as_ref().ok_or_else(|| {
172                    ExecError::Other(
173                        "lateral join produced a right row without a current left row".into(),
174                    )
175                })?;
176                let joined = OwnedPhysicalRow::new(
177                    self.schema.clone(),
178                    PhysicalRow::concat(&left.row, &right),
179                );
180                let matched =
181                    matches!(self.kind, JoinKind::Cross) || self.source.matches(&joined)?;
182                if matched {
183                    self.matched_left = true;
184                    output.push(joined.row);
185                } else if matches!(self.kind, JoinKind::Right | JoinKind::Full) {
186                    output.push(PhysicalRow::concat(
187                        &PhysicalRow::nulls(self.left_schema.physical_width()),
188                        &right,
189                    ));
190                }
191                continue;
192            }
193
194            self.close_right()?;
195            if !self.matched_left && matches!(self.kind, JoinKind::Left | JoinKind::Full) {
196                let left = self.current_left.take().ok_or_else(|| {
197                    ExecError::Other(
198                        "lateral join completed a right stream without a current left row".into(),
199                    )
200                })?;
201                output.push(PhysicalRow::concat(
202                    &left.row,
203                    &PhysicalRow::nulls(self.right_presence.schema.physical_width()),
204                ));
205            } else {
206                self.current_left = None;
207            }
208        }
209
210        if output.is_empty() {
211            return Ok(None);
212        }
213        Ok(Some(Batch::from_physical_rows(self.schema.clone(), output)))
214    }
215}
216
217impl PhysicalOperator for LateralJoin<'_> {
218    fn row_schema(&self) -> &RowSchema {
219        &self.schema
220    }
221
222    fn open(&mut self) -> ExecResult<()> {
223        self.left_rows = Vec::new().into_iter();
224        self.current_left = None;
225        self.close_right()?;
226        self.matched_left = false;
227        self.exhausted = false;
228        self.left.open()
229    }
230
231    fn next(&mut self) -> ExecResult<Option<Batch>> {
232        self.pull(DEFAULT_BATCH_SIZE)
233    }
234
235    fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
236        self.pull(rows.get().min(DEFAULT_BATCH_SIZE))
237    }
238
239    fn close(&mut self) -> ExecResult<()> {
240        self.left_rows = Vec::new().into_iter();
241        self.current_left = None;
242        let right = self.close_right();
243        let right =
244            crate::physical::with_cleanup(right, self.source.close(), "close lateral source");
245        self.matched_left = false;
246        self.exhausted = true;
247        crate::physical::with_cleanup(right, self.left.close(), "close lateral left input")
248    }
249}
250
251#[cfg(test)]
252mod tests {
253    use super::*;
254    use crate::physical::run_to_rows;
255    use crate::scan::TableScan;
256    use uqa_core::Value;
257
258    fn row(values: &[(&str, Value)]) -> ResultRow {
259        values
260            .iter()
261            .map(|(column, value)| ((*column).to_string(), value.clone()))
262            .collect()
263    }
264
265    fn right_row(value: i64) -> OwnedPhysicalRow {
266        let schema = RowSchema::new(vec!["r.n".into()]);
267        let row = PhysicalRow::from_values(vec![Value::Int(value)]);
268        OwnedPhysicalRow::new(schema, row)
269    }
270
271    struct RangeSource;
272
273    impl<'a> LateralSource<'a> for RangeSource {
274        fn rows_for(&mut self, left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>> {
275            let Value::Int(end) = left.get("l.n").cloned().unwrap_or(Value::Null) else {
276                return Ok(crate::SQLRowStream::new(std::iter::empty()));
277            };
278            Ok(crate::SQLRowStream::new(
279                (1..=end).map(|value| Ok(right_row(value))),
280            ))
281        }
282
283        fn admits(&mut self, _right: &OwnedPhysicalRow) -> ExecResult<bool> {
284            Ok(true)
285        }
286
287        fn matches(&mut self, joined: &OwnedPhysicalRow) -> ExecResult<bool> {
288            Ok(joined.get("r.n") == Some(&Value::Int(2)))
289        }
290    }
291
292    #[test]
293    fn left_lateral_preserves_a_left_row_without_an_on_match() {
294        let left = TableScan::from_rows(
295            vec!["l.n".into()],
296            vec![
297                row(&[("l.n", Value::Int(1))]),
298                row(&[("l.n", Value::Int(2))]),
299            ],
300        );
301        let mut join = LateralJoin::new(
302            Box::new(left),
303            Box::new(RangeSource),
304            JoinKind::Left,
305            row(&[("l.n", Value::Null)]),
306            row(&[("r.n", Value::Null)]),
307        );
308        let (_, rows) = run_to_rows(&mut join).unwrap();
309        assert_eq!(rows.len(), 2);
310        assert_eq!(rows[0].get("l.n"), Some(&Value::Int(1)));
311        assert_eq!(rows[0].get("r.n"), Some(&Value::Null));
312        assert_eq!(rows[1].get("l.n"), Some(&Value::Int(2)));
313        assert_eq!(rows[1].get("r.n"), Some(&Value::Int(2)));
314    }
315
316    /// The right relation `1..=l.n` with `r.n <> 2` placed on it, joined on `r.n = 2`.
317    struct RejectingRangeSource;
318
319    impl<'a> LateralSource<'a> for RejectingRangeSource {
320        fn rows_for(&mut self, left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>> {
321            RangeSource.rows_for(left)
322        }
323
324        fn admits(&mut self, right: &OwnedPhysicalRow) -> ExecResult<bool> {
325            Ok(right.get("r.n") != Some(&Value::Int(2)))
326        }
327
328        fn matches(&mut self, joined: &OwnedPhysicalRow) -> ExecResult<bool> {
329            RangeSource.matches(joined)
330        }
331    }
332
333    /// 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.
334    #[test]
335    fn rejected_right_rows_are_absent_from_inner_and_left_lateral_joins() {
336        let n = |value: i64| Value::Int(value);
337        for (kind, expected) in [
338            (JoinKind::Cross, vec![(n(1), n(1)), (n(2), n(1))]),
339            (JoinKind::Inner, Vec::new()),
340            (
341                JoinKind::Left,
342                vec![(n(1), Value::Null), (n(2), Value::Null)],
343            ),
344        ] {
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(RejectingRangeSource),
355                kind,
356                row(&[("l.n", Value::Null)]),
357                row(&[("r.n", Value::Null)]),
358            );
359            let (_, rows) = run_to_rows(&mut join).unwrap();
360            let actual = rows
361                .iter()
362                .map(|row| (row["l.n"].clone(), row["r.n"].clone()))
363                .collect::<Vec<_>>();
364            assert_eq!(actual, expected, "{kind:?}");
365        }
366    }
367
368    struct LargeRangeSource;
369
370    impl<'a> LateralSource<'a> for LargeRangeSource {
371        fn rows_for(&mut self, _left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>> {
372            Ok(crate::SQLRowStream::new(
373                (0..10_000).map(|value| Ok(right_row(value))),
374            ))
375        }
376
377        fn admits(&mut self, _right: &OwnedPhysicalRow) -> ExecResult<bool> {
378            Ok(true)
379        }
380
381        fn matches(&mut self, _joined: &OwnedPhysicalRow) -> ExecResult<bool> {
382            Ok(true)
383        }
384    }
385
386    #[test]
387    fn large_correlated_relation_is_pulled_one_output_batch_at_a_time() {
388        let left = TableScan::from_rows(vec!["l.n".into()], vec![row(&[("l.n", Value::Int(1))])]);
389        let mut join = LateralJoin::new(
390            Box::new(left),
391            Box::new(LargeRangeSource),
392            JoinKind::Cross,
393            row(&[("l.n", Value::Null)]),
394            row(&[("r.n", Value::Null)]),
395        );
396        join.open().unwrap();
397        assert_eq!(join.next().unwrap().unwrap().len(), DEFAULT_BATCH_SIZE);
398        assert_eq!(join.next().unwrap().unwrap().len(), DEFAULT_BATCH_SIZE);
399        join.close().unwrap();
400    }
401
402    struct FailingSource;
403
404    impl<'a> LateralSource<'a> for FailingSource {
405        fn rows_for(&mut self, _left: &OwnedPhysicalRow) -> ExecResult<LateralRows<'a>> {
406            Ok(crate::SQLRowStream::new(
407                vec![
408                    Ok(right_row(1)),
409                    Err(uqa_sql::SQLError::Internal(
410                        "injected lateral failure".into(),
411                    )),
412                ]
413                .into_iter(),
414            ))
415        }
416
417        fn admits(&mut self, _right: &OwnedPhysicalRow) -> ExecResult<bool> {
418            Ok(true)
419        }
420
421        fn matches(&mut self, _joined: &OwnedPhysicalRow) -> ExecResult<bool> {
422            Ok(true)
423        }
424    }
425
426    #[test]
427    fn late_correlated_source_error_is_propagated() {
428        let left = TableScan::from_rows(vec!["l.n".into()], vec![row(&[("l.n", Value::Int(1))])]);
429        let mut join = LateralJoin::new(
430            Box::new(left),
431            Box::new(FailingSource),
432            JoinKind::Cross,
433            row(&[("l.n", Value::Null)]),
434            row(&[("r.n", Value::Null)]),
435        );
436        join.open().unwrap();
437        let error = join.next().unwrap_err();
438        assert!(error.to_string().contains("injected lateral failure"));
439    }
440}