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

Hi, Haibo,

Thank you for the thorough v5 review and for rerunning the 525-case test
matrix. The results and the PL/pgSQL check were very helpful. I agree
that the last-byte guard and the left-to-right verification address the
major regression cases while preserving the BMH performance gains.

The attached v6 patch incorporates the suggested regression coverage and
documentation:

- like_bmh.sql now exercises the UTF-8 BMH path with Greek and CJK
characters under the default deterministic collation. The expected
output is included.

- The cache eligibility comment now explains that only a direct Const
pattern argument is cacheable. A ScalarArrayOpExpr calls the operator
once per array element with the same FmgrInfo, so fn_extra may retain
the first element's search state and yield incorrect results for
subsequent elements, even when the array expression is a Const.

- I ran pgindent over the modified C files and header. The resulting
formatting is included in the patch.

- I fetched upstream master and confirmed that the patch applies and
builds on commit 852fd5b86e1a2ac1139c716eb4c96c09c03a632e. The full
core regression suite passed all tests.

Thanks again for the careful testing. The new UTF-8 regression cases
make direct coverage of the optimized path explicit in this revision.

Best,
Atsushi

2026年9月29日(火) 16:39 Haibo Yan <tristan(dot)yim(at)gmail(dot)com>:

> On Mon, Sep 28, 2026 at 6:41 AM Atsushi Ogawa
> <atsushi(dot)ogawa001(at)gmail(dot)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(dot)ogawa001(at)gmail(dot)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(dot)yim(at)gmail(dot)com>:
> >>>
> >>> On Wed, Sep 16, 2026 at 8:37 AM Atsushi Ogawa
> >>> <atsushi(dot)ogawa001(at)gmail(dot)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(dot)yim(at)gmail(dot)com>:
> >>> >>
> >>> >> On Fri, Jul 17, 2026 at 3:23 AM Atsushi Ogawa
> >>> >> <atsushi(dot)ogawa001(at)gmail(dot)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(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
> >>> >> >>
> >>> >>
> >>> >> 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
>