Introduction

MarsDB is an embeddable property-graph database with an openCypher query subset: single binary, single file, optional in-memory mode. No server process, no network protocol — it links into your Rust, Python, or Go program (or runs standalone via the marsdb CLI) the same way SQLite does for relational data.

$ marsdb :memory:
MarsDB graph database. Enter Cypher statements terminated by `;`. Ctrl-D to exit.
marsdb> CREATE (a:Person {name: 'Alice'})-[:KNOWS]->(b:Person {name: 'Bob'});
marsdb> MATCH (a:Person)-[:KNOWS]->(b:Person) RETURN a.name, b.name;
a.name | b.name
Alice | Bob

Why a graph database

Relational databases model connections as foreign keys and join tables; finding them back out means more joins, one per hop, and the query gets harder to write and slower to run as the path gets longer. A graph database stores the connection itself as a first-class thing, so “friends of friends,” “the shortest path between these two people,” or “everyone reachable within three hops” are direct pattern matches, not a chain of joins.

Why MarsDB specifically

• A real subset of openCypher, not a lookalike. Checked against the openCypher Technology Compatibility Kit on every push. See the Cypher Language Reference for exactly what’s covered.
• Embeddable, not a server. Database::open("path/to.db") or Database::in_memory() and you’re running queries — no daemon to manage, no port to bind, no client/server protocol.
• Crash-safe by construction. Every Cypher statement runs inside one transaction; storage runs on redb, a pure-Rust MVCC single-file engine.
• Bindings, not just a Rust crate. Python (PyO3, prebuilt wheels) and Go (cgo against a small C ABI) both work today.

Where to go next

• New to MarsDB? Start with Getting Started.
• Want a Cypher walkthrough? The Cypher Guide.
• Integrating into a program? Embedding in Rust, Python bindings, or Go bindings.
• Wondering exactly which Cypher features are supported? See the Cypher Language Reference.
• Curious how it’s built? See Performance, or the Internals appendix.

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

Getting Started

The fastest way to try MarsDB is the CLI — no code required.

Install

cargo install marsdb-cli

Or on macOS/Linux via Homebrew (tap):

brew install knoguchi/marsdb/marsdb

Your first session

$ marsdb :memory:
MarsDB graph database. Enter Cypher statements terminated by `;`. Ctrl-D to exit.
marsdb> CREATE (a:Person {name: 'Alice'})-[:KNOWS]->(b:Person {name: 'Bob'});
marsdb> MATCH (a:Person)-[:KNOWS]->(b:Person) RETURN a.name, b.name;
a.name | b.name
Alice | Bob
marsdb>

:memory: starts an in-memory database that disappears on exit. Give it a file path instead — marsdb graph.db — and the data persists between runs. Every statement ends with ;; Ctrl-D exits the REPL.

Running a script

A file of ;-separated statements runs the same way piped through stdin:

marsdb graph.db < setup.cypher

Or as a one-shot query against an existing database:

marsdb graph.db "MATCH (n:Person) RETURN n.name"

Next steps

• Learn Cypher itself: The Cypher Guide
• Embed MarsDB in a program: Embedding in Rust, Python bindings, or Go bindings
• Every CLI flag: CLI Reference

The Cypher Guide

A walkthrough of Cypher itself, one clause at a time, building up a small graph as we go. Every example runs as-is in the CLI REPL (marsdb :memory:) or through any language binding — the Cypher text is identical everywhere. For the full list of what’s implemented, see the Cypher Language Reference.

Creating nodes

CREATE (:Person {name: 'Alice', age: 30, city: 'Boston'})
CREATE (:Person {name: 'Bob', age: 27, city: 'Boston'})
CREATE (:Person {name: 'Carol', age: 35, city: 'Seattle'})

:Person is a label; {...} is the node’s property map. A node needs neither — CREATE (n) works — but an unlabeled node is rarely useful.

Creating relationships

A relationship is written inside a pattern, between two nodes:

CREATE (a:Person {name: 'Dave'})-[:KNOWS]->(b:Person {name: 'Eve'})

This creates both nodes and the relationship between them in one statement. That matters: reusing a variable name across two separate CREATE patterns creates two different nodes, not one — CREATE (a:Person {name: 'Alice'}), (a)-[:KNOWS]->(b:Person {name: 'Bob'}) does not mean “connect the Alice created above.” To connect nodes that already exist, match them first:

MATCH (a:Person {name: 'Alice'}), (b:Person {name: 'Carol'})
CREATE (a)-[:KNOWS]->(b)

MATCH (c:Person {name: 'Carol'}), (d:Person {name: 'Dave'})
CREATE (c)-[:KNOWS]->(d)

The graph so far: Alice -> Carol -> Dave -> Eve, plus Bob, connected to no one.

Reading data: MATCH and RETURN

MATCH (p:Person) RETURN p.name, p.age
MATCH (p:Person {city: 'Boston'}) RETURN p.name
MATCH (a:Person)-[:KNOWS]->(b:Person) RETURN a.name, b.name

RETURN p (no property access) returns the whole node; RETURN * returns every variable bound so far. Relationships work the same way as nodes: MATCH ()-[r:KNOWS]->() RETURN r binds the relationship itself.

Filtering: WHERE

MATCH (p:Person) WHERE p.age > 30 RETURN p.name
MATCH (p:Person) WHERE p.name STARTS WITH 'A' RETURN p.name
MATCH (a:Person), (b:Person)
WHERE a.city = b.city AND a.name <> b.name
RETURN a.name, b.name

A pattern itself can be a filter condition:

MATCH (a:Person)
WHERE exists { (a)-[:KNOWS]->(:Person {city: 'Seattle'}) }
RETURN a.name

Traversing further: variable-length paths

[:KNOWS*1..3] matches 1 to 3 KNOWS hops in a row — “friends, friends of friends, up to 3 hops out”:

MATCH (:Person {name: 'Alice'})-[:KNOWS*1..3]->(f:Person)
RETURN DISTINCT f.name

Bounds can be open (*1.., *..3) or omitted entirely (*, unbounded). shortestPath finds the shortest connection between two nodes over a variable-length relationship. Both endpoints must already be bound by an earlier MATCH — a fresh label/property filter can’t be declared inline inside shortestPath(...):

MATCH (a:Person {name: 'Alice'}) MATCH (b:Person {name: 'Eve'})
MATCH p = shortestPath((a)-[:KNOWS*]-(b))
RETURN length(p)

Updating: SET

MATCH (p:Person {name: 'Alice'}) SET p.age = 31
MATCH (p:Person {name: 'Alice'}) SET p += {city: 'Cambridge', verified: true}
MATCH (p:Person {name: 'Alice'}) SET p:VIP

SET p.field = value sets one property. SET p += {...} merges a map in, leaving properties not mentioned untouched. SET p = {...} (no +) replaces the whole property map. SET p:Label adds a label without touching properties.

Create-or-update: MERGE

MERGE matches a pattern if it exists, or creates it if it doesn’t — useful for “insert this node unless it’s already there”:

MERGE (p:Person {name: 'Alice'})
ON CREATE SET p.firstSeen = 'today'
ON MATCH SET p.lastSeen = 'today'

MERGE is capped at one relationship hop per statement (MERGE (a)-[:KNOWS]->(b) is fine; a longer chain in one MERGE isn’t).

Deleting

MATCH (p:Person {name: 'Bob'}) DELETE p

Bob has no relationships, so plain DELETE works. Carol does — deleting her the same way fails:

MATCH (p:Person {name: 'Carol'}) DELETE p
MATCH (p:Person {name: 'Carol'}) DETACH DELETE p

DETACH DELETE removes the attached relationships first, then the node.

Aggregating

MATCH (p:Person) RETURN p.city, count(*) AS people
MATCH (p:Person) RETURN p.city, collect(p.name) AS names
MATCH (:Person)-[:KNOWS]->(f:Person) RETURN count(DISTINCT f) AS unique_friends

Any bare (non-aggregating) expression in the same RETURN becomes an implicit GROUP BY key — there’s no separate GROUP BY clause.

Ordering, paging, and dedup

MATCH (p:Person) RETURN p.name ORDER BY p.age DESC LIMIT 2
MATCH (p:Person) RETURN DISTINCT p.city

Parameters

MATCH (p:Person {name: $name}) RETURN p.age

Send $name as a bound parameter rather than interpolating it into the query text — see the per-language binding pages (Rust, Python, Go) for exactly how to pass parameters from each.

Where to go next

• Cypher Language Reference — everything implemented, and the current known gaps.
• Embedding in Rust, Python bindings, Go bindings — running these queries from a program.

Embedding in Rust

cargo add marsdb

#![allow(unused)]
fn main() {
let db = marsdb::Database::in_memory()?; // or Database::open("path/to.db")
db.execute("CREATE (a:Person {name: 'Alice'})")?;
let result = db.execute("MATCH (n:Person) RETURN n.name")?;

// Bound work from untrusted callers. A CancellationToken can also be
// cloned and cancelled from another thread.
let options = marsdb::ExecutionOptions {
    max_intermediate_rows: Some(100_000),
    max_result_rows: Some(10_000),
    max_relationship_expansions: Some(1_000_000),
    timeout: Some(std::time::Duration::from_secs(5)),
    ..Default::default()
};
let result = db.execute_with_options("MATCH (n) RETURN n", &options)?;

// Group statements into one atomic unit. Reads through `tx` see its earlier
// writes; any statement error aborts and closes the whole transaction.
let mut tx = db.begin_transaction()?;
tx.execute("CREATE (:Person {name: 'Bob'})")?;
tx.execute("CREATE (:Person {name: 'Carol'})")?;
tx.commit()?;

// Or run a `;`-separated batch, one transaction per statement, one
// QueryResult per statement back:
let results = db.execute_batch("CREATE (a:Person {name: 'Alice'}); CREATE (b:Person {name: 'Bob'})")?;
}

ExecutionOptions::observer accepts an ExecutionObserver callback for dependency-free telemetry. Events contain duration, outcome category, read/write classification, result-row count, and relationship expansions; they deliberately exclude query text and error messages. Syntax and missing-parameter rejections are reported too, and observer panics are contained.

Backup, integrity checks, and other operational concerns that apply regardless of which language you’re calling from are covered in Operations.

Stored procedures (CALL)

MarsDB ships no built-in procedures — CALL proc(args) [YIELD ...] resolves against a marsdb_query::ProcedureProvider you supply via ExecutionOptions::procedures:

#![allow(unused)]
fn main() {
use std::sync::Arc;
use marsdb::{ExecutionOptions, Procedures, ProcedureProvider, ProcedureSignature, Value};
// `ProcedureProvider::call`'s error type -- not re-exported by `marsdb`
// itself, so implementing the trait needs a direct `marsdb-query`
// dependency too (`cargo add marsdb-query`).
use marsdb_query::QueryError;

struct MyProcedures;

impl ProcedureProvider for MyProcedures {
    fn signature(&self, name: &str) -> Option<ProcedureSignature> {
        // Look up `name`'s declared inputs/outputs, or `None` if unknown.
        None
    }
    fn call(&self, name: &str, args: &[Value]) -> Result<Vec<Vec<Value>>, QueryError> {
        // Run the procedure, return its output rows.
        Ok(vec![])
    }
}

let options = ExecutionOptions {
    procedures: Some(Procedures(Arc::new(MyProcedures))),
    ..Default::default()
};
}

More examples

cargo run -p marsdb --example task_tracker    # CRUD + aggregation
cargo run -p marsdb --example social_graph    # variable-length traversal, MATCH...CREATE
cargo run -p marsdb --example params_and_batch # $parameters, execute_batch

Full source in marsdb/examples/. Each also writes an SVG chart of its query result (via plotters) to the current directory.

Natural language → Cypher

marsdb-nl2cypher translates an English question into Cypher against a database’s actual schema (labels/relationship-types/properties in use, introspected automatically), validates its syntax and variable/type binding, and retries once with the exact validation error fed back if the first attempt is invalid. No HTTP/LLM-SDK dependency in the core crate — bring your own LlmClient:

#![allow(unused)]
fn main() {
use marsdb::Database;
use marsdb_nl2cypher::{translate_and_run, LlmClient};

let db = Database::in_memory()?;
db.execute("CREATE (:Person {name: 'Alice'})-[:KNOWS]->(:Person {name: 'Bob'})")?;

let (cypher, result) = translate_and_run(&db, &my_llm_client, "who does Alice know?")?;
}

translate_and_run enforces read-only generated Cypher. Model-generated writes are rejected before execution unless the caller explicitly uses translate_and_run_with_policy(..., ExecutionPolicy::AllowWrites) after performing its own authentication and authorization.

MarsDB’s narrower Cypher subset (vs. full Neo4j Cypher) is a deliberate fit for this — a smaller grammar means fewer ways an LLM can generate something unparseable. The prompt tells the model what’s supported and what to avoid (no bare --> shorthand, MERGE capped at one hop, etc.) — see marsdb-nl2cypher/src/lib.rs’s CAPABILITIES constant.

A runnable example against a local Ollama instance:

ollama serve &
ollama pull llama3.2
cargo run -p marsdb-nl2cypher --example ollama_demo

Python bindings

pip install marsdb

import marsdb
db = marsdb.Database.in_memory()  # or .open(path)
db.execute("CREATE (a:Person {name: 'Alice'})-[:KNOWS]->(b:Person {name: 'Bob'})")
db.execute("MATCH (n:Person) RETURN n.name")
# -> [{'n.name': 'Alice'}, {'n.name': 'Bob'}]

Prebuilt wheels cover macOS (arm64, x86_64) and Linux (x86_64, manylinux); other platforms install from the source distribution and need a Rust toolchain. Built via PyO3 — in-process, no separate server or IPC.

Build from source

cd marsdb-python
python3 -m venv .venv && source .venv/bin/activate
pip install maturin && maturin develop

Go bindings

Unlike marsdb-python (PyO3, in-process), Go has no equivalent in-process FFI story with Rust, so the Go binding goes through the small C ABI crate, marsdb-capi, via cgo.

The binding lives in its own repository, marsdb-go, as two Go modules:

go get github.com/knoguchi/marsdb-go        # core binding, zero deps
go get github.com/knoguchi/marsdb-go/arrow  # Arrow results (arrow-go dep)

The split keeps the core module dependency-free — arrow-go is a heavyweight dependency only columnar consumers should pay for.

Build

The C header is vendored in the binding repo; only the library needs building here. In a checkout of this repository:

cargo build -p marsdb-capi --features arrow

(--features arrow is required by the arrow module and harmless for the core one.) Then, in a marsdb-go checkout:

export CGO_LDFLAGS="-L/path/to/marsdb/target/debug"
go test ./...

Usage

package main

import (
	"fmt"
	"log"

	marsdb "github.com/knoguchi/marsdb-go"
)

func main() {
	db, err := marsdb.InMemory() // or marsdb.Open("path/to.db")
	if err != nil {
		log.Fatal(err)
	}
	defer db.Close()

	if _, err := db.Execute("CREATE (a:Person {name: 'Alice'})-[:KNOWS]->(b:Person {name: 'Bob'})"); err != nil {
		log.Fatal(err)
	}

	rows, err := db.Execute("MATCH (n:Person) RETURN n.name AS name ORDER BY n.name")
	if err != nil {
		log.Fatal(err)
	}
	for _, row := range rows {
		fmt.Println(row["name"])
	}
	// Alice
	// Bob
}

Execute returns []map[string]any, one map per matched row keyed by column name — the same dict-per-row shape as marsdb-python. A returned node decodes as map[string]any{"__type": "node", "id": ..., "labels": []any{...}, "props": map[string]any{...}}; an edge similarly with "__type": "edge" plus "src"/"dst". Integer properties and IDs retain their full precision as int64 (or uint64 for an ID above int64’s range), while fractional values are float64. Dates and durations are returned as canonical ISO-8601 strings such as "1984-10-11" and "P1M2D".

See the marsdb-go README for the full API tour — parameterized queries, transactions, streaming, execution bounds — platform linking notes, and the Arrow module’s column-typing rules.

C API

marsdb-capi is a small, hand-written C ABI (opaque handle + JSON results) — the basis for non-Rust bindings like Go. Header: marsdb-capi/marsdb.h.

typedef struct MarsdbDatabase MarsdbDatabase;

/* Exactly one of `json`/`error` is non-null. Both, when non-null, must be
 * released with marsdb_free_string -- never with free(). */
typedef struct MarsdbResult {
    char *json;
    char *error;
} MarsdbResult;

/* Open (creating if absent) a single-file, on-disk database. Returns NULL
 * on failure (bad UTF-8 path, or the underlying open erroring). */
MarsdbDatabase *marsdb_open(const char *path);

/* Open a purely in-memory database. Nothing is written to disk. */
MarsdbDatabase *marsdb_open_in_memory(void);

/* Reclaims a handle from marsdb_open/marsdb_open_in_memory. NULL is a
 * no-op; double-close or closing a foreign pointer is undefined behavior. */
void marsdb_close(MarsdbDatabase *db);

/* Run one Cypher statement. Result JSON shape:
 *   {"columns": [...], "rows": [[...], ...]}
 * where each value is its natural JSON scalar, or for nodes/edges:
 *   {"__type": "node", "id": ..., "labels": [...], "props": {...}}
 *   {"__type": "edge", "id": ..., "label": ..., "src": ..., "dst": ..., "props": {...}}
 * Dates and durations use canonical ISO-8601 strings.
 */
MarsdbResult marsdb_execute(MarsdbDatabase *db, const char *cypher);

/* Frees a string returned in MarsdbResult.json or MarsdbResult.error.
 * Required -- these are allocated by Rust's global allocator, not malloc. */
void marsdb_free_string(char *s);

Build the shared/static library with cargo build -p marsdb-capi (add --release for an optimized build) — produces libmarsdb_capi.{dylib,so,a} under target/{debug,release}/.

This is intentionally minimal (Open/Execute/Close, JSON results) — enough to build a real language binding on top, which is exactly what marsdb-go does. execute_batch/execute_with_params exist on the Rust side but aren’t exposed through this C ABI.

CLI Reference

marsdb is a single binary: a REPL, a one-shot query runner, and a batch runner, depending on the arguments you give it. (Not installed yet? See Getting Started.)

Usage

marsdb                                  # in-memory REPL
marsdb mydata.db                        # file-backed REPL
marsdb mydata.db "MATCH (n) RETURN n"   # run one query, exit
marsdb :memory: "..."                   # explicit in-memory, one-shot
marsdb mydata.db "CREATE (a); CREATE (b); MATCH (n) RETURN n"  # ;-separated batch
marsdb mydata.db < script.cypher        # piped stdin, same ;-separated batch
marsdb mydata.db --nl "who does Alice know?"  # plain-English question via Ollama

Arguments:

The REPL

Starts whenever no query argument is given and stdin is a terminal. Enter any Cypher statement terminated by ;:

$ marsdb :memory:
MarsDB graph database. Enter Cypher statements terminated by `;`. Ctrl-D to exit.
marsdb> CREATE (a:Person {name: 'Alice'})-[:KNOWS]->(b:Person {name: 'Bob'});
marsdb> MATCH (a:Person)-[:KNOWS]->(b:Person) RETURN a.name, b.name;
a.name | b.name
Alice | Bob

Ctrl-D exits.

Meta-commands

The REPL also has sqlite-style dot commands for quick schema introspection. Each is a thin formatter over a built-in CALL db.* procedure (so the same introspection is available from plain Cypher too, in any binding). Meta-commands run immediately — no trailing ; needed, though one is tolerated.

Example, against a database with one :Person, one :Movie, a WATCHED relationship between them, and a unique index on :Person(name):

marsdb> .labels
Movie  (1)
Person  (1)
marsdb> .types
WATCHED  (1)
marsdb> .props
age
name
stars
title
marsdb> .indexes
:Person(name) UNIQUE
marsdb> .schema
labels:
  Movie  (1)
  Person  (1)

relationship types:
  WATCHED  (1)

indexes:
  :Person(name) UNIQUE

An unrecognized .command prints the same list as .help.

Natural language queries

--nl translates a plain-English question into Cypher and runs it, using a local Ollama instance:

ollama serve &
ollama pull llama3.2
marsdb mydata.db --nl "how many people are there?"

Set OLLAMA_MODEL to use a model other than the default llama3.2. The generated Cypher is printed before its results. Generated writes are rejected — --nl only ever runs read-only queries. The translation itself validates the generated Cypher’s syntax and variable/type binding against the database’s actual schema, retrying once with the validation error fed back if the first attempt doesn’t parse — see the marsdb-nl2cypher crate for the underlying library.

Cypher Language Reference

MarsDB implements a subset of Cypher. It passes the full openCypher TCK. Exhaustive breakdown: CYPHER_COVERAGE.md.

Supported

• Patterns: MATCH/OPTIONAL MATCH, undirected/bracketless/multi-type/ variable-length relationship patterns, named-path capture (including over variable-length hops), shortestPath(), pattern comprehension, pattern predicates.
• Reading & filtering: WHERE (property/identity/label comparisons, pattern predicates, STARTS WITH/ENDS WITH/CONTAINS), exists { ... } (both the simple pattern form and the full nested-subquery form, including nested exists {}), UNWIND, any number of chained WITH boundaries, ORDER BY/SKIP/LIMIT, DISTINCT.
• Writing: CREATE, MERGE (with ON CREATE/ON MATCH), SET, REMOVE, DELETE/DETACH DELETE, MATCH ... CREATE, arbitrary chaining of mutating clauses via trailing WITH or RETURN. MERGE is capped at one relationship hop.
• Aggregation: implicit GROUP BY, count/sum/avg/min/max/ collect/percentileCont/percentileDisc, DISTINCT inside an aggregate call, aggregate expressions composed with arithmetic.
• Functions: the standard scalar/string/math/list function set (coalesce, toInteger/toFloat/toString/toBoolean, keys/ labels/type/properties/id, size/length/nodes/ relationships/head/tail/last/range, toUpper/toLower/ trim/replace/split/substring, abs/ceil/floor/round/ sqrt/sign).
• Temporal types: Date/LocalTime/Time/LocalDateTime/ DateTime/Duration — construction from strings, maps, or another temporal value; comparison; calendar-aware arithmetic; full component access; ISO-8601 string round-tripping.
• Stored procedures: CALL proc(args) [YIELD ...], both standalone and in-query forms, against a caller-supplied ProcedureProvider — see Embedding in Rust. MarsDB itself ships no built-in procedures.
• Parameters: $name scalars, lists (including nested lists), and maps.

Known limitations

• Node/relationship-valued $parameters aren’t supported. Scalar, list, and map parameters already work. This is on the roadmap.
• No cost-based query optimizer. Index seeks and top-k ORDER BY ... LIMIT selection exist, but join/traversal ordering isn’t cost-estimated. See Architecture. This is on the roadmap.
• CALL needs an embedder-supplied ProcedureProvider — there’s no built-in procedure catalog.

Conformance testing

Checked against the openCypher Technology Compatibility Kit (TCK) on every push: 3,880/3,880 scenarios pass across 220 feature files. Per-category numbers are in CYPHER_COVERAGE.md.

git submodule update --init marsdb-tck/openCypher
cargo run --release -p marsdb-tck

Operations

Running MarsDB in practice — backup, integrity checks, crash safety, file format compatibility, and concurrent access. These apply regardless of which language you’re calling from; see Embedding in Rust, Python bindings, Go bindings, or the C API for the exact call syntax in each.

Backup

Database::backup_to(path) writes a transactionally consistent copy of the database to path. The destination must not already exist — an existing file is never overwritten, so a backup can’t silently clobber another database or a previous backup.

#![allow(unused)]
fn main() {
db.backup_to("path/to-backup.db")?;
}

Integrity checks

Database::check_integrity() checks redb’s physical storage and then MarsDB’s own logical graph invariants, returning an IntegrityReport:

#![allow(unused)]
fn main() {
let report = db.check_integrity()?;
}

physical_was_clean: false is worth treating as a signal, not just a statistic — it means the underlying file had damage severe enough for redb to notice and fix. The logical counts in the same report are only meaningful once the physical layer is sound, which is why the physical check runs first. check_integrity needs exclusive access — no other transaction can be open on the database while it runs.

Crash safety

Every Cypher statement runs inside one transaction, committed atomically. Storage runs on redb, a pure-Rust MVCC single-file engine. A dedicated test harness (marsdb-crash-harness, a development tool, not something you run in production) SIGKILLs a MarsDB process mid-workload at unpredictable points and verifies on reopen that every commit the process had acknowledged actually survived. This is a process-crash check — the OS stays up and the page cache stays intact — not a power-loss test; genuine power-loss testing needs fault injection at the block-device layer (e.g. dm-flakey).

Storage format versioning

MarsDB records its own record/table format version inside the database file, separate from redb’s own file format. Opening a file written by an unsupported format version — either an old pre-versioning file or one written by a newer, incompatible version of MarsDB — fails cleanly with an error at open time. MarsDB never silently reinterprets a file it doesn’t understand as if it were the current format.

Concurrent access

A read-only MATCH ... RETURN statement opens a redb ReadTransaction, which runs alongside any number of other concurrent readers and a concurrent writer without contending for redb’s single-writer lock. Every other statement — any write, or a Cypher-level BEGIN session — opens a WriteTransaction. Standard MVCC: one writer at a time, readers never block on it and never block each other.

Session transactions and idle timeout

MarsDB’s Cypher BEGIN / COMMIT / ROLLBACK statements (a MarsDB extension — openCypher itself has no transaction statements) open a session-level write transaction on the Database handle. Every statement executed on that handle after BEGIN runs inside it, reads included, until COMMIT or ROLLBACK closes it.

An open write transaction holds redb’s single writer. If a BEGIN is left open — the caller forgets to COMMIT, or the connection is dropped without closing it — every other writer on that database blocks forever: redb’s begin_write blocks rather than erroring out. This applies to caller-owned transactions too (begin_transaction in Rust, or the equivalent in other bindings), not just session transactions.

Database::set_session_transaction_timeout(Some(duration)) mitigates this for session transactions: once a session transaction has sat idle longer than the configured limit, the next statement that arrives on that handle rolls it back and returns a timeout error, instead of running normally. There’s no background timer — an abandoned transaction with no further traffic on the handle keeps holding the writer lock until another statement actually shows up. If you mix session transactions with caller-owned transaction handles across threads, expect the reclaim to happen on that next statement, not on a clock tick. The timeout is disabled (None) by default.

Performance

Numbers below are measured on a single MacBook (Apple Silicon, arm64), release build, in-process (cargo bench, criterion), against Database::in_memory() unless noted otherwise. Full detail and every dataset size are in BENCHMARKS.md in the repo root.

Compared to Neo4j

Loading the same real dataset — Neo4j’s recommendations example graph (movies

• cast/crew from OMDb, users + ratings from MovieLens; 28,863 nodes, 166,261 relationships) — into both engines from the same generated Cypher script, file-backed on both sides, wall-clock:

Neo4j ran in Docker (neo4j:5.26, official image); MarsDB ran natively. Neo4j’s numbers are phase totals via cypher-shell, not per-query timings. This covers one dataset and one workload shape, not a general claim across all query patterns — see BENCHMARKS.md for the full methodology and the marsdb-demo repo for the reproduction script.

Typical query latencies

Point lookups and single-hop traversals, against a small in-memory dataset:

MATCH (n:Label) RETURN ... LIMIT k (no hop, no WHERE, no ORDER BY) pushes the limit into the storage scan directly, so it stays flat regardless of dataset size — about 22 µs whether the table has 100 rows or 100,000:

Property indexes

MATCH (n:Item {idx: N}) RETURN n.idx, with and without CREATE INDEX ON :Item(idx) declared:

The index seek stays flat regardless of dataset size — it reads exactly the matching entries. Declare an index for any property you filter or join on at meaningful scale; CREATE INDEX ON :Label(prop), see the Cypher Language Reference.

Aggregation

count/sum/avg/min/max/collect and implicit GROUP BY use a hash-based group lookup, scaling close to linearly with row count:

Concurrency

A MATCH ... RETURN opens a read transaction, not a write transaction — concurrent readers run in parallel instead of queueing behind the single-writer lock. 200 queries against a 1,000-node dataset, single thread vs. split across N threads sharing one Arc<Database>:

Sub-linear — it plateaus around 4-8 threads on the 14-core machine this was measured on. Writers still serialize behind each other (one write transaction at a time); see Operations for the full concurrency model.

Reproducing these numbers

cargo bench -p marsdb-graph
cargo bench -p marsdb

The second command runs cypher_ops, ldbc_ops, aggregate_ops, concurrency_ops, and index_ops. Numbers above are single measurements on one machine — expect variance run to run, and different numbers entirely on different hardware.

Scope of these numbers

• No disk-backed sustained-write benchmarks — the numbers above other than the Neo4j comparison ran against Database::in_memory().
• The Neo4j comparison covers one dataset load/query/update/delete workflow, not a general benchmark suite — no JanusGraph, Neptune, or other graph database is compared here.

Architecture

marsdb-storage   thin trait boundary over redb (file + in-memory backends)
marsdb-graph     property graph model, CRUD, KV/adjacency encoding
marsdb-query     openCypher subset: ANTLR4 grammar -> AST -> IR -> executor
marsdb           embeddable public Rust API (Database::open/in_memory/execute)
marsdb-cli       the `marsdb` binary (REPL + one-shot mode)
marsdb-python    PyO3 bindings, builds via maturin
marsdb-capi      C ABI (opaque handle + JSON results), basis for non-Rust bindings
marsdb-nl2cypher natural-language -> Cypher: schema introspection, prompt building, validate-and-repair

Go bindings live in a separate repository, knoguchi/marsdb-go, linking against marsdb-capi via cgo — see Go bindings.

Storage

Storage runs on redb, a pure-Rust single-file MVCC embedded KV engine. Every Cypher statement runs inside one transaction — a read-only MATCH ... RETURN opens a ReadTransaction (a consistent snapshot that runs alongside other concurrent readers or a concurrent writer without contending for redb’s single-writer lock), everything else opens a WriteTransaction, committed or aborted as a whole. Database::begin_transaction lets callers explicitly extend that atomic boundary across multiple statements. MarsDB records its own table/record format version in metadata when the file is created or first opened by a version-aware build, and refuses to open a database written by a newer unsupported format.

Query execution

Query execution compiles Cypher to a small Gremlin-shaped logical IR (AllNodesScan, NodeByLabelScan, Seed, Expand, VarExpand, Filter, IndexSeek) so a future Gremlin frontend could target the same executor. The parser is ANTLR4-generated (marsdb-query/grammar/).

The logical read plan runs as a pull-based row stream through node-ID scans, filters, relationship expansions, and variable-length traversals (each input row’s paths enumerate lazily too). A non-aggregating RETURN ... LIMIT k without ORDER BY stops that pipeline after k rows — or, with DISTINCT, after k distinct projected rows, so MATCH (p)-[:KNOWS*1..3]-(f) RETURN DISTINCT f ... LIMIT 20 stops traversing the moment 20 distinct endpoints exist instead of enumerating every path first. Clause boundaries and inherently blocking operations still materialize: WITH, optional-match reconciliation, aggregation, anything under ORDER BY, mutations, and the public QueryResult. Use ExecutionOptions to put hard ceilings on intermediate rows, result rows, relationship expansions, and elapsed time.

There is no general cost-based optimizer. It’s on the roadmap. Two targeted optimizations complement streaming: a direct MATCH (n[:Label]) RETURN ... LIMIT k scan pushes the limit into storage; and every ORDER BY ... LIMIT k site uses a top-k partial selection (slice::select_nth_unstable_by + a sort of just the k-sized prefix) instead of a full sort of every row. Declared property indexes (CREATE INDEX ON :Label(prop)) are used automatically when a WHERE/ inline-property equality matches one — see the index seek benchmarks.

Cypher coverage

See the Cypher Language Reference for the full, TCK-measured breakdown.

Contributing

Before opening a PR

CI (.github/workflows/rust.yml) runs on every push/PR to main:

• Format + Clippy: cargo fmt --all -- --check and cargo clippy --workspace --all-targets -- -D warnings — zero warnings tolerated.
• Tests: cargo test --workspace --verbose on Linux, macOS, and Windows.
• Bindings: builds and tests the Python (maturin + unittest) and Go (go test) bindings against the same Rust workspace build.

Run the same checks locally before pushing:

cargo fmt --all -- --check
cargo clippy --workspace --all-targets -- -D warnings
cargo test --workspace

Additional local checks

cargo test -p marsdb-graph --test stress -- --ignored --nocapture  # ~15s, large-scale
cargo test -p marsdb-crash-harness -- --ignored --nocapture        # ~7s/30 runs, SIGKILL-and-verify
cargo bench -p marsdb-graph
cargo bench -p marsdb

marsdb-crash-harness is a process-crash durability check (not a full power-loss test — the OS stays up, page cache intact): it spawns a child process committing one transaction at a time, SIGKILLs it at an unpredictable point, reopens the file fresh, and asserts every acknowledged commit survived intact with no gaps or duplicates.

The Cypher parser (the one part of MarsDB that takes raw, untrusted string input directly) is fuzzed via cargo-fuzz — needs nightly:

cargo install cargo-fuzz
cd marsdb-query && cargo +nightly fuzz run parse -- -max_total_time=120

Only claim: never panics. A parse error (Result::Err) is the expected, correct outcome for most fuzzer-generated input.

openCypher TCK conformance

Changes that touch marsdb-query should be checked against the real openCypher TCK, not just the crate’s own unit/smoke tests — see the Cypher Language Reference for what this measures and why:

git submodule update --init marsdb-tck/openCypher
cargo run --release -p marsdb-tck

For fast iteration, restrict to a category/feature:

TCK_FILTER="clauses/create" cargo run -p marsdb-tck --release

If a change moves the conformance numbers, update the table in CYPHER_COVERAGE.md (exact row numbers + the TOTAL row) in the same PR — it’s the ground truth behind the summary on this book’s own Cypher Language Reference page.

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option. By contributing, you agree your contribution is licensed under the same terms.

MarsDB Internals

This part of the book is for developers, or anyone curious about MarsDB’s internals. The earlier chapters tell you how to use MarsDB; this part tells you how it works: the on-disk layout, the transaction machinery, the path a Cypher statement takes from text to rows, and the reasoning behind the design decisions along the way.

A few crates, one storage engine, one query pipeline: ACID transactions, crash safety, secondary indexes, a cost-aware planner, streaming execution, and zero-copy results across three language boundaries. Every performance figure in these chapters comes from this repository’s benchmark suite.

Chapters

1. Design Overview — what MarsDB is, the crate stack, the life of a statement, and the transaction model.
2. The Storage Layer — redb, the thirteen tables, the transaction abstraction, backup and integrity.
3. Graph Encoding — the value model, interning, the record directory format, adjacency keys.
4. The Write Path — the CRUD layer, table-handle caching, mutation anatomy, the integrity checker as invariant spec.
5. The Query Frontend — grammar, AST design, parameters, semantic validation.
6. The IR and the Planner — logical operators, pushdown, property indexes, index seeks, cost-based start-point selection, EXPLAIN.
7. The Executor — plan evaluation, bounded execution, three-valued logic, aggregation, the streaming lane.
8. Results and Language Boundaries — the result model, the C ABI, zero-copy Arrow export.
9. Testing and Measurement — the TCK, the crash harness, the benchmark ledger.
10. Case Studies in Measured Trade-offs — the measurements that made (and unmade) design decisions.

Design Overview

MarsDB is an embeddable property-graph database: a Rust library that runs inside your process, stores an entire graph in a single file (or purely in memory), and answers openCypher queries. There is no server, no network protocol, and no background thread — all database work happens within the caller’s function call. If you have used SQLite, the shape is familiar; MarsDB applies it to the property graph model: nodes with labels and properties, directed typed relationships with properties, and a query language built around pattern matching.

This chapter provides a high-level tour of the whole system: the crate stack, the life of a single statement, and the transaction model. Every later chapter zooms into one region of this map.

The crate stack

MarsDB is a small workspace of layered crates. Each layer talks only to the one below it:

marsdb-cli       the `mars` binary: REPL and one-shot execution
marsdb           public embedding API: Database, Transaction, sessions
marsdb-query     Cypher text -> AST -> logical plan -> executor
marsdb-graph     property-graph model: records, encoding, indexes, CRUD
marsdb-storage   thin boundary over the embedded KV engine (redb)

flowchart BT
    storage["marsdb-storage — thin boundary over redb"]
    graphc["marsdb-graph — records, encoding, indexes, CRUD"]
    query["marsdb-query — Cypher → AST → plan → executor"]
    core["marsdb — Database, Transaction, sessions"]
    cli["marsdb-cli — the mars binary"]
    capi["marsdb-capi — C ABI"]
    py["marsdb-python — PyO3"]
    redb[("redb — B-tree file, MVCC")]
    storage --> redb
    graphc --> storage
    query --> graphc
    core --> query
    cli --> core
    capi --> core
    py --> core

Two observations about this stack shape most of what follows.

The storage engine is reused, not rebuilt. marsdb-storage wraps redb, a pure-Rust single-file embedded key-value store with ACID transactions, MVCC snapshots, and a B-tree file format. Writing a durable, crash-safe storage engine is a multi-year project in its own right, and it is the layer where bugs are least acceptable and hardest to find. Building on a proven engine lets the graph-specific work — encoding, planning, and execution — sit on a foundation whose fsync discipline someone else has already debugged. The cost is accepting redb’s constraints, the most important being its concurrency model: any number of concurrent readers, but only one writer at a time, process-wide. That single-writer rule echoes through the entire design, from the session layer down to lock-ordering comments in the executor. marsdb-graph never imports redb directly; it goes through marsdb-storage’s small trait boundary, which keeps the dependency surface explicit and limits the scope of changes if the engine ever needs to be replaced.

The query language is compiled into an execution-oriented IR rather than interpreted directly from the AST. marsdb-query parses Cypher (an ANTLR grammar generates a parse tree, which a visitor converts into an AST), validates it, and lowers each MATCH pattern into a small tree of logical operators — AllNodesScan, NodeByLabelScan, IndexSeek, IndexRangeSeek, EdgeTypeScan, Seed, Expand, VarExpand, Filter — that the executor evaluates against storage. The operators are traversal-shaped rather than Cypher-shaped on purpose: they describe how to walk the graph, not what the query text said, which is what lets the planner substitute one access path for another (a label scan for an index seek, an anchored expansion for an edge sweep) without the executor caring where the plan came from.

The life of a statement

Everything the database does is reachable from one entry point: Database::execute (and its variants taking parameters and options) in marsdb/src/lib.rs. Tracing one call end to end touches every layer:

1. Parse. The Cypher text goes through the generated parser and the AST-building visitor. A syntax error stops here; nothing has touched storage yet.

2. Substitute parameters. $name placeholders are replaced in the AST from the caller’s parameter map. This is structural substitution, not string splicing — a parameter value can never change the shape of the query, which is why parameterized queries are immune to injection by construction.

3. Route through the session layer. The Database handle checks whether a Cypher-level BEGIN transaction is currently open on it. If so, the statement runs inside that transaction (and sees its uncommitted writes). If not, the statement autocommits: it gets a transaction of its own for exactly its own duration. The lock guarding this check is released before autocommit execution begins, so concurrent readers on one handle actually run concurrently.

4. Open the right kind of transaction. The executor classifies the statement: a read-only shape (MATCH ... RETURN with no write clause) opens a redb read transaction — a consistent MVCC snapshot that coexists with other readers and at most one concurrent writer — while anything that writes opens the write transaction, of which redb allows exactly one at a time.

5. Plan. The pattern is lowered to the logical-operator tree, then rewritten with storage in view: filters over label scans become index seeks where a declared index exists, start points may be reversed based on cost statistics, predicates and limits are pushed down toward the scans. Planning happens per execution, inside the statement’s transaction, so the plan reflects the indexes and statistics that this exact snapshot can see.

6. Evaluate. The executor walks the operator tree, binding variables to nodes, relationships, and values row by row, then applies the statement’s tail: projection, aggregation, ordering, limits, or the write clauses (CREATE, SET, DELETE, …), which mutate storage through marsdb-graph’s CRUD layer inside the same transaction.

7. Commit or abort. Success commits — redb makes the whole statement’s effects durable atomically. Any execution error aborts the transaction: a statement that fails halfway leaves no trace. This all-or-nothing boundary per statement is the database’s basic crash-safety contract, and it holds for a statement that created three thousand nodes just as for one that created one.

flowchart TD
    A["Cypher text"] --> B["Parse (ANTLR → AST)"]
    B -->|syntax error| X1["Error — no transaction ever opened"]
    B --> C["Substitute $params (structural)"]
    C -->|missing param| X1
    C --> D{"Session BEGIN open?"}
    D -->|yes| E["Run inside session write txn"]
    D -->|no| F{"Read-only shape?"}
    F -->|yes| G["Open ReadTransaction (MVCC snapshot)"]
    F -->|no| H["Open WriteTransaction (the single writer)"]
    G --> I["Plan (rewrite with indexes + statistics)"]
    H --> I
    E --> I
    I --> J["Evaluate operator tree, apply tail"]
    J -->|success| K["Commit — atomic, durable"]
    J -->|execution error| L["Abort — no trace left"]

The important property of this pipeline is where the boundaries sit. Parse and parameter errors happen before any transaction exists; planning happens inside the transaction so it can trust its snapshot; and a single statement is always exactly one atomic unit unless the caller has explicitly said otherwise — which brings us to the transaction model.

The transaction model

MarsDB exposes one storage-level reality — redb’s single-writer/many-readers MVCC — through three caller-facing forms, all defined in marsdb/src/lib.rs:

Autocommit is the default described above: one statement, one transaction. There is nothing to configure and no way to observe a half-applied statement.

Caller-owned transactions (Database::begin_transaction) return a Transaction handle owning a write transaction across multiple execute calls, committed or rolled back explicitly. Reads through the handle see the transaction’s own uncommitted writes. Any statement error aborts the whole transaction immediately rather than leaving it open — a deliberate stance: a failed statement may have applied partial effects before failing, and those must never be committable. The error handling makes the invalid state unrepresentable instead of trusting every caller to remember a rollback.

Session transactions are the same idea driven from inside the query language: BEGIN, COMMIT, and ROLLBACK as ordinary statements (an extension — openCypher itself has no transaction statements). This is what makes transactions usable from the CLI and from language bindings that only have an “execute string” API. Each Database handle is one session; BEGIN opens a write transaction that subsequent statements run inside until COMMIT or ROLLBACK. The same abort-on-execution-error stance applies, with one carve-out: a statement that never ran — a parse error, a missing parameter — leaves the transaction open because it made no changes that would require an abort.

Session transactions have an important caveat that follows directly from the single-writer rule: an open session transaction is the process’s one write slot, so an abandoned one blocks every other writer forever — redb’s begin_write blocks rather than erroring. MarsDB mitigates this with an optional idle timeout. The mechanism follows a design rule used throughout: no background threads. Expiry is checked lazily by the next statement to arrive on the session, not by a reaper thread. The database never does work outside a caller’s call stack, which keeps the embedding story simple (no shutdown ordering, no thread-safety obligations imposed on the host process) at the cost of “next statement” being the soonest an expired transaction can actually be reclaimed.

Batches compose with all of this. execute_batch runs a semicolon-separated script with the whole batch parsed up front (a syntax error anywhere means nothing runs), one transaction per statement — unless the script itself says BEGIN ... COMMIT, which works exactly as it does interactively. execute_batch_grouped trades crash-safety granularity for load throughput by committing once per group of statements rather than per statement. Measurements quantify the trade-off: each commit is an fsync, and on a 9,771-statement load script, per-statement commits took 69.1 s while groups of 100 took 13.4 s — and committing the entire script as one group only improved that to 12.1 s. Most of the win arrives by a few hundred statements per group; the numbers, not intuition, are what capped the recommended group size.

Design principles

Three habits recur so often in this codebase that later chapters will mostly be showing you instances of them.

Errors are explicit, and invariants are enforced by construction. Where an invariant holds by design — an index entry that cannot dangle because the only two functions that touch the indexed table maintain the index in the same transaction — the code panics if it is ever violated, rather than silently repairing state that “should be impossible.” Defensive code for unreachable states hides bugs; a panic surfaces them.

Performance claims require measurements. Every trade-off described in this book — index maintenance cost versus scan speedup, group-commit throughput, access-path selection — is documented with numbers from the repository’s benchmark suite, measured on stated workloads. Several design decisions went against the initially attractive option because the measurement said so; the closing case-studies chapter collects these, including an optimization that was fully built, measured at ~2%, and deleted.

The database describes itself. The planner’s choices are observable (EXPLAIN), the schema is introspectable (CALL db.labels() and friends), and execution is bounded and observable (row limits, timeouts, cancellation, and an observer hook). These interfaces expose the information needed to diagnose planning and execution behavior.

With the map established, the next chapter starts at the bottom of the stack: what is actually in the file.

The Storage Layer

Everything MarsDB knows lives in one redb database file, spread across thirteen key-value tables. This chapter describes the engine underneath (marsdb-storage/src/lib.rs), the table catalog (tables.rs), and the small transaction abstraction (txn.rs) that the rest of the system reads through. It deliberately stops short of what the bytes mean — record encodings are the next chapter — and focuses on where bytes go and under what guarantees.

redb in one page

redb is a pure-Rust embedded key-value store in the same family as LMDB: a single file organized as copy-on-write B-trees, with MVCC snapshots. Its contract, as MarsDB relies on it:

• Typed tables. A table is declared with compile-time key and value types (TableDefinition<u64, &[u8]>); redb handles their ordering and serialization. Multimap tables map one key to a set of values.
• Transactions. A ReadTransaction is a consistent snapshot; any number may coexist. A WriteTransaction is exclusive — one per process at a time — and commits atomically and durably.
• Ordered access. Tables support point gets, full iteration, and key-ordered range scans. Tuple keys order component-wise, which is the property MarsDB’s adjacency layout is built on.
• Cheap counts. redb tracks per-table entry counts, so “how many nodes exist” is O(1) — the planner’s cost comparisons depend on this.

Everything above redb treats these as the axioms of the system. What redb does not provide is any notion of graph, schema, index maintenance, or query — all of that is MarsDB.

The table catalog

marsdb-storage/src/tables.rs declares every table in the file. They fall into five groups.

flowchart LR
    subgraph identity["Identity & metadata"]
        META["META\ncounters + format version"]
    end
    subgraph interning["Interning"]
        L2I["LABEL_TO_ID / ID_TO_LABEL"]
        P2I["PROP_TO_ID / ID_TO_PROP"]
    end
    subgraph records["Records"]
        NODES["NODES\nid → encoded record"]
        EDGES["EDGES\nid → encoded record"]
    end
    subgraph adjacency["Adjacency"]
        AO["ADJ_OUT\n(src, label, edge) → dst"]
        AI["ADJ_IN\n(dst, label, edge) → src"]
        RTC["REL_TYPE_COUNTS\nplanner statistic"]
    end
    subgraph indexes["Secondary indexes"]
        NLI["NODE_LABEL_INDEX\nlabel → node ids"]
        IDEFS["INDEX_DEFS\ndeclared (label, prop)"]
        PIDX["PROPERTY_INDEX\nlabel ++ prop ++ value → node ids"]
    end
    NODES -.->|label ids| L2I
    NODES -.->|prop ids| P2I
    AO -.->|mirror of| AI
    IDEFS -.->|gates entries in| PIDX

Identity and metadata. META holds three counters under string keys: the next node id, the next edge id, and the file’s format version. Ids are u64s allocated monotonically and never reused. The format version is checked at open: a file written by an incompatible layout is rejected cleanly with a typed error, never half-read. The check distinguishes a brand-new file (no tables at all — initialize and stamp it, atomically in one transaction, so a crash cannot leave a half-initialized file) from an existing file with an unsupported version (refuse).

Interning. LABEL_TO_ID/ID_TO_LABEL and PROP_TO_ID/ID_TO_PROP are string-interning pairs: label names and property names are mapped to u32 ids once, and every other table speaks ids. This is the classic space/indirection trade — records store four fixed bytes instead of a repeated string, and comparisons become integer comparisons — at the cost of one lookup to translate at the boundary. Property names are interned globally rather than per-label: the same names (name, id, …) recur across labels, and separate namespaces would buy nothing.

Records. NODES and EDGES map u64 id to an encoded record — labels, endpoints, and properties. Chapter 3 covers the encoding.

Adjacency. ADJ_OUT and ADJ_IN are the traversal tables, and their key shape is the single most consequential layout decision in the file:

ADJ_OUT: (src_node_id, label_id, edge_id) -> dst_node_id
ADJ_IN:  (dst_node_id, label_id, edge_id) -> src_node_id

Because tuple keys order component-wise, one node’s entries cluster together, grouped by relationship type. A typed expansion — (n)-[:KNOWS]->() — is a range scan over the (node, label, *) prefix and touches only matching entries: O(matching degree). An untyped expansion widens to the (node, *, *) prefix. The alternative this replaced — a multimap of node_id -> adjacency entries ordered by edge id — forced every typed expansion to decode and label-check the node’s entire entry set: O(total degree), painful exactly where graphs get interesting (high-degree nodes). Two further details are deliberate: the tables are direction-separated mirrors rather than one table with a direction flag (an expansion knows its direction; why scan past the other half), and the keys are native fixed-width tuples rather than packed byte strings — erasing tuple keys to &[u8] was measured on this exact codebase at +34% file size, because it forfeits redb’s fixed-slot packing.

REL_TYPE_COUNTS (label_id -> live edge count) rides along with adjacency: a planner statistic maintained at the only two places an edge is created or deleted. It is never consulted to answer a query, only to cost one — a wrong value could produce a suboptimal plan but never a wrong result, which is the right failure mode for a statistic.

Secondary indexes. NODE_LABEL_INDEX (label_id -> node_ids, a multimap) backs label-filtered scans. INDEX_DEFS records which (label, property) pairs have declared indexes — presence of the key is the declaration — and PROPERTY_INDEX holds the entries: label_id ++ property_id ++ encoded_value -> node_ids. All declared indexes share this one physical table; the (label, property) prefix keeps each logical index’s entries contiguous under redb’s key ordering. The value bytes use an order-preserving encoding, so lexicographic byte comparison matches real value ordering within a type — which is what makes indexed range predicates (WHERE n.year > 2000) a key-range scan rather than a full-index walk.

Opening a database

StorageEngine::open_file (or open_memory, which runs the identical code over redb’s in-memory backend — the entire stack above storage cannot tell the difference) does two jobs beyond calling redb.

First, the format-version handshake described above. Second, it eagerly opens — and therefore creates — every table in the catalog inside one committed write transaction. redb only creates a table on first write-mode open, and reading a never-created table is an error, not an empty result. Creating everything up front means no read path anywhere in the system has to special-case “brand-new, still-empty database.” A dozen lines at open eliminate a whole class of if table-exists checks everywhere else.

Txn: one code path for two transaction types

redb’s WriteTransaction and ReadTransaction are unrelated structs sharing no trait — open_table on each is an inherent method returning different concrete types. But most of MarsDB’s code only ever reads (get/iter/range, never insert), and the same reading function must work inside a write statement’s transaction (to see its own uncommitted writes) and inside a read statement’s snapshot (to avoid contending for the single writer at all).

txn.rs papers over the split with three small enums: Txn (a copyable reference to either transaction kind) and TableHandle/ MultimapTableHandle (either table kind), each dispatching four operations: get, iter, range, and len. That is the entire abstraction. It is deliberately not an implementation of redb’s full ReadableTable trait — matching the whole trait would be boilerplate for methods nothing calls. Each method exists because a call site demanded it: range was left out entirely until the composite-key adjacency needed prefix scans; len was added when the planner needed O(1) cardinalities to compare scan costs. The surface grows only under demand. Reading txn.rs therefore tells you exactly what the entire upper system asks of storage: point gets, ordered iteration, ordered range scans, and counts. Four primitives.

Backup and integrity

backup_to produces a transactionally consistent copy: it opens one read snapshot of the source and copies every table into a freshly created destination file, committing once. The destination is opened with create_new — an existing file is never silently overwritten — and a failed backup removes its own partial file (safe precisely because create_new proved the file was ours). Because the copy is driven from a snapshot, it can run while other readers and a writer proceed, so MVCC also enables online backups.

check_integrity layers two checks: redb’s own physical validation (checksums, allocation), then MarsDB’s logical invariants — every adjacency entry’s endpoints decode, index entries point at live nodes that actually carry the indexed value, counters exceed every live id. The physical check trusts the engine; the logical check trusts no one, and is the tool you reach for when a bug report smells like corruption.

With the file’s shape established, the next chapter opens the record bytes: how a node with three labels and forty properties actually lays out, and what it costs to read one property from it.

Graph Encoding

The previous chapter placed thirteen tables in a file; this one opens the bytes inside them. The material lives in marsdb-graph: the value model (model.rs), the record encoding (encode.rs), name interning (labels.rs, props.rs), and id allocation (id.rs).

The value model

PropertyValue is both the runtime scalar type and the persisted one — there is no separate wire representation to keep in sync. Its variants: Null, Bool, Int (i64), Float (f64), String, six temporal types, homogeneous Lists, and a Map variant that exists solely so map-shaped query parameters can travel through the system — Cypher forbids storing a map as a property, and the query layer rejects it before anything reaches storage.

Values serialize with postcard, a compact serde format (varint integers, no field names). That choice carries a one-way compatibility rule: postcard encodes an enum discriminant by declaration order, so new PropertyValue variants append at the end, and existing ones are never reordered or removed — otherwise every already-stored property silently decodes as the wrong variant. The enum’s declaration order is on-disk ABI.

The temporal variants show a design rule for storing typed values in a dynamically typed system: the type must survive the storage boundary. A date could be stashed as Int(epoch_day) and would round-trip fine — but then a stored integer and a stored date would be indistinguishable on the way back out, and a value that must still print, compare, and expose components as a date after a round trip cannot afford that. So each temporal type is a first-class variant, with representations chosen for comparison-by-integer rather than library convenience:

• Date is days since the Unix epoch — an i64, not a date-library type, so the storage format cannot be broken by a dependency’s internal change, and comparison is integer comparison. (i64 rather than i32 because Cypher’s expanded year range ±999,999,999 reaches ±365 billion epoch days.)
• Duration is the four-component normalized form — months, days, seconds, nanos — because the components are not fungible: without a reference date, “3 months” has no fixed length in days, so collapsing duration({months: 1}) and duration({days: 30}) into one comparable scalar would be silently wrong the moment either is added to a date.
• DateTime stores the UTC instant plus the zone kept only for display; equality and ordering use the instant alone, so two DateTimes at the same instant in different zones compare equal — matching Cypher — even though they print differently. A named zone’s offset is not cached (the same zone has different offsets across a DST transition); it is re-derived on demand.

Each of these is a small instance of the same discipline: pick the representation that makes the invariant (comparison semantics, normalization, range) structural, and push the presentation problems (parsing, formatting, calendars) up into the query layer where they belong.

Interning: strings become integers

Labels and property names are interned: the first write that mentions Person allocates a u32 id for it and records the mapping in both directions (LABEL_TO_ID/ID_TO_LABEL; property names identically in their own pair). From then on, every record, adjacency key, and index key speaks the id. Allocation happens inside the caller’s write transaction via the same counter mechanism as node and edge ids (id.rs::next_id, a read-increment-write on the META table), which means id allocation sits inside the statement’s crash-safety boundary: an aborted statement’s freshly interned label vanishes with it, and no committed state can reference an unallocated id.

The read direction has one subtlety. Interning tables are created lazily by the first write that needs them, and a read transaction on a never-written database finds the table missing rather than empty. The lookup functions treat that specific error as “not found” — it is exactly equivalent — rather than propagating it; the gap was found by a real test (declaring an index on a never-used property), not by speculation.

The record encoding

A node record is not a serialized map. It is a directory:

node:  [label_count: u8][label_id: u32 × n]
       [prop_count: u16]
       [(prop_id: u32, offset: u32) × m]     <- sorted by prop_id
       [values: postcard-encoded, packed in directory order]
edge:  [label_id: u32][src: u64][dst: u64]
       [prop_count / directory / values as above]

Offsets are relative to the values region, and value i’s length is offset[i+1] − offset[i] (the last runs to the end) — which is why values must be packed in directory order: the lengths are implied, not stored.

The simpler alternative — serializing the whole name-keyed property map as one postcard blob — was the first implementation. The directory earns its complexity on the read path: fetching one property from a record is a binary search over the directory plus one postcard decode of just that value. No map is built, no sibling property is touched, and no property-name string is allocated — names appear nowhere in the record; ids resolve back to names only when a caller actually needs the full name-keyed shape. The difference is measured in this repository (an encoding-comparison benchmark under marsdb-storage/examples/): 79x faster for reading 1 property of 20, and still 7x faster even when fully materializing every property. Single-property access is what executors do constantly — every WHERE n.age > 30 evaluation, every projection of n.name — so this is the read path that matters.

Encode and decode take the interning and resolution functions as closures rather than a transaction type, so the same functions serve the write path (interning through the write context) and the read path (resolving through a read snapshot) without the codec knowing either exists. One practical detail with a measured justification: the resolver closure holds its table handle open across an entire record’s worth of resolutions, because opening a redb table handle was itself a measured hot cost — 23.67% of a bulk load, in a profile that predates the fix — and a resolver that re-opened per property would reintroduce exactly that.

Adjacency keys, again

Chapter 2 described ADJ_OUT/ADJ_IN’s composite keys from the table’s point of view; model.rs holds the other half. AdjEntry (edge id, other endpoint, label id) is the in-memory traversal candidate — everything one hop needs, readable from an adjacency entry alone without touching the NODES or EDGES tables. Two helper functions define the prefix bounds: adj_node_bounds(owner) covers every entry a node owns (the untyped expansion), and adj_label_bounds(owner, label) covers one relationship type (the typed expansion). All traversal in the executor ultimately bottoms out in a range scan between one of these pairs of bounds.

The fixed-width warning from chapter 2 bears repeating from this side: these keys are native (u64, u32, u64) tuples because redb keeps fixed-width tuples in fixed slots. A byte-packed [u8; 20] encoding of the same information — attractive for symmetry with other byte-encoded keys — was measured at 2x total database file size.

What is not here

Deletes remove records, adjacency entries, and index entries in the same transaction, and there is no tombstone or vacuum machinery; MVCC old versions are redb’s concern, reclaimed by its copy-on-write B-tree. Ids are never reused, which keeps “dangling id” a state that only a bug (not a design feature) can produce — and the integrity checker treats it accordingly.

The next chapter follows a write statement through GraphStore and WriteCtx to see how records, adjacency, counters, and four kinds of index entry are kept consistent inside one transaction.

The Write Path

A single CREATE (a:Person {name: 'Alice'})-[:KNOWS]->(b) touches nine of the thirteen tables: two records, two adjacency mirrors, a statistics counter, up to four interning entries, a label-index entry per label, and any property-index entries the labels’ declared indexes require. This chapter is about how marsdb-graph keeps all of that consistent with a small amount of machinery: store.rs (the CRUD layer) and write_ctx.rs (the table-handle cache that every write rides on).

Three layers per operation

Every mutating operation exists in the same three forms, e.g. for node creation:

• create_node — public convenience: opens a write transaction, calls the next layer, commits. One operation, one transaction.
• create_node_in_txn — takes a caller-supplied &WriteTransaction. This is what the query executor calls: the executor owns one transaction per statement, and every graph operation the statement performs flows through it.
• create_node_ctx — internal, takes &mut WriteCtx. This is where the actual work lives, and it is the composition point: an operation that needs another operation calls the _ctx form directly so both share one set of table handles.

The layering addresses a redb constraint. redb errors at runtime (TableAlreadyOpen) if one write transaction holds two live handles to the same table. Deleting a node must delete its incident edges; if node-deletion called the public edge-deletion wrapper, each call would open a fresh set of handles on the same transaction and collide with the ones node-deletion already holds. The _ctx layer exists so compound operations compose inside one handle set.

sequenceDiagram
    participant E as Executor (one txn per statement)
    participant S as GraphStore::create_edge_in_txn
    participant C as WriteCtx (lazy handles)
    participant T as redb tables
    E->>S: create edge (label, src, dst, props)
    S->>C: open ctx on the statement's WriteTransaction
    S->>C: nodes() — endpoint existence check
    C->>T: NODES.get(src), NODES.get(dst)
    S->>C: intern label, next edge id
    C->>T: LABEL_TO_ID / META
    S->>C: edges().insert(id, record)
    C->>T: EDGES
    S->>C: adj_out().insert / adj_in().insert
    C->>T: ADJ_OUT, ADJ_IN (mirror keys)
    S->>C: bump REL_TYPE_COUNTS
    C->>T: REL_TYPE_COUNTS
    Note over E,T: nothing durable until the statement's single commit

WriteCtx: lazy handles, measured

WriteCtx is a struct of thirteen Option<Table> fields with accessor methods: first access opens the handle, later accesses reuse it. Two decisions here were made by measurement, and both went against the initially plausible option:

Lazy, not eager. Opening all thirteen handles up front is simpler, but on a 9,771-statement bulk load it was slower than the pre-WriteCtx code (4.89 s → 6.35 s): most calls touch a handful of tables (set_edge_prop_in_txn needs exactly one), and eagerly opening the other unused handles costs more than the redundant opens it was meant to eliminate. Lazy access means a call pays only for the tables it uses, while still collapsing the repeat opens a single call used to perform — node creation previously opened NODES once, the label index once per label, and then the property-index hook re-opened four more tables on top. Table opens are not noise: a profile of that same bulk load attributed 23.67% of total time to them.

Scoped to one operation, not one transaction. Stretching the cache across a whole statement or transaction would save even more opens — but any read that happens while a write is in flight (property lookups in a WHERE, subquery evaluation) would then need to route through the same cached handles, or it hits the very TableAlreadyOpen the cache exists to avoid. That is a redesign of the read-write interleaving across two crates, and the cache’s scope stops where the contained change stops. Knowing where to stop is itself a design decision, and this one is documented in the module header rather than left for the next person to rediscover.

Anatomy of the mutations

Creating a node: intern each label, allocate the id (a counter bump in META — durable only when the caller commits, so id allocation sits inside the same crash-safety boundary as the record it names), encode the record (interning property names as a side effect), insert into NODES, add one NODE_LABEL_INDEX entry per label, and hand the new node to the property-index hook (index::on_node_created) which adds entries for any (label, prop) pair with a declared index.

Creating an edge: verify both endpoints exist (the only referential check the write path needs, since ids are never reused), intern the type, allocate the id, insert the record, then the two mirror-image adjacency entries — (src, label, edge) → dst in ADJ_OUT and (dst, label, edge) → src in ADJ_IN — and bump the type’s edge count.

Deleting an edge is the reverse, with a detail that shows the directory encoding paying off on the write path too: cleanup needs only the header — type, src, dst — to compute the two adjacency keys, so it reads exactly those bytes and never decodes properties or resolves a property name.

Deleting a node ranges over both adjacency tables with the node’s prefix bounds to collect incident edges. Non-detach deletion with incident edges refuses with a typed error before touching anything. DETACH DELETE deletes each incident edge through the shared _ctx path, then the record, the label-index entries, and the property-index entries. The reported edge count comes from the deletions, not the scan — a self-loop appears in both adjacency directions but deletes once, and the statement statistics must say one.

The statistics counter (REL_TYPE_COUNTS) is bumped in exactly two places — edge birth and edge death — and saturates rather than panics on the way down. This differs from the panic-on-violation policy for index invariants because the counter is a planner statistic, a wrong value costs a suboptimal plan but never a wrong answer, so it must degrade to a wrong estimate rather than take the database down.

Bulk deletion (delete_edges_in_txn) exists for a DELETE r statement’s whole edge set: one WriteCtx across every id, label names resolved once per distinct type rather than once per edge. It measured roughly neutral on wall time — a scattered bulk delete’s cost lives in the executor’s match phase, not here, and a tried sort-ids-into-per-table-passes variant moved nothing. Its doc comment therefore justifies the API in terms of its interface and strictly less redundant work, not a claimed speedup.

The integrity checker is the invariant spec

Reading check_integrity back to back with the mutations above is the fastest way to internalize the write path’s contract, because the checker is the invariants written down as executable prose:

• both interning tables are exact inverses, with equal entry counts;
• every label id referenced by any node or edge record resolves;
• every label-index entry points at a live node that carries the label — and every node’s every label has its index entry (both directions);
• every edge’s endpoints are live nodes;
• every edge appears in both adjacency mirrors under the right key — and every adjacency entry corresponds to a live edge with matching header;
• id counters are at or above the maximum allocated id.

Note what the checker reads: node and edge headers only, never properties — the same header-only decode the delete path uses. And note its stance: any violation is CorruptData, an error, not a repair. The write path maintains these invariants by construction — every mutation and its index bookkeeping share one transaction — so a violation means a bug, and the checker’s job is to say so, not to paper over it.

Property indexes — declaration, backfill, uniqueness, and the order-preserving key encoding that makes range seeks work — get their full treatment alongside the planner in chapter 6. The next chapter climbs into marsdb-query at the top: how Cypher text becomes a validated AST.

The Query Frontend

Everything between Cypher text and a validated, executable AST lives at the top of marsdb-query: an ANTLR grammar (grammar/CypherLexer.g4, grammar/CypherParser.g4), the generated parser (src/generated/), a visitor that builds the AST (antlr_visitor.rs, the largest file in the frontend), parameter substitution (params.rs), and a semantic validation pass (semantic.rs). The public surface is three functions: parse (one statement), parse_many (a ;-separated script), and substitute_params.

flowchart LR
    T["Cypher text"] --> L["Generated lexer/parser\n(ANTLR, committed)"]
    L --> PT["Parse tree"]
    PT --> V["Visitor\n(antlr_visitor.rs)"]
    V --> AST["AST\n(ast.rs)"]
    AST --> P["substitute_params\n$name → Literal, in place"]
    P --> SV["validate_statement\nnames + structural kinds"]
    SV --> EX["Executor\n(never sees a $param)"]

Grammar and parse tree

The grammar is a hand-maintained openCypher subset split conventionally into lexer and parser files, compiled by ANTLR into a Rust lexer/parser pair that is generated ahead of time and committed — building MarsDB does not require a Java toolchain.

The AST builder implements ANTLR’s generated visitor trait rather than manually walking parse-tree accessors. The difference matters for alternation-heavy grammars: a rule like literal : boolLit | numLit | NULL | stringLit | listLit | mapLit would otherwise need a hand-written if let Some(x) = ctx.boolLit() ... else if ... chain at every use, while the visitor’s double dispatch routes to the right visit_X method for whichever alternative is actually present. The generated trait imposes one notable constraint: a single return type for the entire tree walk, so the builder threads one shared AstNode enum through every visit method, growing a variant per AST node kind.

The AST encodes planner-relevant shape

ast.rs shows how the AST supports planning. Its Expr type distinguishes comparison shapes by what the planner can later do with them, not just by what they mean.

• Compare(prop, op, literal) — a property against a constant. This narrow shape is the only one eligible for the planner’s index-seek rewriting later.
• PropCompare(prop, op, prop) — a property against another property. Never index-eligible (there is no constant to seek), always a post-scan filter.
• GeneralCompare(expr, op, expr) — anything wider: function calls, arithmetic, bare variables. Same evaluation machinery as projection expressions, same “never index-eligible” stance.
• VarEq(a, b) — node/relationship identity comparison, distinct from comparing properties. The planner also synthesizes it for bound-variable repetition in patterns: in MATCH (a) ... OPTIONAL MATCH (b)-[:KNOWS]-(a), the second a must mean “this same node,” and VarEq is how that constraint survives into the plan.
• HasLabel(var, label) — synthesized for the second and later labels of a multi-label pattern ((n:Post:Message) — the scan handles one label, the filter checks the rest) and also written directly by users (WHERE n:Post).

A frontend that flattened all of these into one generic Compare(expr, op, expr) would be smaller — and would force the planner to re-derive, by structural inspection, exactly the distinctions the AST preserves for free. Keeping the narrow shapes narrow is what makes the later index-seek rewrite a pattern match instead of an analysis.

Desugaring happens here too, always toward fewer downstream cases: IS NOT NULL parses as Not(IsNull(..)) rather than a fourth variant; WHERE a:A:B becomes an And chain of HasLabels; a <> b becomes Not(VarEq(a, b)).

Parameters are structural, not textual

substitute_params walks the AST and replaces every Literal::Param(name) with a concrete literal from the caller’s map, in place, before execution. Two properties fall out of doing this at the AST level rather than anywhere near text:

First, injection is impossible by construction — a parameter value becomes a literal node in an already-parsed tree; there is no string context left in which it could mean anything else.

Second, the executor never sees a parameter. The substitution pass is total (a $name with no binding is an error here), so the executor’s literal evaluation treats Literal::Param as unreachable! — the invariant is enforced at the boundary and assumed thereafter, which is the same policy of surfacing invariant violations that the storage layer applies to its own invariants.

The walk itself is the mechanical price of this design: every expression-bearing position in every clause must be visited, and a new AST position means extending the walk. The compiler is the safety net — an exhaustive match over Statement fails to compile when a variant is added.

Semantic validation: what a statement can promise before running

validate_statement deliberately runs after substitution and before any storage transaction exists. It checks what is knowable from the statement alone:

• Name binding. Every referenced variable is bound by some pattern or projection before use; WITH boundaries reset scope to exactly their output; each UNION arm is scoped independently.
• Structural kinds. A small lattice — node, relationship, scalar, list-of-kind, map, path, unknown — is propagated through expressions, so MATCH (n)-[r]->() RETURN r.prop + n fails now, not mid-scan.

Some checks are deliberately deferred: property value types are data-dependent and stay runtime checks (Cypher is dynamically typed at the property level; the same n.age can be an int on one node and a string on the next). Whether COMMIT is valid right now is session state, owned by the Database layer, not a static property of the statement. And UNION’s column-compatibility rule needs each arm’s real, evaluated column list, which does not exist before execution — so that one check lives in the executor.

The pass runs unconditionally, before every execution. Keeping it storage-free is what makes that affordable: a full-workspace guarantee that no transaction is ever opened for a statement that could have been rejected by looking at it.

Statements and scripts

parse_many and split_statements handle ;-separated scripts — splitting outside string literals, parsing every statement before any runs (chapter 1 covered the execution semantics). EXPLAIN wraps any statement at the grammar level, producing Statement::Explain(inner) — which the frontend validates by validating inner, and which the executor intercepts to print a plan instead of running one; that plan rendering is chapter 6’s subject, along with the planner that produces it.

The IR and the Planner

A MATCH pattern compiles to a small tree of logical operators (ir.rs), which the planner (planner.rs) then rewrites with storage statistics in view. This chapter also covers property indexes themselves (marsdb-graph/src/index.rs), because the planner’s most important rewrites exist to exploit them.

The operator inventory

LogicalPlan has nine operators. Four are leaves — ways to produce initial rows:

• AllNodesScan — every node.
• NodeByLabelScan — every node with a label, via the label index.
• IndexSeek / IndexRangeSeek — nodes with label whose indexed property equals a value, or falls in a bounded range.
• Seed — no storage at all: start from the rows already bound by a previous part of the statement (the WITH continuation case).

One is a combined leaf-and-hop: EdgeTypeScan, a sequential sweep of the whole EDGES table that binds an entire single-hop pattern at once — more on it below. The rest transform rows: Expand (one fixed hop through adjacency), VarExpand ([:TYPE*1..3], a bounded BFS per input row), and Filter (a predicate over the bound row).

The tree shape is deliberately Gremlin-like — scans feeding expansions feeding filters — rather than Cypher-shaped, and the payoff is that “which access path” becomes a local substitution: an IndexSeek can replace a Filter-over-NodeByLabelScan without anything above it noticing.

Plan building is storage-free; rewriting is not

Planning happens in two phases with an explicit boundary.

build_match_plan runs with no storage access at all. It picks the start variable’s leaf (a Seed if the variable is already bound, else a scan), chains an Expand per hop, synthesizes filters from inline pattern properties and extra labels, and wraps remaining WHERE conjuncts around the result. Because it cannot know which indexes exist, it never emits an IndexSeek.

Then, inside the statement’s transaction — where a Txn exists and the question “is there an index on (Person, name)” has a definite answer — the rewrite passes run: apply_index_seeks and the start-point strategies. This split keeps every storage-dependent decision inside the snapshot it will execute against, and keeps the pure part unit-testable without a database.

Pattern semantics are enforced during building, and two bookkeeping sets deserve mention because they encode real Cypher rules that are easy to get wrong. Edge isomorphism: no single pattern may bind two hops to the same relationship instance — the planner threads the set of prior hops’ relationship variables into each subsequent hop (and into VarExpand’s BFS exclusion set) so a hop cannot walk back over an edge the pattern already used. Bound-variable repetition: MATCH (n)-[r]->(n) reuses n for both endpoints, which must mean “the same node” — a repeated variable gets a fresh internal name plus a synthesized VarEq filter, turning the identity constraint into ordinary predicate machinery.

Predicate pushdown

build_match_plan initially wraps the whole pattern in one Filter holding the WHERE clause. Left there, a conjunct like start.prop = 'x' in a multi-hop pattern sits above every Expand, where the index rewrite — which only inspects what is immediately under a Filter — could never see the scan it should replace. So the builder splits the predicate into top-level AND-conjuncts, and each conjunct that provably depends on only the start variable is pushed down to wrap the start node’s leaf directly.

The eligibility test (conjunct_sole_var) is deliberately narrow: it recognizes the simple leaf shapes whose variable references are manifest, and anything it does not recognize stays exactly where it was. A pushdown that guesses can change results; one that declines merely misses an optimization. The same conservatism repeats throughout the planner: every rewrite must be provably answer-preserving, and when in doubt, the plan stays naive.

Property indexes and the seek rewrite

A property index is declared per (label, property) pair, optionally unique. Its entries live in the shared PROPERTY_INDEX table under label_id ++ prop_id ++ encoded_value keys, and the value encoding is where the key implementation detail appears: an order-preserving byte encoding, so that lexicographic byte comparison equals real value ordering within a type. Signed integers get the standard sign-bit flip (mapping two’s-complement order onto unsigned big-endian byte order); floats get the sortable-float transform (flip the sign bit for non-negatives, flip every bit for negatives); strings are raw UTF-8 (codepoint order — the “close enough without ICU collation” trade-off most embedded databases take); a leading type tag keeps different types from interleaving. This is what makes IndexRangeSeek a contiguous key-range scan rather than a full-index walk: WHERE n.year > 2000 becomes byte bounds.

flowchart LR
    subgraph before["Before (storage-free build)"]
        F1["Filter\nn.name = 'Alice' AND n.age > 30"]
        S1["NodeByLabelScan\nn : Person"]
        F1 --> S1
    end
    subgraph after["After apply_index_seeks (inside the txn)"]
        F2["Filter\nn.age > 30   (residual)"]
        S2["IndexSeek\n(Person, name) = 'Alice'"]
        F2 --> S2
    end
    before ==>|"index on (Person, name) exists"| after

apply_index_seeks rewrites Filter(n.prop = literal) over NodeByLabelScan(n, Label) into IndexSeek when INDEX_DEFS says an index exists — and this is why the AST’s narrow Compare(prop, op, literal) shape from chapter 5 matters: the rewrite is a pattern match on exactly that shape. The consumed conjunct is removed and the rest of the predicate is rebuilt above the seek. Range predicates rewrite similarly into IndexRangeSeek, with one correctness condition: for numeric bounds the storage lookup returns a superset (both int and float type regions, lossy conversions widened outward), so the originating conjuncts always survive as a residual Filter — the seek narrows, the filter remains the source of truth.

Choosing where to start

For a pattern like MATCH (a:Common)-->(b:Rare {id: 1}), compiling left-to-right scans every Common node and expands — when starting from the one indexed Rare node and walking adjacency backwards touches only matching rows. Since ADJ_IN mirrors ADJ_OUT, the plan is direction-symmetric and the choice of anchor is purely a cost decision with identical results.

plan_reversed_pattern prices both anchorings with a two-sided estimate built entirely from O(1) statistics — label counts, the total node count, and the per-type edge counts maintained by the write path:

cost(anchor A, other B) = rows_A · (1 + filtered_A)
                        + E_A    · (1 + filtered_B)
E_A = E · rows_A / label_rows_A

The terms approximate the traversal’s work: scan the anchor’s estimated rows; evaluate the anchor’s pushed-down filter per row; walk the anchor’s share of the hop’s edges (the type’s total, prorated by how much an index narrowed the anchor’s label, under a uniform-degree assumption); evaluate the far endpoint’s stranded filter once per walked edge. Row scans, filter evaluations, and edge walks are weighted equally — not by assumption, but because the two non-scan halves were measured at ~0.66 µs and ~0.65 µs per item on a real dataset: the same order of magnitude, so unit weights are reasonable. The filtered flags credit pushable-but-unindexed predicate work (a CONTAINS, a range, a $param equality) whose selectivity is unknowable at plan time and is deliberately not guessed at. On the benchmark shape that motivated the model — 9,125 movies filtered by title CONTAINS against 671 users over 100k edges — the estimate prices the written order at 118k work items versus 200k reversed, and the written order is the measured 9x-faster execution.

Reversal fires only when the far endpoint prices strictly cheaper; ties keep written order, for determinism and because reversal is never free to reason about. And the pass disqualifies itself entirely for any pattern with a variable-length hop, a named path, or shortestPath — those expose traversal order to the user, and a rewrite that changes observable order is not answer-preserving.

The third strategy: sweep the edges

Some single-hop shapes defeat both anchorings — bulk operations like MATCH (a)-[r:RATED]->(b) WHERE r.rating < 2 DELETE r, where any node-side anchor walks enormous adjacency with a per-edge storage get. plan_edge_scan prices a third option: one sequential sweep of the EDGES table, evaluating the relationship predicate directly from each swept record’s bytes — no adjacency, no per-edge point gets. Sequential-versus-random is the whole story: a warm sweep of 166k edge records, per-record predicate decode included, measured ~5–6 ms against ~110 ms for the same edges through per-edge adjacency gets.

Eligibility is the planner’s conservatism at its most explicit: exactly one fixed hop, a written direction, all three variables fresh, at most one label per endpoint, and at least one conjunct on the relationship variable that the sweep can decide from raw bytes with a definite answer. That last clause has a three-valued-logic subtlety: NOT is admitted only over IS NULL, because negating a comparison whose unknown collapsed to false would flip unknowns to true — which Cypher forbids. The cost gate compares the O(1) edge count against the best anchored estimate; everything the sweep cannot decide stays in a residual Filter above.

EXPLAIN

EXPLAIN <statement> runs the frontend and both planning phases — inside a real transaction, so index checks and statistics behave exactly as execution would — and renders the operator tree instead of executing it. The payoff is seeing whether an IndexSeek fired and which residual Filter survived. Clause kinds that never compile to a LogicalPlan (UNWIND, WITH, CREATE — row operations with no traversal shape, and MERGE, whose match-half plan depends on each row’s own bindings) print one-line labels, with binding scope still threaded through them so a MATCH after them explains with the right Seed-versus-scan choice.

The next chapter is the executor: what actually happens when this tree runs.

The Executor

The executor (marsdb-query/src/executor.rs, plus four helper modules for arithmetic, scalar functions, temporal functions, and value comparison) turns a logical plan into rows and applies everything the plan does not cover: projection, aggregation, ordering, write clauses, and the enforcement of execution bounds. It is the largest component in MarsDB, and the reason is not algorithmic sophistication — it is that it implements most of Cypher’s detailed semantics.

Rows and bindings

The unit of data flow is a BindingRow: a map from variable name to Binding, where a binding is a node reference, an edge reference, a computed value, a list, or a path. Operators take a vector of rows and produce a vector of rows; a scan produces one row per node, an Expand produces zero or more successor rows per input row, a Filter drops rows. Nodes and edges travel as ids, not materialized records — properties are fetched on demand through the single-property read path from chapter 3, which is exactly why that path’s performance matters.

Two hidden binding keys never visible to user Cypher do structural work: one correlates OPTIONAL MATCH result rows back to the outer row that seeded them (so left-outer null-padding can be applied to precisely the outer rows that matched nothing), and one tags whether a MERGE row came from the create path or the match path, consumed and stripped before the row becomes visible — that is how ON CREATE SET and ON MATCH SET know which branch each row took.

flowchart TD
    scan["NodeByLabelScan a:Person\none row per node"] --> f1["Filter\na.name = 'Alice'"]
    f1 --> ex["Expand a -[:KNOWS]-> b\nprefix range over ADJ_OUT\n0..n successor rows per input row"]
    ex --> f2["Filter\nb.age > 30\n(property fetched by id, on demand)"]
    f2 --> tail["Tail: project / aggregate / order / write clauses"]
    guard["ExecutionGuard\ncancel · deadline · row + expansion limits"] -.->|checkpoints inside every loop| scan
    guard -.-> ex
    guard -.-> tail

Walking the plan

Plan evaluation is a recursive walk. Scans iterate NODES, the label index, or a property-index lookup; Expand turns each input row’s bound node into a prefix range over ADJ_OUT or ADJ_IN (both, with dedup by edge id, for undirected hops) using the bounds functions from chapter 3. VarExpand runs a bounded BFS per input row, threading the pattern-wide excluded-edge set that enforces edge isomorphism across hops.

OPTIONAL MATCH wraps its whole sub-plan in left-outer semantics: outer rows that produced matches keep them; outer rows that produced none are padded with Null for exactly the variables the optional pattern would have newly bound — a repeated variable keeps its existing binding, which is what makes OPTIONAL MATCH (a)-[r]->(b) with an already-bound a mean “extend this a, or null out r and b.”

Bounded execution

Every long-running loop in the walk calls into an ExecutionGuard, which enforces the caller’s ExecutionOptions cooperatively:

• Cancellation — a cloneable token backed by an atomic bool, flippable from another thread; the guard checks it at loop checkpoints.
• Timeout — a deadline computed once, compared at the same checkpoints.
• Row and expansion limits — intermediate-row count, result-row count, and a relationship-expansion counter that increments per adjacency entry walked.

The design point is where these are checked: during plan evaluation, not after materialization. A runaway MATCH (a)-->(b)-->(c) errors when it exceeds the bound, instead of building an unbounded intermediate result first and truncating it after the memory damage is done. There is no preemption and no watchdog thread — the same no-background-threads rule as everywhere else — so bounds are as granular as the checkpoints, which is the inherent cost of cooperative enforcement.

The guard carries one more piece of state with a story: a map of deleted edge ids to their type names. Cypher permits type(r) to be read after DELETE r earlier in the same statement — a relationship’s type is immutable for its lifetime, so it needs no live record — while reading a deleted edge’s properties is an error. The delete path records each edge’s type just before removal, and type() falls back to that map only when the live lookup fails. This is the kind of semantic detail that no amount of first-principles design produces; it came from conformance testing, and the code comment cites the exact test scenarios.

Expressions and three-valued logic

Predicate and projection evaluation implement Cypher’s SQL-style three-valued logic: a comparison involving null is unknown, unknown propagates through AND/OR by the usual truth tables, and a WHERE keeps only rows whose predicate is definitely true. The planner chapter already showed one place this bites (a NOT over a collapsed-to-false unknown would flip it to true); the executor is where the discipline is enforced uniformly, in the value-comparison module every operator shares.

Values are dynamically typed, and type errors are runtime errors by design (chapter 5’s semantic pass checks only structural kinds). Comparison across incompatible types is false rather than an error — matching Cypher — while arithmetic on wrong types errors with a typed QueryError::Type.

Aggregation

Cypher has no GROUP BY keyword: in an aggregating RETURN or WITH, the non-aggregate items are the grouping key. The executor folds rows into groups keyed by those items’ values, driving one accumulator per aggregate item per group — count, sum, avg, min, max, collect, with DISTINCT variants tracked per accumulator.

Grouping needs hashable keys, and MarsDB’s value type cannot derive Eq/Hash — it contains f64, which Rust’s standard library correctly refuses to hash (IEEE floats have no reflexive equality). The solution is a parallel HashKey type that hashes floats by bit pattern, with the trade-offs documented at the definition: ordinary float grouping is unaffected (equal floats have equal bits), while at the edges NaN groups with NaN (unlike IEEE NaN != NaN) and +0.0/-0.0 land in distinct groups. Nodes and edges hash by id — graph identity, consistent with equality elsewhere. DISTINCT’s seen-set uses the same type: same problem, same fix, one definition.

The two output lanes

Materialized execution — the default — produces a QueryResult: column names, rows of values, and per-statement write statistics. ORDER BY, SKIP, LIMIT, and DISTINCT apply at this stage, against projected columns (which is why an ORDER BY key can reference a projection alias).

The streaming lane (execute_streaming_with_options) pushes rows one at a time into a caller-supplied sink, with bounded memory regardless of result size. Its contract is strict by design: it accepts exactly the shapes that can stream without materialization — a single plain MATCH ... RETURN, SKIP/LIMIT permitted — and errors on ORDER BY, aggregation, DISTINCT, or WITH. Those constructs must see every row before emitting any; silently materializing them would violate the API’s bounded-memory contract, so MarsDB prefers a refusal over a lie. Row-count limits double as early termination: a sink that returns “stop” ends the scan.

Write clauses (CREATE, MERGE, SET, DELETE, REMOVE) execute against the same row stream — for each row the pattern bound, apply the mutation through the _in_txn layer from chapter 4, inside the statement’s one transaction — and count their effects into the statement’s QueryStats.

The next chapter follows a finished result out of the process: how rows cross the C ABI, and how they become Arrow record batches, Python objects, and Go maps without being copied more times than necessary.

Results and Language Boundaries

A query’s answer has to leave the engine — into Rust structs, C callers, Python objects, Go maps, and Arrow consumers. This chapter covers the result model (marsdb-query/src/{result,value}.rs), the C ABI (marsdb-capi), and the Arrow export (marsdb/src/arrow.rs), with an eye on the theme that shapes all of them: every boundary crossing has a cost, and the design goal is to pay each cost once.

The result model

QueryResult is columns, rows of Values, and QueryStats — the per-statement write counters (nodes and relationships created and deleted, properties set, labels added and removed) that answer “how many did my DELETE delete,” which a result’s rows alone cannot. Following the conventions of the wider graph-database ecosystem, removing a property counts as setting it (SET n.p = null and REMOVE n.p are literally the same operation internally).

Value is the query-layer value type, a superset of the storable PropertyValue: it adds whole nodes and edges, paths, and the list/map shapes that exist only at query time. The split is load-bearing. A path is a single alternating node, edge, ..., node vector — not parallel node and edge vectors, which would create an unenforced length invariant across every construction site. A map value can be projected and returned but never stored: the conversion to a storable property rejects it, keeping Cypher’s “no map properties” rule enforced at one chokepoint rather than by every write path.

The C ABI

marsdb-capi compiles to a cdylib/staticlib exposing a C API in the SQLite shape: opaque handles (MarsdbDatabase, statement, result), integer status codes, and a per-handle last_error string. The header, marsdb.h, is the documentation of record; the Rust file’s job is to keep the header’s promises. Three invariants organize the unsafe code:

• No panic crosses the boundary. Every entry point that runs engine code wraps it in catch_unwind — a Rust panic unwinding into a C caller is undefined behavior, so the boundary converts panics into error returns.
• Handles have documented lifetimes. Value handles point into a result’s rows, which are never mutated after construction; advancing to the next row invalidates them by contract (the SQLite convention), and the implementation’s per-row arenas make the contract cheap.
• Errors are pulled, not pushed. Calls return status codes; marsdb_last_error returns the message. The database handle’s error slot is behind a mutex because the header makes no single-caller promise for it.

For bulk results the ABI offers a binary batch lane: one call returns an entire result as a compact self-describing buffer — interned column and property names, varint integers — that a binding decodes in its own language. One boundary crossing per query rather than per value: the per-call FFI overhead (marshalling, error checking, in some runtimes lock acquisition) is paid once. A streaming callback lane covers the opposite shape — unbounded exports under bounded memory — pushing one row per callback through the executor’s streaming path.

Bindings layer on top: the Python binding (marsdb-python, PyO3) links the engine directly into the interpreter process, and the Go binding (marsdb-go, its own repository) consumes this C ABI through cgo. Both follow the same batch-lane strategy for results; both expose the same execution-bounds and transaction surface.

Arrow: the columnar boundary

For analytical consumers such as dataframes and columnar computation, row-oriented results are inconvenient, and per-value conversion is unnecessarily expensive. MarsDB therefore provides a core-owned Arrow export (Database::query_arrow, behind the opt-in arrow cargo feature): the row-to-column transpose happens exactly once, in the engine, and everything downstream of it is zero-copy:

• In Rust, a standard RecordBatchReader.
• Across C, the Arrow C Data Interface stream exported by marsdb-capi (marsdb_stmt_execute_arrow) — Arrow’s ABI for handing ownership of column buffers across a language boundary without serialization.
• In Python, the PyCapsule protocol: any Arrow-aware library imports the stream directly.
• In Go, arrow-go’s cdata import wraps the same stream.

The measured effect, from the Go binding on a 200k-row, three-column result: the batch lane performs ~1.2 million binding-side allocations (83 MB) per query; the Arrow lane performs ~900 (83 KB) — wall time at parity, because engine execution dominates both, but three orders of magnitude less allocator and GC pressure. The columnar boundary’s win is the allocation profile, and it grows as the engine’s own share of the time shrinks.

flowchart LR
    R["Row-oriented QueryResult"] -->|"transpose ONCE\n(strict column inference)"| B["Arrow RecordBatches\n(engine-owned buffers)"]
    B --> RS["Rust: RecordBatchReader"]
    B --> C["C ABI: C Data Interface stream\nmarsdb_stmt_execute_arrow"]
    C --> PY["Python: PyCapsule protocol"]
    C --> GO["Go: arrow-go cdata import"]
    classDef zc stroke-dasharray: 3 3
    class RS,C,PY,GO zc
    %% dashed = zero-copy: pointer handoff, no serialization

Column typing is strict, and deliberately so. Cypher columns are dynamically typed, so the exporter infers each column’s type over the whole result — which is also why the export materializes before the first batch is handed out: inference needs every row. The rules mirror the precision discipline used everywhere else in the system: integers export as Int64 exactly; a column mixing integers and floats is an error, not a silent promotion to Float64 (which corrupts integers beyond 2^53); dates are Date32, durations are Interval(MonthDayNano), other temporals are canonical ISO text; homogeneous lists nest as List<child>; nulls become Arrow validity bits, so a column stays typed by its non-null values. Node, edge, map, and path columns are errors with an instruction — project scalar properties instead — because flattening an entity into strings would discard exactly the structure an analytical consumer would then have to re-parse.

One dependency-hygiene note: the crate re-exports its arrow-rs types for marsdb-capi and marsdb-python to consume, so no downstream crate declares its own arrow-rs dependency and no version split can produce two incompatible definitions of the same C structs.

The remaining chapters step back from the pipeline: how this system is tested and measured, and what the measurements changed.

Testing and Measurement

A database earns trust two ways: by being unable to give wrong answers, and by understanding its own performance. This chapter covers both mechanisms — the correctness stack (unit suites, conformance, crash safety, integrity) and the measurement discipline that the rest of this book has been quietly citing.

The correctness stack

Unit and end-to-end suites live where the code lives: storage and graph invariants in marsdb-graph’s tests, query shape and mechanics in marsdb-query’s, and full workloads at the marsdb crate level — including a suite that runs the LDBC Social Network Benchmark’s short-read queries via real parameter substitution against a shared fixture, asserting exact results, not “doesn’t panic.” Stress tests (50k-node chains, 10k-fanout supernodes with detach-delete, 20k random operations checked against an in-memory oracle) are #[ignore]d by default and run explicitly.

Conformance is the openCypher TCK, run by marsdb-tck: a harness that parses the official Gherkin feature files (vendored as a git submodule), builds each scenario’s initial graph, runs the scenario’s query, and compares against the expected table with TCK value semantics. Every scenario lands in one of five outcomes — pass, wrong result, unexpected behavior, parse-rejected, or runner-unsupported — because “how it fails” is more informative than a pass rate alone: a wrong result is a correctness bug; a clean parse rejection of an unimplemented feature is a scope decision. MarsDB currently passes 3,880 of 3,880 scenarios, and the coverage table (CYPHER_COVERAGE.md) is generated from real runs, not maintained by hand.

The TCK’s deepest value showed up in this book repeatedly without being named: several of the subtlest behaviors in the executor — type(r) surviving DELETE r, edge isomorphism reaching across a pattern into a variable-length hop’s BFS, MERGE accepting a bound-variable property — were found by scenarios, and the code comments cite the exact ones. A conformance suite is a machine-checkable spec, and its scenarios reach corners that first-principles test-writing does not.

Crash safety has its own harness (marsdb-crash-harness), and its scope is stated in its module docs: this is level-1 crash safety — process death while the OS survives and the page cache remains intact — and explicitly not power loss (which loses the page cache and would need fault injection to test). Within that scope, a child process commits a random number of single-CREATE transactions with a monotonically numbered counter; the parent SIGKILLs it at an unpredictable moment, reopens the file cold, and asserts a purely structural invariant — the surviving counter values must be exactly a contiguous prefix {1..K}. No gaps (no half-applied transaction), no duplicates (no doubly-recorded commit). The parent never synchronizes with the child’s commit progress, because the invariant holds regardless of where the kill lands — an assertion designed so that racing is not a bug in the test.

The integrity checker (chapter 4) doubles as the final oracle: stress and crash tests can end with a full logical validation of every cross-table invariant, converting “the test passed” into “and the file is coherent.”

The measurement discipline

BENCHMARKS.md is the repository’s ledger of numbers, and its rules are as much a part of the engineering culture as any code:

• Only measured numbers. Nothing is estimated, extrapolated, or “expected to be fast.” A feature without a benchmark has no performance claim — the file has no placeholder rows.
• Provenance on every number. Hardware, date, build profile, and the exact reproduction command (cargo bench -p ..., using Criterion) accompany each table.
• Caveats are stated, not buried. The concurrent-read scaling table (1.26x at 2 threads up to 1.87x at 8, then a plateau) is followed by two known unisolated factors that may cap it, and the conclusion is scoped to what the data supports: concurrency reliably beats sequential, which is what the feature is for. An explicit “scope of these numbers” section lists what has not been measured — file-backed fsync-pressure throughput, unbenchmarked operators — so absence of evidence is visible instead of silent.
• End-to-end checks bracket the micro-benchmarks. A real dataset (28,863 nodes, 166,261 relationships, loaded from plain Cypher) is the load/query/update/delete lifecycle gate, re-run as internals change; micro-benchmarks alone can miss regressions that only compose at scale.

The payoff of running real workloads is not just numbers — it is bug discovery. The lifecycle benchmark directly surfaced two planner defects (an IndexSeek that never fired for row- and parameter-bound equalities, and a multi-hop pattern’s start-node WHERE never reaching the scan it should narrow), both fixed because a measurement looked wrong. A benchmark suite that only confirms expectations is underused.

Continuous integration

CI runs the test suite on Linux, macOS, and Windows; formatting and clippy as a gate; coverage collection; a dependency security audit; and a bindings job that builds the Python extension and runs its tests against the workspace — plus a build of the C ABI with the Arrow feature, which is the pre-merge check protecting the out-of-repo Go binding (its own CI builds this repository’s C ABI from main and would otherwise discover breakage only after merge).

The final chapter collects the measurements that changed decisions — including those that led to a feature’s removal.

Case Studies in Measured Trade-offs

Every chapter so far has cited measurements in passing. This one collects the decisions those measurements drove — features kept or removed and intuitions overturned — because together they reveal this codebase’s engineering methodology:

Knowing the mechanism tells you the direction of an effect. Only measuring tells you the magnitude — and magnitude is what decides whether the complexity pays.

The label index: a trade, not a win

The label index (label_id -> node_ids) turns a label-filtered scan into an index lookup plus one point-get per match. At 1% selectivity it is roughly 30–80x faster than the full scan (801 µs versus ~7 ms at comparable sizes, staying near-flat per matching row as the table grows). The same benchmark run recorded the costs: every create_node pays an extra index write, and a scan whose label matches every row is slower through the index than a single sequential pass — N point-gets lose to one sweep when N is the whole table. The index shipped because the common query shape benefits from it, while BENCHMARKS.md records both the read benefit and the write and full-scan costs.

An automated review bot later suggested making the index’s read path defensive — silently skipping index entries pointing at missing nodes. The suggestion was rejected on invariant grounds (chapter 4: the entry cannot dangle by construction, and if it ever does, that is corruption that should produce an error rather than be silently ignored).

Fixed-width keys: the erasure tax

Chapter 2’s adjacency layout depends on a result that was not apparent from the design alone: encoding the composite key as a packed byte string instead of a native fixed-width tuple doubled the database file in one measurement, and a related erasure to &[u8] measured +34% — redb keeps fixed-width tuple keys in fixed slots, and byte-erasing them forfeits that packing. The first cut of the composite-key change made exactly this mistake, and the number is what sent it back.

The record directory: optimize the read you actually do

The directory encoding (chapter 3) beat whole-record decoding by 79x for reading one property of twenty — and by 7x even at full materialization, which is the surprise half: the directory was designed for partial reads, but eliminating per-property name allocation and map construction won even the case the old format was supposedly good at. The supporting measurement that shaped the implementation: table-handle opens were 23.67% of a bulk load, which is why decode resolvers hold one handle across a record rather than opening per property.

WriteCtx: the tidy version was slower

Caching table handles per write operation (chapter 4) had an eager variant — open all thirteen handles up front — that was strictly simpler and benchmarked worse than the code it replaced: 4.89 s to 6.35 s on the 9,771-statement load. Most operations touch a handful of tables, and opening the unused handles cost more than the redundant opens the cache saved. The lazy variant kept the win. The lesson generalizes: an optimization’s overhead lives on the same axis as its savings, and only the measured difference says which dominates.

Start-point reversal: pricing the plan, then checking the price

The planner’s anchor-cost model (chapter 6) exists because one query shape — a huge filtered label against a small far endpoint — was 9x faster in written order than reversed, while a naive row-count-comparison rule reversed it. The model’s unit weights are themselves measured (~0.66 µs per filter evaluation, ~0.65 µs per edge walk — the same order of magnitude, so equal weights are reasonable), and its verdict on the motivating query (118k work items written versus 200k reversed) agrees with the observed 9x difference. A cost model is a hypothesis; this one had to explain an existing measurement before it was trusted.

The edge sweep: sequential beats clever

EdgeTypeScan (chapter 6) earns its place with one comparison: a warm sequential sweep of 166k edge records — per-record predicate decode included — costs ~5–6 ms, where the same edges through per-edge adjacency point lookups cost ~110 ms: a twenty-fold difference from the access pattern alone. The operator’s narrow eligibility rules are the other half of the lesson: a 20x mechanism is only worth having if every shape it is allowed to run on provably preserves answers.

Group commit: the knee is early

The grouped batch loader (chapter 1) commits every N statements. The measurement that set the guidance: 69.1 s per-statement, 13.4 s at groups of 100, 12.1 s committing the entire 9,771-statement script once. The fsync amortization is nearly exhausted by a few hundred statements per group — so the documentation recommends modest groups, which also keep the crash-loss window small. Without the three-point curve, the natural instinct (“bigger groups, faster load”) would trade durability granularity for a win that mostly is not there.

The optimization that was removed

A row-representation optimization for the executor’s binding rows was fully implemented and benchmarked end to end — and moved the numbers by roughly 2%. The profile said why: read cost in the affected workloads is dominated by node decoding and traversal, not by the representation of result rows. The change was reverted, not shipped — carrying permanent complexity for two points is a losing trade — and the measurement was kept: knowing where the cost is not is what directed later work at the decode and traversal paths, where the directory encoding and the edge sweep found their wins.

A database, like any long-lived system, is shaped as much by the features it declined to keep as by the ones it kept.

Neutral results get recorded too

The bulk edge-delete API (chapter 4) measured approximately neutral on wall time — the cost of a scattered bulk delete lives in the match phase, and a tried sort-into-per-table-passes variant moved nothing. The function stayed, justified in its doc comment by API shape and strictly less redundant work, with the neutral measurement stated rather than implied away. Recording “this did not help” is what makes the next engineer’s search space smaller; a ledger that only lists wins teaches nothing about where wins are not.

That closes the internals tour. The map, once more, in one breath: a single redb file holding records, mirrored adjacency, and indexes; a statement pipeline from ANTLR grammar through a validated AST to a traversal-shaped plan, rewritten against real statistics inside its own transaction; an executor that enforces Cypher’s semantics under cooperative bounds; results that cross each language boundary once; supported by a conformance suite, a crash harness, and a record of benchmark results used to evaluate design changes.