Re: Row pattern recognition

Hi Henson.

> 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.

Yes, I confirmed this too. WindowAgg node uses
tuplestore_gettupleslot and it relies on buffile.c to read tuples from
disk once it switches to TSS_WRITEFILE/TSS_READFILE state. For reading
data from disk, BufFileLoadBuffer is used. It only keeps single buffer
in size of BLCKSZ.

> 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.

+1.

Regards,
--
Tatsuo Ishii
SRA OSS K.K.
English: http://www.sraoss.co.jp/index_en/
Japanese:http://www.sraoss.co.jp