Row Pattern Recognition im Detail

§1. Der Standard, die Teilmenge und die offenen Fragen

1.1 Umfang des Standards

Row Pattern Recognition wurde mit ISO/IEC 9075-2:2016 in SQL eingeführt und im begleitenden Dokument ISO/IEC 19075-5:2021 (Teil 5, „Row Pattern Recognition") beschrieben.

Der Standard definiert zwei Oberflächen (surfaces) für dieselbe zugrunde liegende Maschinerie. Feature R010 platziert eine MATCH_RECOGNIZE-Klausel in der FROM-Liste und erzeugt damit eine abgeleitete Tabelle (derived table); Feature R020 faltet dieselbe Musterlogik in eine WINDOW-Spezifikation und liefert Window-Function-Ausgaben. Beide Oberflächen teilen den Großteil der Syntax und die gesamte Semantik, sind aber funktional eigenständige Einstiegspunkte — eine Datenbank kann eine von beiden oder beide implementieren.

Die hier diskutierte Patch-Serie implementiert eine Teilmenge ausschließlich von R020; die Tabellenklausel-Form liegt bewusst außerhalb des Umfangs.

Die R020-Oberfläche ist klein, aber ausdrucksstark. Eine Abfrage hängt ein Muster an ein Fenster, indem drei Klauseln in der Window-Spezifikation ergänzt werden: PATTERN beschreibt einen regulären Ausdruck über benannten Pattern-Variablen, DEFINE liefert das boolesche Prädikat, das jede Variable identifiziert, und AFTER MATCH SKIP steuert, wie aufeinanderfolgende Treffer innerhalb der Partition positioniert werden.

Optionale MEASURES, SUBSET, INITIAL/SEEK sowie die Hilfsfunktion CLASSIFIER() runden das Feature ab. (Die Standard-Funktion MATCH_NUMBER() gehört nur zur R010-Oberfläche — 19075-5 §6.3.3 (6) schließt sie ausdrücklich von R020 aus.)

Der Patch deckt von diesem Vokabular genug ab, damit nicht-triviale Abfragen funktionieren, lässt aber mehrere Konstrukte aus, deren Implementierung auf Infrastruktur angewiesen ist, die noch nicht existiert.

Der Rest dieses Abschnitts gliedert das Vokabular des Standards in das, was der Patch bereits unterstützt, und das, was er bewusst auf später verschiebt. Die folgenden Listen spiegeln den aktuellen Stand der Patch-Serie wider.

1.2 Implementierte Features

Das implementierte Vokabular reicht aus, um die kanonischen V-Form-, W-Form- und Umkehrungsmuster auszudrücken, die Row Pattern Recognition überhaupt motivieren. Es deckt zudem jeden Standard-Quantor ab — einschließlich aller sieben reluctant-Varianten *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — sowie die vier Navigationsprimitiven, die DEFINE-Bedingungen brauchen, um benachbarte Zeilen zu vergleichen.

PATTERN-Klausel

Definiert das Row Pattern innerhalb einer Window-Spezifikation.

Regex: + * ? |

Standardquantoren und Alternation.

Regex: ( ) Gruppierung

In Klammern gesetzte Teilmuster.

Regex: {n} {n,} {,m} {n,m}

Beschränkte Wiederholungszahlen (bounded repetition).

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

Alle sieben reluctant-Varianten (non-greedy), die der Standard definiert (von der Absorption-Optimierung ausgenommen).

DEFINE-Klausel

Boolesche Bedingungen zur Identifikation jeder Pattern-Variable.

Universelle Zeilenmuster-Variable

Unqualifizierte Spaltenreferenzen in DEFINE (z. B. bloßes Price) werden auf die aktuelle Zeile aufgelöst, gemäß 19075-5 §4.10/§4.16.

PREV, NEXT (mit Offset)

Greift n Zeilen vor/nach der aktuellen Zeile zu (Standard 1); das innere Argument ist ein beliebiger Wertausdruck, der an der angesteuerten Zeile ausgewertet wird.

FIRST, LAST (mit Offset)

Greift auf eine match-relative Zeile zu; FIRST(expr, n) zielt auf die Zeile n nach Match-Beginn, LAST(expr, n) auf die Zeile n vor der aktuellsten Match-Zeile.

Verbundnavigation (vier Formen)

Äußerer PREV/NEXT-Schritt um ein inneres FIRST/LAST gelegt: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — innerer und äußerer Schritt akzeptieren je einen eigenen Offset.

INITIAL

Pattern-Matches müssen an der aktuellen Zeile beginnen (Standard).

AFTER MATCH SKIP PAST LAST ROW

Standard-Skip-Modus; für Context Absorption geeignet.

AFTER MATCH SKIP TO NEXT ROW

Erlaubt überlappende Matches; deaktiviert die Absorption.

1.3 Nicht implementiert

Die noch nicht implementierten Features lassen sich in drei lose Gruppen einteilen. Die erste — und mit Abstand größte — ist die Familie der Konstrukte rund um MEASURES: die MEASURES-Klausel selbst, SUBSET, CLASSIFIER(), pattern-qualifizierte Spaltenreferenzen wie B.price und pattern-qualifizierte Navigation wie LAST(B.price) oder PREV(B.price).

Es handelt sich weniger um unabhängige Lücken als um verschiedene Sichten auf ein einziges fehlendes Stück: Der Executor müsste eine Match-Historie pro Treffer führen — einen Eintrag für jede Zeile des Matches darüber, welcher Pattern-Variable sie zugeordnet wurde — und ohne diese Historie hat keines der genannten Konstrukte eine sinnvolle Definition. CLASSIFIER() liest den Variablennamen aus diesem Eintrag aus; B.price liest die Preis-Spalte derjenigen Zeilen, deren Eintrag B lautet; LAST(B.price) läuft dieselbe Menge ab und wählt die letzte; SUBSET U = (A, B) definiert eine virtuelle Variable, die über beide Buckets aggregiert; und MEASURES wertet Ausdrücke wie AVG(U.Price) mit genau dieser Aggregation aus.

Der aktuelle Executor wertet DEFINE-Prädikate zeilenweise aus, hält die resultierenden Variablen-Zuordnungen aber nirgends fest — es gibt nichts, was man später abfragen könnte. Der Aufbau der Historie-Infrastruktur ist daher die Voraussetzung für die gesamte Gruppe; die einzelnen Features ergeben sich als kleine Projektionen, sobald die Einträge existieren.

Die zweite Gruppe betrifft alternative Skip-Ziele: AFTER MATCH SKIP TO label, AFTER MATCH SKIP TO FIRST var und AFTER MATCH SKIP TO LAST var. Auch sie hängen von der Match-Historie ab, denn der Executor muss auf eine bestimmte beschriftete Zeile innerhalb des jüngsten Matches zeigen können.

Die übrigen Punkte bilden einen heterogenen Rest: das Schlüsselwort SEEK (die Alternative zu INITIAL), das leere Muster (), die Ausschlussform {- … -} und der reihenfolgeunabhängige Operator PERMUTE.

MEASURES

Benannte Ausgabeausdrücke pro Treffer, z. B. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; in R020 über OVER wie eine Window-Function angesprochen. Akzeptiert die Schlüsselwörter FINAL / RUNNING (19075-5 §5.4), die in R020 zum gleichen Wert kollabieren, da Measures stets an der letzten Match-Zeile ausgewertet werden (19075-5 §6.9 (3)).

SUBSET

Benannte Vereinigungen von Pattern-Variablen, z. B. SUBSET U = (A, B, C). Nutzbar überall dort, wo eine Pattern-Variable referenziert werden kann — MEASURES, pattern-qualifizierte Referenzen in DEFINE, CLASSIFIER(U) — alle benötigen die Match-Historie.

CLASSIFIER()

Gibt zurück, als welche Pattern-Variable eine gegebene Zeile gematcht wurde. Sowohl für DEFINE als auch für MEASURES definiert (19075-5 §5.9); die Antwort an jeder Zeile ist der Variablenname, der für diese Zeile in der Match-Historie eingetragen ist.

Pattern-qualifizierte Spaltenreferenz

Schlichtes B.price in DEFINE oder MEASURES — der Spaltenwert der Zeile, die als benannte Variable abgebildet ist.

Pattern-qualifizierte Navigation

Beschränkt die Navigation auf Zeilen, die als benannte Variable gematcht wurden, z. B. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

Match darf an beliebiger Stelle im Fenster beginnen (im Gegensatz zu INITIAL).

AFTER MATCH SKIP TO label

Sprung zu einer beschrifteten Zeile.

AFTER MATCH SKIP TO FIRST var

Sprung zur ersten als benannte Variable gematchten Zeile.

AFTER MATCH SKIP TO LAST var

Sprung zur letzten als benannte Variable gematchten Zeile.

Regex: {- -}

Ausschluss — entfernt gematchte Zeilen aus der Ausgabe pro Treffer.

Regex: ()

Leeres Muster — matcht die leere Sequenz.

PERMUTE(...)

Reihenfolgeunabhängiges Matching über die aufgelisteten Variablen.

Aggregatfunktionen in DEFINE

Aggregate wie SUM, AVG, COUNT sind in DEFINE-Prädikaten nicht zulässig. Der Standard erlaubt sie als Running-Aggregate über den Teiltreffer (zeilenweise Auswertung gegen die bereits einer Variable zugeordneten Zeilen), was dieselbe Match-Historie voraussetzt, die auch MEASURES/CLASSIFIER() benötigen.

Vier weitere Punkte sind hier festzuhalten, da sie sich leicht mit Auslassungen verwechseln lassen.

Erstens sind die Pattern-Anker ^ und $ bei RPR in der WINDOW-Klausel bereits durch den Standard selbst untersagt (19075-5 §6.13: „the anchors (^ and $) are not permitted with row pattern matching in windows"; zugrunde liegende Definition in 19075-5 §4.14.1); ihr Fehlen ist Konformität, keine Lücke.

Zweitens ist MATCH_NUMBER() ebenso vom Standard aus R020 ausgeschlossen (19075-5 §6.3.3 (6) und 19075-5 §6.9 (1)) — es gehört nur zur R010-Oberfläche, und sein Fehlen ist auch hier Konformität statt fehlendes Feature.

Drittens auferlegt der Standard R020 eine Reihe struktureller Verbote (19075-5 §6.17): Row Pattern Recognition darf nicht in einer anderen Row Pattern Recognition geschachtelt sein; MEASURES und DEFINE dürfen keine Outer References enthalten; Subqueries innerhalb von MEASURES oder DEFINE dürfen keine Pattern-Variablen referenzieren; und RPR darf nicht in einer rekursiven Abfrage verwendet werden.

Viertens liegt MATCH_RECOGNIZE selbst — Feature R010, die Tabellenklausel-Oberfläche derselben Maschinerie — außerhalb des Umfangs dieses Patches. Ob PostgreSQL R010 schließlich aufnimmt, wird Frage einer künftigen Patch-Serie sein, nicht Maßstab dieser hier.

§2. Beispiele — wie es tatsächlich abläuft

Die Beispiele in diesem Abschnitt bauen schrittweise aufeinander auf. Zunächst der konzeptionelle Grund, warum sich Row-Pattern-Matching grundlegend vom String-Pattern-Matching unterscheidet, dann die vier Navigationsfunktionen, die DEFINE-Bedingungen erst interessant machen, und schließlich drei vollständige Traces: ein einzelner Treffer (NFA-Bewegung), Context Absorption im einfachen Fall und der Fall, in dem Absorption nicht mehr sicher ist.

Der interne Mechanismus, der Navigation günstig macht — der 1-Slot-Tuple-Swap — gehört zum Design des Executors und wird im nächsten Abschnitt behandelt, nicht hier.

2.1 Warum sich Row Patterns von Text Patterns unterscheiden

Ein regulärer Ausdruck über Text matcht einen Strom von Zeichen, und an jeder Position steht genau ein Symbol zur Betrachtung. Die Laufzeitfrage — „ist das aktuelle Symbol gleich 'A'?" — hat eine einzige Ja/Nein-Antwort. Backtracking-Automaten nutzen dies aus: pro Zeichen überlebt höchstens ein Zweig, und die Kosten der Mehrdeutigkeit werden durch das erneute Lesen der Eingabe bezahlt.

Ein Row Pattern ist grundsätzlich anders. Eine Zeile ist kein einzelnes Symbol; sie ist ein Tupel von Spalten, das gegen eine Menge boolescher Prädikate ausgewertet wird — die DEFINE-Bedingungen. Zwei Prädikate können an derselben Zeile gleichzeitig wahr sein, und nichts im Standard verlangt, dass sie sich gegenseitig ausschließen. Beispiel:

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

Eine Zeile mit price = 150, volume = 2000 erfüllt sowohl A als auch B, jedoch nicht C. Der Pattern-Matcher kann das nicht zu einem einzigen Zustand kollabieren — zwei Pattern-Variablen sind aktiv, und jedes Pattern-Element, das eine von beiden benennt, darf weiterlaufen. Der NFA muss daher pro Partitionszeile mehrere gleichzeitige Zustände tragen, nicht einen.

Diese eine Beobachtung prägt die übrige Architektur. Der Ausführungszustand ist eine Liste von Kontexten, jeder Kontext eine Liste von Zuständen, und an jeder Zeile fragt die Laufzeit jeden Zustand: „Wohin kann ich angesichts der hier wahren Variablen gehen?" Die daraus entstehenden Verzweigungen sind der Grund, warum die Laufzeit mehrere Pruning-Schichten braucht — Zustandsdeduplizierung innerhalb eines Kontexts, Absorption zwischen Kontexten und die übrigen in §3.6 behandelten Regeln — andernfalls wächst die Zahl aktiver Zustände und Kontexte mit der Partition und das Pattern-Matching wird super-linear.

2.2 Navigationsfunktionen

DEFINE-Bedingungen, die nur die aktuelle Zeile referenzieren, sind begrenzt; fast jedes interessante Muster muss die aktuelle Zeile mit ihren Nachbarn oder mit zuvor im Match akzeptierten Zeilen vergleichen. Der Standard bietet hierfür vier Navigationsfunktionen, und der Patch implementiert sie alle.

PREV(expr [, n])

Die Zeile n Zeilen vor der aktuellen Zeile (Standard n = 1). Für „heute vs. gestern"-Vergleiche.

NEXT(expr [, n])

Die Zeile n Zeilen nach der aktuellen Zeile. Vorausschau; in der Window-Form selten, da das Fenster monoton ist.

FIRST(expr [, n])

Die n-te gematchte Zeile des aktuellen Treffers, vom Anfang aus gezählt. „Vergleiche mit der Zeile, die diesen Match begonnen hat."

LAST(expr [, n])

Die n-te jüngste gematchte Zeile. „Vergleiche mit der zuletzt gematchten Zeile."

Die vier Primitiven lassen sich kombinieren: PREV und NEXT können einen FIRST- oder LAST-Aufruf umschließen und ergeben vier Verbundformen mit der Semantik „springe zu einer match-relativen Zeile und gehe von dort aus eine feste Distanz weiter". So kann ein DEFINE-Ausdruck z. B. die Zeile direkt vor dem Match-Beginn lesen.

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

Gehe m Zeilen zurück von der n-ten Zeile des Matches (Standard m = 1). „Welcher Wert galt unmittelbar vor Match-Beginn?"

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

Gehe m Zeilen vorwärts von der n-ten Zeile des Matches. Reicht weiter in den Match hinein, ohne von der aktuellen Zeile abhängig zu sein.

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

Gehe m Zeilen zurück von der n-ten jüngsten gematchten Zeile. „Vergleiche mit einer Zeile kurz vor dem jüngsten Match."

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

Gehe m Zeilen vorwärts von der n-ten jüngsten gematchten Zeile.

Zwei praktische Punkte sind hier festzuhalten. Erstens lässt sich Navigation verbinden: PREV(FIRST(price)) liest die Zeile direkt vor Match-Beginn, und der Patch unterstützt dies. Zweitens hat Navigation Konsequenzen für die Optimierungen des Executors. PREV und NEXT sind relativ zur aktuellen Zeile und stets sicher; FIRST und Offset-Varianten von LAST sind relativ zu den Match-Grenzen, was mit Context Absorption interagiert und den Planner zwingt, manche Kontexte am Leben zu halten, die er sonst verwerfen würde. Der Mechanismus hinter dieser Wechselwirkung ist Thema von §2.6.

2.3 Durchgearbeitetes Beispiel 1 — NFA-Bewegung

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

Das Muster wird auf vier Elemente abgeflacht:

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

Für die Preisreihe 100, 110, 120, 115, 108, 130:

Der Kernpunkt: In Zeile 3 erfüllt die Zeile sowohl START (immer wahr) als auch DOWN, doch der einzige Zustand, der Zeile 2 überlebt hat, befindet sich auf dem DOWN-Exit-Zweig, sodass nur der Übergang UP → DOWN genommen wird. Die Mehrzustandsnatur aus §2.1 zeigt sich als Fan-out bei jedem UP-Match (der Zustand könnte bei UP+ bleiben oder in Richtung DOWN+ weiterrücken). Die Greedy-Präferenz lautet „erneut schleifen vor verlassen", sodass die Schleifenzweige bei genügend Daten den Match weiter ausdehnen würden; hier stirbt der Schleifen-DOWN in Zeile 5 (130 ≮ 108), und der frühere FIN-Kandidat (Zeilen 0–4) — entstanden, als DOWN in Zeile 4 verlassen wurde — wird als Match festgeschrieben.

Das Ergebnis der Abfrage folgt unmittelbar aus diesem Trace. Unter RPR-Semantik werden die Window-Funktionen first_value(price) und last_value(price) nur an der Zeile ausgewertet, die den Match begonnen hat — jede weitere Zeile im Match liefert für diese Window-Funktionen NULL, da ihr reduzierter Frame leer ist. Die Ausgabe für unsere Daten entspricht daher der Tabelle im rechten oberen Panel des Posters:

Zeile 0 ist der Match-Start, daher umfasst ihr Frame die Zeilen 0–4 und die Window-Funktionen liefern den Eröffnungspreis ($100) und den Tiefstpreis ($108) der V-Form. Die Zeilen 1–4 liegen im Match, sind aber nicht dessen Start und erhalten daher NULL. Zeile 5 (Preis $130) liegt außerhalb jedes Matches und erhält ebenfalls NULL.

2.4 Durchgearbeitetes Beispiel 2 — Alternation und lexikalische Reihenfolge

Die Form (A | B) gibt dem Matcher eine Wahl: An jeder Zeile werden die beiden Alternativen unabhängig geprüft, und beliebig viele dürfen matchen. Hier wird die Mehrzustandsnatur aus §2.1 innerhalb eines einzelnen Kontexts sichtbar — nicht zwischen Kontexten (das ist Absorption), sondern entlang paralleler Zweige, die der Executor im Gleichschritt erkundet.

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

Stelle dir eine Zeile vor, in der der Preis sowohl gestiegen ist als auch $100 überschreitet — sowohl UP als auch HIGH sind wahr. Jede Alternative erzeugt einen eigenen Zustand: einen, der den UP-Zweig läuft, einen, der den HIGH-Zweig läuft. Sie laufen parallel, bis DONE sie auflöst.

Beide Zweige erzeugen einen Match gleicher Länge über dieselben Zeilen, sodass dem Matcher zwei Kandidatenpfade vorliegen — einer mit UP, DONE beschriftet, einer mit HIGH, DONE. Der Standard löst dies durch lexikalische Reihenfolge: Unter den in (UP | HIGH) notierten Alternativen gewinnt die zuerst geschriebene, unabhängig von der Match-Länge. Da UP vor HIGH steht, ist der überlebende Pfad UP, DONE.

Die lexikalische Reihenfolge ist es, die CLASSIFIER() wohldefiniert macht, sobald die Funktion implementiert ist — sie erlaubt der Laufzeit, dem Anwender zu sagen „diese Zeile wurde als UP gematcht, nicht als HIGH", selbst wenn beide Prädikate wahr waren. Die lexikalische Reihenfolge ist die primäre Regel für Alternation: Ein lex-früherer Zweig schlägt einen lex-späteren auch dann, wenn der lex-spätere einen längeren Match ergeben würde, und ein lex-späterer (möglicherweise kürzerer) Zweig kann doch noch gewinnen, wenn jeder lex-frühere Zweig stirbt, bevor er FIN erreicht. Die Greedy-Länge wird innerhalb eines einzelnen Quantors entschieden — bei zwei Vervollständigungen desselben Alternation-Zweigs bevorzugt der Greedy-Quantor mehr Iterationen.

2.5 Durchgearbeitetes Beispiel 3 — Context Absorption (gleiches Schicksal)

Das einfachste Muster, das Absorption zeigt, ist PATTERN (A+) mit DEFINE A AS TRUE. Jede Zeile matcht A, und der Standard verlangt, dass jede Zeile als möglicher Match-Start betrachtet wird. Naiv bedeutet das N Kontexte für eine N-zeilige Partition. Nehmen wir eine fünfzeilige Partition (beliebige Daten — das Prädikat ist konstant wahr):

Der Speicher wächst von O(n) auf O(1). Die Absorptionsregel, die das Verwerfen rechtfertigt, ist bei unbeschränktem Quantor unkompliziert:

Das untere linke Panel des Posters („① Context Absorption") ist genau diese Regel über fünf Zeilen visualisiert.

In der Regel verbirgt sich ein subtiler, aber wichtiger Punkt: Das Verwerfen ist sicher, weil das Prädikat A AS TRUE an jeder Zeile denselben Wert liefert, unabhängig davon, welcher Kontext fragt. Dasselbe gilt für jedes Prädikat, das nur die aktuelle Zeile oder einen festen Offset davon referenziert — einschließlich PREV. Das nächste Beispiel wechselt zu einer konkreten Handelswoche und verwendet ein PREV-basiertes Prädikat; §2.6 nutzt dieselbe Woche erneut, um die Symmetrie zwischen sicherer und unsicherer Absorption deutlich zu machen:

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

Nimm die Handelswoche $100, $108, $112, $116, $110 von Montag bis Freitag — vier Anstiege gefolgt von einem plötzlichen Rückgang. Angenommen, C1 startet am Dienstag (der erste Tag, an dem RISE matcht: $108 > $100), und der Executor verfolgt spekulativ zusätzlich C2 ab Mittwoch. Die RISE-Bedingung jeder Zeile vergleicht den Preis der Zeile mit dem unmittelbaren Vorgänger — ein Fakt auf Partitionsebene, nicht auf Kontextebene — sodass die beiden Kontexte an jeder gemeinsamen Zeile zwangsläufig denselben booleschen Wert berechnen:

Die Geschichte bricht in dem Moment, in dem das Prädikat von den Grenzen jedes einzelnen Kontexts abzuhängen beginnt — und genau darum geht es in §2.6.

2.6 Durchgearbeitetes Beispiel 4 — Wenn Absorption unsicher wird

Angenommen, ein Analyst sucht aufeinanderfolgende Handelstage, an denen eine Aktie innerhalb von zehn Dollar des Starttags des Laufs blieb — eine Art Konsolidierungsfenster. Pattern und DEFINE sehen so aus:

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

Die Bedingung vergleicht jetzt den Preis der aktuellen Zeile mit dem Preis am Start des aktuellen Laufs. Zwei Läufe, die an verschiedenen Tagen begannen, haben unterschiedliche FIRST(price)-Werte, sodass zwei Zustände am gleichen Pattern-Element mit demselben Zähler nicht mehr austauschbar sind: ihre Zukünfte hängen genau von der Grenze ab, die die Absorption verwerfen wollte.

Nimm exakt dieselbe Handelswoche wie in §2.5 — $100, $108, $112, $116, $110 von Montag bis Freitag. Die Laufzeit hält erneut zwei Kandidatenläufe gleichzeitig am Leben: C1 startete am Montag, C2 am Dienstag (unter STABLE+ ist jede Zeile ein potenzieller Lauf-Start).

Unter Absorption wäre C2 am Dienstag in C1 zusammengeführt worden — der zusammengeführte Kontext behält nur eine Obergrenze, sodass C2s eigene Sicht (Obergrenze $118, der viertägige Lauf, der erst am Samstag endet) aus dem internen Zustand nicht mehr rekonstruierbar ist. C2 muss am Leben bleiben, weil er ein unabhängiger Match-Kandidat ist, den die Laufzeit noch brauchen kann: Sobald C1s Match am Mittwoch endet, muss der nächste Versuch von einem noch laufenden C2 aus aufnehmen, statt von vorn zu beginnen. Sobald ein DEFINE-Prädikat eine Match-Start-Abhängigkeit trägt, deaktiviert der Planner die Absorption daher präventiv.

(Wenn der Match des führenden Kontexts doch gelingt, werden Kontexte, die innerhalb seines akzeptierten Bereichs gestartet sind — unter dem Standard AFTER MATCH SKIP PAST LAST ROW — schlicht verworfen; sie wurden nur am Leben gehalten, damit die Laufzeit einen Rückfallpunkt hat, falls der führende Match scheitert.)

Die Abhängigkeitstabelle im rechten unteren Panel des Posters („② Navigation") fasst zusammen, welche Navigationsformen eine Match-Start-Abhängigkeit erzeugen:

Die beiden Beispiele in §2.5 und §2.6 lassen sich auf eine einzige Regel reduzieren. Gleiches Schicksal macht Absorption sicher: Wenn jeder Kontext am gleichen Pattern-Element auf jedes künftige Prädikat dieselbe Antwort berechnen wird, muss nur der älteste behalten werden. Unterschiedliche Schicksale machen Absorption unsicher: Sobald Prädikate auf kontext-privaten Zustand verzweigen — was genau FIRST und Offset-tragendes LAST tun — repräsentiert jeder aktive Kontext eine Zukunft, die kein anderer wiederherstellen kann; jedes Verwerfen riskiert ein falsches Ergebnis.

Der Planner erkennt diese Unterscheidung zur Übersetzungszeit und entscheidet pro Kontext, ob Absorption greift. Genau deshalb bleibt das Benchmark im Panel ③ des Posters sowohl im Erfolgs- als auch im Misserfolgsfall linear: Ist Absorption sicher, kollabiert die Laufzeit Kontexte; ist sie es nicht, akzeptiert der Planner die Mehr-Kontext-Kosten, statt ein falsches Ergebnis zu riskieren.

Die Benchmark-Zahlen auf dem Poster sind derselbe Algorithmus, in großem Maßstab vorgeführt. Beim Erfolgs-Pattern (A+ B+ C+ D) skalieren sowohl PostgreSQL als auch Trino linear in O(n), sobald ein Match bestätigt ist, und PostgreSQLs Vorsprung — etwa 16× bis 33× — ist überwiegend der JVM-Abstand.

Beim Misserfolgs-Pattern (A+ B+ C+ E) hat Trino keine Absorption und fällt auf O(n²) zurück, weil es jedem potenziellen Match-Start nachjagt; bei 100.000 Zeilen dauert das mehr als fünf Stunden, während PostgreSQL noch in 92 ms fertig wird — ein Geschwindigkeitsvorteil von etwa 217.000×.

Diese Lücke ist kein Engineering-Feinschliff — sie ist exakt die Gleiches-Schicksal/Unterschiedliche-Schicksale-Unterscheidung aus §2.5 und §2.6, angewandt auf jede Zeile jedes potenziellen Match-Starts in der Partition.

2.7 Durchgearbeitetes Beispiel 5 — Wenn SKIP die Absorption deaktiviert

Das vorige Beispiel brach die Absorption von der Datenseite: FIRST in DEFINE ließ jeden Kontext Prädikate unterschiedlich auswerten. Absorption kann auch von der Ausgabeseite brechen, und die AFTER MATCH SKIP-Klausel steuert dies.

Betrachte das Pattern PATTERN (A+) mit DEFINE A AS TRUE über fünf Zeilen, die alle A matchen. Unter der Voreinstellung AFTER MATCH SKIP PAST LAST ROW findet der Matcher den längsten Match ab der frühesten Zeile und springt dann darüber hinaus; jeder Kontext, der innerhalb dieses Matches startete, wird implizit als redundant verworfen — genau die Situation, für die Absorption gedacht ist. Die Ausgabe ist ein einziger Match, Zeilen 0–4, und die Laufzeit benötigt nur einen aktiven Kontext.

Wechsle den Skip-Modus zu AFTER MATCH SKIP TO NEXT ROW, und der Vertrag ändert sich:

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

Jetzt muss jede potenzielle Startposition separat gemeldet werden, selbst bei Überlappungen. Für dieselben fünf Zeilen ist die Laufzeit verpflichtet, fünf Matches auszugeben: Zeilen 0–4, 1–4, 2–4, 3–4 und 4–4. Keiner davon darf durch „einen längeren, der früher beginnt" ersetzt werden, weil der Standard alle verlangt.

Beachte, dass das Prädikat sich nicht geändert hat. A AS TRUE wertet an jeder Zeile gleich aus, unabhängig davon, welcher Kontext fragt; die Gleiches-Schicksal-Bedingung aus §2.5 ist also weiterhin erfüllt. Was sich ändert, ist die Ausgabeanforderung: Selbst Kontexte mit identischen Zukünften müssen koexistieren, weil sie verschiedenen Ergebniszeilen entsprechen. Der Planner deaktiviert die Context Absorption daher immer, wenn AFTER MATCH SKIP TO NEXT ROW aktiv ist — unabhängig von der DEFINE-Klausel.

§2.6 und §2.7 nebeneinander ergeben das vollständige Bild, wann Absorption scheitert:

Eine der beiden Bedingungen genügt, um die Absorption für die betroffenen Kontexte zu deaktivieren. Greift keine — also Voreinstellung AFTER MATCH SKIP PAST LAST ROW mit DEFINE-Bedingungen, die nur PREV, NEXT oder schlichtes LAST verwenden — kollabiert die Laufzeit auf einen einzigen Kontext pro Pattern-Position und bleibt durchgehend linear.

§3. Design — vom Parser zum Executor

Row Pattern Recognition ist als drei Stufen umgesetzt, die ihre Arbeit über klar definierte Zwischenformen weiterreichen. Der Parser verwandelt SQL-Text in einen Pattern-Baum und eine Liste von DEFINE-Prädikaten; der Planner übersetzt den Baum in ein flaches Array von Pattern-Elementen und entscheidet, welche davon an Context Absorption teilnehmen können; der Executor lässt das Array zeilenweise in einer Dreiphasen-Schleife gegen die Partition laufen. Jede Stufe hat ihre eigene Datenform, und der Großteil der Design-Eleganz liegt an den Übergängen: ein flaches, cache-freundliches NFA, ein Navigationsmodell, das einen einzigen Tuple-Slot wiederverwendet statt einen pro Referenz zu materialisieren, und eine Absorptionsregel, die O(n²)-Speicher zu O(n) macht.

SQL-Text
  │
  │  Parser-Stufe
  ▼    Frame validieren
       Pattern-Baum bauen
       DEFINE typprüfen

Pattern-Baum + DEFINE-Liste
  │
  │  Planner-Stufe
  ▼    Baum optimieren
       in flaches NFA-Array übersetzen
       Absorbierbarkeit entscheiden

Flaches NFA + Absorptionsflags
  │
  │  Executor-Stufe
  ▼    Engine pro Zeile:
       Match → Absorb → Advance

Match-Ergebnis:
  Startzeile, Länge, Erfolg/Misserfolg

Die folgenden Abschnitte arbeiten sich diese Pipeline hinunter. §3.1 behandelt den Parser und die Form des Pattern-Baums; §3.2 die Kompilierung, die den Baum in das flache NFA überführt; §3.3 das Navigationsmodell, mit dem DEFINE-Prädikate auf Nachbarzeilen zugreifen; §3.4 die Behandlung der Match-Grenzen — die SKIP-, INITIAL- und Bounded-Frame-Regeln, die fixieren, wo ein Match beginnt und endet; §3.5 die Dreiphasen-Engine pro Zeile; §3.6 sammelt alle Pruning-Mechanismen, die den Zustandsraum beschränkt halten; und §3.7 zeigt, was die Implementierung in der EXPLAIN-Ausgabe sichtbar macht.

3.1 Parser — den Pattern-Baum bauen

Der Parser erkennt Pattern Recognition am Vorhandensein einer PATTERN-Klausel in einer Window-Spezifikation. Seine erste Aufgabe ist die Frame-Validierung, da RPR Beschränkungen auferlegt, die gewöhnliche Window-Abfragen nicht haben: der Frame-Modus muss ROWS sein (nicht RANGE oder GROUPS), die Start-Grenze muss CURRENT ROW sein, und EXCLUDE-Optionen sind verboten. Es handelt sich um Konformitätsprüfungen, nicht um Optimierungen — RPRs Begriff vom Frame ist die Match-Spanne, und der Standard sieht nicht vor, ihn mit irgendetwas anderem als den gematchten Zeilen zu füllen.

Sobald der Frame die Validierung besteht, baut der Parser aus der PATTERN-Klausel einen Baum aus vier Knotenarten — einer Variablenreferenz, einer Sequenz (Konkatenation), einer Alternation und einer Gruppe (in Klammern gesetztes Teilmuster). Jeder Knoten trägt den Quantor als drei Werte — untere Schranke, obere Schranke (ggf. unendlich) und ein Flag für reluctant-Matching:

Jedes DEFINE-Prädikat wird dann gegen die Spalten der Partition typgeprüft und auf einen booleschen Ausdruck reduziert. Dabei geschehen zwei praktische Dinge. Erstens wird jede von einem DEFINE-Prädikat referenzierte Spalte als Teil der Ausgabeerfordernisse der Abfrage registriert, sodass der Planner diese Spalten bis zur Executor-Stufe weiterreicht, auch wenn die umgebende Abfrage sie nicht selektiert — sonst hätte die Laufzeit nichts, gegen das sie auswerten könnte. Zweitens sind Variablen, die im PATTERN auftreten, aber nie im DEFINE, implizit wahr: sie matchen jede Zeile.

3.2 Kompilierung — vom AST zum flachen NFA

Der Planner überführt den vom Parser gelieferten Baum in die Datenstruktur, die der Executor ausführen wird: ein flaches, indexadressiertes Array von Pattern-Elementen. Die Kompilierung läuft in sechs Schritten ab:

compile(astTree):
  1. AST optimieren
  2. Größe und Tiefe messen
  3. Element-Array allokieren
  4. aus dem AST befüllen
       (next/jump-Pointer setzen)
  5. finalisieren — FIN-Sentinel einrichten
  6. absorptionsfähige Elemente markieren

Die flache Form ist aus einem einfachen Grund gewählt: Der Executor muss das Pattern viele Male pro Partition durchlaufen, und ein zusammenhängendes, indexadressierbares Array ist die günstigste Datenstruktur dafür. Die interessanten Schritte sind 1 und 6 — Schritt 1, weil er bestimmt, wie groß das Array wird, und Schritt 6, weil er entscheidet, ob die Absorptions-Optimierung aus §2.5 überhaupt greift.

AST-Optimierung

Optimierung zahlt sich doppelt aus: einmal in der statischen Elementanzahl des flachen Arrays und nochmals in jeder zur Laufzeit verarbeiteten Zeile. Jede Transformation verkleinert den Zustandsraum, den die Laufzeit aufzählen muss. Der Optimierer wendet acht Umformungsregeln nacheinander an, bis sich der AST nicht mehr ändert:

SEQ-Abflachung

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

Aufeinanderfolgende Variablen zusammenführen

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

Aufeinanderfolgende Gruppen zusammenführen

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

Aufeinanderfolgende ALT zusammenführen

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

Präfix/Suffix-Absorption

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

ALT abflachen & dedupen

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

Quantor-Multiplikation

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

Single-Child-Auspacken

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

Die Quantor-Multiplikation ist die einzige Transformation, die eine Sicherheitsprüfung verlangt: Der Optimierer kollabiert nur in drei sicheren Fällen — beide Quantoren unbeschränkt ((A+)+ → A+), äußerer exakt ((A{2,3}){5} → A{10,15}) oder Kind trivial {1,1} ((A){2,5} → A{2,5}). Andere Kombinationen können Lücken erzeugen, die die flache Form verfehlen würde — z. B. akzeptiert (A{2}){2,3} nur {4, 6}, ein naives A{4,6} würde aber auch 5 akzeptieren — daher lässt der Optimierer sie unverändert.

Element-Form

Jedes Element des flachen Arrays steht für eine einzelne Position im Pattern. Es gibt fünf logische Arten: eine Variablenreferenz (die einzige Art, die eine Zeile konsumiert); Group-Begin- und Group-End-Marker, die ein in Klammern gesetztes Teilmuster öffnen und schließen; einen Alternation-Marker, der eine Liste von Zweigen anführt; und einen Finish-Marker am Ende des Patterns.

Jedes Element trägt zudem eine Tiefe (seine Gruppen-Schachtelungsebene), den Quantor (Min- und Max-Wiederholungszahl, ggf. unendlich) und zwei Übergangs-Pointer — next, „wohin nach Konsum dieses Elements", und jump, „wohin überspringen" (genutzt von Alternation, um Zweige zu verketten, von Group-Begin, um den Rumpf zu umgehen, wenn der Quantor null erlaubt, und von Group-End, um in den Rumpf zurückzuspringen).

Für PATTERN ((A B)+) sieht das übersetzte Array so aus:

PATTERN ((A B)+) übersetzt zu:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (öffnet Gruppe; jump überspringt
     zu FIN, wenn min = 0)

[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
    (schließt Gruppe; jump läuft zurück)

[4] FIN    Pattern abgeschlossen

Das Pattern wird über next von links nach rechts gelesen, jump übernimmt die nicht-linearen Kanten. Bei idx 3 zeigt der jump des END zurück auf idx 1 — so schleift der unbeschränkte äußere Quantor; bei idx 0 würde der jump des BEGIN über das END hinaus zu idx 4 springen, wenn die Gruppe optional wäre. Die Laufzeit muss zur Laufzeit nie einen Graphen aufbauen — sie folgt einfach diesen beiden Pointern, während sie das Array durchläuft.

Attribute pro Element

Über die Form hinaus trägt jedes Element vier logische Attribute, die das Verhalten der Laufzeit an dieser Position steuern:

Reluctant

Kehrt die Reihenfolge der Quantor-Expansion um. Greedy-Quantoren versuchen „nochmal schleifen" vor „verlassen"; reluctant-Quantoren versuchen „verlassen" zuerst. Bei A+? trägt es die Variable; bei ((…)+?) tragen es BEGIN und END der Gruppe.

Empty-loopable

Wird auf Group-Ends gesetzt, deren Rumpf nullable ist ((A?)*, (A? B?)+, (A | B*)). Sagt der Laufzeit, neben dem normalen Rücksprung einen Fast-Forward-Exit hinzuzufügen, damit der Cycle-Guard legitime Matches in Gruppen mit potenziell leeren Iterationen nicht abtötet.

In-absorbable-region

Markiert jedes Element, das innerhalb einer absorptionsfähigen Region liegt — von der Laufzeit genutzt, um zu verfolgen, ob der aktuelle Zustand noch in sicherem Gebiet ist.

Absorption-comparison-point

Markiert das konkrete Element, an dem Absorptionsvergleiche laufen sollen. Bei einem schlichten A+ liegt er auf der Variable; bei einer unbeschränkten Gruppe wie (A B)+ ausschließlich auf dem Group-End.

Die Trennung zwischen „in-region" und „comparison-point" ist wichtig, weil Absorption nur an Stellen Sinn ergibt, an denen Iterationen abgeschlossen werden. Innerhalb des Rumpfes von (A B)+ ist die Laufzeit mitten in einer Iteration, und der Zähler hat seinen Endwert für diese Runde noch nicht erreicht; ein Vergleich hier hieße, Unvergleichbares zu vergleichen. Der Zustand muss das Group-End erreichen, bevor die Laufzeit entscheiden kann. Das erste Attribut sagt also „du bist noch in absorbierbarem Gebiet"; das zweite sagt „du hast den Vergleichspunkt erreicht — jetzt prüfen".

Absorbierbarkeitsanalyse

Schritt 6 der Kompilierung verleiht der „Gleiches Schicksal"-Regel aus §2.5 ihren Übersetzungszeit-Beleg. Die Entscheidung ist gestaffelt:

isAbsorbable(query):
  if SKIP-Modus != SKIP PAST LAST ROW
      → return false
  if Frame-Ende != UNBOUNDED FOLLOWING
      → return false
  if irgendein DEFINE auf match_start angewiesen
      → return false
  AST durchlaufen und Elemente
  markieren, die einen
  strukturellen Fall erfüllen

Die ersten drei Prüfungen wirken auf Abfrageebene: Sie entsprechen exakt §2.7 (Ausgabeseite: SKIP-Modus), bounded Frame (Grenze bricht Monotonie) und §2.6 (Datenseite: FIRST oder Offset-tragendes LAST in DEFINE). Schlägt eine fehl, setzt die Analyse keine Flags, und Absorption ist abfrageweit deaktiviert. Bestehen alle, lässt der AST-Durchlauf drei strukturelle Formen zu:

Fall 1 — Einfache unbeschränkte Variable

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

Jede Iteration umfasst genau eine Zeile. Der Zähler eines früheren Kontexts ist an jeder gemeinsamen Position stets ≥ dem eines späteren.

Fall 2 — Gruppe fester Länge, äußerer Quantor unbeschränkt

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

Jedes Kind hat min == max, sodass der Rumpf semantisch seiner ausgerollten {1,1}-Form entspricht — (A B{2})+ verhält sich wie (A B B)+. Jede Iteration konsumiert eine feste Zeilenanzahl; die Zähler-Dominanz gilt weiterhin.

Fall 3 — Gruppe, deren Rumpf mit einer unbeschränkten Variable beginnt

(A+ B)+

Die führende unbeschränkte Variable ist selbst absorbierbar (Fall 1) und schirmt frühere Kontexte ab. Die Absorption endet, sobald der Zustand A überschreitet — der Rest des Rumpfes hat keine Monotonie-Garantie, daher werden Flags nur auf A gesetzt.

Die strukturellen Fälle, die diese drei Formen nicht abdecken, sind ebenso lehrreich. A B+ kann mit der aktuellen Regel nicht absorbiert werden, weil das führende A eine Zeile konsumiert, bevor der unbeschränkte Teil beginnt; Kontexte, die eine Zeile auseinander starten, befinden sich daher an unterschiedlichen Positionen innerhalb des unbeschränkten Rumpfes. (Eine geplante Erweiterung „PREFIX absorption", die feste Präfixe über einen Schattenpfad behandelt, ist entworfen und für einen separaten Patch vorgesehen.) Reluctant-Quantoren wie A+? sind konstruktiv ausgenommen: Die Absorptionsregel setzt Greedy-Semantik voraus, in der längere Matches kürzere subsumieren, und reluctant-Matching kehrt diese Richtung um.

Das Ergebnis ist eine Entscheidung pro Element, nicht pro Pattern. Ein einzelner Plan kann Absorption für das führende A+ von Mustern wie (A+ B+ C) oder (A+ B+)+ aktivieren — letzteres ist nichts anderes als Fall 3 auf das führende Element angewandt — und für alles Folgende deaktivieren; die Laufzeit konsultiert bei jedem in Betracht gezogenen Absorptions-Lauf einfach das Comparison-Point-Attribut des Elements, an dem der aktuelle Zustand steht. Sobald ein Zustand in eine nicht-absorbierbare Region eintritt, ist die Absorption für ihn dauerhaft aus — genau das, was §2.5 und §2.6 algorithmisch verlangen.

3.3 Navigation — der 1-Slot-Tuple-Swap

DEFINE-Ausdrücke sind gewöhnliche SQL-Ausdrücke, die gegen eine Zeile ausgewertet werden, dürfen aber PREV, NEXT, FIRST oder LAST enthalten — Referenzen, die auf andere Zeilen zeigen. Die Zeilen selbst sind bereits im Tuplestore des Window gepuffert; was der Executor noch verwalten muss, ist der Tuple-Slot, aus dem die SQL-Ausdrucksmaschinerie liest, denn Spaltenreferenzen im Ausdruck sind zum Plan-Zeitpunkt an einen Slot gebunden. Die Implementierung verwendet für jeden Navigationsaufruf denselben Navigations-Slot wieder: Vor der Auswertung des inneren Ausdrucks wird der Slot eingeswapt und danach wiederhergestellt, sodass der Rest der SQL-Maschinerie nichts davon merkt.

Das Modell, das der Executor sieht, ist klein: Es gibt einen Current-Row-Slot, der die Zeile hält, gegen die der DEFINE-Ausdruck ausgewertet wird, und einen Navigations-Slot, den die Laufzeit vorübergehend auf eine andere Zeile umbiegen kann. Um jeden Navigationsaufruf herum richtet die Laufzeit den Navigations-Slot ein, wertet den inneren Ausdruck so aus, als läse er die aktuelle Zeile, und stellt dann die ursprüngliche Zeile wieder her. Pseudocode:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos außerhalb des gültigen Bereichs:
      return NULL

  current_row_slot sichern
  Zeile bei targetPos
    in current_row_slot laden
  result = eval_inner_expression()
  current_row_slot wiederherstellen
  return result

Der Trick: Es gibt genau einen Slot zum Sichern und Wiederherstellen. Der innere Ausdruck — was immer er ist, einschließlich Arithmetik, Funktionsaufrufen oder anderen Spaltenreferenzen — läuft gegen den geswapten Slot mit demselben Auswertungspfad wie für die aktuelle Zeile. Kein Alternativ-Evaluator, kein Schatten-Slot, keine Tuple-Kopie.

Verbundnavigation wird zum Parse-Zeitpunkt abgeflacht, damit der Swap weiterhin nur einmal stattfindet. PREV(FIRST(price)) wird als zweistufige Navigation erkannt — „springe zur ersten gematchten Zeile, dann eine Zeile zurück" — und als einzelner Navigationsaufruf mit Verbund-Art gespeichert. Die Laufzeit berechnet die Zielposition in zwei Stufen, führt aber nur einen Slot-Swap aus, um die Endzeile zu laden:

compute_target_position(call):

  # relativ zur aktuellen Zeile
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # match-relativ
  FIRST(n):
      return matchStart + n
  LAST(n):
      return lastMatchedRow − n

  # Verbund: match-rel., dann Schritt
  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

  gegen den passenden Bereich validieren
  (Match-Bereich für inneres FIRST/LAST,
   Partition für äußeren Schritt)

Ein Positions-Cache spart das Tuplestore-Holen, wenn mehrere Navigationsaufrufe in demselben DEFINE auf dieselbe Zeile zielen — verbreitet in Ausdrücken wie price > PREV(price) AND volume > PREV(volume), in denen beide Aufrufe auf die Vorzeile auflösen. Der Cache speichert nur „letzte geholte Position", und der Swap selbst bleibt eine einzige Operation.

Die Klassifizierung der Navigationsaufrufe ist der Planner-Beitrag zur Absorptionsentscheidung. Der Planner durchläuft jeden DEFINE-Ausdruck und ordnet jede Variable in einen von zwei Eimern ein, je nachdem, ob alle Kontexte an derselben Zeile dieselbe boolesche Antwort berechnen oder jeder Kontext seine eigene. Der Eimer bestimmt zwei Dinge zur Laufzeit: wie oft die Variable ausgewertet wird (einmal geteilt, oder einmal pro betroffenem Kontext — §3.5 Phase 1), und ob der umgebende Zustand für Context Absorption infrage kommt (§2.5 vs §2.6).

Die Klassifizierung erfolgt zur Plan-Zeit und wird neben jeder DEFINE-Variable abgelegt, sodass die Laufzeit keine Zeit mit der Entscheidung verbringt — sie liest beim Verarbeiten einer Zeile schlicht den Eimer pro Variable.

Retention-Budget

Navigation greift auf Zeilen zu, die die Window-Maschinerie sonst längst weitergestreamt hat. Um diese Zeilen verfügbar zu halten, baut der Executor auf einem Tuplestore auf, der ein gleitendes Fenster jüngerer Zeilen vorhält; die Frage ist, wie breit dieses Fenster sein muss. Der Patch entscheidet zur Übersetzungszeit anhand zweier komplementärer Offsets:

Lookback-Budget

Wie weit ein DEFINE-Aufruf von der aktuellen Zeile aus rückwärts greifen könnte.

Beitragende: PREV, LAST mit Offset, PREV(LAST(...)), NEXT(LAST(...))

Lookahead-from-start-Budget

Wie weit ein DEFINE-Aufruf vom Match-Start des ältesten aktiven Kontexts aus vorwärts (oder bei negativem Wert rückwärts) greifen könnte.

Beitragende: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

Zur Laufzeit setzt der Tuplestore seine Trim-Marke auf die jeweils frühere von zwei Positionen — aktuelle Zeile minus Lookback-Budget, und Match-Start des ältesten aktiven Kontexts plus Lookahead-Budget. Alles davor kann von keinem Navigationsaufruf eines aktiven Kontexts erreicht werden, und der Tuplestore darf es verwerfen. Die zwei Nav Mark-Zähler, die EXPLAIN ausgibt (§3.7) — Lookback und Lookahead — sind die gemessenen Spitzen der beiden Budgets, also die größte Reichweite, die der Executor während der Abfrage in jeweiliger Richtung gebraucht hat.

3.4 Match-Grenzen — SKIP, INITIAL und Bounded Frame

Ein erfolgreicher Match wird als kleines Bündel von Werten aufgezeichnet: ein Gültigkeits-Flag, ein Erfolgs-/Misserfolgs-Flag, die Startzeile des Matches und die Zahl der konsumierten Zeilen. Ist das Gültigkeits-Flag gesetzt, können nachfolgende Anfragen an den Executor — „liegt diese Zeile in einem Match?" — in O(1) durch Inspektion des Bündels antworten. Eine Länge null ist ein echtes Ergebnis, kein Fehler: sie bedeutet, dass das Pattern ohne Konsum einer Zeile gematcht hat, was der Executor von „an dieser Position wurde noch kein Match versucht" unterscheiden muss.

Die AFTER MATCH SKIP-Klausel entscheidet, wo der nächste Match-Versuch beginnt. AFTER MATCH SKIP PAST LAST ROW rückt zur Zeile nach dem Match-Ende und erzeugt die nicht überlappende Ausgabe, die die meisten Abfragen wollen, und ermöglicht die Absorptions-Optimierung.

AFTER MATCH SKIP TO NEXT ROW rückt nur zur Zeile nach dem Match-Start und erlaubt damit überlappende Matches; der Planner deaktiviert die Absorption für den gesamten Plan, wenn dieser Modus aktiv ist.

Die beiden weiteren vom Standard definierten Skip-Ziele — AFTER MATCH SKIP TO FIRST var und AFTER MATCH SKIP TO LAST var — hängen von einer Match-Historie ab, die dieser Patch nicht vorhält. Sie sind in der Grammatik gar nicht vorhanden; der Parser meldet einen generischen Syntaxfehler, falls eines davon angegeben wird.

Dasselbe gilt für SEEK, die Standard-Alternative zu INITIAL. Unter SEEK darf ein Match-Versuch, der bei Zeile R startet, an jeder Zeile zwischen R und dem Frame-Ende erfolgreich sein, nicht nur an R selbst. Der Patch implementiert ausschließlich INITIAL: jeder potenzielle Match ist an einer bestimmten Zeile verankert. Der Parser meldet einen Fehler, falls SEEK verlangt wird. Bounded Frames erhalten eine eigene Behandlung — schreibt der Anwender ROWS BETWEEN CURRENT ROW AND N FOLLOWING statt UNBOUNDED FOLLOWING, kürzt der Executor jeden Kontext, dessen Match die Grenze erreicht hat, durch erzwungenes Mismatch ab, und Absorption wird deaktiviert, da die Grenze die Monotonie-Annahme bricht, auf der die Absorption ruht.

3.5 Die Dreiphasen-Engine pro Zeile

Der Per-Row-Treiber des Executors wird von der umgebenden Window-Maschinerie immer dann aufgerufen, wenn diese wissen muss, ob eine bestimmte Zeile zu einem gematchten Frame gehört. Der Treiber findet oder erstellt den Kontext für die aktuelle Startposition, wertet jedes DEFINE-Prädikat einmal gegen die aktuelle Zeile aus und erzeugt damit ein boolesches Array pro Variable, dann treibt er den NFA um eine Zeile vorwärts. Der Vorwärtsschritt selbst besteht aus drei Phasen in fester Reihenfolge — Match, Absorb, Advance — eingebettet in dieselbe äußere Schleife:

processRow(currentPos):

  # Phase 1 — MATCH (Konvergenz)
  for each context:
      if context überschreitet bounded Frame:
          Mismatch erzwingen (früh abschließen)
          continue
      if matchStartRow weicht von der
         geteilten Auswertungsposition ab:
          match-start-abhängige
          DEFINE-Variablen neu auswerten (§3.3)
      match(context, varMatched)

  # Phase 2 — ABSORB
  if Pattern absorbierbar:
      Flags jedes Kontexts auffrischen
      absorb_contexts()

  # Phase 3 — ADVANCE (Divergenz)
  for each context:
      advance(context, currentPos)

Die Reihenfolge ist keine Stilfrage. Match muss zuerst laufen, weil die Absorption Post-Match-Zähler vergleicht; liefe Absorb vor Match, würden Zustände verglichen, die ohnehin sterben. Advance muss zuletzt laufen, weil es als einzige Phase neue Zustände erzeugt — sie expandiert jeden überlebenden Zustand über Epsilon-Übergänge, bis jeder an einer Variable liegt, die auf die nächste Zeile wartet. Liefe Absorb nach Advance, würden divergierte Nachfolger verglichen, und genau der Punkt, an dem Zustände am klarsten vergleichbar sind, ginge verloren.

Phase 1 — Match

Match ist eine „Konvergenz"-Phase: Zustände überleben mit erhöhtem Zähler oder sterben. Ein subtiler Punkt: Für Variablen in einer absorbierbaren Region führt Match zusätzlich ein Stück Vorwärtsbewegung aus, damit Absorb sauber vergleichen kann. Die Cover-Bedingung greift nur am absorbierbaren Vergleichspunkt — dem END der unbeschränkten Gruppe — sodass Zustände, die gerade Mid-Iteration-Variablen gematcht haben (etwa B in (A B)+), während Match selbst bis zu diesem Vergleichspunkt geführt werden müssen; sonst findet Absorb nichts Vergleichbares und die Optimierung greift nie.

match(context, varMatched):
  for each state in context:
      elem = pattern[state.elemIdx]
      if elem ist keine Variable:
          continue   # Advance behandelt das

      if not varMatched[elem.varId]:
          Zustand verwerfen   # toter Zweig
          continue

      state.counts[elem.depth] += 1

      # Inline-Vorwärtsbewegung, damit
      # die nächste Phase am Vergleichspunkt
      # vergleichen kann statt mitten in
      # der Iteration.
      if elem in-region, aber nicht
         der Vergleichspunkt,
         und Max-Zähler erreicht,
         und elem.next ist ein Group-End:

          die END-Kette ablaufen:
            äußeren Gruppenzähler erhöhen
            state.elemIdx auf END vorrücken
            weiter, solange noch in-region,
              must-exit und next ein END ist
          (stoppt am Vergleichspunkt
           oder an einem noch loopbaren Element)

Der END-Ketten-Lauf macht geschachtelte Gruppen fester Länge absorbierbar. In ((A B){2})+ muss, wenn B sein Max erreicht (B ist {1,1}), der Zähler der inneren Gruppe steigen; erreicht auch dieser sein Max — und schließt damit das innere {2} —, muss der Zähler der äußeren Gruppe ebenfalls steigen, und so fort, bis der Zustand auf dem äußersten Absorptionspunkt landet — dem END der unbeschränkten äußeren Gruppe (dem +). Diese Arbeit in Match zu erledigen, erlaubt es Absorb, gegen Kontexte zu vergleichen, die ihre Post-Iteration-Zähler bereits konsolidiert haben.

Phase 2 — Absorb

Der Absorb-Lauf wandert Kontexte vom jüngsten (Tail) zum ältesten (Head). Für jeden laufenden Kontext, der vollständig absorbierbar ist, scannt er rückwärts nach einem älteren laufenden Kontext, der ihn überdeckt, und gibt den jüngeren frei, falls gefunden. Da Kontexte in Erzeugungsreihenfolge gehalten werden und jede Zeile höchstens einen Kontext erzeugt, bedeuten „neuer" und „älter" tatsächlich „später gestartet" und „früher gestartet".

absorb_contexts():
  for ctx vom Tail rückwärts:
      if ctx fertig
         oder hat irgendeinen
            nicht-absorbierbaren Zustand:
          überspringen
      for older from ctx.prev rückwärts:
          if older fertig
             oder hat keinen absorbierbaren Zustand:
              überspringen
          if covered(older, ctx):
              free(ctx)
              Absorptionslänge protokollieren
              break

covered(older, newer):
  for each state in newer:
      elem = pattern[state.elemIdx]
      if elem ist nicht der Vergleichspunkt:
          return false
      if kein Zustand in older mit:
            gleichem elemIdx
            und isAbsorbable
            und older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Daraus folgen zwei Mikro-Entscheidungen. Die erste: Die Cover-Prüfung lehnt sofort ab, wenn ein Zustand im jüngeren Kontext irgendwo außer an einem Vergleichspunkt sitzt — ein Vergleich an Nicht-Urteilspunkten wäre nicht aussagekräftig.

Die zweite ist das asymmetrische Flag-Paar pro Kontext: has-absorbable-state beantwortet „könnte dieser Kontext einen jüngeren absorbieren?" und ist monoton (geht nur von true→false, wenn Zustände sterben), während all-states-absorbable beantwortet „könnte dieser Kontext absorbiert werden?" und dynamisch ist (kippt zurück auf true, wenn ein nicht-absorbierbarer Zustand entfernt wird). Beide Flags werden in konstanter Zeit vor dem Cover-Scan geprüft, sodass die Absorption ihre vollen Kosten nur auf Kontexten zahlt, die eine reale Chance haben, absorbiert zu werden.

Phase 3 — Advance

Advance ist die „Divergenz"-Phase: Jeder überlebende Zustand wird über Epsilon-Übergänge expandiert, bis jeder Zweig entweder eine Variable erreicht, die auf die nächste Zeile wartet, oder den FIN-Sentinel. Die Expansion ist tiefendurchsuchend, und die Reihenfolge, in der Geschwister-Zweige durchlaufen werden, sorgt dafür, dass die Preferment-Regel des Standards tatsächlich greift — der lexikalisch erste Zweig wird stets zuerst hinzugefügt, und die Deduplizierung beim Einfügen des Zustands verwirft äquivalente spätere Einfügungen still.

advance(context, currentPos):
  alle aktuellen Zustände entnehmen;
  ctx.states von Grund auf neu aufbauen
  for each state in lexikalischer Reihenfolge:
      Visited-Bitmap leeren
      advance_state(state)   # DFS

      # Preferment: erreicht ein DFS FIN,
      # sind verbleibende Zustände weniger
      # bevorzugt und dürfen verworfen werden.
      if FIN erreicht und Zustände verbleiben:
          die übrigen freigeben
          break

advance_state(state):
  über state.elemIdx laufen,
  rekursiv durch:
    ALT-Zweige (in Reihenfolge),
    BEGIN (Gruppe betreten; plus optionaler
           Skip-Pfad bei min = 0),
    END (Rücksprung / verlassen / Fast-Forward —
         siehe unten),
    FIN (matchEndRow festhalten,
         matchedState sichern und spätere
         Kontexte innerhalb des
         Kandidatenbereichs prunen — siehe unten),
  an jeder begegnenden Variable stoppen:
      Zustand zu ctx.states hinzufügen
      (dedupliziert nach elemIdx + counts)

Einen FIN-erreichenden Zustand zu protokollieren tut mehr, als nur den Match-Kandidaten zu markieren. Unter AFTER MATCH SKIP PAST LAST ROW muss der nächste meldbare Match strikt nach dem aktuellen beginnen — sobald ein Kandidat festgehalten ist, wird daher jeder spätere Kontext, dessen Startzeile im Bereich des Kandidaten liegt, sofort verworfen, auch wenn der Kontext, der FIN erreicht hat, per Greedy-Fallback noch nach einem längeren Match suchen mag.

Das Pruning ist sicher, weil — egal wie diese Suche endet (ein längerer Match ersetzt den Kandidaten oder der Kandidat hält stand) — alle gepruneten Kontexte innerhalb eines Bereichs starteten, den der nächste meldbare Match überspringen muss, und daher ohnehin keine eigene Ausgabe liefern könnten.

Dies ist einer von zwei FIN-Zeit-Prunings — das andere, weiter oben in diesem Abschnitt als Teil von Advance beschrieben, verwirft lexikalisch unterlegene Zustände innerhalb desselben Kontexts.

Die kniffligste Logik pro Element steckt im END-Handler. Liegt der Iterationszähler einer Gruppe unter der Untergrenze, muss die Laufzeit zurückspringen; liegt er auf oder über der Obergrenze, muss sie verlassen; dazwischen sind beide Optionen gültig, und die Greediness des Quantors entscheidet, was zuerst probiert wird:

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

  if count < elem.min:
      in den Rumpf zurückspringen
      if elem ist empty-loopable:
          # nullable Rumpf, siehe §3.2
          zusätzlich einen Fast-Forward-
          Zustand klonen, der die Gruppe
          mit erfülltem Count verlässt
          (rettet legitime Matches, die
           der Cycle-Guard sonst töten würde)

  elif count >= elem.max:
      Zähler dieser Tiefe zurücksetzen
      via next verlassen
      (END→END: Zähler des äußeren
       END erhöhen)

  else:
      # min <= count < max: verzweigen
      einen Exit-Zustand bauen
      (Zähler dieser Tiefe zurücksetzen)
      if greedy:
          erst loopen, dann verlassen
          # längere bevorzugen
      else (reluctant):
          erst verlassen
          if Exit FIN erreicht:
              den Loop verwerfen
              # kürzere bevorzugen
          sonst danach loopen

Jeder einem Kontext hinzugefügte Zustand durchläuft eine Deduplizierungsprüfung, die seine Position und Zähler mit der bestehenden Zustandsliste vergleicht. Da Advance Zweige in DFS-Reihenfolge verarbeitet, landet der Zustand des ersten Zweigs jeder Alternation zuerst — und jeder spätere Zweig, der dieselbe Position und dieselben Zähler erzeugt, wird beim Einfügen abgewiesen. Genau das verlangt die Lexikalische-Reihenfolge-Regel aus §2.4, ganz unten in der Laufzeit umgesetzt — ohne separaten Durchlauf.

Empty-loopable Gruppen

Ein subtiler Fall, den die Laufzeit entschärfen muss, ist die nullable Gruppe — eine Gruppe, deren Rumpf null Zeilen matchen kann, weil jedes Kind des Rumpfes selbst optional ist. Muster wie (A?)*, (A? B?)+ und (A | B*) haben diese Eigenschaft: Je nach Daten kann der Rumpf eine Iteration vollenden, ohne irgendeine Zeile zu konsumieren. Das ist im Prinzip in Ordnung, schafft aber eine reale Gefahr für die Epsilon-Expansion des NFA. Erzeugt der Rumpf einen leeren Match, springt das END-Element zu BEGIN zurück, der Rumpf erzeugt erneut einen leeren Match, BEGIN springt zu END usw. Ohne Stopp würde der DFS in Advance niemals enden.

Die Laufzeit stoppt das mit einer Visited-Bitmap (ein Bit pro Pattern-Element), die vor jeder DFS-Expansion eines Zustands geleert wird: Sobald ein Element innerhalb derselben Expansion zum zweiten Mal besucht wird, wird der Pfad aufgegeben. Der Cycle-Guard ist unbedingt und billig, hat aber einen Nebeneffekt — er kann auch Pfade aufgeben, die durch legitime leere Iterationen die Untergrenze erreichen sollten. Nimm (A?){2,3}, ohne dass A irgendwo im Zeilenstrom matcht:

gewünschtes Verhalten:
  Iter 1: A? matcht null Zeilen
          → END, count = 1 (unter min)
  Iter 2: A? matcht null Zeilen
          → END, count = 2 (erfüllt min)
  Verlassen mit Match der Länge null

was der Cycle-Guard alleine tut:
  Iter 1: A? übersprungen → END, count = 1
          → Rücksprung zu BEGIN
  Iter 2: BEGIN bereits besucht
          → DFS bricht ab
  count erreicht min nie
  → Match scheitert (falsch)

Die Lösung wird zur Übersetzungszeit entschieden und zur Laufzeit angewandt. Sieht der Planner eine Gruppe mit nullable-Rumpf, markiert er das END-Element dieser Gruppe als empty-loopable. Zur Laufzeit, wenn der END-Handler aufgrund eines Iterationszählers unterhalb der Untergrenze zurückspringen will, weist die Empty-Loop-Markierung ihn an, neben dem normalen Rücksprung einen zusätzlichen Fast-Forward-Zustand zu klonen:

advance_end (count unter min):

  Primärpfad:
    in den Rumpf zurückspringen
    (hält die Tür offen für einen
     echten, nicht-leeren Match in
     der nächsten Iteration)

  if elem empty-loopable:
    Fast-Forward-Pfad:
      Zähler dieser Tiefe zurücksetzen
      Gruppe via next verlassen,
      verbleibende erforderliche
      Iterationen als leere Matches deklarieren

Die beiden Pfade ergänzen sich. Der primäre Rücksprung fängt den Fall, in dem der Rumpf später noch echte Matches liefern kann — etwa bei (A?){2,3} gefolgt von Daten, in denen A erst auf späteren Zeilen matcht; der Rücksprung erlaubt es der zweiten und dritten Iteration, nicht-leere Matches zu finden. Das Fast-Forward fängt den Fall, in dem der Rumpf nichts produziert: Es umgeht den Cycle-Guard, indem es die Gruppe ganz verlässt und „die übrigen erforderlichen Iterationen sind leer" deklariert; der Match darf mit einem Rumpf der Länge null gelingen. Beide Zustände werden dem Kontext hinzugefügt; welcher sich erfolgreich fortsetzt, gewinnt, und die Deduplizierungsprüfung beim Einfügen verhindert, dass einer der Pfade mehr Zustände als nötig erzeugt.

Über den Cycle-Guard hinaus löst ein weiterer Start-Trick Null-Zeilen-Ergebnisse ganz am Beginn eines Kontexts auf. Der Kontext-Erzeugungsschritt führt an jeder potenziellen Startzeile einen initialen Advance über Epsilon-Übergänge aus — bevor irgendeine Zeile konsumiert wird —, mit einer Position eine Zeile vor dem tatsächlichen Start. Jeder Pfad, der den FIN-Sentinel allein über Epsilon-Übergänge erreicht — ohne eine Zeile zu konsumieren —, erzeugt daher eine End-Position, die kleiner als die Startposition ist; diese Negativ-Span-Koordinate, kombiniert mit der Information, ob FIN tatsächlich erreicht wurde, kodiert den Unterschied zwischen einem leeren Match (Match der Länge null akzeptiert) und einem nicht gematchten Start, ohne ein zusätzliches Flag zu erfordern.

3.6 Wie der Zustandsraum beschränkt bleibt

Die Linearität der Laufzeit ist nicht das Ergebnis einer einzelnen Optimierung. Sie ist der kumulative Effekt eines geschichteten Satzes von Pruning-Regeln, jede gegen eine andere Ursache des Zustandswachstums an einem anderen Punkt im Zyklus pro Zeile. Manche werden zur Übersetzungszeit entschieden und nur zur Laufzeit konsultiert; andere greifen dynamisch. Manche töten einzelne Zustände; andere ganze Kontexte. Die obigen Abschnitte führten jede einzeln im Kontext ein; die folgende Tabelle stellt sie zusammen.

Fehlgeschlagenes Prädikat Match

Variable Zustände, deren DEFINE an der aktuellen Zeile false ergab — tote Zweige.

Inline-END-Ketten-Vorrücken Match

Variablen, die ihren Max-Zähler erreicht haben und sonst den Zustand mitten in der Iteration zurücklassen würden; werden durch Group-Ends fester Länge vorgerückt, damit Absorb am richtigen Punkt vergleichen kann.

Context Absorption Absorb

Jüngere Kontexte, deren Zustände sämtlich von einem älteren Kontext-Zustand mit höherem Zähler überdeckt sind — siehe §2.5 für die konzeptionelle Regel, §3.2 für die Berechtigung zur Übersetzungszeit, §3.5 für die Paarprüfung.

Zustands-Deduplizierung Advance

Zustände, die über verschiedene DFS-Zweige an dieselbe Position mit gleichen Zählern gelangen — nur der erste (lexikalisch früheste) überlebt; spätere Äquivalente werden still verworfen, womit auch die Preferment-Regel umgesetzt ist (§2.4).

FIN-Frühabbruch (innerhalb eines Kontexts) Advance

Zustände, die noch in der DFS-Warteschlange stehen, wenn ein Zweig FIN erreicht — nach lexikalischer Reihenfolge sind die übrigen weniger bevorzugt und dürfen sofort verworfen werden.

Kandidatenmatch-Pruning (kontextübergreifend) On FIN

Andere Kontexte, deren Startzeile innerhalb des Kandidatenbereichs liegt — der Kontext, der FIN erreicht hat, mag noch nach einem längeren Match suchen (Greedy-Fallback), aber unter AFTER MATCH SKIP PAST LAST ROW kann kein Kontext innerhalb des Kandidatenbereichs noch eine meldbare Ausgabe liefern, unabhängig vom Ausgang dieser Suche; er wird sofort gepruned.

Cycle-Guard Advance

Epsilon-Expansionen, die dasselbe Pattern-Element innerhalb desselben DFS erneut besuchen — würden in nullable Gruppen sonst ewig kreisen.

Empty-Loop-Fast-Forward Advance

Legitime Empty-Iteration-Matches, die der Cycle-Guard in nullable Gruppen töten würde — umgeht den Zyklus, indem die Gruppe verlassen wird und verbleibende erforderliche Iterationen als leer erklärt werden.

Bounded-Frame-Cutoff Match

Kontexte, deren Match die nutzerseitig vorgegebene Frame-Obergrenze erreicht hat — werden auf Mismatch gezwungen, damit sie nicht über sie hinausreichen können (§3.4).

Liest man die Einträge nach ihrem Phase-Badge, zeichnet sich der Lebenszyklus eines Kontexts ab: Pruning greift in jeder Zeile in den drei Hauptphasen (Match, Absorb, Advance) und nochmals beim Match-Abschluss (On FIN). Liest man die Beschreibungen, gruppieren sich die Regeln nach Zielen: tote Zweige, redundante Kontexte, äquivalente Zustände, Endlosschleifen und Übergreifen über nutzerseitige Grenzen.

Keine Regel allein würde reichen. Der Cycle-Guard alleine tötete legitime Matches in nullable Gruppen; das Empty-Loop-Fast-Forward alleine stoppte keine unendlichen Epsilon-Schleifen; Absorption alleine konsolidierte zu stark, sobald DEFINE auf den Match-Start verweist; Deduplizierung alleine entfernte nur redundante Zustände, nicht redundante Kontexte. Die Laufzeit bleibt in den relevanten Fällen linear — PATTERN (A+ B+ C+ D) auf 100.000 Zeilen, das Benchmark in Panel ③ des Posters — nur weil jede Schicht das auffängt, was die darüberliegenden übersehen.

3.7 EXPLAIN-Ausgabe

EXPLAIN ANALYZE auf einer RPR-Abfrage liefert NFA-Statistiken, die für gewöhnliche Window-Funktionen nicht erscheinen. Drei Gruppen von Zählern werden neben dem Window-Operator ausgegeben:

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
  (nur wenn die Abfrage FIRST,
   PREV(FIRST(...)) oder NEXT(FIRST(...)) nutzt)

Peak und Total sind direkte Instrumentierung der Laufzeit: wie viele Zustände gleichzeitig je aktiv waren, wie viele über die Lebensdauer der Abfrage erzeugt wurden und wie viele durch Deduplizierung zusammengeführt wurden. Die Match-Längen-Histogramme trennen vier Ergebnisse — erfolgreiche Matches, gescheiterte Match-Versuche, absorbierte Kontexte und Kontexte, die ohne Auswertung gepruned (skipped) wurden — und durch Min/Max/Avg werden Performance-Pathologien auf einen Blick sichtbar: Ein gesunder Lauf zeigt die meisten Kontexte als matched oder absorbed, mit kleinen mismatched-Längen.

Die beiden Nav Mark-Zähler berichten das Tuplestore-Retention-Budget, das §3.3 zur Übersetzungszeit ableitet. Lookback ist die größte Rückwärtsreichweite über PREV, LAST mit Offset und die Verbundformen mit innerem LAST; Lookahead ist die größte Vorwärtsreichweite (oder bei negativem Wert Rückwärtsreichweite), gemessen vom Match-Start des ältesten aktiven Kontexts, beigetragen durch FIRST und die Verbundformen mit innerem FIRST.

Jeder Zähler wird als feste ganze Zahl gedruckt, wenn der Offset konstant ist, als „runtime", wenn der Offset ein nicht-konstanter, je Aufruf auszuwertender Ausdruck ist, und als „retain all", wenn die Laufzeit ein unbeschränktes Budget benötigt. Lookahead wird nur ausgegeben, wenn die Abfrage tatsächlich match-start-relative Navigation nutzt.

Zusammen erlauben diese Zähler, RPR-Performance zu debuggen, ohne gdb an das Backend hängen zu müssen.

Über die Zähler hinaus reproduziert EXPLAIN auch die ursprünglichen PATTERN- und DEFINE-Klauseln getreu — einschließlich reluctant-Quantoren, Gruppenwiederholung und der AFTER MATCH SKIP-Option. Die Implementierung legt einigen Aufwand darauf, diesen Round-Trip stabil zu halten, damit pg_dump und pg_upgrade RPR-Objekte ohne semantische Drift erhalten — die Regression-Suite unter rpr_explain verifiziert das fallweise (siehe §4).

§4. Tests — Coverage Map

Der Patch liefert fünf Regression-Suites, die zusammen jede in §3 beschriebene Schicht abdecken — rund 13.000 Zeilen SQL, jede Suite auf einen anderen Aspekt fokussiert. Die Aufteilung ist beabsichtigt: Parser-Belange, Laufzeit-Korrektheit, Planner-Interaktionen und Ausgabeformatierung in separaten Dateien zu halten, erleichtert die Fehlerlokalisierung und verhindert, dass eine unzusammenhängende Änderung in einer Schicht unbeabsichtigt Tests einer anderen ungültig macht. Die fünf Suites sind:

rpr

End-to-End-Abfragesemantik — realistische Window-Szenarien auf synthetischen Aktiendaten (V-Form, W-Form, aufeinanderfolgende Anstiege, Umkehrungen).

rpr_base

Parser-Schicht — Schlüsselwortakzeptanz, Syntaxformen, Quantoren, Parsing der Navigation, Fehlermeldungen und pg_dump/pg_upgrade-Round-Trip-Stabilität.

rpr_nfa

NFA-Laufzeit — die Dreiphasen-Schleife, Absorption in jeder absorbierbaren Form und Edge-Cases im Kontext-Lebenszyklus.

rpr_explain

Ausgabeformatierung — NFA-Statistik, Pattern-Deparse, Identifier-Quoting, Formatstabilität über Reload.

rpr_integration

Planner-Interaktionen — Schutzmechanismen, die verhindern, dass unzusammenhängende Window-Optimierungen die RPR-Semantik korrumpieren.

4.1 rpr — End-to-End-Szenarien

Die Szenario-Suite ist das öffentliche Gesicht des Testsatzes: Sie nutzt einen synthetischen Aktienkurs-Datensatz mit etwa 1.600 Zeilen und stellt realistische Abfragen — V-Form-Erholung, W-Form (Doppelboden), aufeinanderfolgende Anstiege und Rückgänge, Umkehrungsmuster, Multi-Symbol-Partitionen. Sie ist die einzige Suite, in der Eingaben und Ausgaben wie Abfragen aussehen, die ein Anwender tatsächlich schreiben könnte; die anderen sind bewusst reduktiv und auf jeweils eine Schicht fokussiert.

Weil diese Abfragen alle Schichten kombinieren (Parser, Planner, Executor, EXPLAIN), sagt ein einzelner Fehlschlag in rpr selten, wo der Bug sitzt. Die folgenden vier Suites sind die Bisektion: ein Fehlschlag in rpr plus bestandenes rpr_base schließt den Parser aus; plus bestandenes rpr_nfa grenzt es auf szenariospezifische Datenformen ein; plus bestandenes rpr_integration schließt Planner-Interferenz aus; jede Deparse-Drift zeigt sich in rpr_explain.

4.2 rpr_base — die Parser-Oberfläche

Die Base-Suite ist die größte, und das aus gutem Grund: Sie soll beweisen, dass jedes legale Stück Syntax aus §1.2 tatsächlich geparst wird, jedes illegale Stück aus §1.3 mit einer brauchbaren Fehlermeldung abgewiesen wird und jede akzeptierte Form einen Serialisierungs-Round-Trip übersteht. Der Großteil ist als kleine, fokussierte Snippets gestaltet — eines pro Syntaxmerkmal — statt als lange, realistische Abfragen, weil das Ziel Abdeckung statt Szenariotreue ist.

Die Serialisierungstests verdienen besondere Beachtung. RPR-Objekte (Views, materialisierte Views, pg_dump-Ausgabe) müssen ohne semantische Drift durch die Katalogdarstellung round-trippen — einschließlich Feinheiten wie dem reluctant-Flag eines Quantors oder der genauen Form eines Verbund-Navigationsausdrucks. Eine kleine Menge serialisierungsspezifischer Objekte (die rpr_serial_v*-Views und ihre Untertabellen) wird am Ende des Laufs absichtlich nicht entfernt, sodass die umgebende Regression-Infrastruktur sie aufgreifen und pg_dump sowie pg_upgrade daran ausführen kann. Das übrige Test-Gerüst wird wie üblich abgebaut. So gefangene Bugs (etwa ein reluctant-Flag, das beim Deparse und Re-Parse verlorengeht) treten nur zutage, wenn der Round-Trip Ende zu Ende ausgeübt wird.

4.3 rpr_nfa — die Laufzeit-Engine

Dies ist die Suite, die jeden in §3.5 und §3.6 beschriebenen Mechanismus prüft. Ihre Tests folgen einem konsistenten Muster: eine Eingabetabelle, deren Zeilen explizite boolesche Arrays enthalten, die deklarieren, welche DEFINE-Variablen an jeder Zeile matchen, gepaart mit einem Pattern, das ein bestimmtes Laufzeitverhalten testet. Das Boolean-Array-Idiom entkoppelt den Laufzeittest von der DEFINE-Auswertung — geprüft wird „liefert die NFA-Schleife angesichts der hier matchenden Variablen die erwartete Match-Spanne?", nicht „berechnet der DEFINE-Ausdrucksauswerter diese Booleans korrekt?". Der DEFINE-Auswerter wird an anderer Stelle getestet (rpr_base fürs Parsing, rpr für End-to-End-Verhalten).

Eine typische Test-Fixture sieht so aus — eine Spalte mit Variablennamen-Arrays, in denen jeder Eintrag angibt, welche DEFINE-Variablen an dieser Zeile feuern, und ein Pattern, dessen DEFINE-Klauseln direkt auf diese Namen prüfen:

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

Die Array-Spalte von oben nach unten zu lesen, heißt das Testszenario direkt zu lesen. Die Zeilen 2 und 3 tragen beide Namen — A und B feuern dort beide, sodass der NFA eine echte Wahl hat, wann vom A-Bein auf das B-Bein gewechselt wird. Der erwartete Match (A in den Zeilen 1–3 gefolgt von B in Zeile 4 unter der Greedy-Preferenz des Standards) wird allein durch diese Flags fixiert, ohne irgendeine relevante Ausdrucksauswertung — = ANY ist hier nur die triviale Schicht, die die Array-Spalte gegenüber DEFINE freigibt, nicht das, was der Test prüft. Das gleiche Szenario mit einem numerischen Prädikat (price > PREV(price) usw.) zu schreiben, würde den NFA-Test mit dem Verhalten des Prädikat-Auswerters verschränken; das Array-Idiom hält beides sauber getrennt, und ein Fehlschlag zeigt direkt auf die NFA-Schleife.

Die Absorptions-Abdeckung ist besonders gründlich, weil Absorption die Optimierung ist, die am ehesten still falsche Antworten produziert, wenn sie greift, obwohl sie nicht sollte. Die Tests decken jede Form aus der Fall-Analyse in §3.2 ab:

• einfache unbeschränkte Variable (A+) — der kanonische N-zu-1-Kollaps;
• Gruppen fester Länge ((A B)+, (A B{2})+, drei Ebenen tief geschachtelt ((A (B C){2}){2})+);
• führende unbeschränkte Variable mit festem Suffix (A+ B) — nur das führende A+ trägt Absorptionsflags, das Suffix nicht;
• Absorption pro Zweig in einer Alternation (B+ C | B+ D);
• mehrere unbeschränkte Variablen (A+ B+) — nur die führende ist absorbierbar;
• reluctant-Quantoren (A+?) — verifiziert von der Absorption ausgeschlossen;
• nicht-führendes unbeschränkt (A B+) — verifiziert ausgeschlossen.

Über Absorption hinaus deckt die Suite den Kontext-Lebenszyklus ab: überlappende Kontexte unter AFTER MATCH SKIP TO NEXT ROW, Aufräumen gescheiterter Kontexte mitten im Stream, Abschluss unvollständiger Kontexte am Partitionsende und Kontexte, denen begegnet wird, nachdem im Head-Kontext bereits ein Match-Kandidat festgehalten wurde. Jeder dieser Punkte entspricht einer konkreten Pruning-Regel aus §3.6, und die Tests sind so geschrieben, dass sie laut scheitern, wenn die Regel falsch greift (sei es, weil redundante Kontexte aktiv bleiben, sei es, weil ein Kontext getötet wird, der hätte ausgeben sollen).

4.4 rpr_explain — Ausgabestabilität

Die EXPLAIN-Ausgabe ist Teil des nach außen sichtbaren Vertrags — Drittwerkzeuge (psql-Autovervollständigung, Monitoring-Dashboards, Log-Scraper) parsen sie, und kosmetisch wirkende Änderungen können sie brechen. Die rpr_explain-Suite prüft drei Dinge:

• NFA-Zähler erscheinen an der richtigen Stelle — die Per-WindowAgg-Statistik (peak/total/merged states, peak/total/pruned contexts, Längenhistogramme für matched/mismatched/absorbed/skipped, Nav Mark Lookback und — wenn match-start-relative Navigation genutzt wird — Nav Mark Lookahead) erscheint vollständig unter EXPLAIN ANALYZE mit den dokumentierten Labels.
• Pattern werden korrekt deparset — jede Quantorform inklusive reluctant- und bounded-Varianten; jede Alternation; jede Gruppe; jede AFTER MATCH SKIP-Form; INITIAL; Navigationsaufrufe mit Offsets; Verbundnavigation. Der deparste Text muss unverändert durch den Parser zurück round-trippen.
• Identifier-Quoting ist korrekt — Pattern-Variablen und DEFINE-Ausdrücke werden mit denselben Quoting-Regeln wie gewöhnliche SQL-Identifier ausgegeben, damit ungewöhnliche Variablennamen die pg_dump-Ausgabe nicht brechen.

Wie rpr_base lässt diese Suite ihre Objekte am Laufende absichtlich stehen, damit die Abdeckung von pg_dump und pg_upgrade auch die Explain-seitigen Artefakte umfasst.

4.5 rpr_integration — Planner-Interaktionen

Der PostgreSQL-Planner hat viele Optimierungen, die auf Window-Abfragen wirken — Frame-Kanonisierung, Run-Condition-Pushdown, Deduplizierung identischer Windows, Projektion ungenutzter Ausgaben, Inverse Transitionen für Moving-Aggregates — und jede davon wurde ohne Rücksicht auf RPR entworfen. Die meisten sind unsicher, wenn ein Window eine PATTERN-Klausel hat: Der Frame ist Teil des Match-Vertrags, die Match-Ausgabe ist nicht mehr offensichtlich monoton, und zwei Windows mit gleicher Spezifikation, aber unterschiedlichen DEFINEs liefern echt unterschiedliche Ergebnisse. Die Integration-Suite prüft, dass jede dieser Optimierungen für RPR-Windows korrekt deaktiviert oder umgangen wird:

Frame-Kanonisierung

Der Planner schreibt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING für monotone Aggregate normalerweise zu ROWS UNBOUNDED PRECEDING um. RPRs Frame ist die Match-Spanne, kein Aggregations-Window, und muss wörtlich erhalten bleiben.

Run-Condition-Pushdown

Ein monotones WHERE-Filter auf der Ausgabe einer Window-Funktion kann normalerweise als Stopp-Bedingung in den Window-Operator gepusht werden. Bei RPR würde das Pattern-Matching dadurch vorzeitig abgebrochen und Matches möglicherweise mitten in der Verlängerung abgeschnitten.

Window-Deduplizierung (RPR vs. Non-RPR)

Zwei Windows mit identischer ORDER BY und identischem Frame würden normalerweise zu einem zusammengeführt. Ein RPR-Window und ein Non-RPR-Window können nie Zustand teilen, weil die RPR-Seite Match-Ergebnisse trägt.

Window-Deduplizierung (unterschiedliches DEFINE)

Zwei RPR-Windows mit demselben PATTERN, aber unterschiedlichen DEFINE-Klauseln liefern unterschiedliche Matches und müssen getrennt bleiben, obwohl ihre strukturelle Form identisch ist.

Projektion ungenutzter Ausgaben

Selbst wenn die umgebende Abfrage die Per-Row-Ausgabe des Windows nie liest, darf das RPR-Window nicht entfernt werden: Die Seiteneffekte des Pattern-Matchers (welche Zeilen in welchem Match liegen) speisen Reduced-Frame-Berechnungen anderswo im Plan.

Inverse Transitionen für Moving-Aggregates

Window-Aggregate mit Inverse-Transition-Funktion können normalerweise inkrementell ausgewertet werden, wenn der Frame wandert. RPRs Reduced Frame ist kein gleitendes Fenster; der Inverse-Transition-Pfad würde falsche Ergebnisse liefern.

Das Muster über alle diese Tests ist gleich: Jeder liefert eine Non-RPR-Baseline, die die Optimierung auslöst (und per EXPLAIN bestätigt, dass sie angewandt wird), und führt dann eine strukturell ähnliche RPR-Abfrage aus und prüft, dass die Optimierung nicht angewandt wird. Beide Hälften zusammen belegen, dass der Schutz im Planner echte Arbeit leistet und nicht einfach jede Abfrage ungeprüft durchwinkt.

Diese Suite ist auch der Grund, warum §3.4 kurz ist. Die „Match-Grenzen"-Mechanismen — Reduced Frame, SKIP, INITIAL, Bounded-Frame-Cutoff — werden anderswo operativ getestet; was rpr_integration prüft, ist, dass keine andere Optimizer-Stufe sie auf dem Weg dorthin manipuliert. Ein bestandenes rpr_integration erlaubt es den übrigen Suites, darauf zu vertrauen, dass ihre Eingaben den Executor unverfälscht erreichen.