Row Pattern Recognition Syväluotaus

§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ämä kaksi rajapintaa jakavat suurimman osan syntaksistaan ja koko semantiikkansa, mutta 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ä kolme lauseketta ikkuna­määrittelyn sisään: PATTERN kuvaa säännöllisen lausekkeen nimettyjen kuviomuuttujien yli, DEFINE tarjoaa Boolen predikaatin, joka tunnistaa kunkin muuttujan, ja AFTER MATCH SKIP 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ä.

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 on mielivaltainen arvo­lauseke, joka 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ä.

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 label, AFTER MATCH SKIP TO FIRST var ja AFTER MATCH SKIP TO LAST var. Nämäkin riippuvat osuma­historiasta, koska executorin on kyettävä osoittamaan tiettyä nimettyä riviä viimeisimmän osuman sisällä.

Loput ovat heterogeeninen pyrstö: avainsana SEEK (vaihtoehto INITIAL:lle), tyhjä kuvio (), poissulkemis­muoto {- … -} sekä järjestyksestä riippumaton operaattori PERMUTE.

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 mistä tahansa kohdasta ikkunaa (vs. INITIAL).

AFTER MATCH SKIP TO label

Hyppää nimettyyn riviin.

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 osumakohtaisesta tulosteesta.

Regex: ()

Tyhjä kuvio — täsmää tyhjään jonoon.

PERMUTE(...)

Järjestyksestä riippumaton täsmäys lueteltujen muuttujien yli.

Aggregaattifunktiot DEFINE:ssa

Aggregaatteja kuten SUM, AVG, COUNT ei sallita DEFINE-predikaateissa. Standardi sallii ne juoksevina aggregaatteina osittaisen osuman yli (rivi­kohtainen arviointi muuttujaan jo kuvattuja rivejä vasten), mikä riippuu samasta osuma­historiasta, jonka MEASURES/CLASSIFIER() vaativat.

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; eikä RPR:ää saa käyttää rekursiivisen kyselyn sisällä.

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ä.

§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 kolme päästä päähän -jäljitystä: yksittäisen osuman (NFA-liike), konteksti­absorption helpossa tapauksessa sekä tapauksen, jossa absorptio muuttuu epäturvalliseksi.

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ä.

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. Eteenpäin katsova; ikkuna­muodossa harvinainen, koska ikkuna on monotoninen.

FIRST(expr [, n])

Nykyisen osuman n:s täsmätty rivi alusta laskien. ”Vertaa siihen riviin, joka aloitti tämän osuman.”

LAST(expr [, n])

Viimeisimmistä lukien n:s täsmätty rivi. ”Vertaa viimeisimpään täsmättyyn riviin.”

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 osuman n:nnestä rivistä (oletus m = 1). ”Mikä arvo oli juuri ennen tämän osuman alkua?”

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

Astu m riviä eteenpäin osuman n:nnestä rivistä. Yltää syvemmälle osumaan riippumatta nykyisestä rivistä.

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

Astu m riviä taaksepäin n:nnestä viimeisimmästä täsmätystä rivistä. ”Vertaa riviin hieman ennen viimeisintä osumaa.”

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

Astu m riviä eteenpäin n:nnestä viimeisimmästä täsmätystä rivistä.

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. PREV ja NEXT ovat suhteessa nykyiseen riviin ja aina turvallisia; FIRST sekä LAST:n siirtymä­variantit ovat suhteessa osuman rajoihin, mikä vuorovaikuttaa konteksti­absorption kanssa ja pakottaa suunnittelijan pitämään elossa joitakin konteksteja, jotka muuten hylättäisiin. Tämän vuorovaikutuksen taustalla oleva mekanismi on §2.6:n aihe.

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

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:

Olennainen kohta: rivillä 3 rivi toteuttaa sekä START:n (aina tosi) että DOWN:n, mutta ainoa rivin 2 jälkeen elävä tila on DOWN-poistumisen haarassa, joten vain siirtymä UP → DOWN otetaan. §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 aiempi FIN-kandidaatti (rivit 0–4) — joka syntyi DOWN:n poistuessa rivillä 4 — 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:

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

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 samanaikaisesti.

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. Ne etenevät rinnakkain, kunnes DONE ratkaisee ne.

Molemmat haarat tuottavat samanmittaisen osuman samojen rivien yli, jolloin täsmäimelle jää 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.

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)

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

Muisti kasvaa O(n):stä O(1):een. Hylkäystä oikeuttava absorptio­sääntö on suoraviivainen, kun kvanttori on rajaton:

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ä:

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

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

Absorption alla C2 olisi yhdistetty C1:een tiistaina — yhdistetty konteksti säilyttää vain yhden katon, joten C2:n erillinen näkemys (katto $118, neljän päivän juoksu, joka päättyy vasta lauantaina) ei enää ole palautettavissa sisäisestä tilasta. C2:n on pysyttävä elossa, koska se on itsenäinen osumakandidaatti, jota ajoaika saattaa vielä tarvita: kun C1:n osuma päättyy keskiviikkona, seuraavan yrityksen on poimittava jo käynnissä oleva C2 alusta uudelleen aloittamisen sijaan. 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.)

Posterin oikean alapaneelin (”② Navigointi”) riippuvuus­taulukko tiivistää, mitkä navigointi­muodot synnyttävät osumaan­alku­riippuvuutta:

§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 mikään muu konteksti ei voi palauttaa, ja minkä tahansa hylkääminen riskeeraa väärän vastauksen.

Suunnittelija havaitsee tämän eron käännös­aikana ja päättää konteksti­kohtaisesti, soveltuuko absorptio. Tämä on myös syy, miksi posterin paneelin ③ benchmark pysyy lineaarisena sekä onnistumis- että epäonnistumis­tapauksissa: kun absorptio on turvallinen, ajoaika tiivistää kontekstit, ja kun se ei ole, suunnittelija hyväksyy moni­konteksti­kustannuksen sen sijaan että riskeeraisi väärän vastauksen.

Posterin benchmark-luvut ovat sama algoritmi mittakaavassa. Onnistumis­kuviolla (A+ B+ C+ D) sekä PostgreSQL että Trino skaalautuvat O(n):nä osuman vahvistuttua, ja PostgreSQL:n etu — noin 16×–33× — johtuu enimmäkseen JVM-erosta.

Epäonnistumis­kuviolla (A+ B+ C+ E) Trinolla ei ole absorptiota ja se rappeutuu O(n²):een jahdaten jokaista potentiaalista osuman alkua; 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

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.

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 täyden kuvan siitä, milloin absorptio epäonnistuu:

Jompikumpi ehto riittää kytkemään absorption pois käytöstä kyseessä olevien kontekstien osalta. Kun kumpikaan ei ole voimassa — oletus AFTER MATCH SKIP PAST LAST ROW sekä DEFINE-ehdot, jotka käyttävät vain PREV:iä, NEXT:iä tai paljasta LAST:ia — ajoaika tiivistyy yhteen kontekstiin kuvio­paikkaa kohden ja pysyy lineaarisena alusta loppuun.

§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²)-muistin 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, eikä EXCLUDE-vaihtoehtoja 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:

Kukin DEFINE-predikaatti tyyppi­tarkistetaan sitten partition sarakkeita vasten ja pakotetaan Boolen lausekkeeksi. Tähän liittyy kaksi käytännön asiaa. Ensinnäkin jokainen DEFINE-predikaatin viittaama sarake rekisteröidään osaksi kyselyn tuloste­vaatimuksia, joten suunnittelija 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 kahdeksaa uudelleen­kirjoitus­sääntöä peräkkäin, kunnes AST lakkaa muuttumasta:

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älkiliite­absorptio

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

Kvanttorin kertominen on ainoa muunnos, joka vaatii turva­tarkistuksen: optimoija tiivistää vain kolmessa turvallisessa tapauksessa — molemmat kvanttorit rajattomia ((A+)+ → A+), ulompi tarkka ((A{2,3}){5} → A{10,15}) tai lapsi triviaali {1,1} ((A){2,5} → A{2,5}). 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 — joten optimoija jättää ne koskemattomiksi.

Elementin muoto

Litteän taulukon kukin elementti edustaa yhtä paikkaa kuviossa. Loogisia tyyppejä on viisi: 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; 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ää vaihtoehto haarojen ketjuttamiseen, ryhmän alku rungon ohittamiseen, kun kvanttori sallii nollan, 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 → 4
    (avaa ryhmän; jump hyppää
     FIN:iin kun min = 0)

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

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

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (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 hyppäisi END:n yli indeksiin 4, jos ryhmä olisi valinnainen. 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 neljä 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?)*, (A? B?)+, (A | B*)). Käskee ajoaikaa lisäämään pikahyppy­poistuman normaalin silmukka­takaisin­paluun rinnalle, jotta sykli­vahti ei tapa laillisia osumia ryhmissä, jotka voivat tuottaa tyhjiä iteraatioita.

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 AST läpi 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, AST-käynti hyväksyy kolme 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)+

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 liput asetetaan vain A:han.

Näiden kolmen 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ä. (Jatkokehityksenä on suunniteltu ”PREFIX-absorptio”-laajennus, joka käsittelee kiinteäpituisia etuliitteitä varjopolun kautta, ja se on suunniteltu erilliseen korjauspakettiin.) 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
  hae rivi paikasta targetPos
    paikkaan current_row_slot
  result = arvioi_sisempi_lauseke()
  palauta current_row_slot
  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, ei varjopaikkaa, ei tuplen kopiointia.

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 lastMatchedRow − 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 (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      palauta (lastMatchedRow − 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 ympäröivä tila kelvollinen konteksti­absorptioon (§2.5 vs §2.6).

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. Korjauspaketti päättää käännös­aikana kahden täydentävän siirtymän perusteella:

Taakse­katsonta­budjetti

Kuinka kauas taakse nykyisestä rivistä jokin DEFINE-kutsu voisi yltää.

Vaikuttavat: PREV, LAST siirtymällä, PREV(LAST(...)), NEXT(LAST(...))

Eteenpäin-osuman-alusta -budjetti

Kuinka kauas eteenpäin (tai taakse, jos negatiivinen) vanhimman elävän kontekstin osuman alusta jokin DEFINE-kutsu voisi yltää.

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 kaksi Nav Mark -laskuria (§3.7) — Lookback ja Lookahead — ovat näiden kahden budjetin mitatut huiput, syvimmät paikat, joihin executor joutui kyselyn aikana yltämään kumpaankin suuntaan.

3.4 Osuman rajat — SKIP, INITIAL ja rajattu kehys

Onnistunut osuma kirjataan pienenä arvopakettina: kelpoisuus­lippu, onnistumis-/epäonnistumis­lippu, rivi, jossa osuma alkaa, ja sen kuluttamien rivien lukumäärä. Kun kelpoisuus­lippu on asetettu, executorin myöhemmät kyselyt — ”onko tämä rivi osuman sisällä?” — voivat vastata O(1):ssä tarkastamalla paketin. Pituus nolla on todellinen lopputulos, ei virhe: se edustaa kuviota, joka täsmäsi kuluttamatta yhtään riviä, ja tämä executorin on erotettava 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ä koko kysely­suunnitelman osalta.

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, arvioi kunkin DEFINE-predikaatin kerran nykyistä riviä vasten tuottaakseen muuttuja­kohtaisen Boolen taulukon ja vie sitten NFA:ta yhden rivin verran eteenpäin. 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 ylittää rajatun kehyksen:
          pakota epätäsmäys (vahvista aikaisin)
          jatka
      jos matchStartRow eroaa
         jaetusta arviointi­paikasta:
          arvioi uudelleen osuma-alku-
          riippuvaiset DEFINE-muuttujat (§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)

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]
      jos elem ei ole muuttuja:
          jatka   # advance hoitaa sen

      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:
          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). 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-elementti -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ä),
    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 karsi
         myöhemmät kontekstit tämän
         kandidaatin alueen sisältä — 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 heti kun kandidaatti kirjataan, jokainen myöhempi konteksti, jonka alkurivi osuu kandidaatin alueen sisään, karsitaan välittömästi, 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 toinen kahdesta FIN-aikaisesta karsinta­vaiheesta — toinen, kuvattu aiemmin tässä osiossa Advancen osana, hylkää leksikaalisesti alempi­arvoiset tilat saman kontekstin sisällä.

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ä
          (pelastaa lailliset osumat,
           jotka sykli­vahti muuten
           tappaisi)

  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, sitten poistu
          # suosii pidempää
      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. Kuviot kuten (A?)*, (A? B?)+ ja (A | B*) kaikki omaavat tämän ominaisuuden: datasta riippuen runko voi suorittaa iteraation kuluttamatta yhtään riviä. Periaatteessa tämä on hyvä, mutta se luo todellisen vaaran NFA:n epsilon-laajennukselle. Jos runko tuottaa tyhjän osuman, END-elementti silmukoi takaisin BEGIN:iin, runko tuottaa jälleen tyhjän osuman, BEGIN silmukoi END:iin, ja niin edelleen. Ilman pysäyttäjää Advancen DFS ei koskaan päättyisi.

Ajoaika pysäyttää sen käyty-elementti -bittikartalla (yksi bitti kuvio­elementtiä kohden), joka tyhjennetään ennen kunkin tilan DFS-laajennusta: heti kun jokin elementti vieraillaan toista kertaa saman laajennuksen sisällä, polku hylätään. Sykli­vahti on ehdoton ja halpa, mutta sillä on sivu­vaikutus — se voi myös hylätä polut, jotka pitäisi saavuttaa alarajan laillisten tyhjien iteraatioiden kautta. Tarkastellaan (A?){2,3} -kuviota, jossa A ei täsmää missään rivivirran kohdassa:

tavoiteltu käyttäytyminen:
  iter 1: A? täsmää nollaan riviin
          → END, count = 1 (alle min)
  iter 2: A? täsmää nollaan riviin
          → END, count = 2 (täyttää min)
  poistu nollapituisella osumalla

mitä sykli­vahti tekee yksinään:
  iter 1: A? ohitettu → END, count = 1
          → silmukoi takaisin BEGIN:iin
  iter 2: BEGIN jo vierailtu
          → DFS keskeytyy
  count ei koskaan saavuta min:iä
  → osuma epäonnistuu (virheellinen)

Korjaus 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. Ajoaikana, kun END-käsittelijä on silmukoimassa takaisin, koska iteraatio­laskuri on yhä alarajan alapuolella, tyhjä­silmukka­merkintä käskee sitä kloonaamaan ylimääräisen pikahyppy-tilan normaalin silmukka­takaisinpaluun rinnalle:

advance_end (count alle min:in):

  ensisijainen 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. Ensisijainen silmukka­takaisinpaluu nappaa tapauksen, jossa rungolla on vielä todellisia osumia tuotettavanaan myöhemmin — esimerkiksi (A?){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 nappaa tapauksen, jossa runko ei koskaan tuota mitään: se ohittaa sykli­vahdin poistumalla ryhmästä kokonaan, julistaen ”loput vaadituista iteraatioista ovat tyhjiä” ja sallien osuman onnistua nollapituisella rungolla. Molemmat tilat lisätään kontekstiin; kumpi tahansa, joka venyy onnistuneesti, voittaa, ja 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 lineaarisuus 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 on peitetty vanhemman kontekstin korkeammalla laskurilla varustetulla tilalla — 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ä) FIN:ssä

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 välittömästi.

Sykli­vahti Advance

Epsilon-laajennukset, jotka käyvät uudelleen samassa kuvio­elementissä saman DFS:n sisällä — silmukoituisivat muuten ikuisesti nullattavissa ryhmissä.

Tyhjä­silmukan pikahyppy Advance

Lailliset tyhjä-iteraatio-osumat, jotka sykli­vahti tappaisi nullattavissa ryhmissä — ohittaa syklin poistumalla ryhmästä jäljellä olevat vaaditut iteraatiot tyhjiksi julistettuna.

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) ja uudelleen osuman valmistuessa (FIN:ssä). 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ä sykli­vahti tappaisi lailliset osumat nullattavissa ryhmissä; 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.

3.7 EXPLAIN-tuloste

EXPLAIN ANALYZE RPR:ää käyttävälle kyselylle tuo näkyviin NFA-tasoisia tilastoja, joita ei ole tavallisissa ikkunafunktioissa. Ikkuna­operaattorin oheen annetaan kolme laskuriryhmää:

NFA States:    peak, total, merged
NFA Contexts:  peak, total, pruned
NFA: matched     (len min/max/avg)
NFA: mismatched  (len min/max/avg)
NFA: absorbed    (len min/max/avg)
NFA: skipped     (len min/max/avg)
Nav Mark Lookback:   | runtime | retain all
Nav Mark Lookahead:  | runtime | retain all
  (vain kun kysely käyttää FIRST:iä,
   PREV(FIRST(...)) tai NEXT(FIRST(...)))

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. Osuma­pituus­histogrammit erottavat neljä lopputulosta — onnistuneet osumat, epäonnistuneet osuma­yritykset, absorboidut kontekstit ja kontekstit, jotka karsittiin (ohitettiin) ilman arviointia — 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 käännös­aikana. Lookback on syvin taakse­päin ulottuva yltämä PREV:n, siirtymällä varustetun LAST:n ja yhdistettyjen muotojen sisemmällä LAST:lla; Lookahead on syvin eteenpäin (tai taaksepäin, jos negatiivinen) ulottuva yltämä 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 on arvioitava joka kutsulla, ja ”retain all”, kun ajoaika tarvitsee rajoittamattoman budjetin. Lookahead annetaan vain, kun kysely todella käyttää osuman alkuun suhteellista navigointia.

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

Laskureiden lisäksi EXPLAIN myös toistaa uskollisesti alkuperäiset PATTERN- ja DEFINE-lausekkeet, mukaan lukien vastahakoiset kvanttorit, ryhmä­toiston ja AFTER MATCH SKIP -vaihtoehdon. Toteutus 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 13 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

Päästä päähän -kysely­semantiikka — realistiset ikkuna­skenaariot synteettiselle osakedatalle (V-muoto, W-muoto, peräkkäiset nousut, käänteet).

rpr_base

Parser-kerros — avainsanojen hyväksyntä, syntaksi­muodot, kvanttorit, navigoinnin jäsennys, virheviestit ja pg_dump/pg_upgrade-edestakaisin­vakaus.

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. Se on ainoa paketti, jossa syötteet ja tulosteet lukeutuvat kuin kyselyt, joita käyttäjä saattaisi todella kirjoittaa; muut ovat tarkoituksella pelkistäviä, keskittyen yhteen kerrokseen kerrallaan.

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.

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. Tällä tavoin napatut bugit (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: syöte­taulu, jonka rivit ovat eksplisiittisiä Boolen taulukoita, jotka julistavat, mitkä DEFINE-muuttujat täsmäävät kullakin rivillä, parina kuvio, joka testaa tiettyä ajoajan käyttäytymistä. Boolen 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ä:

• yksinkertainen rajaton muuttuja (A+) — kanoninen N-1-tiivistys;
• kiinteäpituiset ryhmät ((A B)+, (A B{2})+, kolmi­tasoinen sisäkkäinen ((A (B C){2}){2})+);
• johtava rajaton muuttuja kiinteällä jälkiliitteellä (A+ B) — vain johtava A+ kantaa absorptio­lippuja, jälkiliite ei;
• haarakohtainen absorptio vaihtoehdon sisällä (B+ C | B+ D);
• useita rajattomia muuttujia (A+ B+) — vain johtava on absorboituva;
• vastahakoiset kvanttorit (A+?) — varmistettu rajattuna absorption ulkopuolelle;
• ei-johtava rajaton (A B+) — varmistettu rajattuna ulkopuolelle.

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 (psql:n automaattitäydennys, 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:

• NFA-laskurit ilmestyvät oikeaan paikkaan — WindowAgg-kohtaiset tilastot (peak/total/merged-tilat, peak/total/pruned-kontekstit, pituus­histogrammit matched/mismatched/absorbed/skipped, Nav Mark Lookback ja — kun osuman alkuun suhteellinen navigointi on käytössä — Nav Mark Lookahead) kaikki ilmestyvät EXPLAIN ANALYZE:n alla dokumentoiduilla otsikoilla.
• Kuviot deparse:utuvat oikein — jokainen kvanttori­muoto, mukaan lukien vastahakoiset variantit ja rajatut muodot; jokainen vaihtoehto; jokainen ryhmä; jokainen AFTER MATCH SKIP -muoto; INITIAL; navigointi­kutsut siirtymillä; yhdistetty navigointi. Deparse:utuneen tekstin on selvittävä parserin läpi muuttumattomana.
• Tunnistimen lainaus­merkit ovat oikein — kuvio­muuttujat ja DEFINE-lausekkeet annetaan samoilla lainaus­säännöillä kuin tavalliset SQL-tunnistimet, joten epätavalliset muuttuja­nimet eivät riko pg_dump-tulostetta.

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, että jokainen näistä optimoinneista on oikein kytketty pois tai ohitettu RPR-ikkunoille:

Kehyksen kanonisointi

Suunnittelija normaalisti uudelleen­kirjoittaa ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING:n muotoon ROWS UNBOUNDED PRECEDING monotonisille aggregaateille. 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)

Kaksi RPR-ikkunaa samalla PATTERN:llä mutta eri DEFINE-lausekkeilla tuottavat eri osumia ja niiden on pysyttävä erillisinä, vaikka niiden rakenteellinen muoto onkin identtinen.

Käyttämättömien tulosteiden projektio

Vaikka ympäröivä kysely ei koskaan lukisi ikkunan rivi­kohtaista tulostetta, RPR-ikkunaa ei voi poistaa: kuvio­täsmäimen sivuvaikutukset (mitkä rivit ovat minkäkin osuman sisällä) syöttävät pelkistetyn kehyksen laskelmia muualla suunnitelmassa.

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.

Kaava näiden testien yli on sama: kukin tarjoaa ei-RPR-perustason, joka laukaisee optimoinnin (ja varmistaa, että EXPLAIN näyttää sen sovellettavan), ja ajaa sitten rakenteellisesti samanmuotoisen RPR-kyselyn ja varmistaa, että optimointia ei sovelleta. 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.