2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition a fondo

Recorrido guiado por ISO/IEC 19075-5 · SQL R020 en PostgreSQL — qué se construyó, qué queda aún por escribir y cómo funciona realmente.

Material complementario al póster expuesto en PGConf.dev 2026.
Repase el estándar, siga los ejemplos resueltos, explore el diseño y, finalmente, ejecute un simulador NFA en vivo con sus propios patrones.
Discusión: hilo pgsql-hackers · último parche (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

Pre-traducido por IA — errores posibles.

§1. El estándar, el subconjunto y las cuestiones abiertas

1.1 Alcance del estándar

Row Pattern Recognition fue introducido en SQL por ISO/IEC 9075-2:2016 y se describe en el documento complementario ISO/IEC 19075-5:2021 (Parte 5, "Row Pattern Recognition").

El estándar define dos superficies sobre la misma maquinaria subyacente. La característica R010 coloca una cláusula MATCH_RECOGNIZE en la lista FROM para producir una tabla derivada; la característica R020 integra la misma lógica de patrones dentro de una especificación WINDOW para producir salida de función de ventana. Las dos superficies tienen en común una parte considerable de su sintaxis y su semántica (19075-5 señala algunas diferencias específicas de R020 en §6.3.3), pero son puntos de entrada funcionalmente distintos — una base de datos puede implementar una, otra o ambas.

La serie de parches que se discute aquí implementa un subconjunto de R020 únicamente; la forma de cláusula de tabla queda deliberadamente fuera de alcance.

La superficie R020 es pequeña pero expresiva. Una consulta adjunta un patrón a una ventana añadiendo cláusulas dentro de una especificación de ventana cuyo frame es ROWS BETWEEN CURRENT ROW AND …: PATTERN describe una expresión regular sobre variables de patrón nombradas, DEFINE proporciona el predicado booleano que identifica cada variable, y el AFTER MATCH SKIP opcional (por defecto PAST LAST ROW) controla cómo se posicionan las coincidencias sucesivas dentro de la partición.

Las cláusulas opcionales MEASURES, SUBSET, INITIAL/SEEK y la función auxiliar CLASSIFIER() completan la característica. (La función MATCH_NUMBER() del estándar pertenece únicamente a la superficie R010 — 19075-5 §6.3.3 (6) la excluye explícitamente de R020.)

El parche cubre suficiente de este vocabulario como para que consultas no triviales funcionen, pero se detiene antes de varias construcciones cuya implementación depende de infraestructura que aún no se ha construido.

El resto de esta sección reparte el vocabulario del estándar entre lo que el parche ya soporta y lo que deja intencionadamente para más adelante. Las listas siguientes reflejan el estado actual de la serie de parches.

1.2 Características implementadas

El vocabulario implementado basta para expresar los patrones canónicos en V, en W y de inversión que motivan en primer lugar el row pattern recognition. También cubre todos los cuantificadores estándar — incluidas las siete variantes reluctantes *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — y las cuatro primitivas de navegación que las condiciones DEFINE necesitan para comparar filas adyacentes.

Cláusula PATTERN
Define el patrón de filas dentro de una especificación de ventana; hasta 240 variables de patrón distintas.
Frame de ventana
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING o ROWS BETWEEN CURRENT ROW AND n FOLLOWING con n ≥ 1 (19075-5 §6.10.2); cualquier otro frame se rechaza, y EXCLUDE NO OTHERS es la única exclusión aceptada.
Regex: + * ? |
Cuantificadores estándar y alternación.
Regex: agrupación ( )
Subpatrones entre paréntesis.
Regex: {n} {n,} {,m} {n,m}
Conteos de repetición acotados.
Reluctantes *? +? ?? {n}? {n,}? {,m}? {n,m}?
Las siete variantes reluctantes (no codiciosas) que define el estándar (excluidas de la optimización por absorción).
Cláusula DEFINE
Condiciones booleanas que identifican cada variable de patrón.
Variable universal de patrón de fila
Las referencias de columna no calificadas en DEFINE (p. ej., Price desnudo) se resuelven a la fila actual, según 19075-5 §4.10/§4.16.
PREV, NEXT (con desplazamiento)
Acceden a la fila n antes/después de la fila actual (por defecto 1); el argumento interno se evalúa en la fila navegada.
FIRST, LAST (con desplazamiento)
Acceden a una fila relativa al match; FIRST(expr, n) apunta a la fila n posiciones después del inicio del match, LAST(expr, n) a la fila n posiciones antes de la fila más reciente del match.
Navegación compuesta (cuatro formas)
Un paso externo PREV/NEXT superpuesto a un FIRST/LAST interno: PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — tanto el paso interno como el externo aceptan su propio desplazamiento.
Nombres de navegación
PREV, NEXT, FIRST y LAST escritas como llamadas no calificadas dentro de DEFINE siempre significan navegación; una función de usuario con el mismo nombre debe calificarse con el esquema allí.
Argumentos de navegación
Para PREV, NEXT, FIRST y LAST, el argumento interno debe contener al menos una referencia a columna y el desplazamiento debe ser una constante en tiempo de ejecución.
INITIAL
Las coincidencias del patrón deben comenzar en la fila actual (por defecto).
AFTER MATCH SKIP PAST LAST ROW
Modo de salto por defecto; admite absorción de contextos.
AFTER MATCH SKIP TO NEXT ROW
Permite coincidencias solapadas; deshabilita la absorción.

1.3 No implementadas

Las características que permanecen sin implementar se agrupan, de forma laxa, en tres conjuntos. El primero — con diferencia el más amplio — es la familia de construcciones centradas en MEASURES: la propia cláusula MEASURES, SUBSET, CLASSIFIER(), las referencias a columnas calificadas por patrón como B.price, y la navegación calificada por patrón como LAST(B.price) o PREV(B.price).

No se trata tanto de carencias independientes como de distintas vistas de una misma pieza ausente: el executor tendría que retener un historial por match — un registro, para cada fila del match, de a qué variable de patrón se asignó — y ninguna de estas construcciones tiene un significado bien definido sin él. CLASSIFIER() lee el nombre de variable de ese registro; B.price lee la columna price de las filas cuya entrada de registro indica B; LAST(B.price) recorre ese mismo conjunto de filas y selecciona la última; SUBSET U = (A, B) define una variable virtual que agrega sobre ambos cubos; y MEASURES evalúa expresiones como AVG(U.Price) usando precisamente esa agregación.

El executor actual evalúa los predicados DEFINE fila por fila, pero no registra en ningún sitio las asignaciones de variables resultantes — no hay nada que consultar después. Construir la infraestructura de historial es, por tanto, el prerrequisito de todo el grupo; las características individuales emergen como pequeñas proyecciones una vez que existen los registros.

El segundo conjunto se refiere a destinos alternativos de skip: AFTER MATCH SKIP TO FIRST var y AFTER MATCH SKIP TO [LAST] var (SKIP TO var a secas significa SKIP TO LAST var). Estos también dependen del historial de match, ya que el executor debe poder apuntar a la fila asignada a una variable dada dentro del match más reciente.

Los elementos restantes forman una cola heterogénea: la palabra clave SEEK (la alternativa a INITIAL), el patrón vacío (), la forma de exclusión {- … -}, el operador insensible al orden PERMUTE, y las funciones de agregación y subconsultas en DEFINE, ambas rechazadas actualmente (una agregación calificada por variable también necesitaría el historial de match).

MEASURES
Expresiones de salida nombradas por match, p. ej. MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg; en R020 se exponen vía OVER como una función de ventana. Acepta las palabras clave FINAL / RUNNING (19075-5 §5.4), que en R020 colapsan al mismo valor, ya que las measures siempre se evalúan en la última fila del match (19075-5 §6.9 (3)).
SUBSET
Uniones nombradas de variables de patrón, p. ej. SUBSET U = (A, B, C). Utilizable allí donde se pueda referenciar una variable de patrón — MEASURES, referencias calificadas por patrón en DEFINE, CLASSIFIER(U) — todas las cuales requieren historial de match.
CLASSIFIER()
Devuelve como qué variable de patrón se asignó una fila dada. Definida tanto para DEFINE como para MEASURES (19075-5 §5.9); la respuesta en cualquier fila es el nombre de variable registrado en el historial de match para esa fila.
Referencia a columna calificada por patrón
B.price a secas en DEFINE o MEASURES — el valor de la columna en la fila asignada como la variable nombrada.
Navegación calificada por patrón
Restringe la navegación a las filas asignadas como una variable nombrada, p. ej. LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).
SEEK
El match puede comenzar en cualquier fila desde la fila actual hasta el final del frame de ventana completo (frente a INITIAL).
AFTER MATCH SKIP TO FIRST var
Salta a la primera fila asignada como la variable nombrada.
AFTER MATCH SKIP TO [LAST] var
Salta a la última fila asignada como la variable nombrada.
Regex: {- -}
Exclusión — elimina las filas coincidentes de la salida de ALL ROWS PER MATCH. Esa opción no se aplica a las ventanas (19075-5 §6.3.3 (4)), por lo que en una ventana la sintaxis está permitida (§6.13) pero no tiene salida sobre la que actuar.
Regex: ()
Patrón vacío — coincide con la secuencia vacía.
PERMUTE(...)
Coincidencia insensible al orden sobre las variables listadas. La palabra clave se reconoce y se rechaza ("PERMUTE is not supported"); permute sigue pudiendo usarse como nombre de variable de patrón.
Funciones de agregación en DEFINE
Agregaciones como SUM, AVG, COUNT no se permiten en los predicados DEFINE. El estándar las admite como agregaciones acumulativas sobre el match parcial; una agregación calificada por variable como AVG(B.Price) depende del mismo historial por match que requieren MEASURES/CLASSIFIER(), mientras que una no calificada abarca todas las filas del match hasta el momento.
Subconsultas en DEFINE
Toda subconsulta en DEFINE se rechaza. El estándar permite una que no realice row pattern recognition y no referencie ninguna variable de row pattern; por ahora el parche rechaza de más.

Cuatro puntos adicionales merecen mención aquí, ya que son fáciles de confundir con omisiones.

El primero es que los anclajes de patrón ^ y $ no están permitidos con RPR en la cláusula WINDOW por el propio estándar (19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; con la definición subyacente en 19075-5 §4.14.1); su ausencia es conformidad, no una carencia.

El segundo es que MATCH_NUMBER() también está excluido de R020 por el estándar (19075-5 §6.3.3 (6) y 19075-5 §6.9 (1)) — pertenece únicamente a la superficie R010, y su ausencia aquí es de nuevo conformidad y no una característica faltante.

El tercero es un conjunto de prohibiciones estructurales que el estándar impone sobre R020 (19075-5 §6.17): row pattern recognition no puede anidarse dentro de otro row pattern recognition; MEASURES y DEFINE no pueden contener referencias externas; las subconsultas dentro de MEASURES o DEFINE no pueden referenciar variables de row pattern (el parche va más allá y rechaza toda subconsulta en DEFINE, como se indica arriba); y RPR no puede usarse dentro de una consulta recursiva. El parche aplica la regla de referencias externas ("cannot use outer query column in DEFINE clause") y la regla de recursión, esta última para cada elemento de una cláusula WITH RECURSIVE. También rechaza las funciones volátiles y las referencias a la fila completa en DEFINE.

El cuarto es que el propio MATCH_RECOGNIZE — Característica R010, la superficie de cláusula de tabla de la misma maquinaria — queda fuera de alcance para este parche. Si PostgreSQL acabará añadiendo R010 será una cuestión para una serie futura, no una medida de esta.

Procedencia. Las listas de implementadas y no implementadas de esta sección reflejan el estado actual de la serie de parches — concretamente v55 (2026-11-17).

§2. Ejemplos — cómo funciona realmente

Los ejemplos de esta sección se construyen de forma incremental. Se parte de la razón conceptual por la que la coincidencia de patrones de filas es genuinamente distinta de la coincidencia de patrones de texto, después se introducen las cuatro funciones de navegación que dan interés a las condiciones DEFINE, y finalmente se recorren cinco ejemplos resueltos: un único match (movimiento del NFA), alternación, absorción de contextos en el caso fácil y dos casos en los que la absorción se deshabilita.

El mecanismo interno que hace barata la navegación — el intercambio de tuplas de 1 slot — pertenece al diseño del executor y se cubre en la sección siguiente, no aquí.

2.1 Por qué los patrones de filas difieren de los patrones de texto

Una expresión regular de texto opera sobre un flujo de caracteres y, en cada posición, hay exactamente un símbolo a considerar. La pregunta en tiempo de ejecución — "¿el símbolo actual es igual a 'A'?" — tiene una única respuesta de sí/no. Los autómatas con backtracking lo aprovechan: como mucho una rama sobrevive por carácter, y el coste de la ambigüedad se paga releyendo la entrada.

Un patrón de filas es distinto de manera fundamental. Una fila no es un único símbolo; es una tupla de columnas evaluada contra un conjunto de predicados booleanos, las condiciones DEFINE. Dos predicados pueden ser verdaderos en la misma fila a la vez, y nada en el estándar dice que deban ser mutuamente excluyentes. Considere:

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

Una fila con price = 150, volume = 2000 satisface tanto A como B, pero no C. El motor de patrones no puede colapsar esto a un único estado — hay dos variables de patrón vivas, y cualquier elemento del patrón que nombre a alguna de ellas puede avanzar. El NFA debe, por tanto, llevar múltiples estados simultáneos por fila de partición, no uno solo.

Text regex vs row pattern: a single state advances per symbol, while multiple DEFINE predicates can match a row in parallel. TEXT REGEX single state advances through symbols A B C one symbol per position · one transition ROW PATTERN one row, multiple predicates evaluated row price = 150 · volume = 2000 A ✓ price > 100 B ✓ volume > 1000 C ✗ price > 200 two predicates true · two states stay alive
Una regex de texto colapsa a un estado por símbolo; una fila puede satisfacer varios predicados DEFINE a la vez, por lo que varios estados permanecen vivos en paralelo.

Esta sola observación determina el resto de la arquitectura. El estado de ejecución es una lista de contextos, cada contexto es una lista de estados, y en cada fila el runtime pregunta a cada estado: "dadas las variables que son verdaderas aquí, ¿a dónde puedo ir?" Las bifurcaciones resultantes son la razón por la que el runtime necesita varias capas de poda — deduplicación de estados dentro de un contexto, absorción entre contextos y las demás reglas reseñadas en §3.6 — sin las cuales el número de estados y contextos vivos crece con la partición y la coincidencia de patrones se vuelve superlineal.

2.2 Funciones de navegación

Las condiciones DEFINE que solo referencian la fila actual son limitadas; casi cualquier patrón interesante necesita comparar la fila actual con sus vecinas o con las filas ya aceptadas anteriormente en el match. El estándar proporciona cuatro funciones de navegación para ello, y el parche las implementa todas.

PREV(expr [, n])
La fila n posiciones antes de la actual (por defecto n = 1). Se usa para comparaciones del tipo "hoy frente a ayer".
NEXT(expr [, n])
La fila n posiciones después de la actual (por defecto n = 1). Look-ahead hacia adelante; poco común en la forma de ventana porque la ventana es monótona.
FIRST(expr [, n])
La fila n posiciones después de la primera fila del match actual (por defecto n = 0, la propia primera fila). "Comparar con la fila que inició este match".
LAST(expr [, n])
La fila n posiciones antes de la última fila coincidente (por defecto n = 0). Dentro de DEFINE la última fila coincidente es la fila actual, por lo que LAST(price) lee la fila actual.

Las cuatro primitivas se componen: PREV y NEXT pueden envolver una llamada a FIRST o LAST, dando lugar a cuatro formas compuestas cuya semántica es "ir a una fila relativa al match y luego dar un paso de distancia fija respecto a ella". Esto es lo que permite a una expresión DEFINE leer, por ejemplo, la fila inmediatamente anterior al inicio del match.

PREV(FIRST(expr [, n]) [, m])
Retrocede m filas desde la fila que lee FIRST(expr, n) (por defecto n = 0, m = 1). "¿Cuál era el valor justo antes de que comenzara este match?"
NEXT(FIRST(expr [, n]) [, m])
Avanza m filas desde la fila que lee FIRST(expr, n). Llega más adentro del match sin depender de la fila actual.
PREV(LAST(expr [, n]) [, m])
Retrocede m filas desde la fila que lee LAST(expr, n). "Comparar con una fila poco antes de la última fila coincidente".
NEXT(LAST(expr [, n]) [, m])
Avanza m filas desde la fila que lee LAST(expr, n).

Conviene señalar dos puntos prácticos. Primero, la navegación se puede componer: PREV(FIRST(price)) lee la fila inmediatamente anterior al inicio del match, y el parche lo soporta. Segundo, la navegación tiene consecuencias para las optimizaciones del executor. PREV y NEXT simples son relativas a la fila actual y son siempre seguras; FIRST y las variantes de LAST con desplazamiento, solas o dentro de un PREV/NEXT compuesto, son relativas a los límites del match, lo cual interactúa con la absorción de contextos: el planner deshabilita entonces la absorción para todo el patrón. El mecanismo tras esa interacción es el tema de §2.6.

2.3 Ejemplo resuelto 1 — movimiento del NFA

Objetivo de este ejemploMostrar la evolución, fila a fila, del estado del NFA en un patrón simple sin absorción. La traza sigue el contexto iniciado en la fila 0; los contextos iniciados en las filas 1–4 corren a su lado y SKIP PAST LAST ROW los descarta una vez registrado el match de este.
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)
);

El patrón se aplana a cuatro elementos:

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

Para la serie de precios 100, 110, 120, 115, 108, 130:

FilaPrecioVars verdaderasAcción
0100STARTNuevo contexto. START coincide y sale inmediatamente (max=1); el estado avanza a UP+.
1110START, UPUP coincide. Advance se bifurca: un estado se queda en bucle en UP, otro sale a DOWN+.
2120START, UPUP coincide en el estado en bucle y vuelve a bifurcar. El estado DOWN de la fila 1 muere (120 ≮ 110).
3115START, DOWNUP falla en el estado en bucle y muere. El estado DOWN de la fila 2 coincide. Advance se bifurca: bucle en DOWN y salida a #FIN — se registra un candidato a match sobre las filas 0–3.
4108START, DOWNDOWN coincide en el estado en bucle y se bifurca de nuevo; el nuevo candidato FIN sobre las filas 0–4 reemplaza al más corto.
5130START, UPEl estado DOWN en bucle falla (130 ≮ 108). Sin ningún estado vivo restante en este contexto, el candidato registrado (filas 0–4) se finaliza como el match. El siguiente intento comienza en la fila 5; START coincide, pero la partición termina antes de cualquier UP.

El punto clave: en la fila 3, la fila satisface tanto START (siempre verdadero) como DOWN, pero START solo importa a un contexto que comience en la fila 3; en este contexto el estado UP en bucle muere y solo avanza el estado que espera en DOWN+. La naturaleza multiestado de §2.1 se ve como un fan-out en cada coincidencia de UP (el estado podría quedarse en UP+ o avanzar hacia DOWN+). La preferencia codiciosa es "bucle de nuevo antes de salir", por lo que con suficientes datos las ramas en bucle extenderían más el match; aquí el DOWN en bucle muere en la fila 5 (130 ≮ 108), y el último candidato FIN (filas 0–4) — producido cuando DOWN salió en la fila 4, reemplazando al candidato de la fila 3 — se finaliza como el match.

El resultado de la consulta se sigue directamente de esta traza. Bajo la semántica de RPR, las funciones de ventana first_value(price) y last_value(price) solo se evalúan en la fila que inició el match — el resto de filas del match producen NULL para estas funciones, ya que su frame reducido está vacío. La salida para nuestros datos se parece, por tanto, a la tabla que el póster muestra en su panel superior derecho:

FilaPreciostart_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

La fila 0 es el inicio del match, por lo que su frame cubre las filas 0–4 y las funciones de ventana reportan el precio de apertura de la V ($100) y el precio de fondo ($108). Las filas 1–4 están dentro del match pero no son su inicio, por lo que reciben NULL. La fila 5 (precio $130) está fuera de todo match y, por tanto, también recibe NULL.

2.4 Ejemplo resuelto 2 — alternación y orden léxico

Objetivo de este ejemploMostrar cómo un único contexto lleva múltiples estados paralelos cuando una fila satisface más de una alternativa — y cómo el estándar resuelve los empates.

La forma (A | B) ofrece al motor una elección: en cualquier fila, las dos alternativas se prueban independientemente y cualquier número de ellas puede coincidir. Aquí es donde la naturaleza multiestado de §2.1 se hace visible dentro de un único contexto — no entre contextos (eso es absorción), sino a lo largo de ramas paralelas que el executor explora en orden del patrón, primero la rama anterior.

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

Imagine una fila donde el precio tanto ha subido como superado $100 — tanto UP como HIGH son verdaderos. Cada alternativa engendra su propio estado: uno recorriendo la rama UP, otro recorriendo la rama HIGH. Ambos avanzan después a DONE, donde se encuentran.

FilaVars verdaderasEstados vivos
RUP, HIGHEl Estado A (rama UP) y el Estado B (rama HIGH) avanzan ambos a DONE con los mismos conteos; B es un duplicado de A y se descarta
R+1DONEEl Estado A coincide con DONE y llega a #FIN

En términos del estándar, ambas ramas producen un match de la misma longitud sobre las mismas filas, dando dos caminos candidatos — uno etiquetado UP, DONE y otro etiquetado HIGH, DONE. El estándar resuelve esto por orden léxico: entre las alternativas escritas en (UP | HIGH), gana la escrita primero, sin importar la longitud del match. Como UP aparece antes que HIGH, el camino superviviente es UP, DONE. El executor lo impone en la fila R, no en FIN: añade primero el estado de la rama UP, de modo que nfa_append_state_unique() lo conserva y descarta el estado idéntico de la rama HIGH.

El orden léxico es lo que hace que CLASSIFIER() esté bien definido cuando finalmente se implemente — permite al runtime decir al usuario "esta fila coincidió como UP, no HIGH" incluso cuando ambos predicados eran verdaderos. El orden léxico es la regla primaria para la alternación: una rama léxicamente anterior gana sobre una posterior incluso si la posterior produciría un match más largo, y una rama léxicamente posterior (posiblemente más corta) aún puede ganar si todas las ramas anteriores mueren antes de llegar a FIN. La longitud codiciosa se decide dentro de un único cuantificador — dadas dos finalizaciones de la misma rama de alternación, el cuantificador codicioso prefiere más iteraciones.

2.5 Ejemplo resuelto 3 — absorción de contextos (mismo destino)

Objetivo de este ejemploMostrar por qué el trabajo total de estados O(n²) ingenuo se convierte en O(n) con absorción, con O(1) contextos vivos.

El patrón más simple que exhibe absorción es PATTERN (A+) con DEFINE A AS TRUE. Toda fila coincide con A, y el estándar exige que el motor considere cada fila como posible inicio de match. Ingenuamente, esto significa N contextos para una partición de N filas. Tomemos una partición de cinco filas (con cualquier dato — el predicado es constantemente verdadero):

FilaContextos ingenuosCon absorción
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 absorbido
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]

Los contextos vivos bajan de O(n) a O(1), por lo que el total sobre la partición baja de O(n²) a O(n). La regla de absorción que justifica el descarte es directa cuando el cuantificador es ilimitado:

Regla de absorción. Dos contextos cuyo estado vivo está en el mismo elemento del patrón, donde el contexto más antiguo tiene un conteo ≥ al del más nuevo, tienen futuros idénticos bajo un cuantificador ilimitado. El contexto más nuevo puede descartarse; cualquier match que acabe encontrando, el más antiguo encontrará uno más largo o igual.

El panel inferior izquierdo del póster ("① Context Absorption") es exactamente esta regla visualizada sobre cinco filas.

Un punto sutil pero importante se esconde en la regla: el descarte es seguro porque el predicado A AS TRUE evalúa al mismo valor en cada fila, sin importar qué contexto pregunte. Lo mismo sucede con cualquier predicado que referencie solo la fila actual o un desplazamiento fijo desde ella — incluido PREV. El siguiente ejemplo cambia a una semana concreta de precios, usando un predicado basado en PREV, y §2.6 reutilizará exactamente esa semana para hacer obvia la simetría entre absorción segura e insegura:

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

Tomemos la semana bursátil $100, $108, $112, $116, $110 de lunes a viernes — cuatro subidas seguidas de una caída repentina. Supongamos que C1 arranca el martes (el primer día donde RISE coincide: $108 > $100), y que el executor también rastrea especulativamente C2 arrancando el miércoles. La condición RISE de cada fila compara el precio de la fila con su predecesor inmediato — un hecho a nivel de partición, no a nivel de contexto — por lo que los dos contextos se ven obligados a computar el mismo booleano en cada fila que comparten:

DíaPrecioC1 — inicio mar
price > PREV(price)
C2 — inicio mié
price > PREV(price)
Lun$100——
Mar$108$108 > $100 ✓ (recién iniciado)—
Mié$112$112 > $108 ✓$112 > $108 ✓ (recién iniciado)
Jue$116$116 > $112 ✓$116 > $112 ✓
Vie$110$110 > $116 ✗ — finaliza$110 > $116 ✗ — finaliza
Mismo destino En cada fila que C1 y C2 comparten, evalúan expresiones idénticas y producen resultados idénticos — y el viernes mueren con la misma comparación. Cualquiera que sea el futuro de C2, C1 también lo tiene. Absorber C2 en C1 no descarta nada.

La historia se rompe en el instante en que el predicado empieza a depender de los propios límites de cada contexto — y de eso trata §2.6.

2.6 Ejemplo resuelto 4 — cuando la absorción deja de ser segura

Objetivo de este ejemploMostrar qué cambia cuando DEFINE referencia FIRST — la regla de absorción deja de cumplirse y el planner deshabilita la absorción para el patrón.

Supongamos que un analista desea encontrar días bursátiles consecutivos donde una acción se mantuvo dentro de los diez dólares respecto al día en que comenzó la racha — una especie de ventana de consolidación. El patrón y el DEFINE tienen este aspecto:

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

La condición ahora compara el precio de la fila actual con el precio al inicio de la racha actual. Dos rachas que arrancaron en días distintos tienen valores distintos de FIRST(price), por lo que dos estados en el mismo elemento del patrón y con el mismo conteo dejan de ser intercambiables: sus futuros dependen del límite que la absorción estaba a punto de descartar.

Tomemos la misma semana bursátil que en §2.5 — $100, $108, $112, $116, $110 de lunes a viernes. El runtime mantiene de nuevo dos rachas candidatas vivas a la vez: C1 arrancó el lunes, C2 arrancó el martes (toda fila es un posible inicio de racha bajo STABLE+).

DíaPrecioC1 — inicio lun
FIRST = $100
price < $100 + 10
C2 — inicio mar
FIRST = $108
price < $108 + 10
Lun$100$100 < $110 ✓—
Mar$108$108 < $110 ✓$108 < $118 ✓ (recién iniciado)
Mié$112$112 < $110 ✗ — finaliza Lun–Mar$112 < $118 ✓
Jue$116—$116 < $118 ✓
Vie$110—$110 < $118 ✓ (sigue activo)
Destinos distintos C1 muere el miércoles con una racha de dos días (Lun–Mar); C2, por sí solo, seguiría funcionando hasta el viernes. Los mismos precios, la misma forma de pregunta — pero techos distintos derivados de sus propios inicios de match. El mismo día, los dos contextos llegaron a conclusiones opuestas.

Bajo absorción, C2 se habría fusionado en C1 el martes — el contexto fusionado conserva solo el techo de C1 ($110), por lo que la vista distinta de C2 (techo $118, una racha de cuatro días hasta el viernes) no queda cubierta por el futuro de C1. En esta semana concreta la salida no llega a cambiar: C1 registra Lun–Mar, C2 comenzó dentro de ese match y SKIP PAST LAST ROW lo descarta, y el siguiente intento comienza el miércoles con su propio techo ($122) y coincide en Mié–Vie. En general, sin embargo, el resultado DEFINE de un contexto anterior ya no subsume el de uno posterior, por lo que la comparación de conteos en la que se apoya la absorción no es válida. Siempre que un predicado DEFINE tenga dependencia del inicio de match, el planner deshabilita por tanto la absorción de forma preventiva.

(Cuando el match del contexto principal sí tiene éxito, los contextos que arrancaron dentro de su tramo aceptado — bajo el modo por defecto AFTER MATCH SKIP PAST LAST ROW — se descartan sin más; se mantienen vivos únicamente para que el runtime tenga a dónde recurrir si el match principal falla.)

La tabla siguiente amplía el panel inferior derecho del póster ("② Navigation") con las formas compuestas y resume qué formas de navegación crean dependencia del inicio de match:

NavegaciónDep. inicio match¿Absorbible?
PREV, NEXTningunasí
LAST (sin desplazamiento)ningunasí
LAST con desplazamientoverificación de límiteno
FIRST (cualquiera)directano
Compuesta (FIRST interno)directano
Compuesta (LAST interno, sin desplazamiento)ningunasí
Compuesta (LAST interno con desplazamiento)verificación de límiteno

Los dos ejemplos de §2.5 y §2.6 se reducen a una única regla. Mismo destino es lo que hace segura la absorción: si todos los contextos en el mismo elemento del patrón van a calcular la misma respuesta para cada predicado futuro, solo hace falta conservar el más antiguo. Destinos distintos hacen insegura la absorción: en cuanto los predicados se ramifican según estado privado de cada contexto — que es exactamente lo que hacen FIRST y LAST con desplazamiento — cada contexto vivo representa un futuro que ningún otro contexto tiene garantizado cubrir, por lo que ya no puede demostrarse que descartar uno sea seguro.

El planner detecta esta distinción en tiempo de compilación y activa o desactiva la absorción para todo el patrón; cuando está desactivada, el runtime paga el coste multicontexto. El benchmark del panel ③ del póster no usa FIRST, por lo que la absorción permanece activa, y por eso PostgreSQL se mantiene lineal tanto en los casos de éxito como de fallo.

Los números del benchmark del póster son el mismo algoritmo desplegándose a escala. En el patrón de éxito (A+ B+ C+ D), tanto PostgreSQL como Trino escalan aproximadamente O(n) una vez confirmado un match, y PostgreSQL aventaja en aproximadamente entre 16× y 33× (las cifras de Trino ya excluyen el arranque de la JVM).

En el patrón de fallo (A+ B+ C+ E), Trino, que parece carecer de absorción, persigue cada inicio potencial de match y degrada incluso más rápido que O(n²) (unas 56× el tiempo para 5× las filas); con 100.000 filas tarda más de cinco horas, mientras que PostgreSQL aún termina en 92 ms, una aceleración de unas 217.000×.

Esa diferencia no es mero pulido de ingeniería — es precisamente la distinción mismo destino / destino distinto de §2.5 y §2.6, aplicada a cada fila de cada inicio potencial de match en la partición.

2.7 Ejemplo resuelto 5 — cuando SKIP deshabilita la absorción

Objetivo de este ejemploMostrar una segunda forma en que la absorción puede fallar: no porque el predicado se divida, sino porque la semántica de salida exige reportar cada match por separado.

El ejemplo previo rompía la absorción desde el lado de los datos: FIRST en DEFINE hacía que cada contexto evaluara los predicados de forma distinta. La absorción también puede romperse desde el lado de la salida, y la cláusula AFTER MATCH SKIP es la que lo controla.

Considere el patrón PATTERN (A+) con DEFINE A AS TRUE sobre cinco filas que todas coinciden con A. Con el modo por defecto AFTER MATCH SKIP PAST LAST ROW, el motor encuentra el match más largo que comienza en la fila más temprana y luego salta más allá; cualquier contexto que comenzara dentro de ese match se descarta implícitamente como redundante — exactamente la situación que la absorción está diseñada para manejar. La salida es un único match, filas 0–4, y el runtime necesita un único contexto vivo.

Cambie el modo de salto a AFTER MATCH SKIP TO NEXT ROW y el contrato cambia:

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

Ahora toda posición potencial de inicio debe reportarse por separado, incluso cuando los matches se solapan. Para las mismas cinco filas, el runtime debe emitir cinco matches: filas 0–4, 1–4, 2–4, 3–4 y 4–4. Ninguno de ellos puede ser reemplazado por "uno más largo que comienza antes", porque el estándar dice que el usuario los quiere todos.

FilaSKIP PAST LAST ROWSKIP TO NEXT ROW
0el match empieza; filas 0–4 serán el único matchel match empieza en la fila 0
1(dentro del match 0)el match empieza en la fila 1 — debe mantenerse vivo
2(dentro del match 0)el match empieza en la fila 2 — debe mantenerse vivo
3(dentro del match 0)el match empieza en la fila 3 — debe mantenerse vivo
4el match 0 se finaliza (filas 0–4)se finalizan cinco matches: 0–4, 1–4, 2–4, 3–4, 4–4
Salida distinta, destinos distintos Bajo AFTER MATCH SKIP TO NEXT ROW, todo contexto de inicio tardío es su propia fila de salida. Dos contextos en el mismo elemento del patrón ya no son redundantes — ambos son salidas requeridas, y descartar uno omitiría silenciosamente un match que el usuario pidió.

Note que el predicado no ha cambiado. A AS TRUE evalúa igual en cada fila sin importar qué contexto pregunte, por lo que la condición de mismo destino de §2.5 se sigue cumpliendo. Lo que cambia es el requisito de salida: incluso contextos con futuros idénticos deben coexistir porque corresponden a filas distintas del resultado. El planner deshabilita por tanto la absorción de contextos siempre que AFTER MATCH SKIP TO NEXT ROW esté en vigor, sin importar la cláusula DEFINE.

Poner §2.6 y §2.7 una al lado de la otra muestra las dos maneras en que la semántica de una consulta excluye la absorción:

Lado de los datos · §2.6
El predicado evalúa de forma distinta por contexto.
Activado por FIRST o LAST con desplazamiento en DEFINE.
Lado de la salida · §2.7
La salida requiere cada inicio de match como una fila separada.
Activado por AFTER MATCH SKIP TO NEXT ROW.

Cualquiera de las dos condiciones basta para deshabilitar la absorción para todo el patrón, y también un frame que no termina en UNBOUNDED FOLLOWING. Cuando ninguna está en vigor — el modo por defecto AFTER MATCH SKIP PAST LAST ROW, un fin de frame ilimitado y condiciones DEFINE que solo usan PREV, NEXT o LAST sin desplazamiento — la absorción está habilitada, pero solo para los estados de la región absorbible del patrón: una variable inicial codiciosa ilimitada como A+ o A*, un grupo de longitud fija con un cuantificador codicioso ilimitado como (A B)+, un grupo codicioso cuyo cuerpo comienza con uno de estos como (A+ B)+ o (A+ B){2}, o ramas de alternación construidas a partir de ellos; un grupo reluctante descalifica todo su subárbol. Donde eso se cumple, como para A+ en §2.5, el runtime colapsa a un único contexto y se mantiene lineal; START UP+ DOWN+ de §2.3 no obtiene ninguna región absorbible.

§3. Diseño — del parser al executor

Row Pattern Recognition se implementa como tres etapas que se traspasan el trabajo mediante formas intermedias bien definidas. El parser convierte el texto SQL en un árbol de patrones y una lista de predicados DEFINE; el planner compila el árbol en un array plano de elementos de patrón y decide cuáles de ellos pueden participar en la absorción de contextos; el executor ejecuta el array contra la partición fila por fila en un bucle de tres fases. Cada etapa tiene su propia forma de datos, y la mayor parte del ingenio del diseño está en las fronteras: un NFA plano que cabe en caché, un modelo de navegación que reutiliza un único slot de tupla en lugar de materializar uno por referencia, y una regla de absorción que convierte el trabajo O(n²) en O(n).

SQL text
  │
  │  parser stage
  ▼    validate frame
       build pattern tree
       type-check DEFINE

pattern tree + DEFINE list
  │
  │  planner stage
  ▼    optimize the tree
       compile to flat NFA array
       decide absorbability

flat NFA + absorption flags
  │
  │  executor stage
  ▼    per-row engine:
       Match → Absorb → Advance

match result:
  start row, length, success/fail

Las secciones siguientes recorren esta pipeline. §3.1 cubre el parser y la forma del árbol de patrones; §3.2 cubre la compilación que convierte el árbol en el NFA plano; §3.3 cubre el modelo de navegación que los predicados DEFINE usan para mirar filas vecinas; §3.4 cubre la gestión de los límites del match — las reglas SKIP, INITIAL y de frame acotado que fijan dónde empieza y termina un match; §3.5 es el motor por fila de tres fases; §3.6 reúne todos los mecanismos de poda que mantienen acotado el espacio de estados; y §3.7 reseña lo que la implementación expone en la salida de EXPLAIN.

3.1 Parser — construcción del árbol de patrones

El parser reconoce el pattern recognition por la presencia de una cláusula PATTERN dentro de una especificación de ventana. Su primer trabajo es la validación del frame, ya que RPR impone restricciones que las consultas de ventana ordinarias no tienen: el modo de frame debe ser ROWS (no RANGE ni GROUPS), el límite inicial debe ser CURRENT ROW, el límite final debe ser UNBOUNDED FOLLOWING o un desplazamiento positivo FOLLOWING (por lo que también se rechaza un frame por defecto), y las opciones EXCLUDE distintas de EXCLUDE NO OTHERS están prohibidas. Son comprobaciones de conformidad, no optimizaciones — la noción de frame en RPR es el tramo del match, y el estándar no contempla rellenarlo con nada que no sean las filas coincidentes.

Una vez que el frame pasa la validación, el parser convierte la cláusula PATTERN en un árbol construido a partir de cuatro tipos de nodo — una referencia a variable, una secuencia (concatenación), una alternación y un grupo (subpatrón entre paréntesis). Cada nodo lleva el cuantificador como tres números — un límite inferior, un límite superior (posiblemente infinito) y una bandera para coincidencia reluctante:

FuenteCodificación en árbol
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)

A continuación, cada predicado DEFINE se verifica de tipo contra las columnas de la partición y se coacciona a una expresión booleana. De ello se siguen dos cosas prácticas. Primera, el análisis sintáctico no añade nada a la lista de destino de la consulta para DEFINE; en su lugar, el planner marca como necesaria cada columna que referencia un predicado DEFINE, como hace con HAVING, y propaga esas columnas hasta la etapa del executor incluso si la consulta circundante no las selecciona — sin esto, el runtime no tendría nada contra lo que evaluar. Segunda, las variables que aparecen en el PATTERN pero nunca en el DEFINE son implícitamente verdaderas: coinciden con cualquier fila.

3.2 Compilación — del AST a un NFA plano

El planner convierte el árbol del parser en la estructura de datos que el executor ejecutará: un array plano de elementos de patrón direccionado por índice. La compilación procede como una pipeline de seis pasos:

compile(astTree):
  1. optimizar el AST
  2. medir tamaño y profundidad
  3. reservar el array de elementos
  4. rellenar desde el AST
       (asignar punteros next/jump)
  5. finalizar — instalar centinela FIN
  6. marcar elementos elegibles para absorción

La forma plana se elige por una razón sencilla: el executor necesita recorrer el patrón muchas veces por partición, y un array contiguo direccionado por índice es la estructura de datos más barata de recorrer. Los pasos 1 y 6 son los interesantes — el paso 1 porque determina el tamaño del array, y el paso 6 porque decide si la optimización por absorción de §2.5 llegará siquiera a activarse.

Optimización del AST

La optimización rinde dos veces: una en el conteo estático de elementos del array plano, y otra en cada fila procesada en tiempo de ejecución. Cada transformación reduce el espacio de estados que el runtime debe enumerar. El optimizador aplica nueve reglas de reescritura en una única pasada ascendente (dentro de una secuencia, la fusión de grupos se ejecuta una vez más, ya que fusiones anteriores pueden juntar dos grupos idénticos):

Aplanado de SEQ
SEQ(A, SEQ(B, C)) → SEQ(A, B, C)
Fusión de variables consecutivas
A A → A{2}
A{2,3} A{1,2} → A{3,5}
Fusión de grupos consecutivos
(A B)+ (A B)+ → (A B){2,∞}
Fusión de ALT consecutivas
(A | B) (A | B) (A | B) → (A | B){3}
Fusión de prefijo/sufijo
A B (A B)+ → (A B){2,∞}
Aplanado y deduplicación de ALT
(A | (B | C)) → (A | B | C)
(A | B | A) → (A | B)
Multiplicación de cuantificadores
(A+)+ → A+
(A{2,3}){5} → A{10,15}
Desenvoltura de hijo único
SEQ(A) → A
(A){1,1} → A
Normalización de reluctancia
A{2}? → A{2} (la reluctancia se elimina siempre que min = max)

La multiplicación de cuantificadores colapsa solo cuando los conteos alcanzables forman un único intervalo contiguo y el match preferido no se desplaza: un externo exacto ((A{2,3}){5} → A{10,15}), un hijo con min 0, o intervalos del hijo que se tocan con un min del hijo de como mucho 1 o un max del hijo ilimitado ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), donde un externo con min 0 también necesita un min del hijo de como mucho 1 ((A{2,})* se mantiene, ya que A* aceptaría una fila). Un hijo de grupo cuyo propio cuantificador no es exacto debe tener antes un cuerpo de longitud fija, por lo que ((A | B B){1,2}){2} se mantiene intacto incluso bajo un externo exacto. Otras combinaciones pueden introducir huecos que la forma plana pasaría por alto — p. ej., (A{2}){2,3} acepta solo {4, 6}, pero un A{4,6} ingenuo también aceptaría 5 — o desplazar el match preferido ((A{2,3}){1,2} prefiere tres filas donde A{2,6} toma cuatro), por lo que el optimizador las deja intactas. No es la única reescritura condicionada: la fusión de grupos y la fusión de sufijo requieren un cuerpo que consuma un número fijo de filas, la fusión de prefijo rechaza un grupo con min 0, un max finito y contenido nullable, los nodos reluctantes no se fusionan ni se multiplican ((A+?)+ se mantiene), y se rechaza una reescritura cuyo nuevo límite desbordaría.

Forma del elemento

Cada elemento del array plano representa una única posición en el patrón. Hay seis tipos lógicos: una referencia a variable (el único tipo que consume una fila); marcadores de inicio de grupo y fin de grupo, que abren y cierran un subpatrón entre paréntesis; un marcador de alternación, que encabeza una lista de ramas; un separador de rama que termina cada rama; y un marcador de fin al final del patrón.

Cada elemento lleva además una profundidad (su nivel de anidamiento de grupo), el cuantificador (un conteo mínimo y máximo de repetición, posiblemente infinito) y dos punteros de transición — next, "a dónde ir tras consumir este elemento", y jump, "a dónde saltar" (usado por el marcador de alternación y los separadores de rama para encadenar ramas, por el inicio de grupo para nombrar su propio fin de grupo — un grupo cuyo cuantificador permite cero se salta a través del next de ese fin — y por el fin de grupo para volver al cuerpo).

Para PATTERN ((A B)+) el array compilado tiene este aspecto:

PATTERN ((A B)+) compiles to:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 3
    (abre el grupo; jump nombra
     su propio 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
    (cierra el grupo; jump vuelve atrás)

[4] FIN    patrón completo

El patrón se lee de izquierda a derecha mediante next, con jump manejando las aristas no lineales. En el idx 3, el jump del END apunta de vuelta al idx 1, y así itera el cuantificador externo ilimitado; en el idx 0, el jump del BEGIN nombra su END en el idx 3, y si el grupo fuera opcional el salto saldría por el next de ese END hasta el idx 4 sin llegar al END. El runtime nunca tiene que construir un grafo en tiempo de ejecución — simplemente sigue estos dos punteros mientras recorre el array.

Atributos por elemento

Más allá de la forma, cada elemento lleva cinco atributos lógicos que dirigen el comportamiento del runtime en esa posición:

Reluctante
Invierte el orden de expansión del cuantificador. Los cuantificadores codiciosos prueban "iterar de nuevo" antes que "salir"; los reluctantes prueban "salir" primero. Lo lleva la variable para A+?; lo llevan el BEGIN y el END del grupo para ((…)+?).
Empty-loopable
Activado en los fines de grupo cuyo cuerpo es nullable ((A? B?)+, (A | B*)+; (A?)* se multiplica primero a A* y no deja fin de grupo). Indica al runtime que añada una salida fast-forward junto al loop-back normal por debajo de min, de modo que la guarda de ciclos no mate matches legítimos en grupos que pueden producir iteraciones vacías.
Empty-preferred
Activado en los fines de grupo cuyo cuerpo prefiere el match vacío, como en (A?? B??){2}. Ordena la salida fast-forward por delante del loop-back por debajo de min, donde la codicia del propio grupo no dice nada.
En región absorbible
Marca todo elemento que esté dentro de una región elegible para absorción — usado por el runtime para rastrear si el estado actual sigue en territorio seguro.
Punto de comparación de absorción
Marca el elemento concreto donde deben ejecutarse las comparaciones de absorción. Para un A+ simple cae sobre la variable; para un grupo ilimitado como (A B)+ cae únicamente sobre el fin de grupo.

La separación entre "en región" y "punto de comparación" importa porque la absorción solo tiene sentido en los puntos donde se cierran iteraciones. Dentro del cuerpo de (A B)+, el runtime está a mitad de iteración y el conteo aún no ha alcanzado su valor final para esa ronda; comparar aquí significaría comparar valores incomparables. El estado debe llegar al fin de grupo antes de que el runtime pueda decidir. El primer atributo dice por tanto "todavía estás en territorio absorbible"; el segundo dice "has llegado al punto de comparación — verifica ahora".

Análisis de absorbibilidad

El paso 6 de la compilación es lo que da a la regla de "mismo destino" de §2.5 su testigo en tiempo de compilación. La decisión es por capas:

isAbsorbable(query):
  si modo SKIP != SKIP PAST LAST ROW
      → return false
  si fin de frame != UNBOUNDED FOLLOWING
      → return false
  si algún DEFINE depende de match_start
      → return false
  recorrer el array plano desde
  el elemento 0 y marcar elementos
  que satisfacen un caso estructural

Las tres primeras comprobaciones son a nivel de consulta: corresponden exactamente a las condiciones de §2.7 (lado de la salida: modo SKIP), frame acotado (el límite rompe la monotonicidad) y §2.6 (lado de los datos: FIRST o LAST con desplazamiento en DEFINE). Cuando cualquiera de ellas falla, el análisis no marca banderas y la absorción se deshabilita para toda la consulta. Cuando todas pasan, el recorrido admite cuatro formas estructurales:

Caso 1 — Variable ilimitada simple
A+, A*, A{2,∞}
Cada iteración es exactamente una fila. El conteo de un contexto anterior es siempre ≥ al de uno posterior en cada posición compartida.
Caso 2 — Grupo de longitud fija, externo ilimitado
(A B)+, (A B{2})+, ((A (B C){2}){2})+
Cada hijo tiene min == max, por lo que el cuerpo es semánticamente equivalente a su forma desplegada {1,1} — (A B{2})+ se comporta como (A B B)+. Cada iteración consume un número fijo de filas; la dominancia de conteo se sigue cumpliendo.
Caso 3 — Grupo cuyo cuerpo comienza con una variable ilimitada
(A+ B)+, (A+ B){2}
La variable ilimitada inicial es absorbible por sí misma (Caso 1) y protege a los contextos anteriores. La absorción se detiene en cuanto el estado pasa de A — el resto del cuerpo no tiene garantía de monotonicidad, por lo que A recibe ambas banderas, el BEGIN que lo encierra recibe la bandera de región, y B y END no reciben ninguna.
Caso 4 — Alternación
A+ | B+, A+ | C D
Cada rama, alcanzada a través de la cadena de separadores, se juzga por sí misma según los casos anteriores; el marcador de alternación recibe la bandera de región cuando alguna rama cumple los requisitos.

Los casos estructurales no cubiertos por estas cuatro formas son igual de instructivos. A B+ no puede absorberse con la regla actual porque la A inicial consume una fila antes de que comience la parte ilimitada, por lo que contextos separados por una fila están en posiciones distintas dentro del cuerpo ilimitado. Los cuantificadores reluctantes como A+? quedan excluidos por construcción: la regla de absorción asume semántica codiciosa, donde matches más largos subsumen a los más cortos, y la coincidencia reluctante invierte esa dirección.

El resultado es una decisión por elemento, no por patrón. Un único plan de consulta puede tener la absorción habilitada para el A+ inicial de patrones como (A+ B+ C) o (A+ B+)+ — este último es simplemente el Caso 3 aplicado a su elemento inicial — y deshabilitada para todo lo que viene después; el runtime simplemente consulta el atributo de punto de comparación del elemento del estado actual cada vez que considera una pasada de absorción. Una vez que un estado se mueve a una región no absorbible, la absorción queda permanentemente apagada para ese estado — exactamente lo que §2.5 y §2.6 necesitan que sea cierto a nivel algorítmico.

3.3 Navegación — el intercambio de tupla de 1 slot

Las expresiones DEFINE son expresiones SQL ordinarias evaluadas contra una fila, pero pueden incluir PREV, NEXT, FIRST o LAST — referencias que apuntan a filas distintas. Las filas en sí ya están almacenadas en el tuplestore de la ventana; lo que el executor aún tiene que gestionar es el slot de tupla del que lee la maquinaria de expresiones SQL, ya que las referencias a columnas dentro de la expresión están enlazadas a un slot en tiempo de planificación. La implementación reutiliza un único slot de navegación para cada llamada de navegación: el slot se intercambia antes de evaluar la expresión interna y se restaura después, de modo que el resto de la maquinaria de expresiones SQL nunca nota la diferencia.

El modelo que ve el executor es pequeño: hay un slot de la fila actual que contiene la fila contra la que se evalúa la expresión DEFINE, y un slot de navegación que el runtime puede redirigir temporalmente a una fila distinta. Alrededor de cualquier llamada de navegación, el runtime prepara el slot de navegación, evalúa la expresión interna como si estuviera leyendo la fila actual y luego restaura la fila original. Pseudocódigo:

eval_navigation(call):
  targetPos = compute_target_position(call)
  si targetPos está fuera de su rango válido:
      return NULL

  guardar current_row_slot
  si targetPos != currentPos:
      obtener fila en targetPos
        en nav_slot
      apuntar el slot externo a nav_slot
  result = eval_inner_expression()
  restaurar current_row_slot
  copiar el resultado by-ref fuera de nav_slot
  return result

El truco está en que hay exactamente un slot que guardar y restaurar. La expresión interna — sea cual sea, incluida aritmética, llamadas a función u otras referencias a columnas — se ejecuta contra el slot intercambiado usando la misma ruta de evaluación que usaría para la fila actual. Sin evaluador alternativo y sin un slot por referencia; cuando el destino es la fila actual, la obtención y el intercambio se omiten por completo. La obtención copia la fila destino en el slot de navegación (salvo que el slot ya la contenga), y el paso de restauración copia un resultado pasado por referencia a la memoria por tupla para que la siguiente obtención no pueda liberarlo.

La navegación compuesta se aplana en tiempo de parseo para que el intercambio siga ocurriendo una sola vez. PREV(FIRST(price)) se reconoce como una navegación de dos pasos — "ir a la primera fila coincidente, luego retroceder una fila" — y se almacena como una única llamada de navegación con un tipo compuesto. El runtime computa la posición objetivo en dos etapas pero realiza un único intercambio de slot para recuperar la fila final:

compute_target_position(call):

  # relativo a fila actual
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # relativo al match
  FIRST(n):
      return matchStart + n
  LAST(n):
      return currentPos − n

  # compuesto: match-rel, luego paso
  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

  validar contra el rango apropiado
  (rango del match para FIRST/LAST interno,
   rango de partición para paso exterior)

Una caché de posiciones cortocircuita la lectura del tuplestore cuando varias llamadas de navegación en el mismo DEFINE apuntan a la misma fila — habitual en expresiones como price > PREV(price) AND volume > PREV(volume) donde ambas llamadas resuelven a la fila previa. La caché solo almacena "última posición consultada", y el intercambio en sí sigue siendo una única operación.

La clasificación de las llamadas de navegación es la contribución del planner a la decisión de absorción. El planner recorre cada expresión DEFINE y clasifica cada variable en uno de dos cubos, según si todos los contextos calcularán el mismo booleano en la misma fila, o cada contexto calculará el suyo propio. El cubo determina dos cosas en tiempo de ejecución: cuántas veces se evalúa la variable (una compartida, o una por cada contexto afectado — §3.5 Fase 1), y si la absorción de contextos es posible en absoluto (§2.5 vs §2.6): una sola variable dependiente del inicio de match la deshabilita para todo el patrón.

Evaluación compartida · absorción segura Todo contexto ve el mismo booleano en cada fila — mismo destino (§2.5).
  • Sin navegación
  • Solo PREV / NEXT
  • LAST sin desplazamiento
  • Compuesta con LAST interno (sin desplazamiento)
Evaluación por contexto · absorción insegura Los contextos con inicios de match distintos calculan respuestas distintas — destinos distintos (§2.6).
  • LAST con desplazamiento
  • FIRST (cualquier forma)
  • Compuesta con FIRST interno
  • Compuesta con LAST interno (con desplazamiento)

La clasificación se realiza en tiempo de planificación y se almacena junto a cada variable DEFINE, de modo que el runtime no gasta tiempo decidiendo — simplemente lee el cubo de cada variable a medida que procesa una fila.

Presupuesto de retención

La navegación accede a filas que la maquinaria de funciones de ventana ya habría dejado pasar. Para mantener esas filas disponibles, el executor se construye sobre un tuplestore que retiene una ventana deslizante de filas recientes; la pregunta es cuán amplia debe ser esa ventana. El executor lo calcula a partir de dos desplazamientos complementarios, resolviendo cada desplazamiento una vez por scan (los constantes también en la inicialización del executor, para que el EXPLAIN simple pueda mostrarlos):

Presupuesto de lookback
Cuánto hacia atrás desde la fila actual podría llegar cualquier llamada DEFINE.
Contribuyentes: PREV, LAST (cualquier desplazamiento, incluido el 0 por defecto), PREV(LAST(...)), NEXT(LAST(...))
Presupuesto de lookahead-desde-inicio
El alcance mínimo hacia adelante (hacia atrás, cuando es negativo) desde el inicio del match del contexto vivo más antiguo — la fila más temprana que cualquier llamada DEFINE podría necesitar.
Contribuyentes: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

En tiempo de ejecución, la marca de recorte del tuplestore se fija en la más temprana de dos posiciones — la fila actual menos el presupuesto de lookback, y el inicio del match del contexto vivo más antiguo más el presupuesto de lookahead. Nada anterior a esa marca puede ser alcanzado por ninguna llamada de navegación en ningún contexto vivo, y el tuplestore es libre de descartarlo. Las líneas Nav Mark que reporta EXPLAIN (§3.7) — Lookback y Lookahead — son estos dos presupuestos, no picos medidos. Cada una se imprime solo cuando alguna navegación la alimenta y se muestra incluso sin ANALYZE; un desplazamiento cuyo valor solo se conoce en tiempo de ejecución (un parámetro de un plan genérico, por ejemplo) imprime runtime bajo el EXPLAIN simple y su valor resuelto bajo EXPLAIN ANALYZE, y retain all (Lookback) o infinite (Lookahead) señala un desplazamiento que desborda.

3.4 Límites del match — SKIP, INITIAL y frame acotado

El resultado de un match se registra como dos valores: la fila en la que comienza el match y su longitud. Un inicio negativo significa que la posición aún no se ha evaluado; una vez fijado el inicio, las consultas posteriores al executor — "¿está esta fila dentro de un match?" — pueden responderse en O(1) inspeccionando el par. La longitud codifica el resultado: -1 para una fila sin match, 0 para un match vacío y el número de filas para un match real. Una longitud cero es un resultado real, no un error: representa un patrón que coincidió sin consumir ninguna fila, lo que el executor debe distinguir tanto de una fila sin match como de "no se ha intentado ningún match en esta posición todavía".

La cláusula AFTER MATCH SKIP decide dónde comienza el siguiente intento de match. AFTER MATCH SKIP PAST LAST ROW se mueve a la fila siguiente al fin del match, produciendo la salida no solapada que la mayoría de consultas desean y habilitando la optimización por absorción.

AFTER MATCH SKIP TO NEXT ROW se mueve solo a la fila siguiente al inicio del match, permitiendo matches solapados; el planner deshabilita por tanto la absorción para el patrón de esa ventana cuando este modo está en vigor.

Los otros dos destinos de skip que el estándar también define — AFTER MATCH SKIP TO FIRST var y AFTER MATCH SKIP TO LAST var — dependen del historial por match que este parche no retiene. No están presentes en absoluto en la gramática, por lo que el parser lanza un error de sintaxis genérico si se proporciona alguno.

Lo mismo sucede con SEEK, la alternativa del estándar a INITIAL. Bajo SEEK, un intento de match que comienza en la fila R puede tener éxito en cualquier fila desde R hasta el fin del frame, no solo en R. El parche implementa únicamente INITIAL: cada match potencial se ancla en una fila específica. El parser lanza un error si se solicita SEEK. Los frames acotados reciben su propio tratamiento — cuando el usuario escribe ROWS BETWEEN CURRENT ROW AND N FOLLOWING en lugar de UNBOUNDED FOLLOWING, el executor cortocircuita cualquier contexto cuyo match haya alcanzado el límite forzando un mismatch, y la absorción se deshabilita porque el límite rompe la suposición de monotonicidad sobre la que descansa la absorción.

3.5 El motor por fila de tres fases

El driver por fila del executor es invocado por la maquinaria circundante de funciones de ventana cada vez que necesita saber si una fila dada pertenece a un frame coincidente. El driver encuentra o crea el contexto para la posición de inicio actual y luego avanza el NFA fila a fila — reiniciando un array de coincidencias por variable a "no evaluado" en cada fila — hasta que ese contexto no tiene estados vivos o termina la partición. Los predicados DEFINE se evalúan de forma perezosa: una variable se evalúa la primera vez que algún estado la consume, por lo que una variable que ningún estado vivo prueba en esta fila nunca se evalúa. El paso hacia adelante en sí son tres fases en orden fijo — Match, Absorb, Advance — envueltas en el mismo bucle externo:

processRow(currentPos):

  # Fase 1 — MATCH (convergencia)
  para cada contexto:
      si contexto alcanzó el fin de su frame:
          forzar mismatch (finalizar pronto)
          continue
      si matchStartRow difiere de
         la posición de evaluación compartida:
          reiniciar a no evaluadas las variables
          DEFINE dependientes del match-start (§3.3)
      match(context, varMatched)

  # Fase 2 — ABSORB
  si patrón es absorbible:
      refrescar flags de cada contexto
      absorb_contexts()

  # Fase 3 — ADVANCE (divergencia)
  para cada contexto:
      advance(context, currentPos)
      si registró un match y
         SKIP PAST LAST ROW:
          podar contextos posteriores que
          comienzan dentro del match

El orden no es una elección estilística. Match debe ejecutarse primero porque la absorción compara conteos posteriores al match; ejecutar Absorb antes de Match compararía estados a punto de morir. Advance debe ejecutarse el último porque es la única fase que crea nuevos estados — expande cada estado superviviente mediante transiciones épsilon hasta que cada uno llega a una variable a la espera de la siguiente fila. Ejecutar Absorb después de Advance significaría comparar sucesores ya divergidos, perdiendo el punto en que los estados son comparables de forma más limpia.

Fase 1 — Match

Match es una fase de "convergencia": los estados o bien sobreviven con su conteo incrementado, o bien mueren. Un punto sutil es que, para variables que se encuentran en una región absorbible, Match también realiza una pequeña cantidad de avance hacia adelante, para que Absorb pueda comparar limpiamente. La condición de cobertura solo se dispara en el punto de comparación absorbible — el END del grupo ilimitado — por lo que los estados que acaban de coincidir con variables a mitad de iteración (como B dentro de (A B)+) necesitan avanzarse hasta ese punto de comparación durante el propio Match; de lo contrario, Absorb no encuentra nada elegible para comparar y la optimización nunca se activa.

match(context, varMatched):
  para cada estado en contexto:
      elem = pattern[state.elemIdx]
      assert elem es una variable
          # advance solo deja variables

      si varMatched[elem.varId] está
         sin evaluar:
          evaluar su DEFINE ahora
      si no varMatched[elem.varId]:
          descarta estado   # rama muerta
          continue

      state.counts[elem.depth] += 1

      # Avance hacia adelante en línea para
      # que la siguiente fase pueda comparar
      # en el elemento punto de comparación
      # en lugar de a mitad de iteración.
      si elem está in-region pero no
         es el punto de comparación,
         y alcanzó su conteo máximo,
         y elem.next es un group end:

          recorrer la cadena END:
            incrementar conteo del grupo exterior
            avanzar state.elemIdx hasta END
            continuar mientras siga in-region,
              must-exit, y next sea END
          (se detiene en el punto de comparación
           o en un elemento aún loopable)

El recorrido de la cadena de END es lo que hace absorbibles los grupos anidados de longitud fija. En ((A B){2})+, cuando B alcanza su máximo (B es {1,1}), el conteo del grupo interno debe incrementarse; si ese conteo también alcanza su máximo — cerrando el {2} interno — el conteo del grupo externo debe incrementarse igualmente, y así sucesivamente, hasta que el estado aterriza en el punto de absorción más externo — el END del grupo externo ilimitado (el +). Hacer este trabajo en Match permite a Absorb comparar contra contextos que ya han consolidado sus conteos post-iteración.

Fase 2 — Absorb

La pasada de absorb recorre los contextos desde el más nuevo (cola) al más antiguo (cabeza). Para cada contexto en progreso que es totalmente absorbible, escanea hacia atrás buscando un contexto en progreso más antiguo que lo cubra, y libera el más nuevo si lo encuentra. Como los contextos se mantienen en orden de creación y cada fila crea como mucho un contexto, "más nuevo" y "más antiguo" realmente significan "iniciado después" e "iniciado antes".

absorb_contexts():
  para ctx desde la cola hacia atrás:
      si ctx está finalizado
         o tiene algún estado no absorbible
         o tiene un match registrado:
          saltar
      para older desde ctx.prev hacia atrás:
          si older está finalizado
             o no tiene estado absorbible:
              saltar
          si covered(older, ctx):
              free(ctx)
              registrar longitud de absorción
              break

covered(older, newer):
  para cada estado en newer:
      elem = pattern[state.elemIdx]
      si elem no es el punto de comparación:
          return false
      si ningún estado en older con:
            mismo elemIdx
            y isAbsorbable
            y older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

De esto se derivan dos microdecisiones. La primera es que la comprobación de cobertura rechaza inmediatamente si algún estado en el contexto más nuevo se encuentra en algún sitio que no sea un punto de comparación — comparar en puntos no decisorios no sería una comparación con significado.

La segunda es el par asimétrico de banderas de cada contexto: has-absorbable-state responde a "¿podría este contexto absorber a uno más nuevo?" y es monótona (solo puede pasar de true a false a medida que mueren estados), mientras que all-states-absorbable responde a "¿podría ser absorbido este contexto?" y es dinámica (vuelve a true cuando se elimina un estado no absorbible) hasta que el contexto registra un match, lo que la fija en false — absorberlo liberaría un match que ningún contexto absorbente puede reproducir. Ambas banderas se comprueban en tiempo constante antes incluso de comenzar el escaneo de cobertura, por lo que la absorción solo paga su coste completo en contextos con una posibilidad real de ser absorbidos.

Fase 3 — Advance

Advance es la fase de "divergencia": cada estado superviviente se expande mediante transiciones épsilon hasta que cada rama llega o bien a una variable esperando la siguiente fila, o bien al sentinela FIN. La expansión es en profundidad, y el orden en que se recorren las ramas hermanas es lo que hace que la regla de preferencia del estándar tenga realmente efecto — la rama léxicamente primera siempre se añade primero, y el paso de deduplicación en la inserción de estados descarta silenciosamente las adiciones posteriores equivalentes.

advance(context, currentPos):
  saca todos los estados actuales;
  reconstruye ctx.states desde cero
  para cada estado en orden léxico:
      limpia el bitmap de elementos visitados
      limpia el bitmap de visitados

      # Preferencia: una vez que un DFS
      # alcanza FIN, los estados restantes
      # son menos preferidos y pueden
      # descartarse.
      si FIN alcanzado y quedan estados:
          libera el resto
          break

advance_state(state):
  camina vía state.elemIdx,
  recursa por:
    ramas ALT (en orden, deteniéndose
               una vez registrado FIN),
    BEGIN (entra al grupo; más camino
           opcional de salto si min = 0),
    END (loop back / exit / fast-forward —
         ver abajo),
    FIN (registra matchEndRow,
         guarda matchedState, y marca
         el contexto para que se poden
         los contextos posteriores dentro
         del rango del candidato — ver abajo),
  deteniéndose en cada variable encontrada:
      añade estado a ctx.states
      (deduplicando por elemIdx + counts)

Registrar un estado que alcanzó FIN hace más que simplemente marcar el match candidato. Bajo AFTER MATCH SKIP PAST LAST ROW, el siguiente match reportable debe comenzar estrictamente más allá del actual — por lo que, una vez que Advance ha terminado con el contexto que registró un candidato, todo contexto subsiguiente cuya fila de inicio caiga dentro del rango del candidato se poda en la misma fila, aun cuando el contexto que llegó a FIN pueda seguir buscando un match más largo mediante fallback codicioso.

La poda es segura porque, sin importar cómo termine esa búsqueda (un match más largo reemplaza al candidato, o el candidato se mantiene), todos los contextos podados comenzaron dentro de un rango que el siguiente match reportable debe saltar, y por tanto nunca podrían producir salida propia.

Este es el paso de poda en tiempo de FIN entre contextos. Dentro del contexto, FIN también corta el trabajo léxicamente inferior: Advance descarta los estados restantes en cola (descrito antes en esta sección), y dentro de un mismo DFS todo camino menos preferido — ramas ALT posteriores, el otro de los caminos de salto y entrada de BEGIN, el camino de entrada de una variable reluctante, el otro de los caminos de loop y exit de END — se detiene una vez registrado un match, de modo que un advance registra como mucho un match.

La lógica por elemento más delicada vive en el manejador de END. Cuando el conteo de iteraciones de un grupo está por debajo del límite inferior, el runtime debe volver al bucle; cuando está en o por encima del límite superior, debe salir; entre medias, ambas opciones son válidas y la codicia del cuantificador decide cuál probar primero:

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

  si count < elem.min:
      vuelve al cuerpo
      si elem es empty-loopable:
          # cuerpo nullable, ver §3.2
          clona también un estado fast-forward
          que sale del grupo con
          count satisfecho
          (primero fast-forward si el
           cuerpo prefiere vacío; el
           segundo camino se descarta si
           el primero alcanzó FIN)

  elif count >= elem.max:
      reinicia counts en esta profundidad
      sale vía next
      (END→END: incrementa el count
       del END exterior)

  else:
      # min <= count < max: bifurca
      construye un estado de salida
      (counts en esta profundidad reiniciados)
      si greedy:
          primero loop
          si loop alcanzó FIN:
              descarta el exit
              # prefiere más largo
          si no, exit en segundo lugar
      si no (reluctant):
          primero exit
          si exit alcanzó FIN:
              descarta el loop
              # prefiere más corto
          si no, loop en segundo lugar

Cada estado añadido a un contexto pasa por una comprobación de deduplicación que compara su posición y conteos con la lista de estados existente. Como Advance procesa las ramas en orden DFS, el estado de la primera rama de cualquier alternación aterriza primero — y cualquier rama posterior que produzca la misma posición y conteos se rechaza en la inserción. Esto es exactamente lo que pide la regla de orden léxico de §2.4, implementada en la base del runtime sin una pasada separada.

Grupos empty-loopable

Un caso sutil que el runtime tiene que desactivar es el grupo nullable — un grupo cuyo cuerpo puede coincidir con cero filas porque todo hijo del cuerpo es a su vez opcional. Los patrones como (A? B?)+ y (A | B*)+ tienen esta propiedad: según los datos, el cuerpo puede completar una iteración sin consumir ninguna fila. (Un único hijo opcional como (A?)* se reescribe a A* en tiempo de compilación y no deja ningún grupo.) Eso está bien en principio, pero crea un peligro real para la expansión épsilon del NFA. Si el cuerpo produce un match vacío, el elemento END vuelve al cuerpo (su jump es el primer hijo del grupo), el cuerpo vuelve a producir un match vacío, llega de nuevo a END, y así sucesivamente. Sin algo que lo detenga, el DFS de Advance nunca terminaría.

La guarda se decide en tiempo de compilación y se actúa sobre ella en tiempo de ejecución. Cada vez que el planner ve un grupo cuyo cuerpo es nullable, etiqueta el elemento END de ese grupo como empty-loopable. El runtime mantiene un bitmap de visitados, borrado antes de la expansión DFS de cada estado, en el que solo se marcan esos END etiquetados — nada más puede formar un ciclo, porque cualquier otro loop-back ha consumido una fila. Llegar a un END marcado significa que el cuerpo acaba de derivar una iteración vacía, y el estado no se descarta: en o por encima del límite inferior sale del grupo ahí (una iteración vacía detiene el cuantificador), y por debajo de él el estado cae al loop-back normal, de modo que cada llegada vacía sigue incrementando el conteo hasta alcanzar min. Tome (A? B?){2,3} sin que ninguna de las dos variables coincida en el flujo de filas:

iter 1: A? B? coinciden con cero filas
        → END, count = 1 (bajo min)
        END ya marcado (al entrar
        al grupo), pero bajo min:
        → vuelve a A?
iter 2: A? B? coinciden con cero filas
        → END, count = 2 (cumple min)
        END ya marcado, en min:
        → sale del grupo
sale con un match de longitud cero

Por debajo del límite inferior, la etiqueta empty-loop también indica al manejador de END que clone un estado adicional fast-forward junto al camino normal de loop-back:

advance_end (count por debajo de min):

  camino de loop-back:
    vuelve al cuerpo
    (mantiene la puerta abierta para un
     match real, no vacío en la
     siguiente iteración)

  si elem es empty-loopable:
    camino fast-forward:
      reinicia el count de esta profundidad
      sale del grupo vía next,
      tratando las iteraciones requeridas
      restantes como matches vacíos

Los dos caminos cumplen roles complementarios. El loop-back es el que captura el caso en que el cuerpo aún tiene matches reales que producir más adelante — por ejemplo, en (A? B?){2,3} seguido de datos donde A coincide solo en filas posteriores, el loop-back es lo que permite a las iteraciones segunda y tercera encontrar matches no vacíos. El fast-forward sale del grupo de inmediato, declarando "el resto de las iteraciones requeridas son vacías", y permite que el match tenga éxito con un cuerpo de longitud cero. El cuerpo, no la codicia del propio grupo, decide el orden: el fast-forward va primero exactamente cuando el cuerpo prefiere el match vacío (un cuerpo reluctante como (A?? B??)), y si el primer camino llega a FIN el segundo se descarta, de modo que un camino menos preferido no puede reemplazar al match preferido. La comprobación de deduplicación en el momento de la inserción impide que cualquiera de los caminos engendre más estados de la cuenta.

Más allá de la guarda de ciclos, un truco adicional al arranque desambigua los resultados de cero filas justo al inicio de un contexto. El paso de creación de contexto en cada fila potencial de inicio ejecuta un advance inicial mediante transiciones épsilon antes de consumir ninguna fila, usando una posición una fila anterior al inicio real. Cualquier camino que alcance el sentinela FIN solo a través de transiciones épsilon — sin consumir una fila — produce por tanto una posición de fin menor que la posición de inicio; esa coordenada de tramo negativo, combinada con si FIN se alcanzó realmente, codifica la diferencia entre un match vacío (match de longitud 0 aceptado) y un inicio no coincidente sin necesitar una bandera separada.

3.6 Cómo se mantiene acotado el espacio de estados

Mantener acotado el runtime no es el resultado de una única optimización. Es el efecto acumulativo de un conjunto de reglas de poda en capas, cada una capturando una causa distinta de crecimiento del espacio de estados en un punto distinto del ciclo por fila. Algunas se deciden en tiempo de compilación y simplemente se consultan en tiempo de ejecución; otras se disparan dinámicamente. Algunas matan estados individuales; otras matan contextos enteros. Las secciones anteriores introdujeron cada una en su contexto; la tabla siguiente las pone en una sola página.

Predicado fallido Match
Estados de variable cuyo DEFINE evaluó a falso en la fila actual — ramas muertas.
Avance inline de cadena END Match
Variables que han alcanzado su conteo máximo y que de otro modo dejarían el estado a mitad de iteración; se avanzan a través de fines de grupo de longitud fija para que la absorción pueda comparar en el punto correcto.
Absorción de contextos Absorb
Contextos más nuevos en los que cada estado se encuentra en un punto de comparación y está cubierto por un estado absorbible de un contexto más antiguo en el mismo elemento con un conteo mayor o igual — ver §2.5 para la regla conceptual, §3.2 para la elegibilidad en tiempo de compilación, §3.5 para la comprobación por par.
Deduplicación de estados Advance
Estados alcanzados por distintas ramas DFS que acaban en la misma posición con los mismos conteos — solo sobrevive el primero (léxicamente anterior); los equivalentes posteriores se descartan silenciosamente, que es también como se aplica la preferencia (§2.4).
Terminación temprana en FIN (dentro de contexto) Advance
Estados aún pendientes en la cola DFS cuando una rama llega a FIN — por orden léxico, todos los estados restantes son menos preferidos y pueden descartarse de inmediato.
Poda por match candidato (entre contextos) Advance
Otros contextos cuya fila de inicio cae dentro del rango del match candidato — el contexto que llegó a FIN puede seguir buscando un match más largo (fallback codicioso), pero bajo AFTER MATCH SKIP PAST LAST ROW cualquier contexto dentro del rango del candidato ya no puede producir una salida reportable, sin importar cómo termine esa búsqueda, y se poda en cuanto Advance ha terminado con el contexto que registró el candidato.
Guarda de ciclos Advance
Expansiones épsilon que llegan al END de un grupo nullable ya marcado dentro del mismo DFS (marcado al entrar a través de BEGIN, o en una llegada anterior) — de otro modo, iterarían para siempre; el estado sale del grupo ahí en o por encima del límite inferior, y sigue iterando por debajo de él.
Fast-forward de bucle vacío Advance
Por debajo del límite inferior de un grupo nullable, un camino adicional que sale del grupo con las iteraciones requeridas restantes declaradas vacías, ordenado frente al loop-back según la preferencia del cuerpo.
Corte por frame acotado Match
Contextos cuyo match ha alcanzado el límite superior del frame especificado por el usuario — forzados a mismatch para que no puedan extenderse más allá (§3.4).

Leer las entradas por su badge de fase traza la vida de un contexto: la poda se dispara en cada fila a través de las tres fases principales (Match, Absorb, Advance). Leer las descripciones, en cambio, agrupa las reglas por aquello a lo que apuntan: ramas muertas, contextos redundantes, estados equivalentes, bucles infinitos y sobreextensión más allá de los límites impuestos por el usuario.

Ninguna regla por sí sola sería suficiente. El fast-forward de bucle vacío por sí solo no detendría los bucles épsilon infinitos; la absorción por sí sola consolidaría en exceso cuando DEFINE referencia el inicio de match; la deduplicación por sí sola no eliminaría contextos redundantes, solo estados redundantes. El runtime se mantiene lineal en los casos que importan — PATTERN (A+ B+ C+ D) sobre 100.000 filas, el benchmark del panel ③ del póster — solo porque cada capa captura lo que las capas superiores pasan por alto. El código fuente documenta casos que las capas no capturan: la deduplicación mantiene separados los estados que solo difieren en conteos por encima de min, de modo que (A{2,} B)+ C con C nunca verdadero mantiene Θ(n²) estados en el pico y crea Θ(n³) de ellos (37 s sobre 320 filas), y una serie de alternaciones totalmente nullable se enumera camino a camino, de modo que (A?|B?){30} tarda más de media hora.

3.7 Salida de EXPLAIN

EXPLAIN ANALYZE sobre una consulta con RPR expone estadísticas a nivel de NFA que no están presentes para funciones de ventana ordinarias. En formato texto se emiten junto al operador de ventana, después de la línea Pattern:, de las líneas Nav Mark que haya (que el EXPLAIN simple también muestra) y de la línea Storage::

Nav Mark Lookback:  <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
  (cada una solo cuando DEFINE usa
   navegación que la alimenta)
NFA States: N peak, N total, N merged
NFA Contexts: N peak, N total, N pruned
NFA: N matched (len min/max/avg),
     N mismatched (len min/max/avg)
NFA: N absorbed (len min/max/avg),
     N skipped (len min/max/avg)
  (la segunda línea NFA solo cuando
   algún conteo no es cero; un conteo
   cero se imprime sin su (len ...))

Los formatos distintos de texto emiten cada conteo como su propia propiedad. Peak y total son instrumentación directa del runtime: cuántos estados llegaron a estar vivos a la vez, cuántos se crearon a lo largo de la vida de la consulta, y cuántos se fusionaron por deduplicación; pruned cuenta los contextos que fallaron tras una sola fila. Los histogramas de longitud de match separan cuatro resultados — matches exitosos, intentos de match que fallaron tras más de una fila (mismatched), contextos absorbidos y contextos liberados por AFTER MATCH SKIP PAST LAST ROW porque comenzaron dentro de un match registrado (skipped) — y reportarlos con min/max/avg hace visibles de un vistazo las patologías de rendimiento: una ejecución saludable muestra la mayoría de contextos como matched o absorbed, con longitudes mismatched pequeñas.

Los dos contadores Nav Mark reportan el presupuesto de retención del tuplestore que §3.3 deriva de DEFINE. Lookback es el alcance más profundo hacia atrás desde la fila actual a través de PREV, LAST con cualquier desplazamiento (incluido el 0 por defecto) y las formas compuestas con LAST interno; Lookahead es el alcance mínimo hacia adelante (negativo cuando mira antes del inicio de match) medido desde el inicio de match del contexto vivo más antiguo, contribuido por FIRST y las formas compuestas con FIRST interno.

Cada contador se imprime como un entero fijo cuando el desplazamiento es constante, "runtime" cuando el desplazamiento es una expresión no constante que solo se conoce por scan, y — solo para Lookback — "retain all" cuando el desplazamiento desborda; un Lookahead que desborda imprime "infinite". Cada línea se emite solo cuando alguna navegación en DEFINE la alimenta, y ambas aparecen también bajo el EXPLAIN simple: los desplazamientos constantes se fijan en la inicialización del executor, mientras que un desplazamiento que solo se conoce en tiempo de ejecución (un parámetro de un plan genérico, por ejemplo) imprime "runtime" ahí y su entero resuelto bajo EXPLAIN ANALYZE.

Juntos, estos contadores hacen posible depurar el rendimiento de RPR sin necesidad de adjuntar gdb al backend.

Más allá de los contadores, EXPLAIN imprime una línea Pattern: construida a partir del array de elementos compilado, por lo que muestra el patrón tras las reescrituras en tiempo de compilación (PATTERN (A A) se explica como a{2}) y lleva los marcadores de absorción # (punto de comparación) y ~ (región absorbible); DEFINE y la opción AFTER MATCH SKIP no se muestran. Reproducir las cláusulas tal como se escribieron, incluidos los cuantificadores reluctantes, la repetición de grupos y la opción de skip, es tarea de pg_get_viewdef(), que se esfuerza por hacer estable este round-trip para que pg_dump y pg_upgrade puedan preservar los objetos RPR sin deriva semántica — la suite de regresión bajo rpr_explain lo verifica caso por caso (véase §4).

§4. Pruebas — mapa de cobertura

El parche se distribuye con cinco suites de regresión que en conjunto ejercitan cada capa descrita en §3 — aproximadamente 22.000 líneas de SQL, cada suite centrada en una preocupación distinta. La división es deliberada: mantener separadas las cuestiones del parser, la corrección del runtime, las interacciones del planner y el formato de salida hace los fallos más fáciles de localizar, y evita que un cambio sin relación en una capa invalide accidentalmente pruebas de otra. Las cinco suites son:

rpr
Integración con la cláusula WINDOW — escenarios realistas de ventana sobre datos bursátiles sintéticos (forma en V, forma en W, subidas consecutivas, inversiones), además de la semántica de navegación y los errores de restricción de DEFINE.
rpr_base
Capa del parser — aceptación de palabras clave, formas sintácticas, cuantificadores, parseo de navegación, mensajes de error y estabilidad del round-trip pg_dump/pg_upgrade; además de una capa del planner — optimización de patrones, banderas de absorción, fallback de optimización, integración con el planner.
rpr_nfa
Runtime del NFA — el bucle de tres fases, la absorción en cada forma absorbible y los casos límite del ciclo de vida del contexto.
rpr_explain
Formato de salida — estadísticas del NFA, deparse de patrones, comillado de identificadores, estabilidad del formato tras recarga.
rpr_integration
Interacciones del planner — guardas que impiden que optimizaciones de ventana ajenas corrompan la semántica de RPR.

4.1 rpr — escenarios de extremo a extremo

La suite de escenarios es la cara pública del conjunto de pruebas: utiliza un dataset sintético de precios bursátiles de unas 1.600 filas y ejecuta sobre él consultas realistas — recuperación en V, forma en W (doble suelo), subidas y caídas consecutivas, patrones de inversión, particiones multi-símbolo. Estos escenarios son las únicas pruebas cuyas entradas y salidas se leen como consultas que un usuario podría escribir realmente; el resto del archivo, como las demás suites, es reductivo — anidamiento de PREV/NEXT y errores de desplazamiento no constante, reglas de referencia en DEFINE y semántica de los desplazamientos de navegación.

Como estas consultas combinan cada capa (parser, planner, executor, EXPLAIN), un único fallo en rpr rara vez indica dónde reside el bug. Las cuatro suites siguientes son la bisección: un fallo en rpr más un rpr_base aprobado descarta al parser; más un rpr_nfa aprobado lo acota a formas de datos específicas del escenario; más un rpr_integration aprobado descarta interferencia del planner; y cualquier deriva en deparse aparece en rpr_explain.

4.2 rpr_base — la superficie del parser

La suite base es la más grande, y lo es por una razón: es responsable de demostrar que cada pieza legal de sintaxis en §1.2 realmente se parsea, que cada pieza ilegal en §1.3 se rechaza con un error útil, y que cada forma aceptada sobrevive a un round-trip de serialización. La mayor parte está formada por fragmentos pequeños y focalizados — uno por característica sintáctica — en lugar de consultas largas y realistas, porque el objetivo es la cobertura, no el realismo de escenarios. Una segunda parte, la capa del planner, cubre la optimización de patrones, la visualización y el análisis de las banderas de absorción, el fallback de optimización y la integración con el planner (subconsultas, joins, operaciones de conjuntos, ordenación y agrupación).

Las pruebas de serialización merecen atención especial. Los objetos RPR (vistas, vistas materializadas, salida de pg_dump) deben hacer round-trip a través de la representación del catálogo sin deriva semántica, incluidas sutilezas como la bandera reluctant de un cuantificador o la forma exacta de una expresión de navegación compuesta. Un pequeño conjunto de objetos específicos para serialización (las vistas rpr_serial_v* y sus tablas de respaldo) se deja intencionadamente en su sitio al final de la ejecución, de modo que la infraestructura de regresión circundante pueda recogerlos y ejercitar pg_dump y pg_upgrade contra ellos. El resto del andamiaje de prueba se elimina como de costumbre. Defectos como una bandera reluctant que se pierde entre el deparse y el re-parse solo afloran cuando el round-trip se ejercita de extremo a extremo.

4.3 rpr_nfa — el motor de ejecución

Esta es la suite que ejercita cada mecanismo descrito en §3.5 y §3.6. Sus pruebas siguen un patrón consistente: filas VALUES en línea que llevan un array de nombres de variable que declara qué variables DEFINE coinciden en cada fila, emparejadas con un patrón que sondea un comportamiento específico del runtime. El idiom del array desacopla la prueba del runtime de la maquinaria de evaluación de DEFINE — lo que se está probando es "dado que estas variables coinciden aquí, ¿produce el bucle del NFA el tramo de match esperado?" en lugar de "¿calcula correctamente el evaluador de expresiones DEFINE estos booleanos?" El evaluador de DEFINE se prueba en otros sitios (rpr_base para el parseo, rpr para el comportamiento de extremo a extremo).

Una fixture típica tiene este aspecto — una columna de arrays de nombres de variable donde cada entrada dice qué variables DEFINE se disparan en esa fila, y un patrón cuyas cláusulas DEFINE prueban directamente esos nombres:

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

Leer la columna de arrays hacia abajo es leer directamente el escenario de prueba. Las filas 2 y 3 llevan ambos nombres — A y B se disparan ambos ahí, por lo que el NFA tiene una elección real sobre dónde cambiar de la rama A a la rama B. El match esperado (A en las filas 1–3 seguido de B en la fila 4, bajo la preferencia codiciosa del estándar) queda fijado solo por esas banderas, sin evaluación de expresión de ninguna consecuencia aquí — = ANY es solo la capa trivial que expone la columna de array a DEFINE, no lo que la prueba ejercita. Escribir el mismo escenario con un predicado numérico (price > PREV(price) y similares) enredaría la prueba del NFA con el comportamiento del evaluador de predicados; el idiom del array los mantiene limpiamente separados, y un fallo aquí apunta directamente al bucle del NFA.

La cobertura de la absorción es particularmente exhaustiva, porque la absorción es la optimización con mayor probabilidad de producir silenciosamente respuestas erróneas si se activa cuando no debería. Las pruebas cubren cada forma del análisis de casos de §3.2:

Más allá de la absorción, la suite cubre el ciclo de vida del contexto: contextos solapados bajo AFTER MATCH SKIP TO NEXT ROW, limpieza de contextos fallidos a mitad de flujo, finalización al fin de partición de contextos incompletos, y contextos encontrados después de que ya se haya registrado un match candidato en el contexto cabeza. Cada uno de estos mapea a una regla de poda específica en §3.6, y las pruebas están escritas para fallar de forma ruidosa si la regla falla (ya sea dejando vivos contextos redundantes, o matando un contexto que debería haber producido salida).

4.4 rpr_explain — estabilidad de la salida

La salida de EXPLAIN forma parte del contrato de cara al usuario — herramientas de terceros (paneles de monitorización, scrapers de logs) la parsean, y cambios que parecen cosméticos pueden romperlas. La suite rpr_explain verifica tres cosas:

Al igual que rpr_base, esta suite deja intencionadamente sus objetos en su sitio al final de la ejecución para que la cobertura de pg_dump y pg_upgrade se extienda también a los artefactos del lado de explain.

4.5 rpr_integration — interacciones del planner

El planner de PostgreSQL tiene muchas optimizaciones que operan sobre consultas de ventana — canonicalización de frames, pushdown de run-condition, deduplicación de ventanas idénticas, proyección de salida no usada, transiciones inversas de moving-aggregate — y cada una de ellas se diseñó sin RPR en mente. La mayoría son inseguras de aplicar cuando una ventana tiene una cláusula PATTERN: el frame es parte del contrato de match, la salida coincidente ya no es monótona en ningún sentido obvio, y dos ventanas con la misma especificación pero distintos DEFINE producen resultados genuinamente diferentes. La suite de integración verifica cómo trata cada una de estas optimizaciones a las ventanas RPR — la mayoría deben estar deshabilitadas o evitadas:

Canonicalización de frame
El planner normalmente reescribe ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING a ROWS UNBOUNDED PRECEDING para funciones de ventana independientes del frame como row_number, rank y ntile. El frame de RPR es el tramo del match, no una ventana de agregación, y debe permanecer literal.
Pushdown de run-condition
Un filtro WHERE monótono sobre la salida de una función de ventana normalmente puede empujarse al operador de ventana como condición de parada. Para RPR esto terminaría la coincidencia de patrones de forma prematura, posiblemente cortando matches a mitad de extensión.
Deduplicación de ventanas (RPR vs no RPR)
Dos ventanas con ORDER BY y frame idénticos normalmente se fusionarían en una. Una ventana RPR y una ventana no RPR nunca pueden compartir estado porque el lado RPR lleva resultados de match.
Deduplicación de ventanas (DEFINE o SKIP distinto)
Dos ventanas RPR con el mismo PATTERN pero distintas cláusulas DEFINE o un AFTER MATCH SKIP distinto producen matches distintos y deben permanecer separadas, aunque su forma estructural sea idéntica.
Proyección de salida no usada
Esta sí puede aplicarse: cuando la consulta circundante nunca lee la salida de la ventana, la función de ventana pasa a ser NULL y su WindowAgg se elimina, sin cambiar el número de filas. Las pruebas comprueban que las columnas que lee DEFINE siguen llegando al WindowAgg cuando este se mantiene, y que la ventana se conserva cuando se lee su valor.
Transiciones inversas de moving-aggregate
Las agregaciones de ventana con función de transición inversa normalmente pueden evaluarse incrementalmente a medida que el frame se mueve. El frame reducido de RPR no es una ventana deslizante; el camino de transición inversa produciría resultados erróneos.

Otros casos comprueban que la estimación de costes tiene en cuenta DEFINE, que una subconsulta que contiene una ventana RPR no se aplana, que las expresiones DEFINE no se filtran a un WindowAgg superior y que LIMIT permanece por encima del WindowAgg; un segundo grupo ejecuta RPR junto con CTE, joins, operaciones de conjuntos, sentencias preparadas, tablas particionadas y construcciones similares. La mayoría de los casos protegidos siguen la misma forma: una baseline que dispara la optimización (normalmente una consulta no RPR, comprobada en EXPLAIN), y luego una consulta RPR de forma estructuralmente similar en la que la optimización no se aplica — para el caso de deduplicación por DEFINE/SKIP la baseline son dos ventanas RPR idénticas, y el caso de transición inversa comprueba la evitación con una agregación que registra en el log en lugar de con EXPLAIN. Las dos mitades juntas demuestran que la guarda en el planner está haciendo trabajo real, no aprobando cada consulta sin verificación real.

Esta suite es también la razón por la que §3.4 es breve. Los mecanismos de "límites del match" — frame reducido, SKIP, INITIAL, corte por frame acotado — se prueban operacionalmente en otros sitios; lo que rpr_integration verifica es que ninguna otra etapa del optimizador los manipule en su recorrido. Un rpr_integration aprobado es lo que permite al resto de las suites confiar en que sus entradas llegan al executor sin manipulación.