Skip to content

Commit f46a4e1

Browse files
committed
Fix sortedness for singleton sequences
Signed-off-by: Connor Tsui <[email protected]>
1 parent bb58423 commit f46a4e1

2 files changed

Lines changed: 120 additions & 19 deletions

File tree

‎encodings/sequence/src/array.rs‎

Lines changed: 108 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -449,9 +449,9 @@ impl ValidityVTable<Sequence> for Sequence {
449449
pub struct Sequence;
450450

451451
impl Sequence {
452-
fn stats(multiplier: PValue) -> StatsSet {
453-
// A sequence A[i] = base + i * multiplier is sorted iff multiplier >= 0,
454-
// and strictly sorted iff multiplier > 0.
452+
fn stats(multiplier: PValue, length: usize) -> StatsSet {
453+
// With at least two rows, A[i] = base + i * multiplier is sorted iff multiplier >= 0,
454+
// and strictly sorted iff multiplier > 0. Shorter sequences have no unordered pair.
455455
let (is_sorted, is_strict_sorted) = match_each_pvalue!(
456456
multiplier,
457457
uint: |v| { (true, v > 0) },
@@ -462,10 +462,13 @@ impl Sequence {
462462
// SAFETY: we don't have duplicate stats.
463463
unsafe {
464464
StatsSet::new_unchecked(smallvec![
465-
(Stat::IsSorted, StatPrecision::Exact(is_sorted.into())),
465+
(
466+
Stat::IsSorted,
467+
StatPrecision::Exact((length <= 1 || is_sorted).into())
468+
),
466469
(
467470
Stat::IsStrictSorted,
468-
StatPrecision::Exact(is_strict_sorted.into()),
471+
StatPrecision::Exact((length <= 1 || is_strict_sorted).into()),
469472
),
470473
])
471474
}
@@ -488,7 +491,7 @@ impl Sequence {
488491
let dtype = DType::Primitive(ptype, nullability);
489492
let (base, multiplier) = SequenceData::normalize(base, multiplier, ptype)
490493
.vortex_expect("SequenceArray parts must be representable in the output ptype");
491-
let stats = Self::stats(multiplier);
494+
let stats = Self::stats(multiplier, length);
492495
let data = unsafe { SequenceData::new_unchecked(base, multiplier) };
493496
unsafe { Array::from_parts_unchecked(ArrayParts::new(Sequence, dtype, length, data)) }
494497
.with_stats_set(stats)
@@ -504,7 +507,7 @@ impl Sequence {
504507
) -> VortexResult<SequenceArray> {
505508
let dtype = DType::Primitive(ptype, nullability);
506509
let data = SequenceData::try_new(base, multiplier, ptype, nullability, length)?;
507-
let stats = Self::stats(data.multiplier());
510+
let stats = Self::stats(data.multiplier(), length);
508511
Ok(
509512
unsafe { Array::from_parts_unchecked(ArrayParts::new(Sequence, dtype, length, data)) }
510513
.with_stats_set(stats),
@@ -521,7 +524,7 @@ impl Sequence {
521524
let ptype = T::PTYPE;
522525
let dtype = DType::Primitive(ptype, nullability);
523526
let data = SequenceData::try_new_typed(base, multiplier, nullability, length)?;
524-
let stats = Self::stats(data.multiplier());
527+
let stats = Self::stats(data.multiplier(), length);
525528
Ok(
526529
unsafe { Array::from_parts_unchecked(ArrayParts::new(Sequence, dtype, length, data)) }
527530
.with_stats_set(stats),
@@ -539,6 +542,12 @@ mod tests {
539542
use vortex_array::EqMode;
540543
use vortex_array::IntoArray;
541544
use vortex_array::VortexSessionExecute;
545+
use vortex_array::aggregate_fn::Accumulator;
546+
use vortex_array::aggregate_fn::DynAccumulator;
547+
use vortex_array::aggregate_fn::fns::is_sorted::IsSorted;
548+
use vortex_array::aggregate_fn::fns::is_sorted::IsSortedOptions;
549+
use vortex_array::aggregate_fn::fns::is_sorted::is_sorted;
550+
use vortex_array::aggregate_fn::fns::is_sorted::is_strict_sorted;
542551
use vortex_array::arrays::PrimitiveArray;
543552
use vortex_array::assert_arrays_eq;
544553
use vortex_array::dtype::DType;
@@ -612,6 +621,97 @@ mod tests {
612621
assert!(Sequence::try_new_typed(-128i8, -1i8, Nullability::NonNullable, 2).is_err());
613622
}
614623

624+
#[rstest]
625+
#[case::descending(-1i64)]
626+
#[case::constant(0i64)]
627+
#[case::ascending(1i64)]
628+
fn singleton_sequence_has_sorted_seeds(
629+
#[case] multiplier: i64,
630+
#[values(Nullability::NonNullable, Nullability::Nullable)] nullability: Nullability,
631+
) -> VortexResult<()> {
632+
let mut ctx = SESSION.create_execution_ctx();
633+
let arrays = [
634+
Sequence::try_new_typed(10i64, multiplier, nullability, 1)?,
635+
Sequence::try_new(10i64.into(), multiplier.into(), PType::I64, nullability, 1)?,
636+
];
637+
638+
for array in arrays {
639+
for stat in [Stat::IsSorted, Stat::IsStrictSorted] {
640+
assert_eq!(
641+
array
642+
.statistics()
643+
.with_typed_stats_set(|s| s.get_as::<bool>(stat)),
644+
StatPrecision::Exact(true),
645+
);
646+
}
647+
assert!(is_sorted(array.as_ref(), &mut ctx)?);
648+
assert!(is_strict_sorted(array.as_ref(), &mut ctx)?);
649+
}
650+
651+
Ok(())
652+
}
653+
654+
#[rstest]
655+
#[case::descending(-1i64)]
656+
#[case::constant(0i64)]
657+
#[case::ascending(1i64)]
658+
fn singleton_sequence_slice_has_sorted_seeds(#[case] multiplier: i64) -> VortexResult<()> {
659+
let mut ctx = SESSION.create_execution_ctx();
660+
let array =
661+
Sequence::try_new_typed(10i64, multiplier, Nullability::NonNullable, 3)?.slice(1..2)?;
662+
663+
for stat in [Stat::IsSorted, Stat::IsStrictSorted] {
664+
assert_eq!(
665+
array
666+
.statistics()
667+
.with_typed_stats_set(|s| s.get_as::<bool>(stat)),
668+
StatPrecision::Exact(true),
669+
);
670+
}
671+
assert!(is_sorted(&array, &mut ctx)?);
672+
assert!(is_strict_sorted(&array, &mut ctx)?);
673+
674+
Ok(())
675+
}
676+
677+
#[rstest]
678+
#[case::descending(-1i64)]
679+
#[case::constant(0i64)]
680+
#[case::ascending(1i64)]
681+
fn singleton_sequence_sortedness_kernel(#[case] multiplier: i64) -> VortexResult<()> {
682+
let mut ctx = SESSION.create_execution_ctx();
683+
let array =
684+
Sequence::try_new_typed(10i64, multiplier, Nullability::NonNullable, 3)?.slice(1..2)?;
685+
for stat in [Stat::IsSorted, Stat::IsStrictSorted] {
686+
array.statistics().clear(stat);
687+
}
688+
689+
for strict in [false, true] {
690+
let mut accumulator =
691+
Accumulator::try_new(IsSorted, IsSortedOptions { strict }, array.dtype().clone())?;
692+
accumulator.accumulate(&array, &mut ctx)?;
693+
assert!(bool::try_from(&accumulator.finish()?)?);
694+
}
695+
696+
Ok(())
697+
}
698+
699+
#[rstest]
700+
#[case::descending(-1i64)]
701+
#[case::constant(0i64)]
702+
#[case::ascending(1i64)]
703+
fn empty_sequence_slice_is_sorted(#[case] multiplier: i64) -> VortexResult<()> {
704+
let mut ctx = SESSION.create_execution_ctx();
705+
assert!(Sequence::try_new_typed(10i64, multiplier, Nullability::NonNullable, 0).is_err());
706+
707+
let array =
708+
Sequence::try_new_typed(10i64, multiplier, Nullability::NonNullable, 3)?.slice(1..1)?;
709+
assert!(is_sorted(&array, &mut ctx)?);
710+
assert!(is_strict_sorted(&array, &mut ctx)?);
711+
712+
Ok(())
713+
}
714+
615715
#[test]
616716
fn positive_multiplier_is_strict_sorted() -> VortexResult<()> {
617717
let arr = Sequence::try_new_typed(0i64, 3, Nullability::NonNullable, 4)?;

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

Lines changed: 12 additions & 11 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 with at least two rows is sorted iff multiplier >= 0,
19+
/// and strict sorted iff multiplier > 0. Shorter sequences are always strictly sorted.
2020
#[derive(Debug)]
2121
pub(crate) struct SequenceIsSortedKernel;
2222

@@ -36,15 +36,16 @@ impl DynAggregateKernel for SequenceIsSortedKernel {
3636
};
3737

3838
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-
})?;
39+
let result = array.len() <= 1
40+
|| match_each_native_ptype!(m.ptype(), |P| {
41+
m.cast::<P>().map(|x| {
42+
if options.strict {
43+
x > zero::<P>()
44+
} else {
45+
x >= zero::<P>()
46+
}
47+
})
48+
})?;
4849

4950
Ok(Some(IsSorted::make_partial(
5051
batch,

0 commit comments

Comments
 (0)