Skip to content

Commit 24472cb

Browse files
committed
Support file stats on nested struct fields (vortex-data#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 adf3bfa commit 24472cb

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;
@@ -118,6 +119,10 @@ pub trait DynAccumulator: 'static + Send {
118119
/// Whether the accumulator's result is fully determined.
119120
fn is_saturated(&self) -> bool;
120121

122+
/// Whether the current result can satisfy `requested`, taking the accumulated state into
123+
/// account. See [`AggregateFnVTable::partial_can_satisfy`].
124+
fn can_satisfy(&self, requested: &AggregateFnRef) -> AggregateFnSatisfaction;
125+
121126
/// Reset the accumulator's state to the empty group.
122127
fn reset(&mut self);
123128

@@ -292,6 +297,15 @@ impl<V: AggregateFnVTable> DynAccumulator for Accumulator<V> {
292297
})
293298
}
294299

300+
fn can_satisfy(&self, requested: &AggregateFnRef) -> AggregateFnSatisfaction {
301+
let options = self.aggregate_fn.as_::<V>();
302+
// Without a partial nothing was accumulated yet, so only the options can be consulted.
303+
match &self.partial {
304+
Some(partial) => self.vtable.partial_can_satisfy(options, partial, requested),
305+
None => self.vtable.can_satisfy(options, requested),
306+
}
307+
}
308+
295309
fn reset(&mut self) {
296310
self.partial = None;
297311
}

‎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;
@@ -34,7 +35,6 @@ use crate::dtype::DType;
3435
use crate::dtype::FieldNames;
3536
use crate::dtype::Nullability;
3637
use crate::dtype::StructFields;
37-
use crate::partial_ord::partial_max;
3838
use crate::scalar::Scalar;
3939
use crate::scalar::ScalarTruncation;
4040
use crate::scalar::upper_bound;
@@ -66,27 +66,59 @@ pub struct BoundedMax;
6666

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

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

7892
impl BoundedMaxPartial {
79-
fn merge_bound(&mut self, max: Scalar) {
80-
if max.is_null() {
93+
fn merge_bound(&mut self, bound: Scalar, exact: bool) {
94+
if bound.is_null() {
8195
return;
8296
}
8397

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

@@ -97,7 +129,7 @@ impl BoundedMaxPartial {
97129
fn final_scalar(&self, args: AggregateArgs<'_, BoundedMaxOptions>) -> VortexResult<Scalar> {
98130
let dtype = args.return_dtype.clone();
99131
match &self.state {
100-
BoundedMaxState::Value(max) => max.cast(&dtype),
132+
BoundedMaxState::Exact(bound) | BoundedMaxState::Inexact(bound) => bound.cast(&dtype),
101133
BoundedMaxState::Empty | BoundedMaxState::Unknown => Ok(Scalar::null(dtype)),
102134
}
103135
}
@@ -184,6 +216,27 @@ impl AggregateFnVTable for BoundedMax {
184216
}
185217
}
186218

219+
fn partial_can_satisfy(
220+
&self,
221+
options: &Self::Options,
222+
partial: &Self::Partial,
223+
requested: &AggregateFnRef,
224+
) -> AggregateFnSatisfaction {
225+
let satisfaction = self.can_satisfy(options, requested);
226+
let untruncated = matches!(
227+
partial.state,
228+
BoundedMaxState::Empty | BoundedMaxState::Exact(_)
229+
);
230+
if satisfaction == AggregateFnSatisfaction::Approximate
231+
&& untruncated
232+
&& requested.is::<Max>()
233+
{
234+
AggregateFnSatisfaction::Exact
235+
} else {
236+
satisfaction
237+
}
238+
}
239+
187240
fn partial_dtype(&self, options: &Self::Options, input_dtype: &DType) -> Option<DType> {
188241
supported_dtype(options, input_dtype).map(make_bounded_max_partial_dtype)
189242
}
@@ -227,7 +280,8 @@ impl AggregateFnVTable for BoundedMax {
227280
} else if bound.is_null() {
228281
BoundedMaxState::Empty
229282
} else {
230-
BoundedMaxState::Value(bound)
283+
// Serialized partials don't record exactness.
284+
BoundedMaxState::Inexact(bound)
231285
}
232286
};
233287
Ok(BoundedMaxPartial { state })
@@ -241,7 +295,8 @@ impl AggregateFnVTable for BoundedMax {
241295
) -> VortexResult<Self::Partial> {
242296
match second.state {
243297
BoundedMaxState::Empty => {}
244-
BoundedMaxState::Value(max) => first.merge_bound(max),
298+
BoundedMaxState::Exact(bound) => first.merge_bound(bound, true),
299+
BoundedMaxState::Inexact(bound) => first.merge_bound(bound, false),
245300
BoundedMaxState::Unknown => first.unknown(),
246301
}
247302
Ok(first)
@@ -256,10 +311,10 @@ impl AggregateFnVTable for BoundedMax {
256311
let bound_dtype = args.dtype.as_nullable();
257312
match &partial.state {
258313
BoundedMaxState::Empty => Ok(Scalar::null(dtype)),
259-
BoundedMaxState::Value(max) => Ok(Scalar::struct_(
314+
BoundedMaxState::Exact(bound) | BoundedMaxState::Inexact(bound) => Ok(Scalar::struct_(
260315
dtype,
261316
vec![
262-
max.cast(&bound_dtype)?,
317+
bound.cast(&bound_dtype)?,
263318
Scalar::bool(false, Nullability::NonNullable),
264319
],
265320
)),
@@ -298,7 +353,7 @@ impl AggregateFnVTable for BoundedMax {
298353
return Ok(());
299354
};
300355
match truncate_max(result.max, args.options.max_bytes.get())? {
301-
Some(bound) => partial.merge_bound(bound),
356+
Some((bound, truncated)) => partial.merge_bound(bound, !truncated),
302357
None => partial.unknown(),
303358
}
304359
Ok(())
@@ -327,22 +382,21 @@ fn supported_dtype<'a>(_options: &BoundedMaxOptions, input_dtype: &'a DType) ->
327382
.map(|_| input_dtype)
328383
}
329384

330-
fn truncate_max(value: Scalar, max_bytes: usize) -> VortexResult<Option<Scalar>> {
385+
/// Returns the upper bound and whether it was truncated, or `None` if no bound fits `max_bytes`.
386+
fn truncate_max(value: Scalar, max_bytes: usize) -> VortexResult<Option<(Scalar, bool)>> {
331387
let nullability = value.dtype().nullability();
332388
match value.dtype() {
333-
DType::Utf8(_) => {
334-
Ok(
335-
upper_bound(BufferString::from_scalar(value)?, max_bytes, nullability)
336-
.map(|(bound, _)| bound),
337-
)
338-
}
339-
DType::Binary(_) => {
340-
Ok(
341-
upper_bound(ByteBuffer::from_scalar(value)?, max_bytes, nullability)
342-
.map(|(bound, _)| bound),
343-
)
344-
}
345-
_ => Ok(Some(value)),
389+
DType::Utf8(_) => Ok(upper_bound(
390+
BufferString::from_scalar(value)?,
391+
max_bytes,
392+
nullability,
393+
)),
394+
DType::Binary(_) => Ok(upper_bound(
395+
ByteBuffer::from_scalar(value)?,
396+
max_bytes,
397+
nullability,
398+
)),
399+
_ => Ok(Some((value, false))),
346400
}
347401
}
348402

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

0 commit comments

Comments
 (0)