Horton

Re: Some regular-expression performance hacking

Tom Lane <tgl@sss.pgh.pa.us>

View thread View on postgr.es
From: Tom Lane <tgl@sss.pgh.pa.us>
To: "Joel Jacobson" <joel@compiler.org>
Cc: pgsql-hackers@lists.postgresql.org
Date: 2021-02-14T16:45:40Z
Lists: pgsql-hackers 
"Joel Jacobson" <joel@compiler.org> writes:
> I've successfully tested both patches against the 1.5M regexes-in-the-wild dataset.
> Out of the 1489489 (pattern, text string) pairs tested,
> there was only one single deviation:
> This 100577 bytes big regex (pattern_id = 207811)...
> ...
> ...previously raised...
>     error invalid regular expression: regular expression is too complex
> ...but now goes through:

> Nice. The patched regex engine is apparently capable of handling even more complex regexes than before.

Yeah.  There are various limitations that can lead to REG_ETOOBIG, but the
main ones are "too many states" and "too many arcs".  The RAINBOW change
directly reduces the number of arcs and thus makes larger regexes feasible.
I'm sure it's coincidental that the one such example you captured happens
to be fixed by this change, but hey I'll take it.

			regards, tom lane

Commits

  1. Suppress unnecessary regex subre nodes in a couple more cases.

  2. Improve memory management in regex compiler.

  3. Extend a test case a little

  4. Allow complemented character class escapes within regex brackets.

  5. Suppress compiler warning in new regex match-all detection code.

  6. Avoid generating extra subre tree nodes for capturing parentheses.

  7. Convert regex engine's subre tree from binary to N-ary style.

  8. Fix regex engine to suppress useless concatenation sub-REs.

  9. Recognize "match-all" NFAs within the regex engine.

  10. Invent "rainbow" arcs within the regex engine.

  11. Make some minor improvements in the regex code.

  12. Display the time when the process started waiting for the lock, in pg_locks, take 2

  13. README/C-comment: document GiST's NSN value

  14. doc: Mention NO DEPENDS ON EXTENSION in its supported ALTER commands