Re: [PATCH] Use Boyer-Moore-Horspool for simple LIKE contains patterns

Hi Bryan,

Thanks for the report and the clear explanation.

The attached v3 patch takes your first suggestion: only Const patterns can
reuse the cached search state without revalidation.

Params now go through the existing revalidation path, comparing the current
pattern with the saved pattern on each call.
If the pattern changes, the current call falls back to the generic LIKE
matcher,
and subsequent calls using the same cached state do likewise.
This avoids incorrectly reusing the initial pattern when a PL/pgSQL simple
expression reuses its ExprState across variable changes.

I have added your test case to the regression tests, along with test
coverage
for name inputs and repeated calls with an unchanged pattern.
Your example now correctly returns t, f, t.

Based on HEAD fcc0e27f45e2 (with assertions and ICU enabled), all 246 core
regression tests and all four contrib/pg_trgm tests passed.

Thanks again for catching this.

Regards,
Atsushi Ogawa

2026年9月15日(火) 2:27 Bryan Green <dbryan(dot)green(at)gmail(dot)com>:

> On 7/17/2026 5:23 AM, Atsushi Ogawa wrote:
> > Hi Greg,
> >
> > Thanks for the careful review. I have attached a v2 patch.
> >
> >> git grep shows we already use BMH in src/backend/utils/adt/varlena.c
> >> Worth acknowledging that in a code comment somewhere? I didn't see any
> >> obvious advantage to refactoring things out at quick glance, but a
> mention
> >> might be nice.
> >
> > Agreed. I added a comment at the top of like_bmh.c that cross-references
> > the
> > existing Boyer-Moore-Horspool implementation in varlena.c and explains
> why I
> > kept the implementations separate. The varlena.c code searches one
> > (haystack, needle) pair with an adaptively sized skip table, whereas the
> > LIKE
> > path interprets its internal backslash escapes while extracting the
> literal
> > and caches the prepared search state in FmgrInfo for use across rows. I
> did
> > not find a clean way to share that machinery without introducing more
> > coupling
> > than seemed useful.
> >
> >> + * by '%' wildcards. Remove backslash escapes while building the
> search
> >> + * state.
> >>
> >> Slightly off comment. This is for like_bmh_pattern_is_eligible - we are
> > not
> >> removing here, just skipping things when we count.
> >
> > Right. I reworded the comment to say that the eligibility check skips
> > backslash escapes while counting the literal length. The escapes are
> > removed
> > later, when the search state is built.
> >
> >> if (i + 1 >= plen - 1)
> >>
> >> Worth a comment to explain that we are catching the '%foo\%' case here.
> >
> > Added. The new comment explains that this rejects patterns such as
> > '%foo\%', where the backslash escapes the closing '%' rather than a
> literal
> > byte.
> >
> >> pattern_stable = get_fn_expr_arg_stable(flinfo, 1);
> >>
> >> /*
> >> * ScalarArrayOpExpr invokes the operator once per array element. The
> >> * array expression can be stable while the pattern passed to this
> > function
> >> * changes between calls, so it must not use a cached search state.
> >> */
> >> if (flinfo->fn_expr != NULL && IsA(flinfo->fn_expr, ScalarArrayOpExpr))
> >> pattern_stable = false;
> >>
> >> My first thought was to make this an if/else so we don't reclobber, but
> >> seeing how later on we check collation every time, I'm wondering if we
> >> shouldn't just check the pattern as well every time via a memcmp like
> >> regexp.c does in RE_compile_and_cache (and remove that block above).
> >> So we store it verbatim in the like_bmh_init() function with memcpy,
> then
> >> make the check inside like_bmh_match() that looks like this:
> >>
> >> unlikely(collation has changed)
> >>
> >> into:
> >>
> >> unlikely(
> >> collation has changed
> >> OR pattern length has changed
> >> OR pattern itself has changed (e.g. memcmp true)
> >> )
> >>
> >> Also means you could then roll get_fn_expr_arg_stable into that big old
> ||
> >> grouping, and remove pattern_stable entirely.
> >
> > I implemented the suggested verbatim-pattern cache and benchmarked it
> > directly
> > against the initial patch's structural-stability design. The test
> scanned
> > two
> > million rows per transaction, with a warmup followed by the median of
> seven
> > pgbench runs of 40 transactions each. The benchmark used an AMD EPYC
> 7763
> > host with 8 vCPUs, GCC 11.4.0, and an -O2 -g build, using a UTF-8
> database
> > with C locale. The results below are median latency per scan:
> >
> > case initial patch memcmp vs.
> initial
> > ------------------------------------ ------------- --------
> -----------
> > constant, 4-byte literal 63.7 ms 65.1 ms
> +2.3%
> > constant, 32-byte literal 48.8 ms 48.4 ms
> -0.8%
> > constant, 4-byte literal, 8-byte input 43.2 ms 44.0 ms
> +1.8%
> > non-constant, fixed value at runtime 92.9 ms 57.0 ms
> -38.6%
> > non-constant, changes on every row 91.6 ms 172.4 ms
> +88.2%
> >
> > The per-row length check and memcmp were therefore not particularly
> > expensive
> > for stable constant patterns. The more important tradeoff involved
> > non-constant patterns. When the value remained fixed at runtime, the
> > verbatim
> > cache was faster because it could use BMH. When the pattern changed on
> > every
> > row, however, it was substantially slower than the initial patch, which
> > sends
> > that case to the existing generic matcher. The verbatim variant had to
> > repeat
> > the eligibility check and rebuild the 256-entry skip table for every row.
> >
> > I then tested a hybrid of the two approaches. Patterns that
> > get_fn_expr_arg_stable() identifies as a Const or external Param keep the
> > existing comparison-free search state. An eligible non-stable pattern
> > stores
> > its verbatim bytes and is revalidated with a length check and memcmp. On
> > the
> > first mismatch, the state is changed permanently to the generic marker.
> The
> > mismatching row and all later rows use the existing matcher; the
> eligibility
> > check and skip-table build are never repeated.
> >
> > ScalarArrayOpExpr still has to be classified as non-stable, since its
> array
> > expression can be a Const while the operator receives a different
> element on
> > each call. It now uses the same revalidation path and falls back
> > permanently
> > if the elements differ.
> >
> > I reran the comparison on aarch64 using two clean build trees based on
> the
> > same source revision and configured with the same options. Both servers
> > used
> > the same data directory. The table contained two million 32-byte
> strings, a
> > fixed pattern column, and an alternating pattern column. Parallel query
> was
> > disabled, each server was warmed before measurement, and the server order
> > was
> > alternated in ABBA order. The figures below are medians of 16 EXPLAIN
> > (ANALYZE, TIMING OFF) runs:
> >
> > case initial patch hybrid vs. initial
> > -------------------------------- ------------- -------- -----------
> > constant pattern 194.1 ms 185.6 ms -4.4%
> > non-constant, fixed at runtime 299.8 ms 199.9 ms -33.3%
> > non-constant, changes every row 303.4 ms 304.9 ms +0.5%
> > generic fallback control 288.5 ms 289.5 ms +0.3%
> >
> > The constant-pattern difference appears to be a compiler-dependent
> > code-layout
> > effect rather than a benefit of the hybrid design, so I do not interpret
> it
> > as
> > a general speedup. More importantly, the runtime-fixed case captures the
> > benefit of the verbatim cache, while the row-varying case tracks the
> generic
> > fallback control instead of rebuilding the 256-entry skip table for every
> > row.
> >
> > The attached v2 patch uses this hybrid design. Thus the common stable
> path
> > does not pay a memcmp, runtime-fixed non-constant values can use BMH,
> and a
> > pattern that is observed to vary falls back without any rebuild penalty.
> >
> >> Hm...that collation test and message is already caught and done by
> >> GenericMatchText, so you could throw !OidIsValid(collation) into that ||
> >> group as well, and remove the ereport section entirely. It then falls
> >> through later to GenericMatchText, which complains about the collation
> >> there.
> >
> > Done. The invalid-collation case is now included in the rejection group
> and
> > falls through to GenericMatchText. I removed the duplicate ereport block
> > from
> > like_bmh.c.
> >
> >> It did have one test failure:
> >>
> >> @@ -151,8 +151,8 @@
> >> p | matched
> >> --------+---------
> >> %abcd% | t
> >> - %b%e% | f
> >> %b_d% | t
> >> + %b%e% | f
> >> %wxyz% | f
> >> (4 rows)
> >>
> >> I think it's from the "Row-varying patterns must use the generic
> matcher."
> >> test.
> >
> > Thanks for catching this. This was a locale-dependent sort-order issue
> in
> > the
> > test, not a matcher failure. The query now uses ORDER BY p COLLATE "C".
> >
> > I retested the revised patch against PostgreSQL HEAD 0348090: all 246
> core
> > regression tests passed, including like_bmh, and all four contrib/pg_trgm
> > tests passed.
> >
> > Thanks,
> > Atsushi Ogawa
> >
> > 2026年7月15日(水) 3:29 Greg Sabino Mullane <htamfids(at)gmail(dot)com>:
> >
> >> Great idea, love seeing the speedups! Also appreciate the background,
> >> detailed explanation, and benchmarks. Quick code review:
> >>
> >> git grep shows we already use BMH in src/backend/utils/adt/varlena.c
> >> Worth acknowledging that in a code comment somewhere? I didn't see any
> >> obvious advantage to refactoring things out at quick glance, but a
> mention
> >> might be nice.
> >>
> >>> + * by '%' wildcards. Remove backslash escapes while building the
> >> search state.
> >>
> >> Slightly off comment. This is for like_bmh_pattern_is_eligible - we are
> >> not removing here, just skipping things when we count.
> >>
> >>> if (i + 1 >= plen - 1)
> >>
> >> Worth a comment to explain that we are catching the '%foo\%' case here.
> >>
> >>
> >>> pattern_stable = get_fn_expr_arg_stable(flinfo, 1);
> >>>
> >>> /*
> >>> * ScalarArrayOpExpr invokes the operator once per array element. The
> >>> * array expression can be stable while the pattern passed to this
> >> function
> >>> * changes between calls, so it must not use a cached search state.
> >>> */
> >>> if (flinfo->fn_expr != NULL && IsA(flinfo->fn_expr, ScalarArrayOpExpr))
> >>> pattern_stable = false;
> >>
> >> My first thought was to make this an if/else so we don't reclobber, but
> >> seeing how later on we check collation every time, I'm wondering if we
> >> shouldn't just check the pattern as well every time via a memcmp like
> >> regexp.c does in RE_compile_and_cache (and remove that block above). So
> we
> >> store it verbatim in the like_bmh_init() function with memcpy, then make
> >> the check inside like_bmh_match() that looks like this:
> >>
> >> unlikely(collation has changed)
> >>
> >> into:
> >>
> >> unlikely(
> >> collation has changed
> >> OR pattern length has changed
> >> OR pattern itself has changed (e.g. memcmp true)
> >> )
> >>
> >> Also means you could then roll get_fn_expr_arg_stable into that big old
> ||
> >> grouping, and remove pattern_stable entirely.
> >>
> >> Hm...that collation test and message is already caught and done by
> >> GenericMatchText, so you could throw !OidIsValid(collation) into that ||
> >> group as well, and remove the ereport section entirely. It then falls
> >> through later to GenericMatchText, which complains about the collation
> >> there.
> >>
> >> Anyway, the patch compiled cleanly against d15a6bc2 (Tue Jul 14 10:28:04
> >> 2026 +0200)
> >>
> >> It did have one test failure:
> >>
> >> @@ -151,8 +151,8 @@
> >> p | matched
> >> --------+---------
> >> %abcd% | t
> >> - %b%e% | f
> >> %b_d% | t
> >> + %b%e% | f
> >> %wxyz% | f
> >> (4 rows)
> >>
> >> I think it's from the "Row-varying patterns must use the generic
> matcher."
> >> test.
> >>
> >>
> >> Cheers,
> >> Greg
> >>
> >>
> >
> I've continued doing security audits of commitfest patches. I didn't
> find a security issue in this one, but it does return wrong results in
> one case.
>
> A LIKE whose pattern is a plpgsql variable that changes within a
> transaction keeps matching against the first pattern.
>
> create function f(s text, p text) returns boolean
> language plpgsql as $$ begin return s like p; end $$;
>
> select s, p, f(s, p) from (values
> ('xxabcdxx','%abcd%'),
> ('xxabcdxx','%wxyz%'),
> ('xxwxyzxx','%wxyz%')) v(s, p);
> -- HEAD: t, f, t
> -- patch: t, t, f
>
> The cached search state is kept because get_fn_expr_arg_stable() reports
> the pattern stable for a PARAM_EXTERN, but a plpgsql simple expression
> reuses its ExprState across evaluations while the variable changes, so
> it keeps using the first row's literal.
>
> Treating only a Const as stable (IsA(arg, Const)), or always taking the
> revalidate path, fixes it.
>
> --
> Bryan Green
> EDB: https://www.enterprisedb.com
>