Re: Row pattern recognition

Hi Tatsuo, Jian,

Following up on the second item in the "Known issues" list from the
last increment: partition tuplestore spills plus FIRST()/PREV(FIRST())
navigation in DEFINE turn quadratic once the partition spills. Here's
the reproduction and root cause.

Reproduction:

SET work_mem='64kB';
SELECT count(*) FROM (
SELECT id, count(*) OVER w cnt
FROM (SELECT g AS id, repeat('x', 50) AS pad, (g % 11) AS v
FROM generate_series(0, 3999) g) t
WINDOW w AS (ORDER BY id
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
AFTER MATCH SKIP PAST LAST ROW
PATTERN (S A+) DEFINE S AS TRUE, A AS v >= FIRST(v))
) s WHERE cnt > 0;
RESET work_mem;

work_mem=64kB (Storage: Disk), rows -> elapsed:

2,000 0.84 s
4,000 5.4 s
8,000 24.3 s

4.5-6.4x per doubling. The same 8,000 rows in memory: 2.6 ms -- about
9,000x apart. Two controls rule out the obvious explanations: PREV()
in place of FIRST() on the same data stays at 3.3 ms spilled, and a
non-RPR last_value() reaching an equally distant frame under the same
work_mem costs 12.4 ms. So it isn't spilling itself, and it isn't
distance into the partition; it's specifically FIRST()-style
navigation to a fixed match-start row.

Root cause: once a partition's tuplestore spills, only one disk block
is ever resident in memory for it at a time. Re-reading a fixed row
while another position keeps advancing means walking that single
resident block back to the fixed row and out again every time, and
the cost grows with how far apart the two positions have drifted.

This isn't specific to RPR either -- I confirmed it against unpatched
core. Under work_mem=64kB, a plain `count(*), first_value(v),
last_value(v) OVER (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND
UNBOUNDED FOLLOWING)` -- first_value pinned at row 0, last_value at
the partition end -- takes temp read from 6 blocks (count(*) alone)
to 12,017 for the same 2,000 rows, and 8,000 rows goes from 1.9 ms to
24.7 ms just from adding those two fixed-but-distant functions. So
this disk I/O behavior isn't something RPR introduced -- it's a
tuplestore limitation that any query touching more than one position
at once runs into.

Short of a fix, the practical workaround today is to raise work_mem
enough that the whole partition stays in memory -- if it never
spills, none of this applies. Not a real answer for a large
partition, but worth saying plainly since it already makes the
problem disappear for anyone who hits this now.

I'm leaving this as a known limitation. Let me know if you see it
differently.

Best regards,
Henson