§1. RPR 이란 무엇인가

1.1 시퀀스를 SQL 의 1급 표현으로

기존 SQL 은 행을 집합 으로 다룬다. WHERE 는 각 행을 독립적으로 평가하고, GROUP BY 는 행을 모아 요약한다. 이 모델은 "이번 분기 매출 합계" 같은 질문에는 강하지만, "주가가 두 번 연속 떨어진 뒤 한 번 오른 V 자 구간을 모두 찾아라" 같은 질문에는 약하다. 순서가 있는 시퀀스 자체가 SQL 의 1급 표현이 아니었기 때문이다.

SQL 표준 R020 (ISO/IEC 19075-5) 은 윈도우 절을 확장해 이 부족을 메운다. WINDOW 안에 PATTERN 과 DEFINE 절을 더하면, 행의 시퀀스에 정규식을 선언할 수 있다.

SELECT ts, price,
  first_value(price)
    OVER w AS start_price
FROM ticks
WINDOW w AS (
  PARTITION BY symbol ORDER BY ts
  ROWS BETWEEN CURRENT ROW
        AND UNBOUNDED FOLLOWING
  PATTERN (DOWN+ UP+)
  DEFINE
    DOWN AS price < PREV(price),
    UP   AS price > PREV(price)
)

PATTERN 은 형태 를, DEFINE 은 각 변수의 의미 를 선언한다. 위 쿼리는 "하락이 한 번 이상 이어진 뒤 상승이 한 번 이상 따라오는" V 자 구간을 찾는다. DEFINE 은 기존 WHERE 와 달리 PREV · NEXT 같은 네비게이션 함수로 행 간 비교가 가능하다.

매치가 확인되면 표준 용어로 "full window frame" 이 "reduced window frame" 으로 축소된다. 이후 first_value · last_value · sum · count 같은 기존 윈도우 함수가 그 축소된 프레임 위에서 평소처럼 동작한다. 새로운 실행 모델 없이 — 순서 있는 시퀀스가 SQL 표면에 새로운 차원으로 격상되는 것이다.

1.2 활용처

순서가 본질적인 데이터 분석은 도메인을 가리지 않는다. 금융·트레이딩에서는 캔들 패턴, V-shape, 이중바닥, 변동성 돌파 같은 시계열 형상을 찾는다. 관측·모니터링에서는 레이턴시 스파이크, 에러 클러스터, 메트릭 이상치의 연쇄를 추적한다. 사용자 행동 분석에서는 퍼널(전환 경로), 세션화, 이탈 직전 행동 패턴을 추출한다. 로그·보안에서는 login → action → logout 시퀀스나 침입·이상 트래픽 패턴을, IoT·산업에서는 센서 상태 전이와 설비 이상 징후를 잡아낸다.

공통점은 분명하다 — 단순 집합 연산이나 필터로는 표현이 어렵고, 자기 조인이나 LAG 누적으로 풀면 곧 복잡해지는 영역이다. RPR 은 이 영역을 SQL 의 일부로 끌어들인다.

1.3 만들어진 것 — 두 가지 핵심 설계

현 PostgreSQL 구현은 표준 R020 의 핵심 기능에 더해, 효율과 표현력을 받치는 두 가지 굵직한 설계를 담고 있다.

Context Absorption — O(n²) → O(n)

표준은 매처가 모든 행을 잠재적 매치 시작 후보로 고려할 것을 요구한다. 순진하게 구현하면 N 행마다 새 컨텍스트가 생겨 메모리가 O(n²) 로 증가한다. 핵심 관찰은 다음과 같다 — 무한 수량자(A+) 아래에서 같은 NFA 위치에 도달한 두 컨텍스트가 동일한 미래 를 가진다면, 오래된 쪽만 남기고 새 쪽은 안전하게 폐기할 수 있다. 결과적으로 N 개의 컨텍스트가 1 개로 압축된다.

흡수가 가능한 조건은 매치 시작 위치에 의존하지 않는 패턴 이다. 단순 A+, 고정 길이 그룹의 무제한 반복 (A B){n,} 같은 구조에서 적용된다. 반면 매치 시작 행을 참조하는 술어 — FIRST, offset 있는 LAST, 또는 inner 가 그 둘인 compound 형 — 가 있으면 컨텍스트마다 미래가 달라져 흡수할 수 없고, 이 경우 모든 컨텍스트가 살아남는다 (§4.1 의 흡수 안전성 표에서 자세히 다룬다).

Navigation on 1-Slot Tuple Swap

DEFINE 안에서 PREV(price) 는 이전 행의 값을 어떻게 가져오는가? 단순한 방법은 행마다 슬롯을 따로 두고 그쪽 컬럼을 평가하는 것이다. 그러나 PREV, NEXT, FIRST, LAST, 그리고 그 합성형까지 모두 별도 슬롯을 잡으면 메모리·캐시 비용이 커진다.

PostgreSQL 구현은 단일 슬롯(ecxt_outertuple) 만 운용한다. 네비게이션을 만나면 그 슬롯의 튜플을 임시로 대상 행의 튜플로 교체(NAV_SET)하고, 표현식을 평가한 뒤 원래 튜플로 복원(NAV_RESTORE)한다. 슬롯 한 칸으로 모든 행 참조를 처리하므로 메모리 오버헤드가 일정하고, JIT 컴파일까지 그대로 통과한다.

Trino 와의 비교

Trino 도 같은 표준 MATCH_RECOGNIZE 를 구현한다. 매치 성공 케이스에서는 양쪽 모두 단일 패스로 O(n) — 패턴이 한 번 잡히면 그 뒤로 SKIP 정책에 따라 진행하므로 비용이 선형이다. 그러나 매치 실패 케이스에서 차이가 드러난다.

PostgreSQL 대비 Trino 의 실행 시간 비율. 매치 실패에서 격차가 극단으로 벌어진다.

성공·실패 양쪽 모두 단일 패스 O(n) 를 유지하는 비결이 바로 context absorption 이다. Trino 는 흡수 최적화가 없어 매치가 끝까지 못 가는 경로마다 컨텍스트 폭증이 일어나고, 결과적으로 O(n²⁺) 으로 폭발한다. 이 한 가지 사실이 현 구현의 핵심 — 표현력은 표준이 정의하고, 효율은 absorption 이 보장한다.

참고로 매치 성공 케이스의 16~33 배 격차는 알고리즘만의 차이는 아니다. Trino 는 JVM 위에서 분산 실행을 가정해 구동되는 반면 PostgreSQL 은 C 로 작성된 단일 프로세스 엔진이라 평탄한 데이터에서는 시동·인터프리트 오버헤드만으로도 한 자릿수 배 차이가 자연스럽게 난다. 알고리즘 격차의 본 모습은 매치 실패 케이스 — 같은 시동 비용 위에서 21,000 배 ~ 217,000 배로 벌어지는 — 에서 드러난다.

§2. SQL 표준 정리

2.1 두 가지 진입점 — R010 과 R020

SQL 표준의 Row Pattern Recognition 은 두 형태로 정의되어 있다. R010 MATCH_RECOGNIZE 는 FROM 절에 들어가는 독립 구문이고, R020 은 기존 WINDOW 절을 확장하는 형태다. PostgreSQL 은 R020 부터 진입했다 — 기존 Tuple Store 인프라를 재활용해 구현이 간결하기 때문이다. R010 은 R020 완성 후 동일 인프라 위에 올릴 수 있다.

SELECT *
FROM ticks MATCH_RECOGNIZE (
  PARTITION BY symbol ORDER BY ts
  MEASURES CLASSIFIER() AS var
  ALL ROWS PER MATCH
  PATTERN (DOWN+ UP+)
  DEFINE ...
)

SELECT ts, price,
  first_value(price) OVER w
FROM ticks
WINDOW w AS (
  PARTITION BY symbol ORDER BY ts
  ROWS BETWEEN CURRENT ROW
        AND UNBOUNDED FOLLOWING
  PATTERN (DOWN+ UP+)
  DEFINE ...
)

두 형태는 같은 정규식 어휘와 같은 네비게이션 의미론을 공유한다 — PATTERN, DEFINE, MEASURES, SUBSET, PERMUTE, {- -} exclusion, CLASSIFIER(), MATCH_NUMBER(), PREV/NEXT/FIRST/LAST (+ compound), 정규식 한정자 + * ? {n,m}, reluctant 한정자, alternation, grouping, AFTER MATCH SKIP 의 모든 옵션이 공통이다. 다른 점은 위치(FROM 절 vs WINDOW 절)와 출력 모델뿐이다.

2.2 정규식 엔진 선택 — Traditional NFA

표준은 정규식 엔진으로 DFA · Traditional NFA · POSIX NFA 세 가지를 검토한 끝에 POSIX 를 거부했다. POSIX 는 "leftmost longest" 규칙을 강제해 모든 매치를 다 찾은 뒤 최장을 선택해야 하므로 orders of magnitude 느릴 수 있고, 결정적으로 reluctant 한정자 자체를 정의할 수 없다. 표준은 결국 "Perl was adopted as the design target for pattern matching rules" 로 정리했다 — 매치는 가장 이른 행에서 시작하고 발견 즉시 exit, 우선순위는 lexicographic 순서와 greedy/reluctant 선택을 따른다.

PostgreSQL 도 v37 까지는 기존 regex 인프라 위에 구현했으나 패턴 변수 한계와 상태 폭발 문제에 막혀 v38 부터 자체 NFA 엔진으로 전환했다. 자체 NFA 는 표준의 "Perl as design target" 과 정확히 일치하는 traditional NFA 다. 일반 정규식과 다른 점은 알파벳에 ^ $ ( ) - [ ] 같은 특수기호가 함께 포함되는 parenthesized language 로 NFA 상태를 모델링한다는 것 — 그룹 진입/이탈, 대안 선택, 제외 구간을 모두 식별 가능한 형태로 추적한다.

2.3 PATTERN 의 어휘

현재 PostgreSQL 이 받아들이는 PATTERN 구문은 다음과 같다.

표준이 정의하지만 PostgreSQL 이 거부하는 항목도 명확하다. R020 윈도우 절 RPR 에서 anchors ^ / $ 는 표준이 "precisely the same as in MATCH_RECOGNIZE, except that the anchors (^ and $) are not permitted with row pattern matching in windows" 로 명시 금지하므로 parser 가 차단한다. 수량자 직접 중첩 A+ + 도 모호성 때문에 표준이 그룹을 강제((A+)+) 하므로 동일하게 거부된다. 빈 패턴 () 와 PERMUTE(A,B,C) 는 표준이 정의하지만 현재 구현이 아직 받아들이지 않는다 — 둘 다 후속 패치에서 추가 가능한 항목이다 (PERMUTE 는 NFA 상태 머신 확장과 상태 폭발 차단이 필요해 별도 시리즈로 분리되어 있다).

구현 측 제약 한 가지 — PATTERN 안에 등장할 수 있는 서로 다른 변수의 개수는 252 개 (RPR_VARID_MAX) 로 제한된다. 실용 한도는 한참 위이지만 NFA 요소의 varId 필드가 1 바이트라 BEGIN·END·ALT·FIN 같은 예약 ID 를 빼고 남는 슬롯 수가 그 값이다. 초과 시 too many pattern variables 오류로 거부된다.

2.4 DEFINE · Navigation · 출력 · SKIP

PATTERN 외 네 카테고리의 인벤토리는 구현 상태가 갈린다.

DEFINE 과 Navigation

DEFINE 은 변수마다 부울 조건식을 매긴다 (UP AS price > PREV(price)). PATTERN 에 있지만 DEFINE 이 없는 변수는 항상 참으로 간주된다. 네비게이션 함수로는 PREV / NEXT (이전·다음 행 참조, 1-slot 운용) 와 FIRST / LAST (매치 내 시작·끝 행 참조) 가 있다. 이 둘의 합성은 외부 행 기준 · 내부 매치 기준 조합인 PREV(FIRST()) · PREV(LAST()) · NEXT(FIRST()) · NEXT(LAST()) 4 가지로 제한된다. 그 외 조합 — 같은 종류 중첩 (PREV(NEXT()), FIRST(LAST()) 등), 역방향 (외부 매치 기준 · 내부 행 기준, 예: FIRST(PREV())), 3 단 이상 중첩, 합성 내부에 표현식 삽입 — 은 parser 가 모두 거부한다.

AFTER MATCH SKIP

표준이 정의하는 4 모드 중 PostgreSQL 은 두 개를 구현한다. PAST LAST ROW (기본, 매치 직후로 점프) 와 TO NEXT ROW (매치 시작 다음 행, 겹침 허용). 나머지 두 모드 SKIP TO FIRST var 와 SKIP TO LAST var 는 후속 패치 대상이다 — 매치에 참여한 특정 패턴 변수의 첫·마지막 행으로 점프하는 모드인데, 어느 행이 어느 변수에 매핑됐는지를 알아야 하므로 뒤에서 설명할 match history 인프라에 의존한다.

출력 모델

R020 의 MEASURES · ONE/ALL ROWS PER MATCH · CLASSIFIER() · MATCH_NUMBER() · SUBSET · RUNNING/FINAL semantics 는 모두 표준의 일부지만 현 PostgreSQL 구현에는 포함되어 있지 않다. MEASURES 없이도 일반 윈도우 함수(first_value, count(*), sum 등) 로 매치 정보를 충분히 추출할 수 있다는 점이 R020 의 강점이지만, 표준이 정의하는 출력 옵션 전체를 지원하려면 별도 인프라 작업이 필요하다.

DEFINE 안의 거부 항목

DEFINE 표현식 안에서 거부되는 항목은 출처가 셋으로 갈린다. (a) 표준 명시 금지 로는 outer / range-qualified 컬럼 참조 ("not allowed in DEFINE clause") 가 있고, WITH RECURSIVE 안에서의 RPR 사용도 같은 부류다. (b) PostgreSQL 정책 으로 거부하는 것은 volatile 함수와 sequence (nextval()) — 결정성과 부작용 차단을 위해 커미터 정책으로 정한 항목이다. (c) 미구현 으로 거부하는 것은 pattern-qualified reference (A.price) 와 subquery 다. 전자는 match history 인프라가, 후자는 정적 검사 두 개 추가가 land 의 전제다 (자세한 풀이는 §3.4 · §5.5).

패턴 확장

{- ... -} exclusion 은 R010 전용이라 R020 에서는 의미가 없다. 그 외 PATTERN 어휘 확장 후보 (PERMUTE, empty pattern ()) 는 §2.3 에서 다뤘다.

2.5 match history — 후속 패치의 단일 의존성

위 미구현 항목 대부분은 단 하나의 인프라에 묶여 있다 — match history, 즉 "어느 행이 어느 패턴 변수에 매핑됐는가" 를 매치 단위로 인덱싱 가능한 형태로 보존하는 자료구조다. 현 NFA 실행 상태는 루프 카운터의 깊이(현재 어떤 변수에서 몇 번째 반복인지)만 보존하고, 매치가 확정되면 시작·끝 행 위치와 카운터만 남는다 — 행→변수 매핑은 명시적으로 기록되지 않는다.

이 정보가 없으면 매치 단위 계산을 할 수 없다. MEASURES 는 어느 행이 어느 변수인지 알지 못하고, CLASSIFIER() 는 행→변수 매핑 자체를 반환할 수 없으며, MATCH_NUMBER() 는 매치 식별 번호를 매길 수 없다. SUBSET 과 A.price 같은 qualified reference 는 평가 대상 행 집합을 정할 수 없고, SKIP TO FIRST/LAST var 도 특정 변수의 시작·끝 위치를 모른다. 그래서 match history 인프라 한 번을 land 하면 다수의 미구현 기능이 한꺼번에 풀린다 — 후속 패치 시리즈의 우선순위 최상위에 놓이는 이유다.

§3. 사용법

3.1 윈도우 절에 RPR 끼워넣기

R020 의 사용은 의외로 단순하다. 기존 윈도우 절 안에 PATTERN 과 DEFINE 두 키워드만 추가하면 된다. 다른 절은 모두 평소처럼 동작한다 — 출력 컬럼은 SELECT 에, 데이터 소스는 FROM 에, 윈도우 함수는 OVER w 에 적는다.

SELECT ts, price,
  count(*)
    OVER w AS match_len,
  first_value(price)
    OVER w AS start_price,
  last_value(price)
    OVER w AS end_price,
  sum(volume)
    OVER w AS total_vol
FROM ticks
WINDOW w AS (
  PARTITION BY symbol
  ORDER BY ts
  ROWS BETWEEN CURRENT ROW
        AND UNBOUNDED FOLLOWING
  PATTERN (DOWN+ UP+)
  DEFINE
    DOWN AS price < PREV(price),
    UP   AS price > PREV(price)
)

윈도우 프레임은 반드시 ROWS BETWEEN CURRENT ROW AND ... 형식이어야 한다. RANGE 와 GROUPS 는 RPR 과 함께 쓸 수 없고, 시작점도 CURRENT ROW 가 아닌 다른 값은 허용되지 않는다. EXCLUDE 절은 NO OTHERS 외 다른 값을 받지 않는다 — 표준이 그렇게 못 박았기 때문이다.

매치는 각 행을 매치 시작 후보 로 보고 시도된다. 어떤 행 R 에서 PATTERN 이 성립하면 그 행이 매치의 시작점이 되고, 윈도우 함수는 축소된 프레임에서 의미 있는 값을 반환한다. 매치되지 않은 행에서는 count(*) OVER w 가 0 이고 first_value 등은 NULL 이다 — 기본 AFTER MATCH SKIP PAST LAST ROW 정책의 자연스러운 결과다.

3.2 PATTERN — 정규식 어휘

PATTERN 은 자주 만나는 정규식과 거의 같은 어휘를 쓴다. + 는 1회 이상, * 는 0회 이상, ? 는 0 또는 1회를 의미한다. 정확한 횟수가 필요하면 {n}, 범위는 {n,m}, 한쪽이 열려 있으면 {n,} 또는 {,m} 으로 적는다.

-- 하락 → (잠시 평이) → 상승
PATTERN ( DOWN+ FLAT* UP+ )

-- UP 이 3~5 행 연속
PATTERN ( UP{3,5} )

-- 상승 또는 하락 연속
PATTERN ( (UP | DOWN)+ )

-- UP 뒤 DOWN 쌍이 2~4 번
PATTERN ( (UP DOWN){2,4} )

한정자 직접 중첩(A+ +)은 표준이 금지한다. 같은 효과를 원하면 그룹을 거쳐야 한다 ((A+)+). 패턴 내 anchors ^ 와 $ 도 R020 에서는 금지되는데, INITIAL 이 시작 위치를 정하는 역할을 대체한다.

각 한정자에는 reluctant 변형 (+?, *?, ??, {n,m}?) 이 있다. 기본 greedy 는 매치를 가능한 길게 잡지만, reluctant 는 가능한 짧게 잡는다 — 같은 파티션에서 짧은 매치 여러 개를 끊어내고 싶을 때 유용하다. 예를 들어 PATTERN (A+) 로 5 개 행을 받으면 첫 행에서 길이 5 의 매치 하나가 나오지만, PATTERN (A+?) 로 받으면 5 개 행 각각이 길이 1 의 매치가 된다.

3.3 INITIAL — 매치 시작 모드

R020 의 기본 모드 INITIAL 은 각 평가 행 R 마다 "R 이 매치의 첫 행이 되는 매치만 시도" 한다. 즉 R 에서 시작하지 않는 매치는 무시된다. "각 시점에서 그 행을 시작점으로 한 시퀀스의 길이" 같은 분석에 자연스럽게 맞는다.

대안인 SEEK 모드는 — R 에서 시작하지 않더라도 R+1, R+2 ... 끝까지 진행하며 첫 매치를 찾는다 — 표준에 정의되어 있으나 현 PostgreSQL 구현은 parser 단계에서 거부한다 (ERROR: SEEK is not supported / HINT: Use INITIAL instead.). SEEK 가 동작하면 "이 행 이후 다음 V 자 패턴이 어디서 일어나는가" 같은 질문을 자연스럽게 던질 수 있다 — 후속 패치의 후보다.

3.4 DEFINE — 변수의 의미

DEFINE 은 각 패턴 변수에 부울 표현식을 매긴다. 현재 행이 그 변수에 해당하는지 판단하는 술어다. 표현식 안에는 일반 SQL 의 비교·논리 연산자, immutable/stable 함수, 그리고 PREV·NEXT·FIRST·LAST 네비게이션을 자유롭게 쓸 수 있다.

DEFINE 이 없는 변수도 합법이다 — PATTERN 에 등장하지만 DEFINE 에 매기지 않은 변수는 항상 참 으로 평가된다. 반대로 DEFINE 에는 있는데 PATTERN 에 등장하지 않는 변수는 구문 오류(DEFINE variable "..." is not used in PATTERN) 다.

DEFINE 안에서 금지되는 항목은 몇 가지로 나뉜다.

• 표준 명시 금지 — outer / range-qualified column 참조 ("not allowed in DEFINE clause").
• PG 정책 — sequence 함수 (nextval()) 와 volatile 함수 (random(), clock_timestamp()) 거부. 표준은 volatile 함수를 navigation offset 인수에 한해서만 결정성을 요구하지만, PostgreSQL 은 DEFINE 전체에서 거부하기로 했다 (커미터 정책 결정).
• 미구현 — pattern-qualified reference (A.price) 는 표준이 허용하지만 match history 의존이라 후속 패치 대상.
• 과잉 거부 — Subquery 는 표준이 조건부 허용("중첩 RPR 없음 + outer pattern var 미참조") 하지만 현 PG 는 일괄 거부. 정적 검사 추가로 완화 예정.

안전하게 사용할 수 있는 것은 immutable/stable 함수, 현재 행 컬럼, PREV/NEXT/FIRST/LAST, 리터럴·상수 다.

3.5 Navigation

네비게이션 함수는 DEFINE 표현식에서 다른 행을 참조하기 위해 쓴다. 두 가지 기준이 있다 — 행 기준의 PREV/NEXT 와 매치 기준의 FIRST/LAST.

DEFINE
  -- 행 기준 (직전 행)
  DOWN AS price < PREV(price),
  -- 행 기준 (3 행 전)
  BIG  AS price > PREV(price, 3),

  -- 매치 첫 행 대비
  UP   AS price > FIRST(price),
  -- 매치 직전 행 대비
  PEAK AS price > LAST(price)

두 번째 인자는 거리/오프셋이다 — PREV(x, N) 는 N 행 전, FIRST(x, N) 은 매치 시작점에서 N 행 뒤를 가리킨다. 표준은 이 인자로 run-time constant 만 허용한다 (literal, embedded variable 가능, column 참조나 subquery 불가). 파티션 경계 너머나 매치 범위 밖을 가리키면 NULL 이 반환되고, DEFINE 부울식에서는 거짓으로 평가된다.

두 단계 합성도 가능하다 — PREV(FIRST(x)), PREV(LAST(x)), NEXT(FIRST(x)), NEXT(LAST(x)) 네 가지 형태로, 외부는 행 기준이고 내부는 매치 기준이다. 같은 종류끼리(PREV(PREV()), FIRST(LAST())) 또는 역방향 (FIRST(PREV())) 중첩은 거부된다. 중간에 연산자가 끼는 형태 (PREV(FIRST(x) + 1)) 도 마찬가지다.

3.6 AFTER MATCH SKIP

매치 하나가 성립한 뒤 다음 매치를 어디서 시도할지를 정하는 절이다. 표준은 4 가지 모드를 정의하고, PostgreSQL 은 이 중 두 개를 지원한다.

SKIP PAST LAST ROW (기본)

매치된 마지막 행의 바로 다음 행에서 재시도한다. 매치들이 겹치지 않고, 가장 일반적인 정책이다. 5 행 데이터에서 PATTERN (A+) 를 평가하면 첫 행에서 길이 5 의 매치 하나가 잡히고, 나머지 행은 모두 skip 되어 count(*) OVER w 가 0 으로 나온다.

SKIP TO NEXT ROW

매치 시작 행의 바로 다음 행에서 재시도한다. 같은 행이 여러 매치에 중복으로 참여할 수 있다. 같은 5 행에 PATTERN (A+) 를 적용하면 각 행이 자기 자신부터 시작하는 매치를 만들어 카운트가 5, 4, 3, 2, 1 로 줄어드는 분포가 나온다 — "이 시점에서 시작하면 얼마나 멀리 갈 수 있는가" 를 보고 싶을 때 유용하다.

성능 측면에서는 두 모드가 크게 다르다. PAST LAST ROW 는 한 매치 안에서 context absorption 이 그대로 작동해 전체 비용이 O(n) 으로 유지되지만, TO NEXT ROW 는 매 시작점마다 매치를 다시 시도하기 때문에 흡수 효과가 사라지고 누적 비용이 시작점 수에 비례해 증가한다. 결과적으로 한쪽은 선형, 다른 쪽은 초선형 — 파티션이 커질수록 두 모드 간 격차가 빠르게 벌어진다.

남은 두 모드 SKIP TO FIRST var 와 SKIP TO LAST var 는 매치에 참여한 특정 패턴 변수의 첫·마지막 행으로 점프하는 모드다 — 매치 안의 부분 구조를 골라 재시도 위치를 정밀하게 제어할 수 있지만, 행→변수 매핑이 필요하므로 match history 인프라 의존이다.

§4. NFA 내부 · 진단

4.1 Context Absorption — 흡수의 원리

§1 에서 흡수가 N 개의 컨텍스트를 1 개로 압축한다고 언급했다. 좀 더 정밀하게 보면, 흡수가 적용되는 조건은 단순하다 — 같은 NFA 위치에 있는 두 컨텍스트가 무한 수량자 아래에서 동일한 미래 를 가진다면, 오래된(=카운트가 더 높은) 쪽이 새 쪽의 모든 가능한 결과를 이미 포함한다. 따라서 새 컨텍스트는 폐기해도 결과에 영향이 없다.

"동일한 미래" 조건이 깨지는 두 가지 부류가 있다. 첫째는 매치 시작에 의존하는 술어 — FIRST 와 offset 있는 LAST 는 매치 시작 행의 위치를 직접 참조하므로 컨텍스트마다 결과가 달라진다. 둘째는 겹침 허용 SKIP — SKIP TO NEXT ROW 는 출력 측에서 모든 매치 보고를 요구하므로 흡수해버리면 결과를 잃는다.

흡수 적용 가능 여부는 패턴 구조와 DEFINE 사용에 따라 달라진다.

대안(A | B)이 섞인 패턴은 각 대안이 별개 NFA 분기로 전개되고, 분기마다 자체 absorbability 가 판정된다. 한 분기에서 흡수가 가능하면 그 분기 안에서만 컨텍스트가 압축된다.

4.2 플래너 단계의 패턴 최적화

플래너는 PATTERN AST 를 NFA 로 컴파일하기 전에 몇 가지 정규화·축약을 적용한다. 이 단계에서 흡수 가능 여부와 네비게이션의 lookback/lookahead 거리도 함께 사전 판정된다. 적용되는 변환은:

• 중첩 평탄화 — SEQ(A, SEQ(B, C)) → SEQ(A, B, C)
• 인접 변수 병합 — A A → A{2}
• 인접 그룹 병합 — (A B)+ (A B)+ → (A B){2,}
• 인접 ALT 병합 · 평탄화 · 중복 제거 — (A | B) (A | B) → (A | B){2}, (A | (B | C)) → (A | B | C), (A | B | A) → (A | B)
• 접두사/접미사 흡수 — A B (A B)+ → (A B){2,}
• 안전한 중첩 한정자 축소 — (A+)+ → A+, (A{2,3}){5} → A{10,15}
• 단일 자식 unwrap — SEQ(A) → A, (A){1,1} → A

플래너의 결과는 평탄한 NFA 배열로 컴파일되고, 각 요소의 흡수 가능 여부, DEFINE 의 매치 시작 의존성, 네비게이션의 lookback/lookahead 거리가 사전 판정되어 실행기에 전달된다. EXPLAIN 에 출력되는 Pattern: 라인이 이 최적화된 결과다.

4.3 실행의 세 단계 — Match · Absorb · Advance

매 행마다 NFA 는 세 단계 사이클을 돈다. 슬라이드와 deepdive 양쪽 모두 강조하는 골격이다.

MATCH — 현재 행 소비

현재 행에 대해 DEFINE 의 모든 변수 술어를 한 번에 평가한다. 결과는 살아있는 모든 상태가 공유 참조한다. 행 참조 (PREV·NEXT·FIRST·LAST) 는 단일 슬롯에서 대상 행으로 임시 교체 후 복원하는 1-slot tuple swap 방식으로 처리된다 (§1.3 참조). 매치 시작에 의존하는 변수(FIRST, offset 있는 LAST) 는 컨텍스트마다 시작점이 달라 별도 재평가가 필요하다.

ABSORB — 중복 컨텍스트 통합

Match 직후, 살아있는 컨텍스트들을 NFA 위치별로 비교한다. 같은 위치에 있고 더 오래된(=카운트가 더 높은) 컨텍스트가 새 컨텍스트의 미래를 덮으면 새 컨텍스트는 안전하게 폐기된다. 플래너가 사전 판정한 자격에 따라 활성화되며, 매치 시작 의존 술어나 겹침 허용 SKIP 이 있으면 비활성화된다. O(n²) → O(n) 효과는 이 단계에서 만들어진다.

ADVANCE — 다음 행 준비

살아남은 상태들을 깊이 우선으로 진행한다. 다음 패턴 요소로 전이하고, 그룹을 종료하고, 대안 분기를 탐색하고, FIN(매치 후보)에 도달한다. 분기 순서는 어휘적 우선순위로 정해진다. 같은 분기 안에서 같은 패턴 요소를 다시 방문하려는 시도는 차단되고, 정당한 빈 반복은 그룹을 즉시 종료해 우회한다. FIN 도달 시 매치 후보가 확정되고, AFTER MATCH SKIP 정책에 따라 컨텍스트 내 후순위 상태와 매치 범위 내 다른 시작점의 컨텍스트가 정리된다.

4.4 가지치기 8 — 단계별 정리

세 단계 사이클은 각 단계에서 의미 없는 상태와 컨텍스트를 잘라낸다. 총 8 가지 가지치기가 작동한다 (Match 단계에서 카운트가 찬 상태를 그룹 end 로 즉시 진행시키는 inline end-chain advance 와, FIN 도달 시점의 컨텍스트 간 정리는 각 단계의 일부로 묶었다).

▸ Match 단계 (2)

• 술어 실패 — 현재 행에서 DEFINE 술어가 거짓으로 평가된 변수 상태는 더 이상 진행할 수 없으므로 죽은 분기로 폐기.
• 한정 프레임 컷오프 — 사용자 프레임(예: ROWS BETWEEN ... AND k FOLLOWING) 상한을 넘어선 컨텍스트는 더 확장할 수 없으므로 강제 mismatch 처리.

▸ Absorb 단계 (1)

• Context absorption — 같은 NFA 위치에 있고 오래된 컨텍스트가 새 컨텍스트의 미래를 덮을 때 새 컨텍스트는 안전하게 폐기. N 시작점을 1 컨텍스트로 축약하는 핵심 최적화.

▸ Advance 단계 (5)

• 상태 중복 제거 — 서로 다른 DFS 분기를 통해 같은 위치·같은 카운트에 도달한 상태들 중 어휘적으로 앞선 것 하나만 살리고 동등물은 폐기. 매치 선호 규칙(lexicographic preferment)도 이로써 강제된다.
• 후보 매치 시 후순위 상태 폐기 — 컨텍스트 내. 한 분기가 FIN 에 도달한 시점에 DFS 큐에 남은 보류 상태들은 모두 어휘적 후순위라 결과에 영향 없어 즉시 폐기.
• 매치 범위 내 후행 컨텍스트 폐기 — 컨텍스트 간. 매치 범위 안에 시작하는 다른 컨텍스트들은 SKIP PAST LAST ROW 하에서 출력 불가하므로 일괄 제거.
• Cycle guard — 같은 DFS 안에서 같은 패턴 요소를 다시 방문하려는 엡실론 확장 차단. nullable 그룹이 빈 매치로 무한히 반복되는 루프를 막는다.
• Empty-loop fast-forward — cycle guard 가 죽일 수밖에 없는 정당한 빈 반복을 살리는 보완. 남은 필요 반복을 빈 것으로 선언하고 그룹을 즉시 종료해 사이클을 우회한다.

Cycle guard 와 Empty-loop fast-forward 는 짝으로 작동한다 — 전자는 무한 루프를 막고, 후자는 그 과정에서 죽어버리는 정당한 빈 매치를 살린다.

4.5 EXPLAIN 으로 보기

RPR 은 별도 plan node 가 아니라 WindowAgg 노드의 속성으로 동작한다. EXPLAIN ANALYZE 가 NFA 레벨의 통계를 함께 노출하므로 진단에 활용할 수 있다.

WindowAgg
  Output: ts, count(*) OVER w
  Window: w AS (ROWS BETWEEN CURRENT ROW
                AND UNBOUNDED FOLLOWING)
  Pattern: down+" up+          -- " = 흡수 판정점
  Nav Mark Lookback: 1            -- PREV(price) → 1 행 후방
  NFA States: 4 peak, 312 total, 87 merged
  NFA Contexts: 3 peak, 101 total, 47 pruned
  NFA: 12 matched (len 4/18/7.3), 35 mismatched (len 1/3/1.4)
  NFA: 21 absorbed (len 2/15/4.2), 12 skipped (len 0/0/0)
  -> Sort
       Sort Key: ticks.ts
       -> Seq Scan on public.ticks

각 항목의 의미는 다음과 같다.

성능 진단의 핵심은 단순하다 — matched 와 absorbed 의 비중이 크면 NFA 가 효율적으로 동작 중이다. mismatched 의 카운트나 길이가 비정상적으로 크면 매치되지 않는 경로를 길게 추적하고 있다는 뜻이다. States/Contexts 의 peak 가 데이터 크기에 비례해 증가하면 흡수가 작동하지 않는 패턴일 가능성이 크다 — 매치 시작 의존 술어나 reluctant 한정자, 고정 한정자가 흡수를 막고 있는지 확인해야 한다.

§5. 로드맵

현 구현의 R020 핵심 기능을 land 한 뒤에 남는 작업은 크게 세 갈래로 나뉜다 — 단독 패치로 진행 가능한 독립 항목, match history 인프라 선행이 필요한 의존 항목, 그리고 R010 MATCH_RECOGNIZE 본체다. 그 옆에 표준 자체가 금지하는 항목과 PostgreSQL 정책으로 거부하기로 한 항목이 별도로 있다.

5.1 Match History 독립 항목

이 그룹은 현재 NFA 위에 바로 land 가능한 기능이다. 각 항목은 독립 패치로 진행할 수 있고, 머지 시점도 서로 묶이지 않는다.

5.2 Match History 의존 항목

§2.5 에서 설명한 match history 인프라 — "어느 행이 어느 패턴 변수에 매핑됐는가" 를 매치 단위로 보존하는 자료구조 — 가 선행되어야 land 가능한 기능들이다. 인프라 패치 한 번을 land 하면 아래 항목 모두가 조각 패치로 분할되어 빠르게 따라온다.

5.3 R010 — MATCH_RECOGNIZE 본체

R010 MATCH_RECOGNIZE 는 R020 와 동일한 정규식·네비게이션 엔진 위에 올라간다. match history 인프라가 갖춰진 뒤 land 자체는 가능하지만, 채택 여부는 PostgreSQL 커뮤니티의 정책 결정 사안이다 — 새 구문 도입의 크기, SQL 표준위원회 동향, R020 만으로 충분한지의 판단이 함께 걸린다.

R010 이 도입되면 R020 에 없는 몇 가지 기능이 따라온다 — ONE / ALL ROWS PER MATCH 와 그 3 옵션(SHOW EMPTY · OMIT EMPTY · WITH UNMATCHED ROWS), PATTERN 내 anchors ^ / $ 허용, {- ... -} exclusion (매치는 인식하되 출력에서 제외) 등이다.

5.4 표준이 금지하는 것

"거부" 라고 부르지만 실제로는 표준이 명시 금지한 항목이고, parser 단계에서 차단되는 것이다. 표준이 그렇게 못 박은 이유는 모호성을 피하거나 R020 의 window-frame 의미론에 맞지 않기 때문이다.

• 윈도우 프레임 — RANGE / GROUPS 금지 (ROWS only). 시작점은 CURRENT ROW 외 불가. EXCLUDE NO OTHERS 외 옵션 불가.
• PATTERN — anchors ^ / $ 금지 (R020 한정), 수량자 직접 중첩 A+ + 금지.
• Navigation 중첩 — 4 가지 compound form (외부 행 기준 PREV/NEXT × 내부 매치 기준 FIRST/LAST) 외 모든 조합 거부 (같은 종류, 매치 기준끼리, 역방향, 3 단 이상, 중간 표현식 삽입 모두 포함).
• DEFINE — outer / range-qualified 컬럼 참조 금지, 변수 중복 정의 금지.
• Recursive query 안의 RPR — WITH RECURSIVE 안에서 RPR 사용 금지 (ISO/IEC 9075-2 7.17 SR 3)e)f)).
• {- -} exclusion — R010 전용 기능, R020 에서는 의미 없음.

5.5 PG 정책으로 거부하는 것

표준이 명시 금지하지는 않지만, PostgreSQL 의 결정성·부작용 원칙에 따라 거부하기로 한 항목이다. 향후 정책 재검토는 열려 있지만 현 구현은 다음을 막는다.

• DEFINE 안의 volatile 함수 — 표준은 navigation offset 인수에 한해서만 결정성을 요구하지만 PG 는 DEFINE 전체로 확장. 매치 결과의 reproducibility 와 plan 안정성을 우선한 결정이다.
• DEFINE 안의 sequence (nextval()) — 부작용 차단.
• DEFINE 안의 subquery — 표준은 (a) 중첩 RPR 없음 + (b) outer pattern variable 미참조 조건부 허용. 현 PostgreSQL 은 정적 검사 부재로 일괄 거부 — §5.1 에서 조건부 허용으로 완화 예정.

5.6 다음 단계

2026-07 PG20-1 CommitFest 진입을 기점으로 리뷰 사이클이 다시 돌기 시작한다. 메인 라인 머지 시점에 도달하면, 위 분류대로 독립 항목은 항목별 단독 패치로, 의존 항목은 match history 인프라 패치를 먼저 land 한 뒤 조각 패치로 분할되어 진행된다. R010 본체는 그 다음 단계의 정책 결정 사안이다.