Row Pattern Recognition Analiză aprofundată

§1. Standardul, subsetul și întrebările deschise

1.1 Domeniul standardului

Row Pattern Recognition a fost introdus în SQL prin ISO/IEC 9075-2:2016 și este descris în documentul complementar ISO/IEC 19075-5:2021 (Partea 5, „Row Pattern Recognition”).

Standardul definește două suprafețe pentru aceeași mașinărie subiacentă. Caracteristica R010 plasează o clauză MATCH_RECOGNIZE în lista FROM pentru a produce un tabel derivat; caracteristica R020 integrează aceeași logică de tipare într-o specificație WINDOW pentru a produce ieșire de tip funcție-fereastră. Cele două suprafețe împart cea mai mare parte a sintaxei și toată semantica, dar constituie puncte de intrare distincte funcțional — o bază de date poate implementa una sau ambele.

Seria de patch-uri discutată aici implementează un subset al lui R020 exclusiv; forma tabelară este în mod deliberat în afara domeniului.

Suprafața R020 este restrânsă, dar expresivă. O interogare atașează un tipar la o fereastră prin adăugarea a trei clauze în specificația ferestrei: PATTERN descrie o expresie regulată peste variabilele de tipar denumite, DEFINE furnizează predicatul boolean care identifică fiecare variabilă, iar AFTER MATCH SKIP controlează modul în care potrivirile succesive sunt poziționate în cadrul partiției.

Opționalele MEASURES, SUBSET, INITIAL/SEEK și funcția auxiliară CLASSIFIER() completează caracteristica. (Funcția MATCH_NUMBER() din standard aparține exclusiv suprafeței R010 — 19075-5 §6.3.3 (6) o exclude explicit din R020.)

Patch-ul acoperă suficient din acest vocabular pentru a face funcționale interogări netriviale, dar se oprește înainte de mai multe construcții a căror implementare depinde de infrastructură care nu a fost încă construită.

Restul acestei secțiuni partiționează vocabularul standardului în ceea ce patch-ul deja susține și ceea ce lasă în mod intenționat pentru mai târziu. Listele de mai jos reflectă starea curentă a seriei de patch-uri.

1.2 Caracteristici implementate

Vocabularul implementat este suficient pentru a exprima tiparele canonice în formă de V, formă de W și de inversare care motivează în primul rând recunoașterea tiparelor de rânduri. Acoperă, de asemenea, fiecare cuantificator standard — inclusiv toate cele șapte variante reticente *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — și cele patru primitive de navigare de care au nevoie condițiile DEFINE pentru a compara rânduri adiacente.

Clauza PATTERN

Definește tiparul de rânduri în interiorul unei specificații de fereastră.

Regex: + * ? |

Cuantificatori și alternare standard.

Regex: gruparea ( )

Sub-tipare puse între paranteze.

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

Numărări mărginite de repetare.

Reticente *? +? ?? {n}? {n,}? {,m}? {n,m}?

Toate cele șapte variante reticente (non-greedy) definite de standard (excluse din optimizarea de absorbție).

Clauza DEFINE

Condiții booleene care identifică fiecare variabilă de tipar.

Variabilă universală de tipar de rând

Referințele de coloană necalificate în DEFINE (ex.: Price simplu) se rezolvă la rândul curent, conform 19075-5 §4.10/§4.16.

PREV, NEXT (cu deplasament)

Accesează n rânduri înainte/după rândul curent (implicit 1); argumentul interior este o expresie de valoare arbitrară evaluată la rândul navigat.

FIRST, LAST (cu deplasament)

Accesează un rând relativ la potrivire; FIRST(expr, n) țintește rândul aflat n după începutul potrivirii, LAST(expr, n) rândul aflat n înainte de cel mai recent rând al potrivirii.

Navigare compusă (patru forme)

Pasul exterior PREV/NEXT suprapus peste un FIRST/LAST interior: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — atât pasul interior, cât și cel exterior acceptă propriul deplasament.

INITIAL

Potrivirile de tipar trebuie să înceapă la rândul curent (implicit).

AFTER MATCH SKIP PAST LAST ROW

Mod de salt implicit; eligibil pentru absorbția de context.

AFTER MATCH SKIP TO NEXT ROW

Permite potriviri suprapuse; dezactivează absorbția.

1.3 Neimplementate

Caracteristicile rămase neimplementate se împart în trei grupări largi. Prima — și de departe cea mai numeroasă — este familia de construcții centrate pe MEASURES: clauza MEASURES propriu-zisă, SUBSET, CLASSIFIER(), referințele de coloană calificate prin tipar precum B.price, precum și navigarea calificată prin tipar precum LAST(B.price) sau PREV(B.price).

Acestea nu sunt atât lacune independente, cât perspective diferite asupra unei singure piese lipsă: executorul ar trebui să rețină un istoric pe potrivire — o consemnare, pentru fiecare rând al potrivirii, a variabilei de tipar la care a fost mapat — iar niciuna dintre aceste construcții nu are o definiție semnificativă fără el. CLASSIFIER() citește numele variabilei din această consemnare; B.price citește coloana de preț a rândurilor a căror intrare spune B; LAST(B.price) parcurge același set de rânduri și îl alege pe ultimul; SUBSET U = (A, B) definește o variabilă virtuală care agregă peste ambele compartimente; iar MEASURES evaluează expresii precum AVG(U.Price) folosind exact această agregare.

Executorul actual evaluează predicatele DEFINE rând cu rând, dar nu înregistrează nicăieri atribuirile rezultate ale variabilelor — nu există nimic de interogat ulterior. Construirea infrastructurii de istoric este, prin urmare, premisa pentru întregul grup; caracteristicile individuale rezultă ca proiecții mici odată ce consemnările există.

A doua grupare privește țintele alternative de salt: AFTER MATCH SKIP TO etichetă, AFTER MATCH SKIP TO FIRST var și AFTER MATCH SKIP TO LAST var. Acestea depind, de asemenea, de istoricul potrivirii, întrucât executorul trebuie să poată indica un rând etichetat anume în interiorul celei mai recente potriviri.

Elementele rămase formează o coadă eterogenă: cuvântul-cheie SEEK (alternativa la INITIAL), tiparul vid (), forma de excludere {- … -} și operatorul insensibil la ordine PERMUTE.

MEASURES

Expresii de ieșire denumite, pe potrivire, de ex. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; în R020 expusă prin OVER ca o funcție de fereastră. Acceptă cuvintele-cheie FINAL / RUNNING (19075-5 §5.4), care în R020 se reduc la aceeași valoare, întrucât măsurile sunt întotdeauna evaluate pe ultimul rând al potrivirii (19075-5 §6.9 (3)).

SUBSET

Reuniuni denumite de variabile de tipar, de ex. SUBSET U = (A, B, C). Utilizabil oriunde poate fi referită o variabilă de tipar — MEASURES, referințe calificate prin tipar în DEFINE, CLASSIFIER(U) — toate necesitând istoric de potrivire.

CLASSIFIER()

Returnează variabila de tipar la care a fost potrivit un rând dat. Definită atât pentru DEFINE, cât și pentru MEASURES (19075-5 §5.9); răspunsul la orice rând este numele variabilei consemnat în istoricul de potrivire pentru acel rând.

Referință de coloană calificată prin tipar

B.price simplu în DEFINE sau MEASURES — valoarea coloanei din rândul mapat ca variabila denumită.

Navigare calificată prin tipar

Restrânge navigarea la rândurile potrivite ca o variabilă denumită, de ex. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

Potrivirea poate începe oriunde în fereastră (spre deosebire de INITIAL).

AFTER MATCH SKIP TO etichetă

Salt la un rând etichetat.

AFTER MATCH SKIP TO FIRST var

Salt la primul rând potrivit ca variabila denumită.

AFTER MATCH SKIP TO LAST var

Salt la ultimul rând potrivit ca variabila denumită.

Regex: {- -}

Excludere — elimină rândurile potrivite din ieșirea pe potrivire.

Regex: ()

Tipar vid — potrivește secvența vidă.

PERMUTE(...)

Potrivire insensibilă la ordine peste variabilele listate.

Funcții de agregare în DEFINE

Agregările precum SUM, AVG, COUNT nu sunt permise în predicatele DEFINE. Standardul le permite ca agregări curgătoare peste potrivirea parțială (evaluare pe rând împotriva rândurilor deja mapate la o variabilă), ceea ce depinde de același istoric de potrivire pe care îl necesită MEASURES/CLASSIFIER().

Patru aspecte suplimentare merită menționate aici, deoarece pot fi confundate ușor cu omisiuni.

Primul este că ancorele de tipar ^ și $ nu sunt permise cu RPR în clauza WINDOW chiar de către standard (19075-5 §6.13: „ancorele (^ și $) nu sunt permise cu potrivirea de tipare de rânduri în ferestre”; cu definiția subiacentă la 19075-5 §4.14.1); absența lor este conformitate, nu o lacună.

Al doilea este că MATCH_NUMBER() este, de asemenea, exclus din R020 prin standard (19075-5 §6.3.3 (6) și 19075-5 §6.9 (1)) — face parte exclusiv din suprafața R010, iar absența sa aici este, din nou, conformitate, nu o caracteristică lipsă.

Al treilea este un set de interdicții structurale pe care standardul le impune asupra R020 (19075-5 §6.17): recunoașterea tiparelor de rânduri nu poate fi imbricată în interiorul altei recunoașteri de tipare de rânduri; MEASURES și DEFINE nu pot conține referințe externe; subinterogările din interiorul MEASURES sau DEFINE nu pot referi variabile de tipar de rânduri; iar RPR nu poate fi folosit într-o interogare recursivă.

Al patrulea este că MATCH_RECOGNIZE propriu-zis — Caracteristica R010, suprafața de clauză tabelară a aceleiași mașinării — este în afara domeniului acestui patch. Dacă PostgreSQL va adăuga, în cele din urmă, R010 va fi o întrebare pentru o serie viitoare, nu o măsură a acesteia.

§2. Exemple — cum se execută efectiv

Exemplele din această secțiune se construiesc incremental. Pornim de la motivul conceptual pentru care potrivirea de tipare de rânduri este cu adevărat diferită de potrivirea de tipare de text, apoi introducem cele patru funcții de navigare care fac condițiile DEFINE interesante și, în final, parcurgem trei trasee complete: o singură potrivire (mișcarea NFA), absorbția de context în cazul ușor și cazul în care absorbția devine nesigură.

Mecanismul intern care face navigarea ieftină — schimbul de tuplu cu un singur slot — aparține proiectării executorului și este tratat în secțiunea următoare, nu aici.

2.1 De ce tiparele de rânduri diferă de tiparele de text

O expresie regulată de text potrivește un flux de caractere, iar la fiecare poziție există exact un simbol de luat în considerare. Întrebarea de execuție — „simbolul curent este egal cu 'A'?” — are un singur răspuns da/nu. Automatele cu backtracking exploatează acest lucru: cel mult o ramură supraviețuiește per caracter, iar costul ambiguității se plătește prin recitirea intrării.

Un tipar de rânduri este diferit în mod fundamental. Un rând nu este un singur simbol; este un tuplu de coloane evaluat împotriva unui set de predicate booleene, condițiile DEFINE. Două predicate pot fi adevărate simultan la același rând, iar nimic din standard nu spune că trebuie să fie mutual exclusive. Să luăm:

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

Un rând cu price = 150, volume = 2000 satisface atât A, cât și B, dar nu și C. Potrivitorul de tipare nu poate colapsa acest lucru la o singură stare — două variabile de tipar sunt active, iar orice element de tipar care numește oricare dintre ele poate avansa. NFA trebuie, prin urmare, să poarte mai multe stări simultane per rând al partiției, nu una singură.

Această singură observație determină restul arhitecturii. Starea de execuție este o listă de contexte, fiecare context este o listă de stări, iar la fiecare rând execuția întreabă fiecare stare: „date fiind variabilele adevărate aici, unde pot să merg?” Bifurcările rezultate sunt motivul pentru care execuția are nevoie de mai multe straturi de tăiere — deduplicare de stări într-un context, absorbție între contexte și celelalte reguli prezentate în §3.6 — fără de care numărul stărilor și contextelor active crește odată cu partiția, iar potrivirea de tipare devine supra-liniară.

2.2 Funcții de navigare

Condițiile DEFINE care fac referire doar la rândul curent sunt limitate; aproape orice tipar interesant trebuie să compare rândul curent cu vecinii săi sau cu rândurile deja acceptate mai devreme în potrivire. Standardul oferă patru funcții de navigare pentru aceasta, iar patch-ul le implementează pe toate.

PREV(expr [, n])

Rândul aflat n rânduri înaintea rândului curent (implicit n = 1). Folosit pentru comparații „azi vs. ieri”.

NEXT(expr [, n])

Rândul aflat n rânduri după rândul curent. Privire înainte; rar în forma de fereastră, deoarece fereastra este monotonă.

FIRST(expr [, n])

Al n-lea rând potrivit al potrivirii curente, numărând de la început. „Comparație cu rândul care a început această potrivire.”

LAST(expr [, n])

Al n-lea cel mai recent rând potrivit. „Comparație cu cel mai recent rând potrivit.”

Cele patru primitive se compun: PREV și NEXT pot încadra un apel FIRST sau LAST, dând patru forme compuse a căror semantică este „mergi la un rând relativ la potrivire, apoi fă un pas la o distanță fixă față de el”. Acesta este lucrul care permite unei expresii DEFINE să citească, de exemplu, rândul imediat anterior începerii potrivirii.

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

Fă m rânduri înapoi de la al n-lea rând al potrivirii (implicit m = 1). „Care a fost valoarea chiar înainte de începerea acestei potriviri?”

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

Fă m rânduri înainte de la al n-lea rând al potrivirii. Ajunge mai departe în potrivire fără a depinde de rândul curent.

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

Fă m rânduri înapoi de la al n-lea cel mai recent rând potrivit. „Comparație cu un rând puțin înaintea ultimei potriviri.”

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

Fă m rânduri înainte de la al n-lea cel mai recent rând potrivit.

Două puncte practice merită menționate aici. În primul rând, navigarea poate fi compusă: PREV(FIRST(price)) citește rândul imediat anterior începerii potrivirii, iar patch-ul susține acest lucru. În al doilea rând, navigarea are consecințe pentru optimizările executorului. PREV și NEXT sunt relative la rândul curent și sunt întotdeauna sigure; FIRST și variantele cu deplasament ale lui LAST sunt relative la limitele potrivirii, ceea ce interacționează cu absorbția de context și obligă planificatorul să mențină active anumite contexte pe care altminteri le-ar elimina. Mecanismul din spatele acestei interacțiuni este subiectul §2.6.

2.3 Exemplu rezolvat 1 — mișcarea NFA

SELECT company, tdate, price,
  first_value(price) OVER w AS start_price,
  last_value(price)  OVER w AS end_price
FROM stock
WINDOW w AS (
  PARTITION BY company ORDER BY tdate
  ROWS BETWEEN CURRENT ROW
       AND UNBOUNDED FOLLOWING
  AFTER MATCH SKIP PAST LAST ROW
  PATTERN (START UP+ DOWN+)
  DEFINE
    UP   AS price > PREV(price),
    DOWN AS price < PREV(price)
);

Tiparul se aplatizează la patru elemente:

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

Pentru seria de prețuri 100, 110, 120, 115, 108, 130:

Punctul-cheie: la rândul 3, rândul satisface atât START (mereu adevărat), cât și DOWN, dar singura stare care a supraviețuit rândului 2 este pe ramura de ieșire DOWN, așa că se ia doar tranziția UP → DOWN. Natura multi-stare din §2.1 este vizibilă ca evantai la fiecare potrivire UP (starea ar putea rămâne la UP+ sau avansa către DOWN+). Preferința greedy este „buclează din nou înainte de ieșire”, așa că, sub suficiente date, ramurile care buclează ar extinde potrivirea mai mult; aici DOWN-ul care buclează moare la rândul 5 (130 ≮ 108), iar candidatul FIN anterior (rândurile 0–4) — produs când DOWN a ieșit la rândul 4 — este finalizat ca potrivirea.

Rezultatul interogării decurge direct din acest traseu. Sub semantica RPR, funcțiile de fereastră first_value(price) și last_value(price) sunt evaluate doar la rândul care a început potrivirea — orice alt rând al potrivirii produce NULL pentru aceste funcții de fereastră, deoarece cadrul său redus este vid. Ieșirea pentru datele noastre arată, prin urmare, ca tabelul afișat în panoul din dreapta sus al posterului:

Rândul 0 este începutul potrivirii, deci cadrul său acoperă rândurile 0–4, iar funcțiile de fereastră raportează prețul de deschidere al formei de V ($100) și prețul de jos ($108). Rândurile 1–4 sunt în interiorul potrivirii, dar nu sunt începutul ei, așa că primesc NULL. Rândul 5 (preț $130) se află în afara oricărei potriviri și primește, de asemenea, NULL.

2.4 Exemplu rezolvat 2 — alternare și ordine lexicală

Forma (A | B) oferă potrivitorului o alegere: la orice rând, cele două alternative sunt testate independent, iar oricâte dintre ele se pot potrivi. Aici natura multi-stare din §2.1 devine vizibilă în interiorul unui singur context — nu între contexte (asta este absorbție), ci de-a lungul ramurilor paralele pe care executorul le explorează în pas.

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

Imaginați-vă un rând în care prețul a și crescut și a depășit $100 — atât UP, cât și HIGH sunt adevărate. Fiecare alternativă naște propria stare: una mergând pe ramura UP, una pe ramura HIGH. Acestea avansează în paralel până când DONE le rezolvă.

Ambele ramuri produc o potrivire de aceeași lungime peste aceleași rânduri, lăsând potrivitorul cu două căi candidate — una etichetată UP, DONE și una etichetată HIGH, DONE. Standardul rezolvă acest lucru prin ordinea lexicală: dintre alternativele scrise în (UP | HIGH), câștigă cea scrisă prima, indiferent de lungimea potrivirii. Deoarece UP apare înaintea lui HIGH, calea supraviețuitoare este UP, DONE.

Ordinea lexicală este ceea ce face CLASSIFIER() bine definit când va fi în cele din urmă implementat — îi permite execuției să spună utilizatorului „acest rând s-a potrivit cu UP, nu cu HIGH” chiar și când ambele predicate erau adevărate. Ordinea lexicală este regula principală pentru alternare: o ramură lex-anterioară câștigă în fața uneia lex-ulterioare chiar dacă cea lex-ulterioară ar produce o potrivire mai lungă, iar o ramură lex-ulterioară (posibil mai scurtă) poate totuși câștiga dacă fiecare ramură lex-anterioară moare înainte de a ajunge la FIN. Lungimea greedy este decisă în interiorul unui singur cuantificator — date fiind două completări ale aceleiași ramuri de alternare, cuantificatorul greedy preferă mai multe iterații.

2.5 Exemplu rezolvat 3 — absorbție de context (aceeași soartă)

Cel mai simplu tipar care exhibă absorbție este PATTERN (A+) cu DEFINE A AS TRUE. Fiecare rând se potrivește cu A, iar standardul impune ca potrivitorul să considere fiecare rând drept un posibil început de potrivire. Naiv, acest lucru înseamnă N contexte pentru o partiție de N rânduri. Să luăm o partiție de cinci rânduri (orice date — predicatul este constant adevărat):

Memoria crește de la O(n) la O(1). Regula de absorbție care justifică eliminarea este directă când cuantificatorul este nemărginit:

Panoul stâng inferior al posterului („① Absorbție de context”) este exact această regulă vizualizată peste cinci rânduri.

Un punct subtil, dar important, se ascunde în regulă: eliminarea este sigură deoarece predicatul A AS TRUE se evaluează la aceeași valoare la fiecare rând, indiferent care context întreabă. Același lucru este adevărat pentru orice predicat care face referire doar la rândul curent sau la un deplasament fix față de el — inclusiv PREV. Următorul exemplu trece la o săptămână concretă de prețuri, folosind un predicat bazat pe PREV, iar §2.6 va reutiliza exact acea săptămână pentru a face evidentă simetria dintre absorbția sigură și cea nesigură:

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

Să luăm săptămâna de tranzacționare $100, $108, $112, $116, $110 de luni până vineri — patru creșteri urmate de o scădere bruscă. Să presupunem că C1 începe marți (prima zi în care RISE se potrivește: $108 > $100), iar executorul urmărește speculativ și C2 începând miercuri. Condiția RISE a fiecărui rând compară prețul rândului cu predecesorul său imediat — un fapt la nivel de partiție, nu la nivel de context — astfel încât cele două contexte sunt forțate să calculeze același boolean la fiecare rând pe care îl împart:

Povestea se rupe în clipa în care predicatul începe să depindă de limitele proprii ale fiecărui context — iar despre asta este vorba în §2.6.

2.6 Exemplu rezolvat 4 — când absorbția devine nesigură

Să presupunem că un analist dorește să găsească zile de tranzacționare consecutive în care o acțiune a rămas în interval de zece dolari față de ziua în care a început rularea — un fel de fereastră de consolidare. Tiparul și DEFINE arată astfel:

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

Condiția compară acum prețul rândului curent cu prețul de la începutul rulării curente. Două rulări care au început în zile diferite au valori FIRST(price) diferite, astfel încât două stări la același element de tipar și același contor nu mai sunt interschimbabile: viitoarele lor depind de limita pe care absorbția era pe punctul de a o elimina.

Să luăm exact aceeași săptămână de tranzacționare ca în §2.5 — $100, $108, $112, $116, $110 de luni până vineri. Execuția menține din nou două rulări candidate active simultan: C1 a început luni, C2 a început marți (fiecare rând este un potențial început de rulare sub STABLE+).

Sub absorbție, C2 ar fi fost contopit în C1 marți — contextul contopit păstrează doar un singur plafon, astfel încât perspectiva distinctă a lui C2 (plafon $118, rularea de patru zile care se termină abia sâmbătă) nu mai este recuperabilă din starea internă. C2 trebuie să rămână activ deoarece este un candidat independent de potrivire de care execuția poate avea încă nevoie: odată ce potrivirea lui C1 se termină miercuri, următoarea încercare trebuie să continue de la un C2 încă în rulare, în loc să înceapă de la zero. Ori de câte ori un predicat DEFINE poartă dependență de începutul potrivirii, planificatorul dezactivează preemptiv absorbția.

(Când potrivirea contextului conducător reușește efectiv, contextele care au început în interiorul intervalului său acceptat — sub AFTER MATCH SKIP PAST LAST ROW implicit — sunt pur și simplu eliminate; sunt menținute active doar pentru ca execuția să aibă unde să se retragă dacă potrivirea conducătoare eșuează.)

Tabelul de dependențe din panoul dreapta jos al posterului („② Navigare”) rezumă care forme de navigare creează dependență de începutul potrivirii:

Cele două exemple din §2.5 și §2.6 se reduc la o singură regulă. Aceeași soartă este ceea ce face absorbția sigură: dacă fiecare context la același element de tipar va calcula același răspuns pentru fiecare predicat viitor, trebuie păstrat doar cel mai vechi. Sortile diferite fac absorbția nesigură: imediat ce predicatele se ramifică pe starea privată a contextului — ceea ce fac exact FIRST și LAST cu deplasament — fiecare context activ reprezintă un viitor pe care niciun alt context nu îl poate recupera, iar eliminarea oricăruia dintre ele riscă să producă un răspuns greșit.

Planificatorul detectează această distincție la momentul compilării și decide per context dacă absorbția se aplică. Acesta este și motivul pentru care benchmark-ul posterului din panoul ③ rămâne liniar atât în cazurile de succes, cât și în cele de eșec: când absorbția este sigură, execuția colapsează contextele, iar când nu este, planificatorul acceptă costul multi-context în loc să riște un răspuns greșit.

Cifrele din benchmark de pe poster sunt același algoritm desfășurat la scară. Pe tiparul de succes (A+ B+ C+ D), atât PostgreSQL, cât și Trino scalează O(n) odată ce o potrivire este confirmată, iar avansul PostgreSQL — aproximativ 16× până la 33× — este în mare parte decalajul JVM.

Pe tiparul de eșec (A+ B+ C+ E), Trino nu are absorbție și se degradează la O(n²) urmărind fiecare potențial început de potrivire; la 100.000 de rânduri durează peste cinci ore, în timp ce PostgreSQL termină în 92 ms, o accelerare de aproximativ 217.000×.

Acest decalaj nu este finisaj inginerresc — este exact distincția aceeași-soartă / sortile-diferite din §2.5 și §2.6, aplicată fiecărui rând al fiecărui potențial început de potrivire din partiție.

2.7 Exemplu rezolvat 5 — când SKIP dezactivează absorbția

Exemplul anterior a rupt absorbția din partea datelor: FIRST în DEFINE a făcut ca fiecare context să evalueze predicate în mod diferit. Absorbția se poate rupe și din partea ieșirii, iar clauza AFTER MATCH SKIP este cea care controlează acest lucru.

Să luăm tiparul PATTERN (A+) cu DEFINE A AS TRUE peste cinci rânduri care se potrivesc toate cu A. Sub implicitul AFTER MATCH SKIP PAST LAST ROW, potrivitorul găsește cea mai lungă potrivire începând cu cel mai timpuriu rând și apoi sare peste ea; orice context care a început în interiorul acelei potriviri este eliminat implicit ca redundant — exact situația pentru care este proiectată absorbția. Ieșirea este o singură potrivire, rândurile 0–4, iar execuția are nevoie de un singur context activ.

Schimbați modul de salt la AFTER MATCH SKIP TO NEXT ROW și contractul se schimbă:

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

Acum, fiecare poziție potențială de început trebuie raportată separat, chiar și când potrivirile se suprapun. Pentru aceleași cinci rânduri, execuția este obligată să emită cinci potriviri: rândurile 0–4, 1–4, 2–4, 3–4 și 4–4. Niciuna dintre acestea nu poate fi înlocuită de „una mai lungă începând mai devreme”, deoarece standardul spune că utilizatorul le dorește pe toate.

Observați că predicatul nu s-a schimbat. A AS TRUE se evaluează la fel la fiecare rând, indiferent care context întreabă, așa că condiția aceleiași sortire din §2.5 este încă îndeplinită. Ce se schimbă este cerința de ieșire: chiar și contextele cu viitoare identice trebuie să coexiste, deoarece corespund unor rânduri distincte ale rezultatului. Prin urmare, planificatorul dezactivează absorbția de context ori de câte ori AFTER MATCH SKIP TO NEXT ROW este în vigoare, indiferent de clauza DEFINE.

Punând §2.6 și §2.7 alături, obținem imaginea completă a momentului în care absorbția eșuează:

Oricare dintre condiții este suficientă pentru a dezactiva absorbția pentru contextele afectate. Când niciuna nu este în vigoare — implicitul AFTER MATCH SKIP PAST LAST ROW cu condiții DEFINE care folosesc doar PREV, NEXT sau LAST simplu — execuția se reduce la un singur context per poziție de tipar și rămâne liniară până la capăt.

§3. Proiectare — de la parser la executor

Row Pattern Recognition este implementat ca trei etape care își transmit munca prin forme intermediare bine definite. Parserul transformă textul SQL într-un arbore de tipare și o listă de predicate DEFINE; planificatorul compilează arborele într-un tablou plat de elemente de tipar și decide care dintre ele pot participa la absorbția de context; executorul rulează tabloul împotriva partiției rând cu rând într-o buclă în trei faze. Fiecare etapă are propria sa formă de date, iar cea mai mare parte a ingeniozității de proiectare se află la limite: un NFA plat care încape în cache, un model de navigare care refolosește un singur slot de tuplu în loc să materializeze unul per referință și o regulă de absorbție care transformă memoria O(n²) în O(n).

text SQL
  │
  │  etapa parser
  ▼    validează cadrul
       construiește arborele de tipare
       verifică tipurile DEFINE

arbore de tipare + listă DEFINE
  │
  │  etapa planificator
  ▼    optimizează arborele
       compilează în tablou NFA plat
       decide absorbabilitatea

NFA plat + indicatori de absorbție
  │
  │  etapa executor
  ▼    motor pe rând:
       Match → Absorb → Advance

rezultatul potrivirii:
  rând de start, lungime, succes/eșec

Secțiunile de mai jos parcurg acest flux. §3.1 acoperă parserul și forma arborelui de tipare; §3.2 acoperă compilarea care transformă arborele în NFA plat; §3.3 acoperă modelul de navigare pe care îl folosesc predicatele DEFINE pentru a se uita la rândurile vecine; §3.4 acoperă tratarea limitelor potrivirii — regulile SKIP, INITIAL și de cadru mărginit care fixează unde începe și se termină o potrivire; §3.5 este motorul pe rând în trei faze; §3.6 adună toate mecanismele de tăiere care mențin spațiul de stări mărginit; iar §3.7 trece în revistă ceea ce expune implementarea în ieșirea EXPLAIN.

3.1 Parser — construirea arborelui de tipare

Parserul recunoaște recunoașterea de tipare prin prezența unei clauze PATTERN în interiorul unei specificații de fereastră. Prima sa sarcină este validarea cadrului, deoarece RPR impune constrângeri pe care interogările obișnuite de fereastră nu le impun: modul cadrului trebuie să fie ROWS (nu RANGE sau GROUPS), limita de început trebuie să fie CURRENT ROW, iar opțiunile EXCLUDE sunt interzise. Acestea sunt verificări de conformitate, nu optimizări — noțiunea de cadru a RPR este intervalul potrivirii, iar standardul nu prevede umplerea sa cu nimic altceva decât rândurile potrivite.

Odată ce cadrul trece de validare, parserul transformă clauza PATTERN într-un arbore construit din patru tipuri de noduri — o referință de variabilă, o secvență (concatenare), o alternare și un grup (sub-tipar pus între paranteze). Fiecare nod poartă cuantificatorul ca trei numere — o limită inferioară, o limită superioară (posibil infinită) și un indicator pentru potrivirea reticentă:

Fiecare predicat DEFINE este apoi verificat de tipuri împotriva coloanelor partiției și constrâns la o expresie booleană. Două lucruri practice se întâmplă ca parte a acestui proces. În primul rând, fiecare coloană referită de un predicat DEFINE este înregistrată ca parte a cerințelor de ieșire ale interogării, astfel încât planificatorul propagă acele coloane mai departe către etapa de executor, chiar dacă interogarea înconjurătoare nu le selectează — fără asta, execuția nu ar avea nimic împotriva căruia să evalueze. În al doilea rând, variabilele care apar în PATTERN, dar niciodată în DEFINE, sunt implicit adevărate: se potrivesc cu fiecare rând.

3.2 Compilare — de la AST la NFA plat

Planificatorul transformă arborele parserului în structura de date pe care o va rula executorul: un tablou plat de elemente de tipar adresate prin index. Compilarea se desfășoară ca o conductă în șase pași:

compile(astTree):
  1. optimizează AST-ul
  2. măsoară dimensiunea și adâncimea
  3. alocă tabloul de elemente
  4. completează din AST
       (atribuie pointerii next/jump)
  5. finalizează — instalează santinela FIN
  6. marchează elementele eligibile pentru absorbție

Forma plată este aleasă dintr-un motiv simplu: executorul trebuie să traverseze tiparul de multe ori per partiție, iar un tablou contiguu, adresabil prin index, este structura de date cea mai ieftină de parcurs. Pașii 1 și 6 sunt cei interesanți — pasul 1 deoarece determină dimensiunea tabloului, iar pasul 6 deoarece decide dacă optimizarea de absorbție din §2.5 se va activa deloc.

Optimizarea AST

Optimizarea aduce beneficii de două ori: o dată în numărul static de elemente al tabloului plat și din nou în fiecare rând procesat la runtime. Fiecare transformare reduce spațiul de stări pe care execuția trebuie să îl enumere. Optimizatorul aplică opt reguli de rescriere în succesiune până când AST-ul încetează să se schimbe:

Aplatizare SEQ

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

Contopirea variabilelor consecutive

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

Contopirea grupurilor consecutive

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

Contopirea ALT consecutive

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

Absorbția prefixului/sufixului

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

Aplatizare ALT și dedup

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

Înmulțirea cuantificatorilor

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

Despachetare cu un singur copil

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

Înmulțirea cuantificatorilor este singura transformare care necesită o verificare de siguranță: optimizatorul colapsează doar în trei cazuri sigure — ambii cuantificatori nemărginiți ((A+)+ → A+), exterior exact ((A{2,3}){5} → A{10,15}) sau copilul trivial {1,1} ((A){2,5} → A{2,5}). Alte combinații pot introduce goluri pe care forma plată le-ar pierde — de ex., (A{2}){2,3} acceptă doar {4, 6}, dar un A{4,6} naiv ar accepta și 5 — așa că optimizatorul le lasă intacte.

Forma elementului

Fiecare element al tabloului plat reprezintă o singură poziție în tipar. Există cinci tipuri logice: o referință de variabilă (singurul tip care consumă un rând); marcatoare de început de grup și sfârșit de grup, care deschid și închid un sub-tipar pus între paranteze; un marcator de alternare, care conduce o listă de ramuri; și un marcator de încheiere la sfârșitul tiparului.

Fiecare element poartă, de asemenea, o adâncime (nivelul său de imbricare în grup), cuantificatorul (un contor min și max de repetare, posibil infinit) și doi pointeri de tranziție — next, „unde să mergem după ce consumăm acest element”, și jump, „unde să sărim” (folosit de alternare pentru a înlănțui ramuri, de începutul de grup pentru a ocoli corpul când cuantificatorul permite zero și de sfârșitul de grup pentru a bucla înapoi la corp).

Pentru PATTERN ((A B)+) tabloul compilat arată astfel:

PATTERN ((A B)+) se compilează la:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (deschide grupul; jump sare
     la FIN când min = 0)

[1] A      depth 1  quant 1..1
    next → 2

[2] B      depth 1  quant 1..1
    next → 3

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (închide grupul; jump buclează înapoi)

[4] FIN    tipar complet

Tiparul se citește de la stânga la dreapta prin next, cu jump tratând muchiile non-liniare. La idx 3, jump-ul lui END trimite înapoi la idx 1, prin care buclează cuantificatorul exterior nemărginit; la idx 0, jump-ul lui BEGIN ar sări peste END la idx 4 dacă grupul ar fi opțional. Execuția nu trebuie să construiască vreodată un graf la runtime — pur și simplu urmează acești doi pointeri în timp ce parcurge tabloul.

Atribute per element

Dincolo de formă, fiecare element poartă patru atribute logice care direcționează comportamentul execuției în acea poziție:

Reticent

Inversează ordinea expansiunii cuantificatorului. Cuantificatorii greedy încearcă „buclează din nou” înainte de „ieșire”; cei reticenți încearcă mai întâi „ieșirea”. Purtat de variabilă pentru A+?; purtat de BEGIN și END ale grupului pentru ((…)+?).

Buclabil-vid

Setat pe sfârșiturile de grup al căror corp este nullable ((A?)*, (A? B?)+, (A | B*)). Spune execuției să adauge o ieșire de avans rapid alături de bucla normală înapoi, astfel încât garda de ciclu să nu omoare potriviri legitime în grupuri care pot produce iterații vide.

În-regiune-absorbabilă

Marchează fiecare element care se află în interiorul unei regiuni eligibile pentru absorbție — folosit de execuție pentru a urmări dacă starea curentă este încă în teritoriu sigur.

Punct-de-comparație-pentru-absorbție

Marchează elementul specific unde ar trebui să ruleze comparațiile de absorbție. Pentru un simplu A+, aterizează pe variabilă; pentru un grup nemărginit precum (A B)+, aterizează doar pe sfârșitul grupului.

Separarea dintre „în-regiune” și „punct-de-comparație” contează deoarece absorbția are sens doar în punctele în care iterațiile se închid. În interiorul corpului (A B)+, execuția este la mijlocul unei iterații, iar contorul nu a atins încă valoarea finală pentru acea rundă; compararea aici ar însemna compararea de valori incomparabile. Starea trebuie să ajungă la sfârșitul grupului înainte ca execuția să poată decide. Primul atribut spune, prin urmare, „ești încă în teritoriu absorbabil”; al doilea spune „ai ajuns la punctul de comparație — verifică acum”.

Analiza absorbabilității

Pasul 6 al compilării este cel care îi oferă regulii „aceeași soartă” din §2.5 martorul său la momentul compilării. Decizia este pe straturi:

isAbsorbable(query):
  dacă modul SKIP != SKIP PAST LAST ROW
      → return false
  dacă sfârșit frame != UNBOUNDED FOLLOWING
      → return false
  dacă vreun DEFINE depinde de match_start
      → return false
  parcurge AST-ul și marchează
  elementele care satisfac
  un caz structural

Primele trei verificări sunt la nivel de interogare: corespund exact condițiilor §2.7 (partea de ieșire: modul SKIP), cadru mărginit (limita rupe monotonicitatea) și §2.6 (partea de date: FIRST sau LAST cu deplasament în DEFINE). Când oricare dintre ele eșuează, analiza nu setează niciun indicator și absorbția este dezactivată la nivel de interogare. Când toate trec, parcurgerea AST-ului admite trei forme structurale:

Cazul 1 — Variabilă nemărginită simplă

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

Fiecare iterație este exact un rând. Contorul unui context anterior este întotdeauna ≥ cu cel al unui context ulterior la fiecare poziție comună.

Cazul 2 — Grup de lungime fixă, exterior nemărginit

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

Fiecare copil are min == max, deci corpul este semantic echivalent cu forma sa desfăcută {1,1} — (A B{2})+ se comportă ca (A B B)+. Fiecare iterație consumă un număr fix de rânduri; dominanța contorului încă se menține.

Cazul 3 — Grup al cărui corp începe cu o variabilă nemărginită

(A+ B)+

Variabila nemărginită care conduce este ea însăși absorbabilă (Cazul 1) și protejează contextele anterioare. Absorbția se oprește imediat ce starea trece dincolo de A — restul corpului nu are nicio garanție de monotonicitate, așa că indicatorii sunt setați doar pe A.

Cazurile structurale neacoperite de aceste trei forme sunt la fel de instructive. A B+ nu poate fi absorbit de regula curentă deoarece A care conduce consumă un rând înainte de începerea părții nemărginite, astfel încât contextele care încep la un rând diferență se află în poziții diferite în interiorul corpului nemărginit. (O extensie ulterioară de „absorbție de PREFIX” care tratează prefixele de lungime fixă printr-o cale-umbră a fost proiectată și este planificată pentru un patch separat.) Cuantificatorii reticenți precum A+? sunt excluși prin construcție: regula de absorbție presupune semantica greedy, în care potrivirile mai lungi le subsumează pe cele mai scurte, iar potrivirea reticentă inversează acea direcție.

Rezultatul este o decizie per element, nu una per tipar. Un singur plan de interogare poate avea absorbția activată pentru A+ care conduce tipare precum (A+ B+ C) sau (A+ B+)+ — cea din urmă este doar Cazul 3 aplicat elementului său conducător — și dezactivată pentru tot ce urmează; execuția pur și simplu consultă atributul punct-de-comparație al elementului stării curente de fiecare dată când consideră o trecere de absorbție. Odată ce o stare se mută într-o regiune ne-absorbabilă, absorbția este oprită permanent pentru acea stare — exact ceea ce trebuie să fie adevărat la nivel algoritmic în §2.5 și §2.6.

3.3 Navigare — schimbul de tuplu cu un singur slot

Expresiile DEFINE sunt expresii SQL obișnuite evaluate împotriva unui rând, dar pot include PREV, NEXT, FIRST sau LAST — referințe care indică rânduri diferite. Rândurile în sine sunt deja stocate în tuplestore-ul ferestrei; ceea ce trebuie să mai gestioneze executorul este slotul de tuplu de la care citește mașinăria de expresii SQL, întrucât referințele de coloană din interiorul expresiei sunt legate de un slot la momentul planificării. Implementarea refolosește un singur slot de navigare pentru fiecare apel de navigare: slotul este schimbat înainte de evaluarea expresiei interioare și restaurat după, astfel încât restul mașinăriei de expresii SQL nu observă niciodată diferența.

Modelul pe care îl vede executorul este restrâns: există un slot de rând curent care deține rândul împotriva căruia se evaluează expresia DEFINE și un slot de navigare pe care execuția îl poate redirecționa temporar către un rând diferit. În jurul oricărui apel de navigare, execuția configurează slotul de navigare, evaluează expresia interioară ca și cum ar citi rândul curent, apoi restaurează rândul original. Pseudocod:

eval_navigation(call):
  targetPos = compute_target_position(call)
  dacă targetPos este în afara intervalului valid:
      return NULL

  salvează current_row_slot
  preia rândul de la targetPos
    în current_row_slot
  result = eval_inner_expression()
  restaurează current_row_slot
  return result

Trucul este că există exact un singur slot de salvat și restaurat. Expresia interioară — oricare ar fi, inclusiv aritmetică, apeluri de funcții sau alte referințe de coloană — rulează împotriva slotului schimbat folosind aceeași cale de evaluare ca pentru rândul curent. Niciun evaluator alternativ, niciun slot-umbră, nicio copie de tuplu.

Navigarea compusă este aplatizată la momentul analizei astfel încât schimbul să aibă loc tot o singură dată. PREV(FIRST(price)) este recunoscut ca o navigare în doi pași — „mergi la primul rând potrivit, apoi fă un pas înapoi cu un rând” — și stocat ca un singur apel de navigare cu un tip compus. Execuția calculează poziția țintă în două etape, dar efectuează un singur schimb de slot pentru a aduce rândul final:

compute_target_position(call):

  # relativ la rândul curent
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # relativ la potrivire
  FIRST(n):
      return matchStart + n
  LAST(n):
      return lastMatchedRow − n

  # compus: relativ la potrivire, apoi pas
  PREV(FIRST(n), m):
      return (matchStart + n) − m
  NEXT(FIRST(n), m):
      return (matchStart + n) + m
  PREV(LAST(n), m):
      return (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      return (lastMatchedRow − n) + m

  validează în raport cu intervalul potrivit
  (interval de potrivire pentru FIRST/LAST interior,
   interval de partiție pentru pasul exterior)

Un cache de poziție scurtcircuitează preluarea din tuplestore când mai multe apeluri de navigare din același DEFINE țintesc același rând — frecvent în expresii precum price > PREV(price) AND volume > PREV(volume) unde ambele apeluri se rezolvă la rândul anterior. Cache-ul stochează doar „ultima poziție preluată”, iar schimbul în sine rămâne o singură operație.

Clasificarea apelurilor de navigare este contribuția planificatorului la decizia de absorbție. Planificatorul parcurge fiecare expresie DEFINE și sortează fiecare variabilă într-unul din două coșuri, în funcție de dacă toate contextele vor calcula același boolean la același rând sau fiecare context va calcula propriul său. Coșul determină două lucruri la runtime: cât de des este evaluată variabila (o dată partajat sau o dată per context afectat — §3.5 Faza 1) și dacă starea înconjurătoare este eligibilă pentru absorbția de context (§2.5 vs §2.6).

Clasificarea este efectuată la momentul planificării și stocată alături de fiecare variabilă DEFINE, astfel încât execuția nu pierde timp decizând — pur și simplu citește coșul pentru fiecare variabilă pe măsură ce procesează un rând.

Bugetul de reținere

Navigarea ajunge la rânduri pe care mașinăria funcțiilor de fereastră le-a transmis deja mai departe. Pentru a menține acele rânduri disponibile, executorul este construit deasupra unui tuplestore care reține o fereastră glisantă de rânduri recente; întrebarea este cât de lată trebuie să fie acea fereastră. Patch-ul decide la momentul compilării, pornind de la două deplasamente complementare:

Bugetul de privire înapoi (lookback)

Cât de departe înapoi de la rândul curent ar putea ajunge orice apel DEFINE.

Contribuitori: PREV, LAST cu deplasament, PREV(LAST(...)), NEXT(LAST(...))

Bugetul de privire înainte de la start (lookahead-from-start)

Cât de departe înainte (sau înapoi, când este negativ) de la începutul potrivirii celui mai vechi context activ ar putea ajunge orice apel DEFINE.

Contribuitori: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

La runtime, marca de tăiere a tuplestore-ului este setată la cea mai timpurie dintre două poziții — rândul curent minus bugetul lookback și începutul potrivirii celui mai vechi context activ plus bugetul lookahead. Orice se află înaintea acelei mărci nu poate fi atins de niciun apel de navigare în niciun context activ, iar tuplestore-ul este liber să o elimine. Cele două contoare Nav Mark raportate de EXPLAIN (§3.7) — Lookback și Lookahead — sunt vârfurile măsurate ale celor două bugete, cea mai mare adâncime la care a trebuit vreodată să ajungă executorul în oricare direcție pe parcursul interogării.

3.4 Limitele potrivirii — SKIP, INITIAL și cadru mărginit

O potrivire reușită este înregistrată ca un mic pachet de valori: un indicator de validitate, un indicator de succes/eșec, rândul la care începe potrivirea și numărul de rânduri consumate. Când indicatorul de validitate este setat, interogările ulterioare împotriva executorului — „este acest rând în interiorul unei potriviri?” — pot răspunde în O(1) prin inspectarea pachetului. O lungime de zero este un rezultat real, nu o eroare: reprezintă un tipar care s-a potrivit fără a consuma niciun rând, ceea ce executorul trebuie să distingă de „nicio potrivire nu a fost încercată încă în această poziție”.

Clauza AFTER MATCH SKIP decide unde începe următoarea încercare de potrivire. AFTER MATCH SKIP PAST LAST ROW se mută la rândul de după sfârșitul potrivirii, producând ieșirea fără suprapunere pe care o doresc majoritatea interogărilor și permițând optimizarea de absorbție.

AFTER MATCH SKIP TO NEXT ROW se mută doar la rândul de după începutul potrivirii, permițând potriviri suprapuse; planificatorul dezactivează, prin urmare, absorbția pentru întregul plan de interogare când acest mod este în vigoare.

Cele două ținte de salt definite și de standard — AFTER MATCH SKIP TO FIRST var și AFTER MATCH SKIP TO LAST var — depind de istoricul pe potrivire pe care acest patch nu îl reține. Nu sunt prezente deloc în gramatică, așa că parserul ridică o eroare de sintaxă generică dacă oricare este furnizată.

Același lucru este valabil pentru SEEK, alternativa specificației la INITIAL. Sub SEEK, o încercare de potrivire începând la rândul R poate reuși la orice rând de la R până la sfârșitul cadrului, nu doar la R însuși. Patch-ul implementează doar INITIAL: fiecare potrivire potențială este ancorată la un rând specific. Parserul ridică o eroare dacă se solicită SEEK. Cadrele mărginite primesc propriul tratament — când utilizatorul scrie ROWS BETWEEN CURRENT ROW AND N FOLLOWING în loc de UNBOUNDED FOLLOWING, executorul scurtcircuitează orice context a cărui potrivire a atins limita prin forțarea unei nepotriviri, iar absorbția este dezactivată deoarece limita rupe presupunerea de monotonicitate pe care se bazează absorbția.

3.5 Motorul în trei faze, pe rând

Driverul pe rând al executorului este invocat de mașinăria înconjurătoare a funcțiilor de fereastră ori de câte ori trebuie să știe dacă un rând dat aparține unui cadru potrivit. Driverul găsește sau creează contextul pentru poziția curentă de început, evaluează fiecare predicat DEFINE o dată împotriva rândului curent pentru a produce un tablou boolean per variabilă, apoi împinge NFA-ul înainte cu un rând. Pasul înainte însuși este în trei faze într-o ordine fixă — Match, Absorb, Advance — învelite în aceeași buclă exterioară:

processRow(currentPos):

  # Faza 1 — MATCH (convergență)
  pentru fiecare context:
      dacă contextul depășește cadrul mărginit:
          forțează nepotrivire (finalizează devreme)
          continuă
      dacă matchStartRow diferă de
         poziția de evaluare partajată:
          reevaluează variabilele DEFINE
          dependente de începutul potrivirii (§3.3)
      match(context, varMatched)

  # Faza 2 — ABSORB
  dacă tiparul este absorbabil:
      reîmprospătează indicatorii fiecărui context
      absorb_contexts()

  # Faza 3 — ADVANCE (divergență)
  pentru fiecare context:
      advance(context, currentPos)

Ordinea nu este o alegere stilistică. Match trebuie să ruleze primul, deoarece absorbția compară contoare post-potrivire; rularea lui Absorb înainte de Match ar compara stări care urmează să moară. Advance trebuie să ruleze ultima deoarece este singura fază care creează stări noi — extinde fiecare stare supraviețuitoare prin tranziții epsilon până când fiecare ajunge la o variabilă care așteaptă următorul rând. Rularea lui Absorb după Advance ar însemna compararea succesorilor divergenți, ratând punctul în care stările sunt cel mai curat comparabile.

Faza 1 — Match

Match este o fază de „convergență”: stările fie supraviețuiesc cu un contor incrementat, fie mor. Un punct subtil este că pentru variabilele aflate într-o regiune absorbabilă, Match efectuează, de asemenea, o cantitate mică de progres înainte, astfel încât Absorb să poată compara curat. Condiția de acoperire se declanșează doar la punctul de comparație absorbabil — END-ul grupului nemărginit — astfel încât stările care tocmai au potrivit variabile la mijlocul iterației (precum B în interiorul (A B)+) trebuie aduse până la acel punct de comparație în timpul lui Match; altfel, Absorb nu găsește nimic eligibil de comparat, iar optimizarea nu se angajează niciodată.

match(context, varMatched):
  pentru fiecare stare în context:
      elem = pattern[state.elemIdx]
      dacă elem nu este variabilă:
          continuă   # advance se ocupă

      dacă nu varMatched[elem.varId]:
          elimină starea   # ramură moartă
          continuă

      state.counts[elem.depth] += 1

      # Progres înainte inline pentru ca
      # următoarea fază să poată compara la
      # elementul punct-de-comparație, nu
      # la mijlocul iterației.
      dacă elem este în-regiune, dar nu
         punctul de comparație,
         și a atins contorul max,
         iar elem.next este sfârșit de grup:

          parcurge lanțul END:
            incrementează contorul grupului exterior
            avansează state.elemIdx la END
            continuă cât timp încă în-regiune,
              trebuie să iasă, iar next este END
          (se oprește la punctul de comparație
           sau la un element încă buclabil)

Parcurgerea lanțului END face grupurile imbricate de lungime fixă absorbabile. În ((A B){2})+, când B atinge maximul (B este {1,1}), contorul grupului interior trebuie incrementat; dacă acel contor atinge și el maximul — închizând {2} interior — contorul grupului exterior trebuie, de asemenea, incrementat și așa mai departe, până când starea aterizează pe cel mai exterior punct de absorbție — END-ul grupului exterior nemărginit (+). Efectuarea acestei munci în Match permite lui Absorb să compare împotriva contextelor care și-au consolidat deja contoarele post-iterație.

Faza 2 — Absorb

Trecerea de absorbție parcurge contextele de la cel mai nou (coadă) la cel mai vechi (cap). Pentru fiecare context în desfășurare care este complet absorbabil, scanează înapoi după un context mai vechi în desfășurare care îl acoperă și îl eliberează pe cel mai nou dacă este găsit. Deoarece contextele sunt menținute în ordinea creării, iar fiecare rând creează cel mult un context, „mai nou” și „mai vechi” înseamnă cu adevărat „început mai târziu” și „început mai devreme”.

absorb_contexts():
  pentru ctx de la coadă înapoi:
      dacă ctx este terminat
         sau are vreo stare ne-absorbabilă:
          sări
      pentru older de la ctx.prev înapoi:
          dacă older este terminat
             sau nu are nicio stare absorbabilă:
              sări
          dacă covered(older, ctx):
              free(ctx)
              înregistrează lungimea absorbției
              break

covered(older, newer):
  pentru fiecare stare în newer:
      elem = pattern[state.elemIdx]
      dacă elem nu este punctul de comparație:
          return false
      dacă nicio stare în older cu:
            același elemIdx
            și isAbsorbable
            și older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Două micro-decizii decurg din aceasta. Prima este că verificarea de acoperire respinge imediat dacă vreo stare din contextul mai nou se află oriunde altundeva decât într-un punct de comparație — compararea la puncte care nu sunt de judecată nu ar fi o comparație semnificativă.

A doua este perechea asimetrică de indicatori de pe fiecare context: has-absorbable-state răspunde la „poate acest context să absoarbă unul mai nou?” și este monotonic (poate trece doar de la adevărat la fals pe măsură ce stările mor), în timp ce all-states-absorbable răspunde la „poate fi acest context absorbit?” și este dinamic (revine la adevărat când o stare ne-absorbabilă este eliminată). Ambii indicatori sunt verificați în timp constant înainte ca scanarea de acoperire să înceapă măcar, astfel încât absorbția își plătește costul integral doar pe contextele care au o șansă reală de a fi absorbite.

Faza 3 — Advance

Advance este faza de „divergență”: fiecare stare supraviețuitoare este expandată prin tranziții epsilon până când fiecare ramură ajunge fie la o variabilă care așteaptă următorul rând, fie la santinela FIN. Expandarea este în adâncime, iar ordinea în care sunt parcurse ramurile fraților este ceea ce face ca regula de preferință a standardului să aibă efect — ramura lexical primă este întotdeauna adăugată prima, iar pasul de deduplicare la inserarea stării elimină în liniște adăugirile ulterioare echivalente.

advance(context, currentPos):
  scoate toate stările curente;
  reconstruiește ctx.states de la zero
  pentru fiecare stare în ordine lexicală:
      curăță bitmap-ul elementelor vizitate
      advance_state(state)   # DFS

      # Preferință: odată ce un DFS atinge FIN,
      # stările rămase sunt mai puțin preferate
      # și pot fi eliminate.
      dacă FIN atins și stări rămân:
          eliberează restul
          break

advance_state(state):
  parcurge prin state.elemIdx,
  recurge prin:
    ramurile ALT (în ordine),
    BEGIN (intră în grup; plus o cale
           opțională de salt dacă min = 0),
    END (buclează înapoi / iese / avans rapid —
         vezi mai jos),
    FIN (înregistrează matchEndRow,
         salvează matchedState și taie
         contextele ulterioare din intervalul
         acestui candidat — vezi mai jos),
  oprindu-se la fiecare variabilă întâlnită:
      adaugă starea în ctx.states
      (deduplicând după elemIdx + counts)

Înregistrarea unei stări care a ajuns la FIN face mai mult decât să marcheze pur și simplu candidatul de potrivire. Sub AFTER MATCH SKIP PAST LAST ROW, următoarea potrivire raportabilă trebuie să înceapă strict după cea curentă — astfel încât în momentul în care un candidat este înregistrat, fiecare context ulterior al cărui rând de început cade în intervalul candidatului este tăiat imediat, chiar dacă contextul care a atins FIN poate continua să caute o potrivire mai lungă printr-o retragere greedy.

Tăierea este sigură deoarece, indiferent de modul în care se termină acea căutare (o potrivire mai lungă înlocuiește candidatul sau candidatul rămâne), toate contextele tăiate au început într-un interval pe care următoarea potrivire raportabilă trebuie să-l sară, deci nu ar putea niciodată să producă propria ieșire.

Acesta este unul dintre cei doi pași de tăiere la momentul FIN — celălalt, descris mai devreme în această secțiune ca parte din Advance, elimină stările lexical inferioare din interiorul aceluiași context.

Cea mai delicată logică per element se află în handlerul END. Când contorul de iterare al unui grup este sub limita inferioară, execuția trebuie să bucleze înapoi; când este la sau peste limita superioară, trebuie să iasă; între, ambele opțiuni sunt valide, iar lăcomia cuantificatorului decide pe care să o încerce prima:

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

  if count < elem.min:
      buclează înapoi în corp
      dacă elem este buclabil-vid:
          # corp nullable, vezi §3.2
          de asemenea, clonează o stare
          de avans rapid care iese din grup
          cu contorul satisfăcut
          (salvează potriviri legitime pe
           care garda de ciclu le-ar omorî
           altfel)

  elif count >= elem.max:
      resetează contoarele la această adâncime
      iese prin next
      (END→END: incrementează contorul
       END-ului exterior)

  else:
      # min <= count < max: bifurcă
      construiește o stare de ieșire
      (contoarele la această adâncime resetate)
      dacă greedy:
          mai întâi buclează, apoi iese
          # preferă mai lungul
      else (reticent):
          mai întâi iese
          dacă ieșirea a atins FIN:
              elimină bucla
              # preferă mai scurtul
          else buclează al doilea

Fiecare stare adăugată la un context trece printr-o verificare de deduplicare care compară poziția și contoarele sale cu lista de stări existentă. Deoarece Advance procesează ramurile în ordine DFS, starea din prima ramură a oricărei alternări aterizează prima — iar orice ramură ulterioară care produce aceeași poziție și aceleași contoare este respinsă la inserție. Aceasta este exact ceea ce cere regula ordinii lexicale din §2.4, implementată la baza execuției fără o trecere separată.

Grupuri buclabile-vide

Un caz subtil pe care execuția trebuie să-l dezamorseze este grupul nullable — un grup al cărui corp poate potrivi zero rânduri deoarece fiecare copil al corpului este el însuși opțional. Tipare precum (A?)*, (A? B?)+ și (A | B*) au toate această proprietate: în funcție de date, corpul poate completa o iterație fără a consuma deloc vreun rând. Acest lucru este în principiu acceptabil, dar creează un risc real pentru expandarea epsilon a NFA-ului. Dacă corpul produce o potrivire vidă, elementul END buclează înapoi la BEGIN, corpul produce încă o potrivire vidă, BEGIN buclează la END și așa mai departe. Fără ceva care să-l oprească, DFS-ul lui Advance nu s-ar termina niciodată.

Execuția îl oprește cu un bitmap al elementelor vizitate (un bit per element de tipar), curățat înainte de expandarea DFS a fiecărei stări: imediat ce vreun element este vizitat a doua oară în cadrul aceleiași expandări, acea cale este abandonată. Garda de ciclu este necondiționată și ieftină, dar are un efect secundar — poate, de asemenea, să abandoneze căi care ar trebui să atingă limita inferioară prin iterații vide legitime. Să luăm (A?){2,3} fără ca A să se potrivească nicăieri în fluxul de rânduri:

comportament dorit:
  iter 1: A? potrivește zero rânduri
          → END, count = 1 (sub min)
  iter 2: A? potrivește zero rânduri
          → END, count = 2 (atinge min)
  iese cu o potrivire de lungime zero

ce face garda de ciclu de una singură:
  iter 1: A? sărit → END, count = 1
          → buclează înapoi la BEGIN
  iter 2: BEGIN deja vizitat
          → DFS abandonează
  count nu atinge niciodată min
  → potrivirea eșuează (incorect)

Soluția este decisă la momentul compilării și aplicată la runtime. Ori de câte ori planificatorul vede un grup al cărui corp este nullable, etichetează elementul END al acelui grup ca buclabil-vid. La runtime, când handlerul END este pe punctul de a bucla înapoi pentru că contorul de iterare este încă sub limita inferioară, eticheta de buclă vidă îi spune să cloneze o stare suplimentară de avans rapid alături de calea normală de buclare înapoi:

advance_end (count sub min):

  cale primară:
    buclează înapoi în corp
    (menține ușa deschisă pentru o
     potrivire reală, ne-vidă în
     iterația următoare)

  dacă elem este buclabil-vid:
    cale de avans rapid:
      resetează contorul acestei adâncimi
      iese din grup prin next,
      tratând iterațiile rămase
      necesare ca potriviri vide

Cele două căi joacă roluri complementare. Bucla primară înapoi este cea care prinde cazul în care corpul mai are potriviri reale de produs ulterior — de exemplu, în (A?){2,3} urmat de date în care A se potrivește doar pe rânduri ulterioare, bucla înapoi este ceea ce permite iterațiilor a doua și a treia să găsească potriviri ne-vide. Avansul rapid este cel care prinde cazul în care corpul nu produce niciodată nimic: ocolește garda de ciclu prin ieșirea complet din grup, declarând „restul iterațiilor necesare sunt vide”, și permite potrivirii să reușească cu un corp de lungime zero. Ambele stări sunt adăugate la context; oricare se extinde cu succes câștigă, iar verificarea de deduplicare la momentul inserării previne ca oricare cale să nască mai mult decât partea ei de stări.

Dincolo de garda de ciclu, încă un truc de pornire dezambiguizează rezultatele de zero rânduri chiar la începutul unui context. Pasul de creare a contextului la fiecare rând potențial de început rulează un avans inițial prin tranziții epsilon înainte ca vreun rând să fie consumat, folosind o poziție cu un rând înaintea începutului real. Orice cale care ajunge la santinela FIN doar prin tranziții epsilon — fără a consuma un rând — produce, prin urmare, o poziție de sfârșit mai mică decât poziția de început; acea coordonată cu interval negativ, combinată cu dacă FIN a fost efectiv atins, codifică diferența dintre o potrivire vidă (potrivire de lungime 0 acceptată) și un început nepotrivit, fără a avea nevoie de un indicator separat.

3.6 Cum rămâne mărginit spațiul de stări

Liniaritatea execuției nu este rezultatul unei singure optimizări. Este efectul cumulativ al unui set stratificat de reguli de tăiere, fiecare prinzând o cauză diferită a creșterii spațiului de stări într-un punct diferit al ciclului pe rând. Unele sunt decise la momentul compilării și doar consultate la runtime; altele se declanșează dinamic. Unele omoară stări individuale; altele omoară contexte întregi. Secțiunile de mai sus le-au prezentat pe fiecare în context; tabelul de mai jos le pune pe o singură pagină.

Predicat eșuat Match

Stări de variabilă al căror DEFINE s-a evaluat la fals pe rândul curent — ramuri moarte.

Avans inline pe lanțul END Match

Variabile care au atins contorul maxim și ar lăsa altfel starea la mijlocul iterației; avansate prin sfârșiturile grupurilor de lungime fixă astfel încât absorbția să poată compara în punctul corect.

Absorbție de context Absorb

Contexte mai noi a căror fiecare stare este acoperită de starea unui context mai vechi cu un contor mai mare — vezi §2.5 pentru regula conceptuală, §3.2 pentru eligibilitatea la momentul compilării, §3.5 pentru verificarea per pereche.

Deduplicare de stări Advance

Stări atinse prin ramuri DFS diferite care ajung la aceeași poziție cu aceleași contoare — doar prima (cea lexical cea mai timpurie) supraviețuiește; echivalentele ulterioare sunt eliminate în liniște, ceea ce este, de asemenea, modul în care se aplică preferința (§2.4).

Terminare timpurie la FIN (în context) Advance

Stări încă în așteptare în coada DFS când o ramură ajunge la FIN — prin ordinea lexicală, toate stările rămase sunt mai puțin preferate și pot fi eliminate imediat.

Tăiere a candidatului de potrivire (între contexte) La FIN

Alte contexte al căror rând de început cade în intervalul candidatului de potrivire — contextul care a atins FIN poate încă să caute o potrivire mai lungă (retragere greedy), dar sub AFTER MATCH SKIP PAST LAST ROW orice context din intervalul candidatului nu mai poate produce o ieșire raportabilă, indiferent de modul în care se termină acea căutare, și este tăiat imediat.

Garda de ciclu Advance

Expandări epsilon care revizitează același element de tipar în cadrul aceluiași DFS — altfel ar bucla pentru totdeauna în grupuri nullable.

Avans rapid pentru buclă vidă Advance

Potriviri legitime cu iterație vidă pe care garda de ciclu le-ar omorî în grupuri nullable — ocolește ciclul prin ieșirea din grup cu iterațiile rămase necesare declarate vide.

Tăiere de cadru mărginit Match

Contexte a căror potrivire a atins limita superioară a cadrului specificată de utilizator — forțate la nepotrivire pentru a nu se putea extinde dincolo de aceasta (§3.4).

Citirea intrărilor după insigna lor de fază urmărește durata de viață a unui context: tăierea se declanșează la fiecare rând prin cele trei faze principale (Match, Absorb, Advance) și din nou la finalizarea potrivirii (La FIN). Citirea în schimb a descrierilor grupează regulile după ceea ce vizează: ramuri moarte, contexte redundante, stări echivalente, bucle infinite și extindere excesivă dincolo de limitele impuse de utilizator.

Nicio singură regulă, de una singură, nu ar fi suficientă. Garda de ciclu singură ar omorî potriviri legitime în grupuri nullable; avansul rapid pentru buclă vidă singur nu ar opri buclele epsilon infinite; absorbția singură ar consolida în exces când DEFINE face referire la începutul potrivirii; deduplicarea singură nu ar elimina contextele redundante, ci doar stările redundante. Execuția rămâne liniară în cazurile care contează — PATTERN (A+ B+ C+ D) pe 100.000 de rânduri, benchmark-ul din panoul ③ al posterului — doar pentru că fiecare strat prinde ceea ce ratează straturile de deasupra sa.

3.7 Ieșirea EXPLAIN

EXPLAIN ANALYZE pe o interogare cu RPR expune statistici la nivel de NFA care nu sunt prezente pentru funcțiile de fereastră obișnuite. Trei grupuri de contoare sunt emise alături de operatorul de fereastră:

NFA States:    peak, total, merged
NFA Contexts:  peak, total, pruned
NFA: matched     (len min/max/avg)
NFA: mismatched  (len min/max/avg)
NFA: absorbed    (len min/max/avg)
NFA: skipped     (len min/max/avg)
Nav Mark Lookback:   | runtime | retain all
Nav Mark Lookahead:  | runtime | retain all
  (doar când interogarea folosește FIRST,
   PREV(FIRST(...)) sau NEXT(FIRST(...)))

Peak și total sunt instrumentare directă a execuției: câte stări au fost vreodată active simultan, câte au fost create pe parcursul vieții interogării și câte au fost contopite prin deduplicare. Histogramele de lungime a potrivirii separă patru rezultate — potriviri reușite, încercări de potrivire eșuate, contexte absorbite și contexte care au fost tăiate (sărite) fără a fi evaluate — iar raportarea lor cu min/max/avg face vizibile patologiile de performanță dintr-o privire: o rulare sănătoasă arată majoritatea contextelor fie ca potrivite, fie ca absorbite, cu lungimi nepotrivite mici.

Cele două contoare Nav Mark raportează bugetul de reținere al tuplestore-ului pe care §3.3 îl derivă la momentul compilării. Lookback este cea mai mare adâncime de ajungere înapoi peste PREV, LAST cu deplasament și formele compuse cu LAST interior; Lookahead este cea mai mare ajungere înainte (sau înapoi, când este negativă) măsurată de la începutul potrivirii celui mai vechi context activ, contribuită de FIRST și formele compuse cu FIRST interior.

Fiecare contor se afișează ca un întreg fix când deplasamentul este o constantă, „runtime” când deplasamentul este o expresie ne-constantă care trebuie evaluată la fiecare apel și „retain all” când execuția are nevoie de un buget nemărginit. Lookahead este emis doar când interogarea folosește efectiv navigare relativă la începutul potrivirii.

Împreună, aceste contoare fac posibilă depanarea performanței RPR fără atașarea gdb la backend.

Dincolo de contoare, EXPLAIN reproduce, de asemenea, fidel clauzele originale PATTERN și DEFINE, inclusiv cuantificatorii reticenți, repetarea de grup și opțiunea AFTER MATCH SKIP. Implementarea face un efort considerabil pentru a face acest dus-întors stabil, astfel încât pg_dump și pg_upgrade să poată păstra obiectele RPR fără derivă semantică — suita de regresie din rpr_explain o verifică caz cu caz (vezi §4).

§4. Teste — harta de acoperire

Patch-ul include cinci suite de regresie care, împreună, exercită fiecare strat descris în §3 — aproximativ 13.000 de linii de SQL, fiecare suită concentrată pe o preocupare diferită. Separarea este deliberată: ținerea preocupărilor parserului, a corectitudinii de runtime, a interacțiunilor planificatorului și a formatării ieșirii în fișiere separate face mai ușoară localizarea eșecurilor și împiedică o modificare ne-corelată dintr-un strat să invalideze accidental teste dintr-altul. Cele cinci suite sunt:

rpr

Semantica de interogare end-to-end — scenarii realiste de fereastră pe date sintetice de acțiuni (formă de V, formă de W, creșteri consecutive, inversări).

rpr_base

Stratul de parser — acceptarea cuvintelor-cheie, forme de sintaxă, cuantificatori, parsarea de navigare, mesaje de eroare și stabilitatea dus-întors pg_dump/pg_upgrade.

rpr_nfa

Runtime-ul NFA — bucla în trei faze, absorbția în fiecare formă absorbabilă și cazurile-limită ale ciclului de viață al contextului.

rpr_explain

Formatarea ieșirii — statistici NFA, deparsarea tiparului, citarea identificatorilor, stabilitatea formatului peste reîncărcare.

rpr_integration

Interacțiunile planificatorului — protecții care împiedică optimizările de fereastră ne-corelate să corupă semantica RPR.

4.1 rpr — scenarii end-to-end

Suita de scenarii este fața publică a setului de teste: folosește un set de date sintetice de prețuri de acțiuni de aproximativ 1.600 de rânduri și rulează interogări realiste împotriva sa — recuperare în formă de V, formă de W (dublu fund), creșteri și scăderi consecutive, tipare de inversare, partiții multi-simbol. Este singura suită în care intrările și ieșirile se citesc ca interogări pe care un utilizator le-ar putea scrie efectiv; celelalte sunt deliberat reductive, concentrate pe un singur strat la un moment dat.

Deoarece aceste interogări combină fiecare strat (parser, planificator, executor, EXPLAIN), un singur eșec în rpr spune rareori unde trăiește bug-ul. Cele patru suite care urmează sunt bisecția: un eșec în rpr plus un rpr_base care trece exclude parserul; plus un rpr_nfa care trece îl restrânge la forme de date specifice scenariului; plus un rpr_integration care trece exclude interferența planificatorului; iar orice derivă de deparsare apare în rpr_explain.

4.2 rpr_base — suprafața parserului

Suita de bază este cea mai mare și este cea mai mare dintr-un motiv: este responsabilă să dovedească faptul că fiecare bucată legală de sintaxă din §1.2 se parsează efectiv, fiecare bucată ilegală din §1.3 este respinsă cu o eroare utilă și fiecare formă acceptată supraviețuiește unui dus-întors de serializare. Cea mai mare parte a sa este structurată ca fragmente mici și concentrate — câte unul per caracteristică sintactică — în loc de interogări lungi și realiste, deoarece scopul este acoperirea, nu realismul scenariului.

Testele de serializare merită atenție specială. Obiectele RPR (viziuni, viziuni materializate, ieșire pg_dump) trebuie să facă dus-întors prin reprezentarea catalogului fără derivă semantică, inclusiv subtilități precum indicatorul reticent pe un cuantificator sau forma exactă a unei expresii de navigare compuse. Un set mic de obiecte specifice serializării (viziunile rpr_serial_v* și tabelele lor de suport) este lăsat intenționat pe loc la sfârșitul rulării, astfel încât infrastructura înconjurătoare de regresie să le poată prelua și să exercite pg_dump și pg_upgrade împotriva lor. Restul schelei de testare este eliminat ca de obicei. Bug-urile prinse astfel (cum ar fi pierderea unui indicator reticent în timpul deparsării și re-parsării) apar doar când dus-întorsul este exercitat de la un capăt la altul.

4.3 rpr_nfa — motorul de runtime

Aceasta este suita care exercită fiecare mecanism descris în §3.5 și §3.6. Testele sale urmează un tipar consistent: un tabel de intrare ale cărui rânduri sunt tablouri booleene explicite care declară care variabile DEFINE se potrivesc la fiecare rând, asociate cu un tipar care testează un comportament specific de runtime. Idiomul tabloului boolean decuplează testul de runtime de mașinăria de evaluare DEFINE — ceea ce este testat este „dat fiind că aceste variabile se potrivesc aici, bucla NFA produce intervalul de potrivire așteptat?” în loc de „evaluează corect evaluatorul de expresii DEFINE acești booleeni?” Evaluatorul DEFINE este testat altundeva (rpr_base pentru parsare, rpr pentru comportament end-to-end).

O fixare tipică de test arată astfel — o coloană de tablouri cu nume de variabile în care fiecare intrare spune care variabile DEFINE se declanșează pe acel rând și un tipar ale cărui clauze DEFINE testează direct pentru acele nume:

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

Citirea coloanei de tablouri în jos înseamnă citirea directă a scenariului de test. Rândurile 2 și 3 poartă ambele nume — A și B se declanșează amândouă acolo, astfel încât NFA-ul are o alegere reală despre unde să comute de la ramura A la ramura B. Potrivirea așteptată (A la rândurile 1–3 urmată de B la rândul 4, sub preferința greedy a standardului) este fixată doar de acei indicatori, fără evaluare de expresie de vreo importanță aici — = ANY este doar stratul trivial care expune coloana de tablou către DEFINE, nu ceea ce exercită testul. Scrierea aceluiași scenariu cu un predicat numeric (price > PREV(price) și similare) ar încurca testul NFA cu comportamentul evaluatorului de predicate; idiomul tabloului ține cele două curat separate, iar un eșec aici indică direct bucla NFA.

Acoperirea absorbției este deosebit de temeinică, deoarece absorbția este optimizarea cea mai probabilă să producă în liniște răspunsuri greșite dacă se angajează când nu ar trebui. Testele acoperă fiecare formă din analiza de cazuri a §3.2:

• variabilă nemărginită simplă (A+) — colapsul canonic N-la-1;
• grupuri de lungime fixă ((A B)+, (A B{2})+, imbricarea pe trei niveluri ((A (B C){2}){2})+);
• variabilă nemărginită care conduce, cu un sufix fix (A+ B) — doar A+ care conduce poartă indicatori de absorbție, sufixul nu;
• absorbție per ramură în interiorul unei alternări (B+ C | B+ D);
• mai multe variabile nemărginite (A+ B+) — doar cea conducătoare este absorbabilă;
• cuantificatori reticenți (A+?) — verificat că sunt excluși din absorbție;
• nemărginit care nu conduce (A B+) — verificat că este exclus.

Dincolo de absorbție, suita acoperă ciclul de viață al contextului: contexte suprapuse sub AFTER MATCH SKIP TO NEXT ROW, curățarea contextelor eșuate la mijlocul fluxului, finalizarea la sfârșitul partiției a contextelor incomplete și contexte întâlnite după ce un candidat de potrivire a fost deja înregistrat în contextul-cap. Fiecare dintre acestea se mapează la o regulă specifică de tăiere din §3.6, iar testele sunt scrise pentru a eșua zgomotos dacă regula se declanșează greșit (fie prin lăsarea contextelor redundante active, fie prin omorârea unui context care ar fi trebuit să producă ieșire).

4.4 rpr_explain — stabilitatea ieșirii

Ieșirea EXPLAIN face parte din contractul către utilizator — instrumentele terțe (autocompletare psql, panouri de monitorizare, scrapere de jurnal) o parsează, iar modificările care par cosmetice le pot strica. Suita rpr_explain verifică trei lucruri:

• Contoarele NFA apar în locul potrivit — statisticile per WindowAgg (stări peak/total/merged, contexte peak/total/pruned, histograme de lungime pentru matched/mismatched/absorbed/skipped, Nav Mark Lookback și — când navigarea relativă la începutul potrivirii este în uz — Nav Mark Lookahead) toate apar sub EXPLAIN ANALYZE cu etichetele documentate.
• Tiparele se deparsează corect — fiecare formă de cuantificator, inclusiv variantele reticente și formele mărginite; fiecare alternare; fiecare grup; fiecare formă AFTER MATCH SKIP; INITIAL; apeluri de navigare cu deplasamente; navigare compusă. Textul deparsat trebuie să facă dus-întors prin parser nemodificat.
• Citarea identificatorilor este corectă — variabilele de tipar și expresiile DEFINE sunt emise cu aceleași reguli de citare ca identificatorii SQL obișnuiți, astfel încât numele neobișnuite de variabile să nu strice ieșirea pg_dump.

La fel ca rpr_base, această suită își lasă intenționat obiectele pe loc la sfârșitul rulării, astfel încât acoperirea pg_dump și pg_upgrade să se extindă și asupra artefactelor de pe partea de explain.

4.5 rpr_integration — interacțiunile planificatorului

Planificatorul PostgreSQL are multe optimizări care operează pe interogări de fereastră — canonicalizarea cadrului, împingerea condiției de rulare, deduplicarea ferestrelor identice, proiecția ieșirilor neutilizate, tranzițiile inverse ale agregărilor mobile — și fiecare dintre ele a fost proiectată fără RPR în minte. Majoritatea sunt nesigure de aplicat când o fereastră are o clauză PATTERN: cadrul face parte din contractul de potrivire, ieșirea potrivită nu mai este monotonă în vreun mod evident, iar două ferestre cu aceeași specificație, dar DEFINE-uri diferite produc rezultate cu adevărat diferite. Suita de integrare verifică faptul că fiecare dintre aceste optimizări este corect dezactivată sau ocolită pentru ferestrele RPR:

Canonicalizarea cadrului

Planificatorul rescrie în mod normal ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING în ROWS UNBOUNDED PRECEDING pentru agregările monotone. Cadrul RPR este intervalul potrivirii, nu o fereastră de agregare, și trebuie să rămână textual.

Împingerea condiției de rulare

Un filtru monoton WHERE pe ieșirea unei funcții de fereastră poate fi în mod normal împins în operatorul de fereastră ca o condiție de oprire. Pentru RPR, acest lucru ar termina prematur potrivirea de tipare, putând tăia potriviri în mijlocul extinderii.

Deduplicarea ferestrelor (RPR vs non-RPR)

Două ferestre cu ORDER BY și cadru identice ar fi în mod normal contopite într-una. O fereastră RPR și una non-RPR nu pot împărți niciodată starea, deoarece partea RPR poartă rezultate ale potrivirii.

Deduplicarea ferestrelor (DEFINE diferit)

Două ferestre RPR cu același PATTERN, dar clauze DEFINE diferite, produc potriviri diferite și trebuie să rămână distincte, chiar dacă forma lor structurală este identică.

Proiecția ieșirilor neutilizate

Chiar dacă interogarea înconjurătoare nu citește niciodată ieșirea pe rând a ferestrei, fereastra RPR nu poate fi eliminată: efectele secundare ale potrivitorului de tipare (care rânduri sunt în care potrivire) alimentează calculele cadrului redus în alte locuri ale planului.

Tranziții inverse ale agregărilor mobile

Agregările de fereastră cu o funcție de tranziție inversă pot fi în mod normal evaluate incremental pe măsură ce cadrul se mișcă. Cadrul redus al RPR nu este o fereastră glisantă; calea de tranziție inversă ar produce rezultate greșite.

Tiparul prin aceste teste este același: fiecare oferă o referință non-RPR care declanșează optimizarea (și verifică faptul că EXPLAIN o arată ca aplicată), apoi rulează o interogare RPR de formă structurală similară și verifică faptul că optimizarea nu este aplicată. Cele două jumătăți, împreună, dovedesc faptul că protecția din planificator face muncă reală, nu aprobă fiecare interogare fără verificare reală.

Această suită este, de asemenea, motivul pentru care §3.4 este scurtă. Mecanismele „limitelor potrivirii” — cadrul redus, SKIP, INITIAL, tăierea de cadru mărginit — sunt testate operațional altundeva; ceea ce verifică rpr_integration este că niciun alt stadiu al optimizatorului nu se atinge de ele pe parcurs. Un rpr_integration care trece este ceea ce permite restul suitelor să aibă încredere că intrările lor ajung la executor neatinse.