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. Branch ------ REL9_2_STABLE Details ------- http://git.postgresql.org/pg/commitdiff/18b032f8ff156fc482202cddb46b4b457c55cf11 Modified Files -------------- src/backend/regex/regc_nfa.c | 249 +++++++++++++++++++++--------------------- src/backend/regex/regcomp.c | 6 +- 2 files changed, 128 insertions(+), 127 deletions(-) -- Sent via pgsql-committers mailing list ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-committers
