(KO) CUBRID Query Optimizer — 쿼리 그래프, 비용 모델, 조인 열거, 그리고 컴파일된 플랜

학술적 배경
DBMS 공통 설계 패턴 (Common DBMS Design)
CUBRID의 구현
소스 코드 가이드
소스 검증 노트
미해결 질문
출처

학술적 배경

쿼리 옵티마이저는 선언적인 SQL 문을 절차적인 실행 플랜으로 바꾸 는 컴포넌트다. 같은 결과를 만들어내는 동등한 플랜들의 공간 을 탐색한 뒤 추정 비용이 가장 작은 플랜을 골라낸다. Database Internals (Petrov) 의 “Query Processing and Optimization” 장과, 오픈 소스 진영의 정본인 Hellerstein–Stonebraker–Hamilton 의 Architecture of a Database System §6 (Relational Query Processor) 가 같은 재료를 다룬다. 그 아래에는 세 가지 문제가 깔려 있다.

플랜 공간 열거 (plan-space enumeration). N-way 조인의 조인 트리 개수는 초지수적이다. 트리 모양이 Catalan(N-1) 가지에 N! 가지 순서가 곱해진다. 실용적인 근사는 둘이다. 첫째는 Selinger et al., Access Path Selection in a Relational Database Management System (SIGMOD 1979) 의 left-deep 동적 계획법이다. 크기 k 부분집합의 최적 플랜을 크기 k−1 부분집합들의 최적 플랜으로부터 만들어 올리며, 시간 복잡도는 O(2^N · N), 공간 복잡도는 O(2^N) 이다. 둘째는 Cascades 류의 bushy-plan 탐색이다 (Graefe, The Cascades Framework for Query Optimization, IEEE Data Eng. Bull. 1995). 이쪽 은 Volcano 류 탐색 그래프 위에서 메모된 변환 규칙을 적용 한다. 테이블 수가 12 개를 넘는 영역에서는 둘 다 휴리스틱 탐색으로 넘어간다. greedy operator ordering (GOO), iterative improvement, simulated annealing, 또는 PostgreSQL geqo 같은 유전 알고리즘이 그 예다.
카디널리티 / 비용 추정. 한 플랜의 비용은 연산자별 비용의 합이고, 각 연산자의 비용은 입력 카디널리티와 행 단위 작업량 의 함수다. 카디널리티는 selectivity 가정 (독립성, 균일성, 포함–배제 원리) 을 따라 상향식으로 전파된다. 이 가정들이 실제와 잘 맞지 않는다는 점은 잘 알려져 있지만, 그래도 비용이 싸기에 그대로 쓰인다. 비용 모델의 fixed / variable 분리 (Selinger §3.2) 는 비용을 두 부분으로 나눈다. 스캔 한 번당 한 번 지불되는 시작 비용 (예: B-tree 루트에서 첫 leaf 까지 내려가는 비용) 과 추정 행 수에 비례해 늘어나는 행 단위 비용이다.
액세스-패스 선택. 각 base 테이블에서 sequential scan, 단일 컬럼 인덱스, 다중 컬럼 인덱스, covering index, index skip-scan 중 무엇을 쓸지 결정한다. 이미 조인된 두 서브 플랜에 대해서는 nested-loop, index-NL, sort-merge, hash join 중 하나를 고른다. 비용 모델이 최종적으로 순위를 매기는 물리 연산자 결정이 이 단계에 해당한다.

Selinger 논문에는 이름을 따로 붙여 강조할 만한 두 가지 기법이 나온다. 이후의 옵티마이저들은 CUBRID 를 포함해 이 두 가지 위에서 설계된다.

Interesting orders. 어떤 서브-플랜이 조인 컬럼으로 이미 정렬된 튜플을 만들어내고 있다면 (정렬된 인덱스를 사용했거나, 앞단 merge join 이 정렬을 강제했거나), 그 서브-플랜은 unordered 대안보다 비용이 약간 비싸더라도 보존할 가치가 있다. 뒤따르는 sort-merge join 이 명시적 정렬을 생략할 수 있기 때문이다. CUBRID 는 이를 QO_INFO 노드별 planvec 으로 구체화한다. 동치류 (equivalence class) 단위로 흥미로운 정렬 한 가지마다 자기만의 최적 플랜이 따로 보관된다.
Dominance 기반 가지치기. 같은 base 테이블 부분집합을 덮고 같은 interesting order 를 만들어내는 두 플랜 중에서 엄격히 더 비싼 쪽은 즉시 버린다. CUBRID 의 dominance 검사는 qo_check_plan_on_info 가 담당한다.

CUBRID 의 플랜 탐색 구조는 두 가지 CUBRID 특유의 변형을 포함하기 는 하지만 본질적으로 Selinger 를 그대로 따른다. (a) 강하게 연결되어 있지 않은 파티션 그래프에서는 각 연결 부분 그래프가 독립적으로 최적화되고, 결과는 카르테시안 곱으로 결합된다 (qo_search_partition / qo_combine_partitions). (b) 테이블이 8 개를 넘으면 풀 DP 대신 부분 조인 first-node-then-extend 휴리스틱으로 전환되어, DP 탐색 창을 작은 join_unit (테이블 수가 늘어남에 따라 8 → 3 → 2) 으로 좁힌다. 이 부분은 Sybase Adaptive Server 류의 변형으로 소스 주석에 명시되어 있다. qo_search_partition_join 의 인라인 주석을 참고하면 된다.

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

비용 기반 옵티마이저 (System R, PostgreSQL, MySQL, Oracle, SQL Server, CUBRID 모두) 는 교과서적 틀 위에 같은 핵심 어휘를 얹어 쓴다. 다음 섹션에서 등장할 CUBRID 고유의 식별자들은, 이 공유된 설계 공간 안에서 다이얼이 다르게 맞추어진 결과로 읽으면 된다. 발명품이 아니라는 뜻이다.

쿼리 그래프 + 비용 주석이 달린 관계 대수

옵티마이저의 작업 표현은 그래프다. 노드는 base 관계나 파생 테이블이고, 간선은 조인 술어다. 단일 관계에 대한 sargable 술어는 그 노드에 매달려 있고, sargable 하지 않은 술어 (서브 쿼리, 복잡한 식) 는 조인 이후의 필터로 미뤄진다. PostgreSQL 은 이를 RelOptInfo / RestrictInfo 그래프라 부르고, SQL Server 는 memo, Oracle 은 join graph 로 부른다. CUBRID 는 이를 Query Graph 라 부르고, 관계는 QO_NODE, 술어는 QO_TERM, 컬럼 참조는 QO_SEGMENT 로 표현한다.

Bitset 으로 키를 잡는 동적 계획법

Selinger DP 는 플랜의 키로 그 플랜이 덮는 관계의 부분집합을 쓴다. 이 부분집합은 관계 ID 위의 비트셋 정수로 인코딩된다. 관계가 N 개일 때 join-info 테이블의 항목 수는 2^N 이다. PostgreSQL 은 이를 root->join_rel_list (연결 리스트) 와 해시 테이블로 관리한다. CUBRID 는 평탄한 join_info 배열을 잡는데, 그 크기는 QO_JOIN_INFO_SIZE = 1 << bitset_cardinality(partition.nodes) 슬롯이며, 파티션 상대 비트셋을 그대로 인덱스로 쓴다.

동치류별 plan vector

한 DP 슬롯 안에서도 옵티마이저는 dominance 가 성립하지 않는 여러 플랜을 보존할 수 있다. interesting order 한 가지 (즉, 조인 컬럼 동치류 한 가지) 마다 하나씩이다. CUBRID 의 QO_PLANVEC 는 (info, order) 쌍 하나당 최대 NPLANS = 4 개 플랜을 담고, PostgreSQL 의 pathlist 가 같은 역할을 한다.

비용 모델: fixed + variable, CPU + IO

표준 비용 모델은 비용을 네 슬롯으로 나눈다. fixed-cpu, fixed-io, variable-cpu, variable-io 다. fixed 는 연산자가 활성화될 때 한 번만 지불되는 비용 (예: B-tree 루트를 내려가는 비용) 이고, variable 은 행 수에 비례해 누적된다. Selectivity 는 술어별 selectivity 의 독립성 가정 곱으로 계산되며, 과소 추정을 막기 위해 1 / pkeys[i] 로 아래쪽이 잘린다. 카디널리티 는 관계 카디널리티에 누적 selectivity 를 곱해 전파된다. CUBRID 는 qo_plan 과 qo_summary 위에 이 네 슬롯을 정확히 같은 이름으로 들고 있다.

액세스-패스 후보와 조인-방법 후보

옵티마이저는 QO_NODE 마다 {seq scan, 사용 가능한 B-tree 인덱스 하나당 인덱스 스캔, group-by/order-by 인덱스 스캔, loose / index-skip 스캔}을 열거한다. 이미 조인된 두 서브 플랜 쌍에 대해서는 {nested-loop, index-correlated-NL, sort-merge, hash-list}를 열거한다. CUBRID 에서는 세 qo_examine_* 루틴 (qo_examine_nl_join, qo_examine_idx_join, qo_examine_merge_join) 이 디스패치 지점이다. PostgreSQL 의 add_paths_to_joinrel 이 같은 역할을 하며, 그 안에서 match_unsorted_outer, sort_inner_and_outer 등을 부른다.

세 가지 엔진 계열과 CUBRID 의 위치

PostgreSQL 은 geqo_threshold (기본 12) 까지는 left-deep DP 를, 그 이상에서는 유전 알고리즘을 쓴다. 탐색 구조는 상향식 한 방향이며, 탐색 도중 규칙 기반 재작성은 없다.
MySQL 은 nested-loop 순서를 그리디하게 결정하고 straight_join 힌트를 사용한다. 비용 모델은 단순한 편이다. interesting order 가 없고, hash join 도 8.0 에 와서야 추가 되었으며, bushy 플랜은 고려되지 않는다.
SQL Server (그리고 Apache Calcite, MemSQL, CockroachDB) 는 Cascades 류의 메모 기반 탐색을 쓴다. 규칙들이 메모 안에서 서브 플랜을 변환해 가며 비용이 수렴할 때까지 반복한다. bushy 플랜이 자연스럽게 나오지만, 탐색 시간을 제한하기는 더 어렵다.
Oracle 은 다중 전략 옵티마이저다. 작은 조인에는 Selinger 류 DP 를, 탐색 전 단계에서는 규칙 기반 액세스-패스 가지치기를, 매우 큰 조인에는 유전 / 휴리스틱 폴백을 쓴다.

CUBRID 는 System R 계열에 속한다. interesting order 를 갖춘 상향식 DP 를 쓰고, 탐색 도중의 변환 규칙은 없다. 다만 8 개를 넘는 조인에 대해서는 late-Sybase 변형의 부분 조인 창 (window) 기법을 함께 쓴다. 한 파티션 안에서 일어나는 두 단계 탐색이 그 차별점이다. 부분 조인 sweep 이 prefix 를 한 노드씩 확장 하다가 join_unit 만큼의 테이블이 보이면 멈추고, 거기서도 플랜을 못 찾으면 풀 조인 탐색으로 폴백한다.

이론 ↔ CUBRID 매핑

이론적 개념	CUBRID 명칭
관계당 그래프 노드	`QO_NODE` (FROM 절의 `PT_SPEC` 하나당 하나)
관계 간 그래프 간선 (조인 술어)	`term_class == QO_TC_JOIN` 인 `QO_TERM`
관계 단일 행 술어 (sargable)	`term_class == QO_TC_SARG` 인 `QO_TERM`, `QO_NODE_SARGS(node)` 로 인덱싱
그래프 위 컬럼 참조 (segment)	`QO_SEGMENT` (속성 사용 한 번당 하나, `head` = 소속 노드)
조인 컬럼의 동치류 (interesting order)	`QO_EQCLASS`
분리된 부분 그래프 (카르테시안 곱 파티션)	`QO_PARTITION`
node-subset bitset 으로 인덱싱되는 Selinger DP 테이블	`planner->join_info[QO_INFO_INDEX(M_offset, rel_nodes)]`
DP 슬롯 하나당 비-우세 플랜 리스트	`QO_PLANVEC` (`NPLANS = 4`)
플랜 트리 노드 (연산자)	`QO_PLAN`, `plan_type ∈ {SCAN, SORT, JOIN, FOLLOW, WORST}`
비용 벡터	`qo_plan::{fixed,variable}_{cpu,io}_cost`
액세스-패스 열거	`qo_search_planner` 안의 노드별 `node_index` 루프
Index/NL/merge join 디스패치	`qo_examine_idx_join`, `qo_examine_nl_join`, `qo_examine_merge_join`
Selinger left-deep DP	`planner_permutate` → `planner_visit_node`
부분 조인 창	`planner->join_unit` ∈ {2, 3, 8}
플랜 트리 → 물리 플랜 lowering	`qo_to_xasl` (`plan_generation.c`)

CUBRID의 구현

CUBRID 옵티마이저는 세 단계 워크다. (1) PT_NODE → Query Graph 는 의미 검사를 마친 파스 트리로부터 QO_ENV 를 만든다. (2) 비용 모델과 조인 열거는 QG 위에서 4-슬롯 비용 모델로 Selinger DP 를 돌린다. (3) Query Graph → Compiled Graph 는 살아남은 QO_PLAN 트리를 서버가 실행하는 XASL 액세스-스펙 트리로 내린다. 옵티마이저는 클라이언트 (CAS) 에서 동작하고 (#if !defined(SERVER_MODE)), 서버로 전달되는 것은 QO_PLAN 트리가 아니라 XASL 이다.

파이프라인

flowchart LR
  SQL["SQL 문자열"] --> P["파서<br/>(csql_grammar.y)"]
  P --> AST["PT_NODE 트리<br/>(parse_tree.h)"]
  AST --> SC["의미 검사<br/>(semantic_check.c)<br/>이름 해소, 타입 체크"]
  SC --> RW["재작성기<br/>(mq_rewrite, parse_tree_cl.c)<br/>CNF, 뷰 머지,<br/>oracle-style outer join,<br/>술어 push"]
  RW --> OPT["qo_optimize_query<br/>(query_graph.c)"]
  OPT --> EH["qo_optimize_helper"]
  EH --> QG["Query Graph<br/>QO_ENV{nodes, segs, terms,<br/>eqclasses, partitions}"]
  QG --> AN["qo_analyze_term<br/>qo_classify_outerjoin_terms<br/>qo_discover_edges<br/>qo_assign_eq_classes<br/>qo_discover_indexes<br/>qo_discover_partitions"]
  AN --> PLN["qo_planner_search<br/>· qo_alloc_planner"]
  PLN --> SP["qo_search_planner<br/>노드별 액세스-패스<br/>스캔 플랜"]
  SP --> SPP["qo_search_partition (파티션별)"]
  SPP --> SPJ["qo_search_partition_join<br/>(planner_permutate +<br/>partial/total 조인 창)"]
  SPJ --> CMB["qo_combine_partitions<br/>(카르테시안)"]
  CMB --> FIN["qo_plan_finalize"]
  FIN --> X["qo_to_xasl<br/>(plan_generation.c)"]
  X --> XASL["XASL_NODE 트리"]
  XASL --> WIRE["xasl_to_stream → 서버"]

재작성기 (rewriter) 단계는 의미 검사와 옵티마이저 진입점 사이 에 자리 잡고 있는데, 이 문서에서는 의도적으로 다루지 않는다. mq_rewrite 와 parse_tree_cl.c 의 재작성 워크가 CNF 정규화, 단일 행 상수 폴딩, 뷰 머지, Oracle 식 (+) outer-join 의 ANSI 형 변환, 술어 push 변환을 qo_optimize_query 호출 이전에 모두 끝낸다. 그래서 옵티마이저는 이미 정규화된 PT_NODE 만 본다. WHERE 절은 평탄한 최상위 AND 리스트이고, 모든 SPEC 이 ANSI 이며, 대수적으로 안전한 뷰 서브쿼리는 이미 머지된 상태다. 이 단계의 자세한 내용은 함께 캡처된 raw 문서 raw/code-analysis/cubrid/query-processing/[CUBRID QP] Parsing to Query Graph.pptx 를 참고하면 되고, 본 문서는 qo_optimize_query 부터 시작한다.

단계 1 — PT_NODE → Query Graph

진입점은 qo_optimize_query (parser, tree) 다.

// qo_optimize_query — src/optimizer/query_graph.c
QO_PLAN *
qo_optimize_query (PARSER_CONTEXT * parser, PT_NODE * tree)
{
  QO_ENV *env;
  int level;

  qo_get_optimization_param (&level, QO_PARAM_LEVEL);
  if (!OPTIMIZATION_ENABLED (level))      /* PRM_OPTIMIZATION_LEVEL == 0 */
    return NULL;
  if (tree->node_type != PT_SELECT)        /* DML/DDL bypass the optimizer */
    return NULL;

  env = qo_env_init (parser, tree);        /* allocate QO_ENV, walk tree, count */
  if (env == NULL)
    return NULL;

  switch (setjmp (env->catch_))
    {
    case 0:
      return qo_optimize_helper (env);     /* normal path */
    case 1: case 2: default:
      /* OOM, failed assertion, or unknown — error already set */
      break;
    }
  qo_env_free (env);
  return NULL;
}

이 도입부에서 두 가지 설계 결정이 보인다. (a) 옵티마이저는 선택적 (opt-in) 이며 PRM_OPTIMIZATION_LEVEL 을 0 으로 두면 호출자(XASL 생성기) 가 기본 플랜으로 폴백한다. (b) 최적화 전체가 setjmp / longjmp 캐치 프레임 안에서 돈다. optimizer.h 에 정의된 QO_ABORT(env) 와 QO_ASSERT(env, cond) 는 이 switch 로 longjmp 해서, 깊게 중첩된 헬퍼 어디서든 손으로 풀어 내려갈 필요 없이 바로 빠져나올 수 있게 해 준다. 현대 C/C++ 에서는 흔치 않은 스타일이지만, 예외(exception) 보다 앞선 시기에 만들어진 코드라는 점을 감안하면 일관성 있는 선택이다 — QO_ENV 가 할당한 모든 구조체는 결국 qo_env_free 가 한꺼번에 해제한다.

qo_env_init (query_graph.c 에 선언) 은 트리를 한 번 훑어 nnodes/nsegs/nterms 를 센 뒤 4 개의 평행 배열을 할당하고, 이어서 qo_optimize_helper 가 단계별 드라이버 역할을 한다.

// qo_optimize_helper — src/optimizer/query_graph.c (condensed)
static QO_PLAN *
qo_optimize_helper (QO_ENV * env)
{
  PARSER_CONTEXT *parser = QO_ENV_PARSER (env);
  PT_NODE *tree          = QO_ENV_PT_TREE (env);
  PT_NODE *spec, *conj, *next;
  QO_TERM *term;
  QO_NODE *node, *p_node;
  BITSET nodeset;
  QO_PLAN *plan;

  /* (1) Add QO_NODE per FROM spec, QO_SEGMENT per referenced attribute. */
  parser_walk_tree (parser, tree, build_query_graph, &env,
                    build_query_graph_post, &env);
  parser_walk_tree (parser, tree, build_query_graph_function_index, &env,
                    NULL, NULL);
  add_hint (env, tree);
  add_using_index (env, tree->info.query.q.select.using_index);

  /* (2) Dependent-derived-table dependency edges (correlated subqueries). */
  for (n = 0; n < env->nnodes; n++)
    {
      node = QO_ENV_NODE (env, n);
      spec = QO_NODE_ENTITY_SPEC (node);
      if (is_dependent_table (spec))
        {
          /* Find segments referenced by the derived-table expression and
           * back-resolve them to the nodes they live on. Establish
           * artificial dep_set edges so the planner respects ordering. */
          qo_expr_segs (env, spec->info.spec.derived_table, &dependencies);
          if (!bitset_is_empty (&dependencies))
            {
              qo_seg_nodes (env, &dependencies, &antecedents);
              qo_add_dep_term (node, &antecedents, &dependencies, env);
            }
        }
    }

  /* (3) Add ON-clause terms (one location per ANSI join) and WHERE terms. */
  for (spec = tree->info.query.q.select.from; spec; spec = spec->next)
    if (spec->node_type == PT_SPEC && spec->info.spec.on_cond)
      for (conj = spec->info.spec.on_cond; conj; conj = conj->next)
        {
          term = qo_add_term (conj, PREDICATE_TERM, env);
          if (QO_TERM_CLASS (term) == QO_TC_JOIN)
            bitset_add (&nodeset, QO_NODE_IDX (QO_TERM_TAIL (term)));
        }
  for (conj = tree->info.query.q.select.where; conj; conj = conj->next)
    qo_add_term (conj, PREDICATE_TERM, env);

  /* (4) ANSI join without an explicit edge → DUMMY_JOIN term to keep
   *     order stable; right-outer-join → outer_dep_set propagation. */
  for (n = 1; n < env->nnodes; n++)
    {
      node = QO_ENV_NODE (env, n);
      if (QO_NODE_IS_ANSI_JOIN (node) && !BITSET_MEMBER (nodeset, n))
        qo_add_dummy_join_term (env, QO_ENV_NODE (env, n - 1), node);
      if (QO_NODE_PT_JOIN_TYPE (node) == PT_JOIN_RIGHT_OUTER)
        for (k = n - 1; k >= 0 && QO_NODE_IS_ANSI_JOIN (p_node); k--)
          QO_ADD_OUTER_DEP_SET (node, p_node);
    }

  qo_classify_outerjoin_terms (env);   /* SARG → DURING_JOIN / AFTER_JOIN */

  /* (5) Final-segment discovery (segments that survive past the join). */
  parser_walk_tree (parser, tree->info.query.q.select.list,
                    qo_add_final_segment, &env, pt_continue_walk, NULL);
  parser_walk_tree (parser, tree->info.query.q.select.group_by,
                    qo_add_final_segment, &env, pt_continue_walk, NULL);
  parser_walk_tree (parser, tree->info.query.q.select.having,
                    qo_add_final_segment, &env, pt_continue_walk, NULL);

  /* (6) Edge / eq-class / index / partition / sort-limit discovery. */
  qo_discover_edges (env);
  qo_assign_eq_classes (env);
  get_local_subqueries (env, tree);
  get_rank (env);
  qo_discover_indexes (env);
  qo_discover_partitions (env);
  qo_discover_sort_limit_nodes (env);

  /* (7) Plan search. */
  plan = qo_planner_search (env);

  if (plan == NULL)
    qo_env_free (env);
  return plan;
}

각 단계는 모양이 분명하다.

`QO_NODE` — FROM spec 하나당 하나

QO_NODE 는 한 관계의 PT_SPEC 위에 두꺼운 껍질을 씌운 구조다. 통계 필드(ncard, tcard)는 prefetch 단계에서 CAS 워크스페이스에 캐싱해 둔 QO_CLASS_INFO 에서 가져온다. 의존성 비트셋(dep_set, outer_dep_set)은 순열 탐색 중에도 살아남아야 하는 순서 제약을 플래너에게 알려 주는 용도다 — 상관 서브쿼리가 만든 파생 테이블이나 right-outer-join 의 우변은 자기 선행 노드 이전에 방문될 수 없다.

// qo_node — src/optimizer/query_graph.h
struct qo_node
{
  QO_ENV *env;
  PT_NODE *entity_spec;          /* original PT_SPEC */

  BITSET segs;                   /* QO_SEGMENT idxs emanating from this node */
  BITSET eqclasses;              /* QO_EQCLASS idxs joined to this node */
  QO_PARTITION *partition;       /* connected sub-graph this node lives in */
  QO_SEGMENT *oid_seg;           /* virtual OID column for joins */

  BITSET dep_set;                /* nodes this one depends on (corr. subq) */
  BITSET sargs;                  /* QO_TERMs of class TC_SARG on this node */
  double selectivity;            /* product of QO_TERM_SELECTIVITY in sargs */
  BITSET subqueries;             /* QO_SUBQUERY idxs to evaluate per row */

  QO_CLASS_INFO *info;
  unsigned long int ncard;       /* est. row count (System R "ncard") */
  unsigned long int tcard;       /* est. page count ("tcard") */

  const char *class_name;
  int idx;                       /* env-wide id (used in BITSETs) */
  int rel_idx;                   /* partition-relative id (used in join_info BITSETs) */

  QO_NODE_INDEX *indexes;        /* indexes on the underlying class hierarchy */
  QO_USING_INDEX *using_index;   /* USING INDEX hint */
  BITSET outer_dep_set;          /* outer-join-induced predecessors */
  PT_HINT_ENUM hint;
  bool sargable;
  bool sort_limit_candidate;
};

idx 와 rel_idx 의 차이는 한눈에 들어오지 않는다. idx 는 노드의 env->nodes[] 슬롯 번호이고, env 전체에 걸친 비트셋(예: QO_TERM_NODES) 에서 쓰인다. rel_idx 는 노드의 소속 파티션 내 위치이며, DP 테이블의 키가 되는 join_info 비트셋에서 쓰인다. 이렇게 두 개를 분리해 두기 때문에, 쿼리에 파티션이 여러 개 있더라도 DP 키는 파티션 단위 비트 공간 하나로 좁혀지고, join_info 배열은 그 파티션 크기에 비례하는 평탄한 2^|partition| 벡터로 유지된다.

두 개의 카디널리티 필드는 System R 의 유산을 그대로 들고 있다. 실제로 query_graph.h:329-340 의 주석에는 “These silly names are historical artifacts that correspond to the names in the 197? IBM report on query optimization in System R.” 라고 적혀 있다.

`QO_SEGMENT` — 속성 참조 한 번당 하나

QO_SEGMENT 는 쿼리 안에서 한 컬럼이 사용된 한 번 을 표현한다. 같은 컬럼에 대한 두 segment(예: SELECT a FROM t WHERE a = 1 의 두 a) 는 보통 하나로 합쳐진다 — lookup_seg 가 검색해서 기존 segment 를 재사용한다. 즉 segment 의 정체성은 “컬럼 정의” 가 아니라 “컬럼이 등장한 자리” 다. head 필드는 이 segment 가 emanate 하는 노드를 가리키며, ORDBMS 식 path 식(u.direct_groups) 에서는 tail(연결된 클래스 노드) 까지 함께 갖는다. 이 경우 segment 자체가 PATH 텀이 매달리는 봉합선이 된다.

// qo_segment — src/optimizer/query_graph.h
struct qo_segment
{
  QO_ENV *env;
  PT_NODE *pt_node;
  QO_NODE *head, *tail;          /* tail != NULL iff path/join segment */
  QO_SEGMENT *eq_root;           /* union-find root for eq-class grouping */
  QO_EQCLASS *eqclass;
  const char *name;
  bool set_valued, class_attr, shared_attr;
  bool index_term_eq_expr;
  QO_ATTR_INFO *info;            /* per-class statistics */
  BITSET index_terms;            /* terms that can use an index on this seg */
  int idx;
  bool is_function_index;
  bool is_not_null;
};

`QO_TERM` — 술어(sargable, join, 가짜)

term 은 세 군데에서 들어온다. WHERE 의 conjunct, ANSI ON 의 conjunct (conjunct 하나당 term 하나, location 이 0 이 아닌 값으로 표시됨), 그리고 옵티마이저 자신이 만들어 내는 합성(synthetic) term — 점 표기 식의 path 술어, 상관 파생 테이블의 dependent-link, 조인 술어가 없는 ANSI 조인을 위한 dummy join term 이 그것이다.

// qo_term — src/optimizer/query_graph.h
struct qo_term
{
  QO_ENV *env;
  BITSET nodes;                  /* nodes this term references */
  BITSET segments;
  double selectivity;            /* product of leaf selectivities */
  QO_TERMCLASS term_class;
  int rank;
  PT_NODE *pt_expr;              /* original conjunct */
  BITSET subqueries;
  JOIN_TYPE join_type;
  int can_use_index;
  QO_SEGMENT *index_seg[2];      /* sides the optimizer will treat as keys */
  QO_SEGMENT *seg, *oid_seg;     /* PATH-term-specific */
  QO_NODE *head, *tail;
  QO_EQCLASS *eqclass;
  QO_SEGMENT *nominal_seg;
  int flag;                      /* equal_op? rangelist? mergeable_edge? */
  int idx;
  short location;                /* 0 for WHERE, > 0 for ON-conjuncts */
  int *multi_col_segs;
  int multi_col_cnt;
  int pred_order;                /* for view-merge / pred-push ordering */
};

QO_TERMCLASS 의 분류 체계는 비트로 인코딩되어 있어서 QO_IS_PATH_TERM, QO_IS_EDGE_TERM, QO_IS_FAKE_TERM 가 모두 한 비트만 검사하면 끝난다. 분류표는 다음 열 가지 행으로 정리된다.

// QO_TERMCLASS — src/optimizer/query_graph.h
typedef enum
{
  QO_TC_PATH               = 0x30,  /* 1 1 0 000 */
  QO_TC_JOIN               = 0x11,  /* 0 1 0 001 */
  QO_TC_SARG               = 0x02,  /* 0 0 0 010 */
  QO_TC_OTHER              = 0x03,  /* 0 0 0 011 */
  QO_TC_DEP_LINK           = 0x1c,  /* 0 1 1 100 */
  QO_TC_DEP_JOIN           = 0x1d,  /* 0 1 1 101 */
  QO_TC_DURING_JOIN        = 0x04,  /* 0 0 0 100 */
  QO_TC_AFTER_JOIN         = 0x05,  /* 0 0 0 101 */
  QO_TC_TOTALLY_AFTER_JOIN = 0x06,  /* 0 0 0 110 */
  QO_TC_DUMMY_JOIN         = 0x1f   /* 0 1 1 111 */
} QO_TERMCLASS;

#define QO_IS_PATH_TERM(t)  (QO_TERM_CLASS(t) & 0x20)
#define QO_IS_EDGE_TERM(t)  (QO_TERM_CLASS(t) & 0x10)
#define QO_IS_FAKE_TERM(t)  (QO_TERM_CLASS(t) & 0x08)

주석 네 컬럼은 path | edge | fake | num 순이다. 비트 패킹 덕분에 조인 그래프 traversal 에 참여하는 모든 term 은 0x10 비트를 갖고, 옵티마이저가 합성한 모든 “FAKE” term 은 0x08 비트를 갖는다. 이 구분은 비용에 영향을 준다 — fake term 은 merge edge 로 쓸 수 없기 때문에 QO_ENV 의 fake_terms 집합에서 제외되어 qo_examine_merge_join 후보에서 빠진다.

실제 워크로드에서 빈도가 가장 높은 부분 집합은 QO_TC_SARG (단일 관계 술어, 예: a.col2 = 1), QO_TC_JOIN (관계 간 술어, 예: a.col1 = b.col1), QO_TC_DURING_JOIN (left-outer join 우변에 대한 술어로 NULL-extension 의미를 갖고 조인 도중 평가됨), 그리고 QO_TC_AFTER_JOIN (left-outer join 우변에 대한 WHERE 절 술어로 조인 후 평가됨) 이다. DURING_JOIN 과 AFTER_JOIN 의 분리는 SQL 의 고전적인 함정이다 — left-outer join 술어를 ON 에 두느냐 WHERE 에 두느냐가 결과 자체를 바꿔 버린다.

`QO_EQCLASS` — 동치류 / interesting orders

내부 equi-join term a.x = b.y 가 추가될 때마다 두 segment 는 eq_root 포인터로 union-find 로 한 동치류에 합쳐진다. 연쇄적으로 a.x = b.y 와 b.y = c.z 는 (a.x, b.y, c.z) 를 한 동치류로 묶는다. 모든 term 이 추가된 뒤에는 qo_assign_eq_classes 가 동치류 하나당 QO_EQCLASS 객체 하나를 만든다. 각 동치류는 DP 탐색에서 하나의 interesting order 가 된다 — 이 동치류 위로 정렬된 출력을 만드는 서브-플랜은 (info, order) 단위의 planvec 안에서 자기 자리를 따로 차지한다.

`QO_PARTITION` — 연결 부분 그래프

qo_discover_partitions 는 그래프 위에서 연결 컴포넌트 sweep 을 돈다 (fake 가 아닌 edge term 으로 연결된 노드들). 컴포넌트 하나가 QO_PARTITION 하나가 되며, 그 M_offset 은 전역 join_info 배열 안에서 자기 슬라이스가 시작하는 위치를 기록한다. 연결되지 않은 컴포넌트는 명시적 카르테시안 곱을 의미하며, 드물지만 비싸다. CUBRID 는 파티션을 각각 독립적으로 최적화한 뒤, 의존성 순서대로 qo_combine_partitions 가 결합한다.

작업 예시 — 3-way inner join

SELECT 1
  FROM a, b, c
 WHERE a.col1 = b.col1
   AND b.col1 = c.col1
   AND a.col2 = 1
   AND b.col2 = 1
   AND c.col2 = 1

flowchart LR
  subgraph QGEX["QO_ENV (파티션 1개)"]
    direction LR
    A["QO_NODE a [idx=0]<br/>ncard, tcard<br/>sargs={t3: a.col2=1}"]
    B["QO_NODE b [idx=1]<br/>sargs={t4: b.col2=1}"]
    C["QO_NODE c [idx=2]<br/>sargs={t5: c.col2=1}"]
    T1["QO_TERM t1: a.col1=b.col1<br/>class=JOIN, eqclass=E0"]
    T2["QO_TERM t2: b.col1=c.col1<br/>class=JOIN, eqclass=E0"]
    A -- t1 --- B
    B -- t2 --- C
    A --- T1
    B --- T1
    B --- T2
    C --- T2
  end
  E0["QO_EQCLASS E0<br/>{a.col1, b.col1, c.col1}"]
  T1 -. eqclass .-> E0
  T2 -. eqclass .-> E0

노드 셋, 노드별 sargable term 셋(노드별 카디널리티 추정을 낮춘다), 그리고 두 join term — 술어가 체인 형태이므로 둘은 같은 동치류에 들어간다. 그래프가 연결되어 있으므로 파티션은 하나다. DP 테이블은 2^3 = 8 슬롯을 갖는다 (a, b, c, ab, ac, bc, abc, 그리고 사용되지 않는 빈 슬롯).

단계 2 — 비용 모델과 조인 열거

그래프 작성이 끝나면 qo_planner_search 가 QO_PLANNER 골격을 할당하고 qo_search_planner 를 돌린다.

// qo_planner_search — src/optimizer/query_planner.c
QO_PLAN *
qo_planner_search (QO_ENV * env)
{
  QO_PLANNER *planner = qo_alloc_planner (env);
  QO_PLAN *plan;

  if (planner == NULL)
    return NULL;

  qo_info_nodes_init (env);
  qo_plans_init (env);
  plan = qo_search_planner (planner);
  qo_clean_planner (planner);
  return plan;
}

qo_alloc_planner 가 DP 테이블의 모양을 확정한다. 모든 파티션에 걸쳐 M_offset + 2^|partition| 을 합산해서 그 크기만큼 planner->join_info 를 잡고, 최종 합을 planner->M 에 캐싱한다.

이어서 qo_search_planner 는 세 패스를 돈다.

2a — 노드별 액세스-패스 열거

각 base 관계를 sequential scan 한 개와 사용 가능한 인덱스마다 인덱스 스캔 한 개를 만들어 보고, 그중 가장 싼 것을 planner->node_info[i]->planvec 에 기록한다.

// qo_search_planner — query_planner.c (condensed, scan-plan loop)
for (i = 0; i < planner->N; i++)
  {
    node = &planner->node[i];
    info = planner->node_info[QO_NODE_IDX (node)];

    if (PT_SPEC_SPECIAL_INDEX_SCAN (QO_NODE_ENTITY_SPEC (node)))
      {
        /* B-tree key/node info introspection — only one plan possible. */
        ni_entry = QO_NI_ENTRY (QO_NODE_INDEXES (node), 0);
        qo_check_plan_on_info (
            info, qo_index_scan_new (info, node, ni_entry,
                                     QO_SCANMETHOD_INDEX_SCAN_INSPECT,
                                     NULL, NULL));
        continue;
      }

    if (QO_NODE_INDEXES (node) != NULL)
      for (j = 0; j < QO_NI_N (QO_NODE_INDEXES (node)); j++)
        {
          ni_entry    = QO_NI_ENTRY (QO_NODE_INDEXES (node), j);
          index_entry = ni_entry->head;
          if (index_entry->force < 0) continue;        /* disabled index */

          /* Walk index columns left-to-right collecting equal+other terms;
           * stop at the first column with no equal terms. */
          for (nsegs = start_column; nsegs < index_entry->nsegs; nsegs++)
            {
              bitset_union (&seg_terms, &index_entry->seg_equal_terms[nsegs]);
              bitset_union (&seg_terms, &index_entry->seg_other_terms[nsegs]);
              if (bitset_is_empty (&index_entry->seg_equal_terms[nsegs]))
                {
                  if (!bitset_is_empty (&index_entry->seg_other_terms[nsegs]))
                    nsegs++;
                  break;
                }
            }
          bitset_intersect (&seg_terms, &QO_NODE_SARGS (node));

          if (!bitset_is_empty (&seg_terms))
            qo_generate_index_scan (info, node, ni_entry, nsegs);
          else if (index_entry->constraints->filter_predicate
                   && index_entry->force > 0)
            qo_check_plan_on_info (
                info, qo_index_scan_new (info, node, ni_entry,
                                         QO_SCANMETHOD_INDEX_SCAN,
                                         &seg_terms, NULL));
          else if (index_entry->ils_prefix_len > 0)
            qo_generate_loose_index_scan (info, node, ni_entry);
          else
            { /* try INDEX_GROUPBY_SCAN / INDEX_ORDERBY_SCAN if helpful */ }
        }

    qo_generate_seq_scan (info, node);    /* always considered */
  }

segment 와 인덱스 컬럼의 매칭은 좌에서 우로 진행되며, equality term 이 없는 첫 컬럼에서 멈춘다. 이것이 표준적인 “선두 컬럼” 규칙이다. (a,b,c) 에 잡힌 B-tree 가 있을 때 WHERE a=1 AND c=3 쿼리는 a 와 c 만 쓰고 b 는 묶이지 않은 채 둔다는 의미이며, WHERE b=2 AND c=3 은 어느 인덱스 컬럼도 쓰지 못한다는 의미다. is_iss_candidate 플래그는 index-skip-scan 옵션으로, 선행 컬럼의 카디널리티가 작을 때 이 규칙을 완화해 준다.

qo_check_plan_on_info 는 학술적 배경에서 언급한 dominance 검사다 — 이것이 planvec 의 폭주를 막는다. 같은 (info, order) 슬롯에 들어와 있는 어떤 기존 플랜과도 우열이 정해지지 않을 때(즉, 우세 하지도 우세를 받지도 않을 때) 새 플랜이 추가되며, 새 플랜이 누군가를 우세할 경우 기존 플랜을 대체한다.

2b — 비용 계산

비용 모델은 플랜마다 네 개의 숫자를 합성 단위(synthetic units) 로 계산한다. 인덱스 스캔의 경우는 다음과 같다.

// qo_iscan_cost — src/optimizer/query_planner.c (condensed)
static void
qo_iscan_cost (QO_PLAN * planp)
{
  QO_NODE              *nodep        = planp->plan_un.scan.node;
  QO_NODE_INDEX_ENTRY  *ni_entryp    = planp->plan_un.scan.index;
  QO_INDEX_ENTRY       *index_entryp = ni_entryp->head;
  QO_ATTR_CUM_STATS    *cum_statsp   = &ni_entryp->cum_stats;

  /* (a) Selectivity of key-range terms (independence assumption). */
  sel = 1.0;
  for (t = bitset_iterate (&planp->plan_un.scan.terms, &iter); t != -1; ...)
    sel *= QO_TERM_SELECTIVITY (QO_ENV_TERM (..., t));
  sel = MIN (sel, 1.0);

  /* (b) Lower-bound from B-tree partial-key statistics ("pkeys[i] = #
   *     distinct values for the prefix of the first i columns"). */
  if (i <= pkeys_num && cum_statsp->pkeys[index] >= 1)
    sel_limit = 1.0 / (double) cum_statsp->pkeys[index];
  else if (cum_statsp->keys >= 1)
    sel_limit = 1.0 / (double) cum_statsp->keys;
  sel = MAX (sel, sel_limit);

  /* (c) Selectivity of key-filter terms (terms that can be evaluated
   *     against the index entry without going to the heap). */
  filter_sel = 1.0;
  for (t = bitset_iterate (&planp->plan_un.scan.kf_terms, &iter); ...)
    filter_sel *= QO_TERM_SELECTIVITY (QO_ENV_TERM (..., t));

  leaf_access = sel * QO_NODE_NCARD (nodep);
  height      = MAX (cum_statsp->height - 1, 0);
  leaves      = ceil (sel * cum_statsp->leafs);
  index_IO    = (ni_entryp->n * height) + leaves;

  /* Index-skip-scan adds K extra B-tree probes. */
  if (qo_is_index_iss_scan (planp))
    index_IO += cum_statsp->pkeys[0];

  if (qo_is_index_covering_scan (planp))
    {
      object_IO   = 1.0;
      heap_access = 0;
    }
  else
    {
      object_IO   = MAX (1.0, QO_NODE_TCARD (nodep) * sel * filter_sel);
      heap_access = QO_NODE_NCARD (nodep) * sel * filter_sel
                    * (double) ISCAN_OID_ACCESS_OVERHEAD;
    }

  planp->fixed_cpu_cost    = 0.0;
  planp->fixed_io_cost     = index_IO;
  planp->variable_cpu_cost = (leaf_access + heap_access) * (double) QO_CPU_WEIGHT;
  planp->variable_io_cost  = object_IO;
  planp->info->scan_rows   = MAX (1, QO_NODE_NCARD (nodep) * sel * filter_sel);
}

이름이 붙은 상수들이 다이얼이다 (모두 query_planner.c:78-90 에 위치).

매크로	값	의미
`QO_CPU_WEIGHT`	`0.0025`	행당 CPU 비용 (캘리브레이션 상수)
`ISCAN_OID_ACCESS_OVERHEAD`	`20`	인덱스 스캔이 heap 으로 fetch 갈 때의 추가 CPU
`ISCAN_IO_HIT_RATIO`	`0.5`	inner-NL fetch 가 이미 캐시에 있을 가정 비율
`GUESSED_BIND_LIMIT_CARD`	`2000`	`LIMIT ?` 에 대한 카디널리티 추정

Nested-loop join 의 비용은 다음과 같다.

// qo_nljoin_cost — src/optimizer/query_planner.c (condensed)
static void
qo_nljoin_cost (QO_PLAN * planp)
{
  QO_PLAN *outer = planp->plan_un.join.outer;
  QO_PLAN *inner = planp->plan_un.join.inner;
  double guessed_result_cardinality;

  planp->fixed_cpu_cost = outer->fixed_cpu_cost + inner->fixed_cpu_cost;
  planp->fixed_io_cost  = outer->fixed_io_cost  + inner->fixed_io_cost;

  if (QO_PLAN_HAS_LIMIT (planp) && /* limit pushdown applicable */
      (planp->info->planner->can_apply_limit_card
       || qo_plan_is_orderby_skip_candidate (planp)))
    {
      /* Treat outer cardinality as min(limit / hit_prob, outer_card). */
      limit_val = QO_PLAN_HAS_CONSTANT_LIMIT (planp)
        ? db_get_bigint (&QO_ENV_LIMIT_VALUE (planp->info->env))
        : GUESSED_BIND_LIMIT_CARD;
      planp->limit_nljoin_guessed_card =
          MAX (limit_val / outer->info->hit_prob, 1.0);
      guessed_result_cardinality =
          MIN (planp->limit_nljoin_guessed_card, outer->info->cardinality);
    }
  else
    guessed_result_cardinality = outer->info->cardinality;

  inner_cpu_cost = guessed_result_cardinality * inner->variable_cpu_cost;
  if (qo_is_iscan (inner))
    inner_io_cost = guessed_result_cardinality * inner->variable_io_cost
                    * (1 - ISCAN_IO_HIT_RATIO);
  else
    inner_io_cost = (guessed_result_cardinality + SSCAN_DEFAULT_CARD)
                    * inner->variable_io_cost;

  planp->variable_cpu_cost = inner_cpu_cost + outer->variable_cpu_cost;
  planp->variable_io_cost  = inner_io_cost  + outer->variable_io_cost;
}

이 코드의 두 가지 기법은 교과서 그대로다. (a) inner 측 비용은 outer 의 총 비용 이 아니라 outer 의 카디널리티에 곱해진다. outer 행 하나당 inner 를 한 번씩 다시 돈다는 표준 공식이다. (b) inner 가 인덱스 스캔이면 IO 가 (1 - ISCAN_IO_HIT_RATIO) 로 가중된다 — 같은 outer 배치에서 연속으로 들어오는 인덱스 probe 들이 안정적인 비율로 버퍼 풀에 적중한다는 모델링이다. 가운데의 LIMIT 분기는 CUBRID 고유 기능이다 — LIMIT k 쿼리를 카디널리티 추정을 조기에 잘라 내고, 시작 비용이 작으면서 결과를 정렬된 순서로 만들어 내는 플랜을 선호하도록 유도한다.

2c — QG 위에서의 조인 열거

qo_search_partition_join 이 DP 루프다.

// qo_search_partition_join — src/optimizer/query_planner.c (condensed)
static QO_INFO *
qo_search_partition_join (QO_PLANNER * planner, QO_PARTITION * partition,
                          BITSET * remaining_subqueries)
{
  bitset_assign (&remaining_nodes, &QO_PARTITION_NODES (partition));
  nodes_cnt = bitset_cardinality (&remaining_nodes);

  /* Useful terms: every term whose nodes-set is a subset of this
   * partition's nodes. */
  for (i = 0; i < planner->T; i++)
    {
      term = &planner->term[i];
      if (QO_TERM_CLASS (term) == QO_TC_TOTALLY_AFTER_JOIN) continue;
      if (bitset_subset (&remaining_nodes, &QO_TERM_NODES (term)))
        {
          bitset_add (&remaining_terms, i);
          if (QO_TERM_CLASS (term) == QO_TC_PATH) num_path_inner++;
        }
    }

  /* Set the join window. Bigger queries → smaller partial DP. */
  if (num_path_inner || (hint & PT_HINT_ORDERED))
    planner->join_unit = nodes_cnt;                 /* full DP, no fan-out */
  else
    planner->join_unit = (nodes_cnt <= 25) ? MIN (8, nodes_cnt)
                       : (nodes_cnt <= 37) ? 3
                       :                     2;

  /* STEP 1 — partial-join sweep with first-node selection. */
  while (1)
    {
      planner_permutate (planner, partition, hint, /* prev_head: */ node,
                         &visited_nodes, &visited_rel_nodes, &visited_terms,
                         &nested_path_nodes, &remaining_nodes,
                         &remaining_terms, remaining_subqueries,
                         num_path_inner,
                         (planner->join_unit < nodes_cnt) ? &node_idx : NULL);
      if (planner->best_info)
        break;                                      /* OK, found best plan */

      if (planner->join_unit >= nodes_cnt)
        break;                                      /* full search exhausted */

      if (node_idx == -1)
        {
          /* STEP 2 — partial search failed; fall back to total search. */
          bitset_union (&remaining_nodes, &visited_nodes);
          bitset_union (&remaining_terms, &visited_terms);
          BITSET_CLEAR (visited_nodes);
          BITSET_CLEAR (visited_rel_nodes);
          BITSET_CLEAR (visited_terms);
          planner->join_unit = nodes_cnt;
          continue;
        }

      /* Promote the partial-best's outermost node. */
      node = QO_ENV_NODE (env, node_idx);
      bitset_add (&visited_nodes, node_idx);
      bitset_add (&visited_rel_nodes, QO_NODE_REL_IDX (node));
      bitset_remove (&remaining_nodes, node_idx);
      visited_info = (bitset_cardinality (&visited_nodes) == 1)
                     ? planner->node_info[node_idx]
                     : planner->join_info[
                         QO_INFO_INDEX (QO_PARTITION_M_OFFSET (partition),
                                        visited_rel_nodes)];
      if (visited_info == NULL) break;
      bitset_assign (&visited_terms, &visited_info->terms);
      bitset_difference (&remaining_terms, &visited_info->terms);
      planner->join_unit++;
    }
  return planner->best_info;
}

두 패스로 이루어진 형태가 이 코드의 등뼈다. 1 패스는 prefix 의 가장 바깥쪽 노드 한 개를 결정한 뒤, 그 노드에서 시작하는 join_unit 크기의 최적 prefix 를 만들고, 그 노드를 고정시킨 채 한 번 더 반복한다 — 바깥 루프 한 회마다 노드를 하나씩 승격시켜서, join_unit 이 nodes_cnt 에 도달하거나 모든 노드가 소진될 때까지 이어진다. 2 패스는 1 패스가 어떤 플랜도 찾지 못한 경우(의존성이나 outer-join 제약 때문에 모든 prefix 가 부분 조인 창 안에서 불가능한 경우) 에만 발동된다 — join_unit 을 nodes_cnt 로 넓히고 풀 DP 를 돌린다.

planner_permutate 자체는 후보 head 노드마다 planner_visit_node 를 부르는 안쪽 루프이고, planner_visit_node 가 진짜 DP 스텝이다.

// planner_permutate — src/optimizer/query_planner.c (condensed)
for (i = bitset_iterate (remaining_nodes, &bi); i != -1; ...)
  {
    head_node = QO_ENV_NODE (planner->env, i);

    /* Dependency / outer-dependency check. */
    if (!bitset_subset (visited_nodes, &QO_NODE_DEP_SET (head_node)))      continue;
    if (!bitset_subset (visited_nodes, &QO_NODE_OUTER_DEP_SET (head_node))) continue;

    if (bitset_is_empty (visited_nodes))
      {
        /* This is the first node of the join. Iterate over all
         * candidate second-nodes and call planner_visit_node for each. */
        bitset_add (visited_nodes, QO_NODE_IDX (head_node));
        for (j = bitset_iterate (remaining_nodes, &bj); j != -1; ...)
          {
            tail_node = QO_ENV_NODE (planner->env, j);
            if (!bitset_subset (visited_nodes, &QO_NODE_DEP_SET (tail_node)))      continue;
            if (!bitset_subset (visited_nodes, &QO_NODE_OUTER_DEP_SET (tail_node))) continue;
            planner_visit_node (planner, partition, hint, head_node, tail_node,
                                visited_nodes, visited_rel_nodes, visited_terms,
                                nested_path_nodes, remaining_nodes,
                                remaining_terms, remaining_subqueries,
                                num_path_inner);
            if (hint & PT_HINT_ORDERED) break;
          }
        /* Restore on backtrack. */
        BITSET_CLEAR (*visited_nodes);
      }
    else
      {
        /* Not the first node — extend prefix with head_node as new tail. */
        planner_visit_node (planner, partition, hint,
                            prev_head_node, head_node,
                            ...);
      }
    if (hint & PT_HINT_ORDERED) break;   /* /*+ ORDERED */ disables search */
  }

planner_visit_node 안에서 (수백 줄에 걸친 본체는 인용하지 않는다) 쌍별 조인 방법 열거가 디스패치된다.

flowchart TD
  V["planner_visit_node<br/>(outer = visited prefix 의 플랜,<br/>inner = 다음 단일 노드)"]
  V --> J{"visited prefix 와 inner 사이에<br/>join term 이 존재하는가?"}
  J -- "있음 (TC_JOIN edge)" --> A["qo_examine_idx_join<br/>→ qo_examine_correlated_index<br/>(inner 을 인덱스 스캔으로 만들고<br/>outer 값을 key range 로 push)"]
  J -- "있음" --> B["qo_examine_nl_join<br/>(inner = info 위 best plan,<br/>비용 = outer-card × inner-cost)"]
  J -- "있음 (mergeable edge)" --> C["qo_examine_merge_join<br/>(양쪽 모두 eqclass 위로 정렬)"]
  J -- "없음 (카르테시안)" --> D["스킵 — 이 DP 레벨에서는<br/>조인 불가"]
  A --> CHK["qo_check_plan_on_info<br/>per (joined-set, eqclass)"]
  B --> CHK
  C --> CHK
  CHK --> NEXT["planner->join_info[joined_set] 에<br/>저장"]

각 qo_examine_* 루틴은 적절한 종류의 후보 QO_PLAN 을 만들고, qo_plan_compute_cost 가 4 슬롯 비용을 채우게 한 뒤, dominance 검사에 제출한다.

qo_examine_idx_join 은 가장 싸게 끝나는 경로다. (a) inner 가 단일 클래스 스캔이고, (b) inner 에 outer 와의 조인 term 의 선두 컬럼과 일치하는 인덱스가 있으며, (c) 조인 힌트가 허용할 때만 발동된다. 이어서 qo_examine_correlated_index 가 조인 term 을 key range 로 삼는 인덱스 스캔 플랜을 만든다.

// qo_examine_idx_join — src/optimizer/query_planner.c (condensed)
static int
qo_examine_idx_join (QO_INFO * info, JOIN_TYPE join_type, QO_INFO * outer,
                     QO_INFO * inner, BITSET * afj_terms,
                     BITSET * sarged_terms, BITSET * pinned_subqueries)
{
  /* For RIGHT outer joins we converse outer/inner. */
  inner_node = (join_type == JOIN_RIGHT)
               ? QO_ENV_NODE (outer->env, bitset_first_member (&outer->nodes))
               : QO_ENV_NODE (inner->env, bitset_first_member (&inner->nodes));

  /* Hint gating: USE_MERGE / USE_HASH / USE_NL with non-IDX disable us. */
  if      (QO_NODE_HINT (inner_node) & (PT_HINT_USE_IDX | PT_HINT_USE_NL))   {}
  else if (QO_NODE_HINT (inner_node) & PT_HINT_USE_MERGE) goto exit;
  else if ((QO_NODE_HINT (inner_node) & PT_HINT_USE_HASH)
           && !(QO_NODE_HINT (inner_node) & PT_HINT_NO_USE_HASH)) goto exit;

  if (join_type == JOIN_RIGHT)
    n = qo_examine_correlated_index (info, JOIN_LEFT, inner, outer,
                                     afj_terms, sarged_terms,
                                     pinned_subqueries);
  else
    n = qo_examine_correlated_index (info, join_type, outer, inner,
                                     afj_terms, sarged_terms,
                                     pinned_subqueries);
exit:
  return n;
}

qo_examine_nl_join 은 항상 적용 가능한 폴백이다. inner 서브-info 의 가장 좋은 플랜을 골라 outer 와 짝지어 QO_JOINMETHOD_NL_JOIN 을 만든다. qo_examine_merge_join 은 outer 와 inner 모두 조인 term 의 동치류 위로 정렬 가능한 경우에만 발동된다 — 그래서 그래프 작성 단계에서 mergeable 한 모든 term 에 QO_EQCLASS 를 붙여 두는 것이다.

단계 3 — Query Graph → Compiled Graph (XASL)

qo_search_planner 가 반환되면 planner->best_info 가 각 파티션의 승리 DP 슬롯을 들고 있다. qo_combine_partitions 는 그것들을 카르테시안 곱으로 연결한다 (드물고, 보통은 파티션이 하나뿐이다). qo_plan_finalize 가 QO_PLANTYPE_SORT 래퍼와 내림차순 iscan 후처리를 마무리한다. 결과로 나오는 QO_PLAN 트리는 아직 CUBRID 서버가 그대로 실행할 수 있는 형식이 아니다. 호출자(XASL 생성기, xasl_generation.c) 가 qo_to_xasl 을 호출해서 변환한다.

// qo_to_xasl — src/optimizer/plan_generation.c (condensed)
xasl_node *
qo_to_xasl (QO_PLAN * plan, xasl_node * xasl)
{
  QO_ENV *env;
  XASL_NODE *lastxasl;

  if (plan && xasl && (env = plan->info->env))
    {
      xasl = gen_outer (env, plan, &EMPTY_SET, NULL, NULL, xasl);

      /* Walk to the deepest scan/fetch and push the SELECT-list
       * subqueries' dptrs there. */
      for (lastxasl = xasl; lastxasl; )
        {
          if      (lastxasl->scan_ptr) lastxasl = lastxasl->scan_ptr;
          else if (lastxasl->fptr_list) lastxasl = lastxasl->fptr_list;
          else break;
        }
      pt_set_dptr (env->parser, env->pt_tree->info.query.q.select.list,
                   lastxasl, MATCH_ALL);

      xasl = preserve_info (env, plan, xasl);
    }
  else
    xasl = NULL;
  return xasl;
}

gen_outer 는 모든 조인의 outer 측을 액세스-스펙 트리를 재귀적으로 emit 한다. 조인의 경우 inner 측의 액세스-스펙은 해당 XASL 노드에 매단다. QO_PLANTYPE_* 와 XASL 의 매핑은 직접적이다 — QO_PLANTYPE_SCAN 은 부모의 XASL_NODE::spec_list 안의 ACCESS_SPEC_TYPE 슬롯 하나가 되고, QO_PLANTYPE_JOIN 은 같은 XASL 위의 두 액세스-스펙 + 조인의 루프 구조를 통제하는 fptr_list / scan_ptr 계층이 되며, QO_PLANTYPE_SORT 는 임시 파일을 머터리얼라이즈하는 BUILDLIST_PROC 가 된다. selectivity 부기 — preserve_info — 는 플랜의 비용 요약을 원래의 PT_SELECT 에 매달린 qo_summary 에 저장하므로, 이 쿼리가 서브쿼리였다면 바깥 쿼리가 그 비용을 가져다 쓸 수 있다.

flowchart LR
  subgraph QOPLAN["QO_PLAN 트리 (선택된 플랜)"]
    direction TB
    JN["PLANTYPE_JOIN<br/>method=IDX_JOIN<br/>type=INNER"]
    SC1["PLANTYPE_SCAN<br/>method=SEQ_SCAN<br/>node=a, sargs={a.col2=1}"]
    SC2["PLANTYPE_SCAN<br/>method=INDEX_SCAN<br/>node=b, idx=(b.col1)<br/>range_terms={a.col1=b.col1}"]
    JN --> SC1
    JN --> SC2
  end
  QOPLAN --> XGEN["qo_to_xasl<br/>gen_outer"]
  XGEN --> XASL2["XASL_NODE 트리"]
  subgraph XASLR["XASL"]
    direction TB
    BL["BUILDLIST_PROC (top)<br/>spec_list, val_list,<br/>outptr_list"]
    AS1["ACCESS_SPEC (a)<br/>SCAN_TYPE_HEAP<br/>where_pred=a.col2=1"]
    AS2["ACCESS_SPEC (b)<br/>SCAN_TYPE_INDEX<br/>btid=idx_b_col1<br/>key_range=a.col1=b.col1"]
    BL --> AS1
    AS1 -. scan_ptr .-> AS2
  end

qo_to_xasl 이 끝나면 호출자는 XASL 트리를 바이트 스트림으로 직렬화하고 (xasl_to_stream.c) cub_server 로 보낸다. 서버 쪽에서는 stream_to_xasl.c 가 다시 그것을 트리 형태로 복원해서 query_executor.c 로 넘긴다. 옵티마이저의 역할은 그 바이트 스트림이 나오는 시점에 끝난다.

End-to-end 파이프라인 (전체 그림)

sequenceDiagram
    participant U as 사용자
    participant P as 파서
    participant SC as 의미 검사
    participant RW as 재작성기
    participant QG as build_query_graph
    participant AN as analyze/discover
    participant PL as qo_planner_search
    participant XL as qo_to_xasl
    participant SV as cub_server

    U->>P: SQL 문자열
    P->>P: csql_grammar.y → PT_NODE
    P->>SC: PT_NODE
    SC->>SC: pt_flat_spec_pre, bind_names,<br/>resolve_*, eval_type
    SC->>RW: resolved PT_NODE
    RW->>RW: CNF, 뷰 머지,<br/>oracle 식 outer-join,<br/>술어 push
    RW->>QG: 최적화된 PT_NODE
    QG->>QG: qo_add_node × N<br/>qo_add_term × T<br/>qo_add_dummy_join_term
    QG->>AN: QO_ENV
    AN->>AN: qo_classify_outerjoin_terms<br/>qo_discover_edges<br/>qo_assign_eq_classes<br/>qo_discover_indexes<br/>qo_discover_partitions
    AN->>PL: QO_ENV (주석 완료)
    PL->>PL: qo_alloc_planner<br/>노드별 액세스-패스<br/>파티션별 조인 DP<br/>파티션 결합<br/>qo_plan_finalize
    PL->>XL: QO_PLAN 트리
    XL->>XL: gen_outer 재귀,<br/>액세스-스펙 emit
    XL->>SV: XASL 바이트 스트림
    SV->>U: 결과 행

소스 코드 가이드

앵커는 심볼 이름에 둔다. 라인 번호가 아니다. 섹션 끝의 위치 힌트 표는 문서가 마지막으로 updated: 된 시점의 소스를 기준 으로 한 보조 정보일 뿐이다.

옵티마이저 진입 & 환경 (`src/optimizer/`)

qo_optimize_query (query_graph.c) — xasl_generation.c 에서 호출하는 공개 진입점. setjmp/longjmp 캐치 프레임을 친다.
qo_optimize_helper (query_graph.c) — 단계별 드라이버. 그래프 작성, 분류, edge/index/partition 디스커버리, qo_planner_search 호출까지 책임진다.
qo_env_init / qo_env_free (query_graph.c) — QO_ENV 할당과 해제.
qo_validate (query_graph.c) — 그래프 작성 후의 새너티 체크.

쿼리 그래프 타입 (`query_graph.h`)

struct qo_env — 최상위 컨테이너. 노드 / 세그 / 텀 / eqclass / 파티션의 평행 배열과 임시 비트셋 슬롯 tmp_bitset 을 갖는다.
struct qo_node — 관계당 그래프 노드 (QO_NODE_* 접근자 매크로 동반). 통계는 ncard/tcard, 의존성은 dep_set/outer_dep_set, 관계 위 인덱스 리스트는 indexes 에 들어간다.
struct qo_segment — 속성 등장 한 번당 그래프 segment (QO_SEG_* 매크로 동반).
struct qo_term — 술어 그래프 텀. 열 가지 값을 갖는 QO_TERMCLASS enum 과 비트로 인코딩된 QO_IS_PATH_TERM / QO_IS_EDGE_TERM / QO_IS_FAKE_TERM 술어가 여기에 있다.
struct qo_eqclass — interesting-order 동치류.
struct qo_partition — 연결 부분 그래프. join-info 인덱싱 용 M_offset 을 들고 있다.
struct qo_subquery — 상관 서브쿼리 디스크립터.
struct qo_index_entry, qo_node_index_entry, qo_node_index — 인덱스 메타와 segment 별 텀 룩업 테이블 (seg_equal_terms, seg_other_terms).
struct qo_using_index — USING INDEX 힌트 페이로드.

쿼리 그래프 빌더 (`query_graph.c`)

build_query_graph / build_query_graph_post / build_query_graph_function_index — PT_NODE 를 순회하는 parser_walk_tree 콜백.
build_graph_for_entity — PT_SPEC 단위 빌더 (QO_BUILD_STATUS 유한 상태 스테퍼).
qo_add_node — QO_NODE 를 할당하고 PT_SPEC 에 연결.
qo_insert_segment / qo_join_segment / lookup_seg — segment 할당 / 조인 segment 할당 / 룩업.
qo_add_final_segment — SELECT/GROUP BY/HAVING 리스트를 돌며 조인 후에도 살아남아야 하는 segment 를 표시.
qo_add_term — PT_NODE conjunct 하나를 QO_TERM 으로 승격 하고, 분류한 뒤, 노드/세그에 연결.
qo_add_dep_term — 상관 파생 테이블에 대한 QO_TC_DEP_LINK 합성.
qo_add_dummy_join_term — WHERE/ON 술어가 없는 ANSI 조인 에 대한 QO_TC_DUMMY_JOIN 합성.
qo_analyze_term — term_class, can_use_index, index_seg, equal-op / rangelist 플래그 설정.
qo_classify_outerjoin_terms — outer-joined 관계에 걸린 WHERE 절 술어를 QO_TC_DURING_JOIN / QO_TC_AFTER_JOIN / QO_TC_TOTALLY_AFTER_JOIN 로 분리.
qo_discover_edges — env->terms 를 술어 순서로 재정렬해 edge term 이 sarg term 보다 앞서도록 정리.
qo_assign_eq_classes — segment 들에 union-find 를 돌리고, 동치류마다 QO_EQCLASS 를 머터리얼라이즈.
qo_discover_indexes — 노드별로, 클래스 계층 위 인덱스로 QO_NODE_INDEX 를 채움.
qo_discover_partitions — 그래프 위 연결 컴포넌트 sweep, 컴포넌트당 QO_PARTITION 한 개.
qo_discover_sort_limit_nodes — LIMIT 플랜에 반드시 참여해야 하는 노드를 플래그.

비트셋 프리미티브 (`query_bitset.{h,c}`)

BITSET 불투명 타입 + bitset_init, bitset_assign, bitset_union, bitset_intersect, bitset_difference, bitset_subset, BITSET_MEMBER, bitset_iterate, bitset_next_member, bitset_first_member, bitset_cardinality, bitset_delset. {nodes, segs, terms, eqclasses, subqueries} 집합과 DP 테이블 키 모두에서 광범위 하게 쓰인다.

플래너 타입 (`query_planner.h`)

enum QO_PLANTYPE — SCAN | SORT | JOIN | FOLLOW | WORST.
enum QO_SCANMETHOD — SEQ_SCAN | INDEX_SCAN | INDEX_ORDERBY_SCAN | INDEX_GROUPBY_SCAN | INDEX_SCAN_INSPECT.
enum QO_JOINMETHOD — NL_JOIN | IDX_JOIN | MERGE_JOIN | HASH_JOIN.
struct qo_plan — 물리 플랜 노드. plan_un 유니온 (scan / sort / join / follow) 을 들고 있고, 4 개의 비용 필드, sarged_terms, subqueries, order 를 갖는다.
struct qo_planvec — (info, order) 슬롯 하나당 최대 NPLANS=4 개의 비-우세 플랜.
struct qo_info — DP 테이블 셀 (노드 부분집합당 하나). cardinality, scan_rows, total_rows, hit_prob, planvec 배열, best_no_order 단축 필드를 갖는다.
struct qo_planner — 최상위 플래너. node, term, node_info, join_info, cp_info, partition, best_info, worst_plan, worst_info.

플래너 코어 (`query_planner.c`)

qo_planner_search — 공개 진입점. 플래너 할당, 플랜 초기화, qo_search_planner 호출, 정리.
qo_alloc_planner — QO_ENV 의 배열들을 플래너로 복사 하고, 파티션 M_offset 을 설정한 뒤 M 을 합산.
qo_search_planner — 노드별 액세스-패스 루프, 파티션별 조인 드라이버, 파티션 결합, 내림차순 인덱스 후처리.
qo_search_partition — 단일 파티션 드라이버 (1 노드보다 큰 파티션은 qo_search_partition_join 으로 위임).
qo_search_partition_join — join_unit 창 스케일링이 들어간 partial-then-total DP 루프.
planner_permutate — 후보 head 노드마다 후보 inner 와 함께 planner_visit_node 를 호출.
planner_visit_node (인용 생략) — DP 스텝. 방문된 prefix 의 QO_INFO 를 가져와서 qo_examine_*_join 을 디스패치하고, 결과를 join_info[QO_INFO_INDEX(...)] 에 다시 써 넣는다.
qo_examine_idx_join — 인덱스 상관 조인 (가장 싼 경로).
qo_examine_nl_join — 일반 nested-loop 폴백.
qo_examine_merge_join — 공유된 동치류 위에서의 sort-merge.
qo_examine_correlated_index — outer 의 조인 값을 key range 로 쓰는 inner 인덱스 스캔 플랜을 만든다.
qo_check_plan_on_info — dominance 검사. 이 후보가 고려된 뒤 planvec 에 살아남은 플랜 수를 반환.
qo_seq_scan_new — sequential-scan 플랜 할당 + 비용 fn 호출.
qo_index_scan_new — index-scan 플랜 할당 (range, filter, kf term 세팅) + 비용 fn 호출.
qo_join_new — 조인 플랜 할당 (방법은 호출자가 선택). order 전파를 계산.
qo_worst_new — 무한히 비싼 sentinel 플랜 할당 (examine 루틴이 아무것도 만들지 못할 때 사용).
qo_plan_finalize — 최상위 마무리 (descending-index 전파, sort-list 가지치기).
qo_combine_partitions — 파티션별 승자들의 카르테시안 곱 결합.
sort_partitions — 결합 전, 파티션 간 의존성 순서로 파티션을 정렬.

비용 모델 (`query_planner.c`)

qo_plan_compute_cost — vtbl 디스패처. plan->vtbl->cost_fn(plan) 을 부르고 상관 서브쿼리 비용을 더한다.
qo_iscan_cost — 인덱스 스캔의 4 슬롯 비용.
qo_seq_scan_cost — sequential 스캔의 4 슬롯 비용.
qo_nljoin_cost — nested-loop 조인의 4 슬롯 비용 (LIMIT pushdown 분기 포함).
qo_mjoin_cost — sort-merge 조인의 4 슬롯 비용.
qo_sort_cost, qo_follow_cost, qo_worst_cost, qo_zero_cost — 디스패치 말단들.
qo_plan_compute_subquery_cost — 일회성 서브쿼리 비용 (캐시된 QO_SUMMARY 사용).
qo_plan_cmp — 3-way 플랜 비교자 (PLAN_COMP_LT/EQ/GT/UNK). planvec 의 dominance 검사가 사용.
qo_plan_cmp_prefer_covering_index — covering-index 타이브레이커.

Selectivity (`query_planner.c`)

qo_expr_selectivity — PT_EXPR 위의 재귀 selectivity 워커. 연산자별 디스패치.
qo_equal_selectivity, qo_comp_selectivity, qo_between_selectivity, qo_range_selectivity, qo_or_selectivity, qo_and_selectivity, qo_not_selectivity — 연산자별 leaf.

XASL emit (`plan_generation.c`)

qo_to_xasl — 옵티마이저가 끝난 뒤 xasl_generation.c 에서 부르는 공개 진입점.
gen_outer — 플랜의 outer 측을 재귀적으로 emit. inner 는 gen_inner 로 위임.
make_scan_proc, make_buildlist_proc — 최상위 XASL 골격 생성.
add_access_spec — 스캔 플랜 하나로 ACCESS_SPEC_TYPE 하나를 채움.
make_pred_expr — PT_EXPR 을 런타임 술어 식으로 lowering.
make_outptr_list — SELECT 절로부터 프로젝션 리스트 생성.
preserve_info — 부모 PT_SELECT 에 QO_SUMMARY 를 저장해, 호출자가 비용을 다시 계산할 수 있게 한다.

위치 힌트 (2026-04-30 기준)

심볼	파일	라인
`qo_optimize_query`	`optimizer/query_graph.c`	353
`qo_optimize_helper`	`optimizer/query_graph.c`	424
`qo_env_init`	`optimizer/query_graph.c`	633
`qo_validate`	`optimizer/query_graph.c`	762
`build_query_graph`	`optimizer/query_graph.c`	942
`build_query_graph_post`	`optimizer/query_graph.c`	982
`build_query_graph_function_index`	`optimizer/query_graph.c`	1010
`build_graph_for_entity`	`optimizer/query_graph.c`	1107
`qo_add_node`	`optimizer/query_graph.c`	1243
`lookup_node`	`optimizer/query_graph.c`	1374
`qo_insert_segment`	`optimizer/query_graph.c`	1493
`qo_join_segment`	`optimizer/query_graph.c`	1599
`lookup_seg`	`optimizer/query_graph.c`	1620
`qo_add_final_segment`	`optimizer/query_graph.c`	1690
`qo_add_term`	`optimizer/query_graph.c`	1718
`qo_add_dep_term`	`optimizer/query_graph.c`	1837
`struct qo_node`	`optimizer/query_graph.h`	265
`struct qo_segment`	`optimizer/query_graph.h`	436
`struct qo_eqclass`	`optimizer/query_graph.h`	527
`enum QO_TERMCLASS`	`optimizer/query_graph.h`	562
`struct qo_term`	`optimizer/query_graph.h`	591
`struct qo_partition`	`optimizer/query_graph.h`	797
`struct qo_env`	`optimizer/query_graph.h`	849
`enum QO_PLANTYPE`	`optimizer/query_planner.h`	42
`enum QO_SCANMETHOD`	`optimizer/query_planner.h`	51
`enum QO_JOINMETHOD`	`optimizer/query_planner.h`	60
`struct qo_plan`	`optimizer/query_planner.h`	113
`struct qo_planvec`	`optimizer/query_planner.h`	248
`struct qo_info`	`optimizer/query_planner.h`	256
`struct qo_planner`	`optimizer/query_planner.h`	337
`QO_CPU_WEIGHT`	`optimizer/query_planner.c`	79
`ISCAN_OID_ACCESS_OVERHEAD`	`optimizer/query_planner.c`	80
`ISCAN_IO_HIT_RATIO`	`optimizer/query_planner.c`	85
`GUESSED_BIND_LIMIT_CARD`	`optimizer/query_planner.c`	87
`qo_plan_compute_cost`	`optimizer/query_planner.c`	750
`qo_seq_scan_new`	`optimizer/query_planner.c`	1678
`qo_index_scan_new`	`optimizer/query_planner.c`	1784
`qo_iscan_cost`	`optimizer/query_planner.c`	2078
`qo_join_new`	`optimizer/query_planner.c`	2844
`qo_nljoin_cost`	`optimizer/query_planner.c`	3315
`qo_mjoin_cost`	`optimizer/query_planner.c`	3465
`qo_plan_cmp_prefer_covering_index`	`optimizer/query_planner.c`	4044
`qo_plan_cmp`	`optimizer/query_planner.c`	4098
`qo_plan_finalize`	`optimizer/query_planner.c`	5059
`qo_check_plan_on_info`	`optimizer/query_planner.c`	5942
`qo_examine_idx_join`	`optimizer/query_planner.c`	6151
`qo_examine_nl_join`	`optimizer/query_planner.c`	6234
`qo_examine_merge_join`	`optimizer/query_planner.c`	6404
`qo_alloc_planner`	`optimizer/query_planner.c`	7044
`planner_permutate`	`optimizer/query_planner.c`	8190
`qo_planner_search`	`optimizer/query_planner.c`	8352
`qo_generate_join_index_scan`	`optimizer/query_planner.c`	8389
`qo_generate_index_scan`	`optimizer/query_planner.c`	8639
`qo_search_planner`	`optimizer/query_planner.c`	8879
`qo_search_partition_join`	`optimizer/query_planner.c`	9309
`qo_search_partition`	`optimizer/query_planner.c`	9471
`qo_combine_partitions`	`optimizer/query_planner.c`	9576
`qo_expr_selectivity`	`optimizer/query_planner.c`	9710
`make_scan_proc`	`optimizer/plan_generation.c`	133
`make_buildlist_proc`	`optimizer/plan_generation.c`	728
`add_access_spec`	`optimizer/plan_generation.c`	895
`qo_to_xasl`	`optimizer/plan_generation.c`	2915

소스 검증 노트

세 raw 분석은 모두 슬라이드 덱이다. 그래서 어쩔 수 없이 정밀하지 않은 부분이 있고, 현재 소스와의 시간차가 있다. 슬라이드와 소스를 나란히 두고 읽는 사람이 어디까지 슬라이드를 믿고, 어디부터는 소스를 믿어야 할지 짚어 둔다.

analysis_QP_optimizer_1.0.pptx 는 2019-07-25 작성으로, 이후의 몇 가지 개선이 반영되어 있지 않다.
- 슬라이드 22 는 join_info 벡터를 정확히 2^N 슬롯으로 표현 한다. 현재 소스는 파티션마다 M_offset + 2^|partition| 만큼을 잡는다 (qo_alloc_planner, query_planner.c:7044). 파티션이 하나일 때만 두 표현이 같다. 카르테시안 곱 워크로드에서는 planner->M 이 파티션별 합계가 된다.
- 슬라이드 25 (first-node 선별) 는 first-node 선택 로직이 비용 비교에서 조인 관련 인덱스를 고려하지 않는다는 사실을 적어 두었다. 현재 소스의 planner_permutate 도 이 성질을 그대로 갖고 있고, 비용은 best_plan->fixed + variable 에 미방문 노드에 대한 planner_nodeset_join_cost 가 더해지는 형태다. 슬라이드의 지적이 지금도 유효하다.
- 슬라이드 27 은 조인 방법으로 idx_join, nl_join, merge_join 셋만 적어 두었다. 현재 소스에는 (hash-list 조인 기능이 추가된 이후) QO_JOINMETHOD_HASH_JOIN 도 있지만, 별도의 qo_examine_hash_join 이 아니라 qo_join_new 를 통과하는 hash_terms 전파 경로로 게이트된다.
- 슬라이드 28 의 플랜 비교 우선순위 표 (plan_type_scan > plan_type_sort 등) 는 단일 플랜 단위에서는 여전히 qo_plan_cmp 를 정확하게 묘사한다. 다만 그 위에서 한 단계 더 도는 qo_plan_cmp_prefer_covering_index 는 이후에 추가된 별도 루틴이다.
[CUBRID QP] Parsing to Query Graph.pptx (2025-07) 는 최근 자료라 소스와 거의 일치한다. 한 가지 주의할 점은 슬라이드 4–6 이 Query Graph 와 재작성기 후 PT_NODE 트리를 같은 것처럼 말한다는 점이다. 소스에서는 build_query_graph 가 재작성된 PT_NODE 로부터 QO_ENV 를 생성하는 parser_walk 콜백이며, QG 는 QO_ENV 그 자체이지 더 풍부해진 PT_NODE 가 아니다.
[CUBRID QP] QG to CG.pptx (2025-08) 의 구조 슬라이드 1–32 는 앞 덱과 사실상 동일하고, plan enumeration 과 code generation 슬라이드 (33+) 에서만 갈라진다. 플랜 열거 설명은 qo_search_partition_join 의 두 단계 구조를 충실히 따라간다.
PT_NODE 재작성기는 소스 레이아웃 기준으로는 옵티마이저 모듈 바깥이지만 슬라이드 덱 기준으로는 안에 들어와 있다. mq_rewrite 는 parser/ 에 살고 optimizer/ 에 있지 않다. qo_optimize_helper 는 큰 규모의 트리 재작성을 하지 않고 분석만 한다. 뷰 머지와 CNF 정규화는 모두 상류에서 끝나 있고, 옵티마이저는 정규화된 PT_NODE 를 가정한다.
슬라이드 25 의 first-node 선별 코멘트는 본 문서에도 보존해 둘 가치가 있다. 조인이 많고, 첫 번째 테이블이 아닌 다른 테이블 에 선택성 높은 인덱스 조건이 걸려 있는 쿼리에서는 이 성질이 플랜 품질에 실질적인 영향을 준다.
QO_JOINMETHOD_HASH_JOIN 은 도달 가능하지만 전용 qo_examine_hash_join 으로 열거되지는 않는다. hash list scan 은 qo_examine_nl_join → qo_join_new 를 통과하는 동안 적절한 hash 힌트가 켜져 있을 때 hash_terms 비트셋 전파로 선택된다. 덱이 말하는 세 가지 조인 방법 표현은 비용 모델 단위에서는 정확하지만 조인 방법 enum 단위에서는 약간의 과소집계로 보면 된다.

미해결 질문

qo_optimize_query 의 setjmp / longjmp 캐치 프레임이 여전히 필요한가? 엔진 코드에서 현대 C++17 예외는 사용되지 않지만 (CLAUDE.md 의 전역 anti-pattern 규칙), 현대적인 error-return 스타일은 쓰인다. 조사 경로: QO_ABORT 와 QO_ASSERT 의 모든 호출 지점을 추적하고, longjmp 대신 throw 가 가능했을 만한 C++17 코드가 도달할 수 있는지 확인하는 것이다.
부분 조인 join_unit 이 8 / 3 / 2 로 고정된 이유는 무엇인가. qo_search_partition_join 은 25 테이블 이하에서는 MIN(8, nodes_cnt), 26–37 에서는 3, 그 이상에서는 2 로 하드 코딩되어 있다. 소스 주석이 언급하는 Sybase Adaptive Server 계열의 영향을 감안하면 이 숫자들은 경험칙으로 보인다. 조사 경로: nodes_cnt 를 변화시키면서 벤치마크를 sweep 하고 planner->best_info->cost 를 계측해 창을 넓힐 때 실제 플랜 이 개선되는지 확인하는 것이다.
QO_JOINMETHOD_HASH_JOIN 의 열거 커버리지. 해시 조인은 비어 있지 않은 hash_terms 비트셋과 함께 qo_join_new 로 생성되며, 이 비트셋은 merge / idx examine 루틴 안쪽에서 계산된다. 해시 list 스캔이 제안될 기회 자체가 없는 조인 모양 (예: 큰 sargable 필터가 하나 걸린 카르테시안 곱) 이 있는가? 조사 경로: qo_examine_* 의 hash_terms 전파 로직과 조인 힌트 게이팅을 읽어 본다.
ISCAN_IO_HIT_RATIO = 0.5 는 추측값이다. 이 상수는 nested-loop 조인 안의 inner 인덱스 probe 가 버퍼 풀에 hit 하는 비율을 모델링한다. 실제 hit 율은 워크로드 지역성, 버퍼 풀 크기, outer 카디널리티에 좌우된다. 이 상수가 도입하는 비용 모델 오차를 누가 측정해 본 적이 있는가? 조사 경로: qo_nljoin_cost 를 계측하고 TPC-H 같은 워크로드에서 예측 inner I/O 와 관측 inner I/O 를 비교한다.
QO_CPU_WEIGHT = 0.0025 의 캘리브레이션. 이 상수는 4 슬롯 비용 모델에서 CPU 와 I/O 단위를 trade-off 한다. 현대 하드 웨어 (NVMe, 큰 DRAM) 의 I/O-CPU 비율은 이 상수가 처음 캘리브레이션된 1990 년대 하드웨어와 매우 다르다. 조사 경로: 대표적인 현대 워크로드에서 상수를 다시 적합시켜, 값을 줄였을 때 플래너가 인덱스 플랜을 너무 좋아하게 되는지 적절히 좋아하게 되는지 확인한다.
플랜 캐시 피드백 루프. XASL 캐싱은 같은 플랜을 여러 실행 에서 재사용한다는 뜻이다. 그동안 바인드 변수 값은 표류할 수 있고, 결국 그 플랜을 만들 때 썼던 카디널리티 추정이 이미 낡았을 수 있다. 옵티마이저가 통계 변화가 임계치를 넘었을 때 캐시된 플랜을 무효화하는가, 아니면 명시적 DDL / UPDATE STATISTICS 만 무효화 트리거인가? 조사 경로: query/query_executor.c 의 XASL-cache 무효화 후크를 읽는다.
qo_check_plan_on_info dominance 와 NPLANS=4. 왜 정확히 4 인가? 경험적으로는 동시에 살려 둘 만한 interesting order 넷 정도 (무순서 한 개에 가능성 높은 정렬 한두 개) 면 충분 하다고 본 결정으로 보이지만, 소스에는 이 선택에 대한 코멘트 가 없다. NPLANS=4 가 부족한 워크로드가 있을까? 조사 경로: qo_check_plan_on_info 에 오버플로우 카운터를 붙이고, 컬럼 이 많은 와이드 테이블 벤치마크를 돌려 본다.
중첩 outer join 에서의 qo_classify_outerjoin_terms 정합성. outer join 이 중첩될 때 (예: a LEFT JOIN (b LEFT JOIN c ON …) ON …) DURING_JOIN / AFTER_JOIN / TOTALLY_AFTER_JOIN 의 분리는 섬세해진다. 슬라이드 덱은 이 케이스를 다루지 않는다. 조사 경로: 루틴을 끝까지 읽고, 적대적인 테스트 케이스를 만든 다음, PostgreSQL 의 outer-join 플래너 (prepjointree.c) 와 diff 해 본다.

출처

Raw 분석 (`raw/code-analysis/cubrid/query-processing/`)

analysis_QP_optimizer_1.0.pptx — 원본 옵티마이저 개요 덱 (2019-07-25, team2). 32 슬라이드. parser → semantic check → rewriter → optimizer → QO_ENV → planner → plan 까지 다룬다. term-class 분류 체계와 조인 방법 비교의 표준 출처.
[CUBRID QP] Parsing to Query Graph.pptx — 류형규, 2025-07. 1 번 덱보다 깊게 PT_NODE → QO_ENV 파이프라인을 따라간다.
[CUBRID QP] QG to CG.pptx — 같은 저자, 2025-08. 플랜 열거와 XASL emission 을 다룬다.
_converted/analysisqpoptimizer1.0.pptx.md, _converted/cubrid-qp-parsing-to-query-graph.pptx.md, _converted/cubrid-qp-qg-to-cg.pptx.md — markitdown 텍스트 추출본.

본 KB 의 자매 문서

knowledge/code-analysis/cubrid/cubrid-mvcc.md — 인덱스 스캔 과 seq 스캔 액세스 스펙이 행 단위로 호출하는 MVCC 가시성 술어.
knowledge/code-analysis/cubrid/cubrid-heartbeat.md — 직접 관계는 없으며, 단순 교차 링크.

교과서 / 논문

Selinger, Astrahan, Chamberlin, Lorie, Price, Access Path Selection in a Relational Database Management System, SIGMOD 1979 — CUBRID 플래너의 직접 조상인 System R DP 옵티마이저의 표준 인용이다. 특히 §3.2 (Cost formulas), §3.3 (Order preservation in joins, interesting orders), §4 (Multi-relation queries, left-deep DP, dominance pruning) 가 관련 절이다.
Graefe, The Cascades Framework for Query Optimization, IEEE Data Eng. Bull. 1995 — CUBRID 가 속하지 않는 규칙 기반 옵티마이저 계열을 비교 목적으로 인용.
Hellerstein, Stonebraker, Hamilton, Architecture of a Database System, FnT in Databases 2007, §6 “Relational Query Processor” — 설계 공간을 정리한 현대적 서베이.
Database Internals (Petrov), Ch. “Query Processing and Optimization” — 본 문서의 교과서적 틀.

CUBRID 소스 (`/data/hgryoo/references/cubrid/`)

src/optimizer/optimizer.h — 공개 타입과 진입점 프로토타입.
src/optimizer/query_graph.h — QO_NODE, QO_SEGMENT, QO_TERM, QO_EQCLASS, QO_PARTITION, QO_ENV 와 접근자 매크로.
src/optimizer/query_graph.c — 그래프 빌더, qo_optimize_*, edge / eq-class / index / partition 디스커버리, term 분석.
src/optimizer/query_planner.h — QO_PLAN, QO_PLANVEC, QO_INFO, QO_PLANNER 와 enum.
src/optimizer/query_planner.c — DP 탐색, 비용 모델, qo_examine_* 루틴, selectivity 계산.
src/optimizer/plan_generation.c — qo_to_xasl 과 플랜 타입별 XASL_NODE / ACCESS_SPEC_TYPE lowering.
src/optimizer/query_bitset.{c,h} — 옵티마이저 모든 영역 에서 쓰이는 set-of-int 프리미티브.
src/parser/parse_tree.h — 옵티마이저 진입점이 소비하는 PT_NODE 정의.
src/query/xasl.h — qo_to_xasl 이 만들어 내는 XASL_NODE / ACCESS_SPEC_TYPE.
src/xasl/ — 모듈화된 XASL 타입 헤더.
src/parser/xasl_generation.c — qo_optimize_query 와 qo_to_xasl 의 호출자. optimizer/ 에 속하지는 않지만 진입 표면(entry surface) 이다.