Introduction: Why Vectorized Query Execution Engines Matter Now
In modern analytics systems, the classic iterator model (“one row at a time”) simply can’t keep up with the volume and complexity of data I see in real-world warehouses. Every row incurs virtual function calls, branching, and cache misses, which adds a lot of overhead when you’re scanning millions or billions of rows.
A vectorized query execution engine flips that model: instead of processing a single row, it processes a batch (or vector) of values per operator call. In my experience, that single change lets the CPU’s caches, branch predictor, and SIMD instructions finally do their job, often yielding multi‑x speedups on the same hardware.
In this step‑by‑step tutorial, we’ll go from the basic ideas of columnar batches to a minimal but realistic vectorized pipeline, so by the end you’ll have a working mental (and code) model of how engines like DuckDB or modern column stores execute queries at high speed. If you want a deeper theoretical background alongside this hands‑on walkthrough, I recommend also reading Columnar Databases and Vectorization – InfoQ.
Prerequisites and Mental Model for a Vectorized Query Execution Engine
What You Should Already Know
To follow along, you should be comfortable with a systems language like C++ or Rust, basic SQL (SELECT, WHERE, JOIN, GROUP BY), and how a traditional iterator-based engine works (the classic next() per row model). In my own work on execution engines, I’ve also found that a rough feel for CPU caches, memory layout, and branch prediction helps you understand why vectorization is faster, not just how to wire it up.
The Core Vectorized Execution Mental Model
Instead of thinking in rows, think in columnar batches: tightly packed arrays of values for each column, plus optional metadata like null bitmaps. A vectorized query execution engine pulls and pushes these batches through operators (scan, filter, project, aggregate) in a pipeline. Each operator takes a batch, transforms it in-place or produces a new batch, and hands it off to the next operator.
I visualize it as an assembly line: each stage touches whole vectors of data, doing the same operation across hundreds or thousands of values at once. Here’s a minimal sketch of what a vector (column) might look like in C++:
struct ColumnVector {
int32_t *data; // contiguous values
uint8_t *nullmask; // bit-per-row, optional
int size; // number of active entries
int capacity; // max entries in this batch
};
Once you adopt this batch-first mental model, the design choices for the rest of the engine become much more natural.
Step 1: Start from a Simple Iterator-Based Query Execution Engine
Use the Iterator Model as a Baseline
When I first experimented with a vectorized query execution engine, I didn’t start from scratch; I began with a tiny, iterator-based engine I could fully understand in one sitting. The goal here is similar: keep a working baseline so you can compare correctness and performance as you introduce vectors.
A classic iterator engine wires operators together with a next() interface that returns one row at a time. Conceptually, each operator pulls a row from its child, processes it, and either returns it or skips it. In C-like pseudocode, it often looks like this:
struct Row { int32_t a; int32_t b; };
struct Op {
virtual bool next(Row &out) = 0; // returns false when exhausted
};
struct FilterOp : Op {
Op *child;
bool next(Row &out) override {
Row tmp;
while (child->next(tmp)) {
if (tmp.a > 10) { // simple predicate
out = tmp;
return true;
}
}
return false;
}
};
This is the engine you’ll gradually reshape: keep the operator graph, but swap row-based next() for batch-based processing later.
Identify the Seam Where Batches Will Plug In
Before changing anything, I like to locate the narrowest seam in the engine where all data flows through the same abstraction. In most iterator engines, that seam is the Row next(Row)-style API. Your first vectorization step is to introduce a parallel interface that deals with batches instead of single rows, without removing the original one yet.
In practice, that means sketching an alternative operator interface such as:
struct Batch {
ColumnVector *cols; // array of column vectors
int size; // rows in this batch
};
struct VecOp {
virtual bool next_batch(Batch &out) = 0;
};
At this stage, I usually keep both worlds alive: the old row iterator for regression tests, and a new, experimental vector path behind a flag. As you follow the rest of this tutorial, you’ll progressively route more of the pipeline through next_batch, validate that results match the iterator engine, then optimize layout, branching, and SIMD usage. For a concrete look at how production systems made this transition, it’s worth studying Evolution of a Compiling Query Engine.
Step 2: Introduce Vectorized Batches and Columnar Layout
Design a Columnar Batch Structure
Once I have a working iterator engine, my next move is to nail down a concrete batch representation. For a vectorized query execution engine, this is the backbone: every operator will push and pull these batches, so it needs to be simple, cache-friendly, and easy to extend.
I usually start with fixed-size batches (e.g., 1024 or 4096 rows) and a columnar layout: each column is a contiguous array of values, plus a null bitmap. Here’s a compact C-style sketch:
const int BATCH_CAPACITY = 1024;
typedef enum {
TYPE_INT32,
TYPE_INT64,
TYPE_DOUBLE,
} DataType;
struct ColumnVector {
void *data; // pointer to raw values
uint8_t *nullmask; // 1 bit per row, nullable; can be NULL if no nulls
DataType type;
};
struct Batch {
ColumnVector *cols; // array of column vectors
int ncols;
int size; // active rows in this batch (<= BATCH_CAPACITY)
};
In practice, I often allocate one Batch per pipeline stage and reuse it, just overwriting size and values. This reuse keeps memory traffic low and lets the CPU cache do more work.
Add Selection Vectors and Masks
Filtering is where I’ve personally seen vectorization pay off, but it also introduces a key concept: selection. Instead of physically removing rows from each column every time a predicate fails, I mark which row indices are still “alive” using a selection vector.
// Selection by index: indices[0..size) refer into the columns.
struct SelectionVector {
int size;
int indices[BATCH_CAPACITY];
};
struct BatchWithSel {
Batch batch;
SelectionVector sel; // if sel.size == 0, interpret as identity 0..batch.size-1
};
A filter operator then just compacts indices in the selection vector instead of shuffling all column data. When I first implemented this, I saw a big win because the core loop becomes a tight, predictable scan over arrays:
bool filter_gt_int32(ColumnVector *col, BatchWithSel *bw, int32_t threshold) {
SelectionVector *sel = &bw->sel;
int in_size = (sel->size == 0) ? bw->batch.size : sel->size;
int out_size = 0;
int *indices = sel->indices;
int32_t *data = (int32_t *)col->data;
for (int i = 0; i < in_size; i++) {
int row = (sel->size == 0) ? i : indices[i];
if (data[row] > threshold) {
indices[out_size++] = row;
}
}
sel->size = out_size;
bw->batch.size = out_size; // downstream sees only surviving rows
return out_size > 0;
}
This pattern—keep data columnar, track surviving rows in a separate vector—shows up in almost every vectorized engine I’ve worked on.
Process Fixed-Size Batches in Tight Loops
With batches and selection vectors defined, the final step in this phase is to discipline yourself to operate on fixed-size batches inside tight, branch-light loops. Instead of thinking “one row per call,” you now think “up to N rows per call” and write loops that do the same operation for each active index.
As an example, here’s how a simple projection (computing c = a + b) might look using our batch structure:
void project_add_int32(BatchWithSel *bw, int col_a, int col_b, int col_c) {
Batch *b = &bw->batch;
int n = b->size;
ColumnVector *A = &b->cols[col_a];
ColumnVector *B = &b->cols[col_b];
ColumnVector *C = &b->cols[col_c];
int32_t *a = (int32_t *)A->data;
int32_t *bvals = (int32_t *)B->data;
int32_t *c = (int32_t *)C->data;
if (bw->sel.size == 0) {
for (int i = 0; i < n; i++) {
c[i] = a[i] + bvals[i];
}
} else {
int *idx = bw->sel.indices;
for (int k = 0; k < bw->sel.size; k++) {
int i = idx[k];
c[i] = a[i] + bvals[i];
}
}
}
In my experience, once your engine consistently uses this batch-first, columnar, selection-aware pattern, you unlock further optimizations almost for free: SIMD intrinsics, late materialization, and even adaptive batch sizing. If you’d like more background on how production systems structure these loops and memory layouts, it’s helpful to read How to build an extremely fast analytical database -Part3 | by Kaisen Kang | StarRocks Engineering | Medium.
Step 3: Implement Core Vectorized Operators and Pipelining
Vectorized Scan: Filling Batches from Storage
Once I have a batch layout I like, I start wiring up a scan operator; everything else in a vectorized query execution engine tends to build on top of it. The idea is simple: read up to BATCH_CAPACITY values per column, populate a Batch, and return it to the caller.
In a real system, this would sit on top of a buffer pool or columnar file format, but for a first cut I usually back it with plain in-memory arrays so I can focus on correctness and the vectorized control flow:
struct VecOp {
virtual bool next_batch(BatchWithSel &out) = 0;
virtual ~VecOp() {}
};
struct InMemoryScan : VecOp {
BatchWithSel bw;
int total_rows;
int position; // next row to read
InMemoryScan(ColumnVector *cols, int ncols, int nrows) {
bw.batch.cols = cols;
bw.batch.ncols = ncols;
bw.batch.size = 0;
bw.sel.size = 0; // identity selection
total_rows = nrows;
position = 0;
}
bool next_batch(BatchWithSel &out) override {
if (position >= total_rows) return false;
int remaining = total_rows - position;
int to_read = remaining > BATCH_CAPACITY ? BATCH_CAPACITY : remaining;
// For an in-memory demo, we assume data is already in the
// column vectors at indices [0..total_rows). We just expose
// a window by adjusting the selection vector.
bw.batch.size = to_read;
bw.sel.size = to_read;
for (int i = 0; i < to_read; i++) {
bw.sel.indices[i] = position + i;
}
position += to_read;
out = bw;
return true;
}
};
In my early prototypes, keeping scan this simple helped me debug the rest of the pipeline without fighting storage complexity.
Vectorized Filter: Using Selection Vectors
Next, I like to plug in a filter operator on top of scan. It consumes a batch from its child, rewrites the selection vector based on a predicate, and outputs the filtered batch.
struct FilterGtInt32 : VecOp {
VecOp *child;
int col_idx;
int32_t threshold;
FilterGtInt32(VecOp *c, int col, int32_t t)
: child(c), col_idx(col), threshold(t) {}
bool next_batch(BatchWithSel &out) override {
BatchWithSel in;
while (child->next_batch(in)) {
Batch *b = &in.batch;
ColumnVector *col = &b->cols[col_idx];
int32_t *data = (int32_t *)col->data;
SelectionVector *sel = &in.sel;
int in_size = (sel->size == 0) ? b->size : sel->size;
int *idx = sel->indices;
int out_size = 0;
if (sel->size == 0) {
for (int i = 0; i < in_size; i++) {
if (data[i] > threshold) {
idx[out_size++] = i;
}
}
} else {
for (int k = 0; k < in_size; k++) {
int i = idx[k];
if (data[i] > threshold) {
idx[out_size++] = i;
}
}
}
if (out_size == 0) continue; // pull next batch
sel->size = out_size;
b->size = out_size;
out = in;
return true;
}
return false;
}
};
In my experience, this style of filter is a great litmus test: if you can get it working cleanly with nulls and multiple predicates, the rest of the vectorized operators tend to follow the same pattern.
Vectorized Projection: Computing New Columns
Projection is usually the easiest operator to vectorize, which is why I like to add it early. It consumes a batch, runs arithmetic or simple expressions over the active indices, and writes into output columns.
struct ProjectAddInt32 : VecOp {
VecOp *child;
int col_a, col_b, col_out;
ProjectAddInt32(VecOp *c, int a, int b, int out_col)
: child(c), col_a(a), col_b(b), col_out(out_col) {}
bool next_batch(BatchWithSel &out) override {
BatchWithSel in;
if (!child->next_batch(in)) return false;
Batch *b = &in.batch;
ColumnVector *A = &b->cols[col_a];
ColumnVector *B = &b->cols[col_b];
ColumnVector *C = &b->cols[col_out];
int32_t *a = (int32_t *)A->data;
int32_t *bv = (int32_t *)B->data;
int32_t *c = (int32_t *)C->data;
SelectionVector *sel = &in.sel;
if (sel->size == 0) {
for (int i = 0; i < b->size; i++) {
c[i] = a[i] + bv[i];
}
} else {
int *idx = sel->indices;
for (int k = 0; k < sel->size; k++) {
int i = idx[k];
c[i] = a[i] + bv[i];
}
}
out = in;
return true;
}
};
When I first wired this up, I deliberately stuck to very simple expressions to make it easy to cross-check results against the original iterator engine.
Wiring a Pull-Based Vectorized Pipeline
With scan, filter, and projection in place, you can build a small pull-based pipeline that feels very similar to the old iterator style—but now everything speaks in batches. The key is that each VecOp holds a pointer to its child and calls next_batch when it needs more data.
Here’s a tiny end-to-end example: scan a table, filter on column 0, compute c = a + b, and then consume the resulting batches at the root.
void run_pipeline(InMemoryScan *scan, int nrows) {
// Build pipeline: scan -> filter -> project
FilterGtInt32 filter(scan, /*col_idx=*/0, /*threshold=*/10);
ProjectAddInt32 project(&filter, /*a=*/0, /*b=*/1, /*out_col=*/2);
VecOp *root = &project;
BatchWithSel bw;
while (root->next_batch(bw)) {
Batch *b = &bw.batch;
int n = b->size;
// In my prototypes, I just print a few rows to sanity check
// that the pipeline is producing what I expect.
// (Assume column 2 is the projected result.)
int32_t *c = (int32_t *)b->cols[2].data;
SelectionVector *sel = &bw.sel;
if (sel->size == 0) {
for (int i = 0; i < n; i++) {
// consume c[i]
}
} else {
for (int k = 0; k < sel->size; k++) {
int i = sel->indices[k];
// consume c[i]
}
}
}
}
From here, you can iteratively harden the design: add null handling, more data types, and SIMD optimizations, while continuously comparing results to your iterator-based engine. In my own projects, this side-by-side development has been the safest way to evolve a simple prototype into a reliable, high-performance vectorized query execution engine.
Step 4: Validate and Benchmark Your Vectorized Query Execution Engine
Verify Correctness Against the Iterator Baseline
Before I celebrate any speedups, I treat the old iterator engine as a ground truth oracle. For every query pattern you care about (simple filters, projections, a couple of joins/aggregations if you have them), run both engines on the same deterministic dataset and compare results byte-for-byte.
In practice, I like to serialize the output of each engine into sorted vectors and then compare. Here’s a minimal C-style sketch for a single-column integer result:
bool compare_results(const std::vector&it_res, const std::vector &vec_res) { if (it_res.size() != vec_res.size()) return false; std::vector a = it_res, b = vec_res; std::sort(a.begin(), a.end()); std::sort(b.begin(), b.end()); return std::equal(a.begin(), a.end(), b.begin()); }
I’ve caught plenty of subtle bugs this way—especially around null handling and selection vectors.
Build a Simple, Repeatable Benchmark Harness
Once I trust correctness, I wire up a tiny harness that runs the same logical query via the iterator and the vectorized query execution engine, timing each over multiple runs. Use fixed synthetic datasets first so you can scale row counts easily.
void benchmark(QueryPlan *iter_plan, VecOp *vec_root, int trials) {
for (int t = 0; t < trials; t++) {
auto t1 = now();
run_iterator_plan(iter_plan);
auto t2 = now();
run_vectorized_pipeline(vec_root);
auto t3 = now();
double it_ms = millis_between(t1, t2);
double vec_ms = millis_between(t2, t3);
printf("trial %d: iterator=%.3f ms, vectorized=%.3f ms\n", t, it_ms, vec_ms);
}
}
On my first prototypes, even a simple scan+filter+project often showed 2–5x speedups once vectorization was wired correctly.
Interpret Results and Iterate
Raw numbers are just the start; I also profile CPU time and inspect hardware counters (cache misses, branch mispredicts, SIMD usage) to see whether the vectorized path is actually exercising the CPU as intended. If vectorization isn’t clearly faster, I revisit batch size, memory layout, and branching in my tight loops.
To go deeper into practical benchmarking pitfalls (warm-up effects, NUMA, compiler flags) and how they affect OLAP engines, it’s worth reading RISC-V Meets RDBMS: An Experimental Study of Database Performance on an Open Instruction Set Architecture. In my experience, a disciplined test-and-benchmark loop is what finally turns a working prototype into a confidently fast engine.
Conclusion and Next Steps for Your Vectorized Query Execution Engine
Where to Go from Here
By this point, you’ve taken a simple iterator engine and turned it into a basic but real vectorized query execution engine: you defined columnar batches, selection vectors, and fixed-size processing loops; you wired up vectorized scan, filter, and projection; and you validated and benchmarked the new pipeline against your baseline.
In my experience, even this minimal set of operators is enough to see meaningful speedups on analytic-style workloads, often in the 2–5x range for scan-heavy queries. The bigger gains come as you extend the same patterns to more complex operators.
Natural next steps include:
- Aggregations: vectorized GROUP BY and partial aggregates kept in small hash tables.
- Joins: hash joins that probe in batches, with selection vectors controlling which rows advance.
- Adaptive pipelining: changing batch sizes or operator fusion strategies based on data shapes.
- SIMD and null handling: tightening inner loops with intrinsics and robust null semantics.
What’s worked best for me is to evolve the engine incrementally: add one new operator or optimization at a time, keep the iterator path as a safety net, and let benchmarks guide where to invest effort next.
Hi, I’m Cary Huang — a tech enthusiast based in Canada. I’ve spent years working with complex production systems and open-source software. Through TechBuddies.io, my team and I share practical engineering insights, curate relevant tech news, and recommend useful tools and products to help developers learn and work more effectively.
