Re: Row pattern recognition

Hi Tatsuo, Jian,

One construct is handled badly by every implementation I could check,
ours included. Oracle will not compile it, Trino compiles it and
answers wrongly, and we answer correctly at a cost the data does not
bound. It is a quantified subpattern whose body can match zero rows,
and PATTERN ((A? | B){2,}) is the smallest one.

The wrong answer is one our own suite already records, as
test_empty_stop_alt_body in rpr_nfa.sql. Two rows:

WITH t(id, flags) AS (VALUES (1, ARRAY['A']), (2, ARRAY['B']))
SELECT id, flags,
first_value(id) OVER w AS match_start,
last_value(id) OVER w AS match_end
FROM t
WINDOW w AS (ORDER BY id
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
AFTER MATCH SKIP TO NEXT ROW
PATTERN ((A? | B)*)
DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags));

id | flags | match_start | match_end
----+-------+-------------+-----------
1 | {A} | 1 | 1 PostgreSQL
2 | {B} | |

1 | [A] | 1 | 2 Trino 471
2 | [B] | NULL | NULL

The greedy (A? | B)* takes A in iteration 1. In iteration 2 the
preferred branch is A? again; A does not match row 2, so A? matches
empty. Section 7.2 of the standard says "Taking Perl as the model",
and 7.2.8 sets the rule -- once the lower bound is met, a quantifier
stops iterating as soon as its body matches empty -- so the match ends
at row 1 and B never consumes row 2. Perl agrees: "AB" =~ /(A?|B)*/
matches "A". Oracle rejects the shape outright with ORA-62513, so
Perl was the adjudicator. Three more of these are in the same file:
test_728_nullable_alt_first, test_728_stop_binds_at_min and
test_728_nullable_alt_min2.

That is the same rule our cycle guard exists to enforce, and the
construct it governs is the one that costs us the most.

Ours is the third of the three positions: we get the answer right and
pay for it without a bound. The row count is not what drives that
cost; the numbers written in the PATTERN clause are. I would like to
lay out what I measured and ask what our answer should be, because I
do not think a small change to the matcher reaches it.

1. Where the three implementations stand

Oracle refuses the whole class up front:

ORA-62513: Quantified subpatterns that can have empty matches are
not yet supported.

with the cause given as "there were empty matches for the quantified
subpattern in the PATTERN clause, as quantified subpatterns are
currently required to match one or more rows."

Trino accepts them and is fast; the answer above is what that speed
buys. We get the answer right, and this is what it costs. Trino 471
from the official image, twenty rows, with C defined so that it is
never true; elapsed as each server reports it, after warm-up:

Trino 471 this patch
PATTERN ((A? | B){n,} C)
n = 20 0.032 s 0.030 s
n = 40 0.034 s 0.124 s
n = 60 0.046 s 0.380 s
n = 80 0.051 s 0.898 s
n = 100 0.060 s 1.760 s

PATTERN ((A? | B?){n,} C)
n = 20 0.038 s 35.273 s
n = 40 0.037 s > 180 s, cancelled
n = 60 0.048 s > 180 s, cancelled
n = 80 0.061 s > 180 s, cancelled
n = 100 0.082 s > 180 s, cancelled

One character separates the two patterns. Trino is flat across both
-- it stays under a tenth of a second everywhere here, and only starts
to grow past n = 200, reaching 4.8 s at n = 1600 for the first pattern
and 7.2 s for the second. We are polynomial in the first and do not
finish in the second. Section 4 has our side of that in detail.

On the timing alone that is better than what we do, and I will come
back to it. But the same engine does this:

PATTERN ((A? | B){1000000,})
java.lang.StackOverflowError
at io.trino.operator.window.matcher.ThreadEquivalence
.reachableLabels(ThreadEquivalence.java:229)
surfaced to the client as an HTTP 500, not as a user error

PATTERN ((A? | B){100000000,})
the coordinator process dies -- OOM-killed with no memory cap,
exit 1 with the container capped at 4 GB

So no one is comfortable here. Oracle will not compile the pattern at
all; Trino compiles it, answers the small cases wrongly and dies on
the large ones; we answer correctly and have no bound. What stops the
large ones for us is this:

PATTERN ((A? | B){100000000,})
ERROR: stack depth limit exceeded (26 ms)

which is at least an error rather than a crash, but it comes from
check_stack_depth() noticing the recursion, not from anything that
knows what the pattern means. The message does not point at the
pattern, and the value of max_stack_depth decides where the line
falls.

2. Where the states come from

Take the smallest case and look at what is waiting before the first
row is read. PATTERN ((A? | B){2,}), with A false and B true:

states: {A, count 0} {A, count 1}

Writing "_" for an iteration that derived an empty match, that is

A
_ A

and nothing else. B never becomes a state. The first alternative
cannot fail -- A? matches empty when A does not match -- so two empty
iterations satisfy {2,}, the pattern reaches its end, and the empty
match is recorded during the epsilon expansion itself. Recording it
cuts the second alternative before it is enumerated. B's DEFINE is
never even evaluated: with B defined as v / 0 > 0 the query still
returns, and moving B to the front is what makes it raise division by
zero.

Now put something after the group that cannot match, so the pattern
can no longer complete on the spot. PATTERN ((A? | B){2,} C), C never
true:

states: {A, 0} {A, 1} {C, 0} {B, 1} {B, 0}

A
_ A
_ _ C
_ B
B

Five, in preference order. The third is the group exiting after two
empty iterations and landing on the tail. The last two are the second
alternative, which is now reachable because nothing recorded a match
to cut it.

3. Why the count follows min

Nothing above is specific to 2. At {n,} the list is

A _ A _ _ A ... _^(n-1) A
_^n C
_^(n-1) B ... _ B B

which is 2n + 1. The peak state counts confirm it -- twenty rows give
twenty-one live contexts, and NFA States Peak divided by that is 2n+1
at every n:

PATTERN ((A? | B){n,} C) peak peak/21 2n+1
n = 2 107 5.1 5
n = 4 193 9.2 9
n = 8 366 17.4 17
n = 16 718 34.2 33
n = 32 1422 67.7 65
n = 128 5646 268.9 257

The reason is that these states are not redundant. "_ A" and "_ _ A"
sit on the same element, wait on the same row, and read the same
DEFINE, but they carry different iteration counts, and below the lower
bound that difference is real: one of them still owes two mandatory
iterations and the other owes one. Merging them loses matches. Above
the lower bound they do become equivalent, and there the matcher
already folds them -- the cycle guard stops the empty-iteration chain
the moment the count reaches min. It is the run up to min that cannot
be folded.

And min is an int32. PATTERN ((A? | B){100000000,}) is a legal
pattern that asks for a hundred million of these.

4. Two nullable alternatives make it exponential

With one nullable branch the growth is polynomial. Total states
created for PATTERN ((A? | B){n,} C) over twenty rows:

n = 2 3,520
n = 4 7,660
n = 8 22,396
n = 16 102,780
n = 32 564,340
n = 64 2,774,068
n = 128 12,342,196 3.8 s

Roughly n^3 -- eight times the work for twice the n.

With both branches nullable it stops being polynomial. PATTERN
((A? | B?){n,} C), same twenty rows:

n = 2 4,505 0.017 s
n = 4 11,895 0.014 s
n = 6 35,285 0.013 s
n = 8 126,675 0.016 s
n = 10 493,585 0.034 s
n = 12 1,965,615 0.110 s
n = 14 7,860,685 0.449 s
n = 16 31,449,995 1.921 s
n = 20 503,301,095 35.273 s
n = 40 -- > 180 s, cancelled

Four times the work for every two added to n, which is 2^n. Twenty
rows and a two-digit number in the pattern is all it takes. Peak
states stay small -- 902 at n = 20 -- so this is not memory; it is
half a billion states allocated, compared and freed.

This is the case Trino answers in the table of section 1, and the
difference is not luck. At n = 20 it takes 0.038 s to our 35.3 s, and
it is still answering at n = 1600 where we do not reach n = 40.
Their matcher keeps an equivalence over threads, so the paths
that converge are folded before they are walked. Ours enumerates
paths: nfa_advance_alt() recurses once per branch, every branch tail
converges on the same element, and the counts that distinguish the
resulting states are the only thing keeping them apart. There is
already an XXX in nfa_states_equal() saying what the fix would need to
be -- a revisit key of (element, counts) rather than the element alone.

5. What computation buys, and what it does not

Section 4 is a matcher problem and could be improved; Trino shows the
shape of the answer. Section 3 is not.

The 2n + 1 states of PATTERN ((A? | B){2,} C) are all reachable, all
distinguishable, and all needed to answer correctly. Any n we accept,
we must be able to hold. A better equivalence relation folds the ones
above min, which is exactly what the cycle guard already does; it
cannot fold the ones below min without changing the answer. So
whatever we do about section 4, an int32 lower bound on a nullable
body still asks for an int32 number of states.

I looked at three ways to spend less on this anyway. Two of them
are worth doing. None of them removes the floor above.

(i) Represent the run below the lower bound as a count interval
rather than as one state per count. The operations that run goes
through -- a match, the split at min, the clear on exit -- all
look closed over intervals, and for that shape section 3's chain
would become a constant. I am setting this one aside. It does
not generalise: counts is a vector, one entry per nesting depth,
and a nested body's reachable set is not a product of intervals
-- (A{2,} B)+ C, the example already named in the XXX on
nfa_states_equal(), spreads over two depths at once. And the
preference order is the order of the state list, in which one
element's counts are not contiguous, so folding them changes
which derivation wins. It buys one particular shape of pattern,
and puts the preference order at risk to do it.

(ii) Filter on the DEFINE value during the expansion. Today the
expansion parks a state on a variable, and the next row's match
phase evaluates that variable and frees the state if it is false.
The value does not depend on the state -- nfa_eval_var_match()
reads the variable and the row, nothing else -- so the expansion
could evaluate it and never park the state at all. The cost is a
change of phase: the expansion has to run after the row arrives
rather than before it. What it buys is fewer states parked, and
so a shorter list for the duplicate check to walk, at every row
where only some of the variables are true. Where all of them are
true it buys nothing; the maximum is exactly what it is today.
The gain is zero or better and never negative, which makes this
cheap enough to just try.

(iii) Index the duplicate check. nfa_append_state_unique() is a
linear scan of the live state list. Over 320 rows
PATTERN ((A? | B){2,} C) creates 824,328 states and throws away
565,281 of them as duplicates, each found by walking a list whose
peak is 1,607. Building a hash once the list passes some size
would not let us store fewer states, but it would stop us paying
a walk for every state we create.

(ii) and (iii) are both implementable as they stand, and neither
depends on which control section 6 settles on. Where they belong is
the open question. I would write (ii) first and let the measurement
decide: if it moves the numbers on a pattern someone would actually
write, it can join this series, and if it does not, dropping it costs
nothing. (iii) I would rather see as a patch of its own. It adds a
data structure, and it has nothing to do with nullable loops, so it
should be reviewed on its own terms rather than as a footnote to this.
That is a preference, not a decision, and I would rather hear the list
on it.

They are also the kind of item where the hard part is the problem
statement and not the code. Once we agree on what each one has to
preserve, either is a self-contained piece of work that someone else
could pick up.

At the moment what stops it is check_stack_depth(), because the chain
is built by recursion. That is an accident. It fires at min around
ten to twelve thousand on a 2 MB stack, it moves when max_stack_depth
moves, and the error it raises does not mention the pattern. A
non-recursive construction of the same chain would remove the accident
and leave us allocating until the OOM killer arrives, which is where
Trino ends up.

6. So what should we do

Let me say first that I do not think this is settled. There may be a
way to hold these states cheaply that none of us has found, and it is
worth looking for. But replacing the matcher on its own may not reach
it: section 3 is not about how the matcher is written, and this is the
construct Oracle refuses to compile and Trino answers wrongly, which
is not what a tractable problem usually looks like. What I would
suggest is that we contain it with one of the controls below, finish
this series, and take the search for a real answer to a patch of its
own.

Three directions for the control:

(a) Bound the states at run time. Count them against work_mem, or
against a dedicated limit, and raise a clear error when a query
exceeds it. Every pattern the standard allows stays legal, and
the ones too large for this server fail with a message that says
so. It needs an accounting we do not have yet, and it makes the
behaviour depend on a setting.

(b) Reject the pattern at compile time. Refuse a quantified
subpattern whose body can match empty, as Oracle does. A message
can name the offending construct, it costs nothing at run time,
and the RPR_ELEM_EMPTY_LOOP flag we already compute is exactly the
test it needs. It also takes away patterns that work fine today:
PATTERN ((A? | B){2,}) is answered correctly and immediately, and
under this rule it would stop being accepted.

(c) Limit the lower bound alone. Accept a nullable body, refuse {n,}
beyond some n. This covers section 3 without touching section 4,
and without removing the patterns people actually write.

I lean towards (a), and the table in section 1 is the reason. Neither
(b) nor (c) can be decided from the pattern text, because the cost is
not written there. One character separates its two halves -- B
becomes B? -- and at the same n = 100 that moves us from 1.8 seconds
to not finishing in three minutes. Nothing in the text of
((A? | B){100,} C) says seven million states, and nothing in
((A? | B?){100,} C) says it will not stop; the difference is in how
the alternation's branches interact under the quantifier, which is
also not something the person writing the query can read off the page.

That leaves the compile-time rules badly placed. A rule broad enough
to be safe has to reject the first pattern along with the second,
which is (b) and costs us patterns that answer in thirty
milliseconds. A bound on n alone, (c), does nothing for the second
pattern at n = 20. A run-time limit measures the thing that actually
goes wrong, and it is the same shape as what we already do for memory
elsewhere.

I would rather hear what you think before writing any of it. But
whichever way we go, I think it should be decided rather than left to
check_stack_depth().

7. The attached patch

wip-check-for-interrupts-in-nfa-expansion.txt is not a fix for any of
the above. It is the thing I needed before I could measure any of it:
the epsilon expansion had no CHECK_FOR_INTERRUPTS() of its own, so how
long a query like the ones above ran before it noticed a cancel
depended on a check that happens to sit in the duplicate scan of
nfa_append_state_unique(). The patch adds one next to the
check_stack_depth() already in nfa_advance_state(), which every cycle
in the expansion passes through, so the interval is bounded by the
recursion depth instead. The existing one stays; the two bound
different things. It costs nothing measurable and the RPR tests pass.

Naming it wip-*.txt as we agreed, the same way as
wip-readme-cut-duplicated-sections-rev-001.txt. I would like to build
whichever of the above we settle on as further patches on top of this
one, in the same thread, and number them 0XXX-*.txt once they are
agreed.

Anything I have missed in the measurements, or a direction I have not
considered?

Best regards,
Henson