Skip to content

Commit 360c072

Browse files
committed
refactor: decide which GROUP BY expressions are determined in one place
The dependency loop and the GROUP BY key reduction each checked whether a GROUP BY expression is determined, in two different ways. Both now use `group_by_positions_determined_by`, which returns the GROUP BY positions that a set of input fields determines. `group_by_key_indices` builds that set from the GROUP BY columns and what the remaining key columns determine, and keeps the key columns and every expression outside it.
1 parent aef8312 commit 360c072

1 file changed

Lines changed: 78 additions & 44 deletions

File tree

‎datafusion/common/src/functional_dependencies.rs‎

Lines changed: 78 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -522,21 +522,11 @@ pub fn aggregate_functional_dependencies_with_computed_inputs(
522522
&grouped_source_indices,
523523
)
524524
.unwrap_or_default();
525-
// A deterministic computed expression is determined when every
526-
// field it reads is.
527-
let mut determined_output_indices = vec![];
528-
for (output_idx, input_idx) in group_by_input_indices.iter().enumerate() {
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 {
537-
determined_output_indices.push(output_idx);
538-
}
539-
}
525+
let determined_output_indices = group_by_positions_determined_by(
526+
&determined_input_indices,
527+
group_by_input_indices,
528+
computed_input_indices,
529+
);
540530
// A determinant is a key of the output, and so determines the
541531
// aggregate values too, if it is a key of the input or determines
542532
// every GROUP BY expression.
@@ -612,22 +602,63 @@ pub fn aggregate_functional_dependencies_with_computed_inputs(
612602
FunctionalDependencies::new(aggregate_func_dependencies)
613603
}
614604

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.
605+
/// Returns the positions of the GROUP BY expressions that the input fields
606+
/// `fields` determine: when two input rows have the same value in every field
607+
/// of `fields`, they also have the same value for each of these expressions.
608+
/// NULL counts as the same value as NULL, as in GROUP BY.
609+
///
610+
/// A column reference is determined when its field is in `fields`. A computed
611+
/// expression is determined when it is deterministic (its
612+
/// `computed_input_indices` entry is `Some`) and every field it reads is in
613+
/// `fields`.
614+
///
615+
/// For example, for `GROUP BY i_item_sk, s_date, upper(i_desc)` over input
616+
/// fields `[i_item_sk, i_desc, s_item_sk, s_date]`, the fields `[0, 1]`
617+
/// (`i_item_sk` and `i_desc`) determine positions `[0, 2]`, but not `s_date`
618+
/// at position 1.
619+
fn group_by_positions_determined_by(
620+
fields: &[usize],
621+
group_by_input_indices: &[Option<usize>],
622+
computed_input_indices: &[Option<Vec<usize>>],
623+
) -> Vec<usize> {
624+
group_by_input_indices
625+
.iter()
626+
.zip(computed_input_indices)
627+
.enumerate()
628+
.filter(|(_, item)| match item {
629+
(Some(field), _) => fields.contains(field),
630+
(None, Some(read)) => read.iter().all(|field| fields.contains(field)),
631+
(None, None) => false,
632+
})
633+
.map(|(position, _)| position)
634+
.collect()
635+
}
636+
637+
/// Returns the positions of the GROUP BY expressions that the GROUP BY key
638+
/// needs: the GROUP BY list without its extraneous expressions. An expression
639+
/// is extraneous when the other expressions of the key determine it.
640+
///
641+
/// Only column references can be key columns, because a computed expression
642+
/// does not expose the fields it reads. The key columns are the column
643+
/// references without the extraneous ones. They determine every column
644+
/// reference of the GROUP BY list, and through the input dependencies some
645+
/// more fields; every expression that these fields determine is left out of
646+
/// the key.
647+
///
648+
/// For example, `GROUP BY i_item_sk, s_date, upper(i_desc), i_desc` over a
649+
/// join where `i_item_sk` determines `i_desc` needs only `i_item_sk` and
650+
/// `s_date`.
618651
fn group_by_key_indices(
619652
schema: &DFSchema,
620653
group_by_input_indices: &[Option<usize>],
621654
computed_input_indices: &[Option<Vec<usize>>],
622655
) -> Vec<usize> {
623656
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();
657+
let column_inputs = group_by_input_indices
658+
.iter()
659+
.filter(|input_idx| input_idx.is_some())
660+
.copied()
661+
.collect::<Vec<_>>();
631662
let Some(required) = get_required_group_by_exprs_indices(schema, &column_inputs)
632663
else {
633664
return all();
@@ -636,31 +667,34 @@ fn group_by_key_indices(
636667
.iter()
637668
.map(|idx| column_inputs[*idx])
638669
.collect::<Vec<_>>();
639-
let determined =
640-
get_target_functional_dependencies(schema, &key_inputs).unwrap_or_default();
641-
let mut key = required
670+
let mut fields = column_inputs.iter().flatten().copied().collect::<Vec<_>>();
671+
fields.extend(
672+
get_target_functional_dependencies(schema, &key_inputs).unwrap_or_default(),
673+
);
674+
let determined = group_by_positions_determined_by(
675+
&fields,
676+
group_by_input_indices,
677+
computed_input_indices,
678+
);
679+
// A column can be in the GROUP BY list more than one time (`x, x AS k`):
680+
// the key keeps its first position.
681+
let key_positions = key_inputs
642682
.iter()
643-
.map(|idx| column_positions[*idx])
683+
.filter_map(|key_input| {
684+
group_by_input_indices
685+
.iter()
686+
.position(|input| input == key_input)
687+
})
688+
.collect::<Vec<_>>();
689+
let key = (0..group_by_input_indices.len())
690+
.filter(|position| {
691+
key_positions.contains(position) || !determined.contains(position)
692+
})
644693
.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-
}
659694
// A key with no columns is left as the whole GROUP BY list.
660695
if key.is_empty() {
661696
return all();
662697
}
663-
key.sort_unstable();
664698
key
665699
}
666700

0 commit comments

Comments
 (0)