(KO) PostgreSQL 집계, 정렬, 윈도우 실행기 노드

학술적 배경
DBMS 공통 설계 패턴
PostgreSQL의 구현
소스 코드 가이드
소스 검증 (2026-06-05 기준)
PostgreSQL 너머 — 비교 설계와 연구 프론티어
출처

학술적 배경

postgres-executor.md에서 설명한 demand-driven 이터레이터 모델은 모든 연산자를 open / next / close 세 쌍으로 다루며, next 한 번에 튜플 하나를 반환한다. 그러나 모든 관계형 연산자가 이 계약을 대칭적으로 이행할 수 있는 것은 아니다. Database System Concepts(Silberschatz, 7판, 15장 “Query Processing”)는 이 문서 전체를 관통하는 경계선을 그어 놓는다. 그것이 파이프라인 가능(pipelineable) 연산자와 블로킹(blocking) 연산자의 구분이다.

파이프라인 가능 연산자는 입력의 제한된 앞부분만 소비하고도 출력 튜플을 내보낼 수 있다. 선택(selection), 투영(projection), 중첩 루프 조인이 그 예다. 블로킹 연산자는 (DSC §15.7.2.1에서 “모든 입력을 검사하기 전에는 어떤 출력도 만들어 낼 수 없는 연산”으로 설명한다) 첫 번째 출력을 내기 전에 입력 전체를 소비해야 한다. 교과서는 정렬과 집계를 대표적인 블로킹 연산자로 꼽는다. “정렬 연산은 입력 전체를 소비한 후에야 출력 전체를 만들어 낸다”고 하며, 집계 역시 그룹의 결과를 확정하기 전에 해당 그룹의 모든 행을 봐야 한다. 블로킹 연산자는 파이프라인을 둘로 끊어 놓는다. 그 아래에 있는 모든 연산이 완료되어야 위에 있는 연산이 시작되기 때문이다. 플랜 루트 근처에 Sort나 해시 Agg가 있을 때 쿼리의 첫 행이 늦게 나타나는 이유가 바로 여기 있다.

DSC가 제시하는 세 가지 이론 기둥이 이 문서에서 다루는 세 계열을 지탱한다.

1. 집계 — 그룹 축약(grouped reduction). DSC §15.5(“Other Operations → Aggregation”)는 그룹화를 다음과 같이 정의한다. 그룹화 열이 같은 행을 파티션으로 묶고, 각 집계 함수(sum, count, avg 등)의 축약을 그룹 안에서 수행한다. 교과서는 두 가지 물리적 구현을 제시하는데, 이는 그룹 조인의 두 변형과 정확히 대응한다.

정렬 집계(sorted aggregation). 그룹화 열로 입력을 정렬한 뒤, 단일 선형 패스로 그룹 경계(그룹화 열이 이전 행과 달라지는 지점)를 감지하고 경계를 넘을 때 각 그룹을 확정한다. 비용은 정렬이 지배하며, 한 번에 하나의 그룹 상태만 활성 상태이므로 메모리는 그룹 수에 관계없이 *O(1)*다.
해시 집계(hash aggregation). 그룹화 열을 키로 하는 해시 테이블을 구축한다. 입력 튜플마다 테이블을 탐색해 해당 그룹의 진행 중 상태를 현장에서 갱신한다. 전역 정렬이 불필요하고 출력은 입력 전체를 소비한 뒤에야 나온다. 메모리는 *O(고유 그룹 수)*다. 그룹이 메모리에 들어오지 않으면 단순한 해시 집계는 스레싱이나 실패로 이어진다는 점이 아킬레스건이다.

2. 정렬 — 외부 합병 정렬(external merge sort). DSC §15.4(“Sorting”)는 릴레이션이 메모리에 들어오지 않는 경우를 기본으로 다루며 외부 정렬-합병을 제시한다. 입력을 메모리 크기 청크로 읽고, 각 청크를 메모리에서 정렬해 *런(run)*을 만든 뒤 디스크에 쓰고, 하나 이상의 패스로 런을 합병한다. 합병 패스 수는 런 수의 로그에 비례하며, 각 런의 인메모리 정렬이 핵심 연산이다. 쿼리 엔진은 이 전체 로직을 재사용 가능한 정렬 유틸리티로 추출함으로써 Sort 플랜 노드, 정렬 집계 입력 준비, 인덱스 빌드가 하나의 최적화된 구현을 공유할 수 있게 한다.

3. 윈도우 함수 — 정렬된 파티션 위의 프레임. 윈도우 함수 (OVER (PARTITION BY … ORDER BY … ROWS/RANGE BETWEEN …))는 SQL:2003이 집계를 일반화한 것이다. 그룹을 한 행으로 축약하는 대신, 모든 입력 행마다 현재 행의 파티션 안에 있는 연속된(또는 배제 조항이 있을 경우 근사 연속된) 구간인 윈도우 프레임의 집계나 순위를 계산한다. DSC §5.5.1(“Windowing”)은 이 모델을 다음과 같이 설명한다. 행은 파티션으로 나뉘고 정렬된다. 각 행의 프레임은 슬라이딩 윈도우다. 결과는 입력의 카디널리티를 보존한다. 단순 구현은 모든 행에서 프레임 전체를 재계산하므로 *O(파티션 × 프레임)*이 된다. 프레임을 증분으로 슬라이딩하는 것이 이 영역의 핵심 엔지니어링 과제다.

공통 실마리가 있다. 세 계열 모두 블로킹이거나 부분적으로 블로킹이고, 메모리에 들어오지 않을 수 있는 데이터를 저장할 공간이 필요하며, 입력이 이미 정렬되어 있는지 여부에 민감하다. PostgreSQL의 구현은 응답 전에 얼마나 버퍼링해야 하는가 스펙트럼 위의 세 점으로 읽는 것이 가장 자연스럽다.

교과서의 또 다른 아이디어 하나가 세 계열을 묶는다. 메모리 계층 구조가 실제 비용 모델이다. DSC의 외부 정렬과 해싱 전체 논의는 릴레이션이 RAM에 들어오지 않는다는 전제 위에 있으며, 알고리즘의 목표는 디스크 패스를 최소화하는 것이다. 메모리에 맞는 블로킹 연산자는 저렴하고 눈에 띄지 않는다. 반면 오버플로가 발생하면 외부 알고리즘 비용을 치른다. 이 문서에 등장하는 PostgreSQL의 모든 튜닝 파라미터 — work_mem, hash_mem, 제한 정렬, 증분 정렬 그룹 크기, 스필 파티션 수 — 는 연산자가 그 메모리 절벽의 어느 쪽에 있는지를 관리하기 위한 것이다. 맞는 경우 / 맞지 않는 경우의 이분법을 머릿속에 유지하면, 등장하는 각 스필, 각 제한 모드, 각 접두사 그룹 경계가 저렴한 쪽에 머물려는 시도임을 곧 알아차리게 된다.

DBMS 공통 설계 패턴

교과서는 알고리즘을 제시한다. 이 절은 프로덕션 엔진이 그 위에 쌓는 엔지니어링 관습을 정리한다. 다음 절에서 살펴볼 PostgreSQL의 구체적인 심볼들이 이 패턴들을 인스턴스화한다.

전략 선택은 옵티마이저에게 위임한다

정렬 집계 대 해시 집계, 전체 정렬 대 증분 정렬, 윈도우 함수 스택 순서 — 이 모두는 플랜 타임 결정이다. 실행기 노드는 이 결정을 재도출하지 않는다. Plan 노드에서 전략 태그를 읽어 스위치한다. 비용 모델은 정렬 집계가 요구하는 정렬 비용과 해시 집계가 안고 있는 메모리 위험을 비교해 태그 하나를 내보낸다. 결정을 플래너에 두면 실행기는 기계적인 디스패치만 하면 되고, 같은 실행기 코드가 모든 전략을 서비스한다.

공유 재사용 가능 정렬 유틸리티 — 노드마다 정렬 코드를 두지 않는다

Sort 노드, 정렬 집계 입력 경로, 인덱스 빌더 각각에 외부 합병 정렬을 직접 구현하는 대신, 엔진은 이를 하나의 모듈(PostgreSQL: tuplesort.c)에 집중한다. 이 모듈이 작업 메모리 예산, 인메모리 퀵소트, 런 생성, 테이프 합병, LIMIT를 위한 선택적 제한(bounded) (상위-N 힙) 모드, 단일 열 정렬을 위한 datum 고속 경로를 소유한다. 모든 사용자는 튜플을 넘기고 나중에 정렬된 채로 돌려받는다. 이 문서는 이 유틸리티를 블랙박스로 취급하며(postgres-tuplesort.md가 소유), 노드가 어떻게 그것을 구동하는지에 집중한다.

해시 테이블 오버플로 시 실패 대신 스필

해시 집계의 치명적 약점 — 그룹 수에 비례하는 무제한 메모리 — 은 스필링으로 억제한다. 활성 해시 테이블이 메모리 예산을 초과하면 엔진은 새로운 그룹 생성을 중단한다. 새 그룹을 시작해야 할 튜플은 그룹화 키의 해시로 파티션을 나눠 디스크에 기록하고, 나중에 배치 단위로 재집계한다. 하나의 배치도 오버플로할 수 있으므로 스필은 재귀적이다. 각 배치는 이미 소비한 해시 비트 수를 추적하며, 너무 큰 배치는 다음 비트들로 재파티션한다. 이로써 메모리 부족 실패가 디스크 사용으로 우아하게 전환되되, 추가 I/O라는 비용을 치른다.

사전 정렬 활용 — 증분 정렬과 제한 정렬

입력이 요청된 키의 접두사 순서로 이미 정렬되어 있다면(자식 인덱스나 하위 정렬 덕분에), 전체 정렬은 낭비다. 증분 정렬 관습은 접두사 그룹 하나씩 정렬한다. 접두사 키가 바뀔 때까지 행을 읽고, 그 그룹만 나머지 키로 정렬한 뒤 내보내고 반복한다. 메모리는 그룹 하나로 제한되며, 결정적으로 입력 전체를 읽기 전에 첫 행을 반환할 수 있다는 점이 LIMIT 아래에서의 핵심 가치다. 별도로, 제한(bounded) (상위-N) 정렬은 LIMIT N만 필요할 때 지금까지 본 가장 작은 N개 튜플만 유지하고 나머지를 버린다.

파티션 버퍼링과 프레임 증분 슬라이딩

윈도우 함수는 같은 파티션 내 다른 행들에 임의 접근해야 하므로, 엔진은 각 파티션을 스필 가능한 튜플 스토어에 버퍼링하고 여러 읽기 커서를 유지한다(윈도우 함수 하나당 하나의 커서와 프레임 경계 탐색 커서). 성능의 핵심은 **역전이 함수(inverse transition function)**다. 헤드만 앞으로 움직이는 이동 프레임에서, 프레임 전체를 매 행마다 재계산하는 대신, 엔진은 새로 진입한 행을 순방향 전이 함수로 추가하고 새로 이탈한 행을 역전이 함수로 제거해, 상각 기준 행당 *O(1)*로 진행 상태를 슬라이딩한다.

이중 메모리 계층 — 그룹별 상태 대 튜플별 스크래치

집계는 많은 입력 행에 걸쳐 진행 상태를 누적하므로, 전이 값은 집계 인수를 평가하는 튜플별 스크래치보다 오래 살아야 한다. 따라서 엔진은 최소 두 개의 메모리 영역을 유지한다. 그룹 경계에서만 리셋하는 오래 사는 영역(전이 값용)과, 매 행마다 리셋하는 입력 튜플별 영역이다. 그룹 집합은 이를 곱한다. 동시에 추적하는 그룹 집합마다 별도의 전이 영역이 있어, 세밀한 그룹 경계를 넘을 때 그 집합의 상태만 리셋하고 더 거칠게 집계하는 롤업 수준은 계속 누적할 수 있다. 리셋은 컨텍스트 전체를 지우는 bulk clear이지, 전이 값마다 free()를 호출하는 낱개 해제가 아니다. 그래서 수십억 행을 집계하는 경우에도 일시적 메모리가 제한된 수준에 머무른다.

튜플 포맷이 바뀌면 표현식을 재컴파일한다

미묘하지만 중요한 관습이 있다. 합쳐진 전이 표현식은 특정 입력 튜플 *형식(shape)*에 맞게 컴파일된다. 스필된 튜플은 외부 플랜의 원래 포맷이 아닌 최소 튜플(minimal tuple)로 디스크에서 돌아오므로, JIT 컴파일이나 사전 빌드된 전이 표현식을 쓰는 엔진은 스필 데이터 읽기로 전환할 때 재컴파일해야 한다. 이 단계를 건너뛰면 스필된 튜플을 잘못 역직렬화하거나 쓰레기를 조용히 읽어 들이게 된다. PostgreSQL은 모든 포맷 경계에서 이 재컴파일을 명시적으로 수행한다. 공통 인메모리 경로에서 복사 비용을 치르도록 포맷을 통일하는 대신, 각 경계마다 명시적으로 처리하는 설계다.

이론 ↔ PostgreSQL 대응

이론 / 관습	PostgreSQL 이름
집계 전략 태그	`AggStrategy` 열거형: `AGG_PLAIN` / `AGG_SORTED` / `AGG_HASHED` / `AGG_MIXED`
정렬 집계 그룹 경계	`agg_retrieve_direct` 내 `ExecQualAndReset(phase->eqfunctions[…])`
해시 집계 테이블	`AggStatePerHash` 내 그룹 집합별 `TupleHashTable`
해시 스필 트리거 / 모드	`hash_agg_check_limits` → `hash_agg_enter_spill_mode`
파티션 스필 파일	`LogicalTapeSet` 위의 `HashAggSpill`; 재귀 `HashAggBatch`
그룹 집합 단일 패스 플랜	단계 체인(`AggStatePerPhase`), `initialize_phase`
공유 정렬 유틸리티	`tuplesort.c` (`tuplesort_begin_heap` / `_begin_datum` / `_gettupleslot`)
데이텀 (단일 열) 정렬 고속 경로	`SortState.datumSort` → `tuplesort_begin_datum` / `tuplesort_getdatum`
제한 (상위-N) 정렬	`SortState.bounded` → `tuplesort_set_bound`
증분 정렬 상태 기계	`INCSORT_LOADFULLSORT` / `READFULLSORT` / `LOADPREFIXSORT` / `READPREFIXSORT`
접두사 그룹 경계 검사	`PresortedKeyData` 위의 `isCurrentGroup`
윈도우 파티션 버퍼	`WindowAggState.buffer` (a `Tuplestorestate`)
윈도우 함수별 커서	튜플스토어 내 `WindowObject.readptr` / `markptr`
이동 프레임 증분 집계	`eval_windowaggregates` 내 순방향 `transfn` + `invtransfn`
그룹별 전이 영역 대 튜플별 영역	`aggcontexts[]` / `hashcontext` 대 `tmpcontext`

플래너 측 — 특정 전략이 선택된 이유, GROUPING SETS가 단계 체인으로 분해되는 방식, IncrementalSort 경로가 생성되는 위치 — 는 postgres-planner-overview.md와 postgres-path-generation.md가 다룬다. tuplesort.c 내부(런 생성, 테이프 합병, 상위-N 힙)는 postgres-tuplesort.md가 담당한다. 인수 평가와 전이 함수 호출을 융합하는 ExecBuildAggTrans 표현식은 postgres-expression-eval.md가 다룬다. 이 문서는 노드에 집중한다. 각 노드가 실행기의 풀(pull) 프로토콜을 어떻게 구동하는지, 무엇을 버퍼링하는지, 어떻게 스필하는지다.

PostgreSQL의 구현

PostgreSQL은 세 계열을 네 개의 실행기 노드로 구현한다. Agg, Sort, IncrementalSort, WindowAgg 각각은 postgres-executor.md의 모든 다른 노드와 마찬가지로 ExecProcNode 함수 포인터를 가진 PlanState 서브타입이다. 이들을 구분하는 것은 외부 인터페이스가 아니라 내부 상태와 버퍼링 방식이다.

Agg — 하나의 ExecAgg 뒤에 있는 네 가지 전략

플래너는 Agg 플랜 노드에 AggStrategy 태그를 붙인다.

// AggStrategy — src/include/nodes/nodes.h
typedef enum AggStrategy
{
    AGG_PLAIN,          /* simple agg across all input rows */
    AGG_SORTED,         /* grouped agg, input must be sorted */
    AGG_HASHED,         /* grouped agg, use internal hashtable */
    AGG_MIXED,          /* grouped agg, hash and sort both used */
} AggStrategy;

ExecAgg는 얇은 디스패처다. AGG_HASHED/AGG_MIXED는 해시 테이블을 구축하고 드레인하며, AGG_PLAIN/AGG_SORTED는 (플래너가 정렬해 둔) 입력에서 직접 그룹을 스트리밍한다.

// ExecAgg — src/backend/executor/nodeAgg.c
static TupleTableSlot *
ExecAgg(PlanState *pstate)
{
    AggState   *node = castNode(AggState, pstate);
    TupleTableSlot *result = NULL;

    if (!node->agg_done)
    {
        switch (node->phase->aggstrategy)
        {
            case AGG_HASHED:
                if (!node->table_filled)
                    agg_fill_hash_table(node);
                /* FALLTHROUGH */
            case AGG_MIXED:
                result = agg_retrieve_hash_table(node);
                break;
            case AGG_PLAIN:
            case AGG_SORTED:
                result = agg_retrieve_direct(node);
                break;
        }
        if (!TupIsNull(result))
            return result;
    }
    return NULL;
}

정렬/플레인 경로. agg_retrieve_direct는 정렬(또는 플레인, 단일 그룹) 입력에서 O(1) 상태로 한 번에 하나의 그룹을 처리할 수 있다는 불변 조건을 활용한다. 그룹의 첫 번째 튜플을 가져오고, 이전 행과 그룹화 열 동등성 표현식을 실행해 그룹 경계를 감지할 때까지 advance_aggregates를 매 후속 튜플에 실행하고, 그룹을 확정하고 투영한다. 그룹별 전이 상태는 aggcontexts[]에 있으며, 경계마다 rescan(등록된 종료 콜백 실행)된다. 입력 튜플별 스크래치는 tmpcontext에 있으며 매 행마다 리셋된다.

// agg_retrieve_direct — src/backend/executor/nodeAgg.c (condensed)
for (;;)
{
    /* ... advance over the current group, fetch next tuple ... */
    advance_aggregates(aggstate);
    ResetExprContext(tmpcontext);          /* per-input-tuple scratch */
    outerslot = fetch_input_tuple(aggstate);
    if (TupIsNull(outerslot))
        break;                              /* group runs to end of input */
}

그룹 경계 자체는 다음 그룹 집합에 대한 그룹화 열 동등성 표현식을 이전 행과 비교해 감지한다. ExecQualAndReset은 비교를 평가하는 동시에 튜플별 컨텍스트를 리셋한다. 그룹 집합의 경우, nextSetSize가 어느 집합의 동등성 함수를 사용할지 선택하므로, 단일 정렬 패스가 여러 롤업 수준을 동시에 처리할 수 있다.

// agg_retrieve_direct — src/backend/executor/nodeAgg.c (grouping-set boundary)
tmpcontext->ecxt_innertuple = econtext->ecxt_outertuple;
if (aggstate->input_done ||
    (node->aggstrategy != AGG_PLAIN &&
     aggstate->projected_set != -1 &&
     aggstate->projected_set < (numGroupingSets - 1) &&
     nextSetSize > 0 &&
     !ExecQualAndReset(aggstate->phase->eqfunctions[nextSetSize - 1],
                       tmpcontext)))
{
    aggstate->projected_set += 1;          /* advance to next grouping set */
}
else
{
    aggstate->projected_set = 0;           /* start the first/only set fresh */
    /* ... fetch grp_firstTuple, initialize_aggregates, then advance loop ... */
}

해시 경로. agg_fill_hash_table은 외부 플랜 전체를 그룹 집합별 해시 테이블로 드레인한다(블로킹 단계다). 그런 다음 agg_retrieve_hash_table이 테이블을 순회하며 그룹당 한 행씩 내보낸다. 입력 튜플마다 lookup_hash_entries가 모든 해시 테이블을 탐색한다. 히트하면 그 그룹의 상태를 현장에서 진행하고, 미스하면 새 그룹을 생성한다(스필 모드가 활성 상태가 아닌 경우).

// lookup_hash_entries — src/backend/executor/nodeAgg.c (condensed)
for (setno = 0; setno < aggstate->num_hashes; setno++)
{
    /* if hash table already spilled, don't create new entries */
    p_isnew = aggstate->hash_spill_mode ? NULL : &isnew;
    select_current_set(aggstate, setno, true);
    prepare_hash_slot(perhash, outerslot, hashslot);
    entry = LookupTupleHashEntry(hashtable, hashslot, p_isnew, &hash);
    if (entry != NULL)
    {
        if (isnew)
            initialize_hash_entry(aggstate, hashtable, entry);
        pergroup[setno] = TupleHashEntryGetAdditional(hashtable, entry);
    }
    else
    {
        /* no room for a new group: spill this tuple to disk */
        hashagg_spill_tuple(aggstate, &aggstate->hash_spills[setno], slot, hash);
        pergroup[setno] = NULL;
    }
}

스필링. 그룹을 삽입한 후 hash_agg_check_limits가 메타데이터, 항목, 전이 값 메모리를 합산한다. hash_mem_limit을 초과하거나 그룹 수가 hash_ngroups_limit을 넘으면 노드는 스필 모드로 진입한다. 스필된 튜플은 해시 비트로 파티션을 나눠 LogicalTape들에 기록된다. 인메모리 그룹이 모두 드레인된 후 agg_refill_hash_table이 스필된 HashAggBatch 하나를 꺼내고 테이블을 리셋하고 재집계한다. 배치 자체가 너무 크면 더 많은 해시 비트로 재파티션한다(재귀).

flowchart TB
  START["ExecAgg first call<br/>AGG_HASHED"]
  FILL["agg_fill_hash_table:<br/>drain outer plan"]
  LOOK["lookup_hash_entries<br/>probe each hashtable"]
  HIT{"group<br/>found?"}
  ADV["advance_aggregates<br/>(update state in place)"]
  CHK["hash_agg_check_limits"]
  OVER{"over<br/>hash_mem?"}
  SPILLMODE["hash_agg_enter_spill_mode<br/>(stop new groups)"]
  SPILL["hashagg_spill_tuple<br/>partition to LogicalTape"]
  DRAIN["agg_retrieve_hash_table_in_memory"]
  REFILL{"spilled<br/>batches left?"}
  POP["agg_refill_hash_table:<br/>pop HashAggBatch, reset,<br/>re-aggregate (recursive)"]
  DONE["agg_done = true"]

  START --> FILL --> LOOK --> HIT
  HIT -- yes --> ADV --> CHK --> OVER
  HIT -- "no, spill mode" --> SPILL
  OVER -- yes --> SPILLMODE
  OVER -- no --> LOOK
  SPILLMODE --> LOOK
  SPILL --> LOOK
  FILL --> DRAIN --> REFILL
  REFILL -- yes --> POP --> DRAIN
  REFILL -- no --> DONE

그룹 집합. ROLLUP/CUBE/GROUPING SETS 쿼리는 하나의 실제 Agg 노드에 추가 Agg 노드들이 chain으로 연결된 구조다. 실행기는 이를 **단계(phases)**로 합친다. 단계 0은 모든 해시 그룹 집합을 담고, 단계 1..n은 각각 자신만의 정렬 순서를 가진 정렬된 롤업 하나씩을 담는다. 단일 정렬 패스 안에서 agg_retrieve_direct는 그룹 집합마다 하나의 전이 상태(aggcontexts[0..k])를 추적하고 더 세밀한 집합만 경계에서 리셋한다. AGG_MIXED는 첫 번째 정렬 단계에서 해시 테이블을 채운 뒤 단계 0으로 전환해 읽어 낸다. 상태 전환은 initialize_phase가 담당한다.

Sort — tuplesort 위의 순수 블로킹 연산자

Sort는 교과서적 블로커다. 첫 번째 ExecSort 호출은 자식 노드 전체를 tuplesort.c로 드레인하고 tuplesort_performsort를 호출하고 sort_Done을 세운다. 이후의 모든 호출은 다음 정렬된 튜플을 꺼내오기만 한다. 노드는 출력 열이 하나인 경우 datum 정렬을 선택하고(값 전달 타입에 특히 저렴하다), 그 외에는 heap/tuple 정렬을 선택하며, 플래너의 bounded/randomAccess 힌트를 유틸리티에 전달한다.

// ExecSort — src/backend/executor/nodeSort.c (condensed)
if (!node->sort_Done)
{
    if (node->datumSort)
        tuplesortstate = tuplesort_begin_datum(/* type, op, coll, … */);
    else
        tuplesortstate = tuplesort_begin_heap(tupDesc, plannode->numCols,
                                              plannode->sortColIdx, /* … */);
    if (node->bounded)
        tuplesort_set_bound(tuplesortstate, node->bound);

    for (;;)                                 /* blocking: read ALL input */
    {
        slot = ExecProcNode(outerNode);
        if (TupIsNull(slot))
            break;
        tuplesort_puttupleslot(tuplesortstate, slot);
    }
    tuplesort_performsort(tuplesortstate);
    node->sort_Done = true;
}
/* subsequent calls: stream sorted tuples out */
(void) tuplesort_gettupleslot(tuplesortstate, ScanDirectionIsForward(dir),
                              false, slot, NULL);

이 노드는 의도적으로 ExprContext를 초기화하지 않는다. Sort는 qual이나 투영을 평가하지 않으며, 자식의 슬롯 순서만 바꾼다.

IncrementalSort — 사전 정렬된 접두사 위의 네 가지 상태 기계

입력이 정렬 키의 접두사 순서로 이미 정렬되어 있다면, IncrementalSort는 단일 거대 정렬 대신 접두사 그룹 하나씩 정렬해 처리한다. 네 가지 상태 기계 (INCSORT_LOADFULLSORT, INCSORT_READFULLSORT, INCSORT_LOADPREFIXSORT, INCSORT_READPREFIXSORT)를 하이브리드 휴리스틱으로 실행한다. 먼저 최소 그룹 크기 DEFAULT_MIN_GROUP_SIZE(32) 튜플을 모든 키로 정렬하고(작은 그룹에 저렴하다), 그룹이 크다고 판명될 때만 미정렬 접미사 키만 정렬하는 모드로 전환한다. 접두사 그룹 소속 여부는 isCurrentGroup으로 검사하며, 마지막 키부터 역순으로 사전 정렬된 열을 비교한다(꼬리 키가 먼저 바뀔 가능성이 높다).

// isCurrentGroup — src/backend/executor/nodeIncrementalSort.c (condensed)
for (int i = nPresortedCols - 1; i >= 0; i--)   /* last key first */
{
    datumA = slot_getattr(pivot, attno, &isnullA);
    datumB = slot_getattr(tuple, attno, &isnullB);
    /* NULL-vs-NULL handled specially, else call cached equality fn */
    key->fcinfo->args[0].value = datumA;
    key->fcinfo->args[1].value = datumB;
    result = FunctionCallInvoke(key->fcinfo);
    if (!DatumGetBool(result))
        return false;                            /* prefix changed: new group */
}
return true;

성과는 두 가지다. 메모리가 접두사 그룹 하나로 제한되어 스필이 줄고, 입력 전체를 읽기 전에 첫 행을 반환할 수 있다. 플래너가 IncrementalSort를 가장 자주 선택하는 상황인 LIMIT 아래에서 큰 이점을 제공한다.

flowchart TB
  LF["INCSORT_LOADFULLSORT:<br/>accumulate up to 32 tuples,<br/>sort on ALL keys"]
  BIG{"group still<br/>growing past<br/>min size?"}
  SW["switchToPresortedPrefixMode:<br/>re-bucket accumulated tuples"]
  LP["INCSORT_LOADPREFIXSORT:<br/>load one prefix group,<br/>sort on SUFFIX keys only"]
  RF["INCSORT_READFULLSORT:<br/>emit sorted full batch"]
  RP["INCSORT_READPREFIXSORT:<br/>emit sorted prefix group"]
  MORE{"more input?"}
  END["return empty slot"]

  LF --> BIG
  BIG -- "no (small/end)" --> RF
  BIG -- "yes" --> SW --> LP --> RP
  RF --> MORE
  RP --> MORE
  MORE -- yes --> LF
  MORE -- no --> END

WindowAgg — 슬라이딩 프레임과 버퍼링된 파티션

WindowAgg는 단일 윈도우 스펙의 윈도우 함수를 평가한다. 여러 스펙이 있을 때는 플래너가 중간에 Sort 노드를 끼워 여러 WindowAgg를 스택처럼 쌓는다. 입력은 PARTITION BY 다음에 ORDER BY로 정렬되어 도착해야 한다. 노드는 각 파티션을 Tuplestorestate에 버퍼링하고(begin_partition / spool_tuples), 윈도우 함수들은 WindowObject API로 파티션의 임의 행에 접근한다. API는 함수별 읽기/마크 커서를 스토어로 유지한다.

성능의 핵심은 eval_windowaggregates다. UNBOUNDED PRECEDING 헤드에 배제 조항이 없는 프레임은 행이 프레임에 진입하기만 하므로 순방향 전이 함수를 증분으로 실행한다. 헤드가 앞으로 움직이는 프레임은 새로 시작 지점부터 재계산하는 대신 집계의 역전이 함수로 이탈한 행을 제거한다. 역 함수가 없거나 거부하면 새 프레임 전체를 다시 집계한다. 동등 피어 그룹 공유는 동일한 프레임을 가진 모든 행이 한 번 계산된 값을 재사용하게 한다.

// ExecWindowAgg — src/backend/executor/nodeWindowAgg.c (condensed)
if (winstate->status == WINDOWAGG_DONE)
    return NULL;
for (;;)
{
    if (winstate->next_partition)
        begin_partition(winstate);          /* buffer a fresh partition */
    else
        winstate->currentpos++;             /* advance current row; frame moves */

    spool_tuples(winstate, winstate->currentpos);
    if (winstate->partition_spooled &&
        winstate->currentpos >= winstate->spooled_rows)
    {
        release_partition(winstate);
        if (winstate->more_partitions)
            begin_partition(winstate);
        else { winstate->status = WINDOWAGG_DONE; return NULL; }
    }
    /* eval frame-head/tail, window funcs, project; loop if qual rejects */
}

eval_windowaggregates 내부의 결정 분기는 재시작 대 슬라이드 검사다. 각 노드는 각 집계의 실행 중인 전이 값을 처음부터 재시작해야 할 때만 그렇게 한다. 재시작하는 조건은 다음과 같다. 가장 첫 행, 역함수 없이 앞으로 움직이는 프레임 헤드, 임의의 EXCLUDE 절, 또는 이전 프레임과 전혀 겹치지 않는 새 프레임. 그 외 모든 경우에는 슬라이드한다. 상단에서 이탈한 행을 역전이 함수로 제거하고 하단에서 진입한 행을 순방향 전이 함수로 추가한다.

// eval_windowaggregates — src/backend/executor/nodeWindowAgg.c (condensed)
numaggs_restart = 0;
for (i = 0; i < numaggs; i++)
{
    peraggstate = &winstate->peragg[i];
    if (winstate->currentpos == 0 ||                           /* first row */
        (winstate->aggregatedbase != winstate->frameheadpos && /* head moved */
         !OidIsValid(peraggstate->invtransfn_oid)) ||          /* no inverse fn */
        (winstate->frameOptions & FRAMEOPTION_EXCLUSION) ||    /* EXCLUDE clause */
        winstate->aggregatedupto <= winstate->frameheadpos)    /* no overlap */
    {
        peraggstate->restart = true;
        numaggs_restart++;
    }
    else
        peraggstate->restart = false;
}

/* slide: remove rows that fell off the frame head via inverse transition */
while (numaggs_restart < numaggs &&
       winstate->aggregatedbase < winstate->frameheadpos)
{
    window_gettupleslot(agg_winobj, winstate->aggregatedbase, temp_slot);
    /* ... advance_windowaggregate_base() per agg, or mark restart on failure ... */
}

이동 평균 스타일 쿼리에서 이것이 O(파티션) 작업과 O(파티션 × 프레임) 작업의 차이를 만든다. sum/count/avg는 역전이 함수가 있어 슬라이드한다. 반면 줄어드는 프레임 위의 max/min은 없어서 재시작한다.

소스 코드 가이드

파일은 src/backend/executor/ 아래에 노드별로 네 개다. 아래 심볼들은 안정된 앵커다. 행 번호는 이 절 마지막 위치 힌트 표에서만 제공한다.

Agg — `nodeAgg.c`

디스패치 및 검색 척추:

ExecAgg — ExecProcNode 진입점. node->phase->aggstrategy로 스위치해 직접 검색기 또는 해시 검색기로 라우팅한다.
agg_retrieve_direct — AGG_PLAIN/AGG_SORTED 엔진. 정렬된 입력에서 그룹을 순회하며, 단계의 그룹화 동등성 표현식(phase->eqfunctions[…]을 ExecQualAndReset으로 실행)으로 경계를 감지하고 호출당 한 그룹을 확정·투영한다. 그룹 집합 단계 기계를 구동한다. 단계 입력이 소진되면 **initialize_phase**를 호출해 다음 정렬 순서로 넘어가고, AGG_MIXED 노드는 단계 0으로 전환해 해시 테이블을 드레인한다.
agg_fill_hash_table — AGG_HASHED의 블로킹 선행 패스. 외부 플랜을 드레인하며 튜플마다 lookup_hash_entries + advance_aggregates를 호출하고 마지막에 hashagg_finish_initial_spills를 호출한다.
lookup_hash_entries — 각 그룹 집합의 TupleHashTable을 탐색한다. 히트 시 현장에서 진행, 미스 시 그룹 생성, 또는 (스필 모드에서) hashagg_spill_tuple.
agg_retrieve_hash_table / agg_retrieve_hash_table_in_memory — 채워진 테이블을 순회하며 호출당 한 그룹을 확정한다. 인메모리 그룹이 소진되면 agg_refill_hash_table을 호출한다.
agg_refill_hash_table — 스필된 HashAggBatch 하나를 꺼내고, 테이블을 리셋하고, MinimalTuple 입력을 위해 전이 표현식을 재컴파일하고, 배치를 재집계한다(오버플로 시 재귀 스필).

메모리/한계 기계:

build_hash_tables / build_hash_table — hash_choose_num_buckets로 결정한 버킷 수로 그룹 집합마다 TupleHashTable 하나씩 생성한다.
hash_agg_set_limits — get_hash_memory_limit()으로 mem_limit과 ngroups_limit을 도출하며, 스필이 예상될 경우 테이프 버퍼 메모리를 예약한다.
hash_agg_check_limits — 새 그룹을 삽입한 후, 메타 + 항목 + 전이 값 메모리를 합산해 메모리 또는 그룹 한계를 초과하면 스필링을 발동한다.
hash_agg_enter_spill_mode — hash_spill_mode를 뒤집고, 표현식을 재컴파일하고, LogicalTapeSet과 집합별 HashAggSpill 파티션을 지연 생성한다.
ExecInitAgg — AggState, 단계 배열, 집계별/전이별 테이블을 구축한다. 해시/혼합의 경우 해시 테이블과 컨텍스트도 구축하며, 전략 태그에서 use_hashing을 읽는다.
ExecReScanAgg — 재실행을 위해 리셋한다. 파라미터가 없고 스필이 없었던 해시 집계는 기존 테이블을 단순히 재순회할 수 있다.

핵심 구조체/열거형: AggStrategy(nodes.h), AggStatePerHashData, AggStatePerGroupData, HashAggSpill, HashAggBatch, AggStatePerPhase.

Sort — `nodeSort.c`

ExecSort — 첫 번째 호출에서 블로킹. 단일 열이면 tuplesort_begin_datum을, 그 외에는 tuplesort_begin_heap으로 tuplesort를 구성하고, 자식 튜플 전체를 공급하고(tuplesort_puttupleslot / tuplesort_putdatum), tuplesort_performsort를 실행하고 sort_Done을 세운다. 이후 호출은 tuplesort_gettupleslot / tuplesort_getdatum으로 스트리밍 출력한다.
ExecInitSort — EXEC_FLAG_REWIND | BACKWARD | MARK에서 randomAccess를 설정하고, 출력 열 수에서 datumSort를 결정하며, 자식을 리와인드/역방향/마크 요건으로부터 보호한다. 정렬 노드는 ExprContext를 초기화하지 않는다(qual도 투영도 없다).
ExecReScanSort — 랜덤 접근이 가능하고 파라미터 변경이 없으면 정렬된 출력을 재사용한다. 그 외에는 tuplesort를 해체하고 새로 정렬한다.

IncrementalSort — `nodeIncrementalSort.c`

ExecIncrementalSort — 네 가지 상태 기계. 최소 크기 그룹을 모든 키로 전체 정렬(INCSORT_LOADFULLSORT)해 내보내고(INCSORT_READFULLSORT), 큰 그룹에서는 접미사만 정렬하는 모드로 전환(INCSORT_LOADPREFIXSORT / READPREFIXSORT).
preparePresortedCols — 각 사전 정렬 키의 동등성 FmgrInfo/FunctionCallInfo를 PresortedKeyData에 캐싱한다.
isCurrentGroup — 그룹 피벗과 접두사 그룹 소속 여부를 검사하며, 마지막 사전 정렬 키부터 역순으로 비교한다.
switchToPresortedPrefixMode — 큰 그룹이 감지되면 이미 누적된 튜플들을 접두사 정렬 상태로 재분류하고, n_fullsort_remaining으로 잔여 접두사 그룹을 넘긴다.
ExecInitIncrementalSort — 상태를 구축한다. DEFAULT_MIN_GROUP_SIZE(32)가 하이브리드 임계값이다.

WindowAgg — `nodeWindowAgg.c`

ExecWindowAgg — 파티션 루프. 행마다 입력을 스풀하고, 현재 위치를 앞으로 옮기고, 프레임 유효성을 갱신하고, 윈도우 함수를 평가하고 투영한다. status는 WINDOWAGG_RUN / WINDOWAGG_PASSTHROUGH / WINDOWAGG_PASSTHROUGH_STRICT / WINDOWAGG_DONE 중 하나다.
begin_partition — 프레임/그룹 카운터를 리셋하고, 튜플스토어를 할당하고 (prepare_tuplestore), 함수별 마크/탐색 커서를 리셋하고 첫 번째 행을 저장한다.
spool_tuples — 대상 위치까지(또는 파티션 전체까지) 외부 행을 튜플스토어로 읽어 들이며 파티션 경계를 감지한다.
eval_windowaggregates — 이동 집계 엔진. 고정 프레임 헤드에는 증분 순방향 전이, 움직이는 헤드에는 역전이(advance_windowaggregate_base), 역함수가 없으면 전체 재시작, 그리고 피어 그룹 결과 캐싱.
advance_windowaggregate — 한 집계를 한 행 단위로 순방향 전이(FILTER, 엄격성, 확장 객체 처리).
update_frameheadpos / update_frametailpos / row_is_in_frame — 버퍼링된 파티션에서 ROWS/RANGE/GROUPS 프레임 경계와 배제를 해석한다.
ExecInitWindowAgg — WindowAggState, 함수별 및 집계별 테이블, WindowObject들, 프레임 오프셋 표현식을 구축한다.

프레임 의미론 플래그(FRAMEOPTION_RANGE / _ROWS / _GROUPS, FRAMEOPTION_EXCLUDE_*)는 parsenodes.h에 있다.

위치 힌트 (2026-06-05 기준, REL_18 273fe94)

심볼	파일	행
`AggStrategy` (enum)	`src/include/nodes/nodes.h`	358
`initialize_phase`	`src/backend/executor/nodeAgg.c`	479
`build_hash_tables`	`src/backend/executor/nodeAgg.c`	1466
`hash_agg_set_limits`	`src/backend/executor/nodeAgg.c`	1809
`hash_agg_check_limits`	`src/backend/executor/nodeAgg.c`	1867
`hash_agg_enter_spill_mode`	`src/backend/executor/nodeAgg.c`	1911
`lookup_hash_entries`	`src/backend/executor/nodeAgg.c`	2181
`ExecAgg`	`src/backend/executor/nodeAgg.c`	2244
`agg_retrieve_direct`	`src/backend/executor/nodeAgg.c`	2280
`agg_fill_hash_table`	`src/backend/executor/nodeAgg.c`	2626
`agg_refill_hash_table`	`src/backend/executor/nodeAgg.c`	2680
`agg_retrieve_hash_table`	`src/backend/executor/nodeAgg.c`	2835
`ExecInitAgg`	`src/backend/executor/nodeAgg.c`	3279
`ExecReScanAgg`	`src/backend/executor/nodeAgg.c`	4466
`ExecSort`	`src/backend/executor/nodeSort.c`	50
`ExecInitSort`	`src/backend/executor/nodeSort.c`	221
`ExecReScanSort`	`src/backend/executor/nodeSort.c`	362
`preparePresortedCols`	`src/backend/executor/nodeIncrementalSort.c`	164
`isCurrentGroup`	`src/backend/executor/nodeIncrementalSort.c`	212
`switchToPresortedPrefixMode`	`src/backend/executor/nodeIncrementalSort.c`	286
`DEFAULT_MIN_GROUP_SIZE` (macro)	`src/backend/executor/nodeIncrementalSort.c`	467
`ExecIncrementalSort`	`src/backend/executor/nodeIncrementalSort.c`	495
`ExecInitIncrementalSort`	`src/backend/executor/nodeIncrementalSort.c`	976
`advance_windowaggregate`	`src/backend/executor/nodeWindowAgg.c`	243
`advance_windowaggregate_base`	`src/backend/executor/nodeWindowAgg.c`	420
`eval_windowaggregates`	`src/backend/executor/nodeWindowAgg.c`	664
`begin_partition`	`src/backend/executor/nodeWindowAgg.c`	1194
`spool_tuples`	`src/backend/executor/nodeWindowAgg.c`	1283
`row_is_in_frame`	`src/backend/executor/nodeWindowAgg.c`	1427
`update_frameheadpos`	`src/backend/executor/nodeWindowAgg.c`	1536
`ExecWindowAgg`	`src/backend/executor/nodeWindowAgg.c`	2211
`ExecInitWindowAgg`	`src/backend/executor/nodeWindowAgg.c`	2479

소스 검증 (2026-06-05 기준)

각 항목은 커밋 273fe94(REL_18_STABLE) 현재 소스에 대한 사실에서 시작한다. 다른 자료 없이도 직접 확인 가능한 내용이며, 마지막 문장은 확인 방법을 설명한다.

검증된 사실

ExecAgg는 정확히 네 가지 전략으로 디스패치한다. node->phase->aggstrategy에 대한 switch는 AGG_HASHED(폴스루로 AGG_MIXED에 연결됨), AGG_MIXED, AGG_PLAIN/AGG_SORTED 케이스를 가지며, nodes.h의 열거형은 정확히 AGG_PLAIN, AGG_SORTED, AGG_HASHED, AGG_MIXED를 정의한다. 2026-06-05에 ExecAgg와 AggStrategy 열거형을 직접 읽어 확인했다.
해시 집계는 메모리 또는 그룹 수 초과 시 스필 모드에 진입한다. hash_agg_check_limits는 total_mem = meta_mem + entry_mem + tval_mem을 계산하며, 그룹이 하나 이상 있는 상태에서 total_mem > hash_mem_limit || ngroups > hash_ngroups_limit이 되면 hash_agg_enter_spill_mode를 발동한다. ngroups_limit은 초기 크기를 훨씬 초과해 커지는 전이 상태(예: array_agg)를 위해 존재한다. hash_agg_check_limits와 hash_agg_set_limits를 읽어 확인했다.
스필된 집계는 파티션 논리 테이프 단위로 재귀 처리된다. hash_agg_enter_spill_mode는 LogicalTapeSet과 그룹 집합별 HashAggSpill 하나씩을 생성한다. agg_refill_hash_table은 HashAggBatch 하나를(llast / list_delete_last로 스택 방식으로) 꺼내고 used_bits와 input_card를 넘기며, 자체적으로 다시 스필될 수 있다. hash_agg_enter_spill_mode와 agg_refill_hash_table을 읽어 확인했다.
스필된 튜플은 MinimalTuple로 돌아와 표현식 재컴파일을 강제한다. agg_refill_hash_table이 hashagg_recompile_expressions(aggstate, true, true)를 호출하고 ExecStoreMinimalTuple로 튜플을 저장한 뒤 탐색한다. agg_refill_hash_table을 읽어 확인했다.
AGG_MIXED는 정렬 단계 1에서 해시 테이블을 채우고 단계 0에서 읽어 낸다. agg_retrieve_direct에서 혼합 집계의 단계 1(current_phase == 1) 동안 각 튜플이 lookup_hash_entries도 호출한다. 입력이 끝나면 노드가 initialize_phase(…, 0)하고 agg_retrieve_hash_table로 전환한다. agg_refill_hash_table도 배치 처리를 위해 current_phase를 1로 토글했다가 다시 0으로 돌린다. 두 함수를 모두 읽어 확인했다.
Sort는 완전히 블로킹이며 qual이나 투영을 평가하지 않는다. ExecSort는 첫 번째 튜플을 반환하기 전에 외부 플랜 전체를 tuplesort에 로드하고 (sort_Done이 이를 지킨다), ExecInitSort의 주석은 “Sort 노드는 ExecQual이나 ExecProject를 절대 호출하지 않으므로 ExprContext를 초기화하지 않는다”고 명시한다. ExecSort와 ExecInitSort를 읽어 확인했다.
Sort는 단일 출력 열일 때만 datum 정렬을 선택한다. ExecInitSort는 결과 튜플 디스크립터가 속성 하나일 때 datumSort = true로 설정하고, ExecSort는 그 경우 heap 변형 대신 tuplesort_begin_datum / tuplesort_getdatum을 사용한다. 두 함수를 모두 읽어 확인했다.
증분 정렬의 하이브리드 임계값은 32 튜플이다. #define DEFAULT_MIN_GROUP_SIZE 32. ExecIncrementalSort는 전환을 고려하기 전에 전체 정렬 모드에서 minGroupSize 튜플까지 누적하며, 제한이 있을 때는 minGroupSize를 그 한계에 맞게 조정한다. 매크로와 INCSORT_LOADFULLSORT 블록을 읽어 확인했다.
증분 정렬은 사전 정렬 키를 마지막 키부터 역순으로 비교한다. isCurrentGroup이 for (i = nPresortedCols - 1; i >= 0; i--) 루프를 돌며, 꼬리 키가 먼저 바뀔 가능성이 높아 비교자 호출을 최소화한다는 주석이 달려 있다. isCurrentGroup을 읽어 확인했다.
WindowAgg는 각 파티션을 튜플스토어에 버퍼링하고 역전이 함수로 이동 프레임 집계를 슬라이딩한다. begin_partition이 winstate->buffer를 할당하고, eval_windowaggregates가 세 가지 체제를 문서화하고 구현한다. 고정 UNBOUNDED PRECEDING 헤드에는 증분 순방향 전이, 움직이는 헤드에는 역전이, 역함수가 없거나 NULL을 반환하면 전체 재시작. begin_partition, eval_windowaggregates, advance_windowaggregate_base를 읽어 확인했다.
WindowAgg 하나는 정확히 윈도우 스펙 하나를 처리하며, 여러 스펙은 플래너가 스택으로 쌓는다. 파일 헤더가 각 WindowAgg는 “단일 윈도우 스펙만을 위한 것”이며 플래너가 “중간에 Sort 노드를 끼운 WindowAgg 스택을 생성한다”고 명시한다. nodeWindowAgg.c 헤더 주석을 읽어 확인했다.

미해결 질문

해시 집계 스필의 파티션 수와 재파티션 비트 할당은 무엇으로 결정되는가? hash_choose_num_partitions와 HashAggBatch의 used_bits 계산은 호출 위치에서 읽었지만, 비트 예산 수학(HASHAGG_MAX_PARTITIONS, 파티션 팬아웃과 재귀 깊이 사이의 비용 균형)은 추적하지 않았다. 조사 경로: nodeAgg.c의 hash_choose_num_partitions와 hashagg_spill_init.
WINDOWAGG_PASSTHROUGH_STRICT는 상위 WindowAgg에 행을 올려보내야 하는 비최상위 WindowAgg와 어떻게 상호작용하는가? spool_tuples는 패스스루 상태에서도 상위 WindowAgg를 위해 행을 유지한다. PASSTHROUGH 대 PASSTHROUGH_STRICT를 선택하는 정확한 조건(runCondition 푸시다운과 연관됨)은 부분적으로만 추적했다. 조사 경로: ExecWindowAgg의 status 할당 주변에서 runCondition 처리를 읽는다.
Sort 노드와 tuplesort.c의 제한/병렬 모드 경계는 어디인가? 이 문서는 런 생성, 테이프 합병, 상위-N 힙을 블랙박스로 취급한다. 병렬 워커 Sort 경로 (shared_info, tuplesort_get_stats)는 확인했지만 분석하지 않았다. 조사 경로: postgres-tuplesort.md 및 nodeSort.c의 am_worker 브랜치.

PostgreSQL 너머 — 비교 설계와 연구 프론티어

포인터만 제공한다. 각 항목은 후속 문서의 출발점이며, 여기서의 깊이는 의도적으로 얕게 유지한다.

PostgreSQL의 해시 집계 스필은 최근에 추가된 기능이다. PG 13 이전에는 해시 집계가 work_mem을 무제한으로 초과할 수 있었다. 플래너는 너무 많은 그룹이 예상되면 단순히 해시 집계를 회피했는데, 이 추정이 틀리는 경우도 있었다. 파티션 스필 기계(hash_agg_enter_spill_mode, HashAggBatch)는 PG 13에서 Jeff Davis가 추가해 PostgreSQL을 DSC §15.5 및 해시 조인 문헌이 오랫동안 전제했던 “그레이스 해시(grace hash)” / 파티션-재귀 패턴에 맞게 했다. 해시 조인 스필과 나란히 비교하면 두 기계가 얼마나 많은 코드를 공유하는지 알 수 있다.
CUBRID의 집계 및 정렬 경로. CUBRID는 집계를 XASL 트리 내부의 GROUPBY / aggregate_list 메커니즘과 별도 외부 정렬 유틸리티로 처리한다. 그러나 해시 집계 및 그룹 집합 지원, 그리고 비슷한 방식으로 스필하는지 여부는 PostgreSQL의 단계 체인과 다르다. 두 엔진이 단일 정렬 패스에서 ROLLUP/CUBE를 처리하는 방식을 비교하면 PostgreSQL의 AGG_MIXED 단계 기계가 무엇을 얻어 내는지 더 명확히 드러날 것이다.
벡터화 집계와 정렬. 튜플 단위 전이 호출은 벡터화 엔진이 공략하는 바로 그 튜플별 오버헤드다. MonetDB/X100(Boncz, Zukowski & Nes, CIDR 2005)과 컬럼 스토어 계보(dbms-papers/cstore.md)는 그룹화 키 벡터를 직접 집계하고 벡터화된 파티션 정렬을 사용한다. PostgreSQL은 튜플 단위 방식을 유지하며, ExecBuildAggTrans가 인수 평가와 전이 호출을 하나의 JIT 가능 표현식으로 융합하는 것 (postgres-expression-eval.md, postgres-jit.md)이 인터프리터 오버헤드에 대한 대응이다.
런타임 적응 집계 — 실행 중 해시 대 정렬 결정. PostgreSQL은 플랜 타임에 전략을 고정한다. Hellerstein의 eddies 계열 연구나 최근 HyPer/Umbra의 런타임 적응 연산자 같은 시스템들은 실제 카디널리티를 보고 해싱과 정렬 사이를 전환한다. 연구 프론티어는 실제 그룹 수를 본 후 집계 물리 연산자를 선택하고 재선택하는 것이며, 이는 PostgreSQL의 플랜 타임 AggStrategy 태그를 런타임 변수로 만드는 일이다.
근사 사전 정렬 입력 최적화로서의 증분 정렬. 증분 정렬(PG 13, Tomáš Vondra / James Coleman)은 Timsort의 런 감지, 자연 합병 정렬 같은 적응 정렬에서도 볼 수 있는 “사전 정렬 활용” 아이디어의 PostgreSQL 구현이다. 프론티어 질문은 플래너가 이를 충분히 자주 선택하는가다. 부분 정렬된 자식과 LIMIT 조합에서 빛나지만, 전체 정렬 대비 비용 교차점은 추정에 민감하다. postgres-path-generation.md에서 IncrementalSort 경로 선택을 연구하면 이 고리가 닫힐 것이다.
윈도우 함수 프레임 알고리즘. 역전이 트릭(Leis et al., “Efficient Processing of Window Functions in Analytical SQL Queries”, VLDB 2015, HyPer 그룹)은 비가역 집계(예: 줄어드는 프레임 위의 max)를 처리할 때 PostgreSQL의 선형 순방향+역방향+재시작 삼분법을 능가하는 세그먼트 트리 및 집계 트리 접근법을 형식화한다. PostgreSQL은 그 삼분법을 구현하지만 트리 기반 O(log n) 프레임 집계는 구현하지 않는다. 이 간극이 구체적인 최적화 프론티어다.

출처

코드 (REL_18_STABLE, 커밋 273fe94, PG 18.x) — 소스 진실:
- src/backend/executor/nodeAgg.c — Agg 전략, 해시 스필, 그룹 집합 단계.
- src/backend/executor/nodeSort.c — tuplesort.c 위의 블로킹 Sort.
- src/backend/executor/nodeIncrementalSort.c — 네 가지 상태 증분 정렬.
- src/backend/executor/nodeWindowAgg.c — 파티션 버퍼링, 프레임 슬라이딩, 역전이.
- src/include/nodes/nodes.h — AggStrategy 열거형.
- src/include/nodes/execnodes.h — AggState, SortState, IncrementalSortState(INCSORT_*), WindowAggState(WINDOWAGG_*).
- src/include/nodes/parsenodes.h — FRAMEOPTION_* 윈도우 프레임 플래그.
이론 — knowledge/research/dbms-general/database-system-concepts.md (Silberschatz 7판): §15.4 정렬(외부 정렬-합병), §15.5 집계(정렬 대 해시), §15.7.2 파이프라인 대 블로킹 연산자, §5.5.1 윈도잉.
형제 코드 분석 문서 (교차 참조, 중복 없음):
- postgres-executor.md — PlanState 트리, ExecProcNode 풀 프로토콜, TupleTableSlot, 메모리 컨텍스트.
- postgres-tuplesort.md — tuplesort.c 엔진(런 생성, 테이프 합병, 상위-N 힙, datum 대 heap 정렬, 병렬 정렬).
- postgres-expression-eval.md — ExprState / ExecBuildAggTrans(융합 전이 표현식), qual 및 투영 평가.
- postgres-planner-overview.md, postgres-path-generation.md — 전략/경로가 선택되는 이유.
비교 포인터 — dbms-papers/cstore.md(컬럼 스토어 / 벡터화 대비); MonetDB/X100 (Boncz et al., CIDR 2005); Leis et al., “Efficient Processing of Window Functions in Analytical SQL Queries”(VLDB 2015).