From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
---|---|
To: | pgsql-committers(at)lists(dot)postgresql(dot)org |
Subject: | pgsql: Fix performance issue in new regex match-all detection code. |
Date: | 2021-05-03 15:42:50 |
Message-ID: | E1ldaig-0008O7-SY@gemulon.postgresql.org |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-committers |
Fix performance issue in new regex match-all detection code.
Commit 824bf7190 introduced a new search of the NFAs generated by
regex compilation. I failed to think hard about the performance
characteristics of that search, with the predictable outcome
that it's bad: weird regexes can trigger exponential search time.
Worse, there's no check-for-interrupt in that code, so you can't
even cancel the query if this happens.
Fix by introducing memo-ization of the search results, so that any one
NFA state need be examined in detail just once. This potentially uses
a lot of memory, but we can bound the memory usage by putting a limit
on the number of states for which we'll try to prove match-all-ness.
That is sane because we already have a limit (DUPINF) on the maximum
finite string length that a matchall regex can match; and patterns
that involve much more than DUPINF states would probably exceed that
limit anyway.
Also, rearrange the logic so that we check the basic is-the-graph-
all-RAINBOW-arcs property before we start the recursive search to
determine path lengths. This will ensure that we fall out quickly
whenever the NFA couldn't possibly be matchall.
Also stick in a check-for-interrupt, just in case these measures
don't completely eliminate the risk of slowness.
Discussion: https://postgr.es/m/3483895.1619898362@sss.pgh.pa.us
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/f68970e33f4dc48094c24c78c452ad730ae9ae12
Modified Files
--------------
src/backend/regex/regc_nfa.c | 481 ++++++++++++++++++++++++------------
src/backend/regex/regcomp.c | 3 +-
src/test/regress/expected/regex.out | 37 +++
src/test/regress/sql/regex.sql | 8 +
4 files changed, 366 insertions(+), 163 deletions(-)
From | Date | Subject | |
---|---|---|---|
Next Message | Robert Haas | 2021-05-03 16:32:55 | pgsql: amcheck: Improve some confusing reports about TOAST problems. |
Previous Message | Peter Eisentraut | 2021-05-03 10:18:50 | pgsql: Prevent lwlock dtrace probes from unnecessary work |