]> git.ipfire.org Git - thirdparty/postgresql.git/commit
Improve performance of fixempties() pass in regular-expression compiler.
authorTom Lane <tgl@sss.pgh.pa.us>
Fri, 16 Oct 2015 18:58:10 +0000 (14:58 -0400)
committerTom Lane <tgl@sss.pgh.pa.us>
Fri, 16 Oct 2015 19:56:00 +0000 (15:56 -0400)
commite9cf3dc30a4ed82f2c284240841678db15491669
tree6597dbe0a272d1aad392cb44d6247b65081b83af
parentcff9e0659e8b79d4e075d30f04dac5a5587b8ac2
Improve performance of fixempties() pass in regular-expression compiler.

The previous coding took something like O(N^4) time to fully process a
chain of N EMPTY arcs.  We can't really do much better than O(N^2) because
we have to insert about that many arcs, but we can do lots better than
what's there now.  The win comes partly from using mergeins() to amortize
de-duplication of arcs across multiple source states, and partly from
exploiting knowledge of the ordering of arcs for each state to avoid
looking at arcs we don't need to consider during the scan.  We do have
to be a bit careful of the possible reordering of arcs introduced by
the sort-merge coding of the previous commit, but that's not hard to
deal with.

Back-patch to all supported branches.
src/backend/regex/regc_nfa.c
src/backend/regex/regcomp.c