Introduction

Every database query eventually becomes a loop. For decades, the dominant style was the Volcano model (also called iterator or tuple-at-a-time): each operator exposes a next() method that pulls exactly one row from the operator below it. A filter, a join, a projection — each asks the previous layer for one row, processes it, hands it up, and waits.

The model is elegant and easy to compose, but it has a hidden cost. Each next() call carries a function call, a pointer dereference, a type check, a branch, and a loop increment — overhead that has nothing to do with the actual data. When rows are tiny and the computation per row is small, that overhead can be larger than the real work itself.

Vectorized execution — pioneered by Peter Boncz and colleagues in MonetDB/X100 (published 2005) and now the foundation of systems like DuckDB, Velox, and Apache Arrow Compute — attacks this waste at its root. Instead of pulling one row at a time, each operator pulls a vector of 1,000–10,000 values and runs a tight, branch-free loop over the whole batch before yielding to the next operator. The per-call overhead is paid once per batch, not once per row, and the tight inner loop becomes small enough for the CPU to keep in its instruction cache, prefetch data automatically, and — critically — apply SIMD instructions that process multiple values in a single clock cycle.

The result is throughput that can be 10 to 100 times higher than a comparable row-at-a-time engine on the same analytical query.

Try It

Below is a simulation of two execution strategies processing a column of integers and summing the ones that pass a filter. Both do the same arithmetic — the difference is all in how much overhead surrounds each value.

<!-- Controls for row count and batch size -->
<div class="controls">
  <label>
    Rows:
    <input id="rowCount" type="range" min="1000" max="100000" step="1000" value="50000">
    <span id="rowCountVal">50000</span>
  </label>
  <label>
    Batch size:
    <input id="batchSize" type="range" min="1" max="4096" step="1" value="1">
    <span id="batchSizeVal">1</span>
  </label>
</div>
<div class="chart-area">
  <canvas id="chart" width="560" height="220"></canvas>
</div>
<div class="metrics" id="metrics"></div>
<div class="btns">
  <button id="runBtn" type="button">Run simulation</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<p class="note">Simulation model: each operator call costs 80 ns of fixed overhead; each value costs 4 ns of real work. Batch size 1 = pure tuple-at-a-time. Higher batch sizes amortize the overhead across more values.</p>

/* Vectorized execution demo styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .7rem; }
label { display: flex; align-items: center; gap: .5rem; font-size: .88rem; color: #444; flex-wrap: wrap; }
input[type=range] { flex: 1; min-width: 120px; accent-color: #1d3557; }
span { font-weight: 700; color: #1d3557; min-width: 3.5rem; }
.chart-area { background: #f5f7fa; border: 1px solid #dde2e8; border-radius: 10px; padding: .5rem; margin-bottom: .7rem; }
canvas { display: block; max-width: 100%; }
.metrics { display: flex; gap: 1.2rem; flex-wrap: wrap; margin-bottom: .6rem; }
.metric { background: #e8eef3; border-radius: 8px; padding: .45rem .8rem; font-size: .85rem; }
.metric .val { font-weight: 700; font-size: 1.05rem; color: #1d3557; display: block; }
.metric .lbl { color: #666; font-size: .78rem; }
.metric.vec .val { color: #0a7d33; }
.metric.ratio .val { color: #b84800; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.note { font-size: .8rem; color: #666; margin: 0; line-height: 1.4; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Cost model: every operator call pays a fixed overhead (function dispatch,
// null-check, type dispatch, loop setup). Real work per value is much smaller.

const OVERHEAD_PER_CALL_NS = 80;  // fixed overhead per operator call, in nanoseconds
const WORK_PER_VALUE_NS   = 4;    // actual computation per value, in nanoseconds

const rowCountSlider  = document.getElementById('rowCount');
const rowCountVal     = document.getElementById('rowCountVal');
const batchSizeSlider = document.getElementById('batchSize');
const batchSizeVal    = document.getElementById('batchSizeVal');

rowCountSlider.addEventListener('input', () => { rowCountVal.textContent = Number(rowCountSlider.value).toLocaleString(); });
batchSizeSlider.addEventListener('input', () => { batchSizeVal.textContent = Number(batchSizeSlider.value).toLocaleString(); });

// Simulate both strategies: tuple-at-a-time (batchSize=1) vs vectorized (batchSize=k)
function simulate(rows, batchSize) {
  const calls = Math.ceil(rows / batchSize);
  const overheadNs  = calls * OVERHEAD_PER_CALL_NS;
  const workNs      = rows  * WORK_PER_VALUE_NS;
  const totalNs     = overheadNs + workNs;
  const overheadPct = (overheadNs / totalNs) * 100;
  return { totalNs, overheadNs, workNs, overheadPct };
}

// Draw two stacked bars comparing overhead vs work for both strategies
function draw(tupleRes, vecRes) {
  const canvas = document.getElementById('chart');
  const ctx    = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  const barW  = 80;
  const maxNs = Math.max(tupleRes.totalNs, vecRes.totalNs) * 1.1;
  const scale = (H - 60) / maxNs;

  function drawBar(x, res, label, colorWork, colorOverhead) {
    const wH = res.workNs * scale;
    const oH = res.overheadNs * scale;
    const base = H - 40;
    // draw overhead segment (top portion of bar)
    ctx.fillStyle = colorOverhead;
    ctx.fillRect(x, base - wH - oH, barW, oH);
    // draw work segment (bottom portion of bar)
    ctx.fillStyle = colorWork;
    ctx.fillRect(x, base - wH, barW, wH);
    ctx.fillStyle = '#333';
    ctx.font = '12px system-ui';
    ctx.textAlign = 'center';
    ctx.fillText(label, x + barW / 2, H - 20);
    const ms = (res.totalNs / 1e6).toFixed(1);
    ctx.fillText(ms + ' ms', x + barW / 2, base - wH - oH - 6);
  }

  const gap = (W - 2 * barW) / 3;
  drawBar(gap,           tupleRes, 'Tuple-at-a-time', '#4a90d9', '#e63946');
  drawBar(gap * 2 + barW, vecRes,  'Vectorized',   '#4a90d9', '#f4a261');

  // draw legend in top-right corner
  ctx.font = '11px system-ui';
  ctx.textAlign = 'left';
  ctx.fillStyle = '#4a90d9'; ctx.fillRect(W - 160, 10, 14, 14); ctx.fillStyle = '#333'; ctx.fillText('Real work',     W - 142, 22);
  ctx.fillStyle = '#e63946'; ctx.fillRect(W - 160, 30, 14, 14); ctx.fillStyle = '#333'; ctx.fillText('Overhead (tuple)', W - 142, 42);
  ctx.fillStyle = '#f4a261'; ctx.fillRect(W - 160, 50, 14, 14); ctx.fillStyle = '#333'; ctx.fillText('Overhead (vector)', W - 142, 62);
}

function run() {
  const rows      = parseInt(rowCountSlider.value);
  const batchSize = parseInt(batchSizeSlider.value);

  const tupleRes = simulate(rows, 1);          // tuple-at-a-time always uses batch size 1
  const vecRes   = simulate(rows, batchSize);

  draw(tupleRes, vecRes);

  const speedup = tupleRes.totalNs / vecRes.totalNs;
  const metrics = document.getElementById('metrics');
  metrics.innerHTML = `
    <div class="metric">
      <span class="val">${(tupleRes.totalNs / 1e6).toFixed(1)} ms</span>
      <span class="lbl">tuple-at-a-time</span>
    </div>
    <div class="metric vec">
      <span class="val">${(vecRes.totalNs / 1e6).toFixed(1)} ms</span>
      <span class="lbl">${i18nFmt('vectorized (batch=%b%)', { b: batchSize.toLocaleString() })}</span>
    </div>
    <div class="metric ratio">
      <span class="val">${speedup.toFixed(1)}×</span>
      <span class="lbl">speedup</span>
    </div>
    <div class="metric">
      <span class="val">${vecRes.overheadPct.toFixed(1)}%</span>
      <span class="lbl">overhead fraction (vectorized)</span>
    </div>
  `;
}

document.getElementById('runBtn').addEventListener('click', run);
document.getElementById('resetBtn').addEventListener('click', () => {
  rowCountSlider.value  = 50000;
  batchSizeSlider.value = 1;
  rowCountVal.textContent  = '50,000';
  batchSizeVal.textContent = '1';
  document.getElementById('metrics').innerHTML = '';
  const canvas = document.getElementById('chart');
  canvas.getContext('2d').clearRect(0, 0, canvas.width, canvas.height);
});

// Run once on load so the chart appears immediately
run();
Result
Console

Slide the batch size from 1 (pure tuple-at-a-time) upward and watch the overhead fraction collapse. At batch size 1, the per-row overhead from the dispatch loop, function calls, and type checks dwarfs the real computation. By batch size 512 or more, that overhead is amortized across the whole vector and the engine is spending nearly all its time on actual data work.

The Real Performance Story

The speedup comes from three compounding effects:

1. Overhead amortization. Each operator call in the tuple-at-a-time Volcano model carries fixed overhead: a virtual function call (or indirect branch), iterator state updates, null checks, and type dispatch. If processing one value takes 1 ns of real work but 5 ns of overhead, the engine is 83% waste. With vectors of size kk, the overhead is paid once for kk values, so the waste fraction drops to roughly OO+k⋅W\frac{O}{O + k \cdot W} where OO is the per-call overhead and WW is the work per value. At k=1024k = 1024, overhead becomes negligible.

2. Cache friendliness. Column-oriented storage keeps all values of one attribute contiguous in memory. A vectorized scan reads a long contiguous run of integers (or floats, or dates) — every cache line it fetches is fully used. Row-oriented storage interleaves attributes; fetching one column wastes most of each cache line on attributes the query never touches.

3. SIMD acceleration. When the inner loop is tight and branch-free, modern compilers and CPUs apply Single Instruction, Multiple Data instructions: AVX2 can add 8 × 64-bit integers in one cycle, AVX-512 can do 8 × 64-bit in one cycle with wider registers. A vectorized engine whose inner loop is auto-vectorized effectively multiplies its arithmetic throughput by the SIMD width (4–16×) on top of the amortization gain.

These gains interact: amortization cleans up the loop, cache friendliness ensures operands arrive before the CPU stalls, and SIMD multiplies what the CPU can do per cycle. The combination is why systems like DuckDB can scan billions of rows per second on a laptop.

The tradeoff is that vectorized execution complicates materialization: intermediate results between operators must now be buffered in vector-sized chunks, increasing working-set memory. Batch size is therefore a tuning knob — too small and overhead dominates, too large and the vector spills out of L1/L2 cache, negating the cache benefit.

Where It Matters

The vectorized model is not just a database optimization — it is the design principle behind a whole ecosystem of high-performance data tools:

  • Analytical databases (OLAP): DuckDB, ClickHouse, Snowflake, and BigQuery all use vectorized or compiled execution for their scan-heavy analytical workloads. MonetDB/X100 (2005) was the proof of concept; every major analytical engine built since has adopted the idea.
  • Apache Arrow: the columnar in-memory format and its Compute library define a standard representation for vectors that lets different systems share data without copying — Pandas, Spark, DuckDB, and Polars all interoperate through it.
  • Machine learning runtimes: NumPy, PyTorch, and TensorFlow all execute element-wise operations as tight C/CUDA loops over contiguous arrays. The batched forward pass through a neural network is vectorized execution applied to linear algebra.
  • Compilers and query compilation: some engines go one step further and compile queries to native machine code (LLVM IR) so the inner loop contains no interpreter overhead at all — this is the "compiled execution" approach used by HyPer and Databricks Photon. Vectorized and compiled execution are complementary and are often combined.
  • Scientific computing: NumPy ufuncs, MATLAB's matrix operations, and Julia's broadcast operator all rely on the same principle: avoid Python/Julia dispatch per element; run C/Fortran loops over whole arrays.

The common thread is that homogeneous data processed uniformly — all integers, all floats, all dates — lets the machine run at its theoretical peak, free of the branching, polymorphism, and dispatch overhead that general-purpose interpreters pay. See also query optimization for the planning layer that decides which operations to vectorize and in what order.

Conclusion

The Volcano model's elegance came at a price: one virtual call per row, every row, millions of times a second. Vectorized execution tears out that per-row scaffolding and replaces it with tight, predictable loops over homogeneous chunks of a column — loops the CPU can prefetch, cache, and accelerate with SIMD.

The insight is deceptively simple: pay overhead once per batch, not once per value. But the compounding effects — amortized dispatch, cache-line efficiency, and SIMD — turn a modest bookkeeping improvement into a 10–100× throughput gain on analytical workloads.

That shift in thinking, from pulling single rows to pushing vectors, is now the foundation of every fast analytical engine, from DuckDB on a laptop to Snowflake on a cluster. The next time a query over a billion rows returns in seconds, vectorized execution is almost certainly doing the work. Explore query optimization to see how the planner decides which plan to hand to the vectorized engine.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/vectorized-execution/Content licensed under CC BY-NC 4.0.