The CPU’s role in databases

Databases spend 90% of hot-path time on the CPU: evaluating expressions, comparing keys, hashing, decompressing. Understanding the CPU execution model is the prerequisite for writing “cache-friendly” and “vectorization-friendly” code.

Instruction execution cycle

Each instruction roughly passes through four stages:

┌────────┐   ┌────────┐   ┌────────┐   ┌────────┐
│ Fetch  │ → │ Decode │ → │ Execute│ → │ Write  │
└────────┘   └────────┘   └────────┘   └────────┘
     ↑                                              │
     └────────────── next instruction ←─────────────┘

Pipeline

Modern CPUs do not wait for one instruction to finish before fetching the next; they overlap execution like a factory assembly line:

Cycle:  1   2   3   4   5   6
Instr1: IF  ID  EX  WB
Instr2:     IF  ID  EX  WB
Instr3:         IF  ID  EX  WB

The pipeline stalls when data dependencies (next instruction needs the result of the previous one) or control dependencies (branches) occur, dropping performance sharply. Expression evaluation full of branches (e.g. if (type == INT) ... else if (type == STR)) frequently breaks the pipeline.

Cache hierarchy and cache lines

The CPU does not fetch memory byte-by-byte; it loads entire cache lines (usually 64 bytes). The cache hierarchy forms a pyramid:

        ┌─────────┐  fastest / smallest
  L1    │ 32-64KB │  per-core, private, ~1ns
        ├─────────┤
  L2    │ 256KB-1MB│ per-core, private, ~4ns
        ├─────────┤
  L3    │  tens MB │ shared across cores, ~10ns
        ├─────────┤
  Mem   │  tens GB │  ~100ns
        └─────────┘  slowest / largest

The principle of locality is the key to performance:

• Temporal locality: recently accessed data is likely accessed again (loop variables)
• Spatial locality: after accessing an address, nearby addresses will be accessed too

In databases:

• Sequential scans beat random point lookups because the prefetcher can load adjacent cache lines ahead
• B+Trees are more cache-friendly than binary search trees: nodes are stored contiguously, so one cache line holds many keys

Branch prediction

The CPU predicts branch direction to execute ahead speculatively. A misprediction is expensive (flushes the pipeline, ~10-20 cycles lost).

if (row.is_deleted) continue;   // highly predictable: most rows not deleted → hits
if (value > threshold) ...       // random distribution → frequent mispredictions

Optimization: avoid data-dependent branches, or use conditional move (CMOV) instead of branches. Columnar engines often turn filtering into “bitmap + batch skip” to avoid per-row branching.

SIMD and vectorization

Modern CPUs provide Single Instruction Multiple Data (SIMD, e.g. AVX-512) instructions that process 16/32/64 values in one instruction:

Scalar:  for i: c[i] = a[i] + b[i]      // N instructions
Vector:  vadd(c, a, b)                   // 1 instruction handles 8 int32s

This is exactly why vectorized execution engines (DuckDB, ClickHouse, parts of PostgreSQL v17+) are several times faster than the per-row Volcano model: compare 8 values at once, with no branch in the loop.

Multi-core and hyper-threading

• Multi-core: physically multiple execution units that run different queries or partitions truly in parallel
• Hyper-threading (SMT): one physical core exposes two logical cores, switching threads to fill pipeline bubbles

Parallel caution: cores share L3 and memory bandwidth; too many threads can drop throughput due to memory bandwidth bottlenecks or lock contention (Amdahl’s law).

Implications for database design

References

• Computer Organization and Design, Patterson & Hennessy
• Agner Fog: CPU microarchitecture
• ClickHouse: Vectorized Execution