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