10.1 Vectorized Execution, Selection Vectors, and Data Representation

Vectorized execution begins as an engine interface: operators process batches of typed values at once, rather than one row at a time. This approach reduces scheduling overhead, improves cache locality, and exposes compact loops to compilers and SIMD instructions. However, batch processing alone does not guarantee the use of any specific SIMD instruction.

Learning Objectives

• Distinguish between vectorized execution and hardware SIMD;
• Understand the concepts of DataChunk, column vector, validity mask, and selection vector;
• Compare flat, constant, and dictionary/sequence data representations;
• Analyze the batch processing paths for filter, projection, and aggregate operations;
• Balance cache efficiency, latency, and memory usage when selecting batch size.

Row-at-a-time vs. batch-at-a-time

// row-at-a-time
bool next(Row& row);

// batch-at-a-time
bool next_batch(Batch& batch);

If a batch contains 2048 rows, a single operator call can amortize 2048 scheduling invocations; typed arrays also simplify the inner loop.

Batch
  column item_type_id: int32[capacity]
  column value_cents:  int64[capacity]
  validity bitmaps
  cardinality
  optional selection/index indirection

Here, the batch is a horizontal slice of rows, composed of multiple column vectors of equal length.

Why Vectors Are Well-Suited for CPUs

• Contiguous values reduce pointer chasing;
• Type dispatch is applied per batch or kernel rather than per value;
• Validity can be efficiently batch-processed using bitmasks;
• Filters generate position and mask data, allowing subsequent operators to avoid unnecessary copies;
• Compact loops are more amenable to automatic vectorization;
• Prefetching and cache line behavior become more predictable.

String values, nested values, user-defined functions (UDFs), and hash-table random access may still disrupt contiguity.

Selection vector

Filter value_cents >= 50000:

values:    [12000, 8000, 95000, 180000, 5000]
selected:  [2, 3]

Subsequent operators can iterate over the selected positions without immediately compacting and copying each column.

std::size_t select_ge(
    const std::int64_t* values,
    const std::uint64_t* validity,
    std::size_t count,
    std::int64_t threshold,
    std::uint32_t* selected);

Here selectivity means the fraction of input rows that match. At a high matching fraction, indirect gathers or branches may cost more than a dense loop. The engine can choose among selection vector, bitmask, or physical compaction strategies accordingly.

NULL validity

SQL predicates evaluate to UNKNOWN when encountering NULL values. The filter only retains rows where the condition is TRUE:

validity: [1, 0, 1, 1]
values:   [9, ?, 3, 12]
value>5:  [T, U, F, T]
selected: [0, 3]

The kernel can first compute a comparison mask and then AND it with the validity mask. Three-valued logic for AND, OR, and NOT operations is more complex, and NULLs cannot be uniformly treated as false before being used in any expression.

Multiple vector representations

Flat

A contiguous array of values plus a validity mask, simplest to feed into SIMD kernels.

Constant

A single value logically repeated N times. Functions can compute it once and reuse the result; however, care must be taken with NULL or volatile function semantics.

Dictionary

base values: [device, spare_part, consumable]
indices:     [0, 0, 1, 2, 0]

Maintains an encoded and filtered view, avoiding immediate string materialization. Nested dictionary or selection indirection can increase lookup overhead; the engine may flatten or normalize such structures.

Sequence

start + row_index × increment, well-suited for row IDs and similar patterns. Certain predicates can evaluate matching intervals directly, without generating each element individually.

Run-length / compressed

Aggregations and filters can operate directly on runs. For example, COUNT performs cumulative addition based on run lengths. The benefit of compressed execution depends on whether the operator can understand the representation.

DuckDB's Precise Positioning

According to the DuckDB official documentation, vectorized execution is a core feature. Vector represents a container for column values, while DataChunk denotes a set of vectors. It supports various formats (including flat, constant, dictionary, and sequence) and provides a unified vector format that gives generic operators a consistent view.

The commonly cited standard vector size in the current documentation is 2048, but this is merely an implementation parameter, not a requirement that all vector engines must use a size of 2048. When calling public APIs, the vector size can be queried; extensions should not hardcode this value.

• DuckDB Execution Format
• DuckDB Internals Overview

Batch filter

This is a partial C++17 function implementation. The caller supplies count input values, at least ceil(count/64) validity words, and count output-index slots, all valid throughout the call. A 32-bit selection index requires a count limit to prevent silent truncation:

#include <cstddef>
#include <cstdint>
#include <limits>
#include <stdexcept>

std::size_t filter_values(
    const std::int64_t* values,
    const std::uint64_t* validity_words,
    std::size_t count,
    std::int64_t threshold,
    std::uint32_t* selected) {

    if (count > std::numeric_limits<std::uint32_t>::max()) {
        throw std::length_error("selection index exceeds uint32_t");
    }
    std::size_t output = 0;
    for (std::size_t i = 0; i < count; ++i) {
        const bool valid =
            (validity_words[i / 64] >> (i % 64)) & std::uint64_t{1};
        if (valid && values[i] >= threshold) {
            selected[output++] = static_cast<std::uint32_t>(i);
        }
    }
    return output;
}

Check values={9,0,3,12}, validity_words={0b1101}, and threshold=5: the function should return 2 with {0,3} in the first two output slots. Position 1 contains the placeholder 0 but has a cleared validity bit and does not participate. Also test counts 0, 64, and 65 across bitmap-word boundaries.

The compiler may vectorize comparisons, but it does not guarantee efficient vectorization of sparse position compaction. AVX-512 supports mask and compress operations, while AVX2 typically requires lookup or permutation operations or scalar extraction; the engine might instead choose to retain the bitmask directly.

Batch aggregate

struct SumState {
    __int128 total = 0;
    std::uint64_t non_null_count = 0;
};

__int128 is a GCC/Clang extension on supported targets, not a standard C++17 type; other compilers need an equivalent wide-integer implementation. With non_null_count=0, SQL SUM normally returns NULL rather than the initial 0. An integer accumulator still needs an overflow policy. The SQL SUM return type is determined by database rules and cannot be replaced with int64_t wraparound behavior.

AVG typically maintains (sum, count); NULL values do not increment the count. Parallel aggregates require merging of partial states and must preserve decimal or floating-point semantics.

Hash and Vectorization

Batch hash join/aggregation can:

1. Compute hashes in bulk;
2. Prefetch candidate buckets;
3. Probe in bulk;
4. Generate match selection;
5. Materialize payload later.

However, hash table access is data-dependent and random, often limited by memory latency. Faster hash computation via SIMD does not guarantee proportional speedup for the entire join operation; issues such as collisions, skew, and table resizing must still be addressed.

Batch size

Too small: operator-call amortization is insufficient, and SIMD setup/dispatch overhead dominates.

Too large:

• working set exceeds L1/L2 cache capacity;
• memory overhead for selection, validity, and intermediate data increases;
• first-row and cancellation latency rise;
• skewed operators monopolize threads for longer durations;
• cache pollution occurs.

An optimal batch size depends on row width, kernel design, cache hierarchy, instruction set architecture (ISA), and engine pipeline characteristics. Fixing batch sizes at 1024 or 2048 is merely a pragmatic implementation choice, not a hardware law.

Late materialization

A vector engine can first process predicate keys and selections, then retrieve the output columns. However, for compressed files, reading at sparse positions may still require decoding entire pages. For row-store formats, locating additional columns might involve random data gathering.

The optimizer must compare the sequential work of early materialization with the indirection and gathering overhead of late materialization. A low matching fraction generally favors late materialization, while a high fraction may favor dense processing.

Lesson Summary

Vectorized execution improves performance by batching operations through typed representations, reducing overhead in scheduling and materialization. Selections, constant/dictionary vectors, and validity masks help eliminate unnecessary work, but ultimate performance is still constrained by cache behavior, branch prediction, gather operations, and memory bandwidth. In the next lesson, we move into hardware SIMD, where we’ll write safe remainder handling, runtime dispatch logic, and correct SQL numeric semantics.