Re: Uninterruptable regexp_replace in 9.3.1 ?

On Feb21, 2014, at 16:46 , Craig Ringer <craig(at)2ndquadrant(dot)com> wrote:
> The real question IMO is why it's taking so long. It looks like
> cfindloop(...) is being called multiple times, with each call taking a
> couple of seconds.

Yeah, I wondered about this too. I've shortened the example a bit - here
are a few observations

postgres=# select regexp_matches(' $a$b$c$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 33.026 ms

postgres=# select regexp_matches(' $a$b$c$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 60.594 ms

postgres=# select regexp_matches(' $a$b$c$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 114.410 ms

postgres=# select regexp_matches(' $a$b$c$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 227.467 ms

postgres=# select regexp_matches(' $a$b$c$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 452.739 ms

postgres=# select regexp_matches(' $a$b$c$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 943.098 ms

postgres=# select regexp_matches(' $a$b$c$d$e$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 200.795 ms

postgres=# select regexp_matches(' $a$b$c$d$e$f$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 298.264 ms

postgres=# select regexp_matches(' $a$b$c$d$e$f$g$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 444.219 ms

postgres=# select regexp_matches(' $a$b$c$d$e$f$g$h$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 696.137 ms

postgres=# select regexp_matches(' $a$b$c$d$e$f$g$h$i$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 974.502 ms

postgres=# select regexp_matches(' $a$b$c$d$e$f$g$h$i$j$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 1369.703 ms

postgres=# select regexp_matches(' $a$b$c$d$e$f$g$h$i$j$',
$REG$((?:[^'"$;]+|"[^"]*"|'(?:[^']*|'')*'|(\$[^$]*\$).*\2)+)$REG$, 'g');
Time: 2747.766 ms

In other words, the observes runtime is roughly 2^i * 1.5^j for inputs
consiting of i leading spaces (any character will probably do) followed
by j substring of the form $X$ (X is an arbitrary character).

best regards,
Florian Pflug