Re: [PATCH] Use Boyer-Moore-Horspool for simple LIKE contains patterns - Mailing list pgsql-hackers

On Mon, Sep 28, 2026 at 6:41 AM Atsushi Ogawa
<atsushi.ogawa001@gmail.com> wrote:
>
> Hi Haibo,
>
> Thanks again for the thorough testing and analysis of the bounded-work +
> resume approach. I still think that design is sound, but after further
> experiments I would like to propose a simpler alternative in the attached
> v5 patch.
>
> The patch builds on v4 but changes how patterns are cached: only Const
> patterns can use cached BMH search state. Other patterns, including external
> Params and PL/pgSQL variables, select the existing LIKE matcher on the first
> call and keep using it, without per-row revalidation or pattern-change state.
> The search keeps the traditional BMH last-byte guard and Horspool shifts. It
> checks the candidate's last byte first, then compares the remaining literal
> bytes from left to right.
> This allows candidate checks to stop early on mismatches near the start,
> without first scanning a long matching suffix. The shifts remain correct
> because they depend only on the byte at the end of the candidate.
>
> This overall design is a compromise rather than a claim that BMH has the same
> performance characteristics as existing LIKE for every input. When the
> last-byte shift is small, especially when skip is 1 and the last byte is
> frequent, the candidate scan still has a cost.
>
> One change helped substantially: when the last-byte guard matches, the shift
> is always skip_table[lastlit], which is constant for the pattern. Preloading
> that value outside the search loop avoids a dependent table lookup after each
> candidate comparison. In the standalone matrix used for this comparison,
> this reduced the worst observed regression relative to existing LIKE from
> about 4.5x to about 2.0x, and reduced the number of cases above 2x from 26
> to 1 compared with the same left-to-right variant before this change.
>
> The minimum literal length now depends on the database encoding: 6 bytes for
> single-byte encodings and 4 bytes for UTF-8. Non-UTF-8 multibyte encodings
> remain on the existing matcher. For single-byte encodings, the existing
> matcher can scan one byte per very cheap comparison, while a Horspool step
> requires dependent loads from the input and skip table. With only a 4- or
> 5-byte literal, that setup cost can outweigh the skipped comparisons,
> particularly for rare first bytes. Using a threshold of 6 puts 4- and 5-byte
> cases back on the existing path, while retaining useful BMH gains for longer
> literals.
>
> I reran existing LIKE, v4, v4 plus the bounded-work/resume prototype, and
> v5 on AArch64 at PostgreSQL HEAD 5594f209c3. The SQL tests used sequential
> scans with JIT and parallel query disabled; the numbers below are medians of
> nine measurements.
>
>                                             existing      v4    v4+poc       v5
>     UTF8, first-byte mismatch, 128-byte literal
>                                                15.99ms 793.29ms 17.42ms  14.90ms
>     LATIN1, same input                          12.70ms 794.24ms 17.35ms  14.82ms
>     UTF8, penultimate-byte mismatch           2725.31ms  16.99ms 16.27ms 401.36ms
>
> The penultimate-mismatch case is substantially slower than v4, but v5 is
> still about 6.8x faster than existing LIKE. v5 also retained speedups on
> English and Japanese text. The largest observed regression on the repetitive
> inputs was about 1.8x in LATIN1, for which the last-byte shift is often 1.
>
> The bounded-work/resume prototype provides stronger protection when candidate
> checks repeatedly fail late in the comparison: in the AArch64 tests it capped
> the regression on the 128-byte mismatch cases to about 1.1x–1.4x relative to
> existing LIKE. v5 is faster on the first-byte-mismatch case and has a simpler
> search path, but gives up that stronger protection on some inputs with late
> mismatches (such as the penultimate-byte case).
>
> For now, I favor v5 because it leaves the existing matcher implementations
> unchanged and requires no comparison-budget accounting, resume handling, or
> per-row pattern revalidation. Restricting BMH to Const patterns also keeps
> the implementation and matching hot path simpler.
>
> The attached v5 patch passed all 246 core regression tests on 5594f209c3,
> including like_bmh. The targeted like_bmh test also passed in LATIN1. The
> queries in this rerun produced identical results across all four builds.
>
> This is a proposal for a simpler alternative, not a claim of a universal
> no-regression bound. Measurements on other architectures, encodings, and
> workloads would be useful in deciding whether the remaining narrow
> regressions warrant a more adaptive fallback policy.
>
> Regards,
> Atsushi Ogawa
>

Hi Atsushi,

I finished testing v5 and took another look at the new search structure. I
think this version is in good shape.
I reran the full 525-case entropy/mismatch matrix against HEAD. The results I
got were:

                                        v3          bounded /2      v5
    median vs HEAD    0.322x         0.325x          0.296x
    worst                       35.19x           1.73x           1.65x
    p95                           5.10x           1.35x           1.14x
    cases > 1.25x             101              65                21
    cases > 2x                    61               0                   0
    >= 1.25x wins             397           365               458
    >= 2x wins                  347           336               409

So the last-byte guard plus left-to-right verification seems to work very well.
 In this matrix it removes the large regression region without needing the
 bounded-work/resume machinery, while preserving more BMH wins.

I also checked the opposite mismatch orientation, where left-to-right
verification has to compare almost the whole literal before rejecting the
candidate. For example, with `repeat('a', 1024)` and a 128-byte literal roughly
shaped as 126 `a` bytes followed by `~a`, v5 was still about 6x faster than
HEAD in my test.

One additional thing I checked was whether the remaining low-alphabet
regression grows with haystack size. Using the worst family I found in the
matrix (4-symbol alphabet, 64-byte literal), the v5/HEAD ratio was:

    8 KB       1.73x
    128 KB     2.11x
    1 MB       2.69x
    2 MB       2.73x
    4 MB       2.67x
    8 MB       2.77x
    16 MB      2.71x

So this appears to converge to roughly a 2.7x constant-factor regression
rather than continuing to grow with input size. Instrumentation agrees with
that: average skip stays around 2.5 bytes, candidates per byte stay around 0.4,
and verification comparisons are zero in this construction. Both paths remain
 linear in the haystack size; the difference seems to be the constant cost of
  the dependent skip-table load chain versus the existing matcher’s simple
  sequential scan.

For reference, v3 on the same construction converged to a somewhat higher
plateau of roughly 3.4x, so v5 still improves this case as well.

I also verified Bryan's PL/pgSQL reproducer. The old version produces the
stale-pattern result, while v5 matches HEAD. Restricting cached BMH state to
actual Const nodes makes the cache behavior much easier to reason about; I
also checked prepared custom/generic plans, array expressions, and row-varying
patterns and did not find another stale-state case.

Core regression, pg_trgm, LATIN1 checks, and differential testing against
HEAD all passed.

I only have a few minor suggestions:

- It would be useful to add a few multibyte UTF-8 literals directly to
  like_bmh.sql, so the actual UTF-8 BMH path gets explicit regression coverage
  rather than only the nondeterministic-collation fallback.
- A short comment explaining why ScalarArrayOpExpr must not be treated as a
  Const/stable pattern would help prevent a future refactor from accidentally
  reintroducing the cache-lifetime problem.
- The patch could use a final pgindent pass.

None of these look blocking to me. Overall, v5 looks ready for community review.

Thanks,
Haibo

> 2026年9月19日(土) 10:12 Atsushi Ogawa <atsushi.ogawa001@gmail.com>:
>>
>>
>> Hi Haibo,
>>
>> Thanks for the thorough testing and analysis, especially the checks around
>> the resume boundary. I agree with your assessment of the bounded-work +
>> resume design.
>>
>> I compared Max(slen / 2, literal_len) and Max(slen / 4, literal_len) in an
>> expanded standalone matrix.
>>
>> The matrix covers row lengths of 32, 64, 128, and 1024 bytes,
>> literal lengths from 4 to 128 bytes, six haystack types (repetitive,
>> random, and English text), and six match/mismatch shapes. It includes
>> mismatches at the penultimate literal byte and literals as long as
>> the row, for a total of 900 cases.
>>
>> The /4 version improved p95, consistent with your results, but some
>> additional cases showed a substantial loss of BMH wins.
>>
>> For example, with a haystack of 1024 'a' bytes and a literal of 126 'a'
>> bytes followed by '~a', I measured approximately:
>>
>>     existing LIKE       193.4 us/row
>>     /2 with floor         1.38 us/row
>>     /4 with floor        83.8 us/row
>>
>> Here, the last-byte guard matches, the next comparison fails immediately,
>> and the Horspool shift is two bytes. The /2 budget lets BMH finish the
>> search. The /4 budget triggers fallback at offset 513, leaving the generic
>> matcher to repeatedly compare the long matching prefix in the remaining
>> suffix.
>>
>> Across the 900-case matrix, /4 improved p95 relative to existing LIKE
>> from 1.53x to 1.31x, but retention of the unbounded version's >= 2x wins
>> fell from 92.3% to 87.7%.
>>
>> A second run showed the same trend. Note that these are matcher-level
>> measurements, not SQL-level results.
>>
>> The literal-length floor helped some short-row cases, although it also
>> delayed fallback enough to hurt others. So I think both the floor and the
>> divisor involve tradeoffs worth checking in the full benchmark.
>>
>> I also tried a simpler alternative: keep the last-byte guard and
>> Horspool shifts, but compare the remaining literal bytes from left
>> to right rather than right to left, as in traditional BMH.
>>
>> This makes candidate verification follow the same comparison order
>> as existing LIKE, so a mismatch near the start of the literal is
>> detected early instead of after scanning a long matching suffix.
>> It avoids the budget accounting and resume machinery.
>>
>> In a separate direct comparison on the same 900-case matrix, this
>> retained more of the unbounded BMH wins and produced fewer regressions
>> above 1.25x than the bounded /2 version with the literal-length floor.
>> However, its worst regression against existing LIKE was about 4.5x.
>>
>> So it looks interesting because of its simplicity, although bounded-work +
>> resume remains more effective at limiting the larger regressions.
>>
>> For now, I lean toward keeping Max(slen / 2, literal_len) as the main
>> candidate while including /4 in further testing.
>>
>> Regards,
>> Atsushi Ogawa
>>
>>
>> 2026年9月18日(金) 3:20 Haibo Yan <tristan.yim@gmail.com>:
>>>
>>> On Wed, Sep 16, 2026 at 8:37 AM Atsushi Ogawa
>>> <atsushi.ogawa001@gmail.com> wrote:
>>> >
>>> >
>>> > Hi Haibo,
>>> >
>>> > Thanks for the detailed matrix. I reproduced the low-entropy regression
>>> > region and agree with your reading: the cost is driven by alphabet size
>>> > and mismatch position rather than literal length, so adjusting
>>> > LIKE_BMH_MIN_LITERAL_LEN cannot describe the boundary.
>>> >
>>> > I would like to get your thoughts on the general approach first.
>>> > I've attached a rough PoC patch just for reference; it still needs
>>> > some cleanup, and a proper patch along with the full numbers
>>> > will follow later.
>>> >
>>> > Needle-only rule
>>> > ----------------
>>> >
>>> > I first tried a needle-only check: skip BMH when the trailing bytes of the
>>> > literal are periodic. While it handles cases like repeat('a') and certain
>>> > repeat('ab') patterns, it does nothing when the periodicity lies in the
>>> > haystack rather than the literal (e.g., repeat('abcd') with a 64-byte
>>> > literal stays around 15x slower). It also needlessly forces literals like
>>> > '%aaaa%' to the generic matcher on ordinary text where BMH would otherwise
>>> > win. A preparation-time test on the pattern alone does not seem viable.
>>> >
>>> > Bounded work with resume
>>> > ------------------------
>>> >
>>> > The approach I am leaning towards is a runtime guard along the lines of
>>> > your suggestion, structured as follows:
>>> >
>>> > - like_bmh_search() checks the guard (last) byte first and only counts
>>> >   inner-loop byte comparisons beyond that guard. The fast path where the
>>> >   last byte differs has zero accounting overhead, preserving standard BMH
>>> >   performance.
>>> >
>>> > - When the comparison count exceeds a given threshold (currently
>>> >   prototyping slen / 2), BMH aborts and reports the offset up to which it
>>> >   has ruled out matches.
>>> >
>>> > - LikeMatchText() then delegates only the remaining, unsearched suffix
>>> >   (backed up to a character boundary, tested under UTF-8) to GenericMatchText().
>>> >   Because the pattern begins with '%', evaluating the suffix yields the
>>> >   exact same semantics without rescanning the entire string from the
>>> >   start.
>>> >
>>> > Preliminary numbers (100,000 rows, best of 5, ms; HEAD / v3 / v3 + bounded work):
>>> >
>>> >   repeat('a',1024) LIKE '%~aaaaaaaaaaaaaaa%'    111 /  552 / 131
>>> >   repeat('a',1024) LIKE '%~' || 63 x 'a' || '%'  113 / 2007 / 135
>>> >   repeat('a',1024) LIKE '%aaaaaaaaaaaaaaa~%'   1896 /  353 / 325
>>> >   English text LIKE '%worst of crimes%' (miss)   162 /   65 /  47
>>> >
>>> > In a microbenchmark, the worst-case late-mismatch penalty drops from
>>> > ~100x down to ~4x at 1024 bytes (~2.3x at 32 bytes). Early mismatch and
>>> > match-present cases remain unaffected or slightly faster thanks to the
>>> > guard byte.
>>> >
>>> > A residual 1.2-4x overhead remains in cases where the generic matcher
>>> > quickly bails out (e.g., the first pattern byte is absent from the haystack)
>>> > while BMH exhausts its comparison budget before falling back.
>>> > Tightening the budget lowers this ceiling, but also trims BMH's advantages on
>>> > benign inputs.
>>> >
>>> > As a note, the attached PoC is an incremental patch on top of v3 rather
>>> > than HEAD.
>>> >
>>> > Regards,
>>> > Atsushi Ogawa
>>>
>>> Hi Atsushi,
>>>
>>> I took a closer look at the PoC and tested the bounded-work/resume path fairly
>>> aggressively. The general approach looks sound to me.
>>>
>>> In particular, I was able to convince myself that the resume offset is correct.
>>> With
>>>
>>> searched = pos - literal_len + 2
>>>
>>> the returned position is the earliest start that has not already been ruled out
>>> by the completed Horspool alignment. The budget check happens only after the
>>> current candidate comparison has completed, so there is no partially examined
>>> alignment to account for. Backing up to a UTF-8 character boundary only enlarges
>>> the suffix passed to GenericMatchText(), which is safe for %literal%.
>>>
>>> I also ran exhaustive/fuzz differential tests around the resume boundary,
>>> including UTF-8 and single-byte cases, and did not find a mismatch.
>>>
>>> The performance results are encouraging as well. On the previous matrix, using
>>> the current slen / 2 budget changed the overall result roughly as follows:
>>>
>>>                              v3 unbounded    bounded
>>>     median ratio                 0.314x       0.314x
>>>     worst regression             33.30x        1.80x
>>>     cases > 1.25x                    98           64
>>>     cases > 2x                       62            0
>>>     >= 1.25x wins retained                     89.4%
>>>     >= 2x wins retained                        87.8%
>>>
>>> So the >2x regression region disappears while most of the useful BMH
>>> wins remain.
>>>
>>> I did find one issue with the current budget definition. If
>>>
>>>     slen / 2 < literal_len
>>>
>>> then the first candidate can consume the entire budget, after which
>>> GenericMatchText() rescans almost the whole haystack. In my matrix this turned
>>> seven cases from roughly 0.46x wins into 1.46-1.49x regressions.
>>>
>>> A simple lower bound seems to avoid that class:
>>>
>>>     budget = Max(slen / 2, literal_len)
>>>
>>> More interestingly, I also tried several budget values, and
>>>
>>>     Max(slen / 4, literal_len)
>>>
>>> looked better than slen / 2 in this test set. It kept essentially the same
>>> median, worst case, and useful-win retention, but reduced the number of >1.25x
>>> regressions from 64 to 24 and improved the p95 ratio from about 1.31x to 1.23x.
>>>
>>> I would not read too much into /4 as a magic constant yet, but I think the
>>> literal_len lower bound is important, and /4 seems worth including in the full
>>> benchmark when you prepare the next patch.
>>>
>>> One other thing I found is that the remaining ~1.7-1.8x matcher-level
>>> regressions do not appear to come from exhausting the budget too late. In some
>>> of those cases BMH performs fewer byte comparisons than GenericMatchText(),
>>> but still loses because it executes many dependent skip-table lookups with a
>>> small average skip. Tightening the budget further starts to remove substantial
>>> BMH wins, so I don’t think that residual can be eliminated cleanly with a
>>> smaller threshold alone.
>>>
>>> I also checked the “zero accounting overhead” point. On the guard-miss path
>>> the bounded version generates essentially the same fast path as a guard-first
>>> version without accounting; the improvement over v3 appears to come from the
>>> guard-first restructuring itself rather than measurement noise.
>>>
>>> So my current view is:
>>>
>>>     1. the bounded-work + resume design looks correct;
>>>     2. it addresses the serious regression region very effectively;
>>>     3. the budget should probably have a lower bound of literal_len;
>>>     4. Max(slen / 4, literal_len) looks worth testing alongside /2;
>>>     5. beyond that, the remaining small regression region looks more like an
>>>       inherent BMH cost than a failure of the fallback policy.
>>>
>>> Thanks,
>>> Haibo
>>>
>>> >
>>> >
>>> > 2026年9月15日(火) 10:24 Haibo Yan <tristan.yim@gmail.com>:
>>> >>
>>> >> On Fri, Jul 17, 2026 at 3:23 AM Atsushi Ogawa
>>> >> <atsushi.ogawa001@gmail.com> 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@gmail.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
>>> >> >>
>>> >>
>>> >> Hi Ogawa-san,
>>> >>
>>> >> I did some more testing of the BMH fast path, specifically to check whether the
>>> >> repetitive-input regression I mentioned is just one adversarial construction or
>>> >> part of a broader pattern.
>>> >>
>>> >> I ran a matrix varying haystack structure, literal length, mismatch position,
>>> >> and haystack length, with the existing LIKE matcher and the patch's BMH search
>>> >> in the same binary. The overall result is actually quite favorable to BMH: it
>>> >> wins most of the tested cases, often by a large margin. However, there is also a
>>> >> fairly well-defined regression region on low-entropy inputs when the backwards
>>> >> comparison fails late.
>>> >>
>>> >> A few representative numbers are:
>>> >>
>>> >>     haystack                       literal length   existing LIKE
>>> >> BMH       ratio
>>> >>     repeat('a', 1024)                     16           2.14 ms
>>> >> 20.78 ms    9.7x
>>> >>     repeat('a', 1024)                     64           2.13 ms
>>> >> 66.93 ms   31.4x
>>> >>     repeat('ab', ...), 1024              64           2.12 ms
>>> >> 33.24 ms   15.7x
>>> >>     repeat('abcd', ...), 1024           64           2.12 ms
>>> >> 16.70 ms    7.9x
>>> >>     random alphabet=4, 1024         4           2.24 ms       7.41 ms    3.3x
>>> >>     English text, 1024                   16           2.23 ms
>>> >> 1.40 ms    0.63x
>>> >>
>>> >> The important part seems to be the combination of low effective alphabet size
>>> >> and mismatch position, rather than literal length by itself.
>>> >>
>>> >> For example, against `repeat('a', 1024)`, a literal shaped roughly as
>>> >>
>>> >>     ~aaaaaaaaaaaaaaa
>>> >>
>>> >> causes Horspool to compare almost the whole literal backwards before failing,
>>> >> while the skip for `a` is only one byte. For a 16-byte literal I counted 1009
>>> >> candidate alignments and 16 comparisons per alignment. The existing LIKE matcher
>>> >> has almost the opposite behavior here: its first literal byte (`~`) is absent
>>> >> from the haystack, so it rejects candidates very cheaply.
>>> >>
>>> >> Mismatch position changes the result dramatically. With the same 1024-byte
>>> >> repeated-`a` input and a 16-byte literal I measured approximately:
>>> >>
>>> >>     immediate mismatch:   BMH / existing LIKE = 0.04x
>>> >>     middle mismatch:                         = 0.34x
>>> >>     late mismatch:                           = 9.7x
>>> >>
>>> >> So BMH can be much faster or much slower on very similar inputs.
>>> >>
>>> >> This also means that increasing `LIKE_BMH_MIN_LITERAL_LEN` does not appear to
>>> >> address the issue. The worst measured regression actually increased with literal
>>> >> length:
>>> >>
>>> >>     4 bytes     4.3x
>>> >>     8 bytes     5.1x
>>> >>     16 bytes    9.9x
>>> >>     32 bytes   18.5x
>>> >>     64 bytes   33.7x
>>> >>
>>> >> The regression is not universal. In this test set, English text and random data
>>> >> over medium/large alphabets did not show >2x regressions, and for literals >= 8
>>> >> bytes they did not show meaningful regressions at all. So I would describe this
>>> >> as a narrow but systematic low-entropy case rather than a general
>>> >> problem with BMH.
>>> >>
>>> >> I also tried looking for a cheap needle-only rule that could avoid the
>>> >> bad cases.
>>> >> There are some useful signals in the skip table, but they have substantial false
>>> >> positives. More fundamentally, the same byte-identical literal can be a large
>>> >> win or a large loss depending only on the haystack/match position, so a
>>> >> preparation-time test based only on the literal cannot completely solve this.
>>> >>
>>> >> This seems related to the concerns raised in the earlier BMH/LIKE discussions:
>>> >>
>>> >> https://www.postgresql.org/message-id/CALkFZpcbipVJO%3DxVvNQMZ7uLUgHzBn65GdjtBHdeb47QV4XzLw%40mail.gmail.com
>>> >>
>>> >> and Tom Lane's later discussion here:
>>> >>
>>> >> https://www.postgresql.org/message-id/3811203.1675907383%40sss.pgh.pa.us
>>> >>
>>> >> There is also the recent related thread here:
>>> >>
>>> >> https://www.postgresql.org/message-id/flat/88272f23-19b4-493d-bdd7-258218b74881%40gmail.com
>>> >>
>>> >> Given that this is a performance optimization, I think it would be useful to
>>> >> decide explicitly how much regression on this class of inputs is acceptable, or
>>> >> whether some bounded-work fallback would make sense. A runtime guard might be
>>> >> more promising than a needle-only eligibility rule, since it could notice that
>>> >> the search is doing unusually large amounts of work without requiring a separate
>>> >> scan of the haystack.
>>> >>
>>> >> I don't think these results argue against using BMH in general — in the same
>>> >> matrix it was substantially faster in most cases — but they do suggest that
>>> >> the current literal-length threshold alone doesn't describe the profitability
>>> >> boundary.
>>> >>
>>> >> Regards,
>>> >> Haibo