vortex-array 0.93.0

Vortex in memory columnar data format
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

use vortex_error::VortexResult;

use crate::ArrayEq;
use crate::ArrayRef;
use crate::EqMode;
use crate::IntoArray;
use crate::array::ArrayView;
use crate::array::VTable;
use crate::arrays::Chunked;
use crate::arrays::ChunkedArray;
use crate::arrays::Constant;
use crate::arrays::ConstantArray;
use crate::arrays::Dict;
use crate::arrays::DictArray;
use crate::arrays::ScalarFn;
use crate::arrays::ScalarFnArray;
use crate::arrays::chunked::ChunkedArrayExt;
use crate::arrays::dict::DictArrayExt;
use crate::arrays::dict::DictArraySlotsExt;
use crate::arrays::filter::FilterReduceAdaptor;
use crate::arrays::scalar_fn::AnyScalarFn;
use crate::arrays::scalar_fn::ScalarFnArrayExt;
use crate::arrays::slice::SliceReduceAdaptor;
use crate::builtins::ArrayBuiltins;
use crate::optimizer::ArrayOptimizer;
use crate::optimizer::rules::ArrayParentReduceRule;
use crate::optimizer::rules::ParentRuleSet;
use crate::scalar_fn::fns::cast::Cast;
use crate::scalar_fn::fns::cast::CastReduceAdaptor;
use crate::scalar_fn::fns::like::LikeReduceAdaptor;
use crate::scalar_fn::fns::mask::MaskReduceAdaptor;
use crate::scalar_fn::fns::pack::Pack;
use crate::validity::Validity;

pub(crate) const PARENT_RULES: ParentRuleSet<Dict> = ParentRuleSet::new(&[
    ParentRuleSet::lift(&FilterReduceAdaptor(Dict)),
    ParentRuleSet::lift(&CastReduceAdaptor(Dict)),
    ParentRuleSet::lift(&MaskReduceAdaptor(Dict)),
    ParentRuleSet::lift(&LikeReduceAdaptor(Dict)),
    ParentRuleSet::lift(&DictionaryChunkedValuesPullUpRule),
    ParentRuleSet::lift(&DictionaryScalarFnValuesPushDownRule),
    ParentRuleSet::lift(&DictionaryScalarFnCodesPullUpRule),
    ParentRuleSet::lift(&SliceReduceAdaptor(Dict)),
]);

/// Pull a common dictionary values array above chunked dictionary codes.
///
/// Rewrites `Chunked<Dict<codes_i, values>>` into `Dict<Chunked<codes_i>, values>` only when
/// every child dictionary shares the exact same values array allocation.
#[derive(Debug)]
struct DictionaryChunkedValuesPullUpRule;

impl ArrayParentReduceRule<Dict> for DictionaryChunkedValuesPullUpRule {
    type Parent = Chunked;

    fn reduce_parent(
        &self,
        array: ArrayView<'_, Dict>,
        parent: ArrayView<'_, Chunked>,
        _child_idx: usize,
    ) -> VortexResult<Option<ArrayRef>> {
        let values = array.values();
        let codes_dtype = array.codes().dtype().clone();
        let mut all_values_referenced = array.has_all_values_referenced();

        for chunk in parent.iter_chunks() {
            let Some(dict) = chunk.as_opt::<Dict>() else {
                return Ok(None);
            };
            if dict.codes().dtype() != &codes_dtype {
                return Ok(None);
            }
            if !ArrayRef::ptr_eq(dict.values(), values) {
                return Ok(None);
            }
            all_values_referenced |= dict.has_all_values_referenced();
        }

        let code_chunks = parent
            .iter_chunks()
            .map(|chunk| chunk.as_::<Dict>().codes().clone());
        let codes = ChunkedArray::try_new(code_chunks, codes_dtype)?.into_array();
        let dict = DictArray::try_new(codes, values.clone())?;
        let dict = if all_values_referenced {
            unsafe { dict.set_all_values_referenced(true) }
        } else {
            dict
        };

        Ok(Some(dict.into_array()))
    }
}

/// Push down a scalar function to run only over the values of a dictionary array.
#[derive(Debug)]
struct DictionaryScalarFnValuesPushDownRule;

impl ArrayParentReduceRule<Dict> for DictionaryScalarFnValuesPushDownRule {
    type Parent = AnyScalarFn;

    fn reduce_parent(
        &self,
        array: ArrayView<'_, Dict>,
        parent: ArrayView<'_, ScalarFn>,
        child_idx: usize,
    ) -> VortexResult<Option<ArrayRef>> {
        let scalar_fn = parent.scalar_fn();
        let signature = scalar_fn.signature();

        // Preserve pack expressions so exporters can unpack them later.
        if scalar_fn.is::<Pack>() {
            return Ok(None);
        }

        // CastReduceAdaptor handles casts eagerly. If it declines the rewrite, leave the cast on
        // the dictionary instead of creating a lazy cast over its values.
        if scalar_fn.is::<Cast>() {
            return Ok(None);
        }

        // A sliced dictionary can have more values than code rows. Do not increase the work in
        // that case.
        if array.values().len() > array.codes().len() {
            return Ok(None);
        }

        // A fallible function could fail on an unreferenced value that row-wise evaluation would
        // never visit.
        if !array.has_all_values_referenced() && !signature.is_infallible() {
            tracing::trace!(
                "Not pushing down fallible scalar function {} over dictionary with sparse codes {}",
                scalar_fn,
                Dict.id(),
            );
            return Ok(None);
        }

        // TODO(ngates): Support dictionary siblings when their values match.
        let other_children_are_constant = parent
            .iter_children()
            .enumerate()
            .all(|(idx, child)| idx == child_idx || child.is::<Constant>());
        if !other_children_are_constant {
            return Ok(None);
        }

        // Before this rewrite, a null code supplies null for this argument while the constant
        // arguments retain their values. After the rewrite, the null code masks the function's
        // result. Those are equivalent only for a strict function.
        let codes_have_nulls = array.codes().dtype().is_nullable()
            && !matches!(
                array.codes().validity()?,
                Validity::NonNullable | Validity::AllValid
            );
        if codes_have_nulls && !signature.is_strict() {
            tracing::trace!(
                "Not pushing down non-strict scalar function {} over dictionary with null codes {}",
                scalar_fn,
                Dict.id(),
            );
            return Ok(None);
        }

        let values_len = array.values().len();
        let mut value_children = Vec::with_capacity(parent.nchildren());
        for (idx, child) in parent.iter_children().enumerate() {
            if idx == child_idx {
                value_children.push(array.values().clone());
            } else {
                let scalar = child.as_::<Constant>().scalar().clone();
                value_children.push(ConstantArray::new(scalar, values_len).into_array());
            }
        }

        let transformed_values = ScalarFnArray::try_new(scalar_fn.clone(), value_children)?
            .into_array()
            .optimize()?;

        // A non-strict function reaches this point only when the codes are all valid, but their
        // dtype may still be nullable. Remove that declared nullability while rebuilding the
        // dictionary, then cast its output to the function's declared dtype.
        if !signature.is_strict() && array.codes().dtype().is_nullable() {
            let non_nullable_codes = array.codes().cast(array.codes().dtype().as_nonnullable())?;

            // SAFETY: The validity guard proves that the codes contain no nulls. Removing their
            // declared nullability preserves every code, and `transformed_values` has one entry
            // for each original dictionary value.
            let transformed_dict = unsafe {
                DictArray::new_unchecked(non_nullable_codes, transformed_values)
                    .set_all_values_referenced(array.has_all_values_referenced())
            }
            .into_array();

            return Ok(Some(transformed_dict.cast(parent.dtype().clone())?));
        }

        // SAFETY: The codes are unchanged and `transformed_values` has one entry for each original
        // dictionary value, so code bounds and `all_values_referenced` remain unchanged.
        let transformed_dict = unsafe {
            DictArray::new_unchecked(array.codes().clone(), transformed_values)
                .set_all_values_referenced(array.has_all_values_referenced())
        };

        Ok(Some(transformed_dict.into_array()))
    }
}

#[derive(Debug)]
struct DictionaryScalarFnCodesPullUpRule;

impl ArrayParentReduceRule<Dict> for DictionaryScalarFnCodesPullUpRule {
    type Parent = AnyScalarFn;

    fn reduce_parent(
        &self,
        array: ArrayView<'_, Dict>,
        parent: ArrayView<'_, ScalarFn>,
        child_idx: usize,
    ) -> VortexResult<Option<ArrayRef>> {
        // Don't attempt to pull up if there are less than 2 siblings.
        if parent.nchildren() < 2 {
            return Ok(None);
        }

        // Check that all siblings are dictionaries, and have the same number of values as us.
        // This is a cheap first loop.
        if !parent.iter_children().enumerate().all(|(idx, c)| {
            idx == child_idx
                || c.as_opt::<Dict>()
                    .is_some_and(|c| c.values().len() == array.values().len())
        }) {
            return Ok(None);
        }

        // Now run the slightly more expensive check that all siblings have the same codes as us.
        if !parent.iter_children().enumerate().all(|(idx, c)| {
            idx == child_idx
                || c.as_opt::<Dict>()
                    .is_some_and(|c| c.codes().array_eq(array.codes(), EqMode::Value))
        }) {
            return Ok(None);
        }

        let mut new_children = Vec::with_capacity(parent.nchildren());
        for (idx, child) in parent.iter_children().enumerate() {
            if idx == child_idx {
                new_children.push(array.values().clone());
            } else {
                new_children.push(child.as_::<Dict>().values().clone());
            }
        }

        let new_values = ScalarFnArray::try_new(parent.scalar_fn().clone(), new_children)?
            .into_array()
            .optimize()?;

        let new_dict =
            unsafe { DictArray::new_unchecked(array.codes().clone(), new_values) }.into_array();

        Ok(Some(new_dict))
    }
}

#[cfg(test)]
mod tests {
    use std::sync::LazyLock;

    use vortex_buffer::buffer;
    use vortex_error::VortexResult;
    use vortex_session::VortexSession;

    use crate::ArrayRef;
    use crate::IntoArray;
    use crate::arrays::BoolArray;
    use crate::arrays::Chunked;
    use crate::arrays::ChunkedArray;
    use crate::arrays::ConstantArray;
    use crate::arrays::Dict;
    use crate::arrays::DictArray;
    use crate::arrays::PrimitiveArray;
    use crate::arrays::chunked::ChunkedArrayExt;
    use crate::arrays::dict::DictArrayExt;
    use crate::arrays::dict::DictArraySlotsExt;
    use crate::assert_arrays_eq;
    use crate::dtype::Nullability;
    use crate::executor::VortexSessionExecute;
    use crate::optimizer::ArrayOptimizer;
    use crate::scalar::Scalar;
    use crate::scalar_fn::fns::binary::Binary;
    use crate::scalar_fn::fns::not::Not;
    use crate::scalar_fn::fns::operators::Operator;

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

    #[test]
    #[allow(clippy::disallowed_methods)]
    fn chunked_dict_with_shared_values_pulls_values_up() -> VortexResult<()> {
        let values = buffer![10u32, 20, 30].into_array();
        let chunk0 = DictArray::try_new(buffer![0u8, 1].into_array(), values.clone())?.into_array();
        let chunk1 =
            DictArray::try_new(buffer![2u8, 0, 1].into_array(), values.clone())?.into_array();
        let array =
            ChunkedArray::try_new(vec![chunk0, chunk1], values.dtype().clone())?.into_array();

        let optimized = array.optimize()?;
        let dict = optimized.as_::<Dict>();
        let codes = dict.codes().as_::<Chunked>();

        assert!(ArrayRef::ptr_eq(dict.values(), &values));
        assert_eq!(codes.nchunks(), 2);
        let mut ctx = SESSION.create_execution_ctx();
        assert_arrays_eq!(
            optimized,
            PrimitiveArray::from_iter([10u32, 20, 30, 10, 20]),
            &mut ctx
        );

        Ok(())
    }

    #[test]
    #[allow(clippy::disallowed_methods)]
    fn chunked_dict_with_distinct_values_stays_chunked() -> VortexResult<()> {
        let values0 = buffer![10u32, 20, 30].into_array();
        let values1 = buffer![10u32, 20, 30].into_array();
        let chunk0 =
            DictArray::try_new(buffer![0u8, 1].into_array(), values0.clone())?.into_array();
        let chunk1 = DictArray::try_new(buffer![2u8, 0, 1].into_array(), values1)?.into_array();
        let array =
            ChunkedArray::try_new(vec![chunk0, chunk1], values0.dtype().clone())?.into_array();

        let optimized = array.optimize()?;

        assert!(optimized.is::<Chunked>());
        let mut ctx = SESSION.create_execution_ctx();
        assert_arrays_eq!(
            optimized,
            PrimitiveArray::from_iter([10u32, 20, 30, 10, 20]),
            &mut ctx
        );

        Ok(())
    }

    #[test]
    fn scalar_fn_values_pushdown_preserves_all_values_referenced() -> VortexResult<()> {
        let dict = unsafe {
            DictArray::try_new(
                buffer![0u8, 1, 0, 1].into_array(),
                BoolArray::from_iter([true, false]).into_array(),
            )?
            .set_all_values_referenced(true)
        }
        .into_array();

        let result = Not::try_new(dict)?.into_array().optimize()?;
        let result = result.as_::<Dict>();

        assert!(result.has_all_values_referenced());
        assert_arrays_eq!(
            result.array(),
            BoolArray::from_iter([false, true, false, true]),
            &mut SESSION.create_execution_ctx()
        );

        Ok(())
    }

    #[test]
    fn kleene_and_dict_values_pushdown_counterexample() -> VortexResult<()> {
        let codes = PrimitiveArray::from_option_iter([Some(0u8), Some(1), None]).into_array();
        let values = BoolArray::from_iter([true, false]).into_array();
        let dict = DictArray::try_new(codes, values)?.into_array();
        let const_false =
            ConstantArray::new(Scalar::bool(false, Nullability::NonNullable), 3).into_array();
        let expr = Binary::try_new(dict, const_false, Operator::And)?.into_array();

        let mut ctx = SESSION.create_execution_ctx();
        // Kleene AND: null AND false == false
        let expected = BoolArray::from_iter([Some(false), Some(false), Some(false)]).into_array();
        let optimized = expr.optimize()?;
        assert_arrays_eq!(optimized, expected, &mut ctx);
        Ok(())
    }

    #[test]
    fn kleene_or_dict_values_pushdown_counterexample() -> VortexResult<()> {
        let codes = PrimitiveArray::from_option_iter([Some(0u8), Some(1), None]).into_array();
        let values = BoolArray::from_iter([true, false]).into_array();
        let dict = DictArray::try_new(codes, values)?.into_array();
        let const_true =
            ConstantArray::new(Scalar::bool(true, Nullability::NonNullable), 3).into_array();
        let expr = Binary::try_new(dict, const_true, Operator::Or)?.into_array();

        let mut ctx = SESSION.create_execution_ctx();
        // Kleene OR: null OR true == true
        let expected = BoolArray::from_iter([Some(true), Some(true), Some(true)]).into_array();
        let optimized = expr.optimize()?;
        assert_arrays_eq!(optimized, expected, &mut ctx);
        Ok(())
    }
}