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.
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.
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 FOLLOWINGellerROWS BETWEEN CURRENT ROW ANDnFOLLOWINGmed n ≥ 1 (19075-5 §6.10.2); enhver annen ramme avvises, ogEXCLUDE NO OTHERSer 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. barePrice) 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,FIRSTogLASTskrevet som ukvalifiserte kall inne iDEFINEbetyr alltid navigasjon; en brukerfunksjon med samme navn må der være skjemakvalifisert.- Navigasjonsargumenter
- For
PREV,NEXT,FIRSTogLASTmå 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 viaOVERsom 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 iDEFINE,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.priceiDEFINEellerMEASURES— 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");
permutekan fortsatt brukes som navn på en mønstervariabel. - Aggregatfunksjoner i DEFINE
- Aggregater som
SUM,AVG,COUNTer ikke tillatt iDEFINE-predikater. Standarden tillater dem som løpende aggregater over delvis treff; et variabelkvalifisert aggregat somAVG(B.Price)avhenger av samme per-treff-historikk somMEASURES/CLASSIFIER()krever, mens et ukvalifisert aggregat spenner over alle radene i treffet så langt. - Underspørringer i DEFINE
- Enhver underspørring i
DEFINEavvises. 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.
§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.
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
DEFINEer 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
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:
| Rad | Pris | Sanne variabler | Handling |
|---|---|---|---|
| 0 | 100 | START | Ny kontekst. START treffer og forlater umiddelbart (max=1); tilstanden går videre til UP+. |
| 1 | 110 | START, UP | UP treffer. Framrykningen forgrener seg: én tilstand løkker ved UP, en annen går ut til DOWN+. |
| 2 | 120 | START, UP | UP treffer i den løkkende tilstanden og forgrener på nytt. DOWN-tilstanden fra rad 1 dør (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP 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. |
| 4 | 108 | START, DOWN | DOWN treffer i den løkkende tilstanden og forgrener på nytt; den nye FIN-kandidaten over rader 0–4 erstatter den kortere. |
| 5 | 130 | START, UP | Den 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:
| Rad | Pris | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
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 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.
| Rad | Sanne variabler | Aktive tilstander |
|---|---|---|
| R | UP, HIGH | Tilstand 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+1 | DONE | Tilstand 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)
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):
| Rad | Naive kontekster | Med absorpsjon |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 absorbert |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | fem kontekster | C1[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:
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:
| Dag | Pris | C1 — 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 |
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
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+).
| Dag | Pris | C1 — 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) |
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:
| Navigasjon | Treffstart-avh. | Absorberbar? |
|---|---|---|
| PREV, NEXT | ingen | ja |
| LAST (uten forskyvning) | ingen | ja |
| LAST med forskyvning | grensekontroll | nei |
| FIRST (alle) | direkte | nei |
| Sammensatt (indre FIRST) | direkte | nei |
| Sammensatt (indre LAST, uten forskyvning) | ingen | ja |
| Sammensatt (indre LAST med forskyvning) | grensekontroll | nei |
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
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.
| Rad | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | treff starter; rader 0–4 vil være det eneste treffet | treff 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 |
| 4 | treff 0 finaliseres (rader 0–4) | fem treff finaliseres: 0–4, 1–4, 2–4, 3–4, 4–4 |
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å:
FIRST eller forskjøvet LAST i DEFINE.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:
| Kilde | Trekoding |
|---|---|
| A | VAR(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 tilA*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
-
Hver iterasjon er nøyaktig én rad. En tidligere kontekst sin telling er alltid ≥ en senere sin ved hver delt posisjon.
A+,A*,A{2,∞} - Tilfelle 2 — Fastlengdegruppe, ubegrenset ytre
-
Hvert barn har
(A B)+,(A B{2})+,((A (B C){2}){2})+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
-
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.
(A+ B)+,(A+ B){2} - Tilfelle 4 — Alternering
-
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.
A+ | B+,A+ | C D
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.
- Ingen navigasjon
- Kun
PREV/NEXT LASTuten forskyvning- Sammensatt med indre
LAST(uten forskyvning)
LASTmed forskyvningFIRST(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.
- 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.
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 ROWkan 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:
- 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 ledendeA+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 (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) dukker opp under
EXPLAIN ANALYZEi tekst, JSON og XML med de dokumenterte etikettene, og Nav Mark Lookback og Lookahead vises nøyaktig når navigasjon i DEFINE mater dem. - 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 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 FOLLOWINGtilROWS UNBOUNDED PRECEDINGfor rammeuavhengige vindusfunksjoner somrow_number,rankogntile. 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 BYog 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 forskjelligeDEFINE-klausuler eller en annenAFTER MATCH SKIPproduserer 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.