Row Pattern Recognition Mergulho Profundo

§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 compartilham a maior parte da sintaxe e toda a semântica, 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 três cláusulas dentro da especificação da janela: PATTERN descreve uma expressão regular sobre variáveis de padrão nomeadas, DEFINE fornece o predicado booleano que identifica cada variável e AFTER MATCH SKIP 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.

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 é uma expressão de valor arbitrária avaliada 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.

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 label, AFTER MATCH SKIP TO FIRST var e AFTER MATCH SKIP TO LAST var. Estes também dependem do histórico do match, pois o executor precisa apontar para uma linha rotulada específica 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 {- … -} e o operador PERMUTE insensível à ordem.

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 ponto da janela (em contraste com INITIAL).

AFTER MATCH SKIP TO label

Skip para uma linha rotulada.

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 por match.

Regex: ()

Padrão vazio — corresponde à sequência vazia.

PERMUTE(...)

Correspondência insensível à ordem entre as variáveis listadas.

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 (avaliação por linha contra linhas já mapeadas para uma variável), o que depende do mesmo histórico por match exigido por MEASURES/CLASSIFIER().

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; e RPR não pode ser usado dentro de uma consulta recursiva.

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.

§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 três traces ponta a ponta: um único match (movimento do NFA), context absorption no caso fácil e o caso em que absorption se torna inseguro.

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.

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. Look-ahead para frente; pouco comum na forma de janela, pois a janela é monótona.

FIRST(expr [, n])

A n-ésima linha correspondida do match atual, contando do início. "Compare com a linha que iniciou este match."

LAST(expr [, n])

A n-ésima linha correspondida mais recentemente. "Compare com a linha de match mais recente."

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 n-ésima linha do match (padrão 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 n-ésima linha do match. 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 n-ésima linha correspondida mais recentemente. "Compare com uma linha pouco antes do último match."

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

Passo m linhas para frente a partir da n-ésima linha correspondida mais recentemente.

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 são relativos à linha atual e são sempre seguros; FIRST e variantes com offset de LAST são relativos às fronteiras do match, o que interage com context absorption e força o planner a manter vivos alguns contextos que ele descartaria. O mecanismo por trás dessa interação é o tema de §2.6.

2.3 Exemplo prático 1 — Movimento do NFA

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

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:

O ponto-chave: na linha 3, a linha satisfaz tanto START (sempre verdadeiro) quanto DOWN, mas o único estado que sobreviveu à linha 2 está no ramo de saída de DOWN, portanto apenas a transição UP → DOWN é tomada. 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 candidato FIN anterior (linhas 0–4) — produzido quando DOWN saiu na linha 4 — é 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:

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

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 em sincronia.

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. Eles seguem em paralelo até que DONE os resolva.

Ambos os ramos produzem um match do mesmo comprimento sobre as mesmas linhas, deixando o matcher com 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.

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)

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

A memória cresce de O(n) para O(1). A regra de absorption que justifica o descarte é direta quando o quantificador é ilimitado:

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:

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

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

Sob absorption, C2 teria sido fundido em C1 na terça — o contexto fundido mantém apenas um teto, portanto a visão distinta de C2 (teto $118, o run de quatro dias que só termina no sábado) não é mais recuperável a partir do estado interno. C2 precisa permanecer vivo porque é um candidato a match independente que o runtime ainda pode precisar: quando o match de C1 termina na quarta, a próxima tentativa precisa retomar de um C2 ainda em curso, em vez de recomeçar do zero. 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 de dependência no painel inferior direito do pôster ("② Navigation") resume quais formas de navegação criam dependência do início do match:

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 pode recuperar, e descartar qualquer um deles arrisca produzir uma resposta errada.

O planner detecta essa distinção em tempo de compilação e decide por contexto se absorption se aplica. É por isso também que o benchmark do pôster no painel ③ permanece linear tanto nos casos de sucesso quanto de falha: quando absorption é seguro, o runtime colapsa contextos; quando não é, o planner aceita o custo multi-contexto em vez de arriscar uma resposta errada.

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 em O(n) uma vez que um match é confirmado, e a vantagem do PostgreSQL — aproximadamente 16× a 33× — é majoritariamente a diferença da JVM.

No padrão de falha (A+ B+ C+ E), o Trino não tem absorption e degrada para O(n²) perseguindo cada potencial início de match; 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

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.

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á o quadro completo de quando absorption falha:

Qualquer das duas condições basta para desativar absorption para os contextos afetados. Quando nenhuma está em vigor — o padrão AFTER MATCH SKIP PAST LAST ROW com condições DEFINE que usam apenas PREV, NEXT ou LAST sem offset — o runtime colapsa para um único contexto por posição de padrão e permanece linear até o fim.

§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 memória 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 e opções EXCLUDE 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:

Each DEFINE predicate is then type-checked against the partition's columns and coerced to a Boolean expression. Two practical things happen as part of this. First, every column referenced by a DEFINE predicate is registered as part of the query's output requirements, so the planner propagates those columns through to the executor stage even if the surrounding query does not select them — without that, the runtime would have nothing to evaluate against. Second, variables that appear in the PATTERN but never in the DEFINE are implicitly true: they match every row.

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 oito regras de reescrita em sucessão até que o AST pare de mudar:

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}

Absorçã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

A multiplicação de quantificadores é a única transformação que requer uma verificação de segurança: o otimizador colapsa apenas em três casos seguros — ambos os quantificadores ilimitados ((A+)+ → A+), externo exato ((A{2,3}){5} → A{10,15}) ou filho trivial {1,1} ((A){2,5} → A{2,5}). 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 — então o otimizador as deixa intactas.

Forma do elemento

Cada elemento do array plano representa uma única posição no padrão. Há cinco 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; 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 pela alternação para encadear ramos, pelo group begin para contornar o corpo quando o quantificador permite zero, 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 → 4
    (abre grupo; jump pula
     para FIN quando min = 0)

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

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

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (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 pularia o END para o idx 4 se o grupo fosse opcional. 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 quatro 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?)*, (A? B?)+, (A | B*)). Diz ao runtime para adicionar uma saída fast-forward junto ao loop-back normal, para que o cycle guard não mate matches legítimos em grupos que podem produzir iterações vazias.

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 AST 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 pelo AST admite três 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 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 flags são definidas apenas em A.

Os casos estruturais não cobertos por essas três 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. (Uma extensão de continuação chamada "PREFIX absorption" que trata prefixos de comprimento fixo via um shadow path foi projetada e está planejada para um patch separado.) 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
  busca linha em targetPos
    para current_row_slot
  result = eval_inner_expression()
  restaura current_row_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, sem shadow slot, sem cópia de tupla.

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 lastMatchedRow − 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 (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      return (lastMatchedRow − 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 o estado em torno é elegível para context absorption (§2.5 vs §2.6).

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 patch decide em tempo de compilação, a partir de dois offsets complementares:

Orçamento de Lookback

Quão longe para trás, a partir da linha atual, qualquer chamada DEFINE pode alcançar.

Contribuintes: PREV, LAST com offset, PREV(LAST(...)), NEXT(LAST(...))

Orçamento de Lookahead-from-start

Quão longe para frente (ou para trás, quando negativo) a partir do início do match do contexto vivo mais antigo qualquer chamada DEFINE pode alcançar.

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. Os dois contadores Nav Mark que o EXPLAIN reporta (§3.7) — Lookback e Lookahead — são os picos medidos dos dois orçamentos, o mais profundo que o executor jamais teve de alcançar em qualquer direção ao longo da consulta.

3.4 Fronteiras de match — SKIP, INITIAL e frame limitado

Um match bem-sucedido é registrado como um pequeno conjunto de valores: um flag de validade, um flag de sucesso/falha, a linha em que o match começa e o número de linhas que ele consumiu. Quando o flag de validade está definido, consultas subsequentes ao executor — "esta linha está dentro de um match?" — podem responder em O(1) inspecionando o conjunto. 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 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 todo o plano de consulta 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, avalia cada predicado DEFINE uma vez contra a linha atual para produzir um array booleano por variável e, em seguida, conduz o NFA uma linha à frente. 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 excede frame limitado:
          forçar mismatch (finalizar cedo)
          continue
      if matchStartRow difere da
         posição de avaliação compartilhada:
          reavaliar variáveis DEFINE
          dependentes do início do match (§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)

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]
      if elem não é uma variável:
          continue   # advance trata

      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:
          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). 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 elementos 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),
    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 poda
         contextos posteriores dentro
         da faixa do candidato — 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, no momento em que um candidato é registrado, todo contexto subsequente cuja linha inicial caia dentro da faixa do candidato é podado imediatamente, 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 é um dos dois passos de poda em FIN-time — o outro, descrito antes nesta seção como parte de Advance, descarta estados lexicamente inferiores dentro do mesmo contexto.

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
          (resgata matches legítimos que o
           cycle guard mataria de outra forma)

  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, depois sair
          # prefere mais longo
      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?)*, (A? B?)+ e (A | B*) têm essa propriedade: dependendo dos dados, o corpo pode completar uma iteração sem consumir nenhuma linha. 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 BEGIN, o corpo novamente produz um match vazio, BEGIN faz loop para END, e assim por diante. Sem algo para parar isso, a DFS de Advance nunca terminaria.

O runtime detém isso com um bitmap de elementos visitados (um bit por elemento de padrão), limpo antes da expansão DFS de cada estado: assim que qualquer elemento é visitado pela segunda vez dentro da mesma expansão, esse caminho é abandonado. O cycle guard é incondicional e barato, mas tem um efeito colateral — também pode abandonar caminhos que deveriam alcançar o limite inferior por meio de iterações vazias legítimas. Tome (A?){2,3} sem nenhum A correspondendo em parte alguma do fluxo de linhas:

comportamento desejado:
  iter 1: A? corresponde a zero linhas
          → END, count = 1 (abaixo de min)
  iter 2: A? corresponde a zero linhas
          → END, count = 2 (atinge min)
  sai com um match de comprimento zero

o que o cycle guard faz sozinho:
  iter 1: A? pulado → END, count = 1
          → loop back para BEGIN
  iter 2: BEGIN já visitado
          → DFS aborta
  count nunca alcança min
  → match falha (incorreto)

A correção é decidida em tempo de compilação e acionada em runtime. Sempre que o planner vê um grupo cujo corpo é nullable, marca o elemento END desse grupo como empty-loopable. Em runtime, quando o handler de END está prestes a fazer loop back porque a contagem de iteração ainda está abaixo do limite inferior, a marca empty-loop manda clonar um estado adicional fast-forward ao lado do caminho normal de loop-back:

advance_end (count abaixo de min):

  caminho primário:
    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 primário cuida do caso em que o corpo ainda tem matches reais a produzir mais tarde — por exemplo, em (A?){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 cuida do caso em que o corpo nunca produz nada: contorna o cycle guard saindo do grupo inteiramente, declarando "as iterações requeridas restantes são vazias", e permite que o match tenha sucesso com corpo de comprimento zero. Ambos os estados são adicionados ao contexto; o que se estender com sucesso vence, e 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

A linearidade do runtime 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 são todos cobertos por estados de um contexto mais antigo com contagem maior — 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) On FIN

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 de imediato.

Cycle guard Advance

Expansões epsilon que revisitam o mesmo elemento de padrão dentro do mesmo DFS — fariam loop para sempre em grupos nullable.

Empty-loop fast-forward Advance

Matches legítimos de iteração vazia que o cycle guard mataria em grupos nullable — contorna o ciclo saindo do grupo com as iterações requeridas restantes declaradas vazias.

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), e novamente na conclusão do match (On FIN). 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 cycle guard mataria matches legítimos em grupos nullable; 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.

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. Três grupos de contadores são emitidos junto com o operador de janela:

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

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. Os histogramas de comprimento de match separam quatro resultados — matches bem-sucedidos, tentativas de match falhas, contextos absorvidos e contextos podados (skipped) sem terem sido avaliados — 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 em tempo de compilação. Lookback é o alcance mais profundo para trás através de PREV, LAST com offset e formas compostas com LAST interno; Lookahead é o alcance mais profundo para frente (ou para trás, quando negativo) 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 que precisa ser avaliada a cada chamada, e "retain all" quando o runtime precisa de orçamento ilimitado. Lookahead é emitido apenas quando a consulta usa de fato navegação relativa ao início do match.

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

Além dos contadores, o EXPLAIN também reproduz fielmente as cláusulas PATTERN e DEFINE originais, incluindo quantificadores reluctant, repetição de grupo e a opção AFTER MATCH SKIP. A implementação 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 13.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

Semântica de consulta end-to-end — cenários realistas de janela sobre dados sintéticos de ações (forma de V, forma de W, altas consecutivas, reversões).

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.

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. É a única suíte em que as entradas e saídas se leem como consultas que um usuário poderia realmente escrever; as outras são deliberadamente redutivas, focadas em uma única camada por vez.

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.

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. Bugs capturados desta forma (como um flag reluctant sendo 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: uma tabela de entrada cujas linhas são arrays booleanos explícitos declarando quais variáveis DEFINE correspondem em cada linha, emparelhada com um padrão que sonda um comportamento específico de runtime. O idioma do array booleano 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:

• variável simples ilimitada (A+) — o colapso canônico N-para-1;
• grupos de comprimento fixo ((A B)+, (A B{2})+, aninhamento de três níveis ((A (B C){2}){2})+);
• variável ilimitada inicial com sufixo fixo (A+ B) — apenas o A+ inicial carrega flags de absorption, o sufixo não;
• absorption por ramo dentro de uma alternação (B+ C | B+ D);
• múltiplas variáveis ilimitadas (A+ B+) — apenas a inicial é absorvível;
• quantificadores reluctant (A+?) — verificados como excluídos de absorption;
• ilimitada não inicial (A B+) — verificada como excluída.

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 (autocomplete do psql, 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:

• Os contadores NFA aparecem no lugar certo — as estatísticas por WindowAgg (peak/total/merged states, peak/total/pruned contexts, histogramas de comprimento para matched/mismatched/absorbed/skipped, Nav Mark Lookback e — quando a navegação relativa ao início do match está em uso — Nav Mark Lookahead) aparecem todas sob EXPLAIN ANALYZE com os rótulos documentados.
• Os padrões fazem deparse corretamente — cada forma de quantificador, incluindo variantes reluctant e formas limitadas; cada alternação; cada grupo; cada forma de AFTER MATCH SKIP; INITIAL; chamadas de navegação com offsets; navegação composta. O texto deparsed precisa fazer round-trip de volta pelo parser sem alteração.
• O quoting de identificadores está correto — variáveis de padrão e expressões DEFINE são emitidas com as mesmas regras de quoting que identificadores SQL comuns, para que nomes de variável incomuns não quebrem a saída do pg_dump.

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 que cada uma dessas otimizações é corretamente desativada ou contornada para janelas RPR:

Canonicalização de frame

O planner normalmente reescreve ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING como ROWS UNBOUNDED PRECEDING para agregados monótonos. 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 diferente)

Duas janelas RPR com o mesmo PATTERN, mas com cláusulas DEFINE diferentes produzem matches diferentes e precisam permanecer distintas, mesmo que sua forma estrutural seja idêntica.

Projeção de saída não usada

Mesmo que a consulta circundante nunca leia a saída por linha da janela, a janela RPR não pode ser removida: os efeitos colaterais do pattern matcher (quais linhas estão dentro de qual match) alimentam computações de reduced frame em outros pontos do plano.

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.

O padrão entre esses testes é o mesmo: cada um fornece uma baseline não-RPR que dispara a otimização (e verifica que o EXPLAIN mostra que ela está sendo aplicada) e depois executa uma consulta RPR de forma estruturalmente similar e verifica que a otimização não é aplicada. 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.