Re: Row pattern recognition

Hi Tatsuo, Jian,

This is about the run condition block for RPR windows.

Around March we blocked two planner optimizations for RPR windows,
one after the other.

The first was yours. I reported that "WHERE cnt > 0" returned no rows
at all because the filter had been pushed into the WindowAgg, and you
wrote back with the fix:

/* allpaths.c, find_window_run_conditions() */
if (wclause->defineClause != NIL)
return false;

I took it into the series, and the comment above it is still your own
sentence from that mail: "a partition/frame is divided into multiple
reduced frames and each should be evaluated to the end of the
partition/frame".

The second came not long after:

/* planner.c, optimize_window_clauses() */
if (wc->defineClause != NIL)
continue;

That one stops support functions from replacing an RPR window's frame
options with something the pattern matcher cannot use.

What a Run Condition buys, before RPR comes into it. Take the plain
window:

SELECT * FROM (
SELECT i, row_number() OVER w AS rn
FROM big
WINDOW w AS (ORDER BY i
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)) s
WHERE rn <= 3;

WindowAgg (actual rows=3)
Window: w AS (ORDER BY big.i ROWS UNBOUNDED PRECEDING)
Run Condition: (row_number() OVER w <= 3)
-> Sort (actual rows=4)
-> Seq Scan on big (actual rows=200000)

The filter sits above the window, so it cannot become a scan qual.
What the planner can do instead is notice that row_number() only ever
goes up: once a row fails "rn <= 3", no later row can pass either. So
the filter is handed to the WindowAgg as a Run Condition, and the
WindowAgg stops the moment it fails -- it stops pulling from below as
well, which is why the Sort emitted four rows instead of 200,000. The
Seq Scan still read the whole table, because the Sort had to; what is
saved is everything the WindowAgg would have gone on to do. With a
pattern to match, that is where the cost is.

Two things had to be asked of row_number() to get that plan, and both
are in it. "Run Condition" is there because the function answered
SupportRequestWFuncMonotonic with "increasing". And the frame reads
"ROWS UNBOUNDED PRECEDING" although the query said "BETWEEN CURRENT
ROW AND UNBOUNDED FOLLOWING", because the function also answered
SupportRequestOptimizeWindowClause: the frame does not matter to it,
so the planner replaced it with a cheaper one.

That second rewrite is exactly what we blocked for RPR windows, and
for good reason -- an RPR window cannot have its frame taken away.

Two shapes run into the block, and they want different things.

The first is where nothing on the window reads the reduced frame at
all:

SELECT * FROM (
SELECT i, row_number() OVER w AS rn
FROM big
WINDOW w AS (ORDER BY i
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (a b+) DEFINE b AS v > PREV(v))) s
WHERE rn <= 3;

The matcher expands 216,200 NFA states over the whole table and no one
reads the result, since row_number() is counting positions in the
partition. The same query with PATTERN and DEFINE removed is the
plan at the top of this mail: a Run Condition, and actual rows=3.

This one would not need find_window_run_conditions() touched at all.
If the planner could see that no window function on the clause reads
the reduced frame, it could drop the RPR part of the window, and the
existing run condition rules would then apply on their own, because
defineClause is gone.

The second is where one function reads the reduced frame and another
does not:

SELECT * FROM (
SELECT i, count(*) OVER w AS cnt, row_number() OVER w AS rn
FROM big
WINDOW w AS (ORDER BY i
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (a b+) DEFINE b AS v > PREV(v))) s
WHERE rn <= 3;

count() is real RPR output, so the matching does have to happen -- but
only for three rows. The plan expands the same 216,200 states, with
"Rows Removed by Filter: 199997" above it. This is the one that would
need the guard itself narrowed.

I am not claiming the second one is safe. The run condition puts the
WindowAgg into pass-through, and what changes under RPR is how far the
node still has to reach: not to the cut-off row, but out to wherever
the match that crossed it closes.

As things stand, neither shape is giving a wrong answer. They just
take longer than they need to. That is an optimization we have not
done rather than a defect, and the current series is about defects, so
I would rather push the fix down the list.

What do you think?

If we do come back to it, the two start from different places. The
first starts with classifying window functions -- which of them are
affected by RPR at all. If none of the ones on a clause is, that
window can quietly have its RPR turned off, and the run condition
code needs no change at all. The second starts further back, with
going through the whole run condition matrix again under RPR: which
monotonic direction and which operators still hold once the frame is
a reduced one.

Best regards,
Henson