Skip to content

Commit 6e8f9c6

Browse files
ump45noseconnortsui20
authored andcommitted
Report one-row Sequence arrays as sorted for any multiplier
A Sequence with a single element has no adjacent pair to compare, so it is sorted and strictly sorted whatever its multiplier. The constructor stats, the Sequence is_sorted aggregate kernel and the generic sortedness helper all answered from the multiplier (or a cached hint) alone, so a one-row Sequence with a negative multiplier reported unsorted, and one with a zero multiplier reported not strictly sorted. Decoding also restores the stored sortedness hints, which older writers computed the same way, so a decoded one-row array now takes the intrinsic answer over those hints. Closes vortex-data#10579 Signed-off-by: Vincent <[email protected]>
1 parent 3cc1a5f commit 6e8f9c6

4 files changed

Lines changed: 174 additions & 32 deletions

File tree

‎encodings/sequence/src/array.rs‎

Lines changed: 78 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -456,15 +456,20 @@ impl ValidityVTable<Sequence> for Sequence {
456456
pub struct Sequence;
457457

458458
impl Sequence {
459-
fn stats(multiplier: PValue) -> StatsSet {
460-
// A sequence A[i] = base + i * multiplier is sorted iff multiplier >= 0,
461-
// and strictly sorted iff multiplier > 0.
462-
let (is_sorted, is_strict_sorted) = match_each_pvalue!(
463-
multiplier,
464-
uint: |v| { (true, v > 0) },
465-
int: |v| { (v >= 0, v > 0) },
466-
float: |_v| { unreachable!("float multiplier not supported") }
467-
);
459+
fn stats(multiplier: PValue, length: usize) -> StatsSet {
460+
// A sequence A[i] = base + i * multiplier with at least two elements is sorted iff
461+
// multiplier >= 0, and strictly sorted iff multiplier > 0. A single element has no
462+
// adjacent pair to compare, so it is strictly sorted whatever the multiplier.
463+
let (is_sorted, is_strict_sorted) = if length <= 1 {
464+
(true, true)
465+
} else {
466+
match_each_pvalue!(
467+
multiplier,
468+
uint: |v| { (true, v > 0) },
469+
int: |v| { (v >= 0, v > 0) },
470+
float: |_v| { unreachable!("float multiplier not supported") }
471+
)
472+
};
468473

469474
// SAFETY: we don't have duplicate stats.
470475
unsafe {
@@ -495,7 +500,7 @@ impl Sequence {
495500
let dtype = DType::Primitive(ptype, nullability);
496501
let (base, multiplier) = SequenceData::normalize(base, multiplier, ptype)
497502
.vortex_expect("SequenceArray parts must be representable in the output ptype");
498-
let stats = Self::stats(multiplier);
503+
let stats = Self::stats(multiplier, length);
499504
let data = unsafe { SequenceData::new_unchecked(base, multiplier) };
500505
unsafe {
501506
Array::from_parts_unchecked(ArrayParts::new(
@@ -519,7 +524,7 @@ impl Sequence {
519524
) -> VortexResult<SequenceArray> {
520525
let dtype = DType::Primitive(ptype, nullability);
521526
let data = SequenceData::try_new(base, multiplier, ptype, nullability, length)?;
522-
let stats = Self::stats(data.multiplier());
527+
let stats = Self::stats(data.multiplier(), length);
523528
Ok(unsafe {
524529
Array::from_parts_unchecked(ArrayParts::new(
525530
Sequence,
@@ -542,7 +547,7 @@ impl Sequence {
542547
let ptype = T::PTYPE;
543548
let dtype = DType::Primitive(ptype, nullability);
544549
let data = SequenceData::try_new_typed(base, multiplier, nullability, length)?;
545-
let stats = Self::stats(data.multiplier());
550+
let stats = Self::stats(data.multiplier(), length);
546551
Ok(unsafe {
547552
Array::from_parts_unchecked(ArrayParts::new(
548553
Sequence,
@@ -687,6 +692,67 @@ mod tests {
687692
Ok(())
688693
}
689694

695+
#[rstest]
696+
fn singleton_is_strict_sorted(#[values(-1i64, 0, 3)] multiplier: i64) -> VortexResult<()> {
697+
let typed = Sequence::try_new_typed(10i64, multiplier, Nullability::NonNullable, 1)?;
698+
let untyped = Sequence::try_new(
699+
PValue::from(10i64),
700+
PValue::from(multiplier),
701+
PType::I64,
702+
Nullability::NonNullable,
703+
1,
704+
)?;
705+
let sliced = Sequence::try_new_typed(10i64, multiplier, Nullability::NonNullable, 4)?
706+
.into_array()
707+
.slice(1..2)?;
708+
assert!(sliced.is::<Sequence>());
709+
710+
for array in [typed.into_array(), untyped.into_array(), sliced] {
711+
for stat in [Stat::IsSorted, Stat::IsStrictSorted] {
712+
let value = array
713+
.statistics()
714+
.with_typed_stats_set(|s| s.get_as::<bool>(stat));
715+
assert_eq!(value, StatPrecision::Exact(true));
716+
}
717+
}
718+
Ok(())
719+
}
720+
721+
#[test]
722+
fn decode_keeps_singleton_sorted_over_stale_hints() -> VortexResult<()> {
723+
let array = Sequence::try_new_typed(10i64, -1, Nullability::NonNullable, 1)?.into_array();
724+
// Older writers stored the multiplier-only answer for one-row sequences.
725+
array
726+
.statistics()
727+
.set(Stat::IsSorted, StatPrecision::Exact(false.into()));
728+
array
729+
.statistics()
730+
.set(Stat::IsStrictSorted, StatPrecision::Exact(false.into()));
731+
732+
let dtype = array.dtype().clone();
733+
let ctx = ArrayContext::empty();
734+
let serialized = array.serialize(&ctx, &SESSION, &SerializeOptions::default())?;
735+
let mut concat = ByteBufferMut::empty();
736+
for buf in serialized {
737+
concat.extend_from_slice(buf.as_ref());
738+
}
739+
740+
let decoded = SerializedArray::try_from(concat.freeze())?.decode(
741+
&dtype,
742+
1,
743+
&ReadContext::new(ctx.to_ids()),
744+
&SESSION,
745+
)?;
746+
747+
for stat in [Stat::IsSorted, Stat::IsStrictSorted] {
748+
let value = decoded
749+
.statistics()
750+
.with_typed_stats_set(|s| s.get_as::<bool>(stat));
751+
assert_eq!(value, StatPrecision::Exact(true));
752+
}
753+
Ok(())
754+
}
755+
690756
// This is regression test for an issue caught by the fuzzer, where SequenceArrays with
691757
// multiplier > i64::MAX were unable to be constructed.
692758
#[test]

‎encodings/sequence/src/compute/is_sorted.rs‎

Lines changed: 62 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -15,8 +15,8 @@ use crate::Sequence;
1515

1616
/// Sequence-specific is_sorted kernel.
1717
///
18-
/// A sequence `A[i] = base + i * multiplier` is sorted iff multiplier >= 0,
19-
/// and strict sorted iff multiplier > 0.
18+
/// A sequence `A[i] = base + i * multiplier` with at least two elements is sorted iff
19+
/// multiplier >= 0, and strict sorted iff multiplier > 0.
2020
#[derive(Debug)]
2121
pub(crate) struct SequenceIsSortedKernel;
2222

@@ -35,16 +35,21 @@ impl DynAggregateKernel for SequenceIsSortedKernel {
3535
return Ok(None);
3636
};
3737

38-
let m = array.multiplier();
39-
let result = match_each_native_ptype!(m.ptype(), |P| {
40-
m.cast::<P>().map(|x| {
41-
if options.strict {
42-
x > zero::<P>()
43-
} else {
44-
x >= zero::<P>()
45-
}
46-
})
47-
})?;
38+
// A single element is strictly sorted whatever the multiplier.
39+
let result = if array.len() <= 1 {
40+
true
41+
} else {
42+
let m = array.multiplier();
43+
match_each_native_ptype!(m.ptype(), |P| {
44+
m.cast::<P>().map(|x| {
45+
if options.strict {
46+
x > zero::<P>()
47+
} else {
48+
x >= zero::<P>()
49+
}
50+
})
51+
})?
52+
};
4853

4954
Ok(Some(IsSorted::make_partial(
5055
batch,
@@ -54,3 +59,48 @@ impl DynAggregateKernel for SequenceIsSortedKernel {
5459
)?))
5560
}
5661
}
62+
63+
#[cfg(test)]
64+
mod tests {
65+
use std::sync::LazyLock;
66+
67+
use rstest::rstest;
68+
use vortex_array::IntoArray;
69+
use vortex_array::VortexSessionExecute;
70+
use vortex_array::aggregate_fn::AggregateFnVTableExt;
71+
use vortex_array::aggregate_fn::fns::is_sorted::IsSorted;
72+
use vortex_array::aggregate_fn::fns::is_sorted::IsSortedOptions;
73+
use vortex_array::aggregate_fn::kernels::DynAggregateKernel;
74+
use vortex_array::dtype::Nullability;
75+
use vortex_error::VortexResult;
76+
use vortex_session::VortexSession;
77+
78+
use super::SequenceIsSortedKernel;
79+
use crate::Sequence;
80+
81+
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
82+
let session = vortex_array::array_session();
83+
crate::initialize(&session);
84+
session
85+
});
86+
87+
#[rstest]
88+
fn singleton_is_sorted_for_any_multiplier(
89+
#[values(-1i64, 0, 3)] multiplier: i64,
90+
#[values(false, true)] strict: bool,
91+
) -> VortexResult<()> {
92+
let mut ctx = SESSION.create_execution_ctx();
93+
let array =
94+
Sequence::try_new_typed(10i64, multiplier, Nullability::NonNullable, 1)?.into_array();
95+
96+
let result = SequenceIsSortedKernel.aggregate(
97+
&IsSorted.bind(IsSortedOptions { strict }),
98+
&array,
99+
&mut ctx,
100+
)?;
101+
102+
let expected = IsSorted::make_partial(&array, true, strict, &mut ctx)?;
103+
assert_eq!(result, Some(expected));
104+
Ok(())
105+
}
106+
}

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

Lines changed: 24 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -82,16 +82,17 @@ fn is_sorted_impl(array: &ArrayRef, strict: bool, ctx: &mut ExecutionCtx) -> Vor
8282
Stat::IsSorted
8383
};
8484

85+
// Arrays with 0 or 1 elements are (strict) sorted. Check this before the cached
86+
// statistics so that a stale hint cannot contradict it.
87+
if array.len() <= 1 {
88+
return Ok(true);
89+
}
90+
8591
// Short-circuit using cached array statistics.
8692
if let Precision::Exact(value) = array.statistics().get_as::<bool>(stat) {
8793
return Ok(value);
8894
}
8995

90-
// Arrays with 0 or 1 elements are (strict) sorted.
91-
if array.len() <= 1 {
92-
return Ok(true);
93-
}
94-
9596
// Constant and null arrays are always sorted, but not strict sorted.
9697
if array.is::<Constant>() || array.is::<Null>() {
9798
let result = !strict;
@@ -618,9 +619,27 @@ mod tests {
618619
use crate::dtype::DType;
619620
use crate::dtype::Nullability;
620621
use crate::dtype::PType;
622+
use crate::expr::stats::Precision;
623+
use crate::expr::stats::Stat;
621624
use crate::scalar::Scalar;
622625
use crate::validity::Validity;
623626

627+
#[test]
628+
fn singleton_ignores_stale_sortedness_stats() -> VortexResult<()> {
629+
let mut ctx = array_session().create_execution_ctx();
630+
let array = buffer![7i32].into_array();
631+
array
632+
.statistics()
633+
.set(Stat::IsSorted, Precision::Exact(false.into()));
634+
array
635+
.statistics()
636+
.set(Stat::IsStrictSorted, Precision::Exact(false.into()));
637+
638+
assert!(is_sorted(&array, &mut ctx)?);
639+
assert!(is_strict_sorted(&array, &mut ctx)?);
640+
Ok(())
641+
}
642+
624643
// Tests migrated from compute/is_sorted.rs
625644
#[test]
626645
fn test_is_sorted() -> VortexResult<()> {

‎vortex-array/src/serde.rs‎

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,8 @@ use crate::array::new_foreign_array;
3232
use crate::buffer::BufferHandle;
3333
use crate::dtype::DType;
3434
use crate::dtype::TryFromBytes;
35+
use crate::expr::stats::Precision;
36+
use crate::expr::stats::Stat;
3537
use crate::flatbuffers::FlatBuffer;
3638
use crate::flatbuffers::WriteFlatBuffer;
3739
use crate::flatbuffers::array as fba;
@@ -418,9 +420,14 @@ impl SerializedArray {
418420

419421
// Populate statistics from the serialized array.
420422
if let Some(stats) = self.flatbuffer().stats() {
421-
decoded
422-
.statistics()
423-
.set_all(StatsSet::from_flatbuffer(&stats, dtype, session)?);
423+
let mut stats = StatsSet::from_flatbuffer(&stats, dtype, session)?;
424+
// Arrays with 0 or 1 elements are always (strict) sorted. Older writers could store
425+
// a sortedness hint that says otherwise, so the intrinsic fact takes precedence.
426+
if len <= 1 {
427+
stats.set(Stat::IsSorted, Precision::Exact(true.into()));
428+
stats.set(Stat::IsStrictSorted, Precision::Exact(true.into()));
429+
}
430+
decoded.statistics().set_all(stats);
424431
}
425432

426433
Ok(decoded)

0 commit comments

Comments
 (0)