Row Pattern Recognition Mélymerülés

§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 szintaxisának és teljes szemantikájának nagy részét közösen használja, 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 három záradék hozzáadásával csatol mintát az ablakhoz az ablakspecifikáción belül: 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 AFTER MATCH SKIP 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.

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ő argumentum egy tetszőleges értékkifejezés, amelyet a navigált sornál értékelnek 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.

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 címke, AFTER MATCH SKIP TO FIRST változó, és AFTER MATCH 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üli adott címkézett sorra.

A fennmaradó tételek heterogén csoportot alkotnak: a SEEK kulcsszó (az INITIAL alternatívája), az üres minta (), a kizárási forma {- … -}, és a sorrendre érzéketlen PERMUTE operátor.

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 ablak bármely pontján kezdődhet (az INITIAL ellentéte).

AFTER MATCH SKIP TO címke

Ugrás egy címkézett sorra.

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 a találatonkénti kimenetből.

Regex: ()

Üres minta — az üres szekvenciára illeszkedik.

PERMUTE(...)

Sorrendre érzéketlen illesztés a felsorolt változók között.

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 (soronkénti kiértékelés a már változóhoz rendelt sorok ellen), ami ugyanazon találatonkénti előzménytől függ, amelyet a MEASURES/CLASSIFIER() is igényel.

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; továbbá az RPR rekurzív lekérdezésen belül nem használható.

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.

§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 három végponttól végpontig terjedő nyomkövetést mutatunk be: egyetlen találat (NFA-mozgás), kontextusabszorpció a könnyű esetben, és az az eset, amikor az abszorpció biztonságtalanná válik.

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.

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. Előretekintés; az ablak formában ritka, mert az ablak monoton.

FIRST(expr [, n])

Az aktuális találat n-edik illesztett sora az elejétől számítva. „Hasonlíts az e találatot indító sorhoz.”

LAST(expr [, n])

Az n-edik legutóbb illesztett sor. „Hasonlíts a legutóbbi illesztett sorhoz.”

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 a találat n-edik sorától (alapértelmezés 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 a találat n-edik sorától. 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 az n-edik legutóbb illesztett sortól. „Hasonlíts egy nem sokkal a legutóbbi találat előtti sorhoz.”

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

Lépj m sort előre az n-edik legutóbb illesztett sortól.

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. A PREV és a NEXT az aktuális sorhoz viszonyított, és mindig biztonságos; a FIRST és a LAST eltolásos változatai a találat határaihoz viszonyítottak, ami befolyásolja a kontextusabszorpciót, és arra kényszeríti a tervezőt, hogy életben tartson olyan kontextusokat, amelyeket egyébként eldobna. 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

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:

A lényeg: a 3. sorban a sor egyaránt kielégíti a START-ot (mindig igaz) és a DOWN-t, de a 2. sort egyetlen életben maradt állapot a DOWN-kilépő ágon van, így csak az UP → DOWN átmenet érvényesül. 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 a korábbi FIN-jelölt (0–4. sorok) — amely akkor jött létre, amikor a DOWN a 4. sorban kilépett — 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:

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

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 szinkronban tár fel.

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. Párhuzamosan haladnak, amíg a DONE el nem dönti őket.

Mindkét ág azonos hosszúságú találatot termel ugyanazokon a sorokon, két jelölt utat hagyva az illesztőnek — 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.

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

A memória O(n)-ről O(1)-re csökken. Az eldobást indokló abszorpciós szabály egyszerű, amikor a kvantor korlátlan:

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:

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ó

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

Abszorpció esetén a C2-t kedden összeolvasztották volna a C1-be — az egyesített kontextus csak egy plafont tart, így a C2 saját nézete (plafon $118, a négynapos futás, amely csak szombaton ér véget) belső állapotból már nem visszaállítható. A C2-nek életben kell maradnia, mert független találatjelölt, amelyre a futtatónak még szüksége lehet: amint a C1 találata szerdán véget ér, a következő próbálkozásnak egy még futó C2-ből kell folytatnia, nem nulláról kezdenie. 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.)

A poszter jobb alsó paneljén („② Navigation”) található függőségi táblázat összefoglalja, mely navigációs formák hoznak létre találatkezdet-függőséget:

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 más kontextus nem állíthat helyre, és bármelyikük eldobása téves eredményt kockáztat.

A tervező ezt a megkülönböztetést fordítási időben felismeri, és kontextusonként dönti el, hogy alkalmazható-e az abszorpció. Ez az oka annak is, hogy a poszter ③ paneljében szereplő benchmark mind a sikeres, mind a sikertelen esetben lineáris marad: ha az abszorpció biztonságos, a futtató összevonja a kontextusokat; ha nem, a tervező a többkontextusú költséget elfogadja, semhogy téves eredményt kockáztasson.

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 O(n)-ben skálázódik, ha a találat megerősödött, és a PostgreSQL előnye — durván 16×–33× — nagyrészt a JVM-rés.

A sikertelen (A+ B+ C+ E) mintán a Trinónak nincs abszorpciója, és O(n²)-re degradálódik, mert minden potenciális találatkezdet után fut; 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

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.

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 teljes képet ad arról, mikor bukik el az abszorpció:

Bármelyik feltétel elegendő ahhoz, hogy az érintett kontextusoknál letiltsa az abszorpciót. Ha egyik sem érvényes — az alapértelmezett AFTER MATCH SKIP PAST LAST ROW csak PREV-, NEXT- vagy csupasz LAST-feltételeket használó DEFINE-okkal —, a futtató mintapozíciónként egyetlen kontextusra esik össze, és végig lineáris marad.

§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, és az 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:

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. Ennek részeként két gyakorlati dolog történik. Először, minden DEFINE-predikátum által hivatkozott oszlopot a lekérdezés kimeneti követelményeinek részeként regisztrálunk, így a tervező 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ó nyolc átírási szabályt alkalmaz egymás után, amíg az AST megáll a változással:

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-abszorpció

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

A kvantorszorzás az egyetlen olyan transzformáció, amely biztonsági ellenőrzést igényel: az optimalizáló csak három biztonságos esetben von össze — mindkét kvantor korlátlan ((A+)+ → A+), a külső pontos ((A{2,3}){5} → A{10,15}), vagy a gyermek triviális {1,1} ((A){2,5} → A{2,5}). 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á —, így az optimalizáló ezeket érintetlenül hagyja.

Elem alakja

A lapos tömb minden eleme a minta egyetlen pozícióját képviseli. Öt 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; é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” (alternáció láncolásához, csoportkezdet általi test megkerüléséhez, ha a kvantor megengedi a nullát, és csoportvég általi visszahurkoláshoz a testbe).

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 → 4
    (csoportot nyit; a jump
     FIN-re ugrik, ha min = 0)

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

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

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (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 az END után a 4. indexre ugrana, ha a csoport opcionális volna. 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 négy 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?)*, (A? B?)+, (A | B*)). Azt mondja a futtatónak, hogy a 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.

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
  AST bejárása é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, az AST-bejárás három 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 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 a jelzők csak az A-ra kerülnek.

Az e három 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. (Egy követő, fix hosszúságú előtagokat árnyékúton kezelő „PREFIX absorption” bővítményt megterveztek, és külön javítás formájában tervezik kiadni.) 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
  row lekérése targetPos-on
    current_row_slot-ba
  result = eval_inner_expression()
  current_row_slot visszaállítása
  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ő, árnyékslot, tuple-másolat.

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 lastMatchedRow − 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 (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      return (lastMatchedRow − 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 a környező állapot alkalmas-e kontextusabszorpcióra (§2.5 vs §2.6).

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. A javítás fordítási időben dönt, két egymást kiegészítő eltolásból:

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, eltolásos LAST, PREV(LAST(...)), NEXT(LAST(...))

Kezdettől előretekintési költségvetés

Mennyire előre (vagy negatív esetben hátra) érhetne bármely DEFINE-hívás a legidősebb élő kontextus találatkezdetétől.

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 két Nav Mark számláló (§3.7) — Lookback és Lookahead — a két költségvetés mért csúcsa: a legmélyebb elérés, amelyet az executor a lekérdezés folyamán mindkét irányban valaha tett.

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

A sikeres találatot kis értékkötegként rögzítjük: érvényességi jelző, sikeres/sikertelen jelző, a sor, amelynél a találat kezdődik, és az általa fogyasztott sorok száma. Ha az érvényességi jelző 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 köteg vizsgálatával. 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 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 egész lekérdezési tervre 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, egyszer kiértékel minden DEFINE-predikátumot az aktuális sor ellen, hogy változónkénti Boole-tömböt állítson elő, majd egy sorral előre hajtja az NFA-t. 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 túllépi a korlátozott keretet:
          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:
          újraértékeljük a találatkezdet-
          függő DEFINE-változókat (§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)

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]
      if elem nem változó:
          continue   # az advance kezeli

      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:
          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). 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-element 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),
    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
         jelölt tartományán belüli későbbi
         kontextusok metszése — 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 abban a pillanatban, amint egy jelöltet rögzítünk, minden olyan későbbi kontextust, amelynek kezdősora a jelölt tartományán belülre esik, azonnal 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 egyike a két FIN-időbeli metszési lépésnek — a másik, amelyet e szakaszban korábban Advance részeként írtunk le, az ugyanazon kontextuson belüli lexikailag alsóbbrendű állapotokat dobja el.

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
          (jogos találatokat ment meg,
           amelyeket a ciklusőr egyébként
           megölne)

  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, majd kilépés
          # hosszabbat előnyben
      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 a (A?)*, (A? B?)+ és (A | B*), mind 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. 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 BEGIN-re, a test ismét üres találatot termel, a BEGIN END-re hurkol, és így tovább. Valami megállító nélkül az Advance DFS-e sosem terminálna.

A futtató ezt egy felkeresett-elem bitmappel állítja meg (mintaelemenként egy bit), amelyet minden állapot DFS-kibontása előtt töröl: amint bármely elemet másodjára meglátogatunk ugyanazon kibontáson belül, azt az utat elhagyjuk. A ciklusőr feltétel nélküli és olcsó, de van mellékhatása — olyan utakat is elhagyhat, amelyeknek el kellene érniük az alsó korlátot jogos üres iterációkon át. Vegyük a (A?){2,3}-at, ahol az A sehol sem illeszkedik a sorfolyamban:

kívánt viselkedés:
  iter 1: A? nulla sorra illeszkedik
          → END, count = 1 (min alatt)
  iter 2: A? nulla sorra illeszkedik
          → END, count = 2 (eléri a min-t)
  kilépés nulla hosszú találattal

amit a ciklusőr önmagában tesz:
  iter 1: A? átugorva → END, count = 1
          → visszahurkolás BEGIN-re
  iter 2: BEGIN már meglátogatott
          → DFS megszakad
  count sosem éri el a min-t
  → találat elbukik (helytelen)

A javítást 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. Futási időben, amikor az END-kezelő visszahurkolni készül, mert az iterációszám még az alsó korlát alatt van, az üres-hurok jelölés azt mondja neki, hogy a normál visszahurkolási út mellé klónozzon egy további fast-forward állapotot is:

advance_end (count a min alatt):

  elsődleges ú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. Az elsődleges visszahurkolás azt az esetet kapja el, amikor a testnek később még valódi találatai lesznek — például a (A?){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 azt az esetet kapja el, amikor a test soha nem termel semmit: megkerüli a ciklusőrt azzal, hogy teljesen 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. Mindkét állapot bekerül a kontextusba; amelyik sikeresen folytat, az nyer, és 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ó linearitá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 állapotát egy idősebb kontextus magasabb számlálójú á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) FIN-en

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 azonnal metszésre kerülnek.

Ciklusőr Advance

Epszilon-kibontások, amelyek ugyanazon DFS-en belül ugyanazt a mintaelemet újra meglátogatják — egyébként örökké hurkolnának nullázható csoportokban.

Üres-hurok fast-forward Advance

Olyan jogos, üres iterációs találatok, amelyeket a ciklusőr nullázható csoportokban megölne — megkerüli a ciklust azzal, hogy kilép a csoportból, a hátralévő kötelező iterációkat üresként deklarálva.

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, és újra a találat befejeztével (FIN-en). 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. A ciklusőr önmagában megölné a jogos találatokat nullázható csoportokban; 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.

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. Három számlálócsoport kerül kibocsátásra az ablakoperátor mellett:

NFA States:    peak, total, merged
NFA Contexts:  peak, total, pruned
NFA: matched     (len min/max/avg)
NFA: mismatched  (len min/max/avg)
NFA: absorbed    (len min/max/avg)
NFA: skipped     (len min/max/avg)
Nav Mark Lookback:   | runtime | retain all
Nav Mark Lookahead:  | runtime | retain all
  (csak amikor a lekérdezés FIRST-et,
   PREV(FIRST(...))-et vagy NEXT(FIRST(...))-et használ)

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 találathossz-hisztogramok négy kimenetelt különítenek el — sikeres találatok, sikertelen találat-kísérletek, abszorbeált kontextusok és kiértékelés nélkül metszett (skipped) kontextusok —, é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 fordítási időben származtat. A Lookback a legmélyebb visszafelé elérés a PREV, az eltolásos LAST és a belső LAST-os összetett formák között; a Lookahead a legmélyebb előre (vagy negatív esetben hátra) elérés, 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, hívásonként kiértékelendő kifejezés, és „retain all”-ként, ha a futtatónak korlátlan költségvetés kell. A Lookahead csak akkor kerül kibocsátásra, ha a lekérdezés ténylegesen találatkezdethez viszonyított navigációt használ.

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 az eredeti PATTERN és DEFINE záradékokat is hűségesen reprodukálja, beleértve a vonakodó kvantorokat, a csoportismétlést és az AFTER MATCH SKIP opciót. Az implementáció 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 13 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

Végponttól végpontig terjedő lekérdezés-szemantika — realisztikus ablakforgatókönyvek szintetikus tőzsdei adatokon (V-alak, W-alak, egymást követő emelkedések, fordulatok).

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.

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. Ez az egyetlen csomag, ahol a bemenetek és kimenetek úgy olvashatók, mint olyan lekérdezések, amelyeket egy felhasználó valóban írhatna; a többi szándékosan reduktív, egyszerre egyetlen rétegre fókuszál.

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.

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 így elkapott hibák (mint például 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: egy bemeneti tábla, amelynek sorai explicit Boole-tömbök, amelyek 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 Boole-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:

• egyszerű korlátlan változó (A+) — a kanonikus N-1-be összevonás;
• fix hosszúságú csoportok ((A B)+, (A B{2})+, háromszintű ágyazott ((A (B C){2}){2})+);
• vezető korlátlan változó fix utótaggal (A+ B) — csak a vezető A+ hordoz abszorpciós jelzőt, az utótag nem;
• ágonkénti abszorpció alternáción belül (B+ C | B+ D);
• több korlátlan változó (A+ B+) — csak a vezető abszorbeálható;
• vonakodó kvantorok (A+?) — ellenőrzött, hogy ki vannak zárva az abszorpcióból;
• nem vezető korlátlan (A B+) — ellenőrzött, hogy kizárt.

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 (psql automatikus kiegészítés, 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 NFA-számlálók a megfelelő helyen jelennek meg — a WindowAgg-onkénti statisztikák (peak/total/merged states, peak/total/pruned contexts, hossz-hisztogramok matched/mismatched/absorbed/skipped esetekre, Nav Mark Lookback és — amikor találatkezdethez viszonyított navigáció van használatban — Nav Mark Lookahead) mind megjelennek EXPLAIN ANALYZE alatt a dokumentált címkékkel.
• A minták helyesen deparsálnak — minden kvantoralak, beleértve a vonakodó változatokat és a korlátozott formákat; minden alternáció; minden csoport; minden AFTER MATCH SKIP-forma; INITIAL; eltolásos navigációs hívások; összetett navigáció. A deparsolt szövegnek változatlanul vissza kell jutnia a parseren át.
• Az azonosító-idézés helyes — a mintaváltozók és DEFINE-kifejezések ugyanazon idézési szabályokkal kerülnek kibocsátásra, mint a hagyományos SQL-azonosítók, így a szokatlan változónevek nem törik el a pg_dump-kimenetet.

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, hogy ezen optimalizációk mindegyike helyesen van-e letiltva vagy megkerülve RPR-ablakok esetén:

Keret-kanonizáció

A tervező monoton aggregátumok 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)

Két azonos PATTERN-ű, de eltérő DEFINE-záradékú 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

Még ha a környező lekérdezés soha nem is olvassa az ablak soronkénti kimenetét, az RPR-ablak nem távolítható el: a mintaillesztő mellékhatásai (mely sorok melyik találatban vannak) máshol a tervben csökkentett keretű számításokat táplálnak.

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.

A teszteken átívelő minta ugyanaz: mindegyik biztosít egy nem-RPR alapot, amely kiváltja az optimalizációt (és ellenőrzi, hogy az EXPLAIN mutatja-e az alkalmazását), majd egy strukturálisan hasonló alakú RPR-lekérdezést futtat, és ellenőrzi, hogy az optimalizáció nem kerül alkalmazásra. 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.