行模式 识别 深度解析

§1. 标准、子集与待解决的问题

1.1 标准范围

行模式识别由 ISO/IEC 9075-2:2016 引入 SQL，并在配套文档 ISO/IEC 19075-5:2021（第 5 部分，"Row Pattern Recognition"）中加以描述。

标准为同一套底层机制定义了两种表面形式。特性 R010 在 FROM 列表中放置 MATCH_RECOGNIZE 子句以生成派生表；特性 R020 将相同的模式逻辑融入 WINDOW 规范以产生窗口函数输出。两种表面形式共享其大部分语法和全部语义，但它们在功能上是不同的入口点 —— 数据库可以实现其中之一或两者。

此处讨论的补丁系列仅实现了 R020 的子集；表子句形式有意排除在外。

R020 表面虽小但富有表达力。查询通过在窗口规范内添加三个子句来将模式附加到窗口：PATTERN 描述基于命名 模式变量 的正则表达式，DEFINE 提供识别每个变量的布尔谓词，而 AFTER MATCH SKIP 控制后续匹配在分区中的定位方式。

可选的 MEASURES、SUBSET、INITIAL/SEEK 以及辅助函数 CLASSIFIER() 进一步完善了该特性。（标准的 MATCH_NUMBER() 函数仅属于 R010 表面 —— 19075-5 §6.3.3 (6) 明确将其排除在 R020 之外。）

该补丁覆盖了足够的词汇以支持非平凡的查询，但未涉及若干其实现依赖于尚未构建的基础设施的构造。

本节的剩余部分将标准的词汇划分为补丁已经支持的内容和有意留待后续的内容。下面的列表反映了当前补丁系列的状态。

1.2 已实现的特性

已实现的词汇足以表达激发行模式识别动机的典型 V 形、W 形和反转模式。它还覆盖了每一个标准量词 —— 包括所有七种勉强变体 *?、+?、??、{n}?、{n,}?、{,m}?、{n,m}? —— 以及 DEFINE 条件比较相邻行所需的四个导航原语。

PATTERN 子句

在窗口规范内定义行模式。

正则: + * ? |

标准量词和交替。

正则: ( ) 分组

带括号的子模式。

正则: {n} {n,} {,m} {n,m}

有界重复次数。

勉强 *? +? ?? {n}? {n,}? {,m}? {n,m}?

标准定义的所有七种勉强（非贪婪）变体（不参与吸收优化）。

DEFINE 子句

识别每个模式变量的布尔条件。

通用行模式变量

DEFINE 中未限定的列引用（例如裸的 Price）解析为当前行，依据 19075-5 §4.10/§4.16。

PREV、NEXT（带偏移）

到达当前行之前/之后 n 行（默认为 1）；内部参数是在导航到的行上求值的任意值表达式。

FIRST、LAST（带偏移）

到达匹配相对位置的行；FIRST(expr, n) 指向匹配开始之后 n 行的位置，LAST(expr, n) 指向最近匹配行之前 n 行的位置。

复合导航（四种形式）

外层 PREV/NEXT 步骤叠加在内层 FIRST/LAST 之上：PREV(FIRST(expr))、NEXT(FIRST(expr))、PREV(LAST(expr))、NEXT(LAST(expr)) —— 内层和外层步骤都接受各自的偏移量。

INITIAL

模式匹配必须从当前行开始（默认）。

AFTER MATCH SKIP PAST LAST ROW

默认跳跃模式；可参与上下文吸收。

AFTER MATCH SKIP TO NEXT ROW

允许重叠匹配；禁用吸收。

1.3 未实现的特性

尚未实现的特性大致可分为三组。第一组（也是迄今最大的一组）是围绕 MEASURES 的构造家族：MEASURES 子句本身、SUBSET、CLASSIFIER()、模式限定的列引用如 B.price，以及模式限定的导航如 LAST(B.price) 或 PREV(B.price)。

它们与其说是相互独立的缺口，不如说是 同一缺失部件 的不同视角：执行器必须保留一份 每个匹配的历史记录 —— 即对匹配中的每一行，记录它被映射到了哪个模式变量 —— 否则这些构造均无有意义的定义。CLASSIFIER() 从该记录中读出变量名；B.price 读取记录条目为 B 的那些行的 price 列；LAST(B.price) 走过同一组行并选取最后一行；SUBSET U = (A, B) 定义一个对两组进行聚合的虚拟变量；而 MEASURES 正是利用这种聚合来计算 AVG(U.Price) 之类的表达式。

当前的执行器逐行求值 DEFINE 谓词，但不会在任何地方记录结果性的变量分配 —— 之后无可查询。因此构建历史基础设施是整组特性的前提；一旦记录存在，各个特性自然就成为它的小型投影。

第二组涉及替代的跳跃目标：AFTER MATCH SKIP TO label、AFTER MATCH SKIP TO FIRST var，以及 AFTER MATCH SKIP TO LAST var。它们同样依赖于匹配历史，因为执行器必须能够指向最近匹配中某个特定标签的行。

剩余的项是异质的尾巴：SEEK 关键字（INITIAL 的替代）、空模式 ()、排除形式 {- … -}，以及顺序无关的 PERMUTE 运算符。

MEASURES

命名的每匹配输出表达式，例如 MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg；在 R020 中通过 OVER 像窗口函数那样暴露。接受 FINAL / RUNNING 关键字（19075-5 §5.4），在 R020 中两者折叠为同一值，因为度量始终在匹配的最后一行求值（19075-5 §6.9 (3)）。

SUBSET

模式变量的命名并集，例如 SUBSET U = (A, B, C)。可用于任何能够引用模式变量的位置 —— MEASURES、DEFINE 中的模式限定引用、CLASSIFIER(U) —— 而所有这些都需要匹配历史。

CLASSIFIER()

返回某行被匹配为哪个模式变量。在 DEFINE 和 MEASURES 中均有定义（19075-5 §5.9）；任意行处的答案就是该行在匹配历史中记录的变量名。

模式限定的列引用

DEFINE 或 MEASURES 中的裸 B.price —— 表示从被映射为命名变量的那一行所取列的值。

模式限定的导航

将导航限制到被匹配为命名变量的行，例如 LAST(B.price)、FIRST(B.price)、PREV(B.price)、NEXT(B.price)。

SEEK

匹配可在窗口的任何位置开始（与 INITIAL 相对）。

AFTER MATCH SKIP TO label

跳到带标签的行。

AFTER MATCH SKIP TO FIRST var

跳到被匹配为命名变量的第一行。

AFTER MATCH SKIP TO LAST var

跳到被匹配为命名变量的最后一行。

正则: {- -}

排除 —— 从每个匹配的输出中移除被匹配的行。

正则: ()

空模式 —— 匹配空序列。

PERMUTE(...)

对所列变量进行顺序无关匹配。

DEFINE 中的聚合函数

SUM、AVG、COUNT 等聚合在 DEFINE 谓词中不被允许。标准允许它们作为部分匹配上的运行聚合（针对已映射到某个变量的行进行逐行求值），这同样依赖于 MEASURES/CLASSIFIER() 所需的相同每匹配历史。

此处还有四点值得指出，因为它们容易被误认为是缺失的特性。

第一，模式锚点 ^ 和 $ 在 WINDOW 子句中与 RPR 一起使用时不被标准本身允许（19075-5 §6.13："窗口中的行模式匹配不允许使用锚点（^ 和 $）"；其底层定义见 19075-5 §4.14.1）；它们的缺席属于符合性，而非缺口。

第二，MATCH_NUMBER() 同样被标准从 R020 中排除（19075-5 §6.3.3 (6) 与 19075-5 §6.9 (1)）—— 它仅属于 R010 表面，其在此处的缺席同样是符合性，而非缺失的特性。

第三，标准对 R020 施加了一组结构性禁止（19075-5 §6.17）：行模式识别不能嵌套于另一个行模式识别之中；MEASURES 和 DEFINE 不能包含外部引用；MEASURES 或 DEFINE 内的子查询不能引用行模式变量；并且 RPR 不能在递归查询内使用。

第四，MATCH_RECOGNIZE 本身 —— 特性 R010，即同一套机制的表子句表面 —— 不在本补丁的范围内。PostgreSQL 是否最终会加入 R010 将是未来某个补丁系列要回答的问题，而不是衡量本系列的尺度。

§2. 示例 —— 它实际是如何运行的

本节示例逐步构建。我们先从行模式匹配与字符串模式匹配真正不同的概念性原因出发，然后引入让 DEFINE 条件变得有趣的四个导航函数，最后走完三个端到端的轨迹：单一匹配（NFA 移动）、容易情形下的上下文吸收，以及吸收变得不安全的情形。

使导航开销低廉的内部机制 —— 单槽元组交换 —— 属于执行器的设计，将在下一节而非此处讨论。

2.1 为什么行模式不同于文本模式

文本正则表达式匹配字符流，在每个位置上恰好只有一个符号需要考虑。运行时的问题 —— "当前符号是否等于 'A'？" —— 只有一个是/否的答案。回溯自动机利用了这一点：每个字符至多只有一个分支存活，歧义的代价由重新读取输入来承担。

行模式则在根本上不同。行不是单个符号；它是按一 组 布尔谓词（即 DEFINE 条件）求值的列元组。两个谓词可以同时在同一行上为真，标准并未规定它们必须互斥。考虑：

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

一行 price = 150, volume = 2000 同时满足 A 和 B，但不满足 C。模式匹配器不能将其折叠为单一状态 —— 有两个模式变量处于活跃状态，任何命名其中之一的模式元素都可以前进。因此 NFA 必须为分区中的每一行携带 多个同时存在的状态，而非一个。

这一观察驱动了其余的架构。执行状态是一个上下文列表，每个上下文是一个状态列表，在每一行运行时都会询问每个状态："在此处为真的变量下，我能去哪里？"由此产生的分叉正是运行时需要多层裁剪的原因 —— 上下文内的状态去重、跨上下文的吸收，以及 §3.6 中考察的其他规则 —— 否则活跃状态和上下文的数量会随分区增长，模式匹配将变成超线性。

2.2 导航函数

仅引用当前行的 DEFINE 条件是有限的；几乎每个有趣的模式都需要将当前行与其邻居或匹配中之前已接受的行进行比较。标准为此提供了四个导航函数，且补丁全部实现了。

PREV(expr [, n])

当前行之前 n 行的位置（默认 n = 1）。用于"今日与昨日"的比较。

NEXT(expr [, n])

当前行之后 n 行的位置。前向预读；在窗口形式中不常见，因为窗口是单调的。

FIRST(expr [, n])

当前匹配中从起点算起的第 n 个匹配行。"与开启此匹配的那一行比较。"

LAST(expr [, n])

最近第 n 个匹配行。"与最近匹配行比较。"

四个原语可以组合：PREV 和 NEXT 可以包裹一次 FIRST 或 LAST 调用，给出四种复合形式，其语义是"先到达一个匹配相对行，然后从它步进固定距离。"这正是 DEFINE 表达式得以读取（例如）匹配开始之前那一行的方式。

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

从匹配的第 n 行向后退 m 行（默认 m = 1）。"匹配开始之前的值是多少？"

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

从匹配的第 n 行向前进 m 行。在不依赖当前行的情况下进一步深入匹配。

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

从最近第 n 个匹配行向后退 m 行。"与最近匹配之前不久的某行比较。"

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

从最近第 n 个匹配行向前进 m 行。

此处有两点实际要说。首先，导航可以 复合：PREV(FIRST(price)) 读取匹配开始前的那一行，补丁支持这一点。其次，导航对执行器的优化有影响。PREV 和 NEXT 相对于当前行，始终安全；FIRST 与带偏移的 LAST 变体相对于匹配边界，这与上下文吸收相互作用，迫使规划器保留某些原本会被丢弃的上下文。该相互作用背后的机制是 §2.6 的主题。

2.3 实战示例 1 —— NFA 移动

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

The pattern flattens to four elements:

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

For the price series 100, 110, 120, 115, 108, 130:

关键点：在第 3 行，该行同时满足 START（恒为真）与 DOWN，但在第 2 行后唯一存活的状态位于 DOWN 出口分支上，因此只采取 UP → DOWN 转移。§2.1 的多状态本质在每次 UP 匹配处以扇出形式可见（状态可以停留在 UP+ 或 推进到 DOWN+）。贪婪偏好是"先循环再退出"，所以在数据充足时循环分支会进一步扩展匹配；此处循环的 DOWN 在第 5 行死亡（130 ≮ 108），而较早的 FIN 候选（第 0–4 行）—— 在第 4 行 DOWN 退出时产生 —— 被最终确定为匹配。

查询的结果直接源自此轨迹。在 RPR 语义下，窗口函数 first_value(price) 和 last_value(price) 仅在 开启 匹配的那一行求值 —— 匹配中的其他每一行对这些窗口函数都产生 NULL，因为其约简后的框架为空。我们数据的输出因此与海报右上面板所示的表格一致：

第 0 行是匹配的起点，因此其框架覆盖第 0–4 行，窗口函数报告 V 形的开盘价（$100）和最低价（$108）。第 1–4 行虽在匹配内但不是其起点，因此返回 NULL。第 5 行（价格 $130）不在任何匹配内，同样返回 NULL。

2.4 实战示例 2 — 备选与词法顺序

(A | B) 形式给匹配器提供了选项：在任何一行上，两个备选都被独立检查，其中任意数量都可以匹配。这里 §2.1 的多状态性在单一上下文内部可见 — 不是跨上下文（那是 absorption），而是 executor 同步推进的并行分支。

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

设想一行价格上涨且同时超过 $100 — UP 和 HIGH 都为真。每个备选各自产生一个状态：一个走 UP 分支，另一个走 HIGH 分支。两者并行推进，直到 DONE 见分晓。

两个分支在同样的行上产生相同长度的匹配，匹配器面前留下两条候选路径 — 标签分别为 UP, DONE 与 HIGH, DONE。标准用词法顺序（lexical order）来决定胜负：(UP | HIGH) 中先写出的备选获胜，与匹配长度无关。UP 在 HIGH 之前，因此存活路径是 UP, DONE。

词法顺序正是将来 CLASSIFIER() 实现后让它成为良定义函数的依据 — 即便两个谓词都为真，运行时也能告诉用户 "该行被匹配为 UP，而不是 HIGH"。词法顺序是备选的一级规则：词法上更靠前的分支胜过词法上更靠后的分支，即使后者能产生更长的匹配；而词法上靠后（可能更短）的分支只有在所有词法上靠前的分支都先于到达 FIN 之前死亡时才能获胜。贪婪长度是在单个量词内部决出的 — 给定同一备选分支的两次完成，贪婪量词偏好重复次数更多的那一个。

2.5 实战示例 3 — Context absorption（同命运）

展示 absorption 的最简模式是带 DEFINE A AS TRUE 的 PATTERN (A+)。每一行都匹配 A，标准要求匹配器把每一行都当作潜在的匹配起点。朴素地看，N 行分区会产生 N 个上下文。来看一个五行分区（数据无关紧要 — 谓词恒为真）：

内存从 O(n) 缩为 O(1)。在量词为无界时，证明丢弃合法的 absorption 规则很简单：

海报左下面板（"① Context Absorption"）正是把这条规则在五行上做了可视化。

规则中藏着一个微妙但重要的点：丢弃之所以安全，是因为 A AS TRUE 谓词无论哪个上下文来问，在每一行上都算出相同的值。仅引用当前行或相对当前行固定偏移的谓词 — 包括 PREV — 也是如此。下一个示例换用基于 PREV 的谓词，以一周具体的价格来呈现；§2.6 沿用同一周的数据，明示安全 absorption 与不安全 absorption 的对称：

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

考察从周一到周五的一个交易周 $100, $108, $112, $116, $110 — 四次上涨后一次急跌。设 C1 起于周二（RISE 首次匹配的那天：$108 > $100），同时 executor 也在投机性地追踪从周三起的 C2。每行的 RISE 条件把该行价格与上一行价格比较 — 这是分区层面的事实，不是上下文层面的事实 — 所以两个上下文在共享的每一行上都被迫算出相同的布尔值：

一旦谓词开始依赖各自上下文自己的边界，这个故事就崩塌了 — 这正是 §2.6 的主题。

2.6 实战示例 4 — 当 absorption 变得不安全

设想一位分析师想找出股价距离 run 起始日不超过 10 美元的连续交易日 — 一种 consolidation 窗口。模式与 DEFINE 如下：

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

现在该条件把当前行价格与当前 run 开始那天的价格比较。起于不同日子的两个 run 拥有不同的 FIRST(price) 值，因此处于同一模式元素、计数也相同的两个状态不再可互换：它们的未来取决于 absorption 本想丢弃的边界。

沿用 §2.5 完全相同的交易周 — 周一到周五 $100, $108, $112, $116, $110。运行时再次同时保留两个候选 run：C1 起于周一，C2 起于周二（在 STABLE+ 下，每一行都是潜在的 run 起点）。

在 absorption 下，C2 本会在周二被并入 C1 — 合并后的上下文只保留一个天花板，因此 C2 的独立视角（天花板 $118，要到周六才结束的 4 日 run）就无法从内部状态恢复。C2 必须保持存活，因为运行时仍可能需要它作为独立的匹配候选：一旦 C1 的匹配在周三结束，下一次尝试就不会从头开始，而要从仍在推进的 C2 接续。因此，凡 DEFINE 谓词存在匹配起点依赖时，planner 都会先发制人地禁用 absorption。

（如果领跑上下文的匹配确实成功了，那些起于其确认区间内的上下文会 — 在默认的 AFTER MATCH SKIP PAST LAST ROW 下 — 直接被丢弃；保留它们只是为了万一领跑匹配失败时运行时还有可回退的起点。）

海报右下面板（"② Navigation"）的依赖表总结了哪些导航形式会引入匹配起点依赖：

§2.5 和 §2.6 这两个示例可以归并为一条规则。同命运让 absorption 安全：如果同一模式元素上的所有上下文对未来所有谓词都会算出相同答案，那么只保留最老的一个即可。不同命运让 absorption 不安全：当谓词在上下文私有状态上分叉的那一刻 — 这正是 FIRST 和带偏移 LAST 所做的 — 每个存活上下文都代表无法由别的上下文恢复的未来，丢弃任何一个都可能产生错误结果。

planner 在编译期识别这种区分，并按上下文逐一决定是否启用 absorption。这也正是海报面板 ③ 的基准在成功用例和失败用例中都保持线性的原因：当 absorption 安全时，运行时收敛上下文；不安全时，planner 接受多上下文的代价，而不冒错误结果的风险。

海报上的基准数字正是同一算法在大规模上的展开。在成功模式 (A+ B+ C+ D) 下，PostgreSQL 和 Trino 在匹配确定后都按 O(n) 扩展，PostgreSQL 的领先 — 约 16× 到 33× — 大部分来自 JVM 差距。

在失败模式 (A+ B+ C+ E) 下，Trino 没有 absorption，因追逐每一个潜在匹配起点而退化为 O(n²)；在 100,000 行上耗时超过 5 小时，而 PostgreSQL 仅用 92 ms — 约 217,000× 加速。

这个差距并非工程层面的微调 — 正是 §2.5 与 §2.6 中同命运/不同命运区分应用到分区中每一个潜在匹配起点行的结果。

2.7 实战示例 5 — 当 SKIP 禁用 absorption

上一个示例是从数据侧打破 absorption — DEFINE 中的 FIRST 让每个上下文对谓词的求值不同。absorption 也可能在输出侧被打破，控制这一侧的是 AFTER MATCH SKIP 子句。

考察五行全部匹配 A 的情形，模式为 PATTERN (A+)、DEFINE A AS TRUE。在默认 AFTER MATCH SKIP PAST LAST ROW 下，匹配器找出从最早一行开始的最长匹配，然后跳过它；任何在该匹配内部启动的上下文都作为重复被悄悄丢弃 — 正是 absorption 设计要处理的场景。输出是一个匹配，行 0–4，运行时只需要一个存活上下文。

若把 skip 模式改为 AFTER MATCH SKIP TO NEXT ROW，契约就变了：

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

现在每一个潜在的起点位置都必须分别报告，即便匹配相互重叠。对同样的五行，运行时被要求输出五个匹配：行 0–4、1–4、2–4、3–4、4–4。这其中任何一个都不能被 "起点更早的更长匹配" 取代，因为标准说用户想要全部这些。

注意谓词没有变化。A AS TRUE 无论哪个上下文来问，在每一行上都求值相同，因此 §2.5 的同命运条件仍然成立。变化的是输出要求：即便上下文拥有相同的未来，也必须共存，因为它们对应结果中的不同行。所以无论 DEFINE 子句如何，只要 AFTER MATCH SKIP TO NEXT ROW 生效，planner 就禁用 context absorption。

把 §2.6 和 §2.7 并排来看，就构成了 absorption 失败的完整图景：

任意一种条件都足以让受影响的上下文失去 absorption。当两种都不生效 — 默认 AFTER MATCH SKIP PAST LAST ROW 配上仅使用 PREV、NEXT 或不带偏移 LAST 的 DEFINE 条件 — 运行时在每个模式位置上收敛为单一上下文，全程保持线性。

§3. 设计 —— 从解析器到执行器

行模式识别被实现为三个阶段，它们通过定义良好的中间形式相互交接工作。解析器将 SQL 文本转换为模式树和 DEFINE 谓词列表；规划器将该树编译为模式元素的扁平数组，并决定哪些元素可以参与上下文吸收；执行器以三阶段循环逐行对分区运行该数组。每个阶段都有其自身的数据形状，大部分设计巧思位于边界处：一个适合缓存的扁平 NFA、一个复用单个元组槽而非为每次引用物化一个槽的导航模型，以及一条把 O(n²) 内存变成 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

下面的小节按此流水线逐步展开。§3.1 介绍解析器及模式树的形状；§3.2 介绍将树转换为扁平 NFA 的编译过程；§3.3 介绍 DEFINE 谓词用来查看相邻行的导航模型；§3.4 介绍匹配边界处理 —— 即决定匹配从哪里开始和结束的 SKIP、INITIAL 与有界框架规则；§3.5 是三阶段的每行引擎；§3.6 汇总了所有保持状态空间有界的裁剪机制；§3.7 概述实现在 EXPLAIN 输出中暴露的内容。

3.1 解析器 —— 构建模式树

解析器通过窗口规范内是否存在 PATTERN 子句来识别模式识别。其首要任务是框架验证，因为 RPR 施加了普通窗口查询所没有的约束：框架模式必须是 ROWS（不能是 RANGE 或 GROUPS），起始边界必须是 CURRENT ROW，并且禁止 EXCLUDE 选项。这些是符合性检查，而非优化 —— RPR 对框架的理解是 匹配跨度，标准不考虑用匹配行以外的任何东西来填充它。

框架通过验证后，解析器将 PATTERN 子句转换为由四种节点构建的树 —— 变量引用、序列（连接）、交替、分组（带括号的子模式）。每个节点以三个数字携带量词 —— 下界、上界（可能为无穷），以及一个勉强匹配标志：

然后每个 DEFINE 谓词会针对分区的列进行类型检查并强制转换为布尔表达式。其间会发生两件实务上的事情。首先，DEFINE 谓词所引用的每一列都会被注册为查询的输出需求的一部分，因此即便外围查询没有选取这些列，规划器也会将其传递到执行器阶段 —— 否则运行时将无可求值的对象。其次，出现在 PATTERN 中却从未出现在 DEFINE 中的变量隐式为真：它们匹配每一行。

3.2 编译 —— 从 AST 到扁平 NFA

规划器把解析器的树转换为执行器将要运行的数据结构：一个按索引寻址的模式元素扁平数组。编译以六步流水线进行：

compile(astTree):
  1. 优化 AST
  2. 测量大小和深度
  3. 分配元素数组
  4. 从 AST 填充
       （分配 next/jump 指针）
  5. 终结 — 设置 FIN 哨兵
  6. 标记可吸收的元素

选择扁平形式的理由很简单：执行器每个分区都需多次遍历该模式，而连续的索引可寻址数组是最便宜的可遍历数据结构。第 1 步和第 6 步是有趣的 —— 第 1 步因为它决定数组的大小，第 6 步因为它决定 §2.5 中的吸收优化是否会启用。

AST 优化

优化带来双重回报：一次反映在扁平数组的静态元素数量上，再一次反映在运行时处理的每一行上。每条变换都减少了运行时必须枚举的状态空间。优化器依次应用八条重写规则，直至 AST 不再变化：

SEQ 扁平化

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

连续变量合并

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

连续分组合并

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

连续 ALT 合并

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

前缀/后缀吸收

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

ALT 扁平化与去重

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

量词相乘

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

单子节点解包

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

量词相乘是唯一需要安全性检查的变换：优化器仅在三种安全情形下进行折叠 —— 两个量词都无界（(A+)+ → A+）、外层为精确值（(A{2,3}){5} → A{10,15}），或子节点为平凡的 {1,1}（(A){2,5} → A{2,5}）。其他组合可能引入扁平形式会遗漏的间隙 —— 例如 (A{2}){2,3} 仅接受 {4, 6}，但朴素的 A{4,6} 也会接受 5 —— 因此优化器原封不动地保留它们。

元素形状

扁平数组的每个元素代表模式中的一个位置。逻辑上有五种类型：变量引用（唯一消费行的种类）；分组开始和分组结束标记，开启和闭合带括号的子模式；交替标记，作为分支列表的头部；以及位于模式末尾的结束标记。

每个元素还携带一个深度（其分组嵌套层级）、量词（最小和最大重复次数，可能为无穷），以及两个转移指针 —— next（"消费完此元素后去哪里"）和 jump（"跳到何处"，由交替用于串联分支，由分组开始用于在量词允许零时绕过本体，由分组结束用于循环回本体）。

对于 PATTERN ((A B)+)，编译后的数组如下所示：

PATTERN ((A B)+) compiles to:

[0] BEGIN  depth 0  quant 1..∞
    next → 1  jump → 4
    （打开组；当 min = 0 时
     jump 跳到 FIN）

[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
    （关闭组；jump 回环）

[4] FIN    模式完成

模式通过 next 从左到右读取，jump 处理非线性的边。在索引 3 处，END 的 jump 指回索引 1，这正是无界外层量词循环的方式；在索引 0 处，如果分组是可选的，BEGIN 的 jump 将越过 END 跳到索引 4。运行时无需在运行时构造图 —— 它只是在遍历数组时沿这两个指针走。

每元素属性

除了形状之外，每个元素还携带四个逻辑属性，指挥运行时在该位置的行为：

勉强（Reluctant）

反转量词展开的顺序。贪婪量词先尝试"再循环"，再尝试"退出"；勉强量词先尝试"退出"。在 A+? 中由变量携带；在 ((…)+?) 中由分组的 BEGIN 和 END 携带。

可空循环（Empty-loopable）

设置在本体可空的分组结束上（(A?)*、(A? B?)+、(A | B*)）。告知运行时在正常的循环回路之外再加一条快进退出，使循环保护不会在能产生空迭代的分组中扼杀合法匹配。

在可吸收区域内

标记每个位于可吸收区域 内 的元素 —— 由运行时用来跟踪当前状态是否仍处于安全区域。

吸收比较点

标记应运行吸收比较的具体元素。对于简单的 A+，它落在变量上；对于像 (A B)+ 的无界分组，它仅落在分组结束上。

"在区域内"和"比较点"之间的划分很重要，因为吸收仅在迭代闭合的点上才有意义。在 (A B)+ 的本体内部，运行时处于迭代中段，计数尚未达到该轮的最终值；在此处比较意味着比较不可比的值。状态必须到达分组结束后运行时才能裁决。因此第一个属性说"你仍在可吸收区域"；第二个说"你已到达比较点 —— 现在去检查吧。"

可吸收性分析

编译的第 6 步给了 §2.5 的"同命运"规则编译时的见证。该决策是分层的：

isAbsorbable(query):
  若 SKIP 模式 != SKIP PAST LAST ROW
      → return false
  若 frame 结束 != UNBOUNDED FOLLOWING
      → return false
  若任何 DEFINE 依赖 match_start
      → return false
  遍历 AST 并标记
  满足结构性情形的元素

前三个检查是查询级的：它们恰好对应于 §2.7 中的条件（输出侧：SKIP 模式）、有界框架（边界破坏单调性），以及 §2.6（数据侧：DEFINE 中的 FIRST 或带偏移的 LAST）。其中任何一个失败时，分析不设置任何标志，吸收在整个查询范围内被禁用。当全部通过时，AST 遍历允许三种结构形态：

情形 1 —— 简单的无界变量

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

每次迭代恰好为一行。在每个共享位置上，较早上下文的计数始终大于等于较晚上下文的计数。

情形 2 —— 固定长度的分组，外层无界

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

每个子节点都有 min == max，因此本体在语义上等同于其展开的 {1,1} 形式 —— (A B{2})+ 的行为如同 (A B B)+。每次迭代消费固定数量的行；计数支配性仍然成立。

情形 3 —— 本体以无界变量开头的分组

(A+ B)+

领先的无界变量本身可吸收（情形 1）并护住较早的上下文。一旦状态越过 A，吸收就停止 —— 本体的其余部分没有单调性保证，因此仅在 A 上设置标志。

这三种形态 未涵盖 的结构情形同样具有启发性。A B+ 在当前规则下不可吸收，因为领先的 A 在无界部分开始前消费了一行，所以相隔一行启动的上下文在无界本体内部处于不同位置。（一个后续的"PREFIX 吸收"扩展，通过一条影子路径处理固定长度的前缀，已经被设计并计划于另一补丁中提出。）像 A+? 这样的勉强量词从构造上被排除：吸收规则假设贪婪语义，即更长的匹配涵盖更短的匹配，而勉强匹配反转了这个方向。

结果是每元素的决策而非每模式的决策。单个查询计划可以为像 (A+ B+ C) 或 (A+ B+)+ 模式的领先 A+ 启用吸收（后者只是把情形 3 应用于其领先元素），而对其后所有元素禁用吸收；运行时每次考虑吸收阶段时只需查询当前状态所在元素上的比较点属性。一旦某个状态进入不可吸收区域，对该状态的吸收即永久关闭 —— 这正是 §2.5 和 §2.6 在算法层面所要求的。

3.3 导航 —— 单槽元组交换

DEFINE 表达式是针对某一行求值的普通 SQL 表达式，但它们可能包含 PREV、NEXT、FIRST 或 LAST —— 指向 不同行 的引用。行本身已被缓冲在窗口的元组存储中；执行器还需管理的是 SQL 表达式机制读取的元组 槽，因为表达式内的列引用在计划期就被绑定到一个槽。该实现为每个导航调用复用单个导航槽：在求值内部表达式之前换入该槽，之后再恢复，因此 SQL 表达式机制的其余部分对此毫无察觉。

执行器看到的模型很小：有一个 当前行槽，保存 DEFINE 表达式正在求值的那一行；有一个 导航槽，运行时可以将其临时重定向到不同的行。在任何导航调用前后，运行时设置导航槽，仿佛在读取当前行那样求值内部表达式，然后恢复原来的行。伪代码：

eval_navigation(call):
  targetPos = compute_target_position(call)
  若 targetPos 超出其有效范围:
      return NULL

  保存 current_row_slot
  将 targetPos 处的行
    取入 current_row_slot
  result = eval_inner_expression()
  恢复 current_row_slot
  return result

诀窍在于只需保存与恢复恰好一个槽。内部表达式 —— 不管它是什么，包括算术、函数调用或其他列引用 —— 都使用与当前行相同的求值路径在被换入的槽上运行。没有备用求值器，没有影子槽，没有元组复制。

复合导航在解析时被展平，使交换仍只发生一次。PREV(FIRST(price)) 被识别为两步导航 —— "先去匹配的第一行，再向前回退一行" —— 并以一个带复合种类的单一导航调用形式存储。运行时分两阶段计算目标位置，但只执行一次槽交换以获取最终行：

compute_target_position(call):

  # 相对当前行
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # 相对 match
  FIRST(n):
      return matchStart + n
  LAST(n):
      return lastMatchedRow − n

  # 复合: match-rel 后再步进
  PREV(FIRST(n), m):
      return (matchStart + n) − m
  NEXT(FIRST(n), m):
      return (matchStart + n) + m
  PREV(LAST(n), m):
      return (lastMatchedRow − n) − m
  NEXT(LAST(n), m):
      return (lastMatchedRow − n) + m

  对相应范围进行校验
  （内层 FIRST/LAST 用 match 范围，
   外层步进用分区范围）

当同一 DEFINE 中的多个导航调用指向同一行时，位置缓存可以短路元组存储的获取 —— 这在像 price > PREV(price) AND volume > PREV(volume) 这样两个调用都解析到前一行的表达式中很常见。该缓存仅保存"上一次获取的位置"，交换本身仍是单一操作。

导航调用的分类是规划器对吸收决策的贡献。规划器遍历每个 DEFINE 表达式，根据所有上下文是否将在同一行上计算出 相同 的布尔值，或者每个上下文将各自计算 自己 的，将每个变量分入两个桶之一。该桶在运行时决定两件事：变量的求值频率（共享一次，或每个受影响的上下文一次 —— §3.5 阶段 1），以及周围状态是否符合上下文吸收的条件（§2.5 与 §2.6）。

分类在计划期完成并与每个 DEFINE 变量一同存储，因此运行时不花时间做决策 —— 它在处理一行时只需读取每个变量的桶。

保留预算

导航会触及窗口函数机制本来已流过的行。为了让这些行可用，执行器构建在一个保留近期行滑动窗口的元组存储之上；问题是该窗口需要多宽。补丁在编译时根据两个互补的偏移决定：

回溯预算

任何 DEFINE 调用从当前行向后能达到多远。

贡献者： PREV、带偏移的 LAST、PREV(LAST(...))、NEXT(LAST(...))

从起点起的前瞻预算

任何 DEFINE 调用从最老存活上下文的匹配起点向前（或在为负时向后）能达到多远。

贡献者： FIRST、PREV(FIRST(...))、NEXT(FIRST(...))

运行时元组存储的修剪标记被设置为两个位置中较早的那个 —— 当前行减去回溯预算，以及最老存活上下文的匹配起点加上前瞻预算。该标记之前的任何内容都无法被任何存活上下文中的任何导航调用所触及，元组存储可自由地丢弃它们。EXPLAIN 报告的两个 Nav Mark 计数器（§3.7）—— Lookback 和 Lookahead —— 是这两个预算的实测峰值，即整个查询过程中执行器在任一方向上不得不达到的最深位置。

3.4 匹配边界 —— SKIP、INITIAL 与有界框架

一次成功的匹配被记录为一小束值：有效性标志、成功/失败标志、匹配开始的行，以及它消费的行数。当有效性标志被设置后，对执行器的后续查询 —— "这一行是否在某个匹配之内？" —— 可通过检查该束以 O(1) 时间作答。零长度是一个真实的结果，而非错误：它表示一个未消费任何行的匹配，执行器必须将其与"此位置上尚未尝试匹配"区分开。

AFTER MATCH SKIP 子句决定下一次匹配尝试从何处开始。AFTER MATCH SKIP PAST LAST ROW 移到匹配结束之后的那一行，产生大多数查询所期望的非重叠输出，并启用吸收优化。

AFTER MATCH SKIP TO NEXT ROW 仅移到匹配 开始 之后的那一行，允许重叠的匹配；因此当此模式生效时，规划器对整个查询计划禁用吸收。

标准还定义的另两个跳跃目标 —— AFTER MATCH SKIP TO FIRST var 与 AFTER MATCH SKIP TO LAST var —— 依赖于本补丁未保留的每匹配历史。它们根本不在语法中，因此提供任一者时解析器会抛出通用的语法错误。

SEEK（规范中作为 INITIAL 的替代）也是如此。在 SEEK 下，从行 R 开始的匹配尝试可能在从 R 到框架末尾的任何行上成功，而不仅在 R 本身。该补丁仅实现 INITIAL：每个潜在匹配都锚定在特定的行。请求 SEEK 时解析器抛出错误。有界框架有自身的处理 —— 当用户写 ROWS BETWEEN CURRENT ROW AND N FOLLOWING 而非 UNBOUNDED FOLLOWING 时，执行器通过强制不匹配来短路任何已到达边界的上下文，并且禁用吸收，因为该边界破坏了吸收所依赖的单调性假设。

3.5 三阶段每行引擎

每当外围的窗口函数机制需要知道某个给定行是否属于某个已匹配的框架时，执行器的每行驱动程序就被调用。驱动程序为当前起始位置查找或创建上下文，针对当前行对每个 DEFINE 谓词求值一次以产生按变量的布尔数组，然后将 NFA 向前推进一行。前进步骤本身按固定顺序由三个阶段组成 —— Match、Absorb、Advance —— 包裹在同一外层循环中：

processRow(currentPos):

  # 阶段 1 — MATCH (收敛)
  对每个 context:
      若 context 超过有界 frame:
          强制 mismatch（提前结束）
          continue
      若 matchStartRow 不同于
         共享求值位置:
          重新求值 match-start-
          依赖的 DEFINE 变量（§3.3）
      match(context, varMatched)

  # 阶段 2 — ABSORB
  若 pattern 为 absorbable:
      刷新每个 context 的 flags
      absorb_contexts()

  # 阶段 3 — ADVANCE (发散)
  对每个 context:
      advance(context, currentPos)

这一顺序并非风格选择。Match 必须先运行，因为吸收比较的是 匹配后 的计数；在 Match 之前运行 Absorb 会比较即将死亡的状态。Advance 必须最后运行，因为它是唯一创建新状态的阶段 —— 它通过 epsilon 转移扩展每个存活状态，直到每个状态都到达等待下一行的变量。在 Advance 之后运行 Absorb 意味着比较已分叉的后继者，错过状态最清晰可比的时机。

阶段 1 —— Match

Match 是一个"收敛"阶段：状态要么计数递增地存活下来，要么死亡。一个微妙的点是，对于位于可吸收区域内的变量，Match 还会进行少量前向进展，使 Absorb 能够干净地比较。覆盖条件仅在可吸收比较点 —— 即无界分组的 END —— 触发，所以刚刚匹配迭代中段变量（例如 (A B)+ 内的 B）的状态需要在 Match 自身中被走到该比较点；否则 Absorb 会找不到可比较的合适对象，优化便永远不会启动。

match(context, varMatched):
  对 context 中每个 state:
      elem = pattern[state.elemIdx]
      若 elem 不是变量:
          continue   # 由 advance 处理

      若非 varMatched[elem.varId]:
          丢弃 state   # 死分支
          continue

      state.counts[elem.depth] += 1

      # 内联前向推进，使下一阶段
      # 可在比较点元素处进行
      # 比较，而非在迭代中途。
      若 elem 处于 in-region 但
         不是比较点，
         且达到其 max 计数，
         且 elem.next 为 group end:

          沿 END 链行走:
            递增外层组计数
            将 state.elemIdx 推进到 END
            只要仍在 in-region,
              must-exit, 且 next 为 END
          继续
          （在比较点或仍可 loop 的
           元素处停止）

END 链遍历正是嵌套固定长度分组可吸收的原因。在 ((A B){2})+ 中，当 B 达到其最大值（B 为 {1,1}）时，内层分组的计数必须递增；如果该计数也达到其最大值 —— 关闭内层 {2} —— 则外层分组的计数也必须递增，以此类推，直到状态落在最外层的吸收点 —— 即无界外层分组（+）的 END。在 Match 中完成这项工作让 Absorb 能与那些已经整合好其迭代后计数的上下文进行比较。

阶段 2 —— Absorb

吸收阶段从最新（尾部）到最旧（头部）遍历上下文。对每个完全可吸收的进行中上下文，它向后扫描，寻找一个 覆盖 它的较老的进行中上下文，找到时释放较新的那个。由于上下文按创建顺序保留且每行至多创建一个上下文，"较新"和"较老"确实分别对应"较晚启动"和"较早启动"。

absorb_contexts():
  对 ctx 从尾向前:
      若 ctx 已结束
         或存在任何不可吸收的 state:
          跳过
      对 older 从 ctx.prev 向前:
          若 older 已结束
             或无可吸收的 state:
              跳过
          若 covered(older, ctx):
              free(ctx)
              记录吸收长度
              break

covered(older, newer):
  对 newer 中每个 state:
      elem = pattern[state.elemIdx]
      若 elem 不是比较点:
          return false
      若 older 中没有 state 满足:
            相同的 elemIdx
            且 isAbsorbable
            且 older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

由此推出两条微观决策。第一条是：如果较新上下文中的任何状态位于非比较点的位置，覆盖检查就会立即拒绝 —— 在非裁决点处比较不是有意义的比较。

第二条是每个上下文上一对非对称标志：has-absorbable-state 回答"这个上下文能否吸收一个较新的？"且是单调的（仅可随状态死亡而由真→假），而 all-states-absorbable 回答"这个上下文能否被吸收？"且是动态的（在不可吸收状态被移除时会翻回真）。两个标志都在覆盖扫描开始前以常数时间检查，因此吸收只对真正有可能被吸收的上下文付出完整的代价。

阶段 3 —— Advance

Advance 是"发散"阶段：每个存活状态通过 epsilon 转移被扩展，直到每个分支或者到达等待下一行的变量，或者到达 FIN 哨兵。扩展是深度优先的，遍历兄弟分支的顺序正是让标准的偏好规则真正生效的方式 —— 词法上靠前的分支始终先被添加，状态插入时的去重步骤静默地丢弃后续等价的添加。

advance(context, currentPos):
  取出所有当前 state；
  从头重建 ctx.states
  对每个 state 按词法顺序:
      清空已访问元素位图
      advance_state(state)   # DFS

      # 偏好：一旦某次 DFS 到达 FIN，
      # 剩余 state 偏好度较低，
      # 可以丢弃。
      若 FIN 已到达且仍有 state:
          释放其余
          break

advance_state(state):
  沿 state.elemIdx 行走，
  对以下递归进入:
    ALT 分支（按顺序），
    BEGIN (进入组；若 min = 0
           另含可选跳过路径),
    END (loop back / exit / fast-forward —
         见下),
    FIN (记录 matchEndRow,
         保存 matchedState, 并修剪
         此候选范围内的后续 context — 见下),
  在每个遇到的变量处停下:
      将 state 加入 ctx.states
      （按 elemIdx + counts 去重）

记录一个到达 FIN 的状态不仅仅是为候选匹配做书签。在 AFTER MATCH SKIP PAST LAST ROW 下，下一个可报告的匹配必须严格地在当前匹配之后开始 —— 所以一旦候选被记录，每一个起始行落在候选范围内的后续上下文都会被立即裁剪掉，即便命中 FIN 的上下文可能通过贪婪回退继续寻找更长的匹配。

该裁剪是安全的，因为无论该搜索如何结束（更长的匹配替换候选，或候选保留），所有被裁剪的上下文都在下一个可报告匹配必须跳过的范围内启动，因而绝不可能产生自己的输出。

这是 FIN 时的两个裁剪步骤之一 —— 另一个，本节前面作为 Advance 的一部分所述，会在同一上下文内丢弃词法上较劣的状态。

最棘手的每元素逻辑位于 END 处理程序内。当分组的迭代计数低于下界时，运行时必须循环回去；当达到或超过上界时必须退出；处于中间时两种选项都有效，由量词的贪婪性决定先尝试哪一个：

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

  若 count < elem.min:
      循环回到主体
      若 elem 为 empty-loopable:
          # nullable 主体，见 §3.2
          同时克隆一个 fast-forward
          状态，使其退出该组且
          count 已满足
          （拯救合法匹配，
           否则 cycle guard
           会将其杀死）

  否则若 count >= elem.max:
      重置此深度的 counts
      通过 next 退出
      （END→END：递增外层
       END 的 count）

  否则:
      # min <= count < max：分叉
      构建一个退出状态
      （此深度的 counts 已重置）
      若 greedy:
          先 loop，后 exit
          # 偏好更长
      否则 (reluctant):
          先 exit
          若 exit 到达 FIN:
              丢弃 loop
              # 偏好更短
          否则之后再 loop

添加到上下文中的每个状态都会经过去重检查，将其位置和计数与现有状态列表进行比较。由于 Advance 按 DFS 顺序处理分支，任何交替的第一分支产生的状态先落地 —— 而任何后续产生相同位置和计数的分支在插入时被拒绝。这恰好是 §2.4 的词法顺序规则所要求的，在运行时的最底层实现，而无需单独一遍扫描。

可空循环分组

运行时必须解除的一个微妙情形是 可空分组 —— 一个其本体可以匹配零行的分组，因为本体的每个子节点本身都是可选的。像 (A?)*、(A? B?)+ 和 (A | B*) 这样的模式都有此性质：根据数据，本体可以在完全不消费任何行的情况下完成一次迭代。这在原则上没问题，但它给 NFA 的 epsilon 扩展带来了真正的危险。如果本体产生空匹配，END 元素循环回 BEGIN，本体再一次产生空匹配，BEGIN 又循环到 END，依此类推。如果没有东西阻止它，Advance 的 DFS 将永不终止。

运行时用一个已访问元素的位图（每个模式元素一位）来阻止它，该位图在每个状态的 DFS 扩展前被清除：一旦某个元素在同一扩展内被第二次访问，该路径就被放弃。循环保护是无条件的且开销很小，但它有一个副作用 —— 它也可能放弃那些 本应 通过合法空迭代到达下界的路径。考虑行流中 A 在任何地方都不匹配的 (A?){2,3}：

期望行为：
  iter 1: A? 匹配零行
          → END, count = 1 (低于 min)
  iter 2: A? 匹配零行
          → END, count = 2 (满足 min)
  以零长度匹配退出

cycle guard 单独所做的：
  iter 1: A? 被跳过 → END, count = 1
          → 循环回到 BEGIN
  iter 2: BEGIN 已访问
          → DFS 中止
  count 永远到不了 min
  → 匹配失败（错误）

修复方案在编译时决定，在运行时执行。每当规划器看到一个本体可空的分组时，它将该分组的 END 元素标记为 可空循环。在运行时，当 END 处理程序因为迭代计数仍低于下界而即将循环回去时，可空循环标记告诉它在常规循环回退路径之外再克隆一个额外的 快进 状态：

advance_end (count 低于 min)：

  主路径：
    循环回到主体
    （为下一次迭代中
     一次真实、非空的匹配
     保留余地）

  若 elem 为 empty-loopable:
    fast-forward 路径：
      重置此深度的 count
      通过 next 退出该组，
      将剩余所需迭代
      当作空匹配处理

两条路径扮演互补的角色。主循环回退捕获本体之后仍有真实匹配可产出的情形 —— 例如，在 (A?){2,3} 后面跟着仅在更晚行上匹配 A 的数据时，循环回退让第二和第三次迭代得以找到非空匹配。快进捕获本体永不产出任何东西的情形：它通过整体退出分组绕过循环保护，宣告"其余所需的迭代都是空的"，并使匹配以零长度本体获得成功。两个状态都会被加入上下文；谁能成功延伸谁就胜出，插入时的去重检查防止任一路径生成超过其份额的状态。

除了循环保护之外，还有一个启动时的小技巧用于消除上下文最开始处零行结果的歧义。每个潜在起始行的上下文创建步骤会在 任何行被消费之前，从实际起点之前一行的位置出发，进行一次 初始 advance。任何仅通过 epsilon 转移（不消费一行）就到达 FIN 哨兵的路径，因而产生小于起点的结束位置；这个负跨度坐标，加上是否真的到达了 FIN，编码了空匹配（接受长度为 0 的匹配）与未匹配起点之间的差别，无需单独的标志。

3.6 状态空间如何保持有界

运行时的线性并非单一优化的结果。它是一组分层裁剪规则的累积效果，每条规则在每行循环的不同点上捕获不同的状态空间增长成因。有些在编译时决定，仅在运行时被查询；有些在运行时动态触发。有些杀死单个状态；有些杀死整个上下文。前面几节按情境介绍了每条；下面的表格把它们放在一页上。

谓词失败 Match

DEFINE 在当前行求值为假的变量状态 —— 死分支。

内联 END 链推进 Match

已达到最大计数、否则会让状态停留在迭代中段的变量；通过固定长度的分组结束被推进，使吸收可以在正确的点进行比较。

上下文吸收 Absorb

每个状态都被一个具有更高计数的较老上下文状态覆盖的较新上下文 —— 概念性规则参见 §2.5，编译时资格参见 §3.2，按对的检查参见 §3.5。

状态去重 Advance

通过不同 DFS 分支到达相同位置且具有相同计数的状态 —— 只有第一个（词法上最早的）存活；后续等价者被静默丢弃，这也是偏好被强制执行的方式（§2.4）。

FIN 早期终止（上下文内） Advance

当某个分支到达 FIN 时仍在 DFS 队列中待处理的状态 —— 按词法顺序，所有剩余状态都不太被偏好，可以立即丢弃。

候选匹配裁剪（跨上下文） On FIN

其他起始行落在候选匹配范围内的上下文 —— 命中 FIN 的上下文可能仍会继续搜索更长的匹配（贪婪回退），但在 AFTER MATCH SKIP PAST LAST ROW 下，候选范围内的任何上下文无论该搜索如何结束都不再能产生可报告的输出，并被立即裁剪。

循环保护 Advance

在同一 DFS 内重新访问相同模式元素的 epsilon 扩展 —— 否则在可空分组中将永远循环。

空循环快进 Advance

循环保护在可空分组中会扼杀的合法空迭代匹配 —— 通过退出分组并将其余所需迭代声明为空来绕过该循环。

有界框架截断 Match

匹配已到达用户指定框架上界的上下文 —— 被强制不匹配以使其无法越过该上界（§3.4）。

按阶段标识阅读各条目可勾勒出上下文的生命周期：每行通过三个主要阶段（Match、Absorb、Advance）触发裁剪，以及在匹配完成时（On FIN）再次触发。改为按描述阅读，则按所针对的目标对规则进行分组：死分支、冗余上下文、等价状态、无限循环，以及越出用户施加的边界。

任何单条规则单独都不够。循环保护单独会在可空分组中扼杀合法匹配；空循环快进单独无法阻止无限的 epsilon 循环；吸收单独在 DEFINE 引用匹配起点时会过度合并；去重单独只能去除冗余 状态 而非冗余 上下文。运行时在重要情形下保持线性 —— 100,000 行上的 PATTERN (A+ B+ C+ D)，海报面板 ③ 的基准 —— 仅仅是因为每一层都捕获到上面各层遗漏的内容。

3.7 EXPLAIN 输出

带有 RPR 的查询上的 EXPLAIN ANALYZE 会暴露普通窗口函数所没有的 NFA 级统计信息。在窗口算子旁会发出三组计数器：

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

Peak 和 total 是对运行时的直接度量：曾同时存活过多少状态、查询生命周期内创建了多少状态，以及被去重合并掉了多少。匹配长度直方图分离出四种结果 —— 成功匹配、失败的匹配尝试、被吸收的上下文，以及未经求值就被裁剪（跳过）的上下文 —— 并以 min/max/avg 报告它们能让性能病态一目了然：健康运行显示大多数上下文要么是 matched 要么是 absorbed，mismatched 长度很小。

两个 Nav Mark 计数器报告 §3.3 在编译时推导的元组存储保留预算。Lookback 是跨 PREV、带偏移的 LAST 以及内层为 LAST 的复合形式中向后到达的最深位置；Lookahead 是从最老存活上下文匹配起点测量的最深向前（或为负时向后）到达位置，由 FIRST 和内层为 FIRST 的复合形式贡献。

每个计数器在偏移量为常量时打印为固定整数，在偏移量为每次调用都需求值的非常量表达式时打印为"runtime"，在运行时需要无界预算时打印为"retain all"。Lookahead 仅当查询实际使用匹配起点相关的导航时才会发出。

这些计数器加在一起让我们无需将 gdb 附加到后端就能调试 RPR 性能。

除计数器外，EXPLAIN 还忠实地再现原始的 PATTERN 和 DEFINE 子句，包括勉强量词、分组重复，以及 AFTER MATCH SKIP 选项。该实现在使此往返稳定方面下了不少功夫，以便 pg_dump 和 pg_upgrade 能在不发生语义漂移的情况下保留 RPR 对象 —— rpr_explain 下的回归套件逐项进行验证（参见 §4）。

§4. 测试 —— 覆盖地图

该补丁附带五个回归套件，共同练习 §3 描述的每一层 —— 大约 13,000 行 SQL，每个套件专注于一个不同的关注点。这种拆分是有意的：把解析器关注点、运行时正确性、规划器交互和输出格式化保持在独立文件中，使失败更易定位，并防止一层中无关的变更意外地使另一层的测试失效。五个套件是：

rpr

端到端查询语义 —— 在合成股票数据上的真实窗口场景（V 形、W 形、连续上涨、反转）。

rpr_base

解析器层 —— 关键字接受、语法形态、量词、导航解析、错误信息，以及 pg_dump/pg_upgrade 往返稳定性。

rpr_nfa

NFA 运行时 —— 三阶段循环、每种可吸收形态的吸收、以及上下文生命周期的边界情况。

rpr_explain

输出格式化 —— NFA 统计、模式反解析、标识符引用、跨重载的格式稳定性。

rpr_integration

规划器交互 —— 防止无关窗口优化破坏 RPR 语义的守卫。

4.1 rpr —— 端到端场景

场景套件是测试集的公开面孔：它使用约 1,600 行的合成股票价格数据集，并对其运行真实的查询 —— V 形回升、W 形（双底）、连续上涨与下跌、反转模式、多符号分区。它是唯一输入输出读起来像用户可能真正书写的查询的套件；其他套件是有意精简的，每次专注于单一层。

由于这些查询组合了每一层（解析器、规划器、执行器、EXPLAIN），rpr 中的单个失败很少能告诉你 bug 所在。接下来的四个套件就是分而治之：rpr 失败加上 rpr_base 通过可排除解析器；再加上 rpr_nfa 通过则将范围缩窄到特定场景的数据形态；再加上 rpr_integration 通过则可排除规划器干扰；任何反解析漂移会在 rpr_explain 中显现。

4.2 rpr_base —— 解析器表面

base 套件是最大的，且其大有缘由：它负责证明 §1.2 中每条合法语法实际上能被解析、§1.3 中每条非法语法都以有用的错误被拒绝，以及每个被接受的形态都能在序列化往返中存活下来。其主体由小巧聚焦的代码片段构成 —— 每个语法特性一段 —— 而非冗长的真实查询，因为目标是覆盖率而非场景真实性。

序列化测试值得特别关注。RPR 对象（视图、物化视图、pg_dump 输出）必须能在不发生语义漂移的情况下通过目录表示进行往返，包括量词上的勉强标志或复合导航表达式的精确形式等微妙之处。一小组序列化专用对象（rpr_serial_v* 视图及其支持表）在运行结束时被有意 保留，以便周围的回归基础设施能够拾取它们并对其运行 pg_dump 与 pg_upgrade。其余测试脚手架照常被丢弃。以这种方式捕获的 bug（例如勉强标志在反解析和再解析之间丢失）只有在端到端往返时才会浮现。

4.3 rpr_nfa —— 运行时引擎

这是练习 §3.5 与 §3.6 中描述的每个机制的套件。它的测试遵循一致的模式：一张输入表，其每行是显式的布尔数组，声明每一行上哪些 DEFINE 变量匹配，配对一个探测特定运行时行为的模式。布尔数组习惯将运行时测试与 DEFINE 求值机制解耦 —— 所测试的是"给定这些变量在此处匹配，NFA 循环是否产生期望的匹配跨度？"而不是"DEFINE 表达式求值器是否正确地计算了这些布尔值？"DEFINE 求值器在别处测试（解析在 rpr_base，端到端行为在 rpr）。

典型的测试夹具如下 —— 一列由变量名数组组成的列，其中每个条目声明该行上哪些 DEFINE 变量被触发，加上一个模式，其 DEFINE 子句直接对那些名称进行测试：

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

向下读取数组列就是直接阅读测试场景。第 2 行和第 3 行同时携带两个名称 —— A 和 B 都在那里触发，因此 NFA 在何处从 A 腿切换到 B 腿上有真正的选择。期望的匹配（在标准的贪婪偏好下，A 出现在第 1–3 行，B 出现在第 4 行）仅由这些标志确定，此处没有任何有结果性的表达式求值 —— = ANY 只是把数组列暴露给 DEFINE 的平凡层，并不是测试所练习的对象。用数值谓词（如 price > PREV(price) 之类）改写同一场景会把 NFA 测试与谓词求值器的行为纠缠在一起；数组习惯让两者干净地分开，此处的失败直接指向 NFA 循环。

吸收覆盖尤为彻底，因为吸收是最有可能在不该启用时悄无声息地产生错误答案的优化。测试覆盖 §3.2 案例分析中的每一种形态：

• 简单的无界变量（A+）—— 经典的 N 到 1 折叠；
• 固定长度的分组（(A B)+、(A B{2})+、三级嵌套 ((A (B C){2}){2})+）；
• 带有固定后缀的领先无界变量（A+ B）—— 仅领先的 A+ 携带吸收标志，后缀不带；
• 交替内每分支的吸收（B+ C | B+ D）；
• 多个无界变量（A+ B+）—— 仅领先的那个可吸收；
• 勉强量词（A+?）—— 已验证被排除在吸收之外；
• 非领先的无界（A B+）—— 已验证被排除。

除吸收外，该套件还覆盖上下文生命周期：AFTER MATCH SKIP TO NEXT ROW 下的重叠上下文、流中段的失败上下文清理、不完整上下文在分区末尾的最终化，以及在头部上下文中已记录候选匹配后遇到的上下文。其中每一项对应 §3.6 中的一条特定裁剪规则，测试被编写为在规则失误（要么留下冗余上下文存活，要么杀死本应产生输出的上下文）时大声报错。

4.4 rpr_explain —— 输出稳定性

EXPLAIN 输出是面向用户的契约的一部分 —— 第三方工具（psql 自动补全、监控仪表盘、日志抓取器）会解析它，看似仅是表面的修改也可能破坏它们。rpr_explain 套件验证三件事：

• NFA 计数器出现在正确的位置 —— 每个 WindowAgg 的统计信息（peak/total/merged 状态、peak/total/pruned 上下文、matched/mismatched/absorbed/skipped 的长度直方图、Nav Mark Lookback，以及 —— 在使用匹配起点相关导航时 —— Nav Mark Lookahead）都在 EXPLAIN ANALYZE 下以文档化的标签出现。
• 模式正确反解析 —— 每种量词形态，包括勉强变体和有界形式；每种交替；每种分组；每种 AFTER MATCH SKIP 形式；INITIAL；带偏移的导航调用；复合导航。反解析出的文本必须能不变地往返通过解析器。
• 标识符引用正确 —— 模式变量和 DEFINE 表达式以与普通 SQL 标识符相同的引用规则发出，因此不寻常的变量名不会破坏 pg_dump 输出。

与 rpr_base 一样，此套件有意在运行结束时保留其对象，使 pg_dump 与 pg_upgrade 的覆盖也延伸到 explain 侧的产物。

4.5 rpr_integration —— 规划器交互

PostgreSQL 的规划器有许多作用于窗口查询的优化 —— 框架规范化、运行条件下推、相同窗口去重、未使用输出投影、移动聚合的逆向转移 —— 而它们中的每一个在设计时都没有考虑 RPR。它们大多在窗口带有 PATTERN 子句时不安全：框架是匹配契约的一部分；匹配输出在任何明显的意义上都不再单调；规范相同但 DEFINE 不同的两个窗口产生真正不同的结果。集成套件验证每条这样的优化对 RPR 窗口被正确禁用或绕过：

框架规范化

规划器通常会将 ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING 重写为 ROWS UNBOUNDED PRECEDING 以便单调聚合处理。RPR 的框架是匹配跨度，而非聚合窗口，必须原样保留。

运行条件下推

对窗口函数输出的单调 WHERE 过滤通常可作为停止条件下推到窗口算子。对 RPR 而言这会过早地终止模式匹配，可能在匹配延伸的中段切断它。

窗口去重（RPR 与非 RPR）

具有相同 ORDER BY 和框架的两个窗口通常会被合并为一个。RPR 窗口与非 RPR 窗口绝不能共享状态，因为 RPR 一侧携带匹配结果。

窗口去重（不同 DEFINE）

具有相同 PATTERN 但不同 DEFINE 子句的两个 RPR 窗口产生不同的匹配，必须保持区分，即使其结构形态完全相同。

未使用输出投影

即便外围查询从不读取窗口的每行输出，RPR 窗口也不能被移除：模式匹配器的副作用（哪些行属于哪个匹配）会喂给计划中其他位置的约简框架计算。

移动聚合的逆向转移

具有逆向转移函数的窗口聚合通常可在框架移动时增量求值。RPR 的约简框架不是滑动窗口；逆向转移路径会产生错误结果。

这些测试的模式都相同：每个测试提供一个触发该优化的非 RPR 基线（并验证 EXPLAIN 显示其被应用），然后运行结构相似的 RPR 查询，并验证该优化 未 被应用。两半合在一起证明规划器中的守卫是在做实在的工作，而不是在没有真正验证的情况下放行每个查询。

此套件也是 §3.4 较短的原因。"匹配边界"机制 —— 约简框架、SKIP、INITIAL、有界框架截断 —— 在别处接受运行性的测试；rpr_integration 所验证的是没有任何其他优化器阶段在中途篡改它们。rpr_integration 通过让其余套件能够信任它们的输入完整无损地到达执行器。