2026 · Vancouver
Simon Fraser University — Vancouver-campus

Row Pattern Recognition Fördjupning

En guidad rundtur genom ISO/IEC 19075-5 · SQL R020 i PostgreSQL — vad som har byggts, vad som ännu återstår och hur det faktiskt körs.

Komplement till affischen som visas på PGConf.dev 2026.
Skumma standarden, gå igenom genomarbetade exempel, bläddra i designen och kör sedan en interaktiv NFA-simulator med egna mönster.
Diskussion: pgsql-hackers-tråd · senaste patchen (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

AI-föröversatt — fel möjliga.

§1. Standarden, delmängden och de öppna frågorna

1.1 Standardens omfattning

Row Pattern Recognition introducerades i SQL genom ISO/IEC 9075-2:2016 och beskrivs i kompletterande dokument ISO/IEC 19075-5:2021 (del 5, "Row Pattern Recognition").

Standarden definierar två ytor för samma underliggande maskineri. Funktion R010 placerar en MATCH_RECOGNIZE-sats i FROM-listan för att producera en härledd tabell; funktion R020 integrerar samma mönsterlogik i en WINDOW-specifikation för att producera utdata från fönsterfunktioner. De två ytorna har betydande delar av syntax och semantik gemensamt (19075-5 noterar några R020-specifika skillnader i §6.3.3), men är funktionellt distinkta ingångar — en databas kan implementera den ena, den andra eller båda.

Den patch-serie som diskuteras här implementerar en delmängd av endast R020; tabellsats-formen är medvetet utanför omfattningen.

R020-ytan är liten men uttrycksfull. En fråga kopplar ett mönster till ett fönster genom att lägga till satser inuti en fönsterspecifikation vars ram är ROWS BETWEEN CURRENT ROW AND …: PATTERN beskriver ett reguljärt uttryck över namngivna mönstervariabler, DEFINE tillhandahåller det booleska predikat som identifierar varje variabel och den valfria AFTER MATCH SKIP (standard PAST LAST ROW) styr hur efterföljande matchningar placeras inom partitionen.

Valfria MEASURES, SUBSET, INITIAL/SEEK och hjälpfunktionen CLASSIFIER() kompletterar funktionen. (Standardens MATCH_NUMBER()-funktion tillhör endast R010-ytan — 19075-5 §6.3.3 (6) utesluter den uttryckligen från R020.)

Patchen täcker tillräckligt av detta ordförråd för att icke-triviala frågor ska fungera, men stannar före flera konstruktioner vars implementation beror på infrastruktur som ännu inte har byggts.

Resten av detta avsnitt delar upp standardens ordförråd i det som patchen redan stöder och det som den medvetet lämnar till senare. Listorna nedan återspeglar patch-seriens aktuella tillstånd.

1.2 Implementerade funktioner

Det implementerade ordförrådet räcker för att uttrycka de kanoniska V-form-, W-form- och vändmönster som från början motiverar row pattern recognition. Det täcker även varje standardkvantifierare — inklusive alla sju motvilliga varianter *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — samt de fyra navigationsprimitiv som DEFINE-villkor behöver för att jämföra angränsande rader.

PATTERN-sats
Definierar radmönstret inuti en fönsterspecifikation; upp till 240 distinkta mönstervariabler.
Fönsterram
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING eller ROWS BETWEEN CURRENT ROW AND n FOLLOWING med n ≥ 1 (19075-5 §6.10.2); varje annan ram avvisas, och EXCLUDE NO OTHERS är den enda exklusion som accepteras.
Regex: + * ? |
Standardkvantifierare och alternation.
Regex: ( ) gruppering
Delmönster inom parentes.
Regex: {n} {n,} {,m} {n,m}
Begränsade upprepningsantal.
Motvilliga *? +? ?? {n}? {n,}? {,m}? {n,m}?
Alla sju motvilliga (icke-giriga) varianter som standarden definierar (uteslutna från absorptionsoptimering).
DEFINE-sats
Booleska villkor som identifierar varje mönstervariabel.
Universell radmönstervariabel
Okvalificerade kolumnreferenser i DEFINE (t.ex. bara Price) löses till den aktuella raden, enligt 19075-5 §4.10/§4.16.
PREV, NEXT (med offset)
Når n rader före/efter den aktuella raden (standard 1); det inre argumentet utvärderas vid den navigerade raden.
FIRST, LAST (med offset)
Når en matchningsrelativ rad; FIRST(expr, n) riktar sig mot raden n efter matchningens start, LAST(expr, n) raden n före den senaste matchningsraden.
Sammansatt navigation (fyra former)
Yttre PREV/NEXT-steg lagrat ovanpå en inre FIRST/LAST: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — både det inre och yttre steget accepterar var sin offset.
Navigationsnamn
PREV, NEXT, FIRST och LAST skrivna som okvalificerade anrop inuti DEFINE betyder alltid navigation; en användarfunktion med samma namn måste schemakvalificeras där.
Navigationsargument
För PREV, NEXT, FIRST och LAST måste det inre argumentet innehålla minst en kolumnreferens och offset måste vara en körtidskonstant.
INITIAL
Mönstermatchningar måste börja vid den aktuella raden (standard).
AFTER MATCH SKIP PAST LAST ROW
Standardläge för hopp; berättigar till kontextabsorption.
AFTER MATCH SKIP TO NEXT ROW
Tillåter överlappande matchningar; inaktiverar absorption.

1.3 Ej implementerat

De funktioner som förblir oimplementerade faller in i tre löst sammanhållna grupper. Den första — och i särklass största — är familjen av konstruktioner centrerade kring MEASURES: själva MEASURES-satsen, SUBSET, CLASSIFIER(), mönsterkvalificerade kolumnreferenser såsom B.price och mönsterkvalificerad navigation såsom LAST(B.price) eller PREV(B.price).

Dessa är inte oberoende luckor utan snarare olika vyer av en enda saknad pusselbit: executor måste behålla en per-matchningshistorik — en post, för varje rad i matchningen, över vilken mönstervariabel den mappades till — och ingen av dessa konstruktioner har någon meningsfull definition utan den. CLASSIFIER() läser ut variabelnamnet från den posten; B.price läser pris-kolumnen för de rader vars post säger B; LAST(B.price) går igenom samma raduppsättning och plockar den sista; SUBSET U = (A, B) definierar en virtuell variabel som aggregerar över båda hinkarna; och MEASURES utvärderar uttryck som AVG(U.Price) med exakt den aggregeringen.

Den nuvarande executorn utvärderar DEFINE-predikat rad för rad men registrerar inte de resulterande variabeltilldelningarna någonstans — det finns inget att fråga efter senare. Att bygga historikinfrastrukturen är därför en förutsättning för hela gruppen; de enskilda funktionerna faller ut som små projektioner när posterna väl existerar.

Den andra gruppen rör alternativa hoppmål: AFTER MATCH SKIP TO FIRST var och AFTER MATCH SKIP TO [LAST] var (bart SKIP TO var betyder SKIP TO LAST var). Dessa beror också på matchningshistorik, eftersom executorn måste kunna peka på den rad som mappats till en given variabel inuti den senaste matchningen.

De återstående punkterna är en heterogen svans: nyckelordet SEEK (alternativet till INITIAL), det tomma mönstret (), exklusionsformen {- … -}, den ordningsokänsliga PERMUTE-operatorn samt aggregatfunktioner och underfrågor i DEFINE, som båda för närvarande avvisas (ett variabelkvalificerat aggregat skulle också behöva matchningshistoriken).

MEASURES
Namngivna per-matchningsutdataruttryck, t.ex. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; i R020 exponerade via OVER som en fönsterfunktion. Accepterar nyckelorden FINAL / RUNNING (19075-5 §5.4), vilka i R020 kollapsar till samma värde eftersom mått alltid utvärderas på matchningens sista rad (19075-5 §6.9 (3)).
SUBSET
Namngivna unioner av mönstervariabler, t.ex. SUBSET U = (A, B, C). Användbara överallt där en mönstervariabel kan refereras — MEASURES, mönsterkvalificerade referenser i DEFINE, CLASSIFIER(U) — vilka alla behöver matchningshistorik.
CLASSIFIER()
Returnerar vilken mönstervariabel en given rad matchades som. Definierad för både DEFINE och MEASURES (19075-5 §5.9); svaret vid varje rad är variabelnamnet som registrerats i matchningshistoriken för den raden.
Mönsterkvalificerad kolumnreferens
Bart B.price i DEFINE eller MEASURES — värdet från kolumnen för den rad som mappats som den namngivna variabeln.
Mönsterkvalificerad navigation
Begränsa navigation till rader som matchats som en namngiven variabel, t.ex. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).
SEEK
Matchning får börja vid vilken rad som helst från den aktuella raden till slutet av den fullständiga fönsterramen (jämfört med INITIAL).
AFTER MATCH SKIP TO FIRST var
Hoppa till den första raden som matchats som den namngivna variabeln.
AFTER MATCH SKIP TO [LAST] var
Hoppa till den sista raden som matchats som den namngivna variabeln.
Regex: {- -}
Exklusion — tar bort matchade rader från ALL ROWS PER MATCH-utdata. Det alternativet gäller inte för fönster (19075-5 §6.3.3 (4)), så i ett fönster är syntaxen tillåten (§6.13) men har inga utdata att verka på.
Regex: ()
Tomt mönster — matchar den tomma sekvensen.
PERMUTE(...)
Ordningsokänslig matchning över listade variabler. Nyckelordet känns igen och avvisas ("PERMUTE is not supported"); permute förblir användbart som namn på en mönstervariabel.
Aggregatfunktioner i DEFINE
Aggregat såsom SUM, AVG, COUNT tillåts inte i DEFINE-predikat. Standarden tillåter dem som löpande aggregat över den partiella matchningen; ett variabelkvalificerat aggregat såsom AVG(B.Price) beror på samma per-matchningshistorik som MEASURES/CLASSIFIER() kräver, medan ett okvalificerat sträcker sig över alla rader i matchningen hittills.
Underfrågor i DEFINE
Varje underfråga i DEFINE avvisas. Standarden tillåter en som inte utför någon row pattern recognition och inte refererar någon mönstervariabel; patchen överavvisar tills vidare.

Fyra ytterligare punkter är värda att nämna här, eftersom de lätt kan misstas för utelämnanden.

Den första är att mönsterankarna ^ och $ inte tillåts med RPR i WINDOW-satsen enligt själva standarden (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; med den underliggande definitionen i 19075-5 §4.14.1); deras frånvaro är överensstämmelse, inte en lucka.

Den andra är att MATCH_NUMBER() likaledes utesluts från R020 av standarden (19075-5 §6.3.3 (6) och 19075-5 §6.9 (1)) — den är endast del av R010-ytan, och dess frånvaro här är åter igen överensstämmelse snarare än en saknad funktion.

Den tredje är en uppsättning strukturella förbud som standarden ålägger R020 (19075-5 §6.17): row pattern recognition kan inte nästlas inom en annan row pattern recognition; MEASURES och DEFINE får inte innehålla yttre referenser; underfrågor inuti MEASURES eller DEFINE får inte referera till mönstervariabler (patchen går längre och avvisar alla underfrågor i DEFINE, som listats ovan); och RPR får inte användas inuti en rekursiv fråga. Patchen upprätthåller regeln om yttre referenser ("cannot use outer query column in DEFINE clause") och rekursionsregeln, den senare för varje element i en WITH RECURSIVE-sats. Den avvisar också volatila funktioner och helradsreferenser i DEFINE.

Den fjärde är att själva MATCH_RECOGNIZE — funktion R010, tabellsats-ytan för samma maskineri — är utanför omfattningen för denna patch. Huruvida PostgreSQL så småningom lägger till R010 är en fråga för en framtida serie, inte ett mått på denna.

Härkomst. Listorna över implementerade och ej implementerade i detta avsnitt återspeglar patch-seriens aktuella tillstånd — specifikt v55 (2026-11-17).

§2. Exempel — hur det faktiskt körs

Exemplen i detta avsnitt byggs upp stegvis. Vi börjar med det begreppsmässiga skälet till att radmönstermatchning verkligen skiljer sig från strängmönstermatchning, introducerar sedan de fyra navigationsfunktioner som gör DEFINE-villkor intressanta och går slutligen igenom fem genomarbetade exempel: en enstaka matchning (NFA-rörelse), alternation, kontextabsorption i det enkla fallet samt två fall där absorption är inaktiverad.

Den interna mekanism som gör navigation billig — 1-slots-tupelbytet — hör till executors design och behandlas i nästa avsnitt, inte här.

2.1 Varför radmönster skiljer sig från textmönster

Ett reguljärt textuttryck matchar en ström av tecken, och vid varje position finns exakt en symbol att betrakta. Körtidsfrågan — "är den aktuella symbolen lika med 'A'?" — har ett enda ja/nej-svar. Backtrackande automater utnyttjar detta: högst en gren överlever per tecken, och kostnaden för tvetydighet betalas genom att läsa om indata.

Ett radmönster är annorlunda på ett grundläggande sätt. En rad är inte en enskild symbol; den är en tupel av kolumner som utvärderas mot en uppsättning booleska predikat, DEFINE-villkoren. Två predikat kan vara sanna vid samma rad samtidigt, och inget i standarden säger att de måste vara ömsesidigt uteslutande. Betrakta:

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

En rad med price = 150, volume = 2000 uppfyller både A och B men inte C. Mönstermatcharen kan inte kollapsa detta till ett enda tillstånd — två mönstervariabler är aktiva, och varje mönsterelement som namnger någon av dem kan avancera. NFA:n måste därför bära flera samtidiga tillstånd per partitionsrad, inte ett.

Text regex vs row pattern: a single state advances per symbol, while multiple DEFINE predicates can match a row in parallel. TEXT REGEX single state advances through symbols A B C one symbol per position · one transition ROW PATTERN one row, multiple predicates evaluated row price = 150 · volume = 2000 A ✓ price > 100 B ✓ volume > 1000 C ✗ price > 200 two predicates true · two states stay alive
Text-regex kollapsar till ett tillstånd per symbol; en rad kan uppfylla flera DEFINE-predikat samtidigt, så flera tillstånd hålls vid liv parallellt.

Denna enda observation styr resten av arkitekturen. Exekveringstillståndet är en lista av kontexter, varje kontext är en lista av tillstånd, och vid varje rad frågar körtiden varje tillstånd: "givet de variabler som är sanna här, vart kan jag gå?" De grenar som uppstår är skälet till att körtiden behöver flera lager av beskärning — tillståndsdeduplicering inom en kontext, absorption mellan kontexter och de övriga regler som beskrivs i §3.6 — utan vilka antalet aktiva tillstånd och kontexter växer med partitionen och mönstermatchningen blir superlinjär.

2.2 Navigationsfunktioner

DEFINE-villkor som endast refererar den aktuella raden är begränsade; nästan varje intressant mönster behöver jämföra den aktuella raden med sina grannar eller med de rader som redan accepterats tidigare i matchningen. Standarden tillhandahåller fyra navigationsfunktioner för detta, och patchen implementerar alla.

PREV(expr [, n])
Raden n rader före den aktuella raden (standard n = 1). Används för jämförelser av typen "i dag jämfört med i går".
NEXT(expr [, n])
Raden n rader efter den aktuella raden (standard n = 1). Framåtblickande; ovanlig i fönsterform eftersom fönstret är monotont.
FIRST(expr [, n])
Raden n rader efter den första raden i den aktuella matchningen (standard n = 0, själva den första raden). "Jämför med raden som startade denna matchning."
LAST(expr [, n])
Raden n rader före den senast matchade raden (standard n = 0). Inuti DEFINE är den senast matchade raden den aktuella raden, så LAST(price) läser den aktuella raden.

De fyra primitiven sammansätts: PREV och NEXT kan omsluta ett FIRST- eller LAST-anrop, vilket ger fyra sammansatta former vars semantik är "gå till en matchningsrelativ rad och stega sedan ett fast avstånd bort från den". Det är detta som låter ett DEFINE-uttryck läsa till exempel raden omedelbart före matchningens start.

PREV(FIRST(expr [, n]) [, m])
Stega m rader bakåt från den rad som FIRST(expr, n) läser (standard n = 0, m = 1). "Vilket var värdet just innan denna matchning började?"
NEXT(FIRST(expr [, n]) [, m])
Stega m rader framåt från den rad som FIRST(expr, n) läser. Når längre in i matchningen utan att vara beroende av den aktuella raden.
PREV(LAST(expr [, n]) [, m])
Stega m rader bakåt från den rad som LAST(expr, n) läser. "Jämför med en rad strax före den senast matchade raden."
NEXT(LAST(expr [, n]) [, m])
Stega m rader framåt från den rad som LAST(expr, n) läser.

Två praktiska poänger är värda att lyfta här. För det första kan navigation sammansättas: PREV(FIRST(price)) läser raden omedelbart före matchningens start, och patchen stöder detta. För det andra har navigation konsekvenser för executors optimeringar. Enkla PREV och NEXT är relativa den aktuella raden och är alltid säkra; FIRST och offset-varianter av LAST, ensamma eller inuti ett sammansatt PREV/NEXT, är relativa matchningsgränserna, vilket interagerar med kontextabsorption: planeraren inaktiverar då absorption för hela mönstret. Mekanismen bakom denna interaktion är ämnet för §2.6.

2.3 Genomgånget exempel 1 — NFA-rörelse

Målet med detta exempelVisa NFA:ns rad-för-rad-tillståndsutveckling på ett enkelt, icke-absorberande mönster. Spårningen följer kontexten som startade vid rad 0; kontexterna som startade vid raderna 1–4 löper parallellt med den och kastas av SKIP PAST LAST ROW när dess matchning har registrerats.
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önstret plattas ut till fyra element:

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

För prisserien 100, 110, 120, 115, 108, 130:

RadPrisSanna variablerÅtgärd
0100STARTNy kontext. START matchar och avslutas omedelbart (max=1); tillståndet avancerar till UP+.
1110START, UPUP matchar. Avanceringen grenar sig: ett tillstånd loopar vid UP, ett annat avslutas till DOWN+.
2120START, UPUP matchar i det loopande tillståndet och grenar sig igen. DOWN-tillståndet från rad 1 dör (120 ≮ 110).
3115START, DOWNUP misslyckas i det loopande tillståndet och dör. DOWN-tillståndet från rad 2 matchar. Avanceringen grenar sig: loop vid DOWN och avslut till #FIN — en matchningskandidat över raderna 0–3 registreras.
4108START, DOWNDOWN matchar i det loopande tillståndet och grenar sig igen; den nya FIN-kandidaten över raderna 0–4 ersätter den kortare.
5130START, UPDet loopande DOWN-tillståndet misslyckas (130 ≮ 108). Utan något aktivt tillstånd kvar i denna kontext färdigställs den registrerade kandidaten (raderna 0–4) som matchningen. Nästa försök startar vid rad 5; START matchar, men partitionen tar slut före någon UP.

Den centrala poängen: vid rad 3 uppfyller raden både START (alltid sant) och DOWN, men START har betydelse endast för en kontext som startar vid rad 3; i denna kontext dör det loopande UP-tillståndet och endast tillståndet som väntar vid DOWN+ avancerar. Multitillståndsnaturen från §2.1 syns som förgrening vid varje UP-matchning (tillståndet kan stanna vid UP+ eller avancera mot DOWN+). Girig preferens är "loopa igen före utgång", så med tillräckligt mycket data skulle de loopande grenarna förlänga matchningen ytterligare; här dör den loopande DOWN vid rad 5 (130 ≮ 108), och den sista FIN-kandidaten (raderna 0–4) — producerad när DOWN avslutades vid rad 4, och som ersatte kandidaten från rad 3 — färdigställs som matchningen.

Frågans resultat följer direkt av denna spårning. Under RPR-semantik utvärderas fönsterfunktionerna first_value(price) och last_value(price) endast vid raden som startade matchningen — varje annan rad i matchningen producerar NULL för dessa fönsterfunktioner, eftersom dess reducerade ram är tom. Utdata för våra data ser därför ut som tabellen affischen visar i sin övre högra panel:

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

Rad 0 är matchningens start, så dess ram täcker raderna 0–4 och fönsterfunktionerna rapporterar V-formens öppningspris ($100) och bottenpris ($108). Raderna 1–4 ligger inuti matchningen men är inte dess start, så de får NULL. Rad 5 (pris $130) ligger utanför alla matchningar och får likaså NULL.

2.4 Genomgånget exempel 2 — alternation och lexikal ordning

Målet med detta exempelVisa hur en enda kontext bär flera parallella tillstånd när en rad uppfyller mer än ett alternativ — och hur standarden bryter oavgjorda lägen.

Formen (A | B) ger matcharen ett val: vid varje rad testas de två alternativen oberoende, och valfritt antal av dem kan matcha. Det är här multitillståndsnaturen från §2.1 blir synlig inom en enda kontext — inte över kontexter (det är absorption), utan längs parallella grenar som executor utforskar i mönsterordning, tidigare gren först.

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

Tänk dig en rad där priset både har stigit och överstigit $100 — både UP och HIGH är sanna. Varje alternativ skapar sitt eget tillstånd: ett som följer UP-grenen, ett som följer HIGH-grenen. Båda avancerar sedan till DONE, där de möts.

RadSanna variablerAktiva tillstånd
RUP, HIGHTillstånd A (UP-grenen) och tillstånd B (HIGH-grenen) avancerar båda till DONE med samma räknare; B är en dubblett av A och kastas
R+1DONETillstånd A matchar DONE och når #FIN

I standardens termer producerar båda grenarna en matchning av samma längd över samma rader, vilket ger två kandidatvägar — en märkt UP, DONE och en märkt HIGH, DONE. Standarden löser detta genom lexikal ordning: bland alternativen som skrivs i (UP | HIGH) vinner det som skrivs först, oavsett matchningslängd. Eftersom UP kommer före HIGH är den överlevande vägen UP, DONE. Executor upprätthåller detta vid rad R, inte vid FIN: den lägger till UP-grenens tillstånd först, så nfa_append_state_unique() behåller det och släpper det identiska HIGH-grenstillståndet.

Lexikal ordning är det som gör CLASSIFIER() väldefinierad när den så småningom implementeras — den låter körtiden säga till användaren "denna rad matchade UP, inte HIGH" även när båda predikaten var sanna. Lexikal ordning är den primära regeln för alternation: en lex-tidigare gren vinner över en lex-senare även om den lex-senare grenen skulle producera en längre matchning, och en lex-senare (möjligen kortare) gren kan ändå vinna om varje lex-tidigare gren dör innan den når FIN. Girig längd avgörs inom en enskild kvantifierare — givet två kompletteringar av samma alternationsgren föredrar den giriga kvantifieraren fler iterationer.

2.5 Genomgånget exempel 3 — kontextabsorption (samma öde)

Målet med detta exempelVisa varför naivt O(n²) totalt tillståndsarbete blir O(n) under absorption, med O(1) aktiva kontexter.

Det enklaste mönstret som uppvisar absorption är PATTERN (A+) med DEFINE A AS TRUE. Varje rad matchar A, och standarden kräver att matcharen betraktar varje rad som en möjlig matchningsstart. Naivt innebär detta N kontexter för en partition med N rader. Ta en fem-radspartition (vilka data som helst — predikatet är konstant sant):

RadNaiva kontexterMed absorption
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 absorberad
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 kontexterC1[A:5]

Aktiva kontexter minskar från O(n) till O(1), så totalen över partitionen faller från O(n²) till O(n). Absorptionsregeln som motiverar bortkastningen är okomplicerad när kvantifieraren är obegränsad:

Absorptionsregel. Två kontexter vars aktiva tillstånd är vid samma mönsterelement, där den äldre kontexten har en räknare ≥ den nyare, har identiska framtider under en obegränsad kvantifierare. Den nyare kontexten kan kastas; vilken matchning den än så småningom skulle hitta, hittar den äldre kontexten en längre eller lika lång.

Affischens nedre vänstra panel ("① Context Absorption") är exakt denna regel visualiserad över fem rader.

En subtil men viktig poäng döljer sig i regeln: bortkastningen är säker eftersom predikatet A AS TRUE utvärderas till samma värde vid varje rad oavsett vilken kontext som frågar. Samma gäller för varje predikat som endast refererar den aktuella raden eller en fast offset från den — inklusive PREV. Nästa exempel växlar till en konkret handelsvecka av priser med ett PREV-baserat predikat, och §2.6 återanvänder exakt samma vecka för att göra symmetrin mellan säker och osäker absorption uppenbar:

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

Ta handelsveckan $100, $108, $112, $116, $110 från måndag till fredag — fyra uppgångar följda av ett plötsligt fall. Antag att C1 startar på tisdag (första dagen där RISE matchar: $108 > $100), och att executorn spekulativt även följer C2 som startar på onsdag. Varje rads RISE-villkor jämför radens pris med dess omedelbara föregångare — ett partitionsfaktum, inte ett kontextfaktum — så de två kontexterna tvingas beräkna samma boolean vid varje rad de delar:

DagPrisC1 — start tis
price > PREV(price)
C2 — start ons
price > PREV(price)
Mån$100——
Tis$108$108 > $100 ✓ (just startad)—
Ons$112$112 > $108 ✓$112 > $108 ✓ (just startad)
Tor$116$116 > $112 ✓$116 > $112 ✓
Fre$110$110 > $116 ✗ — färdigställ$110 > $116 ✗ — färdigställ
Samma öde Vid varje rad som C1 och C2 delar utvärderar de identiska uttryck och producerar identiska resultat — och på fredag dör de vid exakt samma jämförelse. Vilken framtid C2 än har, har även C1. Att absorbera C2 in i C1 kastar ingenting.

Berättelsen brister i samma stund predikatet börjar bero på varje kontexts egna gränser — och det är vad §2.6 handlar om.

2.6 Genomgånget exempel 4 — när absorption blir osäker

Målet med detta exempelVisa vad som ändras när DEFINE refererar FIRST — absorptionsregeln gäller inte längre och planeraren inaktiverar absorption för mönstret.

Antag att en analytiker vill hitta efterföljande handelsdagar där en aktie hållit sig inom tio dollar från den dag som löpan startade — ett slags konsolideringsfönster. Mönstret och DEFINE ser ut så här:

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

Villkoret jämför nu den aktuella radens pris med priset vid den aktuella löpans start. Två löpor som startat på olika dagar har olika FIRST(price)-värden, så två tillstånd vid samma mönsterelement och samma räknare är inte längre utbytbara: deras framtider beror på den gräns som absorption skulle kasta bort.

Ta exakt samma handelsvecka som i §2.5 — $100, $108, $112, $116, $110 från måndag till fredag. Körtiden håller åter två kandidatlöpor vid liv samtidigt: C1 startade på måndag, C2 startade på tisdag (varje rad är en potentiell löpestart under STABLE+).

DagPrisC1 — start mån
FIRST = $100
price < $100 + 10
C2 — start tis
FIRST = $108
price < $108 + 10
Mån$100$100 < $110 ✓—
Tis$108$108 < $110 ✓$108 < $118 ✓ (just startad)
Ons$112$112 < $110 ✗ — färdigställ mån–tis$112 < $118 ✓
Tor$116—$116 < $118 ✓
Fre$110—$110 < $118 ✓ (löper fortfarande)
Olika öden C1 dör på onsdag med en tvådagars löpa (mån–tis); C2 skulle på egen hand fortsätta löpa hela vägen genom fredag. Samma priser, samma typ av fråga — men olika tak härledda från sina egna matchningsstarter. På exakt samma dag nådde de två kontexterna motsatta slutsatser.

Under absorption skulle C2 ha slagits samman med C1 på tisdag — den sammanslagna kontexten behåller bara C1:s tak ($110), så C2:s distinkta vy (tak $118, en fyradagars löpa genom fredag) täcks inte av C1:s framtid. Just denna vecka råkar utdata inte ändras: C1 registrerar mån–tis, C2 startade inuti den matchningen och kastas av SKIP PAST LAST ROW, och nästa försök startar på onsdag med sitt eget tak ($122) och matchar ons–fre. Generellt sett subsumerar dock en tidigare kontexts DEFINE-resultat inte längre en senares, så räknarjämförelsen som absorption vilar på är ogiltig. Närhelst ett DEFINE-predikat bär matchningsstartberoende inaktiverar planeraren därför absorption preemptivt.

(När den ledande kontextens matchning verkligen lyckas kastas kontexter som startat inom dess accepterade omfång — under standardvärdet AFTER MATCH SKIP PAST LAST ROW — helt enkelt; de hålls vid liv endast för att körtiden ska ha något att falla tillbaka på om den ledande matchningen misslyckas.)

Tabellen nedan utökar affischens nedre högra panel ("② Navigation") med de sammansatta formerna och sammanfattar vilka navigationsformer som skapar matchningsstartberoende:

NavigationMatchningsstart-bero.Absorberbar?
PREV, NEXTingenja
LAST (utan offset)ingenja
LAST med offsetgränskontrollnej
FIRST (alla)direktnej
Sammansatt (inre FIRST)direktnej
Sammansatt (inre LAST, utan offset)ingenja
Sammansatt (inre LAST med offset)gränskontrollnej

De två exemplen i §2.5 och §2.6 reduceras till en enda regel. Samma öde är det som gör absorption säker: om varje kontext vid samma mönsterelement kommer att beräkna samma svar på varje framtida predikat behöver endast den äldsta behållas. Olika öden gör absorption osäker: så snart predikat förgrenar sig på kontext-privat tillstånd — vilket är precis vad FIRST och offset-bärande LAST gör — representerar varje aktiv kontext en framtid som ingen annan kontext garanterat täcker, så att kasta en av dem kan inte längre visas vara säkert.

Planeraren upptäcker denna skillnad vid kompileringstillfället och slår på eller av absorption för hela mönstret; när den är av betalar körtiden multikontextkostnaden. Affischens benchmark i panel ③ använder inget FIRST, så absorption förblir på, vilket är varför PostgreSQL förblir linjär i både framgångs- och misslyckandefallen.

Benchmark-siffrorna på affischen är samma algoritm utspelad i skala. På framgångsmönstret (A+ B+ C+ D) skalar både PostgreSQL och Trino ungefär O(n) när en matchning bekräftats, och PostgreSQL leder med ungefär 16× till 33× (Trino-siffrorna exkluderar redan JVM-uppstarten).

På misslyckandemönstret (A+ B+ C+ E) jagar Trino, som verkar sakna absorption, varje potentiell matchningsstart och degraderas ännu snabbare än O(n²) (ungefär 56× tiden för 5× raderna); vid 100 000 rader tar det mer än fem timmar, medan PostgreSQL fortfarande blir klar på 92 ms, en uppsnabbning på ungefär 217 000×.

Det glappet är inte ingenjörspolering — det är exakt samma öde / olika öden-distinktionen från §2.5 och §2.6, tillämpad på varje rad av varje potentiell matchningsstart i partitionen.

2.7 Genomgånget exempel 5 — när SKIP inaktiverar absorption

Målet med detta exempelVisa ett andra sätt absorption kan misslyckas på: inte för att predikatet splittras, utan för att utdatasemantiken kräver att varje matchning rapporteras separat.

Föregående exempel bröt absorption från data-sidan: FIRST i DEFINE fick varje kontext att utvärdera predikat olika. Absorption kan också brytas från utdata-sidan, och AFTER MATCH SKIP-satsen är det som styr det.

Betrakta mönstret PATTERN (A+) med DEFINE A AS TRUE över fem rader som alla matchar A. Under standardvärdet AFTER MATCH SKIP PAST LAST ROW hittar matcharen den längsta matchningen som börjar vid den tidigaste raden och hoppar sedan förbi den; varje kontext som startat inuti den matchningen kastas implicit som redundant — exakt den situation absorption är designad att hantera. Utdata är en enda matchning, raderna 0–4, och körtiden behöver endast en aktiv kontext.

Växla hopp-läge till AFTER MATCH SKIP TO NEXT ROW så ändras kontraktet:

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

Nu måste varje potentiell startposition rapporteras separat, även när matchningar överlappar. För samma fem rader är körtiden tvungen att avge fem matchningar: raderna 0–4, 1–4, 2–4, 3–4 och 4–4. Ingen av dessa kan ersättas av en "längre som startar tidigare", eftersom standarden säger att användaren vill ha alla.

RadSKIP PAST LAST ROWSKIP TO NEXT ROW
0matchningen börjar; raderna 0–4 blir den enda matchningenmatchningen börjar vid rad 0
1(inuti matchning 0)matchningen börjar vid rad 1 — måste hållas vid liv
2(inuti matchning 0)matchningen börjar vid rad 2 — måste hållas vid liv
3(inuti matchning 0)matchningen börjar vid rad 3 — måste hållas vid liv
4matchning 0 färdigställs (raderna 0–4)fem matchningar färdigställs: 0–4, 1–4, 2–4, 3–4, 4–4
Olika utdata, olika öden Under AFTER MATCH SKIP TO NEXT ROW är varje sent startad kontext sin egen utdatarad. Två kontexter vid samma mönsterelement är inte längre redundanta — de är båda obligatoriska utdata, och att kasta en av dem skulle tyst släppa en matchning som användaren bett om.

Observera att predikatet inte har ändrats. A AS TRUE utvärderas likadant vid varje rad oavsett vilken kontext som frågar, så samma öde-villkoret från §2.5 är fortfarande uppfyllt. Det som ändras är utdata-kravet: även kontexter med identiska framtider måste samexistera eftersom de motsvarar distinkta rader i resultatet. Planeraren inaktiverar därför kontextabsorption närhelst AFTER MATCH SKIP TO NEXT ROW är aktivt, oavsett DEFINE-satsen.

Att ställa §2.6 och §2.7 sida vid sida ger de två sätt på vilka en frågas semantik utesluter absorption:

Datasida · §2.6
Predikatet utvärderas olika per kontext.
Utlöses av FIRST eller offset-bärande LAST i DEFINE.
Utdatasida · §2.7
Utdata kräver att varje matchningsstart är en separat rad.
Utlöses av AFTER MATCH SKIP TO NEXT ROW.

Endera villkoret räcker för att inaktivera absorption för hela mönstret, och detsamma gäller en ram som inte slutar vid UNBOUNDED FOLLOWING. När inget av dem är aktivt — standardvärdet AFTER MATCH SKIP PAST LAST ROW, ett obegränsat ramslut och DEFINE-villkor som endast använder PREV, NEXT eller bart LAST — är absorption aktiverad, men endast för tillstånd i mönstrets absorberbara region: en ledande girig obegränsad variabel såsom A+ eller A*, en grupp med fast längd och en obegränsad girig kvantifierare såsom (A B)+, en girig grupp vars kropp börjar med någon av dessa såsom (A+ B)+ eller (A+ B){2}, eller alternationsgrenar byggda av dessa; en motvillig grupp diskvalificerar hela sitt delträd. Där detta gäller, som för A+ i §2.5, kollapsar körtiden till en enda kontext och förblir linjär; START UP+ DOWN+ från §2.3 får ingen absorberbar region alls.

§3. Design — från parser till executor

Row Pattern Recognition implementeras som tre stadier som lämnar över arbete via väldefinierade mellanformer. Parsern omvandlar SQL-text till ett mönsterträd och en lista över DEFINE-predikat; planeraren kompilerar trädet till en platt array av mönsterelement och avgör vilka av dem som kan delta i kontextabsorption; executor kör arrayen mot partitionen rad för rad i en trefaslupp. Varje stadium har sin egen dataform, och det mesta av designens påhittighet finns vid gränserna: en platt NFA som ryms i cache, en navigationsmodell som återanvänder en enda tupel-slot snarare än att materialisera en per referens, och en absorptionsregel som omvandlar O(n²)-arbete till O(n).

SQL-text
  │
  │  parserstadium
  ▼    validera ram
       bygg mönsterträd
       typkontrollera DEFINE

mönsterträd + DEFINE-lista
  │
  │  planerarstadium
  ▼    optimera trädet
       kompilera till platt NFA-array
       avgör absorberbarhet

platt NFA + absorptionsflaggor
  │
  │  executorstadium
  ▼    per-rad-motor:
       Match → Absorb → Advance

matchningsresultat:
  startrad, längd, framgång/misslyckande

Avsnitten nedan följer denna pipeline. §3.1 täcker parsern och mönsterträdets form; §3.2 täcker kompileringen som omvandlar trädet till den platta NFA:n; §3.3 täcker navigationsmodellen som DEFINE-predikat använder för att titta på angränsande rader; §3.4 täcker hanteringen av matchningsgränser — SKIP-, INITIAL- och begränsad ram-reglerna som fastställer var en matchning börjar och slutar; §3.5 är per-rad-motorn i tre faser; §3.6 samlar alla beskärningsmekanismer som håller tillståndsrymden begränsad; och §3.7 går igenom vad implementationen exponerar i EXPLAIN-utdata.

3.1 Parser — bygga mönsterträdet

Parsern känner igen mönsteridentifiering genom närvaron av en PATTERN-sats inuti en fönsterspecifikation. Dess första uppgift är ramvalidering, eftersom RPR ålägger begränsningar som vanliga fönsterfrågor inte gör: ramläget måste vara ROWS (inte RANGE eller GROUPS), startgränsen måste vara CURRENT ROW, slutgränsen måste vara UNBOUNDED FOLLOWING eller en positiv offset FOLLOWING (så en standardram avvisas också), och EXCLUDE-alternativ andra än EXCLUDE NO OTHERS är förbjudna. Dessa är överensstämmelsekontroller, inte optimeringar — RPR:s uppfattning om en ram är matchningsomfånget, och standarden överväger inte att fylla det med något annat än de matchade raderna.

När ramen klarat valideringen omvandlar parsern PATTERN-satsen till ett träd byggt av fyra slags noder — en variabelreferens, en sekvens (konkatenering), en alternation och en grupp (delmönster inom parentes). Varje nod bär kvantifieraren som tre tal — en undre gräns, en övre gräns (möjligen oändlig) och en flagga för motvillig matchning:

KällaTrädkodning
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)

Varje DEFINE-predikat typkontrolleras sedan mot partitionens kolumner och tvingas till ett booleskt uttryck. Två praktiska saker följer. För det första lägger parsanalysen inte till något i frågans mållista för DEFINE; i stället markerar planeraren varje kolumn som ett DEFINE-predikat refererar som behövd, så som den gör för HAVING, och propagerar dessa kolumner genom till executorstadiet även om den omgivande frågan inte väljer dem — utan det skulle körtiden inte ha något att utvärdera mot. För det andra är variabler som förekommer i PATTERN men aldrig i DEFINE implicit sanna: de matchar varje rad.

3.2 Kompilering — från AST till en platt NFA

Planeraren omvandlar parserns träd till den datastruktur som executor kommer att köra: en platt array av mönsterelement adresserad via index. Kompileringen fortskrider som en sexstegs-pipeline:

compile(astTree):
  1. optimera AST
  2. mät storlek och djup
  3. allokera elementarrayen
  4. fyll från AST
       (tilldela next/jump-pekare)
  5. färdigställ — sätt upp FIN-sentinel
  6. markera absorptionsberättigade element

Den platta formen valdes av ett enkelt skäl: executor behöver traversera mönstret många gånger per partition, och en sammanhängande indexerbar array är den billigaste datastrukturen att gå igenom. Stegen 1 och 6 är de intressanta — steg 1 för att det avgör hur stor arrayen blir, och steg 6 för att det avgör om absorptionsoptimeringen i §2.5 alls aktiveras.

AST-optimering

Optimeringen lönar sig två gånger: en gång i den statiska elementräkningen av den platta arrayen, och igen för varje rad som bearbetas vid körtid. Varje transformation reducerar tillståndsrymden som körtiden måste räkna upp. Optimeraren tillämpar nio omskrivningsregler i ett enda nedifrån-och-upp-pass (inom en sekvens körs gruppsammanslagningen en gång till, eftersom tidigare sammanslagningar kan föra samman två identiska grupper):

SEQ-utplattning
SEQ(A, SEQ(B, C)) → SEQ(A, B, C)
Sammanslagning av efterföljande variabler
A A → A{2}
A{2,3} A{1,2} → A{3,5}
Sammanslagning av efterföljande grupper
(A B)+ (A B)+ → (A B){2,∞}
Sammanslagning av efterföljande ALT
(A | B) (A | B) (A | B) → (A | B){3}
Prefix/suffix-sammanslagning
A B (A B)+ → (A B){2,∞}
ALT-utplattning & dedup
(A | (B | C)) → (A | B | C)
(A | B | A) → (A | B)
Kvantifierare-multiplikation
(A+)+ → A+
(A{2,3}){5} → A{10,15}
Inpackning av enbarn
SEQ(A) → A
(A){1,1} → A
Motvillighetsnormalisering
A{2}? → A{2} (motvillighet rensas överallt där min = max)

Kvantifierare-multiplikation kollapsar endast när de uppnåeliga räknarna bildar ett sammanhängande intervall och den föredragna matchningen inte flyttas: en exakt yttre ((A{2,3}){5} → A{10,15}), ett barn med min 0, eller barnintervall som möts med ett barn-min på högst 1 eller ett obegränsat barn-max ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), där en yttre med min 0 dessutom kräver ett barn-min på högst 1 ((A{2,})* står kvar, eftersom A* skulle acceptera en rad). Ett gruppbarn vars egen kvantifierare inte är exakt måste först ha en kropp med fast längd, så ((A | B B){1,2}){2} lämnas orört även under en exakt yttre. Andra kombinationer kan introducera luckor som den platta formen skulle missa — t.ex. (A{2}){2,3} accepterar bara {4, 6}, men ett naivt A{4,6} skulle också acceptera 5 — eller flytta den föredragna matchningen ((A{2,3}){1,2} föredrar tre rader där A{2,6} tar fyra), så optimeraren lämnar dem orörda. Det är inte den enda villkorade omskrivningen: gruppsammanslagning och suffixsammanslagningen kräver en kropp som konsumerar ett fast antal rader, prefixsammanslagningen avböjer en grupp med min 0, ett ändligt max och nollbart innehåll, motvilliga noder varken slås samman eller multipliceras ((A+?)+ står kvar), och en omskrivning vars nya gräns skulle flöda över avböjs.

Elementform

Varje element i den platta arrayen representerar en enskild position i mönstret. Det finns sex logiska sorter: en variabelreferens (den enda sorten som konsumerar en rad); markörerna group begin och group end, vilka öppnar och stänger ett delmönster inom parentes; en alternationsmarkör, som leder en lista av grenar; en grenseparator som avslutar varje gren; och en slutmarkör i slutet av mönstret.

Varje element bär även ett djup (dess gruppnästningsnivå), kvantifieraren (en min- och max-upprepningsräknare, möjligen oändlig) och två övergångspekare — next, "vart ska man gå efter att ha konsumerat detta element," och jump, "vart ska man hoppa till" (används av alternationsmarkören och grenseparatorerna för att kedja grenar, av group begin för att namnge sitt eget group end — en grupp vars kvantifierare tillåter noll hoppas över via det END:s next — och av group end för att loopa tillbaka till kroppen).

För PATTERN ((A B)+) ser den kompilerade arrayen ut så här:

PATTERN ((A B)+) kompileras till:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 3
    (öppnar grupp; jump namnger
     sitt eget 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
    (stänger grupp; jump loopar tillbaka)

[4] FIN    mönstret klart

Mönstret läses från vänster till höger via next, med jump som hanterar de icke-linjära kanterna. Vid idx 3 pekar END:s jump tillbaka till idx 1, vilket är hur den obegränsade yttre kvantifieraren loopar; vid idx 0 namnger BEGIN:s jump dess END vid idx 3, och om gruppen var valfri skulle hoppet lämna via det END:s next till idx 4 utan att anlända till END. Körtiden behöver aldrig konstruera en graf vid körtiden — den följer bara dessa två pekare när den går igenom arrayen.

Per-element-attribut

Utöver formen bär varje element fem logiska attribut som styr körtidens beteende vid den positionen:

Motvillig
Vänder ordningen för kvantifierarexpansion. Giriga kvantifierare försöker "loopa igen" före "avsluta"; motvilliga kvantifierare försöker "avsluta" först. Bärs av variabeln för A+?; bärs av gruppens BEGIN och END för ((…)+?).
Tomt-loopbar
Sätts på gruppslut vars kropp är nollbar ((A? B?)+, (A | B*)+; (A?)* multipliceras först till A* och lämnar inget gruppslut). Säger åt körtiden att lägga till en snabbavslutning vid sidan av den normala återloopningen under min, så att cykelvakten inte dödar legitima matchningar i grupper som kan producera tomma iterationer.
Tomt-föredragen
Sätts på gruppslut vars kropp föredrar den tomma matchningen, som i (A?? B??){2}. Ordnar snabbavslutningen före återloopningen under min, där gruppens egen girighet inte säger något.
I-absorberbar-region
Markerar varje element som ligger inom en absorptionsberättigad region — används av körtiden för att spåra om det aktuella tillståndet fortfarande befinner sig i säkert territorium.
Absorptionsjämförelsepunkt
Markerar det specifika element där absorptionsjämförelser ska köras. För ett enkelt A+ hamnar den på variabeln; för en obegränsad grupp som (A B)+ hamnar den endast på gruppslutet.

Uppdelningen mellan "i regionen" och "jämförelsepunkt" har betydelse eftersom absorption endast är meningsfull vid punkter där iterationer stängs. Inuti kroppen av (A B)+ är körtiden mitt i en iteration och räknaren har ännu inte nått sitt slutgiltiga värde för den rundan; att jämföra här skulle innebära att jämföra ojämförbara värden. Tillståndet måste nå gruppslutet innan körtiden kan avgöra. Det första attributet säger därför "du är fortfarande i absorberbart territorium"; det andra säger "du har nått jämförelsepunkten — kontrollera nu".

Absorberbarhetsanalys

Steg 6 i kompileringen är det som ger §2.5:s "samma öde"-regel dess kompileringstidsvittne. Beslutet är skiktat:

isAbsorbable(query):
  if SKIP-läge != SKIP PAST LAST ROW
      → return false
  if ramslut != UNBOUNDED FOLLOWING
      → return false
  if någon DEFINE beror på match_start
      → return false
  gå igenom den platta arrayen från
  element 0 och markera element
  som uppfyller ett strukturellt fall

De tre första kontrollerna är frågenivå: de motsvarar exakt villkoren §2.7 (utdatasida: SKIP-läge), begränsad ram (gränsen bryter monotoniciteten) och §2.6 (datasida: FIRST eller offset-bärande LAST i DEFINE). När någon av dem misslyckas sätter analysen inga flaggor och absorption är inaktiverad för hela frågan. När alla godkänns tillåter genomgången fyra strukturella former:

Fall 1 — enkel obegränsad variabel
A+, A*, A{2,∞}
Varje iteration är exakt en rad. En tidigare kontexts räknare är alltid ≥ en senares vid varje delad position.
Fall 2 — grupp med fast längd, obegränsad ytter
(A B)+, (A B{2})+, ((A (B C){2}){2})+
Varje barn har min == max, så kroppen är semantiskt ekvivalent med sin utrullade {1,1}-form — (A B{2})+ beter sig som (A B B)+. Varje iteration konsumerar ett fast antal rader; räknardominans gäller fortfarande.
Fall 3 — grupp vars kropp börjar med en obegränsad variabel
(A+ B)+, (A+ B){2}
Den ledande obegränsade variabeln är själv absorberbar (Fall 1) och skyddar tidigare kontexter. Absorption stannar så snart tillståndet flyttar förbi A — resten av kroppen har ingen monotonicitetsgaranti, så A får båda flaggorna, den omslutande BEGIN får in-region-flaggan, och B och END får ingen.
Fall 4 — alternation
A+ | B+, A+ | C D
Varje gren, nådd via separatorkedjan, bedöms för sig av fallen ovan; alternationsmarkören får in-region-flaggan när någon gren kvalificerar sig.

De strukturella fall som inte täcks av dessa fyra former är lika instruktiva. A B+ kan inte absorberas av den nuvarande regeln eftersom det ledande A konsumerar en rad innan den obegränsade delen börjar, så kontexter som startar en rad isär befinner sig vid olika positioner inuti den obegränsade kroppen. Motvilliga kvantifierare som A+? utesluts genom konstruktion: absorptionsregeln antar girig semantik där längre matchningar subsumerar kortare, och motvillig matchning vänder den riktningen.

Resultatet är ett per-element-beslut snarare än ett per-mönster-beslut. En enda frågeplan kan ha absorption aktiverad för det ledande A+ i mönster som (A+ B+ C) eller (A+ B+)+ — det senare är bara Fall 3 tillämpat på dess ledande element — och inaktiverad för allt därefter; körtiden konsulterar helt enkelt jämförelsepunktsattributet på det aktuella tillståndets element varje gång den överväger en absorptionsomgång. När ett tillstånd flyttar in i en icke-absorberbar region är absorption permanent av för det tillståndet — exakt vad §2.5 och §2.6 behöver för att vara sant på den algoritmiska nivån.

3.3 Navigation — 1-slots-tupelbytet

DEFINE-uttryck är vanliga SQL-uttryck som utvärderas mot en rad, men de kan innehålla PREV, NEXT, FIRST eller LAST — referenser som pekar på olika rader. Raderna själva buffras redan i fönstrets tuplestore; det executorn fortfarande måste hantera är tupel-sloten som SQL-uttrycksmaskineriet läser från, eftersom kolumnreferenser inuti uttrycket är bundna till en slot vid plantid. Implementationen återanvänder en enda navigations-slot för varje navigationsanrop: sloten byts in före utvärderingen av det inre uttrycket och återställs efter, så att resten av SQL-uttrycksmaskineriet aldrig märker skillnaden.

Modellen som executor ser är liten: det finns en aktuell rad-slot som håller raden DEFINE-uttrycket utvärderas mot, och en navigations-slot som körtiden tillfälligt kan dirigera om till en annan rad. Runt varje navigationsanrop sätter körtiden upp navigations-sloten, utvärderar det inre uttrycket som om det läste den aktuella raden och återställer sedan den ursprungliga raden. Pseudokod:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos är utanför sitt giltiga intervall:
      return NULL

  spara current_row_slot
  if targetPos != currentPos:
      hämta rad vid targetPos
        in i nav_slot
      peka yttre slot mot nav_slot
  result = eval_inner_expression()
  återställ current_row_slot
  kopiera by-ref-resultat ut ur nav_slot
  return result

Knepet är att det finns exakt en slot att spara och återställa. Det inre uttrycket — vad det än är, inklusive aritmetik, funktionsanrop eller andra kolumnreferenser — körs mot den utbytta sloten via samma utvärderingsväg som för den aktuella raden. Ingen alternativ utvärderare och ingen slot per referens; när målet är den aktuella raden hoppas hämtningen och bytet över helt. Hämtningen kopierar målraden till navigations-sloten (om inte sloten redan håller den), och återställningssteget kopierar ett pass-by-reference-resultat till per-tupel-minne så att nästa hämtning inte kan frigöra det.

Sammansatt navigation plattas ut vid parstid så att bytet fortfarande sker en gång. PREV(FIRST(price)) identifieras som en tvåstegs-navigation — "gå till den första matchade raden, stega sedan en rad tidigare" — och lagras som ett enda navigationsanrop av sammansatt typ. Körtiden beräknar målpositionen i två stadier men utför endast ett slot-byte för att hämta den slutgiltiga raden:

compute_target_position(call):

  # relativt aktuell rad
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # matchningsrelativt
  FIRST(n):
      return matchStart + n
  LAST(n):
      return currentPos − n

  # sammansatt: matchnings-rel., sedan steg
  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

  validera mot lämpligt intervall
  (matchningsintervall för FIRST/LAST inre,
   partitionsintervall för yttre steg)

En positions-cache kortsluter tuplestore-hämtningen när flera navigationsanrop i samma DEFINE riktar sig mot samma rad — vanligt i uttryck som price > PREV(price) AND volume > PREV(volume) där båda anropen löses till föregående rad. Cachen lagrar endast "senast hämtad position", och bytet i sig förblir en enda operation.

Klassificeringen av navigationsanrop är planerarens bidrag till absorptionsbeslutet. Planeraren går igenom varje DEFINE-uttryck och sorterar varje variabel i en av två hinkar, baserat på om alla kontexter kommer att beräkna samma boolean vid samma rad eller om varje kontext kommer att beräkna sin egen. Hinken bestämmer två saker vid körtid: hur ofta variabeln utvärderas (delat en gång eller en gång per berörd kontext — §3.5 fas 1), och om kontextabsorption alls är möjlig (§2.5 vs §2.6): en enda matchningsstartberoende variabel inaktiverar den för hela mönstret.

Delad utvärdering · absorptionssäker Varje kontext ser samma boolean vid varje rad — samma öde (§2.5).
  • Ingen navigation
  • Endast PREV / NEXT
  • LAST utan offset
  • Sammansatt med inre LAST (utan offset)
Per-kontext-utvärdering · absorptionsosäker Kontexter med olika matchningsstarter beräknar olika svar — olika öden (§2.6).
  • LAST med offset
  • FIRST (alla former)
  • Sammansatt med inre FIRST
  • Sammansatt med inre LAST (med offset)

Klassificeringen utförs vid plantid och lagras vid sidan av varje DEFINE-variabel, så att körtiden inte lägger någon tid på att avgöra — den läser helt enkelt hinken för varje variabel när den behandlar en rad.

Bevarandebudget

Navigation når in i rader som fönsterfunktionsmaskineriet annars har strömmat förbi. För att hålla dessa rader tillgängliga är executor byggd ovanpå en tuplestore som behåller ett glidande fönster av senaste rader; frågan är hur brett det fönstret behöver vara. Executorn räknar ut det utifrån två kompletterande offsets och löser varje offset en gång per skanning (konstanta även vid executor-init, så att vanlig EXPLAIN kan visa dem):

Lookback-budget
Hur långt bakåt från den aktuella raden ett DEFINE-anrop kan nå.
Bidragsgivare: PREV, LAST (alla offsets, inklusive standardvärdet 0), PREV(LAST(...)), NEXT(LAST(...))
Lookahead-från-start-budget
Den minsta framåträckvidden (bakåt, när negativ) från den äldsta aktiva kontextens matchningsstart — den tidigaste rad som något DEFINE-anrop kan behöva.
Bidragsgivare: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

Vid körtid sätts tuplestores trim-märke till den tidigare av två positioner — aktuell rad minus lookback-budgeten, och den äldsta aktiva kontextens matchningsstart plus lookahead-budgeten. Allt före det märket kan inte nås av något navigationsanrop i någon aktiv kontext, och tuplestoren är fri att kasta det. De Nav Mark-rader som EXPLAIN rapporterar (§3.7) — Lookback och Lookahead — är dessa två budgetar, inte uppmätta toppar. Var och en skrivs ut endast när någon navigation matar den och visas även utan ANALYZE; en offset vars värde är känt först vid körtid (till exempel en parameter i en generisk plan) skrivs ut som runtime under vanlig EXPLAIN och som sitt upplösta värde under EXPLAIN ANALYZE, och retain all (Lookback) eller infinite (Lookahead) markerar en offset som flödar över.

3.4 Matchningsgränser — SKIP, INITIAL och begränsad ram

Ett matchningsresultat registreras som två värden: raden där matchningen börjar och dess längd. En negativ start betyder att positionen ännu inte har utvärderats; när starten väl är satt kan efterföljande frågor till executor — "är denna rad inuti en matchning?" — besvaras i O(1) genom att inspektera paret. Längden kodar utfallet: -1 för en omatchad rad, 0 för en tom matchning och radantalet för en verklig matchning. En längd noll är ett verkligt utfall, inte ett fel: det representerar ett mönster som matchade utan att konsumera någon rad, vilket executor måste skilja från både en omatchad rad och "ingen matchning har försökts vid denna position än".

AFTER MATCH SKIP-satsen avgör var nästa matchningsförsök startar. AFTER MATCH SKIP PAST LAST ROW flyttar till raden efter matchningsslutet och producerar det icke-överlappande utdata som de flesta frågor vill ha samt aktiverar absorptionsoptimeringen.

AFTER MATCH SKIP TO NEXT ROW flyttar endast till raden efter matchningens start och tillåter överlappande matchningar; planeraren inaktiverar därför absorption för det fönstrets mönster när detta läge är aktivt.

De två hoppmål som standarden också definierar — AFTER MATCH SKIP TO FIRST var och AFTER MATCH SKIP TO LAST var — beror på per-matchningshistorik som denna patch inte behåller. De finns inte alls i grammatiken, så parsern rapporterar ett generiskt syntaxfel om endera anges.

Detsamma gäller SEEK, specifikationens alternativ till INITIAL. Under SEEK kan ett matchningsförsök som startar vid rad R lyckas vid vilken rad som helst från R till ramens slut, inte bara vid R själv. Patchen implementerar endast INITIAL: varje potentiell matchning förankras vid en specifik rad. Parsern rapporterar ett fel om SEEK begärs. Begränsade ramar får sin egen behandling — när användaren skriver ROWS BETWEEN CURRENT ROW AND N FOLLOWING i stället för UNBOUNDED FOLLOWING, kortsluter executor varje kontext vars matchning nått gränsen genom att tvinga fram en miss, och absorption inaktiveras eftersom gränsen bryter monotonicitetsantagandet som absorption vilar på.

3.5 Per-rad-motorn i tre faser

Executors per-rad-drivrutin anropas av det omgivande fönsterfunktionsmaskineriet närhelst det behöver veta om en given rad tillhör en matchad ram. Drivrutinen hittar eller skapar kontexten för den aktuella startpositionen och driver sedan NFA:n framåt rad för rad — med en per-variabel-matchningsarray som återställs till "outvärderad" för varje rad — tills den kontexten inte har några aktiva tillstånd kvar eller partitionen tar slut. DEFINE-predikat utvärderas lat: en variabel utvärderas första gången något tillstånd konsumerar den, så en variabel som inget aktivt tillstånd testar på denna rad utvärderas aldrig. Själva framåtsteget består av tre faser i fast ordning — Match, Absorb, Advance — inneslutna i samma yttre loop:

processRow(currentPos):

  # Fas 1 — MATCH (konvergens)
  for varje kontext:
      if kontext nått sitt ramslut:
          tvinga fram miss (färdigställ tidigt)
          continue
      if matchStartRow skiljer sig från
         den delade utvärderingspositionen:
          återställ matchningsstartberoende
          DEFINE-vars till outvärderade (§3.3)
      match(kontext, varMatched)

  # Fas 2 — ABSORB
  if mönstret är absorberbart:
      uppdatera varje kontexts flaggor
      absorb_contexts()

  # Fas 3 — ADVANCE (divergens)
  for varje kontext:
      advance(kontext, currentPos)
      if den registrerade en matchning och
         SKIP PAST LAST ROW:
          beskär senare kontexter som
          startar inuti matchningen

Ordningen är inte ett stilval. Match måste köras först eftersom absorption jämför post-match-räknare; att köra Absorb före Match skulle jämföra tillstånd som är på väg att dö. Advance måste köras sist eftersom det är den enda fasen som skapar nya tillstånd — den expanderar varje överlevande tillstånd genom epsilonövergångar tills vart och ett når en variabel som väntar på nästa rad. Att köra Absorb efter Advance skulle innebära att jämföra divergerade efterföljare och missa den punkt där tillstånden är som renast jämförbara.

Fas 1 — Match

Match är en "konvergens"-fas: tillstånd antingen överlever med en inkrementerad räknare eller dör. En subtil poäng är att för variabler som sitter i en absorberbar region utför Match också en liten mängd framåtprogress, så att Absorb kan jämföra rent. Täckningsvillkoret aktiveras endast vid den absorberbara jämförelsepunkten — END för den obegränsade gruppen — så tillstånd som just matchat mellan-iterations-variabler (som B inuti (A B)+) behöver förflyttas upp till den jämförelsepunkten under själva Match; annars hittar Absorb inget berättigat att jämföra och optimeringen aktiveras aldrig.

match(context, varMatched):
  for varje tillstånd i kontexten:
      elem = pattern[state.elemIdx]
      assert elem är en variabel
          # advance parkerar endast variabler

      if varMatched[elem.varId] är
         outvärderad:
          utvärdera dess DEFINE nu
      if not varMatched[elem.varId]:
          släpp tillstånd   # död gren
          continue

      state.counts[elem.depth] += 1

      # Inline framåtprogress så att
      # nästa fas kan jämföra vid
      # jämförelsepunktselementet i stället
      # för mitt i iterationen.
      if elem är in-region men inte
         jämförelsepunkten,
         och har nått sin max-räknare,
         och elem.next är ett gruppslut:

          gå END-kedjan:
            inkrementera yttre grupps räknare
            avancera state.elemIdx till END
            fortsätt så länge fortfarande in-region,
              måste-avsluta, och next är END
          (stannar vid jämförelsepunkten
           eller vid ett fortfarande loopbart element)

Genomgången av END-kedjan är det som gör nästlade grupper med fast längd absorberbara. I ((A B){2})+, när B når sin max (B är {1,1}), måste den inre gruppens räknare inkrementeras; om den räknaren också når sin max — och stänger den inre {2} — måste även den yttre gruppens räknare inkrementeras, och så vidare, tills tillståndet hamnar på den yttersta absorptionspunkten — END för den obegränsade yttre gruppen (+). Att göra detta arbete i Match låter Absorb jämföra mot kontexter som redan konsoliderat sina post-iterations-räknare.

Fas 2 — Absorb

Absorb-passet går igenom kontexter från nyast (svans) till äldst (huvud). För varje pågående kontext som är fullt absorberbar söker det bakåt efter en äldre pågående kontext som täcker den, och frigör den nyare om någon hittas. Eftersom kontexter hålls i skapandeordning och varje rad skapar högst en kontext betyder "nyare" och "äldre" verkligen "startade senare" och "startade tidigare".

absorb_contexts():
  for ctx från svans bakåt:
      if ctx är klar
         eller har något icke-absorberbart tillstånd
         eller håller en registrerad matchning:
          hoppa över
      for äldre från ctx.prev bakåt:
          if äldre är klar
             eller inte har något absorberbart tillstånd:
              hoppa över
          if covered(äldre, ctx):
              free(ctx)
              registrera absorptionslängd
              break

covered(äldre, nyare):
  for varje tillstånd i nyare:
      elem = pattern[state.elemIdx]
      if elem inte är jämförelsepunkten:
          return false
      if inget tillstånd i äldre med:
            samma elemIdx
            och isAbsorbable
            och äldre.counts[depth]
                >= nyare.counts[depth]:
          return false
  return true

Två mikrobeslut följer av detta. Det första är att täckningskontrollen avvisar omedelbart om något tillstånd i den nyare kontexten sitter någon annanstans än vid en jämförelsepunkt — att jämföra vid icke-bedömningspunkter skulle inte vara en meningsfull jämförelse.

Det andra är det asymmetriska flaggparet på varje kontext: har-absorberbart-tillstånd besvarar "kan denna kontext absorbera en nyare?" och är monotont (det kan endast gå sant→falskt när tillstånd dör), medan alla-tillstånd-absorberbara besvarar "kan denna kontext absorberas?" och är dynamisk (det vänder tillbaka till sant när ett icke-absorberbart tillstånd tas bort) tills kontexten registrerar en matchning, vilket låser den till falskt — att absorbera skulle frigöra en matchning som ingen absorberande kontext kan återskapa. Båda flaggorna kontrolleras i konstant tid innan täckningssökningen ens startar, så absorption betalar sin fulla kostnad endast på kontexter som har en verklig chans att absorberas.

Fas 3 — Advance

Advance är "divergens"-fasen: varje överlevande tillstånd expanderas genom epsilonövergångar tills varje gren når antingen en variabel som väntar på nästa rad eller FIN-sentinelen. Expansionen är djupet-först, och den ordning i vilken syskongrenar gås igenom är det som gör att standardens preferensregel faktiskt får effekt — den lexikalt första grenen läggs alltid till först, och dedupliceringssteget vid tillståndsinsättning kastar tyst ekvivalenta senare tillägg.

advance(context, currentPos):
  plocka ut alla nuvarande tillstånd;
  bygg om ctx.states från grunden
  for varje tillstånd i lexikal ordning:
      rensa besökt-bitmappen
      advance_state(state)   # DFS

      # Preferens: när en DFS når FIN
      # är återstående tillstånd mindre
      # föredragna och kan släppas.
      if FIN nåddes och tillstånd kvarstår:
          frigör resten
          break

advance_state(state):
  gå via state.elemIdx,
  rekursera genom:
    ALT-grenar (i ordning, stannar
                när FIN registrerats),
    BEGIN (gå in i grupp; plus valfri
           hopppath om min = 0),
    END (loopa tillbaka / avsluta / snabbavslut —
         se nedan),
    FIN (registrera matchEndRow,
         spara matchedState och flagga
         kontexten så att senare kontexter
         inom denna kandidats omfång
         beskärs — se nedan),
  stannar vid varje variabel som påträffas:
      lägg till tillstånd i ctx.states
      (deduplicerar via elemIdx + counts)

Att registrera ett tillstånd som nådde FIN gör mer än att bara bokmärka kandidatmatchningen. Under AFTER MATCH SKIP PAST LAST ROW måste nästa rapporterbara matchning starta strikt efter den aktuella — så när Advance är klar med kontexten som registrerade en kandidat beskärs varje efterföljande kontext vars startrad ligger inom kandidatens omfång på samma rad, även om kontexten som träffade FIN kan fortsätta söka efter en längre matchning genom girig fallback.

Beskärningen är säker eftersom oavsett hur den sökningen slutar (en längre matchning ersätter kandidaten, eller kandidaten står sig) så startade alla beskurna kontexter inom ett omfång som nästa rapporterbara matchning måste hoppa förbi och kunde därför aldrig producera egna utdata.

Detta är det kontextöverskridande FIN-tids-beskärningssteget. Inom kontexten skär FIN också bort lexikalt underordnat arbete: Advance släpper de återstående köade tillstånden (beskrivet tidigare i detta avsnitt), och inom en DFS stannar varje mindre föredragen väg — senare ALT-grenar, den andra av BEGIN:s hopp- och inträdesvägar, en motvillig variabels inträdesväg, den andra av END:s loop- och avslutsvägar — när en matchning har registrerats, så en advance registrerar högst en matchning.

Den knepigaste per-element-logiken finns i END-hanteraren. När en grupps iterationsräknare är under den nedre gränsen måste körtiden loopa tillbaka; när den är vid eller över den övre gränsen måste den avsluta; däremellan är båda alternativen giltiga och kvantifierarens girighet avgör vilket som ska prövas först:

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

  if count < elem.min:
      loopa tillbaka in i kroppen
      if elem är empty-loopable:
          # nollbar kropp, se §3.2
          klona även ett snabbavsluts-
          tillstånd som lämnar gruppen
          med räknaren uppfylld
          (snabbavslut först om kroppen
           föredrar tom; den andra vägen
           släpps om den första nådde FIN)

  elif count >= elem.max:
      återställ räknare på detta djup
      avsluta via next
      (END→END: inkrementera yttre
       END:s räknare)

  else:
      # min <= count < max: förgrena
      bygg ett avslutningstillstånd
      (räknare på detta djup nollställs)
      if girig:
          loopa först
          if loop nådde FIN:
              släpp avslutet
              # föredra längre
          else avsluta sedan
      else (motvillig):
          avsluta först
          if avslut nådde FIN:
              släpp loopen
              # föredra kortare
          else loopa sedan

Varje tillstånd som läggs till i en kontext går igenom en dedupliceringskontroll som jämför dess position och räknare med den befintliga tillståndslistan. Eftersom Advance bearbetar grenar i DFS-ordning hamnar tillståndet från den första grenen i varje alternation först — och varje senare gren som producerar samma position och räknare avvisas vid insättning. Detta är exakt vad §2.4:s regel om lexikal ordning ber om, implementerat längst ned i körtiden utan ett separat pass.

Tomt-loopbara grupper

Ett subtilt fall som körtiden måste oskadliggöra är den nollbara gruppen — en grupp vars kropp kan matcha noll rader för att varje barn till kroppen självt är valfritt. Mönster som (A? B?)+ och (A | B*)+ har denna egenskap: beroende på data kan kroppen slutföra en iteration utan att konsumera någon rad alls. (Ett enda valfritt barn som (A?)* skrivs om till A* vid kompileringstillfället och lämnar ingen grupp efter sig.) Det är okej i princip, men det skapar en verklig fara för NFA:ns epsilonexpansion. Om kroppen producerar en tom matchning loopar END-elementet tillbaka in i kroppen (dess jump är gruppens första barn), kroppen producerar återigen en tom matchning, når END igen, och så vidare. Utan något som stoppar det skulle Advance:s DFS aldrig terminera.

Vakten avgörs vid kompileringstillfället och utförs vid körtid. Närhelst planeraren ser en grupp vars kropp är nollbar märker den den gruppens END-element som tomt-loopbar. Körtiden håller en besökt-bitmapp, nollställd före varje tillstånds DFS-expansion, i vilken endast dessa märkta END markeras — inget annat kan cykla, eftersom varje annan återloopning har konsumerat en rad. Att nå ett markerat END betyder att kroppen just härlett en tom iteration, och tillståndet kastas inte: vid eller över den nedre gränsen lämnar det gruppen där (en tom iteration stoppar kvantifieraren), och under den faller tillståndet igenom till den normala återloopningen, så varje tom ankomst höjer ändå räknaren tills den når min. Ta (A? B?){2,3} utan att någon av variablerna matchar någonstans i radströmmen:

iter 1: A? B? matchar noll rader
        → END, count = 1 (under min)
        END redan markerat (vid
        gruppinträde), men under min:
        → loopa tillbaka in i A?
iter 2: A? B? matchar noll rader
        → END, count = 2 (uppfyller min)
        END redan markerat, vid min:
        → lämna gruppen
avsluta med en noll-längds matchning

Under den nedre gränsen säger tomt-loop-taggen också åt END-hanteraren att klona ett ytterligare snabbavsluts-tillstånd vid sidan av den normala återloopnings-vägen:

advance_end (count under min):

  återloopningsväg:
    loopa tillbaka in i kroppen
    (håller dörren öppen för en verklig,
     icke-tom matchning i nästa
     iteration)

  if elem är empty-loopable:
    snabbavslutsväg:
      återställ detta djups räknare
      lämna gruppen via next,
      behandla återstående obligatoriska
      iterationer som tomma matchningar

De två vägarna spelar kompletterande roller. Återloopningen är det som fångar fallet där kroppen fortfarande har verkliga matchningar att producera senare — till exempel, i (A? B?){2,3} följt av data där A matchar endast på senare rader, är det återloopningen som låter den andra och tredje iterationen hitta icke-tomma matchningar. Snabbavslutet lämnar gruppen på en gång, förklarar "resten av de obligatoriska iterationerna är tomma" och låter matchningen lyckas med en noll-längds kropp. Kroppen, inte gruppens egen girighet, avgör ordningen: snabbavslutet går först exakt när kroppen föredrar den tomma matchningen (en motvillig kropp såsom (A?? B??)), och om den första vägen når FIN släpps den andra, så en mindre föredragen väg kan inte ersätta den föredragna matchningen. Dedupliceringskontrollen vid insättningstillfället förhindrar att någondera vägen genererar fler tillstånd än sin andel.

Utöver cykelvakten finns ytterligare ett uppstartstrick som disambiguerar noll-rad-utfall vid själva starten av en kontext. Kontextskapandesteget vid varje potentiell startrad kör en initial advance genom epsilonövergångar innan någon rad konsumeras, med en position en rad före den faktiska starten. Varje väg som når FIN-sentinelen genom enbart epsilonövergångar — utan att konsumera en rad — producerar därför en slutposition mindre än startpositionen; den negativa spann-koordinaten, kombinerad med huruvida FIN faktiskt nåddes, kodar skillnaden mellan en tom matchning (längd-0-matchning accepterad) och en omatchad start utan att behöva en separat flagga.

3.6 Hur tillståndsrymden förblir begränsad

Att hålla körtiden begränsad är inte resultatet av en enda optimering. Den är den ackumulerade effekten av en skiktad uppsättning beskärningsregler, där var och en fångar en annan orsak till tillståndsrymdtillväxt vid en annan punkt i per-rad-cykeln. Vissa avgörs vid kompileringstillfället och konsulteras endast vid körtid; andra aktiveras dynamiskt. Vissa dödar enskilda tillstånd; andra dödar hela kontexter. Avsnitten ovan introducerade var och en i sitt sammanhang; tabellen nedan samlar dem på en sida.

Misslyckat predikat Match
Variabeltillstånd vars DEFINE utvärderades till falskt på den aktuella raden — döda grenar.
Inline END-kedjeavanceringen Match
Variabler som har nått sin max-räknare och som annars skulle lämna tillståndet mitt i en iteration; avancerade genom gruppslut med fast längd så att absorption kan jämföra vid rätt punkt.
Kontextabsorption Absorb
Nyare kontexter vars varje tillstånd sitter på en jämförelsepunkt och täcks av en äldre kontexts absorberbara tillstånd vid samma element med en större eller lika stor räknare — se §2.5 för den begreppsmässiga regeln, §3.2 för kompileringstidsberättigandet, §3.5 för per-par-kontrollen.
Tillståndsdeduplicering Advance
Tillstånd nådda via olika DFS-grenar som hamnar vid samma position med samma räknare — endast det första (lexikalt tidigaste) överlever; senare ekvivalenter släpps tyst, vilket också är hur preferens upprätthålls (§2.4).
FIN-tidig terminering (inom kontext) Advance
Tillstånd som fortfarande väntar i DFS-kön när en gren når FIN — enligt lexikal ordning är alla återstående tillstånd mindre föredragna och kan kastas omedelbart.
Kandidatmatchningsbeskärning (mellan kontexter) Advance
Andra kontexter vars startrad ligger inom kandidatmatchningens omfång — kontexten som träffade FIN kan fortfarande söka efter en längre matchning (girig fallback), men under AFTER MATCH SKIP PAST LAST ROW kan ingen kontext inom kandidatens omfång längre producera en rapporterbar utdata, oavsett hur den sökningen slutar, och beskärs så snart Advance är klar med kontexten som registrerade kandidaten.
Cykelvakt Advance
Epsilonexpansioner som når END för en nollbar grupp som redan markerats inom samma DFS (markerat vid inträde via BEGIN, eller vid en tidigare ankomst) — skulle annars loopa för evigt; tillståndet lämnar gruppen där vid eller över den nedre gränsen, och fortsätter loopa under den.
Tomt-loop-snabbavslut Advance
Under den nedre gränsen för en nollbar grupp, en extra väg som lämnar gruppen med de återstående obligatoriska iterationerna förklarade tomma, ordnad mot återloopningen efter kroppens preferens.
Begränsad-ram-avskärning Match
Kontexter vars matchning har nått den användarspecificerade ramens övre gräns — tvingas till en miss så att de inte kan sträcka sig bortom den (§3.4).

Att läsa posterna efter deras fas-emblem följer en kontexts livstid: beskärning aktiveras vid varje rad genom de tre huvudfaserna (Match, Absorb, Advance). Att i stället läsa beskrivningarna grupperar reglerna efter vad de riktar sig mot: döda grenar, redundanta kontexter, ekvivalenta tillstånd, oändliga loopar och översträckning förbi användarpålagda gränser.

Ingen enskild regel räcker på egen hand. Tomt-loop-snabbavslutet ensamt skulle inte stoppa oändliga epsilonloopar; absorption ensamt skulle överkonsolidera när DEFINE refererar matchningsstart; deduplicering ensamt skulle inte ta bort redundanta kontexter, endast redundanta tillstånd. Körtiden förblir linjär i de fall som spelar roll — PATTERN (A+ B+ C+ D) på 100 000 rader, affischens panel ③-benchmark — endast för att varje skikt fångar det som skikten ovanför missar. Källkoden dokumenterar fall som skikten inte fångar: dedup håller isär tillstånd som skiljer sig endast i räknare över min, så (A{2,} B)+ C där C aldrig är sant håller Θ(n²) tillstånd vid toppen och skapar Θ(n³) av dem (37 s över 320 rader), och en följd av helt nollbara alternationer räknas upp väg för väg, så (A?|B?){30} tar över en halvtimme.

3.7 EXPLAIN-utdata

EXPLAIN ANALYZE på en fråga med RPR exponerar statistik på NFA-nivå som inte finns för vanliga fönsterfunktioner. I textformat emitteras de vid sidan av fönsteroperatorn, efter raden Pattern:, eventuella Nav Mark-rader (som vanlig EXPLAIN också visar) och raden Storage::

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (var och en endast när DEFINE använder
   navigation som matar 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)
  (andra NFA-raden endast när någon av
   räknarna är nollskild; en nollräknare
   skrivs ut utan sitt (len ...))

Icke-textformat emitterar varje räknare som en egen egenskap. Peak och total är direkt instrumentering av körtiden: hur många tillstånd som någonsin var aktiva samtidigt, hur många som skapades under frågans livstid och hur många som slogs bort av deduplicering; pruned räknar kontexter som misslyckades efter en enda rad. Matchningslängdshistogrammen separerar fyra utfall — lyckade matchningar, matchningsförsök som misslyckades efter mer än en rad (mismatched), absorberade kontexter och kontexter som frigjorts av AFTER MATCH SKIP PAST LAST ROW eftersom de startade inuti en registrerad matchning (skipped) — och att rapportera dem med min/max/avg gör prestationspatologier synliga med en blick: en frisk körning visar de flesta kontexter som antingen matchade eller absorberade, med små miss-längder.

De två Nav Mark-räknarna rapporterar tuplestore-bevarandebudgeten som §3.3 härleder från DEFINE. Lookback är den djupaste bakåträckvidden från den aktuella raden över PREV, LAST med valfri offset (inklusive standardvärdet 0) och de sammansatta formerna med inre LAST; Lookahead är den minsta framåträckvidden (negativ när den blickar före matchningsstarten) mätt från den äldsta aktiva kontextens matchningsstart, som FIRST och de sammansatta formerna med inre FIRST bidrar till.

Varje räknare skrivs ut som ett fast heltal när offset är en konstant, "runtime" när offset är ett icke-konstant uttryck som är känt endast per skanning, och — endast för Lookback — "retain all" när offset flödar över; en Lookahead som flödar över skrivs ut som "infinite". Varje rad emitteras endast när någon navigation i DEFINE matar den, och båda visas även under vanlig EXPLAIN: konstanta offsets fastställs vid executor-init, medan en offset som är känd först vid körtid (till exempel en parameter i en generisk plan) skrivs ut som "runtime" där och som sitt upplösta heltal under EXPLAIN ANALYZE.

Tillsammans gör dessa räknare det möjligt att felsöka RPR-prestanda utan att koppla gdb till backend.

Utöver räknarna skriver EXPLAIN ut en Pattern:-rad byggd från den kompilerade elementarrayen, så den visar mönstret efter kompileringstidsomskrivningarna (PATTERN (A A) förklaras som a{2}) och bär absorptionsmarkörerna # (jämförelsepunkt) och ~ (absorberbar region); DEFINE och AFTER MATCH SKIP-alternativet visas inte. Att återge satserna som de skrivits, inklusive motvilliga kvantifierare, gruppupprepning och hoppalternativet, är uppgiften för pg_get_viewdef(), som gör viss ansträngning för att göra denna rundresa stabil så att pg_dump och pg_upgrade kan bevara RPR-objekt utan semantisk drift — regressionssviten under rpr_explain verifierar detta fall för fall (se §4).

§4. Tester — täckningskarta

Patchen levereras med fem regressionssviter som tillsammans tränar varje skikt som beskrivs i §3 — ungefär 22 000 rader SQL, där varje svit fokuserar på olika hänsyn. Uppdelningen är medveten: att hålla parserhänsyn, körtidskorrekthet, planerareinteraktioner och utdataformatering i separata filer gör fel lättare att lokalisera och förhindrar att en orelaterad förändring i ett skikt oavsiktligt ogiltigförklarar tester i ett annat. De fem sviterna är:

rpr
WINDOW-satsintegration — realistiska fönsterscenarier på syntetisk aktiedata (V-form, W-form, efterföljande uppgångar, vändningar), plus navigationssemantik och fel för DEFINE-begränsningar.
rpr_base
Parserskiktet — nyckelordsacceptans, syntaxformer, kvantifierare, navigeringsparsning, felmeddelanden och stabilitet i pg_dump/pg_upgrade-rundresa; plus ett planerarskikt — mönsteroptimering, absorptionsflaggor, optimerings-fallback, planerarintegration.
rpr_nfa
NFA-körtid — trefasloopen, absorption i varje absorberbar form och gränsfall i kontextens livscykel.
rpr_explain
Utdataformatering — NFA-statistik, mönsterdeparse, identifierarcitering, formatstabilitet vid omladdning.
rpr_integration
Planerareinteraktioner — skyddsvallar som hindrar orelaterade fönsteroptimeringar från att korrumpera RPR-semantik.

4.1 rpr — scenarier från ände till ände

Scenariosviten är testuppsättningens publika ansikte: den använder en syntetisk aktiekurs-datamängd på ungefär 1 600 rader och kör realistiska frågor mot den — V-form-återhämtning, W-form (dubbel botten), efterföljande uppgångar och fall, vändningsmönster, partitioner med flera symboler. Dessa scenarier är de enda tester vars indata och utdata läses som frågor som en användare faktiskt kan tänkas skriva; resten av filen är, liksom de andra sviterna, reduktiv — PREV/NEXT-nästling och fel för icke-konstanta offsets, DEFINE-referensregler och semantik för navigationsoffsets.

Eftersom dessa frågor kombinerar varje skikt (parser, planerare, executor, EXPLAIN) talar ett enskilt fel i rpr sällan om var felet ligger. De fyra sviterna som följer är bisektionen: ett fel i rpr plus en passerande rpr_base utesluter parsern; plus en passerande rpr_nfa snävar in det till scenariospecifika dataformer; plus en passerande rpr_integration utesluter planerareinblandning; och eventuell deparse-drift dyker upp i rpr_explain.

4.2 rpr_base — parserytan

Bas-sviten är den största, och den är störst av en anledning: den är ansvarig för att bevisa att varje laglig syntaxbit i §1.2 faktiskt parsas, varje olaglig bit i §1.3 avvisas med ett användbart fel och varje accepterad form överlever en serialiseringsrundresa. Huvuddelen är formad som små fokuserade utdrag — en per syntaktisk funktion — snarare än långa realistiska frågor, eftersom målet är täckning snarare än scenariorealism. En andra del, planerarskiktet, täcker mönsteroptimering, visning och analys av absorptionsflaggor, optimerings-fallback och planerarintegration (underfrågor, joins, mängdoperationer, sortering och gruppering).

Serialiseringstesterna förtjänar särskild uppmärksamhet. RPR-objekt (vyer, materialiserade vyer, pg_dump-utdata) måste rundresa genom katalogrepresentationen utan semantisk drift, inklusive finesser som motvillig-flaggan på en kvantifierare eller den exakta formen av ett sammansatt navigationsuttryck. En liten uppsättning serialiseringsspecifika objekt (vyerna rpr_serial_v* och deras stödjande tabeller) lämnas medvetet på plats vid körningens slut, så att den omgivande regressionsinfrastrukturen kan plocka upp dem och köra pg_dump och pg_upgrade mot dem. Resten av testställningen släpps som vanligt. Defekter såsom en motvillig-flagga som tappas mellan deparse och åter-parse dyker upp endast när rundresan körs från ände till ände.

4.3 rpr_nfa — körtidsmotorn

Detta är sviten som tränar varje mekanism som beskrivs i §3.5 och §3.6. Dess tester följer ett konsekvent mönster: inline VALUES-rader som bär en array av variabelnamn som deklarerar vilka DEFINE-variabler som matchar vid varje rad, parad med ett mönster som undersöker ett specifikt körtidsbeteende. Array-idiomet kopplar bort körtidstestet från DEFINE-utvärderingsmaskineriet — det som testas är "givet att dessa variabler matchar här, producerar NFA-loopen det förväntade matchningsomfånget?" snarare än "beräknar DEFINE-uttrycksutvärderaren dessa booleaner korrekt?" DEFINE-utvärderaren testas på annat håll (rpr_base för parsning, rpr för beteende från ände till ände).

En typisk testfixtur ser ut så här — en kolumn av variabelnamnsarrayer där varje post säger vilka DEFINE-variabler som aktiveras på den raden, och ett mönster vars DEFINE-satser testar för dessa namn direkt:

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

Att läsa array-kolumnen nedåt är att läsa testscenariot direkt. Raderna 2 och 3 bär båda namnen — A och B aktiveras båda där, så NFA:n har ett verkligt val om var man ska byta från A-benet till B-benet. Den förväntade matchningen (A vid raderna 1–3 följt av B vid rad 4, under standardens giriga preferens) är fastställd av enbart dessa flaggor, utan någon uttrycksutvärdering av betydelse här — = ANY är bara det triviala skiktet som exponerar array-kolumnen för DEFINE, inte vad testet tränar. Att skriva samma scenario med ett numeriskt predikat (price > PREV(price) och liknande) skulle blanda NFA-testet med predikatutvärderarens beteende; array-idiomet håller de två renligt åtskilda, och ett fel här pekar direkt på NFA-loopen.

Absorptionstäckningen är särskilt grundlig, eftersom absorption är den optimering som med störst sannolikhet tyst producerar felaktiga svar om den aktiveras när den inte ska. Tester täcker varje form från fallanalysen i §3.2:

Utöver absorption täcker sviten kontextens livscykel: överlappande kontexter under AFTER MATCH SKIP TO NEXT ROW, städning av misslyckade kontexter mitt i strömmen, partitionsslut-färdigställande av ofullständiga kontexter, och kontexter som påträffats efter att en kandidatmatchning redan registrerats i huvudkontexten. Var och en av dessa mappar mot en specifik beskärningsregel i §3.6, och testerna är skrivna för att misslyckas högljutt om regeln avlossas felaktigt (antingen genom att lämna redundanta kontexter vid liv eller genom att döda en kontext som skulle ha producerat utdata).

4.4 rpr_explain — utdatastabilitet

EXPLAIN-utdata är del av det användarvända kontraktet — tredjepartsverktyg (övervakningsdashboards, loggskrapor) parsar det, och ändringar som ser kosmetiska ut kan bryta dem. Sviten rpr_explain verifierar tre saker:

Liksom rpr_base lämnar denna svit medvetet sina objekt på plats vid körningens slut så att pg_dump- och pg_upgrade-täckningen sträcker sig till explain-sidans artefakter också.

4.5 rpr_integration — planerareinteraktioner

PostgreSQL:s planerare har många optimeringar som arbetar på fönsterfrågor — ramkanonisering, kör-villkorspushdown, identisk-fönster-deduplicering, oanvänd-utdataprojektion, omvända övergångar för rörliga aggregat — och var och en av dem designades utan RPR i åtanke. De flesta är osäkra att tillämpa när ett fönster har en PATTERN-sats: ramen är del av matchningskontraktet, det matchade utdatat är inte längre monotont på något uppenbart sätt, och två fönster med samma spec men olika DEFINE producerar genuint olika resultat. Integrationssviten verifierar hur var och en av dessa optimeringar behandlar RPR-fönster — de flesta måste inaktiveras eller kringgås:

Ramkanonisering
Planeraren skriver normalt om ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING till ROWS UNBOUNDED PRECEDING för ramoberoende fönsterfunktioner såsom row_number, rank och ntile. RPR:s ram är matchningsomfånget, inte ett aggregeringsfönster, och måste förbli ordagrann.
Kör-villkorspushdown
Ett monotont WHERE-filter på en fönsterfunktions utdata kan normalt skjutas in i fönsteroperatorn som ett stoppvillkor. För RPR skulle detta avsluta mönstermatchning för tidigt och möjligen kapa matchningar mitt under utvidgning.
Fönsterdeduplicering (RPR vs icke-RPR)
Två fönster med identisk ORDER BY och ram skulle normalt slås samman till ett. Ett RPR-fönster och ett icke-RPR-fönster kan aldrig dela tillstånd eftersom RPR-sidan bär matchningsresultat.
Fönsterdeduplicering (olika DEFINE eller SKIP)
Två RPR-fönster med samma PATTERN men olika DEFINE-satser eller ett annat AFTER MATCH SKIP producerar olika matchningar och måste förbli åtskilda, även om deras strukturella form är identisk.
Oanvänd-utdataprojektion
Denna får tillämpas: när den omgivande frågan aldrig läser fönstrets utdata blir fönsterfunktionen NULL och dess WindowAgg tas bort, vilket lämnar radantalet oförändrat. Testerna kontrollerar att de kolumner som DEFINE läser fortfarande når WindowAgg när den står kvar, och att fönstret behålls när dess värde läses.
Omvända övergångar för rörliga aggregat
Fönsteraggregat med en omvänd övergångsfunktion kan normalt utvärderas inkrementellt när ramen rör sig. RPR:s reducerade ram är inte ett glidande fönster; den omvända övergångsvägen skulle producera felaktiga resultat.

Ytterligare fall kontrollerar att kostnadsuppskattningen tar hänsyn till DEFINE, att en underfråga som innehåller ett RPR-fönster inte plattas ut, att DEFINE-uttryck inte läcker in i en övre WindowAgg och att LIMIT stannar ovanför WindowAgg; en andra grupp kör RPR tillsammans med CTE:er, joins, mängdoperationer, förberedda satser, partitionerade tabeller och liknande konstruktioner. De flesta skyddade fall följer samma form: en baslinje som utlöser optimeringen (vanligtvis en icke-RPR-fråga, kontrollerad i EXPLAIN), sedan en RPR-fråga av strukturellt liknande form där optimeringen inte tillämpas — för dedup-fallet med DEFINE/SKIP är baslinjen två identiska RPR-fönster, och fallet med omvänd övergång kontrollerar förbikopplingen med ett loggande aggregat i stället för EXPLAIN. De två halvorna tillsammans bevisar att skyddet i planeraren utför verkligt arbete och inte godkänner varje fråga utan verklig verifiering.

Denna svit är också skälet till att §3.4 är kort. "Matchningsgränser"-mekanismerna — reducerad ram, SKIP, INITIAL, begränsad-ram-avskärning — testas operationellt på annat håll; det rpr_integration verifierar är att inget annat optimerarsteg manipulerar dem på vägen genom. En passerande rpr_integration är det som låter resten av sviterna lita på att deras indata når executor oantastat.