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: <d8899c66-5492-43e9-8eff-a07d1d593ad0@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>
 <2840118.1613671847@sss.pgh.pa.us>
 <d8899c66-5492-43e9-8eff-a07d1d593ad0@www.fastmail.com>
Comments: In-reply-to "Joel Jacobson" <joel@compiler.org>
	message dated "Thu, 18 Feb 2021 20:58:07 +0100"
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <2872013.1613681087.1@sss.pgh.pa.us>
Content-Transfer-Encoding: quoted-printable
Date: Thu, 18 Feb 2021 15:44:47 -0500
Message-ID: <2872014.1613681087@sss.pgh.pa.us>
Precedence: bulk

"Joel Jacobson" <joel@compiler.org> writes:
> Let's see if I can explain the idea:
> One of the problems with representing regexes with large bracket range e=
xpressions, like [a-z],
> is you get an explosion of edges, if the model can only represent state =
transitions for single characters.
> If we could instead let a single edge (for a state transition) represent=
 a set of characters,
> or normally even more efficiently, a set of range of characters, then we=
 could reduce the
> number of edges we need to represent the graph.
> The naive approach to just use the ranges as-is doesn't work.
> Instead, the graph must first be created with single-character edges.
> It is then examined what ranges can be constructed in a way that no sing=
le range
> overlaps any other range, so that every range can be seen as a character=
 in an alphabet.

Hmm ... I might be misunderstanding, but I think our engine already
does a version of this.  See the discussion of "colors" in
src/backend/regex/README.

> Another optimization I've come up with (or probably re-invented because =
it feels quite obvious),
> is to read more than one character, when knowing for sure multiple chara=
cters-in-a-row
> are expected, by concatenating edges having only one parent and one chil=
d.

Maybe.  In practice the actual scanning tends to be tracking more than one
possible NFA state in parallel, so I'm not sure how often we could expect
to be able to use this idea.  That is, even if we know that state X can
only succeed by following an arc to Y and then another to Z, we might
also be interested in what happens if the NFA is in state Q at this point;
and it seems unlikely that Q would have exactly the same two following
arc colors.

I do have some ideas about possible future optimizations, and one reason
I'm grateful for this large set of real regexes is that it can provide a
concrete basis for deciding that particular optimizations are or are not
worth pursuing.  So thanks again for collecting it!

			regards, tom lane