2026 · Vancouver
Simon Fraser University — Vancouverin kampus

Row Pattern Recognition Syväluotaus

Opastettu kierros ISO/IEC 19075-5 · SQL R020 -toiminnallisuuteen PostgreSQL:ssä — mitä on rakennettu, mitä on vielä kirjoittamatta ja miten se todellisuudessa toimii.

Liite PGConf.dev 2026 -tapahtumassa esiteltävälle posterille.
Selaa standardia, käy läpi käytännön esimerkit, tutustu suunnitteluun ja kokeile sen jälkeen interaktiivista NFA-simulaattoria omilla kuvioilla.
Keskustelu: pgsql-hackers -ketju · uusin korjauspaketti (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

Tekoälyn esikäännös — virheitä mahdollisia.

§1. Standardi, sen osajoukko ja avoimet kysymykset

1.1 Standardin laajuus

Row Pattern Recognition lisättiin SQL-standardiin dokumentilla ISO/IEC 9075-2:2016, ja se kuvataan oheisessa dokumentissa ISO/IEC 19075-5:2021 (Part 5, ”Row Pattern Recognition”).

Standardi määrittelee kaksi rajapintaa samalle taustakoneistolle. Ominaisuus R010 sijoittaa MATCH_RECOGNIZE-lausekkeen FROM-listalle tuottaakseen johdetun taulun; ominaisuus R020 sulauttaa saman kuvio­logiikan WINDOW-määrittelyyn tuottaakseen ikkunafunktion tulosteen. Näillä kahdella rajapinnalla on huomattavasti yhteistä syntaksia ja semantiikkaa (19075-5 mainitsee muutamia R020-kohtaisia eroja kohdassa §6.3.3), mutta ne ovat toiminnallisesti erilliset sisääntulopisteet — tietokanta voi toteuttaa jommankumman tai molemmat.

Tässä käsiteltävä korjauspakettisarja toteuttaa osajoukon vain ominaisuudesta R020; taulu­lauseke­muoto on tietoisesti rajattu työn ulkopuolelle.

R020-rajapinta on pieni mutta ilmaisuvoimainen. Kysely liittää kuvion ikkunaan lisäämällä lausekkeita sellaisen ikkuna­määrittelyn sisään, jonka kehys on ROWS BETWEEN CURRENT ROW AND …: PATTERN kuvaa säännöllisen lausekkeen nimettyjen kuviomuuttujien yli, DEFINE tarjoaa Boolen predikaatin, joka tunnistaa kunkin muuttujan, ja vapaaehtoinen AFTER MATCH SKIP (oletus PAST LAST ROW) ohjaa peräkkäisten osumien sijoittumista partition sisällä.

Vapaaehtoiset MEASURES, SUBSET, INITIAL/SEEK sekä apufunktio CLASSIFIER() täydentävät ominaisuutta. (Standardin MATCH_NUMBER()-funktio kuuluu vain R010-rajapintaan — 19075-5 §6.3.3 (6) nimenomaisesti rajaa sen R020:n ulkopuolelle.)

Korjauspaketti kattaa tästä sanastosta riittävän osan, jotta vaativatkin kyselyt toimivat, mutta jättää käsittelemättä useita rakenteita, joiden toteutus riippuu vielä rakentamatta olevasta infrastruktuurista.

Tämän osion loppuosa jakaa standardin sanaston siihen, mitä korjauspaketti jo tukee, ja siihen, mikä on tarkoituksellisesti jätetty myöhemmäksi. Alla olevat listat heijastavat korjauspakettisarjan nykyistä tilaa.

1.2 Toteutetut ominaisuudet

Toteutettu sanasto riittää ilmaisemaan kanoniset V-muoto-, W-muoto- ja käänne­kuviot, jotka motivoivat row pattern recognitionin alun perin. Se kattaa myös jokaisen standardin määrittelemän kvanttorin — mukaan lukien kaikki seitsemän vastahakoista varianttia *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — sekä neljä navigointi­primitiiviä, joita DEFINE-ehdot tarvitsevat verratakseen vierekkäisiä rivejä.

PATTERN-lauseke
Määrittelee rivi­kuvion ikkuna­määrittelyn sisällä; enintään 240 erillistä kuvio­muuttujaa.
Ikkunan kehys
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING tai ROWS BETWEEN CURRENT ROW AND n FOLLOWING, jossa n ≥ 1 (19075-5 §6.10.2); mikä tahansa muu kehys hylätään, ja EXCLUDE NO OTHERS on ainoa hyväksytty poissulkeminen.
Regex: + * ? |
Standardin kvanttorit ja vaihtoehto.
Regex: ( ) -ryhmitys
Sulkeisiin kootut alikuviot.
Regex: {n} {n,} {,m} {n,m}
Rajatut toistolaskurit.
Vastahakoiset *? +? ?? {n}? {n,}? {,m}? {n,m}?
Kaikki seitsemän standardin määrittelemää vastahakoista (ei-ahnetta) varianttia (rajattu absorptio-optimoinnin ulkopuolelle).
DEFINE-lauseke
Boolen ehdot, jotka tunnistavat kunkin kuvio­muuttujan.
Universaali rivimuuttuja
DEFINEssä määrittelemättömät sarakeviittaukset (esim. paljas Price) tarkoittavat nykyistä riviä, kohtien 19075-5 §4.10/§4.16 mukaisesti.
PREV, NEXT (siirtymällä)
Saavuttaa n riviä ennen nykyistä tai sen jälkeen (oletus 1); sisempi argumentti arvioidaan navigoidulla rivillä.
FIRST, LAST (siirtymällä)
Saavuttaa osumaan suhteellisen rivin; FIRST(expr, n) kohdistaa rivin n osuman alun jälkeen, LAST(expr, n) rivin n ennen viimeisintä osumarivia.
Yhdistetty navigointi (neljä muotoa)
Ulompi PREV/NEXT-askel kerrostettuna sisemmän FIRST/LAST-funktion päälle: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — sekä sisempi että ulompi askel hyväksyvät oman siirtymänsä.
Navigointinimet
PREV, NEXT, FIRST ja LAST määrittelemättöminä kutsuina DEFINE:n sisällä tarkoittavat aina navigointia; samanniminen käyttäjän funktio on kirjoitettava siellä skeema­määritteisenä.
Navigoinnin argumentit
Funktioilla PREV, NEXT, FIRST ja LAST sisemmän argumentin on sisällettävä vähintään yksi sarake­viittaus, ja siirtymän on oltava ajonaikainen vakio.
INITIAL
Kuvio­osumien on alettava nykyisestä rivistä (oletus).
AFTER MATCH SKIP PAST LAST ROW
Oletusarvoinen ohitustila; soveltuu konteksti­absorptioon.
AFTER MATCH SKIP TO NEXT ROW
Sallii päällekkäiset osumat; estää absorption.

1.3 Ei toteutettuja

Toteuttamatta jääneet ominaisuudet jakautuvat kolmeen löyhään ryhmään. Ensimmäinen — ja ylivoimaisesti suurin — on MEASURES-keskeisten rakenteiden perhe: itse MEASURES-lauseke, SUBSET, CLASSIFIER(), kuvio­määritteiset sarake­viittaukset kuten B.price sekä kuvio­määritteinen navigointi kuten LAST(B.price) tai PREV(B.price).

Nämä eivät ole niinkään itsenäisiä aukkoja, vaan eri näkökulmia yhteen ja samaan puuttuvaan palaseen: executorin olisi säilytettävä osumakohtainen historia — jokaiselta osuman riviltä merkintä siitä, mihin kuvio­muuttujaan se kuvattiin — eikä yhdelläkään näistä rakenteista ole mielekästä määritelmää ilman sitä. CLASSIFIER() lukee muuttujan nimen tästä merkinnästä; B.price lukee niiden rivien hintasarakkeen, joiden merkintä ilmoittaa B; LAST(B.price) käy läpi saman rivijoukon ja poimii viimeisen; SUBSET U = (A, B) määrittelee virtuaalimuuttujan, joka aggregoi molempien yli; ja MEASURES arvioi lausekkeita kuten AVG(U.Price) juuri tällä aggregoinnilla.

Nykyinen executor arvioi DEFINE-predikaatit rivi kerrallaan mutta ei tallenna syntyviä muuttuja­sidoksia mihinkään — myöhemmin ei ole mistä kysyä. Historia­infrastruktuurin rakentaminen on siten edellytys koko ryhmälle; yksittäiset ominaisuudet putoavat ulos pieninä projekteina, kun merkinnät ovat olemassa.

Toinen ryhmä koskee vaihtoehtoisia ohituskohteita: AFTER MATCH SKIP TO FIRST var ja AFTER MATCH SKIP TO [LAST] var (paljas SKIP TO var tarkoittaa SKIP TO LAST var). Nämäkin riippuvat osuma­historiasta, koska executorin on kyettävä osoittamaan riviä, joka viimeisimmän osuman sisällä kuvattiin tiettyyn muuttujaan.

Loput ovat heterogeeninen pyrstö: avainsana SEEK (vaihtoehto INITIAL:lle), tyhjä kuvio (), poissulkemis­muoto {- … -}, järjestyksestä riippumaton operaattori PERMUTE sekä aggregaatti­funktiot ja alikyselyt DEFINE:ssa, jotka molemmat hylätään toistaiseksi (muuttuja­määritteinen aggregaatti tarvitsisi lisäksi osuma­historian).

MEASURES
Nimettyjä osumakohtaisia tuloste­lausekkeita, esim. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; R020:ssa esiin tuotuna OVER-rakenteen kautta kuten ikkunafunktio. Hyväksyy avainsanat FINAL / RUNNING (19075-5 §5.4), jotka R020:ssa palautuvat samaan arvoon, koska mittaukset arvioidaan aina osuman viimeisellä rivillä (19075-5 §6.9 (3)).
SUBSET
Kuvio­muuttujien nimettyjä unioneja, esim. SUBSET U = (A, B, C). Käytettävissä missä tahansa kuvio­muuttujaan voidaan viitata — MEASURES, kuvio­määritteiset viittaukset DEFINE:ssa, CLASSIFIER(U) — jotka kaikki vaativat osuma­historiaa.
CLASSIFIER()
Palauttaa, miksi kuvio­muuttujaksi annettu rivi täsmättiin. Määritelty sekä DEFINE:lle että MEASURES:lle (19075-5 §5.9); vastaus millä tahansa rivillä on kyseiselle riville osuma­historiaan kirjattu muuttujan nimi.
Kuvio­määritteinen sarake­viittaus
Pelkkä B.price DEFINE:ssa tai MEASURES:ssa — sarakkeen arvo siltä riviltä, joka kuvattiin nimettynä muuttujana.
Kuvio­määritteinen navigointi
Rajoittaa navigoinnin riveihin, jotka täsmättiin nimettynä muuttujana, esim. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).
SEEK
Osuma voi alkaa miltä tahansa riviltä nykyisestä rivistä koko ikkuna­kehyksen loppuun (vs. INITIAL).
AFTER MATCH SKIP TO FIRST var
Hyppää ensimmäiselle riville, joka täsmättiin nimettynä muuttujana.
AFTER MATCH SKIP TO [LAST] var
Hyppää viimeiselle riville, joka täsmättiin nimettynä muuttujana.
Regex: {- -}
Poissulkeminen — poistaa täsmätyt rivit ALL ROWS PER MATCH -tulosteesta. Tämä valinta ei koske ikkunoita (19075-5 §6.3.3 (4)), joten ikkunassa syntaksi on sallittu (§6.13), mutta sillä ei ole tulostetta, johon vaikuttaa.
Regex: ()
Tyhjä kuvio — täsmää tyhjään jonoon.
PERMUTE(...)
Järjestyksestä riippumaton täsmäys lueteltujen muuttujien yli. Avainsana tunnistetaan ja hylätään (”PERMUTE is not supported”); permute on edelleen käytettävissä kuvio­muuttujan nimenä.
Aggregaattifunktiot DEFINE:ssa
Aggregaatteja kuten SUM, AVG, COUNT ei sallita DEFINE-predikaateissa. Standardi sallii ne juoksevina aggregaatteina osittaisen osuman yli; muuttuja­määritteinen aggregaatti kuten AVG(B.Price) riippuu samasta osuma­historiasta, jonka MEASURES/CLASSIFIER() vaativat, kun taas määrittelemätön aggregaatti kattaa kaikki osuman tähänastiset rivit.
Alikyselyt DEFINE:ssa
Jokainen alikysely DEFINE:ssa hylätään. Standardi sallii alikyselyn, joka ei suorita row pattern recognitionia eikä viittaa yhteenkään rivi­kuvio­muuttujaan; korjauspaketti hylkää toistaiseksi liikaa.

Tässä on syytä huomauttaa neljästä lisäkohdasta, sillä ne on helppo erehtyä luulemaan puutteiksi.

Ensimmäinen on, että kuvio­ankkureita ^ ja $ ei sallita RPR:n yhteydessä WINDOW-lausekkeessa itse standardin mukaan (19075-5 §6.13: ”the anchors (^ and $) are not permitted with row pattern matching in windows”; taustalla oleva määritelmä kohdassa 19075-5 §4.14.1); niiden puuttuminen on standardin­mukaisuutta, ei aukko.

Toinen on, että standardi rajaa myös MATCH_NUMBER()-funktion R020:n ulkopuolelle (19075-5 §6.3.3 (6) ja 19075-5 §6.9 (1)) — se kuuluu vain R010-rajapintaan, ja sen puuttuminen täältä on jälleen standardin­mukaisuutta eikä puuttuva ominaisuus.

Kolmas on joukko rakenteellisia kieltoja, jotka standardi asettaa R020:lle (19075-5 §6.17): row pattern recognitionia ei voi sijoittaa sisäkkäin toisen row pattern recognitionin kanssa; MEASURES ja DEFINE eivät saa sisältää ulkoisia viittauksia; MEASURES:n tai DEFINE:n alikyselyt eivät saa viitata rivi­kuvio­muuttujiin (korjauspaketti menee pidemmälle ja hylkää kaikki alikyselyt DEFINE:ssa, kuten yllä lueteltiin); eikä RPR:ää saa käyttää rekursiivisen kyselyn sisällä. Korjauspaketti valvoo ulkoisten viittausten sääntöä (”cannot use outer query column in DEFINE clause”) ja rekursio­sääntöä, jälkimmäistä WITH RECURSIVE -lausekkeen jokaisen elementin osalta. Se hylkää myös volatiilit funktiot ja koko rivin viittaukset DEFINE:ssa.

Neljäs on, että MATCH_RECOGNIZE itse — ominaisuus R010, saman koneiston taulu­lauseke­rajapinta — on tämän korjauspaketin ulkopuolella. Lisääkö PostgreSQL aikanaan R010:n, on tulevien sarjojen kysymys eikä mitta tästä työstä.

Lähde. Tämän osion toteutettujen ja toteuttamattomien listat heijastavat korjauspaketti­sarjan nykytilaa — tarkemmin ottaen versiota v55 (2026-11-17).

§2. Esimerkit — kuinka se todellisuudessa toimii

Tämän osion esimerkit rakentuvat asteittain. Aloitamme käsitteellisestä syystä, miksi rivikuvio­täsmäys on aidosti erilaista kuin merkkijono­kuvio­täsmäys, esittelemme sitten neljä navigointi­funktiota, jotka tekevät DEFINE-ehdoista mielenkiintoisia, ja käymme lopuksi läpi viisi käytännön esimerkkiä: yksittäisen osuman (NFA-liike), vaihtoehdon, konteksti­absorption helpossa tapauksessa sekä kaksi tapausta, joissa absorptio on kytketty pois päältä.

Sisäinen mekanismi, joka tekee navigoinnista halpaa — yhden paikan tuple-vaihto — kuuluu executorin suunnitteluun ja käsitellään seuraavassa osiossa, ei täällä.

2.1 Miksi rivi­kuviot eroavat tekstikuvioista

Tekstin säännöllinen lauseke täsmää merkkivirtaan, ja jokaisessa kohdassa on tarkastel­tavana täsmälleen yksi symboli. Suoritusaikainen kysymys — ”vastaako nykyinen symboli arvoa 'A'?” — saa yhden kyllä/ei-vastauksen. Takaperin etenevät automaatit hyödyntävät tätä: enintään yksi haara säilyy merkkiä kohden, ja monitulkintaisuuden hinta maksetaan lukemalla syöte uudelleen.

Rivikuvio on perustavanlaatuisesti erilainen. Rivi ei ole yksittäinen symboli; se on sarakkeiden tuple, joka arvioidaan Boolen predikaattien joukkoa, DEFINE-ehtoja, vasten. Kaksi predikaattia voi olla totta samalla rivillä yhtä aikaa, eikä standardissa lue, että niiden olisi oltava toisensa poissulkevia. Tarkastellaan:

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

Rivi, jolla price = 150, volume = 2000, toteuttaa sekä A:n että B:n mutta ei C:tä. Kuvio­täsmäin ei voi tiivistää tätä yhdeksi tilaksi — kaksi kuvio­muuttujaa on elossa, ja mikä tahansa kuvio­elementti, joka nimeää jommankumman, voi edetä. NFA:n on siten kannettava useita yhtäaikaisia tiloja partition rivillä, ei vain yhtä.

Text regex vs row pattern: a single state advances per symbol, while multiple DEFINE predicates can match a row in parallel. TEXT REGEX single state advances through symbols A B C one symbol per position · one transition ROW PATTERN one row, multiple predicates evaluated row price = 150 · volume = 2000 A ✓ price > 100 B ✓ volume > 1000 C ✗ price > 200 two predicates true · two states stay alive
Tekstin regex tiivistyy yhteen tilaan symbolia kohden; rivi voi toteuttaa useita DEFINE-predikaatteja kerralla, joten useita tiloja pysyy elossa rinnakkain.

Tämä yksi havainto ohjaa muuta arkkitehtuuria. Suoritus­tila on lista konteksteista, kukin konteksti on lista tiloista, ja jokaisella rivillä ajoaika kysyy jokaiselta tilalta: ”kun otetaan huomioon tässä todet muuttujat, minne voin edetä?” Syntyvät haarautumat ovat syy siihen, miksi ajoaika tarvitsee useita karsinta­kerroksia — tilojen poisto­duplikointi kontekstin sisällä, absorptio kontekstien välillä ja muut §3.6:ssa esitellyt säännöt — joita ilman elävien tilojen ja kontekstien lukumäärä kasvaa partitioon mukaan ja kuvio­täsmäys muuttuu superlineaariseksi.

2.2 Navigointi­funktiot

DEFINE-ehdot, jotka viittaavat vain nykyiseen riviin, ovat rajalliset; lähes jokainen mielenkiintoinen kuvio joutuu vertaamaan nykyistä riviä naapureihinsa tai aiemmin osumassa hyväksyttyihin riveihin. Standardi tarjoaa tähän neljä navigointi­funktiota, ja korjauspaketti toteuttaa ne kaikki.

PREV(expr [, n])
Rivi n riviä ennen nykyistä riviä (oletus n = 1). Käytetään ”tänään vs. eilen” -vertailuihin.
NEXT(expr [, n])
Rivi n riviä nykyisen rivin jälkeen (oletus n = 1). Eteenpäin katsova; ikkuna­muodossa harvinainen, koska ikkuna on monotoninen.
FIRST(expr [, n])
Rivi n riviä nykyisen osuman ensimmäisen rivin jälkeen (oletus n = 0, eli itse ensimmäinen rivi). ”Vertaa siihen riviin, joka aloitti tämän osuman.”
LAST(expr [, n])
Rivi n riviä ennen viimeistä täsmättyä riviä (oletus n = 0). DEFINE:n sisällä viimeinen täsmätty rivi on nykyinen rivi, joten LAST(price) lukee nykyisen rivin.

Nämä neljä primitiiviä yhdistyvät: PREV ja NEXT voivat ympäröidä FIRST- tai LAST-kutsun, mistä syntyy neljä yhdistettyä muotoa, joiden semantiikka on ”siirry osumaan suhteelliselle riville ja astu siitä kiinteä matka kauemmaksi.” Juuri tämän ansiosta DEFINE-lauseke voi lukea esimerkiksi rivin juuri ennen osuman alkua.

PREV(FIRST(expr [, n]) [, m])
Astu m riviä taaksepäin rivistä, jonka FIRST(expr, n) lukee (oletukset n = 0, m = 1). ”Mikä arvo oli juuri ennen tämän osuman alkua?”
NEXT(FIRST(expr [, n]) [, m])
Astu m riviä eteenpäin rivistä, jonka FIRST(expr, n) lukee. Yltää syvemmälle osumaan riippumatta nykyisestä rivistä.
PREV(LAST(expr [, n]) [, m])
Astu m riviä taaksepäin rivistä, jonka LAST(expr, n) lukee. ”Vertaa riviin hieman ennen viimeisintä täsmättyä riviä.”
NEXT(LAST(expr [, n]) [, m])
Astu m riviä eteenpäin rivistä, jonka LAST(expr, n) lukee.

Tässä on syytä mainita kaksi käytännön seikkaa. Ensinnäkin navigointia voi yhdistellä: PREV(FIRST(price)) lukee rivin juuri ennen osuman alkua, ja korjauspaketti tukee tätä. Toiseksi navigoinnilla on seurauksia executorin optimoinneille. Pelkät PREV ja NEXT ovat suhteessa nykyiseen riviin ja aina turvallisia; FIRST sekä LAST:n siirtymä­variantit, yksinään tai yhdistetyn PREV/NEXT-kutsun sisällä, ovat suhteessa osuman rajoihin, mikä vuorovaikuttaa konteksti­absorption kanssa: suunnittelija kytkee tällöin absorption pois koko kuviolta. Tämän vuorovaikutuksen taustalla oleva mekanismi on §2.6:n aihe.

2.3 Käytännön esimerkki 1 — NFA-liike

Esimerkin tavoiteOsoittaa NFA-tilan rivi rivin -kehitys yksinkertaisella, ei-absorptioivalla kuviolla. Jäljitys seuraa rivillä 0 alkanutta kontekstia; riveillä 1–4 alkaneet kontekstit kulkevat sen rinnalla, ja SKIP PAST LAST ROW hylkää ne, kun sen osuma on kirjattu.
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)
);

Kuvio litistyy neljäksi elementiksi:

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

Hintasarjalle 100, 110, 120, 115, 108, 130:

RiviHintaTodet muuttujatToiminto
0100STARTUusi konteksti. START täsmää ja poistuu välittömästi (max=1); tila etenee tilaan UP+.
1110START, UPUP täsmää. Eteneminen haarautuu: yksi tila silmukoituu UP:hen, toinen poistuu tilaan DOWN+.
2120START, UPUP täsmää silmukka­tilassa ja haarautuu uudelleen. Rivin 1 DOWN-tila kuolee (120 ≮ 110).
3115START, DOWNUP epäonnistuu silmukka­tilassa ja kuolee. Rivin 2 DOWN-tila täsmää. Eteneminen haarautuu: silmukka DOWN:ssa ja poistuminen tilaan #FIN — osumakandidaatti riveillä 0–3 kirjataan.
4108START, DOWNDOWN täsmää silmukka­tilassa ja haarautuu uudelleen; uusi FIN-kandidaatti riveillä 0–4 korvaa lyhyemmän.
5130START, UPSilmukoiva DOWN-tila epäonnistuu (130 ≮ 108). Koska tässä kontekstissa ei ole enää eläviä tiloja, kirjattu kandidaatti (rivit 0–4) vahvistetaan osumaksi. Seuraava yritys alkaa rivillä 5; START täsmää, mutta partitio päättyy ennen yhtäkään UP:ta.

Olennainen kohta: rivillä 3 rivi toteuttaa sekä START:n (aina tosi) että DOWN:n, mutta START merkitsee vain rivillä 3 alkavalle kontekstille; tässä kontekstissa silmukoiva UP-tila kuolee ja vain DOWN+:ssa odottava tila etenee. §2.1:n monitilainen luonne näkyy haarautumisena jokaisessa UP-täsmäyksessä (tila voisi jäädä UP+:han tai edetä kohti DOWN+:ia). Ahne suosinta on ”silmukoi vielä ennen poistumista”, joten riittävän datan kanssa silmukka­haarat venyttäisivät osumaa pidemmälle; tässä silmukoiva DOWN kuolee rivillä 5 (130 ≮ 108), ja viimeisin FIN-kandidaatti (rivit 0–4) — joka syntyi DOWN:n poistuessa rivillä 4 ja korvasi rivin 3 kandidaatin — vahvistetaan osumaksi.

Kyselyn tulos seuraa suoraan tästä jäljityksestä. RPR-semantiikan mukaan ikkunafunktiot first_value(price) ja last_value(price) arvioidaan vain sillä rivillä, joka aloitti osuman — jokainen muu osuman rivi tuottaa näille ikkunafunktioille NULL-arvon, koska sen pelkistetty kehys on tyhjä. Tulos datallemme näyttää siten samalta kuin posterin oikean yläpaneelin taulukko:

RiviHintastart_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

Rivi 0 on osuman alku, joten sen kehys kattaa rivit 0–4 ja ikkunafunktiot raportoivat V-muodon avaushinnan ($100) ja pohjahinnan ($108). Rivit 1–4 ovat osuman sisällä mutta eivät sen alussa, joten ne saavat NULL-arvon. Rivi 5 (hinta $130) on minkään osuman ulkopuolella ja saa myös NULL-arvon.

2.4 Käytännön esimerkki 2 — Vaihtoehto ja leksikaalinen järjestys

Esimerkin tavoiteOsoittaa, kuinka yksi konteksti kantaa useita rinnakkaisia tiloja, kun yksi rivi toteuttaa useamman kuin yhden vaihtoehdon — ja kuinka standardi ratkaisee tasapelit.

Muoto (A | B) antaa täsmäimelle valinnan: millä tahansa rivillä molemmat vaihtoehdot testataan riippumattomasti, ja mikä tahansa määrä niistä voi täsmätä. Juuri tässä §2.1:n monitilainen luonne tulee näkyviin yhden kontekstin sisällä — ei kontekstien välillä (se on absorptio), vaan rinnakkaisilla haaroilla, joita executor tutkii kuvion järjestyksessä, aiempi haara ensin.

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

Kuvittele rivi, jolla hinta on sekä noussut että ylittänyt $100 — sekä UP että HIGH ovat tosia. Kumpikin vaihtoehto synnyttää oman tilansa: toinen kävelee UP-haaraa, toinen HIGH-haaraa. Molemmat etenevät sitten DONE:en, jossa ne kohtaavat.

RiviTodet muuttujatElävät tilat
RUP, HIGHTila A (UP-haara) ja tila B (HIGH-haara) etenevät molemmat DONE:en samoilla laskureilla; B on A:n kaksoiskappale ja hylätään
R+1DONETila A täsmää DONE:en ja saavuttaa #FIN-tilan

Standardin termein molemmat haarat tuottavat samanmittaisen osuman samojen rivien yli, jolloin syntyy kaksi kandidaatti­polkua — toinen merkitty UP, DONE, toinen HIGH, DONE. Standardi ratkaisee tämän leksikaalisella järjestyksellä: (UP | HIGH):ssa kirjoitetuista vaihtoehdoista voittaa ensimmäisenä kirjoitettu, riippumatta osuman pituudesta. Koska UP esiintyy ennen HIGH:ia, säilyvä polku on UP, DONE. Executor toteuttaa tämän rivillä R, ei FIN:ssä: se lisää UP-haaran tilan ensin, joten nfa_append_state_unique() säilyttää sen ja pudottaa identtisen HIGH-haaran tilan.

Leksikaalinen järjestys tekee CLASSIFIER():stä hyvin määritellyn, kun se aikanaan toteutetaan — se sallii ajoajan kertoa käyttäjälle ”tämä rivi täsmäsi UP:han, ei HIGH:in”, vaikka molemmat predikaatit olisivat tosia. Leksikaalinen järjestys on vaihtoehdon ensisijainen sääntö: leksikaalisesti aiempi haara voittaa myöhemmän, vaikka myöhempi tuottaisi pidemmän osuman, ja leksikaalisesti myöhempi (mahdollisesti lyhyempi) haara voi silti voittaa, jos jokainen leksikaalisesti aiempi haara kuolee ennen FIN:iä. Ahne pituus ratkaistaan yhden kvanttorin sisällä — saman vaihtoehto­haaran kahdesta päätöksestä ahne kvanttori suosii useampia iteraatioita.

2.5 Käytännön esimerkki 3 — Konteksti­absorptio (sama kohtalo)

Esimerkin tavoiteOsoittaa, miksi tilojen naiivi O(n²)-kokonaistyö muuttuu O(n):ksi absorption ansiosta, kun eläviä konteksteja on O(1).

Yksinkertaisin absorptiota näyttävä kuvio on PATTERN (A+) ja DEFINE A AS TRUE. Jokainen rivi täsmää A:han, ja standardi vaatii täsmäimen harkitsemaan jokaista riviä mahdolliseksi osuman aluksi. Naiivisti tämä tarkoittaa N kontekstia N-rivisellä partitiolla. Otetaan viisi­rivinen partitio (mikä tahansa data — predikaatti on vakio tosi):

RiviNaiivit kontekstitAbsorption kanssa
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 absorboitu
2C1[A:3], C2[A:2], C3[A:1]C1[A:3]
3C1[A:4], C2[A:3], C3[A:2], C4[A:1]C1[A:4]
4viisi kontekstiaC1[A:5]

Elävien kontekstien määrä putoaa O(n):stä O(1):een, joten kokonaismäärä partition yli putoaa O(n²):sta O(n):ään. Hylkäystä oikeuttava absorptio­sääntö on suoraviivainen, kun kvanttori on rajaton:

Absorptio­sääntö. Kaksi kontekstia, joiden elävä tila on samassa kuvio­elementissä ja joista vanhemman laskuri on ≥ uudemman, omaavat identtiset tulevaisuudet rajattoman kvanttorin alla. Uudempi konteksti voidaan hylätä; minkä tahansa osuman se aikanaan löytäisi, vanhempi konteksti löytää pidemmän tai yhtä pitkän.

Posterin vasen alapaneeli (”① Konteksti­absorptio”) on juuri tämä sääntö visualisoituna viidellä rivillä.

Sääntöön kätkeytyy hienovarainen mutta tärkeä seikka: hylkäys on turvallinen, koska predikaatti A AS TRUE arvioituu samaan arvoon jokaisella rivillä riippumatta siitä, mikä konteksti kysyy. Sama pätee mihin tahansa predikaattiin, joka viittaa vain nykyiseen riviin tai sen kiinteään siirtymään — mukaan lukien PREV. Seuraava esimerkki vaihtaa konkreettiseen kauppa­viikkoon ja käyttää PREV-pohjaista predikaattia, ja §2.6 käyttää samaa viikkoa tehdäkseen turvallisen ja epäturvallisen absorption symmetrian ilmeiseksi:

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

Otetaan kauppa­viikko $100, $108, $112, $116, $110 maanantaista perjantaihin — neljä nousua, joita seuraa äkillinen pudotus. Oletetaan, että C1 alkaa tiistaina (ensimmäinen päivä, jolloin RISE täsmää: $108 > $100), ja executor seuraa spekulatiivisesti myös keskiviikkona alkavaa C2:ta. Kunkin rivin RISE-ehto vertaa rivin hintaa sen välittömään edeltäjään — partitio­tason tosiasia, ei konteksti­tason — joten molempien kontekstien on pakko laskea sama Boolen arvo jokaisella jaetulla rivillä:

PäiväHintaC1 — Ti alku
price > PREV(price)
C2 — Ke alku
price > PREV(price)
Ma$100——
Ti$108$108 > $100 ✓ (juuri alkanut)—
Ke$112$112 > $108 ✓$112 > $108 ✓ (juuri alkanut)
To$116$116 > $112 ✓$116 > $112 ✓
Pe$110$110 > $116 ✗ — vahvista$110 > $116 ✗ — vahvista
Sama kohtalo Jokaisella C1:n ja C2:n jakamalla rivillä ne arvioivat identtisiä lausekkeita ja tuottavat identtiset tulokset — ja perjantaina ne kuolevat täsmälleen samaan vertailuun. Mikä tahansa C2:n tulevaisuus on, on myös C1:n. C2:n absorboiminen C1:een ei heitä mitään hukkaan.

Tarina rikkoutuu sillä hetkellä, kun predikaatti alkaa riippua kunkin kontekstin omista rajoista — ja juuri siitä §2.6 puhuu.

2.6 Käytännön esimerkki 4 — Milloin absorptio muuttuu epäturvalliseksi

Esimerkin tavoiteOsoittaa, mikä muuttuu, kun DEFINE viittaa FIRST:iin — absorptio­sääntö ei enää päde, ja suunnittelija kytkee absorption pois kuviolta.

Oletetaan, että analyytikko haluaa löytää peräkkäisiä kauppa­päiviä, joina osake pysyi kymmenen dollarin sisällä juoksun aloituspäivän hinnasta — eräänlainen konsolidoitumis­ikkuna. Kuvio ja DEFINE näyttävät tältä:

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

Ehto vertaa nyt nykyisen rivin hintaa nykyisen juoksun aloitushintaan. Kahdella eri päivinä alkaneella juoksulla on eri FIRST(price)-arvot, joten kaksi tilaa samassa kuvio­elementissä ja samalla laskurilla eivät enää ole keskenään vaihdettavissa: niiden tulevaisuus riippuu rajasta, jonka absorptio oli juuri hylkäämässä.

Otetaan täysin sama kauppa­viikko kuin §2.5:ssä — $100, $108, $112, $116, $110 maanantaista perjantaihin. Ajoaika pitää jälleen elossa kaksi kandidaatti­juoksua samanaikaisesti: C1 alkoi maanantaina, C2 tiistaina (jokainen rivi on potentiaalinen juoksun alku STABLE+:n alla).

PäiväHintaC1 — Ma alku
FIRST = $100
price < $100 + 10
C2 — Ti alku
FIRST = $108
price < $108 + 10
Ma$100$100 < $110 ✓—
Ti$108$108 < $110 ✓$108 < $118 ✓ (juuri alkanut)
Ke$112$112 < $110 ✗ — vahvista Ma–Ti$112 < $118 ✓
To$116—$116 < $118 ✓
Pe$110—$110 < $118 ✓ (yhä käynnissä)
Erilaiset kohtalot C1 kuolee keskiviikkona kahden päivän juoksulla (Ma–Ti); C2 jatkaisi yksinään aina perjantaihin asti. Samat hinnat, sama kysymyksen muoto — mutta omista osumiensa aluista johdetut eri katot. Samana päivänä molemmat kontekstit päätyivät vastakkaisiin johtopäätöksiin.

Absorption alla C2 olisi yhdistetty C1:een tiistaina — yhdistetty konteksti säilyttää vain C1:n katon ($110), joten C2:n erillinen näkemys (katto $118, neljän päivän juoksu perjantaihin asti) ei sisälly C1:n tulevaisuuteen. Juuri tällä viikolla tuloste ei sattumalta muutu: C1 kirjaa Ma–Ti, C2 alkoi tämän osuman sisällä ja SKIP PAST LAST ROW hylkää sen, ja seuraava yritys alkaa keskiviikkona omalla katollaan ($122) ja täsmää Ke–Pe. Yleisesti kuitenkin aiemman kontekstin DEFINE-tulos ei enää kata myöhemmän tulosta, joten laskurivertailu, johon absorptio nojaa, ei ole pätevä. Aina kun DEFINE-predikaatti kantaa osumaan­alku­riippuvuutta, suunnittelija kytkee absorption ennakoivasti pois päältä.

(Kun johtavan kontekstin osuma todella onnistuu, sen hyväksytyn alueen sisällä alkaneet kontekstit — oletusmoodin AFTER MATCH SKIP PAST LAST ROW alla — yksinkertaisesti hylätään; ne pidetään elossa vain jotta ajoajalla on jokin paikka, johon palata, jos johtava osuma epäonnistuu.)

Alla oleva taulukko laajentaa posterin oikeaa alapaneelia (”② Navigointi”) yhdistetyillä muodoilla ja tiivistää, mitkä navigointi­muodot synnyttävät osumaan­alku­riippuvuutta:

NavigointiOsuman alkuriippuvuusAbsorboituuko?
PREV, NEXTeikyllä
LAST (ilman siirtymää)eikyllä
LAST siirtymälläraja­tarkistusei
FIRST (mikä tahansa)suoraei
Yhdistetty (sisempi FIRST)suoraei
Yhdistetty (sisempi LAST, ilman siirtymää)eikyllä
Yhdistetty (sisempi LAST siirtymällä)raja­tarkistusei

§2.5:n ja §2.6:n esimerkit pelkistyvät yhdeksi säännöksi. Sama kohtalo tekee absorptiosta turvallisen: jos jokainen samassa kuvio­elementissä oleva konteksti laskee saman vastauksen jokaiseen tulevaan predikaattiin, vain vanhin tarvitsee säilyttää. Erilaiset kohtalot tekevät absorptiosta epäturvallisen: heti kun predikaatit haarautuvat konteksti­yksityisen tilan perusteella — juuri näin FIRST ja siirtymällinen LAST tekevät — jokainen elävä konteksti edustaa tulevaisuutta, jota minkään muun kontekstin ei taata kattavan, joten yhdenkään hylkäämistä ei enää voida osoittaa turvalliseksi.

Suunnittelija havaitsee tämän eron käännös­aikana ja kytkee absorption päälle tai pois koko kuviolta; kun se on pois päältä, ajoaika maksaa moni­konteksti­kustannuksen. Posterin paneelin ③ benchmark ei käytä FIRST:iä, joten absorptio pysyy päällä, ja siksi PostgreSQL pysyy lineaarisena sekä onnistumis- että epäonnistumis­tapauksissa.

Posterin benchmark-luvut ovat sama algoritmi mittakaavassa. Onnistumis­kuviolla (A+ B+ C+ D) sekä PostgreSQL että Trino skaalautuvat suunnilleen O(n):nä osuman vahvistuttua, ja PostgreSQL on edellä noin 16×–33× (Trinon luvuista on jo jätetty pois JVM:n käynnistys).

Epäonnistumis­kuviolla (A+ B+ C+ E) Trino, jolta absorptio näyttää puuttuvan, jahtaa jokaista potentiaalista osuman alkua ja rappeutuu jopa O(n²):ta nopeammin (noin 56-kertainen aika 5-kertaisella rivimäärällä); 100 000 rivillä se kestää yli viisi tuntia, kun PostgreSQL valmistuu silti 92 ms:ssa, nopeutus noin 217 000×.

Tuo ero ei ole insinöörityön viilausta — se on täsmälleen sama-kohtalo / erilainen-kohtalo -erottelu §2.5:sta ja §2.6:sta sovellettuna jokaiseen partition jokaisen potentiaalisen osuman aloitusriviin.

2.7 Käytännön esimerkki 5 — Milloin SKIP estää absorption

Esimerkin tavoiteOsoittaa toinen tapa, jolla absorptio voi pettää: ei siksi, että predikaatti haarautuisi, vaan koska tulosteen semantiikka vaatii jokaisen osuman raportoimista erikseen.

Edellinen esimerkki rikkoi absorption data­puolelta: FIRST DEFINE:ssa sai kunkin kontekstin arvioimaan predikaatit eri tavalla. Absorptio voi rikkoutua myös tuloste­puolelta, ja juuri AFTER MATCH SKIP -lauseke ohjaa tätä.

Tarkastellaan kuviota PATTERN (A+) ja DEFINE A AS TRUE viidellä rivillä, jotka kaikki täsmäävät A:han. Oletusmoodin AFTER MATCH SKIP PAST LAST ROW alla täsmäin löytää pisimmän, varhaisimmasta rivistä alkavan osuman ja hyppää sen yli; kaikki tämän osuman sisällä alkaneet kontekstit hylätään implisiittisesti tarpeettomina — täsmälleen tilanne, johon absorptio on suunniteltu. Tuloste on yksi osuma, rivit 0–4, ja ajoaika tarvitsee vain yhden elävän kontekstin.

Vaihda ohitus­moodi tilaan AFTER MATCH SKIP TO NEXT ROW, ja sopimus muuttuu:

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

Nyt jokainen potentiaalinen aloituspiste on raportoitava erikseen, vaikka osumat menisivät päällekkäin. Samojen viiden rivin kohdalla ajoajan on tuotettava viisi osumaa: rivit 0–4, 1–4, 2–4, 3–4 ja 4–4. Yhtäkään näistä ei voi korvata ”aiemmin alkavalla pidemmällä”, koska standardi sanoo käyttäjän haluavan ne kaikki.

RiviSKIP PAST LAST ROWSKIP TO NEXT ROW
0osuma alkaa; rivit 0–4 ovat ainoa osumaosuma alkaa rivillä 0
1(osuman 0 sisällä)osuma alkaa rivillä 1 — pidettävä elossa
2(osuman 0 sisällä)osuma alkaa rivillä 2 — pidettävä elossa
3(osuman 0 sisällä)osuma alkaa rivillä 3 — pidettävä elossa
4osuma 0 vahvistuu (rivit 0–4)viisi osumaa vahvistuu: 0–4, 1–4, 2–4, 3–4, 4–4
Eri tuloste, eri kohtalot AFTER MATCH SKIP TO NEXT ROW:n alla jokainen myöhään alkanut konteksti on oma tuloste­rivinsä. Kaksi kontekstia samassa kuvio­elementissä eivät enää ole tarpeettomia — molemmat ovat vaadittuja tulosteita, ja yhden hylkääminen pudottaisi hiljaisesti käyttäjän pyytämän osuman.

Huomaa, että predikaatti ei ole muuttunut. A AS TRUE arvioituu samalla tavalla jokaisella rivillä riippumatta siitä, mikä konteksti kysyy, joten §2.5:n sama-kohtalo-ehto täyttyy edelleen. Mikä muuttuu, on tuloste­vaatimus: jopa identtisten tulevaisuuksien konteksteilla on oltava rinnakkais­elämä, koska ne vastaavat tuloksen erillisiä rivejä. Suunnittelija kytkee siten konteksti­absorption pois päältä aina, kun AFTER MATCH SKIP TO NEXT ROW on voimassa, riippumatta DEFINE-lausekkeesta.

§2.6:n ja §2.7:n asettaminen rinnakkain antaa ne kaksi tapaa, joilla kyselyn semantiikka sulkee absorption pois:

Datapuoli · §2.6
Predikaatti arvioituu eri tavoin konteksteittain.
Laukaisee FIRST tai siirtymällinen LAST DEFINE:ssa.
Tulostepuoli · §2.7
Tuloste vaatii jokaisen osuman alun erillisenä rivinä.
Laukaisee AFTER MATCH SKIP TO NEXT ROW.

Jompikumpi ehto riittää kytkemään absorption pois käytöstä koko kuviolta, ja samoin riittää kehys, joka ei pääty UNBOUNDED FOLLOWING:iin. Kun mikään näistä ei ole voimassa — oletus AFTER MATCH SKIP PAST LAST ROW, rajaton kehyksen loppu sekä DEFINE-ehdot, jotka käyttävät vain PREV:iä, NEXT:iä tai paljasta LAST:ia — absorptio on käytössä, mutta vain kuvion absorboituvan alueen tiloille: johtava ahne rajaton muuttuja kuten A+ tai A*, kiinteäpituinen ryhmä rajattomalla ahneella kvanttorilla kuten (A B)+, ahne ryhmä, jonka runko alkaa jollakin näistä, kuten (A+ B)+ tai (A+ B){2}, tai näistä rakennetut vaihtoehto­haarat; vastahakoinen ryhmä sulkee pois koko alipuunsa. Missä tämä pätee, kuten A+:lle §2.5:ssä, ajoaika tiivistyy yhteen kontekstiin ja pysyy lineaarisena; §2.3:n START UP+ DOWN+ ei saa lainkaan absorboituvaa aluetta.

§3. Suunnittelu — parserista executoriin

Row Pattern Recognition on toteutettu kolmena vaiheena, jotka siirtävät työn eteenpäin hyvin määriteltyjen välimuotojen kautta. Parser muuttaa SQL-tekstin kuvio­puuksi ja DEFINE-predikaattien listaksi; suunnittelija kääntää puun litteäksi kuvio­elementtien taulukoksi ja päättää, mitkä niistä voivat osallistua konteksti­absorptioon; executor ajaa taulukon partitiota vasten rivi rivin kolmi­vaihelaisessa silmukassa. Jokaisella vaiheella on oma data­muotonsa, ja suurin osa suunnittelun nerokkuudesta on rajoilla: välimuistiin mahtuva litteä NFA, navigointi­malli, joka käyttää yhtä tuple-paikkaa eikä materialisoi viittausta kohden, sekä absorptio­sääntö, joka muuttaa O(n²)-työn O(n):ksi.

SQL-teksti
  │
  │  parser-vaihe
  ▼    validoi kehys
       rakenna kuvio­puu
       tyyppitarkista DEFINE

kuvio­puu + DEFINE-lista
  │
  │  suunnittelija-vaihe
  ▼    optimoi puu
       käännä litteäksi NFA-taulukoksi
       päätä absorboituvuus

litteä NFA + absorptio­liput
  │
  │  executor-vaihe
  ▼    rivi­kohtainen moottori:
       Match → Absorb → Advance

osumatulos:
  alkurivi, pituus, onnistuminen/epäonnistuminen

Alla olevat osiot kulkevat tämän putken läpi. §3.1 käsittelee parserin ja kuvio­puun muodon; §3.2 käännöksen, joka muuttaa puun litteäksi NFA:ksi; §3.3 navigointi­mallin, jota DEFINE-predikaatit käyttävät naapuririvien tarkasteluun; §3.4 osuman raja­käsittelyn — SKIP-, INITIAL- ja rajatun kehyksen säännöt, jotka kiinnittävät osuman alun ja lopun; §3.5 on kolmi­vaihelainen rivi­kohtainen moottori; §3.6 kokoaa kaikki karsinta­mekanismit, jotka pitävät tila-avaruuden rajattuna; ja §3.7 kartoittaa sen, mitä toteutus tuo näkyviin EXPLAIN-tulosteessa.

3.1 Parser — kuvio­puun rakentaminen

Parser tunnistaa pattern recognitionin PATTERN-lausekkeen läsnäolosta ikkuna­määrittelyn sisällä. Sen ensimmäinen tehtävä on kehys­validointi, sillä RPR asettaa rajoituksia, joita tavalliset ikkuna­kyselyt eivät: kehys­tilan on oltava ROWS (ei RANGE tai GROUPS), aloituksen on oltava CURRENT ROW, lopun on oltava UNBOUNDED FOLLOWING tai positiivinen siirtymä FOLLOWING (joten myös oletuskehys hylätään), eikä muita EXCLUDE-vaihtoehtoja kuin EXCLUDE NO OTHERS sallita. Nämä ovat standardin­mukaisuus­tarkistuksia, eivät optimointeja — RPR:n käsitys kehyksestä on osuman jänne, eikä standardi harkitse sen täyttämistä mitään muuta kuin täsmättyjä rivejä.

Kun kehys läpäisee validoinnin, parser muuttaa PATTERN-lausekkeen puuksi, joka rakentuu neljästä solmu­tyypistä — muuttuja­viittaus, jono (konkatenaatio), vaihtoehto ja ryhmä (sulkeisiin koottu alikuvio). Kukin solmu kantaa kvanttoria kolmena lukuna — alaraja, yläraja (mahdollisesti ääretön) ja lippu vastahakoiselle täsmäykselle:

LähdePuu­koodaus
AVAR(A, min=1, max=1)
A+VAR(A, min=1, max=∞)
A*VAR(A, min=0, max=∞)
A{3,5}VAR(A, min=3, max=5)
A+?VAR(A, min=1, max=∞, reluctant=true)

Kukin DEFINE-predikaatti tyyppi­tarkistetaan sitten partition sarakkeita vasten ja pakotetaan Boolen lausekkeeksi. Tästä seuraa kaksi käytännön asiaa. Ensinnäkin jäsennys­analyysi ei lisää DEFINE:n vuoksi mitään kyselyn kohde­listaan; sen sijaan suunnittelija merkitsee jokaisen DEFINE-predikaatin viittaaman sarakkeen tarpeelliseksi, kuten se tekee HAVING:lle, ja välittää nämä sarakkeet executor-vaiheelle, vaikka ympäröivä kysely ei niitä valitsisikaan — ilman tätä ajoajalla ei olisi mitään, mitä vasten arvioida. Toiseksi muuttujat, jotka esiintyvät PATTERN:ssa mutta eivät koskaan DEFINE:ssa, ovat implisiittisesti tosia: ne täsmäävät jokaiseen riviin.

3.2 Käännös — AST:stä litteäksi NFA:ksi

Suunnittelija muuttaa parserin puun siksi tieto­rakenteeksi, jonka executor ajaa: indeksoiduksi litteäksi kuvio­elementtien taulukoksi. Käännös etenee kuusi­vaiheisena putkena:

compile(astTree):
  1. optimoi AST
  2. mittaa koko ja syvyys
  3. varaa elementti­taulukko
  4. täytä AST:stä
       (aseta next/jump-osoittimet)
  5. viimeistele — aseta FIN-sentinel
  6. merkitse absorptio­kelpoiset elementit

Litteä muoto on valittu yksinkertaisesta syystä: executorin on käytävä kuvio läpi monta kertaa partitiota kohden, ja yhtenäinen indeksoitava taulukko on halvin tieto­rakenne kävellä. Vaiheet 1 ja 6 ovat mielenkiintoisia — vaihe 1, koska se määrää taulukon koon, ja vaihe 6, koska se päättää, otetaanko §2.5:n absorptio­optimointi ylipäätään käyttöön.

AST-optimointi

Optimointi hyödyttää kahdesti: kerran litteän taulukon staattisessa elementti­määrässä ja uudelleen jokaisella ajoaikana käsiteltävällä rivillä. Jokainen muunnos pienentää tila-avaruutta, joka ajoajan on lueteltava. Optimoija soveltaa yhdeksää uudelleen­kirjoitus­sääntöä yhdellä alhaalta ylös etenevällä läpikäynnillä (jonon sisällä ryhmien yhdistäminen ajetaan vielä kerran, koska aiemmat yhdistämiset voivat tuoda kaksi identtistä ryhmää vierekkäin):

SEQ-litistys
SEQ(A, SEQ(B, C)) → SEQ(A, B, C)
Peräkkäisten muuttujien yhdistäminen
A A → A{2}
A{2,3} A{1,2} → A{3,5}
Peräkkäisten ryhmien yhdistäminen
(A B)+ (A B)+ → (A B){2,∞}
Peräkkäisten ALT-vaihtoehtojen yhdistäminen
(A | B) (A | B) (A | B) → (A | B){3}
Etu-/jälkiliitteen yhdistäminen
A B (A B)+ → (A B){2,∞}
ALT-litistys ja poisto­duplikointi
(A | (B | C)) → (A | B | C)
(A | B | A) → (A | B)
Kvanttorin kertominen
(A+)+ → A+
(A{2,3}){5} → A{10,15}
Yhden lapsen purku
SEQ(A) → A
(A){1,1} → A
Vastahakoisuuden normalisointi
A{2}? → A{2} (vastahakoisuus poistetaan aina, kun min = max)

Kvanttorin kertominen tiivistää vain, kun saavutettavat laskurit muodostavat yhden yhtenäisen välin eikä suosittu osuma siirry: tarkka ulompi ((A{2,3}){5} → A{10,15}), lapsi, jonka min on 0, tai toisiaan koskettavat lapsen välit, kun lapsen min on enintään 1 tai lapsen max on rajaton ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), jolloin ulompi, jonka min on 0, vaatii lisäksi lapsen min:n olevan enintään 1 ((A{2,})* säilyy, koska A* hyväksyisi yhden rivin). Ryhmälapsella, jonka oma kvanttori ei ole tarkka, on ensin oltava kiinteäpituinen runko, joten ((A | B B){1,2}){2} säilyy koskemattomana tarkankin ulomman alla. Muut yhdistelmät voivat tuoda aukkoja, jotka litteä muoto sivuuttaisi — esim. (A{2}){2,3} hyväksyy vain {4, 6}, mutta naiivi A{4,6} hyväksyisi myös 5:n — tai siirtää suosittua osumaa ((A{2,3}){1,2} suosii kolmea riviä, kun A{2,6} ottaa neljä), joten optimoija jättää ne koskemattomiksi. Se ei ole ainoa ehdollinen uudelleen­kirjoitus: ryhmien yhdistäminen ja jälkiliitteen yhdistäminen vaativat rungon, joka kuluttaa kiinteän määrän rivejä, etuliitteen yhdistäminen hylkää ryhmän, jonka min on 0, max äärellinen ja sisältö nullattavissa, vastahakoisia solmuja ei yhdistetä eikä kerrota ((A+?)+ säilyy), ja uudelleen­kirjoitus, jonka uusi raja ylivuotaisi, hylätään.

Elementin muoto

Litteän taulukon kukin elementti edustaa yhtä paikkaa kuviossa. Loogisia tyyppejä on kuusi: muuttuja­viittaus (ainoa, joka kuluttaa rivin); ryhmän alku- ja ryhmän loppu-merkit, jotka avaavat ja sulkevat sulkeisiin kootun alikuvion; vaihtoehto­merkki, joka aloittaa haarojen listan; haaran erotin, joka päättää kunkin haaran; ja lopetus­merkki kuvion lopussa.

Jokainen elementti kantaa myös syvyyttä (ryhmän sisäkkäisyys­tasonsa), kvanttorin (min- ja max-toistolaskuri, mahdollisesti ääretön) ja kaksi siirtymä­osoitinta — next, ”minne mennä tämän elementin kuluttamisen jälkeen”, ja jump, ”minne hypätä” (käyttävät vaihtoehto­merkki ja haaran erottimet haarojen ketjuttamiseen, ryhmän alku oman ryhmän loppunsa nimeämiseen — ryhmä, jonka kvanttori sallii nollan, ohitetaan tämän lopun next-osoittimen kautta — ja ryhmän loppu silmukointiin runkoon takaisin).

Kuviolle PATTERN ((A B)+) käännetty taulukko näyttää tältä:

PATTERN ((A B)+) kääntyy muotoon:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 3
    (avaa ryhmän; jump nimeää
     oman END:nsä)

[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
    (sulkee ryhmän; jump silmukoi takaisin)

[4] FIN    kuvio valmis

Kuvio luetaan vasemmalta oikealle next-osoittimen kautta, ja jump hoitaa ei-lineaariset särmät. Indeksissä 3 END:n jump osoittaa takaisin indeksiin 1, jolla rajaton ulompi kvanttori silmukoituu; indeksissä 0 BEGIN:n jump nimeää sen END:n indeksissä 3, ja jos ryhmä olisi valinnainen, ohitus poistuisi tuon END:n next-osoittimen kautta indeksiin 4 saapumatta END:iin. Ajoajan ei tarvitse rakentaa ajoaikana mitään verkkoa — se yksinkertaisesti seuraa näitä kahta osoitinta kävellessään taulukkoa.

Elementti­kohtaiset attribuutit

Muodon lisäksi kukin elementti kantaa viisi loogista attribuuttia, jotka ohjaavat ajoajan toimintaa kyseisessä paikassa:

Vastahakoinen
Kääntää kvanttorin laajennuksen järjestyksen. Ahneet kvanttorit yrittävät ”silmukoi vielä” ennen ”poistu”; vastahakoiset yrittävät ensin ”poistu”. Kantaa muuttuja kuviolle A+?; kantavat ryhmän BEGIN ja END kuviolle ((…)+?).
Tyhjä­silmukoituva
Asetetaan ryhmien lopuille, joiden runko on nullattavissa ((A? B?)+, (A | B*)+; (A?)* kerrotaan ensin muotoon A* eikä siitä jää ryhmän loppua). Käskee ajoaikaa lisäämään pikahyppy­poistuman normaalin silmukka­takaisin­paluun rinnalle alarajan alapuolella, jotta sykli­vahti ei tapa laillisia osumia ryhmissä, jotka voivat tuottaa tyhjiä iteraatioita.
Tyhjää suosiva
Asetetaan ryhmien lopuille, joiden runko suosii tyhjää osumaa, kuten (A?? B??){2}:ssa. Järjestää pikahyppy­poistuman silmukka­takaisin­paluun edelle alarajan alapuolella, missä ryhmän oma ahneus ei sano mitään.
Absorboituvalla alueella
Merkitsee jokaisen elementin, joka sijaitsee absorptio­kelpoisen alueen sisällä — käytetään ajoajassa seuraamaan, onko nykyinen tila yhä turvallisella alueella.
Absorption vertailupiste
Merkitsee sen elementin, jossa absorptio­vertailut tulisi suorittaa. Yksinkertaiselle A+:lle se osuu muuttujaan; rajattomalle ryhmälle kuten (A B)+ se osuu pelkästään ryhmän loppuun.

Erottelu ”alueella” ja ”vertailupiste” on tärkeä, koska absorptio on mielekäs vain pisteissä, joissa iteraatiot sulkeutuvat. Ryhmän (A B)+ rungon sisällä ajoaika on kesken iteraation eikä laskuri ole vielä saavuttanut lopullista arvoaan kierroksellaan; vertailu täällä tarkoittaisi vertailua keskenään vertailukelvottomien arvojen kesken. Tilan on saavutettava ryhmän loppu ennen kuin ajoaika voi päättää. Ensimmäinen attribuutti siten sanoo ”olet yhä absorboituvalla alueella”; toinen sanoo ”olet saavuttanut vertailupisteen — tarkista nyt”.

Absorboituvuus­analyysi

Käännöksen vaihe 6 antaa §2.5:n ”sama kohtalo” -säännölle sen käännös­aikaisen todistajan. Päätös on kerroksellinen:

isAbsorbable(query):
  jos SKIP-tila != SKIP PAST LAST ROW
      → palauta false
  jos kehyksen loppu != UNBOUNDED FOLLOWING
      → palauta false
  jos jokin DEFINE riippuu match_startista
      → palauta false
  käy litteä taulukko läpi
  elementistä 0 ja merkitse
  rakenteellisen tapauksen
  täyttävät elementit

Ensimmäiset kolme tarkistusta ovat kysely­tasoisia: ne vastaavat täsmälleen §2.7:n (tulostepuoli: SKIP-tila), rajatun kehyksen (rajat rikkovat monotoniaa) ja §2.6:n (datapuoli: FIRST tai siirtymällinen LAST DEFINE:ssa) ehtoja. Kun jokin epäonnistuu, analyysi ei aseta lippuja ja absorptio kytketään pois koko kyselyn osalta. Kun kaikki läpäisevät, läpikäynti hyväksyy neljä rakenteellista muotoa:

Tapaus 1 — Yksinkertainen rajaton muuttuja
A+, A*, A{2,∞}
Kukin iteraatio on tasan yksi rivi. Aiemman kontekstin laskuri on aina ≥ myöhemmän jokaisessa jaetussa paikassa.
Tapaus 2 — Kiinteäpituinen ryhmä, rajaton ulompi
(A B)+, (A B{2})+, ((A (B C){2}){2})+
Jokaisella lapsella on min == max, joten runko on semanttisesti vastaava kuin auki kierrettynä {1,1}-muotonaan — (A B{2})+ käyttäytyy kuin (A B B)+. Kukin iteraatio kuluttaa kiinteän määrän rivejä; laskurin dominanssi pätee yhä.
Tapaus 3 — Ryhmä, jonka runko alkaa rajattomalla muuttujalla
(A+ B)+, (A+ B){2}
Johtava rajaton muuttuja on itse absorboituva (tapaus 1) ja suojaa aiempia konteksteja. Absorptio pysähtyy heti, kun tila siirtyy A:n ohi — rungon loppuosalla ei ole monotonia­takeita, joten A saa molemmat liput, ympäröivä BEGIN saa alue­lipun, eivätkä B ja END saa kumpaakaan.
Tapaus 4 — Vaihtoehto
A+ | B+, A+ | C D
Kukin haara, johon päästään erotin­ketjun kautta, arvioidaan erikseen yllä olevien tapausten mukaan; vaihtoehto­merkki saa alue­lipun, kun jokin haara kelpaa.

Näiden neljän muodon ulkopuoliset rakenteet ovat yhtä opettavaisia. A B+ ei absorboidu nykyisellä säännöllä, koska johtava A kuluttaa rivin ennen rajattoman osan alkua, joten yhden rivin etäisyydellä alkavat kontekstit ovat eri kohdissa rajattoman rungon sisällä. Vastahakoiset kvanttorit kuten A+? on rajattu rakenteellisesti pois: absorptio­sääntö olettaa ahneen semantiikan, jossa pidemmät osumat sulkevat lyhyempiä, ja vastahakoinen täsmäys kääntää tämän suunnan.

Tulos on elementti­kohtainen päätös, ei kuvio­kohtainen. Yksittäisellä kysely­suunnitelmalla absorptio voi olla käytössä kuvioiden kuten (A+ B+ C) tai (A+ B+)+ johtavassa A+:ssa — jälkimmäinen on vain tapauksen 3 sovellus johtavaan elementtiin — ja pois käytöstä kaikessa sen jälkeisessä; ajoaika konsultoi kerran absorptio­kierroksen harkitessaan vain nykyisen tilan elementin vertailupiste­attribuuttia. Kun tila siirtyy ei-absorptiokelpoiseen alueeseen, absorptio on pysyvästi pois käytöstä kyseiselle tilalle — täsmälleen sitä, mitä §2.5:n ja §2.6:n on oltava algoritmisella tasolla totta.

3.3 Navigointi — yhden paikan tuple-vaihto

DEFINE-lausekkeet ovat tavallisia SQL-lausekkeita, jotka arvioidaan riviä vasten, mutta ne voivat sisältää PREV-, NEXT-, FIRST- tai LAST-funktioita — viittauksia, jotka osoittavat eri riviin. Itse rivit on jo puskuroitu ikkunan tuplestoreen; mitä executor joutuu vielä hallitsemaan, on tuplelle varattu paikka, josta SQL-lauseke­koneisto lukee, sillä lausekkeen sarakeviittaukset on sidottu paikkaan suunnittelu­aikana. Toteutus käyttää uudelleen yhtä navigointi­paikkaa jokaiselle navigointi­kutsulle: paikka vaihdetaan paikalleen ennen sisemmän lausekkeen arviointia ja palautetaan jälkeenpäin, joten muu SQL-lauseke­koneisto ei huomaa eroa.

Executorin näkemä malli on pieni: on nykyisen rivin paikka, joka pitää sitä riviä, jota vasten DEFINE-lauseketta arvioidaan, ja navigointi­paikka, jonka ajoaika voi tilapäisesti uudelleen­ohjata toiseen riviin. Kunkin navigointi­kutsun ympärillä ajoaika valmistelee navigointi­paikan, arvioi sisemmän lausekkeen ikään kuin se lukisi nykyistä riviä ja palauttaa sitten alkuperäisen rivin. Pseudokoodi:

eval_navigation(call):
  targetPos = laske_kohdepaikka(call)
  jos targetPos on validin alueensa ulkopuolella:
      palauta NULL

  tallenna current_row_slot
  jos targetPos != currentPos:
      hae rivi paikasta targetPos
        paikkaan nav_slot
      osoita ulompi paikka nav_slotiin
  result = arvioi_sisempi_lauseke()
  palauta current_row_slot
  kopioi viittaustyyppinen tulos nav_slotista
  return result

Niksinä on, että tallennettavia ja palautettavia paikkoja on tasan yksi. Sisempi lauseke — mikä tahansa se onkin, mukaan lukien aritmetiikka, funktiokutsut tai muut sarakeviittaukset — ajetaan vaihdettua paikkaa vasten samaa arviointi­polkua käyttäen kuin nykyiselle riville. Ei vaihtoehtoista arvioijaa eikä paikkaa viittausta kohden; kun kohde on nykyinen rivi, haku ja vaihto ohitetaan kokonaan. Haku kopioi kohderivin navigointi­paikkaan (ellei paikka jo pidä sitä), ja palautus­vaihe kopioi viittauksena välitettävän tuloksen tuplekohtaiseen muistiin, jotta seuraava haku ei voi vapauttaa sitä.

Yhdistetty navigointi litistetään jäsennys­aikana niin, että vaihto tapahtuu yhä kerran. PREV(FIRST(price)) tunnistetaan kaksi­vaiheiseksi navigoinniksi — ”siirry ensimmäiseen täsmättyyn riviin ja astu sitten yksi rivi taaksepäin” — ja tallennetaan yhtenä yhdistetyn tyypin navigointi­kutsuna. Ajoaika laskee kohde­paikan kahdessa vaiheessa mutta tekee vain yhden paikka­vaihdon hakeakseen lopullisen rivin:

compute_target_position(call):

  # nykyiseen riviin suhteutettu
  PREV(n):
      palauta currentPos − n
  NEXT(n):
      palauta currentPos + n

  # osumaan suhteutettu
  FIRST(n):
      palauta matchStart + n
  LAST(n):
      palauta currentPos − n

  # yhdistetty: osumaan suhteutettu, sitten askel
  PREV(FIRST(n), m):
      palauta (matchStart + n) − m
  NEXT(FIRST(n), m):
      palauta (matchStart + n) + m
  PREV(LAST(n), m):
      palauta (currentPos − n) − m
  NEXT(LAST(n), m):
      palauta (currentPos − n) + m

  validoi sopivaa aluetta vasten
  (osuma-alue FIRST/LAST-sisempään,
   partitio-alue ulompaan askeleeseen)

Sijainti­välimuisti oikoo tuplestorehakua, kun useat saman DEFINE:n navigointi­kutsut osuvat samaan riviin — yleistä lausekkeissa kuten price > PREV(price) AND volume > PREV(volume), joissa molemmat kutsut ratkeavat edelliseen riviin. Välimuisti tallentaa vain ”viimeisimmän haetun sijainnin”, ja itse vaihto pysyy yksittäisenä operaationa.

Navigointi­kutsujen luokittelu on suunnittelijan panos absorptio­päätökseen. Suunnittelija käy läpi jokaisen DEFINE-lausekkeen ja lajittelee kunkin muuttujan toiseen kahdesta ryhmästä sen perusteella, laskevatko kaikki kontekstit saman Boolen samalla rivillä vai kukin omansa. Ryhmä määrää ajoaikana kaksi asiaa: kuinka usein muuttuja arvioidaan (kerran jaettuna vai kerran kutakin kohdetta kontekstia kohden — §3.5, vaihe 1), ja onko konteksti­absorptio ylipäätään mahdollinen (§2.5 vs §2.6): yksikin osuman alusta riippuva muuttuja kytkee sen pois koko kuviolta.

Jaettu arviointi · absorption­turvallinen Jokainen konteksti näkee saman Boolen jokaisella rivillä — sama kohtalo (§2.5).
  • Ei navigointia
  • Vain PREV / NEXT
  • LAST ilman siirtymää
  • Yhdistetty sisemmällä LAST:lla (ilman siirtymää)
Kontekstikohtainen arviointi · absorption­epäturvallinen Eri osuman alkujen kontekstit laskevat eri vastaukset — erilaiset kohtalot (§2.6).
  • LAST siirtymällä
  • FIRST (mikä tahansa muoto)
  • Yhdistetty sisemmällä FIRST:llä
  • Yhdistetty sisemmällä LAST:lla (siirtymällä)

Luokittelu suoritetaan suunnittelu­aikana ja tallennetaan kunkin DEFINE-muuttujan oheen, joten ajoaika ei käytä aikaa päättämiseen — se yksinkertaisesti lukee ryhmän kunkin muuttujan kohdalla rivin käsittelyssä.

Säilytys­budjetti

Navigointi ulottuu riveihin, jotka ikkunafunktio­koneisto on muuten jo virrannut ohitse. Pitääkseen nuo rivit saatavilla executor on rakennettu sellaisen tuplestoren päälle, joka säilyttää liukuvan ikkunan tuoreita rivejä; kysymys on, kuinka leveä ikkunan on oltava. Executor selvittää sen kahden täydentävän siirtymän perusteella ja ratkaisee jokaisen siirtymän kerran skannausta kohden (vakiosiirtymät myös executorin alustuksessa, jotta pelkkä EXPLAIN voi näyttää ne):

Taakse­katsonta­budjetti
Kuinka kauas taakse nykyisestä rivistä jokin DEFINE-kutsu voisi yltää.
Vaikuttavat: PREV, LAST (mikä tahansa siirtymä, myös oletus 0), PREV(LAST(...)), NEXT(LAST(...))
Eteenpäin-osuman-alusta -budjetti
Pienin ulottuma eteenpäin (taakse, jos negatiivinen) vanhimman elävän kontekstin osuman alusta — varhaisin rivi, jota jokin DEFINE-kutsu voisi tarvita.
Vaikuttavat: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

Ajoaikana tuplestoren leikkaus­merkki asetetaan kahdesta sijainnista varhaisempaan — nykyinen rivi miinus taakse­katsonta­budjetti ja vanhimman elävän kontekstin osuman alku plus eteenpäin­katsonta­budjetti. Mitään ennen tätä merkkiä ei voi saavuttaa millään navigointi­kutsulla missään elävässä kontekstissa, ja tuplestore voi vapaasti pudottaa sen. EXPLAIN:n raportoimat Nav Mark -rivit (§3.7) — Lookback ja Lookahead — ovat nämä kaksi budjettia, eivät mitattuja huippuja. Kumpikin tulostetaan vain, kun jokin navigointi syöttää sitä, ja se näytetään myös ilman ANALYZE:ta; siirtymä, jonka arvo tiedetään vasta ajoaikana (esimerkiksi geneerisen suunnitelman parametri), tulostuu pelkässä EXPLAINissa muodossa runtime ja EXPLAIN ANALYZEssa ratkaistuna arvonaan, ja retain all (Lookback) tai infinite (Lookahead) merkitsee ylivuotavaa siirtymää.

3.4 Osuman rajat — SKIP, INITIAL ja rajattu kehys

Osuman tulos kirjataan kahtena arvona: rivi, jossa osuma alkaa, ja sen pituus. Negatiivinen alku tarkoittaa, ettei paikkaa ole vielä arvioitu; kun alku on asetettu, executorin myöhemmät kyselyt — ”onko tämä rivi osuman sisällä?” — voivat vastata O(1):ssä tarkastamalla parin. Pituus koodaa lopputuloksen: -1 täsmäämättömälle riville, 0 tyhjälle osumalle ja rivimäärä todelliselle osumalle. Pituus nolla on todellinen lopputulos, ei virhe: se edustaa kuviota, joka täsmäsi kuluttamatta yhtään riviä, ja tämä executorin on erotettava sekä täsmäämättömästä rivistä että tilanteesta ”tässä paikassa ei ole vielä yritetty osumaa”.

AFTER MATCH SKIP -lauseke päättää, mistä seuraava osuma­yritys alkaa. AFTER MATCH SKIP PAST LAST ROW siirtyy osuman lopun jälkeiselle riville tuottaen ei-päällekkäisen tulosteen, jonka useimmat kyselyt haluavat, ja mahdollistaen absorptio­optimoinnin.

AFTER MATCH SKIP TO NEXT ROW siirtyy vain osuman alun jälkeiselle riville sallien päällekkäiset osumat; suunnittelija kytkee tällöin absorption pois käytöstä kyseisen ikkunan kuviolta.

Kaksi muuta standardin määrittelemää ohitus­kohdetta — AFTER MATCH SKIP TO FIRST var ja AFTER MATCH SKIP TO LAST var — riippuvat osumakohtaisesta historiasta, jota tämä korjauspaketti ei säilytä. Niitä ei ole kieliopissa lainkaan, joten parser nostaa yleisen syntaksi­virheen, jos jompikumpi annetaan.

Sama pätee SEEK:iin, spesifikaation vaihtoehtoon INITIAL:lle. SEEK:in alla rivillä R alkava osuma­yritys voi onnistua millä tahansa rivillä R:stä kehyksen loppuun, ei vain itse R:llä. Korjauspaketti toteuttaa vain INITIAL:n: jokainen mahdollinen osuma kiinnittyy tiettyyn riviin. Parser nostaa virheen, jos SEEK:iä pyydetään. Rajatut kehykset saavat oman käsittelynsä — kun käyttäjä kirjoittaa ROWS BETWEEN CURRENT ROW AND N FOLLOWING eikä UNBOUNDED FOLLOWING, executor oikoo jokaista kontekstia, jonka osuma on saavuttanut rajan, pakottamalla epätäsmäyksen, ja absorptio kytketään pois, koska raja rikkoo monotonia­oletuksen, johon absorptio nojaa.

3.5 Kolmi­vaihelainen rivi­kohtainen moottori

Executorin rivi­kohtainen ajuri kutsutaan ympäröivästä ikkunafunktio­koneistosta aina, kun sen on tiedettävä, kuuluuko tietty rivi täsmättyyn kehykseen. Ajuri löytää tai luo nykyisen aloitus­paikan kontekstin ja vie sitten NFA:ta eteenpäin rivi riviltä — nollaten muuttuja­kohtaisen täsmäys­taulukon tilaan ”arvioimaton” kullekin riville — kunnes tuolla kontekstilla ei ole enää eläviä tiloja tai partitio päättyy. DEFINE-predikaatit arvioidaan laiskasti: muuttuja arvioidaan, kun jokin tila kuluttaa sen ensimmäisen kerran, joten muuttujaa, jota yksikään elävä tila ei tällä rivillä testaa, ei koskaan arvioida. Eteenpäin vievä askel itse koostuu kolmesta vaiheesta kiinteässä järjestyksessä — Match, Absorb, Advance — saman ulomman silmukan sisällä:

processRow(currentPos):

  # Vaihe 1 — MATCH (konvergenssi)
  jokaiselle kontekstille:
      jos konteksti saavutti kehyksensä lopun:
          pakota epätäsmäys (vahvista aikaisin)
          jatka
      jos matchStartRow eroaa
         jaetusta arviointi­paikasta:
          nollaa osuma-alku-riippuvaiset
          DEFINE-muuttujat arvioimattomiksi (§3.3)
      match(context, varMatched)

  # Vaihe 2 — ABSORB
  jos kuvio on absorboituva:
      virkistä kunkin kontekstin liput
      absorb_contexts()

  # Vaihe 3 — ADVANCE (divergenssi)
  jokaiselle kontekstille:
      advance(context, currentPos)
      jos se kirjasi osuman ja
         SKIP PAST LAST ROW:
          karsi myöhemmät kontekstit,
          jotka alkavat osuman sisältä

Järjestys ei ole tyylikysymys. Matchin on ajettava ensin, koska absorptio vertaa match-jälkeisiä laskureita; Absorbin ajaminen ennen Matchia vertaisi tiloja, jotka ovat juuri kuolemaisillaan. Advancen on ajettava viimeisenä, koska se on ainoa vaihe, joka luo uusia tiloja — se laajentaa jokaisen säilyneen tilan epsilon-siirtymillä, kunnes jokainen saavuttaa muuttujan, joka odottaa seuraavaa riviä. Absorbin ajaminen Advancen jälkeen tarkoittaisi eronneiden seuraajien vertailua ja sen pisteen ohittamista, jossa tilat ovat puhtaimmin vertailtavissa.

Vaihe 1 — Match

Match on ”konvergenssi”-vaihe: tilat joko säilyvät kasvatetulla laskurilla tai kuolevat. Hienovarainen seikka on, että absorboituvalla alueella istuville muuttujille Match suorittaa myös pienen määrän eteenpäin etenevää työtä, jotta Absorb voi vertailla puhtaasti. Peittävyys­ehto laukeaa vain absorboituvassa vertailupisteessä — rajattoman ryhmän END:ssä — joten juuri välirivi­muuttujiin täsmänneet tilat (kuten B ryhmän (A B)+ sisällä) on kävelytettävä vertailupisteeseen Matchin aikana; muuten Absorb ei löydä mitään vertailuun kelpaavaa eikä optimointi koskaan kytkeydy.

match(context, varMatched):
  jokaiselle tilalle kontekstissa:
      elem = pattern[state.elemIdx]
      vakuuta, että elem on muuttuja
          # advance pysäköi vain muuttujia

      jos varMatched[elem.varId] on
         arvioimaton:
          arvioi sen DEFINE nyt
      jos ei varMatched[elem.varId]:
          pudota tila   # kuollut haara
          jatka

      state.counts[elem.depth] += 1

      # Inline-eteneminen, jotta
      # seuraava vaihe voi vertailla
      # vertailupiste-elementissä
      # iteraation keskikohdan sijaan.
      jos elem on alueella mutta ei
         vertailupisteessä,
         ja saavutti max-laskurinsa,
         ja elem.next on ryhmän loppu:

          käy END-ketju:
            kasvata ulomman ryhmän laskuria
            etene state.elemIdx END:iin
            jatka kunnes yhä alueella,
              must-exit, ja next on END
          (pysähtyy vertailupisteessä
           tai vielä silmukoituvassa elementissä)

END-ketjun kävely tekee sisäkkäisistä kiinteäpituisista ryhmistä absorboituvia. Ryhmässä ((A B){2})+, kun B saavuttaa max-arvonsa (B on {1,1}), sisemmän ryhmän laskurin on kasvettava; jos myös tuo laskuri saavuttaa max-arvonsa — sulkien sisemmän {2}:n — myös ulomman ryhmän laskurin on kasvettava, ja niin edelleen, kunnes tila osuu uloimpaan absorptio­pisteeseen — rajattoman ulomman ryhmän (+:n) END:iin. Tämän työn tekeminen Matchissa antaa Absorbin verrata konteksteja, jotka ovat jo konsolidoineet iteraation jälkeiset laskurinsa.

Vaihe 2 — Absorb

Absorb-vaihe käy kontekstit läpi uusimmasta (häntä) vanhimpaan (pää). Jokaiselle kesken olevalle täysin absorboituvalle kontekstille se etsii taaksepäin vanhempaa kesken olevaa kontekstia, joka peittää sen, ja vapauttaa uudemman, jos sellainen löytyy. Koska kontekstit pidetään luonti­järjestyksessä ja kukin rivi luo enintään yhden kontekstin, ”uudempi” ja ”vanhempi” tarkoittavat todella ”alkanut myöhemmin” ja ”alkanut aikaisemmin”.

absorb_contexts():
  ctx hännästä taaksepäin:
      jos ctx on valmis
         tai siinä on yhtään ei-absorboituvaa tilaa
         tai siinä on kirjattu osuma:
          ohita
      older ctx.prev:stä taaksepäin:
          jos older on valmis
             tai siinä ei ole absorboituvaa tilaa:
              ohita
          jos covered(older, ctx):
              free(ctx)
              kirjaa absorboinnin pituus
              katkaise

covered(older, newer):
  jokaiselle tilalle newer:ssa:
      elem = pattern[state.elemIdx]
      jos elem ei ole vertailupiste:
          palauta false
      jos older:ssa ei ole tilaa, jolla:
            sama elemIdx
            ja isAbsorbable
            ja older.counts[depth]
                >= newer.counts[depth]:
          palauta false
  palauta true

Tästä seuraa kaksi mikropäätöstä. Ensimmäinen on, että peittävyys­tarkistus hylkää välittömästi, jos uudemman kontekstin jokin tila istuu muualla kuin vertailupisteessä — vertailu ei-päätös­pisteissä ei olisi mielekäs vertailu.

Toinen on epäsymmetrinen lippu­pari kussakin kontekstissa: has-absorbable-state vastaa kysymykseen ”voisiko tämä konteksti absorboida uudemman?” ja on monotoninen (se voi vain mennä true→false tilojen kuollessa), kun taas all-states-absorbable vastaa kysymykseen ”voitaisiinko tämä konteksti absorboida?” ja on dynaaminen (se palaa todeksi, kun ei-absorboituva tila poistetaan), kunnes konteksti kirjaa osuman, mikä kiinnittää sen epätodeksi — absorboiminen vapauttaisi osuman, jota mikään absorboiva konteksti ei voi toistaa. Molemmat liput tarkistetaan vakio­ajassa ennen kuin peittävyys­skannaus edes alkaa, joten absorptio maksaa täyden hintansa vain konteksteilta, joilla on todellinen mahdollisuus tulla absorboiduksi.

Vaihe 3 — Advance

Advance on ”divergenssi”-vaihe: jokainen säilynyt tila laajennetaan epsilon-siirtymillä, kunnes jokainen haara saavuttaa joko muuttujan, joka odottaa seuraavaa riviä, tai FIN-sentinelin. Laajennus on syvyys­painotteinen, ja sisko­haarojen kävely­järjestys on se, mikä saa standardin suosinta­säännön todella vaikuttamaan — leksikaalisesti ensimmäinen haara lisätään aina ensin, ja tilan lisäyksen poisto­duplikointi­vaihe hylkää hiljaisesti vastaavat myöhemmät lisäykset.

advance(context, currentPos):
  poimi kaikki nykyiset tilat;
  rakenna ctx.states alusta uudelleen
  jokaiselle tilalle leksikaalisessa järjestyksessä:
      tyhjennä käyty-bittikartta
      advance_state(state)   # DFS

      # Suosinta: kun DFS saavuttaa FIN:in,
      # jäljellä olevat tilat ovat vähemmän
      # suositeltuja ja voidaan pudottaa.
      jos FIN saavutettu ja tiloja jää:
          vapauta loput
          katkaise

advance_state(state):
  kävele state.elemIdx kautta,
  rekursoi:
    ALT-haarat (järjestyksessä, pysähtyen
                kun FIN on kirjattu),
    BEGIN (siirry ryhmään; lisäksi valinnainen
           ohitus­polku jos min = 0),
    END (silmukoi takaisin / poistu / pikahyppy —
         ks. alla),
    FIN (kirjaa matchEndRow,
         tallenna matchedState, ja merkitse
         konteksti, jotta myöhemmät
         kontekstit tämän kandidaatin
         alueen sisältä karsitaan — ks. alla),
  pysähtyen jokaisen kohdatun muuttujan kohdalla:
      lisää tila ctx.states:hin
      (poisto­duplikoiden elemIdx + counts perusteella)

FIN:in saavuttaneen tilan kirjaaminen tekee enemmän kuin merkitsee kandidaatti­osuman. AFTER MATCH SKIP PAST LAST ROW:n alla seuraavan raportoitavan osuman on alettava tiukasti nykyisen jälkeen — joten kun Advance on käsitellyt kandidaatin kirjanneen kontekstin, jokainen myöhempi konteksti, jonka alkurivi osuu kandidaatin alueen sisään, karsitaan samalla rivillä, vaikka FIN:iin osunut konteksti voi jatkaa pidemmän osuman etsintää ahneen varajärjestelmän kautta.

Karsinta on turvallinen, koska riippumatta siitä, miten tuo etsintä päättyy (pidempi osuma korvaa kandidaatin tai kandidaatti pysyy), kaikki karsitut kontekstit alkoivat alueella, jonka seuraavan raportoitavan osuman on ohitettava, eivätkä siten voisi koskaan tuottaa omaa tulostettaan.

Tämä on kontekstien välinen FIN-aikainen karsinta­vaihe. Kontekstin sisällä FIN katkaisee myös leksikaalisesti alempi­arvoisen työn: Advance pudottaa jonossa jäljellä olevat tilat (kuvattu aiemmin tässä osiossa), ja yhden DFS:n sisällä jokainen vähemmän suosittu polku — myöhemmät ALT-haarat, BEGIN:n ohitus- ja sisääntulo­poluista toinen, vastahakoisen muuttujan sisääntulo­polku, END:n silmukka- ja poistumis­poluista toinen — pysähtyy, kun osuma on kirjattu, joten yksi advance kirjaa enintään yhden osuman.

Vaikein elementti­kohtainen logiikka asuu END-käsittelijässä. Kun ryhmän iteraatio­laskuri on alarajan alapuolella, ajoajan on silmukoitava takaisin; kun se on ylärajalla tai sen yli, sen on poistuttava; siltä väliltä molemmat vaihtoehdot ovat kelvollisia ja kvanttorin ahneus päättää, kumpi yritetään ensin:

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

  jos count < elem.min:
      silmukoi takaisin runkoon
      jos elem on tyhjä­silmukoituva:
          # nullattava runko, ks. §3.2
          kloonaa myös pikahyppy­tila,
          joka poistuu ryhmästä
          laskurin täyttyneenä
          (pikahyppy ensin, jos runko
           suosii tyhjää; toinen polku
           pudotetaan, jos ensimmäinen
           saavutti FIN:in)

  muuten jos count >= elem.max:
      nollaa tämän syvyyden laskurit
      poistu next:n kautta
      (END→END: kasvata ulomman
       END:n laskuria)

  muuten:
      # min <= count < max: haaroita
      rakenna poistumis­tila
      (laskurit tällä syvyydellä nollataan)
      jos ahne:
          silmukoi ensin
          jos silmukka saavutti FIN:in:
              pudota poistuminen
              # suosii pidempää
          muuten poistu toisena
      muuten (vastahakoinen):
          poistu ensin
          jos poistuminen saavutti FIN:in:
              pudota silmukka
              # suosii lyhyempää
          muuten silmukoi toisena

Jokainen kontekstiin lisätty tila käy läpi poisto­duplikointi­tarkistuksen, joka vertaa sen sijaintia ja laskureita olemassa olevaan tila­listaan. Koska Advance käsittelee haarat DFS-järjestyksessä, minkä tahansa vaihtoehdon ensimmäisen haaran tila lisätään ensin — ja mikä tahansa myöhempi haara, joka tuottaa saman sijainnin ja laskurit, hylätään lisäyksessä. Juuri tätä §2.4:n leksikaalinen järjestys -sääntö pyytää, toteutettuna ajoajan pohjalla ilman erillistä vaihetta.

Tyhjä­silmukoituvat ryhmät

Hienovarainen tapaus, jonka ajoajan on neutraloitava, on nullattava ryhmä — ryhmä, jonka runko voi täsmätä nollaan riviin, koska jokainen rungon lapsi on itse valinnainen. Kuvioilla kuten (A? B?)+ ja (A | B*)+ on tämä ominaisuus: datasta riippuen runko voi suorittaa iteraation kuluttamatta yhtään riviä. (Yksittäinen valinnainen lapsi kuten (A?)* kirjoitetaan käännös­aikana muotoon A*, eikä siitä jää ryhmää.) Periaatteessa tämä on hyvä, mutta se luo todellisen vaaran NFA:n epsilon-laajennukselle. Jos runko tuottaa tyhjän osuman, END-elementti silmukoi takaisin runkoon (sen jump on ryhmän ensimmäinen lapsi), runko tuottaa jälleen tyhjän osuman, saavuttaa END:n uudelleen, ja niin edelleen. Ilman pysäyttäjää Advancen DFS ei koskaan päättyisi.

Vahti päätetään käännös­aikana ja toimitaan ajoaikana. Aina kun suunnittelija näkee ryhmän, jonka runko on nullattava, se merkitsee tuon ryhmän END-elementin tyhjä­silmukoituvaksi. Ajoaika pitää käyty-bittikarttaa, joka tyhjennetään ennen kunkin tilan DFS-laajennusta ja johon merkitään vain nämä merkityt END:t — mikään muu ei voi muodostaa sykliä, koska kaikki muut takaisin­silmukoinnit ovat kuluttaneet rivin. Merkityn END:n saavuttaminen tarkoittaa, että runko tuotti juuri tyhjän iteraation, eikä tilaa hylätä: alarajalla tai sen yläpuolella se poistuu ryhmästä siinä (tyhjä iteraatio pysäyttää kvanttorin), ja sen alapuolella tila valuu normaaliin silmukka­takaisinpaluuseen, joten jokainen tyhjä saapuminen kasvattaa yhä laskuria, kunnes se saavuttaa min:in. Tarkastellaan (A? B?){2,3} -kuviota, jossa kumpikaan muuttuja ei täsmää missään rivivirran kohdassa:

iter 1: A? B? täsmäävät nollaan riviin
        → END, count = 1 (alle min)
        END jo merkitty (ryhmään
        tultaessa), mutta alle min:
        → silmukoi takaisin A?:hen
iter 2: A? B? täsmäävät nollaan riviin
        → END, count = 2 (täyttää min)
        END jo merkitty, min:issä:
        → poistu ryhmästä
poistu nollapituisella osumalla

Alarajan alapuolella tyhjä­silmukka­merkintä käskee END-käsittelijää myös kloonaamaan ylimääräisen pikahyppy-tilan normaalin silmukka­takaisinpaluun rinnalle:

advance_end (count alle min:in):

  silmukka­takaisinpaluun polku:
    silmukoi takaisin runkoon
    (pitää oven auki todelliselle,
     ei-tyhjälle osumalle seuraavalla
     iteraatiolla)

  jos elem on tyhjä­silmukoituva:
    pikahyppy­polku:
      nollaa tämän syvyyden laskuri
      poistu ryhmästä next:n kautta,
      kohdellen jäljellä olevia
      vaadittuja iteraatioita
      tyhjinä osumina

Nämä kaksi polkua täydentävät toisiaan. Silmukka­takaisinpaluu nappaa tapauksen, jossa rungolla on vielä todellisia osumia tuotettavanaan myöhemmin — esimerkiksi (A? B?){2,3}:ssa, jota seuraa data, jossa A täsmää vain myöhempiin riveihin, silmukka­takaisinpaluu mahdollistaa toiselle ja kolmannelle iteraatiolle löytää ei-tyhjiä osumia. Pikahyppy poistuu ryhmästä heti, julistaen ”loput vaadituista iteraatioista ovat tyhjiä” ja sallien osuman onnistua nollapituisella rungolla. Järjestyksen ratkaisee runko, ei ryhmän oma ahneus: pikahyppy menee ensin täsmälleen silloin, kun runko suosii tyhjää osumaa (vastahakoinen runko kuten (A?? B??)), ja jos ensimmäinen polku saavuttaa FIN:in, toinen pudotetaan, joten vähemmän suosittu polku ei voi korvata suosittua osumaa. Lisäys­vaiheen poisto­duplikointi­tarkistus estää kumpaakaan polkua synnyttämästä enempää kuin osansa tiloja.

Sykli­vahdin lisäksi yksi käynnistys­kikka erottaa nolla-rivisiä lopputuloksia kontekstin alussa. Konteksti­luonti­vaihe jokaisella mahdollisella aloitus­rivillä ajaa alustavan advancen epsilon-siirtymillä ennen kuin yhtäkään riviä on kulutettu, käyttäen sijaintia, joka on yksi rivi ennen todellista alkua. Mikä tahansa polku, joka saavuttaa FIN-sentinelin pelkillä epsilon-siirtymillä — kuluttamatta riviä — tuottaa siten lopetus­sijainnin, joka on alkupaikkaa pienempi; tuo negatiivisen jännevälin koordinaatti yhdistettynä siihen, saavutettiinko FIN tosiasiassa, koodaa eron tyhjän osuman (pituus-0-osuma hyväksytty) ja täsmäämättömän alun välillä ilman erillistä lippua.

3.6 Kuinka tila-avaruus pysyy rajattuna

Ajoajan pysyminen rajattuna ei ole yhden optimoinnin tulos. Se on kerroksellisten karsinta­sääntöjen kumulatiivinen vaikutus, joista kukin nappaa eri syyn tila-avaruuden kasvulle eri kohdassa rivi­kohtaisessa syklissä. Jotkin päätetään käännös­aikana ja vain konsultoidaan ajoaikana; toiset laukeavat dynaamisesti. Jotkin tappavat yksittäisiä tiloja; toiset kokonaisia konteksteja. Yllä olevat osiot esittelivät kunkin niistä omassa yhteydessään; alla oleva taulukko kokoaa ne yhdelle sivulle.

Epäonnistunut predikaatti Match
Muuttuja­tilat, joiden DEFINE arvioitui epätodeksi nykyisellä rivillä — kuolleet haarat.
Sisäänupotettu END-ketjun edistys Match
Muuttujat, jotka ovat saavuttaneet max-laskurinsa ja jättäisivät tilan muuten iteraation keskelle; viedään läpi kiinteäpituisten ryhmien loppujen, jotta absorptio voi vertailla oikeassa kohdassa.
Konteksti­absorptio Absorb
Uudemmat kontekstit, joiden jokainen tila istuu vertailupisteessä ja on peitetty vanhemman kontekstin absorboituvalla tilalla samassa elementissä suuremmalla tai yhtä suurella laskurilla — ks. §2.5 käsitteellinen sääntö, §3.2 käännös­aikainen kelpoisuus, §3.5 pari­kohtainen tarkistus.
Tilojen poisto­duplikointi Advance
Eri DFS-haarojen kautta saavutetut tilat, jotka päätyvät samaan sijaintiin samoilla laskureilla — vain ensimmäinen (leksikaalisesti aikaisin) säilyy; myöhemmät vastaavat hylätään hiljaisesti, mikä on myös tapa, jolla suosinta toteutetaan (§2.4).
FIN-ennenaikainen päättyminen (kontekstin sisällä) Advance
Tilat, jotka ovat vielä DFS-jonossa, kun yksi haara saavuttaa FIN:in — leksikaalisen järjestyksen mukaan kaikki jäljellä olevat tilat ovat vähemmän suosittuja ja voidaan hylätä välittömästi.
Kandidaatti­osuman karsinta (kontekstien välillä) Advance
Muut kontekstit, joiden alkurivi osuu kandidaatti­osuman alueen sisään — FIN:iin osunut konteksti voi jatkaa pidemmän osuman etsintää (ahne varajärjestelmä), mutta AFTER MATCH SKIP PAST LAST ROW:n alla mikään konteksti kandidaatin alueen sisällä ei voi enää tuottaa raportoitavaa tulostetta, riippumatta siitä, miten tuo etsintä päättyy, ja se karsitaan heti, kun Advance on käsitellyt kandidaatin kirjanneen kontekstin.
Sykli­vahti Advance
Epsilon-laajennukset, jotka saavuttavat nullattavan ryhmän END:n, joka on jo merkitty saman DFS:n sisällä (merkitty BEGIN:n kautta tultaessa tai aiemmalla saapumisella) — silmukoituisivat muuten ikuisesti; tila poistuu ryhmästä siinä alarajalla tai sen yläpuolella ja jatkaa silmukointia sen alapuolella.
Tyhjä­silmukan pikahyppy Advance
Nullattavan ryhmän alarajan alapuolella ylimääräinen polku, joka poistuu ryhmästä jäljellä olevat vaaditut iteraatiot tyhjiksi julistettuna ja joka järjestetään silmukka­takaisinpaluuseen nähden rungon suosinnan mukaan.
Rajatun kehyksen katkaisu Match
Kontekstit, joiden osuma on saavuttanut käyttäjän asettaman kehyksen ylärajan — pakotetaan epätäsmäykseen, jotta ne eivät voi venyä sen yli (§3.4).

Merkintöjen lukeminen vaihe­merkin mukaan jäljittää kontekstin elinkaarta: karsinta laukeaa jokaisella rivillä kolmen pää­vaiheen läpi (Match, Absorb, Advance). Kuvauksien lukeminen sen sijaan ryhmittelee säännöt sen mukaan, mihin ne kohdistuvat: kuolleet haarat, tarpeettomat kontekstit, ekvivalentit tilat, äärettömät silmukat ja venyminen käyttäjän asettamien rajojen yli.

Yksittäinen sääntö ei riittäisi yksin. Pelkkä tyhjä­silmukan pikahyppy ei pysäyttäisi äärettömiä epsilon-silmukoita; pelkkä absorptio yli­konsolidoisi, kun DEFINE viittaa osuman alkuun; pelkkä poisto­duplikointi ei poistaisi tarpeettomia konteksteja, vain tarpeettomat tilat. Ajoaika pysyy lineaarisena merkityksellisissä tapauksissa — PATTERN (A+ B+ C+ D) 100 000 rivillä, posterin paneelin ③ benchmark — vain siksi, että jokainen kerros nappaa sen, mitä yllä olevat kerrokset päästävät läpi. Lähdekoodi dokumentoi tapaukset, joita kerrokset eivät nappaa: poisto­duplikointi pitää erillään tilat, jotka eroavat vain min:in ylittävissä laskureissa, joten (A{2,} B)+ C, jossa C ei ole koskaan tosi, pitää huipussaan Θ(n²) tilaa ja luo niitä Θ(n³) (37 s 320 rivillä), ja kokonaan nullattavien vaihtoehtojen jono luetellaan polku polulta, joten (A?|B?){30} kestää yli puoli tuntia.

3.7 EXPLAIN-tuloste

EXPLAIN ANALYZE RPR:ää käyttävälle kyselylle tuo näkyviin NFA-tasoisia tilastoja, joita ei ole tavallisissa ikkunafunktioissa. Teksti­muodossa ne annetaan ikkuna­operaattorin oheen Pattern:-rivin, mahdollisten Nav Mark -rivien (jotka myös pelkkä EXPLAIN näyttää) ja Storage:-rivin jälkeen:

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (kumpikin vain, kun DEFINE käyttää
   sitä syöttävää navigointia)
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)
  (toinen NFA-rivi vain, kun jompikumpi
   lukumäärä on nollasta poikkeava;
   nolla tulostuu ilman (len ...))

Muut kuin teksti­muodot antavat jokaisen lukumäärän omana ominaisuutenaan. Peak ja total ovat suoraa ajoajan instrumentointia: kuinka monta tilaa oli koskaan elossa samanaikaisesti, kuinka monta luotiin kyselyn elinkaaren aikana ja kuinka moni yhdistyi pois poisto­duplikoinnin kautta; pruned laskee kontekstit, jotka epäonnistuivat yhden rivin jälkeen. Osuma­pituus­histogrammit erottavat neljä lopputulosta — onnistuneet osumat, osuma­yritykset, jotka epäonnistuivat useamman kuin yhden rivin jälkeen (mismatched), absorboidut kontekstit ja kontekstit, jotka AFTER MATCH SKIP PAST LAST ROW vapautti, koska ne alkoivat kirjatun osuman sisältä (skipped) — ja niiden raportointi min/max/avg-muodossa tekee suoritus­patologiat näkyviksi yhdellä silmäyksellä: terveessä ajossa useimmat kontekstit näkyvät joko täsmättyinä tai absorboituina ja epätäsmäys­pituudet ovat pieniä.

Kaksi Nav Mark -laskuria raportoivat tuplestoren säilytys­budjetin, jonka §3.3 johtaa DEFINE:stä. Lookback on syvin nykyisestä rivistä taakse­päin ulottuva yltämä PREV:n, minkä tahansa siirtymän (myös oletuksen 0) LAST:n ja yhdistettyjen muotojen sisemmällä LAST:lla; Lookahead on pienin eteenpäin ulottuva yltämä (negatiivinen, kun se katsoo osuman alkua edeltäviin riveihin) mitattuna vanhimman elävän kontekstin osuman alusta, jonka tuottavat FIRST ja yhdistetyt muodot sisemmällä FIRST:llä.

Kukin laskuri tulostuu kiinteänä kokonaislukuna, kun siirtymä on vakio, ”runtime”, kun siirtymä on ei-vakio lauseke, joka tiedetään vasta skannauskohtaisesti, ja — vain Lookbackin osalta — ”retain all”, kun siirtymä ylivuotaa; ylivuotava Lookahead tulostuu muodossa ”infinite”. Kukin rivi annetaan vain, kun jokin DEFINE:n navigointi syöttää sitä, ja molemmat näkyvät myös pelkässä EXPLAIN:ssa: vakiosiirtymät ratkaistaan executorin alustuksessa, kun taas vasta ajoaikana tiedettävä siirtymä (esimerkiksi geneerisen suunnitelman parametri) tulostuu siellä muodossa ”runtime” ja EXPLAIN ANALYZE:ssa ratkaistuna kokonaislukuna.

Yhdessä nämä laskurit mahdollistavat RPR-suorituskyvyn vianetsinnän ilman gdb:n liittämistä taustaprosessiin.

Laskureiden lisäksi EXPLAIN tulostaa käännetystä elementti­taulukosta rakennetun Pattern:-rivin, joten se näyttää kuvion käännös­aikaisten uudelleen­kirjoitusten jälkeen (PATTERN (A A) selittyy muodossa a{2}) ja kantaa absorptio­merkit # (vertailupiste) ja ~ (absorboituva alue); DEFINE:a ja AFTER MATCH SKIP -vaihtoehtoa ei näytetä. Lausekkeiden toistaminen kirjoitetussa muodossa, mukaan lukien vastahakoiset kvanttorit, ryhmä­toisto ja ohitus­vaihtoehto, on pg_get_viewdef():n tehtävä, ja se pitää huolen siitä, että tämä edestakaisin­matkustaminen on vakaa, jotta pg_dump ja pg_upgrade voivat säilyttää RPR-objektit ilman semanttista poikkeamaa — rpr_explain-regressio­paketti varmistaa sen tapaus tapaukselta (ks. §4).

§4. Testit — kattavuuskartta

Korjauspaketti sisältää viisi regressio­pakettia, jotka yhdessä testaavat jokaista §3:ssa kuvattua kerrosta — noin 22 000 riviä SQL:ää, kukin paketti keskittyen eri huoleen. Jako on tarkoituksellinen: parserin, ajoajan oikeellisuuden, suunnittelija­vuorovaikutusten ja tuloste­muotoilun pitäminen erillisissä tiedostoissa tekee virheiden paikantamisesta helpompaa ja estää yhden kerroksen ulkopuolisen muutoksen tahattomasti mitätöimästä toisen kerroksen testejä. Viisi pakettia ovat:

rpr
WINDOW-lausekkeen integraatio — realistiset ikkuna­skenaariot synteettiselle osakedatalle (V-muoto, W-muoto, peräkkäiset nousut, käänteet) sekä navigoinnin semantiikka ja DEFINE-rajoitusten virheet.
rpr_base
Parser-kerros — avainsanojen hyväksyntä, syntaksi­muodot, kvanttorit, navigoinnin jäsennys, virheviestit ja pg_dump/pg_upgrade-edestakaisin­vakaus; lisäksi suunnittelija-kerros — kuvion optimointi, absorptio­liput, optimoinnin vara­polku, suunnittelija­integraatio.
rpr_nfa
NFA-ajoaika — kolmi­vaiheinen silmukka, absorptio jokaisessa absorboituvassa muodossa ja kontekstin elinkaaren reuna­tapaukset.
rpr_explain
Tuloste­muotoilu — NFA-tilastot, kuvion deparsointi, tunnistimen lainaus­merkit, muodon vakaus uudelleen­latauksen yli.
rpr_integration
Suunnittelija­vuorovaikutukset — vartijat, jotka estävät asiaan liittymättömiä ikkuna­optimointeja korruptoimasta RPR-semantiikkaa.

4.1 rpr — päästä päähän -skenaariot

Skenaariopaketti on testijoukon julkinen kasvot: se käyttää noin 1 600 rivin synteettistä osakehinta-aineistoa ja ajaa realistisia kyselyitä sitä vasten — V-muodon palautuminen, W-muoto (kaksoispohja), peräkkäiset nousut ja laskut, käänne­kuviot, monisymboli­partitiot. Nämä skenaariot ovat ainoat testit, joiden syötteet ja tulosteet lukeutuvat kuin kyselyt, joita käyttäjä saattaisi todella kirjoittaa; tiedoston loppuosa on muiden pakettien tavoin pelkistävä — PREV/NEXT-sisäkkäisyyden ja ei-vakioiden siirtymien virheet, DEFINE-viittaussäännöt ja navigointi­siirtymien semantiikka.

Koska nämä kyselyt yhdistävät kaikki kerrokset (parser, suunnittelija, executor, EXPLAIN), yksittäinen rpr:n virhe harvoin kertoo, missä bugi sijaitsee. Neljä seuraavaa pakettia ovat puolituksen välineet: rpr:n virhe ja läpäisevä rpr_base sulkee parserin pois; läpäisevä rpr_nfa kaventaa skenaariokohtaisiin datamuotoihin; läpäisevä rpr_integration sulkee pois suunnittelija­häirinnän; ja deparse-poikkeama näkyy rpr_explain:ssa.

4.2 rpr_base — parser-rajapinta

Base-paketti on suurin, ja se on syystäkin suurin: se vastaa siitä, että jokainen §1.2:n laillinen syntaksi todella jäsentyy, jokainen §1.3:n laiton hylätään hyödyllisellä virheellä ja jokainen hyväksytty muoto selviää serialisointi­kierroksesta. Pääosa siitä on muodoltaan pieniä keskittyneitä koodi­palasia — yksi syntaktista ominaisuutta kohden — pitkien realististen kyselyjen sijaan, koska tavoitteena on kattavuus eikä skenaario­realismi. Toinen osa, suunnittelija-kerros, kattaa kuvion optimoinnin, absorptio­lippujen näytön ja analyysin, optimoinnin vara­polun ja suunnittelija­integraation (alikyselyt, liitokset, joukko­operaatiot, lajittelu ja ryhmittely).

Serialisointi­testit ansaitsevat erityishuomiota. RPR-objektien (näkymät, materialisoidut näkymät, pg_dump-tuloste) on selvittävä luettelo­esityksestä ilman semanttista poikkeamaa, mukaan lukien hienovaraisuudet kuten kvanttorin vastahakoisuus­lippu tai yhdistetyn navigointi­lausekkeen tarkka muoto. Pieni joukko serialisointi­spesifisiä objekteja (näkymät rpr_serial_v* ja niiden tausta­taulut) jätetään tarkoituksella paikalleen ajon lopussa, jotta ympäröivä regressio­infrastruktuuri voi poimia ne ja testata pg_dump:n ja pg_upgrade:n niitä vasten. Muu testi­asetelma puretaan tavanomaisesti. Viat kuten vastahakoisuus­lipun katoaminen deparse–reparse-kierroksessa tulevat näkyviin vain, kun edestakainen matka testataan päästä päähän.

4.3 rpr_nfa — ajoaika­moottori

Tämä on paketti, joka testaa jokaisen §3.5:ssa ja §3.6:ssa kuvatun mekanismin. Sen testit noudattavat johdonmukaista kaavaa: upotetut VALUES-rivit, jotka kantavat muuttuja­nimien taulukkoa, joka julistaa, mitkä DEFINE-muuttujat täsmäävät kullakin rivillä, parina kuvio, joka testaa tiettyä ajoajan käyttäytymistä. Taulukko­idiomi irrottaa ajoaika­testin DEFINE-arviointi­koneistosta — testattavana on ”kun nämä muuttujat täsmäävät tässä, tuottaako NFA-silmukka odotetun osuman jänteen?”, ei ”laskeeko DEFINE-lauseke­arvioija nämä Boolen-arvot oikein?”. DEFINE-arvioijaa testataan muualla (rpr_base jäsennykselle, rpr päästä päähän -käyttäytymiselle).

Tyypillinen testikiinnitys näyttää tältä — sarake muuttuja­nimien taulukoita, jossa kukin merkintä kertoo, mitkä DEFINE-muuttujat laukeavat tällä rivillä, ja kuvio, jonka DEFINE-lausekkeet testaavat näitä nimiä suoraan:

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

Sarake­taulukon lukeminen alaspäin on testi­skenaarion lukemista suoraan. Rivit 2 ja 3 kantavat molempia nimiä — A ja B laukeavat molemmat siellä, joten NFA:lla on todellinen valinta siitä, missä siirtyä A-jalasta B-jalaan. Odotettu osuma (A riveillä 1–3, jota seuraa B rivillä 4 standardin ahneen suosinnan alla) on kiinnitetty pelkillä noilla lipuilla, eikä lauseke­arviointi vaikuta merkittävästi tähän — = ANY on vain triviaali kerros, joka altistaa sarake­taulukon DEFINE:lle, eikä se ole se, mitä testi testaa. Saman skenaarion kirjoittaminen numeerisella predikaatilla (price > PREV(price) ja vastaavat) sotkisi NFA-testin predikaatti­arvioijan käyttäytymisen kanssa; taulukko­idiomi pitää nämä siististi erillään, ja virhe tässä osoittaa suoraan NFA-silmukkaan.

Absorption kattavuus on erityisen perusteellinen, koska absorptio on todennäköisin optimointi tuottamaan hiljaisesti vääriä vastauksia, jos se kytkeytyy päälle silloin, kun ei pitäisi. Testit kattavat jokaisen muodon §3.2:n tapaus­analyysistä:

Absorption lisäksi paketti kattaa kontekstin elinkaaren: päällekkäiset kontekstit AFTER MATCH SKIP TO NEXT ROW:n alla, epäonnistuneiden kontekstien siivous kesken virran, partition lopun viimeistely epätäydellisille konteksteille ja kontekstit, jotka kohdataan sen jälkeen, kun kandidaatti­osuma on jo kirjattu pää­kontekstiin. Kukin näistä karttoituu §3.6:n tiettyyn karsinta­sääntöön, ja testit on kirjoitettu epäonnistumaan äänekkäästi, jos sääntö laukeaa väärin (joko jättämällä tarpeettomia konteksteja eloon tai tappamalla kontekstin, jonka olisi pitänyt tuottaa tuloste).

4.4 rpr_explain — tulosteen vakaus

EXPLAIN-tuloste on osa käyttäjälle suuntautuvaa sopimusta — kolmannen osapuolen työkalut (valvonta­näkymät, lokin lukijat) jäsentävät sitä, ja kosmeettisilta näyttävät muutokset voivat rikkoa ne. rpr_explain-paketti varmistaa kolme asiaa:

Kuten rpr_base, tämä paketti jättää tarkoituksella objektinsa paikalleen ajon lopussa, jotta pg_dump- ja pg_upgrade-kattavuus ulottuu myös explain-puolen artefakteihin.

4.5 rpr_integration — suunnittelija­vuorovaikutukset

PostgreSQL:n suunnittelijalla on monta optimointia, jotka toimivat ikkuna­kyselyihin — kehyksen kanonisointi, run-ehdon työntö, identtisten ikkunoiden poisto­duplikointi, käyttämättömien tulosteiden projektio, liikkuvan aggregaatin käänteissiirtymät — ja jokainen niistä on suunniteltu RPR:ää ajattelematta. Useimmat niistä ovat epäturvallisia sovellettavaksi, kun ikkunalla on PATTERN-lauseke: kehys on osa osumasopimusta, täsmätty tuloste ei ole enää millään ilmeisellä tavalla monotoninen ja kaksi ikkunaa, joilla on sama spec mutta eri DEFINE:t, tuottavat aidosti eri tuloksia. Integraatio­paketti varmistaa, miten kukin näistä optimoinneista kohtelee RPR-ikkunoita — useimmat on kytkettävä pois tai ohitettava:

Kehyksen kanonisointi
Suunnittelija normaalisti uudelleen­kirjoittaa ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING:n muotoon ROWS UNBOUNDED PRECEDING kehyksestä riippumattomille ikkuna­funktioille kuten row_number, rank ja ntile. RPR:n kehys on osuman jänne, ei aggregointi­ikkuna, ja sen on pysyttävä sanasta sanaan.
Run-ehdon työntö
Monotoninen WHERE-suodatin ikkunafunktion tulosteelle voidaan normaalisti työntää ikkuna­operaattoriin pysähdys­ehtona. RPR:lle tämä päättäisi kuvio­täsmäyksen ennenaikaisesti, mahdollisesti katkaisten osumat keskellä venytystä.
Ikkunoiden poisto­duplikointi (RPR vs ei-RPR)
Kaksi ikkunaa identtisellä ORDER BY:llä ja kehyksellä yhdistettäisiin normaalisti yhdeksi. RPR-ikkuna ja ei-RPR-ikkuna eivät voi koskaan jakaa tilaa, koska RPR-puoli kantaa osumatuloksia.
Ikkunoiden poisto­duplikointi (eri DEFINE tai SKIP)
Kaksi RPR-ikkunaa samalla PATTERN:llä mutta eri DEFINE-lausekkeilla tai eri AFTER MATCH SKIP -vaihtoehdolla tuottavat eri osumia ja niiden on pysyttävä erillisinä, vaikka niiden rakenteellinen muoto onkin identtinen.
Käyttämättömien tulosteiden projektio
Tämän saa soveltaa: kun ympäröivä kysely ei koskaan lue ikkunan tulostetta, ikkunafunktiosta tulee NULL ja sen WindowAgg pudotetaan, jolloin rivimäärä ei muutu. Testit varmistavat, että DEFINE:n lukemat sarakkeet saavuttavat yhä WindowAggin, kun se säilyy, ja että ikkuna säilytetään, kun sen arvo luetaan.
Liikkuvan aggregaatin käänteissiirtymät
Ikkuna­aggregaatit, joilla on käänteinen siirtymä­funktio, voidaan normaalisti arvioida inkrementaalisesti kehyksen liikkuessa. RPR:n pelkistetty kehys ei ole liukuva ikkuna; käänteinen siirtymä­polku tuottaisi vääriä tuloksia.

Lisätapaukset varmistavat, että kustannus­arviointi ottaa DEFINE:n huomioon, että RPR-ikkunan sisältävää alikyselyä ei litistetä, etteivät DEFINE-lausekkeet vuoda ylempään WindowAggiin ja että LIMIT pysyy WindowAggin yläpuolella; toinen ryhmä ajaa RPR:ää yhdessä CTE:iden, liitosten, joukko­operaatioiden, valmisteltujen lauseiden, partitioitujen taulujen ja vastaavien rakenteiden kanssa. Useimmat vartioidut tapaukset noudattavat samaa muotoa: perustaso, joka laukaisee optimoinnin (yleensä ei-RPR-kysely, tarkistettu EXPLAINissa), sitten rakenteellisesti samanmuotoinen RPR-kysely, jossa optimointia ei sovelleta — DEFINE/SKIP-poisto­duplikoinnin tapauksessa perustaso on kaksi identtistä RPR-ikkunaa, ja käänteissiirtymän tapaus tarkistaa ohituksen lokittavalla aggregaatilla EXPLAINin sijaan. Näiden kaksi puoliskoa yhdessä todistavat, että suunnittelijan vartija tekee todellista työtä eikä hyväksy jokaista kyselyä ilman todellista varmistusta.

Tämä paketti on myös syy siihen, miksi §3.4 on lyhyt. ”Osuman rajat” -mekanismit — pelkistetty kehys, SKIP, INITIAL, rajatun kehyksen katkaisu — testataan toiminnallisesti muualla; se mitä rpr_integration varmistaa, on ettei mikään muu optimoija­vaihe peuhaa niiden kanssa matkan varrella. Läpäisevä rpr_integration on se, mikä antaa muiden pakettien luottaa siihen, että niiden syötteet saavuttavat executorin koskemattomina.