Vectorized Execution: Batches, Selection Vectors, and Push vs Pull

The classic query engine evaluates one tuple at a time: an operator’s next() returns a single row, its parent calls it in a loop, and each call goes through a virtual dispatch. That interface is simple, composable, and expensive. For a scan over a billion rows, the engine makes a billion virtual calls per operator in the plan, and each call does a handful of arithmetic operations on a few values that may not be in cache.

Vectorized execution keeps the operator interface but changes its granularity: next() returns a batch of a few hundred to a few thousand values, and the operator’s inner loop processes a whole array at once. The interpretation overhead is paid once per batch instead of once per tuple, and the array’s layout allows the compiler to generate tight loops over contiguous memory.

Why the batch size is what it is

A batch is sized so that its working set fits in L1 or L2 cache. If the batch is a column of 4-byte values, a thousand values occupy 4 KB, which fits in L1 on current x86 cores alongside a few other arrays. Too small a batch leaves the per-batch overhead dominant; too large a batch pushes the arrays into L2 and then into memory, and the inner loops lose their locality advantage.

The typical choice is around a thousand rows, with implementations varying between several hundred and a few thousand depending on the operator and the column width. A hash join’s build side may use a smaller batch to keep probe-side keys in cache alongside the table directory; a scan may use a larger one to amortize I/O.

The second design decision is the loop structure. A naive implementation calls a per-value function from inside the batch loop, which reintroduces the interpretation cost it was trying to remove. The efficient form inlines the operation into the loop body, with a switch on the operation outside the loop so that the branch predictor sees a single path.

// batch of int32 values, selection vector of qualifying positions
void filter_gt(const int32_t *col, size_t n, int32_t threshold,
               uint16_t *sel, size_t *out_n) {
    size_t k = 0;
    for (size_t i = 0; i < n; i++) {
        sel[k] = (uint16_t)i;
        k += (col[i] > threshold);   // branchless: keep or overwrite
    }
    *out_n = k;
}

The branchless form matters more than it looks. A predicate with unpredictable selectivity makes the branch mispredict on a large fraction of iterations, and a misprediction costs on the order of ten to twenty cycles. Turning the branch into an arithmetic update keeps the loop at a few cycles per value regardless of selectivity.

Selection vectors instead of copying

A filter that produces a subset of rows has two representations: copy the qualifying values into a new dense array, or keep the original array and record the positions that qualify. The second is a selection vector, and it is the standard choice because it avoids the copy.

The trade is visible at the next operator. A dense copy is contiguous and cache-friendly but costs a memory write per qualifying value and allocates a new buffer. A selection vector costs no copy but makes every downstream access indirect: the operator reads col[sel[i]] rather than col[i], which adds an indexed load and defeats simple vectorization unless the hardware gathers. For high selectivity, the copy wins; for low selectivity, the selection vector wins because it touches only the qualifying values.

Most engines use the selection vector and switch to a dense representation when the selection is nearly full, on the grounds that the indirect access is cheap when the indices are dense and the array is in cache. The threshold is empirical and varies by hardware, which is why implementations carry a tuning constant rather than a derivation.

The selection vector also carries type information. Its width bounds the batch size: a uint16_t selection caps batches at 65,536 rows, which is well above the practical batch size and therefore not a constraint. Some engines use uint32_t to remove the bound entirely.

Columnar layout and the operators it enables

Vectorization pairs naturally with columnar storage: a scan reads one column’s values contiguously, so the batch is already in the layout the operator wants. On row-oriented storage, the scan must transpose rows into columns, which costs a gather per batch and reduces the benefit, though the interpretation savings remain.

Columnar batches make several operators much simpler. A comparison between two columns is a loop over two contiguous arrays. An arithmetic expression over three columns is three arrays and one output array. A hash aggregate over a single grouping column can hash a contiguous array in a tight loop.

They also make null handling a separate concern. A column’s nulls are represented as a bitmap, one bit per value, and every operator must check it. Implementations either branch on the presence of any null in the batch and use a slow path when there is one, or propagate the null bitmap through the computation and mask the result at the end. The first is faster for the common no-null case and requires every operator to have two paths.

Push versus pull

The pull model has a parent call next() on a child until the child reports exhaustion. The push model inverts it: an operator receives a batch, processes it, and pushes the result to its parent. The plan is compiled into a chain of function calls, one per batch, and the innermost source drives the loop.

Push has two advantages. It eliminates the per-batch return-and-dispatch cost, because control flows through the whole pipeline for each batch rather than unwinding and re-entering at each operator. And it makes the pipeline’s state explicit: an operator’s per-batch state lives on the stack rather than in an object, which improves locality.

The cost is that push is harder to compose with operators that need to control their input’s consumption. A limit must signal its child to stop, which in a push model means returning a flag through every intermediate operator or throwing an exception-like control transfer. A sort must drain its input before emitting anything, so it becomes a pipeline breaker regardless of model.

Most engines that adopt push keep pull at blocking boundaries, or compile the whole pipeline and specialise the blocking operators. The compiled form is where push and vectorization converge: if the pipeline is a straight chain of batch operations, the compiler can inline all of them into one loop over the batch and remove the operator boundaries entirely.

Where vectorization does not help

A plan dominated by random I/O gains little. The batch machinery reduces CPU per tuple, but if each tuple requires a page fetch, the CPU is idle waiting for the device and the batch size does not change the number of fetches.

A plan with expensive per-tuple work, such as a user-defined function, gains only if the function itself can be called per batch. A scalar function that must be invoked once per value returns the engine to per-tuple dispatch inside the loop, and the overhead returns with it.

Short queries gain little and may lose: the batch machinery has a fixed setup cost, and a query returning ten rows does not amortize it. This is why engines with vectorized execution often keep a row-at-a-time path for small results, or set the batch size adaptively from the estimated cardinality.

The gains are largest for scans, filters, projections, and arithmetic over wide tables, which is the shape of most analytical queries. They are smallest for pointer-chasing operators such as index scans over a non-clustered index, where the work is memory latency rather than arithmetic. That asymmetry explains why vectorized engines dominate analytical workloads and are less compelling for transactional point lookups, whose cost is dominated by the access path rather than the operator loop, as described in physical operator selection.

The boundary with parallelism

Vectorized execution and parallelism are orthogonal and compose. Each worker runs its own batch pipeline over its fragment, and the exchange between fragments moves batches rather than rows. Moving a batch across a network or a shared-memory queue amortizes the per-message cost the same way the batch amortizes the per-call cost.

The composition has one interaction worth noting: batch size and worker count both affect cache behaviour. A plan with many workers each holding a thousand-row batch of several columns multiplies the working set by the worker count, and the aggregate may exceed the last-level cache even though each worker’s slice fits. Systems therefore reduce batch size at high parallelism, or accept the loss and rely on the per-worker L1 locality that remains. The partitioning decisions that create those fragments are covered in parallel execution and exchange operators.