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

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 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>:

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@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

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

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:

/messages/by-id/CALkFZpcbipVJO=xVvNQMZ7uLUgHzBn65GdjtBHdeb47QV4XzLw@mail.gmail.com

and Tom Lane's later discussion here:

/messages/by-id/3811203.1675907383@sss.pgh.pa.us

There is also the recent related thread here:

/messages/by-id/88272f23-19b4-493d-bdd7-258218b74881@gmail.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

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.green@gmail.com>:

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

2026年9月15日(火) 10:24 Haibo Yan <tristan.yim@gmail.com>:

Glad to see all the refinement happening with this patch. Some less
important things:

* Portions Copyright (c) 1996-2026

This looks like new code. Unless you were working on this in 1996, the
copyrights for the new files (like_bmh.c and like_bmh.h) should be

# Copyright (c) 2026, PostgreSQL Global Development Group

See e.g. src/backend/commands/repack_worker.c

+       if ((pg_database_encoding_max_length() > 1 &&
+                GetDatabaseEncoding() != PG_UTF8) ||
+               !OidIsValid(collation) ||
+               !like_bmh_pattern_is_eligible(p, plen, &literal_len))
+       {
+               state = MemoryContextAlloc(flinfo->fn_mcxt,
sizeof(LikeBMHState));
+               state->mode = LIKE_BMH_GENERIC;
+               flinfo->fn_extra = state;
+               return state;
+       }
+
+       locale = pg_newlocale_from_collation(collation);
+       if (!locale->deterministic)
+       {
+               state = MemoryContextAlloc(flinfo->fn_mcxt,
sizeof(LikeBMHState));
+               state->mode = LIKE_BMH_GENERIC;
+               flinfo->fn_extra = state;
+               return state;
+       }

locale is only used in this one place, so we can remove that var and avoid
writing that same code block twice by rolling the deterministic locale
check directly into the first set of checks:

if ((pg_database_encoding_max_length() > 1 &&
GetDatabaseEncoding() != PG_UTF8) ||
!OidIsValid(collation) ||
!like_bmh_pattern_is_eligible(p, plen, &literal_len) ||
!pg_newlocale_from_collation(collation)->deterministic)

Cheers,
Greg