vortex_array/compute/
is_constant.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::any::Any;
5use std::sync::LazyLock;
6
7use arcref::ArcRef;
8use vortex_dtype::DType;
9use vortex_dtype::Nullability;
10use vortex_error::VortexError;
11use vortex_error::VortexResult;
12use vortex_error::vortex_bail;
13use vortex_error::vortex_err;
14use vortex_scalar::Scalar;
15
16use crate::Array;
17use crate::arrays::ConstantVTable;
18use crate::arrays::NullVTable;
19use crate::compute::ComputeFn;
20use crate::compute::ComputeFnVTable;
21use crate::compute::InvocationArgs;
22use crate::compute::Kernel;
23use crate::compute::Options;
24use crate::compute::Output;
25use crate::expr::stats::Precision;
26use crate::expr::stats::Stat;
27use crate::expr::stats::StatsProvider;
28use crate::expr::stats::StatsProviderExt;
29use crate::vtable::VTable;
30
31static IS_CONSTANT_FN: LazyLock<ComputeFn> = LazyLock::new(|| {
32    let compute = ComputeFn::new("is_constant".into(), ArcRef::new_ref(&IsConstant));
33    for kernel in inventory::iter::<IsConstantKernelRef> {
34        compute.register_kernel(kernel.0.clone());
35    }
36    compute
37});
38
39pub(crate) fn warm_up_vtable() -> usize {
40    IS_CONSTANT_FN.kernels().len()
41}
42
43/// Computes whether an array has constant values. If the array's encoding doesn't implement the
44/// relevant VTable, it'll try and canonicalize in order to make a determination.
45///
46/// An array is constant IFF at least one of the following conditions apply:
47/// 1. It has at least one element (**Note** - an empty array isn't constant).
48/// 1. It's encoded as a [`crate::arrays::ConstantArray`] or [`crate::arrays::NullArray`]
49/// 1. Has an exact statistic attached to it, saying its constant.
50/// 1. Is all invalid.
51/// 1. Is all valid AND has minimum and maximum statistics that are equal.
52///
53/// If the array has some null values but is not all null, it'll never be constant.
54///
55/// Returns `Ok(None)` if we could not determine whether the array is constant, e.g. if
56/// canonicalization is disabled and the no kernel exists for the array's encoding.
57pub fn is_constant(array: &dyn Array) -> VortexResult<Option<bool>> {
58    let opts = IsConstantOpts::default();
59    is_constant_opts(array, &opts)
60}
61
62/// Computes whether an array has constant values. Configurable by [`IsConstantOpts`].
63///
64/// Please see [`is_constant`] for a more detailed explanation of its behavior.
65pub fn is_constant_opts(array: &dyn Array, options: &IsConstantOpts) -> VortexResult<Option<bool>> {
66    Ok(IS_CONSTANT_FN
67        .invoke(&InvocationArgs {
68            inputs: &[array.into()],
69            options,
70        })?
71        .unwrap_scalar()?
72        .as_bool()
73        .value())
74}
75
76struct IsConstant;
77
78impl ComputeFnVTable for IsConstant {
79    fn invoke(
80        &self,
81        args: &InvocationArgs,
82        kernels: &[ArcRef<dyn Kernel>],
83    ) -> VortexResult<Output> {
84        let IsConstantArgs { array, options } = IsConstantArgs::try_from(args)?;
85
86        // We try and rely on some easy-to-get stats
87        if let Some(Precision::Exact(value)) = array.statistics().get_as::<bool>(Stat::IsConstant) {
88            return Ok(Scalar::from(Some(value)).into());
89        }
90
91        let value = is_constant_impl(array, options, kernels)?;
92
93        if options.cost == Cost::Canonicalize {
94            // When we run linear canonicalize, there we must always return an exact answer.
95            assert!(
96                value.is_some(),
97                "is constant in array {array} canonicalize returned None"
98            );
99        }
100
101        // Only if we made a determination do we update the stats.
102        if let Some(value) = value {
103            array
104                .statistics()
105                .set(Stat::IsConstant, Precision::Exact(value.into()));
106        }
107
108        Ok(Scalar::from(value).into())
109    }
110
111    fn return_dtype(&self, _args: &InvocationArgs) -> VortexResult<DType> {
112        // We always return a nullable boolean where `null` indicates we couldn't determine
113        // whether the array is constant.
114        Ok(DType::Bool(Nullability::Nullable))
115    }
116
117    fn return_len(&self, _args: &InvocationArgs) -> VortexResult<usize> {
118        Ok(1)
119    }
120
121    fn is_elementwise(&self) -> bool {
122        false
123    }
124}
125
126fn is_constant_impl(
127    array: &dyn Array,
128    options: &IsConstantOpts,
129    kernels: &[ArcRef<dyn Kernel>],
130) -> VortexResult<Option<bool>> {
131    match array.len() {
132        // Our current semantics are that we can always get a value out of a constant array. We might want to change that in the future.
133        0 => return Ok(Some(false)),
134        // Array of length 1 is always constant.
135        1 => return Ok(Some(true)),
136        _ => {}
137    }
138
139    // Constant and null arrays are always constant
140    if array.is::<ConstantVTable>() || array.is::<NullVTable>() {
141        return Ok(Some(true));
142    }
143
144    let all_invalid = array.all_invalid();
145    if all_invalid {
146        return Ok(Some(true));
147    }
148
149    let all_valid = array.all_valid();
150
151    // If we have some nulls, array can't be constant
152    if !all_valid && !all_invalid {
153        return Ok(Some(false));
154    }
155
156    // We already know here that the array is all valid, so we check for min/max stats.
157    let min = array.statistics().get(Stat::Min);
158    let max = array.statistics().get(Stat::Max);
159
160    if let Some((min, max)) = min.zip(max) {
161        // min/max are equal and exact and there are no NaNs
162        if min.is_exact()
163            && min == max
164            && (Stat::NaNCount.dtype(array.dtype()).is_none()
165                || array.statistics().get_as::<u64>(Stat::NaNCount) == Some(Precision::exact(0u64)))
166        {
167            return Ok(Some(true));
168        }
169    }
170
171    assert!(
172        all_valid,
173        "All values must be valid as an invariant of the VTable."
174    );
175    let args = InvocationArgs {
176        inputs: &[array.into()],
177        options,
178    };
179    for kernel in kernels {
180        if let Some(output) = kernel.invoke(&args)? {
181            return Ok(output.unwrap_scalar()?.as_bool().value());
182        }
183    }
184    if let Some(output) = array.invoke(&IS_CONSTANT_FN, &args)? {
185        return Ok(output.unwrap_scalar()?.as_bool().value());
186    }
187
188    log::debug!(
189        "No is_constant implementation found for {}",
190        array.encoding_id()
191    );
192
193    if options.cost == Cost::Canonicalize && !array.is_canonical() {
194        let array = array.to_canonical();
195        let is_constant = is_constant_opts(array.as_ref(), options)?;
196        return Ok(is_constant);
197    }
198
199    // Otherwise, we cannot determine if the array is constant.
200    Ok(None)
201}
202
203pub struct IsConstantKernelRef(ArcRef<dyn Kernel>);
204inventory::collect!(IsConstantKernelRef);
205
206pub trait IsConstantKernel: VTable {
207    /// # Preconditions
208    ///
209    /// * All values are valid
210    /// * array.len() > 1
211    ///
212    /// Returns `Ok(None)` to signal we couldn't make an exact determination.
213    fn is_constant(&self, array: &Self::Array, opts: &IsConstantOpts)
214    -> VortexResult<Option<bool>>;
215}
216
217#[derive(Debug)]
218pub struct IsConstantKernelAdapter<V: VTable>(pub V);
219
220impl<V: VTable + IsConstantKernel> IsConstantKernelAdapter<V> {
221    pub const fn lift(&'static self) -> IsConstantKernelRef {
222        IsConstantKernelRef(ArcRef::new_ref(self))
223    }
224}
225
226impl<V: VTable + IsConstantKernel> Kernel for IsConstantKernelAdapter<V> {
227    fn invoke(&self, args: &InvocationArgs) -> VortexResult<Option<Output>> {
228        let args = IsConstantArgs::try_from(args)?;
229        let Some(array) = args.array.as_opt::<V>() else {
230            return Ok(None);
231        };
232        let is_constant = V::is_constant(&self.0, array, args.options)?;
233        Ok(Some(Scalar::from(is_constant).into()))
234    }
235}
236
237struct IsConstantArgs<'a> {
238    array: &'a dyn Array,
239    options: &'a IsConstantOpts,
240}
241
242impl<'a> TryFrom<&InvocationArgs<'a>> for IsConstantArgs<'a> {
243    type Error = VortexError;
244
245    fn try_from(value: &InvocationArgs<'a>) -> Result<Self, Self::Error> {
246        if value.inputs.len() != 1 {
247            vortex_bail!("Expected 1 input, found {}", value.inputs.len());
248        }
249        let array = value.inputs[0]
250            .array()
251            .ok_or_else(|| vortex_err!("Expected input 0 to be an array"))?;
252        let options = value
253            .options
254            .as_any()
255            .downcast_ref::<IsConstantOpts>()
256            .ok_or_else(|| vortex_err!("Expected options to be of type IsConstantOpts"))?;
257        Ok(Self { array, options })
258    }
259}
260
261/// When calling `is_constant` the children are all checked for constantness.
262/// This enum decide at each precision/cost level the constant check should run as.
263/// The cost increase as we move down the list.
264#[derive(Clone, Copy, Debug, Eq, PartialEq)]
265pub enum Cost {
266    /// Only apply constant time computation to estimate constantness.
267    Negligible,
268    /// Allow the encoding to do a linear amount of work to determine is constant.
269    /// Each encoding should implement short-circuiting make the common case runtime well below
270    /// a linear scan.
271    Specialized,
272    /// Same as linear, but when necessary canonicalize the array and check is constant.
273    /// This *must* always return a known answer.
274    Canonicalize,
275}
276
277/// Configuration for [`is_constant_opts`] operations.
278#[derive(Clone, Debug)]
279pub struct IsConstantOpts {
280    /// What precision cost trade off should be used
281    pub cost: Cost,
282}
283
284impl Default for IsConstantOpts {
285    fn default() -> Self {
286        Self {
287            cost: Cost::Canonicalize,
288        }
289    }
290}
291
292impl Options for IsConstantOpts {
293    fn as_any(&self) -> &dyn Any {
294        self
295    }
296}
297
298impl IsConstantOpts {
299    pub fn is_negligible_cost(&self) -> bool {
300        self.cost == Cost::Negligible
301    }
302}
303
304#[cfg(test)]
305mod tests {
306    use vortex_buffer::buffer;
307
308    use crate::IntoArray as _;
309    use crate::arrays::PrimitiveArray;
310    use crate::expr::stats::Stat;
311
312    #[test]
313    fn is_constant_min_max_no_nan() {
314        let arr = buffer![0, 1].into_array();
315        arr.statistics()
316            .compute_all(&[Stat::Min, Stat::Max])
317            .unwrap();
318        assert!(!arr.is_constant());
319
320        let arr = buffer![0, 0].into_array();
321        arr.statistics()
322            .compute_all(&[Stat::Min, Stat::Max])
323            .unwrap();
324        assert!(arr.is_constant());
325
326        let arr = PrimitiveArray::from_option_iter([Some(0), Some(0)]);
327        assert!(arr.is_constant());
328    }
329
330    #[test]
331    fn is_constant_min_max_with_nan() {
332        let arr = PrimitiveArray::from_iter([0.0, 0.0, f32::NAN]);
333        arr.statistics()
334            .compute_all(&[Stat::Min, Stat::Max])
335            .unwrap();
336        assert!(!arr.is_constant());
337
338        let arr =
339            PrimitiveArray::from_option_iter([Some(f32::NEG_INFINITY), Some(f32::NEG_INFINITY)]);
340        arr.statistics()
341            .compute_all(&[Stat::Min, Stat::Max])
342            .unwrap();
343        assert!(arr.is_constant());
344    }
345}
vortex_array/compute/is_constant.rs

vortex_array/compute/
is_constant.rs
