2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition ディープダイブ

PostgreSQL 上に実装された ISO/IEC 19075-5 · SQL R020 のガイドツアー — 何を構築し、何がまだ書かれていないか、そして実際にどう動くか。

PGConf.dev 2026 で展示されるポスターの伴走資料。
標準を概観し、実例をたどり、設計を眺めたうえで、自分のパターンでライブ NFA シミュレータを動かしてください。
議論: pgsql-hackers スレッド · 最新 パッチ (v55) · commitfest #4460。
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

AI事前翻訳 — 誤訳の可能性あり。

§1. 標準、サブセット、そして残された課題

1.1 標準の範囲

Row Pattern Recognition は ISO/IEC 9075-2:2016 で SQL に導入され、関連文書 ISO/IEC 19075-5:2021(Part 5、"Row Pattern Recognition")に記述されている。

標準は同一の基盤メカニズムに対して2つの表面(surface)を定義する。機能 R010 は MATCH_RECOGNIZE 句を FROM リストに置いて派生テーブル(derived table)を生成する形で、機能 R020 は同じパターンロジックを WINDOW 仕様に折り畳んでウィンドウ関数の出力を生成する形である。2つの表面は構文と意味論の多くを共有するが(19075-5 は §6.3.3 で R020 固有のいくつかの相違点を挙げている)、機能的には別個の入り口であり — データベースはどちらか一方または両方を実装できる。

ここで議論するパッチシリーズは R020 のみのサブセットを実装する。テーブル句形式は意図的に範囲外である。

R020 表面は小さいが表現力に富む。クエリは、フレームが ROWS BETWEEN CURRENT ROW AND … であるウィンドウ仕様内に句を追加してパターンをウィンドウに付ける。PATTERN は名前付きパターン変数に対する正規表現を記述し、DEFINE は各変数を識別するブール述語を供給し、省略可能な AFTER MATCH SKIP(既定は PAST LAST ROW)はパーティション内で連続するマッチがどう配置されるかを制御する。

オプションの MEASURES、SUBSET、INITIAL/SEEK、補助関数 CLASSIFIER() が機能を仕上げる。(標準の MATCH_NUMBER() 関数は R010 表面のみに属し、19075-5 §6.3.3 (6) は R020 から明示的に除外している。)

このパッチは非自明なクエリを動作させるのに十分な語彙をカバーするが、まだ構築されていないインフラに実装が依存する一部の構文には踏み込まない。

本節の残りでは、標準の語彙をパッチが既に支援するものと意図的に後回しにしたものに分けて整理する。下の一覧はパッチシリーズの現状を反映している。

1.2 実装済み機能

実装された語彙は、row pattern recognition を動機づける典型的な V 字、W 字、反転(reversal)パターンを表現するに十分である。さらにすべての標準数量子 — 7つの reluctant 変種 *?、+?、??、{n}?、{n,}?、{,m}?、{n,m}? を含む — と、DEFINE 条件が隣接行を比較するのに必要な4つのナビゲーション原始操作を網羅する。

PATTERN 句
ウィンドウ仕様内に row pattern を定義する。相異なるパターン変数は最大 240 個まで。
ウィンドウフレーム
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING または n ≥ 1 の ROWS BETWEEN CURRENT ROW AND n FOLLOWING(19075-5 §6.10.2)。それ以外のフレームは拒否され、受け付けられる除外指定は EXCLUDE NO OTHERS のみである。
正規表現: + * ? |
標準数量子と選択(alternation)。
正規表現: ( ) グループ化
括弧で囲まれた部分パターン。
正規表現: {n} {n,} {,m} {n,m}
限定された(bounded)反復回数。
Reluctant *? +? ?? {n}? {n,}? {,m}? {n,m}?
標準が定義する7つの reluctant(非貪欲)変種すべて(absorption 最適化からは除外)。
DEFINE 句
各パターン変数を識別するブール条件。
ユニバーサル行パターン変数
DEFINE 内の修飾なし列参照(例: 素の Price)は現在行に解決される(19075-5 §4.10/§4.16)。
PREV, NEXT (オフセット付き)
現在行の n 行前/後の行へアクセス(既定 1)。内部引数はナビゲート先の行で評価される。
FIRST, LAST (オフセット付き)
マッチ相対の行へアクセス。FIRST(expr, n) はマッチ開始から n 番目の行を、LAST(expr, n) は最新のマッチ行から n 行前を指す。
複合ナビゲーション(四形式)
内側の FIRST/LAST に外側の PREV/NEXT ステップを重ねた形: PREV(FIRST(expr))、NEXT(FIRST(expr))、PREV(LAST(expr))、NEXT(LAST(expr)) — 内側と外側のステップそれぞれが独自のオフセットを取れる。
ナビゲーション名
DEFINE 内で修飾なしの呼び出しとして書かれた PREV、NEXT、FIRST、LAST は常にナビゲーションを意味する。同名のユーザ関数はそこではスキーマ修飾しなければならない。
ナビゲーション引数
PREV、NEXT、FIRST、LAST では、内部引数は少なくとも1つの列参照を含まなければならず、オフセットは実行時定数でなければならない。
INITIAL
パターンマッチは現在行から開始しなければならない(既定)。
AFTER MATCH SKIP PAST LAST ROW
既定の skip モード。context absorption の対象。
AFTER MATCH SKIP TO NEXT ROW
マッチの重なりを許可。absorption を無効化。

1.3 未実装

未実装の機能は大まかに3つのグループに分類される。最初の — そして最大の — グループは MEASURES を中心とする構文ファミリーである。MEASURES 句そのもの、SUBSET、CLASSIFIER()、B.price のようなパターン限定(pattern-qualified)列参照、そして LAST(B.price) や PREV(B.price) のようなパターン限定ナビゲーションがここに含まれる。

これらは独立した欠落というより一つの欠けた断片を異なる角度から見たものである。実行器は マッチ単位の履歴(per-match history) — マッチ内の各行がどのパターン変数にマップされたかの記録 — を保持する必要があり、これらの構文はどれも履歴なしには意味を持たない。CLASSIFIER() はその記録から変数名を読み、B.price は記録項目が B である行の price 列を読み、LAST(B.price) は同じ行集合をたどって最後の一つを選び、SUBSET U = (A, B) は両バケットを束ねる仮想変数を定義し、MEASURES はまさにその集約を用いて AVG(U.Price) のような式を評価する。

現在の実行器は DEFINE 述語を行ごとに評価するが、結果として得られる変数割当をどこにも記録しない — 後から問い合わせる対象がない。したがって履歴インフラの構築がこのグループ全体の前提であり、記録さえ存在すれば個々の機能は小さな射影として自然に得られる。

第二のグループは代替の skip 対象である。AFTER MATCH SKIP TO FIRST var と AFTER MATCH SKIP TO [LAST] var がこれにあたる(素の SKIP TO var は SKIP TO LAST var を意味する)。これらもマッチ履歴に依存する。実行器が最新のマッチ内で特定の変数にマップされた行を指せる必要があるからだ。

残りは雑多な末尾項目である。SEEK キーワード(INITIAL の代替)、空パターン ()、除外(exclusion)形 {- … -}、順序無関係演算子 PERMUTE、そして DEFINE 内の集約関数とサブクエリ(いずれも現在は拒否される。変数限定の集約はマッチ履歴も必要とする)。

MEASURES
マッチごとの出力式に名前を付ける、例: MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg。R020 ではウィンドウ関数のように OVER を介して露出される。FINAL/RUNNING キーワード(19075-5 §5.4)を受け入れるが、R020 では measures が常にマッチの最終行で評価される(19075-5 §6.9 (3))ため両者は同じ値に縮退する。
SUBSET
パターン変数の名前付き和集合、例: SUBSET U = (A, B, C)。パターン変数が参照可能なあらゆる場所で使用可能 — MEASURES、DEFINE 内のパターン限定参照、CLASSIFIER(U) — いずれもマッチ履歴を必要とする。
CLASSIFIER()
与えられた行がどのパターン変数としてマッチしたかを返す。DEFINE と MEASURES の両方で定義される(19075-5 §5.9)。任意の行での答えはその行に対するマッチ履歴に記録された変数名。
パターン限定列参照
DEFINE や MEASURES 内の単純な B.price — 名前付き変数としてマップされた行の列の値。
パターン限定ナビゲーション
名前付き変数としてマッチした行にナビゲーションを制限、例: LAST(B.price)、FIRST(B.price)、PREV(B.price)、NEXT(B.price)。
SEEK
マッチが現在行から完全なウィンドウフレームの末尾までの任意の行で開始可能(INITIAL と対照的)。
AFTER MATCH SKIP TO FIRST var
名前付き変数としてマッチした最初の行へ skip。
AFTER MATCH SKIP TO [LAST] var
名前付き変数としてマッチした最後の行へ skip。
正規表現: {- -}
除外(exclusion) — マッチした行を ALL ROWS PER MATCH の出力から取り除く。このオプションはウィンドウには適用されない(19075-5 §6.3.3 (4))ため、ウィンドウではこの構文は許可される(§6.13)が、作用する出力がない。
正規表現: ()
空パターン — 空シーケンスにマッチ。
PERMUTE(...)
列挙された変数間の順序無関係マッチ。キーワードは認識されたうえで拒否される("PERMUTE is not supported")。permute はパターン変数名としては引き続き使える。
DEFINE 内の集約関数
SUM、AVG、COUNT のような集約関数は DEFINE 述語に使えない。標準は部分マッチに対する running 集約としてこれを許す。AVG(B.Price) のような変数限定の集約は MEASURES/CLASSIFIER() が要求するのと同じマッチ単位の履歴に依存し、限定なしの集約はそれまでのマッチの全行にわたる。
DEFINE 内のサブクエリ
DEFINE 内のサブクエリはすべて拒否される。標準は row pattern recognition を行わず row pattern 変数を参照しないサブクエリを許すが、パッチは現時点では過剰に拒否している。

欠落と取り違えやすい補足が4つあるので、ここで触れておく。

第一に、パターンアンカー ^ と $ は標準自身が WINDOW 句の RPR で許可していない(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 表面のみに属し、ここでの不在は欠落ではなく標準準拠である。

第三に、標準が R020 に課す構造的禁止事項(19075-5 §6.17): row pattern recognition は別の row pattern recognition の中に入れ子にできない。MEASURES と DEFINE は外部参照(outer references)を含めない。MEASURES や DEFINE 内のサブクエリは row pattern 変数を参照できない(パッチはさらに踏み込み、上記のとおり DEFINE 内のサブクエリをすべて拒否する)。RPR は再帰クエリの中で使えない。パッチは外部参照の規則("cannot use outer query column in DEFINE clause")と再帰の規則を強制し、後者は WITH RECURSIVE 句のすべての要素に適用する。また DEFINE 内の volatile 関数と行全体参照(whole-row reference)も拒否する。

第四に、MATCH_RECOGNIZE 自体 — 同じメカニズムのテーブル句表面である機能 R010 — はこのパッチの範囲外である。PostgreSQL がいずれ R010 を追加するかは未来のパッチシリーズの問題であって、今回のシリーズの評価尺度ではない。

出典. 本節の実装済み/未実装の一覧はパッチシリーズの現状を反映しており、具体的には v55(2026-11-17)時点である。

§2. 例 — 実際の動き

本節の例は段階的に積み上がる。まず row pattern matching が文字列パターンマッチングと本質的に異なる概念的理由から始め、次に DEFINE 条件を興味深くする4つのナビゲーション関数を紹介し、最後に5つの例題をたどる。単一マッチ(NFA の動き)、選択(alternation)、簡単な場合の context absorption、そして absorption が無効化される2つの場合である。

ナビゲーションを安価にする内部メカニズム — 1 スロットのタプル交換 — は実行器の設計に属し、ここではなく次節で扱う。

2.1 行パターンがテキストパターンと異なる理由

テキスト正規表現は文字ストリームにマッチし、すべての位置で考慮すべきシンボルは正確に一つである。ランタイムの問い — 「現在のシンボルは 'A' に等しいか?」 — は単一の Yes/No の答えを持つ。バックトラッキングオートマタはこれを利用する。文字あたり高々一つの分岐だけが生き残り、曖昧さのコストは入力を読み直すことで支払われる。

row pattern は根本的に異なる。行は単一シンボルではなく、列のタプルであり、複数のブール述語、すなわち DEFINE 条件に対して評価される。2つの述語が同じ行で同時に真となり得て、標準はそれらが相互排他であることを要求していない。次を考えよ:

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

price = 150, volume = 2000 の行は A と B の両方を満たすが C は満たさない。パターンマッチャはこれを単一状態に縮約できない — 2つのパターン変数が生きており、いずれを名指すパターン要素も前進し得る。したがって NFA はパーティション行ごとに一つでなく 複数の同時状態を保持しなければならない。

テキスト正規表現と行パターンの対比: テキスト正規表現はシンボルごとに単一状態で進むが、行は複数の DEFINE 述語が並列にマッチし得る。 TEXT REGEX single state advances through symbols A B C one symbol per position · one transition ROW PATTERN one row, multiple predicates evaluated row price = 150 · volume = 2000 A ✓ price > 100 B ✓ volume > 1000 C ✗ price > 200 two predicates true · two states stay alive
テキスト正規表現はシンボルごとに一つの状態へ縮約される。行は複数の DEFINE 述語を同時に満たし得るため、複数の状態が並列に生き残る。

この一つの観察が以後のアーキテクチャを規定する。実行状態はコンテキストのリストで、各コンテキストは状態のリストであり、行ごとにランタイムは各状態に「ここで真の変数を踏まえると、どこへ行けるか?」と問う。生じる分岐こそ、ランタイムが複数の枝刈り層 — コンテキスト内の状態重複除去、コンテキスト間の absorption、そして §3.6 で概観されるその他の規則 — を必要とする理由である。それらがなければ、生きている状態とコンテキストの数はパーティションに比例して増え、パターンマッチングのコストは超線形になる。

2.2 ナビゲーション関数

現在行のみを参照する DEFINE 条件は限られる。興味深いパターンのほとんどは、現在行を隣接行と、あるいはマッチ内で既に受理された行と比較する必要がある。標準はこのために4つのナビゲーション関数を提供し、パッチはそのすべてを実装する。

PREV(expr [, n])
現在行の n 行前の行(既定 n = 1)。「今日 vs 昨日」の比較に使用。
NEXT(expr [, n])
現在行の n 行後の行(既定 n = 1)。前方先読み。ウィンドウ形式ではウィンドウが単調なため珍しい。
FIRST(expr [, n])
現在のマッチの最初の行から n 行後の行(既定 n = 0、すなわち最初の行そのもの)。「このマッチを開始した行と比較せよ」。
LAST(expr [, n])
最後のマッチ行から n 行前の行(既定 n = 0)。DEFINE 内では最後のマッチ行は現在行なので、LAST(price) は現在行を読む。

4つの原始操作は合成可能である。PREV と NEXT は FIRST や LAST 呼び出しを包めて、「マッチ相対の行へ移動し、そこから固定距離だけ移動する」という意味の4つの複合形を作る。これにより DEFINE 式は、たとえばマッチ開始直前の行を読める。

PREV(FIRST(expr [, n]) [, m])
FIRST(expr, n) が読む行から m 行戻る(既定 n = 0、m = 1)。「このマッチが始まる直前の値は?」。
NEXT(FIRST(expr [, n]) [, m])
FIRST(expr, n) が読む行から m 行進む。現在行に依存せずマッチの内側に踏み込む。
PREV(LAST(expr [, n]) [, m])
LAST(expr, n) が読む行から m 行戻る。「最新のマッチ行の少し前の行と比較」。
NEXT(LAST(expr [, n]) [, m])
LAST(expr, n) が読む行から m 行進む。

ここで実用的に二点指摘しておきたい。第一に、ナビゲーションは合成できる。PREV(FIRST(price)) はマッチ開始直前の行を読み、パッチはこれを支援する。第二に、ナビゲーションは実行器の最適化に影響する。素の PREV と NEXT は現在行基準であり常に安全だが、FIRST およびオフセット付きの LAST 変種は、単独でも複合 PREV/NEXT の内側でも、マッチ境界基準であり、context absorption と相互作用する。その場合プランナはパターン全体の absorption を無効化する。その相互作用の仕組みは §2.6 の主題である。

2.3 例題 1 — NFA の移動

例の目的シンプルな非吸収パターン上で行ごとの NFA 状態の変遷を示す。トレースは行 0 で始まったコンテキストを追う。行 1–4 で始まったコンテキストはそれと並行して走り、そのマッチが記録されると 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)
);

パターンは四要素に平坦化される:

[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 に対して:

行価格真の変数動作
0100START新しいコンテキスト。START がマッチし即座に退出(max=1)。状態は UP+ へ前進。
1110START, UPUP マッチ。前進時に分岐: 一つは UP でループ、もう一つは DOWN+ へ退出。
2120START, UPループ状態で UP マッチ後、再び分岐。行 1 の DOWN 状態は消滅(120 ≮ 110)。
3115START, DOWNループ状態の UP が失敗して消滅。行 2 の DOWN 状態がマッチ。前進時に分岐: DOWN でループ、#FIN へ退出 — 行 0–3 にわたるマッチ候補が記録される。
4108START, DOWNループ状態で DOWN マッチ後、再び分岐。行 0–4 にわたる新しい FIN 候補が短い方を置き換える。
5130START, UPループ中の DOWN 状態が失敗(130 ≮ 108)。このコンテキストに生存状態が残らないため、記録された候補(行 0–4)がマッチとして確定。次の試行は行 5 で始まる。START はマッチするが、UP を見る前にパーティションが終わる。

要点: 行 3 ではその行が START(常に真)と DOWN の両方を満たすが、START が意味を持つのは行 3 で始まるコンテキストに対してのみである。このコンテキストではループ中の UP 状態が消え、DOWN+ で待つ状態だけが前進する。§2.1 の多状態性はあらゆる UP マッチでのファンアウトとして可視化される(状態は UP+ に留まるか DOWN+ に進めた)。greedy 優先は「退出前にもう一度ループ」なので、データが十分なら反復分岐がマッチをさらに伸ばす。ここではループ中の DOWN が行 5 で消え(130 ≮ 108)、行 4 で DOWN が退出した際に生まれ、行 3 の候補を置き換えた最後の FIN 候補(行 0–4)がマッチとして確定する。

クエリの結果はこのトレースから直接導かれる。RPR 意味論では、ウィンドウ関数 first_value(price) と last_value(price) はマッチを開始した行でのみ評価される — マッチ内の他の行は reduced frame が空なのでこれらのウィンドウ関数に対して NULL を返す。したがって私たちのデータの出力はポスターの右上パネルの表のようになる:

行価格start_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

行 0 はマッチ開始なのでフレームは行 0–4 を覆い、ウィンドウ関数は V 字の始値($100)と底値($108)を報告する。行 1–4 はマッチ内だが開始ではないので NULL を受け取る。行 5(価格 $130)はどのマッチの外でもないため同様に NULL を受け取る。

2.4 例題 2 — 選択と語彙順序

例の目的一つの行が複数の選択肢を満たすとき、単一コンテキストがどのように複数の並列状態を抱えるか、また標準がどうタイブレークするかを示す。

(A | B) 形式はマッチャに選択を与える。任意の行で2つの選択肢が独立に検査され、いくつでもマッチし得る。ここで §2.1 の多状態性が単一コンテキストの内側で可視化される — コンテキスト間ではなく(それが absorption)、実行器がパターン順に、先の分岐から探索する並列分岐に沿って。

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

価格が上昇しかつ $100 を超えた行を想像せよ — UP と HIGH が共に真。各選択肢は自分の状態を生む。一方は UP 分岐を歩き、他方は HIGH 分岐を歩く。その後両者は DONE へ前進し、そこで合流する。

行真の変数生存状態
RUP, HIGH状態 A(UP 分岐)と状態 B(HIGH 分岐)はどちらも同じカウントで DONE へ前進する。B は A の重複であり破棄される
R+1DONE状態 A が DONE にマッチし #FIN に到達

標準の用語でいえば、両分岐は同じ行に対して同じ長さのマッチを生み、2つの候補経路を与える — UP, DONE ラベルと HIGH, DONE ラベル。標準はこれを語彙順序(lexical order)で決する。(UP | HIGH) に書かれた選択肢のうち先に書かれた方がマッチ長と無関係に勝つ。UP が HIGH の前にあるので、生き残る経路は UP, DONE。実行器はこれを FIN ではなく行 R で強制する。UP 分岐の状態を先に追加するので、nfa_append_state_unique() がそれを保持し、同一の HIGH 分岐の状態を落とす。

語彙順序は、いずれ CLASSIFIER() が実装されたとき、それを well-defined にするものである — 両述語が真でもランタイムは「この行は HIGH ではなく UP としてマッチした」と利用者に伝えられる。語彙順序は選択の第一規則だ。lex 上前の分岐は、lex 上後の分岐がより長いマッチを生むとしても勝つ。lex 上後の(おそらくより短い)分岐は、すべての lex 上前の分岐が FIN に到達する前に消えた場合にのみ勝てる。greedy の長さは単一数量子の内部で決まる — 同じ選択分岐の二通りの完了が与えられたとき、greedy 数量子は反復回数の多い方を選好する。

2.5 例題 3 — Context absorption(同じ運命)

例の目的素朴な O(n²) の総状態処理量が absorption の下でなぜ O(n) になり、生存コンテキストが O(1) になるかを示す。

absorption を最も単純に示すパターンは DEFINE A AS TRUE を持つ PATTERN (A+) である。すべての行が A にマッチし、標準はマッチャがすべての行を可能なマッチ開始として考慮することを要求する。素朴に行えば N 行のパーティションに N 個のコンテキストが生じる。5行のパーティションを取ろう(データは何でもよい — 述語は定常真):

行素朴なコンテキストabsorption 適用後
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 吸収
2C1[A:3], C2[A:2], C3[A:1]C1[A:3]
3C1[A:4], C2[A:3], C3[A:2], C4[A:1]C1[A:4]
45つのコンテキストC1[A:5]

生存コンテキストは O(n) から O(1) へ減り、パーティション全体での総量は O(n²) から O(n) に下がる。破棄を正当化する absorption 規則は、数量子が無界のときシンプルである:

Absorption 規則. 生存状態が同じパターン要素にあり、古い側のコンテキストのカウントが新しい側以上である2つのコンテキストは、無界数量子の下で同一の未来を持つ。新しい方は破棄できる。新しい方が最終的に見つけるどんなマッチも、古い方はそれ以上または同等のものを見つける。

ポスター左下のパネル(「① Context Absorption」)はまさにこの規則を5行に渡って可視化したものである。

規則には微妙だが重要な点が潜む。破棄が安全なのは、述語 A AS TRUE がどのコンテキストが問おうと全行で同じ値に評価されるからだ。同じことは現在行のみ、あるいはそこからの固定オフセットのみを参照する任意の述語にも当てはまる — PREV を含む。次の例は PREV ベースの述語を用い、価格の具体的な一週間に切り替える。§2.6 はその同じ一週間を再利用して安全な吸収と安全でない吸収の対称性を明白にする:

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

月曜から金曜までの取引週 $100, $108, $112, $116, $110 を取る — 4度の上昇のあとに突然の下落。C1 が火曜に始まる(RISE が初めてマッチする日: $108 > $100)とし、実行器は投機的に水曜に始まる C2 も追跡する。各行の RISE 条件はその行の価格を直前の価格と比較する — これはパーティションレベルの事実であってコンテキストレベルの事実ではない — ので、2つのコンテキストは共有するすべての行で同じブールを計算するよう強制される:

曜日価格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 ✗ — 確定
同じ運命 C1 と C2 が共有するすべての行で両者は同一の式を評価し同一の結果を生む — そして金曜にまさに同じ比較で消滅する。C2 が持つどんな未来も C1 は持つ。C2 を C1 に吸収しても何も失わない。

述語が各コンテキスト自身の境界に依存し始めた瞬間、物語は崩れる — それが §2.6 の主題である。

2.6 例題 4 — 吸収が安全でなくなる時

例の目的DEFINE が FIRST を参照すると何が変わるかを示す — absorption 規則はもはや成立せず、プランナはそのパターンの absorption を無効化する。

アナリストが、株価がランの開始日から 10 ドル以内に留まった連続営業日を見つけたいとする — 一種の保ち合い(consolidation)ウィンドウである。パターンと DEFINE は次のとおり:

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

条件は今や現在行の価格を現在のランの開始での価格と比較する。異なる日に始まった2つのランは異なる FIRST(price) 値を持つので、同じパターン要素・同じカウントの2つの状態はもはや交換可能ではない。それらの未来は absorption が捨てようとしていた境界に依存する。

§2.5 と全く同じ取引週を取る — 月曜から金曜までの $100, $108, $112, $116, $110。ランタイムは再び2つの候補ランを同時に生かしておく。C1 は月曜開始、C2 は火曜開始(STABLE+ の下ではすべての行が潜在的なラン開始である)。

曜日価格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 ✓ (継続中)
異なる運命 C1 は水曜に2日のラン(月–火)で消滅。C2 は単独なら金曜まで走り続けるはずである。同じ価格、同じ形の問い — しかしそれぞれのマッチ開始から導かれる異なる天井。同じ日に2つのコンテキストは正反対の結論に達した。

absorption の下では C2 は火曜に C1 にマージされていただろう — マージされたコンテキストは C1 の天井($110)しか持たないので、C2 の異なる視点(天井 $118、金曜までの4日のラン)は C1 の未来に覆われない。この週に限っては出力はたまたま変わらない。C1 は月–火を記録し、C2 はそのマッチ内で始まったので SKIP PAST LAST ROW によって破棄され、次の試行は水曜に独自の天井($122)で始まり水–金にマッチする。しかし一般には、先のコンテキストの DEFINE 結果がもはや後のコンテキストのものを包含しないので、absorption が依拠するカウント比較は無効になる。DEFINE 述語がマッチ開始依存性を伴うなら、プランナは先回りして absorption を無効化する。

(先頭のコンテキストのマッチが実際に成功した場合、その受容スパン内で開始したコンテキストは — 既定の AFTER MATCH SKIP PAST LAST ROW の下で — 単に破棄される。先頭のマッチが失敗した場合に立ち戻れる場所として生かされていただけだ。)

下の表はポスター右下パネル(「② Navigation」)を複合形式で拡張したもので、どのナビゲーション形式がマッチ開始依存性を生むかを要約する:

ナビゲーションマッチ開始依存性吸収可?
PREV, NEXTなしはい
LAST (オフセット無し)なしはい
LAST オフセット有り境界チェックいいえ
FIRST (任意)直接いいえ
複合 (内側 FIRST)直接いいえ
複合 (内側 LAST、オフセット無し)なしはい
複合 (内側 LAST オフセット有り)境界チェックいいえ

§2.5 と §2.6 の2つの例は単一の規則に還元される。同じ運命が absorption を安全にする。同じパターン要素のすべてのコンテキストが今後の述語すべてに同じ答えを計算するなら、最古の一つだけ残せばよい。異なる運命は absorption を安全でなくする。述語がコンテキスト固有の状態で分岐し始めた瞬間 — まさに FIRST とオフセット付きの LAST がする事 — 生きているすべてのコンテキストは他のどのコンテキストも覆うことが保証されない未来を表し、そのいずれかを破棄することはもはや安全だと示せない。

プランナはこの区別をコンパイル時に検出し、パターン全体について absorption をオンまたはオフにする。オフのときランタイムは複数コンテキストのコストを払う。ポスターのパネル ③ ベンチマークは FIRST を使わないので absorption はオンのままであり、これが PostgreSQL が成功事例でも失敗事例でも線形に保たれる理由である。

ポスターのベンチマーク数値は同じアルゴリズムが大規模で展開された姿である。成功パターン (A+ B+ C+ D) では PostgreSQL と Trino はともにマッチが確定すればおおよそ O(n) でスケールし、PostgreSQL は約 16× から 33× リードする(Trino の数値は既に JVM 起動を除外している)。

失敗パターン (A+ B+ C+ E) では absorption を持たないとみられる Trino はすべての潜在的マッチ開始を追い、O(n²) よりもさらに速く劣化する(行数 5× で時間約 56×)。100,000 行で五時間以上を要するのに対し、PostgreSQL は依然 92 ミリ秒で終わる。約 217,000× の高速化である。

この差はエンジニアリングの磨き上げではない — まさに §2.5 と §2.6 の同じ運命/異なる運命の区別を、パーティション内のすべての潜在的マッチ開始のすべての行に適用した結果である。

2.7 例題 5 — SKIP が absorption を無効化する時

例の目的absorption が失敗する第二の道を示す。述語が分裂するからではなく、出力意味論がすべてのマッチを別個に報告することを要求するためである。

前の例は absorption をデータ側から壊した。DEFINE 内の FIRST が各コンテキストに述語を異なるように評価させた。absorption は出力側からも壊れる可能性があり、それを制御するのが AFTER MATCH SKIP 句である。

すべて A にマッチする5行に対するパターン PATTERN (A+) と DEFINE A AS TRUE を考えよ。既定の AFTER MATCH SKIP PAST LAST ROW の下で、マッチャは最も早い行から始まる最長マッチを見つけ、その先へ跳ぶ。そのマッチ内で開始したコンテキストはどれも冗長として静かに捨てられる — まさに absorption が扱うために設計された状況だ。出力は単一マッチ、行 0–4 で、ランタイムは生きているコンテキスト一つで済む。

skip モードを AFTER MATCH SKIP TO NEXT ROW に切り替えると契約が変わる:

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

今やすべての潜在的開始位置はマッチが重なる場合でも別個に報告されねばならない。同じ5行に対しランタイムは5つのマッチを出さねばならない。行 0–4、1–4、2–4、3–4、4–4。これらのいずれも「より早く始まるより長いもの」で置き換えられない。標準が利用者はそのすべてを欲するというからだ。

行SKIP PAST LAST ROWSKIP TO NEXT ROW
0マッチ開始; 行 0–4 が唯一のマッチ行 0 でマッチ開始
1(マッチ 0 の内部)行 1 でマッチ開始 — 生かしておく必要あり
2(マッチ 0 の内部)行 2 でマッチ開始 — 生かしておく必要あり
3(マッチ 0 の内部)行 3 でマッチ開始 — 生かしておく必要あり
4マッチ 0 確定(行 0–4)5つのマッチが確定: 0–4, 1–4, 2–4, 3–4, 4–4
異なる出力、異なる運命 AFTER MATCH SKIP TO NEXT ROW の下では、遅れて始まるすべてのコンテキストはそれ自体が出力行である。同じパターン要素にある2つのコンテキストはもはや冗長ではない — どちらも必要な出力であり、一方を捨てることは利用者が要求したマッチを静かに落とすことになる。

述語は変わっていないことに注意。A AS TRUE はどのコンテキストが問おうと全行で同じに評価されるので §2.5 の同じ運命条件は依然満たされる。変わるのは出力要求である。同一の未来を持つコンテキストでさえ、結果の別個の行に対応するから共存せねばならない。したがってプランナは AFTER MATCH SKIP TO NEXT ROW が有効である限り DEFINE 句に関わらず context absorption を無効化する。

§2.6 と §2.7 を並べて置くと、クエリの意味論が absorption を排除する2つの道が見える:

データ側 · §2.6
述語がコンテキストごとに異なって評価される。
DEFINE 内の FIRST またはオフセット付き LAST によって誘発。
出力側 · §2.7
出力がすべてのマッチ開始を別個の行として要求。
AFTER MATCH SKIP TO NEXT ROW によって誘発。

どちらか一つの条件でパターン全体の absorption を無効化するに足り、UNBOUNDED FOLLOWING で終わらないフレームも同様である。いずれも有効でないとき — 既定の AFTER MATCH SKIP PAST LAST ROW、無界のフレーム終端、PREV、NEXT、素の LAST のみ使う DEFINE 条件 — absorption は有効になるが、パターンの吸収可能領域にある状態に対してのみである。吸収可能領域とは、A+ や A* のような先頭の greedy 無界変数、(A B)+ のような無界 greedy 数量子を持つ固定長グループ、(A+ B)+ や (A+ B){2} のように本体がこれらのいずれかで始まる greedy グループ、またはそれらから構成される選択分岐である。reluctant グループはその部分木全体を不適格にする。それが成り立つ場合、§2.5 の A+ のように、ランタイムは単一コンテキストに縮約し線形を保つ。§2.3 の START UP+ DOWN+ には吸収可能領域がまったくない。

§3. 設計 — パーサから実行器まで

Row Pattern Recognition は、よく定義された中間形式を介して仕事を引き渡す三段階で実装される。パーサは SQL テキストをパターン木と DEFINE 述語のリストに変換する。プランナは木をパターン要素の平坦配列にコンパイルし、どれが context absorption に参加できるかを決める。実行器はその配列をパーティションに対して行ごとに三相ループで走らせる。各段階は独自のデータ形状を持ち、巧妙さの大部分は境界にある。キャッシュに収まる平坦 NFA、参照ごとにスロットを実体化せず単一のタプルスロットを再利用するナビゲーションモデル、そして O(n²) の処理量を O(n) に変える absorption 規則である。

SQL テキスト
  │
  │  パーサ段階
  ▼    フレーム検証
       パターン木の構築
       DEFINE の型チェック

パターン木 + DEFINE リスト
  │
  │  プランナ段階
  ▼    木の最適化
       平坦 NFA 配列へコンパイル
       absorbability の判定

平坦 NFA + absorption フラグ
  │
  │  実行器段階
  ▼    行ごとエンジン:
       Match → Absorb → Advance

マッチ結果:
  開始行、長さ、成功/失敗

以下の節はこのパイプラインを下る。§3.1 はパーサとパターン木の形、§3.2 は木を平坦 NFA に変えるコンパイル、§3.3 は DEFINE 述語が隣接行を見るのに使うナビゲーションモデル、§3.4 はマッチ境界処理 — マッチの開始と終了を定める SKIP、INITIAL、限定フレーム規則、§3.5 は三相の行ごとエンジン、§3.6 は状態空間を限定された状態に保つすべての 枝刈り メカニズム、§3.7 は実装が EXPLAIN 出力に露出するものを概観する。

3.1 パーサ — パターン木の構築

パーサはウィンドウ仕様内に PATTERN 句があることで pattern recognition を認識する。最初の仕事はフレーム検証である。RPR は通常のウィンドウクエリにはない制約を課すからだ。フレームモードは ROWS でなければならない(RANGE や GROUPS ではない)、開始境界は CURRENT ROW でなければならず、終了境界は UNBOUNDED FOLLOWING か正の offset FOLLOWING でなければならない(したがって既定のフレームも拒否される)。EXCLUDE NO OTHERS 以外の EXCLUDE オプションは禁止される。これらは標準準拠チェックであり最適化ではない — RPR におけるフレームの概念はマッチ範囲であり、標準はマッチした行以外で埋めることを想定していない。

フレームが検証を通過すると、パーサは PATTERN 句を4種類のノードからなる木に変換する — 変数参照、シーケンス(連結)、選択(alternation)、グループ(括弧で囲まれた部分パターン)。各ノードは数量子を3つの数 — 下界、上界(無限の可能性あり)、reluctant マッチング用フラグ — として持つ:

ソース木のエンコーディング
AVAR(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 述語はパーティションの列に対して型検査され、ブール式へ強制される。ここから実用的な2つのことが従う。第一に、パース解析は DEFINE のためにクエリのターゲットリストへ何も追加しない。代わりにプランナが、HAVING の場合と同様に DEFINE 述語が参照するすべての列を必要なものとして印付けし、外側のクエリがそれらを select しなくとも実行器段階まで伝播する — そうでなければランタイムは評価対象を持たない。第二に、PATTERN に現れるが DEFINE に現れない変数は暗黙に真である。すべての行にマッチする。

3.2 コンパイル — AST から平坦 NFA へ

プランナはパーサの木を実行器が走らせるデータ構造へ変換する。インデックスで番地付けされるパターン要素の平坦配列である。コンパイルは六段階のパイプラインで進む:

compile(astTree):
  1. AST の最適化
  2. サイズと深さの測定
  3. 要素配列の確保
  4. AST から埋める
       (next/jump ポインタの設定)
  5. 仕上げ — FIN センチネルの設定
  6. absorption 対象要素の印付け

平坦な形が選ばれる理由は単純である。実行器はパーティションごとにパターンを何度も走査する必要があり、連続でインデックス番地付けできる配列が最も安価に走査できるデータ構造だからだ。段階 1 と 6 が興味深い — 段階 1 は配列のサイズを決め、段階 6 は §2.5 の absorption 最適化がそもそも作動するかを決めるからである。

AST 最適化

最適化は二度報われる。一度は平坦配列の静的要素数で、もう一度はランタイムで処理される行ごとに。すべての変換はランタイムが列挙すべき状態空間を縮める。オプティマイザは9つの書き換え規則を単一のボトムアップパスで適用する(シーケンス内ではグループ併合がもう一度走る。先の併合が2つの同一グループを隣り合わせにしうるからだ):

SEQ 平坦化
SEQ(A, SEQ(B, C)) → SEQ(A, B, C)
連続変数の併合
A A → A{2}
A{2,3} A{1,2} → A{3,5}
連続グループの併合
(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}
単一子の展開
SEQ(A) → A
(A){1,1} → A
Reluctance の正規化
A{2}? → A{2}(min = max であるところでは reluctance が解除される)

数量子の乗算は、達成可能なカウントが一つの連続区間をなし、かつ優先マッチが動かない場合にのみ合成する。外側が固定((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* は一行を受け入れてしまうからだ)。自身の数量子が固定でないグループの子は、まず本体が固定長でなければならないので、((A | B B){1,2}){2} は外側が固定でもそのまま残る。その他の組み合わせは平坦化により受容カウント集合に隙間(spectrum gap)が生じうる — たとえば (A{2}){2,3} は {4, 6} のみを受け入れるが、単純に A{4,6} へ変換すると 5 も受け入れてしまう — か、優先マッチをずらす((A{2,3}){1,2} は3行を優先するが A{2,6} は4行を取る)ので、オプティマイザは構造をそのまま残す。条件付きの書き換えはこれだけではない。グループ併合と接尾の併合は固定行数を消費する本体を要求し、接頭の併合は min が 0 で max が有限かつ中身が nullable なグループを見送り、reluctant ノードは併合も乗算もされず((A+?)+ は残る)、新しい上下界がオーバーフローする書き換えは見送られる。

要素の形

平坦配列の各要素はパターンの単一位置を表す。論理的な種類は6つ。変数参照(行を消費する唯一の種類)、group begin と group end マーカ(括弧の部分パターンを開閉)、alternation マーカ(分岐リストの先頭)、各分岐を終える branch separator、パターン末尾の finish マーカ。

各要素はさらに深さ(グループ入れ子レベル)、数量子(min/max 反復回数、無限の可能性あり)、2つの遷移ポインタを持つ — next(「この要素を消費した後どこへ進むか」)と jump(「どこへ跳ぶか」。alternation マーカと branch separator で分岐を連ね、group begin で自身の group end を指し — 数量子が 0 を許すグループはその end の next を通じて回避される — 、group end で本体へループバックするのに使われる)。

PATTERN ((A B)+) をコンパイルした配列はこうなる:

PATTERN ((A B)+) のコンパイル結果:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 3
    (グループを開く; 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
    (グループを閉じる; jump は本体へ戻る)

[4] FIN    パターン完了

パターンは next を介して左→右に読まれ、jump が非線形のエッジを扱う。idx 3 の END の jump は idx 1 を指し戻す。これが無界外側数量子のループの仕方である。idx 0 の BEGIN の jump は idx 3 の自身の END を指し、グループがオプションなら回避はその END の next を通って、END に到達することなく idx 4 へ抜ける。ランタイムは実行時にグラフを構築する必要がない — 配列を歩きながらこの2つのポインタを辿るだけだ。

要素ごとの属性

形の他に、各要素はその位置でのランタイム動作を指示する5つの論理属性を持つ:

Reluctant
数量子展開の順序を反転する。greedy 数量子は「退出」より先に「もう一度ループ」を試み、reluctant 数量子は「退出」を先に試みる。A+? では変数が、((…)+?) ではグループの BEGIN と END が持つ。
Empty-loopable
本体が nullable なグループの END に設定((A? B?)+、(A | B*)+。(A?)* は先に A* に乗算され group end が残らない)。min 未満では通常のループバックと並んで fast-forward 退出を追加するようランタイムに指示し、cycle guard が空反復を生み得るグループの正当なマッチを殺さないようにする。
Empty-preferred
本体が空マッチを優先するグループの END に設定((A?? B??){2} のように)。min 未満で、グループ自身の greed が何も言わないところで、fast-forward 退出をループバックより先に並べる。
In-absorbable-region
absorption 適格領域内にあるすべての要素に印を付ける — ランタイムが現在状態が依然安全領域にあるかを追跡するのに使う。
Absorption-comparison-point
absorption 比較を実行すべき特定の要素に印を付ける。単純な A+ では変数に、(A B)+ のような無界グループでは group end のみに位置する。

「in-region」と「comparison-point」を分けるのは重要である。absorption は反復が閉じる点でのみ意味を持つからだ。(A B)+ の本体内ではランタイムは反復の途中で、そのラウンドの最終値にカウントがまだ達していない。ここで比較しても比較不能な値を比べることになる。状態が group end に達してから決めねばならない。したがって最初の属性は「あなたはまだ吸収可能な領域にいる」と言い、2つ目は「比較点に達した — 今すぐ確認せよ」と言う。

吸収可能性の解析

コンパイルの段階 6 が §2.5 の「同じ運命」規則にコンパイル時の証人を与える。決定は階層的である:

isAbsorbable(query):
  if SKIP mode != SKIP PAST LAST ROW
      → return false
  if frame end != UNBOUNDED FOLLOWING
      → return false
  if any DEFINE depends on match_start
      → return false
  平坦配列を要素 0 から巡回し
  構造的事例を満たす
  要素に印付け

最初の3つのチェックはクエリレベルである。それぞれ §2.7 (出力側: SKIP モード)、限定フレーム(境界が単調性を破る)、§2.6 (データ側: DEFINE 内の FIRST またはオフセット付き LAST) の条件と正確に対応する。いずれかが失敗すれば解析はフラグを立てず、クエリ全体で absorption が無効化される。すべて通過すると巡回は4つの構造形を認める:

Case 1 — 単純な無界変数
A+, A*, A{2,∞}
各反復は厳密に一行。早いコンテキストのカウントは共有するすべての位置で遅いものの ≥ である。
Case 2 — 固定長グループ、外側が無界
(A B)+, (A B{2})+, ((A (B C){2}){2})+
すべての子が min == max なので本体は展開された {1,1} 形と意味的に等価 — (A B{2})+ は (A B B)+ のように振る舞う。各反復は固定行数を消費し、カウント優越は依然成立。
Case 3 — 本体が無界変数で始まるグループ
(A+ B)+, (A+ B){2}
先頭の無界変数自体が吸収可能(Case 1)で、早いコンテキストを保護する。状態が A を越える瞬間 absorption は止まる — 本体の残りは単調性の保証がないので、A は両方のフラグを、囲む BEGIN は in-region フラグを受け、B と END は何も受けない。
Case 4 — 選択(alternation)
A+ | B+, A+ | C D
separator の連鎖を通じて到達する各分岐は、上記の事例によってそれぞれ独立に判定される。いずれかの分岐が適格なら alternation マーカは in-region フラグを受ける。

上記4つの形態に該当しない構造的事例も同様に教訓的である。A B+ は現在の規則では吸収できない。先頭の A が無界部分の開始前に行を消費するので、一行ずれて開始するコンテキストは無界本体内の異なる位置にあるからだ。A+? のような reluctant 数量子は構成上除外される。absorption 規則は greedy 意味論(長いマッチが短いマッチを包含)を仮定し、reluctant マッチングはその方向を反転するからである。

結果はパターン単位ではなく要素単位の決定である。単一のクエリ計画で (A+ B+ C) や (A+ B+)+ の先頭 A+ には absorption を有効にし — 後者は Case 3 を先頭要素に適用したものに相当 — その後すべてには無効にできる。ランタイムは absorption パスを考えるたびに現在状態の要素の comparison-point 属性を参照するだけだ。状態が非吸収領域に移ると、その状態の absorption は永続的にオフになる — まさに §2.5 と §2.6 がアルゴリズムレベルで真であるべきものだ。

3.3 ナビゲーション — 1 スロットのタプル交換

DEFINE 式は行に対して評価される通常の SQL 式だが、PREV、NEXT、FIRST、LAST — 異なる行を指す参照 — を含み得る。行自体は既にウィンドウのタプルストアにバッファされている。実行器がなお管理せねばならないのは SQL 式機構が読むタプルスロットである。式内の列参照は計画時にスロットに束縛されるからだ。実装はあらゆるナビゲーション呼び出しで単一の navigation slot を再利用する。内部式の評価前にスロットが入れ替えられ、後で復元されるので、SQL 式機構の他の部分は違いを知らない。

実行器が見るモデルは小さい。DEFINE 式が評価される行を保持する current row slot と、ランタイムが一時的に別行へ向けられる navigation slot がある。あらゆるナビゲーション呼び出しの周辺で、ランタイムは navigation slot を設定し、あたかも current row を読むように内部式を評価し、元の行を復元する。擬似コード:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos が有効範囲外:
      return NULL

  current_row_slot を保存
  if targetPos != currentPos:
      targetPos の行を nav_slot
        へ取得
      外側スロットを nav_slot に向ける
  result = eval_inner_expression()
  current_row_slot を復元
  参照渡しの result を nav_slot から
    コピーして取り出す
  return result

トリックは、保存・復元するスロットが正確に一つだけという点である。内部式 — 算術、関数呼び出し、他の列参照を含め何であれ — は current row に対してと同じ評価経路で交換されたスロットに対して走る。代替評価器なし、参照ごとのスロットなし。対象が現在行のときは取得と交換はまったく省略される。取得は対象行を navigation slot にコピーし(スロットが既にそれを保持していない限り)、復元段階は参照渡しの結果を per-tuple メモリへコピーして、次の取得がそれを解放できないようにする。

複合ナビゲーションはパース時に平坦化され、交換は依然一回で済む。PREV(FIRST(price)) は2段ナビゲーション — 「最初のマッチ行へ移動し、その後一行戻る」 — として認識され、複合種別を持つ単一ナビゲーション呼び出しとして格納される。ランタイムは目標位置を2段で計算するが、最終行を取るためのスロット交換は一回のみ:

compute_target_position(call):

  # 現在行相対
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # マッチ相対
  FIRST(n):
      return matchStart + n
  LAST(n):
      return currentPos − n

  # 複合: マッチ相対の後さらに移動
  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 内側はマッチ範囲、
   外側ステップはパーティション範囲)

同じ DEFINE 内の複数のナビゲーション呼び出しが同じ行を対象にするとき位置キャッシュがタプルストアフェッチを短絡する — price > PREV(price) AND volume > PREV(volume) のような式で両呼び出しが前の行に解決する場合に多い。キャッシュは「最後にフェッチした位置」だけを保持し、交換自体は単一操作のままだ。

ナビゲーション呼び出しの分類はプランナによる absorption 決定への寄与である。プランナはすべての DEFINE 式を歩き、すべてのコンテキストが同じ行で同じブールを計算するか、各コンテキストが独自の計算をするかに基づいて各変数を2つのバケットのいずれかに振り分ける。バケットはランタイムで2つを決める。変数がどれくらい頻繁に評価されるか(共有で一度、または影響を受けるコンテキストごとに一度 — §3.5 Phase 1)、そして context absorption がそもそも可能か(§2.5 vs §2.6)である。マッチ開始依存の変数が一つでもあれば、パターン全体の absorption が無効化される。

共有評価 · 吸収安全 すべてのコンテキストがすべての行で同じブールを見る — 同じ運命(§2.5)。
  • ナビゲーションなし
  • PREV / NEXT のみ
  • オフセットなしの LAST
  • 内側 LAST(オフセットなし)の複合
コンテキスト毎評価 · 吸収不安全 異なるマッチ開始のコンテキストが異なる答えを計算する — 異なる運命(§2.6)。
  • オフセット付きの LAST
  • FIRST(任意形)
  • 内側 FIRST の複合
  • 内側 LAST(オフセット付き)の複合

分類は計画時に行われ各 DEFINE 変数に併せて格納されるので、ランタイムは分類判定に時間を費やさない — 行を処理する際に各変数に予め付与された分類結果を参照するだけだ。

保持範囲

ナビゲーションはウィンドウ関数機構が既にストリームし通り過ぎた行に手を伸ばす。それらを利用可能に保つため、実行器は最近の行のスライディングウィンドウを保持するタプルストアの上に座る。問題はそのウィンドウがどれだけ広いべきかである。実行器は2つの相補的なオフセットからそれを求め、すべてのオフセットをスキャンごとに一度解決する(定数のものは executor init 時にも解決し、素の EXPLAIN が表示できるようにする):

Lookback 範囲
どの DEFINE 呼び出しが現在行からどれだけ後ろへ届きうるか。
寄与要因: PREV、LAST(既定の 0 を含む任意のオフセット)、PREV(LAST(...))、NEXT(LAST(...))
Lookahead-from-start 範囲
最も古い生存コンテキストのマッチ開始からの最小の前方到達距離(負ならば後方) — いずれかの DEFINE 呼び出しが必要としうる最も早い行。
寄与要因: FIRST、PREV(FIRST(...))、NEXT(FIRST(...))

ランタイムでタプルストアのトリムマークは2つの位置のうち早い方 — 現在行から lookback 範囲を引いた位置と、最古の生存コンテキストのマッチ開始に lookahead 範囲を加えた位置 — に設定される。そのマークより前は、どの生存コンテキストのどのナビゲーション呼び出しからも到達できず、タプルストアは自由に捨てられる。EXPLAIN が報告する(§3.7)Nav Mark 行 — Lookback と Lookahead — はこの2範囲そのものであり、測定ピークではない。それぞれ何らかのナビゲーションがそれに寄与するときにのみ出力され、ANALYZE なしでも表示される。値が実行時にしか分からないオフセット(たとえば generic plan のパラメータ)は素の EXPLAIN では runtime と、EXPLAIN ANALYZE では解決された値として出力され、retain all(Lookback)または infinite(Lookahead)はオーバーフローするオフセットを示す。

3.4 マッチ境界 — SKIP、INITIAL、限定フレーム

マッチ結果は2つの値として記録される。マッチ開始の行とその長さである。負の開始はその位置がまだ評価されていないことを意味する。開始が設定されれば、実行器に対する後続のクエリ — 「この行はマッチ内か?」 — はその組を見れば O(1) で答えられる。長さが結果を表す。マッチしなかった行は -1、空マッチは 0、実際のマッチは行数である。長さ 0 はエラーではなく実在の結果である。行を消費せずマッチしたパターンを表し、実行器はマッチしなかった行とも「この位置でまだマッチを試みていない」とも区別せねばならない。

AFTER MATCH SKIP 句は次のマッチ試行がどこから始まるかを決める。AFTER MATCH SKIP PAST LAST ROW はマッチ末尾の次の行へ移り、ほとんどのクエリが望む非重複出力を生み、absorption 最適化を有効にする。

AFTER MATCH SKIP TO NEXT ROW はマッチ開始の次の行のみへ移り、マッチの重なりを許す。したがってプランナはこのモードが有効なときそのウィンドウのパターンに対して absorption を無効化する。

標準が定義するもう2つの skip 対象 — AFTER MATCH SKIP TO FIRST var と AFTER MATCH SKIP TO LAST var — はこのパッチが保持しないマッチ単位履歴に依存する。文法に全く存在しないので、いずれかが供給されるとパーサは一般的な構文エラーを発生させる。

SEEK(仕様の INITIAL の代替)も同様である。SEEK の下では行 R で始まるマッチ試行は R 自身だけでなく R からフレーム末までの任意の行で成功し得る。パッチは INITIAL のみを実装する。すべての潜在的マッチは特定の行に固定される。SEEK が要求されるとパーサはエラーを発生する。限定フレームは独自の扱いを受ける — 利用者が UNBOUNDED FOLLOWING ではなく ROWS BETWEEN CURRENT ROW AND N FOLLOWING を書くと、実行器はマッチが境界に達したコンテキストを強制ミスマッチで短絡し、absorption が依拠する単調性仮定を境界が破るので absorption は無効化される。

3.5 三相の行ごとエンジン

実行器の行ごとドライバは、与えられた行がマッチしたフレームに属するかを知る必要があるたび、周囲のウィンドウ関数機構によって呼び出される。ドライバは現在の開始位置に対するコンテキストを見つけるか作成し、NFA を行ごとに前進させる — 行ごとに変数ごとのマッチ配列を「未評価」にリセットしながら — そのコンテキストに生存状態がなくなるかパーティションが終わるまで。DEFINE 述語は遅延評価される。変数はある状態が初めてそれを消費するときに評価されるので、この行でどの生存状態も検査しない変数は決して評価されない。前進ステップ自体は同じ外側ループに包まれた固定順序の三相 — Match、Absorb、Advance — である:

processRow(currentPos):

  # 第1相 — MATCH (収束)
  for each context:
      if コンテキストがフレーム終端に到達:
          強制ミスマッチ (早期確定)
          continue
      if matchStartRow が共有評価
         位置と異なる:
          マッチ開始依存 DEFINE
          変数を未評価にリセット (§3.3)
      match(context, varMatched)

  # 第2相 — ABSORB
  if パターンが absorbable:
      各コンテキストのフラグ更新
      absorb_contexts()

  # 第3相 — ADVANCE (発散)
  for each context:
      advance(context, currentPos)
      if マッチを記録しかつ
         SKIP PAST LAST ROW:
          マッチ内で始まる後続
          コンテキストを破棄

順序は様式上の選択ではない。Match が最初に走らねばならないのは absorption がマッチ後のカウントを比較するからだ。Match の前に Absorb を走らせれば消えかけている状態を比較してしまう。Advance が最後に走らねばならないのは新しい状態を作る唯一の相だからだ — 生き残ったすべての状態をイプシロン遷移で展開し、各々が次の行を待つ変数に到達するまで進める。Advance の後に Absorb を走らせれば発散した後続を比較し、状態が最も綺麗に比較できる点を逃すことになる。

Phase 1 — Match

Match は「収束」相である。状態はカウントを増して生き残るか消滅する。興味深い点は、吸収可能領域にある変数に対して Match が少量の前進も行い、Absorb が綺麗に比較できるようにすることだ。cover 条件は吸収可能な比較点 — 無界グループの END — でのみ発火するので、反復中間変数((A B)+ 内の B など)に今マッチしたばかりの状態は 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]:
          drop state   # 死んだ分岐
          continue

      state.counts[elem.depth] += 1

      # 次相が反復途中ではなく比較点
      # 要素で比較できるよう
      # インライン前進を行う。
      if elem が in-region だが
         比較点ではなく、
         max カウントに達し、
         elem.next が group end:

          END チェーンを巡回:
            外側グループのカウント増加
            state.elemIdx を END へ進める
            in-region かつ must-exit で
              next が END の間続行
          (比較点またはまだループ可能な
           要素で停止)

end-chain 走査は入れ子の固定長グループを吸収可能にするものだ。((A B){2})+ で B({1,1})が max に達すると内側グループのカウントが増分される。そのカウントも max に達して内側 {2} を閉じれば、外側グループのカウントも増分され、こうして状態が最も外側の吸収点 — 無界外側グループ(+)の END — に達するまで続く。この仕事を Match で行うと、Absorb は反復後カウントを既に集約したコンテキストに対して比較できる。

Phase 2 — Absorb

absorb パスはコンテキストを新しい方(末尾)から古い方(先頭)へ歩く。完全に吸収可能な進行中コンテキストごとに、それを覆う(cover)古い進行中コンテキストを後ろ向きに走査し、見つかれば新しい方を解放する。コンテキストは作成順に保持され各行は高々一つのコンテキストを作るので、「新しい」と「古い」は実際に「より遅く始まった」と「より早く始まった」を意味する。

absorb_contexts():
  for ctx from tail backward:
      if ctx が完了済みまたは
         non-absorbable 状態が一つでもある
         または記録されたマッチを持つ:
          skip
      for older from ctx.prev backward:
          if older が完了済みまたは
             absorbable 状態がない:
              skip
          if covered(older, ctx):
              free(ctx)
              absorption 長を記録
              break

covered(older, newer):
  for each state in newer:
      elem = pattern[state.elemIdx]
      if elem が比較点でない:
          return false
      if older に次の条件の状態がない:
            同じ elemIdx
            かつ isAbsorbable
            かつ older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

ここから2つの微決定が生じる。第一に、cover チェックは新しいコンテキストのいずれかの状態が比較点以外にいれば直ちに拒否する — 非判定点での比較は意味のある比較にならない。

第二に、各コンテキストの非対称フラグ対だ。has-absorbable-state は「このコンテキストはより新しいものを吸収できるか?」に答えるフラグで、単調的だ(状態が消えると true→false にしか進めない)。一方 all-states-absorbable は「このコンテキストは吸収され得るか?」に答えるフラグで、動的である(吸収不能状態が除かれると true に戻る)。ただしコンテキストがマッチを記録すると false に固定される — 吸収すれば、吸収する側のどのコンテキストも再現できないマッチを解放してしまうからだ。両フラグは cover 走査が始まる前に定数時間で確認されるので、absorption は実際に吸収される見込みのあるコンテキストにのみフルコストを支払う。

Phase 3 — Advance

Advance は「発散」相だ。各生存状態はイプシロン遷移を通じて展開され、すべての分岐が次の行を待つ変数または FIN センチネルに到達するまで進む。展開は深さ優先で、兄弟分岐が歩かれる順序が標準の選好規則を機能させるものだ — 語彙的に最初の分岐が常に最初に追加され、状態挿入時の重複除去が等価な後の追加を静かに捨てる。

advance(context, currentPos):
  現在の状態をすべて取り出し
  ctx.states を一から再構築
  for each state in lexical order:
      訪問ビットマップを初期化
      advance_state(state)   # DFS

      # 選好優先: DFS が FIN に達したら
      # 残りの状態は選好度が低いため
      # 破棄可能。
      if FIN 到達かつ残り状態あり:
          残りを free
          break

advance_state(state):
  state.elemIdx を辿り、
  以下を再帰的に処理:
    ALT 分岐 (順序通り、FIN が
              記録されたら停止),
    BEGIN (グループ進入; min = 0 なら
           スキップ経路を追加),
    END (ループバック / 退出 / fast-forward —
         下記参照),
    FIN (matchEndRow を記録,
         matchedState を保存し、この候補
         範囲内の後続コンテキストが破棄
         されるようコンテキストに印付け
         — 下記参照),
  変数に出会うたび停止:
      state を ctx.states に追加
      (elemIdx + counts で重複除去)

FIN に達した状態を記録することは単に候補マッチをブックマークする以上の意味を持つ。AFTER MATCH SKIP PAST LAST ROW の下では次の報告可能なマッチは現在のマッチから厳密に先で始まらねばならない — Advance が候補を記録したコンテキストの処理を終えた時点で、開始行が候補範囲内に落ちるすべての後続コンテキストは同じ行で破棄される。FIN に達したコンテキストが greedy fallback でより長いマッチを探し続け得るとしてもである。

この枝刈りが安全なのは、その探索がどう終わろうとも(より長いマッチが候補を置き換えるか、候補が立つか)破棄されたすべてのコンテキストは次の報告可能なマッチが越えねばならない範囲で始まったので、自身の出力を決して生み得ないからだ。

これがコンテキスト間の FIN-time 枝刈りステップである。コンテキスト内でも FIN は語彙的に劣る作業を断ち切る。Advance は残りのキュー内状態を落とし(本節前半で述べた)、一つの DFS 内では選好度の低いすべての経路 — 後の ALT 分岐、BEGIN のスキップ経路と進入経路の他方、reluctant 変数の進入経路、END のループ経路と退出経路の他方 — がマッチが記録された時点で止まるので、一回の advance が記録するマッチは高々一つである。

最も厄介な要素ごとロジックは END ハンドラに住む。グループの反復カウントが下界未満ならランタイムはループバックせねばならない。上界以上なら退出せねばならない。その間ではどちらも有効で、数量子の greediness がどちらを先に試すかを決める:

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

  if count < elem.min:
      本体へループバック
      if elem が empty-loopable:
          # nullable 本体、§3.2 参照
          グループから退出する
          fast-forward 状態も複製
          (count 充足扱い)
          (本体が空を優先するなら
           fast-forward が先。最初の
           経路が FIN に達したら
           二番目の経路は破棄)

  elif count >= elem.max:
      この深さの counts をリセット
      next で退出
      (END→END: 外側 END の
       count を増加)

  else:
      # min <= count < max: 分岐
      退出状態を生成
      (この深さの counts をリセット)
      if greedy:
          ループ先
          if ループで FIN 到達:
              退出を破棄
              # より長い方を選好
          else 退出を二番目に
      else (reluctant):
          退出先
          if 退出後 FIN 到達:
              ループ破棄
              # より短い方を選好
          else ループ後続

コンテキストに追加されるすべての状態は、自身の位置とカウントを既存状態リストと比較する重複除去チェックを通る。Advance が分岐を DFS 順で処理するので、いずれかの選択の最初の分岐から来た状態が先に着き、同じ位置とカウントを生む後の分岐は挿入時に拒否される。これはまさに §2.4 の語彙順序規則が求めるもので、別パスなしにランタイムの底で実装されている。

空ループ可能グループ

ランタイムが扱わねばならない微妙な事例が nullable グループである — 本体のすべての子が選択的なため、本体が一行も消費せずに反復を完了し得るグループ。(A? B?)+ や (A | B*)+ のようなパターンがこれに該当する。((A?)* のような単一の任意子はコンパイル時に A* へ書き換えられ、グループは残らない。) 原則それで構わないが、NFA のイプシロン展開では実際の危険となる。本体が空マッチを生めば END が本体へ戻り(その jump はグループの最初の子)、本体が再び空マッチを生み、再び END に達し… これを止める仕掛けがなければ Advance の DFS は終わらない。

この guard はコンパイル時に決まり実行時に発動する。プランナは本体が nullable なグループに出会うたび、そのグループの END 要素に empty-loopable タグを付ける。ランタイムは各状態の DFS 展開前にクリアされる訪問ビットマップを保持し、そこにはタグ付きの END だけが印付けされる — 他のループバックはすべて行を消費しているので、それ以外は循環しえない。印付きの END に達したことは本体が空反復を導出したばかりであることを意味し、状態は破棄されない。下界以上ならそこでグループを離れ(空反復は数量子を止める)、下界未満なら状態は通常のループバックへ進むので、空の到達のたびにカウントは min に達するまで増える。行ストリームのどこでもどちらの変数もマッチしない (A? B?){2,3} を見よ:

iter 1: A? B? が 0 行マッチ
        → END, count = 1 (min 未満)
        END は既に印付き (グループ
        進入時) だが min 未満:
        → A? へ loop back
iter 2: A? B? が 0 行マッチ
        → END, count = 2 (min 充足)
        END は既に印付き、min 到達:
        → グループを離れる
長さ 0 マッチで退出

下界未満では、empty-loop タグは END ハンドラに通常のループバック経路と並行して追加の fast-forward 状態もクローンするよう指示する:

advance_end (count が min 未満):

  ループバック経路:
    本体へ loop back
    (次の反復で実際に空でない
     マッチが可能となる道を残す)

  if elem が empty-loopable:
    fast-forward 経路:
      この深さの count をリセット
      next でグループ退出、
      残りの必要な反復を
      空マッチとして扱う

2つの経路は互いに補い合う。ループバックは本体が 後で 実際のマッチを生む場合に対応する — 例えば (A? B?){2,3} に続いて A が後の行でのみマッチするデータでは、ループバックのおかげで第二・第三の反復が空でないマッチを見つけられる。fast-forward は直ちにグループから退出し、「残りの必要な反復はすべて空」と宣言して長さ 0 の本体でマッチを成立させる。順序を決めるのはグループ自身の greed ではなく本体である。fast-forward が先に来るのは本体が空マッチを優先するとき((A?? B??) のような reluctant 本体)に限られ、最初の経路が FIN に達すれば二番目は破棄されるので、選好度の低い経路が優先マッチを置き換えることはできない。挿入時の重複除去チェックがどちらの経路も自分の分以上の状態を生まないよう防ぐ。

cycle guard 以外に、コンテキストの最開始での 0 行結果を曖昧でなくする起動時のトリックがもう一つある。すべての潜在的開始行でのコンテキスト作成段階は、行を消費する前にイプシロン遷移を通じて initial advance を実行する。実際の開始の一行前の位置を使って。行を消費せずイプシロン遷移だけで FIN センチネルに達するすべての経路は、開始位置より小さい終了位置を生む。その負スパン座標が、FIN に実際に達したかと組み合わさって、別フラグなしに空マッチ(長さ 0 マッチを受理)と未マッチ開始の違いを符号化する。

3.6 状態空間が限定された状態に保たれる仕組み

ランタイムを限定された状態に保つことは単一の最適化の結果ではない。行ごとサイクルの異なる地点で状態空間増大の異なる原因を捉える、階層化された 枝刈り 規則群の累積効果である。いくつかはコンパイル時に決まり実行時に参照されるだけ、他は動的に発火する。いくつかは個々の状態を殺し、他はコンテキスト全体を殺す。上の節は各々を文脈の中で紹介した。下の表はそれらを一頁にまとめる。

述語失敗 Match
現在行で DEFINE が偽と評価された変数状態 — 死んだ分岐。
インライン end-chain advance Match
max カウントに達したがそうしなければ状態を反復の途中に置いてしまう変数。absorption が正しい点で比較できるよう固定長 group end を通して進められる。
Context absorption Absorb
すべての状態が比較点にあり、古いコンテキストの、同じ要素にありカウントが同じかそれ以上の吸収可能状態に覆われる新しいコンテキスト — 概念規則は §2.5、コンパイル時適格性は §3.2、ペアごとチェックは §3.5 を見よ。
状態重複除去 Advance
異なる DFS 分岐を通じて到達し同じ位置・同じカウントで終わる状態 — 最初(語彙的に最も早い)だけが生き残り、後の等価物は静かに捨てられる。これが選好が強制される仕方でもある(§2.4)。
FIN 早期終了(コンテキスト内) Advance
一つの分岐が FIN に達したとき DFS キューに依然保留中の状態 — 語彙順序により残るすべての状態はあまり選好されず、直ちに破棄できる。
候補マッチ 枝刈り(コンテキスト間) Advance
開始行が候補マッチ範囲内に落ちる他のコンテキスト — FIN に達したコンテキストはより長いマッチを探し続け得る(greedy fallback)が、AFTER MATCH SKIP PAST LAST ROW の下では候補範囲内のいずれのコンテキストもその探索の結果に関わらず報告可能な出力を生み得ず、Advance が候補を記録したコンテキストの処理を終えた時点で破棄される。
Cycle guard Advance
同じ DFS 内で既に印付きの nullable グループの END(BEGIN を通じた進入時、または先の到達時に印付け)に達するイプシロン展開 — そうでなければ永遠にループする。状態は下界以上ならそこでグループを離れ、下界未満ならループを続ける。
Empty-loop fast-forward Advance
nullable グループの下界未満で、残りの必要反復を空と宣言してグループを退出する追加経路。ループバックとの順序は本体の選好による。
限定フレームカットオフ Match
マッチが利用者指定のフレーム上界に達したコンテキスト — それを越えて延長できないよう強制ミスマッチ(§3.4)。

上の項目をフェーズごとに読めばコンテキストの生涯がたどれる。枝刈りは3つの主要相(Match、Absorb、Advance)を通じてすべての行で発火する。代わりに説明で読むと、規則は何を狙うかでグループ化される。死んだ分岐、冗長なコンテキスト、等価な状態、無限ループ、利用者が課した境界を越える過剰延長。

どの単一規則も単独では不十分だろう。empty-loop fast-forward だけでは無限イプシロンループを止められない。absorption だけでは DEFINE がマッチ開始を参照する場合に過剰集約する。重複除去だけでは冗長な状態のみを除き冗長なコンテキストを除けない。ランタイムが重要な事例 — 100,000 行に対する PATTERN (A+ B+ C+ D)、ポスターのパネル ③ ベンチマーク — で線形を保つのは、すべての層が上の層が見落とすものを捕らえるからにほかならない。ソースは層が捕らえない事例も記録している。重複除去は min を超えるカウントだけが異なる状態を別々に保つので、C が決して真にならない (A{2,} B)+ C はピーク時に Θ(n²) 個の状態を抱え、Θ(n³) 個を生成する(320 行で 37 秒)。また全要素が nullable な選択の連なりは経路ごとに列挙されるので、(A?|B?){30} は 30 分以上かかる。

3.7 EXPLAIN 出力

RPR を持つクエリへの EXPLAIN ANALYZE は、通常のウィンドウ関数には存在しない NFA レベルの統計を露出する。テキスト形式では、それらは 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 ...) なしで出力)

テキスト以外の形式ではすべてのカウントがそれぞれ独立したプロパティとして発行される。Peak と total はランタイムの直接計測である。同時に生きていた状態が何個か、クエリ寿命にわたって何個作られたか、重複除去で何個が併合されたか。pruned は一行だけで失敗したコンテキストを数える。マッチ長ヒストグラムは4つの結果 — 成功マッチ、二行以上進んだ後に失敗したマッチ試行(mismatched)、吸収されたコンテキスト、記録されたマッチ内で始まったため AFTER MATCH SKIP PAST LAST ROW によって解放されたコンテキスト(skipped) — を分離し、min/max/avg で報告して性能の病理を一目で可視化する。健全な実行ではほとんどのコンテキストはマッチか吸収のいずれかとして現れ、ミスマッチの長さは小さい。

2つの Nav Mark カウンタは §3.3 が DEFINE から導出するタプルストアの保持範囲を報告する。Lookback は PREV、任意のオフセット(既定の 0 を含む)の LAST、内側 LAST を持つ複合形にわたる、現在行からの最も深い後方到達。Lookahead は最も古い生存コンテキストのマッチ開始から測定された最小の前方到達(マッチ開始より前を見るときは負)で、FIRST と内側 FIRST を持つ複合形が寄与する。

各カウンタはオフセットが定数なら固定整数、スキャンごとにしか分からない非定数式なら「runtime」と出力され、オフセットがオーバーフローするときは — Lookback に限り — 「retain all」と出力される。オーバーフローする Lookahead は「infinite」と出力される。各行は DEFINE 内の何らかのナビゲーションがそれに寄与するときにのみ発行され、どちらも素の EXPLAIN でも表示される。定数オフセットは executor init 時に確定し、値が実行時にしか分からないオフセット(たとえば generic plan のパラメータ)はそこでは「runtime」と、EXPLAIN ANALYZE では解決された整数として出力される。

これらのカウンタによって、バックエンドに gdb を接続せずに RPR の性能をデバッグできる。

カウンタを超えて、EXPLAIN はコンパイルされた要素配列から組み立てた Pattern: 行を出力するので、コンパイル時の書き換え後のパターンを示し(PATTERN (A A) は EXPLAIN では a{2} と表示される)、absorption マーカ #(比較点)と ~(吸収可能領域)を伴う。DEFINE と AFTER MATCH SKIP オプションは表示されない。句を書かれたとおりに — reluctant 数量子、グループ反復、skip オプションも含めて — 再現するのは pg_get_viewdef() の役目であり、この round-trip を安定にするためにかなりの労を取る。pg_dump と pg_upgrade が意味的ずれなく RPR オブジェクトを保存できるためだ — rpr_explain 配下の回帰スイートが事例ごとに検証する(§4 参照)。

§4. テスト — カバレッジマップ

パッチは §3 で述べられたすべての層を共同で検査する5つの回帰スイートとともに出荷される — 約 22,000 行の SQL であり、各スイートは異なる関心事に集中する。分離は意図的だ。パーサ関心、ランタイム正当性、プランナ相互作用、出力フォーマットを別ファイルに保つと失敗を局所化しやすく、ある層の無関係な変更が別の層のテストを偶然無効化するのを防ぐ。5つのスイートは:

rpr
WINDOW 句との統合 — 合成株価データ上の現実的なウィンドウシナリオ(V 字、W 字、連続上昇、反転)に加え、ナビゲーションの意味論と DEFINE 制約のエラー。
rpr_base
パーサ層 — キーワード受理、構文形、数量子、ナビゲーション解析、エラーメッセージ、pg_dump/pg_upgrade の round-trip 安定性。加えてプランナ層 — パターン最適化、absorption フラグ、最適化のフォールバック、プランナ統合。
rpr_nfa
NFA ランタイム — 三相ループ、すべての吸収可能形での吸収、コンテキスト寿命のエッジケース。
rpr_explain
出力フォーマット — NFA 統計、パターンの deparse、識別子の引用、再ロード間のフォーマット安定性。
rpr_integration
プランナ相互作用 — 無関係なウィンドウ最適化が RPR 意味論を破壊するのを防ぐガード。

4.1 rpr — end-to-endシナリオ

シナリオスイートはテストセットの公的な顔である。約 1,600 行の合成株価データセットを使い、現実的なクエリを実行する — V 字回復、W 字(ダブルボトム)、連続上昇と下落、反転パターン、複数シンボルパーティション。入出力が利用者が実際に書きうるクエリのように読める唯一のテストはこれらのシナリオである。ファイルの残りは、他のスイートと同様に切り詰められている — PREV/NEXT の入れ子と非定数オフセットのエラー、DEFINE の参照規則、ナビゲーションオフセットの意味論。

これらのクエリはすべての層(パーサ、プランナ、実行器、EXPLAIN)を組み合わせるので、rpr の単一失敗はバグがどこに住むかをほとんど教えてくれない。続く四スイートが二分(bisection)である。rpr の失敗と rpr_base の通過はパーサを除外する。rpr_nfa の通過はシナリオ固有のデータ形に絞る。rpr_integration の通過はプランナ干渉を除外する。あらゆる deparse のずれは rpr_explain に現れる。

4.2 rpr_base — パーサ表面

base スイートは最大で、その理由がある。§1.2 のすべての合法な構文片が実際に解析され、§1.3 のすべての非合法な片が有用なエラーで拒否され、すべての受理形が直列化 round trip を生き延びることを証明する責任があるからだ。大部分は長い現実的クエリではなく小さく焦点を絞ったスニペット(構文機能ごとに一つ)として整形される。目標がシナリオ現実性ではなくカバレッジだからだ。第二の部分であるプランナ層は、パターン最適化、absorption フラグの表示と解析、最適化のフォールバック、プランナ統合(サブクエリ、結合、集合演算、ソートとグルーピング)を扱う。

直列化テストには特別な配慮が要る。RPR オブジェクト(ビュー、マテリアライズドビュー、pg_dump 出力)はカタログ表現を round-trip しても意味がずれてはならない — 数量子の reluctant フラグや複合ナビゲーション式の正確な形といった細部まですべて保存される必要がある。これを検証するため、直列化専用オブジェクトの小集合(rpr_serial_v* ビューとそのバッキングテーブル)は意図的に実行終了時まで残される。周囲の回帰インフラがそれを拾い、pg_dump と pg_upgrade を検証できるようにするためだ。残りのテスト用一時オブジェクトは普段通り片付けられる。deparse と再解析で reluctant フラグが失われるといった欠陥は、round-trip を end-to-end で動かして初めて表面化する。

4.3 rpr_nfa — ランタイムエンジン

これは §3.5 と §3.6 で述べたすべてのメカニズムを動かすスイートである。テストは一貫したパターンに従う。各行でどの DEFINE 変数がマッチするかを宣言する変数名の配列を持つインライン VALUES 行と、特定のランタイム動作を探るパターンの組である。配列イディオムはランタイムテストを DEFINE 評価機構から切り離す — テストされているのは「これらの変数がここでマッチするとして NFA ループは期待されるマッチ範囲を生むか?」であって「DEFINE 式評価器はこれらのブールを正しく計算するか?」ではない。DEFINE 評価器は別の場所でテストされる(解析は rpr_base、end-to-endの動作は rpr)。

典型的なテスト入力はこう見える — 各エントリがその行で発火する DEFINE 変数を指す変数名配列の列と、それらの名前を直接検査する DEFINE 句を持つパターン:

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 レッグへどこで切り替えるかについて実際の選択を持つ。期待されるマッチ(標準の greedy 選好の下、行 1–3 の A の後に行 4 の B)はそれらのフラグだけで定まり、ここではいかなる結果的な式評価も介在しない — = ANY は単に配列列を DEFINE に露出する些細な層であってテストが検査するものではない。同じシナリオを数値述語(price > PREV(price) など)で書けば NFA テストが述語評価器の動作と絡み合う。配列イディオムは両者を綺麗に分離し、ここでの失敗は NFA ループを直接指す。

absorption のカバレッジは特に徹底している。absorption は作動すべきでないときに作動すれば静かに誤答を生む可能性が最も高い最適化だからだ。テストは §3.2 のケース分析からのすべての形を網羅する:

absorption を超えて、スイートはコンテキスト寿命を網羅する。AFTER MATCH SKIP TO NEXT ROW 下の重なるコンテキスト、ストリーム途中の失敗コンテキストの片付け、未完了コンテキストのパーティション末確定、ヘッドコンテキストに候補マッチが既に記録された後に出会うコンテキスト。これらはそれぞれ §3.6 の特定の 枝刈り 規則に対応し、テストは規則が誤発火(冗長なコンテキストを生かしておく、または出力を生むべきコンテキストを殺す)した場合に大声で失敗するように書かれている。

4.4 rpr_explain — 出力の安定性

EXPLAIN 出力は利用者向けインタフェースの一部だ — サードパーティツール(監視ダッシュボード、ログスクレイパ)がそれを解析し、見た目の変更が彼らを壊し得る。rpr_explain スイートは3つを検証する:

rpr_base 同様、このスイートも実行終了時にオブジェクトを意図的に残し、pg_dump と pg_upgrade のカバレッジが explain 側のアーティファクトにも及ぶようにする。

4.5 rpr_integration — プランナ相互作用

PostgreSQL のプランナはウィンドウクエリに作用する多くの最適化を持つ — フレーム正規化、run-condition pushdown、同一ウィンドウ重複除去、未使用出力の射影、移動集約の逆遷移 — そしてそれぞれが RPR を念頭に設計されたものではない。それらの大半はウィンドウが PATTERN 句を持つとき適用するのが安全でない。フレームはマッチ契約の一部であり、マッチした出力はもはや明らかな意味で単調でなく、同じ仕様だが異なる DEFINE を持つ2つのウィンドウは本当に異なる結果を生む。integration スイートはこれらの最適化のそれぞれが RPR ウィンドウをどう扱うかを検証する — 大半は無効化または回避されねばならない:

フレーム正規化
プランナは通常、row_number、rank、ntile のようなフレームに依存しないウィンドウ関数に対して ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING を ROWS UNBOUNDED PRECEDING に書き換える。RPR のフレームはマッチ範囲であり集約ウィンドウではない。そのまま保たれねばならない。
Run-condition pushdown
ウィンドウ関数出力に対する単調 WHERE フィルタは通常、停止条件としてウィンドウ演算子へ押し下げられる。RPR ではこれがパターンマッチングを早期終了させ、拡張中のマッチを切り落とす可能性がある。
ウィンドウ重複除去(RPR vs 非 RPR)
同じ ORDER BY とフレームを持つ2つのウィンドウは通常、一つに統合される。RPR ウィンドウと非 RPR ウィンドウは決して状態を共有できない。RPR 側がマッチ結果を保持するからだ。
ウィンドウ重複除去(異なる DEFINE または SKIP)
同じ PATTERN だが異なる DEFINE 句または異なる AFTER MATCH SKIP を持つ2つの RPR ウィンドウは異なるマッチを生み、構造形が同一でも別個に保たれねばならない。
未使用出力の射影
これは適用が許される。外側のクエリがウィンドウの出力を決して読まないとき、ウィンドウ関数は NULL になりその WindowAgg は除去され、行数は変わらない。テストは、WindowAgg が残るときには DEFINE が読む列が依然そこに届くこと、そしてウィンドウの値が読まれるときにはウィンドウが保持されることを確認する。
移動集約の逆遷移
逆遷移関数を持つウィンドウ集約は通常、フレームが移動するにつれ漸進的に評価できる。RPR の reduced frame はスライディングウィンドウではない。逆遷移経路は誤った結果を生む。

さらなるケースは、コスト見積もりが DEFINE を考慮すること、RPR ウィンドウを持つサブクエリが平坦化されないこと、DEFINE 式が上位の WindowAgg へ漏れないこと、LIMIT が WindowAgg の上に留まることを確認する。第二のグループは CTE、結合、集合演算、プリペアド文、パーティションテーブルなどの構文と並べて RPR を実行する。ガードされたケースの大半は同じ形に従う。最適化を誘発するベースライン(通常は非 RPR クエリで、EXPLAIN で確認)の後に、構造的に類似した形の RPR クエリで最適化が適用されないことを確認する — DEFINE/SKIP 重複除去のケースではベースラインは2つの同一 RPR ウィンドウであり、逆遷移のケースは EXPLAIN ではなくログ出力する集約で回避を確認する。両半が共にプランナのガードが実際の仕事をしていることを証明し、すべてのクエリに静かにゴム印を押すのではないと示す。

このスイートは §3.4 が短い理由でもある。「マッチ境界」メカニズム — reduced frame、SKIP、INITIAL、限定フレームカットオフ — は他所で運用的にテストされる。rpr_integration が検証するのは、通り過ぎる途中でこれらに他のオプティマイザ段階が手を加えないことだ。rpr_integration の通過は他のスイートが、自身の入力が無傷で実行器に到達すると信頼できるようにする。