@@ -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`.
618651fn 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