Re: Death by regexp_replace

Kevin Grittner <kgrittn(at)gmail(dot)com> writes:
> On Fri, Jan 15, 2016 at 9:33 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> (FWIW, I think you probably wanted ,+ not ,* in the regex, else there's
>> practically no constraint there, leading to having to consider O(N^2)
>> or more possibilities.)

> On master (commit cf7dfbf2) it responds to pg_cancel_backend(),
> but it seems to be in an endless loop until you do that.

A bit of further experimentation suggests the runtime growth is actually
more like O(2^N). It will terminate in a reasonable amount of time if the
input string is about half as long as the given example.

The problem is that so far as the DFA engine is concerned, the pattern
substring '(,*\1)+' can match almost anything at all, because it's
equivalent to '(,*[^,]+)+' which is easily seen to match any string
whatever that's got at least one non-comma. So, for each possible match
to the substring '([^,]+)', of which there are lots, it has to consider
every possible way of breaking up all the rest of the string into one or
more substrings. The vast majority of those ways will fail when the
backref match is checked, but there's no way to realize it before that.

regards, tom lane