Row Pattern Recognition do hĺbky

§1. Norma, podmnožina a otvorené otázky

1.1 Rozsah normy

Row Pattern Recognition bolo do SQL zavedené normou ISO/IEC 9075-2:2016 a je opísané v sprievodnom dokumente ISO/IEC 19075-5:2021 (Časť 5, „Row Pattern Recognition").

Norma definuje dva povrchy pre rovnaký podkladový mechanizmus. Vlastnosť R010 umiestňuje klauzulu MATCH_RECOGNIZE do zoznamu FROM a vytvára odvodenú tabuľku; vlastnosť R020 zabudúva tú istú logiku vzorov do špecifikácie WINDOW a vytvára výstup okenných funkcií. Oba povrchy zdieľajú väčšinu svojej syntaxe a celú svoju sémantiku, ale predstavujú funkčne odlišné vstupné body — databáza môže implementovať jeden alebo oba.

Séria patchov, o ktorej tu hovoríme, implementuje podmnožinu výhradne R020; tabuľková forma je zámerne mimo rozsahu.

Povrch R020 je malý, ale výrazový. Dotaz pripája vzor k oknu pridaním troch klauzúl do špecifikácie okna: PATTERN opisuje regulárny výraz nad pomenovanými premennými vzoru, DEFINE poskytuje logický predikát, ktorý identifikuje každú premennú, a AFTER MATCH SKIP riadi, ako sú postupné zhody umiestnené v rámci partície.

Voliteľné MEASURES, SUBSET, INITIAL/SEEK a pomocná funkcia CLASSIFIER() vlastnosť dopĺňajú. (Funkcia normy MATCH_NUMBER() patrí výhradne k povrchu R010 — 19075-5 §6.3.3 (6) ju z R020 výslovne vylučuje.)

Patch pokrýva dostatok tejto slovnej zásoby na to, aby fungovali netriviálne dotazy, ale zastavuje sa pred niekoľkými konštrukciami, ktorých implementácia závisí od infraštruktúry, ktorá ešte nebola vybudovaná.

Zvyšok tejto sekcie rozdeľuje slovnú zásobu normy na to, čo patch už podporuje, a na to, čo zámerne ponecháva na neskôr. Nasledujúce zoznamy odrážajú aktuálny stav série patchov.

1.2 Implementované vlastnosti

Implementovaná slovná zásoba postačuje na vyjadrenie kanonických vzorov tvaru V, tvaru W a obratových vzorov, ktoré v prvom rade motivujú rozpoznávanie vzorov v riadkoch. Pokrýva tiež každý štandardný kvantifikátor — vrátane všetkých siedmich neochotných variantov *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — a štyri navigačné primitíva, ktoré podmienky DEFINE potrebujú na porovnanie susediacich riadkov.

klauzula PATTERN

Definuje vzor riadkov v rámci špecifikácie okna.

Regex: + * ? |

Štandardné kvantifikátory a alternácia.

Regex: ( ) zoskupovanie

Sub-vzory v zátvorkách.

Regex: {n} {n,} {,m} {n,m}

Ohraničené počty opakovaní.

Neochotné *? +? ?? {n}? {n,}? {,m}? {n,m}?

Všetkých sedem neochotných (non-greedy) variantov, ktoré norma definuje (vylúčené z optimalizácie absorpcie).

klauzula DEFINE

Logické podmienky identifikujúce každú premennú vzoru.

Univerzálna premenná riadkového vzoru

Nekvalifikované odkazy na stĺpce v DEFINE (napr. holé Price) sa vyhodnotia na aktuálny riadok, podľa 19075-5 §4.10/§4.16.

PREV, NEXT (s posunom)

Dosiahnu n riadkov pred/za aktuálnym riadkom (predvolene 1); vnútorný argument je ľubovoľný hodnotový výraz vyhodnotený v navigovanom riadku.

FIRST, LAST (s posunom)

Dosiahnu riadok relatívny k zhode; FIRST(expr, n) cieli na riadok n po začiatku zhody, LAST(expr, n) na riadok n pred najnovším riadkom zhody.

Zložená navigácia (štyri formy)

Vonkajší krok PREV/NEXT navrstvený na vnútorný FIRST/LAST: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — vnútorný aj vonkajší krok prijímajú vlastný posun.

INITIAL

Zhody vzoru musia začínať v aktuálnom riadku (predvolené).

AFTER MATCH SKIP PAST LAST ROW

Predvolený režim preskočenia; vhodný pre absorpciu kontextu.

AFTER MATCH SKIP TO NEXT ROW

Umožňuje prekrývajúce sa zhody; vypína absorpciu.

1.3 Neimplementované

Vlastnosti, ktoré zostávajú neimplementované, spadajú do troch voľných skupín. Prvou — a zďaleka najväčšou — je rodina konštrukcií sústredených okolo MEASURES: samotná klauzula MEASURES, SUBSET, CLASSIFIER(), odkazy na stĺpce kvalifikované vzorom ako B.price a navigácia kvalifikovaná vzorom ako LAST(B.price) alebo PREV(B.price).

Nejde o nezávislé medzery, ale skôr o rôzne pohľady na jediný chýbajúci kúsok: vykonávateľ by musel uchovávať históriu na zhodu — záznam, pre každý riadok zhody, o tom, na ktorú premennú vzoru bol namapovaný — a žiadna z týchto konštrukcií nemá zmysluplnú definíciu bez nej. CLASSIFIER() číta meno premennej z toho záznamu; B.price číta stĺpec price tých riadkov, ktorých záznam hovorí B; LAST(B.price) prechádza tú istú množinu riadkov a vyberá posledný; SUBSET U = (A, B) definuje virtuálnu premennú, ktorá agreguje cez oba koše; a MEASURES vyhodnocuje výrazy ako AVG(U.Price) presne s touto agregáciou.

Súčasný vykonávateľ vyhodnocuje predikáty DEFINE riadok po riadku, ale výsledné priradenia premenných nikam nezaznamenáva — nie je čo sa neskôr pýtať. Vybudovanie infraštruktúry histórie je preto predpokladom pre celú skupinu; jednotlivé vlastnosti vypadnú ako drobné projekcie, akonáhle záznamy existujú.

Druhá skupina sa týka alternatívnych cieľov preskočenia: AFTER MATCH SKIP TO label, AFTER MATCH SKIP TO FIRST var a AFTER MATCH SKIP TO LAST var. Tieto tiež závisia od histórie zhody, pretože vykonávateľ musí byť schopný ukázať na konkrétny označený riadok vo vnútri najnovšej zhody.

Zvyšné položky sú heterogénnym koncovým radom: kľúčové slovo SEEK (alternatíva k INITIAL), prázdny vzor (), forma vylúčenia {- … -} a operátor PERMUTE necitlivý na poradie.

MEASURES

Pomenované výstupné výrazy na zhodu, napr. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; v R020 vystavené cez OVER ako okenná funkcia. Prijíma kľúčové slová FINAL / RUNNING (19075-5 §5.4), ktoré sa v R020 zlučujú do tej istej hodnoty, keďže miery sa vždy vyhodnocujú na poslednom riadku zhody (19075-5 §6.9 (3)).

SUBSET

Pomenované zjednotenia premenných vzoru, napr. SUBSET U = (A, B, C). Použiteľné všade tam, kde sa môže odkazovať na premennú vzoru — MEASURES, odkazy kvalifikované vzorom v DEFINE, CLASSIFIER(U) — všetko potrebuje históriu zhody.

CLASSIFIER()

Vracia, na ktorú premennú vzoru bol daný riadok namapovaný. Definované pre DEFINE aj MEASURES (19075-5 §5.9); odpoveďou v ľubovoľnom riadku je meno premennej zaznamenané v histórii zhody pre ten riadok.

Odkaz na stĺpec kvalifikovaný vzorom

Holé B.price v DEFINE alebo MEASURES — hodnota stĺpca z riadka namapovaného ako pomenovaná premenná.

Navigácia kvalifikovaná vzorom

Obmedziť navigáciu na riadky namapované ako pomenovaná premenná, napr. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

Zhoda môže začať kdekoľvek v okne (oproti INITIAL).

AFTER MATCH SKIP TO label

Preskočiť na označený riadok.

AFTER MATCH SKIP TO FIRST var

Preskočiť na prvý riadok namapovaný ako pomenovaná premenná.

AFTER MATCH SKIP TO LAST var

Preskočiť na posledný riadok namapovaný ako pomenovaná premenná.

Regex: {- -}

Vylúčenie — odstraňuje namapované riadky z výstupu na zhodu.

Regex: ()

Prázdny vzor — zhoduje sa s prázdnou postupnosťou.

PERMUTE(...)

Zhodovanie necitlivé na poradie cez vymenované premenné.

Agregátne funkcie v DEFINE

Agregáty ako SUM, AVG, COUNT nie sú v predikátoch DEFINE povolené. Norma ich povoľuje ako bežiace agregáty nad čiastočnou zhodou (vyhodnotenie pre každý riadok oproti riadkom už namapovaným na premennú), čo závisí od tej istej histórie zhody, akú vyžadujú MEASURES/CLASSIFIER().

Stojí za to tu uviesť ďalšie štyri body, pretože sa ľahko zamieňajú za opomenutia.

Prvým je, že kotvy vzoru ^ a $ nie sú povolené s RPR v klauzule WINDOW samotnou normou (19075-5 §6.13: „kotvy (^ a $) nie sú povolené pri zhodovaní vzorov riadkov v oknách"; s podkladovou definíciou v 19075-5 §4.14.1); ich neprítomnosť je súladom s normou, nie medzerou.

Druhým je, že MATCH_NUMBER() je rovnako z R020 vylúčená normou (19075-5 §6.3.3 (6) a 19075-5 §6.9 (1)) — patrí výhradne k povrchu R010, a jej absencia je tu opäť súladom, nie chýbajúcou vlastnosťou.

Tretím je súbor štrukturálnych zákazov, ktoré norma R020 ukladá (19075-5 §6.17): rozpoznávanie vzorov riadkov nemôže byť vnorené do iného rozpoznávania vzorov riadkov; MEASURES a DEFINE nesmú obsahovať vonkajšie odkazy; poddotazy vnútri MEASURES alebo DEFINE nesmú odkazovať na premenné vzoru riadkov; a RPR sa nesmie použiť vnútri rekurzívneho dotazu.

Štvrtým je, že samotný MATCH_RECOGNIZE — vlastnosť R010, tabuľkový povrch tej istej mechaniky — je mimo rozsahu tohto patchu. Či PostgreSQL nakoniec pridá R010, bude otázkou pre budúcu sériu, nie meradlom tejto.

§2. Príklady — ako to v skutočnosti beží

Príklady v tejto sekcii sa budujú postupne. Začíname konceptuálnym dôvodom, prečo je zhodovanie vzorov riadkov skutočne odlišné od zhodovania textových vzorov, potom predstavíme štyri navigačné funkcie, vďaka ktorým sú podmienky DEFINE zaujímavé, a nakoniec prejdeme tromi koncovými stopami: jednou zhodou (pohyb NFA), absorpciou kontextu v jednoduchom prípade a prípadom, keď sa absorpcia stáva nebezpečnou.

Vnútorný mechanizmus, ktorý robí navigáciu lacnou — výmena n-tice s 1 slotom — patrí k dizajnu vykonávateľa a je pokrytý v ďalšej sekcii, nie tu.

2.1 Prečo sa vzory riadkov líšia od textových vzorov

Textový regulárny výraz sa zhoduje s prúdom znakov a v každej pozícii je presne jeden symbol na zváženie. Otázka pri behu — „rovná sa aktuálny symbol 'A'?" — má jednu odpoveď áno/nie. Automaty s backtrackingom toto využívajú: na každý znak prežije najviac jedna vetva a cena nejednoznačnosti sa platí opätovným čítaním vstupu.

Vzor riadkov sa líši zásadným spôsobom. Riadok nie je jediný symbol; je to n-tica stĺpcov vyhodnotená oproti množine logických predikátov, podmienkam DEFINE. Dva predikáty môžu byť v tom istom riadku pravdivé súčasne a norma nehovorí, že musia byť vzájomne vylučujúce. Uvažujme:

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

Riadok s price = 150, volume = 2000 spĺňa A aj B, ale nie C. Zhodovač vzorov to nemôže zlúčiť do jedného stavu — dve premenné vzoru sú živé a akýkoľvek prvok vzoru, ktorý ktorúkoľvek z nich pomenuje, môže postúpiť. NFA preto musí niesť viacero súčasných stavov na riadok partície, nie jeden.

Toto jediné pozorovanie poháňa zvyšok architektúry. Stav vykonávania je zoznam kontextov, každý kontext je zoznam stavov a v každom riadku sa beh každého stavu pýta: „vzhľadom na premenné, ktoré sú tu pravdivé, kam môžem ísť?" Vzniknuté rozvetvenia sú dôvodom, prečo beh potrebuje niekoľko vrstiev orezávania — deduplikácia stavov v rámci kontextu, absorpcia naprieč kontextami a ostatné pravidlá zmapované v §3.6 — bez ktorých počet živých stavov a kontextov rastie s partíciou a zhodovanie vzorov sa stáva super-lineárnym.

2.2 Navigačné funkcie

Podmienky DEFINE, ktoré odkazujú iba na aktuálny riadok, sú obmedzené; takmer každý zaujímavý vzor potrebuje porovnať aktuálny riadok so svojimi susedmi alebo s riadkami už skôr v zhode prijatými. Norma na to poskytuje štyri navigačné funkcie a patch implementuje všetky.

PREV(expr [, n])

Riadok n riadkov pred aktuálnym riadkom (predvolene n = 1). Použité pre porovnania „dnes oproti včera".

NEXT(expr [, n])

Riadok n riadkov za aktuálnym riadkom. Predbežný pohľad dopredu; v okennej forme nezvyčajný, pretože okno je monotónne.

FIRST(expr [, n])

n-tý zhodnutý riadok aktuálnej zhody, počítajúc od začiatku. „Porovnaj s riadkom, ktorý začal túto zhodu."

LAST(expr [, n])

n-tý najnovšie zhodnutý riadok. „Porovnaj s najnovším zhodnutým riadkom."

Tieto štyri primitíva sa skladajú: PREV a NEXT môžu obaliť volanie FIRST alebo LAST, čo dáva štyri zložené formy, ktorých sémantika znie „choď na riadok relatívny k zhode, potom o pevnú vzdialenosť od neho odstúp." Toto umožňuje výrazu DEFINE prečítať napríklad riadok bezprostredne pred začiatkom zhody.

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

Krok m riadkov späť od n-tého riadka zhody (predvolene m = 1). „Aká bola hodnota tesne pred začiatkom tejto zhody?"

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

Krok m riadkov vpred od n-tého riadka zhody. Siaha hlbšie do zhody bez závislosti od aktuálneho riadka.

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

Krok m riadkov späť od n-tého najnovšie zhodnutého riadka. „Porovnaj s riadkom krátko pred najnovšou zhodou."

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

Krok m riadkov vpred od n-tého najnovšie zhodnutého riadka.

Stojí za to tu uviesť dva praktické body. Po prvé, navigácia môže byť zložená: PREV(FIRST(price)) číta riadok bezprostredne pred začiatkom zhody a patch to podporuje. Po druhé, navigácia má dôsledky pre optimalizácie vykonávateľa. PREV a NEXT sú relatívne k aktuálnemu riadku a sú vždy bezpečné; FIRST a varianty LAST s posunom sú relatívne k hraniciam zhody, čo interaguje s absorpciou kontextu a núti plánovač udržiavať pri živote niektoré kontexty, ktoré by inak zahodil. Mechanizmus tejto interakcie je témou §2.6.

2.3 Riešený príklad 1 — Pohyb NFA

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

Vzor sa sploští na štyri prvky:

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

Pre cenovú postupnosť 100, 110, 120, 115, 108, 130:

Kľúčový bod: v riadku 3 riadok spĺňa START (vždy pravdivé) aj DOWN, ale jediný stav, ktorý prežil riadok 2, je na vetve výstupu DOWN, takže sa uskutoční iba prechod UP → DOWN. Multi-stavová povaha z §2.1 je viditeľná ako rozvetvenie pri každej zhode UP (stav by mohol zostať na UP+ alebo postúpiť k DOWN+). Greedy preferencia je „cykluj znova pred výstupom", takže pri dostatku dát by cykliace vetvy zhodu predĺžili; tu cykliaci DOWN hynie v riadku 5 (130 ≮ 108) a skorší FIN kandidát (riadky 0–4) — vytvorený, keď DOWN ukončil v riadku 4 — sa finalizuje ako zhoda.

Výsledok dotazu z tejto stopy vyplýva priamo. Podľa sémantiky RPR sa okenné funkcie first_value(price) a last_value(price) vyhodnocujú iba v riadku, ktorý začal zhodu — každý iný riadok v zhode pre tieto okenné funkcie produkuje NULL, keďže jeho zredukovaný rámec je prázdny. Výstup pre naše dáta teda vyzerá ako tabuľka, ktorú poster ukazuje vo svojom paneli vpravo hore:

Riadok 0 je začiatkom zhody, takže jeho rámec pokrýva riadky 0–4 a okenné funkcie hlásia otváraciu cenu V-tvaru ($100) a spodnú cenu ($108). Riadky 1–4 sú vnútri zhody, ale nie jej začiatkom, takže dostávajú NULL. Riadok 5 (cena $130) je mimo akejkoľvek zhody a tiež dostáva NULL.

2.4 Riešený príklad 2 — Alternácia a lexikálne poradie

Forma (A | B) dáva zhodovaču výber: v každom riadku sú dve alternatívy testované nezávisle a môže sa zhodovať ľubovoľný počet z nich. Tu sa multi-stavová povaha z §2.1 stáva viditeľnou vnútri jedného kontextu — nie naprieč kontextami (to je absorpcia), ale pozdĺž paralelných vetiev, ktoré vykonávateľ skúma synchrónne.

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

Predstavte si riadok, kde cena súčasne stúpla a prekročila $100 — sú pravdivé UP aj HIGH. Každá alternatíva splodí svoj vlastný stav: jeden kráča po vetve UP, druhý po vetve HIGH. Postupujú paralelne, kým ich nevyrieši DONE.

Obe vetvy produkujú zhodu rovnakej dĺžky cez tie isté riadky, čím zhodovaču zostávajú dve kandidátske cesty — jedna označená UP, DONE a jedna označená HIGH, DONE. Norma to rieši lexikálnym poradím: spomedzi alternatív zapísaných v (UP | HIGH) vyhráva tá zapísaná ako prvá, bez ohľadu na dĺžku zhody. Keďže sa UP objavuje pred HIGH, prežívajúcou cestou je UP, DONE.

Lexikálne poradie je to, čo robí CLASSIFIER() dobre definovaným, keď bude napokon implementovaný — umožňuje behu povedať používateľovi „tento riadok sa zhoduje s UP, nie s HIGH", aj keď boli oba predikáty pravdivé. Lexikálne poradie je primárnym pravidlom pre alternáciu: lex-skoršia vetva vyhráva nad lex-neskoršou, aj keby lex-neskoršia vetva produkovala dlhšiu zhodu, a lex-neskoršia (možno kratšia) vetva môže predsa vyhrať, ak všetky lex-skoršie vetvy hynú pred dosiahnutím FIN. Greedy dĺžka sa rozhoduje v rámci jediného kvantifikátora — pri dvoch dokončeniach tej istej alternačnej vetvy greedy kvantifikátor preferuje viac iterácií.

2.5 Riešený príklad 3 — Absorpcia kontextu (rovnaký osud)

Najjednoduchší vzor, ktorý vykazuje absorpciu, je PATTERN (A+) s DEFINE A AS TRUE. Každý riadok sa zhoduje s A a norma vyžaduje, aby zhodovač zvažoval každý riadok ako možný začiatok zhody. Naivne to znamená N kontextov pre N-riadkovú partíciu. Vezmime päťriadkovú partíciu (akékoľvek dáta — predikát je konštantne pravdivý):

Pamäť rastie z O(n) na O(1). Pravidlo absorpcie, ktoré ospravedlňuje vyhodenie, je priamočiare, keď je kvantifikátor neohraničený:

Ľavý dolný panel posteru („① Absorpcia kontextu") je presne toto pravidlo vizualizované na piatich riadkoch.

V pravidle sa skrýva jemný, ale dôležitý bod: vyhodenie je bezpečné, pretože predikát A AS TRUE sa v každom riadku vyhodnocuje na rovnakú hodnotu bez ohľadu na to, ktorý kontext sa pýta. To isté platí pre akýkoľvek predikát, ktorý odkazuje iba na aktuálny riadok alebo pevný posun od neho — vrátane PREV. Nasledujúci príklad prepína na konkrétny týždeň cien s predikátom založeným na PREV a §2.6 znovu použije presne ten istý týždeň, aby symetria medzi bezpečnou a nebezpečnou absorpciou bola zrejmá:

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

Vezmime obchodný týždeň $100, $108, $112, $116, $110 od pondelka do piatka — štyri vzostupy, po ktorých nasleduje náhly pokles. Predpokladajme, že C1 začína v utorok (prvý deň, keď sa RISE zhoduje: $108 > $100), a vykonávateľ špekulatívne sleduje aj C2 začínajúci v stredu. Podmienka RISE každého riadka porovnáva cenu riadka s jej bezprostredným predchodcom — fakt na úrovni partície, nie na úrovni kontextu — takže oba kontexty sú nútené vypočítať tú istú logickú hodnotu v každom zdieľanom riadku:

Príbeh sa zlomí v okamihu, keď predikát začne závisieť od vlastných hraníc každého kontextu — a o tom je §2.6.

2.6 Riešený príklad 4 — Keď sa absorpcia stáva nebezpečnou

Predpokladajme, že analytik chce nájsť po sebe nasledujúce obchodné dni, počas ktorých akcia zostala v rozpätí desiatich dolárov od dňa, ktorým beh začal — akési konsolidačné okno. Vzor a DEFINE vyzerajú takto:

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

Podmienka teraz porovnáva cenu aktuálneho riadka s cenou na začiatku aktuálneho behu. Dva behy, ktoré začali v iné dni, majú odlišné hodnoty FIRST(price), takže dva stavy na rovnakom prvku vzoru a s rovnakým počtom už nie sú zameniteľné: ich budúcnosti závisia od hranice, ktorú sa absorpcia chystala vyhodiť.

Vezmime presne ten istý obchodný týždeň ako v §2.5 — $100, $108, $112, $116, $110 od pondelka do piatka. Beh opäť udržiava súčasne dva kandidátske behy pri živote: C1 začal v pondelok, C2 začal v utorok (každý riadok je potenciálnym začiatkom behu pri STABLE+).

Pri absorpcii by bol C2 v utorok zlúčený do C1 — zlúčený kontext si ponecháva iba jeden strop, takže odlišný pohľad C2 (strop $118, štvordňový beh, ktorý končí až v sobotu) už z vnútorného stavu nie je obnoviteľný. C2 musí zostať pri živote, pretože je nezávislým kandidátom na zhodu, ktorý beh ešte môže potrebovať: keď zhoda C1 v stredu skončí, ďalší pokus musí pokračovať zo stále bežiaceho C2 namiesto začínania od nuly. Vždy keď predikát DEFINE nesie závislosť od začiatku zhody, plánovač preto preventívne vypína absorpciu.

(Keď zhoda vedúceho kontextu uspeje, kontexty, ktoré začali vo vnútri jeho prijatého rozsahu — pri predvolenom AFTER MATCH SKIP PAST LAST ROW — sú jednoducho zahodené; sú udržiavané pri živote iba preto, aby beh mal kam ustúpiť, ak vedúca zhoda zlyhá.)

Tabuľka závislostí na pravom dolnom paneli posteru („② Navigácia") zhŕňa, ktoré navigačné formy vytvárajú závislosť od začiatku zhody:

Dva príklady v §2.5 a §2.6 sa redukujú na jediné pravidlo. Rovnaký osud je to, čo robí absorpciu bezpečnou: ak každý kontext na rovnakom prvku vzoru vypočíta rovnakú odpoveď na každý budúci predikát, treba ponechať iba najstarší. Rozdielne osudy robia absorpciu nebezpečnou: hneď ako predikáty rozvetvia podľa kontextovo-súkromného stavu — čo presne robia FIRST a posunové LAST — každý živý kontext predstavuje budúcnosť, ktorú žiadny iný kontext nemôže obnoviť, a vyhodenie ktoréhokoľvek z nich riskuje produkciu nesprávnej odpovede.

Plánovač toto rozlíšenie deteguje v čase kompilácie a rozhoduje pre každý kontext, či sa absorpcia uplatňuje. Toto je tiež dôvod, prečo benchmark posteru v paneli ③ zostáva lineárny v prípadoch úspechu aj zlyhania: keď je absorpcia bezpečná, beh kontexty zlučuje, a keď nie, plánovač akceptuje viac-kontextovú cenu radšej, než by riskoval nesprávnu odpoveď.

Čísla benchmarku na posteri sú ten istý algoritmus odohrávajúci sa v škále. Na úspešnom vzore (A+ B+ C+ D) oba PostgreSQL aj Trino škálujú O(n), keď je zhoda potvrdená, a náskok PostgreSQL — približne 16× až 33× — je väčšinou medzera JVM.

Na neúspešnom vzore (A+ B+ C+ E) Trino nemá absorpciu a degraduje na O(n²) prenasledujúc každý potenciálny začiatok zhody; pri 100 000 riadkoch trvá viac ako päť hodín, zatiaľ čo PostgreSQL stále končí za 92 ms, čo je zrýchlenie približne 217 000×.

Tá medzera nie je inžinierskym leskom — je to presne rozlíšenie rovnakého-osudu / rozdielneho-osudu z §2.5 a §2.6, aplikované na každý riadok každého potenciálneho začiatku zhody v partícii.

2.7 Riešený príklad 5 — Keď SKIP vypne absorpciu

Predošlý príklad zlomil absorpciu zo strany dát: FIRST v DEFINE spôsobil, že každý kontext vyhodnocoval predikáty inak. Absorpcia sa môže zlomiť aj zo strany výstupu, a klauzula AFTER MATCH SKIP je to, čo to ovláda.

Uvažujme vzor PATTERN (A+) s DEFINE A AS TRUE nad piatimi riadkami, ktoré sa všetky zhodujú s A. Pri predvolenom AFTER MATCH SKIP PAST LAST ROW zhodovač nájde najdlhšiu zhodu začínajúcu v najskoršom riadku a potom za ňu skočí; akýkoľvek kontext, ktorý začal vnútri tejto zhody, je implicitne vyhodený ako redundantný — presne situácia, na ktorú je absorpcia navrhnutá. Výstupom je jediná zhoda, riadky 0–4, a beh potrebuje iba jeden živý kontext.

Prepnite režim preskočenia na AFTER MATCH SKIP TO NEXT ROW a kontrakt sa zmení:

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

Teraz musí byť každá potenciálna začiatočná pozícia reportovaná osobitne, aj keď sa zhody prekrývajú. Pre tých istých päť riadkov beh musí vydať päť zhôd: riadky 0–4, 1–4, 2–4, 3–4 a 4–4. Žiadnu z nich nemožno nahradiť „dlhšou začínajúcou skôr", pretože norma hovorí, že používateľ chce všetky.

Všimnite si, že predikát sa nezmenil. A AS TRUE sa v každom riadku vyhodnocuje rovnako bez ohľadu na to, ktorý kontext sa pýta, takže podmienka rovnakého-osudu z §2.5 je stále splnená. Mení sa výstupná požiadavka: aj kontexty s identickými budúcnosťami musia koexistovať, pretože zodpovedajú odlišným riadkom výsledku. Plánovač preto vypína absorpciu kontextu vždy, keď je v platnosti AFTER MATCH SKIP TO NEXT ROW, bez ohľadu na klauzulu DEFINE.

Položenie §2.6 a §2.7 vedľa seba dáva úplný obraz o tom, kedy absorpcia zlyháva:

Ktorákoľvek podmienka stačí na vypnutie absorpcie pre dotknuté kontexty. Keď neplatí ani jedna — predvolené AFTER MATCH SKIP PAST LAST ROW s podmienkami DEFINE, ktoré používajú iba PREV, NEXT alebo holé LAST — beh sa zlučuje do jedného kontextu na pozíciu vzoru a zostáva lineárny počas celého času.

§3. Dizajn — od parsera po vykonávateľa

Row Pattern Recognition je implementované ako tri etapy, ktoré si odovzdávajú prácu cez dobre definované medziformy. Parser prevádza SQL text na strom vzoru a zoznam predikátov DEFINE; plánovač kompiluje strom do plochého poľa prvkov vzoru a rozhoduje, ktoré z nich sa môžu zúčastniť absorpcie kontextu; vykonávateľ púšťa pole oproti partícii riadok po riadku v trojfázovej slučke. Každá etapa má vlastný tvar dát a väčšina dizajnového dôvtipu je na hraniciach: plochý NFA, ktorý sa zmestí do cache, navigačný model, ktorý znovu používa jediný slot n-tice namiesto materializácie jedného na odkaz, a pravidlo absorpcie, ktoré mení pamäť O(n²) na O(n).

SQL text
  │
  │  etapa parsera
  ▼    validovať rámec
       postaviť strom vzoru
       typovo overiť DEFINE

strom vzoru + zoznam DEFINE
  │
  │  etapa plánovača
  ▼    optimalizovať strom
       kompilovať do plochého poľa NFA
       rozhodnúť absorbovateľnosť

plochý NFA + príznaky absorpcie
  │
  │  etapa vykonávateľa
  ▼    motor na riadok:
       Zhoda → Absorpcia → Postup

výsledok zhody:
  začiatočný riadok, dĺžka, úspech/zlyhanie

Nasledujúce sekcie kráčajú nadol týmto potrubím. §3.1 pokrýva parser a tvar stromu vzoru; §3.2 pokrýva kompiláciu, ktorá mení strom na plochý NFA; §3.3 pokrýva navigačný model, ktorý predikáty DEFINE používajú na pohľad na susediace riadky; §3.4 pokrýva spracovanie hraníc zhody — pravidlá SKIP, INITIAL a ohraničeného rámca, ktoré stanovujú, kde zhoda začína a končí; §3.5 je trojfázový motor na riadok; §3.6 zbiera všetky orezávacie mechanizmy, ktoré udržiavajú priestor stavov ohraničený; a §3.7 mapuje, čo implementácia vystavuje vo výstupe EXPLAIN.

3.1 Parser — budovanie stromu vzoru

Parser rozpoznáva rozpoznávanie vzorov podľa prítomnosti klauzuly PATTERN vnútri špecifikácie okna. Jeho prvou úlohou je validácia rámca, keďže RPR ukladá obmedzenia, ktoré bežné okenné dotazy nemajú: režim rámca musí byť ROWS (nie RANGE ani GROUPS), počiatočná hranica musí byť CURRENT ROW a možnosti EXCLUDE sú zakázané. Toto sú kontroly súladu, nie optimalizácie — predstava rámca v RPR je rozsah zhody a norma neuvažuje o jeho vyplnení čímkoľvek iným ako zhodnutými riadkami.

Keď rámec prejde validáciou, parser premení klauzulu PATTERN na strom postavený zo štyroch druhov uzlov — odkaz na premennú, postupnosť (zreťazenie), alternácia a skupina (sub-vzor v zátvorkách). Každý uzol nesie kvantifikátor ako tri čísla — dolná hranica, horná hranica (možno nekonečná) a príznak pre neochotné zhodovanie:

Každý predikát DEFINE je potom typovo overený oproti stĺpcom partície a privedený k logickému výrazu. Ako súčasť toho sa dejú dve praktické veci. Po prvé, každý stĺpec, na ktorý sa odkazuje predikát DEFINE, je registrovaný ako súčasť výstupných požiadaviek dotazu, takže plánovač tieto stĺpce prepúšťa do etapy vykonávateľa, aj keď ich okolitý dotaz nevyberá — bez toho by beh nemal voči čomu vyhodnocovať. Po druhé, premenné, ktoré sa objavujú v PATTERN, ale nikdy v DEFINE, sú implicitne pravdivé: zhodujú sa s každým riadkom.

3.2 Kompilácia — z AST na plochý NFA

Plánovač premieňa strom parsera na dátovú štruktúru, ktorú vykonávateľ pustí: ploché pole prvkov vzoru adresované indexom. Kompilácia prebieha ako šesťkrokové potrubie:

compile(astTree):
  1. optimalizovať AST
  2. zmerať veľkosť a hĺbku
  3. alokovať pole prvkov
  4. naplniť z AST
       (priradiť ukazovatele next/jump)
  5. finalizovať — nastaviť FIN sentinel
  6. označiť prvky vhodné na absorpciu

Plochý tvar je zvolený z jednoduchého dôvodu: vykonávateľ potrebuje prejsť vzor mnohokrát na partíciu a súvislé indexovo-adresovateľné pole je najlacnejšia dátová štruktúra na prechádzanie. Kroky 1 a 6 sú zaujímavé — krok 1, pretože určuje, aké veľké pole bude, a krok 6, pretože rozhoduje, či sa optimalizácia absorpcie z §2.5 vôbec zapne.

Optimalizácia AST

Optimalizácia sa vypláca dvakrát: raz v statickom počte prvkov plochého poľa a opäť v každom riadku spracovanom za behu. Každá transformácia redukuje priestor stavov, ktorý beh musí enumerovať. Optimalizátor aplikuje osem prepisovacích pravidiel za sebou, kým sa AST neprestane meniť:

Splošťovanie SEQ

SEQ(A, SEQ(B, C)) → SEQ(A, B, C)

Zlučovanie po sebe idúcich premenných

A A → A{2}
A{2,3} A{1,2} → A{3,5}

Zlučovanie po sebe idúcich skupín

(A B)+ (A B)+ → (A B){2,∞}

Zlučovanie po sebe idúcich ALT

(A | B) (A | B) (A | B) → (A | B){3}

Absorpcia prefixu/sufixu

A B (A B)+ → (A B){2,∞}

Splošťovanie a deduplikácia ALT

(A | (B | C)) → (A | B | C)
(A | B | A) → (A | B)

Násobenie kvantifikátorov

(A+)+ → A+
(A{2,3}){5} → A{10,15}

Rozbalenie jediného potomka

SEQ(A) → A
(A){1,1} → A

Násobenie kvantifikátorov je jediná transformácia, ktorá vyžaduje bezpečnostnú kontrolu: optimalizátor zlučuje iba v troch bezpečných prípadoch — oba kvantifikátory neohraničené ((A+)+ → A+), vonkajší presný ((A{2,3}){5} → A{10,15}) alebo potomok triviálny {1,1} ((A){2,5} → A{2,5}). Iné kombinácie môžu zaviesť medzery, ktoré by plochá forma minula — napr. (A{2}){2,3} akceptuje iba {4, 6}, ale naivné A{4,6} by akceptovalo aj 5 — takže optimalizátor ich necháva nedotknuté.

Tvar prvku

Každý prvok plochého poľa predstavuje jednu pozíciu vo vzore. Existuje päť logických druhov: odkaz na premennú (jediný druh, ktorý spotrebúva riadok); značky group begin a group end, ktoré otvárajú a zatvárajú sub-vzor v zátvorkách; značka alternácie, ktorá vedie zoznam vetiev; a finish značka na konci vzoru.

Každý prvok tiež nesie hĺbku (úroveň zanorenia skupiny), kvantifikátor (počet min a max opakovaní, možno nekonečný) a dva ukazovatele prechodu — next, „kam ísť po spotrebovaní tohto prvku," a jump, „kam preskočiť" (používa alternácia na zreťazenie vetiev, group begin na obídenie tela, keď kvantifikátor povoľuje nulu, a group end na cyklenie späť do tela).

Pre PATTERN ((A B)+) kompilované pole vyzerá takto:

PATTERN ((A B)+) sa skompiluje na:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (otvára skupinu; jump preskakuje
     na FIN, keď 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
    (zatvára skupinu; jump cyklí späť)

[4] FIN    vzor kompletný

Vzor sa číta zľava doprava cez next, pričom jump spracúva nelineárne hrany. Na idx 3 jump END ukazuje späť na idx 1, čím vonkajší neohraničený kvantifikátor cyklí; na idx 0 by jump BEGIN preskočil za END na idx 4, ak by skupina bola voliteľná. Beh nikdy nemusí konštruovať graf za behu — len sleduje tieto dva ukazovatele počas prechádzania poľa.

Atribúty na prvok

Okrem tvaru každý prvok nesie štyri logické atribúty, ktoré riadia správanie behu na tej pozícii:

Reluctant (neochotný)

Obracia poradie expanzie kvantifikátora. Greedy kvantifikátory skúšajú „cykluj znova" pred „výstup"; neochotné kvantifikátory skúšajú „výstup" najprv. Nesený premennou pre A+?; nesený BEGIN a END skupiny pre ((…)+?).

Empty-loopable

Nastavený na koncoch skupín, ktorých telo je nullable ((A?)*, (A? B?)+, (A | B*)). Hovorí behu pridať rýchly výstup vedľa normálneho cyklenia späť, aby cycle guard nezabil legitímne zhody v skupinách, ktoré môžu produkovať prázdne iterácie.

In-absorbable-region

Označuje každý prvok, ktorý leží v rámci regiónu vhodného na absorpciu — používa beh na sledovanie, či je aktuálny stav stále v bezpečnom území.

Absorption-comparison-point

Označuje konkrétny prvok, kde by sa mali spúšťať porovnania absorpcie. Pre jednoduché A+ pristane na premennej; pre neohraničenú skupinu ako (A B)+ pristane iba na konci skupiny.

Rozdelenie medzi „in-region" a „comparison-point" je dôležité, pretože absorpcia má zmysel iba v bodoch, kde sa iterácie uzatvárajú. Vnútri tela (A B)+ je beh v polovici iterácie a počet ešte nedosiahol svoju finálnu hodnotu pre toto kolo; porovnávanie tu by znamenalo porovnávanie neporovnateľných hodnôt. Stav musí dosiahnuť koniec skupiny, kým môže beh rozhodnúť. Prvý atribút teda hovorí „si stále v absorbovateľnom území"; druhý hovorí „dosiahol si bod porovnania — choď skontrolovať."

Analýza absorbovateľnosti

Krok 6 kompilácie je to, čo dáva pravidlu „rovnakého osudu" z §2.5 jeho kompilačno-časový dôkaz. Rozhodnutie je vrstvené:

isAbsorbable(query):
  ak režim SKIP != SKIP PAST LAST ROW
      → vrátiť false
  ak koniec rámca != UNBOUNDED FOLLOWING
      → vrátiť false
  ak akýkoľvek DEFINE závisí od match_start
      → vrátiť false
  prejsť AST a označiť
  prvky, ktoré spĺňajú
  štrukturálny prípad

Prvé tri kontroly sú na úrovni dotazu: zodpovedajú presne podmienkam §2.7 (strana výstupu: režim SKIP), ohraničenému rámcu (hranica láme monotónnosť) a §2.6 (strana dát: FIRST alebo posunové LAST v DEFINE). Keď ktorákoľvek z nich zlyhá, analýza nenastavuje žiadne príznaky a absorpcia je vypnutá v rámci celého dotazu. Keď všetky prejdú, prechod AST pripúšťa tri štrukturálne tvary:

Prípad 1 — Jednoduchá neohraničená premenná

A+, A*, A{2,∞}

Každá iterácia je presne jeden riadok. Počet skoršieho kontextu je vždy ≥ ako neskoršieho v každej zdieľanej pozícii.

Prípad 2 — Skupina s pevnou dĺžkou, neohraničený vonkajší

(A B)+, (A B{2})+, ((A (B C){2}){2})+

Každý potomok má min == max, takže telo je sémanticky ekvivalentné svojej rozvinutej forme {1,1} — (A B{2})+ sa správa ako (A B B)+. Každá iterácia spotrebuje pevný počet riadkov; dominancia počtu stále platí.

Prípad 3 — Skupina, ktorej telo začína neohraničenou premennou

(A+ B)+

Vedúca neohraničená premenná je sama absorbovateľná (Prípad 1) a chráni skoršie kontexty. Absorpcia sa zastavuje, len čo sa stav posunie za A — zvyšok tela nemá záruku monotónnosti, takže príznaky sú nastavené iba na A.

Štrukturálne prípady nepokryté týmito tromi tvarmi sú rovnako poučné. A B+ nemožno súčasným pravidlom absorbovať, pretože vedúce A spotrebuje riadok skôr, ako začne neohraničená časť, takže kontexty začínajúce o jeden riadok inak sú na rôznych pozíciách vnútri neohraničeného tela. (Následné rozšírenie „PREFIX absorption", ktoré spracúva prefixy s pevnou dĺžkou cez tieňovú cestu, bolo navrhnuté a je plánované pre samostatný patch.) Neochotné kvantifikátory ako A+? sú vylúčené konštrukciou: pravidlo absorpcie predpokladá greedy sémantiku, kde dlhšie zhody pohlcujú kratšie, a neochotné zhodovanie ten smer obracia.

Výsledkom je rozhodnutie na prvok, nie na vzor. Jediný plán dotazu môže mať absorpciu zapnutú pre vedúce A+ vzorov ako (A+ B+ C) alebo (A+ B+)+ — to druhé je len Prípad 3 aplikovaný na svoj vedúci prvok — a vypnutú pre všetko za tým; beh jednoducho konzultuje atribút comparison-point na prvku aktuálneho stavu zakaždým, keď uvažuje o priechode absorpcie. Keď sa stav posunie do regiónu, ktorý nemožno absorbovať, absorpcia je pre ten stav natrvalo vypnutá — presne to, čo §2.5 a §2.6 potrebujú byť pravdivé na algoritmickej úrovni.

3.3 Navigácia — výmena n-tice s 1 slotom

DEFINE výrazy sú obyčajné SQL výrazy vyhodnocované oproti riadku, ale môžu zahŕňať PREV, NEXT, FIRST alebo LAST — odkazy, ktoré ukazujú na iné riadky. Samotné riadky sú už vo vyrovnávacej pamäti tuplestoru okna; čo musí vykonávateľ ešte spravovať, je tuple slot, z ktorého číta mechanizmus SQL výrazov, keďže odkazy na stĺpce vnútri výrazu sú viazané na slot v čase plánu. Implementácia znovu používa jediný navigačný slot pre každé navigačné volanie: slot sa pred vyhodnotením vnútorného výrazu vymení a po ňom obnoví, takže zvyšok mechanizmu SQL výrazov nikdy nepozná rozdiel.

Model, ktorý vykonávateľ vidí, je malý: existuje slot aktuálneho riadka, ktorý drží riadok, voči ktorému sa DEFINE výraz vyhodnocuje, a navigačný slot, ktorý beh môže dočasne presmerovať na iný riadok. Okolo akéhokoľvek navigačného volania beh nastaví navigačný slot, vyhodnotí vnútorný výraz, ako keby čítal aktuálny riadok, a potom obnoví pôvodný riadok. Pseudokód:

eval_navigation(call):
  targetPos = compute_target_position(call)
  ak je targetPos mimo platného rozsahu:
      vrátiť NULL

  uložiť current_row_slot
  načítať riadok na targetPos
    do current_row_slot
  result = eval_inner_expression()
  obnoviť current_row_slot
  vrátiť result

Trik je v tom, že existuje presne jeden slot na uloženie a obnovenie. Vnútorný výraz — čokoľvek to je, vrátane aritmetiky, volaní funkcií alebo iných odkazov na stĺpce — beží oproti vymenenému slotu pomocou tej istej vyhodnocovacej cesty, akú by použil pre aktuálny riadok. Žiadny alternatívny vyhodnocovač, žiadny tieňový slot, žiadna kópia n-tice.

Zložená navigácia sa sploští v čase parsovania, takže výmena sa stále deje raz. PREV(FIRST(price)) je rozpoznané ako dvojkroková navigácia — „choď na prvý zhodnutý riadok, potom o jeden riadok skôr" — a uložené ako jediné navigačné volanie s zloženým druhom. Beh počíta cieľovú pozíciu v dvoch etapách, ale vykoná iba jednu výmenu slotu na načítanie finálneho riadka:

compute_target_position(call):

  # relatívne k aktuálnemu riadku
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # relatívne k zhode
  FIRST(n):
      return matchStart + n
  LAST(n):
      return lastMatchedRow − n

  # zložené: rel. k zhode, potom krok
  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

  validovať voči vhodnému rozsahu
  (rozsah zhody pre vnútorné FIRST/LAST,
   rozsah partície pre vonkajší krok)

Cache pozícií skratuje načítanie z tuplestoru, keď viaceré navigačné volania v tom istom DEFINE cieľa na ten istý riadok — bežné vo výrazoch ako price > PREV(price) AND volume > PREV(volume), kde sa obe volania rozriešia na predošlý riadok. Cache ukladá iba „naposledy načítanú pozíciu" a samotná výmena zostáva jednou operáciou.

Klasifikácia navigačných volaní je príspevkom plánovača k rozhodnutiu o absorpcii. Plánovač prechádza každý DEFINE výraz a triedi každú premennú do jedného z dvoch košov podľa toho, či všetky kontexty vypočítajú tú istú logickú hodnotu v tom istom riadku, alebo každý kontext vypočíta vlastnú. Kôš určuje dve veci za behu: ako často sa premenná vyhodnocuje (raz zdieľaná, alebo raz na dotknutý kontext — §3.5 Fáza 1), a či je okolitý stav vhodný na absorpciu kontextu (§2.5 vs §2.6).

Klasifikácia sa vykonáva v čase plánu a ukladá sa pri každej premennej DEFINE, takže beh netrávi čas rozhodovaním — jednoducho číta kôš pre každú premennú pri spracovaní riadka.

Rozpočet uchovávania

Navigácia siaha do riadkov, ktoré mechanizmus okenných funkcií inak prúdovo prešiel. Aby boli tie riadky dostupné, vykonávateľ je postavený na tuplestore, ktorý zachováva posuvné okno nedávnych riadkov; otázkou je, aké široké musí to okno byť. Patch rozhoduje v čase kompilácie z dvoch doplnkových posunov:

Rozpočet lookback

Ako ďaleko dozadu od aktuálneho riadka môže akékoľvek volanie DEFINE siahnuť.

Prispievatelia: PREV, LAST s posunom, PREV(LAST(...)), NEXT(LAST(...))

Rozpočet lookahead-od-začiatku

Ako ďaleko dopredu (alebo dozadu, ak je záporný) od začiatku zhody najstaršieho živého kontextu môže akékoľvek volanie DEFINE siahnuť.

Prispievatelia: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

Za behu sa značka orezania tuplestoru nastavuje na to, ktorá z dvoch pozícií je skoršia — aktuálny riadok mínus rozpočet lookback, a začiatok zhody najstaršieho živého kontextu plus rozpočet lookahead. Čokoľvek pred touto značkou nemôže dosiahnuť žiadne navigačné volanie v žiadnom živom kontexte, a tuplestore to môže zahodiť. Dva čítače Nav Mark, ktoré EXPLAIN hlási (§3.7) — Lookback a Lookahead — sú namerané vrcholy oboch rozpočtov, najhlbšie, kam vykonávateľ kedy musel siahnuť v ktoromkoľvek smere v priebehu dotazu.

3.4 Hranice zhody — SKIP, INITIAL a ohraničený rámec

Úspešná zhoda sa zaznamenáva ako malý balík hodnôt: príznak platnosti, príznak úspechu/zlyhania, riadok, v ktorom zhoda začína, a počet riadkov, ktoré spotrebovala. Keď je príznak platnosti nastavený, následné dotazy voči vykonávateľovi — „je tento riadok vnútri zhody?" — môžu odpovedať v O(1) prezretím balíka. Dĺžka nula je skutočným výsledkom, nie chybou: predstavuje vzor, ktorý sa zhodol bez spotrebovania ktoréhokoľvek riadka, čo musí vykonávateľ odlíšiť od „v tejto pozícii ešte nebola pokúsená žiadna zhoda."

Klauzula AFTER MATCH SKIP rozhoduje, kde začína nasledujúci pokus o zhodu. AFTER MATCH SKIP PAST LAST ROW sa presúva na riadok za koncom zhody, čím produkuje neprekrývajúci sa výstup, ktorý chce väčšina dotazov, a umožňuje optimalizáciu absorpcie.

AFTER MATCH SKIP TO NEXT ROW sa presúva iba na riadok za začiatkom zhody, čím umožňuje prekrývajúce sa zhody; plánovač preto vypína absorpciu pre celý plán dotazu, keď je tento režim v platnosti.

Dva skip ciele, ktoré norma tiež definuje — AFTER MATCH SKIP TO FIRST var a AFTER MATCH SKIP TO LAST var — závisia od histórie na zhodu, ktorú tento patch neudržiava. V gramatike vôbec nie sú prítomné, takže parser vyvoláva všeobecnú syntaktickú chybu, ak je niektorý uvedený.

To isté platí pre SEEK, alternatívu k INITIAL v špecifikácii. Pri SEEK môže pokus o zhodu začínajúci v riadku R uspieť v ktoromkoľvek riadku od R po koniec rámca, nielen v R samotnom. Patch implementuje iba INITIAL: každá potenciálna zhoda je ukotvená v konkrétnom riadku. Parser vyvoláva chybu, ak je požadovaný SEEK. Ohraničené rámce dostávajú vlastné zaobchádzanie — keď používateľ napíše ROWS BETWEEN CURRENT ROW AND N FOLLOWING namiesto UNBOUNDED FOLLOWING, vykonávateľ skratuje akýkoľvek kontext, ktorého zhoda dosiahla hranicu, vynútením nezhody, a absorpcia sa vypína, pretože hranica láme predpoklad monotónnosti, na ktorom absorpcia spočíva.

3.5 Trojfázový motor na riadok

Driver vykonávateľa na riadok je vyvolaný okolitým mechanizmom okenných funkcií vždy, keď potrebuje vedieť, či daný riadok patrí do zhodnutého rámca. Driver nájde alebo vytvorí kontext pre aktuálnu začiatočnú pozíciu, vyhodnotí každý predikát DEFINE raz oproti aktuálnemu riadku, aby vytvoril logické pole na premennú, potom poháňa NFA dopredu o jeden riadok. Samotný krok dopredu pozostáva z troch fáz v pevnom poradí — Match, Absorb, Advance — obalených v tej istej vonkajšej slučke:

processRow(currentPos):

  # Fáza 1 — MATCH (konvergencia)
  pre každý kontext:
      ak kontext prekračuje ohraničený rámec:
          vynútiť nezhodu (finalizovať skoro)
          continue
      ak sa matchStartRow líši od
         zdieľanej vyhodnocovacej pozície:
          znovu vyhodnotiť DEFINE premenné
          závislé od match-start (§3.3)
      match(context, varMatched)

  # Fáza 2 — ABSORB
  ak je vzor absorbovateľný:
      obnoviť príznaky každého kontextu
      absorb_contexts()

  # Fáza 3 — ADVANCE (divergencia)
  pre každý kontext:
      advance(context, currentPos)

Poradie nie je štylistickou voľbou. Match musí bežať prvý, pretože absorpcia porovnáva post-match počty; spustenie Absorb pred Match by porovnávalo stavy, ktoré sa chystajú zomrieť. Advance musí bežať posledný, pretože je to jediná fáza, ktorá vytvára nové stavy — expanduje každý prežívajúci stav cez epsilon prechody, kým každá vetva nedosiahne premennú čakajúcu na ďalší riadok. Spustenie Absorb po Advance by znamenalo porovnávanie divergovaných nasledovníkov, čím by sa minul bod, v ktorom sú stavy najčistejšie porovnateľné.

Fáza 1 — Match

Match je „konvergenčná" fáza: stavy buď prežívajú s inkrementovaným počtom, alebo hynú. Jemný bod je, že pre premenné sediace v absorbovateľnom regióne Match tiež vykonáva malé množstvo postupu vpred, aby Absorb mohol porovnávať čisto. Podmienka pokrytia sa spúšťa iba v absorbovateľnom bode porovnania — v END neohraničenej skupiny — takže stavy, ktoré práve zhodili premenné v polovici iterácie (ako B vnútri (A B)+), je potrebné prejsť až k tomu bodu porovnania počas samotného Match; inak Absorb nenájde nič vhodné na porovnanie a optimalizácia sa nikdy nezapne.

match(context, varMatched):
  pre každý stav v kontexte:
      elem = pattern[state.elemIdx]
      ak elem nie je premenná:
          continue   # spracúva advance

      ak nie varMatched[elem.varId]:
          zhodiť stav   # mŕtva vetva
          continue

      state.counts[elem.depth] += 1

      # Inline postup vpred, aby
      # nasledujúca fáza mohla porovnávať
      # v prvku bodu porovnania, nie
      # v polovici iterácie.
      ak je elem in-region, ale nie
         bod porovnania,
         a dosiahol max počet,
         a elem.next je koniec skupiny:

          prejsť reťaz END:
            inkrementovať počet vonkajšej skupiny
            posunúť state.elemIdx na END
            pokračovať, kým je in-region,
              musí výjsť, a next je END
          (zastavuje sa v bode porovnania
           alebo na ešte cyklovateľnom prvku)

Prechod reťazom END je to, čo robí vnorené skupiny s pevnou dĺžkou absorbovateľnými. V ((A B){2})+, keď B dosiahne svoj max (B je {1,1}), počet vnútornej skupiny musí inkrementovať; ak ten počet tiež dosiahne svoj max — zatvárajúc vnútorné {2} — počet vonkajšej skupiny musí tiež inkrementovať a tak ďalej, kým stav nepristane na najvonkajšom bode absorpcie — END neohraničenej vonkajšej skupiny (+). Vykonanie tejto práce v Match umožňuje Absorb porovnávať oproti kontextom, ktoré už konsolidovali svoje post-iteračné počty.

Fáza 2 — Absorb

Absorb prechod prechádza kontexty od najnovšieho (chvost) k najstaršiemu (hlava). Pre každý prebiehajúci kontext, ktorý je plne absorbovateľný, skenuje dozadu starší prebiehajúci kontext, ktorý ho pokrýva, a uvoľňuje novší, ak je nájdený. Pretože sú kontexty udržiavané v poradí vytvorenia a každý riadok vytvára najviac jeden kontext, „novší" a „starší" skutočne znamená „začal neskôr" a „začal skôr."

absorb_contexts():
  pre ctx od chvosta dozadu:
      ak je ctx ukončený
         alebo má neabsorbovateľný stav:
          preskočiť
      pre starší od ctx.prev dozadu:
          ak je starší ukončený
             alebo nemá absorbovateľný stav:
              preskočiť
          ak covered(starší, ctx):
              free(ctx)
              zaznamenať dĺžku absorpcie
              break

covered(older, newer):
  pre každý stav v newer:
      elem = pattern[state.elemIdx]
      ak elem nie je bod porovnania:
          return false
      ak v older neexistuje stav s:
            rovnakým elemIdx
            a isAbsorbable
            a older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Z toho vyplývajú dve mikro-rozhodnutia. Prvým je, že kontrola pokrytia okamžite odmieta, ak akýkoľvek stav v novšom kontexte sedí inde ako v bode porovnania — porovnávanie v bodoch nesúdneho rozhodnutia by nebolo zmysluplným porovnávaním.

Druhým je asymetrický pár príznakov na každom kontexte: has-absorbable-state odpovedá „môže tento kontext absorbovať novší?" a je monotónny (môže ísť iba true→false ako stavy hynú), zatiaľ čo all-states-absorbable odpovedá „môže byť tento kontext absorbovaný?" a je dynamický (preklápa sa späť na true, keď je odstránený neabsorbovateľný stav). Oba príznaky sú kontrolované v konštantnom čase ešte pred začiatkom skenovania pokrytia, takže absorpcia platí svoju plnú cenu iba na kontextoch, ktoré majú reálnu šancu byť absorbované.

Fáza 3 — Advance

Advance je „divergenčná" fáza: každý prežívajúci stav je expandovaný cez epsilon prechody, kým každá vetva nedosiahne buď premennú čakajúcu na ďalší riadok, alebo FIN sentinel. Expanzia je do hĺbky a poradie, v ktorom sa prechádzajú súrodenecké vetvy, je to, čo robí pravidlo preferencie normy skutočne účinné — lexikálne prvá vetva je vždy pridaná ako prvá a deduplikačný krok pri vkladaní stavu ticho zahadzuje ekvivalentné neskoršie pridania.

advance(context, currentPos):
  vytiahnuť všetky aktuálne stavy;
  prebudovať ctx.states od nuly
  pre každý stav v lexikálnom poradí:
      vyčistiť visited-element bitmapu
      advance_state(state)   # DFS

      # Preferencia: keď DFS dosiahne FIN,
      # zvyšné stavy sú menej preferované
      # a môžu byť zahodené.
      ak FIN dosiahnuté a stavy zostávajú:
          uvoľniť zvyšok
          break

advance_state(state):
  prejsť cez state.elemIdx,
  rekurzia cez:
    ALT vetvy (v poradí),
    BEGIN (vstúpiť do skupiny; plus voliteľná
           skip cesta, ak min = 0),
    END (cyklus späť / výstup / fast-forward —
         pozri nižšie),
    FIN (zaznamenať matchEndRow,
         uložiť matchedState a orezať
         neskoršie kontexty vnútri
         rozsahu tohto kandidáta — pozri nižšie),
  zastavujúc sa pri každej stretnutej premennej:
      pridať stav do ctx.states
      (deduplikácia podľa elemIdx + counts)

Zaznamenanie stavu, ktorý dosiahol FIN, robí viac ako len záložku kandidátskej zhody. Pri AFTER MATCH SKIP PAST LAST ROW musí ďalšia oznámiteľná zhoda začať striktne za aktuálnou — takže v okamihu, keď je kandidát zaznamenaný, každý nasledujúci kontext, ktorého začiatočný riadok spadá do rozsahu kandidáta, je hneď orezaný, hoci kontext, ktorý zasiahol FIN, môže pokračovať v hľadaní dlhšej zhody cez greedy návrat.

Orezanie je bezpečné, pretože bez ohľadu na to, ako toto hľadanie skončí (dlhšia zhoda nahradí kandidáta, alebo kandidát zostane), všetky orezané kontexty začali vnútri rozsahu, ktorý ďalšia oznámiteľná zhoda musí preskočiť, a preto by nikdy nemohli produkovať vlastný výstup.

Toto je jeden z dvoch krokov orezania v čase FIN — druhý, opísaný skôr v tejto sekcii ako súčasť Advance, zahadzuje lexikálne podriadené stavy vnútri toho istého kontextu.

Najzákernejšia logika na prvok žije v END handleri. Keď je počet iterácií skupiny pod dolnou hranicou, beh musí cyklovať späť; keď je na alebo nad hornou hranicou, musí vystúpiť; medzi tým sú obe možnosti platné a greediness kvantifikátora rozhoduje, ktorú skúsiť ako prvú:

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

  ak count < elem.min:
      cyklovať späť do tela
      ak je elem empty-loopable:
          # nullable telo, viď §3.2
          klonovať aj fast-forward
          stav, ktorý opúšťa skupinu
          s count splneným
          (zachraňuje legitímne zhody,
           ktoré by cycle guard
           inak zabil)

  inak ak count >= elem.max:
      vynulovať counts v tejto hĺbke
      vystúpiť cez next
      (END→END: inkrementovať count
       vonkajšieho END)

  else:
      # min <= count < max: rozvetviť
      vytvoriť výstupný stav
      (počty v tejto hĺbke vynulovať)
      ak greedy:
          najprv cyklus, potom výstup
          # uprednostniť dlhšie
      inak (reluctant):
          najprv výstup
          ak výstup dosiahol FIN:
              zahodiť cyklus
              # uprednostniť kratšie
          inak cyklus druhý

Každý stav pridaný do kontextu prechádza deduplikačnou kontrolou, ktorá porovnáva jeho pozíciu a počty s existujúcim zoznamom stavov. Keďže Advance spracúva vetvy v poradí DFS, stav z prvej vetvy akejkoľvek alternácie pristane prvý — a akákoľvek neskoršia vetva produkujúca tú istú pozíciu a počty je pri vkladaní odmietnutá. Toto je presne to, o čo žiada pravidlo lexikálneho poradia z §2.4, implementované na dne behu bez osobitného prechodu.

Empty-loopable skupiny

Jemný prípad, ktorý beh musí zneškodniť, je nullable skupina — skupina, ktorej telo sa môže zhodovať s nula riadkami, pretože každý potomok tela je sám voliteľný. Vzory ako (A?)*, (A? B?)+ a (A | B*) majú všetky túto vlastnosť: v závislosti od dát môže telo dokončiť iteráciu bez spotrebovania ktoréhokoľvek riadka. To je v princípe v poriadku, ale vytvára to skutočné nebezpečenstvo pre epsilon expanziu NFA. Ak telo produkuje prázdnu zhodu, prvok END cyklí späť na BEGIN, telo opäť produkuje prázdnu zhodu, BEGIN cyklí na END atď. Bez niečoho, čo by to zastavilo, by DFS Advance nikdy neukončil.

Beh to zastavuje pomocou visited-element bitmapy (jeden bit na prvok vzoru) vyčistenej pred každou DFS expanziou stavu: hneď ako je ktorýkoľvek prvok navštívený druhýkrát v rámci tej istej expanzie, je tá cesta opustená. Cycle guard je nepodmienený a lacný, ale má vedľajší účinok — môže tiež opustiť cesty, ktoré by mali dosiahnuť dolnú hranicu cez legitímne prázdne iterácie. Vezmime (A?){2,3}, kde sa A nezhoduje s ničím v prúde riadkov:

želané správanie:
  iter 1: A? sa zhoduje s nula riadkami
          → END, count = 1 (pod min)
  iter 2: A? sa zhoduje s nula riadkami
          → END, count = 2 (spĺňa min)
  výstup s nulovou dĺžkou zhody

čo robí cycle guard sám:
  iter 1: A? preskočené → END, count = 1
          → cyklí späť na BEGIN
  iter 2: BEGIN už navštívený
          → DFS sa preruší
  count nikdy nedosiahne min
  → zhoda zlyhá (nesprávne)

Oprava je rozhodnutá v čase kompilácie a vykonávaná za behu. Vždy keď plánovač vidí skupinu, ktorej telo je nullable, označuje prvok END tej skupiny ako empty-loopable. Za behu, keď sa END handler chystá cyklovať späť, pretože počet iterácií je stále pod dolnou hranicou, empty-loop značka mu hovorí, aby naklonoval ďalší fast-forward stav vedľa normálnej cesty cyklenia späť:

advance_end (count pod min):

  primárna cesta:
    cyklovať späť do tela
    (necháva otvorené dvere pre skutočnú,
     neprázdnu zhodu v ďalšej
     iterácii)

  ak je elem empty-loopable:
    fast-forward cesta:
      vynulovať počet v tejto hĺbke
      vystúpiť zo skupiny cez next,
      zaobchádzajúc s zostávajúcimi
      požadovanými iteráciami ako prázdnymi zhodami

Dve cesty hrajú doplnkové úlohy. Primárny cyklus späť je to, čo zachytáva prípad, kde telo má neskôr stále skutočné zhody na produkciu — napríklad v (A?){2,3} nasledovanom dátami, kde sa A zhoduje iba v neskorších riadkoch, cyklus späť je to, čo umožňuje druhej a tretej iterácii nájsť neprázdne zhody. Fast-forward je to, čo zachytáva prípad, kde telo nikdy nič neprodukuje: obchádza cycle guard úplným výstupom zo skupiny, deklarujúc „zvyšok požadovaných iterácií je prázdny," a umožňuje zhode uspieť s telom nulovej dĺžky. Oba stavy sa pridajú do kontextu; ktorýkoľvek z nich sa úspešne rozšíri, ten vyhráva, a deduplikačná kontrola v čase vkladania zabraňuje ktorejkoľvek ceste vyplodiť viac stavov, ako je jej podiel.

Okrem cycle guardu jeden ďalší trik pri štartovaní rieši dvojznačnosť výsledkov nula-riadkov na úplnom začiatku kontextu. Krok vytvorenia kontextu v každom potenciálnom začiatočnom riadku spúšťa počiatočný advance cez epsilon prechody pred spotrebovaním ktoréhokoľvek riadka, používajúc pozíciu o jeden riadok pred skutočným začiatkom. Akákoľvek cesta, ktorá dosiahne FIN sentinel iba cez epsilon prechody — bez spotrebovania riadka — preto produkuje koncovú pozíciu menšiu ako začiatočná pozícia; tá súradnica záporného rozsahu, kombinovaná s tým, či bol FIN skutočne dosiahnutý, kóduje rozdiel medzi prázdnou zhodou (zhoda dĺžky 0 prijatá) a nezhodným začiatkom bez potreby osobitného príznaku.

3.6 Ako priestor stavov zostáva ohraničený

Linearita behu nie je výsledkom jedinej optimalizácie. Je kumulatívnym efektom vrstvenej sady orezávacích pravidiel, každé z nich zachytáva inú príčinu rastu priestoru stavov v inom bode cyklu na riadok. Niektoré sú rozhodnuté v čase kompilácie a iba konzultované za behu; iné sa spúšťajú dynamicky. Niektoré zabíjajú jednotlivé stavy; iné zabíjajú celé kontexty. Sekcie vyššie predstavili každú z nich v kontexte; tabuľka nižšie ich kladie na jednu stranu.

Zlyhaný predikát Match

Stavy premenných, ktorých DEFINE bolo na aktuálnom riadku vyhodnotené ako false — mŕtve vetvy.

Inline end-chain advance Match

Premenné, ktoré dosiahli svoj max počet a inak by stav opustili v polovici iterácie; posunuté cez konce skupín s pevnou dĺžkou, aby absorpcia mohla porovnávať v správnom bode.

Absorpcia kontextu Absorb

Novšie kontexty, ktorých každý stav je pokrytý stavom staršieho kontextu s vyšším počtom — pozri §2.5 pre konceptuálne pravidlo, §3.2 pre vhodnosť v čase kompilácie, §3.5 pre kontrolu na pár.

Deduplikácia stavov Advance

Stavy dosiahnuté cez rôzne DFS vetvy, ktoré skončia na rovnakej pozícii s rovnakými počtami — prežíva iba prvý (lexikálne najskorší); neskoršie ekvivalenty sú ticho zahodené, čo je tiež spôsob, akým sa presadzuje preferencia (§2.4).

FIN skoré ukončenie (v rámci kontextu) Advance

Stavy stále čakajúce v DFS fronte, keď jedna vetva dosiahne FIN — podľa lexikálneho poradia sú všetky zostávajúce stavy menej preferované a môžu byť okamžite zahodené.

Orezanie kandidátskej zhody (naprieč kontextami) Pri FIN

Iné kontexty, ktorých začiatočný riadok spadá do rozsahu kandidátskej zhody — kontext, ktorý zasiahol FIN, môže stále hľadať dlhšiu zhodu (greedy návrat), ale pri AFTER MATCH SKIP PAST LAST ROW už žiadny kontext vnútri rozsahu kandidáta nemôže produkovať oznámiteľný výstup bez ohľadu na to, ako toto hľadanie skončí, a je hneď orezaný.

Cycle guard Advance

Epsilon expanzie, ktoré opätovne navštevujú ten istý prvok vzoru v rámci toho istého DFS — inak by v nullable skupinách cyklili navždy.

Empty-loop fast-forward Advance

Legitímne zhody prázdnych iterácií, ktoré by cycle guard v nullable skupinách zabil — obchádza cyklus výstupom zo skupiny so zostávajúcimi požadovanými iteráciami deklarovanými ako prázdne.

Cutoff ohraničeného rámca Match

Kontexty, ktorých zhoda dosiahla používateľom určenú hornú hranicu rámca — vynútené k nezhode, aby sa nemohli rozšíriť za ňu (§3.4).

Čítanie záznamov podľa ich fázového odznaku stopuje životnosť kontextu: orezanie sa spúšťa v každom riadku cez tri hlavné fázy (Match, Absorb, Advance) a opäť pri dokončení zhody (Pri FIN). Čítanie opisov namiesto toho zoskupuje pravidlá podľa toho, na čo cieľujú: mŕtve vetvy, redundantné kontexty, ekvivalentné stavy, nekonečné cykly a preceňovanie za používateľom uložené hranice.

Žiadne jediné pravidlo samo by nestačilo. Samotný cycle guard by zabíjal legitímne zhody v nullable skupinách; samotný empty-loop fast-forward by nezastavil nekonečné epsilon cykly; samotná absorpcia by nadmerne konsolidovala, keď DEFINE odkazuje na match-start; samotná deduplikácia by neodstránila redundantné kontexty, iba redundantné stavy. Beh zostáva lineárny v prípadoch, ktoré sú dôležité — PATTERN (A+ B+ C+ D) na 100 000 riadkoch, benchmark panela ③ posteru — iba preto, že každá vrstva zachytáva to, čo vrstvy nad ňou vynechávajú.

3.7 Výstup EXPLAIN

EXPLAIN ANALYZE na dotaze s RPR vystavuje štatistiky na úrovni NFA, ktoré nie sú prítomné pre obyčajné okenné funkcie. Tri skupiny čítačov sú vydávané spolu s okenným operátorom:

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
  (iba keď dotaz používa FIRST,
   PREV(FIRST(...)), alebo NEXT(FIRST(...)))

Peak a total sú priamou inštrumentáciou behu: koľko stavov bolo niekedy súčasne živých, koľko bolo vytvorených počas životnosti dotazu a koľko bolo zlúčených deduplikáciou. Histogramy dĺžok zhôd oddeľujú štyri výsledky — úspešné zhody, zlyhané pokusy o zhodu, absorbované kontexty a kontexty, ktoré boli orezané (skipped) bez vyhodnotenia — a ich reportovanie s min/max/avg robí výkonnostné patológie viditeľnými na prvý pohľad: zdravý beh ukazuje väčšinu kontextov ako buď zhodené, alebo absorbované, s malými dĺžkami nezhody.

Dva čítače Nav Mark reportujú rozpočet uchovávania tuplestoru, ktorý §3.3 odvodzuje v čase kompilácie. Lookback je najhlbší dosah dozadu cez PREV, LAST s posunom a zložené formy s vnútorným LAST; Lookahead je najhlbší dosah dopredu (alebo dozadu, ak je záporný) meraný od začiatku zhody najstaršieho živého kontextu, prispievaný FIRST a zloženými formami s vnútorným FIRST.

Každý čítač sa tlačí ako pevné celé číslo, keď je posun konštantou, „runtime", keď je posun nekonštantným výrazom, ktorý sa musí vyhodnotiť pri každom volaní, a „retain all", keď beh potrebuje neohraničený rozpočet. Lookahead sa vydáva iba vtedy, keď dotaz skutočne používa navigáciu relatívnu k začiatku zhody.

Spolu tieto čítače umožňujú ladiť výkon RPR bez pripájania gdb k backendu.

Okrem čítačov EXPLAIN tiež verne reprodukuje pôvodné klauzuly PATTERN a DEFINE, vrátane neochotných kvantifikátorov, opakovania skupín a možnosti AFTER MATCH SKIP. Implementácia sa snaží, aby tento round-trip bol stabilný, aby pg_dump a pg_upgrade mohli zachovať objekty RPR bez sémantického posunu — regresná sada pod rpr_explain to overuje prípad od prípadu (pozri §4).

§4. Testy — mapa pokrytia

Patch sa dodáva s piatimi regresnými sadami, ktoré spolu cvičia každú vrstvu opísanú v §3 — približne 13 000 riadkov SQL, každá sada zameraná na iný problém. Rozdelenie je zámerné: udržiavanie záležitostí parsera, správnosti behu, interakcií plánovača a formátovania výstupu v oddelených súboroch uľahčuje lokalizovanie zlyhaní a zabraňuje, aby nesúvisiaca zmena v jednej vrstve náhodou neznehodnotila testy v inej. Päť sád je:

rpr

End-to-end sémantika dotazov — realistické okenné scenáre na syntetických akciových dátach (V-tvar, W-tvar, po sebe idúce vzostupy, obraty).

rpr_base

Vrstva parsera — prijatie kľúčových slov, syntaktické tvary, kvantifikátory, parsovanie navigácie, chybové správy a stabilita round-tripu pg_dump/pg_upgrade.

rpr_nfa

NFA runtime — trojfázová slučka, absorpcia v každom absorbovateľnom tvare a hraničné prípady životného cyklu kontextu.

rpr_explain

Formátovanie výstupu — NFA štatistiky, deparse vzoru, citovanie identifikátorov, stabilita formátu cez reload.

rpr_integration

Interakcie plánovača — strážcovia, ktorí zabraňujú nesúvisiacim okenným optimalizáciám korumpovať sémantiku RPR.

4.1 rpr — end-to-end scenáre

Scenárová sada je verejnou tvárou testovacej sady: používa syntetický dataset cien akcií s približne 1 600 riadkami a spúšťa proti nemu realistické dotazy — obnovenie V-tvaru, W-tvar (dvojité dno), po sebe idúce vzostupy a poklesy, obratové vzory, multi-symbolové partície. Je to jediná sada, kde sa vstupy a výstupy čítajú ako dotazy, ktoré by používateľ skutočne napísal; ostatné sú zámerne redukcionistické, zamerané na jednu vrstvu naraz.

Pretože tieto dotazy kombinujú každú vrstvu (parser, plánovač, vykonávateľ, EXPLAIN), jediné zlyhanie v rpr vám zriedka povie, kde chyba žije. Štyri nasledujúce sady sú bisekciou: zlyhanie v rpr plus prechádzajúce rpr_base vylučuje parser; plus prechádzajúce rpr_nfa ho zužuje na scenárovo špecifické tvary dát; plus prechádzajúce rpr_integration vylučuje interferenciu plánovača; a akýkoľvek deparse posun sa objaví v rpr_explain.

4.2 rpr_base — povrch parsera

Základná sada je najväčšia a je najväčšia z dôvodu: je zodpovedná za dokázanie, že každý legálny kus syntaxe v §1.2 sa skutočne parsuje, každý nelegálny kus v §1.3 je odmietnutý s užitočnou chybou a každá akceptovaná forma prežíva serializačný round-trip. Hlavná časť je tvarovaná ako malé zamerané úryvky — jeden na syntaktickú vlastnosť — namiesto dlhých realistických dotazov, pretože cieľom je pokrytie, nie scenárová realistickosť.

Serializačné testy si zaslúžia osobitnú pozornosť. Objekty RPR (pohľady, materializované pohľady, výstup pg_dump) musia prejsť round-trip cez reprezentáciu katalógu bez sémantického posunu, vrátane jemností ako neochotný príznak na kvantifikátore alebo presná forma zloženého navigačného výrazu. Malá sada serializačne špecifických objektov (pohľady rpr_serial_v* a ich podporné tabuľky) je zámerne ponechaná na mieste na konci behu, takže okolitá regresná infraštruktúra ich môže zdvihnúť a cvičiť pg_dump a pg_upgrade proti nim. Zvyšok testovacieho lešenia je zhodený ako obvykle. Chyby zachytené týmto spôsobom (ako strata neochotného príznaku cez deparse a re-parse) sa objavia iba vtedy, keď je round-trip cvičený od konca po koniec.

4.3 rpr_nfa — runtime motor

Toto je sada, ktorá cvičí každý mechanizmus opísaný v §3.5 a §3.6. Jej testy sledujú konzistentný vzor: vstupná tabuľka, ktorej riadky sú explicitné logické polia deklarujúce, ktoré premenné DEFINE sa zhodujú v každom riadku, spárovaná so vzorom, ktorý skúma špecifické runtime správanie. Idióm logického poľa odpája runtime test od mechanizmu vyhodnocovania DEFINE — testuje sa „za predpokladu, že sa tieto premenné tu zhodujú, produkuje NFA slučka očakávaný rozsah zhody?" namiesto „vypočítava vyhodnocovač DEFINE výrazov správne tieto logické hodnoty?" Vyhodnocovač DEFINE sa testuje inde (rpr_base pre parsovanie, rpr pre end-to-end správanie).

Typický testovací fixture vyzerá takto — stĺpec polí mien premenných, kde každý záznam hovorí, ktoré premenné DEFINE sa spustia v tom riadku, a vzor, ktorého klauzuly DEFINE testujú tieto mená priamo:

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

Čítanie stĺpca poľa nadol je čítaním testovacieho scenára priamo. Riadky 2 a 3 nesú obe mená — A aj B sa tam spúšťajú, takže NFA má skutočnú voľbu, kde prepnúť z A-vetvy na B-vetvu. Očakávaná zhoda (A v riadkoch 1–3 nasledovaná B v riadku 4, pri greedy preferencii normy) je fixovaná samotnými týmito príznakmi, bez vyhodnocovania výrazov akéhokoľvek významu tu — = ANY je len triviálnou vrstvou, ktorá vystavuje stĺpec poľa pre DEFINE, nie tým, čo test cvičí. Napísanie toho istého scenára s číselným predikátom (price > PREV(price) a podobne) by spojilo NFA test so správaním vyhodnocovača predikátov; idióm poľa udržiava obe čisto oddelené a zlyhanie tu ukazuje priamo na NFA slučku.

Pokrytie absorpcie je obzvlášť dôkladné, pretože absorpcia je optimalizáciou najpravdepodobnejšou na tiché produkovanie nesprávnych odpovedí, ak sa zapne, keď by nemala. Testy pokrývajú každý tvar z analýzy prípadov v §3.2:

• jednoduchá neohraničená premenná (A+) — kanonický kolaps N na 1;
• skupiny s pevnou dĺžkou ((A B)+, (A B{2})+, trojúrovňovo vnorené ((A (B C){2}){2})+);
• vedúca neohraničená premenná s pevným sufixom (A+ B) — iba vedúce A+ nesie príznaky absorpcie, sufix nie;
• absorpcia na vetvu vnútri alternácie (B+ C | B+ D);
• viacero neohraničených premenných (A+ B+) — iba vedúca je absorbovateľná;
• neochotné kvantifikátory (A+?) — overené, že sú vylúčené z absorpcie;
• nevedúce neohraničené (A B+) — overené, že sú vylúčené.

Okrem absorpcie sada pokrýva životný cyklus kontextu: prekrývajúce sa kontexty pri AFTER MATCH SKIP TO NEXT ROW, čistenie zlyhaných kontextov uprostred prúdu, finalizácia neúplných kontextov na konci partície a kontexty stretnuté po tom, čo už bola kandidátska zhoda zaznamenaná vo vedúcom kontexte. Každé z nich sa mapuje na konkrétne orezávacie pravidlo v §3.6 a testy sú napísané tak, aby hlasno zlyhali, ak pravidlo zlyhá (buď ponechaním redundantných kontextov pri živote, alebo zabitím kontextu, ktorý mal produkovať výstup).

4.4 rpr_explain — stabilita výstupu

Výstup EXPLAIN je súčasťou kontraktu smerom k používateľovi — nástroje tretích strán (psql autocompletion, monitorovacie dashboardy, log scrapery) ho parsujú a zmeny, ktoré vyzerajú kozmeticky, ich môžu zlomiť. Sada rpr_explain overuje tri veci:

• NFA čítače sa objavujú na správnom mieste — štatistiky na WindowAgg (peak/total/merged states, peak/total/pruned contexts, dĺžkové histogramy pre matched/mismatched/absorbed/skipped, Nav Mark Lookback a — keď sa používa navigácia relatívna k začiatku zhody — Nav Mark Lookahead) sa všetky zobrazujú pod EXPLAIN ANALYZE s dokumentovanými označeniami.
• Vzory sa správne deparsujú — každý tvar kvantifikátora, vrátane neochotných variantov a ohraničených foriem; každá alternácia; každá skupina; každá forma AFTER MATCH SKIP; INITIAL; navigačné volania s posunmi; zložená navigácia. Deparsovaný text musí prejsť round-trip späť cez parser nezmenený.
• Citovanie identifikátorov je správne — premenné vzoru a DEFINE výrazy sú vydávané s tými istými pravidlami citovania ako bežné SQL identifikátory, takže nezvyčajné mená premenných nezlomia výstup pg_dump.

Ako rpr_base, táto sada zámerne ponecháva svoje objekty na mieste na konci behu, takže pokrytie pg_dump a pg_upgrade sa rozširuje aj na artefakty na strane explain.

4.5 rpr_integration — interakcie plánovača

Plánovač PostgreSQL má mnoho optimalizácií, ktoré pracujú na okenných dotazoch — kanonikalizácia rámca, pushdown run-condition, deduplikácia identických okien, projekcia nepoužitého výstupu, inverzné prechody pohyblivých agregátov — a každá z nich bola navrhnutá bez RPR na mysli. Väčšina z nich nie je bezpečná na uplatnenie, keď okno má klauzulu PATTERN: rámec je súčasťou kontraktu zhody, zhodnutý výstup už nie je monotónny žiadnym zrejmým spôsobom a dve okná s tou istou špec, ale rozdielnymi DEFINE produkujú skutočne rozdielne výsledky. Integračná sada overuje, že každá z týchto optimalizácií je správne vypnutá alebo obídená pre RPR okná:

Kanonikalizácia rámca

Plánovač normálne prepisuje ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING na ROWS UNBOUNDED PRECEDING pre monotónne agregáty. Rámec RPR je rozsah zhody, nie agregačné okno, a musí zostať doslovný.

Pushdown run-condition

Monotónny filter WHERE na výstupe okennej funkcie môže byť normálne presunutý do okenného operátora ako stop-podmienka. Pre RPR by toto predčasne ukončilo zhodovanie vzoru, možno odrezaním zhôd v polovici rozšírenia.

Deduplikácia okien (RPR vs ne-RPR)

Dve okná s identickým ORDER BY a rámcom by boli normálne zlúčené do jedného. RPR okno a ne-RPR okno nikdy nemôžu zdieľať stav, pretože RPR strana nesie výsledky zhody.

Deduplikácia okien (rôzne DEFINE)

Dve RPR okná s tým istým PATTERN, ale rôznymi klauzulami DEFINE, produkujú rôzne zhody a musia zostať odlišné, aj keď je ich štrukturálny tvar identický.

Projekcia nepoužitého výstupu

Aj keď okolitý dotaz nikdy nečíta výstup okna na riadok, RPR okno nemožno odstrániť: vedľajšie účinky zhodovača vzorov (ktoré riadky sú vnútri ktorej zhody) napájajú výpočty zredukovaného rámca inde v pláne.

Inverzné prechody pohyblivých agregátov

Okenné agregáty s inverznou prechodovou funkciou môžu byť normálne vyhodnocované inkrementálne, ako sa rámec posúva. Zredukovaný rámec RPR nie je posuvným oknom; cesta inverzného prechodu by produkovala nesprávne výsledky.

Vzor naprieč týmito testami je rovnaký: každý poskytuje ne-RPR baseline, ktorý spúšťa optimalizáciu (a overuje, že EXPLAIN ukazuje jej aplikáciu), potom spúšťa RPR dotaz štrukturálne podobného tvaru a overuje, že optimalizácia nie je aplikovaná. Obe polovice spolu dokazujú, že strážca v plánovači robí skutočnú prácu, neschvaľuje každý dotaz bez skutočného overenia.

Táto sada je tiež dôvodom, prečo je §3.4 krátky. Mechanizmy „hraníc zhody" — zredukovaný rámec, SKIP, INITIAL, cutoff ohraničeného rámca — sú testované operačne inde; čo rpr_integration overuje, je, že žiadna iná optimizačná etapa s nimi pri prechode nemanipuluje. Prechádzajúce rpr_integration je to, čo umožňuje zvyšku sád dôverovať, že ich vstupy dosahujú vykonávateľa nedotknuté.