Re: Row pattern recognition

Hi hackers,

This is the first of the postings I said would follow the increment.
It covers 2001 through 2006 and changes nothing in them; it is the
part of the reasoning that a paragraph could not hold.

2001 Bound the END search in row pattern absorption analysis

isUnboundedStart() walks the ->next chain to the END that closes a
group and leaves the walk when it meets an element shallower than the
first child. Depth is unsigned, so at depth 0 there is nothing
shallower to meet -- FIN included. The walk therefore steps past FIN,
and FIN's next is RPR_ELEMIDX_INVALID, which is -1: the read is
elements[-1], in front of the array rather than past its end.

What follows is whatever that word happens to hold, and for the same
reason nothing it finds can end the walk either. On the build I
reproduced it on the word read back as 0, so the walk returned to the
first element and went round from there, and kept going round: a hang,
not a crash. A different allocation would fault instead, which is the
same defect wearing a symptom that is easier to notice.

The patch stops the walk at FIN and lets the existing END test reject
the sequence.

No test comes with it, and the reason is not that the case is hard to
reach but that the tree it needs is one optimizeRPRPattern() does not
produce. Without that pass it is produced, and that is where the fix
was tested: on a build with the optimization commented out the walk is
entered at depth 0 and leaves the array as above, and with the bound
in place it stops at FIN and the sequence is rejected.

On the tree the compiler actually hands to the absorption analysis the
walk is not entered that way, so the bound is defensive rather than a
fix for anything a query can reach today. That is also why the
regression suite carries nothing for it: the test would have to run
against a build with the optimization pass taken out.

2002 Fix row pattern recognition alternation branch-walk overload

One field carries two different links. A compiled alternation chains
each alternative to the next through the jump field of that branch's
first element, and that is the same field a group's BEGIN uses for its
skip past its own END. A branch that begins with a quantified group
has both to store and one place to put them, so one of the two is
lost, and which one depends on where the branch sits.

On the last branch there is no branch link to write, the skip
survives, and the walk reads it as one more alternative.
PATTERN (A | (B C)+ (D E)+) behaves like A | (B C)+ (D E)+ | (D E)+
and matches D E D E, and absorbability analysis over-marks the
trailing group for the same reason. On a branch that is not the last
the loss runs the other way, the branch link overwriting the group's
own skip.

Nesting depth cannot separate the two. Both links leave the same
element at the same depth and point outward.

The patch gives every alternative a SEP element of its own to end on
and runs the branch link from ALT through that chain, so a group's
BEGIN skip can no longer be read as a branch link. The match walk,
absorbability analysis and EXPLAIN's deparse all enumerate branches
through the SEP chain. SEP takes varId 0xFE, which moves BEGIN, END
and ALT down one, and the cost is one element per branch against
RPR_ELEMIDX_MAX.

2003 Preserve row pattern preferment in three PATTERN optimizations

These three rewrites were checked against the wrong invariant. They
keep the set of lengths a pattern can match, which is what one
naturally checks, and that is not enough: leftmost-choice-first
(ISO/IEC 19075-5 7.2) makes the preferred match observable, so the
same query returned different rows depending on whether the rewrite
fired.

What they have in common is that each can move a repetition's exit
decision past a choice point inside the body. The gate is therefore
the body consuming a fixed number of rows (rprBodyHasUniformLength),
which is when the two search orders agree. Alternatives of equal
length count as fixed -- they may pick different variables, but never
different rows -- and anything the measurement cannot pin to a number,
an unbounded quantifier included, counts as varying.

Different variables but never different rows: that is the whole of it.
A reordering is visible only where it changes the rows a match covers,
and where it changes only which derivation reached them there is
nothing to see. So the condition is on the rows a round consumes, and
a body whose rounds all consume the same number leaves the rewrite
nothing observable to move.

mergeConsecutiveGroups and the suffix phase of mergeGroupPrefixSuffix
fold a copy of the body into an adjacent group's quantifier. Over the
rows A, AB, B, A the pattern (A | B B)+ (A | B B)+ prefers all four
rows where the folded (A | B B){2,} takes two. The prefix phase of
the same function reorders nothing and needs no gate.

tryMultiplyQuantifiers needs one condition beyond contiguous counts,
because the nested form settles each round's count before starting
another and stops early when what is left cannot reach the inner
minimum. Over four rows (A{2,3}){1,2} prefers three where the
flattened A{2,6} takes four.

Three rpr_base tests had pinned the wrongly folded pattern -- a{4,9},
a{4,12} and (a b*){2,} -- and now show the pattern as written; runtime
tests fix the preferred match for each. README.rpr IV-3 records the
conditions.

2004 Fix row pattern preferment and cycle handling in the NFA matcher

This is the largest of the six. Four things are in it, and most of
what they fix the regression suite cannot see, so it is worth saying
what each one is before saying why the suite is quiet.

(a) What the sub-pattern prefers, and what counts as a cycle

What orders a quantifier's two moves -- stop here, or go round again
-- is not the quantifier written at that position but what the
sub-pattern under it prefers. nfa_advance_end() took the order from
the group's own greed, which says nothing when min equals max: in
((A?){2}?) the group says only that it is reluctant while the body
still prefers to consume a row. The preference is derived while the
pattern tree is flattened now and recorded on the END as
RPR_ELEM_EMPTY_PREFERRED. Each level combines it differently -- a
concatenation needs every element to agree, a group adds its own skip,
an alternation takes it from the first branch alone, branch order
being preference order -- and all three keep it implying nullability,
which is the condition the executor reads it under.

The cycle guard is the other half of the same order. It identified a
state by its element index alone, where a state is really that index
together with the iteration counts: coming back into a body that
consumes a row, at a higher count, is a new state and not a cycle, and
(A+|B){2} over an all-A partition lost its match to that. Only a
nullable END can close an iteration without consuming a row, so only
those are marked now. Reaching one means the body has just derived an
empty match, and per 7.2.8 an empty iteration at or above the lower
bound stops the quantifier: the group is left there rather than
discarded, discarding having demoted "stop here" below the
alternatives that remained. Below the bound it falls through to the
ordinary loop-back instead. Clearing the marks there would be the
other way to do it, and re-arms the guard of a nested reluctant
quantifier whose empty iterations then recurse until the stack gives
out.

The narrowing has a cost, and it is better said here than found later.
ALT and BEGIN are no longer marked, so within one advance they can be
re-entered any number of times, and a run of alternations whose
branches are all nullable enumerates paths rather than states: k of
them cost 2^k. (A?|B?){30} takes over half an hour here, and the
recursion depth stays at k, so check_stack_depth() never fires and
nothing else stops it either. An XXX at the site says so.

Bounding the cost rather than the cycle needs a revisit key of
(elemIdx, counts) where the bitmap has only elemIdx, and that trades
the time for the space to hold it. Which is to say what this really
is, is a state explosion, and what I would do with it for now is put a
budget shaped like work_mem on the state a match may hold and refuse
past it, rather than limit what a pattern is allowed to say. Spilling
instead is not ruled out; the awkward part is that duplicate states
have to be recognised, and doing that outside memory means a hash
table per batch and a merge on the way back in, which is workable but
a considerable amount of machinery. So: the budget as the answer for
now, and the improvement thought about after.

(b) Not following the rest once a match has been recorded

Once an advance has recorded a candidate match, everything the same
advance would explore after it is less preferred and should have been
dropped. Instead those paths ran on. Some reached FIN again and
overwrote the candidate; others were parked in the state list, where a
state that survives to a later row can complete and replace the match
outright. The first is not measurable -- a match is compared by the
rows it spans, and the two candidates span the same rows -- while the
second is a wrong match once the later row arrives.

The paths meant to cut a less preferred alternative each saved
ctx->matchedState and compared it after their sub-expansion, which
answers "did the call I just made record a match" where the question
is "is there a match at all": one recorded before the save is
invisible. The fact belongs to the context rather than the frame, so
nfa_advance() clears matchUpdated when it starts and
nfa_add_matched_state() sets it; every path that would explore a
second choice stops on it, and nothing further is parked in the state
list, epsilon transitions included. Four paths had no such test at
all, three of them the greedy half of a pair whose reluctant half had
one. The fourth is nfa_advance_alt(), which walked every branch after
one had matched, and that one does move rows: (A* | B) matched empty
on a row where B would have consumed one.

The other three moved nothing in the expected output, for the reason
above, so the patch asserts what it means instead -- in
nfa_add_matched_state() that an advance records once, and in
nfa_add_state_unique() that nothing is parked after it has. rpr_nfa
drives each of the three from a query of its own, and removing any one
of them fails that file in a cassert build. I would rather have a
test that fails without the assertion, and I do not have one.

(c) Counting the iteration when a skip lands on an END

A skip path landing directly on an outer END did not count the
iteration, so a group could fail its min check having run often
enough, and the match was lost rather than mis-ordered. Two sites
need the count: the route in nfa_route_to_elem(), and the skip past an
optional group in nfa_advance_begin().

This is what (a) rests on. Below the bound the fall-through advances
the count one empty iteration at a time, and without the arrival being
counted it never meets its termination condition -- it recurses until
the stack gives out instead. The two are one design and not two
independent fixes.

One of the two sites has a test that fails when it is reverted; the
other does not, and I have not found a query that separates it.

(d) The rest

The exit convention every exit path repeated is folded into
nfa_exit_to(), and an empty match, counted as a failure in the NFA
statistics rather than the length-0 success it is, moves EXPLAIN
counters and nothing else. The below-min fall-through recurses once
per empty iteration, so its depth follows the lower bound, which a
test under a reduced max_stack_depth pins. The expected outputs that
had pinned the wrong preferment now carry the standard's values,
cross-checked against Trino and against Perl.

2005 Follow local conventions in row pattern recognition additions

Nothing to add. Include order, case order, a typedefs.list entry, a
jumble function generated for a plan-only node that no Query can
reach, and two EXPLAIN ANALYZE tests that ran bare where every other
one in the file goes through rpr_explain_filter -- which is why the
expected output had pinned "Maximum Storage: 17kB", the value the
filter exists to normalize. No functional change.

2006 Evaluate an RPR DEFINE only where the NFA maps its variable

The paragraph gave the symptom; what is worth adding is why skipping
the evaluation is allowed.

ISO/IEC 19075-5 evaluates a Boolean condition with the current row
tentatively mapped to that variable, so a variable that no state tests
is a variable whose condition the standard never asks for. The
failing query is not the executor doing extra work that happens to
raise -- it is the executor answering a question the standard did not
put.

Skipping it loses no observable side effect either, and that is the
reviewable claim in this patch: it holds because the planner already
rejects a volatile DEFINE, so the only thing an unevaluated predicate
can lose is an error.

The evaluation is lazy now, through a tri-state cache (RPRVarMatch)
that nfa_eval_var_match fills on first consumption. rpr_evaluate_row
becomes rpr_prepare_row -- it sets the row up and clears the cache --
and nfa_reevaluate_dependent_vars resets the variables that depend on
match_start rather than re-evaluating them. winstate->currentpos is
held at the scan position for the whole ExecRPRProcessRow call,
because the navigation opcodes read it during matching now.

Two cleanups ride along. The match result loses rpr_match_valid and
rpr_match_matched: rpr_match_start and rpr_match_length carry the same
information between them, with start < 0 meaning not determined, and
length -1 unmatched, 0 an empty match, 1 or more a real one.
defineVariableList goes away, only its length having been read, and
defineClauseExprs has that.

Best regards,
Henson