Row Pattern Recognition ディープダイブ

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

1.1 標準の範囲

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

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

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

R020 表面は小さいが表現力に富む。クエリはウィンドウ仕様内に３つの句を追加してパターンをウィンドウに付ける。PATTERN は名前付きパターン変数に対する正規表現を記述し、DEFINE は各変数を識別するブール述語を供給し、AFTER MATCH SKIP はパーティション内で連続するマッチがどう配置されるかを制御する。

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

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

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

1.2 実装済み機能

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

PATTERN 句

ウィンドウ仕様内に row pattern を定義する。

正規表現: + * ? |

標準数量子と選択(alternation)。

正規表現: ( ) グループ化

括弧で囲まれた部分パターン。

正規表現: {n} {n,} {,m} {n,m}

限定された(bounded)反復回数。

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

標準が定義する７つの 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)) — 内側と外側のステップそれぞれが独自のオフセットを取れる。

INITIAL

パターンマッチは現在行から開始しなければならない(既定)。

AFTER MATCH SKIP PAST LAST ROW

既定の skip モード。context absorption の対象。

AFTER MATCH SKIP TO NEXT ROW

マッチの重なりを許可。absorption を無効化。

1.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 label、AFTER MATCH SKIP TO FIRST var、AFTER MATCH SKIP TO LAST var がこれにあたる。これらもマッチ履歴に依存する。実行器が最新のマッチ内の特定のラベル付き行を指せる必要があるからだ。

残りは雑多な末尾項目である。SEEK キーワード(INITIAL の代替)、空パターン ()、除外(exclusion)形 {- … -}、順序無関係演算子 PERMUTE。

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 label

ラベル付き行へ skip。

AFTER MATCH SKIP TO FIRST var

名前付き変数としてマッチした最初の行へ skip。

AFTER MATCH SKIP TO LAST var

名前付き変数としてマッチした最後の行へ skip。

正規表現: {- -}

除外(exclusion) — マッチした行をマッチ単位の出力から取り除く。

正規表現: ()

空パターン — 空シーケンスにマッチ。

PERMUTE(...)

列挙された変数間の順序無関係マッチ。

DEFINE 内の集約関数

SUM、AVG、COUNT のような集約関数は DEFINE 述語に使えない。標準は部分マッチに対する running 集約(ある変数に既にマップされた行に対する行ごとの評価)を許すが、これは MEASURES/CLASSIFIER() が要求するのと同じマッチ履歴に依存する。

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

第一に、パターンアンカー ^ と $ は標準自身が 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 変数を参照できない。RPR は再帰クエリの中で使えない。

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

§2. 例 — 実際の動き

本節の例は段階的に積み上がる。まず row pattern matching が文字列パターンマッチングと本質的に異なる概念的理由から始め、次に DEFINE 条件を興味深くする４つのナビゲーション関数を紹介し、最後に３つのend-to-endのトレースをたどる。単一マッチ(NFA の動き)、簡単な場合の context absorption、そして absorption が安全でなくなる場合である。

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

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

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

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

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

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

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

2.2 ナビゲーション関数

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

PREV(expr [, n])

現在行の n 行前の行(既定 n = 1)。「今日 vs 昨日」の比較に使用。

NEXT(expr [, n])

現在行の n 行後の行。前方先読み。ウィンドウ形式ではウィンドウが単調なため珍しい。

FIRST(expr [, n])

現在のマッチの先頭から数えて n 番目のマッチ行。「このマッチを開始した行と比較せよ」。

LAST(expr [, n])

最新の n 番目のマッチ行。「最新のマッチ行と比較せよ」。

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

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

マッチの n 番目の行から m 行戻る(既定 m = 1)。「このマッチが始まる直前の値は?」。

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

マッチの n 番目の行から m 行進む。現在行に依存せずマッチの内側に踏み込む。

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

最新の n 番目のマッチ行から m 行戻る。「最新のマッチの少し前の行と比較」。

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

最新の n 番目のマッチ行から m 行進む。

ここで実用的に二点指摘しておきたい。第一に、ナビゲーションは合成できる。PREV(FIRST(price)) はマッチ開始直前の行を読み、パッチはこれを支援する。第二に、ナビゲーションは実行器の最適化に影響する。PREV と NEXT は現在行基準であり常に安全だが、FIRST およびオフセット付きの LAST 変種はマッチ境界基準であり、context absorption と相互作用してプランナに本来は破棄する一部のコンテキストを生かしておくことを強いる。その相互作用の仕組みは §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)
);

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

[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 を生き残った唯一の状態は DOWN-exit 分岐にいるため、取られる遷移は UP → DOWN のみである。§2.1 の多状態性はあらゆる UP マッチでのファンアウトとして可視化される(状態は UP+ に留まるか DOWN+ に進めた)。greedy 優先は「退出前にもう一度ループ」なので、データが十分なら反復分岐がマッチをさらに伸ばす。ここではループ中の DOWN が行 5 で消え(130 ≮ 108)、行 4 で DOWN が退出した際に生まれた先の FIN 候補(行 0–4)がマッチとして確定する。

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

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

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

(A | B) 形式はマッチャに選択を与える。任意の行で２つの選択肢が独立に検査され、いくつでもマッチし得る。ここで §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 が決着をつけるまで並列に進む。

両分岐は同じ行に対して同じ長さのマッチを生み、マッチャに２つの候補経路を残す — UP, DONE ラベルと HIGH, DONE ラベル。標準はこれを語彙順序(lexical order)で決する。(UP | HIGH) に書かれた選択肢のうち先に書かれた方がマッチ長と無関係に勝つ。UP が HIGH の前にあるので、生き残る経路は UP, DONE。

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

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

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

メモリは O(n) から O(1) へ。破棄を正当化する absorption 規則は、数量子が無界のときシンプルである:

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

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

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

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

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

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

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

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

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

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

absorption の下では C2 は火曜に C1 にマージされていただろう — マージされたコンテキストは天井を一つしか持たないので、C2 の異なる視点(天井 $118、土曜にようやく終わる４日のラン)はもはや内部状態から復元できない。C2 は生きていなければならない。なぜならランタイムが依然必要としうる独立のマッチ候補だからである。C1 のマッチが水曜に終わった時点で、次の試行は一からやり直すのではなく、まだ走っている C2 から引き継がねばならない。DEFINE 述語がマッチ開始依存性を伴うなら、プランナは先回りして absorption を無効化する。

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

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

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

プランナはこの区別をコンパイル時に検出し、absorption を適用するかをコンテキスト毎に決める。これがポスターのパネル ③ ベンチマークが成功事例でも失敗事例でも線形に保たれる理由でもある。absorption が安全ならランタイムはコンテキストを縮約し、そうでないならプランナは誤答のリスクを取るより複数コンテキストのコストを受け入れる。

ポスターのベンチマーク数値は同じアルゴリズムが大規模で展開された姿である。成功パターン (A+ B+ C+ D) では PostgreSQL と Trino はともにマッチが確定すれば O(n) でスケールし、PostgreSQL の優位 — 約 16× から 33× — は主に JVM 差である。

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

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

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

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

すべて A にマッチする５行に対するパターン 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

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

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

§2.6 と §2.7 を並べて置くと、absorption が失敗する全体像が見える:

どちらか一つの条件で影響を受けるコンテキストの absorption を無効化するに足りる。どちらも有効でないとき — 既定の AFTER MATCH SKIP PAST LAST ROW と PREV、NEXT、素の LAST のみ使う DEFINE 条件 — ランタイムはパターン位置あたり単一コンテキストに縮約し、最後まで線形を保つ。

§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 でなければならず、EXCLUDE オプションは禁止される。これらは標準準拠チェックであり最適化ではない — RPR におけるフレームの概念はマッチ範囲であり、標準はマッチした行以外で埋めることを想定していない。

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

その後、各 DEFINE 述語はパーティションの列に対して型検査され、ブール式へ強制される。この過程で実用的な２つのことが起きる。第一に、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 最適化

最適化は二度報われる。一度は平坦配列の静的要素数で、もう一度はランタイムで処理される行ごとに。すべての変換はランタイムが列挙すべき状態空間を縮める。オプティマイザは AST が変化しなくなるまで８つの書き換え規則を順に適用する:

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

数量子の乗算は安全性チェックが必要な唯一の変換である。オプティマイザは安全な３つのケースでのみ合成する — 両方とも無限((A+)+ → A+)、外側が固定((A{2,3}){5} → A{10,15})、子が {1,1}((A){2,5} → A{2,5})。その他の組み合わせは平坦化により受容カウント集合に隙間(spectrum gap)が生じうる — たとえば (A{2}){2,3} は {4, 6} のみを受け入れるが、単純に A{4,6} へ変換すると 5 も受け入れてしまい意味が変わる。オプティマイザはこれを検知し、構造をそのまま残す。

要素の形

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

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

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

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

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

[4] FIN    パターン完了

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

要素ごとの属性

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

Reluctant

数量子展開の順序を反転する。greedy 数量子は「退出」より先に「もう一度ループ」を試み、reluctant 数量子は「退出」を先に試みる。A+? では変数が、((…)+?) ではグループの BEGIN と END が持つ。

Empty-loopable

本体が nullable なグループの END に設定((A?)*、(A? B?)+、(A | B*))。通常のループバックと並んで fast-forward 退出を追加するようランタイムに指示し、cycle guard が空反復を生み得るグループの正当なマッチを殺さないようにする。

In-absorbable-region

absorption 適格領域内にあるすべての要素に印を付ける — ランタイムが現在状態が依然安全領域にあるかを追跡するのに使う。

Absorption-comparison-point

absorption 比較を実行すべき特定の要素に印を付ける。単純な A+ では変数に、(A B)+ のような無界グループでは group end のみに位置する。

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

吸収可能性の解析

コンパイルの段階 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
  AST を巡回し構造的事例を
  満たす要素に印付け

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

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)+

先頭の無界変数自体が吸収可能(Case 1)で、早いコンテキストを保護する。状態が A を越える瞬間 absorption は止まる — 本体の残りは単調性の保証がないので、フラグは A にのみ設定される。

上記３つの形態に該当しない構造的事例も同様に教訓的である。A B+ は現在の規則では吸収できない。先頭の A が無界部分の開始前に行を消費するので、一行ずれて開始するコンテキストは無界本体内の異なる位置にあるからだ。(固定長接頭部を shadow path で扱う後続の「PREFIX absorption」拡張が設計されており別パッチで予定されている。) 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 を保存
  targetPos の行を current_row_slot
    へ取得
  result = eval_inner_expression()
  current_row_slot を復元
  return result

トリックは、保存・復元するスロットが正確に一つだけという点である。内部式 — 算術、関数呼び出し、他の列参照を含め何であれ — は current row に対してと同じ評価経路で交換されたスロットに対して走る。代替評価器なし、shadow slot なし、タプルコピーなし。

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

compute_target_position(call):

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

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

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

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

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

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

保持範囲

ナビゲーションはウィンドウ関数機構が既にストリームし通り過ぎた行に手を伸ばす。それらを利用可能に保つため、実行器は最近の行のスライディングウィンドウを保持するタプルストアの上に座る。問題はそのウィンドウがどれだけ広いべきかである。パッチは２つの相補的なオフセットからコンパイル時に決める:

Lookback 範囲

どの DEFINE 呼び出しが現在行からどれだけ後ろへ届きうるか。

寄与要因: PREV、オフセット付き LAST、PREV(LAST(...))、NEXT(LAST(...))

Lookahead-from-start 範囲

どの DEFINE 呼び出しが最も古い生存コンテキストのマッチ開始からどれだけ前へ(負ならば後ろへ)届きうるか。

寄与要因: FIRST、PREV(FIRST(...))、NEXT(FIRST(...))

ランタイムでタプルストアのトリムマークは２つの位置のうち早い方 — 現在行から lookback 範囲を引いた位置と、最古の生存コンテキストのマッチ開始に lookahead 範囲を加えた位置 — に設定される。そのマークより前は、どの生存コンテキストのどのナビゲーション呼び出しからも到達できず、タプルストアは自由に捨てられる。EXPLAIN が報告する(§3.7)２つの Nav Mark カウンタ — Lookback と Lookahead — はこの２範囲の測定ピーク、すなわちクエリの過程で実行器が両方向に届かねばならなかった最深点である。

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

成功したマッチは小さな値の束として記録される。妥当性フラグ、成功/失敗フラグ、マッチ開始の行、消費した行数。妥当性フラグが立てば、実行器に対する後続のクエリ — 「この行はマッチ内か?」 — は束を見れば O(1) で答えられる。長さ 0 はエラーではなく実在の結果である。行を消費せずマッチしたパターンを表し、実行器は「この位置でまだマッチを試みていない」と区別せねばならない。

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

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

標準が定義するもう２つの 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 三相の行ごとエンジン

実行器の行ごとドライバは、与えられた行がマッチしたフレームに属するかを知る必要があるたび、周囲のウィンドウ関数機構によって呼び出される。ドライバは現在の開始位置に対するコンテキストを見つけるか作成し、すべての DEFINE 述語を現在行に対して一度評価して変数ごとのブール配列を生み、NFA を一行進める。前進ステップ自体は同じ外側ループに包まれた固定順序の三相 — 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)

順序は様式上の選択ではない。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]
      if elem が変数でない:
          continue   # advance が処理

      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

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

第二に、各コンテキストの非対称フラグ対だ。has-absorbable-state は「このコンテキストはより新しいものを吸収できるか?」に答えるフラグで、単調的だ(状態が消えると true→false にしか進めない)。一方 all-states-absorbable は「このコンテキストは吸収され得るか?」に答えるフラグで、動的である(吸収不能状態が除かれると true に戻る)。両フラグは 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 分岐 (順序通り),
    BEGIN (グループ進入; min = 0 なら
           スキップ経路を追加),
    END (ループバック / 退出 / fast-forward —
         下記参照),
    FIN (matchEndRow を記録,
         matchedState を保存し、この候補
         範囲内の後続コンテキストを破棄
         — 下記参照),
  変数に出会うたび停止:
      state を ctx.states に追加
      (elemIdx + counts で重複除去)

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

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

これは２つの FIN-time 枝刈りステップの一つで、もう一つは本節前半で 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 充足扱い)
          (cycle guard が殺してしまう
           正当なマッチを救済)

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

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

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

空ループ可能グループ

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

ランタイムは訪問要素ビットマップ(パターン要素ごとに 1 ビット)で止める。これは各状態の DFS 展開前にクリアされ、同じ展開内で要素が二度目に訪れられた瞬間その経路は破棄される。cycle guard は無条件で安価だが副作用がある — 正当な空反復で下界に達すべき経路も破棄しうる。行ストリームのどこでも A がマッチしない (A?){2,3} を見よ:

期待される動作:
  iter 1: A? が 0 行マッチ
          → END, count = 1 (min 未満)
  iter 2: A? が 0 行マッチ
          → END, count = 2 (min 充足)
  長さ 0 マッチで退出

cycle guard 単独の動作:
  iter 1: A? skipped → END, count = 1
          → BEGIN へ loop back
  iter 2: BEGIN は訪問済み
          → DFS 中断
  count が min に達しない
  → マッチ失敗 (誤った結果)

解決策はコンパイル時に決まり実行時に発動する。プランナは本体が nullable なグループに出会うたび、そのグループの END 要素に empty-loopable タグを付ける。実行時に END ハンドラが「反復カウントがまだ下界未満」という理由でループバックしようとするとき、このタグが通常のループバック経路と並行して追加の fast-forward 状態もクローンするよう指示する:

advance_end (count が min 未満):

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

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

２つの経路は互いに補い合う。主たるループバックは本体が 後で 実際のマッチを生む場合に対応する — 例えば (A?){2,3} に続いて A が後の行でのみマッチするデータでは、ループバックのおかげで第二・第三の反復が空でないマッチを見つけられる。fast-forward は本体が最後まで何も生まない場合に対応する — グループ自体から退出して cycle guard を回避し、「残りの必要な反復はすべて空」と宣言して長さ 0 の本体でマッチを成立させる。両状態がコンテキストに入り、最後まで生き残った方が勝つ。挿入時の重複除去チェックがどちらの経路も自分の分以上の状態を生まないよう防ぐ。

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 キューに依然保留中の状態 — 語彙順序により残るすべての状態はあまり選好されず、直ちに破棄できる。

候補マッチ 枝刈り(コンテキスト間) On FIN

開始行が候補マッチ範囲内に落ちる他のコンテキスト — FIN に達したコンテキストはより長いマッチを探し続け得る(greedy fallback)が、AFTER MATCH SKIP PAST LAST ROW の下では候補範囲内のいずれのコンテキストもその探索の結果に関わらず報告可能な出力を生み得ず、直ちに破棄される。

Cycle guard Advance

同じ DFS 内で同じパターン要素を再訪するイプシロン展開 — そうでなければ nullable グループで永遠にループする。

Empty-loop fast-forward Advance

cycle guard が nullable グループで殺してしまう正当な空反復マッチ — 残りの必要反復を空と宣言してグループを退出することでサイクルを回避する。

限定フレームカットオフ Match

マッチが利用者指定のフレーム上界に達したコンテキスト — それを越えて延長できないよう強制ミスマッチ(§3.4)。

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

どの単一規則も単独では不十分だろう。cycle guard だけでは nullable グループの正当なマッチを殺すし、empty-loop fast-forward だけでは無限イプシロンループを止められない。absorption だけでは DEFINE がマッチ開始を参照する場合に過剰集約する。重複除去だけでは冗長な状態のみを除き冗長なコンテキストを除けない。ランタイムが重要な事例 — 100,000 行に対する PATTERN (A+ B+ C+ D)、ポスターのパネル ③ ベンチマーク — で線形を保つのは、すべての層が上の層が見落とすものを捕らえるからにほかならない。

3.7 EXPLAIN 出力

RPR を持つクエリへの EXPLAIN ANALYZE は、通常のウィンドウ関数には存在しない NFA レベルの統計を露出する。３つのカウンタグループがウィンドウ演算子と共に発行される:

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 はランタイムの直接計測である。同時に生きていた状態が何個か、クエリ寿命にわたって何個作られたか、重複除去で何個が併合されたか。マッチ長ヒストグラムは４つの結果 — 成功マッチ、失敗マッチ試行、吸収されたコンテキスト、評価されずに破棄(skip)されたコンテキスト — を分離し、min/max/avg で報告して性能の病理を一目で可視化する。健全な実行ではほとんどのコンテキストはマッチか吸収のいずれかとして現れ、ミスマッチの長さは小さい。

２つの Nav Mark カウンタは §3.3 がコンパイル時に導出するタプルストアの保持範囲を報告する。Lookback は PREV、オフセット付き LAST、内側 LAST を持つ複合形にわたる最も深い後方到達。Lookahead は最も古い生存コンテキストのマッチ開始から測定された最も深い前方(負ならば後方)到達で、FIRST と内側 FIRST を持つ複合形が寄与する。

各カウンタはオフセットが定数なら固定整数、呼び出しごとに評価せねばならない非定数式なら「runtime」、ランタイムが無界範囲を必要とするなら「retain all」と出力される。Lookahead はクエリが実際にマッチ開始相対のナビゲーションを使うときのみ発行される。

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

カウンタを超えて、EXPLAIN は元の PATTERN と DEFINE 句を、reluctant 数量子、グループ反復、AFTER MATCH SKIP オプションも含めて忠実に再現する。実装はこの round-trip を安定にするためにかなりの労を取る。pg_dump と pg_upgrade が意味的ずれなく RPR オブジェクトを保存できるためだ — rpr_explain 配下の回帰スイートが事例ごとに検証する(§4 参照)。

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

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

rpr

end-to-endのクエリ意味論 — 合成株価データ上の現実的なウィンドウシナリオ(V 字、W 字、連続上昇、反転)。

rpr_base

パーサ層 — キーワード受理、構文形、数量子、ナビゲーション解析、エラーメッセージ、pg_dump/pg_upgrade の round-trip 安定性。

rpr_nfa

NFA ランタイム — 三相ループ、すべての吸収可能形での吸収、コンテキスト寿命のエッジケース。

rpr_explain

出力フォーマット — NFA 統計、パターンの deparse、識別子の引用、再ロード間のフォーマット安定性。

rpr_integration

プランナ相互作用 — 無関係なウィンドウ最適化が RPR 意味論を破壊するのを防ぐガード。

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

シナリオスイートはテストセットの公的な顔である。約 1,600 行の合成株価データセットを使い、現実的なクエリを実行する — V 字回復、W 字(ダブルボトム)、連続上昇と下落、反転パターン、複数シンボルパーティション。入出力が利用者が実際に書きうるクエリのように読める唯一のスイートだ。他は意図的に切り詰められ、一度に一つの層に集中する。

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

4.2 rpr_base — パーサ表面

base スイートは最大で、その理由がある。§1.2 のすべての合法な構文片が実際に解析され、§1.3 のすべての非合法な片が有用なエラーで拒否され、すべての受理形が直列化 round trip を生き延びることを証明する責任があるからだ。大部分は長い現実的クエリではなく小さく焦点を絞ったスニペット(構文機能ごとに一つ)として整形される。目標がシナリオ現実性ではなくカバレッジだからだ。

直列化テストには特別な配慮が要る。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 変数がマッチするかを宣言する明示的なブール配列を行とする入力テーブルと、特定のランタイム動作を探るパターンの組である。ブール配列イディオムはランタイムテストを 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 のケース分析からのすべての形を網羅する:

• 単純な無界変数(A+) — 典型的な N-to-1 縮約;
• 固定長グループ((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 を超えて、スイートはコンテキスト寿命を網羅する。AFTER MATCH SKIP TO NEXT ROW 下の重なるコンテキスト、ストリーム途中の失敗コンテキストの片付け、未完了コンテキストのパーティション末確定、ヘッドコンテキストに候補マッチが既に記録された後に出会うコンテキスト。これらはそれぞれ §3.6 の特定の 枝刈り 規則に対応し、テストは規則が誤発火(冗長なコンテキストを生かしておく、または出力を生むべきコンテキストを殺す)した場合に大声で失敗するように書かれている。

4.4 rpr_explain — 出力の安定性

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

• NFA カウンタが正しい場所に現れる — WindowAgg ごとの統計(peak/total/merged 状態、peak/total/pruned コンテキスト、matched/mismatched/absorbed/skipped の長さヒストグラム、Nav Mark Lookback、そしてマッチ開始相対のナビゲーションが使われるとき Nav Mark Lookahead)がすべて文書化されたラベルで EXPLAIN ANALYZE 下に現れる。
• パターンが正しく deparse される — reluctant 変種と限定形を含むすべての数量子の形、すべての選択、すべてのグループ、すべての AFTER MATCH SKIP 形、INITIAL、オフセット付きナビゲーション呼び出し、複合ナビゲーション。deparse されたテキストは変更なしにパーサを round-trip せねばならない。
• 識別子の引用が正しい — パターン変数と DEFINE 式は通常の SQL 識別子と同じ引用規則で発行され、変な変数名が pg_dump 出力を壊さない。

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

4.5 rpr_integration — プランナ相互作用

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

フレーム正規化

プランナは通常、単調集約に対して ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING を ROWS UNBOUNDED PRECEDING に書き換える。RPR のフレームはマッチ範囲であり集約ウィンドウではない。そのまま保たれねばならない。

Run-condition pushdown

ウィンドウ関数出力に対する単調 WHERE フィルタは通常、停止条件としてウィンドウ演算子へ押し下げられる。RPR ではこれがパターンマッチングを早期終了させ、拡張中のマッチを切り落とす可能性がある。

ウィンドウ重複除去(RPR vs 非 RPR)

同じ ORDER BY とフレームを持つ２つのウィンドウは通常、一つに統合される。RPR ウィンドウと非 RPR ウィンドウは決して状態を共有できない。RPR 側がマッチ結果を保持するからだ。

ウィンドウ重複除去(異なる DEFINE)

同じ PATTERN だが異なる DEFINE 句を持つ２つの RPR ウィンドウは異なるマッチを生み、構造形が同一でも別個に保たれねばならない。

未使用出力の射影

外側のクエリがウィンドウの行ごと出力を決して読まなくとも、RPR ウィンドウは除去できない。パターンマッチャの副作用(どの行がどのマッチ内か)が計画の他所での reduced-frame 計算に供給されるからだ。

移動集約の逆遷移

逆遷移関数を持つウィンドウ集約は通常、フレームが移動するにつれ漸進的に評価できる。RPR の reduced frame はスライディングウィンドウではない。逆遷移経路は誤った結果を生む。

これらのテストにわたるパターンは同じだ。それぞれが最適化を誘発する非 RPR ベースラインを提供し(EXPLAIN がそれが適用されることを示すのを検証)、構造的に類似した形の RPR クエリを実行して最適化が適用されないことを検証する。両半が共にプランナのガードが実際の仕事をしていることを証明し、すべてのクエリに静かにゴム印を押すのではないと示す。

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