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]