Skip to content

Commit d58de2d

Browse files
committed
Share one Sequence sortedness check between stats and the kernel
Move the length and multiplier logic into Sequence::is_sorted(multiplier, length, strict) and use it for the constructor stats and the is_sorted kernel. Signed-off-by: Vincent <[email protected]>
1 parent de3e710 commit d58de2d

2 files changed

Lines changed: 24 additions & 35 deletions

File tree

‎encodings/sequence/src/array.rs‎

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

458458
impl Sequence {
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!(
470+
multiplier,
471+
uint: |v| { !strict || v > 0 },
472+
int: |v| { if strict { v > 0 } else { v >= 0 } },
473+
float: |_v| { unreachable!("float multiplier not supported") }
474+
)
475+
}
476+
459477
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-
};
478+
let is_sorted = Self::is_sorted(multiplier, length, false);
479+
let is_strict_sorted = Self::is_sorted(multiplier, length, true);
473480

474481
// SAFETY: we don't have duplicate stats.
475482
unsafe {

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

Lines changed: 4 additions & 22 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` with at least two elements is sorted iff
19-
/// multiplier >= 0, 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,24 +32,9 @@ impl DynAggregateKernel for SequenceIsSortedKernel {
3532
return Ok(None);
3633
};
3734

38-
// One-element batches are always (strict) sorted. Keep this here even though
39-
// `is_sorted` also short-circuits on len <= 1: Accumulator dispatches this kernel
40-
// per chunk without that outer check, so a one-row Sequence chunk with a negative
41-
// multiplier would otherwise poison a larger ChunkedArray.
42-
let result = if array.len() <= 1 {
43-
true
44-
} else {
45-
let m = array.multiplier();
46-
match_each_native_ptype!(m.ptype(), |P| {
47-
m.cast::<P>().map(|x| {
48-
if options.strict {
49-
x > zero::<P>()
50-
} else {
51-
x >= zero::<P>()
52-
}
53-
})
54-
})?
55-
};
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);
5638

5739
Ok(Some(IsSorted::make_partial(
5840
batch,

0 commit comments

Comments
 (0)