Horton

Re: Some regular-expression performance hacking

Joel Jacobson <joel@compiler.org>

View thread View on postgr.es
From: "Joel Jacobson" <joel@compiler.org>
To: "Tom Lane" <tgl@sss.pgh.pa.us>
Cc: pgsql-hackers@lists.postgresql.org
Date: 2021-02-18T20:54:38Z
Lists: pgsql-hackers 
On Thu, Feb 18, 2021, at 21:44, Tom Lane wrote:
>Hmm ... I might be misunderstanding, but I think our engine already
>does a version of this.  See the discussion of "colors" in
>src/backend/regex/README.

Thanks, I will read it with great interest.

>Maybe.  In practice the actual scanning tends to be tracking more than one
>possible NFA state in parallel, so I'm not sure how often we could expect
>to be able to use this idea.  That is, even if we know that state X can
>only succeed by following an arc to Y and then another to Z, we might
>also be interested in what happens if the NFA is in state Q at this point;
>and it seems unlikely that Q would have exactly the same two following
>arc colors.

Right. Actually I don't have a clear idea on how it could be implemented in an NFA engine.

>I do have some ideas about possible future optimizations, and one reason
>I'm grateful for this large set of real regexes is that it can provide a
>concrete basis for deciding that particular optimizations are or are not
>worth pursuing.  So thanks again for collecting it!

My pleasure. Thanks for using it!

/Joel

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