Row Pattern Recognition do hĺbky
Sprievodca normou ISO/IEC 19075-5 · SQL R020 v PostgreSQL — čo sa implementovalo, čo ešte zostáva, a ako to v skutočnosti beží.
Preletite normu, prejdite riešenými príkladmi, preskúmajte dizajn a potom riaďte živý NFA simulátor vlastnými vzormi.
Diskusia: vlákno pgsql-hackers · najnovší patch (v55) · commitfest #4460.
Vopred preložené AI — možné chyby.
§1. Norma, podmnožina a otvorené otázky
1.1 Rozsah normy
Row Pattern Recognition bolo do SQL zavedené normou ISO/IEC 9075-2:2016 a je opísané v sprievodnom dokumente ISO/IEC 19075-5:2021 (Časť 5, „Row Pattern Recognition").
Norma definuje dva povrchy pre rovnaký podkladový mechanizmus. Vlastnosť R010 umiestňuje klauzulu MATCH_RECOGNIZE do zoznamu FROM a vytvára odvodenú tabuľku; vlastnosť R020 zabudúva tú istú logiku vzorov do špecifikácie WINDOW a vytvára výstup okenných funkcií. Oba povrchy majú značnú časť syntaxe a sémantiky spoločnú (19075-5 uvádza v §6.3.3 niekoľko rozdielov špecifických pre R020), ale predstavujú funkčne odlišné vstupné body — databáza môže implementovať jeden alebo oba.
Séria patchov, o ktorej tu hovoríme, implementuje podmnožinu výhradne R020; tabuľková forma je zámerne mimo rozsahu.
Povrch R020 je malý, ale výrazový. Dotaz pripája vzor k oknu pridaním klauzúl do špecifikácie okna, ktorej rámec je ROWS BETWEEN CURRENT ROW AND …: PATTERN opisuje regulárny výraz nad pomenovanými premennými vzoru, DEFINE poskytuje logický predikát, ktorý identifikuje každú premennú, a voliteľné AFTER MATCH SKIP (predvolene PAST LAST ROW) riadi, ako sú postupné zhody umiestnené v rámci partície.
Voliteľné MEASURES, SUBSET, INITIAL/SEEK a pomocná funkcia CLASSIFIER() vlastnosť dopĺňajú. (Funkcia normy MATCH_NUMBER() patrí výhradne k povrchu R010 — 19075-5 §6.3.3 (6) ju z R020 výslovne vylučuje.)
Patch pokrýva dostatok tejto slovnej zásoby na to, aby fungovali netriviálne dotazy, ale zastavuje sa pred niekoľkými konštrukciami, ktorých implementácia závisí od infraštruktúry, ktorá ešte nebola vybudovaná.
Zvyšok tejto sekcie rozdeľuje slovnú zásobu normy na to, čo patch už podporuje, a na to, čo zámerne ponecháva na neskôr. Nasledujúce zoznamy odrážajú aktuálny stav série patchov.
1.2 Implementované vlastnosti
Implementovaná slovná zásoba postačuje na vyjadrenie kanonických vzorov tvaru V, tvaru W a obratových vzorov, ktoré v prvom rade motivujú rozpoznávanie vzorov v riadkoch. Pokrýva tiež každý štandardný kvantifikátor — vrátane všetkých siedmich neochotných variantov *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — a štyri navigačné primitíva, ktoré podmienky DEFINE potrebujú na porovnanie susediacich riadkov.
- klauzula PATTERN
- Definuje vzor riadkov v rámci špecifikácie okna; najviac 240 rôznych premenných vzoru.
- Rámec okna
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGaleboROWS BETWEEN CURRENT ROW ANDnFOLLOWINGs n ≥ 1 (19075-5 §6.10.2); akýkoľvek iný rámec je odmietnutý aEXCLUDE NO OTHERSje jediné akceptované vylúčenie.- Regex: + * ? |
- Štandardné kvantifikátory a alternácia.
- Regex: ( ) zoskupovanie
- Sub-vzory v zátvorkách.
- Regex: {n} {n,} {,m} {n,m}
- Ohraničené počty opakovaní.
- Neochotné *? +? ?? {n}? {n,}? {,m}? {n,m}?
- Všetkých sedem neochotných (non-greedy) variantov, ktoré norma definuje (vylúčené z optimalizácie absorpcie).
- klauzula DEFINE
- Logické podmienky identifikujúce každú premennú vzoru.
- Univerzálna premenná riadkového vzoru
- Nekvalifikované odkazy na stĺpce v
DEFINE(napr. holéPrice) sa vyhodnotia na aktuálny riadok, podľa 19075-5 §4.10/§4.16. - PREV, NEXT (s posunom)
- Dosiahnu n riadkov pred/za aktuálnym riadkom (predvolene 1); vnútorný argument sa vyhodnocuje v navigovanom riadku.
- FIRST, LAST (s posunom)
- Dosiahnu riadok relatívny k zhode;
FIRST(expr, n)cieli na riadok n po začiatku zhody,LAST(expr, n)na riadok n pred najnovším riadkom zhody. - Zložená navigácia (štyri formy)
- Vonkajší krok PREV/NEXT navrstvený na vnútorný FIRST/LAST:
PREV(FIRST(expr)),NEXT(FIRST(expr)),PREV(LAST(expr)),NEXT(LAST(expr))— vnútorný aj vonkajší krok prijímajú vlastný posun. - Navigačné názvy
PREV,NEXT,FIRSTaLASTzapísané ako nekvalifikované volania vnútriDEFINEvždy znamenajú navigáciu; používateľská funkcia rovnakého mena tam musí byť kvalifikovaná schémou.- Navigačné argumenty
- Pri
PREV,NEXT,FIRSTaLASTmusí vnútorný argument obsahovať aspoň jeden odkaz na stĺpec a posun musí byť konštanta v čase behu. - INITIAL
- Zhody vzoru musia začínať v aktuálnom riadku (predvolené).
- AFTER MATCH SKIP PAST LAST ROW
- Predvolený režim preskočenia; vhodný pre absorpciu kontextu.
- AFTER MATCH SKIP TO NEXT ROW
- Umožňuje prekrývajúce sa zhody; vypína absorpciu.
1.3 Neimplementované
Vlastnosti, ktoré zostávajú neimplementované, spadajú do troch voľných skupín. Prvou — a zďaleka najväčšou — je rodina konštrukcií sústredených okolo MEASURES: samotná klauzula MEASURES, SUBSET, CLASSIFIER(), odkazy na stĺpce kvalifikované vzorom ako B.price a navigácia kvalifikovaná vzorom ako LAST(B.price) alebo PREV(B.price).
Nejde o nezávislé medzery, ale skôr o rôzne pohľady na jediný chýbajúci kúsok: vykonávateľ by musel uchovávať históriu na zhodu — záznam, pre každý riadok zhody, o tom, na ktorú premennú vzoru bol namapovaný — a žiadna z týchto konštrukcií nemá zmysluplnú definíciu bez nej. CLASSIFIER() číta meno premennej z toho záznamu; B.price číta stĺpec price tých riadkov, ktorých záznam hovorí B; LAST(B.price) prechádza tú istú množinu riadkov a vyberá posledný; SUBSET U = (A, B) definuje virtuálnu premennú, ktorá agreguje cez oba koše; a MEASURES vyhodnocuje výrazy ako AVG(U.Price) presne s touto agregáciou.
Súčasný vykonávateľ vyhodnocuje predikáty DEFINE riadok po riadku, ale výsledné priradenia premenných nikam nezaznamenáva — nie je čo sa neskôr pýtať. Vybudovanie infraštruktúry histórie je preto predpokladom pre celú skupinu; jednotlivé vlastnosti vypadnú ako drobné projekcie, akonáhle záznamy existujú.
Druhá skupina sa týka alternatívnych cieľov preskočenia: AFTER MATCH SKIP TO FIRST var a AFTER MATCH SKIP TO [LAST] var (holé SKIP TO var znamená SKIP TO LAST var). Tieto tiež závisia od histórie zhody, pretože vykonávateľ musí byť schopný ukázať na riadok namapovaný na danú premennú vo vnútri najnovšej zhody.
Zvyšné položky sú heterogénnym koncovým radom: kľúčové slovo SEEK (alternatíva k INITIAL), prázdny vzor (), forma vylúčenia {- … -}, operátor PERMUTE necitlivý na poradie a agregačné funkcie a poddotazy v DEFINE, oboje v súčasnosti odmietané (agregát kvalifikovaný premennou by tiež potreboval históriu zhody).
- MEASURES
- Pomenované výstupné výrazy na zhodu, napr.
MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; v R020 vystavené cezOVERako okenná funkcia. Prijíma kľúčové slová FINAL / RUNNING (19075-5 §5.4), ktoré sa v R020 zlučujú do tej istej hodnoty, keďže miery sa vždy vyhodnocujú na poslednom riadku zhody (19075-5 §6.9 (3)). - SUBSET
- Pomenované zjednotenia premenných vzoru, napr.
SUBSET U = (A, B, C). Použiteľné všade tam, kde sa môže odkazovať na premennú vzoru —MEASURES, odkazy kvalifikované vzorom vDEFINE,CLASSIFIER(U)— všetko potrebuje históriu zhody. - CLASSIFIER()
- Vracia, na ktorú premennú vzoru bol daný riadok namapovaný. Definované pre DEFINE aj MEASURES (19075-5 §5.9); odpoveďou v ľubovoľnom riadku je meno premennej zaznamenané v histórii zhody pre ten riadok.
- Odkaz na stĺpec kvalifikovaný vzorom
- Holé
B.pricevDEFINEaleboMEASURES— hodnota stĺpca z riadka namapovaného ako pomenovaná premenná. - Navigácia kvalifikovaná vzorom
- Obmedziť navigáciu na riadky namapované ako pomenovaná premenná, napr.
LAST(B.price),FIRST(B.price),PREV(B.price),NEXT(B.price). - SEEK
- Zhoda môže začať v ktoromkoľvek riadku od aktuálneho riadka po koniec úplného rámca okna (oproti INITIAL).
- AFTER MATCH SKIP TO FIRST var
- Preskočiť na prvý riadok namapovaný ako pomenovaná premenná.
- AFTER MATCH SKIP TO [LAST] var
- Preskočiť na posledný riadok namapovaný ako pomenovaná premenná.
- Regex: {- -}
- Vylúčenie — odstraňuje namapované riadky z výstupu
ALL ROWS PER MATCH. Táto možnosť sa na okná nevzťahuje (19075-5 §6.3.3 (4)), takže v okne je syntax povolená (§6.13), ale nemá žiadny výstup, na ktorý by pôsobila. - Regex: ()
- Prázdny vzor — zhoduje sa s prázdnou postupnosťou.
- PERMUTE(...)
- Zhodovanie necitlivé na poradie cez vymenované premenné. Kľúčové slovo je rozpoznané a odmietnuté („PERMUTE is not supported");
permutezostáva použiteľné ako názov premennej vzoru. - Agregátne funkcie v DEFINE
- Agregáty ako
SUM,AVG,COUNTnie sú v predikátochDEFINEpovolené. Norma ich povoľuje ako bežiace agregáty nad čiastočnou zhodou; agregát kvalifikovaný premennou, akoAVG(B.Price), závisí od tej istej histórie zhody, akú vyžadujúMEASURES/CLASSIFIER(), zatiaľ čo nekvalifikovaný pokrýva všetky doterajšie riadky zhody. - Poddotazy v DEFINE
- Každý poddotaz v
DEFINEje odmietnutý. Norma povoľuje taký, ktorý nevykonáva rozpoznávanie vzorov riadkov a neodkazuje na žiadnu premennú vzoru riadkov; patch zatiaľ odmieta viac, než musí.
Stojí za to tu uviesť ďalšie štyri body, pretože sa ľahko zamieňajú za opomenutia.
Prvým je, že kotvy vzoru ^ a $ nie sú povolené s RPR v klauzule WINDOW samotnou normou (19075-5 §6.13: „kotvy (^ a $) nie sú povolené pri zhodovaní vzorov riadkov v oknách"; s podkladovou definíciou v 19075-5 §4.14.1); ich neprítomnosť je súladom s normou, nie medzerou.
Druhým je, že MATCH_NUMBER() je rovnako z R020 vylúčená normou (19075-5 §6.3.3 (6) a 19075-5 §6.9 (1)) — patrí výhradne k povrchu R010, a jej absencia je tu opäť súladom, nie chýbajúcou vlastnosťou.
Tretím je súbor štrukturálnych zákazov, ktoré norma R020 ukladá (19075-5 §6.17): rozpoznávanie vzorov riadkov nemôže byť vnorené do iného rozpoznávania vzorov riadkov; MEASURES a DEFINE nesmú obsahovať vonkajšie odkazy; poddotazy vnútri MEASURES alebo DEFINE nesmú odkazovať na premenné vzoru riadkov (patch ide ďalej a odmieta všetky poddotazy v DEFINE, ako je uvedené vyššie); a RPR sa nesmie použiť vnútri rekurzívneho dotazu. Patch vynucuje pravidlo o vonkajších odkazoch („cannot use outer query column in DEFINE clause") a pravidlo o rekurzii, to druhé pre každý prvok klauzuly WITH RECURSIVE. Odmieta tiež volatilné funkcie a odkazy na celý riadok v DEFINE.
Štvrtým je, že samotný MATCH_RECOGNIZE — vlastnosť R010, tabuľkový povrch tej istej mechaniky — je mimo rozsahu tohto patchu. Či PostgreSQL nakoniec pridá R010, bude otázkou pre budúcu sériu, nie meradlom tejto.
§2. Príklady — ako to v skutočnosti beží
Príklady v tejto sekcii sa budujú postupne. Začíname konceptuálnym dôvodom, prečo je zhodovanie vzorov riadkov skutočne odlišné od zhodovania textových vzorov, potom predstavíme štyri navigačné funkcie, vďaka ktorým sú podmienky DEFINE zaujímavé, a nakoniec prejdeme piatimi riešenými príkladmi: jednou zhodou (pohyb NFA), alternáciou, absorpciou kontextu v jednoduchom prípade a dvoma prípadmi, keď je absorpcia vypnutá.
Vnútorný mechanizmus, ktorý robí navigáciu lacnou — výmena n-tice s 1 slotom — patrí k dizajnu vykonávateľa a je pokrytý v ďalšej sekcii, nie tu.
2.1 Prečo sa vzory riadkov líšia od textových vzorov
Textový regulárny výraz sa zhoduje s prúdom znakov a v každej pozícii je presne jeden symbol na zváženie. Otázka pri behu — „rovná sa aktuálny symbol 'A'?" — má jednu odpoveď áno/nie. Automaty s backtrackingom toto využívajú: na každý znak prežije najviac jedna vetva a cena nejednoznačnosti sa platí opätovným čítaním vstupu.
Vzor riadkov sa líši zásadným spôsobom. Riadok nie je jediný symbol; je to n-tica stĺpcov vyhodnotená oproti množine logických predikátov, podmienkam DEFINE. Dva predikáty môžu byť v tom istom riadku pravdivé súčasne a norma nehovorí, že musia byť vzájomne vylučujúce. Uvažujme:
DEFINE A AS price > 100, B AS volume > 1000, C AS price > 200
Riadok s price = 150, volume = 2000 spĺňa A aj B, ale nie C. Zhodovač vzorov to nemôže zlúčiť do jedného stavu — dve premenné vzoru sú živé a akýkoľvek prvok vzoru, ktorý ktorúkoľvek z nich pomenuje, môže postúpiť. NFA preto musí niesť viacero súčasných stavov na riadok partície, nie jeden.
Toto jediné pozorovanie poháňa zvyšok architektúry. Stav vykonávania je zoznam kontextov, každý kontext je zoznam stavov a v každom riadku sa beh každého stavu pýta: „vzhľadom na premenné, ktoré sú tu pravdivé, kam môžem ísť?" Vzniknuté rozvetvenia sú dôvodom, prečo beh potrebuje niekoľko vrstiev orezávania — deduplikácia stavov v rámci kontextu, absorpcia naprieč kontextami a ostatné pravidlá zmapované v §3.6 — bez ktorých počet živých stavov a kontextov rastie s partíciou a zhodovanie vzorov sa stáva super-lineárnym.
2.2 Navigačné funkcie
Podmienky DEFINE, ktoré odkazujú iba na aktuálny riadok, sú obmedzené; takmer každý zaujímavý vzor potrebuje porovnať aktuálny riadok so svojimi susedmi alebo s riadkami už skôr v zhode prijatými. Norma na to poskytuje štyri navigačné funkcie a patch implementuje všetky.
- PREV(expr [, n])
- Riadok n riadkov pred aktuálnym riadkom (predvolene n = 1). Použité pre porovnania „dnes oproti včera".
- NEXT(expr [, n])
- Riadok n riadkov za aktuálnym riadkom (predvolene n = 1). Predbežný pohľad dopredu; v okennej forme nezvyčajný, pretože okno je monotónne.
- FIRST(expr [, n])
- Riadok n riadkov za prvým riadkom aktuálnej zhody (predvolene n = 0, samotný prvý riadok). „Porovnaj s riadkom, ktorý začal túto zhodu."
- LAST(expr [, n])
- Riadok n riadkov pred posledným zhodnutým riadkom (predvolene n = 0). Vnútri
DEFINEje posledným zhodnutým riadkom aktuálny riadok, takžeLAST(price)číta aktuálny riadok.
Tieto štyri primitíva sa skladajú: PREV a NEXT môžu obaliť volanie FIRST alebo LAST, čo dáva štyri zložené formy, ktorých sémantika znie „choď na riadok relatívny k zhode, potom o pevnú vzdialenosť od neho odstúp." Toto umožňuje výrazu DEFINE prečítať napríklad riadok bezprostredne pred začiatkom zhody.
- PREV(FIRST(expr [, n]) [, m])
- Krok m riadkov späť od riadka, ktorý číta
FIRST(expr, n)(predvolene n = 0, m = 1). „Aká bola hodnota tesne pred začiatkom tejto zhody?" - NEXT(FIRST(expr [, n]) [, m])
- Krok m riadkov vpred od riadka, ktorý číta
FIRST(expr, n). Siaha hlbšie do zhody bez závislosti od aktuálneho riadka. - PREV(LAST(expr [, n]) [, m])
- Krok m riadkov späť od riadka, ktorý číta
LAST(expr, n). „Porovnaj s riadkom krátko pred najnovším zhodnutým riadkom." - NEXT(LAST(expr [, n]) [, m])
- Krok m riadkov vpred od riadka, ktorý číta
LAST(expr, n).
Stojí za to tu uviesť dva praktické body. Po prvé, navigácia môže byť zložená: PREV(FIRST(price)) číta riadok bezprostredne pred začiatkom zhody a patch to podporuje. Po druhé, navigácia má dôsledky pre optimalizácie vykonávateľa. Samotné PREV a NEXT sú relatívne k aktuálnemu riadku a sú vždy bezpečné; FIRST a varianty LAST s posunom, samostatne alebo vnútri zloženého PREV/NEXT, sú relatívne k hraniciam zhody, čo interaguje s absorpciou kontextu: plánovač potom vypne absorpciu pre celý vzor. Mechanizmus tejto interakcie je témou §2.6.
2.3 Riešený príklad 1 — Pohyb NFA
SKIP PAST LAST ROW ich zahodí, len čo je jeho zhoda zaznamenaná.SELECT company, tdate, price, first_value(price) OVER w AS start_price, last_value(price) OVER w AS end_price FROM stock WINDOW w AS ( PARTITION BY company ORDER BY tdate ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW PATTERN (START UP+ DOWN+) DEFINE UP AS price > PREV(price), DOWN AS price < PREV(price) );
Vzor sa sploští na štyri prvky:
[0] START quant 1..1 next → 1 [1] UP quant 1..∞ next → 2 [2] DOWN quant 1..∞ next → 3 [3] #FIN
Pre cenovú postupnosť 100, 110, 120, 115, 108, 130:
| Riadok | Cena | Pravdivé premenné | Akcia |
|---|---|---|---|
| 0 | 100 | START | Nový kontext. START sa zhoduje a okamžite končí (max=1); stav postupuje na UP+. |
| 1 | 110 | START, UP | UP sa zhoduje. Postup sa rozvetvuje: jeden stav cyklí na UP, ďalší prechádza na DOWN+. |
| 2 | 120 | START, UP | UP sa zhoduje v cykliacom stave a opäť sa rozvetvuje. Stav DOWN z riadka 1 hynie (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP zlyháva v cykliacom stave a hynie. Stav DOWN z riadka 2 sa zhoduje. Postup sa rozvetvuje: cyklus na DOWN a prechod na #FIN — zaznamená sa kandidát na zhodu cez riadky 0–3. |
| 4 | 108 | START, DOWN | DOWN sa zhoduje v cykliacom stave a znova sa rozvetvuje; nový FIN kandidát cez riadky 0–4 nahrádza kratší. |
| 5 | 130 | START, UP | Cykliaci stav DOWN zlyháva (130 ≮ 108). Keďže v tomto kontexte nezostal žiadny živý stav, zaznamenaný kandidát (riadky 0–4) sa finalizuje ako zhoda. Ďalší pokus začína v riadku 5; START sa zhoduje, ale partícia skončí skôr, ako príde akékoľvek UP. |
Kľúčový bod: v riadku 3 riadok spĺňa START (vždy pravdivé) aj DOWN, ale START má význam iba pre kontext začínajúci v riadku 3; v tomto kontexte cykliaci stav UP hynie a postúpi iba stav čakajúci na DOWN+. Multi-stavová povaha z §2.1 je viditeľná ako rozvetvenie pri každej zhode UP (stav by mohol zostať na UP+ alebo postúpiť k DOWN+). Greedy preferencia je „cykluj znova pred výstupom", takže pri dostatku dát by cykliace vetvy zhodu predĺžili; tu cykliaci DOWN hynie v riadku 5 (130 ≮ 108) a posledný FIN kandidát (riadky 0–4) — vytvorený, keď DOWN ukončil v riadku 4, a nahrádzajúci kandidáta z riadka 3 — sa finalizuje ako zhoda.
Výsledok dotazu z tejto stopy vyplýva priamo. Podľa sémantiky RPR sa okenné funkcie first_value(price) a last_value(price) vyhodnocujú iba v riadku, ktorý začal zhodu — každý iný riadok v zhode pre tieto okenné funkcie produkuje NULL, keďže jeho zredukovaný rámec je prázdny. Výstup pre naše dáta teda vyzerá ako tabuľka, ktorú poster ukazuje vo svojom paneli vpravo hore:
| Riadok | Cena | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
Riadok 0 je začiatkom zhody, takže jeho rámec pokrýva riadky 0–4 a okenné funkcie hlásia otváraciu cenu V-tvaru ($100) a spodnú cenu ($108). Riadky 1–4 sú vnútri zhody, ale nie jej začiatkom, takže dostávajú NULL. Riadok 5 (cena $130) je mimo akejkoľvek zhody a tiež dostáva NULL.
2.4 Riešený príklad 2 — Alternácia a lexikálne poradie
Forma (A | B) dáva zhodovaču výber: v každom riadku sú dve alternatívy testované nezávisle a môže sa zhodovať ľubovoľný počet z nich. Tu sa multi-stavová povaha z §2.1 stáva viditeľnou vnútri jedného kontextu — nie naprieč kontextami (to je absorpcia), ale pozdĺž paralelných vetiev, ktoré vykonávateľ skúma v poradí vzoru, skoršiu vetvu najprv.
PATTERN ((UP | HIGH) DONE) DEFINE UP AS price > PREV(price), HIGH AS price > 100, DONE AS volume > 1000
Predstavte si riadok, kde cena súčasne stúpla a prekročila $100 — sú pravdivé UP aj HIGH. Každá alternatíva splodí svoj vlastný stav: jeden kráča po vetve UP, druhý po vetve HIGH. Oba potom postúpia k DONE, kde sa stretnú.
| Riadok | Pravdivé premenné | Živé stavy |
|---|---|---|
| R | UP, HIGH | Stav A (vetva UP) a Stav B (vetva HIGH) oba postúpia k DONE s rovnakými počtami; B je duplikátom A a je zahodený |
| R+1 | DONE | Stav A sa zhoduje s DONE a dosiahne #FIN |
V termínoch normy obe vetvy produkujú zhodu rovnakej dĺžky cez tie isté riadky, čím vznikajú dve kandidátske cesty — jedna označená UP, DONE a jedna označená HIGH, DONE. Norma to rieši lexikálnym poradím: spomedzi alternatív zapísaných v (UP | HIGH) vyhráva tá zapísaná ako prvá, bez ohľadu na dĺžku zhody. Keďže sa UP objavuje pred HIGH, prežívajúcou cestou je UP, DONE. Vykonávateľ to vynucuje v riadku R, nie pri FIN: stav vetvy UP pridá ako prvý, takže nfa_append_state_unique() ho ponechá a identický stav vetvy HIGH zahodí.
Lexikálne poradie je to, čo robí CLASSIFIER() dobre definovaným, keď bude napokon implementovaný — umožňuje behu povedať používateľovi „tento riadok sa zhoduje s UP, nie s HIGH", aj keď boli oba predikáty pravdivé. Lexikálne poradie je primárnym pravidlom pre alternáciu: lex-skoršia vetva vyhráva nad lex-neskoršou, aj keby lex-neskoršia vetva produkovala dlhšiu zhodu, a lex-neskoršia (možno kratšia) vetva môže predsa vyhrať, ak všetky lex-skoršie vetvy hynú pred dosiahnutím FIN. Greedy dĺžka sa rozhoduje v rámci jediného kvantifikátora — pri dvoch dokončeniach tej istej alternačnej vetvy greedy kvantifikátor preferuje viac iterácií.
2.5 Riešený príklad 3 — Absorpcia kontextu (rovnaký osud)
Najjednoduchší vzor, ktorý vykazuje absorpciu, je PATTERN (A+) s DEFINE A AS TRUE. Každý riadok sa zhoduje s A a norma vyžaduje, aby zhodovač zvažoval každý riadok ako možný začiatok zhody. Naivne to znamená N kontextov pre N-riadkovú partíciu. Vezmime päťriadkovú partíciu (akékoľvek dáta — predikát je konštantne pravdivý):
| Riadok | Naivné kontexty | S absorpciou |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 absorbovaný |
| 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äť kontextov | C1[A:5] |
Živé kontexty klesajú z O(n) na O(1), takže celkový súčet za partíciu klesá z O(n²) na O(n). Pravidlo absorpcie, ktoré ospravedlňuje vyhodenie, je priamočiare, keď je kvantifikátor neohraničený:
Ľavý dolný panel posteru („① Absorpcia kontextu") je presne toto pravidlo vizualizované na piatich riadkoch.
V pravidle sa skrýva jemný, ale dôležitý bod: vyhodenie je bezpečné, pretože predikát A AS TRUE sa v každom riadku vyhodnocuje na rovnakú hodnotu bez ohľadu na to, ktorý kontext sa pýta. To isté platí pre akýkoľvek predikát, ktorý odkazuje iba na aktuálny riadok alebo pevný posun od neho — vrátane PREV. Nasledujúci príklad prepína na konkrétny týždeň cien s predikátom založeným na PREV a §2.6 znovu použije presne ten istý týždeň, aby symetria medzi bezpečnou a nebezpečnou absorpciou bola zrejmá:
PATTERN (RISE+) DEFINE RISE AS price > PREV(price)
Vezmime obchodný týždeň $100, $108, $112, $116, $110 od pondelka do piatka — štyri vzostupy, po ktorých nasleduje náhly pokles. Predpokladajme, že C1 začína v utorok (prvý deň, keď sa RISE zhoduje: $108 > $100), a vykonávateľ špekulatívne sleduje aj C2 začínajúci v stredu. Podmienka RISE každého riadka porovnáva cenu riadka s jej bezprostredným predchodcom — fakt na úrovni partície, nie na úrovni kontextu — takže oba kontexty sú nútené vypočítať tú istú logickú hodnotu v každom zdieľanom riadku:
| Deň | Cena | C1 — začiatok ut price > PREV(price) | C2 — začiatok st price > PREV(price) |
|---|---|---|---|
| Po | $100 | — | — |
| Ut | $108 | $108 > $100 ✓ (práve začal) | — |
| St | $112 | $112 > $108 ✓ | $112 > $108 ✓ (práve začal) |
| Št | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| Pi | $110 | $110 > $116 ✗ — finalizovať | $110 > $116 ✗ — finalizovať |
Príbeh sa zlomí v okamihu, keď predikát začne závisieť od vlastných hraníc každého kontextu — a o tom je §2.6.
2.6 Riešený príklad 4 — Keď sa absorpcia stáva nebezpečnou
DEFINE odkazuje na FIRST — pravidlo absorpcie už neplatí a plánovač pre tento vzor vypína absorpciu.
Predpokladajme, že analytik chce nájsť po sebe nasledujúce obchodné dni, počas ktorých akcia zostala v rozpätí desiatich dolárov od dňa, ktorým beh začal — akési konsolidačné okno. Vzor a DEFINE vyzerajú takto:
PATTERN (STABLE+) DEFINE STABLE AS price < FIRST(price) + 10
Podmienka teraz porovnáva cenu aktuálneho riadka s cenou na začiatku aktuálneho behu. Dva behy, ktoré začali v iné dni, majú odlišné hodnoty FIRST(price), takže dva stavy na rovnakom prvku vzoru a s rovnakým počtom už nie sú zameniteľné: ich budúcnosti závisia od hranice, ktorú sa absorpcia chystala vyhodiť.
Vezmime presne ten istý obchodný týždeň ako v §2.5 — $100, $108, $112, $116, $110 od pondelka do piatka. Beh opäť udržiava súčasne dva kandidátske behy pri živote: C1 začal v pondelok, C2 začal v utorok (každý riadok je potenciálnym začiatkom behu pri STABLE+).
| Deň | Cena | C1 — začiatok po FIRST = $100 price < $100 + 10 | C2 — začiatok ut FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| Po | $100 | $100 < $110 ✓ | — |
| Ut | $108 | $108 < $110 ✓ | $108 < $118 ✓ (práve začal) |
| St | $112 | $112 < $110 ✗ — finalizovať Po–Ut | $112 < $118 ✓ |
| Št | $116 | — | $116 < $118 ✓ |
| Pi | $110 | — | $110 < $118 ✓ (stále beží) |
Pri absorpcii by bol C2 v utorok zlúčený do C1 — zlúčený kontext si ponecháva iba strop C1 ($110), takže odlišný pohľad C2 (strop $118, štvordňový beh do piatka) budúcnosť C1 nepokrýva. V tomto konkrétnom týždni sa výstup náhodou nezmení: C1 zaznamená Po–Ut, C2 začal vnútri tejto zhody a SKIP PAST LAST ROW ho zahodí, a ďalší pokus začína v stredu s vlastným stropom ($122) a zhoduje sa St–Pi. Vo všeobecnosti však výsledok DEFINE skoršieho kontextu už nezahŕňa výsledok neskoršieho, takže porovnanie počtov, na ktorom absorpcia stojí, je neplatné. Vždy keď predikát DEFINE nesie závislosť od začiatku zhody, plánovač preto preventívne vypína absorpciu.
(Keď zhoda vedúceho kontextu uspeje, kontexty, ktoré začali vo vnútri jeho prijatého rozsahu — pri predvolenom AFTER MATCH SKIP PAST LAST ROW — sú jednoducho zahodené; sú udržiavané pri živote iba preto, aby beh mal kam ustúpiť, ak vedúca zhoda zlyhá.)
Tabuľka nižšie rozširuje pravý dolný panel posteru („② Navigácia") o zložené formy a zhŕňa, ktoré navigačné formy vytvárajú závislosť od začiatku zhody:
| Navigácia | Záv. od začiatku zhody | Absorbovateľná? |
|---|---|---|
| PREV, NEXT | žiadna | áno |
| LAST (bez posunu) | žiadna | áno |
| LAST s posunom | kontrola hraníc | nie |
| FIRST (akýkoľvek) | priama | nie |
| Zložená (vnútorný FIRST) | priama | nie |
| Zložená (vnútorný LAST, bez posunu) | žiadna | áno |
| Zložená (vnútorný LAST s posunom) | kontrola hraníc | nie |
Dva príklady v §2.5 a §2.6 sa redukujú na jediné pravidlo. Rovnaký osud je to, čo robí absorpciu bezpečnou: ak každý kontext na rovnakom prvku vzoru vypočíta rovnakú odpoveď na každý budúci predikát, treba ponechať iba najstarší. Rozdielne osudy robia absorpciu nebezpečnou: hneď ako predikáty rozvetvia podľa kontextovo-súkromného stavu — čo presne robia FIRST a posunové LAST — každý živý kontext predstavuje budúcnosť, ktorú žiadny iný kontext zaručene nepokrýva, takže bezpečnosť vyhodenia ktoréhokoľvek z nich už nemožno preukázať.
Plánovač toto rozlíšenie deteguje v čase kompilácie a zapína alebo vypína absorpciu pre celý vzor; keď je vypnutá, beh platí viac-kontextovú cenu. Benchmark posteru v paneli ③ nepoužíva FIRST, takže absorpcia zostáva zapnutá, a preto PostgreSQL zostáva lineárny v prípadoch úspechu aj zlyhania.
Čísla benchmarku na posteri sú ten istý algoritmus odohrávajúci sa v škále. Na úspešnom vzore (A+ B+ C+ D) oba PostgreSQL aj Trino škálujú približne O(n), keď je zhoda potvrdená, a PostgreSQL vedie približne 16× až 33× (údaje Trino už vylučujú štart JVM).
Na neúspešnom vzore (A+ B+ C+ E) Trino, ktorému zrejme chýba absorpcia, prenasleduje každý potenciálny začiatok zhody a degraduje ešte rýchlejšie ako O(n²) (približne 56× viac času pri 5× viac riadkoch); pri 100 000 riadkoch trvá viac ako päť hodín, zatiaľ čo PostgreSQL stále končí za 92 ms, čo je zrýchlenie približne 217 000×.
Tá medzera nie je inžinierskym leskom — je to presne rozlíšenie rovnakého-osudu / rozdielneho-osudu z §2.5 a §2.6, aplikované na každý riadok každého potenciálneho začiatku zhody v partícii.
2.7 Riešený príklad 5 — Keď SKIP vypne absorpciu
Predošlý príklad zlomil absorpciu zo strany dát: FIRST v DEFINE spôsobil, že každý kontext vyhodnocoval predikáty inak. Absorpcia sa môže zlomiť aj zo strany výstupu, a klauzula AFTER MATCH SKIP je to, čo to ovláda.
Uvažujme vzor PATTERN (A+) s DEFINE A AS TRUE nad piatimi riadkami, ktoré sa všetky zhodujú s A. Pri predvolenom AFTER MATCH SKIP PAST LAST ROW zhodovač nájde najdlhšiu zhodu začínajúcu v najskoršom riadku a potom za ňu skočí; akýkoľvek kontext, ktorý začal vnútri tejto zhody, je implicitne vyhodený ako redundantný — presne situácia, na ktorú je absorpcia navrhnutá. Výstupom je jediná zhoda, riadky 0–4, a beh potrebuje iba jeden živý kontext.
Prepnite režim preskočenia na AFTER MATCH SKIP TO NEXT ROW a kontrakt sa zmení:
PATTERN (A+) DEFINE A AS TRUE AFTER MATCH SKIP TO NEXT ROW
Teraz musí byť každá potenciálna začiatočná pozícia reportovaná osobitne, aj keď sa zhody prekrývajú. Pre tých istých päť riadkov beh musí vydať päť zhôd: riadky 0–4, 1–4, 2–4, 3–4 a 4–4. Žiadnu z nich nemožno nahradiť „dlhšou začínajúcou skôr", pretože norma hovorí, že používateľ chce všetky.
| Riadok | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | zhoda začína; riadky 0–4 budú jedinou zhodou | zhoda začína v riadku 0 |
| 1 | (vnútri zhody 0) | zhoda začína v riadku 1 — musí zostať pri živote |
| 2 | (vnútri zhody 0) | zhoda začína v riadku 2 — musí zostať pri živote |
| 3 | (vnútri zhody 0) | zhoda začína v riadku 3 — musí zostať pri živote |
| 4 | zhoda 0 sa finalizuje (riadky 0–4) | finalizuje sa päť zhôd: 0–4, 1–4, 2–4, 3–4, 4–4 |
AFTER MATCH SKIP TO NEXT ROW je každý neskôr-začínajúci kontext vlastným výstupným riadkom. Dva kontexty na rovnakom prvku vzoru už nie sú redundantné — sú oba požadované výstupy a vyhodenie jedného by ticho zahodilo zhodu, o ktorú používateľ požiadal.
Všimnite si, že predikát sa nezmenil. A AS TRUE sa v každom riadku vyhodnocuje rovnako bez ohľadu na to, ktorý kontext sa pýta, takže podmienka rovnakého-osudu z §2.5 je stále splnená. Mení sa výstupná požiadavka: aj kontexty s identickými budúcnosťami musia koexistovať, pretože zodpovedajú odlišným riadkom výsledku. Plánovač preto vypína absorpciu kontextu vždy, keď je v platnosti AFTER MATCH SKIP TO NEXT ROW, bez ohľadu na klauzulu DEFINE.
Položenie §2.6 a §2.7 vedľa seba ukazuje dva spôsoby, ktorými sémantika dotazu vylučuje absorpciu:
FIRST alebo posunovým LAST v DEFINE.AFTER MATCH SKIP TO NEXT ROW.
Ktorákoľvek podmienka stačí na vypnutie absorpcie pre celý vzor, a rovnako aj rámec, ktorý nekončí na UNBOUNDED FOLLOWING. Keď neplatí žiadna z nich — predvolené AFTER MATCH SKIP PAST LAST ROW, neohraničený koniec rámca a podmienky DEFINE, ktoré používajú iba PREV, NEXT alebo holé LAST — absorpcia je zapnutá, ale iba pre stavy v absorbovateľnom regióne vzoru: vedúca greedy neohraničená premenná ako A+ alebo A*, skupina s pevnou dĺžkou s neohraničeným greedy kvantifikátorom ako (A B)+, greedy skupina, ktorej telo začína jedným z nich, ako (A+ B)+ alebo (A+ B){2}, alebo vetvy alternácie zostavené z nich; neochotná skupina diskvalifikuje celý svoj podstrom. Kde to platí, ako pri A+ v §2.5, beh sa zlučuje do jedného kontextu a zostáva lineárny; START UP+ DOWN+ z §2.3 nedostane žiadny absorbovateľný región.
§3. Dizajn — od parsera po vykonávateľa
Row Pattern Recognition je implementované ako tri etapy, ktoré si odovzdávajú prácu cez dobre definované medziformy. Parser prevádza SQL text na strom vzoru a zoznam predikátov DEFINE; plánovač kompiluje strom do plochého poľa prvkov vzoru a rozhoduje, ktoré z nich sa môžu zúčastniť absorpcie kontextu; vykonávateľ púšťa pole oproti partícii riadok po riadku v trojfázovej slučke. Každá etapa má vlastný tvar dát a väčšina dizajnového dôvtipu je na hraniciach: plochý NFA, ktorý sa zmestí do cache, navigačný model, ktorý znovu používa jediný slot n-tice namiesto materializácie jedného na odkaz, a pravidlo absorpcie, ktoré mení prácu O(n²) na O(n).
SQL text
│
│ etapa parsera
▼ validovať rámec
postaviť strom vzoru
typovo overiť DEFINE
strom vzoru + zoznam DEFINE
│
│ etapa plánovača
▼ optimalizovať strom
kompilovať do plochého poľa NFA
rozhodnúť absorbovateľnosť
plochý NFA + príznaky absorpcie
│
│ etapa vykonávateľa
▼ motor na riadok:
Zhoda → Absorpcia → Postup
výsledok zhody:
začiatočný riadok, dĺžka, úspech/zlyhanie
Nasledujúce sekcie kráčajú nadol týmto potrubím. §3.1 pokrýva parser a tvar stromu vzoru; §3.2 pokrýva kompiláciu, ktorá mení strom na plochý NFA; §3.3 pokrýva navigačný model, ktorý predikáty DEFINE používajú na pohľad na susediace riadky; §3.4 pokrýva spracovanie hraníc zhody — pravidlá SKIP, INITIAL a ohraničeného rámca, ktoré stanovujú, kde zhoda začína a končí; §3.5 je trojfázový motor na riadok; §3.6 zbiera všetky orezávacie mechanizmy, ktoré udržiavajú priestor stavov ohraničený; a §3.7 mapuje, čo implementácia vystavuje vo výstupe EXPLAIN.
3.1 Parser — budovanie stromu vzoru
Parser rozpoznáva rozpoznávanie vzorov podľa prítomnosti klauzuly PATTERN vnútri špecifikácie okna. Jeho prvou úlohou je validácia rámca, keďže RPR ukladá obmedzenia, ktoré bežné okenné dotazy nemajú: režim rámca musí byť ROWS (nie RANGE ani GROUPS), počiatočná hranica musí byť CURRENT ROW, koncová hranica musí byť UNBOUNDED FOLLOWING alebo kladný offset FOLLOWING (takže aj predvolený rámec je odmietnutý) a možnosti EXCLUDE iné ako EXCLUDE NO OTHERS sú zakázané. Toto sú kontroly súladu, nie optimalizácie — predstava rámca v RPR je rozsah zhody a norma neuvažuje o jeho vyplnení čímkoľvek iným ako zhodnutými riadkami.
Keď rámec prejde validáciou, parser premení klauzulu PATTERN na strom postavený zo štyroch druhov uzlov — odkaz na premennú, postupnosť (zreťazenie), alternácia a skupina (sub-vzor v zátvorkách). Každý uzol nesie kvantifikátor ako tri čísla — dolná hranica, horná hranica (možno nekonečná) a príznak pre neochotné zhodovanie:
| Zdroj | Kódovanie 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 potom typovo overený oproti stĺpcom partície a privedený k logickému výrazu. Z toho vyplývajú dve praktické veci. Po prvé, analýza parsovania nepridáva kvôli DEFINE nič do cieľového zoznamu dotazu; namiesto toho plánovač označí každý stĺpec, na ktorý sa odkazuje predikát DEFINE, ako potrebný, rovnako ako pri HAVING, a prepúšťa tieto stĺpce do etapy vykonávateľa, aj keď ich okolitý dotaz nevyberá — bez toho by beh nemal voči čomu vyhodnocovať. Po druhé, premenné, ktoré sa objavujú v PATTERN, ale nikdy v DEFINE, sú implicitne pravdivé: zhodujú sa s každým riadkom.
3.2 Kompilácia — z AST na plochý NFA
Plánovač premieňa strom parsera na dátovú štruktúru, ktorú vykonávateľ pustí: ploché pole prvkov vzoru adresované indexom. Kompilácia prebieha ako šesťkrokové potrubie:
compile(astTree):
1. optimalizovať AST
2. zmerať veľkosť a hĺbku
3. alokovať pole prvkov
4. naplniť z AST
(priradiť ukazovatele next/jump)
5. finalizovať — nastaviť FIN sentinel
6. označiť prvky vhodné na absorpciu
Plochý tvar je zvolený z jednoduchého dôvodu: vykonávateľ potrebuje prejsť vzor mnohokrát na partíciu a súvislé indexovo-adresovateľné pole je najlacnejšia dátová štruktúra na prechádzanie. Kroky 1 a 6 sú zaujímavé — krok 1, pretože určuje, aké veľké pole bude, a krok 6, pretože rozhoduje, či sa optimalizácia absorpcie z §2.5 vôbec zapne.
Optimalizácia AST
Optimalizácia sa vypláca dvakrát: raz v statickom počte prvkov plochého poľa a opäť v každom riadku spracovanom za behu. Každá transformácia redukuje priestor stavov, ktorý beh musí enumerovať. Optimalizátor aplikuje deväť prepisovacích pravidiel v jedinom prechode zdola nahor (v rámci sekvencie sa zlučovanie skupín spustí ešte raz, pretože skoršie zlúčenia môžu priviesť dve identické skupiny k sebe):
- Splošťovanie SEQ
SEQ(A, SEQ(B, C))→SEQ(A, B, C)- Zlučovanie po sebe idúcich premenných
-
A A→A{2}
A{2,3} A{1,2}→A{3,5} - Zlučovanie po sebe idúcich skupín
(A B)+ (A B)+→(A B){2,∞}- Zlučovanie po sebe idúcich ALT
(A | B) (A | B) (A | B)→(A | B){3}- Zlučovanie prefixu/sufixu
A B (A B)+→(A B){2,∞}- Splošťovanie a deduplikácia ALT
-
(A | (B | C))→(A | B | C)
(A | B | A)→(A | B) - Násobenie kvantifikátorov
-
(A+)+→A+
(A{2,3}){5}→A{10,15} - Rozbalenie jediného potomka
-
SEQ(A)→A
(A){1,1}→A - Normalizácia neochoty
A{2}?→A{2}(neochota sa ruší všade, kde min = max)
Násobenie kvantifikátorov zlučuje iba vtedy, keď dosiahnuteľné počty tvoria jeden súvislý interval a preferovaná zhoda sa neposunie: presný vonkajší ((A{2,3}){5} → A{10,15}), potomok s min 0, alebo intervaly potomka, ktoré na seba nadväzujú, pri min potomka najviac 1 alebo neohraničenom max potomka ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), pričom vonkajší s min 0 navyše potrebuje min potomka najviac 1 ((A{2,})* zostáva, pretože A* by akceptovalo jeden riadok). Skupinový potomok, ktorého vlastný kvantifikátor nie je presný, musí najprv mať telo s pevnou dĺžkou, takže ((A | B B){1,2}){2} zostáva nedotknuté aj pod presným vonkajším. Iné kombinácie môžu zaviesť medzery, ktoré by plochá forma minula — napr. (A{2}){2,3} akceptuje iba {4, 6}, ale naivné A{4,6} by akceptovalo aj 5 — alebo posunúť preferovanú zhodu ((A{2,3}){1,2} uprednostňuje tri riadky, kde A{2,6} vezme štyri), takže optimalizátor ich necháva nedotknuté. Nie je to jediný podmienený prepis: zlučovanie skupín a zlúčenie sufixu vyžadujú telo, ktoré spotrebuje pevný počet riadkov, zlúčenie prefixu odmieta skupinu s min 0, konečným max a nullable obsahom, neochotné uzly sa nezlučujú ani nenásobia ((A+?)+ zostáva) a prepis, ktorého nová hranica by pretiekla, sa odmietne.
Tvar prvku
Každý prvok plochého poľa predstavuje jednu pozíciu vo vzore. Existuje šesť logických druhov: odkaz na premennú (jediný druh, ktorý spotrebúva riadok); značky group begin a group end, ktoré otvárajú a zatvárajú sub-vzor v zátvorkách; značka alternácie, ktorá vedie zoznam vetiev; oddeľovač vetiev, ktorý ukončuje každú vetvu; a finish značka na konci vzoru.
Každý prvok tiež nesie hĺbku (úroveň zanorenia skupiny), kvantifikátor (počet min a max opakovaní, možno nekonečný) a dva ukazovatele prechodu — next, „kam ísť po spotrebovaní tohto prvku," a jump, „kam preskočiť" (používa značka alternácie a oddeľovače vetiev na zreťazenie vetiev, group begin na pomenovanie vlastného group end — skupina, ktorej kvantifikátor povoľuje nulu, sa preskočí cez next tohto konca — a group end na cyklenie späť do tela).
Pre PATTERN ((A B)+) kompilované pole vyzerá takto:
PATTERN ((A B)+) sa skompiluje na:
[0] BEGIN depth 0 quant 1..∞
next → 1 jump → 3
(otvára skupinu; jump pomenúva
vlastný END)
[1] A depth 1 quant 1..1
next → 2
[2] B depth 1 quant 1..1
next → 3
[3] END depth 0 quant 1..∞
next → 4 jump → 1
(zatvára skupinu; jump cyklí späť)
[4] FIN vzor kompletný
Vzor sa číta zľava doprava cez next, pričom jump spracúva nelineárne hrany. Na idx 3 jump END ukazuje späť na idx 1, čím vonkajší neohraničený kvantifikátor cyklí; na idx 0 jump BEGIN pomenúva jeho END na idx 3, a ak by skupina bola voliteľná, preskočenie by odišlo cez next tohto END na idx 4 bez príchodu na END. Beh nikdy nemusí konštruovať graf za behu — len sleduje tieto dva ukazovatele počas prechádzania poľa.
Atribúty na prvok
Okrem tvaru každý prvok nesie päť logických atribútov, ktoré riadia správanie behu na tej pozícii:
- Reluctant (neochotný)
- Obracia poradie expanzie kvantifikátora. Greedy kvantifikátory skúšajú „cykluj znova" pred „výstup"; neochotné kvantifikátory skúšajú „výstup" najprv. Nesený premennou pre
A+?; nesený BEGIN a END skupiny pre((…)+?). - Empty-loopable
- Nastavený na koncoch skupín, ktorých telo je nullable (
(A? B?)+,(A | B*)+;(A?)*sa najprv vynásobí naA*a nezanechá žiadny koniec skupiny). Hovorí behu pridať pod min rýchly výstup vedľa normálneho cyklenia späť, aby cycle guard nezabil legitímne zhody v skupinách, ktoré môžu produkovať prázdne iterácie. - Empty-preferred
- Nastavený na koncoch skupín, ktorých telo uprednostňuje prázdnu zhodu, ako v
(A?? B??){2}. Radí rýchly výstup pred cyklenie späť pod min, kde vlastná greediness skupiny nič nehovorí. - In-absorbable-region
- Označuje každý prvok, ktorý leží v rámci regiónu vhodného na absorpciu — používa beh na sledovanie, či je aktuálny stav stále v bezpečnom území.
- Absorption-comparison-point
- Označuje konkrétny prvok, kde by sa mali spúšťať porovnania absorpcie. Pre jednoduché
A+pristane na premennej; pre neohraničenú skupinu ako(A B)+pristane iba na konci skupiny.
Rozdelenie medzi „in-region" a „comparison-point" je dôležité, pretože absorpcia má zmysel iba v bodoch, kde sa iterácie uzatvárajú. Vnútri tela (A B)+ je beh v polovici iterácie a počet ešte nedosiahol svoju finálnu hodnotu pre toto kolo; porovnávanie tu by znamenalo porovnávanie neporovnateľných hodnôt. Stav musí dosiahnuť koniec skupiny, kým môže beh rozhodnúť. Prvý atribút teda hovorí „si stále v absorbovateľnom území"; druhý hovorí „dosiahol si bod porovnania — choď skontrolovať."
Analýza absorbovateľnosti
Krok 6 kompilácie je to, čo dáva pravidlu „rovnakého osudu" z §2.5 jeho kompilačno-časový dôkaz. Rozhodnutie je vrstvené:
isAbsorbable(query):
ak režim SKIP != SKIP PAST LAST ROW
→ vrátiť false
ak koniec rámca != UNBOUNDED FOLLOWING
→ vrátiť false
ak akýkoľvek DEFINE závisí od match_start
→ vrátiť false
prejsť ploché pole od
prvku 0 a označiť prvky,
ktoré spĺňajú štrukturálny prípad
Prvé tri kontroly sú na úrovni dotazu: zodpovedajú presne podmienkam §2.7 (strana výstupu: režim SKIP), ohraničenému rámcu (hranica láme monotónnosť) a §2.6 (strana dát: FIRST alebo posunové LAST v DEFINE). Keď ktorákoľvek z nich zlyhá, analýza nenastavuje žiadne príznaky a absorpcia je vypnutá v rámci celého dotazu. Keď všetky prejdú, prechod pripúšťa štyri štrukturálne tvary:
- Prípad 1 — Jednoduchá neohraničená premenná
-
Každá iterácia je presne jeden riadok. Počet skoršieho kontextu je vždy ≥ ako neskoršieho v každej zdieľanej pozícii.
A+,A*,A{2,∞} - Prípad 2 — Skupina s pevnou dĺžkou, neohraničený vonkajší
-
Každý potomok má
(A B)+,(A B{2})+,((A (B C){2}){2})+min == max, takže telo je sémanticky ekvivalentné svojej rozvinutej forme{1,1}—(A B{2})+sa správa ako(A B B)+. Každá iterácia spotrebuje pevný počet riadkov; dominancia počtu stále platí. - Prípad 3 — Skupina, ktorej telo začína neohraničenou premennou
-
Vedúca neohraničená premenná je sama absorbovateľná (Prípad 1) a chráni skoršie kontexty. Absorpcia sa zastavuje, len čo sa stav posunie za A — zvyšok tela nemá záruku monotónnosti, takže A dostane oba príznaky, obklopujúci BEGIN dostane príznak in-region a B ani END nedostanú žiadny.
(A+ B)+,(A+ B){2} - Prípad 4 — Alternácia
-
Každá vetva, dosiahnutá cez reťaz oddeľovačov, sa posudzuje samostatne podľa prípadov vyššie; značka alternácie dostane príznak in-region, keď sa kvalifikuje ktorákoľvek vetva.
A+ | B+,A+ | C D
Štrukturálne prípady nepokryté týmito štyrmi tvarmi sú rovnako poučné. A B+ nemožno súčasným pravidlom absorbovať, pretože vedúce A spotrebuje riadok skôr, ako začne neohraničená časť, takže kontexty začínajúce o jeden riadok inak sú na rôznych pozíciách vnútri neohraničeného tela. Neochotné kvantifikátory ako A+? sú vylúčené konštrukciou: pravidlo absorpcie predpokladá greedy sémantiku, kde dlhšie zhody pohlcujú kratšie, a neochotné zhodovanie ten smer obracia.
Výsledkom je rozhodnutie na prvok, nie na vzor. Jediný plán dotazu môže mať absorpciu zapnutú pre vedúce A+ vzorov ako (A+ B+ C) alebo (A+ B+)+ — to druhé je len Prípad 3 aplikovaný na svoj vedúci prvok — a vypnutú pre všetko za tým; beh jednoducho konzultuje atribút comparison-point na prvku aktuálneho stavu zakaždým, keď uvažuje o priechode absorpcie. Keď sa stav posunie do regiónu, ktorý nemožno absorbovať, absorpcia je pre ten stav natrvalo vypnutá — presne to, čo §2.5 a §2.6 potrebujú byť pravdivé na algoritmickej úrovni.
3.3 Navigácia — výmena n-tice s 1 slotom
DEFINE výrazy sú obyčajné SQL výrazy vyhodnocované oproti riadku, ale môžu zahŕňať PREV, NEXT, FIRST alebo LAST — odkazy, ktoré ukazujú na iné riadky. Samotné riadky sú už vo vyrovnávacej pamäti tuplestoru okna; čo musí vykonávateľ ešte spravovať, je tuple slot, z ktorého číta mechanizmus SQL výrazov, keďže odkazy na stĺpce vnútri výrazu sú viazané na slot v čase plánu. Implementácia znovu používa jediný navigačný slot pre každé navigačné volanie: slot sa pred vyhodnotením vnútorného výrazu vymení a po ňom obnoví, takže zvyšok mechanizmu SQL výrazov nikdy nepozná rozdiel.
Model, ktorý vykonávateľ vidí, je malý: existuje slot aktuálneho riadka, ktorý drží riadok, voči ktorému sa DEFINE výraz vyhodnocuje, a navigačný slot, ktorý beh môže dočasne presmerovať na iný riadok. Okolo akéhokoľvek navigačného volania beh nastaví navigačný slot, vyhodnotí vnútorný výraz, ako keby čítal aktuálny riadok, a potom obnoví pôvodný riadok. Pseudokód:
eval_navigation(call):
targetPos = compute_target_position(call)
ak je targetPos mimo platného rozsahu:
vrátiť NULL
uložiť current_row_slot
ak targetPos != currentPos:
načítať riadok na targetPos
do nav_slot
nasmerovať vonkajší slot na nav_slot
result = eval_inner_expression()
obnoviť current_row_slot
skopírovať by-ref result z nav_slot
vrátiť result
Trik je v tom, že existuje presne jeden slot na uloženie a obnovenie. Vnútorný výraz — čokoľvek to je, vrátane aritmetiky, volaní funkcií alebo iných odkazov na stĺpce — beží oproti vymenenému slotu pomocou tej istej vyhodnocovacej cesty, akú by použil pre aktuálny riadok. Žiadny alternatívny vyhodnocovač a žiadny slot na odkaz; keď je cieľom aktuálny riadok, načítanie aj výmena sa úplne preskočia. Načítanie skopíruje cieľový riadok do navigačného slotu (pokiaľ ho slot už nedrží) a krok obnovenia skopíruje výsledok odovzdávaný odkazom do pamäte na n-ticu, aby ho ďalšie načítanie nemohlo uvoľniť.
Zložená navigácia sa sploští v čase parsovania, takže výmena sa stále deje raz. PREV(FIRST(price)) je rozpoznané ako dvojkroková navigácia — „choď na prvý zhodnutý riadok, potom o jeden riadok skôr" — a uložené ako jediné navigačné volanie s zloženým druhom. Beh počíta cieľovú pozíciu v dvoch etapách, ale vykoná iba jednu výmenu slotu na načítanie finálneho riadka:
compute_target_position(call):
# relatívne k aktuálnemu riadku
PREV(n):
return currentPos − n
NEXT(n):
return currentPos + n
# relatívne k zhode
FIRST(n):
return matchStart + n
LAST(n):
return currentPos − n
# zložené: rel. k zhode, potom krok
PREV(FIRST(n), m):
return (matchStart + n) − m
NEXT(FIRST(n), m):
return (matchStart + n) + m
PREV(LAST(n), m):
return (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − n) + m
validovať voči vhodnému rozsahu
(rozsah zhody pre vnútorné FIRST/LAST,
rozsah partície pre vonkajší krok)
Cache pozícií skratuje načítanie z tuplestoru, keď viaceré navigačné volania v tom istom DEFINE cieľa na ten istý riadok — bežné vo výrazoch ako price > PREV(price) AND volume > PREV(volume), kde sa obe volania rozriešia na predošlý riadok. Cache ukladá iba „naposledy načítanú pozíciu" a samotná výmena zostáva jednou operáciou.
Klasifikácia navigačných volaní je príspevkom plánovača k rozhodnutiu o absorpcii. Plánovač prechádza každý DEFINE výraz a triedi každú premennú do jedného z dvoch košov podľa toho, či všetky kontexty vypočítajú tú istú logickú hodnotu v tom istom riadku, alebo každý kontext vypočíta vlastnú. Kôš určuje dve veci za behu: ako často sa premenná vyhodnocuje (raz zdieľaná, alebo raz na dotknutý kontext — §3.5 Fáza 1), a či je absorpcia kontextu vôbec možná (§2.5 vs §2.6): jediná premenná závislá od začiatku zhody ju vypne pre celý vzor.
- Bez navigácie
- Iba
PREV/NEXT LASTbez posunu- Zložené s vnútorným
LAST(bez posunu)
LASTs posunomFIRST(akákoľvek forma)- Zložené s vnútorným
FIRST - Zložené s vnútorným
LAST(s posunom)
Klasifikácia sa vykonáva v čase plánu a ukladá sa pri každej premennej DEFINE, takže beh netrávi čas rozhodovaním — jednoducho číta kôš pre každú premennú pri spracovaní riadka.
Rozpočet uchovávania
Navigácia siaha do riadkov, ktoré mechanizmus okenných funkcií inak prúdovo prešiel. Aby boli tie riadky dostupné, vykonávateľ je postavený na tuplestore, ktorý zachováva posuvné okno nedávnych riadkov; otázkou je, aké široké musí to okno byť. Vykonávateľ to určí z dvoch doplnkových posunov, pričom každý posun vyrieši raz na sken (konštantné aj pri inicializácii vykonávateľa, aby ich mohol ukázať obyčajný EXPLAIN):
- Rozpočet lookback
- Ako ďaleko dozadu od aktuálneho riadka môže akékoľvek volanie DEFINE siahnuť.
- Rozpočet lookahead-od-začiatku
- Minimálny dosah dopredu (dozadu, ak je záporný) od začiatku zhody najstaršieho živého kontextu — najskorší riadok, ktorý môže akékoľvek volanie DEFINE potrebovať.
Za behu sa značka orezania tuplestoru nastavuje na to, ktorá z dvoch pozícií je skoršia — aktuálny riadok mínus rozpočet lookback, a začiatok zhody najstaršieho živého kontextu plus rozpočet lookahead. Čokoľvek pred touto značkou nemôže dosiahnuť žiadne navigačné volanie v žiadnom živom kontexte, a tuplestore to môže zahodiť. Riadky Nav Mark, ktoré EXPLAIN hlási (§3.7) — Lookback a Lookahead — sú tieto dva rozpočty, nie namerané vrcholy. Každý sa tlačí iba vtedy, keď ho napája nejaká navigácia, a zobrazuje sa aj bez ANALYZE; posun, ktorého hodnota je známa až za behu (napríklad parameter generického plánu), sa pod obyčajným EXPLAIN tlačí ako runtime a pod EXPLAIN ANALYZE ako jeho vyriešená hodnota, a retain all (Lookback) alebo infinite (Lookahead) označuje posun, ktorý pretečie.
3.4 Hranice zhody — SKIP, INITIAL a ohraničený rámec
Výsledok zhody sa zaznamenáva ako dve hodnoty: riadok, v ktorom zhoda začína, a jej dĺžka. Záporný začiatok znamená, že pozícia ešte nebola vyhodnotená; len čo je začiatok nastavený, následné dotazy voči vykonávateľovi — „je tento riadok vnútri zhody?" — môžu odpovedať v O(1) prezretím dvojice. Dĺžka kóduje výsledok: -1 pre nezhodnutý riadok, 0 pre prázdnu zhodu a počet riadkov pre skutočnú zhodu. Dĺžka nula je skutočným výsledkom, nie chybou: predstavuje vzor, ktorý sa zhodol bez spotrebovania ktoréhokoľvek riadka, čo musí vykonávateľ odlíšiť od nezhodnutého riadka aj od „v tejto pozícii ešte nebola pokúsená žiadna zhoda."
Klauzula AFTER MATCH SKIP rozhoduje, kde začína nasledujúci pokus o zhodu. AFTER MATCH SKIP PAST LAST ROW sa presúva na riadok za koncom zhody, čím produkuje neprekrývajúci sa výstup, ktorý chce väčšina dotazov, a umožňuje optimalizáciu absorpcie.
AFTER MATCH SKIP TO NEXT ROW sa presúva iba na riadok za začiatkom zhody, čím umožňuje prekrývajúce sa zhody; plánovač preto vypína absorpciu pre vzor tohto okna, keď je tento režim v platnosti.
Dva skip ciele, ktoré norma tiež definuje — AFTER MATCH SKIP TO FIRST var a AFTER MATCH SKIP TO LAST var — závisia od histórie na zhodu, ktorú tento patch neudržiava. V gramatike vôbec nie sú prítomné, takže parser vyvoláva všeobecnú syntaktickú chybu, ak je niektorý uvedený.
To isté platí pre SEEK, alternatívu k INITIAL v špecifikácii. Pri SEEK môže pokus o zhodu začínajúci v riadku R uspieť v ktoromkoľvek riadku od R po koniec rámca, nielen v R samotnom. Patch implementuje iba INITIAL: každá potenciálna zhoda je ukotvená v konkrétnom riadku. Parser vyvoláva chybu, ak je požadovaný SEEK. Ohraničené rámce dostávajú vlastné zaobchádzanie — keď používateľ napíše ROWS BETWEEN CURRENT ROW AND N FOLLOWING namiesto UNBOUNDED FOLLOWING, vykonávateľ skratuje akýkoľvek kontext, ktorého zhoda dosiahla hranicu, vynútením nezhody, a absorpcia sa vypína, pretože hranica láme predpoklad monotónnosti, na ktorom absorpcia spočíva.
3.5 Trojfázový motor na riadok
Driver vykonávateľa na riadok je vyvolaný okolitým mechanizmom okenných funkcií vždy, keď potrebuje vedieť, či daný riadok patrí do zhodnutého rámca. Driver nájde alebo vytvorí kontext pre aktuálnu začiatočnú pozíciu, potom poháňa NFA dopredu riadok po riadku — pre každý riadok resetuje pole zhôd na premennú na „nevyhodnotené" — kým tento kontext nemá žiadne živé stavy alebo kým partícia neskončí. Predikáty DEFINE sa vyhodnocujú lenivo: premenná sa vyhodnotí, keď ju nejaký stav prvýkrát spotrebúva, takže premenná, ktorú v tomto riadku netestuje žiadny živý stav, sa nikdy nevyhodnotí. Samotný krok dopredu pozostáva z troch fáz v pevnom poradí — Match, Absorb, Advance — obalených v tej istej vonkajšej slučke:
processRow(currentPos):
# Fáza 1 — MATCH (konvergencia)
pre každý kontext:
ak kontext dosiahol koniec svojho rámca:
vynútiť nezhodu (finalizovať skoro)
continue
ak sa matchStartRow líši od
zdieľanej vyhodnocovacej pozície:
resetovať DEFINE premenné závislé
od match-start na nevyhodnotené (§3.3)
match(context, varMatched)
# Fáza 2 — ABSORB
ak je vzor absorbovateľný:
obnoviť príznaky každého kontextu
absorb_contexts()
# Fáza 3 — ADVANCE (divergencia)
pre každý kontext:
advance(context, currentPos)
ak zaznamenal zhodu a
SKIP PAST LAST ROW:
orezať neskoršie kontexty,
ktoré začínajú vnútri zhody
Poradie nie je štylistickou voľbou. Match musí bežať prvý, pretože absorpcia porovnáva post-match počty; spustenie Absorb pred Match by porovnávalo stavy, ktoré sa chystajú zomrieť. Advance musí bežať posledný, pretože je to jediná fáza, ktorá vytvára nové stavy — expanduje každý prežívajúci stav cez epsilon prechody, kým každá vetva nedosiahne premennú čakajúcu na ďalší riadok. Spustenie Absorb po Advance by znamenalo porovnávanie divergovaných nasledovníkov, čím by sa minul bod, v ktorom sú stavy najčistejšie porovnateľné.
Fáza 1 — Match
Match je „konvergenčná" fáza: stavy buď prežívajú s inkrementovaným počtom, alebo hynú. Jemný bod je, že pre premenné sediace v absorbovateľnom regióne Match tiež vykonáva malé množstvo postupu vpred, aby Absorb mohol porovnávať čisto. Podmienka pokrytia sa spúšťa iba v absorbovateľnom bode porovnania — v END neohraničenej skupiny — takže stavy, ktoré práve zhodili premenné v polovici iterácie (ako B vnútri (A B)+), je potrebné prejsť až k tomu bodu porovnania počas samotného Match; inak Absorb nenájde nič vhodné na porovnanie a optimalizácia sa nikdy nezapne.
match(context, varMatched):
pre každý stav v kontexte:
elem = pattern[state.elemIdx]
assert elem je premenná
# advance parkuje iba premenné
ak varMatched[elem.varId] je
nevyhodnotené:
teraz vyhodnotiť jej DEFINE
ak nie varMatched[elem.varId]:
zhodiť stav # mŕtva vetva
continue
state.counts[elem.depth] += 1
# Inline postup vpred, aby
# nasledujúca fáza mohla porovnávať
# v prvku bodu porovnania, nie
# v polovici iterácie.
ak je elem in-region, ale nie
bod porovnania,
a dosiahol max počet,
a elem.next je koniec skupiny:
prejsť reťaz END:
inkrementovať počet vonkajšej skupiny
posunúť state.elemIdx na END
pokračovať, kým je in-region,
musí výjsť, a next je END
(zastavuje sa v bode porovnania
alebo na ešte cyklovateľnom prvku)
Prechod reťazom END je to, čo robí vnorené skupiny s pevnou dĺžkou absorbovateľnými. V ((A B){2})+, keď B dosiahne svoj max (B je {1,1}), počet vnútornej skupiny musí inkrementovať; ak ten počet tiež dosiahne svoj max — zatvárajúc vnútorné {2} — počet vonkajšej skupiny musí tiež inkrementovať a tak ďalej, kým stav nepristane na najvonkajšom bode absorpcie — END neohraničenej vonkajšej skupiny (+). Vykonanie tejto práce v Match umožňuje Absorb porovnávať oproti kontextom, ktoré už konsolidovali svoje post-iteračné počty.
Fáza 2 — Absorb
Absorb prechod prechádza kontexty od najnovšieho (chvost) k najstaršiemu (hlava). Pre každý prebiehajúci kontext, ktorý je plne absorbovateľný, skenuje dozadu starší prebiehajúci kontext, ktorý ho pokrýva, a uvoľňuje novší, ak je nájdený. Pretože sú kontexty udržiavané v poradí vytvorenia a každý riadok vytvára najviac jeden kontext, „novší" a „starší" skutočne znamená „začal neskôr" a „začal skôr."
absorb_contexts():
pre ctx od chvosta dozadu:
ak je ctx ukončený
alebo má neabsorbovateľný stav
alebo drží zaznamenanú zhodu:
preskočiť
pre starší od ctx.prev dozadu:
ak je starší ukončený
alebo nemá absorbovateľný stav:
preskočiť
ak covered(starší, ctx):
free(ctx)
zaznamenať dĺžku absorpcie
break
covered(older, newer):
pre každý stav v newer:
elem = pattern[state.elemIdx]
ak elem nie je bod porovnania:
return false
ak v older neexistuje stav s:
rovnakým elemIdx
a isAbsorbable
a older.counts[depth]
>= newer.counts[depth]:
return false
return true
Z toho vyplývajú dve mikro-rozhodnutia. Prvým je, že kontrola pokrytia okamžite odmieta, ak akýkoľvek stav v novšom kontexte sedí inde ako v bode porovnania — porovnávanie v bodoch nesúdneho rozhodnutia by nebolo zmysluplným porovnávaním.
Druhým je asymetrický pár príznakov na každom kontexte: has-absorbable-state odpovedá „môže tento kontext absorbovať novší?" a je monotónny (môže ísť iba true→false ako stavy hynú), zatiaľ čo all-states-absorbable odpovedá „môže byť tento kontext absorbovaný?" a je dynamický (preklápa sa späť na true, keď je odstránený neabsorbovateľný stav), kým kontext nezaznamená zhodu, čo ho natrvalo nastaví na false — absorpcia by uvoľnila zhodu, ktorú žiadny absorbujúci kontext nedokáže reprodukovať. Oba príznaky sú kontrolované v konštantnom čase ešte pred začiatkom skenovania pokrytia, takže absorpcia platí svoju plnú cenu iba na kontextoch, ktoré majú reálnu šancu byť absorbované.
Fáza 3 — Advance
Advance je „divergenčná" fáza: každý prežívajúci stav je expandovaný cez epsilon prechody, kým každá vetva nedosiahne buď premennú čakajúcu na ďalší riadok, alebo FIN sentinel. Expanzia je do hĺbky a poradie, v ktorom sa prechádzajú súrodenecké vetvy, je to, čo robí pravidlo preferencie normy skutočne účinné — lexikálne prvá vetva je vždy pridaná ako prvá a deduplikačný krok pri vkladaní stavu ticho zahadzuje ekvivalentné neskoršie pridania.
advance(context, currentPos):
vytiahnuť všetky aktuálne stavy;
prebudovať ctx.states od nuly
pre každý stav v lexikálnom poradí:
vyčistiť visited bitmapu
advance_state(state) # DFS
# Preferencia: keď DFS dosiahne FIN,
# zvyšné stavy sú menej preferované
# a môžu byť zahodené.
ak FIN dosiahnuté a stavy zostávajú:
uvoľniť zvyšok
break
advance_state(state):
prejsť cez state.elemIdx,
rekurzia cez:
ALT vetvy (v poradí, zastaví sa,
keď je FIN zaznamenaný),
BEGIN (vstúpiť do skupiny; plus voliteľná
skip cesta, ak min = 0),
END (cyklus späť / výstup / fast-forward —
pozri nižšie),
FIN (zaznamenať matchEndRow,
uložiť matchedState a označiť
kontext, aby neskoršie kontexty
vnútri rozsahu tohto kandidáta
boli orezané — pozri nižšie),
zastavujúc sa pri každej stretnutej premennej:
pridať stav do ctx.states
(deduplikácia podľa elemIdx + counts)
Zaznamenanie stavu, ktorý dosiahol FIN, robí viac ako len záložku kandidátskej zhody. Pri AFTER MATCH SKIP PAST LAST ROW musí ďalšia oznámiteľná zhoda začať striktne za aktuálnou — takže len čo Advance dokončí prácu s kontextom, ktorý zaznamenal kandidáta, každý nasledujúci kontext, ktorého začiatočný riadok spadá do rozsahu kandidáta, je orezaný v tom istom riadku, hoci kontext, ktorý zasiahol FIN, môže pokračovať v hľadaní dlhšej zhody cez greedy návrat.
Orezanie je bezpečné, pretože bez ohľadu na to, ako toto hľadanie skončí (dlhšia zhoda nahradí kandidáta, alebo kandidát zostane), všetky orezané kontexty začali vnútri rozsahu, ktorý ďalšia oznámiteľná zhoda musí preskočiť, a preto by nikdy nemohli produkovať vlastný výstup.
Toto je krok orezania naprieč kontextami v čase FIN. Vnútri kontextu FIN tiež odrezáva lexikálne podriadenú prácu: Advance zahadzuje zostávajúce stavy vo fronte (opísané skôr v tejto sekcii) a v rámci jedného DFS sa každá menej preferovaná cesta — neskoršie vetvy ALT, druhá z ciest preskočenia a vstupu BEGIN, vstupná cesta neochotnej premennej, druhá z ciest cyklu a výstupu END — zastaví, len čo je zhoda zaznamenaná, takže jeden advance zaznamená najviac jednu zhodu.
Najzákernejšia logika na prvok žije v END handleri. Keď je počet iterácií skupiny pod dolnou hranicou, beh musí cyklovať späť; keď je na alebo nad hornou hranicou, musí vystúpiť; medzi tým sú obe možnosti platné a greediness kvantifikátora rozhoduje, ktorú skúsiť ako prvú:
advance_end(state, elem):
count = state.counts[elem.depth]
ak count < elem.min:
cyklovať späť do tela
ak je elem empty-loopable:
# nullable telo, viď §3.2
klonovať aj fast-forward
stav, ktorý opúšťa skupinu
s count splneným
(najprv fast-forward, ak telo
uprednostňuje prázdne; druhá
cesta sa zahodí, ak prvá
dosiahla FIN)
inak ak count >= elem.max:
vynulovať counts v tejto hĺbke
vystúpiť cez next
(END→END: inkrementovať count
vonkajšieho END)
else:
# min <= count < max: rozvetviť
vytvoriť výstupný stav
(počty v tejto hĺbke vynulovať)
ak greedy:
najprv cyklus
ak cyklus dosiahol FIN:
zahodiť výstup
# uprednostniť dlhšie
inak výstup druhý
inak (reluctant):
najprv výstup
ak výstup dosiahol FIN:
zahodiť cyklus
# uprednostniť kratšie
inak cyklus druhý
Každý stav pridaný do kontextu prechádza deduplikačnou kontrolou, ktorá porovnáva jeho pozíciu a počty s existujúcim zoznamom stavov. Keďže Advance spracúva vetvy v poradí DFS, stav z prvej vetvy akejkoľvek alternácie pristane prvý — a akákoľvek neskoršia vetva produkujúca tú istú pozíciu a počty je pri vkladaní odmietnutá. Toto je presne to, o čo žiada pravidlo lexikálneho poradia z §2.4, implementované na dne behu bez osobitného prechodu.
Empty-loopable skupiny
Jemný prípad, ktorý beh musí zneškodniť, je nullable skupina — skupina, ktorej telo sa môže zhodovať s nula riadkami, pretože každý potomok tela je sám voliteľný. Vzory ako (A? B?)+ a (A | B*)+ majú túto vlastnosť: v závislosti od dát môže telo dokončiť iteráciu bez spotrebovania ktoréhokoľvek riadka. (Jediný voliteľný potomok ako (A?)* sa v čase kompilácie prepíše na A* a nezanechá žiadnu skupinu.) To je v princípe v poriadku, ale vytvára to skutočné nebezpečenstvo pre epsilon expanziu NFA. Ak telo produkuje prázdnu zhodu, prvok END cyklí späť do tela (jeho jump je prvý potomok skupiny), telo opäť produkuje prázdnu zhodu, znova dosiahne END atď. Bez niečoho, čo by to zastavilo, by DFS Advance nikdy neukončil.
Ochrana je rozhodnutá v čase kompilácie a vykonávaná za behu. Vždy keď plánovač vidí skupinu, ktorej telo je nullable, označuje prvok END tej skupiny ako empty-loopable. Beh udržiava visited bitmapu, vyčistenú pred každou DFS expanziou stavu, v ktorej sa označujú iba tieto END so značkou empty-loopable — nič iné nemôže cykliť, pretože každé iné cyklenie späť spotrebovalo riadok. Dosiahnutie označeného END znamená, že telo práve odvodilo prázdnu iteráciu, a stav sa nezahodí: na dolnej hranici alebo nad ňou tam opustí skupinu (prázdna iterácia zastavuje kvantifikátor) a pod ňou prepadne do normálneho cyklenia späť, takže každý prázdny príchod stále zvyšuje počet, kým nedosiahne min. Vezmime (A? B?){2,3}, kde sa žiadna z premenných nezhoduje nikde v prúde riadkov:
iter 1: A? B? sa zhodujú s nula riadkami
→ END, count = 1 (pod min)
END už označený (pri vstupe
do skupiny), ale pod min:
→ cyklus späť do A?
iter 2: A? B? sa zhodujú s nula riadkami
→ END, count = 2 (spĺňa min)
END už označený, na min:
→ opustiť skupinu
výstup s nulovou dĺžkou zhody
Pod dolnou hranicou empty-loop značka tiež hovorí END handleru, aby naklonoval ďalší fast-forward stav vedľa normálnej cesty cyklenia späť:
advance_end (count pod min):
cesta cyklenia späť:
cyklovať späť do tela
(necháva otvorené dvere pre skutočnú,
neprázdnu zhodu v ďalšej
iterácii)
ak je elem empty-loopable:
fast-forward cesta:
vynulovať počet v tejto hĺbke
vystúpiť zo skupiny cez next,
zaobchádzajúc s zostávajúcimi
požadovanými iteráciami ako prázdnymi zhodami
Dve cesty hrajú doplnkové úlohy. Cyklus späť je to, čo zachytáva prípad, kde telo má neskôr stále skutočné zhody na produkciu — napríklad v (A? B?){2,3} nasledovanom dátami, kde sa A zhoduje iba v neskorších riadkoch, cyklus späť je to, čo umožňuje druhej a tretej iterácii nájsť neprázdne zhody. Fast-forward okamžite opúšťa skupinu, deklarujúc „zvyšok požadovaných iterácií je prázdny," a umožňuje zhode uspieť s telom nulovej dĺžky. O poradí rozhoduje telo, nie vlastná greediness skupiny: fast-forward ide prvý presne vtedy, keď telo uprednostňuje prázdnu zhodu (neochotné telo ako (A?? B??)), a ak prvá cesta dosiahne FIN, druhá sa zahodí, takže menej preferovaná cesta nemôže nahradiť preferovanú zhodu. Deduplikačná kontrola v čase vkladania zabraňuje ktorejkoľvek ceste vyplodiť viac stavov, ako je jej podiel.
Okrem cycle guardu jeden ďalší trik pri štartovaní rieši dvojznačnosť výsledkov nula-riadkov na úplnom začiatku kontextu. Krok vytvorenia kontextu v každom potenciálnom začiatočnom riadku spúšťa počiatočný advance cez epsilon prechody pred spotrebovaním ktoréhokoľvek riadka, používajúc pozíciu o jeden riadok pred skutočným začiatkom. Akákoľvek cesta, ktorá dosiahne FIN sentinel iba cez epsilon prechody — bez spotrebovania riadka — preto produkuje koncovú pozíciu menšiu ako začiatočná pozícia; tá súradnica záporného rozsahu, kombinovaná s tým, či bol FIN skutočne dosiahnutý, kóduje rozdiel medzi prázdnou zhodou (zhoda dĺžky 0 prijatá) a nezhodným začiatkom bez potreby osobitného príznaku.
3.6 Ako priestor stavov zostáva ohraničený
Udržanie behu ohraničeného nie je výsledkom jedinej optimalizácie. Je kumulatívnym efektom vrstvenej sady orezávacích pravidiel, každé z nich zachytáva inú príčinu rastu priestoru stavov v inom bode cyklu na riadok. Niektoré sú rozhodnuté v čase kompilácie a iba konzultované za behu; iné sa spúšťajú dynamicky. Niektoré zabíjajú jednotlivé stavy; iné zabíjajú celé kontexty. Sekcie vyššie predstavili každú z nich v kontexte; tabuľka nižšie ich kladie na jednu stranu.
- Zlyhaný predikát Match
- Stavy premenných, ktorých DEFINE bolo na aktuálnom riadku vyhodnotené ako false — mŕtve vetvy.
- Inline end-chain advance Match
- Premenné, ktoré dosiahli svoj max počet a inak by stav opustili v polovici iterácie; posunuté cez konce skupín s pevnou dĺžkou, aby absorpcia mohla porovnávať v správnom bode.
- Absorpcia kontextu Absorb
- Novšie kontexty, ktorých každý stav leží v bode porovnania a je pokrytý absorbovateľným stavom staršieho kontextu na tom istom prvku s väčším alebo rovnakým počtom — pozri §2.5 pre konceptuálne pravidlo, §3.2 pre vhodnosť v čase kompilácie, §3.5 pre kontrolu na pár.
- Deduplikácia stavov Advance
- Stavy dosiahnuté cez rôzne DFS vetvy, ktoré skončia na rovnakej pozícii s rovnakými počtami — prežíva iba prvý (lexikálne najskorší); neskoršie ekvivalenty sú ticho zahodené, čo je tiež spôsob, akým sa presadzuje preferencia (§2.4).
- FIN skoré ukončenie (v rámci kontextu) Advance
- Stavy stále čakajúce v DFS fronte, keď jedna vetva dosiahne FIN — podľa lexikálneho poradia sú všetky zostávajúce stavy menej preferované a môžu byť okamžite zahodené.
- Orezanie kandidátskej zhody (naprieč kontextami) Advance
- Iné kontexty, ktorých začiatočný riadok spadá do rozsahu kandidátskej zhody — kontext, ktorý zasiahol FIN, môže stále hľadať dlhšiu zhodu (greedy návrat), ale pri
AFTER MATCH SKIP PAST LAST ROWuž žiadny kontext vnútri rozsahu kandidáta nemôže produkovať oznámiteľný výstup bez ohľadu na to, ako toto hľadanie skončí, a je orezaný, len čo Advance dokončí prácu s kontextom, ktorý kandidáta zaznamenal. - Cycle guard Advance
- Epsilon expanzie, ktoré dosiahnu END nullable skupiny už označený v rámci toho istého DFS (označený pri vstupe cez BEGIN alebo pri skoršom príchode) — inak by cyklili navždy; na dolnej hranici alebo nad ňou tam stav opustí skupinu a pod ňou pokračuje v cyklení.
- Empty-loop fast-forward Advance
- Pod dolnou hranicou nullable skupiny ďalšia cesta, ktorá opúšťa skupinu so zostávajúcimi požadovanými iteráciami deklarovanými ako prázdne, zoradená voči cyklu späť podľa preferencie tela.
- Cutoff ohraničeného rámca Match
- Kontexty, ktorých zhoda dosiahla používateľom určenú hornú hranicu rámca — vynútené k nezhode, aby sa nemohli rozšíriť za ňu (§3.4).
Čítanie záznamov podľa ich fázového odznaku stopuje životnosť kontextu: orezanie sa spúšťa v každom riadku cez tri hlavné fázy (Match, Absorb, Advance). Čítanie opisov namiesto toho zoskupuje pravidlá podľa toho, na čo cieľujú: mŕtve vetvy, redundantné kontexty, ekvivalentné stavy, nekonečné cykly a predlžovanie za hranice uložené používateľom.
Žiadne jediné pravidlo samo by nestačilo. Samotný empty-loop fast-forward by nezastavil nekonečné epsilon cykly; samotná absorpcia by nadmerne konsolidovala, keď DEFINE odkazuje na match-start; samotná deduplikácia by neodstránila redundantné kontexty, iba redundantné stavy. Beh zostáva lineárny v prípadoch, ktoré sú dôležité — PATTERN (A+ B+ C+ D) na 100 000 riadkoch, benchmark panela ③ posteru — iba preto, že každá vrstva zachytáva to, čo vrstvy nad ňou vynechávajú. Zdrojový kód dokumentuje prípady, ktoré vrstvy nezachytia: deduplikácia ponecháva oddelene stavy, ktoré sa líšia iba počtami nad min, takže (A{2,} B)+ C, kde C nikdy nie je pravdivé, drží vo vrchole Θ(n²) stavov a vytvorí ich Θ(n³) (37 s na 320 riadkoch), a séria úplne nullable alternácií sa enumeruje cesta po ceste, takže (A?|B?){30} trvá vyše pol hodiny.
3.7 Výstup EXPLAIN
EXPLAIN ANALYZE na dotaze s RPR vystavuje štatistiky na úrovni NFA, ktoré nie sú prítomné pre obyčajné okenné funkcie. V textovom formáte sú vydávané spolu s okenným operátorom, za riadkom Pattern:, prípadnými riadkami Nav Mark (ktoré ukazuje aj obyčajný EXPLAIN) a riadkom Storage::
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(každý iba vtedy, keď DEFINE používa
navigáciu, ktorá ho napája)
NFA States: N peak, N total, N merged
NFA Contexts: N peak, N total, N pruned
NFA: N matched (len min/max/avg),
N mismatched (len min/max/avg)
NFA: N absorbed (len min/max/avg),
N skipped (len min/max/avg)
(druhý riadok NFA iba vtedy, keď je
niektorý z počtov nenulový; nulový
počet sa tlačí bez svojho (len ...))
Netextové formáty vydávajú každý počet ako samostatnú vlastnosť. Peak a total sú priamou inštrumentáciou behu: koľko stavov bolo niekedy súčasne živých, koľko bolo vytvorených počas životnosti dotazu a koľko bolo zlúčených deduplikáciou; pruned počíta kontexty, ktoré zlyhali po jedinom riadku. Histogramy dĺžok zhôd oddeľujú štyri výsledky — úspešné zhody, pokusy o zhodu, ktoré zlyhali po viac ako jednom riadku (mismatched), absorbované kontexty a kontexty uvoľnené pomocou AFTER MATCH SKIP PAST LAST ROW, pretože začali vnútri zaznamenanej zhody (skipped) — a ich reportovanie s min/max/avg robí výkonnostné patológie viditeľnými na prvý pohľad: zdravý beh ukazuje väčšinu kontextov ako buď zhodnuté, alebo absorbované, s malými dĺžkami nezhody.
Dva čítače Nav Mark reportujú rozpočet uchovávania tuplestoru, ktorý §3.3 odvodzuje z DEFINE. Lookback je najhlbší dosah dozadu od aktuálneho riadka cez PREV, LAST s akýmkoľvek posunom (vrátane predvoleného 0) a zložené formy s vnútorným LAST; Lookahead je minimálny dosah dopredu (záporný, keď hľadí pred začiatok zhody) meraný od začiatku zhody najstaršieho živého kontextu, prispievaný FIRST a zloženými formami s vnútorným FIRST.
Každý čítač sa tlačí ako pevné celé číslo, keď je posun konštantou, „runtime", keď je posun nekonštantným výrazom známym iba na sken, a — iba pre Lookback — „retain all", keď posun pretečie; Lookahead, ktorý pretečie, sa tlačí ako „infinite". Každý riadok sa vydáva iba vtedy, keď ho napája nejaká navigácia v DEFINE, a oba sa zobrazujú aj pod obyčajným EXPLAIN: konštantné posuny sa ustália pri inicializácii vykonávateľa, zatiaľ čo posun známy až za behu (napríklad parameter generického plánu) sa tam tlačí ako „runtime" a pod EXPLAIN ANALYZE ako jeho vyriešené celé číslo.
Spolu tieto čítače umožňujú ladiť výkon RPR bez pripájania gdb k backendu.
Okrem čítačov EXPLAIN tlačí riadok Pattern: zostavený zo skompilovaného poľa prvkov, takže ukazuje vzor po prepisoch v čase kompilácie (PATTERN (A A) sa vysvetlí ako a{2}) a nesie značky absorpcie # (bod porovnania) a ~ (absorbovateľný región); DEFINE a možnosť AFTER MATCH SKIP sa nezobrazujú. Reprodukovanie klauzúl tak, ako boli zapísané, vrátane neochotných kvantifikátorov, opakovania skupín a možnosti preskočenia, je úlohou pg_get_viewdef(), ktorá sa snaží, aby tento round-trip bol stabilný, aby pg_dump a pg_upgrade mohli zachovať objekty RPR bez sémantického posunu — regresná sada pod rpr_explain to overuje prípad od prípadu (pozri §4).
§4. Testy — mapa pokrytia
Patch sa dodáva s piatimi regresnými sadami, ktoré spolu cvičia každú vrstvu opísanú v §3 — približne 22 000 riadkov SQL, každá sada zameraná na iný problém. Rozdelenie je zámerné: udržiavanie záležitostí parsera, správnosti behu, interakcií plánovača a formátovania výstupu v oddelených súboroch uľahčuje lokalizovanie zlyhaní a zabraňuje, aby nesúvisiaca zmena v jednej vrstve náhodou neznehodnotila testy v inej. Päť sád je:
- rpr
- Integrácia klauzuly WINDOW — realistické okenné scenáre na syntetických akciových dátach (V-tvar, W-tvar, po sebe idúce vzostupy, obraty), plus sémantika navigácie a chyby obmedzení DEFINE.
- rpr_base
- Vrstva parsera — prijatie kľúčových slov, syntaktické tvary, kvantifikátory, parsovanie navigácie, chybové správy a stabilita round-tripu pg_dump/pg_upgrade; plus vrstva plánovača — optimalizácia vzorov, príznaky absorpcie, fallback optimalizácie, integrácia s plánovačom.
- rpr_nfa
- NFA runtime — trojfázová slučka, absorpcia v každom absorbovateľnom tvare a hraničné prípady životného cyklu kontextu.
- rpr_explain
- Formátovanie výstupu — NFA štatistiky, deparse vzoru, citovanie identifikátorov, stabilita formátu cez reload.
- rpr_integration
- Interakcie plánovača — strážcovia, ktorí zabraňujú nesúvisiacim okenným optimalizáciám korumpovať sémantiku RPR.
4.1 rpr — end-to-end scenáre
Scenárová sada je verejnou tvárou testovacej sady: používa syntetický dataset cien akcií s približne 1 600 riadkami a spúšťa proti nemu realistické dotazy — obnovenie V-tvaru, W-tvar (dvojité dno), po sebe idúce vzostupy a poklesy, obratové vzory, multi-symbolové partície. Tieto scenáre sú jediné testy, kde sa vstupy a výstupy čítajú ako dotazy, ktoré by používateľ skutočne napísal; zvyšok súboru je, podobne ako ostatné sady, redukcionistický — vnáranie PREV/NEXT a chyby nekonštantných posunov, pravidlá odkazov v DEFINE a sémantika navigačných posunov.
Pretože tieto dotazy kombinujú každú vrstvu (parser, plánovač, vykonávateľ, EXPLAIN), jediné zlyhanie v rpr vám zriedka povie, kde chyba žije. Štyri nasledujúce sady sú bisekciou: zlyhanie v rpr plus prechádzajúce rpr_base vylučuje parser; plus prechádzajúce rpr_nfa ho zužuje na scenárovo špecifické tvary dát; plus prechádzajúce rpr_integration vylučuje interferenciu plánovača; a akýkoľvek deparse posun sa objaví v rpr_explain.
4.2 rpr_base — povrch parsera
Základná sada je najväčšia a je najväčšia z dôvodu: je zodpovedná za dokázanie, že každý legálny kus syntaxe v §1.2 sa skutočne parsuje, každý nelegálny kus v §1.3 je odmietnutý s užitočnou chybou a každá akceptovaná forma prežíva serializačný round-trip. Hlavná časť je tvarovaná ako malé zamerané úryvky — jeden na syntaktickú vlastnosť — namiesto dlhých realistických dotazov, pretože cieľom je pokrytie, nie scenárová realistickosť. Druhá časť, vrstva plánovača, pokrýva optimalizáciu vzorov, zobrazenie a analýzu príznakov absorpcie, fallback optimalizácie a integráciu s plánovačom (poddotazy, spojenia, množinové operácie, triedenie a zoskupovanie).
Serializačné testy si zaslúžia osobitnú pozornosť. Objekty RPR (pohľady, materializované pohľady, výstup pg_dump) musia prejsť round-trip cez reprezentáciu katalógu bez sémantického posunu, vrátane jemností ako neochotný príznak na kvantifikátore alebo presná forma zloženého navigačného výrazu. Malá sada serializačne špecifických objektov (pohľady rpr_serial_v* a ich podporné tabuľky) je zámerne ponechaná na mieste na konci behu, takže okolitá regresná infraštruktúra ich môže zdvihnúť a cvičiť pg_dump a pg_upgrade proti nim. Zvyšok testovacieho lešenia je zhodený ako obvykle. Chyby ako strata neochotného príznaku cez deparse a re-parse sa objavia iba vtedy, keď je round-trip cvičený od konca po koniec.
4.3 rpr_nfa — runtime motor
Toto je sada, ktorá cvičí každý mechanizmus opísaný v §3.5 a §3.6. Jej testy sledujú konzistentný vzor: inline riadky VALUES nesúce pole názvov premenných, ktoré deklaruje, ktoré premenné DEFINE sa zhodujú v každom riadku, spárované so vzorom, ktorý skúma špecifické runtime správanie. Idióm poľa odpája runtime test od mechanizmu vyhodnocovania DEFINE — testuje sa „za predpokladu, že sa tieto premenné tu zhodujú, produkuje NFA slučka očakávaný rozsah zhody?" namiesto „vypočítava vyhodnocovač DEFINE výrazov správne tieto logické hodnoty?" Vyhodnocovač DEFINE sa testuje inde (rpr_base pre parsovanie, rpr pre end-to-end správanie).
Typický testovací fixture vyzerá takto — stĺpec polí mien premenných, kde každý záznam hovorí, ktoré premenné DEFINE sa spustia v tom riadku, a vzor, ktorého klauzuly DEFINE testujú tieto mená priamo:
SELECT id, flags, first_value(id) OVER w AS ms, last_value(id) OVER w AS me FROM (VALUES (1, ARRAY['A']), (2, ARRAY['A','B']), (3, ARRAY['A','B']), (4, ARRAY['B']), (5, ARRAY['_']), (6, ARRAY['A'])) AS t(id, flags) WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING INITIAL PATTERN (A+ B+) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags));
Čítanie stĺpca poľa nadol je čítaním testovacieho scenára priamo. Riadky 2 a 3 nesú obe mená — A aj B sa tam spúšťajú, takže NFA má skutočnú voľbu, kde prepnúť z A-vetvy na B-vetvu. Očakávaná zhoda (A v riadkoch 1–3 nasledovaná B v riadku 4, pri greedy preferencii normy) je fixovaná samotnými týmito príznakmi, bez vyhodnocovania výrazov akéhokoľvek významu tu — = ANY je len triviálnou vrstvou, ktorá vystavuje stĺpec poľa pre DEFINE, nie tým, čo test cvičí. Napísanie toho istého scenára s číselným predikátom (price > PREV(price) a podobne) by spojilo NFA test so správaním vyhodnocovača predikátov; idióm poľa udržiava obe čisto oddelené a zlyhanie tu ukazuje priamo na NFA slučku.
Pokrytie absorpcie je obzvlášť dôkladné, pretože absorpcia je optimalizáciou najpravdepodobnejšou na tiché produkovanie nesprávnych odpovedí, ak sa zapne, keď by nemala. Testy pokrývajú každý tvar z analýzy prípadov v §3.2:
- jednoduchá neohraničená premenná (
A+) — kanonický kolaps N na 1; - skupiny s pevnou dĺžkou (
(A B)+,(A B{2})+, trojúrovňovo vnorené((A (B C){2}){2})+); - vedúca neohraničená premenná s pevným sufixom (
A+ B) — iba vedúceA+nesie príznaky absorpcie, sufix nie; - absorpcia na vetvu vnútri alternácie (
B+ C | B+ D); - viacero neohraničených premenných (
A+ B+) — iba vedúca je absorbovateľná; - neochotné kvantifikátory (
A+?) — overené, že sú vylúčené z absorpcie; - nevedúce neohraničené (
A B+) — overené, že sú vylúčené.
Okrem absorpcie sada pokrýva životný cyklus kontextu: prekrývajúce sa kontexty pri AFTER MATCH SKIP TO NEXT ROW, čistenie zlyhaných kontextov uprostred prúdu, finalizácia neúplných kontextov na konci partície a kontexty stretnuté po tom, čo už bola kandidátska zhoda zaznamenaná vo vedúcom kontexte. Každé z nich sa mapuje na konkrétne orezávacie pravidlo v §3.6 a testy sú napísané tak, aby hlasno zlyhali, ak pravidlo zlyhá (buď ponechaním redundantných kontextov pri živote, alebo zabitím kontextu, ktorý mal produkovať výstup).
4.4 rpr_explain — stabilita výstupu
Výstup EXPLAIN je súčasťou kontraktu smerom k používateľovi — nástroje tretích strán (monitorovacie dashboardy, log scrapery) ho parsujú a zmeny, ktoré vyzerajú kozmeticky, ich môžu zlomiť. Sada rpr_explain overuje tri veci:
- NFA čítače sa objavujú na správnom mieste — štatistiky na WindowAgg (peak/total/merged states, peak/total/pruned contexts, dĺžkové histogramy pre matched/mismatched/absorbed/skipped) sa zobrazujú pod
EXPLAIN ANALYZEv textovom formáte, JSON aj XML s dokumentovanými označeniami, a Nav Mark Lookback a Lookahead sa objavujú presne vtedy, keď ich napája navigácia v DEFINE. - Vzory sa správne deparsujú — každý tvar kvantifikátora, vrátane neochotných variantov a ohraničených foriem; každá alternácia; každá skupina; každá forma
AFTER MATCH SKIP;INITIAL; navigačné volania s posunmi; zložená navigácia. Deparsovaný text musí prejsť round-trip späť cez parser nezmenený. - Citovanie identifikátorov je správne — premenné vzoru a DEFINE výrazy sú vydávané s tými istými pravidlami citovania ako bežné SQL identifikátory, takže nezvyčajné mená premenných nezlomia výstup
pg_dump.
Ako rpr_base, táto sada zámerne ponecháva svoje objekty na mieste na konci behu, takže pokrytie pg_dump a pg_upgrade sa rozširuje aj na artefakty na strane explain.
4.5 rpr_integration — interakcie plánovača
Plánovač PostgreSQL má mnoho optimalizácií, ktoré pracujú na okenných dotazoch — kanonikalizácia rámca, pushdown run-condition, deduplikácia identických okien, projekcia nepoužitého výstupu, inverzné prechody pohyblivých agregátov — a každá z nich bola navrhnutá bez RPR na mysli. Väčšina z nich nie je bezpečná na uplatnenie, keď okno má klauzulu PATTERN: rámec je súčasťou kontraktu zhody, zhodnutý výstup už nie je monotónny žiadnym zrejmým spôsobom a dve okná s tou istou špec, ale rozdielnymi DEFINE produkujú skutočne rozdielne výsledky. Integračná sada overuje, ako každá z týchto optimalizácií zaobchádza s RPR oknami — väčšina musí byť vypnutá alebo obídená:
- Kanonikalizácia rámca
- Plánovač normálne prepisuje
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGnaROWS UNBOUNDED PRECEDINGpre okenné funkcie nezávislé od rámca, akorow_number,rankantile. Rámec RPR je rozsah zhody, nie agregačné okno, a musí zostať doslovný. - Pushdown run-condition
- Monotónny filter
WHEREna výstupe okennej funkcie môže byť normálne presunutý do okenného operátora ako stop-podmienka. Pre RPR by toto predčasne ukončilo zhodovanie vzoru, možno odrezaním zhôd v polovici rozšírenia. - Deduplikácia okien (RPR vs ne-RPR)
- Dve okná s identickým
ORDER BYa rámcom by boli normálne zlúčené do jedného. RPR okno a ne-RPR okno nikdy nemôžu zdieľať stav, pretože RPR strana nesie výsledky zhody. - Deduplikácia okien (rôzne DEFINE alebo SKIP)
- Dve RPR okná s tým istým
PATTERN, ale rôznymi klauzulamiDEFINEalebo inýmAFTER MATCH SKIP, produkujú rôzne zhody a musia zostať odlišné, aj keď je ich štrukturálny tvar identický. - Projekcia nepoužitého výstupu
- Táto sa uplatniť smie: keď okolitý dotaz nikdy nečíta výstup okna, okenná funkcia sa stane NULL a jej WindowAgg sa odstráni, pričom počet riadkov zostane nezmenený. Testy kontrolujú, že stĺpce, ktoré DEFINE číta, stále dosiahnu WindowAgg, keď zostáva, a že okno je ponechané, keď sa jeho hodnota číta.
- Inverzné prechody pohyblivých agregátov
- Okenné agregáty s inverznou prechodovou funkciou môžu byť normálne vyhodnocované inkrementálne, ako sa rámec posúva. Zredukovaný rámec RPR nie je posuvným oknom; cesta inverzného prechodu by produkovala nesprávne výsledky.
Ďalšie prípady kontrolujú, že odhad nákladov zohľadňuje DEFINE, že poddotaz obsahujúci RPR okno sa nesploští, že výrazy DEFINE neunikajú do vyššieho WindowAgg a že LIMIT zostáva nad WindowAgg; druhá skupina spúšťa RPR spolu s CTE, spojeniami, množinovými operáciami, pripravenými príkazmi, partíciovanými tabuľkami a podobnými konštrukciami. Väčšina strážených prípadov má rovnaký tvar: baseline, ktorý spúšťa optimalizáciu (zvyčajne ne-RPR dotaz, kontrolovaný v EXPLAIN), potom RPR dotaz štrukturálne podobného tvaru, kde optimalizácia nie je aplikovaná — pre prípad deduplikácie DEFINE/SKIP je baseline dvojica identických RPR okien a prípad inverzného prechodu kontroluje obídenie pomocou logovacieho agregátu namiesto EXPLAIN. Obe polovice spolu dokazujú, že strážca v plánovači robí skutočnú prácu, neschvaľuje každý dotaz bez skutočného overenia.
Táto sada je tiež dôvodom, prečo je §3.4 krátky. Mechanizmy „hraníc zhody" — zredukovaný rámec, SKIP, INITIAL, cutoff ohraničeného rámca — sú testované operačne inde; čo rpr_integration overuje, je, že žiadna iná optimizačná etapa s nimi pri prechode nemanipuluje. Prechádzajúce rpr_integration je to, čo umožňuje zvyšku sád dôverovať, že ich vstupy dosahujú vykonávateľa nedotknuté.