Skip to content

Commit c76ed53

Browse files
authored
fix: Correct ANY/ALL results for unaliased subqueries on the same table (apache#25273)
## Which issue does this PR close? - Closes apache#25258. ## Rationale for this change During the various decorrelation passes, stripping outer references too early makes the outer and inner columns indistinguishable. Both operands are then rewritten to reference the subquery, turning the join predicate into a comparison of an inner column with itself (something like col1 > col1). ## What changes are included in this PR? Its mostly a minor change in where we strip the outer column reference from the join filter in the optimizer. ## What is the testing strategy for this PR? New SLT tests provided in the initial issue, asserting both results and logical plan shape. ## Are there any user-facing changes? Depreciating the `find_join_exprs` which isn't called internally anymore, replacing it with a helper function in `decorrelate.rs`. --------- Signed-off-by: Adam Gutglick <[email protected]>
1 parent a79a694 commit c76ed53

6 files changed

Lines changed: 271 additions & 35 deletions

File tree

‎datafusion/expr/src/utils.rs‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1505,6 +1505,10 @@ pub fn add_filter(plan: LogicalPlan, predicates: &[&Expr]) -> Result<LogicalPlan
15051505
/// # Return value
15061506
///
15071507
/// Tuple of (expressions containing joins, remaining non-join expressions)
1508+
#[deprecated(
1509+
since = "56.0.0",
1510+
note = "This decorrelation helper is intended for internal optimizer use and has no public replacement"
1511+
)]
15081512
pub fn find_join_exprs(exprs: Vec<&Expr>) -> Result<(Vec<Expr>, Vec<Expr>)> {
15091513
let mut joins = vec![];
15101514
let mut others = vec![];

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 94 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ use std::sync::Arc;
2222

2323
use crate::push_down_filter::lr_is_preserved;
2424
use crate::simplify_expressions::ExprSimplifier;
25+
use crate::utils::replace_qualified_name;
2526

2627
use datafusion_common::nested_struct::is_injective_cast;
2728
use datafusion_common::tree_node::{
@@ -33,11 +34,10 @@ use datafusion_common::{
3334
plan_err,
3435
};
3536
use datafusion_expr::expr::{Alias, GroupingSet};
37+
use datafusion_expr::expr_rewriter::strip_outer_reference;
3638
use datafusion_expr::logical_plan::{Join, JoinType};
3739
use datafusion_expr::simplify::SimplifyContext;
38-
use datafusion_expr::utils::{
39-
collect_subquery_cols, conjunction, find_join_exprs, split_conjunction,
40-
};
40+
use datafusion_expr::utils::{collect_subquery_cols, conjunction, split_conjunction};
4141
use datafusion_expr::{
4242
Aggregate, BinaryExpr, Cast, Distinct, EmptyRelation, Expr, ExprSchemable, Extension,
4343
FetchType, LogicalPlan, LogicalPlanBuilder, MaterializedCte, Operator, SkipType,
@@ -408,7 +408,7 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
408408
}
409409
}
410410
let (mut join_filters, subquery_filters) =
411-
find_join_exprs(subquery_filter_exprs)?;
411+
find_join_exprs(subquery_filter_exprs);
412412
if let Some(in_predicate) = &self.in_predicate_opt {
413413
// in_predicate may be already included in the join filters, remove it from the join filters first.
414414
join_filters = remove_duplicated_filter(join_filters, in_predicate)?;
@@ -1124,6 +1124,60 @@ fn collect_local_correlated_cols(
11241124
}
11251125
}
11261126

1127+
/// Extracts correlated predicates, such as a comparison between a column from the
1128+
/// subquery and a column from the outer scope.
1129+
///
1130+
/// Preserves [`Expr::OuterReferenceColumn`] markers so callers can distinguish
1131+
/// inner and outer columns when qualifying join filters (see [`build_join_filter`]).
1132+
///
1133+
/// # Arguments
1134+
///
1135+
/// * `exprs` - Subquery filter predicates to classify.
1136+
///
1137+
/// # Return value
1138+
///
1139+
/// Tuple of (correlated join filters, remaining subquery filters). Correlated
1140+
/// self-equalities are discarded from both lists.
1141+
pub(crate) fn find_join_exprs(exprs: Vec<&Expr>) -> (Vec<Expr>, Vec<Expr>) {
1142+
let mut joins = vec![];
1143+
let mut others = vec![];
1144+
for filter in exprs {
1145+
// Predicates containing outer references become join filters.
1146+
if filter.contains_outer() {
1147+
// Compare with the outer-reference markers intact: inner and outer
1148+
// columns with the same qualified name belong to different scopes.
1149+
if !matches!(filter, Expr::BinaryExpr(BinaryExpr { left, op: Operator::Eq, right }) if left.eq(right))
1150+
{
1151+
joins.push(filter.clone());
1152+
}
1153+
} else {
1154+
others.push(filter.clone());
1155+
}
1156+
}
1157+
(joins, others)
1158+
}
1159+
1160+
/// Combines join filters and qualifies their inner columns with the subquery alias.
1161+
///
1162+
/// Aliasing must precede stripping outer references so inner and outer columns
1163+
/// with the same qualified name remain distinguishable.
1164+
pub(crate) fn build_join_filter<'a>(
1165+
join_filters: Vec<Expr>,
1166+
correlated_cols: impl IntoIterator<Item = &'a Column>,
1167+
subquery_alias: &str,
1168+
) -> Result<Option<Expr>> {
1169+
let correlated_cols = correlated_cols
1170+
.into_iter()
1171+
.cloned()
1172+
.collect::<BTreeSet<_>>();
1173+
conjunction(join_filters)
1174+
.map(|filter| {
1175+
replace_qualified_name(filter, &correlated_cols, subquery_alias)
1176+
.map(strip_outer_reference)
1177+
})
1178+
.transpose()
1179+
}
1180+
11271181
fn remove_duplicated_filter(
11281182
filters: Vec<Expr>,
11291183
in_predicate: &Expr,
@@ -1141,6 +1195,7 @@ fn remove_duplicated_filter(
11411195
Ok(filters
11421196
.into_iter()
11431197
.filter(|filter| {
1198+
let filter = &strip_outer_reference(filter.clone());
11441199
if filter == in_predicate {
11451200
return false;
11461201
}
@@ -1305,3 +1360,38 @@ fn filter_exprs_evaluation_result_on_empty_batch(
13051360
};
13061361
Ok(pull_up_expr)
13071362
}
1363+
1364+
#[cfg(test)]
1365+
mod tests {
1366+
use super::*;
1367+
use arrow::datatypes::DataType;
1368+
use datafusion_expr::{col, out_ref_col};
1369+
1370+
#[test]
1371+
fn test_find_join_exprs_preserves_outer_references() {
1372+
let outer = out_ref_col(DataType::Int32, "t.a");
1373+
let correlated = col("t.a").eq(outer.clone());
1374+
let self_equality = outer.clone().eq(outer);
1375+
let local = col("t.b").gt(lit(2));
1376+
1377+
assert_eq!(
1378+
find_join_exprs(vec![&correlated, &self_equality, &local]),
1379+
(vec![correlated], vec![local])
1380+
);
1381+
}
1382+
1383+
#[test]
1384+
fn test_build_join_filter() -> Result<()> {
1385+
assert_eq!(build_join_filter(vec![], [], "sq")?, None);
1386+
1387+
let column = Column::from("t.a");
1388+
let outer = out_ref_col(DataType::Int32, "t.a");
1389+
let filters = vec![col("t.a").eq(outer.clone()), outer.gt(lit(1))];
1390+
1391+
assert_eq!(
1392+
build_join_filter(filters, [&column, &column], "sq")?,
1393+
Some(col("sq.a").eq(col("t.a")).and(col("t.a").gt(lit(1))))
1394+
);
1395+
Ok(())
1396+
}
1397+
}

‎datafusion/optimizer/src/decorrelate_lateral_join.rs‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ use crate::decorrelate::{PullUpCorrelatedExpr, UN_MATCHED_ROW_INDICATOR};
2323
use crate::optimizer::ApplyOrder;
2424
use crate::utils::evaluates_to_null;
2525
use crate::{OptimizerConfig, OptimizerRule};
26+
use datafusion_expr::expr_rewriter::strip_outer_reference;
2627
use datafusion_expr::{Expr, Join, expr};
2728

2829
use datafusion_common::tree_node::{
@@ -149,6 +150,8 @@ fn rewrite_internal(join: Join) -> Result<Transformed<LogicalPlan>> {
149150
(rewritten_subquery, correlation_filter, original_join_filter)
150151
};
151152

153+
let correlation_filter = correlation_filter.map(strip_outer_reference);
154+
152155
// For LEFT lateral joins, verify that all column references in the
153156
// correlation filter are resolvable within the join's left and right
154157
// schemas. If the lateral subquery references columns from an outer scope,

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 41 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -21,10 +21,11 @@ use std::ops::Deref;
2121
use std::sync::Arc;
2222

2323
use crate::analyzer::type_coercion::TypeCoercionRewriter;
24-
use crate::decorrelate::{PullUpCorrelatedExpr, UN_MATCHED_ROW_INDICATOR};
24+
use crate::decorrelate::{
25+
PullUpCorrelatedExpr, UN_MATCHED_ROW_INDICATOR, build_join_filter,
26+
};
2527
use crate::extract_equijoin_predicate::split_eq_and_noneq_join_predicate;
2628
use crate::optimizer::ApplyOrder;
27-
use crate::utils::replace_qualified_name;
2829
use crate::{OptimizerConfig, OptimizerRule};
2930

3031
use datafusion_common::alias::AliasGenerator;
@@ -772,7 +773,11 @@ fn subquery_operands_are_bare_columns(
772773
filter
773774
.apply(|e| {
774775
let refs = e.column_refs();
775-
if !refs.is_empty() && refs.iter().all(|c| subquery_cols.contains(*c)) {
776+
// `column_refs` skips outer references, which the join filters keep, so check them separately.
777+
if !refs.is_empty()
778+
&& !e.contains_outer()
779+
&& refs.iter().all(|c| subquery_cols.contains(*c))
780+
{
776781
bare = matches!(e, Expr::Column(_));
777782
return Ok(if bare {
778783
TreeNodeRecursion::Jump
@@ -853,17 +858,11 @@ fn build_join(
853858
let sub_query_alias = LogicalPlanBuilder::from(new_plan)
854859
.alias(alias.to_string())?
855860
.build()?;
856-
let mut all_correlated_cols = BTreeSet::new();
857-
pull_up
858-
.correlated_subquery_cols_map
859-
.values()
860-
.for_each(|cols| all_correlated_cols.extend(cols.iter().cloned()));
861-
862-
// alias the join filter
863-
let join_filter_opt = conjunction(pull_up.join_filters)
864-
.map_or(Ok(None), |filter| {
865-
replace_qualified_name(filter, &all_correlated_cols, alias).map(Some)
866-
})?;
861+
let join_filter_opt = build_join_filter(
862+
pull_up.join_filters,
863+
pull_up.correlated_subquery_cols_map.values().flatten(),
864+
alias,
865+
)?;
867866

868867
if let Some(expr_map) = count_bug_compensation
869868
&& !expr_map.is_empty()
@@ -2662,6 +2661,34 @@ mod tests {
26622661
)
26632662
}
26642663

2664+
#[test]
2665+
fn in_subquery_correlated_with_same_table() -> Result<()> {
2666+
let outer_scan = test_table_scan()?;
2667+
let subquery_scan = test_table_scan()?;
2668+
let subquery = LogicalPlanBuilder::from(subquery_scan)
2669+
.filter(out_ref_col(DataType::UInt32, "test.a").gt(col("test.a")))?
2670+
.project(vec![col("c")])?
2671+
.build()?;
2672+
2673+
let plan = LogicalPlanBuilder::from(outer_scan)
2674+
.filter(in_subquery(col("test.b"), Arc::new(subquery)))?
2675+
.project(vec![col("test.b")])?
2676+
.build()?;
2677+
2678+
// The outer `test.a` and the subquery's `test.a` stay apart in the join filter.
2679+
assert_optimized_plan_equal!(
2680+
plan,
2681+
@r"
2682+
Projection: test.b [b:UInt32]
2683+
LeftSemi Join: Filter: test.b = __correlated_sq_1.c AND test.a > __correlated_sq_1.a [a:UInt32, b:UInt32, c:UInt32]
2684+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
2685+
SubqueryAlias: __correlated_sq_1 [c:UInt32, a:UInt32]
2686+
Projection: test.c, test.a [c:UInt32, a:UInt32]
2687+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
2688+
"
2689+
)
2690+
}
2691+
26652692
/// Test for multiple exists subqueries in the same filter expression
26662693
#[test]
26672694
fn multiple_exists_subqueries() -> Result<()> {

‎datafusion/optimizer/src/scalar_subquery_to_join.rs‎

Lines changed: 10 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -17,12 +17,14 @@
1717

1818
//! [`ScalarSubqueryToJoin`] rewriting scalar subquery filters to `JOIN`s
1919
20-
use std::collections::{BTreeSet, HashMap};
20+
use std::collections::HashMap;
2121
use std::sync::Arc;
2222

23-
use crate::decorrelate::{PullUpCorrelatedExpr, UN_MATCHED_ROW_INDICATOR};
23+
use crate::decorrelate::{
24+
PullUpCorrelatedExpr, UN_MATCHED_ROW_INDICATOR, build_join_filter,
25+
};
2426
use crate::optimizer::ApplyOrder;
25-
use crate::utils::{evaluates_to_null, replace_qualified_name};
27+
use crate::utils::evaluates_to_null;
2628
use crate::{OptimizerConfig, OptimizerRule};
2729

2830
use crate::analyzer::type_coercion::TypeCoercionRewriter;
@@ -33,7 +35,6 @@ use datafusion_common::tree_node::{
3335
use datafusion_common::{Column, Result, ScalarValue, assert_or_internal_err, plan_err};
3436
use datafusion_expr::expr_rewriter::create_col_from_scalar_expr;
3537
use datafusion_expr::logical_plan::{JoinType, Subquery};
36-
use datafusion_expr::utils::conjunction;
3738
use datafusion_expr::{Expr, LogicalPlan, LogicalPlanBuilder, lit, not, when};
3839

3940
/// Optimizer rule that rewrites scalar subquery filters to joins and places an
@@ -361,19 +362,11 @@ fn build_join(
361362
.alias(subquery_alias.to_string())?
362363
.build()?;
363364

364-
let all_correlated_cols: BTreeSet<Column> = pull_up
365-
.correlated_subquery_cols_map
366-
.values()
367-
.flatten()
368-
.cloned()
369-
.collect();
370-
371-
// Correlated columns now live in the decorrelated subquery's output,
372-
// so re-qualify them with the subquery alias.
373-
let join_filter_opt =
374-
conjunction(pull_up.join_filters).map_or(Ok(None), |filter| {
375-
replace_qualified_name(filter, &all_correlated_cols, subquery_alias).map(Some)
376-
})?;
365+
let join_filter_opt = build_join_filter(
366+
pull_up.join_filters,
367+
pull_up.correlated_subquery_cols_map.values().flatten(),
368+
subquery_alias,
369+
)?;
377370

378371
// When pull-up did not extract any usable join keys (a correlated subquery
379372
// whose predicate references only outer columns), fall back to `ON true`:

0 commit comments

Comments
 (0)