Function compile

src/expr/src/scalar/like_pattern.rs:140–184

Builds a Matcher that matches a SQL LIKE pattern.

(pattern: &str, case_insensitive: bool)

/// Builds a Matcher that matches a SQL LIKE pattern.
pub fn compile(pattern: &str, case_insensitive: bool) -> Result<Matcher, EvalError> {
    // We would like to have a consistent, documented limit to the size of
    // supported LIKE patterns. The real limiting factor is the number of states
    // that can be handled by the Regex library. In testing, I was able to
    // create an adversarial pattern "%a%b%c%d%e..." that started failing around
    // 9 KiB, so we chose 8 KiB as the limit. This is consistent with limits
    // set by other databases, like SQL Server.
    // On the other hand, PostgreSQL does not have a documented limit.
    if pattern.len() > 8 << 10 {
        return Err(EvalError::LikePatternTooLong);
    }
    let subpatterns = build_subpatterns(pattern)?;
    // `is_match_subpatterns` resolves each `%` (a `many` subpattern) by searching
    // for the following suffix and backtracking over every candidate position. A
    // single `%` is near-linear, but with two or more the backtracking nests and
    // the cost becomes super-linear in the text length — an adversarial pattern
    // like `%a%a%a` against a long run of `a`s takes time proportional to
    // `len(text)^(number of %)`, which can stall a worker for many minutes. The
    // regex engine matches the same patterns in linear time with no backtracking,
    // so fall back to it whenever more than one backtracking `%` is present (and
    // for the existing case-insensitive / too-many-subpatterns reasons).
    //
    // A `%` with an *empty* suffix short-circuits in `is_match_subpatterns`
    // without any `rfind`/backtracking, and (per `build_subpatterns`) such a `%`
    // can only ever be the trailing subpattern. Only `%` subpatterns with a
    // non-empty suffix nest the backtracking loops, so we count just those. This
    // keeps the common "contains" pattern `%foo%` — which decomposes into one
    // non-empty-suffix `%` plus a trailing empty-suffix `%` — on the fast string
    // matcher, where a single `rfind` is far cheaper than a forward regex scan.
    let backtracking_manys = subpatterns
        .iter()
        .filter(|s| s.many && !s.suffix.is_empty())
        .count();
    let use_regex =
        case_insensitive || subpatterns.len() > MAX_SUBPATTERNS || backtracking_manys > 1;
    let matcher_impl = match use_regex {
        false => MatcherImpl::String(subpatterns),
        true => MatcherImpl::Regex(build_regex(&subpatterns, case_insensitive)?),
    };
    Ok(Matcher {
        pattern: pattern.into(),
        case_insensitive,
        matcher_impl,
    })
}

// The algorithm below is based on the observation that any LIKE pattern can be
// decomposed into multiple parts: