Vectorized execution

Deep dive

How it works

Parts:

• batch — column vectors of about 1-2K values, an optional selection vector and a length
• operator — scan, filter, project, aggregate; next() -> Option<Batch>
• primitive — tiny type-specialized loop, e.g. select_lt_i64_col_const
• selection vector — indices of qualifying rows, instead of copying data
• pipeline breaker — hash build or sort; materializes its input
• morsel scheduler — hands input chunks to threads that run a whole pipeline

Scan ──batch(cols, sel=None)──► Filter ──batch(cols, sel=[3,9,…])──► Project ──► HashAgg
       one virtual call per 2048 rows; each op = loops over primitive kernels

1. Interface: next() -> Option<Batch>. A batch has column vectors, an optional selection vector and a length.
2. Primitives: one tiny function per (operation, type, layout), e.g. select_lt_i64_col_const, generated by macros or templates. No per-value dispatch.
3. Filter: run the primitive over the batch and write a selection vector. Later operators process only the selected indices, or compact them when the selection becomes sparse.
4. Projection / arithmetic: when most rows are selected, compute over all rows and ignore the unselected results. A full dense loop vectorizes and beats gathering.
5. Pipeline breakers (hash build, sort) materialize their input. The rest streams batch by batch, and with morsel-driven parallelism each thread takes chunks of input (morsels) and runs the whole pipeline on them.

Code

pub const VEC: usize = 2048;

pub struct Batch { pub cols: Vec<Vec<i64>>, pub sel: Option<Vec<u32>> }

pub trait Operator { fn next(&mut self) -> Option<Batch>; } // one call per batch, not per row

/// Branch-free: always write the index; advance the cursor only if the predicate held.
pub fn select_lt(col: &[i64], k: i64, sel_in: Option<&[u32]>, out: &mut Vec<u32>) {
    out.clear();
    out.resize(col.len(), 0);
    let mut n = 0;
    match sel_in {
        None => for (i, &v) in col.iter().enumerate() { out[n] = i as u32; n += (v < k) as usize; },
        Some(s) => for &i in s { out[n] = i; n += (col[i as usize] < k) as usize; },
    }
    out.truncate(n);
}

/// Dense kernel: no branches and no gathers, so it compiles to SIMD.
pub fn mul(a: &[i64], b: &[i64], out: &mut [i64]) {
    for ((o, &x), &y) in out.iter_mut().zip(a).zip(b) { *o = x.wrapping_mul(y); }
}

pub struct Scan<'a> { pub cols: Vec<&'a [i64]>, pub pos: usize }
impl Operator for Scan<'_> {
    fn next(&mut self) -> Option<Batch> {
        let n = self.cols[0].len();
        if self.pos >= n { return None; }
        let end = (self.pos + VEC).min(n);
        let cols = self.cols.iter().map(|c| c[self.pos..end].to_vec()).collect(); // real scans decode here
        self.pos = end;
        Some(Batch { cols, sel: None })
    }
}

pub struct Filter<C: Operator> { pub child: C, pub col: usize, pub k: i64 }
impl<C: Operator> Operator for Filter<C> {
    fn next(&mut self) -> Option<Batch> {
        loop {
            let mut b = self.child.next()?;
            let mut out = Vec::with_capacity(VEC);
            select_lt(&b.cols[self.col], self.k, b.sel.as_deref(), &mut out);
            if out.is_empty() { continue; } // never pass empty batches upstream
            b.sel = Some(out);
            return Some(b);
        }
    }
}

/// SELECT sum(c0 * c1) over the child's selected rows.
pub fn sum_product<C: Operator>(mut op: C) -> i64 {
    let mut prod = vec![0i64; VEC];
    let mut total = 0i64;
    while let Some(b) = op.next() {
        let (a, c) = (&b.cols[0], &b.cols[1]);
        match &b.sel {
            Some(s) if s.len() * 4 < a.len() => { // sparse: touch only selected rows
                for &i in s { total = total.wrapping_add(a[i as usize].wrapping_mul(c[i as usize])); }
            }
            sel => { // dense: SIMD over every row, then pick the selected results
                mul(a, c, &mut prod[..a.len()]);
                match sel {
                    Some(s) => for &i in s { total = total.wrapping_add(prod[i as usize]); },
                    None => for &p in &prod[..a.len()] { total = total.wrapping_add(p); },
                }
            }
        }
    }
    total
}

Usage: sum_product(Filter { child: Scan { cols: vec![&price, &qty], pos: 0 }, col: 1, k: 10 }) computes SELECT sum(price*qty) WHERE qty < 10.

Complexity and constants

• Interpretation overhead: about 1 virtual call per 2048 rows instead of several per row. Simple primitives (add, compare) then cost about 0.5-2 cycles per value with SIMD.
• Branchy filter at 50 % selectivity: about half the branches mispredict, roughly 8-10 cycles per row on average. Branch-free: about 1-2 cycles per row at any selectivity.
• Working set per operator: columns × 2048 × 8 B. With 4-8 columns that is 64-128 KiB, inside L2.
• MonetDB/X100 reported one to two orders of magnitude over tuple-at-a-time engines on TPC-H Q1.

Efficiency

• Cost: about 1 virtual call per 2048 rows instead of several per row; simple primitives (add, compare) cost about 0.5-2 cycles per value with SIMD. A branchy filter at 50 % selectivity costs roughly 8-10 cycles per row, a branch-free one 1-2. Working set per operator: columns × 2048 × 8 B, 64-128 KiB for 4-8 columns. Bound: CPU and cache.
• Levers:
  • batch of about 1-2K values per column — dispatch amortized, working set in L2; MonetDB/X100 reported one to two orders of magnitude over tuple-at-a-time on TPC-H Q1 — analytic scans
  • selection vectors or compute-then-mask — 1-2 cycles per row at any selectivity — unselective predicates
  • validity bitmaps, constant and dictionary vectors never expanded — SIMD-friendly data — nullable and low-cardinality columns
  • hash a whole batch, prefetch buckets, then probe — hides memory latency (order of) — joins and aggregations
  • Volcano iterator or compiled pipelines — Kersten et al. found compiled and vectorized comparable, each ahead on different queries — OLTP point queries, or compile-heavy plans
• Naive → standard → state of the art:
  • Volcano, one next() per tuple · hundreds of instructions per row
  • vectorized batches with selection vectors · about 0.5-2 cycles per value
  • morsel-parallel pipelines over SIMD kernels · cores scale on batch-resident data

Implementation notes

• Kernel generation: macros or generics per (type × operation × constant/column) combination. The combinations multiply fast: mature engines instantiate hundreds to thousands of kernels.
• Nulls: a validity bitmap per vector. Compute on all values, then AND the validity masks, rather than branching per value.
• Strings: 16-byte "German strings" (length + 4-byte prefix + pointer or inline) make most comparisons decide on the prefix without dereferencing (Umbra, DuckDB, Velox).
• Constant and dictionary vectors: represent a constant or a dictionary-encoded column without expanding it. A kernel on a constant runs once.
• Adaptive kernels: switch between selection-vector and dense computation at runtime based on observed selectivity, as in the code.
• Hash tables in vectorized form: hash a whole batch, prefetch the buckets, then probe. This hides cache-miss latency (hash join).

Pitfalls

• Batches much larger than L2 lose the cache benefit (column-at-a-time MonetDB materialized whole columns between operators; X100 fixed this with vectors).
• Calling through a function pointer per value inside a "vectorized" loop puts the interpretation overhead back.
• Bounds checks and aliasing can block auto-vectorization. Use iterators/zip or chunks_exact, and check the assembly.
• Forgetting the selection vector downstream processes filtered-out rows. Always test with selective filters.
• Overflow semantics: SIMD loops want wrapping arithmetic, while SQL wants overflow errors. Check flags per batch, not per value.

Variants and alternatives

In production

• Analytics databases: DuckDB, ClickHouse, Snowflake, Vectorwise/Actian Vector, SQL Server batch mode.
• Lakehouse and query-engine libraries: Velox (Meta; Presto C++), Apache DataFusion, Databricks Photon.
• Dataframes: Polars.

Implementations

Sources

• P. Boncz, M. Zukowski, N. Nes, MonetDB/X100: Hyper-Pipelining Query Execution, CIDR, 2005. pdf
• G. Graefe, Volcano—An Extensible and Parallel Query Evaluation System, IEEE TKDE, 1994. paper
• T. Neumann, Efficiently Compiling Efficient Query Plans for Modern Hardware, VLDB, 2011. paper
• T. Kersten et al., Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask, VLDB, 2018. paper · code
• V. Leis, P. Boncz, A. Kemper, T. Neumann, Morsel-Driven Parallelism, SIGMOD, 2014. paper
• K. Ross, Selection Conditions in Main Memory, ACM TODS, 2004. paper