(KO) CUBRID 후처리 — 집계, 윈도우/분석 함수, 그리고 Sort vs Hash GROUP BY
목차
학술적 배경
섹션 제목: “학술적 배경”후처리(post-processing)는 모든 입력 튜플이 이미 생산된 뒤에 — 테이블 스캔, 인덱스 스캔, 조인, 서브쿼리 리스트 파일에 의해 만들어진 뒤에 — 실행되는 절반의 질의 실행이다. 교과서가 다루는 세 가지 문제는 같은 기계와 같은 list-file + sort 기반 위에서 굴러간다.
-
그룹 단위 집계(grouped aggregation) — 입력 튜플 스트림과 그룹핑 키 집합이 주어졌을 때, 서로 다른 키마다 한 개의 출력 튜플과
SUM,AVG,MIN,MAX,COUNT등의 값을 함께 만들어 내는 문제다. 두 가지 전략이 존재한다.- Sort 기반 GROUP BY: 입력을 그룹핑 키로 정렬한 뒤 한 번의 선형 스캔을 수행한다. 같은 키를 가진 튜플들이 인접해 있으므로 키가 바뀔 때마다 누산기를 리셋하면 된다. 비용은 정렬이 좌우한다.
- Hash 기반 GROUP BY: 그룹핑 키를 키로 삼는 인메모리 해시 테이블을 유지한다. 입력 튜플마다 테이블을 프로브하여 새 누산기를 만들거나 기존 누산기에 합친다. 비용은 해시 프로브가 좌우하며, 해시 테이블이 메모리에 들어 맞는 한 정렬은 필요 없다. 들어맞지 않으면 해시 테이블이 디스크로 spill하거나 sort 기반으로 격하된다.
Database Internals(Petrov, 2019) 14장 Query Execution은 이 트레이드오프를 그룹핑 선택도(groups / tuples)와 메모리 예산의 함수로 정리한다. 선택도가 높으면(서로 다른 키가 적으면) hash가 유리하고, 선택도가 낮으면(서로 다른 키가 많으면) sort가 유리하다.
-
윈도우 / 분석 함수(window / analytic) —
RANK(),ROW_NUMBER(),LAG(),LEAD(),MEDIAN(),PERCENTILE_CONT()등 SQL:2003에 정의된 함수들이다. 각 윈도우 함수는 세 개의 하위 절을 가진다.PARTITION BY(행을 그룹화),ORDER BY(파티션 안에서 순서를 정함), 그리고 선택적인 프레임(ROWS BETWEEN ... AND ...). 집계와 달리 모든 입력 튜플이 출력 튜플을 만들어 낸다. 튜플 $t$에 대한 윈도우 함수 값은 $t$가 속한 파티션 안에서 그 프레임에 의해 결정된다. 교과서적 실행 모델은 다음과 같다.- 입력을
(PARTITION BY, ORDER BY)로 정렬한다. - 정렬된 스트림을 따라가며 파티션 경계와 정렬 키 경계를 추적한다.
- 각 튜플마다 프레임 위에서 함수 값을 계산한다.
LAG/LEAD같은 내비게이션 함수,NTH_VALUE같은 그룹 안 오프셋 함수는 같은 파티션 내 다른 튜플로의 임의 접근이 필요하다는 점이다. 이는 중간 그룹/값 리스트 파일을 작성한 뒤 다시 스캔해서 구현한다.
- 입력을
-
외부 정렬(external sort) — 입력 리스트 파일이 정렬 버퍼 (
PRM_ID_SR_NBUFFERS)에 들어맞지 않을 때 정렬 모듈은 고전적인 2단계 머지 소트로 격하된다. in-phase는 버퍼 크기 청크에서 정렬된 run을 만들고, ex-phase는 그 run들을 k-way 머지한다. sort 기반 GROUP BY와 분석 함수의 정렬이 모두 이 기반 위에서 동작한다. Petrov 14장(sort)과 Garcia-Molina/Ullman/Widom의 Database Systems: The Complete Book 15.4장이 모델을 기술하며, CUBRID의 구현은src/storage/external_sort.c에 거주한다.
이 세 문제는 세 가지 성질을 공유한다. (a) 입력은 list file
(QFILE_LIST_ID) — 임시 페이지가 뒷받침하는 가상 순차 파일이다.
(b) 정렬은 콜백 샌드위치(callback sandwich) 로 호출된다. 곧
sort_listfile (..., get_func, put_func, ...)가 get_func로 sort
레코드를 읽고 put_func로 정렬된 레코드를 내보낸다. (c) 키마다의
상태(집계의 누산기, 분석의 윈도우 함수 상태)는 작은 인메모리 구조
체에 보관되며 put 콜백 안으로 접혀 들어가서 정렬 자체는 자기가
집계를 하고 있다는 사실을 알지 못한다는 점이다.
이 콜백 모양 덕분에 CUBRID의 sort 기반 GROUP BY는 호출자가 두 줄
짜리(qexec_groupby → sort_listfile)이 되고, hash 기반 경로는
같은 골격에 끼워 넣을 수 있다. 해시 테이블이 spill하면 키/값 쌍을
리스트 파일로 덤프하고, 마지막 패스는 다시 sort_listfile 호출이
된다.
DBMS 공통 설계 패턴 (Common DBMS Design)
섹션 제목: “DBMS 공통 설계 패턴 (Common DBMS Design)”엔진들이 가장 눈에 띄게 갈리는 지점은 전략 선택을 어디에서 하는가 (planner vs. executor) 그리고 spill을 어떻게 처리하는가 이다. CUBRID의 선택을 자리잡게 해 주는 세 가지 비교 설계를 살펴본다.
PostgreSQL — nodeAgg.c, nodeWindowAgg.c
섹션 제목: “PostgreSQL — nodeAgg.c, nodeWindowAgg.c”PostgreSQL 실행기는 두 개의 별도 노드를 둔다.
-
Agg—src/backend/executor/nodeAgg.c에 구현된다. planner (create_agg_plan)가enable_hashagg,work_mem, 추정 그룹 수에 근거해AGG_HASHED/AGG_SORTED/AGG_PLAIN/AGG_MIXED중 하나를 plan 시점에 결정한다. 해시 집계가work_mem을 넘으면, v13 이후 PostgreSQL은 grace hashing으로 spill한다. 곧 오버플로 튜플을 파티션별 테이프 파일로 흩뿌리고 각 파티션을 독립적으로 재집계한다. 누산기(AggStatePerTrans)와 그룹별 상태 (AggStatePerGroup)는aggcontext메모리에 유지된다. -
WindowAgg—nodeWindowAgg.c에 구현된다. 입력은 위쪽에서(PARTITION BY, ORDER BY)로 정렬되어(별도 Sort 노드가 WindowAgg에 공급) WindowAgg는 파티션을 따라가며 프레임 안에서 각 함수 값을 계산한다. 프레임 로직은RANGE,ROWS,GROUPS모드 모두에 공통이다.
CUBRID 실행기는 GROUP BY를 단일 BUILDLIST_PROC 노드와 별도
분석 루프를 사용한다. 다만 전략 선택은 런타임 이다. 실행기는
end_one_iteration 시점에 관측된 선택도를 보고, 해시 테이블에 계속
누적할지 sort로 폴백할지 결정한다(자세한 내용은 아래에서 다룬다).
MySQL — Item_sum, 임시 테이블, Aggregator_distinct
섹션 제목: “MySQL — Item_sum, 임시 테이블, Aggregator_distinct”MySQL은 각 집계마다 Item_sum 서브클래스(Item_sum_avg,
Item_sum_min, …)를 사용하며, 역사적으로 그룹핑 표현식을 키로 한
임시 테이블로 GROUP BY를 구체화해 왔다. 현대 MySQL(8.0+)은 기본적
으로 AggregateIterator를 사용해 해시 기반 집계를 수행한다.
임시 테이블 폴백은 해시 테이블이 tmp_table_size /
max_heap_table_size를 초과할 경우를 위해 여전히 존재한다. 윈도우
함수는 정렬된 스트림 위의 WindowIterator가 처리한다.
MySQL의 계약 — 집계마다, 그룹마다 누산기 객체 하나, 튜플이 흐를 때
변형됨 — 은 CUBRID의 AGGREGATE_TYPE 체인(g_agg_list)과 같은
모양이다.
Oracle / SQL Server — 비용 기반 폴백을 동반한 sort/hash GROUP BY
섹션 제목: “Oracle / SQL Server — 비용 기반 폴백을 동반한 sort/hash GROUP BY”Oracle 옵티마이저는 추정 카디널리티에 근거해 HASH GROUP BY와
SORT GROUP BY 사이를 선택하며, SQL Server의 Stream Aggregate 와
Hash Match (Aggregate)이 그에 대응되는 선택지다. 양쪽 모두 해시
오버플로를 TempDB 류 저장소로 spill하고 파티션 기반 재결합으로
이어 나간다 — PostgreSQL의 현대 HashAgg와 유사한 모양이다.
이론 ↔ CUBRID 명칭 매핑
섹션 제목: “이론 ↔ CUBRID 명칭 매핑”| 이론적 개념 | CUBRID 명칭 |
|---|---|
| 그룹별 누산기 | AGGREGATE_TYPE::accumulator (cubxasl::aggregate_accumulator) |
| 실행 순서의 집계 체인 | BUILDLIST_PROC_NODE::g_agg_list (xasl.h) |
| 출력 측 집계 체인 (SELECT-list 모양) | GROUPBY_STATE::g_output_agg_list |
| sort 기반 실행 중 그룹별 상태 | GROUPBY_STATE (query_executor.c:213) |
| 롤업 레벨 배열 | GROUPBY_STATE::g_dim of GROUPBY_DIMENSION |
| Hash GROUP BY 컨텍스트 | AGGREGATE_HASH_CONTEXT referenced via GROUPBY_STATE::agg_hash_context |
| 해시 테이블 spill 리스트 | AGGREGATE_HASH_CONTEXT::part_list_id |
| 해시 테이블 메모리 상한 | PRM_ID_MAX_AGG_HASH_SIZE (default 2 MB) |
| 해시 전략 격하 임계 | HASH_AGGREGATE_VH_SELECTIVITY_TUPLE_THRESHOLD (2000) + HASH_AGGREGATE_VH_SELECTIVITY_THRESHOLD (0.5) |
| 정렬 콜백 계약 | sort_listfile (get_fn, put_fn, cmp_fn, key_info, ...) (external_sort.c:1347) |
| sort 기반 GROUP BY put 콜백 | qexec_gby_put_next |
| hash 기반 GROUP BY put 콜백 | qexec_hash_gby_put_next |
| 윈도우 함수의 함수별 상태 | ANALYTIC_FUNCTION_STATE (query_executor.c:259) |
| 윈도우 함수 실행 상태 | ANALYTIC_STATE (query_executor.c:288) |
| 그룹별 튜플 카운트 (윈도우용) | ANALYTIC_FUNCTION_STATE::curr_group_tuple_count |
| 정렬 키 내 튜플 카운트 (윈도우용) | ANALYTIC_FUNCTION_STATE::curr_sort_key_tuple_count |
| 그룹 헤더 사이드카 리스트 | ANALYTIC_FUNCTION_STATE::group_list_id |
| 정렬 키 사이드카 리스트 | ANALYTIC_FUNCTION_STATE::value_list_id |
| 윈도우 함수 출력 재조립 패스 | qexec_analytic_update_group_result |
CUBRID의 구현
섹션 제목: “CUBRID의 구현”qexec_execute_mainblock_internal 드라이버는 정렬되지 않은 입력
리스트 파일을 만들어 낸 뒤, 후처리 단계로 넘어가는 세 개의 진입점으로
분기한다.
qexec_groupby—groupby_list를 가진BUILDLIST_PROCXASL 노드용 진입점. 선택적 WITH ROLLUP을 포함한 GROUP BY 레인 이다.qexec_execute_analytic—ANALYTIC_EVAL_TYPE체인을 가진 XASL 노드용 진입점. 체인이 요구하는 서로 다른 정렬 리스트 마다 한 번씩 호출된다. 즉 같은(PARTITION BY, ORDER BY)를 공유하는 분석 함수들은 파스 시점 (pt_optimize_analytic_list)에서 묶여 하나의 정렬을 함께 타게 된다.qexec_orderby_distinct—ORDER BY와DISTINCT를 위한 진입점. 이 문서에서는 다루지 않는다. 키별 누산기가 빠진 같은sort_listfile기반이다.
flowchart LR
subgraph PROC["처리 단계 (input feed)"]
SCAN["스캔 / 조인 / 서브쿼리"]
LIST["xasl->list_id\n(입력 리스트 파일)"]
HASH["AGGREGATE_HASH_CONTEXT\n(인메모리 해시 테이블)"]
PART["part_list_id\n(spill된 해시 엔트리)"]
end
subgraph POST["후처리 단계"]
GBY["qexec_groupby\n(qexec_execute_mainblock_internal)"]
ANA["qexec_execute_analytic"]
SLF1["sort_listfile\n(GBY: get=qexec_gby_get_next,\n put=qexec_gby_put_next)"]
SLF2["sort_listfile\n(HGBY: put=qexec_hash_gby_put_next)"]
SLF3["sort_listfile\n(ANA: put=qexec_analytic_put_next)"]
OUT["output_file\n(QFILE_LIST_ID)"]
end
SCAN --> LIST
SCAN -. hash agg 적격 .-> HASH
HASH -. LRU spill .-> PART
HASH -. 매우-높은 선택도 .-> PART
LIST --> GBY
PART --> GBY
HASH --> GBY
GBY -- sort 경로 --> SLF1 --> OUT
GBY -- hash 경로 --> SLF2 --> OUT
LIST --> ANA --> SLF3 --> OUT
세 하위 주제 — 집계, 분석, sort/hash 선택 — 는 GROUPBY 상태
구조체, AGGREGATE_HASH_CONTEXT, sort_listfile 기반을
공유한다. 다만 각자가 자기 put 콜백과 자기 상태 기계를 가진다.
하나씩 따라가 본다.
집계 / GROUP BY
섹션 제목: “집계 / GROUP BY”GROUP BY 레인은 두 개의 상태 객체를 가진다. GROUPBY_STATE
(질의 단위, sort/hash 전략 선택과 롤업 디멘전 배열을 보유)와
GROUPBY_DIMENSION (롤업 레벨마다 하나씩, 누산기를 위한
자기 d_agg_list를 담는다).
// GROUPBY_STATE — src/query/query_executor.c (excerpt)typedef struct groupby_state GROUPBY_STATE;struct groupby_state{ int state; SORTKEY_INFO key_info; QFILE_LIST_SCAN_ID *input_scan; QFILE_LIST_ID *output_file;
PRED_EXPR *having_pred; AGGREGATE_TYPE *g_output_agg_list; /* SELECT-list shape */ REGU_VARIABLE_LIST g_regu_list; /* fetch into db_value */ REGU_VARIABLE_LIST g_hk_regu_list; /* hash-key reguvars */ VAL_LIST *g_val_list; OUTPTR_LIST *g_outptr_list; XASL_NODE *xasl; XASL_STATE *xasl_state;
RECDES current_key; /* last seen group key */ RECDES gby_rec; QFILE_TUPLE_RECORD input_tpl; int input_recs;
bool with_rollup; GROUPBY_DIMENSION *g_dim; /* rollup levels */ int g_dim_levels;
int hash_eligible; AGGREGATE_HASH_CONTEXT *agg_hash_context; // ... condensed ...};XASL 생성기는 이 상태가 바인딩하는 BUILDLIST_PROC_NODE 위에
다섯 개의 리스트를 미리 짓는다. g_outptr_list(SELECT-list 모양,
사용자에게 보이는 형태), g_val_list(비-집계 컬럼과 집계
인자들, GROUP BY 순서 로 배치되며 SELECT-only 컬럼이 꼬리에
붙는다), g_regu_list(튜플 위치를 그 db_value들로 가져오는
reguvar들), g_agg_list(집계 함수마다 AGGREGATE_TYPE 노드 하나,
accumulator.value와 함수 인자를 함께 보유), 그리고 g_hk_sort_regu_list
(해시 키 reguvar — hash_eligible == true 일 때만 존재). 슬라이드
덱(Sort, Hash Group By.pptx, slide 2-7)은 GROUP-BY-순서와
SELECT-list-순서의 구분을 강조한다는 점이다. 처리 단계가 쓰는
입력 튜플들은 g_outptr_list의 GROUP BY 순서를 따르므로, 정렬
키는 각 튜플의 머리에서 곧장 읽혀 나온다는 점이 중요하다.
서브 리스트의 순서는 의도된 것이다. 덱의 예제 SELECT c1, c2, avg(c1) FROM t1 GROUP BY c2, c1은 SELECT-list가 (c1, c2, avg(c1))을 읽는데도 입력 리스트 파일은 (c2, c1, c1_arg) 모양
으로 만들어진다. g_outptr_list는 출력 합성을 위해 SELECT-list
모양을 보존하는 한편, 입력 리스트 파일은 GROUP BY 순서이므로
모든 튜플의 정렬 키 prefix가 정확히 그룹핑 벡터가 되도록 만든다.
Sort 기반 파이프라인
섹션 제목: “Sort 기반 파이프라인”qexec_groupby가 진입점이다. 이 함수는 GROUPBY_STATE를
할당하고 출력 리스트 파일을 연 뒤, 입력 리스트 파일을 두 콜백과
함께 sort_listfile에 넘긴다.
// qexec_groupby — src/query/query_executor.c (condensed)qexec_groupby (THREAD_ENTRY * thread_p, XASL_NODE * xasl, ...){ // ... condensed: late binding, grbynum init ... if (qexec_initialize_groupby_state (&gbstate, buildlist->groupby_list, ...) == NULL) GOTO_EXIT_ON_ERROR;
/* open output list file */ gbstate.output_file = qfile_open_list (thread_p, &output_type_list, ...);
/* quick-finalize escapes for empty input or pure hash-agg ... */
/* sort + aggregate: callback sandwich */ 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, ...) != NO_ERROR) GOTO_EXIT_ON_ERROR; // ... condensed ...}qexec_gby_get_next는 단순하다. 입력 리스트 스캔에서 다음 튜플을
당겨와 SORT_REC로 만들어 준다.
// qexec_gby_get_next — src/query/query_executor.cstatic SORT_STATUSqexec_gby_get_next (THREAD_ENTRY * thread_p, RECDES * recdes, void *arg){ GROUPBY_STATE *gbstate = (GROUPBY_STATE *) arg; return qfile_make_sort_key (thread_p, &gbstate->key_info, recdes, gbstate->input_scan, &gbstate->input_tpl);}집계가 실제로 일어나는 곳은 qexec_gby_put_next다. 정렬 모듈은
정렬된 레코드 하나마다(또는 SORT_DUP이 켜졌을 때는 중복 체인
하나마다) 이 콜백을 호출한다. 콜백은 레코드의 키를
gbstate->current_key와 비교해 다르면 직전 그룹을 마무리하고,
새 그룹을 시작하고, 새 튜플을 누산기 체인에 접어 넣는다는 점이다.
상태 기계 스케치는 다음과 같다.
stateDiagram-v2 [*] --> Initial : 정렬 시작 Initial --> StartGroup : 첫 sort_record\n(qexec_gby_start_group_dim) StartGroup --> Accumulating : qexec_gby_agg_tuple Accumulating --> Accumulating : 같은 키\n(qexec_gby_agg_tuple) Accumulating --> Finalize : 새 키\n(qexec_gby_finalize_group_dim) Finalize --> StartGroup : qexec_gby_start_group(0) Accumulating --> EndOfInput : 정렬 소진 EndOfInput --> Finalize : 마지막 그룹 Finalize --> [*]
실제 키 비교와 디멘전 워킹은 qexec_gby_finalize_group_dim 안에
들어 있다. 이 함수는 롤업을 인지하는 finalize 경로다.
// qexec_gby_finalize_group_dim — src/query/query_executor.c (condensed)static intqexec_gby_finalize_group_dim (THREAD_ENTRY * thread_p, GROUPBY_STATE * gbstate, const RECDES * recdes){ int i, j, nkeys, level = 0;
qexec_gby_finalize_group (thread_p, gbstate, 0, gbstate->with_rollup); if (gbstate->with_rollup && recdes) { SORT_REC *key = (SORT_REC *) recdes->data; level = gbstate->g_dim_levels; nkeys = gbstate->key_info.nkeys;
/* find the first key prefix that differs and finalize all * dimensions above that level */ for (i = 1; i < nkeys; i++) { gbstate->key_info.nkeys = i; if ((*gbstate->cmp_fn) (&gbstate->current_key.data, &key, &gbstate->key_info) != 0) { for (j = gbstate->g_dim_levels - 1; j > i; j--) { qexec_gby_finalize_group (thread_p, gbstate, j, true); qexec_gby_start_group (thread_p, gbstate, NULL, j); } level = i + 1; break; } } gbstate->key_info.nkeys = nkeys; }
qexec_gby_start_group (thread_p, gbstate, recdes, 0); return level;}비자명한 사실 두 가지가 있다. 첫째, 롤업 루프는 가장 깊은
디멘전부터 finalize 하면서 위로 거슬러 올라간다는 점이다. 즉
prefix c1은 그대로지만 (c1,c2)가 달라진 경우, (c1,c2,c3)과
(c1,c2)를 추적하던 디멘전은 finalize 되고 c1 단독 디멘전과
total 집계 디멘전은 열린 채로 유지된다. 덱의 GROUPBY_DIMENSION
슬라이드(Sort, Hash Group By.pptx, slide 24)는 이를 “독특한
점”이라고 부른다 — g_dim[0]이 가장 자세한 레벨(모든 GROUP BY
컬럼), g_dim[g_dim_levels-1]이 total 집계, 사이의 슬롯들이
롤업 prefix들이다. 둘째, 정렬 모듈의 nkeys 필드는 비교 루프
안에서 변경되어 prefix별 비교를 가능케 하며, 원래 값은 외부
정렬과의 일관성을 위해 저장 후 복원된다는 점이다.
qexec_gby_finalize_group 호출은 디멘전의 누산기를
gbstate->output_file로 덤프한다.
// qexec_gby_finalize_group — src/query/query_executor.c (condensed)static voidqexec_gby_finalize_group (THREAD_ENTRY * thread_p, GROUPBY_STATE * gbstate, int N, bool keep_list_file){ // ... condensed ... qdata_finalize_aggregate_list (thread_p, gbstate->g_dim[N].d_agg_list, keep_list_file, NULL);
/* move dimension's accumulators into g_output_agg_list */ AGGREGATE_TYPE *g_outp = gbstate->g_output_agg_list; AGGREGATE_TYPE *d_aggp = gbstate->g_dim[N].d_agg_list; while (g_outp != NULL && d_aggp != NULL) { if (g_outp->function != PT_GROUPBY_NUM && d_aggp->accumulator.value != NULL && g_outp->accumulator.value != NULL) { pr_clear_value (g_outp->accumulator.value); *g_outp->accumulator.value = *d_aggp->accumulator.value; PRIM_SET_NULL (d_aggp->accumulator.value); } g_outp = g_outp->next; d_aggp = d_aggp->next; }
/* HAVING + GROUP_BY_NUM evaluation */ if (gbstate->having_pred && eval_pred (thread_p, gbstate->having_pred, ...) != V_TRUE) goto wrapup;
/* compose output tuple via output pointer list and append */ qexec_generate_tuple_descriptor (thread_p, gbstate->output_file, gbstate->g_outptr_list, &xasl_state->vd); qfile_generate_tuple_into_list (thread_p, gbstate->output_file, T_NORMAL); // ... condensed ...}누산기-출력값 복사는 별칭(aliasing) 단축 을 사용한다 —
*g_outp->accumulator.value = *d_aggp->accumulator.value 다음
즉시 PRIM_SET_NULL로 디멘전 누산기를 비운다는 점이다. 이는
의도된 것이다. SELECT-list 모양의 g_output_agg_list는 자기
accumulator.value db_value들을 g_outptr_list의 reguvar들과
공유하므로, 튜플 생성 패스는 공유 포인터 덕분에 방금 finalize 된
집계값을 자연스럽게 집어 든다는 점이다. 덱(slide 16,
“g_agg_list->accumulator.value 는 g_output_list에서 공유되므로
…”)이 이 공유를 명시한다.
누산기 갱신 자체는 qexec_gby_put_next의 비-finalize 분기에서
qexec_gby_agg_tuple으로 일어난다.
// qexec_gby_agg_tuple — src/query/query_executor.cstatic voidqexec_gby_agg_tuple (THREAD_ENTRY * thread_p, GROUPBY_STATE * gbstate, QFILE_TUPLE tpl, int peek){ if (fetch_val_list (thread_p, gbstate->g_regu_list, &gbstate->xasl_state->vd, NULL, NULL, tpl, peek) != NO_ERROR) GOTO_EXIT_ON_ERROR;
for (int i = 0; i < gbstate->g_dim_levels; i++) { if (qdata_evaluate_aggregate_list (thread_p, gbstate->g_dim[i].d_agg_list, &gbstate->xasl_state->vd, NULL, false) != NO_ERROR) GOTO_EXIT_ON_ERROR; }}내부 루프는 모든 롤업 디멘전 을 돌며 같은 입력 튜플을 각각에
접어 넣는다 — 가장 자세한 디멘전과 모든 롤업 prefix에. query_aggregate.cpp에
정의된 qdata_evaluate_aggregate_list는 함수별 디스패치이며,
PT_MIN, PT_MAX, PT_SUM, PT_AVG, PT_COUNT 등을
별도의 내부 switch를 둔다. 덱(page 9)은 이 동작을 다음과 같이
요약한다 — PT_MIN/PT_MAX는 새 값이 진행 중인 극값을
넘으면 덮어쓴다. PT_AVG/PT_SUM은 첫 비-NULL 값에서 초기화
하고 이후 값을 더한다. PT_COUNT는 COUNT(*)이면 무조건
증가, COUNT(col)이면 비-NULL일 때만 증가한다.
그룹 키 전이: qexec_gby_start_group
섹션 제목: “그룹 키 전이: qexec_gby_start_group”새 키가 도착하면 qexec_gby_start_group이 그것을
gbstate->current_key로 기록하고 디멘전의 집계 리스트를
재초기화한다.
// qexec_gby_start_group — src/query/query_executor.c (condensed)static voidqexec_gby_start_group (THREAD_ENTRY * thread_p, GROUPBY_STATE * gbstate, const RECDES * recdes, int N){ if (N == 0 && recdes) { /* save key for later equality tests */ memcpy (gbstate->current_key.data, recdes->data, recdes->length); gbstate->current_key.length = recdes->length; } /* zero the accumulators of dimension N */ QEXEC_CLEAR_AGG_LIST_VALUE (gbstate->g_dim[N].d_agg_list); qdata_initialize_aggregate_list (thread_p, gbstate->g_dim[N].d_agg_list, gbstate->xasl_state->query_id);}N == 0(가장 자세한 디멘전)일 때만 키를 저장한다. 롤업 디멘전은
같은 키를 잘라낸 prefix 형태로 비교자가 계산해 주므로 키를 따로
저장할 필요가 없다.
Hash 기반 파이프라인
섹션 제목: “Hash 기반 파이프라인”hash_eligible == true일 때, 실행기는 처리 단계 도중
(즉 입력 튜플이 end_one_iteration에 도착하는 시점) AGGREGATE_HASH_CONTEXT를
세우고 튜플을 xasl->list_id에 도달하기 전에 qexec_hash_gby_agg_tuple로
보낸다. 후처리는 그 해시 테이블을 정리하는 단계가 된다.
// qexec_hash_gby_agg_tuple — src/query/query_executor.c (condensed)static intqexec_hash_gby_agg_tuple (THREAD_ENTRY * thread_p, XASL_NODE * xasl, XASL_STATE * xasl_state, BUILDLIST_PROC_NODE * proc, QFILE_TUPLE_RECORD * tplrec, QFILE_TUPLE_DESCRIPTOR * tpldesc, QFILE_LIST_ID * groupby_list, bool * output_tuple){ AGGREGATE_HASH_CONTEXT *context = proc->agg_hash_context; AGGREGATE_HASH_KEY *key = context->temp_key; AGGREGATE_HASH_VALUE *value;
if (context->state == HS_REJECT_ALL) return NO_ERROR; /* sort fallback engaged */
qexec_build_agg_hkey (thread_p, xasl_state, proc->g_hk_scan_regu_list, NULL, key); value = (AGGREGATE_HASH_VALUE *) mht_get (context->hash_table, (void *) key);
if (value == NULL) { /* new group: copy key, allocate accumulators, save first tuple */ AGGREGATE_HASH_KEY *new_key = qdata_copy_agg_hkey (thread_p, key); AGGREGATE_HASH_VALUE *new_value = qdata_alloc_agg_hvalue (thread_p, proc->g_func_count, proc->g_agg_list); // ... condensed: stash first tuple into new_value->first_tuple ... mht_put (context->hash_table, new_key, new_value); context->tuple_count++; context->group_count++; context->hash_size += qdata_get_agg_hkey_size (new_key); context->hash_size += qdata_get_agg_hvalue_size (new_value, false); } else { /* existing group: fold accumulators */ *output_tuple = false; value->tuple_count++; context->tuple_count++; qdata_evaluate_aggregate_list (thread_p, proc->g_agg_list, &xasl_state->vd, value->accumulators, false); context->hash_size += qdata_get_agg_hvalue_size (value, true); }
/* keep hash table within memory limit (LRU spill) */ while (context->hash_size > (int) mem_limit) { HENTRY_PTR hentry = context->hash_table->lru_head; key = (AGGREGATE_HASH_KEY *) hentry->key; value = (AGGREGATE_HASH_VALUE *) hentry->data; qdata_save_agg_hentry_to_list (thread_p, key, value, context->temp_dbval_array, context->part_list_id); if (value->first_tuple.tpl != NULL) qfile_add_tuple_to_list (thread_p, groupby_list, value->first_tuple.tpl); context->hash_size -= qdata_get_agg_hkey_size (key); context->hash_size -= qdata_get_agg_hvalue_size (value, false); mht_rem (context->hash_table, key, qdata_free_agg_hentry, NULL); }
/* very-high selectivity → bail to sort path */ if (context->tuple_count > HASH_AGGREGATE_VH_SELECTIVITY_TUPLE_THRESHOLD) { float selectivity = (float) context->group_count / context->tuple_count; if (selectivity > HASH_AGGREGATE_VH_SELECTIVITY_THRESHOLD) { context->state = HS_REJECT_ALL; qdata_save_agg_htable_to_list (thread_p, context->hash_table, groupby_list, context->part_list_id, context->temp_dbval_array); } } // ... condensed ...}이 함수는 덱이 다루는 두 가지 키 중복 사례(slides 18-20)를
구체화한다. 해시 테이블이 prm_get_bigint_value (PRM_ID_MAX_AGG_HASH_SIZE)
(기본 2 MB)를 넘으면 LRU 엔트리를 part_list_id로 spill 하고
제거한다는 점이다. 같은 키가 나중에 다시 삽입되는 것을 막는 장치가
없으므로, part_list_id는 같은 키에 대한 여러 엔트리를 가질 수
있고 각 엔트리는 이미 부분적으로 집계된 상태가 된다. 선택도
(groups / tuples)가 입력 튜플 2000개를 넘은 시점에 0.5를 초과하면,
실행기는 해시 전략이 거의 유일한 키들에 메모리를 낭비하고 있다고
결론짓고 state = HS_REJECT_ALL로 바꾼 뒤 전체 테이블을
part_list_id로 덤프한다. 그 시점부터 새 튜플은
xasl->list_id로 직접 쓰여 sort 기반 집계 경로를 탄다.
해시 경로의 후처리는 sort_listfile을 두 번 호출한다 — 한 번은
part_list_id(해시 오버플로) 위에서, 다음은 xasl->list_id
(sort 폴백) 위에서. 첫 번째 정렬은 정렬된 run 안에서 누산기를
병합하는 put 콜백 qexec_hash_gby_put_next를 사용한다.
// qexec_hash_gby_put_next — src/query/query_executor.c (condensed)static intqexec_hash_gby_put_next (THREAD_ENTRY * thread_p, const RECDES * recdes, void *arg){ GROUPBY_STATE *state = (GROUPBY_STATE *) arg; AGGREGATE_HASH_CONTEXT *context = state->agg_hash_context;
for (SORT_REC *key = (SORT_REC *) recdes->data; key; key = key->next) { // ... condensed: load (key, value) from sorted record ... qdata_load_agg_hentry_from_tuple (thread_p, data, context->temp_part_key, context->temp_part_value, ...);
if (qdata_agg_hkey_eq (context->curr_part_key, context->temp_part_key) && context->sorted_count > 0) { /* same key: fuse accumulators */ AGGREGATE_TYPE *agg_list = state->g_output_agg_list; int i = 0; while (agg_list != NULL) { qdata_aggregate_accumulator_to_accumulator ( thread_p, &context->curr_part_value->accumulators[i], &agg_list->accumulator_domain, agg_list->function, agg_list->domain, &context->temp_part_value->accumulators[i]); agg_list = agg_list->next; i++; } } else { /* different key: dump curr to sorted_part_list_id, swap */ if (context->sorted_count > 0) qdata_save_agg_hentry_to_list (thread_p, context->curr_part_key, context->curr_part_value, context->temp_dbval_array, context->sorted_part_list_id); /* swap (curr, temp) */ // ... condensed ... } context->sorted_count++; } return NO_ERROR;}여기서의 융합은 qdata_aggregate_accumulator_to_accumulator —
같은 키를 미리 집계된 두 값(예: 두 부분합)을 결합하는
연산이다. 이는 누산기를 원시 튜플 값과 결합하는
qdata_evaluate_aggregate_list의 해시-spill 짝꿍이다.
이 첫 번째 패스가 끝나면 sorted_part_list_id는 키마다 한 개의
튜플을 보유한다(병합된 누산기와 함께). 두 번째 패스는
xasl->list_id를 sort 기반 qexec_gby_put_next 기계를 그대로
재사용한다. 단 한 가지 추가는 qexec_locate_agg_hentry_in_list로
sorted_part_list_id로 교차 참조해, 키가 해시 측에 이미 가진
잔여 부분 집계를 집어 든다는 점이다.
WITH ROLLUP — 다중 디멘전 finalize
섹션 제목: “WITH ROLLUP — 다중 디멘전 finalize”GROUP BY ... WITH ROLLUP은 g_dim_levels = nkeys + 1 슬롯을
추가한다. qexec_gby_agg_tuple에서 입력 튜플마다 모든 디멘전에
접어 넣는다. 키 경계에서 qexec_gby_finalize_group_dim은
디멘전을 가장 깊은 것부터 거슬러 오르며 키 prefix가 바뀐
디멘전만 finalize 한다는 점이다. 덱의 GROUP BY c1, c2, c3 WITH ROLLUP 예제(page 19-21)는 (1,1,3)에서 (1,2,1)로 옮겨갈 때
가장 깊은 두 디멘전이 finalize 되고 (c1)과 total 디멘전은 계속
열려 있는 모습을 보여 준다.
미묘한 정합성 이슈가 CBRD-25611(deck slide 29)에서 드러난다.
SELECT-list에 ceil(c1) 같은 표현식이 있고, 그 표현식이 GROUP BY
순서상 c1 앞 위치에 놓이면, c1 컬럼을 NULL로 만드는 롤업
finalize가 그 NULL을 표현식으로도 전파해 버린다는 점이다. 수정안은
디멘전 플래그와 무관하게 원래(non-NULL) 값을 표현식 평가기까지
별도로 공급해야 한다.
분석 / 윈도우 함수
섹션 제목: “분석 / 윈도우 함수”윈도우 함수는 구조적으로 집계와 닮아 있다 — 둘 다 키로 정렬한 뒤
정렬된 스트림을 따라간다 — 다만 두 가지 점에서 다르다. 첫째,
모든 입력 튜플은 동시에 출력 튜플이기도 하다. 둘째, LAG,
LEAD, NTH_VALUE, MEDIAN, PERCENTILE_CONT 같은 일부 윈도우
함수는 같은 파티션 내 다른 튜플로의 임의 접근 을 필요로 한다는
점이다. CUBRID는 첫 번째 패스에서 분석 함수마다 두 개의 사이드카
리스트 파일을 작성하고, 두 번째 qexec_analytic_update_group_result
패스에서 이를 재스캔하는 방식으로 둘 다 처리한다.
상태 객체
섹션 제목: “상태 객체”// ANALYTIC_FUNCTION_STATE — src/query/query_executor.c (excerpt)struct analytic_function_state{ ANALYTIC_TYPE *func_p; RECDES current_key;
QFILE_LIST_ID *group_list_id; /* file containing group headers */ QFILE_LIST_ID *value_list_id; /* file containing group values */ QFILE_LIST_SCAN_ID group_scan_id; QFILE_LIST_SCAN_ID value_scan_id; QFILE_TUPLE_RECORD group_tplrec; QFILE_TUPLE_RECORD value_tplrec;
DB_VALUE cgtc_dbval, cgtc_nn_dbval, csktc_dbval; int curr_group_tuple_count; /* tuples in current group */ int curr_group_tuple_count_nn; /* tuples in current group, non-NULL */ int curr_sort_key_tuple_count; /* tuples sharing current sort key */
int group_tuple_position; /* scan position in current group */ int group_tuple_position_nn; /* same, ignoring NULL values */ int sort_key_tuple_position; /* scan position in current sort key */ int group_consumed_tuples; /* tuples already emitted */};설계의 핵심은 두 사이드카 리스트 파일이다. group_list_id는
파티션마다 (count, count_nn) 튜플 하나를 담는다. value_list_id는
파티션 안의 서로 다른 정렬 키마다 (sort_key_count, value) 튜플
하나를 담는다. 첫 번째 패스가 이 두 파일과 더불어 세 번째 파일을
만들어 낸다 — analytic_state->interm_file은 입력 리스트 파일에
숨겨진 컬럼을 추가한 것 으로, 재스캔 시 위치만으로 파티션 경계와
정렬 키 경계를 식별할 수 있게 해 준다는 점이다. 두 번째 패스는
interm_file을 선형으로 재읽고, group_list_id와 value_list_id
의 커서를 위치시키며, 입력 튜플마다 출력 튜플 하나씩을 내보낸다.
qexec_execute_analytic — 외부 루프
섹션 제목: “qexec_execute_analytic — 외부 루프”// qexec_execute_analytic — src/query/query_executor.c (condensed)qexec_execute_analytic (THREAD_ENTRY * thread_p, XASL_NODE * xasl, XASL_STATE * xasl_state, ANALYTIC_EVAL_TYPE * analytic_eval, ...){ // ... condensed: setup state, regulist domains, intermediate file ... qexec_initialize_analytic_state (thread_p, &analytic_state, analytic_eval->head, ...);
/* open intermediate and output files; intermediate carries * the input tuple shape plus hidden cols for partition/order tracking */ if (is_skip_sort) analytic_state.interm_file = list_id; else analytic_state.interm_file = qfile_open_list (thread_p, &interm_type_list, NULL, xasl_state->query_id, ls_flag, NULL);
/* open input scan + intermediate scan */ qfile_open_list_scan (list_id, &input_scan_id); qfile_open_list_scan (analytic_state.interm_file, &interm_scan_id);
if (is_skip_sort) { /* sort can be skipped if input arrived already sorted (planner) */ qexec_analytic_update_group_result (thread_p, &analytic_state); goto wrapup; }
/* sort + first-pass: writes interm_file, group_list_id, value_list_id */ estimated_pages = qfile_get_estimated_pages_for_sorting (list_id, &analytic_state.key_info); analytic_state.key_info.use_original = 1; analytic_state.cmp_fn = &qfile_compare_partial_sort_record;
if (sort_listfile (thread_p, NULL_VOLID, estimated_pages, &qexec_analytic_get_next, &analytic_state, &qexec_analytic_put_next, &analytic_state, analytic_state.cmp_fn, &analytic_state.key_info, SORT_DUP, NO_SORT_LIMIT, ..., SORT_ANALYTIC) != NO_ERROR) GOTO_EXIT_ON_ERROR;
/* finalize trailing groups (sort_listfile has no terminate hook) */ if (analytic_state.input_recs != 0) { for (i = 0; i < analytic_state.func_count; i++) qexec_analytic_finalize_group (thread_p, analytic_state.xasl_state, &analytic_state.func_state_list[i], false);
/* second pass: re-scan interm_file, position sidecars, emit output */ qexec_analytic_update_group_result (thread_p, &analytic_state); } // ... condensed ...}드라이버는 서로 다른 정렬 리스트마다 한 번씩 호출된다는 점이
중요하다. 질의 파서는 같은 (PARTITION BY, ORDER BY)를 공유하는
윈도우 함수들을 하나의 ANALYTIC_EVAL_TYPE으로 묶으므로,
업스트림 파스 트리 패스인 pt_optimize_analytic_list가 정렬 패스
수를 최소화해 둔다. 덱의 예제 — max(c3) over (partition by c1 order by c2), rank() over (order by c1), min(c3) over (order by c2) — 는 정렬 패스 두 번이 된다. 앞 두 함수에는 (c1,c2)로
정렬, 세 번째 함수에는 c2로 정렬.
첫 번째 패스: qexec_analytic_put_next
섹션 제목: “첫 번째 패스: qexec_analytic_put_next”flowchart TD
A["sort_record가 qexec_analytic_put_next에 도착"]
B{"current_key가 NULL?\n(첫 레코드)"}
C["start_group(reinit=true)\n모든 함수에 대해"]
D{"키가 current_key와 일치?\n(전체 sort_list_size)"}
E["KEEP_RANK; 계속"]
F{"sort_prefix_size == 0?\n(PARTITION BY 없음)"}
G{"키가 current_key와 일치?\n(prefix만)"}
H["finalize_group(is_same_group=true)\nstart_group(reinit=false)"]
I["finalize_group(is_same_group=false)\nstart_group(reinit=true)"]
J["qexec_analytic_add_tuple\n(모든 함수에 대해)"]
A --> B
B -- 예 --> C --> J
B -- 아니오 --> D
D -- 예 --> E --> J
D -- 아니오 --> F
F -- 예 (파티션 없음) --> H
F -- 아니오 --> G
G -- 예 (같은 파티션) --> H
G -- 아니오 --> I
H --> J
I --> J
두 단계 비교 — 먼저 전체 정렬 키, 불일치 시 prefix만 — 가
파티션 vs. 정렬의 구분이다. qexec_analytic_put_next(deck page 4)의
내부 루프는 analytic_state->key_info.nkeys를 변경해
func_p->sort_list_size(전체 키, partition + order)와
func_p->sort_prefix_size(PARTITION BY 컬럼만) 사이를 오간다.
// qexec_analytic_put_next — src/query/query_executor.c (condensed)static intqexec_analytic_put_next (THREAD_ENTRY * thread_p, const RECDES * recdes, void *arg){ ANALYTIC_STATE *analytic_state = (ANALYTIC_STATE *) arg; // ... condensed: load original tuple from sort key page ...
if (analytic_state->input_recs == 0) { /* first record: start every function */ for (i = 0; i < analytic_state->func_count; i++) qexec_analytic_start_group (thread_p, analytic_state->xasl_state, &analytic_state->func_state_list[i], recdes, /*reinit=*/true); } else { for (i = 0; i < analytic_state->func_count; i++) { ANALYTIC_FUNCTION_STATE *func_state = &analytic_state->func_state_list[i]; bool is_same_group = false;
/* compare full sort key */ int nkeys = analytic_state->key_info.nkeys; analytic_state->key_info.nkeys = func_state->func_p->sort_list_size; if (((*analytic_state->cmp_fn) (&func_state->current_key.data, &key, &analytic_state->key_info) == 0) || analytic_state->key_info.nkeys == 0) { analytic_state->key_info.nkeys = nkeys; ANALYTIC_FUNC_SET_FLAG (func_state->func_p, ANALYTIC_KEEP_RANK); if (QPROC_ANALYTIC_IS_OFFSET_FUNCTION (func_state->func_p)) is_same_group = true; /* offset funcs need per-tuple distinct */ else continue; /* same sort key, no work */ } analytic_state->key_info.nkeys = nkeys;
/* compare prefix only */ if (!is_same_group) { if (func_state->func_p->sort_prefix_size == 0) is_same_group = true; else { nkeys = analytic_state->key_info.nkeys; analytic_state->key_info.nkeys = func_state->func_p->sort_prefix_size; if ((*analytic_state->cmp_fn) (&func_state->current_key.data, &key, &analytic_state->key_info) == 0) is_same_group = true; analytic_state->key_info.nkeys = nkeys; } }
if (!is_same_group) { /* partition boundary */ qexec_analytic_finalize_group (thread_p, analytic_state->xasl_state, func_state, /*is_same_group=*/false); pr_clear_value (func_state->func_p->value); qexec_analytic_start_group (thread_p, analytic_state->xasl_state, func_state, recdes, /*reinit=*/true); } else if (...) { /* sort-key boundary (within partition) */ qexec_analytic_finalize_group (thread_p, analytic_state->xasl_state, func_state, /*is_same_group=*/true); qexec_analytic_start_group (thread_p, analytic_state->xasl_state, func_state, recdes, /*reinit=*/false); } } }
qexec_analytic_add_tuple (thread_p, analytic_state, data, peek); analytic_state->input_recs++;}start_group의 두 인자 의미가 중요하다. reinit=true는 “새
파티션, 누산기와 카운터를 처음부터 리셋”이고, reinit=false는
“같은 파티션 안인데 새 정렬 키이므로, 부분값을 살리고 정렬 키
카운터만 리셋”이다. 덱의 qexec_analytic_start_group 슬라이드
(page 4)가 두 케이스를 대비해 설명한다.
함수별 상태 기계
섹션 제목: “함수별 상태 기계”stateDiagram-v2 [*] --> Initial : 정렬 시작 Initial --> NewPartition : 첫 레코드\nstart_group(reinit=true) NewPartition --> SameSortKey : add_tuple SameSortKey --> SameSortKey : 같은 정렬 키\nadd_tuple SameSortKey --> NewSortKey : 정렬 키 변경\n(파티션 안에서) NewSortKey --> NewPartitionFinalize : 파티션 prefix 변경 NewPartitionFinalize --> NewPartition : finalize(is_same_group=false)\nstart_group(reinit=true) NewSortKey --> SameSortKey : finalize(is_same_group=true)\nstart_group(reinit=false)\nadd_tuple SameSortKey --> EOI : 정렬 소진 EOI --> FinalFinalize : 마지막 그룹 finalize FinalFinalize --> SecondPass : update_group_result SecondPass --> [*]
qexec_analytic_finalize_group은 두 사이드카 리스트 파일에 각각
튜플 하나씩을 쓴다.
// qexec_analytic_finalize_group — src/query/query_executor.c (condensed)static intqexec_analytic_finalize_group (THREAD_ENTRY * thread_p, XASL_STATE * xasl_state, ANALYTIC_FUNCTION_STATE * func_state, bool is_same_group){ /* compute the function's final value for the just-closed sort-key range */ qdata_finalize_analytic_func (thread_p, func_state->func_p, is_same_group);
if (!DB_IS_NULL (func_state->func_p->value)) func_state->curr_group_tuple_count_nn += func_state->curr_sort_key_tuple_count;
/* group_list_id gets one (count, count_nn) tuple per partition */ if (!is_same_group) qfile_fast_intint_tuple_to_list (thread_p, func_state->group_list_id, func_state->curr_group_tuple_count, func_state->curr_group_tuple_count_nn);
/* value_list_id gets one (sort_key_count, value) tuple per distinct sort key */ qfile_fast_intval_tuple_to_list (thread_p, func_state->value_list_id, func_state->curr_sort_key_tuple_count, func_state->func_p->value); // ... condensed ...}첫 패스의 출력(interm_file + group_list_id + value_list_id)은 두 번째 패스가 모든 입력 튜플을 각 함수의 출력 컬럼을 재구성 하기에 충분한 정보다.
두 번째 패스: qexec_analytic_update_group_result
섹션 제목: “두 번째 패스: qexec_analytic_update_group_result”이 패스는 중간 파일을 선형으로 재읽는다. 각 튜플을, 각 윈도우
함수를, 사이드카 파일의 커서를 진행시키고 튜플별 출력값을
계산한다. 커서 진행은 qexec_analytic_value_advance(정렬 키
리스트를 앞·뒤로 탐색하면서 그룹 리스트로 파티션 헤더를 추적)와
qexec_analytic_value_lookup(현재 파티션 내 특정 위치로의 임의
접근)에서 구현된다.
// qexec_analytic_update_group_result — src/query/query_executor.c (condensed)static intqexec_analytic_update_group_result (THREAD_ENTRY * thread_p, ANALYTIC_STATE * analytic_state){ // ... condensed: open scans on group_list_id, value_list_id, interm_file ...
while ((sc = qfile_scan_list_next (thread_p, &interm_scan_id, &tplrec_scan, PEEK)) == S_SUCCESS) { fetch_val_list (thread_p, analytic_state->a_regu_list, &xasl_state->vd, ...); qexec_analytic_eval_instnum_pred (thread_p, analytic_state, stage);
for (i = 0; i < analytic_state->func_count; i++) { ANALYTIC_FUNCTION_STATE *func_state = &analytic_state->func_state_list[i]; ANALYTIC_TYPE *func_p = func_state->func_p;
if (func_p->function == PT_ROW_NUMBER) ; /* already computed in first pass; nothing to do */ else if (QPROC_ANALYTIC_IS_OFFSET_FUNCTION (func_p)) { if (func_state->group_tuple_position == -1) qexec_analytic_value_advance (thread_p, func_state, 1, 1, ignore_nulls); else if (func_state->group_consumed_tuples >= func_state->curr_group_tuple_count) { qexec_analytic_group_header_next (thread_p, func_state); func_state->group_consumed_tuples = 0; } } else if (QPROC_IS_INTERPOLATION_FUNC (func_p)) { if (func_state->group_consumed_tuples >= func_state->curr_group_tuple_count) { qexec_analytic_group_header_next (thread_p, func_state); func_state->group_consumed_tuples = 0; } } else qexec_analytic_value_advance (thread_p, func_state, 1, 1, ignore_nulls);
/* function-specific evaluation */ switch (func_p->function) { case PT_LEAD: case PT_LAG: case PT_NTH_VALUE: qexec_analytic_evaluate_offset_function (thread_p, func_state, analytic_state); break; case PT_NTILE: qexec_analytic_evaluate_ntile_function (thread_p, func_state); break; case PT_CUME_DIST: case PT_PERCENT_RANK: qexec_analytic_evaluate_cume_dist_percent_rank_function (thread_p, func_state); break; case PT_MEDIAN: case PT_PERCENTILE_CONT: case PT_PERCENTILE_DISC: qexec_analytic_evaluate_interpolation_function (thread_p, func_state); break; }
func_state->group_consumed_tuples++; }
if (analytic_state->is_output_rec) qexec_insert_tuple_into_list (thread_p, analytic_state->output_file, analytic_state->a_outptr_list, &xasl_state->vd, &tplrec_write); } // ... condensed: cleanup ...}오프셋 함수: LEAD, LAG, NTH_VALUE
섹션 제목: “오프셋 함수: LEAD, LAG, NTH_VALUE”오프셋 평가기는 오프셋 인자를 파티션 안의 목표 위치로 변환한 뒤
qexec_analytic_value_lookup으로 정렬 키 사이드카에서 그
값을 읽는다.
// qexec_analytic_evaluate_offset_function — src/query/query_executor.c (condensed)static intqexec_analytic_evaluate_offset_function (THREAD_ENTRY * thread_p, ANALYTIC_FUNCTION_STATE * func_state, ANALYTIC_STATE * analytic_state){ // ... condensed: locate offset reguvar, read its int value ...
switch (func_p->function) { case PT_LEAD: target_idx = func_state->group_consumed_tuples + offset; break; case PT_LAG: target_idx = func_state->group_consumed_tuples - offset; break; case PT_NTH_VALUE: // ... condensed: cast to double, validate range ... target_idx = (int) floor (nth_idx) - 1; if (func_p->from_last) target_idx = group_tuple_count - target_idx; break; }
if (target_idx >= 0 && target_idx < group_tuple_count) qexec_analytic_value_lookup (thread_p, func_state, target_idx, func_p->ignore_nulls); else put_default = true; /* off the end → default value */
if (put_default) { pr_clear_value (func_p->value); pr_clone_value (default_val_coerced, func_p->value); } return error;}덱(page 8-13)은 네 개의 튜플에 대한 LAG(c2, 1)을 자세히
따라가며 보여 준다. group_consumed_tuples가 출력 튜플마다
어떻게 진행되는지, group_list_id가 lookup의 경계로 쓰는 파티션
카디널리티를 어떻게 제공하는지, target index가 범위를 벗어났을 때
default 값이 어떻게 폴백 되는지를 보여 준다.
보간 함수: MEDIAN, PERCENTILE_CONT, PERCENTILE_DISC
섹션 제목: “보간 함수: MEDIAN, PERCENTILE_CONT, PERCENTILE_DISC”이 함수들은 파티션 안의 분수 위치(fractional position) 의 값을 읽어야 한다. 평가기는 목표의 floor와 ceiling 위치를 계산해 중간 행이 홀수면 가운데 행을 고르고, 짝수면 두 가운데 행 사이를 보간한다.
// qexec_analytic_evaluate_interpolation_function — src/query/query_executor.c (condensed)static intqexec_analytic_evaluate_interpolation_function (THREAD_ENTRY * thread_p, ANALYTIC_FUNCTION_STATE * func_state){ ANALYTIC_TYPE *func_p = func_state->func_p;
/* MEDIAN/PERCENTILE evaluated only at start of group; later tuples reuse */ if (func_state->group_tuple_position_nn > 0) return NO_ERROR; if (func_p->is_const_operand) return NO_ERROR; if (func_state->curr_group_tuple_count_nn == 0) return NO_ERROR;
if (func_p->function == PT_MEDIAN) percentile_d = 0.5; else { // ... condensed: fetch percentile reguvar, validate ... percentile_d = db_get_double (peek_value_p); if (func_p->function == PT_PERCENTILE_DISC) percentile_d = ceil (percentile_d * func_state->curr_group_tuple_count_nn) / func_state->curr_group_tuple_count_nn; }
row_num_d = ((double) (func_state->curr_group_tuple_count_nn - 1)) * percentile_d; f_row_num_d = floor (row_num_d); c_row_num_d = (func_p->function == PT_PERCENTILE_DISC) ? f_row_num_d : ceil (row_num_d);
if (f_row_num_d == c_row_num_d) { qexec_analytic_value_lookup (thread_p, func_state, (int) f_row_num_d, true); qdata_apply_interpolation_function_coercion (func_p->value, &func_p->domain, func_p->value, func_p->function); } else { DB_VALUE c_value, f_value; qexec_analytic_value_lookup (thread_p, func_state, (int) f_row_num_d, true); pr_clone_value (func_p->value, &f_value); qexec_analytic_value_lookup (thread_p, func_state, (int) c_row_num_d, true); pr_clone_value (func_p->value, &c_value); qdata_interpolation_function_values (&f_value, &c_value, row_num_d, f_row_num_d, c_row_num_d, &func_p->domain, func_p->value, func_p->function); } return NO_ERROR;}group_tuple_position_nn > 0 → 즉시 return 가드는 median이
파티션마다 한 번 만 계산됨을 의미한다. 첫 비-NULL 튜플에서
계산한 뒤, 그 파티션의 모든 후속 튜플은 그 값을 재사용한다는
점이다. 따라서 덱의 노트 — 파티션 c1=1의 모든 행이 같은
median(c2) 값을 받는다는 점(page 18: “동일 그룹 내 다른 튜플을
처리하는 경우, 이미 계산된 중간 값을 재사용”) — 이 그대로 성립
한다.
위치 내비게이션: qexec_analytic_value_advance
섹션 제목: “위치 내비게이션: qexec_analytic_value_advance”이 루틴은 두 사이드카 리스트 파일을 일관되게 앞뒤로 이동시킨다.
// qexec_analytic_value_advance — src/query/query_executor.c (condensed)static intqexec_analytic_value_advance (THREAD_ENTRY * thread_p, ANALYTIC_FUNCTION_STATE * func_state, int amount, int max_group_changes, bool ignore_nulls){ while (sc == S_SUCCESS && amount != 0) { /* clamp to group end if max_group_changes <= 0 */ if (amount > 0) { if (max_group_changes <= 0 && func_state->group_tuple_position >= func_state->curr_group_tuple_count - 1) break; func_state->sort_key_tuple_position++; func_state->group_tuple_position++; } else { /* symmetric for backward */ }
/* sort-key boundary: load adjacent sort-key header */ if (func_state->sort_key_tuple_position < 0) { qfile_scan_list_prev (thread_p, &func_state->value_scan_id, ...); qexec_analytic_sort_key_header_load (func_state, ...); func_state->sort_key_tuple_position = func_state->curr_sort_key_tuple_count - 1; } else if (func_state->sort_key_tuple_position >= func_state->curr_sort_key_tuple_count) { qfile_scan_list_next (thread_p, &func_state->value_scan_id, ...); qexec_analytic_sort_key_header_load (func_state, ...); func_state->sort_key_tuple_position = 0; }
/* group boundary: load adjacent group header */ if (func_state->group_tuple_position < 0) { /* prev group */ max_group_changes--; } else if (func_state->group_tuple_position >= func_state->curr_group_tuple_count) { /* next group */ max_group_changes--; }
/* adjust amount: if ignore_nulls, only non-NULL counts */ if (amount > 0) amount -= (DB_IS_NULL (func_p->value) && ignore_nulls) ? 0 : 1; else amount += (DB_IS_NULL (func_p->value) && ignore_nulls) ? 0 : 1; }
if (amount != 0) { if (func_state->curr_group_tuple_count_nn == 0 && ignore_nulls) return NO_ERROR; /* all-NULL group → result is NULL */ return ER_FAILED; /* genuine miss */ } return NO_ERROR;}두 상태 기계가 동기화 되어 함께 도는 모양이다 — 정렬 키 커서와
그룹 커서, 각자 자기 backing 리스트 파일과 자기 위치 카운터를
가진다. max_group_changes 인자는 파티션 경계를 가로지를 수
있는 예산이다(0 = 현재 그룹 안에 머무름, 1 = 한 번까지 경계
넘김, qexec_analytic_group_header_next에서 사용).
qexec_analytic_value_lookup — 임의 접근
섹션 제목: “qexec_analytic_value_lookup — 임의 접근”// qexec_analytic_value_lookup — src/query/query_executor.c (condensed)static intqexec_analytic_value_lookup (THREAD_ENTRY * thread_p, ANALYTIC_FUNCTION_STATE * func_state, int position, bool ignore_nulls){ int offset = position - (ignore_nulls ? func_state->group_tuple_position_nn : func_state->group_tuple_position); if (offset != 0) return qexec_analytic_value_advance (thread_p, func_state, offset, 0, ignore_nulls);
return qexec_analytic_sort_key_header_load (func_state, true);}이는 오프셋 평가기와 보간 평가기가 사용하는 상대 위치 지정 래퍼
다. 현재 위치에서 델타를 계산해 qexec_analytic_value_advance를
max_group_changes = 0(파티션 횡단 금지)으로 호출한다.
Sort vs Hash GROUP BY — 전략 선택과 spill
섹션 제목: “Sort vs Hash GROUP BY — 전략 선택과 spill”sort/hash 결정은 세 층으로 이루어진다. 그 중 plan 시점에 확정되는 것은 첫 번째 한 층뿐이다.
-
Plan 시점 적격성(eligibility): XASL 생성기가 GROUP BY가 해싱에 적합할 때
BUILDLIST_PROC_NODE::g_hash_eligible을 세운다. 주된 기준은 비결정적 집계가 없을 것과 동등 비교 기반 키 추출이 가능할 것이다. 이는qexec_initialize_groupby_state에서GROUPBY_STATE::hash_eligible로 전파된다. -
런타임 메모리 상한: 처리 단계 도중
qexec_hash_gby_agg_tuple은context->hash_size(키 크기 + 누산기 크기의 총합)를 추적한다. 이 값이prm_get_bigint_value (PRM_ID_MAX_AGG_HASH_SIZE)(기본 2 MB)를 넘으면 해시 테이블의 LRU 헤드가part_list_id로 evict 된다는 점이다. 이는 전략을 바꾸지는 않는다. 워킹 셋만 잘라낸다. -
런타임 선택도 기반 폴백:
HASH_AGGREGATE_VH_SELECTIVITY_TUPLE_THRESHOLD = 2000개 튜플이 처리된 시점에 실행기는group_count / tuple_count > HASH_AGGREGATE_VH_SELECTIVITY_THRESHOLD = 0.5f을 검사한다. 비율이 너무 높으면(해시 테이블이 거의 유일한 키들로 차 있다는 뜻이면)state가HS_REJECT_ALL로 바뀌고, 전체 테이블은qdata_save_agg_htable_to_list로part_list_id로 덤프되며, 그 시점부터 새 입력 튜플은 모두xasl->list_id에 직접 쓰여 sort 기반 집계 경로를 탄다.
flowchart TD
START["end_one_iteration\n튜플을 받음"]
ELIG{"hash_eligible &&\nstate != HS_REJECT_ALL?"}
HKEY["해시 키 빌드\n(qexec_build_agg_hkey)"]
PROBE{"키가 hash_table에 있나?"}
NEW["해시 엔트리 할당\nfirst_tuple 보관"]
FOLD["누산기에 접기\n(qdata_evaluate_aggregate_list)"]
MEM{"hash_size > MAX_AGG_HASH_SIZE?"}
EVICT["LRU 헤드를 part_list_id로 spill\nhash_size 감소"]
SEL{"tuple_count > 2000?"}
RATIO{"group_count/tuple_count > 0.5?"}
REJECT["state = HS_REJECT_ALL\nqdata_save_agg_htable_to_list\n→ part_list_id"]
SORT["xasl->list_id에 튜플 기록\n(sort 경로)"]
POST["후처리"]
START --> ELIG
ELIG -- 아니오 --> SORT
ELIG -- 예 --> HKEY --> PROBE
PROBE -- 아니오 --> NEW --> MEM
PROBE -- 예 --> FOLD --> MEM
MEM -- 예 --> EVICT --> SEL
MEM -- 아니오 --> SEL
SEL -- 아니오 --> POST
SEL -- 예 --> RATIO
RATIO -- 아니오 --> POST
RATIO -- 예 --> REJECT --> SORT
SORT --> POST
Hash 경로의 후처리
섹션 제목: “Hash 경로의 후처리”해시 경로 위에서도 후처리는 거의 항상 정렬을 한다.
qexec_groupby는 상태를 살펴보고 다음 세 가지 모양 중 하나를
고른다.
-
순수 hash, sort-skip:
xasl->list_id->tuple_cnt == 0,agg_hash_context->part_list_id->tuple_cnt == 0, 그리고PRM_ID_AGG_HASH_RESPECT_ORDER == false인 경우.qexec_groupby의 조기-탈출 분기가 인메모리 해시 테이블을 순회하며 엔트리당 출력 튜플 한 개를 직접 내보낸다. 정렬은 없다.sort_listfile을 완전히 우회하는 유일한 경로다. -
Spill 동반 hash:
part_list_id가 비어 있지 않은 경우(LRU eviction이 일어났거나, 매우 높은 선택도로 폴백이 발동되었거나). 실행기는 키별 부분 누산기를 병합하기 위해part_list_id를 정렬하고(qexec_hash_gby_put_next사용), 그 다음 병합된 부분 리스트로의 교차 참조와 함께xasl->list_id를 정렬한다 (qexec_gby_put_next사용).sort_listfile호출 두 번이며, 순수 sort 기반 GROUP BY와 같은 콜백 기반이다. -
Sort 폴백:
state == HS_REJECT_ALL인 경우. 케이스 2와 동일하다.xasl->list_id는 폴백 이후의 튜플들을,part_list_id는 덤프된 해시 테이블을 보유한다.
덱(page 23)은 sort-skip 최적화의 정확한 조건을 나열한다 —
hash group by, WITH ROLLUP 없음, agg_hash_respect_order == no, 그리고 처리 단계에서 spill이 일어나지 않았을 것.
외부 정렬 기반
섹션 제목: “외부 정렬 기반”qexec_groupby나 qexec_execute_analytic이 sort_listfile을
호출할 때, 실제 정렬은 src/storage/external_sort.c에 살고 있다.
// sort_listfile — src/storage/external_sort.c (condensed)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, ..., SORT_PARALLEL_TYPE parallel_type){ SORT_PARAM ori_sort_param; SORT_PARAM *sort_param = &ori_sort_param; // ... condensed: copy callbacks into sort_param ... sort_param->limit = limit;
/* sort buffer sized by PRM_ID_SR_NBUFFERS (default), capped at input estimate */ 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);
/* temp file count derived from buffer/input ratio; runs go into half_files */ sort_param->half_files = sort_get_num_half_tmpfiles (sort_param->tot_buffers, input_pages); sort_param->tot_tempfiles = sort_param->half_files << 1;
/* main loop: in-phase (run generation) → ex-phase (k-way merge) */ // ... condensed ...}정렬 버퍼 크기는 PRM_ID_SR_NBUFFERS 페이지(기본값은 시점에
따라 다르므로 소스를 확인) 중 하나다. 입력이
tot_buffers * DB_PAGESIZE 메모리에 들어맞으면 정렬은 순수
인메모리로 끝난다. 그렇지 않으면 정렬된 run을 임시 파일에 쓰고
그것들을 머지한다는 점이다. parallel_type 인자는 직렬과 병렬
정렬 변종 사이의 라우팅을 결정한다 — SORT_ANALYTIC과 디폴트
모드는 병렬 정렬 스케줄러로 보낼 힌트가 있다.
비자명한 상호작용 한 가지가 있다. sort_listfile은 “정렬 끝
났으니 마무리 해 달라”는 후크를 갖고 있지 않다. 그래서
qexec_gby_finalize_group_dim과 qexec_execute_analytic은
sort_listfile이 반환된 뒤 에 마지막 그룹을 수동으로 finalize
해야 한다. qexec_execute_analytic에서 sort_listfile 다음에
오는 루프가 정확히 이 후처리다.
// trailing finalize after sort_listfile (qexec_execute_analytic excerpt)if (analytic_state.input_recs != 0) { for (i = 0; i < analytic_state.func_count; i++) qexec_analytic_finalize_group (thread_p, analytic_state.xasl_state, &analytic_state.func_state_list[i], false); qexec_analytic_update_group_result (thread_p, &analytic_state); }GROUP BY 측에도 같은 invariant가 적용된다. qexec_gby_put_next
내부의 finalize-before-start 순서는 키 전이가 일어났을 때만
발화하므로, 마지막 그룹은 sort_listfile 이후의 정리 단계까지
flush 되지 않은 상태로 남는다는 점이다.
소스 코드 가이드
섹션 제목: “소스 코드 가이드”심볼 이름 을 앵커로 삼는다. 라인 번호는 문서의
updated:시점으로 한정된 힌트일 뿐이다.
집계 / GROUP BY
섹션 제목: “집계 / GROUP BY”드라이버와 상태:
qexec_groupby— 최상위 GROUP BY 진입점.GROUPBY_STATE를 할당하고, 출력 리스트를 열고, sort 콜백과 함께sort_listfile을 호출.GROUPBY_STATE(query_executor.c:213) — 질의별 상태.GROUPBY_DIMENSION(query_executor.c:206) — 롤업 레벨별 슬롯, 자기 집계 리스트를 보유.GROUPBY_DIMENSION_FLAG—GROUP_BY,ROLLUP,CUBE,SET.qexec_initialize_groupby_state— 상태 초기화 및 적격 시 해시 컨텍스트 바인딩.qexec_clear_groupby_state— 정리.qexec_gby_init_group_dim— 디멘전 배열 할당 (g_dim_levels = with_rollup ? nkeys + 1 : 1).
Sort 기반 경로:
qexec_gby_get_next— sortget_fn. 입력 리스트 튜플을SORT_REC으로 변환.qexec_gby_put_next— sortput_fn. 체인된SORT_REC리스트를 순회하며, 키 전이에 따라start_group/agg_tuple/finalize_group_dim을 디스패치.qexec_gby_start_group_dim— 첫 레코드에서 모든 디멘전을 시작.qexec_gby_start_group— 새 키 기록, 한 디멘전의 누산기 영점 복원.qexec_gby_agg_tuple— 현재 입력 튜플을 모든 디멘전의 누산기 체인에 접어 넣음.qexec_gby_finalize_group_dim— 롤업을 인지하는 키 prefix 비교. prefix가 바뀐 디멘전을 모두 finalize.qexec_gby_finalize_group— 주어진 디멘전에서 출력 튜플 한 개를 emit.HAVING과GROUP_BY_NUM평가.qexec_gby_finalize_group_val_list— 롤업으로 떨어져 나간 컬럼들을 NULL로 만듦.
Hash 경로:
qexec_hash_gby_agg_tuple— 처리 단계 측 해시 insert/probe. LRU spill, 매우 높은 선택도 폴백.qexec_hash_gby_get_next—part_list_id용 sortget_fn.qexec_hash_gby_put_next— sortput_fn. 동일 키 run 안에서 누산기 병합.qexec_alloc_agg_hash_context/qexec_alloc_agg_hash_context_buildlist_xasl— 해시 컨텍스트 할당과 초기화.qexec_free_agg_hash_context— 정리.qexec_build_agg_hkey— 현재 reguvar들로부터AGGREGATE_HASH_KEY를 채움.qexec_locate_agg_hentry_in_list— 두 번째 hash-path 정렬 도중sorted_part_list_id에서 키를 스캔.
집계 평가 헬퍼(query_aggregate.cpp):
qdata_evaluate_aggregate_list— 한 튜플을AGGREGATE_TYPE체인에 접어 넣음(함수별 디스패치).qdata_initialize_aggregate_list— 그룹 시작 시 체인 영점화.qdata_finalize_aggregate_list— 체인 마감(예:AVG의 나누기).qdata_aggregate_accumulator_to_accumulator— 두 누산기 병합 (해시-spill 통합 시 사용).qdata_alloc_agg_hvalue/qdata_free_agg_hvalue— 해시 컨텍스트 안의 누산기 저장소.qdata_save_agg_hentry_to_list— (key, value) 엔트리 하나를part_list_id에 기록.qdata_save_agg_htable_to_list— 선택도 폴백 시 해시 테이블 일괄 덤프.qdata_load_agg_hentry_from_tuple— 정렬된 부분 리스트 튜플 에서 (key, value)를 복원.
분석 / 윈도우 함수
섹션 제목: “분석 / 윈도우 함수”드라이버와 상태:
qexec_execute_analytic— 최상위 분석 진입점. 공유 정렬 리스트마다 한 번씩 호출.ANALYTIC_STATE(query_executor.c:288) — 질의별 상태.ANALYTIC_FUNCTION_STATE(query_executor.c:259) — 함수별 상태. 두 사이드카 리스트 파일을 보유.qexec_initialize_analytic_state— 상태와 함수별 하위 상태를 초기화.qexec_initialize_analytic_function_state— 단일ANALYTIC_FUNCTION_STATE빌더.qexec_clear_analytic_state— 정리.
첫 번째 패스(정렬 + 상태 갱신):
qexec_analytic_get_next— sortget_fn.qexec_analytic_put_next— sortput_fn. 파티션/정렬-키 상태 기계.qexec_analytic_start_group— 키 기록, 새 파티션이면 누산기 재초기화, 같은 파티션이면 정렬-키 카운터만 재초기화.qexec_analytic_add_tuple— 현재 튜플을 모든 함수의 누산기와interm_file에 push.qexec_analytic_finalize_group—group_list_id에 (group_count, group_count_nn) 튜플 하나,value_list_id에 (sort_key_count, value) 튜플 하나를 emit.qexec_analytic_eval_instnum_pred— 적절한 단계에서INST_NUM()평가.
두 번째 패스(출력 재조립):
qexec_analytic_update_group_result—interm_file을 재스캔, 커서 위치 지정, 함수별 평가기 디스패치, 출력 기록.qexec_analytic_value_advance— 그룹 경계 추적과 함께 정렬 키 사이드카를 양방향 탐색.qexec_analytic_value_lookup— 현재 파티션 내 위치로의 임의 접근.qexec_analytic_group_header_next— 다음 파티션으로 이동.qexec_analytic_group_header_load/qexec_analytic_sort_key_header_load— 사이드카 헤더를func_state카운터로 역직렬화.
함수별 평가기:
qexec_analytic_evaluate_offset_function—LEAD,LAG,NTH_VALUE.qexec_analytic_evaluate_ntile_function—NTILE.qexec_analytic_evaluate_cume_dist_percent_rank_function—CUME_DIST,PERCENT_RANK.qexec_analytic_evaluate_interpolation_function—MEDIAN,PERCENTILE_CONT,PERCENTILE_DISC.qexec_analytic_eval_in_processing— 처리 단계 도중에 값을 계산 가능한 분석 함수용(예:ROW_NUMBER).
헬퍼(query_analytic.cpp):
qdata_initialize_analytic_func— 그룹별 카운터 영점, 필요 시 distinct 리스트 파일 오픈.qdata_evaluate_analytic_func— 한 튜플을 함수별 진행 중 상태에 접어 넣음.qdata_finalize_analytic_func— 정렬 키 단위 최종 값 계산.
Sort vs Hash GROUP BY — 전략 선택과 spill
섹션 제목: “Sort vs Hash GROUP BY — 전략 선택과 spill”선택도 / 메모리 상수:
HASH_AGGREGATE_VH_SELECTIVITY_TUPLE_THRESHOLD= 2000.HASH_AGGREGATE_VH_SELECTIVITY_THRESHOLD= 0.5f.PRM_ID_MAX_AGG_HASH_SIZE(기본 2 MB) — 메모리 상한.PRM_ID_AGG_HASH_RESPECT_ORDER— 적격이더라도 sort-skip 단축 을 비활성화.PRM_ID_SR_NBUFFERS— 정렬 버퍼 페이지 수.
외부 정렬 기반(storage/external_sort.c):
sort_listfile— 공개 진입점. 콜백을SORT_PARAM에 복사하고 in-phase + ex-phase를 실행.sort_listfile_internal— 실제 드라이버.sort_inphase_sort— 버퍼 크기 청크에서 정렬된 run을 만듦.sort_run_sort— 인메모리 키 배열에 대한 quicksort.sort_run_flush— 정렬된 run을 임시 파일로 flush.sort_exphase_merge— run들의 k-way 머지.sort_exphase_merge_elim_dup— 중복 제거를 동반한 머지 (DISTINCT류 정렬용).SORT_PARAM— 중심 상태 구조체(파일 테이블, 콜백 묶음, 비교자).SORT_PARALLEL_TYPE— 직렬,SORT_ANALYTIC, 그 외 병렬 스케줄러 모드 사이의 선택자.
위치 힌트(2026-04-30 기준)
섹션 제목: “위치 힌트(2026-04-30 기준)”| 심볼 | 파일 | 라인 |
|---|---|---|
HASH_AGGREGATE_VH_SELECTIVITY_TUPLE_THRESHOLD | query_executor.c | 127 |
HASH_AGGREGATE_VH_SELECTIVITY_THRESHOLD | query_executor.c | 130 |
GROUPBY_DIMENSION_FLAG | query_executor.c | 200 |
GROUPBY_DIMENSION struct | query_executor.c | 206 |
GROUPBY_STATE struct | query_executor.c | 213 |
ANALYTIC_FUNCTION_STATE struct | query_executor.c | 259 |
ANALYTIC_STATE struct | query_executor.c | 288 |
qexec_initialize_groupby_state | query_executor.c | 4289 |
qexec_gby_agg_tuple | query_executor.c | 4478 |
qexec_hash_gby_agg_tuple_public | query_executor.c | 4516 |
qexec_hash_gby_agg_tuple | query_executor.c | 4537 |
qexec_hash_gby_get_next | query_executor.c | 4778 |
qexec_hash_gby_put_next | query_executor.c | 4793 |
qexec_gby_get_next | query_executor.c | 4940 |
qexec_gby_put_next | query_executor.c | 4956 |
qexec_groupby | query_executor.c | 5247 |
qexec_execute_mainblock_internal | query_executor.c | 15058 |
qexec_gby_finalize_group_dim | query_executor.c | 19092 |
qexec_gby_finalize_group | query_executor.c | 19184 |
qexec_gby_start_group_dim | query_executor.c | 19408 |
qexec_gby_start_group | query_executor.c | 19430 |
qexec_gby_init_group_dim | query_executor.c | 19501 |
qexec_execute_analytic | query_executor.c | 21007 |
qexec_initialize_analytic_state | query_executor.c | 21593 |
qexec_analytic_get_next | query_executor.c | 21743 |
qexec_analytic_put_next | query_executor.c | 21761 |
qexec_analytic_start_group | query_executor.c | 22045 |
qexec_analytic_finalize_group | query_executor.c | 22118 |
qexec_analytic_add_tuple | query_executor.c | 22195 |
qexec_analytic_evaluate_offset_function | query_executor.c | 22416 |
qexec_analytic_evaluate_cume_dist_percent_rank_function | query_executor.c | 22634 |
qexec_analytic_evaluate_interpolation_function | query_executor.c | 22676 |
qexec_analytic_group_header_load | query_executor.c | 22807 |
qexec_analytic_sort_key_header_load | query_executor.c | 22847 |
qexec_analytic_value_advance | query_executor.c | 22910 |
qexec_analytic_value_lookup | query_executor.c | 23080 |
qexec_analytic_group_header_next | query_executor.c | 23112 |
qexec_analytic_update_group_result | query_executor.c | 23135 |
qexec_alloc_agg_hash_context_buildlist_xasl | query_executor.c | 26906 |
qexec_alloc_agg_hash_context | query_executor.c | 26922 |
qexec_free_agg_hash_context | query_executor.c | 27157 |
qexec_build_agg_hkey | query_executor.c | 27282 |
qexec_locate_agg_hentry_in_list | query_executor.c | 27327 |
sort_run_sort | storage/external_sort.c | 1171 |
sort_listfile | storage/external_sort.c | 1347 |
sort_listfile_internal | storage/external_sort.c | 1749 |
sort_inphase_sort | storage/external_sort.c | 1849 |
sort_run_flush | storage/external_sort.c | 2294 |
sort_exphase_merge_elim_dup | storage/external_sort.c | 2457 |
sort_exphase_merge | storage/external_sort.c | 3381 |
sort_get_avg_numpages_of_nonempty_tmpfile | storage/external_sort.c | 4137 |
sort_get_numpages_of_active_infiles | storage/external_sort.c | 5685 |
sort_run_add_new | storage/external_sort.c | 5747 |
소스 검증 노트
섹션 제목: “소스 검증 노트”원시 분석본(Post-processing(aggregation).pdf,
Post-Processing(analytic).pdf, Sort, Hash Group By.pptx)은
프로젝트 내부 학습 자료로 캡처된 것이다. 구조적 기술은 현재
소스와 충실히 일치하지만, 몇몇 지점은 시점 차이로 어긋났거나
표현이 부정확한 경우가 있다.
-
HASH_AGGREGATE_VH_SELECTIVITY_TUPLE_THRESHOLD값. 덱 (slides 18, 20)은 200개로 쓰고 변경될 수 있음이라고 단서를 단다. 현재 소스는 2000으로 정의되어 있다 (query_executor.c:127). 임계값은 덱 작성 이후 한 자리수 올라간 셈이다. -
“Sort_listfile에는 qexec_gby_get_next와 qexec_gby_put_next 함수가 인자로 전달됩니다.” 검증됨 —
qexec_groupby의 호출 서명이 덱의 설명과 일치한다. 다만 덱의 put 콜백 흐름도(page 7) 진입 노드는qexec_analytic_put_next로 그려져 있는데, 이는 분석 덱에서 복사 붙여넣기 한 흔적이며 GROUP BY의 실제 진입은qexec_gby_put_next이다. -
groupby_dimension의 순서. 덱(slide 24)은g_dim[0]을 모든 컬럼을 기준으로 집계한 결과로, 상위 인덱스를 롤업 prefix로, total 집계(그룹핑 컬럼 없음)를g_dim[1]에, prefix 레벨들을g_dim[2..g_dim_levels-1]에 둔다고 설명한다.qexec_gby_init_group_dim에서 검증됨 — 인덱스 0은GROUPBY_DIM_FLAG_GROUP_BY를 가지고,with_rollup일 때 모든 인덱스가 추가로GROUPBY_DIM_FLAG_ROLLUP을 가진다.qexec_gby_finalize_group_dim의 finalize 순서 는g_dim_levels - 1에서i + 1까지 거슬러 내려가며, 이는 덱의 g_dim 배열 끝에서부터, nkey + 1까지 finalize 규칙과 일치 한다. -
CBRD-25611 — 롤업 표현식 NULL 버그. 덱 slide 29가 수정 내용을 고수준으로 기술한다. 패치가 현재
qexec_gby_finalize_group_val_list에 있는지, 아니면 표현식 평가기에 있는지는 추적되지 않았다. 조사 경로는jira.cubrid.org의 CBRD-25611 커밋 로그다. -
분석 덱 slide page 4의 흐름도. 결정 트리는 파티션 prefix 재비교 순서를 옳게 설명한다. 다만 “비교할 키 개수 = sort_prefix_size” 라벨은 비교 후
nkeys가 원래 값으로 되돌려 진다는 사실을 생략한다. 실제 계약은qexec_analytic_put_next소스의 save-and-restore 패턴이다. -
qexec_initialize_groupby_state는groupby_list != NULL일 때만qfile_initialize_sort_key_info를 호출한다. 함수 머리에서 검증됨.qexec_groupby자체가buildlist->groupby_list == NULL이면 조기 탈출하므로, state-init은 NULL 리스트를 절대 보지 않는다. -
qexec_execute_analytic은 분석 함수가 아니라 정렬 리스트 마다 한 번씩 실행된다.qexec_execute_mainblock_internal의 호출 지점에서 검증됨(루프가xasl->proc.buildlist.a_eval_list를 순회하면서 엔트리당qexec_execute_analytic을 호출). 덱은 정렬 리스트별 반복은 설명하지만, 그 엔트리들을 만들어 내는 planner 측 병합인pt_optimize_analytic_list는 생략한다. -
qexec_execute_analytic의is_skip_sort경로. planner가 이미 정렬된 입력을 만든 경우에 발동한다. 함수는sort_listfile을 건너뛰고qexec_analytic_update_group_result로 직행한다.if (is_skip_sort) { ... goto wrapup; }분기에서 검증됨. 덱은 이 최적화를 다루지 않는다.
미해결 질문
섹션 제목: “미해결 질문”-
오프셋 함수의
is_same_group=true케이스가 같은 정렬 키 안에서도start_group(reinit=false)를 유지하는 이유.qexec_analytic_put_next의 주석(“offset functions will treat all tuples in a group as having a different sort key regardless if this is true or not”)은 튜플별 distinct 값 요구를 시사한다. 그 결과value_list_id는 엄격한 정렬-키 경계 카운트보다 더 많은 엔트리를 갖게 된다. 조사 경로는qexec_analytic_evaluate_offset_function의 읽기 측 커서가 추가 엔트리를 어떻게 소비하는지 추적하는 것이다. -
qexec_analytic_value_advance의 all-NULL 그룹 실패 의미론. 모든 값이 NULL이고ignore_nulls == true라서 목표 위치가 모든 튜플을 건너뛰게 되는 경우, 함수는func_p->value를 직전 내용으로 둔 채NO_ERROR를 반환한다. 호출자(예:qexec_analytic_value_lookup호출자 들)가 그 값을 사용하기 전에 NULL로 리셋하는지 감사가 필요 하다. -
SORT_ANALYTIC병렬 정렬 라우팅.sort_listfile은SORT_PARALLEL_TYPE인자를 받는다. 분석 호출 지점은SORT_ANALYTIC을, GROUP BY 호출 지점은 디폴트를 사용한다.external_sort.c의 다운스트림 병렬 정렬 스케줄러를 추적해 분석 변종이 별도 스케줄링 정책을 갖는지 확인할 필요가 있다. 조사 경로는sort_listfile_internal과sort_run_sort아래의 병렬 후크다. -
HS_REJECT_ALL폴백 후 새 반복이qexec_hash_gby_agg_tuple에 진입하면agg_hash_context는 어떻게 되는가? 함수 진입 가드의state == HS_REJECT_ALL분기는 즉시 반환한다. 그러므로 튜플은 해시를 우회해 호출자에 의해xasl->list_id로 직접 쓰인다. 다만 해시 테이블 자체는 방금qdata_save_agg_htable_to_list로 덤프된 상태다 —mht_table이 그 시점에 해제되는지, 아니면 빈 채로qexec_free_agg_hash_context시점까지 잔존하는지에 따라 메모리 회계가 달라진다. -
PRM_ID_AGG_HASH_RESPECT_ORDER의 의미론.yes(기본값) 로 설정되면 sort-skip 최적화가 적용 가능한 경우에도 후처리를sort_listfile로 강제한다. 왜 디폴트가yes인가? 가설 — 하부 소비자(예: DISTINCT, 여기엔 없지만 다른 곳에서 합성되는 최상위 ORDER BY)가 출력 순서의 결정성을 요구하기 때문일 수 있다. 정렬이 빠지면 같은 hash agg 질의가 두 번 실행될 때 행 순서가 달라질 수 있다는 점이다. 조사 경로는 매개변수 도입 시점의git log다. -
sort_listfile이후의 trailing-group finalize.qexec_groupby와qexec_execute_analytic둘 다sort_listfile이 어떤 drain 후크도 호출하지 않는다는 사실에 의존해 정렬이 반환된 후 마지막 그룹을 finalize 한다. 미래의 리팩터가 그런 후크를 추가한다면(병렬 정렬은 이미 더 복잡한 완료 경로를 가진다) trailing finalize가 두 번 발화할 수 있다는 점이다. 계약이 암시적이다 —external_sort.h의 invariant로 명시화하는 것이 방어적이다. -
interm_file의 메모리 소유.is_skip_sort가 true이면analytic_state.interm_file = list_id(입력 리스트 파일)다. false면interm_file은 새로 연 리스트 파일이다.qexec_execute_analytic끝의 정리 분기는 출력을 복사한 뒤list_id를 파괴한다.is_skip_sort케이스에서(둘이 alias 된 경우)interm_file이 독립적으로 파괴되는지, 아니면 파괴가 정확히 건너뛰어지는지 감사가 필요하다. 조사 경로는qexec_clear_analytic_state추적이다. -
비-위치 reguvar로부터의 해시 키 추출. 덱은
g_hk_regu_list가proc->g_hk_scan_regu_list(타입TYPE_POSITION)로부터 만들어진다고 단언한다(slide 7: regu_list는 TYPE_POSITION 타입). GROUP BY 키가 컬럼이 아니라 표현식 인 경우,TYPE_POSITIONreguvar들은 표현식 값을 튜플 위치로 구체화하는 업스트림 평가에 의해 backing 되어야 한다. 이 구체화가xasl_generation.c에 사는지, 아니면 옵티마이저의pt_optimize_*_for_groupby패스에 사는지 확인이 필요하다.
원시 분석본(raw/code-analysis/cubrid/query-processing/)
섹션 제목: “원시 분석본(raw/code-analysis/cubrid/query-processing/)”Post-processing(aggregation).pdf— sort 기반 및 hash 기반 GROUP BY 실행,GROUPBY_DIMENSION롤업 메커니즘,qexec_groupby흐름도 발췌.Post-Processing(analytic).pdf— 윈도우/분석 함수 실행:qexec_analytic_put_next흐름, 사이드카 리스트 파일,LAG과MEDIAN의 worked example.Sort, Hash Group By.pptx— 전략 선택에 관한 2025년 8월 내부 슬라이드 덱. XASL 리스트 모양(g_outptr_list,g_val_list,g_regu_list,g_agg_list), 처리 측 해시 insert, 키 중복 시나리오, sort-skip 조건, CBRD-25611._converted/post-processingaggregation.pdf.md,_converted/post-processinganalytic.pdf.md,_converted/sort-hash-group-by.pptx.md— markitdown 추출.
자매 문서
섹션 제목: “자매 문서”knowledge/research/dbms-general/database-internals.md— Petrov 14장(Query Execution). sort vs. hash 집계와 외부 정렬 기반에 대한 텍스트북 프레이밍.knowledge/code-analysis/cubrid/cubrid-heartbeat.md— 본 문서 구조의 스타일 모범.
텍스트북 챕터 / 논문
섹션 제목: “텍스트북 챕터 / 논문”- Database Internals(Petrov, 2019), 14장 — 질의 실행 모델, sort/hash 트레이드오프, 외부 정렬.
- Database Systems: The Complete Book(Garcia-Molina, Ullman, Widom), 15장 — 물리적 질의 플랜, 정렬과 해싱 기반 2-pass 알고리즘.
- ISO/IEC 9075-2:2003(SQL:2003) —
WINDOW절 정의. CUBRID의 분석 실행이 구현하는 명세. - PostgreSQL
src/backend/executor/nodeAgg.c와nodeWindowAgg.c소스(BSD 라이선스) — 전략 선택과 윈도우 실행 대안의 비교 레퍼런스.
CUBRID 소스(/data/hgryoo/references/cubrid/)
섹션 제목: “CUBRID 소스(/data/hgryoo/references/cubrid/)”src/query/query_executor.c— 후처리 본체:qexec_groupby,qexec_execute_analytic, put 콜백들, 함수별 평가기들, 해시 컨텍스트 드라이버.src/query/query_aggregate.cpp— 집계 평가 헬퍼:qdata_evaluate_aggregate_list,qdata_finalize_aggregate_list, 해시 키/값 라이프사이클.src/query/query_analytic.cpp— 분석 평가 헬퍼:qdata_initialize_analytic_func,qdata_evaluate_analytic_func,qdata_finalize_analytic_func.src/storage/external_sort.c/external_sort.h—sort_listfile과 in-phase / ex-phase 머지 소트.src/query/list_file.c— 입력과 분석 사이드카 (group_list_id,value_list_id,interm_file) 모두에 쓰이는qfile_*리스트 파일 프리미티브.src/xasl/buildlist_proc_node.hpp(또는 노드가 정의된 곳) —g_outptr_list,g_agg_list,g_hash_eligible,agg_hash_context,g_with_rollup을 보유하는BUILDLIST_PROC_NODE.src/parser/parse_tree.h,xasl_generation.c— 리스트들을 생성하고g_hash_eligible을 결정하는 파서/XASL 빌더 측. 분석 함수의 공유 정렬 병합을 담당하는pt_optimize_analytic_list.