Row Pattern Recognition Dypdykk

§1. Standarden, delmengden og de åpne spørsmålene

1.1 Standardens omfang

Row Pattern Recognition ble innført i SQL gjennom ISO/IEC 9075-2:2016 og er beskrevet i følgedokumentet ISO/IEC 19075-5:2021 (Del 5, "Row Pattern Recognition").

Standarden definerer to flater for det samme underliggende maskineriet. Funksjonen R010 plasserer en MATCH_RECOGNIZE-klausul i FROM-listen for å produsere en avledet tabell; funksjonen R020 fletter den samme mønsterlogikken inn i en WINDOW-spesifikasjon for å produsere vindusfunksjonsutdata. De to flatene deler hoveddelen av syntaksen og hele semantikken, men er funksjonelt distinkte inngangspunkter — en database kan implementere én av dem eller begge.

Patch-serien som diskuteres her, implementerer en delmengde av kun R020; tabellklausulformen er bevisst utenfor omfanget.

R020-flaten er liten, men uttrykksfull. En spørring fester et mønster til et vindu ved å legge til tre klausuler inne i vindusspesifikasjonen: PATTERN beskriver et regulært uttrykk over navngitte mønstervariabler, DEFINE oppgir det boolske predikatet som identifiserer hver variabel, og AFTER MATCH SKIP styrer hvordan etterfølgende treff plasseres innenfor partisjonen.

Valgfrie MEASURES, SUBSET, INITIAL/SEEK og hjelpefunksjonen CLASSIFIER() komplementerer funksjonen. (Standardens MATCH_NUMBER()-funksjon tilhører kun R010-flaten — 19075-5 §6.3.3 (6) ekskluderer den eksplisitt fra R020.)

Patchen dekker nok av dette vokabularet til at ikke-trivielle spørringer fungerer, men stopper foran flere konstruksjoner hvis implementasjon avhenger av infrastruktur som ennå ikke er bygget.

Resten av denne seksjonen deler standardens vokabular inn i det patchen allerede støtter, og det den bevisst lar stå til senere. Listene nedenfor gjenspeiler dagens tilstand for patch-serien.

1.2 Implementerte funksjoner

Det implementerte vokabularet er tilstrekkelig til å uttrykke de kanoniske V-form-, W-form- og reverseringsmønstrene som i utgangspunktet motiverer Row Pattern Recognition. Det dekker også alle standardkvantifikatorer — inkludert alle sju motvillige varianter *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — og de fire navigasjonsprimitivene som DEFINE-betingelser trenger for å sammenligne nærliggende rader.

PATTERN-klausul

Definerer radmønsteret inne i en vindusspesifikasjon.

Regex: + * ? |

Standardkvantifikatorer og alternering.

Regex: ( ) gruppering

Parentesgrupperte delmønstre.

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

Begrensede gjentakelsestall.

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

Alle sju motvillige (ikke-grådige) varianter standarden definerer (ekskludert fra absorpsjonsoptimalisering).

DEFINE-klausul

Boolske betingelser som identifiserer hver mønstervariabel.

Universell radmønstervariabel

Ukvalifiserte kolonnereferanser i DEFINE (f.eks. bare Price) løses til den gjeldende raden, jf. 19075-5 §4.10/§4.16.

PREV, NEXT (med forskyvning)

Når n rader før/etter gjeldende rad (standard 1); det indre argumentet er et vilkårlig verdiuttrykk som evalueres på den navigerte raden.

FIRST, LAST (med forskyvning)

Når en treff-relativ rad; FIRST(expr, n) peker på raden n etter treffstarten, LAST(expr, n) raden n før den nyeste treffraden.

Sammensatt navigasjon (fire former)

Ytre PREV/NEXT-steg lagt over et indre FIRST/LAST: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — både det indre og det ytre steget kan ha sin egen forskyvning.

INITIAL

Mønstertreff må starte på gjeldende rad (standard).

AFTER MATCH SKIP PAST LAST ROW

Standard skipmodus; kvalifisert for kontekstabsorpsjon.

AFTER MATCH SKIP TO NEXT ROW

Tillater overlappende treff; deaktiverer absorpsjon.

1.3 Ikke implementert

Funksjonene som gjenstår uimplementert, faller i tre løse grupper. Den første — og klart største — er familien av konstruksjoner sentrert rundt MEASURES: selve MEASURES-klausulen, SUBSET, CLASSIFIER(), mønsterkvalifiserte kolonnereferanser som B.price, og mønsterkvalifisert navigasjon som LAST(B.price) eller PREV(B.price).

Dette er ikke uavhengige hull så mye som ulike visninger av én enkelt manglende brikke: eksekutoren må beholde en per-treff-historikk — en registrering, for hver rad i treffet, av hvilken mønstervariabel den ble tilordnet — og ingen av disse konstruksjonene har en meningsfull definisjon uten den. CLASSIFIER() leser variabelnavnet ut av den registreringen; B.price leser pris-kolonnen til de radene hvis registrering sier B; LAST(B.price) går gjennom samme sett av rader og velger den siste; SUBSET U = (A, B) definerer en virtuell variabel som aggregerer over begge bøttene; og MEASURES evaluerer uttrykk som AVG(U.Price) med nettopp den aggregeringen.

Dagens eksekutor evaluerer DEFINE-predikater rad for rad, men registrerer ikke de resulterende variabeltilordningene noe sted — det er ingenting å spørre om senere. Å bygge historikkinfrastrukturen er derfor forutsetningen for hele gruppen; de enkelte funksjonene faller ut som små projeksjoner når registreringene finnes.

Den andre grupperingen gjelder alternative skipmål: AFTER MATCH SKIP TO label, AFTER MATCH SKIP TO FIRST var og AFTER MATCH SKIP TO LAST var. Disse avhenger også av treffhistorikk, siden eksekutoren må kunne peke på en bestemt merket rad inne i det nyeste treffet.

De gjenværende elementene er en heterogen hale: nøkkelordet SEEK (alternativet til INITIAL), det tomme mønsteret (), ekskluderingsformen {- … -} og den rekkefølgeufølsomme PERMUTE-operatoren.

MEASURES

Navngitte per-treff-utdataruttrykk, f.eks. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; i R020 eksponert via OVER som en vindusfunksjon. Aksepterer nøkkelordene FINAL / RUNNING (19075-5 §5.4), som i R020 kollapser til samme verdi siden mål alltid evalueres på siste rad i treffet (19075-5 §6.9 (3)).

SUBSET

Navngitte unioner av mønstervariabler, f.eks. SUBSET U = (A, B, C). Kan brukes overalt hvor en mønstervariabel kan refereres — MEASURES, mønsterkvalifiserte referanser i DEFINE, CLASSIFIER(U) — som alle krever treffhistorikk.

CLASSIFIER()

Returnerer hvilken mønstervariabel en gitt rad ble tilordnet. Definert for både DEFINE og MEASURES (19075-5 §5.9); svaret på en gitt rad er variabelnavnet som er registrert i treffhistorikken for den raden.

Mønsterkvalifisert kolonnereferanse

Bart B.price i DEFINE eller MEASURES — verdien av kolonnen fra raden tilordnet den navngitte variabelen.

Mønsterkvalifisert navigasjon

Begrens navigasjon til rader tilordnet en navngitt variabel, f.eks. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

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

AFTER MATCH SKIP TO label

Hopp til en merket rad.

AFTER MATCH SKIP TO FIRST var

Hopp til den første raden tilordnet den navngitte variabelen.

AFTER MATCH SKIP TO LAST var

Hopp til den siste raden tilordnet den navngitte variabelen.

Regex: {- -}

Ekskludering — fjerner treffende rader fra per-treff-utdata.

Regex: ()

Tomt mønster — treffer den tomme sekvensen.

PERMUTE(...)

Rekkefølgeufølsom matching over oppførte variabler.

Aggregatfunksjoner i DEFINE

Aggregater som SUM, AVG, COUNT er ikke tillatt i DEFINE-predikater. Standarden tillater dem som løpende aggregater over delvis treff (per-rad-evaluering mot rader allerede tilordnet en variabel), noe som avhenger av samme per-treff-historikk som MEASURES/CLASSIFIER() krever.

Fire ytterligere punkter er verdt å nevne her, siden de lett kan forveksles med utelatelser.

Det første er at mønsterankrene ^ og $ ikke er tillatt med RPR i WINDOW-klausulen av selve standarden (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; med den underliggende definisjonen i 19075-5 §4.14.1); fraværet er konformitet, ikke et hull.

Det andre er at MATCH_NUMBER() likeledes er ekskludert fra R020 av standarden (19075-5 §6.3.3 (6) og 19075-5 §6.9 (1)) — den tilhører kun R010-flaten, og fraværet her er igjen konformitet snarere enn en manglende funksjon.

Det tredje er et sett strukturelle forbud standarden pålegger R020 (19075-5 §6.17): row pattern recognition kan ikke nestes inne i en annen row pattern recognition; MEASURES og DEFINE kan ikke inneholde ytre referanser; underspørringer inne i MEASURES eller DEFINE kan ikke referere mønstervariabler; og RPR kan ikke brukes inne i en rekursiv spørring.

Det fjerde er at selve MATCH_RECOGNIZE — funksjon R010, tabellklausulflaten til samme maskineri — er utenfor omfanget for denne patchen. Hvorvidt PostgreSQL etter hvert legger til R010, vil være et spørsmål for en fremtidig serie, ikke et mål på denne.

§2. Eksempler — Hvordan det faktisk kjører

Eksemplene i denne seksjonen bygger seg gradvis opp. Vi starter med den konseptuelle grunnen til at row-pattern-matching er genuint forskjellig fra streng-matching, introduserer deretter de fire navigasjonsfunksjonene som gjør DEFINE-betingelser interessante, og går til slutt gjennom tre helhetlige spor: et enkelt treff (NFA-bevegelse), kontekstabsorpsjon i det enkle tilfellet, og tilfellet hvor absorpsjon blir utrygg.

Den interne mekanismen som gjør navigasjon billig — 1-slot tuppelbyttet — tilhører eksekutorens design og dekkes i neste seksjon, ikke her.

2.1 Hvorfor radmønstre skiller seg fra tekstmønstre

Et tekstregulært uttrykk matcher en strøm av tegn, og i hver posisjon finnes nøyaktig ett symbol å vurdere. Kjøretidsspørsmålet — "tilsvarer det gjeldende symbolet 'A'?" — har et enkelt ja/nei-svar. Tilbakesporingsautomater utnytter dette: høyst én gren overlever per tegn, og kostnaden for tvetydighet betales ved å lese inndataen på nytt.

Et radmønster er forskjellig på en fundamental måte. En rad er ikke et enkelt symbol; det er en tuppel av kolonner som evalueres mot et sett av boolske predikater, DEFINE-betingelsene. To predikater kan være sanne samtidig på samme rad, og ingenting i standarden sier at de må være gjensidig utelukkende. Vurder:

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

En rad med price = 150, volume = 2000 tilfredsstiller både A og B, men ikke C. Mønstermatcheren kan ikke kollapse dette til én tilstand — to mønstervariabler er aktive, og ethvert mønsterelement som navngir én av dem, kan rykke fram. NFA-en må derfor bære flere samtidige tilstander per partisjonsrad, ikke én.

Denne enkeltobservasjonen driver resten av arkitekturen. Eksekveringstilstanden er en liste med kontekster, hver kontekst er en liste med tilstander, og ved hver rad spør kjøretiden hver tilstand: "gitt variablene som er sanne her, hvor kan jeg gå?" Forgreningene som oppstår, er grunnen til at kjøretiden trenger flere lag med beskjæring — tilstandsdeduplisering innenfor en kontekst, absorpsjon på tvers av kontekster og de andre reglene som gjennomgås i §3.6 — uten disse vokser antallet aktive tilstander og kontekster med partisjonen, og mønstermatching blir superlineær.

2.2 Navigasjonsfunksjoner

DEFINE-betingelser som kun refererer gjeldende rad, er begrensede; nesten alle interessante mønstre må sammenligne gjeldende rad med naboene eller med radene som allerede er akseptert tidligere i treffet. Standarden tilbyr fire navigasjonsfunksjoner for dette, og patchen implementerer alle.

PREV(expr [, n])

Raden n rader før gjeldende rad (standard n = 1). Brukes til "i dag vs. i går"-sammenligninger.

NEXT(expr [, n])

Raden n rader etter gjeldende rad. Look-ahead framover; uvanlig i vindusform siden vinduet er monotont.

FIRST(expr [, n])

Den n-te treffraden i gjeldende treff, telt fra starten. "Sammenlign med raden som startet dette treffet."

LAST(expr [, n])

Den n-te nyeste treffraden. "Sammenlign med den nyeste treffraden."

De fire primitivene kan komponeres: PREV og NEXT kan omslutte et FIRST- eller LAST-kall, og gir fire sammensatte former med semantikken "gå til en treff-relativ rad, og steg deretter en fast avstand bort fra den". Dette gjør at et DEFINE-uttrykk for eksempel kan lese raden umiddelbart før treffet startet.

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

Steg m rader tilbake fra treffets n-te rad (standard m = 1). "Hva var verdien rett før dette treffet begynte?"

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

Steg m rader fram fra treffets n-te rad. Når lenger inn i treffet uten å avhenge av gjeldende rad.

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

Steg m rader tilbake fra den n-te nyeste treffraden. "Sammenlign med en rad like før det nyeste treffet."

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

Steg m rader fram fra den n-te nyeste treffraden.

To praktiske poeng er verdt å nevne. For det første kan navigasjon sammensettes: PREV(FIRST(price)) leser raden umiddelbart før treffet startet, og patchen støtter dette. For det andre har navigasjon konsekvenser for eksekutorens optimaliseringer. PREV og NEXT er relative til gjeldende rad og er alltid trygge; FIRST og forskjøvne varianter av LAST er relative til treffgrensene, noe som samspiller med kontekstabsorpsjon og tvinger planleggeren til å holde noen kontekster aktive som den ellers ville forkastet. Mekanismen bak det samspillet er temaet i §2.6.

2.3 Eksempel 1 — NFA-bevegelse

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 flates ut 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:

Hovedpoenget: på rad 3 tilfredsstiller raden både START (alltid sann) og DOWN, men den eneste tilstanden som overlevde rad 2, er på DOWN-utgangsgrenen, så bare overgangen UP → DOWN tas. Multitilstandsnaturen fra §2.1 vises som fan-out ved hvert UP-treff (tilstanden kan bli ved UP+ eller rykke fram mot DOWN+). Grådig prioritering er "løkk igjen før utgang", så med nok data ville de løkkende grenene forlenget treffet ytterligere; her dør den løkkende DOWN på rad 5 (130 ≮ 108), og den tidligere FIN-kandidaten (rader 0–4) — produsert da DOWN gikk ut på rad 4 — finaliseres som treffet.

Spørringens resultat følger direkte av dette sporet. Under RPR-semantikk evalueres vindusfunksjonene first_value(price) og last_value(price) bare på raden som startet treffet — alle andre rader i treffet gir NULL for disse vindusfunksjonene, siden den reduserte rammen er tom. Utdataen for våre data ser derfor ut som tabellen posteren viser i øvre høyre panel:

Rad 0 er treffstarten, så rammen dekker rader 0–4, og vindusfunksjonene rapporterer V-formens åpningspris ($100) og bunnpris ($108). Rader 1–4 er inne i treffet, men ikke starten, så de mottar NULL. Rad 5 (pris $130) er utenfor ethvert treff og mottar likeledes NULL.

2.4 Eksempel 2 — Alternering og leksikalsk rekkefølge

Formen (A | B) gir matcheren et valg: ved hver rad testes de to alternativene uavhengig, og et hvilket som helst antall av dem kan treffe. Det er her multitilstandsnaturen fra §2.1 blir synlig inne i én enkelt kontekst — ikke på tvers av kontekster (det er absorpsjon), men langs parallelle grener eksekutoren utforsker i takt.

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

Forestill deg en rad der prisen både har steget og overskredet $100 — både UP og HIGH er sanne. Hvert alternativ spawner sin egen tilstand: én som går UP-grenen, én som går HIGH-grenen. De fortsetter parallelt til DONE løser dem.

Begge grenene produserer et treff av samme lengde over de samme radene, og etterlater matcheren med to kandidatstier — én merket UP, DONE og én merket HIGH, DONE. Standarden løser dette ved leksikalsk rekkefølge: blant alternativene skrevet i (UP | HIGH) vinner den som er skrevet først, uansett trefflengde. Siden UP står før HIGH, er den overlevende stien UP, DONE.

Leksikalsk rekkefølge er det som gjør CLASSIFIER() veldefinert når den til slutt blir implementert — den lar kjøretiden fortelle brukeren "denne raden traff UP, ikke HIGH" selv når begge predikatene var sanne. Leksikalsk rekkefølge er hovedregelen for alternering: en leks-tidligere gren vinner over en leks-senere selv om den leks-senere ville produsert et lengre treff, og en leks-senere (muligens kortere) gren kan likevel vinne hvis hver leks-tidligere gren dør før den når FIN. Grådig lengde avgjøres innenfor én enkelt kvantifikator — gitt to fullføringer av samme altereringsgren, foretrekker den grådige kvantifikatoren flere iterasjoner.

2.5 Eksempel 3 — Kontekstabsorpsjon (samme skjebne)

Det enkleste mønsteret som viser absorpsjon, er PATTERN (A+) med DEFINE A AS TRUE. Hver rad treffer A, og standarden krever at matcheren vurderer hver rad som en mulig treffstart. Naivt betyr dette N kontekster for en N-raders partisjon. Ta en fem-raders partisjon (vilkårlige data — predikatet er konstant sant):

Minnebruk vokser fra O(n) til O(1). Absorpsjonsregelen som rettferdiggjør forkastingen, er enkel når kvantifikatoren er ubegrenset:

Posterens nedre venstre panel ("① Context Absorption") er nettopp denne regelen visualisert over fem rader.

Et subtilt, men viktig poeng skjuler seg i regelen: forkastingen er trygg fordi predikatet A AS TRUE evaluerer til samme verdi ved hver rad uavhengig av hvilken kontekst som spør. Det samme gjelder ethvert predikat som kun refererer gjeldende rad eller en fast forskyvning fra den — inkludert PREV. Det neste eksempelet bytter til en konkret prisuke ved bruk av et PREV-basert predikat, og §2.6 vil gjenbruke nettopp den uka for å gjøre symmetrien mellom trygg og utrygg absorpsjon åpenbar:

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

Ta handelsuken $100, $108, $112, $116, $110 fra mandag til fredag — fire stigninger fulgt av et plutselig fall. Anta at C1 starter på tirsdag (den første dagen RISE treffer: $108 > $100), og at eksekutoren spekulativt også sporer C2 som starter på onsdag. Hver rads RISE-betingelse sammenligner radens pris med dens umiddelbare forgjenger — et partisjonsnivåfaktum, ikke et kontekstnivåfaktum — så de to kontekstene blir tvunget til å regne ut samme Boolean på hver rad de deler:

Historien brister i samme øyeblikk predikatet begynner å avhenge av hver kontekst sine egne grenser — og det er det §2.6 handler om.

2.6 Eksempel 4 — Når absorpsjon blir utrygg

Anta at en analytiker vil finne sammenhengende handelsdager der en aksje holdt seg innenfor ti dollar fra dagen serien startet — en slags konsolideringsvindu. Mønsteret og DEFINE ser slik ut:

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

Betingelsen sammenligner nå gjeldende rads pris med prisen ved starten av gjeldende serie. To serier som startet på forskjellige dager, har forskjellige FIRST(price)-verdier, så to tilstander ved samme mønsterelement og samme telling er ikke lenger utskiftbare: framtidene deres avhenger av grensen absorpsjon var i ferd med å forkaste.

Ta nøyaktig samme handelsuke som i §2.5 — $100, $108, $112, $116, $110 fra mandag til fredag. Kjøretiden holder igjen to kandidatserier aktive samtidig: C1 startet på mandag, C2 startet på tirsdag (hver rad er en mulig seriestart under STABLE+).

Under absorpsjon ville C2 blitt slått sammen med C1 på tirsdag — den sammenslåtte konteksten beholder bare ett tak, så C2 sitt distinkte syn (tak $118, fire-dagers serien som først ender på lørdag) er ikke lenger gjenopprettbart fra intern tilstand. C2 må holdes aktiv fordi den er en uavhengig treffkandidat kjøretiden fortsatt kan trenge: når C1 sitt treff ender på onsdag, må neste forsøk plukke opp fra en fortsatt løpende C2 i stedet for å starte på nytt. Når et DEFINE-predikat bærer treffstart-avhengighet, deaktiverer planleggeren derfor absorpsjon på forhånd.

(Når det ledende kontekstens treff faktisk lykkes, blir kontekster som startet innenfor det aksepterte spennet — under standard AFTER MATCH SKIP PAST LAST ROW — bare forkastet; de holdes kun aktive for at kjøretiden skal ha noe å falle tilbake til hvis det ledende treffet feiler.)

Avhengighetstabellen på posterens nedre høyre panel ("② Navigation") oppsummerer hvilke navigasjonsformer som skaper treffstart-avhengighet:

De to eksemplene i §2.5 og §2.6 reduseres til én enkelt regel. Samme skjebne er det som gjør absorpsjon trygg: hvis hver kontekst ved samme mønsterelement vil regne ut samme svar på hvert framtidige predikat, trenger kun den eldste å beholdes. Forskjellige skjebner gjør absorpsjon utrygg: så snart predikater forgrener seg på kontekstprivat tilstand — som er nettopp det FIRST og forskjøvet LAST gjør — representerer hver aktive kontekst en framtid ingen annen kontekst kan gjenopprette, og å forkaste noen av dem risikerer å produsere et galt svar.

Planleggeren oppdager denne distinksjonen ved kompileringstid og bestemmer per kontekst om absorpsjon gjelder. Det er også grunnen til at posterens benchmark i panel ③ holder seg lineær i både suksess- og feiltilfellene: når absorpsjon er trygg, kollapser kjøretiden kontekster, og når den ikke er det, aksepterer planleggeren multikontekst-kostnaden i stedet for å risikere et galt svar.

Benchmark-tallene på posteren er samme algoritme i skala. På suksessmønsteret (A+ B+ C+ D) skalerer både PostgreSQL og Trino O(n) når et treff er bekreftet, og PostgreSQLs forsprang — omtrent 16× til 33× — er stort sett JVM-gapet.

På feilmønsteret (A+ B+ C+ E) har Trino ingen absorpsjon og degraderes til O(n²) ved å jakte hver mulig treffstart; ved 100 000 rader tar det mer enn fem timer, mens PostgreSQL fortsatt fullfører på 92 ms, en hastighetsøkning på omtrent 217 000×.

Det gapet er ikke ingeniørmessig finpuss — det er nettopp samme-skjebne / forskjellig-skjebne-distinksjonen fra §2.5 og §2.6, anvendt på hver rad av hver mulig treffstart i partisjonen.

2.7 Eksempel 5 — Når SKIP deaktiverer absorpsjon

Det forrige eksempelet brøt absorpsjon fra data-siden: FIRST i DEFINE gjorde at hver kontekst evaluerte predikater forskjellig. Absorpsjon kan også brytes fra utdata-siden, og AFTER MATCH SKIP-klausulen er det som styrer det.

Vurder mønsteret PATTERN (A+) med DEFINE A AS TRUE over fem rader som alle treffer A. Under standard AFTER MATCH SKIP PAST LAST ROW finner matcheren det lengste treffet som starter på den tidligste raden og hopper deretter forbi det; enhver kontekst som startet inne i det treffet, forkastes implisitt som overflødig — nøyaktig den situasjonen absorpsjon er designet for å håndtere. Utdataen er ett enkelt treff, rader 0–4, og kjøretiden trenger kun én aktiv kontekst.

Bytt skipmodus til AFTER MATCH SKIP TO NEXT ROW og kontrakten endres:

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

Nå må hver mulig startposisjon rapporteres separat, selv når treff overlapper. For de samme fem radene er kjøretiden pålagt å emittere fem treff: rader 0–4, 1–4, 2–4, 3–4 og 4–4. Ingen av disse kan erstattes av "et lengre som starter tidligere", fordi standarden sier at brukeren vil ha alle.

Legg merke til at predikatet ikke har endret seg. A AS TRUE evaluerer likt på hver rad uavhengig av hvilken kontekst som spør, så samme-skjebne-betingelsen fra §2.5 er fortsatt oppfylt. Det som endres, er utdata-kravet: selv kontekster med identiske framtider må sameksistere fordi de tilsvarer distinkte rader i resultatet. Planleggeren deaktiverer derfor kontekstabsorpsjon når AFTER MATCH SKIP TO NEXT ROW er aktiv, uavhengig av DEFINE-klausulen.

Å sette §2.6 og §2.7 side om side gir det fulle bildet av når absorpsjon feiler:

Begge betingelsene er nok til å deaktivere absorpsjon for de berørte kontekstene. Når ingen er aktiv — standard AFTER MATCH SKIP PAST LAST ROW med DEFINE-betingelser som bare bruker PREV, NEXT eller bart LAST — kollapser kjøretiden til én enkelt kontekst per mønsterposisjon og holder seg lineær hele veien.

§3. Design — Fra parser til eksekutor

Row Pattern Recognition er implementert som tre stadier som overleverer arbeid gjennom veldefinerte mellomformer. Parseren omdanner SQL-tekst til et mønstertre og en liste med DEFINE-predikater; planleggeren kompilerer treet til et flatt array av mønsterelementer og bestemmer hvilke av dem som kan delta i kontekstabsorpsjon; eksekutoren kjører arrayet mot partisjonen rad for rad i en trefase-løkke. Hvert stadium har sin egen dataform, og det meste av designgeniet ligger ved grensene: en flat NFA som passer i cache, en navigasjonsmodell som gjenbruker en enkelt tuppelslot i stedet for å materialisere én per referanse, og en absorpsjonsregel som gjør O(n²) minne om til O(n).

SQL text
  │
  │  parser stage
  ▼    validate frame
       build pattern tree
       type-check DEFINE

pattern tree + DEFINE list
  │
  │  planner stage
  ▼    optimize the tree
       compile to flat NFA array
       decide absorbability

flat NFA + absorption flags
  │
  │  executor stage
  ▼    per-row engine:
       Match → Absorb → Advance

match result:
  start row, length, success/fail

Seksjonene nedenfor følger denne pipelinen. §3.1 dekker parseren og formen til mønstertreet; §3.2 dekker kompileringen som omdanner treet til den flate NFA-en; §3.3 dekker navigasjonsmodellen DEFINE-predikater bruker for å se på nabbrader; §3.4 dekker treffgrensehåndtering — SKIP-, INITIAL- og bundet-ramme-reglene som fastsetter hvor et treff starter og slutter; §3.5 er trefase-per-rad-motoren; §3.6 samler alle beskjæringsmekanismene som holder tilstandsrommet begrenset; og §3.7 oppsummerer hva implementasjonen eksponerer i EXPLAIN-utdata.

3.1 Parser — bygge mønstertreet

Parseren gjenkjenner pattern recognition ved tilstedeværelsen av en PATTERN-klausul inne i en vindusspesifikasjon. Dens første jobb er rammevalidering, siden RPR påtvinger begrensninger ordinære vindusspørringer ikke har: rammemodusen må være ROWS (ikke RANGE eller GROUPS), startgrensen må være CURRENT ROW, og EXCLUDE-alternativer er forbudt. Dette er konformitetskontroller, ikke optimaliseringer — RPRs forestilling om en ramme er treffspennet, og standarden tar ikke i betraktning å fylle den med annet enn de treffende radene.

Når rammen består valideringen, omdanner parseren PATTERN-klausulen til et tre bygget av fire slags noder — en variabelreferanse, en sekvens (konkatenering), en alternering og en gruppe (parentesgruppert delmønster). Hver node bærer kvantifikatoren som tre tall — en nedre grense, en øvre grense (muligens uendelig) og et flagg for motvillig matching:

Hvert DEFINE-predikat blir deretter typesjekket mot partisjonens kolonner og tvunget til et boolsk uttrykk. To praktiske ting skjer som en del av dette. For det første registreres hver kolonne som refereres av et DEFINE-predikat som en del av spørringens utdatakrav, så planleggeren propagerer disse kolonnene videre til eksekutorstadiet selv om den omsluttende spørringen ikke velger dem — uten det ville kjøretiden ikke ha noe å evaluere mot. For det andre er variabler som forekommer i PATTERN, men aldri i DEFINE, implisitt sanne: de treffer hver rad.

3.2 Kompilering — fra AST til flat NFA

Planleggeren omdanner parserens tre til datastrukturen eksekutoren skal kjøre: et flatt array av mønsterelementer adressert ved indeks. Kompileringen foregår som en seks-trinns pipeline:

compile(astTree):
  1. optimaliser AST-en
  2. mål størrelse og dybde
  3. alloker element-arrayet
  4. fyll fra AST-en
       (tildel next/jump-pekere)
  5. fullfør — sett opp FIN-sentinel
  6. merk elementer som er absorpsjonsegnede

Den flate formen er valgt av en enkel grunn: eksekutoren må traversere mønsteret mange ganger per partisjon, og et sammenhengende indeksadresserbart array er den billigste datastrukturen å gå gjennom. Trinn 1 og 6 er de interessante — trinn 1 fordi det avgjør hvor stort arrayet blir, og trinn 6 fordi det avgjør om absorpsjonsoptimaliseringen i §2.5 i det hele tatt vil aktiveres.

AST-optimalisering

Optimalisering lønner seg to ganger: én gang i det statiske elementantallet til det flate arrayet, og én gang til i hver rad behandlet ved kjøretid. Hver transformasjon reduserer tilstandsrommet kjøretiden må enumerere. Optimalisatoren anvender åtte omskrivingsregler i rekkefølge til AST-en slutter å endre seg:

SEQ-flating

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

Sammenslåing av påfølgende variabler

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

Sammenslåing av påfølgende grupper

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

Sammenslåing av påfølgende ALT

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

Prefiks/suffiks-absorpsjon

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

ALT-flating og dedup

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

Kvantifikatormultiplikasjon

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

Pakking ut av enkelt barn

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

Kvantifikatormultiplikasjon er den eneste transformasjonen som krever en sikkerhetssjekk: optimalisatoren kollapser bare i tre trygge tilfeller — begge kvantifikatorer ubegrenset ((A+)+ → A+), ytre eksakt ((A{2,3}){5} → A{10,15}), eller barnet trivielt {1,1} ((A){2,5} → A{2,5}). Andre kombinasjoner kan innføre hull den flate formen ville oversett — f.eks. (A{2}){2,3} aksepterer kun {4, 6}, men en naiv A{4,6} ville også akseptere 5 — så optimalisatoren lar dem være urørt.

Elementform

Hvert element i det flate arrayet representerer én enkelt posisjon i mønsteret. Det er fem logiske typer: en variabelreferanse (den eneste typen som konsumerer en rad); markører for gruppestart og gruppeslutt, som åpner og lukker et parentesgruppert delmønster; en altereringsmarkør, som leder en liste av grener; og en sluttmarkør ved slutten av mønsteret.

Hvert element bærer også en dybde (gruppenestningsnivået), kvantifikatoren (et min- og makstall for repetisjon, muligens uendelig) og to overgangspekere — next, "hvor man går etter å ha konsumert dette elementet", og jump, "hvor man hopper til" (brukt av alternering for å lenke grener, av gruppestart for å hoppe over kroppen når kvantifikatoren tillater null, og av gruppeslutt for å løkke tilbake til kroppen).

For PATTERN ((A B)+) ser det kompilerte arrayet slik ut:

PATTERN ((A B)+) compiles to:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (åpner gruppen; jump hopper
     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 gruppen; jump løkker tilbake)

[4] FIN    mønster komplett

Mønsteret leses fra venstre mot høyre via next, med jump som håndterer de ikke-lineære kantene. Ved idx 3 peker END sin jump tilbake til idx 1, og det er slik den ubegrensede ytre kvantifikatoren løkker; ved idx 0 ville BEGIN sin jump hoppe forbi END til idx 4 hvis gruppen var valgfri. Kjøretiden trenger aldri å konstruere en graf ved kjøretid — den følger bare disse to pekerne mens den går gjennom arrayet.

Per-element-attributter

Utover form bærer hvert element fire logiske attributter som styrer kjøretidens oppførsel ved den posisjonen:

Motvillig

Snur rekkefølgen for kvantifikatorekspansjon. Grådige kvantifikatorer prøver "løkk igjen" før "avslutt"; motvillige kvantifikatorer prøver "avslutt" først. Båret av variabelen for A+?; båret av gruppens BEGIN og END for ((…)+?).

Tomgangsløkkbar

Settes på gruppeslutt hvis kropp er nullbar ((A?)*, (A? B?)+, (A | B*)). Forteller kjøretiden å legge til en fast-forward-utgang ved siden av den normale løkk-tilbake, slik at syklusvakten ikke dreper legitime treff i grupper som kan produsere tomme iterasjoner.

I-absorberbar-region

Merker hvert element som ligger innenfor en absorpsjonskvalifisert region — brukt av kjøretiden til å spore om gjeldende tilstand fortsatt er i trygt terreng.

Absorpsjons-sammenligningspunkt

Merker det spesifikke elementet hvor absorpsjonssammenligninger skal kjøres. For et enkelt A+ lander det på variabelen; for en ubegrenset gruppe som (A B)+ lander det kun på gruppeslutten.

Skillet mellom "i-region" og "sammenligningspunkt" er viktig fordi absorpsjon kun gir mening på punkter der iterasjoner lukkes. Inne i kroppen til (A B)+ er kjøretiden midt i en iterasjon og tellingen har ikke nådd sin endelige verdi for den runden; å sammenligne her ville bety å sammenligne uforenlige verdier. Tilstanden må nå gruppeslutten før kjøretiden kan avgjøre. Det første attributtet sier derfor "du er fortsatt i absorberbart terreng"; det andre sier "du har nådd sammenligningspunktet — sjekk nå".

Absorberbarhetsanalyse

Trinn 6 i kompileringen er det som gir §2.5 sin "samme skjebne"-regel dens kompileringstidsvitne. Avgjørelsen er lagdelt:

isAbsorbable(query):
  hvis SKIP-modus != SKIP PAST LAST ROW
      → return false
  hvis frame-slutt != UNBOUNDED FOLLOWING
      → return false
  hvis noen DEFINE avhenger av match_start
      → return false
  gå gjennom AST-en og marker
  elementer som oppfyller
  et strukturelt tilfelle

De tre første sjekkene er på spørringsnivå: de tilsvarer nøyaktig betingelsene fra §2.7 (utdatasiden: SKIP-modus), bundet ramme (grensen bryter monotonien) og §2.6 (datasiden: FIRST eller forskjøvet LAST i DEFINE). Når noen av dem feiler, setter analysen ingen flagg og absorpsjon er deaktivert for hele spørringen. Når alle passerer, tillater AST-gjennomgangen tre strukturelle former:

Tilfelle 1 — Enkel ubegrenset variabel

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

Hver iterasjon er nøyaktig én rad. En tidligere kontekst sin telling er alltid ≥ en senere sin ved hver delt posisjon.

Tilfelle 2 — Fastlengdegruppe, ubegrenset ytre

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

Hvert barn har min == max, så kroppen er semantisk ekvivalent med sin utrullede {1,1}-form — (A B{2})+ oppfører seg som (A B B)+. Hver iterasjon konsumerer et fast antall rader; tellingsdominans gjelder fortsatt.

Tilfelle 3 — Gruppe hvis kropp starter med en ubegrenset variabel

(A+ B)+

Den ledende ubegrensede variabelen er selv absorberbar (Tilfelle 1) og skjermer tidligere kontekster. Absorpsjon stopper så snart tilstanden beveger seg forbi A — resten av kroppen har ingen monotonigaranti, så flagg settes kun på A.

De strukturelle tilfellene som ikke dekkes av disse tre formene, er like lærerike. A B+ kan ikke absorberes av den nåværende regelen fordi den ledende A konsumerer en rad før den ubegrensede delen begynner, så kontekster som starter én rad fra hverandre, er på forskjellige posisjoner inne i den ubegrensede kroppen. (En oppfølgende "PREFIX absorption"-utvidelse som håndterer fastlengdeprefikser via en skyggesti, er designet og planlagt for en egen patch.) Motvillige kvantifikatorer som A+? er ekskludert ved konstruksjon: absorpsjonsregelen antar grådig semantikk, der lengre treff subsumerer kortere, og motvillig matching reverserer den retningen.

Resultatet er en per-element-avgjørelse i stedet for en per-mønster-avgjørelse. En enkelt spørringsplan kan ha absorpsjon aktivert for den ledende A+ i mønstre som (A+ B+ C) eller (A+ B+)+ — sistnevnte er bare Tilfelle 3 anvendt på det ledende elementet — og deaktivert for alt etter; kjøretiden konsulterer bare sammenligningspunkt-attributtet på gjeldende tilstands element hver gang den vurderer en absorpsjonspass. Når en tilstand beveger seg inn i en ikke-absorberbar region, er absorpsjon permanent av for den tilstanden — nøyaktig det §2.5 og §2.6 krever skal være sant på algoritmisk nivå.

3.3 Navigasjon — 1-slot tuppelbyttet

DEFINE-uttrykk er ordinære SQL-uttrykk evaluert mot en rad, men de kan inneholde PREV, NEXT, FIRST eller LAST — referanser som peker på forskjellige rader. Selve radene er allerede bufret i vinduets tuplestore; det eksekutoren fortsatt må håndtere, er tuppel-sloten SQL-uttrykksmaskineriet leser fra, siden kolonnereferanser inne i uttrykket er bundet til en slot ved plantid. Implementasjonen gjenbruker en enkelt navigasjonsslot for hvert navigasjonskall: sloten byttes inn før det indre uttrykket evalueres, og gjenopprettes etterpå, så resten av SQL-uttrykksmaskineriet aldri merker forskjellen.

Modellen eksekutoren ser, er liten: det er en gjeldende rad-slot som holder raden DEFINE-uttrykket evalueres mot, og en navigasjonsslot kjøretiden kan omdirigere midlertidig til en annen rad. Rundt et hvilket som helst navigasjonskall setter kjøretiden opp navigasjonsloten, evaluerer det indre uttrykket som om det leste gjeldende rad, og gjenoppretter deretter den opprinnelige raden. Pseudokode:

eval_navigation(call):
  targetPos = compute_target_position(call)
  hvis targetPos er utenfor sitt gyldige område:
      return NULL

  lagre current_row_slot
  hent rad ved targetPos
    inn i current_row_slot
  result = eval_inner_expression()
  gjenopprett current_row_slot
  return result

Trikset er at det er nøyaktig én slot å lagre og gjenopprette. Det indre uttrykket — uansett hva det er, inkludert aritmetikk, funksjonskall eller andre kolonnereferanser — kjører mot den byttede sloten via samme evalueringssti den ville brukt for gjeldende rad. Ingen alternativ evaluator, ingen skyggeslot, ingen tuppelkopi.

Sammensatt navigasjon flates ut ved parsetid slik at byttet fortsatt skjer én gang. PREV(FIRST(price)) gjenkjennes som en to-trinns navigasjon — "gå til den første treffraden, og steg deretter én rad tidligere" — og lagres som ett enkelt navigasjonskall med en sammensatt type. Kjøretiden beregner målposisjonen i to trinn, men utfører kun ett slotbytte for å hente den endelige raden:

compute_target_position(call):

  # relativ til nåværende rad
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

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

  # sammensatt: match-rel, så skritt
  PREV(FIRST(n), m):
      return (matchStart + n) − m
  NEXT(FIRST(n), m):
      return (matchStart + n) + m
  PREV(LAST(n), m):
      return (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      return (lastMatchedRow − n) + m

  valider mot riktig område
  (match-område for FIRST/LAST indre,
   partisjonsområde for ytre skritt)

En posisjonsbuffer kortslutter tuplestore-hentingen når flere navigasjonskall i samme DEFINE peker på samme rad — vanlig i uttrykk som price > PREV(price) AND volume > PREV(volume) der begge kall løses til forrige rad. Bufferet lagrer kun "siste hentede posisjon", og selve byttet forblir én enkelt operasjon.

Klassifiseringen av navigasjonskall er planleggerens bidrag til absorpsjonsavgjørelsen. Planleggeren går gjennom hvert DEFINE-uttrykk og sorterer hver variabel i en av to bøtter, basert på om alle kontekster vil regne ut samme Boolean på samme rad, eller hver kontekst vil regne ut sin egen. Bøtten bestemmer to ting ved kjøretid: hvor ofte variabelen evalueres (én gang delt, eller én gang per berørt kontekst — §3.5 Fase 1), og om den omsluttende tilstanden er kvalifisert for kontekstabsorpsjon (§2.5 vs §2.6).

Klassifiseringen utføres ved plantid og lagres ved siden av hver DEFINE-variabel, så kjøretiden bruker ingen tid på å avgjøre — den leser bare bøtten for hver variabel når den behandler en rad.

Retensjonsbudsjett

Navigasjon strekker seg inn i rader vindusfunksjonsmaskineriet ellers har strømmet forbi. For å holde disse radene tilgjengelige, er eksekutoren bygget på toppen av en tuplestore som beholder et glidende vindu av nylige rader; spørsmålet er hvor bredt det vinduet må være. Patchen avgjør ved kompileringstid, ut fra to komplementære forskyvninger:

Tilbakeblikkbudsjett

Hvor langt bakover fra gjeldende rad et hvilket som helst DEFINE-kall kan strekke seg.

Bidragsytere: PREV, LAST med forskyvning, PREV(LAST(...)), NEXT(LAST(...))

Framoverblikk-fra-start-budsjett

Hvor langt fram (eller bakover, når negativ) fra eldste aktive kontekst sin treffstart et hvilket som helst DEFINE-kall kan strekke seg.

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

Ved kjøretid settes tuplestorens trimmemerke til den tidligere av to posisjoner — gjeldende rad minus tilbakeblikkbudsjettet, og eldste aktive konteksts treffstart pluss framoverblikkbudsjettet. Alt før det merket kan ikke nås av noe navigasjonskall i noen aktiv kontekst, og tuplestoren er fri til å droppe det. De to Nav Mark-tellerne EXPLAIN rapporterer (§3.7) — Lookback og Lookahead — er de målte toppene av de to budsjettene, det dypeste eksekutoren noen gang måtte nå i hver retning gjennom spørringens forløp.

3.4 Treffgrenser — SKIP, INITIAL og bundet ramme

Et vellykket treff registreres som en liten bunt med verdier: et gyldighetsflagg, et suksess/feil-flagg, raden treffet starter på, og antall rader det konsumerte. Når gyldighetsflagget er satt, kan etterfølgende spørringer mot eksekutoren — "er denne raden inne i et treff?" — svare i O(1) ved å inspisere bunten. En lengde på null er et reelt utfall, ikke en feil: det representerer et mønster som traff uten å konsumere noen rad, som eksekutoren må skille fra "ingen treff har blitt forsøkt på denne posisjonen ennå".

AFTER MATCH SKIP-klausulen avgjør hvor neste treffforsøk starter. AFTER MATCH SKIP PAST LAST ROW flytter til raden etter treffslutten, og produserer den ikke-overlappende utdataen de fleste spørringer ønsker, og aktiverer absorpsjonsoptimaliseringen.

AFTER MATCH SKIP TO NEXT ROW flytter kun til raden etter treffstarten, og tillater overlappende treff; planleggeren deaktiverer derfor absorpsjon for hele spørringsplanen når denne modusen er aktiv.

De to skipmålene standarden også definerer — AFTER MATCH SKIP TO FIRST var og AFTER MATCH SKIP TO LAST var — avhenger av per-treff-historikk som denne patchen ikke beholder. De er ikke til stede i grammatikken i det hele tatt, så parseren reiser en generisk syntaksfeil hvis en av dem oppgis.

Det samme gjelder SEEK, spec-alternativet til INITIAL. Under SEEK kan et treffforsøk som starter på rad R, lykkes på en hvilken som helst rad fra R til slutten av rammen, ikke bare på R selv. Patchen implementerer kun INITIAL: hvert mulig treff forankres på en spesifikk rad. Parseren reiser en feil hvis SEEK forespørres. Bundne rammer får sin egen behandling — når brukeren skriver ROWS BETWEEN CURRENT ROW AND N FOLLOWING i stedet for UNBOUNDED FOLLOWING, kortslutter eksekutoren enhver kontekst hvis treff har nådd grensen, ved å tvinge fram en mismatch, og absorpsjon deaktiveres fordi grensen bryter monotoniantakelsen absorpsjon hviler på.

3.5 Trefase-per-rad-motoren

Eksekutorens per-rad-driver påkalles av den omsluttende vindusfunksjonsmaskinen når den må vite om en gitt rad tilhører en treffende ramme. Driveren finner eller oppretter konteksten for gjeldende startposisjon, evaluerer hvert DEFINE-predikat én gang mot gjeldende rad for å produsere et per-variabel boolsk array, og driver deretter NFA-en framover én rad. Selve framoverstrekket er tre faser i en fast rekkefølge — Match, Absorb, Advance — pakket inn i samme ytre løkke:

processRow(currentPos):

  # Fase 1 — MATCH (konvergens)
  for hver kontekst:
      hvis kontekst overskrider begrenset frame:
          tving mismatch (avslutt tidlig)
          continue
      hvis matchStartRow avviker fra
         delt evalueringsposisjon:
          re-evaluer match-start-
          avhengige DEFINE-vars (§3.3)
      match(context, varMatched)

  # Fase 2 — ABSORB
  hvis mønster er absorberbart:
      oppfrisk hver kontekstens flagg
      absorb_contexts()

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

Rekkefølgen er ikke et stilistisk valg. Match må kjøre først fordi absorpsjon sammenligner post-match-tellinger; å kjøre Absorb før Match ville sammenligne tilstander som er i ferd med å dø. Advance må kjøre sist fordi det er den eneste fasen som oppretter nye tilstander — den utvider hver overlevende tilstand gjennom epsilon-overganger til hver enkelt når en variabel som venter på neste rad. Å kjøre Absorb etter Advance ville bety å sammenligne divergerte etterfølgere, og bomme på punktet der tilstandene er mest renhårig sammenlignbare.

Fase 1 — Match

Match er en "konvergens"-fase: tilstander overlever enten med en inkrementert telling, eller dør. Et subtilt poeng er at for variabler som sitter i en absorberbar region, utfører Match også en liten mengde framoverprogresjon, slik at Absorb kan sammenligne rent. Dekkbetingelsen utløses bare ved det absorberbare sammenligningspunktet — END av den ubegrensede gruppen — så tilstander som nettopp har truffet midt-iterasjon-variabler (som B inne i (A B)+), må gås opp til det sammenligningspunktet under selve Match; ellers finner Absorb ingenting kvalifisert å sammenligne og optimaliseringen aktiveres aldri.

match(context, varMatched):
  for hver tilstand i kontekst:
      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 fremoverskritt så neste
      # fase kan sammenligne ved
      # sammenligningspunkt-elementet
      # i stedet for midt-iterasjon.
      hvis elem er in-region men ikke
         sammenligningspunktet,
         og nådde sitt max-antall,
         og elem.next er en group end:

          gå END-kjeden:
            øk ytre gruppe-antall
            før state.elemIdx fram til END
            fortsett så lenge in-region,
              must-exit, og next er END
          (stopper ved sammenligningspunktet
           eller ved et fortsatt loopbart element)

End-kjede-gjennomgangen er det som gjør nestede fastlengdegrupper absorberbare. I ((A B){2})+, når B når sin maks (B er {1,1}), må den indre gruppens telling inkrementeres; hvis den tellingen også når sin maks — lukker den indre {2} — må også den ytre gruppens telling inkrementeres, og så videre, til tilstanden lander på det ytterste absorpsjonspunktet — END av den ubegrensede ytre gruppen (+). Å gjøre dette arbeidet i Match lar Absorb sammenligne mot kontekster som allerede har konsolidert sine post-iterasjon-tellinger.

Fase 2 — Absorb

Absorb-passet går gjennom kontekster fra nyest (hale) til eldst (hode). For hver pågående kontekst som er fullt absorberbar, skanner det bakover etter en eldre pågående kontekst som dekker den, og frigjør den nyere hvis funnet. Siden kontekster holdes i opprettelsesrekkefølge og hver rad oppretter høyst én kontekst, betyr "nyere" og "eldre" virkelig "startet senere" og "startet tidligere".

absorb_contexts():
  for ctx fra halen og bakover:
      hvis ctx er ferdig
         eller har en ikke-absorberbar tilstand:
          hopp over
      for older fra ctx.prev og bakover:
          hvis older er ferdig
             eller ikke har absorberbar tilstand:
              hopp over
          hvis covered(older, ctx):
              free(ctx)
              registrer absorpsjonslengde
              break

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

To mikrobeslutninger følger av dette. Det første er at dekksjekken avviser umiddelbart hvis noen tilstand i den nyere konteksten sitter et annet sted enn et sammenligningspunkt — å sammenligne på ikke-dommepunkter ville ikke være en meningsfull sammenligning.

Det andre er det asymmetriske flaggparet på hver kontekst: has-absorbable-state svarer "kunne denne konteksten absorbere en nyere?" og er monotont (det kan bare gå sann→usann etter hvert som tilstander dør), mens all-states-absorbable svarer "kunne denne konteksten absorberes?" og er dynamisk (det vipper tilbake til sant når en ikke-absorberbar tilstand fjernes). Begge flagg sjekkes i konstant tid før dekkskanningen i det hele tatt starter, så absorpsjon betaler sin fulle kostnad bare på kontekster som har en reell sjanse til å bli absorbert.

Fase 3 — Advance

Advance er "divergens"-fasen: hver overlevende tilstand utvides gjennom epsilon-overganger til hver gren når enten en variabel som venter på neste rad, eller FIN-sentinellen. Utvidelsen er dybde-først, og rekkefølgen søskengrener gås i, er det som gjør at standardens preferanseregel faktisk tar effekt — den leksikalsk første grenen legges alltid til først, og dedupliseringstrinnet ved tilstandsinnsetting forkaster stille ekvivalente senere tillegg.

advance(context, currentPos):
  trekk ut alle nåværende tilstander;
  bygg ctx.states på nytt fra bunnen
  for hver tilstand i leksikalsk rekkefølge:
      tøm bitmap-en for besøkte elementer
      advance_state(state)   # DFS

      # Preferanse: så snart en DFS
      # når FIN, er gjenværende tilstander
      # mindre foretrukket og kan slippes.
      hvis FIN nådd og tilstander gjenstår:
          frigi resten
          break

advance_state(state):
  gå via state.elemIdx,
  rekurser gjennom:
    ALT-grener (i rekkefølge),
    BEGIN (gå inn i gruppen; pluss valgfri
           hopp-sti hvis min = 0),
    END (loop back / exit / fast-forward —
         se under),
    FIN (registrer matchEndRow,
         lagre matchedState, og beskjær
         senere kontekster innenfor denne
         kandidatens område — se under),
  stopper ved hver variabel som påtreffes:
      legg tilstand til ctx.states
      (dedupliserer etter elemIdx + counts)

Å registrere en tilstand som nådde FIN, gjør mer enn bare å bokmerke kandidattreffet. Under AFTER MATCH SKIP PAST LAST ROW må neste rapporterbare treff starte strengt etter det gjeldende — så i det øyeblikket en kandidat registreres, beskjæres umiddelbart hver etterfølgende kontekst hvis startrad faller innenfor kandidatens område, selv om konteksten som traff FIN, kan fortsette å søke etter et lengre treff gjennom grådig fallback.

Beskjæringen er trygg fordi uansett hvordan det søket avsluttes (et lengre treff erstatter kandidaten, eller kandidaten består), startet alle de beskårne kontekstene innenfor et område neste rapporterbare treff må hoppe forbi, og kunne derfor aldri produsere egne utdata.

Dette er ett av to FIN-tidsbeskjæringstrinn — det andre, beskrevet tidligere i denne seksjonen som en del av Advance, forkaster leksikalsk underordnede tilstander inne i samme kontekst.

Den vanskeligste per-element-logikken lever i END-håndtereren. Når en gruppes iterasjonstelling er under nedre grense, må kjøretiden løkke tilbake; når den er på eller over øvre grense, må den avslutte; i mellom er begge alternativer gyldige og kvantifikatorens grådighet bestemmer hvilket som prøves først:

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

  hvis count < elem.min:
      løkk tilbake inn i kroppen
      hvis elem er empty-loopable:
          # nullable kropp, se §3.2
          klon også en fast-forward-
          tilstand som forlater gruppen
          med count tilfredsstilt
          (redder legitime matches
           som cycle guard
           ellers ville drepe)

  ellers hvis count >= elem.max:
      nullstill counts på denne dybden
      avslutt via next
      (END→END: øk ytre
       ENDs count)

  ellers:
      # min <= count < max: fork
      bygg en exit-tilstand
      (counts på denne dybden nullstilt)
      hvis greedy:
          loop først, så exit
          # foretrekk lengre
      ellers (reluctant):
          exit først
          hvis exit nådde FIN:
              slipp loopen
              # foretrekk kortere
          ellers loop som nummer to

Hver tilstand som legges til en kontekst, går gjennom en dedupliseringssjekk som sammenligner dens posisjon og tellinger med den eksisterende tilstandslisten. Siden Advance behandler grener i DFS-rekkefølge, lander tilstanden fra den første grenen i en hvilken som helst alternering først — og enhver senere gren som produserer samme posisjon og tellinger, avvises ved innsetting. Det er nøyaktig det §2.4 sin leksikalsk-rekkefølge-regel ber om, implementert i bunnen av kjøretiden uten et eget pass.

Tomgangsløkkbare grupper

Et subtilt tilfelle kjøretiden må desarmere, er den nullbare gruppen — en gruppe hvis kropp kan treffe null rader fordi hvert barn i kroppen selv er valgfritt. Mønstre som (A?)*, (A? B?)+ og (A | B*) har alle denne egenskapen: avhengig av dataene kan kroppen fullføre en iterasjon uten å konsumere noen rad i det hele tatt. Det er greit i prinsippet, men det skaper en reell fare for NFA-ens epsilon-utvidelse. Hvis kroppen produserer et tomt treff, løkker END-elementet tilbake til BEGIN, kroppen produserer igjen et tomt treff, BEGIN løkker til END, og så videre. Uten noe som stopper det, ville Advance sin DFS aldri terminert.

Kjøretiden stopper det med et besøkt-element-bitkart (én bit per mønsterelement), nullstilt før hver tilstands DFS-utvidelse: så snart noe element besøkes for andre gang innenfor samme utvidelse, forlates den stien. Syklusvakten er ubetinget og billig, men har en bivirkning — den kan også forlate stier som burde nå nedre grense gjennom legitime tomme iterasjoner. Ta (A?){2,3} uten at A treffer noe sted i radstrømmen:

ønsket atferd:
  iter 1: A? treffer null rader
          → END, count = 1 (under min)
  iter 2: A? treffer null rader
          → END, count = 2 (oppfyller min)
  avslutt med et nulllengdetreff

hva syklusvakten gjør alene:
  iter 1: A? hoppes over → END, count = 1
          → løkk tilbake til BEGIN
  iter 2: BEGIN allerede besøkt
          → DFS avbrytes
  telling når aldri min
  → treff feiler (feil)

Løsningen avgjøres ved kompileringstid og handles på ved kjøretid. Når planleggeren ser en gruppe hvis kropp er nullbar, merker den END-elementet til den gruppen som tomgangsløkkbar. Ved kjøretid, når END-håndtereren er i ferd med å løkke tilbake fordi iterasjonstellingen fortsatt er under nedre grense, forteller tomgangsløkk-merket den å klone en ekstra fast-forward-tilstand ved siden av den normale løkk-tilbake-stien:

advance_end (count under min):

  primær sti:
    løkk tilbake inn i kroppen
    (holder døra åpen for et reelt,
     ikke-tomt match i neste
     iterasjon)

  hvis elem er empty-loopable:
    fast-forward-sti:
      nullstill denne dybdens count
      forlat gruppen via next,
      der gjenværende krevde
      iterasjoner behandles som tomme matches

De to stiene spiller komplementære roller. Den primære løkk-tilbake fanger tilfellet der kroppen fortsatt har reelle treff å produsere senere — for eksempel i (A?){2,3} fulgt av data der A kun treffer på senere rader, er det løkk-tilbake som lar andre og tredje iterasjon finne ikke-tomme treff. Fast-forward fanger tilfellet der kroppen aldri produserer noe: den omgår syklusvakten ved å forlate gruppen helt, erklærer "resten av de påkrevde iterasjonene er tomme" og lar treffet lykkes med en nulllengdekropp. Begge tilstander legges til konteksten; den som utvider seg vellykket, vinner, og dedupliseringssjekken ved innsettingstid hindrer at noen sti spawner mer enn sin del av tilstander.

Utover syklusvakten finnes ett til oppstartstriks som disambiguerer null-rad-utfall ved selve starten av en kontekst. Kontekstopprettingstrinnet ved hver mulige startrad kjører en innledende advance gjennom epsilon-overganger før noen rad konsumeres, ved bruk av en posisjon én rad før den faktiske starten. Enhver sti som når FIN-sentinellen kun gjennom epsilon-overganger — uten å konsumere en rad — produserer derfor en sluttposisjon mindre enn startposisjonen; den negativ-spenn-koordinaten, kombinert med om FIN faktisk ble nådd, koder forskjellen mellom et tomt treff (lengde-0-treff akseptert) og en ikke-treffende start uten å trenge et eget flagg.

3.6 Hvordan tilstandsrommet holdes begrenset

Kjøretidens linearitet er ikke resultatet av én enkelt optimalisering. Det er den kumulative effekten av et lagdelt sett beskjæringsregler, der hver enkelt fanger en annen årsak til tilstandsromvekst på et annet punkt i per-rad-syklusen. Noen avgjøres ved kompileringstid og bare konsulteres ved kjøretid; andre utløses dynamisk. Noen dreper individuelle tilstander; andre dreper hele kontekster. Seksjonene over introduserte hver av dem i kontekst; tabellen nedenfor samler dem på én side.

Feilet predikat Match

Variabeltilstander hvis DEFINE evaluerte falsk på gjeldende rad — døde grener.

Innebygd end-chain-advance Match

Variabler som har truffet sin makstelling og ellers ville etterlate tilstanden midt i en iterasjon; rykkes fram gjennom fastlengdegruppe-slutt slik at absorpsjon kan sammenligne på riktig punkt.

Kontekstabsorpsjon Absorb

Nyere kontekster hvis hver tilstand er dekket av en eldre konteksts tilstand med høyere telling — se §2.5 for den konseptuelle regelen, §3.2 for kompileringstidskvalifisering, §3.5 for per-par-sjekken.

Tilstandsdeduplisering Advance

Tilstander nådd via forskjellige DFS-grener som ender på samme posisjon med samme tellinger — bare den første (leksikalsk tidligste) overlever; senere ekvivalenter forkastes stille, noe som også er hvordan preferanse håndheves (§2.4).

FIN tidlig terminering (innenfor kontekst) Advance

Tilstander fortsatt ventende i DFS-køen når én gren når FIN — etter leksikalsk rekkefølge er alle gjenværende tilstander mindre foretrukket og kan forkastes umiddelbart.

Kandidattreff-beskjæring (på tvers av kontekster) On FIN

Andre kontekster hvis startrad faller innenfor kandidattreffets område — konteksten som traff FIN, kan fortsatt fortsette å søke etter et lengre treff (grådig fallback), men under AFTER MATCH SKIP PAST LAST ROW kan ingen kontekst innenfor kandidatens område lenger produsere en rapporterbar utdata, uavhengig av hvordan det søket ender, og beskjæres umiddelbart.

Syklusvakt Advance

Epsilon-utvidelser som besøker samme mønsterelement på nytt innenfor samme DFS — ville ellers løkke for alltid i nullbare grupper.

Tomgangsløkk fast-forward Advance

Legitime tomgangsiterasjons-treff som syklusvakten ville drept i nullbare grupper — omgår syklusen ved å forlate gruppen med gjenværende påkrevde iterasjoner erklært tomme.

Bundet-ramme-avskjæring Match

Kontekster hvis treff har nådd den brukerspesifiserte rammeøvre grensen — tvinges til mismatch slik at de ikke kan strekke seg utover den (§3.4).

Å lese oppføringene etter fasebadge sporer en konteksts levetid: beskjæring utløses ved hver rad gjennom de tre hovedfasene (Match, Absorb, Advance), og igjen ved treffullføring (On FIN). Å lese beskrivelsene grupperer i stedet reglene etter hva de retter seg mot: døde grener, overflødige kontekster, ekvivalente tilstander, uendelige løkker og overstrekking forbi brukerpålagte grenser.

Ingen enkelt regel alene ville være nok. Syklusvakten alene ville drept legitime treff i nullbare grupper; tomgangsløkk-fast-forward alene ville ikke stoppet uendelige epsilon-løkker; absorpsjon alene ville overkonsolidert når DEFINE refererer treffstart; deduplisering alene ville ikke fjernet overflødige kontekster, kun overflødige tilstander. Kjøretiden holder seg lineær i tilfellene som betyr noe — PATTERN (A+ B+ C+ D) på 100 000 rader, posterens panel ③-benchmark — bare fordi hvert lag fanger det lagene over det bommer på.

3.7 EXPLAIN-utdata

EXPLAIN ANALYZE på en spørring med RPR eksponerer NFA-nivå-statistikk som ikke er til stede for ordinære vindusfunksjoner. Tre grupper tellere emitteres ved siden av vindusoperatoren:

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
  (only when the query uses FIRST,
   PREV(FIRST(...)), or NEXT(FIRST(...)))

Peak og total er direkte instrumentering av kjøretiden: hvor mange tilstander noen gang var aktive samtidig, hvor mange som ble opprettet i løpet av spørringens levetid, og hvor mange som ble slått sammen ved deduplisering. Trefflengdehistogrammene skiller fire utfall — vellykkede treff, mislykkede treffforsøk, absorberte kontekster og kontekster som ble beskåret (skipped) uten å bli evaluert — og å rapportere dem med min/max/avg gjør ytelsespatologier synlige med et blikk: en sunn kjøring viser de fleste kontekstene som enten treffende eller absorberte, med små mislykkede lengder.

De to Nav Mark-tellerne rapporterer tuplestore-retensjonsbudsjettet §3.3 utleder ved kompileringstid. Lookback er det dypeste bakoverstrekket på tvers av PREV, LAST med forskyvning og de sammensatte formene med indre LAST; Lookahead er det dypeste framoverstrekket (eller bakoverstrekket, når negativt) målt fra eldste aktive konteksts treffstart, bidratt av FIRST og de sammensatte formene med indre FIRST.

Hver teller skrives ut som et fast heltall når forskyvningen er en konstant, "runtime" når forskyvningen er et ikke-konstant uttrykk som må evalueres hvert kall, og "retain all" når kjøretiden trenger et ubegrenset budsjett. Lookahead emitteres bare når spørringen faktisk bruker treffstart-relativ navigasjon.

Sammen gjør disse tellerne det mulig å feilsøke RPR-ytelse uten å feste gdb til backenden.

Utover tellerne gjengir EXPLAIN også trofast de opprinnelige PATTERN- og DEFINE-klausulene, inkludert motvillige kvantifikatorer, grupperepetisjon og AFTER MATCH SKIP-alternativet. Implementasjonen legger en del arbeid i å gjøre denne rundturen stabil slik at pg_dump og pg_upgrade kan bevare RPR-objekter uten semantisk drift — regresjonssuiten under rpr_explain verifiserer det tilfelle for tilfelle (se §4).

§4. Tester — dekningsoversikt

Patchen leveres med fem regresjonssuiter som sammen øver hvert lag beskrevet i §3 — omtrent 13 000 linjer SQL, hver suite fokusert på et annet anliggende. Splittet er bevisst: å holde parser-anliggender, kjøretidskorrekthet, planleggerinteraksjoner og utdataformatering i separate filer gjør feil lettere å lokalisere og hindrer at en urelatert endring i ett lag utilsiktet ugyldiggjør tester i et annet. De fem suitene er:

rpr

Helhetlig spørringssemantikk — realistiske vindusscenarioer på syntetiske aksjedata (V-form, W-form, sammenhengende stigninger, reverseringer).

rpr_base

Parser-laget — nøkkelordaksept, syntaksformer, kvantifikatorer, navigasjonsparsing, feilmeldinger og pg_dump/pg_upgrade-rundturstabilitet.

rpr_nfa

NFA-kjøretid — trefase-løkken, absorpsjon i hver absorberbar form, og kontekstlivssyklus-kanttilfeller.

rpr_explain

Utdataformatering — NFA-statistikk, mønsterdeparse, identifikatorsitering, formatstabilitet på tvers av lasting.

rpr_integration

Planleggerinteraksjoner — vakter som hindrer urelaterte vindusoptimaliseringer fra å korrumpere RPR-semantikk.

4.1 rpr — helhetlige scenarioer

Scenariosuiten er testsettets offentlige ansikt: den bruker et syntetisk aksjekurs-datasett på rundt 1 600 rader og kjører realistiske spørringer mot det — V-form-gjenoppretting, W-form (dobbel bunn), sammenhengende stigninger og fall, reverseringsmønstre, multisymbol-partisjoner. Det er den eneste suiten der inn- og utdata leses som spørringer en bruker faktisk kunne skrive; de andre er bevisst reduktive, fokusert på ett lag av gangen.

Siden disse spørringene kombinerer hvert lag (parser, planlegger, eksekutor, EXPLAIN), forteller en enkelt feil i rpr sjelden hvor feilen ligger. De fire suitene som følger, er bisekseringen: en feil i rpr pluss en passerende rpr_base utelukker parseren; pluss en passerende rpr_nfa snevrer det inn til scenariospesifikke dataformer; pluss en passerende rpr_integration utelukker planlegger-interferens; og enhver deparse-drift dukker opp i rpr_explain.

4.2 rpr_base — parserflaten

Base-suiten er den største, og den er størst med en grunn: den er ansvarlig for å bevise at hver lovlig syntaksbit i §1.2 faktisk parses, hver ulovlig bit i §1.3 avvises med en nyttig feil, og hver akseptert form overlever en serialiseringsrundtur. Hoveddelen er formet som små fokuserte snutter — én per syntaktisk funksjon — i stedet for lange realistiske spørringer, fordi målet er dekning snarere enn scenarierealisme.

Serialiseringstestene fortjener spesiell oppmerksomhet. RPR-objekter (views, materialiserte views, pg_dump-utdata) må rundturere gjennom katalogrepresentasjonen uten semantisk drift, inkludert subtiliteter som motvillig-flagget på en kvantifikator eller den nøyaktige formen til et sammensatt navigasjonsuttrykk. Et lite sett serialiseringspesifikke objekter (rpr_serial_v*-viewene og deres underliggende tabeller) blir bevisst stående ved slutten av kjøringen, slik at den omsluttende regresjonsinfrastrukturen kan plukke dem opp og øve pg_dump og pg_upgrade mot dem. Resten av teststillaset slettes som vanlig. Feil fanget på denne måten (som at et motvillig-flagg går tapt på tvers av deparse og re-parse) dukker bare opp når rundturen utøves helhetlig.

4.3 rpr_nfa — kjøretidsmotoren

Dette er suiten som øver hver mekanisme beskrevet i §3.5 og §3.6. Testene følger et konsistent mønster: en inndatatabell hvor radene er eksplisitte boolske array som erklærer hvilke DEFINE-variabler som treffer på hver rad, paret med et mønster som sonderer en spesifikk kjøretidsoppførsel. Boolsk-array-idiomet kobler kjøretidstesten fra DEFINE-evalueringsmaskineriet — det som testes, er "gitt at disse variablene treffer her, produserer NFA-løkken det forventede treffspennet?" snarere enn "regner DEFINE-uttrykksevaluatoren riktig ut disse boolske verdiene?" DEFINE-evaluatoren testes andre steder (rpr_base for parsing, rpr for helhetlig oppførsel).

En typisk testoppsett ser slik ut — en kolonne av variabelnavn-arrays der hver oppføring sier hvilke DEFINE-variabler som utløses på den raden, og et mønster hvis DEFINE-klausuler tester for de navnene 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));

Å lese array-kolonnen nedover er å lese testscenarioet direkte. Rader 2 og 3 bærer begge navn — A og B utløses begge der, så NFA-en har et reelt valg om hvor den skal bytte fra A-grenen til B-grenen. Det forventede treffet (A på rader 1–3 fulgt av B på rad 4, under standardens grådige preferanse) er fastsatt av de flaggene alene, uten uttrykksevaluering av betydning her — = ANY er bare det trivielle laget som eksponerer array-kolonnen til DEFINE, ikke det testen øver. Å skrive samme scenario med et numerisk predikat (price > PREV(price) og lignende) ville sammenflette NFA-testen med predikatevaluatorens oppførsel; array-idiomet holder de to rent atskilt, og en feil her peker direkte på NFA-løkken.

Absorpsjonsdekningen er spesielt grundig, fordi absorpsjon er optimaliseringen mest sannsynlig til stille å produsere gale svar hvis den aktiveres når den ikke burde. Tester dekker hver form fra §3.2 sin tilfelleanalyse:

• enkel ubegrenset variabel (A+) — den kanoniske N-til-1-kollapsen;
• fastlengdegrupper ((A B)+, (A B{2})+, tre-nivå nestet ((A (B C){2}){2})+);
• ledende ubegrenset variabel med et fast suffiks (A+ B) — bare den ledende A+ bærer absorpsjonsflagg, suffikset ikke;
• per-gren-absorpsjon inne i en alternering (B+ C | B+ D);
• flere ubegrensede variabler (A+ B+) — bare den ledende er absorberbar;
• motvillige kvantifikatorer (A+?) — verifisert å være ekskludert fra absorpsjon;
• ikke-ledende ubegrenset (A B+) — verifisert å være ekskludert.

Utover absorpsjon dekker suiten kontekstlivssyklusen: overlappende kontekster under AFTER MATCH SKIP TO NEXT ROW, opprydding av feilede kontekster midt i strømmen, partisjonsslutt-finalisering av ufullstendige kontekster, og kontekster som påtreffes etter at et kandidattreff allerede er registrert i hovedkonteksten. Hver av disse svarer til en spesifikk beskjæringsregel i §3.6, og testene er skrevet for å feile høylytt hvis regelen feiltolkes (enten ved å la overflødige kontekster være aktive, eller ved å drepe en kontekst som burde ha produsert utdata).

4.4 rpr_explain — utdatastabilitet

EXPLAIN-utdata er en del av den brukervendte kontrakten — tredjepartsverktøy (psql-autofullføring, overvåkingsdashbord, loggskrapere) parser den, og endringer som ser kosmetiske ut, kan ødelegge dem. rpr_explain-suiten verifiserer tre ting:

• NFA-tellere vises på rett sted — per-WindowAgg-statistikken (peak/total/merged states, peak/total/pruned contexts, lengdehistogrammer for matched/mismatched/absorbed/skipped, Nav Mark Lookback, og — når treffstart-relativ navigasjon er i bruk — Nav Mark Lookahead) dukker alle opp under EXPLAIN ANALYZE med de dokumenterte etikettene.
• Mønstre deparses korrekt — hver kvantifikatorform, inkludert motvillige varianter og bundne former; hver alternering; hver gruppe; hver AFTER MATCH SKIP-form; INITIAL; navigasjonskall med forskyvninger; sammensatt navigasjon. Den deparsede teksten må rundturere tilbake gjennom parseren uendret.
• Identifikatorsitering er korrekt — mønstervariabler og DEFINE-uttrykk emitteres med samme siteringsregler som ordinære SQL-identifikatorer, slik at uvanlige variabelnavn ikke ødelegger pg_dump-utdata.

Som rpr_base lar denne suiten bevisst objektene være ved slutten av kjøringen, slik at pg_dump- og pg_upgrade-dekningen også strekker seg til explain-side-artefaktene.

4.5 rpr_integration — planleggerinteraksjoner

PostgreSQLs planlegger har mange optimaliseringer som opererer på vindusspørringer — rammekanonisering, run-condition-pushdown, identisk-vindu-deduplisering, ubrukt-utdata-projeksjon, moving-aggregate inverse transitions — og hver av dem ble designet uten RPR i tankene. De fleste er utrygge å anvende når et vindu har en PATTERN-klausul: rammen er del av treffkontrakten, det treffende utdataet er ikke lenger monotont på noen åpenbar måte, og to vinduer med samme spec, men forskjellige DEFINE-er, produserer genuint forskjellige resultater. Integrasjonssuiten verifiserer at hver av disse optimaliseringene er korrekt deaktivert eller forbigått for RPR-vinduer:

Rammekanonisering

Planleggeren omskriver normalt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING til ROWS UNBOUNDED PRECEDING for monotone aggregater. RPRs ramme er treffspennet, ikke et aggregeringsvindu, og må forbli ordrett.

Run-condition-pushdown

Et monotont WHERE-filter på en vindusfunksjons utdata kan normalt skyves inn i vindusoperatoren som en stopp-betingelse. For RPR ville dette terminere mønstermatching for tidlig, og potensielt kutte av treff midt i en utvidelse.

Vindusdeduplisering (RPR vs ikke-RPR)

To vinduer med identisk ORDER BY og ramme ville normalt bli slått sammen til ett. Et RPR-vindu og et ikke-RPR-vindu kan aldri dele tilstand fordi RPR-siden bærer treffresultater.

Vindusdeduplisering (forskjellig DEFINE)

To RPR-vinduer med samme PATTERN, men forskjellige DEFINE-klausuler produserer forskjellige treff og må forbli distinkte, selv om deres strukturelle form er identisk.

Ubrukt-utdata-projeksjon

Selv om den omsluttende spørringen aldri leser vinduets per-rad-utdata, kan RPR-vinduet ikke fjernes: mønstermatcherens bivirkninger (hvilke rader som er inne i hvilket treff) mater reduserte-ramme-beregninger andre steder i planen.

Moving-aggregate inverse transitions

Vindusaggregater med en invers overgangsfunksjon kan normalt evalueres inkrementelt etter hvert som rammen beveger seg. RPRs reduserte ramme er ikke et glidende vindu; den inverse overgangsstien ville produsert gale resultater.

Mønsteret på tvers av disse testene er det samme: hver gir en ikke-RPR-baseline som utløser optimaliseringen (og verifiserer at EXPLAIN viser at den anvendes), kjører deretter en RPR-spørring av strukturelt lignende form og verifiserer at optimaliseringen ikke anvendes. De to halvdelene sammen beviser at vakten i planleggeren gjør reelt arbeid, ikke godkjenner hver spørring uten reell verifisering.

Denne suiten er også grunnen til at §3.4 er kort. "Treffgrenser"-mekanismene — redusert ramme, SKIP, INITIAL, bundet-ramme-avskjæring — testes operasjonelt andre steder; det rpr_integration verifiserer, er at ingen annen optimalisatorfase tukler med dem på veien gjennom. En passerende rpr_integration er det som lar resten av suitene stole på at inndataene deres når eksekutoren uskadet.