What is vectorized query execution, and why does processing a batch of rows per operator call typically run several times faster than processing one row per call?
answer
- batch ~1024 rows, column-wise arrays
- selection vector instead of per-row branch
- one call amortized over the batch
- batch sized to fit L1/L2
- SIMD needs contiguous typed columns
basics
~20 sEach operator call returns a batch — commonly around 1024 rows held column-wise — instead of one row. Per-call dispatch is amortized over the batch, and the inner loops become tight, branch-free, cache-resident and SIMD-friendly, so far more cycles go into real work.
solid answer
~50 sVectorized execution keeps the operator tree but changes the granularity: an operator call yields a *vector* of values — typically 1024 to 4096 rows, stored one array per column — rather than a single tuple. Three effects compound: 1. **Amortized dispatch.** One indirect call now covers a thousand rows instead of one. 2. **Tight primitive loops.** A filter becomes a loop over an integer array with no per-row function pointer, so the compiler can unroll it and emit SIMD instructions; results are recorded in a selection vector or bitmap rather than by branching per row. 3. **Cache residency.** Batch size is chosen so all live vectors fit in L1/L2, so data is touched once per pass without falling back to memory. The costs are real: memory per operator grows from one tuple to several batches, latency is now quantized to a batch, null handling needs bitmaps, and single-row OLTP work gains nothing. It is the standard design for analytical engines and pointless for point lookups.
code
text · 15 lines// row-at-a-time: one call + one branch per row
next(): t = child.next(); if (eval(pred,t)) return t; ...
// vectorized: one call per batch, branch-free inner loop
int filter_gt_i32(const int32_t* col, int32_t k,
const uint16_t* in_sel, int n,
uint16_t* out_sel) {
int m = 0;
for (int i = 0; i < n; i++) {
uint16_t p = in_sel[i];
out_sel[m] = p;
m += (col[p] > k); // no branch; auto-vectorizable
}
return m; // number of surviving rows
}go deeper
Know the one-line version: operators pass batches of rows instead of single rows, which is much faster on large scans.
Explain the batch size, the columnar layout, amortized dispatch, and the branch-free selection vector — and that pipelining is preserved.
Discuss cache sizing of the batch, selection-vector compaction after selective filters, memory-per-operator under concurrency, and why OLTP gains nothing.
Position it as one of two answers to interpretation overhead, with compilation as the other, and tie the choice to workload shape, engineering cost and latency budget.
## The starting point In the classic iterator model an operator returns one tuple per call. That costs an indirect call per operator level per row, plus interpreting the expression tree for each row, plus instruction-cache pressure from hopping between operator code paths on every single row. On analytical scans this overhead can exceed the useful work by an order of magnitude. ## The change vectorization makes Vectorized (batch-at-a-time) execution keeps everything structurally familiar — still a tree of operators, still demand-driven calls — and changes only *how much* travels per call. A call returns a **vector**: a fixed-size chunk of rows, typically 1024–4096, stored **column-wise**, one contiguous array per column, with a separate null bitmap per column. Inside an operator the work is no longer "process this tuple" but "run this primitive over this array". A primitive is a tiny specialized loop such as `less_than_int32_const(int32* col, int32 constant, sel_t* out)`. ## Why it is faster — four compounding reasons **1. Amortized dispatch.** One virtual call now serves a whole batch. Per-row call overhead drops by roughly the batch size, which alone removes most of the interpretation tax. **2. Branch-free inner loops.** Instead of `if (predicate) return row`, a vectorized filter writes qualifying positions into a *selection vector* (an array of indices) or flips bits in a bitmap. Downstream operators then process only the selected positions. Removing the unpredictable per-row branch matters as much as removing the call. **3. SIMD and compiler optimization.** A loop over a typed contiguous array with no calls and no branches is exactly what an optimizing compiler auto-vectorizes: 4, 8 or 16 values per instruction, plus unrolling and out-of-order overlap. This only works because the layout is columnar — the values being compared are adjacent in memory. **4. Cache behaviour.** The batch size is not arbitrary: it is picked so that the vectors an operator is working on fit comfortably in L1/L2. Small enough to stay cache-resident, large enough to amortize the call. This is why 1024-ish, not 1 and not 10 million, is the sweet spot: full materialization would push every intermediate through main memory. ## What it does not change Vectorization is orthogonal to plan shape. Join order, index choice and cardinality estimation are unaffected. Blocking operators are still blocking — a sort still consumes all input before emitting. Pipelining is preserved; the pipeline unit is simply a batch instead of a row, so memory is O(batch × operators), still bounded and tiny compared with materializing whole intermediates. ## Costs and limits - **Memory per operator** rises from one tuple to several arrays; with high concurrency that multiplies. - **Latency granularity.** Nothing leaves an operator until its batch is filled or its input ends, so time-to-first-row is slightly worse. For interactive OLTP with single-row answers this is pure loss. - **Implementation cost.** You need a primitive per (operation × type) combination; the executable size and the code you must maintain grow quickly, which is why engines generate these primitives from templates. - **Selection-vector bookkeeping.** After a very selective filter, later operators either process a sparse batch (wasting the density benefit) or must compact it (a copy). Engines heuristically decide when to compact. - **No help for point queries.** A primary-key lookup returning one row gets none of the benefit and pays the batch machinery. ## Relationship to columnar storage Vectorization is *enabled* but not *required* by columnar storage. Reading only the referenced columns from a column store hands the executor contiguous typed arrays for free, so column stores and vectorized executors are usually found together. A row store can still vectorize by transposing rows into column vectors after the scan — it pays a copy but keeps the tight inner loops. ## How it compares to compilation The two well-known answers to interpretation overhead are vectorization (bigger units, precompiled primitives) and just-in-time compilation (fuse operators into one generated loop so tuples stay in registers). Vectorization keeps the code precompiled and debuggable with no compile-time latency; compilation removes the intermediate vectors entirely. Published comparisons put them in the same performance league on analytical queries, with compilation favoured on compute-heavy expression work and vectorization favoured on memory-bound scans and short queries where compile time would not amortize.
- Why is the batch size usually around 1024 rather than a much larger number?The batch must be big enough to amortize the per-call dispatch but small enough that the vectors an operator touches stay in L1/L2 cache. Push it to millions of rows and every intermediate round-trips through main memory, which is exactly the full-materialization cost vectorization is trying to avoid. Around a thousand rows the dispatch cost is already negligible, so growing further buys nothing and starts costing cache misses.
- Does vectorized execution require columnar storage?No, but they fit together. Vectorization needs contiguous typed arrays for the inner loops to be SIMD-friendly, which a column store provides directly and cheaply for exactly the referenced columns. A row store can vectorize by transposing rows into column vectors after the scan; it pays that copy but still gets the amortized dispatch and tight loops.
Instead of asking the warehouse for one item at a time, you send a pallet order: the same paperwork now covers a thousand items, and the forklift can move them in one sweep.
saying these in an interview costs you the question
- Claiming vectorization means running the query on the GPU or on multiple cores — it is about batch granularity within one thread, and is orthogonal to parallelism.
- Saying vectorization materializes the full intermediate result; the whole point is a cache-sized batch, not the whole relation.
- Assuming vectorization makes OLTP point lookups faster.
- Believing it changes the plan or the optimizer's decisions.
- Thinking the speedup is purely SIMD; the amortized dispatch and removed branches usually contribute as much or more.