(KO) CUBRID 통계 — 카디널리티, NDV, Min/Max, 그리고 비용 옵티마이저용 히스토그램

목차

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

학술적 배경

비용 기반 옵티마이저는 query 가 실제로 돌기 전에 각 연산자가 몇 개의 튜플을 만들어 낼지를 미리 알아맞혀야 한다. Database Internals (Petrov, “Query Processing and Optimization” 장; 동등하게 Hellerstein –Stonebraker–Hamilton, Architecture of a Database System §6.3 “Plan Space” 와 §6.4 “Selectivity Estimation”) 가 이 문제를 세 겹의 질문으로 풀어 놓는다.

1. 비용 모델이 원하는 숫자가 무엇인가. 두 보편 입력은 카디널리티 (predicate 나 join 을 통과하고 살아남는 행 수) 와 I/O 풋프린트 (그 행들이 사는 페이지 수) 다. Selinger 의 System R 논문 Access Path Selection in a Relational Database Management System (Selinger et al., SIGMOD 1979) §3 이 지금도 쓰이는 비용 방정식을 못 박는다. cost = page_fetches + W * RSI_calls 이고, W 는 CPU 와 I/O 의 가중치다. 카디널리티는 base table 에서는 selectivity * |R| 이고, join 에서는 입력을 재귀적으로 곱이 전파된다.
2. selectivity 는 데이터에서 어떻게 도출하는가. 사십 년간 실 서비스에서 쓰인 근사가 셋 있고, 셋 모두 CUBRID 코드에서 보인다.
   • 균등 분포 가정. 컬럼 col 의 NDV 가 D 인 등치 predicate col = const 를, 각 distinct 값이 |R|/D 번 등장한다고 가정해 selectivity 를 1/D 로 둔다 (Selinger §3.2). 범위 predicate 는 min/max 가 알려져 있다면 (hi-lo)/(MAX-MIN) 이 된다.
   • 독립성 가정. p AND q 는 곱한다 (sel(p) * sel(q)). p OR q 는 inclusion-exclusion 으로 sel(p) + sel(q) - sel(p)*sel(q) 다. 컬럼이 상관되어 있으면 틀리지만 싸다.
   • 히스토그램. 컬럼 값 공간을 equi-width 또는 equi-depth 로 bucket 분할하고, skew 처리를 위해 MCV (most common values) 리스트를 옵션으로 둔다. 고전적 서베이는 Poosala et al., Improved Histograms for Selectivity Estimation of Range Predicates (SIGMOD 1996) 이며, 아이디어 자체는 Kooi 의 박사 논문 (1980) 과 Piatetsky-Shapiro & Connell, Accurate Estimation of the Number of Tuples Satisfying a Condition (SIGMOD 1984) 으로 거슬러 올라간다.
3. 테이블을 매번 통째로 읽지 않고 그 숫자들을 어떻게 모으는가. 세 가지 표본 추출 체제가 있다.
   • Full scan. 정확하지만 테이블 크기에 비례한다.
   • Page sampling. heap 페이지 k 개를 무작위로 골라 distinct 값을 세고 scale-up 한다. 분산이 한정된다. 이론적 토대는 Haas & Stokes, Estimating the Number of Classes via Sample Coverage (J. Stat. Comp. 1998) 이다. 표본으로부터 NDV 를 추정하는 것은 원리적으로 어렵다는 사실 (Charikar–Chaudhuri– Motwani–Narasayya, Towards Estimation Error Guarantees for Distinct Values, PODS 2000) 이 알려져 있고, 대부분의 엔진 은 그 편향을 받아들이고 산다.
   • 스트리밍 스케치. HyperLogLog 부류로, 아직 CUBRID 에는 없다.

이 모델이 비워 둔 두 가지 구현 결정이 모든 실제 엔진의 모양을 결정하고 본 문서의 나머지를 틀 짓는다.

1. 히스토그램의 분해 단위가 무엇인가. 컬럼별 full equi-depth bucket 배열인가 (PostgreSQL 의 pg_statistic.stahistogram)? 인덱스별 partial-key distinct count 인가 (CUBRID 의 BTREE_STATS::pkeys)? 둘 다인가 (Oracle)? CUBRID 은 인덱스별 partial-key 카운트와 컬럼별 NDV 스칼라 하나를 고른다. 컬럼별 bucket 배열은 두지 않는다.
2. 옵티마이저는 그 숫자를 어디서 가져 오는가. 인메모리 스키마 객체에 캐시해 둔 채 (CUBRID, MySQL) 가져 오는가, 시스템 view 로 그때그때 가져 오는가 (PostgreSQL pg_statistic)? CUBRID 은 캐시된 스키마 객체 경로다. 통계는 SM_CLASS 워크스페이스 캐시와 함께 다니고, UPDATE STATISTICS 가 떨어지면 새로 고친다.

이 두 결정이 짚어지고 나면, 본 문서의 모든 CUBRID 구체 구조는 둘 중 하나를 구현하거나 그 접근을 빠르게 만든다는 점이 분명해진다.

DBMS 공통 설계 패턴

모든 관계형 엔진은 통계 수집 주변에서 비슷한 패턴들을 잡아 든다.

테이블별 표본 + 컬럼별 digest

어떤 형태의 ANALYZE 가 heap 을 (full 또는 sampled) 워크하면서 컬럼별 요약 (NDV, min, max, MCV, 히스토그램) 을 만들어 시스템 카탈 로그에 쓴다. 옵티마이저는 parse/plan 시점에 카탈로그를 읽고, 런타임 엔 절대 읽지 않는다. 요약은 시간이 지나면 낡고 새로 고침이 필요해진 다 — 백그라운드 스케줄로 (Oracle 의 자동 stats job), row-count 임계 로 (PostgreSQL autovacuum_analyze), 또는 사용자가 DDL 을 발행할 때만 (CUBRID 의 UPDATE STATISTICS).

공짜 통계 출처로서의 B+Tree

leaf 까지 워크된 B+Tree 는 이미 자기 key 수, leaf 페이지 수, height, 그리고 (key 연결을 사용하면) 다중 컬럼 키의 임의 prefix 의 distinct count 를 알고 있다. 인덱스를 진실의 원천으로 쓰는 편이 heap 에서 다시 도출하는 것보다 싸며, 인덱스가 있는 컬럼에 대해서는 CUBRID, MySQL InnoDB (mysql.innodb_index_stats), Oracle 의 DBMS_STATS.GATHER_INDEX_STATS 모두 그렇게 한다.

인덱스 워크가 아닌 query 로 NDV 를 얻기

비인덱스 컬럼의 NDV 는 B+Tree 에서 읽어 낼 수 없다 — 그런 트리가 없기 때문이다. 가장 싼 구현은 SELECT count(distinct col1), count(distinct col2), …, count(*) FROM tbl 을 발행해 기존 query 실행기에 장부를 맡기는 것이다. 표본 힌트를 옵션으로 함께 줄 수도 있다. CUBRID 가 정확히 이 경로를 택한다 — stats_make_select_list_for_ndv 가 컬럼 리스트를 만들고 stats_get_ndv_by_query 가 SQL 을 돌리며, fullscan 이 아닐 때는 /*+ SAMPLING_SCAN */ 힌트가 붙는다.

캐시된 스키마 객체 vs. on-demand 카탈로그 read

PostgreSQL 은 매 plan 마다 pg_statistic 을 다시 읽는다. CUBRID 은 CLASS_STATS 를 SM_CLASS 워크스페이스 객체에 캐시하고, 매 UPDATE STATISTICS 후에 새로 고친다. 이후 같은 connection 에서의 query 는 서버 round-trip 없이 캐시된 구조를 읽는다. trade-off 는 staleness 와 plan-time 지연 간의 교환이며, xstats_get_statistics_from_server 가 검사하는 timestamp 가 일부 완화한다.

CUBRID 의 위치

CUBRID 의 설계는 세 고전 엔진의 하이브리드다.

측면	PostgreSQL	MySQL InnoDB	Oracle	CUBRID
트리거	autovacuum + 수동 ANALYZE	DDL 시 영구화 + 수동	자동 job + 수동	수동 UPDATE STATISTICS 만
heap 워크	무작위 페이지 표본	무작위 인덱스 표본	블록 표본	full scan + B+Tree 위 reservoir
히스토그램 종류	equi-depth + MCV	없음. prefix 별 NDV 만	equi-depth 또는 hybrid	없음. prefix 별 NDV 만
NDV 출처	표본 + 보정 공식	인덱스 leaf 워크	표본 + 보정	SQL count(distinct) (sampled 또는 full)
저장	시스템 테이블 pg_statistic	mysql.innodb_*_stats 테이블	SYS.WRI$_OPTSTAT_*	카탈로그 CLS_INFO + DISK_REPR + 시스템 클래스 _db_class 행
옵티마이저 access	plan 시점 카탈로그 lookup	스키마 캐시	카탈로그 lookup	SM_CLASS::stats 워크스페이스 캐시

가장 결과가 큰 CUBRID 고유 선택은 컬럼별 히스토그램의 부재다. 디스크 위에 equi-depth bucket 배열이 없다. 그래서 partial-key NDV 만으로는 답할 수 없는 모든 범위 predicate 비용 계산이 query_planner.c 의 DEFAULT_*_SELECTIVITY 상수로 회귀한다.

CUBRID의 구현

통계 서브시스템은 저장 계층 (행 레이아웃을 알고 B+Tree 를 워크할 수 있는 쪽) 과 옵티마이저 (query 모양을 알고 행 수 추정이 필요한 쪽) 사이의 다리다. 그 다리는 UPDATE STATISTICS DDL 마다 단 한 번 다시 세워진다 — autovacuum 도, 시간 기반 새로 고침도, 읽기 경로 위 표본도 없다.

무엇을 모으는가

각 클래스마다 CUBRID 은 정확히 세 가족의 숫자를 유지한다. 모두 디스 크 위 클래스 representation 레코드 (DISK_REPR) 와 클래스 정보 레코드 (CLS_INFO) 위에 정착한다.

// btree_stats — src/storage/statistics.h
struct btree_stats
{
  BTID btid;
  int leafs;        /* number of leaf pages including overflow pages */
  int pages;        /* number of total pages */
  int height;       /* the height of the B+tree */
  int keys;         /* number of keys */
  int has_function; /* is a function index */
  TP_DOMAIN *key_type;
  int pkeys_size;   /* pkeys array size */
  int *pkeys;       /* partial keys info: pkeys[0] -> # of {a},
                     *                    pkeys[1] -> # of {a,b}, ... */
  int dedup_idx;    /* support for SUPPORT_DEDUPLICATE_KEY_MODE */
};

struct attr_stats
{
  int id;
  DB_TYPE type;
  int n_btstats;
  BTREE_STATS *bt_stats;
  INT64 ndv;        /* Number of Distinct Values of column */
};

struct class_stats
{
  unsigned int time_stamp;
  int heap_num_objects;  /* cardinality of the class */
  int heap_num_pages;    /* heap-file footprint */
  int n_attrs;
  ATTR_STATS *attr_stats;
};

클래스 단위 숫자는 heap_num_objects (전체 행 수, 비용 방정식 의 |R|) 와 heap_num_pages (페이지 단위 heap 파일 풋프린트, 순차 및 full-table I/O 의 크기를 가늠하는 데 쓴다) 다. attribute 단위 숫자는 컬럼별 NDV 인 attr_stats::ndv 다. 인덱스 단위 숫자는 leafs, pages, height, keys 와 partial-key 배열 pkeys[] 이며, pkeys[i] 는 다중 컬럼 인덱스의 처음 i+1 컬럼의 distinct count 다.

히스토그램은 없다 — MCV 배열도, equi-depth 경계 리스트도, bucket 별 frequency 도 없다. 공개 레벨에는 min/max 레코드도 없다 (내부 적으로 STATS_MIN_MAX_SIZE 가 정의되어 있지만 주변 필드는 폐기되 었다). 옵티마이저로 출하되는 유일한 컬럼별 영구 스칼라는 ndv 뿐 이다. 이는 의도된 단순화다 — partial-key NDV 가 predicate 에 답할 수 없을 때 옵티마이저는 고정 selectivity 상수로 회귀한다.

수집 경로

UPDATE STATISTICS 는 네트워크 계층으로 서버로 디스패치되며, 거기서 xstats_update_statistics 가 클래스에 SCH_S_LOCK 을 단 하나만 잡고 끝까지 돈다 — reader 는 스캔할 수 있고 스키마는 변할 수 없으며 같은 클래스에 대한 다른 UPDATE STATISTICS 는 직렬화 된다.

flowchart TD
  A["UPDATE STATISTICS<br/>parser PT_UPDATE_STATS"] --> B["execute_statement.c<br/>do_update_stats()"]
  B --> C["sm_update_statistics<br/>schema_manager.c"]
  C --> D["network_interface_cl<br/>stats_update_statistics"]
  D --> E["network_interface_sr<br/>handler 4278"]
  E --> F["xstats_update_statistics<br/>(서버, SCH_S_LOCK)"]
  F --> G["catalog_get_class_info<br/>cls_info_p"]
  F --> H["catalog_get_representation<br/>disk_repr_p"]
  F --> I["partition_get_partition_oids"]
  I -->|count > 0| J["stats_update_partitioned_statistics<br/>(파티션별 + 누적기)"]
  I -->|count == 0| K["btree_get_stats — 인덱스별"]
  K --> L["btree_get_stats_with_fullscan<br/>또는 btree_get_stats_with_AR_sampling"]
  C --> M["NDV via SQL:<br/>SELECT count(distinct ...), count(*)"]
  M --> N["stats_get_ndv_by_query<br/>statistics_cl.c"]
  N --> F
  F --> O["catalog_add_representation<br/>(disk_repr_p 영구화)"]
  F --> P["catalog_add_class_info<br/>(time_stamp, tot_∗ 영구화)"]
  F --> Q["catcls_update_class_stats<br/>(_db_class 행 기록)"]

매 UPDATE STATISTICS 마다 두 개의 별개 워크가 돈다.

NDV 워크는 서버 RPC 보다 먼저 클라이언트에서 돈다. stats_get_ndv_by_query (statistics_cl.c) 가 SELECT count(distinct c1), count(distinct c2), …, count(*) FROM [classname] 을 만들어 서버에 일반 query 로 보낸다. WITH FULLSCAN 이 명시 되지 않은 한 SAMPLING_SCAN 힌트가 붙는다. precision 이 STATS_MAX_PRECISION = 4000 을 넘는 char/varchar 컬럼과 모든 LOB, JSON 컬럼은 sentinel 인 cast(-1 as BIGINT) 를 받아 distinct 카운팅에서 빠진다. 수천 자짜리 컬럼의 비교 비용이 무한정 이기 때문이다. 결과 튜플이 xstats_update_statistics 로 들어가는 CLASS_ATTR_NDV 배열이 된다.

B+Tree 워크는 서버에서 xstats_update_statistics 안에서 돈다. 인덱스 attribute 마다 btree_get_stats 가 페이지 수에 따라 full scan 과 acceptance-rejection 표본 추출 사이에서 결정한다.

// btree_get_stats — src/storage/btree.c
if (with_fullscan || npages <= STATS_SAMPLING_THRESHOLD)
  {
    /* do fullscan at small table */
    ret = btree_get_stats_with_fullscan (thread_p, env);
  }
else
  {
    ret = btree_get_stats_with_AR_sampling (thread_p, env);
  }

STATS_SAMPLING_THRESHOLD 는 5000 페이지다 — 그 아래에서는 full scan 이 표본보다 싸다. 그 위에서는 AR sampler 가 distinct leaf 5000 개를 (STATS_SAMPLING_LEAFS_MAX) 방문하거나 5000 회의 시도가 지나거나 (STATS_SAMPLING_THRESHOLD) 까지 무작위 leaf 를 고른다.

// btree_get_stats_with_AR_sampling — src/storage/btree.c
for (n = 0; n < STATS_SAMPLING_THRESHOLD; n++)
  {
    if (env->stat_info->leafs >= STATS_SAMPLING_LEAFS_MAX)
      break;
    BTS->C_page = btree_find_AR_sampling_leaf (thread_p, ...);
    /* ... walk every key on this leaf, increment keys, pkeys[] ... */
  }
/* apply distributed expansion */
exp_ratio = (double) env->stat_info->pages / (double) env->stat_info->leafs;
env->stat_info->leafs *= exp_ratio;
env->stat_info->keys  *= exp_ratio;
for (i = 0; i < env->pkeys_val_num; i++)
  env->stat_info->pkeys[i] *= exp_ratio;

표본 추출기는 B+Tree 의 페이지 분포가 대체로 균등하다는 Lehman 스타일의 가정에 기댄다 — skew 가 있으면 expansion 이 과대 또는 과소 하게 되어 옵티마이저가 편향된 추정을 받는다. 일반 OLTP 워크로드에서 는 selectivity 모델의 자릿수 단위 분해도가 그 편향을 흡수한다.

full-scan 경로는 단순하다 — 가장 왼쪽 leaf 로 내려간 뒤 (btree_find_lower_bound_leaf) leaf 레벨 next-key 순회 (btree_find_next_index_record) 를 돌면서 매 키마다 MVCC 가시성 필터를 적용한다.

// btree_get_stats_with_fullscan — src/storage/btree.c
mvcc_snapshot = logtb_get_mvcc_snapshot (thread_p);
ret = btree_find_lower_bound_leaf (thread_p, BTS, env->stat_info);
while (!BTREE_END_OF_SCAN (BTS))
  {
    if (!VPID_EQ (&(BTS->C_vpid), &C_vpid))
      env->stat_info->leafs++;
    ret = btree_get_stats_key (thread_p, env, mvcc_snapshot);
    ret = btree_find_next_index_record (thread_p, BTS);
  }

btree_get_stats_key 호출 한 번이 keys 를 1 증가시키고 다중 컬럼 키를 btree_get_stats_midxkey 로 풀어 넣어 각 pkeys[i] — 인덱스 의 처음 i+1 컬럼의 distinct count — 를 갱신한다. MVCC 필터 (btree_get_num_visible_from_leaf_and_ovf) 는 다른 트랜잭션이 지웠지만 보였던 OID 만 가지고 있던 키가 카운트되지 않게 한다 — reader 가 보는 행 수와 일치한다.

전체 행 수 cls_info_p->ci_tot_objects 는 heap 워크에서 도출되는 것이 아니다 — NDV query 의 count(*) 에서 그대로 가져온다.

// xstats_update_statistics — src/storage/statistics_sr.c
/* use value from "select --+ sampling count(*) ..." */
cls_info_p->ci_tot_objects =
  class_attr_ndv->attr_ndv[class_attr_ndv->attr_cnt].ndv;

인덱스 attr_cnt 자리의 슬롯이 stats_make_select_list_for_ndv 가 끝에 붙여 둔 count(*) 이다. 페이지 수 ci_tot_pages 는 파일 매니저 (file_get_num_user_pages) 에서 온다 — heap 페이지 수는 순수 물리적 측정이며, MVCC 가시성과 무관하다.

카탈로그에 저장하기

통계는 두 평행한 자리에 산다. 카탈로그 매니저의 분리 설계 (참조 cubrid-catalog-manager.md §“Disk representation vs. 논리 스키마”) 를 그대로 거울처럼 따른다.

내부 카탈로그는 정전, untyped representation 을 저장한다 — xstats_update_statistics 가 catalog_add_representation 을 호출해 disk_repr_p (attribute 별, 인덱스별 숫자) 를 영구화하고, catalog_add_class_info 를 호출해 cls_info_p (time_stamp, tot_objects, tot_pages, heap 파일 id) 를 영구화한다. 이 레코 드들은 카탈로그 매니저의 CTID 키 overflow 파일에 저장되며, 서버 가 SQL 파싱 없이 다시 읽을 수 있다.

사용자 가시 시스템 클래스 _db_class 는 같은 필드의 거울본을 들고 다닌다. 그래서 SELECT … FROM _db_class 가 최신 통계를 본다. catcls_update_class_stats 는 클래스 이름으로 _db_class 행을 찾고, heap 매니저로 그 행을 읽고, catcls_update_or_value_class_stats_fields 로 통계 필드를 mutate 한 뒤, 표준 heap 갱신 경로 (인덱스 유지보수는 locator_update_index 로) 로 다시 쓴다.

서버에서 클라이언트로 통계를 실어 보내는 와이어 포맷은 목적에 맞춘 것이다 — 구조체를 memcpy 한 것이 아니라 (구조체 안에는 호스트 의존적 레이아웃을 가진 포인터와 64-bit 값이 들어 있다) OR 로 packed 된 버퍼이며, xstats_get_statistics_from_server 가 조립한다.

// xstats_get_statistics_from_server — src/storage/statistics_sr.c
size = (OR_INT_SIZE   /* time_stamp of CLS_INFO */
        + OR_INT_SIZE /* tot_objects of CLS_INFO */
        + OR_INT_SIZE /* tot_pages of CLS_INFO */
        + OR_INT_SIZE /* n_attrs from DISK_REPR */
        + (OR_INT_SIZE   /* id of DISK_ATTR */
           + OR_INT_SIZE /* type of DISK_ATTR */
           + OR_INT_SIZE /* n_btstats of DISK_ATTR */
           + OR_INT64_SIZE /* Number of Distinct Values */
        ) * n_attrs);

size += ((OR_BTID_ALIGNED_SIZE  /* btid of BTREE_STATS */
          + OR_INT_SIZE /* leafs */ + OR_INT_SIZE /* pages */
          + OR_INT_SIZE /* height */ + OR_INT_SIZE /* keys */
          + OR_INT_SIZE /* dedup_idx */
          + OR_INT_SIZE /* has_function */
         ) * tot_n_btstats);
size += tot_key_info_size;  /* key_type, pkeys[] */

와이어 레벨에서 짚어 둘 것이 셋 있다. NDV 는 OR_INT64_SIZE 로 보낸다 (카탈로그 필드가 INT64 다). 그러나 모든 B+Tree 통계는 OR_INT_SIZE (signed 32-bit) 다. 10억 행짜리 테이블에서는 인덱스 별 keys 필드가 포화될 수 있다. 표본 expansion 코드는 if (… < 0) … = INT_MAX overflow 가드로 방어하지만, 진짜 full-scan 이 2^31 키 를 넘어 가면 조용히 truncate 된다. 클래스 단위 ci_tot_objects 도 와이어 위에서는 32-bit 다 — 그 출처가 64-bit NDV count(*) 값임에 도 그렇다.

클라이언트 측 (statistics_cl.c 의 stats_client_unpack_statistics) 은 packing 을 워크스페이스 할당기 (db_ws_alloc) 에서 잡은 인메모리 CLASS_STATS 로 역으로 풀고, key 단위 카운트를 정상 범위로 죈다.

// stats_client_unpack_statistics — src/storage/statistics_cl.c
/* validate key stats info */
for (...)
  {
    btree_stats_p->keys =
      MIN (btree_stats_p->keys, class_stats_p->heap_num_objects);
    for (k = 0; k < btree_stats_p->pkeys_size; k++)
      btree_stats_p->pkeys[k] =
        MIN (btree_stats_p->pkeys[k], btree_stats_p->keys);
  }

MIN 클램프가 중요한 이유는 B+Tree 의 keys 카운트가 일시적으로 클래스의 heap_num_objects 를 넘어 갈 수 있기 때문이다 — heap NDV query 가 놓친 미커밋 insert 를 B+Tree 가 봤거나, 두 패스 사이의 MVCC 가시성 차이 때문이다. 옵티마이저가 keys > heap_num_objects 를 그대로 보면 카디널리티 산수가 깨지므로 클라이언트가 방어적으로 trim 한다.

옵티마이저의 소비 경로

옵티마이저는 카탈로그를 직접 읽지 않는다. plan 시점에 qo_get_attr_info (query_graph.c) 가 각 QO_SEGMENT (query graph 위의 컬럼 참조) 를 호출되며, 워크스페이스 SM_CLASS 에 매달려 있는 캐시된 CLASS_STATS 에서 ATTR_STATS 를 꺼낸다.

// qo_get_attr_info — src/optimizer/query_graph.c
stats = QO_GET_CLASS_STATS (class_info_entryp);
QO_ASSERT (env, stats != NULL);
/* search the attribute from the class information */
attr_statsp = stats->attr_stats;
n_attrs = stats->n_attrs;
for (j = 0; j < n_attrs; j++, attr_statsp++)
  {
    if (attr_statsp->id == attr_id)
      break;
  }

세그먼트가 B+Tree 통계가 있으면 (즉 컬럼이 인덱스가 있으면), 인덱스별 BTREE_STATS 레코드들을 세그먼트 위 단일 QO_ATTR_CUM_STATS 요약으로 접는다. 접는 규칙은 최대 height 와 최대 keys 카운트의 인덱스를 유지한다 — “가장 좋은 카디널 리티 인덱스” 휴리스틱이다.

// qo_get_attr_info — src/optimizer/query_graph.c (loop body)
cum_statsp->leafs += bstatsp->leafs;
cum_statsp->pages += bstatsp->pages;
cum_statsp->height = MAX (cum_statsp->height, bstatsp->height);

if (cum_statsp->pkeys_size == 0
    || cum_statsp->keys < bstatsp->keys)
  {
    cum_statsp->keys = bstatsp->keys;
    cum_statsp->key_type = bstatsp->key_type;
    cum_statsp->pkeys_size = bstatsp->pkeys_size;
    /* … reallocate pkeys array … */
    for (i = 0; i < cum_statsp->pkeys_size; i++)
      cum_statsp->pkeys[i] = bstatsp->pkeys[i];
  }

aggregate 는 QO_SEG_INFO(seg) 에 캐시되며 비용 함수와 selectivity 추정기 양쪽이 읽는다.

비용 함수

qo_iscan_cost 와 qo_sscan_cost 는 네 튜플 (fixed_cpu_cost, fixed_io_cost, variable_cpu_cost, variable_io_cost) 을 계산하며, 이것이 qo_plan_compute_cost 의 plan 정렬을 구동한다.

// qo_iscan_cost — src/optimizer/query_planner.c
sel = 1.0;
for (... iterate index terms ...)
  sel *= QO_TERM_SELECTIVITY (termp);
sel = MIN (sel, 1.0);

/* selectivity floor */
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;
else if (QO_NODE_NCARD (nodep) >= 1)
  sel_limit = 1.0 / (double) QO_NODE_NCARD (nodep);
sel = MAX (sel, sel_limit);

leaf_access = sel * (double) QO_NODE_NCARD (nodep);
height      = (double) cum_statsp->height - 1;
leaves      = ceil (sel * (double) cum_statsp->leafs);
opages      = (double) QO_NODE_TCARD (nodep);
index_IO    = (n * height) + leaves;

planp->fixed_io_cost     = index_IO;
planp->variable_cpu_cost = (leaf_access + heap_access) * QO_CPU_WEIGHT;
planp->variable_io_cost  = object_IO;

B+Tree 통계는 비용 컴포넌트에 일대일로 매핑된다. height 는 스캔당 한 번 부과되는 random-access 깊이, leafs 는 매칭되는 키마다 부과되는 leaf 페이지 I/O 다. pkeys[] 는 selectivity floor 를 제공한다. 1/pkeys[i] 는 prefix i+1 컬럼이 매칭된 predicate 를 옵티마이저가 믿어 줄 가장 작은 카디널리티이며, 따라서 인덱스가 풀 수 없는 predicate 에서도 비용이 0 으로 무너지지 않는다.

selectivity floor 가 partial-key NDV 의 구조 하중이다. 이게 없으면 qo_*_selectivity 곱 사슬 (각각 최대 1.0, 흔히 DEFAULT_*_SELECTIVITY = 0.001 에서 0.1) 이 다중 AND predicate 에서 행 수를 과소 추정 하고 옵티마이저는 비용은 낮고 카디널리티도 낮은 plan 을 과도하게 선호하게 된다.

qo_sscan_cost 는 비교하면 사소하다 — sequential scan 비용은 QO_NODE_NCARD * QO_CPU_WEIGHT CPU 와 QO_NODE_TCARD I/O 다. 여기서 NCARD 는 heap_num_objects, TCARD 는 heap_num_pages 다.

// qo_sscan_cost — src/optimizer/query_planner.c
planp->variable_cpu_cost = (double) QO_NODE_NCARD (nodep) * QO_CPU_WEIGHT;
planp->variable_io_cost  = (double) QO_NODE_TCARD (nodep);

Selectivity 추정기

qo_expr_selectivity 가 디스패처다 — predicate 트리를 워크하면서 AND/OR/NOT 에서 재귀하고 적절한 leaf 추정기를 부른다.

// qo_expr_selectivity — src/optimizer/query_planner.c
case PT_OR:    selectivity = qo_or_selectivity   (env, lhs, rhs);  break;
case PT_AND:   selectivity = qo_and_selectivity  (env, lhs, rhs);  break;
case PT_EQ:
case PT_NULLSAFE_EQ:
                selectivity = qo_equal_selectivity (env, node);    break;
case PT_GE: case PT_GT: case PT_LT: case PT_LE:
                selectivity = qo_comp_selectivity  (env, node);    break;
case PT_BETWEEN:
                selectivity = qo_between_selectivity (env, node);  break;
case PT_RANGE:  selectivity = qo_range_selectivity (env, node);    break;
case PT_LIKE:   selectivity = prm_get_float_value (PRM_ID_LIKE_TERM_SELECTIVITY); break;
case PT_IS_NULL: selectivity = DEFAULT_NULL_SELECTIVITY; break;
case PT_IS_IN:   selectivity = qo_all_some_in_selectivity (env, node); break;

qo_and_selectivity 와 qo_or_selectivity 는 순수 독립성 가정 산수 (p*q 와 p+q-p*q) 다 — Selinger §3.2 의 직접 인용.

qo_equal_selectivity 는 통계를 실제로 쓰는 유일한 추정기이며, 컬럼 NDV 를 직접 쓰지 않고 인덱스 카디널리티 형태로 쓴다.

// qo_equal_selectivity — src/optimizer/query_planner.c
case PC_ATTR:
  /* attr = const */
  lhs_icard = qo_index_cardinality (env, lhs);
  if (lhs_icard != 0)
    selectivity = (1.0 / lhs_icard);
  else
    selectivity = DEFAULT_EQUAL_SELECTIVITY;

qo_index_cardinality 는 컬럼별 NDV (attr_stats::ndv) 와 인덱스 별 partial-key distinct count (pkeys[0]) 를 섞는다.

// qo_index_cardinality — src/optimizer/query_planner.c
if (info->ndv > 0)
  {
    int ndv = (info->ndv > INT_MAX) ? INT_MAX : info->ndv;
    if (info->cum_stats.is_indexed == true
        && info->cum_stats.pkeys[0] > 0)
      return MIN (ndv, info->cum_stats.pkeys[0]);
    return ndv;
  }
if (info->cum_stats.is_indexed != true)
  return 0;
/* return number of the first partial-key */
return info->cum_stats.pkeys[0];

두 출처 사이의 MIN 은 NDV query 와 B+Tree 워크가 어긋나는 경우의 안전망이다. 예를 들어 컬럼이 인덱스를 가졌는데 SQL count(distinct) 가 표본으로 돌아 과소 추정했거나, B+Tree 가 heap NDV 가 놓친, vacuum 되지 않은 삭제된 키를 포함한 경우다. MIN 을 고르면 더 작은 distinct count 쪽으로, 즉 등치 predicate 당 더 큰 추정 행 수 쪽으로 편향된다. 이는 옵티마이저 실수 중에서 더 보수적인 방향이다 (과대 추정은 사이클을 낭비하지만 과소 추정 은 나쁜 plan 을 고른다).

비등치 추정기들은 상수다. qo_comp_selectivity, qo_between_selectivity, qo_range_selectivity 는 predicate 의 실제 범위 경계를 무시하고 고정 DEFAULT_*_SELECTIVITY 매크로를 반환한다.

// query_planner.c — selectivity defaults
#define DEFAULT_NULL_SELECTIVITY     (double) 0.01
#define DEFAULT_EXISTS_SELECTIVITY   (double) 0.1
#define DEFAULT_SELECTIVITY          (double) 0.1
#define DEFAULT_EQUAL_SELECTIVITY    (double) 0.001
#define DEFAULT_EQUIJOIN_SELECTIVITY (double) 0.001
#define DEFAULT_COMP_SELECTIVITY     (double) 0.1
#define DEFAULT_BETWEEN_SELECTIVITY  (double) 0.01
#define DEFAULT_IN_SELECTIVITY       (double) 0.01
#define DEFAULT_RANGE_SELECTIVITY    (double) 0.1

qo_comp_selectivity 는 한 줄이다 (return DEFAULT_COMP_SELECTIVITY) 이고, qo_between_selectivity 도 비슷하다. 구조적 이유는 디스크 위에 min/max 또는 히스토그램 경계가 없기 때문이다. predicate 상수와 비교할 대상이 없는 것이다. 그래서 추정기는 </>/<=/>= 를 하드코딩된 10% 추측으로, BETWEEN 을 1% 로 회귀한다. 이 단순화의 비용은 범위가 많은 워크로드의 plan 품질에서 치러진다.

데이터 기반 추정을 받는 유일한 범위형 predicate 는 IN/= SOME (qo_all_some_in_selectivity) 이다 — 등치 selectivity 에 IN-list 카디널리티를 곱한다. IN-list 카디널리티는 값 리스트의 literal 길이 이거나, RHS 가 subquery 인 경우에는 ((XASL_NODE *) arg2->info.query.xasl)->cardinality 다 — 그 자체는 subquery 의 자기 통계로부터 더 이른 옵티마이저 패스에서 채워진다. 결과는 폭주를 막기 위해 0.5 에서 cap 된다.

표본 추출용 NDV 보정

헤더 파일은 표본의 distinct count 가 매우 낮을 때 NDV 를 위로 보정 하는 helper 를 출하한다.

// stats_adjust_sampling_weight — src/storage/statistics.h
STATIC_INLINE int
stats_adjust_sampling_weight (INT64 sampling_ndv, int sampling_weight)
{
  /* Differential weight is applied to NDV within 1% of all rows of sample data. */
  if (sampling_weight <= 1)
    return sampling_weight;
  int min_NDV = NUMBER_OF_SAMPLING_PAGES * EXPECTED_ROWS_PER_PAGE / 100;
  if (sampling_ndv < min_NDV)
    return MAX (sampling_weight * sampling_ndv / min_NDV, 1);
  return sampling_weight;
}

상수 NUMBER_OF_SAMPLING_PAGES = 5000 과 EXPECTED_ROWS_PER_PAGE = 20 으로부터 1% 표본 임계값은 5000 * 20 / 100 = 1000 distinct 값이다 — 그 아래에서는 표본의 NDV 가 컬럼에 중복이 많다는 강한 신호로 취급되며, up-scaling weight 이 표본-모집단 외삽이 과도해 지지 않도록 비례해 줄어든다. 모집단 수준의 공식은 다음과 같다.

weight' = weight * (sampling_ndv / 1000)   if sampling_ndv < 1000

floor 는 1 이다. Haas-Stokes 의 coverage 추정기도, Charikar 풍의 worst-case bound 도 없다 — CUBRID 은 NDV 가 건강하면 표본을 믿고, 그렇지 않을 때만 외삽을 누른다.

같은 가족의 두 번째 공식은 qo_estimate_ndv 이며, group-by 카디널 리티에 쓴다.

// qo_estimate_ndv — src/optimizer/query_planner.c
/* formula: n * (1 - ((N - p) / N)^(N / n))
 *   N: total_nrows
 *   p: expected_nrows
 *   n: NDV of group columns
 */
double qo_estimate_ndv (double N, double p, double n)
{
  if (N <= 0.0 || n <= 0.0)
    return 0.0;
  double ratio = (N - p) / N;
  double exponent = N / n;
  return n * (1.0 - pow (ratio, exponent));
}

이는 고전적 balls-in-bins distinct-count 공식이다 (Yao 1977; Cardenas 1975) — N 개 항목이 n 개 distinct 그룹에 균등 분포하고 p 개 항목을 관찰한 뒤, 비어 있지 않은 그룹의 기대 수가 n * (1 - ((N-p)/N)^(N/n)) 이다. GROUP BY plan 의 QO_PLAN::info::ngroups 를 설정하는 qo_estimate_ngroups 를 구동한다. 그러나 그 자체가 BTREE_STATS::pkeys 로 되돌아 가는 일은 없다 — 호출자가 넘겨 주는 NDV 를 그대로 소비할 뿐이다.

DDL 트리거

UPDATE STATISTICS 는 pt_update_stats_info 라는 info union 을 들고 있는 PT_NODE 로 파싱된다.

// pt_update_stats_info — src/parser/parse_tree.h
struct pt_update_stats_info
{
  PT_NODE *class_list;   /* PT_NAME */
  int all_classes;       /* 1 iff ALL CLASSES, -1 iff ON CATALOG CLASSES */
  int with_fullscan;     /* 1 iff WITH FULLSCAN */
};

semantic checker pt_check_update_stats 가 권한을 검증하고 (각 클래스에 ALTER 권한이 필요하다) ALL CLASSES 를 실제 클래스 집합으로 펼친다. executor 는 execute_statement.c 에 산다.

// do_update_stats — src/query/execute_statement.c
for (cls = statement->info.update_stats.class_list;
     cls != NULL && error == NO_ERROR;
     cls = cls->next)
  {
    class_mop = cls->info.name.db_object;
    class_type = ((SM_CLASS *) class_mop->object)->class_type;
    if (class_type == SM_CLASS_CT)
      error = sm_update_statistics (class_mop, statement->info.update_stats.with_fullscan);
  }

sm_update_statistics (schema_manager.c) 는 클래스에 대한 더러운 워크스페이스 상태를 flush 하고 stats_update_statistics 를 호출 한다 — 그것이 결국 서버 측 xstats_update_statistics 에 도달한다. 서버가 성공으로 돌아오면 sm_update_statistics 가 캐시된 class_->stats 를 무효화하고, 그 다음 sm_get_class_with_statistics 호출에서 묵시적으로 다시 fetch 된다.

// sm_update_statistics — src/object/schema_manager.c
error = stats_update_statistics (classop, with_fullscan);
if (error == NO_ERROR)
  {
    if (classop->object != NULL)
      {
        error = au_fetch_class_force (classop, &class_, AU_FETCH_READ);
        if (error == NO_ERROR)
          {
            if (class_->stats != NULL)
              {
                stats_free_statistics (class_->stats);
                class_->stats = NULL;
              }
            /* … flush class so subsequent fetch picks up new stats … */
          }
      }
  }

평행한 자동 트리거 경로도 있다 — 벌크 로더 (load_sa_loader.cpp), CREATE INDEX 와 ALTER TABLE (execute_schema.c), 그리고 standalone-mode 부트 (util_sa.c) 가 모두 STATS_WITH_SAMPLING 으 로 sm_update_statistics 를 호출해 큰 행-모양 변경 후 통계를 새로 고친다. 시간 기반 또는 임계 기반 자동 트리거는 없고, 순전히 스키마 / 데이터 DDL 이벤트에 의해 구동된다.

히스토그램 bucket 레이아웃 (또는 그 부재)

CUBRID 의 “equi-depth 히스토그램” 등가물은 partial-key distinct-count 벡터 pkeys[] 다. 다중 컬럼 인덱스 (a, b, c) 를 다음을 들고 다닌다.

graph LR
  subgraph BTREE_STATS_pkeys["BTREE_STATS::pkeys[] for index(a,b,c)"]
    P0["pkeys[0] = NDV of {a}<br/>예: 100"]
    P1["pkeys[1] = NDV of {a,b}<br/>예: 1000"]
    P2["pkeys[2] = NDV of {a,b,c}<br/>예: 100000<br/>== keys"]
    P0 --> P1 --> P2
  end
  subgraph cost["qo_iscan_cost 가 사용"]
    SF["sel_limit = 1.0 / pkeys[i]<br/>i = 등치 바인딩된 leading 세그먼트의 수"]
  end
  P0 -.->|i=0, predicate on a| SF
  P1 -.->|i=1, predicate on a AND b| SF
  P2 -.->|i=2, predicate on a AND b AND c| SF

이는 히스토그램이 아니다 — 값 축의 양자화도, bucket 별 frequency 도, 상/하한도 없다. pkeys[i] 라는 단일 숫자가 답하는 질문은 정확히 하나다 — “이 인덱스의 처음 i+1 컬럼이 등치로 바인딩되었을 때, 남는 distinct 키는 몇 개인가?” 이는 등치 selectivity 의 하한 (1/pkeys[i]) 을 묶기에 충분하지만 값 분포의 모양에 대해서는 옵티 마이저에 아무 것도 알려 주지 않는다. 최대 prefix 길이는 BTREE_STATS_PKEYS_NUM = 8 (statistics.h 에 정의) 이다. 컬럼이 8개를 넘는 인덱스는 truncate 되며, 클라이언트 unpacker 는 sanity 불변식으로 마지막 pkeys[pkeys_size-1] 을 keys 와 같게 강제한다.

소스 코드 가이드

심볼을 단계별로 묶었다. 라인 번호는 문서의 updated: 날짜로 한정된 힌트다.

DDL 표면

• pt_update_stats_info — 파서 노드
• pt_check_update_stats — semantic check, authorization
• do_update_stats — executor 진입 (in execute_statement.c, 4483 라인 부근)
• sm_update_statistics — schema-manager 디스패처
• stats_update_statistics — 클라이언트 측 네트워크 호출
• network_interface_sr.cpp (서버 핸들러 4278 라인 부근) — 서버 진입

서버 측 수집

• xstats_update_statistics — 최상위 서버 루틴
• stats_update_partitioned_statistics — 파티션 누적기
• btree_get_stats — 인덱스별 디스패처 (full vs. AR sampling)
• btree_get_stats_with_fullscan — 가장 왼쪽 leaf 하강 + leaf 워크
• btree_get_stats_with_AR_sampling — STATS_SAMPLING_THRESHOLD / STATS_SAMPLING_LEAFS_MAX 로 묶인 무작위 leaf 표본 추출기
• btree_find_AR_sampling_leaf — 무작위 leaf 선택자
• btree_get_stats_key — 키별 카운터 + MVCC 가시성 필터
• btree_get_stats_midxkey — 다중 컬럼 partial-key 갱신자
• btree_get_num_visible_from_leaf_and_ovf — leaf+overflow 의 MVCC 가시성
• stats_find_inherited_index_stats — 파티션별 인덱스 lookup
• stats_get_time_stamp — time() 래퍼
• stats_dump_class_statistics — 디버그 덤프 (DEBUG 전용)

클라이언트 측 NDV 수집

• stats_get_ndv_by_query — SELECT count(distinct …), count(*) 러너
• stats_make_select_list_for_ndv — 컬럼 리스트 빌더, LOB/JSON/대형 char 옵트아웃
• stats_ndv_dump — 디버그 덤프
• STATS_MAX_PRECISION = 4000 — char precision 컷오프
• STATS_WITH_FULLSCAN, STATS_WITH_SAMPLING — boolean 모드
• stats_adjust_sampling_weight — inline NDV up-scaling helper

카탈로그 영구화

• catalog_get_class_info, catalog_add_class_info — CLS_INFO read/write
• catalog_get_representation, catalog_add_representation — DISK_REPR read/write
• catalog_start_access_with_dir_oid — 디렉토리-OID lock
• catcls_update_class_stats — _db_class 행 mutator
• catcls_update_or_value_class_stats_fields — 필드 단위 stat 갱신자

와이어 포맷

• xstats_get_statistics_from_server — 서버 측 packer
• OR_PUT_INT, OR_PUT_INT64, OR_PUT_BTID, or_pack_domain — packing primitive
• stats_client_unpack_statistics — MIN 클램프와 함께 클라이언트 측 unpacker
• stats_get_statistics — 클라이언트 래퍼, stats_get_statistics_from_server 호출
• stats_free_statistics — 워크스페이스 할당기 deallocator

옵티마이저 소비

• qo_get_attr_info — BTREE_STATS 배열을 QO_ATTR_CUM_STATS 로 접음
• qo_get_attr_info_func_index — function-index 변종
• QO_ATTR_CUM_STATS — 접힌 누적 구조체 (in optimizer.h)
• QO_GET_CLASS_STATS — 클래스 정보 entry 에서 CLASS_STATS 로의 포인터
• qo_index_cardinality — MIN(ndv, pkeys[0]) 블렌더
• qo_index_cardinality_with_dedup — seg-bitset dedup 이 추가된 동일 함수
• qo_classify — predicate operand 분류기 (PC_ATTR / PC_CONST / …)
• qo_iscan_cost — 인덱스 스캔 비용 방정식
• qo_sscan_cost — sequential scan 비용 방정식
• qo_plan_compute_cost — plan 비용 디스패처
• qo_expr_selectivity — predicate 트리 워커
• qo_or_selectivity, qo_and_selectivity, qo_not_selectivity — 독립성 가정 산수
• qo_equal_selectivity — 데이터 기반 leaf 추정기 단 하나 (qo_index_cardinality 사용)
• qo_comp_selectivity — 상수 DEFAULT_COMP_SELECTIVITY
• qo_between_selectivity — 상수 DEFAULT_BETWEEN_SELECTIVITY
• qo_range_selectivity — PT_BETWEEN_EQ_NA 에 대해서만 인덱스 카디널리티 사용
• qo_all_some_in_selectivity — IN-list / IN-subquery selectivity
• qo_estimate_ndv — 표본 추출 하의 Yao-Cardenas balls-in-bins NDV
• qo_estimate_ngroups — group-by 카디널리티

공개 구조체 / 상수

• CLASS_STATS, ATTR_STATS, BTREE_STATS — in statistics.h
• CLASS_ATTR_NDV, ATTR_NDV — in statistics.h
• BTREE_STATS_PKEYS_NUM = 8 — partial-key fanout cap
• STATS_SAMPLING_THRESHOLD = 5000, STATS_SAMPLING_LEAFS_MAX = 5000 — 표본 추출기 경계
• NUMBER_OF_SAMPLING_PAGES = 5000, EXPECTED_ROWS_PER_PAGE = 20 — NDV 보정 상수
• DEFAULT_*_SELECTIVITY — query_planner.c 의 폴백 selectivity 표

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

심볼	파일	라인
xstats_update_statistics	src/storage/statistics_sr.c	109
stats_update_partitioned_statistics	src/storage/statistics_sr.c	1048
xstats_get_statistics_from_server	src/storage/statistics_sr.c	376
stats_find_inherited_index_stats	src/storage/statistics_sr.c	1443
stats_get_time_stamp	src/storage/statistics_sr.c	831
stats_get_statistics	src/storage/statistics_cl.c	56
stats_client_unpack_statistics	src/storage/statistics_cl.c	85
stats_free_statistics	src/storage/statistics_cl.c	252
stats_dump	src/storage/statistics_cl.c	293
stats_get_ndv_by_query	src/storage/statistics_cl.c	435
stats_make_select_list_for_ndv	src/storage/statistics_cl.c	569
BTREE_STATS	src/storage/statistics.h	60
ATTR_STATS	src/storage/statistics.h	82
CLASS_STATS	src/storage/statistics.h	93
stats_adjust_sampling_weight	src/storage/statistics.h	135
BTREE_STATS_PKEYS_NUM	src/storage/statistics.h	43
STATS_SAMPLING_THRESHOLD	src/storage/statistics.h	37
btree_get_stats	src/storage/btree.c	7397
btree_get_stats_with_fullscan	src/storage/btree.c	7264
btree_get_stats_with_AR_sampling	src/storage/btree.c	7131
btree_get_stats_key	src/storage/btree.c	6959
btree_get_stats_midxkey	src/storage/btree.c	6854
qo_iscan_cost	src/optimizer/query_planner.c	2078
qo_sscan_cost	src/optimizer/query_planner.c	1711
qo_expr_selectivity	src/optimizer/query_planner.c	9711
qo_equal_selectivity	src/optimizer/query_planner.c	9916
qo_range_selectivity	src/optimizer/query_planner.c	10207
qo_comp_selectivity	src/optimizer/query_planner.c	10174
qo_between_selectivity	src/optimizer/query_planner.c	10188
qo_all_some_in_selectivity	src/optimizer/query_planner.c	10338
qo_index_cardinality	src/optimizer/query_planner.c	10504
qo_estimate_ndv	src/optimizer/query_planner.c	684
DEFAULT_*_SELECTIVITY macros	src/optimizer/query_planner.c	427-435
qo_get_attr_info	src/optimizer/query_graph.c	5168
qo_get_attr_info_func_index	src/optimizer/query_graph.c	5003
QO_ATTR_CUM_STATS	src/optimizer/optimizer.h	119
catcls_update_class_stats	src/storage/catalog_class.c	4453
sm_update_statistics	src/object/schema_manager.c	4201
do_update_stats	src/query/execute_statement.c	~4483
pt_update_stats_info	src/parser/parse_tree.h	2977

소스 검증 노트

비용 함수가 읽는 것 vs. 실제로 채워지는 필드

qo_iscan_cost 가 읽는 것을 xstats_update_statistics 가 쓰는 것과 대조해 보면 짚어 둘 만한 세 지점이 보인다.

cum_statsp->keys 는 채워지지만 I/O 비용에 쓰이지 않는다. 이 필드는 qo_iscan_cost 에서 보조 selectivity-floor 출처로만 닿 는다 — partial-key 폴백이 실패할 때 sel_limit = 1.0 / cum_statsp->keys. 실제 leaf I/O 비용 (leaves = ceil (sel * (double) cum_statsp->leafs)) 은 keys 에 의존하지 않는다. 즉 (낡은 stats 표본 때문에) keys 카운트가 틀리지만 leafs 가 옳은 인덱스는 I/O 비용은 정확하나 selectivity floor 가 잘못될 수 있다 — 미묘하지만 실제로 흔한 skew 다.

heap_num_objects 는 옵티마이저에 두 번 도달한다. 한 번은 QO_NODE_NCARD (서버가 NDV count(*) 로 채운 CLASS_STATS::heap_num_objects) 로 도달하고, 다른 한 번은 leading unique 인덱스의 pkeys[pkeys_size-1] == keys 로 묵시적으로 도달한다. 두 값은 MVCC 가시성 skew 안에서 일치해야 하지만, stats_client_unpack_statistics 의 클라이언트 측 MIN 클램프는 아래 로만 죈다 (pkeys <= keys <= heap_num_objects). heap_num_objects 가 너무 작으면 (NDV count(*) 가 표본으로 돌았거나 두 패스 사이에 heap 이 prune 됐거 나) 인덱스 keys 는 조용히 truncate 되고 불일치가 가려진다.

dedup_idx 필드는 출하되지만 의미는 feature flag 에 달려 있다. btree_get_stats_key 의 SUPPORT_DEDUPLICATE_KEY_MODE 코드 경로와 btree_is_same_key_for_stats 필터는 인접한 키가 dedup 접미만 다를 때 키별 카운터를 다시 쓴다. 덤프 코드는 dedup_idx != 0 을 assert 하지만 모든 빌드에서 이 기능이 켜져 있지는 않다 — 꺼져 있을 때는 필드가 0 으로 출하되고 옵티마이저가 무시한다. 와이어 프로토콜에는 어느 쪽이 deduplication 을 켰는지 확인하는 명시적 핸드셰이크가 없 어서, 서버-클라이언트 불일치가 원리적으로는 편향된 pkeys[] 카운 트를 옵티마이저로 흘려 보낼 수 있다.

NDV vs. partial-key 블렌딩

qo_index_cardinality 는 둘 다 양수일 때 MIN(ndv, pkeys[0]) 을 반환한다 — 주석 (“Choose the better NDV of the two”) 이 이게 더 나은 추정이라고 단언하며, NDV 가 인덱스의 distinct-key 카운트를 넘 을 수 없다는 가정 하에서는 옳다. 그러나 MIN 이 안전한 것은 인덱 스가 추정 대상 컬럼을 포괄할 때뿐이다 — 다른 컬럼의 leading-prefix 인덱스를 가진 컬럼을 pkeys[0] 은 잘못된 차원이다. 함수는 먼 저 info->cum_stats.is_indexed == true 를 검증하지만, qo_get_attr_info 의 aggregation 규칙 (최대 keys 카운트의 인덱스를 유지) 때문에 별개 컬럼의 인덱스가 지배할 수 있다. 실무에 서는 이것이 한 테이블에 사는, 카디널리티가 높은 무관한 인덱스가 공존하는 컬럼을 낙관적 등치 selectivity 로 나타난다.

범위 selectivity 는 카디널리티 기반이 아니다

qo_comp_selectivity 와 qo_between_selectivity 는 글자 그대로 한 줄짜리이며 상수를 반환한다. BTREE_STATS::keys 나 attr_stats::ndv 에서 결과로 가는 경로가 없다. 디스크 위에 min/max 레코드가 없다는 사실과 일관된다 — 엔진에는 predicate 상수와 비교 할 대상이 없다 — 그러나 결과적으로 비용 모델은 WHERE c >= 5 와 WHERE c >= 5000000 을 같은 selectivity 로 본다. 큰 분석 범위에서 는 이것이 체계적으로 잘못 비용된 plan 을 낳는다. 사용자 가시 완화 는 /*+ INDEX(t, idx) */ 힌트이며, 비용 비교를 short-circuit 한다.

파티션 클래스 통계는 산술 평균이지 확률적 블렌드가 아니다

stats_update_partitioned_statistics 는 각 파티션의 leafs, pages, keys, pkeys[] 를 PARTITION_STATS_ACUMULATOR 에 누적 한 뒤 부모 클래스의 btree_stats_p->leafs = sum[btree_iter].leafs 를 합으로 둔다 (평균이 아니라 합이다). 단 height 만 파티션별 평균 을 ceil 한다. 헤더 주석이 근거를 설명하지만 (“only one partition is pruned”), 그 결과는 partition pruning 없이 파티션 클래스를 SELECT 하면 어느 단일 파티션의 실제 leaf 페이지 수보다 훨씬 큰 부풀려진 keys 와 leafs 카운트를 본다는 것이다. plan 시점에 partition pruning 이 보이지 않을 때 옵티마이저가 파티션 클래스에 대한 sequential scan 쪽으로 편향되게 만든다.

미해결 질문

• 자동 갱신 여부. 통계는 명시적인 UPDATE STATISTICS (또는 DDL 경로의 sm_update_statistics 호출자) 로만 갱신된다. 자동 갱신 을 발동할 임계나 트리거가 있어야 하는가, 그리고 누가 staleness 를 측정해야 하는가? 카탈로그 stamp ci_time_stamp 는 xstats_get_statistics_from_server 가 검사하지만, 그것은 중복 fetch 를 short-circuit 하는 용도일 뿐 수집을 트리거하지 않는다.
• UPDATE STATISTICS 동안의 동시성. xstats_update_statistics 는 SCH_S_LOCK 을 잡고 디렉토리 OID 위 X_LOCK 으로 카탈로그 를 쓴다. 갱신 도중의 read 는 대기하거나 (xstats_get_statistics_from_server 가 무조건 SCH_S_LOCK 을 잡는다) 갱신 전 representation 을 본다. stats_free_statistics 와 다음 sm_get_class_with_statistics 사이에서 동시 query 가 워크스페이스 캐시를 잡는 창이 있는가? sm_update_statistics 의 fix-up 은 다시 fetch 전에 클래스 상태를 flush 하지만, 워크 스페이스 class_->stats = NULL 대입은 레이스해 보인다.
• 와이어 위 64-bit 행 수. attr_stats::ndv 에는 OR_PUT_INT64 를 쓰지만 cls_info_p->ci_tot_objects 와 모든 BTREE_STATS 필드는 OR_PUT_INT 를 쓴다. 이게 누락 (ci_tot_objects 의 출처가 64-bit count(*) 값임) 인가, 아니면 ~20 억 행 한도가 의도된 것인가?
• 미래 확장으로서의 히스토그램. 구조체는 자리를 예약해 두었고 (BTREE_STATS_RESERVED_NUM = 4), DEFAULT_*_SELECTIVITY 상수는 자연스러운 displacement 후보다. 컬럼별 equi-depth 히스토그램이나 MCV 리스트 출시 로드맵이 있는가?
• 표본 추출과 MVCC. AR 표본 추출기와 SQL count(distinct) query 는 각자의 MVCC 스냅샷에서 돈다. 같은 스냅샷일 필요는 없다. 행을 동시 insert 하는 장기 트랜잭션은 unique 인덱스에서 BTREE_STATS::keys < ATTR_STATS::ndv 를 만들 수 있다. 클라이언트의 MIN 클램프가 그것을 가리지만 원인을 귀속시키지 는 않는다. 두 패스가 스냅샷을 공유해야 하는가?
• Function-index NDV. qo_get_attr_info_func_index 는 function-index 식에 대한 합성 QO_ATTR_INFO 를 만들지만 그 밑의 B+Tree 통계는 source 컬럼이 아니라 함수의 평가값을 모은다. 옵티마이저의 qo_index_cardinality 는 컬럼 단위 양인 attr_stats::ndv 를 사용해 NDV 를 블렌딩하지만 function 인덱스 에는 합성 컬럼에 대한 대응 attr_stats::ndv 가 없다. function-index 경로가 조용히 pkeys[0] 만 쓰고 있는 것인가?

출처

이 문서를 쓰면서 읽은 코드 경로 (updated: 에 대응하는 소스 리비전 의 라인):

• src/storage/statistics.h (153 라인)
• src/storage/statistics_sr.h (45 라인)
• src/storage/statistics_sr.c (1496 라인)
• src/storage/statistics_cl.c (651 라인)
• src/storage/btree.c (6847-7560 라인 부근 — 통계 수집)
• src/optimizer/query_planner.c (427-435 라인 selectivity 기본값; 670-695 qo_estimate_ndv; 1700-1730 qo_sscan_cost; 2073-2272 qo_iscan_cost; 9700-10650 selectivity 패밀리)
• src/optimizer/query_graph.c (5003-5160 라인 qo_get_attr_info_func_index; 5161-5300 qo_get_attr_info)
• src/optimizer/optimizer.h (95-132 라인 QO_ATTR_CUM_STATS)
• src/storage/catalog_class.c (4453-4559 라인 catcls_update_class_stats)
• src/object/schema_manager.c (4189-4250 라인 sm_update_statistics)
• src/query/execute_statement.c (4483 라인 부근 do_update_stats)
• src/parser/parse_tree.h (2977 라인 pt_update_stats_info; 1233 라인 PT_HINT_SAMPLING_SCAN)
• src/parser/semantic_check.c (10419 라인 pt_check_update_stats)
• src/communication/network_interface_sr.cpp (4278 라인 서버 핸들러)
• src/communication/network_interface_cl.c (5772 라인 stats_update_statistics 클라이언트 래퍼)

교재 참고 문헌:

• Selinger, P. G. et al. Access Path Selection in a Relational Database Management System. SIGMOD 1979. §3.2 selectivity 추정, §3.3 비용 방정식 분해.
• Hellerstein, J. M.; Stonebraker, M.; Hamilton, J. Architecture of a Database System. Foundations and Trends in Databases, 2007. §6.3 plan space, §6.4 selectivity 추정.
• Petrov, A. Database Internals. O’Reilly, 2019. “Query Processing and Optimization” 장.
• Poosala, V.; Ioannidis, Y. E.; Haas, P. J.; Shekita, E. Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD 1996. CUBRID 이 구현하지 않는 equi-depth + MCV 히스토그램 프레임 워크.
• Charikar, M.; Chaudhuri, S.; Motwani, R.; Narasayya, V. Towards Estimation Error Guarantees for Distinct Values. PODS 2000. 표본 기반 NDV 의 하한.
• Haas, P. J.; Stokes, L. Estimating the Number of Classes via Sample Coverage. Journal of the American Statistical Association, 1998. 표본 NDV 보정의 토대.
• Yao, S. B. Approximating Block Accesses in Database Organizations. CACM 20(4), 1977. qo_estimate_ndv 의 balls-in-bins 공식의 출발.
• Cardenas, A. F. Analysis and Performance of Inverted Database Structures. CACM 18(5), 1975. Yao 와 짝을 이루며 같은 공식에 참조됨.

이 지식 베이스 안의 cross-reference:

• cubrid-query-optimizer.md — plan space, QO_ENV / QO_NODE / QO_PLAN 데이터 흐름. 동적 프로그래밍 join 열거기 안에서 qo_iscan_cost 가 들어가는 자리.
• cubrid-catalog-manager.md — CLS_INFO, DISK_REPR, _db_class, catalog_get_representation, catalog_add_class_info.
• cubrid-btree.md — leaf 페이지 레이아웃, latch-coupling 규율, BTID, btree_get_stats_with_fullscan 이 재사용하는 하강 경로.