Re: Row pattern recognition

From: Henson Choi <assam258(at)gmail(dot)com>
To: Tatsuo Ishii <ishii(at)postgresql(dot)org>
Cc: vik(at)postgresfriends(dot)org, er(at)xs4all(dot)nl, jacob(dot)champion(at)enterprisedb(dot)com, david(dot)g(dot)johnston(at)gmail(dot)com, peter(at)eisentraut(dot)org, pgsql-hackers(at)postgresql(dot)org
Subject: Re: Row pattern recognition
Date: 2026-02-24 01:28:19
Message-ID: CAAAe_zAxEqdyoOgx4u0A2RXu829CE-RJbJjg1jVz00j3aSYryQ@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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

Attachment Content-Type Size
nocfbot-0003-alt-dfs-early-termination.patch application/octet-stream 23.8 KB
nocfbot-0001-rpr-explain-32bit-fix.patch application/octet-stream 4.2 KB
nocfbot-0005-cycle-detection-bitmap.patch application/octet-stream 6.9 KB
nocfbot-0002-prev-next-define-only.patch application/octet-stream 4.2 KB
nocfbot-0004-reluctant-quantifiers.patch application/octet-stream 65.6 KB
nocfbot-0006-allow-a0-quantifier.patch application/octet-stream 5.7 KB

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Ashutosh Bapat 2026-02-24 01:30:21 Re: some validate_relation_kind() tidying
Previous Message Masahiko Sawada 2026-02-24 01:21:50 Re: Support logical replication of DDLs