Row Pattern Recognition Analiză aprofundată
Un tur ghidat prin ISO/IEC 19075-5 · SQL R020 în PostgreSQL — ce s-a construit, ce rămâne nescris și cum se execută efectiv.
Parcurgeți standardul, urmăriți exemple practice, explorați proiectarea, apoi acționați un simulator NFA în timp real cu propriile dumneavoastră tipare.
Discuție: fir pgsql-hackers · cel mai recent patch (v55) · commitfest #4460.
Tradus preliminar de IA — erori posibile.
§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 au în comun o parte considerabilă a sintaxei și a semanticii (19075-5 notează câteva diferențe specifice R020 în §6.3.3), 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 de clauze în interiorul unei specificații de fereastră al cărei cadru este ROWS BETWEEN CURRENT ROW AND …: PATTERN descrie o expresie regulată peste variabilele de tipar denumite, DEFINE furnizează predicatul boolean care identifică fiecare variabilă, iar clauza opțională AFTER MATCH SKIP (implicit PAST LAST ROW) 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ă; până la 240 de variabile de tipar distincte.
- Cadrul ferestrei
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGsauROWS BETWEEN CURRENT ROW ANDnFOLLOWINGcu n ≥ 1 (19075-5 §6.10.2); orice alt cadru este respins, iarEXCLUDE NO OTHERSeste singura excludere acceptată.- 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.:Pricesimplu) 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 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. - Nume de navigare
PREV,NEXT,FIRSTșiLASTscrise ca apeluri necalificate în interiorulDEFINEînseamnă întotdeauna navigare; o funcție a utilizatorului cu același nume trebuie calificată acolo cu schema.- Argumente de navigare
- Pentru
PREV,NEXT,FIRSTșiLAST, argumentul interior trebuie să conțină cel puțin o referință de coloană, iar deplasamentul trebuie să fie o constantă la runtime. - 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 FIRST var și AFTER MATCH SKIP TO [LAST] var (SKIP TO var simplu înseamnă SKIP TO LAST var). Acestea depind, de asemenea, de istoricul potrivirii, întrucât executorul trebuie să poată indica rândul mapat la o variabilă dată î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 {- … -}, operatorul insensibil la ordine PERMUTE, precum și funcțiile de agregare și subinterogările în DEFINE, ambele respinse în prezent (o agregare calificată cu o variabilă ar avea nevoie și ea de istoricul potrivirii).
- MEASURES
- Expresii de ieșire denumite, pe potrivire, de ex.
MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; în R020 expusă prinOVERca 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 înDEFINE,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.pricesimplu înDEFINEsauMEASURES— 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 la orice rând, de la rândul curent până la sfârșitul cadrului complet al ferestrei (spre deosebire de INITIAL).
- 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
ALL ROWS PER MATCH. Acea opțiune nu se aplică ferestrelor (19075-5 §6.3.3 (4)), așa că într-o fereastră sintaxa este permisă (§6.13), dar nu are nicio ieșire asupra căreia să acționeze. - Regex: ()
- Tipar vid — potrivește secvența vidă.
- PERMUTE(...)
- Potrivire insensibilă la ordine peste variabilele listate. Cuvântul-cheie este recunoscut și respins („PERMUTE is not supported”);
permuterămâne utilizabil ca nume de variabilă de tipar. - Funcții de agregare în DEFINE
- Agregările precum
SUM,AVG,COUNTnu sunt permise în predicateleDEFINE. Standardul le permite ca agregări curgătoare peste potrivirea parțială; o agregare calificată cu o variabilă, precumAVG(B.Price), depinde de același istoric de potrivire pe care îl necesităMEASURES/CLASSIFIER(), în timp ce una necalificată acoperă toate rândurile potrivirii de până acum. - Subinterogări în DEFINE
- Orice subinterogare din
DEFINEeste respinsă. Standardul permite una care nu efectuează recunoaștere de tipare de rânduri și nu referă nicio variabilă de tipar de rânduri; deocamdată, patch-ul respinge mai mult decât este necesar.
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 (patch-ul merge mai departe și respinge toate subinterogările din DEFINE, după cum s-a arătat mai sus); iar RPR nu poate fi folosit într-o interogare recursivă. Patch-ul aplică regula referințelor externe („cannot use outer query column in DEFINE clause”) și regula recursivității, pe aceasta din urmă pentru fiecare element al unei clauze WITH RECURSIVE. De asemenea, respinge funcțiile volatile și referințele la rândul întreg în DEFINE.
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 cinci exemple rezolvate: o singură potrivire (mișcarea NFA), alternarea, absorbția de context în cazul ușor și două cazuri în care absorbția este dezactivată.
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 (implicit n = 1). Privire înainte; rar în forma de fereastră, deoarece fereastra este monotonă.
- FIRST(expr [, n])
- Rândul aflat n rânduri după primul rând al potrivirii curente (implicit n = 0, chiar primul rând). „Comparație cu rândul care a început această potrivire.”
- LAST(expr [, n])
- Rândul aflat n rânduri înaintea ultimului rând potrivit (implicit n = 0). În interiorul
DEFINE, ultimul rând potrivit este rândul curent, așa căLAST(price)citește rândul curent.
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 rândul pe care îl citește
FIRST(expr, n)(implicit n = 0, m = 1). „Care a fost valoarea chiar înainte de începerea acestei potriviri?” - NEXT(FIRST(expr [, n]) [, m])
- Fă m rânduri înainte de la rândul pe care îl citește
FIRST(expr, n). 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 rândul pe care îl citește
LAST(expr, n). „Comparație cu un rând puțin înaintea celui mai recent rând potrivit.” - NEXT(LAST(expr [, n]) [, m])
- Fă m rânduri înainte de la rândul pe care îl citește
LAST(expr, n).
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 simple sunt relative la rândul curent și sunt întotdeauna sigure; FIRST și variantele cu deplasament ale lui LAST, singure sau în interiorul unui PREV/NEXT compus, sunt relative la limitele potrivirii, ceea ce interacționează cu absorbția de context: planificatorul dezactivează atunci absorbția pentru întregul tipar. Mecanismul din spatele acestei interacțiuni este subiectul §2.6.
2.3 Exemplu rezolvat 1 — mișcarea NFA
SKIP PAST LAST ROW odată ce potrivirea sa este înregistrată.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:
| Rând | Preț | Variabile adevărate | Acțiune |
|---|---|---|---|
| 0 | 100 | START | Context nou. START se potrivește și iese imediat (max=1); starea avansează la UP+. |
| 1 | 110 | START, UP | UP se potrivește. Avansul se bifurcă: o stare buclează la UP, alta iese către DOWN+. |
| 2 | 120 | START, UP | UP se potrivește în starea care buclează și se bifurcă din nou. Starea DOWN de la rândul 1 moare (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP eșuează pe starea care buclează și moare. Starea DOWN de la rândul 2 se potrivește. Avansul se bifurcă: bucla la DOWN și ieșirea către #FIN — se înregistrează un candidat de potrivire peste rândurile 0–3. |
| 4 | 108 | START, DOWN | DOWN se potrivește pe starea care buclează și se bifurcă din nou; noul candidat FIN peste rândurile 0–4 îl înlocuiește pe cel mai scurt. |
| 5 | 130 | START, UP | Starea DOWN care buclează eșuează (130 ≮ 108). Fără nicio stare activă rămasă în acest context, candidatul înregistrat (rândurile 0–4) este finalizat ca potrivire. Următoarea încercare începe la rândul 5; START se potrivește, dar partiția se termină înainte de vreun UP. |
Punctul-cheie: la rândul 3, rândul satisface atât START (mereu adevărat), cât și DOWN, dar START contează doar pentru un context care începe la rândul 3; în acest context, starea UP care buclează moare și avansează doar starea care așteaptă la 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 ultimul candidat FIN (rândurile 0–4) — produs când DOWN a ieșit la rândul 4, înlocuind candidatul de la rândul 3 — este finalizat ca potrivire.
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ând | Preț | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
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 ordinea tiparului, ramura anterioară întâi.
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. Ambele avansează apoi la DONE, unde se întâlnesc.
| Rând | Variabile adevărate | Stări active |
|---|---|---|
| R | UP, HIGH | Starea A (ramura UP) și Starea B (ramura HIGH) avansează ambele la DONE cu aceleași contoare; B este un duplicat al lui A și este eliminată |
| R+1 | DONE | Starea A potrivește DONE și ajunge la #FIN |
În termenii standardului, ambele ramuri produc o potrivire de aceeași lungime peste aceleași rânduri, rezultând 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. Executorul aplică acest lucru la rândul R, nu la FIN: adaugă mai întâi starea de pe ramura UP, astfel încât nfa_append_state_unique() o păstrează și elimină starea identică de pe ramura HIGH.
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):
| Rând | Contexte naive | Cu absorbție |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 absorbit |
| 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 | cinci contexte | C1[A:5] |
Contextele active scad de la O(n) la O(1), astfel încât totalul pe partiție scade de la O(n²) la O(n). 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:
| Zi | Preț | C1 — start marți price > PREV(price) | C2 — start miercuri price > PREV(price) |
|---|---|---|---|
| Lun | $100 | — | — |
| Mar | $108 | $108 > $100 ✓ (tocmai a început) | — |
| Mie | $112 | $112 > $108 ✓ | $112 > $108 ✓ (tocmai a început) |
| Joi | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| Vin | $110 | $110 > $116 ✗ — finalizează | $110 > $116 ✗ — finalizează |
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ă
DEFINE face referire la FIRST — regula de absorbție nu mai este valabilă, iar planificatorul dezactivează absorbția pentru tipar.
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+).
| Zi | Preț | C1 — start luni FIRST = $100 price < $100 + 10 | C2 — start marți FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| Lun | $100 | $100 < $110 ✓ | — |
| Mar | $108 | $108 < $110 ✓ | $108 < $118 ✓ (tocmai a început) |
| Mie | $112 | $112 < $110 ✗ — finalizează Lun–Mar | $112 < $118 ✓ |
| Joi | $116 | — | $116 < $118 ✓ |
| Vin | $110 | — | $110 < $118 ✓ (încă rulează) |
Sub absorbție, C2 ar fi fost contopit în C1 marți — contextul contopit păstrează doar plafonul lui C1 ($110), astfel încât perspectiva distinctă a lui C2 (plafon $118, o rulare de patru zile până vineri) nu este acoperită de viitorul lui C1. În această săptămână anume, ieșirea se întâmplă să nu se schimbe: C1 înregistrează Lun–Mar, C2 a început în interiorul acelei potriviri și este eliminat de SKIP PAST LAST ROW, iar următoarea încercare începe miercuri cu propriul plafon ($122) și potrivește Mie–Vin. În general însă, rezultatul DEFINE al unui context anterior nu îl mai subsumează pe cel al unuia ulterior, așa că comparația de contoare pe care se bazează absorbția este invalidă. Ori de câte ori un predicat DEFINE poartă dependență de începutul potrivirii, planificatorul dezactivează, prin urmare, 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 mai jos extinde panoul dreapta jos al posterului („② Navigare”) cu formele compuse și rezumă care forme de navigare creează dependență de începutul potrivirii:
| Navigare | Dep. de începutul potrivirii | Absorbabil? |
|---|---|---|
| PREV, NEXT | niciuna | da |
| LAST (fără deplasament) | niciuna | da |
| LAST cu deplasament | verificare a limitei | nu |
| FIRST (oricare) | directă | nu |
| Compus (FIRST interior) | directă | nu |
| Compus (LAST interior, fără deplasament) | niciuna | da |
| Compus (LAST interior cu deplasament) | verificare a limitei | nu |
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. Sorțile 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 este garantat să îl acopere, așa că eliminarea unuia nu mai poate fi demonstrată ca sigură.
Planificatorul detectează această distincție la momentul compilării și activează sau dezactivează absorbția pentru întregul tipar; când este dezactivată, execuția plătește costul multi-context. Benchmark-ul posterului din panoul ③ nu folosește FIRST, așa că absorbția rămâne activă, motiv pentru care PostgreSQL rămâne liniar atât în cazurile de succes, cât și în cele de eșec.
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ă aproximativ O(n) odată ce o potrivire este confirmată, iar PostgreSQL conduce cu aproximativ 16× până la 33× (cifrele Trino exclud deja pornirea JVM).
Pe tiparul de eșec (A+ B+ C+ E), Trino, căruia pare să-i lipsească absorbția, urmărește fiecare potențial început de potrivire și se degradează chiar mai rapid decât O(n²) (un timp de aproximativ 56× mai mare pentru de 5× mai multe rânduri); 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.
| Rând | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | începe potrivirea; rândurile 0–4 vor fi singura potrivire | potrivirea începe la rândul 0 |
| 1 | (în interiorul potrivirii 0) | potrivirea începe la rândul 1 — trebuie menținută activă |
| 2 | (în interiorul potrivirii 0) | potrivirea începe la rândul 2 — trebuie menținută activă |
| 3 | (în interiorul potrivirii 0) | potrivirea începe la rândul 3 — trebuie menținută activă |
| 4 | potrivirea 0 se finalizează (rândurile 0–4) | cinci potriviri se finalizează: 0–4, 1–4, 2–4, 3–4, 4–4 |
AFTER MATCH SKIP TO NEXT ROW, fiecare context care începe târziu este propriul rând de ieșire. Două contexte la același element de tipar nu mai sunt redundante — sunt amândouă ieșiri necesare, iar eliminarea uneia ar elimina în liniște o potrivire pe care utilizatorul a cerut-o.
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 cele două moduri în care semantica unei interogări exclude absorbția:
FIRST sau LAST cu deplasament în DEFINE.AFTER MATCH SKIP TO NEXT ROW.
Oricare dintre condiții este suficientă pentru a dezactiva absorbția pentru întregul tipar, la fel și un cadru care nu se termină la UNBOUNDED FOLLOWING. Când niciuna nu este în vigoare — implicitul AFTER MATCH SKIP PAST LAST ROW, un sfârșit de cadru nemărginit și condiții DEFINE care folosesc doar PREV, NEXT sau LAST simplu — absorbția este activată, dar doar pentru stările din regiunea absorbabilă a tiparului: o variabilă greedy nemărginită aflată la început, precum A+ sau A*, un grup de lungime fixă cu un cuantificator greedy nemărginit, precum (A B)+, un grup greedy al cărui corp începe cu una dintre acestea, precum (A+ B)+ sau (A+ B){2}, ori ramuri de alternare construite din acestea; un grup reticent descalifică întregul său subarbore. Acolo unde acest lucru este valabil, ca pentru A+ din §2.5, execuția se reduce la un singur context și rămâne liniară; START UP+ DOWN+ din §2.3 nu primește deloc o regiune absorbabilă.
§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ă munca 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, limita de sfârșit trebuie să fie UNBOUNDED FOLLOWING sau un deplasament pozitiv FOLLOWING (deci și un cadru implicit este respins), iar opțiunile EXCLUDE altele decât EXCLUDE NO OTHERS 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ă:
| Sursă | Codificare în arbore |
|---|---|
| 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) |
Fiecare predicat DEFINE este apoi verificat de tipuri împotriva coloanelor partiției și constrâns la o expresie booleană. Două lucruri practice decurg de aici. În primul rând, analiza de parsare nu adaugă nimic în lista țintă a interogării pentru DEFINE; în schimb, planificatorul marchează ca necesară fiecare coloană referită de un predicat DEFINE, așa cum face pentru HAVING, și 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ă nouă reguli de rescriere într-o singură trecere de jos în sus (în cadrul unei secvențe, contopirea grupurilor rulează încă o dată, deoarece contopirile anterioare pot aduce două grupuri identice unul lângă altul):
- 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}- Contopirea 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 - Normalizarea reticenței
A{2}?→A{2}(reticența este eliminată oriunde min = max)
Înmulțirea cuantificatorilor colapsează doar când contoarele realizabile formează un singur interval contiguu, iar potrivirea preferată nu se mută: un exterior exact ((A{2,3}){5} → A{10,15}), un copil cu min 0 sau intervale ale copilului care se ating, cu un min al copilului de cel mult 1 sau un max al copilului nemărginit ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), unde un exterior cu min 0 necesită și un min al copilului de cel mult 1 ((A{2,})* rămâne, deoarece A* ar accepta un singur rând). Un copil de tip grup al cărui propriu cuantificator nu este exact trebuie mai întâi să aibă un corp de lungime fixă, astfel încât ((A | B B){1,2}){2} rămâne intact chiar și sub un exterior exact. 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 — sau pot deplasa potrivirea preferată ((A{2,3}){1,2} preferă trei rânduri, acolo unde A{2,6} ia patru), așa că optimizatorul le lasă intacte. Nu este singura rescriere condiționată: contopirea grupurilor și contopirea sufixului necesită un corp care consumă un număr fix de rânduri, contopirea prefixului refuză un grup cu min 0, max finit și conținut nullable, nodurile reticente nu sunt nici contopite, nici înmulțite ((A+?)+ rămâne), iar o rescriere a cărei nouă limită ar produce overflow este refuzată.
Forma elementului
Fiecare element al tabloului plat reprezintă o singură poziție în tipar. Există șase 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; un separator de ramură care încheie fiecare ramură; ș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 marcatorul de alternare și de separatorii de ramură pentru a înlănțui ramuri, de începutul de grup pentru a-și numi propriul sfârșit de grup — un grup al cărui cuantificator permite zero este sărit prin next-ul acelui sfârșit — ș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 → 3
(deschide grupul; jump numește
propriul 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
(î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 își numește END-ul de la idx 3, iar dacă grupul ar fi opțional, saltul ar ieși prin next-ul acelui END către idx 4, fără a ajunge la END. 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ă cinci 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? B?)+,(A | B*)+;(A?)*este mai întâi înmulțit înA*și nu lasă niciun sfârșit de grup). Spune execuției să adauge o ieșire de avans rapid alături de bucla normală înapoi sub min, astfel încât garda de ciclu să nu omoare potriviri legitime în grupuri care pot produce iterații vide. - Vid-preferat
- Setat pe sfârșiturile de grup al căror corp preferă potrivirea vidă, ca în
(A?? B??){2}. Ordonează ieșirea de avans rapid înaintea buclei înapoi sub min, acolo unde propria lăcomie a grupului nu spune nimic. - Î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 tabloul plat de la
elementul 0 ș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 admite patru forme structurale:
- Cazul 1 — Variabilă nemărginită simplă
-
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ă.
A+,A*,A{2,∞} - Cazul 2 — Grup de lungime fixă, exterior nemărginit
-
Fiecare copil are
(A B)+,(A B{2})+,((A (B C){2}){2})+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ă
-
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ă A primește ambii indicatori, BEGIN-ul care îl înconjoară primește indicatorul de în-regiune, iar B și END nu primesc niciunul.
(A+ B)+,(A+ B){2} - Cazul 4 — Alternare
-
Fiecare ramură, atinsă prin lanțul de separatori, este judecată separat după cazurile de mai sus; marcatorul de alternare primește indicatorul de în-regiune când oricare ramură se califică.
A+ | B+,A+ | C D
Cazurile structurale neacoperite de aceste patru 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. 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
dacă targetPos != currentPos:
preia rândul de la targetPos
în nav_slot
îndreaptă slotul exterior spre nav_slot
result = eval_inner_expression()
restaurează current_row_slot
copiază rezultatul by-ref din nav_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 și niciun slot per referință; când ținta este rândul curent, preluarea și schimbul sunt omise cu totul. Preluarea copiază rândul țintă în slotul de navigare (cu excepția cazului în care slotul îl deține deja), iar pasul de restaurare copiază un rezultat transmis prin referință în memoria per-tuplu, astfel încât următoarea preluare să nu îl poată elibera.
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 currentPos − 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 (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − 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ă absorbția de context este posibilă în vreun fel (§2.5 vs §2.6): o singură variabilă dependentă de începutul potrivirii o dezactivează pentru întregul tipar.
- Nicio navigare
- Doar
PREV/NEXT LASTfără deplasament- Compus cu
LASTinterior (fără deplasament)
LASTcu deplasamentFIRST(orice formă)- Compus cu
FIRSTinterior - Compus cu
LASTinterior (cu deplasament)
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ă. Executorul o calculează pornind de la două deplasamente complementare, rezolvând fiecare deplasament o dată per scanare (pe cele constante și la inițializarea executorului, astfel încât EXPLAIN simplu să le poată afișa):
- Bugetul de privire înapoi (lookback)
- Cât de departe înapoi de la rândul curent ar putea ajunge orice apel DEFINE.
- Bugetul de privire înainte de la start (lookahead-from-start)
- Ajungerea minimă înainte (înapoi, când este negativă) de la începutul potrivirii celui mai vechi context activ — cel mai timpuriu rând de care ar putea avea nevoie orice apel DEFINE.
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. Liniile Nav Mark raportate de EXPLAIN (§3.7) — Lookback și Lookahead — sunt aceste două bugete, nu vârfuri măsurate. Fiecare este afișată doar când o navigare o alimentează și apare chiar și fără ANALYZE; un deplasament a cărui valoare este cunoscută doar la runtime (de exemplu, un parametru de plan generic) afișează runtime sub EXPLAIN simplu și valoarea sa rezolvată sub EXPLAIN ANALYZE, iar retain all (Lookback) sau infinite (Lookahead) marchează un deplasament care produce overflow.
3.4 Limitele potrivirii — SKIP, INITIAL și cadru mărginit
Un rezultat de potrivire este înregistrat ca două valori: rândul la care începe potrivirea și lungimea sa. Un început negativ înseamnă că poziția nu a fost încă evaluată; odată ce începutul este setat, interogările ulterioare împotriva executorului — „este acest rând în interiorul unei potriviri?” — pot răspunde în O(1) prin inspectarea perechii. Lungimea codifică rezultatul: -1 pentru un rând nepotrivit, 0 pentru o potrivire vidă și numărul de rânduri pentru o potrivire reală. 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ă atât de un rând nepotrivit, cât și 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 tiparul acelei ferestre 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, apoi împinge NFA-ul înainte rând cu rând — resetând pentru fiecare rând un tablou de potrivire per variabilă la „neevaluat” — până când acel context nu mai are stări active sau partiția se termină. Predicatele DEFINE sunt evaluate leneș: o variabilă este evaluată prima dată când o stare o consumă, astfel încât o variabilă pe care nicio stare activă nu o testează la acest rând nu este evaluată niciodată. 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 a atins sfârșitul cadrului său:
forțează nepotrivire (finalizează devreme)
continuă
dacă matchStartRow diferă de
poziția de evaluare partajată:
resetează variabilele DEFINE dependente
de începutul potrivirii la neevaluat (§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)
dacă a înregistrat o potrivire și
SKIP PAST LAST ROW:
taie contextele ulterioare care
încep în interiorul potrivirii
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]
asertează că elem este o variabilă
# advance parchează doar variabile
dacă varMatched[elem.varId] este
neevaluat:
evaluează-i DEFINE-ul acum
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ă
sau deține o potrivire înregistrată:
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ă) până când contextul înregistrează o potrivire, ceea ce îl fixează la fals — absorbția ar elibera o potrivire pe care niciun context absorbant nu o poate reproduce. 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 de vizitare
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, oprindu-se
odată ce FIN e înregistrat),
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 marchează
contextul astfel încât contextele
ulterioare din intervalul acestui
candidat să fie tăiate — 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, odată ce Advance a terminat cu contextul care a înregistrat un candidat, fiecare context ulterior al cărui rând de început cade în intervalul candidatului este tăiat la același rând, 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 pasul de tăiere între contexte la momentul FIN. În interiorul contextului, FIN reduce și munca lexical inferioară: Advance elimină stările rămase în coadă (descris mai devreme în această secțiune), iar în cadrul unui DFS, fiecare cale mai puțin preferată — ramurile ALT ulterioare, cealaltă dintre căile de salt și de intrare ale lui BEGIN, calea de intrare a unei variabile reticente, cealaltă dintre căile de buclare și de ieșire ale lui END — se oprește odată ce o potrivire este înregistrată, astfel încât un singur advance înregistrează cel mult o potrivire.
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
(avans rapid primul dacă
corpul preferă vidul; a doua
cale este eliminată dacă
prima a atins FIN)
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ă
dacă bucla a atins FIN:
elimină ieșirea
# preferă mai lungul
else iese al doilea
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? B?)+ și (A | B*)+ au această proprietate: în funcție de date, corpul poate completa o iterație fără a consuma deloc vreun rând. (Un singur copil opțional, precum (A?)*, este rescris în A* la momentul compilării și nu lasă în urmă niciun grup.) 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 în corp (jump-ul său este primul copil al grupului), corpul produce încă o potrivire vidă, ajunge din nou la END și așa mai departe. Fără ceva care să-l oprească, DFS-ul lui Advance nu s-ar termina niciodată.
Garda 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. Execuția păstrează un bitmap de vizitare, curățat înainte de expandarea DFS a fiecărei stări, în care sunt marcate doar acele END-uri etichetate — nimic altceva nu poate cicla, deoarece orice altă buclare înapoi a consumat un rând. Atingerea unui END marcat înseamnă că corpul tocmai a derivat o iterație vidă, iar starea nu este eliminată: la sau peste limita inferioară, părăsește grupul acolo (o iterație vidă oprește cuantificatorul), iar sub ea starea trece mai departe la bucla normală înapoi, astfel încât fiecare sosire vidă crește totuși contorul până când acesta atinge min. Să luăm (A? B?){2,3} fără ca vreuna dintre variabile să se potrivească nicăieri în fluxul de rânduri:
iter 1: A? B? potrivesc zero rânduri
→ END, count = 1 (sub min)
END deja marcat (la intrarea
în grup), dar sub min:
→ buclează înapoi în A?
iter 2: A? B? potrivesc zero rânduri
→ END, count = 2 (atinge min)
END deja marcat, la min:
→ părăsește grupul
iese cu o potrivire de lungime zero
Sub limita inferioară, eticheta de buclă vidă îi spune, de asemenea, handlerului END să cloneze o stare suplimentară de avans rapid alături de calea normală de buclare înapoi:
advance_end (count sub min):
cale de buclare înapoi:
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 înapoi este cea care prinde cazul în care corpul mai are potriviri reale de produs ulterior — de exemplu, în (A? B?){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 iese imediat din grup, declarând „restul iterațiilor necesare sunt vide”, și permite potrivirii să reușească cu un corp de lungime zero. Corpul, nu propria lăcomie a grupului, decide ordinea: avansul rapid merge primul exact atunci când corpul preferă potrivirea vidă (un corp reticent precum (A?? B??)), iar dacă prima cale ajunge la FIN, a doua este eliminată, astfel încât o cale mai puțin preferată nu poate înlocui potrivirea preferată. 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
Faptul că execuția rămâne mărginită 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 în care fiecare stare se află într-un punct de comparație și este acoperită de o stare absorbabilă a unui context mai vechi, la același element, cu un contor mai mare sau egal — 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) Advance
- 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 ROWorice 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 ce Advance a terminat cu contextul care a înregistrat candidatul. - Garda de ciclu Advance
- Expandări epsilon care ajung la END-ul unui grup nullable deja marcat în cadrul aceluiași DFS (marcat la intrarea prin BEGIN sau la o sosire anterioară) — altfel ar bucla pentru totdeauna; starea părăsește grupul acolo la sau peste limita inferioară și continuă să bucleze sub ea.
- Avans rapid pentru buclă vidă Advance
- Sub limita inferioară a unui grup nullable, o cale suplimentară care iese din grup cu iterațiile rămase necesare declarate vide, ordonată față de bucla înapoi după preferința corpului.
- 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). 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ă. 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. Sursa documentează cazuri pe care straturile nu le prind: dedup păstrează separat stările care diferă doar prin contoare peste min, astfel încât (A{2,} B)+ C cu C niciodată adevărat menține Θ(n²) stări la vârf și creează Θ(n³) dintre ele (37 s pe 320 de rânduri), iar o succesiune de alternări complet nullable este enumerată cale cu cale, astfel încât (A?|B?){30} durează peste o jumătate de oră.
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. În format text, acestea sunt emise alături de operatorul de fereastră, după linia Pattern:, eventualele linii Nav Mark (pe care le arată și EXPLAIN simplu) și linia Storage::
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(fiecare doar când DEFINE folosește
o navigare care o alimentează)
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)
(a doua linie NFA doar când oricare
contor este nenul; un contor zero
se afișează fără (len ...))
Formatele non-text emit fiecare contor ca proprietate separată. 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; pruned numără contextele care au eșuat după un singur rând. Histogramele de lungime a potrivirii separă patru rezultate — potriviri reușite, încercări de potrivire care au eșuat după mai mult de un rând (mismatched), contexte absorbite și contexte eliberate de AFTER MATCH SKIP PAST LAST ROW pentru că au început în interiorul unei potriviri înregistrate (skipped) — 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ă din DEFINE. Lookback este cea mai mare adâncime de ajungere înapoi de la rândul curent peste PREV, LAST cu orice deplasament (inclusiv implicitul 0) și formele compuse cu LAST interior; Lookahead este ajungerea minimă înainte (negativă când privește înaintea începutului potrivirii) 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ă cunoscută doar per scanare și — doar pentru Lookback — „retain all” când deplasamentul produce overflow; un Lookahead care produce overflow se afișează „infinite”. Fiecare linie este emisă doar când o navigare din DEFINE o alimentează, iar ambele apar și sub EXPLAIN simplu: deplasamentele constante sunt stabilite la inițializarea executorului, în timp ce un deplasament cunoscut doar la runtime (de exemplu, un parametru de plan generic) afișează acolo „runtime” și întregul său rezolvat sub EXPLAIN ANALYZE.
Împreună, aceste contoare fac posibilă depanarea performanței RPR fără atașarea gdb la backend.
Dincolo de contoare, EXPLAIN afișează o linie Pattern: construită din tabloul de elemente compilat, așa că arată tiparul după rescrierile de la momentul compilării (PATTERN (A A) se explică drept a{2}) și poartă marcatorii de absorbție # (punct de comparație) și ~ (regiune absorbabilă); DEFINE și opțiunea AFTER MATCH SKIP nu sunt afișate. Reproducerea clauzelor așa cum au fost scrise, inclusiv cuantificatorii reticenți, repetarea de grup și opțiunea de skip, este sarcina lui pg_get_viewdef(), care 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 22.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
- Integrarea cu clauza WINDOW — scenarii realiste de fereastră pe date sintetice de acțiuni (formă de V, formă de W, creșteri consecutive, inversări), plus semantica navigării și erorile de restricție DEFINE.
- 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; plus un strat de planificator — optimizarea tiparelor, indicatorii de absorbție, fallback-ul optimizării, integrarea cu planificatorul.
- 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. Aceste scenarii sunt singurele teste ale căror intrări și ieșiri se citesc ca interogări pe care un utilizator le-ar putea scrie efectiv; restul fișierului, ca și celelalte suite, este reductiv — imbricarea PREV/NEXT și erorile de deplasament ne-constant, regulile de referință DEFINE și semantica deplasamentelor de navigare.
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. O a doua parte, stratul de planificator, acoperă optimizarea tiparelor, afișarea și analiza indicatorilor de absorbție, fallback-ul optimizării și integrarea cu planificatorul (subinterogări, join-uri, operații pe mulțimi, sortare și grupare).
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. Defecte precum 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: rânduri VALUES inline care poartă un tablou de nume de variabile ce declară care variabile DEFINE se potrivesc la fiecare rând, asociate cu un tipar care testează un comportament specific de runtime. Idiomul tabloului 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) — doarA+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 (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) apar sub
EXPLAIN ANALYZEîn text, JSON și XML cu etichetele documentate, iar Nav Mark Lookback și Lookahead apar exact atunci când navigarea din DEFINE le alimentează. - 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ă modul în care fiecare dintre aceste optimizări tratează ferestrele RPR — majoritatea trebuie dezactivate sau ocolite:
- Canonicalizarea cadrului
- Planificatorul rescrie în mod normal
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGînROWS UNBOUNDED PRECEDINGpentru funcțiile de fereastră independente de cadru, precumrow_number,rankșintile. 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
WHEREpe 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 sau SKIP diferit)
- Două ferestre RPR cu același
PATTERN, dar clauzeDEFINEdiferite sau unAFTER MATCH SKIPdiferit, produc potriviri diferite și trebuie să rămână distincte, chiar dacă forma lor structurală este identică. - Proiecția ieșirilor neutilizate
- Aceasta are voie să se aplice: când interogarea înconjurătoare nu citește niciodată ieșirea ferestrei, funcția de fereastră devine NULL, iar WindowAgg-ul ei este eliminat, lăsând numărul de rânduri neschimbat. Testele verifică faptul că coloanele citite de DEFINE ajung în continuare la WindowAgg atunci când acesta rămâne și că fereastra este păstrată atunci când valoarea sa este citită.
- 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.
Cazuri suplimentare verifică faptul că estimarea costului ține cont de DEFINE, că o subinterogare care conține o fereastră RPR nu este aplatizată, că expresiile DEFINE nu ajung într-un WindowAgg superior și că LIMIT rămâne deasupra WindowAgg-ului; un al doilea grup rulează RPR alături de CTE-uri, join-uri, operații pe mulțimi, instrucțiuni pregătite, tabele partiționate și construcții similare. Majoritatea cazurilor protejate urmează aceeași formă: o referință care declanșează optimizarea (de obicei o interogare non-RPR, verificată în EXPLAIN), apoi o interogare RPR de formă structurală similară în care optimizarea nu este aplicată — pentru cazul de dedup DEFINE/SKIP, referința este formată din două ferestre RPR identice, iar cazul tranzițiilor inverse verifică ocolirea cu o agregare care scrie în jurnal, nu cu EXPLAIN. 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.