Row Pattern Recognition Plongée technique
Guide d'ISO/IEC 19075-5 · SQL R020 implémenté sur PostgreSQL — ce qui a été construit, ce qui reste à faire, et comment cela fonctionne réellement.
Survolez le standard, parcourez les exemples détaillés, examinez la conception, puis pilotez un simulateur NFA en direct avec vos propres motifs.
Discussion : fil pgsql-hackers · dernier patch (v55) · commitfest #4460.
Pré-traduit par IA — erreurs possibles.
§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 ont en commun une part considérable de leur syntaxe et de leur sémantique (19075-5 signale en §6.3.3 quelques différences propres à R020), 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 des clauses dans une spécification de fenêtre dont la frame est ROWS BETWEEN CURRENT ROW AND … : 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 la clause optionnelle AFTER MATCH SKIP (par défaut PAST LAST ROW) 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 ; jusqu'à 240 variables de motif distinctes.
- Frame de fenêtre
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGouROWS BETWEEN CURRENT ROW ANDnFOLLOWINGavec n ≥ 1 (19075-5 §6.10.2) ; toute autre frame est rejetée, etEXCLUDE NO OTHERSest la seule exclusion acceptée.- 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.Priceseul) 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 évalué 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. - Noms de navigation
PREV,NEXT,FIRSTetLASTécrits comme appels non qualifiés dansDEFINEdésignent toujours la navigation ; une fonction utilisateur du même nom doit y être qualifiée par son schéma.- Arguments de navigation
- Pour
PREV,NEXT,FIRSTetLAST, l'argument interne doit contenir au moins une référence de colonne et le décalage doit être une constante à l'exécution. - 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 FIRST var et AFTER MATCH SKIP TO [LAST] var (SKIP TO var seul signifie SKIP TO LAST var). Elles dépendent également de l'historique de correspondance, puisque l'exécuteur doit pouvoir pointer sur la ligne mappée à une variable donnée 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 {- … -}, l'opérateur insensible à l'ordre PERMUTE, ainsi que les fonctions d'agrégation et les sous-requêtes dans DEFINE, toutes deux actuellement rejetées (un agrégat qualifié par une variable nécessiterait lui aussi l'historique de correspondance).
- 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 viaOVERà 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 dansDEFINE,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.pricedansDEFINEouMEASURES— 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 quelle ligne, de la ligne courante jusqu'à la fin de la frame de fenêtre complète (par opposition à INITIAL).
- 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
ALL ROWS PER MATCH. Cette option ne s'applique pas aux fenêtres (19075-5 §6.3.3 (4)) ; dans une fenêtre, la syntaxe est donc permise (§6.13) mais n'a aucune sortie sur laquelle agir. - Regex : ()
- Motif vide — correspond à la séquence vide.
- PERMUTE(...)
- Mise en correspondance insensible à l'ordre sur les variables listées. Le mot-clé est reconnu puis rejeté (« PERMUTE is not supported ») ;
permutereste utilisable comme nom de variable de motif. - Fonctions d'agrégation dans DEFINE
- Les agrégats tels que
SUM,AVG,COUNTne sont pas permis dans les prédicatsDEFINE. Le standard les autorise comme agrégats courants (running aggregates) sur la correspondance partielle ; un agrégat qualifié par une variable tel queAVG(B.Price)dépend du même historique par correspondance queMEASURES/CLASSIFIER(), tandis qu'un agrégat non qualifié porte sur toutes les lignes de la correspondance jusqu'ici. - Sous-requêtes dans DEFINE
- Toute sous-requête dans
DEFINEest rejetée. Le standard en permet une qui n'effectue aucune row pattern recognition et ne référence aucune variable de motif ; le patch rejette pour l'instant plus que nécessaire.
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 (le patch va plus loin et rejette toutes les sous-requêtes dans DEFINE, comme indiqué plus haut) ; et RPR ne peut pas être utilisée à l'intérieur d'une requête récursive. Le patch applique la règle des références externes (« cannot use outer query column in DEFINE clause ») et la règle de récursion, cette dernière pour chaque élément d'une clause WITH RECURSIVE. Il rejette également les fonctions volatiles et les références à la ligne entière dans DEFINE.
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 cinq exemples détaillés : une correspondance unique (mouvement de la NFA), l'alternation, l'absorption de contexte dans le cas facile, et deux cas où l'absorption est désactivée.
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 (par défaut n = 1). Anticipation en avant ; peu fréquente sous la forme fenêtre car la fenêtre est monotone.
- FIRST(expr [, n])
- La ligne située n rangs après la première ligne de la correspondance courante (par défaut n = 0, la première ligne elle-même). « Comparer avec la ligne qui a commencé cette correspondance. »
- LAST(expr [, n])
- La ligne située n rangs avant la dernière ligne correspondante (par défaut n = 0). Dans
DEFINE, la dernière ligne correspondante est la ligne courante, si bien queLAST(price)lit la ligne courante.
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 ligne que lit
FIRST(expr, n)(par défaut n = 0, 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 ligne que lit
FIRST(expr, n). Atteint plus loin dans la correspondance sans dépendre de la ligne courante. - PREV(LAST(expr [, n]) [, m])
- Reculer de m rangs depuis la ligne que lit
LAST(expr, n). « Comparer avec une ligne peu avant la dernière ligne correspondante. » - NEXT(LAST(expr [, n]) [, m])
- Avancer de m rangs depuis la ligne que lit
LAST(expr, n).
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 simples sont relatifs à la ligne courante et sont toujours sûrs ; FIRST et les variantes de LAST avec décalage, seuls ou à l'intérieur d'un PREV/NEXT composé, sont relatifs aux frontières de la correspondance, ce qui interagit avec l'absorption de contexte : le planner désactive alors l'absorption pour le motif entier. Le mécanisme de cette interaction est le sujet du §2.6.
2.3 Exemple détaillé 1 — Mouvement de la NFA
SKIP PAST LAST ROW une fois sa correspondance enregistrée.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 :
| Ligne | Prix | Vars vraies | Action |
|---|---|---|---|
| 0 | 100 | START | Nouveau contexte. START correspond et sort immédiatement (max=1) ; l'état avance vers UP+. |
| 1 | 110 | START, UP | UP correspond. L'avancée bifurque : un état boucle sur UP, un autre sort vers DOWN+. |
| 2 | 120 | START, UP | UP correspond dans l'état en boucle et bifurque à nouveau. L'état DOWN issu de la ligne 1 meurt (120 ≮ 110). |
| 3 | 115 | START, DOWN | UP échoue sur l'état en boucle et meurt. L'état DOWN issu de la ligne 2 correspond. L'avancée bifurque : boucle sur DOWN, et sortie vers #FIN — un candidat de correspondance sur les lignes 0–3 est enregistré. |
| 4 | 108 | START, DOWN | DOWN correspond sur l'état en boucle et bifurque à nouveau ; le nouveau candidat FIN sur les lignes 0–4 remplace le plus court. |
| 5 | 130 | START, UP | L'état DOWN en boucle échoue (130 ≮ 108). Faute d'état vivant restant dans ce contexte, le candidat enregistré (lignes 0–4) est finalisé comme la correspondance. La tentative suivante démarre à la ligne 5 ; START correspond, mais la partition se termine avant tout UP. |
Point clé : à la ligne 3, la ligne satisfait à la fois START (toujours vrai) et DOWN, mais START n'importe qu'à un contexte démarrant à la ligne 3 ; dans ce contexte, l'état UP en boucle meurt et seul l'état en attente sur DOWN+ avance. 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 dernier candidat FIN (lignes 0–4) — produit quand DOWN est sorti à la ligne 4, en remplacement du candidat de la ligne 3 — 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 :
| Ligne | Prix | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
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 dans l'ordre du motif, la branche antérieure d'abord.
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. Tous deux avancent ensuite vers DONE, où ils se rejoignent.
| Ligne | Vars vraies | États vivants |
|---|---|---|
| R | UP, HIGH | L'état A (branche UP) et l'état B (branche HIGH) avancent tous deux vers DONE avec les mêmes comptes ; B est un doublon de A et est éliminé |
| R+1 | DONE | L'état A correspond à DONE et atteint #FIN |
Dans les termes du standard, les deux branches produisent une correspondance de même longueur sur les mêmes lignes, ce qui donne 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'exécuteur applique cette règle à la ligne R, et non à FIN : il ajoute d'abord l'état de la branche UP, si bien que nfa_append_state_unique() le conserve et écarte l'état identique de la branche HIGH.
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) :
| Ligne | Contextes naïfs | Avec absorption |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 absorbé |
| 2 | C1[A:3], C2[A:2], C3[A:1] | C1[A:3] |
| 3 | C1[A:4], C2[A:3], C3[A:2], C4[A:1] | C1[A:4] |
| 4 | cinq contextes | C1[A:5] |
Les contextes vivants passent de O(n) à O(1), si bien que le total sur la partition tombe de O(n²) à O(n). 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 :
| Jour | Prix | C1 — début mardi price > PREV(price) | C2 — début mercredi price > PREV(price) |
|---|---|---|---|
| Lun | 100 $ | — | — |
| Mar | 108 $ | 108 $ > 100 $ ✓ (vient de démarrer) | — |
| Mer | 112 $ | 112 $ > 108 $ ✓ | 112 $ > 108 $ ✓ (vient de démarrer) |
| Jeu | 116 $ | 116 $ > 112 $ ✓ | 116 $ > 112 $ ✓ |
| Ven | 110 $ | 110 $ > 116 $ ✗ — finalisation | 110 $ > 116 $ ✗ — finalisation |
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
DEFINE référence FIRST — la règle d'absorption ne tient plus, et le planner désactive l'absorption pour le motif.
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+).
| Jour | Prix | C1 — début lundi FIRST = 100 $ price < 100 $ + 10 | C2 — début mardi FIRST = 108 $ price < 108 $ + 10 |
|---|---|---|---|
| Lun | 100 $ | 100 $ < 110 $ ✓ | — |
| Mar | 108 $ | 108 $ < 110 $ ✓ | 108 $ < 118 $ ✓ (vient de démarrer) |
| Mer | 112 $ | 112 $ < 110 $ ✗ — finalise Lun–Mar | 112 $ < 118 $ ✓ |
| Jeu | 116 $ | — | 116 $ < 118 $ ✓ |
| Ven | 110 $ | — | 110 $ < 118 $ ✓ (toujours en cours) |
Sous absorption, C2 aurait été fusionné dans C1 le mardi — le contexte fusionné ne garde que le plafond de C1 (110 $), donc la vue distincte de C2 (plafond 118 $, une série de quatre jours jusqu'au vendredi) n'est pas couverte par le futur de C1. Cette semaine-là, la sortie ne change justement pas : C1 enregistre Lun–Mar, C2 a démarré à l'intérieur de cette correspondance et est éliminé par SKIP PAST LAST ROW, et la tentative suivante démarre le mercredi avec son propre plafond (122 $) et correspond sur Mer–Ven. En général, toutefois, le résultat DEFINE d'un contexte antérieur ne subsume plus celui d'un contexte postérieur, si bien que la comparaison de comptes sur laquelle repose l'absorption n'est plus valide. 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 ci-dessous étend celui du panneau inférieur droit du poster (« ② Navigation ») avec les formes composées et résume quelles formes de navigation créent une dépendance au début de correspondance :
| Navigation | Dép. début de match | Absorbable ? |
|---|---|---|
| PREV, NEXT | aucune | oui |
| LAST (sans décalage) | aucune | oui |
| LAST avec décalage | contrôle de frontière | non |
| FIRST (toute forme) | directe | non |
| Composée (FIRST interne) | directe | non |
| Composée (LAST interne, sans décalage) | aucune | oui |
| Composée (LAST interne avec décalage) | contrôle de frontière | non |
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 n'est garanti de couvrir, si bien qu'on ne peut plus montrer qu'en jeter un est sûr.
Le planner détecte cette distinction à la compilation et active ou désactive l'absorption pour le motif entier ; lorsqu'elle est désactivée, le runtime paie le coût multi-contextes. Le benchmark du poster dans le panneau ③ n'utilise aucun FIRST, donc l'absorption reste active, ce qui explique pourquoi PostgreSQL reste linéaire à la fois dans les cas de succès et d'échec.
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 à peu près en O(n) dès qu'une correspondance est confirmée, et PostgreSQL mène d'environ 16× à 33× (les chiffres de Trino excluent déjà le démarrage de la JVM).
Sur le motif d'échec (A+ B+ C+ E), Trino, qui semble dépourvu d'absorption, poursuit chaque début de correspondance potentiel et se dégrade même plus vite qu'en O(n²) (environ 56× le temps pour 5× les lignes) ; à 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.
| Ligne | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | début de correspondance ; les lignes 0–4 seront la seule correspondance | la correspondance démarre à la ligne 0 |
| 1 | (à l'intérieur de la correspondance 0) | la correspondance démarre à la ligne 1 — doit être maintenue vivante |
| 2 | (à l'intérieur de la correspondance 0) | la correspondance démarre à la ligne 2 — doit être maintenue vivante |
| 3 | (à l'intérieur de la correspondance 0) | la correspondance démarre à la ligne 3 — doit être maintenue vivante |
| 4 | la correspondance 0 se finalise (lignes 0–4) | cinq correspondances se finalisent : 0–4, 1–4, 2–4, 3–4, 4–4 |
AFTER MATCH SKIP TO NEXT ROW, chaque contexte démarrant tardivement est sa propre ligne de sortie. Deux contextes au même élément de motif ne sont plus redondants — ils sont tous deux des sorties requises, et en éliminer un ferait silencieusement disparaître une correspondance demandée par l'utilisateur.
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 les deux manières dont la sémantique d'une requête exclut l'absorption :
FIRST ou un LAST avec décalage dans DEFINE.AFTER MATCH SKIP TO NEXT ROW.
L'une ou l'autre des conditions suffit à désactiver l'absorption pour le motif entier, de même qu'une frame qui ne se termine pas à UNBOUNDED FOLLOWING. Lorsqu'aucune n'est en vigueur — le AFTER MATCH SKIP PAST LAST ROW par défaut, une fin de frame non bornée, et des conditions DEFINE n'utilisant que PREV, NEXT ou un LAST nu — l'absorption est activée, mais uniquement pour les états situés dans la région absorbable du motif : une variable greedy non bornée en tête telle que A+ ou A*, un groupe de longueur fixe avec un quantificateur greedy non borné tel que (A B)+, un groupe greedy dont le corps commence par l'une de ces formes tel que (A+ B)+ ou (A+ B){2}, ou des branches d'alternation construites à partir de celles-ci ; un groupe reluctant disqualifie tout son sous-arbre. Là où cela tient, comme pour A+ au §2.5, le runtime se réduit à un seul contexte et reste linéaire ; START UP+ DOWN+ du §2.3 n'obtient aucune région absorbable.
§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 un travail 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, la borne de fin doit être UNBOUNDED FOLLOWING ou un décalage FOLLOWING positif (une frame par défaut est donc rejetée elle aussi), et les options EXCLUDE autres que EXCLUDE NO OTHERS 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 :
| Source | Encodage en arbre |
|---|---|
| A | VAR(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) |
Chaque prédicat DEFINE est ensuite vérifié typologiquement contre les colonnes de la partition et coercé en une expression booléenne. Deux conséquences pratiques en découlent. Premièrement, l'analyse sémantique n'ajoute rien à la liste cible de la requête pour DEFINE ; c'est le planner qui marque comme nécessaire chaque colonne référencée par un prédicat DEFINE, comme il le fait pour HAVING, et 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 neuf règles de réécriture en une seule passe ascendante (au sein d'une séquence, la fusion de groupes s'exécute une fois de plus, car des fusions antérieures peuvent rapprocher deux groupes identiques) :
- 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}- Fusion 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 - Normalisation de la reluctance
A{2}?→A{2}(la reluctance est effacée partout où min = max)
La multiplication de quantificateurs ne fusionne que lorsque les comptes atteignables forment un seul intervalle contigu et que la correspondance préférée ne se déplace pas : un externe exact ((A{2,3}){5} → A{10,15}), un enfant de min 0, ou des intervalles d'enfant qui se touchent avec un min d'enfant d'au plus 1 ou un max d'enfant non borné ((A+)+ → A+, (A{1,3}){2,4} → A{2,12}), où un externe de min 0 exige aussi un min d'enfant d'au plus 1 ((A{2,})* reste tel quel, puisque A* accepterait une seule ligne). Un enfant de type groupe dont le quantificateur propre n'est pas exact doit d'abord avoir un corps de longueur fixe, si bien que ((A | B B){1,2}){2} reste intact même sous un externe exact. 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 — ou déplacer la correspondance préférée ((A{2,3}){1,2} préfère trois lignes là où A{2,6} en prend quatre), l'optimiseur les laisse donc intactes. Ce n'est pas la seule réécriture soumise à condition : la fusion de groupes et la fusion de suffixe exigent un corps qui consomme un nombre fixe de lignes, la fusion de préfixe refuse un groupe de min 0, de max fini et au contenu nullable, les nœuds reluctant ne sont ni fusionnés ni multipliés ((A+?)+ reste tel quel), et une réécriture dont la nouvelle borne déborderait est refusée.
Forme d'un élément
Chaque élément du tableau plat représente une position unique dans le motif. Il y a six 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 ; un séparateur de branche qui termine chaque branche ; 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 le marqueur d'alternation et les séparateurs de branche pour chaîner les branches, par group begin pour désigner son propre group end — un groupe dont le quantificateur autorise zéro est contourné via le next de ce END — 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 → 3
(ouvre le groupe ; jump désigne
son propre 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
(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 désigne son END à l'idx 3, et si le groupe était optionnel, le contournement sortirait par le next de ce END vers l'idx 4 sans arriver au END. 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 cinq 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? B?)+,(A | B*)+;(A?)*est d'abord multiplié enA*et ne laisse aucune fin de groupe). Indique au runtime d'ajouter une sortie « fast-forward » à côté du loop-back normal sous le min, afin que le garde-cycle ne tue pas des correspondances légitimes dans les groupes qui peuvent produire des itérations vides. - Empty-preferred
- Posé sur les fins de groupe dont le corps préfère la correspondance vide, comme dans
(A?? B??){2}. Place la sortie fast-forward avant le loop-back sous le min, là où le caractère greedy propre du groupe ne dit rien. - 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 le tableau plat depuis
l'élément 0 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 admet quatre formes structurelles :
- Cas 1 — Variable non bornée simple
-
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.
A+,A*,A{2,∞} - Cas 2 — Groupe de longueur fixe, externe non borné
-
Chaque enfant a
(A B)+,(A B{2})+,((A (B C){2}){2})+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
-
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é, si bien que A reçoit les deux drapeaux, le BEGIN englobant reçoit le drapeau in-region, et B et END n'en reçoivent aucun.
(A+ B)+,(A+ B){2} - Cas 4 — Alternation
-
Chaque branche, atteinte par la chaîne de séparateurs, est jugée indépendamment selon les cas ci-dessus ; le marqueur d'alternation reçoit le drapeau in-region dès qu'une branche se qualifie.
A+ | B+,A+ | C D
Les cas structurels non couverts par ces quatre 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é. 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
si targetPos != currentPos:
récupérer la ligne à targetPos
dans nav_slot
pointer le slot externe sur nav_slot
result = eval_inner_expression()
restaurer current_row_slot
copier le résultat par référence hors de nav_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 ni de slot par référence ; lorsque la cible est la ligne courante, la récupération et l'échange sont entièrement sautés. La récupération copie la ligne cible dans le slot de navigation (sauf si le slot la contient déjà), et l'étape de restauration copie un résultat passé par référence dans la mémoire par tuple afin que la récupération suivante ne puisse pas le libérer.
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 currentPos − 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 (currentPos − n) − m
NEXT(LAST(n), m):
return (currentPos − 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'absorption de contexte est possible tout court (§2.5 vs §2.6) : une seule variable dépendante du début de correspondance la désactive pour le motif entier.
- Aucune navigation
PREV/NEXTuniquementLASTsans décalage- Composé avec
LASTinterne (sans décalage)
LASTavec décalageFIRST(toute forme)- Composé avec
FIRSTinterne - Composé avec
LASTinterne (avec décalage)
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. L'exécuteur la détermine à partir de deux décalages complémentaires, en résolvant chaque décalage une fois par scan (les décalages constants aussi à l'initialisation de l'exécuteur, afin qu'un EXPLAIN simple puisse les afficher) :
- Budget de lookback
- Jusqu'où en arrière de la ligne courante un appel DEFINE pourrait atteindre.
- Budget de lookahead depuis le début
- La portée minimale vers l'avant (vers l'arrière, lorsque négative) depuis le début de correspondance du plus ancien contexte vivant — la ligne la plus précoce dont un appel DEFINE pourrait avoir besoin.
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 lignes Nav Mark que rapporte EXPLAIN (§3.7) — Lookback et Lookahead — sont ces deux budgets, et non des pics mesurés. Chacune n'est affichée que lorsqu'une navigation l'alimente, et apparaît même sans ANALYZE ; un décalage dont la valeur n'est connue qu'à l'exécution (un paramètre de plan générique, par exemple) affiche runtime sous un EXPLAIN simple et sa valeur résolue sous EXPLAIN ANALYZE, et retain all (Lookback) ou infinite (Lookahead) signale un décalage qui déborde.
3.4 Frontières de correspondance — SKIP, INITIAL et frame bornée
Un résultat de correspondance est enregistré sous forme de deux valeurs : la ligne où la correspondance commence, et sa longueur. Un début négatif signifie que la position n'a pas encore été évaluée ; une fois le début 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 cette paire. La longueur encode l'issue : -1 pour une ligne sans correspondance, 0 pour une correspondance vide, et le nombre de lignes pour une correspondance réelle. 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 à la fois d'une ligne sans correspondance et 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 le motif de cette fenêtre 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, puis fait avancer la NFA ligne par ligne — en réinitialisant pour chaque ligne un tableau de correspondance par variable à « non évalué » — jusqu'à ce que ce contexte n'ait plus d'état vivant ou que la partition se termine. Les prédicats DEFINE sont évalués paresseusement : une variable est évaluée la première fois qu'un état la consomme, si bien qu'une variable qu'aucun état vivant ne teste sur cette ligne n'est jamais évaluée. 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 a atteint sa fin de frame:
forcer mismatch (finaliser tôt)
continue
si matchStartRow diffère de
la position d'évaluation partagée:
remettre à non évalué 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)
s'il a enregistré un match et
SKIP PAST LAST ROW:
élaguer les contextes postérieurs
qui démarrent dans le match
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]
assert elem est une variable
# advance ne gare que des variables
si varMatched[elem.varId] est
non évalué:
évaluer son DEFINE maintenant
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
ou détient un match enregistré:
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é) jusqu'à ce que le contexte enregistre une correspondance, ce qui le fige à faux — l'absorber libérerait une correspondance qu'aucun contexte absorbant ne peut reproduire. 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 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, en s'arrêtant
dès que FIN est enregistré),
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 marque
le contexte pour que les contextes
postérieurs dans la plage du candidat
soient élagués — 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'une fois qu'Advance en a terminé avec le contexte qui a enregistré un candidat, chaque contexte ultérieur dont la ligne de départ tombe à l'intérieur de la portée du candidat est élagué sur la même ligne, 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'étape d'élagage à FIN entre contextes. À l'intérieur du contexte, FIN coupe aussi le travail lexicalement inférieur : Advance abandonne les états restants dans la file (décrit plus haut dans cette section), et au sein d'un même DFS, chaque chemin moins préféré — les branches ALT ultérieures, l'autre des chemins de saut et d'entrée de BEGIN, le chemin d'entrée d'une variable reluctant, l'autre des chemins de boucle et de sortie de END — s'arrête une fois qu'une correspondance est enregistrée, si bien qu'une avancée enregistre au plus une correspondance.
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
(fast-forward d'abord si le
corps préfère le vide ; le
second chemin est abandonné
si le premier a atteint FIN)
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
si loop a atteint FIN :
abandonner l'exit
# préférer plus long
sinon exit en second
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? B?)+ et (A | B*)+ ont cette propriété : selon les données, le corps peut compléter une itération sans consommer aucune ligne. (Un unique enfant optionnel comme (A?)* est réécrit en A* à la compilation et ne laisse aucun groupe.) 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 dans le corps (son jump est le premier enfant du groupe), le corps produit à nouveau une correspondance vide, atteint de nouveau END, et ainsi de suite. Sans quelque chose pour l'arrêter, le DFS d'Advance ne se terminerait jamais.
La garde 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. Le runtime tient un bitmap des visités, réinitialisé avant chaque expansion DFS d'un état, dans lequel seuls ces END marqués sont notés — rien d'autre ne peut boucler, car tout autre loop-back a consommé une ligne. Atteindre un END noté signifie que le corps vient de dériver une itération vide, et l'état n'est pas écarté : à la borne inférieure ou au-dessus, il quitte le groupe à cet endroit (une itération vide arrête le quantificateur), et en dessous, l'état passe au loop-back normal, si bien que chaque arrivée vide augmente encore le compte jusqu'à atteindre min. Prenez (A? B?){2,3} sans qu'aucune des variables ne corresponde nulle part dans le flux de lignes :
iter 1: A? B? matchent zéro ligne
→ END, count = 1 (sous min)
END déjà noté (à l'entrée
du groupe), mais sous min :
→ reboucler dans A?
iter 2: A? B? matchent zéro ligne
→ END, count = 2 (atteint min)
END déjà noté, à min :
→ quitter le groupe
sortir avec un match de longueur zéro
Sous la borne inférieure, le marqueur empty-loop indique aussi au handler de END de cloner un état fast-forward supplémentaire à côté du chemin de loop-back normal :
advance_end (count en dessous de min) :
chemin de loop-back :
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 est ce qui rattrape le cas où le corps a encore de vraies correspondances à produire plus tard — par exemple, dans (A? B?){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 sort immédiatement 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. C'est le corps, et non le caractère greedy propre du groupe, qui décide de l'ordre : le fast-forward passe en premier exactement lorsque le corps préfère la correspondance vide (un corps reluctant tel que (A?? B??)), et si le premier chemin atteint FIN, le second est abandonné, si bien qu'un chemin moins préféré ne peut pas remplacer la correspondance préférée. 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é
Garder le runtime borné 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 se trouve sur un point de comparaison et est couvert par un état absorbable d'un contexte plus ancien au même élément avec un compte supérieur ou égal — 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) Advance
- 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é dès qu'Advance en a terminé avec le contexte qui a enregistré le candidat. - Garde-cycle Advance
- Expansions epsilon qui atteignent le END d'un groupe nullable déjà noté au sein du même DFS (noté à l'entrée via BEGIN, ou lors d'une arrivée antérieure) — boucleraient sinon indéfiniment ; l'état quitte le groupe à cet endroit à la borne inférieure ou au-dessus, et continue de boucler en dessous.
- Fast-forward d'empty-loop Advance
- Sous la borne inférieure d'un groupe nullable, un chemin supplémentaire qui sort du groupe avec les itérations requises restantes déclarées vides, ordonné par rapport au loop-back selon la préférence du corps.
- 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). 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 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. Le source documente des cas que les couches n'attrapent pas : la déduplication garde séparés des états qui ne diffèrent que par des comptes au-dessus de min, si bien que (A{2,} B)+ C avec C jamais vrai détient Θ(n²) états au pic et en crée Θ(n³) (37 s sur 320 lignes), et une suite d'alternations entièrement nullable est énumérée chemin par chemin, si bien que (A?|B?){30} prend plus d'une demi-heure.
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. En format texte, elles sont émises aux côtés de l'opérateur de fenêtrage, après la ligne Pattern:, les éventuelles lignes Nav Mark (que EXPLAIN simple affiche aussi) et la ligne Storage: :
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(each only when DEFINE uses navigation
that feeds it)
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)
(second NFA line only when either
count is nonzero; a zero count
prints without its (len ...))
Les formats autres que texte émettent chaque compte comme une propriété distincte. 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 ; pruned compte les contextes qui ont échoué après une seule ligne. Les histogrammes de longueur de correspondance séparent quatre résultats — correspondances réussies, tentatives qui ont échoué après plus d'une ligne (mismatched), contextes absorbés, et contextes libérés par AFTER MATCH SKIP PAST LAST ROW parce qu'ils ont démarré à l'intérieur d'une correspondance enregistrée (skipped) — 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 de DEFINE. Lookback est la portée maximale en arrière depuis la ligne courante à travers PREV, LAST avec tout décalage (y compris le 0 par défaut), et les formes composées avec LAST interne ; Lookahead est la portée minimale vers l'avant (négative lorsqu'elle regarde avant le début de correspondance) 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 connue seulement par scan, et — pour Lookback uniquement — « retain all » quand le décalage déborde ; un Lookahead qui déborde affiche « infinite ». Chaque ligne n'est émise que lorsqu'une navigation dans DEFINE l'alimente, et toutes deux apparaissent aussi sous EXPLAIN simple : les décalages constants sont fixés à l'initialisation de l'exécuteur, tandis qu'un décalage connu seulement à l'exécution (un paramètre de plan générique, par exemple) y affiche « runtime » et son entier résolu sous EXPLAIN ANALYZE.
Ensemble, ces compteurs permettent de déboguer les performances RPR sans attacher gdb au backend.
Au-delà des compteurs, EXPLAIN affiche une ligne Pattern: construite à partir du tableau d'éléments compilé ; elle montre donc le motif après les réécritures de compilation (PATTERN (A A) s'explique en a{2}) et porte les marqueurs d'absorption # (point de comparaison) et ~ (région absorbable) ; DEFINE et l'option AFTER MATCH SKIP ne sont pas affichés. Reproduire les clauses telles qu'écrites, y compris les quantificateurs reluctant, la répétition de groupe et l'option de skip, est le rôle de pg_get_viewdef(), qui 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 22 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
- Intégration de la clause WINDOW — 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), plus la sémantique de navigation et les erreurs de restriction de DEFINE.
- 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 ; plus une couche planner — optimisation de motif, drapeaux d'absorption, repli d'optimisation, intégration au planner.
- 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. Ces scénarios sont les seuls tests dont les entrées et sorties se lisent comme des requêtes qu'un utilisateur pourrait réellement écrire ; le reste du fichier, comme les autres suites, est réducteur — imbrication de PREV/NEXT et erreurs de décalage non constant, règles de référence dans DEFINE, et sémantique des décalages de navigation.
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. Une seconde partie, la couche planner, couvre l'optimisation de motif, l'affichage et l'analyse des drapeaux d'absorption, le repli d'optimisation et l'intégration au planner (sous-requêtes, jointures, opérations ensemblistes, tri et regroupement).
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. Des défauts 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 : des lignes VALUES inline portant un tableau de noms de variables qui déclare quelles variables DEFINE correspondent à chaque ligne, appariées avec un motif qui sonde un comportement runtime précis. L'idiome du tableau 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 leA+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 (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) apparaissent sous
EXPLAIN ANALYZEen texte, JSON et XML avec les libellés documentés, et Nav Mark Lookback et Lookahead apparaissent exactement lorsqu'une navigation dans DEFINE les alimente. - 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 comment chacune de ces optimisations traite les fenêtres RPR — la plupart doivent être désactivées ou contournées :
- Canonicalisation de frame
- Le planner réécrit normalement
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGenROWS UNBOUNDED PRECEDINGpour les fonctions de fenêtrage indépendantes de la frame telles querow_number,ranketntile. 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
WHEREmonotone 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 BYet 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 ou SKIP différents)
- Deux fenêtres RPR avec le même
PATTERNmais des clausesDEFINEdifférentes ou unAFTER MATCH SKIPdifférent produisent des correspondances différentes et doivent rester distinctes, même si leur forme structurelle est identique. - Projection de sorties inutilisées
- Celle-ci a le droit de s'appliquer : lorsque la requête englobante ne lit jamais la sortie de la fenêtre, la fonction de fenêtrage devient NULL et son WindowAgg est supprimé, sans changer le nombre de lignes. Les tests vérifient que les colonnes que lit DEFINE atteignent toujours le WindowAgg lorsqu'il est conservé, et que la fenêtre est conservée lorsque sa valeur est lue.
- 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.
D'autres cas vérifient que l'estimation des coûts tient compte de DEFINE, qu'une sous-requête contenant une fenêtre RPR n'est pas aplatie, que les expressions DEFINE ne fuient pas dans un WindowAgg supérieur, et que LIMIT reste au-dessus du WindowAgg ; un second groupe exécute RPR aux côtés de CTE, jointures, opérations ensemblistes, requêtes préparées, tables partitionnées et constructions similaires. La plupart des cas gardés suivent la même forme : une référence qui déclenche l'optimisation (généralement une requête non-RPR, vérifiée dans EXPLAIN), puis une requête RPR de forme structurellement similaire où l'optimisation n'est pas appliquée — pour le cas de déduplication DEFINE/SKIP, la référence est constituée de deux fenêtres RPR identiques, et le cas des transitions inverses vérifie le contournement avec un agrégat qui journalise plutôt qu'avec EXPLAIN. 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.