Skip to content

Commit 910f993

Browse files
ump45noseump45nose
authored
Report one-row Sequence arrays as sorted for any multiplier (#10602)
## Summary - Tracking Issue: #10177 Closes #10579. A one-row `Sequence` has no adjacent pair to compare, so it is sorted and strictly sorted whatever its multiplier. Its constructor stats, its `is_sorted` aggregate kernel and the generic sortedness helper answered from the multiplier (or a cached hint) alone, so a negative multiplier reported unsorted and a zero multiplier reported not strictly sorted. ## Changes - `Sequence::stats` now takes the length and reports both flags as exact `true` when it is at most 1. This covers `try_new`, `try_new_typed` and slicing, which goes through `new_unchecked`. - `SequenceIsSortedKernel` returns `true` for a one-row batch, so direct aggregate execution agrees with the stats. - `is_sorted_impl` checks `len() <= 1` before the cached statistics, so a stale hint can't contradict it. - `SerializedArray::decode` sets both flags to exact `true` for arrays with at most one element after it restores the stored statistics. Files written before this change can store the multiplier-only answer for one-row sequences, and this makes the intrinsic fact win over those historical hints. New tests cover the typed and untyped constructors and a one-row slice of a longer sequence (multipliers -1, 0 and 3), the kernel called directly for strict and non-strict, decoding a one-row sequence whose serialized hints say unsorted, and the generic helper with stale cached stats. Apart from the positive-multiplier cases, they all fail on `develop`. ## AI assistance This PR was written by an AI coding agent working under my account (code, tests and this description), and I'm the responsible human for it. Points worth a reviewer's attention: the decode change in `vortex-array/src/serde.rs` applies to every encoding, not only `Sequence`, on the basis that any array with at most one element is (strictly) sorted; and it overwrites the stored hint with exact `true` rather than dropping it. --------- Signed-off-by: Vincent <[email protected]>
1 parent dfb3e92 commit 910f993

4 files changed

Lines changed: 193 additions & 32 deletions

File tree

‎encodings/sequence/src/array.rs‎

Lines changed: 83 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -456,15 +456,27 @@ 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!(
459+
/// Whether a sequence `A[i] = base + i * multiplier` of `length` elements is sorted, or
460+
/// strictly sorted when `strict` is set.
461+
///
462+
/// With at least two elements it is sorted iff multiplier >= 0, and strictly sorted iff
463+
/// multiplier > 0. Zero or one elements have no adjacent pair to compare, so they are
464+
/// strictly sorted whatever the multiplier.
465+
pub(crate) fn is_sorted(multiplier: PValue, length: usize, strict: bool) -> bool {
466+
if length <= 1 {
467+
return true;
468+
}
469+
match_each_pvalue!(
463470
multiplier,
464-
uint: |v| { (true, v > 0) },
465-
int: |v| { (v >= 0, v > 0) },
471+
uint: |v| { !strict || v > 0 },
472+
int: |v| { if strict { v > 0 } else { v >= 0 } },
466473
float: |_v| { unreachable!("float multiplier not supported") }
467-
);
474+
)
475+
}
476+
477+
fn stats(multiplier: PValue, length: usize) -> StatsSet {
478+
let is_sorted = Self::is_sorted(multiplier, length, false);
479+
let is_strict_sorted = Self::is_sorted(multiplier, length, true);
468480

469481
// SAFETY: we don't have duplicate stats.
470482
unsafe {
@@ -495,7 +507,7 @@ impl Sequence {
495507
let dtype = DType::Primitive(ptype, nullability);
496508
let (base, multiplier) = SequenceData::normalize(base, multiplier, ptype)
497509
.vortex_expect("SequenceArray parts must be representable in the output ptype");
498-
let stats = Self::stats(multiplier);
510+
let stats = Self::stats(multiplier, length);
499511
let data = unsafe { SequenceData::new_unchecked(base, multiplier) };
500512
unsafe {
501513
Array::from_parts_unchecked(ArrayParts::new(
@@ -519,7 +531,7 @@ impl Sequence {
519531
) -> VortexResult<SequenceArray> {
520532
let dtype = DType::Primitive(ptype, nullability);
521533
let data = SequenceData::try_new(base, multiplier, ptype, nullability, length)?;
522-
let stats = Self::stats(data.multiplier());
534+
let stats = Self::stats(data.multiplier(), length);
523535
Ok(unsafe {
524536
Array::from_parts_unchecked(ArrayParts::new(
525537
Sequence,
@@ -542,7 +554,7 @@ impl Sequence {
542554
let ptype = T::PTYPE;
543555
let dtype = DType::Primitive(ptype, nullability);
544556
let data = SequenceData::try_new_typed(base, multiplier, nullability, length)?;
545-
let stats = Self::stats(data.multiplier());
557+
let stats = Self::stats(data.multiplier(), length);
546558
Ok(unsafe {
547559
Array::from_parts_unchecked(ArrayParts::new(
548560
Sequence,
@@ -687,6 +699,67 @@ mod tests {
687699
Ok(())
688700
}
689701

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

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

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

4-
use num_traits::zero;
54
use vortex_array::ArrayRef;
65
use vortex_array::ExecutionCtx;
76
use vortex_array::aggregate_fn::AggregateFnRef;
87
use vortex_array::aggregate_fn::fns::is_sorted::IsSorted;
98
use vortex_array::aggregate_fn::kernels::DynAggregateKernel;
10-
use vortex_array::match_each_native_ptype;
119
use vortex_array::scalar::Scalar;
1210
use vortex_error::VortexResult;
1311

1412
use crate::Sequence;
1513

1614
/// Sequence-specific is_sorted kernel.
1715
///
18-
/// A sequence `A[i] = base + i * multiplier` is sorted iff multiplier >= 0,
19-
/// and strict sorted iff multiplier > 0.
16+
/// See [`Sequence::is_sorted`] for when a sequence is (strictly) sorted.
2017
#[derive(Debug)]
2118
pub(crate) struct SequenceIsSortedKernel;
2219

@@ -35,16 +32,9 @@ impl DynAggregateKernel for SequenceIsSortedKernel {
3532
return Ok(None);
3633
};
3734

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-
})?;
35+
// `is_sorted` short-circuits on len <= 1, but the Chunked accumulator dispatches this
36+
// kernel per chunk without that outer check, so the length has to be considered here too.
37+
let result = Sequence::is_sorted(array.multiplier(), array.len(), options.strict);
4838

4939
Ok(Some(IsSorted::make_partial(
5040
batch,
@@ -54,3 +44,75 @@ impl DynAggregateKernel for SequenceIsSortedKernel {
5444
)?))
5545
}
5646
}
47+
48+
#[cfg(test)]
49+
mod tests {
50+
use std::sync::LazyLock;
51+
52+
use rstest::rstest;
53+
use vortex_array::IntoArray;
54+
use vortex_array::VortexSessionExecute;
55+
use vortex_array::aggregate_fn::AggregateFnVTableExt;
56+
use vortex_array::aggregate_fn::fns::is_sorted::IsSorted;
57+
use vortex_array::aggregate_fn::fns::is_sorted::IsSortedOptions;
58+
use vortex_array::aggregate_fn::fns::is_sorted::is_sorted;
59+
use vortex_array::aggregate_fn::fns::is_sorted::is_strict_sorted;
60+
use vortex_array::aggregate_fn::kernels::DynAggregateKernel;
61+
use vortex_array::arrays::ChunkedArray;
62+
use vortex_array::dtype::DType;
63+
use vortex_array::dtype::Nullability;
64+
use vortex_array::dtype::PType;
65+
use vortex_error::VortexResult;
66+
use vortex_session::VortexSession;
67+
68+
use super::SequenceIsSortedKernel;
69+
use crate::Sequence;
70+
71+
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
72+
let session = VortexSession::empty();
73+
crate::initialize(&session);
74+
session
75+
});
76+
77+
#[rstest]
78+
fn singleton_is_sorted_for_any_multiplier(
79+
#[values(-1i64, 0, 3)] multiplier: i64,
80+
#[values(false, true)] strict: bool,
81+
) -> VortexResult<()> {
82+
let mut ctx = SESSION.create_execution_ctx();
83+
let array =
84+
Sequence::try_new_typed(10i64, multiplier, Nullability::NonNullable, 1)?.into_array();
85+
86+
let result = SequenceIsSortedKernel.aggregate(
87+
&IsSorted.bind(IsSortedOptions { strict }),
88+
&array,
89+
&mut ctx,
90+
)?;
91+
92+
let expected = IsSorted::make_partial(&array, true, strict, &mut ctx)?;
93+
assert_eq!(result, Some(expected));
94+
Ok(())
95+
}
96+
97+
#[rstest]
98+
fn singleton_chunk_keeps_chunked_array_sorted(
99+
#[values(-1i64, 0)] multiplier: i64,
100+
) -> VortexResult<()> {
101+
let mut ctx = SESSION.create_execution_ctx();
102+
// The Chunked accumulator hands each chunk to this kernel directly, without going through
103+
// `is_sorted`, so the one-row first chunk must not report unsorted.
104+
let chunked = ChunkedArray::try_new(
105+
[
106+
Sequence::try_new_typed(5i64, multiplier, Nullability::NonNullable, 1)?
107+
.into_array(),
108+
Sequence::try_new_typed(10i64, 1, Nullability::NonNullable, 3)?.into_array(),
109+
],
110+
DType::Primitive(PType::I64, Nullability::NonNullable),
111+
)?
112+
.into_array();
113+
114+
assert!(is_sorted(&chunked, &mut ctx)?);
115+
assert!(is_strict_sorted(&chunked, &mut ctx)?);
116+
Ok(())
117+
}
118+
}

‎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;
@@ -620,11 +621,29 @@ mod tests {
620621
use crate::dtype::DType;
621622
use crate::dtype::Nullability;
622623
use crate::dtype::PType;
624+
use crate::expr::stats::Precision;
625+
use crate::expr::stats::Stat;
623626
use crate::scalar::Scalar;
624627
use crate::validity::Validity;
625628

626629
static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
627630

631+
#[test]
632+
fn singleton_ignores_stale_sortedness_stats() -> VortexResult<()> {
633+
let mut ctx = SESSION.create_execution_ctx();
634+
let array = buffer![7i32].into_array();
635+
array
636+
.statistics()
637+
.set(Stat::IsSorted, Precision::Exact(false.into()));
638+
array
639+
.statistics()
640+
.set(Stat::IsStrictSorted, Precision::Exact(false.into()));
641+
642+
assert!(is_sorted(&array, &mut ctx)?);
643+
assert!(is_strict_sorted(&array, &mut ctx)?);
644+
Ok(())
645+
}
646+
628647
// Tests migrated from compute/is_sorted.rs
629648
#[test]
630649
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)