From c2539388101eaf8c9cc5fa198a3b90d7e9346889 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Fri, 5 Jun 2026 13:07:22 +0900 Subject: [PATCH 48/68] Reformat the design-decisions chapter in the row pattern recognition README Chapter XII recorded each key design decision as a "Choice:" line plus a bulleted "Rationale:" list. Rewrite XII-1 through XII-4 as prose instead -- a short paragraph stating the decision, followed by a paragraph for its rationale -- to match the rest of the file. No rationale is dropped. XII-4 also picks up the detail, noted by Jian He, that the state and context structures live in a partition-lifespan memory context that is freed in release_partition. Documentation only. --- src/backend/executor/README.rpr | 54 ++++++++++++++++----------------- 1 file changed, 26 insertions(+), 28 deletions(-) diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index 55f899f7fef..df574a0a6f4 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -1320,47 +1320,45 @@ Chapter XII Summary of Key Design Decisions XII-1. Flat Array vs Tree-Based NFA - Choice: Flat array (RPRPatternElement[]) + The compiled pattern is stored as a flat array of fixed-size 16-byte + RPRPatternElement structs rather than as a tree. - Rationale: - - Cache-friendly: 16-byte fixed size, contiguous memory - - Index-based references: 2-byte indices instead of pointers - - Easy to serialize: can use memcpy when passing to plan nodes + The array is contiguous and cache-friendly, elements reference each + other by 2-byte index instead of by pointer, and the whole structure + can be serialized with memcpy when passed to plan nodes. XII-2. Forward-only Execution vs Backtracking - Choice: Forward-only (state set tracking) + The NFA is simulated forward-only, tracking a set of live states, + rather than by backtracking. - Rationale: - - Backtracking takes exponential time in the worst case - - NFA simulation guarantees polynomial time - - DFS order naturally guarantees preferment. - Greedy/reluctant per quantifier requires only reversing the DFS order - - Window functions receive sorted rows sequentially. - Forward-only fits directly into this pipeline, - whereas backtracking requires re-fetching previous rows - - DEFINE conditions are SQL expressions (PREV, RUNNING aggregates, etc.) - with high re-evaluation cost. Forward-only requires only one evaluation - per row + Backtracking would take exponential time in the worst case, whereas + forward-only NFA simulation is polynomial. Forward-only also fits the + window pipeline, which delivers sorted rows sequentially: it needs no + re-fetching of earlier rows, and each row's DEFINE conditions (SQL + expressions such as PREV or running aggregates, with high re-evaluation + cost) are evaluated only once. DFS order yields preferment naturally, + with greedy or reluctant behavior per quantifier obtained by reversing + that order. XII-3. Per-Context Management - Choice: Independent context per start row + A separate match context is maintained for each start row. - Rationale: - - Supports overlapping matches under SKIP TO NEXT ROW - - Determines the frame for each row independently - - Absorption optimization can eliminate redundant contexts in O(n) + This supports overlapping matches under SKIP TO NEXT ROW, determines + each row's frame independently, and lets the absorption optimization + eliminate redundant contexts in O(n). XII-4. Memory Pool Management - Choice: Custom free list + NFA states are managed through a custom free list, and both RPRNFAState + and RPRNFAContext are allocated in a partition-lifespan memory context + that is freed in release_partition. - Rationale: - - NFA states are created and destroyed in large numbers per row - - Avoids palloc/pfree overhead - - State size is variable (counts[] array), but within a single query - maxDepth is fixed, so all states have the same size + NFA states are created and destroyed in large numbers per row, so the + free list avoids palloc/pfree overhead. Their size varies (the + counts[] array), but maxDepth is fixed within a single query, so all + states have the same size. XII-5. Execution Optimization Summary -- 2.50.1 (Apple Git-155)