jayzhan211 commented on code in PR #27319:
URL: https://github.com/apache/datafusion/pull/27319#discussion_r4571153717


##########
datafusion/physical-expr/src/equivalence/class.rs:
##########
@@ -699,6 +699,27 @@ impl EquivalenceGroup {
             .collect()
     }
 
+    /// Projects `expr` through the mapping, or else projects another member of
+    /// its equivalence class.
+    ///
+    /// The members of a class are equal on every row, so a projected member
+    /// describes the same partitioning or ordering as `expr`. For example, if
+    /// `x` is in a class with `get_field(s, 'k')`, a projection that keeps `s`
+    /// but drops `x` projects `x` to `get_field(s, 'k')`. Literal members are
+    /// skipped, because a literal does not describe how rows are distributed.
+    fn project_expr_or_equivalent(
+        &self,
+        aug_mapping: &AugmentedMapping,
+        expr: &Arc<dyn PhysicalExpr>,
+    ) -> Option<Arc<dyn PhysicalExpr>> {
+        Self::project_expr_indirect(aug_mapping, expr).or_else(|| {
+            self.get_equivalence_class(expr)?
+                .iter()
+                .filter(|member| *member != expr && !member.is::<Literal>())

Review Comment:
   Optional cleanup: removing `&& !member.is::<Literal>()` still passes every 
test in this PR and the equivalence, join, aggregate and subquery slt files, so 
nothing pins this skip. Also, if `x` is in a class with `'a'`, every row has 
the same `x`, so `Hash(['a'])` would still be true. Could you either drop the 
skip and its doc sentence, or add a test that shows what it prevents?



##########
datafusion/sqllogictest/test_files/equivalence_properties.slt:
##########
@@ -375,6 +375,60 @@ physical_plan
 05)--------RepartitionExec: partitioning=RoundRobinBatch(2), 
input_partitions=1, maintains_sort_order=true
 06)----------StreamingTableExec: partition_sizes=1, projection=[a, b, c], 
infinite_source=true, output_ordering=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST, 
c@2 ASC NULLS LAST]
 
+# A partitioned mark join on a struct field, under an aggregate grouped by the
+# same field. The join output is already hash partitioned on the field, so the
+# aggregate needs no repartition. Projection pushdown then moves the field
+# access into the scan and drops the join key from the join output. The join
+# must still know its partitioning through the equivalent field access, or the
+# plan fails the sanity check.
+statement ok
+set datafusion.execution.target_partitions = 2;
+
+statement ok
+set datafusion.optimizer.hash_join_single_partition_threshold_rows = 0;
+
+statement ok
+COPY (SELECT named_struct('k', 'a') AS s)
+TO 'test_files/scratch/equivalence_properties/mark_join/1.parquet';
+
+statement ok
+COPY (SELECT named_struct('k', 'b') AS s)
+TO 'test_files/scratch/equivalence_properties/mark_join/2.parquet';
+
+statement ok
+CREATE EXTERNAL TABLE mark_join STORED AS PARQUET
+LOCATION 'test_files/scratch/equivalence_properties/mark_join/';
+
+query T rowsort
+SELECT s['k'] FROM mark_join
+WHERE s['k'] = 'a' OR s['k'] IN (SELECT s['k'] FROM mark_join)
+GROUP BY 1;
+----
+a
+b
+
+query TT
+EXPLAIN SELECT s['k'] FROM mark_join
+WHERE s['k'] = 'a' OR s['k'] IN (SELECT s['k'] FROM mark_join)
+GROUP BY 1;
+----
+physical_plan
+01)ProjectionExec: expr=[__datafusion_extracted_2@0 as mark_join.s[k]]
+02)--AggregateExec: mode=SinglePartitioned, gby=[__datafusion_extracted_2@0 as 
__datafusion_extracted_2], aggr=[]
+03)----FilterExec: __datafusion_extracted_3@1 = a OR mark@0, 
projection=[__datafusion_extracted_2@2]
+04)------ProjectionExec: expr=[mark@0 as mark, get_field(s@1, k) as 
__datafusion_extracted_3, get_field(s@1, k) as __datafusion_extracted_2]
+05)--------HashJoinExec: mode=Partitioned, join_type=LeftMark, 
on=[(__datafusion_extracted_4@0, mark_join.s[k]@0)], projection=[mark@2, s@1]
+06)----------RepartitionExec: partitioning=Hash([__datafusion_extracted_4@0], 
2), input_partitions=2
+07)------------DataSourceExec: file_groups={2 groups: 
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/equivalence_properties/mark_join/1.parquet],
 
[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/equivalence_properties/mark_join/2.parquet]]},
 projection=[get_field(s@0, k) as __datafusion_extracted_4, s], 
file_type=parquet
+08)----------RepartitionExec: partitioning=Hash([mark_join.s[k]@0], 2), 
input_partitions=2
+09)------------DataSourceExec: file_groups={2 groups: 
[[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/equivalence_properties/mark_join/1.parquet],
 
[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/equivalence_properties/mark_join/2.parquet]]},
 projection=[get_field(s@0, k) as mark_join.s[k]], file_type=parquet, 
predicate=DynamicFilter [ empty ], dynamic_rg_pruning=eligible
+
+statement ok

Review Comment:
   Optional: a `UNION ALL` of two of these joins fails differently on `main` 
(`Internal error: ... Not all InterleaveExec children have a consistent hash or 
range partitioning`). This PR fixes it, but no test covers that shape. Could 
you add it here?
   
   ```suggestion
   # A union of two such joins, which InterleaveExec combines by partitioning.
   query T rowsort
   SELECT k FROM (
     SELECT s['k'] AS k FROM mark_join
     WHERE s['k'] = 'a' OR s['k'] IN (SELECT s['k'] FROM mark_join)
     UNION ALL
     SELECT s['k'] FROM mark_join
     WHERE s['k'] = 'b' OR s['k'] IN (SELECT s['k'] FROM mark_join)
   ) GROUP BY k;
   ----
   a
   b
   
   statement ok
   ```



##########
datafusion/physical-expr/src/equivalence/class.rs:
##########
@@ -699,6 +699,27 @@ impl EquivalenceGroup {
             .collect()
     }
 
+    /// Projects `expr` through the mapping, or else projects another member of
+    /// its equivalence class.
+    ///
+    /// The members of a class are equal on every row, so a projected member
+    /// describes the same partitioning or ordering as `expr`. For example, if
+    /// `x` is in a class with `get_field(s, 'k')`, a projection that keeps `s`
+    /// but drops `x` projects `x` to `get_field(s, 'k')`. Literal members are
+    /// skipped, because a literal does not describe how rows are distributed.
+    fn project_expr_or_equivalent(
+        &self,
+        aug_mapping: &AugmentedMapping,
+        expr: &Arc<dyn PhysicalExpr>,
+    ) -> Option<Arc<dyn PhysicalExpr>> {
+        Self::project_expr_indirect(aug_mapping, expr).or_else(|| {

Review Comment:
   @cetra3 thanks for the quick fix! The fallback only runs at the top level, 
so a join key computed from the field (`s['k'] || 'z'`) still fails, and with 
this PR that query fails to plan, while `main` plans it with a two-phase 
aggregate. With the fallback, `EnsureRequirements` now reuses the join's 
partitioning. After `ProjectionPushdown`, the key `__datafusion_extracted_4 || 
'z'` can only be projected if its child `__datafusion_extracted_4` also falls 
back to `get_field(s, 'k')`.
   
   ```sql
   SELECT s['k'] || 'z' FROM mark_join
   WHERE s['k'] = 'a' OR s['k'] || 'z' IN (SELECT s['k'] || 'z' FROM mark_join)
   GROUP BY 1;
   -- main: az, bz; this PR: SanityCheckPlan error
   ```
   
   Moving the fallback into `project_expr_indirect` covers children too. It 
needs a guard, because classes can refer to each other (`a = b + 1`, `b = a + 
1`), and without one that case overflows the stack:
   
   ```diff
        fn project_expr_indirect(
            aug_mapping: &AugmentedMapping,
            expr: &Arc<dyn PhysicalExpr>,
   +        equivalents: Option<&Self>,
   +        tried: &mut Vec<Arc<dyn PhysicalExpr>>,
        ) -> Option<Arc<dyn PhysicalExpr>> {
   @@
   -                        Self::project_expr_indirect(aug_mapping, child)
   +                        Self::project_expr_indirect(
   +                            aug_mapping,
   +                            child,
   +                            equivalents,
   +                            tried,
   +                        )
   @@
   -        None
   +        // Members of a class are equal on every row, so a projectable 
member
   +        // stands in for `expr`. `tried` stops cycles such as `x = f(y)`, 
`y = g(x)`.
   +        let group = equivalents?;
   +        if tried.contains(expr) {
   +            return None;
   +        }
   +        tried.push(Arc::clone(expr));
   +        group
   +            .get_equivalence_class(expr)?
   +            .iter()
   +            .filter(|member| *member != expr && !member.is::<Literal>())
   +            .find_map(|member| {
   +                Self::project_expr_indirect(aug_mapping, member, 
equivalents, tried)
   +            })
        }
   @@ fn project_expr_or_equivalent
   -        Self::project_expr_indirect(aug_mapping, expr).or_else(|| {
   -            self.get_equivalence_class(expr)?
   -                .iter()
   -                .filter(|member| *member != expr && !member.is::<Literal>())
   -                .find_map(|member| Self::project_expr_indirect(aug_mapping, 
member))
   -        })
   +        Self::project_expr_indirect(aug_mapping, expr, Some(self), &mut 
Vec::new())
   @@ fn project
   -                if let Some(projected) = 
Self::project_expr_indirect(augmented, source) {
   +                if let Some(projected) =
   +                    Self::project_expr_indirect(augmented, source, None, 
&mut Vec::new())
   +                {
   ```
   
   With this change and the tests below, the full sqllogictest suite and `cargo 
clippy -p datafusion-physical-expr --all-targets --all-features` pass. Each 
test fails if you remove the part of the change it covers.
   
   <details>
   <summary>Tests to add: the slt case above, a nested unit test, and a cycle 
unit test</summary>
   
   In `equivalence_properties.slt`, before `DROP TABLE mark_join;`:
   
   ```sql
   # The same plan with a join key computed from the field.
   query T rowsort
   SELECT s['k'] || 'z' FROM mark_join
   WHERE s['k'] = 'a' OR s['k'] || 'z' IN (SELECT s['k'] || 'z' FROM mark_join)
   GROUP BY 1;
   ----
   az
   bz
   ```
   
   In `class.rs` tests:
   
   ```rs
       #[test]
       fn test_project_dropped_child_through_equivalent_expression() -> 
Result<()> {
           // - columns: [a, b, c, d], with a = b + c and d = a * 2.
           // - a projection that keeps b and c projects d to (b + c) * 2, which
           //   needs a's equivalent inside d's equivalent.
           let schema = abc_schema();
           let a = col("a", &schema)?;
           let b_plus_c = binary(
               col("b", &schema)?,
               Operator::Plus,
               col("c", &schema)?,
               &schema,
           )?;
           let mut group = EquivalenceGroup::default();
           group.add_equal_conditions(Arc::clone(&a), b_plus_c);
           group.add_equal_conditions(
               col("d", &schema)?,
               binary(a, Operator::Multiply, lit(2), &schema)?,
           );
           let mapping = ProjectionMapping::from_indices(&[1, 2], &schema)?;
           let projected_schema = Arc::new(Schema::new(vec![
               Field::new("b", DataType::Int32, false),
               Field::new("c", DataType::Int32, false),
           ]));
           let expected = binary(
               binary(
                   col("b", &projected_schema)?,
                   Operator::Plus,
                   col("c", &projected_schema)?,
                   &projected_schema,
               )?,
               Operator::Multiply,
               lit(2),
               &projected_schema,
           )?;
   
           let projected = group.project_expr(&mapping, &col("d", &schema)?);
           assert!(projected.is_some_and(|expr| expr.eq(&expected)));
           Ok(())
       }
   
       #[test]
       fn test_project_cyclic_equivalent_expressions_terminates() -> Result<()> 
{
           // a = b + 1 and b = a + 1 refer to each other; a projection that 
keeps
           // only c cannot project a, and must not recurse forever.
           let schema = abc_schema();
           let (a, b) = (col("a", &schema)?, col("b", &schema)?);
           let mut group = EquivalenceGroup::default();
           group.add_equal_conditions(
               Arc::clone(&a),
               binary(Arc::clone(&b), Operator::Plus, lit(1), &schema)?,
           );
           group.add_equal_conditions(
               Arc::clone(&b),
               binary(Arc::clone(&a), Operator::Plus, lit(1), &schema)?,
           );
           let mapping = ProjectionMapping::from_indices(&[2], &schema)?;
           assert!(group.project_expr(&mapping, &a).is_none());
           Ok(())
       }
   ```
   
   </details>
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to