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.
Regards,
Atsushi Ogawa
Use-Boyer-Moore-Horspool-for-simple-LIKE-patterns.patch
Description: Binary data
