Skip to content

Commit 730a9fe

Browse files
committed
fix: treat a deterministic computed GROUP BY expression as determined by a key
A computed GROUP BY expression was never counted as determined, so a key next to one, such as `GROUP BY i_item_sk, upper(i_desc)`, was no longer a key of the aggregate output, and queries that plan on 55.2.0 failed. The new `aggregate_functional_dependencies_with_computed_inputs` takes a `computed_input_indices` parameter with the input fields each deterministic computed GROUP BY expression reads. Such an expression is determined when every field it reads is. Volatile expressions and expressions with subqueries or outer references are never determined. `aggregate_functional_dependencies` keeps its signature and is deprecated since 57.0.0; it treats every computed expression as not determined. Also adds tests for the DISTINCT and window frame symptoms of apache#27112.
1 parent 3546d38 commit 730a9fe

5 files changed

Lines changed: 181 additions & 18 deletions

File tree

‎datafusion/common/src/functional_dependencies.rs‎

Lines changed: 43 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -445,10 +445,43 @@ impl Deref for FunctionalDependencies {
445445
/// the expression computes a new value. Only a column reference can carry an
446446
/// input dependency; a computed expression such as `CAST(pk AS INT)` cannot,
447447
/// even though its output name may equal the column's name.
448+
///
449+
/// Every computed GROUP BY expression is treated as not determined by any
450+
/// determinant.
451+
#[deprecated(
452+
since = "57.0.0",
453+
note = "Use `aggregate_functional_dependencies_with_computed_inputs` instead"
454+
)]
448455
pub fn aggregate_functional_dependencies(
449456
aggr_input_schema: &DFSchema,
450457
group_by_input_indices: &[Option<usize>],
451458
aggr_schema: &DFSchema,
459+
) -> FunctionalDependencies {
460+
aggregate_functional_dependencies_with_computed_inputs(
461+
aggr_input_schema,
462+
group_by_input_indices,
463+
&vec![None; group_by_input_indices.len()],
464+
aggr_schema,
465+
)
466+
}
467+
468+
/// Calculates functional dependencies for aggregate output, when there is a GROUP BY expression.
469+
///
470+
/// `group_by_input_indices[i]` is the index of the input field that GROUP BY
471+
/// expression `i` passes through unchanged (a column reference), or `None` if
472+
/// the expression computes a new value. Only a column reference can carry an
473+
/// input dependency; a computed expression such as `CAST(pk AS INT)` cannot,
474+
/// even though its output name may equal the column's name.
475+
///
476+
/// `computed_input_indices[i]` lists the input fields that a deterministic
477+
/// computed GROUP BY expression `i` reads, or is `None` for a column
478+
/// reference or a volatile expression. A computed expression whose fields
479+
/// are all determined by a determinant is determined by it too.
480+
pub fn aggregate_functional_dependencies_with_computed_inputs(
481+
aggr_input_schema: &DFSchema,
482+
group_by_input_indices: &[Option<usize>],
483+
computed_input_indices: &[Option<Vec<usize>>],
484+
aggr_schema: &DFSchema,
452485
) -> FunctionalDependencies {
453486
let mut aggregate_func_dependencies = vec![];
454487
let aggr_fields = aggr_schema.fields();
@@ -489,14 +522,18 @@ pub fn aggregate_functional_dependencies(
489522
&grouped_source_indices,
490523
)
491524
.unwrap_or_default();
492-
// Dependencies are tracked for columns only, so a computed
493-
// expression is never counted as determined, even when its inputs
494-
// are.
525+
// A deterministic computed expression is determined when every
526+
// field it reads is.
495527
let mut determined_output_indices = vec![];
496528
for (output_idx, input_idx) in group_by_input_indices.iter().enumerate() {
497-
if let Some(input_idx) = input_idx
498-
&& determined_input_indices.contains(input_idx)
499-
{
529+
let determined = match (input_idx, &computed_input_indices[output_idx]) {
530+
(Some(input_idx), _) => determined_input_indices.contains(input_idx),
531+
(None, Some(read)) => read
532+
.iter()
533+
.all(|idx| determined_input_indices.contains(idx)),
534+
(None, None) => false,
535+
};
536+
if determined {
500537
determined_output_indices.push(output_idx);
501538
}
502539
}

‎datafusion/common/src/lib.rs‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -71,10 +71,13 @@ pub use file_options::file_type::{
7171
DEFAULT_ARROW_EXTENSION, DEFAULT_AVRO_EXTENSION, DEFAULT_CSV_EXTENSION,
7272
DEFAULT_JSON_EXTENSION, DEFAULT_PARQUET_EXTENSION, GetExt,
7373
};
74+
#[expect(deprecated)]
75+
pub use functional_dependencies::aggregate_functional_dependencies;
7476
pub use functional_dependencies::{
7577
Constraint, Constraints, Dependency, FunctionalDependence, FunctionalDependencies,
76-
aggregate_functional_dependencies, get_required_group_by_exprs_indices,
77-
get_required_sort_exprs_indices, get_target_functional_dependencies,
78+
aggregate_functional_dependencies_with_computed_inputs,
79+
get_required_group_by_exprs_indices, get_required_sort_exprs_indices,
80+
get_target_functional_dependencies,
7881
};
7982
use hashbrown::DefaultHashBuilder;
8083
pub use join_type::{JoinConstraint, JoinSide, JoinType};

‎datafusion/expr/src/logical_plan/plan.rs‎

Lines changed: 45 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -58,8 +58,9 @@ use datafusion_common::{
5858
Column, Constraints, DFSchema, DFSchemaRef, DataFusionError, Dependency,
5959
FunctionalDependence, FunctionalDependencies, NullEquality, ParamValues, Result,
6060
ScalarValue, Spans, SplitPoint, TableReference, UnnestOptions,
61-
aggregate_functional_dependencies, assert_eq_or_internal_err, assert_or_internal_err,
62-
internal_err, plan_datafusion_err, plan_err, validate_range_split_points,
61+
aggregate_functional_dependencies_with_computed_inputs, assert_eq_or_internal_err,
62+
assert_or_internal_err, internal_err, plan_datafusion_err, plan_err,
63+
validate_range_split_points,
6364
};
6465
use itertools::Itertools as _;
6566

@@ -4529,21 +4530,56 @@ fn calc_func_dependencies_for_aggregate(
45294530
// - Otherwise, it may be possible to propagate functional dependencies.
45304531
if !contains_grouping_set(group_expr) {
45314532
// One entry per GROUP BY output field, in the order of `aggr_schema`
4532-
let group_by_input_indices = grouping_set_to_exprlist(group_expr)?
4533-
.into_iter()
4533+
let group_exprs = grouping_set_to_exprlist(group_expr)?;
4534+
let group_by_input_indices = group_exprs
4535+
.iter()
45344536
.map(|item| passthrough_field_index(item, input.schema()))
45354537
.collect::<Vec<_>>();
4536-
let aggregate_func_dependencies = aggregate_functional_dependencies(
4537-
input.schema(),
4538-
&group_by_input_indices,
4539-
aggr_schema,
4540-
);
4538+
let computed_input_indices = group_exprs
4539+
.iter()
4540+
.zip(&group_by_input_indices)
4541+
.map(|(item, input_idx)| match input_idx {
4542+
Some(_) => None,
4543+
None => deterministic_input_indices(item, input.schema()),
4544+
})
4545+
.collect::<Vec<_>>();
4546+
let aggregate_func_dependencies =
4547+
aggregate_functional_dependencies_with_computed_inputs(
4548+
input.schema(),
4549+
&group_by_input_indices,
4550+
&computed_input_indices,
4551+
aggr_schema,
4552+
);
45414553
Ok(aggregate_func_dependencies)
45424554
} else {
45434555
Ok(FunctionalDependencies::empty())
45444556
}
45454557
}
45464558

4559+
/// Returns the input fields that `expr` reads, or `None` if `expr` is volatile,
4560+
/// contains a subquery or reads a column that is not an input field.
4561+
fn deterministic_input_indices(expr: &Expr, schema: &DFSchema) -> Option<Vec<usize>> {
4562+
let has_subquery = expr
4563+
.exists(|e| {
4564+
Ok(matches!(
4565+
e,
4566+
Expr::ScalarSubquery(_)
4567+
| Expr::Exists(_)
4568+
| Expr::InSubquery(_)
4569+
| Expr::SetComparison(_)
4570+
| Expr::OuterReferenceColumn(..)
4571+
))
4572+
})
4573+
.unwrap_or(true);
4574+
if expr.is_volatile() || has_subquery {
4575+
return None;
4576+
}
4577+
expr.column_refs()
4578+
.into_iter()
4579+
.map(|column| schema.index_of_column(column).ok())
4580+
.collect()
4581+
}
4582+
45474583
/// This function projects functional dependencies of the `input` plan according
45484584
/// to projection expressions `exprs`.
45494585
fn calc_func_dependencies_for_project(

‎datafusion/sqllogictest/test_files/functional_dependencies.slt‎

Lines changed: 60 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -787,7 +787,23 @@ ORDER BY i_item_sk;
787787
1 1
788788
2 1
789789

790-
# 8.4 The planner adds `i_desc`, which `i_item_sk` determines, to the inner
790+
# 8.4 `i_item_sk` is not a key of `item_dates`: the DISTINCT must stay, and the
791+
# default window frame must stay RANGE (peers of item 1 count together).
792+
query I
793+
SELECT DISTINCT i_item_sk FROM item_dates ORDER BY i_item_sk;
794+
----
795+
1
796+
2
797+
798+
query II
799+
SELECT i_item_sk, count(*) OVER (ORDER BY i_item_sk) FROM item_dates
800+
ORDER BY i_item_sk;
801+
----
802+
1 2
803+
1 2
804+
2 3
805+
806+
# 8.5 The planner adds `i_desc`, which `i_item_sk` determines, to the inner
791807
# GROUP BY. `i_desc` is an extraneous column of the inner aggregate's key and
792808
# is removed from it, so the key still exists after the projection removes
793809
# `i_desc`, and `c` can be selected.
@@ -801,6 +817,49 @@ GROUP BY i_item_sk, s_date ORDER BY i_item_sk, s_date;
801817
1 101 1
802818
2 100 1
803819

820+
# 8.6 `upper(i_desc)` reads only `i_desc`, which `i_item_sk` determines, so
821+
# `i_item_sk` is a key of the inner aggregate and `c` can be selected.
822+
query II
823+
SELECT i_item_sk, c
824+
FROM (SELECT i_item_sk, upper(i_desc) AS u, count(*) AS c
825+
FROM item JOIN sales ON i_item_sk = s_item_sk
826+
GROUP BY i_item_sk, upper(i_desc)) q
827+
GROUP BY i_item_sk ORDER BY i_item_sk;
828+
----
829+
1 2
830+
2 1
831+
832+
# 8.7 `s_date + 1` reads `s_date`, which `i_item_sk` does not determine.
833+
statement error
834+
SELECT i_item_sk, c
835+
FROM (SELECT i_item_sk, s_date + 1 AS d, count(*) AS c
836+
FROM item JOIN sales ON i_item_sk = s_item_sk
837+
GROUP BY i_item_sk, s_date + 1) q
838+
GROUP BY i_item_sk;
839+
----
840+
DataFusion error: Error during planning: Column in SELECT must be in GROUP BY or an aggregate function: While expanding wildcard, column "q.c" must appear in the GROUP BY clause or must be part of an aggregate function, currently only "q.i_item_sk" appears in the SELECT clause satisfies this requirement
841+
842+
843+
# 8.8 A volatile expression is never determined: the join stays an inner join.
844+
query TT
845+
EXPLAIN SELECT sum(o_amount) FROM orders
846+
JOIN (SELECT i_item_sk FROM item JOIN sales ON i_item_sk = s_item_sk
847+
GROUP BY i_item_sk, random() > 0.5) g
848+
ON o_item_sk = g.i_item_sk;
849+
----
850+
logical_plan
851+
01)Aggregate: groupBy=[[]], aggr=[[sum(CAST(orders.o_amount AS Int64))]]
852+
02)--Projection: orders.o_amount
853+
03)----Inner Join: orders.o_item_sk = g.i_item_sk
854+
04)------TableScan: orders projection=[o_item_sk, o_amount]
855+
05)------SubqueryAlias: g
856+
06)--------Projection: item.i_item_sk
857+
07)----------Aggregate: groupBy=[[item.i_item_sk, random() > Float64(0.5), item.i_desc]], aggr=[[]]
858+
08)------------Projection: item.i_item_sk, item.i_desc
859+
09)--------------Inner Join: item.i_item_sk = sales.s_item_sk
860+
10)----------------TableScan: item projection=[i_item_sk, i_desc]
861+
11)----------------TableScan: sales projection=[s_item_sk]
862+
804863
statement ok
805864
DROP VIEW item_dates;
806865

‎docs/source/library-user-guide/upgrading/56.0.0.md‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1123,6 +1123,34 @@ let indices: Vec<Option<usize>> = exprs
11231123
let target = get_target_functional_dependencies(schema, &indices);
11241124
```
11251125

1126+
### `aggregate_functional_dependencies` is deprecated
1127+
1128+
`aggregate_functional_dependencies` is deprecated; use
1129+
`aggregate_functional_dependencies_with_computed_inputs` instead. Its new
1130+
`computed_input_indices: &[Option<Vec<usize>>]` parameter lists, for each GROUP
1131+
BY expression, the input fields that a deterministic computed expression reads,
1132+
or is `None` for a column reference or a volatile expression. A computed
1133+
expression is determined by a key when every field it reads is, so the key
1134+
stays a key of the aggregate output. The deprecated function treats every
1135+
computed expression as not determined.
1136+
1137+
**Migration guide:**
1138+
1139+
```rust,ignore
1140+
// Before
1141+
let deps = aggregate_functional_dependencies(input_schema, &group_by_input_indices, aggr_schema);
1142+
1143+
// After
1144+
let deps = aggregate_functional_dependencies_with_computed_inputs(
1145+
input_schema,
1146+
&group_by_input_indices,
1147+
&computed_input_indices,
1148+
aggr_schema,
1149+
);
1150+
```
1151+
1152+
See [issue #27112](https://github.com/apache/datafusion/issues/27112) for details.
1153+
11261154
### `FileSource::exact_filter` controls scan equivalence properties
11271155

11281156
`FileScanConfig` no longer derives equivalence properties (constant columns

0 commit comments

Comments
 (0)