Use a hash table for the regexp cache

Hi hackers,

This is about the TODO item "Better regexp cache management" [1].

Each backend caches up to 32 compiled regular expressions
(MAX_CACHED_RES, fixed at compile time). Lookups scan an array
linearly, and a hit is moved to the front with memmove(). Workloads
that cycle through more than 32 patterns recompile on every call, which
costs about 9x in the benchmark below.

This came up in 2008 [2]. Tom pointed out then that measuring the
cache in bytes would mean breaking into the regex library's private
data structures, suggested a dedicated GUC counting regexps rather than
reusing work_mem, and doubted the self-organizing list would hold up
beyond about 1000 entries because of the O(N) search and memmove. The
first concern has since gone away: since commit bea3d7e3831 each
compiled regexp lives in its own memory context, so its size is easy
to get. The attached patch addresses the third concern, which is the
part that has to be fixed before the size can usefully be raised.

v1-0001 replaces the array with a simplehash table keyed by pattern,
flags and collation, and keeps the entries in a dlist in LRU order.
Lookups and move-to-front are O(1). The replacement policy is still
move-to-front, so the reasoning in the existing comment carries over
unchanged, and the limit is still 32, so behavior is the same as
before. Two details:

- The most recently used entry is compared directly before computing
a hash, so a query that reuses one pattern doesn't regress.

- Each cached_re_str is allocated in its regexp's own memory context
and the hash table only holds pointers. The regex_t handed back to
callers therefore no longer moves when the cache is reorganized (it
used to move with every memmove). A new entry is inserted into the
hash table only after pg_regcomp() succeeds, and the hash insert is
the last step that can fail, so an ERROR leaves the cache consistent.

The patch adds a regression test (in regex.sql) that checks via
pg_backend_memory_contexts that the cache holds 32 entries and evicts
the least recently used one. It turns off debug_parallel_query around
the statements that fill the cache, since the regexps would otherwise
be compiled in a parallel worker. The test passes unmodified on master
as well. There are no user-visible changes, so no documentation
changes.

The patch is against master (8e82d6610e7). It builds without warnings
and passes the full meson test suite, TAP tests included, on macOS
arm64 (clang 21); the regression tests also pass with
debug_parallel_query = regress. There is nothing platform-specific in
it; I'll follow up on cfbot results. pgindent is clean and
typedefs.list is updated.

Benchmark (Apple M5, release build without assertions, 1 client). Each
query does 10000 matches cycling through N distinct patterns. Master
and patched servers run side by side and runs alternate between them;
values are median latency per query over 5 runs of 5 seconds. The
script is attached and takes two installation directories:

With the default limit of 32:

N master patched ratio
1 2.79 ms 2.84 ms 1.02
8 3.41 ms 3.32 ms 0.97
32 4.29 ms 3.80 ms 0.89
33 38.53 ms 38.23 ms 0.99
64 38.75 ms 38.69 ms 1.00
1024 47.08 ms 45.94 ms 0.98

Both built with -DMAX_CACHED_RES=1024, to show what raising the limit
would do with each data structure:

N master patched ratio
1 3.40 ms 3.32 ms 0.98
32 5.01 ms 3.89 ms 0.78
100 8.17 ms 4.68 ms 0.57
300 13.18 ms 5.51 ms 0.42
1000 40.79 ms 5.44 ms 0.13

With the array, a 1000-entry cache hit costs about as much as compiling
the regexp from scratch. With the hash table, the cost stays nearly
flat.

So 0001 is meant for commit on its own, and I'd like to get agreement
on the next step before writing it. For reference, one compiled
regexp takes 9 kB (short literal), 13 kB (email-like pattern) or 34 kB
(50-way alternation) according to pg_backend_memory_contexts. So
today's cache costs roughly 0.3-1 MB per backend, and 1000 entries
would be around 13 MB. The options I see:

1. A GUC limiting the cache by memory (the TODO entry suggests
regexp_cache_size = '1MB'), using MemoryContextMemAllocated() on
each regexp's context. This bounds per-backend memory directly,
whatever the patterns look like.

2. A GUC limiting the number of entries, as suggested in 2008. This
is simpler, but the memory it allows varies with pattern complexity.

3. No GUC; raise the compiled-in limit to something like 128 or 256.

I lean towards 1, with a default close to today's footprint, but
opinions are welcome. Either way, the most recently used entry would
always be kept, since the caller is holding a pointer to it.

[1] https://wiki.postgresql.org/wiki/Todo#Cache_Usage
[2] https://postgr.es/m/8584.1213826927@sss.pgh.pa.us

--
Tianyi Gao