1use 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
17pub 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 fn admits(&mut self, right: &OwnedPhysicalRow) -> ExecResult<bool>;
27
28 fn matches(&mut self, joined: &OwnedPhysicalRow) -> ExecResult<bool>;
29
30 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
50pub 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 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 #[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}