(KO) PostgreSQL tuplesort — 인메모리 퀵정렬, 외부 병합 정렬, 논리 테이프, Tuplestore

목차

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

학술적 배경

정렬은 컴퓨팅에서 가장 오래된 문제 중 하나이면서 관계형 엔진 내부에서 가장 많이 쓰이는 연산이기도 하다. ORDER BY가 가장 눈에 띄는 소비자이지만, 정렬은 병합 조인, 정렬 기반 GROUP BY/DISTINCT, CREATE INDEX(B-트리는 힙 튜플을 정렬한 뒤 리프를 벌크 로드해 구축한다), 윈도우 함수, UNION의 기반이기도 하다. 모든 데이터베이스 정렬 구현을 조직하는 핵심 사실은 하나다. 데이터가 메모리에 맞지 않을 수 있다. 교과서의 인메모리 qsort는 전체 배열에 대한 랜덤 접근을 전제 하지만, 데이터베이스는 그 전제를 할 수 없다. 따라서 빠른 인메모리 정렬에서 각 데이터를 제한된 횟수만큼만 접근하는 디스크 기반 정렬로 우아하게 하강해야 한다. Knuth의 The Art of Computer Programming 3권(Sorting and Searching)이 표준 참고 문헌이며, PostgreSQL 소스 주석도 직접 인용한다. 병합 힙은 “Algorithm 5.2.3H”, 런 생성 루프는 “Algorithm 5.4.1, replacement selection”에서 이어진다. Database System Concepts(Silberschatz 7판, 15장 “Query Processing”)은 같은 내용을 DBMS 관점에서 **외부 정렬-병합(external sort-merge)**으로 정리한다.

외부 정렬-병합 알고리즘은 두 단계로 구성된다.

1. 런 생성(run generation). 입력을 메모리 버짓 M 페이지 단위로 읽고, 각 청크를 인메모리 정렬 후 *정렬된 런(sorted run)*으로 기록한다. 이 단계가 끝나면 입력이 디스크 위 ⌈N/M⌉개의 정렬된 런으로 변환되며, N은 입력 페이지 수다.

2. 병합(merge). 런들을 하나로 합친다. 단일 병합 패스는 한 번에 최대 M-1개의 런을 합칠 수 있으므로(런당 입력 버퍼 1개, 출력 버퍼 1개), 모든 것을 하나로 줄이려면 ⌈log_{M-1}(N/M)⌉번의 패스가 필요하다. 각 패스는 전체 데이터 집합을 한 번씩 읽고 쓰므로 총 I/O는 2N · (1 + ⌈log_{M-1}(N/M)⌉) 페이지 전송이다. 현실적인 M 값에서는 테라바이트 데이터도 두세 번의 패스로 충분하다.

이 골격에서 실제 코드를 이해하는 데 중요한 두 가지 발전이 있다. 첫째는 대체 선택(replacement selection)(Knuth 5.4.1)이다. 고정 M 페이지 청크를 정렬하는 대신, M개의 튜플로 구성된 힙을 유지하며 가장 작은 것을 방출할 때마다 입력에서 하나를 더 읽는다. 새 튜플이 방금 방출한 것 이상이면 현재 런에, 그렇지 않으면 다음 런을 위해 보관한다. 부분적으로 정렬된 입력에서는 평균 2M 페이지 런이 생성되어 런 수와 병합 패스를 절반으로 줄인다. 반면 AlphaSort 논문(Nyberg et al. 1994, AlphaSort: A Cache-Sensitive Parallel External Sort, dbms-papers/alphasortsigmod.md)은 현대 캐시 바운드 하드웨어에서는 반대가 성립한다고 주장한다. 대체 선택은 캐시보다 큰 힙에 랜덤 접근하므로 지역성이 나쁘다. 따라서 CPU 캐시에 맞는 짧은 퀵정렬 런을 생성하고 패스를 하나 더 치르는 편이 더 빠를 수 있다. PostgreSQL은 이 교훈을 그대로 수용했다. 2016년에 런 생성에서 대체 선택을 퇴출하고 퀵정렬 런으로 교체했으며, 힙은 병합에만 남겼다.

둘째는 비교 비용 자체다. 외부 정렬 비용은 보통 페이지 I/O로 모델링하지만, 중간 규모 데이터의 인메모리 정렬에서는 비교자가 병목이 된다. text 비교는 OS 콜레이션 라이브러리로 strcoll을 호출할 수 있으며, 이는 수백 사이클에 달한다. 단축 키(abbreviated key) 기법은 선두 정렬 컬럼의 고정 크기 순서 보존 프록시를 저장한다. C 유사 콜레이션 하의 text라면 8바이트를 Datum에 압축해, 일반적인 경우 단일 정수 비교로 해결하고 동점일 때만 비싼 전체 비교자로 넘어간다. 이는 반복되는 주제다. 비교 횟수는 O(N log N)이라 줄이기 어려우므로, 엔진들은 비교당 비용을 낮추는 쪽을 공략한다.

마지막으로 바운드(bounded) 경우(ORDER BY ... LIMIT n)는 점근적으로 다르다. N개 항목을 모두 정렬하지 않고도 가장 작은 n개를 반환할 수 있다. 크기 n의 바운드 최댓값 힙(bounded max-heap)은 O(N log n) 시간과 O(n) 공간으로 이를 해결하며, N이 아무리 커도 디스크에 스필하지 않는다. PatSort/patience-sort (Chandramouli & Goldstein 2014, Patience is a Virtue, dbms-papers/patsort-sigmod14.md)는 입력의 기존 런을 활용하는 또 다른 축을 탐구한다. PostgreSQL은 이를 구현하지 않지만, 퀵정렬 기반 런 생성이 남겨 두는 여지를 잘 보여 준다.

DBMS 공통 설계 패턴

진지한 엔진은 결국 같은 힘에 의해 형성된 정렬 컴포넌트를 갖게 된다. 공통 관례를 먼저 정의해 두면, PostgreSQL 심볼들이 알려진 설계 공간에서의 선택지로 읽힌다.

하나의 컴포넌트, 두 가지 체제

데이터베이스 정렬 모듈은 거의 항상 단일 상태 기계로 작성된다. 처음에는 인메모리로 낙관적으로 시작하다가 반드시 필요할 때만 디스크로 낙하한다. 공통 패턴은 다음과 같다.

• 먼저 쌓고, 나중에 결정. 튜플이 도착하는 대로 인메모리 배열에 복사한다. 소비된 메모리 누계를 버짓(work_mem)과 비교하며, 버짓이 버티는 한 I/O나 테이프 기계는 건드리지 않는다.
• 외부 모드로의 단방향 전환. 버짓이 초과되는 순간 외부 정렬을 확정한다. 지금까지 가진 것을 첫 번째 런으로 정렬해 쓰고, 이후로는 런 단위로 동작한다. 전환은 단방향이며, 런 하나를 스필하고 나면 되돌아올 수 없다.
• 런 생성, 그리고 병합. 빌드 단계가 정렬된 런들을 만들면, 병합 단계가 이를 합친다. 병합은 각 런의 현재 선두 튜플을 담은 선택 트리, 루저 트리, 또는 단순 이진 힙을 사용해 출력 튜플 하나당 M 선두를 선형 스캔하는 대신 log(M) 힙 시프트만 수행한다.

임시 파일 공간 문제

“테이프당 OS 파일 하나”라는 나이브한 설계에는 악명 높은 결함이 있다. 최종 병합 중에 모든 데이터가 입력 런과 출력 런에 동시에 존재하므로, 피크 디스크 사용량이 데이터 볼륨의 약 2배가 된다. 디스크 공간을 신경 쓰는 엔진들은 모든 논리 테이프를 단일 백킹 파일에 묶고, 읽는 즉시 블록을 전역 프리 풀로 재활용함으로 써 이 문제를 해결한다. 각 런은 정확히 한 번 순차 읽기되므로, 병합이 블록을 소비하는 즉시 그 공간이 출력 런에 재사용된다. 피크 사용량이 약 1x로 떨어진다.

비교 비용 최적화

• 단축/정규화 키(abbreviated / normalized keys). 선두 컬럼의 고정 크기 정렬 가능 프록시를 기계 정수로 비교하되, 동점 시 전체 비교자로 폴백한다. 단축이 구별 능력을 발휘하지 못하는 경우(예: 거의 동일한 긴 문자열 컬럼)를 대비해, 좋은 구현은 정렬 중 측정하다가 효과가 없으면 최적화를 중단한다.
• 타입 특화 비교자(type-specialized comparators). 일반 int4/int8/Datum 케이스에서 간접 funcptr(a,b) 호출을 인라인 정수 비교로 대체하면, 호출 오버헤드와 분기 예측 실패가 비교당 한 번씩 제거된다.

바운드(top-N) 정렬

ORDER BY ... LIMIT n은 고정 크기 힙으로 특수 처리된다. 지금까지 본 것 중 가장 작은 n개를 최댓값 힙에 유지하되, 보유한 것 중 가장 큰 것이 루트에 오도록 키를 반전한다. 새 튜플은 루트보다 좋지 않으면 비교 한 번에 버려진다. 이 경로는 스필하지 않으며 O(N log n)으로 동작한다.

정렬 없는 형제 컴포넌트

엔진들은 순서를 바꾸지 않고 튜플 스트림을 버퍼링해야 하기도 한다. 뒤로 스크롤 하는 커서, 내부 릴레이션을 재읽는 Materialize 노드, 재귀 CTE 작업 테이블이 대표적이다. 이는 훨씬 단순한 컴포넌트다. 인메모리-후-스필 구조와 메모리 회계를 공유하지만, 비교자도 없고 런도 없으며 하나 이상의 읽기 커서를 가진 시퀀스다. PostgreSQL은 이를 tuplestore라고 부른다.

flowchart TD
  IN["incoming tuples"] --> ACC["accumulate in memtuples[]<br/>track availMem"]
  ACC --> FIT{"fit in work_mem?"}
  FIT -->|"yes, at performsort"| QS["in-memory quicksort<br/>TSS_SORTEDINMEM"]
  FIT -->|"no: budget exceeded"| EXT["switch to external<br/>TSS_BUILDRUNS"]
  EXT --> RUN["quicksort this batch<br/>write sorted run to a tape"]
  RUN --> MORE{"more input?"}
  MORE -->|"yes"| RUN
  MORE -->|"no"| MERGE["merge runs with<br/>binary min-heap"]
  MERGE --> PASS{"runs left > merge order?"}
  PASS -->|"yes"| MERGE
  PASS -->|"no: 1 run"| DONE["TSS_SORTEDONTAPE /<br/>TSS_FINALMERGE on the fly"]
  QS --> OUT["gettuple returns sorted order"]
  DONE --> OUT

PostgreSQL의 구현

PostgreSQL은 위의 모든 내용을 tuplesort.c 하나에 구현하며, 테이프 메카닉을 logtape.c에, 정렬 없는 형제를 tuplestore.c에 분리한다. 제네릭 엔진은 타입에 무관하다. 호출자는 tuplesortvariants.c에서 comparetup/writetup/readtup 콜백을 제공하며(힙 튜플, 인덱스 튜플, datum, BRIN, GIN), 코어 엔진은 오직 SortTuple 구조체만 다룬다.

SortTuple — 엔진이 실제로 섞는 것

엔진은 HeapTuple을 직접 정렬하지 않는다. 선두 키를 인라인으로 담은 작은 고정 크기 SortTuple 구조체 배열을 정렬하며, 일반적인 비교에서 heap_getattr 없이 처리할 수 있다.

// SortTuple — src/include/utils/tuplesort.h
typedef struct
{
  void     *tuple;      /* the tuple itself */
  Datum    datum1;      /* value of first key column */
  bool    isnull1;    /* is first key column NULL? */
  int      srctape;    /* source tape number */
} SortTuple;

datum1은 값 전달 타입이면 선두 컬럼 값을, 단축이 활성화되어 있으면 단축 프록시를 담는다. srctape는 병합 중 힙 원소가 어느 런에서 왔는지 알기 위해서만 쓰인다. 전체 튜플은 별도 palloc 청크(또는 병합 중에는 슬랩 슬롯)에서 tuple에 매달린다.

6가지 상태 기계

Tuplesortstate는 여섯 가지 가능한 상태를 순회하며, 모듈 전체가 현재 상태에 대한 스위치다.

// TupSortStatus — src/backend/utils/sort/tuplesort.c
typedef enum
{
  TSS_INITIAL,        /* Loading tuples; still within memory limit */
  TSS_BOUNDED,        /* Loading tuples into bounded-size heap */
  TSS_BUILDRUNS,        /* Loading tuples; writing to tape */
  TSS_SORTEDINMEM,      /* Sort completed entirely in memory */
  TSS_SORTEDONTAPE,      /* Sort completed, final run is on tape */
  TSS_FINALMERGE,        /* Performing final merge on-the-fly */
} TupSortStatus;

TSS_INITIAL은 낙관적 인메모리 상태다. work_mem을 초과하지 않으면 performsort가 배열을 퀵정렬하고 TSS_SORTEDINMEM으로 이동한다. 테이프도 없고 I/O도 없다. 메모리를 초과하면 TSS_BUILDRUNS로 이동해 런을 스필한다. TSS_BOUNDED는 LIMIT-n 힙이다. 두 외부 종료 상태는 단일 결과 테이프가 존재하는지(TSS_SORTEDONTAPE, 예: 랜덤 접근용으로 병합이 하나의 런으로 수렴한 경우), 아니면 호출자가 튜플을 당기면서 최종 병합이 지연 수행되는지(TSS_FINALMERGE)에 따라 갈린다.

flowchart TD
  INIT["TSS_INITIAL<br/>accumulate in memtuples[]"]
  INIT -->|"bounded and count > 2*bound"| BND["TSS_BOUNDED<br/>fixed-size max-heap of n"]
  INIT -->|"work_mem exceeded:<br/>inittapes + dumptuples"| BR["TSS_BUILDRUNS<br/>quicksort each run to tape"]
  INIT -->|"performsort, fit in memory"| SIM["TSS_SORTEDINMEM<br/>final quicksort"]
  BND -->|"performsort:<br/>sort_bounded_heap"| SIM
  BR -->|"performsort: dumptuples<br/>then mergeruns"| FM["TSS_FINALMERGE<br/>merge on the fly"]
  BR -->|"mergeruns collapses to 1 run<br/>or random access requested"| SOT["TSS_SORTEDONTAPE<br/>single frozen result tape"]
  SIM --> GET["tuplesort_gettuple_common"]
  FM --> GET
  SOT --> GET

런 생성은 퀵정렬 기반, 대체 선택 아님

이것이 코드에 담긴 AlphaSort 교훈이다. 메모리가 찰 때마다 dumptuples는 전체 memtuples 배열을 퀵정렬하고 대상 테이프에 하나의 런으로 스트리밍한 뒤 튜플 메모리를 초기화한다.

// dumptuples — src/backend/utils/sort/tuplesort.c
/* Sort all tuples accumulated within the allowed amount of memory for
 * this run using quicksort */
tuplesort_sort_memtuples(state);
/* ... */
memtupwrite = state->memtupcount;
for (i = 0; i < memtupwrite; i++)
{
  SortTuple  *stup = &state->memtuples[i];
  WRITETUP(state, state->destTape, stup);
}
state->memtupcount = 0;
/* ... reset tuplecontext, FREEMEM(tupleMem), markrunend ... */
markrunend(state->destTape);

따라서 런은 대략 work_mem 크기이며, 각 런은 독립적으로 퀵정렬된다. AlphaSort의 캐시 친화성 논거에 따른 선택이다. 대체 선택보다 런이 더 많이 생겨 추가 병합 패스가 필요할 수 있다는 트레이드오프가 있다.

특화된 퀵정렬

인메모리 정렬(전체 인메모리 케이스와 각 런 모두)은 사용 가능한 가장 저렴한 퀵정렬로 디스패치된다. 선두 키가 알려진 정수 비교자를 가진 순수 Datum이라면, 비교자 함수 포인터 호출을 완전히 피하는 완전 인라인 타입 특화 변형을 사용한다.

// tuplesort_sort_memtuples — src/backend/utils/sort/tuplesort.c
if (state->base.haveDatum1 && state->base.sortKeys)
{
  if (state->base.sortKeys[0].comparator == ssup_datum_unsigned_cmp)
  {
    qsort_tuple_unsigned(state->memtuples, state->memtupcount, state);
    return;
  }
#if SIZEOF_DATUM >= 8
  else if (state->base.sortKeys[0].comparator == ssup_datum_signed_cmp)
  {
    qsort_tuple_signed(state->memtuples, state->memtupcount, state);
    return;
  }
#endif
  else if (state->base.sortKeys[0].comparator == ssup_datum_int32_cmp)
  {
    qsort_tuple_int32(state->memtuples, state->memtupcount, state);
    return;
  }
}
/* Can we use the single-key sort function? */
if (state->base.onlyKey != NULL)
  qsort_ssup(state->memtuples, state->memtupcount, state->base.onlyKey);
else
  qsort_tuple(state->memtuples, state->memtupcount,
        state->base.comparetup, state);

이 qsort_tuple* 함수들은 sort_template.h에서 생성된다. 삽입 정렬 컷오프를 가진 인터럽트 가능한 인트로정렬 스타일 퀵정렬인데, 핫 비교가 인라인 정수 비교라는 점이 특화점이다.

단축 키 — 측정하고 중단 가능

sortKeys[0]이 abbrev_converter를 제공하면, tuplesort_puttuple_common은 각 튜플이 도착할 때 datum1을 단축 프록시로 교체한다. 중요한 점은 단축이 효과를 발휘하는지 주기적으로 opclass에 묻고, 그렇지 않으면 이미 저장된 datum1을 실제 값으로 되돌리며 중단한다는 것이다.

// tuplesort_puttuple_common — src/backend/utils/sort/tuplesort.c
if (!useAbbrev)
{
  /* Leave ordinary Datum representation, or NULL value. ... */
}
else if (!consider_abort_common(state))
{
  /* Store abbreviated key representation */
  tuple->datum1 = state->base.sortKeys->abbrev_converter(tuple->datum1,
                               state->base.sortKeys);
}
else
{
  /* Set state to be consistent with never trying abbreviation. */
  REMOVEABBREV(state, state->memtuples, state->memtupcount);
}

consider_abort_common은 지수적으로 증가하는 간격(abbrevNext이 각 확인마다 두 배)으로 샘플링하고 opclass의 abbrev_abort를 호출해 지금까지 본 단축들이 충분히 구별력이 있는지 판단한다. 단축은 외부 모드로 전환된 후에도 자동으로 비활성화된다. 테이프 위 직렬화된 튜플은 단축 키를 담지 않으므로, mergeruns가 런을 다시 읽기 전에 abbrev_converter를 null로 만든다.

소스 코드 가이드

이 섹션은 호출 흐름별로 안정적인 심볼들을 나열하고 포지션 힌트 테이블로 마무리한다. 서술 앵커는 공개 API(tuplesort_begin_* → tuplesort_puttuple_common → tuplesort_performsort → tuplesort_gettuple_common), 외부 정렬 기계(inittapes, dumptuples, mergeruns, mergeonerun, beginmerge), 논리 테이프 레이어, 그리고 tuplestore다.

튜플 적재와 단방향 전환 (tuplesort.c)

tuplesort_begin_common이 상태와 초기 memtuples 배열을 할당한다. tuplesortvariants.c 의 타입별 tuplesort_begin_heap/_begin_datum/_begin_index_* 래퍼들이 비교자/IO 콜백을 설치한다. 튜플은 tuplesort_puttuple_common으로 진입하며, TSS_INITIAL 분기가 인메모리-vs-외부 결정의 핵심이다.

// tuplesort_puttuple_common (TSS_INITIAL arm) — src/backend/utils/sort/tuplesort.c
case TSS_INITIAL:
  /* Save the tuple into the unsorted array. First, grow the array
   * as needed. ... if we fail, there'll still be room to store the
   * incoming tuple, and then we'll switch to tape-based operation. */
  if (state->memtupcount >= state->memtupsize - 1)
  {
    (void) grow_memtuples(state);
    Assert(state->memtupcount < state->memtupsize);
  }
  state->memtuples[state->memtupcount++] = *tuple;

  /* ... bounded-sort switch check (see below) ... */

  /* Done if we still fit in available memory and have array slots. */
  if (state->memtupcount < state->memtupsize && !LACKMEM(state))
  {
    MemoryContextSwitchTo(oldcontext);
    return;
  }

  /* Nope; time to switch to tape-based operation. */
  inittapes(state, true);
  dumptuples(state, false);
  break;

두 종료 조건은 배열 가득 참(memtupcount >= memtupsize, 배열이 더 자라지 못함)과 메모리 부족(LACKMEM — availMem < 0)이다. 둘 중 하나가 inittapes와 첫 dumptuples를 촉발한다. 이후 상태는 TSS_BUILDRUNS이며, 이후 puttuple 호출은 TSS_BUILDRUNS 분기에 착지해 배열에 추가하고 메모리가 찰 때마다 dumptuples를 호출해 새 런을 만든다.

grow_memtuples는 배열을 두 배로 늘리지만, 두 배가 메모리 버짓을 날려버릴 때 성장을 중단(growmemtuples = false)하므로 배열 성장과 스필 결정이 깔끔하게 맞물린다.

tuplesort_performsort — 분기점

performsort는 누적된 상태가 마무리되는 곳이다. 현재 상태에 대한 스위치다.

// tuplesort_performsort — src/backend/utils/sort/tuplesort.c
case TSS_INITIAL:
  if (SERIAL(state))
  {
    /* Just qsort 'em and we're done */
    tuplesort_sort_memtuples(state);
    state->status = TSS_SORTEDINMEM;
  }
  else if (WORKER(state))
  {
    /* Parallel workers must still dump out tuples to tape. No
     * merge is required to produce single output run, though. */
    inittapes(state, false);
    dumptuples(state, true);
    worker_nomergeruns(state);
    state->status = TSS_SORTEDONTAPE;
  }
  else
  {
    /* Leader will take over worker tapes and merge worker runs. */
    leader_takeover_tapes(state);
    mergeruns(state);
  }
  break;

case TSS_BOUNDED:
  sort_bounded_heap(state);   /* heap -> sorted array */
  break;

case TSS_BUILDRUNS:
  dumptuples(state, true);    /* flush the last run */
  mergeruns(state);           /* sets TSS_SORTEDONTAPE or TSS_FINALMERGE */
  break;

TSS_INITIAL의 세 하위 케이스는 각각 단순 직렬 정렬(모두 맞으면 퀵정렬), 병렬 워커(자체 테이프에 하나의 런을 구체화해야 함, 로컬 병합 불필요), 병렬 리더 (자체 정렬을 하지 않고 워커 테이프를 가져와 병합)에 해당한다.

테이프 구성: inittapes, selectnewtape, tuplesort_merge_order

inittapes는 병합 차수를 선택하고 LogicalTapeSet을 생성하며 첫 출력 테이프를 선택한다. 병합 차수는 순전히 work_mem에서 도출된다.

// tuplesort_merge_order — src/backend/utils/sort/tuplesort.c
mOrder = allowedMem / (2 * TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE);
/* Even in minimum memory, use at least a MINORDER merge. ... do not use
 * more than a MAXORDER merge. ... high order merges are quite slow due to
 * CPU cache effects; it can be faster to pay the I/O cost of a multi-pass
 * merge than to perform a single merge pass across many hundreds of tapes. */
mOrder = Max(mOrder, MINORDER);   /* MINORDER == 6   */
mOrder = Min(mOrder, MAXORDER);   /* MAXORDER == 500 */
return mOrder;

이것이 현대(9.6 이후) 테이프 모델이다. 더 이상 고정 “7개 테이프” 폴리페이즈 방식은 없다. MINORDER = 6, MAXORDER = 500이며, 테이프마다 BLCKSZ 블록 하나와 MERGE_BUFFER_SIZE(= BLCKSZ * 32) 프리페치 윈도우가 예산에 들어간다. 500 상한은 소스 주석에서 명시적으로 정당화된다. 그 이상에서는 캐시 효과 탓에 고차 병합이 추가 패스보다 느려진다.

selectnewtape는 라운드 로빈 런 배치를 구현한다. maxTapes보다 적은 출력 테이프가 있는 동안은 런당 새 테이프를 만들고, 이후로는 nOutputTapes 모듈로 기존 테이프에 런을 추가한다. 따라서 1000개의 런과 병합 차수 500이 있으면, 각각 약 2개의 런을 담은 500개의 테이프가 균형 다중 패스 병합을 위해 준비된다.

병합: mergeruns, mergeonerun, beginmerge

mergeruns는 균형 k-방향 병합 드라이버다. 먼저 큰 memtuples 배열을 해제하고 (힙에는 입력 테이프당 슬롯 하나면 충분하므로 더 이상 work_mem/런 분량의 슬롯이 필요 없다), 튜플 메모리를 슬랩 할당자(고정 크기 슬롯, 단편화 없음)로 전환하고, 나머지 메모리를 테이프 프리페치 버퍼로 준다.

// mergeruns — src/backend/utils/sort/tuplesort.c
/* We no longer need a large memtuples array. ... */
FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
pfree(state->memtuples);
/* Initialize the slab allocator. We need one slab slot per input tape,
 * for the tuples in the heap, plus one to hold the tuple last returned
 * from tuplesort_gettuple. */
if (state->base.tuples)
  init_slab_allocator(state, state->nOutputTapes + 1);
/* Allocate a new 'memtuples' array, for the heap. It will hold one tuple
 * from each input tape. */
state->memtupsize = state->nOutputTapes;
state->memtuples = (SortTuple *) MemoryContextAlloc(state->base.maincontext,
                          state->nOutputTapes * sizeof(SortTuple));
/* Use all the remaining memory we have available for tape buffers ... */
state->tape_buffer_mem = state->availMem;

이후 루프를 돈다. 새 패스를 시작하는 각 반복은 이전 패스의 출력 테이프를 다음 패스의 입력 테이프로 전환하고, 버퍼 메모리를 분배하고, 병합한다. 패스 후 런이 하나 이상 남으면 다시 루프한다(다중 패스 병합). 런이 하나만 남으면 병합 완료다. 랜덤 접근이 필요하지 않을 때, mergeruns는 하나 짧게 멈춘다. 테이프에 <= maxTapes개의 런이 남았을 때 병합을 완료하지 않고 gettuple이 최종 병합을 즉석에서 수행하도록 내버려 둔다. 이것이 TSS_FINALMERGE 상태다. 마지막으로 전체 데이터 집합을 한 번 더 쓰는 것을 절약한다.

실제 한 세트의 런을 병합하는 것은 교과서 힙 병합이다.

// mergeonerun — src/backend/utils/sort/tuplesort.c
beginmerge(state);                       /* load 1 tuple from each input tape */
while (state->memtupcount > 0)
{
  /* write the smallest (heap root) to destTape */
  srcTapeIndex = state->memtuples[0].srctape;
  srcTape = state->inputTapes[srcTapeIndex];
  WRITETUP(state, state->destTape, &state->memtuples[0]);
  if (state->memtuples[0].tuple)
    RELEASE_SLAB_SLOT(state, state->memtuples[0].tuple);

  /* pull next tuple from that same tape, replace heap root with it */
  if (mergereadnext(state, srcTape, &stup))
  {
    stup.srctape = srcTapeIndex;
    tuplesort_heap_replace_top(state, &stup);
  }
  else
  {
    tuplesort_heap_delete_top(state);   /* that run is exhausted */
    state->nInputRuns--;
  }
}
markrunend(state->destTape);

beginmerge는 각 활성 테이프의 선두 튜플로 힙을 초기화한다. 힙 자체는 이진 최솟값 힙(tuplesort_heap_insert / tuplesort_heap_replace_top / tuplesort_heap_delete_top)으로, Knuth 5.2.3H에 따라 구현된다. replace_top이 핫 오퍼레이션으로, 루트를 덮어쓰고 한 번의 패스에 아래로 시프트해 삭제-후-삽입 쌍을 피한다.

바운드(top-N) 정렬

플래너가 LIMIT n을 알면 tuplesort_set_bound를 호출하고, TSS_INITIAL 분기는 고정 크기 힙이 모든 것을 유지하는 것보다 저렴해지는 순간을 감시한다.

// tuplesort_puttuple_common (bounded switch) — src/backend/utils/sort/tuplesort.c
if (state->bounded &&
  (state->memtupcount > state->bound * 2 ||
   (state->memtupcount > state->bound && LACKMEM(state))))
{
  make_bounded_heap(state);   /* -> TSS_BOUNDED */
  return;
}

make_bounded_heap은 정렬 방향을 반전(보유 세트 중 가장 큰 것이 루트에 오도록)하고 정확히 bound개의 요소로 힙을 구성한다. 이후 TSS_BOUNDED 분기는 현재 루트보다 작지 않은 들어오는 튜플을 단일 비교로 버리거나, 그렇지 않으면 루트와 교체한다.

// tuplesort_puttuple_common (TSS_BOUNDED arm) — src/backend/utils/sort/tuplesort.c
case TSS_BOUNDED:
  if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
  {
    /* new tuple <= top of the heap, so we can discard it */
    free_sort_tuple(state, tuple);
  }
  else
  {
    /* discard top of heap, replacing it with the new tuple */
    free_sort_tuple(state, &state->memtuples[0]);
    tuplesort_heap_replace_top(state, tuple);
  }
  break;

이 경로는 스필하지 않는다. 힙은 O(bound) 크기이며, performsort 시점에 sort_bounded_heap이 제자리에서 정렬된 배열로 변환한다. 이론 섹션에서 설명한 점근적 이득이 여기에 있다. O(N log N) 대신 O(N log n)이다.

병렬 정렬: 워커는 런을, 리더는 병합을

PostgreSQL은 각 워커가 입력의 자신 몫을 공유 SharedFileSet 내 워커 소유의 논리 테이프 하나에 정렬해 하나의 런으로 만들도록 정렬을 병렬화한다. 리더는 자체 스캔이나 정렬을 수행하지 않는다. 워커들의 고정된 테이프를 임포트해 최종 병합 하나를 실행한다. 세 매크로가 상태를 분류한다.

// SERIAL / WORKER / LEADER — src/backend/utils/sort/tuplesort.c
#define SERIAL(state)    ((state)->shared == NULL)
#define WORKER(state)    ((state)->shared && (state)->worker != -1)
#define LEADER(state)    ((state)->shared && (state)->worker == -1)

worker_nomergeruns(워커의 performsort에서 호출됨)는 워커의 단일 출력 테이프를 결과로 고정한다. leader_takeover_tapes가 리더 측 글루다. 모든 워커가 끝났음을 확인한 뒤, 각 워커 테이프를 임포트하고 리더 상태가 마치 런을 직접 생성한 것처럼 보이도록 조정해 mergeruns가 수정 없이 실행될 수 있게 한다.

// leader_takeover_tapes — src/backend/utils/sort/tuplesort.c
/* There will always be exactly 1 run per worker, and exactly one input
 * tape per run, because workers always output exactly 1 run ... */
state->outputTapes = palloc0(nParticipants * sizeof(LogicalTape *));
state->nOutputTapes = nParticipants;
state->nOutputRuns = nParticipants;
for (j = 0; j < nParticipants; j++)
  state->outputTapes[j] = LogicalTapeImport(state->tapeset, j, &shared->tapes[j]);
state->status = TSS_BUILDRUNS;

프로세스 간 공유 상태는 tuplesort_estimate_shared, tuplesort_initialize_shared, tuplesort_attach_shared로 설정된다. Sharedsort 구조체는 SharedFileSet, 스핀락으로 보호되는 workersFinished 카운터, LogicalTapeImport가 소비하는 워커별 TapeShare 디스크립터를 담는다.

논리 테이프: 파일 하나, 재활용 블록 (logtape.c)

logtape.c는 2x 디스크 문제를 해결하기 위해 존재한다. 헤더에 계약이 명확히 명시 된다. 각 테이프 데이터셋(최종 출력 제외)은 정확히 한 번 쓰이고 한 번 읽히므로, 읽힌 블록은 다시 필요하지 않아 공간을 재활용할 수 있다. 모든 테이프가 하나의 BufFile에 들어간다. 각 테이프는 각 블록 끝의 트레일러로 연결된 BLCKSZ 블록 체인이다.

// TapeBlockTrailer macros — src/backend/utils/sort/logtape.c
#define TapeBlockPayloadSize  (BLCKSZ - sizeof(TapeBlockTrailer))
#define TapeBlockGetTrailer(buf) \
  ((TapeBlockTrailer *) ((char *) buf + TapeBlockPayloadSize))
#define TapeBlockIsLast(buf) (TapeBlockGetTrailer(buf)->next < 0)

재활용은 읽기 중에 발생한다. ltsReadBlock은 블록을 읽고, 테이프가 고정(frozen) 되어 있지 않으면 즉시 프리리스트로 반환한다.

// ltsReadFillBuffer (read+recycle) — src/backend/utils/sort/logtape.c
ltsReadBlock(lt->tapeSet, datablocknum, thisbuf);
if (!lt->frozen)
  ltsReleaseBlock(lt->tapeSet, datablocknum);
lt->curBlockNumber = lt->nextBlockNumber;
lt->nbytes += TapeBlockGetNBytes(thisbuf);

프리리스트는 블록 번호의 최솟값 힙이라 쓰기 시 항상 가장 낮은 프리 블록을 선호하며, 파일을 컴팩트하게 유지하고 쓰기를 최대한 순차적으로 만든다. ltsGetFreeBlock은 힙 루트를 꺼내고(비어 있으면 파일을 확장), ltsReleaseBlock은 해제된 블록을 다시 삽입한다.

// ltsGetFreeBlock — src/backend/utils/sort/logtape.c
/* freelist empty; allocate a new block */
if (lts->nFreeBlocks == 0)
  return lts->nBlocksAllocated++;
/* remove top of minheap */
blocknum = heap[0];
holeval = heap[--lts->nFreeBlocks];
/* sift down ... choose smaller child, stop when holeval <= both children */

읽기로 해제된 모든 블록이 병합 출력 런에 즉시 재사용 가능하므로, 파일 크기 피크가 실제 데이터 볼륨 근처에 머문다. 정렬 결과가 랜덤 접근을 지원해야 하는 경우(스크롤 가능 커서, mark/restore가 있는 병합 조인), 최종 테이프는 LogicalTapeFreeze로 고정된다. 마지막 부분 블록을 플러시하고, 단일 블록 읽기 버퍼로 전환하고, 재활용을 중단해 테이프를 다시 읽고 탐색할 수 있게 한다.

// LogicalTapeFreeze — src/backend/utils/sort/logtape.c
if (lt->dirty)
{
  TapeBlockSetNBytes(lt->buffer, lt->nbytes);
  ltsWriteBlock(lt->tapeSet, lt->curBlockNumber, lt->buffer);
}
lt->writing = false;
lt->frozen = true;
/* ... reset to single-BLCKSZ buffer, read first block, set up for seeks ... */

logtape.c는 HashAgg 케이스를 위해 enable_prealloc(테이프당 블록 사전 할당)도 지원한다. HashAgg에서는 많은 테이프가 동시에 쓰이며, 인터리브된 단일 블록 할당이 심하게 단편화되기 때문이다. TAPE_WRITE_PREALLOC_MIN/MAX가 두 배씩 늘어나는 사전 할당 윈도우를 바운드한다.

Tuplestore: 정렬 없는 형제 (tuplestore.c)

tuplestore.c는 “tuplesort.c의 단순화 버전으로, 튜플을 정렬하지 않고 시퀀스를 저장하고 그대로 돌려주기만 한다.” 핵심 추가 기능은 다중 독립 읽기 포인터다. Materialize 노드, 뒤로 스크롤하는 커서, 재귀 CTE 작업 테이블이 버퍼링된 시퀀스를 재읽을 수 있어야 하기 때문이다. 각 포인터는 자신만의 위치를 가진다.

// TSReadPointer — src/backend/utils/sort/tuplestore.c
typedef struct
{
  int      eflags;      /* capability flags */
  bool    eof_reached;  /* read has reached EOF */
  int      current;    /* next array index to read */
  int      file;      /* temp file# */
  off_t    offset;      /* byte offset in file */
} TSReadPointer;

tuplesort와 같은 세 가지 상태 형태이지만, 런도 없고 비교자도 없다.

// TupStoreStatus — src/backend/utils/sort/tuplestore.c
typedef enum
{
  TSS_INMEM,          /* Tuples still fit in memory */
  TSS_WRITEFILE,        /* Writing to temp file */
  TSS_READFILE,        /* Reading from temp file */
} TupStoreStatus;

tuplestore_puttuple_common은 TSS_INMEM 상태에서 memtuples[]에 쌓는다. LACKMEM이 발동되면 단일 BufFile을 만들고, 역방향 스캔 결정을 고정하고(길이 접두사 레코드로 저장하기 시작한 뒤 역방향 스캔 방식을 변경할 수 없다), 모든 것을 덤프하고 TSS_WRITEFILE로 진입한다.

// tuplestore_puttuple_common (TSS_INMEM spill) — src/backend/utils/sort/tuplestore.c
if (state->memtupcount < state->memtupsize && !LACKMEM(state))
  return;
/* Nope; time to switch to tape-based operation. */
PrepareTempTablespaces();
state->myfile = BufFileCreateTemp(state->interXact);
state->backward = (state->eflags & EXEC_FLAG_BACKWARD) != 0;
tuplestore_updatemax(state);
state->status = TSS_WRITEFILE;
dumptuples(state);

읽기는 활성 포인터의 위치로 단일 BufFile을 탐색해 TSS_WRITEFILE과 TSS_READFILE 사이를 전환한다. 파일 상단의 주석에 활성 포인터의 위치만 암묵적으로 파일의 탐색 위치이며, 비활성 포인터는 명시적인 file/offset을 가진다고 설명한다. tuplestore_trim은 모든 포인터의 되감기가 비활성화된 경우 가장 오래된 읽기 포인터 이전의 튜플을 버린다. 이것이 순방향으로만 읽는 Materialize가 메모리를 바운드되게 유지하는 방식이다. tuplesort와 달리 tuplestore는 logtape.c를 사용하지 않는다. 재활용할 런이 없으므로 단순한 BufFile로 충분하다.

포지션 힌트 (2026-06-05 기준, REL_18 273fe94)

심볼	파일	라인
TupSortStatus (enum)	tuplesort.c	154
SLAB_SLOT_SIZE / SlabSlot	tuplesort.c	142
MINORDER / MAXORDER / MERGE_BUFFER_SIZE	tuplesort.c	176
Tuplesortstate (struct)	tuplesort.c	185
SERIAL / WORKER / LEADER	tuplesort.c	403
tuplesort_begin_common	tuplesort.c	642
grow_memtuples	tuplesort.c	1052
tuplesort_puttuple_common	tuplesort.c	1169
consider_abort_common	tuplesort.c	1318
tuplesort_performsort	tuplesort.c	1363
tuplesort_gettuple_common	tuplesort.c	1470
tuplesort_merge_order	tuplesort.c	1778
inittapes	tuplesort.c	1865
selectnewtape	tuplesort.c	1948
init_slab_allocator	tuplesort.c	1981
mergeruns	tuplesort.c	2017
mergeonerun	tuplesort.c	2200
beginmerge	tuplesort.c	2260
dumptuples	tuplesort.c	2307
make_bounded_heap	tuplesort.c	2587
sort_bounded_heap	tuplesort.c	2636
tuplesort_sort_memtuples	tuplesort.c	2676
tuplesort_heap_insert	tuplesort.c	2738
tuplesort_heap_replace_top	tuplesort.c	2798
worker_nomergeruns	tuplesort.c	3047
leader_takeover_tapes	tuplesort.c	3068
ssup_datum_unsigned_cmp	tuplesort.c	3139
SortTuple (struct)	tuplesort.h	148
LogicalTape (struct)	logtape.c	137
LogicalTapeSet (struct)	logtape.c	187
TapeBlockGetTrailer (macro)	logtape.c	104
ltsGetFreeBlock	logtape.c	371
ltsReleaseBlock	logtape.c	469
LogicalTapeSetCreate	logtape.c	556
LogicalTapeImport	logtape.c	609
LogicalTapeWrite	logtape.c	761
LogicalTapeRewindForRead	logtape.c	846
LogicalTapeRead	logtape.c	928
LogicalTapeFreeze	logtape.c	981
TupStoreStatus (enum)	tuplestore.c	72
TSReadPointer (struct)	tuplestore.c	91
Tuplestorestate (struct)	tuplestore.c	103
tuplestore_begin_heap	tuplestore.c	330
tuplestore_alloc_read_pointer	tuplestore.c	395
tuplestore_puttuple_common	tuplestore.c	799
tuplestore_gettuple	tuplestore.c	955
dumptuples (tuplestore)	tuplestore.c	1258
tuplestore_trim	tuplestore.c	1424

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

검증된 사실

• 런 생성은 대체 선택이 아닌 퀵정렬. dumptuples에서 확인. 전체 memtuples 배열에 tuplesort_sort_memtuples(퀵정렬)를 호출하고 대상 테이프에 하나의 런으로 스트리밍한다. 빌드 단계에는 Knuth 5.4.1 대체 선택 힙이 없다. 힙(tuplesort_heap_*)은 mergeonerun/beginmerge의 병합에만 사용된다. AlphaSort 캐시 지역성 논거와 프로젝트의 2016년 대체 선택 제거 기록과 일치한다.

• 인메모리-vs-외부 결정은 LACKMEM 또는 배열 소진으로 키된 단방향 전환. tuplesort_puttuple_common의 TSS_INITIAL 분기에서 확인. memtupcount < memtupsize && !LACKMEM(state)인 동안은 메모리에 머문다. 그렇지 않으면 inittapes

  • dumptuples를 호출하고 state->status == TSS_BUILDRUNS로 전환하며 TSS_INITIAL로 절대 돌아오지 않는다.

• 병합 차수는 work_mem에서 계산되고 [6, 500]으로 클램핑. tuplesort_merge_order에서 확인. mOrder = allowedMem / (2 * TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE), 이후 Max(mOrder, MINORDER)와 Min(mOrder, MAXORDER) 적용. MINORDER = 6, MAXORDER = 500. 500 상한은 소스 주석에서 고차 병합의 CPU 캐시 효과로 정당화된다.

• 모든 논리 테이프는 하나의 임시 파일을 공유하고 블록은 최솟값 힙 프리리스트로 읽기 시 재활용. logtape.c 헤더 주석, ltsReadFillBuffer(ltsReadBlock 직후 frozen이 아니면 ltsReleaseBlock 호출), ltsGetFreeBlock / ltsReleaseBlock (다음 쓰기에 가장 낮은 프리 블록을 꺼내는 블록 번호 최솟값 힙)에서 확인. 이것이 피크 디스크 사용량을 약 1x로 바운드한다.

• 바운드 정렬은 스필하지 않는 고정 크기 반전 힙. TSS_INITIAL 바운드 전환 테스트 (memtupcount > bound * 2 || (... && LACKMEM)), make_bounded_heap(reversedirection 후 정확히 bound개 요소의 힙), TSS_BOUNDED 분기(단일 비교로 버리기-또는-교체)에서 확인. sort_bounded_heap이 performsort 시점에 제자리에서 힙 해제한다.

• 단축 키는 put 시점에 설치되며 런타임에 중단 가능. tuplesort_puttuple_common (datum1 채우기 위해 abbrev_converter 호출, 또는 중단 시 REMOVEABBREV)과 consider_abort_common(지수적으로 증가하는 abbrevNext 간격으로 샘플링하고 abbrev_abort 호출)에서 확인. mergeruns가 런을 다시 읽기 전에 abbrev_converter를 null로 만든다. 테이프 위 튜플에는 단축 키가 없기 때문이다.

• 타입 특화 퀵정렬은 비교자 함수 포인터를 우회. tuplesort_sort_memtuples에서 확인. sortKeys[0].comparator가 매칭되는 ssup_datum_*_cmp이면 qsort_tuple_unsigned/_signed/_int32로 디스패치하고, 그렇지 않으면 qsort_ssup(단일 키) 또는 제네릭 qsort_tuple로 디스패치한다.

• 병렬 정렬: 워커는 자신의 테이프에 정확히 하나의 런, 리더는 가져와 최종 병합. tuplesort_performsort(WORKER 분기: inittapes(false) + dumptuples(true) + worker_nomergeruns)와 leader_takeover_tapes(LogicalTapeImport로 nParticipants 워커 테이프 임포트, nOutputRuns = nParticipants, 상태 TSS_BUILDRUNS, 이후 mergeruns)에서 확인.

• Tuplestore는 정렬을 하지 않고 다중 읽기 포인터를 지원하며 단순 BufFile로 스필. tuplestore.c 헤더(“tuplesort.c의 단순화 버전, 정렬 없음”), TSReadPointer, tuplestore_alloc_read_pointer, tuplestore_puttuple_common(BufFileCreateTemp로 스필, LogicalTapeSet 사용 안 함)에서 확인. tuplestore_trim이 가장 오래된 읽기 포인터 이전 튜플을 회수한다.

미해결 질문

1. TSS_FINALMERGE(지연 즉석 병합)이 결과 테이프 구체화를 실제로 앞서는 시점은? mergeruns는 랜덤 접근이 필요하지 않고 <= maxTapes개의 런이 있을 때 병합 패스 하나를 짧게 멈춰 gettuple이 지연 병합하도록 한다. 전체 쓰기/읽기 패스 절약과 스캔 중 튜플당 힙 유지 비용 사이의 손익 분기점은 코드에서 특성화되지 않았다. 조사 경로: 다양한 런 수에서 TSS_FINALMERGE와 강제 최종 병합을 비교한다.

2. 단축이 실제로 얼마나 자주 중단되며, 낭비된 비용은? consider_abort_common은 포기할 때 REMOVEABBREV로 이미 저장된 datum1을 되돌린다. 구별 능력이 없는 (adversarial한) 선두 키에서 변환 후 되돌리는 비용, 그리고 두 배씩 증가하는 abbrevNext 스케줄이 이를 얼마나 빨리 잡아내는지는 워크로드 의존적이며 여기서 측정되지 않았다.

3. 최솟값 힙 프리리스트의 “가장 낮은 프리 블록” 쓰기 정책이 SSD에서도 중요한가? logtape.c 주석 자체가 LIFO-vs-최솟값 힙 선택을 불분명하다고 표시한다(“XXX perhaps a LIFO policy for free blocks would be better?”). 탐색 없는 스토리지에서는 순차성 논거가 약해지지만, 단편화/컴팩트성 논거는 남아 있다. 조사 경로: NVMe에서 두 정책 하의 임시 파일 크기와 쓰기 증폭을 측정한다.

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

• AlphaSort와 캐시 인식 런 생성. PostgreSQL이 대체 선택 대신 퀵정렬 런을 선택한 것은 AlphaSort 논제를 디스크 지향 엔진에 적용한 것이다. 캐시에 맞는 짧은 런과 추가 병합 패스가 힙이 캐시를 스래싱하는 긴 대체 선택 런을 이길 수 있다. 현대 하드웨어에서 런 수 대 병합 패스 트레이드오프 측정은 PostgreSQL이 입력 사전 정렬성에 전략을 적응시키지 않아 포기하는 것을 수치화할 것이다. 논문: Nyberg et al. 1994 (dbms-papers/alphasortsigmod.md).

• Patience sort / 런 감지. Chandramouli & Goldstein 2014(Patience is a Virtue, dbms-papers/patsort-sigmod14.md)은 입력의 자연 발생 오름차순 런을 감지해 병합한다. PostgreSQL의 고정 배치 퀵정렬 런이 완전히 무시하는 부분 사전 정렬성을 활용하는 방식이다. 거의 정렬된 입력(예: 추가 전용 시계열)에서 patience 스타일 런 감지기는 거의 선형에 수렴할 수 있다. PostgreSQL의 dumptuples와 대비하는 것은 구체적인 연구 프론티어다.

• CUBRID의 외부 정렬. CUBRID는 자체 테이프/런 모델과 임시 파일 재활용을 가진 외부 정렬이 있다. CUBRID의 런 병합과 mergeruns/logtape.c를 나란히 비교하면 PostgreSQL의 단일 파일 블록 재활용 최솟값 힙이 테이프당 파일 방식과 비교해 무엇을 얻는지 명확해질 것이다. (CUBRID 트리의 쿼리 실행 분석 참조.)

• 벡터화/SIMD 정렬. 현대 분석 엔진은 고정 폭 키를 분기 없는 SIMD 가속 네트워크 정렬과 래딕스 패스로 정렬한다. PostgreSQL의 특화되었지만 스칼라인 qsort_tuple_int32를 훨씬 뛰어넘는다. 단축 키는 “고정 폭 프록시로 정렬”을 향한 PostgreSQL의 중간 단계다. 완전한 정규화 키 래딕스 정렬이 미실현 확장이다.

• 스필 철학: tuplesort vs. tuplestore vs. HashAgg. 셋 다 임시 파일로 스필하지만 재활용자가 다르다. 정렬은 logtape 최솟값 힙, tuplestore는 단순 BufFile, HashAgg는 사전 할당 logtape를 쓴다. 세 스필 경로와 왜 갈라지는지에 대한 통합 설명은 임시 파일 서브시스템 전체를 명확히 할 것이다. (할당자 측은 postgres-memory-contexts.md, HashAgg 스필은 postgres-agg-sort-nodes.md 참조.)

출처

트리 내 소스 파일 (REL_18_STABLE, commit 273fe94)

• src/backend/utils/sort/tuplesort.c — 제네릭 정렬 엔진: 상태 기계, puttuple/performsort/gettuple, 런 생성(dumptuples), 테이프 설정(inittapes, tuplesort_merge_order, selectnewtape), 병합(mergeruns, mergeonerun, beginmerge), 병합 힙(tuplesort_heap_*), 바운드 정렬(make_bounded_heap, sort_bounded_heap), 단축(consider_abort_common), 병렬 글루 (worker_nomergeruns, leader_takeover_tapes).
• src/backend/utils/sort/tuplesortvariants.c — 타입별 begin/comparetup/ writetup/readtup 콜백(힙, datum, 인덱스 btree/hash, BRIN, GIN). 특화된 ssup_datum_* 비교자들이 여기서 연결된다.
• src/backend/utils/sort/logtape.c — 논리 테이프 셋: 하나의 BufFile, 트레일러가 있는 블록 체인, 최솟값 힙 프리리스트(ltsGetFreeBlock/ltsReleaseBlock), 읽기 시 재활용, LogicalTapeFreeze, 사전 할당.
• src/backend/utils/sort/tuplestore.c — 다중 읽기 포인터를 가진 정렬 없는 시퀀스 버퍼(TSReadPointer), 인메모리-후-BufFile 스필, tuplestore_trim.
• src/backend/utils/sort/sharedtuplestore.c — 병렬 인식 공유 튜플 스토어(병렬 해시 조인). 대조를 위해 언급, 범위 밖.
• src/backend/utils/sort/sortsupport.c — SortSupport 설정, 단축 연결.
• src/include/utils/tuplesort.h — SortTuple, TuplesortPublic, 공개 API와 병렬 정렬용 SortCoordinate/Sharedsort.

논문 및 교과서 챕터

• Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching. 소스 주석은 Algorithm 5.2.3H(병합 힙)와 PostgreSQL이 런 생성에 의도적으로 더 이상 사용하지 않는 대체 선택 자료(5.4.1)를 인용한다.
• Nyberg, Barclay, Cvetanovic, Gray, Lomet (1994). “AlphaSort: A Cache-Sensitive Parallel External Sort.” SIGMOD. 대체 선택 대비 퀵정렬 런의 캐시 지역성 논거 (knowledge/research/dbms-papers/alphasortsigmod.md).
• Chandramouli & Goldstein (2014). “Patience is a Virtue: Revisiting Merge and Sort on Modern Processors.” SIGMOD. 런 감지와 patience sort (knowledge/research/dbms-papers/patsort-sigmod14.md).
• Database System Concepts (Silberschatz, Korth, Sudarshan, 7판), 15장 “Query Processing” — 외부 정렬-병합 알고리즘, 런 생성, 병합 패스 비용 모델 (knowledge/research/dbms-general/).
• Database Internals (Petrov 2019), 7장 — 외부 정렬, 런 병합, 임시 파일 관리 프레이밍.

형제 문서 (교차 참조 — 메커니즘은 해당 문서 소유, 여기서 중복하지 않음)

• postgres-agg-sort-nodes.md — tuplesort와 tuplestore를 구동하는 Sort, IncrementalSort, Agg/HashAgg 플랜 노드. HashAgg의 자체 스필 경로는 logtape.c 사전 할당을 사용한다.
• postgres-executor.md — tuplestore를 인스턴스화하는 실행기 스캐폴딩(Materialize, 커서, 재귀 CTE 작업 테이블).
• postgres-memory-contexts.md — work_mem 버짓, tuplesort가 튜플 메모리에 사용하는 슬랩/범프 할당자, MemoryContextReset.
• postgres-parallel-query.md — tuplesort_initialize_shared / SharedFileSet 아래의 병렬 워커/DSM 기계.
• postgres-nbtree.md — CREATE INDEX가 힙의 tuplesort로 B-트리를 벌크 로드한다 (tuplesort_begin_index_btree).