Re: Pathological regexp match

Michael Glaesemann wrote:
>
> On Jan 28, 2010, at 21:59 , Alvaro Herrera wrote:
>
> >Hi Michael,
> >
> >Michael Glaesemann wrote:
> >>We came across a regexp that takes very much longer than expected.
> >>
> >>PostgreSQL 8.4.1 on x86_64-unknown-linux-gnu, compiled by GCC
> >>gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-44), 64-bit
> >>
> >>SELECT 'ooo...' ~ $r$Z(Q)[^Q]*A.*?(\1)$r$; -- omitted for email
> >>brevity
> >
> >The ? after .* is pointless.
>
> Interesting. I would expect that *? would be the non-greedy version
> of *, meaning match up to the first \1 (in this case the first Q
> following A), rather than as much as possible.

Huh, you are right, *? is the non-greedy version. I keep forgetting
those. Note that they only work if you have regex_flavor set to
advanced, though (which is the default).

> However, as you point out, Postgres doesn't appear to take this into
> account:
>
> postgres=# select regexp_replace('oooZQoooAoooQooQooQooo', $r$(Z(Q)
> [^Q]*A.*(\2))$r$, $s$X$s$);
> regexp_replace
> ----------------
> oooXooo
> (1 row)
>
> postgres=# select regexp_replace('oooZQoooAoooQooQooQooo', $r$(Z(Q)
> [^Q]*A.*?(\2))$r$, $s$X$s$);
> regexp_replace
> ----------------
> oooXooo
> (1 row)

Hmm, that's strange ...

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support