Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mCpM6-0001HG-Mz for pgsql-hackers@arkaria.postgresql.org; Sun, 08 Aug 2021 20:25:10 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1mCpM5-0003dN-CU for pgsql-hackers@arkaria.postgresql.org; Sun, 08 Aug 2021 20:25:09 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mCpM4-0003dE-SX for pgsql-hackers@lists.postgresql.org; Sun, 08 Aug 2021 20:25:09 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mCpM2-0004Lw-3G for pgsql-hackers@lists.postgresql.org; Sun, 08 Aug 2021 20:25:07 +0000 Received: from sss1.sss.pgh.pa.us (localhost [127.0.0.1]) by sss.pgh.pa.us (8.15.2/8.15.2) with ESMTP id 178KP0xT3224307; Sun, 8 Aug 2021 16:25:00 -0400 From: Tom Lane To: Mark Dilger cc: Andrew Dunstan , PostgreSQL Hackers , Joel Jacobson Subject: Re: Another regexp performance improvement: skip useless paren-captures In-reply-to: References: <2219936.1628115334@sss.pgh.pa.us> <31908a04-f73b-8c5b-ed99-919fd4cd4b54@dunslane.net> <2390507.1628174181@sss.pgh.pa.us> <2BFE7DFD-8537-4B4E-BC4C-2F265A836651@enterprisedb.com> <3173384.1628442278@sss.pgh.pa.us> Comments: In-reply-to Mark Dilger message dated "Sun, 08 Aug 2021 11:22:24 -0700" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0" Content-ID: <3224278.1628454278.0@sss.pgh.pa.us> Date: Sun, 08 Aug 2021 16:25:00 -0400 Message-ID: <3224306.1628454300@sss.pgh.pa.us> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk ------- =_aaaaaaaaaa0 Content-Type: text/plain; charset="us-ascii" Content-ID: <3224278.1628454278.1@sss.pgh.pa.us> Content-Transfer-Encoding: quoted-printable Mark Dilger writes: > Hmm. This changes the behavior when applied against master (c1132aae336= c41cf9d316222e525d8d593c2b5d2): > select regexp_split_to_array('uuuzkodphfbfbfb', '((.))(\1\2)', 'ntw'); > regexp_split_to_array > ----------------------- > - {"",zkodphfbfbfb} > + {uuuzkodphfbfbfb} > (1 row) Ugh. The regex engine is finding the match correctly, but it's failing to tell the caller where it is :-(. I was a little too cute in optimizing the regmatch_t result-vector copying in pg_regexec, and forgot to ensure that the overall match position would be reported. Thanks for the testing! regards, tom lane ------- =_aaaaaaaaaa0 Content-Type: text/x-diff; name="optimize-useless-captures-3.patch"; charset="us-ascii" Content-ID: <3224278.1628454278.2@sss.pgh.pa.us> Content-Description: optimize-useless-captures-3.patch Content-Transfer-Encoding: quoted-printable diff --git a/contrib/pg_trgm/trgm_regexp.c b/contrib/pg_trgm/trgm_regexp.c index bf1dea6352..64816dd370 100644 --- a/contrib/pg_trgm/trgm_regexp.c +++ b/contrib/pg_trgm/trgm_regexp.c @@ -541,9 +541,11 @@ createTrgmNFA(text *text_re, Oid collation, * Stage 1: Compile the regexp into a NFA, using the regexp library. */ #ifdef IGNORECASE - RE_compile(®ex, text_re, REG_ADVANCED | REG_ICASE, collation); + RE_compile(®ex, text_re, + REG_ADVANCED | REG_NOSUB | REG_ICASE, collation); #else - RE_compile(®ex, text_re, REG_ADVANCED, collation); + RE_compile(®ex, text_re, + REG_ADVANCED | REG_NOSUB, collation); #endif = /* diff --git a/src/backend/regex/regc_lex.c b/src/backend/regex/regc_lex.c index 7673dab76f..45727ffa01 100644 --- a/src/backend/regex/regc_lex.c +++ b/src/backend/regex/regc_lex.c @@ -528,10 +528,7 @@ next(struct vars *v) } assert(NOTREACHED); } - if (v->cflags & REG_NOSUB) - RETV('(', 0); /* all parens non-capturing */ - else - RETV('(', 1); + RETV('(', 1); break; case CHR(')'): if (LASTTYPE('(')) diff --git a/src/backend/regex/regcomp.c b/src/backend/regex/regcomp.c index 60a220c57a..ae3a7b6a38 100644 --- a/src/backend/regex/regcomp.c +++ b/src/backend/regex/regcomp.c @@ -65,7 +65,7 @@ static struct subre *subre(struct vars *, int, int, stru= ct state *, struct state static void freesubre(struct vars *, struct subre *); static void freesubreandsiblings(struct vars *, struct subre *); static void freesrnode(struct vars *, struct subre *); -static void optst(struct vars *, struct subre *); +static void removecaptures(struct vars *, struct subre *); static int numst(struct subre *, int); static void markst(struct subre *); static void cleanst(struct vars *); @@ -431,7 +431,8 @@ pg_regcomp(regex_t *re, dumpst(v->tree, debug, 1); } #endif - optst(v, v->tree); + if (v->cflags & REG_NOSUB) + removecaptures(v, v->tree); v->ntree =3D numst(v->tree, 1); markst(v->tree); cleanst(v); @@ -1013,14 +1014,16 @@ parseqatom(struct vars *v, break; case BACKREF: /* the Feature From The Black Lagoon */ INSIST(type !=3D LACON, REG_ESUBREG); - INSIST(v->nextvalue < v->nsubs, REG_ESUBREG); - INSIST(v->subs[v->nextvalue] !=3D NULL, REG_ESUBREG); + subno =3D v->nextvalue; + assert(subno > 0); + INSIST(subno < v->nsubs, REG_ESUBREG); + NOERRN(); + INSIST(v->subs[subno] !=3D NULL, REG_ESUBREG); NOERRN(); - assert(v->nextvalue > 0); atom =3D subre(v, 'b', BACKR, lp, rp); NOERRN(); - subno =3D v->nextvalue; atom->backno =3D subno; + v->subs[subno]->flags |=3D BRUSE; EMPTYARC(lp, rp); /* temporarily, so there's something */ NEXT(); break; @@ -2141,19 +2144,54 @@ freesrnode(struct vars *v, /* might be NULL */ } = /* - * optst - optimize a subRE subtree + * removecaptures - remove unnecessary capture subREs + * + * If the caller said that it doesn't care about subexpression match data= , + * we may delete the "capture" markers on subREs that are not referenced + * by any backrefs, and then simplify anything that's become non-messy. + * Call this only if REG_NOSUB flag is set. */ static void -optst(struct vars *v, - struct subre *t) +removecaptures(struct vars *v, + struct subre *t) { + struct subre *t2; + + assert(t !=3D NULL); + + /* + * If this isn't itself a backref target, clear capno and tentatively + * clear CAP flag. + */ + if (!(t->flags & BRUSE)) + { + t->capno =3D 0; + t->flags &=3D ~CAP; + } + + /* Now recurse to children */ + for (t2 =3D t->child; t2 !=3D NULL; t2 =3D t2->sibling) + { + removecaptures(v, t2); + /* Propagate child CAP flag back up, if it's still set */ + if (t2->flags & CAP) + t->flags |=3D CAP; + } + /* - * DGP (2007-11-13): I assume it was the programmer's intent to eventual= ly - * come back and add code to optimize subRE trees, but the routine coded - * just spends effort traversing the tree and doing nothing. We can do - * nothing with less effort. + * If t now contains neither captures nor backrefs, there's no longer an= y + * need to care where its sub-match boundaries are, so we can reduce it = to + * a simple DFA node. (Note in particular that MIXED child greediness i= s + * not a hindrance here, so we don't use the MESSY() macro.) */ - return; + if ((t->flags & (CAP | BACKR)) =3D=3D 0) + { + if (t->child) + freesubreandsiblings(v, t->child); + t->child =3D NULL; + t->op =3D '=3D'; + t->flags &=3D ~MIXED; + } } = /* @@ -2501,6 +2539,8 @@ stdump(struct subre *t, fprintf(f, " hascapture"); if (t->flags & BACKR) fprintf(f, " hasbackref"); + if (t->flags & BRUSE) + fprintf(f, " isreferenced"); if (!(t->flags & INUSE)) fprintf(f, " UNUSED"); if (t->latype !=3D (char) -1) diff --git a/src/backend/regex/regexec.c b/src/backend/regex/regexec.c index 5b9a087820..c08a224618 100644 --- a/src/backend/regex/regexec.c +++ b/src/backend/regex/regexec.c @@ -213,12 +213,10 @@ pg_regexec(regex_t *re, return REG_NOMATCH; backref =3D (v->g->info & REG_UBACKREF) ? 1 : 0; v->eflags =3D flags; - if (v->g->cflags & REG_NOSUB) - nmatch =3D 0; /* override client */ v->nmatch =3D nmatch; - if (backref) + if (backref && nmatch <=3D v->g->nsub) { - /* need work area */ + /* need larger work area */ if (v->g->nsub + 1 <=3D LOCALMAT) v->pmatch =3D mat; else @@ -229,7 +227,13 @@ pg_regexec(regex_t *re, v->nmatch =3D v->g->nsub + 1; } else + { + /* we can store results directly in caller's array */ v->pmatch =3D pmatch; + /* ensure any extra entries in caller's array are filled with -1 */ + if (nmatch > 0) + zapallsubs(pmatch, nmatch); + } v->details =3D details; v->start =3D (chr *) string; v->search_start =3D (chr *) string + search_start; @@ -290,12 +294,20 @@ pg_regexec(regex_t *re, else st =3D find(v, &v->g->tree->cnfa, &v->g->cmap); = - /* copy (portion of) match vector over if necessary */ - if (st =3D=3D REG_OKAY && v->pmatch !=3D pmatch && nmatch > 0) + /* on success, ensure caller's match vector is filled correctly */ + if (st =3D=3D REG_OKAY && nmatch > 0) { - zapallsubs(pmatch, nmatch); - n =3D (nmatch < v->nmatch) ? nmatch : v->nmatch; - memcpy(VS(pmatch), VS(v->pmatch), n * sizeof(regmatch_t)); + if (v->pmatch !=3D pmatch) + { + /* copy portion of match vector over from (larger) work area */ + assert(nmatch <=3D v->nmatch); + memcpy(VS(pmatch), VS(v->pmatch), nmatch * sizeof(regmatch_t)); + } + if (v->g->cflags & REG_NOSUB) + { + /* don't expose possibly-partial sub-match results to caller */ + zapallsubs(pmatch, nmatch); + } } = /* clean up */ @@ -752,7 +764,6 @@ cdissect(struct vars *v, break; case '(': /* no-op capture node */ assert(t->child !=3D NULL); - assert(t->capno > 0); er =3D cdissect(v, t->child, begin, end); break; default: diff --git a/src/backend/utils/adt/jsonpath_gram.y b/src/backend/utils/adt= /jsonpath_gram.y index de3d97931e..bd5d4488a0 100644 --- a/src/backend/utils/adt/jsonpath_gram.y +++ b/src/backend/utils/adt/jsonpath_gram.y @@ -583,6 +583,14 @@ jspConvertRegexFlags(uint32 xflags) errmsg("XQuery \"x\" flag (expanded regular expressions) is not imp= lemented"))); } = + /* + * We'll never need sub-match details at execution. While + * RE_compile_and_execute would set this flag anyway, force it on here t= o + * ensure that the regex cache entries created by makeItemLikeRegex are + * useful. + */ + cflags |=3D REG_NOSUB; + return cflags; } = diff --git a/src/backend/utils/adt/regexp.c b/src/backend/utils/adt/regexp= .c index 484d4265fd..268cee1cbe 100644 --- a/src/backend/utils/adt/regexp.c +++ b/src/backend/utils/adt/regexp.c @@ -347,6 +347,10 @@ RE_compile_and_execute(text *text_re, char *dat, int = dat_len, { regex_t *re; = + /* Use REG_NOSUB if caller does not want sub-match details */ + if (nmatch < 2) + cflags |=3D REG_NOSUB; + /* Compile RE */ re =3D RE_compile_and_cache(text_re, cflags, collation); = @@ -1412,6 +1416,7 @@ setup_regexp_matches(text *orig_str, text *pattern, = pg_re_flags *re_flags, int orig_len; pg_wchar *wide_str; int wide_len; + int cflags; regex_t *cpattern; regmatch_t *pmatch; int pmatch_len; @@ -1430,7 +1435,10 @@ setup_regexp_matches(text *orig_str, text *pattern,= pg_re_flags *re_flags, wide_len =3D pg_mb2wchar_with_len(VARDATA_ANY(orig_str), wide_str, orig_= len); = /* set up the compiled pattern */ - cpattern =3D RE_compile_and_cache(pattern, re_flags->cflags, collation); + cflags =3D re_flags->cflags; + if (!use_subpatterns) + cflags |=3D REG_NOSUB; + cpattern =3D RE_compile_and_cache(pattern, cflags, collation); = /* do we want to remember subpatterns? */ if (use_subpatterns && cpattern->re_nsub > 0) @@ -1952,7 +1960,7 @@ regexp_fixed_prefix(text *text_re, bool case_insensi= tive, Oid collation, if (case_insensitive) cflags |=3D REG_ICASE; = - re =3D RE_compile_and_cache(text_re, cflags, collation); + re =3D RE_compile_and_cache(text_re, cflags | REG_NOSUB, collation); = /* Examine it to see if there's a fixed prefix */ re_result =3D pg_regprefix(re, &str, &slen); diff --git a/src/include/regex/regex.h b/src/include/regex/regex.h index 2b48a19fb7..0455ae8069 100644 --- a/src/include/regex/regex.h +++ b/src/include/regex/regex.h @@ -106,7 +106,7 @@ typedef struct #define REG_QUOTE 000004 /* no special characters, none */ #define REG_NOSPEC REG_QUOTE /* historical synonym */ #define REG_ICASE 000010 /* ignore case */ -#define REG_NOSUB 000020 /* don't care about subexpressions */ +#define REG_NOSUB 000020 /* caller doesn't need subexpr match data */ #define REG_EXPANDED 000040 /* expanded format, white space & comments */ #define REG_NLSTOP 000100 /* \n doesn't match . or [^ ] */ #define REG_NLANCH 000200 /* ^ matches after \n, $ before */ diff --git a/src/include/regex/regguts.h b/src/include/regex/regguts.h index 8db631c83b..91a52840c4 100644 --- a/src/include/regex/regguts.h +++ b/src/include/regex/regguts.h @@ -477,13 +477,14 @@ struct subre #define MIXED 04 /* mixed preference below */ #define CAP 010 /* capturing parens here or below */ #define BACKR 020 /* back reference here or below */ +#define BRUSE 040 /* is referenced by a back reference */ #define INUSE 0100 /* in use in final tree */ -#define NOPROP 03 /* bits which may not propagate up */ +#define UPPROP (MIXED|CAP|BACKR) /* flags which should propagate up */ #define LMIX(f) ((f)<<2) /* LONGER -> MIXED */ #define SMIX(f) ((f)<<1) /* SHORTER -> MIXED */ -#define UP(f) (((f)&~NOPROP) | (LMIX(f) & SMIX(f) & MIXED)) +#define UP(f) (((f)&UPPROP) | (LMIX(f) & SMIX(f) & MIXED)) #define MESSY(f) ((f)&(MIXED|CAP|BACKR)) -#define PREF(f) ((f)&NOPROP) +#define PREF(f) ((f)&(LONGER|SHORTER)) #define PREF2(f1, f2) ((PREF(f1) !=3D 0) ? PREF(f1) : PREF(f2)) #define COMBINE(f1, f2) (UP((f1)|(f2)) | PREF2(f1, f2)) char latype; /* LATYPE code, if lookaround constraint */ diff --git a/src/test/modules/test_regex/expected/test_regex.out b/src/tes= t/modules/test_regex/expected/test_regex.out index 44da7d2019..5a6cdf47c2 100644 --- a/src/test/modules/test_regex/expected/test_regex.out +++ b/src/test/modules/test_regex/expected/test_regex.out @@ -146,12 +146,12 @@ select * from test_regex('(a)e', 'ae', '-'); {ae,a} (2 rows) = --- expectMatch 4.2 o (a)e ae -select * from test_regex('(a)e', 'ae', 'o'); - test_regex = ------------- - {0} - {NULL} +-- expectMatch 4.2 oPR (.)\1e abeaae aae {} +select * from test_regex('(.)\1e', 'abeaae', 'oPR'); + test_regex = +-------------------------------- + {1,REG_UBACKREF,REG_UNONPOSIX} + {aae,NULL} (2 rows) = -- expectMatch 4.3 b {\(a\)b} ab ab a @@ -2658,6 +2658,20 @@ select * from test_regex('(\w+(?=3D )).*\1', 'abc a= bcd abd', 'HLRP'); {"abc abc",abc} (2 rows) = +-- exercise oversize-regmatch_t-array paths in regexec() +-- (that case is not reachable via test_regex, sadly) +select substring('fffoooooooooooooooooooooooooooooooo', '^(.)\1(.)(.)(.)(= .)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)= (.)(.)(.)'); + substring = +----------- + f +(1 row) + +select regexp_split_to_array('abcxxxdefyyyghi', '((.))(\1\2)'); + regexp_split_to_array = +----------------------- + {abc,def,ghi} +(1 row) + -- doing 15 "octal escapes vs back references" -- # initial zero is always octal -- expectMatch 15.1 MP "a\\010b" "a\bb" "a\bb" @@ -3476,6 +3490,22 @@ select * from test_regex('((.))(\2){0}', 'xy', 'RPQ= '); {x,x,x,NULL} (2 rows) = +-- expectMatch 21.37 RP ((.))(\2) xyy yy y y y +select * from test_regex('((.))(\2)', 'xyy', 'RP'); + test_regex = +-------------------------------- + {3,REG_UBACKREF,REG_UNONPOSIX} + {yy,y,y,y} +(2 rows) + +-- expectMatch 21.38 oRP ((.))(\2) xyy yy {} {} {} +select * from test_regex('((.))(\2)', 'xyy', 'oRP'); + test_regex = +-------------------------------- + {3,REG_UBACKREF,REG_UNONPOSIX} + {yy,NULL,NULL,NULL} +(2 rows) + -- doing 22 "multicharacter collating elements" -- # again ugh -- MCCEs are not implemented in Postgres, so we skip all these tests diff --git a/src/test/modules/test_regex/sql/test_regex.sql b/src/test/mod= ules/test_regex/sql/test_regex.sql index 9224fdfdd3..3419564203 100644 --- a/src/test/modules/test_regex/sql/test_regex.sql +++ b/src/test/modules/test_regex/sql/test_regex.sql @@ -63,8 +63,8 @@ select * from test_regex('ab', 'ab', 'b'); = -- expectMatch 4.1 - (a)e ae ae a select * from test_regex('(a)e', 'ae', '-'); --- expectMatch 4.2 o (a)e ae -select * from test_regex('(a)e', 'ae', 'o'); +-- expectMatch 4.2 oPR (.)\1e abeaae aae {} +select * from test_regex('(.)\1e', 'abeaae', 'oPR'); -- expectMatch 4.3 b {\(a\)b} ab ab a select * from test_regex('\(a\)b', 'ab', 'b'); -- expectMatch 4.4 - a((b)c) abc abc bc b @@ -775,6 +775,11 @@ select * from test_regex('(^\w+).*\1', 'abc abc abc',= 'LRP'); select * from test_regex('(^\w+\M).*\1', 'abc abcd abd', 'LRP'); select * from test_regex('(\w+(?=3D )).*\1', 'abc abcd abd', 'HLRP'); = +-- exercise oversize-regmatch_t-array paths in regexec() +-- (that case is not reachable via test_regex, sadly) +select substring('fffoooooooooooooooooooooooooooooooo', '^(.)\1(.)(.)(.)(= .)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)= (.)(.)(.)'); +select regexp_split_to_array('abcxxxdefyyyghi', '((.))(\1\2)'); + -- doing 15 "octal escapes vs back references" = -- # initial zero is always octal @@ -1011,6 +1016,10 @@ select * from test_regex('(a*)*', 'bc', 'N'); select * from test_regex(' TO (([a-z0-9._]+|"([^"]+|"")+")+)', 'asd TO fo= o', 'M'); -- expectMatch 21.36 RPQ ((.))(\2){0} xy x x x {} select * from test_regex('((.))(\2){0}', 'xy', 'RPQ'); +-- expectMatch 21.37 RP ((.))(\2) xyy yy y y y +select * from test_regex('((.))(\2)', 'xyy', 'RP'); +-- expectMatch 21.38 oRP ((.))(\2) xyy yy {} {} {} +select * from test_regex('((.))(\2)', 'xyy', 'oRP'); = -- doing 22 "multicharacter collating elements" -- # again ugh ------- =_aaaaaaaaaa0--