================================================================================ PostgreSQL Row Pattern Recognition: Flat-Array Stream NFA 해설서 ================================================================================ 대상 독자: PostgreSQL 실행기(executor) 및 플래너(planner) 구조에 기본적인 이해가 있는 개발자 범위: PATTERN/DEFINE 절의 파싱부터 NFA 런타임 실행까지 전 과정 관련 코드: - src/backend/parser/parse_rpr.c (파서 단계) - src/backend/optimizer/plan/rpr.c (옵티마이저 단계) - src/backend/executor/nodeWindowAgg.c (실행기 단계) - src/include/nodes/plannodes.h (계획 노드 정의) - src/include/nodes/execnodes.h (실행 상태 정의) - src/include/optimizer/rpr.h (타입 및 상수) ================================================================================ Flat-Array Stream NFA란? 본 구현의 NFA는 전통적인 상태 전이 그래프가 아닌 16바이트 고정 크기 요소의 평탄 배열(flat array)로 표현된다. 실행 시에는 행 스트림을 전방 전용(forward-only)으로 처리하며, 역추적(backtracking) 없이 엡실론 전이를 즉시 확장하는 방식으로 동작한다. - Flat-Array: 패턴을 그래프가 아닌 평탄 배열로 컴파일 (제IV장) - Stream: 행을 한 방향으로 순차 소비하며, 되돌아가지 않음 (제XII장) - NFA: 하나의 컨텍스트 내에 복수 상태가 공존하는 비결정적 실행 (제VI장) 제I장 Row Pattern Recognition 개요 ================================================================================ Row Pattern Recognition(이하 RPR)은 SQL:2016에서 도입된 기능으로, 순서가 있는 행 집합에서 정규 표현식 기반의 패턴을 매칭한다. SQL 표준은 두 가지 형태를 정의한다: Feature R010: MATCH_RECOGNIZE (FROM 절) - 전용 테이블 연산자 - MATCH_NUMBER(), CLASSIFIER() 등 전용 함수 제공 - ONE ROW PER MATCH / ALL ROWS PER MATCH 선택 가능 Feature R020: RPR in a window (WINDOW 절) - 기존 윈도우 함수 프레임워크에 통합 - ALL ROWS PER MATCH만 지원 - MATCH_NUMBER() 없음 본 구현은 Feature R020을 대상으로 한다. 기본 구문은 다음과 같다: SELECT ... OVER ( PARTITION BY ... ORDER BY ... ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING [INITIAL | SEEK] -- SEEK는 표준에 정의되어 있으나 미구현 AFTER MATCH SKIP TO NEXT ROW | SKIP PAST LAST ROW PATTERN ( <정규표현식> ) DEFINE <변수> AS <조건>, ... ) PATTERN 절은 행 변수들의 정규표현식이다. DEFINE 절은 각 변수가 현재 행에서 참(true)인지 판별하는 불리언 조건이다. 예시: PATTERN (A+ B) DEFINE A AS price > PREV(price), B AS price < PREV(price) 이 패턴은 "가격이 연속 상승하다가 하락하는 구간"을 매칭한다. 제II장 전체 처리 파이프라인 ================================================================================ RPR 처리는 세 단계로 나뉜다: ┌─────────────────────────────────────────────────────────┐ │ 1. 파싱 (Parser) │ │ SQL 텍스트 → PATTERN AST + DEFINE 표현식 트리 │ │ │ │ 2. 컴파일 (Optimizer/Planner) │ │ PATTERN AST → 최적화 → 평탄 NFA 요소 배열 │ │ │ │ 3. 실행 (Executor) │ │ NFA 시뮬레이션으로 행 단위 매칭 │ └─────────────────────────────────────────────────────────┘ 각 단계는 독립적인 자료구조를 사용하며, 단계 간 인터페이스는 명확하다: 파서 → 플래너: WindowClause.rpPattern (RPRPatternNode 트리) WindowClause.defineClause (TargetEntry 리스트) 플래너 → 실행기: WindowAgg.rpPattern (RPRPattern 구조체) WindowAgg.defineClause (TargetEntry 리스트) 제III장 파싱 단계 ================================================================================ III-1. 진입점 transformWindowDefinitions() (parse_clause.c) └─ transformRPR() (parse_rpr.c) transformRPR()는 RPCommonSyntax가 존재하면 호출되며, 다음을 수행한다: (1) 프레임 옵션 검증 - ROWS만 허용 (RANGE, GROUPS 불가) - 시작 경계는 CURRENT ROW만 허용 - EXCLUDE 옵션 불허 (2) WindowClause로 정보 전사 - rpPattern, rpSkipTo, initial 필드 복사 (3) DEFINE 절 변환 (transformDefineClause) III-2. PATTERN AST 파서는 PATTERN 절을 RPRPatternNode 트리로 변환한다. 각 노드의 타입은 다음 네 가지이다: RPR_PATTERN_VAR 변수 참조. varName 필드에 이름 저장. RPR_PATTERN_SEQ 연결(concatenation). children에 자식 노드 리스트. RPR_PATTERN_ALT 교대(alternation). children에 분기 노드 리스트. RPR_PATTERN_GROUP 그룹(괄호). children에 본문 노드 리스트. 모든 노드에 min/max 필드가 있어 수량자를 표현한다: A → VAR(A, min=1, max=1) A+ → VAR(A, min=1, max=INF) A* → VAR(A, min=0, max=INF) A? → VAR(A, min=0, max=1) A{3,5} → VAR(A, min=3, max=5) reluctant 필드가 -1이 아니면 비탐욕적(reluctant) 수량자이다. 예시: PATTERN ((A+ B) | C*) ALT ├─ SEQ │ ├─ VAR(A, 1, INF) │ └─ VAR(B, 1, 1) └─ VAR(C, 0, INF) III-3. DEFINE 절 변환 transformDefineClause()는 각 DEFINE 변수를: (1) 변수명 중복 검사 (2) 표현식을 일반 SQL 표현식으로 변환 (3) Boolean 타입 강제 (coerce_to_boolean) (4) TargetEntry로 래핑, resname에 변수명 설정 PATTERN에서 사용되었지만 DEFINE에 정의되지 않은 변수는 암묵적으로 TRUE로 평가된다 (모든 행에 매칭). 제IV장 컴파일 단계 ================================================================================ IV-1. 진입점 create_windowagg_plan() (createplan.c) ├─ collectPatternVariables() 변수명 수집 ├─ filterDefineClause() 미사용 DEFINE 제거 └─ buildRPRPattern() NFA 컴파일 (6단계) IV-2. buildRPRPattern()의 6단계 Phase 1: AST 최적화 (optimizeRPRPattern) Phase 2: 통계 수집 (scanRPRPattern) Phase 3: 메모리 할당 (allocateRPRPattern) Phase 4: NFA 요소 채우기 (fillRPRPattern) Phase 5: 최종화 (finalizeRPRPattern) Phase 6: 흡수 가능성 분석 (computeAbsorbability) IV-3. Phase 1: AST 최적화 파서가 생성한 AST를 복사한 후, 다음 최적화를 적용한다: (a) SEQ 평탄화: 중첩된 SEQ를 펼침 SEQ(A, SEQ(B, C)) → SEQ(A, B, C) (b) 연속 변수 병합: 같은 변수의 연속 출현을 단일 수량자로 A A → A{2} A{2,3} A{1,2} → A{3,5} (c) 연속 그룹 병합: 동일한 그룹의 반복을 병합 (A B)+ (A B)+ → (A B){2,INF} (d) 연속 ALT 병합: 동일한 ALT의 반복을 병합 (A | B) (A | B) (A | B) → (A | B){3} (e) 프리픽스/서픽스 흡수: 그룹 앞뒤의 동일 시퀀스를 흡수 A B (A B)+ → (A B){2,INF} (f) ALT 평탄화 및 중복 제거 (A | (B | C)) → (A | B | C) (A | B | A) → (A | B) (g) 수량자 곱셈: 안전한 경우 중첩 수량자를 단일화 (A+)+ → A+ (A{2,3}){5} → A{10,15} (h) 단일 자식 언래핑 SEQ(A) → A, (A){1,1} → A IV-4. Phase 4: NFA 요소 배열 생성 최적화된 AST를 RPRPatternElement의 평탄 배열로 변환한다. 이것이 런타임에서 NFA 시뮬레이션에 사용되는 핵심 자료구조이다. RPRPatternElement 구조 (16바이트): 필드 크기 설명 ───────────────────────────────────────────────────── varId 1B 변수 ID (0-251) 또는 제어 코드 (252-255) depth 1B 그룹 중첩 깊이 flags 1B 비트 플래그 (아래 참조) reserved 1B 패딩 min 4B 수량자 최솟값 max 4B 수량자 최댓값 next 2B 다음 요소 인덱스 (순차 흐름) jump 2B 분기 대상 인덱스 (ALT/GROUP용) 제어 코드: RPR_VARID_BEGIN (252) 그룹 시작 마커 RPR_VARID_END (253) 그룹 종료 마커 RPR_VARID_ALT (254) 교대 시작 마커 RPR_VARID_FIN (255) 패턴 완료 마커 요소 플래그 (1바이트, 비트마스크): 비트 상수 설정 대상 설명 -------------------------------------------------------------------------- 0x01 RPR_ELEM_RELUCTANT VAR, BEGIN, 비탐욕(non-greedy) 수량자. END 짧은 매치 우선: 루프 탈출을 먼저 시도한 후 반복. 단순 변수(A+?)는 VAR에, 그룹((...)+?)은 BEGIN+END에 설정 0x02 RPR_ELEM_EMPTY_LOOP END 그룹 본체가 빈 매치를 생성할 수 있음 (모든 자식이 nullable). 정상 루프백과 함께 빠른 전진 탈출 클론을 생성하여 사이클 감지가 정상 매칭을 제거하지 않도록 보장. (IV-4b) 0x04 RPR_ELEM_ABSORBABLE_BRANCH VAR, BEGIN, 흡수 가능 영역 내 요소 표시. END, ALT 런타임에 현재 NFA 상태가 흡수 가능 컨텍스트에 있는지 추적하는 데 사용 0x08 RPR_ELEM_ABSORBABLE VAR, END 흡수 판정 지점. 연속 반복 간 흡수 비교를 수행할 위치를 표시. - 단순 무한 VAR (A+): VAR 요소 자체에 설정 - 무한 GROUP ((A B)+): END 요소에만 설정 접근자 매크로: RPRElemIsReluctant(e) (e)->flags & 0x01 RPRElemCanEmptyLoop(e) (e)->flags & 0x02 RPRElemIsAbsorbableBranch(e) (e)->flags & 0x04 RPRElemIsAbsorbable(e) (e)->flags & 0x08 예시: PATTERN (A+ B | C) AST: ALT(SEQ(VAR(A,1,INF), VAR(B,1,1)), VAR(C,1,1)) 컴파일 결과: idx varId depth min max next jump 설명 ─────────────────────────────────────────────────── 0 ALT 0 1 1 1 -1 교대 시작 1 A(0) 1 1 INF 2 3 분기1: A+ 2 B(1) 1 1 1 4 -1 분기1: B → FIN 3 C(2) 1 1 1 4 -1 분기2: C → FIN 4 FIN 0 1 1 -1 -1 패턴 완료 - idx 0: ALT 마커. next(=1)은 첫 분기 시작 - idx 1: A 변수. next(=2)는 B, jump(=3)는 둘째 분기 시작 - idx 2: B 변수. next(=4)는 FIN - idx 3: C 변수. next(=4)는 FIN - idx 4: FIN 마커. 매칭 성공 신호 next와 jump의 역할: - next: 현재 요소를 "소비한 후" 이동할 다음 요소. VAR의 경우 매칭 성공 후의 다음 위치. BEGIN/END의 경우 그룹 내부/외부의 다음 위치. - jump: "건너뛸" 대상 요소. ALT의 각 분기에서 다음 분기로의 점프. BEGIN에서 END+1로의 스킵 (min=0인 그룹). END에서 그룹 본문 시작으로의 루프백. 예시: PATTERN ((A B)+) idx varId depth min max next jump 설명 ─────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 4 그룹 시작 1 A(0) 1 1 1 2 -1 A 2 B(1) 1 1 1 3 -1 B 3 END 0 1 INF 4 1 그룹 종료 4 FIN 0 1 1 -1 -1 패턴 완료 - idx 0: BEGIN. next(=1)은 그룹 본문 진입. jump(=4)는 END 다음 = FIN으로 스킵 (min=0이면 사용). - idx 3: END. next(=4)는 그룹 밖으로 탈출. jump(=1)은 그룹 본문 시작으로 루프백. IV-4a. Reluctant 플래그 (RPR_ELEM_RELUCTANT) Reluctant 플래그는 Phase 4(fillRPRPattern)에서 AST 노드의 reluctant 필드가 음이 아닌 경우(reluctant >= 0) 설정된다. 런타임에서 수량자 확장의 우선순위를 역전시킨다: 탐욕(기본): 루프백을 먼저 시도한 후 탈출 (긴 매치 선호) 비탐욕: 탈출을 먼저 시도한 후 루프백 (짧은 매치 선호) 수량자를 담당하는 모든 요소에 플래그가 설정된다: 단순 VAR (A+?): VAR 요소에 RPR_ELEM_RELUCTANT 설정 그룹 ((...)+?): BEGIN과 END 요소에 RPR_ELEM_RELUCTANT 설정 런타임(nfa_advance)에서 플래그가 DFS 탐색 순서를 제어한다: 수량자가 있는 VAR: 탐욕: 우선 경로 = next (계속), 복제 = jump (건너뛰기) 비탐욕: 우선 경로 = jump (건너뛰기), 복제 = next (계속) END 요소: 탐욕: 우선 경로 = jump (루프백), 복제 = next (탈출) 비탐욕: 우선 경로 = next (탈출), 복제 = jump (루프백) BEGIN (min=0): 탐욕: 우선 경로 = next (그룹 진입), 복제 = jump (건너뛰기) 비탐욕: 우선 경로 = jump (건너뛰기), 복제 = next (그룹 진입) 흡수 최적화는 탐욕 수량자를 필요로 한다. 비탐욕 수량자는 흡수 가능성 분석에서 제외된다(IV-5 참조). IV-4b. Empty Loop 플래그 (RPR_ELEM_EMPTY_LOOP) Empty-loop 플래그는 Phase 4(fillRPRPatternGroup)에서 그룹 본체가 nullable일 때 -- 즉, 본체의 모든 경로가 0행 매치가 가능할 때 (모든 자식이 nullable) -- END 요소에 설정된다. 이 플래그가 설정되는 예시 패턴: (A?)* A가 nullable(min=0)이므로 그룹 본체가 nullable -> END에 플래그 설정 (A? B?)+ 모든 자식이 nullable -> 본체 nullable -> END에 플래그 설정 (A | B*) B*가 nullable이므로 ALT가 nullable -> END에 플래그 설정 이 플래그는 제로 소비 사이클 감지(elemIdx 방문 비트맵)와 연동하여 동작한다. 이 플래그가 없으면 사이클 감지만으로는 정상적인 매칭이 실패할 수 있다. 문제 예시: (A*){2,3} - 반복 1: A*가 가용한 모든 행 소비 -> count=1, END 도달 - 반복 2로 루프백: A*가 0행 매치 -> END 재도달 - 사이클 감지가 동일 행에서 같은 elemIdx 재방문 감지 -> 상태 제거 - count가 min(2)에 미도달 -> 매칭 실패 (오류) RPR_ELEM_EMPTY_LOOP 플래그가 있으면 nfa_advance_end는 두 경로를 생성한다: 정상적인 루프백(사이클 감지가 결국 제거)과 루프를 완전히 우회하는 빠른 전진 탈출 클론. (상세 런타임 동작은 IX-4(c) 참조.) IV-5. 흡수 가능성 분석 (RPR_ELEM_ABSORBABLE) 컨텍스트 흡수(Context Absorption)는 O(n²) → O(n) 최적화 기법이다. (런타임 동작은 제VIII장에서 설명.) 이 단계에서는 패턴이 흡수 최적화에 적합한 구조인지 판별하고, 해당 요소에 플래그를 설정한다: RPR_ELEM_ABSORBABLE 흡수 비교 지점 RPR_ELEM_ABSORBABLE_BRANCH 흡수 가능 영역의 요소 적합 조건: (1) SKIP PAST LAST ROW (NEXT ROW가 아닌 경우) (2) 프레임 끝이 UNBOUNDED FOLLOWING 구조적 조건 (isUnboundedStart + computeAbsorbabilityRecursive): Case 1: 단순 VAR+ (예: A+) → VAR에 ABSORBABLE | ABSORBABLE_BRANCH 설정 Case 2: GROUP+ 내부가 {1,1} VAR들로만 구성 (예: (A B)+) → 자식들에 ABSORBABLE_BRANCH, END에 ABSORBABLE | ABSORBABLE_BRANCH 설정 Case 3: GROUP+ 본문이 VAR+로 시작 (예: (A+ B)+) → BEGIN에서 본문으로 재귀하여 Case 1 적용. A에 ABSORBABLE | ABSORBABLE_BRANCH 설정. B, END에는 플래그 없음 → B로 진행하면 흡수 중단. 흡수 가능성은 패턴 단위가 아니라 요소(element) 단위로 판정된다. RPR_ELEM_ABSORBABLE 플래그가 설정된 요소에 상태가 있을 때만 흡수 비교가 수행되며, 해당 영역을 벗어나면 흡수가 영구 중단된다. 이 메커니즘에 의해, 런타임에서 "먼저 시작한 컨텍스트가 나중 시작 컨텍스트를 항상 포함한다"는 단조성(monotonicity)을 보장한다. 제V장 NFA 런타임 자료구조 ================================================================================ V-1. RPRNFAState — NFA 상태 하나의 NFA 상태는 "패턴의 어디까지 진행했는가"를 나타낸다. 필드 설명 ───────────────────────────────────────────────────── elemIdx 현재 위치한 패턴 요소의 인덱스 counts[] 각 그룹 깊이별 반복 횟수 isAbsorbable 흡수 가능 영역에 있는지 여부 next 연결 리스트의 다음 상태 counts 배열의 크기는 (maxDepth + 1)이며, 구조체 끝에 가변 길이로 할당된다 (flexible array member). 예시: PATTERN ((A B)+ C)에서 3번째 반복의 B를 기다리는 상태 요소 배열: [0:BEGIN(d0) 1:A(d1) 2:B(d1) 3:END(d0) 4:C(d0) 5:FIN] elemIdx = 2 (B, depth 1) counts[0] = 2 (depth 0: END의 깊이. 그룹 2회 반복 완료) counts[1] = 1 (depth 1: B의 깊이. 현재 반복에서 A 매칭) 카운트는 elemIdx가 아닌 depth로 인덱싱된다. counts[0]은 END(depth 0) 통과 시 증가하며, 상태가 B(depth 1)에 있어도 그룹 반복 횟수를 보존한다. 두 상태가 "같다(equal)"의 정의: elemIdx가 같고, 해당 요소의 depth까지의 counts가 같으면 동일하다. nfa_states_equal()에서 counts[0..elem->depth]를 memcmp로 비교한다. 현재 요소의 깊이 이하의 카운트만 의미가 있기 때문이다. V-2. RPRNFAContext — 매칭 컨텍스트 하나의 컨텍스트는 "특정 시작 행에서 시작된 매칭 시도"를 나타낸다. 필드 설명 ───────────────────────────────────────────────────── states 활성 NFA 상태들의 연결 리스트 matchStartRow 매칭이 시작된 행 번호 matchEndRow 매칭이 완료된 행 번호 (-1이면 미완료) lastProcessedRow 마지막으로 처리한 행 matchedState FIN에 도달한 상태 (greedy 폴백용) hasAbsorbableState 이 컨텍스트가 다른 컨텍스트를 흡수할 수 있는지 allStatesAbsorbable 이 컨텍스트가 흡수당할 수 있는지 next, prev 양방향 연결 리스트 NFA는 비결정적(nondeterministic)이므로 하나의 컨텍스트 안에 여러 상태가 동시에 존재할 수 있다. 예시: PATTERN (A | B) C에서, 첫 행이 A와 B 모두에 매칭되면 컨텍스트 안에 두 개의 상태가 공존한다: 상태1: elemIdx=3 (C를 기다림, A 분기 경유) 상태2: elemIdx=3 (C를 기다림, B 분기 경유) 이 경우 두 상태의 (elemIdx, counts)가 같으므로 nfa_add_state_unique()에 의해 먼저 추가된 상태1(A 분기)만 유지된다. DFS가 ALT의 첫 분기부터 처리하므로 A 경유 상태가 먼저 등록되고, B 경유 상태는 중복으로 폐기된다. 이것이 우선성(preferment) 보장이다. V-3. WindowAggState의 RPR 필드 nfaContext / nfaContextTail 활성 컨텍스트의 양방향 연결 리스트 nfaContextFree 재사용 컨텍스트 풀 nfaStateFree 재사용 상태 풀 nfaVarMatched 행별 캐시: varMatched[varId] nfaVisitedElems 사이클 감지용 비트맵 nfaStateSize RPRNFAState의 사전 계산 크기 메모리 관리: 상태와 컨텍스트는 자체 free-list를 통해 관리된다. palloc 대신 재사용 풀에서 가져오고, 해제 시 풀로 반환한다. 이는 빈번한 할당/해제의 오버헤드를 줄인다. 제VI장 NFA 실행: 3단계 모델 ================================================================================ VI-1. 진입점과 전체 흐름 윈도우 함수가 각 행을 처리할 때, row_is_in_reduced_frame()이 호출된다. 이 함수는 현재 행이 매칭된 프레임에 속하는지 판별하며, 필요하면 update_reduced_frame()을 호출하여 NFA를 구동한다. update_reduced_frame()의 흐름: (1) 대상 행의 컨텍스트를 찾거나 새로 생성 (2) 행 처리 루프 진입 (3) 루프 종료 후 결과를 reduced_frame_map에 기록 행 처리 루프의 의사 코드: targetCtx = nfa_get_head_context(pos) if targetCtx == NULL: targetCtx = nfa_start_context(pos) for currentPos = startPos ... if not nfa_evaluate_row(currentPos): -- 행이 존재하지 않으면 nfa_finalize_all_contexts() -- 모든 컨텍스트 완료 처리 break nfa_process_row(currentPos) -- 3단계 처리 nfa_start_context(currentPos + 1) -- 다음 시작점 미리 생성 nfa_cleanup_dead_contexts() -- 죽은 컨텍스트 제거 if targetCtx->states == NULL: -- 대상 컨텍스트 소진 break 핵심: 하나의 행을 처리하기 위해 여러 행을 앞서 처리할 수 있다. 윈도우 함수 특성상, 행 N의 프레임을 결정하려면 N 이후의 행들도 봐야 하기 때문이다. VI-2. 컨텍스트 생성: nfa_start_context() 새 컨텍스트를 생성하고 초기 advance를 수행한다. (1) nfa_context_alloc()으로 컨텍스트 할당 (2) matchStartRow = pos 설정 (3) 초기 상태 생성: elemIdx=0 (패턴 첫 요소), counts=all zero (4) nfa_advance(initialAdvance=true) 호출 초기 advance는 패턴 시작 부분의 엡실론 전이를 확장한다. 예를 들어 PATTERN ((A | B) C)의 초기 advance: 시작: elemIdx=0 (ALT) → ALT 분기 확장 → elemIdx=1 (A) — VAR이므로 상태 추가, 여기서 멈춤 → elemIdx=2 (B) — VAR이므로 상태 추가, 여기서 멈춤 결과: 컨텍스트에 두 개의 상태 {A를 기다림, B를 기다림} 초기 advance에서는 FIN에 도달해도 매칭으로 기록하지 않는다. 이는 빈 매칭(zero-length match)을 방지하기 위함이다. VI-3. 행 평가: nfa_evaluate_row() 현재 행에 대해 DEFINE 절의 모든 변수 조건을 한 번에 평가한다. for each defineClause[i]: result = ExecEvalExpr(defineClause[i]) varMatched[i] = (not null and true) PREV(), NEXT() 등 행 네비게이션 연산자를 지원하기 위해 이전 행, 현재 행, 다음 행을 각각 다른 슬롯에 설정한다: ecxt_scantuple = 이전 행 (PREV 참조용) ecxt_outertuple = 현재 행 (기본 참조) ecxt_innertuple = 다음 행 (NEXT 참조용) varMatched 배열은 이후 Phase 1(Match)에서 참조된다. VI-4. nfa_process_row(): 3단계 처리 한 행에 대한 NFA 처리는 세 단계로 나뉜다: ┌────────────────────────────────────────────┐ │ Phase 1: MATCH (수렴) │ │ 현재 행과 각 VAR 상태를 대조. │ │ 매칭 실패한 상태를 제거. │ │ │ │ Phase 2: ABSORB (흡수) │ │ 중복 컨텍스트를 병합하여 상태 폭발 방지. │ │ │ │ Phase 3: ADVANCE (확장) │ │ 엡실론 전이를 확장하여 다음 행을 준비. │ └────────────────────────────────────────────┘ 이 순서가 중요하다: - Match가 먼저 실행되어 "현재 행을 소비"한다. - Absorb는 Match 직후, 상태가 업데이트된 시점에서 수행한다. - Advance는 마지막에 실행하여 "다음 행을 기다리는 상태"를 준비한다. 제VII장 Phase 1: Match ================================================================================ nfa_match()는 컨텍스트의 각 상태를 순회하며: (1) 상태의 elemIdx가 VAR 요소인지 확인 (2) nfa_eval_var_match()로 현재 행과 대조 (3) 매칭 성공: 반복 카운트 증가, 상태 유지 (4) 매칭 실패: 상태 제거 매칭 판정 (nfa_eval_var_match): varId가 defineVariableList의 범위 내이면: varMatched[varId]의 값 사용 varId가 범위를 초과하면 (DEFINE에 정의되지 않은 변수): 무조건 true (모든 행에 매칭) 간단한 VAR의 즉시 advance: min=1, max=1인 VAR이고 다음 요소가 END인 경우, Match 단계에서 바로 END까지 처리한다. 이는 Phase 2(Absorb)에서 정확한 상태 비교를 위해 필요하다. 예: PATTERN ((A B)+)에서 A가 매칭되면 즉시 B로 advance하고, B가 매칭되면 즉시 END까지 진행하여 그룹 카운트를 완료한다. 그래야 다른 컨텍스트와의 흡수 비교가 가능하다. 제VIII장 Phase 2: Absorb (컨텍스트 흡수) ================================================================================ VIII-1. 문제 현재 구현에서는 처리하는 각 행마다 새 컨텍스트를 시작한다. PATTERN (A+)를 10행에 적용하면 10개의 컨텍스트가 생기고, 각 컨텍스트는 독립적으로 상태를 추적한다. 행이 N개이면 총 상태 수는 O(N²)이 된다: 컨텍스트1 (행1 시작): A를 N번 매칭 가능 컨텍스트2 (행2 시작): A를 N-1번 매칭 가능 ... 컨텍스트N (행N 시작): A를 1번 매칭 가능 VIII-2. 해법: 컨텍스트 흡수 핵심 관찰: 먼저 시작한 컨텍스트는 나중 시작 컨텍스트의 모든 매칭을 포함한다 (단조성 원리). 컨텍스트1이 행1에서 시작하여 A를 5번 매칭했다면, 컨텍스트2(행2 시작)가 A를 4번 매칭한 상태는 컨텍스트1에 이미 포함되어 있다. 따라서 컨텍스트2는 컨텍스트1에 "흡수"될 수 있다. VIII-3. 흡수 조건 (1) 패턴이 isAbsorbable로 표시됨 (IV-5 참조) (2) 대상 컨텍스트의 allStatesAbsorbable이 true (3) 더 이전 컨텍스트가 대상의 모든 상태를 "커버"함 커버 조건 (nfa_states_covered): 더 이전 컨텍스트에 같은 elemIdx의 상태가 존재하고, 해당 깊이의 카운트가 더 크거나 같으면 커버된다. VIII-4. 이중 플래그 설계 두 개의 불리언 플래그로 흡수 판단을 효율화한다: hasAbsorbableState (단조적: true→false만 가능) "이 컨텍스트가 다른 컨텍스트를 흡수할 능력이 있는가?" 흡수 가능 상태가 하나라도 있으면 true. 상태가 제거되어 흡수 가능 상태가 없어지면 false로 전환. 한번 false가 되면 다시 true가 되지 않는다. allStatesAbsorbable (동적: 변동 가능) "이 컨텍스트가 흡수당할 수 있는가?" 모든 상태가 흡수 가능 영역에 있으면 true. 비흡수 상태가 추가되면 false, 그것이 제거되면 다시 true. VIII-5. 흡수 순서 nfa_absorb_contexts()는 테일(최신)에서 헤드(최고참)로 순회한다. for ctx = tail to head: if ctx.allStatesAbsorbable: for older = ctx.prev to head: if older.hasAbsorbableState: if nfa_states_covered(older, ctx): free(ctx) -- 흡수됨 break 최신 컨텍스트부터 검사하므로, 가장 최근에 시작된 (= 가장 짧은 매칭을 가진) 컨텍스트가 먼저 흡수된다. 제IX장 Phase 3: Advance (엡실론 전이 확장) ================================================================================ IX-1. 개요 nfa_advance()는 Match 후의 각 상태에서 엡실론 전이를 확장하여, "다음 행을 기다리는 새로운 상태들"을 생성한다. 엡실론 전이란 행을 소비하지 않고 이동하는 전이이다: - ALT: 각 분기로 분기 - BEGIN: 그룹 진입 (또는 min=0이면 스킵) - END: 그룹 루프백 (또는 조건 충족 시 탈출) - FIN: 매칭 완료 기록 - VAR의 loop/exit: 수량자에 따른 반복/탈출 VAR 요소에 도달하면 확장을 멈추고 상태를 추가한다. VAR은 "다음 행을 소비할" 요소이기 때문이다. IX-2. 처리 순서: DFS와 우선성(Preferment) advance는 상태들을 어휘적 순서(lexicographic order)로 처리하며, 각 상태에 대해 깊이 우선 탐색(DFS)을 수행한다. 이 DFS 순서가 곧 SQL 표준의 "우선성(preferment)"을 보장한다: PATTERN 텍스트에서 먼저 나타나는 분기가 우선한다. 예시: PATTERN (A | B) C ALT의 첫 분기 A가 둘째 분기 B보다 우선한다. A와 B가 모두 매칭 가능할 때, A 경유 매칭이 선택된다. nfa_add_state_unique()가 동일한 상태의 중복 추가를 방지하므로, 먼저 추가된 (= 우선 분기의) 상태가 유지된다. IX-3. 라우팅 함수: nfa_route_to_elem() advance 단계의 모든 요소 간 전이는 nfa_route_to_elem()을 경유한다. 이 함수는 다음 요소의 타입에 따라 동작을 분기한다: 다음 요소가 VAR이면: (1) 상태를 컨텍스트에 추가 (nfa_add_state_unique) (2) VAR의 min=0이면 스킵 경로도 추가 (next로 재귀) → 여기서 확장이 멈춘다 (VAR은 "다음 행을 소비할" 요소) 다음 요소가 비-VAR(ALT, BEGIN, END, FIN)이면: → nfa_advance_state()를 재귀 호출하여 계속 확장 이 구조 덕분에 advance는 VAR에 도달할 때까지 엡실론 전이를 재귀적으로 따라가며, VAR에서만 멈추는 일관된 동작을 보인다. IX-4. 요소별 advance 동작 (a) ALT (nfa_advance_alt) ALT 요소를 만나면 모든 분기를 순서대로 확장한다. 각 분기의 첫 요소는 jump 포인터로 연결되어 있다. idx=0 (ALT) → 분기1 시작(next) → 분기2 시작(jump) → ... 각 분기에 대해 nfa_advance_state()를 재귀 호출한다. (b) BEGIN (nfa_advance_begin) 그룹 진입을 처리한다. jump는 END 다음 요소(= 그룹 밖의 첫 요소)를 가리킨다. Greedy (기본): (1) 그룹 본문으로 진입 (next로 이동, 해당 depth 카운트 리셋) (2) min=0이면 그룹 스킵 경로도 추가 (jump로 이동) Reluctant: 순서 반전 — 스킵 경로를 먼저, 그룹 진입을 나중에. 스킵 경로가 FIN에 도달하면 그룹 진입 경로는 생성하지 않는다 (최단 매칭 우선). (c) END (nfa_advance_end) 그룹 종료를 처리한다. 반복 로직의 핵심이다. 현재 깊이의 카운트가 count라 하면: count < min: 루프백 (jump로 이동, 그룹 본문 반복) RPR_ELEM_EMPTY_LOOP 플래그가 설정된 경우: 루프백 외에 fast-forward 탈출 경로도 추가한다. 이는 본문이 빈 매칭을 생성하여 count가 영원히 min에 도달하지 못할 수 있기 때문이다. fast-forward는 counts[depth]를 0으로 리셋하고 next로 탈출한다 (나머지 필요 반복을 빈 매칭으로 간주). min <= count < max: Greedy: 루프백 우선, 탈출 나중 Reluctant: 탈출 우선, 루프백 나중 탈출 경로가 FIN에 도달하면 루프백을 생략. count >= max: 무조건 탈출 (next로 이동) 탈출 시: counts[depth] = 0으로 리셋하고, 다음 요소가 외부 END이면 외부 depth의 카운트를 증가시킨다. (d) VAR (nfa_advance_var) 수량자가 있는 VAR 요소의 반복/탈출을 처리한다. 현재 깊이의 카운트가 count라 하면: count < min: 무조건 루프 (같은 elemIdx에 머무름, 다음 행 대기) min <= count < max: Greedy: 루프 우선, 탈출(next) 나중 Reluctant: 탈출 우선, 루프 나중 탈출 경로가 FIN에 도달하면 루프를 생략. count >= max: 무조건 탈출 (next로 이동) 탈출 시: counts[depth] = 0으로 리셋한다. (e) FIN 매칭 성공. matchedState에 현재 상태를 이동하여 기록하고, matchEndRow를 현재 행으로 설정한다. FIN에 도달하면 아직 처리되지 않은 나머지 상태들을 모두 제거한다 (early termination). DFS 순서에 의해 FIN에 먼저 도달한 경로가 가장 높은 우선성을 가지므로, 나머지는 열등한 경로이다. 이것이 우선성(preferment) 보장의 핵심 메커니즘이다. SKIP PAST LAST ROW 모드에서는 FIN 도달 시, 매칭 범위 내에서 시작된 후속 컨텍스트들을 즉시 프루닝한다. IX-5. 상태 중복 제거: nfa_add_state_unique() 새 상태를 컨텍스트에 추가할 때, 기존 상태와 비교하여 동일한 상태가 이미 존재하면 추가하지 않는다. 비교 기준: elemIdx + counts[0..elem->depth] (V-1 참조) 이 중복 제거가 NFA의 상태 폭발을 억제하는 핵심 메커니즘이다. DFS 순서에 의해 우선 분기의 상태가 먼저 추가되므로, 후순위 분기의 동일 상태는 자동으로 폐기된다. IX-6. 사이클 감지: nfaVisitedElems 그룹 본문이 빈 매칭(zero consumption)을 생성할 수 있는 경우, END에서 루프백하면 무한 루프가 발생할 수 있다. 예시: PATTERN ((A?)*) A?는 min=0이므로 매칭 없이 통과 가능. 외부 그룹이 반복하면: BEGIN → A? skip → END → BEGIN → ... 이를 방지하기 위해: (1) 컴파일 시: 본문이 nullable한 그룹의 END에 RPR_ELEM_EMPTY_LOOP 플래그 설정. 이 플래그의 런타임 효과는 IX-4(c) 참조: count < min일 때 fast-forward 탈출 경로를 추가하여, 빈 매칭으로 count가 증가하지 못하는 교착을 해소한다. (2) 런타임 시: advance 내 각 상태의 DFS 확장 직전에 nfaVisitedElems 비트맵을 초기화한다 (상태별 1회). DFS 중 각 요소 방문 시 해당 elemIdx 비트를 설정. 이미 방문한 elemIdx에 재방문하면 해당 경로를 중단. 주의: 비트맵은 elemIdx만 추적하고 counts는 고려하지 않는다. 따라서 같은 elemIdx이지만 다른 counts를 가진 정당한 재방문도 차단될 수 있다. 이는 그룹 본문이 nullable(모든 경로가 빈 매치 가능)인 경우에만 발생하며, END -> loop-back -> skip -> END가 단일 DFS 내에서 순환한다. 이 경우 END 요소에 RPR_ELEM_EMPTY_LOOP 플래그가 설정되어 있으므로, fast-forward exit(IX-4(c))이 순환을 우회하는 대안 경로를 제공한다. 제X장 매칭 결과 처리 ================================================================================ X-1. Reduced Frame Map RPR 매칭 결과는 reduced_frame_map이라는 바이트 배열에 기록된다. 각 행에 대해 하나의 바이트가 할당되며, 값은 다음 중 하나이다: RF_NOT_DETERMINED (0) 아직 처리되지 않음 RF_FRAME_HEAD (1) 매칭의 시작 행 RF_SKIPPED (2) 매칭 내부 행 (프레임에서 건너뜀) RF_UNMATCHED (3) 매칭 실패 윈도우 함수는 이 맵을 참조하여 각 행의 프레임 포함 여부를 결정한다. X-2. AFTER MATCH SKIP 매칭 성공 후 다음 매칭 시도의 시작점을 결정한다: SKIP TO NEXT ROW: 매칭 시작 행의 다음 행부터 새 매칭 시도. 겹치는 매칭이 가능하다. SKIP PAST LAST ROW: 매칭 종료 행의 다음 행부터 새 매칭 시도. 겹치지 않는 매칭만 가능하다. X-3. INITIAL vs SEEK 표준 정의 (6.12절): INITIAL: 첫 행이 R인 매치를 찾는다. SEEK: R부터 전체 윈도우 프레임 끝까지 어디에서든 첫 번째 매치를 탐색한다. 어느 경우든, 매치가 없으면 축소된 윈도우 프레임은 비어 있다. 기본값은 INITIAL이다. 현재 구현: SEEK는 미지원 (파서가 에러를 발생시킨다). INITIAL만 지원하며, 각 행 pos에서 시작하는 매치만 탐색한다. 제XI장 구체적 예제: 전 과정 추적 ================================================================================ XI-1. 쿼리 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 (A+ B) DEFINE A AS price > PREV(price), B AS price < PREV(price) ); XI-2. 데이터 행번호 tdate price ────────────────────────── 0 2024-01-01 100 1 2024-01-02 110 2 2024-01-03 120 3 2024-01-04 115 4 2024-01-05 130 XI-3. 컴파일 결과 PATTERN (A+ B) → 최적화 후 그대로 idx varId depth min max next jump ────────────────────────────────────────── 0 A(0) 0 1 INF 1 -1 A+ 1 B(1) 0 1 1 2 -1 B 2 FIN 0 1 1 -1 -1 DEFINE: A → "price > PREV(price)", B → "price < PREV(price)" isAbsorbable = true (A+는 단순 무제한 VAR) XI-4. 실행 추적 --- 행 0 (price=100) --- update_reduced_frame(0) 호출. 컨텍스트C0 생성 (matchStartRow=0). 초기 advance: elemIdx=0(A) → VAR이므로 상태 추가. C0.states = [{elemIdx=0, counts=[0]}] nfa_evaluate_row(0): A: price(100) > PREV(price) → PREV 없음 → false B: price(100) < PREV(price) → PREV 없음 → false varMatched = [false, false] nfa_process_row(0): Phase 1 (Match): A(0) 상태 vs varMatched[0]=false → 상태 제거 C0.states = [] (빈 상태) Phase 2 (Absorb): 생략 (상태 없음) Phase 3 (Advance): 생략 (상태 없음) C0.states가 비었으므로 루프 종료. matchEndRow < matchStartRow → RF_UNMATCHED. register_reduced_frame_map(0, RF_UNMATCHED). --- 행 1 (price=110) --- update_reduced_frame(1) 호출. 컨텍스트C1 생성 (matchStartRow=1). 초기 advance: C1.states = [{elemIdx=0, counts=[0]}] nfa_evaluate_row(1): A: 110 > PREV(100) → true B: 110 < PREV(100) → false varMatched = [true, false] nfa_process_row(1): Phase 1 (Match): A(0) 매칭 성공 → counts[0]++ → counts=[1] C1.states = [{elemIdx=0, counts=[1]}] Phase 3 (Advance): 상태 {elemIdx=0, counts=[1]}: A+ (min=1, count=1, max=INF) count >= min이므로: Greedy → 루프 우선: {elemIdx=0, counts=[1]} 유지 탈출: counts[0]=0 리셋, next(=1) → {elemIdx=1, counts=[0]} C1.states = [{elemIdx=0, counts=[1]}, {elemIdx=1, counts=[0]}] --- 행 2 (price=120) --- 컨텍스트C2 생성 (matchStartRow=2). 초기 advance: C2.states = [{elemIdx=0, counts=[0]}] nfa_evaluate_row(2): A: 120 > PREV(110) → true B: 120 < PREV(110) → false varMatched = [true, false] C1 nfa_process_row(2): Phase 1 (Match): {elemIdx=0, counts=[1]}: A 매칭 → counts=[2] {elemIdx=1, counts=[0]}: B 미매칭 → 제거 C1.states = [{elemIdx=0, counts=[2]}] C2 nfa_process_row(2): Phase 1 (Match): {elemIdx=0, counts=[0]}: A 매칭 → counts=[1] C2.states = [{elemIdx=0, counts=[1]}] Phase 2 (Absorb): C1(먼저 시작)이 C2를 커버하는가? C1: {elemIdx=0, counts=[2]}, C2: {elemIdx=0, counts=[1]} 같은 elemIdx, C1.counts >= C2.counts → 커버됨 C2 흡수됨. → 제거. Phase 3 (Advance): {elemIdx=0, counts=[2]}: Greedy → 루프 + 탈출 루프: {elemIdx=0, counts=[2]} 탈출: counts[0]=0 리셋, next(=1) → {elemIdx=1, counts=[0]} C1.states = [{elemIdx=0, counts=[2]}, {elemIdx=1, counts=[0]}] 컨텍스트C3 생성 (matchStartRow=3). --- 행 3 (price=115) --- nfa_evaluate_row(3): A: 115 > PREV(120) → false B: 115 < PREV(120) → true varMatched = [false, true] nfa_process_row(3): Phase 1 (Match): {elemIdx=0, counts=[2]}: A 미매칭 → 제거 {elemIdx=1, counts=[0]}: B 매칭 → counts=[1] C1.states = [{elemIdx=1, counts=[1]}] Phase 3 (Advance): {elemIdx=1, counts=[1]}: B (min=1, max=1) count(1) >= max(1) → 무조건 탈출 counts[0]=0 리셋, next = 2 (FIN) FIN 도달 → matchEndRow = 3, matchedState 기록. early termination: 나머지 상태 없으므로 즉시 완료. C1.states = [] (FIN 도달 후 빈 상태) C1.states 비었고 matchEndRow=3 >= matchStartRow=1 → 매칭 성공. register_reduced_frame_map(1, RF_FRAME_HEAD) register_reduced_frame_map(2, RF_SKIPPED) register_reduced_frame_map(3, RF_SKIPPED) --- 행 4 (price=130) --- update_reduced_frame(4) 호출. C3이 이미 생성되어 있으나 matchStartRow=3이므로 해당 없음. 새 컨텍스트 C4 생성 (matchStartRow=4). nfa_evaluate_row(4): A: 130 > PREV(115) → true B: 130 < PREV(115) → false ... 이후 행이 없으므로 nfa_finalize_all_contexts() 호출. 매칭 미완료 → RF_UNMATCHED. XI-5. 최종 결과 행0: RF_UNMATCHED → 프레임 = 자기 자신 행1: RF_FRAME_HEAD → 프레임 = 행1~행3 행2: RF_SKIPPED → 행1의 매칭 내부 행3: RF_SKIPPED → 행1의 매칭 내부 행4: RF_UNMATCHED → 프레임 = 자기 자신 제XII장 핵심 설계 결정 요약 ================================================================================ XII-1. 평탄 배열 vs 트리 기반 NFA 선택: 평탄 배열 (RPRPatternElement[]) 이유: - 캐시 친화적: 16바이트 고정 크기, 연속 메모리 - 인덱스 기반 참조: 포인터 대신 2바이트 인덱스 - 직렬화 용이: 계획 노드로 전달 시 memcpy 가능 XII-2. Forward-only 실행 vs 백트래킹 선택: Forward-only (상태 집합 추적) 이유: - 백트래킹은 최악의 경우 지수적 시간 - NFA 시뮬레이션은 다항 시간 보장 - DFS 순서가 우선성(preferment)을 자연스럽게 보장. 수량자별 greedy/reluctant는 DFS 탐색 순서 반전만으로 구현 - 윈도우 함수는 정렬된 행을 순차적으로 받는다. Forward-only는 이 파이프라인에 그대로 맞지만, 백트래킹은 이전 행의 재방문(re-fetch)이 필요하다 - DEFINE 조건은 SQL 식(PREV, RUNNING 집계 등)이므로 재평가 비용이 높다. Forward-only는 행당 1회 평가로 충분 XII-3. 컨텍스트 단위 관리 선택: 시작 행별 독립 컨텍스트 이유: - SKIP TO NEXT ROW에서 겹치는 매칭 지원 - 각 행의 프레임을 독립적으로 결정 - 흡수 최적화로 중복 컨텍스트 O(n) 제거 가능 XII-4. 메모리 풀 관리 선택: 자체 free-list 이유: - NFA 상태는 행마다 대량 생성/소멸 - palloc/pfree 오버헤드 회피 - 상태 크기가 가변적 (counts 배열)이지만, 하나의 쿼리 내에서 maxDepth가 고정이므로 모든 상태가 같은 크기 XII-5. 실행 최적화 종합 다음 최적화들이 NFA 시뮬레이션을 실용적으로 만든다. ── 컴파일 시 ── (1) AST 최적화 (IV-3) 패턴을 NFA로 변환하기 전에 AST를 단순화한다. 연속 변수 병합(A A → A{2}), SEQ 평탄화, 수량자 곱셈 등을 통해 NFA 요소 수를 줄인다. 의미: 요소 수 감소는 상태 공간 축소로 직결되며, 이후 모든 런타임 단계(매칭, 흡수, advance)의 비용이 감소한다. ── 런타임: advance 단계 ── (2) 그룹 스킵 (IX-4(b)) min=0인 그룹의 BEGIN에서 jump로 그룹 전체를 건너뛴다. 그룹 본문을 탐색하지 않고 바로 그룹 밖의 첫 요소로 이동. Greedy는 진입 후 스킵, Reluctant는 스킵 후 진입 순서. 의미: 선택적 그룹(min=0)에서 본문 탐색 없이 즉시 스킵 경로를 생성하여 불필요한 DFS 확장을 회피한다. (3) 상태 중복 제거 (IX-5) advance에서 DFS가 같은 (elemIdx, counts) 조합의 상태를 여러 경로로 생성할 수 있다. 또한 VAR 반복과 달리 그룹 반복에서는 VAR 상태로는 흡수 비교가 불가능하므로 Phase 1 매치 후 END까지 inline advance하는데, 이 과정에서도 같은 END에 도달하는 중복 상태가 발생할 수 있다. nfa_add_state_unique()가 두 경우 모두에서 동일 상태의 중복 추가를 차단한다. 의미: ALT 분기나 수량자 확장에서 상태 수의 지수적 증가를 방지한다. DFS 순서에 의해 우선 분기의 상태가 먼저 등록되므로, 후순위 분기의 동일 상태는 자동 폐기되어 우선성(preferment)도 함께 보장된다. (4) 사이클 감지 및 fast-forward (IX-6, IX-4(c)) nullable 그룹 본문(예: A?)이 빈 매칭을 반복하면 END → BEGIN 루프백이 무한히 계속될 수 있다. 두 메커니즘으로 해결한다: - visited 비트맵(nfaVisitedElems)으로 같은 요소의 재방문을 차단하여 무한 루프를 방지 (안전성) - RPR_ELEM_EMPTY_LOOP 플래그가 설정된 END에서 count < min일 때, 나머지 필요 반복을 빈 매칭으로 간주하고 그룹 밖으로 탈출하는 fast-forward 경로 추가 (정확성) 의미: 사이클 감지가 종료를 보장하고, fast-forward가 min 조건 충족을 보장한다. 이것이 없으면 nullable 그룹을 포함하는 패턴이 무한 루프에 빠지거나 매칭에 실패한다. (5) 매칭 프루닝 (IX-4(e)) advance 중 상태가 FIN에 도달하면 해당 컨텍스트의 나머지 미처리 상태를 모두 제거한다. DFS 순서에 의해 FIN에 먼저 도달한 경로가 가장 높은 우선성을 가지므로, 나머지는 열등한 경로이다. 의미: 최선의 매칭이 확정되면 열등한 경로의 탐색을 즉시 중단한다. 우선성 보장과 성능 최적화를 동시에 달성한다. ── 런타임: 컨텍스트 간 ── (6) Early Termination (SKIP PAST LAST ROW) SKIP PAST LAST ROW 모드에서 매칭이 확정되면, 매칭 범위 내에 시작 행이 있는 후속 컨텍스트들을 추가 처리 없이 즉시 프루닝한다. SKIP TO NEXT ROW 모드에서는 각 행이 독립적인 매칭을 필요로 하므로 겹치는 컨텍스트를 유지한다. 의미: 선행 매칭 범위와 시작 행이 겹치는 후속 컨텍스트를 프루닝하여 불필요한 처리를 회피한다. (7) 컨텍스트 흡수 (VIII장) 각 행마다 독립 컨텍스트를 생성하면 O(n²) 상태가 누적된다. 먼저 시작한 컨텍스트가 나중 컨텍스트의 상태를 포함하는 단조성을 이용하여, 중복 컨텍스트를 조기에 제거한다. 흡수 가능 여부는 요소(element) 단위로 판정된다. RPR_ELEM_ABSORBABLE 플래그가 설정된 요소에서만 비교가 수행된다 (IV-5 참조). 의미: 활성 컨텍스트 수를 상수 수준으로 유지하여 O(n²) → O(n) 시간 복잡도를 달성한다. 이것이 없으면 긴 파티션에서 성능이 급격히 저하된다. 부록 A. 주요 함수 색인 ================================================================================ 함수명 파일 역할 ────────────────────────────────────────────────────────────────────── transformRPR parse_rpr.c 파서 진입점 transformDefineClause parse_rpr.c DEFINE 변환 collectPatternVariables rpr.c 변수 수집 filterDefineClause rpr.c DEFINE 필터링 buildRPRPattern rpr.c NFA 컴파일 메인 optimizeRPRPattern rpr.c AST 최적화 fillRPRPattern rpr.c NFA 요소 생성 finalizeRPRPattern rpr.c 최종화 computeAbsorbability rpr.c 흡수 분석 update_reduced_frame nodeWindowAgg.c 실행 메인 루프 nfa_start_context nodeWindowAgg.c 컨텍스트 생성 nfa_process_row nodeWindowAgg.c 3단계 처리 nfa_evaluate_row nodeWindowAgg.c DEFINE 평가 nfa_match nodeWindowAgg.c Phase 1 nfa_absorb_contexts nodeWindowAgg.c Phase 2 nfa_advance nodeWindowAgg.c Phase 3 nfa_advance_state nodeWindowAgg.c 상태별 분기 nfa_route_to_elem nodeWindowAgg.c 요소 라우팅 nfa_advance_alt nodeWindowAgg.c ALT 처리 nfa_advance_begin nodeWindowAgg.c BEGIN 처리 nfa_advance_end nodeWindowAgg.c END 처리 nfa_advance_var nodeWindowAgg.c VAR 처리 nfa_add_state_unique nodeWindowAgg.c 중복 제거 nfa_states_covered nodeWindowAgg.c 흡수 커버 판정 부록 B. 자료구조 관계도 ================================================================================ 파서 계층 ──────── RPCommonSyntax ├─ rpSkipTo: RPSkipTo ├─ initial: bool └─ rpPattern: RPRPatternNode* (트리) ├─ nodeType: VAR | SEQ | ALT | GROUP ├─ min, max: 수량자 ├─ varName: 변수명 (VAR만) └─ children: List* (SEQ/ALT/GROUP만) 플래너 계층 ────────── WindowAgg (계획 노드) ├─ rpSkipTo: RPSkipTo ├─ defineClause: List └─ rpPattern: RPRPattern* ├─ numVars: int ├─ varNames: char** ├─ maxDepth: RPRDepth ├─ isAbsorbable: bool ├─ numElements: int └─ elements: RPRPatternElement[] (평탄 배열) ├─ varId (1B) ├─ depth (1B) ├─ flags (1B) ├─ reserved (1B) ├─ min, max (4B + 4B) └─ next, jump (2B + 2B) 실행기 계층 ────────── WindowAggState ├─ rpPattern: RPRPattern* (계획에서 복사) ├─ defineClauseList: List ├─ nfaVarMatched: bool[] (행별 캐시) ├─ nfaVisitedElems: bitmapword* (사이클 감지) ├─ nfaContext ←→ nfaContextTail (양방향 리스트) │ └─ RPRNFAContext │ ├─ states: RPRNFAState* (연결 리스트) │ │ ├─ elemIdx │ │ ├─ counts[] │ │ └─ isAbsorbable │ ├─ matchStartRow, matchEndRow │ ├─ matchedState (FIN 도달 시 복제) │ ├─ hasAbsorbableState │ └─ allStatesAbsorbable ├─ nfaContextFree (재활용 풀) └─ nfaStateFree (재활용 풀) 부록 C. NFA 요소 배열 예시 모음 ================================================================================ C-1. PATTERN (A B C) idx varId depth min max next jump ────────────────────────────────────────── 0 A 0 1 1 1 -1 1 B 0 1 1 2 -1 2 C 0 1 1 3 -1 3 FIN 0 1 1 -1 -1 C-2. PATTERN (A+ B*) idx varId depth min max next jump flags ───────────────────────────────────────────────── 0 A 0 1 INF 1 -1 ABSORBABLE | ABSORBABLE_BRANCH 1 B 0 0 INF 2 -1 2 FIN 0 1 1 -1 -1 A+만 흡수 포인트 (Case 1). A를 벗어나면 해당 상태의 흡수가 영구 비활성화된다. C-3. PATTERN (A | B | C) idx varId depth min max next jump ────────────────────────────────────────── 0 ALT 0 1 1 1 -1 교대 시작 1 A 1 1 1 4 2 분기1 → FIN, jump → 분기2 2 B 1 1 1 4 3 분기2 → FIN, jump → 분기3 3 C 1 1 1 4 -1 분기3 → FIN 4 FIN 0 1 1 -1 -1 C-4. PATTERN ((A B)+ C) idx varId depth min max next jump flags ─────────────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 4 ABSORBABLE_BRANCH 1 A 1 1 1 2 -1 ABSORBABLE_BRANCH 2 B 1 1 1 3 -1 ABSORBABLE_BRANCH 3 END 0 1 INF 4 1 ABSORBABLE | ABSORBABLE_BRANCH 4 C 0 1 1 5 -1 5 FIN 0 1 1 -1 -1 Case 2: {1,1} 본문 VAR의 GROUP+. A, B는 브랜치; END가 흡수 포인트. C-6 (Case 3)과 비교. C-5. PATTERN ((A | B)+? C) idx varId depth min max next jump flags ─────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 5 RELUCTANT, 그룹 시작 1 ALT 1 1 1 2 -1 교대 시작 2 A 2 1 1 4 3 분기1 3 B 2 1 1 4 -1 분기2 4 END 0 1 INF 5 1 RELUCTANT, 그룹 종료 5 C 0 1 1 6 -1 6 FIN 0 1 1 -1 -1 C-6. PATTERN ((A+ B)+ C) — 흡수 가능성 플래그 예시 idx varId depth min max next jump flags ────────────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 4 ABSORBABLE_BRANCH, 그룹 시작 1 A 1 1 INF 2 -1 ABSORBABLE | ABSORBABLE_BRANCH 2 B 1 1 1 3 -1 3 END 0 1 INF 4 1 그룹 종료 4 C 0 1 1 5 -1 5 FIN 0 1 1 -1 -1 BEGIN에서 본문으로 재귀 → A가 Case 1 (단순 VAR+) 적용. A에 ABSORBABLE | ABSORBABLE_BRANCH, BEGIN에 ABSORBABLE_BRANCH. B, END에는 플래그 없음 → 상태가 B로 진행하면 흡수 중단. (IV-5 Case 3 참조) C-7. PATTERN ((A+ B | C*)+ D) -- ALT 분기별 흡수 예시 idx varId depth min max next jump flags ────────────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 6 ABSORBABLE_BRANCH 1 ALT 1 1 1 2 -1 ABSORBABLE_BRANCH 2 A 2 1 INF 3 4 ABSORBABLE | ABSORBABLE_BRANCH 3 B 2 1 1 5 -1 4 C 2 0 INF 5 -1 ABSORBABLE | ABSORBABLE_BRANCH 5 END 0 1 INF 6 1 EMPTY_LOOP 6 D 0 1 1 7 -1 7 FIN 0 1 1 -1 -1 ALT 분기는 독립적으로 흡수 가능 여부를 판정한다. 분기 1: A+가 Case 1 → A에 ABSORBABLE. B에는 플래그 없음. 분기 2: C*가 Case 1 → C에 ABSORBABLE. A와 C 모두 각 분기 경로의 일부로 ABSORBABLE_BRANCH를 받는다. END에 EMPTY_LOOP: 분기 2 (C*)가 nullable이므로 그룹 본문이 nullable. BEGIN, ALT에는 ABSORBABLE_BRANCH (흡수 가능 요소로의 경로). ================================================================================ 문서 끝 ================================================================================