(KO) CUBRID 런타임 메모이제이션 — Subquery Cache, Filter-Predicate Cache, 그리고 XASL별 Memoize 헬퍼

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

학술적 배경

쿼리 plan 은 데이터베이스가 군더더기 작업을 줄일 수 있는 가장 작은 단위가 아니다. XASL cache(cubrid-xasl-cache.md)는 컴파일 파이프라인 자체를 메모이즈해 PREPARE 된 문장을 두 번째로 EXECUTE 할 때 parse, semantic-check, optimize, code-gen 을 건너뛰게 한다. 그러나 그 캐시는 plan 경계 에서 멈춘다. 같은 plan을 매번 실행할 때 마다 동일 한 scan 연산자를 다시 걷고, 같은 술어를 한 행씩 평가하며, 외부 튜플 한 건마다 같은 비상관 서브쿼리를 재실행한다. 런타임 안에서 누군가 그 작업을 가로채 결과를 기억해 두지 않는 한.

그 누군가 가 바로 런타임 메모이제이션 이다. Michie 의 1968년 Memo functions and machine learning 에서 출발한 패턴이 그대로 적용된다. f(args) → result 를 다시 써, 첫 호출은 결과를 계산해 인자 키 해시에 보관하고, 그 다음부터는 저장된 결과를 돌려준다. 쿼리 엔진의 순수 함수 들은 사실 순수하지 않다. 페이지를 읽고, 래치를 잡는다. 하지만 상태가 안정적인 한 멱등하다. 트랜잭션이 필요한 락을 보유하고 동시 DDL이 끼어들지 않는 한 같은 인자로 두 번 부르면 같은 결과가 나온다. 런타임 캐시가 안전한 것은 이 멱등성 덕분이다.

행 단위 hot path 안에서 메모이즈할 수 있는 자리는 셋이다.

비상관 스칼라 서브쿼리. WHERE salary > (SELECT AVG(salary) FROM emp) 같은 문장의 안쪽 블록은 바깥 컬럼과 무관하다. 단순한 실행기는 외부 행 한 건 마다 이를 호출하지만, 똑똑한 실행기는 한 번만 호출하고 결과 스칼라를 캐시한다. 키는 바인드 값들이다. 상관 서브쿼리도 상관 컬럼 distinct 값이 적으면 같은 최적화로 일반화 된다. N 번의 안쪽 실행이 K 번(서로 다른 상관 튜플 수)으로 줄어 든다.

컴파일된 필터 술어. 함수 기반 인덱스나 부분 인덱스는 술어를 B-tree 안에 직렬화된 XASL 바이트 스트림 형태로 들고 있다. 모든 인덱스 연산 — INSERT, UPDATE, DELETE, range scan — 이 이를 실행 가능한 PRED_EXPR_WITH_CONTEXT 트리로 만들어 써야 한다. BTID 별로 역직렬화된 트리를 캐시해 두면 쿼리들 사이에 비용이 분산되고, 미리 컴파일 된 정규식(RLIKE)도 함께 재활용된다.

Nested-loop join 안쪽 튜플. A NLJ B ON A.x = B.x 형태에서 단순 실행은 외부 튜플 한 건마다 B 를 한 번씩 스캔한다. A.x 의 distinct 값이 적다면 안쪽 스캔이 군더더기로 반복된다. 조인 컬럼 값으로 키잉한 안쪽 튜플 집합을 캐시하면 군더더기 스캔이 사라진다. 대신 스트리밍 이라면 피할 수 있었을 튜플 메모리 화(materialization) 비용을 받아 들여야 한다. DuckDB, Velox 같은 벡터화 엔진은 배치 해시 빌드 덕분에 이를 공짜로 얻지만, row-store 에는 명시적인 메모이즈 패스가 필요 하다.

세 가지 모두 같은 패턴의 사례다. DB_VALUE 배열을 키로 갖는 해시, 지연 채움(lazy fill), 메모리 상한, hit-ratio 가드. 차이는 무엇 을 메모이즈하느냐, 키가 무엇 이냐, 수명을 누가 소유 하느냐에 있다. fpcache 는 서버 전역이며 쿼리 사이를 가로지른다. sq_cache 와 memoize::storage 는 XASL 별, 실행 별이다. 쿼리 사이를 가로지르는 캐시만 DDL 무효화가 필요하다. XASL 별 캐시들은 XASL 노드가 파괴 되는 시점에 자동으로 무효화된다.

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

엔진마다 같은 세 개의 다이얼을 돌린다. 메모이즈 단위, 키, staleness 판정.

서브쿼리 캐싱. Postgres 는 InitPlan(비상관, 실행 전 한 번)과 SubPlan(상관, 인라인)을 구분하고, SubPlan 의 useHashTable 플래그 가 켜지면 상관 파라미터를 키로 한 work_mem 해시를 만든다. Oracle 의 scalar subquery cache 는 모든 SELECT (...) 스칼라를 256 엔트리 LRU 해시로 감싼다. SQL Server 는 옵티마이즈 시점에 스칼라 서브쿼리 를 join 으로 변환한다. MySQL 은 비상관 서브쿼리를 머터리얼라이즈하고 상관 서브쿼리에는 해싱을 하지 않는다. CUBRID 의 subquery_cache 는 Oracle 에 가장 가깝다. 호출별 해시, 자유 상수가 키, 바이트 단위 예산, fail-on-full, hit-ratio 가드.

필터 술어 캐싱. Postgres 는 백엔드별 PlanCache 안에 역직렬화 된 plan tree 를 캐시하고, 함수 기반 인덱스 술어 상태는 RelationCacheInvalidateEntry 로 무효화한다. Oracle 은 이를 cursor / library cache 안에 숨긴다. CUBRID 의 fpcache 는 그보다 더 입자가 잘다. 함수 기반 / 부분 인덱스가 술어를 B-tree 안에 들고 있고, fpcache 는 BTID 별로 역직렬화된 식의 풀(pool)을 유지한다.

일반 메모이제이션. PostgreSQL 14 이상의 Memoize plan 노드 (nodeMemoize.c)는 파라미터화된 NLJ 의 안쪽 출력을 조인 키로 캐시하며, work_mem 으로 묶이고, LRU 로 evict 되며, 옵티마이저가 선택한다. CUBRID 의 memoize::storage 는 동일한 역할을 하지만 plan 노드가 아니라 런타임 헬퍼 다. 실행 시점에 정적 memoize::possible_check 를 통과한 모양에만 부착되며, 메모리 한도 초과나 hit ratio 저조 시 일반 재실행으로 폴백한다.

이론 ↔ CUBRID 매핑

이론적 개념	CUBRID의 이름
인자 기반 메모이제이션	셋 모두: `sq_cache`, `fpcache`, `memoize::storage`
실행별 스칼라 서브쿼리 캐시	`XASL_NODE::sq_cache` 위의 `SQ_CACHE`
서브쿼리 키 / 값	`SQ_KEY { DB_VALUE **dbv_array }` / `SQ_VAL { SQ_REGU_VALUE val }`
서브쿼리 hit-ratio 가드	`SQ_CACHE_MIN_HIT_RATIO`(=9, 60% 점유에서 발화)
쿼리 횡단 필터 술어 캐시	`fpcache_Hashmap`(latch-free, BTID 키)
필터 술어 엔트리 / 클론 풀	`FPCACHE_ENTRY` / `PRED_EXPR_WITH_CONTEXT **clone_stack`
필터 술어 eviction / 무효화	`fpcache_cleanup`(LRU heap) / `fpcache_remove_by_class`
NLJ 안쪽 메모이제이션	`memoize::storage`
Memoize 키 / 값 / 버킷	`memoize::key` / `value` / `std::unordered_multimap<key, value, …>`
Memoize 키 추출기	`key_maker<TARGET_CLASS>` / `key_maker<TARGET_LIST>`
Memoize 적용 가능성 / hit-ratio 가드	`possible_check` / `MEMOIZE_HIT_RATIO_THRESHOLD = 0.5`(1000회 접근 후)
서버 파라미터(sq / fp / memoize)	`PRM_ID_MAX_SUBQUERY_CACHE_SIZE` / `PRM_ID_FILTER_PRED_MAX_CACHE_*` / `PRM_ID_MEMOIZE_MEMORY_LIMIT`

CUBRID의 구현

세 캐시가 런타임의 군더더기 작업을 막는 층상 방어선 을 이룬다. 동일한 플레이북(DB_VALUE 배열 해시 키, fail-on-full 메모리 예산, hit-ratio 가드)을 세 개의 수명 범위 — 호출별, 쿼리별, 서버 전역 — 에서 따로따로 적용한 결과다.

쿼리 수명 안에서의 캐시 위치

flowchart TB
  subgraph PARSE["1) 파싱 + 계획 (클라이언트)"]
    P2["xasl_generation.c<br/>XASL_SET_FLAG (xasl, XASL_USES_SQ_CACHE)"]
  end
  subgraph PREP["2) Prepare (서버)"]
    Q1["xqmgr_prepare_query + xcache_insert"]
  end
  subgraph EXEC["3) Execute (서버)"]
    E2["qexec_execute_scan<br/>(블록 단위 드라이버)"]
    M1[("memoize::storage<br/>XASL별 다중 튜플<br/>NLJ 상관 키")]
    SQ1[("SQ_CACHE<br/>XASL별 스칼라<br/>자유 상수 키")]
    EVAL["eval_pred<br/>fetch_peek_dbval"]
    INDEX["btree_range_search<br/>· filter pred"]
    FP1[("fpcache_Hashmap<br/>서버 전역<br/>BTID 키")]
  end
  subgraph DDL["4) DDL"]
    INV["locator_sr.c<br/>fpcache_remove_by_class"]
  end

  P2 --> Q1 --> E2
  E2 --> M1
  E2 --> EVAL --> SQ1
  E2 --> INDEX --> FP1
  FP1 --> EVAL
  INV --> FP1

세 개의 경계선이 보인다.

(eval ↔ sq_cache) eval_pred 와 fetch_peek_dbval 안에서, 실행기가 XASL 서브쿼리를 가리키는 TYPE_CONSTANT regu 변수(regu_var->xasl != NULL)에 도달했을 때, 그 XASL 이 XASL_USES_SQ_CACHE 플래그를 들고 있다면 평가기는 먼저 sq_cache 를 prob 한다. miss 면 서브쿼리를 실행하고 스칼라 결과를 put 한다. R_EXISTS 술어도 같은 패턴이다.

(scan ↔ fpcache) locator_eval_filter_predicate 안에서, 함수 기반 또는 부분 인덱스 술어를 평가하기 직전에 locator 는 fpcache_claim 을 호출해 역직렬화된 PRED_EXPR_WITH_CONTEXT 를 얻는다. 사용 가능 한 클론이 있으면 그것을, 없으면 새로 역직렬화한 인스턴스를. 평가가 끝나면 fpcache_retire 로 클론을 반환하거나(스택이 가득 차 있으면) 해제한다.

(scan ↔ memoize) qexec_execute_scan 안에서, nested-loop join 의 안쪽 XASL 이 memoize::storage 를 들고 있다면 드라이버는 현재 조인 키를 memoize_get 으로 캐시를 prob 한다. hit 면 캐시된 튜플 들이 다음 scan 함수로 흘러들어가고 안쪽 스캔은 건너뛴다. miss 면 드라이버가 일반 스캔을 실행하면서 통과한 튜플마다 memoize_put 을 부르고, 스캔이 끝나면 memoize_put_nullptr 을 부른다.

Subquery cache — XASL 노드 위의 `SQ_CACHE`

캐시는 자기가 캐시하는 XASL 노드 위에 산다.

// SQ_CACHE — src/query/subquery_cache.h
struct sq_cache
{
  SQ_KEY *sq_key_struct;        /* prebuilt key shape */
#if defined (SERVER_MODE) || defined (SA_MODE)
  MHT_TABLE *ht;
  UINT64 size_max;              /* size budget (bytes) */
  UINT64 size;
  bool enabled;                 /* hit-ratio guard */
  struct { int hit; int miss; } stats;
#endif
};

struct sq_key { DB_VALUE **dbv_array; int n_elements; };
struct sq_val { SQ_REGU_VALUE val; REGU_DATATYPE type; };

키는 자유 상수 배열이다. XASL 생성 단계에서, 변하는 입력이 바인드 값이나 상관 컬럼뿐인 서브쿼리를 옵티마이저가 식별하면 XASL_USES_SQ_CACHE 플래그를 세팅하고 sq_key_struct 안에 SQ_KEY 모양 — 살아 있는 regu 변수들을 가리키는 포인터 배열 — 을 저장해 둔다. 실행 시점에는 sq_make_key 가 그 배열을 따라가며 각 DB_VALUE 를 db_value_copy 로 깊은 복사 해 새 SQ_KEY 를 만든다.

해시 함수 는 mht_get_hash_number 의 결과를 회전하고 XOR 한다. 13 비트 회전은 동일 원소가 자리만 바뀐 경우의 충돌을 방지한다. memoize::key::hash 가 쓰는 관용구와 같다.

// sq_hash_func — src/query/subquery_cache.c
for (int i = 0; i < k->n_elements; i++)
  {
    h = ROTL32 (h, 13);
    h ^= mht_get_hash_number (ht_size, k->dbv_array[i]);
  }

값은 두 가지 모양 중 하나다. TYPE_CONSTANT(스칼라 서브쿼리)는 깊은 복사된 DB_VALUE. TYPE_LIST_ID(EXISTS)는 안쪽 결과가 비어 있지 않은지 여부를 나타내는 boolean 하나면 충분하다. EXISTS 는 집합이 공집합인지만 묻기 때문이다.

// sq_make_val — src/query/subquery_cache.c (condensed)
case TYPE_CONSTANT:
  ret->val.dbvalptr = db_value_copy (val->value.dbvalptr);
  break;
case TYPE_LIST_ID:
  ret->val.exists = (val->value.srlist_id->list_id->tuple_cnt > 0);
  break;

메모리 예산과 hit-ratio 가드. 단위는 엔트리 수 가 아니라 바이트 다. PRM_ID_MAX_SUBQUERY_CACHE_SIZE 가 hard cap 이며, sq_put 은 사용 바이트를 추적하다 큰 엔트리는 거부하고 캐시를 비활성화한다. sq_get 의 hit-ratio 가드는 점유율이 60% 를 넘는 순간 발화한다.

// sq_get — src/query/subquery_cache.c (condensed)
if ((double) SQ_CACHE_SIZE (xasl) > (double) SQ_CACHE_SIZE_MAX (xasl) * 0.6)
  if (SQ_CACHE_HIT (xasl) / SQ_CACHE_MISS (xasl) < SQ_CACHE_MIN_HIT_RATIO)
    { SQ_CACHE_ENABLED (xasl) = false; return false; }

정수 나눗셈이 hit/miss 를 floor 한다. 헤더 주석은 9, it means 90% 라고 적혀 있지만 실제 컷오프는 이보다 약간 낮은 쪽으로 편향된다.

행 평가에 두 군데서 연결된다. 둘 다 prob-or-execute 라는 같은 패턴을 따른다. R_EXISTS 는 query_evaluator.c::eval_pred 에서, TYPE_CONSTANT 는 fetch.c::fetch_peek_dbval 에서.

// fetch_peek_dbval — src/query/fetch.c (condensed)
if (xasl && XASL_IS_FLAGED (xasl, XASL_USES_SQ_CACHE)
    && !(SQ_CACHE_HT (xasl) && !SQ_CACHE_ENABLED (xasl)))
  {
    if (!sq_get (thread_p, SQ_CACHE_KEY_STRUCT (xasl), xasl, regu_var))
      {
        EXECUTE_REGU_VARIABLE_XASL (thread_p, regu_var, vd);
        if ((key = sq_make_key (thread_p, xasl)) == NULL)
          { XASL_CLEAR_FLAG (xasl, XASL_USES_SQ_CACHE); goto exit_on_error; }
        if (sq_put (thread_p, key, xasl, regu_var) == ER_FAILED)
          { sq_free_key (thread_p, key); }
      }
  }

비활성화 검사 !(SQ_CACHE_HT && !SQ_CACHE_ENABLED) 는 다음을 의미 한다. 미초기화(지연 초기화 시도) 또는 활성(사용)이면 들어가고, 초기화는 됐지만 비활성화 됨 인 경우만 캐시를 건너뛴다.

Filter-predicate cache — `fpcache_Hashmap`

세 캐시 중 유일하게 서버 전역이다. 함수 기반 / 부분 인덱스는 자기 술어를 B-tree 정의 안에 들고 있고, 모든 인덱스 연산이 이를 실행 가능한 트리 형태로 필요로 한다. fpcache 는 BTID 별로 역직렬화된 트리를 캐시한다.

// fpcache_ent — src/query/filter_pred_cache.c
struct fpcache_ent
{
  BTID btid;
  /* Latch-free stuff. */
  FPCACHE_ENTRY *stack, *next;
  pthread_mutex_t mutex;
  UINT64 del_id;

  OID class_oid;
  struct timeval time_last_used;        /* LRU timestamp */

  PRED_EXPR_WITH_CONTEXT **clone_stack; /* deserialised tree pool */
  INT32 clone_stack_head;
};

메모이제이션이 두 층이다. 바깥쪽: 해시맵, BTID 가 키. 안쪽: 클론 스택 — 각 엔트리가 PRED_EXPR_WITH_CONTEXT 의 작은 풀을 들고 있고, 풀 크기는 PRM_ID_FILTER_PRED_MAX_CACHE_CLONES 가 정한다. 동시 reader 들은 들어올 때 클론을 claim 하고 나갈 때 retire 한다. 빈 스택을 claim 하면 새로 역직렬화하고, 가득 찬 스택 에 retire 하면 클론을 해제한다. 이 패턴은 “역직렬화된 구조는 스레드 간에 공유될 수 없다” 라는 제약을 푼다. 각 스레드가 자신의 사적 사본을 다시 역직렬화 비용 없이 얻는다. 통계는 네 결과를 구분한다. 해시맵 hit/miss, 클론 hit/miss.

동시성. cubthread::lockfree_hashmap<BTID, fpcache_ent> — 지연 삭제(del_id)를 가진 latch-free 오픈 체인 해시. 읽기는 쓰기를 막지 않고, 쓰기는 클론 스택을 변경할 때만 fpcache_entry->mutex 로 직렬화된다.

Claim 경로.

// fpcache_claim — src/query/filter_pred_cache.c (condensed)
fpcache_entry = fpcache_Hashmap.find (thread_p, *btid);
if (fpcache_entry != NULL)
  {
    ATOMIC_INC_64 (&fpcache_Stat_hit, 1);
    if (fpcache_entry->clone_stack_head >= 0)
      {
        *filter_pred = fpcache_entry->clone_stack[fpcache_entry->clone_stack_head--];
        ATOMIC_INC_64 (&fpcache_Stat_clone_hit, 1);
      }
    pthread_mutex_unlock (&fpcache_entry->mutex);
  }

if (*filter_pred == NULL)
  {
    HL_HEAPID old_heap = db_change_private_heap (thread_p, 0);
    stx_map_stream_to_filter_pred (thread_p, filter_pred,
                                   or_pred->pred_stream,
                                   or_pred->pred_stream_size);
    db_change_private_heap (thread_p, old_heap);
  }

핵심은 역직렬화가 글로벌 힙 (db_change_private_heap (thread_p, 0)) 에서 일어난다는 점이다. 스레드 사적 힙이 아니다. 캐시된 클론은 어떤 단일 트랜잭션보다 오래 살아남으며, 사적 힙 할당은 트랜잭션 종료 시점에 회수되어 댕글링 포인터를 만들었을 것이다.

Retire 는 claim 의 거울 — find-or-insert, 자리가 있으면 클론을 push, 없으면 해제. 새 엔트리를 insert 하면 fpcache_Entry_counter >= fpcache_Soft_capacity 일 때 cleanup 이 시작된다.

Eviction. fpcache_cleanup 은 binary-heap 으로 LRU 를 구현한다. 모든 엔트리를 훑어 가장 오래된 20% (FPCACHE_CLEANUP_RATIO = 0.2) 를 time_last_used 로 정렬해 지운다. fpcache_Cleanup_flag 가 한 번에 한 cleaner 만 동작하게 직렬화한다. 상한은 soft — cleanup 중에는 잠시 초과될 수 있다.

무효화. fpcache_remove_by_class 는 locator_sr.c:5679 (클래스 drop), locator_sr.c:6302(클래스 alter), log_manager.c:5105 (DDL recovery)에서 호출된다. 두 단계 워크 — 먼저 BTID 들을 모으고 (이터레이션 중 삭제 불가), 그 다음 erase. 한 번에 모을 수 있는 양은 FPCACHE_DELETE_BTIDS_SIZE = 1024 로 제한되며, 버퍼가 가득 차면 바깥 루프가 이터레이션을 다시 시작한다.

Memoize — XASL별 `memoize::storage`

세 캐시 중 가장 새로 들어온 친구다(코드량 29 KB, 다른 두 친구는 15 KB와 23 KB). nested-loop join 의 안쪽을 메모이즈한다. 외부 스캔이 만나는 distinct 한 상관 키 값마다 안쪽 스캔의 튜플 묶음을 캐시해, 같은 키가 반복되는 외부 행은 캐시에서 읽도록 한다.

// storage — src/query/memoize.hpp (condensed)
class storage
{
public:
  static storage *new_storage (THREAD_ENTRY *, size_t max_storage_size,
                               xasl_node *);
  result_code get ();
  result_code put ();
  result_code put_nullptr();
  void set_key_changed ();

  size_t hit;
  size_t miss;
private:
  std::unordered_multimap<key *, value *, key::hash, key::equal>
    m_key_value_map;
  fixed_allocator<key> m_key_fixed_allocator;
  /* ... */
};

다중 튜플 값. sq_cache(키당 스칼라 1개)와 fpcache(키당 트리 1개 + 클론 풀)와 달리 memoize 는 unordered_multimap 을 쓴다. 한 키에 0개 이상의 값(안쪽 튜플의 컬럼 리스트)이 매핑된다. “안쪽 매치 가 없는” 빈 케이스는 스캔 종료 시 put_nullptr 이 삽입한 nullptr 값으로 표현한다.

스캔 루프와 두 단계 상호작용. qexec_execute_scan 은 안쪽 스캔 을 돌리기 전에 캐시를 prob 한다. hit 이면 캐시된 값들을 다음 scan 함수로 흘려 보낸다. miss 이면 일반 스캔을 돌리면서 통과한 튜플마다 put, 끝에서 put_nullptr 을 부른다.

storage::get 의 상태 머신은 (key_changed, has_range) 두 변수에 따라 세 갈래다.

key_changed = true(외부 행이 set_key_changed 로 진행 신호를 받음): 새 키를 만들고 m_key_value_map 을 조회. 엔트리가 없으면 miss++, NOT_FOUND 반환(안쪽 스캔이 돌아야 한다). 있으면 hit++, 첫 값을 dequeue (nullptr → ENDED, 그 외 → SUCCESS).
key_changed = false, has_range = true: m_current_value_list 에서 다음 캐시 튜플 pop. 비었으면 has_range=false, ENDED. 그 외에는 SUCCESS.
key_changed = false, has_range = false: NOT_FOUND.

키 추출은 구조적이다. memoize::key_maker<TARGET_TYPE> 은 안쪽 XASL 의 술어 트리(where_key, where_pred, where_range, if_pred, after_join_pred, 그리고 dptr_list)를 걸으며 모든 TYPE_CONSTANT regu 변수 — 외부 스캔에서 흘러들어온 상관 컬럼 — 를 모은다. 그 다음 dbvalptr 이 spec regu 리스트 포인터(TARGET_CLASS 용 cls_regu_list_pred/rest/range/key, TARGET_LIST 의 list-node 대응물)에 매치되는 TYPE_CONSTANT 를 제거 한다. 그것들은 안쪽 스캔의 자기 바인딩 이지 상관 컬럼이 아니다. 남은 것이 캐시 키가 된다. if constexpr 분기가 spec 타입에 따라 알맞은 union 필드를 고른다. 그 외에는 동일한 로직이다.

적용 가능성은 memoize::possible_check 가 결정한다. XASL 노드를 훑어 안전하지 않은 모양들을 거른다. spec/val_list null, spec->next non-null(다중 spec), bptr_list/fptr_list non-null, 지원되지 않는 spec->type(CLASS_ATTR, SET, JSON_TABLE, METHOD, REGUVAL_LIST, SHOWSTMT, DBLINK), 시스템 클래스 또는 MVCC 비활성 클래스, spec->access 가 SEQUENTIAL/INDEX 이외, val_list 안의 set/multiset/sequence 도메인, dptr_list 멤버 중 XASL_LINK_TO_REGU_VARIABLE 이 없는 항목. 재귀의 level 인자는 aptr_list 의 재귀를 level >= 1 에서만 허용한다. level == 0 의 바깥 aptr_list 는 옵티마이저가 끌어올린 비상관 서브쿼리들이며 안쪽 스캔 메모이즈와는 무관하다.

Hit-ratio 가드. sq_cache 와 같은 모양이다. 1000회 접근 (MEMOIZE_FREE_ITERATION_LIMIT)을 넘긴 뒤 hit ratio 가 0.5 미만 (MEMOIZE_HIT_RATIO_THRESHOLD)이면 스토리지가 자기 자신을 비활성화 한다.

// storage::put — src/query/memoize.cpp (condensed)
if (disabled || get_current_size() >= m_max_storage_size)
  { disabled = true; return result_code::FULL; }
if (hit + miss > MEMOIZE_FREE_ITERATION_LIMIT)
  if (((double)hit) / (hit + miss) < MEMOIZE_HIT_RATIO_THRESHOLD)
    { disabled = true; return result_code::FULL; }

문턱치가 sq_cache 의 90% 보다 너그러운 까닭은 단순하다. 100 튜플 짜리 안쪽 스캔에서 50% hit 면 CPU/IO 절감액이 작지 않다.

할당 풀. 키는 m_key_fixed_allocator(slab 할당기, 고정 크기 블록 재활용)에서, 값은 malloc 에서. 두 할당기를 쓰는 까닭은 키는 숫자가 많아서(외부 행마다 하나) slab 재활용으로 이득을 보고, 값은 크기가 들쑥날쑥하기 때문이다.

수명 주기 연결. qexec_execute_mainblock 의 라인 15770 부근에서 spec_level == 0 && level >= 1 && !mvcc_select_lock_needed 일 때 실행기는 안쪽 XASL 위에 new_memoize_storage 를 호출한다. qexec_execute_scan 은 xasl->memoize_storage 가 non-null 이면 qexec_execute_nljoin_with_memoize 로 진입한다. hit 이면 캐시된 fast-path 가 즉시 반환하고, 그 외에는 일반 스캔 루프가 통과 튜플마다 memoize_put 을 부르고 끝에 memoize_put_nullptr 을 부른다. 스토리 지는 다음 install(이터레이션 리셋) 시 clear_memoize_storage 가, 또는 teardown 시 qexec_clear_xasl 이 파괴한다.

세 캐시 비교

축	`sq_cache`	`fpcache`	`memoize::storage`
범위(scope)	XASL 별	서버 전역	XASL 별
키	`DB_VALUE` 배열(자유 상수)	`BTID`	`DB_VALUE` 배열(상관 컬럼)
값	`DB_VALUE` 또는 boolean	`PRED_EXPR_WITH_CONTEXT` 클론 풀	`std::vector<DB_VALUE>`(다중 튜플)
해시 테이블	`MHT_TABLE`(사적)	`cubthread::lockfree_hashmap`	`std::unordered_multimap`
동시성	단일 스레드	latch-free + 엔트리별 mutex	단일 스레드
Eviction	fail-on-full	binary heap 기반 LRU	fail-on-full
무효화	XASL teardown	`fpcache_remove_by_class`	XASL teardown
Hit-ratio 가드	60% 점유에서 90%	없음(cleanup 이 staleness 처리)	1000 접근 후 50%
크기 예산	`PRM_ID_MAX_SUBQUERY_CACHE_SIZE`	`PRM_ID_FILTER_PRED_MAX_CACHE_*`	`PRM_ID_MEMOIZE_MEMORY_LIMIT`
사용 사례	비상관 스칼라 서브쿼리	함수 기반/부분 인덱스 술어	NLJ 안쪽
Plan 시점 플래그	`XASL_USES_SQ_CACHE`	없음(활성화 시 항상 동작)	없음(런타임 `possible_check`)
초기화	지연(첫 put/get)	부팅(`fpcache_initialize`)	지연(실행마다)

세 캐시 모두 키를 DB_VALUE 배열에서 끌어내고 회전-XOR 해시를 사용한다. 셋 다 메모리를 지배 예산으로 다루며 자기 비활성화 가드를 포함한다. 차이는 무엇 을 메모이즈하느냐(스칼라 vs 트리 풀 vs 튜플 스트림)와 수명 안의 어디 에 캐시가 앉아 있느냐에서 나온다.

소스 코드 가이드

심볼은 파일과 호출 흐름을 따라 그룹화한다. 위치 표는 절 끝에 둔다.

subquery_cache.c

키/값 수명: sq_make_key, sq_make_val, sq_free_key, sq_free_val, sq_unpack_val. 해시 정책: sq_hash_func, sq_cmp_func, sq_rem_func. 수명 주기: sq_cache_initialize(테이블 지연 생성), sq_cache_destroy, sq_put(바이트 예산 가드, mht_put_if_not_exists), sq_get(60% 점유 hit-ratio 가드). 매크로: SQ_CACHE_MIN_HIT_RATIO, SQ_CACHE_EXPECTED_ENTRY_SIZE, 그리고 해시 테이블/활성 플래그/키 모양/hit-miss 카운터/사이즈/사이즈 상한에 대한 SQ_CACHE_*(xasl) 접근자 군.

filter_pred_cache.c

정적 전역: fpcache_Enabled, fpcache_Soft_capacity, fpcache_Hashmap, fpcache_Entry_counter, fpcache_Clone_counter, fpcache_Clone_stack_size, fpcache_Cleanup_flag, fpcache_Cleanup_bh, fpcache_Stat_* 카운터 군.

Latch-free 엔트리 디스크립터 콜백: fpcache_entry_alloc, fpcache_entry_free, fpcache_entry_init, fpcache_entry_uninit, fpcache_copy_key — 모두 LF_EM_USING_MUTEX 와 함께 fpcache_Entry_descriptor 에 묶여 있다.

공개 API: fpcache_initialize, fpcache_finalize, fpcache_claim, fpcache_retire, fpcache_remove_by_class, fpcache_drop_all, fpcache_dump. 내부: fpcache_cleanup, fpcache_compare_cleanup_candidates(tv_sec 만 비교). 상수: FPCACHE_CLEANUP_RATIO = 0.2, FPCACHE_DELETE_BTIDS_SIZE = 1024.

외부에서 claim/retire 를 부르는 곳은 locator_sr.c 의 locator_eval_filter_predicate 하나뿐이다. fpcache_remove_by_class 는 locator_drop_class, locator_check_btid, 그리고 log_manager.c 의 DDL 로그 재생이 부른다.

memoize.cpp

네임스페이스 상수: MEMOIZE_FREE_ITERATION_LIMIT = 1000, MEMOIZE_HIT_RATIO_THRESHOLD = 0.5, hash_entry_sz.

타입: result_code enum(SUCCESS/ENDED/NOT_FOUND/FULL/ERROR), key (DB_VALUE 의 vector + hash + equal), value(DB_VALUE 의 vector), storage 클래스. 정적 싱글턴: checker(possible_check), cls_key_maker, list_key_maker(key_maker<TARGET_TYPE> 인스턴스).

key_maker<TARGET_TYPE> 은 함수 객체 템플릿으로, 방문 가능한 모든 XASL/술어 노드에 대한 오버로드를 제공한다. 최상위 (thread_p, xasl, key_ptr_src), 재귀 서브쿼리 walker, pred_expr*, pred*, eval_term, comp_eval_term, alsm_eval_term, like_eval_term, rlike_eval_term, regu_variable_node*, ARITH_TYPE*, REGU_VARIABLE_LIST, REGU_VALUE_LIST*, function_node*, sp_node*. TYPE_CONSTANT regu 포인터를 모은 뒤 spec 자기 regu 들을 빼고 남은 개수를 돌려준다.

storage 멤버: new_storage(팩토리), 생성/소멸자, init, get, put, put_nullptr, get_key, get_value, set_value, set_key_changed, start_timer/stop_timer(TSC, thread_p->on_trace 일 때만), get_current_size. C 브리지: new_memoize_storage, clear_memoize_storage, memoize_get, memoize_put, memoize_put_nullptr — result_code 를 (success, is_ended) 두 boolean 으로 바꾸고 FULL 일 때 스토리지를 비운다.

횡단 참조

query_executor.c: qexec_execute_nljoin_with_memoize(8164), qexec_execute_scan(8299), qexec_execute_mainblock(15770 install 지점), qexec_clear_xasl(teardown 지점들 ~2335, 2396, 2914). query_evaluator.c: eval_pred 의 R_EXISTS 분기(1849). fetch.c: fetch_peek_dbval 의 TYPE_CONSTANT 분기(4002). locator_sr.c: locator_eval_filter_predicate(~8170); fpcache_remove_by_class 호출자(5679, 6302). log_manager.c: DDL recovery 호출(5105). xasl_generation.c: XASL_USES_SQ_CACHE 설정 지점(1681, 6996, 14010).

위치 힌트(이 리비전 기준)

심볼	파일	라인
`SQ_KEY`, `SQ_VAL`, `SQ_CACHE`	`subquery_cache.h`	51-95
`SQ_CACHE_MIN_HIT_RATIO`	`subquery_cache.h`	40
`sq_make_key`, `sq_make_val`	`subquery_cache.c`	67, 103
`sq_free_key`, `sq_free_val`	`subquery_cache.c`	143, 162
`sq_unpack_val`, `sq_hash_func`	`subquery_cache.c`	191, 227
`sq_cmp_func`, `sq_rem_func`	`subquery_cache.c`	251, 283
`sq_cache_initialize`	`subquery_cache.c`	301
`sq_put`, `sq_get`	`subquery_cache.c`	337, 407
`sq_cache_destroy`	`subquery_cache.c`	461
`FPCACHE_ENTRY` (struct fpcache_ent)	`filter_pred_cache.c`	41
`fpcache_Hashmap`, `fpcache_Entry_descriptor`	`filter_pred_cache.c`	74, 118
`fpcache_initialize`, `fpcache_finalize`	`filter_pred_cache.c`	146, 209
`fpcache_entry_alloc`/`free`/`init`/`uninit`	`filter_pred_cache.c`	250-335
`fpcache_claim`, `fpcache_retire`	`filter_pred_cache.c`	362, 430
`fpcache_remove_by_class`, `fpcache_dump`	`filter_pred_cache.c`	506, 594
`fpcache_cleanup`	`filter_pred_cache.c`	645
`fpcache_compare_cleanup_candidates`	`filter_pred_cache.c`	733
`fpcache_drop_all`	`filter_pred_cache.c`	760
`MEMOIZE_FREE_ITERATION_LIMIT`/`THRESHOLD`	`memoize.hpp`	32-33
`memoize::key` / `value` / `storage`	`memoize.hpp`	47, 67, 81
`memoize::possible_check`	`memoize.cpp`	39
`memoize::key_maker<TARGET_TYPE>`	`memoize.cpp`	163
`memoize::key::hash`/`equal`	`memoize.cpp`	668, 679
`memoize::storage::new_storage`/`dtor`	`memoize.cpp`	693, 765
`memoize::storage::get`/`put`/`put_nullptr`	`memoize.cpp`	813, 893, 937
`memoize::storage::get_key`/`get_value`	`memoize.cpp`	981, 1003
C 브리지: `new_memoize_storage`/`clear_`/`memoize_`	`memoize.cpp`	1045-1186
`XASL_USES_SQ_CACHE`, `sq_cache`, `memoize_storage`	`xasl.h`	518, 1167, 1194
`eval_pred`(sq_cache 연결)	`query_evaluator.c`	1849
`fetch_peek_dbval`(sq_cache 연결)	`fetch.c`	4002
`qexec_execute_nljoin_with_memoize`	`query_executor.c`	8164
`qexec_execute_scan`(memoize hook)	`query_executor.c`	8299
`new_memoize_storage` install 지점	`query_executor.c`	15770
`locator_eval_filter_predicate`	`locator_sr.c`	~8170
`fpcache_remove_by_class` 호출자	`locator_sr.c` / `log_manager.c`	5679, 6302 / 5105

소스 검증 및 비교 노트

Subquery cache 정수 절단(integer truncation). 가드 SQ_CACHE_HIT / SQ_CACHE_MISS < SQ_CACHE_MIN_HIT_RATIO 는 정수 나눗셈이고, MISS == 0 이면 zero division 이 발생한다. 가드 자체는 60% 점유 이후에만 돌기 때문에 실제로는 어딘가에서 miss 가 나 있을 수밖에 없지만, 60% 까지 완벽히 적중한 워크로드라면 이론적으로 크래시가 가능하다. 방어적 MISS == 0 체크는 없다.
SQ_CACHE_MIN_HIT_RATIO 주석 vs 값. 헤더 주석은 “9, it means 90%” 라고 되어 있고 상수는 정수 9 다. 컷오프는 hits/misses ∈ [8, 9) 이면 비활성화, [9, 10) 이면 유지로 동작한다. 즉 90% 가 아니라 그보다 살짝 낮은 쪽으로 편향된다.
Filter-pred soft cap. fpcache_Entry_counter 는 insert 와 cleanup 사이에 Soft_capacity 를 잠시 초과할 수 있다. fpcache_remove_by_class 안의 엔트리가 해시맵에 없다 단언 (assert (false))은 동시 무효화가 없다는 가정에 의지한다. DDL 부하가 큰 워크로드에서는 디버그 빌드가 이 단언에 걸릴 수 있다.
Memoize hit-ratio 가드는 put 에서 발화한다. get 이 아니다. 안쪽이 한 번에 다 채워진 뒤 읽기만 일어나는 캐시는 영원히 비활성화 되지 않는다. 워밍업 단계에서 이 비대칭이 의미를 가진다.
sq_cache_initialize 가 sq_get 안에서 두 번 불린다. null 체크에서 한 번, if (!SQ_CACHE_HT) 안에서 또 한 번. Hit-ratio 블록은 지연 초기화 전에 SQ_CACHE_HIT/MISS 를 참조한다. 0 으로 초기화돼 있다면 무해하지만 호출 순서가 미묘하다.
서버 모드 전용 필드. SQ_CACHE 의 해시와 통계는 SERVER_MODE/SA_MODE 가드 안에 있다. CS_MODE 에서는 캐시가 사실상 sq_key_struct 하나뿐이다. 키는 클라이언트에서 계산되고 해시 테이블은 서버에서 관리된다. XASL_USES_SQ_CACHE 플래그는 직렬화된 XASL 과 함께 운반된다.
fpcache_compare_cleanup_candidates 는 tv_usec 을 무시한다. 비교 기준이 tv_sec 뿐이다. 1초 미만 사이에 retire 된 엔트리들의 순서는 정의되지 않으며, 벤치마크처럼 회전이 빠른 워크로드에서는 eviction 이 노이즈에 흔들린다.
Memoize 의 aptr_list 재귀 게이트가 level >= 1. level 0 의 바깥 aptr_list 는 옵티마이저가 끌어올린 비상관 서브쿼리들이며 안쪽 스캔 메모이즈 결정과 무관하다. level 1 이상이면 안쪽 블록의 구조 일부다.
filter_pred_cache.c 에 해시맵 선언이 두 개. 라인 74-76 은 fpcache_Hashmap(C++ lockfree_hashmap), fpcache_Ht (C LF_HASH_TABLE), fpcache_Ht_freelist 를 선언한다. 실제로 쓰는 것은 C++ 쪽이며 C 스타일 두 개는 잔재로 보인다.

열린 질문

sq_cache 와 속성 상관 서브쿼리. 캐시 키는 자유 상수만 다룬다. 옵티마이저가 속성 상관 서브쿼리를 상수 형태로 재작성하는가, 아니면 그런 케이스에는 XASL_USES_SQ_CACHE 가 단순히 안 걸리는가? xasl_generation.c 의 설정 지점(1681, 6996, 14010)이 답을 갖고 있다.
memoize::storage 가 DDL 보다 오래 사는가? XASL cache 는 DDL 시 xcache_remove_by_oid 로 엔트리를 무효화하지만, 진행 중인 실행 은 자기 스토리지를 들고 정상 종료한다. 빠르게 읽었을 때 race 는 없어 보이지만 형식적 증명은 추적이 더 필요하다.
fpcache 의 키가 왜 (class_oid, btid) 가 아닌가? 현재 키는 BTID 단독이다. 스키마 재사용 시 두 클래스가 BTID 를 공유할 수 있 다는 가정 하에 캐시는 유일성을 신뢰하고 fpcache_retire 안에서 OID_EQ (class_oid) 로 단언한다.
Hit-ratio 임계값들이 튜닝된 값인가? 9(sq_cache), 0.5(memoize), 임계값 없음(fpcache)은 측정이라기보다는 직관적 선택처럼 보인다.
fpcache 가 MERGE / UPSERT 를 다루는가? locator_eval_filter_predicate 는 모든 B-tree 변이에서 호출된다. MERGE 는 같은 인덱스에 INSERT 와 UPDATE 경로 모두를 발사하므로 두 경로 모두 캐시를 사용해야 한다. 다만 MERGE 가 한 행을 insert 한 뒤 update 할 때의 claim/retire 순서까지는 여기서 추적하지 않았다.
set_value 가 hit 마다 다시 clone 한다. 값 리스트가 넓을 때는 새 값이 이전 값과 같더라도 행마다 복사 비용이 든다. 비교 후 skip 이 도움이 되려면 pr_clone_value 보다 비교가 싸야 한다. 측정되지 않았다.

출처

CUBRID 소스 파일(참고용):

src/query/subquery_cache.{c,h} — 스칼라 서브쿼리 캐시; SQ_CACHE, SQ_KEY, SQ_VAL, SQ_TYPE 정의; 예산 매크로.
src/query/filter_pred_cache.{c,h} — 서버 전역 필터 술어 캐시; 공개 fpcache_* API.
src/query/memoize.{hpp,cpp} — XASL 별 일반 메모이제이션; storage, key, value, result_code, C 브리지.
src/query/query_executor.c — memoize_* 와 sq_cache_destroy 를 qexec_execute_scan / mainblock / clear_xasl 에 연결.
src/query/query_evaluator.c, src/query/fetch.c — eval_pred / fetch_peek_dbval 의 sq_cache prob.
src/transaction/locator_sr.c, src/transaction/log_manager.c — fpcache_claim / retire 호출자와 fpcache_remove_by_class 트리거 (DDL + 복구).
src/parser/xasl_generation.c — XASL_USES_SQ_CACHE 설정 지점.

문서 간 참조:

cubrid-xasl-cache.md — plan 단위 캐시, 보완 관계: XASL cache 는 컴파일된 plan 전체를 메모이즈하고, 런타임 캐시들은 그 plan 아래 실행의 조각 들을 메모이즈한다. 둘 다 cubthread::lockfree_hashmap 을 통한 latch-free 해시맵 패턴을 공유한다.
cubrid-query-evaluator.md — eval_pred, fetch_peek_dbval, 그리고 PRED_EXPR walker — sq_cache prob 한 단계 위.
cubrid-btree.md — fpcache 의 키로 쓰이는 BTID 의 소유자.