forked frompostgres/postgres
- Notifications
You must be signed in to change notification settings - Fork6
Commitf68970e
committed
Fix performance issue in new regex match-all detection code.
Commit824bf71 introduced a new search of the NFAs generated byregex compilation. I failed to think hard about the performancecharacteristics of that search, with the predictable outcomethat it's bad: weird regexes can trigger exponential search time.Worse, there's no check-for-interrupt in that code, so you can'teven cancel the query if this happens.Fix by introducing memo-ization of the search results, so that any oneNFA state need be examined in detail just once. This potentially usesa lot of memory, but we can bound the memory usage by putting a limiton 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 maximumfinite string length that a matchall regex can match; and patternsthat involve much more than DUPINF states would probably exceed thatlimit anyway.Also, rearrange the logic so that we check the basic is-the-graph-all-RAINBOW-arcs property before we start the recursive search todetermine path lengths. This will ensure that we fall out quicklywhenever the NFA couldn't possibly be matchall.Also stick in a check-for-interrupt, just in case these measuresdon't completely eliminate the risk of slowness.Discussion:https://postgr.es/m/3483895.1619898362@sss.pgh.pa.us1 parentb94409a commitf68970e
File tree
4 files changed
+366
-163
lines changed- src
- backend/regex
- test/regress
- expected
- sql
4 files changed
+366
-163
lines changed0 commit comments
Comments
(0)