Re: Row pattern recognition

Henson Choi <assam258@gmail.com>

From: Henson Choi <assam258@gmail.com>

To: Tatsuo Ishii <ishii@postgresql.org>

Cc: vik@postgresfriends.org, er@xs4all.nl, jacob.champion@enterprisedb.com, david.g.johnston@gmail.com, peter@eisentraut.org, pgsql-hackers@postgresql.org

Date: 2026-02-24T01:28:19Z

Lists: pgsql-hackers

Attachments

nocfbot-0003-alt-dfs-early-termination.patch (application/octet-stream) patch 0003
nocfbot-0001-rpr-explain-32bit-fix.patch (application/octet-stream) patch 0001
nocfbot-0005-cycle-detection-bitmap.patch (application/octet-stream) patch 0005
nocfbot-0002-prev-next-define-only.patch (application/octet-stream) patch 0002
nocfbot-0004-reluctant-quantifiers.patch (application/octet-stream) patch 0004
nocfbot-0006-allow-a0-quantifier.patch (application/octet-stream) patch 0006

Hi Tatsuo,

Here are six incremental patches on top of v43.

nocfbot-0001 through nocfbot-0004 are the same patches from the
previous round (32-bit test fix, PREV/NEXT restriction, ALT lexical
ordering, reluctant quantifiers).

nocfbot-0005: Detect zero-consumption NFA cycles

Adds a per-element visited bitmap to detect zero-consumption cycles
during DFS epsilon expansion.  Before each state's DFS, the bitmap
is cleared; as nfa_advance_state() recurses through epsilon
transitions, each elemIdx is marked visited.  If the same elemIdx
is reached again within the same DFS, it means an epsilon-only
loop -- the state is freed immediately.

The ad-hoc (count == 0 && min == 0) exit condition in
nfa_advance_end() is removed.  The FIXME test cases are resolved
and renamed to "Zero-Consumption Cycle Detection".

nocfbot-0006: Allow A{0} quantifier

With cycle detection in place, this becomes straightforward.
Lowers the {n} bound minimum from 1 to 0.  A{0} is treated as an
epsilon transition -- the variable is skipped entirely.

Next I plan to work on test reorganization, cross-database result
comparison, and a review pass over the NFA executor.

Best regards,
Henson

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

Adjust cross-version upgrade tests for seg_out() fix
- 3e3d7875e956 19 (unreleased) cited
Rationalize error comments in partition split/merge tests
- ecb2508aaf9b 19 (unreleased) cited
Add fast path for foreign key constraint checks
- 2da86c1ef9b5 19 (unreleased) cited
Fix assorted pretty-trivial memory leaks in the backend.
- e78d1d6d47dc 19 (unreleased) cited
Add temporal FOREIGN KEY contraints
- 89f908a6d0ac 18.0 cited
Add trailing commas to enum definitions
- 611806cd726f 17.0 cited
Remove obsolete executor cleanup code
- d060e921ea5a 17.0 cited