2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition Mélymerülés

Vezetett áttekintés az ISO/IEC 19075-5 · SQL R020 PostgreSQL-implementációjáról — mit készítettünk el, mi maradt megírásra, és hogyan működik a valóságban.

Kísérőanyag a PGConf.dev 2026 rendezvényen kiállított poszterhez.
Tekintse át a szabványt, lépjen végig a kidolgozott példákon, böngéssze a tervezést, majd irányítson saját mintákkal egy élő NFA-szimulátort.
Vita: pgsql-hackers szál · legutóbbi javítás (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

MI előfordítás — hibák lehetségesek.

§1. A szabvány, a részhalmaz és a nyitott kérdések

1.1 A szabvány hatóköre

A Row Pattern Recognition az ISO/IEC 9075-2:2016 szabvánnyal került be az SQL-be, részletes leírását a kísérő ISO/IEC 19075-5:2021 dokumentum (5. rész, „Row Pattern Recognition”) tartalmazza.

A szabvány ugyanazon mögöttes gépezethez két felületet definiál. Az R010 jellemző egy MATCH_RECOGNIZE záradékot helyez el a FROM listában, származtatott tábla előállítása céljából; az R020 jellemző ugyanezt a mintalogikát egy WINDOW-specifikációba ágyazza, ablakfüggvény-kimenet előállítása céljából. A két felület szintaxisa és szemantikája nagyrészt közös (a 19075-5 §6.3.3 néhány R020-specifikus eltérést rögzít), funkcionálisan azonban különálló belépési pontok — egy adatbázis bármelyiket vagy mindkettőt implementálhatja.

Az itt tárgyalt javítássorozat kizárólag az R020 egy részhalmazát valósítja meg; a táblazáradék-forma szándékosan kívül esik a hatókörön.

Az R020-felület kicsi, de kifejező. Egy lekérdezés úgy csatol mintát az ablakhoz, hogy záradékokat ad egy olyan ablakspecifikációhoz, amelynek kerete ROWS BETWEEN CURRENT ROW AND …: a PATTERN egy reguláris kifejezést ír le elnevezett mintaváltozók felett, a DEFINE az egyes változókat azonosító Boole-predikátumot adja meg, az opcionális AFTER MATCH SKIP (alapértelmezés PAST LAST ROW) pedig azt szabályozza, hogyan helyezkednek el az egymást követő találatok a partíción belül.

A jellemzőt opcionális MEASURES, SUBSET, INITIAL/SEEK elemek, valamint a kisegítő CLASSIFIER() függvény teszi teljessé. (A szabvány MATCH_NUMBER() függvénye kizárólag az R010-felülethez tartozik — a 19075-5 §6.3.3 (6) kifejezetten kizárja az R020-ból.)

A javítás elegendő szókincset fed le ahhoz, hogy nem triviális lekérdezések is működjenek, de néhány olyan konstrukciónál megáll, amelyek implementációja még meg nem épült infrastruktúrától függ.

A szakasz további része a szabvány szókincsét aszerint particionálja, hogy mit támogat már a javítás, és mit hagy szándékosan későbbre. Az alábbi listák a javítássorozat jelenlegi állapotát tükrözik.

1.2 Megvalósított jellemzők

A megvalósított szókincs elegendő a kanonikus V-alakú, W-alakú és fordulási minták kifejezéséhez, amelyek elsősorban motiválják a row pattern recognitiont. Lefedi továbbá az összes szabványos kvantort — beleértve mind a hét vonakodó (reluctant) változatot: *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — és azt a négy navigációs primitívet, amelyekre a DEFINE-feltételeknek szükségük van szomszédos sorok összehasonlításához.

PATTERN záradék
A sorminta meghatározása az ablakspecifikáción belül; legfeljebb 240 különböző mintaváltozóval.
Ablakkeret
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING vagy ROWS BETWEEN CURRENT ROW AND n FOLLOWING, ahol n ≥ 1 (19075-5 §6.10.2); minden más keret elutasításra kerül, és kizárásként csak az EXCLUDE NO OTHERS fogadható el.
Regex: + * ? |
Szabványos kvantorok és alternáció.
Regex: ( ) csoportosítás
Zárójelezett részminták.
Regex: {n} {n,} {,m} {n,m}
Korlátozott ismétlésszámok.
Vonakodó *? +? ?? {n}? {n,}? {,m}? {n,m}?
Mind a hét vonakodó (nem mohó) változat, amelyet a szabvány definiál (ki van zárva az abszorpciós optimalizációból).
DEFINE záradék
Az egyes mintaváltozókat azonosító Boole-feltételek.
Univerzális sor-minta változó
A DEFINE-ban szereplő minősítetlen oszlophivatkozások (pl. csupasz Price) az aktuális sorra oldódnak fel, a 19075-5 §4.10/§4.16 szerint.
PREV, NEXT (eltolással)
Az aktuális sor előtti/utáni n-edik sor elérése (alapértelmezés 1); a belső argumentumot a navigált sornál értékelik ki.
FIRST, LAST (eltolással)
Találathoz viszonyított sor elérése; a FIRST(expr, n) a találat kezdetétől n-edik sort célozza, a LAST(expr, n) a legutóbbi találatsortól n sorral korábbit.
Összetett navigáció (négy forma)
Külső PREV/NEXT lépés egy belső FIRST/LAST tetejére rétegezve: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — a belső és a külső lépés egyaránt elfogadja a saját eltolását.
Navigációs nevek
A DEFINE-on belül minősítetlen hívásként írt PREV, NEXT, FIRST és LAST mindig navigációt jelent; az azonos nevű felhasználói függvényt ott sémával kell minősíteni.
Navigációs argumentumok
A PREV, NEXT, FIRST és LAST esetén a belső argumentumnak legalább egy oszlophivatkozást kell tartalmaznia, az eltolásnak pedig futásidejű konstansnak kell lennie.
INITIAL
A mintaillesztésnek az aktuális sornál kell kezdődnie (alapértelmezés).
AFTER MATCH SKIP PAST LAST ROW
Alapértelmezett ugrási mód; alkalmas kontextusabszorpcióra.
AFTER MATCH SKIP TO NEXT ROW
Átfedő találatokat tesz lehetővé; letiltja az abszorpciót.

1.3 Nem megvalósított

A megvalósítatlanul maradt jellemzők három laza csoportba sorolhatók. Az első — és messze a legnagyobb — a MEASURES köré szerveződő konstrukciók családja: maga a MEASURES záradék, a SUBSET, a CLASSIFIER(), mintával minősített oszlophivatkozások, mint például a B.price, és mintával minősített navigáció, mint a LAST(B.price) vagy PREV(B.price).

Ezek nem annyira független hiányosságok, mint inkább egyetlen hiányzó elem különböző nézetei: az executornak találatonkénti előzményt kellene megőriznie — minden találatbeli sorhoz feljegyzést arról, melyik mintaváltozóhoz lett hozzárendelve —, e nélkül egyik konstrukciónak sincs értelmes definíciója. A CLASSIFIER() kiolvassa a változónevet ebből a feljegyzésből; a B.price azon sorok ár oszlopát olvassa, amelyek feljegyzésében B szerepel; a LAST(B.price) ugyanazt a sorhalmazt bejárja, és kiválasztja az utolsót; a SUBSET U = (A, B) olyan virtuális változót definiál, amely mindkét vödörre összesít; a MEASURES pedig AVG(U.Price)-szerű kifejezéseket pontosan ezzel az aggregációval értékel ki.

A jelenlegi executor a DEFINE-predikátumokat soronként értékeli ki, de a kapott változó-hozzárendeléseket sehol nem rögzíti — később nincs mit lekérdezni. Az előzmény-infrastruktúra felépítése tehát az egész csoport előfeltétele; az egyes jellemzők kis vetületekként adódnak, amint a feljegyzések léteznek.

A második csoport az alternatív ugrási célokat érinti: AFTER MATCH SKIP TO FIRST változó és AFTER MATCH SKIP TO [LAST] változó (a csupasz SKIP TO változó jelentése SKIP TO LAST változó). Ezek is a találat-előzményen múlnak, mivel az executornak rá kell tudnia mutatni a legutóbbi találaton belül arra a sorra, amely egy adott változóhoz van leképezve.

A fennmaradó tételek heterogén csoportot alkotnak: a SEEK kulcsszó (az INITIAL alternatívája), az üres minta (), a kizárási forma {- … -}, a sorrendre érzéketlen PERMUTE operátor, valamint a DEFINE-beli aggregátum függvények és alkérdések, amelyeket a javítás jelenleg egyaránt elutasít (egy változóval minősített aggregátumhoz a találat-előzményre is szükség lenne).

MEASURES
Találatonkénti, elnevezett kimeneti kifejezések, pl. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; R020-ban OVER révén jelenik meg ablakfüggvényként. Elfogadja a FINAL / RUNNING kulcsszavakat (19075-5 §5.4), amelyek R020-ban ugyanarra az értékre esnek össze, mivel a mértékeket mindig a találat utolsó során értékelik ki (19075-5 §6.9 (3)).
SUBSET
Mintaváltozók elnevezett uniói, pl. SUBSET U = (A, B, C). Bárhol használható, ahol mintaváltozóra hivatkozni lehet — MEASURES, mintával minősített hivatkozások a DEFINE-ban, CLASSIFIER(U) —, amelyek mindegyike találat-előzményt igényel.
CLASSIFIER()
Visszaadja, hogy egy adott sor melyik mintaváltozóként lett illesztve. Mind a DEFINE-ra, mind a MEASURES-re definiált (19075-5 §5.9); a válasz egy adott sornál az adott sorhoz a találat-előzményben rögzített változónév.
Mintával minősített oszlophivatkozás
Csupasz B.price a DEFINE-ban vagy MEASURES-ben — az oszlop értéke abból a sorból, amely az elnevezett változóként van leképezve.
Mintával minősített navigáció
A navigáció korlátozása az elnevezett változóként illesztett sorokra, pl. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).
SEEK
A találat az aktuális sortól a teljes ablakkeret végéig bármely sornál kezdődhet (az INITIAL ellentéte).
AFTER MATCH SKIP TO FIRST változó
Ugrás az elnevezett változóként illesztett első sorra.
AFTER MATCH SKIP TO [LAST] változó
Ugrás az elnevezett változóként illesztett utolsó sorra.
Regex: {- -}
Kizárás — eltávolítja az illesztett sorokat az ALL ROWS PER MATCH kimenetéből. Ez az opció ablakokra nem vonatkozik (19075-5 §6.3.3 (4)), így ablakban a szintaxis megengedett (§6.13), de nincs olyan kimenet, amelyre hatna.
Regex: ()
Üres minta — az üres szekvenciára illeszkedik.
PERMUTE(...)
Sorrendre érzéketlen illesztés a felsorolt változók között. A kulcsszót a rendszer felismeri és elutasítja („PERMUTE is not supported”); a permute továbbra is használható mintaváltozó-névként.
Aggregátum függvények a DEFINE-ban
A SUM, AVG, COUNT jellegű aggregátumok nem engedélyezettek a DEFINE-predikátumokban. A szabvány futó aggregátumokként megengedi őket a részleges találat felett; egy változóval minősített aggregátum, mint például az AVG(B.Price), ugyanazon találatonkénti előzménytől függ, amelyet a MEASURES/CLASSIFIER() is igényel, míg egy minősítetlen a találat eddigi összes során fut végig.
Alkérdések a DEFINE-ban
A DEFINE-ban minden alkérdés elutasításra kerül. A szabvány megengedi azt, amely nem végez row pattern recognitiont és nem hivatkozik sormintaváltozóra; a javítás egyelőre a szükségesnél többet utasít el.

Itt érdemes négy további pontot megemlíteni, mivel könnyen összetéveszthetők hiányosságokkal.

Az első, hogy a minta-horgonyok ^ és $ a WINDOW záradékban folyó RPR-rel maga a szabvány által nem engedélyezettek (19075-5 §6.13: „the anchors (^ and $) are not permitted with row pattern matching in windows”; a mögöttes definícióval a 19075-5 §4.14.1-ben); hiányuk megfelelés, nem pedig hiányosság.

A második, hogy a MATCH_NUMBER() hasonlóképpen ki van zárva az R020-ból a szabvány által (19075-5 §6.3.3 (6) és 19075-5 §6.9 (1)) — kizárólag az R010-felület része, hiánya itt szintén megfelelés, nem hiányzó jellemző.

A harmadik a szabvány által az R020-ra rótt strukturális tiltások halmaza (19075-5 §6.17): a row pattern recognition nem ágyazható másik row pattern recognitionbe; a MEASURES és a DEFINE nem tartalmazhat külső hivatkozásokat; a MEASURES vagy DEFINE belüli alkérdések nem hivatkozhatnak sormintaváltozókra (a javítás ennél tovább megy, és a DEFINE-ban minden alkérdést elutasít, ahogy fent szerepel); továbbá az RPR rekurzív lekérdezésen belül nem használható. A javítás érvényesíti a külső hivatkozásra vonatkozó szabályt („cannot use outer query column in DEFINE clause”) és a rekurzióra vonatkozó szabályt, az utóbbit egy WITH RECURSIVE záradék minden elemére. Emellett elutasítja a volatile függvényeket és a teljes sorra mutató hivatkozásokat a DEFINE-ban.

A negyedik az, hogy maga a MATCH_RECOGNIZE — az R010 jellemző, ugyanazon gépezet táblazáradék-felülete — kívül esik e javítás hatókörén. Hogy a PostgreSQL végül hozzáad-e R010-et, az egy jövőbeli sorozat kérdése lesz, nem ennek mércéje.

Eredet. Az e szakaszban szereplő megvalósított és nem megvalósított listák a javítássorozat aktuális állapotát tükrözik — konkrétan a v55-öt (2026-11-17).

§2. Példák — Hogyan működik a valóságban

A szakasz példái fokozatosan épülnek fel. Először annak fogalmi okát tárgyaljuk, hogy a sormintaillesztés miért alapvetően különbözik a szövegmintaillesztéstől, majd bemutatjuk azt a négy navigációs függvényt, amelyek a DEFINE-feltételeket érdekessé teszik, végül öt kidolgozott példát mutatunk be: egyetlen találat (NFA-mozgás), alternáció, kontextusabszorpció a könnyű esetben, és két eset, amikor az abszorpció le van tiltva.

A navigációt olcsóvá tévő belső mechanizmus — az 1-slotos tuple-csere — az executor tervezéséhez tartozik, és a következő szakaszban tárgyaljuk, nem itt.

2.1 Miért különböznek a sorminták a szövegmintáktól

A szöveges reguláris kifejezés karakterek folyamára illeszkedik, és minden pozícióban pontosan egy szimbólumot kell figyelembe venni. A futási idejű kérdés — „egyenlő-e az aktuális szimbólum az 'A'-val?” — egyetlen igen/nem választ ad. A visszalépő automaták ezt használják ki: karakterenként legfeljebb egy ág marad életben, és a többértelműség költségét a bemenet újraolvasásával fizetik meg.

A sorminta alapvető módon különbözik. Egy sor nem egyetlen szimbólum; oszlopok tuple-ja, amelyet Boole-predikátumok egy halmaza, a DEFINE-feltételek ellen értékelnek ki. Két predikátum egyidejűleg igaz lehet ugyanazon a soron, és semmi nem mondja a szabványban, hogy egymást kizáróaknak kellene lenniük. Tekintsük a következőt:

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

Egy price = 150, volume = 2000 sor egyaránt kielégíti az A-t és a B-t, de a C-t nem. A mintaillesztő ezt nem tudja egyetlen állapotra összevonni — két mintaváltozó él, és bármely mintaelem, amely valamelyiküket nevezi meg, előreléphet. Az NFA-nak ezért partíciósoronként több egyidejű állapotot kell hordoznia, nem egyet.

Text regex vs row pattern: a single state advances per symbol, while multiple DEFINE predicates can match a row in parallel. TEXT REGEX single state advances through symbols A B C one symbol per position · one transition ROW PATTERN one row, multiple predicates evaluated row price = 150 · volume = 2000 A ✓ price > 100 B ✓ volume > 1000 C ✗ price > 200 two predicates true · two states stay alive
A szöveges regex szimbólumonként egyetlen állapotra esik össze; egy sor több DEFINE-predikátumot is kielégíthet egyszerre, így párhuzamosan több állapot marad életben.

Ez az egyetlen megfigyelés vezérli az architektúra többi részét. A végrehajtási állapot kontextusok listája, minden kontextus állapotok listája, és minden sornál a futtató minden állapottól megkérdezi: „adott az itt igaz változók halmaza, hová léphetek?” Az ebből adódó elágazások miatt van szüksége a futtatónak több metszési rétegre — kontextuson belüli állapot-deduplikáció, kontextusok közötti abszorpció és a §3.6-ban áttekintett további szabályok —, amelyek nélkül az élő állapotok és kontextusok száma a partícióval együtt nő, és a mintaillesztés szuperlineárissá válik.

2.2 Navigációs függvények

A csak az aktuális sorra hivatkozó DEFINE-feltételek korlátozottak; szinte minden érdekes mintának össze kell hasonlítania az aktuális sort a szomszédaival vagy a találatban korábban elfogadott sorokkal. A szabvány négy navigációs függvényt biztosít erre, és a javítás mindegyiket megvalósítja.

PREV(expr [, n])
Az aktuális sor előtti n-edik sor (alapértelmezés n = 1). „Ma vs. tegnap” összehasonlításokhoz.
NEXT(expr [, n])
Az aktuális sor utáni n-edik sor (alapértelmezés n = 1). Előretekintés; az ablak formában ritka, mert az ablak monoton.
FIRST(expr [, n])
Az aktuális találat első sora után n sorral következő sor (alapértelmezés n = 0, maga az első sor). „Hasonlíts az e találatot indító sorhoz.”
LAST(expr [, n])
Az utolsó illesztett sor előtt n sorral lévő sor (alapértelmezés n = 0). A DEFINE-on belül az utolsó illesztett sor az aktuális sor, így a LAST(price) az aktuális sort olvassa.

A négy primitív összetehető: a PREV és a NEXT körbe foghat egy FIRST- vagy LAST-hívást, így négy összetett formát adva, amelyek szemantikája: „menj egy találathoz viszonyított sorra, majd lépj rögzített távolságra tőle”. Ez teszi lehetővé, hogy egy DEFINE-kifejezés például a találat kezdete előtti sort olvassa.

PREV(FIRST(expr [, n]) [, m])
Lépj m sort vissza attól a sortól, amelyet a FIRST(expr, n) olvas (alapértelmezések n = 0, m = 1). „Mi volt az érték közvetlenül a találat kezdete előtt?”
NEXT(FIRST(expr [, n]) [, m])
Lépj m sort előre attól a sortól, amelyet a FIRST(expr, n) olvas. Mélyebbre nyúl a találatba anélkül, hogy az aktuális sortól függne.
PREV(LAST(expr [, n]) [, m])
Lépj m sort vissza attól a sortól, amelyet a LAST(expr, n) olvas. „Hasonlíts egy nem sokkal a legutóbbi illesztett sor előtti sorhoz.”
NEXT(LAST(expr [, n]) [, m])
Lépj m sort előre attól a sortól, amelyet a LAST(expr, n) olvas.

Itt két gyakorlati szempontot érdemes említeni. Először, a navigáció összetehető: a PREV(FIRST(price)) a találat kezdete előtti sort olvassa, és a javítás ezt támogatja. Másodszor, a navigációnak vannak az executor optimalizációira nézve következményei. Az önálló PREV és NEXT az aktuális sorhoz viszonyított, és mindig biztonságos; a FIRST és a LAST eltolásos változatai — önmagukban vagy egy összetett PREV/NEXT belsejében — a találat határaihoz viszonyítottak, ami befolyásolja a kontextusabszorpciót: ilyenkor a tervező a teljes mintára letiltja az abszorpciót. Az e kölcsönhatás mögötti mechanizmus a §2.6 témája.

2.3 Kidolgozott példa 1 — NFA-mozgás

A példa céljaBemutatni a soronkénti NFA-állapotfejlődést egy egyszerű, nem abszorbeáló mintán. A nyomkövetés a 0. sornál indult kontextust követi; az 1–4. sornál indult kontextusok mellette futnak, és a SKIP PAST LAST ROW eldobja őket, amint ennek a kontextusnak a találata rögzítésre került.
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)
);

A minta négy elemre lapul:

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

A 100, 110, 120, 115, 108, 130 ársorozatra:

SorÁrIgaz változókMűvelet
0100STARTÚj kontextus. A START illeszkedik és azonnal kilép (max=1); az állapot UP+-ra lép.
1110START, UPAz UP illeszkedik. Az előrelépés elágazik: az egyik állapot UP-on hurkol, a másik DOWN+-ra lép ki.
2120START, UPAz UP illeszkedik a hurkoló állapotban, és újra elágazik. Az 1. sorból származó DOWN állapot meghal (120 ≮ 110).
3115START, DOWNAz UP elbukik a hurkoló állapoton, és meghal. A 2. sorból származó DOWN állapot illeszkedik. Az előrelépés elágazik: hurkolás DOWN-on, és kilépés #FIN-re — rögzítésre kerül egy találatjelölt a 0–3. sorok felett.
4108START, DOWNA DOWN illeszkedik a hurkoló állapoton, és újra elágazik; a 0–4. sorok feletti új FIN-jelölt felváltja a rövidebbet.
5130START, UPA hurkoló DOWN állapot elbukik (130 ≮ 108). Mivel ebben a kontextusban nem maradt élő állapot, a rögzített jelölt (0–4. sorok) találatként véglegesül. A következő kísérlet az 5. sornál indul; a START illeszkedik, de a partíció véget ér, mielőtt bármely UP következne.

A lényeg: a 3. sorban a sor egyaránt kielégíti a START-ot (mindig igaz) és a DOWN-t, de a START csak egy a 3. sornál induló kontextus számára számít; ebben a kontextusban a hurkoló UP állapot meghal, és csak a DOWN+-on várakozó állapot lép tovább. A §2.1 többállapotú jellege minden UP-illeszkedésnél elágazásként jelenik meg (az állapot maradhat UP+-on vagy léphet DOWN+ felé). A mohó preferencia: „hurkolj újra, mielőtt kilépnél”, így elegendő adat esetén a hurkoló ágak tovább nyújtanák a találatot; itt a hurkoló DOWN az 5. sorban meghal (130 ≮ 108), és az utolsó FIN-jelölt (0–4. sorok) — amely akkor jött létre, amikor a DOWN a 4. sorban kilépett, felváltva a 3. sori jelöltet — találatként véglegesül.

A lekérdezés eredménye közvetlenül ebből a nyomkövetésből adódik. RPR-szemantika alatt a first_value(price) és last_value(price) ablakfüggvények csak a találatot indító soron értékelődnek ki — a találat minden más sora NULL-t ad ezekre az ablakfüggvényekre, mivel csökkentett kerete üres. Az adatainkra adódó kimenet tehát úgy néz ki, ahogyan azt a poszter a jobb felső paneljén mutatja:

SorÁrstart_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

A 0. sor a találat kezdete, így kerete a 0–4. sorokat fedi, és az ablakfüggvények a V-alak nyitóárát ($100) és aljárát ($108) adják. Az 1–4. sorok a találaton belül, de nem annak kezdetén vannak, így NULL-t kapnak. Az 5. sor (ár $130) bármely találaton kívül esik, és szintén NULL-t kap.

2.4 Kidolgozott példa 2 — Alternáció és lexikai sorrend

A példa céljaBemutatni, hogyan hordoz egyetlen kontextus több párhuzamos állapotot, amikor egy sor egynél több alternatívát elégít ki — és hogyan dönt a szabvány a holtversenyekről.

Az (A | B) forma választást ad az illesztőnek: bármely sornál a két alternatívát egymástól függetlenül teszteljük, és bármennyi illeszkedhet közülük. Itt válik láthatóvá a §2.1 többállapotú jellege egyetlen kontextuson belül — nem kontextusok között (ez az abszorpció), hanem párhuzamos ágak mentén, amelyeket az executor a minta sorrendjében tár fel, a korábbi ágat előbb.

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

Képzeljünk el egy sort, ahol az ár egyszerre emelkedett és meghaladta a $100-t — mind az UP, mind a HIGH igaz. Mindegyik alternatíva saját állapotot szül: az egyik az UP ágat járja, a másik a HIGH ágat. Ezután mindkettő a DONE-ra lép, ahol találkoznak.

SorIgaz változókÉlő állapotok
RUP, HIGHAz A állapot (UP-ág) és a B állapot (HIGH-ág) egyaránt azonos számlálókkal lép a DONE-ra; B az A duplikátuma, és eldobásra kerül
R+1DONEAz A állapot illeszkedik a DONE-ra, és eléri a #FIN-t

A szabvány fogalmai szerint mindkét ág azonos hosszúságú találatot termel ugyanazokon a sorokon, ami két jelölt utat ad — az egyiket UP, DONE, a másikat HIGH, DONE címkéje jelöli. A szabvány lexikai sorrend alapján dönt: az (UP | HIGH)-ban felírt alternatívák közül az nyer, amely előbb szerepel, függetlenül a találat hosszától. Mivel az UP a HIGH előtt áll, a túlélő út az UP, DONE. Az executor ezt az R sornál érvényesíti, nem a FIN-nél: az UP-ági állapotot veszi fel elsőként, így a nfa_append_state_unique() azt tartja meg, és eldobja a vele azonos HIGH-ági állapotot.

A lexikai sorrend teszi jól definiálttá a CLASSIFIER()-t, amikor majd megvalósítják — lehetővé teszi a futtatónak, hogy közölje a felhasználóval: „ez a sor UP-ra illeszkedett, nem HIGH-ra”, még ha mindkét predikátum igaz volt is. A lexikai sorrend az alternáció elsődleges szabálya: egy lexikailag korábbi ág győz egy lexikailag későbbivel szemben akkor is, ha a későbbi hosszabb találatot adna; a lexikailag későbbi (esetleg rövidebb) ág pedig akkor győzhet, ha minden korábbi ág elhal a FIN elérése előtt. A mohó hosszt egyetlen kvantoron belül dönti el a rendszer — ugyanazon alternációs ág két befejezése közül a mohó kvantor a több iterációt részesíti előnyben.

2.5 Kidolgozott példa 3 — Kontextusabszorpció (azonos sors)

A példa céljaBemutatni, miért válik a naiv O(n²) teljes állapotmunka O(n)-né abszorpció esetén, O(1) élő kontextussal.

A legegyszerűbb minta, amely abszorpciót mutat, a PATTERN (A+) a DEFINE A AS TRUE-val. Minden sor illeszkedik az A-ra, és a szabvány előírja, hogy az illesztőnek minden sort lehetséges találatkezdetnek kell tekintenie. Naivan ez N kontextust jelent egy N soros partícióhoz. Vegyünk egy öt soros partíciót (bármilyen adat — a predikátum konstans igaz):

SorNaiv kontextusokAbszorpcióval
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 abszorbeálva
2C1[A:3], C2[A:2], C3[A:1]C1[A:3]
3C1[A:4], C2[A:3], C3[A:2], C4[A:1]C1[A:4]
4öt kontextusC1[A:5]

Az élő kontextusok száma O(n)-ről O(1)-re csökken, így a partíció egészére vett összesített munka O(n²)-ről O(n)-re esik. Az eldobást indokló abszorpciós szabály egyszerű, amikor a kvantor korlátlan:

Abszorpciós szabály. Két kontextus, amelyek élő állapota ugyanazon a mintaelemen áll, és ahol az idősebb kontextus számlálója ≥ az újabbé, korlátlan kvantor mellett azonos jövővel rendelkezik. Az újabb kontextus eldobható; bármilyen találatot is találna végül, az idősebb kontextus hosszabbat vagy azzal egyenlőt fog találni.

A poszter bal alsó panele („① Context Absorption”) pontosan ezt a szabályt vizualizálja öt soron.

Egy finom, de fontos pont rejlik a szabályban: az eldobás biztonságos, mert az A AS TRUE predikátum minden soron ugyanazt az értéket adja, függetlenül attól, melyik kontextus kérdezi. Ugyanez igaz minden olyan predikátumra, amely csak az aktuális sorra vagy ahhoz képest rögzített eltolásra hivatkozik — beleértve a PREV-et is. A következő példa egy konkrét árhétre vált át, PREV-alapú predikátummal, és a §2.6 pontosan ugyanazt a hetet újrahasználja, hogy a biztonságos és a biztonságtalan abszorpció szimmetriáját nyilvánvalóvá tegye:

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

Vegyük a hétfőtől péntekig tartó $100, $108, $112, $116, $110 kereskedési hetet — négy emelkedést egy hirtelen esés követ. Tegyük fel, hogy C1 kedden indul (az első nap, amikor a RISE illeszkedik: $108 > $100), és az executor spekulatívan szerdán induló C2-t is követ. Minden sor RISE-feltétele a sor árát közvetlen elődjének árával hasonlítja össze — partíciószintű tény, nem kontextusszintű —, így a két kontextus minden közös sorukon kénytelen ugyanazt a Boole-értéket számolni:

NapÁrC1 — Kedd indít
price > PREV(price)
C2 — Szerda indít
price > PREV(price)
Hét$100——
Kedd$108$108 > $100 ✓ (épp indult)—
Szer$112$112 > $108 ✓$112 > $108 ✓ (épp indult)
Csüt$116$116 > $112 ✓$116 > $112 ✓
Pén$110$110 > $116 ✗ — véglegesítés$110 > $116 ✗ — véglegesítés
Azonos sors Minden közös sornál a C1 és a C2 azonos kifejezéseket értékel ki, azonos eredményekkel — és pénteken pontosan ugyanazon az összehasonlításon halnak meg. Bármi is C2 jövője, az a C1-é is. C2 C1-be való abszorbeálása semmit nem dob el.

A történet abban a pillanatban összeomlik, amint a predikátum az egyes kontextusok saját határaitól kezd függeni — és pontosan erről szól a §2.6.

2.6 Kidolgozott példa 4 — Mikor válik biztonságtalanná az abszorpció

A példa céljaBemutatni, mi változik, amikor a DEFINE a FIRST-re hivatkozik — az abszorpciós szabály már nem áll, és a tervező letiltja a mintára az abszorpciót.

Tegyük fel, hogy egy elemző olyan egymást követő kereskedési napokat keres, amikor egy részvény a futás kezdetét adó nap árának tíz dolláros sávjában maradt — egyfajta konszolidációs ablakot. A minta és a DEFINE így néz ki:

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

A feltétel most az aktuális sor árát az aktuális futás kezdetén lévő árhoz hasonlítja. Két futás, amely különböző napokon indult, eltérő FIRST(price) értékkel rendelkezik, így két állapot ugyanazon a mintaelemen és ugyanazon számláló mellett már nem cserélhető fel: jövőjük attól a határtól függ, amelyet az abszorpció eldobni készült.

Vegyük pontosan ugyanazt a kereskedési hetet, mint a §2.5-ben — $100, $108, $112, $116, $110 hétfőtől péntekig. A futtató ismét két jelölt futást tart életben egyszerre: C1 hétfőn indult, C2 kedden indult (minden sor potenciális futáskezdet a STABLE+ alatt).

NapÁrC1 — Hétfő indít
FIRST = $100
price < $100 + 10
C2 — Kedd indít
FIRST = $108
price < $108 + 10
Hét$100$100 < $110 ✓—
Kedd$108$108 < $110 ✓$108 < $118 ✓ (épp indult)
Szer$112$112 < $110 ✗ — Hét–Kedd véglegesítés$112 < $118 ✓
Csüt$116—$116 < $118 ✓
Pén$110—$110 < $118 ✓ (még fut)
Eltérő sorsok A C1 szerdán meghal kétnapos futással (Hét–Kedd); a C2 önmagában péntekig tovább futna. Ugyanazok az árak, ugyanaz a kérdés formája — de a saját találatkezdetükből származó eltérő plafonok. Pontosan ugyanazon a napon a két kontextus ellentétes következtetésre jutott.

Abszorpció esetén a C2-t kedden összeolvasztották volna a C1-be — az egyesített kontextus csak a C1 plafonját ($110) tartja meg, így a C2 saját nézetét (plafon $118, négynapos futás péntekig) a C1 jövője nem fedi le. Ezen a konkrét héten a kimenet véletlenül nem változik: a C1 a Hét–Kedd találatot rögzíti, a C2 e találaton belül indult, és a SKIP PAST LAST ROW eldobja, a következő kísérlet pedig szerdán indul saját plafonnal ($122), és a Szer–Pén sorokra illeszkedik. Általában azonban egy korábbi kontextus DEFINE-eredménye már nem foglalja magában egy későbbiét, így az abszorpció által használt számláló-összehasonlítás érvénytelen. Valahányszor egy DEFINE-predikátum találatkezdet-függőséget hordoz, a tervező ezért preventíven letiltja az abszorpciót.

(Amikor a vezető kontextus találata sikeresen lezárul, az elfogadott szakaszán belül indult kontextusokat — az alapértelmezett AFTER MATCH SKIP PAST LAST ROW alatt — egyszerűen eldobjuk; csak azért tartjuk őket életben, hogy a futtatónak legyen visszaesési pontja, ha a vezető találat elbukik.)

Az alábbi táblázat az összetett formákkal bővíti a poszter jobb alsó paneljét („② Navigation”), és összefoglalja, mely navigációs formák hoznak létre találatkezdet-függőséget:

NavigációTalálatkezdet-függőségAbszorbeálható?
PREV, NEXTnincsigen
LAST (eltolás nélkül)nincsigen
LAST eltolássalhatárellenőrzésnem
FIRST (bármilyen)közvetlennem
Összetett (belső FIRST)közvetlennem
Összetett (belső LAST, eltolás nélkül)nincsigen
Összetett (belső LAST eltolással)határellenőrzésnem

A §2.5 és §2.6 két példája egyetlen szabályra redukálható. Az azonos sors teszi az abszorpciót biztonságossá: ha minden, ugyanazon a mintaelemen lévő kontextus minden jövőbeli predikátumra ugyanazt a választ adja, csak a legidősebbet kell megtartani. Az eltérő sorsok az abszorpciót biztonságtalanná teszik: amint a predikátumok kontextus-privát állapotra ágaznak — ezt teszi pontosan a FIRST és az eltolásos LAST —, minden élő kontextus olyan jövőt képvisel, amelyet egyetlen más kontextus sem fed le garantáltan, így egyikük eldobásáról sem mutatható már ki, hogy biztonságos.

A tervező ezt a megkülönböztetést fordítási időben felismeri, és a teljes mintára be- vagy kikapcsolja az abszorpciót; ha ki van kapcsolva, a futtató megfizeti a többkontextusú költséget. A poszter ③ paneljében szereplő benchmark nem használ FIRST-et, így az abszorpció bekapcsolva marad, ezért marad a PostgreSQL mind a sikeres, mind a sikertelen esetben lineáris.

A poszteren látható benchmark-számok ugyanazt az algoritmust mutatják skálán. A sikeres (A+ B+ C+ D) mintán mind a PostgreSQL, mind a Trino nagyjából O(n)-ben skálázódik, ha a találat megerősödött, és a PostgreSQL durván 16×–33×-os előnyben van (a Trino-számok a JVM indítását már nem tartalmazzák).

A sikertelen (A+ B+ C+ E) mintán a Trino, amelyből láthatóan hiányzik az abszorpció, minden potenciális találatkezdet után fut, és még az O(n²)-nél is gyorsabban romlik (5× annyi sorra kb. 56× annyi idő); 100 000 sornál több mint öt óráig tart, miközben a PostgreSQL még mindig 92 ms-ban végez, ami körülbelül 217 000× gyorsulás.

Ez a rés nem mérnöki finomítás — pontosan a §2.5 és §2.6 azonos-sors / eltérő-sors megkülönböztetése, alkalmazva a partíció minden potenciális találatkezdetére.

2.7 Kidolgozott példa 5 — Mikor tiltja le a SKIP az abszorpciót

A példa céljaBemutatni az abszorpció bukásának második módját: nem azért, mert a predikátum elágazik, hanem mert a kimenetszemantika minden találat külön közlését kívánja.

Az előző példa az abszorpciót az adat oldaláról törte meg: a DEFINE-beli FIRST miatt minden kontextus eltérően értékelte a predikátumokat. Az abszorpció a kimenet oldaláról is megtörhet, és ezt az AFTER MATCH SKIP záradék szabályozza.

Tekintsük a PATTERN (A+) mintát DEFINE A AS TRUE-val öt sor felett, amelyek mindegyike illeszkedik az A-ra. Az alapértelmezett AFTER MATCH SKIP PAST LAST ROW alatt az illesztő a legkorábbi sorból induló leghosszabb találatot találja meg, majd átugorja; minden olyan kontextust, amely e találaton belül indult, implicite eldob redundánsként — pontosan az a helyzet, amit az abszorpció kezelni hivatott. A kimenet egyetlen találat, a 0–4. sorok, és a futtatónak csak egy élő kontextusra van szüksége.

Váltsuk az ugrási módot AFTER MATCH SKIP TO NEXT ROW-ra, és a szerződés megváltozik:

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

Most minden potenciális kezdőpozíciót külön közölni kell, akkor is, ha a találatok átfednek. Ugyanazon az öt soron a futtatónak öt találatot kell kibocsátania: 0–4, 1–4, 2–4, 3–4 és 4–4. Egyiket sem helyettesítheti egy „korábban induló hosszabb”, mert a szabvány szerint a felhasználó mindet kéri.

SorSKIP PAST LAST ROWSKIP TO NEXT ROW
0találat indul; a 0–4. sorok lesznek az egyetlen találattalálat indul a 0. sornál
1(a 0. találaton belül)találat indul az 1. sornál — életben kell tartani
2(a 0. találaton belül)találat indul a 2. sornál — életben kell tartani
3(a 0. találaton belül)találat indul a 3. sornál — életben kell tartani
40. találat véglegesedik (0–4. sorok)öt találat véglegesedik: 0–4, 1–4, 2–4, 3–4, 4–4
Eltérő kimenet, eltérő sorsok Az AFTER MATCH SKIP TO NEXT ROW alatt minden későn induló kontextus saját kimeneti sor. Két, ugyanazon a mintaelemen lévő kontextus már nem redundáns — mindkettő elvárt kimenet, és bármelyikük eldobása csendben eldobna egy találatot, amelyet a felhasználó kért.

Vegyük észre, hogy a predikátum nem változott. Az A AS TRUE minden soron ugyanúgy értékelődik ki, függetlenül attól, melyik kontextus kérdezi, így a §2.5 azonos-sors feltétele továbbra is teljesül. Ami változik, az a kimeneti követelmény: még az azonos jövőjű kontextusoknak is együtt kell létezniük, mert az eredmény különálló sorainak felelnek meg. A tervező ezért letiltja a kontextusabszorpciót minden olyan esetben, amikor az AFTER MATCH SKIP TO NEXT ROW érvényes, a DEFINE-záradéktól függetlenül.

A §2.6 és §2.7 egymás mellé helyezése megmutatja azt a két módot, ahogyan egy lekérdezés szemantikája kizárja az abszorpciót:

Adatoldal · §2.6
A predikátum kontextusonként eltérően értékelődik ki.
Kiváltja: FIRST vagy eltolásos LAST a DEFINE-ban.
Kimeneti oldal · §2.7
A kimenet minden találatkezdetet külön sorként követel meg.
Kiváltja: AFTER MATCH SKIP TO NEXT ROW.

Bármelyik feltétel elegendő ahhoz, hogy a teljes mintára letiltsa az abszorpciót, és ugyanígy az is, ha a keret nem UNBOUNDED FOLLOWING-nál ér véget. Ha egyik sem érvényes — az alapértelmezett AFTER MATCH SKIP PAST LAST ROW, korlátlan keretvég, és csak PREV-, NEXT- vagy csupasz LAST-feltételeket használó DEFINE —, az abszorpció engedélyezett, de csak a minta abszorbeálható régiójában lévő állapotokra: ez egy vezető mohó korlátlan változó, mint az A+ vagy az A*, egy korlátlan mohó kvantorú, rögzített hosszúságú csoport, mint az (A B)+, egy mohó csoport, amelynek törzse ezek egyikével kezdődik, mint az (A+ B)+ vagy az (A+ B){2}, vagy ezekből épített alternációs ágak; egy vonakodó csoport a teljes részfáját kizárja. Ahol ez teljesül, mint az A+ esetén a §2.5-ben, a futtató egyetlen kontextusra esik össze, és lineáris marad; a §2.3 START UP+ DOWN+ mintája egyáltalán nem kap abszorbeálható régiót.

§3. Tervezés — A parsertől az executorig

A Row Pattern Recognition három szakaszban valósul meg, amelyek jól definiált köztes formákon át adják át a munkát. A parser SQL-szöveget mintafává és DEFINE-predikátumok listájává alakít; a tervező a fát mintaelemek lapos tömbjévé fordítja, és eldönti, melyek vehetnek részt a kontextusabszorpcióban; az executor a tömböt soronként, háromfázisú ciklusban futtatja a partíción. Minden szakasznak megvan a maga adatformája, és a tervezési leleményesség nagy része a határokon helyezkedik el: gyorsítótárba illő lapos NFA, egyetlen tuple-slotot újrahasználó navigációs modell hivatkozásonkénti materializálás helyett, és olyan abszorpciós szabály, amely az O(n²) memóriát O(n)-re redukálja.

SQL-szöveg
  │
  │  parser-szakasz
  ▼    keret validálása
       mintafa építése
       DEFINE típusellenőrzése

mintafa + DEFINE-lista
  │
  │  tervező-szakasz
  ▼    fa optimalizálása
       fordítás lapos NFA-tömbbé
       abszorbeálhatóság eldöntése

lapos NFA + abszorpciós jelzők
  │
  │  executor-szakasz
  ▼    soronkénti motor:
       Match → Absorb → Advance

találati eredmény:
  kezdősor, hossz, sikeres/sikertelen

Az alábbi szakaszok ezen a pipeline-on haladnak végig. A §3.1 a parsert és a mintafa alakját tárgyalja; a §3.2 a fát lapos NFA-vá fordító kompilációt; a §3.3 a navigációs modellt, amellyel a DEFINE-predikátumok szomszédos sorokra tekintenek; a §3.4 a találat-határok kezelését — a SKIP-, INITIAL- és korlátozott keretszabályokat, amelyek rögzítik, hol kezdődik és hol végződik egy találat; a §3.5 a háromfázisú soronkénti motor; a §3.6 az állapotteret korlátok között tartó metszési mechanizmusokat gyűjti össze; a §3.7 pedig azt tekinti át, mit ad vissza az implementáció az EXPLAIN kimenetében.

3.1 Parser — a mintafa felépítése

A parser akkor ismeri fel a pattern recognitiont, ha az ablakspecifikációban PATTERN záradék szerepel. Első feladata a keret validálása, mivel az RPR olyan megszorításokat ír elő, amelyeket a hagyományos ablaklekérdezések nem: a keret módja ROWS kell legyen (nem RANGE vagy GROUPS), a kezdő határnak CURRENT ROW-nak kell lennie, a záró határnak UNBOUNDED FOLLOWING-nak vagy pozitív eltolás FOLLOWING-nak (így az alapértelmezett keret is elutasításra kerül), és az EXCLUDE NO OTHERS-tól eltérő EXCLUDE opciók tiltottak. Ezek megfelelőségi ellenőrzések, nem optimalizációk — az RPR keretfogalma a találat-szakasz, és a szabvány nem számol azzal, hogy mást, mint az illesztett sorokat tegyünk bele.

Miután a keret átment a validáláson, a parser a PATTERN záradékot fává alakítja négyféle csomópontból — változóhivatkozás, szekvencia (konkatenáció), alternáció és csoport (zárójelezett részminta). Minden csomópont a kvantort három számként hordozza — alsó korlát, felső korlát (lehet végtelen), és a vonakodó illesztés jelzője:

ForrásFa-kódolás
AVAR(A, min=1, max=1)
A+VAR(A, min=1, max=∞)
A*VAR(A, min=0, max=∞)
A{3,5}VAR(A, min=3, max=5)
A+?VAR(A, min=1, max=∞, reluctant=true)

Ezt követően minden DEFINE-predikátumot típusellenőrzünk a partíció oszlopaihoz képest, és Boole-kifejezéssé kényszerítjük. Ebből két gyakorlati dolog következik. Először, a parse-elemzés semmit nem ad a lekérdezés céllistájához a DEFINE miatt; ehelyett a tervező minden DEFINE-predikátum által hivatkozott oszlopot szükségesként jelöl meg, ahogyan a HAVING esetén is, és ezeket az oszlopokat eljuttatja az executor-szakaszig akkor is, ha a környező lekérdezés nem szelektálja őket — e nélkül a futtatónak nem lenne mire kiértékelnie. Másodszor, a PATTERN-ben szereplő, de a DEFINE-ban soha meg nem jelenő változók implicit módon igazak: minden sorra illeszkednek.

3.2 Kompiláció — az AST-tól a lapos NFA-ig

A tervező a parser fáját az executor által futtatott adatszerkezetté alakítja: mintaelemek lapos, indexszel címezhető tömbjévé. A kompiláció hatlépéses pipeline-ként halad:

compile(astTree):
  1. AST optimalizálása
  2. méret és mélység mérése
  3. elemtömb allokálása
  4. feltöltés az AST-ből
       (next/jump mutatók beállítása)
  5. véglegesítés — FIN-őr beállítása
  6. abszorpciós elemek megjelölése

A lapos forma egyszerű okból választott: az executornak partíciónként sokszor kell végigjárnia a mintát, és egy összefüggő, indexszel címezhető tömb a legolcsóbb adatszerkezet a bejáráshoz. Az 1. és 6. lépés érdekes — az 1. azért, mert meghatározza, mekkora lesz a tömb, a 6. azért, mert eldönti, hogy a §2.5 abszorpciós optimalizációja egyáltalán beindul-e.

AST-optimalizáció

Az optimalizáció kétszer térül meg: egyszer a lapos tömb statikus elemszámában, majd minden futási idejű sornál. Minden transzformáció csökkenti a futtató által felsorolandó állapotteret. Az optimalizáló kilenc átírási szabályt alkalmaz egyetlen alulról felfelé haladó menetben (egy szekvencián belül a csoportegyesítés még egyszer lefut, mivel a korábbi egyesítések két azonos csoportot hozhatnak egymás mellé):

SEQ-laposítás
SEQ(A, SEQ(B, C)) → SEQ(A, B, C)
Egymás utáni változók egyesítése
A A → A{2}
A{2,3} A{1,2} → A{3,5}
Egymás utáni csoportok egyesítése
(A B)+ (A B)+ → (A B){2,∞}
Egymás utáni ALT egyesítése
(A | B) (A | B) (A | B) → (A | B){3}
Előtag/utótag-egyesítés
A B (A B)+ → (A B){2,∞}
ALT-laposítás és deduplikáció
(A | (B | C)) → (A | B | C)
(A | B | A) → (A | B)
Kvantorszorzás
(A+)+ → A+
(A{2,3}){5} → A{10,15}
Egygyermekes kibontás
SEQ(A) → A
(A){1,1} → A
Vonakodás normalizálása
A{2}? → A{2} (a vonakodás mindenütt törlődik, ahol min = max)

A kvantorszorzás csak akkor von össze, ha az elérhető számok egyetlen összefüggő intervallumot alkotnak, és az előnyben részesített találat nem mozdul el: pontos külső kvantor ((A{2,3}){5} → A{10,15}), 0 minimumú gyermek, vagy egymáshoz érő gyermekintervallumok legfeljebb 1-es gyermekminimummal vagy korlátlan gyermekmaximummal ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), ahol a 0 minimumú külső kvantorhoz legfeljebb 1-es gyermekminimum is kell (az (A{2,})* megmarad, mivel az A* egyetlen sort is elfogadna). Egy olyan csoport-gyermeknek, amelynek saját kvantora nem pontos, előbb rögzített hosszúságú törzzsel kell rendelkeznie, így a ((A | B B){1,2}){2} pontos külső kvantor mellett is érintetlen marad. Más kombinációk olyan hézagokat vezethetnének be, amelyeket a lapos forma elmulasztana — pl. (A{2}){2,3} csak {4, 6}-ot fogad el, de egy naiv A{4,6} az 5-öt is elfogadná —, vagy eltolhatnák az előnyben részesített találatot (az (A{2,3}){1,2} három sort részesít előnyben, ahol az A{2,6} négyet vesz fel), így az optimalizáló ezeket érintetlenül hagyja. Nem ez az egyetlen feltételhez kötött átírás: a csoportegyesítés és az utótag-egyesítés olyan törzset kíván, amely rögzített számú sort fogyaszt, az előtag-egyesítés elutasítja a 0 minimumú, véges maximumú és nullázható tartalmú csoportot, a vonakodó csomópontok sem egyesítésre, sem szorzásra nem kerülnek (az (A+?)+ megmarad), és elmarad az az átírás, amelynek új korlátja túlcsordulna.

Elem alakja

A lapos tömb minden eleme a minta egyetlen pozícióját képviseli. Hat logikai fajta létezik: a változóhivatkozás (az egyetlen, amely sort fogyaszt); a csoportkezdet és csoportvég jelölők, amelyek megnyitnak és lezárnak egy zárójelezett részmintát; az alternációjelölő, amely ágak listáját vezeti; az egyes ágakat lezáró ágelválasztó; és a befejezőjelölő a minta végén.

Minden elem hordoz továbbá egy mélységet (csoport-beágyazási szintje), a kvantort (min. és max. ismétlésszám, esetleg végtelen) és két átmenetmutatót — next, „hová menjen az elem fogyasztása után”, és jump, „hová ugorjon át” (az alternációjelölő és az ágelválasztók az ágak láncolásához használják, a csoportkezdet a saját csoportvégének megnevezéséhez — a nullát megengedő kvantorú csoport e vég next-jén keresztül kerül átugrásra —, a csoportvég pedig a testbe való visszahurkoláshoz).

A PATTERN ((A B)+) esetén a fordított tömb így néz ki:

PATTERN ((A B)+) így fordul:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 3
    (csoportot nyit; a jump
     a saját END-jét nevezi meg)

[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
    (csoportot zár; jump visszahurkol)

[4] FIN    minta kész

A minta balról jobbra olvasható a next-en keresztül, a jump kezeli a nem lineáris éleket. A 3. indexnél az END jump-ja az 1. indexre mutat vissza, így hurkol a korlátlan külső kvantor; a 0. indexnél a BEGIN jump-ja a 3. indexen lévő END-jét nevezi meg, és ha a csoport opcionális volna, az átugrás ennek az END-nek a next-jén keresztül a 4. indexre vezetne, anélkül hogy az END-re megérkezne. A futtatónak soha nem kell futási időben gráfot építenie — egyszerűen e két mutatót követi a tömb bejárása közben.

Elemenkénti attribútumok

Az alakon túl minden elem öt logikai attribútumot hordoz, amelyek az adott pozíción a futtató viselkedését irányítják:

Vonakodó
Megfordítja a kvantor-kifejtés sorrendjét. A mohó kvantorok először „hurkolj újra”, majd „lépj ki” sorrendet próbálnak; a vonakodók először a „lépj ki”-t. A+? esetén a változó hordozza; ((…)+?) esetén a csoport BEGIN- és END-elemei hordozzák.
Üresen hurkolható
Olyan csoportvégekre van beállítva, amelyek teste nullázható ((A? B?)+, (A | B*)+; az (A?)* előbb A*-gá szorzódik, és nem hagy csoportvéget). Azt mondja a futtatónak, hogy a min alatti normál visszahurkolás mellé állítson be egy gyors-előre kilépést is, hogy a ciklusőr ne öljön meg jogos találatokat olyan csoportokban, amelyek üres iterációkat is termelhetnek.
Üreset előnyben részesítő
Olyan csoportvégekre van beállítva, amelyek teste az üres találatot részesíti előnyben, mint az (A?? B??){2}-ben. A gyors-előre kilépést a min alatti visszahurkolás elé sorolja, ahol a csoport saját mohósága semmit nem mond.
Abszorbeálható régióban
Megjelöli azokat az elemeket, amelyek egy abszorpciós régión belül helyezkednek el — a futtató ezzel követi, hogy az aktuális állapot biztonságos területen van-e.
Abszorpció-összehasonlítási pont
Megjelöli azt a konkrét elemet, ahol az abszorpciós összehasonlítások futnak. Egyszerű A+ esetén a változóra esik; egy korlátlan (A B)+ csoport esetén kizárólag a csoport végére.

A „régióban” és „összehasonlítási pont” megkülönböztetése azért fontos, mert az abszorpciónak csak az iterációzárás helyein van értelme. A (A B)+ testében a futtató iteráció közben van, és a számláló még nem érte el az adott körre vonatkozó végleges értékét; itt összehasonlítani összehasonlíthatatlan értékeket jelentene. Az állapotnak el kell érnie a csoport végét, mielőtt a futtató dönthet. Az első attribútum tehát azt mondja: „még abszorbeálható területen vagy”; a második azt: „elérted az összehasonlítási pontot — most ellenőrizz”.

Abszorbeálhatósági elemzés

A kompiláció 6. lépése adja a §2.5 „azonos sors” szabályának fordítási idejű tanúját. A döntés rétegzett:

isAbsorbable(query):
  if SKIP mode != SKIP PAST LAST ROW
      → return false
  if frame end != UNBOUNDED FOLLOWING
      → return false
  if any DEFINE depends on match_start
      → return false
  a lapos tömb bejárása a 0.
  elemtől, és olyan elemek megjelölése,
  amelyek egy strukturális esetet kielégítenek

Az első három ellenőrzés lekérdezésszintű: pontosan a §2.7 (kimeneti oldal: SKIP-mód), a korlátozott keret (a határ megtöri a monotonitást) és a §2.6 (adatoldal: FIRST vagy eltolásos LAST a DEFINE-ban) feltételeinek felelnek meg. Ha bármelyik elbukik, az elemzés nem állít be jelzőket, és az abszorpció lekérdezésszinten letiltott. Ha mind átmegy, a bejárás négy strukturális alakot fogad el:

1. eset — Egyszerű korlátlan változó
A+, A*, A{2,∞}
Minden iteráció pontosan egy sor. Egy korábbi kontextus számlálója minden közös pozíción mindig ≥ egy későbbié.
2. eset — Fix hosszúságú csoport, korlátlan külső
(A B)+, (A B{2})+, ((A (B C){2}){2})+
Minden gyermeknek min == max, így a test szemantikailag egyenértékű a kifejtett {1,1} formájával — az (A B{2})+ úgy viselkedik, mint az (A B B)+. Minden iteráció rögzített számú sort fogyaszt; a számláló-dominancia fennáll.
3. eset — Olyan csoport, amelynek teste korlátlan változóval kezdődik
(A+ B)+, (A+ B){2}
A vezető korlátlan változó maga is abszorbeálható (1. eset), és pajzsként szolgál a korábbi kontextusoknak. Az abszorpció megáll, amint az állapot túllép az A-n — a test többi részére nincs monotonitási garancia, így az A mindkét jelzőt megkapja, a befoglaló BEGIN a régión belüli jelzőt kapja, a B és az END pedig egyiket sem.
4. eset — Alternáció
A+ | B+, A+ | C D
Minden ágat, amelyet az elválasztólánc mentén ér el, a fenti esetek alapján önállóan ítél meg; az alternációjelölő akkor kapja meg a régión belüli jelzőt, ha bármely ág megfelel.

Az e négy alak által le nem fedett strukturális esetek éppoly tanulságosak. Az A B+ a jelenlegi szabály szerint nem abszorbeálható, mert a vezető A egy sort fogyaszt, mielőtt a korlátlan rész elkezdődne, így az egy sorral eltolt kontextusok a korlátlan testen belül eltérő pozíciókban vannak. A vonakodó kvantorokat, mint az A+?, konstrukcióból kizárjuk: az abszorpciós szabály mohó szemantikát feltételez, ahol a hosszabb találatok elnyelik a rövidebbeket, és a vonakodó illesztés ezt megfordítja.

Az eredmény elemenkénti, nem mintaszintű döntés. Egyetlen lekérdezési terv lehet abszorpcióval engedélyezett a vezető A+-ra olyan minták esetén, mint az (A+ B+ C) vagy (A+ B+)+ — utóbbi csak a 3. eset alkalmazva a vezető elemre —, és letiltott minden ezt követőre; a futtató minden abszorpciós vizsgálatkor egyszerűen lekérdezi az aktuális állapot elemén az összehasonlítási pont attribútumot. Amint egy állapot nem abszorbeálható régióba lép, az abszorpció arra az állapotra véglegesen ki van kapcsolva — pontosan ez kell, hogy a §2.5 és §2.6 igaz legyen az algoritmus szintjén.

3.3 Navigáció — az 1-slotos tuple-csere

A DEFINE-kifejezések közönséges SQL-kifejezések, amelyeket egy sor ellen értékelnek ki, de tartalmazhatnak PREV-, NEXT-, FIRST- vagy LAST-hivatkozást — olyanokat, amelyek más sorokra mutatnak. Maguk a sorok már az ablak tuplestore-jában vannak pufferelve; amit az executornak még kezelnie kell, az a tuple-slot, amelyből az SQL-kifejezésgépezet olvas, mivel a kifejezésen belüli oszlophivatkozások tervezési időben slothez kötöttek. Az implementáció minden navigációs híváshoz egyetlen navigációs slotot használ újra: a slotot a belső kifejezés kiértékelése előtt cseréljük be, és utána visszaállítjuk, így az SQL-kifejezésgépezet többi része mit sem észlel a különbségből.

Az executor által látott modell kicsi: van egy aktuális sor slot, amely azt a sort tartja, amely ellen a DEFINE-kifejezést kiértékeljük, és egy navigációs slot, amelyet a futtató ideiglenesen másik sorra irányíthat át. Bármely navigációs hívás körül a futtató beállítja a navigációs slotot, kiértékeli a belső kifejezést, mintha az az aktuális sort olvasná, majd visszaállítja az eredeti sort. Pszeudokód:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos kívül esik az érvényes tartományán:
      return NULL

  current_row_slot mentése
  if targetPos != currentPos:
      row lekérése targetPos-on
        nav_slot-ba
      külső slot nav_slot-ra irányítása
  result = eval_inner_expression()
  current_row_slot visszaállítása
  by-ref result kimásolása nav_slot-ból
  return result

A trükk az, hogy pontosan egy slot van menteni és visszaállítani. A belső kifejezés — bármi legyen is, beleértve az aritmetikát, függvényhívásokat vagy más oszlophivatkozásokat — a felcserélt slot ellen fut, ugyanazon a kiértékelési úton, mint az aktuális sornál. Nincs alternatív kiértékelő és hivatkozásonkénti slot; ha a cél az aktuális sor, a lekérés és a csere teljesen elmarad. A lekérés a célsort a navigációs slotba másolja (hacsak a slot már nem azt tartja), a visszaállítási lépés pedig a hivatkozással átadott eredményt tuple-onkénti memóriába másolja, hogy a következő lekérés ne szabadíthassa fel.

Az összetett navigáció parse időben kilapított, így a csere továbbra is egyszer történik. A PREV(FIRST(price)) kétlépéses navigációként ismerhető fel — „menj az első illesztett sorra, majd lépj egy sorral korábbra” — és egyetlen navigációs hívásként tárolt összetett fajtával. A futtató két szakaszban számolja ki a célpozíciót, de csak egy slot-cserét végez a végső sor lekéréséhez:

compute_target_position(call):

  # aktuális sorhoz viszonyított
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # találathoz viszonyított
  FIRST(n):
      return matchStart + n
  LAST(n):
      return currentPos − n

  # összetett: találathoz visz., majd lépés
  PREV(FIRST(n), m):
      return (matchStart + n) − m
  NEXT(FIRST(n), m):
      return (matchStart + n) + m
  PREV(LAST(n), m):
      return (currentPos − n) − m
  NEXT(LAST(n), m):
      return (currentPos − n) + m

  validáljuk a megfelelő tartomány ellen
  (találattartomány a FIRST/LAST belsőre,
   partíciótartomány a külső lépésre)

Egy pozíciógyorsítótár rövidre zárja a tuplestore-lekérést, ha ugyanazon DEFINE több navigációs hívása ugyanazt a sort célozza — gyakori az olyan kifejezéseknél, mint a price > PREV(price) AND volume > PREV(volume), ahol mindkét hívás az előző sort oldja fel. A gyorsítótár csak az „utoljára lekért pozíciót” tárolja, és maga a csere egyetlen művelet marad.

A navigációs hívások osztályozása a tervező hozzájárulása az abszorpciós döntéshez. A tervező végigjárja minden DEFINE-kifejezést, és minden változót egyikbe sorol a két vödör közül, aszerint hogy minden kontextus ugyanazt a Boole-értéket számolja-e ugyanazon a soron, vagy mindegyik a sajátját. A vödör futási időben két dolgot határoz meg: milyen gyakran értékelődik ki a változó (egyszer megosztva, vagy érintett kontextusonként egyszer — §3.5 1. fázis), és hogy egyáltalán lehetséges-e kontextusabszorpció (§2.5 vs §2.6): egyetlen találatkezdet-függő változó a teljes mintára letiltja.

Megosztott kiértékelés · abszorpcióra biztonságos Minden kontextus ugyanazt a Boole-értéket látja minden soron — azonos sors (§2.5).
  • Nincs navigáció
  • Csak PREV / NEXT
  • LAST eltolás nélkül
  • Összetett, belső LAST-tal (eltolás nélkül)
Kontextusonkénti kiértékelés · abszorpcióra biztonságtalan Az eltérő találatkezdetű kontextusok eltérő válaszokat számolnak — eltérő sorsok (§2.6).
  • LAST eltolással
  • FIRST (bármely forma)
  • Összetett, belső FIRST-tel
  • Összetett, belső LAST-tal (eltolással)

Az osztályozás tervezési időben történik, és minden DEFINE-változó mellé tárolt, így a futtató semmi időt nem tölt döntéssel — egyszerűen lekérdezi a változó vödrét, miközben a sort feldolgozza.

Megőrzési költségvetés

A navigáció olyan sorokba nyúl bele, amelyeken az ablakfüggvény-gépezet egyébként már túlhaladt. Hogy ezek a sorok elérhetőek maradjanak, az executor egy tuplestore tetejére épül, amely a friss sorok csúszó ablakát tartja meg; a kérdés az, milyen szélesnek kell ennek lennie. Az executor két egymást kiegészítő eltolásból számolja ki, minden eltolást scanenként egyszer feloldva (a konstansokat az executor inicializálásakor is, hogy a sima EXPLAIN megjeleníthesse őket):

Visszatekintési költségvetés
Mennyire visszafelé érhetne bármely DEFINE-hívás az aktuális sortól.
Hozzájárulók: PREV, LAST (bármilyen eltolással, beleértve az alapértelmezett 0-t is), PREV(LAST(...)), NEXT(LAST(...))
Kezdettől előretekintési költségvetés
A legkisebb előre irányuló elérés (negatív esetben hátra) a legidősebb élő kontextus találatkezdetétől — a legkorábbi sor, amelyre bármely DEFINE-hívásnak szüksége lehet.
Hozzájárulók: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

Futási időben a tuplestore vágási jelét a két pozíció közül a korábbira állítjuk be — az aktuális sor mínusz a visszatekintési költségvetés, illetve a legidősebb élő kontextus találatkezdete plusz az előretekintési költségvetés. Az e jel előtt lévőket egyetlen élő kontextus egyetlen navigációs hívása sem érheti el, és a tuplestore eldobhatja őket. Az EXPLAIN által jelentett Nav Mark sorok (§3.7) — Lookback és Lookahead — ez a két költségvetés, nem mért csúcsok. Mindegyik csak akkor jelenik meg, ha valamilyen navigáció táplálja, és ANALYZE nélkül is látható; egy olyan eltolás, amelynek értéke csak futási időben ismert (például egy generic plan paramétere), sima EXPLAIN alatt runtime-ként, EXPLAIN ANALYZE alatt pedig feloldott értékével jelenik meg, a retain all (Lookback) vagy az infinite (Lookahead) pedig túlcsorduló eltolást jelöl.

3.4 Találat-határok — SKIP, INITIAL és korlátozott keret

A találat eredményét két értékként rögzítjük: a sor, amelynél a találat kezdődik, és a hossza. A negatív kezdet azt jelenti, hogy a pozíciót még nem értékelték ki; ha a kezdet be van állítva, a későbbi, executor felé intézett kérdések — „benne van-e ez a sor egy találatban?” — O(1)-ben válaszolhatók a pár vizsgálatával. A hossz kódolja a kimenetet: -1 az illeszkedés nélküli sorra, 0 az üres találatra, és a sorok száma valódi találatra. A nulla hossz valós kimenet, nem hiba: olyan mintát képvisel, amely sor fogyasztása nélkül illeszkedett, amit az executornak meg kell különböztetnie mind az illeszkedés nélküli sortól, mind attól, hogy „erre a pozícióra még nem történt találat-kísérlet”.

Az AFTER MATCH SKIP záradék dönti el, hol kezdődik a következő találat-kísérlet. Az AFTER MATCH SKIP PAST LAST ROW a találat vége utáni sorra lép, a legtöbb lekérdezés által óhajtott nem átfedő kimenetet előállítva, és lehetővé téve az abszorpciós optimalizációt.

Az AFTER MATCH SKIP TO NEXT ROW csak a találat kezdete utáni sorra lép, átfedő találatokat engedélyezve; a tervező ezért az adott ablak mintájára letiltja az abszorpciót, ha ez a mód érvényes.

A szabvány által szintén definiált két ugrási cél — AFTER MATCH SKIP TO FIRST változó és AFTER MATCH SKIP TO LAST változó — találatonkénti előzménytől függnek, amelyet ez a javítás nem tart meg. Nem szerepelnek egyáltalán a nyelvtanban, így a parser általános szintaktikai hibát vet, ha bármelyiket megadják.

Ugyanez igaz a SEEK-re is, amely a specifikációban az INITIAL alternatívája. SEEK alatt egy R sortól induló találat-kísérlet R-től a keret végéig bármely soron sikerülhet, nem csak magán R-en. A javítás csak az INITIAL-t valósítja meg: minden potenciális találat egy konkrét sorhoz horgonyzott. A parser hibát vet, ha SEEK-et kérnek. A korlátozott keretek külön kezelést kapnak — amikor a felhasználó ROWS BETWEEN CURRENT ROW AND N FOLLOWING-ot ír UNBOUNDED FOLLOWING helyett, az executor minden olyan kontextust rövidre zár, amelynek találata elérte a határt, kényszerített eltérés révén, és az abszorpció letiltott, mert a határ megtöri az abszorpció alapját képező monotonitási feltételezést.

3.5 A háromfázisú soronkénti motor

Az executor soronkénti meghajtóját a környező ablakfüggvény-gépezet hívja meg, valahányszor tudnia kell, hogy egy adott sor egy illesztett keretbe tartozik-e. A meghajtó megkeresi vagy létrehozza az aktuális kezdőpozícióhoz tartozó kontextust, majd soronként előre hajtja az NFA-t — minden sornál „kiértékeletlen” állapotba állítva vissza egy változónkénti illeszkedési tömböt —, amíg abban a kontextusban nem marad élő állapot, vagy a partíció véget nem ér. A DEFINE-predikátumok kiértékelése lusta: egy változó akkor értékelődik ki, amikor egy állapot először fogyasztja, így az a változó, amelyet ezen a soron egyetlen élő állapot sem tesztel, soha nem értékelődik ki. Maga az előrelépés három fázis fix sorrendben — Match, Absorb, Advance — ugyanabba a külső ciklusba burkolva:

processRow(currentPos):

  # 1. fázis — MATCH (konvergencia)
  for each context:
      if context elérte a keretvégét:
          eltérés kényszerítése (korai véglegesítés)
          continue
      if matchStartRow eltér a megosztott
         kiértékelési pozíciótól:
          a találatkezdet-függő DEFINE-
          változók kiértékeletlenre állítása (§3.3)
      match(context, varMatched)

  # 2. fázis — ABSORB
  if pattern is absorbable:
      kontextusonként jelzők frissítése
      absorb_contexts()

  # 3. fázis — ADVANCE (divergencia)
  for each context:
      advance(context, currentPos)
      if találatot rögzített és
         SKIP PAST LAST ROW:
          a találaton belül induló
          későbbi kontextusok metszése

A sorrend nem stiláris döntés. A Match-nek kell elsőként futnia, mert az abszorpció match utáni számlálókat hasonlít össze; Absorb futtatása Match előtt olyan állapotokat hasonlítana, amelyek éppen meghalni készülnek. Az Advance-nek kell utolsónak futnia, mert ez az egyetlen fázis, amely új állapotokat hoz létre — minden túlélő állapotot epszilon-átmeneteken át kibont, amíg mindegyik el nem ér egy következő sorra váró változót. Az Absorb futtatása az Advance után divergált utódok összehasonlítását jelentené, elszalasztva azt a pontot, ahol az állapotok a legtisztábban összehasonlíthatók.

1. fázis — Match

A Match „konvergencia” fázis: az állapotok vagy túlélnek megnövelt számlálóval, vagy meghalnak. Egy finom pont: az abszorbeálható régióban ülő változókra a Match egy kis előrehaladást is végez, hogy az Absorb tisztán hasonlíthasson. A lefedettségi feltétel csak az abszorbeálható összehasonlítási ponton sül el — a korlátlan csoport END-jén —, így azokat az állapotokat, amelyek éppen iteráció közbeni változókra (mint a B az (A B)+-on belül) illeszkedtek, magán a Match-en belül kell felvinni az összehasonlítási pontig; máskülönben az Absorb semmit nem talál összehasonlításra alkalmasként, és az optimalizáció soha nem lép működésbe.

match(context, varMatched):
  for each state in context:
      elem = pattern[state.elemIdx]
      assert elem változó
          # az advance csak változókon parkol

      if varMatched[elem.varId]
         kiértékeletlen:
          DEFINE-jának kiértékelése most
      if not varMatched[elem.varId]:
          állapot eldobása   # halott ág
          continue

      state.counts[elem.depth] += 1

      # Inline előrehaladás, hogy a
      # következő fázis az összehasonlítási
      # pont elemén hasonlíthasson, ne
      # iteráció közben.
      if elem in-region, de nem
         az összehasonlítási pont,
         és elérte a max. számlálót,
         és elem.next csoportvég:

          END-lánc bejárása:
            külső csoport számláló növelése
            state.elemIdx léptetése END-re
            folytatás, amíg még in-region,
              must-exit, és next END
          (megáll az összehasonlítási ponton
           vagy egy még hurkolható elemen)

Az END-lánc bejárása teszi az ágyazott fix hosszúságú csoportokat abszorbeálhatóvá. A ((A B){2})+-ben, amikor a B eléri a maximumát (a B {1,1}), a belső csoport számlálóját növelni kell; ha az is eléri a maximumát — lezárva a belső {2}-t —, a külső csoport számlálóját is növelni kell, és így tovább, amíg az állapot a legkülső abszorpciós pontra nem érkezik — a korlátlan külső csoport (a +) END-jére. E munka Match-ben végrehajtása lehetővé teszi, hogy az Absorb olyan kontextusokkal hasonlítson össze, amelyek már konszolidálták az iteráció utáni számlálóikat.

2. fázis — Absorb

Az Absorb-fázis a kontextusokat a legújabbtól (farok) a legidősebbig (fej) járja be. Minden olyan, folyamatban lévő kontextusra, amely teljesen abszorbeálható, visszafelé keres egy idősebb folyamatban lévő kontextust, amely lefedi, és felszabadítja az újabbat, ha talál ilyet. Mivel a kontextusokat létrehozási sorrendben tartjuk, és minden sor legfeljebb egy kontextust hoz létre, az „újabb” és az „idősebb” valóban „később indultat” és „korábban indultat” jelent.

absorb_contexts():
  for ctx from tail backward:
      if ctx befejezett
         vagy bármely nem abszorbeálható állapotot tartalmaz
         vagy rögzített találatot tart:
          skip
      for older from ctx.prev backward:
          if older befejezett
             vagy nincs abszorbeálható állapota:
              skip
          if covered(older, ctx):
              free(ctx)
              abszorpciós hossz rögzítése
              break

covered(older, newer):
  for each state in newer:
      elem = pattern[state.elemIdx]
      if elem nem az összehasonlítási pont:
          return false
      if nincs olyan állapot older-ben:
            azonos elemIdx-szel
            és isAbsorbable-lal
            és older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Ebből két mikro-döntés következik. Az első, hogy a fedési ellenőrzés azonnal elutasít, ha az újabb kontextus bármely állapota nem összehasonlítási ponton áll — nem ítéleti pontokon történő összehasonlítás nem lenne értelmes.

A második a kontextusonkénti aszimmetrikus jelzőpár: a has-absorbable-state arra válaszol, hogy „abszorbeálhatna-e ez a kontextus egy újabbat?”, és monoton (csak true→false irányba mehet, ahogy az állapotok meghalnak); az all-states-absorbable arra válaszol, hogy „abszorbeálható-e ez a kontextus?”, és dinamikus (visszavált true-ra, amikor egy nem abszorbeálható állapotot eltávolítunk), amíg a kontextus nem rögzít találatot, ami false-ra rögzíti — az abszorbeálás olyan találatot szabadítana fel, amelyet egyetlen abszorbeáló kontextus sem tud reprodukálni. Mindkét jelzőt konstans időben ellenőrizzük, még mielőtt a fedési pásztázás elindulna, így az abszorpció a teljes költségét csak olyan kontextusokon fizeti meg, amelyeknek valós esélyük van abszorbeálódni.

3. fázis — Advance

Az Advance a „divergencia” fázis: minden túlélő állapotot epszilon-átmeneteken át kibontunk, amíg minden ág el nem ér egy következő sorra váró változót vagy a FIN-őrt. A kibontás mélységi, és a testvérágak bejárási sorrendje az, ami a szabvány preferenciaszabályát ténylegesen érvényre juttatja — a lexikailag első ág mindig elsőként kerül hozzáadásra, és az állapotbeillesztéskori deduplikációs lépés csendben eldobja az ekvivalens későbbi hozzáadásokat.

advance(context, currentPos):
  összes aktuális állapot kihúzása;
  ctx.states újraépítése nulláról
  for each state lexikai sorrendben:
      visited bitmap törlése
      advance_state(state)   # DFS

      # Preferencia: amint egy DFS eléri a FIN-t,
      # a maradék állapotok kevésbé preferáltak
      # és eldobhatók.
      if FIN reached and states remain:
          a többi felszabadítása
          break

advance_state(state):
  bejárás state.elemIdx-en át,
  rekurzió ezeken keresztül:
    ALT-ágak (sorrendben, megállva,
              amint FIN rögzítésre került),
    BEGIN (csoportba lépés; plusz opcionális
           ugró út, ha min = 0),
    END (visszahurkolás / kilépés / fast-forward —
         lásd alább),
    FIN (matchEndRow rögzítése,
         matchedState mentése, és a
         kontextus megjelölése, hogy a jelölt
         tartományán belüli későbbi kontextusok
         metszésre kerüljenek — lásd alább),
  minden talált változónál megállva:
      állapot hozzáadása ctx.states-hez
      (deduplikáció elemIdx + counts alapján)

A FIN-t elérő állapot rögzítése többet tesz, mint csupán könyvjelzőt rak a jelölt találathoz. Az AFTER MATCH SKIP PAST LAST ROW alatt a következő közölhető találatnak szigorúan az aktuális után kell kezdődnie — így amint az Advance végzett a jelöltet rögzítő kontextussal, minden olyan későbbi kontextust, amelynek kezdősora a jelölt tartományán belülre esik, ugyanazon a soron metszünk, még akkor is, ha a FIN-t elért kontextus mohó visszaesés révén tovább kereshet hosszabb találatot.

A metszés biztonságos, mert akárhogy is végződik az a keresés (egy hosszabb találat felváltja a jelöltet, vagy a jelölt megáll), minden metszett kontextus olyan tartományon belül indult, amelyet a következő közölhető találatnak át kell ugrania, így saját kimenetet sosem termelhetnének.

Ez a kontextusok közötti FIN-időbeli metszési lépés. A kontextuson belül a FIN a lexikailag alsóbbrendű munkát is levágja: az Advance eldobja a hátralévő sorban álló állapotokat (e szakaszban korábban leírva), és egyetlen DFS-en belül minden kevésbé preferált út — a későbbi ALT-ágak, a BEGIN ugró és belépő útja közül a másik, egy vonakodó változó belépő útja, az END hurok- és kilépő útja közül a másik — megáll, amint találat rögzítésre került, így egy advance legfeljebb egy találatot rögzít.

A legbonyolultabb elemenkénti logika az END-kezelőben él. Ha a csoport iterációszáma az alsó korlát alatt van, a futtatónak vissza kell hurkolnia; ha eléri vagy meghaladja a felső korlátot, ki kell lépnie; köztük mindkét opció érvényes, és a kvantor mohósága dönti el, melyiket próbáljuk először:

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

  if count < elem.min:
      visszahurkolás a testbe
      if elem üresen hurkolható:
          # nullázható test, lásd §3.2
          klónozzunk egy fast-forward
          állapotot is, amely kilép a csoportból
          kielégített számlálóval
          (előbb fast-forward, ha a test
           az üreset részesíti előnyben; a
           második út eldobásra kerül, ha
           az első FIN-t ért el)

  elif count >= elem.max:
      számláló nullázása ezen a mélységen
      kilépés next-en át
      (END→END: külső
       END számlálójának növelése)

  else:
      # min <= count < max: elágazás
      kilépő állapot építése
      (számlálók nullázva ezen a mélységen)
      if mohó:
          először hurok
          if a hurok FIN-t ért el:
              kilépés eldobása
              # hosszabbat előnyben
          else másodszor kilépés
      else (vonakodó):
          először kilépés
          if a kilépés FIN-t ért el:
              hurok eldobása
              # rövidebbet előnyben
          else másodszor hurok

Minden, kontextushoz hozzáadott állapot átmegy egy deduplikációs ellenőrzésen, amely a pozícióját és számlálóit a meglévő állapotlistával hasonlítja össze. Mivel az Advance az ágakat DFS-sorrendben dolgozza fel, bármely alternáció első ágából származó állapot kerül be elsőként — és bármely ugyanazt a pozíciót és számlálókat termelő későbbi ág beillesztéskor elutasításra kerül. Pontosan ezt kéri a §2.4 lexikai-sorrend szabálya, a futtató mélyén megvalósítva, külön áthaladás nélkül.

Üresen hurkolható csoportok

Egy finom eset, amelyet a futtatónak hatástalanítania kell, a nullázható csoport — olyan csoport, amelynek teste nulla sorra is illeszkedhet, mert a test minden gyermeke maga is opcionális. Az olyan minták, mint az (A? B?)+ és az (A | B*)+, ezzel a tulajdonsággal rendelkeznek: az adatoktól függően a test úgy fejezhet be egy iterációt, hogy egyetlen sort sem fogyasztott el. (Egyetlen opcionális gyermek, mint az (A?)*, fordítási időben A*-gá íródik át, és nem hagy maga után csoportot.) Ez elvben rendben van, de valós veszélyt jelent az NFA epszilon-kibontásának. Ha a test üres találatot termel, az END-elem visszahurkol a testbe (a jump-ja a csoport első gyermeke), a test ismét üres találatot termel, újra eléri az END-et, és így tovább. Valami megállító nélkül az Advance DFS-e sosem terminálna.

Az őrt fordítási időben döntjük el, és futási időben hajtjuk végre. Valahányszor a tervező nullázható testű csoportot lát, az adott csoport END-elemét üresen hurkolhatónak jelöli. A futtató egy felkeresési bitmapet tart fenn, amelyet minden állapot DFS-kibontása előtt töröl, és amelyben csak ezek a megjelölt END-ek kerülnek bejelölésre — semmi más nem tud ciklusba kerülni, mert minden más visszahurkolás sort fogyasztott. Egy bejelölt END elérése azt jelenti, hogy a test épp üres iterációt vezetett le, és az állapot nem kerül eldobásra: az alsó korlátnál vagy fölötte ott kilép a csoportból (egy üres iteráció leállítja a kvantort), alatta pedig a normál visszahurkolásra esik át, így minden üres érkezés tovább növeli a számlálót, amíg az el nem éri a min-t. Vegyük az (A? B?){2,3}-at, ahol egyik változó sem illeszkedik sehol a sorfolyamban:

iter 1: A? B? nulla sorra illeszkedik
        → END, count = 1 (min alatt)
        END már bejelölve (csoportba
        lépéskor), de min alatt:
        → visszahurkolás A?-ba
iter 2: A? B? nulla sorra illeszkedik
        → END, count = 2 (eléri a min-t)
        END már bejelölve, min-nél:
        → kilépés a csoportból
kilépés nulla hosszú találattal

Az alsó korlát alatt az üres-hurok jelölés azt is mondja az END-kezelőnek, hogy a normál visszahurkolási út mellé klónozzon egy további fast-forward állapotot is:

advance_end (count a min alatt):

  visszahurkolási út:
    visszahurkolás a testbe
    (nyitva tartja az ajtót egy valódi,
     nem üres találat előtt a következő
     iterációban)

  if elem üresen hurkolható:
    fast-forward út:
      e mélység számlálójának nullázása
      kilépés a csoportból next-en át,
      a hátralévő kötelező iterációkat
      üres találatként kezelve

A két út egymást kiegészítő szerepet játszik. A visszahurkolás azt az esetet kapja el, amikor a testnek később még valódi találatai lesznek — például az (A? B?){2,3} után olyan adatban, ahol az A csak későbbi sorokon illeszkedik, a visszahurkolás engedi a második és harmadik iterációnak nem üres találatot találni. A fast-forward azonnal kilép a csoportból, kijelentve, hogy „a hátralévő kötelező iterációk üresek”, és engedi a találatot nulla hosszú testtel sikerülni. A sorrendet a test dönti el, nem a csoport saját mohósága: a fast-forward pontosan akkor kerül előre, ha a test az üres találatot részesíti előnyben (vonakodó test, mint az (A?? B??)), és ha az első út eléri a FIN-t, a második eldobásra kerül, így egy kevésbé preferált út nem válthatja fel a preferált találatot. A beillesztéskori deduplikációs ellenőrzés megakadályozza, hogy bármelyik út a részén túl több állapotot szüljön.

A ciklusőrön túl egy további indítási trükk egyértelműsíti a kontextus legelején a nulla-soros kimeneteleket. A kontextus-létrehozási lépés minden potenciális kezdősornál egy kezdeti advance-et futtat epszilon-átmeneteken át mielőtt bármely sort fogyasztanánk, a tényleges kezdetnél egy sorral korábbi pozíciót használva. Bármely olyan út, amely kizárólag epszilon-átmeneteken át eléri a FIN-őrt — sor fogyasztása nélkül —, ezért a kezdetnél kisebb végpozíciót termel; ez a negatív-szakasz koordináta, kombinálva azzal, hogy a FIN ténylegesen elérődött-e, kódolja az üres találat (nulla hosszú találat elfogadva) és egy nem illesztett kezdet közötti különbséget, anélkül hogy külön jelzőre lenne szükség.

3.6 Hogyan marad korlátos az állapottér

A futtató korlátos tartása nem egyetlen optimalizáció eredménye. Egy rétegzett metszési szabályhalmaz kumulatív hatása, amelyek mindegyike más-más állapottér-növekedési okot kap el a soronkénti ciklus más-más pontján. Egyeseket fordítási időben döntünk el, és futási időben csupán lekérdezzük; mások dinamikusan sülnek el. Egyesek egyedi állapotokat ölnek; mások egész kontextusokat. A fenti szakaszok mindegyiket kontextusban vezették be; az alábbi táblázat egy oldalra teszi őket.

Sikertelen predikátum Match
Olyan változó-állapotok, amelyek DEFINE-ja az aktuális soron hamisra értékelődött — halott ágak.
Inline END-lánc előrehaladás Match
Olyan változók, amelyek elérték a max. számlálójukat, és egyébként iteráció közben hagynák el az állapotot; fix hosszúságú csoportvégeken át léptetve, hogy az abszorpció a megfelelő ponton hasonlíthasson.
Kontextusabszorpció Absorb
Olyan újabb kontextusok, amelyek minden állapota összehasonlítási ponton ül, és egy idősebb kontextusnak ugyanazon az elemen lévő, nagyobb vagy egyenlő számlálójú abszorbeálható állapota lefedi — fogalmi szabály a §2.5-ben, fordítási idejű alkalmasság a §3.2-ben, páronkénti ellenőrzés a §3.5-ben.
Állapot-deduplikáció Advance
Különböző DFS-ágakon át elért állapotok, amelyek ugyanazon pozícióba és számlálókkal érkeznek — csak az első (lexikailag legkorábbi) marad; a későbbi ekvivalenseket csendben eldobjuk, így érvényesül a preferencia is (§2.4).
FIN korai befejezés (kontextuson belül) Advance
Olyan állapotok, amelyek még a DFS-sorban vannak, amikor egy ág eléri a FIN-t — lexikai sorrend szerint minden hátralévő állapot kevésbé preferált, és azonnal eldobható.
Jelölt-találat metszés (kontextusok között) Advance
Más kontextusok, amelyek kezdősora a jelölt találat tartományán belülre esik — a FIN-t elért kontextus mohó visszaeséssel tovább kereshet hosszabb találatot, de AFTER MATCH SKIP PAST LAST ROW alatt a jelölt tartományán belüli kontextusok többé nem termelhetnek közölhető kimenetet, függetlenül attól, hogyan végződik a keresés, és metszésre kerülnek, amint az Advance végzett a jelöltet rögzítő kontextussal.
Ciklusőr Advance
Epszilon-kibontások, amelyek ugyanazon DFS-en belül egy már bejelölt nullázható csoport END-jét érik el (bejelölve a BEGIN-en át történő belépéskor vagy egy korábbi érkezéskor) — egyébként örökké hurkolnának; az állapot az alsó korlátnál vagy fölötte ott kilép a csoportból, alatta pedig tovább hurkol.
Üres-hurok fast-forward Advance
Egy nullázható csoport alsó korlátja alatt egy további út, amely kilép a csoportból, a hátralévő kötelező iterációkat üresként deklarálva, és amelyet a test preferenciája sorol a visszahurkoláshoz képest.
Korlátozott keret levágás Match
Olyan kontextusok, amelyek találata elérte a felhasználó által megadott keret felső korlátját — eltérés kényszerítve, hogy ne nyúljanak túl rajta (§3.4).

A bejegyzések fázisjelvény szerinti olvasása a kontextus életciklusát követi: a metszés minden sornál elsül a három fő fázison (Match, Absorb, Advance) át. A leírások alapján olvasva a szabályok aszerint csoportosulnak, mit céloznak: halott ágak, redundáns kontextusok, ekvivalens állapotok, végtelen ciklusok és felhasználó által szabott határokon való túlnyúlás.

Egyetlen szabály önmagában nem volna elég. Az üres-hurok fast-forward önmagában nem állítaná meg a végtelen epszilon-hurkokat; az abszorpció önmagában túlságosan összevonná a kontextusokat, amikor a DEFINE a találatkezdetre hivatkozik; a deduplikáció önmagában nem szüntetné meg a redundáns kontextusokat, csak a redundáns állapotokat. A futtató a fontos esetekben — PATTERN (A+ B+ C+ D) 100 000 soron, a poszter ③ paneljének benchmarkja — azért marad lineáris, mert minden réteg elkapja, amit a fölötte lévő rétegek elszalasztanak. A forráskód dokumentál olyan eseteket, amelyeket a rétegek nem kapnak el: a deduplikáció megtartja azokat az állapotokat, amelyek csak a min fölötti számlálókban különböznek, így a soha nem igaz C-vel futó (A{2,} B)+ C csúcson Θ(n²) állapotot tart, és Θ(n³)-at hoz létre (37 s 320 soron), egy csupa nullázható alternációkból álló sorozat pedig útról útra kerül felsorolásra, így az (A?|B?){30} több mint fél óráig tart.

3.7 EXPLAIN-kimenet

Az EXPLAIN ANALYZE egy RPR-t használó lekérdezésen NFA-szintű statisztikákat hoz felszínre, amelyek a hagyományos ablakfüggvényeknél nincsenek jelen. Szöveges formátumban az ablakoperátor mellett kerülnek kibocsátásra, a Pattern: sor, az esetleges Nav Mark sorok (amelyeket a sima EXPLAIN is megjelenít) és a Storage: sor után:

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (mindegyik csak akkor, ha a DEFINE
   őt tápláló navigációt használ)
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)
  (a második NFA-sor csak akkor, ha
   bármelyik szám nem nulla; a nulla
   szám (len ...) nélkül jelenik meg)

A nem szöveges formátumok minden számot külön tulajdonságként bocsátanak ki. A peak és a total a futtató közvetlen műszerezése: hány állapot volt valaha egyidejűleg élő, hány jött létre a lekérdezés élettartama alatt, és hányat olvasztott össze a deduplikáció; a pruned az egyetlen sor után elbukott kontextusokat számolja. A találathossz-hisztogramok négy kimenetelt különítenek el — sikeres találatok, egynél több sor után elbukott találat-kísérletek (mismatched), abszorbeált kontextusok, és azok a kontextusok, amelyeket az AFTER MATCH SKIP PAST LAST ROW felszabadított, mert egy rögzített találaton belül indultak (skipped) —, és min/max/átl. közlése egy pillantással láthatóvá teszi a teljesítmény-patológiákat: egy egészséges futás a kontextusok többségét vagy matched, vagy absorbed kategóriában mutatja, kis mismatched hosszakkal.

A két Nav Mark számláló a tuplestore-megőrzési költségvetést jelenti, amelyet a §3.3 a DEFINE-ból származtat. A Lookback a legmélyebb visszafelé elérés az aktuális sortól a PREV, a bármilyen eltolású (beleértve az alapértelmezett 0-t is) LAST és a belső LAST-os összetett formák között; a Lookahead a legkisebb előre irányuló elérés (negatív, ha a találatkezdet elé néz), a legidősebb élő kontextus találatkezdetétől mérve, amelyhez a FIRST és a belső FIRST-tel rendelkező összetett formák járulnak hozzá.

Mindegyik számláló rögzített egész számként jelenik meg, ha az eltolás konstans, „runtime”-ként, ha az eltolás nem konstans, csak scanenként ismert kifejezés, és — csak a Lookback esetén — „retain all”-ként, ha az eltolás túlcsordul; a túlcsorduló Lookahead „infinite”-ként jelenik meg. Minden sor csak akkor kerül kibocsátásra, ha a DEFINE valamely navigációja táplálja, és mindkettő a sima EXPLAIN alatt is megjelenik: a konstans eltolások az executor inicializálásakor rögzülnek, míg a csak futási időben ismert eltolás (például egy generic plan paramétere) ott „runtime”-ként, az EXPLAIN ANALYZE alatt pedig feloldott egész számként jelenik meg.

Együttvéve ezek a számlálók lehetővé teszik az RPR-teljesítmény hibakeresését anélkül, hogy gdb-t kellene csatolni a backendhez.

A számlálókon túl az EXPLAIN egy Pattern: sort is kiír, amely a lefordított elemtömbből épül, így a mintát a fordítási idejű átírások utáni formájában mutatja (a PATTERN (A A) a{2}-ként jelenik meg), és hordozza a # (összehasonlítási pont) és ~ (abszorbeálható régió) abszorpciós jelölőket; a DEFINE és az AFTER MATCH SKIP opció nem jelenik meg. A záradékok leírt formában való reprodukálása, beleértve a vonakodó kvantorokat, a csoportismétlést és a skip opciót, a pg_get_viewdef() feladata, amely jelentős erőfeszítést tesz, hogy ez a kör stabil legyen, így a pg_dump és a pg_upgrade szemantikai eltolódás nélkül megőrizhesse az RPR-objektumokat — az rpr_explain alatti regressziós csomag esetenként ellenőrzi (lásd §4).

§4. Tesztek — Lefedettségi térkép

A javítás öt regressziós csomagot tartalmaz, amelyek együttesen a §3-ban leírt minden réteget gyakorolnak — durván 22 000 sornyi SQL, minden csomag más-más szempontra fókuszálva. A felosztás szándékos: a parser-szempontok, a futási helyesség, a tervező-interakciók és a kimeneti formázás külön fájlokban tartása megkönnyíti a hibák lokalizálását, és megakadályozza, hogy az egyik rétegben végzett, nem összefüggő változtatás véletlenül érvénytelenítsen egy másikban lévő teszteket. Az öt csomag:

rpr
WINDOW-záradék integráció — realisztikus ablakforgatókönyvek szintetikus tőzsdei adatokon (V-alak, W-alak, egymást követő emelkedések, fordulatok), továbbá navigációs szemantika és DEFINE-korlátozási hibák.
rpr_base
Parser-réteg — kulcsszó-elfogadás, szintaxisformák, kvantorok, navigáció-parszolás, hibaüzenetek és pg_dump/pg_upgrade kör-stabilitás; továbbá egy tervezőréteg — mintaoptimalizáció, abszorpciós jelzők, optimalizációs visszaesés, tervező-integráció.
rpr_nfa
NFA-futtató — a háromfázisú ciklus, abszorpció minden abszorbeálható alakon, és a kontextus életciklus szélső esetei.
rpr_explain
Kimeneti formázás — NFA-statisztikák, minta-deparszolás, azonosító-idézés, újratöltésen átívelő formátumstabilitás.
rpr_integration
Tervező-interakciók — őrök, amelyek megakadályozzák, hogy nem összefüggő ablakoptimalizációk megrontsák az RPR-szemantikát.

4.1 rpr — végponttól végpontig terjedő forgatókönyvek

A forgatókönyvi csomag a tesztkészlet nyilvános arca: egy körülbelül 1600 soros szintetikus tőzsdeár-adathalmazt használ, és realisztikus lekérdezéseket futtat ellene — V-alakú visszapattanás, W-alak (kettős mélypont), egymást követő emelkedések és esések, fordulati minták, többszimbólumú partíciók. Ezek a forgatókönyvek az egyetlen tesztek, ahol a bemenetek és kimenetek úgy olvashatók, mint olyan lekérdezések, amelyeket egy felhasználó valóban írhatna; a fájl többi része a többi csomaghoz hasonlóan reduktív — PREV/NEXT-beágyazás és nem konstans eltolás hibái, DEFINE-hivatkozási szabályok és navigációs eltolás-szemantika.

Mivel ezek a lekérdezések minden réteget kombinálnak (parser, tervező, executor, EXPLAIN), az rpr-ben fellépő egyetlen hiba ritkán mondja meg, hol él a hiba. A négy következő csomag a felezés: egy hibás rpr plusz egy átmenő rpr_base kizárja a parsert; plusz egy átmenő rpr_nfa a forgatókönyv-specifikus adatformákra szűkíti; plusz egy átmenő rpr_integration kizárja a tervezői interferenciát; és a deparse-eltolódás az rpr_explain-ben jelenik meg.

4.2 rpr_base — a parser felülete

Az alap csomag a legnagyobb, és ennek oka van: ezé a feladat bizonyítani, hogy a §1.2 minden legális szintaxisdarabja valóban parsolódik, a §1.3 minden illegális darabja hasznos hibával elutasításra kerül, és minden elfogadott forma túléli a szerializációs kört. Nagy része kicsi, fókuszált részletekként formált — szintaktikai jellemzőnként egy —, nem hosszú realisztikus lekérdezésekként, mivel a cél a lefedettség, nem a forgatókönyvi realizmus. Egy második rész, a tervezőréteg, lefedi a mintaoptimalizációt, az abszorpciós jelzők megjelenítését és elemzését, az optimalizációs visszaesést és a tervező-integrációt (alkérdések, joinok, halmazműveletek, rendezés és csoportosítás).

A szerializációs tesztek külön figyelmet érdemelnek. Az RPR-objektumoknak (nézetek, materializált nézetek, pg_dump-kimenet) szemantikai eltolódás nélkül kell körbemenniük a katalógus-reprezentáción át, beleértve olyan finomságokat, mint a kvantor vonakodó jelzője vagy egy összetett navigációs kifejezés pontos formája. Néhány szerializáció-specifikus objektumot (az rpr_serial_v* nézetek és az alattuk lévő táblák) szándékosan helyén hagyunk a futás végén, hogy a környező regressziós infrastruktúra felvehesse és pg_dump-pal és pg_upgrade-del gyakorolhassa őket. A teszt-állványzat többi részét a szokásos módon eldobjuk. Az olyan hibák, mint egy vonakodó jelző elvesztése deparse és újraparszolás között, csak akkor kerülnek felszínre, ha a kört végponttól végpontig gyakoroljuk.

4.3 rpr_nfa — a futtatómotor

Ez az a csomag, amely minden, a §3.5-ben és §3.6-ban leírt mechanizmust gyakorol. Tesztjei egységes mintát követnek: inline VALUES-sorok, amelyek változónevek tömbjét hordozzák, és ezzel deklarálják, mely DEFINE-változók illeszkednek az egyes sorokon, párosítva egy mintával, amely egy adott futási idejű viselkedést szondáz. A tömbös idióma elkülöníti a futtató-tesztet a DEFINE-kiértékelési gépezettől — azt teszteljük, hogy „adott, hogy ezek a változók itt illeszkednek, az NFA-ciklus a várt találat-szakaszt termeli-e?”, nem pedig azt, hogy „a DEFINE-kifejezés-kiértékelő helyesen számolja-e ezeket a Boole-okat?”. A DEFINE-kiértékelőt máshol teszteljük (rpr_base a parszolásra, rpr a végponttól végpontig terjedő viselkedésre).

Egy tipikus tesztfixtúra így néz ki — változónevek tömbjeinek oszlopa, ahol minden bejegyzés azt mondja, mely DEFINE-változók sülnek el az adott soron, és egy minta, amelynek DEFINE-záradékai közvetlenül ezekre a nevekre tesztelnek:

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

A tömb-oszlop lefelé olvasása a tesztforgatókönyv közvetlen olvasása. A 2. és 3. sor mindkét nevet hordozza — az A és a B is elsül ott, így az NFA-nak valós választása van arról, hol váltson az A-lábról a B-lábra. A várt találat (A az 1–3. sorokon, majd B a 4. soron, a szabvány mohó preferenciája szerint) önmagában ezekkel a jelzőkkel rögzített, itt semmilyen érdemleges kifejezés-kiértékelés nélkül — az = ANY csak a triviális réteg, amely az oszlopot a DEFINE számára elérhetővé teszi, nem ezt teszteljük. Ugyanezen forgatókönyv numerikus predikátummal (price > PREV(price) és hasonlók) való felírása összekuszálná az NFA-tesztet a predikátum-kiértékelő viselkedésével; a tömb-idióma tisztán szétválasztja a kettőt, és egy itteni hiba közvetlenül az NFA-ciklusra mutat.

Az abszorpciós lefedettség különösen alapos, mert az abszorpció az az optimalizáció, amely a legvalószínűbben csendben rossz választ ad, ha akkor lép működésbe, amikor nem kellene. A tesztek a §3.2 esetelemzésének minden alakját lefedik:

Az abszorpción túl a csomag a kontextus életciklusát is lefedi: átfedő kontextusok AFTER MATCH SKIP TO NEXT ROW alatt, sikertelen kontextusok takarítása menet közben, befejezetlen kontextusok partíció végi véglegesítése, és kontextusok, amelyekkel azután találkozunk, hogy a fej-kontextusban már egy jelölt találat rögzítésre került. Ezek mindegyike a §3.6 egy adott metszési szabályához kapcsolódik, és a tesztek úgy íródtak, hogy hangosan elbukjanak, ha a szabály téves jelet ad (akár redundáns kontextusokat hagy életben, akár olyat öl meg, amelynek kimenetet kellett volna termelnie).

4.4 rpr_explain — kimeneti stabilitás

Az EXPLAIN-kimenet a felhasználói szerződés része — harmadik féltől származó eszközök (monitorozási dashboardok, naplólekérdezők) parszolják, és a kozmetikainak tűnő változások eltörhetik őket. Az rpr_explain csomag három dolgot ellenőriz:

Az rpr_base-hez hasonlóan ez a csomag is szándékosan a helyén hagyja az objektumait a futás végén, hogy a pg_dump- és pg_upgrade-lefedettség az explain-oldali műtermékekre is kiterjedjen.

4.5 rpr_integration — tervező-interakciók

A PostgreSQL tervezője számos olyan optimalizációval rendelkezik, amelyek ablaklekérdezéseken működnek — keret-kanonizáció, futási feltétel lenyomása, azonos ablakok deduplikációja, használatlan kimenet projekciója, mozgóátlag-inverz átmenetek —, és mindegyiket RPR nélkül tervezték. Többségük biztonságtalan alkalmazni, ha egy ablakhoz PATTERN záradék tartozik: a keret a találati szerződés része, az illesztett kimenet semmilyen nyilvánvaló módon már nem monoton, és két ugyanazon specifikációval, de eltérő DEFINE-okkal rendelkező ablak valódi, eltérő eredményeket termel. Az integrációs csomag ellenőrzi, hogyan kezeli ezen optimalizációk mindegyike az RPR-ablakokat — többségüket le kell tiltani vagy meg kell kerülni:

Keret-kanonizáció
A tervező keretfüggetlen ablakfüggvények, mint a row_number, a rank és az ntile esetén a ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING-ot rendszerint ROWS UNBOUNDED PRECEDING-re írja át. Az RPR kerete a találat-szakasz, nem aggregációs ablak, és szó szerint kell maradnia.
Futási feltétel lenyomása
Egy ablakfüggvény kimenetén ülő monoton WHERE-szűrő rendszerint lenyomható az ablakoperátorba megállási feltételként. RPR esetén ez idő előtt megszakítaná a mintaillesztést, esetleg kibontás közben vágva el a találatokat.
Ablak-deduplikáció (RPR vs nem-RPR)
Két azonos ORDER BY- és keretű ablak rendszerint összevonható lenne. Egy RPR-ablak és egy nem-RPR-ablak soha nem oszthat meg állapotot, mert az RPR-oldal találati eredményeket hordoz.
Ablak-deduplikáció (eltérő DEFINE vagy SKIP)
Két azonos PATTERN-ű, de eltérő DEFINE-záradékú vagy eltérő AFTER MATCH SKIP-ű RPR-ablak eltérő találatokat termel, és különálló kell maradjon, még ha strukturális alakjuk azonos is.
Használatlan kimenet projekciója
Ez az optimalizáció alkalmazható: ha a környező lekérdezés soha nem olvassa az ablak kimenetét, az ablakfüggvény NULL-lá válik, és a WindowAgg-ja eldobásra kerül, a sorok számát változatlanul hagyva. A tesztek ellenőrzik, hogy a DEFINE által olvasott oszlopok továbbra is eljutnak a WindowAgg-hoz, amikor az megmarad, és hogy az ablak megmarad, ha az értékét olvassák.
Mozgóátlag-inverz átmenetek
Az inverz átmeneti függvénnyel rendelkező ablak-aggregátumok rendszerint inkrementálisan értékelhetők, ahogy a keret mozog. Az RPR csökkentett kerete nem csúszó ablak; az inverz átmenet útvonala téves eredményt adna.

További esetek ellenőrzik, hogy a költségbecslés figyelembe veszi a DEFINE-t, hogy egy RPR-ablakot tartalmazó alkérdés nem lapul ki, hogy a DEFINE-kifejezések nem szivárognak át egy felsőbb WindowAgg-ba, és hogy a LIMIT a WindowAgg fölött marad; egy második csoport az RPR-t CTE-k, joinok, halmazműveletek, előkészített utasítások, particionált táblák és hasonló konstrukciók mellett futtatja. A legtöbb őrzött eset ugyanazt az alakot követi: egy alap, amely kiváltja az optimalizációt (rendszerint nem-RPR lekérdezés, EXPLAIN-ben ellenőrizve), majd egy strukturálisan hasonló alakú RPR-lekérdezés, ahol az optimalizáció nem kerül alkalmazásra — a DEFINE/SKIP deduplikációs esetben az alap két azonos RPR-ablak, az inverz átmeneti eset pedig EXPLAIN helyett naplózó aggregátummal ellenőrzi a megkerülést. A két fél együttesen bizonyítja, hogy a tervezőben lévő őr valódi munkát végez, nem valódi ellenőrzés nélkül hagy jóvá minden lekérdezést.

Ez a csomag az oka annak is, hogy a §3.4 rövid. A „találat-határok” mechanizmusait — csökkentett keret, SKIP, INITIAL, korlátozott keret levágása — máshol operacionálisan teszteljük; az rpr_integration azt ellenőrzi, hogy semmilyen más optimalizálási szakasz nem nyúl hozzájuk útközben. Egy átmenő rpr_integration teszi lehetővé a többi csomagnak, hogy megbízzon abban: bemeneteik bántatlanul érik el az executort.