2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition do hĺbky

Sprievodca normou ISO/IEC 19075-5 · SQL R020 v PostgreSQL — čo sa implementovalo, čo ešte zostáva, a ako to v skutočnosti beží.

Sprievodca k posteru vystavenému na PGConf.dev 2026.
Preletite normu, prejdite riešenými príkladmi, preskúmajte dizajn a potom riaďte živý NFA simulátor vlastnými vzormi.
Diskusia: vlákno pgsql-hackers · najnovší patch (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

Vopred preložené AI — možné chyby.

§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 majú značnú časť syntaxe a sémantiky spoločnú (19075-5 uvádza v §6.3.3 niekoľko rozdielov špecifických pre R020), 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 klauzúl do špecifikácie okna, ktorej rámec je ROWS BETWEEN CURRENT ROW AND …: PATTERN opisuje regulárny výraz nad pomenovanými premennými vzoru, DEFINE poskytuje logický predikát, ktorý identifikuje každú premennú, a voliteľné AFTER MATCH SKIP (predvolene PAST LAST ROW) 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; najviac 240 rôznych premenných vzoru.
Rámec okna
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING alebo ROWS BETWEEN CURRENT ROW AND n FOLLOWING s n ≥ 1 (19075-5 §6.10.2); akýkoľvek iný rámec je odmietnutý a EXCLUDE NO OTHERS je jediné akceptované vylúčenie.
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 sa vyhodnocuje 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.
Navigačné názvy
PREV, NEXT, FIRST a LAST zapísané ako nekvalifikované volania vnútri DEFINE vždy znamenajú navigáciu; používateľská funkcia rovnakého mena tam musí byť kvalifikovaná schémou.
Navigačné argumenty
Pri PREV, NEXT, FIRST a LAST musí vnútorný argument obsahovať aspoň jeden odkaz na stĺpec a posun musí byť konštanta v čase behu.
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 FIRST var a AFTER MATCH SKIP TO [LAST] var (holé SKIP TO var znamená SKIP TO LAST var). Tieto tiež závisia od histórie zhody, pretože vykonávateľ musí byť schopný ukázať na riadok namapovaný na danú premennú 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 {- … -}, operátor PERMUTE necitlivý na poradie a agregačné funkcie a poddotazy v DEFINE, oboje v súčasnosti odmietané (agregát kvalifikovaný premennou by tiež potreboval históriu zhody).

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ť v ktoromkoľvek riadku od aktuálneho riadka po koniec úplného rámca okna (oproti INITIAL).
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 ALL ROWS PER MATCH. Táto možnosť sa na okná nevzťahuje (19075-5 §6.3.3 (4)), takže v okne je syntax povolená (§6.13), ale nemá žiadny výstup, na ktorý by pôsobila.
Regex: ()
Prázdny vzor — zhoduje sa s prázdnou postupnosťou.
PERMUTE(...)
Zhodovanie necitlivé na poradie cez vymenované premenné. Kľúčové slovo je rozpoznané a odmietnuté („PERMUTE is not supported"); permute zostáva použiteľné ako názov premennej vzoru.
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; agregát kvalifikovaný premennou, ako AVG(B.Price), závisí od tej istej histórie zhody, akú vyžadujú MEASURES/CLASSIFIER(), zatiaľ čo nekvalifikovaný pokrýva všetky doterajšie riadky zhody.
Poddotazy v DEFINE
Každý poddotaz v DEFINE je odmietnutý. Norma povoľuje taký, ktorý nevykonáva rozpoznávanie vzorov riadkov a neodkazuje na žiadnu premennú vzoru riadkov; patch zatiaľ odmieta viac, než musí.

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 (patch ide ďalej a odmieta všetky poddotazy v DEFINE, ako je uvedené vyššie); a RPR sa nesmie použiť vnútri rekurzívneho dotazu. Patch vynucuje pravidlo o vonkajších odkazoch („cannot use outer query column in DEFINE clause") a pravidlo o rekurzii, to druhé pre každý prvok klauzuly WITH RECURSIVE. Odmieta tiež volatilné funkcie a odkazy na celý riadok v DEFINE.

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

Pôvod. Zoznamy implementovaných a neimplementovaných vlastností v tejto sekcii odrážajú aktuálny stav série patchov — konkrétne v55 (2026-11-17).

§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 piatimi riešenými príkladmi: jednou zhodou (pohyb NFA), alternáciou, absorpciou kontextu v jednoduchom prípade a dvoma prípadmi, keď je absorpcia vypnutá.

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.

Text regex vs row pattern: a single state advances per symbol, while multiple DEFINE predicates can match a row in parallel. TEXT REGEX single state advances through symbols A B C one symbol per position · one transition ROW PATTERN one row, multiple predicates evaluated row price = 150 · volume = 2000 A ✓ price > 100 B ✓ volume > 1000 C ✗ price > 200 two predicates true · two states stay alive
Textový regex sa zlučuje do jedného stavu na symbol; riadok môže súčasne spĺňať viacero predikátov DEFINE, takže viaceré stavy zostávajú paralelne živé.

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 (predvolene n = 1). Predbežný pohľad dopredu; v okennej forme nezvyčajný, pretože okno je monotónne.
FIRST(expr [, n])
Riadok n riadkov za prvým riadkom aktuálnej zhody (predvolene n = 0, samotný prvý riadok). „Porovnaj s riadkom, ktorý začal túto zhodu."
LAST(expr [, n])
Riadok n riadkov pred posledným zhodnutým riadkom (predvolene n = 0). Vnútri DEFINE je posledným zhodnutým riadkom aktuálny riadok, takže LAST(price) číta aktuálny riadok.

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 riadka, ktorý číta FIRST(expr, n) (predvolene n = 0, m = 1). „Aká bola hodnota tesne pred začiatkom tejto zhody?"
NEXT(FIRST(expr [, n]) [, m])
Krok m riadkov vpred od riadka, ktorý číta FIRST(expr, n). Siaha hlbšie do zhody bez závislosti od aktuálneho riadka.
PREV(LAST(expr [, n]) [, m])
Krok m riadkov späť od riadka, ktorý číta LAST(expr, n). „Porovnaj s riadkom krátko pred najnovším zhodnutým riadkom."
NEXT(LAST(expr [, n]) [, m])
Krok m riadkov vpred od riadka, ktorý číta LAST(expr, n).

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. Samotné PREV a NEXT sú relatívne k aktuálnemu riadku a sú vždy bezpečné; FIRST a varianty LAST s posunom, samostatne alebo vnútri zloženého PREV/NEXT, sú relatívne k hraniciam zhody, čo interaguje s absorpciou kontextu: plánovač potom vypne absorpciu pre celý vzor. Mechanizmus tejto interakcie je témou §2.6.

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

Cieľ tohto príkladuUkázať riadok po riadku evolúciu stavov NFA na jednoduchom, neabsorbujúcom vzore. Stopa sleduje kontext začatý v riadku 0; kontexty začaté v riadkoch 1–4 bežia popri ňom a SKIP PAST LAST ROW ich zahodí, len čo je jeho zhoda zaznamenaná.
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:

RiadokCenaPravdivé premennéAkcia
0100STARTNový kontext. START sa zhoduje a okamžite končí (max=1); stav postupuje na UP+.
1110START, UPUP sa zhoduje. Postup sa rozvetvuje: jeden stav cyklí na UP, ďalší prechádza na DOWN+.
2120START, UPUP sa zhoduje v cykliacom stave a opäť sa rozvetvuje. Stav DOWN z riadka 1 hynie (120 ≮ 110).
3115START, DOWNUP zlyháva v cykliacom stave a hynie. Stav DOWN z riadka 2 sa zhoduje. Postup sa rozvetvuje: cyklus na DOWN a prechod na #FIN — zaznamená sa kandidát na zhodu cez riadky 0–3.
4108START, DOWNDOWN sa zhoduje v cykliacom stave a znova sa rozvetvuje; nový FIN kandidát cez riadky 0–4 nahrádza kratší.
5130START, UPCykliaci stav DOWN zlyháva (130 ≮ 108). Keďže v tomto kontexte nezostal žiadny živý stav, zaznamenaný kandidát (riadky 0–4) sa finalizuje ako zhoda. Ďalší pokus začína v riadku 5; START sa zhoduje, ale partícia skončí skôr, ako príde akékoľvek UP.

Kľúčový bod: v riadku 3 riadok spĺňa START (vždy pravdivé) aj DOWN, ale START má význam iba pre kontext začínajúci v riadku 3; v tomto kontexte cykliaci stav UP hynie a postúpi iba stav čakajúci na 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 posledný FIN kandidát (riadky 0–4) — vytvorený, keď DOWN ukončil v riadku 4, a nahrádzajúci kandidáta z riadka 3 — 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:

RiadokCenastart_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

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

Cieľ tohto príkladuUkázať, ako jediný kontext nesie viacero paralelných stavov, keď jeden riadok spĺňa viac ako jednu alternatívu — a ako norma prerušuje rovnosti.

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 v poradí vzoru, skoršiu vetvu najprv.

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. Oba potom postúpia k DONE, kde sa stretnú.

RiadokPravdivé premennéŽivé stavy
RUP, HIGHStav A (vetva UP) a Stav B (vetva HIGH) oba postúpia k DONE s rovnakými počtami; B je duplikátom A a je zahodený
R+1DONEStav A sa zhoduje s DONE a dosiahne #FIN

V termínoch normy obe vetvy produkujú zhodu rovnakej dĺžky cez tie isté riadky, čím vznikajú 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. Vykonávateľ to vynucuje v riadku R, nie pri FIN: stav vetvy UP pridá ako prvý, takže nfa_append_state_unique() ho ponechá a identický stav vetvy HIGH zahodí.

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)

Cieľ tohto príkladuUkázať, prečo sa naivná celková práca so stavmi O(n²) stáva pri absorpcii O(n), s O(1) živými kontextmi.

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

RiadokNaivné kontextyS absorpciou
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 absorbovaný
2C1[A:3], C2[A:2], C3[A:1]C1[A:3]
3C1[A:4], C2[A:3], C3[A:2], C4[A:1]C1[A:4]
4päť kontextovC1[A:5]

Živé kontexty klesajú z O(n) na O(1), takže celkový súčet za partíciu klesá z O(n²) na O(n). Pravidlo absorpcie, ktoré ospravedlňuje vyhodenie, je priamočiare, keď je kvantifikátor neohraničený:

Pravidlo absorpcie. Dva kontexty, ktorých živý stav je na rovnakom prvku vzoru, kde má starší kontext počet ≥ ako novší, majú identické budúcnosti pri neohraničenom kvantifikátore. Novší kontext sa môže vyhodiť; akúkoľvek zhodu, ktorú by napokon našiel, starší kontext nájde dlhšiu alebo rovnakú.

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

DeňCenaC1 — začiatok ut
price > PREV(price)
C2 — začiatok st
price > PREV(price)
Po$100——
Ut$108$108 > $100 ✓ (práve začal)—
St$112$112 > $108 ✓$112 > $108 ✓ (práve začal)
Št$116$116 > $112 ✓$116 > $112 ✓
Pi$110$110 > $116 ✗ — finalizovať$110 > $116 ✗ — finalizovať
Rovnaký osud Každý zdieľaný riadok C1 a C2 vyhodnocuje rovnaké výrazy a produkuje rovnaké výsledky — a v piatok hynú pri tom istom porovnaní. Akúkoľvek budúcnosť má C2, má aj C1. Absorpcia C2 do C1 nič neodhodí.

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

Cieľ tohto príkladuUkázať, čo sa zmení, keď DEFINE odkazuje na FIRST — pravidlo absorpcie už neplatí a plánovač pre tento vzor vypína absorpciu.

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

DeňCenaC1 — začiatok po
FIRST = $100
price < $100 + 10
C2 — začiatok ut
FIRST = $108
price < $108 + 10
Po$100$100 < $110 ✓—
Ut$108$108 < $110 ✓$108 < $118 ✓ (práve začal)
St$112$112 < $110 ✗ — finalizovať Po–Ut$112 < $118 ✓
Št$116—$116 < $118 ✓
Pi$110—$110 < $118 ✓ (stále beží)
Rozdielne osudy C1 hynie v stredu s dvojdňovým behom (Po–Ut); C2 by sám osebe bežal ďalej až do piatka. Tie isté ceny, tá istá forma otázky — ale rozdielne stropy odvodené od ich vlastných začiatkov zhody. V ten istý deň dva kontexty dospeli k opačným záverom.

Pri absorpcii by bol C2 v utorok zlúčený do C1 — zlúčený kontext si ponecháva iba strop C1 ($110), takže odlišný pohľad C2 (strop $118, štvordňový beh do piatka) budúcnosť C1 nepokrýva. V tomto konkrétnom týždni sa výstup náhodou nezmení: C1 zaznamená Po–Ut, C2 začal vnútri tejto zhody a SKIP PAST LAST ROW ho zahodí, a ďalší pokus začína v stredu s vlastným stropom ($122) a zhoduje sa St–Pi. Vo všeobecnosti však výsledok DEFINE skoršieho kontextu už nezahŕňa výsledok neskoršieho, takže porovnanie počtov, na ktorom absorpcia stojí, je neplatné. 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 nižšie rozširuje pravý dolný panel posteru („② Navigácia") o zložené formy a zhŕňa, ktoré navigačné formy vytvárajú závislosť od začiatku zhody:

NavigáciaZáv. od začiatku zhodyAbsorbovateľná?
PREV, NEXTžiadnaáno
LAST (bez posunu)žiadnaáno
LAST s posunomkontrola hranícnie
FIRST (akýkoľvek)priamanie
Zložená (vnútorný FIRST)priamanie
Zložená (vnútorný LAST, bez posunu)žiadnaáno
Zložená (vnútorný LAST s posunom)kontrola hranícnie

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 zaručene nepokrýva, takže bezpečnosť vyhodenia ktoréhokoľvek z nich už nemožno preukázať.

Plánovač toto rozlíšenie deteguje v čase kompilácie a zapína alebo vypína absorpciu pre celý vzor; keď je vypnutá, beh platí viac-kontextovú cenu. Benchmark posteru v paneli ③ nepoužíva FIRST, takže absorpcia zostáva zapnutá, a preto PostgreSQL zostáva lineárny v prípadoch úspechu aj zlyhania.

Čí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ú približne O(n), keď je zhoda potvrdená, a PostgreSQL vedie približne 16× až 33× (údaje Trino už vylučujú štart JVM).

Na neúspešnom vzore (A+ B+ C+ E) Trino, ktorému zrejme chýba absorpcia, prenasleduje každý potenciálny začiatok zhody a degraduje ešte rýchlejšie ako O(n²) (približne 56× viac času pri 5× viac riadkoch); 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

Cieľ tohto príkladuUkázať druhý spôsob, akým môže absorpcia zlyhať: nie preto, že sa predikát rozvetví, ale preto, že výstupná sémantika vyžaduje, aby bola každá zhoda reportovaná osobitne.

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.

RiadokSKIP PAST LAST ROWSKIP TO NEXT ROW
0zhoda začína; riadky 0–4 budú jedinou zhodouzhoda začína v riadku 0
1(vnútri zhody 0)zhoda začína v riadku 1 — musí zostať pri živote
2(vnútri zhody 0)zhoda začína v riadku 2 — musí zostať pri živote
3(vnútri zhody 0)zhoda začína v riadku 3 — musí zostať pri živote
4zhoda 0 sa finalizuje (riadky 0–4)finalizuje sa päť zhôd: 0–4, 1–4, 2–4, 3–4, 4–4
Iný výstup, iné osudy Pri AFTER MATCH SKIP TO NEXT ROW je každý neskôr-začínajúci kontext vlastným výstupným riadkom. Dva kontexty na rovnakom prvku vzoru už nie sú redundantné — sú oba požadované výstupy a vyhodenie jedného by ticho zahodilo zhodu, o ktorú používateľ požiadal.

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 ukazuje dva spôsoby, ktorými sémantika dotazu vylučuje absorpciu:

Strana dát · §2.6
Predikát sa vyhodnocuje pre každý kontext inak.
Spúšťané FIRST alebo posunovým LAST v DEFINE.
Strana výstupu · §2.7
Výstup vyžaduje každý začiatok zhody ako samostatný riadok.
Spúšťané AFTER MATCH SKIP TO NEXT ROW.

Ktorákoľvek podmienka stačí na vypnutie absorpcie pre celý vzor, a rovnako aj rámec, ktorý nekončí na UNBOUNDED FOLLOWING. Keď neplatí žiadna z nich — predvolené AFTER MATCH SKIP PAST LAST ROW, neohraničený koniec rámca a podmienky DEFINE, ktoré používajú iba PREV, NEXT alebo holé LAST — absorpcia je zapnutá, ale iba pre stavy v absorbovateľnom regióne vzoru: vedúca greedy neohraničená premenná ako A+ alebo A*, skupina s pevnou dĺžkou s neohraničeným greedy kvantifikátorom ako (A B)+, greedy skupina, ktorej telo začína jedným z nich, ako (A+ B)+ alebo (A+ B){2}, alebo vetvy alternácie zostavené z nich; neochotná skupina diskvalifikuje celý svoj podstrom. Kde to platí, ako pri A+ v §2.5, beh sa zlučuje do jedného kontextu a zostáva lineárny; START UP+ DOWN+ z §2.3 nedostane žiadny absorbovateľný región.

§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í prácu 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, koncová hranica musí byť UNBOUNDED FOLLOWING alebo kladný offset FOLLOWING (takže aj predvolený rámec je odmietnutý) a možnosti EXCLUDE iné ako EXCLUDE NO OTHERS 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:

ZdrojKódovanie stromu
AVAR(A, min=1, max=1)
A+VAR(A, min=1, max=∞)
A*VAR(A, min=0, max=∞)
A{3,5}VAR(A, min=3, max=5)
A+?VAR(A, min=1, max=∞, reluctant=true)

Každý predikát DEFINE je potom typovo overený oproti stĺpcom partície a privedený k logickému výrazu. Z toho vyplývajú dve praktické veci. Po prvé, analýza parsovania nepridáva kvôli DEFINE nič do cieľového zoznamu dotazu; namiesto toho plánovač označí každý stĺpec, na ktorý sa odkazuje predikát DEFINE, ako potrebný, rovnako ako pri HAVING, a prepúšťa tieto stĺpce 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 deväť prepisovacích pravidiel v jedinom prechode zdola nahor (v rámci sekvencie sa zlučovanie skupín spustí ešte raz, pretože skoršie zlúčenia môžu priviesť dve identické skupiny k sebe):

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}
Zlučovanie 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
Normalizácia neochoty
A{2}? → A{2} (neochota sa ruší všade, kde min = max)

Násobenie kvantifikátorov zlučuje iba vtedy, keď dosiahnuteľné počty tvoria jeden súvislý interval a preferovaná zhoda sa neposunie: presný vonkajší ((A{2,3}){5} → A{10,15}), potomok s min 0, alebo intervaly potomka, ktoré na seba nadväzujú, pri min potomka najviac 1 alebo neohraničenom max potomka ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), pričom vonkajší s min 0 navyše potrebuje min potomka najviac 1 ((A{2,})* zostáva, pretože A* by akceptovalo jeden riadok). Skupinový potomok, ktorého vlastný kvantifikátor nie je presný, musí najprv mať telo s pevnou dĺžkou, takže ((A | B B){1,2}){2} zostáva nedotknuté aj pod presným vonkajším. 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 — alebo posunúť preferovanú zhodu ((A{2,3}){1,2} uprednostňuje tri riadky, kde A{2,6} vezme štyri), takže optimalizátor ich necháva nedotknuté. Nie je to jediný podmienený prepis: zlučovanie skupín a zlúčenie sufixu vyžadujú telo, ktoré spotrebuje pevný počet riadkov, zlúčenie prefixu odmieta skupinu s min 0, konečným max a nullable obsahom, neochotné uzly sa nezlučujú ani nenásobia ((A+?)+ zostáva) a prepis, ktorého nová hranica by pretiekla, sa odmietne.

Tvar prvku

Každý prvok plochého poľa predstavuje jednu pozíciu vo vzore. Existuje šesť 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; oddeľovač vetiev, ktorý ukončuje každú vetvu; 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 značka alternácie a oddeľovače vetiev na zreťazenie vetiev, group begin na pomenovanie vlastného group end — skupina, ktorej kvantifikátor povoľuje nulu, sa preskočí cez next tohto konca — 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 → 3
    (otvára skupinu; jump pomenúva
     vlastný END)

[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 jump BEGIN pomenúva jeho END na idx 3, a ak by skupina bola voliteľná, preskočenie by odišlo cez next tohto END na idx 4 bez príchodu na END. 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 päť logických atribútov, 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? B?)+, (A | B*)+; (A?)* sa najprv vynásobí na A* a nezanechá žiadny koniec skupiny). Hovorí behu pridať pod min 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.
Empty-preferred
Nastavený na koncoch skupín, ktorých telo uprednostňuje prázdnu zhodu, ako v (A?? B??){2}. Radí rýchly výstup pred cyklenie späť pod min, kde vlastná greediness skupiny nič nehovorí.
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ť ploché pole od
  prvku 0 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 pripúšťa štyri š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)+, (A+ B){2}
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 A dostane oba príznaky, obklopujúci BEGIN dostane príznak in-region a B ani END nedostanú žiadny.
Prípad 4 — Alternácia
A+ | B+, A+ | C D
Každá vetva, dosiahnutá cez reťaz oddeľovačov, sa posudzuje samostatne podľa prípadov vyššie; značka alternácie dostane príznak in-region, keď sa kvalifikuje ktorákoľvek vetva.

Štrukturálne prípady nepokryté týmito štyrmi 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. 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
  ak targetPos != currentPos:
      načítať riadok na targetPos
        do nav_slot
      nasmerovať vonkajší slot na nav_slot
  result = eval_inner_expression()
  obnoviť current_row_slot
  skopírovať by-ref result z nav_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č a žiadny slot na odkaz; keď je cieľom aktuálny riadok, načítanie aj výmena sa úplne preskočia. Načítanie skopíruje cieľový riadok do navigačného slotu (pokiaľ ho slot už nedrží) a krok obnovenia skopíruje výsledok odovzdávaný odkazom do pamäte na n-ticu, aby ho ďalšie načítanie nemohlo uvoľniť.

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 currentPos − 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 (currentPos − n) − m
  NEXT(LAST(n), m):
      return (currentPos − 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 absorpcia kontextu vôbec možná (§2.5 vs §2.6): jediná premenná závislá od začiatku zhody ju vypne pre celý vzor.

Zdieľané vyhodnotenie · bezpečné pre absorpciu Každý kontext vidí v každom riadku rovnakú logickú hodnotu — rovnaký osud (§2.5).
  • Bez navigácie
  • Iba PREV / NEXT
  • LAST bez posunu
  • Zložené s vnútorným LAST (bez posunu)
Vyhodnotenie na kontext · nebezpečné pre absorpciu Kontexty s rôznymi začiatkami zhody vypočítavajú rôzne odpovede — rozdielne osudy (§2.6).
  • LAST s posunom
  • FIRST (akákoľvek forma)
  • Zložené s vnútorným FIRST
  • Zložené s vnútorným LAST (s posunom)

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ť. Vykonávateľ to určí z dvoch doplnkových posunov, pričom každý posun vyrieši raz na sken (konštantné aj pri inicializácii vykonávateľa, aby ich mohol ukázať obyčajný EXPLAIN):

Rozpočet lookback
Ako ďaleko dozadu od aktuálneho riadka môže akékoľvek volanie DEFINE siahnuť.
Prispievatelia: PREV, LAST (akýkoľvek posun vrátane predvoleného 0), PREV(LAST(...)), NEXT(LAST(...))
Rozpočet lookahead-od-začiatku
Minimálny dosah dopredu (dozadu, ak je záporný) od začiatku zhody najstaršieho živého kontextu — najskorší riadok, ktorý môže akékoľvek volanie DEFINE potrebovať.
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ť. Riadky Nav Mark, ktoré EXPLAIN hlási (§3.7) — Lookback a Lookahead — sú tieto dva rozpočty, nie namerané vrcholy. Každý sa tlačí iba vtedy, keď ho napája nejaká navigácia, a zobrazuje sa aj bez ANALYZE; posun, ktorého hodnota je známa až za behu (napríklad parameter generického plánu), sa pod obyčajným EXPLAIN tlačí ako runtime a pod EXPLAIN ANALYZE ako jeho vyriešená hodnota, a retain all (Lookback) alebo infinite (Lookahead) označuje posun, ktorý pretečie.

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

Výsledok zhody sa zaznamenáva ako dve hodnoty: riadok, v ktorom zhoda začína, a jej dĺžka. Záporný začiatok znamená, že pozícia ešte nebola vyhodnotená; len čo je začiatok nastavený, následné dotazy voči vykonávateľovi — „je tento riadok vnútri zhody?" — môžu odpovedať v O(1) prezretím dvojice. Dĺžka kóduje výsledok: -1 pre nezhodnutý riadok, 0 pre prázdnu zhodu a počet riadkov pre skutočnú zhodu. 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 nezhodnutého riadka aj 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 vzor tohto okna, 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, potom poháňa NFA dopredu riadok po riadku — pre každý riadok resetuje pole zhôd na premennú na „nevyhodnotené" — kým tento kontext nemá žiadne živé stavy alebo kým partícia neskončí. Predikáty DEFINE sa vyhodnocujú lenivo: premenná sa vyhodnotí, keď ju nejaký stav prvýkrát spotrebúva, takže premenná, ktorú v tomto riadku netestuje žiadny živý stav, sa nikdy nevyhodnotí. 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 dosiahol koniec svojho rámca:
          vynútiť nezhodu (finalizovať skoro)
          continue
      ak sa matchStartRow líši od
         zdieľanej vyhodnocovacej pozície:
          resetovať DEFINE premenné závislé
          od match-start na nevyhodnotené (§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)
      ak zaznamenal zhodu a
         SKIP PAST LAST ROW:
          orezať neskoršie kontexty,
          ktoré začínajú vnútri zhody

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]
      assert elem je premenná
          # advance parkuje iba premenné

      ak varMatched[elem.varId] je
         nevyhodnotené:
          teraz vyhodnotiť jej DEFINE
      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
         alebo drží zaznamenanú zhodu:
          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), kým kontext nezaznamená zhodu, čo ho natrvalo nastaví na false — absorpcia by uvoľnila zhodu, ktorú žiadny absorbujúci kontext nedokáže reprodukovať. 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 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í, zastaví sa,
               keď je FIN zaznamenaný),
    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 označiť
         kontext, aby neskoršie kontexty
         vnútri rozsahu tohto kandidáta
         boli orezané — 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 len čo Advance dokončí prácu s kontextom, ktorý zaznamenal kandidáta, každý nasledujúci kontext, ktorého začiatočný riadok spadá do rozsahu kandidáta, je orezaný v tom istom riadku, 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 krok orezania naprieč kontextami v čase FIN. Vnútri kontextu FIN tiež odrezáva lexikálne podriadenú prácu: Advance zahadzuje zostávajúce stavy vo fronte (opísané skôr v tejto sekcii) a v rámci jedného DFS sa každá menej preferovaná cesta — neskoršie vetvy ALT, druhá z ciest preskočenia a vstupu BEGIN, vstupná cesta neochotnej premennej, druhá z ciest cyklu a výstupu END — zastaví, len čo je zhoda zaznamenaná, takže jeden advance zaznamená najviac jednu zhodu.

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
          (najprv fast-forward, ak telo
           uprednostňuje prázdne; druhá
           cesta sa zahodí, ak prvá
           dosiahla FIN)

  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
          ak cyklus dosiahol FIN:
              zahodiť výstup
              # uprednostniť dlhšie
          inak výstup druhý
      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? B?)+ a (A | B*)+ majú túto vlastnosť: v závislosti od dát môže telo dokončiť iteráciu bez spotrebovania ktoréhokoľvek riadka. (Jediný voliteľný potomok ako (A?)* sa v čase kompilácie prepíše na A* a nezanechá žiadnu skupinu.) 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äť do tela (jeho jump je prvý potomok skupiny), telo opäť produkuje prázdnu zhodu, znova dosiahne END atď. Bez niečoho, čo by to zastavilo, by DFS Advance nikdy neukončil.

Ochrana 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. Beh udržiava visited bitmapu, vyčistenú pred každou DFS expanziou stavu, v ktorej sa označujú iba tieto END so značkou empty-loopable — nič iné nemôže cykliť, pretože každé iné cyklenie späť spotrebovalo riadok. Dosiahnutie označeného END znamená, že telo práve odvodilo prázdnu iteráciu, a stav sa nezahodí: na dolnej hranici alebo nad ňou tam opustí skupinu (prázdna iterácia zastavuje kvantifikátor) a pod ňou prepadne do normálneho cyklenia späť, takže každý prázdny príchod stále zvyšuje počet, kým nedosiahne min. Vezmime (A? B?){2,3}, kde sa žiadna z premenných nezhoduje nikde v prúde riadkov:

iter 1: A? B? sa zhodujú s nula riadkami
        → END, count = 1 (pod min)
        END už označený (pri vstupe
        do skupiny), ale pod min:
        → cyklus späť do A?
iter 2: A? B? sa zhodujú s nula riadkami
        → END, count = 2 (spĺňa min)
        END už označený, na min:
        → opustiť skupinu
výstup s nulovou dĺžkou zhody

Pod dolnou hranicou empty-loop značka tiež hovorí END handleru, aby naklonoval ďalší fast-forward stav vedľa normálnej cesty cyklenia späť:

advance_end (count pod min):

  cesta cyklenia späť:
    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. 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? B?){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 okamžite opúšťa skupinu, deklarujúc „zvyšok požadovaných iterácií je prázdny," a umožňuje zhode uspieť s telom nulovej dĺžky. O poradí rozhoduje telo, nie vlastná greediness skupiny: fast-forward ide prvý presne vtedy, keď telo uprednostňuje prázdnu zhodu (neochotné telo ako (A?? B??)), a ak prvá cesta dosiahne FIN, druhá sa zahodí, takže menej preferovaná cesta nemôže nahradiť preferovanú zhodu. 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ý

Udržanie behu ohraničeného 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 leží v bode porovnania a je pokrytý absorbovateľným stavom staršieho kontextu na tom istom prvku s väčším alebo rovnaký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) Advance
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 orezaný, len čo Advance dokončí prácu s kontextom, ktorý kandidáta zaznamenal.
Cycle guard Advance
Epsilon expanzie, ktoré dosiahnu END nullable skupiny už označený v rámci toho istého DFS (označený pri vstupe cez BEGIN alebo pri skoršom príchode) — inak by cyklili navždy; na dolnej hranici alebo nad ňou tam stav opustí skupinu a pod ňou pokračuje v cyklení.
Empty-loop fast-forward Advance
Pod dolnou hranicou nullable skupiny ďalšia cesta, ktorá opúšťa skupinu so zostávajúcimi požadovanými iteráciami deklarovanými ako prázdne, zoradená voči cyklu späť podľa preferencie tela.
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). Čítanie opisov namiesto toho zoskupuje pravidlá podľa toho, na čo cieľujú: mŕtve vetvy, redundantné kontexty, ekvivalentné stavy, nekonečné cykly a predlžovanie za hranice uložené používateľom.

Žiadne jediné pravidlo samo by nestačilo. 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ú. Zdrojový kód dokumentuje prípady, ktoré vrstvy nezachytia: deduplikácia ponecháva oddelene stavy, ktoré sa líšia iba počtami nad min, takže (A{2,} B)+ C, kde C nikdy nie je pravdivé, drží vo vrchole Θ(n²) stavov a vytvorí ich Θ(n³) (37 s na 320 riadkoch), a séria úplne nullable alternácií sa enumeruje cesta po ceste, takže (A?|B?){30} trvá vyše pol hodiny.

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. V textovom formáte sú vydávané spolu s okenným operátorom, za riadkom Pattern:, prípadnými riadkami Nav Mark (ktoré ukazuje aj obyčajný EXPLAIN) a riadkom Storage::

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (každý iba vtedy, keď DEFINE používa
   navigáciu, ktorá ho napája)
NFA States: N peak, N total, N merged
NFA Contexts: N peak, N total, N pruned
NFA: N matched (len min/max/avg),
     N mismatched (len min/max/avg)
NFA: N absorbed (len min/max/avg),
     N skipped (len min/max/avg)
  (druhý riadok NFA iba vtedy, keď je
   niektorý z počtov nenulový; nulový
   počet sa tlačí bez svojho (len ...))

Netextové formáty vydávajú každý počet ako samostatnú vlastnosť. 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; pruned počíta kontexty, ktoré zlyhali po jedinom riadku. Histogramy dĺžok zhôd oddeľujú štyri výsledky — úspešné zhody, pokusy o zhodu, ktoré zlyhali po viac ako jednom riadku (mismatched), absorbované kontexty a kontexty uvoľnené pomocou AFTER MATCH SKIP PAST LAST ROW, pretože začali vnútri zaznamenanej zhody (skipped) — 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ď zhodnuté, alebo absorbované, s malými dĺžkami nezhody.

Dva čítače Nav Mark reportujú rozpočet uchovávania tuplestoru, ktorý §3.3 odvodzuje z DEFINE. Lookback je najhlbší dosah dozadu od aktuálneho riadka cez PREV, LAST s akýmkoľvek posunom (vrátane predvoleného 0) a zložené formy s vnútorným LAST; Lookahead je minimálny dosah dopredu (záporný, keď hľadí pred začiatok zhody) 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 známym iba na sken, a — iba pre Lookback — „retain all", keď posun pretečie; Lookahead, ktorý pretečie, sa tlačí ako „infinite". Každý riadok sa vydáva iba vtedy, keď ho napája nejaká navigácia v DEFINE, a oba sa zobrazujú aj pod obyčajným EXPLAIN: konštantné posuny sa ustália pri inicializácii vykonávateľa, zatiaľ čo posun známy až za behu (napríklad parameter generického plánu) sa tam tlačí ako „runtime" a pod EXPLAIN ANALYZE ako jeho vyriešené celé číslo.

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

Okrem čítačov EXPLAIN tlačí riadok Pattern: zostavený zo skompilovaného poľa prvkov, takže ukazuje vzor po prepisoch v čase kompilácie (PATTERN (A A) sa vysvetlí ako a{2}) a nesie značky absorpcie # (bod porovnania) a ~ (absorbovateľný región); DEFINE a možnosť AFTER MATCH SKIP sa nezobrazujú. Reprodukovanie klauzúl tak, ako boli zapísané, vrátane neochotných kvantifikátorov, opakovania skupín a možnosti preskočenia, je úlohou pg_get_viewdef(), ktorá 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 22 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
Integrácia klauzuly WINDOW — realistické okenné scenáre na syntetických akciových dátach (V-tvar, W-tvar, po sebe idúce vzostupy, obraty), plus sémantika navigácie a chyby obmedzení DEFINE.
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; plus vrstva plánovača — optimalizácia vzorov, príznaky absorpcie, fallback optimalizácie, integrácia s plánovačom.
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. Tieto scenáre sú jediné testy, kde sa vstupy a výstupy čítajú ako dotazy, ktoré by používateľ skutočne napísal; zvyšok súboru je, podobne ako ostatné sady, redukcionistický — vnáranie PREV/NEXT a chyby nekonštantných posunov, pravidlá odkazov v DEFINE a sémantika navigačných posunov.

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ť. Druhá časť, vrstva plánovača, pokrýva optimalizáciu vzorov, zobrazenie a analýzu príznakov absorpcie, fallback optimalizácie a integráciu s plánovačom (poddotazy, spojenia, množinové operácie, triedenie a zoskupovanie).

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 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: inline riadky VALUES nesúce pole názvov premenných, ktoré deklaruje, ktoré premenné DEFINE sa zhodujú v každom riadku, spárované so vzorom, ktorý skúma špecifické runtime správanie. Idióm 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:

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 (monitorovacie dashboardy, log scrapery) ho parsujú a zmeny, ktoré vyzerajú kozmeticky, ich môžu zlomiť. Sada rpr_explain overuje tri veci:

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, ako každá z týchto optimalizácií zaobchádza s RPR oknami — väčšina musí byť vypnutá alebo obídená:

Kanonikalizácia rámca
Plánovač normálne prepisuje ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING na ROWS UNBOUNDED PRECEDING pre okenné funkcie nezávislé od rámca, ako row_number, rank a ntile. 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 alebo SKIP)
Dve RPR okná s tým istým PATTERN, ale rôznymi klauzulami DEFINE alebo iným AFTER MATCH SKIP, produkujú rôzne zhody a musia zostať odlišné, aj keď je ich štrukturálny tvar identický.
Projekcia nepoužitého výstupu
Táto sa uplatniť smie: keď okolitý dotaz nikdy nečíta výstup okna, okenná funkcia sa stane NULL a jej WindowAgg sa odstráni, pričom počet riadkov zostane nezmenený. Testy kontrolujú, že stĺpce, ktoré DEFINE číta, stále dosiahnu WindowAgg, keď zostáva, a že okno je ponechané, keď sa jeho hodnota číta.
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.

Ďalšie prípady kontrolujú, že odhad nákladov zohľadňuje DEFINE, že poddotaz obsahujúci RPR okno sa nesploští, že výrazy DEFINE neunikajú do vyššieho WindowAgg a že LIMIT zostáva nad WindowAgg; druhá skupina spúšťa RPR spolu s CTE, spojeniami, množinovými operáciami, pripravenými príkazmi, partíciovanými tabuľkami a podobnými konštrukciami. Väčšina strážených prípadov má rovnaký tvar: baseline, ktorý spúšťa optimalizáciu (zvyčajne ne-RPR dotaz, kontrolovaný v EXPLAIN), potom RPR dotaz štrukturálne podobného tvaru, kde optimalizácia nie je aplikovaná — pre prípad deduplikácie DEFINE/SKIP je baseline dvojica identických RPR okien a prípad inverzného prechodu kontroluje obídenie pomocou logovacieho agregátu namiesto EXPLAIN. 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é.