(KO) CUBRID External Sort — 런 생성, 다중 병합, 그리고 정렬 기반 substrate
목차
학술적 배경
섹션 제목: “학술적 배경”외부 정렬(external sort)은 입력이 RAM에 들어가지 않을 때 데이터베이스 엔진이 하는 일이다. Knuth 의 The Art of Computer Programming 3권 (Sorting and Searching) 후반부 절반이 통째로 이 문제에 할애되어 있다. Graefe 의 두 서베이 — Query Evaluation Techniques (ACM CSUR, 1993) 와 Implementing Sorting in Database Systems (ACM CSUR, 2006) — 가 Knuth 를 관계형 시스템의 엔지니어링 어휘로 옮겨 준다. Petrov 의 Database Internals (2019) 14장이 같은 모델을 짧게 요약한다. 공통된 모델은 두 단계로 되어 있다.
1단계 — 런 생성 (run generation). 입력을 메모리 정렬 버퍼가 가득 찰 때까지 읽고, 그 청크를 정렬해 임시 파일에 런(run) 하나로 적는다. 입력이 끝날 때까지 반복한다. 단순함과 런 길이 사이의 절충이 존재한다.
- 크기 M 짜리 버퍼 위에서의 quicksort / mergesort 는 길이 M 짜리 런을 만든다. 런 개수는 대략 N/M 이다.
- Replacement selection (Knuth §5.4.1, Algorithm R) 은 크기 M 짜리 힙을 유지하며 마지막에 출력한 키 이상인 최소값을 내보낸다. 새 입력이 마지막 출력보다 크거나 같으면 현재 런을 계속 잇고, 작으면 다음 런용으로 잡아 둔다. 무작위 입력에서는 기댓값 길이가 2M 인 런이 나오고, 부분 정렬 입력에서는 런 하나 로 입력 전체가 흡수되는 일도 있다. 교과서적인 절충은 이렇다 — replacement selection 이 필요한 병합 fan-in 을 절반으로 줄여 주지만, 일회성 quicksort 대신 레코드마다 힙 갱신 비용을 낸다.
Postgres 가 v15 이전까지, 그리고 몇몇 연구 엔진이 쓰는 현대적
변종은 run-detection 이 붙은 natural mergesort 다 — 입력을
훑으며 이미 단조로운 구간을 찾아내 그 자체를 기존 런으로 취급
하고, 경계 부분만 정렬한다는 점이다. 출력 런 길이는 최소 M
(버퍼 한 번 분량) 이고 near-sorted 입력에서는 훨씬 길어진다.
CUBRID 의 런 생성기가 이 계열에 속한다 (Knuth 의 “natural
mergesort” 에 내림차순 구간을 즉석에서 뒤집는 reverse-flip 을
얹은 형태다. 아래 sort_run_find 와 sort_run_sort 참조).
2단계 — 다중 병합 (multi-way merge). 길이 L 의 런 R 개가 주어졌을 때, 이를 정렬된 출력 하나로 합친다. fan-in k 는 가용 버퍼 개수에 묶인다 — 입력 런마다 read 버퍼 하나, write 버퍼 하나. k-way 병합의 패스 횟수는 ⌈log_k(R)⌉ 이며, 총 I/O 는 대략 2N·⌈log_k(R)⌉ 페이지 (패스마다 read+write) 다. 각 병합 단계 에서 쓰는 자료구조는 다음과 같다.
- 힙 (winner tree / loser tree). k 개 입력 런의 head 가 잎이 되는 균형 이진 트리다. root 가 모든 런 통틀어 현재 최소 값이다. 한 번 emit 할 때마다 승자의 잎을 그 런의 다음 원소로 바꾸고 root 까지 sift 한다 — 원소당 O(log k). Knuth 알고리즘 5.4.2D 다.
- 정렬된 연결 리스트. k 가 작을 때 (대략 8 이하), 런 포인터 의 단순 insertion-sort 단방향 연결 리스트가 힙보다 빠르다. 캐시 footprint 가 캐시 라인 한 줄 분량이고, 가장 흔한 경우 (이번 승자가 직전 승자와 같은 런) 가 O(1) 이기 때문이다.
- Polyphase merge (Knuth §5.4.2, Gilstad 1960) — 임시 테이프
/파일 개수가 적고 고정되어 있을 때, 런들을 Fibonacci 풍 분포로
파일에 흩어 두어, 어느 한 파일이 병목 런을 혼자 들고 있지
않게 한다. CUBRID 은 polyphase 를 쓰지 않는다. 입력 4개 +
출력 4개 = 총 8개의 임시 파일로 묶어 둔 균형 병합 (
SORT_MAX_HALF_FILES = 4) 을 쓴다.
정렬 도중의 중복 제거. 같은 키가 여러 번 나타날 때 — DISTINCT
나 unique 인덱스 로딩처럼 — 중복은 마지막 출력 시점이 아니라
모든 병합 단계에서 제거할 수 있다. 그렇게 하면 중간 런이 작아져
이후 패스의 I/O 도 줄어든다. 비용은 어차피 ordering 을 위해
하던 비교 검사 한 번이다. CUBRID 은 이를 SORT_DUP_OPTION enum
({ SORT_DUP, SORT_ELIM_DUP }) 으로 노출하고, 중복 제거 경로
에서는 sort_exphase_merge_elim_dup 라는 별도 병합 루프로 디스
패치한다.
I/O 비용 모델. 정렬 버퍼 크기 M (페이지 단위), 총 입력 N
페이지, 병합 fan-in k = M − 1 (입력 런마다 버퍼 하나 + write
버퍼 하나) 이라 할 때, 패스 횟수는 ⌈log_k(N/M)⌉ + 1 이다 (런
생성에 1, 병합에 나머지). 총 I/O 는 대략 2N·passes 다. 모델이
말해 주는 바는 분명하다 — M 을 키우는 것은 곱셈으로 효과가
커지고 (런 수 감소, fan-in 증가, 패스 수 감소), k 를 키우는 것은
로그로만 효과가 커진다. 실제 엔진들이 M 을 sysparam (work_mem,
sort_buffer_size, sr_nbuffers) 으로 노출하는 이유가 바로 그
곱셈 효과 때문이다 — 워크로드별로 튜닝할 가치가 있다.
DBMS 공통 설계 패턴
섹션 제목: “DBMS 공통 설계 패턴”엔진들은 다섯 축을 따라 갈라진다. (1) 런 생성 알고리즘 (quicksort vs. replacement-selection vs. natural mergesort), (2) 병합 트리 자료구조 (힙 vs. 정렬 리스트 vs. tree of losers), (3) 메모리 모델 (고정 버퍼 vs. spill 가능한 해시), (4) 병렬성 (단일 스레드 vs. 분할 워커 풀), (5) B+Tree 벌크 로드와 다른 엔진 내부 정렬 사용처와의 통합.
PostgreSQL — tuplesort.c
섹션 제목: “PostgreSQL — tuplesort.c”PostgreSQL 의 외부 정렬은 src/backend/utils/sort/tuplesort.c
에 있다. v15 이전까지는 Knuth 의 알고리즘 5.4.2D — replacement
selection 을 곁들인 polyphase merge 를 썼다. 런 생성은
work_mem 만큼의 튜플로 이진 힙을 유지해 HeapTuple 키 순서로
emit 했고, 런들은 물리 임시 파일을 공유하는 logical tape
(logtape.c) 에 쓰였다. 병합 fan-in 은 maintenance_work_mem /
max_files_per_process 로 묶였다. v15 에서 런 생성기는 quicksort-
and-spill 으로 바뀌었고 (여전히 tuplesort.c 내부), 병합 단계는
지금도 힙을 쓴다. 클라이언트 인터페이스 (tuplesort_begin_heap,
tuplesort_putdatum, tuplesort_performsort,
tuplesort_getdatum) 는 명시적인 begin / put / sort / get / end
단계를 가진 상태 기계이지, get/put 콜백 한 쌍이 아니라는 점이
구별된다.
MySQL — filesort
섹션 제목: “MySQL — filesort”MySQL InnoDB 의 filesort (sql/filesort.cc) 는 quicksort 기반
런 생성기를 쓰며 (replacement selection 없음), 짧은 고정폭 키
에서는 옵션으로 radix sort 를 쓴다. 병합은 힙 기반 k-way 다.
k 는 sort_buffer_size 로 묶인다. filesort 에는 결과가
sort_buffer_size 안에 들어가면 임시 파일을 아예 만들지 않는
in-memory only 빠른 경로가 따로 있어, 디스크 경로는 overflow
시에만 작동한다.
SQL Server / Oracle
섹션 제목: “SQL Server / Oracle”SQL Server 의 sort iterator 는 블랙박스지만, 옵티마이저가 큰
입력을 추정하면 워커 스레드 사이에서 exchange and merge 풍
병렬 정렬을 수행한다고 문서가 설명한다. Oracle 은 Automatic
Memory Management (pga_aggregate_target) 로 관리되는 워크에어
리어를 쓰며, sort 가 quota 를 넘으면 TEMPFILE 로 spill 한다.
이론 ↔ CUBRID 명칭 매핑
섹션 제목: “이론 ↔ CUBRID 명칭 매핑”위의 다섯 축을 CUBRID 심볼에 사상하면 다음과 같다.
| 이론적 개념 | CUBRID 명칭 |
|---|---|
| 최상위 sort 진입점 | sort_listfile (external_sort.c) |
| 호출별 sort 상태 | SORT_PARAM (external_sort.c:134) |
| 정렬 버퍼 (M 페이지) | SORT_PARAM::internal_memory, PRM_ID_SR_NBUFFERS 가 결정 |
| 런 생성 단계 (1단계) | sort_inphase_sort |
| 메모리 내 정렬 알고리즘 | sort_run_sort → sort_run_find + sort_run_merge (natural mergesort) |
| 런 탐지 (Knuth natural mergesort) | sort_run_find (오름/내림 구간 탐지 + flip) |
| 런 flush | sort_run_flush 가 정렬된 in-memory 런을 슬롯 페이지로 FILE_TEMP 에 적음 |
| 병합 단계 (2단계) | sort_exphase_merge / sort_exphase_merge_elim_dup |
| 병합 토너먼트 자료구조 | SORT_REC_LIST sr_list[SORT_MAX_HALF_FILES] — 정렬된 연결 리스트 (k ≤ 4) |
| 병합 fan-in 상한 | SORT_MAX_HALF_FILES = 4 (총 8개 임시 파일 = 입력 4 + 출력 4) |
| 병합별 버퍼 분할 | sort_find_inbuf_size — 출력에 절반, 나머지를 입력들이 나눠 가짐 |
| 백엔드 임시 파일 | FILE_TEMP 할당 — file_create_temp / sort_add_new_file |
| 긴 레코드 (다중 페이지) overflow | sort_param->multipage_file + overflow_insert / sort_retrieve_longrec |
| 병합 도중 중복 제거 | sort_exphase_merge_elim_dup, SORT_DUP_OPTION::SORT_ELIM_DUP 로 게이트 |
| 비교자 디스패치 | SORT_CMP_FUNC 콜백 (호출자 제공) |
| 입출력 sandwich | SORT_GET_FUNC / SORT_PUT_FUNC 콜백 |
| 병렬 라우팅용 호출자 태그 | SORT_PARALLEL_TYPE enum (external_sort.h:59) |
| 병렬 sort 코디네이터 | sort_start_parallelism / sort_end_parallelism |
| 병렬 병합 트리 fan-in | SORT_PX_MERGE_FILES (N 개 병렬 결과의 다단계 병합) |
| ORDER BY 호출자 | qfile_sort_list → qfile_sort_list_with_func → sort_listfile |
| sort 기반 GROUP BY 호출자 | qexec_groupby → sort_listfile (qexec_gby_put_next 와 함께) |
| 해시-spill GROUP BY 호출자 | qexec_groupby → sort_listfile (qexec_hash_gby_put_next 와 함께) |
| B+Tree 벌크 로드 호출자 | btree_index_sort → sort_listfile (btree_construct_leafs 와 함께) |
| 병렬 인덱스 leaf 빌드 | SORT_INDEX_LEAF 병렬 타입, btree_sort_get_next_parallel |
CUBRID의 구현
섹션 제목: “CUBRID의 구현”CUBRID 의 외부 정렬은 단일 C 파일이다 — src/storage/external_sort.c,
약 5,850 줄. 공개 심볼은 정확히 두 개 — 진입점인 sort_listfile
과 병렬 B+Tree 입력 어댑터인 btree_sort_get_next_parallel.
나머지는 모두 static 이다. 파일은 다섯 겹의 동심원으로 짜여
있다. (a) 임시 파일 페이지를 위한 슬롯 페이지 프리미티브, (b)
in-memory 런 탐지/병합 프리미티브, (c) 런 생성 단계
(sort_inphase_sort), (d) 병합 단계 (sort_exphase_merge 와
중복 제거 쌍둥이), (e) SORT_PARALLEL_TYPE 워커 위에서 c 와 d
를 감싸는 병렬 코디네이션 계층.
최상위 흐름 — sort_listfile
섹션 제목: “최상위 흐름 — sort_listfile”sort_listfile 은 모든 호출자가 작성하는 계약이다. external_sort.h
에 선언된 시그니처는 다음과 같다.
// sort_listfile — src/storage/external_sort.hextern int sort_listfile (THREAD_ENTRY *thread_p, INT16 volid, int est_inp_pg_cnt, SORT_GET_FUNC *get_fn, void *get_arg, SORT_PUT_FUNC *put_fn, void *put_arg, SORT_CMP_FUNC *cmp_fn, void *cmp_arg, SORT_DUP_OPTION option, int limit, bool includes_tde_class, SORT_PARALLEL_TYPE sort_parallel_type);호출자는 함수 포인터 셋을 넘긴다 — get_fn 은 다음 입력 레코드
를 가져오고, put_fn 은 정렬된 레코드가 나오는 대로 받으며,
cmp_fn 이 순서를 정의한다. 그리고 콜백에 그대로 되돌려질 불투
명한 인자 포인터 세 개를 함께 넘긴다. 호출자의 데이터 모델이
무엇이든 (ORDER BY 의 list-file 튜플, B+Tree 로드의 heap-record
OID, GROUP BY 의 해시-spill 엔트리) external_sort.c 안에서는
보이지 않는다 — 모듈 내부에서 모든 레코드는 그저 RECDES { data, length, type } 와 불투명 비교자로만 보인다.
최상위 본체는 단순하다.
// sort_listfile — src/storage/external_sort.c (condensed)intsort_listfile (THREAD_ENTRY *thread_p, INT16 volid, int est_inp_pg_cnt, SORT_GET_FUNC *get_fn, void *get_arg, SORT_PUT_FUNC *put_fn, void *put_arg, SORT_CMP_FUNC *cmp_fn, void *cmp_arg, SORT_DUP_OPTION option, int limit, bool includes_tde_class, SORT_PARALLEL_TYPE parallel_type){ SORT_PARAM ori_sort_param; SORT_PARAM *sort_param = &ori_sort_param; // ... condensed: install callbacks, init temp file slots ...
if (est_inp_pg_cnt > 0) input_pages = est_inp_pg_cnt + MAX ((int)(est_inp_pg_cnt * 0.1), 2); else input_pages = prm_get_integer_value (PRM_ID_SR_NBUFFERS);
sort_param->tot_buffers = MIN (prm_get_integer_value (PRM_ID_SR_NBUFFERS), input_pages); sort_param->tot_buffers = MAX (4, sort_param->tot_buffers);
sort_param->internal_memory = (char *) malloc ((size_t) sort_param->tot_buffers * (size_t) DB_PAGESIZE); // ... condensed: fall back to 4-page minimum on OOM ...
sort_param->half_files = sort_get_num_half_tmpfiles (sort_param->tot_buffers, input_pages); sort_param->tot_tempfiles = sort_param->half_files << 1; sort_param->in_half = 0;
// ... condensed: per-file dynamic arrays for run-list bookkeeping ...
#if defined(SERVER_MODE) sort_param->px_parallel_num = sort_check_parallelism (thread_p, sort_param); if (sort_param->px_parallel_num <= 1) error = sort_listfile_internal (thread_p, sort_param); /* serial path */ else { /* parallel */ px_sort_param = malloc (sizeof (SORT_PARAM) * sort_param->px_parallel_num); error = sort_start_parallelism (thread_p, px_sort_param, sort_param); SORT_EXECUTE_PARALLEL (sort_param->px_parallel_num, px_sort_param, sort_listfile_execute); SORT_WAIT_PARALLEL (sort_param->px_parallel_num, sort_param, px_sort_param); error = sort_end_parallelism (thread_p, px_sort_param, sort_param); }#else error = sort_listfile_internal (thread_p, sort_param);#endif
// ... condensed: return all temp resources, free internal memory ... return error;}세 가지를 짚어 둘 만하다. 첫째, 페이지 단위의 정렬 버퍼 크기는
tot_buffers 이며 min (PRM_ID_SR_NBUFFERS, input_pages_with_10pct_slack)
로 계산되고, 4 페이지 아래로 떨어지지 않도록 floor 가 걸려 있다.
DBA 가 만질 수 있는 손잡이는 sysparam sr_nbuffers (별칭
sort_buffer_size) 하나뿐이다. 호출자의 est_inp_pg_cnt 는
입력이 작다고 알려져 있을 때 버퍼를 줄이는 방향 으로만 작동
한다. 둘째, half_files (병합 fan-in) 는 예상 런 수에서 계산
되어, 작은 정렬이 단지 한두 개의 런을 만들기 위해 임시 파일
8개를 잡는 일이 없도록 한다 (sort_get_num_half_tmpfiles 참조).
셋째, 병렬 경로는 런타임 검사 (sort_check_parallelism) 로
게이트되어 있다는 점이다 — 옵티마이저가 병렬 정렬을 결정하지
않고, 실행자가 결정한다.
sort_listfile_internal — 두 단계 드라이버
섹션 제목: “sort_listfile_internal — 두 단계 드라이버”병렬 결정이 no 이거나, 각 병렬 워커 안쪽에서, 제어는
sort_listfile_internal 로 넘어온다.
// sort_listfile_internal — src/storage/external_sort.cintsort_listfile_internal (THREAD_ENTRY *thread_p, SORT_PARAM *sort_param){ int error = NO_ERROR; int file_pg_cnt_est;
/* Phase 1: run generation */ error = sort_inphase_sort (thread_p, sort_param, sort_param->get_fn, sort_param->get_arg, &sort_param->total_numrecs); if (error != NO_ERROR) return error;
if (sort_param->tot_runs > 1) { /* Allocate the output half of the temp-file pair. * The input half was allocated lazily inside Phase 1. */ file_pg_cnt_est = sort_get_avg_numpages_of_nonempty_tmpfile (sort_param); file_pg_cnt_est = MAX (1, file_pg_cnt_est); for (i = sort_param->half_files; i < sort_param->tot_tempfiles; i++) { error = sort_add_new_file (thread_p, &(sort_param->temp[i]), file_pg_cnt_est, true, sort_param->tde_encrypted); if (error != NO_ERROR) return error; }
/* Phase 2: merge. Two variants depending on dedup option. */ if (sort_param->option == SORT_ELIM_DUP) error = sort_exphase_merge_elim_dup (thread_p, sort_param); else error = sort_exphase_merge (thread_p, sort_param); } return error;}구조는 빡빡하다. 1단계는 항상 돈다. 2단계는 런이 둘 이상 만들어 졌을 때만 돈다. 중복 제거 분기는 2단계 진입 시 한 번 정해지고 그 후로는 다시 보지 않는다. 두 단계 사이의 스트리밍 hand-off 는 없다 — 2단계가 1단계가 적어 둔 런들 을 읽기 때문에, 1단계가 완전히 끝난 뒤에야 2단계가 시작된다는 점이다.
flowchart TB
subgraph CALLER["호출자"]
GET["get_fn / get_arg<br/>(scan, hash spill, heap iter)"]
PUT["put_fn / put_arg<br/>(list-file 작성기, leaf 빌더)"]
CMP["cmp_fn / cmp_arg<br/>(SORTKEY_INFO, collation, NULLS, ASC/DESC)"]
end
subgraph PHASE1["1단계 — 런 생성"]
SIS["sort_inphase_sort"]
SRS["sort_run_sort<br/>(버퍼 위에서 natural mergesort)"]
SRF["sort_run_flush<br/>(런을 슬롯 페이지로 적음)"]
end
subgraph PHASE2["2단계 — 병합"]
SEM["sort_exphase_merge<br/>또는 sort_exphase_merge_elim_dup"]
TRN["k-way 병합 토너먼트<br/>(SORT_REC_LIST sr_list)"]
end
subgraph TEMP["FILE_TEMP 백엔드"]
H1["temp[0..half_files-1]<br/>(입력 절반)"]
H2["temp[half_files..tot]<br/>(출력 절반)"]
OVF["multipage_file<br/>(긴 레코드 overflow)"]
end
subgraph OUT["출력"]
PS["정렬된 순서대로<br/>레코드별 put_fn 호출"]
end
GET --> SIS
CMP -.-> SRS
CMP -.-> TRN
SIS --> SRS --> SRF --> H1
SIS -.long record.-> OVF
H1 --> SEM
SEM --> TRN --> H2
H2 -.다음 패스에서 절반 swap.-> H1
SEM -- final pass --> PS --> PUT
이 그림이 짚어 주는 구조적 포인트가 있다. 런 생성은 임시 파일
풀의 입력 절반 에 쓴다. 병합 단계는 입력 절반에서 읽고 출력
절반에 쓴다. 한 패스가 끝날 때마다 두 절반이 자리를 바꾼다
(sort_param->in_half ^= half_files). 마지막 패스는 임시 파일
로 되돌아 쓰지 않는다 — 곧장 put_fn 으로 레코드를 흘려
보낸다 (sort_exphase_merge 의 very_last_run 분기 참조).
1단계 — sort_inphase_sort 안의 런 생성
섹션 제목: “1단계 — sort_inphase_sort 안의 런 생성”sort_inphase_sort 는 채우고-정렬하고-flush 하는 루프다. 버퍼를
두 절반으로 쪼갠 채로 유지한다 — 레코드 영역은 internal_memory
시작에서부터 앞으로 자라고, 인덱스 영역은 output_buffer 에서
거꾸로 자란다. 레코드는 레코드 영역에 쌓이며, 그와 평행하게
포인터 배열 (인덱스 영역) 이 만들어진다. 두 영역이 만나면 버퍼
가 꽉 찬 것이고, 포인터 배열이 정렬된다.
// sort_inphase_sort — src/storage/external_sort.c (condensed shape)static intsort_inphase_sort (THREAD_ENTRY *thread_p, SORT_PARAM *sort_param, SORT_GET_FUNC *get_fn, void *get_arg, unsigned int *total_numrecs){ RECDES temp_recdes; char *item_ptr; /* head of free space in the record area */ char **index_area; /* index-area pointer cursor (grows down) */ char **index_buff; /* boundary used to detect "full" */ long numrecs = 0, sort_numrecs = 0; int out_curfile = sort_param->in_half;
output_buffer = sort_param->internal_memory + ((long)(sort_param->tot_buffers - 1) * DB_PAGESIZE); item_ptr = sort_param->internal_memory + SORT_RECORD_LENGTH_SIZE; index_area = (char **)(output_buffer - sizeof (char *)); index_buff = index_area - 1;
for (;;) { if ((char *)index_buff < item_ptr) status = SORT_REC_DOESNT_FIT; /* buffer full */ else { temp_recdes.data = item_ptr; temp_recdes.area_size = ...; /* remaining contiguous */ status = (*get_fn) (thread_p, &temp_recdes, get_arg); if (status == SORT_NOMORE_RECS) break; }
switch (status) { case SORT_REC_DOESNT_FIT: /* Sort what we have, flush it as a run, reset cursors. */ if (numrecs > 0) { index_area = sort_run_sort (thread_p, sort_param, index_area + 1, numrecs, sort_numrecs, index_buff, &numrecs); if (sort_param->option == SORT_ELIM_DUP && /* still room and dedup shrunk us */ ...) { /* keep filling the same run */ ... } else { error = sort_run_flush (thread_p, sort_param, out_curfile, cur_page, output_buffer, index_area, numrecs, REC_HOME); numrecs = 0; item_ptr = sort_param->internal_memory + SORT_RECORD_LENGTH_SIZE; index_area = (char **)(output_buffer - sizeof (char *)); index_buff = index_area - 1; if (++out_curfile >= sort_param->half_files) out_curfile = sort_param->in_half; /* round-robin */ } sort_numrecs = numrecs; } /* Long-record path: temp_recdes.length > SORT_MAXREC_LENGTH */ if (temp_recdes.length > SORT_MAXREC_LENGTH) { /* Re-fetch the full record into long_recdes. * Push it into sort_param->multipage_file via overflow_insert. * The in-buffer entry stores only the VPID pointer. */ ... error = sort_run_flush (..., REC_BIGONE); ... } break;
case SORT_SUCCESS: SORT_RECORD_LENGTH (item_ptr) = temp_recdes.length; *index_area = item_ptr; numrecs++; index_area--; index_buff -= 2; /* one slot for the pointer, one for slack */ item_ptr += DB_ALIGN (temp_recdes.length, MAX_ALIGNMENT) + SORT_RECORD_LENGTH_SIZE; break; } }
/* Drain whatever is left in the buffer at end of input. */ if (numrecs > 0) { index_area = sort_run_sort (..., &numrecs); if (sort_param->tot_runs > 0 || SORT_IS_PARALLEL (sort_param)) sort_run_flush (..., REC_HOME); /* one more run */ else for (i = 0; i < numrecs; i++) /* short-circuit */ (*sort_param->put_fn) (thread_p, &temp_recdes, sort_param->put_arg); } ...}이름을 붙여 둘 만한 설계 결정이 몇 개 있다.
라운드 로빈 런 분배. 연달아 만들어지는 런들이 입력 절반의
임시 파일들을 차례로 돈다 (out_curfile). half_files = 4
이고 런이 13개라면, 배치는 다음과 같이 된다 — temp[0]: runs 0,4,8,12; temp[1]: runs 1,5,9; temp[2]: runs 2,6,10; temp[3]: runs 3,7,11. 이렇게 하면 런 개수와 무관하게 병합 fan-in 이
균형 잡힌다. Knuth 가 테이프 드라이브용으로 묘사하는 polyphase
분배를 우회한다는 점이다.
중복 제거 시 런 연장 분기. SORT_ELIM_DUP 가 켜져 있으면,
버퍼를 정렬한 결과가 (중복이 합쳐져) 작아지는 일이 흔하다. 정렬
후 꼬리에 여전히 더 받을 자리가 남으면, sort_inphase_sort 는
flush 하지 않고 커서를 재배치해 같은 런을 계속 채운다. 그래서
중복이 많은 입력 — 예를 들어 같은 키를 여러 heap row 가 공유하는
unique 인덱스 로딩 — 에서 실제 런 길이가 (버퍼 한 개 분량보다)
가변적으로, 종종 더 길게 나오는 이유가 이것이다.
긴 레코드 overflow. 한 튜플이 `SORT_MAXREC_LENGTH = DB_PAGESIZE
- sizeof(SLOTTED_PAGE_HEADER) - sizeof(SLOT)
— 대략 슬롯 오버 헤드를 뺀 페이지 한 장 — 을 넘으면 in-line 으로 저장할 수 없다. 이 경우 레코드를 힙 할당된long_recdes로 다시 가져와서, 사이드 카(side-car) overflow 파일 (sort_param->multipage_file,file_create_temp로 첫 사용 시점에 lazy 하게 생성) 에 적고, 버퍼 내 엔트리는rec_type = REC_BIGONE이 붙은 단일 VPID 포인터 가 된다. 병합 단계가REC_BIGONE엔트리를 보면sort_retrieve_longrec(내부에서overflow_get` 을 호출) 으로 실제 레코드를 비교 및 emit 직전에 materialise 한다. 긴 레코드 런들은 개별로 flush 된다 — 항상 그 런의 마지막이자 유일한 레코드 다.
런 단일 short-circuit. 루프가 끝났는데 tot_runs == 0 이면,
입력 전체가 버퍼에 들어갔다는 뜻이다. 이를 임시 파일에 적어 두었
다가 다시 읽어 올 이유가 없다 — 코드는 정렬된 인덱스 영역을 그냥
순회하며 put_fn 을 직접 호출한다. 그 다음 sort_listfile_internal
이 tot_runs <= 1 을 보고 2단계를 통째로 건너뛴다.
sort_run_sort — natural mergesort 엔진
섹션 제목: “sort_run_sort — natural mergesort 엔진”sort_run_sort 는 메모리 내 포인터 배열에 실제 순서를 세우는
일을 한다. quicksort 가 아니라 Knuth 의 natural mergesort 다 —
sort_run_find 로 단조 구간을 찾고 (내림차순이면 flip), SORT_STACK
에 push 한 뒤, sort_run_merge 로 인접한 같은-깊이 런들을 합친다.
// sort_run_sort — src/storage/external_sort.c (condensed)static char **sort_run_sort (THREAD_ENTRY *thread_p, SORT_PARAM *sort_param, char **base, long limit, long sort_numrecs, char **otherbase, long *srun_limit){ // ... limit accounting elided ... st_p->top = -1; cnt = (int) (log10 (ceil ((double) limit / 2.0)) / log10 (2.0)) + 2; st_p->srun = db_private_alloc (NULL, cnt * sizeof (SRUN));
do { sort_run_find (src, &src_top, st_p, limit, compare, comp_arg, option); if (src_top < limit) sort_run_find (src, &src_top, st_p, limit, compare, comp_arg, option);
while (st_p->top >= 1 && ((src_top >= limit) /* final */ || (st_p->srun[st_p->top - 1].tree_depth == st_p->srun[st_p->top].tree_depth))) /* equal */ sort_run_merge (dest, src, st_p, compare, comp_arg, option); } while (src_top < limit);
// ... merge with previously-found run if any ...}natural mergesort 가 O(N log N) 으로 묶이는 이유는 “같은-깊이
런만 병합한다” 는 규칙 때문이다 — 병합할 때마다 깊이가 1 늘어
나므로 스택 높이가 ⌈log₂ N⌉ 을 넘지 않는다. SRUN 구조체는
low_high ∈ {'L', 'H'} 를 들고 다니며, 현재 런이 low (base)
버퍼에 있는지 high (otherbase) 버퍼에 있는지를 추적한다 —
sort_run_merge 가 두 버퍼 사이를 ping-pong 하므로 매 병합이
대상 버퍼를 갈아 가며 세 번째 버퍼를 추가로 잡지 않는다는 점
이다.
sort_run_find 는 런 탐지기다. 다음 두 슬롯을 읽어 런이 오름인
지 내림인지 결정하고, 추세가 유지되는 동안 늘려 가며, 내림이면
flip 하고, *top 을 그 런 뒤로 옮기고, descriptor 를 스택에 push
한다. 이미 정렬된 입력에서는 길이 N 의 런 하나만 만들어지고
병합 스택이 한 칸짜리가 된다 — 즉 degenerate sort 비용이 O(N)
이다.
중복 제거 옵션은 sort_run_find 안에 SORT_CHECK_DUPLICATE(stop, next_stop) 매크로로 접혀 들어 있다. 두 인접 원소가 SORT_DUP
모드에서 같다고 비교되면 중복이 생존자의 체인에 매달려서 put-
콜백이 그 리스트를 walk 할 수 있게 된다. SORT_ELIM_DUP 모드
에서는 중복의 슬롯이 NULL 로 표시되어 run-find 끝의 right-shift
compaction 단계에서 빠져 나간다. 어느 쪽이든 병합 단계는 중복이
없는 입력을 본다.
2단계 — sort_exphase_merge
섹션 제목: “2단계 — sort_exphase_merge”병합 단계는 병합 패스의 루프다. 각 패스가 입력 절반에서
act_infiles 개의 런을 읽어 합치고, 결과를 출력 절반에 쓴다.
패스가 끝나면 두 절반이 자리를 바꾼다. 모든 입력 파일을 통틀어
활성 런이 단 하나만 남으면 루프가 종료된다 — 그 시점에 그 런이
put_fn 으로 흘러 나간다.
// sort_exphase_merge — src/storage/external_sort.c (skeletal)static intsort_exphase_merge (THREAD_ENTRY *thread_p, SORT_PARAM *sort_param){ while ((act_infiles = sort_get_numpages_of_active_infiles (sort_param)) > 1) { sort_checkalloc_numpages_of_outfiles (thread_p, sort_param); in_sectsize = sort_find_inbuf_size (sort_param->tot_buffers, act_infiles); out_sectsize = sort_param->tot_buffers - in_sectsize * act_infiles; // ... lay out per-input-section addresses ...
num_runs = max(file_contents[i].count for i in input half); if (num_runs == 1) very_last_run = true;
for (j = num_runs; j > 0; j--) { /* Special case: only one input run survives in this pass. * Just copy it to the output instead of running the merge. */ if (!very_last_run && j == 1 && sort_get_numpages_of_active_infiles (sort_param) == 1) { // bulk page copy: read into internal_memory, write to output continue; }
/* Initialize per-input cursors: read first page of each run, peek * its first record into smallest_elem_ptr[i]. * Set up the SORT_REC_LIST tournament. */ ... /* Tournament loop: emit min, advance its cursor, re-position. */ for (;;) { min = min_p->rec_pos; if (very_last_run && !SORT_IS_PARALLEL(sort_param)) (*sort_param->put_fn)(thread_p, &smallest_elem_ptr[min], sort_param->put_arg); else sort_spage_insert (out_cur_bufaddr, &smallest_elem_ptr[min]);
/* Advance min's cursor; refill its input section if exhausted; * if its run is fully drained, unlink it from sr_list. */ ... /* Re-establish the order of sr_list using "last_elem_cmp" * shortcut — see below. */ ... } // ... flush output section, record run length ... } /* swap input/output halves for the next pass */ temp = sort_param->in_half; sort_param->in_half = out_half; out_half = temp; }}병합 토너먼트 — 힙이 아니라 정렬 연결 리스트
섹션 제목: “병합 토너먼트 — 힙이 아니라 정렬 연결 리스트”CUBRID 의 k-way 병합은 힙 이 아니다. SORT_MAX_HALF_FILES = 4
이므로 fan-in 의 최댓값이 4 다 — 힙이 비용을 회수하기에는 너무
작다. 대신 활성 입력 파일마다 SORT_REC_LIST 노드를 하나씩 둔
단방향 연결 리스트를 유지한다. 각 입력의 head 를 기준으로 오름
차순 정렬되어 있다. emit 은 sr_list 의 head 를 가져 간다 (O(1))
이고, 승자의 커서를 한 칸 앞으로 옮긴 뒤 새 head 를 자기 자리
까지 bubble 시킨다 — 최악 O(k) 이지만, 보통 O(1) 이다 (많은 런
에서 새 head 가 여전히 최솟값이기 때문).
// SORT_REC_LIST — src/storage/external_sort.ctypedef struct sort_rec_list SORT_REC_LIST;struct sort_rec_list{ struct sort_rec_list *next; /* next sorted record item */ int rec_pos; /* which input file (index 0..k-1) */ bool is_duplicated; /* dedup-during-merge marker */};rec_pos 가 토너먼트 상태를 들고 다닌다 — 리스트 노드 자체는
정적이다. 그 rec_pos 값들만 자리를 옮긴다. min_p 가 head
포인터이며, emit 후 새 head 의 레코드를 입력 섹션에서 읽어 와서
리스트를 재정렬하고 (대개 한 번의 swap) min_p 가 그 새 head
가 된다.
flowchart LR
subgraph IN["입력 런 (입력 절반 임시 파일별)"]
R0["run on temp[0]<br/>head: 'apple'"]
R1["run on temp[1]<br/>head: 'banana'"]
R2["run on temp[2]<br/>head: 'cherry'"]
R3["run on temp[3]<br/>head: 'date'"]
end
subgraph TOURN["sr_list — 정렬된 연결 리스트"]
M["min_p → rec_pos=0<br/>(apple)"]
M2["next → rec_pos=1<br/>(banana)"]
M3["next → rec_pos=2<br/>(cherry)"]
M4["next → rec_pos=3<br/>(date)"]
M --> M2 --> M3 --> M4
end
subgraph OUT["출력 런"]
OS["out_sectaddr<br/>(write 버퍼 = internal_memory 의 절반)"]
end
R0 --> M
R1 --> M2
R2 --> M3
R3 --> M4
M -- emit 'apple' --> OS
R0 -- next: 'avocado' --> M
M -.bubble: apple 자리에 'avocado'<br/>'avocado' > 'banana', swap.-> M2
last_elem_cmp 단축
섹션 제목: “last_elem_cmp 단축”sort_exphase_merge 안에 자명하지 않은 최적화가 하나 있다 —
한 런의 현재 입력 페이지의 마지막 레코드 가 두 번째로 작은 런의
head 보다 작다고 비교되면, 이 페이지에 남은 모든 레코드 도
다음 경쟁자보다 작다는 사실이 자동으로 보장된다는 점이다. 그래서
페이지 전체를 leverage 하여 레코드 단위 리스트 재정렬을 통째로
건너뛰고 그 페이지를 그대로 출력으로 흘려 보낸다.
// sort_exphase_merge — last_elem_cmp shortcut (condensed)if (act_slot[min_p->rec_pos] == 0) /* new input page */ { /* peek the page's last slot */ sort_spage_get_record (in_cur_bufaddr[min_p->rec_pos], last_slot[min_p->rec_pos] - 1, &last_elem_ptr, PEEK); last_elem_cmp = (*compare) (&last_elem_ptr.data, &smallest_elem_ptr[p->rec_pos].data, compare_arg); }// ... in the main emit loop ...if (last_elem_cmp <= 0) ; /* already found min — skip the bubble walk */else for (s = min_p; s; s = s->next) { /* re-sort sr_list */ ... }거의 disjoint 한 입력 (예 — sort key 로 이미 분할되어 있는 데이터셋) 에서 이 단축은 비교 비용을 튜플당 한 번에서 페이지당 한 번으로 줄여 준다.
병합 도중 중복 제거 — sort_exphase_merge_elim_dup
섹션 제목: “병합 도중 중복 제거 — sort_exphase_merge_elim_dup”중복 제거 변종은 일반 병합과 두 군데에서 다르다. 첫째, sr_list
의 초기 정렬 후 한 번 더 훑어 연속된 같은 head 들을
is_duplicated = true 로 표시한다. 둘째, emit 루프에서 중복으로
표시된 레코드는 출력 영역에 적지 않고 조용히 지나간다.
// sort_exphase_merge_elim_dup — emission gate (condensed)if (min_p->is_duplicated == false) { /* OUTPUT THE RECORD (final pass: put_fn; otherwise: out section) */ ... }else ; /* skip the duplicate */
/* Always advance the winner's cursor regardless of duplication. */미묘한 케이스 하나 — 다음 레코드가 새 입력 페이지의 시작에서 도
착할 때, 중복 제거 루프는 그 페이지의 직전 head 와도 비교해야
한다. (act_slot == last_slot - 1) && (last_elem_cmp == 0) 검사
가 “이 페이지의 마지막 원소가 다른 런의 다음 페이지 첫 원소와
중복” 인 케이스를 처리한다. 일반 병합은 무시하는 이 케이스가
바로 sort_exphase_merge_elim_dup 가 sort_exphase_merge 의
파라미터화된 버전이 아니라 별도 함수인 이유다 — bookkeeping 이
중복 추적과 너무 얽혀 있어 깔끔하게 합쳐지지 않는다.
백엔드 저장소 — FILE_TEMP 와 런 파일
섹션 제목: “백엔드 저장소 — FILE_TEMP 와 런 파일”정렬이 쓰는 모든 임시 파일은 FILE_TEMP 할당이다 (
cubrid-disk-manager.md 에 기술됨). 라이프사이클은 다음과 같다.
- 할당.
sort_add_new_file이 예상 페이지 수를 들고file_create_temp를 호출한다. 파일은 트랜잭션의 임시 파일 목록에 등록되며, 호출자가 retire 하거나 트랜잭션이 끝날 때 까지 살아 있다. - 암호화. 호출자가
includes_tde_class = true를 넘겼으면 (해당 클래스가 TDE-encrypted 일 때 켜진다), 임시 파일도 그 자체 로file_apply_tde_algorithm으로 암호화된다. TDE 플래그는sort_param->tde_encrypted를 타고 매sort_write_area마다 검사된다. - 페이지 I/O.
sort_write_area와sort_read_area는file_numerable_find_nth로 파일 상대 페이지 번호를VPID에 사상한 뒤,pgbuf_copy_from_area/pgbuf_copy_to_area로 보통 fix 경로를 우회한다 — 임시 페이지는 WAL 도 LSN 추적도 필요 없기 때문이다. - 반납.
sort_listfile이 종료할 때,sort_param->temp[]안의 모든 임시 파일이sort_return_used_resources→file_temp_retire로 풀려난다. 만들어졌다면 multipage overflow 파일도 함께 retire 된다.
런 목록 bookkeeping 은 임시 파일 위에 얹은 sparse 한 한 겹이다 —
각 FILE_CONTENTS 엔트리가 동적 num_pages[] 배열을 들고 있으
며, 그 파일의 런 하나당 한 칸을 기록한다. sort_run_add_new 가
append 한다. sort_run_remove_first 는 first_run 을 한 칸
당긴다 (배열을 compact 하지 않는다). 런은 (파일 인덱스, 런
인덱스) 로 식별되며, 그 물리 페이지들은 cur_page[file_index]
에서 시작해 cur_page + num_pages[run_index] 까지 연속 번호로
매겨진다.
// FILE_CONTENTS — src/storage/external_sort.cstruct file_contents{ int *num_pages; /* dynamic array of per-run page counts */ int num_slots; /* size of the num_pages allocation */ int first_run; /* index of the head run, or -1 if empty */ int last_run; /* index of the tail run */ int start_index; /* used for parallel split of the last run */};비교자 디스패치 — SORTKEY_INFO 와 cmp_fn
섹션 제목: “비교자 디스패치 — SORTKEY_INFO 와 cmp_fn”비교자는 호출자가 제공하지만, 그 인자 모양은 관습적이다 —
호출자가 제공하는 cmp_arg 는, CUBRID 의 호출자 모두에서
약속된 형태로, 다중 컬럼 정렬 키를 기술하는 SORTKEY_INFO *
다. 컬럼마다 SUBKEY_INFO 가 하나씩 붙는다.
// SUBKEY_INFO — src/storage/external_sort.hstruct SUBKEY_INFO{ int col; /* tuple-column index */ int permuted_col; TP_DOMAIN *col_dom; TP_DOMAIN *cmp_dom; /* domain for cross-domain MEDIAN */ DB_VALUE_COMPARE_RESULT (*sort_f) (void *tplp1, void *tplp2, TP_DOMAIN *dom, int do_coercion, int total_order, int *start_col); int is_desc; /* descending column */ int is_nulls_first; /* NULLS FIRST per-column */ bool use_cmp_dom;};
struct SORTKEY_INFO{ int nkeys; int use_original; /* sort tuples by ref vs by-value */ SUBKEY_INFO *key; SUBKEY_INFO default_keys[8]; /* inline allocation for common case */ int error;};list-file 호출자 (qfile_sort_list_with_func) 는 두 비교자 중
하나를 설치한다 — use_original == 1 일 때 (일부 컬럼만 키
컬럼이고 비교자가 원본 튜플로 reach back 해야 함) 의
qfile_compare_partial_sort_record, 또는 튜플 전체가 키인
경우의 qfile_compare_all_sort_record. B+Tree 호출자는
compare_driver 를 설치한다 — midxkey 인자를 비교할 줄 안다.
컬럼별 collation, ASC/DESC, NULLS-FIRST/LAST 가 존중되는 곳은
오직 비교자 한 군데뿐이다. 정렬 모듈의 나머지는 collation 을
보지 않는다.
호출자 통합
섹션 제목: “호출자 통합”네 개의 주요 호출자가 sort_listfile 을 엔진의 서로 다른 부분에
배선한다. 각 호출자가 SORT_PARALLEL_TYPE 태그를 골라, 정렬
모듈에게 어떻게 (또는 병렬로 할지 말지) 를 알려 준다.
flowchart TB
subgraph CALL["sort_listfile 호출자"]
QSL["qfile_sort_list_with_func<br/>(SORT_ORDER_BY / SORT_ORDER_WITH_LIMIT)"]
QGB["qexec_groupby<br/>(SORT_GROUP_BY)"]
QGB2["qexec_groupby (해시 spill 경로)<br/>(SORT_GROUP_BY)"]
QAN["qexec_execute_analytic<br/>(SORT_ANALYTIC)"]
BIS["btree_index_sort<br/>(SORT_INDEX_LEAF)"]
end
subgraph SR["sort_listfile (진입점)"]
DEC["sort_check_parallelism<br/>(parallel_type + 입력 페이지 수)"]
SER["sort_listfile_internal (직렬)"]
PAR["px_sort_param[1..N] + worker_manager"]
end
subgraph OUTS["호출자별 put_fn"]
QFS["qfile_put_next_sort_item<br/>(QFILE_LIST_ID 에 append)"]
GBS["qexec_gby_put_next<br/>(그룹별 누적 fold)"]
HGB["qexec_hash_gby_put_next<br/>(spill 된 그룹 재집계)"]
ANP["qexec_analytic_put_next"]
BCL["btree_construct_leafs<br/>(leaf 레코드 작성)"]
end
QSL --> DEC
QGB --> DEC
QGB2 --> DEC
QAN --> DEC
BIS --> DEC
DEC --> SER
DEC --> PAR
SER --> QFS
SER --> GBS
SER --> HGB
SER --> ANP
SER --> BCL
PAR --> QFS
PAR --> BCL
ORDER BY — qfile_sort_list_with_func
섹션 제목: “ORDER BY — qfile_sort_list_with_func”qfile_sort_list_with_func (list_file.c) 가 표준 ORDER BY
진입점이다. 정렬되지 않은 list-file 위에 입력 스캔을 열고, 새
출력 list-file (srlist_id) 을 할당한 뒤, 둘 모두를 들고 다닐
SORT_INFO 구조체를 초기화하고, 기본 콜백
qfile_get_next_sort_item 와 qfile_put_next_sort_item 을 들고
sort_listfile 을 부른다.
// qfile_sort_list_with_func — src/query/list_file.c (condensed)sort_result = sort_listfile (thread_p, NULL_VOLID, estimated_pages, get_func, &info, put_func, &info, cmp_func, &info.key_info, dup_option, limit, srlist_id->tfile_vfid->tde_encrypted, parallel_type); /* SORT_ORDER_BY */dup_option 은 SELECT DISTINCT 일 때 SORT_ELIM_DUP, 평범한
ORDER BY 일 때는 SORT_DUP 이다. parallel_type 은 unlimited
ORDER BY 에서는 SORT_ORDER_BY 이고, LIMIT 가 붙으면
SORT_ORDER_WITH_LIMIT 으로 fallback 한다 (top-K 의 경우 split-
and-merge 로직이 아직 limit 를 존중하지 않으므로 병렬 정렬은
게이트로 막혀 있다). 정렬 후 원본 list-file 은 파괴되고, 출력
list-file 의 식별자가 호출자의 슬롯으로 복사된다.
정렬된 출력이 집계와 윈도우 함수에 어떻게 소비되는지에 대한
자세한 흐름은 cubrid-post-processing.md 를 보라.
sort 기반 GROUP BY — qexec_groupby
섹션 제목: “sort 기반 GROUP BY — qexec_groupby”GROUP BY 호출자 (query_executor.c) 는 sort 경로에서 정렬된
출력 리스트를 전혀 materialise 하지 않는다 — put-콜백 자체가
집계기다.
// qexec_groupby — src/query/query_executor.c (condensed)if (sort_listfile (thread_p, NULL_VOLID, estimated_pages, &qexec_gby_get_next, &gbstate, &qexec_gby_put_next, &gbstate, gbstate.cmp_fn, &gbstate.key_info, SORT_DUP, NO_SORT_LIMIT, gbstate.output_file->tfile_vfid->tde_encrypted, SORT_GROUP_BY) != NO_ERROR) GOTO_EXIT_ON_ERROR;qexec_gby_put_next 는 정렬된 레코드마다 한 번씩 호출된다.
들어오는 레코드의 그룹 키를 직전 키와 비교한다. 키가 바뀌면
이전 그룹의 누적치(accumulator) 를 출력 list-file 에 flush 하고,
누적기를 reset 한 뒤 새 그룹을 연다. 정렬 모듈은 집계가 일어나고
있다는 사실을 절대 알지 못한다 — 그 관점에서 put_fn 은 그저
싱크다.
해시-spill fallback 경로도 같은 패턴을 쓰지만 콜백이
qexec_hash_gby_put_next 다. 이미 spill 된 해시 테이블에서 부분
적으로 fold 된 부분합을 재집계한다. 두 경로 모두 자세한 walk 는
cubrid-post-processing.md 에 있다.
B+Tree 벌크 로드 — btree_index_sort
섹션 제목: “B+Tree 벌크 로드 — btree_index_sort”기존 테이블 위에서 CREATE INDEX 가 돌면, btree_load.c 의
btree_index_sort 가 벌크 로드를 지휘한다. heap 파일(들) 을
스캔하고, (key || OID || class_OID) 모양의 sort 레코드를 만들어
서, 정렬한 뒤, 정렬된 스트림을 btree_construct_leafs 에 흘려
보내 leaf 페이지를 bottom-up 으로 빌드한다.
// btree_index_sort — src/storage/btree_load.creturn sort_listfile (thread_p, sort_args->hfids[0].vfid.volid, 0, &btree_sort_get_next, sort_args, out_func, out_args, /* btree_construct_leafs */ compare_driver, sort_args, SORT_DUP, /* allow dups; uniq enforced inside */ NO_SORT_LIMIT, includes_tde_class, SORT_INDEX_LEAF);unique 인덱스에 대해서도 SORT_DUP 옵션이 쓰인다. unique 검사는
정렬 모듈이 아니라 btree_construct_leafs 안에서 강제되기 때문
이다 — (key || OID) 위의 비교자는 같은 키를 가진 두 행을 다른
레코드로 취급하므로 정렬이 위반을 감지하지 못한다는 점이다.
SORT_INDEX_LEAF 병렬 타입은 더 정교한 병렬 경로를 트리거한다 —
각 워커가 btree_sort_get_next_parallel 로 heap 의 disjoint
한 데이터 sector 부분집합을 스캔해 자기 정렬된 런을 만들고, 이
런들이 워커 사이에서 트리 형태로 병합된다 (아래 참조). 정렬된
스트림이 btree_construct_leafs 에 어떻게 소비되는지의 walk 는
cubrid-btree.md 를 보라.
해시 조인 spill fallback
섹션 제목: “해시 조인 spill fallback”해시 조인의 build side 가 메모리를 넘치면, CUBRID 의 join
실행자는 sort-merge join 으로 fallback 한다 — 역사적인 “spill to
sort” 경로다. 여기서의 정렬은 build side 와 probe side 양쪽을
평범한 qfile_sort_list 일 뿐, 특별한 put-콜백은 없다.
조인 로직이 정렬된 두 리스트를 독립적으로 walk 한다. spill 조건
과 spill 후 iteration 루프는 cubrid-hash-join.md 의 cross-
reference 를 보라.
병렬 정렬
섹션 제목: “병렬 정렬”병렬 정렬은 세 코디네이터 함수로 배선된다 —
sort_check_parallelism (병렬화 여부 결정), sort_start_parallelism
(입력을 워커들에게 분할), sort_end_parallelism (워커별 결과를
하나로 병합). 결정은 타입별이다.
// sort_check_parallelism — src/storage/external_sort.c (condensed)intsort_check_parallelism (THREAD_ENTRY *thread_p, SORT_PARAM *sort_param){ if (sort_param->px_type == SORT_ORDER_BY) { SORT_INFO *sort_info_p = (SORT_INFO *) sort_param->get_arg; parallel_num = parallel_query::compute_parallel_degree (parallel_query::parallel_type::SORT, sort_info_p->input_file->page_cnt, sort_info_p->parallelism /* hint */); if (parallel_num < 2 || sort_info_p->input_file->tuple_cnt <= parallel_num) return 1; sort_param->px_worker_manager = parallel_query::worker_manager::try_reserve_workers (parallel_num); return sort_param->px_worker_manager ? parallel_num : 1; } else if (sort_param->px_type == SORT_INDEX_LEAF) { // ... compute degree from heap page/sector counts ... } else return 1; /* GROUP BY, ANALYTIC, ORDER WITH LIMIT: no parallel yet */}병렬 지원이 있는 것은 SORT_ORDER_BY 와 SORT_INDEX_LEAF 뿐
이다. GROUP BY, analytic 함수, LIMIT 가 붙은 ORDER BY 는
return 1 (직렬) 경로로 빠진다.
ORDER BY 의 병렬 분할
섹션 제목: “ORDER BY 의 병렬 분할”ORDER BY 의 경우 sort_split_input_temp_file 가 입력 list-file
의 페이지 체인을 walk 해 prev/next VPID 링크를 다시 연결하면서
parallel_num 개의 거의 같은 크기 segment 로 잘라, 각 segment
를 워커의 private 입력으로 넘긴다. 각 워커는 독립적으로
sort_listfile_internal 을 — 1단계와 2단계를 자기 private 임시
파일 위의 단일 정렬된 런까지 — 돌린 뒤, pthread_cond_t 로
완료를 알린다.
메인 스레드는 SORT_WAIT_PARALLEL 로 기다린 뒤 sort_end_parallelism
→ sort_merge_run_for_parallel 을 호출한다. 마지막 병합은 다단계
다 — 최대 SORT_MAX_PARALLEL 워커와 단계당 SORT_PX_MERGE_FILES
의 fan-in 으로, 워커들의 결과 런이 높이 ⌈log_{SORT_PX_MERGE_FILES}(parallel_num)⌉
의 트리로 합쳐지며, 각 레벨이 워커 풀에 sort_merge_nruns_parallel
태스크를 다시 던진다. 마지막으로 sort_split_last_run 이 병합된
결과를 다시 워커들에게 분배해, 각 워커가 자기 몫을 출력 list-
file 에 병렬로 쓴다 — 이렇게 ORDER BY 순서를 보존하면서도 쓰기
를 병렬화한다.
인덱스 leaf 의 병렬 빌드
섹션 제목: “인덱스 leaf 의 병렬 빌드”SORT_INDEX_LEAF 의 경우, 병렬 분할은 입력 list-file 이 아니라
파일 sector 단위에서 이루어진다. sort_start_parallelism 이
각 heap 파일을 file_get_all_data_sectors 를 호출하고
parallel_query::ftab_set 으로 sector 목록을 워커들에게 분할
한다. 그 후 각 워커가 자기 btree_sort_get_next_parallel 를
돌려 자기 sector 부분집합 안의 페이지를 iterate 하며 직렬
btree_sort_get_next 와 똑같은 sort 레코드를 만들어 낸다.
병합 후 단계 (sort_merge_run_for_parallel_index_leaf_build) 가
다단계 병합 트리를 돌린 뒤, sort_put_result_from_tmpfile 로
병합된 스트림을 메인 스레드의 btree_construct_leafs 에 흘려
보낸다. leaf 빌드 자체는 병렬화 되지 않는다 — sort 의 윗부분
만 병렬화된다 — B+Tree leaf 가 strict 한 순서로 bottom-up 으로
쓰여지기 때문에, 병렬 appender 가 결국 가장 오른쪽 leaf 에서
직렬화될 수밖에 없다는 점이다.
flowchart TB
subgraph S1["sort_start_parallelism"]
SP1["sort_split_input_temp_file<br/>(ORDER BY: list-file VPID 체인 자르기)"]
SP2["ftab_set::split (INDEX_LEAF: sector 목록 자르기)"]
end
subgraph WORKERS["N 워커 스레드"]
W0["worker 0:<br/>sort_listfile_execute<br/>= 1단계 + 2단계"]
W1["worker 1: ..."]
W2["worker 2: ..."]
W3["worker 3: ..."]
end
subgraph S2["sort_end_parallelism"]
SM["sort_merge_run_for_parallel<br/>(레벨 0..L: 단계당 SORT_PX_MERGE_FILES 병합)"]
SLR["sort_split_last_run<br/>(병합된 런을 워커들에게 다시 분배)"]
SPF["sort_put_result_for_parallel<br/>(출력 list-file 에 병렬 쓰기)"]
end
S1 --> WORKERS
WORKERS --> SM --> SLR --> SPF
병렬 계층은 호출별 opt-in 이다 (호출자의 SORT_PARALLEL_TYPE
와 compute_parallel_degree 의 답이 모두 게이트). 실패한 워커
는 자기 에러를 sort_param->main_error_context 로 funnel 하고,
메인 스레드가 완료 시점에 cuberr::context::swap 으로 그것을
다시 자기 컨텍스트로 가져 온다.
CUBRID 이 이 기본값을 고른 이유
섹션 제목: “CUBRID 이 이 기본값을 고른 이유”k = 4 (작은 fan-in), 정렬된 연결 리스트 (힙 없음), natural mergesort (런 탐지 + 병합) 의 조합은 흔치 않지만 일관된 선택이다.
- 작은
SORT_MAX_HALF_FILES는 연결 리스트 토너먼트 비용을 싸게 유지하고, 큰 동시 워크로드에서 file-descriptor 압박을 피한다. 절충은 큰 입력에서 병합 패스가 늘어난다는 것이지만,PRM_ID_SR_NBUFFERS의 기본값이 대부분의 install 에서 충분히 크기 때문에 패스가 늘어날 일은 드물다. - 런 탐지가 붙은 natural mergesort 는 near-sorted 입력에 친절 하다. 실행기는 sort 에 그런 입력을 자주 건넨다 (예 — 인덱스 prefix 가 이미 정렬을 만들어 둔 컬럼 위의 GROUP BY). quicksort 기반 생성기는 사전 정렬을 보지 못하는데, 이 구현은 그 경우 O(N) 으로 collapse 한다.
- 별도 함수로 분리된 dedup-during-merge 는 의도적인 코드 중복이다 — 등호 추적이 충분히 도처에 퍼져 있어서 일반 병합 안에 런타임 검사로 섞어 두면 (더 흔한) 일반 병합 경로가 느려 진다는 점이다. 두 함수는 본문의 ~70 % 를 공유하지만 각각이 곧은 직선 코드로 유지된다.
소스 코드 가이드
섹션 제목: “소스 코드 가이드”anchor 는 심볼명이다. 라인은 흘러간다.
심볼들을 책임별로 묶어 두었다.
공개 진입점 / 드라이버
sort_listfile— 최상위 진입점.SORT_PARAM을 셋업하고, 병렬 vs. 직렬을 결정해 디스패치한다.sort_listfile_internal— 직렬 드라이버. 1단계 후 2단계.sort_listfile_execute— 병렬 워커 변종.cubthread::callable_task가 호출한다.
1단계 — 런 생성
sort_inphase_sort— 채우고-정렬-flush 루프. 모든 런을 만든다.sort_run_sort— 메모리 내 포인터 배열에 대한 natural mergesort.sort_run_find후sort_run_merge를 호출.sort_run_find— 단조 구간 탐지 (asc 또는 desc), 내림이면 flip, SORT_STACK 에 push. 중복을 inline 으로 표시한다.sort_run_merge— 스택 꼭대기의 인접 두 런을 alternate 버퍼 로 병합.low_high를 ping-pong.sort_run_flip— 제자리 reverse (run-find 가 내림 구간에서 사용).sort_run_flush— 정렬된 메모리 내 런을FILE_TEMP파일의 슬롯 페이지 시퀀스로 직렬화.sort_validate— 디버그 전용 ordering 검사.
2단계 — 병합
sort_exphase_merge— 표준 k-way 병합 루프.sort_exphase_merge_elim_dup— 병합 도중 dedup 하는 변종.sort_get_numpages_of_active_infiles— 런이 하나라도 남은 입력 파일 수.sort_get_num_file_contents— 한 입력 파일의 런 수.sort_run_add_new/sort_run_remove_first— 파일별 런 목록 관리.sort_checkalloc_numpages_of_outfiles— 매 병합 패스 전에 출력 페이지를 미리 할당. 사용되지 않을 출력 파일은 retire.sort_find_inbuf_size— 버퍼를 입력 섹션들 (활성 입력당 하나) 과 출력 섹션 사이로 분할.
백엔드 저장소
sort_add_new_file— 정렬용 임시 파일을 위한file_create_temp래퍼.tde_encrypted를 존중.sort_write_area/sort_read_area— 벌크 페이지 I/O.pgbuf_copy_from_area/pgbuf_copy_to_area사용.sort_return_used_resources— 모든 임시 파일 retire, 내부 메모리 free, 병렬 상태 정리.sort_retrieve_longrec—multipage_file에서overflow_get으로 긴 레코드 페치.sort_get_avg_numpages_of_nonempty_tmpfile— 출력 절반의 페이지 할당 추정량.
슬롯 페이지 프리미티브 (private)
sort_spage_initialize,sort_spage_insert,sort_spage_get_record,sort_spage_get_numrecs,sort_spage_offsetcmp,sort_spage_compact,sort_spage_find_free— 정렬 임시 페이지를 위한 슬롯 페이지 모델의 로컬 재구현이다. 공유slotted_page.c와 분리되어 있는 이유는, 임시 페이지가 LSN, WAL, 페이지 버퍼 fix 모두 필요로 하지 않기 때문이다.
비교자 + 키 정보 (헤더 노출)
SORT_GET_FUNC,SORT_PUT_FUNC,SORT_CMP_FUNC— 콜백 typedef (external_sort.h).SORT_REC— 임시 레코드 헤더. breadcrumb VPID + offset 벡터를 들고 있으며 임시 파일 페이지에 산다.SUBKEY_INFO/SORTKEY_INFO— 다중 컬럼 키 descriptor. 컬럼별 collation, ASC/DESC, NULLS FIRST/LAST 포함.SORT_INFO— list-file 호출자별 wrapper.s_id,input_file,output_file,key_info,parallelism,orderby_stats를 들고 다닌다.
병렬성 (server-mode 한정)
sort_check_parallelism—parallel_query::compute_parallel_degree와 워커 reservation 으로 차수 결정.sort_start_parallelism/sort_end_parallelism— 워커 스폰과 결과 병합 코디네이션.sort_split_input_temp_file— ORDER BY 입력 list-file 페이지 들을 parallel_num 개 segment 로 자르기.sort_merge_run_for_parallel/sort_merge_run_for_parallel_index_leaf_build— 워커 결과들 의 다단계 트리 병합. 단계별SORT_PX_MERGE_FILESfan-in.sort_merge_nruns/sort_merge_nruns_parallel— 한 트리 레벨의 병합 워커.sort_split_last_run— 마지막 병합된 런을 워커들에게 다시 분배해 출력 list-file 에 병렬 쓰기를 가능하게 함.sort_put_result_for_parallel— 워커별, 자기 몫 결과의 writer.sort_put_result_from_tmpfile— 마지막 임시 파일을put_fn으로 drain.
호출자 어댑터
qfile_sort_list_with_func(list_file.c) — 일반 ORDER BY / DISTINCT 진입점.qfile_get_next_sort_item+qfile_put_next_sort_item와 비교자qfile_compare_partial_sort_record/qfile_compare_all_sort_record를 공급.qfile_sort_list(list_file.c) — 커스텀 콜백이 필요 없는 호출자를 위한qfile_sort_list_with_func의 얇은 wrapper.qexec_groupby(query_executor.c) — sort 기반 GROUP BY 드라이버.qexec_gby_get_next/qexec_gby_put_next와 spill 경로qexec_hash_gby_put_next사용.qexec_orderby_distinct(query_executor.c) — 최상위 ORDER BY / DISTINCT 드라이버.qfile_sort_list_with_func에 위임.qexec_execute_analytic(query_executor.c) — window 함수 드라이버.(PARTITION BY, ORDER BY)로 정렬.btree_index_sort(btree_load.c) — B+Tree 벌크 로드 드라이버.btree_sort_get_next와btree_construct_leafs사용.btree_sort_get_next_parallel(btree_load.c,external_sort.h) — 인덱스 leaf 빌드의 병렬 모드 get 콜백.
이 개정 시점의 위치 힌트 (2026-05-01)
섹션 제목: “이 개정 시점의 위치 힌트 (2026-05-01)”| 심볼 | 파일 | 라인 |
|---|---|---|
SORT_PARALLEL_TYPE | external_sort.h | 59 |
SORT_GET_FUNC / SORT_PUT_FUNC / SORT_CMP_FUNC | external_sort.h | 68 |
SORT_REC | external_sort.h | 77 |
SUBKEY_INFO | external_sort.h | 101 |
SORTKEY_INFO | external_sort.h | 131 |
SORT_INFO | external_sort.h | 142 |
sort_listfile (decl) | external_sort.h | 160 |
SORT_MAX_HALF_FILES | external_sort.c | 75 |
SORT_MAXREC_LENGTH | external_sort.c | 91 |
FILE_CONTENTS | external_sort.c | 107 |
SORT_PARAM | external_sort.c | 134 |
SORT_REC_LIST | external_sort.c | 192 |
SORT_STACK | external_sort.c | 238 |
sort_inphase_sort (decl) | external_sort.c | 253 |
sort_exphase_merge_elim_dup (decl) | external_sort.c | 255 |
sort_exphase_merge (decl) | external_sort.c | 256 |
sort_run_sort | external_sort.c | 1170 |
sort_listfile | external_sort.c | 1346 |
sort_listfile_execute (server-mode) | external_sort.c | 1599 |
sort_listfile_internal | external_sort.c | 1748 |
sort_inphase_sort | external_sort.c | 1848 |
sort_run_find | external_sort.c | 887 |
sort_run_merge | external_sort.c | 1008 |
sort_retrieve_longrec | external_sort.c | 2412 |
sort_exphase_merge_elim_dup | external_sort.c | 2456 |
sort_put_result_from_tmpfile | external_sort.c | 3245 |
sort_split_last_run | external_sort.c | 3344 |
sort_exphase_merge | external_sort.c | 3380 |
sort_split_input_temp_file | external_sort.c | 4457 |
sort_merge_run_for_parallel | external_sort.c | 4568 |
sort_merge_run_for_parallel_index_leaf_build | external_sort.c | 4733 |
sort_merge_nruns | external_sort.c | 4883 |
sort_check_parallelism | external_sort.c | 4935 |
sort_put_result_for_parallel | external_sort.c | 5040 |
sort_merge_nruns_parallel | external_sort.c | 5131 |
sort_start_parallelism | external_sort.c | 5195 |
sort_end_parallelism | external_sort.c | 5329 |
sort_write_area | external_sort.c | 5417 |
sort_read_area | external_sort.c | 5477 |
sort_get_num_half_tmpfiles | external_sort.c | 5522 |
sort_checkalloc_numpages_of_outfiles | external_sort.c | 5577 |
sort_get_numpages_of_active_infiles | external_sort.c | 5684 |
sort_find_inbuf_size | external_sort.c | 5723 |
sort_run_add_new | external_sort.c | 5746 |
sort_run_remove_first | external_sort.c | 5786 |
sort_get_num_file_contents | external_sort.c | 5807 |
qfile_sort_list_with_func | list_file.c | 4330 |
qfile_sort_list | list_file.c | 4481 |
qexec_groupby (sort path) | query_executor.c | 5247 |
qexec_groupby (hash-spill sort_listfile) | query_executor.c | 5465 |
qexec_groupby (sort-based sort_listfile) | query_executor.c | 5546 |
qexec_orderby_distinct | query_executor.c | 3936 |
qexec_orderby_distinct_by_sorting | query_executor.c | 4000 |
btree_index_sort | btree_load.c | 3208 |
btree_sort_get_next_parallel | btree_load.c | 3325 |
btree_sort_get_next | btree_load.c | 3659 |
소스 검증 (2026-05-01 기준)
섹션 제목: “소스 검증 (2026-05-01 기준)”cubrid-post-processing.md가qexec_groupby와qexec_execute_analytic가 정렬 콜백 (qexec_gby_put_next,qexec_hash_gby_put_next,qexec_analytic_put_next) 을 어떻게 쓰는지 문서화한다. 전략 선택 (sort 기반 vs. hash 기반 GROUP BY) 도 거기 산다. 본 문서는 두 경로가 결국 부르는 정렬 substrate 만 다룬다.cubrid-post-processing.md의 라인 번호 참조 (예 —external_sort.c:1347가sort_listfile) 는 2026-05-01 기준으로 한 칸 어긋나 있다 — 함수 시그니처 라인이 1347 이고 함수 이름은 1346 에 있다. 심볼을 anchor 로 쓰자.cubrid-btree.md가 벌크 로드 소비자 (btree_construct_leafs) 와 leaf 페이지 쓰기 경로를 문서화 한다.btree_index_sort자체는sort_listfile위의 얇은 wrapper 이며 본 문서에서 walk 한다. unique 제약 검사는 소비자에 있고 정렬에는 없다는 점이다 — 그래서 unique 인덱스에 대해서도SORT_DUP가 쓰인다 ((key || OID)위의 sort 비교자는 키만으로는 uniqueness 위반을 감지할 수 없다).cubrid-disk-manager.md가FILE_TEMP라이프사이클을 소유한다. 정렬 임시 파일에는 한 가지 특수성이 있다 — TDE 플래 그 (includes_tde_class) 를 이고 갈 수 있다는 점이다. 그래서 중간의 암호화된 클래스 데이터가 raw 디스크에서 읽히지 않는다. 플래그는 매sort_write_area호출에 동승한다.cubrid-list-file.md(예정) —QFILE_LIST_ID를, ORDER BY 와 GROUP BY 의 입출력 sink 모양으로 문서화한다.external_sort.h의SORT_INFO구조체가 그 다리다.cubrid-hash-join.md(예정) — 해시 조인이 build side 를 spill 하면 fallback sort-merge join 이 양쪽 입력에qfile_sort_list를 쓴다. 평범한 ORDER BY 스타일 경로이며 특별한 put-콜백은 없다.cubrid-post-processing.md가 참조하는 deckSort, Hash Group By.pptx는 sort GROUP BY 의 콜백 규율을 짚어 주며 본 문서의 구조와 일치한다.- loser tree 라는 표현이 CUBRID 코드 리뷰에서 비공식적으로
쓰이는 일이 있는데, 실제 구현 (
SORT_REC_LIST sr_list) 은 emit 당 O(k) 로 도는 정렬된 단방향 연결 리스트이지, 트리의 O(log k) 가 아니다. k = 4 에서는 두 자료구조의 점근적 거동 이 동일하며, 캐시 footprint 측면에서 연결 리스트가 이긴다.
미해결 질문
섹션 제목: “미해결 질문”- 적응적 런 생성 알고리즘. CUBRID 은 메모리 내 버퍼 위에서 항상 natural mergesort 를 쓴다. replacement-selection (레코드 당 힙 갱신 비용을 내고 더 긴 기댓 런 길이를 얻음) 으로 바꾸어 총 I/O 를 줄일 수 있는 워크로드 영역이 있는가? Postgres v15 는 캐시 거동을 이유로 그 반대 방향으로 — replacement-selection 에서 quicksort 로 — 옮겼다. CUBRID 의 전형적인 ORDER BY 위주 OLAP 워크로드 위에서의 측정이 결판을 낼 것이다.
- GPU 가속 정렬. 현대 엔진 (HeavyDB, 커스텀 커널을 쓰는
ClickHouse) 은 가용할 때 메모리 내 정렬을 GPU 로 밀어 넣는다.
CUBRID 에는 GPU 통합이 없다. 질문은 —
sort_run_sort안의 메모리 내 단계 전체를 호스트 측 DMA in/out 을 곁들인 CUDA Thrust 호출로 대체할 수 있는가다. 임시 파일 단계는 CPU 에 남는다. - 재시작 가능한 진행을 위한 정렬 상태 체크포인트. 멀티-
테라바이트 데이터셋 위의 장시간 ORDER BY 가 끝 무렵에 실패
하면 현재는 처음부터 다시 시작한다. N 페이지마다 런 목록
bookkeeping 을 체크포인트 해 두면 회복이 이미 끝난 병합 패스
를 건너뛸 수 있다. bookkeeping 의 크기가 작다 (임시 파일당
FILE_CONTENTS한 개, 각각 동적 int 배열) — 체크포인트 비용 이 무시할 만하다. - k > 4 케이스를 위한 polyphase 병합. CUBRID 의 하드 캡
SORT_MAX_HALF_FILES = 4는 매우 큰 정렬에 많은 패스를 강요 한다. 캡을 올리는 일은 간단하지만 동시성에서 file-descriptor 압박을 키운다. 대안은 polyphase 병합 (Knuth §5.4.2) 으로, 같은 총 파일 수를 유지하면서 더 나은 병합 균형을 위해 런을 Fibonacci 스타일로 분배하는 방식이다. CUBRID 의 전형적인 정렬 버퍼 크기에서, 대부분 워크로드의 이득은 작을 것이다. - GROUP BY 와 analytic 의 병렬 정렬. 2026-05-01 시점에
병렬 커버리지가 있는 것은
SORT_ORDER_BY와SORT_INDEX_LEAF뿐이다.SORT_GROUP_BY와SORT_ANALYTIC의 분기는sort_check_parallelism와sort_start_parallelism에서 명시적으로return 1/ER_FAILED로 빠진다. GROUP BY 로의 병렬 확장은 사소하지 않다 — 그룹별 누적 상태가 워커 사이를 넘어 합쳐져야 한다는 점에서, 다른 계층에서의 해시-spill 재 집계 문제와 동치다. - 해시 조인 spill fallback 의 통합. 예정된
cubrid-hash-join.md의 cross-reference 는 현재로서는 forward declaration 이다. 실제 코드 경로 (qexec_hashjoin등) 는 파티션이 들어가지 않을 때qfile_sort_list를 직접 호출한다.SORT_HASH_JOIN_SPILL병렬-타입 태그는 없다 — spill 이 평범한 ORDER BY 로 취급되어 spill 이 클 때조차 병렬 정렬을 쓸 수 없다는 점이다. 전용 병렬- 타입 슬롯 하나를 만들 만한 가치가 있는지가 열려 있다.
- 코드:
src/storage/external_sort.c(드라이버 + 런 생성 + 병합- 병렬 코디네이션)
src/storage/external_sort.h(콜백 typedef +sort_listfile선언)src/storage/btree_load.c(btree_index_sort,btree_sort_get_next,btree_sort_get_next_parallel,btree_construct_leafs)src/query/list_file.c(qfile_sort_list_with_func,qfile_sort_list,qfile_get_next_sort_item,qfile_put_next_sort_item,qfile_compare_partial_sort_record,qfile_compare_all_sort_record)src/query/query_executor.c(qexec_groupby,qexec_orderby_distinct,qexec_orderby_distinct_by_sorting,qexec_execute_analytic, GROUP BY put/get 콜백)src/storage/file_manager.c(file_create_temp,file_temp_retire,file_apply_tde_algorithm,file_numerable_find_nth,file_alloc_multiple)src/base/system_parameter.c(PRM_ID_SR_NBUFFERS,PRM_ID_SORT_BUFFER_SIZE)src/storage/px_sort.h,src/query/px_callable_task.hpp,src/query/px_worker_manager.hpp,src/query/px_parallel.hpp,src/query/px_ftab_set.hpp(external_sort.c가 참조하는 병렬 인프라)
- 이론적 참고문헌:
- Knuth, The Art of Computer Programming, vol. 3: Sorting and Searching, 2nd ed., chapter 5 (특히 §5.4.1 “Multiway merging and replacement selection, §5.4.2 The polyphase merge”, §5.2.4 Sorting by merging).
- Graefe, “Query Evaluation Techniques for Large Databases”, ACM Computing Surveys 25(2), 1993, §7 External sorting.
- Graefe, “Implementing Sorting in Database Systems”, ACM Computing Surveys 38(3), 2006 — in-database sort 엔지니어링의 실용 서베이.
- Petrov, Database Internals (O’Reilly, 2019), chapter 14 Query Execution — external-sort 와 sort 기반 GROUP BY 의 framing.
- Garcia-Molina, Ullman, Widom, Database Systems: The Complete Book, 2nd ed., chapter 15.4 — §“학술적 배경” 에서 쓴 I/O 비용 모델.
- 이 지식 베이스 안의 cross-reference:
knowledge/code-analysis/cubrid/cubrid-post-processing.md(같은 sort substrate 위의 sort 기반 GROUP BY + analytic 함수)knowledge/code-analysis/cubrid/cubrid-btree.md(벌크 로드 정렬의 소비자btree_construct_leafs)knowledge/code-analysis/cubrid/cubrid-disk-manager.md(FILE_TEMP라이프사이클)knowledge/research/dbms-general/database-internals.md(Petrov 14장 capture)