Skip to content

Commit 6cf7cb5

Browse files
authored
fix: preserve lambda bindings in nested-loop join projection pushdown (apache#26399)
## Which issue does this PR close? - Closes apache#26396. ## Rationale for this change A nested-loop join whose lambda captures a column from the other input can fail during physical optimization with `unable to unwrap lambda`, even though the query executes correctly with physical optimization disabled. These queries should work with the default optimizer while retaining projection pushdown for expressions that can be evaluated on one join input. ## What changes are included in this PR? - Keep each lambda and its body in the enclosing high-order function's scope when extracting join-filter expressions. Ordinary sibling expressions, other function arguments, and complete high-order expressions that depend on only one input remain eligible for pushdown. - Remap captured columns and rebase lambda parameter indices when moving an expression to an input projection, extending the intermediate filter schema, and pruning unused filter columns. Nested lambdas retain their relative parameter offsets and bindings. - Add `nested_loop_join_lambda.slt` with result and physical-plan regressions. This change preserves lambda bodies within their enclosing function; it does not introduce hoisting of individual computations from inside a lambda body. ## What is the testing strategy for this PR? The new SQL test covers the original reproducer with either join-input order, mixed predicates, nested lambdas, parameter shadowing, empty/NULL arrays, and extraction of complete high-order functions onto either input. Different input and filter schema widths exercise parameter rebasing. Three `EXPLAIN` checks verify that ordinary expressions and complete high-order functions are still pushed down. ## Are there any user-facing changes? Nested-loop joins with lambda predicates now plan and execute with the default physical optimizer. There are no public API or configuration changes.
1 parent fe612e2 commit 6cf7cb5

2 files changed

Lines changed: 275 additions & 41 deletions

File tree

‎datafusion/physical-optimizer/src/projection_pushdown.rs‎

Lines changed: 83 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -30,8 +30,8 @@ use datafusion_common::config::ConfigOptions;
3030
use datafusion_common::tree_node::{
3131
Transformed, TransformedResult, TreeNode, TreeNodeRecursion,
3232
};
33-
use datafusion_common::{JoinSide, JoinType, Result};
34-
use datafusion_physical_expr::expressions::Column;
33+
use datafusion_common::{JoinSide, JoinType, Result, internal_datafusion_err};
34+
use datafusion_physical_expr::expressions::{Column, LambdaExpr, LambdaVariable};
3535
use datafusion_physical_expr_common::physical_expr::{PhysicalExpr, is_volatile};
3636
use datafusion_physical_plan::ExecutionPlan;
3737
use datafusion_physical_plan::joins::NestedLoopJoinExec;
@@ -130,7 +130,7 @@ fn try_push_down_join_filter(
130130
rhs_rewrite.data.1.column_indices(),
131131
lhs_rewrite.data.0.schema().as_ref(),
132132
rhs_rewrite.data.0.schema().as_ref(),
133-
);
133+
)?;
134134

135135
let new_lhs_length = lhs_rewrite.data.0.schema().fields.len();
136136
let projections = match projections.as_ref() {
@@ -219,8 +219,14 @@ fn try_push_down_projection(
219219
})
220220
.collect::<Fields>();
221221

222-
let join_filter = JoinFilter::new(
222+
let expression = remap_filter_expr(
223223
new_expr.data,
224+
join_filter.schema().fields().len(),
225+
rewriter.intermediate_column_indices.len(),
226+
|column| Ok(column.clone()),
227+
)?;
228+
let join_filter = JoinFilter::new(
229+
expression,
224230
rewriter.intermediate_column_indices,
225231
Arc::new(Schema::new(intermediate_schema)),
226232
);
@@ -240,15 +246,14 @@ fn minimize_join_filter(
240246
old_column_indices: &[ColumnIndex],
241247
lhs_schema: &Schema,
242248
rhs_schema: &Schema,
243-
) -> JoinFilter {
249+
) -> Result<JoinFilter> {
244250
let mut used_columns = HashSet::with_capacity(old_column_indices.len());
245251
expr.apply(|expr| {
246252
if let Some(col) = expr.downcast_ref::<Column>() {
247253
used_columns.insert(col.index());
248254
}
249255
Ok(TreeNodeRecursion::Continue)
250-
})
251-
.expect("Closure cannot fail");
256+
})?;
252257

253258
let new_column_indices = old_column_indices
254259
.iter()
@@ -265,27 +270,24 @@ fn minimize_join_filter(
265270
})
266271
.collect::<Fields>();
267272

268-
let final_expr = expr
269-
.transform_up(|expr| match expr.downcast_ref::<Column>() {
270-
None => Ok(Transformed::no(expr)),
271-
Some(column) => {
272-
let new_idx = used_columns
273-
.iter()
274-
.filter(|idx| **idx < column.index())
275-
.count();
276-
let new_column = Column::new(column.name(), new_idx);
277-
Ok(Transformed::yes(
278-
Arc::new(new_column) as Arc<dyn PhysicalExpr>
279-
))
280-
}
281-
})
282-
.expect("Closure cannot fail");
273+
let final_expr = remap_filter_expr(
274+
expr,
275+
old_column_indices.len(),
276+
new_column_indices.len(),
277+
|column| {
278+
let new_idx = used_columns
279+
.iter()
280+
.filter(|idx| **idx < column.index())
281+
.count();
282+
Ok(Column::new(column.name(), new_idx))
283+
},
284+
)?;
283285

284-
JoinFilter::new(
285-
final_expr.data,
286+
Ok(JoinFilter::new(
287+
final_expr,
286288
new_column_indices,
287289
Arc::new(Schema::new(fields)),
288-
)
290+
))
289291
}
290292

291293
/// Implements the push-down machinery.
@@ -300,6 +302,7 @@ struct JoinFilterRewriter<'a> {
300302
join_side_schema: &'a Schema,
301303
join_side_projections: Vec<(Arc<dyn PhysicalExpr>, String)>,
302304
intermediate_column_indices: Vec<ColumnIndex>,
305+
original_filter_column_count: usize,
303306
alias_generator: &'a AliasGenerator,
304307
}
305308

@@ -327,6 +330,7 @@ impl<'a> JoinFilterRewriter<'a> {
327330
join_side,
328331
join_side_schema,
329332
join_side_projections: projections,
333+
original_filter_column_count: column_indices.len(),
330334
intermediate_column_indices: column_indices,
331335
alias_generator,
332336
}
@@ -339,6 +343,11 @@ impl<'a> JoinFilterRewriter<'a> {
339343
&mut self,
340344
expr: Arc<dyn PhysicalExpr>,
341345
) -> Result<Transformed<Arc<dyn PhysicalExpr>>> {
346+
// A lambda is evaluated by its enclosing high-order function. Keep its
347+
// body in that scope; a complete high-order function may still be moved.
348+
if expr.is::<LambdaExpr>() {
349+
return Ok(Transformed::no(expr));
350+
}
342351
let depends_on_this_side = self.depends_on_join_side(&expr, self.join_side)?;
343352
// We don't push down things that do not depend on this side (other side or no side).
344353
if !depends_on_this_side {
@@ -378,22 +387,21 @@ impl<'a> JoinFilterRewriter<'a> {
378387
// First, add a new projection. The expression must be rewritten, as it is no longer
379388
// executed against the filter schema.
380389
let new_idx = self.join_side_projections.len();
381-
let rewritten_expr = expr.transform_up(|expr| {
382-
Ok(match expr.downcast_ref::<Column>() {
383-
None => Transformed::no(expr),
384-
Some(column) => {
385-
let intermediate_column =
386-
&self.intermediate_column_indices[column.index()];
387-
assert_eq!(intermediate_column.side, self.join_side);
388-
389-
let join_side_index = intermediate_column.index;
390-
let field = self.join_side_schema.field(join_side_index);
391-
let new_column = Column::new(field.name(), join_side_index);
392-
Transformed::yes(Arc::new(new_column) as Arc<dyn PhysicalExpr>)
393-
}
394-
})
395-
})?;
396-
self.join_side_projections.push((rewritten_expr.data, name));
390+
let rewritten_expr = remap_filter_expr(
391+
expr,
392+
self.original_filter_column_count,
393+
self.join_side_schema.fields().len(),
394+
|column| {
395+
let intermediate_column =
396+
&self.intermediate_column_indices[column.index()];
397+
assert_eq!(intermediate_column.side, self.join_side);
398+
399+
let join_side_index = intermediate_column.index;
400+
let field = self.join_side_schema.field(join_side_index);
401+
Ok(Column::new(field.name(), join_side_index))
402+
},
403+
)?;
404+
self.join_side_projections.push((rewritten_expr, name));
397405

398406
// Then, update the column indices
399407
let new_intermediate_idx = self.intermediate_column_indices.len();
@@ -420,6 +428,40 @@ impl<'a> JoinFilterRewriter<'a> {
420428
}
421429
}
422430

431+
/// Remaps captured columns and rebases lambda parameters when the input changes.
432+
/// Parameters are appended after the input columns, including at nested lambda
433+
/// scopes. Moving a complete high-order expression preserves their relative
434+
/// offsets, so every parameter shifts by the change in the root input width.
435+
fn remap_filter_expr(
436+
expr: Arc<dyn PhysicalExpr>,
437+
old_input_len: usize,
438+
new_input_len: usize,
439+
map_column: impl Fn(&Column) -> Result<Column>,
440+
) -> Result<Arc<dyn PhysicalExpr>> {
441+
expr.transform_up(|expr| {
442+
if let Some(column) = expr.downcast_ref::<Column>() {
443+
let new_column = map_column(column)?;
444+
if new_column != *column {
445+
return Ok(Transformed::yes(Arc::new(new_column) as _));
446+
}
447+
} else if let Some(variable) = expr.downcast_ref::<LambdaVariable>()
448+
&& old_input_len != new_input_len
449+
{
450+
let offset = variable.index().checked_sub(old_input_len).ok_or_else(|| {
451+
internal_datafusion_err!(
452+
"Lambda parameter {variable} precedes the {old_input_len} input columns"
453+
)
454+
})?;
455+
return Ok(Transformed::yes(Arc::new(LambdaVariable::new(
456+
new_input_len + offset,
457+
Arc::clone(variable.field()),
458+
)) as _));
459+
}
460+
Ok(Transformed::no(expr))
461+
})
462+
.data()
463+
}
464+
423465
#[cfg(test)]
424466
mod test {
425467
use super::*;
Lines changed: 192 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,192 @@
1+
# Licensed to the Apache Software Foundation (ASF) under one
2+
# or more contributor license agreements. See the NOTICE file
3+
# distributed with this work for additional information
4+
# regarding copyright ownership. The ASF licenses this file
5+
# to you under the Apache License, Version 2.0 (the
6+
# "License"); you may not use this file except in compliance
7+
# with the License. You may obtain a copy of the License at
8+
#
9+
# http://www.apache.org/licenses/LICENSE-2.0
10+
#
11+
# Unless required by applicable law or agreed to in writing,
12+
# software distributed under the License is distributed on an
13+
# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
# KIND, either express or implied. See the License for the
15+
# specific language governing permissions and limitations
16+
# under the License.
17+
18+
# Regression for https://github.com/apache/datafusion/issues/26396.
19+
statement ok
20+
SET datafusion.sql_parser.dialect = 'duckdb'
21+
22+
statement ok
23+
SET datafusion.execution.target_partitions = 1
24+
25+
statement ok
26+
SET datafusion.optimizer.join_reordering = false
27+
28+
statement ok
29+
CREATE TABLE lambda_lists AS
30+
SELECT * FROM (VALUES
31+
([1, 30], 'a', 7, 2),
32+
([40], 'b', 8, 4),
33+
([], 'empty', 9, 2),
34+
(NULL, 'null', 10, 2)
35+
) AS v(items, k, n, threshold)
36+
37+
statement ok
38+
CREATE TABLE lambda_cutoffs AS
39+
SELECT * FROM (VALUES (25, -3), (5, -1)) AS v(cutoff, score)
40+
41+
# The lambda captures a column from the opposite join input.
42+
query TI
43+
SELECT s.k, s.n
44+
FROM (SELECT 25 AS cutoff) c
45+
JOIN lambda_lists s ON array_any_match(s.items, x -> x < c.cutoff)
46+
----
47+
a 7
48+
49+
query TI
50+
SELECT s.k, s.n
51+
FROM lambda_lists s
52+
JOIN (SELECT 25 AS cutoff) c ON array_any_match(s.items, x -> x < c.cutoff)
53+
----
54+
a 7
55+
56+
# Extract ordinary expressions from both inputs while preserving the lambda.
57+
# Growing and then pruning the filter schema must also rebase its parameters.
58+
query ITI rowsort
59+
SELECT c.cutoff, s.k, s.n
60+
FROM lambda_cutoffs c JOIN lambda_lists s
61+
ON array_any_match(s.items, x -> x < c.cutoff)
62+
AND abs(c.score) > abs(s.threshold)
63+
----
64+
25 a 7
65+
66+
# The outer high-order function spans both inputs. Its array argument is a
67+
# complete single-input high-order function that can still be projected out.
68+
query IT rowsort
69+
SELECT c.cutoff, s.k
70+
FROM lambda_cutoffs c JOIN lambda_lists s
71+
ON array_any_match(array_transform(s.items, y -> y + 1), x -> x < c.cutoff)
72+
AND abs(c.score) > abs(s.threshold)
73+
----
74+
25 a
75+
76+
# Nested lambdas capture both a join column and the outer lambda's parameter.
77+
query IT rowsort
78+
SELECT c.cutoff, s.k
79+
FROM lambda_cutoffs c JOIN lambda_lists s
80+
ON array_any_match(s.items,
81+
x -> array_any_match(s.items, y -> y <= x AND x < c.cutoff))
82+
AND abs(c.score) > abs(s.threshold)
83+
----
84+
25 a
85+
86+
# Shadowed names and an unused outer parameter must keep their own bindings.
87+
query IT rowsort
88+
SELECT c.cutoff, s.k
89+
FROM lambda_cutoffs c JOIN lambda_lists s
90+
ON array_any_match(s.items,
91+
x -> array_any_match(s.items, x -> x < c.cutoff))
92+
AND abs(c.score) > abs(s.threshold)
93+
----
94+
25 a
95+
96+
# Projecting an entire high-order function is valid when its inputs and
97+
# captures all belong to one side. Selected payload columns widen that input
98+
# beyond the filter's schema, exercising rebasing into the input projection.
99+
query ITII rowsort
100+
SELECT c.cutoff, s.k, s.n, s.threshold
101+
FROM lambda_cutoffs c JOIN lambda_lists s
102+
ON CAST(array_any_match(s.items, x -> x < s.n) AS BIGINT) < abs(c.score)
103+
----
104+
25 a 7 2
105+
25 b 8 4
106+
25 empty 9 2
107+
5 b 8 4
108+
5 empty 9 2
109+
110+
# The same single-side extraction with nested lambdas and an outer capture.
111+
query ITII rowsort
112+
SELECT c.cutoff, s.k, s.n, s.threshold
113+
FROM lambda_cutoffs c JOIN lambda_lists s
114+
ON CAST(array_any_match(s.items,
115+
x -> array_any_match(s.items, y -> y <= x AND x < s.n)) AS BIGINT) < abs(c.score)
116+
----
117+
25 a 7 2
118+
25 b 8 4
119+
25 empty 9 2
120+
5 b 8 4
121+
5 empty 9 2
122+
123+
# Extract the complete function on the left input as well.
124+
query ITII rowsort
125+
SELECT c.cutoff, s.k, s.n, s.threshold
126+
FROM lambda_lists s JOIN lambda_cutoffs c
127+
ON CAST(array_any_match(s.items, x -> x < s.n) AS BIGINT) < abs(c.score)
128+
----
129+
25 a 7 2
130+
25 b 8 4
131+
25 empty 9 2
132+
5 b 8 4
133+
5 empty 9 2
134+
135+
statement ok
136+
SET datafusion.explain.physical_plan_only = true
137+
138+
# Both abs expressions must still be pushed below the join.
139+
query TT
140+
EXPLAIN SELECT c.cutoff, s.k, s.n
141+
FROM lambda_cutoffs c JOIN lambda_lists s
142+
ON array_any_match(s.items, x -> x < c.cutoff)
143+
AND abs(c.score) > abs(s.threshold)
144+
----
145+
physical_plan
146+
01)ProjectionExec: expr=[cutoff@0 as cutoff, k@3 as k, n@4 as n]
147+
02)--NestedLoopJoinExec: join_type=Inner, filter=array_any_match(items@1, (x) -> x@4 < cutoff@0) AND join_proj_push_down_1@2 > join_proj_push_down_2@3, projection=[cutoff@0, score@1, items@3, k@4, n@5, threshold@6]
148+
03)----ProjectionExec: expr=[cutoff@0 as cutoff, score@1 as score, abs(score@1) as join_proj_push_down_1]
149+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
150+
05)----ProjectionExec: expr=[items@0 as items, k@1 as k, n@2 as n, threshold@3 as threshold, abs(threshold@3) as join_proj_push_down_2]
151+
06)------DataSourceExec: partitions=1, partition_sizes=[1]
152+
153+
# A whole high-order function is still eligible for projection pushdown.
154+
query TT
155+
EXPLAIN SELECT c.cutoff, s.k, s.n, s.threshold
156+
FROM lambda_cutoffs c JOIN lambda_lists s
157+
ON CAST(array_any_match(s.items, x -> x < s.n) AS BIGINT) < abs(c.score)
158+
----
159+
physical_plan
160+
01)ProjectionExec: expr=[cutoff@0 as cutoff, k@3 as k, n@4 as n, threshold@5 as threshold]
161+
02)--NestedLoopJoinExec: join_type=Inner, filter=join_proj_push_down_2@1 < join_proj_push_down_1@0, projection=[cutoff@0, score@1, items@3, k@4, n@5, threshold@6]
162+
03)----ProjectionExec: expr=[cutoff@0 as cutoff, score@1 as score, abs(score@1) as join_proj_push_down_1]
163+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
164+
05)----ProjectionExec: expr=[items@0 as items, k@1 as k, n@2 as n, threshold@3 as threshold, CAST(array_any_match(items@0, (x) -> x@4 < n@2) AS Int64) as join_proj_push_down_2]
165+
06)------DataSourceExec: partitions=1, partition_sizes=[1]
166+
167+
# The array argument may be extracted without extracting either lambda body.
168+
query TT
169+
EXPLAIN SELECT c.cutoff, s.k
170+
FROM lambda_cutoffs c JOIN lambda_lists s
171+
ON array_any_match(array_transform(s.items, y -> y + 1), x -> x < c.cutoff)
172+
AND abs(c.score) > abs(s.threshold)
173+
----
174+
physical_plan
175+
01)ProjectionExec: expr=[cutoff@0 as cutoff, k@3 as k]
176+
02)--NestedLoopJoinExec: join_type=Inner, filter=array_any_match(join_proj_push_down_2@2, (x) -> x@4 < cutoff@0) AND join_proj_push_down_1@1 > join_proj_push_down_3@3, projection=[cutoff@0, score@1, items@3, k@4, threshold@5]
177+
03)----ProjectionExec: expr=[cutoff@0 as cutoff, score@1 as score, abs(score@1) as join_proj_push_down_1]
178+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
179+
05)----ProjectionExec: expr=[items@0 as items, k@1 as k, threshold@2 as threshold, array_transform(items@0, (y) -> y@3 + 1) as join_proj_push_down_2, abs(threshold@2) as join_proj_push_down_3]
180+
06)------DataSourceExec: partitions=1, partition_sizes=[1]
181+
182+
statement ok
183+
RESET datafusion.explain.physical_plan_only
184+
185+
statement ok
186+
SET datafusion.execution.target_partitions = 4
187+
188+
statement ok
189+
RESET datafusion.optimizer.join_reordering
190+
191+
statement ok
192+
RESET datafusion.sql_parser.dialect

0 commit comments

Comments
 (0)