Re: Row pattern recognition

Hi jian,

This started as an offlist thread, but I'm posting this reply to
pgsql-hackers instead. The reasoning behind the test count and
structure seems useful to whoever else is reviewing this patch, so I'd
rather have it on the CF record than in a private exchange between the
two of us. Hope that's alright.

First, the concern and the convention. Tests for existing features are
what one file per feature accumulated over decades (join.sql has 252
commits since 1999, window.sql 48 since 2008). Recent large features
kept their cross-feature tests inside a feature-centered file too: MERGE
in merge.sql (1,841 lines), SQL/JSON in sqljson*.sql (about 2,400 lines
together). RPR follows that same convention and is organized around
RPR, but because this volume arrived all at once it looks unusually
large in line count, and the tests that cross into other features are
concentrated on the RPR side.

So, separate from the answers below, I have three options in mind for
dealing with the file size without reducing the number of tests. (1)
Move rpr_nfa.sql and rpr_explain.sql, which test the NFA engine itself,
into a separate test module. (2) Rather than keeping the RPR tests that
cross into existing features (GROUP BY, subquery/CTE, JOIN, set
operations and so on) on the RPR side, rewrite them against the tables
and queries of each feature's existing tests (groupingsets.sql,
subselect.sql, join.sql, ...) and distribute them there -- a direction
that differs from the convention above, so it needs discussion. (3)
Split a large file like rpr_base.sql into topical files along the
sections its own header already lists. For example,
serialization/deserialization (1,697 lines, 23% of the file), navigation
functions (670), quantifiers and PATTERN syntax (about 800), pattern
optimization and absorption (about 930), error cases (about 520) and the
DEFINE clause (335) are each self-contained topics that can be moved as
they are, without rewriting, and moving serialization/deserialization
alone would bring rpr_base.sql down to about 5,650 lines. All three
keep what the tests verify and only move it, though (2) comes with the
work of rewriting the queries against the existing tables. I'll ask for
your view at the end.

> "argument of row pattern navigation operation must include at least
> one column reference"
> This error message in function define_walker appeared in rpr_base.out,
rpr.out.
>
> How about we consolidate all these error cases into a single place?
>
> "argument of row pattern navigation operation must include at least
> one column reference"
> It appeared 11 times, which I would say is excessive.
> Is 11 times really necessary?

In the source there are only two call sites for this errmsg, in
parse_rpr.c: one for the case where the argument is a plain nav, one
that runs only after a compound nav like PREV/NEXT(FIRST/LAST()) has
been flattened into a single node. They are mutually exclusive
branches, not the same code. So there is nothing to consolidate there.

The 11 is how many regression cases hit those two sites, not how many
places raise the error. They split cleanly into a combination:

simple: constant, expression, with-offset (3)
compound: constant, expression,
inner offset, outer offset, both offsets (5)
literal: string, NULL, prepared-statement parameter (3)

3 + 5 + 3 = 11, and each cell is a different shape -- removing any one
leaves that cell uncovered. I would rather keep all eleven than trade
coverage for a lower count.

> ```
> --
> -- Parser/planner tests: rpr_base.sql
> -- NFA engine tests: rpr_nfa.sql
> -- EXPLAIN statistics tests: rpr_explain.sql
> --
> ```
> I don't think the above comments are necessary.

That's the index at the top of rpr.sql, pointing at rpr_base.sql,
rpr_nfa.sql and rpr_explain.sql. I'd rather keep it -- now that the
suite is split five ways, it tells a reader at a glance which file
covers what.

>
https://github.com/assam258-5892/postgres/blob/ec3797180cb1ec6df48bc6633929b33b7f2aae4d/src/test/regress/sql/rpr_base.sql
> says "7373 lines".
> We should try to find ways to reduce the size of the tests.
> "7373 lines". is unmaintainable.

Same position as before, and here is the reasoning behind it: from the
code alone, two tests cover both call sites in parse_rpr.c. But this
suite is not written against the code, it is written against the
DEFINE/PREV/NEXT interface as a black box, so a later rewrite of
parse_rpr.c is still caught if it changes what the interface accepts.
That is the same reason the matrix has eleven cells and not two.

Once that is the standard, every other RPR test is built the same way.
Cutting this one spot without changing the standard everywhere would
just leave it inconsistent with the rest of the suite -- I don't see a
narrower standard that still catches what these eleven catch, so I am
not planning to shrink this one.

The size does not come from an unusual number of tests, though: the
query count is in line with the existing features, and the size comes
from query length (see below). Counting by the existing-feature areas
rpr_base.sql's own header lists under "planner layer", against each
feature's own dedicated test count (the RPR column counts queries using
OVER in rpr_base.sql, the dedicated column counts all queries in those
files, and the cross cases in rpr_integration.sql and rpr.sql are left
out):

existing feature area RPR cross-tests dedicated tests (file)
subquery/CTE 5 495 (subselect.sql 260 +
with.sql 235)
JOIN 11 605 (join.sql)
complex expressions 5 31 (case.sql)
set operations (UNION etc.) 4 156 (union.sql)
sorting and grouping 52 265 (select_distinct
43+limit 40+
select_having
11+groupingsets 171)

No area exceeds that feature's own dedicated test count; subquery/CTE
and JOIN sit at 1-2%, set operations at 3%. Complex expressions (16%)
and sorting and grouping (about 20%) are higher -- the first because its
baseline, case.sql, is only 31 queries, the second not by accident:
parseCheckAggregates() was originally built to substitute grouped
columns to point at the RTE_GROUP RTE in exactly two places, the target
list and the HAVING clause. DEFINE is the only part of a WindowClause
whose expression tree can reference columns (PARTITION BY and ORDER BY
only point at target-list entries, and frame offsets must be Var-free),
so that substitution had to be taught a third place. HAVING already
gets tested against every grouping shape because of this same
substitution (see groupingsets.sql's HAVING section); DEFINE needs the
same kind of checking for the same reason. This area isn't large
because its scope grew -- it's the same requirement HAVING already
carries, applied to the new place that needed it.

One more point, about format rather than count: squeezing the WINDOW
clause onto one or two lines to save lines is its own kind of loss. RPR
adds PATTERN, DEFINE and INITIAL/SEEK on top of the ordinary PARTITION
BY / ORDER BY / frame a window clause already carries, so one keyword
per line is what keeps each sub-clause readable at a glance. Running
them together would make the file shorter and each query harder to read
at the same time -- shrinking for readability's sake while making it
less readable is not a trade I'd take.

What that trade-off actually looks like exists in insert.sql too:

create or replace function donothingbrtrig_func() returns trigger as
$$begin raise notice 'b: %', new.b; return NULL; end$$ language plpgsql;

A whole trigger function body squeezed onto one line. The file total
goes down, but that one line isn't something I'd call readable -- not a
trade I want to import into the RPR tests.

It isn't just that clauses get added -- the frame and ORDER BY are
effectively required here too. The frame is enforced by the parser:
rpr_frame_is_supported() rejects the default frame and requires ROWS
BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING (or ...offset FOLLOWING)
spelled out. ORDER BY isn't checked by the parser, but PATTERN is a
sequential, time-series analysis -- leaving it out would put row order
at the mercy of whatever the plan happens to produce that day, not at
anything the query actually asked for.

The FROM side gets long for the same kind of reason. The hardest
deparse bugs in this patch mostly came from DEFINE clashing with a
JOIN's USING list, and rpr_res_fa_v is the example:

CREATE VIEW rpr_res_fa_v AS
SELECT count(*) OVER w AS cnt
FROM (rpr_res_fa FULL JOIN rpr_res_fb USING (x)),
((rpr_res_fc JOIN rpr_res_fa t4 USING (x)) AS j(x, x_1)
JOIN rpr_res_fb t5 USING (x))
WINDOW w AS (ORDER BY j.x
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (A+)
DEFINE A AS x_1 > 0);

DEFINE reads x_1, the name the alias list j(x, x_1) gives to
rpr_res_fc.y. The anonymous FULL JOIN already takes the plain name x,
so when deparsing the second USING the deparser has to skip both x and
x_1 and picks x_2. Running that nesting onto one line would make it
impossible to tell where each name came from -- the line breaks aren't
decoration, they're what lets a reader follow it.

In numbers (queries with an actual WINDOW clause (OVER) / total lines /
lines per query; select.sql has no query using OVER at all, so it's
counted by plain SELECT statements instead):

select.sql : 50 / 273 / 5.5
window.sql : 383 / 2311 / 6.0
rpr.sql : 152 / 2944 / 19.4
rpr_base.sql : 584 / 7345 / 12.6
rpr_nfa.sql : 213 / 5607 / 26.3
rpr_explain.sql : 321 / 4012 / 12.5
rpr_integration.sql : 84 / 1568 / 18.7

select.sql (5.5) and window.sql (6.0) are the lowest. All five RPR
files come in at 12.5 or higher -- even the lowest of them,
rpr_explain.sql (12.5), is more than double window.sql. Once a frame,
ORDER BY, PATTERN and DEFINE all have to go into the same query, an RPR
query that uses windowing runs structurally longer than an ordinary one
that does.

As for run time, I measured on a dev machine (8 cores, assert-enabled
build) with test_setup run first (serial case repeated 5 times, full
suite 3 times):

five RPR tests, serial about 1.0 s (about 6.6% of the 15.2 s wall
time)
five RPR tests, parallel about 0.5 s (about 3.3%)
full regression suite (244) about 15.2 s (about 57 s summed over tests)

By lines, RPR is 14.2% of all regression-test SQL (150,946 lines); by
summed test time it is about 2%. So the burden of this volume is in
reading and maintaining it, not in run time, and that is the angle from
which I'm asking about the options above.

To sum up:

- Against window.sql, rpr_base.sql has 1.5x the queries (584/383) and
rpr.sql actually has fewer, 0.4x (152/383). The files are still
bigger because each query is longer by structure (frame, ORDER BY,
PATTERN, DEFINE, or a USING merge) -- lines per query go from 6.0 in
window.sql to 12.6 in rpr_base.sql (2.1x) and 19.4 in rpr.sql (3.2x),
and that length multiple combined with the count multiple gives the
total-line multiples (3.2x and 1.3x). It is length, not count, that
got multiplied. Longer queries are a separate question from cutting
the number of tests to compensate, and I'm not comfortable accepting
that trade.

- Had the same number of tests been written at window.sql's density (6.0
lines per query), the five RPR files would total about 8,100 lines
(rpr_base.sql 3,504, rpr.sql 912, rpr_nfa.sql 1,278, rpr_explain.sql
1,926, rpr_integration.sql 504) instead of the actual 21,476. Holding
the test count fixed, the files come out 2.1x bigger for rpr_base.sql
and rpr_explain.sql, 3.1x for rpr_integration.sql, 3.2x for rpr.sql
and 4.4x for rpr_nfa.sql, 2.6x overall -- and all of that multiple
comes from the length of a single query.

- rpr_nfa.sql and rpr_explain.sql are their own group -- they look at
the NFA engine itself (the matching itself, and the EXPLAIN output
that reports on it), not surrounding features. Within that pair, only
rpr_nfa.sql (26.3) stands out on density, not rpr_explain.sql (12.5),
but what they target is the same. PostgreSQL already has a precedent
for this: its own regex engine splits the same way, into ordinary
feature tests (155 lines) and a dedicated module just for the engine's
own correctness (1786 lines). Verifying one internal state machine
properly taking that much space on its own is an established practice
in this codebase, not something RPR invented. Option (1) above is
simply following that precedent.

- rpr_integration.sql is the one place that checks how RPR interacts
with the planner: section A has one guard test per planner
optimization, section B has integration scenarios. Some cases (e.g.
B11 and the A5 join-removal ones) were added for bugs found in review.
Its size, 84 queries and 1568 lines, is a cost worth paying.

Finally, a question: of the three options above -- moving the two
NFA-related files into a separate module, distributing the cross-feature
tests into each feature's existing tests, and splitting rpr_base.sql
into topical files -- which one, or which combination, do you think is
realistic? If you see another direction, I'd like to hear that too.
Either way, I'd want what the tests verify kept as it is.

Best regards,
Henson