Skip to content

Commit 306174f

Browse files
committed
feat(physical-plan): add generic Rows-backed GroupColumn to keep mixed schemas on the column-wise path
Add `RowsGroupColumn`, a generic `GroupColumn` backed by a single-field `RowConverter` from arrow's row format. Route nested types (`Struct`, `List`, `LargeList`, `FixedSizeList`, and recursive combinations arrow's row converter can encode) to it via `group_column_supported_type` / `make_group_column`. Before this, a single nested column in a GROUP BY key made `supported_schema` return `false` and the whole aggregation fell back to the row-wise `GroupValuesRows`, even when every other column would have qualified for the column-wise fast path. With the generic fallback, only the nested column pays the row-encoding cost; the native columns keep their compact column-wise storage. Impact (measured by `mixed_schema_column_path_uses_less_memory_than_rows_fallback` with 4000 groups of `8 × Int64 + 1 × FixedSizeList<Int64, 4>`): - old (all-rows fallback): 1096 KB - new (column-wise + row-backed nested column): **594 KB (54.2%)** Correctness: - Hashing (`create_hashes` on the raw input columns) already supports nested types, and the caller-side `-0.0/NaN` normalization performed for `GroupValuesRows` keeps hashing aligned with the row-format equality this column implements. Covered by `nested_float_edge_cases_match_rows_fallback`. - Multi-batch streaming intern + `EmitTo::First` / `take_n` covered by `multi_batch_and_emit_first_matches_rows_fallback`. - FSL / Struct roundtrip + `supports_type` invariant covered by the unit tests inside `row_backed`. Follow-ups tracked separately: - Cover types `RowConverter` cannot encode (currently a moving target; if the arrow-rs release DataFusion pins encodes them all — including Map — the fallback is complete). - With full coverage, retire `GroupValuesRows` entirely (motivation: apache#23404). Refs: apache#23404, apache#22715.
1 parent a8d1af6 commit 306174f

3 files changed

Lines changed: 643 additions & 1 deletion

File tree

‎datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs‎

Lines changed: 261 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,13 +21,15 @@ mod boolean;
2121
mod bytes;
2222
pub mod bytes_view;
2323
pub mod primitive;
24+
pub mod row_backed;
2425

2526
use std::mem::{self, size_of};
2627

2728
use crate::aggregates::group_values::GroupValues;
2829
use crate::aggregates::group_values::multi_group_by::{
2930
boolean::BooleanGroupValueBuilder, bytes::ByteGroupValueBuilder,
3031
bytes_view::ByteViewGroupValueBuilder, primitive::PrimitiveGroupValueBuilder,
32+
row_backed::RowsGroupColumn,
3133
};
3234
use arrow::array::{Array, ArrayRef, BooleanBufferBuilder};
3335
use 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.
925927
fn 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

Comments
 (0)