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
Date: Thu, 18 Feb 2021 13:10:47 -0500
Message-ID: <2840118.1613671847@sss.pgh.pa.us> (raw)
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>
"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 version 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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tgl@sss.pgh.pa.us, joel@compiler.org, pgsql-hackers@lists.postgresql.org
Subject: Re: Some regular-expression performance hacking
In-Reply-To: <2840118.1613671847@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox