Row Pattern Recognition Diepgaande Verkenning
Een rondleiding door ISO/IEC 19075-5 · SQL R020 in PostgreSQL — wat is gebouwd, wat nog niet is geschreven, en hoe het daadwerkelijk wordt uitgevoerd.
Doorblader de standaard, doorloop uitgewerkte voorbeelden, bekijk het ontwerp, en bestuur vervolgens een live NFA-simulator met eigen patronen.
Discussie: pgsql-hackers thread · nieuwste patch (v55) · commitfest #4460.
AI-voorvertaald — fouten mogelijk.
§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 hebben aanzienlijk veel syntaxis en semantiek gemeen (19075-5 noemt in §6.3.3 enkele R020-specifieke verschillen), 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 clausules toe te voegen aan een window-specificatie waarvan het frame ROWS BETWEEN CURRENT ROW AND … is: PATTERN beschrijft een reguliere expressie over benoemde patroonvariabelen, DEFINE levert het Booleaanse predicaat dat elke variabele identificeert, en de optionele AFTER MATCH SKIP (standaard PAST LAST ROW) 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; maximaal 240 verschillende patroonvariabelen.
- Window-frame
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGofROWS BETWEEN CURRENT ROW ANDnFOLLOWINGmet n ≥ 1 (19075-5 §6.10.2); elk ander frame wordt afgewezen, enEXCLUDE NO OTHERSis de enige geaccepteerde uitsluiting.- 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. kalePrice) 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 wordt op de genavigeerde rij 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. - Navigatienamen
PREV,NEXT,FIRSTenLASTdie als ongekwalificeerde aanroepen binnenDEFINEworden geschreven, betekenen altijd navigatie; een gebruikersfunctie met dezelfde naam moet daar schema-gekwalificeerd worden.- Navigatieargumenten
- Voor
PREV,NEXT,FIRSTenLASTmoet het binnenste argument ten minste één kolomverwijzing bevatten en moet de offset een runtime-constante zijn. - 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 FIRST var en AFTER MATCH SKIP TO [LAST] var (een kale SKIP TO var betekent SKIP TO LAST var). Ook deze zijn afhankelijk van match-historie, aangezien de executor in staat moet zijn de rij aan te wijzen die binnen de meest recente match aan een gegeven variabele is toegewezen.
De overige items vormen een heterogene staart: het sleutelwoord SEEK (het alternatief voor INITIAL), het lege patroon (), de uitsluitingsvorm {- … -}, de volgorde-onafhankelijke PERMUTE-operator, en aggregaatfuncties en subquery's in DEFINE, die beide momenteel worden afgewezen (een variabelegekwalificeerd aggregaat zou ook de match-historie nodig hebben).
- MEASURES
- Benoemde per-match-uitvoer-uitdrukkingen, bijv.
MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; in R020 ontsloten viaOVERzoals 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 inDEFINE,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.priceinDEFINEofMEASURES— 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 op elke rij beginnen vanaf de huidige rij tot het einde van het volledige window-frame (vs. INITIAL).
- 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
ALL ROWS PER MATCH-uitvoer. Die optie is niet van toepassing op windows (19075-5 §6.3.3 (4)), dus in een window is de syntaxis toegestaan (§6.13), maar is er geen uitvoer waarop deze kan inwerken. - Regex: ()
- Leeg patroon — matcht de lege reeks.
- PERMUTE(...)
- Volgorde-onafhankelijke matching over opgesomde variabelen. Het sleutelwoord wordt herkend en afgewezen ("PERMUTE is not supported");
permuteblijft bruikbaar als naam van een patroonvariabele. - Aggregaatfuncties in DEFINE
- Aggregaten zoals
SUM,AVG,COUNTzijn niet toegestaan inDEFINE-predicaten. De standaard staat ze toe als running-aggregaten over de gedeeltelijke match; een variabelegekwalificeerd aggregaat zoalsAVG(B.Price)is afhankelijk van dezelfde per-match-historie dieMEASURES/CLASSIFIER()vereisen, terwijl een ongekwalificeerd aggregaat over alle rijen van de match tot dusver loopt. - Subquery's in DEFINE
- Elke subquery in
DEFINEwordt afgewezen. De standaard staat er een toe die geen row pattern recognition uitvoert en naar geen enkele rijpatroonvariabele verwijst; de patch wijst voorlopig te veel af.
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 (de patch gaat verder en wijst alle subquery's in DEFINE af, zoals hierboven vermeld); en RPR mag niet binnen een recursieve query worden gebruikt. De patch handhaaft de regel voor externe verwijzingen ("cannot use outer query column in DEFINE clause") en de recursieregel, de laatste voor elk element van een WITH RECURSIVE-clausule. Ook wijst de patch volatile functies en verwijzingen naar de hele rij in DEFINE af.
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 vijf uitgewerkte voorbeelden door: een enkele match (NFA-beweging), alternatie, contextabsorptie in het eenvoudige geval, en twee gevallen waarin absorptie is uitgeschakeld.
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 (standaard n = 1). Voorwaartse look-ahead; ongebruikelijk in window-vorm omdat het window monotoon is.
- FIRST(expr [, n])
- De rij n rijen na de eerste rij van de huidige match (standaard n = 0, de eerste rij zelf). "Vergelijk met de rij die deze match startte."
- LAST(expr [, n])
- De rij n rijen vóór de laatste gematchte rij (standaard n = 0). Binnen
DEFINEis de laatste gematchte rij de huidige rij, dusLAST(price)leest de huidige 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 rij die
FIRST(expr, n)leest (standaard n = 0, m = 1). "Wat was de waarde vlak voordat deze match begon?" - NEXT(FIRST(expr [, n]) [, m])
- Stap m rijen vooruit vanaf de rij die
FIRST(expr, n)leest. Reikt verder in de match zonder afhankelijk te zijn van de huidige rij. - PREV(LAST(expr [, n]) [, m])
- Stap m rijen terug vanaf de rij die
LAST(expr, n)leest. "Vergelijk met een rij kort vóór de meest recent gematchte rij." - NEXT(LAST(expr [, n]) [, m])
- Stap m rijen vooruit vanaf de rij die
LAST(expr, n)leest.
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. Gewone PREV en NEXT zijn relatief ten opzichte van de huidige rij en zijn altijd veilig; FIRST en offset-varianten van LAST, alleen of binnen een samengestelde PREV/NEXT, zijn relatief ten opzichte van de matchgrenzen, wat in wisselwerking staat met contextabsorptie: de planner schakelt absorptie dan voor het hele patroon uit. Het mechanisme achter die wisselwerking is het onderwerp van §2.6.
2.3 Uitgewerkt voorbeeld 1 — NFA-beweging
SKIP PAST LAST ROW verworpen zodra de match ervan is geregistreerd.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:
| Rij | Prijs | Ware vars | Actie |
|---|---|---|---|
| 0 | 100 | START | Nieuwe context. START matcht en verlaat onmiddellijk (max=1); toestand gaat verder naar UP+. |
| 1 | 110 | START, UP | UP matcht. Voortgang vorkt: één toestand blijft in UP loopen, een andere verlaat naar DOWN+. |
| 2 | 120 | START, UP | UP matcht in de loopende toestand en vorkt opnieuw. De DOWN-toestand van rij 1 sterft (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP faalt in de loopende toestand en sterft. De DOWN-toestand van rij 2 matcht. Voortgang vorkt: loop op DOWN, en verlaat naar #FIN — een matchkandidaat over rijen 0–3 wordt geregistreerd. |
| 4 | 108 | START, DOWN | DOWN matcht in de loopende toestand en vorkt opnieuw; de nieuwe FIN-kandidaat over rijen 0–4 vervangt de kortere. |
| 5 | 130 | START, UP | De loopende DOWN-toestand faalt (130 ≮ 108). Nu er in deze context geen actieve toestand meer over is, wordt de geregistreerde kandidaat (rijen 0–4) als match gefinaliseerd. De volgende poging begint bij rij 5; START matcht, maar de partitie eindigt vóór enige UP. |
Het kernpunt: op rij 3 voldoet de rij aan zowel START (altijd waar) als DOWN, maar START is alleen van belang voor een context die op rij 3 begint; in deze context sterft de loopende UP-toestand en gaat alleen de toestand die op DOWN+ wacht verder. 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 laatste FIN-kandidaat (rijen 0–4) — geproduceerd toen DOWN bij rij 4 verliet, ter vervanging van de kandidaat van rij 3 — 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 | Prijs | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
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 patroonvolgorde verkent, de eerdere tak eerst.
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. Beide gaan vervolgens verder naar DONE, waar ze samenkomen.
| Rij | Ware vars | Actieve toestanden |
|---|---|---|
| R | UP, HIGH | Toestand A (UP-tak) en Toestand B (HIGH-tak) gaan beide verder naar DONE met dezelfde tellers; B is een duplicaat van A en wordt verworpen |
| R+1 | DONE | Toestand A matcht DONE en bereikt #FIN |
In termen van de standaard produceren beide takken een match van dezelfde lengte over dezelfde rijen, wat twee kandidaatspaden oplevert — éé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. De executor dwingt dit af op rij R, niet bij FIN: hij voegt de toestand van de UP-tak als eerste toe, dus nfa_append_state_unique() behoudt die en laat de identieke toestand van de HIGH-tak vallen.
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):
| Rij | Naïeve contexten | Met absorptie |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 geabsorbeerd |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | vijf contexten | C1[A:5] |
Het aantal actieve contexten daalt van O(n) naar O(1), zodat het totaal over de partitie daalt van O(n²) naar O(n). 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:
| Dag | Prijs | C1 — Di start price > PREV(price) | C2 — Wo start price > PREV(price) |
|---|---|---|---|
| Ma | $100 | — | — |
| Di | $108 | $108 > $100 ✓ (zojuist gestart) | — |
| Wo | $112 | $112 > $108 ✓ | $112 > $108 ✓ (zojuist gestart) |
| Do | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| Vr | $110 | $110 > $116 ✗ — finaliseren | $110 > $116 ✗ — finaliseren |
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
DEFINE naar FIRST verwijst — de absorptieregel geldt niet meer, en de planner schakelt absorptie voor het patroon uit.
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).
| Dag | Prijs | C1 — Ma start FIRST = $100 price < $100 + 10 | C2 — Di start FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| Ma | $100 | $100 < $110 ✓ | — |
| Di | $108 | $108 < $110 ✓ | $108 < $118 ✓ (zojuist gestart) |
| Wo | $112 | $112 < $110 ✗ — finaliseer Ma–Di | $112 < $118 ✓ |
| Do | $116 | — | $116 < $118 ✓ |
| Vr | $110 | — | $110 < $118 ✓ (loopt nog) |
Onder absorptie zou C2 op dinsdag in C1 zijn samengevoegd — de samengevoegde context behoudt alleen het plafond van C1 ($110), dus de eigen kijk van C2 (plafond $118, een vierdaagse reeks tot en met vrijdag) wordt niet gedekt door de toekomst van C1. In deze specifieke week verandert de uitvoer toevallig niet: C1 registreert Ma–Di, C2 is binnen die match gestart en wordt door SKIP PAST LAST ROW verworpen, en de volgende poging begint op woensdag met een eigen plafond ($122) en matcht Wo–Vr. In het algemeen omvat het DEFINE-resultaat van een eerdere context echter niet langer dat van een latere, zodat de tellervergelijking waarop absorptie steunt ongeldig is. 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 onderstaande tabel breidt het paneel rechtsonder van de poster ("② Navigation") uit met de samengestelde vormen en vat samen welke navigatievormen matchstart-afhankelijkheid creëren:
| Navigatie | Matchstart-afh. | Absorbeerbaar? |
|---|---|---|
| PREV, NEXT | geen | ja |
| LAST (zonder offset) | geen | ja |
| LAST met offset | grenscontrole | nee |
| FIRST (elke) | direct | nee |
| Samengesteld (binnenste FIRST) | direct | nee |
| Samengesteld (binnenste LAST, zonder offset) | geen | ja |
| Samengesteld (binnenste LAST met offset) | grenscontrole | nee |
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 waarvan niet gegarandeerd is dat een andere context die dekt, zodat het verwerpen van een ervan niet langer als veilig kan worden aangetoond.
De planner detecteert dit onderscheid bij compilatie en schakelt absorptie voor het hele patroon in of uit; wanneer het uit staat, betaalt de runtime de multi-contextkosten. De benchmark op de poster in paneel ③ gebruikt geen FIRST, dus absorptie blijft aan, en daarom blijft PostgreSQL zowel in het succes- als in het faalgeval lineair.
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 ruwweg O(n) zodra een match is bevestigd, en PostgreSQL heeft een voorsprong van ruwweg 16× tot 33× (de cijfers van Trino sluiten de JVM-opstart al uit).
Op het faalpatroon (A+ B+ C+ E) jaagt Trino, dat absorptie lijkt te missen, elke potentiële matchstart na en degradeert zelfs sneller dan O(n²) (ongeveer 56× de tijd voor 5× de rijen); 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.
| Rij | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | match begint; rijen 0–4 worden de enige match | match begint op rij 0 |
| 1 | (binnen match 0) | match begint op rij 1 — moet in leven worden gehouden |
| 2 | (binnen match 0) | match begint op rij 2 — moet in leven worden gehouden |
| 3 | (binnen match 0) | match begint op rij 3 — moet in leven worden gehouden |
| 4 | match 0 finaliseert (rijen 0–4) | vijf matches finaliseren: 0–4, 1–4, 2–4, 3–4, 4–4 |
AFTER MATCH SKIP TO NEXT ROW is elke laat-startende context een eigen uitvoerrij. Twee contexten op hetzelfde patroonelement zijn niet langer overbodig — ze zijn beide vereiste uitvoer, en het verwerpen van een ervan zou stilzwijgend een match laten vallen die de gebruiker heeft opgevraagd.
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 de twee manieren waarop de semantiek van een query absorptie uitsluit:
FIRST of offsetdragende LAST in DEFINE.AFTER MATCH SKIP TO NEXT ROW.
Eén van beide condities volstaat om absorptie voor het hele patroon uit te schakelen, en dat geldt ook voor een frame dat niet op UNBOUNDED FOLLOWING eindigt. Wanneer geen ervan van kracht is — de standaard AFTER MATCH SKIP PAST LAST ROW, een onbegrensd frame-einde, en DEFINE-condities die uitsluitend PREV, NEXT of een onversierde LAST gebruiken — is absorptie ingeschakeld, maar alleen voor toestanden in het absorbeerbare gebied van het patroon: een voorloopende gulzige onbegrensde variabele zoals A+ of A*, een groep met vaste lengte met een onbegrensde gulzige kwantor zoals (A B)+, een gulzige groep waarvan het lichaam met een van deze begint zoals (A+ B)+ of (A+ B){2}, of alternatietakken die daaruit zijn opgebouwd; een reluctante groep diskwalificeert zijn hele subboom. Waar dat geldt, zoals voor A+ in §2.5, reduceert de runtime tot één enkele context en blijft lineair; START UP+ DOWN+ uit §2.3 krijgt helemaal geen absorbeerbaar gebied.
§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²)-werk 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, de eindgrens moet UNBOUNDED FOLLOWING of een positieve offset FOLLOWING zijn (dus ook een standaardframe wordt afgewezen), en andere EXCLUDE-opties dan EXCLUDE NO OTHERS 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:
| Bron | Boomcodering |
|---|---|
| A | VAR(A, min=1, max=1) |
| A+ | VAR(A, min=1, max=∞) |
| A* | VAR(A, min=0, max=∞) |
| A{3,5} | VAR(A, min=3, max=5) |
| A+? | VAR(A, min=1, max=∞, reluctant=true) |
Elk DEFINE-predicaat wordt vervolgens getypecheckt tegen de kolommen van de partitie en gecoerced tot een Booleaanse expressie. Daaruit volgen twee praktische zaken. Ten eerste voegt de parse-analyse voor DEFINE niets toe aan de target list van de query; in plaats daarvan markeert de planner elke kolom waarnaar een DEFINE-predicaat verwijst als nodig, zoals bij HAVING, en geeft die kolommen door 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 negen herschrijfregels toe in één enkele bottom-up-pass (binnen een reeks draait de groepssamenvoeging nog één keer, omdat eerdere samenvoegingen twee identieke groepen naast elkaar kunnen brengen):
- 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-samenvoeging
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 - Normalisatie van reluctantie
A{2}?→A{2}(reluctantie wordt gewist overal waar min = max)
Kwantorvermenigvuldiging voegt alleen samen wanneer de haalbare tellingen één aaneengesloten interval vormen en de geprefereerde match niet verschuift: een exacte buitenste ((A{2,3}){5} → A{10,15}), een kind met min 0, of kind-intervallen die op elkaar aansluiten met een kind-min van hooguit 1 of een onbegrensde kind-max ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), waarbij een buitenste met min 0 ook een kind-min van hooguit 1 nodig heeft ((A{2,})* blijft, aangezien A* één rij zou accepteren). Een groepskind waarvan de eigen kwantor niet exact is, moet eerst een lichaam met vaste lengte hebben, dus ((A | B B){1,2}){2} blijft intact, zelfs onder een exacte buitenste. 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 — of de geprefereerde match verschuiven ((A{2,3}){1,2} prefereert drie rijen waar A{2,6} er vier neemt), dus laat de optimizer ze intact. Het is niet de enige afgeschermde herschrijving: groepssamenvoeging en de suffix-samenvoeging vereisen een lichaam dat een vast aantal rijen consumeert, de prefix-samenvoeging weigert een groep met min 0, een eindige max en nullable inhoud, reluctante knopen worden niet samengevoegd of vermenigvuldigd ((A+?)+ blijft), en een herschrijving waarvan de nieuwe grens zou overlopen wordt geweigerd.
Elementvorm
Elk element van de vlakke array vertegenwoordigt één positie in het patroon. Er zijn zes 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; een takscheidingsteken dat elke tak afsluit; 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 de alternatiemarker en de takscheidingstekens om takken aan elkaar te koppelen, door groepsbegin om zijn eigen groepseinde aan te wijzen — een groep waarvan de kwantor nul toestaat wordt overgeslagen via de next van dat einde — 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 → 3
(opent groep; jump wijst
zijn eigen END aan)
[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 wijst de jump van BEGIN zijn END bij idx 3 aan, en indien de groep optioneel was zou de sprong via de next van die END naar idx 4 vertrekken zonder bij de END aan te komen. 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 vijf 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? B?)+,(A | B*)+;(A?)*wordt eerst vermenigvuldigd totA*en laat geen groepseinde achter). Vertelt de runtime om onder min 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. - Empty-preferred
- Ingesteld op groepseindes waarvan het lichaam de lege match prefereert, zoals in
(A?? B??){2}. Plaatst de fast-forward-exit onder min vóór de loop-back, waar de eigen gulzigheid van de groep niets zegt. - 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 vlakke array vanaf
element 0 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 doorloop vier structurele vormen toe:
- Geval 1 — Eenvoudige onbegrensde variabele
-
Elke iteratie is precies één rij. De teller van een eerdere context is altijd ≥ die van een latere op elke gedeelde positie.
A+,A*,A{2,∞} - Geval 2 — Groep met vaste lengte, onbegrensd buitenste
-
Elk kind heeft
(A B)+,(A B{2})+,((A (B C){2}){2})+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
-
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 krijgt A beide vlaggen, krijgt de omsluitende BEGIN de in-region-vlag, en krijgen B en END geen.
(A+ B)+,(A+ B){2} - Geval 4 — Alternatie
-
Elke tak, bereikt via de keten van scheidingstekens, wordt afzonderlijk beoordeeld volgens de bovenstaande gevallen; de alternatiemarker krijgt de in-region-vlag wanneer een tak in aanmerking komt.
A+ | B+,A+ | C D
De structurele gevallen die niet door deze vier 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. 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
if targetPos != currentPos:
haal rij op positie targetPos op
in nav_slot
laat buitenste slot naar nav_slot wijzen
result = eval_inner_expression()
herstel current_row_slot
kopieer by-ref-resultaat uit nav_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 en geen slot per verwijzing; wanneer het doel de huidige rij is, worden het ophalen en de swap helemaal overgeslagen. Het ophalen kopieert de doelrij naar de navigatieslot (tenzij de slot die al bevat), en de herstelstap kopieert een pass-by-reference-resultaat naar per-tuple-geheugen, zodat de volgende ophaalactie het niet kan vrijgeven.
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 currentPos − 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 (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − 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 contextabsorptie überhaupt mogelijk is (§2.5 vs §2.6): één enkele matchstart-afhankelijke variabele schakelt deze voor het hele patroon uit.
- Geen navigatie
- Uitsluitend
PREV/NEXT LASTzonder offset- Samengesteld met binnenste
LAST(zonder offset)
LASTmet offsetFIRST(elke vorm)- Samengesteld met binnenste
FIRST - Samengesteld met binnenste
LAST(met offset)
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 executor bepaalt dit op basis van twee complementaire offsets, waarbij elke offset eenmaal per scan wordt opgelost (constante ook bij executor-init, zodat gewone EXPLAIN ze kan tonen):
- Lookback-budget
- Hoe ver achterwaarts vanaf de huidige rij elke DEFINE-aanroep zou kunnen reiken.
- Lookahead-vanaf-start-budget
- Het minimale voorwaartse bereik (achterwaarts, indien negatief) vanaf het matchbegin van de oudste actieve context — de vroegste rij die een DEFINE-aanroep nodig zou kunnen hebben.
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 Nav Mark-regels die EXPLAIN rapporteert (§3.7) — Lookback en Lookahead — zijn deze twee budgetten, geen gemeten pieken. Elk wordt alleen afgedrukt wanneer een navigatie het voedt en wordt ook zonder ANALYZE getoond; een offset waarvan de waarde pas tijdens runtime bekend is (bijvoorbeeld een parameter van een generic plan) wordt onder gewone EXPLAIN als runtime afgedrukt en onder EXPLAIN ANALYZE als zijn opgeloste waarde, en retain all (Lookback) of infinite (Lookahead) markeert een offset die overloopt.
3.4 Matchgrenzen — SKIP, INITIAL, en begrensd frame
Een matchresultaat wordt opgeslagen als twee waarden: de rij waarop de match begint, en de lengte ervan. Een negatieve start betekent dat de positie nog niet is geëvalueerd; zodra de start is ingesteld, kunnen daaropvolgende vragen aan de executor — "valt deze rij binnen een match?" — in O(1) worden beantwoord door het paar te inspecteren. De lengte codeert de uitkomst: -1 voor een niet-gematchte rij, 0 voor een lege match, en het aantal rijen voor een echte match. 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 zowel een niet-gematchte rij als "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 de start van de match, waardoor overlappende matches mogelijk worden; de planner schakelt daarom absorptie voor het patroon van dat window 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 en stuurt vervolgens de NFA rij voor rij vooruit — waarbij voor elke rij een matcharray per variabele op "niet geëvalueerd" wordt teruggezet — totdat die context geen actieve toestanden meer heeft of de partitie eindigt. DEFINE-predicaten worden lui geëvalueerd: een variabele wordt geëvalueerd de eerste keer dat een toestand haar consumeert, dus een variabele die geen enkele actieve toestand op deze rij test, wordt nooit geëvalueerd. 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 zijn frame-einde bereikte:
forceer mismatch (vroegtijdig finaliseren)
continue
als matchStartRow afwijkt van
de gedeelde evaluatiepositie:
zet matchstart-afhankelijke
DEFINE-vars terug op niet geëvalueerd (§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)
als het een match registreerde en
SKIP PAST LAST ROW:
snoei latere contexten die
binnen de match starten
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]
assert elem is een variabele
# advance parkeert alleen variabelen
als varMatched[elem.varId]
niet geëvalueerd is:
evalueer nu zijn DEFINE
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
of een geregistreerde match bevat:
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) totdat de context een match registreert, wat de vlag vastzet op onwaar — absorberen zou een match vrijgeven die geen absorberende context kan reproduceren. 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-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, stoppend
zodra FIN is geregistreerd),
BEGIN (groep binnengaan; plus optioneel
overslagpad als min = 0),
END (terug lussen / verlaten / fast-forward —
zie hieronder),
FIN (registreer matchEndRow,
bewaar matchedState, en markeer
de context zodat latere contexten
binnen het bereik van deze kandidaat
worden gesnoeid — 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 Advance klaar is met de context die een kandidaat registreerde, wordt elke daaropvolgende context waarvan de startrij binnen het bereik van de kandidaat valt op dezelfde rij 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 de context-overschrijdende FIN-tijd-snoeistap. Binnen de context snijdt FIN ook lexicaal-inferieur werk af: Advance laat de resterende toestanden in de wachtrij vallen (eerder in deze sectie beschreven), en binnen één DFS stopt elk minder geprefereerd pad — latere ALT-takken, het andere van de overslag- en binnengaanpaden van BEGIN, het binnengaanpad van een reluctante variabele, het andere van de lus- en exitpaden van END — zodra een match is geregistreerd, zodat één advance hooguit één match registreert.
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
(fast-forward eerst als het
lichaam leeg prefereert; het
tweede pad vervalt als het
eerste FIN bereikte)
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
als lus FIN bereikte:
verwerp de exit
# voorkeur langer
else exit als tweede
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? B?)+ en (A | B*)+ hebben deze eigenschap: afhankelijk van de data kan het lichaam een iteratie voltooien zonder ook maar één rij te consumeren. (Eén enkel optioneel kind zoals (A?)* wordt tijdens compilatie herschreven tot A* en laat geen groep achter.) 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 in het lichaam (zijn jump is het eerste kind van de groep), het lichaam produceert opnieuw een lege match, bereikt END opnieuw, enzovoort. Zonder iets om het te stoppen zou de DFS van Advance nooit eindigen.
De bewaker 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. De runtime houdt een visited-bitmap bij, gewist vóór elke DFS-uitbreiding van een toestand, waarin alleen die getagde END's worden gemarkeerd — niets anders kan een cyclus vormen, omdat elke andere loop-back een rij heeft geconsumeerd. Het bereiken van een gemarkeerde END betekent dat het lichaam zojuist een lege iteratie heeft afgeleid, en de toestand wordt niet verworpen: op of boven de ondergrens verlaat hij daar de groep (een lege iteratie stopt de kwantor), en eronder valt de toestand door naar de normale loop-back, zodat elke lege aankomst de teller nog verhoogt totdat deze min bereikt. Neem (A? B?){2,3} zonder dat ergens in de rijenstroom een van beide variabelen matcht:
iter 1: A? B? matchen nul rijen
→ END, count = 1 (onder min)
END reeds gemarkeerd (bij
binnengaan groep), maar onder min:
→ terug lussen in A?
iter 2: A? B? matchen nul rijen
→ END, count = 2 (haalt min)
END reeds gemarkeerd, op min:
→ verlaat de groep
afsluiten met een nullengte-match
Onder de ondergrens vertelt de empty-loop-tag de END-handler ook om een aanvullende fast-forward-toestand te klonen naast het normale loop-back-pad:
advance_end (count onder min):
loop-back-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 loop-back vangt het geval op waarin het lichaam nog later echte matches kan produceren — bijvoorbeeld bij (A? B?){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 verlaat de groep onmiddellijk, verklaart "de rest van de vereiste iteraties zijn leeg", en laat de match slagen met een lichaam van lengte nul. Het lichaam, niet de eigen gulzigheid van de groep, bepaalt de volgorde: de fast-forward gaat precies dan eerst wanneer het lichaam de lege match prefereert (een reluctant lichaam zoals (A?? B??)), en als het eerste pad FIN bereikt, vervalt het tweede, zodat een minder geprefereerd pad de geprefereerde match niet kan vervangen. 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
Het begrensd houden 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 op een vergelijkingspunt staat en wordt gedekt door een absorbeerbare toestand van een oudere context op hetzelfde element met een grotere of gelijke 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) Advance
- 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 ROWkan elke context binnen het bereik van de kandidaat geen rapporteerbare uitvoer meer produceren, ongeacht hoe die zoektocht eindigt, en wordt gesnoeid zodra Advance klaar is met de context die de kandidaat registreerde. - Cyclusbewaker Advance
- Epsilon-uitbreidingen die de END van een nullable groep bereiken die binnen dezelfde DFS al is gemarkeerd (gemarkeerd bij binnengaan via BEGIN, of bij een eerdere aankomst) — zouden anders eeuwig lussen; de toestand verlaat daar de groep op of boven de ondergrens, en blijft eronder lussen.
- Empty-loop fast-forward Advance
- Onder de ondergrens van een nullable groep, een extra pad dat de groep verlaat met de resterende vereiste iteraties verklaard als leeg, ten opzichte van de loop-back geordend volgens de voorkeur van het lichaam.
- 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). 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 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. De broncode documenteert gevallen die de lagen niet opvangen: dedup houdt toestanden die alleen verschillen in tellers boven min gescheiden, dus (A{2,} B)+ C waarbij C nooit waar is, bevat op de piek Θ(n²) toestanden en creëert er Θ(n³) (37 s over 320 rijen), en een reeks volledig nullable alternaties wordt pad voor pad opgesomd, dus (A?|B?){30} duurt meer dan een half uur.
3.7 EXPLAIN-uitvoer
EXPLAIN ANALYZE op een query met RPR onthult NFA-niveau-statistieken die voor gewone window-functies niet aanwezig zijn. In tekstformaat worden ze naast de window-operator afgegeven, na de Pattern:-regel, eventuele Nav Mark-regels (die ook gewone EXPLAIN toont) en de Storage:-regel:
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(elk alleen wanneer DEFINE navigatie
gebruikt die het voedt)
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)
(tweede NFA-regel alleen wanneer een
van beide tellingen niet nul is; een
telling nul wordt zonder (len ...) afgedrukt)
Niet-tekstformaten geven elke telling als eigen property af. 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; pruned telt contexten die na één enkele rij faalden. De matchlengtehistogrammen scheiden vier uitkomsten — succesvolle matches, matchpogingen die na meer dan één rij faalden (mismatched), geabsorbeerde contexten, en contexten die door AFTER MATCH SKIP PAST LAST ROW werden vrijgegeven omdat ze binnen een geregistreerde match begonnen (skipped) — 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 uit DEFINE afleidt. Lookback is de diepste achterwaartse reikwijdte vanaf de huidige rij over PREV, LAST met elke offset (inclusief de standaard 0), en de samengestelde vormen met binnenste LAST; Lookahead is de minimale voorwaartse reikwijdte (negatief wanneer deze vóór het matchbegin kijkt) 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 pas per scan bekend is, en — alleen voor Lookback — "retain all" wanneer de offset overloopt; een Lookahead die overloopt wordt als "infinite" afgedrukt. Elke regel wordt alleen afgegeven wanneer een navigatie in DEFINE deze voedt, en beide verschijnen ook onder gewone EXPLAIN: constante offsets worden bij executor-init vastgelegd, terwijl een offset die pas tijdens runtime bekend is (bijvoorbeeld een parameter van een generic plan) daar "runtime" afdrukt en onder EXPLAIN ANALYZE zijn opgeloste geheel getal.
Samen maken deze tellers het mogelijk om RPR-prestaties te debuggen zonder gdb aan de backend te koppelen.
Naast de tellers drukt EXPLAIN een Pattern:-regel af die is opgebouwd uit de gecompileerde elementarray, zodat deze het patroon na de compile-time-herschrijvingen toont (PATTERN (A A) wordt verklaard als a{2}) en de absorptiemarkers # (vergelijkingspunt) en ~ (absorbeerbaar gebied) draagt; DEFINE en de AFTER MATCH SKIP-optie worden niet getoond. Het reproduceren van de clausules zoals geschreven, inclusief reluctante kwantoren, groepsherhaling en de skip-optie, is de taak van pg_get_viewdef(), dat aanzienlijke moeite doet 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 22.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
- Integratie met de WINDOW-clausule — realistische window-scenario's op synthetische aandelendata (V-vorm, W-vorm, opeenvolgende stijgingen, omkeringen), plus navigatiesemantiek en fouten bij DEFINE-beperkingen.
- rpr_base
- Parserlaag — sleutelwoordacceptatie, syntaxisvormen, kwantoren, navigatieparsing, foutmeldingen, en pg_dump/pg_upgrade round-trip-stabiliteit; plus een plannerlaag — patroonoptimalisatie, absorptievlaggen, optimalisatie-fallback, plannerintegratie.
- 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. Deze scenario's zijn de enige tests waarvan de inputs en outputs lezen als queries die een gebruiker werkelijk zou kunnen schrijven; de rest van het bestand is, net als de andere suites, reductief — nesting van PREV/NEXT en fouten bij niet-constante offsets, DEFINE-verwijzingsregels, en semantiek van navigatie-offsets.
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. Een tweede deel, de plannerlaag, dekt patroonoptimalisatie, weergave en analyse van absorptievlaggen, optimalisatie-fallback, en plannerintegratie (subquery's, joins, set-operaties, sortering en groepering).
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. Defecten 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: inline VALUES-rijen met een array van variabelenamen die declareert welke DEFINE-variabelen op elke rij matchen, gekoppeld aan een patroon dat een specifiek runtimegedrag onderzoekt. Het 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 voorloopendeA+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 (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) verschijnen onder
EXPLAIN ANALYZEin tekst, JSON en XML met de gedocumenteerde labels, en Nav Mark Lookback en Lookahead verschijnen precies wanneer navigatie in DEFINE ze voedt. - 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 hoe elk van deze optimalisaties met RPR-windows omgaat — de meeste moeten worden uitgeschakeld of omzeild:
- Framecanonicalisatie
- De planner herschrijft normaal
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGtotROWS UNBOUNDED PRECEDINGvoor frame-onafhankelijke window-functies zoalsrow_number,rankenntile. 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 BYen 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 of SKIP)
- Twee RPR-windows met dezelfde
PATTERNmaar verschillendeDEFINE-clausules of een andereAFTER MATCH SKIPproduceren verschillende matches en moeten onderscheiden blijven, ook al is hun structurele vorm identiek. - Projectie van ongebruikte uitvoer
- Deze mag wel worden toegepast: wanneer de omringende query de uitvoer van het window nooit leest, wordt de window-functie NULL en wordt de bijbehorende WindowAgg verwijderd, waarbij het aantal rijen ongewijzigd blijft. De tests controleren dat de kolommen die DEFINE leest de WindowAgg nog bereiken wanneer deze blijft, en dat het window behouden blijft wanneer de waarde ervan wordt gelezen.
- 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.
Verdere gevallen controleren dat de kostenschatting rekening houdt met DEFINE, dat een subquery met een RPR-window niet wordt afgevlakt, dat DEFINE-expressies niet weglekken naar een hogere WindowAgg, en dat LIMIT boven de WindowAgg blijft; een tweede groep voert RPR uit samen met CTE's, joins, set-operaties, prepared statements, gepartitioneerde tabellen en vergelijkbare constructies. De meeste afgeschermde gevallen volgen dezelfde vorm: een baseline die de optimalisatie activeert (meestal een niet-RPR-query, gecontroleerd in EXPLAIN), en vervolgens een RPR-query van structureel vergelijkbare vorm waarbij de optimalisatie niet wordt toegepast — voor het DEFINE/SKIP-dedup-geval is de baseline twee identieke RPR-windows, en het inverse-transitie-geval controleert de omzeiling met een loggend aggregaat in plaats van EXPLAIN. 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.