Re: Row pattern recognition

Hi Henson,

> Hi Tatsuo,
>
> Attached are 6 incremental patches on top of v46.

Thank you!

> 0001-0005 are small independent fixes. 0006 is the main
> PREV/NEXT navigation redesign that was discussed as the
> "experimental" implementation in prior messages.
>
> Here is a summary of each patch:
>
>
> 0001: Remove unused regex/regex.h include from nodeWindowAgg.c
> The regex header was left over from an earlier implementation
> that used the regex engine for pattern matching. The current
> NFA engine in execRPR.c does not use it.

Good catch!

> 0002: Add CHECK_FOR_INTERRUPTS() to nfa_add_state_unique()
> This function iterates through a linked list of NFA states
> to check for duplicates. In state explosion scenarios
> (complex patterns with alternations and quantifiers), this
> list can grow significantly. Without an interrupt check,
> the loop is unresponsive to query cancellation.

Looks good to me.

> 0003: Add CHECK_FOR_INTERRUPTS() to nfa_try_absorb_context()
> Similar to 0002. The absorption loop iterates through the
> context chain, which can grow unbounded with streaming
> window patterns. Each iteration also calls
> nfa_states_covered() which has its own loop.

Looks good to me.

> 0004: Fix in-place modification of defineClause TargetEntry
> In set_upper_references(), the defineClause TargetEntry
> was modified in-place by fix_upper_expr() without making
> a copy first. This follows the same flatCopyTargetEntry()
> pattern already used for the main targetlist in the same
> function.

Probably we want to modify the comment above since it implies an
in-place modification? What about something like this? (Modifies -> Replace)

/*
* Replace an expression tree in each DEFINE clause so that all Var
* nodes's varno refers to OUTER_VAR.
*/

> 0005: Fix mark handling for last_value() under RPR
> This is a revised version of the v45 0004 patch that you
> commented on [1]. You pointed out that suppressing
> WinSetMarkPosition() entirely under RPR was too strong a
> limitation, and we agreed to drop it and revisit together
> with the experimental PREV/NEXT patch.
>
> The RPR executor patch changed set_mark from true to
> false in window_last_value() to avoid mark advancement
> problems under RPR. But this also penalizes non-RPR
> queries by preventing tuplestore memory reclamation.
>
> The revised approach: restore set_mark=true (upstream
> default), and add a targeted guard in
> WinGetFuncArgInFrame() that only suppresses mark
> advancement for SEEK_TAIL under RPR -- not for all
> seek types as in v45 0004. Only SEEK_TAIL needs
> suppression because advancing the mark from the tail
> could prevent revisiting earlier rows that still fall
> within a future row's reduced frame.

I think instead we can set a mark at frameheadpos when seek type is
SEEK_TAIL and RPR is enabled. See attached patch.

> 0006: Implement 1-slot PREV/NEXT navigation for RPR
> This is the main patch. It redesigns PREV/NEXT navigation
> from the 3-slot model (outer/scan/inner with varno
> rewriting) to a 1-slot model using expression opcodes.
>
> Key changes:
>
> - RPRNavExpr: a new expression node type that replaces
> the previous approach of identifying PREV/NEXT by
> funcid. The parser transforms PREV/NEXT function calls
> into RPRNavExpr nodes in ParseFuncOrColumn().
>
> - EEOP_RPR_NAV_SET/RESTORE: two new opcodes that
> temporarily swap ecxt_outertuple to the target row
> during expression evaluation. The argument expression
> evaluates against the swapped slot, then the original
> slot is restored. This eliminates varno rewriting and
> naturally supports arbitrary offsets.
>
> - 2-argument form: PREV(value, offset) and
> NEXT(value, offset) are now supported. The offset
> defaults to 1 if omitted; offset=0 refers to the
> current row. The offset must be a run-time constant
> per the SQL standard.
>
> - nav_winobj: a dedicated WindowObject with its own
> tuplestore read pointer, separate from aggregate
> processing. A mark pointer pinned at position 0
> prevents tuplestore truncation so that PREV(expr, N)
> can reach any prior row. This is conservative -- it
> retains the entire partition -- but since the standard
> requires offsets to be run-time constants, we could
> advance the mark to (currentpos - max_offset) in a
> future optimization. I'd prefer to defer that until
> the basic navigation is stable.
>
> - Documentation and tests updated.
>
>
> Changes from the experimental version of 0006:
>
> - NULL/negative offset error rationale changed from "matching
> Oracle behavior" to the SQL standard (ISO/IEC 9075-2,
> Subclause 5.6.2: "There is an exception if the value of
> the offset is negative or null"). The behavior is the same;
> only the comment was corrected.
>
> - RPRNavKind changed from -1/+1 values to plain enum values.
> The previous version used kind as an arithmetic multiplier
> (offset * kind), but this pattern cannot extend to FIRST/LAST
> which have different position semantics. The new version uses
> a switch statement with pg_sub/add_s64_overflow instead.
>
> - Parser validation walkers consolidated from three separate
> walkers into a single NavCheckResult struct + nav_check_walker,
> reducing tree traversals from up to 4 per RPRNavExpr to 1-2.
>
> - JIT changed from attempting to compile to explicit interpreter
> fallback. See item 2 below for the rationale.
>
> - Additional test cases for subquery offset (caught by
> DEFINE-level restriction), first-arg subquery, and first-arg
> volatile function (allowed per standard).
>
> I've reviewed and revised 0006 since the experimental version.
> I think it is now ready to be included in the next version of
> the patch set. It passes all existing regression tests (rpr,
> rpr_base, rpr_explain, rpr_nfa) and adds comprehensive tests
> for the new functionality.

Excellent! I will take a look at it. (it will take for a while).

> Two items I'd like your opinion on:
>
> 1. 0005 (mark handling): The revised approach only suppresses
> mark advancement for SEEK_TAIL under RPR, unlike v45 0004
> which suppressed it for all seek types. Does narrowing to
> SEEK_TAIL seem reasonable to you, or do you see cases where
> other seek types could also be affected?

See the comment above.

> 2. LLVM JIT fallback (in 0006): The mid-expression slot swap
> conflicts with how JIT caches tuple data pointers. The
> experimental version produced wrong results under
> jit_above_cost=0, and I have not found a clean fix within
> the current JIT framework. For now, DEFINE expressions
> containing PREV/NEXT fall back to the interpreter; other
> expressions in the same query are still JIT-compiled.
> I'd like to keep this as-is for now and look for a proper
> JIT solution over time. Does that sound reasonable?

I am not an expert of JIT, but for me, it sounds reasonable. We can
enhance it later on.

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