Why a query pipeline at all

SQL is declarative — "give me these rows". The engine has to invent a plan that produces them. That invention is the query pipeline.

• Classical 7-stage architecture — Selinger 1979, System R. Every major RDBMS shares this skeleton.
• The pipeline materialises SQL into an iterator plan plus a cache that skips compile on re-execute.

Scope: broker/CAS in; storage stack (heap, B+Tree, page buffer, MVCC) out.

Parser — Flex + Bison → PT_NODE

The front door. Turn a string into a tree.

• Lexer — Flex tokenizer. Keywords, identifiers, literals, operators.
• Parser — GLR Bison grammar. GLR handles SQL's ambiguities — same prefix can mean different productions.
• Output IR — PT_NODE, a polymorphic tagged-union tree. Each node: a node_type tag, a dispatch into three function-pointer arrays (init / apply / free), sub-info via union info, and next for sibling lists.
• Allocator — PT_NODE allocated from a per-PARSER_CONTEXT block allocator; freed on context destroy.

The whole front-end and middle-end mutates this tree in place. Its shape is the prerequisite for reading any later stage.

Semantic check — resolve, type, CNF

The parser produces shape, not meaning. Semantic check annotates the tree with meaning.

Four passes, all driven by pt_check_with_info:

1. Name resolution. Every PT_NAME must bind to something — a column in scope, a function, a parameter. Consults the catalog. Failed binding → error 213, "Unknown column ..." at this stage.
2. Where-clause aggregate check. Aggregates (SUM, COUNT) belong in SELECT / HAVING, not WHERE. Catches WHERE COUNT(*) > 0 early.
3. Host-variable replacement. Bound parameters (? placeholders) get their type info from the supplied bind.
4. semantic_check_local — the heavy pass. Recurses with pt_semantic_type to check operand types, insert implicit coercions, and constant-fold literal-only sub-expressions (1 + 2 → 3).

Then pt_cnf rewrites every WHERE clause into conjunctive normal form — (A OR B) AND (C OR D). CNF is the shared language: rewriter pushes conjuncts, optimizer costs each, executor evaluates in eval_pred.

Every node carries type / OID / coercion annotations; the rewriter inherits a typed tree.

Query rewrite — flatten, inline, lower

mq_rewrite and friends — the algebraic transform pass. Operates on a fully-resolved, type-checked, CNF'd tree. The goal is to expose work to the optimizer that was hidden inside the source SQL.

LIMIT lowering ripples across rewrite, plan generation, and runtime — one feature, three stages.

Cost model basics

A cost-based optimizer is exactly as good as its cost model — which is exactly as good as its statistics.

• Cardinality — how many rows does this operator emit?
  • Comes from _db_stat for base relations; from per-operator estimates for derived ones.
  • seq scan(R) → |R|.
  • σ(R, p) → |R| * selectivity(p).
  • R ⋈ S on equi-key → |R| * |S| / max(distinct(R.key), distinct(S.key)).
• Selectivity — fraction of rows that pass a predicate.
  • Per-column histograms when available; back-off to default constants (e.g. 0.1 for =, 0.333 for <) when not.
  • qo_equal_selectivity, qo_range_selectivity are the consumer APIs.
• IO term — pages read. Index access costs tree_height + leaf_pages_scanned; sequential costs pages(R).
• CPU term — per-tuple work. Scaled by an internal constant; rarely the dominant factor on a real workload.

Same SQL + same catalog → same plan. Data growth causing cardinality drift is what the RT recompile check watches.

XASL generation — QO_PLAN → XASL_NODE tree

XASL is the executor IR. Where QO_PLAN says "merge-join R with S", XASL says "open scan over R, open scan over S, drive merge with OUTPTR_LIST, evaluate pred per probe."

• One XASL_NODE per relational operator, with three child-slot conventions:

• Sub-IRs carried by every XASL_NODE:
  • ACCESS_SPEC — which relation, which index, which range, which heap.
  • OUTPTR_LIST — projection list — what tuple shape this node emits.
  • PRED_EXPR — the predicate tree for the WHERE / ON clause attached here.
  • REGU_VARIABLE — operand resolver (constant / column / arithmetic expression).
• Serialisation. xts_* fixes up internal pointers as integer offsets into one flat byte buffer for cache, ship, and checksum.

aptr runs once; dptr runs per outer tuple. Misreading those is the most common bug in XASL-level patches.

Volcano executor — open / next / close

The back-end's executor is a textbook Volcano iterator.

• One method triple per operator: open() initialises state, next() produces the next tuple or EOF, close() tears down.
• Tuples are pulled, not pushed. Rows climb the tree on demand.
• Back-pressure is automatic — operators below stall until the next next() arrives. LIMIT 10 stops the whole sub-tree after row 10.

// qexec_execute_mainblock_internal — src/query/query_executor.c
int run (THREAD_ENTRY *th, XASL_NODE *xasl)
{
  scan_open (xasl, &sid);                  // open
  while (scan_next (&sid, &tuple) == OK)   // next
    {
      if (!eval_pred (xasl->where, tuple)) continue;
      list_file_append (xasl->list_id, project (xasl->outptr, tuple));
    }
  scan_close (&sid);                       // close
  return NO_ERROR;
}

Scan manager — SCAN_ID dispatch

One uniform open / next / close interface upward.

Access methods

One line each. All present the same SCAN_ID interface upward.

Access method = how tuples enter the pipeline. Every other operator consumes from one of these; everything else is shaping.

Predicate evaluation — PRED_EXPR + REGU_VARIABLE

The same evaluator runs at every site that needs "does this tuple match?" — scan filters, join conditions, post-processing.

• PRED_EXPR tree. Two leaf kinds: T_PRED (boolean operator: AND, OR, NOT) and T_EVAL_TERM (leaf comparison: x = y, a < b, s LIKE p).
• REGU_VARIABLE operands. Resolves to: a constant, a column reference, an arithmetic expression (via qdata_*), a function call, or a host parameter.
• Three-valued logic. TRUE / FALSE / UNKNOWN; Kleene's rules — TRUE AND UNKNOWN = UNKNOWN, FALSE AND UNKNOWN = FALSE.

// eval_pred — src/query/query_evaluator.c
DB_LOGICAL eval_pred (THREAD_ENTRY *th, PRED_EXPR *p, VAL_DESCR *vd, OID *o)
{
  switch (p->type)
    {
    case T_PRED:      return pred_combine (eval_pred (p->lhs), eval_pred (p->rhs), p->op);
    case T_EVAL_TERM: return eval_term (th, &p->term, vd, o); // fetch_peek_dbval
    case T_NOT_TERM:  return v_not (eval_pred (p->child));
    }
}

One evaluator, four call sites: key_pred (index), where_pred (scan), merge_pred/inner_pred (join), post-processing.

Source walkthrough — where to read next

Symbol names are the stable handle. Line numbers drift with refactors; git grep -n '<symbol>' src/ is your friend.

Each stage has a dedicated detail doc linked from cubrid-overview-query-processing.md.

Beyond CUBRID — research frontiers

The four-stage Selinger pipeline is universal, but every layer has alternative formulations in the literature and in modern engines.

CUBRID: System R + DP + Volcano + SHA-1 cache — a defensible position with a clear roadmap for where the engine could move.