2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition Approfondimento

Un percorso guidato attraverso ISO/IEC 19075-5 · SQL R020 in PostgreSQL — cosa è stato realizzato, cosa rimane ancora da scrivere e come funziona effettivamente.

Materiale complementare al poster esposto al PGConf.dev 2026.
Si scorra lo standard, si percorrano esempi pratici, si esplori la progettazione e infine si utilizzi un simulatore NFA dal vivo con i propri pattern.
Discussione: thread pgsql-hackers · patch più recente (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

Pre-tradotto da IA — errori possibili.

§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 hanno in comune una parte considerevole di sintassi e semantica (19075-5 segnala in §6.3.3 alcune differenze specifiche di R020), 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 clausole all'interno di una specifica della finestra il cui frame è ROWS BETWEEN CURRENT ROW AND …: PATTERN descrive un'espressione regolare su variabili di pattern con nome, DEFINE fornisce il predicato booleano che identifica ciascuna variabile e la clausola opzionale AFTER MATCH SKIP (default PAST LAST ROW) 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; fino a 240 variabili di pattern distinte.
Frame della finestra
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING oppure ROWS BETWEEN CURRENT ROW AND n FOLLOWING con n ≥ 1 (19075-5 §6.10.2); qualsiasi altro frame viene respinto, e EXCLUDE NO OTHERS è l'unica esclusione accettata.
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 è valutato 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.
Nomi di navigazione
PREV, NEXT, FIRST e LAST scritti come chiamate non qualificate all'interno di DEFINE indicano sempre navigazione; lì una funzione utente con lo stesso nome deve essere qualificata con lo schema.
Argomenti di navigazione
Per PREV, NEXT, FIRST e LAST, l'argomento interno deve contenere almeno un riferimento a colonna e l'offset deve essere una costante a runtime.
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 FIRST var e AFTER MATCH SKIP TO [LAST] var (SKIP TO var nudo equivale a SKIP TO LAST var). Anche questi dipendono dalla storia del match, poiché l'executor deve poter puntare alla riga mappata a una data variabile 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 {- … -}, l'operatore PERMUTE insensibile all'ordine, e le funzioni di aggregazione e le subquery in DEFINE, entrambe attualmente respinte (un aggregato qualificato per variabile richiederebbe anch'esso la storia del match).

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 riga dalla riga corrente fino alla fine dell'intero frame della finestra (al contrario di INITIAL).
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 di ALL ROWS PER MATCH. Tale opzione non si applica alle finestre (19075-5 §6.3.3 (4)), quindi in una finestra la sintassi è ammessa (§6.13) ma non ha alcun output su cui agire.
Regex: ()
Pattern vuoto — corrisponde alla sequenza vuota.
PERMUTE(...)
Matching insensibile all'ordine sulle variabili elencate. La parola chiave viene riconosciuta e respinta ("PERMUTE is not supported"); permute resta utilizzabile come nome di variabile di pattern.
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; un aggregato qualificato per variabile come AVG(B.Price) dipende dalla stessa storia per match richiesta da MEASURES/CLASSIFIER(), mentre uno non qualificato spazia su tutte le righe del match fino a quel punto.
Subquery in DEFINE
Ogni subquery in DEFINE viene respinta. Lo standard ne consente una che non esegue row pattern recognition e non referenzia alcuna variabile di pattern; per ora il patch respinge più del necessario.

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 (il patch va oltre e respinge tutte le subquery in DEFINE, come elencato sopra); e RPR non può essere utilizzato all'interno di una query ricorsiva. Il patch applica la regola sui riferimenti esterni ("cannot use outer query column in DEFINE clause") e la regola sulla ricorsione, quest'ultima per ogni elemento di una clausola WITH RECURSIVE. Respinge inoltre le funzioni volatili e i riferimenti a riga intera in DEFINE.

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.

Provenienza. Gli elenchi delle funzionalità implementate e non implementate in questa sezione riflettono lo stato corrente della serie di patch — specificamente v55 (2026-11-17).

§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 cinque esempi pratici: un singolo match (movimento dell'NFA), l'alternativa, l'assorbimento del contesto nel caso semplice e due casi in cui l'assorbimento è disabilitato.

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.

Text regex vs row pattern: a single state advances per symbol, while multiple DEFINE predicates can match a row in parallel. TEXT REGEX single state advances through symbols A B C one symbol per position · one transition ROW PATTERN one row, multiple predicates evaluated row price = 150 · volume = 2000 A ✓ price > 100 B ✓ volume > 1000 C ✗ price > 200 two predicates true · two states stay alive
Una regex testuale si riduce a uno stato per simbolo; una riga può soddisfare più predicati DEFINE contemporaneamente, quindi più stati restano attivi in parallelo.

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 (default n = 1). Look-ahead in avanti; raro nella forma a finestra poiché la finestra è monotona.
FIRST(expr [, n])
La riga n righe dopo la prima riga del match corrente (default n = 0, la prima riga stessa). "Confronta con la riga che ha avviato questo match."
LAST(expr [, n])
La riga n righe prima dell'ultima riga associata (default n = 0). All'interno di DEFINE l'ultima riga associata è la riga corrente, quindi LAST(price) legge la riga corrente.

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 dalla riga letta da FIRST(expr, n) (default n = 0, m = 1). "Quale era il valore appena prima che iniziasse questo match?"
NEXT(FIRST(expr [, n]) [, m])
Si spostano m righe in avanti dalla riga letta da FIRST(expr, n). Raggiunge punti più interni del match senza dipendere dalla riga corrente.
PREV(LAST(expr [, n]) [, m])
Si spostano m righe indietro dalla riga letta da LAST(expr, n). "Confronta con una riga poco prima dell'ultima riga associata."
NEXT(LAST(expr [, n]) [, m])
Si spostano m righe in avanti dalla riga letta da LAST(expr, n).

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 semplici sono relative alla riga corrente e sono sempre sicure; FIRST e le varianti con offset di LAST, da sole o all'interno di un PREV/NEXT composto, sono relative ai confini del match, il che interagisce con l'assorbimento del contesto: il planner disabilita allora l'assorbimento per l'intero pattern. Il meccanismo dietro tale interazione è oggetto di §2.6.

2.3 Esempio pratico 1 — movimento dell'NFA

Obiettivo di questo esempioMostrare l'evoluzione riga per riga dello stato dell'NFA su un pattern semplice e non assorbente. La traccia segue il contesto iniziato alla riga 0; i contesti iniziati alle righe 1–4 procedono in parallelo e vengono scartati da SKIP PAST LAST ROW una volta registrato il suo match.
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:

RigaPrezzoVariabili vereAzione
0100STARTNuovo contesto. START corrisponde ed esce immediatamente (max=1); lo stato avanza a UP+.
1110START, UPUP corrisponde. L'avanzamento si biforca: uno stato si ripete su UP, un altro esce verso DOWN+.
2120START, UPUP corrisponde nello stato in loop e si biforca di nuovo. Lo stato DOWN della riga 1 muore (120 ≮ 110).
3115START, DOWNUP fallisce sullo stato in loop e muore. Lo stato DOWN della riga 2 corrisponde. L'avanzamento si biforca: loop su DOWN ed uscita verso #FIN — viene registrato un candidato di match sulle righe 0–3.
4108START, DOWNDOWN corrisponde nello stato in loop e si biforca di nuovo; il nuovo candidato FIN sulle righe 0–4 sostituisce quello più corto.
5130START, UPLo stato DOWN in loop fallisce (130 ≮ 108). Non restando alcuno stato attivo in questo contesto, il candidato registrato (righe 0–4) è finalizzato come match. Il tentativo successivo inizia alla riga 5; START corrisponde, ma la partizione termina prima di qualsiasi UP.

Il punto chiave: alla riga 3, la riga soddisfa sia START (sempre vero) sia DOWN, ma START conta solo per un contesto che inizia alla riga 3; in questo contesto lo stato UP in loop muore e avanza solo lo stato in attesa su 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 l'ultimo candidato FIN (righe 0–4) — prodotto quando DOWN è uscito alla riga 4, sostituendo il candidato della riga 3 — 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:

RigaPrezzostart_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

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

Obiettivo di questo esempioMostrare come un singolo contesto trasporti più stati paralleli quando una riga soddisfa più di un'alternativa — e come lo standard risolva i pareggi.

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 ordine di pattern, prima il ramo precedente.

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. Entrambi avanzano poi a DONE, dove si incontrano.

RigaVariabili vereStati attivi
RUP, HIGHStato A (ramo UP) e stato B (ramo HIGH) avanzano entrambi a DONE con gli stessi conteggi; B è un duplicato di A e viene scartato
R+1DONELo stato A corrisponde a DONE e raggiunge #FIN

Nei termini dello standard entrambi i rami producono un match della stessa lunghezza sulle stesse righe, dando 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'executor applica questa regola alla riga R, non a FIN: aggiunge per primo lo stato del ramo UP, quindi nfa_append_state_unique() lo mantiene e scarta lo stato identico del ramo HIGH.

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)

Obiettivo di questo esempioMostrare perché il lavoro totale sugli stati O(n²) ingenuo diventa O(n) sotto assorbimento, con O(1) contesti attivi.

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

RigaContesti ingenuiCon assorbimento
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 assorbito
2C1[A:3], C2[A:2], C3[A:1]C1[A:3]
3C1[A:4], C2[A:3], C3[A:2], C4[A:1]C1[A:4]
4cinque contestiC1[A:5]

I contesti attivi scendono da O(n) a O(1), quindi il totale sulla partizione scende da O(n²) a O(n). La regola di assorbimento che giustifica lo scarto è semplice quando il quantificatore è illimitato:

Regola di assorbimento. Due contesti il cui stato attivo si trova sullo stesso elemento del pattern, in cui il contesto più vecchio ha un conteggio ≥ del più nuovo, hanno futuri identici sotto un quantificatore illimitato. Il contesto più nuovo può essere scartato; qualunque match esso troverebbe alla fine, il contesto più vecchio ne troverà uno più lungo o uguale.

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:

GiornoPrezzoC1 — inizio mar
price > PREV(price)
C2 — inizio mer
price > PREV(price)
Lun$100——
Mar$108$108 > $100 ✓ (appena iniziato)—
Mer$112$112 > $108 ✓$112 > $108 ✓ (appena iniziato)
Gio$116$116 > $112 ✓$116 > $112 ✓
Ven$110$110 > $116 ✗ — finalizza$110 > $116 ✗ — finalizza
Stesso destino In ogni riga condivisa da C1 e C2, valutano espressioni identiche e producono risultati identici — e venerdì muoiono sullo stesso identico confronto. Qualunque futuro abbia C2, lo ha anche C1. Assorbire C2 in C1 non scarta nulla.

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

Obiettivo di questo esempioMostrare cosa cambia quando DEFINE riferisce FIRST — la regola di assorbimento non vale più, e il planner disabilita l'assorbimento per il pattern.

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+).

GiornoPrezzoC1 — inizio lun
FIRST = $100
price < $100 + 10
C2 — inizio mar
FIRST = $108
price < $108 + 10
Lun$100$100 < $110 ✓—
Mar$108$108 < $110 ✓$108 < $118 ✓ (appena iniziato)
Mer$112$112 < $110 ✗ — finalizza lun–mar$112 < $118 ✓
Gio$116—$116 < $118 ✓
Ven$110—$110 < $118 ✓ (ancora attivo)
Destini diversi C1 muore mercoledì con una sequenza di due giorni (lun–mar); C2, da solo, proseguirebbe fino a venerdì. Stessi prezzi, stessa forma di domanda — ma soglie diverse derivate dai propri inizi di match. Nello stesso identico giorno, i due contesti hanno raggiunto conclusioni opposte.

Sotto assorbimento, C2 sarebbe stato fuso in C1 martedì — il contesto fuso conserva solo la soglia di C1 ($110), quindi la vista distinta di C2 (soglia $118, una sequenza di quattro giorni fino a venerdì) non è coperta dal futuro di C1. In questa particolare settimana l'output non cambia: C1 registra lun–mar, C2 è iniziato all'interno di quel match ed è scartato da SKIP PAST LAST ROW, e il tentativo successivo inizia mercoledì con la propria soglia ($122) e fa match su mer–ven. In generale, però, il risultato DEFINE di un contesto precedente non sussume più quello di uno successivo, quindi il confronto dei conteggi su cui si basa l'assorbimento non è valido. 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 seguente estende il pannello in basso a destra del poster ("② Navigation") con le forme composte e riassume quali forme di navigazione creano dipendenza dall'inizio del match:

NavigazioneDip. inizio matchAssorbibile?
PREV, NEXTnessunasì
LAST (senza offset)nessunasì
LAST con offsetcontrollo di confineno
FIRST (qualsiasi)direttano
Composto (FIRST interno)direttano
Composto (LAST interno, senza offset)nessunasì
Composto (LAST interno con offset)controllo di confineno

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 ha la garanzia di coprire, quindi scartarne uno non può più essere dimostrato sicuro.

Il planner rileva questa distinzione in fase di compilazione e attiva o disattiva l'assorbimento per l'intero pattern; quando è disattivato, il runtime paga il costo multi-contesto. Il benchmark del poster nel pannello ③ non usa FIRST, quindi l'assorbimento resta attivo, ed è per questo che PostgreSQL rimane lineare sia nei casi di successo sia nei casi di fallimento.

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 approssimativamente O(n) una volta confermato un match, e PostgreSQL è in vantaggio di circa 16× a 33× (i valori di Trino escludono già l'avvio della JVM).

Sul pattern di fallimento (A+ B+ C+ E), Trino, che sembra non avere assorbimento, insegue ogni potenziale inizio di match e degrada persino più rapidamente di O(n²) (circa 56× il tempo per 5× le righe); 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

Obiettivo di questo esempioMostrare un secondo modo in cui l'assorbimento può fallire: non perché il predicato si divide, ma perché la semantica di output richiede che ogni match sia riportato separatamente.

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.

RigaSKIP PAST LAST ROWSKIP TO NEXT ROW
0il match inizia; le righe 0–4 saranno l'unico matchil match inizia alla riga 0
1(interno al match 0)il match inizia alla riga 1 — deve restare attivo
2(interno al match 0)il match inizia alla riga 2 — deve restare attivo
3(interno al match 0)il match inizia alla riga 3 — deve restare attivo
4il match 0 si finalizza (righe 0–4)cinque match si finalizzano: 0–4, 1–4, 2–4, 3–4, 4–4
Output diverso, destini diversi Sotto AFTER MATCH SKIP TO NEXT ROW, ogni contesto a partenza posticipata costituisce una propria riga di output. Due contesti sullo stesso elemento del pattern non sono più ridondanti — sono entrambi output richiesti, e scartarne uno farebbe silenziosamente cadere un match che l'utente ha richiesto.

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 ottengono i due modi in cui la semantica di una query esclude l'assorbimento:

Lato dati · §2.6
Il predicato valuta in modo diverso per ciascun contesto.
Innescato da FIRST o LAST con offset in DEFINE.
Lato output · §2.7
L'output richiede ogni inizio di match come riga separata.
Innescato da AFTER MATCH SKIP TO NEXT ROW.

Una sola di queste condizioni è sufficiente a disabilitare l'assorbimento per l'intero pattern, e lo stesso vale per un frame che non termina con UNBOUNDED FOLLOWING. Quando nessuna è in vigore — la modalità predefinita AFTER MATCH SKIP PAST LAST ROW, una fine del frame illimitata e condizioni DEFINE che usano solo PREV, NEXT o LAST nudo — l'assorbimento è abilitato, ma solo per gli stati nella regione assorbibile del pattern: una variabile iniziale greedy illimitata come A+ o A*, un gruppo a lunghezza fissa con un quantificatore greedy illimitato come (A B)+, un gruppo greedy il cui corpo inizia con uno di questi come (A+ B)+ o (A+ B){2}, oppure rami di alternativa costruiti a partire da essi; un gruppo reluctant squalifica l'intero sottoalbero. Dove ciò vale, come per A+ in §2.5, il runtime si riduce a un singolo contesto e rimane lineare; START UP+ DOWN+ di §2.3 non ottiene alcuna regione assorbibile.

§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 il lavoro 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, il confine finale deve essere UNBOUNDED FOLLOWING o un offset positivo FOLLOWING (quindi anche un frame di default viene respinto), e le opzioni EXCLUDE diverse da EXCLUDE NO OTHERS 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:

SorgenteCodifica nell'albero
AVAR(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)

Ogni predicato DEFINE viene quindi sottoposto a type-check rispetto alle colonne della partizione e coerciato in un'espressione booleana. Ne seguono due cose pratiche. Primo, l'analisi di parsing non aggiunge nulla alla target list della query per DEFINE; il planner invece marca come necessaria ogni colonna referenziata da un predicato DEFINE, come fa per HAVING, e 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 nove regole di riscrittura in un unico passaggio bottom-up (all'interno di una sequenza la fusione di gruppi viene eseguita una volta in più, poiché fusioni precedenti possono avvicinare due gruppi identici):

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}
Fusione 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
Normalizzazione della reluctance
A{2}? → A{2} (la reluctance viene rimossa ovunque min = max)

La moltiplicazione di quantificatori collassa solo quando i conteggi raggiungibili formano un unico intervallo contiguo e il match preferito non si sposta: un esterno esatto ((A{2,3}){5} → A{10,15}), un figlio con min 0, oppure intervalli del figlio che si toccano con un min del figlio al più 1 o un max del figlio illimitato ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), dove un esterno con min 0 richiede inoltre un min del figlio al più 1 ((A{2,})* resta, poiché A* accetterebbe una riga). Un figlio gruppo il cui quantificatore non è esatto deve prima avere un corpo a lunghezza fissa, quindi ((A | B B){1,2}){2} resta intatto anche con un esterno esatto. 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 — oppure spostare il match preferito ((A{2,3}){1,2} preferisce tre righe dove A{2,6} ne prende quattro), quindi l'ottimizzatore le lascia intatte. Non è l'unica riscrittura soggetta a condizioni: la fusione di gruppi e la fusione di suffisso richiedono un corpo che consumi un numero fisso di righe, la fusione di prefisso rifiuta un gruppo con min 0, max finito e contenuto nullable, i nodi reluctant non vengono né fusi né moltiplicati ((A+?)+ resta), e una riscrittura il cui nuovo limite andrebbe in overflow viene rifiutata.

Forma dell'elemento

Ogni elemento dell'array piatto rappresenta una singola posizione nel pattern. Esistono sei 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; un separatore di ramo che chiude ciascun ramo; 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 dal marker di alternativa e dai separatori di ramo per concatenare rami, dall'inizio gruppo per indicare la propria fine gruppo — un gruppo il cui quantificatore consente zero viene saltato tramite il next di tale fine — 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 → 3
    (apre il gruppo; jump indica
     il proprio 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
    (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 indica il suo END all'indice 3, e se il gruppo fosse opzionale lo skip uscirebbe tramite il next di quell'END verso l'indice 4 senza arrivare all'END. 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 cinque 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? B?)+, (A | B*)+; (A?)* viene prima moltiplicato in A* e non lascia alcun group end). Indica al runtime di aggiungere un'uscita fast-forward accanto al normale loop-back sotto min, così che la guard di ciclo non uccida match legittimi in gruppi che possono produrre iterazioni vuote.
Empty-preferred
Impostato sui group end il cui corpo preferisce il match vuoto, come in (A?? B??){2}. Ordina l'uscita fast-forward prima del loop-back sotto min, dove la greediness del gruppo stesso non dice nulla.
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'array piatto a partire
  dall'elemento 0 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 ammette quattro 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)+, (A+ B){2}
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 A riceve entrambi i flag, il BEGIN che lo racchiude riceve il flag in-region, e B ed END non ne ricevono nessuno.
Caso 4 — alternativa
A+ | B+, A+ | C D
Ciascun ramo, raggiunto attraverso la catena dei separatori, è valutato a sé dai casi precedenti; il marker di alternativa riceve il flag in-region quando un qualsiasi ramo è idoneo.

I casi strutturali non coperti da queste quattro 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. 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
  se targetPos != currentPos:
      recupera la riga in targetPos
        in nav_slot
      punta lo slot esterno a nav_slot
  result = eval_inner_expression()
  ripristina current_row_slot
  copia il risultato by-ref fuori da nav_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 e nessuno slot per riferimento; quando il target è la riga corrente, fetch e scambio vengono saltati del tutto. Il fetch copia la riga target nello slot di navigazione (a meno che lo slot non la contenga già), e il passo di ripristino copia un risultato pass-by-reference nella memoria per-tupla così che il fetch successivo non possa liberarlo.

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 currentPos − 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 (currentPos − n) − m
  NEXT(LAST(n), m):
      ritorna (currentPos − 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 l'assorbimento del contesto sia possibile o meno (§2.5 vs §2.6): una singola variabile dipendente dall'inizio del match lo disabilita per l'intero pattern.

Valutazione condivisa · assorbimento sicuro Ogni contesto vede lo stesso booleano in ogni riga — stesso destino (§2.5).
  • Nessuna navigazione
  • Solo PREV / NEXT
  • LAST senza offset
  • Composto con LAST interno (senza offset)
Valutazione per contesto · assorbimento non sicuro Contesti con inizi di match diversi calcolano risposte diverse — destini diversi (§2.6).
  • LAST con offset
  • FIRST (qualsiasi forma)
  • Composto con FIRST interno
  • Composto con LAST interno (con offset)

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. L'executor lo calcola a partire da due offset complementari, risolvendo ogni offset una volta per scan (quelli costanti anche all'init dell'executor, così che un EXPLAIN semplice possa mostrarli):

Budget di lookback
Quanto indietro dalla riga corrente potrebbe arrivare una qualsiasi chiamata DEFINE.
Contribuenti: PREV, LAST (qualsiasi offset, incluso il default 0), PREV(LAST(...)), NEXT(LAST(...))
Budget di lookahead-from-start
Lo spostamento minimo in avanti (indietro, quando negativo) dall'inizio del match del contesto attivo più vecchio — la riga più precoce di cui una qualsiasi chiamata DEFINE potrebbe aver bisogno.
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. Le righe Nav Mark riportate da EXPLAIN (§3.7) — Lookback e Lookahead — sono questi due budget, non picchi misurati. Ciascuna viene stampata solo quando qualche navigazione la alimenta ed è mostrata anche senza ANALYZE; un offset il cui valore è noto solo a runtime (ad esempio un parametro di un generic plan) stampa runtime con EXPLAIN semplice e il suo valore risolto con EXPLAIN ANALYZE, e retain all (Lookback) o infinite (Lookahead) indica un offset che va in overflow.

3.4 Confini del match — SKIP, INITIAL e frame delimitato

Il risultato di un match viene registrato come due valori: la riga in cui il match inizia e la sua lunghezza. Un inizio negativo indica che la posizione non è ancora stata valutata; una volta impostato l'inizio, le query successive all'executor — "questa riga è all'interno di un match?" — possono rispondere in O(1) ispezionando la coppia. La lunghezza codifica l'esito: -1 per una riga senza match, 0 per un match vuoto e il numero di righe per un match reale. 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 sia da una riga senza match sia 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 il pattern di quella finestra 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, quindi fa avanzare l'NFA riga per riga — reimpostando per ogni riga un array di match per variabile a "non valutato" — finché quel contesto non ha più stati attivi o la partizione termina. I predicati DEFINE sono valutati in modo lazy: una variabile viene valutata la prima volta che uno stato la consuma, quindi una variabile che nessuno stato attivo testa su questa riga non viene mai valutata. 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 ha raggiunto la fine del suo frame:
          forza mismatch (finalizza in anticipo)
          continua
      se matchStartRow differisce dalla
         posizione di valutazione condivisa:
          reimposta a non valutate 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)
      se ha registrato un match e
         SKIP PAST LAST ROW:
          pota i contesti successivi che
          iniziano all'interno del match

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]
      asserisci che elem è una variabile
          # advance parcheggia solo variabili

      se varMatched[elem.varId] è
         non valutato:
          valuta ora il suo DEFINE
      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
         o contiene un match registrato:
          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) finché il contesto non registra un match, il che lo fissa a false — assorbirlo libererebbe un match che nessun contesto assorbente può riprodurre. 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
      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, fermandosi
              una volta registrato FIN),
    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 marca
         il contesto così che i contesti
         successivi entro l'intervallo
         del candidato vengano potati — 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, una volta che Advance ha finito con il contesto che ha registrato un candidato, ogni contesto successivo la cui riga di inizio cade entro l'intervallo del candidato viene potato sulla stessa riga, 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 è il passo di pruning tra contesti all'arrivo a FIN. All'interno del contesto, FIN taglia anche il lavoro lessicalmente inferiore: Advance scarta gli stati rimanenti in coda (descritto in precedenza in questa sezione), e all'interno di un singolo DFS ogni percorso meno preferito — rami ALT successivi, l'altro tra i percorsi di skip e di ingresso di BEGIN, il percorso di ingresso di una variabile reluctant, l'altro tra i percorsi di loop e di uscita di END — si ferma una volta registrato un match, quindi un advance registra al più un match.

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
          (prima il fast-forward se il
           corpo preferisce il vuoto; il
           secondo percorso è scartato se
           il primo ha raggiunto FIN)

  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
          se il loop ha raggiunto FIN:
              scarta l'uscita
              # preferisci più lungo
          altrimenti esci dopo
      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? B?)+ e (A | B*)+ hanno questa proprietà: a seconda dei dati, il corpo può completare un'iterazione senza consumare alcuna riga. (Un singolo figlio opzionale come (A?)* viene riscritto in A* in fase di compilazione e non lascia alcun gruppo.) 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 nel corpo (il suo jump è il primo figlio del gruppo), il corpo produce nuovamente un match vuoto, raggiunge di nuovo END, e così via. Senza qualcosa che lo fermi, il DFS di Advance non terminerebbe mai.

La guard è 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. Il runtime mantiene una bitmap visited, svuotata prima dell'espansione DFS di ogni stato, in cui vengono marcati solo quegli END contrassegnati — nient'altro può ciclare, perché qualsiasi altro loop-back ha consumato una riga. Raggiungere un END marcato significa che il corpo ha appena derivato un'iterazione vuota, e lo stato non viene scartato: al limite inferiore o sopra di esso lascia lì il gruppo (un'iterazione vuota arresta il quantificatore), e sotto di esso lo stato prosegue verso il normale loop-back, così che ogni arrivo vuoto incrementi comunque il conteggio finché non raggiunge min. Si prenda (A? B?){2,3} senza che alcuna delle due variabili corrisponda nel flusso di righe:

iter 1: A? B? corrispondono a zero righe
        → END, count = 1 (sotto min)
        END già marcato (all'ingresso
        nel gruppo), ma sotto min:
        → loop indietro in A?
iter 2: A? B? corrispondono a zero righe
        → END, count = 2 (raggiunge min)
        END già marcato, al min:
        → lascia il gruppo
esce con un match di lunghezza zero

Sotto il limite inferiore il tag empty-loop dice inoltre all'handler di END di clonare uno stato fast-forward aggiuntivo insieme al normale percorso di loop-back:

advance_end (count sotto min):

  percorso di loop-back:
    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 è ciò che cattura il caso in cui il corpo ha ancora match reali da produrre in seguito — ad esempio, in (A? B?){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 esce subito dal gruppo, dichiarando "le iterazioni rimanenti richieste sono vuote", e consente al match di riuscire con un corpo di lunghezza zero. È il corpo, non la greediness del gruppo stesso, a decidere l'ordine: il fast-forward va per primo esattamente quando il corpo preferisce il match vuoto (un corpo reluctant come (A?? B??)), e se il primo percorso raggiunge FIN il secondo viene scartato, così che un percorso meno preferito non possa sostituire il match preferito. 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

Mantenere limitato il 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 si trova su un punto di confronto ed è coperto da uno stato assorbibile di un contesto più vecchio sullo stesso elemento con un conteggio maggiore o uguale — 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) Advance
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 non appena Advance ha finito con il contesto che ha registrato il candidato.
Cycle guard Advance
Espansioni epsilon che raggiungono l'END di un gruppo nullable già marcato entro lo stesso DFS (marcato all'ingresso tramite BEGIN, o in un arrivo precedente) — altrimenti looperebbero per sempre; lo stato lascia lì il gruppo al limite inferiore o sopra, e continua il loop sotto di esso.
Fast-forward su loop vuoto Advance
Sotto il limite inferiore di un gruppo nullable, un percorso aggiuntivo che esce dal gruppo con le restanti iterazioni richieste dichiarate vuote, ordinato rispetto al loop-back secondo la preferenza del corpo.
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). 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. 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. Il sorgente documenta casi che gli strati non catturano: la dedup mantiene separati stati che differiscono solo per conteggi sopra min, quindi (A{2,} B)+ C con C mai vero mantiene Θ(n²) stati al picco e ne crea Θ(n³) (37 s su 320 righe), e una sequenza di alternative interamente nullable viene enumerata percorso per percorso, quindi (A?|B?){30} impiega oltre mezz'ora.

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. In formato testo vengono emesse accanto all'operatore di finestra, dopo la riga Pattern:, le eventuali righe Nav Mark (che anche un EXPLAIN semplice mostra) e la riga Storage::

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (ciascuna solo quando DEFINE usa
   navigazione che la alimenta)
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)
  (seconda riga NFA solo quando uno dei
   due conteggi è diverso da zero; un
   conteggio zero viene stampato senza
   il suo (len ...))

I formati non testuali emettono ogni conteggio come proprietà a sé. 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; pruned conta i contesti falliti dopo una sola riga. Gli istogrammi di lunghezza del match separano quattro esiti — match riusciti, tentativi di match falliti dopo più di una riga (mismatched), contesti assorbiti e contesti liberati da AFTER MATCH SKIP PAST LAST ROW perché iniziati all'interno di un match registrato (skipped) — 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 da DEFINE. Lookback è la profondità massima all'indietro dalla riga corrente tra PREV, LAST con qualsiasi offset (incluso il default 0) e le forme composte con LAST interno; Lookahead è lo spostamento minimo in avanti (negativo quando guarda prima dell'inizio del match) misurato dall'inizio del match del contesto attivo più vecchio, contribuito 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 nota solo per scan, e — solo per Lookback — "retain all" quando l'offset va in overflow; un Lookahead in overflow stampa "infinite". Ogni riga viene emessa solo quando qualche navigazione in DEFINE la alimenta, ed entrambe compaiono anche con un EXPLAIN semplice: gli offset costanti sono fissati all'init dell'executor, mentre un offset noto solo a runtime (ad esempio un parametro di un generic plan) stampa lì "runtime" e il suo intero risolto con EXPLAIN ANALYZE.

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

Oltre ai contatori, EXPLAIN stampa una riga Pattern: costruita dall'array di elementi compilato, quindi mostra il pattern dopo le riscritture in fase di compilazione (PATTERN (A A) viene spiegato come a{2}) e porta i marker di assorbimento # (punto di confronto) e ~ (regione assorbibile); DEFINE e l'opzione AFTER MATCH SKIP non vengono mostrati. Riprodurre le clausole come scritte, inclusi quantificatori reluctant, ripetizione di gruppo e l'opzione di skip, è compito di pg_get_viewdef(), che 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 22.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
Integrazione con la clausola WINDOW — scenari di finestra realistici su dati borsistici sintetici (forma a V, forma a W, rialzi consecutivi, inversioni), più semantica della navigazione ed errori di restrizione di DEFINE.
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; più uno strato planner — ottimizzazione del pattern, flag di assorbimento, fallback dell'ottimizzazione, integrazione con il planner.
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. Questi scenari sono gli unici test in cui input e output si leggono come query che un utente potrebbe effettivamente scrivere; il resto del file, come le altre suite, è riduttivo — annidamento di PREV/NEXT ed errori di offset non costante, regole di riferimento in DEFINE e semantica dell'offset di navigazione.

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. Una seconda parte, lo strato planner, copre l'ottimizzazione del pattern, la visualizzazione e l'analisi dei flag di assorbimento, il fallback dell'ottimizzazione e l'integrazione con il planner (subquery, join, operazioni su insiemi, ordinamento e raggruppamento).

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. Difetti 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: righe VALUES inline che portano un array di nomi di variabile che dichiara quali variabili DEFINE corrispondano in ogni riga, abbinate a un pattern che sonda uno specifico comportamento del runtime. L'idioma dell'array 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:

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 (dashboard di monitoraggio, scraper di log) lo parsano, e modifiche che sembrano cosmetiche possono romperli. La suite rpr_explain verifica tre cose:

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 come ognuna di queste ottimizzazioni tratta le finestre RPR — la maggior parte deve essere disabilitata o aggirata:

Canonicalizzazione del frame
Il planner normalmente riscrive ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING in ROWS UNBOUNDED PRECEDING per le funzioni finestra indipendenti dal frame come row_number, rank e ntile. 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 o SKIP diversi)
Due finestre RPR con lo stesso PATTERN ma clausole DEFINE diverse o un AFTER MATCH SKIP diverso producono match diversi e devono restare distinte, anche se la loro forma strutturale è identica.
Proiezione dell'output non utilizzato
Questa può essere applicata: quando la query circostante non legge mai l'output della finestra, la funzione finestra diventa NULL e il suo WindowAgg viene eliminato, lasciando invariato il numero di righe. I test verificano che le colonne lette da DEFINE raggiungano ancora il WindowAgg quando questo resta, e che la finestra venga mantenuta quando il suo valore viene letto.
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.

Ulteriori casi verificano che la stima dei costi tenga conto di DEFINE, che una subquery contenente una finestra RPR non venga appiattita, che le espressioni DEFINE non trapelino in un WindowAgg superiore e che LIMIT resti sopra il WindowAgg; un secondo gruppo esegue RPR insieme a CTE, join, operazioni su insiemi, prepared statement, tabelle partizionate e costrutti simili. La maggior parte dei casi protetti segue la stessa forma: una baseline che innesca l'ottimizzazione (di solito una query non-RPR, verificata in EXPLAIN), poi una query RPR strutturalmente simile in cui l'ottimizzazione non viene applicata — per il caso di dedup DEFINE/SKIP la baseline è costituita da due finestre RPR identiche, e il caso della transizione inversa verifica l'aggiramento con un aggregato che scrive nel log anziché con EXPLAIN. 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.