2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition Dybdegående gennemgang

En guidet rundvisning gennem ISO/IEC 19075-5 · SQL R020 i PostgreSQL — hvad vi har bygget, hvad der endnu ikke er skrevet, og hvordan det faktisk kører.

Ledsagedokument til posteren udstillet ved PGConf.dev 2026.
Skim standarden, gå igennem gennemarbejdede eksempler, gennemse designet, og kør derefter en live NFA-simulator med dine egne mønstre.
Diskussion: pgsql-hackers tråd · seneste patch (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

AI-foroversat — fejl mulige.

§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 har betydelige dele af syntaks og semantik til fælles (19075-5 noterer nogle få R020-specifikke forskelle i §6.3.3), 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 klausuler inden i en window-specifikation, hvis frame er ROWS BETWEEN CURRENT ROW AND …: PATTERN beskriver et regulært udtryk over navngivne mønstervariabler, DEFINE leverer det booleske prædikat, der identificerer hver variabel, og den valgfrie AFTER MATCH SKIP (standard PAST LAST ROW) 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; op til 240 forskellige mønstervariabler.
Window-frame
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING eller ROWS BETWEEN CURRENT ROW AND n FOLLOWING med n ≥ 1 (19075-5 §6.10.2); enhver anden frame afvises, og EXCLUDE NO OTHERS er den eneste accepterede eksklusion.
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 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.
Navigationsnavne
PREV, NEXT, FIRST og LAST skrevet som ukvalificerede kald inden i DEFINE betyder altid navigation; en brugerfunktion med samme navn skal skema-kvalificeres dér.
Navigationsargumenter
For PREV, NEXT, FIRST og LAST skal det indre argument indeholde mindst én kolonnereference, og offset skal være en run-time-konstant.
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 FIRST var og AFTER MATCH SKIP TO [LAST] var (bart SKIP TO var betyder SKIP TO LAST var). Disse afhænger også af match-historik, da executoren skal kunne pege på den række, der er mappet til en given variabel inden i det seneste match.

De resterende elementer er en heterogen hale: SEEK-nøgleordet (alternativet til INITIAL), det tomme mønster (), eksklusionsformen {- … -}, den ordens-uafhængige PERMUTE-operator samt aggregatfunktioner og underforespørgsler i DEFINE, som begge i øjeblikket afvises (et variabelkvalificeret aggregat ville også kræve match-historikken).

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 ved enhver række fra den aktuelle række til slutningen af den fulde window-frame (vs. INITIAL).
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 ALL ROWS PER MATCH-output. Den option gælder ikke for vinduer (19075-5 §6.3.3 (4)), så i et vindue er syntaksen tilladt (§6.13), men har intet output at virke på.
Regex: ()
Tomt mønster — matcher den tomme sekvens.
PERMUTE(...)
Ordens-uafhængig matching på tværs af angivne variabler. Nøgleordet genkendes og afvises ("PERMUTE is not supported"); permute kan stadig bruges som navn på en mønstervariabel.
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; et variabelkvalificeret aggregat såsom AVG(B.Price) afhænger af den samme per-match-historik, som MEASURES/CLASSIFIER() kræver, mens et ukvalificeret spænder over alle hidtidige rækker i matchet.
Underforespørgsler i DEFINE
Enhver underforespørgsel i DEFINE afvises. Standarden tillader en, der ikke udfører row pattern recognition og ikke refererer til nogen row pattern-variabel; patchen afviser indtil videre for meget.

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 (patchen går videre og afviser alle underforespørgsler i DEFINE, som angivet ovenfor); og RPR må ikke anvendes inden i en rekursiv forespørgsel. Patchen håndhæver reglen om ydre referencer ("cannot use outer query column in DEFINE clause") og rekursionsreglen, sidstnævnte for hvert element i en WITH RECURSIVE-klausul. Den afviser også volatile funktioner og helrækkereferencer i DEFINE.

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.

Oprindelse. De implementerede og ikke-implementerede lister i dette afsnit afspejler den aktuelle tilstand af patch-serien — specifikt v55 (2026-11-17).

§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 fem gennemarbejdede eksempler: et enkelt match (NFA-bevægelse), alternation, kontekstabsorption i det lette tilfælde og to tilfælde, hvor absorption er deaktiveret.

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.

Text regex vs row pattern: a single state advances per symbol, while multiple DEFINE predicates can match a row in parallel. TEXT REGEX single state advances through symbols A B C one symbol per position · one transition ROW PATTERN one row, multiple predicates evaluated row price = 150 · volume = 2000 A ✓ price > 100 B ✓ volume > 1000 C ✗ price > 200 two predicates true · two states stay alive
Text-regex kollapser til én tilstand pr. symbol; en række kan opfylde flere DEFINE-prædikater på én gang, så flere tilstande forbliver levende parallelt.

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 (standard n = 1). Fremad-look-ahead; usædvanlig i window-formen, fordi vinduet er monotont.
FIRST(expr [, n])
Rækken n rækker efter den første række i det aktuelle match (standard n = 0, selve den første række). "Sammenlign med den række, der startede dette match."
LAST(expr [, n])
Rækken n rækker før den sidste matchede række (standard n = 0). Inden i DEFINE er den sidste matchede række den aktuelle række, så LAST(price) læser den aktuelle 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 den række, FIRST(expr, n) læser (standarder n = 0, m = 1). "Hvad var værdien lige før dette match begyndte?"
NEXT(FIRST(expr [, n]) [, m])
Træd m rækker frem fra den række, FIRST(expr, n) læser. 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 række, LAST(expr, n) læser. "Sammenlign med en række kort før den senest matchede række."
NEXT(LAST(expr [, n]) [, m])
Træd m rækker frem fra den række, LAST(expr, n) læser.

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. Simple PREV og NEXT er relative til den aktuelle række og altid sikre; FIRST og offset-varianter af LAST, alene eller inden i en sammensat PREV/NEXT, er relative til match-grænserne, hvilket interagerer med kontekstabsorption: planneren deaktiverer da absorption for hele mønsteret. Mekanismen bag denne interaktion er emnet for §2.6.

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

Mål for dette eksempelVis NFA-tilstandens udvikling række for række på et enkelt, ikke-absorberende mønster. Sporet følger konteksten startet ved række 0; konteksterne startet ved rækker 1–4 kører ved siden af den og kasseres af SKIP PAST LAST ROW, når dens match er registreret.
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:

RækkePrisSande varsHandling
0100STARTNy kontekst. START matcher og afsluttes straks (max=1); tilstand rykker frem til UP+.
1110START, UPUP matcher. Advance forgrener sig: én tilstand looper ved UP, en anden afslutter til DOWN+.
2120START, UPUP matcher i den loopende tilstand og forgrener sig igen. DOWN-tilstanden fra række 1 dør (120 ≮ 110).
3115START, DOWNUP fejler på den loopende tilstand og dør. DOWN-tilstanden fra række 2 matcher. Advance forgrener sig: loop ved DOWN, og afslut til #FIN — en match-kandidat over rækker 0–3 registreres.
4108START, DOWNDOWN matcher på den loopende tilstand og forgrener sig igen; den nye FIN-kandidat over rækker 0–4 erstatter den kortere.
5130START, UPDen loopende DOWN-tilstand fejler (130 ≮ 108). Uden nogen levende tilstand tilbage i denne kontekst færdiggøres den registrerede kandidat (rækker 0–4) som matchet. Det næste forsøg starter ved række 5; START matcher, men partitionen slutter før nogen UP.

Hovedpointen: ved række 3 opfylder rækken både START (altid sand) og DOWN, men START har kun betydning for en kontekst, der starter ved række 3; i denne kontekst dør den loopende UP-tilstand, og kun tilstanden, der venter ved DOWN+, rykker frem. 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 sidste FIN-kandidat (rækker 0–4) — produceret da DOWN afsluttede ved række 4, som erstatning for række-3-kandidaten — 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ækkePrisstart_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

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

Mål for dette eksempelVis, hvordan en enkelt kontekst bærer flere parallelle tilstande, når én række opfylder mere end ét alternativ — og hvordan standarden bryder uafgjort.

(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 mønsterrækkefølge, tidligere gren først.

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. Begge rykker derefter frem til DONE, hvor de mødes.

RækkeSande varsLevende tilstande
RUP, HIGHTilstand A (UP-gren) og tilstand B (HIGH-gren) rykker begge frem til DONE med de samme tællere; B er en dublet af A og kasseres
R+1DONETilstand A matcher DONE og når #FIN

I standardens termer producerer begge grene et match af samme længde over de samme rækker, hvilket giver 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. Executoren håndhæver dette ved række R, ikke ved FIN: den tilføjer UP-grenens tilstand først, så nfa_append_state_unique() beholder den og dropper den identiske HIGH-gren-tilstand.

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)

Mål for dette eksempelVis, hvorfor naivt O(n²) samlet tilstandsarbejde bliver O(n) under absorption, med O(1) levende kontekster.

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

RækkeNaive konteksterMed absorption
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 absorberet
2C1[A:3], C2[A:2], C3[A:1]C1[A:3]
3C1[A:4], C2[A:3], C3[A:2], C4[A:1]C1[A:4]
4fem konteksterC1[A:5]

Levende kontekster falder fra O(n) til O(1), så totalen over partitionen falder fra O(n²) til O(n). Absorptionsreglen, der retfærdiggør kassationen, er ligetil, når kvantoren er ubegrænset:

Absorptionsregel. To kontekster, hvis levende tilstand er ved det samme mønsterelement, hvor den ældre kontekst har et antal ≥ den nyere, har identiske fremtider under en ubegrænset kvantor. Den nyere kontekst kan kasseres; uanset hvilket match den i sidste ende ville finde, vil den ældre kontekst finde et længere eller lige langt.

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:

DagPrisC1 — tirs. start
price > PREV(price)
C2 — ons. start
price > PREV(price)
Man$100——
Tirs$108$108 > $100 ✓ (lige startet)—
Ons$112$112 > $108 ✓$112 > $108 ✓ (lige startet)
Tors$116$116 > $112 ✓$116 > $112 ✓
Fre$110$110 > $116 ✗ — færdiggør$110 > $116 ✗ — færdiggør
Samme skæbne På hver række C1 og C2 deler, evaluerer de identiske udtryk og producerer identiske resultater — og fredag dør de ved den selvsamme sammenligning. Uanset hvilken fremtid C2 har, har C1 den også. At absorbere C2 ind i C1 smider intet væk.

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

Mål for dette eksempelVis, hvad der ændrer sig, når DEFINE refererer til FIRST — absorptionsreglen holder ikke længere, og planneren deaktiverer absorption for mønsteret.

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

DagPrisC1 — man. start
FIRST = $100
price < $100 + 10
C2 — tirs. start
FIRST = $108
price < $108 + 10
Man$100$100 < $110 ✓—
Tirs$108$108 < $110 ✓$108 < $118 ✓ (lige startet)
Ons$112$112 < $110 ✗ — færdiggør man.–tirs.$112 < $118 ✓
Tors$116—$116 < $118 ✓
Fre$110—$110 < $118 ✓ (stadig i gang)
Forskellige skæbner C1 dør onsdag med en to-dages runde (man.–tirs.); C2 ville, alene, fortsætte helt igennem til fredag. Samme priser, samme spørgsmålsform — men forskellige lofter afledt af deres egne match-starts. På selvsamme dag nåede de to kontekster modsatte konklusioner.

Under absorption ville C2 være blevet flettet ind i C1 tirsdag — den flettede kontekst beholder kun C1's loft ($110), så C2's særskilte syn (loft $118, en fire-dages runde til og med fredag) er ikke dækket af C1's fremtid. I netop denne uge ændres outputtet tilfældigvis ikke: C1 registrerer man.–tirs., C2 startede inden i det match og kasseres af SKIP PAST LAST ROW, og næste forsøg starter onsdag med sit eget loft ($122) og matcher ons.–fre. Generelt subsumerer en tidligere konteksts DEFINE-resultat dog ikke længere en senere konteksts, så den antalssammenligning, absorption bygger på, er ugyldig. 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.)

Tabellen nedenfor udvider posterens nederste højre panel ("② Navigation") med de sammensatte former og opsummerer, hvilke navigationsformer der skaber match-start-afhængighed:

NavigationMatch-start-afh.Absorberbar?
PREV, NEXTingenja
LAST (uden offset)ingenja
LAST med offsetgrænsetjeknej
FIRST (enhver)direktenej
Sammensat (indre FIRST)direktenej
Sammensat (indre LAST, uden offset)ingenja
Sammensat (indre LAST med offset)grænsetjeknej

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 med sikkerhed dækker, så det kan ikke længere vises at være sikkert at kassere én.

Planneren opdager denne sondring ved compile time og slår absorption til eller fra for hele mønsteret; når den er slået fra, betaler køretiden multi-kontekst-omkostningen. Posterens benchmark i panel ③ bruger ingen FIRST, så absorption forbliver slået til, og derfor forbliver PostgreSQL lineær i både success- og failure-tilfældene.

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 cirka O(n), når et match er bekræftet, og PostgreSQL fører med cirka 16× til 33× (Trino-tallene udelukker allerede JVM-opstart).

På failure-mønsteret (A+ B+ C+ E) jagter Trino, som ser ud til at mangle absorption, enhver potentiel match-start og degenererer endnu hurtigere end O(n²) (cirka 56× tiden for 5× rækkerne); 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

Mål for dette eksempelVis en anden måde, hvorpå absorption kan fejle: ikke fordi prædikatet splittes, men fordi output-semantikken kræver, at hvert match rapporteres separat.

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.

RækkeSKIP PAST LAST ROWSKIP TO NEXT ROW
0match starter; rækker 0–4 vil være det eneste matchmatch starter ved række 0
1(inden i match 0)match starter ved række 1 — skal holdes i live
2(inden i match 0)match starter ved række 2 — skal holdes i live
3(inden i match 0)match starter ved række 3 — skal holdes i live
4match 0 færdiggøres (rækker 0–4)fem matches færdiggøres: 0–4, 1–4, 2–4, 3–4, 4–4
Forskelligt output, forskellige skæbner Under AFTER MATCH SKIP TO NEXT ROW er enhver sent startende kontekst sin egen output-række. To kontekster ved det samme mønsterelement er ikke længere redundante — de er begge påkrævede output, og at kassere én ville stille og roligt droppe et match, brugeren bad om.

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 de to måder, hvorpå en forespørgsels semantik udelukker absorption:

Datasiden · §2.6
Prædikatet evalueres forskelligt pr. kontekst.
Udløst af FIRST eller offset-bærende LAST i DEFINE.
Outputsiden · §2.7
Output kræver enhver match-start som en separat række.
Udløst af AFTER MATCH SKIP TO NEXT ROW.

Begge betingelser er nok til at deaktivere absorption for hele mønsteret, og det samme er en frame, der ikke slutter ved UNBOUNDED FOLLOWING. Når ingen af dem er i kraft — standard AFTER MATCH SKIP PAST LAST ROW, en ubegrænset frame-slutning og DEFINE-betingelser, der kun bruger PREV, NEXT eller bart LAST — er absorption aktiveret, men kun for tilstande i mønsterets absorberbare område: en ledende greedy ubegrænset variabel såsom A+ eller A*, en fast-længde-gruppe med en ubegrænset greedy kvantor såsom (A B)+, en greedy gruppe, hvis krop starter med en af disse, såsom (A+ B)+ eller (A+ B){2}, eller alternationsgrene bygget af disse; en tilbageholdende gruppe diskvalificerer hele sit undertræ. Hvor det holder, som for A+ i §2.5, kollapser køretiden til en enkelt kontekst og forbliver lineær; START UP+ DOWN+ fra §2.3 får slet intet absorberbart område.

§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²)-arbejde 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, slutgrænsen skal være UNBOUNDED FOLLOWING eller et positivt offset FOLLOWING (så en standard-frame afvises også), og andre EXCLUDE-optioner end EXCLUDE NO OTHERS 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:

KildeTræ-kodning
AVAR(A, min=1, max=1)
A+VAR(A, min=1, max=∞)
A*VAR(A, min=0, max=∞)
A{3,5}VAR(A, min=3, max=5)
A+?VAR(A, min=1, max=∞, reluctant=true)

Hvert DEFINE-prædikat type-tjekkes derefter mod partitionens kolonner og tvinges til et boolsk udtryk. To praktiske ting følger. For det første tilføjer parse-analysen intet til forespørgslens target list for DEFINE; i stedet markerer planneren enhver kolonne, som et DEFINE-prædikat refererer til, som nødvendig, ligesom den gør for HAVING, og 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 ni omskrivningsregler i et enkelt bottom-up-gennemløb (inden i en sekvens kører gruppesammenflettelsen én gang mere, da tidligere sammenflettelser kan bringe to identiske grupper sammen):

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-sammenflettelse
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
Normalisering af tilbageholdenhed
A{2}? → A{2} (tilbageholdenhed fjernes overalt, hvor min = max)

Kvantor-multiplikation kollapser kun, når de opnåelige antal danner ét sammenhængende interval, og det foretrukne match ikke flytter sig: en eksakt ydre ((A{2,3}){5} → A{10,15}), et barn med min 0 eller barne-intervaller, der støder op til hinanden, med et barne-min på højst 1 eller et ubegrænset barne-max ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), hvor en ydre med min 0 også kræver et barne-min på højst 1 ((A{2,})* bliver, da A* ville acceptere én række). Et gruppebarn, hvis egen kvantor ikke er eksakt, skal først have en krop med fast længde, så ((A | B B){1,2}){2} forbliver intakt selv under en eksakt ydre. 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 — eller flytte det foretrukne match ((A{2,3}){1,2} foretrækker tre rækker, hvor A{2,6} tager fire), så optimeringsenheden lader dem være intakte. Det er ikke den eneste betingede omskrivning: gruppesammenflettelse og suffiks-sammenflettelsen kræver en krop, der forbruger et fast antal rækker, præfiks-sammenflettelsen afviser en gruppe med min 0, et endeligt max og nullable indhold, tilbageholdende noder hverken sammenflettes eller multipliceres ((A+?)+ bliver), og en omskrivning, hvis nye grænse ville overflowe, afvises.

Elementform

Hvert element af det flade array repræsenterer en enkelt position i mønsteret. Der er seks 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; en grenseparator, der afslutter hver gren; 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-markøren og grenseparatorerne til at kæde grene sammen, af group begin til at navngive sin egen group end — en gruppe, hvis kvantor tillader nul, springes over via den ends next — 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 → 3
    (åbner gruppe; jump navngiver
     sin egen END)

[1] A      depth 1  quant 1..1
    next → 2

[2] B      depth 1  quant 1..1
    next → 3

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (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 navngiver BEGIN's jump dens END ved idx 3, og hvis gruppen var valgfri, ville springet forlade gruppen via den ENDs next til idx 4 uden at ankomme til END. 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 fem 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? B?)+, (A | B*)+; (A?)* multipliceres først til A* og efterlader ingen group end). Fortæller køretiden at tilføje en fast-forward-exit ved siden af det normale loop-back under min, så cyklus-vagten ikke dræber legitime matches i grupper, der kan producere tomme iterationer.
Tom-foretrukken
Sat på group ends, hvis krop foretrækker det tomme match, som i (A?? B??){2}. Placerer fast-forward-exit foran loop-back under min, hvor gruppens egen grådighed intet siger.
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 det flade array fra
  element 0 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 gennemgangen fire 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)+, (A+ B){2}
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å A får begge flag, den omsluttende BEGIN får i-område-flaget, og B og END får ingen.
Tilfælde 4 — Alternation
A+ | B+, A+ | C D
Hver gren, nået via separator-kæden, bedømmes for sig efter tilfældene ovenfor; alternation-markøren får i-område-flaget, når en hvilken som helst gren kvalificerer.

De strukturelle tilfælde, der ikke er dækket af disse fire 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. 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
  hvis targetPos != currentPos:
      hent række ved targetPos
        ind i nav_slot
      peg ydre slot på nav_slot
  result = eval_inner_expression()
  gendan current_row_slot
  kopiér by-ref result ud af nav_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 og ingen slot pr. reference; når målet er den aktuelle række, springes hentning og swap helt over. Hentningen kopierer målrækken ind i navigationsslotten (medmindre slotten allerede holder den), og gendannelsestrinet kopierer et pass-by-reference-resultat ind i per-tuple-hukommelse, så den næste hentning ikke kan frigive det.

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 currentPos − 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 (currentPos − n) − m
  NEXT(LAST(n), m):
      returnér (currentPos − 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 kontekstabsorption overhovedet er mulig (§2.5 vs §2.6): en enkelt match-start-afhængig variabel deaktiverer den for hele mønsteret.

Delt evaluering · absorption-sikker Enhver kontekst ser den samme boolean på hver række — samme skæbne (§2.5).
  • Ingen navigation
  • Kun PREV / NEXT
  • LAST uden offset
  • Sammensat med indre LAST (uden offset)
Per-kontekst-evaluering · absorption-usikker Kontekster med forskellige match-starts beregner forskellige svar — forskellige skæbner (§2.6).
  • LAST med offset
  • FIRST (enhver form)
  • Sammensat med indre FIRST
  • Sammensat med indre LAST (med offset)

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. Executoren udregner det ud fra to komplementære offsets og løser hvert offset én gang pr. scan (konstante også ved executor-init, så almindelig EXPLAIN kan vise dem):

Lookback-budget
Hvor langt bagud fra den aktuelle række ethvert DEFINE-kald kan nå.
Bidragsydere: PREV, LAST (ethvert offset, inklusive standardværdien 0), PREV(LAST(...)), NEXT(LAST(...))
Lookahead-fra-start-budget
Den mindste rækkevidde frem (bagud, når negativ) fra den ældste levende konteksts match-start — den tidligste række, noget DEFINE-kald kan få brug for.
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 konteksts 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 Nav Mark-linjer, som EXPLAIN rapporterer (§3.7) — Lookback og Lookahead — er disse to budgetter, ikke målte toppe. Hver udskrives kun, når en eller anden navigation forsyner den, og vises også uden ANALYZE; et offset, hvis værdi først kendes ved køretid (fx en generic-plan-parameter), udskrives som runtime under almindelig EXPLAIN og som sin løste værdi under EXPLAIN ANALYZE, og retain all (Lookback) eller infinite (Lookahead) markerer et offset, der overflower.

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

Et match-resultat registreres som to værdier: den række, hvor matchet starter, og dets længde. En negativ start betyder, at positionen endnu ikke er evalueret; når starten er sat, kan efterfølgende forespørgsler mod executoren — "er denne række inden i et match?" — svare i O(1) ved at inspicere parret. Længden koder udfaldet: -1 for en umatchet række, 0 for et tomt match og rækkeantallet for et reelt match. 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 både en umatchet række og "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 det pågældende vindues mønster, 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 og driver derefter NFA'en frem række for række — idet et per-variabel match-array nulstilles til "ikke evalueret" for hver række — indtil den kontekst ikke har flere levende tilstande, eller partitionen slutter. DEFINE-prædikater evalueres dovent: en variabel evalueres første gang en tilstand forbruger den, så en variabel, som ingen levende tilstand tester på denne række, evalueres aldrig. 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 har nået sin frame-slutning:
          fremtving mismatch (færdiggør tidligt)
          continue
      hvis matchStartRow afviger fra
         den delte evalueringsposition:
          nulstil match-start-afhængige
          DEFINE-vars til ikke evalueret (§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)
      hvis den registrerede et match og
         SKIP PAST LAST ROW:
          beskær senere kontekster, der
          starter inden i matchet

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]
      assert elem er en variabel
          # advance parkerer kun variabler

      hvis varMatched[elem.varId] er
         ikke evalueret:
          evaluer dens DEFINE nu
      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
         eller holder et registreret match:
          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), indtil konteksten registrerer et match, hvilket låser det til falsk — absorption ville frigøre et match, som ingen absorberende kontekst kan genskabe. 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-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, stopper
               når FIN er registreret),
    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 flag
         konteksten, så senere kontekster
         inden i denne kandidats interval
         beskæres — 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å når Advance er færdig med den kontekst, der registrerede en kandidat, beskæres enhver efterfølgende kontekst, hvis startrække falder inden i kandidatens interval, på samme række, 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 beskæringstrinet på tværs af kontekster ved FIN-tid. Inden i konteksten skærer FIN også leksikalsk underordnet arbejde væk: Advance dropper de resterende tilstande i køen (beskrevet tidligere i dette afsnit), og inden for én DFS stopper enhver mindre foretrukken sti — senere ALT-grene, den anden af BEGINs skip- og enter-stier, en tilbageholdende variabels enter-sti, den anden af ENDs loop- og exit-stier — når et match er registreret, så én advance registrerer højst ét match.

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
          (fast-forward først, hvis
           kroppen foretrækker tom; den
           anden sti droppes, hvis den
           første nåede FIN)

  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
          hvis loop nåede FIN:
              drop exit
              # foretræk længere
          ellers exit som nummer to
      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? B?)+ og (A | B*)+ har denne egenskab: afhængigt af dataene kan kroppen fuldføre en iteration uden at forbruge nogen række overhovedet. (Et enkelt valgfrit barn såsom (A?)* omskrives til A* ved compile time og efterlader ingen gruppe.) 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 ind i kroppen (dets jump er gruppens første barn), kroppen producerer endnu en gang et tomt match, når END igen, og så videre. Uden noget til at stoppe det ville Advance's DFS aldrig terminere.

Vagten 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. Køretiden holder en visited-bitmap, ryddet før hver tilstands DFS-udvidelse, hvori kun de taggede END'er markeres — intet andet kan danne en cyklus, fordi ethvert andet loop-back har forbrugt en række. At nå en markeret END betyder, at kroppen netop har afledt en tom iteration, og tilstanden kasseres ikke: ved eller over den nedre grænse forlader den gruppen dér (en tom iteration stopper kvantoren), og under den falder tilstanden igennem til det normale loop-back, så hver tom ankomst stadig øger tællingen, indtil den når min. Tag (A? B?){2,3} uden at nogen af variablerne matcher nogen steder i rækkestrømmen:

iter 1: A? B? matcher nul rækker
        → END, count = 1 (under min)
        END allerede markeret (ved
        indgang i gruppen), men under min:
        → loop tilbage ind i A?
iter 2: A? B? matcher nul rækker
        → END, count = 2 (opfylder min)
        END allerede markeret, ved min:
        → forlad gruppen
afslut med et nul-længde-match

Under den nedre grænse fortæller empty-loop-tagget også END-handleren at klone en yderligere fast-forward-tilstand ved siden af den normale loop-back-sti:

advance_end (count under min):

  loop-back-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. Loop-back er det, der fanger tilfældet, hvor kroppen stadig har reelle matches at producere senere — for eksempel i (A? B?){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 afslutter gruppen med det samme, erklærer "resten af de krævede iterationer er tomme" og lader matchet lykkes med en nul-længde-krop. Kroppen, ikke gruppens egen grådighed, afgør rækkefølgen: fast-forward går først præcis når kroppen foretrækker det tomme match (en tilbageholdende krop såsom (A?? B??)), og hvis den første sti når FIN, droppes den anden, så en mindre foretrukken sti ikke kan erstatte det foretrukne match. 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

At holde køretiden begrænset 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 sidder på et sammenligningspunkt og er dækket af en ældre konteksts absorberbare tilstand ved samme element med et større eller lige så stort 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) Advance
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, så snart Advance er færdig med den kontekst, der registrerede kandidaten.
Cyklusvagt Advance
Epsilon-udvidelser, der når END af en nullable gruppe, som allerede er markeret inden for samme DFS (markeret ved indgang via BEGIN eller ved en tidligere ankomst) — ville ellers loope evigt; tilstanden forlader gruppen dér ved eller over den nedre grænse og bliver ved med at loope under den.
Tom-loop fast-forward Advance
Under den nedre grænse af en nullable gruppe en ekstra sti, der afslutter gruppen med de resterende krævede iterationer erklæret tomme, ordnet i forhold til loop-back efter kroppens præference.
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). 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. 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. Kildekoden dokumenterer tilfælde, som lagene ikke fanger: dedup holder tilstande, der kun adskiller sig i tællinger over min, adskilt, så (A{2,} B)+ C med C aldrig sand holder Θ(n²) tilstande på toppen og opretter Θ(n³) af dem (37 s over 320 rækker), og en serie af helt nullable alternationer enumereres sti for sti, så (A?|B?){30} tager over en halv time.

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. I tekstformat udsendes de ved siden af window-operatøren, efter Pattern:-linjen, eventuelle Nav Mark-linjer (som almindelig EXPLAIN også viser) og Storage:-linjen:

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (hver kun når DEFINE bruger navigation,
   der forsyner den)
NFA States: N peak, N total, N merged
NFA Contexts: N peak, N total, N pruned
NFA: N matched (len min/max/avg),
     N mismatched (len min/max/avg)
NFA: N absorbed (len min/max/avg),
     N skipped (len min/max/avg)
  (anden NFA-linje kun når et af
   antallene er ikke-nul; et nul-antal
   udskrives uden sin (len ...))

Ikke-tekst-formater udsender hvert antal som sin egen egenskab. 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; pruned tæller kontekster, der fejlede efter en enkelt række. Match-længde-histogrammerne adskiller fire udfald — succesfulde matches, match-forsøg, der fejlede efter mere end én række (mismatched), absorberede kontekster og kontekster frigjort af AFTER MATCH SKIP PAST LAST ROW, fordi de startede inden i et registreret match (skipped) — 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 fra DEFINE. Lookback er den dybeste baglæns rækkevidde fra den aktuelle række på tværs af PREV, LAST med ethvert offset (inklusive standardværdien 0) og de sammensatte former med indre LAST; Lookahead er den mindste fremadrettede rækkevidde (negativ, når den kigger før match-start) målt fra den ældste levende konteksts 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 kun kendes pr. scan, og — kun for Lookback — "retain all", når offsettet overflower; en Lookahead, der overflower, udskrives som "infinite". Hver linje udsendes kun, når en eller anden navigation i DEFINE forsyner den, og begge vises også under almindelig EXPLAIN: konstante offsets fastlægges ved executor-init, mens et offset, der først kendes ved køretid (fx en generic-plan-parameter), dér udskrives som "runtime" og som sit løste heltal under EXPLAIN ANALYZE.

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

Ud over tællerne udskriver EXPLAIN en Pattern:-linje bygget fra det kompilerede elementarray, så den viser mønsteret efter compile-time-omskrivningerne (PATTERN (A A) forklares som a{2}) og bærer absorptionsmarkørerne # (sammenligningspunkt) og ~ (absorberbart område); DEFINE og AFTER MATCH SKIP-optionen vises ikke. At reproducere klausulerne som skrevet, inklusive tilbageholdende kvantorer, gruppe-gentagelse og skip-optionen, er opgaven for pg_get_viewdef(), som 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 22.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
WINDOW-klausul-integration — realistiske window-scenarier på syntetiske aktiedata (V-form, W-form, sammenhængende stigninger, vendinger) samt navigationssemantik og DEFINE-restriktionsfejl.
rpr_base
Parser-laget — nøgleord-accept, syntaksformer, kvantorer, navigations-parsing, fejlmeddelelser og pg_dump/pg_upgrade-round-trip-stabilitet; plus et planner-lag — mønsteroptimering, absorptionsflag, optimerings-fallback, planner-integration.
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. Disse scenarier er de eneste test, hvis input og output læser som forespørgsler, en bruger faktisk kunne skrive; resten af filen er, ligesom de andre suiter, reduktiv — PREV/NEXT-indlejring og fejl ved ikke-konstante offsets, DEFINE-referenceregler og navigations-offset-semantik.

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. En anden del, planner-laget, dækker mønsteroptimering, visning og analyse af absorptionsflag, optimerings-fallback og planner-integration (underforespørgsler, joins, mængdeoperationer, sortering og gruppering).

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. Defekter 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: inline VALUES-rækker, der bærer et array af variabelnavne, som erklærer hvilke DEFINE-variabler der matcher på hver række, parret med et mønster, der prober en specifik køretidsadfærd. 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:

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 (overvågnings-dashboards, log-scrapers) parser det, og ændringer, der ser kosmetiske ud, kan ødelægge dem. rpr_explain-suiten verificerer tre ting:

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, hvordan hver af disse optimeringer behandler RPR-vinduer — de fleste skal deaktiveres eller omgås:

Frame-kanonisering
Planneren omskriver normalt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING til ROWS UNBOUNDED PRECEDING for frame-uafhængige window-funktioner såsom row_number, rank og ntile. 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 eller SKIP)
To RPR-vinduer med samme PATTERN, men forskellige DEFINE-klausuler eller en forskellig AFTER MATCH SKIP producerer forskellige matches og skal forblive adskilte, selvom deres strukturelle form er identisk.
Unused-output-projektion
Denne må gerne anvendes: når den omgivende forespørgsel aldrig læser vinduets output, bliver window-funktionen NULL, og dens WindowAgg droppes, mens rækkeantallet forbliver uændret. Testene tjekker, at de kolonner, DEFINE læser, stadig når WindowAgg, når den bliver, og at vinduet bevares, når dets værdi læses.
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.

Yderligere tilfælde tjekker, at omkostningsestimering tager højde for DEFINE, at en underforespørgsel, der holder et RPR-vindue, ikke flades ud, at DEFINE-udtryk ikke lækker ind i en øvre WindowAgg, og at LIMIT forbliver over WindowAgg; en anden gruppe kører RPR sammen med CTE'er, joins, mængdeoperationer, prepared statements, partitionerede tabeller og lignende konstruktioner. De fleste beskyttede tilfælde følger samme form: en baseline, der udløser optimeringen (som regel en ikke-RPR-forespørgsel, tjekket i EXPLAIN), og derefter en RPR-forespørgsel af strukturelt lignende form, hvor optimeringen ikke anvendes — for DEFINE/SKIP-dedup-tilfældet er baselinen to identiske RPR-vinduer, og inverse-transition-tilfældet tjekker omgåelsen med et loggende aggregat snarere end EXPLAIN. 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.