Re: Row pattern recognition

Hi Jian,

Thanks for v51. v51-0001 fixes the loss of forward reach for FIRST(expr,
n > 0). That regression was my reason for saying the nav-offset
consolidation should not go in now, so that ground is gone. I will go on
with the review of the series.

Let me put the conclusion first, though. The trouble is not the
consolidation itself but the premise it rests on. There are several
defects in the same place, and the consolidation does not remove them --
it changes what they do, from fail-closed to fail-silent. So rather than
keeping the consolidation apart, I would like to bundle it together with
the related defects and fix them as one. Then it becomes a safe change
and can go into this patchset -- which is where you wanted it.

A word on approach. Neither refactoring for its own sake, nor fixing one
defect at a time as each one turns up, fits where we are. I would rather
we put every defect we have found so far side by side, analyze them
together, and improve towards a single design that resolves all of the
cases at once. Otherwise we keep touching the same place over and over,
paying the review and verification cost again each time. I hope you will
read what follows in that light.

From the verification I have run, the basic idea of the navigation code
looks sound. What it needs now is to be verified against a wider range
of cases and improved from there. I would like you to take ownership of
that area and work it through together with the design, over a broader
scope than a single patch.

For my part: I will verify it from a QA angle first -- building cases,
running them, collecting the failures -- and once it is close to
finished, go over it again in a line-by-line code review.

I have grouped what follows by patch, so it is visible which defect
touches which one.

Background

Today an offset is used in two places, for two different jobs.

* eval_define_offsets() resolves it once, in ExecInitWindowAgg, to
fill in the trim metadata (navMaxOffset / navFirstOffset). That
decides how far back rows are kept: advance_nav_mark() sets the
mark position from it, and everything before that is released.

* The actual navigation target is decided per row, by
ExecEvalRPRNavSet() evaluating the offset expression. That decides
which row we go to.

That split is what keeps the failures below fail-closed. When the two
disagree, we end up asking for a row that has already been released, and
the mark-position check in window_gettupleslot() catches it before any
tuplestore read. The "cannot fetch row: 0 before WindowObject's mark
position: 1" in the defect 1 reproducer is exactly that: init read a 0,
decided it would never look back, and released the row that the per-row
evaluation then went looking for. Nothing comes back silently wrong.

So the redundancy is the safety net. And all of it stands on one
premise: an offset has a value by the time it is resolved. That premise
is already false today.

================================================================
1. The nav-offset consolidation
v50-0001-Evaluate-navigation-offset-once-at-one-place
v50-0002-Drop-the-shared-nav_traversal_walker-for-RPR-DEFINE
v51-0001-Fix-the-regression-failure
================================================================

I applied it on our tree and checked. As your commit message says, every
offset is evaluated at init and stored, and ExecEvalRPRNavSet() only
reads those int64 values. So the per-row evaluation is gone, and the
value frozen at init decides the actual navigation target.

With the two collapsed into one, there is nothing left to disagree with.
The mark check can no longer fire on an offset mismatch -- it only fires
now if the trim metadata itself is wrong (see defect 5) -- and a wrong
init value picks the target row unchallenged. The safety net comes off.

That carries the premise above straight into the results. Running the
reproducer of defect 1 below, as is:

offset correct baseline with the patch
------ -------- ---------------- -------------------
n = 1 0,9,... 0,9,... (right) 0,0,... (silently wrong)
n = 2 0,0,8,. internal elog 0,0,... (silently wrong)
n = 3 0,0,0,7 internal elog 0,0,... (silently wrong)

All three return the answer for f(0), because the 0 read at init now
decides where PREV points. No error, no warning. Two things get worse at
once: what was fail-closed for n >= 2 becomes fail-silent, and n = 1,
which was *right* on the baseline, becomes wrong.

Five defects sit at this spot; the series already resolves one of them.

Defect 1 -- a nav offset taken from a function or lateral argument

CREATE TABLE d(v int); INSERT INTO d SELECT generate_series(1,10);
CREATE TABLE t(x int8); INSERT INTO t VALUES (2);
CREATE FUNCTION f(n int8) RETURNS TABLE(cnt bigint)
LANGUAGE sql STABLE AS $$
SELECT count(*) OVER w FROM d
WINDOW w AS (ORDER BY v ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING PATTERN (A+)
DEFINE A AS v > PREV(v, n)) $$;

SELECT * FROM f(2); -- fine: the third row is 8
SELECT * FROM t, f(t.x); -- ERROR: cannot fetch row: 0 before
-- WindowObject's mark position: 1

A query that works when called directly turns into an internal error
once it is inlined and its argument comes from another FROM item.

Whether this happens depends on where the offset value comes from. A
bind parameter (PARAM_EXTERN, $1) is fine: ExecInitWindowAgg runs again
on every execution, and by then the value is there, so even with a
generic plan forced, EXECUTE returns the right answer.

The trouble is with the other kind of parameter. Function-RTE inlining
and lateral references plant a PARAM_EXEC in the nav offset, and that
one has no value yet at init and changes from one outer row to the next.
Executor init freezes the still-unset param as a constant 0, and nothing
re-evaluates it on rescan.

Two neighbours already show the right way. LIMIT/OFFSET calls
recompute_limits() again on rescan, and the frame offsets are evaluated
during execution by calculate_frame_offsets(). The nav offset alone is
frozen once at init and never revisited.

Defect 2 -- EXPLAIN (GENERIC_PLAN) fails on a parameter offset

EXPLAIN (GENERIC_PLAN, COSTS OFF)
SELECT count(*) OVER w FROM generate_series(1,5) g(v)
WINDOW w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (A+) DEFINE A AS v > PREV(v, $1));
-- ERROR: no value found for parameter 1

No user-defined function is involved; this is plain SQL. The same query
returns the right answer when run with EXECUTE. It only fails when you
ask to see the plan: eval_define_offsets() evaluates the offset without
looking at EXEC_FLAG_EXPLAIN_GENERIC.

This one collides with the consolidation head-on. The consolidation
relies on ExecInitWindowAgg being reached for EXPLAIN in order to print
concrete offsets instead of "runtime". But the fix here is to put an
EXEC_FLAG_EXPLAIN_GENERIC guard at that very call, skipping the
evaluation -- the way execPartition.c already skips execution-time
pruning for a generic plan. On today's tree the two fit together: the
kind stays NEEDS_EVAL and EXPLAIN prints "runtime". After the
consolidation they do not. With the plan-node kind gone there is no
"unknown" left to print, so a guarded EXPLAIN would show "Nav Mark
Lookback: 0" -- a made-up number no reader can tell from a real 0.

Defect 3 -- the planner does not account for PARAM_EXEC in DEFINE

CREATE TABLE outer_t (threshold int);
INSERT INTO outer_t VALUES (10), (200);
CREATE TABLE stock (price int);
INSERT INTO stock SELECT g FROM generate_series(1, 100) g;

CREATE FUNCTION fn(th int) RETURNS SETOF bigint
LANGUAGE sql STABLE AS $$
SELECT DISTINCT count(*) OVER w FROM stock
WINDOW w AS (ORDER BY price ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING AFTER MATCH SKIP PAST LAST ROW
INITIAL PATTERN (a+) DEFINE a AS price > th) $$;

SELECT * FROM fn(10) ORDER BY 1; -- 0, 90
SELECT * FROM fn(200) ORDER BY 1; -- 0

-- DISTINCT is planned as a HashAgg here, and HashAgg rescan is gated
-- on chgParam, so the hash table built for the first outer row is
-- re-served for the second.
SELECT o.threshold, f FROM outer_t o, LATERAL fn(o.threshold) f
ORDER BY 1, 2;
-- now: 10|0 10|90 200|0 200|90
-- expected: 10|0 10|90 200|0
--
-- Both 200 rows are th=10's cached answer set {0, 90}; 200|0 only
-- coincides with the right value. Reversing the outer order makes it
-- plain: with outer_t as (VALUES (200),(10),(50)), every row gets
-- 200's answer -- 200|0 10|0 50|0
-- With SET enable_hashagg = off the plan becomes Sort+Unique and the
-- result is correct.

The argument is used only inside DEFINE, so once the function is inlined
the PARAM_EXEC appears only in defineClause. But the T_WindowAgg case of
finalize_plan() (the worker under SS_finalize_plan()) finalizes
startOffset and endOffset only, never defineClause, so that param is
missing from extParam and allParam. On rescan the chgParam signal
therefore never reaches the cache node above (here the HashAgg), which
re-serves the hash table built for the first outer row.

This looks like the plumbing root under the two above. If defect 1 is
"the value is not there yet", this one is "nobody notices the value
changed". Even with re-evaluation code in place, the signal that a
parameter changed would not arrive -- so the plumbing has to be laid
first.

The fix looks like one line: add a finalize_primnode() call for
defineClause to the T_WindowAgg case of finalize_plan(). I tried it, and
the stale row disappears with the RPR suites all passing.

Defect 4 -- the outer offset of a compound nav goes unvalidated
(the series resolves this one)

CREATE TABLE nav (id int, val int);
INSERT INTO nav VALUES (1,10), (2,20), (3,30);

-- inner in range: errors, as it should
SELECT id, count(*) OVER w FROM nav WINDOW w AS (
ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (A B+)
DEFINE A AS TRUE, B AS PREV(FIRST(val, 0), NULL::int8) IS NULL);
-- ERROR: row pattern navigation offset must not be null

-- inner out of range (offset 99): same illegal outer offset passes
SELECT id, count(*) OVER w FROM nav WINDOW w AS (
ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (A B+)
DEFINE A AS TRUE, B AS PREV(FIRST(val, 99), NULL::int8) IS NULL);
-- no error; rows are returned

Today ExecEvalRPRNavSet() validates the inner offset inline at the top,
unconditionally. The outer offset, by contrast, is validated only in the
helper rpr_nav_get_compound_offset() -- and all four compound arms
(PREV/NEXT over FIRST/LAST) break out with target_pos = -1, before that
helper is ever called, as soon as the inner position overflows or falls
outside the match range. The asymmetry is right there in
ExecEvalRPRNavSet(): one check inline and always run, the other
delegated to a callee the early exits skip -- and so the same illegal
query errors out or passes quietly depending on the data.

The series resolves this. The consolidation removes
rpr_nav_get_compound_offset() and lifts both the inner and the outer
offset into eval_nav_offset() at init, where the NULL/negative check
runs once, unconditionally, independent of any row. Both queries above
then error alike. Noting it as a point in the series' favour.

There is something worth pausing on here, though. Nobody knew about this
defect, no test observes it, and the patch was not written to fix it. It
just went away. The same is true of defect 5 below: nobody is watching
what that executor code does today.

If a defect we never knew about can vanish quietly, a defect we never
know about can appear quietly too. Same place, same blind spot. We were
lucky this time; there is no guarantee about the next. That is why I
would rather we sort the defects out and put a test on each of them
first, and lay the consolidation on top of that, than take the series as
it stands.

Defect 5 -- three NEXT_FIRST comments say the opposite of the code
right below them

This is the very code the patch rewrites. Three comments -- the
visit_nav_exec header, the NEXT_FIRST branch, and its planner twin in
visit_nav_plan -- state that "NEXT_FIRST's reach (inner+outer) is always
>= 0, so it never updates minFirstOffset / firstOffset (which track the
minimum)", while the code immediately below performs an unconditional
Min() update -- and that update is load-bearing. Two of the three -- the
visit_nav_exec header and the NEXT_FIRST branch -- are carried over
verbatim into compute_nav_offsets by v50-0001; the third disappears with
visit_nav_plan. After the consolidation the surviving Min() is the only
one left, so the comment sitting on top of it matters more, not less.

minFirstOffset starts at the sentinel PG_INT64_MAX. In a query where
NEXT_FIRST is the only FIRST-family nav, that Min() is the only path
that pulls the sentinel down to inner + outer. That value becomes
navFirstOffset and forms the lookahead bound in advance_nav_mark. (Today
the update exists twice, in visit_nav_plan for constant offsets and in
visit_nav_exec for runtime ones; after the consolidation only the
executor one is left.)

Remove the Min() trusting the comment, and navFirstOffset stays at the
sentinel: the overflow check in advance_nav_mark then trips, the
matchStart clamp is skipped altogether, the nav mark runs ahead, and
NEXT(FIRST()) fetches collapse with "cannot fetch row: N before
WindowObject's mark position: M".

The planner-side Min() is caught by the tests we have. Drop it and
rpr.sql's existing

DEFINE A AS TRUE, B AS NEXT(FIRST(val, 1), 1) > 0

case dies with "cannot fetch row: 2 before WindowObject's mark position:
3", and rpr_explain's "Nav Mark Lookahead: 3" turns into "infinite". So
the comments are not merely unhelpful -- two tests that already exist
contradict them.

Nobody is watching the executor-side Min(). Delete that one and all five
rpr tests still pass: constant offsets never reach visit_nav_exec, and
the two existing NEXT(FIRST($1),$2) tests that do reach it use overflow
offsets, where the PG_INT64_MAX clamp hides the difference. To pin it
down, the offset has to be decided at run time and not overflow.

SET plan_cache_mode = force_generic_plan;

CREATE TABLE t AS
SELECT g AS id, g AS v FROM generate_series(1, 200) g;

PREPARE p(int8, int8) AS
SELECT sum(cnt) FROM (
SELECT count(*) OVER w AS cnt
FROM t WINDOW w AS (
ORDER BY id
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
AFTER MATCH SKIP TO NEXT ROW
PATTERN (A+)
DEFINE A AS NEXT(FIRST(v, $1), $2) >= 0
)
) s;

EXECUTE p(0, 1); -- sum = 20099
EXECUTE p(0, 3); -- sum = 20094

-- with the executor-side Min() removed:
-- ERROR: cannot fetch row: 1 before WindowObject's mark position: 2

force_generic_plan is needed: under a custom plan $1 folds to a Const
and the query goes back through the planner path. Without a case like
this, nobody observes what that executor code and its comment are doing
to each other. The patch rewrites the code and carries the comments over
unchanged, and after the consolidation that copy is the only one left --
so this is the moment to correct them.

One more thing sitting in the same code

make_windowagg assigns node->defineClause = wc->defineClause with no
copy, so the WindowAgg plan node and the parse tree's WindowClause share
the same List header and cells; set_upper_references then writes
OUTER_VAR Vars back into those shared cells. After planning, the DEFINE
TLEs in parse->windowClause therefore carry plan-level structure.
Nothing misbehaves in SQL today -- no code reads it after planning, and
plancache always hands the planner a querytree it is free to scribble on
(a private copy; for a one-shot plan, a tree that is planned exactly
once and then thrown away) -- but it breaks list ownership. And
setrefs.c is inconsistent with itself here: the frame offsets and run
conditions are fixed up by assigning the result back into the plan
node's own field (wplan->startOffset = fix_scan_expr(...)), so the
WindowClause is never dragged along, while defineClause alone is fixed
up by overwriting the cells of a list the plan node does not own
(lfirst(l) = tle) -- which is also unlike the targetlist loop just above
it, which builds a brand-new list.

Where this leaves the series

v51-0001 fixes the loss of forward reach for FIRST(expr, n > 0), which
was my ground for rejecting. Taken. With the regression gone, I have no
reason to block the series either.

But unless it is bundled with the remaining four, it moves the broken
premise from the trim metadata to the actual result.

Also, the fix I had in mind for defect 1 -- classify an offset that
holds an exec param as retain-all at plan time, giving up trim -- cannot
be written on top of this patch: RPRNavOffsetKind, extract_const_offset
and visit_nav_plan are all gone, and disabling trim is now the
navMaxOffset < 0 sentinel. We need to settle the fix together.

================================================================
2. v51-0002-Stop-evaluating-navigation-arguments-in-case-rows-not-exists
================================================================

Defect 6 -- an out-of-range navigation evaluates its argument
(this patch fixes it)

CREATE TABLE t (id int, v int);
INSERT INTO t VALUES (1,10), (2,20), (3,30);

-- The first row has no PREV row, so by the standard the navigation
-- is null -> unknown -> the first row must not be mapped.
SELECT id, count(*) OVER w AS cnt FROM t WINDOW w AS (
ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
INITIAL PATTERN (A) DEFINE A AS PREV(v IS NULL));
-- now: first row cnt = 1 expected: 0

-- COALESCE behaves the same; NEXT does it at the last row.
SELECT id, count(*) OVER w AS cnt FROM t WINDOW w AS (
ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
INITIAL PATTERN (A) DEFINE A AS PREV(COALESCE(v, -1)) = -1);

An out-of-range target row is represented not as "there is no row" but
as an all-NULL fake row, and the argument is evaluated on it. So an
argument that looks at NULL directly -- IS NULL, COALESCE -- comes out
true and the row gets mapped. An argument insensitive to NULL (say
PREV(v) > 5) lands on the right answer, but only by accident.

I think both the direction and the implementation are right:
EEOP_RPR_NAV_SET writes a definitive resnull, and the following
EEOP_JUMP_IF_NULL skips the argument steps and lands on RESTORE. That
produces exactly the result the standard asks for. 19075-5 5.6.2 says
"If there is no previous row, the null value is returned", and spells
out the consequence -- "then PREV(A.Price) is null, so the Boolean
condition is not True, and therefore the first row cannot be mapped to
A". The standard mandates the result, not the evaluation strategy; but
skipping the argument is the only reliable way to get that result, since
an argument evaluated against an all-NULL row can turn the null into a
non-null value (IS NULL, COALESCE) -- and it also keeps a side-effecting
or erroring argument from running on a row that does not exist.

Defect 7 -- folding and pull-up erase the column reference in a nav
argument

This is what the clauses.c hunk of this patch touches.

There are two routes into it.

Folding -- written directly, the parser rejects it:

... DEFINE A AS PREV(true)
-- ERROR: argument of row pattern navigation operation must include
-- at least one column reference

Yet the same shape passes once folding has been through it. v > 1 OR
true folds to true, and no column reference is left in the navigation
argument.

... DEFINE A AS PREV(v > 1 OR true)

Pull-up -- the same logical query gives different answers depending on
the shape of the plan:

-- (a) a real table, one row
CREATE TABLE t (id int, v int);
INSERT INTO t VALUES (1, 10);
SELECT id, count(*) OVER w AS cnt FROM t WINDOW w AS (
ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
INITIAL PATTERN (A) DEFINE A AS PREV(v IS NULL));
-- now: cnt = 1

-- (b) a single-row VALUES -- the same query, and 0
WITH t(id, v) AS (VALUES (1, 10))
SELECT id, count(*) OVER w AS cnt FROM t WINDOW w AS (
ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
INITIAL PATTERN (A) DEFINE A AS PREV(v IS NULL));
-- now: cnt = 0

In (b), pull_up_simple_values() pulls the VALUES up and
pullup_replace_vars() substitutes v with the Const 10. No column
reference is left in the navigation argument, so 10 IS NULL is folded
away in advance. The answer depends on the plan shape.

One thing to add: with v51-0002 in, the difference in this query is
covered up -- there is no target row, so neither side evaluates the
argument and both give 0. But the substitution is still there, and the
invariant that arg must hold a column reference is still broken.

Parse analysis imposes opposite requirements on the two children (see
define_walker in parse_rpr.c):

- arg must contain at least one column reference
- offset_arg / compound_offset_arg must not contain column refs

The argument has to be evaluated on the target row, so it must keep a
column reference; the offset has to be a run-time constant, so it must
have none. The planner, however, treats them alike and const-folds all
of them recursively -- and so it produces what parse analysis would have
rejected: a navigation argument that does not depend on the target row.
There are more routes that erase the column reference than the
v > 1 OR true above: inline_function(), folding a CASE with a constant
condition, COALESCE(1, v) -> 1.

Pull-up happens earlier still, so clauses.c cannot even reach it. And
the same pull-up route can bypass the volatility check itself -- that is
defect 10 below.

Defect 8 -- a DEFINE predicate is evaluated every row even for a
variable no state ever tries to map

This is the principle of this patch, one level up.

CREATE TABLE t (id int, v int);
INSERT INTO t VALUES (1,1), (2,2), (3,3);

-- A is false at every row, so B is never tentatively mapped. By the
-- standard B's condition is evaluated at no row at all, and all three
-- rows come back unmatched (cnt = 0).
SELECT id, v, count(*) OVER w AS cnt FROM t WINDOW w AS (
ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (A B)
DEFINE A AS v < 0, B AS 1 / (v - v) > 0);
-- now: ERROR: division by zero expected: cnt = 0 on all rows

rpr_evaluate_row() evaluates every DEFINE predicate in defineClauseExprs
on every row, unconditionally. If the predicate of a variable that no
active NFA state tests at that row raises a runtime error, the whole
query dies.

ISO/IEC 19075-5, 4.16 DEFINE: "The Boolean conditions are evaluated on
successive rows of a row pattern partition in a trial match, with the
current row being tentatively mapped to a primary row pattern variable
PRPV as permitted by the pattern." The standard's matching procedure
therefore never evaluates B's condition here -- no row is ever
tentatively mapped to B -- and the result it defines for this query is a
clean "no match", cnt = 0 on every row. We evaluate a condition the
procedure never reaches, and a query with a well-defined result dies
with an error instead.

If v51-0002 says "do not evaluate the argument when there is no target
row", this says "do not evaluate the predicate of a variable you are not
even trying to map". Same grain. You have raised the short-circuit
yourself before, on exactly this shape -- PATTERN (A B) with A false. It
was framed as an optimization then; the case above shows it is also a
correctness question. Would you raise it as a formal item on the list?

Three requests

* Please split the T_RPRNavExpr case in clauses.c out of this commit.
As written it does not change behavior: expression_tree_mutator
already handles T_RPRNavExpr, and eval_const_expressions_mutator's
default path calls it. I would rather we analyze defect 7 first,
and take this up as a patch that actually fixes it.

* The all-NULL row in nav_null_slot is dead with this fix: its only
reader, ExecEvalRPRNavSet(), now returns early before installing the
slot into econtext, so the fake row is never evaluated against. The
slot serves only as an out-of-range sentinel now -- please have
ExecRPRNavGetSlot() return NULL instead and drop nav_null_slot.

* Two comments. (1) In ExecEvalRPRNavSet, "If the target row does
exist..." is followed by the code for the row *not* existing, and
the same sentence ends with a stray "1". (2) In ExecInitExprRec
(execExpr.c), "the EEOP_RPR_NAV_SET step has already stored a
nav_null_slot" is no longer true with this patch -- that step stores
nothing into econtext, it only writes a definitive resnull.

================================================================
3. v51-0003-Introduce-execution-struct-RprNavState
================================================================

You are right about the problem. Writing the resolved offsets onto the
RPRNavExpr in the plan tree goes straight against
src/backend/executor/README: "This arrangement allows the plan tree to
be completely read-only so far as the executor is concerned: all data
that is modified during execution is in the state tree. Read-only plan
trees make life much simpler for plan caching and reuse." Executor init
would be modifying a tree that is shared through CachedPlan. Moving them
into execution state is the right direction, the FOR PORTION OF
precedent fits, and the code reads clean. I would rather not rush a
verdict on it, though, and take the time to satisfy myself there is no
defect -- it sits right against the premise above, so it is worth the
care.

One thing to note: the rescan side of defect 1 survives this patch.
RprNavState moves the storage from the plan tree into execution state,
but it is still filled once in ExecInitExprRec, and ExecReScanWindowAgg
leaves the nav offsets alone -- so a PARAM_EXEC stays frozen. Seen the
other way, this structure gives us the place to hang that re-evaluation
on.

Two things I would like to settle while reading it.

* Naming. Everything in the tree is RPR* (RPRNavExpr, RPRNavKind,
RPRNFAState); only the new types are RprNavState / RprNavOffsets.

* The JsonExprState you cite is a plain struct with no NodeTag.
RprNavState carries a NodeTag and uses makeNode, claiming a new node
tag; if it is never used as a Node, a palloc would do, as in the
precedent.

================================================================
4. v50-0001-refactor-DEFINE-volatile-expression-check
(a patch I have not taken yet)
================================================================

Defect 9 -- the volatility gate only runs before folding

CREATE FUNCTION off_leak(n bigint DEFAULT (random()*5)::bigint)
RETURNS bigint LANGUAGE sql STABLE AS 'SELECT n';

SELECT count(*) OVER w FROM generate_series(1,100) g(v)
WINDOW w AS (ORDER BY v ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING PATTERN (A+) DEFINE A AS v > PREV(v,
off_leak()));
-- repeat it: ERROR: cannot fetch row: N before WindowObject's
-- mark position: M

In planner.c, validate_rpr_define_volatility() runs before
preprocess_expression(), so it never sees the volatile default argument
that folding splices in afterwards. The function's STABLE label is
honest: there is no random() in its body, and given its arguments it
returns the same value within a statement.

A default argument is not the only thing that enters DEFINE after the
gate has run. flatten_join_alias_vars can plant a volatile implicit cast
into the merged column of an outer JOIN USING by the same route. (An
inner join will not do: buildMergedJoinVar() prefers the uncoerced input
for JOIN_INNER, so no cast survives into the merged column.) And when it
lands in the DEFINE body rather than in an offset, there is no error at
all: the match simply differs from one execution to the next.

This is a defect you have already aimed at. As your commit message says,
that patch moves the check to after preprocess_expression(), following
contain_volatile_functions_after_planning. That closes the hole. I have
not taken the patch yet, and this defect is the argument for it.

A word on the symptom as well. With the offset evaluated in two places
today, the volatile value differs between them and trips the
mark-position check above. Once the consolidation is in, even that error
is gone and the answer quietly differs from run to run. Six runs of the
same query:

baseline 86, 88, ERROR, ERROR, ERROR, 90
with the patch 98, 97, 96, 99, 96, 96

One more thing bothers me here. EXPLAIN of that query prints "Nav Mark
Lookback: runtime" on the baseline and "Nav Mark Lookback: 1" with the
patch, while the offset actually ranges over 0..5 at run time. The error
goes away because the mark is no longer derived from the same evaluation
the navigation uses -- not because the value is right. Baking a constant
lookback out of an offset expression that is not constant may be worth a
look of its own.

So this one has to close before the consolidation, or along with it.

Defect 10 -- the gate is not merely late; some paths never reach it

CREATE TABLE t (id int);
INSERT INTO t VALUES (1), (2);

-- (a) at the top level it is rejected, as it should be
SELECT id FROM t
WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING PATTERN (A+) DEFINE A AS random() > 0.5);
-- ERROR: volatile functions are not allowed in DEFINE clause

-- (b) wrap it in a FROM subquery and it passes quietly
SELECT id FROM (
SELECT id FROM t
WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING PATTERN (A+) DEFINE A AS random() > 0.5)) s;

-- (c) control: OFFSET 0 blocks the pull-up, and the error is back
SELECT id FROM (
SELECT id FROM t
WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING PATTERN (A+) DEFINE A AS random() > 0.5)
OFFSET 0) s;
-- ERROR: volatile functions are not allowed in DEFINE clause

An EXISTS subquery and a UNION ALL leaf behave like (b).

validate_rpr_define_volatility() is called only from the windowClause
preprocessing loop in subquery_planner. But when the window is not
referenced by any OVER (hasWindowFuncs = false), the windowClause is
dropped before that loop ever sees it:

- pull_up_simple_subquery(): is_simple_subquery() gates on
subquery->hasWindowFuncs, not on windowClause != NIL, so the whole
subquery Query -- windowClause included -- is discarded on pull-up;
- simplify_EXISTS_query(): the same gate, then an outright
query->windowClause = NIL;
- a UNION ALL leaf reaches the first of these through
pull_up_union_leaf_queries() -> pull_up_subqueries_recurse().

So the same invalid DEFINE is rejected or quietly accepted depending on
the shape of the query: wrap it in a FROM subquery and the error goes
away.

Moving the check after preprocess_expression() does not close this on
its own. All three discards happen earlier in subquery_planner --
pull_up_sublinks(), pull_up_subqueries() and flatten_simple_union_all()
all run before the first preprocess_expression() call -- so the old
position and the new one iterate exactly the same, already-pruned,
parse->windowClause. The check has to be reachable, not just late. Worth
looking at together when we reopen that patch.

One thing to decide

You noted losing the error cursor position as a trade-off in the commit
message. That choice looks unavoidable to me, in fact. When
inline_function() in eval_const_expressions re-parses a SQL function's
prosrc and substitutes it, the substituted FuncExpr keeps a location
relative to the function body. Attach an errposition to that in a
post-fold check and the location is applied to the outer query, where it
points somewhere else entirely. So a post-fold check is better off
attaching no position at all.

But that is exactly why I would keep the pre-fold check. A post-fold
check cannot tell a node the user wrote from a node an inlined function
body brought in -- nothing on the node records which string its location
belongs to -- so it has to drop the cursor for every case, the plain
hand-written volatile included. Only the check before folding can still
point at it. The first for the position (errposition attached), the
second for correctness (errposition omitted) -- how about keeping both?

A policy call rides along with that. Do we accept a volatile in a dead
branch, as in CASE WHEN false THEN random()? A double check catches it
up front; a single post-fold check lets it through. I would like us to
settle which behaviour we want.

================================================================
5. v50-0002-refactor-define_walker
(another patch I have not taken yet)
================================================================

Defect 11 -- nav_count counts nav nodes, not nesting depth

DEFINE A AS PREV(FIRST(v) + LAST(v)) > 0
-- ERROR: cannot nest row pattern navigation more than two levels deep

Rejecting it is right. ISO/IEC 19075-5 5.6.4 describes the compound
operation only for the shape where FIRST / LAST is nested directly
inside PREV / NEXT -- as in PREV(LAST(A.Price + A.Tax, 1), 3) -- and its
evaluation procedure only makes sense for that shape: "The inner
operator, LAST, operates on the set of rows that are mapped to the row
pattern variable A ... The outer operator, PREV, starts from the row
found in step 1 and backs up 3 rows ... Let R be an
implementation-dependent range variable that references the row found by
step 2 [and] the resulting expression R.Price + R.Tax is evaluated". So
a complex expression belongs inside the innermost nav's argument, not
inside the outer one. (The normative Syntax Rules are in ISO/IEC 9075-2;
19075-5 is the explanatory TR.)

PREV(FIRST(v) + LAST(v)) is not that shape: the outer PREV's argument is
an arbitrary expression adding two navs. FIRST(v) and LAST(v) point at
different rows, so there is no row for PREV to back up from. 5.6.2
rejects PREV(1) with the same kind of reasoning -- "Without a column
reference or CLASSIFIER function, there is no way to determine the row
that is the starting point for offsetting." The argument above does have
column references, but two sibling navigations designate two different
rows, so there is still no single row for PREV to offset from.

The trouble is the diagnosis. There is no three-level nesting in that
input; it is two levels deep, with two sibling navs. But ctx->nav_count
counts every RPRNavExpr found anywhere in the outer nav's argument
subtree -- it keeps recursing -- so the count check fires before the
depth check. We reject it for a reason that is not true.

The error should state the actual rule: nav nesting is allowed only when
the inner nav is the direct argument of the outer one. That wording
already sits seven lines below -- "row pattern navigation operation must
be a direct argument of the outer navigation" -- and it does fire
correctly for the single-sibling PREV(v + FIRST(v)). Only this class
never reaches it. The HINT on the errmsg does list the four legal
compound forms, so the user is not left entirely without a clue -- but
the errmsg itself is still false.

This is the very walker your patch reworks. If we reopen it, I would
like the diagnosis fixed along the way.

And the point you make in that commit message -- that "must be a
run-time constant" looks wrong, since the offset can be a plpgsql STABLE
function -- is the same question as defect 1: is an offset that comes
from a function argument or a lateral argument a run-time constant? That
answer sets the fix for defects 1 and 2, so it is best settled together
with this patch.

One more meeting point: the invariant defect 7 leans on -- arg must hold
a column reference, the offset must not -- is exactly the check this
patch rewrites from has_column_ref to contain_var_clause. So the fix for
defect 7 and this patch land in the same place.

================================================================
A proposal
================================================================

I am not against resolving the offset in one place. But that
consolidation rests on the premise that an offset has a value by the
time it is resolved, and that premise is already false today.

The eleven defects above come down to five roots:

* offsets and arguments are frozen once at executor init
(defects 1, 2)
* the planner's tree walks do not look into defineClause yet
(defect 3, and list ownership with it)
* the volatility gate runs only before folding, and some paths never
reach it at all (defects 9, 10)
* folding and pull-up erase the column reference in a nav argument --
an invariant parse analysis enforces is broken in the planner
(defect 7)
* we evaluate to a different result than the standard defines -- the
argument of an out-of-range nav, and the predicate of a variable we
are not even trying to map (defects 6, 8)

So rather than fixing them one at a time, I think they are better done
as one bundle -- with the consolidation in it. What the bundle would
carry:

1. Make the premise hold: evaluate the offset again once the value is
known, the way frame offsets and nodeLimit already do, or give up
trim when the offset comes from such an argument.
2. Wire defineClause into the planner plumbing (finalize_plan's
PARAM_EXEC bookkeeping, the reachability of the volatility check).
3. Settle where the volatility check goes, before and after folding,
and put it there.
4. Protect arg from constant folding and from pull-up substitution.
5. Bring evaluation in line with the standard: no argument when there
is no target row, no predicate when we are not trying to map.
6. Add the EXPLAIN guard.
7. On top of that, resolve the offset in one place -- the
consolidation.

The comments and the diagnosis get put right along the way (defects 5
and 11).

Going in as one bundle, the consolidation becomes a much safer change
and I would be glad to see it in -- exactly where you want it, in this
patchset, only bundled with the defects.

Would you be able to work on top of these patches? Working from the same
base would make it easier for us to check each other.

I would like us to agree on what goes into this round and what waits,
before we go further.

A note on version numbers

There is still no complete v50. What went out as v50-0001..0020, and
v51-0001..0003 now, are all increments on top of v49. Bumping the
version for every increment means the same number ends up standing for
different patches. This mail is itself an example: v50-0001 and v50-0002
in the section headings above each name two different patches, and
without spelling out the full patch name there is no telling which.

I will post a draft of a numbering convention with the series that
follows. I would welcome your thoughts on it.

Two small things

Noticed while reading the patch:

* The definition of nav_traversal_walker() is gone, but its
declaration is still in src/include/optimizer/rpr.h -- and with it
the whole supporting block: the NavTraversal struct, the NavVisitFn
callback typedef, and the comment above them, which still says the
walker is "defined in rpr.c". NavTraversal and NavVisitFn are also
still in src/tools/pgindent/typedefs.list.

* README.rpr still describes navMaxOffsetKind / navFirstOffsetKind,
RPR_NAV_OFFSET_NEEDS_EVAL and RPR_NAV_OFFSET_RETAIN_ALL. A comment
in rpr_explain.sql still refers to visit_nav_exec and one in rpr.sql
to RPR_NAV_OFFSET_NEEDS_EVAL; the matching rpr.out / rpr_explain.out
carry the same lines.

Best regards,
Henson