Skip to content

Commit 70e7a34

Browse files
thorfourclaude
authored andcommitted
Support file stats on nested struct fields (#6389)
Store file-level statistics via a post-order walk of the DType tree, so nested struct fields get whole-file pruning instead of only top-level columns. Each leaf gets a stats entry, and each nullable struct gets a trailing null-count entry. A new `is_nested` footer flag keeps old files readable via the legacy top-level-only layout. Signed-off-by: "Thor" <[email protected]> Signed-off-by: Thor <[email protected]>
1 parent ea4ba3a commit 70e7a34

26 files changed

Lines changed: 3047 additions & 875 deletions

File tree

‎vortex-array/src/aggregate_fn/accumulator.rs‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@ use crate::ExecutionCtx;
1515
use crate::aggregate_fn::AggregateDTypes;
1616
use crate::aggregate_fn::AggregateFn;
1717
use crate::aggregate_fn::AggregateFnRef;
18+
use crate::aggregate_fn::AggregateFnSatisfaction;
1819
use crate::aggregate_fn::AggregateFnVTable;
1920
use crate::aggregate_fn::session::AggregateFnSessionExt;
2021
use crate::columnar::AnyColumnar;
@@ -192,6 +193,10 @@ pub trait DynAccumulator: 'static + Send {
192193
/// Whether the accumulator's result is fully determined.
193194
fn is_saturated(&self) -> bool;
194195

196+
/// Whether the current result can satisfy `requested`, taking the accumulated state into
197+
/// account. See [`AggregateFnVTable::partial_can_satisfy`].
198+
fn can_satisfy(&self, requested: &AggregateFnRef) -> AggregateFnSatisfaction;
199+
195200
/// Reset the accumulator's state to the empty group.
196201
fn reset(&mut self);
197202

@@ -318,6 +323,15 @@ impl<V: AggregateFnVTable> DynAccumulator for Accumulator<V> {
318323
})
319324
}
320325

326+
fn can_satisfy(&self, requested: &AggregateFnRef) -> AggregateFnSatisfaction {
327+
let options = self.aggregate_fn.as_::<V>();
328+
// Without a partial nothing was accumulated yet, so only the options can be consulted.
329+
match &self.partial {
330+
Some(partial) => self.vtable.partial_can_satisfy(options, partial, requested),
331+
None => self.vtable.can_satisfy(options, requested),
332+
}
333+
}
334+
321335
fn reset(&mut self) {
322336
self.partial = None;
323337
}

‎vortex-array/src/aggregate_fn/fns/bounded_max/mod.rs‎

Lines changed: 147 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
// SPDX-License-Identifier: Apache-2.0
22
// SPDX-FileCopyrightText: Copyright the Vortex contributors
33

4+
use std::cmp::Ordering;
45
use std::fmt::Display;
56
use std::fmt::Formatter;
67
use std::num::NonZeroUsize;
@@ -33,7 +34,6 @@ use crate::dtype::DType;
3334
use crate::dtype::FieldNames;
3435
use crate::dtype::Nullability;
3536
use crate::dtype::StructFields;
36-
use crate::partial_ord::partial_max;
3737
use crate::scalar::Scalar;
3838
use crate::scalar::ScalarTruncation;
3939
use crate::scalar::upper_bound;
@@ -65,27 +65,59 @@ pub struct BoundedMax;
6565

6666
enum BoundedMaxState {
6767
Empty,
68-
Value(Scalar),
68+
/// The true maximum: it fit within the byte bound, so it was never truncated.
69+
Exact(Scalar),
70+
/// An upper bound of the true maximum, either because the maximum was truncated or because
71+
/// it was combined from a serialized partial, which doesn't record exactness.
72+
Inexact(Scalar),
6973
Unknown,
7074
}
7175

76+
impl BoundedMaxState {
77+
fn bound(bound: Scalar, exact: bool) -> Self {
78+
if exact {
79+
Self::Exact(bound)
80+
} else {
81+
Self::Inexact(bound)
82+
}
83+
}
84+
}
85+
7286
/// Partial accumulator state for the bounded maximum aggregate.
7387
pub struct BoundedMaxPartial {
7488
state: BoundedMaxState,
7589
}
7690

7791
impl BoundedMaxPartial {
78-
fn merge_bound(&mut self, max: Scalar) {
79-
if max.is_null() {
92+
fn merge_bound(&mut self, bound: Scalar, exact: bool) {
93+
if bound.is_null() {
8094
return;
8195
}
8296

83-
self.state = match std::mem::replace(&mut self.state, BoundedMaxState::Empty) {
84-
BoundedMaxState::Empty => BoundedMaxState::Value(max),
85-
BoundedMaxState::Value(current) => BoundedMaxState::Value(
86-
partial_max(max, current).vortex_expect("incomparable bounded max scalars"),
87-
),
88-
BoundedMaxState::Unknown => BoundedMaxState::Unknown,
97+
let (current, current_exact) =
98+
match std::mem::replace(&mut self.state, BoundedMaxState::Empty) {
99+
BoundedMaxState::Empty => {
100+
self.state = BoundedMaxState::bound(bound, exact);
101+
return;
102+
}
103+
BoundedMaxState::Unknown => {
104+
self.state = BoundedMaxState::Unknown;
105+
return;
106+
}
107+
BoundedMaxState::Exact(current) => (current, true),
108+
BoundedMaxState::Inexact(current) => (current, false),
109+
};
110+
111+
// The larger bound wins. It is the true maximum iff it was not truncated: every other
112+
// value is at most its own bound, which is below the winner. On a tie, either side being
113+
// exact means the true maximum reaches the bound.
114+
self.state = match bound
115+
.partial_cmp(&current)
116+
.vortex_expect("incomparable bounded max scalars")
117+
{
118+
Ordering::Greater => BoundedMaxState::bound(bound, exact),
119+
Ordering::Less => BoundedMaxState::bound(current, current_exact),
120+
Ordering::Equal => BoundedMaxState::bound(current, exact || current_exact),
89121
};
90122
}
91123

@@ -96,7 +128,7 @@ impl BoundedMaxPartial {
96128
fn final_scalar(&self, args: AggregateArgs<'_, BoundedMaxOptions>) -> VortexResult<Scalar> {
97129
let dtype = args.return_dtype.clone();
98130
match &self.state {
99-
BoundedMaxState::Value(max) => max.cast(&dtype),
131+
BoundedMaxState::Exact(bound) | BoundedMaxState::Inexact(bound) => bound.cast(&dtype),
100132
BoundedMaxState::Empty | BoundedMaxState::Unknown => Ok(Scalar::null(dtype)),
101133
}
102134
}
@@ -183,6 +215,27 @@ impl AggregateFnVTable for BoundedMax {
183215
}
184216
}
185217

218+
fn partial_can_satisfy(
219+
&self,
220+
options: &Self::Options,
221+
partial: &Self::Partial,
222+
requested: &AggregateFnRef,
223+
) -> AggregateFnSatisfaction {
224+
let satisfaction = self.can_satisfy(options, requested);
225+
let untruncated = matches!(
226+
partial.state,
227+
BoundedMaxState::Empty | BoundedMaxState::Exact(_)
228+
);
229+
if satisfaction == AggregateFnSatisfaction::Approximate
230+
&& untruncated
231+
&& requested.is::<Max>()
232+
{
233+
AggregateFnSatisfaction::Exact
234+
} else {
235+
satisfaction
236+
}
237+
}
238+
186239
fn partial_dtype(&self, options: &Self::Options, input_dtype: &DType) -> Option<DType> {
187240
supported_dtype(options, input_dtype).map(make_bounded_max_partial_dtype)
188241
}
@@ -226,7 +279,8 @@ impl AggregateFnVTable for BoundedMax {
226279
} else if bound.is_null() {
227280
BoundedMaxState::Empty
228281
} else {
229-
BoundedMaxState::Value(bound)
282+
// Serialized partials don't record exactness.
283+
BoundedMaxState::Inexact(bound)
230284
}
231285
};
232286
Ok(BoundedMaxPartial { state })
@@ -240,7 +294,8 @@ impl AggregateFnVTable for BoundedMax {
240294
) -> VortexResult<Self::Partial> {
241295
match second.state {
242296
BoundedMaxState::Empty => {}
243-
BoundedMaxState::Value(max) => first.merge_bound(max),
297+
BoundedMaxState::Exact(bound) => first.merge_bound(bound, true),
298+
BoundedMaxState::Inexact(bound) => first.merge_bound(bound, false),
244299
BoundedMaxState::Unknown => first.unknown(),
245300
}
246301
Ok(first)
@@ -255,10 +310,10 @@ impl AggregateFnVTable for BoundedMax {
255310
let bound_dtype = args.dtype.as_nullable();
256311
match &partial.state {
257312
BoundedMaxState::Empty => Ok(Scalar::null(dtype)),
258-
BoundedMaxState::Value(max) => Ok(Scalar::struct_(
313+
BoundedMaxState::Exact(bound) | BoundedMaxState::Inexact(bound) => Ok(Scalar::struct_(
259314
dtype,
260315
vec![
261-
max.cast(&bound_dtype)?,
316+
bound.cast(&bound_dtype)?,
262317
Scalar::bool(false, Nullability::NonNullable),
263318
],
264319
)),
@@ -293,7 +348,7 @@ impl AggregateFnVTable for BoundedMax {
293348
return Ok(());
294349
};
295350
match truncate_max(result.max, args.options.max_bytes.get())? {
296-
Some(bound) => partial.merge_bound(bound),
351+
Some((bound, truncated)) => partial.merge_bound(bound, !truncated),
297352
None => partial.unknown(),
298353
}
299354
Ok(())
@@ -322,22 +377,21 @@ fn supported_dtype<'a>(_options: &BoundedMaxOptions, input_dtype: &'a DType) ->
322377
.map(|_| input_dtype)
323378
}
324379

325-
fn truncate_max(value: Scalar, max_bytes: usize) -> VortexResult<Option<Scalar>> {
380+
/// Returns the upper bound and whether it was truncated, or `None` if no bound fits `max_bytes`.
381+
fn truncate_max(value: Scalar, max_bytes: usize) -> VortexResult<Option<(Scalar, bool)>> {
326382
let nullability = value.dtype().nullability();
327383
match value.dtype() {
328-
DType::Utf8(_) => {
329-
Ok(
330-
upper_bound(BufferString::from_scalar(value)?, max_bytes, nullability)
331-
.map(|(bound, _)| bound),
332-
)
333-
}
334-
DType::Binary(_) => {
335-
Ok(
336-
upper_bound(ByteBuffer::from_scalar(value)?, max_bytes, nullability)
337-
.map(|(bound, _)| bound),
338-
)
339-
}
340-
_ => Ok(Some(value)),
384+
DType::Utf8(_) => Ok(upper_bound(
385+
BufferString::from_scalar(value)?,
386+
max_bytes,
387+
nullability,
388+
)),
389+
DType::Binary(_) => Ok(upper_bound(
390+
ByteBuffer::from_scalar(value)?,
391+
max_bytes,
392+
nullability,
393+
)),
394+
_ => Ok(Some((value, false))),
341395
}
342396
}
343397

@@ -584,4 +638,67 @@ mod tests {
584638
assert_eq!(roundtrip, options);
585639
Ok(())
586640
}
641+
642+
#[test]
643+
fn bounded_max_exactly_satisfies_max_only_when_untruncated() -> VortexResult<()> {
644+
let mut ctx = array_session().create_execution_ctx();
645+
let requested = Max.bind(NumericalAggregateOpts::skip_nans());
646+
let new_acc = || {
647+
Accumulator::try_new(
648+
BoundedMax,
649+
BoundedMaxOptions {
650+
max_bytes: max_bytes(4),
651+
},
652+
VarBinViewArray::from_iter_str(["x"]).dtype().clone(),
653+
)
654+
};
655+
656+
// Every value fits the bound, so the bound is the true extremum.
657+
let mut acc = new_acc()?;
658+
acc.accumulate(
659+
&VarBinViewArray::from_iter_str(["b", "abc"]).into_array(),
660+
&mut ctx,
661+
)?;
662+
assert_eq!(acc.can_satisfy(&requested), AggregateFnSatisfaction::Exact);
663+
664+
// A truncated value that isn't the extremum doesn't affect exactness.
665+
acc.accumulate(
666+
&VarBinViewArray::from_iter_str(["aaaaa"]).into_array(),
667+
&mut ctx,
668+
)?;
669+
assert_eq!(acc.can_satisfy(&requested), AggregateFnSatisfaction::Exact);
670+
671+
// A truncated extremum makes the bound approximate.
672+
acc.accumulate(
673+
&VarBinViewArray::from_iter_str(["bbbbb"]).into_array(),
674+
&mut ctx,
675+
)?;
676+
assert_eq!(
677+
acc.can_satisfy(&requested),
678+
AggregateFnSatisfaction::Approximate
679+
);
680+
681+
// Exactness isn't serialized, so a winning partial combined from its scalar form is
682+
// approximate even though it was exact where it was computed.
683+
let mut source = new_acc()?;
684+
source.accumulate(
685+
&VarBinViewArray::from_iter_str(["b"]).into_array(),
686+
&mut ctx,
687+
)?;
688+
assert_eq!(
689+
source.can_satisfy(&requested),
690+
AggregateFnSatisfaction::Exact
691+
);
692+
let mut acc = new_acc()?;
693+
acc.accumulate(
694+
&VarBinViewArray::from_iter_str(["a"]).into_array(),
695+
&mut ctx,
696+
)?;
697+
acc.combine_partials(source.partial_scalar()?)?;
698+
assert_eq!(
699+
acc.can_satisfy(&requested),
700+
AggregateFnSatisfaction::Approximate
701+
);
702+
Ok(())
703+
}
587704
}

0 commit comments

Comments
 (0)