How the SQL Engine Works

OxiDB's SQL engine is a standalone relational engine — its own crate, its own files, zero shared state with the document engine. This article walks through what actually happens between SELECT arriving on the wire and rows coming back: parsing, execution, storage, transactions, locking, crash recovery — and the things the engine deliberately does not do. Everything here describes the code as it ships; where there is a trade-off, the trade-off is stated.

The shape of the thing

The engine mounts beside the document engine in the same server process, off by default (OXIDB_SQL=1). A request tagged engine: "sql" routes to it; everything else takes the document path untouched. A SQL table and a document collection can share a name and never meet — they live in different directories with different formats.

{ "engine": "sql", "cmd": "sql",
  "sql": "SELECT * FROM products WHERE id = $1",
  "params": [42] }

Each database gets its own engine instance (the default at ${OXIDB_DATA}/sql, named databases at ${OXIDB_DATA}/<name>/sql). One instance is a single shared handle: a mutex-guarded core holding the catalog, the tables, and the WAL, plus a session-transaction registry and a row-lock table beside it.

Life of a query

1. Parse. The SQL text goes through sqlparser's generic grammar, and the resulting syntax tree is translated into the engine's own logical AST. Translation is where honesty is enforced: anything the executor cannot actually do — an unsupported locking clause, an exotic query body — is rejected by name at this stage rather than accepted and quietly mis-executed. A few shapes the grammar cannot express (EF Core's CREATE SEQUENCE, SELECT NEXT VALUE FOR, SHOW INDEXES) are recognized as raw text before the parser sees them.

2. Cache. Text → AST is a pure function, so parsed statements are cached (up to 512 texts, whole-map drop past that). Applications loop over a small set of parameterized texts; parsing costs more than cloning an AST, so repeat statements skip the parser entirely. Parameters (? / $N) bind at execution, not parse, which is what makes the cache safe.

3. Rewrite at parse time. Non-recursive CTEs are inlined as derived tables — a CTE referenced twice is inlined twice, and the executor never knows it existed. A WITH RECURSIVE CTE is split into its anchor and step arms and materialized later by fixpoint iteration: the step re-runs with the CTE bound to the previous round's rows until nothing new appears, with guards at 1M iterations / 10M rows so a cyclic step terminates.

4. Execute. The executor is written against a small Store trait — scan, point-lookup, insert, update, delete, lock — with two implementations: the engine itself (autocommit: every operation applies and logs immediately) and a transaction (everything buffers in an overlay; more below). The same executor code serves both, which is why transactional and autocommit SQL cannot drift apart semantically.

Finding rows without scanning everything

There is no cost-based optimizer, and that is a deliberate size-and-predictability choice. Instead there is a short list of mechanical pruning rules that cover the shapes real applications send:

• Equality conjuncts use indexes. A WHERE clause is decomposed into its top-level ANDed equality tests; if a secondary index (or the primary key map) covers them, the scan collapses to an index lookup.
• Index-nested-loop joins. When the outer side of a join is small and the inner side has an index on the join key, the engine probes the index per outer row instead of scanning the inner table — with a hard cap on the outer size so the strategy can never be worse than the scan it replaces.
• Short-circuit logic. AND/OR stop evaluating when the answer is decided; STARTS_WITH/ENDS_WITH compare borrowed bytes in place (they exist because ordinal affix tests otherwise rendered as per-row SUBSTRING + LENGTH).

Expression evaluation itself is a borrowed-value tree walk. A stack-machine expression compiler was built, measured, and reverted: against an evaluator that already avoids cloning, compilation was net-negative. The lesson stuck — the engine optimizes what profiling shows, not what folklore suggests.

Where rows live

Every table is a TableState: rows addressed by an internal row id, a primary-key map for point lookups, and secondary indexes rebuilt at open. Rows are held one of two ways:

• Resident (default): all rows in memory, reads are direct.
• Disk-first (OXIDB_SQL_DISK_FIRST=1): the bulk of each table stays in its last-checkpoint snapshot file, memory-mapped; only rows changed since that checkpoint live in RAM. Resident memory tracks the write rate, not the table size.

Durability: a WAL and a MANIFEST

The write path is conventional and boring on purpose. Every mutation appends a CRC-framed, sequence-numbered record to a single live WAL file. A transaction's operations travel as one batch record — one append, one fsync, all-or-nothing on recovery.

Checkpoints are where it gets interesting. A checkpoint writes a whole new generation into its own directory — gen.N/ holding a catalog.json and one row-snapshot file per table — fsyncs it all, and then promotes it by atomically renaming a tiny MANIFEST file recording {generation, wal_seq} into place. That rename is the single commit point:

• Crash before the rename → the previous MANIFEST, and therefore the previous intact generation, is still in force. The half-written gen.N/ is swept at the next open.
• Crash after → the new generation is live, and recovery replays only WAL records past the recorded wal_seq watermark — so a not-yet-truncated WAL can never double-apply a checkpointed, non-idempotent operation like ALTER TABLE.

Because the catalog and the row snapshots switch together, their arities can never disagree after a crash — the failure mode the old overwrite-in-place layout actually had. One deliberate exception: sequences live in their own sequences.json, saved on every NEXT VALUE FOR — far more often than a checkpoint — because a handed-out sequence value must never be re-issued, even if the transaction that took it rolled back.

Transactions: an overlay, not a version store

A transaction buffers everything — row changes, created/dropped tables, index DDL, uniqueness state — in an in-memory overlay over the committed engine state. Its own reads see the overlay first (read-your-writes); the engine's committed state is untouched until commit. COMMIT hands the buffered operations to the engine as one atomic WAL batch; dropping the transaction (explicit ROLLBACK, a failed statement, a vanished connection) discards the overlay. SAVEPOINT is a snapshot of the overlay's data, and rolling back to one restores it without touching the engine.

Interactive transactions survive across wire calls by being parked: between requests the overlay sits in a registry keyed by a session id, and the next statement resumes it. Uniqueness checks probe the engine's persistent maps through the overlay, so their cost scales with the transaction's writes, never with table size.

Row locks and SELECT ... FOR UPDATE

Concurrency control is pessimistic and lock-based. A Condvar lock table maps (table, row id) to an owner — an open transaction, or an ephemeral autocommit statement:

• SELECT ... FOR UPDATE locks every matched row until commit/rollback, re-evaluating the match to a fixpoint (the matched set can change while waiting on a contended row). Only a plain single-table SELECT qualifies; joins, aggregates, DISTINCT, set operations, views and derived tables are refused by name — a locking clause that does not lock is worse than none.
• Plain UPDATE/DELETE take the same locks before mutating, so two concurrent read-modify-write transactions on one row serialize instead of losing a write.
• Waiting always happens with the engine mutex released — the lock holder needs that mutex to commit and let the waiter proceed. Deadlocks are not detected; they resolve as a lock timeout on one side (OXIDB_SQL_LOCK_TIMEOUT_MS, default 5000), which aborts that statement's transaction.

What isolation you actually get

That is READ COMMITTED — the same default contract PostgreSQL ships with — plus pessimistic upgrades where you ask for them. There is no MVCC: no row version chains, no snapshot timestamps, no vacuum. This is a considered position, not an omission. The engine's one non-negotiable asset is provable simplicity — a buffered overlay committed as one WAL batch is something crash tests can corner — and its readers already never block on writers, which is the benefit MVCC is usually bought for. Snapshot isolation would cost version-chain memory, visibility rules and garbage collection, for a guarantee its real workloads (EF Core applications, short transactions) have not asked for.

Instant ALTER TABLE — the 500M-row problem

ADD COLUMN and DROP COLUMN are O(1): no row rewrite, no checkpoint, no downtime, regardless of table size. The trick is a split between physical and logical schema. The catalog stores the physical truth; the executor only ever sees a logical view:

• ADD appends a slot to the physical schema. Old rows, which are physically short, read back padded with the new column's default. Nothing on disk moves.
• DROP tombstones the column in place (the same idea as Postgres's attisdropped). The physical cell stays in every row; reads project it out, writes fill it with a placeholder.
• Durability rides on the WAL record alone. The next ordinary checkpoint — which rewrites every row anyway — compacts: rows are rewritten to the live columns and the tombstones leave the catalog. The deferred O(n) cost is folded into work that was already being paid.

Stored procedures: two languages, one rule

CREATE PROCEDURE ... AS BEGIN ... END stores SQL text, re-parsed per CALL — zero toolchain. LANGUAGE COBRA stores compiled bytecode run by an in-server VM: the procedure defines run(db, ...params), its queries join the CALL's transaction, and determinism is validated at CREATE — async, imports and I/O are rejected up front, with a 100M-instruction fuel cap at runtime. The rule behind both: a CALL must be safe to replicate, so a procedure may compute, read and write — and nothing else.

In a cluster

SQL writes replicate through Raft as statements: the server classifies each statement by parsing it, and anything that is not read-only ships to the group. SELECT ... FOR UPDATE deliberately classifies as a write — routed to a replica, its lock would be theater. Read-only SQL runs node-locally (a replica, when the pool has one). The engine is not sharded: oxipool shards by collection and shard key, which a SQL statement does not have, so SQL routes to one backend rather than scattering.

Backup without stopping

backup holds the engine lock for two O(1) moments — pin the committed generation, note the WAL length, unpin at the end — and runs the slow tar/compress with the lock released. A pinned generation is safe from GC and freezes WAL truncation, so the archive (a synthesized MANIFEST, the pinned gen.N/, a stable WAL prefix, sequences.json) is crash-consistent as of the pin instant while writes and auto-checkpoints continue around it.

Proof over promises

The engine's conformance claim is not self-graded: it runs the official EF Core relational specification suite — all twelve Northwind suites, over the wire — at 3832/3832 green. Where behavior had to be pinned down (case-insensitive LIKE, COLLATE, VALUES table constructors, multi-level correlated subqueries), the spec run is what forced the decision. And where it competes, it measures: against PostgreSQL over the same EF Core provider it wins most benchmark shapes — with the loss analysis published alongside the wins, including the one that turned out to be a bias in the benchmark harness rather than the engine.

Reference of the SQL surface itself — DDL, joins, CTEs, window functions, set operations — lives on the SQL page. The transaction wire protocol and session semantics are on the server page.