1mod kernel;
5mod pattern;
6
7use std::fmt::Display;
8use std::fmt::Formatter;
9
10pub use kernel::*;
11use pattern::LikePattern;
12use prost::Message;
13use vortex_buffer::BitBuffer;
14use vortex_buffer::BitBufferMut;
15use vortex_buffer::BufferAllocatorRef;
16use vortex_error::VortexResult;
17use vortex_error::vortex_bail;
18use vortex_error::vortex_err;
19use vortex_session::VortexSession;
20use vortex_session::registry::CachedId;
21
22use crate::AnyColumnar;
23use crate::ArrayRef;
24use crate::Canonical;
25use crate::ExecutionCtx;
26use crate::IntoArray;
27use crate::arrays::BoolArray;
28use crate::arrays::ConstantArray;
29use crate::arrays::ScalarFnArray;
30use crate::arrays::VarBinViewArray;
31use crate::arrays::varbinview::BinaryView;
32use crate::arrays::varbinview::ResolvedViews;
33use crate::dtype::DType;
34use crate::dtype::Nullability;
35use crate::expr::display::ExprDisplay;
36use crate::proto::expr as pb;
37use crate::require_input;
38use crate::scalar::Scalar;
39use crate::scalar_fn::Arity;
40use crate::scalar_fn::ChildName;
41use crate::scalar_fn::ExecutionArgs;
42use crate::scalar_fn::ScalarFnExecutionResult;
43use crate::scalar_fn::ScalarFnId;
44use crate::scalar_fn::ScalarFnVTable;
45use crate::scalar_fn::ScalarFnVTableExt;
46
47#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash)]
49pub struct LikeOptions {
50 pub negated: bool,
51 pub case_insensitive: bool,
52}
53
54impl Display for LikeOptions {
55 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
56 if self.negated {
57 write!(f, "NOT ")?;
58 }
59 if self.case_insensitive {
60 write!(f, "ILIKE")
61 } else {
62 write!(f, "LIKE")
63 }
64 }
65}
66
67#[derive(Clone)]
69pub struct Like;
70
71impl Like {
72 pub fn try_new(
78 input: ArrayRef,
79 pattern: ArrayRef,
80 options: LikeOptions,
81 ) -> VortexResult<ScalarFnArray> {
82 ScalarFnArray::try_new(Like.bind(options), [input, pattern])
83 }
84}
85
86impl ScalarFnVTable for Like {
87 type Options = LikeOptions;
88
89 fn id(&self) -> ScalarFnId {
90 static ID: CachedId = CachedId::new("vortex.like");
91 *ID
92 }
93
94 fn serialize(&self, instance: &Self::Options) -> VortexResult<Option<Vec<u8>>> {
95 Ok(Some(
96 pb::LikeOpts {
97 negated: instance.negated,
98 case_insensitive: instance.case_insensitive,
99 }
100 .encode_to_vec(),
101 ))
102 }
103
104 fn deserialize(
105 &self,
106 _metadata: &[u8],
107 _session: &VortexSession,
108 ) -> VortexResult<Self::Options> {
109 let opts = pb::LikeOpts::decode(_metadata)?;
110 Ok(LikeOptions {
111 negated: opts.negated,
112 case_insensitive: opts.case_insensitive,
113 })
114 }
115
116 fn arity(&self, _options: &Self::Options) -> Arity {
117 Arity::Exact(2)
118 }
119
120 fn child_name(&self, _instance: &Self::Options, child_idx: usize) -> ChildName {
121 match child_idx {
122 0 => ChildName::from("child"),
123 1 => ChildName::from("pattern"),
124 _ => unreachable!("Invalid child index {} for Like expression", child_idx),
125 }
126 }
127
128 fn fmt_sql(
129 &self,
130 options: &Self::Options,
131 expr: &dyn ExprDisplay,
132 f: &mut Formatter<'_>,
133 ) -> std::fmt::Result {
134 Display::fmt(expr.display_child(0), f)?;
135 if options.negated {
136 write!(f, " not")?;
137 }
138 if options.case_insensitive {
139 write!(f, " ilike ")?;
140 } else {
141 write!(f, " like ")?;
142 }
143 Display::fmt(expr.display_child(1), f)
144 }
145
146 fn return_dtype(&self, _options: &Self::Options, arg_dtypes: &[DType]) -> VortexResult<DType> {
147 let input = &arg_dtypes[0];
148 let pattern = &arg_dtypes[1];
149
150 if !input.is_utf8() {
151 vortex_bail!("LIKE expression requires UTF8 input dtype, got {}", input);
152 }
153 if !pattern.is_utf8() {
154 vortex_bail!(
155 "LIKE expression requires UTF8 pattern dtype, got {}",
156 pattern
157 );
158 }
159
160 Ok(DType::Bool(
161 (input.is_nullable() || pattern.is_nullable()).into(),
162 ))
163 }
164
165 fn execute(
166 &self,
167 options: &Self::Options,
168 args: &dyn ExecutionArgs,
169 ctx: &mut ExecutionCtx,
170 ) -> VortexResult<ArrayRef> {
171 let child = args.get(0)?;
172 let pattern = args.get(1)?;
173
174 execute_like(&child, &pattern, *options, ctx)
175 }
176
177 fn execute_step(
178 &self,
179 options: &Self::Options,
180 args: &dyn ExecutionArgs,
181 ctx: &mut ExecutionCtx,
182 ) -> VortexResult<ScalarFnExecutionResult> {
183 if !args.input_matches(1, |pattern| {
185 pattern
186 .as_constant()
187 .is_some_and(|pattern| pattern.is_null())
188 })? {
189 require_input!(args, 0 => AnyColumnar);
190 require_input!(args, 1 => AnyColumnar);
191 }
192 self.execute(options, args, ctx)
193 .map(ScalarFnExecutionResult::done)
194 }
195
196 fn is_strict(&self, _instance: &Self::Options) -> bool {
197 true
198 }
199
200 fn is_infallible(&self, _options: &Self::Options) -> bool {
201 true
202 }
203}
204
205pub(crate) fn execute_like(
210 array: &ArrayRef,
211 pattern: &ArrayRef,
212 options: LikeOptions,
213 ctx: &mut ExecutionCtx,
214) -> VortexResult<ArrayRef> {
215 assert_eq!(
216 array.len(),
217 pattern.len(),
218 "LIKE: length mismatch for {}",
219 array.encoding_id()
220 );
221 let len = array.len();
222 let nullability =
223 Nullability::from(array.dtype().is_nullable() || pattern.dtype().is_nullable());
224
225 if len == 0 {
226 return Ok(Canonical::empty(&DType::Bool(nullability)).into_array());
227 }
228
229 if let Some(pattern_const) = pattern.as_constant() {
230 let Some(pattern_str) = pattern_const.as_utf8().value() else {
231 return Ok(
233 ConstantArray::new(Scalar::null(DType::Bool(Nullability::Nullable)), len)
234 .into_array(),
235 );
236 };
237 let values = array.clone().execute::<VarBinViewArray>(ctx)?;
238 let haystack = values.resolved_views();
239 let ascii_haystack =
242 options.case_insensitive && pattern_str.as_str().is_ascii() && is_ascii(&haystack);
243 let compiled = LikePattern::compile(
244 pattern_str.as_str(),
245 options.case_insensitive,
246 ascii_haystack,
247 )?;
248 let bits = eval_pattern(&haystack, &compiled, options.negated, ctx.allocator());
249 let validity = values.validity()?.union_nullability(nullability);
250 return Ok(BoolArray::new(bits, validity).into_array());
251 }
252
253 let values = array.clone().execute::<VarBinViewArray>(ctx)?;
255 let patterns = pattern.clone().execute::<VarBinViewArray>(ctx)?;
256 let haystack = values.resolved_views();
257 let pattern_views = patterns.resolved_views();
258 let ascii_haystack = options.case_insensitive && is_ascii(&haystack);
259
260 let mut cached: Option<(&[u8], LikePattern)> = None;
263 let mut bits = BitBufferMut::with_capacity_in(len, ctx.allocator().clone());
264 for i in 0..len {
265 let pattern_bytes = pattern_views.bytes(i);
266 let compiled = match &cached {
267 Some((bytes, compiled)) if *bytes == pattern_bytes => compiled,
268 _ => {
269 let pattern_str = std::str::from_utf8(pattern_bytes)
270 .map_err(|e| vortex_err!("LIKE pattern is not valid UTF-8: {e}"))?;
271 let compiled = LikePattern::compile(
272 pattern_str,
273 options.case_insensitive,
274 ascii_haystack && pattern_str.is_ascii(),
275 )?;
276 &cached.insert((pattern_bytes, compiled)).1
277 }
278 };
279 bits.append(compiled.matches(haystack.bytes(i)) != options.negated);
280 }
281 let validity = values
282 .validity()?
283 .and(patterns.validity()?)?
284 .union_nullability(nullability);
285 Ok(BoolArray::new(bits.freeze(), validity).into_array())
286}
287
288fn eval_pattern(
294 haystack: &ResolvedViews<'_>,
295 pattern: &LikePattern,
296 negated: bool,
297 allocator: &BufferAllocatorRef,
298) -> BitBuffer {
299 let len = haystack.len();
300 match pattern {
301 LikePattern::Eq(needle) if needle.len() <= BinaryView::MAX_INLINED_SIZE => {
302 let needle_view = BinaryView::new_inlined(needle).as_u128();
305 BitBuffer::collect_bool_in(
306 len,
307 |i| (haystack.views()[i].as_u128() == needle_view) != negated,
308 allocator.clone(),
309 )
310 }
311 LikePattern::Eq(needle) => {
312 let needle_head = BinaryView::head_of(needle);
315 BitBuffer::collect_bool_in(
316 len,
317 |i| {
318 let view = &haystack.views()[i];
319 let matched =
320 view.head() == needle_head && haystack.bytes(i)[4..] == needle[4..];
321 matched != negated
322 },
323 allocator.clone(),
324 )
325 }
326 LikePattern::StartsWith(needle) => {
327 let needle_len = needle.len();
331 let prefix_len = needle_len.min(4);
332 let needle_prefix = u32::from_le_bytes(BinaryView::prefix_of(needle));
334 let prefix_mask = if prefix_len == 4 {
335 u32::MAX
336 } else {
337 (1u32 << (8 * prefix_len)) - 1
338 };
339 BitBuffer::collect_bool_in(
340 len,
341 |i| {
342 let view = &haystack.views()[i];
343 let matched = view.len() as usize >= needle_len
344 && (u32::from_le_bytes(view.prefix()) & prefix_mask) == needle_prefix
345 && (needle_len <= 4 || haystack.bytes(i)[4..needle_len] == needle[4..]);
346 matched != negated
347 },
348 allocator.clone(),
349 )
350 }
351 LikePattern::EndsWith(needle) => {
352 let needle_len = needle.len();
355 BitBuffer::collect_bool_in(
356 len,
357 |i| {
358 let matched = unsafe {
361 let view = haystack.views().get_unchecked(i);
362 view.len() as usize >= needle_len
363 && bytes_eq(suffix_bytes_unchecked(haystack, view, needle_len), needle)
364 };
365 matched != negated
366 },
367 allocator.clone(),
368 )
369 }
370 LikePattern::IEqAscii(needle) => BitBuffer::collect_bool_in(
371 len,
372 |i| {
373 let view = &haystack.views()[i];
374 let matched = view.len() as usize == needle.len()
375 && haystack.bytes(i).eq_ignore_ascii_case(needle);
376 matched != negated
377 },
378 allocator.clone(),
379 ),
380 LikePattern::Contains(finder, needle_len) => BitBuffer::collect_bool_in(
381 len,
382 |i| {
383 let view = &haystack.views()[i];
384 let matched =
385 view.len() as usize >= *needle_len && finder.find(haystack.bytes(i)).is_some();
386 matched != negated
387 },
388 allocator.clone(),
389 ),
390 _ => BitBuffer::collect_bool_in(
391 len,
392 |i| pattern.matches(haystack.bytes(i)) != negated,
393 allocator.clone(),
394 ),
395 }
396}
397
398fn is_ascii(haystack: &ResolvedViews<'_>) -> bool {
400 haystack
401 .views()
402 .iter()
403 .all(|view| haystack.view_bytes(view).is_ascii())
404}
405
406#[inline]
412unsafe fn suffix_bytes_unchecked<'a>(
413 haystack: &ResolvedViews<'a>,
414 view: &'a BinaryView,
415 suffix_len: usize,
416) -> &'a [u8] {
417 let len = view.len() as usize;
418 if view.is_inlined() {
419 unsafe { view.as_inlined().value().get_unchecked(len - suffix_len..) }
421 } else {
422 let view = view.as_view();
423 let end = view.offset as usize + len;
424 unsafe {
426 haystack
427 .buffers()
428 .get_unchecked(view.buffer_index as usize)
429 .get_unchecked(end - suffix_len..end)
430 }
431 }
432}
433
434#[inline]
439fn bytes_eq(lhs: &[u8], rhs: &[u8]) -> bool {
440 lhs.len() == rhs.len() && std::iter::zip(lhs, rhs).all(|(l, r)| l == r)
441}
442
443#[cfg(test)]
444mod tests {
445 use std::sync::LazyLock;
446
447 use rstest::rstest;
448 use vortex_session::VortexSession;
449
450 use crate::IntoArray;
451 use crate::VortexSessionExecute;
452 use crate::arrays::BoolArray;
453 use crate::arrays::ConstantArray;
454 use crate::arrays::VarBinArray;
455 use crate::arrays::VarBinViewArray;
456 use crate::assert_arrays_eq;
457 use crate::dtype::DType;
458 use crate::dtype::Nullability;
459 use crate::expr::get_item;
460 use crate::expr::like;
461 use crate::expr::lit;
462 use crate::expr::not_ilike;
463 use crate::expr::root;
464 use crate::scalar::Scalar;
465 use crate::scalar_fn::fns::like::Like;
466 use crate::scalar_fn::fns::like::LikeOptions;
467 use crate::scalar_fn::fns::like::is_ascii;
468 use crate::scalar_fn::fns::like::suffix_bytes_unchecked;
469
470 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
471
472 const LONG: &str = "a value far too long to live inside its own view";
473
474 fn run_like(
475 array: crate::ArrayRef,
476 pattern: crate::ArrayRef,
477 options: LikeOptions,
478 ) -> crate::ArrayRef {
479 Like::try_new(array, pattern, options).unwrap().into_array()
480 }
481
482 #[rstest]
483 #[case("hello", [true, false, false, false])]
485 #[case("he%", [true, false, true, false])]
486 #[case("%llo", [true, false, false, true])]
487 #[case("%ell%", [true, false, false, true])]
488 #[case("h_llo", [true, false, false, false])]
490 #[case("h%o", [true, false, false, false])]
491 #[case("%", [true, true, true, true])]
492 #[case("_____", [true, true, false, true])]
493 fn test_like_patterns(#[case] pattern: &str, #[case] expected: [bool; 4]) {
494 let mut ctx = SESSION.create_execution_ctx();
495 let array =
496 VarBinViewArray::from_iter_str(["hello", "world", "help", "jello"]).into_array();
497 let result = run_like(
498 array,
499 ConstantArray::new(pattern, 4).into_array(),
500 LikeOptions::default(),
501 );
502 assert_arrays_eq!(result, BoolArray::from_iter(expected), &mut ctx);
503 }
504
505 #[test]
506 fn test_like_escapes() {
507 let mut ctx = SESSION.create_execution_ctx();
508 let array = VarBinViewArray::from_iter_str(["100%", "100x", "a_b", "axb"]).into_array();
509
510 let result = run_like(
511 array.clone(),
512 ConstantArray::new(r"100\%", 4).into_array(),
513 LikeOptions::default(),
514 );
515 assert_arrays_eq!(
516 result,
517 BoolArray::from_iter([true, false, false, false]),
518 &mut ctx
519 );
520
521 let result = run_like(
522 array,
523 ConstantArray::new(r"a\_b", 4).into_array(),
524 LikeOptions::default(),
525 );
526 assert_arrays_eq!(
527 result,
528 BoolArray::from_iter([false, false, true, false]),
529 &mut ctx
530 );
531 }
532
533 #[test]
534 fn test_like_regex_meta_characters_are_literal() {
535 let mut ctx = SESSION.create_execution_ctx();
536 let array = VarBinViewArray::from_iter_str(["a.c", "abc", "a$c"]).into_array();
537 let result = run_like(
538 array,
539 ConstantArray::new("a.%", 3).into_array(),
540 LikeOptions::default(),
541 );
542 assert_arrays_eq!(result, BoolArray::from_iter([true, false, false]), &mut ctx);
543 }
544
545 #[test]
546 fn test_like_unicode() {
547 let mut ctx = SESSION.create_execution_ctx();
548 let array =
549 VarBinViewArray::from_iter_str(["h\u{00a3}llo", "hxllo", "h\u{00a3}xllo"]).into_array();
550 let result = run_like(
552 array,
553 ConstantArray::new("h_llo", 3).into_array(),
554 LikeOptions::default(),
555 );
556 assert_arrays_eq!(result, BoolArray::from_iter([true, true, false]), &mut ctx);
557 }
558
559 #[test]
560 fn test_nlike() {
561 let mut ctx = SESSION.create_execution_ctx();
562 let array = VarBinViewArray::from_iter_str(["hello", "world"]).into_array();
563 let result = run_like(
564 array,
565 ConstantArray::new("he%", 2).into_array(),
566 LikeOptions {
567 negated: true,
568 case_insensitive: false,
569 },
570 );
571 assert_arrays_eq!(result, BoolArray::from_iter([false, true]), &mut ctx);
572 }
573
574 #[test]
575 fn test_ilike() {
576 let mut ctx = SESSION.create_execution_ctx();
577 let ilike = LikeOptions {
578 negated: false,
579 case_insensitive: true,
580 };
581
582 let array = VarBinViewArray::from_iter_str(["HELLO", "world", "Help"]).into_array();
584 let result = run_like(array, ConstantArray::new("he%", 3).into_array(), ilike);
585 assert_arrays_eq!(result, BoolArray::from_iter([true, false, true]), &mut ctx);
586
587 let array = VarBinViewArray::from_iter_str(["\u{212a}", "k", "x"]).into_array();
589 let result = run_like(array, ConstantArray::new("k", 3).into_array(), ilike);
590 assert_arrays_eq!(result, BoolArray::from_iter([true, true, false]), &mut ctx);
591 }
592
593 #[test]
594 fn test_nilike() {
595 let mut ctx = SESSION.create_execution_ctx();
596 let array = VarBinViewArray::from_iter_str(["HELLO", "world"]).into_array();
597 let result = run_like(
598 array,
599 ConstantArray::new("he%", 2).into_array(),
600 LikeOptions {
601 negated: true,
602 case_insensitive: true,
603 },
604 );
605 assert_arrays_eq!(result, BoolArray::from_iter([false, true]), &mut ctx);
606 }
607
608 #[test]
609 fn test_like_nullable_input() {
610 let mut ctx = SESSION.create_execution_ctx();
611 let array = VarBinViewArray::from_iter_nullable_str([Some("hello"), None, Some("help")])
612 .into_array();
613 let result = run_like(
614 array,
615 ConstantArray::new("he%", 3).into_array(),
616 LikeOptions::default(),
617 );
618 assert_arrays_eq!(
619 result,
620 BoolArray::from_iter([Some(true), None, Some(true)]),
621 &mut ctx
622 );
623 }
624
625 #[test]
626 fn test_like_null_pattern() {
627 let mut ctx = SESSION.create_execution_ctx();
628 let array = VarBinViewArray::from_iter_str(["hello", "world"]).into_array();
629 let result = run_like(
630 array,
631 ConstantArray::new(Scalar::null(DType::Utf8(Nullability::Nullable)), 2).into_array(),
632 LikeOptions::default(),
633 );
634 assert_arrays_eq!(result, BoolArray::from_iter([None, None]), &mut ctx);
635 }
636
637 #[test]
638 fn test_like_per_row_patterns() {
639 let mut ctx = SESSION.create_execution_ctx();
640 let array = VarBinViewArray::from_iter_str(["hello", "hello", "hello"]).into_array();
641 let patterns = VarBinViewArray::from_iter_str(["he%", "%world", "h_llo"]).into_array();
642 let result = run_like(array, patterns, LikeOptions::default());
643 assert_arrays_eq!(result, BoolArray::from_iter([true, false, true]), &mut ctx);
644 }
645
646 #[test]
647 fn test_like_non_canonical_input() {
648 let mut ctx = SESSION.create_execution_ctx();
649 let array = VarBinArray::from_iter(
651 [Some("hello"), Some("world")],
652 DType::Utf8(Nullability::Nullable),
653 )
654 .into_array();
655 let result = run_like(
656 array,
657 ConstantArray::new("he%", 2).into_array(),
658 LikeOptions::default(),
659 );
660 assert_arrays_eq!(
661 result,
662 BoolArray::from_iter([Some(true), Some(false)]),
663 &mut ctx
664 );
665 }
666
667 #[test]
668 fn dtype() {
669 let dtype = DType::Utf8(Nullability::NonNullable);
670 let like_expr = like(root(), lit("%test%"));
671 assert_eq!(
672 like_expr.return_dtype(&dtype).unwrap(),
673 DType::Bool(Nullability::NonNullable)
674 );
675 }
676
677 #[test]
678 fn signature() {
679 let like_expr = like(root(), lit("%test%"));
680 assert!(
681 like_expr
682 .as_scalar()
683 .is_some_and(|f| f.signature().is_strict())
684 );
685 assert!(
686 like_expr
687 .as_scalar()
688 .is_some_and(|f| f.signature().is_infallible())
689 );
690 }
691
692 #[test]
693 fn test_display() {
694 let expr = like(get_item("name", root()), lit("%john%"));
695 assert_eq!(expr.to_string(), "$.name like \"%john%\"");
696
697 let expr2 = not_ilike(root(), lit("test*"));
698 assert_eq!(expr2.to_string(), "$ not ilike \"test*\"");
699 }
700
701 #[test]
702 fn suffix_bytes_are_value_suffixes() {
703 let array = VarBinViewArray::from_iter_str(["short", LONG, "another long value here"]);
704 let haystack = array.resolved_views();
705 for (index, view) in haystack.views().iter().enumerate() {
706 let value = haystack.bytes(index);
707 for suffix_len in 0..=value.len() {
708 let suffix = unsafe { suffix_bytes_unchecked(&haystack, view, suffix_len) };
710 assert_eq!(suffix, &value[value.len() - suffix_len..]);
711 }
712 }
713 }
714
715 #[rstest]
716 #[case::inlined(["short", "tiny"], true)]
717 #[case::referenced([LONG, "another long value here"], true)]
718 #[case::inlined_non_ascii(["short", "é"], false)]
719 #[case::referenced_non_ascii([LONG, "a long value ending in é"], false)]
720 fn detects_ascii(#[case] values: [&str; 2], #[case] expected: bool) {
721 let array = VarBinViewArray::from_iter_str(values);
722 assert_eq!(is_ascii(&array.resolved_views()), expected);
723 }
724
725 #[test]
727 fn executes_non_columnar_input_iteratively() -> vortex_error::VortexResult<()> {
728 let mut ctx = SESSION.create_execution_ctx();
729 let chunks = vec![
730 VarBinViewArray::from_iter_str(["alpha", "beta"]).into_array(),
731 VarBinViewArray::from_iter_str(["alphabet"]).into_array(),
732 ];
733 let dtype = chunks[0].dtype().clone();
734 let chunked = crate::arrays::ChunkedArray::try_new(chunks, dtype)?.into_array();
735 let result = Like::try_new(
736 chunked,
737 ConstantArray::new("alpha%", 3).into_array(),
738 LikeOptions::default(),
739 )?
740 .into_array();
741
742 assert_arrays_eq!(result, BoolArray::from_iter([true, false, true]), &mut ctx);
743 Ok(())
744 }
745}