2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition Dypdykk

En guidet tur gjennom ISO/IEC 19075-5 · SQL R020 i PostgreSQL — hva som er bygget, hva som fortsatt mangler, og hvordan det faktisk kjører.

Følgedokument til posteren som vises på PGConf.dev 2026.
Bla gjennom standarden, gå gjennom eksempler, utforsk designet, og kjør deretter en live NFA-simulator med dine egne mønstre.
Diskusjon: pgsql-hackers tråd · nyeste patch (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

AI-foroversatt — feil mulig.

§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 har mye syntaks og semantikk felles (19075-5 nevner noen R020-spesifikke forskjeller i §6.3.3), men de 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 klausuler inne i en vindusspesifikasjon hvis ramme er ROWS BETWEEN CURRENT ROW AND …: PATTERN beskriver et regulært uttrykk over navngitte mønstervariabler, DEFINE oppgir det boolske predikatet som identifiserer hver variabel, og den valgfrie AFTER MATCH SKIP (standard PAST LAST ROW) 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; opptil 240 distinkte mønstervariabler.
Vindusramme
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING eller ROWS BETWEEN CURRENT ROW AND n FOLLOWING med n ≥ 1 (19075-5 §6.10.2); enhver annen ramme avvises, og EXCLUDE NO OTHERS er den eneste eksklusjonen som aksepteres.
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 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.
Navigasjonsnavn
PREV, NEXT, FIRST og LAST skrevet som ukvalifiserte kall inne i DEFINE betyr alltid navigasjon; en brukerfunksjon med samme navn må der være skjemakvalifisert.
Navigasjonsargumenter
For PREV, NEXT, FIRST og LAST må det indre argumentet inneholde minst én kolonnereferanse, og forskyvningen må være en kjøretidskonstant.
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 FIRST var og AFTER MATCH SKIP TO [LAST] var (bart SKIP TO var betyr SKIP TO LAST var). Disse avhenger også av treffhistorikk, siden eksekutoren må kunne peke på raden tilordnet en gitt variabel inne i det nyeste treffet.

De gjenværende elementene er en heterogen hale: nøkkelordet SEEK (alternativet til INITIAL), det tomme mønsteret (), ekskluderingsformen {- … -}, den rekkefølgeufølsomme PERMUTE-operatoren, samt aggregatfunksjoner og underspørringer i DEFINE, som begge for tiden avvises (et variabelkvalifisert aggregat ville også trenge treffhistorikken).

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 på hvilken som helst rad fra gjeldende rad til slutten av den fulle vindusrammen (vs. INITIAL).
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 ALL ROWS PER MATCH-utdataene. Det alternativet gjelder ikke for vinduer (19075-5 §6.3.3 (4)), så i et vindu er syntaksen tillatt (§6.13), men har ingen utdata å virke på.
Regex: ()
Tomt mønster — treffer den tomme sekvensen.
PERMUTE(...)
Rekkefølgeufølsom matching over oppførte variabler. Nøkkelordet gjenkjennes og avvises ("PERMUTE is not supported"); permute kan fortsatt brukes som navn på en mønstervariabel.
Aggregatfunksjoner i DEFINE
Aggregater som SUM, AVG, COUNT er ikke tillatt i DEFINE-predikater. Standarden tillater dem som løpende aggregater over delvis treff; et variabelkvalifisert aggregat som AVG(B.Price) avhenger av samme per-treff-historikk som MEASURES/CLASSIFIER() krever, mens et ukvalifisert aggregat spenner over alle radene i treffet så langt.
Underspørringer i DEFINE
Enhver underspørring i DEFINE avvises. Standarden tillater en som ikke utfører row pattern recognition og ikke refererer noen mønstervariabel; patchen avviser foreløpig mer enn nødvendig.

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 (patchen går lenger og avviser alle underspørringer i DEFINE, som nevnt ovenfor); og RPR kan ikke brukes inne i en rekursiv spørring. Patchen håndhever regelen om ytre referanser ("cannot use outer query column in DEFINE clause") og rekursjonsregelen, den siste for hvert element i en WITH RECURSIVE-klausul. Den avviser også volatile funksjoner og helrads-referanser i DEFINE.

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.

Opprinnelse. Listene over implementerte og ikke-implementerte funksjoner i denne seksjonen gjenspeiler dagens tilstand for patch-serien — spesifikt v55 (2026-11-17).

§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 fem gjennomarbeidede eksempler: et enkelt treff (NFA-bevegelse), alternering, kontekstabsorpsjon i det enkle tilfellet, og to tilfeller der absorpsjon er deaktivert.

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.

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
Tekstregex kollapser til én tilstand per symbol; en rad kan tilfredsstille flere DEFINE-predikater samtidig, så flere tilstander holdes aktive parallelt.

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 (standard n = 1). Look-ahead framover; uvanlig i vindusform siden vinduet er monotont.
FIRST(expr [, n])
Raden n rader etter den første raden i gjeldende treff (standard n = 0, selve den første raden). "Sammenlign med raden som startet dette treffet."
LAST(expr [, n])
Raden n rader før den siste treffraden (standard n = 0). Inne i DEFINE er den siste treffraden gjeldende rad, så LAST(price) leser gjeldende rad.

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 raden FIRST(expr, n) leser (standardverdier n = 0, m = 1). "Hva var verdien rett før dette treffet begynte?"
NEXT(FIRST(expr [, n]) [, m])
Steg m rader fram fra raden FIRST(expr, n) leser. Når lenger inn i treffet uten å avhenge av gjeldende rad.
PREV(LAST(expr [, n]) [, m])
Steg m rader tilbake fra raden LAST(expr, n) leser. "Sammenlign med en rad like før den nyeste treffraden."
NEXT(LAST(expr [, n]) [, m])
Steg m rader fram fra raden LAST(expr, n) leser.

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. Rene PREV og NEXT er relative til gjeldende rad og er alltid trygge; FIRST og forskjøvne varianter av LAST, alene eller inne i en sammensatt PREV/NEXT, er relative til treffgrensene, noe som samspiller med kontekstabsorpsjon: planleggeren deaktiverer da absorpsjon for hele mønsteret. Mekanismen bak det samspillet er temaet i §2.6.

2.3 Eksempel 1 — NFA-bevegelse

Mål med dette eksempeletVise rad-for-rad NFA-tilstandsutvikling på et enkelt, ikke-absorberende mønster. Sporet følger konteksten som startet på rad 0; kontekstene som startet på rad 1–4, løper ved siden av og forkastes av SKIP PAST LAST ROW når treffet dens er registrert.
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:

RadPrisSanne variablerHandling
0100STARTNy kontekst. START treffer og forlater umiddelbart (max=1); tilstanden går videre til UP+.
1110START, UPUP treffer. Framrykningen forgrener seg: én tilstand løkker ved UP, en annen går ut til DOWN+.
2120START, UPUP treffer i den løkkende tilstanden og forgrener på nytt. DOWN-tilstanden fra rad 1 dør (120 ≮ 110).
3115START, DOWNUP feiler på den løkkende tilstanden og dør. DOWN-tilstanden fra rad 2 treffer. Framrykningen forgrener seg: løkk ved DOWN og utgang til #FIN — en treffkandidat over rader 0–3 registreres.
4108START, DOWNDOWN treffer i den løkkende tilstanden og forgrener på nytt; den nye FIN-kandidaten over rader 0–4 erstatter den kortere.
5130START, UPDen løkkende DOWN-tilstanden feiler (130 ≮ 108). Uten aktive tilstander igjen i denne konteksten finaliseres den registrerte kandidaten (rader 0–4) som treffet. Neste forsøk starter på rad 5; START treffer, men partisjonen ender før noen UP.

Hovedpoenget: på rad 3 tilfredsstiller raden både START (alltid sann) og DOWN, men START betyr bare noe for en kontekst som starter på rad 3; i denne konteksten dør den løkkende UP-tilstanden, og bare tilstanden som venter ved DOWN+, rykker fram. 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 siste FIN-kandidaten (rader 0–4) — produsert da DOWN gikk ut på rad 4, og som erstattet kandidaten fra rad 3 — 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:

RadPrisstart_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

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

Mål med dette eksempeletVise hvordan én enkelt kontekst bærer flere parallelle tilstander når én rad tilfredsstiller mer enn ett alternativ — og hvordan standarden løser uavgjorte tilfeller.

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 mønsterrekkefølge, tidligste gren først.

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. Begge rykker deretter fram til DONE, der de møtes.

RadSanne variablerAktive tilstander
RUP, HIGHTilstand A (UP-grenen) og tilstand B (HIGH-grenen) rykker begge fram til DONE med samme tellinger; B er et duplikat av A og forkastes
R+1DONETilstand A treffer DONE og når #FIN

I standardens termer produserer begge grenene et treff av samme lengde over de samme radene, noe som gir 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. Eksekutoren håndhever dette på rad R, ikke ved FIN: den legger til UP-grenens tilstand først, så nfa_append_state_unique() beholder den og forkaster den identiske HIGH-grenens tilstand.

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)

Mål med dette eksempeletVise hvorfor naivt O(n²) totalt tilstandsarbeid blir O(n) under absorpsjon, med O(1) aktive kontekster.

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

RadNaive konteksterMed absorpsjon
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 absorbert
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]

Aktive kontekster faller fra O(n) til O(1), så totalen over partisjonen faller fra O(n²) til O(n). Absorpsjonsregelen som rettferdiggjør forkastingen, er enkel når kvantifikatoren er ubegrenset:

Absorpsjonsregel. To kontekster hvis aktive tilstand står ved samme mønsterelement, der den eldre konteksten har telling ≥ den nyere, har identiske framtider under en ubegrenset kvantifikator. Den nyere konteksten kan forkastes; uansett hvilket treff den til slutt ville funnet, vil den eldre konteksten finne et lengre eller likt.

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:

DagPrisC1 — start tirsdag
price > PREV(price)
C2 — start onsdag
price > PREV(price)
Man$100——
Tir$108$108 > $100 ✓ (akkurat startet)—
Ons$112$112 > $108 ✓$112 > $108 ✓ (akkurat startet)
Tor$116$116 > $112 ✓$116 > $112 ✓
Fre$110$110 > $116 ✗ — finaliser$110 > $116 ✗ — finaliser
Samme skjebne Hver rad C1 og C2 deler, evaluerer de identiske uttrykk og produserer identiske resultater — og på fredag dør de ved nøyaktig samme sammenligning. Uansett hvilken framtid C2 har, har C1 den også. Å absorbere C2 inn i C1 kaster ingenting bort.

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

Mål med dette eksempeletVise hva som endrer seg når DEFINE refererer FIRST — absorpsjonsregelen holder ikke lenger, og planleggeren deaktiverer absorpsjon for mønsteret.

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

DagPrisC1 — start mandag
FIRST = $100
price < $100 + 10
C2 — start tirsdag
FIRST = $108
price < $108 + 10
Man$100$100 < $110 ✓—
Tir$108$108 < $110 ✓$108 < $118 ✓ (akkurat startet)
Ons$112$112 < $110 ✗ — finaliser man–tir$112 < $118 ✓
Tor$116—$116 < $118 ✓
Fre$110—$110 < $118 ✓ (løper fortsatt)
Forskjellige skjebner C1 dør på onsdag med en to-dagers serie (man–tir); C2 ville, på egen hånd, fortsette å løpe helt gjennom fredag. Samme priser, samme spørsmålsform — men forskjellige tak avledet fra deres egne treffstart. På nøyaktig samme dag nådde de to kontekstene motsatte konklusjoner.

Under absorpsjon ville C2 blitt slått sammen med C1 på tirsdag — den sammenslåtte konteksten beholder bare C1 sitt tak ($110), så C2 sitt distinkte syn (tak $118, en fire-dagers serie gjennom fredag) dekkes ikke av C1 sin framtid. Denne bestemte uka endres utdataen tilfeldigvis ikke: C1 registrerer man–tir, C2 startet inne i det treffet og forkastes av SKIP PAST LAST ROW, og neste forsøk starter på onsdag med sitt eget tak ($122) og treffer ons–fre. Generelt subsumerer imidlertid en tidligere konteksts DEFINE-resultat ikke lenger en senere konteksts, så tellingssammenligningen absorpsjon bygger på, er ugyldig. 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.)

Tabellen nedenfor utvider posterens nedre høyre panel ("② Navigation") med de sammensatte formene og oppsummerer hvilke navigasjonsformer som skaper treffstart-avhengighet:

NavigasjonTreffstart-avh.Absorberbar?
PREV, NEXTingenja
LAST (uten forskyvning)ingenja
LAST med forskyvninggrensekontrollnei
FIRST (alle)direktenei
Sammensatt (indre FIRST)direktenei
Sammensatt (indre LAST, uten forskyvning)ingenja
Sammensatt (indre LAST med forskyvning)grensekontrollnei

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 garantert dekker, så det kan ikke lenger vises at det er trygt å forkaste en av dem.

Planleggeren oppdager denne distinksjonen ved kompileringstid og slår absorpsjon på eller av for hele mønsteret; når den er av, betaler kjøretiden multikontekst-kostnaden. Posterens benchmark i panel ③ bruker ingen FIRST, så absorpsjon forblir på, og det er grunnen til at PostgreSQL holder seg lineær i både suksess- og feiltilfellene.

Benchmark-tallene på posteren er samme algoritme i skala. På suksessmønsteret (A+ B+ C+ D) skalerer både PostgreSQL og Trino omtrent O(n) når et treff er bekreftet, og PostgreSQL leder med omtrent 16× til 33× (Trino-tallene utelater allerede JVM-oppstart).

På feilmønsteret (A+ B+ C+ E) jakter Trino, som ser ut til å mangle absorpsjon, hver mulig treffstart og degraderes enda raskere enn O(n²) (omtrent 56× tiden for 5× radene); 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

Mål med dette eksempeletVise en andre måte absorpsjon kan feile: ikke fordi predikatet splittes, men fordi utdatasemantikken krever at hvert treff rapporteres separat.

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.

RadSKIP PAST LAST ROWSKIP TO NEXT ROW
0treff starter; rader 0–4 vil være det eneste treffettreff starter på rad 0
1(inne i treff 0)treff starter på rad 1 — må holdes aktivt
2(inne i treff 0)treff starter på rad 2 — må holdes aktivt
3(inne i treff 0)treff starter på rad 3 — må holdes aktivt
4treff 0 finaliseres (rader 0–4)fem treff finaliseres: 0–4, 1–4, 2–4, 3–4, 4–4
Forskjellig utdata, forskjellige skjebner Under AFTER MATCH SKIP TO NEXT ROW er hver senstartet kontekst sin egen utdatarad. To kontekster ved samme mønsterelement er ikke lenger overflødige — de er begge påkrevde utdata, og å forkaste en av dem ville stille fjerne et treff brukeren ba om.

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 de to måtene en spørrings semantikk utelukker absorpsjon på:

Datasiden · §2.6
Predikat evaluerer forskjellig per kontekst.
Utløst av FIRST eller forskjøvet LAST i DEFINE.
Utdatasiden · §2.7
Utdata krever hver treffstart som separat rad.
Utløst av AFTER MATCH SKIP TO NEXT ROW.

Begge betingelsene er nok til å deaktivere absorpsjon for hele mønsteret, og det samme er en ramme som ikke ender ved UNBOUNDED FOLLOWING. Når ingen av dem er aktiv — standard AFTER MATCH SKIP PAST LAST ROW, en ubegrenset rammeslutt og DEFINE-betingelser som bare bruker PREV, NEXT eller bart LAST — er absorpsjon aktivert, men bare for tilstander i mønsterets absorberbare region: en ledende grådig ubegrenset variabel som A+ eller A*, en gruppe med fast lengde og en ubegrenset grådig kvantifikator som (A B)+, en grådig gruppe hvis kropp starter med en av disse, som (A+ B)+ eller (A+ B){2}, eller alterneringsgrener bygget av disse; en motvillig gruppe diskvalifiserer hele sitt undertre. Der dette holder, som for A+ i §2.5, kollapser kjøretiden til én enkelt kontekst og holder seg lineær; START UP+ DOWN+ fra §2.3 får ingen absorberbar region i det hele tatt.

§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²) arbeid 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, sluttgrensen må være UNBOUNDED FOLLOWING eller en positiv forskyvning FOLLOWING (så en standardramme avvises også), og andre EXCLUDE-alternativer enn EXCLUDE NO OTHERS 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:

KildeTrekoding
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-predikat blir deretter typesjekket mot partisjonens kolonner og tvunget til et boolsk uttrykk. To praktiske ting følger. For det første legger parseanalysen ingenting til spørringens mål-liste for DEFINE; i stedet merker planleggeren hver kolonne et DEFINE-predikat refererer som nødvendig, slik den gjør for HAVING, og 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 ni omskrivingsregler i ett enkelt nedenfra-og-opp-pass (innenfor en sekvens kjører gruppesammenslåingen én gang til, siden tidligere sammenslåinger kan bringe to identiske grupper sammen):

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-sammenslåing
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
Normalisering av motvilje
A{2}? → A{2} (motvilje fjernes overalt der min = max)

Kvantifikatormultiplikasjon kollapser bare når de oppnåelige tellingene danner ett sammenhengende intervall og det foretrukne treffet ikke flytter seg: en eksakt ytre ((A{2,3}){5} → A{10,15}), et barn med min 0, eller barneintervaller som berører hverandre med en barne-min på høyst 1 eller en ubegrenset barne-max ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), der en ytre med min 0 også krever en barne-min på høyst 1 ((A{2,})* blir stående, siden A* ville akseptere én rad). Et gruppebarn hvis egen kvantifikator ikke er eksakt, må først ha en kropp med fast lengde, så ((A | B B){1,2}){2} forblir urørt selv under en eksakt ytre. 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 — eller flytte det foretrukne treffet ((A{2,3}){1,2} foretrekker tre rader der A{2,6} tar fire), så optimalisatoren lar dem være urørt. Det er ikke den eneste betingede omskrivingen: gruppesammenslåing og suffiks-sammenslåingen krever en kropp som konsumerer et fast antall rader, prefiks-sammenslåingen avslår en gruppe med min 0, en endelig max og nullbart innhold, motvillige noder verken slås sammen eller multipliseres ((A+?)+ blir stående), og en omskriving der den nye grensen ville flyte over, avslås.

Elementform

Hvert element i det flate arrayet representerer én enkelt posisjon i mønsteret. Det er seks 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; en grenseparator som avslutter hver gren; 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 altereringsmarkøren og grenseparatorene for å lenke grener, av gruppestart for å navngi sin egen gruppeslutt — en gruppe hvis kvantifikator tillater null, hoppes over gjennom den sluttens next — 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 → 3
    (åpner gruppen; jump navngir
     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 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 navngir BEGIN sin jump sin END ved idx 3, og hvis gruppen var valgfri, ville hoppet gå ut gjennom den END-ens next til idx 4 uten å ankomme END. 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 fem 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? B?)+, (A | B*)+; (A?)* multipliseres først til A* og etterlater ingen gruppeslutt). Forteller kjøretiden å legge til en fast-forward-utgang ved siden av den normale løkk-tilbake under min, slik at syklusvakten ikke dreper legitime treff i grupper som kan produsere tomme iterasjoner.
Tomt-foretrukket
Settes på gruppeslutt hvis kropp foretrekker det tomme treffet, som i (A?? B??){2}. Ordner fast-forward-utgangen foran løkk-tilbake under min, der gruppens egen grådighet ikke sier noe.
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 det flate arrayet fra
  element 0 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 gjennomgangen fire 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)+, (A+ B){2}
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å A får begge flaggene, den omsluttende BEGIN får i-region-flagget, og B og END får ingen.
Tilfelle 4 — Alternering
A+ | B+, A+ | C D
Hver gren, nådd gjennom separatorkjeden, vurderes for seg selv etter tilfellene ovenfor; altereringsmarkøren får i-region-flagget når en hvilken som helst gren kvalifiserer.

De strukturelle tilfellene som ikke dekkes av disse fire 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. 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
  hvis targetPos != currentPos:
      hent rad ved targetPos
        inn i nav_slot
      pek ytre slot på nav_slot
  result = eval_inner_expression()
  gjenopprett current_row_slot
  kopier by-ref-resultat ut av nav_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 og ingen slot per referanse; når målet er gjeldende rad, hoppes hentingen og byttet helt over. Hentingen kopierer målraden inn i navigasjonsloten (med mindre sloten allerede holder den), og gjenopprettingstrinnet kopierer et pass-by-reference-resultat inn i per-tuppel-minne, slik at neste henting ikke kan frigjøre det.

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 currentPos − 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 (currentPos − n) − m
  NEXT(LAST(n), m):
      return (currentPos − 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 kontekstabsorpsjon i det hele tatt er mulig (§2.5 vs §2.6): én enkelt treffstart-avhengig variabel deaktiverer den for hele mønsteret.

Delt evaluering · absorpsjonstrygg Hver kontekst ser samme Boolean ved hver rad — samme skjebne (§2.5).
  • Ingen navigasjon
  • Kun PREV / NEXT
  • LAST uten forskyvning
  • Sammensatt med indre LAST (uten forskyvning)
Per-kontekst-evaluering · absorpsjonsutrygg Kontekster med forskjellige treffstart regner ut forskjellige svar — forskjellige skjebner (§2.6).
  • LAST med forskyvning
  • FIRST (alle former)
  • Sammensatt med indre FIRST
  • Sammensatt med indre LAST (med forskyvning)

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. Eksekutoren regner det ut fra to komplementære forskyvninger, og løser hver forskyvning én gang per skanning (konstante også ved eksekutor-init, slik at ren EXPLAIN kan vise dem):

Tilbakeblikkbudsjett
Hvor langt bakover fra gjeldende rad et hvilket som helst DEFINE-kall kan strekke seg.
Bidragsytere: PREV, LAST (enhver forskyvning, inkludert standardverdien 0), PREV(LAST(...)), NEXT(LAST(...))
Framoverblikk-fra-start-budsjett
Minste framoverstrekk (bakover, når negativt) fra eldste aktive kontekst sin treffstart — den tidligste raden et hvilket som helst DEFINE-kall kan trenge.
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. Nav Mark-linjene EXPLAIN rapporterer (§3.7) — Lookback og Lookahead — er disse to budsjettene, ikke målte topper. Hver skrives bare ut når en navigasjon mater den, og vises selv uten ANALYZE; en forskyvning hvis verdi bare er kjent ved kjøretid (for eksempel en generisk-plan-parameter) skriver ut runtime under ren EXPLAIN og sin løste verdi under EXPLAIN ANALYZE, og retain all (Lookback) eller infinite (Lookahead) markerer en forskyvning som flyter over.

3.4 Treffgrenser — SKIP, INITIAL og bundet ramme

Et treffresultat registreres som to verdier: raden treffet starter på, og lengden. En negativ start betyr at posisjonen ikke er evaluert ennå; når starten er satt, kan etterfølgende spørringer mot eksekutoren — "er denne raden inne i et treff?" — svare i O(1) ved å inspisere paret. Lengden koder utfallet: -1 for en rad uten treff, 0 for et tomt treff, og radantallet for et reelt treff. 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 både fra en rad uten treff og 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 det vinduets mønster 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, og driver deretter NFA-en framover rad for rad — og nullstiller et per-variabel treffarray til "uevaluert" for hver rad — til den konteksten ikke har flere aktive tilstander eller partisjonen ender. DEFINE-predikater evalueres lat: en variabel evalueres første gang en tilstand konsumerer den, så en variabel ingen aktiv tilstand tester på denne raden, evalueres aldri. 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 nådde sin frame-slutt:
          tving mismatch (avslutt tidlig)
          continue
      hvis matchStartRow avviker fra
         delt evalueringsposisjon:
          nullstill match-start-avhengige
          DEFINE-vars til uevaluert (§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)
      hvis den registrerte et match og
         SKIP PAST LAST ROW:
          beskjær senere kontekster som
          starter inne i matchen

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

      hvis varMatched[elem.varId] er
         uevaluert:
          evaluer dens DEFINE nå
      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
         eller holder et registrert match:
          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) inntil konteksten registrerer et treff, som låser det til usann — absorpsjon ville frigjøre et treff ingen absorberende kontekst kan reprodusere. 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 besøkt-bitmap-en
      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, stopper
                så snart FIN er registrert),
    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 flagg
         konteksten så senere kontekster
         innenfor denne kandidatens område
         beskjæres — 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å når Advance er ferdig med konteksten som registrerte en kandidat, beskjæres hver etterfølgende kontekst hvis startrad faller innenfor kandidatens område, på samme rad, 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 FIN-tidsbeskjæringstrinnet på tvers av kontekster. Inne i konteksten kutter FIN også leksikalsk underordnet arbeid: Advance forkaster de gjenværende tilstandene i køen (beskrevet tidligere i denne seksjonen), og innenfor én DFS stopper hver mindre foretrukket sti — senere ALT-grener, den andre av BEGINs hopp- og inngangssti, en motvillig variabels inngangssti, den andre av ENDs løkke- og utgangssti — så snart et treff er registrert, så én advance registrerer høyst ett treff.

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
          (fast-forward først hvis
           kroppen foretrekker tomt; den
           andre stien slippes hvis
           den første nådde FIN)

  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
          hvis loop nådde FIN:
              slipp exit
              # foretrekk lengre
          ellers exit som nummer to
      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? B?)+ og (A | B*)+ har denne egenskapen: avhengig av dataene kan kroppen fullføre en iterasjon uten å konsumere noen rad i det hele tatt. (Et enkelt valgfritt barn som (A?)* omskrives til A* ved kompileringstid og etterlater ingen gruppe.) 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 inn i kroppen (dens jump er gruppens første barn), kroppen produserer igjen et tomt treff, når END igjen, og så videre. Uten noe som stopper det, ville Advance sin DFS aldri terminert.

Vakten 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. Kjøretiden holder et besøkt-bitkart, nullstilt før hver tilstands DFS-utvidelse, der bare de merkede END-ene markeres — ingenting annet kan gå i sykel, fordi enhver annen løkk-tilbake har konsumert en rad. Å nå en markert END betyr at kroppen nettopp avledet en tom iterasjon, og tilstanden forkastes ikke: på eller over nedre grense forlater den gruppen der (en tom iterasjon stopper kvantifikatoren), og under den faller tilstanden gjennom til den normale løkk-tilbake, så hver tom ankomst likevel øker tellingen til den når min. Ta (A? B?){2,3} uten at noen av variablene treffer noe sted i radstrømmen:

iter 1: A? B? treffer null rader
        → END, count = 1 (under min)
        END allerede markert (ved
        gruppeinngang), men under min:
        → løkk tilbake inn i A?
iter 2: A? B? treffer null rader
        → END, count = 2 (oppfyller min)
        END allerede markert, ved min:
        → forlat gruppen
avslutt med et nulllengdetreff

Under nedre grense forteller tomgangsløkk-merket også END-håndtereren å klone en ekstra fast-forward-tilstand ved siden av den normale løkk-tilbake-stien:

advance_end (count under min):

  løkk-tilbake-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. Løkk-tilbake fanger tilfellet der kroppen fortsatt har reelle treff å produsere senere — for eksempel i (A? B?){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 forlater gruppen med en gang, erklærer "resten av de påkrevde iterasjonene er tomme" og lar treffet lykkes med en nulllengdekropp. Kroppen, ikke gruppens egen grådighet, avgjør rekkefølgen: fast-forward går først nøyaktig når kroppen foretrekker det tomme treffet (en motvillig kropp som (A?? B??)), og hvis den første stien når FIN, slippes den andre, så en mindre foretrukket sti ikke kan erstatte det foretrukne treffet. 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

At kjøretiden holdes begrenset, 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 sitter på et sammenligningspunkt og er dekket av en eldre konteksts absorberbare tilstand ved samme element med større eller lik 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) Advance
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 så snart Advance er ferdig med konteksten som registrerte kandidaten.
Syklusvakt Advance
Epsilon-utvidelser som når END-en til en nullbar gruppe som allerede er markert innenfor samme DFS (markert ved inngang gjennom BEGIN, eller ved en tidligere ankomst) — ville ellers løkke for alltid; tilstanden forlater gruppen der på eller over nedre grense, og fortsetter å løkke under den.
Tomgangsløkk fast-forward Advance
Under nedre grense for en nullbar gruppe, en ekstra sti som forlater gruppen med gjenværende påkrevde iterasjoner erklært tomme, ordnet mot løkk-tilbake etter kroppens preferanse.
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). Å 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. 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å. Kildekoden dokumenterer tilfeller lagene ikke fanger: dedup holder tilstander som bare skiller seg i tellinger over min fra hverandre, så (A{2,} B)+ C der C aldri er sann, holder Θ(n²) tilstander på topp og oppretter Θ(n³) av dem (37 s over 320 rader), og en rekke helt nullbare alterneringer enumereres sti for sti, så (A?|B?){30} tar over en halvtime.

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. I tekstformat emitteres de ved siden av vindusoperatoren, etter Pattern:-linjen, eventuelle Nav Mark-linjer (som ren EXPLAIN også viser) og Storage:-linjen:

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (hver bare når DEFINE bruker navigasjon
   som mater 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)
  (andre NFA-linje bare når en av
   tellingene er ikke-null; en null-telling
   skrives ut uten sin (len ...))

Ikke-tekstformater emitterer hver telling som sin egen egenskap. 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; pruned teller kontekster som feilet etter én enkelt rad. Trefflengdehistogrammene skiller fire utfall — vellykkede treff, treffforsøk som feilet etter mer enn én rad (mismatched), absorberte kontekster og kontekster frigjort av AFTER MATCH SKIP PAST LAST ROW fordi de startet inne i et registrert treff (skipped) — 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 fra DEFINE. Lookback er det dypeste bakoverstrekket fra gjeldende rad på tvers av PREV, LAST med enhver forskyvning (inkludert standardverdien 0) og de sammensatte formene med indre LAST; Lookahead er det minste framoverstrekket (negativt når det ser før treffstarten) 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 bare er kjent per skanning, og — kun for Lookback — "retain all" når forskyvningen flyter over; en Lookahead som flyter over, skrives ut som "infinite". Hver linje emitteres bare når en navigasjon i DEFINE mater den, og begge vises også under ren EXPLAIN: konstante forskyvninger fastsettes ved eksekutor-init, mens en forskyvning som bare er kjent ved kjøretid (for eksempel en generisk-plan-parameter) skriver ut "runtime" der og sitt løste heltall under EXPLAIN ANALYZE.

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

Utover tellerne skriver EXPLAIN ut en Pattern:-linje bygget fra det kompilerte element-arrayet, så den viser mønsteret etter kompileringstidsomskrivingene (PATTERN (A A) forklares som a{2}) og bærer absorpsjonsmarkørene # (sammenligningspunkt) og ~ (absorberbar region); DEFINE og AFTER MATCH SKIP-alternativet vises ikke. Å gjengi klausulene slik de er skrevet, inkludert motvillige kvantifikatorer, grupperepetisjon og skip-alternativet, er jobben til pg_get_viewdef(), som 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 22 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
WINDOW-klausulintegrasjon — realistiske vindusscenarioer på syntetiske aksjedata (V-form, W-form, sammenhengende stigninger, reverseringer), pluss navigasjonssemantikk og DEFINE-restriksjonsfeil.
rpr_base
Parser-laget — nøkkelordaksept, syntaksformer, kvantifikatorer, navigasjonsparsing, feilmeldinger og pg_dump/pg_upgrade-rundturstabilitet; pluss et planleggerlag — mønsteroptimalisering, absorpsjonsflagg, optimaliserings-fallback, planleggerintegrasjon.
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. Disse scenarioene er de eneste testene der inn- og utdata leses som spørringer en bruker faktisk kunne skrive; resten av filen er, som de andre suitene, reduktiv — PREV/NEXT-nesting og feil for ikke-konstante forskyvninger, DEFINE-referanseregler og semantikk for navigasjonsforskyvninger.

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. En andre del, planleggerlaget, dekker mønsteroptimalisering, visning og analyse av absorpsjonsflagg, optimaliserings-fallback og planleggerintegrasjon (underspørringer, joins, settoperasjoner, sortering og gruppering).

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. Defekter som et motvillig-flagg som 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: inline VALUES-rader som bærer et array av variabelnavn som erklærer hvilke DEFINE-variabler som treffer på hver rad, paret med et mønster som sonderer en spesifikk kjøretidsoppførsel. 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:

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 (overvåkingsdashbord, loggskrapere) parser den, og endringer som ser kosmetiske ut, kan ødelegge dem. rpr_explain-suiten verifiserer tre ting:

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 hvordan hver av disse optimaliseringene behandler RPR-vinduer — de fleste må deaktiveres eller forbigås:

Rammekanonisering
Planleggeren omskriver normalt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING til ROWS UNBOUNDED PRECEDING for rammeuavhengige vindusfunksjoner som row_number, rank og ntile. 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 eller SKIP)
To RPR-vinduer med samme PATTERN, men forskjellige DEFINE-klausuler eller en annen AFTER MATCH SKIP produserer forskjellige treff og må forbli distinkte, selv om deres strukturelle form er identisk.
Ubrukt-utdata-projeksjon
Denne får lov til å anvendes: når den omsluttende spørringen aldri leser vinduets utdata, blir vindusfunksjonen NULL og dens WindowAgg droppes, mens radantallet forblir uendret. Testene sjekker at kolonnene DEFINE leser, fortsatt når WindowAgg når den blir stående, og at vinduet beholdes når verdien leses.
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.

Ytterligere tilfeller sjekker at kostnadsestimering tar hensyn til DEFINE, at en underspørring som holder et RPR-vindu ikke flates ut, at DEFINE-uttrykk ikke lekker inn i en øvre WindowAgg, og at LIMIT forblir over WindowAgg; en andre gruppe kjører RPR sammen med CTE-er, joins, settoperasjoner, preparerte setninger, partisjonerte tabeller og lignende konstruksjoner. De fleste vaktede tilfellene følger samme form: en baseline som utløser optimaliseringen (vanligvis en ikke-RPR-spørring, sjekket i EXPLAIN), deretter en RPR-spørring av strukturelt lignende form der optimaliseringen ikke anvendes — for DEFINE/SKIP-dedup-tilfellet er baselinen to identiske RPR-vinduer, og invers-overgang-tilfellet sjekker forbigåelsen med et loggende aggregat i stedet for EXPLAIN. 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.