Row Pattern Recognition Approfondimento

§1. Lo standard, il sottoinsieme e le questioni aperte

1.1 Ambito dello standard

Row Pattern Recognition è stato introdotto in SQL da ISO/IEC 9075-2:2016 ed è descritto nel documento complementare ISO/IEC 19075-5:2021 (Parte 5, "Row Pattern Recognition").

Lo standard definisce due superfici per lo stesso meccanismo sottostante. La feature R010 inserisce una clausola MATCH_RECOGNIZE nella lista FROM per produrre una tabella derivata; la feature R020 integra la stessa logica di pattern in una specifica WINDOW per produrre l'output di una funzione finestra. Le due superfici condividono la maggior parte della sintassi e tutta la semantica, ma costituiscono punti di ingresso funzionalmente distinti — un database può implementarne una sola oppure entrambe.

La serie di patch qui discussa implementa un sottoinsieme della sola R020; la forma a clausola di tabella è deliberatamente fuori ambito.

La superficie R020 è ridotta ma espressiva. Una query associa un pattern a una finestra aggiungendo tre clausole all'interno della specifica della finestra: PATTERN descrive un'espressione regolare su variabili di pattern con nome, DEFINE fornisce il predicato booleano che identifica ciascuna variabile e AFTER MATCH SKIP controlla come i match successivi vengono posizionati all'interno della partizione.

Le clausole opzionali MEASURES, SUBSET, INITIAL/SEEK e la funzione ausiliaria CLASSIFIER() completano la feature. (La funzione MATCH_NUMBER() dello standard appartiene esclusivamente alla superficie R010 — 19075-5 §6.3.3 (6) la esclude esplicitamente da R020.)

Il patch copre una porzione di questo vocabolario sufficiente a far funzionare query non banali, ma si ferma prima di diversi costrutti la cui implementazione dipende da infrastrutture non ancora realizzate.

Il resto di questa sezione suddivide il vocabolario dello standard in ciò che il patch già supporta e ciò che lascia intenzionalmente per un secondo momento. Gli elenchi seguenti riflettono lo stato corrente della serie di patch.

1.2 Funzionalità implementate

Il vocabolario implementato è sufficiente a esprimere i pattern canonici a forma di V, a forma di W e di inversione che motivano lo stesso row pattern recognition. Copre inoltre ogni quantificatore standard — incluse tutte e sette le varianti reluctant *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — e le quattro primitive di navigazione necessarie alle condizioni DEFINE per confrontare righe adiacenti.

Clausola PATTERN

Definisce il row pattern all'interno di una specifica di finestra.

Regex: + * ? |

Quantificatori standard e alternativa.

Regex: raggruppamento ( )

Sotto-pattern racchiusi tra parentesi.

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

Conteggi di ripetizione delimitati.

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

Tutte e sette le varianti reluctant (non-greedy) definite dallo standard (escluse dall'ottimizzazione per assorbimento).

Clausola DEFINE

Condizioni booleane che identificano ciascuna variabile di pattern.

Variabile universale di pattern di riga

I riferimenti di colonna non qualificati in DEFINE (es. Price nudo) si risolvono alla riga corrente, secondo 19075-5 §4.10/§4.16.

PREV, NEXT (con offset)

Raggiungono n righe prima/dopo la riga corrente (default 1); l'argomento interno è un'espressione di valore arbitraria valutata sulla riga navigata.

FIRST, LAST (con offset)

Raggiungono una riga relativa al match; FIRST(expr, n) punta alla riga n dopo l'inizio del match, LAST(expr, n) alla riga n prima della riga di match più recente.

Navigazione composta (quattro forme)

Un passo esterno PREV/NEXT sovrapposto a un FIRST/LAST interno: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — sia il passo interno sia quello esterno accettano il proprio offset.

INITIAL

I match del pattern devono iniziare dalla riga corrente (default).

AFTER MATCH SKIP PAST LAST ROW

Modalità di skip predefinita; ammissibile per l'assorbimento del contesto.

AFTER MATCH SKIP TO NEXT ROW

Consente match sovrapposti; disabilita l'assorbimento.

1.3 Non implementate

Le funzionalità che rimangono non implementate si raggruppano in tre famiglie generali. La prima — e di gran lunga la più estesa — è quella dei costrutti centrati su MEASURES: la clausola MEASURES stessa, SUBSET, CLASSIFIER(), i riferimenti a colonna qualificati per pattern come B.price e la navigazione qualificata per pattern come LAST(B.price) o PREV(B.price).

Non si tratta tanto di lacune indipendenti quanto di viste diverse di un unico tassello mancante: l'executor dovrebbe mantenere una storia per match — un registro, per ogni riga del match, della variabile di pattern a cui è stata associata — e nessuno di questi costrutti ha una definizione significativa senza di essa. CLASSIFIER() legge il nome della variabile da quel registro; B.price legge la colonna price delle righe la cui voce nel registro indica B; LAST(B.price) percorre lo stesso insieme di righe e ne seleziona l'ultima; SUBSET U = (A, B) definisce una variabile virtuale che aggrega su entrambi i bucket; e MEASURES valuta espressioni come AVG(U.Price) utilizzando esattamente tale aggregazione.

L'executor attuale valuta i predicati DEFINE riga per riga ma non registra da alcuna parte le assegnazioni di variabile risultanti — non c'è nulla da interrogare in seguito. La costruzione dell'infrastruttura di storia è quindi il prerequisito per l'intero gruppo; le singole funzionalità ricadono come piccole proiezioni una volta che i registri esistono.

Il secondo gruppo riguarda i target alternativi di skip: AFTER MATCH SKIP TO label, AFTER MATCH SKIP TO FIRST var e AFTER MATCH SKIP TO LAST var. Anche questi dipendono dalla storia del match, poiché l'executor deve poter puntare a una specifica riga etichettata all'interno del match più recente.

Gli elementi rimanenti formano una coda eterogenea: la parola chiave SEEK (alternativa a INITIAL), il pattern vuoto (), la forma di esclusione {- … -} e l'operatore PERMUTE insensibile all'ordine.

MEASURES

Espressioni di output per match con nome, ad es. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; in R020 esposte tramite OVER come una funzione finestra. Accetta le parole chiave FINAL / RUNNING (19075-5 §5.4), che in R020 collassano sullo stesso valore poiché le measures sono sempre valutate sull'ultima riga del match (19075-5 §6.9 (3)).

SUBSET

Unioni con nome di variabili di pattern, ad es. SUBSET U = (A, B, C). Utilizzabili ovunque sia possibile referenziare una variabile di pattern — MEASURES, riferimenti qualificati per pattern in DEFINE, CLASSIFIER(U) — tutti casi che richiedono la storia del match.

CLASSIFIER()

Restituisce la variabile di pattern come la quale una data riga è stata associata. Definita sia per DEFINE sia per MEASURES (19075-5 §5.9); la risposta in una qualsiasi riga è il nome della variabile registrato nella storia del match per quella riga.

Riferimento a colonna qualificato per pattern

B.price nudo in DEFINE o MEASURES — il valore della colonna dalla riga mappata come la variabile indicata.

Navigazione qualificata per pattern

Limita la navigazione alle righe associate a una variabile con nome, ad es. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

Il match può iniziare in qualsiasi punto della finestra (al contrario di INITIAL).

AFTER MATCH SKIP TO label

Salta a una riga etichettata.

AFTER MATCH SKIP TO FIRST var

Salta alla prima riga associata alla variabile indicata.

AFTER MATCH SKIP TO LAST var

Salta all'ultima riga associata alla variabile indicata.

Regex: {- -}

Esclusione — rimuove le righe associate dall'output per match.

Regex: ()

Pattern vuoto — corrisponde alla sequenza vuota.

PERMUTE(...)

Matching insensibile all'ordine sulle variabili elencate.

Funzioni di aggregazione in DEFINE

Aggregati come SUM, AVG, COUNT non sono ammessi nei predicati DEFINE. Lo standard li consente come aggregati running sul match parziale (valutazione per riga sulle righe già mappate a una variabile), il che dipende dalla stessa storia per match richiesta da MEASURES/CLASSIFIER().

Vale la pena segnalare qui altri quattro punti, poiché possono facilmente essere scambiati per omissioni.

Il primo è che gli anchor di pattern ^ e $ non sono ammessi con RPR nella clausola WINDOW dallo standard stesso (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; con la definizione sottostante in 19075-5 §4.14.1); la loro assenza è conformità allo standard, non una lacuna.

Il secondo è che MATCH_NUMBER() è ugualmente escluso da R020 dallo standard (19075-5 §6.3.3 (6) e 19075-5 §6.9 (1)) — fa parte esclusivamente della superficie R010, e la sua assenza qui è anch'essa conformità e non una funzionalità mancante.

Il terzo è un insieme di proibizioni strutturali che lo standard impone su R020 (19075-5 §6.17): un row pattern recognition non può essere annidato all'interno di un altro row pattern recognition; MEASURES e DEFINE non possono contenere riferimenti esterni; le subquery interne a MEASURES o DEFINE non possono referenziare variabili di pattern; e RPR non può essere utilizzato all'interno di una query ricorsiva.

Il quarto è che MATCH_RECOGNIZE stesso — la feature R010, la superficie a clausola di tabella dello stesso meccanismo — è fuori ambito per questo patch. Se PostgreSQL aggiungerà alla fine R010 sarà una questione per una serie futura, non un parametro di valutazione di questa.

§2. Esempi — come funziona effettivamente

Gli esempi in questa sezione si costruiscono in modo incrementale. Si parte dalla ragione concettuale per cui il row-pattern matching è genuinamente diverso dal matching di pattern su stringhe, si introducono poi le quattro funzioni di navigazione che rendono interessanti le condizioni DEFINE e infine si percorrono tre tracce end-to-end: un singolo match (movimento dell'NFA), l'assorbimento del contesto nel caso semplice e il caso in cui l'assorbimento diventa insicuro.

Il meccanismo interno che rende economica la navigazione — lo scambio di tupla a 1 slot — appartiene alla progettazione dell'executor ed è trattato nella sezione successiva, non qui.

2.1 Perché i row pattern differiscono dai pattern testuali

Un'espressione regolare testuale opera su un flusso di caratteri, e in ogni posizione c'è esattamente un simbolo da considerare. La domanda a runtime — "il simbolo corrente è uguale a 'A'?" — ha un'unica risposta sì/no. Gli automi a backtracking sfruttano questo fatto: al più un ramo sopravvive per carattere, e il costo dell'ambiguità si paga rileggendo l'input.

Un row pattern è diverso in modo fondamentale. Una riga non è un singolo simbolo; è una tupla di colonne valutata rispetto a un insieme di predicati booleani, le condizioni DEFINE. Due predicati possono essere veri contemporaneamente sulla stessa riga, e nulla nello standard impone che siano mutuamente esclusivi. Si consideri:

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

Una riga con price = 150, volume = 2000 soddisfa sia A sia B ma non C. Il matcher di pattern non può ridurre questa situazione a un singolo stato — due variabili di pattern sono attive e qualsiasi elemento del pattern che nomini una delle due può avanzare. L'NFA deve quindi mantenere più stati simultanei per ogni riga di partizione, non uno solo.

Questa singola osservazione determina il resto dell'architettura. Lo stato di esecuzione è una lista di contesti, ogni contesto è una lista di stati, e a ogni riga il runtime chiede a ciascuno stato: "date le variabili vere qui, dove posso andare?" I fork che ne derivano sono il motivo per cui il runtime necessita di diversi livelli di pruning — deduplicazione di stato all'interno di un contesto, assorbimento tra contesti e le altre regole esaminate in §3.6 — senza i quali il numero di stati e contesti attivi cresce con la partizione e il pattern matching diventa super-lineare.

2.2 Funzioni di navigazione

Le condizioni DEFINE che si riferiscono solo alla riga corrente sono limitate; quasi ogni pattern interessante necessita di confrontare la riga corrente con le sue vicine o con righe già accettate in precedenza nel match. Lo standard fornisce quattro funzioni di navigazione per questo scopo, e il patch le implementa tutte.

PREV(expr [, n])

La riga n righe prima della riga corrente (default n = 1). Utilizzata per confronti del tipo "oggi vs. ieri".

NEXT(expr [, n])

La riga n righe dopo la riga corrente. Look-ahead in avanti; raro nella forma a finestra poiché la finestra è monotona.

FIRST(expr [, n])

L'n-esima riga associata del match corrente, contando dall'inizio. "Confronta con la riga che ha avviato questo match."

LAST(expr [, n])

L'n-esima riga associata più recente. "Confronta con la riga associata più recente."

Le quattro primitive si compongono: PREV e NEXT possono racchiudere una chiamata a FIRST o LAST, dando luogo a quattro forme composte la cui semantica è "vai a una riga relativa al match, poi spostati di una distanza fissa." Questo è ciò che consente a un'espressione DEFINE di leggere, ad esempio, la riga immediatamente precedente l'inizio del match.

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

Si spostano m righe indietro dall'n-esima riga del match (default m = 1). "Quale era il valore appena prima che iniziasse questo match?"

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

Si spostano m righe in avanti dall'n-esima riga del match. Raggiunge punti più interni del match senza dipendere dalla riga corrente.

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

Si spostano m righe indietro dall'n-esima riga associata più recente. "Confronta con una riga poco prima del match più recente."

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

Si spostano m righe in avanti dall'n-esima riga associata più recente.

Vale la pena fare qui due osservazioni pratiche. Primo, la navigazione può essere composta: PREV(FIRST(price)) legge la riga immediatamente precedente l'inizio del match, e il patch lo supporta. Secondo, la navigazione ha conseguenze sulle ottimizzazioni dell'executor. PREV e NEXT sono relative alla riga corrente e sono sempre sicure; FIRST e le varianti con offset di LAST sono relative ai confini del match, il che interagisce con l'assorbimento del contesto e costringe il planner a mantenere attivi alcuni contesti che altrimenti scarterebbe. Il meccanismo dietro tale interazione è oggetto di §2.6.

2.3 Esempio pratico 1 — movimento dell'NFA

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

Il pattern si appiattisce in quattro elementi:

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

Per la serie di prezzi 100, 110, 120, 115, 108, 130:

Il punto chiave: alla riga 3, la riga soddisfa sia START (sempre vero) sia DOWN, ma l'unico stato sopravvissuto alla riga 2 è sul ramo di uscita verso DOWN, perciò viene presa solo la transizione UP → DOWN. La natura multi-stato di §2.1 è visibile come fan-out a ogni match di UP (lo stato potrebbe restare a UP+ oppure avanzare verso DOWN+). La preferenza greedy è "ripeti prima di uscire", per cui con dati sufficienti i rami in loop estenderebbero ulteriormente il match; qui il DOWN in loop muore alla riga 5 (130 ≮ 108), e il candidato FIN precedente (righe 0–4) — prodotto quando DOWN è uscito alla riga 4 — viene finalizzato come match.

Il risultato della query discende direttamente da questa traccia. Nella semantica RPR, le funzioni finestra first_value(price) e last_value(price) vengono valutate solo sulla riga che ha avviato il match — ogni altra riga del match produce NULL per queste funzioni finestra, poiché il suo frame ridotto è vuoto. L'output per i nostri dati appare quindi come la tabella che il poster mostra nel suo pannello in alto a destra:

La riga 0 è l'inizio del match, perciò il suo frame copre le righe 0–4 e le funzioni finestra riportano il prezzo di apertura della V ($100) e il prezzo minimo ($108). Le righe 1–4 sono interne al match ma non ne sono l'inizio, perciò ricevono NULL. La riga 5 (prezzo $130) è esterna a qualsiasi match e riceve anch'essa NULL.

2.4 Esempio pratico 2 — alternativa e ordine lessicale

La forma (A | B) offre al matcher una scelta: in qualsiasi riga, le due alternative vengono testate indipendentemente, e un qualsiasi numero di esse può corrispondere. È qui che la natura multi-stato di §2.1 diventa visibile all'interno di un singolo contesto — non tra contesti (quello è l'assorbimento), bensì lungo rami paralleli che l'executor esplora in lockstep.

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

Si immagini una riga in cui il prezzo è salito e ha superato $100 — sia UP sia HIGH sono veri. Ciascuna alternativa genera il proprio stato: uno percorre il ramo UP, l'altro il ramo HIGH. Procedono in parallelo finché DONE non li risolve.

Entrambi i rami producono un match della stessa lunghezza sulle stesse righe, lasciando il matcher con due percorsi candidati — uno etichettato UP, DONE e uno etichettato HIGH, DONE. Lo standard risolve la situazione con l'ordine lessicale: tra le alternative scritte in (UP | HIGH), vince quella scritta per prima, indipendentemente dalla lunghezza del match. Poiché UP compare prima di HIGH, il percorso sopravvissuto è UP, DONE.

L'ordine lessicale è ciò che rende CLASSIFIER() ben definito quando verrà eventualmente implementato — consente al runtime di dire all'utente "questa riga è associata a UP, non a HIGH" anche quando entrambi i predicati sono veri. L'ordine lessicale è la regola primaria per l'alternativa: un ramo lessicalmente precedente vince su uno lessicalmente successivo anche se quest'ultimo produrrebbe un match più lungo, e un ramo lessicalmente successivo (eventualmente più corto) può comunque vincere se ogni ramo lessicalmente precedente muore prima di raggiungere FIN. La lunghezza greedy si decide all'interno di un singolo quantificatore — date due completazioni dello stesso ramo dell'alternativa, il quantificatore greedy preferisce più iterazioni.

2.5 Esempio pratico 3 — assorbimento del contesto (stesso destino)

Il pattern più semplice che esibisce assorbimento è PATTERN (A+) con DEFINE A AS TRUE. Ogni riga corrisponde ad A, e lo standard richiede che il matcher consideri ogni riga come possibile inizio di match. In modo ingenuo, ciò significa N contesti per una partizione di N righe. Si prenda una partizione di cinque righe (dati arbitrari — il predicato è costantemente vero):

La memoria passa da O(n) a O(1). La regola di assorbimento che giustifica lo scarto è semplice quando il quantificatore è illimitato:

Il pannello in basso a sinistra del poster ("① Context Absorption") è esattamente questa regola visualizzata su cinque righe.

Nella regola si nasconde un punto sottile ma importante: lo scarto è sicuro perché il predicato A AS TRUE valuta lo stesso valore in ogni riga, indipendentemente dal contesto che lo richiede. Lo stesso vale per qualsiasi predicato che riferisca solo la riga corrente o un offset fisso da essa — incluso PREV. L'esempio successivo passa a una settimana concreta di prezzi, usando un predicato basato su PREV, e §2.6 riutilizzerà esattamente quella settimana per rendere evidente la simmetria tra assorbimento sicuro e non sicuro:

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

Si prenda la settimana borsistica $100, $108, $112, $116, $110 da lunedì a venerdì — quattro rialzi seguiti da un brusco calo. Si supponga che C1 inizi martedì (il primo giorno in cui RISE corrisponde: $108 > $100), e che l'executor speculativamente tracci anche C2 partendo da mercoledì. La condizione RISE di ogni riga confronta il prezzo della riga con il suo predecessore immediato — un fatto a livello di partizione, non a livello di contesto — pertanto i due contesti sono costretti a calcolare lo stesso booleano in ogni riga che condividono:

Il quadro si rompe nell'istante in cui il predicato inizia a dipendere dai confini di ciascun contesto — ed è di questo che tratta §2.6.

2.6 Esempio pratico 4 — quando l'assorbimento diventa non sicuro

Si supponga che un analista voglia individuare giorni di borsa consecutivi in cui un titolo si è mantenuto entro dieci dollari rispetto al giorno in cui la sequenza è iniziata — una sorta di finestra di consolidamento. Il pattern e DEFINE appaiono così:

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

La condizione ora confronta il prezzo della riga corrente con il prezzo all'inizio della sequenza corrente. Due sequenze iniziate in giorni diversi hanno valori di FIRST(price) diversi, quindi due stati sullo stesso elemento del pattern e con lo stesso conteggio non sono più intercambiabili: i loro futuri dipendono dal confine che l'assorbimento stava per scartare.

Si prenda la stessa identica settimana di §2.5 — $100, $108, $112, $116, $110 da lunedì a venerdì. Il runtime mantiene di nuovo due sequenze candidate attive contemporaneamente: C1 iniziata lunedì, C2 iniziata martedì (ogni riga è un potenziale inizio di sequenza sotto STABLE+).

Sotto assorbimento, C2 sarebbe stato fuso in C1 martedì — il contesto fuso conserva una sola soglia, quindi la vista distinta di C2 (soglia $118, la sequenza di quattro giorni che termina solo sabato) non è più recuperabile dallo stato interno. C2 deve restare attivo perché è un candidato di match indipendente di cui il runtime potrebbe ancora aver bisogno: una volta che il match di C1 termina mercoledì, il tentativo successivo deve ripartire da un C2 ancora attivo piuttosto che ricominciare da capo. Ogni volta che un predicato DEFINE porta dipendenza dall'inizio del match, il planner disabilita quindi preventivamente l'assorbimento.

(Quando il match del contesto principale riesce, i contesti iniziati all'interno del suo span accettato — con la modalità predefinita AFTER MATCH SKIP PAST LAST ROW — vengono semplicemente scartati; sono mantenuti attivi solo affinché il runtime abbia qualcosa su cui ripiegare se il match principale fallisce.)

La tabella delle dipendenze nel pannello in basso a destra del poster ("② Navigation") riassume quali forme di navigazione creano dipendenza dall'inizio del match:

I due esempi in §2.5 e §2.6 si riducono a un'unica regola. Lo stesso destino è ciò che rende sicuro l'assorbimento: se ogni contesto sullo stesso elemento del pattern calcolerà la stessa risposta a ogni predicato futuro, è necessario mantenere solo il più vecchio. Destini diversi rendono l'assorbimento non sicuro: non appena i predicati si diramano su stato privato del contesto — che è esattamente ciò che fanno FIRST e LAST con offset — ogni contesto attivo rappresenta un futuro che nessun altro contesto può recuperare, e scartarne uno rischia di produrre una risposta errata.

Il planner rileva questa distinzione in fase di compilazione e decide per contesto se l'assorbimento si applica. È anche per questo che il benchmark del poster nel pannello ③ rimane lineare sia nei casi di successo sia nei casi di fallimento: quando l'assorbimento è sicuro il runtime collassa i contesti, e quando non lo è, il planner accetta il costo multi-contesto piuttosto che rischiare una risposta errata.

I numeri del benchmark sul poster mostrano lo stesso algoritmo applicato su larga scala. Sul pattern di successo (A+ B+ C+ D), sia PostgreSQL sia Trino scalano O(n) una volta confermato un match, e il vantaggio di PostgreSQL — circa 16× a 33× — è in gran parte dovuto al gap della JVM.

Sul pattern di fallimento (A+ B+ C+ E), Trino non ha assorbimento e degrada a O(n²) inseguendo ogni potenziale inizio di match; a 100.000 righe impiega oltre cinque ore, mentre PostgreSQL termina in 92 ms, con uno speed-up di circa 217.000×.

Tale divario non è una rifinitura ingegneristica — è esattamente la distinzione stesso destino / destini diversi di §2.5 e §2.6, applicata a ogni riga di ogni potenziale inizio di match nella partizione.

2.7 Esempio pratico 5 — quando SKIP disabilita l'assorbimento

L'esempio precedente rompeva l'assorbimento dal lato dei dati: FIRST in DEFINE faceva sì che ogni contesto valutasse i predicati in modo diverso. L'assorbimento può rompersi anche dal lato dell'output, e la clausola AFTER MATCH SKIP è ciò che lo controlla.

Si consideri il pattern PATTERN (A+) con DEFINE A AS TRUE su cinque righe che corrispondono tutte ad A. Con la modalità predefinita AFTER MATCH SKIP PAST LAST ROW, il matcher trova il match più lungo a partire dalla riga più precoce e poi salta oltre; qualsiasi contesto iniziato all'interno di quel match viene implicitamente scartato come ridondante — esattamente la situazione che l'assorbimento è progettato per gestire. L'output è un singolo match, righe 0–4, e il runtime necessita di un solo contesto attivo.

Si commuti la modalità di skip a AFTER MATCH SKIP TO NEXT ROW e il contratto cambia:

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

Ora ogni potenziale posizione di partenza deve essere riportata separatamente, anche quando i match si sovrappongono. Per le stesse cinque righe il runtime è tenuto a emettere cinque match: righe 0–4, 1–4, 2–4, 3–4 e 4–4. Nessuno di questi può essere sostituito da uno "più lungo che inizia prima", perché lo standard afferma che l'utente li vuole tutti.

Si noti che il predicato non è cambiato. A AS TRUE valuta nello stesso modo in ogni riga, indipendentemente dal contesto che lo richiede, quindi la condizione di stesso destino di §2.5 è ancora soddisfatta. Ciò che cambia è il requisito di output: anche contesti con futuri identici devono coesistere perché corrispondono a righe distinte del risultato. Il planner disabilita pertanto l'assorbimento del contesto ogni volta che AFTER MATCH SKIP TO NEXT ROW è in vigore, indipendentemente dalla clausola DEFINE.

Affiancando §2.6 e §2.7 si ottiene il quadro completo di quando l'assorbimento fallisce:

Una sola di queste condizioni è sufficiente a disabilitare l'assorbimento per i contesti interessati. Quando nessuna è in vigore — la modalità predefinita AFTER MATCH SKIP PAST LAST ROW con condizioni DEFINE che usano solo PREV, NEXT o LAST nudo — il runtime si riduce a un singolo contesto per posizione del pattern e rimane lineare per tutto il percorso.

§3. Progettazione — dal parser all'executor

Row Pattern Recognition è implementato come tre stadi che si scambiano il lavoro attraverso forme intermedie ben definite. Il parser trasforma il testo SQL in un albero di pattern e in una lista di predicati DEFINE; il planner compila l'albero in un array piatto di elementi di pattern e decide quali tra essi possono partecipare all'assorbimento del contesto; l'executor esegue l'array sulla partizione riga per riga in un ciclo a tre fasi. Ogni stadio ha la propria forma di dati, e gran parte dell'ingegnosità di progetto è ai confini: un NFA piatto che entra in cache, un modello di navigazione che riusa un singolo slot di tupla invece di materializzarne uno per riferimento, e una regola di assorbimento che trasforma la memoria O(n²) in O(n).

testo SQL
  │
  │  stadio parser
  ▼    valida il frame
       costruisce l'albero di pattern
       type-check del DEFINE

albero di pattern + lista DEFINE
  │
  │  stadio planner
  ▼    ottimizza l'albero
       compila in array NFA piatto
       decide l'assorbibilità

NFA piatto + flag di assorbimento
  │
  │  stadio executor
  ▼    motore per riga:
       Match → Absorb → Advance

risultato del match:
  riga di inizio, lunghezza, successo/fallimento

Le sezioni seguenti percorrono questa pipeline. §3.1 copre il parser e la forma dell'albero di pattern; §3.2 copre la compilazione che trasforma l'albero in NFA piatto; §3.3 copre il modello di navigazione usato dai predicati DEFINE per esaminare righe vicine; §3.4 copre la gestione dei confini di match — le regole SKIP, INITIAL e di frame delimitato che fissano dove un match inizia e termina; §3.5 è il motore per riga a tre fasi; §3.6 raccoglie tutti i meccanismi di pruning che mantengono limitato lo spazio degli stati; e §3.7 esamina ciò che l'implementazione espone nell'output di EXPLAIN.

3.1 Parser — costruzione dell'albero di pattern

Il parser riconosce il pattern recognition dalla presenza di una clausola PATTERN all'interno di una specifica di finestra. Il suo primo compito è la validazione del frame, poiché RPR impone vincoli che le normali query con finestra non hanno: la modalità del frame deve essere ROWS (non RANGE o GROUPS), il confine iniziale deve essere CURRENT ROW e le opzioni EXCLUDE sono proibite. Si tratta di controlli di conformità, non di ottimizzazioni — la nozione di frame in RPR è lo span del match, e lo standard non contempla di riempirlo con altro che le righe matched.

Una volta che il frame supera la validazione, il parser trasforma la clausola PATTERN in un albero costruito da quattro tipi di nodo — un riferimento di variabile, una sequenza (concatenazione), un'alternativa e un gruppo (sotto-pattern tra parentesi). Ogni nodo porta il quantificatore come tre numeri — un limite inferiore, un limite superiore (eventualmente infinito) e un flag per il matching reluctant:

Ogni predicato DEFINE viene quindi sottoposto a type-check rispetto alle colonne della partizione e coerciato in un'espressione booleana. Due cose pratiche avvengono in questa fase. Primo, ogni colonna referenziata da un predicato DEFINE viene registrata tra i requisiti di output della query, così il planner propaga tali colonne fino allo stadio executor anche se la query circostante non le seleziona — senza ciò, il runtime non avrebbe nulla su cui valutare. Secondo, le variabili che compaiono nel PATTERN ma mai nel DEFINE sono implicitamente vere: corrispondono a ogni riga.

3.2 Compilazione — dall'AST a un NFA piatto

Il planner trasforma l'albero del parser nella struttura dati che l'executor eseguirà: un array piatto di elementi di pattern indirizzato per indice. La compilazione procede come una pipeline a sei passi:

compile(astTree):
  1. ottimizza l'AST
  2. misura dimensione e profondità
  3. alloca l'array degli elementi
  4. riempie dall'AST
       (assegna i puntatori next/jump)
  5. finalizza — imposta il sentinella FIN
  6. marca gli elementi assorbibili

La forma piatta è scelta per una ragione semplice: l'executor deve attraversare il pattern molte volte per partizione, e un array contiguo indirizzabile per indice è la struttura dati più economica da percorrere. I passi 1 e 6 sono i più interessanti — il passo 1 perché determina quanto sarà grande l'array, e il passo 6 perché decide se l'ottimizzazione di assorbimento di §2.5 verrà attivata.

Ottimizzazione dell'AST

L'ottimizzazione paga due volte: una nel conteggio statico degli elementi dell'array piatto e una in ogni riga elaborata a runtime. Ogni trasformazione riduce lo spazio degli stati che il runtime deve enumerare. L'ottimizzatore applica in successione otto regole di riscrittura finché l'AST non smette di cambiare:

Appiattimento di SEQ

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

Fusione di variabili consecutive

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

Fusione di gruppi consecutivi

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

Fusione di ALT consecutive

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

Assorbimento di prefisso/suffisso

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

Appiattimento e dedup di ALT

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

Moltiplicazione di quantificatori

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

Unwrap del figlio singolo

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

La moltiplicazione di quantificatori è l'unica trasformazione che richiede un controllo di sicurezza: l'ottimizzatore collassa solo in tre casi sicuri — entrambi i quantificatori illimitati ((A+)+ → A+), esterno esatto ((A{2,3}){5} → A{10,15}), oppure il figlio triviale {1,1} ((A){2,5} → A{2,5}). Altre combinazioni possono introdurre gap che la forma piatta perderebbe — ad es., (A{2}){2,3} accetta solo {4, 6}, ma un ingenuo A{4,6} accetterebbe anche 5 — quindi l'ottimizzatore le lascia intatte.

Forma dell'elemento

Ogni elemento dell'array piatto rappresenta una singola posizione nel pattern. Esistono cinque tipologie logiche: un riferimento di variabile (l'unico tipo che consuma una riga); marker di inizio gruppo e fine gruppo, che aprono e chiudono un sotto-pattern tra parentesi; un marker di alternativa, che guida una lista di rami; e un marker di conclusione alla fine del pattern.

Ogni elemento porta inoltre una profondità (il livello di annidamento del gruppo), il quantificatore (conteggi min e max di ripetizione, eventualmente infiniti) e due puntatori di transizione — next, "dove andare dopo aver consumato questo elemento," e jump, "dove saltare" (usato dall'alternativa per concatenare rami, dall'inizio gruppo per bypassare il corpo quando il quantificatore consente zero, e dalla fine gruppo per fare loop sul corpo).

Per PATTERN ((A B)+) l'array compilato appare così:

PATTERN ((A B)+) compiles to:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (apre il gruppo; jump salta
     a FIN quando min = 0)

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

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

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (chiude il gruppo; jump fa loop indietro)

[4] FIN    pattern completo

Il pattern si legge da sinistra a destra tramite next, con jump che gestisce gli archi non lineari. All'indice 3 il jump di END punta indietro all'indice 1, ed è così che il quantificatore esterno illimitato fa loop; all'indice 0 il jump di BEGIN salterebbe oltre END all'indice 4 se il gruppo fosse opzionale. Il runtime non deve mai costruire un grafo a runtime — segue semplicemente questi due puntatori mentre percorre l'array.

Attributi per elemento

Oltre alla forma, ogni elemento porta quattro attributi logici che indirizzano il comportamento del runtime in quella posizione:

Reluctant

Inverte l'ordine di espansione del quantificatore. I quantificatori greedy provano "ripeti" prima di "esci"; i quantificatori reluctant provano "esci" per primo. Portato dalla variabile per A+?; portato dal BEGIN e END del gruppo per ((…)+?).

Empty-loopable

Impostato sui group end il cui corpo è nullable ((A?)*, (A? B?)+, (A | B*)). Indica al runtime di aggiungere un'uscita fast-forward accanto al normale loop-back, così che la guard di ciclo non uccida match legittimi in gruppi che possono produrre iterazioni vuote.

In-absorbable-region

Marca ogni elemento che si trova all'interno di una regione assorbibile — usato dal runtime per tracciare se lo stato corrente è ancora in territorio sicuro.

Absorption-comparison-point

Marca l'elemento specifico in cui devono essere eseguiti i confronti di assorbimento. Per un semplice A+ ricade sulla variabile; per un gruppo illimitato come (A B)+ ricade sul solo group end.

La distinzione tra "in-region" e "comparison-point" è importante perché l'assorbimento ha senso solo nei punti in cui le iterazioni si chiudono. All'interno del corpo di (A B)+, il runtime è a metà iterazione e il conteggio non ha ancora raggiunto il suo valore finale per quel giro; confrontare qui significherebbe confrontare valori incomparabili. Lo stato deve raggiungere il group end prima che il runtime possa decidere. Il primo attributo dice quindi "sei ancora in territorio assorbibile"; il secondo dice "hai raggiunto il punto di confronto — vai a controllare ora."

Analisi di assorbibilità

Il passo 6 della compilazione è ciò che fornisce alla regola di "stesso destino" di §2.5 il suo testimone in fase di compilazione. La decisione è stratificata:

isAbsorbable(query):
  se modalità SKIP != SKIP PAST LAST ROW
      → ritorna false
  se fine del frame != UNBOUNDED FOLLOWING
      → ritorna false
  se qualche DEFINE dipende da match_start
      → ritorna false
  percorre l'AST e marca
  gli elementi che soddisfano
  un caso strutturale

I primi tre controlli sono a livello di query: corrispondono esattamente alle condizioni di §2.7 (lato output: modalità SKIP), del frame delimitato (il confine rompe la monotonia) e di §2.6 (lato dati: FIRST o LAST con offset in DEFINE). Quando uno di essi fallisce, l'analisi non imposta alcun flag e l'assorbimento è disabilitato a livello di query. Quando tutti passano, la visita dell'AST ammette tre forme strutturali:

Caso 1 — variabile illimitata semplice

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

Ogni iterazione è esattamente una riga. Il conteggio di un contesto precedente è sempre ≥ a quello di uno successivo in ogni posizione condivisa.

Caso 2 — gruppo a lunghezza fissa, esterno illimitato

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

Ogni figlio ha min == max, quindi il corpo è semanticamente equivalente alla sua forma srotolata {1,1} — (A B{2})+ si comporta come (A B B)+. Ogni iterazione consuma un numero fisso di righe; la dominanza dei conteggi vale ancora.

Caso 3 — gruppo il cui corpo inizia con una variabile illimitata

(A+ B)+

La variabile illimitata iniziale è essa stessa assorbibile (Caso 1) e protegge i contesti precedenti. L'assorbimento si interrompe non appena lo stato supera A — il resto del corpo non ha garanzia di monotonia, quindi i flag sono impostati solo su A.

I casi strutturali non coperti da queste tre forme sono altrettanto istruttivi. A B+ non può essere assorbito dalla regola attuale perché l'A iniziale consuma una riga prima che inizi la parte illimitata, quindi contesti distanti una riga sono in posizioni diverse all'interno del corpo illimitato. (Un'estensione successiva di "PREFIX absorption" che gestisce prefissi a lunghezza fissa tramite un percorso shadow è stata progettata e pianificata per un patch separato.) I quantificatori reluctant come A+? sono esclusi per costruzione: la regola di assorbimento presuppone la semantica greedy, in cui i match più lunghi sussumono quelli più brevi, e il matching reluctant inverte tale direzione.

Il risultato è una decisione per elemento anziché per pattern. Un singolo piano di query può avere l'assorbimento abilitato per l'A+ iniziale di pattern come (A+ B+ C) o (A+ B+)+ — quest'ultimo è semplicemente il Caso 3 applicato al suo elemento iniziale — e disabilitato per tutto ciò che segue; il runtime consulta semplicemente l'attributo comparison-point sull'elemento dello stato corrente ogni volta che valuta un passaggio di assorbimento. Una volta che uno stato entra in una regione non assorbibile, l'assorbimento è permanentemente disattivato per quello stato — esattamente ciò che §2.5 e §2.6 richiedono a livello algoritmico.

3.3 Navigazione — lo scambio di tupla a 1 slot

Le espressioni DEFINE sono ordinarie espressioni SQL valutate su una riga, ma possono includere PREV, NEXT, FIRST o LAST — riferimenti che puntano a righe diverse. Le righe stesse sono già bufferizzate nel tuplestore della finestra; ciò che l'executor deve ancora gestire è lo slot di tupla da cui legge il meccanismo di valutazione delle espressioni SQL, poiché i riferimenti a colonna all'interno dell'espressione sono legati a uno slot in fase di pianificazione. L'implementazione riusa un singolo slot di navigazione per ogni chiamata di navigazione: lo slot viene scambiato prima di valutare l'espressione interna e ripristinato dopo, così che il resto del meccanismo di valutazione SQL non se ne accorga mai.

Il modello visto dall'executor è piccolo: esiste uno slot della riga corrente che contiene la riga su cui viene valutata l'espressione DEFINE, e uno slot di navigazione che il runtime può temporaneamente reindirizzare a una riga diversa. Attorno a ogni chiamata di navigazione il runtime imposta lo slot di navigazione, valuta l'espressione interna come se stesse leggendo la riga corrente, quindi ripristina la riga originale. Pseudocodice:

eval_navigation(call):
  targetPos = compute_target_position(call)
  se targetPos è fuori dal suo intervallo valido:
      ritorna NULL

  salva current_row_slot
  recupera la riga in targetPos
    in current_row_slot
  result = eval_inner_expression()
  ripristina current_row_slot
  ritorna result

Il trucco è che c'è esattamente uno slot da salvare e ripristinare. L'espressione interna — qualunque essa sia, inclusa aritmetica, chiamate di funzione o altri riferimenti a colonna — viene eseguita sullo slot scambiato utilizzando lo stesso percorso di valutazione che userebbe per la riga corrente. Nessun valutatore alternativo, nessuno shadow slot, nessuna copia di tupla.

La navigazione composta viene appiattita in fase di parsing in modo che lo scambio avvenga comunque una sola volta. PREV(FIRST(price)) viene riconosciuto come una navigazione a due passi — "vai alla prima riga associata, poi spostati una riga indietro" — e memorizzato come una singola chiamata di navigazione con tipo composto. Il runtime calcola la posizione target in due fasi ma esegue un solo scambio di slot per recuperare la riga finale:

compute_target_position(call):

  # relativo alla riga corrente
  PREV(n):
      ritorna currentPos − n
  NEXT(n):
      ritorna currentPos + n

  # relativo al match
  FIRST(n):
      ritorna matchStart + n
  LAST(n):
      ritorna lastMatchedRow − n

  # composto: rel-match, poi step
  PREV(FIRST(n), m):
      ritorna (matchStart + n) − m
  NEXT(FIRST(n), m):
      ritorna (matchStart + n) + m
  PREV(LAST(n), m):
      ritorna (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      ritorna (lastMatchedRow − n) + m

  valida rispetto all'intervallo appropriato
  (intervallo del match per FIRST/LAST interno,
   intervallo della partizione per lo step esterno)

Una cache di posizione cortocircuita il fetch del tuplestore quando più chiamate di navigazione nello stesso DEFINE puntano alla stessa riga — frequente in espressioni come price > PREV(price) AND volume > PREV(volume), dove entrambe le chiamate si risolvono nella riga precedente. La cache memorizza solo "ultima posizione recuperata", e lo scambio resta una singola operazione.

La classificazione delle chiamate di navigazione è il contributo del planner alla decisione di assorbimento. Il planner percorre ogni espressione DEFINE e ordina ciascuna variabile in uno di due bucket, a seconda che tutti i contesti calcolino lo stesso booleano sulla stessa riga, oppure che ciascun contesto calcoli il proprio. Il bucket determina due cose a runtime: con quale frequenza la variabile viene valutata (una volta condivisa, o una volta per ogni contesto interessato — §3.5 Fase 1), e se lo stato circostante è idoneo all'assorbimento del contesto (§2.5 vs §2.6).

La classificazione viene eseguita in fase di pianificazione e memorizzata accanto a ciascuna variabile DEFINE, quindi il runtime non spende tempo a decidere — legge semplicemente il bucket per ogni variabile mentre elabora una riga.

Budget di retention

La navigazione raggiunge righe che il meccanismo della funzione finestra avrebbe altrimenti già superato in streaming. Per mantenere disponibili tali righe, l'executor è costruito sopra un tuplestore che conserva una finestra scorrevole di righe recenti; la domanda è quanto ampia debba essere tale finestra. Il patch lo decide in fase di compilazione, a partire da due offset complementari:

Budget di lookback

Quanto indietro dalla riga corrente potrebbe arrivare una qualsiasi chiamata DEFINE.

Contribuenti: PREV, LAST con offset, PREV(LAST(...)), NEXT(LAST(...))

Budget di lookahead-from-start

Quanto in avanti (o indietro, quando negativo) dall'inizio del match del contesto attivo più vecchio una qualsiasi chiamata DEFINE potrebbe arrivare.

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

A runtime, il trim mark del tuplestore è impostato sulla più precoce tra due posizioni — riga corrente meno il budget di lookback, e inizio match del contesto attivo più vecchio più il budget di lookahead. Qualsiasi cosa prima di tale mark non può essere raggiunta da alcuna chiamata di navigazione in alcun contesto attivo, e il tuplestore può scartarla. I due contatori Nav Mark riportati da EXPLAIN (§3.7) — Lookback e Lookahead — sono i picchi misurati dei due budget, la profondità massima che l'executor ha dovuto raggiungere in ciascuna direzione nel corso della query.

3.4 Confini del match — SKIP, INITIAL e frame delimitato

Un match riuscito viene registrato come un piccolo bundle di valori: un flag di validità, un flag di successo/fallimento, la riga in cui il match inizia e il numero di righe consumate. Quando il flag di validità è impostato, le query successive all'executor — "questa riga è all'interno di un match?" — possono rispondere in O(1) ispezionando il bundle. Una lunghezza pari a zero è un risultato reale, non un errore: rappresenta un pattern che ha avuto match senza consumare alcuna riga, e l'executor deve distinguerlo da "nessun match è stato ancora tentato in questa posizione".

La clausola AFTER MATCH SKIP decide dove inizia il successivo tentativo di match. AFTER MATCH SKIP PAST LAST ROW si sposta sulla riga successiva alla fine del match, producendo l'output non sovrapposto desiderato dalla maggior parte delle query e abilitando l'ottimizzazione di assorbimento.

AFTER MATCH SKIP TO NEXT ROW si sposta solo sulla riga successiva all'inizio del match, consentendo match sovrapposti; il planner disabilita pertanto l'assorbimento per l'intero piano di query quando questa modalità è in vigore.

I due target di skip che lo standard definisce inoltre — AFTER MATCH SKIP TO FIRST var e AFTER MATCH SKIP TO LAST var — dipendono dalla storia per match che questo patch non conserva. Non sono affatto presenti nella grammatica, quindi il parser solleva un errore di sintassi generico se uno dei due viene fornito.

Lo stesso vale per SEEK, l'alternativa specificata dallo standard ad INITIAL. Con SEEK, un tentativo di match che parte alla riga R può riuscire in qualsiasi riga da R fino alla fine del frame, non solo in R stessa. Il patch implementa solo INITIAL: ogni potenziale match è ancorato a una riga specifica. Il parser solleva un errore se SEEK viene richiesto. I frame delimitati ricevono un trattamento proprio — quando l'utente scrive ROWS BETWEEN CURRENT ROW AND N FOLLOWING invece di UNBOUNDED FOLLOWING, l'executor cortocircuita qualsiasi contesto il cui match abbia raggiunto il confine forzando un mismatch, e l'assorbimento viene disabilitato perché il confine rompe l'ipotesi di monotonia su cui l'assorbimento si basa.

3.5 Il motore per riga a tre fasi

Il driver per riga dell'executor viene invocato dal meccanismo della funzione finestra circostante ogni volta che deve sapere se una data riga appartiene a un frame matched. Il driver trova o crea il contesto per la posizione iniziale corrente, valuta ogni predicato DEFINE una volta sulla riga corrente per produrre un array booleano per variabile, quindi fa avanzare l'NFA di una riga. Il passo di avanzamento è composto da tre fasi in ordine fisso — Match, Absorb, Advance — incapsulate nello stesso loop esterno:

processRow(currentPos):

  # Fase 1 — MATCH (convergenza)
  per ogni contesto:
      se il contesto eccede il frame delimitato:
          forza mismatch (finalizza in anticipo)
          continua
      se matchStartRow differisce dalla
         posizione di valutazione condivisa:
          rivaluta le variabili DEFINE dipendenti
          dall'inizio del match (§3.3)
      match(context, varMatched)

  # Fase 2 — ABSORB
  se il pattern è assorbibile:
      aggiorna i flag di ogni contesto
      absorb_contexts()

  # Fase 3 — ADVANCE (divergenza)
  per ogni contesto:
      advance(context, currentPos)

L'ordine non è una scelta stilistica. Match deve essere eseguito per primo perché l'assorbimento confronta conteggi post-match; eseguire Absorb prima di Match comporterebbe confrontare stati prossimi alla morte. Advance deve essere eseguito per ultimo perché è l'unica fase che crea nuovi stati — espande ogni stato superstite attraverso transizioni epsilon finché ciascuno raggiunge una variabile in attesa della riga successiva. Eseguire Absorb dopo Advance significherebbe confrontare successori divergenti, perdendo il punto in cui gli stati sono più nettamente confrontabili.

Fase 1 — Match

Match è una fase di "convergenza": gli stati o sopravvivono con un conteggio incrementato, o muoiono. Un punto sottile è che, per le variabili in una regione assorbibile, Match esegue anche una piccola quantità di avanzamento, così che Absorb possa confrontare in modo pulito. La condizione di cover scatta solo nel punto di confronto assorbibile — il END del gruppo illimitato — quindi gli stati che hanno appena fatto match su variabili a metà iterazione (come B all'interno di (A B)+) devono essere portati fino a quel punto di confronto durante lo stesso Match; altrimenti Absorb non trova nulla di idoneo da confrontare e l'ottimizzazione non si attiva.

match(context, varMatched):
  per ogni stato nel contesto:
      elem = pattern[state.elemIdx]
      se elem non è una variabile:
          continua   # advance lo gestisce

      se non varMatched[elem.varId]:
          scarta lo stato   # ramo morto
          continua

      state.counts[elem.depth] += 1

      # Avanzamento inline per fare in
      # modo che la fase successiva possa
      # confrontare sull'elemento punto di
      # confronto anziché a metà iterazione.
      se elem è in-region ma non
         il punto di confronto,
         e ha raggiunto il suo conteggio max,
         e elem.next è un group end:

          percorre la catena END:
            incrementa il conteggio del gruppo esterno
            avanza state.elemIdx a END
            continua mentre è ancora in-region,
              deve uscire, e next è END
          (si ferma al punto di confronto
           o su un elemento ancora ripetibile)

Il percorso della catena END è ciò che rende assorbibili i gruppi annidati a lunghezza fissa. In ((A B){2})+, quando B raggiunge il suo max (B è {1,1}), il conteggio del gruppo interno deve incrementarsi; se anche tale conteggio raggiunge il suo max — chiudendo il {2} interno — anche il conteggio del gruppo esterno deve incrementarsi, e così via, finché lo stato non atterra sul punto di assorbimento più esterno — il END del gruppo esterno illimitato (il +). Eseguire questo lavoro in Match consente ad Absorb di confrontare contesti che hanno già consolidato i propri conteggi post-iterazione.

Fase 2 — Absorb

Il passaggio di absorb percorre i contesti dal più nuovo (coda) al più vecchio (testa). Per ogni contesto in corso che sia interamente assorbibile, scandisce all'indietro alla ricerca di un contesto più vecchio in corso che lo copra e libera il più nuovo se trovato. Poiché i contesti sono mantenuti in ordine di creazione e ogni riga crea al massimo un contesto, "più nuovo" e "più vecchio" significano davvero "iniziato dopo" e "iniziato prima".

absorb_contexts():
  per ctx dalla coda all'indietro:
      se ctx è terminato
         o ha qualche stato non assorbibile:
          salta
      per older da ctx.prev all'indietro:
          se older è terminato
             o non ha stati assorbibili:
              salta
          se covered(older, ctx):
              free(ctx)
              registra lunghezza di assorbimento
              break

covered(older, newer):
  per ogni stato in newer:
      elem = pattern[state.elemIdx]
      se elem non è il punto di confronto:
          ritorna false
      se nessuno stato in older con:
            stesso elemIdx
            e isAbsorbable
            e older.counts[depth]
                >= newer.counts[depth]:
          ritorna false
  ritorna true

Da ciò seguono due micro-decisioni. La prima è che il check di cover rifiuta immediatamente se qualche stato nel contesto più nuovo si trova altrove rispetto a un punto di confronto — confrontare in punti di non giudizio non costituirebbe un confronto significativo.

La seconda è la coppia di flag asimmetrica su ogni contesto: has-absorbable-state risponde "questo contesto potrebbe assorbirne uno più nuovo?" ed è monotono (può solo passare da true→false man mano che gli stati muoiono), mentre all-states-absorbable risponde "questo contesto potrebbe essere assorbito?" ed è dinamico (torna a true quando uno stato non assorbibile viene rimosso). Entrambi i flag vengono controllati in tempo costante prima ancora che inizi la scansione di cover, quindi l'assorbimento paga il suo costo pieno solo sui contesti che hanno una reale possibilità di essere assorbiti.

Fase 3 — Advance

Advance è la fase di "divergenza": ogni stato sopravvissuto viene espanso attraverso transizioni epsilon finché ogni ramo raggiunge una variabile in attesa della riga successiva o il sentinella FIN. L'espansione è in profondità (DFS), e l'ordine in cui vengono percorsi i rami fratelli è ciò che fa effettivamente entrare in vigore la regola di preferenza dello standard — il ramo lessicalmente primo viene sempre aggiunto per primo, e il passo di deduplicazione all'inserimento dello stato scarta silenziosamente le aggiunte successive equivalenti.

advance(context, currentPos):
  estrae tutti gli stati correnti;
  ricostruisce ctx.states da zero
  per ogni stato in ordine lessicale:
      svuota la bitmap visited-element
      advance_state(state)   # DFS

      # Preferenza: una volta che un DFS
      # raggiunge FIN, gli stati rimanenti
      # sono meno preferiti e possono essere scartati.
      se FIN raggiunto e ci sono stati rimanenti:
          libera il resto
          break

advance_state(state):
  percorre via state.elemIdx,
  ricorre attraverso:
    rami ALT (in ordine),
    BEGIN (entra nel gruppo; più percorso
           opzionale di skip se min = 0),
    END (loop back / exit / fast-forward —
         vedi sotto),
    FIN (registra matchEndRow,
         salva matchedState, e pota
         i contesti successivi entro
         l'intervallo del candidato — vedi sotto),
  fermandosi su ogni variabile incontrata:
      aggiunge lo stato a ctx.states
      (deduplicando per elemIdx + counts)

Registrare uno stato che ha raggiunto FIN fa più che semplicemente segnalare il match candidato. Con AFTER MATCH SKIP PAST LAST ROW, il successivo match riportabile deve iniziare strettamente oltre quello corrente — quindi nel momento in cui un candidato viene registrato, ogni contesto successivo la cui riga di inizio cade entro l'intervallo del candidato viene potato immediatamente, anche se il contesto che ha colpito FIN può continuare a cercare un match più lungo tramite fallback greedy.

Il pruning è sicuro perché, indipendentemente da come termini quella ricerca (un match più lungo sostituisce il candidato, oppure il candidato resta), tutti i contesti potati sono iniziati entro un intervallo oltre il quale il successivo match riportabile deve saltare, e quindi non potrebbero mai produrre un proprio output.

Questo è uno dei due passi di pruning all'arrivo a FIN — l'altro, descritto in precedenza in questa sezione come parte di Advance, scarta gli stati lessicalmente inferiori all'interno dello stesso contesto.

La logica per elemento più delicata risiede nell'handler di END. Quando il conteggio di iterazione di un gruppo è inferiore al limite inferiore, il runtime deve fare loop; quando è pari o superiore al limite superiore, deve uscire; nel mezzo, entrambe le opzioni sono valide e la greediness del quantificatore decide quale tentare per prima:

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

  se count < elem.min:
      loop indietro nel corpo
      se elem è empty-loopable:
          # corpo nullable, vedi §3.2
          clona anche uno stato fast-forward
          che esce dal gruppo
          con count soddisfatto
          (recupera match legittimi che
           la cycle guard altrimenti
           ucciderebbe)

  altrimenti se count >= elem.max:
      azzera i conteggi a questa profondità
      esci via next
      (END→END: incrementa il conteggio
       dell'END esterno)

  altrimenti:
      # min <= count < max: fork
      costruisce uno stato di uscita
      (conteggi a questa profondità azzerati)
      se greedy:
          loop prima, poi esci
          # preferisci più lungo
      altrimenti (reluctant):
          esci prima
          se l'uscita ha raggiunto FIN:
              scarta il loop
              # preferisci più corto
          altrimenti loop dopo

Ogni stato aggiunto a un contesto attraversa un check di deduplicazione che confronta la sua posizione e i suoi conteggi con la lista degli stati esistenti. Poiché Advance elabora i rami in ordine DFS, lo stato del primo ramo di una qualsiasi alternativa atterra per primo — e qualsiasi ramo successivo che produca la stessa posizione e gli stessi conteggi viene respinto all'inserimento. È esattamente ciò che la regola dell'ordine lessicale di §2.4 richiede, implementata al fondo del runtime senza un passaggio separato.

Gruppi empty-loopable

Un caso sottile che il runtime deve disinnescare è il gruppo nullable — un gruppo il cui corpo può corrispondere a zero righe perché ogni figlio del corpo è esso stesso opzionale. Pattern come (A?)*, (A? B?)+ e (A | B*) hanno tutti questa proprietà: a seconda dei dati, il corpo può completare un'iterazione senza consumare alcuna riga. In linea di principio è corretto, ma crea un rischio reale per l'espansione epsilon dell'NFA. Se il corpo produce un match vuoto, l'elemento END fa loop indietro a BEGIN, il corpo produce nuovamente un match vuoto, BEGIN fa loop a END, e così via. Senza qualcosa che lo fermi, il DFS di Advance non terminerebbe mai.

Il runtime lo ferma con una bitmap visited-element (un bit per elemento del pattern), svuotata prima dell'espansione DFS di ogni stato: non appena un elemento viene visitato una seconda volta all'interno della stessa espansione, quel percorso viene abbandonato. La cycle guard è incondizionata ed economica, ma ha un effetto collaterale — può abbandonare anche percorsi che dovrebbero raggiungere il limite inferiore attraverso iterazioni vuote legittime. Si prenda (A?){2,3} senza alcun A che corrisponda nel flusso di righe:

comportamento desiderato:
  iter 1: A? corrisponde a zero righe
          → END, count = 1 (sotto min)
  iter 2: A? corrisponde a zero righe
          → END, count = 2 (raggiunge min)
  esce con un match di lunghezza zero

cosa fa la cycle guard da sola:
  iter 1: A? saltato → END, count = 1
          → loop indietro a BEGIN
  iter 2: BEGIN già visitato
          → il DFS si interrompe
  count non raggiunge mai min
  → il match fallisce (errato)

La correzione è decisa in fase di compilazione e applicata a runtime. Ogni volta che il planner vede un gruppo il cui corpo è nullable, contrassegna l'elemento END di quel gruppo come empty-loopable. A runtime, quando l'handler di END sta per fare loop indietro perché il conteggio di iterazione è ancora sotto il limite inferiore, il tag empty-loop gli dice di clonare uno stato fast-forward aggiuntivo insieme al normale percorso di loop-back:

advance_end (count sotto min):

  percorso primario:
    loop indietro nel corpo
    (lascia la porta aperta a un match
     reale e non vuoto nella prossima
     iterazione)

  se elem è empty-loopable:
    percorso fast-forward:
      azzera il conteggio a questa profondità
      esce dal gruppo via next,
      trattando le rimanenti iterazioni
      richieste come match vuoti

I due percorsi svolgono ruoli complementari. Il loop-back primario è ciò che cattura il caso in cui il corpo ha ancora match reali da produrre in seguito — ad esempio, in (A?){2,3} seguito da dati in cui A corrisponde solo su righe successive, il loop-back è ciò che consente alla seconda e alla terza iterazione di trovare match non vuoti. Il fast-forward è ciò che cattura il caso in cui il corpo non produce mai nulla: bypassa la cycle guard uscendo interamente dal gruppo, dichiarando "le iterazioni rimanenti richieste sono vuote", e consente al match di riuscire con un corpo di lunghezza zero. Entrambi gli stati vengono aggiunti al contesto; vince quello che si estende con successo, e il check di deduplicazione all'inserimento impedisce a uno dei due percorsi di generare più stati del dovuto.

Oltre alla cycle guard, un altro trucco di avvio disambigua gli esiti a zero righe all'inizio di un contesto. Il passo di creazione del contesto in ogni potenziale riga di partenza esegue un initial advance attraverso transizioni epsilon prima che venga consumata qualsiasi riga, usando una posizione una riga prima della partenza effettiva. Qualsiasi percorso che raggiunga il sentinella FIN tramite sole transizioni epsilon — senza consumare una riga — produce quindi una posizione finale inferiore a quella iniziale; quella coordinata di span negativa, combinata con il fatto che FIN sia stato effettivamente raggiunto, codifica la differenza tra un match vuoto (match di lunghezza 0 accettato) e una partenza non corrispondente senza bisogno di un flag separato.

3.6 Come lo spazio degli stati resta limitato

La linearità del runtime non è il risultato di una singola ottimizzazione. È l'effetto cumulativo di un insieme stratificato di regole di pruning, ognuna delle quali cattura una diversa causa di crescita dello spazio degli stati in un diverso punto del ciclo per riga. Alcune sono decise in fase di compilazione e semplicemente consultate a runtime; altre si attivano dinamicamente. Alcune uccidono singoli stati; altre uccidono interi contesti. Le sezioni precedenti hanno introdotto ciascuna di esse nel proprio contesto; la tabella seguente le presenta tutte in un unico quadro.

Predicato fallito Match

Stati di variabile il cui DEFINE è risultato falso sulla riga corrente — rami morti.

Avanzamento inline della catena END Match

Variabili che hanno raggiunto il loro conteggio massimo e altrimenti lascerebbero lo stato a metà iterazione; portate avanti attraverso i group end a lunghezza fissa in modo che l'assorbimento possa confrontare nel punto giusto.

Assorbimento del contesto Absorb

Contesti più nuovi ogni cui stato è coperto da uno stato di un contesto più vecchio con un conteggio più alto — vedi §2.5 per la regola concettuale, §3.2 per l'idoneità in fase di compilazione, §3.5 per il check per coppia.

Deduplicazione di stato Advance

Stati raggiunti attraverso rami DFS diversi che finiscono nella stessa posizione con gli stessi conteggi — sopravvive solo il primo (lessicalmente precedente); le successive equivalenti vengono silenziosamente scartate, che è anche il modo in cui viene applicata la preferenza (§2.4).

Terminazione anticipata su FIN (entro il contesto) Advance

Stati ancora pendenti nella coda DFS quando un ramo raggiunge FIN — per ordine lessicale, tutti gli stati rimanenti sono meno preferiti e possono essere scartati immediatamente.

Pruning del match candidato (tra contesti) Su FIN

Altri contesti la cui riga di inizio cade entro l'intervallo del match candidato — il contesto che ha colpito FIN può continuare a cercare un match più lungo (fallback greedy), ma con AFTER MATCH SKIP PAST LAST ROW qualsiasi contesto entro l'intervallo del candidato non può più produrre un output riportabile, indipendentemente da come termini quella ricerca, ed è potato immediatamente.

Cycle guard Advance

Espansioni epsilon che rivisitano lo stesso elemento del pattern entro lo stesso DFS — altrimenti looperebbero per sempre nei gruppi nullable.

Fast-forward su loop vuoto Advance

Match di iterazione vuota legittimi che la cycle guard ucciderebbe nei gruppi nullable — bypassa il ciclo uscendo dal gruppo con le restanti iterazioni richieste dichiarate vuote.

Cutoff del frame delimitato Match

Contesti il cui match ha raggiunto il limite superiore del frame specificato dall'utente — forzati al mismatch in modo che non possano estendersi oltre (§3.4).

Leggere le voci dal badge della loro fase traccia il ciclo di vita di un contesto: il pruning si attiva a ogni riga attraverso le tre fasi principali (Match, Absorb, Advance) e nuovamente al completamento del match (Su FIN). Leggere invece le descrizioni raggruppa le regole per ciò che esse colpiscono: rami morti, contesti ridondanti, stati equivalenti, loop infiniti ed estensioni oltre i confini imposti dall'utente.

Nessuna singola regola da sola sarebbe sufficiente. La cycle guard da sola ucciderebbe match legittimi nei gruppi nullable; il fast-forward su loop vuoto da solo non fermerebbe i loop epsilon infiniti; l'assorbimento da solo consoliderebbe troppo quando DEFINE riferisce match-start; la deduplicazione da sola non rimuoverebbe i contesti ridondanti, ma solo gli stati ridondanti. Il runtime resta lineare nei casi che contano — PATTERN (A+ B+ C+ D) su 100.000 righe, il benchmark del pannello ③ del poster — solo perché ogni strato cattura ciò che gli strati superiori si lasciano sfuggire.

3.7 Output di EXPLAIN

EXPLAIN ANALYZE su una query con RPR espone statistiche a livello di NFA non presenti per le ordinarie funzioni finestra. Tre gruppi di contatori vengono emessi accanto all'operatore di finestra:

NFA States:    peak, total, merged
NFA Contexts:  peak, total, pruned
NFA: matched     (len min/max/avg)
NFA: mismatched  (len min/max/avg)
NFA: absorbed    (len min/max/avg)
NFA: skipped     (len min/max/avg)
Nav Mark Lookback:   | runtime | retain all
Nav Mark Lookahead:  | runtime | retain all
  (solo quando la query usa FIRST,
   PREV(FIRST(...)) o NEXT(FIRST(...)))

Peak e total sono strumentazione diretta del runtime: quanti stati sono stati attivi contemporaneamente, quanti sono stati creati nel corso della vita della query e quanti sono stati fusi dalla deduplicazione. Gli istogrammi di lunghezza del match separano quattro esiti — match riusciti, tentativi di match falliti, contesti assorbiti e contesti potati (skipped) senza essere valutati — e riportarli con min/max/avg rende visibili a colpo d'occhio le patologie di performance: una run sana mostra la maggior parte dei contesti come matched o absorbed, con lunghezze mismatched piccole.

I due contatori Nav Mark riportano il budget di retention del tuplestore che §3.3 deriva in fase di compilazione. Lookback è la profondità massima all'indietro tra PREV, LAST con offset e le forme composte con LAST interno; Lookahead è la profondità massima in avanti (o indietro, se negativa) misurata dall'inizio del match del contesto attivo più vecchio, contribuita da FIRST e dalle forme composte con FIRST interno.

Ogni contatore viene stampato come intero fisso quando l'offset è una costante, "runtime" quando l'offset è un'espressione non costante che deve essere valutata a ogni chiamata, e "retain all" quando il runtime necessita di un budget illimitato. Lookahead viene emesso solo quando la query usa effettivamente navigazione relativa all'inizio del match.

Insieme, questi contatori rendono possibile il debug delle prestazioni RPR senza attaccare gdb al backend.

Oltre ai contatori, EXPLAIN riproduce fedelmente anche le clausole originali PATTERN e DEFINE, inclusi quantificatori reluctant, ripetizione di gruppo e l'opzione AFTER MATCH SKIP. L'implementazione si premura di rendere stabile questo round-trip in modo che pg_dump e pg_upgrade possano preservare gli oggetti RPR senza derive semantiche — la regression suite sotto rpr_explain lo verifica caso per caso (vedi §4).

§4. Test — mappa di copertura

Il patch include cinque regression suite che insieme esercitano ogni strato descritto in §3 — circa 13.000 righe di SQL, ciascuna suite focalizzata su una preoccupazione diversa. La suddivisione è deliberata: mantenere in file separati le questioni del parser, la correttezza a runtime, le interazioni con il planner e la formattazione dell'output rende più facile localizzare i fallimenti, e impedisce che una modifica non correlata in uno strato invalidi accidentalmente i test in un altro. Le cinque suite sono:

rpr

Semantica end-to-end della query — scenari di finestra realistici su dati borsistici sintetici (forma a V, forma a W, rialzi consecutivi, inversioni).

rpr_base

Strato parser — accettazione delle parole chiave, forme sintattiche, quantificatori, parsing della navigazione, messaggi di errore e stabilità del round-trip pg_dump/pg_upgrade.

rpr_nfa

Runtime dell'NFA — il loop a tre fasi, l'assorbimento in ogni forma assorbibile e i casi limite del ciclo di vita del contesto.

rpr_explain

Formattazione dell'output — statistiche NFA, deparse del pattern, quoting degli identificatori, stabilità del formato nel ricaricamento.

rpr_integration

Interazioni con il planner — guardie che impediscono ad ottimizzazioni di finestra non correlate di corrompere la semantica RPR.

4.1 rpr — scenari end-to-end

La suite degli scenari è il volto pubblico dell'insieme dei test: utilizza un dataset sintetico di prezzi azionari di circa 1.600 righe ed esegue query realistiche su di esso — recupero a V, forma a W (doppio minimo), rialzi e ribassi consecutivi, pattern di inversione, partizioni multi-simbolo. È l'unica suite in cui input e output si leggono come query che un utente potrebbe effettivamente scrivere; le altre sono deliberatamente riduttive, focalizzate su un singolo strato per volta.

Poiché queste query combinano ogni strato (parser, planner, executor, EXPLAIN), un singolo fallimento in rpr raramente indica dove risieda il bug. Le quattro suite che seguono sono la bisezione: un fallimento in rpr con rpr_base che passa esclude il parser; con anche rpr_nfa che passa restringe a forme di dati specifiche dello scenario; con anche rpr_integration che passa esclude interferenze del planner; e qualsiasi deriva di deparse emerge in rpr_explain.

4.2 rpr_base — la superficie del parser

La suite base è la più ampia, e lo è per un motivo: è responsabile di dimostrare che ogni pezzo di sintassi legale di §1.2 venga effettivamente parsato, che ogni pezzo illegale di §1.3 sia respinto con un errore utile e che ogni forma accettata sopravviva a un round trip di serializzazione. Il grosso è costituito da piccoli snippet mirati — uno per ogni feature sintattica — piuttosto che da query realistiche lunghe, perché l'obiettivo è la copertura più che il realismo dello scenario.

I test di serializzazione meritano particolare attenzione. Gli oggetti RPR (view, view materializzate, output di pg_dump) devono fare round-trip attraverso la rappresentazione del catalogo senza derive semantiche, includendo sottigliezze come il flag reluctant su un quantificatore o la forma esatta di un'espressione di navigazione composta. Un piccolo insieme di oggetti specifici per la serializzazione (le view rpr_serial_v* e le loro tabelle di backing) viene intenzionalmente lasciato in posto alla fine della run, così che l'infrastruttura di regression circostante possa prenderli ed esercitare pg_dump e pg_upgrade su di essi. Il resto dello scaffolding di test viene rimosso come al solito. I bug catturati in questo modo (come un flag reluctant perso durante deparse e re-parse) emergono solo quando il round-trip viene esercitato end-to-end.

4.3 rpr_nfa — il motore di runtime

Questa è la suite che esercita ogni meccanismo descritto in §3.5 e §3.6. I suoi test seguono uno schema coerente: una tabella di input le cui righe sono array booleani espliciti che dichiarano quali variabili DEFINE corrispondano in ogni riga, abbinata a un pattern che sonda uno specifico comportamento del runtime. L'idioma dell'array booleano disaccoppia il test del runtime dal meccanismo di valutazione di DEFINE — ciò che si sta testando è "date queste variabili che corrispondono qui, il loop NFA produce lo span di match atteso?" piuttosto che "il valutatore di espressioni DEFINE calcola correttamente questi booleani?" Il valutatore DEFINE è testato altrove (rpr_base per il parsing, rpr per il comportamento end-to-end).

Una fixture tipica di test appare così — una colonna di array di nomi di variabili in cui ogni voce indica quali variabili DEFINE si attivano su quella riga, e un pattern le cui clausole DEFINE testano direttamente quei nomi:

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

Leggere la colonna degli array dall'alto verso il basso significa leggere direttamente lo scenario di test. Le righe 2 e 3 portano entrambi i nomi — A e B si attivano entrambe lì, quindi l'NFA ha una vera scelta su dove passare dal ramo A al ramo B. Il match atteso (A nelle righe 1–3 seguito da B nella riga 4, secondo la preferenza greedy dello standard) è fissato da quei flag soli, senza alcuna valutazione di espressione di rilievo — = ANY è solo lo strato banale che espone la colonna array a DEFINE, non ciò che il test esercita. Scrivere lo stesso scenario con un predicato numerico (price > PREV(price) e simili) intreccerebbe il test dell'NFA con il comportamento del valutatore di predicati; l'idioma degli array li mantiene nettamente separati, e un fallimento qui punta direttamente al loop NFA.

La copertura dell'assorbimento è particolarmente approfondita, perché l'assorbimento è l'ottimizzazione più probabile a produrre silenziosamente risposte errate se si attiva quando non dovrebbe. I test coprono ogni forma dell'analisi dei casi di §3.2:

• variabile illimitata semplice (A+) — il canonico collasso N-a-1;
• gruppi a lunghezza fissa ((A B)+, (A B{2})+, annidato a tre livelli ((A (B C){2}){2})+);
• variabile illimitata iniziale con suffisso fisso (A+ B) — solo l'A+ iniziale porta i flag di assorbimento, il suffisso no;
• assorbimento per ramo all'interno di un'alternativa (B+ C | B+ D);
• più variabili illimitate (A+ B+) — solo quella iniziale è assorbibile;
• quantificatori reluctant (A+?) — verificati esclusi dall'assorbimento;
• illimitato non iniziale (A B+) — verificato escluso.

Oltre all'assorbimento, la suite copre il ciclo di vita del contesto: contesti sovrapposti sotto AFTER MATCH SKIP TO NEXT ROW, cleanup di contesti falliti a metà flusso, finalizzazione a fine partizione di contesti incompleti e contesti incontrati dopo che un match candidato è già stato registrato nel contesto di testa. Ognuno di questi corrisponde a una specifica regola di pruning in §3.6, e i test sono scritti per fallire rumorosamente se la regola sbaglia (sia lasciando in vita contesti ridondanti, sia uccidendo un contesto che avrebbe dovuto produrre output).

4.4 rpr_explain — stabilità dell'output

L'output di EXPLAIN fa parte del contratto rivolto all'utente — strumenti di terze parti (autocompletamento di psql, dashboard di monitoraggio, scraper di log) lo parsano, e modifiche che sembrano cosmetiche possono romperli. La suite rpr_explain verifica tre cose:

• I contatori NFA compaiono al posto giusto — le statistiche per WindowAgg (peak/total/merged states, peak/total/pruned contexts, istogrammi di lunghezza per matched/mismatched/absorbed/skipped, Nav Mark Lookback e — quando è in uso navigazione relativa all'inizio del match — Nav Mark Lookahead) compaiono tutte sotto EXPLAIN ANALYZE con le etichette documentate.
• I pattern vengono deparsati correttamente — ogni forma di quantificatore, incluse le varianti reluctant e le forme delimitate; ogni alternativa; ogni gruppo; ogni forma di AFTER MATCH SKIP; INITIAL; chiamate di navigazione con offset; navigazione composta. Il testo deparsato deve fare round-trip attraverso il parser invariato.
• Il quoting degli identificatori è corretto — le variabili di pattern e le espressioni DEFINE vengono emesse con le stesse regole di quoting degli ordinari identificatori SQL, così che nomi di variabile insoliti non rompano l'output di pg_dump.

Come rpr_base, questa suite lascia intenzionalmente i propri oggetti in posto a fine run così che la copertura di pg_dump e pg_upgrade si estenda anche agli artefatti lato explain.

4.5 rpr_integration — interazioni con il planner

Il planner di PostgreSQL ha molte ottimizzazioni che operano sulle query con finestra — canonicalizzazione del frame, pushdown di run-condition, deduplicazione di finestre identiche, proiezione dell'output non utilizzato, transizioni inverse di moving-aggregate — e ognuna di esse è stata progettata senza tenere conto di RPR. La maggior parte è insicura da applicare quando una finestra ha una clausola PATTERN: il frame fa parte del contratto del match, l'output matched non è più monotono in alcun modo ovvio, e due finestre con la stessa spec ma DEFINE diversi producono risultati genuinamente diversi. La suite di integrazione verifica che ognuna di queste ottimizzazioni sia correttamente disabilitata o aggirata per le finestre RPR:

Canonicalizzazione del frame

Il planner normalmente riscrive ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING in ROWS UNBOUNDED PRECEDING per gli aggregati monotoni. Il frame di RPR è lo span del match, non una finestra di aggregazione, e deve rimanere verbatim.

Pushdown di run-condition

Un filtro WHERE monotono sull'output di una funzione finestra può normalmente essere spinto nell'operatore finestra come stop-condition. Per RPR ciò terminerebbe il pattern matching prematuramente, potenzialmente interrompendo match a metà estensione.

Deduplicazione di finestra (RPR vs non-RPR)

Due finestre con ORDER BY e frame identici verrebbero normalmente fuse in una. Una finestra RPR e una non-RPR non possono mai condividere stato perché la parte RPR porta risultati di match.

Deduplicazione di finestra (DEFINE diversi)

Due finestre RPR con lo stesso PATTERN ma clausole DEFINE diverse producono match diversi e devono restare distinte, anche se la loro forma strutturale è identica.

Proiezione dell'output non utilizzato

Anche se la query circostante non legge mai l'output per riga della finestra, la finestra RPR non può essere rimossa: gli effetti collaterali del pattern matcher (quali righe sono dentro quale match) alimentano calcoli di reduced-frame altrove nel piano.

Transizioni inverse di moving-aggregate

Gli aggregati di finestra con una funzione di transizione inversa possono normalmente essere valutati in modo incrementale al movimento del frame. Il reduced frame di RPR non è una finestra scorrevole; il percorso a transizione inversa produrrebbe risultati errati.

Lo schema in questi test è il medesimo: ognuno fornisce una baseline non-RPR che innesca l'ottimizzazione (e verifica che EXPLAIN ne mostri l'applicazione), poi esegue una query RPR strutturalmente simile e verifica che l'ottimizzazione non venga applicata. Le due metà insieme dimostrano che la guardia nel planner sta facendo un lavoro reale, non approvando ogni query senza verifica.

Questa suite è anche il motivo per cui §3.4 è breve. I meccanismi di "confini del match" — reduced frame, SKIP, INITIAL, cutoff del frame delimitato — sono testati operativamente altrove; ciò che rpr_integration verifica è che nessun altro stadio dell'ottimizzatore vi interferisca durante il passaggio. Un rpr_integration che passa è ciò che consente al resto delle suite di confidare che i propri input raggiungano l'executor senza alterazioni.