Re: Row pattern recognition

Hi hackers,

This is the second of the postings that follow the increment. It
covers 2007 through 2013 and changes nothing in them.

One thing before the seven, about where they come from. They all
begin in jian he's review: what is here is the patches he sent, with
the verification worked out and settled into this shape. He has been
reading this code closely and sending patches rather than reports, and
the series is better for it.

The seven are one subject seen from three stages: the DEFINE clause
and its navigations, in the parser, in the planner and in the
executor. 2007 and 2013 are the parser's, 2008 and 2012 the
planner's, 2009 and 2011 the executor's, and 2010 is the one that
carries a decision from the second stage to the third.

2007 Correct resno and dedup handling of RPR DEFINE targetlist entries

Two small things in one loop. A DEFINE predicate reads columns, and
the parser has to see that the query's targetlist carries each of
them, so the column reaches the window that evaluates the predicate.

Whether a column was already there was decided on its table and
attribute number alone. A LATERAL outer reference can carry those
same two numbers while naming a column of another relation at another
level, and it then answered for the local one: the entry was never
added, the column never reached the plan, and setrefs.c failed with
"variable not found in subplan target list". Comparing the two Vars
with equal() settles it, the level being the field that separates
them.

The other is where the new entry's number comes from. It was counted
off the length of the list, which numbers that entry correctly and
leaves the parser's own counter one behind, so whatever is appended
next takes the same number again. Only a later window's PARTITION BY
or ORDER BY key can be that next thing, DEFINE being transformed after
both. Nothing then reads a wrong value; what notices is the Assert
already standing in apply_tlist_labeling().

2008 Register DEFINE-only correlated parameters in the WindowAgg's extParam

A bind parameter in a DEFINE always worked; a correlated one did not,
and that difference is the patch. A plan records the parameters that
can change underneath it while it runs, so a rescan knows what has to
be thrown away. Only the correlated kind is ever recorded -- a bind
parameter is fixed for the whole execution and invalidates nothing.
finalize_plan() gathers them from a plan's targetlist and its qual,
and from any other expression field only where its switch names one.
For a WindowAgg it named the two frame offsets, and not the DEFINE
clause.

A parameter that appears nowhere else is therefore missing from that
record. When the join tells the node directly beneath it that the
parameter changed, the news reaches anything further down only by
being matched against what each node declared -- and the WindowAgg
declared nothing, so it is never told. A hashed aggregate above it
keeps the table it has whenever nothing beneath it changed, which is
now what ExecReScanAgg() concludes, and the next outer row is answered
from the table built for the previous one.

Nothing catches that earlier, because the check at the end of
finalize_plan() fires on a parameter that should not be in the record,
never on one that is missing.

2009 Return null from a row pattern navigation to a nonexistent row

A navigation names a row relative to the match, and the standard has
one answer for when that row falls outside the range it may search:
the navigation is null. The argument is not evaluated at all, there
being no row to evaluate it against.

The implementation answered with a row instead. A slot built once at
init, every column null, was installed as the current row and the
argument ran over it. Where the argument is strict and reads a column
the two agree -- null in, null out -- which is why no existing
expected output moved. Where it is not, they part: PREV(val IS NOT
NULL) on the first row of a partition came out false, and PREV(v IS
NULL) came out true. A row that is not there was indistinguishable
from a real row whose columns happen to be null.

Now the fetch returns nothing rather than a made-up row, the setup
step records the navigation as null and leaves the current row in
place, and a jump between it and the argument steps over the argument
entirely. Over five rows, DEFINE A AS PREV(val is not null) is null
goes from matching nowhere to a one-row match on the first.

One case is left over, and it belongs to constant folding rather than
to this. A single-row WITH ... VALUES is pulled up and its column
folded to a constant, including where that column sits under a
navigation and so names a row other than the one the constant was
taken from; PREV(v / 0) then raises at plan time for a navigation that
has no row to go to. It is tracked separately.

2010 Resolve RPR navigation offsets in the executor, not the plan tree

The same offset expression was resolved in four places: two settling
the tuplestore trim bounds, in the planner for the constant ones and
at executor init for the rest, and two more driving the navigation
itself, compiled inline and re-evaluated on every row.

Init is the wrong place for the second of those. A bind parameter has
its value before init and keeps it for the whole execution; a
correlated one -- the PARAM_EXEC an inlined SRF or a LATERAL leaves
behind -- has none, the array being allocated empty and filled during
execution. An offset read there resolved to 0 and stayed 0 for the
life of the node, with nothing to re-run on a rescan. The mark then
sat on the row being matched, and the first PREV or LAST reaching two
rows back raised "cannot fetch row before WindowObject's mark
position".

So it is done once, at the start of each scan rather than at init,
immediately after calculate_frame_offsets() settles the window frame's
own offsets for the same reason. What cannot be resolved there is
left for the scan, which is also what stops EXPLAIN (GENERIC_PLAN)
failing on an unbound $n.

Two costs. A null or negative offset is now rejected at the start of
every scan, so a query that never reached the navigation -- an empty
partition -- errors where it used to return nothing. And the two
walks that assign and consume the navigation numbers have to visit in
the same order, which nothing enforces but their being written the
same way.

2011 Centralize the RPR field initialization in ExecInitWindowAgg

A refactor. The RPR initialization was in five places in
ExecInitWindowAgg() and is in one now, in struct declaration order,
and I could not construct a query whose result, plan or EXPLAIN output
differs.

2012 Check RPR DEFINE volatility after expression preprocessing

PostgreSQL does not test expression volatility during parse analysis.
The test belongs to the planner and runs after preprocessing, so what
the planner folds away is never tested -- a volatile in a branch that
is dropped, or in a subquery that is discarded, is not seen. Mainline
moved FOR PORTION OF's own check for that reason in June
(a272a58b942); this does the same for DEFINE, and the two now stand in
the same function a few lines apart.

Before it, the check ran on the parse tree, and that is not the tree
the executor gets. eval_const_expressions() splices in a function's
default arguments -- parse analysis deliberately leaves them out so
the planner can insert the current ones -- and inlines SQL bodies. So
the old check both missed and over-reached. A STABLE SQL wrapper
whose default argument is (random() * 5)::bigint passed as one STABLE
call, and the statement after it spliced random() in, leaving a
navigation offset drawn from random() at run time. A VOLATILE SQL
function whose body is a constant was rejected, where inlining and
folding leave the DEFINE a constant TRUE with nothing volatile left to
run.

The line it draws is not whether the window is ever executed. The
loop runs over every window clause of every Query the planner plans,
before select_active_windows() drops the ones no OVER references, so a
top-level window nothing refers to is checked and rejected though
nothing will ever run it, and so is a subquery an OFFSET 0 keeps or a
CTE something references. What is not checked is a Query the planner
never plans: a subquery flattened into its parent, a rel made dummy by
WHERE false, an unreferenced CTE, a UNION ALL leaf flattened like any
other.

What is left over belongs to the convention rather than to this patch.
Folding substitutes a bound Param only for a custom plan, so a
prepared statement can be accepted and then rejected once the plan
cache moves to a generic one. FOR PORTION OF has the same, which
makes it a question to put to the convention rather than to answer
here.

2013 Report a sibling navigation as not being a direct argument

Message only. A compound navigation -- PREV(FIRST(...)) and its three
siblings -- is the one nested form allowed, and only where the inner
navigation is the outer's argument itself, so that the two can be
flattened into a single operation. Anything else under a PREV is not
a compound navigation at all, which is the first thing to say about
it.

It was said second. The branch tested the nesting depth first, and a
depth means nothing until the argument is known to be exactly one
navigation, so PREV(FIRST(v) + LAST(v)) reported "cannot nest row
pattern navigation more than two levels deep" -- of two navigations
that are siblings, both one level under PREV -- and asked for the
removal of a level that is not there. PREV(FIRST(PREV(v))) is what
that message is for.

Best regards,
Henson