query-engine

A relational execution engine with three execution strategies over one operator set: iterator (Volcano), vectorized, and compiled to C. All three run the same physical plans on the same data, so the benchmarks compare execution strategy and nothing else.

The iterator and vectorized engines are the same code. batch_size is a parameter (1 or 1024), not a second implementation, so the difference between them is per-tuple dispatch, branching and cache behavior.

Results

Apple Silicon, Apple clang 21, -O2. The first query uses 10M rows; the join and compiled benchmarks use 2M to keep them quick.

Scan, filter, project

SELECT c0 + c1 FROM t WHERE c2 < 4, 10M rows, about 4% selectivity:

batch_size = 1      (iterator)     80.6 ms
batch_size = 1024   (vectorized)    6.4 ms

12.7x. Per-operator times from a profiled run (timing every tuple inflates the batch_size=1 column, so the numbers above come from unprofiled runs):

Operator	bs=1	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

At batch size 1 every operator makes a virtual call per tuple and there is no loop for the compiler to vectorize. At 1024 the dispatch cost is spread over a batch and each operator runs a tight loop over a column. Both produce the same rows and checksum.

Join and 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 to a 100-row dimension:

Operator	bs=1	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 join's build side and the aggregate copy rows into dense storage before hashing (docs/0002); the probe side streams. Times are exclusive of children, and HashJoin's rows in counts both inputs.

Compiled execution

The Scan, Filter, Project pipeline can also be generated as one C loop, compiled with cc -shared -fPIC, loaded with dlopen and run. Same query, 2M rows, execution time only:

Iterator:    17.6 ms
Vectorized:   1.3 ms
Compiled:     5.6 ms   (+ 471 ms to compile)

Vectorized wins. Its column loops auto-vectorize to SIMD, the generated scalar loop has a branch per row, and one run does not pay back the compile time. Compilation should do better on deeper pipelines and on plans that run many times. Joins and aggregates are not compiled; those plans use the interpreter. See docs/0005.

Design

• Pull-based operators (open, next, close); execution strategy is a parameter. docs/0001
• Filter does not move data. It writes a selection vector of row indices; chained filters narrow it in place. docs/0002
• Batches are reused across calls. The caller owns the batch it passes down.
• Profiling lives on ExecutionContext, not on operators, and times are exclusive per operator. docs/0003
• Logical and physical plans are separate, so the optimizer rewrites the logical plan without touching execution code. docs/0004

Build and run

make run                         # 10M rows, batch sizes 1 and 1024
./build/engine --rows 50000000
make test                        # regression tests

Needs a C++20 compiler and nothing else.

Write-up

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

Status

• v0: Scan, Filter, Project with selection vectors, configurable batch size, per-operator profiling.
• v1: hash join (inner equi-join) and aggregate (integer GROUP BY with SUM and COUNT), identical results across batch sizes.
• Phase 3: optimizer with predicate pushdown, cardinality estimates and EXPLAIN. Join side selection is reported but not applied. Join reordering and histograms are not done.
• Phase 4: compiled Scan, Filter, Project pipeline, checked against the interpreter on every run. No codegen for joins or aggregates.
• Tests (tests/test_engine.cpp): selection vector chaining, join and aggregate edge cases (duplicate keys, no matches, multi-batch resume, groups spanning batches, empty input, re-open), optimizer pushdown, codegen rejection rules, profiler exclusivity.