行模式 识别 深度解析
PostgreSQL 中 ISO/IEC 19075-5 · SQL R020 的导览之旅 —— 我们构建了什么、还有哪些尚未实现,以及它实际是如何运行的。
浏览标准、走完实战示例、了解设计,然后用您自己的模式驱动一个实时 NFA 模拟器。
讨论:pgsql-hackers 讨论串 · 最新 补丁 (v55) · commitfest #4460。
AI 预翻译 — 可能有误。
§1. 标准、子集与待解决的问题
1.1 标准范围
行模式识别由 ISO/IEC 9075-2:2016 引入 SQL,并在配套文档 ISO/IEC 19075-5:2021(第 5 部分,"Row Pattern Recognition")中加以描述。
标准为同一套底层机制定义了两种表面形式。特性 R010 在 FROM 列表中放置 MATCH_RECOGNIZE 子句以生成派生表;特性 R020 将相同的模式逻辑融入 WINDOW 规范以产生窗口函数输出。两种表面形式在语法和语义上有相当多的共同之处(19075-5 在 §6.3.3 中列出了 R020 特有的若干差异),但它们在功能上是不同的入口点 —— 数据库可以实现其中之一或两者。
此处讨论的补丁系列仅实现了 R020 的子集;表子句形式有意排除在外。
R020 表面虽小但富有表达力。查询通过在框架为 ROWS BETWEEN CURRENT ROW AND … 的窗口规范内添加子句来将模式附加到窗口:PATTERN 描述基于命名 模式变量 的正则表达式,DEFINE 提供识别每个变量的布尔谓词,而可选的 AFTER MATCH SKIP(默认为 PAST LAST ROW)控制后续匹配在分区中的定位方式。
可选的 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 子句
- 在窗口规范内定义行模式;最多 240 个不同的模式变量。
- 窗口框架
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING或ROWS BETWEEN CURRENT ROW ANDnFOLLOWING(其中 n ≥ 1)(19075-5 §6.10.2);任何其他框架都会被拒绝,并且EXCLUDE NO OTHERS是唯一被接受的排除选项。- 正则: + * ? |
- 标准量词和交替。
- 正则: ( ) 分组
- 带括号的子模式。
- 正则: {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))—— 内层和外层步骤都接受各自的偏移量。 - 导航名称
- 在
DEFINE内以未限定调用形式书写的PREV、NEXT、FIRST和LAST始终表示导航;同名的用户函数在那里必须加模式名限定。 - 导航参数
- 对于
PREV、NEXT、FIRST和LAST,内部参数必须包含至少一个列引用,且偏移量必须是运行时常量。 - 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 FIRST var 和 AFTER MATCH SKIP TO [LAST] var(裸的 SKIP TO var 表示 SKIP TO LAST var)。它们同样依赖于匹配历史,因为执行器必须能够指向最近匹配中被映射到给定变量的那一行。
剩余的项是异质的尾巴:SEEK 关键字(INITIAL 的替代)、空模式 ()、排除形式 {- … -}、顺序无关的 PERMUTE 运算符,以及 DEFINE 中的聚合函数和子查询,两者目前都会被拒绝(变量限定的聚合还需要匹配历史)。
- 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 FIRST var
- 跳到被匹配为命名变量的第一行。
- AFTER MATCH SKIP TO [LAST] var
- 跳到被匹配为命名变量的最后一行。
- 正则: {- -}
- 排除 —— 从
ALL ROWS PER MATCH的输出中移除被匹配的行。该选项不适用于窗口(19075-5 §6.3.3 (4)),因此在窗口中该语法是允许的(§6.13),但没有可作用的输出。 - 正则: ()
- 空模式 —— 匹配空序列。
- PERMUTE(...)
- 对所列变量进行顺序无关匹配。该关键字会被识别并拒绝("PERMUTE is not supported");
permute仍可用作模式变量名。 - DEFINE 中的聚合函数
SUM、AVG、COUNT等聚合在DEFINE谓词中不被允许。标准允许它们作为部分匹配上的运行聚合;像AVG(B.Price)这样的变量限定聚合依赖于MEASURES/CLASSIFIER()所需的相同每匹配历史,而未限定的聚合则覆盖迄今为止匹配中的所有行。- DEFINE 中的子查询
DEFINE中的每个子查询都会被拒绝。标准允许不执行行模式识别且不引用任何行模式变量的子查询;补丁目前的拒绝范围过宽。
此处还有四点值得指出,因为它们容易被误认为是缺失的特性。
第一,模式锚点 ^ 和 $ 在 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 内的子查询不能引用行模式变量(补丁走得更远,如上所列,拒绝 DEFINE 中的所有子查询);并且 RPR 不能在递归查询内使用。补丁强制执行外部引用规则("cannot use outer query column in DEFINE clause")和递归规则,后者适用于 WITH RECURSIVE 子句的每个元素。它还拒绝 DEFINE 中的 volatile 函数和整行引用。
第四,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 行的位置(默认 n = 1)。前向预读;在窗口形式中不常见,因为窗口是单调的。
- FIRST(expr [, n])
- 当前匹配首行之后 n 行的位置(默认 n = 0,即首行本身)。"与开启此匹配的那一行比较。"
- LAST(expr [, n])
- 最后一个匹配行之前 n 行的位置(默认 n = 0)。在
DEFINE内,最后一个匹配行就是当前行,因此LAST(price)读取的是当前行。
四个原语可以组合:PREV 和 NEXT 可以包裹一次 FIRST 或 LAST 调用,给出四种复合形式,其语义是"先到达一个匹配相对行,然后从它步进固定距离。"这正是 DEFINE 表达式得以读取(例如)匹配开始之前那一行的方式。
- PREV(FIRST(expr [, n]) [, m])
- 从
FIRST(expr, n)所读取的行向后退 m 行(默认 n = 0、m = 1)。"匹配开始之前的值是多少?" - NEXT(FIRST(expr [, n]) [, m])
- 从
FIRST(expr, n)所读取的行向前进 m 行。在不依赖当前行的情况下进一步深入匹配。 - PREV(LAST(expr [, n]) [, m])
- 从
LAST(expr, n)所读取的行向后退 m 行。"与最近匹配行之前不久的某行比较。" - NEXT(LAST(expr [, n]) [, m])
- 从
LAST(expr, n)所读取的行向前进 m 行。
此处有两点实际要说。首先,导航可以 复合:PREV(FIRST(price)) 读取匹配开始前的那一行,补丁支持这一点。其次,导航对执行器的优化有影响。单纯的 PREV 和 NEXT 相对于当前行,始终安全;FIRST 与带偏移的 LAST 变体,无论单独使用还是位于复合的 PREV/NEXT 之内,都相对于匹配边界,这与上下文吸收相互作用:此时规划器会对整个模式禁用吸收。该相互作用背后的机制是 §2.6 的主题。
2.3 实战示例 1 —— NFA 移动
SKIP PAST LAST ROW 丢弃。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) );
该模式展平为四个元素:
[0] START quant 1..1 next → 1 [1] UP quant 1..∞ next → 2 [2] DOWN quant 1..∞ next → 3 [3] #FIN
对于价格序列 100, 110, 120, 115, 108, 130:
| 行 | 价格 | 为真的变量 | 动作 |
|---|---|---|---|
| 0 | 100 | START | 新上下文。START 匹配并立即退出(max=1);状态推进到 UP+。 |
| 1 | 110 | START, UP | UP 匹配。推进时分叉:一个状态在 UP 处循环,另一个退出到 DOWN+。 |
| 2 | 120 | START, UP | UP 在循环状态上匹配并再次分叉。来自第 1 行的 DOWN 状态死亡(120 ≮ 110)。 |
| 3 | 115 | START, DOWN | UP 在循环状态上失败并死亡。来自第 2 行的 DOWN 状态匹配。推进时分叉:在 DOWN 处循环,以及退出到 #FIN —— 记录一个覆盖第 0–3 行的匹配候选。 |
| 4 | 108 | START, DOWN | DOWN 在循环状态上匹配并再次分叉;覆盖第 0–4 行的新 FIN 候选取代较短的那个。 |
| 5 | 130 | START, UP | 循环的 DOWN 状态失败(130 ≮ 108)。此上下文中已无存活状态,于是记录的候选(第 0–4 行)被最终确定为匹配。下一次尝试从第 5 行开始;START 匹配,但在出现任何 UP 之前分区就结束了。 |
关键点:在第 3 行,该行同时满足 START(恒为真)与 DOWN,但 START 只对从第 3 行开始的上下文才有意义;在此上下文中,循环的 UP 状态死亡,只有在 DOWN+ 处等待的状态推进。§2.1 的多状态本质在每次 UP 匹配处以扇出形式可见(状态可以停留在 UP+ 或 推进到 DOWN+)。贪婪偏好是"先循环再退出",所以在数据充足时循环分支会进一步扩展匹配;此处循环的 DOWN 在第 5 行死亡(130 ≮ 108),而最后的 FIN 候选(第 0–4 行)—— 在第 4 行 DOWN 退出时产生,取代了第 3 行的候选 —— 被最终确定为匹配。
查询的结果直接源自此轨迹。在 RPR 语义下,窗口函数 first_value(price) 和 last_value(price) 仅在 开启 匹配的那一行求值 —— 匹配中的其他每一行对这些窗口函数都产生 NULL,因为其约简后的框架为空。我们数据的输出因此与海报右上面板所示的表格一致:
| 行 | 价格 | start_price | end_price |
|---|---|---|---|
| 0 | 100 | 100 | 108 |
| 1 | 110 | — | — |
| 2 | 120 | — | — |
| 3 | 115 | — | — |
| 4 | 108 | — | — |
| 5 | 130 | — | — |
第 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,在那里汇合。
| 行 | 为真的变量 | 存活状态 |
|---|---|---|
| R | UP, HIGH | 状态 A(UP 分支)和状态 B(HIGH 分支)以相同的计数推进到 DONE;B 是 A 的重复,被丢弃 |
| R+1 | DONE | 状态 A 匹配 DONE 并到达 #FIN |
按标准的说法,两个分支在同样的行上产生相同长度的匹配,形成两条候选路径 — 标签分别为 UP, DONE 与 HIGH, DONE。标准用词法顺序(lexical order)来决定胜负:(UP | HIGH) 中先写出的备选获胜,与匹配长度无关。UP 在 HIGH 之前,因此存活路径是 UP, DONE。executor 在第 R 行而非 FIN 处强制执行这一点:它先加入 UP 分支的状态,因此 nfa_append_state_unique() 保留该状态并丢弃相同的 HIGH 分支状态。
词法顺序正是将来 CLASSIFIER() 实现后让它成为良定义函数的依据 — 即便两个谓词都为真,运行时也能告诉用户 "该行被匹配为 UP,而不是 HIGH"。词法顺序是备选的一级规则:词法上更靠前的分支胜过词法上更靠后的分支,即使后者能产生更长的匹配;而词法上靠后(可能更短)的分支只有在所有词法上靠前的分支都先于到达 FIN 之前死亡时才能获胜。贪婪长度是在单个量词内部决出的 — 给定同一备选分支的两次完成,贪婪量词偏好重复次数更多的那一个。
2.5 实战示例 3 — Context absorption(同命运)
展示 absorption 的最简模式是带 DEFINE A AS TRUE 的 PATTERN (A+)。每一行都匹配 A,标准要求匹配器把每一行都当作潜在的匹配起点。朴素地看,N 行分区会产生 N 个上下文。来看一个五行分区(数据无关紧要 — 谓词恒为真):
| 行 | 朴素上下文 | 启用 absorption |
|---|---|---|
| 0 | C1[A:1] | C1[A:1] |
| 1 | C1[A:2], C2[A:1] | C1[A:2] — C2 被吸收 |
| 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 | 五个上下文 | C1[A:5] |
存活上下文从 O(n) 缩为 O(1),因此整个分区上的总量从 O(n²) 降为 O(n)。在量词为无界时,证明丢弃合法的 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 条件把该行价格与上一行价格比较 — 这是分区层面的事实,不是上下文层面的事实 — 所以两个上下文在共享的每一行上都被迫算出相同的布尔值:
| 星期 | 价格 | C1 — 周二开始 price > PREV(price) | C2 — 周三开始 price > PREV(price) |
|---|---|---|---|
| 一 | $100 | — | — |
| 二 | $108 | $108 > $100 ✓(刚开始) | — |
| 三 | $112 | $112 > $108 ✓ | $112 > $108 ✓(刚开始) |
| 四 | $116 | $116 > $112 ✓ | $116 > $112 ✓ |
| 五 | $110 | $110 > $116 ✗ — 确定 | $110 > $116 ✗ — 确定 |
一旦谓词开始依赖各自上下文自己的边界,这个故事就崩塌了 — 这正是 §2.6 的主题。
2.6 实战示例 4 — 当 absorption 变得不安全
DEFINE 引用 FIRST 时会发生什么变化 — absorption 规则不再成立,planner 对该模式禁用 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 起点)。
| 星期 | 价格 | C1 — 周一开始 FIRST = $100 price < $100 + 10 | C2 — 周二开始 FIRST = $108 price < $108 + 10 |
|---|---|---|---|
| 一 | $100 | $100 < $110 ✓ | — |
| 二 | $108 | $108 < $110 ✓ | $108 < $118 ✓(刚开始) |
| 三 | $112 | $112 < $110 ✗ — 周一–二确定 | $112 < $118 ✓ |
| 四 | $116 | — | $116 < $118 ✓ |
| 五 | $110 | — | $110 < $118 ✓(继续推进) |
在 absorption 下,C2 本会在周二被并入 C1 — 合并后的上下文只保留 C1 的天花板($110),因此 C2 的独立视角(天花板 $118,持续到周五的 4 日 run)不被 C1 的未来所覆盖。在这一周里,输出恰好不会改变:C1 记录周一–二,C2 起始于该匹配之内并由 SKIP PAST LAST ROW 丢弃,下一次尝试从周三开始,带有自己的天花板($122),并匹配周三–五。但一般而言,较早上下文的 DEFINE 结果不再涵盖较晚上下文的结果,因此 absorption 所依赖的计数比较不再成立。因此,凡 DEFINE 谓词存在匹配起点依赖时,planner 都会先发制人地禁用 absorption。
(如果领跑上下文的匹配确实成功了,那些起于其确认区间内的上下文会 — 在默认的 AFTER MATCH SKIP PAST LAST ROW 下 — 直接被丢弃;保留它们只是为了万一领跑匹配失败时运行时还有可回退的起点。)
下表在海报右下面板("② Navigation")的基础上补充了复合形式,总结了哪些导航形式会引入匹配起点依赖:
| 导航 | 匹配起点依赖 | 可吸收? |
|---|---|---|
| PREV, NEXT | 无 | 是 |
| LAST(无偏移) | 无 | 是 |
| LAST 含偏移 | 边界检查 | 否 |
| FIRST(任何形式) | 直接依赖 | 否 |
| 复合(内层 FIRST) | 直接依赖 | 否 |
| 复合(内层 LAST,无偏移) | 无 | 是 |
| 复合(内层 LAST 含偏移) | 边界检查 | 否 |
§2.5 和 §2.6 这两个示例可以归并为一条规则。同命运让 absorption 安全:如果同一模式元素上的所有上下文对未来所有谓词都会算出相同答案,那么只保留最老的一个即可。不同命运让 absorption 不安全:当谓词在上下文私有状态上分叉的那一刻 — 这正是 FIRST 和带偏移 LAST 所做的 — 每个存活上下文都代表一个不能保证被别的上下文覆盖的未来,因此丢弃其中任何一个都无法再被证明是安全的。
planner 在编译期识别这种区分,并对整个模式开启或关闭 absorption;关闭时,运行时承担多上下文的代价。海报面板 ③ 的基准未使用 FIRST,因此 absorption 保持开启,这正是 PostgreSQL 在成功用例和失败用例中都保持线性的原因。
海报上的基准数字正是同一算法在大规模上的展开。在成功模式 (A+ B+ C+ D) 下,PostgreSQL 和 Trino 在匹配确定后都大致按 O(n) 扩展,PostgreSQL 领先约 16× 到 33×(Trino 的数字已排除 JVM 启动时间)。
在失败模式 (A+ B+ C+ E) 下,Trino 看来缺少 absorption,追逐每一个潜在匹配起点,退化得甚至比 O(n²) 更快(行数增至 5× 时耗时约为 56×);在 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。这其中任何一个都不能被 "起点更早的更长匹配" 取代,因为标准说用户想要全部这些。
| 行 | SKIP PAST LAST ROW | SKIP TO NEXT ROW |
|---|---|---|
| 0 | 开始匹配;行 0–4 会是唯一的匹配 | 在行 0 开始匹配 |
| 1 | (在匹配 0 内部) | 在行 1 开始匹配 — 必须保留 |
| 2 | (在匹配 0 内部) | 在行 2 开始匹配 — 必须保留 |
| 3 | (在匹配 0 内部) | 在行 3 开始匹配 — 必须保留 |
| 4 | 匹配 0 确定(行 0–4) | 五个匹配全部确定:0–4、1–4、2–4、3–4、4–4 |
AFTER MATCH SKIP TO NEXT ROW 下,每一个晚开始的上下文都是自己独立的一行输出。同一模式元素上的两个上下文不再冗余 — 它们都是必需的输出,丢弃任何一个都会悄无声息地丢掉用户要求的匹配。
注意谓词没有变化。A AS TRUE 无论哪个上下文来问,在每一行上都求值相同,因此 §2.5 的同命运条件仍然成立。变化的是输出要求:即便上下文拥有相同的未来,也必须共存,因为它们对应结果中的不同行。所以无论 DEFINE 子句如何,只要 AFTER MATCH SKIP TO NEXT ROW 生效,planner 就禁用 context absorption。
把 §2.6 和 §2.7 并排来看,就得到查询语义排除 absorption 的两种方式:
DEFINE 中的 FIRST 或带偏移的 LAST 触发。AFTER MATCH SKIP TO NEXT ROW 触发。
任意一种条件都足以对整个模式禁用 absorption,不以 UNBOUNDED FOLLOWING 结束的框架也同样如此。当这些都不生效 — 默认 AFTER MATCH SKIP PAST LAST ROW、无界的框架结束,以及仅使用 PREV、NEXT 或不带偏移 LAST 的 DEFINE 条件 — absorption 被启用,但仅针对处于模式可吸收区域内的状态:像 A+ 或 A* 这样的领先贪婪无界变量、像 (A B)+ 这样带无界贪婪量词的固定长度分组、像 (A+ B)+ 或 (A+ B){2} 这样本体以上述之一开头的贪婪分组,或由这些构成的交替分支;勉强分组会使其整个子树失去资格。在满足这一条件之处,如 §2.5 中的 A+,运行时收敛为单一上下文并保持线性;§2.3 中的 START UP+ DOWN+ 则完全没有可吸收区域。
§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,结束边界必须是 UNBOUNDED FOLLOWING 或正的 offset FOLLOWING(因此使用默认值的框架也会被拒绝),并且禁止 EXCLUDE NO OTHERS 以外的 EXCLUDE 选项。这些是符合性检查,而非优化 —— RPR 对框架的理解是 匹配跨度,标准不考虑用匹配行以外的任何东西来填充它。
框架通过验证后,解析器将 PATTERN 子句转换为由四种节点构建的树 —— 变量引用、序列(连接)、交替、分组(带括号的子模式)。每个节点以三个数字携带量词 —— 下界、上界(可能为无穷),以及一个勉强匹配标志:
| 源 | 树编码 |
|---|---|
| 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) |
然后每个 DEFINE 谓词会针对分区的列进行类型检查并强制转换为布尔表达式。由此带来两件实务上的事情。首先,解析分析不会为 DEFINE 向查询的目标列表添加任何内容;而是由规划器像处理 HAVING 那样,将 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 优化
优化带来双重回报:一次反映在扁平数组的静态元素数量上,再一次反映在运行时处理的每一行上。每条变换都减少了运行时必须枚举的状态空间。优化器在一次自底向上的遍历中应用九条重写规则(在序列内部,分组合并会再运行一次,因为先前的合并可能使两个相同的分组相邻):
- 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{2}?→A{2}(凡 min = max 之处都会清除勉强性)
量词相乘仅在可达到的计数构成一个连续区间且首选匹配不变时才进行折叠:外层为精确值((A{2,3}){5} → A{10,15})、子节点 min 为 0,或者子区间首尾相接且子节点 min 至多为 1 或子节点 max 无界((A+)+ → A+、(A{1,3}){2,4} → A{2,12}),其中外层 min 为 0 时还要求子节点 min 至多为 1((A{2,})* 保持不变,因为 A* 会接受一行)。自身量词不精确的分组子节点必须先具有固定长度的本体,因此即使外层为精确值,((A | B B){1,2}){2} 也原样保留。其他组合可能引入扁平形式会遗漏的间隙 —— 例如 (A{2}){2,3} 仅接受 {4, 6},但朴素的 A{4,6} 也会接受 5 —— 或者移动首选匹配((A{2,3}){1,2} 首选三行,而 A{2,6} 会取四行),因此优化器原封不动地保留它们。它并不是唯一受限的重写:分组合并和后缀合并要求本体消费固定数量的行,前缀合并不处理 min 为 0、max 有限且内容可空的分组,勉强节点既不合并也不相乘((A+?)+ 保持不变),新边界会溢出的重写也会被放弃。
元素形状
扁平数组的每个元素代表模式中的一个位置。逻辑上有六种类型:变量引用(唯一消费行的种类);分组开始和分组结束标记,开启和闭合带括号的子模式;交替标记,作为分支列表的头部;结束每个分支的分支分隔符;以及位于模式末尾的结束标记。
每个元素还携带一个深度(其分组嵌套层级)、量词(最小和最大重复次数,可能为无穷),以及两个转移指针 —— next("消费完此元素后去哪里")和 jump("跳到何处",由交替标记和分支分隔符用于串联分支,由分组开始用于指明其自身的分组结束 —— 量词允许零的分组经由该结束的 next 被跳过 —— 由分组结束用于循环回本体)。
对于 PATTERN ((A B)+),编译后的数组如下所示:
PATTERN ((A B)+) compiles to:
[0] BEGIN depth 0 quant 1..∞
next → 1 jump → 3
(打开组;jump 指明
其自身的 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
(关闭组;jump 回环)
[4] FIN 模式完成
模式通过 next 从左到右读取,jump 处理非线性的边。在索引 3 处,END 的 jump 指回索引 1,这正是无界外层量词循环的方式;在索引 0 处,BEGIN 的 jump 指明位于索引 3 的 END;如果分组是可选的,跳过将经由该 END 的 next 离开到索引 4,而不会到达 END。运行时无需在运行时构造图 —— 它只是在遍历数组时沿这两个指针走。
每元素属性
除了形状之外,每个元素还携带五个逻辑属性,指挥运行时在该位置的行为:
- 勉强(Reluctant)
- 反转量词展开的顺序。贪婪量词先尝试"再循环",再尝试"退出";勉强量词先尝试"退出"。在
A+?中由变量携带;在((…)+?)中由分组的 BEGIN 和 END 携带。 - 可空循环(Empty-loopable)
- 设置在本体可空的分组结束上(
(A? B?)+、(A | B*)+;(A?)*会先被相乘为A*,不留下分组结束)。告知运行时在低于 min 时于正常的循环回路旁再加一条快进退出,使循环保护不会在能产生空迭代的分组中扼杀合法匹配。 - 空匹配优先(Empty-preferred)
- 设置在本体偏好空匹配的分组结束上,如
(A?? B??){2}。在低于 min、分组自身的贪婪性不起作用之处,将快进退出排在循环回路之前。 - 在可吸收区域内
- 标记每个位于可吸收区域 内 的元素 —— 由运行时用来跟踪当前状态是否仍处于安全区域。
- 吸收比较点
- 标记应运行吸收比较的具体元素。对于简单的
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
从元素 0 开始遍历扁平数组
并标记满足结构性情形
的元素
前三个检查是查询级的:它们恰好对应于 §2.7 中的条件(输出侧:SKIP 模式)、有界框架(边界破坏单调性),以及 §2.6(数据侧:DEFINE 中的 FIRST 或带偏移的 LAST)。其中任何一个失败时,分析不设置任何标志,吸收在整个查询范围内被禁用。当全部通过时,该遍历允许四种结构形态:
- 情形 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 —— 本体以无界变量开头的分组
-
领先的无界变量本身可吸收(情形 1)并护住较早的上下文。一旦状态越过 A,吸收就停止 —— 本体的其余部分没有单调性保证,因此 A 获得两个标志,外围的 BEGIN 获得区域内标志,而 B 和 END 都不获得标志。
(A+ B)+、(A+ B){2} - 情形 4 —— 交替
-
经由分隔符链到达的每个分支,都按上述情形各自单独判断;只要任一分支符合条件,交替标记就获得区域内标志。
A+ | B+、A+ | C D
这四种形态 未涵盖 的结构情形同样具有启发性。A B+ 在当前规则下不可吸收,因为领先的 A 在无界部分开始前消费了一行,所以相隔一行启动的上下文在无界本体内部处于不同位置。像 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 != currentPos:
将 targetPos 处的行
取入 nav_slot
将外层槽指向 nav_slot
result = eval_inner_expression()
恢复 current_row_slot
将按引用传递的结果从 nav_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 currentPos − n
# 复合: match-rel 后再步进
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
对相应范围进行校验
(内层 FIRST/LAST 用 match 范围,
外层步进用分区范围)
当同一 DEFINE 中的多个导航调用指向同一行时,位置缓存可以短路元组存储的获取 —— 这在像 price > PREV(price) AND volume > PREV(volume) 这样两个调用都解析到前一行的表达式中很常见。该缓存仅保存"上一次获取的位置",交换本身仍是单一操作。
导航调用的分类是规划器对吸收决策的贡献。规划器遍历每个 DEFINE 表达式,根据所有上下文是否将在同一行上计算出 相同 的布尔值,或者每个上下文将各自计算 自己 的,将每个变量分入两个桶之一。该桶在运行时决定两件事:变量的求值频率(共享一次,或每个受影响的上下文一次 —— §3.5 阶段 1),以及上下文吸收是否可能(§2.5 与 §2.6):只要有一个依赖匹配起点的变量,就会对整个模式禁用吸收。
- 无导航
- 仅
PREV/NEXT - 不带偏移的
LAST - 内层为
LAST(无偏移)的复合
- 带偏移的
LAST FIRST(任意形式)- 内层为
FIRST的复合 - 内层为
LAST(带偏移)的复合
分类在计划期完成并与每个 DEFINE 变量一同存储,因此运行时不花时间做决策 —— 它在处理一行时只需读取每个变量的桶。
保留预算
导航会触及窗口函数机制本来已流过的行。为了让这些行可用,执行器构建在一个保留近期行滑动窗口的元组存储之上;问题是该窗口需要多宽。执行器根据两个互补的偏移来计算,每次扫描对每个偏移解析一次(常量偏移在执行器初始化时也会解析,以便普通 EXPLAIN 能够显示它们):
- 回溯预算
- 任何 DEFINE 调用从当前行向后能达到多远。
- 从起点起的前瞻预算
- 从最老存活上下文的匹配起点出发的最小向前到达距离(为负时为向后)—— 即任何 DEFINE 调用可能需要的最早一行。
运行时元组存储的修剪标记被设置为两个位置中较早的那个 —— 当前行减去回溯预算,以及最老存活上下文的匹配起点加上前瞻预算。该标记之前的任何内容都无法被任何存活上下文中的任何导航调用所触及,元组存储可自由地丢弃它们。EXPLAIN 报告的 Nav Mark 行(§3.7)—— Lookback 和 Lookahead —— 就是这两个预算,而非实测峰值。每一行仅在有导航为其提供输入时才打印,并且即使没有 ANALYZE 也会显示;值仅在运行时才能确定的偏移(例如 generic plan 的参数)在普通 EXPLAIN 下打印 runtime,在 EXPLAIN ANALYZE 下打印其解析后的值,而 retain all(Lookback)或 infinite(Lookahead)表示溢出的偏移。
3.4 匹配边界 —— SKIP、INITIAL 与有界框架
匹配结果被记录为两个值:匹配开始的行,以及其长度。负的起始值表示该位置尚未被求值;一旦起始值被设置,对执行器的后续查询 —— "这一行是否在某个匹配之内?" —— 可通过检查这对值以 O(1) 时间作答。长度编码了结果:-1 表示未匹配的行,0 表示空匹配,真实匹配则为行数。零长度是一个真实的结果,而非错误:它表示一个未消费任何行的匹配,执行器必须将其与未匹配的行以及"此位置上尚未尝试匹配"都区分开。
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 三阶段每行引擎
每当外围的窗口函数机制需要知道某个给定行是否属于某个已匹配的框架时,执行器的每行驱动程序就被调用。驱动程序为当前起始位置查找或创建上下文,然后逐行向前驱动 NFA —— 每一行都将按变量的匹配数组重置为"未求值" —— 直到该上下文不再有存活状态或分区结束。DEFINE 谓词是惰性求值的:变量在某个状态首次消费它时才被求值,因此在这一行上没有任何存活状态测试的变量永远不会被求值。前进步骤本身按固定顺序由三个阶段组成 —— 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)
若其记录了匹配且为
SKIP PAST LAST ROW:
修剪起始于该匹配内的
后续 context
这一顺序并非风格选择。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 是变量
# advance 只会停留在变量上
若 varMatched[elem.varId] 为
未求值:
立即对其 DEFINE 求值
若非 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 分支(按顺序,一旦记录了
FIN 即停止),
BEGIN (进入组;若 min = 0
另含可选跳过路径),
END (loop back / exit / fast-forward —
见下),
FIN (记录 matchEndRow,
保存 matchedState, 并标记
该 context,使此候选范围内的
后续 context 被修剪 — 见下),
在每个遇到的变量处停下:
将 state 加入 ctx.states
(按 elemIdx + counts 去重)
记录一个到达 FIN 的状态不仅仅是为候选匹配做书签。在 AFTER MATCH SKIP PAST LAST ROW 下,下一个可报告的匹配必须严格地在当前匹配之后开始 —— 所以一旦 Advance 处理完记录了候选的上下文,每一个起始行落在候选范围内的后续上下文都会在同一行被裁剪掉,即便命中 FIN 的上下文可能通过贪婪回退继续寻找更长的匹配。
该裁剪是安全的,因为无论该搜索如何结束(更长的匹配替换候选,或候选保留),所有被裁剪的上下文都在下一个可报告匹配必须跳过的范围内启动,因而绝不可能产生自己的输出。
这是跨上下文的 FIN 时裁剪步骤。在上下文内部,FIN 也会削减词法上较劣的工作:Advance 丢弃剩余的排队状态(本节前面已述),并且在一次 DFS 内,每一条偏好度较低的路径 —— 后面的 ALT 分支、BEGIN 的跳过路径与进入路径中的另一条、勉强变量的进入路径、END 的循环路径与退出路径中的另一条 —— 都会在记录匹配后停止,因此一次推进至多记录一个匹配。
最棘手的每元素逻辑位于 END 处理程序内。当分组的迭代计数低于下界时,运行时必须循环回去;当达到或超过上界时必须退出;处于中间时两种选项都有效,由量词的贪婪性决定先尝试哪一个:
advance_end(state, elem):
count = state.counts[elem.depth]
若 count < elem.min:
循环回到主体
若 elem 为 empty-loopable:
# nullable 主体,见 §3.2
同时克隆一个 fast-forward
状态,使其退出该组且
count 已满足
(若主体偏好空匹配则
先 fast-forward;若第一条
路径到达 FIN,则丢弃
第二条路径)
否则若 count >= elem.max:
重置此深度的 counts
通过 next 退出
(END→END:递增外层
END 的 count)
否则:
# min <= count < max:分叉
构建一个退出状态
(此深度的 counts 已重置)
若 greedy:
先 loop
若 loop 到达 FIN:
丢弃 exit
# 偏好更长
否则其次 exit
否则 (reluctant):
先 exit
若 exit 到达 FIN:
丢弃 loop
# 偏好更短
否则之后再 loop
添加到上下文中的每个状态都会经过去重检查,将其位置和计数与现有状态列表进行比较。由于 Advance 按 DFS 顺序处理分支,任何交替的第一分支产生的状态先落地 —— 而任何后续产生相同位置和计数的分支在插入时被拒绝。这恰好是 §2.4 的词法顺序规则所要求的,在运行时的最底层实现,而无需单独一遍扫描。
可空循环分组
运行时必须解除的一个微妙情形是 可空分组 —— 一个其本体可以匹配零行的分组,因为本体的每个子节点本身都是可选的。像 (A? B?)+ 和 (A | B*)+ 这样的模式都有此性质:根据数据,本体可以在完全不消费任何行的情况下完成一次迭代。(像 (A?)* 这样只有单个可选子节点的情形会在编译时被改写为 A*,不留下分组。)这在原则上没问题,但它给 NFA 的 epsilon 扩展带来了真正的危险。如果本体产生空匹配,END 元素循环回本体(其 jump 是分组的第一个子节点),本体再一次产生空匹配,再次到达 END,依此类推。如果没有东西阻止它,Advance 的 DFS 将永不终止。
该保护在编译时决定,在运行时执行。每当规划器看到一个本体可空的分组时,它将该分组的 END 元素标记为 可空循环。运行时维护一个已访问位图,在每个状态的 DFS 扩展前清除,其中只标记那些被打上标记的 END —— 其他任何东西都不会形成循环,因为任何其他的循环回退都已消费了一行。到达已标记的 END 意味着本体刚刚推导出一次空迭代,而该状态不会被丢弃:在下界或以上时,它就在那里离开分组(一次空迭代会使量词停止);低于下界时,状态落入常规的循环回退,因此每次空到达仍会使计数增加,直至达到 min。考虑行流中两个变量在任何地方都不匹配的 (A? B?){2,3}:
iter 1: A? B? 匹配零行
→ END, count = 1 (低于 min)
END 已被标记(在进入分组时),
但低于 min:
→ 循环回到 A?
iter 2: A? B? 匹配零行
→ END, count = 2 (满足 min)
END 已被标记,处于 min:
→ 离开分组
以零长度匹配退出
在低于下界时,可空循环标记还告诉 END 处理程序在常规循环回退路径之外再克隆一个额外的 快进 状态:
advance_end (count 低于 min):
循环回退路径:
循环回到主体
(为下一次迭代中
一次真实、非空的匹配
保留余地)
若 elem 为 empty-loopable:
fast-forward 路径:
重置此深度的 count
通过 next 退出该组,
将剩余所需迭代
当作空匹配处理
两条路径扮演互补的角色。循环回退捕获本体之后仍有真实匹配可产出的情形 —— 例如,在 (A? B?){2,3} 后面跟着仅在更晚行上匹配 A 的数据时,循环回退让第二和第三次迭代得以找到非空匹配。快进立即退出分组,宣告"其余所需的迭代都是空的",并使匹配以零长度本体获得成功。决定顺序的是本体,而不是分组自身的贪婪性:恰好在本体偏好空匹配时(像 (A?? B??) 这样的勉强本体),快进排在前面;若第一条路径到达 FIN,第二条就被丢弃,因此偏好度较低的路径无法取代首选匹配。插入时的去重检查防止任一路径生成超过其份额的状态。
除了循环保护之外,还有一个启动时的小技巧用于消除上下文最开始处零行结果的歧义。每个潜在起始行的上下文创建步骤会在 任何行被消费之前,从实际起点之前一行的位置出发,进行一次 初始 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 队列中待处理的状态 —— 按词法顺序,所有剩余状态都不太被偏好,可以立即丢弃。
- 候选匹配裁剪(跨上下文) Advance
- 其他起始行落在候选匹配范围内的上下文 —— 命中 FIN 的上下文可能仍会继续搜索更长的匹配(贪婪回退),但在
AFTER MATCH SKIP PAST LAST ROW下,候选范围内的任何上下文无论该搜索如何结束都不再能产生可报告的输出,并在 Advance 处理完记录了该候选的上下文后立即被裁剪。 - 循环保护 Advance
- 在同一 DFS 内到达已被标记的可空分组 END 的 epsilon 扩展(在经由 BEGIN 进入时或在较早的到达时被标记)—— 否则将永远循环;在下界或以上时状态就在那里离开分组,低于下界时则继续循环。
- 空循环快进 Advance
- 在可空分组的下界以下,一条额外的路径,它退出分组并将其余所需迭代声明为空,并按本体的偏好与循环回退排定先后。
- 有界框架截断 Match
- 匹配已到达用户指定框架上界的上下文 —— 被强制不匹配以使其无法越过该上界(§3.4)。
按阶段标识阅读各条目可勾勒出上下文的生命周期:每行通过三个主要阶段(Match、Absorb、Advance)触发裁剪。改为按描述阅读,则按所针对的目标对规则进行分组:死分支、冗余上下文、等价状态、无限循环,以及越出用户施加的边界。
任何单条规则单独都不够。空循环快进单独无法阻止无限的 epsilon 循环;吸收单独在 DEFINE 引用匹配起点时会过度合并;去重单独只能去除冗余 状态 而非冗余 上下文。运行时在重要情形下保持线性 —— 100,000 行上的 PATTERN (A+ B+ C+ D),海报面板 ③ 的基准 —— 仅仅是因为每一层都捕获到上面各层遗漏的内容。源代码中记录了这些层捕获不到的情形:去重会把仅在 min 以上计数不同的状态分开保留,因此 C 永不为真的 (A{2,} B)+ C 在峰值时持有 Θ(n²) 个状态,并累计创建 Θ(n³) 个状态(320 行耗时 37 s);而由全可空交替组成的序列会被逐条路径枚举,因此 (A?|B?){30} 要花半小时以上。
3.7 EXPLAIN 输出
带有 RPR 的查询上的 EXPLAIN ANALYZE 会暴露普通窗口函数所没有的 NFA 级统计信息。在文本格式中,它们在窗口算子旁、位于 Pattern: 行、任何 Nav Mark 行(普通 EXPLAIN 也会显示)以及 Storage: 行之后发出:
Nav Mark Lookback: <n> | runtime | retain all
Nav Mark Lookahead: <n> | runtime | infinite
(每一行仅在 DEFINE 使用了
为其提供输入的导航时出现)
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)
(第二个 NFA 行仅在任一计数
非零时出现;计数为零时
不带其 (len ...) 打印)
非文本格式将每个计数作为单独的属性发出。Peak 和 total 是对运行时的直接度量:曾同时存活过多少状态、查询生命周期内创建了多少状态,以及被去重合并掉了多少;pruned 统计在单行之后就失败的上下文。匹配长度直方图分离出四种结果 —— 成功匹配、在超过一行之后才失败的匹配尝试(mismatched)、被吸收的上下文,以及因起始于已记录匹配之内而被 AFTER MATCH SKIP PAST LAST ROW 释放的上下文(skipped)—— 并以 min/max/avg 报告它们能让性能病态一目了然:健康运行显示大多数上下文要么是 matched 要么是 absorbed,mismatched 长度很小。
两个 Nav Mark 计数器报告 §3.3 从 DEFINE 推导的元组存储保留预算。Lookback 是跨 PREV、带任意偏移(包括默认的 0)的 LAST 以及内层为 LAST 的复合形式,从当前行向后到达的最深位置;Lookahead 是从最老存活上下文匹配起点测量的最小向前到达距离(在查看匹配起点之前的行时为负),由 FIRST 和内层为 FIRST 的复合形式贡献。
每个计数器在偏移量为常量时打印为固定整数,在偏移量为仅在每次扫描时才能确定的非常量表达式时打印为"runtime",并且 —— 仅对 Lookback —— 在偏移溢出时打印为"retain all";溢出的 Lookahead 打印为"infinite"。每一行仅在 DEFINE 中有导航为其提供输入时才会发出,并且两者在普通 EXPLAIN 下也会出现:常量偏移在执行器初始化时就已确定,而值仅在运行时才能确定的偏移(例如 generic plan 的参数)在那里打印"runtime",在 EXPLAIN ANALYZE 下打印其解析后的整数。
这些计数器加在一起让我们无需将 gdb 附加到后端就能调试 RPR 性能。
除计数器外,EXPLAIN 还会打印一行由编译后的元素数组构建的 Pattern:,因此它显示的是经过编译时重写后的模式(PATTERN (A A) 解释为 a{2}),并带有吸收标记 #(比较点)和 ~(可吸收区域);DEFINE 和 AFTER MATCH SKIP 选项不会显示。按书写原样再现这些子句(包括勉强量词、分组重复和跳跃选项)是 pg_get_viewdef() 的工作,它在使此往返稳定方面下了不少功夫,以便 pg_dump 和 pg_upgrade 能在不发生语义漂移的情况下保留 RPR 对象 —— rpr_explain 下的回归套件逐项进行验证(参见 §4)。
§4. 测试 —— 覆盖地图
该补丁附带五个回归套件,共同练习 §3 描述的每一层 —— 大约 22,000 行 SQL,每个套件专注于一个不同的关注点。这种拆分是有意的:把解析器关注点、运行时正确性、规划器交互和输出格式化保持在独立文件中,使失败更易定位,并防止一层中无关的变更意外地使另一层的测试失效。五个套件是:
- rpr
- WINDOW 子句集成 —— 在合成股票数据上的真实窗口场景(V 形、W 形、连续上涨、反转),以及导航语义和 DEFINE 限制错误。
- rpr_base
- 解析器层 —— 关键字接受、语法形态、量词、导航解析、错误信息,以及 pg_dump/pg_upgrade 往返稳定性;另有规划器层 —— 模式优化、吸收标志、优化回退、规划器集成。
- rpr_nfa
- NFA 运行时 —— 三阶段循环、每种可吸收形态的吸收、以及上下文生命周期的边界情况。
- rpr_explain
- 输出格式化 —— NFA 统计、模式反解析、标识符引用、跨重载的格式稳定性。
- rpr_integration
- 规划器交互 —— 防止无关窗口优化破坏 RPR 语义的守卫。
4.1 rpr —— 端到端场景
场景套件是测试集的公开面孔:它使用约 1,600 行的合成股票价格数据集,并对其运行真实的查询 —— V 形回升、W 形(双底)、连续上涨与下跌、反转模式、多符号分区。这些场景是唯一输入输出读起来像用户可能真正书写的查询的测试;该文件的其余部分与其他套件一样是精简的 —— PREV/NEXT 嵌套与非常量偏移错误、DEFINE 引用规则,以及导航偏移语义。
由于这些查询组合了每一层(解析器、规划器、执行器、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。其余测试脚手架照常被丢弃。诸如勉强标志在反解析和再解析之间丢失这样的缺陷,只有在端到端往返时才会浮现。
4.3 rpr_nfa —— 运行时引擎
这是练习 §3.5 与 §3.6 中描述的每个机制的套件。它的测试遵循一致的模式:内联的 VALUES 行携带一个变量名数组,声明每一行上哪些 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 输出是面向用户的契约的一部分 —— 第三方工具(监控仪表盘、日志抓取器)会解析它,看似仅是表面的修改也可能破坏它们。rpr_explain 套件验证三件事:
- NFA 计数器出现在正确的位置 —— 每个 WindowAgg 的统计信息(peak/total/merged 状态、peak/total/pruned 上下文、matched/mismatched/absorbed/skipped 的长度直方图)在
EXPLAIN ANALYZE下以文本、JSON 和 XML 格式以文档化的标签出现,并且 Nav Mark Lookback 和 Lookahead 恰好在 DEFINE 中有导航为其提供输入时出现。 - 模式正确反解析 —— 每种量词形态,包括勉强变体和有界形式;每种交替;每种分组;每种
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,以便row_number、rank和ntile等与框架无关的窗口函数处理。RPR 的框架是匹配跨度,而非聚合窗口,必须原样保留。 - 运行条件下推
- 对窗口函数输出的单调
WHERE过滤通常可作为停止条件下推到窗口算子。对 RPR 而言这会过早地终止模式匹配,可能在匹配延伸的中段切断它。 - 窗口去重(RPR 与非 RPR)
- 具有相同
ORDER BY和框架的两个窗口通常会被合并为一个。RPR 窗口与非 RPR 窗口绝不能共享状态,因为 RPR 一侧携带匹配结果。 - 窗口去重(不同 DEFINE 或 SKIP)
- 具有相同
PATTERN但DEFINE子句不同或AFTER MATCH SKIP不同的两个 RPR 窗口产生不同的匹配,必须保持区分,即使其结构形态完全相同。 - 未使用输出投影
- 这一条是允许应用的:当外围查询从不读取窗口的输出时,窗口函数变为 NULL 且其 WindowAgg 被删除,行数保持不变。测试检查在 WindowAgg 保留时 DEFINE 读取的列仍能到达它,并且在窗口的值被读取时该窗口会被保留。
- 移动聚合的逆向转移
- 具有逆向转移函数的窗口聚合通常可在框架移动时增量求值。RPR 的约简框架不是滑动窗口;逆向转移路径会产生错误结果。
其他用例检查代价估算是否考虑了 DEFINE、持有 RPR 窗口的子查询不会被展平、DEFINE 表达式不会泄漏到上层 WindowAgg,以及 LIMIT 保持在 WindowAgg 之上;第二组将 RPR 与 CTE、连接、集合操作、预备语句、分区表以及类似构造一起运行。大多数受守卫的用例遵循相同的形态:一个触发该优化的基线(通常是非 RPR 查询,在 EXPLAIN 中检查),然后是一个结构相似、该优化 未 被应用的 RPR 查询 —— 对于 DEFINE/SKIP 去重用例,基线是两个相同的 RPR 窗口,而逆向转移用例则用一个记录日志的聚合而非 EXPLAIN 来检查绕过。两半合在一起证明规划器中的守卫是在做实在的工作,而不是在没有真正验证的情况下放行每个查询。
此套件也是 §3.4 较短的原因。"匹配边界"机制 —— 约简框架、SKIP、INITIAL、有界框架截断 —— 在别处接受运行性的测试;rpr_integration 所验证的是没有任何其他优化器阶段在中途篡改它们。rpr_integration 通过让其余套件能够信任它们的输入完整无损地到达执行器。