Re: Row pattern recognition

Attached is v54 RPR patches.

V54 includes many bug fixes and enhancements by applying 10 patches
[1] on top of v53.

[1] https://www.postgresql.org/message-id/CAAAe_zDsYugq506ou49PU%2BOk%2B4Umn5n59Qs5wYofvKyfEpvZJQ%40mail.gmail.com

Brief introduction to incremental patches cited from [1] below. More
details can be found in [1].

0001 Let a row pattern DEFINE clause take part in grouping
[wrong result]
v53 left DEFINE out of the GROUP BY substitution, so a grouping
set that nulls a column made setrefs.c fail with "wrong
varnullingrels". DEFINE now goes through the same steps as the
target list. Also fixes PREV(k / 0) failing at plan time when
k is a USING column of mixed types.

0002 Tighten parse analysis of DEFINE clauses and row pattern
syntax [wrong result]
Whole-row references, ROW(t.*), names qualified by a function
name or block label, and the FILTER or ORDER BY of an aggregate
got around the qualifier rule of ISO/IEC 19075-5 6.5. They
are rejected now, and a few SQLSTATEs change.

0003 Fix DEFINE memory leak and empty-iteration looping in RPR
executor [wrong result]
An empty first iteration kept a derivation the standard
excludes, so some patterns matched different rows than Perl;
query results change for such patterns. Also fixes the DEFINE
memory leak (94MB down to 18MB on 300k rows) and adds an
interrupt check.

0004 Move DEFINE input tracking from parse analysis to the planner
[wrong result]
Parse analysis planted DEFINE's Vars in the target list, and
planning could fail with "variable not found in subplan target
list". DEFINE is now handled the way havingQual is. Also
stops subquery pull-up from folding a navigation argument, and
fixes a crash on a navigation offset.

0005 Make a deparsed DEFINE clause re-parse as written
[wrong result]
A view holding a DEFINE clause could not be dumped and restored
once another column carried the same name. The names DEFINE
reads are now settled first and reserved. Also changes
pg_get_viewdef() output for some queries without row pattern
recognition; the commit message lists them.

0006 Tighten RPRPattern node I/O and reuse existing helpers in RPR
code [latent]
A malformed node string now fails with an internal error
instead of being misread. Existing helpers replace
hand-written code.

0007 Record two RPR costs and correct comments the code no longer
matches [comments, asserts]
Comments, plus five checks the executor cannot reach, now
Asserts: two elog(ERROR) calls and three early returns.
Records two known costs as XXX: the state comparison in
nfa_states_equal(), and nav_winobj's shared read pointer.

0008 Tidy and extend the row pattern recognition regression tests
[tests]
Tests only: rpr_ prefixes, fewer redundant ORDER BY, new tests,
and fixes for tests that tested less than their comments said.

0009 Bring the row pattern recognition documentation up to date
[docs]
Documentation only: SGML and README.rpr checked against the
code.

0010 Reorder README.rpr by processing order [docs]
Moves the chapters into the order a query goes through the
code: parsing, DEFINE planning, PATTERN compilation, the
executor, the worked example, deparse and EXPLAIN, and the
summary last. Text moves; section numbers and cross references
follow, and the Chapter IV title is reworded.

The series of patches are to implement the row pattern recognition
(SQL/RPR) feature. At present the implementation is a subset of
SQL/RPR (ISO/IEC 19075-2:2016). Namely, implementation of some
features of R020 (WINDOW clause). R010 (MATCH_RECOGNIZE) is out of the
scope of the patches.

Currently following features are implemented in the patches.

- PATTERN
- PATTERN regular expressions (+, *, ?)
alternation (|), grouping () , {n}, {n,}, {n,m}, {,m}
reluctant quantifiers (*? etc.),
Empty pattern ("PATTERN ()") are not permitted by the standard
Anchors (^, $) are not permitted in R020 by the standard
- DEFINE
- INITIAL
- AFTER MATCH SKIP TO PAST LAST ROW
- AFTER MATCH SKIP TO NEXT ROW
- Row pattern navigation (FIRST, LAST, PREV, NEXT and their compound forms)

Currently following features are not implemented in the patches.

- MEASURES
- Pattern variable name qualified column reference (e.g. A.price)
- SUBSET
- SEEK
- AFTER MATCH SKIP TO
- AFTER MATCH SKIP TO FIRST
- AFTER MATCH SKIP TO LAST
- PATTERN regular expression {- and -}
- PERMUTE
- CLASSIFIER

Author: Tatsuo Ishii <ishii(at)postgresql(dot)org>
Author: Henson Choi <assam258(at)gmail(dot)com>
Author: jian he <jian(dot)universality(at)gmail(dot)com>
Reviewed-by: Vik Fearing <vik(at)postgresfriends(dot)org>
Reviewed-by: Jacob Champion <jchampion(at)timescale(dot)com>
Reviewed-by: Peter Eisentraut <peter(at)eisentraut(dot)org>
Reviewed-by: NINGWEI CHEN <chen(at)sraoss(dot)co(dot)jp>
Reviewed-by: "David G. Johnston" <david(dot)g(dot)johnston(at)gmail(dot)com>
Reviewed-by: Chao Li <li(dot)evan(dot)chao(at)gmail(dot)com>
Reviewed-by: SungJun Jang <sjjang112233(at)gmail(dot)com>
Reviewed-by: Zsolt Parragi <zsolt(dot)parragi(at)percona(dot)com>
Reviewed-by: SeongJun Shin <<shinsj4653(at)gmail(dot)com>

Discussion: https://postgr.es/m/20230625.210509.1276733411677577841.t-ishii%40sranhm.sra.co.jp

Regards,
--
Tatsuo Ishii
SRA OSS K.K.
English: http://www.sraoss.co.jp/index_en/
Japanese:http://www.sraoss.co.jp