Skip to main content

vortex_array/arrays/varbin/compute/
compare.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::cmp::Ordering;
5
6use vortex_buffer::BitBuffer;
7use vortex_error::VortexExpect as _;
8use vortex_error::VortexResult;
9use vortex_error::vortex_bail;
10
11use crate::ArrayRef;
12use crate::ExecutionCtx;
13use crate::IntoArray;
14use crate::array::ArrayView;
15use crate::arrays::BoolArray;
16use crate::arrays::PrimitiveArray;
17use crate::arrays::VarBin;
18use crate::arrays::varbin::VarBinArraySlotsExt;
19use crate::dtype::DType;
20use crate::dtype::IntegerPType;
21use crate::match_each_integer_ptype;
22use crate::scalar_fn::fns::binary::CompareKernel;
23use crate::scalar_fn::fns::operators::CompareOperator;
24
25// This implementation exists so we can compare against a constant in encoded space, without
26// canonicalizing the VarBin array to VarBinView.
27impl CompareKernel for VarBin {
28    fn compare(
29        lhs: ArrayView<'_, VarBin>,
30        rhs: &ArrayRef,
31        operator: CompareOperator,
32        ctx: &mut ExecutionCtx,
33    ) -> VortexResult<Option<ArrayRef>> {
34        let Some(rhs_const) = rhs.as_constant() else {
35            return Ok(None);
36        };
37
38        let len = lhs.len();
39
40        // The compare adaptor resolves null constants before dispatching to this kernel, so
41        // the scalar always carries a value.
42        let rhs_bytes: &[u8] = match rhs_const.dtype() {
43            DType::Binary(_) => rhs_const
44                .as_binary()
45                .value()
46                .vortex_expect("RHS should not be null")
47                .as_slice(),
48            DType::Utf8(_) => rhs_const
49                .as_utf8()
50                .value()
51                .vortex_expect("RHS should not be null")
52                .as_str()
53                .as_bytes(),
54            _ => vortex_bail!("VarBinArray can only have type of Binary or Utf8"),
55        };
56
57        let buffer = if rhs_bytes.is_empty() {
58            // Comparisons against "" only need the value lengths, i.e. the offset deltas.
59            match operator {
60                CompareOperator::Gte => BitBuffer::new_set(len), /* Every possible value is >= "" */
61                CompareOperator::Lt => BitBuffer::new_unset(len), // No value is < ""
62                CompareOperator::Eq | CompareOperator::Lte => {
63                    let lhs_offsets = lhs.offsets().clone().execute::<PrimitiveArray>(ctx)?;
64                    match_each_integer_ptype!(lhs_offsets.ptype(), |P| {
65                        compare_offsets_to_empty::<P>(lhs_offsets, true)
66                    })
67                }
68                CompareOperator::NotEq | CompareOperator::Gt => {
69                    let lhs_offsets = lhs.offsets().clone().execute::<PrimitiveArray>(ctx)?;
70                    match_each_integer_ptype!(lhs_offsets.ptype(), |P| {
71                        compare_offsets_to_empty::<P>(lhs_offsets, false)
72                    })
73                }
74            }
75        } else {
76            let lhs_offsets = lhs.offsets().clone().execute::<PrimitiveArray>(ctx)?;
77            match_each_integer_ptype!(lhs_offsets.ptype(), |P| {
78                compare_bytes_to_constant(
79                    lhs_offsets.as_slice::<P>(),
80                    lhs.bytes().as_slice(),
81                    rhs_bytes,
82                    operator,
83                )
84            })
85        };
86
87        Ok(Some(
88            BoolArray::new(
89                buffer,
90                lhs.validity()?.union_nullability(rhs.dtype().nullability()),
91            )
92            .into_array(),
93        ))
94    }
95}
96
97fn compare_offsets_to_empty<P: IntegerPType>(offsets: PrimitiveArray, eq: bool) -> BitBuffer {
98    let fn_ = if eq { P::eq } else { P::ne };
99    let offsets = offsets.as_slice::<P>();
100    BitBuffer::collect_bool(offsets.len() - 1, |idx| {
101        let left = unsafe { offsets.get_unchecked(idx) };
102        let right = unsafe { offsets.get_unchecked(idx + 1) };
103        fn_(left, right)
104    })
105}
106
107/// Compare every value in a VarBin array against a constant, resolving values through the
108/// offsets. Dispatches the operator outside the lane loop so each predicate inlines into its
109/// own loop.
110fn compare_bytes_to_constant<P: IntegerPType>(
111    offsets: &[P],
112    bytes: &[u8],
113    constant: &[u8],
114    operator: CompareOperator,
115) -> BitBuffer {
116    match operator {
117        CompareOperator::Eq => {
118            collect_lane_bits(offsets, |start, end| value_eq(bytes, start, end, constant))
119        }
120        CompareOperator::NotEq => {
121            collect_lane_bits(offsets, |start, end| !value_eq(bytes, start, end, constant))
122        }
123        CompareOperator::Gt => collect_lane_bits(offsets, |start, end| {
124            value_cmp(bytes, start, end, constant).is_gt()
125        }),
126        CompareOperator::Gte => collect_lane_bits(offsets, |start, end| {
127            value_cmp(bytes, start, end, constant).is_ge()
128        }),
129        CompareOperator::Lt => collect_lane_bits(offsets, |start, end| {
130            value_cmp(bytes, start, end, constant).is_lt()
131        }),
132        CompareOperator::Lte => collect_lane_bits(offsets, |start, end| {
133            value_cmp(bytes, start, end, constant).is_le()
134        }),
135    }
136}
137
138/// Bit-pack `predicate(offsets[i], offsets[i + 1])` over each lane of a VarBin array.
139fn collect_lane_bits<P: IntegerPType>(
140    offsets: &[P],
141    predicate: impl Fn(usize, usize) -> bool,
142) -> BitBuffer {
143    BitBuffer::collect_bool(offsets.len() - 1, |idx| {
144        // SAFETY: `collect_bool` yields idx < offsets.len() - 1.
145        let start = unsafe { offsets.get_unchecked(idx) }.as_();
146        let end = unsafe { offsets.get_unchecked(idx + 1) }.as_();
147        predicate(start, end)
148    })
149}
150
151/// Whether `bytes[start..end]` equals `constant`, comparing lengths first so lanes of a
152/// different length never touch the value bytes.
153///
154/// Offsets at null positions are not validated, so an out-of-bounds or inverted range is
155/// possible there; such lanes answer `false`, and validity masks them out of the result anyway.
156#[allow(clippy::inline_always)]
157#[inline(always)]
158fn value_eq(bytes: &[u8], start: usize, end: usize, constant: &[u8]) -> bool {
159    // A lane can only match when its length equals the constant's, so lanes of a different
160    // length answer without touching the value bytes. An inverted garbage range (start > end)
161    // wraps to a huge value that never equals `constant.len()`.
162    end.wrapping_sub(start) == constant.len()
163        && bytes.get(start..end).is_some_and(|value| value == constant)
164}
165
166/// Order `bytes[start..end]` against `constant`, treating the unvalidated garbage ranges that
167/// can appear at null positions as empty; validity masks those lanes out of the result anyway.
168#[allow(clippy::inline_always)]
169#[inline(always)]
170fn value_cmp(bytes: &[u8], start: usize, end: usize, constant: &[u8]) -> Ordering {
171    bytes.get(start..end).unwrap_or_default().cmp(constant)
172}
173
174#[cfg(test)]
175mod test {
176    use std::sync::LazyLock;
177
178    use vortex_buffer::ByteBuffer;
179    use vortex_session::VortexSession;
180
181    use crate::IntoArray;
182    use crate::VortexSessionExecute;
183    use crate::arrays::BoolArray;
184    use crate::arrays::ConstantArray;
185    use crate::arrays::VarBinArray;
186    use crate::arrays::VarBinViewArray;
187    use crate::assert_arrays_eq;
188    use crate::builtins::ArrayBuiltins;
189    use crate::dtype::DType;
190    use crate::dtype::Nullability;
191    use crate::scalar::Scalar;
192    use crate::scalar_fn::fns::operators::Operator;
193
194    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
195
196    #[test]
197    fn test_binary_compare() {
198        let mut ctx = SESSION.create_execution_ctx();
199        let array = VarBinArray::from_iter(
200            [Some(b"abc".to_vec()), None, Some(b"def".to_vec())],
201            DType::Binary(Nullability::Nullable),
202        );
203        let result = array
204            .into_array()
205            .binary(
206                ConstantArray::new(
207                    Scalar::binary(ByteBuffer::copy_from(b"abc"), Nullability::Nullable),
208                    3,
209                )
210                .into_array(),
211                Operator::Eq,
212            )
213            .unwrap();
214
215        assert_arrays_eq!(
216            result,
217            BoolArray::from_iter([Some(true), None, Some(false)]),
218            &mut ctx
219        );
220    }
221
222    #[test]
223    fn varbinview_compare() {
224        let mut ctx = SESSION.create_execution_ctx();
225        let array = VarBinArray::from_iter(
226            [Some(b"abc".to_vec()), None, Some(b"def".to_vec())],
227            DType::Binary(Nullability::Nullable),
228        );
229        let vbv = VarBinViewArray::from_iter(
230            [None, None, Some(b"def".to_vec())],
231            DType::Binary(Nullability::Nullable),
232        );
233        let result = array
234            .into_array()
235            .binary(vbv.into_array(), Operator::Eq)
236            .unwrap();
237
238        assert_arrays_eq!(
239            result,
240            BoolArray::from_iter([None, None, Some(true)]),
241            &mut ctx
242        );
243    }
244}
245
246#[cfg(test)]
247mod tests {
248    use std::sync::LazyLock;
249
250    use vortex_buffer::ByteBuffer;
251    use vortex_session::VortexSession;
252
253    use crate::IntoArray;
254    use crate::VortexSessionExecute;
255    use crate::arrays::BoolArray;
256    use crate::arrays::ConstantArray;
257    use crate::arrays::VarBinArray;
258    use crate::arrays::varbin::builder::VarBinBuilder;
259    use crate::assert_arrays_eq;
260    use crate::builtins::ArrayBuiltins;
261    use crate::dtype::DType;
262    use crate::dtype::Nullability;
263    use crate::scalar::Scalar;
264    use crate::scalar_fn::fns::operators::Operator;
265
266    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
267
268    #[test]
269    fn test_null_compare() {
270        let arr = VarBinArray::from_iter([Some("h")], DType::Utf8(Nullability::NonNullable));
271
272        let const_ = ConstantArray::new(Scalar::utf8("", Nullability::Nullable), 1);
273
274        let result = arr
275            .into_array()
276            .binary(const_.into_array(), Operator::Eq)
277            .unwrap();
278        assert_arrays_eq!(
279            result,
280            BoolArray::from_iter([Some(false)]),
281            &mut SESSION.create_execution_ctx()
282        );
283    }
284
285    /// Regression: [`CompareKernel`] must handle every offset width; a `VarBinArray` built with
286    /// `i64` offsets once failed the constant comparison. Triggering this only requires `i64`
287    /// offsets, not large data.
288    ///
289    /// [`CompareKernel`]: super::CompareKernel
290    #[test]
291    fn varbin_i64_offsets_compare_constant() {
292        let mut ctx = SESSION.create_execution_ctx();
293        let mut builder = VarBinBuilder::<i64>::with_capacity_in(
294            DType::Utf8(Nullability::NonNullable),
295            3,
296            vortex_buffer::BufferAllocatorRef::static_ref(),
297        );
298        builder.append_value(b"abc");
299        builder.append_value(b"xyz");
300        builder.append_value(b"abc");
301        let array = builder.finish_into_varbin();
302
303        let result = array
304            .into_array()
305            .binary(
306                ConstantArray::new(Scalar::utf8("abc", Nullability::NonNullable), 3).into_array(),
307                Operator::Eq,
308            )
309            .unwrap();
310
311        let expected = BoolArray::from_iter([true, false, true]);
312        assert_arrays_eq!(result, expected, &mut ctx);
313    }
314
315    #[test]
316    fn varbin_i64_offsets_compare_constant_binary() {
317        let mut ctx = SESSION.create_execution_ctx();
318        let mut builder = VarBinBuilder::<i64>::with_capacity_in(
319            DType::Binary(Nullability::NonNullable),
320            3,
321            vortex_buffer::BufferAllocatorRef::static_ref(),
322        );
323        builder.append_value(b"abc");
324        builder.append_value(b"xyz");
325        builder.append_value(b"abc");
326        let array = builder.finish_into_varbin();
327
328        let result = array
329            .into_array()
330            .binary(
331                ConstantArray::new(
332                    Scalar::binary(ByteBuffer::copy_from(b"abc"), Nullability::NonNullable),
333                    3,
334                )
335                .into_array(),
336                Operator::Eq,
337            )
338            .unwrap();
339
340        let expected = BoolArray::from_iter([true, false, true]);
341        assert_arrays_eq!(result, expected, &mut ctx);
342    }
343}