Re: Row pattern recognition

Hi hackers,

This follows the ten-patch increment on top of v53 that I posted for
row pattern recognition (RPR, SQL:2016 R020, CF 4460) in the thread
"Row pattern recognition" [1]. Patches 0001 and 0004 change planner
code in places that are not specific to RPR, so this mail explains
them for readers who know the planner but not RPR.

What the planner needs to know about RPR is small. A window clause
can say

WINDOW w AS (ORDER BY id
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (A+ B)
DEFINE A AS price > PREV(price), B AS price < PREV(price))

DEFINE gives each pattern variable a boolean expression over rows, and
PREV, NEXT, FIRST and LAST evaluate their argument at another row.
The expressions are held in WindowClause.defineClause. The WindowAgg
evaluates them, but they are not in the target list and not quals of
any scan, so the code that works out which columns the plan has to
provide never asks for what they read.

The patches are the nocfbot-0001 and nocfbot-0004 files attached to
[1]. The same commits are in
https://github.com/assam258-5892/postgres/tree/RPR-20260930, on top of
v53. Nothing here is meant to change what a query without a DEFINE
clause does, and neither patch changes an existing expected output
outside the rpr_base and rpr_integration tests.

What the patches do

The first five changes come from one idea. A DEFINE clause is an
expression that does not sit where the planner normally looks, the
target list and the quals, so the planner handles the query without
knowing it is there. The main line is to treat DEFINE as one more
consumer of the query's columns, the way HAVING is. HAVING does two
things that matter here. It makes the node below supply what it
reads, even though the target list does not mention it. And an
expression that GROUP BY already computed is read as the computed
value, not computed again from the base columns. A DEFINE clause is
evaluated by the WindowAgg on top of its input in the same way, so it
needs both. Three things follow:

- The planner has to find out which columns DEFINE reads and carry
them down to the window's input. Where the input already computes
an expression, such as a GROUP BY expression, DEFINE reads that
computed value instead of computing it again (1, 2).

- Every step in which the planner rewrites the query's expressions
has to treat DEFINE the same way, or its copy drifts out of step
with the rest. Grouping is the main case: an expression used in
GROUP BY is first replaced by its computed value and later
restored to the expression, and DEFINE has to go through both (2).
Subquery pull-up and join alias expansion are rewrites of the same
kind, with one exception: a navigation argument is evaluated at
another row, so it has to stay an expression over the row and must
not be folded into a constant (3).

- A window that will not run should be dropped like any plain
window, and its DEFINE must not stand in the way of other
optimizations (4, 5).

The last item (6) is a separate crash fix that does not follow from
this line.

1. DEFINE is handled like havingQual (0004).

Before, parse analysis added the Vars a DEFINE clause reads to the
target list as resjunk entries. That rewrote the user's target list,
and it was not enough. When a composite value arrives through a
pulled-up subquery, eval_const_expressions() splits an IS [NOT] NULL
test on it into one test per field. If the window's PARTITION BY or
ORDER BY holds the same value, its sortgroupref keeps the input target
from flattening it, so those fields never reach the WindowAgg input
and planning fails with "variable not found in subplan target list".

Now the patch asks for the columns in two places. The planner records
for each column how far up the join tree it is needed (attr_needed),
and a join relation puts on its output only what is still needed above
it. A DEFINE clause is in neither the target list nor any qual, so
nothing asked for what it reads, and a join could drop it on the way.
build_base_rel_tlists() now marks those columns as needed at the top
of the join tree, so they climb through the joins like the target
list's own columns. The upper planner, however, builds the target of
each node explicitly instead of propagating attr_needed, so each
target above the join tree has to ask for them again, and for the
window's input that is the next step.

make_window_input_target() adds to the window input target whatever
the preprocessed clause reads that the target does not already offer.
The walk stops at an expression the target computes whole, since
setrefs.c resolves the DEFINE copy against that column. Each DEFINE
condition is preprocessed as a qual, as havingQual is, and the
parser's Var planting is gone. In EXPLAIN VERBOSE a column that only
a DEFINE clause reads now appears on the WindowAgg's input but no
longer on its output.

2. Grouped input (0001, and a part of 0004).

parseCheckAggregates() rewrote only the target list and HAVING, so
over grouped input a DEFINE clause kept plain relation Vars while the
target list copies of the same columns became Vars of the RTE_GROUP
RTE. Plain GROUP BY hides this, but a grouping set that nulls a
column the DEFINE clause reads makes the two copies disagree in
varnullingrels, and setrefs.c fails:

CREATE TABLE t (category text, val int);
SELECT category, count(*) OVER w FROM t GROUP BY ROLLUP(category)
WINDOW w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (A) DEFINE A AS category IS NOT NULL);
ERROR: wrong varnullingrels (b) (expected (b 2)) for Var 1/1

ISO/IEC 19075-5 6.4 makes the row pattern input table the result of
FROM, WHERE, GROUP BY and HAVING, so this shape has to work.
defineClause now goes through the same steps as the target list:
substitute_grouped_columns() in parseCheckAggregates() (after
flatten_join_alias_for_parser() when there are joins, so that the
merged column of a FULL JOIN USING matches its grouping item), and
flatten_group_exprs() in subquery_planner() and in get_query_def().
GROUPING() cannot appear in DEFINE, so finalize_grouping_exprs() is
not needed. 0004 also lets a DEFINE clause spell a GROUP BY
expression: under GROUP BY val + 1, one repeating val + 1 used to
offer the bare val to the grouping check and was rejected.

3. A navigation argument stays row-dependent (0001 and 0004).

The argument of PREV, NEXT, FIRST and LAST is evaluated at the row the
navigation lands on. Pulling up a one-row VALUES list, a subquery or
a function RTE that folded to a constant replaced the column with that
value, and constant folding then raised at plan time an error that
execution would not reach on the row the navigation misses. The
example is PREV(v / 0) with no previous row.

replace_rte_variables_mutator() now flags the argument of an
RPRNavExpr, and pullup_replace_vars_callback() treats a replacement
made there as needing a PlaceHolderVar, so a replacement that does not
read the row is wrapped instead of folded in; whether one that reads
the row is wrapped is left to the usual pull-up rules (a plain Var or
a strict expression over Vars is not) (0004). A USING column whose
merged value is an expression, as in a FULL JOIN or when one side has
to be converted to the common type, resolves to the join's alias Var,
and flatten_join_alias_vars_mutator() could copy a pulled-up Const
into the argument the same way, so it flags the argument too. It is
stricter, though: in planner calls it wraps any replacement other than
a plain Var or PlaceHolderVar, including a strict expression over Vars
such as the implicit cast (0001).

4. remove_unused_subquery_outputs() is back to its upstream form
(0004).

It refused to replace an unused window function output whose window
had a DEFINE clause, and kept every bare-Var output that a DEFINE
clause read. Neither is needed. select_active_windows() makes no
such exception, and with the tracking in 1 a DEFINE clause reads a
relation column of its own query level, never the subquery's output
entry. A row pattern window in a subquery that nothing reads is now
removed with its WindowAgg, like a plain window.

5. The DEFINE clause of a window that will not run is emptied (0004).

grouping_planner() empties defineClause of every window clause that
will not run, right after select_active_windows(). For a subquery
that is when the subquery is planned, before its own join removal.
The reason is that 1 marks what a dead clause reads as needed, which
makes join removal keep the join, and query_tree_walker() visits
defineClause while join removal requires that no Var of a removed
relation remain anywhere in the tree. An outer join to a relation
that only such a clause reads can now be removed. Only defineClause
is cleared: winref indexes windowClause, so the clause itself must
stay, and rpPattern is what marks it as a row pattern window, which
find_window_run_conditions() and optimize_window_clauses() rely on. A
comment in query_tree_walker() records the rule.

6. A crash on a navigation offset (0004).

A navigation offset spelled like an expression the window input
already carries, such as a window ORDER BY key, crashed.
fix_upper_expr() replaced the offset with a reference to that input
column, and the executor, which resolves offsets once per scan before
any input row is read, dereferenced a null slot.
fix_upper_expr_mutator() now handles RPRNavExpr itself and fixes the
offsets with fix_scan_expr(), as set_plan_refs() does for the frame
offsets of the WindowAgg.

What I would like to hear

I found these places test by test, so I cannot rule out cases the
tests do not reach. I would value a look from anyone who knows these
functions, and three questions in particular:

- Is flagging the argument in the two mutators,
replace_rte_variables_mutator() and
flatten_join_alias_vars_mutator(), and wrapping a replacement in a
PlaceHolderVar the right way to keep a navigation argument
row-dependent, or is there a better place or a mechanism I should
use instead?

- Is it acceptable to empty defineClause in grouping_planner() so
that join removal sees no stale Var, rather than teaching
query_tree_walker() or join removal to skip it?

- Is there a case of an expression that the walk over what DEFINE
reads handles wrongly when DEFINE is treated like havingQual? I
know of one already: a column that only DEFINE reads, below
GROUP BY, is not asked for by the grouping input.

[1]
https://postgr.es/m/CAAAe_zDsYugq506ou49PU+Ok+4Umn5n59Qs5wYofvKyfEpvZJQ@mail.gmail.com

Best regards,
Henson