Opensource internals

ClickHouse Runs Regular Expressions Four Different Ways

35 min read Jay Hubbert

Before touching RE2, ClickHouse analyses the pattern: literal substrings become SIMD substring searches, anchored literals become memcmp, and simple grammars get JIT-compiled to machine code.

TL;DR: match(s, 'foo') in ClickHouse does not run a regexp engine. The pattern is analysed once at construction: if it reduces to a literal substring it becomes a SIMD substring search, if it is anchored it becomes a memcmp, and only genuinely general patterns reach RE2 — and even those get a literal-substring pre-filter first.

Every log-analytics query reaches for match(). Every one of them pays for a regexp engine that they mostly do not need.

sql 
SELECT count() FROM hits WHERE match(url, '/api/v[0-9]+/users');
SELECT count() FROM hits WHERE match(user_agent, 'Mozilla/5.0');
SELECT count() FROM hits WHERE match(path, '^/admin');

Those three queries have almost nothing in common syntactically, but ClickHouse’s regexp layer treats them very differently, and the differences are worth understanding because they are where the performance lives.

The relevant files are src/Common/OptimizedRegularExpression.{h,cpp}, src/Functions/Regexps.h, src/Common/RegexpJIT/RegexpProgram.{h,cpp} and src/Interpreters/JIT/CompileRegexp.cpp.

The tier list

A pattern is classified once, at construction, and the classification picks one of four ways of evaluating it:

text 
                    pattern arrives
                           |
                           v
              +----------------------------+
              |  OptimizedRegularExpression |
              |  constructor: analyse()     |
              +----------------------------+
                           |
        +------------------+------------------+------------------+
        |                  |                  |                  |
        v                  v                  v                  v
   is_trivial?      anchored literal?   required substring?   general
        |                  |                  |                  |
        v                  v                  v                  v
  substring search  memcmp at           substring pre-filter  the regexp
                    one offset          then the regexp       engine
                                                           (JIT or RE2)

The ways, in the order they are checked:

  1. Trivial — the whole pattern is a literal. match(s, 'foo') becomes “does foo occur in s”.
  2. Anchored literal — the pattern is ^literal, literal$, or ^literal$. There is exactly one offset at which it can match, so it becomes a memcmp.
  3. General with a required substring — the pattern contains a literal that must appear in any match. The literal is searched for first; if it is not there, the pattern cannot match and the regexp engine is never invoked.
  4. General — the regexp engine, which for a restricted grammar of patterns is a JIT-compiled native matcher and for everything else is RE2.

Tier 1 and 2: the RegexpMatchKind enum

The classification is recorded in an enum:

cpp 
// src/Common/OptimizedRegularExpression.h:45
/// How `match` evaluates the pattern. Everything except `General` is a comparison against a literal, without re2.
enum class RegexpMatchKind : uint8_t
{
    General,   /// The re2 engine is required.
    Substring, /// The whole pattern is a literal: matches iff the literal occurs anywhere (same as `is_trivial`).
    Exact,     /// `^literal$`: matches iff the subject is equal to the literal.
    Prefix,    /// `^literal`: matches iff the subject starts with the literal.
    Suffix,    /// `literal$`: matches iff the subject ends with the literal.
};

inline bool isAnchoredLiteralMatchKind(RegexpMatchKind kind)
{
    /// A switch instead of a boolean expression, so that a new enum value cannot be silently ignored here.
    switch (kind)
    {
        case RegexpMatchKind::Exact:
        case RegexpMatchKind::Prefix:
        case RegexpMatchKind::Suffix:
            return true;
        case RegexpMatchKind::General:
        case RegexpMatchKind::Substring:
            return false;
    }
}

The comment on isAnchoredLiteralMatchKind is a nice piece of engineering discipline: using a switch over the enum rather than a boolean expression means that adding a new enum value produces a compiler warning at every place that switches on it. With a boolean expression like kind == Exact || kind == Prefix || kind == Suffix, a new value would silently fall into the “not anchored” case.

The anchored-literal matching is a memcmp at a single computed offset:

cpp 
// src/Common/OptimizedRegularExpression.cpp:804
bool OptimizedRegularExpression::matchAnchoredLiteral(const char * subject, size_t subject_size, size_t & match_offset) const
{
    const size_t literal_size = required_substring.size();

    if (subject_size < literal_size)
        return false;

    if (match_kind == RegexpMatchKind::Exact && subject_size != literal_size)
        return false;

    /// `$` in re2 is the end of the text (`\z`, not `\Z`), so there is exactly one offset to compare at.
    const size_t offset = match_kind == RegexpMatchKind::Suffix ? subject_size - literal_size : 0;

    if (0 != memcmp(subject + offset, required_substring.data(), literal_size))
        return false;

    match_offset = offset;
    return true;
}

Note the Exact case: ^literal$ requires the subject to be exactly the literal, so the length must match too. Prefix is a memcmp at offset 0 with no length constraint; Suffix is a memcmp at offset subject_size - literal_size.

The analysis

The classification comes out of analyze(), which runs once in the constructor:

cpp 
// src/Common/OptimizedRegularExpression.cpp:666
RegexpAnalysisResult OptimizedRegularExpression::analyze(std::string_view regexp_)
try
{
    RegexpAnalysisResult r;
    Literals alternative_literals;
    Literal required_literal;
    analyzeImpl(regexp_, regexp_.data(), required_literal, r.is_trivial, r.has_capture, alternative_literals); // NOLINT
    r.required_substring = std::move(required_literal.literal);
    r.required_substring_is_prefix = required_literal.prefix;
    for (auto & lit : alternative_literals)
        r.alternatives.push_back(std::move(lit.literal));

    /// A literal dropped by the analysis above (too short, or tuned away like `www`) leaves nothing to compare against.
    if (r.is_trivial)
        r.match_kind = RegexpMatchKind::Substring;
    else
        r.match_kind = analyzeAnchoredLiteral(regexp_, r.required_substring);

    return r;
}
catch (...)
{
    LOG_ERROR(
        getLogger("OptimizeRegularExpression"), "Analyze RegularExpression failed, got error: {}", DB::getCurrentExceptionMessage(false));
    return {};
}

Two notes. The whole thing is wrapped in a try/catch that swallows errors and returns an empty result — an analysis failure must never make a query fail; it just means “no optimisation available, use RE2”. And the analyze() result is a static function, callable without constructing an OptimizedRegularExpression, which is what the regexp-tree dictionary uses to pre-classify thousands of patterns:

cpp 
// src/Dictionaries/RegExpTreeDictionary.cpp:250
#if USE_VECTORSCAN
        RegexpAnalysisResult result;
        if (use_vectorscan)
            result = OptimizedRegularExpression::analyze(regex);

        for (auto & alter : result.alternatives)
        {
            if (alter.size() < 3)
            {
                result.alternatives.clear();
                break;
            }
        }

The analyser

analyzeImpl is a character-by-character scanner over the pattern. It tracks the current literal run, the nesting depth, whether we are inside a character class, and a set of “alternative” literals for a|b|c patterns.

The core of it is a switch over pattern characters:

cpp 
// src/Common/OptimizedRegularExpression.cpp:365
    while (pos != end)
    {
        switch (*pos)
        {

with each case classifying the character:

cpp 
// src/Common/OptimizedRegularExpression.cpp:489
            case '[':
                /// RE2 reads a `[` inside an already-open character class as a literal member of that
                /// class, so it neither opens a class nor nests. Taking it as another class left the
                /// tracker one level deep after the class had closed, and a top-level `|` after
                /// `[[]` was then not seen as an alternative at all.
                /// The one exception is a POSIX named class such as `[[:alpha:]]`, whose inner
                /// `[:...:]` belongs to the enclosing class and has to be consumed as a whole.
                if (in_square_braces)
                {
                    pos = skipPosixNamedClass(pos, end);
                    break;
                }

                in_square_braces = true;
                ++depth;
                square_braces_body_begin = pos + 1;
                finish_non_trivial_char();
                ++pos;
                break;

            case ']':
                if (!in_square_braces)
                    goto ordinary;

                /// RE2 follows the convention that a `]` written first in a class - right after `[`
                /// or after `[^` - is a literal member of it rather than its end: `[]a]` is the class
                /// of `]` and `a`. Closing the class here instead left the rest of its body to be
                /// analyzed as a top-level literal run, and the prefilter then required a substring
                /// that the pattern does not.
                if (pos == square_braces_body_begin
                    || (pos == square_braces_body_begin + 1 && *square_braces_body_begin == '^'))
                {
                    ++pos;
                    break;
                }

                --depth;
                if (depth == 0)
                    in_square_braces = false;
                finish_non_trivial_char();
                ++pos;
                break;

Read the comments carefully: they are all about matching RE2’s interpretation of the pattern exactly. The analyser is not trying to understand what the user meant; it is trying to compute a sound over-approximation of “what must be in the subject”. If the analyser believes a substring must be present and it is not, then the pattern cannot match — but only if the analyser’s belief is correct. So every edge case in RE2’s syntax has to be mirrored.

The [[:alpha:]] handling is a separate helper for POSIX named classes:

cpp 
// src/Common/OptimizedRegularExpression.cpp:145
/// Recognizes a POSIX named class such as `[:alpha:]` or `[:^digit:]` written inside a character
/// class, and returns the position right after its closing `:]`. `pos` points at the `[`.
/// When this is not a named class, re2 reads the `[` as a literal member of the enclosing class,
/// and the returned position is just the next character.
const char * skipPosixNamedClass(const char * pos, const char * end)
{
    if (end - pos <= 2 || pos[1] != ':')
        return pos + 1;

    /// re2 looks for the closing `:]` in the whole rest of the regexp, not only up to the `]` that
    /// ends the enclosing class, and reads the `[` as a literal when there is none.
    for (const char * name_end = pos + 2; name_end <= end - 2; ++name_end)
        if (name_end[0] == ':' && name_end[1] == ']')
            return name_end + 2;

    return pos + 1;
}

Note “re2 looks for the closing :] in the whole rest of the regexp, not only up to the ] that ends the enclosing class”. That is an obscure RE2 behaviour, and the analyser has to reproduce it exactly.

Escapes and metacharacters

Escapes are handled by a helper that knows which escapes carry arguments that must not be mistaken for literals:

cpp 
// src/Common/OptimizedRegularExpression.cpp:74
/// Skips an escape sequence unsupported by the trivial-substring analysis.
/// Consumes arguments of hex, octal and Unicode property escapes, and the body of
/// `\Q...\E` quoted literals, so they are not treated as regexp-meaningful literals.
/// `pos` points at the character right after the backslash.
const char * skipUnsupportedEscape(const char * pos, const char * end)
{
    if (pos == end)
        return pos;

    auto is_octal_digit = [](char c) { return c >= '0' && c <= '7'; };

    if (*pos == 'x')
    {
        ++pos;
        if (pos != end && *pos == '{')
        {
            while (pos != end && *pos != '}')
                ++pos;
            if (pos != end)
                ++pos;
        }
        else
        {
            for (size_t i = 0; i < 2 && pos != end && isHexDigit(*pos); ++i)
                ++pos;
        }
    }

\Q...\E is the interesting one: it quotes a whole run of text so that its contents are literal. The analyser must consume the body of it, or it would treat the body’s punctuation as regexp syntax.

The “tuning” hack

Once the analysis produces a set of candidate literal runs, the analyser picks the best one — with a hard-coded bias against strings that are common in web analytics:

cpp 
// src/Common/OptimizedRegularExpression.cpp:596
            auto tuning_strings_condition = [](const std::string & str)
            {
                return str != "://" && str != "http://" && str != "www" && str != "Windows ";
            };
            size_t max_length = 0;
            Substrings::const_iterator candidate_it = trivial_substrings.begin();
            for (Substrings::const_iterator it = trivial_substrings.begin(); it != trivial_substrings.end(); ++it)
            {
                if (it->first.size() > max_length && tuning_strings_condition(it->first))
                {
                    max_length = it->first.size();
                    candidate_it = it;
                }
            }

            if (max_length >= MIN_LENGTH_FOR_STRSTR || ((!is_first_call || has_alternative_on_depth_0) && max_length > 0))
            {
                required_substring.literal = candidate_it->first;
                required_substring.prefix = candidate_it->second;
                required_substring.suffix = candidate_it + 1 == trivial_substrings.end();
            }

"://", "http://", "www" and "Windows " are excluded from being chosen as the pre-filter substring. The rationale is in the header comment:

cpp 
// src/Common/OptimizedRegularExpression.h:17
/** Uses two ways to optimize a regular expression:
  * 1. If the regular expression is trivial (reduces to finding a substring in a string),
  *     then replaces the search with strstr or strcasestr.
  * 2. If the regular expression contains a non-alternative substring of sufficient length,
  *     then before testing, strstr or strcasestr of sufficient length is used;
  *     regular expression is only fully checked if a substring is found.
  * 3. In other cases, the re2 engine is used.
  *
  * This makes sense, since strstr and strcasestr in libc for Linux are well optimized.

Consider Mozilla/5.0 as a pattern. The literal run is Mozilla/5.0, which is fine. But consider a pattern like http://example\.com/.* — the literal runs are http://example.com/ and, say, www. If www were chosen, the pre-filter would reject nearly every URL, because almost no URL contains www in the path being matched. Excluding www explicitly is a domain-specific heuristic: the authors knew their users.

MIN_LENGTH_FOR_STRSTR is 3:

cpp 
// src/Common/OptimizedRegularExpression.cpp:14
constexpr size_t MIN_LENGTH_FOR_STRSTR = 3;

Below three characters, a substring search is not worth its overhead — a two-character substring scan over a long haystack is not much cheaper than running the regexp automaton, and the pre-filter would reject too few subjects.

Tier 3: the pre-filter

The pre-filter is the second tier of the optimisation, and it is where most real-world patterns land. Here is the whole match path:

cpp 
// src/Common/OptimizedRegularExpression.cpp:824
bool OptimizedRegularExpression::match(const char * subject, size_t subject_size) const
{
    if (isAnchoredLiteral())
    {
        size_t match_offset = 0;
        return matchAnchoredLiteral(subject, subject_size, match_offset);
    }

    const UInt8 * haystack = reinterpret_cast<const UInt8 *>(subject);
    const UInt8 * haystack_end = haystack + subject_size;

    if (is_trivial)
    {
        if (required_substring.empty())
            return true;

        if (is_case_insensitive)
            return haystack_end != case_insensitive_substring_searcher->search(haystack, subject_size);
        return haystack_end != case_sensitive_substring_searcher->search(haystack, subject_size);
    }

    if (!required_substring.empty())
    {
        if (is_case_insensitive)
        {
            if (haystack_end == case_insensitive_substring_searcher->search(haystack, subject_size))
                return false;
        }
        else
        {
            if (haystack_end == case_sensitive_substring_searcher->search(haystack, subject_size))
                return false;
        }
    }

    return re2->Match({subject, subject_size}, 0, subject_size, re2::RE2::UNANCHORED, nullptr, 0);
}

The structure is a series of early exits. The third one is the pre-filter: if the required substring is not present, return false without touching RE2. The searchers are ClickHouse’s own CaseSensitiveStringSearcher and ASCIICaseInsensitiveStringSearcher, which are SIMD-accelerated substring searchers (not libc strstr, despite the comment).

The constructors pick the searcher:

cpp 
// src/Common/OptimizedRegularExpression.cpp:770
    if (!required_substring.empty())
    {
        if (is_case_insensitive)
            case_insensitive_substring_searcher = std::make_unique<ASCIICaseInsensitiveStringSearcher>(
                reinterpret_cast<UInt8 *>(required_substring.data()), required_substring.size());
        else
            case_sensitive_substring_searcher = std::make_unique<CaseSensitiveStringSearcher>(
                reinterpret_cast<UInt8 *>(required_substring.data()), required_substring.size());
    }

Note that ASCIICaseInsensitiveStringSearcher folds only ASCII, and the constructor refuses to use the anchored-literal path in that case:

cpp 
// src/Common/OptimizedRegularExpression.cpp:707
    /// A case-insensitive re2 folds Unicode (`k` also matches U+212A), which a byte comparison cannot reproduce.
    if (is_case_insensitive && isAnchoredLiteral())
        match_kind = RegexpMatchKind::General;

That is a correctness guard: RE2’s case-insensitive matching folds k with the Kelvin sign U+212A, so ^K$ would match a three-byte string in RE2 but not with an ASCII memcmp. Rather than get it wrong, the anchored optimisation is disabled for case-insensitive patterns.

The compile-time decision

The constructor also decides not to build an RE2 object at all when the pattern is trivial or anchored:

cpp 
// src/Common/OptimizedRegularExpression.cpp:693
OptimizedRegularExpression::OptimizedRegularExpression(const std::string & regexp_, int options)
{
    /// Just three following options are supported
    if (options & (~(RE_CASELESS | RE_NO_CAPTURE | RE_DOT_NL)))
        throw DB::Exception(DB::ErrorCodes::CANNOT_COMPILE_REGEXP, "OptimizedRegularExpression: Unsupported option.");

    RegexpAnalysisResult result = analyze(regexp_);
    required_substring = result.required_substring;
    is_trivial = result.is_trivial;
    has_capture = result.has_capture;
    required_substring_is_prefix = result.required_substring_is_prefix;
    match_kind = result.match_kind;
    is_case_insensitive = options & RE_CASELESS;
cpp 
// src/Common/OptimizedRegularExpression.cpp:714
    number_of_subpatterns = 0;
    if (!is_trivial && !isAnchoredLiteral())
    {
        /// re2 patterns can be machine-generated and huge; bound them in error messages.
        /// Truncate on a UTF-8 code point boundary so a multi-byte character is not cut in half.
        auto for_message = [](const std::string & re) -> std::string
        {
            static constexpr size_t max_code_points = 256;
            const size_t bytes = DB::UTF8::computeBytesBeforeCodePoint(
                reinterpret_cast<const UInt8 *>(re.data()), re.size(), max_code_points);
            if (bytes >= re.size())
                return re;
            return re.substr(0, bytes) + "... (truncated, " + std::to_string(re.size()) + " bytes total)";
        };

So for match(s, 'foo'), no RE2 object is ever constructed. The pattern is analysed, classified as Substring, and the only thing that exists is a substring searcher.

The for_message lambda is a nice defensive touch: a machine-generated pattern can be megabytes long, and putting it in an exception message would be a problem. It truncates on a UTF-8 code point boundary so a multi-byte character is not cut in half.

The re2 object is built with UTF-8 encoding but falls back to Latin-1:

cpp 
// src/Common/OptimizedRegularExpression.cpp:729
        /// Compile the re2 regular expression.
        re2::RE2::Options regexp_options;

        /// Never write error messages to stderr. It's ignorant to do it from library code.
        regexp_options.set_log_errors(false);

        if (is_case_insensitive)
            regexp_options.set_case_sensitive(false);

        if (is_dot_nl)
            regexp_options.set_dot_nl(true);

        re2 = std::make_unique<re2::RE2>(regexp_, regexp_options);

        /// Fallback to latin1 to allow matching binary data.
        if (!re2->ok() && re2->error_code() == re2::RE2::ErrorCode::ErrorBadUTF8)
        {
            regexp_options.set_encoding(re2::RE2::Options::EncodingLatin1);
            re2 = std::make_unique<re2::RE2>(regexp_, regexp_options);
        }

The Latin-1 fallback matters: match on binary data with a pattern containing invalid UTF-8 would otherwise fail to compile. And the capture group count is bounded:

cpp 
// src/Common/OptimizedRegularExpression.cpp:762
        if (!is_no_capture)
        {
            number_of_subpatterns = re2->NumberOfCapturingGroups();
            if (number_of_subpatterns > MAX_SUBPATTERNS)
                throw DB::Exception(DB::ErrorCodes::CANNOT_COMPILE_REGEXP, "OptimizedRegularExpression: too many subpatterns in regexp: {}", for_message(regexp_));
        }

MAX_SUBPATTERNS is 1024.

Matching many times: the limit trick

OptimizedRegularExpression::match has an overload that returns many matches, used by extractAll and replaceRegexp*. The limit parameter is the “match with a limited number of matches” trick:

cpp 
// src/Common/OptimizedRegularExpression.h:121
    /// Search starting at `start_pos` (a byte offset into `subject`), while keeping the whole `subject` available as
    /// context. This is required for the correct evaluation of zero-width assertions such as `^`, `$` and `\b`: they
    /// must see the characters surrounding `start_pos`. Iterative "match all" functions must use this overload and
    /// advance `start_pos` instead of shifting the `subject` pointer, otherwise every continuation point looks like the
    /// beginning of the text. The returned match offsets are relative to `subject` (not to `start_pos`).
    unsigned match(const char * subject, size_t subject_size, size_t start_pos, MatchVec & matches) const
    {
        return match(subject, subject_size, start_pos, matches, number_of_subpatterns + 1);
    }

    bool match(const char * subject, size_t subject_size) const;
    bool match(const char * subject, size_t subject_size, Match & match) const;

    unsigned match(const char * subject, size_t subject_size, MatchVec & matches, unsigned limit) const
    {
        return match(subject, subject_size, 0, matches, limit);
    }

    unsigned match(const char * subject, size_t subject_size, size_t start_pos, MatchVec & matches, unsigned limit) const;

The start_pos parameter is subtle and important. If you wanted all matches you could naively call match repeatedly on successively shorter suffixes of the subject. But that would break ^, $ and \b: a \b at the start of the suffix would see the suffix’s first character as the beginning of the text, and a ^ would match in the middle of the string. Keeping the whole subject as context and passing a start offset is the only correct way.

The limit is clamped to the number of capture groups plus one, because that is how many spans RE2 can report:

cpp 
// src/Common/OptimizedRegularExpression.cpp:931
unsigned OptimizedRegularExpression::match(const char * subject, size_t subject_size, size_t start_pos, MatchVec & matches, unsigned limit) const
{
    const UInt8 * haystack = reinterpret_cast<const UInt8 *>(subject);
    const UInt8 * haystack_end = haystack + subject_size;
    /// Search starts here, but the characters before it remain available as context for zero-width assertions.
    const UInt8 * search_begin = haystack + start_pos;

    matches.clear();

    if (limit == 0)
        return 0;

    limit = std::min(limit, number_of_subpatterns + 1);

and the actual RE2 call uses a stack-allocated array for the pieces:

cpp 
// src/Common/OptimizedRegularExpression.cpp:994
    DB::PODArrayWithStackMemory<std::string_view, 128> pieces(limit);

    if (!re2->Match({subject, subject_size}, start_pos, subject_size, re2::RE2::UNANCHORED, pieces.data(), static_cast<int>(pieces.size())))
    {
        return 0;
    }

PODArrayWithStackMemory<std::string_view, 128> means: up to 128 elements on the stack, no allocation. Since limit is clamped to number_of_subpatterns + 1 and MAX_SUBPATTERNS is 1024, a pathological pattern could exceed 128 and spill to the heap — but the common case does not allocate at all.

Tier 4: the regexp JIT

The last tier is a JIT that replaces RE2 for a restricted subset of patterns. It is a separate subsystem from the expression JIT: it has its own tiny IR, its own parser, and its own LLVM emitter.

The IR

The IR is deliberately tiny and has no LLVM dependency:

cpp 
// src/Common/RegexpJIT/RegexpProgram.h:11
/** Intermediate representation of a regular expression that belongs to a "simple" subset,
  * suitable for compilation into a native, branch-light, SIMD-friendly matcher (see `CompileRegexp.h`).
  *
  * The representation is intentionally tiny and free of any LLVM dependency, so it can live in
  * `Common` and be unit-tested in isolation. `tryCompileToProgram` is the parser: it returns
  * `std::nullopt` for anything outside the supported subset, in which case the caller must fall
  * back to the general engine (RE2). The parser is conservative on purpose - false negatives
  * (falling back to RE2 for a pattern we could have handled) are harmless, false positives
  * (accepting a pattern whose semantics we get wrong) are bugs.
  *
  * Semantics are byte-wise (Latin-1), matching how RE2 is used by the affected functions when
  * the pattern stays in the supported subset; any construct that would require Unicode-aware
  * matching makes the parser bail out.
  */

“False negatives are harmless, false positives are bugs” — that is the governing principle of the whole design, and it is stated up front.

The op set:

cpp 
// src/Common/RegexpJIT/RegexpProgram.h:86
enum class OpKind : uint8_t
{
    Literal,        /// Match a fixed byte string at the cursor and advance past it.
    PrefixAnchor,   /// `^` - assert the cursor is at the string start.
    SuffixAnchor,   /// `$` - assert the cursor is at the string end.
    CharQuant,      /// `[set]`, `[set]?`, `[set]*`, `[set]+`, `[set]{n,m}`, `.`, `.*`, a single char/class.
    Optional,       /// `(?:...)?` / `(...)?` - greedily match `body`, or skip it.
    CaptureStart,   /// Record the cursor as the start of capture group `capture_index`.
    CaptureEnd,     /// Record the cursor as the end of capture group `capture_index`.
};

Character classes are 256-bit membership bitmaps:

cpp 
// src/Common/RegexpJIT/RegexpProgram.h:28
/// A set of bytes, as a 256-bit membership bitmap. `[abc]`, `[^abc]`, `.`, `\d`, ... all reduce to this.
struct CharSet
{
    std::array<uint64_t, 4> bitmap{};

    void add(uint8_t c) { bitmap[c >> 6] |= (1ULL << (c & 63u)); }
    bool contains(uint8_t c) const { return (bitmap[c >> 6] >> (c & 63u)) & 1u; }

and each quantified op records whether it can be matched without backtracking:

cpp 
// src/Common/RegexpJIT/RegexpProgram.h:104
    /// OpKind::CharQuant
    CharSet set;
    uint32_t min = 1;
    uint32_t max = 1;                       /// UINT32_MAX means unbounded.
    bool greedy = true;
    /// True if the stop position is unambiguous (the following first-byte set is disjoint from `set`,
    /// or the quantifier is right-anchored), so it can be matched in a single greedy pass with no
    /// backtracking. Filled by `tryCompileToProgram`. See the no-backtracking analysis there.
    bool deterministic = true;

The conservative parser

The parser bails out on anything it does not fully understand. The bail-out list is long and specific:

cpp 
// src/Common/RegexpJIT/RegexpProgram.cpp:12
constexpr uint32_t UNBOUNDED = std::numeric_limits<uint32_t>::max();

/// Maximum number of `Optional` constructs we are willing to compile. Each one can duplicate the
/// continuation in the generated code, so without a cap the code size could grow exponentially.
constexpr int MAX_OPTIONALS = 4;
/// We only JIT-compile patterns that match greedily without any backtracking, so matching is always
/// linear in the input (never slower than the general engine). A quantifier needs backtracking when
/// its stop is ambiguous (the following first-byte set overlaps the quantified set and it is not
/// right-anchored) - e.g. `.*a`; such patterns fall back to the general engine. A quantifier whose
/// stop is unambiguous - e.g. `.+`, `[^/]+/`, `.*$` - is matched in a single greedy pass.
/// See `analyzeFirst`.
constexpr int MAX_NONDET_QUANTIFIERS = 0;
/// Guard against pathological nesting depth.
constexpr int MAX_DEPTH = 16;

MAX_NONDET_QUANTIFIERS = 0 is the striking one: the JIT does not compile a single backtracking quantifier. Every pattern it accepts matches in a single greedy pass. That is a performance guarantee, not just a simplification: a JIT-compiled matcher that backtracks could be quadratic or worse, which would be worse than RE2’s guarantee.

The backtracking analysis is a first-set computation:

cpp 
// src/Common/RegexpJIT/RegexpProgram.cpp:632
/// Compute, for each position, the set of bytes that the continuation can begin with, and use it to
/// mark every `CharQuant` as `deterministic` (its stop is unambiguous: the following first-byte set
/// is disjoint from the quantified set, or it is right-anchored - the following set is empty).
/// A deterministic quantifier matches in a single greedy pass with no backtracking.
/// Side effects: counts variable quantifiers that are NOT deterministic (`nondet_quant`, each of
/// which needs an O(n) give-back) and `Optional` groups (`fork_count`, a bounded 2-way choice).
/// Returns the first-byte set of `ops`, given that what follows them can begin with `follow`.
static CharSet analyzeFirst(std::vector<Op> & ops, const CharSet & follow, int & nondet_quant, int & fork_count)
{
    const size_t n = ops.size();
    std::vector<CharSet> rest_first(n + 1);
    rest_first[n] = follow;

    for (size_t i = n; i-- > 0;)
    {
        Op & op = ops[i];
        const CharSet & after = rest_first[i + 1];
        switch (op.kind)
        {
            case OpKind::Literal:
            {
                CharSet first;
                if (!op.literal.empty())
                    first.add(op.literal[0]);
                rest_first[i] = first; /// a literal is not nullable
                break;
            }
            case OpKind::CharQuant:
            {
                op.deterministic = !op.set.intersects(after);
                if (!op.deterministic && op.min < op.max)
                    ++nondet_quant;
                rest_first[i] = op.set;
                if (op.min == 0) /// can match zero characters, so the continuation is also possible here
                    rest_first[i].unite(after);
                break;
            }

The logic: a quantifier over set S is deterministic if the next thing can only start with a byte not in S. Take [^/]+/: the quantified set is “not slash”, and the continuation is “/”, which is disjoint — so the run stops unambiguously at the first slash, no give-back needed. Take .*a: the quantified set is “anything”, and the continuation is “a”, which overlaps — so the run might have to give back characters. The latter is rejected.

There is another subtle correctness guard, about Unicode case folding:

cpp 
// src/Common/RegexpJIT/RegexpProgram.cpp:688
/// RE2 runs case-insensitive matching in UTF-8 mode with Unicode-aware (simple) case folding. The only
/// ASCII letters whose fold class reaches outside ASCII are `k`/`K` (which also fold to U+212A KELVIN
/// SIGN, UTF-8 `E2 84 AA`) and `s`/`S` (which also fold to U+017F LATIN SMALL LETTER LONG S, UTF-8
/// `C5 BF`). Our matcher folds ASCII only and scans byte-wise, so it can match (or, for a maximal run,
/// fail to stop at) those code points differently from RE2. Detect that and fall back to the general
/// engine.
static bool caseInsensitiveTouchesNonAsciiFold(const std::vector<Op> & ops)

The check is subtle because a negated class can accidentally include the high bytes of the Kelvin sign:

cpp 
// src/Common/RegexpJIT/RegexpProgram.cpp:709
                /// A byte-wise scan agrees with RE2 on a fold code point only when the set's membership of
                /// the ASCII letter equals its membership of every byte of that code point's UTF-8 encoding.
                /// Checking only `set.contains('k'/'s')` (as a previous version did) misses negated classes:
                /// e.g. `(?i)[^a-z]` excludes `k`/`s` after folding and inversion, yet its inverted bitmap
                /// contains the high bytes of KELVIN SIGN / LONG S, so the matcher would accept those bytes
                /// while RE2 (folding them to `k`/`s`) rejects them.
                const CharSet & set = op.set;
                const bool kelvin_matches_as_k = set.contains(0xE2) && set.contains(0x84) && set.contains(0xAA);
                const bool long_s_matches_as_s = set.contains(0xC5) && set.contains(0xBF);
                if (set.contains('k') != kelvin_matches_as_k || set.contains('s') != long_s_matches_as_s)
                    return true;

The comment says “as a previous version did” — this is a bug that was found and fixed, and the comment documents exactly what the old code got wrong.

The bail-out list

tryCompileToProgram is where all the conservative decisions are made:

cpp 
// src/Common/RegexpJIT/RegexpProgram.cpp:751
std::optional<RegexpProgram> tryCompileToProgram(std::string_view pattern, const ParseFlags & flags)
{
    if (pattern.empty())
        return std::nullopt;

    /// A case-insensitive pattern containing non-ASCII bytes would need Unicode case folding.
    if (flags.case_insensitive)
        for (unsigned char c : pattern)
            if (!isAscii(c))
                return std::nullopt;

    Parser parser(pattern, flags);
    auto program = parser.parse();
    if (!program)
        return std::nullopt;
cpp 
// src/Common/RegexpJIT/RegexpProgram.cpp:767
    /// `OptimizedRegularExpression` rejects patterns with more than `MAX_SUBPATTERNS` (1024) capturing
    /// groups; accepting them here would turn that error into a successful match. `num_captures` counts
    /// group 0 (the whole match), so the number of capturing groups is `num_captures - 1`.
    constexpr int MAX_SUBPATTERNS = 1024;
    if (program->num_captures - 1 > MAX_SUBPATTERNS)
        return std::nullopt;

Note the reasoning: the JIT must not accept a pattern that OptimizedRegularExpression would reject, because that would turn an error into a successful match — a behaviour change.

cpp 
// src/Common/RegexpJIT/RegexpProgram.cpp:779
    /// A pure unanchored literal (e.g. `abc`, `\.com`) is already handled optimally by the
    /// substring searcher inside `OptimizedRegularExpression`; the JIT's position-by-position scan
    /// would be slower, so defer such patterns to the general engine.
    if (!program->anchored_start && !program->anchored_end && program->ops.size() == 1
        && program->ops[0].kind == OpKind::Literal)
        return std::nullopt;

    /// Bound the generated code size: `emitLiteral` emits one comparison per literal byte, so a pattern
    /// such as `^` + a very large literal + `$` would otherwise make LLVM compile an enormous function
    /// once the compile-count threshold is reached. Such patterns gain nothing from the JIT (RE2 already
    /// searches long literals optimally), so fall back to the general engine.
    constexpr size_t MAX_PROGRAM_SIZE = 256;
    if (programSize(program->ops) > MAX_PROGRAM_SIZE)
        return std::nullopt;

The first of these is an interesting piece of engineering honesty: the JIT defers a pattern it could handle, because the substring searcher in OptimizedRegularExpression is already faster for that shape. The JIT’s position-by-position scan is only a win for patterns that need structure.

The emitter

The LLVM emitter builds a matcher with the signature:

cpp 
// src/Interpreters/JIT/CompileRegexp.h:36
using JITRegexpMatcherFunc = uint8_t (*)(
    const uint8_t * begin, const uint8_t * end, const uint8_t * search_from,
    const uint8_t ** capture_starts, const uint8_t ** capture_ends);

The third argument search_from is what lets extractAll iterate: the matcher searches at or after search_from while keeping begin/end as the context for ^/$.

The emitter is a continuation-passing style translation into basic blocks:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:142
/// Emits LLVM IR for the per-string matcher described by a `RegexpProgram`.
///
/// The matcher is a depth-first, greedy, backtracking search over the program's operations,
/// expressed entirely with basic blocks: each operation either advances the cursor and continues
/// with the rest of the program (in continuation-passing style) or branches to a failure label.
/// Variable-length operations (`CharQuant`, `Optional`) introduce backtracking points - a greedy
/// "give-back" loop for quantifiers and a body/skip fork for optionals - which keeps the matcher
/// equivalent to RE2 on the supported subset without an explicit backtracking stack.

The character-class scan is where the SIMD comes in:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:365
    /// Emit a scan that consumes the maximal run of bytes that are in `set`, starting at `cursor`,
    /// stopping at the first byte not in `set` or at `scan_limit` (which callers set to `end` for an
    /// unbounded quantifier, or to `cursor + max` for a bounded one so the scan does no more work than
    /// the cap allows). Leaves the insert point at a fresh block where the returned value (a pointer to
    /// the stop position) is available.
    llvm::Value * emitConsumeRun(llvm::Value * cursor, const CharSet & set, llvm::Value * scan_limit)
    {
        size_t in_count = set.count();
        if (in_count == 0)
            return cursor;
        if (in_count == 256)
            return scan_limit; /// Every byte is in the set, so the run extends all the way to `scan_limit`.

        /// Pick the cheaper set to test with SIMD: the members themselves, or the stop set (complement).
        bool stop_when_member = false;
        std::vector<uint8_t> members;
        bool use_simd = true;
        if (in_count <= SIMD_MEMBERS_MAX)
        {
            members = listMembers(set, /* complement */ false);
            stop_when_member = false; /// stop at the first byte that is NOT one of the members.
        }
        else if (256 - in_count <= SIMD_MEMBERS_MAX)
        {
            members = listMembers(set, /* complement */ true);
            stop_when_member = true; /// stop at the first byte that IS a stop member.
        }
        else
        {
            use_simd = false;
        }

with SIMD_MEMBERS_MAX = 8. So the SIMD path is used when the set (or its complement) has at most 8 members; otherwise the emitter falls back to a 256-byte lookup table:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:469
        b.SetInsertPoint(scalar_test);
        auto * byte = loadByte(p);
        auto * table_elem = b.CreateInBoundsGEP(
            llvm::ArrayType::get(b.getInt8Ty(), 256), set_table, {b.getInt64(0), b.CreateZExt(byte, b.getInt64Ty())});
        auto * in_set = b.CreateICmpNE(loadByte(table_elem), b.getInt8(0));
        run_end->addIncoming(p, scalar_test);
        b.CreateCondBr(in_set, advance1, done);

And the SIMD body:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:433
            b.SetInsertPoint(simd_body);
            auto * vec = b.CreateAlignedLoad(vec_type, p, llvm::Align(1));
            llvm::Value * match_vec = nullptr;
            for (uint8_t m : members)
            {
                auto * splat = b.CreateVectorSplat(16, b.getInt8(m));
                auto * eq = b.CreateICmpEQ(vec, splat);
                match_vec = match_vec ? b.CreateOr(match_vec, eq) : eq;
            }
            auto * match_mask = b.CreateBitCast(match_vec, b.getInt16Ty());
            auto * stop_mask = stop_when_member ? match_mask : b.CreateNot(match_mask);
            auto * any_stop = b.CreateICmpNE(stop_mask, b.getInt16(0));
            b.CreateCondBr(any_stop, simd_hit, advance16);

            b.SetInsertPoint(simd_hit);
            auto * cttz = llvm::Intrinsic::getOrInsertDeclaration(&module, llvm::Intrinsic::cttz, {b.getInt16Ty()});
            auto * tz = b.CreateCall(cttz, {stop_mask, b.getTrue()});

Sixteen bytes at a time, with cttz to find the first matching byte. The bitmap is 16 bytes wide but only 8 members, so the comparison is up to 8 pcmpeqb + 7 por per 16 bytes — cheap.

The unanchored search and the quadratic trap

There is one more piece of the emitter that is worth calling out, because it addresses a real algorithmic problem:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:203
            /// Unanchored match: try every start position from `search_from` to `end` (inclusive), leftmost wins.
            ///
            /// If the program begins with an unbounded greedy quantifier over a byte set (possibly behind
            /// leading zero-width operations - capture markers or empty optionals like `()?` / `(?:)?` -
            /// which do not move the cursor), a failed attempt at `start` also fails at every position
            /// strictly inside the consumed run: at an interior start the quantifier consumes the same run
            /// end, and the set of give-back positions it tries is a subset of those already tried (and
            /// rejected) at `start`. So the search can resume at that run's end instead of `start + 1`.
            /// Without this, patterns like `[0-9]+a` or `()?[0-9]+a` on non-matching input rescan the run at
            /// every offset and are quadratic. This shortcut is sound only for `max == UNBOUNDED`: a finite
            /// `max` can still match by aligning its bounded window later in the run, so the bounded case
            /// relies on the `cursor + max` scan cap in `emitCharQuant` instead.
            for (const Op & op : top_ops)
            {
                if (isZeroWidthOp(op))
                    continue; /// does not move the cursor, so it does not affect the run the quantifier consumes
                if (op.kind == OpKind::CharQuant && op.max == UNBOUNDED)
                    leading_quant_op = &op;
                break; /// the first cursor-advancing operation decides
            }

The naive unanchored search tries every start position. If the pattern starts with [0-9]+ and the input is a long run of digits with no a at the end, then every start position inside the run re-scans the whole run — quadratic. The fix is to observe that if the attempt at the start of the run failed, every interior start will also fail (it consumes the same run end and has fewer give-back positions), so the search can jump straight to the end of the run.

This is a real algorithmic improvement, and it is only sound because of the analysis that went with it. The bounded case ([0-9]{1,5}a) cannot use the shortcut, because a later start can succeed by aligning its window differently — so the bounded case relies on a different mechanism, capping the scan at cursor + max:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:508
    void emitCharQuant(const Op & op, llvm::Value * cursor, const Cont * rest, llvm::BasicBlock * fail)
    {
        /// For a finite `max`, cap the run scan at `cursor + max`. Scanning the whole maximal run first
        /// and only then clamping to `max` is what makes iterative callers (`extractAll`,
        /// `replaceRegexpAll`) with bounded repeats quadratic, as each call rescans the full remainder.
        llvm::Value * scan_limit = end_arg;
        if (op.max != UNBOUNDED)
        {
            auto * max_ptr = gepByte(cursor, static_cast<int64_t>(op.max));
            scan_limit = b.CreateSelect(b.CreateICmpUGT(max_ptr, end_arg), end_arg, max_ptr);
        }

The compilation cache and the count threshold

The JIT is only worth it for a hot pattern. The threshold is a setting:

cpp 
// src/Core/Settings.cpp:1466
    DECLARE(Bool, compile_regular_expressions, true, R"(
Compile simple regular expressions used in functions like `match` and `extract` to native code. Patterns outside the supported subset transparently fall back to the general engine.
)", 0, \
        {"26.7", false, true, "New setting to enable JIT compilation of simple regular expressions in functions like `match` and `extract`."}) \
    DECLARE(UInt64, min_count_to_compile_regular_expression, 3, R"(
Minimum count of executing same regular expression before it is get compiled.
)", 0, \
        {"26.7", 3, 3, "New setting controlling how many times a regular expression must be used before it is JIT-compiled."}) \

Default: on, and compile after 3 uses. The counting is done in a bounded map:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:51
    /// Counts how many times each (pattern, flags) key has been seen, so a pattern is compiled only after
    /// `min_count_to_compile` uses (mirrors `compile_expressions`). It is bounded: cleared wholesale once
    /// it grows past `MAX_SEEN_COUNTER_ENTRIES`, and also reset by `resetRegexpJITInstance` (i.e. by
    /// `SYSTEM DROP COMPILED EXPRESSION CACHE`), so the default-enabled path cannot accumulate unbounded
    /// process-wide state for workloads with many unique patterns.
    std::mutex regexp_seen_counter_mutex;
    std::unordered_map<UInt128, UInt64, UInt128Hash> regexp_seen_counter;
    constexpr size_t MAX_SEEN_COUNTER_ENTRIES = 10000;

and the whole lookup:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:704
RegexpJITMatcher getRegexpJITMatcher(
    const std::string & pattern, bool case_insensitive, bool dot_all, size_t min_count_to_compile)
{
    /// `std::numeric_limits<size_t>::max()` is the disabled sentinel (`compile_regular_expressions = 0`).
    /// Return before doing any work, so a disabled JIT neither parses patterns nor grows the seen-count
    /// map - some callers (`extractAll`, `replaceRegexp*`) invoke this unconditionally.
    if (min_count_to_compile == std::numeric_limits<size_t>::max())
        return {};

    /// Without a compiled-expression cache nothing outlives the call that compiled the matcher, so a hot
    /// pattern pays a full LLVM compile on every call, serialised on one process-wide lock. Stay on RE2.
    auto * compiled_expression_cache = CompiledExpressionCacheFactory::instance().tryGetCache();
    if (!compiled_expression_cache)
        return {};

The second early-out is important: without a compiled-expression cache, the compiled matcher would be destroyed at the end of the call, and the next call would recompile it — paying an LLVM compilation per query block, serialised on a process-wide lock. That would be far worse than RE2.

The compiled matcher is stored in the shared compiled-expression cache, keyed by a SipHash of the pattern and flags:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:654
UInt128 computeKey(const std::string & pattern, bool case_insensitive, bool dot_all)
{
    SipHash hash;
    hash.update(pattern.data(), pattern.size());
    hash.update(case_insensitive);
    hash.update(dot_all);
    return hash.get128();
}

And failures are swallowed:

cpp 
// src/Interpreters/JIT/CompileRegexp.cpp:752
    catch (...)
    {
        /// A failure to compile is not a correctness problem - the caller falls back to RE2.
        tryLogCurrentException(getLogger("CompileRegexp"), "Failed to JIT-compile a regular expression, falling back to RE2");
        return {};
    }

Using the JIT

The call site, in MatchImpl.h, is where the tiering becomes visible:

cpp 
// src/Functions/MatchImpl.h:164
        /// Fast path: a JIT-compiled matcher for a simple regular expression (see `CompileRegexp.h`).
        /// LIKE and SIMILAR TO patterns are not regular expressions (the needle is not an RE2 pattern),
        /// so they never take this path.
        if constexpr (!is_like_or_similar_to)
        {
            if (regexp_jit_min_count != std::numeric_limits<size_t>::max())
            {
                /// `match`/`extract` build RE2 with `RE_DOT_NL` (see `Regexps::createRegexp`), so `.` matches newline.
                if (auto matcher = getRegexpJITMatcher(needle, case_insensitive, /* dot_all */ true, regexp_jit_min_count))
                {
                    /// Allocated once per call (not per row); reused for every row below.
                    VectorWithMemoryTracking<const uint8_t *> capture_starts(matcher.num_captures);
                    VectorWithMemoryTracking<const uint8_t *> capture_ends(matcher.num_captures);

                    size_t prev_offset = 0;
                    for (size_t i = 0; i < input_rows_count; ++i)
                    {
                        const auto * str_begin = reinterpret_cast<const uint8_t *>(haystack_data.data() + prev_offset);
                        const auto * str_end = reinterpret_cast<const uint8_t *>(haystack_data.data() + haystack_offsets[i]);
                        const bool matched = matcher.func(str_begin, str_end, str_begin, capture_starts.data(), capture_ends.data()) == 1;
                        res[i] = negate ^ matched;
                        prev_offset = haystack_offsets[i];
                    }

Note the “allocated once per call (not per row)” comment: the capture arrays are sized once and reused for every row, because the matcher writes into them rather than returning them.

And there is a debug-mode verification, comparing every JIT result against RE2:

cpp 
// src/Functions/MatchImpl.h:188
#ifndef NDEBUG
                    verifyMatchAgainstRE2(haystack_data, haystack_offsets, needle, res, input_rows_count);
#endif

That is the kind of thing that makes a “bit-for-bit identical to RE2” claim credible: in a debug build, every JIT result is checked against the general engine.

extractAll and the iteration protocol

extractAll uses the matcher in a loop, and the search_from protocol matters:

cpp 
// src/Functions/extractAll.cpp:121
            /// Search for the leftmost match at or after `pos`, but keep the whole string `[begin, end)` as the
            /// subject so that `^` stays anchored at the true string start (as in the RE2 path below) instead of
            /// re-anchoring at every iteration. The matcher reports capture spans as absolute pointers into the
            /// haystack (see `CompileRegexp.h`).
            const auto * subject_begin = reinterpret_cast<const uint8_t *>(begin);
            const auto * subject_end = reinterpret_cast<const uint8_t *>(end);
            const auto * search_from = reinterpret_cast<const uint8_t *>(pos);
            if (matcher.func(subject_begin, subject_end, search_from, capture_starts.data(), capture_ends.data()) != 1)
                return false;
            if (capture_ends[0] == capture_starts[0]) /// empty whole match - stop, like the RE2 path
                return false;

The local cache

One more piece: the pattern cache. RE2 compilation is expensive, and a query often uses the same handful of patterns over and over:

cpp 
// src/Functions/Regexps.h:92
/// Caches compiled re2 objects for given string patterns. Intended to support the common situation of a small set of patterns which are
/// evaluated over and over within the same query. In these situations, usage of the cache will save unnecessary pattern re-compilation.
/// However, we must be careful that caching does not add too much static overhead to overall pattern evaluation. Therefore, the cache is
/// intentionally very lightweight: a) no thread-safety/mutexes, b) small & fixed capacity, c) no collision list, d) but also no open
/// addressing, instead collisions simply replace the existing element.
class LocalCacheTable
{

The design constraints in that comment are the interesting part: no mutexes. The cache is per-thread (it is a function-local static in the caller), so no synchronisation is needed. 1000 buckets, no collision list, no open addressing — a collision just replaces the entry.

cpp 
// src/Functions/Regexps.h:109
    template <bool like, bool similar_to, bool no_capture, bool case_insensitive>
    const OptimizedRegularExpression & getOrSet(std::string_view pattern)
    {
        Bucket & bucket = known_regexps[hasher(pattern) % CACHE_SIZE];

        if (bucket.regexp == nullptr) [[unlikely]]
        {
            /// insert new entry
            ++misses;
            String key(pattern);
            auto compiled = std::make_unique<OptimizedRegularExpression>(createRegexp<like, similar_to, no_capture, case_insensitive>(key));
            bucket = {std::move(key), std::move(compiled)};
        }
        else
        {
            if (pattern != bucket.pattern)
            {
                /// replace existing entry
                ++misses;
                String key(pattern);
                auto compiled = std::make_unique<OptimizedRegularExpression>(createRegexp<like, similar_to, no_capture, case_insensitive>(key));
                bucket = {std::move(key), std::move(compiled)};
            }
            else
                ++hits;
        }

        return *bucket.regexp;
    }

Note [[unlikely]] on the miss branch, and that hits/misses are counted in plain members and flushed in the destructor:

cpp 
// src/Functions/Regexps.h:100
    ~LocalCacheTable()
    {
        if (hits)
            ProfileEvents::increment(ProfileEvents::RegexpLocalCacheHit, hits);
        if (misses)
            ProfileEvents::increment(ProfileEvents::RegexpLocalCacheMiss, misses);
    }

“Flushed once, in the destructor: per-lookup increments would contend on counters shared by all threads of the query.” The counters are per-instance (per-thread), so no contention; they are reported to ProfileEvents once when the cache dies.

Trade-offs

The tiering buys:

  • Common patterns never touch a regexp engine. match(s, 'foo') is a substring search. match(s, '^/admin') is a memcmp.
  • No RE2 object for trivial patterns. Not just a faster match — no compilation at all, so no allocation, no compile time.
  • A sound pre-filter for general patterns. The literal analysis is exact, so the pre-filter never rejects a subject that would have matched.
  • A JIT tier with a linearity guarantee. The JIT only compiles patterns that match in a single greedy pass, so it can never be slower than RE2 in the pathological case.
  • Bounded state. The seen-counter map is cleared wholesale when it reaches 10 000 entries; the local cache is a fixed 1000 buckets.

It costs:

  • A second regexp dialect to maintain. The analyser’s job is to reproduce RE2’s exact interpretation of every construct, and every comment in OptimizedRegularExpression.cpp is about a case where it once did not. The [[:alpha:]] handling, the []a] handling, the \Q...\E handling, the % — each is a bug that was found.
  • A third dialect for the JIT. RegexpProgram’s parser is a separate conservative parser with its own set of bail-outs, and it has to agree with RE2 for the subset it accepts. The caseInsensitiveTouchesNonAsciiFold check exists because it once did not.
  • A heuristic with a domain bias. The "://" / "http://" / "www" / "Windows " exclusion list is a hard-coded assumption about web analytics workloads. It is not wrong — those substrings are rarely discriminating — but it is a heuristic, and it is hard-coded.
  • Three code paths to test. Trivial, anchored, general-with-prefilter, general-with-JIT: a change to any of them has to preserve the agreement between all four. The verifyMatchAgainstRE2 debug check exists for exactly this reason.

The lesson

The interesting idea is that a regexp library is not one thing but a cascade, and most users only ever need the first tier. ClickHouse’s OptimizedRegularExpression is that cascade, and the design principle behind every tier is the same: compute a sound over-approximation of the match set cheaply, and only escalate when the cheap test fails.

The second idea worth copying is the conservative parser discipline. The JIT’s parser bails out on anything it does not fully understand, and the governing rule is written down as “false negatives are harmless, false positives are bugs”. A fast path that is wrong sometimes is worse than no fast path, because the user cannot tell when it applies.

And the third is the willingness to encode domain knowledge — the "www" exclusion list — in a place where it is one line and obvious, rather than burying it in a general-purpose engine.

ClickhouseInternalsRegexpPerformanceJit