Row Pattern Recognition Diepgaande Verkenning

§1. De Standaard, de Subset en de Openstaande Vragen

1.1 Reikwijdte van de standaard

Row Pattern Recognition werd in SQL geïntroduceerd door ISO/IEC 9075-2:2016 en wordt beschreven in het begeleidende document ISO/IEC 19075-5:2021 (Deel 5, "Row Pattern Recognition").

De standaard definieert twee oppervlakken voor dezelfde onderliggende machinerie. Feature R010 plaatst een MATCH_RECOGNIZE-clausule in de FROM-lijst om een afgeleide tabel te produceren; Feature R020 integreert dezelfde patroonlogica in een WINDOW-specificatie om uitvoer van een window-functie te leveren. De twee oppervlakken delen het merendeel van hun syntaxis en al hun semantiek, maar zijn functioneel onderscheiden ingangen — een database kan een van beide of beide implementeren.

De patchreeks die hier wordt besproken implementeert een subset van uitsluitend R020; de tabelclausulevorm valt bewust buiten de scope.

Het R020-oppervlak is klein maar expressief. Een query koppelt een patroon aan een window door drie clausules toe te voegen aan de window-specificatie: PATTERN beschrijft een reguliere expressie over benoemde patroonvariabelen, DEFINE levert het Booleaanse predicaat dat elke variabele identificeert, en AFTER MATCH SKIP bepaalt hoe opeenvolgende matches binnen de partitie worden gepositioneerd.

Optionele MEASURES, SUBSET, INITIAL/SEEK, en de hulpfunctie CLASSIFIER() maken de feature compleet. (De MATCH_NUMBER()-functie uit de standaard behoort uitsluitend tot het R010-oppervlak — 19075-5 §6.3.3 (6) sluit deze expliciet uit van R020.)

De patch dekt voldoende van dit vocabulaire om niet-triviale queries te laten werken, maar stopt voor diverse constructies waarvan de implementatie afhankelijk is van infrastructuur die nog niet is gebouwd.

De rest van deze sectie verdeelt het vocabulaire van de standaard in wat de patch reeds ondersteunt en wat bewust voor later wordt uitgesteld. De onderstaande lijsten weerspiegelen de huidige stand van de patchreeks.

1.2 Geïmplementeerde features

Het geïmplementeerde vocabulaire is voldoende om de canonieke V-vorm-, W-vorm- en omkeringspatronen uit te drukken die row pattern recognition in de eerste plaats motiveren. Het dekt ook elke standaard kwantor — inclusief alle zeven reluctante varianten *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — en de vier navigatieprimitieven die DEFINE-condities nodig hebben om aangrenzende rijen te vergelijken.

PATTERN-clausule

Definieert het rijpatroon binnen een window-specificatie.

Regex: + * ? |

Standaard kwantoren en alternatie.

Regex: ( ) groepering

Subpatronen tussen haakjes.

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

Begrensde herhalingsaantallen.

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

Alle zeven reluctante (niet-gulzige) varianten die de standaard definieert (uitgesloten van de absorptie-optimalisatie).

DEFINE-clausule

Booleaanse condities die elke patroonvariabele identificeren.

Universele rijpatroonvariabele

Niet-gekwalificeerde kolomverwijzingen in DEFINE (bijv. kale Price) worden naar de huidige rij herleid, volgens 19075-5 §4.10/§4.16.

PREV, NEXT (met offset)

Bereik n rijen voor/na de huidige rij (standaard 1); het binnenste argument is een willekeurige waarde-expressie die op de genavigeerde rij wordt geëvalueerd.

FIRST, LAST (met offset)

Bereik een matchrelatieve rij; FIRST(expr, n) richt zich op de rij n na het matchbegin, LAST(expr, n) op de rij n vóór de meest recente matchrij.

Samengestelde navigatie (vier vormen)

Buitenste PREV/NEXT-stap gelaagd op een binnenste FIRST/LAST: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — zowel de binnenste als de buitenste stap accepteert een eigen offset.

INITIAL

Patroonmatches moeten beginnen bij de huidige rij (standaard).

AFTER MATCH SKIP PAST LAST ROW

Standaard skip-modus; komt in aanmerking voor contextabsorptie.

AFTER MATCH SKIP TO NEXT ROW

Staat overlappende matches toe; schakelt absorptie uit.

1.3 Niet geïmplementeerd

De features die niet zijn geïmplementeerd vallen in drie globale groeperingen uiteen. De eerste — en veruit de grootste — is de familie van constructies rond MEASURES: de MEASURES-clausule zelf, SUBSET, CLASSIFIER(), patroongekwalificeerde kolomverwijzingen zoals B.price, en patroongekwalificeerde navigatie zoals LAST(B.price) of PREV(B.price).

Dit zijn niet zozeer onafhankelijke leemtes als wel verschillende perspectieven op één ontbrekend onderdeel: de executor zou een per-match-historie moeten bijhouden — een registratie, voor elke rij in de match, van welke patroonvariabele eraan is toegewezen — en geen van deze constructies heeft zonder dit een zinvolle definitie. CLASSIFIER() leest de variabelenaam uit die registratie; B.price leest de prijskolom van de rijen waarvan het registratiegegeven B aanduidt; LAST(B.price) doorloopt dezelfde set rijen en kiest de laatste; SUBSET U = (A, B) definieert een virtuele variabele die over beide buckets aggregeert; en MEASURES evalueert uitdrukkingen als AVG(U.Price) precies via die aggregatie.

De huidige executor evalueert DEFINE-predicaten rij voor rij, maar registreert de resulterende variabeletoewijzingen nergens — er is achteraf niets te bevragen. Het bouwen van de historie-infrastructuur is daarom de voorwaarde voor de gehele groep; de individuele features volgen als kleine projecties zodra de registraties bestaan.

De tweede groepering betreft alternatieve skip-doelen: AFTER MATCH SKIP TO label, AFTER MATCH SKIP TO FIRST var, en AFTER MATCH SKIP TO LAST var. Ook deze zijn afhankelijk van match-historie, aangezien de executor in staat moet zijn een specifieke gelabelde rij binnen de meest recente match aan te wijzen.

De overige items vormen een heterogene staart: het sleutelwoord SEEK (het alternatief voor INITIAL), het lege patroon (), de uitsluitingsvorm {- … -}, en de volgorde-onafhankelijke PERMUTE-operator.

MEASURES

Benoemde per-match-uitvoer-uitdrukkingen, bijv. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; in R020 ontsloten via OVER zoals een window-functie. Accepteert de sleutelwoorden FINAL / RUNNING (19075-5 §5.4), die in R020 samenvallen tot dezelfde waarde, aangezien measures altijd worden geëvalueerd op de laatste rij van de match (19075-5 §6.9 (3)).

SUBSET

Benoemde verenigingen van patroonvariabelen, bijv. SUBSET U = (A, B, C). Bruikbaar overal waar naar een patroonvariabele kan worden verwezen — MEASURES, patroongekwalificeerde refs in DEFINE, CLASSIFIER(U) — die alle match-historie vereisen.

CLASSIFIER()

Geeft terug als welke patroonvariabele een bepaalde rij is gematcht. Gedefinieerd voor zowel DEFINE als MEASURES (19075-5 §5.9); het antwoord op elke rij is de variabelenaam die in de match-historie voor die rij is geregistreerd.

Patroongekwalificeerde kolomverwijzing

Een onversierde B.price in DEFINE of MEASURES — de waarde van de kolom uit de rij die als de benoemde variabele is toegewezen.

Patroongekwalificeerde navigatie

Beperk navigatie tot rijen die als een benoemde variabele zijn gematcht, bijv. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

Match mag overal in het window beginnen (vs. INITIAL).

AFTER MATCH SKIP TO label

Skip naar een gelabelde rij.

AFTER MATCH SKIP TO FIRST var

Skip naar de eerste rij die als de benoemde variabele is gematcht.

AFTER MATCH SKIP TO LAST var

Skip naar de laatste rij die als de benoemde variabele is gematcht.

Regex: {- -}

Uitsluiting — verwijdert gematchte rijen uit de per-match-uitvoer.

Regex: ()

Leeg patroon — matcht de lege reeks.

PERMUTE(...)

Volgorde-onafhankelijke matching over opgesomde variabelen.

Aggregaatfuncties in DEFINE

Aggregaten zoals SUM, AVG, COUNT zijn niet toegestaan in DEFINE-predicaten. De standaard staat ze toe als running-aggregaten over de gedeeltelijke match (per-rij-evaluatie tegen rijen die reeds aan een variabele zijn toegewezen), wat afhankelijk is van dezelfde per-match-historie die MEASURES/CLASSIFIER() vereisen.

Vier aanvullende punten zijn hier het vermelden waard, omdat ze gemakkelijk voor weglatingen kunnen worden aangezien.

Het eerste is dat de patroonankers ^ en $ door de standaard zelf niet zijn toegestaan met RPR in de WINDOW-clausule (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; met de onderliggende definitie in 19075-5 §4.14.1); hun afwezigheid is conformiteit, geen leemte.

Het tweede is dat MATCH_NUMBER() eveneens door de standaard wordt uitgesloten van R020 (19075-5 §6.3.3 (6) en 19075-5 §6.9 (1)) — het maakt uitsluitend deel uit van het R010-oppervlak, en de afwezigheid hier is opnieuw conformiteit en niet een ontbrekende feature.

Het derde is een reeks structurele verboden die de standaard oplegt aan R020 (19075-5 §6.17): row pattern recognition kan niet worden genest binnen een andere row pattern recognition; MEASURES en DEFINE mogen geen externe verwijzingen bevatten; subquery's binnen MEASURES of DEFINE mogen niet naar rijpatroonvariabelen verwijzen; en RPR mag niet binnen een recursieve query worden gebruikt.

Het vierde is dat MATCH_RECOGNIZE zelf — Feature R010, het tabelclausuleoppervlak van dezelfde machinerie — buiten de scope van deze patch valt. Of PostgreSQL uiteindelijk R010 toevoegt is een vraag voor een toekomstige reeks, niet een maatstaf voor deze.

§2. Voorbeelden — Hoe Het Daadwerkelijk Werkt

De voorbeelden in deze sectie bouwen incrementeel op. We beginnen met de conceptuele reden waarom row-pattern matching wezenlijk verschilt van string-pattern matching, introduceren vervolgens de vier navigatiefuncties die DEFINE-condities interessant maken, en lopen ten slotte drie end-to-end-traces door: een enkele match (NFA-beweging), contextabsorptie in het eenvoudige geval, en het geval waarin absorptie onveilig wordt.

Het interne mechanisme dat navigatie goedkoop maakt — de 1-slot tuple swap — behoort tot het ontwerp van de executor en wordt in de volgende sectie behandeld, niet hier.

2.1 Waarom rijpatronen verschillen van tekstpatronen

Een reguliere tekstexpressie matcht een stroom karakters, en op elke positie is er precies één symbool om te overwegen. De runtimevraag — "is het huidige symbool gelijk aan 'A'?" — heeft één enkel ja/nee-antwoord. Backtrackende automaten benutten dit: per karakter overleeft hooguit één tak, en de kosten van ambiguïteit worden betaald door de invoer opnieuw te lezen.

Een rijpatroon is op een fundamentele manier anders. Een rij is geen enkel symbool; het is een tuple van kolommen die wordt geëvalueerd tegen een set Booleaanse predicaten, de DEFINE-condities. Twee predicaten kunnen tegelijkertijd waar zijn op dezelfde rij, en niets in de standaard zegt dat ze elkaar wederzijds moeten uitsluiten. Beschouw:

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

Een rij met price = 150, volume = 2000 voldoet aan zowel A als B, maar niet aan C. De pattern matcher kan dit niet tot één enkele toestand reduceren — twee patroonvariabelen zijn actief, en elk patroonelement dat een van beide benoemt kan voortgaan. De NFA moet daarom meerdere gelijktijdige toestanden per partitierij bijhouden, niet één.

Deze ene observatie drijft de rest van de architectuur. De uitvoeringstoestand is een lijst van contexten, elke context is een lijst van toestanden, en bij elke rij vraagt de runtime aan elke toestand: "gegeven de variabelen die hier waar zijn, waarheen kan ik?" De vorken die hieruit ontstaan zijn de reden dat de runtime meerdere snoeilagen nodig heeft — toestanddeduplicatie binnen een context, absorptie over contexten heen, en de overige regels behandeld in §3.6 — zonder welke het aantal actieve toestanden en contexten met de partitie meegroeit en patroonmatching superlineair wordt.

2.2 Navigatiefuncties

DEFINE-condities die uitsluitend naar de huidige rij verwijzen zijn beperkt; vrijwel elk interessant patroon moet de huidige rij vergelijken met buurrijen of met rijen die al eerder in de match zijn geaccepteerd. De standaard voorziet hiervoor in vier navigatiefuncties, en de patch implementeert ze alle.

PREV(expr [, n])

De rij n rijen vóór de huidige rij (standaard n = 1). Gebruikt voor vergelijkingen "vandaag vs. gisteren".

NEXT(expr [, n])

De rij n rijen na de huidige rij. Voorwaartse look-ahead; ongebruikelijk in window-vorm omdat het window monotoon is.

FIRST(expr [, n])

De n-de gematchte rij van de huidige match, geteld vanaf het begin. "Vergelijk met de rij die deze match startte."

LAST(expr [, n])

De n-de meest recent gematchte rij. "Vergelijk met de meest recent gematchte rij."

De vier primitieven kunnen worden samengesteld: PREV en NEXT kunnen een FIRST- of LAST-aanroep omsluiten, wat vier samengestelde vormen oplevert met als semantiek "ga naar een matchrelatieve rij, en stap dan een vaste afstand daarvan vandaan." Dit stelt een DEFINE-expressie in staat om bijvoorbeeld de rij onmiddellijk voorafgaand aan het matchbegin te lezen.

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

Stap m rijen terug vanaf de n-de rij van de match (standaard m = 1). "Wat was de waarde vlak voordat deze match begon?"

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

Stap m rijen vooruit vanaf de n-de rij van de match. Reikt verder in de match zonder afhankelijk te zijn van de huidige rij.

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

Stap m rijen terug vanaf de n-de meest recent gematchte rij. "Vergelijk met een rij kort vóór de meest recente match."

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

Stap m rijen vooruit vanaf de n-de meest recent gematchte rij.

Twee praktische punten verdienen hier vermelding. Ten eerste kan navigatie worden samengesteld: PREV(FIRST(price)) leest de rij onmiddellijk voorafgaand aan het matchbegin, en de patch ondersteunt dit. Ten tweede heeft navigatie gevolgen voor de optimalisaties van de executor. PREV en NEXT zijn relatief ten opzichte van de huidige rij en zijn altijd veilig; FIRST en offset-varianten van LAST zijn relatief ten opzichte van de matchgrenzen, wat in wisselwerking staat met contextabsorptie en de planner dwingt sommige contexten in leven te houden die anders zouden worden verworpen. Het mechanisme achter die wisselwerking is het onderwerp van §2.6.

2.3 Uitgewerkt voorbeeld 1 — NFA-beweging

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

Het patroon vlakt af tot vier elementen:

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

Voor de prijsreeks 100, 110, 120, 115, 108, 130:

Het kernpunt: op rij 3 voldoet de rij aan zowel START (altijd waar) als DOWN, maar de enige toestand die rij 2 overleefde bevindt zich op de DOWN-exittak, dus uitsluitend de UP → DOWN-transitie wordt genomen. Het multi-toestand-karakter van §2.1 is zichtbaar als fan-out bij elke UP-match (de toestand kan op UP+ blijven of voortgaan naar DOWN+). Gulzige voorkeur is "loop opnieuw vóór exit", dus bij voldoende data zouden de loopende takken de match verder uitbreiden; hier sterft de loopende DOWN bij rij 5 (130 ≮ 108), en de eerdere FIN-kandidaat (rijen 0–4) — geproduceerd toen DOWN bij rij 4 verliet — wordt als de match gefinaliseerd.

Het resultaat van de query volgt direct uit deze trace. Onder RPR-semantiek worden de window-functies first_value(price) en last_value(price) uitsluitend geëvalueerd op de rij die de match startte — elke andere rij in de match levert NULL op voor deze window-functies, aangezien het gereduceerde frame leeg is. De uitvoer voor onze data ziet er daarom uit zoals de tabel die de poster in het paneel rechtsboven toont:

Rij 0 is het matchbegin, dus haar frame beslaat rijen 0–4 en de window-functies rapporteren de openingsprijs van de V-vorm ($100) en de bodemprijs ($108). Rijen 1–4 vallen binnen de match maar zijn niet het begin, dus ontvangen NULL. Rij 5 (prijs $130) ligt buiten enige match en ontvangt eveneens NULL.

2.4 Uitgewerkt voorbeeld 2 — Alternatie en lexicale volgorde

De vorm (A | B) geeft de matcher een keuze: op elke rij worden de twee alternatieven onafhankelijk getest, en een willekeurig aantal ervan kan matchen. Dit is waar het multi-toestand-karakter van §2.1 zichtbaar wordt binnen één enkele context — niet over contexten heen (dat is absorptie), maar langs parallelle takken die de executor in pas verkent.

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

Stel een rij voor waarop de prijs zowel is gestegen als $100 heeft overschreden — zowel UP als HIGH zijn waar. Elk alternatief brengt zijn eigen toestand voort: één die over de UP-tak loopt, één over de HIGH-tak. Ze gaan parallel verder totdat DONE ze beslist.

Beide takken produceren een match van dezelfde lengte over dezelfde rijen, waardoor de matcher achterblijft met twee kandidaatspaden — één met label UP, DONE en één met label HIGH, DONE. De standaard beslecht dit op basis van lexicale volgorde: van de alternatieven geschreven in (UP | HIGH) wint diegene die als eerste is geschreven, ongeacht de matchlengte. Omdat UP vóór HIGH staat, is het overlevende pad UP, DONE.

Lexicale volgorde is wat CLASSIFIER() welgedefinieerd maakt zodra deze uiteindelijk wordt geïmplementeerd — het stelt de runtime in staat de gebruiker te vertellen "deze rij matchte UP, niet HIGH", zelfs wanneer beide predicaten waar waren. Lexicale volgorde is de primaire regel voor alternatie: een lexicaal eerdere tak wint van een lexicaal latere, zelfs als de lexicaal latere tak een langere match zou opleveren, en een lexicaal latere (mogelijk kortere) tak kan nog steeds winnen als elke lexicaal eerdere tak sterft voordat FIN wordt bereikt. Gulzige lengte wordt beslist binnen één enkele kwantor — gegeven twee voltooiingen van dezelfde alternatietak, geeft de gulzige kwantor de voorkeur aan meer iteraties.

2.5 Uitgewerkt voorbeeld 3 — Contextabsorptie (zelfde lot)

Het eenvoudigste patroon dat absorptie vertoont is PATTERN (A+) met DEFINE A AS TRUE. Elke rij matcht A, en de standaard vereist dat de matcher elke rij als mogelijk matchbegin beschouwt. Naïef betekent dit N contexten voor een partitie van N rijen. Neem een partitie van vijf rijen (willekeurige data — het predicaat is constant waar):

Het geheugen groeit van O(n) naar O(1). De absorptieregel die de verwerping rechtvaardigt is eenvoudig wanneer de kwantor onbegrensd is:

Het paneel linksonder van de poster ("① Context Absorption") is precies deze regel gevisualiseerd over vijf rijen.

Een subtiel maar belangrijk punt schuilt in de regel: de verwerping is veilig omdat het predicaat A AS TRUE op elke rij dezelfde waarde oplevert, ongeacht welke context het vraagt. Hetzelfde geldt voor elk predicaat dat uitsluitend naar de huidige rij of een vaste offset daarvan verwijst — inclusief PREV. Het volgende voorbeeld schakelt over op een concrete week van prijzen, met een PREV-gebaseerd predicaat, en §2.6 zal precies diezelfde week hergebruiken om de symmetrie tussen veilige en onveilige absorptie helder te maken:

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

Neem de handelsweek $100, $108, $112, $116, $110 van maandag tot en met vrijdag — vier stijgingen gevolgd door een plotselinge daling. Stel dat C1 op dinsdag start (de eerste dag waarop RISE matcht: $108 > $100), en de executor speculatief ook C2 volgt vanaf woensdag. De RISE-conditie van elke rij vergelijkt de prijs van die rij met haar onmiddellijke voorganger — een partitieniveau-feit, geen contextniveau-feit — dus de twee contexten worden gedwongen dezelfde Booleaanse waarde te berekenen op elke rij die ze delen:

Het verhaal breekt op het moment dat het predicaat begint af te hangen van de eigen grenzen van elke context — en daarover gaat §2.6.

2.6 Uitgewerkt voorbeeld 4 — Wanneer absorptie onveilig wordt

Stel dat een analist opeenvolgende handelsdagen wil vinden waarop een aandeel binnen tien dollar bleef van de dag waarop de reeks startte — een soort consolidatievenster. Het patroon en de DEFINE zien er als volgt uit:

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

De conditie vergelijkt nu de prijs van de huidige rij met de prijs aan het begin van de huidige reeks. Twee reeksen die op verschillende dagen zijn gestart hebben verschillende FIRST(price)-waarden, dus twee toestanden bij hetzelfde patroonelement en dezelfde teller zijn niet langer uitwisselbaar: hun toekomsten zijn afhankelijk van de grens die absorptie op het punt stond te verwerpen.

Neem precies dezelfde handelsweek als in §2.5 — $100, $108, $112, $116, $110 van maandag tot en met vrijdag. De runtime houdt opnieuw twee kandidaatreeksen tegelijk in leven: C1 startte op maandag, C2 startte op dinsdag (elke rij is onder STABLE+ een potentieel reeksbegin).

Onder absorptie zou C2 op dinsdag in C1 zijn samengevoegd — de samengevoegde context behoudt slechts één plafond, dus de eigen kijk van C2 (plafond $118, de vierdaagse reeks die pas op zaterdag eindigt) is niet meer uit de interne toestand te herstellen. C2 moet in leven blijven omdat het een onafhankelijke matchkandidaat is die de runtime mogelijk nog nodig heeft: zodra de match van C1 op woensdag eindigt, moet de volgende poging verdergaan vanaf een nog lopende C2 in plaats van helemaal opnieuw te beginnen. Wanneer een DEFINE-predicaat matchstart-afhankelijkheid bevat, schakelt de planner daarom absorptie preventief uit.

(Wanneer de match van de voorste context wel slaagt, worden contexten die binnen haar geaccepteerde bereik zijn gestart — onder de standaard AFTER MATCH SKIP PAST LAST ROW — simpelweg verworpen; ze worden alleen in leven gehouden zodat de runtime ergens op kan terugvallen mocht de voorste match falen.)

De afhankelijkheidstabel in het paneel rechtsonder van de poster ("② Navigation") vat samen welke navigatievormen matchstart-afhankelijkheid creëren:

De twee voorbeelden in §2.5 en §2.6 reduceren tot één enkele regel. Zelfde lot is wat absorptie veilig maakt: als elke context bij hetzelfde patroonelement op elk toekomstig predicaat hetzelfde antwoord zal berekenen, hoeft slechts de oudste behouden te blijven. Verschillende lotsbestemmingen maken absorptie onveilig: zodra predicaten zich vertakken op context-private toestand — wat precies is wat FIRST en offsetdragende LAST doen — vertegenwoordigt elke actieve context een toekomst die geen enkele andere context kan herstellen, en het verwerpen van een ervan riskeert een verkeerd antwoord.

De planner detecteert dit onderscheid bij compilatie en beslist per context of absorptie van toepassing is. Dit is ook waarom de benchmark op de poster in paneel ③ zowel in het succes- als in het faalgeval lineair blijft: wanneer absorptie veilig is reduceert de runtime contexten, en wanneer het dat niet is, accepteert de planner de multi-contextkosten in plaats van een verkeerd antwoord te riskeren.

De benchmarkcijfers op de poster zijn hetzelfde algoritme dat zich op schaal afspeelt. Op het succespatroon (A+ B+ C+ D) schalen zowel PostgreSQL als Trino O(n) zodra een match is bevestigd, en de voorsprong van PostgreSQL — ruwweg 16× tot 33× — is voornamelijk de JVM-kloof.

Op het faalpatroon (A+ B+ C+ E) heeft Trino geen absorptie en degradeert tot O(n²) bij het najagen van elke potentiële matchstart; bij 100.000 rijen duurt het meer dan vijf uur, terwijl PostgreSQL nog steeds in 92 ms klaar is, een versnelling van circa 217.000×.

Die kloof is geen technische verfraaiing — het is precies het zelfde-lot/verschillend-lot-onderscheid uit §2.5 en §2.6, toegepast op elke rij van elke potentiële matchstart in de partitie.

2.7 Uitgewerkt voorbeeld 5 — Wanneer SKIP absorptie uitschakelt

Het vorige voorbeeld brak absorptie aan de data-zijde: FIRST in DEFINE zorgde dat elke context predicaten anders evalueerde. Absorptie kan ook breken aan de uitvoer-zijde, en de AFTER MATCH SKIP-clausule is wat dit bepaalt.

Beschouw het patroon PATTERN (A+) met DEFINE A AS TRUE over vijf rijen die alle A matchen. Onder de standaard AFTER MATCH SKIP PAST LAST ROW vindt de matcher de langste match die op de vroegste rij begint en springt vervolgens daaroverheen; elke context die binnen die match is gestart wordt impliciet als overbodig verworpen — precies de situatie waarvoor absorptie is ontworpen. De uitvoer is één enkele match, rijen 0–4, en de runtime heeft slechts één actieve context nodig.

Schakel de skip-modus over naar AFTER MATCH SKIP TO NEXT ROW en het contract verandert:

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

Nu moet elke potentiële startpositie afzonderlijk worden gerapporteerd, zelfs wanneer matches overlappen. Voor dezelfde vijf rijen moet de runtime vijf matches afgeven: rijen 0–4, 1–4, 2–4, 3–4, en 4–4. Geen ervan kan worden vervangen door een "langere die eerder start", omdat de standaard zegt dat de gebruiker ze allemaal wil.

Merk op dat het predicaat niet is veranderd. A AS TRUE evalueert op elke rij hetzelfde, ongeacht welke context het vraagt, dus aan de zelfde-lot-conditie van §2.5 is nog steeds voldaan. Wat verandert is de uitvoer-vereiste: zelfs contexten met identieke toekomsten moeten naast elkaar bestaan omdat ze overeenkomen met onderscheiden rijen van het resultaat. De planner schakelt daarom contextabsorptie uit zodra AFTER MATCH SKIP TO NEXT ROW van kracht is, ongeacht de DEFINE-clausule.

§2.6 en §2.7 naast elkaar gezet geeft het volledige beeld van wanneer absorptie faalt:

Eén van beide condities volstaat om absorptie voor de betrokken contexten uit te schakelen. Wanneer geen van beide van kracht is — de standaard AFTER MATCH SKIP PAST LAST ROW met DEFINE-condities die uitsluitend PREV, NEXT of een onversierde LAST gebruiken — reduceert de runtime tot één enkele context per patroonpositie en blijft het hele traject lineair.

§3. Ontwerp — Van Parser tot Executor

Row Pattern Recognition is geïmplementeerd als drie stadia die het werk via welgedefinieerde tussenvormen doorgeven. De parser zet SQL-tekst om in een patroonboom en een lijst DEFINE-predicaten; de planner compileert de boom tot een vlakke array van patroonelementen en beslist welke ervan aan contextabsorptie kunnen deelnemen; de executor voert de array rij voor rij uit tegen de partitie in een driefasenlus. Elk stadium heeft zijn eigen datavorm, en het meeste ontwerpinzicht zit aan de grenzen: een vlakke NFA die in de cache past, een navigatiemodel dat één enkele tuple-slot hergebruikt in plaats van er één per verwijzing te materialiseren, en een absorptieregel die O(n²)-geheugen omzet in O(n).

SQL-tekst
  │
  │  parserstadium
  ▼    valideer frame
       bouw patroonboom
       typecheck DEFINE

patroonboom + DEFINE-lijst
  │
  │  plannerstadium
  ▼    optimaliseer de boom
       compileer naar vlakke NFA-array
       bepaal absorbeerbaarheid

vlakke NFA + absorptievlaggen
  │
  │  executorstadium
  ▼    per-rij-engine:
       Match → Absorbeer → Voortgaan

matchresultaat:
  startrij, lengte, succes/fail

De onderstaande secties lopen deze pipeline door. §3.1 behandelt de parser en de vorm van de patroonboom; §3.2 behandelt de compilatie die de boom omzet in de vlakke NFA; §3.3 behandelt het navigatiemodel dat DEFINE-predicaten gebruiken om naar buurrijen te kijken; §3.4 behandelt matchgrensafhandeling — de SKIP-, INITIAL- en begrensd-frame-regels die vastleggen waar een match begint en eindigt; §3.5 is de driefasen-per-rij-engine; §3.6 verzamelt alle snoeimechanismen die de toestandsruimte begrensd houden; en §3.7 inventariseert wat de implementatie in EXPLAIN-uitvoer onthult.

3.1 Parser — de patroonboom bouwen

De parser herkent patroonherkenning aan de aanwezigheid van een PATTERN-clausule binnen een window-specificatie. Zijn eerste taak is framevalidatie, aangezien RPR beperkingen oplegt die gewone window-queries niet kennen: de framemodus moet ROWS zijn (niet RANGE of GROUPS), de begingrens moet CURRENT ROW zijn, en EXCLUDE-opties zijn verboden. Dit zijn conformiteitscontroles, geen optimalisaties — RPR's notie van een frame is de matchspanwijdte, en de standaard overweegt niet deze met iets anders dan de gematchte rijen te vullen.

Zodra het frame de validatie doorstaat, zet de parser de PATTERN-clausule om in een boom opgebouwd uit vier soorten knooppunten — een variabeleverwijzing, een sequentie (concatenatie), een alternatie, en een groep (subpatroon tussen haakjes). Elk knooppunt draagt de kwantor als drie getallen — een ondergrens, een bovengrens (mogelijk oneindig), en een vlag voor reluctante matching:

Elk DEFINE-predicaat wordt vervolgens getypecheckt tegen de kolommen van de partitie en gecoerced tot een Booleaanse expressie. Hierbij gebeuren twee praktische zaken. Ten eerste wordt elke kolom waarnaar door een DEFINE-predicaat wordt verwezen geregistreerd als onderdeel van de uitvoer-vereisten van de query, zodat de planner die kolommen doorgeeft tot het executorstadium, zelfs als de omringende query ze niet selecteert — zonder dit zou de runtime niets hebben om tegen te evalueren. Ten tweede zijn variabelen die in de PATTERN verschijnen maar nooit in de DEFINE impliciet waar: ze matchen elke rij.

3.2 Compilatie — van AST naar een vlakke NFA

De planner zet de boom van de parser om in de datastructuur die de executor zal uitvoeren: een vlakke array van patroonelementen die per index wordt geadresseerd. De compilatie verloopt als een zesstaps-pipeline:

compile(astTree):
  1. optimaliseer de AST
  2. meet grootte en diepte
  3. alloceer de element-array
  4. vul vanuit de AST
       (wijs next/jump-pointers toe)
  5. finaliseer — stel FIN-schildwacht in
  6. markeer absorptie-geschikte elementen

De vlakke vorm is om een eenvoudige reden gekozen: de executor moet het patroon vele malen per partitie doorlopen, en een aaneengesloten index-adresseerbare array is de goedkoopste datastructuur om te doorlopen. Stappen 1 en 6 zijn de interessante — stap 1 omdat deze bepaalt hoe groot de array wordt, en stap 6 omdat deze beslist of de absorptie-optimalisatie van §2.5 überhaupt in werking treedt.

AST-optimalisatie

Optimalisatie loont tweemaal: één keer in de statische elementtelling van de vlakke array, en opnieuw bij elke rij die tijdens runtime wordt verwerkt. Elke transformatie verkleint de toestandsruimte die de runtime moet opsommen. De optimizer past achter elkaar acht herschrijfregels toe totdat de AST stopt met veranderen:

SEQ-afvlakking

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

Samenvoeging van opeenvolgende variabelen

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

Samenvoeging van opeenvolgende groepen

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

Samenvoeging van opeenvolgende ALT

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

Prefix/suffix-absorptie

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

ALT-afvlakking & dedup

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

Kwantorvermenigvuldiging

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

Uitpakken van enkel kind

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

Kwantorvermenigvuldiging is de enige transformatie die een veiligheidscontrole vereist: de optimizer voegt uitsluitend samen in drie veilige gevallen — beide kwantoren onbegrensd ((A+)+ → A+), buitenste exact ((A{2,3}){5} → A{10,15}), of het kind triviaal {1,1} ((A){2,5} → A{2,5}). Andere combinaties kunnen gaten introduceren die de vlakke vorm zou missen — bijv. (A{2}){2,3} accepteert alleen {4, 6}, maar een naïeve A{4,6} zou ook 5 accepteren — dus laat de optimizer ze intact.

Elementvorm

Elk element van de vlakke array vertegenwoordigt één positie in het patroon. Er zijn vijf logische soorten: een variabeleverwijzing (de enige soort die een rij consumeert); markers voor groepsbegin en groepseinde, die een subpatroon tussen haakjes openen en sluiten; een alternatiemarker, die een lijst van takken aanvoert; en een eindmarker aan het einde van het patroon.

Elk element draagt ook een diepte (zijn groepsnestingsniveau), de kwantor (een min- en max-herhalingstelling, mogelijk oneindig), en twee transitiewijzers — next, "waarheen te gaan nadat dit element is geconsumeerd," en jump, "waar naar te springen" (gebruikt door alternatie om takken aan elkaar te koppelen, door groepsbegin om het lichaam te omzeilen wanneer de kwantor nul toestaat, en door groepseinde om terug te lussen naar het lichaam).

Voor PATTERN ((A B)+) ziet de gecompileerde array er als volgt uit:

PATTERN ((A B)+) compileert naar:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (opent groep; jump slaat
     over naar FIN wanneer min = 0)

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

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

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (sluit groep; jump lust terug)

[4] FIN    patroon compleet

Het patroon wordt links-naar-rechts gelezen via next, terwijl jump de niet-lineaire randen afhandelt. Bij idx 3 wijst de jump van END terug naar idx 1, wat de manier is waarop de onbegrensde buitenste kwantor lust; bij idx 0 zou de jump van BEGIN over de END heen springen naar idx 4 indien de groep optioneel was. De runtime hoeft nooit tijdens runtime een graaf op te bouwen — hij volgt simpelweg deze twee wijzers terwijl hij de array doorloopt.

Attributen per element

Naast vorm draagt elk element vier logische attributen die het gedrag van de runtime op die positie sturen:

Reluctant

Keert de volgorde van kwantoruitbreiding om. Gulzige kwantoren proberen "loop opnieuw" vóór "exit"; reluctante kwantoren proberen eerst "exit". Gedragen door de variabele voor A+?; gedragen door BEGIN en END van de groep voor ((…)+?).

Empty-loopable

Ingesteld op groepseindes waarvan het lichaam nullable is ((A?)*, (A? B?)+, (A | B*)). Vertelt de runtime om een fast-forward-exit toe te voegen naast de normale loop-back, zodat de cyclusbewaker geen legitieme matches doodt in groepen die lege iteraties kunnen produceren.

In-absorbable-region

Markeert elk element dat binnen een absorptie-geschikte regio ligt — gebruikt door de runtime om bij te houden of de huidige toestand zich nog in veilig gebied bevindt.

Absorption-comparison-point

Markeert het specifieke element waar absorptievergelijkingen moeten worden uitgevoerd. Voor een eenvoudige A+ komt deze op de variabele te liggen; voor een onbegrensde groep als (A B)+ komt deze uitsluitend op het groepseinde te liggen.

De splitsing tussen "in-region" en "comparison-point" is van belang omdat absorptie alleen zinvol is op punten waar iteraties sluiten. Binnen het lichaam van (A B)+ bevindt de runtime zich midden in een iteratie en heeft de teller nog niet zijn eindwaarde voor die ronde bereikt; vergelijken op deze plek zou betekenen dat onvergelijkbare waarden worden vergeleken. De toestand moet het groepseinde bereiken voordat de runtime kan beslissen. Het eerste attribuut zegt daarom "je bent nog in absorbeerbaar gebied"; het tweede zegt "je hebt het vergelijkingspunt bereikt — controleer nu."

Absorbeerbaarheidsanalyse

Stap 6 van de compilatie is wat de "zelfde lot"-regel van §2.5 zijn compile-time-getuige geeft. De beslissing is gelaagd:

isAbsorbable(query):
  if SKIP-modus != SKIP PAST LAST ROW
      → return false
  if frame-einde != UNBOUNDED FOLLOWING
      → return false
  if enige DEFINE afhankelijk van match_start
      → return false
  doorloop de AST en markeer
  elementen die voldoen aan
  een structureel geval

De eerste drie controles zijn op queryniveau: ze corresponderen precies met de condities van §2.7 (uitvoerzijde: SKIP-modus), begrensd frame (grens doorbreekt monotoniciteit), en §2.6 (datazijde: FIRST of offsetdragende LAST in DEFINE). Wanneer een ervan faalt, plaatst de analyse geen vlaggen en is absorptie querybreed uitgeschakeld. Wanneer ze alle slagen, laat de AST-doorloop drie structurele vormen toe:

Geval 1 — Eenvoudige onbegrensde variabele

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

Elke iteratie is precies één rij. De teller van een eerdere context is altijd ≥ die van een latere op elke gedeelde positie.

Geval 2 — Groep met vaste lengte, onbegrensd buitenste

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

Elk kind heeft min == max, dus is het lichaam semantisch equivalent met zijn uitgerolde {1,1}-vorm — (A B{2})+ gedraagt zich als (A B B)+. Elke iteratie consumeert een vast aantal rijen; tellerdominantie blijft gelden.

Geval 3 — Groep waarvan het lichaam begint met een onbegrensde variabele

(A+ B)+

De voorloopende onbegrensde variabele is zelf absorbeerbaar (Geval 1) en beschermt eerdere contexten. Absorptie stopt zodra de toestand voorbij A beweegt — de rest van het lichaam biedt geen monotoniciteitsgarantie, dus worden vlaggen uitsluitend op A gezet.

De structurele gevallen die niet door deze drie vormen worden gedekt zijn even leerzaam. A B+ kan met de huidige regel niet worden geabsorbeerd omdat de voorloopende A een rij consumeert vóórdat het onbegrensde deel begint, dus contexten die één rij uit elkaar starten bevinden zich op verschillende posities binnen het onbegrensde lichaam. (Een vervolg-uitbreiding "PREFIX-absorptie" die vaste-lengte-prefixen afhandelt via een schaduwpad is ontworpen en gepland voor een aparte patch.) Reluctante kwantoren zoals A+? zijn per constructie uitgesloten: de absorptieregel veronderstelt gulzige semantiek, waarin langere matches kortere absorberen, en reluctante matching keert die richting om.

Het resultaat is een beslissing per element in plaats van per patroon. Eén enkel queryplan kan absorptie ingeschakeld hebben voor de voorloopende A+ van patronen als (A+ B+ C) of (A+ B+)+ — dit laatste is gewoon Geval 3 toegepast op zijn voorloopende element — en uitgeschakeld voor alles erna; de runtime raadpleegt simpelweg het vergelijkingspuntattribuut op het element van de huidige toestand telkens als het een absorptiepass overweegt. Zodra een toestand naar een niet-absorbeerbare regio beweegt, is absorptie permanent uit voor die toestand — precies wat §2.5 en §2.6 nodig hebben om op algoritmisch niveau waar te zijn.

3.3 Navigatie — de 1-slot tuple-swap

DEFINE-expressies zijn gewone SQL-expressies die tegen een rij worden geëvalueerd, maar ze kunnen PREV, NEXT, FIRST of LAST bevatten — verwijzingen die naar andere rijen wijzen. De rijen zelf zijn al gebufferd in de tuplestore van het window; wat de executor nog moet beheren is de tuple-slot waaruit de SQL-expressiemachinerie leest, aangezien kolomverwijzingen binnen de expressie tijdens het plannen aan een slot worden gebonden. De implementatie hergebruikt één enkele navigatieslot voor elke navigatieaanroep: de slot wordt ingewisseld vóór het evalueren van de binnenste expressie en daarna hersteld, zodat de rest van de SQL-expressiemachinerie het verschil nooit merkt.

Het model dat de executor ziet is klein: er is een huidige-rij-slot die de rij bevat waartegen de DEFINE-expressie wordt geëvalueerd, en een navigatieslot die de runtime tijdelijk naar een andere rij kan omleiden. Rondom elke navigatieaanroep stelt de runtime de navigatieslot in, evalueert de binnenste expressie alsof deze de huidige rij leest, en herstelt vervolgens de oorspronkelijke rij. Pseudocode:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos buiten geldig bereik:
      return NULL

  bewaar current_row_slot
  haal rij op positie targetPos op
    in current_row_slot
  result = eval_inner_expression()
  herstel current_row_slot
  return result

De truc is dat er precies één slot is om op te slaan en te herstellen. De binnenste expressie — wat deze ook is, inclusief rekenkunde, functieaanroepen of andere kolomverwijzingen — wordt uitgevoerd tegen de gewisselde slot via hetzelfde evaluatiepad als bij de huidige rij. Geen alternatieve evaluator, geen schaduwslot, geen tuple-kopie.

Samengestelde navigatie wordt tijdens het parsen afgevlakt zodat de wissel nog steeds eenmalig plaatsvindt. PREV(FIRST(price)) wordt herkend als een tweestappige navigatie — "ga naar de eerste gematchte rij, en stap dan één rij eerder" — en opgeslagen als één navigatieaanroep met een samengesteld type. De runtime berekent de doelpositie in twee fasen, maar voert slechts één slotswap uit om de uiteindelijke rij op te halen:

compute_target_position(call):

  # huidige-rij relatief
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # match-relatief
  FIRST(n):
      return matchStart + n
  LAST(n):
      return lastMatchedRow − n

  # samengesteld: match-rel, dan stap
  PREV(FIRST(n), m):
      return (matchStart + n) − m
  NEXT(FIRST(n), m):
      return (matchStart + n) + m
  PREV(LAST(n), m):
      return (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      return (lastMatchedRow − n) + m

  valideer tegen het geschikte bereik
  (matchbereik voor binnen FIRST/LAST,
   partitiebereik voor buitenste stap)

Een positiecache kortsluit het ophalen uit de tuplestore wanneer meerdere navigatieaanroepen in dezelfde DEFINE op dezelfde rij richten — gebruikelijk in expressies als price > PREV(price) AND volume > PREV(volume) waar beide aanroepen tot de vorige rij resolveren. De cache slaat alleen "laatst opgehaalde positie" op, en de swap zelf blijft één enkele operatie.

De classificatie van navigatieaanroepen is de bijdrage van de planner aan de absorptiebeslissing. De planner doorloopt elke DEFINE-expressie en sorteert elke variabele in een van twee buckets, op basis van of alle contexten dezelfde Booleaanse waarde op dezelfde rij zullen berekenen, of dat elke context zijn eigen berekent. De bucket bepaalt twee dingen tijdens runtime: hoe vaak de variabele wordt geëvalueerd (eenmaal gedeeld, of eenmaal per betrokken context — §3.5 Fase 1), en of de omringende toestand in aanmerking komt voor contextabsorptie (§2.5 vs §2.6).

De classificatie wordt tijdens het plannen uitgevoerd en samen met elke DEFINE-variabele opgeslagen, zodat de runtime geen tijd besteedt aan beslissen — hij leest simpelweg de bucket voor elke variabele tijdens het verwerken van een rij.

Retentiebudget

Navigatie reikt naar rijen die de window-functiemachinerie anders al voorbij zou hebben gestreamd. Om die rijen beschikbaar te houden is de executor gebouwd boven op een tuplestore die een schuivend venster van recente rijen behoudt; de vraag is hoe breed dat venster moet zijn. De patch beslist tijdens compilatie, op basis van twee complementaire offsets:

Lookback-budget

Hoe ver achterwaarts vanaf de huidige rij elke DEFINE-aanroep zou kunnen reiken.

Bijdragers: PREV, LAST met offset, PREV(LAST(...)), NEXT(LAST(...))

Lookahead-vanaf-start-budget

Hoe ver voorwaarts (of achterwaarts, indien negatief) vanaf het matchbegin van de oudste actieve context elke DEFINE-aanroep zou kunnen reiken.

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

Tijdens runtime wordt de trim-markering van de tuplestore gezet op de vroegste van twee posities — de huidige rij minus het lookback-budget, en het matchbegin van de oudste actieve context plus het lookahead-budget. Alles vóór die markering kan door geen enkele navigatieaanroep in een actieve context worden bereikt, en de tuplestore mag het laten vallen. De twee Nav Mark-tellers die EXPLAIN rapporteert (§3.7) — Lookback en Lookahead — zijn de gemeten pieken van de twee budgetten, het diepste dat de executor ooit in beide richtingen heeft moeten reiken in de loop van de query.

3.4 Matchgrenzen — SKIP, INITIAL, en begrensd frame

Een succesvolle match wordt opgeslagen als een kleine bundel waarden: een geldigheidsvlag, een succes/faalvlag, de rij waarop de match begint, en het aantal rijen dat deze heeft geconsumeerd. Wanneer de geldigheidsvlag is ingesteld, kunnen daaropvolgende vragen aan de executor — "valt deze rij binnen een match?" — in O(1) worden beantwoord door de bundel te inspecteren. Een lengte van nul is een echt resultaat, geen fout: het vertegenwoordigt een patroon dat is gematcht zonder een rij te consumeren, wat de executor moet onderscheiden van "er is op deze positie nog geen matchpoging gedaan."

De AFTER MATCH SKIP-clausule beslist waar de volgende matchpoging begint. AFTER MATCH SKIP PAST LAST ROW verplaatst naar de rij na het matcheinde, waarbij de niet-overlappende uitvoer wordt geproduceerd die de meeste queries willen, en de absorptie-optimalisatie wordt geactiveerd.

AFTER MATCH SKIP TO NEXT ROW verplaatst slechts naar de rij na het matchbegin start, waardoor overlappende matches mogelijk worden; de planner schakelt daarom absorptie voor het hele queryplan uit wanneer deze modus van kracht is.

De twee skip-doelen die de standaard ook definieert — AFTER MATCH SKIP TO FIRST var en AFTER MATCH SKIP TO LAST var — zijn afhankelijk van per-match-historie die deze patch niet bijhoudt. Ze komen helemaal niet voor in de grammatica, dus de parser geeft een generieke syntaxisfout als een ervan wordt opgegeven.

Hetzelfde geldt voor SEEK, het alternatief van de spec voor INITIAL. Onder SEEK mag een matchpoging die op rij R begint slagen op elke rij van R tot het einde van het frame, niet uitsluitend op R zelf. De patch implementeert uitsluitend INITIAL: elke potentiële match wordt verankerd op een specifieke rij. De parser geeft een fout als SEEK wordt gevraagd. Begrensde frames krijgen hun eigen behandeling — wanneer de gebruiker ROWS BETWEEN CURRENT ROW AND N FOLLOWING schrijft in plaats van UNBOUNDED FOLLOWING, kortsluit de executor elke context waarvan de match de grens heeft bereikt door een mismatch te forceren, en absorptie wordt uitgeschakeld omdat de grens de monotoniciteitsaanname doorbreekt waarop absorptie steunt.

3.5 De driefasen-per-rij-engine

De per-rij-driver van de executor wordt aangeroepen door de omringende window-functiemachinerie wanneer deze moet weten of een gegeven rij tot een gematcht frame behoort. De driver vindt of creëert de context voor de huidige startpositie, evalueert elk DEFINE-predicaat één keer tegen de huidige rij om een Booleaanse array per variabele te produceren, en stuurt vervolgens de NFA met één rij vooruit. De voorwaartse stap zelf bestaat uit drie fasen in een vaste volgorde — Match, Absorbeer, Voortgaan — verpakt in dezelfde buitenste lus:

processRow(currentPos):

  # Fase 1 — MATCH (convergentie)
  voor elke context:
      als context begrensd frame overschrijdt:
          forceer mismatch (vroegtijdig finaliseren)
          continue
      als matchStartRow afwijkt van
         de gedeelde evaluatiepositie:
          herevaluer matchstart-
          afhankelijke DEFINE-vars (§3.3)
      match(context, varMatched)

  # Fase 2 — ABSORB
  als patroon absorbeerbaar is:
      ververs vlaggen van elke context
      absorb_contexts()

  # Fase 3 — ADVANCE (divergentie)
  voor elke context:
      advance(context, currentPos)

De volgorde is geen stilistische keuze. Match moet eerst draaien omdat absorptie post-match-tellers vergelijkt; Absorb vóór Match draaien zou toestanden vergelijken die op het punt staan te sterven. Advance moet als laatste draaien omdat het de enige fase is die nieuwe toestanden creëert — het breidt elke overlevende toestand uit via epsilon-transities tot elk een variabele bereikt die op de volgende rij wacht. Absorb na Advance draaien zou betekenen dat gedivergeerde opvolgers worden vergeleken, en mist het punt waarop toestanden het zuiverst vergelijkbaar zijn.

Fase 1 — Match

Match is een "convergentie"-fase: toestanden overleven met een verhoogde teller, of sterven. Een subtiel punt is dat Match voor variabelen die zich in een absorbeerbaar gebied bevinden ook een kleine hoeveelheid voorwaartse vooruitgang uitvoert, zodat Absorb zuiver kan vergelijken. De cover-conditie treedt uitsluitend op het absorbeerbare vergelijkingspunt op — de END van de onbegrensde groep — dus toestanden die zojuist mid-iteratie-variabelen hebben gematcht (zoals B binnen (A B)+) moeten tijdens Match zelf worden doorgelopen tot dat vergelijkingspunt; anders vindt Absorb niets om te vergelijken en treedt de optimalisatie nooit in werking.

match(context, varMatched):
  voor elke toestand in context:
      elem = pattern[state.elemIdx]
      als elem geen variabele is:
          continue   # advance handelt het af

      als niet varMatched[elem.varId]:
          verwijder toestand   # dode tak
          continue

      state.counts[elem.depth] += 1

      # Inline voorwaartse vooruitgang zodat
      # de volgende fase op het vergelijkings-
      # punt-element kan vergelijken in plaats
      # van mid-iteratie.
      als elem in-region is maar niet
         het vergelijkingspunt,
         en zijn maxteller heeft bereikt,
         en elem.next een groepseinde is:

          doorloop de END-keten:
            verhoog buitenste groepsteller
            verplaats state.elemIdx naar END
            ga door zolang nog in-region,
              must-exit, en next END is
          (stopt op het vergelijkingspunt
           of op een nog-loopbaar element)

De end-keten-doorloop is wat geneste vaste-lengte-groepen absorbeerbaar maakt. In ((A B){2})+ moet, wanneer B zijn max bereikt (B is {1,1}), de teller van de binnenste groep worden verhoogd; als die teller ook zijn max bereikt — waarmee de binnenste {2} wordt gesloten — moet de teller van de buitenste groep ook worden verhoogd, enzovoort, totdat de toestand op het buitenste absorptiepunt landt — de END van de onbegrensde buitenste groep (de +). Door dit werk in Match te doen kan Absorb vergelijken met contexten die hun post-iteratie-tellers reeds hebben geconsolideerd.

Fase 2 — Absorb

De absorb-pass doorloopt contexten van nieuwste (staart) naar oudste (kop). Voor elke lopende context die volledig absorbeerbaar is, scant deze achterwaarts naar een oudere lopende context die haar dekt, en geeft de nieuwere vrij indien gevonden. Omdat contexten in volgorde van aanmaak worden bewaard en elke rij hooguit één context creëert, betekenen "nieuwer" en "ouder" werkelijk "later gestart" en "eerder gestart".

absorb_contexts():
  voor ctx van staart achterwaarts:
      als ctx voltooid is
         of een niet-absorbeerbare toestand heeft:
          sla over
      voor older van ctx.prev achterwaarts:
          als older voltooid is
             of geen absorbeerbare toestand heeft:
              sla over
          als covered(older, ctx):
              free(ctx)
              registreer absorptielengte
              break

covered(older, newer):
  voor elke toestand in newer:
      elem = pattern[state.elemIdx]
      als elem niet het vergelijkingspunt is:
          return false
      als geen toestand in older met:
            zelfde elemIdx
            en isAbsorbable
            en older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Twee microbeslissingen volgen hieruit. De eerste is dat de cover-controle onmiddellijk afwijst als een toestand in de nieuwere context zich ergens anders bevindt dan een vergelijkingspunt — vergelijken op niet-beoordelingspunten zou geen zinvolle vergelijking zijn.

De tweede is het asymmetrische vlaggenpaar op elke context: has-absorbable-state beantwoordt "kan deze context een nieuwere absorberen?" en is monotoon (kan alleen waar→onwaar gaan terwijl toestanden sterven), terwijl all-states-absorbable beantwoordt "kan deze context worden geabsorbeerd?" en dynamisch is (klapt terug naar waar wanneer een niet-absorbeerbare toestand wordt verwijderd). Beide vlaggen worden in constante tijd gecontroleerd vóórdat de cover-scan ook maar begint, dus absorptie betaalt zijn volledige kosten alleen voor contexten die een echte kans hebben te worden geabsorbeerd.

Fase 3 — Advance

Advance is de "divergentie"-fase: elke overlevende toestand wordt uitgebreid via epsilon-transities tot elke tak ofwel een variabele bereikt die op de volgende rij wacht, ofwel de FIN-schildwacht. De uitbreiding is depth-first, en de volgorde waarin gelijksoortige takken worden doorlopen is wat de preferentie-regel van de standaard daadwerkelijk laat werken — de lexicaal eerste tak wordt altijd als eerste toegevoegd, en de deduplicatiestap bij toestandsinvoeging verwerpt stilzwijgend equivalente latere toevoegingen.

advance(context, currentPos):
  haal alle huidige toestanden eruit;
  herbouw ctx.states vanaf nul
  voor elke toestand in lexicale volgorde:
      wis de visited-element-bitmap
      advance_state(state)   # DFS

      # Preferentie: zodra een DFS FIN bereikt,
      # zijn resterende toestanden minder
      # geprefereerd en kunnen worden verwijderd.
      als FIN bereikt en toestanden resteren:
          geef de rest vrij
          break

advance_state(state):
  doorloop via state.elemIdx,
  recursief door:
    ALT-takken (op volgorde),
    BEGIN (groep binnengaan; plus optioneel
           overslagpad als min = 0),
    END (terug lussen / verlaten / fast-forward —
         zie hieronder),
    FIN (registreer matchEndRow,
         bewaar matchedState, en snoei
         latere contexten binnen het
         bereik van deze kandidaat — zie hieronder),
  stoppend bij elke aangetroffen variabele:
      voeg toestand toe aan ctx.states
      (dedupliceren op elemIdx + counts)

Het registreren van een toestand die FIN bereikte doet meer dan alleen de kandidaatmatch markeren. Onder AFTER MATCH SKIP PAST LAST ROW moet de volgende rapporteerbare match strikt voorbij de huidige beginnen — dus zodra een kandidaat wordt geregistreerd, wordt elke daaropvolgende context waarvan de startrij binnen het bereik van de kandidaat valt onmiddellijk gesnoeid, ook al kan de context die FIN raakte via gulzige terugval blijven zoeken naar een langere match.

Het snoeien is veilig omdat, ongeacht hoe die zoektocht eindigt (een langere match vervangt de kandidaat, of de kandidaat blijft staan), alle gesnoeide contexten zijn gestart binnen een bereik dat de volgende rapporteerbare match moet overslaan, en dus nooit eigen uitvoer zouden kunnen produceren.

Dit is een van de twee FIN-tijd-snoeistappen — de andere, eerder in deze sectie als onderdeel van Advance beschreven, verwerpt lexicaal-inferieure toestanden binnen dezelfde context.

De lastigste per-element-logica leeft in de END-handler. Wanneer de iteratieteller van een groep onder de ondergrens ligt, moet de runtime terug lussen; wanneer deze op of boven de bovengrens is, moet hij verlaten; daartussen zijn beide opties geldig en bepaalt de gulzigheid van de kwantor welke eerst wordt geprobeerd:

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

  als count < elem.min:
      lus terug in het lichaam
      als elem empty-loopable is:
          # nullable lichaam, zie §3.2
          kloon ook een fast-forward-
          toestand die de groep verlaat
          met count vervuld
          (redt legitieme matches
           die de cyclusbewaker anders
           zou doden)

  elif count >= elem.max:
      reset tellers op deze diepte
      verlaat via next
      (END→END: verhoog buitenste
       END-teller)

  else:
      # min <= count < max: fork
      bouw een exit-toestand
      (tellers op deze diepte gereset)
      als gulzig:
          eerst lussen, dan verlaten
          # voorkeur langer
      else (reluctant):
          eerst verlaten
          als exit FIN bereikte:
              verwerp de lus
              # voorkeur korter
          else lus als tweede

Elke toestand die aan een context wordt toegevoegd doorloopt een deduplicatiecontrole die zijn positie en tellers vergelijkt met de bestaande toestandslijst. Omdat Advance takken in DFS-volgorde verwerkt, landt de toestand uit de eerste tak van elke alternatie als eerste — en elke latere tak die dezelfde positie en tellers oplevert wordt bij invoeging afgewezen. Dit is precies wat de lexicaal-volgorde-regel van §2.4 verlangt, geïmplementeerd onderaan de runtime zonder afzonderlijke pass.

Empty-loopable groepen

Een subtiel geval dat de runtime moet ontmantelen is de nullable groep — een groep waarvan het lichaam nul rijen kan matchen omdat elk kind van het lichaam zelf optioneel is. Patronen als (A?)*, (A? B?)+ en (A | B*) hebben alle deze eigenschap: afhankelijk van de data kan het lichaam een iteratie voltooien zonder ook maar één rij te consumeren. Dat is in principe prima, maar het levert een reëel gevaar op voor de epsilon-uitbreiding van de NFA. Als het lichaam een lege match produceert, lust het END-element terug naar BEGIN, het lichaam produceert opnieuw een lege match, BEGIN lust naar END, enzovoort. Zonder iets om het te stoppen zou de DFS van Advance nooit eindigen.

De runtime stopt het met een visited-element-bitmap (één bit per patroonelement), gewist vóór elke DFS-uitbreiding van een toestand: zodra een element binnen dezelfde uitbreiding voor de tweede keer wordt bezocht, wordt dat pad opgegeven. De cyclusbewaker is onvoorwaardelijk en goedkoop, maar heeft een neveneffect — hij kan ook paden opgeven die de ondergrens zouden moeten bereiken via legitieme lege iteraties. Neem (A?){2,3} zonder dat ergens in de rijenstroom een A matcht:

gewenst gedrag:
  iter 1: A? matcht nul rijen
          → END, count = 1 (onder min)
  iter 2: A? matcht nul rijen
          → END, count = 2 (haalt min)
  afsluiten met een nullengte-match

wat de cyclusbewaker alleen doet:
  iter 1: A? overgeslagen → END, count = 1
          → terug lussen naar BEGIN
  iter 2: BEGIN reeds bezocht
          → DFS afgebroken
  count bereikt min nooit
  → match faalt (onjuist)

De oplossing wordt tijdens compilatie bepaald en tijdens runtime uitgevoerd. Wanneer de planner een groep ziet waarvan het lichaam nullable is, tagt deze het END-element van die groep als empty-loopable. Tijdens runtime, wanneer de END-handler op het punt staat terug te lussen omdat de iteratieteller nog onder de ondergrens ligt, vertelt de empty-loop-tag deze om een aanvullende fast-forward-toestand te klonen naast het normale loop-back-pad:

advance_end (count onder min):

  primair pad:
    lus terug in het lichaam
    (houdt de deur open voor een echte,
     niet-lege match in de volgende
     iteratie)

  als elem empty-loopable is:
    fast-forward-pad:
      reset de teller op deze diepte
      verlaat de groep via next,
      en behandel resterende vereiste
      iteraties als lege matches

De twee paden vervullen complementaire rollen. De primaire loop-back vangt het geval op waarin het lichaam nog later echte matches kan produceren — bijvoorbeeld bij (A?){2,3} gevolgd door data waarin A alleen op latere rijen matcht, is de loop-back wat de tweede en derde iteratie in staat stelt niet-lege matches te vinden. De fast-forward vangt het geval op waarin het lichaam nooit iets produceert: deze omzeilt de cyclusbewaker door de groep volledig te verlaten en verklaart "de rest van de vereiste iteraties zijn leeg", waardoor de match kan slagen met een lichaam van lengte nul. Beide toestanden worden aan de context toegevoegd; degene die met succes uitbreidt wint, en de deduplicatiecontrole bij invoeging voorkomt dat een van beide paden meer dan zijn deel aan toestanden voortbrengt.

Naast de cyclusbewaker disambigueert nog één opstart-truc nul-rij-uitkomsten aan het begin van een context. De contextcreatiestap bij elke potentiële startrij voert een initiële voortgang uit via epsilon-transities voordat een rij wordt geconsumeerd, gebruikmakend van een positie één rij vóór het werkelijke begin. Elk pad dat de FIN-schildwacht uitsluitend via epsilon-transities bereikt — zonder een rij te consumeren — produceert daarom een eindpositie kleiner dan de startpositie; die negatieve-spancoördinaat, gecombineerd met of FIN daadwerkelijk werd bereikt, codeert het verschil tussen een lege match (lengte-0-match geaccepteerd) en een ongematchte start zonder dat een aparte vlag nodig is.

3.6 Hoe de toestandsruimte begrensd blijft

De lineariteit van de runtime is niet het resultaat van één enkele optimalisatie. Het is het cumulatieve effect van een gelaagde reeks snoeiregels, elk gericht op een andere oorzaak van toestandsruimtegroei op een ander punt in de per-rij-cyclus. Sommige worden tijdens compilatie bepaald en alleen tijdens runtime geraadpleegd; andere treden dynamisch in werking. Sommige doden afzonderlijke toestanden; andere doden gehele contexten. De voorgaande secties introduceerden ze elk in context; de onderstaande tabel zet ze op één pagina.

Mislukt predicaat Match

Variabele-toestanden waarvan de DEFINE op de huidige rij onwaar evalueerde — dode takken.

Inline end-keten-voortgang Match

Variabelen die hun maxteller hebben bereikt en de toestand anders mid-iteratie zouden achterlaten; doorgevoerd door vaste-lengte-groepseindes zodat absorptie op het juiste punt kan vergelijken.

Contextabsorptie Absorb

Nieuwere contexten waarvan elke toestand wordt gedekt door een toestand van een oudere context met een hogere teller — zie §2.5 voor de conceptuele regel, §3.2 voor de compile-time-geschiktheid, §3.5 voor de per-paar-controle.

Toestanddeduplicatie Advance

Toestanden bereikt via verschillende DFS-takken die op dezelfde positie met dezelfde tellers eindigen — alleen de eerste (lexicaal vroegste) overleeft; latere equivalenten worden stilzwijgend verworpen, wat ook is hoe preferentie wordt afgedwongen (§2.4).

FIN-vroege-beëindiging (binnen context) Advance

Toestanden die nog in de DFS-wachtrij staan wanneer één tak FIN bereikt — op grond van lexicale volgorde zijn alle resterende toestanden minder geprefereerd en kunnen onmiddellijk worden verworpen.

Kandidaat-match-snoei (over contexten) Bij FIN

Andere contexten waarvan de startrij binnen het bereik van de kandidaatmatch valt — de context die FIN raakte kan nog blijven zoeken naar een langere match (gulzige terugval), maar onder AFTER MATCH SKIP PAST LAST ROW kan elke context binnen het bereik van de kandidaat geen rapporteerbare uitvoer meer produceren, ongeacht hoe die zoektocht eindigt, en wordt onmiddellijk gesnoeid.

Cyclusbewaker Advance

Epsilon-uitbreidingen die hetzelfde patroonelement binnen dezelfde DFS opnieuw bezoeken — zouden anders eeuwig lussen in nullable groepen.

Empty-loop fast-forward Advance

Legitieme lege-iteratie-matches die de cyclusbewaker in nullable groepen zou doden — omzeilt de cyclus door de groep te verlaten met resterende vereiste iteraties verklaard als leeg.

Begrensd-frame-afkapping Match

Contexten waarvan de match de door de gebruiker opgegeven frame-bovengrens heeft bereikt — gedwongen tot mismatch zodat ze daar niet voorbij kunnen reiken (§3.4).

Het lezen van de items op hun fasebadge traceert de levensduur van een context: snoei treedt op bij elke rij door de drie hoofdfasen (Match, Absorb, Advance), en opnieuw bij matchvoltooiing (Bij FIN). Het lezen van de beschrijvingen groepeert de regels in plaats daarvan op wat ze viseren: dode takken, overbodige contexten, equivalente toestanden, oneindige lussen, en overschrijding van door de gebruiker opgelegde grenzen.

Geen enkele regel zou op zichzelf voldoende zijn. De cyclusbewaker alleen zou legitieme matches in nullable groepen doden; de empty-loop fast-forward alleen zou geen oneindige epsilon-lussen stoppen; absorptie alleen zou over-consolideren wanneer DEFINE naar matchstart verwijst; deduplicatie alleen zou geen overbodige contexten verwijderen, alleen overbodige toestanden. De runtime blijft lineair in de gevallen die ertoe doen — PATTERN (A+ B+ C+ D) op 100.000 rijen, de benchmark in paneel ③ van de poster — uitsluitend omdat elke laag opvangt wat de lagen erboven missen.

3.7 EXPLAIN-uitvoer

EXPLAIN ANALYZE op een query met RPR onthult NFA-niveau-statistieken die voor gewone window-functies niet aanwezig zijn. Drie groepen tellers worden naast de window-operator afgegeven:

NFA States:    peak, total, merged
NFA Contexts:  peak, total, pruned
NFA: matched     (len min/max/avg)
NFA: mismatched  (len min/max/avg)
NFA: absorbed    (len min/max/avg)
NFA: skipped     (len min/max/avg)
Nav Mark Lookback:   | runtime | retain all
Nav Mark Lookahead:  | runtime | retain all
  (uitsluitend wanneer de query FIRST,
   PREV(FIRST(...)) of NEXT(FIRST(...)) gebruikt)

Peak en total zijn directe instrumentatie van de runtime: hoeveel toestanden ooit gelijktijdig actief waren, hoeveel er over de levensduur van de query zijn gecreëerd, en hoeveel er door deduplicatie zijn samengevoegd. De matchlengtehistogrammen scheiden vier uitkomsten — succesvolle matches, mislukte matchpogingen, geabsorbeerde contexten, en contexten die werden gesnoeid (skipped) zonder te zijn geëvalueerd — en het rapporteren ervan met min/max/avg maakt prestatiepathologieën in één oogopslag zichtbaar: een gezonde run toont de meeste contexten als gematcht of geabsorbeerd, met kleine mismatched-lengtes.

De twee Nav Mark-tellers rapporteren het tuplestore-retentiebudget dat §3.3 tijdens compilatie afleidt. Lookback is de diepste achterwaartse reikwijdte over PREV, LAST met offset, en de samengestelde vormen met binnenste LAST; Lookahead is de diepste voorwaartse (of achterwaartse, indien negatief) reikwijdte gemeten vanaf het matchbegin van de oudste actieve context, bijgedragen door FIRST en de samengestelde vormen met binnenste FIRST.

Elke teller wordt afgedrukt als een vast geheel getal wanneer de offset constant is, "runtime" wanneer de offset een niet-constante expressie is die bij elke aanroep moet worden geëvalueerd, en "retain all" wanneer de runtime een onbegrensd budget nodig heeft. Lookahead wordt alleen afgegeven wanneer de query daadwerkelijk matchstart-relatieve navigatie gebruikt.

Samen maken deze tellers het mogelijk om RPR-prestaties te debuggen zonder gdb aan de backend te koppelen.

Naast de tellers reproduceert EXPLAIN ook getrouw de oorspronkelijke PATTERN- en DEFINE-clausules, inclusief reluctante kwantoren, groepsherhaling, en de AFTER MATCH SKIP-optie. De implementatie doet aanzienlijke moeite om deze round-trip stabiel te maken zodat pg_dump en pg_upgrade RPR-objecten kunnen behouden zonder semantische afwijkingen — de regressiesuite onder rpr_explain verifieert dit geval voor geval (zie §4).

§4. Tests — Dekkingskaart

De patch wordt geleverd met vijf regressiesuites die samen elke laag beschreven in §3 doorlichten — ruwweg 13.000 regels SQL, elke suite gericht op een andere zorg. De splitsing is opzettelijk: door parserzorgen, runtimecorrectheid, plannerinteracties en uitvoerformattering in afzonderlijke bestanden te houden, worden fouten beter lokaliseerbaar en voorkomt het dat een ongerelateerde wijziging in één laag per ongeluk tests in een andere ongeldig maakt. De vijf suites zijn:

rpr

End-to-end-querysemantiek — realistische window-scenario's op synthetische aandelendata (V-vorm, W-vorm, opeenvolgende stijgingen, omkeringen).

rpr_base

Parserlaag — sleutelwoordacceptatie, syntaxisvormen, kwantoren, navigatieparsing, foutmeldingen, en pg_dump/pg_upgrade round-trip-stabiliteit.

rpr_nfa

NFA-runtime — de driefasenlus, absorptie in elke absorbeerbare vorm, en randgevallen in de contextlevenscyclus.

rpr_explain

Uitvoerformattering — NFA-statistieken, patroon-deparse, identifier-quoting, formaatstabiliteit over herlading.

rpr_integration

Plannerinteracties — bewakingen die voorkomen dat ongerelateerde window-optimalisaties RPR-semantiek corrumperen.

4.1 rpr — end-to-end-scenario's

De scenariosuite is het publieke gezicht van de testset: deze gebruikt een synthetische aandelenkoersdataset van ongeveer 1.600 rijen en voert er realistische queries op uit — V-vormig herstel, W-vorm (dubbele bodem), opeenvolgende stijgingen en dalingen, omkeringspatronen, partities met meerdere symbolen. Het is de enige suite waarin de inputs en outputs lezen als queries die een gebruiker werkelijk zou kunnen schrijven; de andere zijn opzettelijk reductief, telkens gericht op één laag.

Omdat deze queries elke laag combineren (parser, planner, executor, EXPLAIN), vertelt een enkele storing in rpr zelden waar de bug zich bevindt. De vier daaropvolgende suites vormen de bisectie: een storing in rpr plus een geslaagde rpr_base sluit de parser uit; plus een geslaagde rpr_nfa versmalt het tot scenariospecifieke datavormen; plus een geslaagde rpr_integration sluit plannerinterferentie uit; en elke deparse-afwijking duikt op in rpr_explain.

4.2 rpr_base — het parseroppervlak

De base-suite is de grootste, en deze is met reden de grootste: zij is verantwoordelijk voor het bewijzen dat elk legaal stuk syntaxis in §1.2 daadwerkelijk parseert, elk illegaal stuk in §1.3 wordt afgewezen met een nuttige fout, en elke geaccepteerde vorm een serialisatie-round-trip overleeft. Het grootste deel ervan is gevormd als kleine, gerichte fragmenten — één per syntactische feature — in plaats van lange realistische queries, omdat het doel dekking is in plaats van scenariorealisme.

De serialisatietests verdienen bijzondere aandacht. RPR-objecten (views, materialized views, pg_dump-uitvoer) moeten via de catalogusrepresentatie round-trippen zonder semantische afwijking, inclusief subtiliteiten zoals de reluctante vlag op een kwantor of de exacte vorm van een samengestelde navigatie-expressie. Een kleine set serialisatiespecifieke objecten (de rpr_serial_v*-views en hun onderliggende tabellen) wordt aan het einde van de run opzettelijk achtergelaten, zodat de omringende regressie-infrastructuur ze kan oppakken en pg_dump en pg_upgrade erop kan uitvoeren. De rest van de teststeiger wordt zoals gebruikelijk verwijderd. Bugs die op deze manier worden gevangen (zoals een reluctante vlag die verloren gaat tussen deparse en herparse) komen alleen aan het licht wanneer de round-trip end-to-end wordt uitgevoerd.

4.3 rpr_nfa — de runtime-engine

Dit is de suite die elk mechanisme beschreven in §3.5 en §3.6 doorlicht. De tests volgen een consistent patroon: een invoertabel waarvan de rijen expliciete Booleaanse arrays zijn die declareren welke DEFINE-variabelen op elke rij matchen, gekoppeld aan een patroon dat een specifiek runtimegedrag onderzoekt. Het Booleaanse-array-idioom ontkoppelt de runtimetest van de DEFINE-evaluatiemachinerie — wat wordt getest is "produceert de NFA-lus, gegeven dat deze variabelen hier matchen, de verwachte matchspanne?" in plaats van "berekent de DEFINE-expressie-evaluator deze Booleaanse waarden correct?" De DEFINE-evaluator wordt elders getest (rpr_base voor parsing, rpr voor end-to-end-gedrag).

Een typische testfixture ziet er als volgt uit — een kolom van variabelenaam-arrays waarbij elke invoer aangeeft welke DEFINE-variabelen op die rij vuren, en een patroon waarvan de DEFINE-clausules direct op die namen testen:

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

Het lezen van de array-kolom van boven naar beneden is het direct lezen van het testscenario. Rijen 2 en 3 dragen beide namen — zowel A als B vuren daar, dus heeft de NFA een echte keuze waar van het A-been naar het B-been moet worden overgeschakeld. De verwachte match (A bij rijen 1–3 gevolgd door B op rij 4, onder de gulzige preferentie van de standaard) wordt uitsluitend door die vlaggen vastgelegd, zonder hier enige expressie-evaluatie van betekenis — = ANY is slechts de triviale laag die de array-kolom blootstelt aan DEFINE, niet wat de test doorlicht. Hetzelfde scenario schrijven met een numeriek predicaat (price > PREV(price) en dergelijke) zou de NFA-test verstrengelen met het gedrag van de predicaatevaluator; het array-idioom houdt beide zuiver gescheiden, en een storing hier wijst direct naar de NFA-lus.

De absorptiedekking is bijzonder grondig, omdat absorptie de optimalisatie is die het meest waarschijnlijk stilzwijgend verkeerde antwoorden produceert als zij in werking treedt wanneer dat niet zou moeten. Tests dekken elke vorm uit de gevalanalyse van §3.2:

• eenvoudige onbegrensde variabele (A+) — de canonieke N-naar-1-reductie;
• vaste-lengte-groepen ((A B)+, (A B{2})+, drielaags genest ((A (B C){2}){2})+);
• voorloopende onbegrensde variabele met een vast suffix (A+ B) — alleen de voorloopende A+ draagt absorptievlaggen, het suffix niet;
• per-tak-absorptie binnen een alternatie (B+ C | B+ D);
• meerdere onbegrensde variabelen (A+ B+) — alleen de voorloopende is absorbeerbaar;
• reluctante kwantoren (A+?) — geverifieerd te zijn uitgesloten van absorptie;
• niet-voorloopende onbegrensd (A B+) — geverifieerd te zijn uitgesloten.

Naast absorptie dekt de suite de contextlevenscyclus: overlappende contexten onder AFTER MATCH SKIP TO NEXT ROW, opruimen van mislukte contexten gedurende de stroom, finalisatie aan partitie-einde van onvolledige contexten, en contexten die worden aangetroffen nadat een kandidaatmatch reeds in de kopcontext is geregistreerd. Elk hiervan komt overeen met een specifieke snoeiregel in §3.6, en de tests zijn zo geschreven dat ze luid falen als de regel misvuurt (hetzij door overbodige contexten in leven te laten, hetzij door een context te doden die uitvoer had moeten produceren).

4.4 rpr_explain — uitvoerstabiliteit

EXPLAIN-uitvoer is onderdeel van het naar de gebruiker gerichte contract — third-party-tools (psql-autocompletie, monitoringdashboards, log-scrapers) parseren het, en wijzigingen die cosmetisch lijken kunnen ze breken. De rpr_explain-suite verifieert drie dingen:

• NFA-tellers verschijnen op de juiste plaats — de per-WindowAgg-statistieken (peak/total/merged states, peak/total/pruned contexts, lengtehistogrammen voor matched/mismatched/absorbed/skipped, Nav Mark Lookback, en — wanneer matchstart-relatieve navigatie in gebruik is — Nav Mark Lookahead) verschijnen alle onder EXPLAIN ANALYZE met de gedocumenteerde labels.
• Patronen worden correct gedeparset — elke kwantorvorm, inclusief reluctante varianten en begrensde vormen; elke alternatie; elke groep; elke AFTER MATCH SKIP-vorm; INITIAL; navigatieaanroepen met offsets; samengestelde navigatie. De gedeparsete tekst moet ongewijzigd terug kunnen door de parser.
• Identifier-quoting is correct — patroonvariabelen en DEFINE-expressies worden afgegeven met dezelfde quoting-regels als gewone SQL-identifiers, zodat ongebruikelijke variabelenamen pg_dump-uitvoer niet breken.

Net als rpr_base laat deze suite haar objecten aan het einde van de run opzettelijk staan, zodat pg_dump- en pg_upgrade-dekking zich ook uitstrekt tot de explain-zijdige artefacten.

4.5 rpr_integration — plannerinteracties

De planner van PostgreSQL kent vele optimalisaties die op window-queries opereren — framecanonicalisatie, run-condition-pushdown, deduplicatie van identieke windows, projectie van ongebruikte uitvoer, inverse transities voor moving-aggregates — en elk daarvan is ontworpen zonder RPR in gedachten. De meeste zijn onveilig om toe te passen wanneer een window een PATTERN-clausule heeft: het frame maakt deel uit van het matchcontract, de gematchte uitvoer is op geen voor de hand liggende wijze meer monotoon, en twee windows met dezelfde spec maar verschillende DEFINEs leveren werkelijk verschillende resultaten op. De integratiesuite verifieert dat elk van deze optimalisaties correct wordt uitgeschakeld of omzeild voor RPR-windows:

Framecanonicalisatie

De planner herschrijft normaal ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING tot ROWS UNBOUNDED PRECEDING voor monotone aggregaten. Het frame van RPR is de matchspanne, geen aggregatievenster, en moet woordelijk blijven.

Run-condition-pushdown

Een monotoon WHERE-filter op de uitvoer van een window-functie kan normaal als stopconditie in de window-operator worden geduwd. Voor RPR zou dit patroonmatching voortijdig beëindigen, mogelijk matches in midden-uitbreiding afkappend.

Window-deduplicatie (RPR vs niet-RPR)

Twee windows met identieke ORDER BY en frame zouden normaal worden samengevoegd. Een RPR-window en een niet-RPR-window kunnen nooit toestand delen omdat de RPR-zijde matchresultaten draagt.

Window-deduplicatie (verschillende DEFINE)

Twee RPR-windows met dezelfde PATTERN maar verschillende DEFINE-clausules produceren verschillende matches en moeten onderscheiden blijven, ook al is hun structurele vorm identiek.

Projectie van ongebruikte uitvoer

Zelfs als de omringende query de per-rij-uitvoer van het window nooit leest, kan het RPR-window niet worden verwijderd: de bijwerkingen van de pattern matcher (welke rijen binnen welke match vallen) voeden gereduceerd-frame-berekeningen elders in het plan.

Inverse transities voor moving-aggregates

Window-aggregaten met een inverse transitiefunctie kunnen normaal incrementeel worden geëvalueerd terwijl het frame beweegt. Het gereduceerde frame van RPR is geen schuivend venster; het inverse-transitiepad zou verkeerde resultaten produceren.

Het patroon over deze tests is hetzelfde: elke biedt een niet-RPR-baseline die de optimalisatie activeert (en verifieert dat EXPLAIN toont dat deze wordt toegepast), en voert vervolgens een RPR-query van structureel vergelijkbare vorm uit en verifieert dat de optimalisatie niet wordt toegepast. De twee helften samen bewijzen dat de bewaking in de planner echt werk verricht, en niet elke query zonder echte verificatie goedkeurt.

Deze suite is ook de reden dat §3.4 kort is. De mechanismen voor "matchgrenzen" — gereduceerd frame, SKIP, INITIAL, begrensd-frame-afkapping — worden elders operationeel getest; wat rpr_integration verifieert is dat geen enkele andere optimizer-stap er onderweg mee knoeit. Een geslaagde rpr_integration is wat de overige suites in staat stelt erop te vertrouwen dat hun inputs ongeschonden de executor bereiken.