Row Pattern Recognition Plongée technique

§1. Le standard, le sous-ensemble et les questions ouvertes

1.1 Portée du standard

Row Pattern Recognition a été introduit dans SQL par ISO/IEC 9075-2:2016 et est décrit dans le document compagnon ISO/IEC 19075-5:2021 (Partie 5, « Row Pattern Recognition »).

Le standard définit deux surfaces pour le même mécanisme sous-jacent. La fonctionnalité R010 place une clause MATCH_RECOGNIZE dans la liste FROM pour produire une table dérivée ; la fonctionnalité R020 intègre la même logique de motif dans une spécification WINDOW pour produire la sortie d'une fonction de fenêtrage. Les deux surfaces partagent l'essentiel de leur syntaxe et la totalité de leur sémantique, mais constituent des points d'entrée fonctionnellement distincts — une base de données peut implémenter l'une, l'autre, ou les deux.

La série de patchs discutée ici implémente un sous-ensemble de R020 uniquement ; la forme en clause de table est délibérément hors périmètre.

La surface R020 est petite mais expressive. Une requête attache un motif à une fenêtre en ajoutant trois clauses dans la spécification de fenêtre : PATTERN décrit une expression régulière sur des variables de motif nommées, DEFINE fournit le prédicat booléen qui identifie chaque variable, et AFTER MATCH SKIP contrôle la manière dont les correspondances successives sont positionnées au sein de la partition.

Les éléments optionnels MEASURES, SUBSET, INITIAL/SEEK, ainsi que la fonction auxiliaire CLASSIFIER() complètent la fonctionnalité. (La fonction MATCH_NUMBER() du standard appartient uniquement à la surface R010 — 19075-5 §6.3.3 (6) l'exclut explicitement de R020.)

Le patch couvre une part suffisante de ce vocabulaire pour faire fonctionner des requêtes non triviales, mais s'arrête avant plusieurs constructions dont l'implémentation dépend d'une infrastructure qui n'a pas encore été construite.

La suite de cette section partitionne le vocabulaire du standard entre ce que le patch prend déjà en charge et ce qui est intentionnellement laissé pour plus tard. Les listes ci-dessous reflètent l'état actuel de la série de patchs.

1.2 Fonctionnalités implémentées

Le vocabulaire implémenté suffit à exprimer les motifs canoniques en V, en W et de renversement (reversal) qui motivent à l'origine row pattern recognition. Il couvre également tous les quantificateurs standards — y compris les sept variantes reluctant *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}? — ainsi que les quatre primitives de navigation dont les conditions DEFINE ont besoin pour comparer des lignes adjacentes.

Clause PATTERN

Définit le motif de lignes au sein d'une spécification de fenêtre.

Regex : + * ? |

Quantificateurs standards et alternation.

Regex : ( ) groupement

Sous-motifs entre parenthèses.

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

Comptes de répétition bornés.

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

Les sept variantes reluctant (non gourmandes) définies par le standard (exclues de l'optimisation par absorption).

Clause DEFINE

Conditions booléennes identifiant chaque variable de motif.

Variable universelle de motif de ligne

Les références de colonnes non qualifiées dans DEFINE (p. ex. Price seul) se résolvent à la ligne courante, selon 19075-5 §4.10/§4.16.

PREV, NEXT (avec décalage)

Atteint la ligne située n rangs avant/après la ligne courante (par défaut 1) ; l'argument interne est une expression de valeur arbitraire évaluée sur la ligne ainsi atteinte.

FIRST, LAST (avec décalage)

Atteint une ligne relative à la correspondance ; FIRST(expr, n) cible la n-ième ligne après le début de la correspondance, LAST(expr, n) la n-ième ligne avant la dernière ligne correspondante.

Navigation composée (quatre formes)

Étape externe PREV/NEXT superposée à un FIRST/LAST interne : PREV(FIRST(expr)), NEXT(FIRST(expr)), PREV(LAST(expr)), NEXT(LAST(expr)) — l'étape interne et l'étape externe acceptent chacune leur propre décalage.

INITIAL

Les correspondances de motif doivent commencer à la ligne courante (par défaut).

AFTER MATCH SKIP PAST LAST ROW

Mode skip par défaut ; éligible à l'absorption de contexte.

AFTER MATCH SKIP TO NEXT ROW

Permet le chevauchement des correspondances ; désactive l'absorption.

1.3 Non implémenté

Les fonctionnalités encore non implémentées se regroupent de manière lâche en trois familles. La première — et de loin la plus importante — est la famille de constructions centrées sur MEASURES : la clause MEASURES elle-même, SUBSET, CLASSIFIER(), les références de colonnes qualifiées par motif comme B.price, et la navigation qualifiée par motif comme LAST(B.price) ou PREV(B.price).

Il ne s'agit pas de lacunes indépendantes, mais plutôt de différentes vues d'une seule pièce manquante : l'exécuteur devrait conserver un historique par correspondance (per-match history) — un enregistrement, pour chaque ligne de la correspondance, de la variable de motif à laquelle elle a été mappée — et aucune de ces constructions n'a de définition significative sans cet historique. CLASSIFIER() lit le nom de la variable dans cet enregistrement ; B.price lit la colonne price des lignes dont l'entrée d'enregistrement vaut B ; LAST(B.price) parcourt le même ensemble de lignes et en sélectionne la dernière ; SUBSET U = (A, B) définit une variable virtuelle qui agrège les deux compartiments ; et MEASURES évalue des expressions comme AVG(U.Price) en utilisant précisément cette agrégation.

L'exécuteur actuel évalue les prédicats DEFINE ligne par ligne mais n'enregistre nulle part les affectations de variables qui en résultent — il n'y a rien à interroger ensuite. Construire l'infrastructure d'historique est donc la condition préalable à tout ce groupe ; les fonctionnalités individuelles en découlent comme de petites projections une fois les enregistrements présents.

La deuxième famille concerne les cibles de skip alternatives : AFTER MATCH SKIP TO label, AFTER MATCH SKIP TO FIRST var, et AFTER MATCH SKIP TO LAST var. Elles dépendent également de l'historique de correspondance, puisque l'exécuteur doit pouvoir pointer sur une ligne étiquetée précise au sein de la correspondance la plus récente.

Les éléments restants forment une queue hétérogène : le mot-clé SEEK (l'alternative à INITIAL), le motif vide (), la forme d'exclusion {- … -}, et l'opérateur insensible à l'ordre PERMUTE.

MEASURES

Expressions de sortie nommées par correspondance, par exemple MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg ; en R020, exposées via OVER à la manière d'une fonction de fenêtrage. Accepte les mots-clés FINAL / RUNNING (19075-5 §5.4), qui en R020 se réduisent à la même valeur puisque les measures sont toujours évaluées sur la dernière ligne de la correspondance (19075-5 §6.9 (3)).

SUBSET

Unions nommées de variables de motif, par exemple SUBSET U = (A, B, C). Utilisable partout où une variable de motif peut être référencée — MEASURES, références qualifiées par motif dans DEFINE, CLASSIFIER(U) — qui requièrent tous l'historique de correspondance.

CLASSIFIER()

Renvoie à quelle variable de motif une ligne donnée a été mappée. Définie pour DEFINE et MEASURES (19075-5 §5.9) ; la réponse pour une ligne donnée est le nom de variable enregistré dans l'historique de correspondance pour cette ligne.

Référence de colonne qualifiée par motif

Forme nue B.price dans DEFINE ou MEASURES — la valeur de la colonne issue de la ligne mappée à la variable nommée.

Navigation qualifiée par motif

Restreint la navigation aux lignes mappées à une variable nommée, par exemple LAST(B.price), FIRST(B.price), PREV(B.price), NEXT(B.price).

SEEK

La correspondance peut commencer n'importe où dans la fenêtre (par opposition à INITIAL).

AFTER MATCH SKIP TO label

Saut vers une ligne étiquetée.

AFTER MATCH SKIP TO FIRST var

Saut vers la première ligne mappée à la variable nommée.

AFTER MATCH SKIP TO LAST var

Saut vers la dernière ligne mappée à la variable nommée.

Regex : {- -}

Exclusion — retire les lignes correspondantes de la sortie par correspondance.

Regex : ()

Motif vide — correspond à la séquence vide.

PERMUTE(...)

Mise en correspondance insensible à l'ordre sur les variables listées.

Fonctions d'agrégation dans DEFINE

Les agrégats tels que SUM, AVG, COUNT ne sont pas permis dans les prédicats DEFINE. Le standard les autorise comme agrégats courants (running aggregates) sur la correspondance partielle (évaluation par ligne sur les lignes déjà mappées à une variable), ce qui dépend du même historique par correspondance que MEASURES/CLASSIFIER().

Quatre autres points méritent d'être notés ici, car ils sont aisément confondus avec des omissions.

Le premier est que les ancres de motif ^ et $ ne sont pas permises avec RPR dans la clause WINDOW par le standard lui-même (19075-5 §6.13 : « the anchors (^ and $) are not permitted with row pattern matching in windows » ; définition sous-jacente à 19075-5 §4.14.1) ; leur absence relève de la conformité, non d'une lacune.

Le second est que MATCH_NUMBER() est de même exclu de R020 par le standard (19075-5 §6.3.3 (6) et 19075-5 §6.9 (1)) — il appartient uniquement à la surface R010, et son absence ici relève à nouveau de la conformité, non d'une fonctionnalité manquante.

Le troisième est un ensemble d'interdictions structurelles que le standard impose à R020 (19075-5 §6.17) : row pattern recognition ne peut pas être imbriquée dans une autre row pattern recognition ; MEASURES et DEFINE ne peuvent pas contenir de références externes ; les sous-requêtes à l'intérieur de MEASURES ou DEFINE ne peuvent pas référencer de variables de motif ; et RPR ne peut pas être utilisée à l'intérieur d'une requête récursive.

Le quatrième est que MATCH_RECOGNIZE lui-même — la fonctionnalité R010, la surface en clause de table du même mécanisme — est hors périmètre pour ce patch. Le fait que PostgreSQL ajoute ou non R010 à terme sera une question pour une série future, et non une mesure de celle-ci.

§2. Exemples — Comment cela fonctionne réellement

Les exemples de cette section se construisent de manière incrémentale. On commence par la raison conceptuelle pour laquelle la mise en correspondance de motifs sur des lignes est véritablement différente de la mise en correspondance de motifs sur des chaînes de caractères, puis on présente les quatre fonctions de navigation qui rendent les conditions DEFINE intéressantes, et l'on déroule enfin trois traces de bout en bout : une correspondance unique (mouvement de la NFA), l'absorption de contexte dans le cas facile, et le cas où l'absorption devient dangereuse.

Le mécanisme interne qui rend la navigation peu coûteuse — l'échange à un seul slot de tuple — relève de la conception de l'exécuteur et est traité dans la section suivante, pas ici.

2.1 Pourquoi les motifs de lignes diffèrent des motifs de texte

Une expression régulière textuelle met en correspondance un flux de caractères, et à chaque position il y a exactement un symbole à considérer. La question d'exécution — « le symbole courant est-il égal à 'A' ? » — a une réponse unique oui/non. Les automates à backtracking exploitent ce fait : au plus une branche survit par caractère, et le coût de l'ambiguïté est payé en relisant l'entrée.

Un motif de lignes diffère d'une manière fondamentale. Une ligne n'est pas un symbole unique ; c'est un tuple de colonnes évalué contre un ensemble de prédicats booléens, les conditions DEFINE. Deux prédicats peuvent être vrais simultanément sur la même ligne, et rien dans le standard ne dit qu'ils doivent être mutuellement exclusifs. Considérez :

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

Une ligne avec price = 150, volume = 2000 satisfait à la fois A et B mais pas C. Le pattern matcher ne peut pas réduire cela à un état unique — deux variables de motif sont vivantes, et tout élément de motif qui en nomme l'une ou l'autre peut avancer. La NFA doit donc porter plusieurs états simultanés par ligne de partition, et non un seul.

Cette seule observation conditionne le reste de l'architecture. L'état d'exécution est une liste de contextes, chaque contexte est une liste d'états, et à chaque ligne le runtime demande à chaque état : « étant données les variables qui sont vraies ici, où puis-je aller ? » Les bifurcations qui en résultent expliquent pourquoi le runtime a besoin de plusieurs couches d'élagage — déduplication d'états au sein d'un contexte, absorption entre contextes, et les autres règles passées en revue au §3.6 — sans lesquelles le nombre d'états et de contextes vivants croît avec la partition et la mise en correspondance de motifs devient super-linéaire.

2.2 Fonctions de navigation

Les conditions DEFINE qui ne référencent que la ligne courante sont limitées ; presque tout motif intéressant doit comparer la ligne courante à ses voisines ou aux lignes déjà acceptées plus tôt dans la correspondance. Le standard fournit quatre fonctions de navigation pour cela, et le patch les implémente toutes.

PREV(expr [, n])

La ligne située n rangs avant la ligne courante (par défaut n = 1). Utilisée pour des comparaisons « aujourd'hui vs. hier ».

NEXT(expr [, n])

La ligne située n rangs après la ligne courante. Anticipation en avant ; peu fréquente sous la forme fenêtre car la fenêtre est monotone.

FIRST(expr [, n])

La n-ième ligne correspondante de la correspondance courante, comptée depuis le début. « Comparer avec la ligne qui a commencé cette correspondance. »

LAST(expr [, n])

La n-ième ligne correspondante la plus récente. « Comparer avec la ligne correspondante la plus récente. »

Les quatre primitives se composent : PREV et NEXT peuvent encapsuler un appel FIRST ou LAST, donnant quatre formes composées dont la sémantique est « aller à une ligne relative à la correspondance, puis se décaler d'une distance fixe ». C'est ce qui permet à une expression DEFINE de lire, par exemple, la ligne immédiatement antérieure au début de la correspondance.

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

Reculer de m rangs depuis la n-ième ligne de la correspondance (par défaut m = 1). « Quelle était la valeur juste avant le début de cette correspondance ? »

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

Avancer de m rangs depuis la n-ième ligne de la correspondance. Atteint plus loin dans la correspondance sans dépendre de la ligne courante.

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

Reculer de m rangs depuis la n-ième ligne correspondante la plus récente. « Comparer avec une ligne peu avant la dernière correspondance. »

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

Avancer de m rangs depuis la n-ième ligne correspondante la plus récente.

Deux remarques pratiques s'imposent. Premièrement, la navigation peut être composée : PREV(FIRST(price)) lit la ligne immédiatement antérieure au début de la correspondance, et le patch le supporte. Deuxièmement, la navigation a des conséquences sur les optimisations de l'exécuteur. PREV et NEXT sont relatifs à la ligne courante et sont toujours sûrs ; FIRST et les variantes de LAST avec décalage sont relatifs aux frontières de la correspondance, ce qui interagit avec l'absorption de contexte et force le planner à garder vivants certains contextes qu'il aurait sinon écartés. Le mécanisme de cette interaction est le sujet du §2.6.

2.3 Exemple détaillé 1 — Mouvement de la NFA

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

Le motif s'aplatit en quatre éléments :

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

Pour la série de prix 100, 110, 120, 115, 108, 130 :

Point clé : à la ligne 3, la ligne satisfait à la fois START (toujours vrai) et DOWN, mais le seul état ayant survécu à la ligne 2 est sur la branche de sortie DOWN, donc seule la transition UP → DOWN est prise. La nature multi-états du §2.1 est visible comme un éventail à chaque correspondance UP (l'état pourrait rester sur UP+ ou avancer vers DOWN+). La préférence greedy est « rebouclons avant de sortir », si bien qu'avec assez de données les branches en boucle prolongeraient davantage la correspondance ; ici, le DOWN en boucle meurt à la ligne 5 (130 ≮ 108), et le candidat FIN antérieur (lignes 0–4) — produit quand DOWN est sorti à la ligne 4 — est finalisé comme la correspondance.

Le résultat de la requête découle directement de cette trace. Sous la sémantique RPR, les fonctions de fenêtrage first_value(price) et last_value(price) ne sont évaluées qu'à la ligne qui a commencé la correspondance — toute autre ligne dans la correspondance produit NULL pour ces fonctions de fenêtrage, puisque sa frame réduite est vide. La sortie pour nos données ressemble donc au tableau que le poster montre dans son panneau supérieur droit :

La ligne 0 est le début de la correspondance, donc sa frame couvre les lignes 0–4 et les fonctions de fenêtrage rapportent le prix d'ouverture ($100) et le prix le plus bas ($108) du V. Les lignes 1–4 sont à l'intérieur de la correspondance mais n'en sont pas le début, elles reçoivent donc NULL. La ligne 5 (prix $130) est en dehors de toute correspondance et reçoit également NULL.

2.4 Exemple détaillé 2 — Alternation et ordre lexical

La forme (A | B) donne au matcher un choix : à n'importe quelle ligne, les deux alternatives sont testées indépendamment, et un nombre quelconque d'entre elles peut correspondre. C'est ici que la nature multi-états du §2.1 devient visible à l'intérieur d'un seul contexte — non pas entre contextes (cela, c'est l'absorption), mais le long de branches parallèles que l'exécuteur explore en parallèle synchrone.

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

Imaginez une ligne où le prix a à la fois augmenté et dépassé 100 $ — UP et HIGH sont tous deux vrais. Chaque alternative engendre son propre état : l'un parcourant la branche UP, l'autre la branche HIGH. Ils progressent en parallèle jusqu'à ce que DONE les résolve.

Les deux branches produisent une correspondance de même longueur sur les mêmes lignes, laissant au matcher deux chemins candidats — l'un étiqueté UP, DONE et l'autre HIGH, DONE. Le standard résout cela par l'ordre lexical : parmi les alternatives écrites dans (UP | HIGH), celle écrite en premier l'emporte, indépendamment de la longueur de la correspondance. Comme UP apparaît avant HIGH, le chemin survivant est UP, DONE.

L'ordre lexical est ce qui rend CLASSIFIER() bien défini lorsqu'il sera finalement implémenté — il permet au runtime de dire à l'utilisateur « cette ligne a correspondu à UP, pas à HIGH » même lorsque les deux prédicats étaient vrais. L'ordre lexical est la règle principale pour l'alternation : une branche lexicalement antérieure l'emporte sur une lexicalement postérieure même si cette dernière produirait une correspondance plus longue, et une branche lexicalement postérieure (potentiellement plus courte) peut tout de même l'emporter si toutes les branches lexicalement antérieures meurent avant d'atteindre FIN. La longueur greedy se décide au sein d'un seul quantificateur — étant données deux complétions de la même branche d'alternation, le quantificateur greedy préfère plus d'itérations.

2.5 Exemple détaillé 3 — Absorption de contexte (même sort)

Le motif le plus simple qui exhibe l'absorption est PATTERN (A+) avec DEFINE A AS TRUE. Chaque ligne correspond à A, et le standard exige que le matcher considère chaque ligne comme un début de correspondance possible. Naïvement, cela signifie N contextes pour une partition de N lignes. Prenons une partition de cinq lignes (n'importe quelles données — le prédicat est constamment vrai) :

La mémoire passe de O(n) à O(1). La règle d'absorption qui justifie l'élimination est directe lorsque le quantificateur est non borné :

Le panneau inférieur gauche du poster (« ① Context Absorption ») est exactement cette règle visualisée sur cinq lignes.

Un point subtil mais important se cache dans la règle : l'élimination est sûre parce que le prédicat A AS TRUE évalue à la même valeur à chaque ligne, indépendamment du contexte qui pose la question. Il en va de même pour tout prédicat qui ne référence que la ligne courante ou un décalage fixe par rapport à elle — y compris PREV. L'exemple suivant passe à une semaine concrète de prix, en utilisant un prédicat à base de PREV, et le §2.6 réutilisera précisément cette même semaine pour rendre évidente la symétrie entre absorption sûre et absorption dangereuse :

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

Prenons la semaine de bourse 100 $, 108 $, 112 $, 116 $, 110 $ du lundi au vendredi — quatre hausses suivies d'une chute soudaine. Supposons que C1 démarre le mardi (le premier jour où RISE correspond : 108 $ > 100 $), et que l'exécuteur suive spéculativement aussi C2 à partir du mercredi. La condition RISE de chaque ligne compare le prix de la ligne à son prédécesseur immédiat — un fait au niveau de la partition, non au niveau du contexte — si bien que les deux contextes sont contraints de calculer le même booléen à chaque ligne qu'ils partagent :

L'histoire se brise à l'instant où le prédicat commence à dépendre des frontières propres de chaque contexte — et c'est de cela que traite le §2.6.

2.6 Exemple détaillé 4 — Quand l'absorption devient dangereuse

Supposons qu'un analyste cherche les jours de bourse consécutifs où une action est restée à moins de dix dollars du cours du jour où la série a démarré — une sorte de fenêtre de consolidation. Le motif et le DEFINE ressemblent à ceci :

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

La condition compare désormais le prix de la ligne courante au prix au début de la série courante. Deux séries qui ont démarré à des jours différents ont des valeurs FIRST(price) différentes, si bien que deux états au même élément de motif et au même compte ne sont plus interchangeables : leurs futurs dépendent de la frontière que l'absorption était sur le point de jeter.

Prenons exactement la même semaine de bourse qu'au §2.5 — 100 $, 108 $, 112 $, 116 $, 110 $ du lundi au vendredi. Le runtime garde à nouveau deux séries candidates vivantes en même temps : C1 a démarré lundi, C2 a démarré mardi (chaque ligne est un début de série potentiel sous STABLE+).

Sous absorption, C2 aurait été fusionné dans C1 le mardi — le contexte fusionné ne garde qu'un seul plafond, donc la vue distincte de C2 (plafond 118 $, la série de quatre jours qui ne se termine que le samedi) n'est plus récupérable depuis l'état interne. C2 doit rester vivant parce qu'il est un candidat de correspondance indépendant dont le runtime pourrait encore avoir besoin : une fois la correspondance de C1 terminée le mercredi, la prochaine tentative doit reprendre depuis un C2 toujours en cours plutôt que de repartir de zéro. Chaque fois qu'un prédicat DEFINE porte une dépendance au début de correspondance, le planner désactive donc l'absorption préventivement.

(Lorsque la correspondance du contexte de tête réussit, les contextes qui ont démarré à l'intérieur de sa portée acceptée — sous le AFTER MATCH SKIP PAST LAST ROW par défaut — sont simplement éliminés ; ils ne sont gardés vivants que pour que le runtime ait un repli si la correspondance de tête échoue.)

Le tableau de dépendance sur le panneau inférieur droit du poster (« ② Navigation ») résume quelles formes de navigation créent une dépendance au début de correspondance :

Les deux exemples des §2.5 et §2.6 se ramènent à une seule règle. Le même sort est ce qui rend l'absorption sûre : si tout contexte au même élément de motif calculera la même réponse à tout prédicat futur, seul le plus ancien doit être conservé. Des sorts différents rendent l'absorption dangereuse : dès que les prédicats bifurquent sur un état privé au contexte — précisément ce que font FIRST et LAST avec décalage — chaque contexte vivant représente un futur qu'aucun autre contexte ne peut récupérer, et en jeter un risque de produire une mauvaise réponse.

Le planner détecte cette distinction à la compilation et décide par contexte si l'absorption s'applique. C'est aussi pourquoi le benchmark du poster dans le panneau ③ reste linéaire à la fois dans les cas de succès et d'échec : quand l'absorption est sûre, le runtime fusionne les contextes, et quand elle ne l'est pas, le planner accepte le coût multi-contextes plutôt que de risquer une mauvaise réponse.

Les chiffres du benchmark sur le poster sont le même algorithme déployé à grande échelle. Sur le motif de succès (A+ B+ C+ D), PostgreSQL et Trino passent tous deux à l'échelle en O(n) dès qu'une correspondance est confirmée, et l'avance de PostgreSQL — environ 16× à 33× — provient majoritairement de l'écart JVM.

Sur le motif d'échec (A+ B+ C+ E), Trino n'a pas d'absorption et dégrade en O(n²) en poursuivant chaque début de correspondance potentiel ; à 100 000 lignes il prend plus de cinq heures, tandis que PostgreSQL termine encore en 92 ms, soit une accélération d'environ 217 000×.

Cet écart n'est pas une finition d'ingénierie — c'est précisément la distinction même-sort / sorts-différents des §2.5 et §2.6, appliquée à chaque ligne de chaque début de correspondance potentiel dans la partition.

2.7 Exemple détaillé 5 — Quand SKIP désactive l'absorption

L'exemple précédent brisait l'absorption du côté données : FIRST dans DEFINE faisait évaluer les prédicats différemment à chaque contexte. L'absorption peut aussi se briser du côté sortie, et la clause AFTER MATCH SKIP est ce qui contrôle cela.

Considérons le motif PATTERN (A+) avec DEFINE A AS TRUE sur cinq lignes qui correspondent toutes à A. Sous le AFTER MATCH SKIP PAST LAST ROW par défaut, le matcher trouve la plus longue correspondance commençant à la ligne la plus précoce puis la dépasse ; tout contexte ayant démarré à l'intérieur de cette correspondance est implicitement éliminé comme redondant — exactement la situation pour laquelle l'absorption est conçue. La sortie est une seule correspondance, lignes 0–4, et le runtime n'a besoin que d'un contexte vivant.

Passez le mode skip à AFTER MATCH SKIP TO NEXT ROW et le contrat change :

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

Désormais, chaque position de départ potentielle doit être rapportée séparément, même lorsque les correspondances se chevauchent. Pour les mêmes cinq lignes, le runtime est tenu d'émettre cinq correspondances : lignes 0–4, 1–4, 2–4, 3–4 et 4–4. Aucune ne peut être remplacée par une « plus longue commençant plus tôt », parce que le standard dit que l'utilisateur les veut toutes.

Notez que le prédicat n'a pas changé. A AS TRUE évalue de la même manière à chaque ligne, indépendamment du contexte qui pose la question, si bien que la condition de même sort du §2.5 est encore satisfaite. Ce qui change, c'est l'exigence de sortie : même des contextes aux futurs identiques doivent coexister parce qu'ils correspondent à des lignes distinctes du résultat. Le planner désactive donc l'absorption de contexte chaque fois que AFTER MATCH SKIP TO NEXT ROW est en vigueur, indépendamment de la clause DEFINE.

Mettre les §2.6 et §2.7 côte à côte donne l'image complète des cas où l'absorption échoue :

L'une ou l'autre des conditions suffit à désactiver l'absorption pour les contextes affectés. Lorsqu'aucune n'est en vigueur — le AFTER MATCH SKIP PAST LAST ROW par défaut avec des conditions DEFINE n'utilisant que PREV, NEXT ou un LAST nu — le runtime se réduit à un seul contexte par position de motif et reste linéaire jusqu'au bout.

§3. Conception — Du parser à l'exécuteur

Row Pattern Recognition est implémenté comme trois étapes qui se passent le travail à travers des formes intermédiaires bien définies. Le parser transforme le texte SQL en un arbre de motif et une liste de prédicats DEFINE ; le planner compile l'arbre en un tableau plat d'éléments de motif et décide lesquels peuvent participer à l'absorption de contexte ; l'exécuteur fait tourner le tableau contre la partition ligne par ligne dans une boucle à trois phases. Chaque étape a sa propre forme de données, et l'essentiel de l'ingéniosité de conception se situe aux frontières : une NFA plate qui tient en cache, un modèle de navigation qui réutilise un seul slot de tuple plutôt que d'en matérialiser un par référence, et une règle d'absorption qui transforme une mémoire 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

Les sections ci-dessous parcourent ce pipeline. Le §3.1 traite du parser et de la forme de l'arbre de motif ; le §3.2 traite de la compilation qui transforme l'arbre en NFA plate ; le §3.3 traite du modèle de navigation que les prédicats DEFINE utilisent pour consulter les lignes voisines ; le §3.4 traite de la gestion des frontières de correspondance — les règles SKIP, INITIAL et de frame bornée qui fixent où une correspondance commence et se termine ; le §3.5 est le moteur par ligne en trois phases ; le §3.6 rassemble tous les mécanismes d'élagage qui maintiennent l'espace d'états borné ; et le §3.7 passe en revue ce que l'implémentation expose dans la sortie d'EXPLAIN.

3.1 Parser — construction de l'arbre de motif

Le parser reconnaît la pattern recognition par la présence d'une clause PATTERN dans une spécification de fenêtre. Sa première tâche est la validation de la frame, puisque RPR impose des contraintes que les requêtes de fenêtrage ordinaires n'ont pas : le mode de frame doit être ROWS (et non RANGE ou GROUPS), la borne de début doit être CURRENT ROW, et les options EXCLUDE sont interdites. Ce sont des contrôles de conformité, non des optimisations — la notion de frame en RPR est la portée de la correspondance, et le standard n'envisage pas de la remplir avec autre chose que les lignes correspondantes.

Une fois la frame validée, le parser transforme la clause PATTERN en un arbre construit à partir de quatre sortes de nœuds — une référence de variable, une séquence (concaténation), une alternation, et un groupe (sous-motif entre parenthèses). Chaque nœud porte le quantificateur sous forme de trois nombres — une borne inférieure, une borne supérieure (éventuellement infinie), et un drapeau de mise en correspondance reluctant :

Chaque prédicat DEFINE est ensuite vérifié typologiquement contre les colonnes de la partition et coercé en une expression booléenne. Deux choses pratiques se produisent à cette occasion. Premièrement, chaque colonne référencée par un prédicat DEFINE est enregistrée comme faisant partie des exigences de sortie de la requête, si bien que le planner propage ces colonnes jusqu'à l'étape de l'exécuteur même si la requête englobante ne les sélectionne pas — sans cela, le runtime n'aurait rien sur quoi évaluer. Deuxièmement, les variables qui apparaissent dans PATTERN mais jamais dans DEFINE sont implicitement vraies : elles correspondent à chaque ligne.

3.2 Compilation — de l'AST à une NFA plate

Le planner transforme l'arbre du parser en la structure de données que l'exécuteur fera tourner : un tableau plat d'éléments de motif adressés par indice. La compilation procède selon un pipeline en six étapes :

compile(astTree):
  1. optimiser l'AST
  2. mesurer taille et profondeur
  3. allouer le tableau d'éléments
  4. remplir depuis l'AST
       (assigner pointeurs next/jump)
  5. finaliser — installer la sentinelle FIN
  6. marquer les éléments éligibles à l'absorption

La forme plate est choisie pour une raison simple : l'exécuteur doit traverser le motif de nombreuses fois par partition, et un tableau contigu adressable par indice est la structure de données la moins coûteuse à parcourir. Les étapes 1 et 6 sont les intéressantes — l'étape 1 parce qu'elle détermine la taille du tableau, et l'étape 6 parce qu'elle décide si l'optimisation par absorption du §2.5 s'engagera ou non.

Optimisation de l'AST

L'optimisation paie deux fois : une fois dans le nombre statique d'éléments du tableau plat, et une autre fois à chaque ligne traitée au runtime. Chaque transformation réduit l'espace d'états que le runtime doit énumérer. L'optimiseur applique huit règles de réécriture en succession jusqu'à ce que l'AST cesse de changer :

Aplatissement de SEQ

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

Fusion de variables consécutives

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

Fusion de groupes consécutifs

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

Fusion d'ALT consécutives

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

Absorption de préfixe/suffixe

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

Aplatissement et déduplication d'ALT

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

Multiplication de quantificateurs

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

Déballage de fils unique

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

La multiplication de quantificateurs est la seule transformation qui requiert un contrôle de sûreté : l'optimiseur ne fusionne que dans trois cas sûrs — les deux quantificateurs non bornés ((A+)+ → A+), l'externe exact ((A{2,3}){5} → A{10,15}), ou l'enfant trivial {1,1} ((A){2,5} → A{2,5}). D'autres combinaisons peuvent introduire des trous que la forme plate manquerait — par exemple, (A{2}){2,3} n'accepte que {4, 6}, mais un A{4,6} naïf accepterait aussi 5 — l'optimiseur les laisse donc intactes.

Forme d'un élément

Chaque élément du tableau plat représente une position unique dans le motif. Il y a cinq sortes logiques : une référence de variable (la seule sorte qui consomme une ligne) ; des marqueurs group begin et group end, qui ouvrent et ferment un sous-motif entre parenthèses ; un marqueur d'alternation, qui mène une liste de branches ; et un marqueur de fin à la fin du motif.

Chaque élément porte également une profondeur (son niveau d'imbrication de groupe), le quantificateur (un nombre min et max de répétitions, éventuellement infini), et deux pointeurs de transition — next, « où aller après avoir consommé cet élément », et jump, « où sauter » (utilisé par l'alternation pour chaîner les branches, par group begin pour contourner le corps quand le quantificateur autorise zéro, et par group end pour reboucler vers le corps).

Pour PATTERN ((A B)+) le tableau compilé ressemble à ceci :

PATTERN ((A B)+) compiles to:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    (ouvre le groupe ; jump saute
     vers FIN si min = 0)

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

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

[3] END    depth 0  quant 1..∞
    next → 4  jump → 1
    (ferme le groupe ; jump reboucle)

[4] FIN    motif complet

Le motif se lit de gauche à droite via next, jump gérant les arêtes non linéaires. À l'idx 3, le jump de END pointe en arrière vers l'idx 1, ce qui est la manière dont le quantificateur externe non borné boucle ; à l'idx 0, le jump de BEGIN sauterait par-dessus END jusqu'à l'idx 4 si le groupe était optionnel. Le runtime n'a jamais à construire un graphe au runtime — il se contente de suivre ces deux pointeurs en parcourant le tableau.

Attributs par élément

Au-delà de la forme, chaque élément porte quatre attributs logiques qui dirigent le comportement du runtime à cette position :

Reluctant

Inverse l'ordre de l'expansion du quantificateur. Les quantificateurs greedy essaient « reboucler » avant « sortir » ; les quantificateurs reluctant essaient « sortir » d'abord. Porté par la variable pour A+? ; porté par les BEGIN et END du groupe pour ((…)+?).

Empty-loopable

Posé sur les fins de groupe dont le corps est nullable ((A?)*, (A? B?)+, (A | B*)). Indique au runtime d'ajouter une sortie « fast-forward » en parallèle du loop-back normal, afin que le garde-cycle ne tue pas des correspondances légitimes dans les groupes qui peuvent produire des itérations vides.

In-absorbable-region

Marque chaque élément situé au sein d'une région éligible à l'absorption — utilisé par le runtime pour suivre si l'état courant est encore en territoire sûr.

Absorption-comparison-point

Marque l'élément précis où les comparaisons d'absorption doivent s'exécuter. Pour un simple A+, il atterrit sur la variable ; pour un groupe non borné comme (A B)+, il atterrit uniquement sur la fin de groupe.

La distinction entre « in-region » et « comparison-point » importe parce que l'absorption n'a de sens qu'aux points où les itérations se ferment. À l'intérieur du corps de (A B)+, le runtime est en mi-itération et le compte n'a pas encore atteint sa valeur finale pour ce tour ; comparer ici reviendrait à comparer des valeurs incomparables. L'état doit atteindre la fin de groupe avant que le runtime ne puisse décider. Le premier attribut dit donc « vous êtes toujours en territoire absorbable » ; le second dit « vous avez atteint le point de comparaison — allez vérifier maintenant ».

Analyse d'absorbabilité

L'étape 6 de la compilation est ce qui donne à la règle « même sort » du §2.5 son témoin à la compilation. La décision est en couches :

isAbsorbable(query):
  si mode SKIP != SKIP PAST LAST ROW
      → return false
  si fin de frame != UNBOUNDED FOLLOWING
      → return false
  si un DEFINE dépend de match_start
      → return false
  parcourir l'AST et marquer
  les éléments qui satisfont
  un cas structurel

Les trois premiers contrôles sont au niveau de la requête : ils correspondent exactement aux conditions du §2.7 (côté sortie : mode SKIP), à la frame bornée (la borne brise la monotonicité), et au §2.6 (côté données : FIRST ou LAST avec décalage dans DEFINE). Lorsque l'un d'eux échoue, l'analyse ne pose aucun drapeau et l'absorption est désactivée pour toute la requête. Lorsqu'ils passent tous, le parcours de l'AST admet trois formes structurelles :

Cas 1 — Variable non bornée simple

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

Chaque itération vaut exactement une ligne. Le compte d'un contexte plus ancien est toujours ≥ celui d'un plus récent à toute position partagée.

Cas 2 — Groupe de longueur fixe, externe non borné

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

Chaque enfant a min == max, si bien que le corps est sémantiquement équivalent à sa forme déroulée {1,1} — (A B{2})+ se comporte comme (A B B)+. Chaque itération consomme un nombre fixe de lignes ; la domination des comptes tient encore.

Cas 3 — Groupe dont le corps commence par une variable non bornée

(A+ B)+

La variable non bornée de tête est elle-même absorbable (Cas 1) et protège les contextes plus anciens. L'absorption s'arrête dès que l'état dépasse A — le reste du corps n'a aucune garantie de monotonicité, les drapeaux ne sont donc posés que sur A.

Les cas structurels non couverts par ces trois formes sont tout aussi instructifs. A B+ ne peut pas être absorbé par la règle actuelle parce que le A de tête consomme une ligne avant que la partie non bornée ne commence, si bien que des contextes démarrant à une ligne d'écart se trouvent à des positions différentes à l'intérieur du corps non borné. (Une extension de suivi « PREFIX absorption » qui gère les préfixes de longueur fixe via un chemin fantôme a été conçue et est prévue pour un patch séparé.) Les quantificateurs reluctant comme A+? sont exclus par construction : la règle d'absorption suppose la sémantique greedy, où les correspondances plus longues subsument les plus courtes, et la mise en correspondance reluctant inverse cette direction.

Le résultat est une décision par élément plutôt que par motif. Un seul plan de requête peut avoir l'absorption activée pour le A+ de tête de motifs comme (A+ B+ C) ou (A+ B+)+ — ce dernier est simplement le Cas 3 appliqué à son élément de tête — et désactivée pour tout ce qui suit ; le runtime consulte simplement l'attribut comparison-point sur l'élément de l'état courant chaque fois qu'il envisage une passe d'absorption. Une fois qu'un état entre dans une région non absorbable, l'absorption est définitivement désactivée pour cet état — précisément ce que les §2.5 et §2.6 exigent au niveau algorithmique.

3.3 Navigation — l'échange de tuple à un seul slot

Les expressions DEFINE sont des expressions SQL ordinaires évaluées contre une ligne, mais elles peuvent inclure PREV, NEXT, FIRST ou LAST — des références qui pointent vers des lignes différentes. Les lignes elles-mêmes sont déjà mises en tampon dans le tuplestore de la fenêtre ; ce que l'exécuteur doit encore gérer est le slot de tuple à partir duquel la machinerie d'expressions SQL lit, puisque les références de colonnes à l'intérieur de l'expression sont liées à un slot au moment de la planification. L'implémentation réutilise un seul slot de navigation pour chaque appel de navigation : le slot est échangé avant d'évaluer l'expression interne et restauré ensuite, si bien que le reste de la machinerie d'expressions SQL n'y voit que du feu.

Le modèle vu par l'exécuteur est petit : il y a un slot de ligne courante qui contient la ligne contre laquelle l'expression DEFINE est évaluée, et un slot de navigation que le runtime peut temporairement rediriger vers une ligne différente. Autour de tout appel de navigation, le runtime configure le slot de navigation, évalue l'expression interne comme s'il lisait la ligne courante, puis restaure la ligne originale. Pseudo-code :

eval_navigation(call):
  targetPos = compute_target_position(call)
  si targetPos est hors de sa plage valide:
      return NULL

  sauvegarder current_row_slot
  récupérer la ligne à targetPos
    dans current_row_slot
  result = eval_inner_expression()
  restaurer current_row_slot
  return result

L'astuce est qu'il y a exactement un slot à sauvegarder et restaurer. L'expression interne — quelle qu'elle soit, y compris arithmétique, appels de fonctions, ou autres références de colonnes — s'exécute contre le slot échangé en empruntant le même chemin d'évaluation qu'elle emprunterait pour la ligne courante. Pas d'évaluateur alternatif, pas de slot fantôme, pas de copie de tuple.

La navigation composée est aplatie au moment du parsing afin que l'échange ait toujours lieu une seule fois. PREV(FIRST(price)) est reconnue comme une navigation à deux étapes — « aller à la première ligne correspondante, puis se décaler d'une ligne en arrière » — et stockée comme un seul appel de navigation de type composé. Le runtime calcule la position cible en deux phases mais n'effectue qu'un seul échange de slot pour récupérer la ligne finale :

compute_target_position(call):

  # relatif à la ligne courante
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # relatif au match
  FIRST(n):
      return matchStart + n
  LAST(n):
      return lastMatchedRow − n

  # composé : match-rel, puis pas
  PREV(FIRST(n), m):
      return (matchStart + n) − m
  NEXT(FIRST(n), m):
      return (matchStart + n) + m
  PREV(LAST(n), m):
      return (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      return (lastMatchedRow − n) + m

  valider contre la plage appropriée
  (plage du match pour FIRST/LAST interne,
   plage de partition pour le pas externe)

Un cache de positions court-circuite la lecture du tuplestore quand plusieurs appels de navigation dans le même DEFINE ciblent la même ligne — fréquent dans des expressions comme price > PREV(price) AND volume > PREV(volume) où les deux appels résolvent vers la ligne précédente. Le cache ne stocke que la « dernière position lue », et l'échange lui-même reste une opération unique.

La classification des appels de navigation est la contribution du planner à la décision d'absorption. Le planner parcourt chaque expression DEFINE et trie chaque variable dans l'un de deux compartiments, selon que tous les contextes calculeront le même booléen à la même ligne, ou que chaque contexte calculera le sien. Le compartiment détermine deux choses au runtime : à quelle fréquence la variable est évaluée (une fois en partagé, ou une fois par contexte affecté — §3.5 Phase 1), et si l'état environnant est éligible à l'absorption de contexte (§2.5 vs §2.6).

La classification est effectuée à la planification et stockée à côté de chaque variable DEFINE, si bien que le runtime ne passe aucun temps à décider — il lit simplement le compartiment de chaque variable au fur et à mesure qu'il traite une ligne.

Budget de rétention

La navigation atteint des lignes que la machinerie de fonctions de fenêtrage a par ailleurs déjà fait défiler. Pour garder ces lignes disponibles, l'exécuteur est construit sur un tuplestore qui retient une fenêtre glissante de lignes récentes ; la question est de savoir quelle largeur cette fenêtre doit avoir. Le patch décide à la compilation, à partir de deux décalages complémentaires :

Budget de lookback

Jusqu'où en arrière de la ligne courante un appel DEFINE pourrait atteindre.

Contributeurs : PREV, LAST avec décalage, PREV(LAST(...)), NEXT(LAST(...))

Budget de lookahead depuis le début

Jusqu'où en avant (ou en arrière, lorsque négatif) du début de correspondance du plus ancien contexte vivant un appel DEFINE pourrait atteindre.

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

Au runtime, la marque de coupe du tuplestore est positionnée à la première (la plus précoce) de deux positions — la ligne courante moins le budget de lookback, et le début de correspondance du plus ancien contexte vivant plus le budget de lookahead. Tout ce qui est avant cette marque ne peut être atteint par aucun appel de navigation dans aucun contexte vivant, et le tuplestore est libre de l'écarter. Les deux compteurs Nav Mark que rapporte EXPLAIN (§3.7) — Lookback et Lookahead — sont les pics mesurés des deux budgets, la profondeur maximale que l'exécuteur a dû atteindre dans l'une ou l'autre direction au cours de la requête.

3.4 Frontières de correspondance — SKIP, INITIAL et frame bornée

Une correspondance réussie est enregistrée comme un petit ensemble de valeurs : un drapeau de validité, un drapeau succès/échec, la ligne où la correspondance commence, et le nombre de lignes qu'elle a consommées. Lorsque le drapeau de validité est posé, les requêtes ultérieures à l'exécuteur — « cette ligne est-elle à l'intérieur d'une correspondance ? » — peuvent répondre en O(1) en inspectant cet ensemble. Une longueur de zéro est un vrai résultat, non une erreur : elle représente un motif qui a correspondu sans consommer aucune ligne, ce que l'exécuteur doit distinguer de « aucune correspondance n'a encore été tentée à cette position ».

La clause AFTER MATCH SKIP décide où commence la prochaine tentative de correspondance. AFTER MATCH SKIP PAST LAST ROW se déplace à la ligne après la fin de la correspondance, produisant la sortie sans chevauchement que veulent la plupart des requêtes et permettant l'optimisation par absorption.

AFTER MATCH SKIP TO NEXT ROW ne se déplace qu'à la ligne après le début de la correspondance, autorisant des correspondances qui se chevauchent ; le planner désactive donc l'absorption pour tout le plan de requête lorsque ce mode est en vigueur.

Les deux cibles de skip que le standard définit également — AFTER MATCH SKIP TO FIRST var et AFTER MATCH SKIP TO LAST var — dépendent de l'historique par correspondance que ce patch ne conserve pas. Elles ne sont pas présentes du tout dans la grammaire, donc le parser lève une erreur de syntaxe générique si l'une ou l'autre est fournie.

Il en va de même pour SEEK, l'alternative de la spec à INITIAL. Sous SEEK, une tentative de correspondance commençant à la ligne R peut réussir à n'importe quelle ligne de R à la fin de la frame, et pas seulement à R elle-même. Le patch n'implémente que INITIAL : chaque correspondance potentielle est ancrée à une ligne précise. Le parser lève une erreur si SEEK est demandé. Les frames bornées reçoivent leur propre traitement — lorsque l'utilisateur écrit ROWS BETWEEN CURRENT ROW AND N FOLLOWING plutôt que UNBOUNDED FOLLOWING, l'exécuteur court-circuite tout contexte dont la correspondance a atteint la borne en forçant un échec, et l'absorption est désactivée parce que la borne brise l'hypothèse de monotonicité sur laquelle repose l'absorption.

3.5 Le moteur par ligne en trois phases

Le pilote par ligne de l'exécuteur est invoqué par la machinerie environnante de fonctions de fenêtrage chaque fois qu'elle a besoin de savoir si une ligne donnée appartient à une frame correspondante. Le pilote trouve ou crée le contexte pour la position de départ courante, évalue chaque prédicat DEFINE une fois contre la ligne courante pour produire un tableau booléen par variable, puis fait avancer la NFA d'une ligne. L'étape d'avancement elle-même comprend trois phases dans un ordre fixe — Match, Absorb, Advance — englobées par la même boucle externe :

processRow(currentPos):

  # Phase 1 — MATCH (convergence)
  pour chaque contexte:
      si contexte dépasse le frame borné:
          forcer mismatch (finaliser tôt)
          continue
      si matchStartRow diffère de
         la position d'évaluation partagée:
          réévaluer les variables DEFINE
          dépendantes du match-start (§3.3)
      match(context, varMatched)

  # Phase 2 — ABSORB
  si pattern est absorbable:
      rafraîchir les flags de chaque contexte
      absorb_contexts()

  # Phase 3 — ADVANCE (divergence)
  pour chaque contexte:
      advance(context, currentPos)

L'ordre n'est pas un choix stylistique. Match doit s'exécuter en premier parce que l'absorption compare des comptes post-match ; exécuter Absorb avant Match comparerait des états sur le point de mourir. Advance doit s'exécuter en dernier parce que c'est la seule phase qui crée de nouveaux états — elle étend chaque état survivant via des transitions epsilon jusqu'à ce que chacun atteigne une variable en attente de la prochaine ligne. Exécuter Absorb après Advance reviendrait à comparer des successeurs divergés, ratant le moment où les états sont le plus proprement comparables.

Phase 1 — Match

Match est une phase de « convergence » : les états soit survivent avec un compte incrémenté, soit meurent. Un point subtil est que, pour les variables situées dans une région absorbable, Match effectue aussi un peu de progression vers l'avant, afin qu'Absorb puisse comparer proprement. La condition de cover ne se déclenche qu'au point de comparaison absorbable — le END du groupe non borné — si bien que les états qui viennent de faire correspondre des variables en mi-itération (comme B à l'intérieur de (A B)+) doivent être avancés jusqu'à ce point de comparaison pendant Match lui-même ; sinon Absorb ne trouve rien d'éligible à comparer et l'optimisation ne s'engage jamais.

match(context, varMatched):
  pour chaque état dans contexte:
      elem = pattern[state.elemIdx]
      si elem n'est pas une variable:
          continue   # advance s'en charge

      si non varMatched[elem.varId]:
          abandonner l'état   # branche morte
          continue

      state.counts[elem.depth] += 1

      # Progression inline vers l'avant
      # afin que la phase suivante puisse
      # comparer à l'élément du point de
      # comparaison plutôt qu'au milieu
      # d'une itération.
      si elem est in-region mais pas
         le point de comparaison,
         et a atteint son compte max,
         et elem.next est un group end:

          parcourir la chaîne END:
            incrémenter le compte du groupe externe
            avancer state.elemIdx jusqu'à END
            continuer tant qu'on reste in-region,
              must-exit, et next est END
          (s'arrête au point de comparaison
           ou sur un élément encore loopable)

Le parcours de la chaîne de END est ce qui rend les groupes imbriqués de longueur fixe absorbables. Dans ((A B){2})+, quand B atteint son max (B est {1,1}), le compte du groupe interne doit s'incrémenter ; si ce compte atteint aussi son max — fermant le {2} interne — le compte du groupe externe doit s'incrémenter aussi, et ainsi de suite, jusqu'à ce que l'état atterrisse sur le point d'absorption le plus externe — le END du groupe externe non borné (le +). Faire ce travail dans Match permet à Absorb de comparer face à des contextes qui ont déjà consolidé leurs comptes post-itération.

Phase 2 — Absorb

La passe d'absorb parcourt les contextes du plus récent (queue) au plus ancien (tête). Pour chaque contexte en cours qui est entièrement absorbable, elle scanne en arrière à la recherche d'un contexte en cours plus ancien qui le couvre, et libère le plus récent s'il est trouvé. Parce que les contextes sont conservés dans l'ordre de création et que chaque ligne crée au plus un contexte, « plus récent » et « plus ancien » signifient bien « démarré plus tard » et « démarré plus tôt ».

absorb_contexts():
  pour ctx depuis la queue vers l'arrière:
      si ctx est terminé
         ou a un état non-absorbable:
          passer
      pour older depuis ctx.prev vers l'arrière:
          si older est terminé
             ou n'a pas d'état absorbable:
              passer
          si covered(older, ctx):
              free(ctx)
              enregistrer la longueur d'absorption
              break

covered(older, newer):
  pour chaque état dans newer:
      elem = pattern[state.elemIdx]
      si elem n'est pas le point de comparaison:
          return false
      si aucun état dans older avec:
            même elemIdx
            et isAbsorbable
            et older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

Deux micro-décisions en découlent. La première est que le contrôle de cover rejette immédiatement si un état du contexte plus récent se trouve ailleurs qu'à un point de comparaison — comparer à des points hors jugement ne serait pas une comparaison significative.

La seconde est la paire de drapeaux asymétriques sur chaque contexte : has-absorbable-state répond à « ce contexte pourrait-il en absorber un plus récent ? » et est monotone (il ne peut passer que de vrai à faux à mesure que les états meurent), tandis que all-states-absorbable répond à « ce contexte pourrait-il être absorbé ? » et est dynamique (il revient à vrai quand un état non absorbable est retiré). Les deux drapeaux sont vérifiés en temps constant avant même que le scan de cover ne commence, si bien que l'absorption ne paie son coût plein que sur les contextes ayant une vraie chance d'être absorbés.

Phase 3 — Advance

Advance est la phase de « divergence » : chaque état survivant est étendu via des transitions epsilon jusqu'à ce que chaque branche atteigne soit une variable en attente de la prochaine ligne, soit la sentinelle FIN. L'expansion est en profondeur d'abord, et l'ordre dans lequel les branches frères sont parcourues est ce qui fait que la règle de préférence du standard prend réellement effet — la branche lexicalement première est toujours ajoutée en premier, et l'étape de déduplication à l'insertion d'état rejette silencieusement les ajouts ultérieurs équivalents.

advance(context, currentPos):
  retire tous les états actuels ;
  reconstruit ctx.states depuis zéro
  pour chaque état dans l'ordre lexical:
      efface le bitmap des éléments visités
      advance_state(state)   # DFS

      # Préférence : une fois qu'un DFS
      # atteint FIN, les états restants
      # sont moins préférés et peuvent
      # être abandonnés.
      si FIN atteint et il reste des états:
          libère le reste
          break

advance_state(state):
  parcourt via state.elemIdx,
  récurse à travers:
    branches ALT (dans l'ordre),
    BEGIN (entre dans le groupe ; plus
           chemin optionnel de saut si min = 0),
    END (loop back / exit / fast-forward —
         voir ci-dessous),
    FIN (enregistre matchEndRow,
         sauvegarde matchedState, et élague
         les contextes postérieurs à l'intérieur
         de la plage du candidat — voir ci-dessous),
  s'arrêtant à chaque variable rencontrée:
      ajoute l'état à ctx.states
      (en dédupliquant par elemIdx + counts)

Enregistrer un état ayant atteint FIN fait plus que simplement marquer la correspondance candidate. Sous AFTER MATCH SKIP PAST LAST ROW, la prochaine correspondance rapportable doit commencer strictement au-delà de l'actuelle — si bien qu'au moment où un candidat est enregistré, chaque contexte ultérieur dont la ligne de départ tombe à l'intérieur de la portée du candidat est élagué immédiatement, même si le contexte ayant atteint FIN peut continuer à chercher une correspondance plus longue via un repli greedy.

L'élagage est sûr parce que, peu importe comment cette recherche se termine (une correspondance plus longue remplace le candidat, ou le candidat tient), tous les contextes élagués ont démarré à l'intérieur d'une portée que la prochaine correspondance rapportable devra dépasser, et ne pourraient donc jamais produire leur propre sortie.

C'est l'une des deux étapes d'élagage à FIN — l'autre, décrite plus haut dans cette section au sein d'Advance, écarte les états lexicalement inférieurs à l'intérieur du même contexte.

La logique par élément la plus délicate vit dans le handler de END. Quand le compte d'itération d'un groupe est en dessous de la borne inférieure, le runtime doit reboucler ; quand il est à ou au-dessus de la borne supérieure, il doit sortir ; entre les deux, les deux options sont valides et la greediness du quantificateur décide laquelle essayer en premier :

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

  si count < elem.min:
      reboucler dans le corps
      si elem est empty-loopable :
          # corps nullable, voir §3.2
          cloner aussi un état fast-forward
          qui sort du groupe avec
          count satisfait
          (sauve les matches légitimes
           que le cycle guard tuerait
           sinon)

  elif count >= elem.max:
      réinitialiser les counts à cette profondeur
      sortir via next
      (END→END : incrémenter le count
       du END extérieur)

  else:
      # min <= count < max : fork
      construire un état de sortie
      (counts à cette profondeur réinitialisés)
      si greedy :
          d'abord loop, puis exit
          # préférer plus long
      sinon (reluctant) :
          d'abord exit
          si exit a atteint FIN :
              abandonner le loop
              # préférer plus court
          sinon loop en second

Chaque état ajouté à un contexte passe par un contrôle de déduplication qui compare sa position et ses comptes à la liste d'états existante. Parce qu'Advance traite les branches en ordre DFS, l'état issu de la première branche d'une alternation atterrit en premier — et toute branche ultérieure produisant les mêmes position et comptes est rejetée à l'insertion. C'est exactement ce que demande la règle d'ordre lexical du §2.4, implémentée au fond du runtime sans passe séparée.

Groupes empty-loopable

Un cas subtil que le runtime doit désamorcer est le groupe nullable — un groupe dont le corps peut correspondre à zéro ligne parce que chaque enfant du corps est lui-même optionnel. Les motifs comme (A?)*, (A? B?)+ et (A | B*) ont tous cette propriété : selon les données, le corps peut compléter une itération sans consommer aucune ligne. C'est correct en principe, mais cela crée un véritable danger pour l'expansion epsilon de la NFA. Si le corps produit une correspondance vide, l'élément END reboucle vers BEGIN, le corps produit à nouveau une correspondance vide, BEGIN reboucle vers END, et ainsi de suite. Sans quelque chose pour l'arrêter, le DFS d'Advance ne se terminerait jamais.

Le runtime l'arrête avec un bitmap d'éléments visités (un bit par élément de motif), réinitialisé avant chaque expansion DFS d'un état : dès qu'un élément quelconque est visité une seconde fois au sein de la même expansion, ce chemin est abandonné. Le garde-cycle est inconditionnel et bon marché, mais il a un effet de bord — il peut aussi abandonner des chemins qui devraient atteindre la borne inférieure via des itérations vides légitimes. Prenez (A?){2,3} sans qu'aucun A ne corresponde nulle part dans le flux de lignes :

comportement souhaité :
  iter 1: A? matche zéro ligne
          → END, count = 1 (sous min)
  iter 2: A? matche zéro ligne
          → END, count = 2 (atteint min)
  sortir avec un match de longueur zéro

ce que fait le cycle guard tout seul :
  iter 1: A? sauté → END, count = 1
          → reboucler vers BEGIN
  iter 2: BEGIN déjà visité
          → DFS abandonne
  count n'atteint jamais min
  → le match échoue (incorrect)

La correction est décidée à la compilation et appliquée au runtime. Chaque fois que le planner voit un groupe dont le corps est nullable, il marque l'élément END de ce groupe comme empty-loopable. Au runtime, quand le handler de END est sur le point de reboucler parce que le compte d'itération est encore en dessous de la borne inférieure, le marqueur empty-loop lui indique de cloner un état fast-forward supplémentaire à côté du chemin de loop-back normal :

advance_end (count en dessous de min) :

  chemin primaire :
    reboucler dans le corps
    (garde la porte ouverte pour un
     match réel, non vide à la
     prochaine itération)

  si elem est empty-loopable :
    chemin fast-forward :
      réinitialiser le count de cette profondeur
      sortir du groupe via next,
      en traitant les itérations requises
      restantes comme des matches vides

Les deux chemins jouent des rôles complémentaires. Le loop-back primaire est ce qui rattrape le cas où le corps a encore de vraies correspondances à produire plus tard — par exemple, dans (A?){2,3} suivi de données où A ne correspond que sur des lignes ultérieures, le loop-back est ce qui permet aux deuxième et troisième itérations de trouver des correspondances non vides. Le fast-forward est ce qui rattrape le cas où le corps ne produit jamais rien : il contourne le garde-cycle en sortant entièrement du groupe, déclarant « le reste des itérations requises sont vides », et laisse la correspondance réussir avec un corps de longueur zéro. Les deux états sont ajoutés au contexte ; celui qui s'étend avec succès l'emporte, et le contrôle de déduplication à l'insertion empêche l'un ou l'autre chemin d'engendrer plus que sa part d'états.

Au-delà du garde-cycle, une astuce de démarrage supplémentaire désambigüe les résultats à zéro ligne au tout début d'un contexte. L'étape de création de contexte à chaque ligne de départ potentielle exécute une avance initiale via des transitions epsilon avant qu'aucune ligne ne soit consommée, en utilisant une position une ligne avant le départ réel. Tout chemin qui atteint la sentinelle FIN par les seules transitions epsilon — sans consommer de ligne — produit donc une position de fin inférieure à la position de départ ; cette coordonnée à portée négative, combinée avec le fait que FIN ait été effectivement atteint ou non, encode la différence entre une correspondance vide (correspondance de longueur 0 acceptée) et un départ sans correspondance, sans avoir besoin d'un drapeau séparé.

3.6 Comment l'espace d'états reste borné

La linéarité du runtime n'est pas le résultat d'une optimisation unique. C'est l'effet cumulé d'un ensemble en couches de règles d'élagage, chacune attrapant une cause différente de croissance de l'espace d'états à un point différent du cycle par ligne. Certaines sont décidées à la compilation et simplement consultées au runtime ; d'autres se déclenchent dynamiquement. Certaines tuent des états individuels ; d'autres tuent des contextes entiers. Les sections ci-dessus ont introduit chacune d'elles en contexte ; le tableau ci-dessous les regroupe sur une page.

Prédicat échoué Match

États de variable dont le DEFINE évalue à faux sur la ligne courante — branches mortes.

Avancée inline en chaîne de END Match

Variables ayant atteint leur compte max et qui laisseraient sinon l'état en mi-itération ; avancées à travers les fins de groupes de longueur fixe pour qu'Absorb puisse comparer au bon point.

Absorption de contexte Absorb

Contextes plus récents dont chaque état est couvert par un état d'un contexte plus ancien avec un compte supérieur — voir §2.5 pour la règle conceptuelle, §3.2 pour l'éligibilité à la compilation, §3.5 pour le contrôle par paire.

Déduplication d'états Advance

États atteints via différentes branches DFS qui aboutissent à la même position avec les mêmes comptes — seul le premier (lexicalement le plus précoce) survit ; les équivalents ultérieurs sont silencieusement écartés, ce qui est aussi la manière dont la préférence est imposée (§2.4).

Terminaison anticipée à FIN (au sein d'un contexte) Advance

États encore en attente dans la file DFS quand une branche atteint FIN — par ordre lexical, tous les états restants sont moins préférés et peuvent être écartés immédiatement.

Élagage de correspondance candidate (entre contextes) À FIN

Autres contextes dont la ligne de départ tombe à l'intérieur de la portée de la correspondance candidate — le contexte ayant atteint FIN peut continuer à chercher une correspondance plus longue (repli greedy), mais sous AFTER MATCH SKIP PAST LAST ROW, tout contexte à l'intérieur de la portée du candidat ne peut plus produire de sortie rapportable, indépendamment de l'issue de cette recherche, et est élagué immédiatement.

Garde-cycle Advance

Expansions epsilon qui revisitent le même élément de motif au sein du même DFS — boucleraient sinon indéfiniment dans les groupes nullable.

Fast-forward d'empty-loop Advance

Correspondances légitimes à itération vide que le garde-cycle tuerait dans les groupes nullable — contourne le cycle en sortant du groupe avec les itérations requises restantes déclarées vides.

Coupe de frame bornée Match

Contextes dont la correspondance a atteint la borne supérieure de la frame spécifiée par l'utilisateur — forcés à un échec pour qu'ils ne puissent pas s'étendre au-delà (§3.4).

Lire les entrées par leur badge de phase trace le cycle de vie d'un contexte : l'élagage se déclenche à chaque ligne à travers les trois phases principales (Match, Absorb, Advance), et à nouveau à l'achèvement de la correspondance (À FIN). Lire les descriptions à la place regroupe les règles par ce qu'elles ciblent : branches mortes, contextes redondants, états équivalents, boucles infinies, et débordement au-delà des bornes imposées par l'utilisateur.

Aucune règle seule ne suffirait. Le garde-cycle seul tuerait des correspondances légitimes dans les groupes nullable ; le fast-forward d'empty-loop seul n'arrêterait pas les boucles epsilon infinies ; l'absorption seule consoliderait à l'excès quand DEFINE référence le début de correspondance ; la déduplication seule ne supprimerait pas les contextes redondants, seulement les états redondants. Le runtime reste linéaire dans les cas qui comptent — PATTERN (A+ B+ C+ D) sur 100 000 lignes, le benchmark du panneau ③ du poster — seulement parce que chaque couche attrape ce que les couches au-dessus laissent passer.

3.7 Sortie d'EXPLAIN

EXPLAIN ANALYZE sur une requête avec RPR fait apparaître des statistiques au niveau NFA qui ne sont pas présentes pour les fonctions de fenêtrage ordinaires. Trois groupes de compteurs sont émis aux côtés de l'opérateur de fenêtrage :

NFA States:    peak, total, merged
NFA Contexts:  peak, total, pruned
NFA: matched     (len min/max/avg)
NFA: mismatched  (len min/max/avg)
NFA: absorbed    (len min/max/avg)
NFA: skipped     (len min/max/avg)
Nav Mark Lookback:   | runtime | retain all
Nav Mark Lookahead:  | runtime | retain all
  (only when the query uses FIRST,
   PREV(FIRST(...)), or NEXT(FIRST(...)))

Peak et total sont une instrumentation directe du runtime : combien d'états ont été vivants simultanément, combien ont été créés sur la durée de vie de la requête, et combien ont été fusionnés par déduplication. Les histogrammes de longueur de correspondance séparent quatre résultats — correspondances réussies, tentatives échouées, contextes absorbés, et contextes élagués (skipped) sans avoir été évalués — et les rapporter avec min/max/moy rend les pathologies de performance visibles d'un coup d'œil : un run sain montre la plupart des contextes comme matched ou absorbed, avec des longueurs mismatched petites.

Les deux compteurs Nav Mark rapportent le budget de rétention du tuplestore que le §3.3 dérive à la compilation. Lookback est la portée maximale en arrière à travers PREV, LAST avec décalage, et les formes composées avec LAST interne ; Lookahead est la portée maximale en avant (ou en arrière, quand négative) mesurée depuis le début de correspondance du plus ancien contexte vivant, contribuée par FIRST et les formes composées avec FIRST interne.

Chaque compteur s'imprime comme un entier fixe quand le décalage est une constante, « runtime » quand le décalage est une expression non constante qui doit être évaluée à chaque appel, et « retain all » quand le runtime a besoin d'un budget non borné. Lookahead n'est émis que lorsque la requête utilise effectivement une navigation relative au début de correspondance.

Ensemble, ces compteurs permettent de déboguer les performances RPR sans attacher gdb au backend.

Au-delà des compteurs, EXPLAIN reproduit aussi fidèlement les clauses PATTERN et DEFINE originales, y compris les quantificateurs reluctant, la répétition de groupe et l'option AFTER MATCH SKIP. L'implémentation va à un certain effort pour rendre ce round-trip stable, afin que pg_dump et pg_upgrade puissent préserver les objets RPR sans dérive sémantique — la suite de régression rpr_explain le vérifie cas par cas (voir §4).

§4. Tests — Carte de couverture

Le patch est livré avec cinq suites de régression qui ensemble exercent chaque couche décrite au §3 — environ 13 000 lignes de SQL, chaque suite focalisée sur une préoccupation différente. La séparation est délibérée : garder les préoccupations du parser, la justesse runtime, les interactions du planner et la mise en forme de sortie dans des fichiers séparés rend les échecs plus faciles à localiser, et empêche qu'un changement sans rapport dans une couche n'invalide accidentellement les tests d'une autre. Les cinq suites sont :

rpr

Sémantique de requête de bout en bout — scénarios de fenêtrage réalistes sur des données boursières synthétiques (forme en V, forme en W, hausses consécutives, renversements).

rpr_base

Couche parser — acceptation des mots-clés, formes syntaxiques, quantificateurs, parsing de la navigation, messages d'erreur, et stabilité du round-trip pg_dump/pg_upgrade.

rpr_nfa

Runtime NFA — la boucle à trois phases, l'absorption dans chaque forme absorbable, et les cas limites du cycle de vie des contextes.

rpr_explain

Mise en forme de sortie — statistiques NFA, deparse de motif, échappement d'identifiants, stabilité du format à travers le rechargement.

rpr_integration

Interactions du planner — gardes empêchant les optimisations de fenêtrage sans rapport de corrompre la sémantique RPR.

4.1 rpr — scénarios de bout en bout

La suite de scénarios est la vitrine publique de l'ensemble de tests : elle utilise un jeu de données synthétique de cours boursiers d'environ 1 600 lignes et exécute contre lui des requêtes réalistes — récupération en V, forme en W (double creux), hausses et baisses consécutives, motifs de renversement, partitions multi-symboles. C'est la seule suite où les entrées et sorties se lisent comme des requêtes qu'un utilisateur pourrait réellement écrire ; les autres sont délibérément réductrices, focalisées sur une seule couche à la fois.

Parce que ces requêtes combinent chaque couche (parser, planner, exécuteur, EXPLAIN), un échec unique dans rpr indique rarement où vit le bug. Les quatre suites qui suivent constituent la bissection : un échec dans rpr plus un rpr_base passant exclut le parser ; plus un rpr_nfa passant le réduit à des formes de données spécifiques au scénario ; plus un rpr_integration passant exclut l'interférence du planner ; et toute dérive de deparse apparaît dans rpr_explain.

4.2 rpr_base — la surface du parser

La suite de base est la plus grande, et elle l'est pour une raison : elle est chargée de prouver que chaque morceau de syntaxe légal du §1.2 se parse effectivement, que chaque morceau illégal du §1.3 est rejeté avec une erreur utile, et que chaque forme acceptée survit à un round-trip de sérialisation. L'essentiel est façonné en petits extraits ciblés — un par fonctionnalité syntaxique — plutôt qu'en longues requêtes réalistes, car l'objectif est la couverture plutôt que le réalisme du scénario.

Les tests de sérialisation méritent une attention particulière. Les objets RPR (vues, vues matérialisées, sortie pg_dump) doivent faire un round-trip par la représentation catalogue sans dérive sémantique, y compris des subtilités comme le drapeau reluctant sur un quantificateur ou la forme exacte d'une expression de navigation composée. Un petit ensemble d'objets spécifiques à la sérialisation (les vues rpr_serial_v* et leurs tables sous-jacentes) est intentionnellement laissé en place à la fin du run, afin que l'infrastructure de régression environnante puisse les récupérer et exercer pg_dump et pg_upgrade contre eux. Le reste de l'échafaudage de test est supprimé comme d'habitude. Les bugs attrapés ainsi (comme un drapeau reluctant perdu à travers le deparse et le re-parse) ne se manifestent que lorsque le round-trip est exercé de bout en bout.

4.3 rpr_nfa — le moteur runtime

C'est la suite qui exerce chaque mécanisme décrit aux §3.5 et §3.6. Ses tests suivent un schéma cohérent : une table d'entrée dont les lignes sont des tableaux booléens explicites déclarant quelles variables DEFINE correspondent à chaque ligne, appariée avec un motif qui sonde un comportement runtime précis. L'idiome du tableau booléen découple le test runtime de la machinerie d'évaluation des DEFINE — ce qui est testé est « étant donné que ces variables correspondent ici, la boucle NFA produit-elle la portée de correspondance attendue ? » plutôt que « l'évaluateur d'expression DEFINE calcule-t-il correctement ces booléens ? » L'évaluateur de DEFINE est testé ailleurs (rpr_base pour le parsing, rpr pour le comportement de bout en bout).

Un dispositif de test typique ressemble à ceci — une colonne de tableaux de noms de variables où chaque entrée indique quelles variables DEFINE se déclenchent sur cette ligne, et un motif dont les clauses DEFINE testent ces noms directement :

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

Lire la colonne de tableau verticalement, c'est lire directement le scénario de test. Les lignes 2 et 3 portent les deux noms — A et B s'y déclenchent tous deux, si bien que la NFA a un vrai choix quant au moment de basculer de la branche A à la branche B. La correspondance attendue (A aux lignes 1–3 suivi de B à la ligne 4, sous la préférence greedy du standard) est fixée par ces drapeaux seuls, sans aucune évaluation d'expression de conséquence ici — = ANY n'est que la couche triviale qui expose la colonne tableau à DEFINE, et non ce que le test exerce. Écrire le même scénario avec un prédicat numérique (price > PREV(price) et similaires) emmêlerait le test NFA avec le comportement de l'évaluateur de prédicats ; l'idiome du tableau garde les deux proprement séparés, et un échec ici pointe directement vers la boucle NFA.

La couverture de l'absorption est particulièrement minutieuse, parce que l'absorption est l'optimisation la plus susceptible de produire silencieusement de mauvaises réponses si elle s'engage là où elle ne le devrait pas. Les tests couvrent chaque forme de l'analyse de cas du §3.2 :

• variable non bornée simple (A+) — la fusion canonique N vers 1 ;
• groupes de longueur fixe ((A B)+, (A B{2})+, imbrication à trois niveaux ((A (B C){2}){2})+) ;
• variable non bornée de tête avec un suffixe fixe (A+ B) — seul le A+ de tête porte les drapeaux d'absorption, pas le suffixe ;
• absorption par branche au sein d'une alternation (B+ C | B+ D) ;
• plusieurs variables non bornées (A+ B+) — seule celle de tête est absorbable ;
• quantificateurs reluctant (A+?) — vérifiés exclus de l'absorption ;
• non bornée hors de tête (A B+) — vérifiée exclue.

Au-delà de l'absorption, la suite couvre le cycle de vie des contextes : contextes chevauchants sous AFTER MATCH SKIP TO NEXT ROW, nettoyage des contextes échoués en cours de flux, finalisation de fin de partition pour les contextes incomplets, et contextes rencontrés après qu'une correspondance candidate a déjà été enregistrée dans le contexte de tête. Chacun de ces cas correspond à une règle d'élagage précise du §3.6, et les tests sont écrits pour échouer bruyamment si la règle se déclenche mal (soit en laissant des contextes redondants vivants, soit en tuant un contexte qui aurait dû produire une sortie).

4.4 rpr_explain — stabilité de la sortie

La sortie d'EXPLAIN fait partie du contrat exposé à l'utilisateur — des outils tiers (autocomplétion psql, dashboards de monitoring, scrapeurs de logs) la parsent, et des changements qui paraissent cosmétiques peuvent les casser. La suite rpr_explain vérifie trois choses :

• Les compteurs NFA apparaissent au bon endroit — les statistiques par WindowAgg (peak/total/merged states, peak/total/pruned contexts, histogrammes de longueur pour matched/mismatched/absorbed/skipped, Nav Mark Lookback, et — lorsqu'une navigation relative au début de correspondance est utilisée — Nav Mark Lookahead) apparaissent toutes sous EXPLAIN ANALYZE avec les libellés documentés.
• Les motifs se reparsent correctement — chaque forme de quantificateur, y compris les variantes reluctant et les formes bornées ; chaque alternation ; chaque groupe ; chaque forme d'AFTER MATCH SKIP ; INITIAL ; appels de navigation avec décalages ; navigation composée. Le texte deparsed doit faire un round-trip à travers le parser sans changement.
• L'échappement d'identifiants est correct — les variables de motif et les expressions DEFINE sont émises avec les mêmes règles d'échappement que les identifiants SQL ordinaires, si bien que des noms de variables inhabituels ne cassent pas la sortie de pg_dump.

Comme rpr_base, cette suite laisse intentionnellement ses objets en place à la fin du run, afin que la couverture de pg_dump et pg_upgrade s'étende aussi aux artefacts du côté explain.

4.5 rpr_integration — interactions du planner

Le planner de PostgreSQL a de nombreuses optimisations qui opèrent sur les requêtes de fenêtrage — canonicalisation de frame, descente de run-condition, déduplication de fenêtres identiques, projection de sorties inutilisées, transitions inverses de moving-aggregate — et chacune d'elles a été conçue sans avoir RPR à l'esprit. La plupart sont dangereuses à appliquer quand une fenêtre a une clause PATTERN : la frame fait partie du contrat de correspondance, la sortie matched n'est plus monotone d'aucune manière évidente, et deux fenêtres avec la même spec mais des DEFINE différents produisent des résultats véritablement différents. La suite d'intégration vérifie que chacune de ces optimisations est correctement désactivée ou contournée pour les fenêtres RPR :

Canonicalisation de frame

Le planner réécrit normalement ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING en ROWS UNBOUNDED PRECEDING pour les agrégats monotones. La frame de RPR est la portée de correspondance, pas une fenêtre d'agrégation, et doit rester telle quelle.

Descente de run-condition

Un filtre WHERE monotone sur la sortie d'une fonction de fenêtrage peut normalement être descendu dans l'opérateur de fenêtrage comme condition d'arrêt. Pour RPR, cela terminerait la mise en correspondance prématurément, coupant éventuellement des correspondances en cours d'extension.

Déduplication de fenêtres (RPR vs non-RPR)

Deux fenêtres avec un ORDER BY et une frame identiques seraient normalement fusionnées en une seule. Une fenêtre RPR et une fenêtre non-RPR ne peuvent jamais partager d'état parce que le côté RPR porte des résultats de correspondance.

Déduplication de fenêtres (DEFINE différents)

Deux fenêtres RPR avec le même PATTERN mais des clauses DEFINE différentes produisent des correspondances différentes et doivent rester distinctes, même si leur forme structurelle est identique.

Projection de sorties inutilisées

Même si la requête englobante ne lit jamais la sortie par ligne de la fenêtre, la fenêtre RPR ne peut pas être retirée : les effets de bord du pattern matcher (quelles lignes sont à l'intérieur de quelle correspondance) alimentent des calculs à frame réduite ailleurs dans le plan.

Transitions inverses de moving-aggregate

Les agrégats de fenêtrage avec une fonction de transition inverse peuvent normalement être évalués incrémentalement à mesure que la frame se déplace. La frame réduite de RPR n'est pas une fenêtre glissante ; le chemin par transition inverse produirait de mauvais résultats.

Le schéma de ces tests est le même : chacun fournit une référence non-RPR qui déclenche l'optimisation (et vérifie qu'EXPLAIN la montre appliquée), puis exécute une requête RPR de forme structurellement similaire et vérifie que l'optimisation n'est pas appliquée. Les deux moitiés ensemble prouvent que la garde dans le planner fait un vrai travail, et n'approuve pas chaque requête sans vraie vérification.

Cette suite est aussi la raison pour laquelle le §3.4 est court. Les mécanismes des « frontières de correspondance » — frame réduite, SKIP, INITIAL, coupe de frame bornée — sont testés opérationnellement ailleurs ; ce que rpr_integration vérifie, c'est qu'aucune autre étape de l'optimiseur ne les altère en chemin. Un rpr_integration qui passe est ce qui permet aux autres suites d'avoir confiance que leurs entrées atteignent l'exécuteur sans être altérées.