콘텐츠로 이동
hgryoo · Docs

(KO) CUBRID List-File — 연산자 사이를 흐르는 spillable 튜플 스트림과 머터리얼라이즈 기반

목차

학술적 배경

섹션 제목: “학술적 배경”

질의 계획(query plan)은 튜플을 받아 튜플을 내보내는 연산자(operator)들의 방향성 비순환 그래프(DAG)다. 이웃한 두 연산자 사이에서 튜플을 옮기는 정석은 두 가지다. 첫째, Volcano(Graefe 1994)가 정의한 수요 주도(demand-driven) 반복이다. 소비자가 생산자에게 next()를 호출하면 생산자는 호출 한 번에 정확히 한 튜플을 만들어 내보낸다. 트리의 바닥(leaf)까지 호출이 내려갔다가 한 행이 거슬러 올라오는 식이다. 아무 것도 머터리얼라이즈되지 않으며, 호출 스택이 곧 파이프 역할을 한다. 둘째, 명시적 머터리얼라이즈(explicit materialisation) 다. 생산자는 자기가 만든 모든 튜플을 임시 튜플 스트림에 먼저 써 두고, 소비자는 그 스트림을 처음부터 다시 읽는다. Graefe 1993(Query Evaluation Techniques for Large Databases)은 두 설계를 나란히 분류한 뒤, 실제 엔진은 둘을 섞는다는 점을 지적한다. 대부분의 연산자는 반복으로 처리하지만, 일부는 머터리얼라이즈를 피할 수 없다는 점이 핵심이다.

머터리얼라이즈를 강제하는 연산자 부류는 크게 넷이다.

  1. 정렬(Sort). 머지 정렬은 가장 작은 튜플 한 개를 내보내기 전에 입력 전체를 다 받아야 한다. 입력은 어딘가에 보관되어야 하고, 메모리 안에 들어오지 않으면 디스크로 떨어진다.
  2. 해시 빌드(Hash build, 해시 조인의 빌드 측 또는 해시 GROUP BY). probe 측은 스트리밍이 가능하지만, 빌드 측은 입력 전체를 끝까지 받아 인덱스를 만들어야 첫 probe가 시작된다.
  3. 다회차 스캔(Multi-pass scan). 같은 입력을 두 번 이상 훑어야 하는 연산이 있다. 파티션 위에서 동작하는 분석 함수, 재귀 CTE(recursive CTE), 일부 CONNECT BY 순회, 외부 행마다 한 번씩 실행되는 상관 서브쿼리의 내부 측이 그 예다. 이런 입력은 재스캔 가능한 버퍼에 잡아 두는 것이 가장 효율적이다.
  4. 서브쿼리 결과 메모이제이션(memoisation). 비상관(uncorrelated) 서브쿼리가 외부 계획에 CONSTANT 참조로 들어올 때, 서브쿼리는 한 번만 실행되고 그 결과 튜플이 어딘가에 저장된 뒤 모든 참조는 그 저장소를 읽는다. 머터리얼라이즈가 없으면 매 참조마다 서브쿼리가 다시 실행된다.

Hellerstein과 Stonebraker는 Anatomy of a Database System 에서 이 객체를 연산자 간 파이프(inter-operator pipe) 라 부르고, 질의가 spill하는 순간 실행기 시간의 대부분이 이 파이프 위에서 사용된다는 점을 강조한다. 이 파이프가 일반 임시 파일과 구별되는 성질은 셋이다.

  • 순차 쓰기, 순차 읽기. 파이프는 질의 도중 임의로 갱신되지 않는다. 생산자는 끝날 때까지 append만 하고, 끝난 뒤에는 소비자에게는 immutable이 된다. 정렬과 해시는 내부적으로 다시 쓰지만, 그것이 만들어 내보내는 파이프 자체는 append-only다.
  • 자기 기술적(self-describing) 튜플. 파이프는 reader가 각 튜플을 타입 있는 값으로 다시 디코딩할 수 있을 만큼의 메타데이터를 함께 운반해야 한다. 술어(predicate)를 평가할 수 있으려면 그래야 한다. 표준 인코딩은 튜플별 길이 prefix와 스트림 차원의 타입 리스트의 조합이며, Database Internals (Petrov, 1장 File Organization)가 slotted page, 고정/가변 길이 튜플 이라는 이름으로 같은 패턴을 설명한다.
  • Spill 가능성. 결과가 몇 KB 안쪽이면 디스크 공간을 잡지 않아야 하고, 그 한계를 넘으면 투명하게 디스크로 옮겨가야 한다. PostgreSQL의 Tuplestore도, CUBRID의 list-file도 둘 다 처음에는 작은 in-memory 페이지 배열에 매달려 있다가 압력이 오면 임시 파일로 자기 자신을 옮긴다.

파이프 안의 튜플 표현은 또 다른 설계 다이얼이다. 흔한 형태는 셋이다. packed row(고정·가변 길이 값을 연속해서 쓰고 가변 길이 값에는 prefix를 두는 방식; 대부분의 row store 임시 스트림이 채택)와, columnar(컬럼당 버퍼 한 개; 분석 엔진이 선호)와, 불투명 인코딩 blob(직렬화된 C struct; 깨지기 쉬워서 드물다)이 그 셋이다. CUBRID는 packed row를 채택하되 길이 prefix를 두 단계로 둔다. 튜플당 한 개, 값마다 한 개. 자세한 내용은 아래 ## CUBRID의 구현에서 다룬다.

마지막 이론적 조각은 수명(lifecycle) 이다. 파이프는 한 질의 실행 안에서만 존재한다. 생산자가 open할 때 만들어져서, 생산자가 close할 때까지 쓰여지고, 소비자가 close할 때까지 읽히고, 그 뒤에 파괴된다. 크래시 시 파이프를 복구할 필요가 없다. 롤백할 것이 없고, 어떤 트랜잭션도 그 내용을 커밋하지 않았기 때문이다. 그래서 스토리지 매니저는 이를 복구 대상이 아니고 WAL 로그도 남기지 않는 파일로 취급한다. CUBRID의 FILE_TEMP과 PAGE_QRESULT 페이지 타입이 정확히 이 계약(contract)을 인코딩한다.

DBMS 공통 설계 패턴 (Common DBMS Design)

섹션 제목: “DBMS 공통 설계 패턴 (Common DBMS Design)”

엔진들이 갈리는 지점은 튜플 스트림 추상을 몇 가지로 노출하는가, 그리고 in-memory에서 디스크로 넘어가는 전이가 어디서 일어나는가 다. 형태 자체는 거의 동일하다.

PostgreSQL — Tuplestore와 Tuplesort

섹션 제목: “PostgreSQL — Tuplestore와 Tuplesort”

PostgreSQL은 객체를 둘로 나눈다.

  • Tuplestore (src/backend/utils/sort/tuplestore.c) — 범용 spillable 튜플 버퍼. Material 계획 노드, WindowAgg, Tablefunc, RowsFromFunc의 보조 저장소로 쓰인다. work_mem이 꽉 차기 전까지는 메모리 위에 머무르고, 넘치면 BufFile 기반 디스크 파일로 spill한다. 정방향 스캔, 역방향 스캔, rewind를 모두 지원한다. 생산자는 tuplestore_puttuple / tuplestore_putvalues로 쓰고, 소비자는 tuplestore_gettupleslot으로 읽는다.
  • Tuplesort (tuplesort.c) — 삽입 시점에 정렬 하는 특화 spillable 버퍼. Sort, Agg(sort 전략), Unique, Limit, ANALYZE가 사용한다. 내부 상태는 TSS_INITIAL, TSS_BOUNDED, TSS_BUILDRUNS, TSS_FINALMERGE 중 하나다. 입력이 work_mem에 들어오는지, top-N을 활용할 수 있는지에 따라 결정된다.

분리 자체가 의도다. Tuplestore는 정렬이 필요 없을 때 정렬 비용을 지불하지 않고, Tuplesort의 정렬 로직은 범용 버퍼 위에 덧붙여진 것이 아니다. 둘은 spill 기반으로 BufFile을 공유한다.

MySQL — filesort, 임시 테이블, Filesort_buffer

섹션 제목: “MySQL — filesort, 임시 테이블, Filesort_buffer”

MySQL의 대응물은 더 잘게 쪼개져 있다. Filesort (sql/filesort.cc) 는 ORDER BY를 처리하며 개념상 Tuplesort에 가깝다. 메모리의 sort buffer가 차면 tmpdir의 머지 파일들로 spill한다. 임시 테이블 (sql/sql_tmp_table.cc)은 GROUP BY와 DISTINCT를 처리한다. 이쪽은 스트림이라기보다는 보통의 MyISAM/InnoDB 테이블에 가까우며, in-memory MEMORY 엔진에서 시작하다가 tmp_table_size를 넘으면 디스크 위 MyISAM/InnoDB로 옮겨간다. 스트리밍 쪽은 JOIN_CACHE 그리고 MySQL 8의 새로운 iterator 인터페이스(AggregateIterator, WindowIterator)가 담당한다.

SQL Server — Table Spool / Index Spool

섹션 제목: “SQL Server — Table Spool / Index Spool”

SQL Server는 spool 자체 를 두 가지 계획 연산자로 노출한다. Table Spool은 임의의 튜플 스트림을 TempDB에 머터리얼라이즈하고, Index Spool은 머터리얼라이즈한 뒤 재 probe를 위해 B-tree 인덱스를 덧붙인다. spool이 일급 노드이기 때문에 옵티마이저는 어떤 서브플랜을 spool하고 어떤 것은 재실행할지 명시적으로 비교한다. spool 저장소는 TempDB이며, 자체 버퍼 풀과 복구 규칙을 가진다.

이론 ↔ CUBRID 대응

섹션 제목: “이론 ↔ CUBRID 대응”

CUBRID는 PostgreSQL이 둘로 쪼갠 추상을 단일 튜플 스트림 추상 — list file — 으로 합쳐 둔다. 정렬, GROUP BY, 해시 빌드, 서브쿼리 메모, 최종 결과 전달이 모두 같은 QFILE_LIST_ID 위에서 동작한다. 정렬은 list file 위에서 동작하는 함수 로 구현되어 있다. qfile_sort_list가 정렬되지 않은 list file을 읽어 external_sort를 거쳐 정렬된 list file을 만들어 낸다는 점이다. 별도의 객체가 아니다.

이론 개념CUBRID 명칭
튜플 스트림 식별자(무엇)QFILE_LIST_ID (query_list.h)
그 아래 저장소 핸들QMGR_TEMP_FILE (query_manager.h)
in-memory spill 버퍼QMGR_TEMP_FILE::membuf[] (PAGE_PTR 배열)
디스크 spill 기반FILE_TEMP via file_create_temp (file_manager.c)
디스크 페이지 포맷PAGE_QRESULT (qmgr_init_external_file_page이 설정)
페이지 헤더QFILE_PAGE_HEADER (32바이트)
튜플 포맷길이 prefix를 가진 packed row, QFILE_TUPLE
값마다의 헤더QFILE_TUPLE_VALUE_HEADER (flag + length)
스트림 차원 타입 리스트QFILE_TUPLE_VALUE_TYPE_LIST (TP_DOMAIN * 배열)
생산자 iterator 상태QFILE_LIST_ID::last_pgptr / last_offset / lasttpl_len
소비자 iterator 상태QFILE_LIST_SCAN_ID (query_list.h)
scan 연산자로 노출되는 wrapperS_LIST_SCAN / LLIST_SCAN_ID (scan_manager.h)
파이프 open(생산자)qfile_open_list
튜플 appendqfile_add_tuple_to_list (또는 qfile_generate_tuple_into_list)
파이프 close(생산자)qfile_close_list
스캔 openqfile_open_list_scan
다음 튜플 가져오기(소비자)qfile_scan_list_next
스캔 closeqfile_close_scan
파이프 파괴(임시 페이지 해제)qfile_destroy_list
집합 연산 파이프qfile_combine_two_list (UNION / INTERSECT / DIFFERENCE)
정렬 wrapperqfile_sort_list / qfile_sort_list_with_func
질의 간 결과 메모이제이션QFILE_LIST_CACHE_ENTRY + qfile_lookup_list_cache_entry

공유 추상 하나로 합쳤을 때 얻는 아키텍처적 보상은 크다. 실행기 (query_executor.c), 스캔 계층(scan_manager.c), 후처리 계층 (query_aggregate.cpp, query_analytic.cpp), 그리고 질의 간 결과 캐시(list-file 캐시)가 모두 같은 어휘를 쓴다. 새로운 머터리얼라이즈 연산자(또는 새로운 소비자)를 추가하는 일은 대체로 qfile_open_list와 qfile_scan_list_next를 호출하는 일에 머문다. spill 로직, 페이지 레이아웃, 수명 관리는 그대로 상속된다.

CUBRID의 구현

섹션 제목: “CUBRID의 구현”

이 섹션은 추상을 네 단계로 줌 인 한다. 식별자(QFILE_LIST_ID), 페이지 포맷(QFILE_PAGE_HEADER + 튜플), 생산자/소비자 연산, 그리고 주변 XASL 실행과 묶이는 수명 — 가 그 넷이다. 각 단계마다 list_file.c 안의 작은 함수 묶음이 노출되어 있고, 본문은 라인번호가 아닌 심볼명 을 anchor로 쓴다. ## 소스 코드 가이드 끝의 위치 힌트 표가 심볼을 현재 라인 오프셋과 묶어 둔다.

QFILE_LIST_ID — 튜플 스트림 식별자

섹션 제목: “QFILE_LIST_ID — 튜플 스트림 식별자”

QFILE_LIST_ID는 거의 모든 컴포넌트가 주고받는 핸들이다. 튜플 그 자체가 아니고, 바이트 자체도 아니다. 약 120바이트의 작은 struct로, 바이트가 어디에 있는지, 몇 개의 튜플이 들어 있는지, 그 스키마가 어떤 모양인지, 그리고 writer 측 cursor 상태가 무엇인지를 기술한다.

// QFILE_LIST_ID — src/query/query_list.h
struct qfile_list_id
{
  QFILE_TUPLE_VALUE_TYPE_LIST type_list;  /* domain of each column */
  SORT_LIST *sort_list;                   /* sort attributes (if sorted) */
  INT64 tuple_cnt;                        /* total tuples */
  int   page_cnt;                         /* total pages */
  VPID  first_vpid;                       /* head of page chain */
  VPID  last_vpid;                        /* tail of page chain */
  PAGE_PTR last_pgptr;                    /* live last-page latch (writer) */
  int   last_offset;                      /* end-of-data on last page */
  int   lasttpl_len;                      /* last tuple length (for prev links) */
  QUERY_ID query_id;                      /* owning query */
  VFID  temp_vfid;                        /* duplicated from tfile_vfid */
  struct qmgr_temp_file *tfile_vfid;      /* the actual storage handle */
  QFILE_TUPLE_DESCRIPTOR tpl_descr;       /* writer-side fast path */
  bool  is_domain_resolved;
  bool  is_result_cached;
  QFILE_LIST_ID *dependent_list_id;       /* chained on qfile_connect_list */
};

세 가지 관찰이 가능하다.

  1. struct는 파일에 대한 정적 기술 (타입 리스트, 정렬 속성, 소유 질의) 과 생성 중 cursor (last_pgptr, last_offset, lasttpl_len) 을 함께 담는다. list file이 만들어지는 동안 cursor 필드는 latch 잡혀 있는 페이지를 가리키고, qfile_close_list 가 돌고 나면 그 필드들은 NULL로 비워지며 페이지의 latch가 풀린다. 따라서 list file 은 정확히 세 가지 상태 중 하나에 있다. open이고 쓰는 중(cursor 살아 있음), close이고 읽기 가능(cursor NULL, 페이지는 디스크/ membuf), 파괴됨(struct 비워짐) 중 하나다.
  2. 실제 저장소는 한 단계 더 들어가야 보인다. tfile_vfid는 QMGR_TEMP_FILE을 가리키며, 이 객체가 in-memory membuf[]을 들고 있고, membuf가 다 차고 나서야 file_create_temp로 만든 FILE_TEMP의 temp_vfid를 들고 있게 된다. list file은 디스크를 직접 보지 않는다. qmgr_get_new_page / qmgr_get_old_page 만 본다. 두 함수가 내부적으로 membuf를 먼저 검사한다.
  3. dependent_list_id는 qfile_connect_list로 매단 보조 list file 들의 단방향 체인이다. 부모 스트림을 자식과 논리적으로 연장해야 할 때 쓰인다. 예를 들어 외부 실행이 살아 있는 동안 함께 살아남아야 하는 서브쿼리 중간 결과가 그렇다. 체인은 추이적으로 파괴된다. qfile_destroy_list가 dependent_list_id로 재귀하기 때문에 소유 관계가 모호하지 않다.

페이지 체인 레이아웃

섹션 제목: “페이지 체인 레이아웃”

list file은 데이터베이스 페이지(기본 16 KB의 DB_PAGESIZE)들의 양방향 연결 체인이다. 각 페이지는 32바이트 QFILE_PAGE_HEADER로 시작하며, 바이트 32부터 last_offset까지 튜플이 빽빽히 채워진다.

// qfile_page_header — src/query/query_list.h
struct qfile_page_header
{
  int    pg_tplcnt;     /* # tuples on this page */
  PAGEID prev_pgid;     /* previous data page */
  PAGEID next_pgid;     /* next data page */
  int    lasttpl_off;   /* last-tuple offset (for backward scan) */
  PAGEID ovfl_pgid;     /* overflow page chain head */
  VOLID  prev_volid;    /* (volid, pageid) split into separate fields */
  VOLID  next_volid;
  VOLID  ovfl_volid;
};

페이지마다 별도의 overflow chain 이 ovfl_pgid / ovfl_volid 에 매달린다. 이 체인은 QFILE_MAX_TUPLE_SIZE_IN_PAGE(= `DB_PAGESIZE

  • 32) 보다 큰 튜플을 담는다. 큰 튜플은 분할된다. 첫 청크는 데이터 페이지에 인라인으로 남고, 나머지는 overflow 페이지들로 나뉘어 저장되며, 소비자가 페이지 헤더의 ovfl_pgid != NULL_PAGEID를 만나면 qfile_get_tuple_from_current_list`가 청크들을 다시 이어 붙인다.
flowchart LR
  subgraph MEMBUF["QMGR_TEMP_FILE.membuf[] (in-memory 페이지들)"]
    M0["page 0<br/>QFILE_PAGE_HEADER<br/>tuples..."]
    M1["page 1<br/>tuples..."]
    M2["page 2<br/>tuples..."]
  end
  subgraph TEMP["FILE_TEMP (디스크 spill)"]
    D0["page 3<br/>tuples..."]
    D1["page 4<br/>tuples..."]
    DN["page N<br/>tuples..."]
  end
  LISTID["QFILE_LIST_ID<br/>first_vpid → page 0<br/>last_vpid → page N<br/>last_pgptr → page N latch"]
  M0 -- next_vpid --> M1
  M1 -- next_vpid --> M2
  M2 -- next_vpid --> D0
  D0 -- next_vpid --> D1
  D1 -- next_vpid --> DN
  LISTID -. owns .-> M0
  LISTID -. live cursor on .-> DN

체인은 두 종류의 저장소를 한 줄로 잇는다. membuf 위의 페이지는 volid == NULL_VOLID 와 pageid 자리에 배열 인덱스를 갖는다. FILE_TEMP 위의 페이지는 진짜 (volid, pageid)를 갖는다. reader는 이 차이를 알 필요가 없다. qmgr_get_old_page가 먼저 membuf를 검사하고(vpid->pageid <= membuf_last), 거기서 못 찾으면 pgbuf_fix 로 떨어진다. list file 입장에서 보면 체인은 균질하다.

튜플 포맷 — packed row, 두 단계 길이 prefix

섹션 제목: “튜플 포맷 — packed row, 두 단계 길이 prefix”

페이지 안에 들어가는 각 튜플은 길이 prefix가 두 개 붙은 packed row 다.

[ tuple_length (4) | prev_tuple_length (4) | value_0 | value_1 | ... | value_N-1 ]

prev_tuple_length가 있어서 qfile_scan_list_prev가 페이지 헤더로 다시 돌아가지 않고 한 칸씩 역방향으로 걸어갈 수 있다. 각 값에도 prefix가 붙는다.

[ flag (4) | val_len (4) | <val_len bytes of packed value, MAX_ALIGNMENT-padded> ]

flag는 값이 있으면 V_BOUND, SQL NULL이면 V_UNBOUND(이 경우 val_len == 0)다. 패킹된 값은 컬럼의 PR_TYPE이 정의한 disk-image 포맷 — 즉 pr_data_writeval이 토해 내는 바이트열 — 이다. 이걸 다시 DB_VALUE로 디코딩하는 것은 소비자의 몫이며, 보통은 fetch_val_list 이후 qdata_set_valptr_list_with_domain이 처리한다.

이 레이아웃을 실현하는 매크로 — QFILE_PUT_TUPLE_LENGTH, QFILE_GET_TUPLE_VALUE_HEADER_POSITION, QFILE_GET_TUPLE_VALUE_LENGTH, QFILE_GET_TUPLE_VALUE_FLAG — 는 query_list.h에 살며 튜플을 만지는 모든 자리에 inline된다. 타입을 보지 않는다. 단지 raw 바이트 오프셋만 다룬다.

prefix가 두 단계인 이유

섹션 제목: “prefix가 두 단계인 이유”

소비자가 자기가 쓰지 않을 값을 빠르게 건너뛸 수 있어야 하기 때문이다. 예를 들어 5번 컬럼 위에서 술어를 평가하려고 0–4번 컬럼을 디코딩하지 않은 채로 건너뛰는 경우가 그렇다. 그리고 writer는 다음 튜플이 들어갈 공간을 페이지 단위 할당 전에 알아야 하기 때문이다. 튜플 단위 prefix는 qfile_scan_next가 디코딩 없이 페이지를 걸어갈 수 있게 해 주고, 값 단위 prefix는 qfile_locate_tuple_value가 N번째 컬럼으로 매크로 스텝핑 하나만으로 점프할 수 있게 해 준다.

생산자 측 — open / write / close

섹션 제목: “생산자 측 — open / write / close”
sequenceDiagram
  autonumber
  participant Op as Producer (BUILDLIST_PROC)
  participant LF as list_file
  participant QM as query_manager
  participant FM as file_manager
  Op->>LF: qfile_open_list(type_list, query_id, flag, NULL)
  LF->>QM: qmgr_create_new_temp_file(TEMP_FILE_MEMBUF_NORMAL)
  QM-->>LF: QMGR_TEMP_FILE (membuf 비어 있음, FILE_TEMP 아직 없음)
  LF-->>Op: QFILE_LIST_ID*
  loop 출력 튜플마다
    Op->>LF: qfile_generate_tuple_into_list(T_NORMAL)
    LF->>LF: qfile_allocate_new_page_if_need
    alt membuf에 빈 페이지 있음
      LF->>QM: qmgr_get_new_page (membuf[i+1] 반환)
    else membuf 꽉 참 → spill
      LF->>QM: qmgr_get_new_page (membuf 자리 없음)
      QM->>FM: file_create_temp(1, &temp_vfid) (최초 1회)
      QM->>FM: file_alloc(temp_vfid, init_page, ...)
      FM-->>QM: 진짜 디스크 페이지
      QM-->>LF: PAGE_PTR
    end
    LF->>LF: qfile_save_normal_tuple → memcpy values<br/>qfile_add_tuple_to_list_id (cursor 진행)<br/>qfile_set_dirty_page
  end
  Op->>LF: qfile_close_list (last_pgptr unlatch)

qfile_open_list는 생성자 역할이다. QFILE_LIST_ID를 할당하고, 타입 리스트를 깊은 복사(TP_DOMAIN * 배열을 deep copy)하고, 저장소로 쓸 QMGR_TEMP_FILE을 잡고, QFILE_FLAG_DISTINCT가 켜져 있으면 SORT_LIST를 만든 뒤, 이 파일을 쿼리별 임시 파일 회계에 등록한다.

// qfile_open_list — src/query/list_file.c (condensed)
QFILE_LIST_ID *
qfile_open_list (THREAD_ENTRY * thread_p, QFILE_TUPLE_VALUE_TYPE_LIST * type_list_p, SORT_LIST * sort_list_p,
                 QUERY_ID query_id, int flag, QFILE_LIST_ID * existing_list_id)
{
  QFILE_LIST_ID *list_id_p = existing_list_id ? existing_list_id : (QFILE_LIST_ID *) malloc (sizeof (QFILE_LIST_ID));
  // ... condensed: NULL checks ...


  QFILE_CLEAR_LIST_ID (list_id_p);
  list_id_p->type_list.type_cnt = type_list_p->type_cnt;
  list_id_p->query_id = query_id;


  if (QFILE_IS_FLAG_SET (flag, QFILE_FLAG_RESULT_FILE) && !QFILE_IS_LIST_CACHE_DISABLED)
    list_id_p->tfile_vfid = qmgr_create_result_file (thread_p, query_id);
  else if (QFILE_IS_FLAG_SET (flag, QFILE_FLAG_USE_KEY_BUFFER))
    list_id_p->tfile_vfid = qmgr_create_new_temp_file (thread_p, query_id, TEMP_FILE_MEMBUF_KEY_BUFFER);
  else
    list_id_p->tfile_vfid = qmgr_create_new_temp_file (thread_p, query_id, TEMP_FILE_MEMBUF_NORMAL);
  // ... condensed: allocate type_list.domp, build sort_list if DISTINCT ...
  return list_id_p;
}

open 시점에 어떤 종류의 임시 파일을 깔지 셋 중 하나로 결정된다.

  • qmgr_create_result_file — 질의의 최종 결과 다. 최상위 XASL의 list file에 QFILE_FLAG_RESULT_FILE이 켜진 경우다. 수명이 실행기를 넘어 살아남는다. 클라이언트가 xqfile_get_list_file_page 로 페이지를 가져간다.
  • TEMP_FILE_MEMBUF_NORMAL — 기본값. membuf 크기는 PRM_ID_TEMP_MEM_BUFFER_PAGES(기본 4 페이지)다. 대부분의 중간 list file이 여기에 해당한다.
  • TEMP_FILE_MEMBUF_KEY_BUFFER — index-scan 키 버퍼용으로 더 큰 membuf 크기(PRM_ID_INDEX_SCAN_KEY_BUFFER_PAGES)를 쓴다. 그 외에는 동일한 코드 경로다.

open 직후에는 데이터 페이지가 아직 할당되지 않는다. 첫 페이지는 첫 qfile_add_tuple_to_list(또는 qfile_generate_tuple_into_list / qfile_get_first_page) 호출 시점에 lazy하게 만들어진다.

// qfile_allocate_new_page (condensed) — src/query/list_file.c
static PAGE_PTR
qfile_allocate_new_page (THREAD_ENTRY * thread_p, QFILE_LIST_ID * list_id_p, PAGE_PTR page_p, bool is_ovf_page)
{
  VPID new_vpid;
  PAGE_PTR new_page_p = qmgr_get_new_page (thread_p, &new_vpid, list_id_p->tfile_vfid);
  if (new_page_p == NULL) return NULL;


  QFILE_PUT_TUPLE_COUNT (new_page_p, 0);
  QFILE_PUT_PREV_VPID (new_page_p, &list_id_p->last_vpid);
  if (is_ovf_page) QFILE_PUT_NEXT_VPID_NULL (new_page_p);
  else             LS_PUT_NEXT_VPID (new_page_p);     /* NULL_PAGEID_IN_PROGRESS */
  QFILE_PUT_LAST_TUPLE_OFFSET (new_page_p, QFILE_PAGE_HEADER_SIZE);
  QFILE_PUT_OVERFLOW_VPID_NULL (new_page_p);


  if (page_p) QFILE_PUT_NEXT_VPID (page_p, &new_vpid);    /* link old → new */
  list_id_p->page_cnt++;
  if (page_p) qfile_set_dirty_page (thread_p, page_p, FREE, list_id_p->tfile_vfid);
  else        QFILE_COPY_VPID (&list_id_p->first_vpid, &new_vpid);  /* very first page */
  QFILE_COPY_VPID (&list_id_p->last_vpid, &new_vpid);
  list_id_p->last_pgptr = new_page_p;
  list_id_p->last_offset = QFILE_PAGE_HEADER_SIZE;
  return new_page_p;
}

membuf와 디스크의 분기점은 qmgr_get_new_page다.

// qmgr_get_new_page (condensed) — src/query/query_manager.c
PAGE_PTR
qmgr_get_new_page (THREAD_ENTRY * thread_p, VPID * vpid_p, QMGR_TEMP_FILE * tfile_vfid_p)
{
  /* first try the in-memory page array */
  if (tfile_vfid_p->membuf != NULL && tfile_vfid_p->membuf_last < tfile_vfid_p->membuf_npages - 1)
    {
      vpid_p->volid  = NULL_VOLID;
      vpid_p->pageid = ++(tfile_vfid_p->membuf_last);
      return tfile_vfid_p->membuf[tfile_vfid_p->membuf_last];
    }


  /* membuf exhausted → spill: ensure a FILE_TEMP exists, then alloc from it */
  if (VFID_ISNULL (&tfile_vfid_p->temp_vfid))
    {
      file_create_temp (thread_p, 1, &tfile_vfid_p->temp_vfid);
      tfile_vfid_p->temp_file_type = FILE_TEMP;
      /* ... TDE setup if encrypted ... */
    }
  return qmgr_get_external_file_page (thread_p, vpid_p, tfile_vfid_p);
}

페이지는 두 영역에 살면서 하나의 논리적 체인에 엮인다. membuf는 qmgr_allocate_tempfile_with_buffer가 단일 큰 malloc으로 잘라 만든 고정 크기 DB_PAGESIZE 버퍼들의 배열이다. FILE_TEMP 페이지는 파일 매니저의 tempcache가 추적하는 진짜 디스크 페이지다. 둘 사이의 전이는 list file 하나를 정확히 한 번, membuf가 다 찼을 때 일어난다.

튜플 쓰기 경로 — 세 가지

섹션 제목: “튜플 쓰기 경로 — 세 가지”

생산자가 튜플 바이트를 어떻게 알고 있느냐에 따라 진입점이 셋이다.

  • qfile_add_tuple_to_list — 바이트가 이미 QFILE_TUPLE 버퍼에 직렬화되어 있을 때 쓴다. 부모의 list로 자식의 sub-block이 복사되거나, 실행기가 tpl_descr 용량을 초과해서 qdata_copy_valptr_list_to_tuple 로 fallback한 경우가 그렇다. 페이지보다 큰 튜플도 qfile_allocate_new_ovf_page 메커니즘으로 처리한다.
  • qfile_generate_tuple_into_list — 바이트가 아직 직렬화되어 있지 않을 때 쓴다. 값은 QFILE_TUPLE_DESCRIPTOR의 f_valp[] 배열이 가리키는 DB_VALUE * 들에 흩어져 있다. descriptor의 tuple_type(T_SINGLE_BOUND_ITEM, T_NORMAL, T_SORTKEY, T_MERGE)이 네 가지 qfile_save_*_tuple 콜백 중 하나를 고른다. 실행기 메인 루프 qexec_end_one_iteration이 쓰는 fast path가 이쪽이다.
  • qfile_fast_intint_tuple_to_list / qfile_fast_intval_tuple_to_list / qfile_fast_val_tuple_to_list — descriptor를 통째로 우회해서 값 1–2개짜리 튜플을 직접 쓰는 미세 최적화. 작은 고정 모양의 행을 자주 내보내는 성능 민감 경로(예: 병렬 코디네이터가 (worker_id, count)를 토해내는 경로)가 사용한다.
// qfile_save_normal_tuple — src/query/list_file.c (condensed)
static int
qfile_save_normal_tuple (QFILE_TUPLE_DESCRIPTOR * tuple_descr_p, char *tuple_p, char *page_p, int tuple_length)
{
  int total_tuple_value_size = 0, tuple_value_size;
  for (int i = 0; i < tuple_descr_p->f_cnt; i++)
    {
      if (qdata_copy_db_value_to_tuple_value (tuple_descr_p->f_valp[i], tuple_p, &tuple_value_size) != NO_ERROR)
        return ER_FAILED;
      total_tuple_value_size += tuple_value_size;
      tuple_p += tuple_value_size;
    }
  QFILE_PUT_TUPLE_LENGTH (page_p, tuple_length);
  return NO_ERROR;
}

qdata_copy_db_value_to_tuple_value가 필드마다 [flag, val_len, packed_bytes]를 쓰고 소비된 바이트 수를 반환한다. 모든 필드가 다 쓰이면 행의 맨 앞 4바이트 에 전체 튜플 길이를 도장 찍어 넣는다. 이걸로 소비자가 한 번에 다음 튜플로 점프할 수 있다.

큰 튜플 경로 — overflow 페이지

섹션 제목: “큰 튜플 경로 — overflow 페이지”

tuple_length > QFILE_MAX_TUPLE_SIZE_IN_PAGE(= DB_PAGESIZE - 32) 이면 writer는 overflow 경로를 탄다.

// qfile_add_tuple_to_list — overflow tail (condensed)
prev_page_p = cur_page_p;
for (offset = tuple_page_size, tuple_p = tuple + offset; offset < tuple_length;
     offset += tuple_page_size, tuple_p += tuple_page_size)
  {
    new_page_p = qfile_allocate_new_ovf_page (thread_p, list_id_p, cur_page_p, prev_page_p,
                                              tuple_length, offset, &tuple_page_size);
    if (new_page_p == NULL) /* error */
    memcpy ((char *) new_page_p + QFILE_PAGE_HEADER_SIZE, tuple_p, tuple_page_size);
    prev_page_p = new_page_p;
  }

첫 청크는 보통 튜플처럼 데이터 페이지에 안착하고, 그 이후 청크는 한 페이지에 한 청크씩 줄지어 들어가며, 이 줄은 데이터 페이지의 ovfl_pgid 에 매달린 체인이 된다. overflow 페이지는 QFILE_PUT_TUPLE_COUNT (page, QFILE_OVERFLOW_TUPLE_COUNT_FLAG)(= -2)로 표시되어, 소비자가 이걸 일반 페이지로 오인하지 않는다.

생산자 close

섹션 제목: “생산자 close”

qfile_close_list는 latch 해제 한 줄짜리 연산이다. 데이터는 이미 디스크(또는 membuf)에 다 있고, close가 하는 일은 살아 있는 writer 페이지의 latch를 풀어 다른 소비자나 다른 생산자가 fix할 수 있게 만드는 것뿐이다.

// qfile_close_list — src/query/list_file.c
void
qfile_close_list (THREAD_ENTRY * thread_p, QFILE_LIST_ID * list_id_p)
{
  if (list_id_p && list_id_p->last_pgptr != NULL)
    {
      QFILE_PUT_NEXT_VPID_NULL (list_id_p->last_pgptr);   /* terminate chain */
      qmgr_free_old_page_and_init (thread_p, list_id_p->last_pgptr, list_id_p->tfile_vfid);
    }
}

여기서 일어나는 체인 종료 쓰기 가 미묘하다. writer가 파일을 만들고 있는 동안 새로 할당된 페이지의 next_vpid는 LS_PUT_NEXT_VPID 매크로에 의해 NULL_PAGEID_IN_PROGRESS로 도장 찍혀 있었다(SERVER_MODE 한정). 이를 진짜 NULL_PAGEID로 마무리하는 것은 qfile_close_list 뿐이다. 이로써 비동기 / 스트리밍 모드의 소비자에게 “생산자가 끝났고 더 이상 페이지가 추가되지 않는다”는 신호가 전달된다. qfile_reopen_list_as_append_mode가 정반대 방향의 동작이다. 마지막 페이지를 다시 write latch로 fix해서 이후의 qfile_add_tuple_to_list 호출이 파일을 더 길게 늘릴 수 있게 만든다.

소비자 측 — scan

섹션 제목: “소비자 측 — scan”
// QFILE_LIST_SCAN_ID — src/query/query_list.h
struct qfile_list_scan_id
{
  SCAN_STATUS status;          /* S_OPENED / S_STARTED / S_ENDED / S_CLOSED */
  SCAN_POSITION position;      /* S_BEFORE / S_ON / S_AFTER */
  VPID curr_vpid;
  PAGE_PTR curr_pgptr;         /* live page latch */
  QFILE_TUPLE curr_tpl;        /* pointer into curr_pgptr */
  bool keep_page_on_finish;
  bool is_read_only;
  int curr_offset;
  int curr_tplno;
  QFILE_TUPLE_RECORD tplrec;   /* spliced buffer for overflow tuples */
  QFILE_LIST_ID list_id;       /* COPY of the list-file (independent cursor) */
};

스캔 안의 list_id는 생산자의 QFILE_LIST_ID의 복사본 이라는 점이 중요하다. 복사는 qfile_open_list_scan 안의 qfile_copy_list_id 가 한다. 덕분에 소비자의 read cursor가 생산자나 다른 소비자로부터 완전히 분리된다. 여러 reader가 같은 list file을 동시에 스캔할 수 있고, 각자 자기 curr_pgptr latch를 들고 있다. 수명은 그 아래의 QMGR_TEMP_FILE을 ref-counting(qfile_update_qlist_count)으로 관리해 서, 마지막 cursor가 close될 때까지 임시 파일이 파괴되지 않도록 한다.

Open

섹션 제목: “Open”
// qfile_open_list_scan — src/query/list_file.c
int
qfile_open_list_scan (QFILE_LIST_ID * list_id_p, QFILE_LIST_SCAN_ID * scan_id_p)
{
  scan_id_p->status   = S_OPENED;
  scan_id_p->position = S_BEFORE;
  scan_id_p->keep_page_on_finish = 0;
  scan_id_p->is_read_only = false;
  scan_id_p->curr_vpid.pageid = NULL_PAGEID;
  scan_id_p->curr_vpid.volid  = NULL_VOLID;
  QFILE_CLEAR_LIST_ID (&scan_id_p->list_id);


  if (qfile_copy_list_id (&scan_id_p->list_id, list_id_p, true, QFILE_SKIP_DEPENDENT) != NO_ERROR)
    return ER_FAILED;


  scan_id_p->tplrec.size = 0;
  scan_id_p->tplrec.tpl  = NULL;
  return NO_ERROR;
}

상태는 (S_OPENED, S_BEFORE, no-page-fixed) 로 시작한다. open만으로는 어떤 페이지도 fix하지 않는다. 첫 qfile_scan_list_next 호출이 들어와야 페이지가 잡힌다. 그 전까지는 open된 채로 비어 있는 cursor가 버퍼 풀에 어떤 비용도 발생시키지 않는다.

Next

섹션 제목: “Next”

qfile_scan_list_next는 얇은 wrapper다. 위치 머신인 qfile_scan_next 와 머터리얼라이저인 qfile_retrieve_tuple로 위임한다.

// qfile_scan_next — src/query/list_file.c (condensed)
static SCAN_CODE
qfile_scan_next (THREAD_ENTRY * thread_p, QFILE_LIST_SCAN_ID * scan_id_p)
{
  if (scan_id_p->position == S_BEFORE)
    {
      if (scan_id_p->list_id.tuple_cnt == 0) return S_END;
      /* fix first page, position cursor at first tuple */
      scan_id_p->curr_pgptr  = qmgr_get_old_page (thread_p, &scan_id_p->list_id.first_vpid,
                                                  scan_id_p->list_id.tfile_vfid);
      QFILE_COPY_VPID (&scan_id_p->curr_vpid, &scan_id_p->list_id.first_vpid);
      scan_id_p->curr_offset = QFILE_PAGE_HEADER_SIZE;
      scan_id_p->curr_tpl    = (char *) scan_id_p->curr_pgptr + QFILE_PAGE_HEADER_SIZE;
      scan_id_p->curr_tplno  = 0;
      scan_id_p->position    = S_ON;
      return S_SUCCESS;
    }
  else if (scan_id_p->position == S_ON)
    {
      /* still tuples on this page? */
      if (scan_id_p->curr_tplno < QFILE_GET_TUPLE_COUNT (scan_id_p->curr_pgptr) - 1)
        {
          scan_id_p->curr_offset += QFILE_GET_TUPLE_LENGTH (scan_id_p->curr_tpl);
          scan_id_p->curr_tpl    += QFILE_GET_TUPLE_LENGTH (scan_id_p->curr_tpl);
          scan_id_p->curr_tplno++;
          return S_SUCCESS;
        }
      /* page exhausted — follow next_vpid */
      else if (qfile_has_next_page (scan_id_p->curr_pgptr))
        {
          VPID next_vpid; QFILE_GET_NEXT_VPID (&next_vpid, scan_id_p->curr_pgptr);
          PAGE_PTR next_page_p = qmgr_get_old_page (thread_p, &next_vpid, scan_id_p->list_id.tfile_vfid);
          qmgr_free_old_page_and_init (thread_p, scan_id_p->curr_pgptr, scan_id_p->list_id.tfile_vfid);
          QFILE_COPY_VPID (&scan_id_p->curr_vpid, &next_vpid);
          scan_id_p->curr_pgptr  = next_page_p;
          scan_id_p->curr_tplno  = 0;
          scan_id_p->curr_offset = QFILE_PAGE_HEADER_SIZE;
          scan_id_p->curr_tpl    = (char *) scan_id_p->curr_pgptr + QFILE_PAGE_HEADER_SIZE;
          return S_SUCCESS;
        }
      else
        {
          scan_id_p->position = S_AFTER;
          if (!scan_id_p->keep_page_on_finish)
            qmgr_free_old_page_and_init (thread_p, scan_id_p->curr_pgptr, scan_id_p->list_id.tfile_vfid);
          return S_END;
        }
    }
  /* ... S_AFTER → S_END ... */
}

상태 머신은 예상한 그대로다. S_BEFORE → S_ON(첫 페이지 fix) → S_ON(같은 페이지 안에서 다음 튜플로, 또는 다음 페이지로) → S_AFTER / S_END(페이지 release). qfile_scan_list_prev는 대칭 연산이다. 튜플별 prev_tuple_length prefix로 한 칸 뒤로 가고, 페이지 헤더의 prev_pgid로 체인을 거꾸로 걷는다.

Retrieve — peek vs copy

섹션 제목: “Retrieve — peek vs copy”
// qfile_retrieve_tuple — src/query/list_file.c (condensed)
static SCAN_CODE
qfile_retrieve_tuple (THREAD_ENTRY * thread_p, QFILE_LIST_SCAN_ID * scan_id_p,
                      QFILE_TUPLE_RECORD * tuple_record_p, int peek)
{
  if (QFILE_GET_OVERFLOW_PAGE_ID (scan_id_p->curr_pgptr) == NULL_PAGEID)
    {
      if (peek) tuple_record_p->tpl = scan_id_p->curr_tpl;     /* zero-copy */
      else      memcpy (tuple_record_p->tpl, scan_id_p->curr_tpl, QFILE_GET_TUPLE_LENGTH (scan_id_p->curr_tpl));
    }
  else
    {
      /* tuple has overflow pages → splice into scan_id_p->tplrec */
      qfile_get_tuple_from_current_list (thread_p, scan_id_p, &scan_id_p->tplrec);
      tuple_record_p->tpl = scan_id_p->tplrec.tpl;
    }
  return S_SUCCESS;
}

peek = true는 zero-copy fast path다. 다음 advance 전에 튜플을 한 번 읽고 끝나는 곳 — 술어 평가, 프로젝션, 정렬 키 추출, 부분 튜플의 집합 멤버십 검사 등 — 이 모두 이걸 쓴다. 반환된 포인터는 다음 qfile_scan_list_next 호출까지만 유효하다(다음 호출이 페이지의 latch 를 풀 수 있기 때문). peek = false는 호출자 소유 버퍼로 복사하는 경로이며, 호출자가 다음 advance를 넘어 튜플을 들고 있어야 할 때 쓴다. 머지 조인이 외부 측을 진행시키면서 내부 측 현재 행을 기억하는 경로가 대표적이다.

overflow 튜플(QFILE_GET_OVERFLOW_PAGE_ID(curr_pgptr) != NULL_PAGEID) 에 대해서는 peek가 불가능하다. 바이트가 여러 페이지에 흩어져 있기 때문이다. 이 경우 qfile_get_tuple_from_current_list가 항상 그 바이트들을 스캔당 하나뿐인 tplrec 버퍼로 먼저 모은다.

집합 연산 — qfile_combine_two_list

섹션 제목: “집합 연산 — qfile_combine_two_list”

두 list file 사이의 UNION, INTERSECT, DIFFERENCE는 모두 같은 드라이버 하나로 처리된다. qfile_combine_two_list다. 큰 그림은 sort-merge에 가깝다. 튜플 단위 액션 콜백이 flag로 갈아 끼워진다.

flowchart TB
  A["qfile_combine_two_list(L, R, flag)"] --> B{"flag == UNION ALL?"}
  B -- "yes" --> U["qfile_union_list (L 복제, R append, 정렬 없음)"]
  B -- "no" --> S1["L을 모든 컬럼 기준 정렬 (Q_DISTINCT 또는 Q_ALL)"]
  S1 --> S2["R을 모든 컬럼 기준 정렬"]
  S2 --> O["dest list open"]
  O --> M{"action 콜백 선택"}
  M -- "INTERSECT" --> M1["act_both = qfile_add_one_tuple<br/>act_left = act_right = NULL"]
  M -- "DIFFERENCE" --> M2["act_left = qfile_add_tuple<br/>act_both = act_right = NULL"]
  M -- "UNION DISTINCT" --> M3["act_left = act_right = qfile_add_tuple<br/>act_both = qfile_add_one_tuple"]
  M -- "UNION ALL (post-sort)" --> M4["act_both = qfile_add_two_tuple<br/>(둘 다 복사)"]
  M1 --> L["merge loop: L의 top과 R의 top 비교<br/>cmp<0 → act_left, cmp==0 → act_both, cmp>0 → act_right"]
  M2 --> L
  M3 --> L
  M4 --> L
  L --> C["qfile_close_list (dest)"]

DISTINCT가 싸게 동작하는 비결은 qfile_advance_single 대신 qfile_advance_group을 쓰는 데 있다. _group이 같은 키를 가진 연속 구간을 비교 한 번 단위로 합친다. 따라서 양쪽 입력 모두에서 중복 행이 와도 출력에는 중복이 생기지 않는다.

qfile_union_list는 UNION ALL의 끝장 fast-path다. 정렬도 안 하고, 튜플도 일일이 보지 않는다. 두 번째 list의 페이지를 첫 번째 list의 끝에 물리적으로 이어 붙인다. 첫 번째 list 마지막 페이지의 next_vpid 를 두 번째 list 첫 페이지로 가리키도록 갈아끼울 뿐이다 (qfile_append_list).

정렬 wrapper — qfile_sort_list / qfile_sort_list_with_func

섹션 제목: “정렬 wrapper — qfile_sort_list / qfile_sort_list_with_func”

정렬은 list file의 원시 연산이 아니다. list file 하나를 받아 list file 하나를 내놓는 함수일 뿐이며, 그 함수의 본체는 external_sort를 콜백으로 감싸는 sandwich다.

// qfile_sort_list_with_func — src/query/list_file.c (condensed)
QFILE_LIST_ID *
qfile_sort_list_with_func (THREAD_ENTRY * thread_p, QFILE_LIST_ID * list_id_p, SORT_LIST * sort_list_p,
                           QUERY_OPTIONS option, int flag, SORT_GET_FUNC * get_func, SORT_PUT_FUNC * put_func,
                           SORT_CMP_FUNC * cmp_func, void *extra_arg, int limit, bool do_close,
                           int parallelism, ORDERBY_STATS * orderby_stats)
{
  qfile_close_list (thread_p, list_id_p);                       /* unlatch input writer */
  QFILE_LIST_ID *srlist_id = qfile_open_list (thread_p, &list_id_p->type_list, sort_list_p,
                                              list_id_p->query_id, flag, NULL);   /* output */


  QFILE_LIST_SCAN_ID t_scan_id; QFILE_SORT_SCAN_ID s_scan_id; SORT_INFO info;
  qfile_open_list_scan (list_id_p, &t_scan_id);
  qfile_initialize_sort_info (&info, list_id_p, sort_list_p);
  info.s_id = &s_scan_id; info.output_file = srlist_id; info.input_file = list_id_p;


  if (get_func == NULL) get_func = &qfile_get_next_sort_item;   /* default reader callback */
  if (put_func == NULL) put_func = &qfile_put_next_sort_item;   /* default writer callback */
  if (cmp_func == NULL) cmp_func = (info.key_info.use_original ? &qfile_compare_partial_sort_record
                                                               : &qfile_compare_all_sort_record);


  int sort_result = sort_listfile (thread_p, NULL_VOLID, estimated_pages, get_func, &info,
                                   put_func, &info, cmp_func, &info.key_info,
                                   (option == Q_DISTINCT ? SORT_ELIM_DUP : SORT_DUP),
                                   limit, srlist_id->tfile_vfid->tde_encrypted, parallel_type);
  /* ... destroy input list_id_p, copy srlist_id over list_id_p ... */
  return list_id_p;
}

콜백 셋이 external_sort를 list file에 끼워 맞춘다.

  • get_func — external_sort가 다음 입력 레코드를 읽을 때 호출 한다. 기본값은 qfile_get_next_sort_item으로, 입력 스캔에서 튜플을 하나 가져와 정렬 키 컬럼을 SORT_REC에 복사한다.
  • put_func — external_sort가 정렬된 레코드를 내보낼 때 호출한다. 기본값은 qfile_put_next_sort_item으로, SORT_REC을 다시 튜플로 디코드한 뒤 출력 list file에 qfile_add_tuple_to_list로 더한다. 집계 연산은 이걸 qexec_gby_put_next로 갈아끼워서(정렬 기반 GROUP BY) 출력될 튜플이 곧바로 누적기에 접히도록 만든다.
  • cmp_func — external_sort가 두 SORT_REC을 비교할 때 호출한다. 기본값은 qfile_compare_all_sort_record(전체 키 비교) 또는 qfile_compare_partial_sort_record(정렬 키가 원본 튜플의 prefix 일 때).
flowchart LR
  subgraph CONS["CUBRID list-file"]
    LIN["unsorted list-file<br/>(QFILE_LIST_ID)"]
    LSCAN["QFILE_LIST_SCAN_ID<br/>(input cursor)"]
    LOUT["sorted list-file<br/>(QFILE_LIST_ID)"]
  end
  subgraph EXT["external_sort.c"]
    GETFN["get_func →<br/>qfile_get_next_sort_item"]
    PUTFN["put_func →<br/>qfile_put_next_sort_item"]
    CMPFN["cmp_func →<br/>qfile_compare_∗_sort_record"]
    INPHASE["IN-PHASE:<br/>build sorted runs<br/>in sort buffer"]
    EXPHASE["EX-PHASE:<br/>k-way merge runs<br/>through sort buffer"]
  end
  LIN --> LSCAN
  LSCAN --> GETFN
  GETFN --> INPHASE
  INPHASE --> EXPHASE
  EXPHASE --> CMPFN
  EXPHASE --> PUTFN
  PUTFN --> LOUT

external_sort 자체도 sort buffer가 차면 자신의 FILE_TEMP 파일들로 run을 spill한다. list file의 membuf-then-FILE_TEMP와는 별개의 spill 기반이다. list file은 운반 계층이고, 정렬은 알고리즘이다.

타입 리스트 추론과 실행기 바인딩

섹션 제목: “타입 리스트 추론과 실행기 바인딩”

list file이 자기 컬럼 타입을 들고 있는 자리는 type_list.domp 의 TP_DOMAIN * 배열이다. 실행기는 이 배열을 생산자 XASL의 outptr_list 에서 만들어 낸다.

flowchart LR
  X["xasl_node<br/>type=BUILDLIST_PROC"] --> O["outptr_list<br/>(REGU_VARIABLE list)"]
  O --> R["각 REGU_VARIABLE은<br/>domain (TP_DOMAIN*)을 가짐"]
  R --> T["pt_node_to_db_domain 또는<br/>regu_variable_get_domain"]
  T --> TL["QFILE_TUPLE_VALUE_TYPE_LIST<br/>(domp[], type_cnt)"]
  TL --> Q["qfile_open_list(..., &type_list, ...)"]
  Q --> L["새 QFILE_LIST_ID<br/>type_list.domp = deep copy"]

qfile_open_list의 deep copy는 의도적이다. 원본 도메인은 파서 트리 arena 위에 있을 수 있고(질의 실행이 끝나기 전에 해제될 수 있다), list file은 그보다 오래 살아남아야 하므로 자기 사본이 있어야 한다. list가 파괴될 때 qfile_clear_list_id가 type_list.domp를 free_and_init한다.

qfile_unify_types는 두 list file을 합치거나 한쪽을 다른 쪽에 append 할 때 두 타입 리스트를 화해시킨다. 양쪽 domp[] 배열을 함께 걸으며 tp_domain_resolve_value로 LUB(least upper bound) 도메인을 고른다. SELECT 'abc' UNION SELECT 1이 VARCHAR 도메인의 컬럼 위에서 정수 행이 강제 형 변환되는 스트림으로 변하는 자리가 여기다.

qfile_modify_type_list는 더 가벼운 재구성기다. 실행기가 자기가 원하는 타입 리스트를 이미 알고 있고, outptr_list로부터 자동 유도된 것을 덮어쓰기만 하면 되는 경우(예: 빌드 컬럼이 부분 집합인 해시 조인 빌드 측)에 쓴다.

둘러싼 XASL과 묶인 수명

섹션 제목: “둘러싼 XASL과 묶인 수명”

list file은 한 XASL 실행 동안 정확히 하나의 XASL 노드 가 소유한다. 소유 노드는 그 list file을 qfile_open_list로 만들어낸 노드이고, 결과 는 xasl->list_id에 저장된다. 실행기의 qexec_clear_xasl_head가 (qexec_clear_xasl이 XASL 트리를 정리하면서) 모든 노드를 돌며 다음을 호출한다.

// qexec_clear_xasl_head excerpt — src/query/query_executor.c
if (xasl->list_id && !xasl->list_id->is_result_cached)
  {
    (void) qfile_close_list (thread_p, xasl->list_id);
    qfile_destroy_list (thread_p, xasl->list_id);
  }

두 가지 의미가 있다.

  1. 소비된 sub-block의 list file은 소비자 XASL과 함께 죽는다. BUILDLIST_PROC 자식 XASL의 list_id는 qexec_open_scan 시점에 한 번 머터리얼라이즈되고, 부모는 S_LIST_SCAN으로 그걸 읽다가, 부모 XASL 트리가 정리될 때 함께 파괴된다. GC는 없다. 수명은 스택 모양이다.
  2. 결과 캐시된 list file은 질의 경계를 넘어 살아남는다. is_result_cached가 true면 list file의 소유주가 list-file 캐시(QFILE_LIST_CACHE_ENTRY)로 옮겨간다. XASL 트리는 헐려 나가도 list file은 남는다. 캐시가 evict하기로 결정할 때 (qfile_clear_list_cache)까지.
sequenceDiagram
  autonumber
  participant E as Query (executor)
  participant X as Parent XASL (BUILDLIST_PROC)
  participant SX as Sub-XASL (BUILDLIST_PROC)
  participant LF as list-file (sub-XASL.list_id)
  E->>X: qexec_execute_mainblock(parent)
  X->>SX: qexec_execute_mainblock(sub) (예: aptr_list)
  SX->>LF: qfile_open_list (TEMP_FILE_MEMBUF_NORMAL)
  loop sub-XASL이 튜플 생산
    SX->>LF: qfile_generate_tuple_into_list (T_NORMAL)
  end
  SX->>LF: qfile_close_list
  X->>LF: scan_open_list_scan (S_LIST_SCAN)
  loop 부모가 튜플 소비
    X->>LF: qfile_scan_list_next (peek)
  end
  X->>LF: qfile_close_scan
  E->>X: qexec_clear_xasl (트리 정리)
  X->>LF: qfile_close_list + qfile_destroy_list (sub-XASL.list_id)

캐싱 경로 — QFILE_LIST_CACHE_ENTRY

섹션 제목: “캐싱 경로 — QFILE_LIST_CACHE_ENTRY”

list-file 캐시는 XASL-cache 엔트리당 하나의 해시 테이블이며, 한 질의 전체의 결과를 파라미터 값(DB_VALUE_ARRAY)으로 키 잡아 메모이제 이션한다. qfile_lookup_list_cache_entry에서 hit이면 이전에 만들어 두고 아직 파괴되지 않은 list file을 list_id로 들고 있는 QFILE_LIST_CACHE_ENTRY가 돌아온다.

// qfile_lookup_list_cache_entry — src/query/list_file.c (condensed)
QFILE_LIST_CACHE_ENTRY *
qfile_lookup_list_cache_entry (THREAD_ENTRY * thread_p, XASL_CACHE_ENTRY * xasl,
                               const DB_VALUE_ARRAY * params, bool * result_cached)
{
  *result_cached = false;
  if (QFILE_IS_LIST_CACHE_DISABLED) return NULL;
  if (qfile_List_cache.n_hts == 0)  return NULL;


  csect_enter (thread_p, CSECT_QPROC_LIST_CACHE, INF_WAIT);
  if (xasl->list_ht_no < 0) xasl->list_ht_no = qcache_get_new_ht_no (thread_p);


  QFILE_LIST_CACHE_ENTRY *lent = mht_get (qfile_List_cache.list_hts[xasl->list_ht_no], params);
  qfile_List_cache.lookup_counter++;
  if (lent && !lent->deletion_marker)
    {
      *result_cached = true;
      /* register tran_index, bump ref_count + time_last_used */
    }
  csect_exit (thread_p, CSECT_QPROC_LIST_CACHE);
  return *result_cached ? lent : NULL;
}

질의 실행 시작 시점에 캐시 hit이 발견되면 실행기는 머터리얼라이즈를 건너뛴다. 캐시된 list_id가 그대로 결과로 사용되고, XASL 트리 자체의 list file은 만들어지지 않는다. 질의 실행이 끝났고 캐싱 조건이 맞으면 (트리거가 발화되지 않았고, autocommit 경계 문제가 없는 등), qfile_update_list_cache_entry가 생산 list file을 새 캐시 엔트리로 복제한다. eviction은 표준적인 TTL + LRU(time_last_used, ref_count) 와 용량 한도(PRM_ID_LIST_MAX_QUERY_CACHE_PAGES)를 qfile_list_cache_cleanup이 결합해 처리한다.

XASL 캐시와의 관계는 명확하다. 모든 list-cache 엔트리는 어떤 XASL-cache 엔트리에 종속된다. XASL 캐시가 어떤 plan을 evict하면 qfile_clear_list_cache가 그 XASL의 list-cache 엔트리들을 모두 함께 지운다. 이 덕분에 list-cache 엔트리가 stale plan을 가리키는 일이 발생하지 않는다.

소스 코드 가이드

섹션 제목: “소스 코드 가이드”

이 섹션은 list-file 모듈로 cross-reference를 만들 때 anchor로 삼아야 할 심볼들의 명단이다. 그룹 순서는 ## CUBRID의 구현에서 따라간 생산자 / 소비자 / 집합 연산 / 정렬 / 캐시 / 수명 순서와 일치한다.

타입과 매크로 (query_list.h)

섹션 제목: “타입과 매크로 (query_list.h)”
  • QFILE_LIST_ID — 튜플 스트림 식별자.
  • QFILE_LIST_SCAN_ID — 소비자 cursor.
  • QFILE_PAGE_HEADER(32바이트) 와 오프셋 매크로: QFILE_TUPLE_COUNT_OFFSET, QFILE_PREV_PAGE_ID_OFFSET, QFILE_NEXT_PAGE_ID_OFFSET, QFILE_LAST_TUPLE_OFFSET, QFILE_OVERFLOW_PAGE_ID_OFFSET, QFILE_PREV_VOL_ID_OFFSET, QFILE_NEXT_VOL_ID_OFFSET, QFILE_OVERFLOW_VOL_ID_OFFSET.
  • 튜플 포맷 매크로: QFILE_TUPLE_LENGTH_SIZE(= 8 — 두 길이 prefix 합), QFILE_TUPLE_VALUE_HEADER_SIZE(= 8), QFILE_MAX_TUPLE_SIZE_IN_PAGE, QFILE_GET_TUPLE_LENGTH, QFILE_GET_PREV_TUPLE_LENGTH, QFILE_GET_TUPLE_VALUE_FLAG, QFILE_GET_TUPLE_VALUE_LENGTH, QFILE_GET_TUPLE_VALUE_HEADER_POSITION.
  • 스트림 flag enum: QFILE_FLAG_RESULT_FILE, QFILE_FLAG_UNION, QFILE_FLAG_INTERSECT, QFILE_FLAG_DIFFERENCE, QFILE_FLAG_ALL, QFILE_FLAG_DISTINCT, QFILE_FLAG_USE_KEY_BUFFER, QFILE_NOT_USE_MEMBUF.
  • 정렬 메타데이터: SORT_LIST, SORT_TYPE, SORT_ORDER, SORT_NULLS, QFILE_SORTED_LIST_ID, QFILE_SORT_SCAN_ID.
  • 단일 튜플 타입 enum: QFILE_TUPLE_TYPE(T_SINGLE_BOUND_ITEM, T_NORMAL, T_SORTKEY, T_MERGE).
  • overflow 페이지용 특수 flag: QFILE_OVERFLOW_TUPLE_COUNT_FLAG(= -2).

Open / write / close

섹션 제목: “Open / write / close”
  • qfile_initialize / qfile_finalize — 모듈 단위 셋업. qfile_sort_list_Freelist(SORT_LIST 레코드 lock-free freelist) 와 qfile_Max_tuple_page_size 상수를 만든다.
  • qfile_open_list — 생성자. QFILE_LIST_ID 할당, TEMP_FILE_MEMBUF_NORMAL / _KEY_BUFFER / result-file 기반 선택, 타입 리스트 deep copy, DISTINCT면 옵션 sort list 구성.
  • qfile_close_list — next_vpid 체인 종료, 살아 있는 writer 페이지 unfix.
  • qfile_reopen_list_as_append_mode — 마지막 페이지를 write latch로 재 fix. UNION ALL fast-path append가 사용한다.
  • qfile_get_first_page — 첫 데이터 페이지를 즉시 할당. 외부 코드가 튜플 추가 전에 첫 VPID를 알아야 할 때 쓴다.
  • qfile_destroy_list — 임시 파일 저장소를 해제. dependent_list_id 로 재귀.
  • qfile_free_list_id / QFILE_FREE_AND_INIT_LIST_ID — QFILE_LIST_ID struct와 그 소유 배열 해제.
  • qfile_clear_list_id — struct 비우고 type_list.domp / sort_list / tpl_descr.f_valp 해제(임시 파일 본체는 그대로 둠). 소유권 이전용.
  • qfile_copy_list_id / qfile_clone_list_id — QFILE_DEPENDENT_MODE 로 dependent_list_id를 따라갈지 말지 정해서 식별자 복제.

튜플 쓰기 경로

섹션 제목: “튜플 쓰기 경로”
  • qfile_add_tuple_to_list — 직렬화된 QFILE_TUPLE을 append. oversize 튜플은 overflow 페이지로 처리.
  • qfile_generate_tuple_into_list — QFILE_TUPLE_DESCRIPTOR 로부터 append. qfile_save_normal_tuple / _single_bound_item_tuple / _sort_key_tuple / _merge_tuple 중 하나를 디스패치.
  • qfile_save_tuple — 네 콜백 디스패처 진입점.
  • qfile_fast_intint_tuple_to_list / qfile_fast_intval_tuple_to_list / qfile_fast_val_tuple_to_list — 알려진 작은 모양을 descriptor 를 우회.
  • qfile_add_item_to_list — 단일 컬럼 편의 래퍼.
  • qfile_add_overflow_tuple_to_list — 이미 overflow를 가진 튜플을 한 list-file에서 다른 list-file로 그대로 복사.
  • qfile_add_tuple_get_pos_in_list — append + 방금 쓴 튜플의 QFILE_TUPLE_POSITION 반환. 해시 조인 빌드가 키별 행 위치를 기록할 때 쓴다.

페이지 할당 헬퍼 (static)

섹션 제목: “페이지 할당 헬퍼 (static)”
  • qfile_allocate_new_page — qmgr_get_new_page로 새 페이지를 fix 하고 prev/next를 잇고 체인 포인터를 QFILE_LIST_ID에 복사.
  • qfile_allocate_new_ovf_page — overflow 페이지 버전.
  • qfile_allocate_new_page_if_need — 모든 튜플 쓰기 경로가 진입하는 분기 게이트.
  • qfile_add_tuple_to_list_id — 쓰기 후 사후 정리(tuple_cnt, last_offset, lasttpl_len 진행).
  • qfile_initialize_page_header — 새 페이지 헤더 zero-init.
  • qfile_set_dirty_page / qfile_set_dirty_page_and_skip_logging dirty 표시 + WAL 경유 또는 (FILE_TEMP은 복구 대상 아님으로) 로깅 생략.

Scan 경로

섹션 제목: “Scan 경로”
  • qfile_open_list_scan — QFILE_LIST_SCAN_ID 초기화, list_id deep copy.
  • qfile_scan_list_next — qfile_scan_list (qfile_scan_next, ...) 래퍼.
  • qfile_scan_list_prev — qfile_scan_list (qfile_scan_prev, ...) 래퍼.
  • qfile_close_scan — 살아 있는 page latch 해제, 스캔별 tplrec 해제, 스캔 로컬 list_id deep clear.
  • qfile_save_current_scan_tuple_position / qfile_jump_scan_tuple_position — 책갈피와 seek. 해시 조인 빌드가 키별 행 위치 저장하고 probe가 거기로 점프할 때 쓴다.
  • qfile_start_scan_fix / qfile_end_scan_fix — 서브 호출 동안 cursor를 잃지 않도록 현재 페이지를 pin/unpin.
  • qfile_get_tuple — QFILE_TUPLE_POSITION 으로 단일 튜플 조회 (overflow 튜플의 전체 바이트 머터리얼라이즈 용도).
  • qfile_overwrite_tuple — 튜플 바이트의 in-place 재작성. 작업 버퍼로 쓰는 list-file에서 UPDATE형 변경(드물다).
  • qfile_set_tuple_column_value — 좁은 in-place 컬럼 갱신.

Static 상태 머신 헬퍼

섹션 제목: “Static 상태 머신 헬퍼”
  • qfile_scan_next / qfile_scan_prev — S_BEFORE / S_ON / S_AFTER 위치 머신.
  • qfile_retrieve_tuple — 위치를 잡은 뒤의 peek vs copy 머터리얼 라이즈.
  • qfile_get_tuple_from_current_list — overflow 튜플 바이트를 overflow 페이지 체인에서 끌어와 스캔의 tplrec에 합쳐 넣는다.

집합 연산과 append

섹션 제목: “집합 연산과 append”
  • qfile_combine_two_list — UNION / INTERSECT / DIFFERENCE 드라이버. 입력 정렬(UNION ALL fast-path 제외) → dest open → action 콜백을 끼운 sort-merge.
  • qfile_union_list(static, UNION ALL용으로 qfile_combine_two_list 가 부름) — qfile_clone_list_id + qfile_reopen_list_as_append_mode
    • qfile_copy_tuple(꼬리 처리)로 페이지 체인 splice.
  • qfile_append_list — 물리적 페이지 체인 연장(튜플 반복 없음).
  • qfile_connect_list — 자식 dependent_list_id를 부모에 매달아 파괴를 cascade.
  • qfile_truncate_list — 모든 튜플 drop, QFILE_LIST_ID는 재사용 가능 상태로 유지.
  • qfile_advance_single / qfile_advance_group(static) — merge 중 한 레코드 또는 한 그룹 진행.
  • qfile_add_one_tuple / qfile_add_two_tuple(static) — qfile_combine_two_list가 merge에 끼우는 action 콜백.
  • qfile_compare_tuple_helper(static) — merge용 행 전체 비교.
  • qfile_unify_types — 양쪽 컬럼 도메인 화해.

정렬 wrapper

섹션 제목: “정렬 wrapper”
  • qfile_sort_list — QUERY_OPTIONS(Q_DISTINCT vs Q_ALL)로 flag만 고르는 좁은 래퍼.
  • qfile_sort_list_with_func — 호출자가 get_func / put_func / cmp_func을 직접 공급하는 풀 파워 진입점. query_executor.c의 정렬 기반 GROUP BY가 쓴다(별도 cubrid-post-processing.md 참고).
  • qfile_make_sort_key / qfile_generate_sort_tuple — 튜플을 SORT_REC 안팎으로 변환.
  • qfile_compare_partial_sort_record / qfile_compare_all_sort_record — 기본 cmp_func.
  • qfile_initialize_sort_key_info / qfile_clear_sort_key_info — SORT_LIST로부터 SORTKEY_INFO 빌드/해제.
  • qfile_initialize_sort_info / qfile_clear_sort_info(static) — SORT_INFO 빌드/해제.
  • qfile_get_next_sort_item / qfile_put_next_sort_item(static) external_sort 기본 콜백.
  • qfile_get_estimated_pages_for_sorting — external_sort가 run 수를 추정하기 위한 입력.

List-file (질의 결과) 캐시

섹션 제목: “List-file (질의 결과) 캐시”
  • qfile_initialize_list_cache / qfile_finalize_list_cache — 모듈 셋업 (qfile_List_cache 전역 + 해시 테이블 풀).
  • qfile_lookup_list_cache_entry — (xasl_cache_entry, params) 로 hit-or-miss probe.
  • qfile_update_list_cache_entry — insert. 캐싱을 opt-in한 질의가 완료될 때 호출.
  • qfile_clear_list_cache — 특정 XASL 캐시 엔트리에 매달린 모든 list-cache 엔트리 무효화.
  • qfile_end_use_of_list_cache_entry — 트랜잭션의 참조 1 감소. ref_count → 0이면 evict 가능.
  • qfile_list_cache_cleanup(static) — PRM_ID_LIST_MAX_QUERY_CACHE_PAGES 기반 LRU + TTL 청소.
  • qfile_clear_uncommited_list_cache_entry — abort된 트랜잭션의 캐시 엔트리 정리(다른 트랜잭션이 못 봄).
  • qfile_allocate_list_cache_entry / qfile_free_list_cache_entry 풀 기반 할당(qfile_List_cache_entry_pool).
  • qfile_print_list_cache_entry / qfile_dump_list_cache_internal 진단.
  • qfile_hash_db_value_array / qfile_compare_equal_db_value_array — 해시 테이블 키 함수.

저장소 측 기반

섹션 제목: “저장소 측 기반”
  • QMGR_TEMP_FILE(query_manager.h) — (membuf[], membuf_last, membuf_npages, temp_vfid, temp_file_type, tde_encrypted) 를 감싼다.
  • qmgr_create_new_temp_file(query_manager.c) — 새 membuf를 깎아 QMGR_TEMP_FILE 생성.
  • qmgr_create_result_file — 동일하지만 임시 파일이 보존 되도록 flag 처리(생산 질의보다 오래 살아남아 클라이언트가 가져감).
  • qmgr_get_new_page(query_manager.c) — append 시 membuf vs FILE_TEMP 중재.
  • qmgr_get_old_page / qmgr_get_old_page_read_only — read 시 중재.
  • qmgr_free_old_page_and_init — fix된 페이지 해제(membuf는 no-op, FILE_TEMP은 pgbuf_unfix).
  • qmgr_free_list_temp_file — QMGR_TEMP_FILE 파괴(qfile_destroy_list 에서 호출).
  • qmgr_get_external_file_page(static) — temp_vfid를 file_alloc, PAGE_QRESULT ptype 설정.
  • file_create_temp(file_manager.c) — FILE_TEMP VFID 할당. spill의 실제 기반.
  • file_temp_retire — FILE_TEMP을 tempcache로 반납.
  • xqfile_get_list_file_page — 질의 결과의 서버→클라이언트 페이지 전송.

query_executor.c 안의 cross-reference

섹션 제목: “query_executor.c 안의 cross-reference”
  • qexec_end_one_iteration — 외부 블록 술어를 통과한 각 행마다 qfile_generate_tuple_into_list (T_NORMAL) 호출.
  • qexec_clear_xasl / qexec_clear_xasl_head — 모든 XASL의 list_id를 qfile_close_list + qfile_destroy_list 호출(단, is_result_cached이면 제외).
  • qexec_orderby_distinct — qfile_sort_list 호출.
  • qexec_groupby / qexec_hash_gby_finalize — 정렬 기반은 qfile_sort_list_with_func + qexec_gby_put_next, 해시 기반은 qexec_hash_gby_agg_tuple로 해시 빌드. 결과 list-file은 해시 spill 산물이다.
  • qexec_execute_analytic — analytic 입력을 qfile_sort_list
    • 보조 list file들(group_list_id, value_list_id — 윈도 함수 상태)을 같이 운용.
  • xqmgr_execute_query / qmgr_process_query — 최상위 QFILE_LIST_ID를 보유하고 query manager에 등록하는 진입점.

scan_manager.c 안의 cross-reference

섹션 제목: “scan_manager.c 안의 cross-reference”
  • scan_open_list_scan — QFILE_LIST_SCAN_ID를 만든 뒤 LLIST_SCAN_ID + S_LIST_SCAN 타입의 SCAN_ID로 감싼다. 이 덕분에 list-file이 실행기 입장에서 일반 스캔 연산자처럼 보이게 된다.
  • scan_next_scan_local(S_LIST_SCAN 케이스) → scan_next_list_scan qfile_scan_list_next로 한 튜플을 가져온 뒤 regu_list_pred / regu_list_rest를 평가.
  • scan_init_scan_id / scan_init_scan_pred — 모든 스캔 타입이 공유하는 일반 scan-id 초기화.

위치 힌트 (2026-05-01 기준, /data/hgryoo/references/cubrid 워크트리)

섹션 제목: “위치 힌트 (2026-05-01 기준, /data/hgryoo/references/cubrid 워크트리)”
심볼파일라인
qfile_page_header (struct)src/query/query_list.h66
qfile_list_id (struct)src/query/query_list.h425
qfile_list_scan_id (struct)src/query/query_list.h498
qfile_initializesrc/query/list_file.c1156
qfile_finalizesrc/query/list_file.c1178
qfile_open_listsrc/query/list_file.c1203
qfile_close_listsrc/query/list_file.c1352
qfile_reopen_list_as_append_modesrc/query/list_file.c1373
qfile_allocate_new_pagesrc/query/list_file.c1465
qfile_allocate_new_ovf_pagesrc/query/list_file.c1526
qfile_allocate_new_page_if_needsrc/query/list_file.c1561
qfile_add_tuple_to_list_idsrc/query/list_file.c1592
qfile_add_tuple_to_listsrc/query/list_file.c1610
qfile_save_single_bound_item_tuplesrc/query/list_file.c1672
qfile_save_normal_tuplesrc/query/list_file.c1695
qfile_save_sort_key_tuplesrc/query/list_file.c1715
qfile_save_merge_tuplesrc/query/list_file.c1751
qfile_save_tuplesrc/query/list_file.c1804
qfile_generate_tuple_into_listsrc/query/list_file.c1848
qfile_fast_intint_tuple_to_listsrc/query/list_file.c1908
qfile_fast_intval_tuple_to_listsrc/query/list_file.c1968
qfile_fast_val_tuple_to_listsrc/query/list_file.c2055
qfile_add_overflow_tuple_to_listsrc/query/list_file.c2138
qfile_get_first_pagesrc/query/list_file.c2218
qfile_destroy_listsrc/query/list_file.c2269
xqfile_get_list_file_pagesrc/query/list_file.c2312
qfile_add_item_to_listsrc/query/list_file.c2442
qfile_combine_two_listsrc/query/list_file.c2688
qfile_append_listsrc/query/list_file.c2953
qfile_connect_listsrc/query/list_file.c3130
qfile_truncate_listsrc/query/list_file.c3210
qfile_union_list (static)src/query/list_file.c3359
qfile_make_sort_keysrc/query/list_file.c3507
qfile_generate_sort_tuplesrc/query/list_file.c3643
qfile_get_next_sort_itemsrc/query/list_file.c3729
qfile_put_next_sort_itemsrc/query/list_file.c3765
qfile_compare_partial_sort_recordsrc/query/list_file.c3925
qfile_compare_all_sort_recordsrc/query/list_file.c4003
qfile_initialize_sort_key_infosrc/query/list_file.c4145
qfile_clear_sort_key_infosrc/query/list_file.c4243
qfile_initialize_sort_infosrc/query/list_file.c4266
qfile_clear_sort_info (static)src/query/list_file.c4290
qfile_sort_list_with_funcsrc/query/list_file.c4331
qfile_sort_listsrc/query/list_file.c4482
qfile_copy_list_pages (static)src/query/list_file.c4509
qfile_duplicate_listsrc/query/list_file.c4626
qfile_get_tuplesrc/query/list_file.c4663
qfile_get_tuple_from_current_list (static)src/query/list_file.c4738
qfile_scan_next (static)src/query/list_file.c4762
qfile_scan_prev (static)src/query/list_file.c4865
qfile_save_current_scan_tuple_positionsrc/query/list_file.c4959
qfile_retrieve_tuple (static)src/query/list_file.c4971
qfile_jump_scan_tuple_positionsrc/query/list_file.c5033
qfile_start_scan_fixsrc/query/list_file.c5124
qfile_open_list_scansrc/query/list_file.c5162
qfile_scan_list (static)src/query/list_file.c5206
qfile_scan_list_nextsrc/query/list_file.c5229
qfile_scan_list_prevsrc/query/list_file.c5243
qfile_end_scan_fixsrc/query/list_file.c5257
qfile_close_scansrc/query/list_file.c5279
qfile_initialize_list_cachesrc/query/list_file.c5400
qfile_finalize_list_cachesrc/query/list_file.c5521
qfile_clear_list_cachesrc/query/list_file.c5570
qfile_lookup_list_cache_entrysrc/query/list_file.c6035
qfile_update_list_cache_entrysrc/query/list_file.c6196
qfile_end_use_of_list_cache_entrysrc/query/list_file.c6419
qfile_add_tuple_get_pos_in_listsrc/query/list_file.c6559
qfile_has_next_pagesrc/query/list_file.c6636
qfile_update_domains_on_type_listsrc/query/list_file.c6648
qfile_set_tuple_column_valuesrc/query/list_file.c6740
qfile_overwrite_tuplesrc/query/list_file.c6868
qfile_update_qlist_countsrc/query/list_file.c7041
qfile_collect_list_sector_infosrc/query/list_file.c7085
qfile_free_list_sector_infosrc/query/list_file.c7181
qmgr_create_new_temp_filesrc/query/query_manager.c2954
qmgr_get_new_pagesrc/query/query_manager.c2822
qmgr_get_external_file_page (static)src/query/query_manager.c2912
qmgr_init_external_file_page (static)src/query/query_manager.c2890
scan_open_list_scansrc/query/scan_manager.c3715

소스 검증 노트

섹션 제목: “소스 검증 노트”
  • cubrid-query-executor.md와의 비교 — 그 문서는 list-file을 모든 BUILDLIST_PROC의 머터리얼라이즈 출력으로 명명하고, qexec_end_one_iteration이 qfile_generate_tuple_into_list (T_NORMAL)로 쓴다고 단정한다. 이 워크트리 query_executor.c 1262 라인 근처에서 검증 완료. qexec_hash_gby_agg_tuple을 통한 fast-path 분기(g_hash_eligible이 켜진 경우)는 spill 경로일 때만 qfile_generate_tuple_into_list로 빠진다. in-memory 해시 테이블은 튜플을 list-file이 아니라 AGGREGATE_HASH_CONTEXT 안에 들고 있다. spill 발생 시의 list-file은 agg_hash_context->part_list_id 로, 스트리밍 파이프가 아닌 해시 spill 기반 으로 사용되는 list-file이다.
  • cubrid-post-processing.md와의 비교 — 그 문서는 정렬 기반 GROUP BY와 ORDER BY의 진입을 qfile_sort_list로, UNION / INTERSECT / DIFFERENCE의 드라이버를 qfile_combine_two_list로 명명한다. 둘 다 검증 완료. 후처리 문서는 또한 실제 정렬 커널을 external_sort.c::sort_listfile로 명시한다. list-file은 입출력 운반 계층 이고, 정렬은 external_sort의 일 이다. 둘 사이의 경계는 sort_listfile의 콜백 계약 (get_func / put_func / cmp_func)이다. ## CUBRID의 구현의 qfile_sort_list_with_func 설명을 참고.
  • cubrid-page-buffer-manager.md와의 비교 — list-file 페이지가 FILE_TEMP으로 spill되는 순간, 그 페이지는 일반 데이터베이스 페이지가 된다. pgbuf_fix / pgbuf_unfix를 그대로 거치며, ptype은 PAGE_QRESULT다. 다시 말해 list-file의 spill 페이지는 heap이나 B-tree 페이지와 같은 LRU에서 슬롯을 두고 경쟁한다. 반면 membuf 페이지는 page buffer pool에 전혀 들어가 있지 않다. qmgr_allocate_tempfile_with_buffer가 raw malloc으로 만든 메모리일 뿐이다. 이 두 단계 설계 덕분에 작은 list-file은 사실상 공짜이고(pgbuf 슬롯을 점유하지 않음), 큰 list-file은 spill된 이후에야 page-buffer의 시민이 된다.
  • MVCC와의 상호작용. list-file은 질의 사적이다. 다른 트랜잭션 이 그 내용을 보지 못한다. 튜플이 list-file로 들어가는 시점의 visibility는 생산 스캔 쪽에서 처리된다(heap_get_visible_version 와 scan_next_heap_scan이 친구들이다). 일단 list-file에 들어간 튜플은 이 질의 입장에서는 commit된 상태 다. list-file 단위 MVCC는 없다. 이 때문에 트랜잭션 안에서 외부 스캔이 일찍 실행되고 머터리얼라이즈된 list-file이 같은 트랜잭션 후반에 읽힐 때, 그 사이에 base heap이 갱신되더라도 같은 튜플 을 두 번 보게 된다. 단일 statement 안에서는 이것이 우리가 원하는 snapshot 안정성이다. cursor(HOLDABLE cursor)의 경우 commit을 넘어 살아남는 것은 결과 list-file뿐이고, 따라서 commit 경계 너머에서도 자연스레 snapshot 안정적이다.
  • WAL. FILE_TEMP 위의 list-file 페이지는 qfile_set_dirty_page 를 쓰며, 인덱스 키 버퍼 모드에서는 qfile_set_dirty_page_and_skip_logging 을 쓴다. FILE_TEMP 파일은 복구 대상이 아니므로 이 페이지에 대한 로그 레코드는 불필요하고, CUBRID는 가능한 곳에서 로깅을 건너뛴다. 크래시가 나면 tempcache가 통째로 비워지고, 진행 중 이었던 질의는 단순히 클라이언트에서 다시 시작된다. PostgreSQL이 BufFile를, SQL Server가 TempDB minimal logging를 똑같이 내리는 트레이드오프다. 임시 튜플 스트림은 WAL 비용을 지불하지 않지만, 크래시 시 재실행을 한 번 더 한다.
  • 이름 충돌 주의. list-file 캐시(QFILE_LIST_CACHE_ENTRY)는 XASL 캐시(XASL_CACHE_ENTRY)와 다르다. 둘은 연결되어 있지만 분리된다. XASL 캐시는 plan을 메모이제이션하고, list-file 캐시는 그 plan의 실행 결과 를 메모이제이션한다. 결과 캐시 hit는 실행을 건너뛰게 하고, plan 캐시 hit는 parse-and-optimise를 건너뛰게 한다. 결과 캐시 엔트리는 XASL 캐시 엔트리(xcache_entry)에 대한 back pointer를 들고 있어서, XASL eviction이 자동으로 list-cache eviction 으로 cascade된다(qfile_clear_list_cache).

미해결 질문

섹션 제목: “미해결 질문”
  • 병렬 writer. qfile_open_list는 하나의 살아 있는 writer cursor(last_pgptr)를 만들어 낸다. 병렬 heap 스캔 경로 (scan_open_parallel_heap_scan)는 튜플을 여러 생산자 스레드로 fan-out하는 것처럼 보인다. 각 병렬 워커가 자기만의 private list-file에 쓰고 코디네이터가 머지하는 구조인지, 아니면 writer cursor가 mutex로 보호되는 단일 list-file에 모두가 쓰는 구조인지 검증이 필요하다. query_executor.c에서 parallelism을 grep하면 ORDERBY_STATS의 parallel 인자가 qfile_sort_list_with_func까지 내려가는 모습이 보인다. 따라서 병렬 정렬은 지원되는 듯한데, list-file 자체 안의 병렬 쓰기 경로는 명확하지 않다.
  • 압축 튜플 포맷. 모든 튜플이 비압축으로 저장된다. 컬럼이 많은 list-file(예: 컬럼이 다수인 서브쿼리)에서는 낭비가 크다. CUBRID가 row-compressed list-file에 대한 계획이나 실험이 있는지는 불분명 하다. list_file.c 안에 compress 심볼은 없다.
  • 컬럼나 변형. packed-row 포맷은 OLTP 형 질의에는 무난하지만, 컬럼 폭이 넓은 분석 질의에는 병리적이다. CUBRID에는 컬럼나 list-file이 없다. PostgreSQL은 core 밖에서 columnar 확장이 있고, MySQL/MariaDB ColumnStore는 별도 엔진이다. 컬럼나 list-file (QFILE_LIST_ID가 컬럼당 membuf 체인을 갖는)은 폭이 좁은 리팩토 링 후보지만, 이 방향의 작업 흔적은 없다.
  • Membuf 크기 정책. PRM_ID_TEMP_MEM_BUFFER_PAGES는 기본 몇 페이지에 그친다. 실제로는 다수의 서브쿼리 결과가 작아서 spill 까지 가지 않는다. 현재 워크로드를 기본값이 적절한지, 그리고 질의 단위 적응적 크기 조정이 가치 있는지는 프로파일링이 필요한 주제다. TEMP_FILE_MEMBUF_NORMAL과 TEMP_FILE_MEMBUF_KEY_BUFFER 의 분리에서 보듯이 엔진은 이미 사용 사례에 따라 차별화하고 있다. CONNECT BY나 큰 해시 빌드 같은 known-big 생산자를 위해 TEMP_FILE_MEMBUF_LARGE를 추가하는 일은 이미 한 발자국 거리에 있다.
  • is_result_cached 소유권 경계. xasl->list_id->is_result_cached 가 true면 실행기는 list-file을 파괴하지 않고 캐시가 소유한다. 이 비트를 toggle하는 흐름이 qexec_execute_query, qmgr_process_query, xcache_can_entry_cache_list에 흩어져 있다. 단일 ownership-transfer 함수가 있으면 좋겠지만, 현재의 분산은 CUBRID의 C 에러 모델 — 모든 owner가 success/failure를 반환하고 caller가 결정 — 와 일관된다. 실제 버그가 발견되지 않는 한 굳이 리팩토링할 가치는 없을 것이다.

출처

섹션 제목: “출처”
  • src/query/list_file.c (~7,200줄) — 본 구현체. 페이지 할당 (qfile_allocate_new_page), 튜플 쓰기(qfile_save_normal_tuple 과 친구들), 스캔 상태 머신(qfile_scan_next), 집합 연산 (qfile_combine_two_list), 정렬 wrapper(qfile_sort_list_with_func), 결과 캐시(qfile_lookup_list_cache_entry 등)가 모두 여기 있다.
  • src/query/list_file.h — 공개 API.
  • src/query/query_list.h — QFILE_LIST_ID, QFILE_LIST_SCAN_ID, QFILE_PAGE_HEADER, 튜플 포맷 매크로, sort-list 타입.
  • src/query/query_manager.h — QMGR_TEMP_FILE(저장소 핸들).
  • src/query/query_manager.c — qmgr_create_new_temp_file, qmgr_get_new_page / qmgr_get_old_page, membuf vs FILE_TEMP 중재.
  • src/query/scan_manager.c — scan_open_list_scan(list-file을 S_LIST_SCAN 스캔 연산자로 감싸는 자리).
  • src/query/query_executor.c — 호출 위치들: qexec_end_one_iteration (writer), qexec_clear_xasl(수명), qexec_groupby / qexec_orderby_distinct / qexec_execute_analytic(정렬 호출자), qexec_clear_list_cache_by_class(캐시 무효화).
  • src/storage/file_manager.c — file_create_temp, file_alloc, file_temp_retire. spill 아래 깔리는 FILE_TEMP 기반.

교재 참조:

  • Goetz Graefe, Volcano — An Extensible and Parallel Query Evaluation System (TKDE 1994). iterator 모델과, 모든 list-file 소비자가 따르는 open / next / close 계약.
  • Goetz Graefe, Query Evaluation Techniques for Large Databases (Computing Surveys 1993). 튜플 버퍼, 머터리얼라이즈, 집합 연산을 위한 sort-merge.
  • Alex Petrov, Database Internals (O’Reilly 2019). 1장(파일 조직, slotted page, 튜플 길이 prefix)와 14장(정렬, 머지, GROUP BY). 본 KB의 knowledge/research/dbms-general/database-internals.md 에 캡쳐되어 있다.
  • Joseph M. Hellerstein, Michael Stonebraker, James Hamilton, Architecture of a Database System (Foundations and Trends in Databases 2007). inter-operator pipe 어휘와 연산자 트리 구현 모델.
  • Abraham Silberschatz, Henry Korth, S. Sudarshan, Database System Concepts (6판). 12장 (“Query Processing)과 13장 (Query Optimization”)이 머터리얼라이즈 vs 파이프라이닝 트레이드오프를 교과서적으로 정리한다. 본 KB의 knowledge/research/dbms-general/database-system-concepts.md에 캡쳐되어 있다.