Skip to content

Commit 6de8300

Browse files
compheadadriangb
andcommitted
feat: decorrelate a window below a correlated equality filter
When every correlated conjunct below a window has the form `col = <outer expr>`, add `col` to the `PARTITION BY` of every window function and pull the filter above the window. Each extended window expression is aliased to its old name, so the output schema is unchanged. Volatile outer expressions, columns with a float leaf (`-0.0 = 0.0` holds but a partition splits them) and lossy casts keep the subquery correlated. Lossless widening casts are accepted through `is_injective_cast`. An input with count bug handling also keeps the subquery correlated. Closes apache#25897. Co-authored-by: Adrian Garcia Badaracco <[email protected]>
1 parent b86f1f2 commit 6de8300

4 files changed

Lines changed: 208 additions & 70 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: 112 additions & 28 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());
@@ -664,6 +674,16 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
664674
.iter()
665675
.all(|expr| partitions_by_all(expr, &local_correlated_cols))
666676
{
677+
// `inner.y = outer.k` keeps the rows of one `y` value for
678+
// each outer row, so partitioning by `y` as well gives each
679+
// window function the same rows. A window over an
680+
// aggregate with count bug handling stops the pull up in
681+
// `pass_through_pulled_up_cols`.
682+
if self.can_extend_partition_by {
683+
let extended =
684+
partition_window_by(window, &local_correlated_cols)?;
685+
return self.pass_through_pulled_up_cols(extended);
686+
}
667687
self.can_pull_up = false;
668688
}
669689
self.pass_through_pulled_up_cols(plan)
@@ -907,6 +927,46 @@ fn correlated_filter_columns(plan: &LogicalPlan) -> Vec<Column> {
907927
cols
908928
}
909929

930+
/// Adds `cols` to the `PARTITION BY` of every window function of `window`. Each
931+
/// window expression keeps its old output name, so nothing above sees a change.
932+
fn partition_window_by(window: &Window, cols: &BTreeSet<Column>) -> Result<LogicalPlan> {
933+
let window_expr = window
934+
.window_expr
935+
.iter()
936+
.map(|expr| {
937+
add_partition_by(expr, cols).alias_if_changed(expr.schema_name().to_string())
938+
})
939+
.collect::<Result<Vec<_>>>()?;
940+
Window::try_new(window_expr, Arc::clone(&window.input)).map(LogicalPlan::Window)
941+
}
942+
943+
fn add_partition_by(expr: &Expr, cols: &BTreeSet<Column>) -> Expr {
944+
match expr {
945+
Expr::Alias(alias) => Expr::Alias(Alias {
946+
expr: Box::new(add_partition_by(&alias.expr, cols)),
947+
..alias.clone()
948+
}),
949+
Expr::WindowFunction(window_fun) => {
950+
let mut window_fun = window_fun.clone();
951+
for col in cols {
952+
let partitioned = window_fun
953+
.params
954+
.partition_by
955+
.iter()
956+
.any(|expr| matches!(expr, Expr::Column(c) if c == col));
957+
if !partitioned {
958+
window_fun
959+
.params
960+
.partition_by
961+
.push(Expr::Column(col.clone()));
962+
}
963+
}
964+
Expr::WindowFunction(window_fun)
965+
}
966+
_ => expr.clone(),
967+
}
968+
}
969+
910970
/// Whether the window function `expr` lists each of `cols` as a plain
911971
/// `PARTITION BY` column.
912972
fn partitions_by_all(expr: &Expr, cols: &BTreeSet<Column>) -> bool {
@@ -926,30 +986,54 @@ fn partitions_by_all(expr: &Expr, cols: &BTreeSet<Column>) -> bool {
926986
}
927987

928988
fn can_pullup_over_aggregation(expr: &Expr) -> bool {
929-
if let Expr::BinaryExpr(BinaryExpr {
989+
split_column_equality(expr).is_some()
990+
}
991+
992+
/// Whether partitioning by the columns of `expr` keeps the rows `expr` matches
993+
/// for one outer row in one partition. That holds for `col = <expr>` or
994+
/// `<expr> = col`, where:
995+
/// - `<expr>` reads no subquery column and is not volatile.
996+
/// - `col` has no float leaf, because `-0.0 = 0.0` holds but a partition
997+
/// keeps the two apart.
998+
/// - `col` is cast only by a cast that keeps distinct values distinct. A lossy
999+
/// cast lets several `col` values match one outer row, see #26014.
1000+
fn is_partitionable_equality(expr: &Expr, schema: &DFSchema) -> bool {
1001+
let Some((col_side, other)) = split_column_equality(expr) else {
1002+
return false;
1003+
};
1004+
let (col, cast_to) = match col_side {
1005+
Expr::Cast(Cast { expr, field }) => (&**expr, Some(field.data_type())),
1006+
_ => (col_side, None),
1007+
};
1008+
let Ok(col_type) = col.get_type(schema) else {
1009+
return false;
1010+
};
1011+
!other.is_volatile()
1012+
&& !has_float_leaf(&col_type)
1013+
&& cast_to.is_none_or(|to| is_injective_cast(&col_type, to))
1014+
}
1015+
1016+
/// Splits `col = <expr>` or `<expr> = col` into the subquery column side, a
1017+
/// column or a cast of one, and the other side, which reads no subquery column.
1018+
fn split_column_equality(expr: &Expr) -> Option<(&Expr, &Expr)> {
1019+
let Expr::BinaryExpr(BinaryExpr {
9301020
left,
9311021
op: Operator::Eq,
9321022
right,
9331023
}) = expr
934-
{
935-
match (&**left, &**right) {
936-
(Expr::Column(_), right) => !right.any_column_refs(),
937-
(left, Expr::Column(_)) => !left.any_column_refs(),
938-
(Expr::Cast(Cast { expr, .. }), right)
939-
if matches!(&**expr, Expr::Column(_)) =>
940-
{
941-
!right.any_column_refs()
942-
}
943-
(left, Expr::Cast(Cast { expr, .. }))
944-
if matches!(&**expr, Expr::Column(_)) =>
945-
{
946-
!left.any_column_refs()
947-
}
948-
(_, _) => false,
949-
}
950-
} else {
951-
false
952-
}
1024+
else {
1025+
return None;
1026+
};
1027+
[(&**left, &**right), (&**right, &**left)]
1028+
.into_iter()
1029+
.find(|(col_side, other)| {
1030+
let is_col = match col_side {
1031+
Expr::Column(_) => true,
1032+
Expr::Cast(Cast { expr, .. }) => matches!(&**expr, Expr::Column(_)),
1033+
_ => false,
1034+
};
1035+
is_col && !other.any_column_refs()
1036+
})
9531037
}
9541038

9551039
fn collect_local_correlated_cols(

‎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)