From: Tom Lane <tgl@sss.pgh.pa.us>
To: "Joel Jacobson" <joel@compiler.org>
cc: pgsql-hackers@lists.postgresql.org
Subject: Re: Some regular-expression performance hacking
In-reply-to: <12e6381c-adc1-4711-a619-864fb8df969c@www.fastmail.com>
References: <1340281.1613018383@sss.pgh.pa.us>
 <85140bfb-516c-449b-8a03-7930abb42b88@www.fastmail.com>
 <1813969.1613250697@sss.pgh.pa.us>
 <913516b8-c3d7-4dea-bf60-d735cf4673f1@www.fastmail.com>
 <2155152.1613358697@sss.pgh.pa.us>
 <99f6cbe0-6e58-4e41-add0-977271a5cf84@www.fastmail.com>
 <2752386.1613595636@sss.pgh.pa.us>
 <5deabab3-a335-4b57-a046-8a9ad8f2f142@www.fastmail.com>
 <12e6381c-adc1-4711-a619-864fb8df969c@www.fastmail.com>
Comments: In-reply-to "Joel Jacobson" <joel@compiler.org>
	message dated "Thu, 18 Feb 2021 12:04:55 +0100"
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <2840117.1613671847.1@sss.pgh.pa.us>
Content-Transfer-Encoding: quoted-printable
Date: Thu, 18 Feb 2021 13:10:47 -0500
Message-ID: <2840118.1613671847@sss.pgh.pa.us>
Precedence: bulk

"Joel Jacobson" <joel@compiler.org> writes:
>> I've produced a new dataset which now also includes the regex flags (if
>> any) used for each subject applied to a pattern.

Again, thanks for collecting this data!  I'm a little confused about
how you produced the results in the "tests" table, though.  It sort
of looks like you tried to feed the Javascript flags to regexp_match(),
which unsurprisingly doesn't work all that well.  Even discounting
that, I'm not getting quite the same results, and I don't understand
why not.  So how was that made from the raw "patterns" and "subjects"
tables?

> PostgreSQL 13.2 on x86_64-apple-darwin19.6.0, compiled by Apple clang ve=
rsion 11.0.3 (clang-1103.0.32.62), 64-bit
> Time: 758514.703 ms (12:38.515)
> Time: 755883.600 ms (12:35.884)
> Time: 746522.107 ms (12:26.522)
> =

> PostgreSQL 14devel on x86_64-apple-darwin20.3.0, compiled by Apple clang=
 version 12.0.0 (clang-1200.0.32.29), 64-bit
> HEAD (4e703d671)
> Time: 519620.646 ms (08:39.621)
> Time: 518998.366 ms (08:38.998)
> Time: 519696.129 ms (08:39.696)

Hmmm ... we haven't yet committed any performance-relevant changes to the
regex code, so it can't take any credit for this improvement from 13.2 to
HEAD.  I speculate that this is due to some change in our parallelism
stuff (since I observe that this query is producing a parallelized hash
plan).  Still, the next drop to circa 2:21 runtime is impressive enough
by itself.

> Heh, what a funny coincidence:
> The regex I used to shrink the very-long-pattern,
> actually happens to run a lot faster with the patches.

Yeah, that just happens to be a poster child for the MATCHALL idea:

> EXPLAIN ANALYZE SELECT regexp_matches(repeat('a',100000),'^(.{1,80})(.*?=
)(.{1,80})$');

Each of the parenthesized subexpressions of the RE is successfully
recognized as being MATCHALL, with length range 1..80 for two of them and
0..infinity for the middle one.  That means the engine doesn't have to
physically scan the text to determine whether a possible division point
satisfies the sub-regexp; and that means we can find the correct division
points in O(N) not O(N^2) time.

			regards, tom lane