lance_index/
scalar.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright The Lance Authors
3
4//! Scalar indices for metadata search & filtering
5
6use arrow::buffer::{OffsetBuffer, ScalarBuffer};
7use arrow_array::ListArray;
8use arrow_schema::Field;
9use datafusion::functions::regex::regexplike::RegexpLikeFunc;
10use datafusion::functions::string::contains::ContainsFunc;
11use datafusion::functions_nested::array_has;
12use datafusion_common::{Column, scalar::ScalarValue};
13use std::collections::HashSet;
14use std::{any::Any, ops::Bound, sync::Arc};
15
16use datafusion_expr::{
17    Expr,
18    expr::{Like, ScalarFunction},
19};
20use inverted::query::{FtsQuery, FtsQueryNode, FtsSearchParams, MatchQuery, fill_fts_query_column};
21use lance_core::Result;
22
23use lance_datafusion::udf::CONTAINS_TOKENS_UDF;
24
25use crate::IndexParams;
26pub use crate::metrics::MetricsCollector;
27pub use lance_index_core::scalar::{
28    AnyQuery, BuiltinIndexType, CreatedIndex, IndexFile, IndexReader, IndexStore, IndexWriter,
29    LANCE_SCALAR_INDEX, OldIndexDataFilter, RowIdRemapper, ScalarIndex, ScalarIndexParams,
30    SearchResult, TrainingCriteria, TrainingOrdering, UpdateCriteria,
31};
32
33pub mod bitmap;
34pub mod bloomfilter;
35pub mod btree;
36pub mod expression;
37pub mod fmindex;
38pub mod inverted;
39pub mod json;
40pub mod label_list;
41pub mod lance_format;
42pub mod ngram;
43pub mod registry;
44#[cfg(feature = "geo")]
45pub mod rtree;
46pub mod zoned;
47pub mod zonemap;
48
49pub use inverted::tokenizer::InvertedIndexParams;
50
51/// Convert a `Vec<`[`lance_index_core::scalar::IndexFile`]`>` to a
52/// `Vec<`[`lance_table::format::IndexFile`]`>`.
53///
54/// These two structs have identical fields; this helper bridges the crate
55/// boundary without relying on orphan-rule–violating `From` impls.
56pub fn index_files_to_table(
57    files: Vec<lance_index_core::scalar::IndexFile>,
58) -> Vec<lance_table::format::IndexFile> {
59    files
60        .into_iter()
61        .map(|f| lance_table::format::IndexFile {
62            path: f.path,
63            size_bytes: f.size_bytes,
64        })
65        .collect()
66}
67
68/// Convert a `Vec<`[`lance_table::format::IndexFile`]`>` to a
69/// `Vec<`[`lance_index_core::scalar::IndexFile`]`>`.
70///
71/// These two structs have identical fields; this helper bridges the crate
72/// boundary without relying on orphan-rule–violating `From` impls.
73pub fn table_files_to_index(
74    files: Vec<lance_table::format::IndexFile>,
75) -> Vec<lance_index_core::scalar::IndexFile> {
76    files
77        .into_iter()
78        .map(|f| lance_index_core::scalar::IndexFile {
79            path: f.path,
80            size_bytes: f.size_bytes,
81        })
82        .collect()
83}
84
85impl IndexParams for InvertedIndexParams {
86    fn as_any(&self) -> &dyn std::any::Any {
87        self
88    }
89
90    fn index_name(&self) -> &str {
91        "INVERTED"
92    }
93}
94
95/// A full text search query
96#[derive(Debug, Clone, PartialEq)]
97pub struct FullTextSearchQuery {
98    pub query: FtsQuery,
99
100    /// The maximum number of results to return
101    pub limit: Option<i64>,
102
103    /// The wand factor to use for ranking
104    /// if None, use the default value of 1.0
105    /// Increasing this value will reduce the recall and improve the performance
106    /// 1.0 is the value that would give the best performance without recall loss
107    pub wand_factor: Option<f32>,
108}
109
110impl FullTextSearchQuery {
111    /// Create a new terms query
112    pub fn new(query: String) -> Self {
113        let query = MatchQuery::new(query).into();
114        Self {
115            query,
116            limit: None,
117            wand_factor: None,
118        }
119    }
120
121    /// Create a new fuzzy query
122    pub fn new_fuzzy(term: String, max_distance: Option<u32>) -> Self {
123        let query = MatchQuery::new(term).with_fuzziness(max_distance).into();
124        Self {
125            query,
126            limit: None,
127            wand_factor: None,
128        }
129    }
130
131    /// Create a new compound query
132    pub fn new_query(query: FtsQuery) -> Self {
133        Self {
134            query,
135            limit: None,
136            wand_factor: None,
137        }
138    }
139
140    /// Set the column to search over
141    /// This is available for only MatchQuery and PhraseQuery
142    pub fn with_column(mut self, column: String) -> Result<Self> {
143        self.query = fill_fts_query_column(&self.query, &[column], true)?;
144        Ok(self)
145    }
146
147    /// Set the column to search over
148    /// This is available for only MatchQuery
149    pub fn with_columns(mut self, columns: &[String]) -> Result<Self> {
150        self.query = fill_fts_query_column(&self.query, columns, true)?;
151        Ok(self)
152    }
153
154    /// limit the number of results to return
155    /// if None, return all results
156    pub fn limit(mut self, limit: Option<i64>) -> Self {
157        self.limit = limit;
158        self
159    }
160
161    pub fn wand_factor(mut self, wand_factor: Option<f32>) -> Self {
162        self.wand_factor = wand_factor;
163        self
164    }
165
166    pub fn columns(&self) -> HashSet<String> {
167        self.query.columns()
168    }
169
170    pub fn params(&self) -> FtsSearchParams {
171        FtsSearchParams::new()
172            .with_limit(self.limit.map(|limit| limit as usize))
173            .with_wand_factor(self.wand_factor.unwrap_or(1.0))
174    }
175}
176
177/// A query that a basic scalar index (e.g. btree / bitmap) can satisfy
178///
179/// This is a subset of expression operators that is often referred to as the
180/// "sargable" operators
181///
182/// Note that negation is not included.  Negation should be applied later.  For
183/// example, to invert an equality query (e.g. all rows where the value is not 7)
184/// you can grab all rows where the value = 7 and then do an inverted take (or use
185/// a block list instead of an allow list for prefiltering)
186#[derive(Debug, Clone, PartialEq)]
187pub enum SargableQuery {
188    /// Retrieve all row ids where the value is in the given [min, max) range
189    Range(Bound<ScalarValue>, Bound<ScalarValue>),
190    /// Retrieve all row ids where the value is in the given set of values
191    IsIn(Vec<ScalarValue>),
192    /// Retrieve all row ids where the value is exactly the given value
193    Equals(ScalarValue),
194    /// Retrieve all row ids where the value matches the given full text search query
195    FullTextSearch(FullTextSearchQuery),
196    /// Retrieve all row ids where the value is null
197    IsNull(),
198    /// Retrieve all row ids where the value matches LIKE 'prefix%' pattern
199    /// This is used for both explicit LIKE expressions and starts_with() function calls
200    LikePrefix(ScalarValue),
201}
202
203/// Escape the LIKE metacharacters (`\`, `%`, `_`) in a literal string so it can be
204/// embedded in a LIKE pattern and matched literally (paired with `ESCAPE '\'`).
205fn escape_like_pattern(s: &str) -> String {
206    let mut out = String::with_capacity(s.len() + 2);
207    for c in s.chars() {
208        if matches!(c, '\\' | '%' | '_') {
209            out.push('\\');
210        }
211        out.push(c);
212    }
213    out
214}
215
216impl AnyQuery for SargableQuery {
217    fn as_any(&self) -> &dyn Any {
218        self
219    }
220
221    fn format(&self, col: &str) -> String {
222        match self {
223            Self::Range(lower, upper) => match (lower, upper) {
224                (Bound::Unbounded, Bound::Unbounded) => "true".to_string(),
225                (Bound::Unbounded, Bound::Included(rhs)) => format!("{} <= {}", col, rhs),
226                (Bound::Unbounded, Bound::Excluded(rhs)) => format!("{} < {}", col, rhs),
227                (Bound::Included(lhs), Bound::Unbounded) => format!("{} >= {}", col, lhs),
228                (Bound::Included(lhs), Bound::Included(rhs)) => {
229                    format!("{} >= {} && {} <= {}", col, lhs, col, rhs)
230                }
231                (Bound::Included(lhs), Bound::Excluded(rhs)) => {
232                    format!("{} >= {} && {} < {}", col, lhs, col, rhs)
233                }
234                (Bound::Excluded(lhs), Bound::Unbounded) => format!("{} > {}", col, lhs),
235                (Bound::Excluded(lhs), Bound::Included(rhs)) => {
236                    format!("{} > {} && {} <= {}", col, lhs, col, rhs)
237                }
238                (Bound::Excluded(lhs), Bound::Excluded(rhs)) => {
239                    format!("{} > {} && {} < {}", col, lhs, col, rhs)
240                }
241            },
242            Self::IsIn(values) => {
243                format!(
244                    "{} IN [{}]",
245                    col,
246                    values
247                        .iter()
248                        .map(|val| val.to_string())
249                        .collect::<Vec<_>>()
250                        .join(",")
251                )
252            }
253            Self::FullTextSearch(query) => {
254                format!("fts({})", query.query)
255            }
256            Self::IsNull() => {
257                format!("{} IS NULL", col)
258            }
259            Self::Equals(val) => {
260                format!("{} = {}", col, val)
261            }
262            Self::LikePrefix(prefix) => {
263                format!("{} LIKE '{}%'", col, prefix)
264            }
265        }
266    }
267
268    fn to_expr(&self, col: String) -> Expr {
269        let col_expr = Expr::Column(Column::new_unqualified(col));
270        match self {
271            Self::Range(lower, upper) => match (lower, upper) {
272                (Bound::Unbounded, Bound::Unbounded) => {
273                    Expr::Literal(ScalarValue::Boolean(Some(true)), None)
274                }
275                (Bound::Unbounded, Bound::Included(rhs)) => {
276                    col_expr.lt_eq(Expr::Literal(rhs.clone(), None))
277                }
278                (Bound::Unbounded, Bound::Excluded(rhs)) => {
279                    col_expr.lt(Expr::Literal(rhs.clone(), None))
280                }
281                (Bound::Included(lhs), Bound::Unbounded) => {
282                    col_expr.gt_eq(Expr::Literal(lhs.clone(), None))
283                }
284                (Bound::Included(lhs), Bound::Included(rhs)) => col_expr.between(
285                    Expr::Literal(lhs.clone(), None),
286                    Expr::Literal(rhs.clone(), None),
287                ),
288                (Bound::Included(lhs), Bound::Excluded(rhs)) => col_expr
289                    .clone()
290                    .gt_eq(Expr::Literal(lhs.clone(), None))
291                    .and(col_expr.lt(Expr::Literal(rhs.clone(), None))),
292                (Bound::Excluded(lhs), Bound::Unbounded) => {
293                    col_expr.gt(Expr::Literal(lhs.clone(), None))
294                }
295                (Bound::Excluded(lhs), Bound::Included(rhs)) => col_expr
296                    .clone()
297                    .gt(Expr::Literal(lhs.clone(), None))
298                    .and(col_expr.lt_eq(Expr::Literal(rhs.clone(), None))),
299                (Bound::Excluded(lhs), Bound::Excluded(rhs)) => col_expr
300                    .clone()
301                    .gt(Expr::Literal(lhs.clone(), None))
302                    .and(col_expr.lt(Expr::Literal(rhs.clone(), None))),
303            },
304            Self::IsIn(values) => col_expr.in_list(
305                values
306                    .iter()
307                    .map(|val| Expr::Literal(val.clone(), None))
308                    .collect::<Vec<_>>(),
309                false,
310            ),
311            Self::FullTextSearch(query) => col_expr.like(Expr::Literal(
312                ScalarValue::Utf8(Some(query.query.to_string())),
313                None,
314            )),
315            Self::IsNull() => col_expr.is_null(),
316            Self::Equals(value) => col_expr.eq(Expr::Literal(value.clone(), None)),
317            Self::LikePrefix(prefix) => match prefix {
318                ScalarValue::Utf8(Some(s))
319                | ScalarValue::LargeUtf8(Some(s))
320                | ScalarValue::Utf8View(Some(s)) => {
321                    // The prefix is a literal string. If it contains LIKE metacharacters
322                    // (`_`, `%`, `\`) they must be escaped before appending the `%` wildcard;
323                    // otherwise an inexact recheck (e.g. zone maps) would treat them as
324                    // wildcards and over-match rows that do not start with the literal prefix.
325                    // When the prefix has no metacharacters we keep the plain
326                    // `col LIKE 'prefix%'` form (no `ESCAPE`), identical to the prior behavior,
327                    // so DataFusion's optimized prefix matcher still applies.
328                    // A `Utf8View` prefix is handled here too (rather than falling through to
329                    // the catch-all arm, which would rebuild the recheck without the trailing
330                    // `%` and silently turn prefix matching into equality matching) and is
331                    // normalized to a `Utf8` pattern below, mirroring how the parser normalizes
332                    // `Utf8View` to `Utf8` (see `expression.rs`).
333                    let escaped = escape_like_pattern(s);
334                    let needs_escape = escaped.as_str() != s.as_str();
335                    let pattern = format!("{}%", escaped);
336                    let pattern_value = match prefix {
337                        ScalarValue::LargeUtf8(_) => ScalarValue::LargeUtf8(Some(pattern)),
338                        _ => ScalarValue::Utf8(Some(pattern)),
339                    };
340                    if needs_escape {
341                        Expr::Like(Like {
342                            negated: false,
343                            expr: Box::new(col_expr),
344                            pattern: Box::new(Expr::Literal(pattern_value, None)),
345                            escape_char: Some('\\'),
346                            case_insensitive: false,
347                        })
348                    } else {
349                        col_expr.like(Expr::Literal(pattern_value, None))
350                    }
351                }
352                other => col_expr.like(Expr::Literal(other.clone(), None)),
353            },
354        }
355    }
356
357    fn dyn_eq(&self, other: &dyn AnyQuery) -> bool {
358        match other.as_any().downcast_ref::<Self>() {
359            Some(o) => self == o,
360            None => false,
361        }
362    }
363}
364
365/// A query that a LabelListIndex can satisfy
366#[derive(Debug, Clone, PartialEq)]
367pub enum LabelListQuery {
368    /// Retrieve all row ids where every label is in the list of values for the row
369    HasAllLabels(Vec<ScalarValue>),
370    /// Retrieve all row ids where at least one of the given labels is in the list of values for the row
371    HasAnyLabel(Vec<ScalarValue>),
372}
373
374impl AnyQuery for LabelListQuery {
375    fn as_any(&self) -> &dyn Any {
376        self
377    }
378
379    fn format(&self, col: &str) -> String {
380        format!("{}", self.to_expr(col.to_string()))
381    }
382
383    fn to_expr(&self, col: String) -> Expr {
384        match self {
385            Self::HasAllLabels(labels) => {
386                let labels_arr = ScalarValue::iter_to_array(labels.iter().cloned()).unwrap();
387                let offsets_buffer =
388                    OffsetBuffer::new(ScalarBuffer::<i32>::from(vec![0, labels_arr.len() as i32]));
389                let labels_list = ListArray::try_new(
390                    Arc::new(Field::new("item", labels_arr.data_type().clone(), true)),
391                    offsets_buffer,
392                    labels_arr,
393                    None,
394                )
395                .unwrap();
396                let labels_arr = Arc::new(labels_list);
397                Expr::ScalarFunction(ScalarFunction {
398                    func: Arc::new(array_has::ArrayHasAll::new().into()),
399                    args: vec![
400                        Expr::Column(Column::new_unqualified(col)),
401                        Expr::Literal(ScalarValue::List(labels_arr), None),
402                    ],
403                })
404            }
405            Self::HasAnyLabel(labels) => {
406                let labels_arr = ScalarValue::iter_to_array(labels.iter().cloned()).unwrap();
407                let offsets_buffer =
408                    OffsetBuffer::new(ScalarBuffer::<i32>::from(vec![0, labels_arr.len() as i32]));
409                let labels_list = ListArray::try_new(
410                    Arc::new(Field::new("item", labels_arr.data_type().clone(), true)),
411                    offsets_buffer,
412                    labels_arr,
413                    None,
414                )
415                .unwrap();
416                let labels_arr = Arc::new(labels_list);
417                Expr::ScalarFunction(ScalarFunction {
418                    func: Arc::new(array_has::ArrayHasAny::new().into()),
419                    args: vec![
420                        Expr::Column(Column::new_unqualified(col)),
421                        Expr::Literal(ScalarValue::List(labels_arr), None),
422                    ],
423                })
424            }
425        }
426    }
427
428    fn dyn_eq(&self, other: &dyn AnyQuery) -> bool {
429        match other.as_any().downcast_ref::<Self>() {
430            Some(o) => self == o,
431            None => false,
432        }
433    }
434}
435
436/// A query that a NGramIndex can satisfy
437#[derive(Debug, Clone, PartialEq)]
438pub enum TextQuery {
439    /// Retrieve all row ids where the text contains the given string
440    StringContains(String),
441    /// Retrieve all row ids whose text matches the given regular expression.
442    ///
443    /// The pattern is a full regular expression (as accepted by `regexp_like`).
444    /// The index returns a candidate superset that the scan rechecks, so any
445    /// pattern is sound; patterns with no usable trigram structure simply fall
446    /// back to rechecking every row.
447    Regex(String),
448    // TODO: In the future we should be able to do case-insensitive contains
449    // as well as partial matches (e.g. LIKE 'foo%').
450}
451
452impl AnyQuery for TextQuery {
453    fn as_any(&self) -> &dyn Any {
454        self
455    }
456
457    fn format(&self, col: &str) -> String {
458        format!("{}", self.to_expr(col.to_string()))
459    }
460
461    fn to_expr(&self, col: String) -> Expr {
462        match self {
463            Self::StringContains(substr) => Expr::ScalarFunction(ScalarFunction {
464                func: Arc::new(ContainsFunc::new().into()),
465                args: vec![
466                    Expr::Column(Column::new_unqualified(col)),
467                    Expr::Literal(ScalarValue::Utf8(Some(substr.clone())), None),
468                ],
469            }),
470            // `regexp_like` returns Boolean directly, so the reconstructed
471            // expression can be used as-is for the recheck filter (no IsNotNull
472            // wrapper, unlike `regexp_match`). It is the semantic equivalent of
473            // the original predicate for the "does it match" question.
474            Self::Regex(pattern) => Expr::ScalarFunction(ScalarFunction {
475                func: Arc::new(RegexpLikeFunc::new().into()),
476                args: vec![
477                    Expr::Column(Column::new_unqualified(col)),
478                    Expr::Literal(ScalarValue::Utf8(Some(pattern.clone())), None),
479                ],
480            }),
481        }
482    }
483
484    fn dyn_eq(&self, other: &dyn AnyQuery) -> bool {
485        match other.as_any().downcast_ref::<Self>() {
486            Some(o) => self == o,
487            None => false,
488        }
489    }
490}
491
492/// A query that a InvertedIndex can satisfy
493#[derive(Debug, Clone, PartialEq)]
494pub enum TokenQuery {
495    /// Retrieve all row ids where the text contains all tokens parsed from given string. The tokens
496    /// are separated by punctuations and white spaces.
497    TokensContains(String),
498}
499
500/// A query that a BloomFilter index can satisfy
501///
502/// This is a subset of SargableQuery that only includes operations that bloom filters
503/// can efficiently handle: equals, is_null, and is_in queries.
504#[derive(Debug, Clone, PartialEq)]
505pub enum BloomFilterQuery {
506    /// Retrieve all row ids where the value is exactly the given value
507    Equals(ScalarValue),
508    /// Retrieve all row ids where the value is null
509    IsNull(),
510    /// Retrieve all row ids where the value is in the given set of values
511    IsIn(Vec<ScalarValue>),
512}
513
514impl AnyQuery for BloomFilterQuery {
515    fn as_any(&self) -> &dyn Any {
516        self
517    }
518
519    fn format(&self, col: &str) -> String {
520        match self {
521            Self::Equals(val) => {
522                format!("{} = {}", col, val)
523            }
524            Self::IsNull() => {
525                format!("{} IS NULL", col)
526            }
527            Self::IsIn(values) => {
528                format!(
529                    "{} IN [{}]",
530                    col,
531                    values
532                        .iter()
533                        .map(|val| val.to_string())
534                        .collect::<Vec<_>>()
535                        .join(",")
536                )
537            }
538        }
539    }
540
541    fn to_expr(&self, col: String) -> Expr {
542        let col_expr = Expr::Column(Column::new_unqualified(col));
543        match self {
544            Self::Equals(value) => col_expr.eq(Expr::Literal(value.clone(), None)),
545            Self::IsNull() => col_expr.is_null(),
546            Self::IsIn(values) => col_expr.in_list(
547                values
548                    .iter()
549                    .map(|val| Expr::Literal(val.clone(), None))
550                    .collect::<Vec<_>>(),
551                false,
552            ),
553        }
554    }
555
556    fn dyn_eq(&self, other: &dyn AnyQuery) -> bool {
557        match other.as_any().downcast_ref::<Self>() {
558            Some(o) => self == o,
559            None => false,
560        }
561    }
562}
563
564impl AnyQuery for TokenQuery {
565    fn as_any(&self) -> &dyn Any {
566        self
567    }
568
569    fn format(&self, col: &str) -> String {
570        format!("{}", self.to_expr(col.to_string()))
571    }
572
573    fn to_expr(&self, col: String) -> Expr {
574        match self {
575            Self::TokensContains(substr) => Expr::ScalarFunction(ScalarFunction {
576                func: Arc::new(CONTAINS_TOKENS_UDF.clone()),
577                args: vec![
578                    Expr::Column(Column::new_unqualified(col)),
579                    Expr::Literal(ScalarValue::Utf8(Some(substr.clone())), None),
580                ],
581            }),
582        }
583    }
584
585    fn dyn_eq(&self, other: &dyn AnyQuery) -> bool {
586        match other.as_any().downcast_ref::<Self>() {
587            Some(o) => self == o,
588            None => false,
589        }
590    }
591}
592
593#[cfg(feature = "geo")]
594#[derive(Debug, Clone, PartialEq)]
595pub struct RelationQuery {
596    pub value: ScalarValue,
597    pub field: Field,
598}
599
600/// A query that a Geo index can satisfy
601#[cfg(feature = "geo")]
602#[derive(Debug, Clone, PartialEq)]
603pub enum GeoQuery {
604    IntersectQuery(RelationQuery),
605    IsNull,
606}
607
608#[cfg(feature = "geo")]
609impl AnyQuery for GeoQuery {
610    fn as_any(&self) -> &dyn Any {
611        self
612    }
613
614    fn format(&self, col: &str) -> String {
615        match self {
616            Self::IntersectQuery(query) => {
617                format!("Intersect({} {})", col, query.value)
618            }
619            Self::IsNull => {
620                format!("{} IS NULL", col)
621            }
622        }
623    }
624
625    fn to_expr(&self, _col: String) -> Expr {
626        todo!()
627    }
628
629    fn dyn_eq(&self, other: &dyn AnyQuery) -> bool {
630        match other.as_any().downcast_ref::<Self>() {
631            Some(o) => self == o,
632            None => false,
633        }
634    }
635}
636
637/// Compute the lexicographically next prefix by incrementing the last character's code point.
638/// Returns None if no valid upper bound exists.
639///
640/// This is used for LIKE prefix queries to convert `LIKE 'foo%'` to range `[foo, fop)`.
641///
642/// # UTF-8 and Unicode Handling
643///
644/// This function operates on Unicode code points (characters), not bytes. Since UTF-8
645/// byte ordering is identical to Unicode code point ordering, incrementing a character's
646/// code point produces the correct lexicographic successor for byte-wise string comparison.
647///
648/// If incrementing the last character would overflow or land in the surrogate range
649/// (U+D800-U+DFFF), we try incrementing the previous character, and so on.
650///
651/// Examples:
652/// - `"foo"` → `Some("fop")`
653/// - `"café"` → `Some("cafê")`  (é U+00E9 → ê U+00EA)
654/// - `"abc中"` → `Some("abc丮")` (中 U+4E2D → 丮 U+4E2E)
655/// - `"cafÿ"` → `Some("cafĀ")` (ÿ U+00FF → Ā U+0100)
656pub fn compute_next_prefix(prefix: &str) -> Option<String> {
657    if prefix.is_empty() {
658        return None;
659    }
660
661    let chars: Vec<char> = prefix.chars().collect();
662
663    // Try incrementing characters from right to left
664    for i in (0..chars.len()).rev() {
665        if let Some(next_char) = next_unicode_char(chars[i]) {
666            let mut result: String = chars[..i].iter().collect();
667            result.push(next_char);
668            return Some(result);
669        }
670        // This character cannot be incremented (e.g., U+10FFFF), try previous
671    }
672
673    // All characters were at maximum value
674    None
675}
676
677/// Get the next valid Unicode scalar value after the given character.
678/// Skips the surrogate range (U+D800-U+DFFF) which is not valid in UTF-8.
679fn next_unicode_char(c: char) -> Option<char> {
680    let cp = c as u32;
681    let next_cp = cp.checked_add(1)?;
682
683    // Skip surrogate range (U+D800-U+DFFF)
684    let next_cp = if (0xD800..=0xDFFF).contains(&next_cp) {
685        0xE000
686    } else {
687        next_cp
688    };
689
690    char::from_u32(next_cp)
691}
692
693#[cfg(test)]
694mod tests {
695    use super::*;
696
697    #[test]
698    fn test_like_prefix_to_expr_escapes_metacharacters() {
699        // The stored prefix is a literal string, so LIKE metacharacters in it must be
700        // escaped when the recheck predicate is rebuilt; otherwise `_`/`%` would act as
701        // wildcards and over-match. The reconstructed expression uses `ESCAPE '\'`.
702        let query = SargableQuery::LikePrefix(ScalarValue::Utf8(Some("a_b%x".to_string())));
703        let Expr::Like(like) = query.to_expr("name".to_string()) else {
704            panic!("expected a LIKE expression");
705        };
706        assert_eq!(like.escape_char, Some('\\'));
707        assert!(!like.negated);
708        assert!(!like.case_insensitive);
709        let Expr::Literal(ScalarValue::Utf8(Some(pattern)), _) = like.pattern.as_ref() else {
710            panic!("expected a Utf8 literal pattern");
711        };
712        assert_eq!(pattern.as_str(), "a\\_b\\%x%");
713
714        // A prefix without metacharacters only gains the trailing wildcard and keeps the
715        // plain `LIKE 'app%'` form (no `ESCAPE`) so the optimized prefix matcher still applies.
716        let query = SargableQuery::LikePrefix(ScalarValue::Utf8(Some("app".to_string())));
717        let Expr::Like(like) = query.to_expr("name".to_string()) else {
718            panic!("expected a LIKE expression");
719        };
720        assert_eq!(like.escape_char, None);
721        let Expr::Literal(ScalarValue::Utf8(Some(pattern)), _) = like.pattern.as_ref() else {
722            panic!("expected a Utf8 literal pattern");
723        };
724        assert_eq!(pattern.as_str(), "app%");
725
726        // A `Utf8View` prefix must get the same treatment instead of falling through to the
727        // catch-all arm: it is normalized to a `Utf8` pattern that keeps the trailing `%`
728        // (and `ESCAPE '\'` when the prefix has metacharacters), so prefix pruning preserves
729        // starts-with semantics rather than degrading to equality.
730        let query = SargableQuery::LikePrefix(ScalarValue::Utf8View(Some("a_b%x".to_string())));
731        let Expr::Like(like) = query.to_expr("name".to_string()) else {
732            panic!("expected a LIKE expression");
733        };
734        assert_eq!(like.escape_char, Some('\\'));
735        let Expr::Literal(ScalarValue::Utf8(Some(pattern)), _) = like.pattern.as_ref() else {
736            panic!("expected a Utf8 literal pattern");
737        };
738        assert_eq!(pattern.as_str(), "a\\_b\\%x%");
739
740        let query = SargableQuery::LikePrefix(ScalarValue::Utf8View(Some("app".to_string())));
741        let Expr::Like(like) = query.to_expr("name".to_string()) else {
742            panic!("expected a LIKE expression");
743        };
744        assert_eq!(like.escape_char, None);
745        let Expr::Literal(ScalarValue::Utf8(Some(pattern)), _) = like.pattern.as_ref() else {
746            panic!("expected a Utf8 literal pattern");
747        };
748        assert_eq!(pattern.as_str(), "app%");
749    }
750}
lance_index/scalar.rs

lance_index/
scalar.rs
