Row Pattern Recognition Dybdegående gennemgang

§1. Standarden, delmængden og de åbne spørgsmål

1.1 Standardens omfang

Row Pattern Recognition blev indført i SQL ved ISO/IEC 9075-2:2016 og er beskrevet i ledsagedokumentet ISO/IEC 19075-5:2021 (Del 5, "Row Pattern Recognition").

Standarden definerer to overflader til det samme underliggende maskineri. Feature R010 placerer en MATCH_RECOGNIZE-klausul i FROM-listen for at producere en afledt tabel; feature R020 samler den samme mønsterlogik i en WINDOW-specifikation for at producere window-funktion-output. De to overflader deler hovedparten af deres syntaks og hele deres semantik, men de er funktionelt adskilte indgangspunkter — en database kan implementere en af dem eller begge.

Patch-serien, der diskuteres her, implementerer en delmængde af kun R020; table-clause-formen er bevidst uden for omfanget.

R020-overfladen er lille, men udtryksfuld. En forespørgsel knytter et mønster til et vindue ved at tilføje tre klausuler inden i window-specifikationen: PATTERN beskriver et regulært udtryk over navngivne mønstervariabler, DEFINE leverer det booleske prædikat, der identificerer hver variabel, og AFTER MATCH SKIP styrer, hvordan på hinanden følgende matches placeres inden for partitionen.

Valgfrie MEASURES, SUBSET, INITIAL/SEEK og hjælpefunktionen CLASSIFIER() afrunder featuren. (Standardens MATCH_NUMBER()-funktion hører kun til R010-overfladen — 19075-5 §6.3.3 (6) udelukker den specifikt fra R020.)

Patchen dækker nok af dette vokabular til at få ikke-trivielle forespørgsler til at fungere, men stopper kort før flere konstruktioner, hvis implementering afhænger af infrastruktur, der endnu ikke er bygget.

Resten af dette afsnit opdeler standardens vokabular i det, patchen allerede understøtter, og det, den med vilje overlader til senere. Listerne nedenfor afspejler den aktuelle tilstand af patch-serien.

1.2 Implementerede features

Det implementerede vokabular er tilstrækkeligt til at udtrykke de kanoniske V-form-, W-form- og omvendingsmønstre, der overhovedet motiverer row pattern recognition. Det dækker også enhver standardkvantor — inklusive alle syv tilbageholdende varianter *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — samt de fire navigationsprimitiver, som DEFINE-betingelser har brug for for at sammenligne tilstødende rækker.

PATTERN-klausul

Definerer rækkemønsteret inden i en window-specifikation.

Regex: + * ? |

Standardkvantorer og alternation.

Regex: ( ) gruppering

Parentesserede undermønstre.

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

Begrænsede gentagelsesantal.

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

Alle syv tilbageholdende (non-greedy) varianter, som standarden definerer (udelukket fra absorptionsoptimering).

DEFINE-klausul

Booleske betingelser, der identificerer hver mønstervariabel.

Universel rækkemønster-variabel

Ukvalificerede kolonnereferencer i DEFINE (f.eks. blot Price) løses til den aktuelle række, jf. 19075-5 §4.10/§4.16.

PREV, NEXT (med offset)

Når n rækker før/efter den aktuelle række (standard 1); det indre argument er et vilkårligt værdiudtryk, der evalueres på den navigerede række.

FIRST, LAST (med offset)

Når en match-relativ række; FIRST(expr, n) peger på rækken n efter match-start, LAST(expr, n) rækken n før den seneste match-række.

Sammensat navigation (fire former)

Ydre PREV/NEXT-trin lagt oven på en indre FIRST/LAST: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — både det indre og ydre trin accepterer deres eget offset.

INITIAL

Mønstermatches skal starte ved den aktuelle række (standard).

AFTER MATCH SKIP PAST LAST ROW

Standardspring-tilstand; berettiget til kontekstabsorption.

AFTER MATCH SKIP TO NEXT ROW

Tillader overlappende matches; deaktiverer absorption.

1.3 Ikke implementeret

De features, der endnu ikke er implementeret, falder i tre løse grupperinger. Den første — og langt den største — er familien af konstruktioner centreret omkring MEASURES: selve MEASURES-klausulen, SUBSET, CLASSIFIER(), mønsterkvalificerede kolonnereferencer såsom B.price og mønsterkvalificeret navigation såsom LAST(B.price) eller PREV(B.price).

Disse er ikke uafhængige huller, men snarere forskellige syn på et enkelt manglende stykke: executoren ville være nødt til at bevare en per-match-historik — en optegnelse for hver række i matchet over, hvilken mønstervariabel den blev mappet til — og ingen af disse konstruktioner har en meningsfuld definition uden den. CLASSIFIER() læser variabelnavnet ud af den optegnelse; B.price læser pris-kolonnen for de rækker, hvis optegnelses­indgang siger B; LAST(B.price) går igennem den samme mængde rækker og vælger den sidste; SUBSET U = (A, B) definerer en virtuel variabel, der aggregerer over begge buckets; og MEASURES evaluerer udtryk som AVG(U.Price) ved hjælp af præcis den aggregering.

Den nuværende executor evaluerer DEFINE-prædikater række for række, men registrerer ikke de resulterende variabeltildelinger nogen steder — der er intet at forespørge på senere. At bygge historik-infrastrukturen er derfor en forudsætning for hele gruppen; de enkelte features falder ud som små projektioner, når optegnelserne eksisterer.

Den anden gruppering vedrører alternative skip-mål: AFTER MATCH SKIP TO label, AFTER MATCH SKIP TO FIRST var og AFTER MATCH SKIP TO LAST var. Disse afhænger også af match-historik, da executoren skal kunne pege på en specifik mærket række inden i det seneste match.

De resterende elementer er en heterogen hale: SEEK-nøgleordet (alternativet til INITIAL), det tomme mønster (), eksklusionsformen {- … -} og den ordens-uafhængige PERMUTE-operator.

MEASURES

Navngivne per-match-output-udtryk, fx MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; i R020 eksponeret via OVER som en window-funktion. Accepterer FINAL/RUNNING-nøgleordene (19075-5 §5.4), som i R020 kollapser til samme værdi, da measures altid evalueres på den sidste række af matchet (19075-5 §6.9 (3)).

SUBSET

Navngivne foreninger af mønstervariabler, fx SUBSET U = (A, B, C). Anvendelig overalt, hvor en mønstervariabel kan refereres — MEASURES, mønsterkvalificerede referencer i DEFINE, CLASSIFIER(U) — som alle kræver match-historik.

CLASSIFIER()

Returnerer hvilken mønstervariabel en given række blev matchet som. Defineret for både DEFINE og MEASURES (19075-5 §5.9); svaret på enhver række er det variabelnavn, der er registreret i match-historikken for den række.

Mønsterkvalificeret kolonnereference

Bart B.price i DEFINE eller MEASURES — værdien af kolonnen fra den række, der er mappet som den navngivne variabel.

Mønsterkvalificeret navigation

Begrænser navigation til rækker matchet som en navngiven variabel, fx LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

Match kan starte hvor som helst i vinduet (vs. INITIAL).

AFTER MATCH SKIP TO label

Spring til en mærket række.

AFTER MATCH SKIP TO FIRST var

Spring til den første række matchet som den navngivne variabel.

AFTER MATCH SKIP TO LAST var

Spring til den sidste række matchet som den navngivne variabel.

Regex: {- -}

Eksklusion — fjerner matchede rækker fra per-match-output.

Regex: ()

Tomt mønster — matcher den tomme sekvens.

PERMUTE(...)

Ordens-uafhængig matching på tværs af angivne variabler.

Aggregatfunktioner i DEFINE

Aggregater såsom SUM, AVG, COUNT er ikke tilladt i DEFINE-prædikater. Standarden tillader dem som løbende aggregater over det delvise match (per-række-evaluering mod rækker, der allerede er mappet til en variabel), hvilket afhænger af den samme per-match-historik, som MEASURES/CLASSIFIER() kræver.

Yderligere fire punkter er værd at bemærke her, da de er nemme at forveksle med udeladelser.

Det første er, at mønsterankrene ^ og $ ikke er tilladt med RPR i WINDOW-klausulen af selve standarden (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; med den underliggende definition i 19075-5 §4.14.1); deres fravær er overholdelse, ikke et hul.

Det andet er, at MATCH_NUMBER() tilsvarende er udelukket fra R020 af standarden (19075-5 §6.3.3 (6) og 19075-5 §6.9 (1)) — den er kun en del af R010-overfladen, og dens fravær her er igen overholdelse snarere end en manglende feature.

Det tredje er en række strukturelle forbud, som standarden pålægger R020 (19075-5 §6.17): row pattern recognition kan ikke være indlejret inden i en anden row pattern recognition; MEASURES og DEFINE må ikke indeholde ydre referencer; underforespørgsler inden i MEASURES eller DEFINE må ikke referere til row pattern-variabler; og RPR må ikke anvendes inden i en rekursiv forespørgsel.

Det fjerde er, at MATCH_RECOGNIZE selv — Feature R010, table-clause-overfladen af det samme maskineri — er uden for omfanget af denne patch. Hvorvidt PostgreSQL i sidste ende tilføjer R010, vil være et spørgsmål for en fremtidig serie, ikke et mål for denne.

§2. Eksempler — sådan kører det rent faktisk

Eksemplerne i dette afsnit bygges op trinvist. Vi starter med den begrebsmæssige grund til, at row-pattern matching er reelt forskellig fra string-pattern matching, introducerer derefter de fire navigationsfunktioner, der gør DEFINE-betingelser interessante, og gennemgår til sidst tre ende-til-ende-spor: et enkelt match (NFA-bevægelse), kontekstabsorption i det lette tilfælde og tilfældet, hvor absorption bliver usikker.

Den interne mekanisme, der gør navigation billig — 1-slot tuple-swap — hører til executorens design og er dækket i næste afsnit, ikke her.

2.1 Hvorfor rækkemønstre adskiller sig fra tekstmønstre

Et tekst-regulært udtryk matcher en strøm af tegn, og på enhver position er der præcis ét symbol at overveje. Køretidsspørgsmålet — "er det aktuelle symbol lig med 'A'?" — har et enkelt ja/nej-svar. Backtracking-automater udnytter dette: højst én gren overlever pr. tegn, og prisen for tvetydighed betales ved at genlæse inputtet.

Et rækkemønster er anderledes på en fundamental måde. En række er ikke et enkelt symbol; det er en tuple af kolonner, der evalueres mod en mængde af booleske prædikater, DEFINE-betingelserne. To prædikater kan være sande på samme række samtidig, og intet i standarden siger, at de skal være gensidigt udelukkende. Betragt:

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

En række med price = 150, volume = 2000 opfylder både A og B, men ikke C. Mønstermatcheren kan ikke kollapse dette til en enkelt tilstand — to mønstervariabler er levende, og ethvert mønsterelement, der navngiver en af dem, kan rykke frem. NFA'en skal derfor bære flere samtidige tilstande pr. partitionsrække, ikke én.

Denne enkelte observation driver resten af arkitekturen. Eksekveringstilstanden er en liste af kontekster, hver kontekst er en liste af tilstande, og på hver række spørger køretiden hver tilstand: "givet de variabler, der er sande her, hvor kan jeg gå hen?" De gaffelpunkter, der opstår, er årsagen til, at køretiden har brug for flere lag af beskæring — tilstandsdeduplikering inden for en kontekst, absorption på tværs af kontekster og de andre regler, der gennemgås i §3.6 — uden hvilke antallet af levende tilstande og kontekster vokser med partitionen, og mønstermatching bliver superlineær.

2.2 Navigationsfunktioner

DEFINE-betingelser, der kun refererer til den aktuelle række, er begrænsede; næsten ethvert interessant mønster har brug for at sammenligne den aktuelle række med sine naboer eller med de rækker, der allerede er accepteret tidligere i matchet. Standarden leverer fire navigationsfunktioner til dette, og patchen implementerer dem alle.

PREV(expr [, n])

Rækken n rækker før den aktuelle række (standard n = 1). Bruges til "i dag vs. i går"-sammenligninger.

NEXT(expr [, n])

Rækken n rækker efter den aktuelle række. Fremad-look-ahead; usædvanlig i window-formen, fordi vinduet er monotont.

FIRST(expr [, n])

Den n'te matchede række i det aktuelle match, talt fra starten. "Sammenlign med den række, der startede dette match."

LAST(expr [, n])

Den n'te seneste matchede række. "Sammenlign med den senest matchede række."

De fire primitiver kan kombineres: PREV og NEXT kan ombryde et FIRST- eller LAST-kald, hvilket giver fire sammensatte former, hvis semantik er "gå til en match-relativ række, og træd derefter en fast afstand væk fra den". Dette er, hvad der tillader et DEFINE-udtryk at læse for eksempel rækken umiddelbart før matchet startede.

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

Træd m rækker tilbage fra matchets n'te række (standard m = 1). "Hvad var værdien lige før dette match begyndte?"

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

Træd m rækker frem fra matchets n'te række. Når længere ind i matchet uden at afhænge af den aktuelle række.

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

Træd m rækker tilbage fra den n'te seneste matchede række. "Sammenlign med en række kort før det seneste match."

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

Træd m rækker frem fra den n'te seneste matchede række.

To praktiske pointer er værd at fremhæve her. For det første kan navigation sammensættes: PREV(FIRST(price)) læser rækken umiddelbart før matchet startede, og patchen understøtter dette. For det andet har navigation konsekvenser for executorens optimeringer. PREV og NEXT er relative til den aktuelle række og altid sikre; FIRST og offset-varianter af LAST er relative til match-grænserne, hvilket interagerer med kontekstabsorption og tvinger planneren til at holde nogle kontekster i live, som den ellers ville kassere. Mekanismen bag denne interaktion er emnet for §2.6.

2.3 Gennemgået eksempel 1 — NFA-bevægelse

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

Mønsteret flades ud til fire elementer:

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

For prisserien 100, 110, 120, 115, 108, 130:

Hovedpointen: ved række 3 opfylder rækken både START (altid sand) og DOWN, men den eneste tilstand, der overlevede række 2, er på DOWN-exit-grenen, så kun UP → DOWN-overgangen tages. Multi-tilstandsnaturen fra §2.1 er synlig som fan-out ved hvert UP-match (tilstand kunne forblive ved UP+ eller rykke frem mod DOWN+). Greedy-præference er "loop igen før exit", så med nok data ville de loopende grene forlænge matchet yderligere; her dør den loopende DOWN ved række 5 (130 ≮ 108), og den tidligere FIN-kandidat (rækker 0–4) — produceret da DOWN afsluttede ved række 4 — færdiggøres som matchet.

Forespørgslens resultat følger direkte af dette spor. Under RPR-semantik evalueres window-funktionerne first_value(price) og last_value(price) kun på den række, der startede matchet — enhver anden række i matchet producerer NULL for disse window-funktioner, da dens reducerede frame er tom. Outputtet for vores data ser derfor ud som tabellen, posteren viser i sit øverste højre panel:

Række 0 er match-start, så dens frame dækker rækker 0–4, og window-funktionerne rapporterer V-formens åbningspris ($100) og bundpris ($108). Rækker 1–4 er inden i matchet, men ikke dets start, så de modtager NULL. Række 5 (pris $130) er uden for ethvert match og modtager ligeledes NULL.

2.4 Gennemgået eksempel 2 — Alternation og leksikalsk orden

(A | B)-formen giver matcheren et valg: på enhver række testes de to alternativer uafhængigt, og et hvilket som helst antal af dem kan matche. Dette er, hvor multi-tilstandsnaturen fra §2.1 bliver synlig inden i en enkelt kontekst — ikke på tværs af kontekster (det er absorption), men langs parallelle grene, som executoren udforsker i takt.

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

Forestil dig en række, hvor prisen både er steget og har overskredet $100 — både UP og HIGH er sande. Hvert alternativ afføder sin egen tilstand: én går langs UP-grenen, én går langs HIGH-grenen. De fortsætter parallelt, indtil DONE opløser dem.

Begge grene producerer et match af samme længde over de samme rækker, og efterlader matcheren med to kandidatstier — én mærket UP, DONE og én mærket HIGH, DONE. Standarden løser dette med leksikalsk orden: blandt alternativerne skrevet i (UP | HIGH) vinder den, der er skrevet først, uanset matchlængde. Fordi UP optræder før HIGH, er den overlevende sti UP, DONE.

Leksikalsk orden er det, der gør CLASSIFIER() veldefineret, når den i sidste ende implementeres — den tillader køretiden at fortælle brugeren "denne række matchede UP, ikke HIGH", selv når begge prædikater var sande. Leksikalsk orden er den primære regel for alternation: en leksikalsk tidligere gren vinder over en leksikalsk senere, selv hvis den leksikalsk senere gren ville producere et længere match, og en leksikalsk senere (muligvis kortere) gren kan stadig vinde, hvis enhver leksikalsk tidligere gren dør før den når FIN. Greedy-længde afgøres inden i en enkelt kvantor — givet to fuldførelser af den samme alternationsgren foretrækker den greedy kvantor flere iterationer.

2.5 Gennemgået eksempel 3 — Kontekstabsorption (samme skæbne)

Det enkleste mønster, der udviser absorption, er PATTERN (A+) med DEFINE A AS TRUE. Enhver række matcher A, og standarden kræver, at matcheren betragter enhver række som en mulig match-start. Naivt betyder dette N kontekster for en N-række-partition. Tag en partition med fem rækker (et hvilket som helst data — prædikatet er konstant sandt):

Hukommelsen vokser fra O(n) til O(1). Absorptionsreglen, der retfærdiggør kassationen, er ligetil, når kvantoren er ubegrænset:

Posterens nederste venstre panel ("① Context Absorption") er præcis denne regel visualiseret over fem rækker.

En subtil, men vigtig pointe gemmer sig i reglen: kassationen er sikker, fordi prædikatet A AS TRUE evalueres til den samme værdi på enhver række uanset hvilken kontekst der spørger. Det samme gælder ethvert prædikat, der kun refererer til den aktuelle række eller en fast offset fra den — inklusive PREV. Næste eksempel skifter til en konkret prisuge ved hjælp af et PREV-baseret prædikat, og §2.6 vil genbruge præcis den uge for at gøre symmetrien mellem sikker og usikker absorption tydelig:

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

Tag handelsugen $100, $108, $112, $116, $110 fra mandag til fredag — fire stigninger efterfulgt af et pludseligt fald. Antag, at C1 starter tirsdag (den første dag, hvor RISE matcher: $108 > $100), og executoren spekulativt også sporer C2 startende onsdag. Hver rækkes RISE-betingelse sammenligner rækkens pris med dens umiddelbare forgænger — en partitionsniveau-kendsgerning, ikke en kontekstniveau-kendsgerning — så de to kontekster er tvunget til at beregne den samme boolean på hver række, de deler:

Historien går i stykker det øjeblik prædikatet begynder at afhænge af hver konteksts egne grænser — og det er, hvad §2.6 handler om.

2.6 Gennemgået eksempel 4 — Når absorption bliver usikker

Antag, at en analytiker ønsker at finde sammenhængende handelsdage, hvor en aktie holdt sig inden for ti dollars af den dag, runden startede — en slags konsolideringsvindue. Mønsteret og DEFINE ser således ud:

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

Betingelsen sammenligner nu den aktuelle rækkes pris med prisen ved starten af den aktuelle runde. To runder, der startede på forskellige dage, har forskellige FIRST(price)-værdier, så to tilstande ved det samme mønsterelement og det samme antal er ikke længere udskiftelige: deres fremtider afhænger af den grænse, som absorption var ved at kassere.

Tag selvsamme handelsuge som i §2.5 — $100, $108, $112, $116, $110 fra mandag til fredag. Køretiden holder igen to kandidatrunder i live samtidig: C1 startede mandag, C2 startede tirsdag (enhver række er en potentiel rundestart under STABLE+).

Under absorption ville C2 være blevet flettet ind i C1 tirsdag — den flettede kontekst beholder kun ét loft, så C2's særskilte syn (loft $118, den fire-dages runde, der først slutter lørdag) er ikke længere genskabeligt fra intern tilstand. C2 skal forblive i live, fordi den er en uafhængig match-kandidat, som køretiden stadig kan få brug for: når C1's match slutter onsdag, må næste forsøg samles op fra en stadig kørende C2 i stedet for at starte forfra. Når et DEFINE-prædikat bærer match-start-afhængighed, deaktiverer planneren derfor preemptivt absorption.

(Når den ledende konteksts match lykkes, kasseres kontekster, der startede inden i dens accepterede spænd — under standard AFTER MATCH SKIP PAST LAST ROW — simpelthen; de holdes kun i live, så køretiden har noget at falde tilbage på, hvis det ledende match fejler.)

Afhængighedstabellen på posterens nederste højre panel ("② Navigation") opsummerer, hvilke navigationsformer der skaber match-start-afhængighed:

De to eksempler i §2.5 og §2.6 reducerer til en enkelt regel. Samme skæbne er det, der gør absorption sikker: hvis enhver kontekst ved det samme mønsterelement vil beregne det samme svar på ethvert fremtidigt prædikat, behøves kun den ældste at blive bevaret. Forskellige skæbner gør absorption usikker: så snart prædikater forgrener sig på kontekst-privat tilstand — hvilket er præcis, hvad FIRST og offset-bærende LAST gør — repræsenterer enhver levende kontekst en fremtid, som ingen anden kontekst kan genskabe, og at kassere nogen af dem risikerer at producere et forkert svar.

Planneren opdager denne sondring ved compile time og beslutter per kontekst, om absorption gælder. Det er også grunden til, at posterens benchmark i panel ③ forbliver lineært i både success- og failure-tilfældene: når absorption er sikker, kollapser køretiden kontekster, og når det ikke er, accepterer planneren multi-kontekst-omkostningen frem for at risikere et forkert svar.

Benchmark-tallene på posteren er den samme algoritme, der udspiller sig i stor skala. På success-mønsteret (A+ B+ C+ D) skalerer både PostgreSQL og Trino O(n), når et match er bekræftet, og PostgreSQL's forspring — cirka 16× til 33× — er for det meste JVM-forskellen.

På failure-mønsteret (A+ B+ C+ E) har Trino ingen absorption og degenererer til O(n²) ved at jagte enhver potentiel match-start; ved 100.000 rækker tager det mere end fem timer, mens PostgreSQL stadig afslutter på 92 ms, en hastighedsforøgelse på cirka 217.000×.

Den forskel er ikke ingeniørmæssig finpudsning — det er præcis samme-skæbne/forskellige-skæbner-sondringen fra §2.5 og §2.6, anvendt på hver række af enhver potentiel match-start i partitionen.

2.7 Gennemgået eksempel 5 — Når SKIP deaktiverer absorption

Det forrige eksempel brød absorption fra data-siden: FIRST i DEFINE fik hver kontekst til at evaluere prædikater forskelligt. Absorption kan også brydes fra output-siden, og AFTER MATCH SKIP-klausulen er det, der styrer det.

Betragt mønsteret PATTERN (A+) med DEFINE A AS TRUE over fem rækker, der alle matcher A. Under standard AFTER MATCH SKIP PAST LAST ROW finder matcheren det længste match, der starter ved den tidligste række, og springer derefter forbi det; enhver kontekst, der startede inden i det match, kasseres implicit som redundant — præcis den situation, absorption er designet til at håndtere. Outputtet er et enkelt match, rækker 0–4, og køretiden behøver kun én levende kontekst.

Skift skip-tilstanden til AFTER MATCH SKIP TO NEXT ROW, og kontrakten ændrer sig:

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

Nu skal enhver potentiel startposition rapporteres separat, selv når matches overlapper. For de samme fem rækker er køretiden forpligtet til at udsende fem matches: rækker 0–4, 1–4, 2–4, 3–4 og 4–4. Ingen af disse kan erstattes af et "længere, der starter tidligere", fordi standarden siger, at brugeren ønsker dem alle.

Bemærk, at prædikatet ikke har ændret sig. A AS TRUE evalueres på samme måde på enhver række uanset hvilken kontekst der spørger, så §2.5 samme-skæbne-betingelsen er stadig opfyldt. Det, der ændrer sig, er output-kravet: selv kontekster med identiske fremtider skal sameksistere, fordi de svarer til forskellige rækker af resultatet. Planneren deaktiverer derfor kontekstabsorption, når AFTER MATCH SKIP TO NEXT ROW er i kraft, uanset DEFINE-klausulen.

At sætte §2.6 og §2.7 side om side giver det fulde billede af, hvornår absorption fejler:

Begge betingelser er nok til at deaktivere absorption for de berørte kontekster. Når ingen af dem er i kraft — standard AFTER MATCH SKIP PAST LAST ROW med DEFINE-betingelser, der kun bruger PREV, NEXT eller bart LAST — kollapser køretiden til en enkelt kontekst pr. mønsterposition og forbliver lineær hele vejen igennem.

§3. Design — fra parser til executor

Row Pattern Recognition er implementeret som tre stadier, der afleverer arbejde gennem veldefinerede mellemformer. Parseren omdanner SQL-tekst til et mønstertræ og en liste af DEFINE-prædikater; planneren kompilerer træet til et fladt array af mønsterelementer og afgør, hvilke af dem der kan deltage i kontekstabsorption; executoren kører arrayet mod partitionen række for række i en trefaset løkke. Hvert stadie har sin egen dataform, og det meste af designets opfindsomhed ligger ved grænserne: en flad NFA, der passer i cachen, en navigationsmodel, der genbruger en enkelt tuple-slot snarere end at materialisere én pr. reference, og en absorptionsregel, der gør O(n²)-hukommelse til O(n).

SQL-tekst
  │
  │  parser-stadie
  ▼    valider frame
       byg mønstertræ
       type-tjek DEFINE

mønstertræ + DEFINE-liste
  │
  │  planner-stadie
  ▼    optimer træet
       kompiler til flad NFA-array
       afgør absorberbarhed

flad NFA + absorptionsflag
  │
  │  executor-stadie
  ▼    per-række-motor:
       Match → Absorb → Advance

match-resultat:
  startrække, længde, succes/fejl

Afsnittene nedenfor går igennem denne pipeline. §3.1 dækker parseren og mønstertræets form; §3.2 dækker kompileringen, der omdanner træet til den flade NFA; §3.3 dækker navigationsmodellen, som DEFINE-prædikater bruger til at kigge på nabo-rækker; §3.4 dækker match-grænse-håndtering — SKIP-, INITIAL- og begrænset-frame-reglerne, der fastlægger, hvor et match starter og slutter; §3.5 er den trefasede per-række-motor; §3.6 samler alle beskæringsmekanismerne, der holder tilstandsrummet begrænset; og §3.7 gennemgår, hvad implementationen eksponerer i EXPLAIN-output.

3.1 Parser — opbygning af mønstertræet

Parseren genkender pattern recognition gennem tilstedeværelsen af en PATTERN-klausul inden i en window-specifikation. Dens første opgave er frame-validering, da RPR pålægger begrænsninger, som almindelige window-forespørgsler ikke gør: frame-tilstanden skal være ROWS (ikke RANGE eller GROUPS), startgrænsen skal være CURRENT ROW, og EXCLUDE-optioner er forbudt. Dette er overholdelseskontroller, ikke optimeringer — RPR's begreb om en frame er match-spændet, og standarden overvejer ikke at fylde det med andet end de matchede rækker.

Når framen består valideringen, omdanner parseren PATTERN-klausulen til et træ bygget af fire slags noder — en variabelreference, en sekvens (konkatenation), en alternation og en gruppe (parentesseret undermønster). Hver node bærer kvantoren som tre tal — en nedre grænse, en øvre grænse (muligvis uendelig) og et flag for tilbageholdende matching:

Hvert DEFINE-prædikat type-tjekkes derefter mod partitionens kolonner og tvinges til et boolsk udtryk. To praktiske ting sker som en del af dette. For det første registreres enhver kolonne refereret af et DEFINE-prædikat som en del af forespørgslens output-krav, så planneren propagerer disse kolonner videre til executor-stadiet, selv hvis den omgivende forespørgsel ikke vælger dem — uden det ville køretiden ikke have noget at evaluere imod. For det andet er variabler, der optræder i PATTERN, men aldrig i DEFINE, implicit sande: de matcher enhver række.

3.2 Kompilering — fra AST til en flad NFA

Planneren omdanner parserens træ til den datastruktur, som executoren vil køre: et fladt array af mønsterelementer adresseret efter indeks. Kompileringen forløber som en seks-trins pipeline:

compile(astTree):
  1. optimer AST'en
  2. mål størrelse og dybde
  3. allokér elementarrayet
  4. fyld fra AST'en
       (tildel next/jump-pegere)
  5. finaliser — opsæt FIN-sentinel
  6. marker absorption-egnede elementer

Den flade form er valgt af en enkel grund: executoren skal traversere mønsteret mange gange pr. partition, og et sammenhængende indeks-adresserbart array er den billigste datastruktur at gå igennem. Trin 1 og 6 er de interessante — trin 1, fordi det afgør, hvor stort arrayet vil være, og trin 6, fordi det afgør, om absorptionsoptimeringen i §2.5 overhovedet aktiveres.

AST-optimering

Optimering betaler sig to gange: én gang i det statiske elementantal i det flade array og igen i hver række behandlet ved køretid. Hver transformation reducerer det tilstandsrum, som køretiden skal enumerere. Optimeringsenheden anvender otte omskrivningsregler i rækkefølge, indtil AST'en stopper med at ændre sig:

SEQ-fladning

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

Sammenflettelse af på hinanden følgende variabler

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

Sammenflettelse af på hinanden følgende grupper

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

Sammenflettelse af på hinanden følgende ALT

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

Præfiks/suffiks-absorption

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

ALT-fladning & dedup

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

Kvantor-multiplikation

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

Enkelt-barn-udpakning

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

Kvantor-multiplikation er den eneste transformation, der kræver et sikkerhedstjek: optimeringsenheden kollapser kun i tre sikre tilfælde — begge kvantorer ubegrænsede ((A+)+ → A+), ydre eksakt ((A{2,3}){5} → A{10,15}) eller barnet trivielt {1,1} ((A){2,5} → A{2,5}). Andre kombinationer kan introducere huller, som den flade form ville misse — fx accepterer (A{2}){2,3} kun {4, 6}, men en naiv A{4,6} ville også acceptere 5 — så optimeringsenheden lader dem være intakte.

Elementform

Hvert element af det flade array repræsenterer en enkelt position i mønsteret. Der er fem logiske slags: en variabelreference (den eneste slags, der forbruger en række); group begin- og group end-markører, der åbner og lukker et parentesseret undermønster; en alternation-markør, der står i spidsen for en liste af grene; og en finish-markør ved slutningen af mønsteret.

Hvert element bærer også en dybde (dets gruppe-indlejringsniveau), kvantoren (et min- og max-gentagelsesantal, muligvis uendelig) og to overgangspegere — next, "hvor man skal gå hen efter at have forbrugt dette element", og jump, "hvor man skal springe hen" (brugt af alternation til at kæde grene sammen, af group begin til at omgå kroppen, når kvantoren tillader nul, og af group end til at loope tilbage til kroppen).

For PATTERN ((A B)+) ser det kompilerede array således ud:

PATTERN ((A B)+) kompilerer til:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (åbner gruppe; jump springer
     til FIN når 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
    (lukker gruppe; jump looper tilbage)

[4] FIN    mønster komplet

Mønsteret læses fra venstre mod højre via next, med jump til at håndtere de ikke-lineære kanter. Ved idx 3 peger END's jump tilbage til idx 1, hvilket er hvordan den ubegrænsede ydre kvantor looper; ved idx 0 ville BEGIN's jump springe forbi END til idx 4, hvis gruppen var valgfri. Køretiden behøver aldrig at konstruere en graf ved køretid — den følger blot disse to pegere, mens den går igennem arrayet.

Per-element-attributter

Ud over form bærer hvert element fire logiske attributter, der dirigerer køretidens adfærd ved den position:

Tilbageholdende

Vender rækkefølgen af kvantor-udvidelse. Greedy-kvantorer prøver "loop igen" før "exit"; tilbageholdende kvantorer prøver "exit" først. Båret af variablen for A+?; båret af gruppens BEGIN og END for ((…)+?).

Tom-loopbar

Sat på group ends, hvis krop er nullable ((A?)*, (A? B?)+, (A | B*)). Fortæller køretiden at tilføje en fast-forward-exit ved siden af det normale loop-back, så cyklus-vagten ikke dræber legitime matches i grupper, der kan producere tomme iterationer.

I-absorberbart-område

Markerer hvert element, der ligger inden i et absorption-egnet område — brugt af køretiden til at spore, om den aktuelle tilstand stadig er i sikkert territorium.

Absorption-sammenligningspunkt

Markerer det specifikke element, hvor absorption-sammenligninger skal køres. For en simpel A+ lander det på variablen; for en ubegrænset gruppe som (A B)+ lander det på group end alene.

Opsplitningen mellem "i-område" og "sammenligningspunkt" har betydning, fordi absorption kun giver mening ved punkter, hvor iterationer lukker. Inden i kroppen af (A B)+ er køretiden midt i en iteration, og antallet har endnu ikke nået sin endelige værdi for den runde; at sammenligne her ville betyde at sammenligne uforenelige værdier. Tilstanden skal nå group end, før køretiden kan beslutte. Den første attribut siger derfor "du er stadig i absorberbart territorium"; den anden siger "du har nået sammenligningspunktet — tjek nu."

Absorberbarhedsanalyse

Trin 6 af kompileringen er det, der giver §2.5's "samme skæbne"-regel dens compile-time-vidne. Beslutningen er lagdelt:

isAbsorbable(query):
  hvis SKIP-tilstand != SKIP PAST LAST ROW
      → returnér false
  hvis frame-slut != UNBOUNDED FOLLOWING
      → returnér false
  hvis nogen DEFINE afhænger af match_start
      → returnér false
  gå igennem AST'en og marker
  elementer, der opfylder
  et strukturelt tilfælde

De første tre tjek er på query-niveau: de svarer præcis til betingelserne §2.7 (output-siden: SKIP-tilstand), begrænset frame (grænse bryder monotonicitet) og §2.6 (data-siden: FIRST eller offset-bærende LAST i DEFINE). Når nogen af dem fejler, sætter analysen ingen flag, og absorption deaktiveres query-bredt. Når de alle passerer, accepterer AST-gennemgangen tre strukturelle former:

Tilfælde 1 — Simpel ubegrænset variabel

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

Hver iteration er præcis én række. En tidligere konteksts antal er altid ≥ en senere kontekst' ved enhver delt position.

Tilfælde 2 — Fast-længde-gruppe, ubegrænset ydre

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

Hvert barn har min == max, så kroppen er semantisk ækvivalent med dens udrullede {1,1}-form — (A B{2})+ opfører sig som (A B B)+. Hver iteration forbruger et fast antal rækker; count-dominans holder stadig.

Tilfælde 3 — Gruppe, hvis krop starter med en ubegrænset variabel

(A+ B)+

Den ledende ubegrænsede variabel er selv absorberbar (Tilfælde 1) og afskærmer tidligere kontekster. Absorption stopper, så snart tilstanden bevæger sig forbi A — resten af kroppen har ingen monotonicitetsgaranti, så flag sættes kun på A.

De strukturelle tilfælde, der ikke er dækket af disse tre former, er lige så lærerige. A B+ kan ikke absorberes af den nuværende regel, fordi den ledende A forbruger en række, før den ubegrænsede del begynder, så kontekster, der starter én række fra hinanden, er på forskellige positioner inden i den ubegrænsede krop. (En opfølgende "PREFIX-absorption"-udvidelse, der håndterer fast-længde-præfikser via en skyggesti, er blevet designet og planlagt til en separat patch.) Tilbageholdende kvantorer som A+? er udelukket pr. konstruktion: absorptionsreglen antager greedy-semantik, hvor længere matches subsumerer kortere, og tilbageholdende matching vender den retning.

Resultatet er en per-element-beslutning snarere end en per-mønster-beslutning. En enkelt forespørgselsplan kan have absorption aktiveret for den ledende A+ i mønstre som (A+ B+ C) eller (A+ B+)+ — sidstnævnte er blot Tilfælde 3 anvendt på dens ledende element — og deaktiveret for alt efter; køretiden konsulterer simpelthen sammenligningspunkts-attributten på den aktuelle tilstands element, hver gang den overvejer et absorptionsgennemløb. Når en tilstand bevæger sig ind i et ikke-absorberbart område, er absorption permanent slået fra for den tilstand — præcis hvad §2.5 og §2.6 har brug for skal være sandt på algoritmisk niveau.

3.3 Navigation — 1-slot tuple-swap

DEFINE-udtryk er almindelige SQL-udtryk evalueret mod en række, men de kan inkludere PREV, NEXT, FIRST eller LAST — referencer, der peger på forskellige rækker. Rækkerne selv er allerede buffret i vinduets tuplestore; hvad executoren stadig skal håndtere, er den tuple-slot, som SQL-udtryksmaskineriet læser fra, da kolonnereferencer inden i udtrykket er bundet til en slot ved plan time. Implementationen genbruger en enkelt navigationsslot for hvert navigationskald: slotten swappes ind, før det indre udtryk evalueres, og gendannes efter, så resten af SQL-udtryksmaskineriet aldrig kender forskel.

Modellen, executoren ser, er lille: der er en current row slot, der holder den række, DEFINE-udtrykket evalueres mod, og en navigation slot, som køretiden midlertidigt kan omdirigere til en anden række. Omkring ethvert navigationskald sætter køretiden navigationsslotten op, evaluerer det indre udtryk, som om det læste den aktuelle række, og gendanner derefter den oprindelige række. Pseudokode:

eval_navigation(call):
  targetPos = compute_target_position(call)
  hvis targetPos er uden for sit gyldige interval:
      returnér NULL

  gem current_row_slot
  hent række ved targetPos
    ind i current_row_slot
  result = eval_inner_expression()
  gendan current_row_slot
  returnér result

Tricket er, at der er præcis én slot at gemme og gendanne. Det indre udtryk — uanset hvad det er, inklusive aritmetik, funktionskald eller andre kolonnereferencer — kører mod den swappede slot ved hjælp af den samme evalueringssti, som det ville for den aktuelle række. Ingen alternativ evaluator, ingen skygge-slot, ingen tuple-kopi.

Sammensat navigation flades ud ved parse time, så swappen stadig sker én gang. PREV(FIRST(price)) genkendes som en to-trins-navigation — "gå til den første matchede række, og træd derefter én række tidligere" — og gemmes som et enkelt navigationskald med en sammensat slags. Køretiden beregner målpositionen i to stadier, men udfører kun én slot-swap for at hente den endelige række:

compute_target_position(call):

  # current-row relativ
  PREV(n):
      returnér currentPos − n
  NEXT(n):
      returnér currentPos + n

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

  # sammensat: match-rel, derefter trin
  PREV(FIRST(n), m):
      returnér (matchStart + n) − m
  NEXT(FIRST(n), m):
      returnér (matchStart + n) + m
  PREV(LAST(n), m):
      returnér (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      returnér (lastMatchedRow − n) + m

  valider mod det relevante interval
  (match-interval for FIRST/LAST indre,
   partitionsinterval for ydre trin)

En positionscache kortslutter tuplestore-hentningen, når flere navigationskald i samme DEFINE peger på den samme række — almindeligt i udtryk som price > PREV(price) AND volume > PREV(volume), hvor begge kald løses til den forrige række. Cachen gemmer kun "sidst hentede position", og selve swappen forbliver én operation.

Klassifikationen af navigationskald er plannerens bidrag til absorptionsbeslutningen. Planneren går igennem hvert DEFINE-udtryk og sorterer hver variabel i én af to spande, baseret på om alle kontekster vil beregne den samme boolean på den samme række, eller hver kontekst vil beregne sin egen. Spanden bestemmer to ting ved køretid: hvor ofte variablen evalueres (én gang delt eller én gang pr. berørt kontekst — §3.5 Fase 1), og om den omgivende tilstand er berettiget til kontekstabsorption (§2.5 vs §2.6).

Klassifikationen udføres ved plan time og gemmes ved siden af hver DEFINE-variabel, så køretiden bruger ingen tid på at beslutte — den læser blot spanden for hver variabel, mens den behandler en række.

Bevaringsbudget

Navigation når ind i rækker, som window-funktion-maskineriet ellers har streamet forbi. For at holde disse rækker tilgængelige er executoren bygget oven på en tuplestore, der bevarer et glidende vindue af nylige rækker; spørgsmålet er, hvor bredt det vindue skal være. Patchen beslutter ved compile time ud fra to komplementære offsets:

Lookback-budget

Hvor langt bagud fra den aktuelle række ethvert DEFINE-kald kan nå.

Bidragsydere: PREV, LAST med offset, PREV(LAST(...)), NEXT(LAST(...))

Lookahead-fra-start-budget

Hvor langt frem (eller bagud, når negativ) fra den ældste levende kontekst' match-start ethvert DEFINE-kald kan nå.

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

Ved køretid sættes tuplestoreens trim-mærke til den af to positioner, der er tidligere — aktuel række minus lookback-budgettet og den ældste levende kontekst' match-start plus lookahead-budgettet. Alt før det mærke kan ikke nås af noget navigationskald i nogen levende kontekst, og tuplestoreen kan frit slippe det. De to Nav Mark-tællere, som EXPLAIN rapporterer (§3.7) — Lookback og Lookahead — er de målte toppe af de to budgetter, det dybeste executoren nogensinde måtte nå i begge retninger gennem forespørgslens forløb.

3.4 Match-grænser — SKIP, INITIAL og begrænset frame

Et succesfuldt match registreres som en lille bundt af værdier: et gyldighedsflag, et succes/fejl-flag, den række, hvor matchet starter, og antallet af rækker, det forbrugte. Når gyldighedsflaget er sat, kan efterfølgende forespørgsler mod executoren — "er denne række inden i et match?" — svare i O(1) ved at inspicere bundtet. En længde på nul er et reelt udfald, ikke en fejl: den repræsenterer et mønster, der matchede uden at forbruge nogen række, hvilket executoren skal skelne fra "intet match er forsøgt på denne position endnu."

AFTER MATCH SKIP-klausulen afgør, hvor det næste match-forsøg starter. AFTER MATCH SKIP PAST LAST ROW flytter til rækken efter match-slutningen, hvilket producerer det ikke-overlappende output, de fleste forespørgsler ønsker, og aktiverer absorptionsoptimeringen.

AFTER MATCH SKIP TO NEXT ROW flytter kun til rækken efter match-starten, hvilket tillader overlappende matches; planneren deaktiverer derfor absorption for hele forespørgselsplanen, når denne tilstand er i kraft.

De to skip-mål, standarden også definerer — AFTER MATCH SKIP TO FIRST var og AFTER MATCH SKIP TO LAST var — afhænger af per-match-historik, som denne patch ikke bevarer. De er slet ikke til stede i grammatikken, så parseren rejser en generisk syntaksfejl, hvis nogen af dem leveres.

Det samme gælder SEEK, specifikationens alternativ til INITIAL. Under SEEK kan et match-forsøg, der starter ved række R, lykkes ved enhver række fra R til frame-slutningen, ikke kun ved R selv. Patchen implementerer kun INITIAL: ethvert potentielt match forankres ved en specifik række. Parseren rejser en fejl, hvis SEEK anmodes om. Begrænsede frames får deres egen behandling — når brugeren skriver ROWS BETWEEN CURRENT ROW AND N FOLLOWING snarere end UNBOUNDED FOLLOWING, kortslutter executoren enhver kontekst, hvis match har nået grænsen, ved at fremtvinge et mismatch, og absorption deaktiveres, fordi grænsen bryder den monotonicitetsantagelse, som absorption hviler på.

3.5 Den trefasede per-række-motor

Executorens per-række-driver påkaldes af det omgivende window-funktion-maskineri, når det har brug for at vide, om en given række hører til en matchet frame. Driveren finder eller opretter konteksten for den aktuelle startposition, evaluerer hvert DEFINE-prædikat én gang mod den aktuelle række for at producere et per-variabel boolsk array, og driver derefter NFA'en frem med én række. Selve forward-trinet er tre faser i fast rækkefølge — Match, Absorb, Advance — pakket ind i den samme ydre løkke:

processRow(currentPos):

  # Fase 1 — MATCH (konvergens)
  for hver kontekst:
      hvis kontekst overskrider begrænset frame:
          fremtving mismatch (færdiggør tidligt)
          continue
      hvis matchStartRow afviger fra
         den delte evalueringsposition:
          gen-evaluer match-start-
          afhængige DEFINE-vars (§3.3)
      match(context, varMatched)

  # Fase 2 — ABSORB
  hvis mønster er absorberbart:
      opfrisk hver konteksts flag
      absorb_contexts()

  # Fase 3 — ADVANCE (divergens)
  for hver kontekst:
      advance(context, currentPos)

Rækkefølgen er ikke et stilistisk valg. Match skal køre først, fordi absorption sammenligner post-match-tællinger; at køre Absorb før Match ville sammenligne tilstande, der er ved at dø. Advance skal køre sidst, fordi det er den eneste fase, der skaber nye tilstande — den udvider hver overlevende tilstand gennem epsilon-overgange, indtil hver enkelt når en variabel, der venter på næste række. At køre Absorb efter Advance ville betyde at sammenligne divergerede efterfølgere og misse det punkt, hvor tilstande er mest rent sammenlignelige.

Fase 1 — Match

Match er en "konvergens"-fase: tilstande overlever enten med et inkrementeret antal eller dør. En subtil pointe er, at for variabler, der sidder i et absorberbart område, udfører Match også en lille mængde fremadrettet fremskridt, så Absorb kan sammenligne rent. Cover-betingelsen affyres kun ved det absorberbare sammenligningspunkt — END af den ubegrænsede gruppe — så tilstande, der lige har matchet mid-iteration-variabler (som B inden i (A B)+), skal gås op til det sammenligningspunkt under selve Match; ellers finder Absorb intet egnet at sammenligne, og optimeringen aktiveres aldrig.

match(context, varMatched):
  for hver state i context:
      elem = pattern[state.elemIdx]
      hvis elem ikke er en variabel:
          continue   # advance håndterer det

      hvis ikke varMatched[elem.varId]:
          drop state   # død gren
          continue

      state.counts[elem.depth] += 1

      # Inline fremad-fremskridt så den
      # næste fase kan sammenligne ved
      # sammenligningspunkts-elementet
      # snarere end mid-iteration.
      hvis elem er in-region men ikke
         sammenligningspunktet,
         og nåede sit max-antal,
         og elem.next er en group end:

          gå END-kæden:
            inkrementer ydre gruppe-antal
            ryk state.elemIdx frem til END
            fortsæt mens stadig in-region,
              must-exit, og next er END
          (stopper ved sammenligningspunktet
           eller ved et stadig loopbart element)

End-kæde-gennemgangen er det, der gør indlejrede fast-længde-grupper absorberbare. I ((A B){2})+, når B når sit max (B er {1,1}), skal den indre gruppes antal inkrementeres; hvis det antal også når sit max — lukker den indre {2} — skal den ydre gruppes antal også inkrementeres, og så videre, indtil tilstanden lander på det yderste absorptionspunkt — END af den ubegrænsede ydre gruppe (+'en). At udføre dette arbejde i Match lader Absorb sammenligne mod kontekster, der allerede har konsolideret deres post-iterations-tællinger.

Fase 2 — Absorb

Absorb-gennemløbet går igennem kontekster fra nyeste (hale) til ældste (hoved). For hver igangværende kontekst, der er fuldt absorberbar, scanner den baglæns efter en ældre igangværende kontekst, der dækker den, og frigør den nyere, hvis fundet. Fordi kontekster holdes i oprettelsesrækkefølge, og hver række opretter højst én kontekst, betyder "nyere" og "ældre" virkelig "startet senere" og "startet tidligere."

absorb_contexts():
  for ctx fra hale baglæns:
      hvis ctx er færdig
         eller har nogen ikke-absorberbar tilstand:
          spring over
      for older fra ctx.prev baglæns:
          hvis older er færdig
             eller har ingen absorberbar tilstand:
              spring over
          hvis covered(older, ctx):
              free(ctx)
              registrer absorptionslængde
              break

covered(older, newer):
  for hver state i newer:
      elem = pattern[state.elemIdx]
      hvis elem ikke er sammenligningspunktet:
          returnér false
      hvis ingen state i older med:
            samme elemIdx
            og isAbsorbable
            og older.counts[depth]
                >= newer.counts[depth]:
          returnér false
  returnér true

To mikro-beslutninger følger af dette. Den første er, at cover-tjekket afviser straks, hvis nogen tilstand i den nyere kontekst sidder andre steder end ved et sammenligningspunkt — at sammenligne ved ikke-bedømmelsespunkter ville ikke være en meningsfuld sammenligning.

Den anden er det asymmetriske flag-par på hver kontekst: has-absorbable-state besvarer "kunne denne kontekst absorbere en nyere?" og er monotont (det kan kun gå sand→falsk, mens tilstande dør), mens all-states-absorbable besvarer "kunne denne kontekst absorberes?" og er dynamisk (det vender tilbage til sandt, når en ikke-absorberbar tilstand fjernes). Begge flag tjekkes i konstant tid, før cover-scanningen overhovedet starter, så absorption betaler sin fulde pris kun på kontekster, der har en reel chance for at blive absorberet.

Fase 3 — Advance

Advance er "divergens"-fasen: hver overlevende tilstand udvides gennem epsilon-overgange, indtil hver gren når enten en variabel, der venter på næste række, eller FIN-sentinellen. Udvidelsen er depth-first, og rækkefølgen, hvori søskendegrene gås, er det, der får standardens preferment-regel til faktisk at træde i kraft — den leksikalsk første gren tilføjes altid først, og deduplikeringstrinnet ved tilstandsindsættelse kasserer stille senere ækvivalente tilføjelser.

advance(context, currentPos):
  træk alle nuværende tilstande ud;
  genopbyg ctx.states fra bunden
  for hver state i leksikalsk orden:
      ryd visited-element-bitmappet
      advance_state(state)   # DFS

      # Preferment: når en DFS når FIN,
      # er resterende tilstande mindre foretrukne
      # og kan kasseres.
      hvis FIN nået og tilstande tilbage:
          frigør resten
          break

advance_state(state):
  gå via state.elemIdx,
  rekursér gennem:
    ALT-grene (i rækkefølge),
    BEGIN (træd ind i gruppe; plus valgfri
           skip-sti hvis min = 0),
    END (loop tilbage / exit / fast-forward —
         se nedenfor),
    FIN (registrer matchEndRow,
         gem matchedState, og beskær
         senere kontekster inden i denne
         kandidats interval — se nedenfor),
  stop ved hver variabel mødt:
      tilføj state til ctx.states
      (dedupliker efter elemIdx + counts)

At registrere en tilstand, der nåede FIN, gør mere end blot at bogmærke kandidatmatchet. Under AFTER MATCH SKIP PAST LAST ROW skal det næste rapporterbare match starte strengt forbi det nuværende — så i samme øjeblik en kandidat registreres, beskæres enhver efterfølgende kontekst, hvis startrække falder inden i kandidatens interval, med det samme, selvom konteksten, der ramte FIN, kan fortsætte søgningen efter et længere match gennem greedy fallback.

Beskæringen er sikker, fordi uanset hvordan den søgning slutter (et længere match erstatter kandidaten, eller kandidaten står), startede alle de beskårede kontekster inden i et interval, som det næste rapporterbare match skal springe forbi, og kunne derfor aldrig producere deres eget output.

Dette er et af to FIN-tids beskæringstrin — det andet, beskrevet tidligere i dette afsnit som en del af Advance, kasserer leksikalsk underordnede tilstande inden i den samme kontekst.

Den vanskeligste per-element-logik bor i END-handleren. Når en gruppes iterationstælling er under den nedre grænse, skal køretiden loope tilbage; når den er ved eller over den øvre grænse, skal den afslutte; ind imellem er begge muligheder gyldige, og kvantorens greediness afgør, hvilken der prøves først:

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

  hvis count < elem.min:
      loop tilbage ind i kroppen
      hvis elem er empty-loopable:
          # nullable krop, se §3.2
          klon også en fast-forward-
          tilstand, der afslutter gruppen
          med count opfyldt
          (redder legitime matches,
           som cyklusvagten ellers
           ville dræbe)

  elif count >= elem.max:
      nulstil counts på denne dybde
      afslut via next
      (END→END: inkrementer ydre
       END's count)

  else:
      # min <= count < max: fork
      byg en exit-tilstand
      (counts på denne dybde nulstillet)
      hvis greedy:
          loop først, derefter exit
          # foretræk længere
      ellers (tilbageholdende):
          exit først
          hvis exit nåede FIN:
              drop loopen
              # foretræk kortere
          ellers loop som nummer to

Hver tilstand tilføjet til en kontekst går igennem et deduplikeringstjek, der sammenligner dens position og tællinger med den eksisterende tilstandsliste. Fordi Advance behandler grene i DFS-rækkefølge, lander tilstanden fra den første gren af enhver alternation først — og enhver senere gren, der producerer samme position og tællinger, afvises ved indsættelse. Dette er præcis, hvad §2.4's leksikalske-orden-regel beder om, implementeret i bunden af køretiden uden et separat gennemløb.

Tom-loopbare grupper

Et subtilt tilfælde, køretiden skal afmontere, er den nullable gruppe — en gruppe, hvis krop kan matche nul rækker, fordi hvert barn af kroppen selv er valgfrit. Mønstre som (A?)*, (A? B?)+ og (A | B*) har alle denne egenskab: afhængigt af dataene kan kroppen fuldføre en iteration uden at forbruge nogen række overhovedet. Det er fint i princippet, men det skaber en reel fare for NFA'ens epsilon-udvidelse. Hvis kroppen producerer et tomt match, looper END-elementet tilbage til BEGIN, kroppen producerer endnu en gang et tomt match, BEGIN looper til END, og så videre. Uden noget til at stoppe det ville Advance's DFS aldrig terminere.

Køretiden stopper det med en visited-element-bitmap (én bit pr. mønsterelement), ryddet før hver tilstands DFS-udvidelse: så snart noget element besøges en anden gang inden for samme udvidelse, opgives den sti. Cyklusvagten er ubetinget og billig, men den har en bivirkning — den kan også opgive stier, der burde nå den nedre grænse gennem legitime tomme iterationer. Tag (A?){2,3} uden at A matcher nogen steder i rækkestrømmen:

ønsket adfærd:
  iter 1: A? matcher nul rækker
          → END, count = 1 (under min)
  iter 2: A? matcher nul rækker
          → END, count = 2 (opfylder min)
  afslut med et nul-længde-match

hvad cyklusvagten gør alene:
  iter 1: A? sprunget over → END, count = 1
          → loop tilbage til BEGIN
  iter 2: BEGIN allerede besøgt
          → DFS afbryder
  count når aldrig min
  → match fejler (forkert)

Rettelsen besluttes ved compile time og handles på ved køretid. Når planneren ser en gruppe, hvis krop er nullable, tagger den den gruppes END-element som empty-loopable. Ved køretid, når END-handleren er ved at loope tilbage, fordi iterationstællingen stadig er under den nedre grænse, fortæller empty-loop-tagget den at klone en yderligere fast-forward-tilstand ved siden af den normale loop-back-sti:

advance_end (count under min):

  primær sti:
    loop tilbage ind i kroppen
    (holder døren åben for et reelt,
     ikke-tomt match i den næste
     iteration)

  hvis elem er empty-loopable:
    fast-forward-sti:
      nulstil denne dybdes count
      afslut gruppen via next,
      idet resterende krævede
      iterationer behandles som tomme matches

De to stier spiller komplementære roller. Den primære loop-back er det, der fanger tilfældet, hvor kroppen stadig har reelle matches at producere senere — for eksempel i (A?){2,3} efterfulgt af data, hvor A kun matcher på senere rækker, er det loop-back, der tillader den anden og tredje iteration at finde ikke-tomme matches. Fast-forward er det, der fanger tilfældet, hvor kroppen aldrig producerer noget: den omgår cyklusvagten ved helt at afslutte gruppen og erklærer "resten af de krævede iterationer er tomme" og lader matchet lykkes med en nul-længde-krop. Begge tilstande tilføjes konteksten; den, der udvides succesfuldt, vinder, og deduplikeringstjekket på indsættelsestidspunktet forhindrer nogen sti i at afføde mere end sin andel af tilstande.

Ud over cyklusvagten disambiguerer endnu et opstartstrick nul-række-udfald ved selve starten af en kontekst. Kontekst-oprettelsestrinnet ved hver potentiel startrække kører en initial advance gennem epsilon-overgange før nogen række forbruges, ved hjælp af en position én række før den faktiske start. Enhver sti, der når FIN-sentinellen alene gennem epsilon-overgange — uden at forbruge en række — producerer derfor en slutposition mindre end startpositionen; den negative-span-koordinat, kombineret med hvorvidt FIN faktisk blev nået, koder forskellen mellem et tomt match (længde-0-match accepteret) og en umatchet start uden at have brug for et separat flag.

3.6 Hvordan tilstandsrummet forbliver begrænset

Køretidens linearitet er ikke resultatet af en enkelt optimering. Det er den kumulative effekt af et lagdelt sæt beskæringsregler, hver enkelt fanger en forskellig årsag til tilstandsrum-vækst på et forskelligt punkt i per-række-cyklussen. Nogle besluttes ved compile time og blot konsulteres ved køretid; andre affyres dynamisk. Nogle dræber individuelle tilstande; andre dræber hele kontekster. Afsnittene ovenfor introducerede hver af dem i kontekst; tabellen nedenfor sætter dem på én side.

Fejlet prædikat Match

Variabel-tilstande, hvis DEFINE evaluerede falsk på den aktuelle række — døde grene.

Inline end-chain advance Match

Variabler, der har ramt deres max-antal og ellers ville efterlade tilstanden mid-iteration; rykket frem gennem fast-længde-gruppe-ender, så absorption kan sammenligne ved det rette punkt.

Kontekstabsorption Absorb

Nyere kontekster, hvis hver tilstand er dækket af en ældre kontekst' tilstand med et højere antal — se §2.5 for den begrebsmæssige regel, §3.2 for compile-time-berettigelsen, §3.5 for per-par-tjekket.

Tilstandsdeduplikering Advance

Tilstande nået via forskellige DFS-grene, der ender på samme position med samme tællinger — kun den første (leksikalsk tidligste) overlever; senere ækvivalente kasseres stille, hvilket også er, hvordan preferment håndhæves (§2.4).

FIN tidlig terminering (inden i kontekst) Advance

Tilstande stadig afventende i DFS-køen, når én gren når FIN — efter leksikalsk orden er alle resterende tilstande mindre foretrukne og kan kasseres straks.

Kandidat-match-beskæring (på tværs af kontekster) On FIN

Andre kontekster, hvis startrække falder inden i kandidatmatchets interval — konteksten, der ramte FIN, kan stadig fortsætte med at søge efter et længere match (greedy fallback), men under AFTER MATCH SKIP PAST LAST ROW kan enhver kontekst inden i kandidatens interval ikke længere producere et rapporterbart output, uanset hvordan den søgning slutter, og beskæres med det samme.

Cyklusvagt Advance

Epsilon-udvidelser, der genbesøger samme mønsterelement inden for samme DFS — ville ellers loope evigt i nullable grupper.

Tom-loop fast-forward Advance

Legitime tom-iterations-matches, som cyklusvagten ville dræbe i nullable grupper — omgår cyklussen ved at afslutte gruppen med resterende krævede iterationer erklæret tomme.

Begrænset-frame-afskæring Match

Kontekster, hvis match har nået den brugerspecificerede frame-øvre-grænse — tvunget til mismatch, så de ikke kan strække sig ud over den (§3.4).

At læse posterne efter deres fase-badge sporer en konteksts levetid: beskæring affyres ved hver række gennem de tre hovedfaser (Match, Absorb, Advance), og igen ved match-fuldførelse (On FIN). At læse beskrivelserne i stedet grupperer reglerne efter, hvad de er rettet mod: døde grene, redundante kontekster, ækvivalente tilstande, uendelige løkker og over-udvidelse forbi brugerpålagte grænser.

Ingen enkelt regel ville være nok i sig selv. Cyklusvagten alene ville dræbe legitime matches i nullable grupper; tom-loop fast-forward alene ville ikke stoppe uendelige epsilon-løkker; absorption alene ville over-konsolidere, når DEFINE refererer til match-start; deduplikering alene ville ikke fjerne redundante kontekster, kun redundante tilstande. Køretiden forbliver lineær i de tilfælde, der betyder noget — PATTERN (A+ B+ C+ D) på 100.000 rækker, posterens panel ③-benchmark — kun fordi hvert lag fanger, hvad lagene ovenover det misser.

3.7 EXPLAIN-output

EXPLAIN ANALYZE på en forespørgsel med RPR eksponerer NFA-niveau-statistik, der ikke er til stede for almindelige window-funktioner. Tre grupper af tællere udsendes ved siden af window-operatøren:

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
  (kun når forespørgslen bruger FIRST,
   PREV(FIRST(...)) eller NEXT(FIRST(...)))

Peak og total er direkte instrumentering af køretiden: hvor mange tilstande der nogensinde var levende samtidig, hvor mange der blev oprettet i forespørgslens levetid, og hvor mange der blev flettet væk ved deduplikering. Match-længde-histogrammerne adskiller fire udfald — succesfulde matches, fejlede match-forsøg, absorberede kontekster og kontekster, der blev beskåret (skipped) uden at blive evalueret — og at rapportere dem med min/max/avg gør ydelses-patologier synlige ved et blik: et sundt run viser de fleste kontekster som enten matched eller absorbed, med mismatched-længder små.

De to Nav Mark-tællere rapporterer tuplestore-bevaringsbudgettet, som §3.3 udleder ved compile time. Lookback er den dybeste baglæns rækkevidde på tværs af PREV, LAST med offset og de sammensatte former med indre LAST; Lookahead er den dybeste fremad (eller baglæns, når negativ) rækkevidde målt fra den ældste levende kontekst' match-start, bidraget af FIRST og de sammensatte former med indre FIRST.

Hver tæller udskrives som et fast heltal, når offsettet er en konstant, "runtime", når offsettet er et ikke-konstant udtryk, der skal evalueres ved hvert kald, og "retain all", når køretiden har brug for et ubegrænset budget. Lookahead udsendes kun, når forespørgslen faktisk bruger match-start-relativ navigation.

Sammen gør disse tællere det muligt at debugge RPR-ydelse uden at vedhæfte gdb til backenden.

Ud over tællerne reproducerer EXPLAIN også trofast de oprindelige PATTERN- og DEFINE-klausuler, inklusive tilbageholdende kvantorer, gruppe-gentagelse og AFTER MATCH SKIP-optionen. Implementationen gør sig umage for at gøre denne round-trip stabil, så pg_dump og pg_upgrade kan bevare RPR-objekter uden semantisk drift — regressionssuiten under rpr_explain verificerer det tilfælde for tilfælde (se §4).

§4. Test — dækningskort

Patchen leveres med fem regressionssuiter, der tilsammen udøver hvert lag beskrevet i §3 — cirka 13.000 linjer SQL, hver suite fokuseret på en forskellig bekymring. Opdelingen er bevidst: at holde parser-bekymringer, køretidskorrekthed, planner-interaktioner og output-formatering i separate filer gør fejl lettere at lokalisere og forhindrer en urelateret ændring i ét lag i utilsigtet at invalidere test i et andet. De fem suiter er:

rpr

Ende-til-ende-forespørgselssemantik — realistiske window-scenarier på syntetiske aktiedata (V-form, W-form, sammenhængende stigninger, vendinger).

rpr_base

Parser-laget — nøgleord-accept, syntaksformer, kvantorer, navigations-parsing, fejlmeddelelser og pg_dump/pg_upgrade-round-trip-stabilitet.

rpr_nfa

NFA-køretid — den trefasede løkke, absorption i hver absorberbar form og kontekst-livscyklus-grænsetilfælde.

rpr_explain

Output-formatering — NFA-statistik, mønster-deparse, identifikator-citering, formatstabilitet på tværs af genindlæsning.

rpr_integration

Planner-interaktioner — vagter, der forhindrer urelaterede window-optimeringer i at korrumpere RPR-semantik.

4.1 rpr — ende-til-ende-scenarier

Scenarie-suiten er det offentlige ansigt af testsættet: den bruger et syntetisk aktiekurs-datasæt på cirka 1.600 rækker og kører realistiske forespørgsler mod det — V-form-genopretning, W-form (double bottom), sammenhængende stigninger og fald, vendingsmønstre, multi-symbol-partitioner. Det er den eneste suite, hvor input og output læser som forespørgsler, en bruger faktisk kunne skrive; de andre er bevidst reduktive, fokuseret på et enkelt lag ad gangen.

Fordi disse forespørgsler kombinerer hvert lag (parser, planner, executor, EXPLAIN), fortæller en enkelt fejl i rpr sjældent hvor fejlen bor. De fire suiter, der følger, er bisektionen: en fejl i rpr plus en bestået rpr_base udelukker parseren; plus en bestået rpr_nfa indsnævrer den til scenarie-specifikke dataformer; plus en bestået rpr_integration udelukker planner-indblanding; og enhver deparse-drift dukker op i rpr_explain.

4.2 rpr_base — parser-overfladen

Base-suiten er den største, og den er størst af en grund: den er ansvarlig for at bevise, at hvert lovligt stykke syntaks i §1.2 faktisk parser, hvert ulovligt stykke i §1.3 afvises med en nyttig fejl, og hver accepteret form overlever en serialiserings-round-trip. Hovedparten af den er formet som små fokuserede uddrag — ét pr. syntaktisk feature — snarere end lange realistiske forespørgsler, fordi målet er dækning snarere end scenarie-realisme.

Serialiseringstestene fortjener særlig opmærksomhed. RPR-objekter (views, materialiserede views, pg_dump-output) skal round-trippe gennem katalogrepræsentationen uden semantisk drift, inklusive subtiliteter som tilbageholdende-flaget på en kvantor eller den nøjagtige form af et sammensat navigations-udtryk. Et lille sæt serialiserings-specifikke objekter (rpr_serial_v*-views og deres bagvedliggende tabeller) efterlades bevidst ved slutningen af kørslen, så den omgivende regressionsinfrastruktur kan samle dem op og udøve pg_dump og pg_upgrade mod dem. Resten af test-stilladset droppes som sædvanligt. Fejl fanget på denne måde (såsom et tilbageholdende flag, der mistes på tværs af deparse og gen-parse) dukker kun op, når round-trippen udøves ende til ende.

4.3 rpr_nfa — køretidsmotoren

Dette er suiten, der udøver hver mekanisme beskrevet i §3.5 og §3.6. Dens test følger et konsistent mønster: en input-tabel, hvis rækker er eksplicitte boolske arrays, der erklærer hvilke DEFINE-variabler der matcher på hver række, parret med et mønster, der prober en specifik køretidsadfærd. Boolean-array-idiomet afkobler køretidstesten fra DEFINE-evalueringsmaskineriet — hvad der testes, er "givet at disse variabler matcher her, producerer NFA-løkken så det forventede match-spænd?" snarere end "beregner DEFINE-udtryksevaluatoren disse booleans korrekt?" DEFINE-evaluatoren testes andetsteds (rpr_base for parsing, rpr for ende-til-ende-adfærd).

En typisk test-fixtur ser således ud — en kolonne af variabelnavn-arrays, hvor hver indgang siger, hvilke DEFINE-variabler der affyres på den række, og et mønster, hvis DEFINE-klausuler tester for de navne direkte:

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

At læse array-kolonnen ned er at læse testscenariet direkte. Rækker 2 og 3 bærer begge navne — A og B affyres begge der, så NFA'en har et reelt valg om, hvor man skal skifte fra A-benet til B-benet. Det forventede match (A på rækker 1–3 efterfulgt af B på række 4 under standardens greedy preferment) er fastlagt af de flag alene, uden nogen udtryksevaluering af betydning her — = ANY er blot det trivielle lag, der eksponerer array-kolonnen til DEFINE, ikke hvad testen udøver. At skrive det samme scenarie med et numerisk prædikat (price > PREV(price) og lignende) ville sammenfiltre NFA-testen med prædikatevaluatorens adfærd; array-idiomet holder de to rent adskilt, og en fejl her peger direkte på NFA-løkken.

Absorption-dækningen er særligt grundig, fordi absorption er den optimering, der mest sandsynligt stille producerer forkerte svar, hvis den aktiveres, når den ikke burde. Test dækker hver form fra §3.2's case-analyse:

• simpel ubegrænset variabel (A+) — den kanoniske N-til-1-kollaps;
• fast-længde-grupper ((A B)+, (A B{2})+, tre-niveau indlejret ((A (B C){2}){2})+);
• ledende ubegrænset variabel med et fast suffiks (A+ B) — kun den ledende A+ bærer absorption-flag, suffikset gør ikke;
• per-gren-absorption inden i en alternation (B+ C | B+ D);
• flere ubegrænsede variabler (A+ B+) — kun den ledende er absorberbar;
• tilbageholdende kvantorer (A+?) — verificeret at være udelukket fra absorption;
• ikke-ledende ubegrænset (A B+) — verificeret at være udelukket.

Ud over absorption dækker suiten kontekst-livscyklussen: overlappende kontekster under AFTER MATCH SKIP TO NEXT ROW, fejlet-kontekst-oprydning midt i strømmen, partitions-slut-færdiggørelse af ufuldstændige kontekster og kontekster mødt efter at et kandidat-match allerede er registreret i hoved-konteksten. Hver af disse afbildes på en specifik beskæringsregel i §3.6, og testene er skrevet til at fejle højlydt, hvis reglen affyres forkert (enten ved at lade redundante kontekster være levende eller ved at dræbe en kontekst, der skulle have produceret output).

4.4 rpr_explain — output-stabilitet

EXPLAIN-output er en del af den brugervendte kontrakt — tredjepartsværktøjer (psql autocompletion, overvågnings-dashboards, log-scrapers) parser det, og ændringer, der ser kosmetiske ud, kan ødelægge dem. rpr_explain-suiten verificerer tre ting:

• NFA-tællere optræder det rette sted — per-WindowAgg-statistikken (peak/total/merged states, peak/total/pruned kontekster, længde-histogrammer for matched/mismatched/absorbed/skipped, Nav Mark Lookback og — når match-start-relativ navigation er i brug — Nav Mark Lookahead) dukker alle op under EXPLAIN ANALYZE med de dokumenterede etiketter.
• Mønstre deparser korrekt — hver kvantor-form, inklusive tilbageholdende varianter og begrænsede former; hver alternation; hver gruppe; hver AFTER MATCH SKIP-form; INITIAL; navigationskald med offsets; sammensat navigation. Den deparsede tekst skal round-trippe tilbage gennem parseren uændret.
• Identifikator-citering er korrekt — mønstervariabler og DEFINE-udtryk udsendes med de samme citerings-regler som almindelige SQL-identifikatorer, så usædvanlige variabelnavne ikke ødelægger pg_dump-output.

Ligesom rpr_base efterlader denne suite bevidst sine objekter ved slutningen af kørslen, så pg_dump- og pg_upgrade-dækning også strækker sig til explain-side-artefakterne.

4.5 rpr_integration — planner-interaktioner

PostgreSQL's planner har mange optimeringer, der opererer på window-forespørgsler — frame-kanonisering, run-condition-pushdown, identisk-window-deduplikering, unused-output-projektion, moving-aggregate inverse transitions — og hver enkelt af dem blev designet uden RPR i tankerne. De fleste af dem er usikre at anvende, når et vindue har en PATTERN-klausul: framen er en del af match-kontrakten, det matchede output er ikke længere monotont på nogen åbenbar måde, og to vinduer med samme spec, men forskellige DEFINE'er, producerer reelt forskellige resultater. Integration-suiten verificerer, at hver af disse optimeringer korrekt er deaktiveret eller omgået for RPR-vinduer:

Frame-kanonisering

Planneren omskriver normalt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING til ROWS UNBOUNDED PRECEDING for monotone aggregater. RPR's frame er match-spændet, ikke et aggregeringsvindue, og skal forblive ordret.

Run-condition-pushdown

Et monotont WHERE-filter på en window-funktions output kan normalt skubbes ind i window-operatøren som en stop-betingelse. For RPR ville dette terminere pattern matching for tidligt, muligvis afskære matches mid-udvidelse.

Window-deduplikering (RPR vs ikke-RPR)

To vinduer med identisk ORDER BY og frame ville normalt blive flettet til ét. Et RPR-vindue og et ikke-RPR-vindue kan aldrig dele tilstand, fordi RPR-siden bærer match-resultater.

Window-deduplikering (forskellig DEFINE)

To RPR-vinduer med samme PATTERN, men forskellige DEFINE-klausuler producerer forskellige matches og skal forblive adskilte, selvom deres strukturelle form er identisk.

Unused-output-projektion

Selv hvis den omgivende forespørgsel aldrig læser vinduets per-række-output, kan RPR-vinduet ikke fjernes: pattern matcherens bivirkninger (hvilke rækker er inden i hvilket match) fodrer reduceret-frame-beregninger andetsteds i planen.

Moving-aggregate inverse transitions

Window-aggregater med en inverse transition-funktion kan normalt evalueres inkrementelt, når framen flytter sig. RPR's reducerede frame er ikke et glidende vindue; inverse transition-stien ville producere forkerte resultater.

Mønsteret på tværs af disse test er det samme: hver leverer en ikke-RPR-baseline, der udløser optimeringen (og verificerer, at EXPLAIN viser, at den anvendes), og kører derefter en RPR-forespørgsel af strukturelt lignende form og verificerer, at optimeringen ikke anvendes. De to halvdele beviser sammen, at vagten i planneren udfører reelt arbejde, ikke godkender enhver forespørgsel uden reel verifikation.

Denne suite er også grunden til, at §3.4 er kort. "Match-grænse"-mekanismerne — reduceret frame, SKIP, INITIAL, begrænset-frame-afskæring — testes operationelt andetsteds; hvad rpr_integration verificerer, er, at intet andet optimeringsstadie pilper med dem på vejen igennem. En bestået rpr_integration er det, der lader resten af suiterne stole på, at deres input når executoren uskadt.