@@ -21,13 +21,15 @@ mod boolean;
2121mod bytes;
2222pub mod bytes_view;
2323pub mod primitive;
24+ pub mod row_backed;
2425
2526use std:: mem:: { self , size_of} ;
2627
2728use crate :: aggregates:: group_values:: GroupValues ;
2829use crate :: aggregates:: group_values:: multi_group_by:: {
2930 boolean:: BooleanGroupValueBuilder , bytes:: ByteGroupValueBuilder ,
3031 bytes_view:: ByteViewGroupValueBuilder , primitive:: PrimitiveGroupValueBuilder ,
32+ row_backed:: RowsGroupColumn ,
3133} ;
3234use arrow:: array:: { Array , ArrayRef , BooleanBufferBuilder } ;
3335use arrow:: compute:: cast;
@@ -923,6 +925,15 @@ macro_rules! instantiate_primitive {
923925/// builder for. The `group_column_supported_type_matches_make_group_column`
924926/// test below pins this biconditional.
925927fn group_column_supported_type ( data_type : & DataType ) -> bool {
928+ // Nested types (Struct / List / LargeList / FixedSizeList, recursively) have
929+ // no type-specialized `GroupColumn`; they are handled by the generic
930+ // row-backed fallback in `make_group_column` whenever arrow's row format can
931+ // encode them. Gate the fallback to nested types so intentionally-excluded
932+ // scalar types (e.g. Float16, Decimal256) stay on `GroupValuesRows` and the
933+ // `group_column_supported_type` ⇔ `make_group_column` invariant holds.
934+ if data_type. is_nested ( ) {
935+ return RowsGroupColumn :: supports_type ( data_type) ;
936+ }
926937 matches ! (
927938 * data_type,
928939 DataType :: Int8
@@ -1067,6 +1078,14 @@ fn make_group_column(field: &Field) -> Result<Box<dyn GroupColumn>> {
10671078 v. push ( Box :: new ( BooleanGroupValueBuilder :: < false > :: new ( ) ) ) ;
10681079 }
10691080 }
1081+ // Generic fallback for nested types (Struct / List / LargeList /
1082+ // FixedSizeList, recursively) that lack a type-specialized builder but
1083+ // can be encoded by arrow's row format. This is what lets a mixed
1084+ // schema keep the column-wise fast path for its native columns instead
1085+ // of dropping the whole key onto `GroupValuesRows`.
1086+ ref dt if dt. is_nested ( ) && RowsGroupColumn :: supports_type ( dt) => {
1087+ v. push ( Box :: new ( RowsGroupColumn :: try_new ( dt. clone ( ) ) ?) ) ;
1088+ }
10701089 _ => return not_impl_err ! ( "{data_type} not supported in GroupValuesColumn" ) ,
10711090 }
10721091 debug_assert_eq ! (
@@ -1273,6 +1292,248 @@ mod tests {
12731292 GroupIndexView , group_column_supported_type, make_group_column, supported_schema,
12741293 } ;
12751294
1295+ /// A mixed group-by key of several native columns plus one nested column
1296+ /// that has no type-specialized `GroupColumn`.
1297+ ///
1298+ /// Before the generic row-backed fallback, `supported_schema` returned
1299+ /// `false` for this schema, so the *entire* key dropped to the row-wise
1300+ /// `GroupValuesRows`. Now only the nested column pays the row-encoding
1301+ /// cost; the native columns keep their compact column-wise storage. This
1302+ /// test proves both that (a) the results are identical and (b) the
1303+ /// column-wise path now uses less memory than the all-rows fallback.
1304+ #[ test]
1305+ fn mixed_schema_column_path_uses_less_memory_than_rows_fallback ( ) {
1306+ use crate :: aggregates:: group_values:: GroupValuesRows ;
1307+ use arrow:: array:: { FixedSizeListArray , Int64Array } ;
1308+ use arrow:: datatypes:: Int64Type ;
1309+
1310+ // 8 native Int64 columns + 1 FixedSizeList<Int64, 4> ("embedding").
1311+ let fsl_field = Arc :: new ( Field :: new ( "item" , DataType :: Int64 , true ) ) ;
1312+ let mut fields: Vec < Field > = ( 0 ..8 )
1313+ . map ( |i| Field :: new ( format ! ( "k{i}" ) , DataType :: Int64 , false ) )
1314+ . collect ( ) ;
1315+ fields. push ( Field :: new (
1316+ "emb" ,
1317+ DataType :: FixedSizeList ( Arc :: clone ( & fsl_field) , 4 ) ,
1318+ true ,
1319+ ) ) ;
1320+ let schema: SchemaRef = Arc :: new ( Schema :: new ( fields) ) ;
1321+
1322+ // The whole schema must now be eligible for the column-wise path.
1323+ assert ! (
1324+ supported_schema( schema. as_ref( ) ) ,
1325+ "mixed native + nested schema should be column-supported now"
1326+ ) ;
1327+
1328+ // Build `n_groups` distinct rows (each row is its own group).
1329+ let n_groups = 4000usize ;
1330+ let mut cols: Vec < ArrayRef > = ( 0 ..8 )
1331+ . map ( |c| {
1332+ let vals: Vec < i64 > =
1333+ ( 0 ..n_groups) . map ( |r| ( r as i64 ) * 8 + c as i64 ) . collect ( ) ;
1334+ Arc :: new ( Int64Array :: from ( vals) ) as ArrayRef
1335+ } )
1336+ . collect ( ) ;
1337+ let emb: Vec < Option < Vec < Option < i64 > > > > = ( 0 ..n_groups)
1338+ . map ( |r| {
1339+ Some ( vec ! [
1340+ Some ( r as i64 ) ,
1341+ Some ( r as i64 + 1 ) ,
1342+ Some ( r as i64 + 2 ) ,
1343+ Some ( r as i64 + 3 ) ,
1344+ ] )
1345+ } )
1346+ . collect ( ) ;
1347+ cols. push (
1348+ Arc :: new ( FixedSizeListArray :: from_iter_primitive :: < Int64Type , _ , _ > (
1349+ emb, 4 ,
1350+ ) ) as ArrayRef ,
1351+ ) ;
1352+
1353+ // Intern the same data into both implementations.
1354+ let mut column_path = GroupValuesColumn :: < false > :: try_new ( Arc :: clone ( & schema) )
1355+ . expect ( "column path" ) ;
1356+ let mut rows_path =
1357+ GroupValuesRows :: try_new ( Arc :: clone ( & schema) ) . expect ( "rows path" ) ;
1358+
1359+ let mut g1 = vec ! [ ] ;
1360+ let mut g2 = vec ! [ ] ;
1361+ column_path. intern ( & cols, & mut g1) . unwrap ( ) ;
1362+ rows_path. intern ( & cols, & mut g2) . unwrap ( ) ;
1363+
1364+ // (a) Correctness: same number of groups and identical group assignment.
1365+ assert_eq ! ( column_path. len( ) , n_groups) ;
1366+ assert_eq ! ( rows_path. len( ) , n_groups) ;
1367+ assert_eq ! ( g1, g2, "group assignment must match the rows fallback" ) ;
1368+
1369+ // (b) Memory: the column-wise path stores the 8 native columns compactly
1370+ // and only row-encodes the nested one, so it must be smaller than
1371+ // encoding every column into rows.
1372+ let column_size = column_path. size ( ) ;
1373+ let rows_size = rows_path. size ( ) ;
1374+ println ! (
1375+ "mixed-schema group values size: column-wise = {column_size} bytes, \
1376+ all-rows fallback = {rows_size} bytes \
1377+ ({:.1}% of fallback)",
1378+ 100.0 * column_size as f64 / rows_size as f64
1379+ ) ;
1380+ assert ! (
1381+ column_size < rows_size,
1382+ "expected column-wise path ({column_size}) to use less memory than \
1383+ the all-rows fallback ({rows_size})"
1384+ ) ;
1385+
1386+ // Emitted values must be equal too (compare via the rows fallback which
1387+ // is the established reference implementation).
1388+ let out_col = column_path. emit ( EmitTo :: All ) . unwrap ( ) ;
1389+ let out_row = rows_path. emit ( EmitTo :: All ) . unwrap ( ) ;
1390+ assert_eq ! ( out_col. len( ) , out_row. len( ) ) ;
1391+ for ( a, b) in out_col. iter ( ) . zip ( out_row. iter ( ) ) {
1392+ assert_eq ! ( a. as_ref( ) , b. as_ref( ) ) ;
1393+ }
1394+ }
1395+
1396+ /// Relabel a group-index vector so labels are assigned in order of first
1397+ /// appearance. Two vectors are equivalent groupings iff their canonical
1398+ /// forms are equal — this ignores the (opaque, non-semantic) difference in
1399+ /// group-index numbering between the vectorized column path and the
1400+ /// sequential rows fallback.
1401+ fn canonical_grouping ( groups : & [ usize ] ) -> Vec < usize > {
1402+ let mut map = HashMap :: new ( ) ;
1403+ let mut next = 0usize ;
1404+ groups
1405+ . iter ( )
1406+ . map ( |& g| {
1407+ * map. entry ( g) . or_insert_with ( || {
1408+ let v = next;
1409+ next += 1 ;
1410+ v
1411+ } )
1412+ } )
1413+ . collect ( )
1414+ }
1415+
1416+ /// The generic row-backed column must be behavior-preserving: for the
1417+ /// nested columns it now handles, `GroupValuesColumn` must induce the same
1418+ /// grouping (partition of rows) as the established `GroupValuesRows`
1419+ /// fallback — including the float `-0.0` / `+0.0` / `NaN` edge cases decided
1420+ /// jointly by hashing and the row format.
1421+ #[ test]
1422+ fn nested_float_edge_cases_match_rows_fallback ( ) {
1423+ use crate :: aggregates:: group_values:: GroupValuesRows ;
1424+ use arrow:: array:: { FixedSizeListArray , Float64Array } ;
1425+
1426+ let item = Arc :: new ( Field :: new ( "item" , DataType :: Float64 , true ) ) ;
1427+ let schema: SchemaRef = Arc :: new ( Schema :: new ( vec ! [ Field :: new(
1428+ "emb" ,
1429+ DataType :: FixedSizeList ( Arc :: clone( & item) , 2 ) ,
1430+ true ,
1431+ ) ] ) ) ;
1432+ assert ! ( supported_schema( schema. as_ref( ) ) ) ;
1433+
1434+ // Rows exercising +0.0 vs -0.0, two NaN bit patterns, and inner nulls.
1435+ let nan = f64:: NAN ;
1436+ let other_nan = f64:: from_bits ( 0x7ff8_0000_0000_0001 ) ;
1437+ let values = Float64Array :: from ( vec ! [
1438+ Some ( 0.0 ) ,
1439+ Some ( 1.0 ) , // [ +0.0, 1.0 ]
1440+ Some ( -0.0 ) ,
1441+ Some ( 1.0 ) , // [ -0.0, 1.0 ]
1442+ Some ( nan) ,
1443+ Some ( 2.0 ) , // [ NaN, 2.0 ]
1444+ Some ( other_nan) ,
1445+ Some ( 2.0 ) , // [ NaN', 2.0 ]
1446+ Some ( 0.0 ) ,
1447+ Some ( 1.0 ) , // [ +0.0, 1.0 ] (dup of row 0)
1448+ ] ) ;
1449+ let field_ref = Arc :: new ( Field :: new ( "item" , DataType :: Float64 , true ) ) ;
1450+ let input: ArrayRef = Arc :: new ( FixedSizeListArray :: new (
1451+ field_ref,
1452+ 2 ,
1453+ Arc :: new ( values) ,
1454+ None ,
1455+ ) ) ;
1456+
1457+ let cols = vec ! [ input] ;
1458+
1459+ let mut column_path =
1460+ GroupValuesColumn :: < false > :: try_new ( Arc :: clone ( & schema) ) . unwrap ( ) ;
1461+ let mut rows_path = GroupValuesRows :: try_new ( Arc :: clone ( & schema) ) . unwrap ( ) ;
1462+
1463+ let mut g1 = vec ! [ ] ;
1464+ let mut g2 = vec ! [ ] ;
1465+ column_path. intern ( & cols, & mut g1) . unwrap ( ) ;
1466+ rows_path. intern ( & cols, & mut g2) . unwrap ( ) ;
1467+
1468+ assert_eq ! (
1469+ canonical_grouping( & g1) ,
1470+ canonical_grouping( & g2) ,
1471+ "column-wise path must induce the same grouping as the rows fallback \
1472+ on float edge cases (got column={g1:?}, rows={g2:?})"
1473+ ) ;
1474+ assert_eq ! ( column_path. len( ) , rows_path. len( ) ) ;
1475+ }
1476+
1477+ /// Equivalence across multiple `intern` batches and `EmitTo::First(n)`.
1478+ #[ test]
1479+ fn multi_batch_and_emit_first_matches_rows_fallback ( ) {
1480+ use crate :: aggregates:: group_values:: GroupValuesRows ;
1481+ use arrow:: array:: { FixedSizeListArray , Int32Array } ;
1482+ use arrow:: datatypes:: Int32Type ;
1483+
1484+ let item = Arc :: new ( Field :: new ( "item" , DataType :: Int32 , true ) ) ;
1485+ let schema: SchemaRef = Arc :: new ( Schema :: new ( vec ! [
1486+ Field :: new( "k" , DataType :: Int32 , false ) ,
1487+ Field :: new( "emb" , DataType :: FixedSizeList ( Arc :: clone( & item) , 2 ) , true ) ,
1488+ ] ) ) ;
1489+
1490+ let make_batch = |base : i32 | -> Vec < ArrayRef > {
1491+ let k = Arc :: new ( Int32Array :: from ( vec ! [ base, base + 1 , base] ) ) as ArrayRef ;
1492+ let emb: Vec < Option < Vec < Option < i32 > > > > = vec ! [
1493+ Some ( vec![ Some ( base) , Some ( base) ] ) ,
1494+ Some ( vec![ Some ( base + 1 ) , None ] ) ,
1495+ Some ( vec![ Some ( base) , Some ( base) ] ) , // dup of row 0
1496+ ] ;
1497+ let emb = Arc :: new (
1498+ FixedSizeListArray :: from_iter_primitive :: < Int32Type , _ , _ > ( emb, 2 ) ,
1499+ ) as ArrayRef ;
1500+ vec ! [ k, emb]
1501+ } ;
1502+
1503+ let mut column_path =
1504+ GroupValuesColumn :: < false > :: try_new ( Arc :: clone ( & schema) ) . unwrap ( ) ;
1505+ let mut rows_path = GroupValuesRows :: try_new ( Arc :: clone ( & schema) ) . unwrap ( ) ;
1506+
1507+ for base in [ 0 , 10 , 0 ] {
1508+ let cols = make_batch ( base) ;
1509+ let ( mut a, mut b) = ( vec ! [ ] , vec ! [ ] ) ;
1510+ column_path. intern ( & cols, & mut a) . unwrap ( ) ;
1511+ rows_path. intern ( & cols, & mut b) . unwrap ( ) ;
1512+ // Same grouping (partition), even if the opaque group-index labels
1513+ // differ between the vectorized and sequential paths.
1514+ assert_eq ! (
1515+ canonical_grouping( & a) ,
1516+ canonical_grouping( & b) ,
1517+ "grouping must match for batch base={base}"
1518+ ) ;
1519+ }
1520+
1521+ let total_groups = column_path. len ( ) ;
1522+ assert_eq ! ( total_groups, rows_path. len( ) ) ;
1523+
1524+ // `EmitTo::First(n)` then `EmitTo::All` on the nested column path must
1525+ // work and together emit exactly `total_groups` rows. (Cross-path value
1526+ // equality is covered by `mixed_schema_...` and the row_backed unit
1527+ // tests; group-index ordering differs here so we check counts.)
1528+ let col_first = column_path. emit ( EmitTo :: First ( 2 ) ) . unwrap ( ) ;
1529+ assert_eq ! ( col_first[ 0 ] . len( ) , 2 ) ;
1530+ let col_rest = column_path. emit ( EmitTo :: All ) . unwrap ( ) ;
1531+ assert_eq ! ( col_first[ 0 ] . len( ) + col_rest[ 0 ] . len( ) , total_groups) ;
1532+ // Column count / schema preserved on both emits.
1533+ assert_eq ! ( col_first. len( ) , schema. fields( ) . len( ) ) ;
1534+ assert_eq ! ( col_rest. len( ) , schema. fields( ) . len( ) ) ;
1535+ }
1536+
12761537 /// CRITICAL invariant: if `group_column_supported_type(t)` returns true
12771538 /// the dispatcher must accept that type at intern time, and conversely
12781539 /// if `group_column_supported_type(t)` returns false the planner must
0 commit comments