AsterDB

A vectorized in-memory analytical query engine in C++20
Columnar storage · batch execution · rule-based optimizer · hash joins

---

The result

Pushing a filter below a join and narrowing the scanned columns makes this query 8.2× faster over a million rows — and returns byte-identical output in all four configurations.

SELECT c.country, COUNT(*), SUM(s.revenue)
FROM sales s JOIN customers c ON s.customer_id = c.id
WHERE s.year >= 2024 AND s.revenue > 1000
GROUP BY c.country ORDER BY SUM(s.revenue) DESC;

EXPLAIN shows exactly what the optimizer did — this is real output, not a sketch:

BEFORE (120.41 ms)                        AFTER (14.66 ms)
Aggregate group=[c.country]               Aggregate group=[c.country]
  Filter (s.year >= 2024 AND ...)           HashJoin s.customer_id = c.id
    HashJoin s.customer_id = c.id             Filter (s.year >= 2024 AND ...)
      Scan sales [0, 1, 2, 3, 4]                Scan sales [1, 3, 4]
      Scan customers [0, 1, 2, 3]             Scan customers [0, 2]

The filter moved below the join, so it eliminates rows before the most expensive operator runs; the scans narrowed from 5→3 and 4→2 columns.

Architecture

Three decisions shape everything else:

• Selection vectors. A filter emits sorted row indices, never a copy. Filtering a 10 M-row column performs zero allocations, verified by a global operator new counter.
• Dictionary-encoded strings. STRING columns are int32 codes into a shared dictionary, so GROUP BY region hashes integers. Built on day one — retrofitting means touching every operator.
• Toggleable optimizer rules. Every rewrite switches off at runtime, which is the only reason E4 can attribute a speedup to one specific rule.

Details in ARCHITECTURE.md · reasoning and rejected alternatives in DECISIONS.md · public types in docs/API.md.

Written up in docs/DESIGN_NOTES.md.

Building

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build
./build/bin/asterdb

Requires CMake ≥ 3.20 and a C++20 compiler (GCC ≥ 12, Clang ≥ 15, or MSYS2/MinGW-w64 on Windows). No third-party runtime dependencies — GoogleTest is fetched by CMake and never linked into the engine.

# Reproduce the benchmarks
cmake -B build-release -DCMAKE_BUILD_TYPE=Release -DASTERDB_BUILD_BENCHMARKS=ON
cmake --build build-release -j
python datasets/generate.py --rows 10000 --rows 1000000 --rows 10000000
./build-release/bin/asterdb_bench --machine "<your CPU, RAM, OS>"

Engineering practice

• 238 tests, green in Debug, Release, and under ASan + UBSan on Linux CI
• 14 pandas cross-checks — aggregates and joins validated against an independent implementation, because an engine tested only against itself can be consistently wrong
• Warnings-as-errors, including -Wconversion -Wshadow -Wcast-align -Wold-style-cast
• CI on every push: GCC and Clang × Debug and Release, sanitizers, doc-link checking
• 11 Architecture Decision Records recording the alternatives that were rejected and why
• A knowledge graph (graphify-out/, 1400+ nodes) so structural questions resolve to file:line

Scope

Deliberately not a database: no durability, transactions, network layer, cost-based optimizer, or out-of-core execution — and single-threaded by decision, not omission (ADR-011).

The constraint is the point. A smaller engine with rigorous, honestly-reported measurements is a better artifact than a larger one with none — and the full list of what this project refuses to be is in REQUIREMENTS.md §2.

Repository map

Path	What is in it
docs/BENCHMARKS.md	The primary deliverable — methodology, results, analysis
docs/DESIGN_NOTES.md	The three hardest problems and what they taught
docs/API.md	Public types and the invariants callers must not break
docs/GRAMMAR.md	The exact SQL and CSV subset accepted
ARCHITECTURE.md · DECISIONS.md	Design, and why
REQUIREMENTS.md · PHASES.md · RULES.md	Scope, plan, working rules
MEMORY.md	Project state and session log — read this first to pick the work up
include/ · src/	Engine: common, storage, parser, optimizer, execution
benchmarks/ · tests/	Timing harness and 238 tests

License

MIT — see LICENSE.