Row Pattern Recognition Do hloubky

§1. Standard, podmnožina a otevřené otázky

1.1 Rozsah standardu

Row Pattern Recognition bylo do SQL zavedeno normou ISO/IEC 9075-2:2016 a je popsáno v doprovodném dokumentu ISO/IEC 19075-5:2021 (část 5, „Row Pattern Recognition“).

Standard definuje dvě rozhraní pro stejný podkladový mechanismus. Funkce R010 umisťuje klauzuli MATCH_RECOGNIZE do seznamu FROM a produkuje odvozenou tabulku; funkce R020 tutéž logiku vzorů zabaluje do specifikace WINDOW a produkuje výstup okenní funkce. Obě rozhraní sdílejí převážnou část syntaxe a celou sémantiku, jsou však funkčně odlišnými vstupními body — databáze může implementovat jedno nebo obě.

Série patchů, o které se zde hovoří, implementuje podmnožinu výhradně R020; tabulková podoba je záměrně mimo rozsah.

Rozhraní R020 je malé, ale výrazové. Dotaz připojí vzor k oknu tím, že do specifikace okna přidá tři klauzule: PATTERN popisuje regulární výraz nad pojmenovanými proměnnými vzoru, DEFINE dodává booleovský predikát, který každou proměnnou identifikuje, a AFTER MATCH SKIP řídí, jak jsou po sobě jdoucí shody umisťovány v rámci partition.

Volitelné konstrukce MEASURES, SUBSET, INITIAL/SEEK a pomocná funkce CLASSIFIER() celou funkci doplňují. (Funkce standardu MATCH_NUMBER() patří pouze k rozhraní R010 — 19075-5 §6.3.3 (6) ji z R020 výslovně vylučuje.)

Patch pokrývá dostatek tohoto slovníku k tomu, aby fungovaly netriviální dotazy, ale zastavuje se před několika konstrukcemi, jejichž implementace závisí na infrastruktuře, která zatím nebyla vybudována.

Zbytek této sekce dělí slovník standardu na to, co patch již podporuje, a na to, co záměrně ponechává na později. Seznamy níže odrážejí aktuální stav série patchů.

1.2 Implementované funkce

Implementovaný slovník postačuje k vyjádření kanonických vzorů ve tvaru V, W a obratu, které jsou prvotním důvodem existence row pattern recognition. Pokrývá také všechny standardní kvantifikátory — včetně všech sedmi neochotných variant *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — a čtyři navigační primitiva, která potřebují podmínky DEFINE ke srovnávání sousedních řádků.

klauzule PATTERN

Definuje vzor řádků uvnitř specifikace okna.

Regex: + * ? |

Standardní kvantifikátory a alternace.

Regex: ( ) seskupování

Závorkované podvzory.

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

Omezené počty opakování.

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

Všech sedm neochotných (non-greedy) variant, které standard definuje (vyloučeny z optimalizace absorpce).

klauzule DEFINE

Booleovské podmínky identifikující každou proměnnou vzoru.

Univerzální proměnná řádkového vzoru

Nekvalifikované odkazy na sloupce v DEFINE (např. holé Price) se vyhodnotí na aktuální řádek, dle 19075-5 §4.10/§4.16.

PREV, NEXT (s offsetem)

Sahají n řádků před/za aktuální řádek (výchozí 1); vnitřní argument je libovolný hodnotový výraz vyhodnocený na navigovaném řádku.

FIRST, LAST (s offsetem)

Sahají na řádek relativní vůči shodě; FIRST(expr, n) cílí na řádek n po začátku shody, LAST(expr, n) na řádek n před nejnovějším řádkem shody.

Složená navigace (čtyři formy)

Vnější krok PREV/NEXT navrstvený nad vnitřním FIRST/LAST: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — vnitřní i vnější krok přijímá vlastní offset.

INITIAL

Shody vzoru musí začínat na aktuálním řádku (výchozí).

AFTER MATCH SKIP PAST LAST ROW

Výchozí režim přeskoku; způsobilý pro kontextovou absorpci.

AFTER MATCH SKIP TO NEXT ROW

Povoluje překrývající se shody; absorpci znemožňuje.

1.3 Neimplementováno

Funkce, které zůstávají neimplementované, spadají do tří volných skupin. První — a zdaleka největší — je rodina konstrukcí soustředěná kolem MEASURES: samotná klauzule MEASURES, SUBSET, CLASSIFIER(), odkazy na sloupce kvalifikované vzorem jako B.price a navigace kvalifikovaná vzorem jako LAST(B.price) nebo PREV(B.price).

Nejde tolik o nezávislé mezery, jako spíše o různé pohledy na jednu chybějící součást: executor by musel uchovávat historii každé shody — záznam pro každý řádek shody o tom, ke které proměnné vzoru byl namapován — a žádná z těchto konstrukcí bez ní nemá smysluplnou definici. CLASSIFIER() čte z tohoto záznamu název proměnné; B.price čte sloupec price řádků, jejichž záznam říká B; LAST(B.price) prochází stejnou množinu řádků a vybírá poslední; SUBSET U = (A, B) definuje virtuální proměnnou agregující nad oběma kbelíky; a MEASURES vyhodnocuje výrazy jako AVG(U.Price) přesně pomocí této agregace.

Současný executor vyhodnocuje predikáty DEFINE řádek po řádku, ale výsledná přiřazení proměnných nikam nezaznamenává — není nad čím se později dotazovat. Vybudování infrastruktury historie je tedy předpokladem pro celou skupinu; jednotlivé funkce z toho vypadnou jako malé projekce, jakmile záznamy existují.

Druhá skupina se týká alternativních cílů přeskoku: AFTER MATCH SKIP TO label, AFTER MATCH SKIP TO FIRST var a AFTER MATCH SKIP TO LAST var. Ty také závisí na historii shody, protože executor musí být schopen ukázat na konkrétní označený řádek uvnitř nejnovější shody.

Zbývající položky tvoří různorodý zbytek: klíčové slovo SEEK (alternativa k INITIAL), prázdný vzor (), vylučovací forma {- … -} a operátor PERMUTE nezávislý na pořadí.

MEASURES

Pojmenované výstupní výrazy pro každou shodu, např. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; v R020 zpřístupněno přes OVER jako okenní funkce. Přijímá klíčová slova FINAL / RUNNING (19075-5 §5.4), která se v R020 sbalí na stejnou hodnotu, protože měření jsou vždy vyhodnocována na posledním řádku shody (19075-5 §6.9 (3)).

SUBSET

Pojmenované sjednocení proměnných vzoru, např. SUBSET U = (A, B, C). Použitelné všude, kde lze odkazovat na proměnnou vzoru — MEASURES, odkazy kvalifikované vzorem v DEFINE, CLASSIFIER(U) — vše vyžaduje historii shody.

CLASSIFIER()

Vrací, jako která proměnná vzoru byl daný řádek přiřazen. Definováno pro DEFINE i MEASURES (19075-5 §5.9); odpověď na libovolném řádku je název proměnné zaznamenaný pro daný řádek v historii shody.

Odkaz na sloupec kvalifikovaný vzorem

Holé B.price v DEFINE nebo MEASURES — hodnota sloupce z řádku namapovaného jako pojmenovaná proměnná.

Navigace kvalifikovaná vzorem

Omezuje navigaci na řádky přiřazené pojmenované proměnné, např. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

Shoda smí začít kdekoli v okně (na rozdíl od INITIAL).

AFTER MATCH SKIP TO label

Přeskok na označený řádek.

AFTER MATCH SKIP TO FIRST var

Přeskok na první řádek přiřazený pojmenované proměnné.

AFTER MATCH SKIP TO LAST var

Přeskok na poslední řádek přiřazený pojmenované proměnné.

Regex: {- -}

Vyloučení — odstraňuje přiřazené řádky z výstupu shody.

Regex: ()

Prázdný vzor — odpovídá prázdné posloupnosti.

PERMUTE(...)

Shoda nezávislá na pořadí napříč vyjmenovanými proměnnými.

Agregační funkce v DEFINE

Agregace jako SUM, AVG, COUNT nejsou v predikátech DEFINE povoleny. Standard je povoluje jako běžící agregace nad částečnou shodou (vyhodnocení po řádcích vůči řádkům již přiřazeným proměnné), což závisí na stejné historii každé shody, kterou vyžadují MEASURES/CLASSIFIER().

Stojí za to zmínit další čtyři body, neboť je snadné je zaměnit za opomenutí.

Prvním je, že kotvy vzoru ^ a $ nejsou s RPR v klauzuli WINDOW povoleny samotným standardem (19075-5 §6.13: „the anchors (^ and $) are not permitted with row pattern matching in windows“; s podkladovou definicí v 19075-5 §4.14.1); jejich absence je dodržování, nikoli mezera.

Druhým je, že MATCH_NUMBER() je standardem rovněž vyloučena z R020 (19075-5 §6.3.3 (6) a 19075-5 §6.9 (1)) — patří pouze k rozhraní R010 a její absence je zde opět dodržováním, nikoli chybějící funkcí.

Třetím je sada strukturálních zákazů, které standard ukládá R020 (19075-5 §6.17): row pattern recognition nemůže být vnořeno do jiného row pattern recognition; MEASURES a DEFINE nesmí obsahovat vnější odkazy; poddotazy uvnitř MEASURES nebo DEFINE nesmí odkazovat na proměnné vzoru řádků; a RPR nesmí být použito uvnitř rekurzivního dotazu.

Čtvrtým je, že samotné MATCH_RECOGNIZE — funkce R010, tabulkové rozhraní téhož mechanismu — je mimo rozsah tohoto patche. Zda PostgreSQL nakonec přidá R010, bude otázkou budoucí série, nikoli měřítkem této.

§2. Příklady — jak to ve skutečnosti běží

Příklady v této sekci se budují postupně. Začneme koncepčním důvodem, proč je shoda nad řádky skutečně odlišná od shody nad řetězci, poté představíme čtyři navigační funkce, díky nimž jsou podmínky DEFINE zajímavé, a nakonec projdeme tři trasy od začátku do konce: jednu shodu (pohyb NFA), kontextovou absorpci v jednoduchém případě a případ, kdy se absorpce stává nebezpečnou.

Vnitřní mechanismus, který činí navigaci levnou — výměna n-tice v jednom slotu — patří k návrhu executoru a je probírán v další sekci, nikoli zde.

2.1 Proč se vzory řádků liší od textových vzorů

Textový regulární výraz odpovídá proudu znaků a na každé pozici je k uvážení právě jeden symbol. Otázka za běhu — „rovná se aktuální symbol 'A'?“ — má jedinou odpověď ano/ne. Automaty s návratem to využívají: na každý znak přežije nanejvýš jedna větev a cena nejednoznačnosti se platí opětovným čtením vstupu.

Vzor řádků je odlišný zásadním způsobem. Řádek není jediným symbolem; je to n-tice sloupců vyhodnocená vůči množině booleovských predikátů, podmínkám DEFINE. Dva predikáty mohou být na stejném řádku pravdivé současně a nic ve standardu neříká, že se musí vzájemně vylučovat. Uvažujme:

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

Řádek s price = 150, volume = 2000 splňuje A i B, ale ne C. Vyhodnocovač vzoru to nemůže zhroutit do jediného stavu — dvě proměnné vzoru jsou aktivní a libovolný prvek vzoru, který některou z nich pojmenovává, může postoupit. NFA proto musí nést více současných stavů na řádek partition, nikoli jeden.

Toto jediné pozorování řídí zbytek architektury. Stav vykonávání je seznamem kontextů, každý kontext je seznamem stavů a na každém řádku se runtime u každého stavu ptá: „vzhledem k proměnným, které jsou zde pravdivé, kam mohu jít?“ Vznikající větvení je důvodem, proč runtime potřebuje několik vrstev prořezávání — deduplikaci stavů v rámci kontextu, absorpci napříč kontexty a další pravidla popsaná v §3.6 — bez nichž počet aktivních stavů a kontextů roste s partition a shoda vzorů se stává superlineární.

2.2 Navigační funkce

Podmínky DEFINE odkazující pouze na aktuální řádek jsou omezené; téměř každý zajímavý vzor potřebuje porovnat aktuální řádek se sousedy nebo s řádky již dříve přijatými v shodě. Standard k tomu poskytuje čtyři navigační funkce a patch je implementuje všechny.

PREV(expr [, n])

Řádek n řádků před aktuálním (výchozí n = 1). Používá se pro porovnání „dnes vs. včera“.

NEXT(expr [, n])

Řádek n řádků za aktuálním. Pohled vpřed; v okenní formě neobvyklý, protože okno je monotónní.

FIRST(expr [, n])

n-tý přiřazený řádek aktuální shody, počítáno od začátku. „Porovnej s řádkem, který tuto shodu zahájil.“

LAST(expr [, n])

n-tý nejaktuálnější přiřazený řádek. „Porovnej s nejnověji přiřazeným řádkem.“

Tato čtyři primitiva se skládají: PREV a NEXT mohou obalit volání FIRST nebo LAST a poskytnout čtyři složené formy, jejichž sémantika je „přejdi na řádek relativní vůči shodě a poté udělej krok pevné vzdálenosti od něj“. To umožňuje výrazu DEFINE číst například řádek bezprostředně před začátkem shody.

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

Krok m řádků zpět od n-tého řádku shody (výchozí m = 1). „Jaká byla hodnota těsně před tím, než tato shoda začala?“

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

Krok m řádků vpřed od n-tého řádku shody. Sahá dál do shody bez závislosti na aktuálním řádku.

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

Krok m řádků zpět od n-tého nejaktuálnějšího přiřazeného řádku. „Porovnej s řádkem krátce před nejnovější shodou.“

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

Krok m řádků vpřed od n-tého nejaktuálnějšího přiřazeného řádku.

Stojí za to zde uvést dva praktické body. Za prvé, navigaci lze skládat: PREV(FIRST(price)) čte řádek bezprostředně před začátkem shody a patch to podporuje. Za druhé má navigace důsledky pro optimalizace executoru. PREV a NEXT jsou relativní k aktuálnímu řádku a jsou vždy bezpečné; FIRST a varianty LAST s offsetem jsou relativní k hranicím shody, což se prolíná s kontextovou absorpcí a nutí planner ponechat naživu některé kontexty, které by jinak zahodil. Mechanismus této interakce je tématem §2.6.

2.3 Propracovaný pří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 se zploští na čtyři prvky:

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

Pro řadu cen 100, 110, 120, 115, 108, 130:

Klíčová poznámka: na řádku 3 řádek splňuje jak START (vždy pravdivé), tak DOWN, ale jediný stav, který přežil řádek 2, je na větvi výstupu DOWN, takže se uskuteční pouze přechod UP → DOWN. Vícestavová povaha z §2.1 je viditelná jako rozvětvení při každé shodě UP (stav by mohl zůstat v UP+ nebo postoupit směrem k DOWN+). Lačná preference je „znovu cyklit před výstupem“, takže s dostatečnými daty by cyklící větve shodu prodloužily; zde cyklící DOWN umírá na řádku 5 (130 ≮ 108) a dřívější kandidát FIN (řádky 0–4) — vytvořený, když DOWN vystoupil na řádku 4 — je finalizován jako shoda.

Výsledek dotazu vyplývá přímo z této trasy. Podle sémantiky RPR jsou okenní funkce first_value(price) a last_value(price) vyhodnoceny pouze na řádku, který shodu zahájil — každý další řádek shody pro tyto okenní funkce produkuje NULL, protože jeho redukovaný rámec je prázdný. Výstup pro naše data tedy vypadá jako tabulka, kterou poster ukazuje ve svém pravém horním panelu:

Řádek 0 je začátkem shody, takže jeho rámec pokrývá řádky 0–4 a okenní funkce hlásí počáteční cenu V-tvaru ($100) a spodní cenu ($108). Řádky 1–4 jsou uvnitř shody, ale nejsou jejím začátkem, proto dostávají NULL. Řádek 5 (cena $130) je mimo jakoukoli shodu a rovněž dostává NULL.

2.4 Propracovaný příklad 2 — alternace a lexikální pořadí

Forma (A | B) dává vyhodnocovači volbu: na libovolném řádku jsou obě alternativy testovány nezávisle a libovolný jejich počet může odpovídat. Zde se vícestavová povaha z §2.1 stává viditelnou uvnitř jediného kontextu — nikoli napříč kontexty (to je absorpce), ale podél paralelních větví, které executor zkoumá synchronně.

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

Představme si řádek, kde cena vzrostla a zároveň překročila $100 — obě UP i HIGH jsou pravdivé. Každá alternativa zplodí svůj stav: jeden jde větví UP, druhý větví HIGH. Postupují paralelně, dokud je DONE nevyřeší.

Obě větve produkují shodu stejné délky nad stejnými řádky, takže vyhodnocovači zbývají dvě kandidátní cesty — jedna označená UP, DONE a jedna HIGH, DONE. Standard to řeší lexikálním pořadím: mezi alternativami zapsanými v (UP | HIGH) vyhrává ta zapsaná dříve, bez ohledu na délku shody. Protože UP je uvedeno před HIGH, přeživší cestou je UP, DONE.

Lexikální pořadí je to, co činí CLASSIFIER() dobře definovaným, až bude nakonec implementován — umožňuje runtime sdělit uživateli „tento řádek odpovídal UP, nikoli HIGH“, i když oba predikáty byly pravdivé. Lexikální pořadí je primárním pravidlem pro alternaci: lexikálně dřívější větev vyhrává nad lexikálně pozdější, i kdyby lexikálně pozdější větev produkovala delší shodu, a lexikálně pozdější (případně kratší) větev může přesto vyhrát, jestliže všechny lexikálně dřívější větve umírají před dosažením FIN. Lačná délka se rozhoduje uvnitř jednoho kvantifikátoru — mezi dvěma dokončeními téže větve alternace lačný kvantifikátor preferuje více iterací.

2.5 Propracovaný příklad 3 — kontextová absorpce (stejný osud)

Nejjednodušším vzorem vykazujícím absorpci je PATTERN (A+) s DEFINE A AS TRUE. Každý řádek odpovídá A a standard vyžaduje, aby vyhodnocovač uvažoval každý řádek jako možný začátek shody. Naivně to znamená N kontextů pro partition o N řádcích. Vezměme partition o pěti řádcích (jakákoli data — predikát je konstantně pravdivý):

Paměť roste z O(n) na O(1). Absorpční pravidlo, které toto zahození ospravedlňuje, je při neomezeném kvantifikátoru přímočaré:

Levý dolní panel posteru („① Context Absorption“) je přesně toto pravidlo vizualizované přes pět řádků.

V pravidle se skrývá jemný, ale důležitý bod: zahození je bezpečné, protože predikát A AS TRUE dává stejnou hodnotu na každém řádku bez ohledu na to, který kontext se táže. Totéž platí pro každý predikát odkazující pouze na aktuální řádek nebo na pevný offset od něj — včetně PREV. Další příklad přechází na konkrétní týden cen s predikátem založeným na PREV a §2.6 přesně tento týden znovu použije, aby symetrie mezi bezpečnou a nebezpečnou absorpcí byla zřejmá:

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

Vezměme obchodní týden $100, $108, $112, $116, $110 od pondělí do pátku — čtyři růsty následované náhlým poklesem. Předpokládejme, že C1 začíná v úterý (první den, kdy RISE odpovídá: $108 > $100), a executor spekulativně sleduje také C2 začínající ve středu. Podmínka RISE každého řádku porovnává cenu řádku s jeho bezprostředním předchůdcem — což je fakt na úrovni partition, nikoli na úrovni kontextu — takže oba kontexty jsou nuceny počítat stejný boolean na každém sdíleném řádku:

Příběh se zlomí v okamžiku, kdy predikát začne záviset na vlastních hranicích každého kontextu — a o tom je §2.6.

2.6 Propracovaný příklad 4 — kdy se absorpce stává nebezpečnou

Předpokládejme, že analytik chce najít po sobě jdoucí obchodní dny, kdy akcie zůstala do deseti dolarů od dne, kdy běh začal — jakési konsolidační okno. Vzor a DEFINE vypadají takto:

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

Podmínka nyní porovnává cenu aktuálního řádku s cenou na začátku aktuálního běhu. Dva běhy, které začaly v různé dny, mají různé hodnoty FIRST(price), takže dva stavy na stejném prvku vzoru a se stejným počtem už nejsou zaměnitelné: jejich budoucnost závisí na hranici, kterou se absorpce chystala zahodit.

Vezměme zcela stejný obchodní týden jako v §2.5 — $100, $108, $112, $116, $110 od pondělí do pátku. Runtime opět udržuje dva kandidátní běhy současně: C1 začal v pondělí, C2 začal v úterý (každý řádek je potenciálním začátkem běhu pod STABLE+).

Při absorpci by se C2 v úterý sloučil s C1 — sloučený kontext si ponechává jen jeden strop, takže odlišný pohled C2 (strop $118, čtyřdenní běh, který končí až v sobotu) už nelze z vnitřního stavu obnovit. C2 musí zůstat naživu, protože je nezávislým kandidátem na shodu, který runtime může ještě potřebovat: jakmile shoda C1 skončí ve středu, další pokus musí pokračovat z dosud běžícího C2, místo aby začínal od nuly. Kdykoli predikát DEFINE nese závislost na začátku shody, planner proto absorpci preventivně vypne.

(Pokud shoda vedoucího kontextu uspěje, kontexty, které začaly uvnitř jeho přijatého rozsahu — při výchozím AFTER MATCH SKIP PAST LAST ROW — se jednoduše zahodí; jsou ponechány naživu jen proto, aby runtime měl kam ustoupit, kdyby vedoucí shoda selhala.)

Tabulka závislostí v pravém dolním panelu posteru („② Navigation“) shrnuje, které navigační formy vytvářejí závislost na začátku shody:

Dva příklady v §2.5 a §2.6 se redukují na jedno pravidlo. Stejný osud činí absorpci bezpečnou: pokud každý kontext na stejném prvku vzoru spočítá stejnou odpověď na každý budoucí predikát, stačí udržet jen nejstarší. Odlišné osudy činí absorpci nebezpečnou: jakmile se predikáty větví podle stavu soukromého kontextu — což přesně dělají FIRST a LAST s offsetem — každý aktivní kontext představuje budoucnost, kterou žádný jiný kontext nemůže obnovit, a zahození kteréhokoli z nich riskuje špatnou odpověď.

Planner toto rozlišení zjistí v době kompilace a rozhoduje pro každý kontext zvlášť, zda se absorpce použije. To je také důvod, proč benchmark v panelu ③ posteru zůstává lineární jak v případě úspěchu, tak v případě selhání: když je absorpce bezpečná, runtime kontexty sloučí, a když ne, planner přijme cenu více kontextů, než aby riskoval špatnou odpověď.

Čísla benchmarku na posteru jsou tentýž algoritmus v reálném měřítku. U úspěšného vzoru (A+ B+ C+ D) škálují PostgreSQL i Trino O(n), jakmile je shoda potvrzena, a náskok PostgreSQL — zhruba 16× až 33× — je převážně rozdílem JVM.

U vzoru se selháním (A+ B+ C+ E) Trino absorpci nemá a degraduje na O(n²) při sledování každého potenciálního začátku shody; při 100 000 řádcích trvá přes pět hodin, zatímco PostgreSQL dokončí za 92 ms, zrychlení přibližně 217 000×.

Tento rozdíl není inženýrským vyleštěním — je to přesně rozlišení stejného/odlišného osudu z §2.5 a §2.6, uplatněné na každý řádek každého potenciálního začátku shody v partition.

2.7 Propracovaný příklad 5 — kdy SKIP vypíná absorpci

Předchozí příklad porušil absorpci ze strany dat: FIRST v DEFINE způsobil, že každý kontext vyhodnocuje predikáty odlišně. Absorpce může selhat i ze strany výstupu a klauzule AFTER MATCH SKIP to ovládá.

Uvažujme vzor PATTERN (A+) s DEFINE A AS TRUE nad pěti řádky, které všechny odpovídají A. Při výchozím AFTER MATCH SKIP PAST LAST ROW vyhodnocovač najde nejdelší shodu začínající nejdřívějším řádkem a poté za ni přeskočí; jakýkoli kontext, který začal uvnitř této shody, je implicitně zahozen jako nadbytečný — přesně situace, na kterou je absorpce navržena. Výstupem je jediná shoda, řádky 0–4, a runtime potřebuje jen jeden aktivní kontext.

Přepněte režim přeskoku na AFTER MATCH SKIP TO NEXT ROW a kontrakt se změní:

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

Nyní musí být každá potenciální výchozí pozice hlášena samostatně, i když se shody překrývají. Pro stejných pět řádků musí runtime vydat pět shod: řádky 0–4, 1–4, 2–4, 3–4 a 4–4. Žádnou z nich nelze nahradit „delší začínající dříve“, protože standard říká, že uživatel chce všechny.

Všimněte si, že predikát se nezměnil. A AS TRUE se vyhodnocuje stejně na každém řádku bez ohledu na to, který kontext se táže, takže podmínka stejného osudu z §2.5 je stále splněna. Mění se však výstupní požadavek: i kontexty s identickou budoucností musí koexistovat, protože odpovídají odlišným řádkům výsledku. Planner proto kontextovou absorpci vypíná vždy, když je v platnosti AFTER MATCH SKIP TO NEXT ROW, bez ohledu na klauzuli DEFINE.

Položíme-li §2.6 a §2.7 vedle sebe, dostáváme úplný obraz toho, kdy absorpce selhává:

Kterákoli z těchto podmínek stačí k vypnutí absorpce pro dotčené kontexty. Když není v platnosti žádná — výchozí AFTER MATCH SKIP PAST LAST ROW s podmínkami DEFINE, které používají pouze PREV, NEXT nebo holé LAST — runtime sloučí kontexty na jeden na pozici vzoru a zůstává po celou dobu lineární.

§3. Návrh — od parseru po executor

Row Pattern Recognition je implementováno jako tři fáze, které si práci předávají skrze dobře definované mezilehlé formy. Parser převádí SQL text na strom vzoru a seznam predikátů DEFINE; planner kompiluje strom do plochého pole prvků vzoru a rozhoduje, které z nich se mohou účastnit kontextové absorpce; executor spouští pole nad partition řádek po řádku v třífázové smyčce. Každá fáze má vlastní tvar dat a většina důmyslu návrhu se nachází na hranicích: ploché NFA, které se vejde do cache, navigační model, který znovu používá jediný slot n-tice místo materializace jednoho na referenci, a absorpční pravidlo, které mění paměť O(n²) na O(n).

SQL text
  │
  │  fáze parseru
  ▼    ověřit rámec
       sestavit strom vzoru
       zkontrolovat typy DEFINE

strom vzoru + seznam DEFINE
  │
  │  fáze planneru
  ▼    optimalizovat strom
       kompilovat do plochého pole NFA
       rozhodnout o absorbovatelnosti

ploché NFA + příznaky absorpce
  │
  │  fáze executoru
  ▼    engine po řádcích:
       Match → Absorb → Advance

výsledek shody:
  výchozí řádek, délka, úspěch/selhání

Sekce níže prochází tuto pipeline shora dolů. §3.1 popisuje parser a tvar stromu vzoru; §3.2 popisuje kompilaci, která strom mění na ploché NFA; §3.3 popisuje navigační model, který predikáty DEFINE používají k pohledu na sousední řádky; §3.4 popisuje zacházení s hranicemi shody — pravidla SKIP, INITIAL a omezeného rámce, která fixují, kde shoda začíná a končí; §3.5 je třífázový engine po řádcích; §3.6 shromažďuje všechny prořezávací mechanismy, které drží stavový prostor omezený; a §3.7 zkoumá, co implementace zobrazuje ve výstupu EXPLAIN.

3.1 Parser — sestavení stromu vzoru

Parser rozpozná pattern recognition podle přítomnosti klauzule PATTERN uvnitř specifikace okna. Jeho první prací je validace rámce, neboť RPR ukládá omezení, která běžné okenní dotazy nemají: režim rámce musí být ROWS (nikoli RANGE nebo GROUPS), počáteční hranice musí být CURRENT ROW a možnosti EXCLUDE jsou zakázány. Jde o kontroly dodržování, nikoli o optimalizace — pojem rámce v RPR je rozsah shody a standard nepředpokládá jeho vyplňování jinými než přiřazenými řádky.

Jakmile rámec projde validací, parser převede klauzuli PATTERN na strom sestavený ze čtyř druhů uzlů — odkaz na proměnnou, sekvence (zřetězení), alternace a skupina (závorkovaný podvzor). Každý uzel nese kvantifikátor jako tři čísla — dolní mez, horní mez (případně nekonečnou) a příznak neochotného vyhodnocování:

Každý predikát DEFINE je poté typově kontrolován vůči sloupcům partition a převeden na booleovský výraz. Dějí se přitom dvě praktické věci. Za prvé je každý sloupec odkazovaný predikátem DEFINE registrován jako součást výstupních požadavků dotazu, takže planner tyto sloupce propaguje až do fáze executoru, i když je okolní dotaz nevybírá — bez toho by runtime neměl proti čemu vyhodnocovat. Za druhé jsou proměnné, které se objevují v PATTERN, ale nikdy v DEFINE, implicitně pravdivé: odpovídají každému řádku.

3.2 Kompilace — z AST do plochého NFA

Planner mění strom z parseru na datovou strukturu, kterou executor spustí: ploché pole prvků vzoru adresované indexem. Kompilace probíhá jako šestikroková pipeline:

compile(astTree):
  1. optimalizovat AST
  2. změřit velikost a hloubku
  3. alokovat pole prvků
  4. naplnit z AST
       (přiřadit ukazatele next/jump)
  5. finalizovat — nastavit zarážku FIN
  6. označit prvky způsobilé k absorpci

Plochý tvar je zvolen z jednoduchého důvodu: executor potřebuje vzor procházet mnohokrát na partition a souvislé indexem adresovatelné pole je nejlevnější datová struktura, kterou lze procházet. Kroky 1 a 6 jsou zajímavé — krok 1, protože určuje, jak velké pole bude, a krok 6, protože rozhoduje, zda se vůbec uplatní optimalizace absorpce z §2.5.

Optimalizace AST

Optimalizace se vyplácí dvakrát: jednou ve statickém počtu prvků plochého pole a podruhé na každém řádku zpracovaném za běhu. Každá transformace redukuje stavový prostor, který runtime musí vyčíslit. Optimalizátor aplikuje osm přepisovacích pravidel po sobě, dokud se AST nepřestane měnit:

Zploštění SEQ

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

Slučování po sobě jdoucích proměnných

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

Slučování po sobě jdoucích skupin

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

Slučování po sobě jdoucích ALT

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

Absorpce prefixu/sufixu

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

Zploštění a deduplikace ALT

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

Násobení kvantifikátorů

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

Rozbalení jediného potomka

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

Násobení kvantifikátorů je jediná transformace, která vyžaduje kontrolu bezpečnosti: optimalizátor sloučí pouze ve třech bezpečných případech — oba kvantifikátory neomezené ((A+)+ → A+), vnější přesný ((A{2,3}){5} → A{10,15}), nebo potomek triviální {1,1} ((A){2,5} → A{2,5}). Jiné kombinace mohou vytvořit mezery, které by plochá forma minula — např. (A{2}){2,3} přijímá pouze {4, 6}, ale naivní A{4,6} by přijal i 5 — takže je optimalizátor ponechává netknuté.

Tvar prvku

Každý prvek plochého pole představuje jednu pozici ve vzoru. Existuje pět logických druhů: odkaz na proměnnou (jediný druh, který spotřebovává řádek); značky začátku a konce skupiny, které otevírají a uzavírají závorkovaný podvzor; značka alternace, která stojí v čele seznamu větví; a značka konce na konci vzoru.

Každý prvek nese také hloubku (úroveň zanoření skupiny), kvantifikátor (minimální a maximální počet opakování, případně nekonečný) a dva přechodové ukazatele — next, „kam jít po spotřebování tohoto prvku“, a jump, „kam přeskočit“ (alternace jím řetězí větve, začátek skupiny obchází tělo, když to kvantifikátor s nulou dovoluje, a konec skupiny se vrací zpět do těla).

Pro PATTERN ((A B)+) vypadá zkompilované pole takto:

PATTERN ((A B)+) se kompiluje na:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (otevírá skupinu; jump přeskočí
     na FIN při 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
    (uzavírá skupinu; jump cyklí zpět)

[4] FIN    vzor dokončen

Vzor se čte zleva doprava přes next, přičemž jump obstarává nelineární hrany. Na indexu 3 ukazuje jump u END zpět na index 1, čímž neomezený vnější kvantifikátor cyklí; na indexu 0 by jump u BEGIN přeskočil za END na index 4, kdyby byla skupina nepovinná. Runtime nikdy nemusí za běhu konstruovat graf — pouze sleduje tyto dva ukazatele, jak prochází polem.

Atributy jednotlivých prvků

Kromě tvaru nese každý prvek čtyři logické atributy, které řídí chování runtime na dané pozici:

Neochotný

Obrací pořadí rozvíjení kvantifikátoru. Lačné kvantifikátory zkoušejí „znovu cyklit“ před „ukončit“; neochotné kvantifikátory zkoušejí „ukončit“ jako první. Pro A+? nese proměnná; pro ((…)+?) nesou BEGIN a END skupiny.

Lze cyklit naprázdno

Nastaveno na koncích skupin, jejichž tělo je nullable ((A?)*, (A? B?)+, (A | B*)). Říká runtime, aby přidal rychlý výstup vedle běžného návratu do cyklu, aby ochrana proti cyklům neusmrtila legitimní shody ve skupinách, které mohou produkovat prázdné iterace.

V absorbovatelné oblasti

Označuje každý prvek ležící uvnitř oblasti způsobilé k absorpci — runtime jej používá ke sledování, zda je aktuální stav stále v bezpečném území.

Bod absorpčního porovnání

Označuje konkrétní prvek, kde se má provést absorpční porovnání. U jednoduchého A+ dopadá na proměnnou; u neomezené skupiny jako (A B)+ dopadá pouze na konec skupiny.

Rozdíl mezi „v oblasti“ a „bod porovnání“ je důležitý, protože absorpce dává smysl pouze v bodech, kde se iterace uzavírají. Uvnitř těla (A B)+ je runtime uprostřed iterace a počet ještě nedosáhl konečné hodnoty pro toto kolo; porovnávat zde by znamenalo porovnávat nesrovnatelné hodnoty. Stav musí dosáhnout konce skupiny, než runtime může rozhodnout. První atribut tedy říká „stále jsi v absorbovatelném území“; druhý říká „dosáhl jsi bodu porovnání — nyní zkontroluj“.

Analýza absorbovatelnosti

Krok 6 kompilace je to, co dává pravidlu „stejný osud“ z §2.5 jeho doklad v době kompilace. Rozhodnutí je vrstvené:

isAbsorbable(query):
  if SKIP mode != SKIP PAST LAST ROW
      → return false
  if konec rámce != UNBOUNDED FOLLOWING
      → return false
  if některý DEFINE závisí na match_start
      → return false
  projít AST a označit
  prvky splňující
  strukturální případ

První tři kontroly jsou na úrovni dotazu: odpovídají přesně podmínkám §2.7 (strana výstupu: režim SKIP), omezený rámec (hranice porušuje monotónnost) a §2.6 (strana dat: FIRST nebo LAST s offsetem v DEFINE). Pokud kterákoli selže, analýza nenastavuje žádné příznaky a absorpce je vypnuta v celém dotazu. Pokud všechny projdou, průchod AST přijímá tři strukturální tvary:

Případ 1 — jednoduchá neomezená proměnná

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

Každá iterace je přesně jeden řádek. Počet staršího kontextu je vždy ≥ počtu mladšího na každé sdílené pozici.

Případ 2 — skupina s pevnou délkou, neomezený vnějšek

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

Každý potomek má min == max, takže tělo je sémanticky ekvivalentní rozvinuté formě {1,1} — (A B{2})+ se chová jako (A B B)+. Každá iterace spotřebovává pevný počet řádků; dominance počtu stále platí.

Případ 3 — skupina, jejíž tělo začíná neomezenou proměnnou

(A+ B)+

Vedoucí neomezená proměnná je sama absorbovatelná (případ 1) a chrání starší kontexty. Absorpce se zastaví, jakmile stav opustí A — zbytek těla nemá záruku monotónnosti, takže příznaky jsou nastaveny pouze na A.

Strukturální případy nepokryté těmito třemi tvary jsou stejně poučné. A B+ aktuální pravidlo nedokáže absorbovat, protože vedoucí A spotřebuje řádek, než neomezená část začne, takže kontexty začínající o řádek od sebe jsou na různých pozicích uvnitř neomezeného těla. (Navazující rozšíření „PREFIX absorption“, které řeší pevné prefixy přes stínovou cestu, bylo navrženo a plánuje se pro samostatný patch.) Neochotné kvantifikátory jako A+? jsou vyloučeny konstrukcí: absorpční pravidlo předpokládá lačnou sémantiku, kdy delší shody pohlcují kratší, a neochotná shoda tento směr obrací.

Výsledkem je rozhodnutí na úrovni prvku, nikoli na úrovni vzoru. Jediný plán dotazu může mít absorpci zapnutou pro vedoucí A+ vzorů jako (A+ B+ C) nebo (A+ B+)+ — ten druhý je jen případ 3 aplikovaný na vedoucí prvek — a vypnutou pro všechno ostatní; runtime jednoduše konzultuje atribut bodu porovnání na prvku aktuálního stavu pokaždé, když zvažuje absorpční průchod. Jakmile se stav přesune do oblasti, kterou nelze absorbovat, je absorpce pro tento stav natrvalo vypnuta — přesně to, co §2.5 a §2.6 potřebují, aby platilo na algoritmické úrovni.

3.3 Navigace — výměna n-tice v jednom slotu

Výrazy DEFINE jsou běžné SQL výrazy vyhodnocované vůči řádku, ale mohou obsahovat PREV, NEXT, FIRST nebo LAST — odkazy ukazující na jiné řádky. Samotné řádky jsou již vyrovnávány v tuplestore okna; co executor stále musí řídit, je slot n-tice, ze kterého SQL strojírna výrazů čte, protože odkazy na sloupce uvnitř výrazu jsou na slot vázány v době plánování. Implementace pro každé volání navigace znovu používá jediný navigační slot: slot je před vyhodnocením vnitřního výrazu prohozen a poté obnoven, takže zbytek SQL strojírny výrazů nikdy nepozná rozdíl.

Model, který executor vidí, je malý: existuje slot aktuálního řádku, který drží řádek, vůči kterému se výraz DEFINE vyhodnocuje, a navigační slot, který runtime může dočasně přesměrovat na jiný řádek. Kolem každého volání navigace runtime nastaví navigační slot, vyhodnotí vnitřní výraz, jako by četl aktuální řádek, a poté původní řádek obnoví. Pseudokód:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos je mimo platný rozsah:
      return NULL

  uložit current_row_slot
  načíst řádek na targetPos
    do current_row_slot
  result = eval_inner_expression()
  obnovit current_row_slot
  return result

Trik spočívá v tom, že je k uložení a obnovení přesně jeden slot. Vnitřní výraz — ať už jde o aritmetiku, volání funkcí nebo jiné odkazy na sloupce — běží proti prohozenému slotu stejnou cestou vyhodnocování, jakou by použil pro aktuální řádek. Žádný alternativní evaluátor, žádný stínový slot, žádné kopírování n-tice.

Složená navigace se zplošťuje při parsování, takže k výměně stále dochází pouze jednou. PREV(FIRST(price)) je rozpoznáno jako dvoukroková navigace — „přejdi na první přiřazený řádek a poté udělej krok o řádek dříve“ — a uloženo jako jediné navigační volání složeného druhu. Runtime spočítá cílovou pozici ve dvou fázích, ale provede jen jednu výměnu slotu pro načtení finálního řádku:

compute_target_position(call):

  # relativní vůči aktuálnímu řádku
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # relativní vůči shodě
  FIRST(n):
      return matchStart + n
  LAST(n):
      return lastMatchedRow − n

  # složené: relativní vůči shodě, pak 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

  ověřit vůči odpovídajícímu rozsahu
  (rozsah shody pro vnitřní FIRST/LAST,
   rozsah partition pro vnější krok)

Cache pozic zkracuje načítání z tuplestore, když více navigačních volání v témže DEFINE cílí na stejný řádek — běžné ve výrazech jako price > PREV(price) AND volume > PREV(volume), kde obě volání směřují na předchozí řádek. Cache si ukládá pouze „posledně načtenou pozici“ a samotná výměna zůstává jedinou operací.

Klasifikace navigačních volání je příspěvkem planneru k rozhodnutí o absorpci. Planner projde každý výraz DEFINE a každou proměnnou zařadí do jedné ze dvou přihrádek podle toho, zda všechny kontexty spočítají na stejném řádku stejný boolean, nebo každý kontext spočítá vlastní. Přihrádka určuje za běhu dvě věci: jak často je proměnná vyhodnocována (jednou sdíleně nebo jednou na dotčený kontext — §3.5 fáze 1) a zda je okolní stav způsobilý ke kontextové absorpci (§2.5 vs. §2.6).

Klasifikace se provádí v době plánování a ukládá se vedle každé proměnné DEFINE, takže runtime se rozhodováním nezdržuje — při zpracování řádku jednoduše přečte přihrádku každé proměnné.

Rozpočet uchovávání

Navigace sahá do řádků, které strojírna okenní funkce jinak již proudově odeslala. Aby tyto řádky zůstaly dostupné, je executor postaven nad tuplestore, který uchovává klouzavé okno nedávných řádků; otázkou je, jak široké toto okno musí být. Patch rozhoduje v době kompilace ze dvou doplňujících se offsetů:

Rozpočet pohledu zpět

Jak daleko zpět od aktuálního řádku by jakékoli volání DEFINE mohlo dosáhnout.

Přispěvatelé: PREV, LAST s offsetem, PREV(LAST(...)), NEXT(LAST(...))

Rozpočet pohledu vpřed od začátku

Jak daleko vpřed (nebo zpět, je-li záporný) od začátku shody nejstaršího aktivního kontextu by jakékoli volání DEFINE mohlo dosáhnout.

Přispěvatelé: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

Za běhu se značka oříznutí tuplestore nastaví na dřívější ze dvou pozic — aktuální řádek minus rozpočet pohledu zpět a začátek shody nejstaršího aktivního kontextu plus rozpočet pohledu vpřed. Cokoli před touto značkou nemůže být dosaženo žádným navigačním voláním v žádném aktivním kontextu a tuplestore to může zahodit. Dva čítače Nav Mark, které EXPLAIN hlásí (§3.7) — Lookback a Lookahead — jsou naměřené vrcholy těchto dvou rozpočtů, nejhlouběji, kam musel executor v průběhu dotazu kdy dosáhnout v některém směru.

3.4 Hranice shody — SKIP, INITIAL a omezený rámec

Úspěšná shoda je zaznamenána jako malý balíček hodnot: příznak platnosti, příznak úspěchu/selhání, řádek, na kterém shoda začíná, a počet řádků, které spotřebovala. Když je příznak platnosti nastaven, následné dotazy proti executoru — „je tento řádek uvnitř shody?“ — mohou odpovědět v O(1) prozkoumáním balíčku. Délka nula je skutečným výsledkem, nikoli chybou: představuje vzor, který se shodl bez spotřebování řádku, což executor musí odlišit od „na této pozici dosud nebyla pokus o shodu“.

Klauzule AFTER MATCH SKIP rozhoduje, kde začíná další pokus o shodu. AFTER MATCH SKIP PAST LAST ROW přesouvá na řádek za koncem shody, čímž produkuje neperekrývající se výstup, který chce většina dotazů, a umožňuje absorpční optimalizaci.

AFTER MATCH SKIP TO NEXT ROW přesouvá pouze na řádek za začátkem shody, čímž umožňuje překrývající se shody; planner proto pro celý plán dotazu absorpci v tomto režimu vypíná.

Dva další cíle přeskoku, které standard rovněž definuje — AFTER MATCH SKIP TO FIRST var a AFTER MATCH SKIP TO LAST var — závisí na historii shody, kterou tento patch neuchovává. V gramatice vůbec nejsou, takže parser při jejich uvedení vyvolá obecnou syntaktickou chybu.

Totéž platí pro SEEK, alternativu specifikace k INITIAL. Při SEEK může pokus o shodu začínající na řádku R uspět na libovolném řádku od R do konce rámce, nejen na samotném R. Patch implementuje pouze INITIAL: každá potenciální shoda je zakotvena na konkrétním řádku. Parser při požadavku na SEEK vyvolá chybu. Omezené rámce mají vlastní zpracování — když uživatel napíše ROWS BETWEEN CURRENT ROW AND N FOLLOWING místo UNBOUNDED FOLLOWING, executor zkrátí každý kontext, jehož shoda dosáhla hranice, vynucením neúspěchu, a absorpce je vypnuta, protože hranice porušuje předpoklad monotónnosti, na němž absorpce stojí.

3.5 Třífázový engine po řádcích

Driver executoru pro jednotlivé řádky je volán okolní strojírnou okenní funkce, kdykoli potřebuje vědět, zda daný řádek patří do přiřazeného rámce. Driver najde nebo vytvoří kontext pro aktuální výchozí pozici, vyhodnotí každý predikát DEFINE jednou vůči aktuálnímu řádku, čímž vytvoří booleovské pole na proměnnou, a poté posune NFA o jeden řádek vpřed. Samotný krok vpřed je třífázový v pevném pořadí — Match, Absorb, Advance — obalený stejnou vnější smyčkou:

processRow(currentPos):

  # Fáze 1 — MATCH (konvergence)
  for každý kontext:
      if kontext překračuje omezený rámec:
          vynutit neúspěch (finalizovat předčasně)
          continue
      if matchStartRow se liší od
         sdílené pozice vyhodnocování:
          přehodnotit DEFINE proměnné
          závislé na začátku shody (§3.3)
      match(context, varMatched)

  # Fáze 2 — ABSORB
  if vzor je absorbovatelný:
      obnovit příznaky každého kontextu
      absorb_contexts()

  # Fáze 3 — ADVANCE (divergence)
  for každý kontext:
      advance(context, currentPos)

Pořadí není stylistickou volbou. Match musí běžet jako první, protože absorpce porovnává po-match počty; spuštění Absorb před Match by porovnávalo stavy, které mají umřít. Advance musí běžet jako poslední, protože je jedinou fází, která vytváří nové stavy — rozšiřuje každý přeživší stav přes epsilonové přechody, dokud každý nedosáhne proměnné čekající na další řádek. Spuštění Absorb po Advance by znamenalo porovnávat divergované následníky, čímž bychom minuli okamžik, kdy jsou stavy nejjasněji srovnatelné.

Fáze 1 — Match

Match je fáze „konvergence“: stavy buď přežijí s navýšeným počtem, nebo zemřou. Jemný bod je, že u proměnných nacházejících se v absorbovatelné oblasti Match také provádí malé množství postupu vpřed, aby Absorb mohl porovnávat čistě. Podmínka pokrytí se aktivuje pouze na bodu absorpčního porovnání — END neomezené skupiny — takže stavy, které právě porovnaly proměnné uprostřed iterace (jako B uvnitř (A B)+), je třeba během Match dotáhnout až k tomuto bodu porovnání; jinak Absorb nenajde nic způsobilého k porovnání a optimalizace se nikdy neuplatní.

match(context, varMatched):
  for každý stav v contextu:
      elem = pattern[state.elemIdx]
      if elem není proměnná:
          continue   # zpracovává advance

      if not varMatched[elem.varId]:
          zahodit stav   # mrtvá větev
          continue

      state.counts[elem.depth] += 1

      # Vložený postup vpřed, aby
      # další fáze mohla porovnávat
      # na bodu porovnání místo
      # uprostřed iterace.
      if elem je v oblasti, ale není
         bodem porovnání,
         a dosáhl maxima počtu,
         a elem.next je konec skupiny:

          projít řetězec END:
            inkrementovat počet vnější skupiny
            posunout state.elemIdx na END
            pokračovat, pokud stále v oblasti,
              musí-vystoupit a next je END
          (zastaví na bodu porovnání
           nebo na prvku, který lze stále cyklit)

Průchod řetězcem END je tím, co činí vnořené skupiny pevné délky absorbovatelnými. V ((A B){2})+, když B dosáhne svého maxima (B je {1,1}), musí se inkrementovat počet vnitřní skupiny; pokud i tento počet dosáhne maxima — uzavře vnitřní {2} — musí se inkrementovat i počet vnější skupiny a tak dále, dokud stav nepřistane na nejvíc vnějším bodu absorpce — END neomezené vnější skupiny (+). Provedením této práce v Match lze v Absorb porovnávat vůči kontextům, které již konsolidovaly své po-iterační počty.

Fáze 2 — Absorb

Průchod absorpce prochází kontexty od nejnovějšího (konec) k nejstaršímu (začátek). Pro každý probíhající kontext, který je plně absorbovatelný, prohledává zpět starší probíhající kontext, který jej pokrývá, a pokud takový najde, novější uvolní. Protože kontexty jsou drženy v pořadí vzniku a každý řádek vytváří nejvýše jeden kontext, „novější“ a „starší“ skutečně znamená „spuštěno později“ a „spuštěno dříve“.

absorb_contexts():
  for ctx od konce zpět:
      if ctx je dokončen
         nebo má jakýkoli neabsorbovatelný stav:
          přeskočit
      for older od ctx.prev zpět:
          if older je dokončen
             nebo nemá absorbovatelný stav:
              přeskočit
          if covered(older, ctx):
              free(ctx)
              zaznamenat délku absorpce
              break

covered(older, newer):
  for každý stav v newer:
      elem = pattern[state.elemIdx]
      if elem není bod porovnání:
          return false
      if v older neexistuje stav s:
            stejným elemIdx
            a isAbsorbable
            a older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Z toho plynou dvě mikro-rozhodnutí. Prvním je, že kontrola pokrytí okamžitě odmítne, pokud kterýkoli stav v novějším kontextu sedí kdekoli jinde než na bodu porovnání — porovnávání v bodech bez úsudku by nebylo smysluplné.

Druhým je asymetrická dvojice příznaků u každého kontextu: has-absorbable-state odpovídá na „mohl by tento kontext absorbovat novější?“ a je monotónní (může přejít pouze true→false, jak stavy umírají), zatímco all-states-absorbable odpovídá na „mohl by být tento kontext absorbován?“ a je dynamický (vrací se na true, když je odstraněn neabsorbovatelný stav). Oba příznaky se kontrolují v konstantním čase ještě před zahájením skenování pokrytí, takže absorpce platí plnou cenu pouze u kontextů, které mají reálnou šanci být absorbovány.

Fáze 3 — Advance

Advance je fáze „divergence“: každý přeživší stav je rozšířen přes epsilonové přechody, dokud každá větev nedosáhne buď proměnné čekající na další řádek, nebo zarážky FIN. Rozšíření je do hloubky a pořadí, ve kterém se procházejí sourozenecké větve, je to, co skutečně uvádí v platnost preferenční pravidlo standardu — lexikálně první větev je vždy přidána jako první a krok deduplikace při vkládání stavu tiše zahodí ekvivalentní pozdější přírůstky.

advance(context, currentPos):
  vyjmout všechny aktuální stavy;
  znovu sestavit ctx.states od nuly
  for každý stav v lexikálním pořadí:
      vyčistit bitmapu navštívených prvků
      advance_state(state)   # DFS

      # Preference: jakmile DFS dosáhne FIN,
      # zbývající stavy jsou méně preferované
      # a lze je zahodit.
      if FIN dosaženo a stavy zůstávají:
          uvolnit zbytek
          break

advance_state(state):
  jít přes state.elemIdx,
  rekurzivně přes:
    větve ALT (v pořadí),
    BEGIN (vstup do skupiny; plus volitelná
           cesta přeskoku, je-li min = 0),
    END (cyklit zpět / vystoupit / rychle vpřed —
         viz níže),
    FIN (zaznamenat matchEndRow,
         uložit matchedState a prořezat
         pozdější kontexty uvnitř rozsahu
         tohoto kandidáta — viz níže),
  zastavit u každé narazené proměnné:
      přidat stav do ctx.states
      (deduplikovat podle elemIdx + counts)

Záznam stavu, který dosáhl FIN, dělá víc než jen označuje kandidátní shodu záložkou. Při AFTER MATCH SKIP PAST LAST ROW musí další ohlásitelná shoda začít striktně za aktuální — takže ve chvíli, kdy je kandidát zaznamenán, je každý následný kontext, jehož výchozí řádek leží uvnitř rozsahu kandidáta, okamžitě prořezán, přestože kontext, který narazil na FIN, může dál hledat delší shodu lačným ústupem.

Prořezávání je bezpečné, protože ať už toto hledání skončí jakkoli (delší shoda nahradí kandidáta nebo kandidát zůstane), všechny prořezané kontexty začaly uvnitř rozsahu, který musí další ohlásitelná shoda přeskočit, a nemohly by tedy nikdy produkovat vlastní výstup.

Toto je jeden ze dvou prořezávacích kroků v okamžiku FIN — druhý, popsaný dříve v této sekci jako součást Advance, zahazuje lexikálně horší stavy uvnitř téhož kontextu.

Nejtrikovější logika na úrovni prvku se nachází v handleru END. Když je iterační počet skupiny pod dolní mezí, runtime musí cyklit zpět; když je na nebo nad horní mezí, musí vystoupit; mezi tím jsou obě možnosti platné a o tom, kterou zkusit jako první, rozhoduje lačnost kvantifikátoru:

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

  if count < elem.min:
      cyklit zpět do těla
      if elem lze cyklit naprázdno:
          # nullable tělo, viz §3.2
          klonovat také rychlý-vpřed
          stav, který skupinu opouští
          se splněným počtem
          (zachrání legitimní shody,
           které by ochrana proti
           cyklům jinak usmrtila)

  elif count >= elem.max:
      resetovat počty na této hloubce
      vystoupit přes next
      (END→END: inkrementovat
       count vnějšího END)

  else:
      # min <= count < max: rozvětvit
      sestavit výstupní stav
      (počty na této hloubce resetovat)
      if lačné:
          nejdřív cyklit, pak vystoupit
          # preferovat delší
      else (neochotné):
          nejdřív vystoupit
          if výstup dosáhl FIN:
              zahodit smyčku
              # preferovat kratší
          else cyklit jako druhé

Každý stav přidaný do kontextu prochází deduplikační kontrolou, která porovnává jeho pozici a počty se stávajícím seznamem stavů. Protože Advance zpracovává větve v pořadí DFS, stav z první větve jakékoli alternace přistává jako první — a jakákoli pozdější větev produkující stejnou pozici a počty je při vkládání odmítnuta. To je přesně to, co vyžaduje pravidlo lexikálního pořadí z §2.4, implementované na dně runtime bez zvláštního průchodu.

Skupiny, které lze cyklit naprázdno

Jemný případ, který runtime musí zneškodnit, je nullable skupina — skupina, jejíž tělo se může shodnout s nulou řádků, protože každý potomek těla je sám nepovinný. Vzory jako (A?)*, (A? B?)+ a (A | B*) mají všechny tuto vlastnost: v závislosti na datech může tělo dokončit iteraci, aniž by spotřebovalo jediný řádek. To je v principu v pořádku, ale vytváří to reálné riziko pro epsilonové rozšíření NFA. Pokud tělo produkuje prázdnou shodu, prvek END cyklí zpět na BEGIN, tělo opět produkuje prázdnou shodu, BEGIN cyklí na END a tak dále. Bez něčeho, co to zastaví, by DFS Advance nikdy neskončilo.

Runtime to zastavuje bitmapou navštívených prvků (jeden bit na prvek vzoru), vyčištěnou před DFS expanzí každého stavu: jakmile je libovolný prvek navštíven podruhé v rámci téže expanze, tato cesta je opuštěna. Ochrana proti cyklům je bezpodmínečná a levná, ale má vedlejší účinek — může také opustit cesty, které by měly dosáhnout dolní meze přes legitimní prázdné iterace. Vezměme (A?){2,3} bez jediného A shodujícího se kdekoli v proudu řádků:

požadované chování:
  iter 1: A? se shodne s 0 řádky
          → END, count = 1 (pod min)
  iter 2: A? se shodne s 0 řádky
          → END, count = 2 (splňuje min)
  vystoupit s nulovou délkou shody

co dělá samotná ochrana proti cyklům:
  iter 1: A? přeskočeno → END, count = 1
          → cyklit zpět na BEGIN
  iter 2: BEGIN již navštíveno
          → DFS přerušeno
  count nikdy nedosáhne min
  → shoda selže (nesprávné)

Oprava se rozhoduje v době kompilace a uplatňuje za běhu. Kdykoli planner vidí skupinu, jejíž tělo je nullable, označí prvek END této skupiny jako lze cyklit naprázdno. Za běhu, když se handler END chystá cyklit zpět, protože iterační počet je stále pod dolní mezí, prázdně-cyklovatelný štítek mu říká, aby vedle běžné cesty zpětného cyklu klonoval další rychlý-vpřed stav:

advance_end (count pod min):

  primární cesta:
    cyklit zpět do těla
    (nechává dveře otevřené pro skutečnou,
     neprázdnou shodu v další
     iteraci)

  if elem lze cyklit naprázdno:
    cesta rychle vpřed:
      resetovat počet této hloubky
      opustit skupinu přes next,
      zacházet se zbylými povinnými
      iteracemi jako s prázdnými shodami

Obě cesty hrají komplementární role. Primární zpětný cyklus zachytává případ, kdy tělo má později ještě skutečné shody — např. u (A?){2,3} s daty, kde A odpovídá až na pozdějších řádcích, zpětný cyklus umožňuje druhé a třetí iteraci nalézt neprázdné shody. Rychlý-vpřed zachytává případ, kdy tělo nikdy nic neprodukuje: obchází ochranu proti cyklům úplným výstupem ze skupiny, prohlásí „zbytek povinných iterací je prázdný“ a umožňuje shodě uspět s tělem nulové délky. Oba stavy jsou přidány do kontextu; vyhrává ten, který se úspěšně rozšíří, a deduplikační kontrola při vkládání brání kterékoli cestě vytvořit více stavů, než kolik jí přísluší.

Kromě ochrany proti cyklům jeden další startovací trik rozlišuje nulové výsledky hned na začátku kontextu. Krok vytvoření kontextu při každém potenciálním výchozím řádku spouští počáteční advance přes epsilonové přechody před spotřebováním jakéhokoli řádku, s použitím pozice o jeden řádek před skutečným startem. Každá cesta, která dosáhne zarážky FIN pouze přes epsilonové přechody — bez spotřebování řádku — proto produkuje koncovou pozici menší než výchozí pozici; tato souřadnice se záporným rozsahem, ve spojení s tím, zda bylo FIN skutečně dosaženo, kóduje rozdíl mezi prázdnou shodou (přijatá shoda délky 0) a nepřiřazeným startem, aniž by byl potřebný samostatný příznak.

3.6 Jak zůstává stavový prostor omezený

Linearita runtime není výsledkem jediné optimalizace. Je kumulativním účinkem vrstvené sady prořezávacích pravidel, kde každé zachytává jinou příčinu růstu stavového prostoru v jiném bodě cyklu po řádku. Některá se rozhodují v době kompilace a za běhu jsou pouze konzultována; jiná se aktivují dynamicky. Některá zabíjejí jednotlivé stavy; jiná celé kontexty. Sekce výše každé z nich uvedly v kontextu; tabulka níže je shrnuje na jedné stránce.

Selhaný predikát Match

Stavy proměnných, jejichž DEFINE vyhodnotil na aktuálním řádku false — mrtvé větve.

Vložený posun řetězcem END Match

Proměnné, které dosáhly maxima počtu a jinak by stav opustily uprostřed iterace; posunuty přes konce skupin pevné délky, aby absorpce mohla porovnávat ve správném bodě.

Kontextová absorpce Absorb

Novější kontexty, jejichž každý stav je pokryt stavem staršího kontextu s vyšším počtem — viz §2.5 pro koncepční pravidlo, §3.2 pro způsobilost v době kompilace, §3.5 pro kontrolu po dvojicích.

Deduplikace stavů Advance

Stavy dosažené přes různé větve DFS, které končí na stejné pozici se stejnými počty — přežívá pouze první (lexikálně nejdřívější); pozdější ekvivalenty jsou tiše zahozeny, čímž se vynucuje i preference (§2.4).

Předčasné ukončení FIN (v rámci kontextu) Advance

Stavy stále čekající ve frontě DFS, když jedna větev dosáhne FIN — podle lexikálního pořadí jsou všechny zbývající stavy méně preferované a lze je okamžitě zahodit.

Prořezávání kandidátní shody (napříč kontexty) Při FIN

Jiné kontexty, jejichž výchozí řádek leží uvnitř rozsahu kandidátní shody — kontext, který narazil na FIN, může dál hledat delší shodu (lačný ústup), ale při AFTER MATCH SKIP PAST LAST ROW už žádný kontext uvnitř rozsahu kandidáta nemůže produkovat ohlasitelný výstup, bez ohledu na to, jak toto hledání skončí, a je okamžitě prořezán.

Ochrana proti cyklům Advance

Epsilonové expanze, které znovu navštíví stejný prvek vzoru v rámci téhož DFS — v nullable skupinách by jinak cyklily donekonečna.

Rychle vpřed při prázdném cyklu Advance

Legitimní shody prázdných iterací, které by v nullable skupinách ochrana proti cyklům usmrtila — obchází cyklus výstupem ze skupiny, přičemž zbývající povinné iterace prohlásí za prázdné.

Mez omezeného rámce Match

Kontexty, jejichž shoda dosáhla uživatelem zadané horní hranice rámce — vynucené k neúspěchu, aby nemohly přesáhnout (§3.4).

Čtení záznamů podle jejich fázového odznaku sleduje životní cyklus kontextu: prořezávání se aktivuje na každém řádku ve třech hlavních fázích (Match, Absorb, Advance) a znovu při dokončení shody (Při FIN). Čtení popisů naopak seskupuje pravidla podle toho, na co cílí: mrtvé větve, nadbytečné kontexty, ekvivalentní stavy, nekonečné cykly a překročení uživatelem stanovených hranic.

Žádné jediné pravidlo by samo o sobě nestačilo. Samotná ochrana proti cyklům by usmrtila legitimní shody v nullable skupinách; samotný rychlý-vpřed při prázdném cyklu by nezastavil nekonečné epsilonové cykly; samotná absorpce by nad-konsolidovala, když DEFINE odkazuje na začátek shody; samotná deduplikace by neodstranila nadbytečné kontexty, pouze nadbytečné stavy. Runtime zůstává lineární v důležitých případech — PATTERN (A+ B+ C+ D) na 100 000 řádcích, benchmark v panelu ③ posteru — pouze proto, že každá vrstva zachytává to, co vrstvy nad ní minou.

3.7 Výstup EXPLAIN

EXPLAIN ANALYZE nad dotazem s RPR zobrazuje statistiky na úrovni NFA, které u běžných okenních funkcí nejsou. Vedle okenního operátoru jsou vydávány tři skupiny čítačů:

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
  (pouze když dotaz používá FIRST,
   PREV(FIRST(...)) nebo NEXT(FIRST(...)))

Peak a total jsou přímou instrumentací runtime: kolik stavů bylo kdy současně aktivních, kolik bylo za životnost dotazu vytvořeno a kolik bylo deduplikací sloučeno. Histogramy délek shody oddělují čtyři výsledky — úspěšné shody, selhané pokusy o shodu, absorbované kontexty a kontexty, které byly prořezány (přeskočeny), aniž by byly vyhodnoceny — a jejich hlášení s min/max/avg činí výkonnostní patologie viditelné na první pohled: zdravý běh ukazuje většinu kontextů jako shodnuté nebo absorbované, s malými délkami nešodných.

Dva čítače Nav Mark hlásí rozpočet uchovávání tuplestore, který §3.3 odvozuje v době kompilace. Lookback je nejhlubší dosah zpět přes PREV, LAST s offsetem a složené formy s vnitřním LAST; Lookahead je nejhlubší dosah vpřed (nebo zpět, je-li záporný) měřený od začátku shody nejstaršího aktivního kontextu, kterým přispívá FIRST a složené formy s vnitřním FIRST.

Každý čítač se vypíše jako pevné celé číslo, je-li offset konstantní, jako „runtime“, je-li offset nekonstantní výraz, který je třeba vyhodnocovat při každém volání, a „retain all“, potřebuje-li runtime neomezený rozpočet. Lookahead se vypisuje pouze tehdy, používá-li dotaz skutečně navigaci relativní k začátku shody.

Společně tyto čítače umožňují ladit výkon RPR bez nutnosti připojovat gdb k backendu.

Kromě čítačů EXPLAIN také věrně reprodukuje původní klauzule PATTERN a DEFINE, včetně neochotných kvantifikátorů, opakování skupin a možnosti AFTER MATCH SKIP. Implementace se snaží, aby tato cesta tam a zpět byla stabilní, takže pg_dump a pg_upgrade mohou zachovat objekty RPR bez sémantického posunu — regresní sada pod rpr_explain to ověřuje případ po případu (viz §4).

§4. Testy — mapa pokrytí

Patch je dodáván s pěti regresními sadami, které dohromady prověřují každou vrstvu popsanou v §3 — zhruba 13 000 řádků SQL, každá sada zaměřená na jinou oblast. Rozdělení je záměrné: oddělení záležitostí parseru, správnosti runtime, interakcí planneru a formátování výstupu do samostatných souborů usnadňuje lokalizaci selhání a brání tomu, aby nesouvisející změna v jedné vrstvě nechtěně neplatila testy v jiné. Pět sad je:

rpr

Sémantika dotazů od začátku do konce — realistické okenní scénáře nad syntetickými daty akcií (V-tvar, W-tvar, po sobě jdoucí růsty, obraty).

rpr_base

Vrstva parseru — přijímání klíčových slov, syntaktické tvary, kvantifikátory, parsování navigace, chybové zprávy a stabilita cesty pg_dump/pg_upgrade tam a zpět.

rpr_nfa

NFA runtime — třífázová smyčka, absorpce ve všech absorbovatelných tvarech a hraniční případy životního cyklu kontextu.

rpr_explain

Formátování výstupu — statistiky NFA, deparse vzoru, citace identifikátorů, stabilita formátu napříč znovunačtením.

rpr_integration

Interakce planneru — pojistky bránící nesouvisejícím okenním optimalizacím v poškození sémantiky RPR.

4.1 rpr — scénáře od začátku do konce

Scénářová sada je veřejnou tváří testovacího setu: používá syntetický dataset cen akcií o asi 1 600 řádcích a spouští nad ním realistické dotazy — zotavení ve tvaru V, W-tvar (dvojité dno), po sobě jdoucí růsty a poklesy, obratové vzory, partitioning podle více symbolů. Je jedinou sadou, kde se vstupy a výstupy čtou jako dotazy, které by uživatel skutečně napsal; ostatní jsou záměrně redukční, zaměřené vždy na jednu vrstvu.

Protože tyto dotazy kombinují všechny vrstvy (parser, planner, executor, EXPLAIN), jedno selhání v rpr jen zřídka napoví, kde chyba leží. Čtyři následující sady tvoří bisekci: selhání v rpr a procházející rpr_base vylučuje parser; navíc procházející rpr_nfa zužuje problém na tvary dat specifické pro scénář; navíc procházející rpr_integration vylučuje zásah planneru; a jakýkoli posun v deparse se projeví v rpr_explain.

4.2 rpr_base — povrch parseru

Základní sada je největší a je největší z nějakého důvodu: zodpovídá za prokázání, že každý legální kus syntaxe z §1.2 skutečně parsuje, každý nelegální kus z §1.3 je odmítnut s užitečnou chybou a každá přijatá forma přežije cestu serializace tam a zpět. Většina je formována jako krátké zaměřené úryvky — po jednom pro každou syntaktickou funkci — místo dlouhých realistických dotazů, protože cílem je pokrytí, nikoli scénářová realističnost.

Serializační testy si zaslouží zvláštní pozornost. Objekty RPR (pohledy, materializované pohledy, výstup pg_dump) musí cestou přes reprezentaci v katalogu projít bez sémantického posunu, včetně jemností jako příznak neochotnosti na kvantifikátoru nebo přesná forma složeného navigačního výrazu. Malá sada objektů specifických pro serializaci (pohledy rpr_serial_v* a jejich podkladové tabulky) je na konci běhu záměrně ponechána na místě, aby si je mohla okolní regresní infrastruktura převzít a uplatnit nad nimi pg_dump a pg_upgrade. Zbytek lešení testů se ruší jako obvykle. Chyby zachycené tímto způsobem (jako ztráta příznaku neochotnosti při deparse a opětovném parsování) se projeví pouze při kompletním cyklu od konce do konce.

4.3 rpr_nfa — runtime engine

Toto je sada, která prověřuje každý mechanismus popsaný v §3.5 a §3.6. Její testy se řídí konzistentním vzorcem: vstupní tabulka, jejíž řádky jsou explicitní booleovská pole deklarující, které proměnné DEFINE odpovídají na každém řádku, ve dvojici se vzorem zkoumajícím konkrétní chování runtime. Idiom booleovských polí odpojuje test runtime od strojírny vyhodnocování DEFINE — testuje se „dány proměnné, které zde odpovídají, produkuje smyčka NFA očekávaný rozsah shody?“, nikoli „počítá evaluátor výrazu DEFINE tyto booleany správně?“ Evaluátor DEFINE je testován jinde (rpr_base pro parsování, rpr pro chování od konce do konce).

Typický testovací fixture vypadá takto — sloupec polí názvů proměnných, kde každý záznam říká, které proměnné DEFINE se na daném řádku aktivují, a vzor, jehož klauzule DEFINE testují přímo na tyto názvy:

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

Čtení sloupce polí shora dolů je čtením testovacího scénáře přímo. Řádky 2 a 3 nesou obě jména — A i B se tam aktivují, takže NFA má skutečnou volbu, kde se přepnout z větve A na větev B. Očekávaná shoda (A na řádcích 1–3 následované B na řádku 4 podle lačné preference standardu) je dána výhradně těmito příznaky, bez vyhodnocování výrazů, které by zde mělo nějaký dopad — = ANY je jen triviální vrstva, která zpřístupňuje sloupec polí pro DEFINE, nikoli to, co test prověřuje. Zápis téhož scénáře s číselným predikátem (price > PREV(price) apod.) by zamotal test NFA s chováním evaluátoru predikátů; idiom polí oboje udržuje čistě oddělené a selhání zde ukazuje přímo na smyčku NFA.

Pokrytí absorpce je obzvlášť důkladné, protože absorpce je optimalizace, která nejpravděpodobněji tiše produkuje chybné odpovědi, pokud se uplatní tam, kde by neměla. Testy pokrývají každý tvar z analýzy případů v §3.2:

• jednoduchá neomezená proměnná (A+) — kanonické sloučení N na 1;
• skupiny pevné délky ((A B)+, (A B{2})+, třístupňově vnořené ((A (B C){2}){2})+);
• vedoucí neomezená proměnná s pevným sufixem (A+ B) — absorpční příznaky nese pouze vedoucí A+, sufix ne;
• absorpce na úrovni větve uvnitř alternace (B+ C | B+ D);
• více neomezených proměnných (A+ B+) — absorbovatelná je pouze ta vedoucí;
• neochotné kvantifikátory (A+?) — ověřeno, že jsou z absorpce vyloučeny;
• nevedoucí neomezené (A B+) — ověřeno, že je vyloučeno.

Kromě absorpce sada pokrývá životní cyklus kontextu: překrývající se kontexty při AFTER MATCH SKIP TO NEXT ROW, úklid neúspěšných kontextů uprostřed proudu, finalizaci nedokončených kontextů na konci partition a kontexty vstupující až poté, co byl v hlavním kontextu již zaznamenán kandidát na shodu. Každý z těchto případů odpovídá konkrétnímu prořezávacímu pravidlu v §3.6 a testy jsou napsány tak, aby hlasitě selhaly, pokud pravidlo selže (buď ponecháním nadbytečných kontextů naživu, nebo zabitím kontextu, který měl produkovat výstup).

4.4 rpr_explain — stabilita výstupu

Výstup EXPLAIN je součástí uživatelského kontraktu — nástroje třetích stran (autodoplnění psql, monitorovací dashboardy, scrapery logů) jej parsují a zdánlivě kosmetické změny je mohou rozbít. Sada rpr_explain ověřuje tři věci:

• Čítače NFA se objevují na správném místě — statistiky pro každý WindowAgg (peak/total/merged states, peak/total/pruned contexts, histogramy délek pro matched/mismatched/absorbed/skipped, Nav Mark Lookback a — pokud se používá navigace relativní k začátku shody — Nav Mark Lookahead) se všechny zobrazují pod EXPLAIN ANALYZE s dokumentovanými popisky.
• Vzory se deparsují správně — každý tvar kvantifikátoru včetně neochotných variant a omezených forem; každá alternace; každá skupina; každá forma AFTER MATCH SKIP; INITIAL; navigační volání s offsety; složená navigace. Deparseovaný text musí beze změny projít zpět parserem.
• Citace identifikátorů je správná — proměnné vzoru a výrazy DEFINE se vydávají se stejnými pravidly citace jako běžné SQL identifikátory, takže neobvyklé názvy proměnných nerozbíjejí výstup pg_dump.

Stejně jako rpr_base tato sada záměrně ponechává své objekty na konci běhu na místě, takže pokrytí pg_dump a pg_upgrade se vztahuje i na artefakty na straně explain.

4.5 rpr_integration — interakce s plannerem

Planner PostgreSQL má mnoho optimalizací operujících na okenních dotazech — kanonikalizace rámce, pushdown run-condition, deduplikace identických oken, projekce nepoužitého výstupu, inverzní přechody pohyblivé agregace — a každá z nich byla navržena bez ohledu na RPR. Většinu z nich není bezpečné aplikovat, když má okno klauzuli PATTERN: rámec je součástí kontraktu shody, přiřazený výstup již není zřejmě monotónní a dvě okna se stejnou specifikací, ale různými DEFINE produkují skutečně odlišné výsledky. Integrační sada ověřuje, že každá z těchto optimalizací je pro okna RPR správně vypnuta nebo obejita:

Kanonikalizace rámce

Planner běžně přepisuje ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING na ROWS UNBOUNDED PRECEDING pro monotónní agregace. Rámec RPR je rozsahem shody, nikoli agregačním oknem, a musí zůstat doslovný.

Pushdown run-condition

Monotónní filtr WHERE nad výstupem okenní funkce lze běžně zatlačit do okenního operátoru jako stop-podmínku. Pro RPR by to předčasně ukončilo shodu vzorů, případně by ořízlo shody uprostřed rozšiřování.

Deduplikace oken (RPR vs. ne-RPR)

Dvě okna s identickým ORDER BY a rámcem by se běžně sloučila do jednoho. Okno RPR a okno bez RPR nemohou nikdy sdílet stav, protože strana RPR nese výsledky shody.

Deduplikace oken (odlišné DEFINE)

Dvě okna RPR se stejným PATTERN, ale různými klauzulemi DEFINE produkují různé shody a musí zůstat oddělena, i když je jejich strukturální tvar identický.

Projekce nepoužitého výstupu

I když okolní dotaz nikdy nečte výstup okna pro jednotlivé řádky, nelze okno RPR odstranit: vedlejší účinky vyhodnocovače vzorů (které řádky jsou uvnitř které shody) jsou vstupem pro výpočty redukovaného rámce jinde v plánu.

Inverzní přechody pohyblivé agregace

Okenní agregace s inverzní přechodovou funkcí lze běžně vyhodnocovat inkrementálně, jak se rámec pohybuje. Redukovaný rámec RPR není klouzavým oknem; cesta inverzních přechodů by produkovala nesprávné výsledky.

Vzor napříč těmito testy je stejný: každý poskytuje výchozí stav bez RPR, který spouští optimalizaci (a ověřuje, že EXPLAIN ukazuje její aplikaci), pak spouští dotaz RPR strukturálně podobného tvaru a ověřuje, že optimalizace není aplikována. Obě poloviny dohromady prokazují, že pojistka v planneru skutečně pracuje a neschvaluje každý dotaz bez skutečného ověření.

Tato sada je také důvodem, proč je §3.4 krátká. Mechanismy „hranic shody“ — redukovaný rámec, SKIP, INITIAL, mez omezeného rámce — jsou testovány operačně jinde; co rpr_integration ověřuje, je, že do nich žádná jiná optimalizační fáze cestou nezasahuje. Procházející rpr_integration je to, co zbytku sad umožňuje důvěřovat, že jejich vstupy se k executoru dostanou nedotčené.