Re: Regex performance regression induced by match-all code

On Sat, May 1, 2021, at 21:46, Tom Lane wrote:
> I found a nasty performance problem in commit 824bf7190: given the
> right sort of regex, checkmatchall() takes an unreasonable amount
> of time.

Nice catch.

> fix-exponential-cost-of-checkmatchall-1.patch

I've successfully tested the patch on the regex corpus:

SELECT
is_match <> (subject ~ pattern),
captured IS DISTINCT FROM regexp_match(subject, pattern, flags),
COUNT(*)
FROM performance_test
GROUP BY 1,2
ORDER BY 1,2;
?column? | ?column? | count
----------+----------+---------
f | f | 3253889
(1 row)

HEAD (651d005e76bc0b9542615f609b4d0d946035dc58)
Time: 94096.020 ms (01:34.096)
Time: 93102.287 ms (01:33.102)
Time: 93333.746 ms (01:33.334)

fix-exponential-cost-of-checkmatchall-1.patch
Time: 95247.529 ms (01:35.248)
Time: 92617.502 ms (01:32.618)
Time: 93259.700 ms (01:33.260)

I've also tested the problematic type of regexes:

HEAD (651d005e76bc0b9542615f609b4d0d946035dc58)
SELECT regexp_matches('', '(.|){20}','');
Time: 61.613 ms
SELECT regexp_matches('', '(.|){25}','');
Time: 1928.674 ms (00:01.929)
SELECT regexp_matches('', '(.|){27}','');
Time: 7789.601 ms (00:07.790)

fix-exponential-cost-of-checkmatchall-1.patch
SELECT regexp_matches('', '(.|){20}','');
Time: 0.965 ms
SELECT regexp_matches('', '(.|){25}','');
Time: 0.586 ms
SELECT regexp_matches('', '(.|){27}','');
Time: 0.788 ms

Nice improvement, thanks.

/Joel