Skip to content

Commit aef8312

Browse files
committed
fix: remove determined computed GROUP BY expressions from the GROUP BY key
`get_required_group_by_exprs_indices` gives up on any computed GROUP BY expression, so the GROUP BY key kept every expression. A projection that removed one of them dropped the key, and a query such as `GROUP BY i_item_sk, s_date, upper(i_desc)` below an outer `GROUP BY i_item_sk, s_date` failed to plan, although it plans on 55.2.0. The new `group_by_key_indices` removes extraneous columns from the key as before, and also a deterministic computed expression whose fields the remaining key columns determine. A key left with no columns falls back to the whole GROUP BY list.
1 parent 730a9fe commit aef8312

2 files changed

Lines changed: 78 additions & 11 deletions

File tree

‎datafusion/common/src/functional_dependencies.rs‎

Lines changed: 55 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -577,16 +577,11 @@ pub fn aggregate_functional_dependencies_with_computed_inputs(
577577
// Remove extraneous columns (the GROUP BY expressions that the others
578578
// determine) from the key, so that the key still exists after a
579579
// projection removes them.
580-
let source_indices = match get_required_group_by_exprs_indices(
580+
let source_indices = group_by_key_indices(
581581
aggr_input_schema,
582582
group_by_input_indices,
583-
) {
584-
Some(mut indices) => {
585-
indices.sort_unstable();
586-
indices
587-
}
588-
None => (0..count).collect(),
589-
};
583+
computed_input_indices,
584+
);
590585
let nullable = source_indices
591586
.iter()
592587
.any(|idx| aggr_fields[*idx].is_nullable());
@@ -617,6 +612,58 @@ pub fn aggregate_functional_dependencies_with_computed_inputs(
617612
FunctionalDependencies::new(aggregate_func_dependencies)
618613
}
619614

615+
/// Returns the GROUP BY expressions that the whole GROUP BY key needs. A column
616+
/// that the other columns determine is left out, and so is a deterministic
617+
/// computed expression whose fields the remaining columns determine.
618+
fn group_by_key_indices(
619+
schema: &DFSchema,
620+
group_by_input_indices: &[Option<usize>],
621+
computed_input_indices: &[Option<Vec<usize>>],
622+
) -> Vec<usize> {
623+
let all = || (0..group_by_input_indices.len()).collect();
624+
let (column_positions, column_inputs): (Vec<usize>, Vec<Option<usize>>) =
625+
group_by_input_indices
626+
.iter()
627+
.enumerate()
628+
.filter(|(_, input_idx)| input_idx.is_some())
629+
.map(|(idx, input_idx)| (idx, *input_idx))
630+
.unzip();
631+
let Some(required) = get_required_group_by_exprs_indices(schema, &column_inputs)
632+
else {
633+
return all();
634+
};
635+
let key_inputs = required
636+
.iter()
637+
.map(|idx| column_inputs[*idx])
638+
.collect::<Vec<_>>();
639+
let determined =
640+
get_target_functional_dependencies(schema, &key_inputs).unwrap_or_default();
641+
let mut key = required
642+
.iter()
643+
.map(|idx| column_positions[*idx])
644+
.collect::<Vec<_>>();
645+
for (idx, (input_idx, read)) in group_by_input_indices
646+
.iter()
647+
.zip(computed_input_indices)
648+
.enumerate()
649+
{
650+
let is_determined = read.as_ref().is_some_and(|read| {
651+
read.iter().all(|field| {
652+
determined.contains(field) || key_inputs.contains(&Some(*field))
653+
})
654+
});
655+
if input_idx.is_none() && !is_determined {
656+
key.push(idx);
657+
}
658+
}
659+
// A key with no columns is left as the whole GROUP BY list.
660+
if key.is_empty() {
661+
return all();
662+
}
663+
key.sort_unstable();
664+
key
665+
}
666+
620667
/// Returns target indices, for the determinant keys that are inside
621668
/// group by expressions.
622669
///

‎datafusion/sqllogictest/test_files/functional_dependencies.slt‎

Lines changed: 23 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -817,7 +817,27 @@ GROUP BY i_item_sk, s_date ORDER BY i_item_sk, s_date;
817817
1 101 1
818818
2 100 1
819819

820-
# 8.6 `upper(i_desc)` reads only `i_desc`, which `i_item_sk` determines, so
820+
# 8.6 `upper(i_desc)` reads `i_desc`, which `i_item_sk` determines, and
821+
# `s_date + 1` reads `s_date`: both are removed from the key of the inner
822+
# aggregate.
823+
query III
824+
SELECT i_item_sk, s_date, c
825+
FROM (SELECT i_item_sk, s_date, count(*) AS c FROM item JOIN sales ON i_item_sk = s_item_sk
826+
GROUP BY i_item_sk, s_date, upper(i_desc), s_date + 1) q
827+
GROUP BY i_item_sk, s_date ORDER BY i_item_sk, s_date;
828+
----
829+
1 100 1
830+
1 101 1
831+
2 100 1
832+
833+
# 8.7 A GROUP BY that reads no column keeps the whole GROUP BY list as its key.
834+
query I
835+
SELECT count(*) FROM orders
836+
JOIN (SELECT 1 AS k FROM sales WHERE false GROUP BY 'x') g ON o_item_sk = g.k;
837+
----
838+
0
839+
840+
# 8.8 `upper(i_desc)` reads only `i_desc`, which `i_item_sk` determines, so
821841
# `i_item_sk` is a key of the inner aggregate and `c` can be selected.
822842
query II
823843
SELECT i_item_sk, c
@@ -829,7 +849,7 @@ GROUP BY i_item_sk ORDER BY i_item_sk;
829849
1 2
830850
2 1
831851

832-
# 8.7 `s_date + 1` reads `s_date`, which `i_item_sk` does not determine.
852+
# 8.9 `s_date + 1` reads `s_date`, which `i_item_sk` does not determine.
833853
statement error
834854
SELECT i_item_sk, c
835855
FROM (SELECT i_item_sk, s_date + 1 AS d, count(*) AS c
@@ -840,7 +860,7 @@ GROUP BY i_item_sk;
840860
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
841861

842862

843-
# 8.8 A volatile expression is never determined: the join stays an inner join.
863+
# 8.10 A volatile expression is never determined: the join stays an inner join.
844864
query TT
845865
EXPLAIN SELECT sum(o_amount) FROM orders
846866
JOIN (SELECT i_item_sk FROM item JOIN sales ON i_item_sk = s_item_sk

0 commit comments

Comments
 (0)