Skip to content

Commit a9fc673

Browse files
compheadadriangb
andauthored
feat: decorrelate a window below a correlated equality filter (apache#26013)
## Which issue does this PR close? - Closes apache#25897. ## Rationale for this change Since apache#25838, a correlated filter below a window function keeps the subquery correlated unless the filter reads only `PARTITION BY` columns. Such queries fail with "Physical plan does not support logical expression ...". For example (apache#25792): ```sql SELECT t1.id, sub.id, sub.rn FROM t1, LATERAL ( SELECT t2.id, row_number() OVER (ORDER BY t2.id) AS rn FROM (SELECT * FROM t2 WHERE t2.t1_id = t1.id) AS t2 ) AS sub; ``` ## What changes are included in this PR? When every correlated conjunct has the form `col = <outer expr>`, the filter keeps the rows of one `col` value for each outer row. `PullUpCorrelatedExpr` then adds `col` to the `PARTITION BY` of every window function and pulls the filter above the window, as Spark (`DecorrelateInnerQuery`) and DuckDB (`FlattenDependentJoins`) do. Each extended window expression is aliased to its old name, so the output schema does not change. The subquery stays correlated when: - the outer expression is volatile. - `col` has a float leaf. `-0.0 = 0.0` holds, but a partition keeps the two apart. - a conjunct casts `col` with a lossy cast. A lossy cast lets several `col` values match one outer row, which is apache#26014. Widening casts that keep distinct values distinct are accepted through `is_injective_cast`, which was a private Map key helper in `datafusion-common`. - an aggregate without `GROUP BY` sits below the window. It returns a row for an outer row without a match, which the pulled up filter would drop. A Projection over a count bug aggregate now records the expressions that read no column, such as `1 AS x`, in `collected_count_expr_map`. Before, such a Projection dropped the entry. A scalar subquery then returned NULL instead of `1` for an outer row without a match, and the window guard above did not see the aggregate. The core of the change is @adriangb's commit 1a2ad03, which apache#25838 reverted to stay a bug fix. ## What is the testing strategy for this PR? - `subquery.slt` and `lateral_join.slt`: the window cases from apache#25838 that expected an error now check results, plus an `EXPLAIN` that shows `PARTITION BY [b.y]`. - New cases that stay correlated: a lossy `CAST`, a float column with signed zeros, a volatile outer expression, and a window over an aggregate without `GROUP BY` behind a Projection, `DISTINCT` or a Filter, or in an `EXISTS`, `NOT EXISTS`, `IN` or `LATERAL` subquery. - New cases with results: a widening cast, a lower window that already outputs the extended name, a constant projected over a count bug aggregate, and a window over a grouped aggregate. ## Are there any user-facing changes? Queries with a correlated equality below a window function now run instead of failing with a not-implemented error. A scalar subquery that projects a constant over a correlated aggregate now returns the constant for outer rows without a match, instead of NULL. `datafusion_common::nested_struct::is_injective_cast` is now public. --------- Co-authored-by: Adrian Garcia Badaracco <[email protected]>
1 parent 3e6058d commit a9fc673

4 files changed

Lines changed: 260 additions & 71 deletions

File tree

‎datafusion/common/src/nested_struct.rs‎

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -903,7 +903,7 @@ fn validate_map_key_data_type(
903903
}
904904
Ok(())
905905
}
906-
_ if is_injective_map_key_cast(source_type, target_type) => Ok(()),
906+
_ if is_injective_cast(source_type, target_type) => Ok(()),
907907
_ => _plan_err!(
908908
"Cannot safely evolve Map key type from {} to {}",
909909
source_type,
@@ -912,15 +912,15 @@ fn validate_map_key_data_type(
912912
}
913913
}
914914

915-
/// Returns true when casting a Map key from `source_type` to `target_type` is
916-
/// known to preserve key identity.
915+
/// Returns true when casting from `source_type` to `target_type` is known to
916+
/// preserve value identity, so distinct source values stay distinct.
917917
///
918-
/// Keep this list conservative. Map keys define equality/lookup identity, so
919-
/// only representation widenings that cannot merge distinct source keys belong
920-
/// here. Other Arrow-supported casts, including decimal/timestamp widening and
921-
/// dictionaries, should stay rejected until their identity semantics are
922-
/// deliberately reviewed.
923-
fn is_injective_map_key_cast(source_type: &DataType, target_type: &DataType) -> bool {
918+
/// Keep this list conservative. Map keys and decorrelated equality keys depend
919+
/// on identity, so only representation widenings that cannot merge distinct
920+
/// source values belong here. Other Arrow-supported casts, including
921+
/// decimal/timestamp widening and dictionaries, should stay rejected until
922+
/// their identity semantics are deliberately reviewed.
923+
pub fn is_injective_cast(source_type: &DataType, target_type: &DataType) -> bool {
924924
matches!(
925925
(source_type, target_type),
926926
(
@@ -2283,14 +2283,14 @@ mod tests {
22832283
(DataType::UInt16, DataType::Int64),
22842284
(DataType::UInt32, DataType::Int64),
22852285
] {
2286-
assert!(is_injective_map_key_cast(&source_type, &target_type));
2286+
assert!(is_injective_cast(&source_type, &target_type));
22872287
}
22882288
for (source_type, target_type) in [
22892289
(DataType::UInt8, DataType::Int8),
22902290
(DataType::UInt16, DataType::Int16),
22912291
(DataType::UInt32, DataType::Int32),
22922292
] {
2293-
assert!(!is_injective_map_key_cast(&source_type, &target_type));
2293+
assert!(!is_injective_cast(&source_type, &target_type));
22942294
}
22952295
}
22962296

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 117 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -23,11 +23,14 @@ use std::sync::Arc;
2323
use crate::push_down_filter::lr_is_preserved;
2424
use crate::simplify_expressions::ExprSimplifier;
2525

26+
use datafusion_common::nested_struct::is_injective_cast;
2627
use datafusion_common::tree_node::{
2728
Transformed, TransformedResult, TreeNode, TreeNodeRecursion, TreeNodeRewriter,
2829
};
30+
use datafusion_common::utils::has_float_leaf;
2931
use datafusion_common::{
30-
Column, DFSchemaRef, HashMap, Result, ScalarValue, assert_or_internal_err, plan_err,
32+
Column, DFSchema, DFSchemaRef, HashMap, Result, ScalarValue, assert_or_internal_err,
33+
plan_err,
3134
};
3235
use datafusion_expr::expr::{Alias, GroupingSet};
3336
use datafusion_expr::logical_plan::{Join, JoinType};
@@ -38,7 +41,7 @@ use datafusion_expr::utils::{
3841
use datafusion_expr::{
3942
Aggregate, BinaryExpr, Cast, Distinct, EmptyRelation, Expr, ExprSchemable, Extension,
4043
FetchType, LogicalPlan, LogicalPlanBuilder, MaterializedCte, Operator, SkipType,
41-
UserDefinedLogicalNodeCore, expr, lit,
44+
UserDefinedLogicalNodeCore, Window, expr, lit,
4245
};
4346

4447
/// This struct rewrite the sub query plan by pull up the correlated
@@ -59,6 +62,10 @@ pub struct PullUpCorrelatedExpr {
5962
/// Indicates if we encounter any correlated expression that can not be pulled up
6063
/// above a aggregation without changing the meaning of the query.
6164
can_pull_over_aggregation: bool,
65+
/// Whether every correlated conjunct seen so far passes
66+
/// [`is_partitionable_equality`], so a Window above them can partition by their
67+
/// columns.
68+
can_extend_partition_by: bool,
6269
/// Do we need to handle [the count bug] during the pull up process.
6370
///
6471
/// The "count bug" was described in [Optimization of Nested SQL
@@ -117,6 +124,7 @@ impl PullUpCorrelatedExpr {
117124
exists_sub_query: false,
118125
can_pull_up: true,
119126
can_pull_over_aggregation: true,
127+
can_extend_partition_by: true,
120128
need_handle_count_bug: false,
121129
collected_count_expr_map: HashMap::new(),
122130
pull_up_having_expr: None,
@@ -321,7 +329,9 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
321329
// outer row. A non-equality filter can return duplicates, see
322330
// https://github.com/apache/datafusion/issues/25808.
323331
// - A Window keeps or drops whole partitions when the filter reads
324-
// only its `PARTITION BY` columns. `f_up` checks this.
332+
// only its `PARTITION BY` columns. For other filters, `f_up` adds
333+
// the columns of a column equality to `PARTITION BY` and keeps
334+
// the subquery correlated in the remaining cases.
325335
// - An Unnest maps each input row to its own output rows, so a
326336
// filter on a column it passes through keeps the same rows.
327337
// The arm above checks that the filter does not read an unnested
@@ -384,11 +394,11 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
384394
match &plan {
385395
LogicalPlan::Filter(plan_filter) => {
386396
let subquery_filter_exprs = split_conjunction(&plan_filter.predicate);
387-
self.can_pull_over_aggregation = self.can_pull_over_aggregation
388-
&& subquery_filter_exprs
389-
.iter()
390-
.filter(|e| e.contains_outer())
391-
.all(|&e| can_pullup_over_aggregation(e));
397+
for &expr in subquery_filter_exprs.iter().filter(|e| e.contains_outer()) {
398+
self.can_pull_over_aggregation &= can_pullup_over_aggregation(expr);
399+
self.can_extend_partition_by &=
400+
is_partitionable_equality(expr, plan_filter.input.schema());
401+
}
392402
for expr in &subquery_filter_exprs {
393403
if expr.contains_outer() && !self.correlated_filters.contains(expr) {
394404
self.correlated_filters.push((*expr).clone());
@@ -713,6 +723,16 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
713723
.iter()
714724
.all(|expr| partitions_by_all(expr, &local_correlated_cols))
715725
{
726+
// `inner.y = outer.k` keeps the rows of one `y` value for
727+
// each outer row, so partitioning by `y` as well gives each
728+
// window function the same rows. An aggregate without
729+
// `GROUP BY` below returns a row for an outer row without
730+
// a match, which the pulled up filter would drop.
731+
if self.can_extend_partition_by && !self.pulled_up_scalar_agg {
732+
let extended =
733+
partition_window_by(window, &local_correlated_cols)?;
734+
return self.pass_through_pulled_up_cols(extended);
735+
}
716736
self.can_pull_up = false;
717737
}
718738
self.pass_through_pulled_up_cols(plan)
@@ -960,6 +980,46 @@ fn correlated_filter_columns(plan: &LogicalPlan) -> Vec<Column> {
960980
cols
961981
}
962982

983+
/// Adds `cols` to the `PARTITION BY` of every window function of `window`. Each
984+
/// window expression keeps its old output name, so nothing above sees a change.
985+
fn partition_window_by(window: &Window, cols: &BTreeSet<Column>) -> Result<LogicalPlan> {
986+
let window_expr = window
987+
.window_expr
988+
.iter()
989+
.map(|expr| {
990+
add_partition_by(expr, cols).alias_if_changed(expr.schema_name().to_string())
991+
})
992+
.collect::<Result<Vec<_>>>()?;
993+
Window::try_new(window_expr, Arc::clone(&window.input)).map(LogicalPlan::Window)
994+
}
995+
996+
fn add_partition_by(expr: &Expr, cols: &BTreeSet<Column>) -> Expr {
997+
match expr {
998+
Expr::Alias(alias) => Expr::Alias(Alias {
999+
expr: Box::new(add_partition_by(&alias.expr, cols)),
1000+
..alias.clone()
1001+
}),
1002+
Expr::WindowFunction(window_fun) => {
1003+
let mut window_fun = window_fun.clone();
1004+
for col in cols {
1005+
let partitioned = window_fun
1006+
.params
1007+
.partition_by
1008+
.iter()
1009+
.any(|expr| matches!(expr, Expr::Column(c) if c == col));
1010+
if !partitioned {
1011+
window_fun
1012+
.params
1013+
.partition_by
1014+
.push(Expr::Column(col.clone()));
1015+
}
1016+
}
1017+
Expr::WindowFunction(window_fun)
1018+
}
1019+
_ => expr.clone(),
1020+
}
1021+
}
1022+
9631023
/// Whether the window function `expr` lists each of `cols` as a plain
9641024
/// `PARTITION BY` column.
9651025
fn partitions_by_all(expr: &Expr, cols: &BTreeSet<Column>) -> bool {
@@ -989,30 +1049,54 @@ fn collides_with_existing(exprs: &[Expr], candidate: &Expr) -> bool {
9891049
}
9901050

9911051
fn can_pullup_over_aggregation(expr: &Expr) -> bool {
992-
if let Expr::BinaryExpr(BinaryExpr {
1052+
split_column_equality(expr).is_some()
1053+
}
1054+
1055+
/// Whether partitioning by the columns of `expr` keeps the rows `expr` matches
1056+
/// for one outer row in one partition. That holds for `col = <expr>` or
1057+
/// `<expr> = col`, where:
1058+
/// - `<expr>` reads no subquery column and is not volatile.
1059+
/// - `col` has no float leaf, because `-0.0 = 0.0` holds but a partition
1060+
/// keeps the two apart.
1061+
/// - `col` is cast only by a cast that keeps distinct values distinct. A lossy
1062+
/// cast lets several `col` values match one outer row, see #26014.
1063+
fn is_partitionable_equality(expr: &Expr, schema: &DFSchema) -> bool {
1064+
let Some((col_side, other)) = split_column_equality(expr) else {
1065+
return false;
1066+
};
1067+
let (col, cast_to) = match col_side {
1068+
Expr::Cast(Cast { expr, field }) => (&**expr, Some(field.data_type())),
1069+
_ => (col_side, None),
1070+
};
1071+
let Ok(col_type) = col.get_type(schema) else {
1072+
return false;
1073+
};
1074+
!other.is_volatile()
1075+
&& !has_float_leaf(&col_type)
1076+
&& cast_to.is_none_or(|to| is_injective_cast(&col_type, to))
1077+
}
1078+
1079+
/// Splits `col = <expr>` or `<expr> = col` into the subquery column side, a
1080+
/// column or a cast of one, and the other side, which reads no subquery column.
1081+
fn split_column_equality(expr: &Expr) -> Option<(&Expr, &Expr)> {
1082+
let Expr::BinaryExpr(BinaryExpr {
9931083
left,
9941084
op: Operator::Eq,
9951085
right,
9961086
}) = expr
997-
{
998-
match (&**left, &**right) {
999-
(Expr::Column(_), right) => !right.any_column_refs(),
1000-
(left, Expr::Column(_)) => !left.any_column_refs(),
1001-
(Expr::Cast(Cast { expr, .. }), right)
1002-
if matches!(&**expr, Expr::Column(_)) =>
1003-
{
1004-
!right.any_column_refs()
1005-
}
1006-
(left, Expr::Cast(Cast { expr, .. }))
1007-
if matches!(&**expr, Expr::Column(_)) =>
1008-
{
1009-
!left.any_column_refs()
1010-
}
1011-
(_, _) => false,
1012-
}
1013-
} else {
1014-
false
1015-
}
1087+
else {
1088+
return None;
1089+
};
1090+
[(&**left, &**right), (&**right, &**left)]
1091+
.into_iter()
1092+
.find(|(col_side, other)| {
1093+
let is_col = match col_side {
1094+
Expr::Column(_) => true,
1095+
Expr::Cast(Cast { expr, .. }) => matches!(&**expr, Expr::Column(_)),
1096+
_ => false,
1097+
};
1098+
is_col && !other.any_column_refs()
1099+
})
10161100
}
10171101

10181102
fn collect_local_correlated_cols(
@@ -1121,7 +1205,11 @@ fn proj_exprs_evaluation_result_on_empty_batch(
11211205
})
11221206
.data()?;
11231207

1124-
if result_expr.ne(expr) {
1208+
// An expression that reads no column, like `1 AS x`, keeps its value
1209+
// on an empty input, while the join that replaces the subquery gives
1210+
// it NULL for an outer row without a match.
1211+
let is_constant = !expr.any_column_refs() && !expr.contains_outer();
1212+
if result_expr.ne(expr) || is_constant {
11251213
let info = SimplifyContext::builder()
11261214
.with_schema(Arc::clone(schema))
11271215
.build();

‎datafusion/sqllogictest/test_files/lateral_join.slt‎

Lines changed: 13 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -755,16 +755,19 @@ ORDER BY t1.id, sub.x;
755755

756756
# --- Correlated filter below a window function ---
757757
# https://github.com/apache/datafusion/issues/25792
758-
# Pulling `t2.t1_id = t1.id` above the window would number the t2 rows of all
759-
# t1 rows together instead of the t2 rows of each t1 row.
760-
# Expected result once supported: (1, 10, 1), (1, 20, 2), (2, 30, 1).
761-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression OuterReferenceColumn
758+
# The pull up adds `t2.t1_id` to the `PARTITION BY` of the window, so each t1
759+
# row still numbers only its own t2 rows.
760+
query III
762761
SELECT t1.id, sub.id, sub.rn
763762
FROM t1, LATERAL (
764763
SELECT t2.id, row_number() OVER (ORDER BY t2.id) AS rn
765764
FROM (SELECT * FROM t2 WHERE t2.t1_id = t1.id) AS t2
766765
) AS sub
767766
ORDER BY t1.id, sub.id;
767+
----
768+
1 10 1
769+
1 20 2
770+
2 30 1
768771

769772
# A correlated filter above the window is still decorrelated. The window
770773
# numbers all t2 rows, then the filter keeps the rows of each t1 row.
@@ -850,8 +853,8 @@ ORDER BY t1.id, sub.id;
850853
1 20 2
851854
2 30 1
852855

853-
# The filter must read a `PARTITION BY` column of every window function.
854-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression OuterReferenceColumn
856+
# Every window function is partitioned by the columns of the filter.
857+
query IIII
855858
SELECT t1.id, sub.id, sub.rn, sub.c
856859
FROM t1, LATERAL (
857860
SELECT t2.id,
@@ -860,6 +863,10 @@ FROM t1, LATERAL (
860863
FROM t2 WHERE t2.t1_id = t1.id
861864
) AS sub
862865
ORDER BY t1.id, sub.id;
866+
----
867+
1 10 1 1
868+
1 20 2 1
869+
2 30 1 1
863870

864871
# --- Implicit LATERAL (comma without LATERAL keyword) ---
865872
# DuckDB auto-detects lateral correlation; DataFusion requires

0 commit comments

Comments
 (0)