2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition Mergulho Profundo

Um guia através de ISO/IEC 19075-5 · SQL R020 no PostgreSQL — o que foi construído, o que ainda falta e como realmente funciona.

Material complementar ao pôster exibido na PGConf.dev 2026.
Percorra o padrão, acompanhe exemplos práticos, explore o design e, em seguida, conduza um simulador NFA ao vivo com seus próprios padrões.
Discussão: thread pgsql-hackers · patch mais recente (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

Pré-traduzido por IA — erros possíveis.

§1. O Padrão, o Subconjunto e as Questões em Aberto

1.1 Escopo do padrão

Row Pattern Recognition foi introduzido no SQL pela ISO/IEC 9075-2:2016 e é descrito no documento complementar ISO/IEC 19075-5:2021 (Parte 5, "Row Pattern Recognition").

O padrão define duas superfícies para o mesmo mecanismo subjacente. A funcionalidade R010 coloca uma cláusula MATCH_RECOGNIZE na lista FROM para produzir uma tabela derivada; a funcionalidade R020 incorpora a mesma lógica de padrões em uma especificação WINDOW para produzir saída de função de janela. As duas superfícies têm considerável sintaxe e semântica em comum (19075-5 aponta algumas diferenças específicas de R020 em §6.3.3), mas são pontos de entrada funcionalmente distintos — um banco de dados pode implementar uma, outra ou ambas.

A série de patches discutida aqui implementa um subconjunto apenas de R020; a forma de cláusula de tabela está deliberadamente fora do escopo.

A superfície R020 é pequena, mas expressiva. Uma consulta acopla um padrão a uma janela adicionando cláusulas dentro de uma especificação de janela cujo frame é ROWS BETWEEN CURRENT ROW AND …: PATTERN descreve uma expressão regular sobre variáveis de padrão nomeadas, DEFINE fornece o predicado booleano que identifica cada variável e o opcional AFTER MATCH SKIP (padrão PAST LAST ROW) controla como matches sucessivos são posicionados dentro da partição.

Os opcionais MEASURES, SUBSET, INITIAL/SEEK e a função auxiliar CLASSIFIER() completam a funcionalidade. (A função MATCH_NUMBER() do padrão pertence apenas à superfície R010 — 19075-5 §6.3.3 (6) a exclui especificamente de R020.)

O patch cobre vocabulário suficiente para fazer consultas não triviais funcionarem, mas para antes de várias construções cuja implementação depende de infraestrutura que ainda não foi construída.

O restante desta seção particiona o vocabulário do padrão entre o que o patch já suporta e o que ele intencionalmente deixa para depois. As listas abaixo refletem o estado atual da série de patches.

1.2 Funcionalidades implementadas

O vocabulário implementado é suficiente para expressar os padrões canônicos em forma de V, em forma de W e de reversão que motivam o row pattern recognition em primeiro lugar. Também cobre todos os quantificadores padrão — incluindo todas as sete variantes reluctant *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — e as quatro primitivas de navegação que as condições DEFINE precisam para comparar linhas adjacentes.

Cláusula PATTERN
Define o row pattern dentro de uma especificação de janela; até 240 variáveis de padrão distintas.
Frame da janela
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING ou ROWS BETWEEN CURRENT ROW AND n FOLLOWING com n ≥ 1 (19075-5 §6.10.2); qualquer outro frame é rejeitado, e EXCLUDE NO OTHERS é a única exclusão aceita.
Regex: + * ? |
Quantificadores padrão e alternação.
Regex: agrupamento ( )
Subpadrões entre parênteses.
Regex: {n} {n,} {,m} {n,m}
Contagens de repetição limitadas.
Reluctant *? +? ?? {n}? {n,}? {,m}? {n,m}?
Todas as sete variantes reluctant (não gulosas) que o padrão define (excluídas da otimização de absorption).
Cláusula DEFINE
Condições booleanas que identificam cada variável de padrão.
Variável universal de padrão de linha
Referências de coluna não qualificadas em DEFINE (ex.: Price isolado) são resolvidas para a linha atual, conforme 19075-5 §4.10/§4.16.
PREV, NEXT (com offset)
Alcança n linhas antes/depois da linha atual (padrão 1); o argumento interno é avaliado na linha navegada.
FIRST, LAST (com offset)
Alcança uma linha relativa ao match; FIRST(expr, n) aponta para a linha n após o início do match, LAST(expr, n) para a linha n antes da linha de match mais recente.
Navegação composta (quatro formas)
Passo externo PREV/NEXT sobreposto a um FIRST/LAST interno: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — tanto o passo interno quanto o externo aceitam seu próprio offset.
Nomes de navegação
PREV, NEXT, FIRST e LAST escritos como chamadas não qualificadas dentro de DEFINE sempre significam navegação; uma função de usuário com o mesmo nome deve ser qualificada por schema ali.
Argumentos de navegação
Para PREV, NEXT, FIRST e LAST, o argumento interno deve conter pelo menos uma referência de coluna e o offset deve ser uma constante de run-time.
INITIAL
Os matches do padrão devem começar na linha atual (padrão).
AFTER MATCH SKIP PAST LAST ROW
Modo skip padrão; elegível para context absorption.
AFTER MATCH SKIP TO NEXT ROW
Permite matches sobrepostos; desativa absorption.

1.3 Não implementado

As funcionalidades que permanecem não implementadas se dividem em três agrupamentos amplos. O primeiro — e de longe o maior — é a família de construções centradas em MEASURES: a própria cláusula MEASURES, SUBSET, CLASSIFIER(), referências de coluna qualificadas por padrão como B.price e navegação qualificada por padrão como LAST(B.price) ou PREV(B.price).

Estas não são lacunas independentes, mas sim diferentes visões de uma única peça faltante: o executor teria que reter um histórico por match — um registro, para cada linha do match, de qual variável de padrão ela foi mapeada — e nenhuma dessas construções tem definição significativa sem isso. CLASSIFIER() lê o nome da variável a partir desse registro; B.price lê a coluna price das linhas cuja entrada de registro diz B; LAST(B.price) percorre o mesmo conjunto de linhas e escolhe a última; SUBSET U = (A, B) define uma variável virtual que agrega sobre ambos os baldes; e MEASURES avalia expressões como AVG(U.Price) usando exatamente essa agregação.

O executor atual avalia os predicados DEFINE linha por linha, mas não registra as atribuições de variável resultantes em lugar nenhum — não há nada a consultar depois. Construir a infraestrutura de histórico é, portanto, o pré-requisito para todo o grupo; as funcionalidades individuais aparecem como pequenas projeções uma vez que os registros existam.

O segundo agrupamento diz respeito a destinos alternativos de skip: AFTER MATCH SKIP TO FIRST var e AFTER MATCH SKIP TO [LAST] var (SKIP TO var sozinho significa SKIP TO LAST var). Estes também dependem do histórico do match, pois o executor precisa apontar para a linha mapeada para uma dada variável dentro do match mais recente.

Os itens restantes formam uma cauda heterogênea: a palavra-chave SEEK (alternativa a INITIAL), o padrão vazio (), a forma de exclusão {- … -}, o operador PERMUTE insensível à ordem e funções de agregação e subconsultas em DEFINE, ambas atualmente rejeitadas (uma agregação qualificada por variável também precisaria do histórico do match).

MEASURES
Expressões nomeadas de saída por match, por exemplo, MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; em R020, é exposto via OVER como uma função de janela. Aceita as palavras-chave FINAL / RUNNING (19075-5 §5.4), que em R020 colapsam para o mesmo valor, já que as measures sempre são avaliadas na última linha do match (19075-5 §6.9 (3)).
SUBSET
Uniões nomeadas de variáveis de padrão, por exemplo, SUBSET U = (A, B, C). Utilizável onde quer que uma variável de padrão possa ser referenciada — MEASURES, refs qualificadas por padrão em DEFINE, CLASSIFIER(U) — todas as quais precisam do histórico do match.
CLASSIFIER()
Retorna como qual variável de padrão uma dada linha foi correspondida. Definida tanto para DEFINE quanto para MEASURES (19075-5 §5.9); a resposta em qualquer linha é o nome da variável registrado no histórico do match para essa linha.
Referência de coluna qualificada por padrão
B.price simples em DEFINE ou MEASURES — o valor da coluna da linha mapeada como a variável nomeada.
Navegação qualificada por padrão
Restringe a navegação às linhas correspondidas como uma variável nomeada, por exemplo, LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).
SEEK
O match pode começar em qualquer linha, da linha atual até o fim do frame completo da janela (em contraste com INITIAL).
AFTER MATCH SKIP TO FIRST var
Skip para a primeira linha correspondida como a variável nomeada.
AFTER MATCH SKIP TO [LAST] var
Skip para a última linha correspondida como a variável nomeada.
Regex: {- -}
Exclusão — remove linhas correspondidas da saída de ALL ROWS PER MATCH. Essa opção não se aplica a janelas (19075-5 §6.3.3 (4)), então em uma janela a sintaxe é permitida (§6.13), mas não tem saída sobre a qual atuar.
Regex: ()
Padrão vazio — corresponde à sequência vazia.
PERMUTE(...)
Correspondência insensível à ordem entre as variáveis listadas. A palavra-chave é reconhecida e rejeitada ("PERMUTE is not supported"); permute continua utilizável como nome de variável de padrão.
Funções de agregação em DEFINE
Agregações como SUM, AVG, COUNT não são permitidas em predicados DEFINE. O padrão as permite como agregações running sobre o match parcial; uma agregação qualificada por variável como AVG(B.Price) depende do mesmo histórico por match exigido por MEASURES/CLASSIFIER(), enquanto uma não qualificada abrange todas as linhas do match até o momento.
Subconsultas em DEFINE
Toda subconsulta em DEFINE é rejeitada. O padrão permite uma que não realize row pattern recognition e não referencie nenhuma variável de row pattern; por ora, o patch rejeita além do necessário.

Quatro pontos adicionais merecem ser observados aqui, pois são facilmente confundidos com omissões.

O primeiro é que as âncoras de padrão ^ e $ não são permitidas com RPR na cláusula WINDOW pelo próprio padrão (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; com a definição subjacente em 19075-5 §4.14.1); sua ausência é conformidade, não uma lacuna.

O segundo é que MATCH_NUMBER() também é excluída de R020 pelo padrão (19075-5 §6.3.3 (6) e 19075-5 §6.9 (1)) — faz parte apenas da superfície R010 e sua ausência aqui é novamente conformidade, e não uma funcionalidade faltante.

O terceiro é um conjunto de proibições estruturais que o padrão impõe a R020 (19075-5 §6.17): row pattern recognition não pode ser aninhado dentro de outro row pattern recognition; MEASURES e DEFINE não podem conter referências externas; subconsultas dentro de MEASURES ou DEFINE não podem referenciar variáveis de row pattern (o patch vai além e rejeita todas as subconsultas em DEFINE, como listado acima); e RPR não pode ser usado dentro de uma consulta recursiva. O patch aplica a regra de referência externa ("cannot use outer query column in DEFINE clause") e a regra de recursão, esta última para cada elemento de uma cláusula WITH RECURSIVE. Ele também rejeita funções voláteis e referências de linha inteira em DEFINE.

O quarto é que o próprio MATCH_RECOGNIZE — funcionalidade R010, a superfície de cláusula de tabela do mesmo mecanismo — está fora do escopo deste patch. Se o PostgreSQL eventualmente adicionará R010 será uma questão para uma série futura, não uma métrica desta.

Procedência. As listas de implementado e não implementado nesta seção refletem o estado atual da série de patches — especificamente v55 (2026-11-17).

§2. Exemplos — Como Realmente Funciona

Os exemplos desta seção são construídos de forma incremental. Começamos pela razão conceitual de que row-pattern matching é genuinamente diferente de string-pattern matching, depois introduzimos as quatro funções de navegação que tornam as condições DEFINE interessantes e, por fim, percorremos cinco exemplos práticos: um único match (movimento do NFA), alternação, context absorption no caso fácil e dois casos em que absorption é desativado.

O mecanismo interno que torna a navegação barata — a troca de tupla em 1 slot — pertence ao design do executor e é abordado na próxima seção, não aqui.

2.1 Por que row patterns diferem de padrões de texto

Uma expressão regular de texto corresponde a um fluxo de caracteres e, em cada posição, há exatamente um símbolo a considerar. A pergunta de runtime — "o símbolo atual é igual a 'A'?" — tem uma única resposta sim/não. Autômatos com backtracking exploram isso: no máximo um ramo sobrevive por caractere, e o custo da ambiguidade é pago relendo a entrada.

Um row pattern é diferente de uma maneira fundamental. Uma linha não é um único símbolo; é uma tupla de colunas avaliada contra um conjunto de predicados booleanos, as condições DEFINE. Dois predicados podem ser verdadeiros na mesma linha simultaneamente, e nada no padrão diz que eles devem ser mutuamente exclusivos. Considere:

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

Uma linha com price = 150, volume = 2000 satisfaz tanto A quanto B, mas não C. O matcher de padrão não pode colapsar isso em um único estado — duas variáveis de padrão estão vivas, e qualquer elemento de padrão que nomeie qualquer uma delas pode avançar. O NFA, portanto, deve carregar múltiplos estados simultâneos por linha de partição, não apenas um.

Regex de texto vs row pattern: um único estado avança por símbolo, enquanto vários predicados DEFINE podem corresponder a uma linha em paralelo. 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
A regex de texto colapsa para um estado por símbolo; uma linha pode satisfazer vários predicados DEFINE de uma vez, então múltiplos estados permanecem vivos em paralelo.

Essa única observação dirige o restante da arquitetura. O estado de execução é uma lista de contextos, cada contexto é uma lista de estados, e em cada linha o runtime pergunta a cada estado: "dadas as variáveis que são verdadeiras aqui, para onde posso ir?" As bifurcações resultantes são a razão pela qual o runtime precisa de várias camadas de poda — deduplicação de estado dentro de um contexto, absorption entre contextos e as outras regras examinadas em §3.6 — sem as quais o número de estados e contextos vivos cresce com a partição e o pattern matching se torna super-linear.

2.2 Funções de navegação

Condições DEFINE que referenciam apenas a linha atual são limitadas; quase todo padrão interessante precisa comparar a linha atual com seus vizinhos ou com as linhas já aceitas anteriormente no match. O padrão fornece quatro funções de navegação para isso, e o patch implementa todas elas.

PREV(expr [, n])
A linha n linhas antes da linha atual (padrão n = 1). Usada para comparações "hoje vs. ontem".
NEXT(expr [, n])
A linha n linhas após a linha atual (padrão n = 1). Look-ahead para frente; pouco comum na forma de janela, pois a janela é monótona.
FIRST(expr [, n])
A linha n linhas após a primeira linha do match atual (padrão n = 0, a própria primeira linha). "Compare com a linha que iniciou este match."
LAST(expr [, n])
A linha n linhas antes da última linha correspondida (padrão n = 0). Dentro de DEFINE, a última linha correspondida é a linha atual, então LAST(price) lê a linha atual.

As quatro primitivas se compõem: PREV e NEXT podem envolver uma chamada FIRST ou LAST, dando quatro formas compostas cuja semântica é "vá para uma linha relativa ao match e depois dê um passo fixo a partir dela". É isso que permite a uma expressão DEFINE ler, por exemplo, a linha imediatamente anterior ao início do match.

PREV(FIRST(expr [, n]) [, m])
Passo m linhas para trás a partir da linha que FIRST(expr, n) lê (padrões n = 0, m = 1). "Qual era o valor logo antes de este match começar?"
NEXT(FIRST(expr [, n]) [, m])
Passo m linhas para frente a partir da linha que FIRST(expr, n) lê. Alcança mais longe dentro do match sem depender da linha atual.
PREV(LAST(expr [, n]) [, m])
Passo m linhas para trás a partir da linha que LAST(expr, n) lê. "Compare com uma linha pouco antes da última linha correspondida."
NEXT(LAST(expr [, n]) [, m])
Passo m linhas para frente a partir da linha que LAST(expr, n) lê.

Dois pontos práticos vale destacar aqui. Primeiro, a navegação pode ser composta: PREV(FIRST(price)) lê a linha imediatamente anterior ao início do match, e o patch suporta isso. Segundo, a navegação tem consequências para as otimizações do executor. PREV e NEXT simples são relativos à linha atual e são sempre seguros; FIRST e variantes com offset de LAST, sozinhos ou dentro de um PREV/NEXT composto, são relativos às fronteiras do match, o que interage com context absorption: o planner então desativa absorption para o padrão inteiro. O mecanismo por trás dessa interação é o tema de §2.6.

2.3 Exemplo prático 1 — Movimento do NFA

Objetivo deste exemploMostrar a evolução do estado do NFA linha a linha em um padrão simples e não absorvente. O trace acompanha o contexto iniciado na linha 0; os contextos iniciados nas linhas 1–4 correm ao lado dele e são descartados por SKIP PAST LAST ROW assim que seu match é registrado.
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)
);

O padrão é achatado em quatro elementos:

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

Para a série de preços 100, 110, 120, 115, 108, 130:

LinhaPreçoVars verdadeirasAção
0100STARTNovo contexto. START corresponde e sai imediatamente (max=1); o estado avança para UP+.
1110START, UPUP corresponde. O Advance bifurca: um estado faz loop em UP, outro sai para DOWN+.
2120START, UPUP corresponde no estado em loop e bifurca novamente. O estado DOWN da linha 1 morre (120 ≮ 110).
3115START, DOWNUP falha no estado em loop e morre. O estado DOWN da linha 2 corresponde. O Advance bifurca: loop em DOWN e saída para #FIN — um candidato a match sobre as linhas 0–3 é registrado.
4108START, DOWNDOWN corresponde no estado em loop e bifurca novamente; o novo candidato FIN sobre as linhas 0–4 substitui o mais curto.
5130START, UPO estado DOWN em loop falha (130 ≮ 108). Sem estado vivo restante neste contexto, o candidato registrado (linhas 0–4) é finalizado como match. A próxima tentativa inicia na linha 5; START corresponde, mas a partição termina antes de qualquer UP.

O ponto-chave: na linha 3, a linha satisfaz tanto START (sempre verdadeiro) quanto DOWN, mas START só importa para um contexto que começa na linha 3; neste contexto o estado UP em loop morre e apenas o estado que aguarda em DOWN+ avança. A natureza multi-estado de §2.1 é visível como fan-out em cada match de UP (o estado pode permanecer em UP+ ou avançar em direção a DOWN+). A preferência greedy é "loop novamente antes de sair", então com dados suficientes os ramos em loop estenderiam o match ainda mais; aqui, o DOWN em loop morre na linha 5 (130 ≮ 108), e o último candidato FIN (linhas 0–4) — produzido quando DOWN saiu na linha 4, substituindo o candidato da linha 3 — é finalizado como o match.

O resultado da consulta segue diretamente desse trace. Sob a semântica de RPR, as funções de janela first_value(price) e last_value(price) são avaliadas apenas na linha que iniciou o match — toda outra linha do match produz NULL para essas funções de janela, pois seu reduced frame é vazio. A saída para nossos dados, portanto, fica como a tabela que o pôster mostra em seu painel superior direito:

LinhaPreçostart_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

A linha 0 é o início do match, portanto seu frame cobre as linhas 0–4 e as funções de janela relatam o preço de abertura da forma de V ($100) e o preço de fundo ($108). As linhas 1–4 estão dentro do match, mas não são seu início, portanto recebem NULL. A linha 5 (preço $130) está fora de qualquer match e recebe NULL da mesma forma.

2.4 Exemplo prático 2 — Alternação e ordem lexical

Objetivo deste exemploMostrar como um único contexto carrega múltiplos estados paralelos quando uma linha satisfaz mais de uma alternativa — e como o padrão desempata.

A forma (A | B) dá ao matcher uma escolha: em qualquer linha, as duas alternativas são testadas independentemente e qualquer número delas pode corresponder. É aqui que a natureza multi-estado de §2.1 se torna visível dentro de um único contexto — não entre contextos (isso é absorption), mas ao longo de ramos paralelos que o executor explora na ordem do padrão, o ramo anterior primeiro.

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

Imagine uma linha em que o preço subiu e ultrapassou $100 — tanto UP quanto HIGH são verdadeiros. Cada alternativa gera seu próprio estado: um percorrendo o ramo UP, outro percorrendo o ramo HIGH. Ambos então avançam para DONE, onde se encontram.

LinhaVars verdadeirasEstados vivos
RUP, HIGHEstado A (ramo UP) e Estado B (ramo HIGH) avançam ambos para DONE com as mesmas contagens; B é uma duplicata de A e é descartado
R+1DONEO estado A corresponde a DONE e alcança #FIN

Nos termos do padrão, ambos os ramos produzem um match do mesmo comprimento sobre as mesmas linhas, dando dois caminhos candidatos — um rotulado UP, DONE e outro HIGH, DONE. O padrão resolve isso por ordem lexical: entre as alternativas escritas em (UP | HIGH), a escrita primeiro vence, independentemente do comprimento do match. Como UP aparece antes de HIGH, o caminho sobrevivente é UP, DONE. O executor impõe isso na linha R, não em FIN: ele adiciona primeiro o estado do ramo UP, então nfa_append_state_unique() o mantém e descarta o estado idêntico do ramo HIGH.

A ordem lexical é o que torna CLASSIFIER() bem definido quando for eventualmente implementado — ela permite ao runtime dizer ao usuário "esta linha correspondeu a UP, não a HIGH" mesmo quando ambos os predicados eram verdadeiros. A ordem lexical é a regra primária para alternação: um ramo lex-anterior vence sobre um lex-posterior mesmo que o lex-posterior produzisse um match mais longo, e um ramo lex-posterior (possivelmente mais curto) ainda pode vencer se todo ramo lex-anterior morrer antes de alcançar FIN. O comprimento greedy é decidido dentro de um único quantificador — dadas duas conclusões do mesmo ramo de alternação, o quantificador greedy prefere mais iterações.

2.5 Exemplo prático 3 — Context absorption (mesmo destino)

Objetivo deste exemploMostrar por que o trabalho total ingênuo de estados, O(n²), se torna O(n) sob absorption, com O(1) contextos vivos.

O padrão mais simples que exibe absorption é PATTERN (A+) com DEFINE A AS TRUE. Toda linha corresponde a A, e o padrão exige que o matcher considere cada linha como possível início de match. Ingenuamente, isso significa N contextos para uma partição de N linhas. Tome uma partição de cinco linhas (quaisquer dados — o predicado é constante verdadeiro):

LinhaContextos ingênuosCom absorption
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 absorvido
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]
4cinco contextosC1[A:5]

Os contextos vivos caem de O(n) para O(1), então o total sobre a partição cai de O(n²) para O(n). A regra de absorption que justifica o descarte é direta quando o quantificador é ilimitado:

Regra de absorption. Dois contextos cujo estado vivo está no mesmo elemento de padrão, onde o contexto mais antigo tem contagem ≥ a do mais novo, têm futuros idênticos sob um quantificador ilimitado. O contexto mais novo pode ser descartado; qualquer match que ele eventualmente encontraria, o contexto mais antigo encontrará um maior ou igual.

O painel inferior esquerdo do pôster ("① Context Absorption") é exatamente essa regra visualizada sobre cinco linhas.

Um ponto sutil, porém importante, se esconde na regra: o descarte é seguro porque o predicado A AS TRUE avalia para o mesmo valor em cada linha, independentemente de qual contexto pergunta. O mesmo vale para qualquer predicado que referencie apenas a linha atual ou um offset fixo dela — incluindo PREV. O próximo exemplo passa para uma semana concreta de preços, usando um predicado baseado em PREV, e §2.6 reutilizará exatamente essa semana para tornar óbvia a simetria entre absorption seguro e inseguro:

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

Tome a semana de pregão $100, $108, $112, $116, $110 de segunda a sexta — quatro altas seguidas por uma queda repentina. Suponha que C1 comece na terça (o primeiro dia em que RISE corresponde: $108 > $100), e que o executor também rastreie especulativamente C2 começando na quarta. A condição RISE de cada linha compara o preço da linha com seu predecessor imediato — um fato de nível de partição, não de nível de contexto — então os dois contextos são forçados a computar o mesmo booleano em cada linha que compartilham:

DiaPreçoC1 — início ter
price > PREV(price)
C2 — início qua
price > PREV(price)
Seg$100——
Ter$108$108 > $100 ✓ (acabou de iniciar)—
Qua$112$112 > $108 ✓$112 > $108 ✓ (acabou de iniciar)
Qui$116$116 > $112 ✓$116 > $112 ✓
Sex$110$110 > $116 ✗ — finaliza$110 > $116 ✗ — finaliza
Mesmo destino Em cada linha que C1 e C2 compartilham, ambos avaliam expressões idênticas e produzem resultados idênticos — e na sexta morrem exatamente na mesma comparação. Qualquer futuro que C2 tenha, C1 também tem. Absorver C2 em C1 não descarta nada.

A história se rompe no instante em que o predicado começa a depender das próprias fronteiras de cada contexto — e é disso que §2.6 trata.

2.6 Exemplo prático 4 — Quando absorption se torna inseguro

Objetivo deste exemploMostrar o que muda quando DEFINE referencia FIRST — a regra de absorption deixa de valer, e o planner desativa absorption para o padrão.

Suponha que um analista queira encontrar dias consecutivos de pregão em que uma ação ficou dentro de dez dólares do dia em que o run começou — uma espécie de janela de consolidação. O padrão e o DEFINE ficam assim:

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

A condição agora compara o preço da linha atual com o preço no início do run atual. Dois runs que começaram em dias diferentes têm valores diferentes de FIRST(price), portanto dois estados no mesmo elemento de padrão e na mesma contagem deixam de ser intercambiáveis: seus futuros dependem da fronteira que absorption estava prestes a descartar.

Tome a mesma semana de pregão de §2.5 — $100, $108, $112, $116, $110 de segunda a sexta. O runtime novamente mantém dois runs candidatos vivos ao mesmo tempo: C1 começou na segunda, C2 começou na terça (toda linha é um potencial início de run sob STABLE+).

DiaPreçoC1 — início seg
FIRST = $100
price < $100 + 10
C2 — início ter
FIRST = $108
price < $108 + 10
Seg$100$100 < $110 ✓—
Ter$108$108 < $110 ✓$108 < $118 ✓ (acabou de iniciar)
Qua$112$112 < $110 ✗ — finaliza seg–ter$112 < $118 ✓
Qui$116—$116 < $118 ✓
Sex$110—$110 < $118 ✓ (ainda em curso)
Destinos diferentes C1 morre na quarta com um run de dois dias (seg–ter); C2, por si só, seguiria em curso até a sexta. Mesmos preços, mesma forma de pergunta — mas tetos diferentes derivados dos próprios inícios de match. No mesmo dia, os dois contextos chegaram a conclusões opostas.

Sob absorption, C2 teria sido fundido em C1 na terça — o contexto fundido mantém apenas o teto de C1 ($110), portanto a visão distinta de C2 (teto $118, um run de quatro dias até a sexta) não é coberta pelo futuro de C1. Nesta semana em particular a saída por acaso não muda: C1 registra seg–ter, C2 começou dentro desse match e é descartado por SKIP PAST LAST ROW, e a próxima tentativa começa na quarta com seu próprio teto ($122) e corresponde a qua–sex. Em geral, porém, o resultado DEFINE de um contexto anterior não subsume mais o de um posterior, então a comparação de contagens em que absorption se apoia é inválida. Sempre que um predicado DEFINE carrega dependência do início do match, o planner desativa absorption preventivamente.

(Quando o match do contexto líder realmente tem sucesso, contextos que começaram dentro de seu span aceito — sob o padrão AFTER MATCH SKIP PAST LAST ROW — são simplesmente descartados; eles são mantidos vivos apenas para que o runtime tenha um ponto de retorno caso o match líder falhe.)

A tabela abaixo estende o painel inferior direito do pôster ("② Navigation") com as formas compostas e resume quais formas de navegação criam dependência do início do match:

NavegaçãoDep. de início de matchAbsorvível?
PREV, NEXTnenhumasim
LAST (sem offset)nenhumasim
LAST com offsetverificação de fronteiranão
FIRST (qualquer)diretanão
Composta (FIRST interno)diretanão
Composta (LAST interno, sem offset)nenhumasim
Composta (LAST interno com offset)verificação de fronteiranão

Os dois exemplos em §2.5 e §2.6 se reduzem a uma única regra. O mesmo destino é o que torna a absorption segura: se todo contexto no mesmo elemento de padrão computará a mesma resposta para cada predicado futuro, apenas o mais antigo precisa ser mantido. Destinos diferentes tornam a absorption insegura: assim que os predicados se ramificam com base em estado privado do contexto — que é exatamente o que FIRST e LAST com offset fazem — todo contexto vivo representa um futuro que nenhum outro contexto tem garantia de cobrir, então já não se pode demonstrar que descartar um deles é seguro.

O planner detecta essa distinção em tempo de compilação e liga ou desliga absorption para o padrão inteiro; quando está desligado, o runtime paga o custo multi-contexto. O benchmark do pôster no painel ③ não usa FIRST, então absorption permanece ligado, e é por isso que o PostgreSQL permanece linear tanto nos casos de sucesso quanto de falha.

Os números do benchmark no pôster são o mesmo algoritmo se desdobrando em escala. No padrão de sucesso (A+ B+ C+ D), tanto o PostgreSQL quanto o Trino escalam aproximadamente em O(n) uma vez que um match é confirmado, e o PostgreSQL lidera por aproximadamente 16× a 33× (os números do Trino já excluem a inicialização da JVM).

No padrão de falha (A+ B+ C+ E), o Trino, que aparentemente não tem absorption, persegue cada potencial início de match e degrada ainda mais rápido que O(n²) (cerca de 56× o tempo para 5× as linhas); a 100.000 linhas, leva mais de cinco horas, enquanto o PostgreSQL ainda termina em 92 ms, um speed-up de cerca de 217.000×.

Essa diferença não é polimento de engenharia — é precisamente a distinção mesmo destino / destinos diferentes de §2.5 e §2.6, aplicada a cada linha de cada potencial início de match na partição.

2.7 Exemplo prático 5 — Quando SKIP desativa absorption

Objetivo deste exemploMostrar uma segunda maneira pela qual absorption pode falhar: não porque o predicado se ramifica, mas porque a semântica de saída exige que cada match seja reportado separadamente.

O exemplo anterior quebrou absorption do lado dos dados: FIRST em DEFINE fez cada contexto avaliar predicados de modo diferente. Absorption também pode quebrar pelo lado da saída, e quem controla isso é a cláusula AFTER MATCH SKIP.

Considere o padrão PATTERN (A+) com DEFINE A AS TRUE sobre cinco linhas que todas correspondem a A. Sob o padrão AFTER MATCH SKIP PAST LAST ROW, o matcher encontra o match mais longo começando na linha mais antiga e depois pula para depois dele; qualquer contexto que começou dentro daquele match é implicitamente descartado como redundante — exatamente a situação para a qual absorption foi projetada. A saída é um único match, linhas 0–4, e o runtime precisa de apenas um contexto vivo.

Troque o modo skip para AFTER MATCH SKIP TO NEXT ROW e o contrato muda:

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

Agora cada posição potencial de início precisa ser reportada separadamente, mesmo quando os matches se sobrepõem. Para as mesmas cinco linhas, o runtime é obrigado a emitir cinco matches: linhas 0–4, 1–4, 2–4, 3–4 e 4–4. Nenhum deles pode ser substituído por um "mais longo começando antes", porque o padrão diz que o usuário quer todos eles.

LinhaSKIP PAST LAST ROWSKIP TO NEXT ROW
0match começa; linhas 0–4 serão o único matchmatch começa na linha 0
1(dentro do match 0)match começa na linha 1 — precisa ser mantido vivo
2(dentro do match 0)match começa na linha 2 — precisa ser mantido vivo
3(dentro do match 0)match começa na linha 3 — precisa ser mantido vivo
4match 0 finaliza (linhas 0–4)cinco matches finalizam: 0–4, 1–4, 2–4, 3–4, 4–4
Saída diferente, destinos diferentes Sob AFTER MATCH SKIP TO NEXT ROW, todo contexto iniciado tardiamente é sua própria linha de saída. Dois contextos no mesmo elemento de padrão deixam de ser redundantes — ambos são saídas obrigatórias, e descartar um silenciaria um match que o usuário pediu.

Note que o predicado não mudou. A AS TRUE avalia da mesma forma em cada linha, independentemente de qual contexto pergunta, então a condição de mesmo destino de §2.5 ainda é cumprida. O que muda é o requisito de saída: mesmo contextos com futuros idênticos precisam coexistir porque correspondem a linhas distintas do resultado. O planner, portanto, desativa context absorption sempre que AFTER MATCH SKIP TO NEXT ROW está em vigor, independentemente da cláusula DEFINE.

Colocar §2.6 e §2.7 lado a lado dá as duas maneiras pelas quais a semântica de uma consulta exclui absorption:

Lado dos dados · §2.6
O predicado avalia de forma diferente por contexto.
Disparado por FIRST ou LAST com offset em DEFINE.
Lado da saída · §2.7
A saída exige cada início de match como linha separada.
Disparado por AFTER MATCH SKIP TO NEXT ROW.

Qualquer das duas condições basta para desativar absorption para o padrão inteiro, assim como um frame que não termina em UNBOUNDED FOLLOWING. Quando nenhuma está em vigor — o padrão AFTER MATCH SKIP PAST LAST ROW, um fim de frame ilimitado e condições DEFINE que usam apenas PREV, NEXT ou LAST sem offset — absorption é ativado, mas apenas para estados na região absorvível do padrão: uma variável inicial greedy ilimitada como A+ ou A*, um grupo de comprimento fixo com um quantificador greedy ilimitado como (A B)+, um grupo greedy cujo corpo começa com um desses como (A+ B)+ ou (A+ B){2}, ou ramos de alternação construídos a partir deles; um grupo reluctant desqualifica toda a sua subárvore. Onde isso vale, como para A+ em §2.5, o runtime colapsa para um único contexto e permanece linear; START UP+ DOWN+ de §2.3 não recebe nenhuma região absorvível.

§3. Design — Do Parser ao Executor

Row Pattern Recognition é implementado como três estágios que repassam o trabalho por meio de formas intermediárias bem definidas. O parser transforma o texto SQL em uma árvore de padrão e uma lista de predicados DEFINE; o planner compila a árvore em um array plano de elementos de padrão e decide quais deles podem participar de context absorption; o executor executa o array contra a partição linha a linha em um loop de três fases. Cada estágio tem sua própria forma de dados, e a maior parte da engenhosidade do design está nas fronteiras: um NFA plano que cabe em cache, um modelo de navegação que reutiliza um único slot de tupla em vez de materializar um por referência, e uma regra de absorption que transforma trabalho O(n²) em O(n).

texto SQL
  │
  │  estágio do parser
  ▼    validar frame
       construir árvore de padrão
       type-check de DEFINE

árvore de padrão + lista DEFINE
  │
  │  estágio do planner
  ▼    otimizar a árvore
       compilar para array NFA plano
       decidir absorbability

NFA plano + flags de absorption
  │
  │  estágio do executor
  ▼    motor por linha:
       Match → Absorb → Advance

resultado do match:
  linha inicial, comprimento, sucesso/falha

As seções abaixo descem por esse pipeline. §3.1 cobre o parser e a forma da árvore de padrão; §3.2 cobre a compilação que transforma a árvore no NFA plano; §3.3 cobre o modelo de navegação que os predicados DEFINE usam para olhar linhas vizinhas; §3.4 cobre o tratamento das fronteiras de match — as regras de SKIP, INITIAL e frame limitado que fixam onde um match começa e termina; §3.5 é o motor por linha de três fases; §3.6 reúne todos os mecanismos de poda que mantêm o espaço de estados limitado; e §3.7 examina o que a implementação expõe na saída de EXPLAIN.

3.1 Parser — construindo a árvore de padrão

O parser reconhece pattern recognition pela presença de uma cláusula PATTERN dentro de uma especificação de janela. Seu primeiro trabalho é a validação do frame, já que RPR impõe restrições que consultas de janela comuns não impõem: o modo do frame deve ser ROWS (não RANGE nem GROUPS), a fronteira inicial deve ser CURRENT ROW, a fronteira final deve ser UNBOUNDED FOLLOWING ou um offset positivo FOLLOWING (portanto um frame deixado no padrão também é rejeitado), e opções EXCLUDE diferentes de EXCLUDE NO OTHERS são proibidas. Essas são checagens de conformidade, não otimizações — a noção de frame em RPR é o span do match, e o padrão não contempla preenchê-lo com algo além das linhas correspondidas.

Uma vez que o frame passa pela validação, o parser transforma a cláusula PATTERN em uma árvore construída a partir de quatro tipos de nó — uma referência de variável, uma sequência (concatenação), uma alternação e um grupo (subpadrão entre parênteses). Cada nó carrega o quantificador como três números — um limite inferior, um limite superior (possivelmente infinito) e um flag para matching reluctant:

OrigemCodificação na árvore
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)

Cada predicado DEFINE é então verificado quanto ao tipo contra as colunas da partição e convertido em uma expressão booleana. Duas coisas práticas decorrem disso. Primeiro, a análise de parse não adiciona nada à target list da consulta para DEFINE; em vez disso, o planner marca como necessária toda coluna que um predicado DEFINE referencia, como faz para HAVING, e propaga essas colunas até o estágio do executor mesmo que a consulta circundante não as selecione — sem isso, o runtime não teria nada contra o que avaliar. Segundo, variáveis que aparecem no PATTERN mas nunca no DEFINE são implicitamente verdadeiras: correspondem a toda linha.

3.2 Compilação — do AST a um NFA plano

O planner transforma a árvore do parser na estrutura de dados que o executor irá rodar: um array plano de elementos de padrão endereçados por índice. A compilação procede como um pipeline de seis passos:

compile(astTree):
  1. otimizar o AST
  2. medir tamanho e profundidade
  3. alocar o array de elementos
  4. preencher a partir do AST
       (atribuir ponteiros next/jump)
  5. finalizar — configurar sentinela FIN
  6. marcar elementos elegíveis para absorption

A forma plana é escolhida por uma razão simples: o executor precisa percorrer o padrão muitas vezes por partição, e um array contíguo endereçável por índice é a estrutura de dados mais barata de percorrer. Os passos 1 e 6 são os interessantes — o passo 1 porque determina o tamanho do array, e o passo 6 porque decide se a otimização de absorption de §2.5 será ativada de fato.

Otimização do AST

A otimização compensa duas vezes: uma na contagem estática de elementos do array plano e novamente em cada linha processada em runtime. Cada transformação reduz o espaço de estados que o runtime precisa enumerar. O otimizador aplica nove regras de reescrita em uma única passagem bottom-up (dentro de uma sequência, a fusão de grupos roda mais uma vez, já que fusões anteriores podem juntar dois grupos idênticos):

Achatamento de SEQ
SEQ(A, SEQ(B, C)) → SEQ(A, B, C)
Fusão de variáveis consecutivas
A A → A{2}
A{2,3} A{1,2} → A{3,5}
Fusão de grupos consecutivos
(A B)+ (A B)+ → (A B){2,∞}
Fusão de ALT consecutivos
(A | B) (A | B) (A | B) → (A | B){3}
Fusão de prefixo/sufixo
A B (A B)+ → (A B){2,∞}
Achatamento e deduplicação de ALT
(A | (B | C)) → (A | B | C)
(A | B | A) → (A | B)
Multiplicação de quantificadores
(A+)+ → A+
(A{2,3}){5} → A{10,15}
Desembrulhar filho único
SEQ(A) → A
(A){1,1} → A
Normalização de reluctance
A{2}? → A{2} (a reluctance é removida sempre que min = max)

A multiplicação de quantificadores colapsa apenas quando as contagens alcançáveis formam um único intervalo contíguo e o match preferido não se move: um externo exato ((A{2,3}){5} → A{10,15}), um filho com min 0, ou intervalos do filho que se tocam com min do filho no máximo 1 ou max do filho ilimitado ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), em que um externo com min 0 também precisa de min do filho no máximo 1 ((A{2,})* permanece, já que A* aceitaria uma linha). Um filho de grupo cujo próprio quantificador não é exato precisa primeiro ter um corpo de comprimento fixo, então ((A | B B){1,2}){2} permanece intacto mesmo sob um externo exato. Outras combinações podem introduzir lacunas que a forma plana perderia — por exemplo, (A{2}){2,3} aceita apenas {4, 6}, mas um A{4,6} ingênuo também aceitaria 5 — ou deslocar o match preferido ((A{2,3}){1,2} prefere três linhas, onde A{2,6} toma quatro), então o otimizador as deixa intactas. Não é a única reescrita condicionada: a fusão de grupos e a fusão de sufixo exigem um corpo que consuma um número fixo de linhas, a fusão de prefixo recusa um grupo com min 0, max finito e conteúdo nullable, nós reluctant não são fundidos nem multiplicados ((A+?)+ permanece), e uma reescrita cujo novo limite estouraria é recusada.

Forma do elemento

Cada elemento do array plano representa uma única posição no padrão. Há seis tipos lógicos: uma referência de variável (o único tipo que consome uma linha); marcadores group begin e group end, que abrem e fecham um subpadrão entre parênteses; um marcador de alternação, que encabeça uma lista de ramos; um separador de ramo que termina cada ramo; e um marcador de fim ao final do padrão.

Cada elemento também carrega uma profundidade (seu nível de aninhamento de grupo), o quantificador (uma contagem mínima e máxima de repetições, possivelmente infinita) e dois ponteiros de transição — next, "para onde ir após consumir este elemento", e jump, "para onde pular" (usado pelo marcador de alternação e pelos separadores de ramo para encadear ramos, pelo group begin para nomear seu próprio group end — um grupo cujo quantificador permite zero é pulado através do next desse end — e pelo group end para fazer loop de volta ao corpo).

Para PATTERN ((A B)+), o array compilado fica assim:

PATTERN ((A B)+) compila para:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 3
    (abre grupo; jump nomeia
     seu próprio 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
    (fecha grupo; jump faz loop de volta)

[4] FIN    padrão completo

O padrão é lido da esquerda para a direita via next, com jump tratando as arestas não lineares. No idx 3, o jump do END aponta de volta para o idx 1, e é assim que o quantificador externo ilimitado faz loop; no idx 0, o jump do BEGIN nomeia seu END no idx 3, e se o grupo fosse opcional o skip sairia pelo next desse END para o idx 4 sem chegar ao END. O runtime nunca precisa construir um grafo em runtime — apenas segue esses dois ponteiros enquanto percorre o array.

Atributos por elemento

Além da forma, cada elemento carrega cinco atributos lógicos que dirigem o comportamento do runtime naquela posição:

Reluctant
Inverte a ordem de expansão do quantificador. Quantificadores greedy tentam "loop novamente" antes de "sair"; quantificadores reluctant tentam "sair" primeiro. Carregado pela variável para A+?; carregado pelo BEGIN e END do grupo para ((…)+?).
Empty-loopable
Definido em ends de grupo cujo corpo é nullable ((A? B?)+, (A | B*)+; (A?)* é primeiro multiplicado em A* e não deixa group end). Diz ao runtime para adicionar uma saída fast-forward ao lado do loop-back normal abaixo de min, para que o cycle guard não mate matches legítimos em grupos que podem produzir iterações vazias.
Empty-preferred
Definido em ends de grupo cujo corpo prefere o match vazio, como em (A?? B??){2}. Ordena a saída fast-forward à frente do loop-back abaixo de min, onde a própria greediness do grupo não diz nada.
In-absorbable-region
Marca todo elemento que está dentro de uma região elegível para absorption — usado pelo runtime para rastrear se o estado atual ainda está em território seguro.
Absorption-comparison-point
Marca o elemento específico onde as comparações de absorption devem ser executadas. Para um simples A+, recai sobre a variável; para um grupo ilimitado como (A B)+, recai apenas sobre o group end.

A divisão entre "in-region" e "comparison-point" importa porque absorption só faz sentido em pontos onde as iterações se fecham. Dentro do corpo de (A B)+, o runtime está no meio de uma iteração e a contagem ainda não atingiu seu valor final para aquela rodada; comparar aqui significaria comparar valores incomparáveis. O estado precisa alcançar o group end antes que o runtime possa decidir. O primeiro atributo, portanto, diz "você ainda está em território absorvível"; o segundo diz "você atingiu o ponto de comparação — verifique agora".

Análise de absorbability

O passo 6 da compilação é o que dá à regra de "mesmo destino" de §2.5 sua testemunha em tempo de compilação. A decisão é em camadas:

isAbsorbable(query):
  if modo SKIP != SKIP PAST LAST ROW
      → retorna false
  if fim do frame != UNBOUNDED FOLLOWING
      → retorna false
  if algum DEFINE depende de match_start
      → retorna false
  percorre o array plano a partir
  do elemento 0 e marca elementos
  que satisfazem um caso estrutural

As três primeiras checagens são em nível de consulta: correspondem exatamente às condições §2.7 (lado da saída: modo SKIP), frame limitado (a fronteira quebra a monotonicidade) e §2.6 (lado dos dados: FIRST ou LAST com offset em DEFINE). Quando alguma delas falha, a análise não define flags e absorption é desativada para toda a consulta. Quando todas passam, o percurso admite quatro formas estruturais:

Caso 1 — Variável simples ilimitada
A+, A*, A{2,∞}
Cada iteração é exatamente uma linha. A contagem de um contexto anterior é sempre ≥ à de um posterior em toda posição compartilhada.
Caso 2 — Grupo de comprimento fixo, externo ilimitado
(A B)+, (A B{2})+, ((A (B C){2}){2})+
Todo filho tem min == max, então o corpo é semanticamente equivalente à sua forma desenrolada {1,1} — (A B{2})+ se comporta como (A B B)+. Cada iteração consome um número fixo de linhas; a dominância de contagem ainda se sustenta.
Caso 3 — Grupo cujo corpo começa com uma variável ilimitada
(A+ B)+, (A+ B){2}
A variável ilimitada inicial é ela própria absorvível (Caso 1) e protege contextos anteriores. Absorption para assim que o estado passa de A — o restante do corpo não tem garantia de monotonicidade, então A recebe ambos os flags, o BEGIN envolvente recebe o flag in-region, e B e END não recebem nenhum.
Caso 4 — Alternação
A+ | B+, A+ | C D
Cada ramo, alcançado pela cadeia de separadores, é julgado individualmente pelos casos acima; o marcador de alternação recebe o flag in-region quando algum ramo se qualifica.

Os casos estruturais não cobertos por essas quatro formas são igualmente instrutivos. A B+ não pode ser absorvido pela regra atual porque o A inicial consome uma linha antes de a parte ilimitada começar, então contextos que iniciaram com uma linha de diferença estão em posições distintas dentro do corpo ilimitado. Quantificadores reluctant como A+? são excluídos por construção: a regra de absorption assume semântica greedy, em que matches mais longos subsumem os mais curtos, e o matching reluctant inverte essa direção.

O resultado é uma decisão por elemento, e não por padrão. Um único plano de consulta pode ter absorption ativado para o A+ inicial de padrões como (A+ B+ C) ou (A+ B+)+ — o último é apenas o Caso 3 aplicado ao seu elemento inicial — e desativado para tudo o que vem depois; o runtime simplesmente consulta o atributo comparison-point do elemento do estado atual cada vez que considera uma passagem de absorption. Uma vez que um estado se mova para uma região não absorvível, absorption fica permanentemente desligado para esse estado — exatamente o que §2.5 e §2.6 precisam que seja verdade no nível algorítmico.

3.3 Navegação — a troca de tupla em 1 slot

Expressões DEFINE são expressões SQL comuns avaliadas contra uma linha, mas podem incluir PREV, NEXT, FIRST ou LAST — referências que apontam para linhas diferentes. As próprias linhas já estão em buffer no tuplestore da janela; o que o executor ainda precisa gerenciar é o slot de tupla do qual a maquinaria de expressões SQL lê, já que referências de coluna dentro da expressão estão vinculadas a um slot em tempo de plano. A implementação reutiliza um único navigation slot para cada chamada de navegação: o slot é trocado antes de avaliar a expressão interna e restaurado depois, então o resto da maquinaria de expressões SQL nunca percebe a diferença.

O modelo que o executor enxerga é pequeno: há um current row slot que mantém a linha contra a qual a expressão DEFINE está sendo avaliada, e um navigation slot que o runtime pode redirecionar temporariamente para uma linha diferente. Em torno de qualquer chamada de navegação, o runtime configura o navigation slot, avalia a expressão interna como se estivesse lendo a linha atual e depois restaura a linha original. Pseudocódigo:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos está fora da faixa válida:
      return NULL

  salva current_row_slot
  if targetPos != currentPos:
      busca linha em targetPos
        para nav_slot
      aponta slot externo para nav_slot
  result = eval_inner_expression()
  restaura current_row_slot
  copia resultado by-ref para fora de nav_slot
  return result

O truque é que existe exatamente um slot para salvar e restaurar. A expressão interna — seja qual for, incluindo aritmética, chamadas de função ou outras referências de coluna — roda contra o slot trocado usando o mesmo caminho de avaliação que usaria para a linha atual. Sem avaliador alternativo e sem slot por referência; quando o alvo é a linha atual, a busca e a troca são totalmente puladas. A busca copia a linha alvo para o navigation slot (a menos que o slot já a contenha), e o passo de restauração copia um resultado pass-by-reference para a memória por tupla, para que a próxima busca não possa liberá-lo.

A navegação composta é achatada em tempo de parse para que a troca ainda aconteça uma única vez. PREV(FIRST(price)) é reconhecida como navegação de duas etapas — "vá para a primeira linha correspondida e depois dê um passo uma linha antes" — e armazenada como uma única chamada de navegação com tipo composto. O runtime calcula a posição alvo em duas etapas, mas executa apenas uma troca de slot para buscar a linha final:

compute_target_position(call):

  # relativa à linha atual
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # relativa ao match
  FIRST(n):
      return matchStart + n
  LAST(n):
      return currentPos − n

  # composta: relativa ao match, depois passo
  PREV(FIRST(n), m):
      return (matchStart + n) − m
  NEXT(FIRST(n), m):
      return (matchStart + n) + m
  PREV(LAST(n), m):
      return (currentPos − n) − m
  NEXT(LAST(n), m):
      return (currentPos − n) + m

  valida contra a faixa apropriada
  (faixa do match para FIRST/LAST internos,
   faixa da partição para o passo externo)

Um cache de posição encurta a busca no tuplestore quando várias chamadas de navegação no mesmo DEFINE apontam para a mesma linha — comum em expressões como price > PREV(price) AND volume > PREV(volume), em que ambas as chamadas resolvem para a linha anterior. O cache armazena apenas a "última posição buscada", e a troca em si permanece uma única operação.

A classificação das chamadas de navegação é a contribuição do planner à decisão de absorption. O planner percorre cada expressão DEFINE e classifica cada variável em um de dois baldes, com base em se todos os contextos computarão o mesmo booleano na mesma linha, ou se cada contexto computará o seu próprio. O balde determina duas coisas em runtime: com que frequência a variável é avaliada (uma vez compartilhada, ou uma vez por contexto afetado — §3.5 Fase 1) e se context absorption é possível de todo (§2.5 vs §2.6): uma única variável dependente do início do match o desativa para o padrão inteiro.

Avaliação compartilhada · absorption seguro Todo contexto vê o mesmo booleano em cada linha — mesmo destino (§2.5).
  • Sem navegação
  • Apenas PREV / NEXT
  • LAST sem offset
  • Composto com LAST interno (sem offset)
Avaliação por contexto · absorption inseguro Contextos com inícios de match diferentes computam respostas diferentes — destinos diferentes (§2.6).
  • LAST com offset
  • FIRST (qualquer forma)
  • Composto com FIRST interno
  • Composto com LAST interno (com offset)

A classificação é realizada em tempo de plano e armazenada junto a cada variável DEFINE, então o runtime não gasta tempo decidindo — apenas lê o balde de cada variável ao processar uma linha.

Orçamento de retenção

A navegação alcança linhas que a maquinaria de funções de janela já transmitiu adiante. Para manter essas linhas disponíveis, o executor é construído sobre um tuplestore que retém uma janela deslizante de linhas recentes; a questão é quão larga essa janela precisa ser. O executor a calcula a partir de dois offsets complementares, resolvendo cada offset uma vez por scan (os constantes também na inicialização do executor, para que o EXPLAIN simples possa mostrá-los):

Orçamento de Lookback
Quão longe para trás, a partir da linha atual, qualquer chamada DEFINE pode alcançar.
Contribuintes: PREV, LAST (qualquer offset, incluindo o padrão 0), PREV(LAST(...)), NEXT(LAST(...))
Orçamento de Lookahead-from-start
O alcance mínimo para frente (para trás, quando negativo) a partir do início do match do contexto vivo mais antigo — a linha mais antiga de que qualquer chamada DEFINE pode precisar.
Contribuintes: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

Em tempo de execução, o trim mark do tuplestore é definido para qualquer das duas posições que for mais antiga — linha atual menos o orçamento de lookback, e o início do match do contexto vivo mais antigo mais o orçamento de lookahead. Qualquer coisa antes desse marco não pode ser alcançada por nenhuma chamada de navegação em qualquer contexto vivo, e o tuplestore está livre para descartá-la. As linhas Nav Mark que o EXPLAIN reporta (§3.7) — Lookback e Lookahead — são esses dois orçamentos, não picos medidos. Cada uma é impressa apenas quando alguma navegação a alimenta e é mostrada mesmo sem ANALYZE; um offset cujo valor só é conhecido em tempo de execução (um parâmetro de generic plan, por exemplo) imprime runtime sob EXPLAIN simples e seu valor resolvido sob EXPLAIN ANALYZE, e retain all (Lookback) ou infinite (Lookahead) marca um offset que estoura.

3.4 Fronteiras de match — SKIP, INITIAL e frame limitado

Um resultado de match é registrado como dois valores: a linha em que o match começa e seu comprimento. Um início negativo significa que a posição ainda não foi avaliada; uma vez definido o início, consultas subsequentes ao executor — "esta linha está dentro de um match?" — podem responder em O(1) inspecionando o par. O comprimento codifica o resultado: -1 para uma linha sem match, 0 para um match vazio e a contagem de linhas para um match real. Comprimento zero é um resultado real, não um erro: representa um padrão que correspondeu sem consumir qualquer linha, o que o executor precisa distinguir tanto de uma linha sem match quanto de "nenhum match foi tentado nesta posição ainda".

A cláusula AFTER MATCH SKIP decide onde a próxima tentativa de match começa. AFTER MATCH SKIP PAST LAST ROW move para a linha após o fim do match, produzindo a saída não sobreposta que a maioria das consultas deseja e habilitando a otimização de absorption.

AFTER MATCH SKIP TO NEXT ROW move apenas para a linha após o início do match, permitindo matches sobrepostos; o planner, portanto, desativa absorption para o padrão dessa janela quando este modo está em vigor.

Os dois destinos de skip que o padrão também define — AFTER MATCH SKIP TO FIRST var e AFTER MATCH SKIP TO LAST var — dependem do histórico por match que este patch não retém. Eles não estão presentes na gramática, então o parser levanta um erro de sintaxe genérico se qualquer um for fornecido.

O mesmo vale para SEEK, a alternativa do spec a INITIAL. Sob SEEK, uma tentativa de match começando na linha R pode ter sucesso em qualquer linha de R até o fim do frame, não apenas em R. O patch implementa apenas INITIAL: todo match potencial está ancorado em uma linha específica. O parser levanta um erro se SEEK for solicitado. Frames limitados recebem seu próprio tratamento — quando o usuário escreve ROWS BETWEEN CURRENT ROW AND N FOLLOWING em vez de UNBOUNDED FOLLOWING, o executor encurta qualquer contexto cujo match tenha alcançado a fronteira forçando um mismatch, e absorption é desativado porque a fronteira quebra a suposição de monotonicidade na qual absorption se apoia.

3.5 O motor por linha de três fases

O driver por linha do executor é invocado pela maquinaria circundante de funções de janela sempre que ela precisa saber se uma dada linha pertence a um frame correspondido. O driver encontra ou cria o contexto para a posição inicial atual e, em seguida, conduz o NFA adiante linha a linha — redefinindo um array de match por variável para "não avaliado" a cada linha — até que esse contexto não tenha mais estados vivos ou a partição termine. Predicados DEFINE são avaliados sob demanda: uma variável é avaliada na primeira vez que algum estado a consome, então uma variável que nenhum estado vivo testa nesta linha nunca é avaliada. O passo à frente em si são três fases em uma ordem fixa — Match, Absorb, Advance — envolvidas no mesmo loop externo:

processRow(currentPos):

  # Fase 1 — MATCH (convergência)
  for cada contexto:
      if contexto alcançou seu fim de frame:
          forçar mismatch (finalizar cedo)
          continue
      if matchStartRow difere da
         posição de avaliação compartilhada:
          redefinir variáveis DEFINE dependentes
          do início do match para não avaliadas (§3.3)
      match(context, varMatched)

  # Fase 2 — ABSORB
  if padrão é absorbable:
      atualizar flags de cada contexto
      absorb_contexts()

  # Fase 3 — ADVANCE (divergência)
  for cada contexto:
      advance(context, currentPos)
      if registrou um match e
         SKIP PAST LAST ROW:
          podar contextos posteriores que
          começam dentro do match

A ordem não é uma escolha estilística. Match precisa rodar primeiro porque absorption compara contagens pós-match; rodar Absorb antes de Match compararia estados que estão prestes a morrer. Advance precisa rodar por último porque é a única fase que cria novos estados — expande cada estado sobrevivente por meio de transições epsilon até que cada um alcance uma variável esperando a próxima linha. Rodar Absorb após Advance significaria comparar sucessores divergentes, perdendo o ponto em que os estados são mais limpamente comparáveis.

Fase 1 — Match

Match é uma fase de "convergência": estados ou sobrevivem com a contagem incrementada, ou morrem. Um ponto sutil é que para variáveis em uma região absorvível, Match também executa um pequeno avanço para frente, para que Absorb possa comparar de forma limpa. A condição cover só dispara no comparison point absorvível — o END do grupo ilimitado — então estados que acabaram de corresponder a variáveis no meio da iteração (como B dentro de (A B)+) precisam ser levados até esse comparison point durante o próprio Match; caso contrário, Absorb não encontra nada elegível a comparar e a otimização nunca é ativada.

match(context, varMatched):
  for cada state em context:
      elem = pattern[state.elemIdx]
      assert elem é uma variável
          # advance estaciona apenas variáveis

      if varMatched[elem.varId] está
         não avaliado:
          avalia seu DEFINE agora
      if not varMatched[elem.varId]:
          descarta state   # ramo morto
          continue

      state.counts[elem.depth] += 1

      # Avanço inline para que a próxima
      # fase possa comparar no elemento
      # de comparison point em vez de
      # no meio de uma iteração.
      if elem está in-region mas não é
         o comparison point,
         e atingiu sua contagem máxima,
         e elem.next é um group end:

          percorre a cadeia de END:
            incrementa contagem do grupo externo
            avança state.elemIdx para END
            continua enquanto ainda in-region,
              must-exit e next é END
          (para no comparison point
           ou em um elemento ainda loopável)

O percurso da end-chain é o que torna grupos aninhados de comprimento fixo absorvíveis. Em ((A B){2})+, quando B alcança seu max (B é {1,1}), a contagem do grupo interno precisa ser incrementada; se essa contagem também alcançar seu max — fechando o {2} interno — a contagem do grupo externo também precisa ser incrementada, e assim por diante, até o estado pousar no ponto de absorption mais externo — o END do grupo externo ilimitado (o +). Fazer esse trabalho em Match permite a Absorb comparar contra contextos que já consolidaram suas contagens pós-iteração.

Fase 2 — Absorb

A passagem absorb percorre os contextos do mais novo (tail) ao mais antigo (head). Para cada contexto em andamento que seja totalmente absorvível, ela faz um scan para trás procurando um contexto em andamento mais antigo que o cubra e libera o mais novo se encontrado. Como contextos são mantidos na ordem de criação e cada linha cria no máximo um contexto, "mais novo" e "mais antigo" significam realmente "iniciado depois" e "iniciado antes".

absorb_contexts():
  for ctx do tail para trás:
      if ctx terminou
         ou tem algum estado não-absorbable
         ou mantém um match registrado:
          skip
      for older de ctx.prev para trás:
          if older terminou
             ou não tem estado absorbable:
              skip
          if covered(older, ctx):
              free(ctx)
              registra comprimento de absorption
              break

covered(older, newer):
  for cada state em newer:
      elem = pattern[state.elemIdx]
      if elem não é o comparison point:
          return false
      if não há state em older com:
            mesmo elemIdx
            e isAbsorbable
            e older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Duas microdecisões seguem disso. A primeira é que a verificação de cover rejeita imediatamente se qualquer estado no contexto mais novo estiver em qualquer lugar que não seja um comparison point — comparar em pontos que não são de julgamento não seria uma comparação significativa.

A segunda é o par de flags assimétricas em cada contexto: has-absorbable-state responde "este contexto poderia absorver um mais novo?" e é monotônico (só pode ir true→false conforme estados morrem), enquanto all-states-absorbable responde "este contexto poderia ser absorvido?" e é dinâmico (volta a true quando um estado não-absorbable é removido) até que o contexto registre um match, o que o fixa em false — absorver liberaria um match que nenhum contexto absorvente pode reproduzir. Ambas as flags são verificadas em tempo constante antes mesmo de o scan de cover começar, então absorption paga seu custo total apenas em contextos que têm chance real de serem absorvidos.

Fase 3 — Advance

Advance is the "divergence" phase: each surviving state is expanded through epsilon transitions until every branch reaches either a variable waiting for the next row or the FIN sentinel. The expansion is depth-first, and the order in which sibling branches are walked is what makes the standard's preferment rule actually take effect — the lexically first branch is always added first, and the deduplication step at state insertion silently discards equivalent later additions.

advance(context, currentPos):
  retira todos os estados atuais;
  reconstrói ctx.states do zero
  for cada state em ordem lexical:
      limpa o bitmap de visitados
      advance_state(state)   # DFS

      # Preferência: quando uma DFS atinge FIN,
      # os estados restantes são menos preferidos
      # e podem ser descartados.
      if FIN atingido e ainda há estados:
          libera os demais
          break

advance_state(state):
  percorre via state.elemIdx,
  recursão por:
    ramos ALT (em ordem, parando
               quando FIN é registrado),
    BEGIN (entra no grupo; mais caminho
           opcional de skip se min = 0),
    END (loop back / sair / fast-forward —
         ver abaixo),
    FIN (registra matchEndRow,
         salva matchedState e marca
         o contexto para que contextos
         posteriores dentro da faixa do
         candidato sejam podados — ver abaixo),
  parando em cada variável encontrada:
      adiciona state a ctx.states
      (deduplicando por elemIdx + counts)

Registrar um estado que alcançou FIN faz mais do que apenas marcar o match candidato. Sob AFTER MATCH SKIP PAST LAST ROW, o próximo match reportável precisa começar estritamente após o atual — então, assim que Advance termina com o contexto que registrou um candidato, todo contexto subsequente cuja linha inicial caia dentro da faixa do candidato é podado na mesma linha, mesmo que o contexto que atingiu FIN possa continuar buscando um match mais longo via greedy fallback.

A poda é segura porque não importa como essa busca termine (um match mais longo substitui o candidato, ou o candidato permanece): todos os contextos podados começaram dentro de uma faixa que o próximo match reportável precisa pular, e portanto nunca poderiam produzir saída própria.

Este é o passo de poda em FIN-time entre contextos. Dentro do contexto, FIN também corta trabalho lexicamente inferior: Advance descarta os estados restantes na fila (descrito antes nesta seção), e dentro de uma DFS todo caminho menos preferido — ramos ALT posteriores, o outro dos caminhos de skip e de entrada de BEGIN, o caminho de entrada de uma variável reluctant, o outro dos caminhos de loop e de saída de END — para assim que um match é registrado, então um advance registra no máximo um match.

A lógica por elemento mais delicada vive no handler de END. Quando a contagem de iteração de um grupo está abaixo do limite inferior, o runtime precisa fazer loop back; quando está em ou acima do limite superior, precisa sair; entre eles, ambas as opções são válidas e a greediness do quantificador decide qual tentar primeiro:

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

  if count < elem.min:
      loop back para o corpo
      if elem é empty-loopable:
          # corpo nullable, ver §3.2
          também clona um estado fast-forward
          que sai do grupo com contagem
          satisfeita
          (fast-forward primeiro se o
           corpo prefere vazio; o segundo
           caminho é descartado se o
           primeiro atingiu FIN)

  elif count >= elem.max:
      reseta counts nesta profundidade
      sai via next
      (END→END: incrementa contagem
       do END externo)

  else:
      # min <= count < max: bifurca
      constrói um estado de saída
      (counts nesta profundidade resetados)
      if greedy:
          loop primeiro
          if o loop atingiu FIN:
              descarta a saída
              # prefere mais longo
          else sair em segundo
      else (reluctant):
          sair primeiro
          if a saída atingiu FIN:
              descarta o loop
              # prefere mais curto
          else loop como segundo

Todo estado adicionado a um contexto passa por uma verificação de deduplicação que compara sua posição e contagens com a lista de estados existente. Como Advance processa ramos em ordem DFS, o estado do primeiro ramo de qualquer alternação chega primeiro — e qualquer ramo posterior que produza a mesma posição e contagens é rejeitado na inserção. Isso é exatamente o que a regra de ordem lexical de §2.4 pede, implementada no fundo do runtime sem uma passagem separada.

Grupos empty-loopable

Um caso sutil que o runtime precisa neutralizar é o grupo nullable — um grupo cujo corpo pode corresponder a zero linhas porque cada filho do corpo é, ele próprio, opcional. Padrões como (A? B?)+ e (A | B*)+ têm essa propriedade: dependendo dos dados, o corpo pode completar uma iteração sem consumir nenhuma linha. (Um único filho opcional como (A?)* é reescrito para A* em tempo de compilação e não deixa grupo para trás.) Em princípio, isso está bem, mas cria um perigo real para a expansão epsilon do NFA. Se o corpo produz um match vazio, o elemento END faz loop back para dentro do corpo (seu jump é o primeiro filho do grupo), o corpo novamente produz um match vazio, alcança END de novo, e assim por diante. Sem algo para parar isso, a DFS de Advance nunca terminaria.

O guard é decidido em tempo de compilação e acionado em runtime. Sempre que o planner vê um grupo cujo corpo é nullable, marca o elemento END desse grupo como empty-loopable. O runtime mantém um bitmap de visitados, limpo antes da expansão DFS de cada estado, no qual apenas esses ENDs marcados são registrados — nada mais pode formar ciclo, porque qualquer outro loop-back já consumiu uma linha. Alcançar um END registrado significa que o corpo acabou de derivar uma iteração vazia, e o estado não é descartado: em ou acima do limite inferior ele deixa o grupo ali (uma iteração vazia encerra o quantificador), e abaixo dele o estado segue para o loop-back normal, então cada chegada vazia ainda eleva a contagem até atingir min. Tome (A? B?){2,3} sem nenhuma das variáveis correspondendo em parte alguma do fluxo de linhas:

iter 1: A? B? correspondem a zero linhas
        → END, count = 1 (abaixo de min)
        END já registrado (na entrada
        do grupo), mas abaixo de min:
        → loop back para dentro de A?
iter 2: A? B? correspondem a zero linhas
        → END, count = 2 (atinge min)
        END já registrado, em min:
        → deixa o grupo
sai com um match de comprimento zero

Abaixo do limite inferior, a marca empty-loop também manda o handler de END clonar um estado adicional fast-forward ao lado do caminho normal de loop-back:

advance_end (count abaixo de min):

  caminho de loop-back:
    loop back para o corpo
    (mantém a porta aberta para um match
     real, não vazio, na próxima iteração)

  if elem é empty-loopable:
    caminho fast-forward:
      reseta a contagem desta profundidade
      sai do grupo via next,
      tratando as iterações requeridas
      restantes como matches vazios

Os dois caminhos têm papéis complementares. O loop-back cuida do caso em que o corpo ainda tem matches reais a produzir mais tarde — por exemplo, em (A? B?){2,3} seguido de dados em que A só corresponde em linhas posteriores, é o loop-back que permite à segunda e terceira iteração encontrar matches não vazios. O fast-forward sai do grupo de imediato, declarando "as iterações requeridas restantes são vazias", e permite que o match tenha sucesso com corpo de comprimento zero. É o corpo, e não a própria greediness do grupo, que decide a ordem: o fast-forward vai primeiro exatamente quando o corpo prefere o match vazio (um corpo reluctant como (A?? B??)), e se o primeiro caminho alcança FIN o segundo é descartado, de modo que um caminho menos preferido não pode substituir o match preferido. A verificação de deduplicação na inserção impede que qualquer caminho gere mais estados que sua cota.

Além do cycle guard, mais um truque de inicialização desambigua resultados de zero linhas no início de um contexto. O passo de criação de contexto, em cada linha de início potencial, executa um advance inicial por meio de transições epsilon antes de qualquer linha ser consumida, usando uma posição uma linha antes do início real. Qualquer caminho que alcance o sentinela FIN apenas por transições epsilon — sem consumir uma linha — produz, portanto, uma posição final menor que a posição inicial; essa coordenada de span negativo, combinada com se FIN foi realmente alcançado, codifica a diferença entre um match vazio (match de comprimento 0 aceito) e um início não correspondido sem precisar de um flag separado.

3.6 Como o espaço de estados permanece limitado

Manter o runtime limitado não é o resultado de uma única otimização. É o efeito cumulativo de um conjunto em camadas de regras de poda, cada uma capturando uma causa diferente de crescimento do espaço de estados em um ponto diferente do ciclo por linha. Algumas são decididas em tempo de compilação e apenas consultadas em runtime; outras disparam dinamicamente. Algumas matam estados individuais; outras matam contextos inteiros. As seções acima introduziram cada uma em contexto; a tabela abaixo as coloca em uma única página.

Predicado falho Match
Estados de variável cujo DEFINE avaliou falso na linha atual — ramos mortos.
Avanço inline da end-chain Match
Variáveis que atingiram a contagem máxima e que de outra forma deixariam o estado no meio da iteração; avançadas por ends de grupo de comprimento fixo para que absorption possa comparar no ponto certo.
Context absorption Absorb
Contextos mais novos cujos estados estão todos em um comparison point e são cobertos por um estado absorvível de um contexto mais antigo no mesmo elemento com contagem maior ou igual — ver §2.5 para a regra conceitual, §3.2 para a elegibilidade em tempo de compilação, §3.5 para a verificação por par.
Deduplicação de estados Advance
Estados alcançados por ramos DFS diferentes que terminam na mesma posição com as mesmas contagens — apenas o primeiro (lexicamente mais antigo) sobrevive; equivalentes posteriores são silenciosamente descartados, que é também como a preferência é imposta (§2.4).
Terminação antecipada em FIN (dentro do contexto) Advance
Estados ainda pendentes na fila DFS quando um ramo alcança FIN — pela ordem lexical, todos os estados restantes são menos preferidos e podem ser descartados imediatamente.
Poda de match candidato (entre contextos) Advance
Outros contextos cuja linha inicial cai dentro da faixa do match candidato — o contexto que atingiu FIN ainda pode continuar buscando um match mais longo (greedy fallback), mas sob AFTER MATCH SKIP PAST LAST ROW qualquer contexto dentro da faixa do candidato não pode mais produzir saída reportável, independentemente de como essa busca termine, e é podado assim que Advance termina com o contexto que registrou o candidato.
Cycle guard Advance
Expansões epsilon que alcançam o END de um grupo nullable já registrado dentro do mesmo DFS (registrado na entrada via BEGIN, ou em uma chegada anterior) — fariam loop para sempre; o estado deixa o grupo ali em ou acima do limite inferior, e continua em loop abaixo dele.
Empty-loop fast-forward Advance
Abaixo do limite inferior de um grupo nullable, um caminho extra que sai do grupo com as iterações requeridas restantes declaradas vazias, ordenado em relação ao loop-back pela preferência do corpo.
Cutoff de frame limitado Match
Contextos cujo match alcançou o limite superior do frame especificado pelo usuário — forçados a mismatch para não se estenderem além dele (§3.4).

Ler as entradas pela sua tag de fase rastreia a vida de um contexto: a poda dispara em cada linha pelas três fases principais (Match, Absorb, Advance). Ler as descrições, em vez disso, agrupa as regras pelo que elas miram: ramos mortos, contextos redundantes, estados equivalentes, loops infinitos e extensão excessiva além de fronteiras impostas pelo usuário.

Nenhuma regra isolada seria suficiente. Sozinho, o empty-loop fast-forward não pararia loops epsilon infinitos; sozinha, a absorption consolidaria demais quando DEFINE referencia o início do match; sozinha, a deduplicação não removeria contextos redundantes, apenas estados redundantes. O runtime permanece linear nos casos que importam — PATTERN (A+ B+ C+ D) em 100.000 linhas, o benchmark do painel ③ do pôster — apenas porque cada camada captura o que as camadas acima dela perdem. O código-fonte documenta casos que as camadas não capturam: a dedup mantém separados estados que diferem apenas em contagens acima de min, então (A{2,} B)+ C com C nunca verdadeiro mantém Θ(n²) estados no pico e cria Θ(n³) deles (37 s sobre 320 linhas), e uma sequência de alternações totalmente nullable é enumerada caminho a caminho, então (A?|B?){30} leva mais de meia hora.

3.7 Saída de EXPLAIN

EXPLAIN ANALYZE em uma consulta com RPR expõe estatísticas em nível de NFA que não estão presentes para funções de janela comuns. Em formato texto, elas são emitidas junto com o operador de janela, após a linha Pattern:, quaisquer linhas Nav Mark (que o EXPLAIN simples também mostra) e a linha Storage::

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (cada uma apenas quando DEFINE usa
   navegação que a 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)
  (segunda linha NFA apenas quando alguma
   das contagens é diferente de zero; uma
   contagem zero imprime sem seu (len ...))

Formatos não texto emitem cada contagem como sua própria propriedade. Peak e total são instrumentação direta do runtime: quantos estados estiveram vivos simultaneamente, quantos foram criados ao longo do tempo de vida da consulta e quantos foram fundidos pela deduplicação; pruned conta contextos que falharam após uma única linha. Os histogramas de comprimento de match separam quatro resultados — matches bem-sucedidos, tentativas de match que falharam após mais de uma linha (mismatched), contextos absorvidos e contextos liberados por AFTER MATCH SKIP PAST LAST ROW por terem começado dentro de um match registrado (skipped) — e reportá-los com min/max/avg torna patologias de desempenho visíveis num relance: uma execução saudável mostra a maioria dos contextos como matched ou absorbed, com comprimentos de mismatched pequenos.

Os dois contadores Nav Mark reportam o orçamento de retenção do tuplestore que §3.3 deriva de DEFINE. Lookback é o alcance mais profundo para trás a partir da linha atual através de PREV, LAST com qualquer offset (incluindo o padrão 0) e formas compostas com LAST interno; Lookahead é o alcance mínimo para frente (negativo quando olha antes do início do match) medido a partir do início do match do contexto vivo mais antigo, contribuído por FIRST e formas compostas com FIRST interno.

Cada contador imprime como um inteiro fixo quando o offset é uma constante, "runtime" quando o offset é uma expressão não constante conhecida apenas a cada scan, e — apenas para Lookback — "retain all" quando o offset estoura; um Lookahead que estoura imprime "infinite". Cada linha é emitida apenas quando alguma navegação em DEFINE a alimenta, e ambas aparecem também sob EXPLAIN simples: offsets constantes são fixados na inicialização do executor, enquanto um offset conhecido apenas em tempo de execução (um parâmetro de generic plan, por exemplo) imprime "runtime" ali e seu inteiro resolvido sob EXPLAIN ANALYZE.

Juntos, esses contadores tornam possível depurar o desempenho de RPR sem anexar gdb ao backend.

Além dos contadores, o EXPLAIN imprime uma linha Pattern: construída a partir do array de elementos compilado, então mostra o padrão após as reescritas de tempo de compilação (PATTERN (A A) é explicado como a{2}) e carrega os marcadores de absorption # (comparison point) e ~ (região absorvível); DEFINE e a opção AFTER MATCH SKIP não são mostrados. Reproduzir as cláusulas como escritas, incluindo quantificadores reluctant, repetição de grupo e a opção de skip, é tarefa de pg_get_viewdef(), que se esforça para tornar esse round-trip estável, de modo que pg_dump e pg_upgrade possam preservar objetos RPR sem deriva semântica — a suíte de regressão sob rpr_explain verifica isso caso a caso (ver §4).

§4. Testes — Mapa de Cobertura

O patch acompanha cinco suítes de regressão que juntas exercitam cada camada descrita em §3 — aproximadamente 22.000 linhas de SQL, cada suíte focada em uma preocupação diferente. A divisão é deliberada: manter as preocupações do parser, a correção do runtime, as interações do planner e a formatação de saída em arquivos separados torna as falhas mais fáceis de localizar e impede que uma mudança não relacionada em uma camada invalide acidentalmente testes em outra. As cinco suítes são:

rpr
Integração com a cláusula WINDOW — cenários realistas de janela sobre dados sintéticos de ações (forma de V, forma de W, altas consecutivas, reversões), além de semântica de navegação e erros de restrição de DEFINE.
rpr_base
Camada do parser — aceitação de palavras-chave, formas sintáticas, quantificadores, parsing de navegação, mensagens de erro e estabilidade do round-trip pg_dump/pg_upgrade; além de uma camada do planner — otimização de padrão, flags de absorption, fallback de otimização, integração com o planner.
rpr_nfa
Runtime do NFA — o loop de três fases, absorption em cada forma absorvível e casos extremos do ciclo de vida do contexto.
rpr_explain
Formatação de saída — estatísticas do NFA, deparse de padrão, aspas de identificadores, estabilidade de formato após reload.
rpr_integration
Interações do planner — guardas que impedem otimizações de janela não relacionadas de corromper a semântica de RPR.

4.1 rpr — cenários end-to-end

A suíte de cenários é a face pública do conjunto de testes: usa um dataset sintético de preços de ações com cerca de 1.600 linhas e executa consultas realistas sobre ele — recuperação em forma de V, forma de W (fundo duplo), altas e quedas consecutivas, padrões de reversão, partições multi-símbolo. Esses cenários são os únicos testes cujas entradas e saídas se leem como consultas que um usuário poderia realmente escrever; o restante do arquivo, como as outras suítes, é redutivo — aninhamento de PREV/NEXT e erros de offset não constante, regras de referência em DEFINE e semântica de offset de navegação.

Como essas consultas combinam todas as camadas (parser, planner, executor, EXPLAIN), uma única falha em rpr raramente diz onde o bug vive. As quatro suítes seguintes são a bisseção: uma falha em rpr mais um rpr_base passando descarta o parser; mais um rpr_nfa passando estreita para formas específicas de dados de cenário; mais um rpr_integration passando descarta interferência do planner; e qualquer drift de deparse aparece em rpr_explain.

4.2 rpr_base — a superfície do parser

A suíte base é a maior, e é a maior por uma razão: é responsável por provar que cada peça legal de sintaxe em §1.2 realmente faz parse, cada peça ilegal em §1.3 é rejeitada com um erro útil e cada forma aceita sobrevive a um round trip de serialização. A maior parte dela tem o formato de pequenos snippets focados — um por funcionalidade sintática — em vez de consultas longas e realistas, porque o objetivo é cobertura, não realismo de cenário. Uma segunda parte, a camada do planner, cobre otimização de padrão, exibição e análise de flags de absorption, fallback de otimização e integração com o planner (subconsultas, joins, operações de conjunto, ordenação e agrupamento).

Os testes de serialização merecem atenção especial. Objetos RPR (views, materialized views, saída de pg_dump) precisam fazer round-trip pela representação do catálogo sem deriva semântica, incluindo sutilezas como o flag reluctant em um quantificador ou a forma exata de uma expressão de navegação composta. Um pequeno conjunto de objetos específicos de serialização (as views rpr_serial_v* e suas tabelas de suporte) é intencionalmente deixado no lugar ao final da execução, para que a infraestrutura de regressão circundante possa pegá-los e exercitar pg_dump e pg_upgrade contra eles. O restante do andaime de teste é descartado como de costume. Defeitos como um flag reluctant perdido entre deparse e re-parse só aparecem quando o round-trip é exercitado de ponta a ponta.

4.3 rpr_nfa — o motor do runtime

Esta é a suíte que exercita cada mecanismo descrito em §3.5 e §3.6. Seus testes seguem um padrão consistente: linhas VALUES inline carregando um array de nomes de variáveis que declara quais variáveis DEFINE correspondem em cada linha, emparelhadas com um padrão que sonda um comportamento específico de runtime. O idioma do array desacopla o teste do runtime da maquinaria de avaliação DEFINE — o que está sendo testado é "dado que estas variáveis correspondem aqui, o loop NFA produz o span de match esperado?", e não "o avaliador de expressões DEFINE computa corretamente esses booleanos?". O avaliador DEFINE é testado em outro lugar (rpr_base para parsing, rpr para comportamento end-to-end).

Uma fixture típica de teste fica assim — uma coluna de arrays de nomes de variáveis em que cada entrada diz quais variáveis DEFINE disparam naquela linha, e um padrão cujas cláusulas DEFINE testam diretamente esses nomes:

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

Reading the array column down is reading the test scenario directly. Rows 2 and 3 carry both names — A and B both fire there, so the NFA has a real choice about where to switch from the A-leg to the B-leg. The expected match (A at rows 1–3 followed by B at row 4, under the standard's greedy preferment) is fixed by those flags alone, with no expression evaluation of any consequence here — = ANY is just the trivial layer that exposes the array column to DEFINE, not what the test exercises. Writing the same scenario with a numeric predicate (price > PREV(price) and similar) would tangle the NFA test with the predicate evaluator's behavior; the array idiom keeps the two cleanly separate, and a failure here points directly at the NFA loop.

A cobertura de absorption é particularmente minuciosa, porque absorption é a otimização com maior probabilidade de produzir respostas erradas silenciosamente caso ative quando não devesse. Os testes cobrem cada forma da análise de casos de §3.2:

Além de absorption, a suíte cobre o ciclo de vida do contexto: contextos sobrepostos sob AFTER MATCH SKIP TO NEXT ROW, limpeza de contextos falhos no meio do fluxo, finalização no fim da partição de contextos incompletos e contextos encontrados após um match candidato já ter sido registrado no contexto cabeça. Cada um deles mapeia para uma regra de poda específica em §3.6, e os testes são escritos para falhar ruidosamente se a regra disparar errado (deixando contextos redundantes vivos ou matando um contexto que deveria ter produzido saída).

4.4 rpr_explain — estabilidade da saída

A saída de EXPLAIN faz parte do contrato visível ao usuário — ferramentas de terceiros (dashboards de monitoramento, log scrapers) a fazem parse, e mudanças que parecem cosméticas podem quebrá-las. A suíte rpr_explain verifica três coisas:

Como rpr_base, esta suíte intencionalmente deixa seus objetos no lugar ao final da execução para que a cobertura de pg_dump e pg_upgrade se estenda também aos artefatos do lado do explain.

4.5 rpr_integration — interações do planner

O planner do PostgreSQL tem muitas otimizações que operam em consultas de janela — canonicalização de frame, run-condition pushdown, deduplicação de janelas idênticas, projeção de saída não usada, transições inversas de agregados móveis — e cada uma delas foi projetada sem ter RPR em mente. A maioria delas é insegura aplicar quando uma janela tem uma cláusula PATTERN: o frame faz parte do contrato do match, a saída correspondida não é mais monótona de qualquer maneira óbvia, e duas janelas com a mesma especificação mas DEFINEs diferentes produzem resultados genuinamente diferentes. A suíte de integração verifica como cada uma dessas otimizações trata janelas RPR — a maioria precisa ser desativada ou contornada:

Canonicalização de frame
O planner normalmente reescreve ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING como ROWS UNBOUNDED PRECEDING para funções de janela independentes de frame como row_number, rank e ntile. O frame de RPR é o span do match, não uma janela de agregação, e precisa permanecer verbatim.
Run-condition pushdown
Um filtro WHERE monótono na saída de uma função de janela normalmente pode ser empurrado para dentro do operador de janela como condição de parada. Em RPR, isso terminaria o pattern matching prematuramente, possivelmente cortando matches em meio à extensão.
Deduplicação de janelas (RPR vs não-RPR)
Duas janelas com ORDER BY e frame idênticos normalmente seriam fundidas em uma. Uma janela RPR e uma janela não-RPR nunca podem compartilhar estado porque o lado RPR carrega resultados de match.
Deduplicação de janelas (DEFINE ou SKIP diferente)
Duas janelas RPR com o mesmo PATTERN, mas com cláusulas DEFINE diferentes ou um AFTER MATCH SKIP diferente produzem matches diferentes e precisam permanecer distintas, mesmo que sua forma estrutural seja idêntica.
Projeção de saída não usada
Esta pode ser aplicada: quando a consulta circundante nunca lê a saída da janela, a função de janela se torna NULL e seu WindowAgg é removido, deixando a contagem de linhas inalterada. Os testes verificam que as colunas que DEFINE lê ainda chegam ao WindowAgg quando ele permanece, e que a janela é mantida quando seu valor é lido.
Transições inversas de agregados móveis
Agregados de janela com função de transição inversa normalmente podem ser avaliados incrementalmente conforme o frame se move. O reduced frame de RPR não é uma janela deslizante; o caminho de transição inversa produziria resultados errados.

Casos adicionais verificam que a estimativa de custo leva DEFINE em conta, que uma subconsulta contendo uma janela RPR não é achatada, que expressões DEFINE não vazam para um WindowAgg superior e que LIMIT permanece acima do WindowAgg; um segundo grupo executa RPR junto com CTEs, joins, operações de conjunto, prepared statements, tabelas particionadas e construções similares. A maioria dos casos protegidos segue a mesma forma: uma baseline que dispara a otimização (geralmente uma consulta não-RPR, verificada no EXPLAIN), depois uma consulta RPR de forma estruturalmente similar em que a otimização não é aplicada — para o caso de dedup de DEFINE/SKIP a baseline são duas janelas RPR idênticas, e o caso de transição inversa verifica o contorno com um agregado de logging em vez do EXPLAIN. As duas metades juntas provam que a guarda no planner está fazendo trabalho real, e não aprovando toda consulta sem verificação real.

Esta suíte é também a razão pela qual §3.4 é curta. Os mecanismos de "fronteiras de match" — reduced frame, SKIP, INITIAL, cutoff de frame limitado — são testados operacionalmente em outro lugar; o que rpr_integration verifica é que nenhum outro estágio do otimizador os adultera no caminho. Um rpr_integration que passa é o que permite às demais suítes confiar que suas entradas chegam ao executor sem serem violadas.