Row Pattern Recognition 심층 분석

§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 사양 안에 접어 넣어 윈도우 함수 출력을 만드는 형태이다. 두 표면은 문법 대부분과 시맨틱 전체를 공유하지만 기능적으로는 별개의 진입점이며 — 데이터베이스는 둘 중 하나 또는 둘 다를 구현할 수 있다.

여기서 논의하는 패치 시리즈는 R020만의 부분 집합을 구현하며, 테이블-절 형태는 의도적으로 범위 밖이다.

R020 표면은 작지만 표현력이 풍부하다. 질의는 윈도우 사양 안에 세 가지 절을 추가하여 패턴을 윈도우에 부착한다. PATTERN은 명명된 패턴 변수들에 대한 정규식을 기술하고, DEFINE은 각 변수를 식별하는 불리언 술어를 공급하며, AFTER MATCH SKIP은 파티션 내에서 연속된 매치가 어떻게 배치되는지 제어한다.

선택적인 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을 정의한다.

정규식: + * ? |

표준 수량자와 대안(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)) — 내부와 외부 스텝 각각 자체 오프셋을 가질 수 있다.

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 label, AFTER MATCH SKIP TO FIRST var, AFTER MATCH SKIP TO LAST var가 여기 해당한다. 이들 또한 매치 히스토리에 의존하는데, 실행기가 가장 최근 매치 안의 특정 레이블 붙은 행을 가리킬 수 있어야 하기 때문이다.

나머지는 이질적인 잔여 항목들이다. SEEK 키워드(INITIAL의 대안), 빈 패턴 (), 제외(exclusion) 형태 {- … -}, 그리고 순서 무관 연산자 PERMUTE이다.

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 label

레이블이 지정된 행으로 skip.

AFTER MATCH SKIP TO FIRST var

해당 변수로 매치된 첫 행으로 skip.

AFTER MATCH SKIP TO LAST var

해당 변수로 매치된 마지막 행으로 skip.

정규식: {- -}

제외(exclusion) — 매치된 행을 매치별 출력에서 제거.

정규식: ()

빈 패턴 — 빈 시퀀스에 매치.

PERMUTE(...)

나열된 변수들에 대한 순서 무관 매칭.

DEFINE의 집계 함수

SUM, AVG, COUNT 같은 집계 함수는 DEFINE 술어에 사용할 수 없다. 표준은 부분 매치에 대한 running 집계(어떤 변수로 이미 매핑된 행들에 대한 행별 평가)를 허용하지만, 이는 MEASURES/CLASSIFIER()가 요구하는 것과 동일한 매치 히스토리에 의존한다.

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

첫째, 패턴 앵커 ^와 $는 표준 자체가 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 변수를 참조할 수 없고, RPR은 재귀 질의 내부에서 사용될 수 없다.

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

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

이 절의 예제들은 점진적으로 쌓아 올린다. 먼저 row pattern matching이 문자열 패턴 매칭과 본질적으로 다른 개념적 이유에서 시작해, DEFINE 조건을 흥미롭게 만드는 네 가지 내비게이션 함수를 소개하고, 마지막으로 세 가지 end-to-end 추적을 따라간다. 단일 매치(NFA 이동), 단순한 경우의 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는 파티션 행마다 하나가 아닌 여러 동시 상태를 들고 있어야 한다.

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

2.2 내비게이션 함수

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

PREV(expr [, n])

현재 행의 n행 앞 행(기본값 n = 1). "오늘 vs 어제" 비교에 사용.

NEXT(expr [, n])

현재 행의 n행 뒤 행. 전방 lookahead. 윈도우 형태에서는 윈도우가 단조롭기 때문에 흔치 않다.

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 변형은 매치 경계 기준이어서 context absorption과 상호작용한다. 그 결과 플래너가 그렇지 않았다면 버렸을 일부 컨텍스트를 살려 두게 만든다. 이 상호작용의 메커니즘은 §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)
);

패턴은 네 개 요소로 평탄화된다:

[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에 대해:

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

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

행 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이 결판을 낼 때까지 병렬로 진행한다.

두 분기는 같은 행들에서 같은 길이의 매치를 만들어내, 매처에는 두 후보 경로 — UP, DONE 라벨과 HIGH, DONE 라벨 — 가 남는다. 표준은 이를 어휘 순서(lexical order)로 결정한다. (UP | HIGH)에 작성된 대안 중 먼저 쓰인 쪽이 매치 길이와 무관하게 이긴다. UP이 HIGH보다 앞에 있으므로 살아남는 경로는 UP, DONE이다.

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

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). 그리고 실행기는 투기적으로 수요일에 시작되는 C2도 추적한다. 각 행의 RISE 조건은 그 행의 가격을 직전 행의 가격과 비교한다 — 이는 파티션 수준의 사실이지 컨텍스트 수준의 사실이 아니다 — 따라서 두 컨텍스트는 공유하는 모든 행에서 같은 불리언을 계산하도록 강제된다:

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

2.6 풀이 예제 4 — 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+ 하에서는 모든 행이 잠재적 런 시작이다).

absorption 하에서는 C2가 화요일에 C1으로 병합되었을 것이다 — 병합된 컨텍스트는 천장을 하나만 유지하므로, C2의 별개 시각(천장 $118, 토요일에야 끝나는 4일 런)은 더 이상 내부 상태에서 복원 불가능하다. C2는 런타임이 여전히 필요로 할 수 있는 독립 매치 후보이기 때문에 살아 있어야 한다. C1의 매치가 수요일에 끝나면, 다음 시도는 처음부터 다시 시작하지 않고 여전히 진행 중인 C2에서 이어받아야 한다. 따라서 DEFINE 술어가 매치 시작 의존성을 가질 때마다 플래너는 absorption을 선제적으로 비활성화한다.

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

포스터 우하단 패널("② Navigation")의 의존성 표는 어떤 내비게이션 형태가 매치 시작 의존성을 만드는지 요약한다:

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

플래너는 이 구분을 컴파일 타임에 감지하고 컨텍스트별로 absorption 적용 여부를 결정한다. 이것이 포스터 패널 ③의 벤치마크가 성공 사례와 실패 사례 모두에서 선형으로 유지되는 이유이기도 하다. absorption이 안전하면 런타임이 컨텍스트를 축약하고, 그렇지 않으면 플래너는 잘못된 답의 위험 대신 다중 컨텍스트 비용을 받아들인다.

포스터의 벤치마크 수치는 같은 알고리즘을 대규모로 펼친 것이다. 성공 패턴 (A+ B+ C+ D)에서 PostgreSQL과 Trino 모두 매치가 확정되면 O(n)으로 스케일하며, PostgreSQL의 우위 — 약 16×에서 33× — 는 대부분 JVM 격차이다.

실패 패턴 (A+ B+ C+ E)에서 Trino는 absorption이 없어 모든 잠재 매치 시작을 쫓느라 O(n²)으로 퇴화한다. 100,000행에서 다섯 시간 이상 걸리는 반면, 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가 유효할 때 context absorption을 비활성화한다.

§2.6과 §2.7을 나란히 놓으면 absorption이 실패하는 전체 그림이 보인다:

두 조건 중 하나만 있어도 영향을 받은 컨텍스트의 absorption을 비활성화하기에 충분하다. 둘 다 적용되지 않을 때 — 기본 AFTER MATCH SKIP PAST LAST ROW와 PREV, NEXT, 단순 LAST만 사용하는 DEFINE 조건 — 런타임은 패턴 위치당 단일 컨텍스트로 축약되어 끝까지 선형성을 유지한다.

§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여야 하고, EXCLUDE 옵션은 금지된다. 이는 표준 준수 검사이지 최적화가 아니다 — RPR에서 프레임 개념은 매치 구간이며, 표준은 매치된 행 외의 무언가로 채우는 것을 고려하지 않는다.

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

그 후 각 DEFINE 술어는 파티션의 컬럼들에 대해 타입 검사되고 불리언 표현식으로 강제된다. 이 과정에서 두 가지 실용적 일이 일어난다. 첫째, 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 최적화

최적화는 두 번 보상한다. 한 번은 평탄 배열의 정적 요소 수에서, 또 한 번은 런타임에서 처리되는 모든 행에서. 모든 변환은 런타임이 열거해야 하는 상태 공간을 줄인다. 옵티마이저는 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}). 그 외 조합은 평탄화하면 받아들이는 카운트 집합에 빈자리(spectrum gap)가 생길 수 있다 — 예를 들어 (A{2}){2,3}은 {4, 6}만 받지만 단순히 A{4,6}으로 바꾸면 5도 받게 되어 의미가 달라진다. 옵티마이저는 이런 경우를 감지하고 구조를 그대로 둔다.

요소 형태

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

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

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

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

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

요소별 속성

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

Reluctant

수량자 확장 순서를 뒤집는다. greedy 수량자는 "exit"보다 "loop again"을 먼저 시도하고, reluctant 수량자는 "exit"를 먼저 시도한다. A+?의 경우 변수가, ((…)+?)의 경우 그룹의 BEGIN과 END가 들고 있다.

Empty-loopable

본체가 nullable한 그룹의 END에 설정((A?)*, (A? B?)+, (A | B*)). 정상 loop-back과 함께 fast-forward exit를 추가하도록 런타임에 지시하여, cycle guard가 빈 반복을 만들 수 있는 그룹의 정당한 매치를 죽이지 않게 한다.

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
  AST를 순회하며 구조적 사례를
  만족하는 요소를 표시

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

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

앞서는 무한 변수 자체가 흡수 가능(Case 1)하고 이전 컨텍스트를 보호. 상태가 A를 지나는 즉시 absorption 중단 — 본체의 나머지는 단조성 보장이 없으므로, 플래그는 A에만 설정.

위 세 가지 형태에 해당되지 않는 구조적 사례도 마찬가지로 교훈적이다. A B+는 현재 규칙으로 흡수될 수 없다. 앞서는 A가 무한 부분이 시작되기 전에 행을 소비하므로, 한 행 차이로 시작한 컨텍스트들이 무한 본체 내부의 서로 다른 위치에 있게 되기 때문이다. (고정 길이 접두를 shadow path로 처리하는 후속 "PREFIX absorption" 확장이 설계되어 별도 패치로 계획되어 있다.) 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 저장
  targetPos의 행을 current_row_slot
    으로 가져옴
  result = eval_inner_expression()
  current_row_slot 복원
  return result

트릭은 저장하고 복원할 슬롯이 정확히 하나라는 점이다. 내부 표현식 — 산술, 함수 호출, 다른 컬럼 참조 등 무엇이든 — 은 current row에 대해서와 같은 평가 경로를 사용해 교체된 슬롯에 대해 실행된다. 대체 평가기 없음, shadow slot 없음, 튜플 복사 없음.

복합 내비게이션은 파싱 시점에 평탄화되어 교환이 여전히 한 번만 일어나도록 한다. 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 lastMatchedRow − n

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

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

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

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

유지 범위

내비게이션은 윈도우 함수 메커니즘이 이미 스트리밍해 지나간 행들로 도달한다. 그 행들을 사용 가능하게 유지하기 위해 실행기는 최근 행들의 슬라이딩 윈도우를 보존하는 tuplestore 위에 자리한다. 문제는 그 윈도우가 얼마나 넓어야 하는가이다. 패치는 컴파일 타임에 두 가지 보완적 오프셋으로부터 결정한다:

Lookback 범위

어떤 DEFINE 호출이 현재 행에서 얼마나 뒤로 도달할 수 있는지.

발생 요인: PREV, 오프셋이 있는 LAST, 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 — 는 두 범위의 측정된 피크, 즉 질의 동안 실행기가 양쪽 방향으로 도달해야 했던 가장 깊은 지점이다.

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

성공한 매치는 작은 값 묶음으로 기록된다. 유효성 플래그, 성공/실패 플래그, 매치가 시작되는 행, 그리고 소비한 행 수이다. 유효성 플래그가 설정되면 실행기에 대한 후속 질의 — "이 행이 매치 안에 있는가?" — 는 묶음을 확인해 O(1)로 답할 수 있다. 길이 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단계 행별 엔진

실행기의 행별 드라이버는 주어진 행이 매치된 프레임에 속하는지 알아야 할 때마다 주변 윈도우 함수 메커니즘에 의해 호출된다. 드라이버는 현재 시작 위치에 대한 컨텍스트를 찾거나 생성하고, 모든 DEFINE 술어를 현재 행에 대해 한 번 평가하여 변수별 불리언 배열을 산출한 뒤, NFA를 한 행 앞으로 진행시킨다. 전진 단계 자체는 같은 외부 루프에 감싸인 고정된 순서의 세 단계 — 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)

이 순서는 양식상의 선택이 아니다. 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]
      if elem이 변수가 아님:
          continue   # advance가 처리

      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로 되돌아감). 두 플래그 모두 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 분기 (순서대로),
    BEGIN (그룹 진입; min = 0이면
           선택적 건너뛰기 경로 추가),
    END (루프백 / 종료 / fast-forward —
         아래 참조),
    FIN (matchEndRow 기록,
         matchedState 저장, 그리고 이 후보
         범위 안의 이후 컨텍스트들 폐기
         — 아래 참조),
  변수를 만날 때마다 멈춤:
      state를 ctx.states에 추가
      (elemIdx + counts로 중복 제거)

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

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

이는 두 FIN-time 가지치기 단계 중 하나이다 — 다른 하나는 이 절 앞부분에서 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 충족 처리)
          (cycle guard가 죽일 정당한
           매치를 구제)

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

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

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

빈 루프 가능 그룹

런타임이 다뤄야 하는 미묘한 경우가 nullable 그룹이다 — 본체의 모든 자식이 선택적이라, 본체가 한 행도 소비하지 않고 반복을 끝낼 수 있는 그룹. (A?)*, (A? B?)+, (A | B*) 같은 패턴이 이에 해당한다. 원칙적으로는 문제가 없지만 NFA의 엡실론 확장에서는 실제 위험이 된다. 본체가 빈 매치를 내면 END가 BEGIN으로 돌아가고, 본체가 다시 빈 매치를 내고, BEGIN이 다시 END로 가고… 이를 멈추는 장치가 없으면 Advance의 DFS는 끝나지 않는다.

런타임은 방문한 요소 비트맵(패턴 요소당 1비트)으로 이를 멈춘다. 이 비트맵은 각 상태의 DFS 확장 전에 클리어된다. 같은 확장 안에서 어떤 요소든 두 번째로 방문되는 즉시 그 경로는 포기된다. cycle guard는 무조건적이고 저렴하지만 부작용이 있다 — 정당한 빈 반복으로 하한에 도달해야 하는 경로도 포기할 수 있다. 행 스트림 어디서도 A가 매치되지 않는 (A?){2,3}를 보자:

의도된 동작:
  iter 1: A?가 0행 매치
          → END, count = 1 (min 미만)
  iter 2: A?가 0행 매치
          → END, count = 2 (min 충족)
  길이 0 매치로 종료

cycle guard 단독 동작:
  iter 1: A? skipped → END, count = 1
          → BEGIN으로 loop back
  iter 2: BEGIN 이미 방문됨
          → DFS 중단
  count가 min에 도달 못함
  → 매치 실패 (잘못된 결과)

해결책은 컴파일 타임에 결정되어 런타임에 발동된다. 플래너는 본체가 nullable인 그룹을 만날 때마다 그 그룹의 END 요소에 empty-loopable 태그를 단다. 런타임에서 END 핸들러가 "반복 카운트가 아직 하한 미만"이라는 이유로 loop back하려 할 때, 이 태그가 정상 loop-back 경로와 함께 추가 fast-forward 상태도 복제하도록 지시한다:

advance_end (count가 min 미만):

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

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

두 경로는 서로 보완한다. 정상 loop-back은 본체가 이후에 실제 매치를 만들 경우를 처리한다 — 예컨대 (A?){2,3} 뒤에 A가 늦은 행에서만 매치되는 데이터가 따라올 때, loop-back 덕분에 두 번째·세 번째 반복이 비어있지 않은 매치를 찾을 수 있다. fast-forward는 본체가 끝까지 아무것도 만들지 못하는 경우를 처리한다 — 그룹 자체를 빠져나가 cycle guard를 우회하고, "남은 필요 반복은 모두 비어 있다"고 선언해 길이 0 본체로 매치를 성립시킨다. 두 상태 모두 컨텍스트에 들어가고, 끝까지 살아남은 쪽이 이긴다. 삽입 시 중복 제거 검사가 어느 쪽도 자기 몫 이상의 상태를 만들지 못하게 막는다.

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 큐에서 여전히 보류 중인 상태들 — 어휘 순서에 따라 모든 남은 상태들은 덜 선호되며 즉시 폐기 가능.

후보 매치 가지치기(컨텍스트 간) On FIN

시작 행이 후보 매치 범위 안에 있는 다른 컨텍스트들 — FIN에 도달한 컨텍스트는 더 긴 매치를 계속 찾을 수 있지만(greedy fallback), AFTER MATCH SKIP PAST LAST ROW 하에서는 후보 범위 안의 어떤 컨텍스트도 그 탐색 결과와 무관하게 더 이상 보고 가능한 출력을 낼 수 없으므로 즉시 폐기.

Cycle guard Advance

같은 DFS 안에서 같은 패턴 요소를 다시 방문하는 엡실론 확장 — 그렇지 않으면 nullable 그룹에서 영원히 루프.

Empty-loop fast-forward Advance

cycle guard가 nullable 그룹에서 죽일 정당한 빈 반복 매치 — 남은 필요 반복을 빈 것으로 선언하고 그룹을 종료하여 사이클을 우회.

한정 프레임 컷오프 Match

매치가 사용자 지정 프레임 상한에 도달한 컨텍스트 — 이를 넘어 확장할 수 없도록 강제 mismatch(§3.4).

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

어떤 단일 규칙도 그 자체로 충분하지 않다. cycle guard만으로는 nullable 그룹의 정당한 매치를 죽일 것이고, empty-loop fast-forward만으로는 무한 엡실론 루프를 멈추지 못할 것이며, absorption만으로는 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
  (질의가 FIRST, PREV(FIRST(...)),
   NEXT(FIRST(...))을 사용할 때만)

Peak과 total은 런타임의 직접 계측이다. 동시에 살아있던 상태가 몇 개였는지, 질의 수명 동안 몇 개가 생성되었는지, 중복 제거로 얼마나 많이 병합되었는지. 매치 길이 히스토그램은 네 가지 결과 — 성공한 매치, 실패한 매치 시도, 흡수된 컨텍스트, 평가 없이 폐기(skip)된 컨텍스트 — 를 분리하고 min/max/avg로 보고하여 성능 병리를 한눈에 보이게 한다. 건강한 실행은 대부분 컨텍스트가 매치 또는 흡수로 나타나며 mismatched 길이는 작다.

두 Nav Mark 카운터는 §3.3이 컴파일 타임에 도출하는 tuplestore 유지 범위를 보고한다. Lookback은 PREV, 오프셋이 있는 LAST, 내부 LAST가 있는 복합 형태에 걸친 가장 깊은 후방 도달이다. Lookahead는 가장 오래된 살아있는 컨텍스트의 매치 시작에서 측정된 가장 깊은 전방(또는 음수일 때 후방) 도달로, FIRST와 내부 FIRST가 있는 복합 형태가 기여한다.

각 카운터는 오프셋이 상수일 때 고정 정수로, 호출마다 평가해야 하는 비상수 표현식일 때 "runtime"으로, 런타임이 무한 범위를 필요로 할 때 "retain all"로 출력된다. Lookahead는 질의가 실제로 매치 시작 상대 내비게이션을 사용할 때만 방출된다.

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

카운터 외에도 EXPLAIN은 원래 PATTERN과 DEFINE 절을 reluctant 수량자, 그룹 반복, AFTER MATCH SKIP 옵션까지 포함하여 충실히 재현한다. 구현은 이 round-trip을 안정적으로 만들기 위해 상당한 노력을 기울여, pg_dump와 pg_upgrade가 의미 변형 없이 RPR 객체를 보존할 수 있게 한다 — rpr_explain의 회귀 테스트가 이를 사례별로 검증한다(§4 참조).

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

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

rpr

end-to-end 질의 시맨틱 — 합성 주가 데이터에 대한 현실적인 윈도우 시나리오(V형, W형, 연속 상승, 반전).

rpr_base

파서 계층 — 키워드 수용, 구문 형태, 수량자, 내비게이션 파싱, 오류 메시지, pg_dump/pg_upgrade round-trip 안정성.

rpr_nfa

NFA 런타임 — 3단계 루프, 모든 흡수 가능 형태에서의 흡수, 컨텍스트 생애 엣지 케이스.

rpr_explain

출력 포맷팅 — NFA 통계, 패턴 deparse, 식별자 인용, 재로드 간 포맷 안정성.

rpr_integration

플래너 상호작용 — 무관한 윈도우 최적화가 RPR 시맨틱을 손상시키지 않도록 하는 가드.

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

시나리오 스위트는 테스트 세트의 공식 얼굴이다. 약 1,600행의 합성 주가 데이터셋을 사용해 현실적인 질의를 실행한다 — V형 회복, W형(이중 바닥), 연속 상승과 하락, 반전 패턴, 다중 심볼 파티션. 입력과 출력이 사용자가 실제로 작성할 만한 질의처럼 읽히는 유일한 스위트이다. 나머지는 의도적으로 환원적이며 한 번에 한 계층에 집중한다.

이 질의들이 모든 계층(파서, 플래너, 실행기, 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을 견딘다는 것을 증명할 책임이 있기 때문이다. 대부분이 길고 현실적인 질의가 아니라 작고 집중된 스니펫(구문 기능당 하나)으로 이루어져 있다. 목표가 시나리오 현실성이 아닌 커버리지이기 때문이다.

직렬화 테스트는 특별한 주의가 필요하다. 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 변수가 매치되는지 명시적으로 선언하는 불리언 배열을 행으로 가진 입력 테이블과, 특정 런타임 동작을 탐사하는 패턴의 짝이다. 불리언 배열 관용구는 런타임 테스트를 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의 사례 분석에서 나온 모든 형태를 다룬다:

• 단순 무한 변수(A+) — 정형적 N-to-1 축약;
• 고정 길이 그룹((A B)+, (A B{2})+, 3단계 중첩 ((A (B C){2}){2})+);
• 고정 접미를 가진 앞서는 무한 변수(A+ B) — 앞서는 A+만 absorption 플래그를 가지고 접미는 갖지 않음;
• 대안 안에서의 분기별 absorption(B+ C | B+ D);
• 다중 무한 변수(A+ B+) — 앞서는 것만 흡수 가능;
• reluctant 수량자(A+?) — absorption에서 제외 검증;
• 앞서지 않는 무한(A B+) — 제외 검증.

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

4.4 rpr_explain — 출력 안정성

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

• NFA 카운터가 올바른 위치에 나타남 — WindowAgg별 통계(피크/총/병합된 상태, 피크/총/폐기된 컨텍스트, matched/mismatched/absorbed/skipped 길이 히스토그램, Nav Mark Lookback, 그리고 매치 시작 상대 내비게이션 사용 시 Nav Mark Lookahead) 모두 문서화된 레이블로 EXPLAIN ANALYZE에 표시.
• 패턴이 올바르게 deparse됨 — reluctant 변형과 한정 형태를 포함한 모든 수량자 형태, 모든 alternation, 모든 group, 모든 AFTER MATCH SKIP 형태, INITIAL, 오프셋이 있는 내비게이션 호출, 복합 내비게이션. deparse된 텍스트는 변경 없이 파서를 통해 round-trip되어야 함.
• 식별자 인용이 올바름 — 패턴 변수와 DEFINE 표현식은 일반 SQL 식별자와 같은 인용 규칙으로 방출되어, 비정상 변수 이름이 pg_dump 출력을 망가뜨리지 않음.

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

4.5 rpr_integration — 플래너 상호작용

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

프레임 정규화

플래너는 보통 단조 집계에 대해 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)

같은 PATTERN이지만 다른 DEFINE 절을 가진 두 RPR 윈도우는 다른 매치를 산출하므로 구조적 형태가 동일하더라도 별개로 유지되어야 함.

미사용 출력 투영

외부 질의가 윈도우의 행별 출력을 결코 읽지 않더라도 RPR 윈도우는 제거될 수 없음. 패턴 매처의 부수 효과(어떤 행이 어떤 매치 안에 있는지)가 계획의 다른 곳에서 reduced-frame 계산을 공급함.

이동 집계 inverse 전이

inverse 전이 함수가 있는 윈도우 집계는 보통 프레임이 이동함에 따라 점진적으로 평가 가능. RPR의 reduced frame은 슬라이딩 윈도우가 아니며, inverse 전이 경로는 잘못된 결과를 낼 것임.

이 테스트들 전반에 걸친 패턴은 같다. 각 테스트는 최적화를 트리거하는 비-RPR 베이스라인을 제공하고(EXPLAIN이 그것이 적용됨을 보이는지 검증), 구조적으로 유사한 형태의 RPR 질의를 실행하여 최적화가 적용되지 않음을 검증한다. 두 절반이 함께 플래너의 가드가 모든 질의에 조용히 도장만 찍는 것이 아니라 실제 작업을 하고 있음을 증명한다.

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