2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition Do hloubky

Komentovaná prohlídka ISO/IEC 19075-5 · SQL R020 v PostgreSQL — co jsme vytvořili, co zatím chybí a jak to ve skutečnosti běží.

Doprovod k posteru vystavenému na PGConf.dev 2026.
Prolistujte standard, projděte si propracované příklady, prohlédněte si návrh a pak si vyzkoušejte živý simulátor NFA s vlastními vzory.
Diskuse: vlákno pgsql-hackers · poslední patch (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

Předem přeloženo AI — možné chyby.

§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í mají značnou část syntaxe i sémantiky společnou (19075-5 uvádí v §6.3.3 několik rozdílů specifických pro R020), 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 přidá klauzule do specifikace okna, jejíž rámec je ROWS BETWEEN CURRENT ROW AND …: 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 volitelné AFTER MATCH SKIP (výchozí PAST LAST ROW) ří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; nejvýše 240 různých proměnných vzoru.
Rámec okna
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING nebo ROWS BETWEEN CURRENT ROW AND n FOLLOWING s n ≥ 1 (19075-5 §6.10.2); jakýkoli jiný rámec je odmítnut a jediné přijímané vyloučení je EXCLUDE NO OTHERS.
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 se vyhodnocuje 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.
Navigační názvy
PREV, NEXT, FIRST a LAST zapsané jako nekvalifikovaná volání uvnitř DEFINE vždy znamenají navigaci; uživatelská funkce stejného jména tam musí být kvalifikována schématem.
Navigační argumenty
U PREV, NEXT, FIRST a LAST musí vnitřní argument obsahovat alespoň jeden odkaz na sloupec a offset musí být konstanta v době běhu.
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 FIRST var a AFTER MATCH SKIP TO [LAST] var (holé SKIP TO var znamená SKIP TO LAST var). Ty také závisí na historii shody, protože executor musí být schopen ukázat na řádek namapovaný na danou proměnnou 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 {- … -}, operátor PERMUTE nezávislý na pořadí a agregační funkce a poddotazy v DEFINE, obojí v současnosti odmítané (agregace kvalifikovaná proměnnou by také potřebovala historii shody).

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 na kterémkoli řádku od aktuálního řádku až po konec úplného rámce okna (na rozdíl od INITIAL).
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 ALL ROWS PER MATCH. Tato volba se na okna nevztahuje (19075-5 §6.3.3 (4)), takže v okně je syntaxe povolena (§6.13), ale nemá žádný výstup, na který by působila.
Regex: ()
Prázdný vzor — odpovídá prázdné posloupnosti.
PERMUTE(...)
Shoda nezávislá na pořadí napříč vyjmenovanými proměnnými. Klíčové slovo je rozpoznáno a odmítnuto („PERMUTE is not supported“); permute zůstává použitelné jako název proměnné vzoru.
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; agregace kvalifikovaná proměnnou, jako AVG(B.Price), závisí na stejné historii každé shody, kterou vyžadují MEASURES/CLASSIFIER(), zatímco nekvalifikovaná agregace pokrývá všechny dosavadní řádky shody.
Poddotazy v DEFINE
Každý poddotaz v DEFINE je odmítnut. Standard povoluje takový, který neprovádí row pattern recognition a neodkazuje na žádnou proměnnou vzoru řádků; patch zatím odmítá víc, než musí.

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ů (patch jde dál a odmítá všechny poddotazy v DEFINE, jak je uvedeno výše); a RPR nesmí být použito uvnitř rekurzivního dotazu. Patch vynucuje pravidlo o vnějších odkazech („cannot use outer query column in DEFINE clause“) a pravidlo o rekurzi, to druhé pro každý prvek klauzule WITH RECURSIVE. Odmítá také volatilní funkce a odkazy na celý řádek v DEFINE.

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

Původ. Seznamy implementovaných a neimplementovaných položek v této sekci odrážejí aktuální stav série patchů — konkrétně v55 (17. 11. 2026).

§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 pět propracovaných příkladů: jednu shodu (pohyb NFA), alternaci, kontextovou absorpci v jednoduchém případě a dva případy, kdy je absorpce vypnuta.

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.

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 se sbalí na jeden stav na symbol; řádek může současně splňovat více predikátů DEFINE, takže více stavů zůstává paralelně aktivních.

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 (výchozí n = 1). Pohled vpřed; v okenní formě neobvyklý, protože okno je monotónní.
FIRST(expr [, n])
Řádek n řádků za prvním řádkem aktuální shody (výchozí n = 0, tedy samotný první řádek). „Porovnej s řádkem, který tuto shodu zahájil.“
LAST(expr [, n])
Řádek n řádků před posledním přiřazeným řádkem (výchozí n = 0). Uvnitř DEFINE je posledním přiřazeným řádkem aktuální řádek, takže LAST(price) čte aktuální řádek.

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 řádku, který čte FIRST(expr, n) (výchozí n = 0, 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 řádku, který čte FIRST(expr, n). Sahá dál do shody bez závislosti na aktuálním řádku.
PREV(LAST(expr [, n]) [, m])
Krok m řádků zpět od řádku, který čte LAST(expr, n). „Porovnej s řádkem krátce před nejnověji přiřazeným řádkem.“
NEXT(LAST(expr [, n]) [, m])
Krok m řádků vpřed od řádku, který čte LAST(expr, n).

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. Prosté PREV a NEXT jsou relativní k aktuálnímu řádku a jsou vždy bezpečné; FIRST a varianty LAST s offsetem, samostatně i uvnitř složeného PREV/NEXT, jsou relativní k hranicím shody, což se prolíná s kontextovou absorpcí: planner pak absorpci vypne pro celý vzor. Mechanismus této interakce je tématem §2.6.

2.3 Propracovaný příklad 1 — pohyb NFA

Cíl tohoto příkladuUkázat vývoj stavu NFA řádek po řádku na jednoduchém, neabsorbujícím vzoru. Trasa sleduje kontext zahájený na řádku 0; kontexty zahájené na řádcích 1–4 běží souběžně s ním a jsou zahozeny pomocí SKIP PAST LAST ROW, jakmile je jeho shoda zaznamenána.
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:

ŘádekCenaPravdivé proměnnéAkce
0100STARTNový kontext. START odpovídá a okamžitě vystupuje (max=1); stav postupuje na UP+.
1110START, UPUP odpovídá. Posun se větví: jeden stav cyklí v UP, druhý vystupuje do DOWN+.
2120START, UPUP odpovídá v cyklícím stavu a opět se větví. Stav DOWN z řádku 1 umírá (120 ≮ 110).
3115START, DOWNUP selže v cyklícím stavu a umírá. Stav DOWN z řádku 2 odpovídá. Posun se větví: cyklus v DOWN a výstup do #FIN — je zaznamenán kandidát na shodu přes řádky 0–3.
4108START, DOWNDOWN odpovídá v cyklícím stavu a opět se větví; nový kandidát FIN přes řádky 0–4 nahrazuje ten kratší.
5130START, UPCyklící stav DOWN selže (130 ≮ 108). Protože v tomto kontextu nezbývá žádný aktivní stav, je zaznamenaný kandidát (řádky 0–4) finalizován jako shoda. Další pokus začíná na řádku 5; START odpovídá, ale partition končí dříve, než přijde jakýkoli UP.

Klíčová poznámka: na řádku 3 řádek splňuje jak START (vždy pravdivé), tak DOWN, ale START má význam jen pro kontext začínající na řádku 3; v tomto kontextu cyklící stav UP umírá a postupuje pouze stav čekající na 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 poslední kandidát FIN (řádky 0–4) — vytvořený, když DOWN vystoupil na řádku 4, a nahrazující kandidáta z řádku 3 — 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:

ŘádekCenastart_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

Řá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í

Cíl tohoto příkladuUkázat, jak jeden kontext nese více paralelních stavů, když jeden řádek splňuje více než jednu alternativu — a jak standard řeší remízy.

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á v pořadí vzoru, dřívější větev jako první.

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. Oba pak postoupí na DONE, kde se setkají.

ŘádekPravdivé proměnnéAktivní stavy
RUP, HIGHStav A (větev UP) i stav B (větev HIGH) postoupí na DONE se stejnými počty; B je duplikátem A a je zahozen
R+1DONEStav A odpovídá DONE a dosáhne #FIN

V pojmech standardu obě větve produkují shodu stejné délky nad stejnými řádky, což dává 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. Executor to vynucuje na řádku R, nikoli na FIN: stav větve UP přidá jako první, takže nfa_append_state_unique() jej ponechá a identický stav větve HIGH zahodí.

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)

Cíl tohoto příkladuUkázat, proč se naivní celková práce se stavy O(n²) při absorpci mění na O(n), s O(1) aktivními kontexty.

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

ŘádekNaivní kontextyS absorpcí
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 absorbován
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ět kontextůC1[A:5]

Počet aktivních kontextů klesá z O(n) na O(1), takže celkový součet přes partition klesá z O(n²) na O(n). Absorpční pravidlo, které toto zahození ospravedlňuje, je při neomezeném kvantifikátoru přímočaré:

Absorpční pravidlo. Dva kontexty, jejichž aktivní stav je na stejném prvku vzoru, kde starší kontext má počet ≥ novější, mají při neomezeném kvantifikátoru identickou budoucnost. Novější kontext lze zahodit; jakoukoli shodu, kterou by nakonec našel, najde starší kontext stejně dlouhou nebo delší.

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:

DenCenaC1 — start v Po
price > PREV(price)
C2 — start v Út
price > PREV(price)
Po$100——
Út$108$108 > $100 ✓ (právě započato)—
St$112$112 > $108 ✓$112 > $108 ✓ (právě započato)
Čt$116$116 > $112 ✓$116 > $112 ✓
Pá$110$110 > $116 ✗ — finalizovat$110 > $116 ✗ — finalizovat
Stejný osud Na každém řádku, který C1 a C2 sdílejí, vyhodnocují identické výrazy a produkují identické výsledky — a v pátek umírají při zcela stejném porovnání. Jakoukoli budoucnost má C2, má i C1. Absorpcí C2 do C1 se nic neztrácí.

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

Cíl tohoto příkladuUkázat, co se mění, když DEFINE odkazuje na FIRST — absorpční pravidlo již neplatí a planner pro daný vzor absorpci vypne.

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

DenCenaC1 — start v Po
FIRST = $100
price < $100 + 10
C2 — start v Út
FIRST = $108
price < $108 + 10
Po$100$100 < $110 ✓—
Út$108$108 < $110 ✓$108 < $118 ✓ (právě započato)
St$112$112 < $110 ✗ — finalizovat Po–Út$112 < $118 ✓
Čt$116—$116 < $118 ✓
Pá$110—$110 < $118 ✓ (stále běží)
Odlišné osudy C1 umírá ve středu s dvoudenním během (Po–Út); C2 by sám o sobě pokračoval až do pátku. Stejné ceny, stejná forma otázky — avšak různé stropy odvozené z jejich vlastních počátků shody. Tentýž den dospěly oba kontexty k opačným závěrům.

Při absorpci by se C2 v úterý sloučil s C1 — sloučený kontext si ponechává jen strop C1 ($110), takže odlišný pohled C2 (strop $118, čtyřdenní běh až do pátku) budoucnost C1 nepokrývá. V tomto konkrétním týdnu se výstup shodou okolností nezmění: C1 zaznamená Po–Út, C2 začal uvnitř této shody a je zahozen pomocí SKIP PAST LAST ROW a další pokus začíná ve středu s vlastním stropem ($122) a odpovídá St–Pá. Obecně však výsledek DEFINE dřívějšího kontextu již nezahrnuje výsledek pozdějšího, takže porovnání počtů, na němž absorpce stojí, je neplatné. 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 níže rozšiřuje pravý dolní panel posteru („② Navigation“) o složené formy a shrnuje, které navigační formy vytvářejí závislost na začátku shody:

NavigaceZávislost na začátku shodyAbsorbovatelné?
PREV, NEXTžádnáano
LAST (bez offsetu)žádnáano
LAST s offsetemkontrola hranicne
FIRST (libovolné)přímáne
Složená (vnitřní FIRST)přímáne
Složená (vnitřní LAST, bez offsetu)žádnáano
Složená (vnitřní LAST s offsetem)kontrola hranicne

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 zaručeně nepokrývá, takže zahození kteréhokoli z nich již nelze prokázat jako bezpečné.

Planner toto rozlišení zjistí v době kompilace a zapne nebo vypne absorpci pro celý vzor; když je vypnutá, runtime nese cenu více kontextů. Benchmark v panelu ③ posteru nepoužívá FIRST, takže absorpce zůstává zapnutá, a proto PostgreSQL zůstává lineární jak v případě úspěchu, tak v případě selhání.

Čí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 zhruba O(n), jakmile je shoda potvrzena, a PostgreSQL vede zhruba 16× až 33× (údaje Trino již nezahrnují start JVM).

U vzoru se selháním (A+ B+ C+ E) Trino, kterému absorpce zřejmě chybí, sleduje každý potenciální začátek shody a degraduje ještě rychleji než O(n²) (zhruba 56× delší čas pro 5× více řádků); 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

Cíl tohoto příkladuUkázat druhý způsob, jakým absorpce může selhat: ne proto, že se predikát rozštěpí, ale proto, že výstupní sémantika vyžaduje, aby každá shoda byla hlášena samostatně.

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.

ŘádekSKIP PAST LAST ROWSKIP TO NEXT ROW
0shoda začíná; řádky 0–4 budou jedinou shodoushoda začíná na řádku 0
1(uvnitř shody 0)shoda začíná na řádku 1 — musí zůstat naživu
2(uvnitř shody 0)shoda začíná na řádku 2 — musí zůstat naživu
3(uvnitř shody 0)shoda začíná na řádku 3 — musí zůstat naživu
4shoda 0 finalizována (řádky 0–4)finalizováno pět shod: 0–4, 1–4, 2–4, 3–4, 4–4
Odlišný výstup, odlišné osudy Při AFTER MATCH SKIP TO NEXT ROW je každý později začínající kontext vlastním výstupním řádkem. Dva kontexty na stejném prvku vzoru už nejsou nadbyteční — jsou oba požadovaným výstupem a zahození jednoho by tiše ztratilo shodu, o kterou uživatel požádal.

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 dva způsoby, jimiž sémantika dotazu absorpci vylučuje:

Strana dat · §2.6
Predikát se v různých kontextech vyhodnocuje odlišně.
Spouštěno FIRST nebo LAST s offsetem v DEFINE.
Strana výstupu · §2.7
Výstup vyžaduje každý začátek shody jako samostatný řádek.
Spouštěno AFTER MATCH SKIP TO NEXT ROW.

Kterákoli z těchto podmínek stačí k vypnutí absorpce pro celý vzor, a stejně tak rámec, který nekončí na UNBOUNDED FOLLOWING. Když není v platnosti žádná z nich — výchozí AFTER MATCH SKIP PAST LAST ROW, neomezený konec rámce a podmínky DEFINE, které používají pouze PREV, NEXT nebo holé LAST — je absorpce zapnutá, ale jen pro stavy v absorbovatelné oblasti vzoru: vedoucí lačná neomezená proměnná jako A+ nebo A*, skupina s pevnou délkou a neomezeným lačným kvantifikátorem jako (A B)+, lačná skupina, jejíž tělo začíná jedním z těchto tvarů, jako (A+ B)+ nebo (A+ B){2}, nebo větve alternace sestavené z nich; neochotná skupina vylučuje celý svůj podstrom. Kde to platí, jako u A+ v §2.5, runtime sloučí kontexty na jeden a zůstává lineární; START UP+ DOWN+ z §2.3 nemá absorbovatelnou oblast vůbec žádnou.

§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í práci 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, koncová hranice musí být UNBOUNDED FOLLOWING nebo kladný offset FOLLOWING (takže je odmítnut i výchozí rámec) a možnosti EXCLUDE jiné než EXCLUDE NO OTHERS 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í:

ZdrojReprezentace ve 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 poté typově kontrolován vůči sloupcům partition a převeden na booleovský výraz. Z toho plynou dvě praktické věci. Za prvé analýza při parsování do cílového seznamu dotazu kvůli DEFINE nic nepřidává; místo toho planner označí každý sloupec odkazovaný predikátem DEFINE jako potřebný, stejně jako to dělá u HAVING, a 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 devět přepisovacích pravidel v jediném průchodu zdola nahoru (uvnitř sekvence se slučování skupin spustí ještě jednou, protože dřívější sloučení mohou svést dohromady dvě identické skupiny):

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}
Slučování 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
Normalizace neochotnosti
A{2}? → A{2} (neochotnost se ruší všude, kde min = max)

Násobení kvantifikátorů sloučí pouze tehdy, když dosažitelné počty tvoří jeden souvislý interval a preferovaná shoda se neposune: přesný vnější kvantifikátor ((A{2,3}){5} → A{10,15}), potomek s min 0, nebo intervaly potomka, které na sebe navazují, s min potomka nejvýše 1 nebo neomezeným max potomka ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), přičemž vnější kvantifikátor s min 0 navíc vyžaduje min potomka nejvýše 1 ((A{2,})* zůstává, protože A* by přijal jeden řádek). Potomek-skupina, jejíž vlastní kvantifikátor není přesný, musí nejprve mít tělo pevné délky, takže ((A | B B){1,2}){2} zůstává netknuté i při přesném vnějším kvantifikátoru. 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 — nebo posunout preferovanou shodu ((A{2,3}){1,2} preferuje tři řádky, kde A{2,6} bere čtyři), takže je optimalizátor ponechává netknuté. Není to jediný podmíněný přepis: slučování skupin a slučování sufixu vyžadují tělo, které spotřebovává pevný počet řádků, slučování prefixu odmítá skupinu s min 0, konečným max a nullable obsahem, neochotné uzly se neslučují ani nenásobí ((A+?)+ zůstává) a přepis, jehož nová mez by přetekla, je odmítnut.

Tvar prvku

Každý prvek plochého pole představuje jednu pozici ve vzoru. Existuje šest 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í; oddělovač větví, který ukončuje každou větev; 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“ (značka alternace a oddělovače větví jím řetězí větve, začátek skupiny jím pojmenovává vlastní konec skupiny — skupina, jejíž kvantifikátor dovoluje nulu, se přeskakuje přes next tohoto konce — 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 → 3
    (otevírá skupinu; jump pojmenovává
     její 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
    (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 pojmenovává jump u BEGIN jeho END na indexu 3, a kdyby byla skupina nepovinná, přeskok by odešel přes next tohoto END na index 4, aniž by na END dorazil. 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 pět logických atributů, 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? B?)+, (A | B*)+; (A?)* se nejprve vynásobí na A* a žádný konec skupiny nezanechá). Říká runtime, aby pod min 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.
Preferuje prázdnou shodu
Nastaveno na koncích skupin, jejichž tělo preferuje prázdnou shodu, jako v (A?? B??){2}. Pod min řadí rychlý výstup před návrat do cyklu, kde lačnost samotné skupiny nic neříká.
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 ploché pole od
  prvku 0 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 přijímá čtyř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)+, (A+ B){2}
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 A dostane oba příznaky, obklopující BEGIN dostane příznak oblasti a B ani END nedostanou žádný.
Případ 4 — alternace
A+ | B+, A+ | C D
Každá větev, dosažená přes řetěz oddělovačů, je posouzena samostatně podle výše uvedených případů; značka alternace dostane příznak oblasti, pokud se kvalifikuje kterákoli větev.

Strukturální případy nepokryté těmito čtyřmi 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. 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
  if targetPos != currentPos:
      načíst řádek na targetPos
        do nav_slot
      nasměrovat vnější slot na nav_slot
  result = eval_inner_expression()
  obnovit current_row_slot
  zkopírovat by-ref výsledek z nav_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 a žádný slot na každou referenci; když je cílem aktuální řádek, načtení i výměna se zcela vynechají. Načtení zkopíruje cílový řádek do navigačního slotu (pokud jej slot již nedrží) a krok obnovení zkopíruje výsledek předávaný odkazem do paměti pro jednotlivé n-tice, aby jej další načtení nemohlo uvolnit.

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 currentPos − 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 (currentPos − n) − m
  NEXT(LAST(n), m):
      return (currentPos − 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 kontextová absorpce vůbec možná (§2.5 vs. §2.6): jediná proměnná závislá na začátku shody ji vypne pro celý vzor.

Sdílené vyhodnocování · bezpečné pro absorpci Každý kontext vidí na každém řádku stejný boolean — stejný osud (§2.5).
  • Bez navigace
  • Pouze PREV / NEXT
  • LAST bez offsetu
  • Složené s vnitřním LAST (bez offsetu)
Vyhodnocování podle kontextu · nebezpečné pro absorpci Kontexty s různými začátky shody počítají různé odpovědi — odlišné osudy (§2.6).
  • LAST s offsetem
  • FIRST (jakákoli forma)
  • Složené s vnitřním FIRST
  • Složené s vnitřním LAST (s offsetem)

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. Executor to určuje ze dvou doplňujících se offsetů a každý offset vyhodnotí jednou na průchod (konstantní také při inicializaci executoru, aby je mohl ukázat i prostý EXPLAIN):

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 (libovolný offset, včetně výchozí 0), PREV(LAST(...)), NEXT(LAST(...))
Rozpočet pohledu vpřed od začátku
Minimální dosah vpřed (zpět, je-li záporný) od začátku shody nejstaršího aktivního kontextu — nejdřívější řádek, který by jakékoli volání DEFINE mohlo potřebovat.
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. Řádky Nav Mark, které EXPLAIN hlásí (§3.7) — Lookback a Lookahead — jsou tyto dva rozpočty, nikoli naměřené vrcholy. Každý se vypíše jen tehdy, když do něj přispívá nějaká navigace, a zobrazuje se i bez ANALYZE; offset, jehož hodnota je známa až za běhu (například parametr generického plánu), se při prostém EXPLAIN vypíše jako runtime a při EXPLAIN ANALYZE jako vyhodnocená hodnota, a retain all (Lookback) nebo infinite (Lookahead) označuje offset, který přeteče.

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

Výsledek shody je zaznamenán jako dvě hodnoty: řádek, na kterém shoda začíná, a její délka. Záporný začátek znamená, že pozice dosud nebyla vyhodnocena; jakmile je začátek nastaven, následné dotazy proti executoru — „je tento řádek uvnitř shody?“ — mohou odpovědět v O(1) prozkoumáním této dvojice. Délka kóduje výsledek: -1 pro nepřiřazený řádek, 0 pro prázdnou shodu a počet řádků pro skutečnou shodu. 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 jak od nepřiřazeného řádku, tak od „na této pozici dosud nebyl 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 v tomto režimu absorpci pro vzor daného okna 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 a poté posouvá NFA vpřed řádek po řádku — pro každý řádek resetuje pole shod jednotlivých proměnných na „nevyhodnoceno“ — dokud tento kontext nemá žádné aktivní stavy nebo partition neskončí. Predikáty DEFINE se vyhodnocují líně: proměnná se vyhodnotí, až ji nějaký stav poprvé spotřebovává, takže proměnná, kterou na tomto řádku netestuje žádný aktivní stav, se nikdy nevyhodnotí. 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 dosáhl konce svého rámce:
          vynutit neúspěch (finalizovat předčasně)
          continue
      if matchStartRow se liší od
         sdílené pozice vyhodnocování:
          resetovat DEFINE proměnné
          závislé na začátku shody
          na nevyhodnoceno (§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)
      if zaznamenal shodu a
         SKIP PAST LAST ROW:
          prořezat pozdější kontexty,
          které začínají uvnitř shody

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]
      assert elem je proměnná
          # advance parkuje jen proměnné

      if varMatched[elem.varId] je
         nevyhodnoceno:
          vyhodnotit jeho DEFINE nyní
      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
         nebo drží zaznamenanou shodu:
          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), dokud kontext nezaznamená shodu, což jej natrvalo nastaví na false — absorpce by uvolnila shodu, kterou žádný absorbující kontext nedokáže reprodukovat. 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
      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í, zastavit,
               jakmile je FIN zaznamenáno),
    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 označit
         kontext, aby pozdější kontexty
         uvnitř rozsahu tohoto kandidáta
         byly prořezány — 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 jakmile Advance dokončí práci s kontextem, který kandidáta zaznamenal, je každý následný kontext, jehož výchozí řádek leží uvnitř rozsahu kandidáta, prořezán na tomtéž řádku, 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 prořezávací krok v okamžiku FIN napříč kontexty. Uvnitř kontextu FIN také odřezává lexikálně horší práci: Advance zahodí zbývající stavy ve frontě (popsáno dříve v této sekci) a v rámci jednoho DFS se každá méně preferovaná cesta — pozdější větve ALT, druhá z cest přeskoku a vstupu u BEGIN, cesta vstupu neochotné proměnné, druhá z cest cyklu a výstupu u END — zastaví, jakmile je shoda zaznamenána, takže jeden advance zaznamená nejvýše jednu shodu.

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
          (rychlý-vpřed jako první, pokud
           tělo preferuje prázdnou shodu;
           druhá cesta se zahodí, pokud
           první dosáhla FIN)

  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
          if cyklus dosáhl FIN:
              zahodit výstup
              # preferovat delší
          else vystoupit jako druhé
      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? B?)+ a (A | B*)+ mají tuto vlastnost: v závislosti na datech může tělo dokončit iteraci, aniž by spotřebovalo jediný řádek. (Jediný nepovinný potomek jako (A?)* je v době kompilace přepsán na A* a žádnou skupinu nezanechá.) 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 do těla (jeho jump je první potomek skupiny), tělo opět produkuje prázdnou shodu, znovu dosáhne END a tak dále. Bez něčeho, co to zastaví, by DFS Advance nikdy neskončilo.

Ochrana 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. Runtime udržuje bitmapu navštívených, vyčištěnou před DFS expanzí každého stavu, ve které se označují pouze END s tímto štítkem — nic jiného cyklit nemůže, protože každý jiný návrat do cyklu spotřeboval řádek. Dosažení označeného END znamená, že tělo právě odvodilo prázdnou iteraci, a stav se nezahazuje: na dolní mezi nebo nad ní tam skupinu opustí (prázdná iterace kvantifikátor zastavuje) a pod ní propadne do běžného zpětného cyklu, takže každý prázdný příchod stále zvyšuje počet, dokud nedosáhne min. Vezměme (A? B?){2,3}, kde žádná z proměnných neodpovídá nikde v proudu řádků:

iter 1: A? B? se shodnou s 0 řádky
        → END, count = 1 (pod min)
        END již označen (při vstupu
        do skupiny), ale pod min:
        → cyklit zpět do A?
iter 2: A? B? se shodnou s 0 řádky
        → END, count = 2 (splňuje min)
        END již označen, na min:
        → opustit skupinu
vystoupit s nulovou délkou shody

Pod dolní mezí štítek prázdného cyklu také říká handleru END, aby vedle běžné cesty zpětného cyklu klonoval další rychlý-vpřed stav:

advance_end (count pod min):

  cesta zpětného cyklu:
    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. Zpětný cyklus zachytává případ, kdy tělo má později ještě skutečné shody — např. u (A? B?){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 skupinu okamžitě opustí, prohlásí „zbytek povinných iterací je prázdný“ a umožňuje shodě uspět s tělem nulové délky. O pořadí rozhoduje tělo, nikoli lačnost samotné skupiny: rychlý-vpřed jde první právě tehdy, když tělo preferuje prázdnou shodu (neochotné tělo jako (A?? B??)), a pokud první cesta dosáhne FIN, druhá se zahodí, takže méně preferovaná cesta nemůže nahradit preferovanou shodu. 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ý

Udržení runtime v mezích 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 sedí na bodu porovnání a je pokryt absorbovatelným stavem staršího kontextu na stejném prvku s větším nebo stejný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) Advance
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 prořezán, jakmile Advance dokončí práci s kontextem, který kandidáta zaznamenal.
Ochrana proti cyklům Advance
Epsilonové expanze, které v rámci téhož DFS dosáhnou END nullable skupiny, který je již označen (označen při vstupu přes BEGIN nebo při dřívějším příchodu) — jinak by cyklily donekonečna; na dolní mezi nebo nad ní tam stav skupinu opustí a pod ní cyklí dál.
Rychle vpřed při prázdném cyklu Advance
Pod dolní mezí nullable skupiny dodatečná cesta, která skupinu opouští se zbývajícími povinnými iteracemi prohlášenými za prázdné, seřazená vůči zpětnému cyklu podle preference těla.
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). Č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ý 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. Zdrojový kód dokumentuje případy, které vrstvy nezachytí: deduplikace drží odděleně stavy, které se liší jen počty nad min, takže (A{2,} B)+ C, kde C nikdy není pravdivé, drží ve špičce Θ(n²) stavů a vytvoří jich Θ(n³) (37 s nad 320 řádky), a běh samých nullable alternací se vyčísluje cestu po cestě, takže (A?|B?){30} trvá přes půl hodiny.

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. V textovém formátu jsou vydávány vedle okenního operátoru, za řádkem Pattern:, případnými řádky Nav Mark (které ukazuje i prostý EXPLAIN) a řádkem Storage::

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (každý jen tehdy, když DEFINE používá
   navigaci, která do něj přispívá)
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ý řádek NFA jen tehdy, když je
   některý z počtů nenulový; nulový počet
   se vypíše bez svého (len ...))

Netextové formáty vydávají každý počet jako samostatnou vlastnost. 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; pruned počítá kontexty, které selhaly po jediném řádku. Histogramy délek shody oddělují čtyři výsledky — úspěšné shody, pokusy o shodu, které selhaly po více než jednom řádku (mismatched), absorbované kontexty a kontexty uvolněné pomocí AFTER MATCH SKIP PAST LAST ROW, protože začaly uvnitř zaznamenané shody (skipped) — 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 neshodných.

Dva čítače Nav Mark hlásí rozpočet uchovávání tuplestore, který §3.3 odvozuje z DEFINE. Lookback je nejhlubší dosah zpět od aktuálního řádku přes PREV, LAST s libovolným offsetem (včetně výchozí 0) a složené formy s vnitřním LAST; Lookahead je minimální dosah vpřed (záporný, když sahá před začátek shody) 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 známý až pro daný průchod, a — pouze u Lookback — „retain all“, když offset přeteče; Lookahead, který přeteče, se vypíše jako „infinite“. Každý řádek se vydává jen tehdy, když do něj přispívá nějaká navigace v DEFINE, a oba se objevují i pod prostým EXPLAIN: konstantní offsety jsou ustaveny při inicializaci executoru, zatímco offset známý až za běhu (například parametr generického plánu) se tam vypíše jako „runtime“ a pod EXPLAIN ANALYZE jako vyhodnocené celé číslo.

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

Kromě čítačů EXPLAIN vypisuje řádek Pattern: sestavený ze zkompilovaného pole prvků, takže ukazuje vzor po přepisech v době kompilace (PATTERN (A A) se vysvětlí jako a{2}) a nese absorpční značky # (bod porovnání) a ~ (absorbovatelná oblast); DEFINE ani možnost AFTER MATCH SKIP se nezobrazují. Reprodukce klauzulí tak, jak byly zapsány, včetně neochotných kvantifikátorů, opakování skupin a možnosti přeskoku, je úkolem pg_get_viewdef(), která 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 22 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
Integrace s klauzulí WINDOW — realistické okenní scénáře nad syntetickými daty akcií (V-tvar, W-tvar, po sobě jdoucí růsty, obraty), navíc sémantika navigace a chyby omezení DEFINE.
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; navíc vrstva planneru — optimalizace vzoru, absorpční příznaky, záložní cesta optimalizace, integrace s plannerem.
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ů. Tyto scénáře jsou jedinými testy, jejichž vstupy a výstupy se čtou jako dotazy, které by uživatel skutečně napsal; zbytek souboru je, stejně jako ostatní sady, redukční — vnořování PREV/NEXT a chyby nekonstantních offsetů, pravidla odkazů v DEFINE a sémantika navigačních offsetů.

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. Druhá část, vrstva planneru, pokrývá optimalizaci vzoru, zobrazení a analýzu absorpčních příznaků, záložní cestu optimalizace a integraci s plannerem (poddotazy, spojení, množinové operace, řazení a seskupování).

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. Vady 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: vložené řádky VALUES nesoucí pole názvů proměnných, které deklaruje, které proměnné DEFINE odpovídají na každém řádku, ve dvojici se vzorem zkoumajícím konkrétní chování runtime. Idiom 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:

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

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, jak každá z těchto optimalizací zachází s okny RPR — většina musí být vypnuta nebo obejita:

Kanonikalizace rámce
Planner běžně přepisuje ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING na ROWS UNBOUNDED PRECEDING pro okenní funkce nezávislé na rámci, jako row_number, rank a ntile. 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 nebo SKIP)
Dvě okna RPR se stejným PATTERN, ale různými klauzulemi DEFINE nebo odlišným AFTER MATCH SKIP produkují různé shody a musí zůstat oddělena, i když je jejich strukturální tvar identický.
Projekce nepoužitého výstupu
Tato optimalizace se uplatnit smí: když okolní dotaz nikdy nečte výstup okna, okenní funkce se stane NULL a její WindowAgg se odstraní, přičemž počet řádků zůstane nezměněn. Testy ověřují, že sloupce, které DEFINE čte, se k WindowAgg stále dostanou, když zůstává, a že okno je zachováno, když se jeho hodnota čte.
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.

Další případy ověřují, že odhad nákladů zohledňuje DEFINE, že poddotaz obsahující okno RPR není zploštěn, že výrazy DEFINE neprosakují do vyššího WindowAgg a že LIMIT zůstává nad WindowAgg; druhá skupina spouští RPR spolu s CTE, spojeními, množinovými operacemi, připravenými příkazy, partitionovanými tabulkami a podobnými konstrukcemi. Většina hlídaných případů má stejný tvar: výchozí stav, který spouští optimalizaci (obvykle dotaz bez RPR, ověřený v EXPLAIN), pak dotaz RPR strukturálně podobného tvaru, kde optimalizace není aplikována — u případu deduplikace DEFINE/SKIP je výchozím stavem dvojice identických oken RPR a případ inverzních přechodů ověřuje obejití pomocí logující agregace místo EXPLAIN. 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é.