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.
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.
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 kuviologiikan 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; taululausekemuoto on tietoisesti rajattu työn ulkopuolelle.
R020-rajapinta on pieni mutta ilmaisuvoimainen. Kysely liittää kuvion ikkunaan lisäämällä lausekkeita sellaisen ikkunamää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äännekuviot, 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ä navigointiprimitiiviä, joita DEFINE-ehdot tarvitsevat verratakseen vierekkäisiä rivejä.
- PATTERN-lauseke
- Määrittelee rivikuvion ikkunamäärittelyn sisällä; enintään 240 erillistä kuviomuuttujaa.
- Ikkunan kehys
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGtaiROWS BETWEEN CURRENT ROW ANDnFOLLOWING, jossa n ≥ 1 (19075-5 §6.10.2); mikä tahansa muu kehys hylätään, jaEXCLUDE NO OTHERSon 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 kuviomuuttujan.
- 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,FIRSTjaLASTmäärittelemättöminä kutsuinaDEFINE:n sisällä tarkoittavat aina navigointia; samanniminen käyttäjän funktio on kirjoitettava siellä skeemamääritteisenä.- Navigoinnin argumentit
- Funktioilla
PREV,NEXT,FIRSTjaLASTsisemmän argumentin on sisällettävä vähintään yksi sarakeviittaus, ja siirtymän on oltava ajonaikainen vakio. - INITIAL
- Kuvioosumien on alettava nykyisestä rivistä (oletus).
- AFTER MATCH SKIP PAST LAST ROW
- Oletusarvoinen ohitustila; soveltuu kontekstiabsorptioon.
- 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(), kuviomääritteiset sarakeviittaukset kuten B.price sekä kuviomää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 kuviomuuttujaan 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ä muuttujasidoksia mihinkään — myöhemmin ei ole mistä kysyä. Historiainfrastruktuurin 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 osumahistoriasta, 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 (), poissulkemismuoto {- … -}, järjestyksestä riippumaton operaattori PERMUTE sekä aggregaattifunktiot ja alikyselyt DEFINE:ssa, jotka molemmat hylätään toistaiseksi (muuttujamääritteinen aggregaatti tarvitsisi lisäksi osumahistorian).
- MEASURES
- Nimettyjä osumakohtaisia tulostelausekkeita, esim.
MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; R020:ssa esiin tuotunaOVER-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
- Kuviomuuttujien nimettyjä unioneja, esim.
SUBSET U = (A, B, C). Käytettävissä missä tahansa kuviomuuttujaan voidaan viitata —MEASURES, kuviomääritteiset viittauksetDEFINE:ssa,CLASSIFIER(U)— jotka kaikki vaativat osumahistoriaa. - CLASSIFIER()
- Palauttaa, miksi kuviomuuttujaksi annettu rivi täsmättiin. Määritelty sekä DEFINE:lle että MEASURES:lle (19075-5 §5.9); vastaus millä tahansa rivillä on kyseiselle riville osumahistoriaan kirjattu muuttujan nimi.
- Kuviomääritteinen sarakeviittaus
- Pelkkä
B.priceDEFINE:ssa taiMEASURES:ssa — sarakkeen arvo siltä riviltä, joka kuvattiin nimettynä muuttujana. - Kuviomää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 ikkunakehyksen 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”);
permuteon edelleen käytettävissä kuviomuuttujan nimenä. - Aggregaattifunktiot DEFINE:ssa
- Aggregaatteja kuten
SUM,AVG,COUNTei sallitaDEFINE-predikaateissa. Standardi sallii ne juoksevina aggregaatteina osittaisen osuman yli; muuttujamääritteinen aggregaatti kutenAVG(B.Price)riippuu samasta osumahistoriasta, jonkaMEASURES/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 rivikuviomuuttujaan; korjauspaketti hylkää toistaiseksi liikaa.
Tässä on syytä huomauttaa neljästä lisäkohdasta, sillä ne on helppo erehtyä luulemaan puutteiksi.
Ensimmäinen on, että kuvioankkureita ^ 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 standardinmukaisuutta, 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 standardinmukaisuutta 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 rivikuviomuuttujiin (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 rekursiosää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 taululausekerajapinta — 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 rivikuviotäsmäys on aidosti erilaista kuin merkkijonokuviotäsmäys, esittelemme sitten neljä navigointifunktiota, jotka tekevät DEFINE-ehdoista mielenkiintoisia, ja käymme lopuksi läpi viisi käytännön esimerkkiä: yksittäisen osuman (NFA-liike), vaihtoehdon, kontekstiabsorption 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 rivikuviot eroavat tekstikuvioista
Tekstin säännöllinen lauseke täsmää merkkivirtaan, ja jokaisessa kohdassa on tarkasteltavana 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ä. Kuviotäsmäin ei voi tiivistää tätä yhdeksi tilaksi — kaksi kuviomuuttujaa on elossa, ja mikä tahansa kuvioelementti, 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. Suoritustila 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 karsintakerroksia — tilojen poistoduplikointi 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 kuviotäsmäys muuttuu superlineaariseksi.
2.2 Navigointifunktiot
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ä navigointifunktiota, 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; ikkunamuodossa 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, jotenLAST(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 kontekstiabsorption 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
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:
| Rivi | Hinta | Todet muuttujat | Toiminto |
|---|---|---|---|
| 0 | 100 | START | Uusi konteksti. START täsmää ja poistuu välittömästi (max=1); tila etenee tilaan UP+. |
| 1 | 110 | START, UP | UP täsmää. Eteneminen haarautuu: yksi tila silmukoituu UP:hen, toinen poistuu tilaan DOWN+. |
| 2 | 120 | START, UP | UP täsmää silmukkatilassa ja haarautuu uudelleen. Rivin 1 DOWN-tila kuolee (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP epäonnistuu silmukkatilassa ja kuolee. Rivin 2 DOWN-tila täsmää. Eteneminen haarautuu: silmukka DOWN:ssa ja poistuminen tilaan #FIN — osumakandidaatti riveillä 0–3 kirjataan. |
| 4 | 108 | START, DOWN | DOWN täsmää silmukkatilassa ja haarautuu uudelleen; uusi FIN-kandidaatti riveillä 0–4 korvaa lyhyemmän. |
| 5 | 130 | START, UP | Silmukoiva 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 silmukkahaarat 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:
| Rivi | Hinta | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
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 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.
| Rivi | Todet muuttujat | Elävät tilat |
|---|---|---|
| R | UP, HIGH | Tila 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+1 | DONE | Tila A täsmää DONE:en ja saavuttaa #FIN-tilan |
Standardin termein molemmat haarat tuottavat samanmittaisen osuman samojen rivien yli, jolloin syntyy kaksi kandidaattipolkua — 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 vaihtoehtohaaran kahdesta päätöksestä ahne kvanttori suosii useampia iteraatioita.
2.5 Käytännön esimerkki 3 — Kontekstiabsorptio (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 viisirivinen partitio (mikä tahansa data — predikaatti on vakio tosi):
| Rivi | Naiivit kontekstit | Absorption kanssa |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 absorboitu |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | viisi kontekstia | C1[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 absorptiosääntö on suoraviivainen, kun kvanttori on rajaton:
Posterin vasen alapaneeli (”① Kontekstiabsorptio”) 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 kauppaviikkoon 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 kauppaviikko $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 — partitiotason tosiasia, ei kontekstitason — joten molempien kontekstien on pakko laskea sama Boolen arvo jokaisella jaetulla rivillä:
| Päivä | Hinta | C1 — 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 |
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
DEFINE viittaa FIRST:iin — absorptiosääntö ei enää päde, ja suunnittelija kytkee absorption pois kuviolta.
Oletetaan, että analyytikko haluaa löytää peräkkäisiä kauppapäiviä, joina osake pysyi kymmenen dollarin sisällä juoksun aloituspäivän hinnasta — eräänlainen konsolidoitumisikkuna. 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 kuvioelementissä 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 kauppaviikko kuin §2.5:ssä — $100, $108, $112, $116, $110 maanantaista perjantaihin. Ajoaika pitää jälleen elossa kaksi kandidaattijuoksua samanaikaisesti: C1 alkoi maanantaina, C2 tiistaina (jokainen rivi on potentiaalinen juoksun alku STABLE+:n alla).
| Päivä | Hinta | C1 — 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ä) |
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 osumaanalkuriippuvuutta, 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ä navigointimuodot synnyttävät osumaanalkuriippuvuutta:
| Navigointi | Osuman alkuriippuvuus | Absorboituuko? |
|---|---|---|
| PREV, NEXT | ei | kyllä |
| LAST (ilman siirtymää) | ei | kyllä |
| LAST siirtymällä | rajatarkistus | ei |
| FIRST (mikä tahansa) | suora | ei |
| Yhdistetty (sisempi FIRST) | suora | ei |
| Yhdistetty (sisempi LAST, ilman siirtymää) | ei | kyllä |
| Yhdistetty (sisempi LAST siirtymällä) | rajatarkistus | ei |
§2.5:n ja §2.6:n esimerkit pelkistyvät yhdeksi säännöksi. Sama kohtalo tekee absorptiosta turvallisen: jos jokainen samassa kuvioelementissä oleva konteksti laskee saman vastauksen jokaiseen tulevaan predikaattiin, vain vanhin tarvitsee säilyttää. Erilaiset kohtalot tekevät absorptiosta epäturvallisen: heti kun predikaatit haarautuvat kontekstiyksityisen 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ösaikana ja kytkee absorption päälle tai pois koko kuviolta; kun se on pois päältä, ajoaika maksaa monikontekstikustannuksen. Posterin paneelin ③ benchmark ei käytä FIRST:iä, joten absorptio pysyy päällä, ja siksi PostgreSQL pysyy lineaarisena sekä onnistumis- että epäonnistumistapauksissa.
Posterin benchmark-luvut ovat sama algoritmi mittakaavassa. Onnistumiskuviolla (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äonnistumiskuviolla (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
Edellinen esimerkki rikkoi absorption datapuolelta: FIRST DEFINE:ssa sai kunkin kontekstin arvioimaan predikaatit eri tavalla. Absorptio voi rikkoutua myös tulostepuolelta, 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 ohitusmoodi 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.
| Rivi | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | osuma alkaa; rivit 0–4 ovat ainoa osuma | osuma 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 |
| 4 | osuma 0 vahvistuu (rivit 0–4) | viisi osumaa vahvistuu: 0–4, 1–4, 2–4, 3–4, 4–4 |
AFTER MATCH SKIP TO NEXT ROW:n alla jokainen myöhään alkanut konteksti on oma tulosterivinsä. Kaksi kontekstia samassa kuvioelementissä 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 tulostevaatimus: jopa identtisten tulevaisuuksien konteksteilla on oltava rinnakkaiselämä, koska ne vastaavat tuloksen erillisiä rivejä. Suunnittelija kytkee siten kontekstiabsorption 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:
FIRST tai siirtymällinen LAST DEFINE:ssa.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 vaihtoehtohaarat; 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 kuviopuuksi ja DEFINE-predikaattien listaksi; suunnittelija kääntää puun litteäksi kuvioelementtien taulukoksi ja päättää, mitkä niistä voivat osallistua kontekstiabsorptioon; executor ajaa taulukon partitiota vasten rivi rivin kolmivaihelaisessa silmukassa. Jokaisella vaiheella on oma datamuotonsa, ja suurin osa suunnittelun nerokkuudesta on rajoilla: välimuistiin mahtuva litteä NFA, navigointimalli, joka käyttää yhtä tuple-paikkaa eikä materialisoi viittausta kohden, sekä absorptiosääntö, joka muuttaa O(n²)-työn O(n):ksi.
SQL-teksti
│
│ parser-vaihe
▼ validoi kehys
rakenna kuviopuu
tyyppitarkista DEFINE
kuviopuu + DEFINE-lista
│
│ suunnittelija-vaihe
▼ optimoi puu
käännä litteäksi NFA-taulukoksi
päätä absorboituvuus
litteä NFA + absorptioliput
│
│ executor-vaihe
▼ rivikohtainen 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 kuviopuun muodon; §3.2 käännöksen, joka muuttaa puun litteäksi NFA:ksi; §3.3 navigointimallin, jota DEFINE-predikaatit käyttävät naapuririvien tarkasteluun; §3.4 osuman rajakäsittelyn — SKIP-, INITIAL- ja rajatun kehyksen säännöt, jotka kiinnittävät osuman alun ja lopun; §3.5 on kolmivaihelainen rivikohtainen moottori; §3.6 kokoaa kaikki karsintamekanismit, jotka pitävät tila-avaruuden rajattuna; ja §3.7 kartoittaa sen, mitä toteutus tuo näkyviin EXPLAIN-tulosteessa.
3.1 Parser — kuviopuun rakentaminen
Parser tunnistaa pattern recognitionin PATTERN-lausekkeen läsnäolosta ikkunamäärittelyn sisällä. Sen ensimmäinen tehtävä on kehysvalidointi, sillä RPR asettaa rajoituksia, joita tavalliset ikkunakyselyt eivät: kehystilan 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 standardinmukaisuustarkistuksia, 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ä solmutyypistä — muuttujaviittaus, 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ähde | Puukoodaus |
|---|---|
| A | VAR(A, min=1, max=1) |
| A+ | VAR(A, min=1, max=∞) |
| A* | VAR(A, min=0, max=∞) |
| A{3,5} | VAR(A, min=3, max=5) |
| A+? | VAR(A, min=1, max=∞, reluctant=true) |
Kukin DEFINE-predikaatti tyyppitarkistetaan sitten partition sarakkeita vasten ja pakotetaan Boolen lausekkeeksi. Tästä seuraa kaksi käytännön asiaa. Ensinnäkin jäsennysanalyysi ei lisää DEFINE:n vuoksi mitään kyselyn kohdelistaan; 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 tietorakenteeksi, jonka executor ajaa: indeksoiduksi litteäksi kuvioelementtien taulukoksi. Käännös etenee kuusivaiheisena putkena:
compile(astTree):
1. optimoi AST
2. mittaa koko ja syvyys
3. varaa elementtitaulukko
4. täytä AST:stä
(aseta next/jump-osoittimet)
5. viimeistele — aseta FIN-sentinel
6. merkitse absorptiokelpoiset 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 tietorakenne 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 absorptiooptimointi ylipäätään käyttöön.
AST-optimointi
Optimointi hyödyttää kahdesti: kerran litteän taulukon staattisessa elementtimäärässä ja uudelleen jokaisella ajoaikana käsiteltävällä rivillä. Jokainen muunnos pienentää tila-avaruutta, joka ajoajan on lueteltava. Optimoija soveltaa yhdeksää uudelleenkirjoitussää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 poistoduplikointi
-
(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 uudelleenkirjoitus: 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 uudelleenkirjoitus, jonka uusi raja ylivuotaisi, hylätään.
Elementin muoto
Litteän taulukon kukin elementti edustaa yhtä paikkaa kuviossa. Loogisia tyyppejä on kuusi: muuttujaviittaus (ainoa, joka kuluttaa rivin); ryhmän alku- ja ryhmän loppu-merkit, jotka avaavat ja sulkevat sulkeisiin kootun alikuvion; vaihtoehtomerkki, joka aloittaa haarojen listan; haaran erotin, joka päättää kunkin haaran; ja lopetusmerkki kuvion lopussa.
Jokainen elementti kantaa myös syvyyttä (ryhmän sisäkkäisyystasonsa), 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 vaihtoehtomerkki 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.
Elementtikohtaiset 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 muotoonA*eikä siitä jää ryhmän loppua). Käskee ajoaikaa lisäämään pikahyppypoistuman normaalin silmukkatakaisinpaluun rinnalle alarajan alapuolella, jotta syklivahti 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ää pikahyppypoistuman silmukkatakaisinpaluun edelle alarajan alapuolella, missä ryhmän oma ahneus ei sano mitään. - Absorboituvalla alueella
- Merkitsee jokaisen elementin, joka sijaitsee absorptiokelpoisen alueen sisällä — käytetään ajoajassa seuraamaan, onko nykyinen tila yhä turvallisella alueella.
- Absorption vertailupiste
- Merkitsee sen elementin, jossa absorptiovertailut 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”.
Absorboituvuusanalyysi
Käännöksen vaihe 6 antaa §2.5:n ”sama kohtalo” -säännölle sen käännösaikaisen 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 kyselytasoisia: 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
-
Kukin iteraatio on tasan yksi rivi. Aiemman kontekstin laskuri on aina ≥ myöhemmän jokaisessa jaetussa paikassa.
A+,A*,A{2,∞} - Tapaus 2 — Kiinteäpituinen ryhmä, rajaton ulompi
-
Jokaisella lapsella on
(A B)+,(A B{2})+,((A (B C){2}){2})+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
-
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 monotoniatakeita, joten A saa molemmat liput, ympäröivä BEGIN saa aluelipun, eivätkä B ja END saa kumpaakaan.
(A+ B)+,(A+ B){2} - Tapaus 4 — Vaihtoehto
-
Kukin haara, johon päästään erotinketjun kautta, arvioidaan erikseen yllä olevien tapausten mukaan; vaihtoehtomerkki saa aluelipun, kun jokin haara kelpaa.
A+ | B+,A+ | C D
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: absorptiosääntö olettaa ahneen semantiikan, jossa pidemmät osumat sulkevat lyhyempiä, ja vastahakoinen täsmäys kääntää tämän suunnan.
Tulos on elementtikohtainen päätös, ei kuviokohtainen. Yksittäisellä kyselysuunnitelmalla 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 absorptiokierroksen harkitessaan vain nykyisen tilan elementin vertailupisteattribuuttia. 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-lausekekoneisto lukee, sillä lausekkeen sarakeviittaukset on sidottu paikkaan suunnitteluaikana. Toteutus käyttää uudelleen yhtä navigointipaikkaa jokaiselle navigointikutsulle: paikka vaihdetaan paikalleen ennen sisemmän lausekkeen arviointia ja palautetaan jälkeenpäin, joten muu SQL-lausekekoneisto ei huomaa eroa.
Executorin näkemä malli on pieni: on nykyisen rivin paikka, joka pitää sitä riviä, jota vasten DEFINE-lauseketta arvioidaan, ja navigointipaikka, jonka ajoaika voi tilapäisesti uudelleenohjata toiseen riviin. Kunkin navigointikutsun ympärillä ajoaika valmistelee navigointipaikan, 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 arviointipolkua 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 navigointipaikkaan (ellei paikka jo pidä sitä), ja palautusvaihe kopioi viittauksena välitettävän tuloksen tuplekohtaiseen muistiin, jotta seuraava haku ei voi vapauttaa sitä.
Yhdistetty navigointi litistetään jäsennysaikana niin, että vaihto tapahtuu yhä kerran. PREV(FIRST(price)) tunnistetaan kaksivaiheiseksi navigoinniksi — ”siirry ensimmäiseen täsmättyyn riviin ja astu sitten yksi rivi taaksepäin” — ja tallennetaan yhtenä yhdistetyn tyypin navigointikutsuna. Ajoaika laskee kohdepaikan kahdessa vaiheessa mutta tekee vain yhden paikkavaihdon 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)
Sijaintivälimuisti oikoo tuplestorehakua, kun useat saman DEFINE:n navigointikutsut 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.
Navigointikutsujen luokittelu on suunnittelijan panos absorptiopää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 kontekstiabsorptio ylipäätään mahdollinen (§2.5 vs §2.6): yksikin osuman alusta riippuva muuttuja kytkee sen pois koko kuviolta.
- Ei navigointia
- Vain
PREV/NEXT LASTilman siirtymää- Yhdistetty sisemmällä
LAST:lla (ilman siirtymää)
LASTsiirtymälläFIRST(mikä tahansa muoto)- Yhdistetty sisemmällä
FIRST:llä - Yhdistetty sisemmällä
LAST:lla (siirtymällä)
Luokittelu suoritetaan suunnitteluaikana 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äilytysbudjetti
Navigointi ulottuu riveihin, jotka ikkunafunktiokoneisto 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):
- Taaksekatsontabudjetti
- Kuinka kauas taakse nykyisestä rivistä jokin DEFINE-kutsu voisi yltää.
- 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.
Ajoaikana tuplestoren leikkausmerkki asetetaan kahdesta sijainnista varhaisempaan — nykyinen rivi miinus taaksekatsontabudjetti ja vanhimman elävän kontekstin osuman alku plus eteenpäinkatsontabudjetti. Mitään ennen tätä merkkiä ei voi saavuttaa millään navigointikutsulla 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 osumayritys 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 absorptiooptimoinnin.
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ää ohituskohdetta — 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 syntaksivirheen, jos jompikumpi annetaan.
Sama pätee SEEK:iin, spesifikaation vaihtoehtoon INITIAL:lle. SEEK:in alla rivillä R alkava osumayritys 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 monotoniaoletuksen, johon absorptio nojaa.
3.5 Kolmivaihelainen rivikohtainen moottori
Executorin rivikohtainen ajuri kutsutaan ympäröivästä ikkunafunktiokoneistosta aina, kun sen on tiedettävä, kuuluuko tietty rivi täsmättyyn kehykseen. Ajuri löytää tai luo nykyisen aloituspaikan kontekstin ja vie sitten NFA:ta eteenpäin rivi riviltä — nollaten muuttujakohtaisen täsmäystaulukon 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 arviointipaikasta:
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ävyysehto laukeaa vain absorboituvassa vertailupisteessä — rajattoman ryhmän END:ssä — joten juuri välirivimuuttujiin 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 absorptiopisteeseen — 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 luontijä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ävyystarkistus hylkää välittömästi, jos uudemman kontekstin jokin tila istuu muualla kuin vertailupisteessä — vertailu ei-päätöspisteissä ei olisi mielekäs vertailu.
Toinen on epäsymmetrinen lippupari 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 vakioajassa ennen kuin peittävyysskannaus 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 syvyyspainotteinen, ja siskohaarojen kävelyjärjestys on se, mikä saa standardin suosintasäännön todella vaikuttamaan — leksikaalisesti ensimmäinen haara lisätään aina ensin, ja tilan lisäyksen poistoduplikointivaihe 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
ohituspolku 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
(poistoduplikoiden elemIdx + counts perusteella)
FIN:in saavuttaneen tilan kirjaaminen tekee enemmän kuin merkitsee kandidaattiosuman. 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 karsintavaihe. Kontekstin sisällä FIN katkaisee myös leksikaalisesti alempiarvoisen 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ääntulopoluista toinen, vastahakoisen muuttujan sisääntulopolku, END:n silmukka- ja poistumispoluista toinen — pysähtyy, kun osuma on kirjattu, joten yksi advance kirjaa enintään yhden osuman.
Vaikein elementtikohtainen logiikka asuu END-käsittelijässä. Kun ryhmän iteraatiolaskuri 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 pikahyppytila,
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 poistumistila
(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 poistoduplikointitarkistuksen, joka vertaa sen sijaintia ja laskureita olemassa olevaan tilalistaan. 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ösaikana 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ösaikana 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 takaisinsilmukoinnit 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 silmukkatakaisinpaluuseen, 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äsilmukkamerkintä käskee END-käsittelijää myös kloonaamaan ylimääräisen pikahyppy-tilan normaalin silmukkatakaisinpaluun rinnalle:
advance_end (count alle min:in):
silmukkatakaisinpaluun polku:
silmukoi takaisin runkoon
(pitää oven auki todelliselle,
ei-tyhjälle osumalle seuraavalla
iteraatiolla)
jos elem on tyhjäsilmukoituva:
pikahyppypolku:
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. Silmukkatakaisinpaluu 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, silmukkatakaisinpaluu 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äysvaiheen poistoduplikointitarkistus estää kumpaakaan polkua synnyttämästä enempää kuin osansa tiloja.
Syklivahdin lisäksi yksi käynnistyskikka erottaa nolla-rivisiä lopputuloksia kontekstin alussa. Kontekstiluontivaihe jokaisella mahdollisella aloitusrivillä 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 lopetussijainnin, 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 karsintasääntöjen kumulatiivinen vaikutus, joista kukin nappaa eri syyn tila-avaruuden kasvulle eri kohdassa rivikohtaisessa syklissä. Jotkin päätetään käännösaikana 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
- Muuttujatilat, 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.
- Kontekstiabsorptio 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ösaikainen kelpoisuus, §3.5 parikohtainen tarkistus.
- Tilojen poistoduplikointi 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.
- Kandidaattiosuman karsinta (kontekstien välillä) Advance
- Muut kontekstit, joiden alkurivi osuu kandidaattiosuman 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. - Syklivahti 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 silmukkatakaisinpaluuseen 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 vaihemerkin 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 ylikonsolidoisi, kun DEFINE viittaa osuman alkuun; pelkkä poistoduplikointi 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: poistoduplikointi 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. Tekstimuodossa ne annetaan ikkunaoperaattorin 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 tekstimuodot 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 poistoduplikoinnin kautta; pruned laskee kontekstit, jotka epäonnistuivat yhden rivin jälkeen. Osumapituushistogrammit erottavat neljä lopputulosta — onnistuneet osumat, osumayritykset, 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 suorituspatologiat näkyviksi yhdellä silmäyksellä: terveessä ajossa useimmat kontekstit näkyvät joko täsmättyinä tai absorboituina ja epätäsmäyspituudet ovat pieniä.
Kaksi Nav Mark -laskuria raportoivat tuplestoren säilytysbudjetin, jonka §3.3 johtaa DEFINE:stä. Lookback on syvin nykyisestä rivistä taaksepä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ä elementtitaulukosta rakennetun Pattern:-rivin, joten se näyttää kuvion käännösaikaisten uudelleenkirjoitusten jälkeen (PATTERN (A A) selittyy muodossa a{2}) ja kantaa absorptiomerkit # (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 ohitusvaihtoehto, on pg_get_viewdef():n tehtävä, ja se pitää huolen siitä, että tämä edestakaisinmatkustaminen on vakaa, jotta pg_dump ja pg_upgrade voivat säilyttää RPR-objektit ilman semanttista poikkeamaa — rpr_explain-regressiopaketti varmistaa sen tapaus tapaukselta (ks. §4).
§4. Testit — kattavuuskartta
Korjauspaketti sisältää viisi regressiopakettia, jotka yhdessä testaavat jokaista §3:ssa kuvattua kerrosta — noin 22 000 riviä SQL:ää, kukin paketti keskittyen eri huoleen. Jako on tarkoituksellinen: parserin, ajoajan oikeellisuuden, suunnittelijavuorovaikutusten ja tulostemuotoilun 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 ikkunaskenaariot 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ä, syntaksimuodot, kvanttorit, navigoinnin jäsennys, virheviestit ja pg_dump/pg_upgrade-edestakaisinvakaus; lisäksi suunnittelija-kerros — kuvion optimointi, absorptioliput, optimoinnin varapolku, suunnittelijaintegraatio.
- rpr_nfa
- NFA-ajoaika — kolmivaiheinen silmukka, absorptio jokaisessa absorboituvassa muodossa ja kontekstin elinkaaren reunatapaukset.
- rpr_explain
- Tulostemuotoilu — NFA-tilastot, kuvion deparsointi, tunnistimen lainausmerkit, muodon vakaus uudelleenlatauksen yli.
- rpr_integration
- Suunnittelijavuorovaikutukset — vartijat, jotka estävät asiaan liittymättömiä ikkunaoptimointeja 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äännekuviot, monisymbolipartitiot. 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 navigointisiirtymien 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 suunnittelijahä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ää serialisointikierroksesta. Pääosa siitä on muodoltaan pieniä keskittyneitä koodipalasia — yksi syntaktista ominaisuutta kohden — pitkien realististen kyselyjen sijaan, koska tavoitteena on kattavuus eikä skenaariorealismi. Toinen osa, suunnittelija-kerros, kattaa kuvion optimoinnin, absorptiolippujen näytön ja analyysin, optimoinnin varapolun ja suunnittelijaintegraation (alikyselyt, liitokset, joukkooperaatiot, lajittelu ja ryhmittely).
Serialisointitestit ansaitsevat erityishuomiota. RPR-objektien (näkymät, materialisoidut näkymät, pg_dump-tuloste) on selvittävä luetteloesityksestä ilman semanttista poikkeamaa, mukaan lukien hienovaraisuudet kuten kvanttorin vastahakoisuuslippu tai yhdistetyn navigointilausekkeen tarkka muoto. Pieni joukko serialisointispesifisiä objekteja (näkymät rpr_serial_v* ja niiden taustataulut) jätetään tarkoituksella paikalleen ajon lopussa, jotta ympäröivä regressioinfrastruktuuri voi poimia ne ja testata pg_dump:n ja pg_upgrade:n niitä vasten. Muu testiasetelma puretaan tavanomaisesti. Viat kuten vastahakoisuuslipun katoaminen deparse–reparse-kierroksessa tulevat näkyviin vain, kun edestakainen matka testataan päästä päähän.
4.3 rpr_nfa — ajoaikamoottori
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 muuttujanimien taulukkoa, joka julistaa, mitkä DEFINE-muuttujat täsmäävät kullakin rivillä, parina kuvio, joka testaa tiettyä ajoajan käyttäytymistä. Taulukkoidiomi irrottaa ajoaikatestin DEFINE-arviointikoneistosta — testattavana on ”kun nämä muuttujat täsmäävät tässä, tuottaako NFA-silmukka odotetun osuman jänteen?”, ei ”laskeeko DEFINE-lausekearvioija 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 muuttujanimien 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));
Saraketaulukon lukeminen alaspäin on testiskenaarion 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ä lausekearviointi vaikuta merkittävästi tähän — = ANY on vain triviaali kerros, joka altistaa saraketaulukon DEFINE:lle, eikä se ole se, mitä testi testaa. Saman skenaarion kirjoittaminen numeerisella predikaatilla (price > PREV(price) ja vastaavat) sotkisi NFA-testin predikaattiarvioijan käyttäytymisen kanssa; taulukkoidiomi 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 tapausanalyysistä:
- yksinkertainen rajaton muuttuja (
A+) — kanoninen N-1-tiivistys; - kiinteäpituiset ryhmät (
(A B)+,(A B{2})+, kolmitasoinen sisäkkäinen((A (B C){2}){2})+); - johtava rajaton muuttuja kiinteällä jälkiliitteellä (
A+ B) — vain johtavaA+kantaa absorptiolippuja, 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 kandidaattiosuma on jo kirjattu pääkontekstiin. Kukin näistä karttoituu §3.6:n tiettyyn karsintasää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 (valvontanä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, pituushistogrammit matched/mismatched/absorbed/skipped) ilmestyvät
EXPLAIN ANALYZE:n alla teksti-, JSON- ja XML-muodossa dokumentoiduilla otsikoilla, ja Nav Mark Lookback ja Lookahead ilmestyvät täsmälleen silloin, kun DEFINE:n navigointi syöttää niitä. - Kuviot deparse:utuvat oikein — jokainen kvanttorimuoto, mukaan lukien vastahakoiset variantit ja rajatut muodot; jokainen vaihtoehto; jokainen ryhmä; jokainen
AFTER MATCH SKIP-muoto;INITIAL; navigointikutsut siirtymillä; yhdistetty navigointi. Deparse:utuneen tekstin on selvittävä parserin läpi muuttumattomana. - Tunnistimen lainausmerkit ovat oikein — kuviomuuttujat ja DEFINE-lausekkeet annetaan samoilla lainaussäännöillä kuin tavalliset SQL-tunnistimet, joten epätavalliset muuttujanimet 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 — suunnittelijavuorovaikutukset
PostgreSQL:n suunnittelijalla on monta optimointia, jotka toimivat ikkunakyselyihin — kehyksen kanonisointi, run-ehdon työntö, identtisten ikkunoiden poistoduplikointi, 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. Integraatiopaketti varmistaa, miten kukin näistä optimoinneista kohtelee RPR-ikkunoita — useimmat on kytkettävä pois tai ohitettava:
- Kehyksen kanonisointi
- Suunnittelija normaalisti uudelleenkirjoittaa
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING:n muotoonROWS UNBOUNDED PRECEDINGkehyksestä riippumattomille ikkunafunktioille kutenrow_number,rankjantile. RPR:n kehys on osuman jänne, ei aggregointiikkuna, ja sen on pysyttävä sanasta sanaan. - Run-ehdon työntö
- Monotoninen
WHERE-suodatin ikkunafunktion tulosteelle voidaan normaalisti työntää ikkunaoperaattoriin pysähdysehtona. RPR:lle tämä päättäisi kuviotäsmäyksen ennenaikaisesti, mahdollisesti katkaisten osumat keskellä venytystä. - Ikkunoiden poistoduplikointi (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 poistoduplikointi (eri DEFINE tai SKIP)
- Kaksi RPR-ikkunaa samalla
PATTERN:llä mutta eriDEFINE-lausekkeilla tai eriAFTER 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
- Ikkunaaggregaatit, 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ä kustannusarviointi 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, joukkooperaatioiden, 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-poistoduplikoinnin 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 optimoijavaihe 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.