Row Pattern Recognition 深入探討
PostgreSQL 中 ISO/IEC 19075-5 · SQL R020 的導覽 — 我們建構了什麼、還有哪些未完成,以及它實際如何運作。
瀏覽標準、跟著實作範例操作、檢視設計,然後以你自己的 pattern 操作即時的 NFA 模擬器。
相關討論:pgsql-hackers 討論串 · 最新 patch (v55) · commitfest #4460。
AI 預譯 — 可能有誤。
§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 的輸出。兩種介面在語法與語意上有相當多的共同之處(19075-5 於 §6.3.3 中列出若干 R020 特有的差異),但它們是功能上不同的進入點 — 資料庫可實作其一或兩者皆實作。
此處討論的 patch 系列僅實作 R020 的子集;資料表子句形式刻意不在範圍內。
R020 介面雖小但具表達力。查詢透過在 frame 為 ROWS BETWEEN CURRENT ROW AND … 的 window 規格中加入子句以將 pattern 附加到 window:PATTERN 以具名 pattern 變數描述一個 regular expression,DEFINE 提供識別每個變數的 Boolean 述詞,可選的 AFTER MATCH SKIP(預設為 PAST LAST ROW)則控制連續的 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;最多 240 個不同的 pattern 變數。
- Window frame
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING或ROWS BETWEEN CURRENT ROW ANDnFOLLOWING,其中 n ≥ 1(19075-5 §6.10.2);其他任何 frame 都會被拒絕,且EXCLUDE NO OTHERS是唯一被接受的排除選項。- 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。 - 導覽名稱
- 在
DEFINE中以未限定呼叫形式撰寫的PREV、NEXT、FIRST與LAST一律表示導覽;同名的使用者函數在該處必須以 schema 限定。 - 導覽引數
- 對於
PREV、NEXT、FIRST與LAST,內部引數必須包含至少一個欄位參照,且 offset 必須是 run-time 常數。 - 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 FIRST var 與 AFTER MATCH SKIP TO [LAST] var(裸的 SKIP TO var 表示 SKIP TO LAST var)。這些同樣仰賴 match 歷史,因為 executor 必須能夠指向最近一次 match 中被對應到某個變數的列。
其餘項目是混雜的尾巴:SEEK 關鍵字(INITIAL 的替代品)、空 pattern ()、排除形式 {- … -}、不在意順序的 PERMUTE 運算子,以及 DEFINE 中的彙總函數與子查詢,兩者目前皆會被拒絕(以變數限定的彙總同樣需要 match 歷史)。
- 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 frame 結尾之間的任何一列開始(相對於 INITIAL)。
- AFTER MATCH SKIP TO FIRST var
- 跳到被 match 為具名變數的第一列。
- AFTER MATCH SKIP TO [LAST] var
- 跳到被 match 為具名變數的最後一列。
- Regex:{- -}
- 排除 — 將 match 到的列從
ALL ROWS PER MATCH的輸出中移除。該選項不適用於 window(19075-5 §6.3.3 (4)),因此在 window 中此語法雖被允許(§6.13),卻沒有可作用的輸出。 - Regex:()
- 空 pattern — 匹配空序列。
- PERMUTE(...)
- 對所列變數進行不在意順序的匹配。此關鍵字會被辨識並拒絕("PERMUTE is not supported");
permute仍可作為 pattern 變數名稱使用。 - DEFINE 中的彙總函數
- 於
DEFINE述詞中不允許SUM、AVG、COUNT等彙總。標準允許它們作為對部分 match 的 running aggregate;像AVG(B.Price)這樣以變數限定的彙總仰賴MEASURES/CLASSIFIER()所需的同一份每 match 歷史,而未限定的彙總則涵蓋 match 至今的所有列。 - DEFINE 中的子查詢
DEFINE中的所有子查詢都會被拒絕。標準允許不進行 row pattern recognition 且不參照任何 row pattern 變數的子查詢;目前 patch 拒絕得比標準更多。
此處還有四點值得注意,因為它們容易被誤認為遺漏。
第一點是:標準本身不允許在 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 變數(patch 更進一步,如上所列拒絕 DEFINE 中的所有子查詢);RPR 也不得在遞迴查詢中使用。Patch 強制執行外部參照規則("cannot use outer query column in DEFINE clause")與遞迴規則,後者適用於 WITH RECURSIVE 子句的每個元素。它亦拒絕 DEFINE 中的 volatile 函數與整列參照。
第四點是: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 列的列(預設 n = 1)。向前 look-ahead;在 window 形式下不常見,因為 window 是單調的。
- FIRST(expr [, n])
- 目前 match 第一列之後 n 列的列(預設 n = 0,即第一列本身)。「與開始此 match 的列比較。」
- LAST(expr [, n])
- 最後一個 match 到的列之前 n 列的列(預設 n = 0)。在
DEFINE中,最後一個 match 到的列就是目前列,因此LAST(price)讀取的是目前列。
這四個 primitive 可以組合:PREV 與 NEXT 可包覆 FIRST 或 LAST 呼叫,形成四種複合形式,語意為「先到相對於 match 的某列,再從該列固定距離地移動」。這正是讓 DEFINE 運算式可以讀取例如 match 開始前一列的方式。
- PREV(FIRST(expr [, n]) [, m])
- 從
FIRST(expr, n)所讀取的列往回 m 列(預設 n = 0、m = 1)。「此 match 開始前的值是什麼?」 - NEXT(FIRST(expr [, n]) [, m])
- 從
FIRST(expr, n)所讀取的列向前 m 列。可在不依賴目前列的情況下深入 match。 - PREV(LAST(expr [, n]) [, m])
- 從
LAST(expr, n)所讀取的列往回 m 列。「與最近 match 到的列之前不久的列比較。」 - NEXT(LAST(expr [, n]) [, m])
- 從
LAST(expr, n)所讀取的列向前 m 列。
這裡有兩個實務要點值得指出。其一,導覽可以複合:PREV(FIRST(price)) 讀取 match 開始前一列,patch 支援此寫法。其二,導覽會影響 executor 的最佳化。單純的 PREV 與 NEXT 相對於目前列,永遠是安全的;FIRST 與帶 offset 的 LAST 變體,無論單獨使用或位於複合 PREV/NEXT 之內,皆相對於 match 邊界,會與 context absorption 互動:此時 planner 會對整個 pattern 停用 absorption。此互動背後的機制將在 §2.6 說明。
2.3 實作範例 1 — NFA 移動
SKIP PAST LAST ROW 丟棄。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:
| 列 | 價格 | 為真的變數 | 動作 |
|---|---|---|---|
| 0 | 100 | START | 新 context。START 匹配並立即離開(max=1);state 推進至 UP+。 |
| 1 | 110 | START, UP | UP 匹配。推進產生分叉:一個 state 在 UP 處迴圈,另一個離開至 DOWN+。 |
| 2 | 120 | START, UP | UP 在迴圈 state 中匹配並再次分叉。第 1 列的 DOWN state 消亡(120 ≮ 110)。 |
| 3 | 115 | START, DOWN | UP 在迴圈 state 上失敗並消亡。第 2 列的 DOWN state 匹配。推進產生分叉:在 DOWN 迴圈,並離開至 #FIN — 記錄一個涵蓋第 0–3 列的候選 match。 |
| 4 | 108 | START, DOWN | DOWN 在迴圈 state 上匹配並再次分叉;涵蓋第 0–4 列的新 FIN 候選取代較短的那個。 |
| 5 | 130 | START, UP | 迴圈中的 DOWN state 失敗(130 ≮ 108)。此 context 中已無存活 state,已記錄的候選(第 0–4 列)被定案為 match。下一次嘗試從第 5 列開始;START 匹配,但 partition 在任何 UP 之前即結束。 |
重點:在第 3 列,該列同時滿足 START(恆為真)與 DOWN,但 START 只對從第 3 列開始的 context 有意義;在此 context 中,迴圈中的 UP state 消亡,只有等待於 DOWN+ 的 state 推進。§2.1 的多狀態本質在每次 UP 匹配時以 fan-out 形式可見(state 可留在 UP+ 或推進至 DOWN+)。Greedy 偏好是「先迴圈再離開」,因此在資料足夠時迴圈分支會延伸 match 更遠;這裡迴圈中的 DOWN 在第 5 列消亡(130 ≮ 108),最後的 FIN 候選(第 0–4 列) — 由 DOWN 在第 4 列離開時產生,取代了第 3 列的候選 — 被定案為 match。
此查詢的結果直接源自此追蹤。在 RPR 語意下,window function first_value(price) 與 last_value(price) 僅在啟動 match 的列上評估 — match 中的其他每一列對這些 window function 皆產生 NULL,因為其 reduced frame 為空。因此我們資料的輸出長得像海報右上面板所展示的表格:
| 列 | 價格 | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
第 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 順序(較早的分支優先)探索的平行分支。
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,並在該處會合。
| 列 | 為真的變數 | 存活的 state |
|---|---|---|
| R | UP, HIGH | State A(UP 分支)與 State B(HIGH 分支)皆以相同計數推進至 DONE;B 是 A 的重複,因此被丟棄 |
| R+1 | DONE | State A 匹配 DONE 並到達 #FIN |
以標準的用語來說,兩個分支對相同列產生相同長度的 match,得出兩條候選路徑 — 一條標示為 UP, DONE,另一條標示為 HIGH, DONE。標準以字面順序解決此情況:在 (UP | HIGH) 中所寫的替代中,先寫者勝出,與 match 長度無關。因為 UP 出現在 HIGH 之前,存活的路徑是 UP, DONE。Executor 在第 R 列而非 FIN 時強制執行此規則:它先加入 UP 分支的 state,因此 nfa_append_state_unique() 保留該 state 並丟棄相同的 HIGH 分支 state。
字面順序使得 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(任何資料皆可 — 述詞恆為真):
| 列 | 素樸 context | 套用 absorption |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 被吸收 |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | 五個 context | C1[A:5] |
存活 context 從 O(n) 縮減為 O(1),因此整個 partition 的總量從 O(n²) 降為 O(n)。在量詞無上界時,使丟棄合理化的 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:
| 日 | 價格 | C1 — 週二起 price > PREV(price) | C2 — 週三起 price > PREV(price) |
|---|---|---|---|
| 週一 | $100 | — | — |
| 週二 | $108 | $108 > $100 ✓(剛開始) | — |
| 週三 | $112 | $112 > $108 ✓ | $112 > $108 ✓(剛開始) |
| 週四 | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| 週五 | $110 | $110 > $116 ✗ — 定案 | $110 > $116 ✗ — 定案 |
當述詞開始依賴每個 context 自身的邊界時,故事就破滅了 — 這正是 §2.6 要談的。
2.6 實作範例 4 — Absorption 何時變得不安全
DEFINE 參照 FIRST 時會發生什麼變化 — absorption 規則不再成立,planner 對該 pattern 停用 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 起點)。
| 日 | 價格 | C1 — 週一起 FIRST = $100 price < $100 + 10 | C2 — 週二起 FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| 週一 | $100 | $100 < $110 ✓ | — |
| 週二 | $108 | $108 < $110 ✓ | $108 < $118 ✓(剛開始) |
| 週三 | $112 | $112 < $110 ✗ — 定案週一–週二 | $112 < $118 ✓ |
| 週四 | $116 | — | $116 < $118 ✓ |
| 週五 | $110 | — | $110 < $118 ✓(仍在進行) |
在 absorption 之下,C2 會於週二被併入 C1 — 合併後的 context 只保留 C1 的上限($110),因此 C2 獨特的視角(上限 $118、一路到週五的四日 run)並不被 C1 的未來所涵蓋。在這一週,輸出恰好不會改變:C1 記錄週一–週二,C2 在該 match 內開始,因此被 SKIP PAST LAST ROW 丟棄,下一次嘗試從週三以其自身的上限($122)開始,並匹配週三–週五。但一般而言,較早 context 的 DEFINE 結果不再涵蓋較晚 context 的結果,因此 absorption 所依賴的計數比較不再有效。因此每當 DEFINE 述詞帶有 match-start 依賴時,planner 就會預先停用 absorption。
(當領先 context 的 match 確實成功時,於其接受範圍內開始的 context — 在預設 AFTER MATCH SKIP PAST LAST ROW 之下 — 會直接被丟棄;它們保留存活只是為了在領先 match 失敗時 runtime 有後備可用。)
下表以複合形式擴充海報右下面板(「② Navigation」),並彙整哪些導覽形式會產生 match-start 依賴:
| 導覽 | Match-start 依賴 | 可吸收? |
|---|---|---|
| PREV, NEXT | 無 | 是 |
| LAST(無 offset) | 無 | 是 |
| LAST 含 offset | 邊界檢查 | 否 |
| FIRST(任何) | 直接 | 否 |
| 複合(內部 FIRST) | 直接 | 否 |
| 複合(內部 LAST,無 offset) | 無 | 是 |
| 複合(內部 LAST 含 offset) | 邊界檢查 | 否 |
§2.5 與 §2.6 的兩個範例可歸納為單一規則。命運相同使得 absorption 安全:若同一 pattern 元素上的每個 context 對於每個未來述詞都會算出相同答案,那麼只需保留最舊的即可。命運不同使 absorption 不安全:一旦述詞依 context 私有狀態而分歧 — 這正是 FIRST 與帶 offset 的 LAST 所做的 — 每個存活 context 都代表一個其他 context 無法保證涵蓋的未來,因此丟棄其中任一個已無法證明是安全的。
Planner 在編譯期偵測此區別,並對整個 pattern 開啟或關閉 absorption;關閉時,runtime 承擔多 context 成本。海報面板 ③ 的 benchmark 未使用 FIRST,因此 absorption 維持開啟,這正是 PostgreSQL 在成功與失敗情況下皆維持線性的原因。
海報上的 benchmark 數字就是相同演算法在大規模下的表現。在成功 pattern (A+ B+ C+ D) 上,PostgreSQL 與 Trino 在 match 確認後皆大致呈 O(n),而 PostgreSQL 領先約 16× 至 33×(Trino 的數字已排除 JVM 啟動時間)。
在失敗 pattern (A+ B+ C+ E) 上,Trino 似乎沒有 absorption,會追蹤每個潛在 match 起點,且退化得比 O(n²) 更快(列數 5× 時耗時約 56×);在 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 列。這些都不能被「從更早開始的較長者」取代,因為標準規定使用者想要全部。
| 列 | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | match 開始;第 0–4 列將是唯一 match | match 從第 0 列開始 |
| 1 | (在 match 0 內) | match 從第 1 列開始 — 必須保留存活 |
| 2 | (在 match 0 內) | match 從第 2 列開始 — 必須保留存活 |
| 3 | (在 match 0 內) | match 從第 3 列開始 — 必須保留存活 |
| 4 | match 0 定案(第 0–4 列) | 五個 match 定案:0–4、1–4、2–4、3–4、4–4 |
AFTER MATCH SKIP TO NEXT ROW 之下,每個較晚開始的 context 都是自己的輸出列。同一 pattern 元素上的兩個 context 不再冗餘 — 它們都是必要的輸出,丟棄其中之一會悄悄丟失使用者要求的 match。
注意述詞並未改變。A AS TRUE 在每列都以相同方式評估,無論哪個 context 在問,所以 §2.5 的命運相同條件仍然成立。改變的是輸出需求:即使擁有相同未來的 context 也必須共存,因為它們對應結果中不同的列。因此只要 AFTER MATCH SKIP TO NEXT ROW 生效,無論 DEFINE 子句為何,planner 都會停用 context absorption。
將 §2.6 與 §2.7 並列,便可看見查詢語意排除 absorption 的兩種方式:
DEFINE 中的 FIRST 或帶 offset 的 LAST 觸發。AFTER MATCH SKIP TO NEXT ROW 觸發。
任一條件都足以對整個 pattern 停用 absorption,不以 UNBOUNDED FOLLOWING 結尾的 frame 亦然。當這些皆未生效時 — 預設 AFTER MATCH SKIP PAST LAST ROW、無上界的 frame 結尾,以及僅使用 PREV、NEXT 或裸 LAST 的 DEFINE 條件 — absorption 會被啟用,但僅限於 pattern 可吸收區域中的 state:開頭的 greedy 無上界變數,例如 A+ 或 A*;帶 greedy 無上界量詞的固定長度 group,例如 (A B)+;本體以上述之一開頭的 greedy group,例如 (A+ B)+ 或 (A+ B){2};或由這些構成的替代分支;reluctant group 會使其整個子樹失去資格。在此條件成立時,如 §2.5 的 A+,runtime 收斂為單一 context 並維持線性;§2.3 的 START UP+ DOWN+ 則完全沒有可吸收區域。
§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,結束邊界必須為 UNBOUNDED FOLLOWING 或正值 offset FOLLOWING(因此預設的 frame 也會被拒絕),且禁止 EXCLUDE NO OTHERS 以外的 EXCLUDE 選項。這些是符合規範的檢查,而非最佳化 — RPR 對 frame 的概念是match span,標準並未設想以匹配列以外的東西去填它。
一旦 frame 通過驗證,parser 便將 PATTERN 子句轉為由四種節點組成的 tree — 變數參照、sequence(串接)、alternation,以及 group(以括號包圍的子 pattern)。每個節點以三個數字攜帶量詞 — 下界、上界(可能為無限),以及 reluctant matching 旗標:
| 來源 | Tree 編碼 |
|---|---|
| A | VAR(A, min=1, max=1) |
| A+ | VAR(A, min=1, max=∞) |
| A* | VAR(A, min=0, max=∞) |
| A{3,5} | VAR(A, min=3, max=5) |
| A+? | VAR(A, min=1, max=∞, reluctant=true) |
每個 DEFINE 述詞接著針對 partition 欄位進行型別檢查,並強制轉型為 Boolean 運算式。隨之而來的有兩件實際的事。第一,parse analysis 不會為 DEFINE 在查詢的 target list 中加入任何東西;而是由 planner 將 DEFINE 述詞所參照的每個欄位標示為需要,如同對 HAVING 所做的那樣,並且即使外層查詢未選擇這些欄位,也會把它們傳遞至 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 必須列舉的狀態空間。最佳化器以單一次由下而上的 pass 套用九個重寫規則(在一個 sequence 內,group 合併會再執行一次,因為較早的合併可能使兩個相同的 group 相鄰):
- 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 - Reluctance 正規化
A{2}?→A{2}(凡 min = max 之處皆清除 reluctance)
量詞相乘只在可達成的計數構成一個連續區間、且偏好的 match 不會移動時才收斂:外部為精確值((A{2,3}){5} → A{10,15})、子節點的 min 為 0,或子區間彼此相接且子節點 min 至多為 1 或子節點 max 無上界((A+)+ → A+、(A{1,3}){2,4} → A{2,12}),其中 min 為 0 的外部還需要子節點 min 至多為 1((A{2,})* 保持原樣,因為 A* 會接受一列)。量詞本身非精確值的 group 子節點必須先具有固定長度的本體,因此 ((A | B B){1,2}){2} 即使在精確的外部之下仍保持原樣。其他組合可能引入扁平形式會遺漏的缺口 — 例如 (A{2}){2,3} 只接受 {4, 6},但素樸的 A{4,6} 也會接受 5 — 或移動偏好的 match((A{2,3}){1,2} 偏好三列,而 A{2,6} 會取四列),因此最佳化器將它們保持原樣。它並非唯一受限的重寫:group 合併與後綴合併要求本體消耗固定數量的列,前綴合併會拒絕 min 為 0、max 有限且內容可為空的 group,reluctant 節點既不合併也不相乘((A+?)+ 保持原樣),新邊界會溢位的重寫也會被拒絕。
元素形狀
扁平陣列的每個元素代表 pattern 中的單一位置。共有六種邏輯類型:變數參照(唯一會消耗一列的類型);group 起始與group 結束標記,用來開啟與關閉以括號包圍的子 pattern;alternation 標記,作為一系列分支的開頭;結束每個分支的分支分隔符;以及位於 pattern 末端的結束標記。
每個元素也攜帶深度(其 group 巢狀層級)、量詞(最小與最大重複次數,可能為無限)以及兩個轉移指標 — next,「消耗此元素後要去哪裡」,以及 jump,「要跳到何處」(alternation 標記與分支分隔符用以串連分支;group 起始用以指名其自身的 group 結束 — 量詞允許 0 的 group 會經由該結束的 next 被略過;group 結束用以迴圈回到本體)。
對於 PATTERN ((A B)+),編譯後的陣列如下:
PATTERN ((A B)+) 編譯為:
[0] BEGIN depth 0 quant 1..∞
next → 1 jump → 3
(開啟 group;jump 指名
其自身的 END)
[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,BEGIN 的 jump 指名其位於 idx 3 的 END,若 group 為選擇性(optional),略過會經由該 END 的 next 離開至 idx 4,而不會抵達 END。Runtime 永不必在執行期建構圖 — 它只在走訪陣列時跟隨這兩個指標。
每元素屬性
除形狀外,每個元素攜帶五個邏輯屬性,引導 runtime 在該位置的行為:
- Reluctant
- 反轉量詞展開的順序。Greedy 量詞會先嘗試「再次迴圈」再「離開」;reluctant 量詞先嘗試「離開」。對於
A+?,由變數攜帶;對於((…)+?),由 group 的 BEGIN 與 END 攜帶。 - Empty-loopable
- 設於本體可為空的 group end(
(A? B?)+、(A | B*)+;(A?)*會先被相乘為A*,不留下 group end)。指示 runtime 在低於 min 時,於一般 loop-back 旁加上快速前進離開,以避免 cycle guard 在可產生空迭代的 group 中扼殺合法 match。 - Empty-preferred
- 設於本體偏好空 match 的 group end,如
(A?? B??){2}。在低於 min 時將快速前進離開排在 loop-back 之前,此時 group 本身的 greed 不提供任何指示。 - 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
從元素 0 開始走訪扁平陣列,
並標示滿足某種結構性情況的
元素
前三項是查詢層級的檢查:分別精確對應 §2.7(輸出面:SKIP 模式)、有界 frame(邊界破壞單調性)以及 §2.6(資料面:DEFINE 中的 FIRST 或帶 offset 的 LAST)的條件。任何一項失敗時,分析不會設定任何旗標,整個查詢的 absorption 即停用。三者皆通過時,走訪會接受四種結構形狀:
- 情況 1 — 簡單的無上界變數
-
每次迭代恰為一列。在每個共享位置上,較早 context 的計數總是 ≥ 較晚者。
A+、A*、A{2,∞} - 情況 2 — 固定長度的 group,外層無上界
-
每個子節點
(A B)+、(A B{2})+、((A (B C){2}){2})+min == max,所以本體在語意上等同於展開的{1,1}形式 —(A B{2})+的行為如同(A B B)+。每次迭代消耗固定數量的列;計數支配性仍成立。 - 情況 3 — 本體以無上界變數開頭的 group
-
開頭的無上界變數本身可吸收(情況 1)並屏蔽較早的 context。一旦 state 越過 A,absorption 便停止 — 本體其餘部分沒有單調性保證,所以 A 獲得兩個旗標,外圍的 BEGIN 獲得 in-region 旗標,B 與 END 則都沒有。
(A+ B)+、(A+ B){2} - 情況 4 — Alternation
-
經由分隔符鏈抵達的每個分支,各自依上述情況判定;任一分支合格時,alternation 標記即獲得 in-region 旗標。
A+ | B+、A+ | C D
這四種形狀未涵蓋的結構情況同樣具啟發性。A B+ 在目前規則下無法被吸收,因為開頭的 A 在無上界部分開始前消耗了一列,所以相隔一列開始的 context 處於無上界本體內的不同位置。像 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
if targetPos != currentPos:
將 targetPos 的列
取入 nav_slot
將外部 slot 指向 nav_slot
result = eval_inner_expression()
還原 current_row_slot
將 by-ref 結果從 nav_slot 複製出來
return result
訣竅在於只需儲存與還原一個 slot。內部運算式 — 不論是什麼,包括算術、函數呼叫或其他欄位參照 — 對換入的 slot 執行時,使用與目前列相同的評估路徑。沒有替代評估器,也沒有每次參照各一個的 slot;當目標為目前列時,取列與換入會完全略過。取列會將目標列複製到導覽 slot(除非該 slot 已持有該列),而還原步驟會將 pass-by-reference 結果複製到 per-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 currentPos − 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 (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − 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),以及 context absorption 究竟是否可能(§2.5 對 §2.6):只要有一個依賴 match-start 的變數,就會對整個 pattern 停用它。
- 無導覽
- 僅
PREV/NEXT LAST不帶 offset- 內部為
LAST(不帶 offset)的複合
LAST帶 offsetFIRST(任何形式)- 內部為
FIRST的複合 - 內部為
LAST(帶 offset)的複合
分類於 plan 時執行,並與每個 DEFINE 變數一同儲存,所以 runtime 不需花時間決定 — 處理一列時只需讀取每個變數的 bucket。
保留預算
導覽會碰觸 window-function 機制原本已經串流過去的列。為使這些列保持可用,executor 建構在保留近期列滑動視窗的 tuplestore 之上;問題是該視窗需要多寬。Executor 由兩個互補的 offset 算出它,每次 scan 解析每個 offset 一次(常數 offset 也會在 executor init 時解析,以便單純的 EXPLAIN 能顯示它們):
- Lookback 預算
- 任何 DEFINE 呼叫從目前列向後可碰觸的最遠距離。
- 由起點往前的 lookahead 預算
- 從最舊存活 context 的 match 起點算起的最小向前距離(負值時則向後) — 即任何 DEFINE 呼叫可能需要的最早一列。
執行期 tuplestore 的 trim mark 設為兩個位置中較早者 — 目前列減去 lookback 預算,以及最舊存活 context 的 match 起點加上 lookahead 預算。在該標記之前的任何東西都無法被任何存活 context 中的任何導覽呼叫碰觸,tuplestore 可自由丟棄。EXPLAIN 回報的 Nav Mark 行(§3.7) — Lookback 與 Lookahead — 就是這兩個預算,而非測得的峰值。每一行只在有導覽供給它時才會輸出,且即使沒有 ANALYZE 也會顯示;值僅在執行期才得知的 offset(例如 generic plan 的參數)在單純 EXPLAIN 下輸出 runtime,在 EXPLAIN ANALYZE 下輸出其解析後的值,而 retain all(Lookback)或 infinite(Lookahead)表示 offset 溢位。
3.4 Match 邊界 — SKIP、INITIAL 與有界 frame
Match 結果以兩個值記錄:match 起始的列,以及其長度。起點為負表示該位置尚未被評估;一旦起點被設定,後續對 executor 的查詢 — 「此列是否在 match 內?」 — 可透過檢視這兩個值以 O(1) 回答。長度編碼了結果:-1 表示未匹配的列,0 表示空 match,真實的 match 則為列數。長度為零是真實的結果,並非錯誤:代表 pattern 匹配但未消耗任何列,executor 必須將其與未匹配的列以及「此位置尚未嘗試 match」兩者區分。
AFTER MATCH SKIP 子句決定下次 match 嘗試從何處開始。AFTER MATCH SKIP PAST LAST ROW 移至 match 結束之後一列,產生大多數查詢想要的非重疊輸出,並啟用 absorption 最佳化。
AFTER MATCH SKIP TO NEXT ROW 僅移至 match 起始之後一列,允許重疊的 match;因此當此模式生效時,planner 會對該 window 的 pattern 停用 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,然後逐列驅動 NFA 前進 — 每列都將逐變數的 match 陣列重置為「未評估」 — 直到該 context 不再有存活 state 或 partition 結束。DEFINE 述詞採延遲評估:變數在某個 state 首次消耗它時才被評估,因此本列沒有任何存活 state 測試的變數永遠不會被評估。前進步驟本身依固定順序分為三階段 — 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)
if 它記錄了 match 且為
SKIP PAST LAST ROW:
修剪在該 match 內開始的
後續 context
順序並非風格選擇。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]
assert elem 是變數
# advance 只停駐於變數
if varMatched[elem.varId] 為
未評估:
立即評估其 DEFINE
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
或持有已記錄的 match:
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),直到該 context 記錄 match 為止,此時它被固定為 false — 吸收它會釋放一個任何吸收方 context 都無法重現的 match。兩個旗標都在 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 分支(依順序,一旦記錄
FIN 即停止)、
BEGIN(進入 group;如果 min = 0
另加一條可選 skip 路徑)、
END(loop back / exit / fast-forward —
見下文)、
FIN(記錄 matchEndRow、
儲存 matchedState,並標記
該 context,使位於此候選
範圍內的後續 context
被修剪 — 見下文),
在每次遇到變數處停止:
將 state 加入 ctx.states
(以 elemIdx + counts 去重)
記錄到達 FIN 的 state 不只是為候選 match 加上書籤。在 AFTER MATCH SKIP PAST LAST ROW 之下,下一個可回報的 match 必須嚴格地從目前 match 之後開始 — 所以一旦 Advance 處理完記錄了候選的 context,起始列落在該候選範圍內的後續 context 即在同一列被修剪,即便擊中 FIN 的 context 可能透過 greedy fallback 繼續尋找更長的 match。
此修剪是安全的,因為無論該搜尋如何結束(較長的 match 取代候選,或候選保留),所有被修剪的 context 都在下一個可回報 match 必須跳過的範圍內開始,因此永遠無法產生自身輸出。
這是跨 context 的 FIN 時點修剪步驟。在 context 內,FIN 也會截斷字面較劣的工作:Advance 丟棄其餘排隊中的 state(本節先前已敘述),且在單次 DFS 內,每條較不被偏好的路徑 — 較晚的 ALT 分支、BEGIN 的 skip 與 enter 路徑中的另一條、reluctant 變數的 enter 路徑、END 的 loop 與 exit 路徑中的另一條 — 都會在 match 被記錄後停止,因此一次 advance 最多記錄一個 match。
最棘手的逐元素邏輯位於 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
(若本體偏好空,則快速前進
優先;若第一條路徑到達
FIN,則丟棄第二條)
elif count >= elem.max:
重置此 depth 的計數
經由 next 離開
(END→END:遞增外層
END 的計數)
else:
# min <= count < max:分叉
建立離開 state
(此 depth 的計數重置)
if greedy:
先迴圈
if 迴圈到達 FIN:
丟棄離開
# 偏好較長
else 再離開
else(reluctant):
先離開
if 離開到達 FIN:
丟棄迴圈
# 偏好較短
else 再迴圈
每個加入 context 的 state 都經過去重檢查,比較其位置與計數對既有 state 清單。由於 Advance 以 DFS 順序處理分支,任何替代第一條分支的 state 先落地 — 任何稍後產生相同位置與計數的分支在插入時即被拒。這正是 §2.4 字面順序規則所要求的,並在 runtime 底層不需另外的 pass 即實作。
Empty-loopable group
Runtime 必須化解的一個微妙情況是可空 group — 由於本體的每個子節點本身皆為選擇性,本體可匹配零列的 group。像 (A? B?)+ 與 (A | B*)+ 這樣的 pattern 具有此性質:視資料而定,本體可能完全不消耗任何列即完成一次迭代。(像 (A?)* 這樣只有單一選擇性子節點的情況,會在編譯期重寫為 A*,不留下 group。)原則上這沒有問題,但它對 NFA 的 epsilon 展開造成真實的風險。若本體產生空 match,END 元素會迴圈回到本體(其 jump 為 group 的第一個子節點),本體再次產生空 match,再次到達 END,如此反覆。若沒有東西阻止,Advance 的 DFS 將永不終止。
此 guard 在編譯期決定,於 runtime 動作。每當 planner 看到本體可為空的 group 時,它將該 group 的 END 元素標記為 empty-loopable。Runtime 保留一個已造訪 bitmap,於每個 state 的 DFS 展開前清除,其中只標記這些被標記的 END — 其他東西都無法形成循環,因為任何其他 loop-back 都已消耗了一列。到達已標記的 END 表示本體剛導出一次空迭代,而 state 不會被丟棄:在下界或以上時,它在該處離開 group(空迭代使量詞停止),低於下界時,state 落入一般的 loop-back,因此每次空的抵達仍會使計數增加,直到達到 min。考慮 (A? B?){2,3} 而列流中兩個變數皆不匹配的情況:
iter 1:A? B? 匹配零列
→ END,count = 1(未達 min)
END 已被標記(於進入
group 時),但低於 min:
→ 迴圈回到 A?
iter 2:A? B? 匹配零列
→ END,count = 2(達到 min)
END 已被標記,且已達 min:
→ 離開 group
以零長度 match 退出
在低於下界時,empty-loop 標記也告訴 END 處理器在一般 loop-back 路徑外另複製一個快速前進 state:
advance_end(count 低於 min):
loop-back 路徑:
迴圈回到本體
(為下一次迭代中真正
非空的 match 保留可能性)
if elem 為 empty-loopable:
快速前進路徑:
重置此 depth 的計數
經由 next 離開 group,
將剩餘必要迭代視為
空 match
兩條路徑扮演互補角色。Loop-back 處理本體稍後仍有真實 match 可產生的情況 — 例如,在 (A? B?){2,3} 後的資料中,A 只在較晚的列匹配,loop-back 讓第二、第三次迭代得以找到非空 match。快速前進則立即離開該 group,宣告「其餘必要迭代為空」,讓 match 以零長度本體成功。決定順序的是本體,而非 group 本身的 greed:恰好在本體偏好空 match 時(像 (A?? B??) 這樣的 reluctant 本體),快速前進排在前面,且若第一條路徑到達 FIN,第二條即被丟棄,因此較不被偏好的路徑無法取代偏好的 match。插入時的去重檢查防止任一路徑生出超過其份額的 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) Advance
- 起始列落於候選 match 範圍內的其他 context — 擊中 FIN 的 context 可能仍持續尋找更長的 match(greedy fallback),但在
AFTER MATCH SKIP PAST LAST ROW之下,任何在候選範圍內的 context 都無法再產生可回報輸出(無論搜尋如何結束),故在 Advance 處理完記錄了候選的 context 後即被修剪。 - Cycle guard Advance
- 到達可空 group 中於同一 DFS 內已被標記(經由 BEGIN 進入時,或於較早的抵達時標記)之 END 的 epsilon 展開 — 否則會無限迴圈;在下界或以上時 state 於該處離開 group,低於下界時則持續迴圈。
- Empty-loop 快速前進 Advance
- 在可空 group 的下界以下,一條離開 group 並宣告其餘必要迭代為空的額外路徑,並依本體的偏好與 loop-back 排定先後。
- 有界 frame 截止 Match
- match 已達使用者指定 frame 上界的 context — 強制不匹配以避免越界(§3.4)。
依 phase badge 閱讀條目可追蹤 context 的生命週期:修剪在每列穿越三個主要階段時觸發(Match、Absorb、Advance)。改依描述閱讀則依目標分組規則:死掉的分支、冗餘 context、等價 state、無限迴圈,以及超出使用者邊界的越界延伸。
任一單一規則皆不足。Empty-loop 快速前進單獨無法阻止無限 epsilon 迴圈;absorption 單獨在 DEFINE 參照 match-start 時會過度合併;去重單獨只移除冗餘的 state,無法移除冗餘的 context。Runtime 在重要情境中保持線性 — PATTERN (A+ B+ C+ D) 在 100,000 列上、海報面板 ③ 的 benchmark — 只因為每一層都抓住其上層所遺漏的。原始碼記載了這些層未能抓住的情況:去重會將僅在 min 以上計數不同的 state 分開保留,因此在 C 永不為真時,(A{2,} B)+ C 在峰值時持有 Θ(n²) 個 state,並建立 Θ(n³) 個 state(320 列需 37 秒);而一連串全部可空的替代會逐條路徑列舉,因此 (A?|B?){30} 需要超過半小時。
3.7 EXPLAIN 輸出
對使用 RPR 的查詢執行 EXPLAIN ANALYZE 會呈現一般 window function 沒有的 NFA 層級統計。在 text 格式中,它們與 window 運算子一起發出,位於 Pattern: 行、任何 Nav Mark 行(單純的 EXPLAIN 也會顯示)以及 Storage: 行之後:
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(各自僅在 DEFINE 使用了
供給它的導覽時出現)
NFA States: N peak, N total, N merged
NFA Contexts: N peak, N total, N pruned
NFA: N matched (len min/max/avg),
N mismatched (len min/max/avg)
NFA: N absorbed (len min/max/avg),
N skipped (len min/max/avg)
(第二個 NFA 行僅在任一計數
非零時出現;計數為零時
不輸出其 (len ...))
非 text 格式將每個計數各自作為屬性發出。Peak 與 total 是 runtime 的直接量測:曾同時存活的 state 數、查詢生命週期內建立的 state 數,以及被去重合併掉的 state 數;pruned 計算在單一列後即失敗的 context。Match 長度的直方圖分為四種結果 — 成功 match、在超過一列後才失敗的 match 嘗試(mismatched)、被吸收的 context,以及因在已記錄的 match 內開始而被 AFTER MATCH SKIP PAST LAST ROW 釋放的 context(skipped) — 並以 min/max/avg 回報,能一眼揭示效能病灶:健康的執行會顯示大多數 context 為 matched 或 absorbed,且 mismatched 長度較小。
兩個 Nav Mark 計數器回報 §3.3 由 DEFINE 推導的 tuplestore 保留預算。Lookback 是 PREV、任何 offset(包括預設的 0)的 LAST,以及內含 LAST 的複合形式中,從目前列算起最深的向後距離;Lookahead 是從最舊存活 context 的 match 起點測量,由 FIRST 與內含 FIRST 的複合形式所貢獻的最小向前距離(當它看向 match 起點之前時為負值)。
當 offset 為常數時,每個計數器列為固定整數;當 offset 為僅於每次 scan 才得知的非常數運算式時列為「runtime」;且 — 僅限 Lookback — 當 offset 溢位時列為「retain all」;溢位的 Lookahead 則列為「infinite」。每一行僅在 DEFINE 中有導覽供給它時發出,且兩者在單純的 EXPLAIN 下也會出現:常數 offset 於 executor init 時確定,而值僅在執行期才得知的 offset(例如 generic plan 的參數)在該處列為「runtime」,在 EXPLAIN ANALYZE 下則列出其解析後的整數。
這些計數器加總,使得無需將 gdb 附加到 backend 也能除錯 RPR 效能。
除計數器外,EXPLAIN 會輸出一個由編譯後元素陣列建立的 Pattern: 行,因此它顯示的是編譯期重寫後的 pattern(PATTERN (A A) 會 explain 為 a{2}),並帶有 absorption 標記 #(比較點)與 ~(可吸收區域);DEFINE 與 AFTER MATCH SKIP 選項則不顯示。依原樣重現子句(包括 reluctant 量詞、group 重複與 skip 選項)是 pg_get_viewdef() 的工作,它為使此 round-trip 穩定下了相當功夫,讓 pg_dump 與 pg_upgrade 能在不發生語意漂移下保留 RPR 物件 — rpr_explain 之下的 regression suite 逐案驗證之(見 §4)。
§4. 測試 — 覆蓋率地圖
Patch 隨附五個 regression suite,合計覆蓋 §3 中描述的每一層 — 約 22,000 行 SQL,每個 suite 聚焦於不同關注點。此拆分為刻意之舉:將 parser 議題、runtime 正確性、planner 互動與輸出格式分置不同檔案,能讓失敗更易於定位,並避免某層的無關變更意外使另一層的測試失效。五個 suite 為:
- rpr
- WINDOW 子句整合 — 在合成的股票資料上執行真實 window 情境(V 形、W 形、連續上漲、反轉),外加導覽語意與 DEFINE 限制錯誤。
- rpr_base
- Parser 層 — 關鍵字接受、語法形狀、量詞、導覽解析、錯誤訊息,以及 pg_dump/pg_upgrade round-trip 穩定性;外加 planner 層 — pattern 最佳化、absorption 旗標、最佳化 fallback、planner 整合。
- 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,是簡化的 — PREV/NEXT 巢狀與非常數 offset 錯誤、DEFINE 參照規則,以及導覽 offset 語意。
因為這些查詢結合每一層(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 一個 — 而非長的真實查詢,因為目標是覆蓋率而非情境真實性。第二部分是 planner 層,涵蓋 pattern 最佳化、absorption 旗標的顯示與分析、最佳化 fallback,以及 planner 整合(子查詢、join、集合運算、排序與分組)。
序列化測試值得特別注意。RPR 物件(view、materialized view、pg_dump 輸出)必須在通過 catalog 表示時 round-trip 而不發生語意漂移,包括量詞上的 reluctant 旗標或複合導覽運算式的精確形式等細節。一小組序列化專屬物件(rpr_serial_v* view 與其支撐表)在執行結尾刻意保留,使周圍的 regression 基礎設施能接手並對之執行 pg_dump 與 pg_upgrade。其餘測試框架照常 drop。像反解析與重新解析間遺失 reluctant 旗標這樣的缺陷,只在端到端 round-trip 時才會浮現。
4.3 rpr_nfa — runtime 引擎
這是執行 §3.5 與 §3.6 中所有機制的 suite。其測試遵循一致的 pattern:行內 VALUES 的各列帶有一個變數名稱陣列,宣告哪些 DEFINE 變數在該列匹配,並配上一個探測特定 runtime 行為的 pattern。此陣列慣用法將 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 輸出是面向使用者契約的一部分 — 第三方工具(監控儀表板、log scraper)會解析它,看似化妝性的變更可能將之打破。rpr_explain suite 驗證三件事:
- NFA 計數器出現於正確位置 — 每個 WindowAgg 的統計(peak/total/merged states、peak/total/pruned contexts、matched/mismatched/absorbed/skipped 的長度直方圖)在
EXPLAIN ANALYZE下以 text、JSON 與 XML 及文件標籤顯示,且 Nav Mark Lookback 與 Lookahead 恰在 DEFINE 中有導覽供給它們時出現。 - 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為row_number、rank與ntile等與 frame 無關的 window function 改寫為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 或 SKIP)
- 具相同
PATTERN但不同DEFINE子句或不同AFTER MATCH SKIP的兩個 RPR window 會產生不同 match,必須維持區別,即便結構形狀相同。 - 未使用輸出投影
- 這一項允許套用:當外圍查詢從不讀取 window 的輸出時,window function 會變成 NULL,其 WindowAgg 被移除,列數不變。測試檢查當 WindowAgg 保留時,DEFINE 讀取的欄位仍能到達 WindowAgg,以及當其值被讀取時 window 會被保留。
- Moving-aggregate inverse transition
- 具反向 transition function 的 window 彙總通常可隨 frame 移動而增量評估。RPR 的 reduced frame 並非滑動視窗;inverse transition 路徑會產生錯誤結果。
其他案例檢查成本估算會考量 DEFINE、持有 RPR window 的子查詢不會被攤平、DEFINE 運算式不會洩漏至上層 WindowAgg,以及 LIMIT 維持在 WindowAgg 之上;第二組則將 RPR 與 CTE、join、集合運算、prepared statement、分割資料表及類似構造一起執行。大多數受防護的案例遵循相同形狀:觸發該最佳化的基準(通常是非 RPR 查詢,並於 EXPLAIN 中檢查),接著是結構相似、該最佳化未套用的 RPR 查詢 — 對於 DEFINE/SKIP 去重案例,基準是兩個相同的 RPR window,而 inverse-transition 案例則以記錄 log 的彙總而非 EXPLAIN 檢查繞過。兩半合在一起證明 planner 中的防護真的在做事,而非未經實際驗證即放行所有查詢。
這也是為何 §3.4 篇幅短的原因。「Match 邊界」機制 — reduced frame、SKIP、INITIAL、有界 frame 截止 — 於他處有操作性測試;rpr_integration 所驗證的是沒有其他 optimizer 階段在過程中干涉它們。rpr_integration 通過正是讓其餘 suite 能信任其輸入未被竄改地送達 executor 的關鍵。