2026 · Vancouver
Simon Fraser University — Vancouver Campus

Row Pattern Recognition 심층 분석

PostgreSQL 위에 구현된 ISO/IEC 19075-5 · SQL R020 가이드 — 무엇을 만들었고, 무엇이 아직 남아 있으며, 실제로 어떻게 동작하는지.

PGConf.dev 2026에 전시된 포스터의 동반 자료입니다.
표준을 훑어보고, 실제 예제를 따라가며, 설계를 살펴본 뒤, 직접 만든 패턴으로 라이브 NFA 시뮬레이터를 돌려보십시오.
관련 토론: pgsql-hackers 스레드 · 최신 패치 (v55) · commitfest #4460.
Tatsuo Ishii — SRA OSS K.K.  ishii@postgresql.org
Henson Choi — INZENT CO., LTD.  assam@inzent.com

AI 사전 번역 — 오역 가능.

§1. 표준, 하위 집합, 그리고 남은 과제

1.1 표준 범위

Row Pattern Recognition은 ISO/IEC 9075-2:2016에서 SQL에 도입되었으며, 동반 문서인 ISO/IEC 19075-5:2021(파트 5, "Row Pattern Recognition")에 기술되어 있다.

표준은 동일한 기반 메커니즘에 대해 두 가지 표면(surface)을 정의한다. 기능 R010은 MATCH_RECOGNIZE 절을 FROM 목록에 두어 파생 테이블(derived table)을 만드는 형태이고, 기능 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 구현된 기능

구현된 어휘는 row pattern recognition을 동기 부여하는 정형적 V형, W형, 반전(reversal) 패턴을 표현하기에 충분하다. 또한 모든 표준 수량자 — 일곱 가지 reluctant 변형 *?, +?, ??, {n}?, {n,}?, {,m}?, {n,m}?를 포함 — 와, DEFINE 조건이 인접한 행을 비교하는 데 필요한 네 가지 내비게이션 원시 연산을 모두 다룬다.

PATTERN 절
윈도우 사양 안에 row pattern을 정의한다. 서로 다른 패턴 변수는 최대 240개.
윈도우 프레임
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING 또는 n ≥ 1인 ROWS BETWEEN CURRENT ROW AND n FOLLOWING (19075-5 §6.10.2). 그 밖의 프레임은 거부되며, 허용되는 제외(exclusion) 옵션은 EXCLUDE NO OTHERS뿐이다.
정규식: + * ? |
표준 수량자와 대안(alternation).
정규식: ( ) 그룹핑
괄호로 묶인 하위 패턴.
정규식: {n} {n,} {,m} {n,m}
한정된(bounded) 반복 횟수.
Reluctant *? +? ?? {n}? {n,}? {,m}? {n,m}?
표준이 정의하는 일곱 가지 reluctant(비탐욕) 변형 전부(absorption 최적화에서는 제외됨).
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의 내부 인수는 컬럼 참조를 하나 이상 포함해야 하고, 오프셋은 실행 시점 상수(run-time constant)여야 한다.
INITIAL
패턴 매치는 현재 행에서 시작해야 함(기본값).
AFTER MATCH SKIP PAST LAST ROW
기본 skip 모드. context absorption 적용 가능.
AFTER MATCH SKIP TO NEXT ROW
매치의 중첩 허용. absorption 비활성화.

1.3 미구현

아직 구현되지 않은 기능들은 느슨하게 세 그룹으로 묶인다. 첫 번째 — 그리고 가장 큰 — 그룹은 MEASURES를 중심으로 하는 구문 가족이다. MEASURES 절 자체, SUBSET, CLASSIFIER(), B.price 같은 패턴 한정(pattern-qualified) 컬럼 참조, 그리고 LAST(B.price)나 PREV(B.price) 같은 패턴 한정 내비게이션이 여기 속한다.

이들은 독립된 결함이라기보다 하나의 빠진 조각을 다른 각도에서 본 것이다. 실행기는 매치별 히스토리(per-match history) — 매치 내 각 행이 어떤 패턴 변수에 매핑되었는지의 기록 — 를 유지해야 하며, 이 구문들 중 어느 것도 그 기록 없이는 의미 있는 정의를 가질 수 없다. CLASSIFIER()는 그 기록에서 변수 이름을 읽고, B.price는 기록 항목이 B인 행의 price 컬럼을 읽으며, LAST(B.price)는 같은 행 집합을 훑어 마지막 하나를 골라낸다. SUBSET U = (A, B)는 두 버킷을 합쳐 집계하는 가상 변수를 정의하고, MEASURES는 정확히 그 집계를 사용해 AVG(U.Price) 같은 표현을 평가한다.

현재 실행기는 DEFINE 술어를 행마다 평가하지만 그 결과 변수 할당을 어디에도 기록하지 않는다 — 나중에 질의할 대상이 없다. 따라서 히스토리 인프라 구축이 이 그룹 전체의 선결 조건이며, 기록이 존재하기만 하면 개별 기능들은 작은 투영(projection)으로서 자연스럽게 따라온다.

두 번째 그룹은 대안적인 skip 대상들이다. AFTER MATCH SKIP TO FIRST var와 AFTER MATCH SKIP TO [LAST] var가 여기 해당한다(단순 SKIP TO var는 SKIP TO LAST var를 뜻한다). 이들 또한 매치 히스토리에 의존하는데, 실행기가 가장 최근 매치 안에서 주어진 변수에 매핑된 행을 가리킬 수 있어야 하기 때문이다.

나머지는 이질적인 잔여 항목들이다. SEEK 키워드(INITIAL의 대안), 빈 패턴 (), 제외(exclusion) 형태 {- … -}, 순서 무관 연산자 PERMUTE, 그리고 DEFINE 안의 집계 함수와 서브쿼리이다. 뒤의 둘은 현재 모두 거부된다(변수 한정 집계는 매치 히스토리도 필요로 한다).

MEASURES
매치별 출력 표현식의 이름 지정, 예: MEASURES LAST(B.Price) AS Bottom, AVG(U.Price) AS Avg. R020에서는 윈도우 함수처럼 OVER를 통해 노출된다. FINAL/RUNNING 키워드(19075-5 §5.4)를 받아들이지만, R020에서는 measures가 항상 매치의 마지막 행에서 평가되므로(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
해당 변수로 매치된 첫 행으로 skip.
AFTER MATCH SKIP TO [LAST] var
해당 변수로 매치된 마지막 행으로 skip.
정규식: {- -}
제외(exclusion) — 매치된 행을 ALL ROWS PER MATCH 출력에서 제거. 이 옵션은 윈도우에는 적용되지 않으므로(19075-5 §6.3.3 (4)), 윈도우에서는 이 문법이 허용되지만(§6.13) 작용할 출력이 없다.
정규식: ()
빈 패턴 — 빈 시퀀스에 매치.
PERMUTE(...)
나열된 변수들에 대한 순서 무관 매칭. 키워드는 인식된 뒤 거부되며("PERMUTE is not supported"), permute는 여전히 패턴 변수 이름으로 쓸 수 있다.
DEFINE의 집계 함수
SUM, AVG, COUNT 같은 집계 함수는 DEFINE 술어에 사용할 수 없다. 표준은 부분 매치에 대한 running 집계를 허용한다. AVG(B.Price) 같은 변수 한정 집계는 MEASURES/CLASSIFIER()가 요구하는 것과 동일한 매치 히스토리에 의존하고, 비한정 집계는 지금까지의 매치에 속한 모든 행을 대상으로 한다.
DEFINE의 서브쿼리
DEFINE 안의 서브쿼리는 모두 거부된다. 표준은 row pattern recognition을 수행하지 않고 row pattern 변수를 참조하지 않는 서브쿼리를 허용하지만, 패치는 현재 그보다 넓게 거부한다.

누락으로 오인되기 쉬운 네 가지 추가 주의사항을 여기 짚어둔다.

첫째, 패턴 앵커 ^와 $는 표준 자체가 WINDOW 절의 RPR에서 허용하지 않는다(19075-5 §6.13: "the anchors (^ and $) are not permitted with row pattern matching in windows"; 기반 정의는 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): row pattern recognition은 다른 row pattern recognition 안에 중첩될 수 없고, MEASURES와 DEFINE은 외부 참조(outer references)를 포함할 수 없으며, MEASURES나 DEFINE 내부의 서브쿼리는 row pattern 변수를 참조할 수 없으며(패치는 더 나아가 위에 적은 대로 DEFINE의 서브쿼리를 모두 거부한다), RPR은 재귀 질의 내부에서 사용될 수 없다. 패치는 외부 참조 규칙("cannot use outer query column in DEFINE clause")과 재귀 규칙을 강제하며, 후자는 WITH RECURSIVE 절의 모든 요소에 적용한다. 또한 DEFINE 안의 volatile 함수와 전체 행(whole-row) 참조도 거부한다.

넷째, MATCH_RECOGNIZE 자체 — 같은 메커니즘의 테이블-절 표면인 기능 R010 — 는 이 패치의 범위 밖이다. PostgreSQL이 결국 R010을 추가할지 여부는 미래 패치 시리즈의 문제이지, 이번 시리즈의 평가 척도가 아니다.

출처. 이 절의 구현/미구현 목록은 패치 시리즈의 현재 상태를 반영하며, 구체적으로는 v55 (2026-11-17) 기준이다.

§2. 예제 — 실제 동작 방식

이 절의 예제들은 점진적으로 쌓아 올린다. 먼저 row pattern matching이 문자열 패턴 매칭과 본질적으로 다른 개념적 이유에서 시작해, DEFINE 조건을 흥미롭게 만드는 네 가지 내비게이션 함수를 소개하고, 마지막으로 다섯 가지 예제를 따라간다. 단일 매치(NFA 이동), 대안(alternation), 단순한 경우의 context absorption, 그리고 absorption이 비활성화되는 두 가지 경우이다.

내비게이션을 저렴하게 만드는 내부 메커니즘 — 1-슬롯 튜플 교환 — 은 실행기 설계에 속하며 여기가 아니라 다음 절에서 다룬다.

2.1 행 패턴이 텍스트 패턴과 다른 이유

텍스트 정규식은 문자 스트림에 매칭되며, 모든 위치에 고려할 심볼이 정확히 하나 있다. 런타임의 질문 — "현재 심볼이 'A'와 같은가?" — 은 단일한 예/아니오 답을 가진다. 백트래킹 오토마타는 이를 활용한다. 문자당 최대 하나의 분기만 살아남고, 모호함의 비용은 입력을 다시 읽는 것으로 지불된다.

row pattern은 근본적으로 다르다. 행은 단일 심볼이 아니라 컬럼들의 튜플이며, 여러 불리언 술어 즉 DEFINE 조건들에 대해 평가된다. 두 술어가 같은 행에서 동시에 참일 수 있고, 표준은 그들이 상호 배타적이어야 한다고 말하지 않는다. 다음을 보자:

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

price = 150, volume = 2000인 행은 A와 B를 모두 만족하지만 C는 만족하지 않는다. 패턴 매처는 이를 단일 상태로 축약할 수 없다 — 두 패턴 변수가 살아 있고, 그중 어느 쪽이든 이름으로 지목하는 패턴 요소가 진행될 수 있다. 따라서 NFA는 파티션 행마다 하나가 아닌 여러 동시 상태를 들고 있어야 한다.

텍스트 정규식 대 행 패턴: 텍스트 정규식은 심볼마다 단일 상태로 진행하지만, 행은 여러 DEFINE 술어가 병렬로 매치될 수 있다. TEXT REGEX single state advances through symbols A B C one symbol per position · one transition ROW PATTERN one row, multiple predicates evaluated row price = 150 · volume = 2000 A ✓ price > 100 B ✓ volume > 1000 C ✗ price > 200 two predicates true · two states stay alive
텍스트 정규식은 심볼마다 하나의 상태로 축약된다. 행은 여러 DEFINE 술어를 동시에 만족할 수 있어, 다수의 상태가 병렬로 살아남는다.

이 단 하나의 관찰이 나머지 아키텍처를 좌우한다. 실행 상태는 컨텍스트들의 리스트이고, 각 컨텍스트는 상태들의 리스트이며, 매 행마다 런타임은 모든 상태에 대해 "여기서 참인 변수들을 가지고 어디로 갈 수 있는가?"를 묻는다. 그 결과로 생기는 분기들이 런타임에 여러 계층의 가지치기 — 컨텍스트 내부의 상태 중복 제거, 컨텍스트 간의 absorption, 그리고 §3.6에 정리된 다른 규칙들 — 가 필요한 이유다. 이것들이 없다면 살아 있는 상태와 컨텍스트 수는 파티션에 비례해 늘고, 패턴 매칭 비용은 초선형(super-linear)이 된다.

2.2 내비게이션 함수

현재 행만 참조하는 DEFINE 조건은 제한적이다. 거의 모든 흥미로운 패턴은 현재 행을 그 이웃 또는 매치 안에서 이미 받아들여진 행들과 비교해야 한다. 표준은 이를 위해 네 가지 내비게이션 함수를 제공하며, 패치는 이 모두를 구현한다.

PREV(expr [, n])
현재 행의 n행 앞 행(기본값 n = 1). "오늘 vs 어제" 비교에 사용.
NEXT(expr [, n])
현재 행의 n행 뒤 행(기본값 n = 1). 전방 lookahead. 윈도우 형태에서는 윈도우가 단조롭기 때문에 흔치 않다.
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 안에서든 매치 경계 기준이어서 context absorption과 상호작용한다. 이때 플래너는 패턴 전체에 대해 absorption을 비활성화한다. 이 상호작용의 메커니즘은 §2.6의 주제이다.

2.3 풀이 예제 1 — NFA 이동

예제의 목적단순한 비-absorbing 패턴에서 행마다의 NFA 상태 변화를 보인다. 추적은 행 0에서 시작한 컨텍스트를 따라간다. 행 1–4에서 시작한 컨텍스트들은 그와 나란히 실행되다가, 그 매치가 기록되면 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에 대해:

행가격참 변수동작
0100START새 컨텍스트. START 매치되고 즉시 종료(max=1). 상태는 UP+로 진행.
1110START, UPUP 매치. 진행 시 분기: 한 상태는 UP에서 반복, 다른 상태는 DOWN+로 진출.
2120START, UP반복 중인 상태에서 UP 매치 후 다시 분기. 행 1의 DOWN 상태는 사망(120 ≮ 110).
3115START, DOWN반복 상태에서 UP 실패하여 사망. 행 2의 DOWN 상태가 매치. 진행 시 분기: DOWN에서 반복, #FIN로 종료 — 행 0–3에 걸친 매치 후보가 기록됨.
4108START, DOWN반복 상태에서 DOWN 매치 후 다시 분기. 행 0–4에 걸친 새 FIN 후보가 더 짧은 후보를 대체.
5130START, UP반복 중이던 DOWN 상태 실패(130 ≮ 108). 이 컨텍스트에 살아있는 상태가 남지 않으므로 기록된 후보(행 0–4)가 매치로 확정. 다음 시도는 행 5에서 시작. START는 매치하지만 UP을 만나기 전에 파티션이 끝남.

핵심: 행 3에서 그 행은 START(항상 참)와 DOWN 모두를 만족하지만, START는 행 3에서 시작하는 컨텍스트에만 의미가 있다. 이 컨텍스트에서는 반복 중이던 UP 상태가 사망하고 DOWN+에서 대기하던 상태만 진행한다. §2.1의 다중 상태성은 매 UP 매치마다 팬아웃으로 가시화된다(상태는 UP+에 머물거나 DOWN+로 진행할 수 있다). greedy 선호는 "종료 전에 한 번 더 반복"이므로 데이터가 충분하면 반복 분기가 매치를 더 길게 연장한다. 여기서는 반복 중이던 DOWN이 행 5에서 사망(130 ≮ 108)하고, 행 4에서 DOWN이 종료될 때 만들어져 행 3의 후보를 대체한 마지막 FIN 후보(행 0–4)가 매치로 확정된다.

질의 결과는 이 추적에서 직접 따라온다. RPR 시맨틱에서는 윈도우 함수 first_value(price)와 last_value(price)가 매치를 시작한 행에서만 평가된다 — 매치 안의 다른 모든 행은 reduced frame이 비어 있으므로 이 윈도우 함수에 대해 NULL을 산출한다. 따라서 우리 데이터의 출력은 포스터 우상단 패널에 표시된 표와 같다:

행가격start_priceend_price
0100100108
1110——
2120——
3115——
4108——
5130——

행 0은 매치 시작이므로 프레임이 행 0–4를 포함하고, 윈도우 함수는 V형의 시작 가격($100)과 바닥 가격($108)을 보고한다. 행 1–4는 매치 안이지만 시작이 아니므로 NULL을 받는다. 행 5(가격 $130)는 어떤 매치 밖이라 마찬가지로 NULL을 받는다.

2.4 풀이 예제 2 — 대안과 어휘 순서

예제의 목적한 행이 둘 이상의 대안을 만족할 때 단일 컨텍스트가 어떻게 여러 병렬 상태를 들고 가는지, 그리고 표준이 어떻게 타이브레이크를 하는지 보인다.

(A | B) 형태는 매처에 선택지를 준다. 어떤 행에서든 두 대안이 독립적으로 검사되고 그중 임의의 수가 매치할 수 있다. 여기서 §2.1의 다중 상태성이 단일 컨텍스트 안에서 가시화된다 — 컨텍스트 간(이쪽은 absorption)이 아니라, 실행기가 패턴 순서대로(앞선 분기 먼저) 탐색하는 병렬 분기들로서.

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

가격이 상승했고 동시에 $100을 초과한 행을 상상하라 — UP과 HIGH가 모두 참이다. 각 대안은 자신의 상태를 낳는다. 하나는 UP 분기를, 다른 하나는 HIGH 분기를 걷는다. 이어서 두 상태 모두 DONE으로 진행하고, 거기서 만난다.

행참 변수살아있는 상태
RUP, HIGH상태 A(UP-분기)와 상태 B(HIGH-분기)가 같은 카운트로 둘 다 DONE으로 진행. B는 A의 중복이므로 폐기됨
R+1DONE상태 A가 DONE에 매치되어 #FIN에 도달

표준의 관점에서 두 분기는 같은 행들에서 같은 길이의 매치를 만들어내, 두 후보 경로 — UP, DONE 라벨과 HIGH, DONE 라벨 — 가 생긴다. 표준은 이를 어휘 순서(lexical order)로 결정한다. (UP | HIGH)에 작성된 대안 중 먼저 쓰인 쪽이 매치 길이와 무관하게 이긴다. UP이 HIGH보다 앞에 있으므로 살아남는 경로는 UP, DONE이다. 실행기는 이를 FIN이 아니라 행 R에서 강제한다. UP-분기 상태를 먼저 추가하므로 nfa_append_state_unique()가 그것을 유지하고 동일한 HIGH-분기 상태를 버린다.

어휘 순서는 CLASSIFIER()가 결국 구현될 때 그것을 잘 정의된 함수로 만들어주는 것이다 — 두 술어가 모두 참이어도 런타임이 사용자에게 "이 행은 HIGH가 아니라 UP으로 매치되었다"고 알려줄 수 있다. 어휘 순서는 대안의 일차 규칙이다. lex 더 앞쪽 분기가 lex 더 뒷쪽 분기를 이기며, 이는 lex-뒷쪽이 더 긴 매치를 만들 수 있더라도 마찬가지다. 그리고 lex-뒷쪽(아마 더 짧은) 분기는 모든 lex-앞쪽 분기가 FIN에 도달하기 전에 사망하는 경우에 한해 이길 수 있다. greedy 길이는 단일 수량자 안에서 결정된다 — 같은 대안 분기의 두 완료가 주어졌을 때 greedy 수량자는 반복 횟수가 더 많은 쪽을 선호한다.

2.5 풀이 예제 3 — Context absorption (같은 운명)

예제의 목적순진한 O(n²) 총 상태 작업량이 absorption 하에서 왜 O(n)이 되고, 살아있는 컨텍스트는 O(1)이 되는지 보인다.

absorption을 보이는 가장 단순한 패턴은 DEFINE A AS TRUE를 가진 PATTERN (A+)이다. 모든 행이 A에 매치되고, 표준은 매처가 모든 행을 잠재적 매치 시작으로 고려할 것을 요구한다. 순진하게는 N행 파티션에 N개 컨텍스트가 생긴다. 다섯 행짜리 파티션을 보자(데이터는 무엇이든 — 술어가 상수 참):

행순진한 컨텍스트absorption 적용
0C1[A:1]C1[A:1]
1C1[A:2], C2[A:1]C1[A:2] — C2 흡수됨
2C1[A:3], C2[A:2], C3[A:1]C1[A:3]
3C1[A:4], C2[A:3], C3[A:2], C4[A:1]C1[A:4]
4다섯 컨텍스트C1[A:5]

살아있는 컨텍스트가 O(n)에서 O(1)로 줄어들므로, 파티션 전체에 걸친 총량은 O(n²)에서 O(n)으로 떨어진다. 폐기를 정당화하는 absorption 규칙은 수량자가 무한일 때 간단하다:

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). 그리고 실행기는 투기적으로 수요일에 시작되는 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 ✗ — 확정
같은 운명 C1과 C2가 공유하는 모든 행에서 둘은 동일한 표현식을 평가해 동일한 결과를 산출한다 — 그리고 금요일에 정확히 같은 비교에서 함께 사망한다. C2가 가질 어떤 미래든 C1도 갖는다. C2를 C1에 흡수시키는 것은 아무것도 버리지 않는다.

술어가 각 컨텍스트 자신의 경계에 의존하기 시작하는 순간 이야기는 깨진다 — 그것이 §2.6의 주제다.

2.6 풀이 예제 4 — Absorption이 안전하지 않게 될 때

예제의 목적DEFINE이 FIRST를 참조할 때 무엇이 변하는지 보인다 — absorption 규칙이 더 이상 성립하지 않고, 플래너는 그 패턴에 대해 absorption을 비활성화한다.

분석가가 주가가 런(run) 시작일로부터 10달러 이내에 머문 연속 거래일을 찾고 싶어한다고 하자 — 일종의 consolidation 윈도우이다. 패턴과 DEFINE은 다음과 같다:

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

이 조건은 이제 현재 행의 가격을 현재 런 시작의 가격과 비교한다. 다른 날에 시작된 두 런은 서로 다른 FIRST(price) 값을 가지므로, 동일한 패턴 요소와 동일한 카운트의 두 상태가 더 이상 교환 가능하지 않다. 그들의 미래는 absorption이 막 버리려 했던 경계에 의존한다.

§2.5와 정확히 같은 거래주를 사용하자 — 월요일부터 금요일까지 $100, $108, $112, $116, $110. 런타임은 다시 두 후보 런을 동시에 살려둔다. C1은 월요일 시작, C2는 화요일 시작(STABLE+ 하에서는 모든 행이 잠재적 런 시작이다).

요일가격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 ✓ (계속 진행)
다른 운명 C1은 수요일에 이틀 짜리 런(월–화)으로 사망. C2는 그 자체로는 금요일까지 계속 살아 있을 것이다. 같은 가격, 같은 형태의 질문 — 그러나 각자의 매치 시작에서 도출된 다른 천장. 같은 날에 두 컨텍스트가 정반대 결론에 도달했다.

absorption 하에서는 C2가 화요일에 C1으로 병합되었을 것이다 — 병합된 컨텍스트는 C1의 천장($110)만 유지하므로, C2의 별개 시각(천장 $118, 금요일까지 이어지는 4일 런)은 C1의 미래가 커버하지 못한다. 이 특정한 주에는 우연히 출력이 바뀌지 않는다. C1이 월–화를 기록하고, 그 매치 안에서 시작한 C2는 SKIP PAST LAST ROW에 의해 폐기되며, 다음 시도는 수요일에 자신의 천장($122)으로 시작해 수–금에 매치한다. 그러나 일반적으로는 앞선 컨텍스트의 DEFINE 결과가 더 이상 나중 컨텍스트의 결과를 포괄하지 않으므로, absorption이 의존하는 카운트 비교가 무효가 된다. 따라서 DEFINE 술어가 매치 시작 의존성을 가질 때마다 플래너는 absorption을 선제적으로 비활성화한다.

(선두 컨텍스트의 매치가 실제로 성공한 경우, 그 인정된 구간 내에서 시작된 컨텍스트들은 — 기본 AFTER MATCH SKIP PAST LAST ROW 하에서 — 단순히 폐기된다. 선두 매치가 실패할 경우 런타임이 되돌아갈 곳이 있도록 살려두는 것뿐이다.)

아래 표는 포스터 우하단 패널("② Navigation")에 복합 형태를 더해 확장한 것으로, 어떤 내비게이션 형태가 매치 시작 의존성을 만드는지 요약한다:

내비게이션매치 시작 의존성흡수 가능?
PREV, NEXT없음예
LAST (오프셋 없음)없음예
LAST 오프셋 있음경계 검사아니오
FIRST (임의)직접아니오
복합 (내부 FIRST)직접아니오
복합 (내부 LAST, 오프셋 없음)없음예
복합 (내부 LAST 오프셋 있음)경계 검사아니오

§2.5와 §2.6의 두 예제는 단일 규칙으로 환원된다. 같은 운명이 absorption을 안전하게 만든다. 동일한 패턴 요소의 모든 컨텍스트가 미래의 모든 술어에 대해 같은 답을 계산할 것이라면, 가장 오래된 것만 유지하면 된다. 다른 운명은 absorption을 안전하지 않게 한다. 술어가 컨텍스트 사적 상태에서 분기하는 순간 — 그것이 정확히 FIRST와 오프셋이 있는 LAST가 하는 일이다 — 살아있는 모든 컨텍스트는 다른 어떤 컨텍스트도 커버한다고 보장할 수 없는 미래를 대표하므로, 그중 하나를 폐기하는 것이 안전하다고 더 이상 보일 수 없다.

플래너는 이 구분을 컴파일 타임에 감지하고 패턴 전체에 대해 absorption을 켜거나 끈다. 꺼져 있으면 런타임이 다중 컨텍스트 비용을 치른다. 포스터 패널 ③의 벤치마크는 FIRST를 쓰지 않으므로 absorption이 켜진 채로 유지되며, 그래서 PostgreSQL이 성공 사례와 실패 사례 모두에서 선형으로 유지된다.

포스터의 벤치마크 수치는 같은 알고리즘을 대규모로 펼친 것이다. 성공 패턴 (A+ B+ C+ D)에서 PostgreSQL과 Trino 모두 매치가 확정되면 대략 O(n)으로 스케일하며, PostgreSQL이 약 16×에서 33× 앞선다(Trino 수치는 이미 JVM 시작 시간을 제외한 것이다).

실패 패턴 (A+ B+ C+ E)에서 absorption이 없는 것으로 보이는 Trino는 모든 잠재 매치 시작을 쫓느라 O(n²)보다도 빠르게 퇴화한다(행 수 5×에 시간 약 56×). 100,000행에서 다섯 시간 이상 걸리는 반면, PostgreSQL은 92 ms에 끝낸다 — 약 217,000× 속도 향상.

이 격차는 엔지니어링 다듬기가 아니다 — 정확히 §2.5와 §2.6의 같은 운명/다른 운명 구분을 파티션의 모든 잠재 매치 시작 행에 적용한 결과이다.

2.7 풀이 예제 5 — SKIP이 absorption을 비활성화할 때

예제의 목적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 ROWSKIP 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가 유효할 때 context absorption을 비활성화한다.

§2.6과 §2.7을 나란히 놓으면 질의의 시맨틱이 absorption을 배제하는 두 가지 방식이 보인다:

데이터 측 · §2.6
술어가 컨텍스트마다 다르게 평가됨.
DEFINE의 FIRST 또는 오프셋이 있는 LAST에 의해 유발.
출력 측 · §2.7
출력이 모든 매치 시작을 별개 행으로 요구.
AFTER MATCH SKIP TO NEXT ROW에 의해 유발.

두 조건 중 하나만 있어도 패턴 전체의 absorption을 비활성화하기에 충분하며, UNBOUNDED FOLLOWING으로 끝나지 않는 프레임도 마찬가지다. 어느 것도 적용되지 않을 때 — 기본 AFTER MATCH SKIP PAST LAST ROW, 무한 프레임 끝, 그리고 PREV, NEXT, 단순 LAST만 사용하는 DEFINE 조건 — absorption이 활성화되지만, 패턴의 흡수 가능 영역(absorbable region)에 있는 상태에만 적용된다. 흡수 가능 영역이란 A+나 A* 같은 선두 greedy 무한 변수, (A B)+ 같은 무한 greedy 수량자를 가진 고정 길이 그룹, (A+ B)+나 (A+ B){2}처럼 본문이 이들 중 하나로 시작하는 greedy 그룹, 또는 이들로 구성된 대안 분기이다. reluctant 그룹은 그 하위 트리 전체를 자격에서 제외한다. 이것이 성립하는 곳에서는, §2.5의 A+처럼, 런타임이 단일 컨텍스트로 축약되어 선형성을 유지한다. §2.3의 START UP+ DOWN+는 흡수 가능 영역이 전혀 없다.

§3. 설계 — 파서에서 실행기까지

Row Pattern Recognition은 잘 정의된 중간 형식을 통해 작업을 넘기는 세 단계로 구현된다. 파서는 SQL 텍스트를 패턴 트리와 DEFINE 술어 목록으로 변환한다. 플래너는 트리를 패턴 요소들의 평탄 배열로 컴파일하고 그중 어떤 것이 context absorption에 참여할 수 있는지 결정한다. 실행기는 그 배열을 파티션에 대해 행마다 3단계 루프로 실행한다. 각 단계는 자체 데이터 형태를 가지며, 대부분의 영리함은 경계에 있다. 캐시에 들어가는 평탄 NFA, 참조마다 슬롯을 만들지 않고 단일 튜플 슬롯을 재사용하는 내비게이션 모델, 그리고 O(n²) 작업량을 O(n)으로 바꾸는 absorption 규칙이다.

SQL 텍스트
  │
  │  파서 단계
  ▼    프레임 검증
       패턴 트리 구축
       DEFINE 타입 검사

패턴 트리 + DEFINE 리스트
  │
  │  플래너 단계
  ▼    트리 최적화
       평탄 NFA 배열로 컴파일
       absorbability 판정

평탄 NFA + absorption 플래그
  │
  │  실행기 단계
  ▼    행별 엔진:
       Match → Absorb → Advance

매치 결과:
  시작 행, 길이, 성공/실패

아래 절들은 이 파이프라인을 따라 내려간다. §3.1은 파서와 패턴 트리의 형태를, §3.2는 트리를 평탄 NFA로 바꾸는 컴파일을, §3.3은 DEFINE 술어가 이웃 행을 보는 데 쓰는 내비게이션 모델을, §3.4는 매치 경계 처리 — 매치 시작과 끝을 고정하는 SKIP, INITIAL, 한정 프레임 규칙 — 를, §3.5는 3단계 행별 엔진을, §3.6은 상태 공간을 한정된 채 유지하는 모든 가지치기 메커니즘을, §3.7은 구현이 EXPLAIN 출력에 노출하는 내용을 다룬다.

3.1 파서 — 패턴 트리 구축

파서는 윈도우 사양 안에 PATTERN 절이 있는지로 pattern recognition을 인식한다. 첫 번째 작업은 프레임 검증이다. RPR은 일반 윈도우 질의에는 없는 제약을 부과하기 때문이다. 프레임 모드는 ROWS여야 하며(RANGE나 GROUPS가 아님), 시작 경계는 CURRENT ROW여야 하고, 끝 경계는 UNBOUNDED FOLLOWING 또는 양수 offset FOLLOWING이어야 하며(따라서 기본값 프레임도 거부된다), EXCLUDE NO OTHERS 이외의 EXCLUDE 옵션은 금지된다. 이는 표준 준수 검사이지 최적화가 아니다 — RPR에서 프레임 개념은 매치 구간이며, 표준은 매치된 행 외의 무언가로 채우는 것을 고려하지 않는다.

프레임이 검증을 통과하면 파서는 PATTERN 절을 네 종류의 노드 — 변수 참조, 시퀀스(연결), 대안(alternation), 그룹(괄호로 묶인 하위 패턴) — 으로 이루어진 트리로 변환한다. 각 노드는 수량자를 세 개의 수로 들고 있다: 하한, 상한(무한일 수 있음), 그리고 reluctant 매칭 플래그.

소스트리 인코딩
AVAR(A, min=1, max=1)
A+VAR(A, min=1, max=∞)
A*VAR(A, min=0, max=∞)
A{3,5}VAR(A, min=3, max=5)
A+?VAR(A, min=1, max=∞, reluctant=true)

그 후 각 DEFINE 술어는 파티션의 컬럼들에 대해 타입 검사되고 불리언 표현식으로 강제된다. 그 결과 두 가지 실용적 일이 따른다. 첫째, 파스 분석(parse analysis)은 DEFINE을 위해 질의의 타깃 리스트에 아무것도 추가하지 않는다. 대신 플래너가 HAVING에 대해 하듯 DEFINE 술어가 참조하는 모든 컬럼을 필요한 것으로 표시하고, 외부 질의가 그 컬럼을 select하지 않더라도 실행기 단계까지 전파한다 — 그렇지 않으면 런타임이 평가할 대상이 없다. 둘째, PATTERN에는 등장하지만 DEFINE에는 등장하지 않는 변수는 암묵적으로 참이다: 모든 행에 매치된다.

3.2 컴파일 — AST에서 평탄 NFA로

플래너는 파서의 트리를 실행기가 돌릴 자료구조 — 인덱스로 주소 지정되는 패턴 요소의 평탄 배열 — 로 변환한다. 컴파일은 6단계 파이프라인으로 진행된다:

compile(astTree):
  1. AST 최적화
  2. 크기와 깊이 측정
  3. 요소 배열 할당
  4. AST로부터 채움
       (next/jump 포인터 할당)
  5. 마무리 — FIN 센티널 설정
  6. absorption 대상 요소 표시

평탄 형태가 선택된 이유는 단순하다. 실행기는 파티션마다 패턴을 여러 번 순회해야 하며, 연속된 인덱스 주소 지정 가능한 배열이 순회하기에 가장 저렴한 자료구조이다. 1단계와 6단계가 흥미롭다 — 1단계는 배열의 크기를 결정하고, 6단계는 §2.5의 absorption 최적화가 작동할지 여부를 결정하기 때문이다.

AST 최적화

최적화는 두 번 보상한다. 한 번은 평탄 배열의 정적 요소 수에서, 또 한 번은 런타임에서 처리되는 모든 행에서. 모든 변환은 런타임이 열거해야 하는 상태 공간을 줄인다. 옵티마이저는 아홉 가지 재작성 규칙을 단일 상향식(bottom-up) 패스로 적용한다(시퀀스 안에서는 그룹 병합이 한 번 더 실행되는데, 앞선 병합이 동일한 두 그룹을 인접하게 만들 수 있기 때문이다):

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
Reluctance 정규화
A{2}? → A{2} (min = max인 곳에서는 reluctance를 제거)

수량자 곱셈은 도달 가능한 카운트가 하나의 연속 구간을 이루고 선호되는 매치가 바뀌지 않을 때만 합친다. 외부가 고정((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}는 외부가 고정이어도 그대로 남는다. 그 외 조합은 평탄화하면 받아들이는 카운트 집합에 빈자리(spectrum gap)가 생기거나 — 예를 들어 (A{2}){2,3}은 {4, 6}만 받지만 단순히 A{4,6}으로 바꾸면 5도 받게 된다 — 선호되는 매치가 이동할 수 있으므로((A{2,3}){1,2}는 세 행을 선호하지만 A{2,6}은 네 행을 취한다), 옵티마이저는 구조를 그대로 둔다. 조건이 걸린 재작성은 이것만이 아니다. 그룹 병합과 접미 병합은 고정된 수의 행을 소비하는 본체를 요구하고, 접두 병합은 min이 0이고 max가 유한하며 내용이 nullable한 그룹을 거절하며, reluctant 노드는 병합도 곱셈도 되지 않고((A+?)+는 그대로 남는다), 새 한계가 오버플로되는 재작성은 거절된다.

요소 형태

평탄 배열의 각 요소는 패턴의 단일 위치를 나타낸다. 여섯 가지 논리적 종류가 있다: 변수 참조(행을 소비하는 유일한 종류), group begin과 group end 마커(괄호 하위 패턴을 열고 닫음), alternation 마커(분기 목록의 머리), 각 분기를 끝내는 branch separator, 패턴 끝의 finish 마커이다.

각 요소는 또한 깊이(그룹 중첩 수준), 수량자(min/max 반복 횟수, 무한일 수 있음), 그리고 두 전이 포인터를 가진다 — next("이 요소를 소비한 후 어디로 갈지")와 jump("어디로 건너뛸지", alternation 마커와 branch separator에서는 분기 연결, group begin에서는 자신의 group end를 지정 — 수량자가 0을 허용하는 그룹은 그 END의 next를 통해 건너뛴다 — , group end에서는 본체로 되돌아가는 데 사용).

PATTERN ((A B)+)의 컴파일된 배열은 다음과 같다:

PATTERN ((A B)+) 컴파일 결과:

[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가 비선형 간선을 처리한다. idx 3에서 END의 jump는 idx 1로 돌아가는데, 이것이 무한 외부 수량자가 루프하는 방식이다. idx 0에서 BEGIN의 jump는 idx 3의 자기 END를 지정하며, 그룹이 선택적이라면 건너뛰기는 END에 도착하지 않고 그 END의 next를 통해 idx 4로 나간다. 런타임은 그래프를 구성할 필요가 없다 — 배열을 순회하면서 이 두 포인터를 따라가기만 한다.

요소별 속성

형태 외에도 각 요소는 그 위치에서 런타임의 동작을 지시하는 다섯 가지 논리 속성을 가진다:

Reluctant
수량자 확장 순서를 뒤집는다. greedy 수량자는 "exit"보다 "loop again"을 먼저 시도하고, reluctant 수량자는 "exit"를 먼저 시도한다. A+?의 경우 변수가, ((…)+?)의 경우 그룹의 BEGIN과 END가 들고 있다.
Empty-loopable
본체가 nullable한 그룹의 END에 설정((A? B?)+, (A | B*)+. (A?)*는 먼저 A*로 곱해져 group end가 남지 않는다). min 미만에서 정상 loop-back 옆에 fast-forward exit를 추가하도록 런타임에 지시하여, cycle guard가 빈 반복을 만들 수 있는 그룹의 정당한 매치를 죽이지 않게 한다.
Empty-preferred
(A?? B??){2}처럼 본체가 빈 매치를 선호하는 그룹의 END에 설정. min 미만에서, 그룹 자체의 greed가 아무것도 말해 주지 않는 곳에서, fast-forward exit를 loop-back보다 앞에 둔다.
In-absorbable-region
absorption 가능 영역 안에 있는 모든 요소에 표시 — 런타임이 현재 상태가 여전히 안전 영역에 있는지 추적하는 데 사용.
Absorption-comparison-point
absorption 비교가 실행되어야 하는 특정 요소 표시. 단순한 A+의 경우 변수에 위치, (A B)+ 같은 무한 그룹의 경우 group end에만 위치.

"in-region"과 "comparison-point"의 분리는 중요하다. absorption은 반복이 닫히는 지점에서만 의미가 있기 때문이다. (A B)+의 본체 내부에서는 런타임이 반복 중이고 그 라운드의 카운트가 아직 최종 값에 도달하지 않았다. 여기서 비교하면 비교 불가능한 값을 비교하는 셈이다. 상태가 group end에 도달해야 런타임이 결정할 수 있다. 따라서 첫 속성은 "당신은 아직 흡수 가능 영역에 있다"고 말하고, 두 번째는 "당신은 비교 지점에 도달했다 — 지금 확인하라"고 말한다.

흡수 가능성 분석

컴파일의 6단계는 §2.5의 "같은 운명" 규칙에 컴파일 타임 증거를 제공한다. 결정은 계층적이다:

isAbsorbable(query):
  if SKIP mode != SKIP PAST LAST ROW
      → return false
  if frame end != UNBOUNDED FOLLOWING
      → return false
  if any DEFINE depends on match_start
      → return false
  요소 0부터 평탄 배열을 순회하며
  구조적 사례를 만족하는
  요소를 표시

처음 세 검사는 질의 레벨이다. 이는 정확히 §2.7(출력 측: SKIP 모드), 한정 프레임(경계가 단조성을 깸), §2.6(데이터 측: DEFINE의 FIRST 또는 오프셋이 있는 LAST)의 조건과 대응한다. 그중 하나라도 실패하면 분석은 어떤 플래그도 설정하지 않고 absorption은 질의 전반에서 비활성화된다. 모두 통과하면 순회는 네 가지 구조적 형태를 인정한다:

Case 1 — 단순 무한 변수
A+, A*, A{2,∞}
각 반복은 정확히 한 행. 이른 컨텍스트의 카운트는 공유된 모든 위치에서 늦은 컨텍스트의 그것보다 항상 ≥.
Case 2 — 고정 길이 그룹, 무한 외부
(A B)+, (A B{2})+, ((A (B C){2}){2})+
모든 자식이 min == max이므로 본체는 의미적으로 펼친 {1,1} 형태와 동등 — (A B{2})+는 (A B B)+처럼 동작. 각 반복은 고정된 수의 행을 소비. 카운트 우세는 여전히 성립.
Case 3 — 본체가 무한 변수로 시작하는 그룹
(A+ B)+, (A+ B){2}
앞서는 무한 변수 자체가 흡수 가능(Case 1)하고 이전 컨텍스트를 보호. 상태가 A를 지나는 즉시 absorption 중단 — 본체의 나머지는 단조성 보장이 없으므로, A는 두 플래그를 모두 받고, 둘러싼 BEGIN은 in-region 플래그를 받으며, B와 END는 아무것도 받지 않는다.
Case 4 — 대안
A+ | B+, A+ | C D
separator 체인을 통해 도달하는 각 분기를 위 사례들로 개별 판정한다. 어느 분기든 자격을 갖추면 alternation 마커는 in-region 플래그를 받는다.

위 네 가지 형태에 해당되지 않는 구조적 사례도 마찬가지로 교훈적이다. A B+는 현재 규칙으로 흡수될 수 없다. 앞서는 A가 무한 부분이 시작되기 전에 행을 소비하므로, 한 행 차이로 시작한 컨텍스트들이 무한 본체 내부의 서로 다른 위치에 있게 되기 때문이다. A+?같은 reluctant 수량자는 구성상 제외된다. absorption 규칙은 greedy 시맨틱(긴 매치가 짧은 매치를 포함)을 가정하는데, reluctant 매칭은 그 방향을 뒤집는다.

결과는 패턴별이 아닌 요소별 결정이다. 하나의 질의 계획이 (A+ B+ C)나 (A+ B+)+의 선두 A+에는 absorption을 활성화하고 — 후자는 Case 3을 그 선두 요소에 적용한 것에 해당 — 그 이후 모든 것에는 비활성화할 수 있다. 런타임은 absorption 패스를 고려할 때마다 현재 상태의 요소에 있는 comparison-point 속성을 참조하기만 한다. 상태가 비-흡수 영역으로 이동하면 그 상태에 대해 absorption은 영구히 꺼진다 — 정확히 §2.5와 §2.6이 알고리즘 레벨에서 참이어야 하는 것이다.

3.3 내비게이션 — 1-슬롯 튜플 교환

DEFINE 표현식은 행에 대해 평가되는 일반 SQL 표현식이지만, PREV, NEXT, FIRST, LAST — 다른 행을 가리키는 참조 — 를 포함할 수 있다. 행 자체는 이미 윈도우의 tuplestore에 버퍼링되어 있다. 실행기가 여전히 관리해야 하는 것은 SQL 표현식 메커니즘이 읽는 튜플 슬롯이다. 표현식 안의 컬럼 참조는 계획 시점에 슬롯에 바인딩되기 때문이다. 구현은 모든 내비게이션 호출에 대해 단일 navigation slot을 재사용한다. 내부 표현식을 평가하기 전에 슬롯을 교체했다가 후에 복원하므로, SQL 표현식 메커니즘의 나머지는 그 차이를 전혀 알지 못한다.

실행기가 보는 모델은 작다. DEFINE 표현식이 평가되는 행을 들고 있는 current row slot과, 런타임이 일시적으로 다른 행을 가리키도록 할 수 있는 navigation slot이 있다. 임의의 내비게이션 호출 주변에서 런타임은 navigation slot을 설정하고, 마치 current row를 읽는 것처럼 내부 표현식을 평가한 뒤, 원래 행을 복원한다. 의사코드:

eval_navigation(call):
  targetPos = compute_target_position(call)
  if targetPos가 유효 범위 밖:
      return NULL

  current_row_slot 저장
  if targetPos != currentPos:
      targetPos의 행을
        nav_slot으로 가져옴
      외부 슬롯이 nav_slot을 가리키게 함
  result = eval_inner_expression()
  current_row_slot 복원
  by-ref 결과를 nav_slot에서 복사해 냄
  return result

트릭은 저장하고 복원할 슬롯이 정확히 하나라는 점이다. 내부 표현식 — 산술, 함수 호출, 다른 컬럼 참조 등 무엇이든 — 은 current row에 대해서와 같은 평가 경로를 사용해 교체된 슬롯에 대해 실행된다. 대체 평가기도, 참조마다의 슬롯도 없다. 대상이 현재 행이면 페치와 교환을 아예 건너뛴다. 페치는 대상 행을 navigation slot으로 복사하며(슬롯이 이미 그 행을 들고 있지 않은 한), 복원 단계는 pass-by-reference 결과를 per-tuple 메모리로 복사해 다음 페치가 그것을 해제하지 못하게 한다.

복합 내비게이션은 파싱 시점에 평탄화되어 교환이 여전히 한 번만 일어나도록 한다. PREV(FIRST(price))는 두 단계 내비게이션 — "첫 매치된 행으로 이동한 뒤 한 행 뒤로" — 으로 인식되어 복합 종류를 가진 단일 내비게이션 호출로 저장된다. 런타임은 대상 위치를 두 단계로 계산하지만 최종 행을 가져오기 위해 슬롯 교환은 한 번만 수행한다:

compute_target_position(call):

  # 현재 행 상대
  PREV(n):
      return currentPos − n
  NEXT(n):
      return currentPos + n

  # 매치 상대
  FIRST(n):
      return matchStart + n
  LAST(n):
      return currentPos − n

  # 복합: 매치 상대 후 추가 이동
  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 내부는 매치 범위,
   외부 단계는 파티션 범위)

같은 DEFINE 안의 여러 내비게이션 호출이 같은 행을 대상으로 할 때 위치 캐시가 tuplestore 페치를 단축한다 — price > PREV(price) AND volume > PREV(volume) 같은 표현식에서 두 호출이 모두 이전 행으로 해소되는 경우가 흔하다. 캐시는 "마지막 페치된 위치"만 저장하며, 교환 자체는 단일 연산으로 남는다.

내비게이션 호출의 분류는 absorption 결정에 대한 플래너의 기여이다. 플래너는 모든 DEFINE 표현식을 순회하며, 모든 컨텍스트가 같은 행에서 같은 불리언을 계산할지 또는 각 컨텍스트가 자기 것을 계산할지에 따라 각 변수를 두 버킷 중 하나로 분류한다. 버킷은 런타임에 두 가지를 결정한다. 변수가 얼마나 자주 평가되는지(공유로 한 번, 또는 영향받는 컨텍스트마다 한 번 — §3.5 Phase 1), 그리고 context absorption이 애초에 가능한지(§2.5 vs §2.6)이다. 매치 시작에 의존하는 변수가 하나라도 있으면 패턴 전체에 대해 absorption이 비활성화된다.

공유 평가 · absorption 안전 모든 컨텍스트가 모든 행에서 같은 불리언을 봄 — 같은 운명(§2.5).
  • 내비게이션 없음
  • PREV / NEXT만
  • 오프셋 없는 LAST
  • 내부 LAST(오프셋 없음)인 복합
컨텍스트별 평가 · absorption 안전하지 않음 매치 시작이 다른 컨텍스트들이 다른 답을 계산 — 다른 운명(§2.6).
  • 오프셋 있는 LAST
  • FIRST (임의 형태)
  • 내부 FIRST인 복합
  • 내부 LAST(오프셋 있음)인 복합

분류는 계획 시점에 수행되어 각 DEFINE 변수에 함께 저장되므로, 런타임은 분류 판정에 시간을 쓰지 않는다 — 행을 처리하면서 각 변수에 미리 붙은 분류 결과를 조회하기만 한다.

유지 범위

내비게이션은 윈도우 함수 메커니즘이 이미 스트리밍해 지나간 행들로 도달한다. 그 행들을 사용 가능하게 유지하기 위해 실행기는 최근 행들의 슬라이딩 윈도우를 보존하는 tuplestore 위에 자리한다. 문제는 그 윈도우가 얼마나 넓어야 하는가이다. 실행기는 두 가지 보완적 오프셋으로부터 이를 산출하며, 모든 오프셋을 스캔마다 한 번 해석한다(상수 오프셋은 executor init 시점에도 해석하여 일반 EXPLAIN이 보여줄 수 있게 한다):

Lookback 범위
어떤 DEFINE 호출이 현재 행에서 얼마나 뒤로 도달할 수 있는지.
발생 요인: PREV, LAST(기본값 0을 포함한 모든 오프셋), PREV(LAST(...)), NEXT(LAST(...))
Lookahead-from-start 범위
가장 오래된 살아있는 컨텍스트의 매치 시작으로부터의 최소 전방 도달(음수일 때 후방) — 어떤 DEFINE 호출이 필요로 할 수 있는 가장 이른 행.
발생 요인: FIRST, PREV(FIRST(...)), NEXT(FIRST(...))

런타임에 tuplestore의 trim mark는 두 위치 중 더 이른 것 — current row에서 lookback 범위를 뺀 위치와, 가장 오래된 살아있는 컨텍스트의 매치 시작에 lookahead 범위를 더한 위치 — 으로 설정된다. 그 마크 이전의 어떤 것도 어떤 살아있는 컨텍스트의 어떤 내비게이션 호출도 도달할 수 없으며, tuplestore는 자유롭게 버릴 수 있다. EXPLAIN이 보고하는(§3.7) Nav Mark 줄 — Lookback과 Lookahead — 은 이 두 범위 자체이며, 측정된 피크가 아니다. 각각은 어떤 내비게이션이 그것에 기여할 때만 출력되고, ANALYZE 없이도 표시된다. 값이 실행 시점에야 알려지는 오프셋(예를 들어 generic plan의 파라미터)은 일반 EXPLAIN에서는 runtime으로, EXPLAIN ANALYZE에서는 해석된 값으로 출력되며, retain all(Lookback) 또는 infinite(Lookahead)는 오버플로되는 오프셋을 나타낸다.

3.4 매치 경계 — SKIP, INITIAL, 한정 프레임

매치 결과는 두 값으로 기록된다. 매치가 시작되는 행과 그 길이이다. 음수 시작은 그 위치가 아직 평가되지 않았음을 뜻한다. 시작이 설정되면 실행기에 대한 후속 질의 — "이 행이 매치 안에 있는가?" — 는 그 쌍을 확인해 O(1)로 답할 수 있다. 길이가 결과를 인코딩한다. 매치되지 않은 행은 -1, 빈 매치는 0, 실제 매치는 행 수이다. 길이 0은 실제 결과이지 오류가 아니다. 행을 소비하지 않고 매치된 패턴을 나타내며, 실행기는 이를 매치되지 않은 행과도, "이 위치에서 아직 매치를 시도하지 않았다"와도 구분해야 한다.

AFTER MATCH SKIP 절은 다음 매치 시도가 어디서 시작될지 결정한다. AFTER MATCH SKIP PAST LAST ROW는 매치 끝 다음 행으로 이동하여 대부분 질의가 원하는 비중첩 출력을 산출하고 absorption 최적화를 활성화한다.

AFTER MATCH SKIP TO NEXT ROW는 매치 시작 다음 행으로만 이동하여 매치의 중첩을 허용한다. 따라서 플래너는 이 모드가 유효할 때 그 윈도우의 패턴에 대해 absorption을 비활성화한다.

표준이 정의하는 다른 두 skip 대상 — AFTER MATCH SKIP TO FIRST var와 AFTER MATCH SKIP TO LAST var — 는 이 패치가 유지하지 않는 매치별 히스토리에 의존한다. 문법에 전혀 존재하지 않으므로, 둘 중 어느 것이라도 제공되면 파서가 일반 구문 오류를 발생시킨다.

SEEK(스펙의 INITIAL 대안) 또한 마찬가지다. SEEK 하에서는 행 R에서 시작한 매치 시도가 R 자체뿐 아니라 R부터 프레임 끝까지 어디서든 성공할 수 있다. 패치는 INITIAL만 구현한다. 모든 잠재 매치는 특정 행에 고정된다. SEEK이 요청되면 파서는 오류를 낸다. 한정 프레임은 자체 처리를 받는다 — 사용자가 UNBOUNDED FOLLOWING 대신 ROWS BETWEEN CURRENT ROW AND N FOLLOWING을 작성할 때, 실행기는 매치가 경계에 도달한 어떤 컨텍스트든 강제 미스매치로 단축하며, 경계가 absorption이 의존하는 단조성 가정을 깨뜨리므로 absorption은 비활성화된다.

3.5 3단계 행별 엔진

실행기의 행별 드라이버는 주어진 행이 매치된 프레임에 속하는지 알아야 할 때마다 주변 윈도우 함수 메커니즘에 의해 호출된다. 드라이버는 현재 시작 위치에 대한 컨텍스트를 찾거나 생성한 뒤, 그 컨텍스트에 살아있는 상태가 남지 않거나 파티션이 끝날 때까지 NFA를 행 단위로 진행시킨다 — 각 행마다 변수별 매치 배열을 "미평가"로 초기화한다. DEFINE 술어는 지연 평가된다. 변수는 어떤 상태가 처음 그것을 소비할 때 평가되므로, 이 행에서 어떤 살아있는 상태도 검사하지 않는 변수는 결코 평가되지 않는다. 전진 단계 자체는 같은 외부 루프에 감싸인 고정된 순서의 세 단계 — Match, Absorb, Advance — 이다:

processRow(currentPos):

  # 1단계 — MATCH (수렴)
  for each context:
      if 컨텍스트가 프레임 끝에 도달:
          강제 미스매치 (조기 종료)
          continue
      if matchStartRow가 공유 평가
         위치와 다름:
          매치 시작 의존 DEFINE
          변수를 미평가로 초기화 (§3.3)
      match(context, varMatched)

  # 2단계 — ABSORB
  if 패턴이 absorbable:
      각 컨텍스트의 플래그 갱신
      absorb_contexts()

  # 3단계 — ADVANCE (발산)
  for each context:
      advance(context, currentPos)
      if 매치를 기록했고
         SKIP PAST LAST ROW:
          매치 안에서 시작한
          이후 컨텍스트 폐기

이 순서는 양식상의 선택이 아니다. Match가 먼저 실행되어야 하는 이유는 absorption이 매치 후 카운트를 비교하기 때문이다. Match 전에 Absorb를 실행하면 막 죽으려는 상태들을 비교하게 된다. Advance가 마지막에 실행되어야 하는 이유는 새로운 상태를 만드는 유일한 단계이기 때문이다 — 살아남은 모든 상태를 엡실론 전이로 확장해 각 상태가 다음 행을 기다리는 변수에 도달하게 한다. Advance 후 Absorb를 실행하면 발산한 후속들을 비교하게 되어, 상태들이 가장 깔끔하게 비교 가능한 지점을 놓치게 된다.

Phase 1 — Match

Match는 "수렴" 단계이다. 상태는 카운트가 증가한 채 살아남거나 사망한다. 흥미로운 점은 흡수 가능 영역에 있는 변수에 대해 Match가 약간의 전진도 수행하여 Absorb가 깔끔하게 비교할 수 있게 한다는 것이다. cover 조건은 흡수 가능 비교 지점 — 무한 그룹의 END — 에서만 발동한다. 따라서 반복 중간 변수((A B)+ 내부의 B 등)에 방금 매치한 상태들은 Match 자체에서 그 비교 지점까지 끌어올려야 한다. 그렇지 않으면 Absorb가 비교할 적격 상태를 찾지 못하고 최적화가 작동하지 않는다.

match(context, varMatched):
  for each state in context:
      elem = pattern[state.elemIdx]
      assert elem이 변수
          # advance는 변수에만 상태를 둔다

      if varMatched[elem.varId]가
         미평가:
          지금 DEFINE을 평가
      if not varMatched[elem.varId]:
          drop state   # 죽은 분기
          continue

      state.counts[elem.depth] += 1

      # 다음 단계가 반복 중간이 아닌
      # 비교 지점 요소에서 비교하도록
      # 인라인 전진 수행.
      if elem이 in-region이지만
         비교 지점이 아니고,
         max 카운트에 도달했으며,
         elem.next가 group end:

          END 체인 순회:
            외부 그룹 카운트 증가
            state.elemIdx를 END로 전진
            여전히 in-region이고,
              must-exit이며 next가 END인 동안 계속
          (비교 지점 또는 아직 루프 가능한
           요소에서 멈춤)

end-chain 순회는 중첩된 고정 길이 그룹을 흡수 가능하게 만드는 것이다. ((A B){2})+에서 B({1,1})가 max에 도달하면 내부 그룹의 카운트가 증가해야 하고, 그 카운트도 max에 도달해 내부 {2}를 닫으면 외부 그룹의 카운트도 증가해야 하고, 이렇게 상태가 가장 바깥 흡수 지점 — 무한 외부 그룹(+)의 END — 에 도달할 때까지 계속된다. 이 작업을 Match에서 수행하면 Absorb는 반복 후 카운트가 이미 통합된 컨텍스트들에 대해 비교할 수 있다.

Phase 2 — Absorb

absorb 패스는 컨텍스트를 가장 새것(tail)에서 가장 오래된 것(head)으로 순회한다. 완전히 흡수 가능한 진행 중 컨텍스트마다 그것을 덮는(cover) 더 오래된 진행 중 컨텍스트를 뒤로 스캔하고, 발견되면 새 것을 해제한다. 컨텍스트는 생성 순서로 유지되고 각 행은 최대 하나의 컨텍스트를 만들기 때문에, "새것"과 "오래된 것"은 실제로 "더 늦게 시작"과 "더 일찍 시작"을 의미한다.

absorb_contexts():
  for ctx from tail backward:
      if ctx가 종료됐거나
         non-absorbable 상태가 하나라도 있거나
         기록된 매치를 들고 있음:
          skip
      for older from ctx.prev backward:
          if older가 종료됐거나
             absorbable 상태가 없음:
              skip
          if covered(older, ctx):
              free(ctx)
              absorption 길이 기록
              break

covered(older, newer):
  for each state in newer:
      elem = pattern[state.elemIdx]
      if elem이 비교 지점이 아님:
          return false
      if older에 다음 조건의 상태가 없음:
            같은 elemIdx
            그리고 isAbsorbable
            그리고 older.counts[depth]
                >= newer.counts[depth]:
          return false
  return true

이로부터 두 가지 미세 결정이 따라온다. 첫째, cover 검사는 새 컨텍스트의 어떤 상태든 비교 지점이 아닌 곳에 있으면 즉시 거부한다 — 판정이 아닌 지점에서 비교하면 의미 있는 비교가 되지 않는다.

둘째, 각 컨텍스트의 비대칭 플래그 쌍이다. has-absorbable-state는 "이 컨텍스트가 새 것을 흡수할 수 있는가?"에 답하는 플래그로, 단조적이다(상태가 죽으면서 true→false로만 갈 수 있음). 반면 all-states-absorbable은 "이 컨텍스트가 흡수될 수 있는가?"에 답하는 플래그로, 동적이다(흡수 불가 상태가 제거되면 true로 되돌아감). 단, 컨텍스트가 매치를 기록하면 false로 고정된다 — 흡수하면 어떤 흡수 컨텍스트도 재현할 수 없는 매치를 해제하게 되기 때문이다. 두 플래그 모두 cover 스캔이 시작되기 전에 상수 시간에 검사되므로, absorption은 실제로 흡수될 가능성이 있는 컨텍스트에 대해서만 전체 비용을 지불한다.

Phase 3 — Advance

Advance는 "발산" 단계이다. 살아남은 각 상태는 모든 분기가 다음 행을 기다리는 변수 또는 FIN 센티널에 도달할 때까지 엡실론 전이로 확장된다. 확장은 깊이 우선이며, 형제 분기가 순회되는 순서가 표준의 선호 규칙을 실제로 작동시킨다 — 어휘적으로 가장 앞선 분기가 항상 먼저 추가되고, 상태 삽입 시의 중복 제거 단계가 동등한 나중 추가를 조용히 폐기한다.

advance(context, currentPos):
  현재 상태들을 모두 빼낸 뒤
  ctx.states를 처음부터 다시 구성
  for each state in lexical order:
      방문 비트맵 초기화
      advance_state(state)   # DFS

      # 선호 우선: DFS가 FIN에 도달하면
      # 남은 상태들은 덜 선호되므로
      # 폐기 가능.
      if FIN 도달 및 남은 상태 있음:
          나머지 free
          break

advance_state(state):
  state.elemIdx로 순회,
  다음을 통해 재귀:
    ALT 분기 (순서대로, FIN이
              기록되면 중단),
    BEGIN (그룹 진입; min = 0이면
           선택적 건너뛰기 경로 추가),
    END (루프백 / 종료 / fast-forward —
         아래 참조),
    FIN (matchEndRow 기록,
         matchedState 저장, 그리고
         이 후보 범위 안의 이후
         컨텍스트들이 폐기되도록
         컨텍스트에 표시 — 아래 참조),
  변수를 만날 때마다 멈춤:
      state를 ctx.states에 추가
      (elemIdx + counts로 중복 제거)

FIN에 도달한 상태를 기록하는 것은 단순히 후보 매치를 표시해두는 것 이상이다. AFTER MATCH SKIP PAST LAST ROW 하에서는 다음 보고 가능한 매치는 현재 것 다음에서 엄격하게 시작해야 하므로, 후보를 기록한 컨텍스트에 대해 Advance가 끝나면, 시작 행이 후보 범위 안에 있는 모든 후속 컨텍스트는 같은 행에서 폐기된다 — FIN에 도달한 컨텍스트는 greedy fallback으로 더 긴 매치를 계속 찾을 수 있더라도.

이 가지치기가 안전한 이유는 그 탐색이 어떻게 끝나든(긴 매치가 후보를 대체하거나 후보가 유지되거나) 폐기된 모든 컨텍스트는 다음 보고 가능한 매치가 건너뛰어야 하는 범위 안에서 시작했으므로 자체 출력을 결코 낼 수 없기 때문이다.

이것이 컨텍스트 간 FIN-time 가지치기 단계이다. 컨텍스트 안에서도 FIN은 어휘적으로 열등한 작업을 잘라낸다. Advance는 대기 중인 나머지 상태들을 폐기하고(이 절 앞부분에서 설명), 하나의 DFS 안에서는 덜 선호되는 모든 경로 — 뒤쪽 ALT 분기, BEGIN의 건너뛰기/진입 경로 중 다른 쪽, reluctant 변수의 진입 경로, END의 루프/종료 경로 중 다른 쪽 — 가 매치가 기록되면 멈추므로, 한 번의 advance는 최대 하나의 매치만 기록한다.

가장 까다로운 요소별 로직은 END 핸들러에 있다. 그룹의 반복 카운트가 하한 미만이면 런타임은 loop back해야 한다. 상한에 있거나 그 이상이면 종료해야 한다. 그 사이에서는 두 옵션 모두 유효하며, 수량자의 greediness가 어느 것을 먼저 시도할지 결정한다:

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

  if count < elem.min:
      본체로 루프백
      if elem이 empty-loopable:
          # nullable 본체, §3.2 참조
          그룹을 빠져나가는
          fast-forward 상태도 복제
          (count 충족 처리)
          (본체가 빈 매치를 선호하면
           fast-forward 먼저. 첫 경로가
           FIN에 도달하면 두 번째
           경로는 폐기)

  elif count >= elem.max:
      이 깊이의 counts 초기화
      next로 종료
      (END→END: 외부 END의
       count 증가)

  else:
      # min <= count < max: 분기
      종료 상태 생성
      (이 깊이의 counts 초기화)
      if greedy:
          루프 먼저
          if 루프 후 FIN 도달:
              종료 폐기
              # 긴 것 선호
          else 종료를 두 번째로
      else (reluctant):
          종료 먼저
          if 종료 후 FIN 도달:
              루프 폐기
              # 짧은 것 선호
          else 루프 후속

컨텍스트에 추가되는 모든 상태는 자신의 위치와 카운트를 기존 상태 목록과 비교하는 중복 제거 검사를 거친다. Advance가 분기를 DFS 순서로 처리하기 때문에 어떤 alternation의 첫 분기에서 온 상태가 먼저 자리잡고, 같은 위치와 카운트를 산출하는 나중 분기는 삽입 시 거부된다. 이것이 정확히 §2.4의 어휘 순서 규칙이 요구하는 것이며, 별도 패스 없이 런타임 바닥에서 구현된다.

빈 루프 가능 그룹

런타임이 다뤄야 하는 미묘한 경우가 nullable 그룹이다 — 본체의 모든 자식이 선택적이라, 본체가 한 행도 소비하지 않고 반복을 끝낼 수 있는 그룹. (A? B?)+, (A | B*)+ 같은 패턴이 이런 성질을 가진다. 데이터에 따라서는 본체가 행을 전혀 소비하지 않고 한 번의 반복을 마칠 수 있다. ((A?)*처럼 선택적 자식이 하나뿐인 경우는 컴파일 타임에 A*로 재작성되어 그룹이 남지 않는다.) 원칙적으로는 문제가 없지만 NFA의 엡실론 확장에서는 실제 위험이 된다. 본체가 빈 매치를 내면 END가 본체로 되돌아가고(그 jump는 그룹의 첫 자식이다), 본체가 다시 빈 매치를 내고, 다시 END에 도달하고… 이를 멈추는 장치가 없으면 Advance의 DFS는 끝나지 않는다.

이 guard는 컴파일 타임에 결정되어 런타임에 발동된다. 플래너는 본체가 nullable인 그룹을 만날 때마다 그 그룹의 END 요소에 empty-loopable 태그를 단다. 런타임은 각 상태의 DFS 확장 전에 클리어되는 방문 비트맵을 유지하며, 거기에는 태그가 달린 END만 표시된다 — 다른 루프백은 모두 행을 소비했으므로 그 밖의 어떤 것도 순환할 수 없다. 표시된 END에 도달했다는 것은 본체가 방금 빈 반복을 도출했다는 뜻이며, 상태는 폐기되지 않는다. 하한 이상이면 거기서 그룹을 떠나고(빈 반복은 수량자를 멈춘다), 하한 미만이면 정상 loop-back으로 넘어가므로, 빈 도착마다 여전히 카운트가 올라 min에 도달한다. 행 스트림 어디서도 두 변수 모두 매치되지 않는 (A? B?){2,3}를 보자:

iter 1: A? B?가 0행 매치
        → END, count = 1 (min 미만)
        END는 (그룹 진입 시) 이미 표시됨,
        그러나 min 미만:
        → A?로 loop back
iter 2: A? B?가 0행 매치
        → END, count = 2 (min 충족)
        END 이미 표시됨, min 도달:
        → 그룹을 떠남
길이 0 매치로 종료

하한 미만에서는 empty-loop 태그가 END 핸들러에게 정상 loop-back 경로와 함께 추가 fast-forward 상태도 복제하도록 지시한다:

advance_end (count가 min 미만):

  loop-back 경로:
    본체로 loop back
    (다음 반복에서 실제 비어있지 않은
     매치가 가능하도록 길을 열어둠)

  if elem이 empty-loopable:
    fast-forward 경로:
      이 깊이의 count 초기화
      next로 그룹 종료,
      남은 필수 반복을
      빈 매치로 처리

두 경로는 서로 보완한다. loop-back은 본체가 이후에 실제 매치를 만들 경우를 처리한다 — 예컨대 (A? B?){2,3} 뒤에 A가 늦은 행에서만 매치되는 데이터가 따라올 때, loop-back 덕분에 두 번째·세 번째 반복이 비어있지 않은 매치를 찾을 수 있다. fast-forward는 곧바로 그룹을 빠져나가, "남은 필요 반복은 모두 비어 있다"고 선언해 길이 0 본체로 매치를 성립시킨다. 순서는 그룹 자체의 greed가 아니라 본체가 결정한다. 본체가 빈 매치를 선호할 때((A?? B??) 같은 reluctant 본체) 정확히 그때 fast-forward가 먼저 가고, 첫 경로가 FIN에 도달하면 두 번째는 폐기되므로, 덜 선호되는 경로가 선호되는 매치를 대체할 수 없다. 삽입 시 중복 제거 검사가 어느 쪽도 자기 몫 이상의 상태를 만들지 못하게 막는다.

cycle guard 외에 시작 시점의 또 다른 트릭이 컨텍스트 시작에서 0-행 결과를 모호하지 않게 만든다. 모든 잠재 시작 행에서 컨텍스트 생성 단계는 어떤 행도 소비하기 전에 엡실론 전이를 통해 초기 advance를 실행한다. 실제 시작보다 한 행 앞 위치를 사용하여. 따라서 행을 소비하지 않고 엡실론 전이만으로 FIN 센티널에 도달한 모든 경로는 시작 위치보다 작은 끝 위치를 산출한다. 그 음수 스팬 좌표는 FIN이 실제로 도달되었는지와 결합되어, 별도 플래그 없이 빈 매치(길이 0 매치 수용)와 매치되지 않은 시작의 차이를 인코딩한다.

3.6 상태 공간이 한정된 채 유지되는 방법

런타임을 한정된 채 유지하는 것은 단일 최적화의 결과가 아니다. 행별 사이클의 서로 다른 지점에서 상태 공간 증가의 서로 다른 원인을 잡는, 계층화된 가지치기 규칙들의 누적 효과이다. 일부는 컴파일 타임에 결정되어 런타임에 단지 참조되며, 다른 일부는 동적으로 발동한다. 일부는 개별 상태를 죽이고, 다른 일부는 전체 컨텍스트를 죽인다. 위의 절들은 각각을 맥락 안에서 소개했다. 아래 표는 이를 한 페이지에 모은다.

술어 실패 Match
현재 행에서 DEFINE이 거짓으로 평가된 변수 상태 — 죽은 분기.
인라인 end-chain advance Match
최대 카운트에 도달했지만 그렇지 않으면 상태를 반복 중간에 두게 될 변수. absorption이 올바른 지점에서 비교할 수 있도록 고정 길이 group end를 통해 진행됨.
Context absorption Absorb
모든 상태가 비교 지점에 있고, 오래된 컨텍스트의 같은 요소에 있는 흡수 가능 상태 중 카운트가 크거나 같은 것에 의해 덮이는 새 컨텍스트 — 개념 규칙은 §2.5, 컴파일 타임 자격은 §3.2, 쌍별 검사는 §3.5 참조.
상태 중복 제거 Advance
다른 DFS 분기를 통해 도달한 상태들이 같은 위치, 같은 카운트로 끝날 때 — 첫(어휘적으로 가장 앞선) 것만 살아남고 이후 동등물은 조용히 폐기. 이것이 또한 선호가 강제되는 방식이다(§2.4).
FIN 조기 종료(컨텍스트 내) Advance
한 분기가 FIN에 도달했을 때 DFS 큐에서 여전히 보류 중인 상태들 — 어휘 순서에 따라 모든 남은 상태들은 덜 선호되며 즉시 폐기 가능.
후보 매치 가지치기(컨텍스트 간) Advance
시작 행이 후보 매치 범위 안에 있는 다른 컨텍스트들 — FIN에 도달한 컨텍스트는 더 긴 매치를 계속 찾을 수 있지만(greedy fallback), AFTER MATCH SKIP PAST LAST ROW 하에서는 후보 범위 안의 어떤 컨텍스트도 그 탐색 결과와 무관하게 더 이상 보고 가능한 출력을 낼 수 없으므로, 후보를 기록한 컨텍스트에 대해 Advance가 끝나는 즉시 폐기.
Cycle guard Advance
같은 DFS 안에서 이미 표시된(BEGIN을 통한 진입 시, 또는 앞선 도착 시 표시) nullable 그룹의 END에 도달하는 엡실론 확장 — 그렇지 않으면 영원히 루프. 하한 이상이면 상태는 거기서 그룹을 떠나고, 하한 미만이면 계속 루프한다.
Empty-loop fast-forward Advance
nullable 그룹의 하한 미만에서, 남은 필요 반복을 빈 것으로 선언하고 그룹을 빠져나가는 추가 경로. 본체의 선호에 따라 loop-back과의 순서가 정해진다.
한정 프레임 컷오프 Match
매치가 사용자 지정 프레임 상한에 도달한 컨텍스트 — 이를 넘어 확장할 수 없도록 강제 mismatch(§3.4).

위 항목들을 단계별로 묶어 읽으면 컨텍스트의 생애가 추적된다. 가지치기는 세 주요 단계(Match, Absorb, Advance)를 통해 모든 행에서 발동한다. 대신 설명으로 읽으면 규칙들이 무엇을 겨냥하는지로 그룹화된다. 죽은 분기, 중복 컨텍스트, 동등한 상태, 무한 루프, 사용자가 부과한 경계를 넘는 과도한 확장.

어떤 단일 규칙도 그 자체로 충분하지 않다. empty-loop fast-forward만으로는 무한 엡실론 루프를 멈추지 못할 것이며, absorption만으로는 DEFINE이 매치 시작을 참조할 때 과도하게 통합할 것이고, 중복 제거만으로는 중복된 컨텍스트가 아닌 중복된 상태만 제거할 것이다. 런타임이 중요한 경우 — 100,000행에서의 PATTERN (A+ B+ C+ D), 포스터 패널 ③ 벤치마크 — 에 선형으로 유지되는 이유는 모든 계층이 위 계층이 놓친 것을 잡기 때문이다. 소스는 계층들이 잡지 못하는 경우도 문서화한다. 중복 제거는 min 이상에서 카운트만 다른 상태들을 구별해 유지하므로, C가 결코 참이 아닌 (A{2,} B)+ C는 피크에 Θ(n²)개의 상태를 들고 누적으로 Θ(n³)개를 생성하며(320행에 37초), 모두 nullable한 대안이 연속되면 경로 하나하나가 열거되므로 (A?|B?){30}은 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 줄은 둘 중 하나라도
   0이 아닐 때만. 0인 카운트는
   (len ...) 없이 출력)

텍스트가 아닌 형식은 모든 카운트를 개별 속성으로 방출한다. Peak과 total은 런타임의 직접 계측이다. 동시에 살아있던 상태가 몇 개였는지, 질의 수명 동안 몇 개가 생성되었는지, 중복 제거로 얼마나 많이 병합되었는지. pruned는 한 행 만에 실패한 컨텍스트를 센다. 매치 길이 히스토그램은 네 가지 결과 — 성공한 매치, 두 행 이상 진행한 뒤 실패한 매치 시도(mismatched), 흡수된 컨텍스트, 기록된 매치 안에서 시작했기 때문에 AFTER MATCH SKIP PAST LAST ROW로 해제된 컨텍스트(skipped) — 를 분리하고 min/max/avg로 보고하여 성능 병리를 한눈에 보이게 한다. 건강한 실행은 대부분 컨텍스트가 매치 또는 흡수로 나타나며 mismatched 길이는 작다.

두 Nav Mark 카운터는 §3.3이 DEFINE으로부터 도출하는 tuplestore 유지 범위를 보고한다. Lookback은 PREV, 모든 오프셋(기본값 0 포함)의 LAST, 내부 LAST가 있는 복합 형태에 걸친, 현재 행으로부터의 가장 깊은 후방 도달이다. Lookahead는 가장 오래된 살아있는 컨텍스트의 매치 시작에서 측정된 최소 전방 도달(매치 시작 이전을 볼 때는 음수)로, FIRST와 내부 FIRST가 있는 복합 형태가 기여한다.

각 카운터는 오프셋이 상수일 때 고정 정수로, 스캔마다에야 알려지는 비상수 표현식일 때 "runtime"으로, 그리고 — Lookback에 한해 — 오프셋이 오버플로될 때 "retain all"로 출력된다. 오버플로되는 Lookahead는 "infinite"로 출력된다. 각 줄은 DEFINE의 어떤 내비게이션이 그것에 기여할 때만 방출되며, 둘 다 일반 EXPLAIN에서도 나타난다. 상수 오프셋은 executor init 시점에 확정되고, 실행 시점에야 알려지는 오프셋(예를 들어 generic plan의 파라미터)은 거기서 "runtime"으로, EXPLAIN ANALYZE에서는 해석된 정수로 출력된다.

이 카운터들은 함께 백엔드에 gdb를 붙이지 않고도 RPR 성능을 디버깅 가능하게 만든다.

카운터 외에도 EXPLAIN은 컴파일된 요소 배열로부터 만든 Pattern: 줄을 출력하므로, 컴파일 타임 재작성 이후의 패턴을 보여주고(PATTERN (A A)는 a{2}로 표시된다) absorption 마커 #(비교 지점)와 ~(흡수 가능 영역)를 달고 있다. DEFINE과 AFTER MATCH SKIP 옵션은 표시되지 않는다. reluctant 수량자, 그룹 반복, skip 옵션을 포함해 작성된 그대로 절을 재현하는 것은 pg_get_viewdef()의 일이며, 이 함수는 round-trip을 안정적으로 만들기 위해 상당한 노력을 기울여, pg_dump와 pg_upgrade가 의미 변형 없이 RPR 객체를 보존할 수 있게 한다 — rpr_explain의 회귀 테스트가 이를 사례별로 검증한다(§4 참조).

§4. 테스트 — 커버리지 맵

이 패치는 §3에서 설명한 모든 계층을 함께 검사하는 다섯 개의 회귀 테스트 스위트와 함께 제공된다 — 대략 22,000줄의 SQL이며, 각 스위트는 서로 다른 관심사에 집중되어 있다. 분리는 의도적이다. 파서 관심사, 런타임 정확성, 플래너 상호작용, 출력 포맷팅을 별도 파일에 두면 실패를 지역화하기 쉽고, 한 계층의 무관한 변경이 다른 계층의 테스트를 우연히 무효화하는 것을 방지한다. 다섯 스위트는 다음과 같다:

rpr
WINDOW 절 통합 — 합성 주가 데이터에 대한 현실적인 윈도우 시나리오(V형, W형, 연속 상승, 반전), 그리고 내비게이션 시맨틱과 DEFINE 제약 오류.
rpr_base
파서 계층 — 키워드 수용, 구문 형태, 수량자, 내비게이션 파싱, 오류 메시지, pg_dump/pg_upgrade round-trip 안정성. 그리고 플래너 계층 — 패턴 최적화, absorption 플래그, 최적화 fallback, 플래너 통합.
rpr_nfa
NFA 런타임 — 3단계 루프, 모든 흡수 가능 형태에서의 흡수, 컨텍스트 생애 엣지 케이스.
rpr_explain
출력 포맷팅 — NFA 통계, 패턴 deparse, 식별자 인용, 재로드 간 포맷 안정성.
rpr_integration
플래너 상호작용 — 무관한 윈도우 최적화가 RPR 시맨틱을 손상시키지 않도록 하는 가드.

4.1 rpr — end-to-end 시나리오

시나리오 스위트는 테스트 세트의 공식 얼굴이다. 약 1,600행의 합성 주가 데이터셋을 사용해 현실적인 질의를 실행한다 — V형 회복, W형(이중 바닥), 연속 상승과 하락, 반전 패턴, 다중 심볼 파티션. 이 시나리오들은 입력과 출력이 사용자가 실제로 작성할 만한 질의처럼 읽히는 유일한 테스트이다. 파일의 나머지는 다른 스위트들처럼 환원적이다 — PREV/NEXT 중첩과 비상수 오프셋 오류, DEFINE 참조 규칙, 내비게이션 오프셋 시맨틱.

이 질의들이 모든 계층(파서, 플래너, 실행기, EXPLAIN)을 결합하기 때문에 rpr에서의 단일 실패는 버그가 어디 있는지 잘 알려주지 않는다. 뒤따르는 네 스위트가 이등분(bisection)이다. rpr 실패와 rpr_base 통과는 파서를 배제하고, rpr_nfa 통과 추가로는 시나리오 특정 데이터 형태로 좁혀지며, rpr_integration 통과로는 플래너 간섭이 배제되고, 어떤 deparse drift든 rpr_explain에 나타난다.

4.2 rpr_base — 파서 표면

base 스위트가 가장 크며, 그럴 만한 이유가 있다. §1.2의 모든 합법적 구문 조각이 실제로 파싱되고, §1.3의 모든 불법적 조각이 유용한 오류로 거부되며, 수용된 모든 형태가 직렬화 round trip을 견딘다는 것을 증명할 책임이 있기 때문이다. 대부분이 길고 현실적인 질의가 아니라 작고 집중된 스니펫(구문 기능당 하나)으로 이루어져 있다. 목표가 시나리오 현실성이 아닌 커버리지이기 때문이다. 두 번째 부분인 플래너 계층은 패턴 최적화, absorption 플래그 표시와 분석, 최적화 fallback, 플래너 통합(서브쿼리, 조인, 집합 연산, 정렬과 그룹화)을 다룬다.

직렬화 테스트는 특별한 주의가 필요하다. RPR 객체(뷰, 구체화 뷰, pg_dump 출력)는 카탈로그 표현을 거친 round-trip 후에도 의미가 어긋나면 안 된다 — 수량자의 reluctant 플래그나 복합 내비게이션 표현식의 정확한 형태 같은 세부까지 모두 보존되어야 한다. 이를 검증하기 위해 직렬화 전용 객체 한 묶음(rpr_serial_v* 뷰와 그 backing 테이블)을 일부러 실행 끝까지 남겨둔다. 그러면 주변 회귀 인프라가 이를 집어 pg_dump와 pg_upgrade를 검증할 수 있다. 나머지 테스트 보조 객체는 평소처럼 정리된다. deparse 후 다시 파싱하는 과정에서 reluctant 플래그가 사라지는 것 같은 결함은 round-trip을 end-to-end로 돌려봐야만 드러난다.

4.3 rpr_nfa — 런타임 엔진

이 스위트는 §3.5와 §3.6에서 설명된 모든 메커니즘을 검사한다. 테스트는 일관된 패턴을 따른다. 각 행에서 어떤 DEFINE 변수가 매치되는지 선언하는 변수명 배열을 담은 인라인 VALUES 행과, 특정 런타임 동작을 탐사하는 패턴의 짝이다. 배열 관용구는 런타임 테스트를 DEFINE 평가 메커니즘으로부터 분리한다 — 테스트되는 것은 "이 변수들이 여기서 매치된다고 할 때 NFA 루프가 예상 매치 구간을 산출하는가?"이지 "DEFINE 표현식 평가기가 이 불리언들을 올바르게 계산하는가?"가 아니다. DEFINE 평가기는 다른 곳에서 테스트된다(파싱은 rpr_base, end-to-end 동작은 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-leg에서 B-leg로 전환할지에 대해 실제 선택을 가진다. 예상 매치(표준의 greedy 선호 하에서 행 1–3의 A 다음에 행 4의 B)는 그 플래그들만으로 고정되며, 여기서는 어떤 결과적인 표현식 평가도 개입하지 않는다 — = ANY는 배열 컬럼을 DEFINE에 노출하는 사소한 계층일 뿐, 테스트가 검사하는 것이 아니다. 같은 시나리오를 숫자 술어(price > PREV(price) 등)로 작성하면 NFA 테스트가 술어 평가기의 동작과 얽히게 된다. 배열 관용구는 둘을 깔끔하게 분리하며, 여기서의 실패는 NFA 루프를 직접 가리킨다.

absorption 커버리지가 특히 철저하다. absorption은 작동해서는 안 될 때 작동하면 조용히 잘못된 답을 산출할 가능성이 가장 높은 최적화이기 때문이다. 테스트는 §3.2의 사례 분석에서 나온 모든 형태를 다룬다:

absorption 외에 스위트는 컨텍스트 생애를 다룬다. AFTER MATCH SKIP TO NEXT ROW 하의 중첩 컨텍스트, 스트림 중간의 실패 컨텍스트 정리, 미완료 컨텍스트의 파티션 끝 확정, 헤드 컨텍스트에서 후보 매치가 이미 기록된 후 만나는 컨텍스트들. 이들 각각은 §3.6의 특정 가지치기 규칙에 매핑되며, 테스트는 규칙이 잘못 발동(중복 컨텍스트를 살려두거나 출력을 내야 했던 컨텍스트를 죽이거나)하면 큰 소리로 실패하도록 작성되어 있다.

4.4 rpr_explain — 출력 안정성

EXPLAIN 출력은 사용자 대면 인터페이스의 일부이다 — 서드 파티 도구(모니터링 대시보드, 로그 스크레이퍼)가 파싱하며, 겉보기에 사소한 변경도 그 도구들을 망가뜨릴 수 있다. rpr_explain 스위트는 세 가지를 검증한다:

rpr_base처럼 이 스위트도 의도적으로 객체를 실행 끝에 그대로 두어 pg_dump와 pg_upgrade 커버리지가 explain 측 아티팩트까지 확장된다.

4.5 rpr_integration — 플래너 상호작용

PostgreSQL의 플래너는 윈도우 질의에서 작동하는 많은 최적화를 가진다 — 프레임 정규화, run-condition pushdown, 동일 윈도우 중복 제거, 미사용 출력 투영, 이동 집계 inverse 전이 — 그리고 각 최적화는 RPR을 염두에 두지 않고 설계되었다. 그중 대부분은 윈도우에 PATTERN 절이 있을 때 적용하기에 안전하지 않다. 프레임은 매치 계약의 일부이고, 매치된 출력은 더 이상 어떤 명백한 방식으로도 단조롭지 않으며, 같은 사양이지만 다른 DEFINE을 가진 두 윈도우는 진정으로 다른 결과를 산출한다. integration 스위트는 이 최적화들 각각이 RPR 윈도우를 어떻게 다루는지 검증한다 — 대부분은 비활성화되거나 우회되어야 한다:

프레임 정규화
플래너는 보통 row_number, rank, ntile 같은 프레임 무관 윈도우 함수에 대해 ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING을 ROWS UNBOUNDED PRECEDING으로 재작성. RPR의 프레임은 매치 구간이지 집계 윈도우가 아니므로 그대로 유지되어야 함.
Run-condition pushdown
윈도우 함수 출력에 대한 단조 WHERE 필터는 보통 정지 조건으로 윈도우 연산자에 push 가능. RPR에서는 이것이 패턴 매칭을 조기 종료시켜 확장 중인 매치를 잘라낼 수 있음.
윈도우 중복 제거(RPR vs 비-RPR)
같은 ORDER BY와 프레임을 가진 두 윈도우는 보통 하나로 병합. RPR 윈도우와 비-RPR 윈도우는 RPR 측이 매치 결과를 들고 있어 결코 상태를 공유할 수 없음.
윈도우 중복 제거(다른 DEFINE 또는 SKIP)
같은 PATTERN이지만 다른 DEFINE 절이나 다른 AFTER MATCH SKIP을 가진 두 RPR 윈도우는 다른 매치를 산출하므로 구조적 형태가 동일하더라도 별개로 유지되어야 함.
미사용 출력 투영
이 최적화는 적용이 허용됨. 외부 질의가 윈도우의 출력을 결코 읽지 않으면 윈도우 함수는 NULL이 되고 그 WindowAgg는 제거되며, 행 수는 변하지 않음. 테스트는 WindowAgg가 남을 때 DEFINE이 읽는 컬럼이 여전히 WindowAgg에 도달하는지, 그리고 값이 읽힐 때 윈도우가 유지되는지 검사.
이동 집계 inverse 전이
inverse 전이 함수가 있는 윈도우 집계는 보통 프레임이 이동함에 따라 점진적으로 평가 가능. RPR의 reduced frame은 슬라이딩 윈도우가 아니며, inverse 전이 경로는 잘못된 결과를 낼 것임.

추가 사례들은 비용 추정이 DEFINE을 반영하는지, RPR 윈도우를 담은 서브쿼리가 평탄화되지 않는지, DEFINE 표현식이 상위 WindowAgg로 새어 나가지 않는지, LIMIT이 WindowAgg 위에 머무는지 검사한다. 두 번째 그룹은 CTE, 조인, 집합 연산, prepared statement, 파티션 테이블 및 유사 구문과 함께 RPR을 실행한다. 가드가 걸린 사례 대부분은 같은 형태를 따른다. 최적화를 트리거하는 베이스라인(보통 비-RPR 질의, EXPLAIN으로 확인) 다음에, 최적화가 적용되지 않는 구조적으로 유사한 형태의 RPR 질의가 온다 — DEFINE/SKIP 중복 제거 사례의 베이스라인은 동일한 두 RPR 윈도우이고, inverse 전이 사례는 EXPLAIN 대신 로깅 집계로 우회를 검사한다. 두 절반이 함께 플래너의 가드가 모든 질의에 조용히 도장만 찍는 것이 아니라 실제 작업을 하고 있음을 증명한다.

이 스위트는 또한 §3.4가 짧은 이유이다. "매치 경계" 메커니즘 — reduced frame, SKIP, INITIAL, 한정 프레임 컷오프 — 은 다른 곳에서 운영적으로 테스트된다. rpr_integration이 검증하는 것은 다른 어떤 옵티마이저 단계도 지나는 도중에 이를 건드리지 않는다는 것이다. rpr_integration의 통과는 다른 스위트들이 자신의 입력이 손상되지 않은 채 실행기에 도달한다고 신뢰할 수 있게 해준다.