Match with a regular expression

Status

The DuckDB step

Variants

Test for a pattern match

Test whether, or count how often, a value matches a regular expression or LIKE pattern.

What other tools call it

Meridian's classification; an independent blind rating agreed on 86.2% of 312 rows (exact class, version 2).

Background

When to use it

In DuckDB, regexp_matches returns true if the string merely contains the pattern, unless the tokens ^ and $ anchor the pattern to the start and end of the string.^[2] In DuckDB, regexp_full_match returns true only if the entire string matches the regular expression.^[2] When a regular expression is used to validate a column, anchor it or use a full-match test, so that a value which merely contains a valid fragment is not passed as valid. (Meridian's view)

A regular expression denial of service (ReDoS) is an attack that supplies a regular expression or an input that takes a long time to evaluate, exploiting the super-linear worst-case complexity of many implementations.^[3] In PostgreSQL, regular expressions can be contrived that take arbitrary amounts of time and memory to process, so patterns from hostile sources call for wariness and, if they must be accepted, a statement timeout.^[4] DuckDB uses the RE2 library as its regular expression engine.^[2] RE2 was designed to handle regular expressions from untrusted users without risk, and one of its primary guarantees is that match time is linear in the length of the input string.^[5] Where a pattern comes from a user rather than from the analyst writing the query, prefer an engine with a linear-time guarantee, or set a time limit. (Meridian's view)

Different syntaxes for writing regular expressions have existed since the 1980s, one of them the widely used Perl syntax.^[1] Starting in 1997, Philip Hazel developed Perl Compatible Regular Expressions (PCRE), which attempts to closely mimic Perl's regex functionality.^[1] RE2's syntax is, roughly speaking, a subset of that accepted by PCRE, with various caveats.^[6] PostgreSQL's regular expressions are implemented using a software package written by Henry Spencer.^[4] RE2 does not support constructs for which only backtracking solutions are known to exist, so backreferences and look-around assertions are not supported.^[5] Test a pattern copied from another tool in the engine that will run it, rather than assuming the dialects agree. (Meridian's view)

In Python and some other implementations, such as Java, the quantifiers *, + and ? are greedy by default because they match as many characters as possible.^[1] In RE2, x+ matches one or more x and prefers more, while x+? matches one or more x and prefers fewer.^[6]

The method

Regular expressions originated in 1951, when mathematician Stephen Cole Kleene described regular languages using his mathematical notation called regular events.^[1] Ken Thompson built Kleene's notation into the editor QED as a means to match patterns in text files, and later added the capability to the Unix editor ed, which eventually led to grep's use of regular expressions.^[1] Thompson's construction algorithm builds a nondeterministic finite automaton (NFA) from a regular expression, and Thompson first described a way of translating regular expressions into NFAs in a 1968 paper.^[1][7]

There are at least three different algorithms that decide whether and how a given regular expression matches a string.^[1] A deterministic finite automaton (DFA) built explicitly from a regular expression of size m costs O(2^m) in time and memory to construct, but runs on a string of size n in O(n) time.^[1] Simulating the NFA directly keeps the DFA implicit and avoids the exponential construction cost, but the running cost rises to O(mn).^[1] Matching by backtracking can take exponential time, which simple implementations show on expressions like (a|aa)*b that contain both alternation and unbounded quantification.^[1] Any implementation that allows backreferences, or implements the various extensions introduced by Perl, must include some kind of backtracking.^[1] A backreference like \1 matches the string matched by a previous parenthesised expression, so (cat|dog)\1 matches catcat and dogdog but not catdog nor dogcat.^[7] RE2 evaluates all alternatives in parallel, where a backtracking engine tests each alternative sequentially.^[5]

Compared with the alternatives

In PostgreSQL, a LIKE pattern always covers the entire string, whereas a regular expression may match anywhere within a string unless it is explicitly anchored to the beginning or end.^[4] In PostgreSQL, the SIMILAR TO operator interprets its pattern using the SQL standard's definition of a regular expression.^[4] In PostgreSQL, SIMILAR TO, like LIKE, succeeds only if its pattern matches the entire string.^[4] In PostgreSQL, LIKE searches, being much simpler than SIMILAR TO and regular expressions, are safer to use with possibly hostile pattern sources.^[4] Before regular expressions, many search languages allowed simple wildcards such as * for any sequence of characters and ? for a single character, relics of which survive in glob syntax for filenames and in the SQL LIKE operator.^[1] Where a fixed prefix, a fixed suffix or a simple wildcard says what is needed, LIKE is the plainer choice; a regular expression earns its place when the pattern needs alternation, repetition or groups. (Meridian's view)

Sources

1. [1]Regular expression - Wikipediasecondary source
2. [2]Regular Expressions – DuckDBdocumentation
3. [3]ReDoS - Wikipediasecondary source
4. [4]PostgreSQL: Documentation: 18: 9.7. Pattern Matchingdocumentation
5. [5]GitHub - google/re2: RE2 is a fast, safe, thread-friendly alternative to backtracking regular expression engines like those used in PCRE, Perl, and Python. It is a C++ library. · GitHubdocumentation
6. [6]Syntax · google/re2 Wiki · GitHubdocumentation
7. [7]Regular Expression Matching Can Be Simple And Fastsecondary source

Used in