Horton

Re: Some regular-expression performance hacking

Noah Misch <noah@leadboat.com>

View thread View on postgr.es
From: Noah Misch <noah@leadboat.com>
To: Joel Jacobson <joel@compiler.org>
Cc: Tom Lane <tgl@sss.pgh.pa.us>, pgsql-hackers@lists.postgresql.org
Date: 2021-03-06T18:09:25Z
Lists: pgsql-hackers 
On Sat, Feb 13, 2021 at 06:19:34PM +0100, Joel Jacobson wrote:
> To test the correctness of the patches,
> I thought it would be nice with some real-life regexes,
> and just as important, some real-life text strings,
> to which the real-life regexes are applied to.
> 
> I therefore patched Chromium's v8 regexes engine,
> to log the actual regexes that get compiled when
> visiting websites, and also the text strings that
> are the regexes are applied to during run-time
> when the regexes are executed.
> 
> I logged the regex and text strings as base64 encoded
> strings to STDOUT, to make it easy to grep out the data,
> so it could be imported into PostgreSQL for analytics.
> 
> In total, I scraped the first-page of some ~50k websites,
> which produced 45M test rows to import,
> which when GROUP BY pattern and flags was reduced
> down to 235k different regex patterns,
> and 1.5M different text string subjects.

It's great to see this kind of testing.  Thanks for doing it.

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