Skip to content

Commit ad8578a

Browse files
kumarUjjawalalambclaude
authored
fix: preserve constant equivalence properties through projection (#27123)
## Which issue does this PR close? Closes #26624. ## Rationale for this change With `prefer_hash_join = false`, a query can fail physical plan validation when a filter makes a computed sort or join key constant. Embedding a projection into the sort-merge join loses the constant property after sorting has already relied on it. ## What changes are included in this PR? Preserve each projected equivalence class's constant metadata. A projected member has the same value as its source member on every row, and projection keeps rows in the same partitions. Its known value and uniform or partition-local status therefore still hold. Outer joins clear constants on the NULL-padded side before projecting their output. Partition merges clear `Heterogeneous` constants. Also preserve scalar-subquery leaves during indirect projection. They read a shared subquery result without depending on the input schema. The arithmetic `ORDER BY` reproduction needs the metadata copy; the scalar-subquery join reproduction needs both changes. ## What is the testing strategy for this PR? SQL cases in `joins.slt` cover arithmetic, `upper()`, left joins, and the scalar-subquery join. A NULL-padded left join checks that matched values sort before the NULL rows. The metadata unit test covers known, unknown, and partition-local constants, dropped arguments, and partition merging. The original SQL cases and metadata test fail before the fix and pass afterward. Validation includes the extended workspace tests, full lint suite, and strict all-features Clippy. ## Are there any user-facing changes? Affected queries plan and execute successfully. No public API changes. Needs a backport to `branch-56` for the 56.0.0 regression tracker (#24461). --------- Co-authored-by: Andrew Lamb <[email protected]> Co-authored-by: Claude Fable 5.1 <[email protected]>
1 parent 13bd9d1 commit ad8578a

3 files changed

Lines changed: 154 additions & 4 deletions

File tree

‎datafusion/physical-expr/src/equivalence/class.rs‎

Lines changed: 51 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@ use super::ProjectionMapping;
1212
use crate::expressions::{Column, Literal};
1313
use crate::physical_expr::add_offset_to_expr;
1414
use crate::projection::ProjectionTargets;
15+
use crate::scalar_subquery::ScalarSubqueryExpr;
1516
use crate::{PhysicalExpr, PhysicalExprRef, PhysicalSortExpr, PhysicalSortRequirement};
1617

1718
use datafusion_common::tree_node::{Transformed, TransformedResult, TreeNode};
@@ -631,8 +632,8 @@ impl EquivalenceGroup {
631632
aug_mapping: &AugmentedMapping,
632633
expr: &Arc<dyn PhysicalExpr>,
633634
) -> Option<Arc<dyn PhysicalExpr>> {
634-
// Literals don't need to be projected
635-
if expr.downcast_ref::<Literal>().is_some() {
635+
// These leaves do not read columns from the projected input schema.
636+
if expr.is::<Literal>() || expr.is::<ScalarSubqueryExpr>() {
636637
return Some(Arc::clone(expr));
637638
}
638639

@@ -742,7 +743,11 @@ impl EquivalenceGroup {
742743
pub fn project(&self, mapping: &ProjectionMapping) -> Self {
743744
let projected_classes = self.iter().map(|cls| {
744745
let new_exprs = self.project_expressions(mapping, cls.iter());
745-
EquivalenceClass::new(new_exprs.flatten())
746+
let mut projected = EquivalenceClass::new(new_exprs.flatten());
747+
// Projection changes column references, not constant values or how
748+
// they are distributed across partitions.
749+
projected.constant = projected.constant.or_else(|| cls.constant.clone());
750+
projected
746751
});
747752

748753
// The key is the source expression, and the value is the equivalence
@@ -1334,6 +1339,49 @@ mod tests {
13341339
Ok(())
13351340
}
13361341

1342+
#[test]
1343+
fn test_project_preserves_constant_metadata() -> Result<()> {
1344+
let schema = abc_schema();
1345+
let expr = binary(col("b", &schema)?, Operator::Divide, lit(2i32), &schema)?;
1346+
let mapping = ProjectionMapping::from_indices(&[1], &schema)?;
1347+
let dropped_mapping = ProjectionMapping::from_indices(&[0], &schema)?;
1348+
let projected_b: Arc<dyn PhysicalExpr> = Arc::new(Column::new("b", 0));
1349+
let projected_expr: Arc<dyn PhysicalExpr> = Arc::new(BinaryExpr::new(
1350+
Arc::clone(&projected_b),
1351+
Operator::Divide,
1352+
lit(2i32),
1353+
));
1354+
1355+
for across in [
1356+
AcrossPartitions::Uniform(Some(ScalarValue::Int32(Some(2)))),
1357+
AcrossPartitions::Uniform(None),
1358+
AcrossPartitions::Heterogeneous,
1359+
] {
1360+
let mut group = EquivalenceGroup::default();
1361+
// The class has no literal member, so `EquivalenceClass::new` cannot
1362+
// restore the constant.
1363+
group.add_constant(ConstExpr::new(Arc::clone(&expr), across.clone()));
1364+
1365+
let mut projected = group.project(&mapping);
1366+
assert_eq!(
1367+
projected.is_expr_constant(&projected_expr),
1368+
Some(across.clone())
1369+
);
1370+
// A constant expression does not imply that its argument is constant.
1371+
assert_eq!(projected.is_expr_constant(&projected_b), None);
1372+
assert!(group.project(&dropped_mapping).is_empty());
1373+
1374+
let heterogeneous = across == AcrossPartitions::Heterogeneous;
1375+
assert_eq!(projected.clear_per_partition_constants(), heterogeneous);
1376+
assert_eq!(
1377+
projected.is_expr_constant(&projected_expr),
1378+
(!heterogeneous).then_some(across)
1379+
);
1380+
}
1381+
1382+
Ok(())
1383+
}
1384+
13371385
#[test]
13381386
fn test_project_constant_of_equivalent_source() -> Result<()> {
13391387
// - columns: [a, b, c].

‎datafusion/sqllogictest/test_files/aggregate.slt‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3093,7 +3093,9 @@ SELECT g, percentile_cont(x, m) FROM (SELECT value % 4 AS g, value AS x, 0.25 AS
30933093
2 26
30943094
3 27
30953095

3096-
query error DataFusion error: Execution error: Percentile value for 'PERCENTILE_CONT' must be constant across the aggregation, found differing values 0.5 and 0.9
3096+
# The partial states are merged in whichever order the partitions finish,
3097+
# so the two differing values can be reported in either order
3098+
query error DataFusion error: Execution error: Percentile value for 'PERCENTILE_CONT' must be constant across the aggregation, found differing values (0\.5 and 0\.9|0\.9 and 0\.5)
30973099
SELECT g, percentile_cont(x, m) FROM (SELECT value % 4 AS g, value AS x, CASE WHEN value <= 50 THEN 0.5 ELSE 0.9 END AS m FROM generate_series(1, 100)) GROUP BY g
30983100

30993101
query IR

‎datafusion/sqllogictest/test_files/joins.slt‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6343,3 +6343,103 @@ DROP TABLE projection_networks;
63436343

63446344
statement ok
63456345
set datafusion.execution.target_partitions = 4;
6346+
6347+
# A computed constant must survive the projection embedded into a sort-merge
6348+
# join, even when only the expression's argument is projected.
6349+
# https://github.com/apache/datafusion/issues/26624
6350+
statement ok
6351+
set datafusion.optimizer.prefer_hash_join = false;
6352+
6353+
statement ok
6354+
CREATE TABLE constant_projection (a INT, b INT, s VARCHAR) AS VALUES
6355+
(1, 1, 'x'), (2, 0, 'X'), (3, 1, 'y'), (4, NULL, NULL), (5, 1, 'X');
6356+
6357+
query II
6358+
SELECT t1.b + 1 AS x, t2.a
6359+
FROM constant_projection t1 JOIN constant_projection t2 ON t1.a = t2.a
6360+
WHERE t1.b + 1 = 2
6361+
ORDER BY x, t2.a;
6362+
----
6363+
2 1
6364+
2 3
6365+
2 5
6366+
6367+
statement ok
6368+
set datafusion.explain.physical_plan_only = true;
6369+
6370+
query TT
6371+
EXPLAIN SELECT t1.b + 1 AS x, t2.a
6372+
FROM constant_projection t1 JOIN constant_projection t2 ON t1.a = t2.a
6373+
WHERE t1.b + 1 = 2
6374+
ORDER BY x, t2.a;
6375+
----
6376+
physical_plan
6377+
01)SortPreservingMergeExec: [x@0 ASC NULLS LAST, a@1 ASC NULLS LAST]
6378+
02)--SortExec: expr=[a@1 ASC NULLS LAST], preserve_partitioning=[true]
6379+
03)----ProjectionExec: expr=[CAST(b@0 AS Int64) + 1 as x, a@1 as a]
6380+
04)------SortMergeJoinExec: join_type=Inner, on=[(a@0, a@0)], projection=[b@1, a@2]
6381+
05)--------SortExec: expr=[a@0 ASC], preserve_partitioning=[true]
6382+
06)----------RepartitionExec: partitioning=Hash([a@0], 4), input_partitions=1
6383+
07)------------FilterExec: CAST(b@1 AS Int64) + 1 = 2
6384+
08)--------------DataSourceExec: partitions=1, partition_sizes=[1]
6385+
09)--------SortExec: expr=[a@0 ASC], preserve_partitioning=[true]
6386+
10)----------RepartitionExec: partitioning=Hash([a@0], 4), input_partitions=1
6387+
11)------------DataSourceExec: partitions=1, partition_sizes=[1]
6388+
6389+
statement ok
6390+
reset datafusion.explain.physical_plan_only;
6391+
6392+
query II
6393+
SELECT t1.b + 1 AS x, t2.a
6394+
FROM constant_projection t1 LEFT JOIN constant_projection t2 ON t1.a = t2.a
6395+
WHERE t1.b + 1 = 2
6396+
ORDER BY x, t2.a;
6397+
----
6398+
2 1
6399+
2 3
6400+
2 5
6401+
6402+
# NULL padding invalidates the right side's constant, so x still needs sorting.
6403+
query II
6404+
SELECT t2.b + 1 AS x, t1.a
6405+
FROM constant_projection t1
6406+
LEFT JOIN (SELECT * FROM constant_projection WHERE b + 1 = 2) t2 ON t1.a = t2.a
6407+
ORDER BY x, t1.a;
6408+
----
6409+
2 1
6410+
2 3
6411+
2 5
6412+
NULL 2
6413+
NULL 4
6414+
6415+
query TI
6416+
SELECT upper(t1.s) AS x, t2.a
6417+
FROM constant_projection t1 JOIN constant_projection t2 ON t1.a = t2.a
6418+
WHERE upper(t1.s) = 'X'
6419+
ORDER BY x, t2.a;
6420+
----
6421+
X 1
6422+
X 2
6423+
X 5
6424+
6425+
statement ok
6426+
DROP TABLE constant_projection;
6427+
6428+
# The expression must also survive when it contains a scalar-subquery leaf.
6429+
statement ok
6430+
CREATE TABLE subquery_projection (a INT, b INT) AS VALUES (1, 1), (2, 0);
6431+
6432+
query III
6433+
SELECT * FROM (
6434+
SELECT t1.b + (SELECT max(a) FROM subquery_projection) AS x
6435+
FROM subquery_projection t1 JOIN subquery_projection t2 ON t1.a = t2.a
6436+
) s JOIN subquery_projection t3 ON s.x = t3.a
6437+
WHERE s.x = 2;
6438+
----
6439+
2 2 0
6440+
6441+
statement ok
6442+
DROP TABLE subquery_projection;
6443+
6444+
statement ok
6445+
reset datafusion.optimizer.prefer_hash_join;

0 commit comments

Comments
 (0)