8000 Fix performance issue in new regex match-all detection code. · Giperboloid/postgres@f68970e · GitHub
[go: up one dir, main page]
Skip to content

Commit f68970e

Browse files
tglsfdctglsfdc
committed
Fix performance issue in new regex match-all detection code.
Commit 824bf71 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
1 parent b94409a commit f68970e

File tree

4 files changed

+366
-163
lines changed

4 files changed

+366
-163
lines changed

0 commit comments

Comments
 (0)
0