From abe7d3a66ff5f1afcaf097c61a9a7c7fb1d88728 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Sat, 5 Sep 2026 00:26:00 +0900 Subject: [PATCH] Mark two costs the RPR engine carries on purpose Two limitations the series carries knowingly met nothing at the code. nfa_states_equal() compares counts exactly. Where max is RPR_QUANTITY_INF nothing reads a count above min -- RPRElemCanLoop() is unconditionally true there and RPRElemCanExit() is already satisfied -- so two states differing only above min have the same future and still compare different. Neither in-context discard folds them back: dedup is that comparison, and the FIN pruning in nfa_advance() never fires while the pattern cannot complete. A branching unbounded pattern that never reaches FIN then holds Theta(n^2) states at peak and creates Theta(n^3) of them, each re-tested by the linear scan in nfa_append_state_unique(). (A{2,} B)+ C with C never true takes 30 ms over 80 rows, 37 s over 320, and does not finish over 640. prepare_tuplestore() allocates one mark and one read pointer for nav_winobj, and both rpr_prepare_row() and ExecRPRNavGetSlot() reach the tuplestore through it. The frontier row and the navigation target are not the same row, so the two drag the single seekpos back and forth. In memory that is a pointer move; once the tuplestore spills, tuplestore_skiptuples() is tuple-at-a-time tape I/O and work_mem rather than the data sets the cost: PATTERN (S A+) DEFINE A AS v >= FIRST(v) over 8000 rows takes 2.6 ms in memory and 24.3 s at work_mem 64kB. README.rpr said the opposite at both sites. Chapter IX called the counter saturation harmless, which it is at RPR_COUNT_INF but which says nothing about the range below it, where the same comparison is finer than the future it stands for. Chapter VI said holding nav_winobj's pointer pair apart from the other window objects leaves everyone else's fetches undisturbed, without saying that the pair's own two consumers share it with each other. Both paragraphs now carry the rest and point at the marker that measures it. The answers do not change at either site, and no code does. --- src/backend/executor/README.rpr | 15 +++++++++++++++ src/backend/executor/execRPR.c | 16 ++++++++++++++++ src/backend/executor/nodeWindowAgg.c | 15 +++++++++++++++ 3 files changed, 46 insertions(+) diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index 2786220836d..9dc934bcb76 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -917,6 +917,14 @@ RPR_COUNT_INF iterations a quantifier can neither run out nor be exceeded -- but a bare count++ added anywhere in the engine would overflow int32 instead of settling there. +That is the far end. Below it the same comparison is finer than the +future it stands for: where max is RPR_QUANTITY_INF, no decision in the +engine reads a count above min, so states differing only there behave +alike from that point on and this memcmp still keeps them apart. A +branching unbounded pattern that never reaches FIN pays for it, and the +XXX at nfa_states_equal() carries the cost and what a clamp would have +to preserve. + V-2. RPRNFAContext -- Matching Context A single context represents "a matching attempt started from a specific @@ -1279,6 +1287,13 @@ trim the tuplestore without moving anyone else's fetches. The mark only ever advances, and every RPR window gets a nav_winobj whether or not its DEFINE navigates at all. +Apart from everyone else, but not from itself: the pair is one pair, and +both rpr_prepare_row() and ExecRPRNavGetSlot() reach the tuplestore +through it. The frontier row and the navigation target are not the same +row, so the two drag the single seekpos back and forth. In memory that +costs a pointer move; spilled it costs a re-read, and the XXX at +prepare_tuplestore() carries the measurement. + Each RPRNavExpr carries a navno, its index into that list of offsets. The parser leaves it -1; compute_define_metadata() (optimizer/plan/createplan.c) numbers the navigations in walk order diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c index dd11157e4c5..29a503e52e7 100644 --- a/src/backend/executor/execRPR.c +++ b/src/backend/executor/execRPR.c @@ -282,6 +282,22 @@ nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, RPRNFAState *s2) * groups. Per the count-clear policy such a slot is zeroed when its * owning element exits (see nfa_advance_var and the inline fast path in * nfa_match), so it must not participate in equivalence judgment. + * + * XXX the comparison is finer than the future it stands for. Where max + * is RPR_QUANTITY_INF, RPRElemCanLoop() holds at every count and + * RPRElemCanExit() at every count at or above min, so two states that + * differ only above min behave identically from here on. Counts saturate + * at RPR_COUNT_INF, which is only the int32 guard, so this memcmp keeps + * such states apart and neither in-context discard folds them back: dedup + * calls them different, and the FIN early termination in nfa_advance() + * never fires while the pattern cannot complete. A branching unbounded + * pattern that never reaches FIN then holds Theta(n^2) states at peak and + * creates Theta(n^3) of them, each re-tested by the linear scan in + * nfa_append_state_unique(): (A{2,} B)+ C with C never true takes 30 ms + * over 80 rows, 37 s over 320, and does not finish over 640. Clamping the + * increment to min where max is unbounded would fold them into the memcmp + * already here, but every counts[] consumer, nfa_states_covered() + * included, has to be shown that the clamp preserves it. */ elem = &pattern->elements[s1->elemIdx]; compareDepth = elem->depth + 1; diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index d9c5b25cd3d..e9026f17c00 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -1297,6 +1297,21 @@ prepare_tuplestore(WindowAggState *winstate) * resolve_nav_offsets() runs before the first begin_partition(), so * the kind here is FIXED or RETAIN_ALL even for a parameterized * offset; RETAIN_ALL disables trim. + * + * XXX one read pointer serves two fetches that sit far apart. + * rpr_prepare_row() fetches the frontier row the NFA is advancing + * over, and ExecRPRNavGetSlot() fetches near matchStartRow for the + * FIRST family; both go through window_gettupleslot(), which seeks + * relative to seekpos, so the two drag the one pointer across the + * whole match on every row. In memory that is a pointer move, but + * once the tuplestore spills tuplestore_skiptuples() is + * tuple-at-a-time tape I/O and the cost turns quasi-quadratic: + * PATTERN (S A+) DEFINE A AS v >= FIRST(v) under work_mem 64kB takes + * 0.84 s at 2,000 rows, 5.4 s at 4,000 and 24.3 s at 8,000, against + * 2.6 ms for those same 8,000 rows in memory. The answers are + * identical either way. Separating them needs a second WindowObject + * carrying its own read pointer for match-start navigation, which + * stays inside this file. */ winstate->nav_winobj->markptr = tuplestore_alloc_read_pointer(winstate->buffer, 0);