Re: Row pattern recognition - Mailing list pgsql-hackers

Hi hackers,

This is the increment on top of v51.  It is 27 patches, named
nocfbot-XXXX-*.txt as before.

The fixed branch for this posting, which I will not rewrite, is:

  https://github.com/assam258-5892/postgres/tree/RPR-20260904

They apply on top of v51, in numeric order and with nothing else in
between.  The base is the cfbot branch's commit for it, ac0ac5c599e
"[CF 4460] v51 - Implement row pattern recognition feature", which
is the posted v51 series on master of 2026-09-02.

Each entry says what v51 does wrong and what the patch does about
it, and the tag in brackets says what kind of problem it is.  Four
of the 22 in the series proper give a wrong answer or a spurious
error on v51 today; with those in, no wrong answer we know of is
left standing, and what remains open is quality, set out under
"Known issues" at the end.

The four are:

  - 2001 a view over a join stops re-parsing once the other side
    acquires a column the DEFINE names
  - 2008 a DEFINE clause reads ungrouped columns under GROUP BY
  - 2010 a DEFINE clause takes a qualifier the pattern variable owns
  - 2012 a navigation argument reads a constant, not the target row

Numbering

Numbers are reissued whenever the base version changes.  These are
cut against v51; they do not continue the ones that went out on
08-26 against v50, where the same number names a different commit.

The bands are the ones the last posting set out:

  0XXX  put back what the series changed outside its own scope,
        or bring it level with a base that has moved
  1XXX  reviewed upstream, not yet absorbed into a version
        (empty -- v50 took all of it)
  2XXX  the series proper -- cleaned up, not yet reviewed upstream
  3XXX  my own lane, in progress (empty)
  4XXX  Jian's lane, in progress (empty -- it held what still had
        an open question or had just come in from his inbox, and
        everything that stood there has been settled and sits in
        2XXX now)
  9XXX  reproduces without RPR at all -- submitted separately

The empty bands stay reserved.

Apply order is the numeric order.

One note on authorship before the list.  Twelve of the 27 carry Jian
as the author -- he wrote them, I rebased them onto the series,
verified them and wrote the messages.  His are 2008 through 2019.

0XXX -- bring the series level with the base

  0001 Place pg_nodiscard ahead of the storage class in the RPR
       optimizer  [build]
       Seven forward declarations wrote "static pg_nodiscard
       List *".  The attribute has to come first, and cfbot's
       Windows MinGW job rejected them.  Move it in front of
       static, as the rest of the tree writes it.  I have no
       Windows environment here, so I expect cfbot to confirm it.

2XXX -- the series

  2001 Pin the column names a DEFINE clause references when
       deparsing  [wrong result]
       The standard gives the qualifier slot in a DEFINE clause to
       the pattern variable, so a column there is written bare and
       cannot be qualified with its table -- which is how the
       deparser resolves an ambiguous column everywhere else.  A
       view over a join whose DEFINE names a column of one side
       therefore stops re-parsing once the other side acquires a
       column of that name, and pg_dump output fails to restore.
       Pin the names a DEFINE clause reads instead: the newcomer is
       renamed to name_1 and declared in a column alias list, so
       the DEFINE reference goes on meaning what it meant.  This
       went out as wip-0001 on 08-31.

  2002 Evaluate an RPR DEFINE clause in the context reserved for it
       [leak]
       A context was built for the DEFINE predicate, but the
       evaluation never used it, so the predicate's scratch went to
       one that lives as long as the query.  That was an omission
       in writing the patch; my apologies.  Peak resident size over
       300k rows falls from 94MB to 18MB for a DEFINE that
       allocates.  No test: this shows up in resident size, which
       the regression suite does not observe.

  2003 Report the frame row pattern recognition needs, not the
       broken option  [diagnostics]
       Each guard named the option it caught, so a window with no
       frame clause was told about an option the query never wrote,
       and a frame that broke more than one rule was told about
       them one at a time.  Naming what is wrong without saying
       what is allowed leaves the user to guess.  The report now
       lists the frames row pattern recognition accepts, so the
       query can be corrected from it.  The set of accepted frames
       does not change.

  2004 Report a non-constant row pattern navigation offset as a
       syntax error  [diagnostics]
       Two guards enforce one rule -- a navigation offset must be a
       constant -- but reported it in two classes, one as a syntax
       error and the other as not implemented.  It is a restriction
       on what the offset may be, not a gap in what was built, so
       both report it as a syntax error now.  Only the class
       changes.

  2005 Blame the alternation when a glued quantifier token is
       followed by an Op  [diagnostics]
       A quantifier written against an operator with no space
       between them arrives as one token, handled by a trick rather
       than taken apart.  Nothing is known to go wrong in what the
       grammar accepts; the diagnostics are where it shows.  The
       report named a pair that is not a quantifier at all; it
       blames the alternation now.  Other spellings leave the same
       kind of ambiguity, and pulling this out as its own patch,
       done properly, may be the better answer later.

  2006 Settle one contract for the RPRPattern copy, out and read
       functions  [latent]
       The pattern node needs its copy, out and read written by
       hand, and the three disagreed with each other and with the
       header in three places.  For the values actually in use they
       agree, so nothing goes wrong today.  This makes them agree
       over the whole range the fields can represent, and states
       the contract in the header.

  2007 Correct two errors in the row pattern recognition
       documentation  [docs]
       One clause was described in the wrong synopsis, and a note
       said that exceeding one limit raises an error where the
       limit named beside it raises one too and does not say so.
       Both are corrected.  The documentation, the comments and
       README.rpr may want a review round of their own once the
       code is settled; this posting does not attempt that.

  2008 Let a row pattern DEFINE clause take part in grouping
       [wrong result]
       GROUP BY restricts which columns a query may name, and
       makes a grouped expression readable only through its
       result.  The DEFINE clause was left out of that
       substitution, so it went on reading the ungrouped columns.
       Cases needing no substitution happened to work; a grouping
       set that can null a column failed outright.  ISO/IEC
       19075-5 6.4 puts the row pattern input table after GROUP BY,
       so this is a shape the feature owes.  The substitution is
       carried through DEFINE now, the deparser included, so a view
       over grouped input still re-parses.  More usage patterns are
       worth testing than the ones covered here.

  2009 Let an unreferenced RPR window and its DEFINE columns be
       removed  [plan shape]
       A window whose function nothing reads is dropped when the
       subquery is planned.  Row pattern recognition had been made
       an exception, and should not have been.  What changes:

       - a window is no longer kept alive merely because it
         carries a DEFINE clause; that premise was false
       - which windows survive is decided in this same pass, so
         the window functions are settled first and the set is
         read from what they leave
       - a dropped window's DEFINE clause is withdrawn with it,
         being the one place a window clause owns an expression
         tree

       The window clause itself stays in the list, so indexes into
       it do not move.

  2010 Reject whole-row references and qualified names in a DEFINE
       clause  [wrong result]
       ISO/IEC 19075-5 6.5 gives the qualifier slot in a DEFINE
       clause to the pattern variable, so nothing else may occupy
       it.  Two gaps let something else through:

       - a bare relation name was accepted and produced a
         whole-row reference, which has nothing to resolve
         against there
       - ROW(t.*) was expanded before either check saw it, and a
         view written that way cannot be restored

       Both are rejected now, and the rule widens to every
       qualified name.  Nothing becomes unreachable -- unqualified,
       each of them still resolves -- and a name resolved by a hook
       that answers before the parser never reaches this rule at
       all.  The checks also moved to where the reference has
       resolved, so a mistyped column keeps the hint it gets
       everywhere else.

  2011 Simplify the RPR pattern grammar actions with castNode
       [cleanup]
       Two grammar actions tested the node type before reading it
       and wrapped the value when the test failed.  The test cannot
       fail.  Take the cast instead.  No grammar rule or precedence
       changes.

  2012 Do not substitute a row-independent value into a navigation
       argument  [wrong result]
       Subquery pull-up substitutes the constant a one-row
       subquery's column stands for.  Inside a navigation argument
       it must not: PREV and its kin read the argument at another
       row, where the column is not the constant this row gave.
       That substitution is the defect, and it is what this
       corrects.  Constant folding only surfaced it -- with the
       column gone nothing stopped the fold, so PREV(v / 0) over a
       one-row VALUES read 10 / 0 and raised while planning, where
       execution, finding no target row, never divides.  The
       folding pass is not at fault and is unchanged.

  2013 Have the RPR executor read its own state instead of being
       handed it  [cleanup]
       A bundle of small refactorings:

       - values the executor already holds were computed by the
         caller and passed down; they are read where they are
       - a helper took one context and left the guard and the walk
         to each of its callers; it does both itself now
       - a function with no caller left, and a free path that
         cleared three fields where it should clear all
       - a classification whose cascade order carried the meaning;
         it tests the recorded row first instead
       - an early exit for the case that was wrapping the other
       - assertions that re-derived what had just been enforced

  2014 Name the RPR NFA helpers for what they do and assert what
       they assume  [cleanup]
       - two helpers named neither their subject nor their
         effect; renamed
       - one of them did a second job that belonged to its
         caller; moved out
       - three assumptions carried in comments become assertions,
         and two unreachable NULL branches go

  2015 Name the RPR quantifier tests instead of spelling them out
       [cleanup]
       - two functions made the same quantifier decisions, one
         through local booleans and the other written out by
         hand; the tests get names in the header, so both ask the
         same question
       - two of those differ only in < versus <=, which is the
         reason to name them rather than merge them

  2016 Pass elements, not indexes, through the absorbability walk
       [cleanup]
       - three functions took an element index, and one a scope
         depth with it, which every caller had to keep
         consistent; they take the element now
       - that exposed an assumption one of them rested on, which
         holds by test rather than by luck now

  2017 Drop the redundant origin and collation marking of a DEFINE
       clause  [cleanup]
       Two calls at the end of DEFINE parse analysis do nothing
       the clause needs, and both go:

       - one fills in fields only a SELECT targetlist or a
         RETURNING list uses
       - the other repeats work a later pass does anyway

  2018 Report an EXCLUDE clause on its own, not as a frame shape
       [diagnostics]
       - EXCLUDE was listed among the frames 2003 reports as
         accepted, but it modifies a frame rather than being one;
         it gets a report of its own
       - that report is raised after the shape has been settled,
         so a query breaking both is told about the shape first,
         which has to be rewritten either way
       - the remaining message carries its frames as parameters,
         so a translator is not asked to reproduce SQL syntax

  2019 Reset the DEFINE evaluation context where the predicate runs
       [cleanup]
       - the context was reset in two places away from the
         predicate it belongs to, correct only because nothing
         allocated across those boundaries; it is reset
         immediately before the predicate now
       - one function is renamed to the verb it actually performs

  2020 Bring README.rpr level with the code it describes
       [comments]
       Read from the code back to the document, the README was
       wrong in eighteen places and silent about more:

       - the wrong ones had mostly outlived the code they
         described
       - what the feature asks of the planner had never been
         written down, nor anything about the two printers that
         display a pattern; those are two new chapters, appended
         so no existing number moves
       - eight more sections fill gaps inside the existing ones

  2021 Record which WindowClause field answers "is this a row
       pattern window"  [comments]
       Three fields are set together at parse analysis, so any of
       them looks like the marker for a row pattern window.  The
       planner does not keep them so: 2009 empties defineClause
       alone.  The header now says to test rpPattern, and what an
       emptied defineClause beside it means -- the clause will not
       run.  Comment only.

  2022 Mark two costs the RPR engine carries on purpose
       [comments]
       Two limitations the series carries knowingly met nothing
       at the code, and README.rpr said the opposite at both:

       - states are compared exactly where nothing above the
         lower bound is read, so two with the same future stay
         apart and a branching unbounded pattern piles them up:
         (A{2,} B)+ C with C never true takes 30 ms over 80 rows,
         37 s over 320, and does not finish over 640
       - the frontier row and the navigation target share one
         read pointer, so once the tuplestore spills each drags
         the other back: PATTERN (S A+) DEFINE A AS v >= FIRST(v)
         over 8000 rows takes 2.6 ms in memory and 24.3 s at
         work_mem 64kB

       The answers do not change and no code does.

9XXX -- reproduces without row pattern recognition

  These four are here because they sit on the branch, not because
  they belong to this feature.  Each should go out as its own
  submission with its own commitfest entry, and none should wait on
  this one.

  9001 Add EXCLUDE TIES window frame test coverage  [coverage]
       Working on the row pattern code turned up window frame
       cases the existing tests do not reach: nth_value() has no
       EXCLUDE TIES coverage at all, and last_value() has it only
       over frames that contain the current row.  One query for
       each.  Coverage of this kind belongs with the window tests
       rather than the RPR ones, and I am collecting whatever else
       turns up to propose as a patch of its own.

  9002 Keep column names of relation RTEs outside the FROM clause
       unchanged  [wrong result]
       An unnamed FULL JOIN USING makes the USING name unique
       across the whole query, and that was applied to relations
       the deparser never prints -- a rule's NEW and OLD, and the
       target of an UPDATE or DELETE -- which have nowhere to
       declare a renamed column:

         CREATE TABLE t1 (x int, y int);
         CREATE TABLE t2 (x int, z int);
         CREATE TABLE t3 (x int, w int);
         CREATE TABLE log (x int);

         CREATE RULE r AS ON UPDATE TO t1 DO ALSO
           INSERT INTO log
             SELECT g.y FROM t1 g, t2 FULL JOIN t3 USING (x)
             WHERE g.x <> new.x;

       g is in the FROM clause and can take an alias list, so it
       deparses as g(x_1, y).  new cannot, and deparsed as new.x_1
       all the same, so pg_dump output dropped the rule on
       restore, reporting only

         ERROR:  column new.x_1 does not exist

       This reproduces without row pattern recognition and goes
       out as its own patch.  It came out of writing 2001, which
       only widens the way in.

  9003 Retry open() when it fails with EINTR  [wrong result]
       POSIX allows open() to fail with EINTR and macOS returns
       it, but only under heavy file I/O -- ordinary use never
       sees it, and every occurrence here followed a macOS 26.6.1
       update.  We did not retry, so the failure surfaced far from
       its cause: a file initdb should have created was missing,
       or a parallel query crashed while starting its workers.
       Add pg_open(), which retries, and use it in place of open()
       through the backend, frontend and port layers.

  9004 Put two typedefs.list entries back in sorted order
       [cleanup]
       typedefs.list is otherwise in byte order.
       JsonTablePlanJoinType went in after JsonTablePlanState, and
       PgStatShared_Index ahead of PgStatShared_IO, which reads as
       alphabetical only under a case-insensitive comparison the
       rest of the file does not use.  The file then agrees with
       LC_ALL=C sort throughout.

Known issues

  What remains is quality, not correctness.  Nothing below gives a
  wrong answer, and as far as we have been able to find that class
  is now empty: what stands is performance, an optimization not
  applied, and one legitimate query refused.

  One patch leaves an item of its own.  2010 refuses every
  qualified name in a DEFINE clause, including a function
  parameter written as f1.thr, which v51 accepts and which still
  works unqualified.  Where such a name collides with a pattern
  variable, the hook's reading wins.  The detail goes in a posting
  of its own.

  What no patch here carries, and what has to be settled before the
  feature is committed, comes to this.  None of it gives a wrong
  answer, and each is worth a patch of its own rather than a line
  here:

    - to keep preferment from returning wrong answers the cycle
      detection was narrowed to where it hardly fires, and a
      repetition over a nullable body explodes.  A bound on the
      states held is the first answer; refusing such a pattern, as
      Oracle does with ORA-62513, is the alternative
    - the frontier row and the navigation target sit far apart in
      the partition and share one read pointer, so once it spills
      each access walks between them.  A pointer each removes the
      walk, but one buffer still serves them all, so every switch
      re-reads a block.  Keeping the last n blocks read, with n
      taken from the pattern and the data, would close it
    - the run condition is off wherever a DEFINE is present, even
      for window functions that do not depend on the frame
    - a DEFINE expression refuses every subquery, where the
      standard allows one that neither does row pattern
      recognition itself nor reads an outer pattern variable

Best regards,
Henson