Horton

Thread

Commits

  1. Improve performance of regular expression back-references.

  2. Fix semantics of regular expression back-references.

  3. Allow condition variables to be used in interrupt code.

  1. Regex back-reference semantics and performance

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-03-01T00:53:49Z

    I noticed that some of the slowest cases in Joel's regex test corpus
had issues with back-reference matching, and along the way to fixing
that discovered what seems to me to be a bug in the engine's handling
of back-references.  To wit, what should happen if a back-reference
is to a subexpression that contains constraints?  A simple example is

	SELECT regexp_match('foof', '(^f)o*\1');

To my mind, the back reference is only chartered to match the literal
characters matched by the referenced subexpression.  Here, since that
expression matches "f", the backref should too, and thus we should get
a match to "foof".  Perl gives that answer, anyway; but our existing
code says there's no match.  That's because it effectively copies the
constraints within the referenced subexpression, in addition to making
the data comparison.  The "^" can't match where the second "f" is, so
we lose.

0001 attached fixes this by stripping constraint arcs out of the NFA
that's applied to the backref subre tree node.

Now, as to the performance issue ... if you load up the data in
"trouble.sql" attached, and do

	SELECT regexp_matches(subject, pattern, 'g') FROM trouble;

you'll be waiting a good long time, even with our recent improvements.
(Up to now I hadn't tried the 'g' flag with Joel's test cases, so
I hadn't noticed what a problem this particular example has got.)
The reason for the issue is that the pattern is

	(["'`])(?:\\\1|.)*?\1

and the subject string has a mix of " and ' quote characters.  As
currently implemented, our engine tries to resolve the match at
any substring ending in either " or ', since the NFA created for
the backref can match either.  That leads to O(N^2) time wasted
trying to verify wrong matches.

I realized that this could be improved by replacing the NFA/DFA
match step for a backref node with a string literal match, if the
backreference match string is already known at the time we try
to apply the NFA/DFA.  That's not a panacea, but it helps in most
simple cases including this one.  The way to visualize what is
happening is that we have a tree of binary concatenation nodes:

	          concat
	         /      \
	  capture        concat
	                /      \
	     other stuff        backref

Each concat node performs fast NFA/DFA checks on both its children
before recursing to the children to make slow exact checks.  When we
recurse to the capture node, it records the actual match substring,
so now we know whether the capture is " or '.  Then, when we recurse
to the lower concat node, the capture is available while it makes
NFA/DFA checks for its two children; so it will never mistakenly
guess that its second child matches a substring it doesn't, and
thus it won't try to do exact checking of the "other stuff" on a
match that's bound to fail later.

So this works as long as the tree of concat nodes is right-deep,
which fortunately is the normal case.  It won't help if we have
a left-deep tree:

	               concat
	              /      \
	        concat        backref
	       /      \
	capture        other stuff

because the upper concat node will do its NFA/DFA check on the backref
node before recursing to its left child, where the capture will occur.
But to get that tree, you have to have written extra parentheses:

	((capture)otherstuff)\2

I don't see a way to improve that situation, unless perhaps with
massive rejiggering of the regex execution engine.  But 0002 attached
does help a lot in the simple case.

(BTW, the connection between 0001 and 0002 is that if we want to keep
the existing semantics that a backref enforces constraints, 0002
doesn't work, since it won't do that.)

			regards, tom lane

  2. Re: Regex back-reference semantics and performance

    Joel Jacobson <joel@compiler.org> — 2021-03-01T11:13:56Z

    On Mon, Mar 1, 2021, at 01:53, Tom Lane wrote:
>0001-fix-backref-semantics.patch
>0002-backref-performance-hack.patch

I've successfully tested both patches.

On HEAD the trouble-query took forever, I cancelled it after 23 minutes.

HEAD (f5a5773a9dc4185414fe538525e20d8512c2ba35):
SELECT regexp_matches(subject, pattern, 'g') FROM trouble;
^CCancel request sent
ERROR:  canceling statement due to user request
Time: 1387398.764 ms (23:07.399)

HEAD + 0001 + 0002:
SELECT regexp_matches(subject, pattern, 'g') FROM trouble;
Time: 24.943 ms
Time: 22.217 ms
Time: 20.250 ms

Very nice!

I also verified the patches gave the same result for the performance_test:

SELECT
  is_match <> (subject ~ pattern) AS is_match_diff,
  captured IS DISTINCT FROM regexp_match(subject, pattern, flags) AS captured_diff,
  COUNT(*)
FROM performance_test
GROUP BY 1,2
ORDER BY 1,2
;

is_match_diff | captured_diff |  count
---------------+---------------+---------
f             | f             | 3360068
(1 row)

No notable timing differences:

HEAD (f5a5773a9dc4185414fe538525e20d8512c2ba35)
Time: 97016.668 ms (01:37.017)
Time: 96945.567 ms (01:36.946)
Time: 95261.263 ms (01:35.261)

HEAD + 0001:
Time: 97165.302 ms (01:37.165)
Time: 96327.836 ms (01:36.328)
Time: 96295.643 ms (01:36.296)

HEAD + 0001 + 0002:
Time: 96447.527 ms (01:36.448)
Time: 94262.288 ms (01:34.262)
Time: 95331.483 ms (01:35.331)

/Joel

  3. Re: Regex back-reference semantics and performance

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-03-01T20:22:08Z

    "Joel Jacobson" <joel@compiler.org> writes:
> On Mon, Mar 1, 2021, at 01:53, Tom Lane wrote:
>> 0001-fix-backref-semantics.patch
>> 0002-backref-performance-hack.patch

> I've successfully tested both patches.

Again, thanks for testing!

> On HEAD the trouble-query took forever, I cancelled it after 23 minutes.

Yeah, I have not had the patience to run it to completion either.

> No notable timing differences:

I'm seeing a win of maybe 1% across the entire corpus, which isn't
much but it's something.  It's not too surprising that this backref
issue is seldom hit, or we'd have had more complaints about it.

BTW, I had what seemed like a great idea to improve the situation in
the left-deep-tree case I talked about: we could remember the places
where we'd had to use the NFA to check a backreference subre, and
then at the point where we capture the reference string, recheck any
previous approximate answers, and fail the capture node's match when
any previous backref doesn't match.  Turns out this only mostly works.
In corner cases where the match is ambiguous, it can change the
results from what we got before, which I don't think is acceptable.
Basically, that allows the backref node to have action-at-a-distance
effects on where the earlier concat node divides a substring, which
changes the behavior.

So it seems this is about the best we can do for now.  I'll wait
a little longer to see if anyone complains about the proposed
semantics change, though.

			regards, tom lane