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ěží.
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.
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 FOLLOWINGneboROWS BETWEEN CURRENT ROW ANDnFOLLOWINGs n ≥ 1 (19075-5 §6.10.2); jakýkoli jiný rámec je odmítnut a jediné přijímané vyloučení jeEXCLUDE 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,FIRSTaLASTzapsané jako nekvalifikovaná volání uvnitřDEFINEvždy znamenají navigaci; uživatelská funkce stejného jména tam musí být kvalifikována schématem.- Navigační argumenty
- U
PREV,NEXT,FIRSTaLASTmusí 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řesOVERjako 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 vDEFINE,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.pricevDEFINEneboMEASURES— 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“);
permutezůstává použitelné jako název proměnné vzoru. - Agregační funkce v DEFINE
- Agregace jako
SUM,AVG,COUNTnejsou v predikátechDEFINEpovoleny. Standard je povoluje jako běžící agregace nad částečnou shodou; agregace kvalifikovaná proměnnou, jakoAVG(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
DEFINEje 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.
§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.
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ř
DEFINEje posledním přiřazeným řádkem aktuální řádek, takžeLAST(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
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:
| Řádek | Cena | Pravdivé proměnné | Akce |
|---|---|---|---|
| 0 | 100 | START | Nový kontext. START odpovídá a okamžitě vystupuje (max=1); stav postupuje na UP+. |
| 1 | 110 | START, UP | UP odpovídá. Posun se větví: jeden stav cyklí v UP, druhý vystupuje do DOWN+. |
| 2 | 120 | START, UP | UP odpovídá v cyklícím stavu a opět se větví. Stav DOWN z řádku 1 umírá (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP 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. |
| 4 | 108 | START, DOWN | DOWN 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ší. |
| 5 | 130 | START, UP | Cyklí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:
| Řádek | Cena | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
Řá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á 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í.
| Řádek | Pravdivé proměnné | Aktivní stavy |
|---|---|---|
| R | UP, HIGH | Stav 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+1 | DONE | Stav 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)
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ý):
| Řádek | Naivní kontexty | S absorpcí |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 absorbován |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | pě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é:
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:
| Den | Cena | C1 — 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 |
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
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+).
| Den | Cena | C1 — 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ěží) |
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:
| Navigace | Závislost na začátku shody | Absorbovatelné? |
|---|---|---|
| PREV, NEXT | žádná | ano |
| LAST (bez offsetu) | žádná | ano |
| LAST s offsetem | kontrola hranic | ne |
| 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 hranic | ne |
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
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.
| Řádek | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | shoda začíná; řádky 0–4 budou jedinou shodou | shoda 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 |
| 4 | shoda 0 finalizována (řádky 0–4) | finalizováno pět shod: 0–4, 1–4, 2–4, 3–4, 4–4 |
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:
FIRST nebo LAST s offsetem v DEFINE.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í:
| Zdroj | Reprezentace ve stromu |
|---|---|
| A | VAR(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í naA*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á
-
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.
A+,A*,A{2,∞} - Případ 2 — skupina s pevnou délkou, neomezený vnějšek
-
Každý potomek má
(A B)+,(A B{2})+,((A (B C){2}){2})+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
-
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ý.
(A+ B)+,(A+ B){2} - Případ 4 — alternace
-
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.
A+ | B+,A+ | C D
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.
- Bez navigace
- Pouze
PREV/NEXT LASTbez offsetu- Složené s vnitřním
LAST(bez offsetu)
LASTs offsetemFIRST(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.
- 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.
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 ROWuž žá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:
- 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 (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) se zobrazují pod
EXPLAIN ANALYZEv textu, JSON i XML s dokumentovanými popisky a Nav Mark Lookback a Lookahead se objevují právě tehdy, když do nich přispívá navigace v DEFINE. - 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, 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 FOLLOWINGnaROWS UNBOUNDED PRECEDINGpro okenní funkce nezávislé na rámci, jakorow_number,rankantile. Rámec RPR je rozsahem shody, nikoli agregačním oknem, a musí zůstat doslovný. - Pushdown run-condition
- Monotónní filtr
WHEREnad 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 BYa 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 klauzulemiDEFINEnebo odlišnýmAFTER MATCH SKIPprodukují 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é.