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

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