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

Hi,

This patch adds a Boyer-Moore-Horspool (BMH) fast path for simple LIKE '%literal%' contains-search patterns.

Motivation
col LIKE '%literal%' is a common query shape. The existing matcher scans the input one position at a time, which is O(text * pattern) in the worst case. For medium-to-long search literals, a Boyer-Moore-Horspool search skips ahead using a 256-entry bad-character table and is substantially faster in practice, while staying simple and allocation-light.

What the patch does
The dispatch happens at execution time, inside the existing textlike and namelike entry points. On the first call for a given FmgrInfo, the code inspects the (escape-normalized) pattern; if it is eligible it builds and caches a small BMH search state in FmgrInfo.fn_extra and uses it for every subsequent row. If the pattern is not eligible, it caches a "generic" marker so that later rows go straight to the existing matcher with no re-analysis. Scalar-array operator calls (LIKE ANY / LIKE ALL) also stay on the generic path because the pattern can change between array elements under one FmgrInfo.

Because dispatch stays inside the existing textlike and namelike functions, planner behavior and index-path selection, including pg_trgm, are unchanged.

The BMH path is used only when:

the pattern is stable for the current execution (constant, or a query-stable parameter as reported by get_fn_expr_arg_stable())
the pattern starts and ends with %
the middle part contains no unescaped % or _
the unescaped literal is at least four bytes
the database encoding is single-byte or UTF-8
the collation is deterministic
Correctness and eligibility
Because BMH is a byte-oriented search, it is restricted to single-byte and UTF-8 encodings, where a byte match cannot land in the middle of a character. Other multibyte encodings stay on the existing generic matcher; for those the code records the "generic" marker before doing any pattern analysis, so the existing matcher implementation itself is unchanged.

Nondeterministic collations also stay on the existing path, since equality there is not a byte comparison (canonical equivalence, expansions such as ß/ss, etc.).

The four-byte minimum is a conservative, measurement-derived choice. A prototype that enabled BMH for three-byte literals was roughly 7.7% slower than the generic matcher in that case.

Testing
Regression tests cover eligible and fallback patterns, escaped wildcards, varying patterns, scalar-array operations, NULLs, name, prepared statements, and deterministic and nondeterministic ICU collations.

Tested against PostgreSQL HEAD 5594f20 Simplify truncate_query_log() callers. The patch passes the core regression tests, contrib/pg_trgm, and the full Meson test suite. A differential test covering 84 patterns, 10,000 input strings, and both text and name produced identical results before and after the patch.

Benchmarks
Environment: Oracle Linux 8 (Linux 5.4 aarch64, Neoverse-N1),
GCC 8.5.0, built with CFLAGS="-O2 -g" --without-readline --without-zlib.

All tables report averages over seven runs.  Both execution orders were
measured: normal means baseline then patched, and swapped means patched then
baseline.

1M-row synthetic contains search, 50 loops per run:

literal  order   baseline ms  patched ms  change
-------  ------  -----------  ----------  ------
      4  normal    13040.802   10517.101  -19.4%
      4  swapped   12996.720   10541.411  -18.9%
      8  normal    12574.798    6801.678  -45.9%
      8  swapped   12586.869    6787.560  -46.1%
     12  normal    12627.778    5787.701  -54.2%
     12  swapped   12549.117    5749.858  -54.2%
     16  normal    12684.681    5425.017  -57.2%
     16  swapped   12615.273    5414.224  -57.1%

pg_attribute.attname contains search, 50,000 loops per run:

pattern   order    path              baseline ms  patched ms  change
--------  -------  ----------------  -----------  ----------  ------
%class%   normal   BMH                 17098.160   13102.455  -23.4%
%class%   swapped  BMH                 17146.756   13157.733  -23.3%
%cla_s%   normal   generic fallback    17218.321   17419.863   +1.17%
%cla_s%   swapped  generic fallback    17137.538   17317.907   +1.05%

Non-UTF-8 multibyte fallback (EUC), 1M rows, 20 loops per run,
inner-wildcard miss:

type  encoding  order    baseline ms  patched ms  change
----  --------  -------  -----------  ----------  ------
text  EUC_JP    normal     12061.780   12111.844   +0.42%
text  EUC_JP    swapped    12053.521   12071.416   +0.15%
text  EUC_KR    normal     12508.889   12652.742   +1.15%
text  EUC_KR    swapped    12481.675   12610.906   +1.04%
name  EUC_JP    normal      5631.629    5693.626   +1.10%
name  EUC_JP    swapped     5586.379    5634.642   +0.86%
name  EUC_KR    normal      5811.589    5851.628   +0.69%
name  EUC_KR    swapped     5806.066    5836.244   +0.52%
Callgrind measured a small fallback cost: executed instructions increased by 0.184% on aarch64 and 0.248% on x86-64. The wall-clock benchmarks above showed fallback differences of at most 1.17%.

To keep the initial patch focused, it handles ordinary LIKE only; ILIKE and NOT LIKE are unchanged.