Skip to content

Commit cee7bae

Browse files
authored
Support predicate subqueries in projections (apache#24972)
## Which issue does this PR close? - Closes apache#23022. ## Rationale for this change Predicate subqueries such as `EXISTS`, `IN`, and `NOT IN` are valid scalar expressions in a `SELECT` list, but DataFusion currently only decorrelates them when they appear in filters. Projection queries therefore reach physical planning with an unsupported logical subquery expression. This continues the work from the now-closed stale apache#23039 and covers multiple and correlated projection subqueries as well as SQL null semantics. ## What changes are included in this PR? - decorrelate `EXISTS`, `NOT EXISTS`, `IN`, and `NOT IN` expressions inside projections into mark joins - materialize projected `IN`/`NOT IN` values with SQL three-valued logic by tracking matches, nulls, and empty subqueries - preserve projection output names and avoid duplicate columns in correlated subquery projections ## What is the testing strategy for this PR? Optimizer plan tests cover projected `IN` rewriting. New SQLLogicTest cases cover uncorrelated and correlated `EXISTS`/`IN`, multiple subqueries in one projection, empty inputs, null inputs, and `NOT IN` three-valued logic. Locally validated with: - `cargo test -p datafusion-optimizer decorrelate_predicate_subquery` (53 passed) - `cargo test -p datafusion-sqllogictest --test sqllogictests -- subquery_projection` - `cargo clippy -p datafusion-optimizer --all-targets --all-features -- -D warnings` - `cargo fmt --all -- --check` ## Are there any user-facing changes? Yes. Predicate subqueries can now be evaluated as projected scalar expressions. There are no public API changes.
1 parent 3a6a18c commit cee7bae

4 files changed

Lines changed: 280 additions & 27 deletions

File tree

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 158 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -29,16 +29,16 @@ use crate::{OptimizerConfig, OptimizerRule};
2929
use datafusion_common::alias::AliasGenerator;
3030
use datafusion_common::tree_node::{Transformed, TransformedResult, TreeNode};
3131
use datafusion_common::{
32-
Column, DFSchemaRef, ExprSchema, NullEquality, Result, assert_or_internal_err,
33-
plan_err,
32+
Column, DFSchemaRef, ExprSchema, NullEquality, Result, ScalarValue,
33+
assert_or_internal_err, plan_err,
3434
};
3535
use datafusion_expr::expr::{Exists, InSubquery};
3636
use datafusion_expr::expr_rewriter::create_col_from_scalar_expr;
3737
use datafusion_expr::logical_plan::{JoinType, Subquery};
3838
use datafusion_expr::utils::{conjunction, expr_to_columns, split_conjunction_owned};
3939
use datafusion_expr::{
4040
BinaryExpr, Expr, Filter, LogicalPlan, LogicalPlanBuilder, Operator, exists,
41-
in_subquery, lit, not, not_exists, not_in_subquery,
41+
in_subquery, lit, not, not_exists, not_in_subquery, when,
4242
};
4343

4444
use log::debug;
@@ -70,6 +70,37 @@ impl OptimizerRule for DecorrelatePredicateSubquery {
7070
})?
7171
.data;
7272

73+
if let LogicalPlan::Projection(projection) = plan {
74+
if !projection.expr.iter().any(has_subquery) {
75+
return Ok(Transformed::no(LogicalPlan::Projection(projection)));
76+
}
77+
78+
let original_projection = projection.clone();
79+
let mut cur_input = Arc::unwrap_or_clone(projection.input);
80+
let mut rewritten_exprs = Vec::with_capacity(projection.expr.len());
81+
for expr in projection.expr {
82+
let original_name = expr.schema_name().to_string();
83+
let (new_input, mut rewritten_expr) =
84+
rewrite_inner_subqueries(cur_input, expr, config, true)?;
85+
if has_subquery(&rewritten_expr) {
86+
return Ok(Transformed::no(LogicalPlan::Projection(
87+
original_projection,
88+
)));
89+
}
90+
cur_input = new_input;
91+
92+
if rewritten_expr.schema_name().to_string() != original_name {
93+
rewritten_expr = rewritten_expr.alias(original_name);
94+
}
95+
rewritten_exprs.push(rewritten_expr);
96+
}
97+
98+
let new_plan = LogicalPlanBuilder::from(cur_input)
99+
.project(rewritten_exprs)?
100+
.build()?;
101+
return Ok(Transformed::yes(new_plan));
102+
}
103+
73104
let LogicalPlan::Filter(filter) = plan else {
74105
return Ok(Transformed::no(plan));
75106
};
@@ -105,7 +136,7 @@ impl OptimizerRule for DecorrelatePredicateSubquery {
105136
// The subquery expression is embedded within another expression
106137
SubqueryPredicate::Embedded(expr) => {
107138
let (plan, expr_without_subqueries) =
108-
rewrite_inner_subqueries(cur_input, expr, config)?;
139+
rewrite_inner_subqueries(cur_input, expr, config, false)?;
109140
cur_input = plan;
110141
other_exprs.push(expr_without_subqueries);
111142
}
@@ -140,6 +171,7 @@ fn rewrite_inner_subqueries(
140171
outer: LogicalPlan,
141172
expr: Expr,
142173
config: &dyn OptimizerConfig,
174+
materialize_in_value: bool,
143175
) -> Result<(LogicalPlan, Expr)> {
144176
let mut cur_input = outer;
145177
let alias = config.alias_generator();
@@ -160,12 +192,23 @@ fn rewrite_inner_subqueries(
160192
subquery: Subquery { subquery, .. },
161193
negated,
162194
}) => {
163-
let in_predicate = subquery
164-
.head_output_expr()?
165-
.map_or(plan_err!("single expression required."), |output_expr| {
166-
Ok(Expr::eq(*expr.clone(), output_expr))
167-
})?;
168-
match mark_join(&cur_input, &subquery, Some(&in_predicate), negated, alias)? {
195+
let rewritten = if materialize_in_value {
196+
in_subquery_value_mark_join(
197+
&cur_input,
198+
&subquery,
199+
*expr.clone(),
200+
negated,
201+
alias,
202+
)?
203+
} else {
204+
let in_predicate = subquery
205+
.head_output_expr()?
206+
.map_or(plan_err!("single expression required."), |output_expr| {
207+
Ok(Expr::eq(*expr.clone(), output_expr))
208+
})?;
209+
mark_join(&cur_input, &subquery, Some(&in_predicate), negated, alias)?
210+
};
211+
match rewritten {
169212
Some((plan, exists_expr)) => {
170213
cur_input = plan;
171214
Ok(Transformed::yes(exists_expr))
@@ -179,6 +222,48 @@ fn rewrite_inner_subqueries(
179222
Ok((cur_input, expr_without_subqueries.data))
180223
}
181224

225+
fn in_subquery_value_mark_join(
226+
left: &LogicalPlan,
227+
subquery: &LogicalPlan,
228+
expr: Expr,
229+
negated: bool,
230+
alias: &Arc<AliasGenerator>,
231+
) -> Result<Option<(LogicalPlan, Expr)>> {
232+
let output_expr = subquery
233+
.head_output_expr()?
234+
.map_or(plan_err!("single expression required."), Ok)?;
235+
let in_predicate = Expr::eq(expr.clone(), output_expr.clone());
236+
let Some((matched_plan, matched)) =
237+
mark_join(left, subquery, Some(&in_predicate), false, alias)?
238+
else {
239+
return Ok(None);
240+
};
241+
242+
// SQL IN needs three facts per outer row to distinguish FALSE from UNKNOWN.
243+
let null_subquery = LogicalPlanBuilder::from(subquery.clone())
244+
.filter(output_expr.is_null())?
245+
.build()?;
246+
let Some((null_plan, subquery_has_null)) =
247+
mark_join(&matched_plan, &null_subquery, None, false, alias)?
248+
else {
249+
return Ok(None);
250+
};
251+
let Some((final_plan, subquery_non_empty)) =
252+
mark_join(&null_plan, subquery, None, false, alias)?
253+
else {
254+
return Ok(None);
255+
};
256+
257+
let unknown = subquery_has_null.or(expr.is_null().and(subquery_non_empty));
258+
let result = when(matched, lit(true))
259+
.when(unknown, lit(ScalarValue::Boolean(None)))
260+
.otherwise(lit(false))?;
261+
Ok(Some((
262+
final_plan,
263+
if negated { not(result) } else { result },
264+
)))
265+
}
266+
182267
enum SubqueryPredicate {
183268
// The subquery expression is at the top level of the filter and can be fully replaced by a
184269
// semi/anti join
@@ -428,16 +513,17 @@ fn build_join(
428513

429514
// Keep only columns that actually belong to the RIGHT child, and sort by their
430515
// position in the right schema for deterministic order.
431-
let mut right_cols_idx_and_col: Vec<(usize, Column)> = needed
516+
let mut right_col_indices: Vec<usize> = needed
432517
.into_iter()
433-
.filter_map(|c| right_schema.index_of_column(&c).ok().map(|idx| (idx, c)))
518+
.filter_map(|column| right_schema.index_of_column(&column).ok())
434519
.collect();
435520

436-
right_cols_idx_and_col.sort_by_key(|(idx, _)| *idx);
521+
right_col_indices.sort_unstable();
522+
right_col_indices.dedup();
437523

438-
let right_proj_exprs: Vec<Expr> = right_cols_idx_and_col
524+
let right_proj_exprs: Vec<Expr> = right_col_indices
439525
.into_iter()
440-
.map(|(_, c)| Expr::Column(c))
526+
.map(|index| Expr::Column(Column::from(right_schema.qualified_field(index))))
441527
.collect();
442528

443529
let right_projected = if !right_proj_exprs.is_empty() {
@@ -1203,6 +1289,63 @@ mod tests {
12031289
)
12041290
}
12051291

1292+
#[test]
1293+
fn in_subquery_in_projection() -> Result<()> {
1294+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
1295+
.project(vec![
1296+
in_subquery(col("c"), test_subquery_with_name("sq")?).alias("is_present"),
1297+
])?
1298+
.build()?;
1299+
1300+
assert_optimized_plan_equal!(
1301+
plan,
1302+
@r"
1303+
Projection: CASE WHEN __correlated_sq_1.mark THEN Boolean(true) WHEN __correlated_sq_2.mark OR test.c IS NULL AND __correlated_sq_3.mark THEN Boolean(NULL) ELSE Boolean(false) END AS is_present [is_present:Boolean;N]
1304+
LeftMark Join: Filter: Boolean(true) [a:UInt32, b:UInt32, c:UInt32, mark:Boolean;N, mark:Boolean;N, mark:Boolean;N]
1305+
LeftMark Join: Filter: Boolean(true) [a:UInt32, b:UInt32, c:UInt32, mark:Boolean;N, mark:Boolean;N]
1306+
LeftMark Join: Filter: test.c = __correlated_sq_1.c [a:UInt32, b:UInt32, c:UInt32, mark:Boolean;N]
1307+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
1308+
Projection: __correlated_sq_1.c [c:UInt32]
1309+
SubqueryAlias: __correlated_sq_1 [c:UInt32]
1310+
Projection: sq.c [c:UInt32]
1311+
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
1312+
SubqueryAlias: __correlated_sq_2 [c:UInt32]
1313+
Filter: sq.c IS NULL [c:UInt32]
1314+
Projection: sq.c [c:UInt32]
1315+
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
1316+
SubqueryAlias: __correlated_sq_3 [c:UInt32]
1317+
Projection: sq.c [c:UInt32]
1318+
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
1319+
"
1320+
)
1321+
}
1322+
1323+
#[test]
1324+
fn unsupported_correlated_in_projection_is_left_unchanged() -> Result<()> {
1325+
let subquery = Arc::new(
1326+
LogicalPlanBuilder::from(scan_tpch_table("orders"))
1327+
.filter(
1328+
out_ref_col(DataType::Int64, "customer.c_custkey")
1329+
.eq(col("orders.o_custkey")),
1330+
)?
1331+
.limit(0, Some(1))?
1332+
.project(vec![col("orders.o_custkey")])?
1333+
.build()?,
1334+
);
1335+
let plan = LogicalPlanBuilder::from(scan_tpch_table("customer"))
1336+
.project(vec![
1337+
in_subquery(col("customer.c_custkey"), subquery).alias("is_present"),
1338+
])?
1339+
.build()?;
1340+
1341+
let result = DecorrelatePredicateSubquery::new()
1342+
.rewrite(plan.clone(), &crate::OptimizerContext::new())?;
1343+
1344+
assert!(!result.transformed);
1345+
assert_eq!(result.data, plan);
1346+
Ok(())
1347+
}
1348+
12061349
/// Test for single NOT IN subquery filter
12071350
#[test]
12081351
fn not_in_subquery_simple() -> Result<()> {

‎datafusion/sqllogictest/test_files/predicates.slt‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1008,12 +1008,14 @@ explain select x from t where x NOT IN (1,2,3,4,5) AND x IN (1,2,3);
10081008
logical_plan EmptyRelation: rows=0
10091009
physical_plan EmptyExec
10101010

1011-
query error DataFusion error: This feature is not implemented: Physical plan does not support logical expression InSubquery\(InSubquery \{ expr: Literal\(Int64\(NULL\), None\), subquery: <subquery>, negated: false \}\)
1011+
query BB
10121012
WITH empty AS (SELECT 10 WHERE false)
10131013
SELECT
10141014
NULL IN (SELECT * FROM empty), -- should be false, as the right side is empty relation
10151015
NULL NOT IN (SELECT * FROM empty) -- should be true, as the right side is empty relation
10161016
FROM (SELECT 1) t;
1017+
----
1018+
false true
10171019

10181020
query I
10191021
WITH empty AS (SELECT 10 WHERE false)

‎datafusion/sqllogictest/test_files/projection_pushdown.slt‎

Lines changed: 20 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -2295,11 +2295,11 @@ SET datafusion.execution.target_partitions = 4;
22952295
# Without the fix, extraction reuses `__datafusion_extracted_1` and planning
22962296
# aborts with: Optimizer rule 'push_down_leaf_projections' failed Schema error:
22972297
# Schema contains duplicate unqualified field name __datafusion_extracted_1.
2298-
# With the fix, the generator starts at 2, as the plan below shows.
2298+
# With the fix, generated aliases remain distinct, as the plan below shows.
22992299
#
2300-
# This is `EXPLAIN` under `logical_plan_only` rather than an executed query
2301-
# because a surviving `InSubquery` expression has no physical plan; the logical
2302-
# plan is both the observable result and exactly what regressed.
2300+
# Keep this as `EXPLAIN` under `logical_plan_only`: the logical plan exposes both
2301+
# the collision-free extracted aliases and the mark joins used to preserve the
2302+
# three-valued semantics of `IN` in a projection.
23032303
#####################
23042304

23052305
statement ok
@@ -2321,13 +2321,22 @@ SELECT
23212321
FROM simple_struct;
23222322
----
23232323
logical_plan
2324-
01)Projection: simple_struct.id, simple_struct.id IN (<subquery>) AS has_matching_label
2325-
02)--Subquery:
2326-
03)----Projection: simple_struct.id
2327-
04)------Filter: __datafusion_extracted_2 > Int64(120) AND __datafusion_extracted_1 != Utf8("delta")
2328-
05)--------Projection: get_field(simple_struct.s, Utf8("value")) AS __datafusion_extracted_2, simple_struct.id, get_field(simple_struct.s, Utf8("label")) AS __datafusion_extracted_1
2329-
06)----------TableScan: simple_struct projection=[id, s], partial_filters=[get_field(simple_struct.s, Utf8("value")) > Int64(120)]
2330-
07)--TableScan: simple_struct projection=[id]
2324+
01)Projection: simple_struct.id, __correlated_sq_1.mark IS NOT DISTINCT FROM Boolean(true) OR __correlated_sq_2.mark IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_1.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS has_matching_label
2325+
02)--LeftMark Join:
2326+
03)----LeftMark Join:
2327+
04)------LeftMark Join: simple_struct.id = __correlated_sq_1.id
2328+
05)--------TableScan: simple_struct projection=[id]
2329+
06)--------SubqueryAlias: __correlated_sq_1
2330+
07)----------Projection: simple_struct.id
2331+
08)------------Filter: __datafusion_extracted_4 > Int64(120) AND __datafusion_extracted_1 != Utf8("delta")
2332+
09)--------------Projection: get_field(simple_struct.s, Utf8("value")) AS __datafusion_extracted_4, simple_struct.id, get_field(simple_struct.s, Utf8("label")) AS __datafusion_extracted_1
2333+
10)----------------TableScan: simple_struct projection=[id, s], partial_filters=[get_field(simple_struct.s, Utf8("value")) > Int64(120)]
2334+
11)------EmptyRelation: rows=0
2335+
12)----SubqueryAlias: __correlated_sq_3
2336+
13)------Projection: simple_struct.id
2337+
14)--------Filter: __datafusion_extracted_6 > Int64(120) AND __datafusion_extracted_1 != Utf8("delta")
2338+
15)----------Projection: get_field(simple_struct.s, Utf8("value")) AS __datafusion_extracted_6, simple_struct.id, get_field(simple_struct.s, Utf8("label")) AS __datafusion_extracted_1
2339+
16)------------TableScan: simple_struct projection=[id, s], partial_filters=[Boolean(true), get_field(simple_struct.s, Utf8("value")) > Int64(120)]
23312340

23322341
statement ok
23332342
set datafusion.explain.logical_plan_only = false;

0 commit comments

Comments
 (0)