query-engine

A relational execution engine implementing iterator (Volcano), vectorized, and compiled (codegen-to-C) execution over the same operator set, benchmarked on identical physical plans and workloads.

The point: when a vectorized engine beats an iterator engine, where does the win actually come from? Here both strategies run the exact same operator code - batch_size is a configuration value, not a separate code path - so the measured delta isolates execution-strategy overhead (per-tuple virtual dispatch, branching, cache behavior) from everything else.

Current results

Row counts differ between sections below on purpose: v0 uses 10,000,000 rows to show the batching win at a scale where it is unmistakable; v1, phase 3, and phase 4 use 2,000,000 so the join and the runtime compile step stay fast to benchmark. Each section is labeled with its own row count.

SELECT c0 + c1 FROM t WHERE c2 < 4 over 10,000,000 rows (~4% selectivity), Apple clang 21, -O2, Apple Silicon:

batch_size = 1      [iterator (Volcano)]     80.6 ms
batch_size = 1024   [vectorized]              6.4 ms
Speedup: 12.7x

Per-operator breakdown (from a separate profiled run; per-tuple timer overhead inflates the batch_size=1 numbers, which is why headline timings above come from unprofiled runs):

Operator	Time (bs=1)	Time (bs=1024)	Calls (bs=1)	Calls (bs=1024)	Rows In	Rows Out
Scan	148.8 ms	3.8 ms	10,000,000	9,766	10,000,000	10,000,000
Filter	127.3 ms	2.4 ms	10,000,000	9,766	10,000,000	400,365
Project	5.4 ms	0.2 ms	400,365	9,766	400,365	400,365

Why: the iterator engine pays one virtual call per operator per tuple (branch + dispatch overhead, no loop for the compiler to vectorize); the batched engine amortizes dispatch over 1024 tuples and runs tight loops over columnar buffers. Both runs produce byte-identical results (row count and checksum verified).

v1: join + group-by

SELECT dim.d1, SUM(fact.c0), COUNT(*) FROM fact JOIN dim ON fact.c2 = dim.d0 GROUP BY dim.d1 - a 2M-row fact table hash-joined against a 100-row dimension, then grouped. Both operators run the same code at both batch sizes and produce identical output (10 groups, checksum verified). Profiled per-operator table (the pipeline-breaker cost of per-tuple hashing is exactly what batching amortizes here):

Operator	Time (bs=1)	Time (bs=1024)	Rows In	Rows Out
Scan	31.5 ms	0.8 ms	2,000,100	2,000,100
HashJoin	30.7 ms	7.7 ms	2,000,100	2,000,000
Aggregate	11.9 ms	11.5 ms	2,000,000	10

The hash-join build side and the aggregate materialize (gather through the selection vector into dense storage before hashing) - the deliberate materialization exception at pipeline breakers. The join probe side stays streaming and selection-based.

Each operator's reported time is exclusive of its children: HashJoin's timer starts only after its child's next() returns (same as Filter), so building the hash table over the build side is counted here and nowhere else, and pulling the probe side's rows is not double-counted. HashJoin's Rows In (2,000,100) is both sides combined: 2,000,000 probe rows plus the 100 build rows consumed while hashing.

Phase 4: compiled execution

A third strategy on the same plan: generate C for the Scan -> Filter -> Project pipeline as one fused loop, compile it at runtime (cc -shared -fPIC), dlopen it, and run it. compile() mirrors lower() - the compiled path takes the same LogicalPlan the interpreter and optimizer use. The v0 query, three ways (2M rows, execution time only; compiled results verified identical):

Iterator:    17.6 ms
Vectorized:   1.3 ms
Compiled:     5.6 ms   (+ 471 ms one-time compile)

Note the honest result: vectorized wins here. On a filter+project this simple, the vectorized engine's columnar batch loops auto-vectorize to SIMD, and the compiled path's one-time compile cost isn't amortized in a single run. Compilation pulls ahead on deeper multi-operator pipelines - where crossing operator boundaries and materializing intermediates dominate - and when a plan runs many times. Codegen covers the linear pipeline only; join/aggregate plans fall back to the interpreter. docs/0005

Design

• Pull-based operators (open / next / close), written once; execution strategy is configuration. docs/0001
• Selection vectors, not compaction: Filter never moves data - it emits indices into still-full column buffers. Chained filters compact the selection in place. docs/0002
• Batch memory is reused, never reallocated per call; the puller owns the batch it passes down.
• Instrumentation lives on ExecutionContext, not on operators; exclusive per-operator timing by construction. docs/0003
• Logical -> physical plan split is kept even while lowering is 1:1, so the phase-3 cost-based optimizer slots in without touching execution code.

Build & run

make run                     # 10M rows, batch sizes 1 and 1024
./build/engine --rows 50000000
make test                    # regression tests: selection vectors, join/aggregate
                              # edge cases, optimizer pushdown, codegen rejection rules

Requires a C++20 compiler; no other dependencies.

Write-up

One post per phase, walking through what I built and what the numbers showed (including the phase-4 result that surprised me):

1. Building a Volcano execution engine from scratch
2. Why batching made my query engine 12x faster
3. A query optimizer that provably cannot change your results
4. I compiled my query pipeline to C, and it got slower

Status / roadmap

• v0: Scan -> Filter -> Project, selection vectors, configurable batch size, per-operator instrumentation, iterator-vs-vectorized benchmark
• v1: hash Join + Aggregate (inner equi-join, integer GROUP BY with SUM/COUNT) with the materialization exception at pipeline breakers; join+group-by benchmark verified identical across batch sizes
• Phase 3: cost-based optimizer - LogicalPlan -> LogicalPlan pass with predicate pushdown and cardinality estimation, EXPLAIN, and report-only join-side selection; optimized plans verified identical to unoptimized at both batch sizes (docs/0004). (Join reordering and histogram stats deferred - need 3+ table joins to matter.)
• Phase 4: compiled execution - generate C for the Scan -> Filter -> Project pipeline, compile at runtime (cc + dlopen), run on the same plan; three-way iterator/vectorized/compiled benchmark with a hard compiled-vs-interpreted identity gate (docs/0005). (Join/aggregate codegen deferred - those plans use the interpreter.)
• Regression test suite (tests/test_engine.cpp, run with make test): selection-vector chaining, join/aggregate edge cases (duplicate keys, no match, multi-batch resume, groups spanning batches, empty input, re-open), optimizer pushdown (index remapping, unpushable filters, stacked filters, idempotence), codegen's reject rules, and a profiler-exclusivity check.