Row Pattern Recognition 深入探討

§1. 標準、子集，以及尚未解決的問題

1.1 標準範圍

Row Pattern Recognition 由 ISO/IEC 9075-2:2016 引入 SQL，並於配套文件 ISO/IEC 19075-5:2021（第 5 部分，「Row Pattern Recognition」）中加以描述。

標準為相同的底層機制定義了兩種介面。Feature R010 在 FROM 清單中放入 MATCH_RECOGNIZE 子句以產生衍生資料表；Feature R020 則將相同的 pattern 邏輯整合進 WINDOW 規格中，以產生 window function 的輸出。兩種介面共用大部分語法以及所有語意，但它們是功能上不同的進入點 — 資料庫可實作其一或兩者皆實作。

此處討論的 patch 系列僅實作 R020 的子集；資料表子句形式刻意不在範圍內。

R020 介面雖小但具表達力。查詢透過在 window 規格中加入三個子句以將 pattern 附加到 window：PATTERN 以具名 pattern 變數描述一個 regular expression，DEFINE 提供識別每個變數的 Boolean 述詞，AFTER MATCH SKIP 則控制連續的 match 在 partition 內如何定位。

可選的 MEASURES、SUBSET、INITIAL/SEEK，以及輔助函數 CLASSIFIER() 構成此 feature 的其餘部分。（標準中的 MATCH_NUMBER() 函數僅屬於 R010 介面 — 19075-5 §6.3.3 (6) 明確將其排除於 R020 之外。）

此 patch 涵蓋的語彙已足以使非平凡的查詢運作，但對於若干實作上仰賴尚未建置的基礎設施的構造則不予實作。

本節其餘部分將標準的語彙劃分為 patch 已支援者，以及刻意保留待日後實作者。下列清單反映目前 patch 系列的狀態。

1.2 已實作的 feature

已實作的語彙足以表達促成 row pattern recognition 出現的典型 V 形、W 形與反轉 pattern。它亦涵蓋所有標準量詞 — 包括所有七個 reluctant 變體 *?、+?、??、{n}?、{n,}?、{,m}?、{n,m}? — 以及 DEFINE 條件比較相鄰列所需的四個導覽 primitive。

PATTERN 子句

於 window 規格中定義 row pattern。

Regex：+ * ? |

標準量詞與替代（alternation）。

Regex：( ) 群組

以括號包圍的子 pattern。

Regex：{n} {n,} {,m} {n,m}

具邊界的重複次數。

Reluctant *? +? ?? {n}? {n,}? {,m}? {n,m}?

標準定義的所有七個 reluctant（非貪婪）變體（排除於 absorption 最佳化之外）。

DEFINE 子句

用以識別每個 pattern 變數的 Boolean 條件。

通用列模式變數

DEFINE 中未限定的欄位參照（例如裸的 Price）會解析為目前列，依據 19075-5 §4.10/§4.16。

PREV、NEXT（含 offset）

取得目前列之前／之後 n 列（預設為 1）；內部引數為任意值運算式，於被導覽的列上評估。

FIRST、LAST（含 offset）

取得相對於 match 的列；FIRST(expr, n) 指向 match 起始之後第 n 列，LAST(expr, n) 指向最近 match 列之前第 n 列。

複合導覽（四種形式）

於內部 FIRST/LAST 之上疊加外部的 PREV/NEXT 步驟：PREV(FIRST(expr))、NEXT(FIRST(expr))、PREV(LAST(expr))、NEXT(LAST(expr)) — 內外步驟皆可接受各自的 offset。

INITIAL

Pattern match 必須從目前列開始（預設）。

AFTER MATCH SKIP PAST LAST ROW

預設的 skip 模式；可進行 context absorption。

AFTER MATCH SKIP TO NEXT ROW

允許重疊的 match；停用 absorption。

1.3 尚未實作

尚未實作的 feature 大致可分為三群。第一群 — 也是規模最大的一群 — 是圍繞 MEASURES 的構造系列：MEASURES 子句本身、SUBSET、CLASSIFIER()、像 B.price 這樣以 pattern 限定的欄位參照，以及像 LAST(B.price) 或 PREV(B.price) 這樣以 pattern 限定的導覽。

這些並非彼此獨立的缺口，而是單一缺失元件的不同面向：executor 必須保留每個 match 的歷史 — 對 match 中每一列記錄它被對應到哪個 pattern 變數 — 沒有它，這些構造均無有意義的定義。CLASSIFIER() 從該記錄中讀取變數名稱；B.price 讀取記錄項為 B 的列的 price 欄位；LAST(B.price) 走訪相同的列集並挑出最後一個；SUBSET U = (A, B) 定義了一個虛擬變數來彙整兩個 bucket；而 MEASURES 則正是利用此彙整來評估 AVG(U.Price) 之類的運算式。

目前的 executor 逐列評估 DEFINE 述詞，但並未在任何地方記錄所得的變數指派 — 沒有東西可供日後查詢。因此，建立歷史基礎設施是整個群組的前提；一旦記錄存在，個別 feature 便可作為簡單的投影自然呈現。

第二群與替代的 skip 目標有關：AFTER MATCH SKIP TO label、AFTER MATCH SKIP TO FIRST var、AFTER MATCH SKIP TO LAST var。這些同樣仰賴 match 歷史，因為 executor 必須能夠指向最近一次 match 中某個具名的列。

其餘項目是混雜的尾巴：SEEK 關鍵字（INITIAL 的替代品）、空 pattern ()、排除形式 {- … -}，以及不在意順序的 PERMUTE 運算子。

MEASURES

每個 match 的具名輸出運算式，例如 MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg；於 R020 中藉由 OVER 如同 window function 般呈現。接受 FINAL / RUNNING 關鍵字（19075-5 §5.4），於 R020 中兩者會收斂為相同值，因為 measure 總是於 match 的最後一列評估（19075-5 §6.9 (3)）。

SUBSET

具名的 pattern 變數聯集，例如 SUBSET U = (A, B, C)。可於任何能參照 pattern 變數的位置使用 — MEASURES、DEFINE 中的 pattern 限定參照、CLASSIFIER(U) — 全都需要 match 歷史。

CLASSIFIER()

傳回某一列被 match 為哪個 pattern 變數。於 DEFINE 與 MEASURES 皆有定義（19075-5 §5.9）；任一列的答案就是該列在 match 歷史中所記錄的變數名稱。

Pattern 限定的欄位參照

於 DEFINE 或 MEASURES 中的裸 B.price — 從被對應為具名變數的列中取得該欄位的值。

Pattern 限定的導覽

將導覽限制於被 match 為具名變數的列，例如 LAST(B.price)、FIRST(B.price)、PREV(B.price)、NEXT(B.price)。

SEEK

Match 可從 window 中任意位置開始（相對於 INITIAL）。

AFTER MATCH SKIP TO label

跳到具名標籤的列。

AFTER MATCH SKIP TO FIRST var

跳到被 match 為具名變數的第一列。

AFTER MATCH SKIP TO LAST var

跳到被 match 為具名變數的最後一列。

Regex：{- -}

排除 — 將 match 到的列從每個 match 的輸出中移除。

Regex：()

空 pattern — 匹配空序列。

PERMUTE(...)

對所列變數進行不在意順序的匹配。

DEFINE 中的彙總函數

於 DEFINE 述詞中不允許 SUM、AVG、COUNT 等彙總。標準允許它們作為對部分 match 的 running aggregate（針對已被對應到變數的列做逐列評估），這仰賴 MEASURES/CLASSIFIER() 所需的同一份每 match 歷史。

此處還有四點值得注意，因為它們容易被誤認為遺漏。

第一點是：標準本身不允許在 WINDOW 子句中與 RPR 一起使用 pattern anchor ^ 與 $（19075-5 §6.13：「the anchors (^ and $) are not permitted with row pattern matching in windows」；底層定義於 19075-5 §4.14.1）；它們不存在屬於符合規範，而非缺口。

第二點是：MATCH_NUMBER() 同樣被標準排除於 R020 之外（19075-5 §6.3.3 (6) 與 19075-5 §6.9 (1)） — 它僅屬於 R010 介面，這裡缺席同樣屬於符合規範，而非缺漏 feature。

第三點是標準對 R020 施加的一組結構性禁止（19075-5 §6.17）：row pattern recognition 不能巢狀在另一個 row pattern recognition 中；MEASURES 與 DEFINE 不得包含外部參照；MEASURES 或 DEFINE 中的子查詢不得參照 row pattern 變數；RPR 也不得在遞迴查詢中使用。

第四點是：MATCH_RECOGNIZE 本身 — Feature R010，同一機制的資料表子句介面 — 不在本 patch 範圍內。PostgreSQL 是否最終會加入 R010 是未來系列的問題，並非衡量本系列的標準。

§2. 範例 — 它實際如何執行

本節範例採漸進方式建立。我們先從概念上說明為何 row-pattern 匹配與 string-pattern 匹配確實不同，接著介紹使 DEFINE 條件富有意義的四個導覽函數，最後走過三個端到端的追蹤：單一 match（NFA 移動）、容易情境下的 context absorption，以及 absorption 變得不安全的情境。

讓導覽變得低成本的內部機制 — 1-slot tuple 交換 — 屬於 executor 的設計，將於下一節說明，本節不涵蓋。

2.1 為何 row pattern 與文字 pattern 不同

文字 regular expression 匹配的是字元流，每個位置都恰好只有一個符號需考慮。執行時的問題 — 「目前符號是否等於 'A'？」 — 只有一個是／否答案。回溯式自動機善用此特性：每個字元最多保留一條分支，模糊性的成本透過重新讀取輸入來支付。

Row pattern 則在根本上不同。一列並不是單一符號；它是一組欄位的 tuple，針對一組 Boolean 述詞 — 即 DEFINE 條件 — 進行評估。兩個述詞可以同時對同一列為真，標準也沒有規定它們必須互斥。考慮以下情境：

DEFINE
  A AS price > 100,
  B AS volume > 1000,
  C AS price > 200

一列若 price = 150, volume = 2000 同時滿足 A 與 B 但不滿足 C。Pattern matcher 無法將此情況收斂為單一狀態 — 有兩個 pattern 變數同時存活，且任何指稱其中之一的 pattern 元素皆可推進。因此 NFA 必須每個 partition 列同時帶有多個狀態，而非僅一個。

這個觀察驅動了整個架構的其餘部分。執行狀態是一張 context 清單，每個 context 是一張 state 清單，每一列上 runtime 對每個 state 詢問：「給定此處為真的變數，我能去哪裡？」由此產生的分叉，正是 runtime 需要多層修剪的原因 — context 內部的 state 去重、跨 context 的 absorption，以及 §3.6 探討的其他規則 — 缺少這些，存活的 state 與 context 數量會隨 partition 增長，pattern 匹配將變為超線性。

2.2 導覽函數

僅參照目前列的 DEFINE 條件能力有限；幾乎每個有意思的 pattern 都需要將目前列與其鄰居或先前已接受的列比較。標準為此提供四個導覽函數，patch 全數實作。

PREV(expr [, n])

目前列之前 n 列的列（預設 n = 1）。用於「今天 vs. 昨天」的比較。

NEXT(expr [, n])

目前列之後 n 列的列。向前 look-ahead；在 window 形式下不常見，因為 window 是單調的。

FIRST(expr [, n])

目前 match 的第 n 個 match 列，從起點開始計數。「與開始此 match 的列比較。」

LAST(expr [, n])

最近第 n 個 match 到的列。「與最近 match 到的列比較。」

這四個 primitive 可以組合：PREV 與 NEXT 可包覆 FIRST 或 LAST 呼叫，形成四種複合形式，語意為「先到相對於 match 的某列，再從該列固定距離地移動」。這正是讓 DEFINE 運算式可以讀取例如 match 開始前一列的方式。

PREV(FIRST(expr [, n]) [, m])

從 match 的第 n 列往回 m 列（預設 m = 1）。「此 match 開始前的值是什麼？」

NEXT(FIRST(expr [, n]) [, m])

從 match 的第 n 列向前 m 列。可在不依賴目前列的情況下深入 match。

PREV(LAST(expr [, n]) [, m])

從最近第 n 個 match 到的列往回 m 列。「與最近 match 之前不久的列比較。」

NEXT(LAST(expr [, n]) [, m])

從最近第 n 個 match 到的列向前 m 列。

這裡有兩個實務要點值得指出。其一，導覽可以複合：PREV(FIRST(price)) 讀取 match 開始前一列，patch 支援此寫法。其二，導覽會影響 executor 的最佳化。PREV 與 NEXT 相對於目前列，永遠是安全的；FIRST 與帶 offset 的 LAST 變體則相對於 match 邊界，會與 context absorption 互動，並迫使 planner 保留某些原本會丟棄的 context。此互動背後的機制將在 §2.6 說明。

2.3 實作範例 1 — NFA 移動

SELECT company, tdate, price,
  first_value(price) OVER w AS start_price,
  last_value(price)  OVER w AS end_price
FROM stock
WINDOW w AS (
  PARTITION BY company ORDER BY tdate
  ROWS BETWEEN CURRENT ROW
       AND UNBOUNDED FOLLOWING
  AFTER MATCH SKIP PAST LAST ROW
  PATTERN (START UP+ DOWN+)
  DEFINE
    UP   AS price > PREV(price),
    DOWN AS price < PREV(price)
);

此 pattern 攤平為四個元素：

[0] START  quant 1..1   next → 1
[1] UP     quant 1..∞   next → 2
[2] DOWN   quant 1..∞   next → 3
[3] #FIN

對於價格序列 100, 110, 120, 115, 108, 130：

重點：在第 3 列，該列同時滿足 START（恆為真）與 DOWN，但從第 2 列存活下來的 state 只在 DOWN-exit 分支上，因此只走 UP → DOWN 轉移。§2.1 的多狀態本質在每次 UP 匹配時以 fan-out 形式可見（state 可留在 UP+ 或推進至 DOWN+）。Greedy 偏好是「先迴圈再離開」，因此在資料足夠時迴圈分支會延伸 match 更遠；這裡迴圈中的 DOWN 在第 5 列消亡（130 ≮ 108），稍早的 FIN 候選（第 0–4 列） — 由 DOWN 在第 4 列離開時產生 — 被定案為 match。

此查詢的結果直接源自此追蹤。在 RPR 語意下，window function first_value(price) 與 last_value(price) 僅在啟動 match 的列上評估 — match 中的其他每一列對這些 window function 皆產生 NULL，因為其 reduced frame 為空。因此我們資料的輸出長得像海報右上面板所展示的表格：

第 0 列是 match 起點，所以它的 frame 涵蓋第 0–4 列，window function 回報 V 形的開盤價（$100）與最低價（$108）。第 1–4 列雖在 match 中但非起點，所以它們收到 NULL。第 5 列（價格 $130）位於任何 match 之外，同樣收到 NULL。

2.4 實作範例 2 — 替代與字面順序

(A | B) 形式給予 matcher 選擇：在任何列上，兩個替代會獨立測試，且任意數量皆可匹配。這是 §2.1 的多狀態本質在單一 context 內變得可見的場合 — 不是跨 context（那是 absorption），而是沿著 executor 同步探索的平行分支。

PATTERN ((UP | HIGH) DONE)
DEFINE
  UP   AS price > PREV(price),
  HIGH AS price > 100,
  DONE AS volume > 1000

想像有一列其價格既上漲又超過 $100 — UP 與 HIGH 同時為真。每個替代會產生自己的 state：其一走 UP 分支，其一走 HIGH 分支。兩者平行進行，直到 DONE 將它們解決。

兩個分支對相同列產生相同長度的 match，讓 matcher 有兩條候選路徑 — 一條標示為 UP, DONE，另一條標示為 HIGH, DONE。標準以字面順序解決此情況：在 (UP | HIGH) 中所寫的替代中，先寫者勝出，與 match 長度無關。因為 UP 出現在 HIGH 之前，存活的路徑是 UP, DONE。

字面順序使得 CLASSIFIER() 最終實作時能有明確定義 — 它讓 runtime 能告訴使用者「此列被匹配為 UP，非 HIGH」，即便兩個述詞皆為真。字面順序是替代的主要規則：字面較早的分支勝過字面較晚者，即使較晚者會產生較長 match；而當每個較早分支都在到達 FIN 前消亡時，較晚（可能較短）的分支仍可勝出。Greedy 長度則於單一量詞內部決定 — 給定同一替代分支的兩種完成方式，greedy 量詞偏好更多次迭代。

2.5 實作範例 3 — Context absorption（命運相同）

展現 absorption 的最簡單 pattern 是 PATTERN (A+) 配上 DEFINE A AS TRUE。每列皆匹配 A，標準要求 matcher 將每列都視為可能的 match 起點。素樸地看，這對 N 列 partition 意味 N 個 context。取一個五列 partition（任何資料皆可 — 述詞恆為真）：

記憶體從 O(n) 縮減為 O(1)。在量詞無上界時，使丟棄合理化的 absorption 規則非常直接：

海報左下面板（「① Context Absorption」）就是此規則在五列上的視覺化。

規則中藏著一個微妙但重要的點：丟棄之所以安全，是因為述詞 A AS TRUE 在每列都評估為相同值，無論哪個 context 在問。任何僅參照目前列或其固定 offset 的述詞 — 包括 PREV — 也是如此。下一個範例改用具體的一週價格，使用以 PREV 為基礎的述詞，§2.6 會重複使用同一週，以使安全與不安全 absorption 之間的對稱性顯而易見：

PATTERN (RISE+)
DEFINE RISE AS price > PREV(price)

取一週交易日 $100、$108、$112、$116、$110，從週一到週五 — 四次上漲後驟然下跌。假設 C1 於週二開始（RISE 第一次匹配的日子：$108 > $100），executor 也推測性地追蹤 C2 從週三開始。每列的 RISE 條件比較該列價格與其前一列 — 這是 partition 層級的事實，而非 context 層級 — 所以兩個 context 在它們共享的每一列都被迫計算相同的 Boolean：

當述詞開始依賴每個 context 自身的邊界時，故事就破滅了 — 這正是 §2.6 要談的。

2.6 實作範例 4 — Absorption 何時變得不安全

假設一位分析師想找出股價維持在 run 開始當日上下 10 美元範圍內的連續交易日 — 一種盤整視窗。Pattern 與 DEFINE 如下：

PATTERN (STABLE+)
DEFINE STABLE AS price < FIRST(price) + 10

此條件改為比較目前列的價格與目前 run 起始當日的價格。從不同日子開始的兩個 run 擁有不同的 FIRST(price) 值，所以兩個位於相同 pattern 元素、相同計數的 state 不再可互換：它們的未來取決於原本要被 absorption 丟棄的邊界。

取與 §2.5 完全相同的交易週 — $100、$108、$112、$116、$110，從週一到週五。Runtime 同樣同時保留兩個候選 run：C1 從週一開始，C2 從週二開始（在 STABLE+ 下，每一列都是潛在 run 起點）。

在 absorption 之下，C2 會於週二被併入 C1 — 合併後的 context 只保留一個上限，因此 C2 獨特的視角（上限 $118、那個只到週六才結束的四日 run）便無法從內部狀態回復。C2 必須存活，因為它是 runtime 仍可能需要的獨立 match 候選：一旦 C1 的 match 在週三結束，下一次嘗試必須從仍在進行的 C2 接續，而非從頭重啟。因此每當 DEFINE 述詞帶有 match-start 依賴時，planner 就會預先停用 absorption。

（當領先 context 的 match 確實成功時，於其接受範圍內開始的 context — 在預設 AFTER MATCH SKIP PAST LAST ROW 之下 — 會直接被丟棄；它們保留存活只是為了在領先 match 失敗時 runtime 有後備可用。）

海報右下面板（「② Navigation」）的依賴表彙整哪些導覽形式會產生 match-start 依賴：

§2.5 與 §2.6 的兩個範例可歸納為單一規則。命運相同使得 absorption 安全：若同一 pattern 元素上的每個 context 對於每個未來述詞都會算出相同答案，那麼只需保留最舊的即可。命運不同使 absorption 不安全：一旦述詞依 context 私有狀態而分歧 — 這正是 FIRST 與帶 offset 的 LAST 所做的 — 每個存活 context 都代表其他 context 無法回復的未來，丟棄其中任一個都可能導致錯誤答案。

Planner 在編譯期偵測此區別，並逐 context 決定是否套用 absorption。這也是為何海報面板 ③ 的 benchmark 在成功與失敗情況下皆維持線性：當 absorption 安全時，runtime 收斂 context；當不安全時，planner 寧可承擔多 context 成本，也不冒錯誤答案的風險。

海報上的 benchmark 數字就是相同演算法在大規模下的表現。在成功 pattern (A+ B+ C+ D) 上，PostgreSQL 與 Trino 在 match 確認後皆呈 O(n)，而 PostgreSQL 領先約 16× 至 33× — 大部分來自 JVM 差距。

在失敗 pattern (A+ B+ C+ E) 上，Trino 沒有 absorption，會退化為 O(n²) 追蹤每個潛在 match 起點；在 100,000 列時需超過五小時，而 PostgreSQL 仍在 92 ms 內完成，加速約 217,000×。

此差距並非工程上的精修 — 而正是 §2.5 與 §2.6 中命運相同／命運不同的區別，套用於 partition 中每個潛在 match 起點的每一列。

2.7 實作範例 5 — 當 SKIP 停用 absorption

上一個範例從資料面打破 absorption：DEFINE 中的 FIRST 使每個 context 以不同方式評估述詞。Absorption 也可從輸出面被打破，控制此情況的是 AFTER MATCH SKIP 子句。

考慮 pattern PATTERN (A+) 配上 DEFINE A AS TRUE，作用於五列且全部匹配 A。在預設 AFTER MATCH SKIP PAST LAST ROW 下，matcher 找到從最早列開始的最長 match，然後跳過它；任何於該 match 內開始的 context 都因冗餘而被隱式丟棄 — 正是 absorption 設計處理的情境。輸出是單一 match，第 0–4 列，runtime 只需一個存活 context。

將 skip 模式切換為 AFTER MATCH SKIP TO NEXT ROW，契約就變了：

PATTERN (A+)
DEFINE A AS TRUE
AFTER MATCH SKIP TO NEXT ROW

現在每個潛在起始位置都必須個別回報，即使 match 重疊也是如此。對相同的五列，runtime 必須輸出五個 match：第 0–4、1–4、2–4、3–4 與 4–4 列。這些都不能被「從更早開始的較長者」取代，因為標準規定使用者想要全部。

注意述詞並未改變。A AS TRUE 在每列都以相同方式評估，無論哪個 context 在問，所以 §2.5 的命運相同條件仍然成立。改變的是輸出需求：即使擁有相同未來的 context 也必須共存，因為它們對應結果中不同的列。因此只要 AFTER MATCH SKIP TO NEXT ROW 生效，無論 DEFINE 子句為何，planner 都會停用 context absorption。

將 §2.6 與 §2.7 並列，便可看見 absorption 失效的全貌：

任一條件都足以對受影響的 context 停用 absorption。當兩者皆未生效時 — 預設 AFTER MATCH SKIP PAST LAST ROW 配上僅使用 PREV、NEXT 或裸 LAST 的 DEFINE 條件 — runtime 對每個 pattern 位置收斂為單一 context，並全程維持線性。

§3. 設計 — 從 Parser 到 Executor

Row Pattern Recognition 由三個階段實作，並透過明確定義的中介形式交接工作。Parser 將 SQL 文字轉為 pattern tree 與 DEFINE 述詞清單；planner 將該 tree 編譯為扁平的 pattern 元素陣列，並決定哪些元素可參與 context absorption；executor 以三階段迴圈逐列對 partition 執行該陣列。每個階段有自身的資料形狀，而大部分設計巧思皆在邊界處：可放入 cache 的扁平 NFA、重複使用單一 tuple slot 而非為每次參照具現化一個的導覽模型，以及將 O(n²) 記憶體轉為 O(n) 的 absorption 規則。

SQL 文字
  │
  │  parser 階段
  ▼    驗證 frame
       建立 pattern tree
       對 DEFINE 進行型別檢查

pattern tree + DEFINE 清單
  │
  │  planner 階段
  ▼    最佳化 tree
       編譯為扁平 NFA 陣列
       判斷可吸收性

扁平 NFA + absorption 旗標
  │
  │  executor 階段
  ▼    逐列引擎：
       Match → Absorb → Advance

match 結果：
  start 列、長度、成功／失敗

以下各節沿此管線往下走。§3.1 涵蓋 parser 與 pattern tree 的形狀；§3.2 涵蓋將 tree 轉為扁平 NFA 的編譯；§3.3 涵蓋 DEFINE 述詞用以檢視鄰近列的導覽模型；§3.4 涵蓋 match 邊界處理 — 固定 match 起訖位置的 SKIP、INITIAL 與有界 frame 規則；§3.5 是逐列三階段引擎；§3.6 彙整所有讓狀態空間有界的修剪機制；§3.7 概觀此實作於 EXPLAIN 輸出中所呈現的內容。

3.1 Parser — 建立 pattern tree

Parser 透過 window 規格中是否存在 PATTERN 子句來辨識 pattern recognition。它首先要做的工作是 frame 驗證，因為 RPR 加上了一般 window 查詢沒有的限制：frame 模式必須為 ROWS（而非 RANGE 或 GROUPS），起始邊界必須為 CURRENT ROW，且禁止 EXCLUDE 選項。這些是符合規範的檢查，而非最佳化 — RPR 對 frame 的概念是match span，標準並未設想以匹配列以外的東西去填它。

一旦 frame 通過驗證，parser 便將 PATTERN 子句轉為由四種節點組成的 tree — 變數參照、sequence（串接）、alternation，以及 group（以括號包圍的子 pattern）。每個節點以三個數字攜帶量詞 — 下界、上界（可能為無限），以及 reluctant matching 旗標：

每個 DEFINE 述詞接著針對 partition 欄位進行型別檢查，並強制轉型為 Boolean 運算式。過程中會發生兩件實際的事。第一，DEFINE 述詞所參照的每個欄位都會被登錄為查詢輸出需求的一部分，因此即使外層查詢未選擇這些欄位，planner 也會把它們傳遞至 executor 階段 — 否則 runtime 沒有可評估的對象。第二，出現在 PATTERN 但從未出現在 DEFINE 中的變數隱式為真：它們匹配每一列。

3.2 編譯 — 從 AST 到扁平 NFA

Planner 將 parser 的 tree 轉為 executor 將執行的資料結構：以索引定址的扁平 pattern 元素陣列。編譯為一個六步驟的管線：

compile(astTree)：
  1. 最佳化 AST
  2. 量測大小與深度
  3. 配置元素陣列
  4. 由 AST 填入
       （指派 next/jump 指標）
  5. 收尾 — 設定 FIN sentinel
  6. 標示 absorption 合格的元素

選用扁平形狀的理由很簡單：executor 每個 partition 必須走訪 pattern 多次，而連續且可索引的陣列是走訪成本最低的資料結構。第 1 步與第 6 步是有趣的部分 — 第 1 步因為它決定陣列大小，第 6 步因為它決定 §2.5 的 absorption 最佳化是否會啟用。

AST 最佳化

最佳化雙倍受益：一次在扁平陣列的靜態元素數量上，另一次在 runtime 處理的每一列上。每個變換都減少 runtime 必須列舉的狀態空間。最佳化器依序套用八個重寫規則，直到 AST 不再改變：

SEQ 攤平

SEQ(A, SEQ(B, C)) → SEQ(A, B, C)

連續變數合併

A A → A{2}
A{2,3} A{1,2} → A{3,5}

連續 group 合併

(A B)+ (A B)+ → (A B){2,∞}

連續 ALT 合併

(A | B) (A | B) (A | B) → (A | B){3}

前綴／後綴吸收

A B (A B)+ → (A B){2,∞}

ALT 攤平與去重

(A | (B | C)) → (A | B | C)
(A | B | A) → (A | B)

量詞相乘

(A+)+ → A+
(A{2,3}){5} → A{10,15}

單子節點 unwrap

SEQ(A) → A
(A){1,1} → A

量詞相乘是唯一需要安全性檢查的變換：最佳化器只在三種安全情況下收斂 — 兩個量詞皆無上界（(A+)+ → A+）、外部為精確值（(A{2,3}){5} → A{10,15}），或子節點為平凡的 {1,1}（(A){2,5} → A{2,5}）。其他組合可能引入扁平形式會遺漏的缺口 — 例如 (A{2}){2,3} 只接受 {4, 6}，但素樸的 A{4,6} 也會接受 5 — 因此最佳化器將它們保持原樣。

元素形狀

扁平陣列的每個元素代表 pattern 中的單一位置。共有五種邏輯類型：變數參照（唯一會消耗一列的類型）；group 起始與group 結束標記，用來開啟與關閉以括號包圍的子 pattern；alternation 標記，作為一系列分支的開頭；以及位於 pattern 末端的結束標記。

每個元素也攜帶深度（其 group 巢狀層級）、量詞（最小與最大重複次數，可能為無限）以及兩個轉移指標 — next，「消耗此元素後要去哪裡」，以及 jump，「要跳到何處」（alternation 用以串連分支；group 起始在量詞允許 0 時用以略過本體；group 結束用以迴圈回到本體）。

對於 PATTERN ((A B)+)，編譯後的陣列如下：

PATTERN ((A B)+) 編譯為：

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    （開啟 group；jump 在 min = 0
     時略過至 FIN）

[1] A      depth 1  quant 1..1
    next → 2

[2] B      depth 1  quant 1..1
    next → 3

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    （關閉 group；jump 迴圈回去）

[4] FIN    pattern 完成

Pattern 透過 next 由左至右讀取，jump 處理非線性邊。在 idx 3，END 的 jump 指回 idx 1，這就是無上界外層量詞如何迴圈的方式；在 idx 0，若 group 為選擇性（optional），BEGIN 的 jump 會略過 END 到 idx 4。Runtime 永不必在執行期建構圖 — 它只在走訪陣列時跟隨這兩個指標。

每元素屬性

除形狀外，每個元素攜帶四個邏輯屬性，引導 runtime 在該位置的行為：

Reluctant

反轉量詞展開的順序。Greedy 量詞會先嘗試「再次迴圈」再「離開」；reluctant 量詞先嘗試「離開」。對於 A+?，由變數攜帶；對於 ((…)+?)，由 group 的 BEGIN 與 END 攜帶。

Empty-loopable

設於本體可為空的 group end（(A?)*、(A? B?)+、(A | B*)）。指示 runtime 在一般 loop-back 之外加上快速前進離開，以避免 cycle guard 在可產生空迭代的 group 中扼殺合法 match。

In-absorbable-region

標示位於 absorption 合格區域內的每個元素 — 由 runtime 用以追蹤目前 state 是否仍在安全範圍內。

Absorption-comparison-point

標示應執行 absorption 比較的特定元素。對於簡單的 A+，標示落在變數上；對於像 (A B)+ 這樣的無上界 group，僅落在 group end 上。

區分「in-region」與「comparison-point」很重要，因為 absorption 只在迭代收尾的位置才有意義。在 (A B)+ 的本體中，runtime 正處於迭代中段，計數尚未到達該回合的最終值；於此處比較會等同於比較不可比較的值。State 必須先到達 group end，runtime 才能決定。因此第一個屬性說「你仍在可吸收區域內」；第二個屬性說「你已到達比較點 — 現在去檢查」。

可吸收性分析

編譯的第 6 步為 §2.5 的「命運相同」規則提供了編譯期的見證。決策是分層的：

isAbsorbable(query)：
  if SKIP 模式 != SKIP PAST LAST ROW
      → return false
  if frame 結束 != UNBOUNDED FOLLOWING
      → return false
  if 任何 DEFINE 依賴 match_start
      → return false
  走訪 AST 並標示
  滿足某種結構性情況的
  元素

前三項是查詢層級的檢查：分別精確對應 §2.7（輸出面：SKIP 模式）、有界 frame（邊界破壞單調性）以及 §2.6（資料面：DEFINE 中的 FIRST 或帶 offset 的 LAST）的條件。任何一項失敗時，分析不會設定任何旗標，整個查詢的 absorption 即停用。三者皆通過時，AST 走訪會接受三種結構形狀：

情況 1 — 簡單的無上界變數

A+、A*、A{2,∞}

每次迭代恰為一列。在每個共享位置上，較早 context 的計數總是 ≥ 較晚者。

情況 2 — 固定長度的 group，外層無上界

(A B)+、(A B{2})+、((A (B C){2}){2})+

每個子節點 min == max，所以本體在語意上等同於展開的 {1,1} 形式 — (A B{2})+ 的行為如同 (A B B)+。每次迭代消耗固定數量的列；計數支配性仍成立。

情況 3 — 本體以無上界變數開頭的 group

(A+ B)+

開頭的無上界變數本身可吸收（情況 1）並屏蔽較早的 context。一旦 state 越過 A，absorption 便停止 — 本體其餘部分沒有單調性保證，所以旗標只設於 A 上。

這三種形狀未涵蓋的結構情況同樣具啟發性。A B+ 在目前規則下無法被吸收，因為開頭的 A 在無上界部分開始前消耗了一列，所以相隔一列開始的 context 處於無上界本體內的不同位置。（以陰影路徑處理固定長度前綴的後續「PREFIX absorption」延伸已有設計，預計列為獨立 patch。）像 A+? 這樣的 reluctant 量詞依設計即被排除：absorption 規則假設 greedy 語意（較長 match 涵蓋較短者），reluctant matching 則反轉此方向。

結果是逐元素而非逐 pattern 的決策。單一查詢計畫可對 (A+ B+ C) 或 (A+ B+)+ 開頭的 A+ 啟用 absorption — 後者只是情況 3 套用於其開頭元素 — 而對其後一切停用；runtime 在考慮每次 absorption pass 時，只需查閱目前 state 所在元素的 comparison-point 屬性。一旦 state 移入不可吸收區域，該 state 的 absorption 永久關閉 — 這正是 §2.5 與 §2.6 在演算法層面需要為真的情況。

3.3 導覽 — 1-slot tuple 交換

DEFINE 運算式是針對一列評估的一般 SQL 運算式，但可能包含 PREV、NEXT、FIRST 或 LAST — 指向不同列的參照。列本身已緩衝於 window 的 tuplestore；executor 仍需管理的是 SQL 運算式機制讀取所用的 tuple slot，因為運算式中的欄位參照於 plan 時即綁定到一個 slot。本實作在每次導覽呼叫中重複使用單一導覽 slot：在評估內部運算式前換入 slot，評估後還原，所以 SQL 運算式機制其餘部分完全察覺不到差異。

Executor 看到的模型很小：有一個目前列 slot，持有 DEFINE 運算式正在評估的列；還有一個導覽 slot，runtime 可暫時將其重新導向至不同的列。在任何導覽呼叫前後，runtime 設定導覽 slot、彷彿讀取目前列般評估內部運算式，再還原原始列。虛擬碼：

eval_navigation(call)：
  targetPos = compute_target_position(call)
  if targetPos 在有效範圍之外：
      return NULL

  保存 current_row_slot
  將 targetPos 的列
    取入 current_row_slot
  result = eval_inner_expression()
  還原 current_row_slot
  return result

訣竅在於只需儲存與還原一個 slot。內部運算式 — 不論是什麼，包括算術、函數呼叫或其他欄位參照 — 對換入的 slot 執行時，使用與目前列相同的評估路徑。沒有替代評估器、沒有 shadow slot、沒有 tuple 複製。

複合導覽於 parse 時被攤平，使換入仍只發生一次。PREV(FIRST(price)) 被辨識為兩步驟導覽 — 「先到第一個 match 列，再往回一列」 — 並儲存為單一具複合類型的導覽呼叫。Runtime 分兩階段計算目標位置，但只執行一次 slot 換入以取得最終列：

compute_target_position(call)：

  # 相對於目前列
  PREV(n)：
      return currentPos − n
  NEXT(n)：
      return currentPos + n

  # 相對於 match
  FIRST(n)：
      return matchStart + n
  LAST(n)：
      return lastMatchedRow − n

  # 複合：先 match-rel，再 step
  PREV(FIRST(n), m)：
      return (matchStart + n) − m
  NEXT(FIRST(n), m)：
      return (matchStart + n) + m
  PREV(LAST(n), m)：
      return (lastMatchedRow − n) − m
  NEXT(LAST(n), m)：
      return (lastMatchedRow − n) + m

  針對適當範圍進行驗證
  （FIRST/LAST 內部用 match 範圍，
   外部 step 用 partition 範圍）

當同一個 DEFINE 中有多個導覽呼叫指向同一列時，位置 cache 會將 tuplestore 的取列短路 — 在像 price > PREV(price) AND volume > PREV(volume) 這樣兩次呼叫皆解析為前一列的運算式中很常見。Cache 只儲存「最後取得的位置」，換入本身仍是單一操作。

導覽呼叫的分類是 planner 對 absorption 決策的貢獻。Planner 走訪每個 DEFINE 運算式，並依「所有 context 是否會在同一列計算相同的 Boolean，或各 context 計算各自的」將每個變數歸入兩個 bucket 之一。Bucket 在 runtime 決定兩件事：變數的評估頻率（共享一次，或每個受影響 context 一次 — §3.5 Phase 1），以及周圍 state 是否合於 context absorption（§2.5 對 §2.6）。

分類於 plan 時執行，並與每個 DEFINE 變數一同儲存，所以 runtime 不需花時間決定 — 處理一列時只需讀取每個變數的 bucket。

保留預算

導覽會碰觸 window-function 機制原本已經串流過去的列。為使這些列保持可用，executor 建構在保留近期列滑動視窗的 tuplestore 之上；問題是該視窗需要多寬。Patch 在編譯期由兩個互補的 offset 決定：

Lookback 預算

任何 DEFINE 呼叫從目前列向後可碰觸的最遠距離。

貢獻者：PREV、帶 offset 的 LAST、PREV(LAST(...))、NEXT(LAST(...))

由起點往前的 lookahead 預算

任何 DEFINE 呼叫從最舊存活 context 的 match 起點向前（負值時則向後）可碰觸的最遠距離。

貢獻者：FIRST、PREV(FIRST(...))、NEXT(FIRST(...))

執行期 tuplestore 的 trim mark 設為兩個位置中較早者 — 目前列減去 lookback 預算，以及最舊存活 context 的 match 起點加上 lookahead 預算。在該標記之前的任何東西都無法被任何存活 context 中的任何導覽呼叫碰觸，tuplestore 可自由丟棄。EXPLAIN 回報的兩個 Nav Mark 計數器（§3.7） — Lookback 與 Lookahead — 是這兩個預算的測得峰值，即 executor 在查詢過程中於任一方向所需碰觸的最深處。

3.4 Match 邊界 — SKIP、INITIAL 與有界 frame

成功的 match 以一小組值記錄：有效旗標、成功／失敗旗標、match 起始的列以及它消耗的列數。當有效旗標被設定時，後續對 executor 的查詢 — 「此列是否在 match 內？」 — 可透過檢視該 bundle 以 O(1) 回答。長度為零是真實的結果，並非錯誤：代表 pattern 匹配但未消耗任何列，executor 必須將其與「此位置尚未嘗試 match」區分。

AFTER MATCH SKIP 子句決定下次 match 嘗試從何處開始。AFTER MATCH SKIP PAST LAST ROW 移至 match 結束之後一列，產生大多數查詢想要的非重疊輸出，並啟用 absorption 最佳化。

AFTER MATCH SKIP TO NEXT ROW 僅移至 match 起始之後一列，允許重疊的 match；因此當此模式生效時，planner 會對整個查詢計畫停用 absorption。

標準另外定義的兩個 skip 目標 — AFTER MATCH SKIP TO FIRST var 與 AFTER MATCH SKIP TO LAST var — 仰賴本 patch 未保留的每 match 歷史。它們完全不在文法中，所以提供任一者時 parser 會丟出一般語法錯誤。

SEEK（規格中 INITIAL 的替代品）也是如此。在 SEEK 之下，從第 R 列開始的 match 嘗試可在 R 至 frame 結束之間任一列成功，而非僅在 R 處。Patch 僅實作 INITIAL：每個潛在 match 錨定於特定列。若請求 SEEK，parser 會丟出錯誤。有界 frame 有自己的處理 — 當使用者寫 ROWS BETWEEN CURRENT ROW AND N FOLLOWING 而非 UNBOUNDED FOLLOWING 時，executor 透過強制不匹配將任何 match 已達邊界的 context 短路，且 absorption 會被停用，因為邊界破壞了 absorption 所依賴的單調性假設。

3.5 三階段逐列引擎

Executor 的逐列驅動由外圍 window-function 機制每當需要知道某列是否屬於 match 範圍時呼叫。驅動找到或建立目前起始位置的 context，對每個 DEFINE 述詞針對目前列評估一次以產生一個逐變數的 Boolean 陣列，然後驅動 NFA 前進一列。前進步驟本身依固定順序分為三階段 — Match、Absorb、Advance — 包裹在同一外層迴圈中：

processRow(currentPos)：

  # Phase 1 — MATCH（收斂）
  for each context：
      if context 超出有界 frame：
          強制不匹配（提早定案）
          continue
      if matchStartRow 與
         共享評估位置不同：
          重新評估依賴 match-start
          的 DEFINE 變數（§3.3）
      match(context, varMatched)

  # Phase 2 — ABSORB
  if pattern 可吸收：
      重整每個 context 的旗標
      absorb_contexts()

  # Phase 3 — ADVANCE（發散）
  for each context：
      advance(context, currentPos)

順序並非風格選擇。Match 必須先執行，因為 absorption 比較match 後的計數；先 Absorb 會比較即將消亡的 state。Advance 必須最後執行，因為它是唯一會建立新 state 的階段 — 它將每個存活 state 透過 epsilon transition 展開，直到每條分支抵達等待下一列的變數。在 Advance 之後 Absorb 會比較已發散的後繼，錯過 state 最清楚可比的時點。

Phase 1 — Match

Match 是「收斂」階段：state 要麼以遞增的計數存活，要麼消亡。一個細節是：對於位於可吸收區域內的變數，Match 也會執行少量向前推進，使 Absorb 能乾淨地比較。Cover 條件僅在可吸收比較點 — 即無上界 group 的 END — 處觸發，因此剛匹配迭代中段變數（如 (A B)+ 內的 B）的 state，必須於 Match 階段就走到該比較點；否則 Absorb 找不到可比較的合格項目，最佳化便不會啟用。

match(context, varMatched)：
  for each state in context：
      elem = pattern[state.elemIdx]
      if elem 不是變數：
          continue   # advance 處理

      if not varMatched[elem.varId]：
          捨棄 state   # 死掉的分支
          continue

      state.counts[elem.depth] += 1

      # 行內向前推進，讓下一階段
      # 能在 comparison-point 元素
      # 而非迭代中段比較。
      if elem 在區域內但非
         比較點，
         且已達最大計數，
         且 elem.next 為 group end：

          走訪 END 鏈：
            遞增外層 group 計數
            將 state.elemIdx 推進至 END
            當仍在區域內、
              必須離開且 next 為 END 時繼續
          （在比較點處或仍可迴圈的
           元素處停止）

END 鏈走訪正是讓巢狀固定長度 group 可吸收的關鍵。在 ((A B){2})+ 中，當 B 達到最大值（B 為 {1,1}）時，內層 group 的計數必須遞增；若該計數也達到最大值 — 關閉內層 {2} — 外層 group 的計數也必須遞增，依此類推，直到 state 落在最外層的 absorption point — 即無上界外層 group（+）的 END。在 Match 執行此工作可讓 Absorb 對已合併迭代後計數的 context 進行比較。

Phase 2 — Absorb

Absorb pass 從最新（tail）走訪到最舊（head）的 context。對每個進行中且完全可吸收的 context，它向後掃描尋找覆蓋它的較舊進行中 context，找到則釋放較新者。由於 context 以建立順序保留，且每列最多建立一個 context，「較新」與「較舊」確實意味「較晚開始」與「較早開始」。

absorb_contexts()：
  for ctx from tail backward：
      if ctx 已完成
         或有任何不可吸收的 state：
          skip
      for older from ctx.prev backward：
          if older 已完成
             或無可吸收的 state：
              skip
          if covered(older, ctx)：
              free(ctx)
              記錄吸收長度
              break

covered(older, newer)：
  for each state in newer：
      elem = pattern[state.elemIdx]
      if elem 不是比較點：
          return false
      if older 中無 state 滿足：
            相同的 elemIdx
            且 isAbsorbable
            且 older.counts[depth]
                >= newer.counts[depth]：
          return false
  return true

由此衍生兩個微決策。第一，若較新 context 中的任一 state 處於比較點之外的任何位置，cover 檢查立即拒絕 — 在非判決點處比較不會是有意義的比較。

第二是每個 context 上的非對稱旗標對：has-absorbable-state 回答「此 context 能否吸收較新者？」是單調的（隨著 state 消亡只能由 true→false），而 all-states-absorbable 回答「此 context 能否被吸收？」是動態的（當不可吸收 state 被移除時會翻回 true）。兩個旗標都在 cover 掃描開始前以常數時間檢查，所以 absorption 只在真正有機會被吸收的 context 上付出全部成本。

Phase 3 — Advance

Advance 是「發散」階段：每個存活 state 都透過 epsilon transition 展開，直到每條分支抵達等待下一列的變數或 FIN sentinel。展開為深度優先，兄弟分支的走訪順序正是讓標準的 preferment 規則實際生效的方式 — 字面最先的分支總是先加入，state 插入時的去重步驟會默默丟棄等價的較晚加入。

advance(context, currentPos)：
  取出全部目前的 state；
  從零重建 ctx.states
  for each state 依字面順序：
      清除已造訪元素的 bitmap
      advance_state(state)   # DFS

      # Preferment：一旦某次 DFS 到達 FIN，
      # 其餘 state 較不被偏好，
      # 可被丟棄。
      if 已達 FIN 且仍有 state：
          釋放其餘
          break

advance_state(state)：
  經由 state.elemIdx 走訪，
  遞迴穿越：
    ALT 分支（依順序）、
    BEGIN（進入 group；如果 min = 0
           另加一條可選 skip 路徑）、
    END（loop back / exit / fast-forward —
         見下文）、
    FIN（記錄 matchEndRow、
         儲存 matchedState，並修剪
         位於此候選範圍內的後續
         context — 見下文），
  在每次遇到變數處停止：
      將 state 加入 ctx.states
      （以 elemIdx + counts 去重）

記錄到達 FIN 的 state 不只是為候選 match 加上書籤。在 AFTER MATCH SKIP PAST LAST ROW 之下，下一個可回報的 match 必須嚴格地從目前 match 之後開始 — 所以候選一被記錄，起始列落在該候選範圍內的後續 context 即立刻被修剪，即便擊中 FIN 的 context 可能透過 greedy fallback 繼續尋找更長的 match。

此修剪是安全的，因為無論該搜尋如何結束（較長的 match 取代候選，或候選保留），所有被修剪的 context 都在下一個可回報 match 必須跳過的範圍內開始，因此永遠無法產生自身輸出。

這是兩個 FIN 時點修剪步驟之一 — 另一個作為 Advance 一部分先前已敘述，丟棄同 context 內字面較劣的 state。

最棘手的逐元素邏輯位於 END 處理器中。當某 group 的迭代計數低於下界時，runtime 必須迴圈回去；當它等於或超過上界時，必須離開；介於兩者之間時，兩個選項皆有效，由量詞的 greediness 決定先嘗試何者：

advance_end(state, elem)：
  count = state.counts[elem.depth]

  if count < elem.min：
      迴圈回到本體
      if elem 為 empty-loopable：
          # 可空本體，見 §3.2
          另複製一個快速前進
          state，以已滿足的計數
          離開該 group
          （拯救 cycle guard 否則會
           扼殺的合法 match）

  elif count >= elem.max：
      重置此 depth 的計數
      經由 next 離開
      （END→END：遞增外層
       END 的計數）

  else：
      # min <= count < max：分叉
      建立離開 state
      （此 depth 的計數重置）
      if greedy：
          先迴圈，再離開
          # 偏好較長
      else（reluctant）：
          先離開
          if 離開到達 FIN：
              丟棄迴圈
              # 偏好較短
          else 再迴圈

每個加入 context 的 state 都經過去重檢查，比較其位置與計數對既有 state 清單。由於 Advance 以 DFS 順序處理分支，任何替代第一條分支的 state 先落地 — 任何稍後產生相同位置與計數的分支在插入時即被拒。這正是 §2.4 字面順序規則所要求的，並在 runtime 底層不需另外的 pass 即實作。

Empty-loopable group

A subtle case the runtime has to defuse is the nullable group — a group whose body can match zero rows because every child of the body is itself optional. Patterns like (A?)*, (A? B?)+, and (A | B*) all have this property: depending on the data, the body can complete an iteration without consuming any row at all. That is fine in principle, but it creates a real hazard for the NFA's epsilon expansion. If the body produces an empty match, the END element loops back to BEGIN, the body once again produces an empty match, BEGIN loops to END, and so on. Without something to stop it, Advance's DFS would never terminate.

Runtime 透過已造訪元素 bitmap 阻止它（每個 pattern 元素一位元），於每個 state 的 DFS 展開前清除：在同一展開中任何元素第二次被造訪時，該路徑即放棄。Cycle guard 是無條件且廉價的，但它有副作用 — 它也可能放棄本應透過合法空迭代達到下界的路徑。考慮 (A?){2,3} 而列流中沒有任何 A 匹配的情況：

期望行為：
  iter 1：A? 匹配零列
          → END，count = 1（未達 min）
  iter 2：A? 匹配零列
          → END，count = 2（達到 min）
  以零長度 match 退出

cycle guard 單獨會做的事：
  iter 1：A? 略過 → END，count = 1
          → 迴圈回 BEGIN
  iter 2：BEGIN 已造訪
          → DFS 中止
  count 永遠未達 min
  → match 失敗（不正確）

解法在編譯期決定，於 runtime 動作。每當 planner 看到本體可為空的 group 時，它將該 group 的 END 元素標記為 empty-loopable。在 runtime，當 END 處理器因為迭代計數仍低於下界而要迴圈回去時，empty-loop 標記告訴它在一般 loop-back 路徑外另複製一個快速前進 state：

advance_end（count 低於 min）：

  主要路徑：
    迴圈回到本體
    （為下一次迭代中真正
     非空的 match 保留可能性）

  if elem 為 empty-loopable：
    快速前進路徑：
      重置此 depth 的計數
      經由 next 離開 group，
      將剩餘必要迭代視為
      空 match

兩條路徑扮演互補角色。主要 loop-back 處理本體稍後仍有真實 match 可產生的情況 — 例如，在 (A?){2,3} 後的資料中，A 只在較晚的列匹配，loop-back 讓第二、第三次迭代得以找到非空 match。快速前進處理本體永遠不產生任何東西的情況：它透過完全離開該 group 繞過 cycle guard，宣告「其餘必要迭代為空」，讓 match 以零長度本體成功。兩個 state 都會加入 context；最終哪一個延伸成功者勝出，插入時的去重檢查也防止任一路徑生出超過其份額的 state。

除 cycle guard 外，另有一個啟動技巧消除 context 開頭零列結果的歧義。每個潛在起始列的 context 建立步驟會在消耗任何列之前，使用實際起點前一列的位置，透過 epsilon transition 執行初始 advance。任何僅靠 epsilon transition 即抵達 FIN sentinel — 未消耗任何列 — 的路徑因此產生一個小於起始位置的結束位置；該負跨度座標結合是否真的到達 FIN，可在不需另外旗標的情況下編碼空 match（接受長度為 0 的 match）與未匹配起點之間的差異。

3.6 狀態空間如何維持有界

Runtime 的線性並非單一最佳化的結果。它是一組分層修剪規則的累積效果，每條在每列循環的不同點抓住狀態空間增長的不同原因。有些於編譯期決定，runtime 僅查閱；有些則動態觸發。有些殺掉個別 state；有些則殺掉整個 context。上面各節皆於各自脈絡介紹過；下表將它們彙整於一頁。

失敗述詞 Match

DEFINE 在目前列上評估為 false 的變數 state — 死掉的分支。

行內 end-chain advance Match

已達最大計數、否則會將 state 留在迭代中段的變數；穿越固定長度 group 的 end 推進，使 absorption 可在正確點比較。

Context absorption Absorb

每個 state 都被某較舊 context 中具更高計數的 state 覆蓋的較新 context — 概念規則見 §2.5、編譯期合格性見 §3.2、逐對檢查見 §3.5。

State 去重 Advance

經不同 DFS 分支抵達相同位置且計數相同的 state — 只有第一個（字面最早者）存活；後來的等價者被默默丟棄，這也是 preferment 的執行方式（§2.4）。

FIN 提早終止（context 內） Advance

當某分支到達 FIN 時，仍待於 DFS 佇列中的 state — 依字面順序，其餘 state 較不被偏好，可立即丟棄。

候選 match 修剪（跨 context） On FIN

起始列落於候選 match 範圍內的其他 context — 擊中 FIN 的 context 可能仍持續尋找更長的 match（greedy fallback），但在 AFTER MATCH SKIP PAST LAST ROW 之下，任何在候選範圍內的 context 都無法再產生可回報輸出（無論搜尋如何結束），故立即修剪。

Cycle guard Advance

在同一 DFS 內重複造訪同一 pattern 元素的 epsilon 展開 — 否則會在可空 group 中無限迴圈。

Empty-loop 快速前進 Advance

cycle guard 在可空 group 中會殺掉的合法空迭代 match — 透過離開 group 並宣告其餘必要迭代為空來繞過 cycle。

有界 frame 截止 Match

match 已達使用者指定 frame 上界的 context — 強制不匹配以避免越界（§3.4）。

依 phase badge 閱讀條目可追蹤 context 的生命週期：修剪在每列穿越三個主要階段時觸發（Match、Absorb、Advance），並在 match 完成時再次觸發（On FIN）。改依描述閱讀則依目標分組規則：死掉的分支、冗餘 context、等價 state、無限迴圈，以及超出使用者邊界的越界延伸。

任一單一規則皆不足。Cycle guard 單獨會殺掉可空 group 中的合法 match；empty-loop 快速前進單獨無法阻止無限 epsilon 迴圈；absorption 單獨在 DEFINE 參照 match-start 時會過度合併；去重單獨只移除冗餘的 state，無法移除冗餘的 context。Runtime 在重要情境中保持線性 — PATTERN (A+ B+ C+ D) 在 100,000 列上、海報面板 ③ 的 benchmark — 只因為每一層都抓住其上層所遺漏的。

3.7 EXPLAIN 輸出

對使用 RPR 的查詢執行 EXPLAIN ANALYZE 會呈現一般 window function 沒有的 NFA 層級統計。三組計數器與 window 運算子一起發出：

NFA States：    peak, total, merged
NFA Contexts：  peak, total, pruned
NFA: matched     (len min/max/avg)
NFA: mismatched  (len min/max/avg)
NFA: absorbed    (len min/max/avg)
NFA: skipped     (len min/max/avg)
Nav Mark Lookback：   | runtime | retain all
Nav Mark Lookahead：  | runtime | retain all
  （僅當查詢使用 FIRST、
   PREV(FIRST(...)) 或 NEXT(FIRST(...)) 時）

Peak 與 total 是 runtime 的直接量測：曾同時存活的 state 數、查詢生命週期內建立的 state 數，以及被去重合併掉的 state 數。Match 長度的直方圖分為四種結果 — 成功 match、失敗的 match 嘗試、被吸收的 context，以及被修剪（skipped）而未評估的 context — 並以 min/max/avg 回報，能一眼揭示效能病灶：健康的執行會顯示大多數 context 為 matched 或 absorbed，且 mismatched 長度較小。

兩個 Nav Mark 計數器回報 §3.3 在編譯期推導的 tuplestore 保留預算。Lookback 是 PREV、帶 offset 的 LAST，以及內含 LAST 的複合形式中最深的向後距離；Lookahead 是從最舊存活 context 的 match 起點測量，由 FIRST 與內含 FIRST 的複合形式所貢獻的最深向前（或負值時為向後）距離。

當 offset 為常數時，每個計數器列為固定整數；當 offset 為每次呼叫都需評估的非常數運算式時列為「runtime」；當 runtime 需要無上界預算時列為「retain all」。Lookahead 僅在查詢實際使用 match-start 相對導覽時發出。

這些計數器加總，使得無需將 gdb 附加到 backend 也能除錯 RPR 效能。

除計數器外，EXPLAIN 亦忠實重現原始 PATTERN 與 DEFINE 子句，包括 reluctant 量詞、group 重複以及 AFTER MATCH SKIP 選項。實作為使此 round-trip 穩定下了相當功夫，讓 pg_dump 與 pg_upgrade 能在不發生語意漂移下保留 RPR 物件 — rpr_explain 之下的 regression suite 逐案驗證之（見 §4）。

§4. 測試 — 覆蓋率地圖

Patch 隨附五個 regression suite，合計覆蓋 §3 中描述的每一層 — 約 13,000 行 SQL，每個 suite 聚焦於不同關注點。此拆分為刻意之舉：將 parser 議題、runtime 正確性、planner 互動與輸出格式分置不同檔案，能讓失敗更易於定位，並避免某層的無關變更意外使另一層的測試失效。五個 suite 為：

rpr

端到端查詢語意 — 在合成的股票資料上執行真實 window 情境（V 形、W 形、連續上漲、反轉）。

rpr_base

Parser 層 — 關鍵字接受、語法形狀、量詞、導覽解析、錯誤訊息，以及 pg_dump/pg_upgrade round-trip 穩定性。

rpr_nfa

NFA runtime — 三階段迴圈、各種可吸收形狀的 absorption，以及 context 生命週期邊界情況。

rpr_explain

輸出格式 — NFA 統計、pattern 反解析、識別字引號、跨重新載入的格式穩定性。

rpr_integration

Planner 互動 — 防止無關 window 最佳化破壞 RPR 語意的防護。

4.1 rpr — 端到端情境

情境 suite 是測試集合的公共面貌：使用約 1,600 列的合成股價資料集，並對其執行真實查詢 — V 形回升、W 形（雙底）、連續漲跌、反轉 pattern、多 symbol 的 partition。它是唯一輸入與輸出讀起來像使用者實際撰寫之查詢的 suite；其他則刻意簡化，每次聚焦單一層。

因為這些查詢結合每一層（parser、planner、executor、EXPLAIN），rpr 單一失敗很少能直接告訴你 bug 在哪裡。接下來四個 suite 即為分割定位的方法：rpr 失敗加上 rpr_base 通過排除 parser；再加上 rpr_nfa 通過將範圍縮至情境特有的資料形狀；再加上 rpr_integration 通過排除 planner 干擾；任何反解析漂移會顯現於 rpr_explain。

4.2 rpr_base — parser 介面

Base suite 規模最大，這有原因：它負責證明 §1.2 中每一項合法語法確實能解析、§1.3 中每一項非法語法會以有用的錯誤拒絕，且每個被接受的形式都能熬過序列化 round trip。其大宗為小而專注的片段 — 每個語法 feature 一個 — 而非長的真實查詢，因為目標是覆蓋率而非情境真實性。

序列化測試值得特別注意。RPR 物件（view、materialized view、pg_dump 輸出）必須在通過 catalog 表示時 round-trip 而不發生語意漂移，包括量詞上的 reluctant 旗標或複合導覽運算式的精確形式等細節。一小組序列化專屬物件（rpr_serial_v* view 與其支撐表）在執行結尾刻意保留，使周圍的 regression 基礎設施能接手並對之執行 pg_dump 與 pg_upgrade。其餘測試框架照常 drop。透過此方式發現的 bug（如反解析與重新解析間遺失 reluctant 旗標）只在端到端 round-trip 時才會浮現。

4.3 rpr_nfa — runtime 引擎

這是執行 §3.5 與 §3.6 中所有機制的 suite。其測試遵循一致的 pattern：輸入表的每列為明確 Boolean 陣列，宣告哪些 DEFINE 變數在該列匹配，並配上一個探測特定 runtime 行為的 pattern。Boolean 陣列的慣用法將 runtime 測試與 DEFINE 評估機制解耦 — 所測試的是「給定這些變數在此匹配，NFA 迴圈是否產生預期的 match span？」而非「DEFINE 運算式評估器是否正確計算這些 Boolean？」DEFINE 評估器於他處測試（rpr_base 測解析，rpr 測端到端行為）。

典型測試 fixture 如下 — 一個變數名稱陣列的欄位，每個項目宣告哪些 DEFINE 變數在該列觸發，並有一個 DEFINE 子句直接測試這些名稱的 pattern：

SELECT id, flags,
  first_value(id) OVER w AS ms,
  last_value(id)  OVER w AS me
FROM (VALUES
  (1, ARRAY['A']),
  (2, ARRAY['A','B']),
  (3, ARRAY['A','B']),
  (4, ARRAY['B']),
  (5, ARRAY['_']),
  (6, ARRAY['A'])) AS t(id, flags)
WINDOW w AS (ORDER BY id
  ROWS BETWEEN CURRENT ROW
       AND UNBOUNDED FOLLOWING
  INITIAL PATTERN (A+ B+)
  DEFINE
    A AS 'A' = ANY(flags),
    B AS 'B' = ANY(flags));

沿陣列欄位往下讀就是直接閱讀測試情境。第 2 與第 3 列同時帶有兩個名稱 — A 與 B 都在那裡觸發，所以 NFA 對於從 A 段切換至 B 段確有真實選擇。預期 match（在標準的 greedy preferment 之下，第 1–3 列為 A，接著第 4 列為 B）僅由那些旗標固定，此處沒有任何後果性的運算式評估 — = ANY 只是將陣列欄位暴露給 DEFINE 的瑣細層，並非測試所執行的內容。以數值述詞（price > PREV(price) 等）撰寫相同情境會讓 NFA 測試與述詞評估器行為糾纏；陣列慣用法將兩者乾淨地分離，這裡的失敗便直接指向 NFA 迴圈。

Absorption 的覆蓋特別徹底，因為 absorption 是不該啟用卻啟用時最容易默默產生錯誤答案的最佳化。測試涵蓋 §3.2 案例分析中的每種形狀：

• 簡單無上界變數（A+） — 典型的 N 對 1 收斂；
• 固定長度 group（(A B)+、(A B{2})+、三層巢狀 ((A (B C){2}){2})+）；
• 開頭無上界變數加上固定後綴（A+ B） — 只有開頭的 A+ 帶有 absorption 旗標，後綴沒有；
• 替代內部的逐分支 absorption（B+ C | B+ D）；
• 多個無上界變數（A+ B+） — 僅開頭者可吸收；
• Reluctant 量詞（A+?） — 已驗證被排除於 absorption 之外；
• 非開頭的無上界（A B+） — 已驗證被排除。

除 absorption 外，此 suite 涵蓋 context 生命週期：AFTER MATCH SKIP TO NEXT ROW 下的重疊 context、串流中段失敗 context 的清理、partition 結尾對未完成 context 的定案，以及在 head context 中已記錄候選 match 後遭遇的 context。這些每一項都對應 §3.6 中的特定修剪規則，測試撰寫成在規則誤觸發時（無論是讓冗餘 context 存活，或殺掉應產生輸出的 context）會大聲失敗。

4.4 rpr_explain — 輸出穩定性

EXPLAIN 輸出是面向使用者契約的一部分 — 第三方工具（psql 自動完成、監控儀表板、log scraper）會解析它，看似化妝性的變更可能將之打破。rpr_explain suite 驗證三件事：

• NFA 計數器出現於正確位置 — 每個 WindowAgg 的統計（peak/total/merged states、peak/total/pruned contexts、matched/mismatched/absorbed/skipped 的長度直方圖、Nav Mark Lookback，以及 — 當使用 match-start 相對導覽時 — Nav Mark Lookahead）都在 EXPLAIN ANALYZE 下以文件標籤顯示。
• Pattern 反解析正確 — 每種量詞形狀（包括 reluctant 變體與有界形式）、每個替代、每個 group、每種 AFTER MATCH SKIP 形式、INITIAL、帶 offset 的導覽呼叫、複合導覽。反解析的文字必須能不變地通過 parser round-trip。
• 識別字引號正確 — pattern 變數與 DEFINE 運算式以與一般 SQL 識別字相同的引號規則發出，使得不尋常的變數名稱不會破壞 pg_dump 輸出。

與 rpr_base 一樣，此 suite 在執行結尾刻意保留物件，使 pg_dump 與 pg_upgrade 的覆蓋亦延伸至 explain 端的產物。

4.5 rpr_integration — planner 互動

PostgreSQL 的 planner 對 window 查詢有許多最佳化 — frame 規範化、run-condition 下推、相同 window 的去重、未使用輸出投影、moving-aggregate inverse transition — 而每一項在設計時皆未考慮 RPR。當 window 有 PATTERN 子句時，大多數套用是不安全的：frame 是 match 契約的一部分、match 輸出已不再以任何明顯方式呈單調、相同規格但不同 DEFINE 的兩個 window 真的會產生不同結果。Integration suite 驗證以下每項最佳化在 RPR window 上皆被正確停用或繞過：

Frame 規範化

Planner 通常會將 ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING 為單調彙總改寫為 ROWS UNBOUNDED PRECEDING。RPR 的 frame 是 match span，不是彙總視窗，必須維持原樣。

Run-condition 下推

對 window function 輸出的單調 WHERE 過濾通常可下推為 window 運算子的停止條件。對 RPR 而言這會提前終止 pattern matching，可能在延伸途中切斷 match。

Window 去重（RPR 對非 RPR）

具相同 ORDER BY 與 frame 的兩個 window 通常會被合併為一個。RPR window 與非 RPR window 永遠不能共享狀態，因為 RPR 端攜帶 match 結果。

Window 去重（不同 DEFINE）

具相同 PATTERN 但不同 DEFINE 子句的兩個 RPR window 會產生不同 match，必須維持區別，即便結構形狀相同。

未使用輸出投影

即使外圍查詢從不讀取 window 的逐列輸出，RPR window 也無法移除：pattern matcher 的副作用（哪些列在哪個 match 內）會餵入計畫他處的 reduced-frame 計算。

Moving-aggregate inverse transition

具反向 transition function 的 window 彙總通常可隨 frame 移動而增量評估。RPR 的 reduced frame 並非滑動視窗；inverse transition 路徑會產生錯誤結果。

這些測試的 pattern 都相同：各自提供觸發該最佳化的非 RPR 基準（並驗證 EXPLAIN 顯示其被套用），接著執行結構相似的 RPR 查詢並驗證該最佳化未套用。兩半合在一起證明 planner 中的防護真的在做事，而非未經實際驗證即放行所有查詢。

這也是為何 §3.4 篇幅短的原因。「Match 邊界」機制 — reduced frame、SKIP、INITIAL、有界 frame 截止 — 於他處有操作性測試；rpr_integration 所驗證的是沒有其他 optimizer 階段在過程中干涉它們。rpr_integration 通過正是讓其餘 suite 能信任其輸入未被竄改地送達 executor 的關鍵。