README.md

September 10, 2026 · View on GitHub

FrankenSQLite

An independent ground-up Rust reimplementation of SQLite with page-level MVCC concurrent-writer support.

TL;DR

The Problem: SQLite allows only one writer at a time. A single lock byte (WAL_WRITE_LOCK at wal.c:3698) serializes all writers. For write-heavy workloads, this bottleneck caps throughput regardless of how many cores you have. Torn writes and bit-flips can corrupt the database with no self-repair mechanism.

The Solution: FrankenSQLite reimplements SQLite from scratch in Rust, with a safe engine core and two architectural innovations:

MVCC Concurrent Writers. The single-writer lock is replaced with page-level Multi-Version Concurrency Control. Writers that touch different pages can overlap their page work, while commit validation and publication still contain coordinated sections. Serializable Snapshot Isolation (SSI) tracks write-skew dependencies by default. A safe write-merge ladder (intent replay + structured page patches) is present as dormant/tested implementation work but is not yet wired into the live commit path; current same-page base drift aborts and retries.
RaptorQ Durability Research. The workspace contains RaptorQ/ECS building blocks and partial native-mode integration. The live compatibility runtime does not yet justify a blanket self-healing or numeric durability claim; the native-mode sections below are design plus partial implementation and are gated on end-to-end recovery evidence.

The current runnable engine is already real, but still hybrid. Compatibility mode over standard SQLite files is the live runtime path today. Database text encodings UTF-8 (encoding 1) and UTF-16le/UTF-16be (encodings 2/3) are admitted for both reads and writes; UTF-16 support is newer than the long-verified UTF-8 surface, and attaching databases with mismatched encodings is rejected. Native mode / ECS sections below describe the longer-term design plus partial implementation work. See "Current Implementation Status" before treating every section as present-day behavior.

Install the CLI

Linux and macOS:

curl -fsSL "https://raw.githubusercontent.com/Dicklesworthstone/frankensqlite/main/install.sh?$(date +%s)" | bash

Windows PowerShell:

irm "https://raw.githubusercontent.com/Dicklesworthstone/frankensqlite/main/install.ps1?$([DateTime]::UtcNow.Ticks)" | iex

The installers select the native release artifact, require its SHA-256 entry, authenticate the signed checksum manifest when minisign is available, and run exact-version plus SQL smoke tests before reporting success. The Linux artifacts are fully static so the same downloads work on glibc- and musl-based distributions. Exact-version, air-gapped, custom-destination, source-build, and post-install verification controls are documented by install.sh --help and Get-Help ./install.ps1 -Detailed. Rust users can instead install the CLI with cargo +nightly install fsqlite-cli --locked (the workspace builds on the dated nightly toolchain pinned in rust-toolchain.toml). Prebuilt installer support covers v0.1.16-v0.1.17 and resumes with v0.2.0; v0.1.18-v0.1.19 did not publish native signed artifact sets. When minisign is present, a missing or invalid signature fails closed rather than silently downgrading authenticity.

Why FrankenSQLite?

Feature	C SQLite	FrankenSQLite
Concurrent writers	1 (file-level lock)	Many by design (page-level MVCC with SSI); full concurrent-writer certification remains gated on the correctness gates below
Isolation level	SERIALIZABLE (by serializing)	SERIALIZABLE (SSI for concurrent mode)
Concurrent readers	Many (WAL; 5 read-mark slots by default)	Many (Compat: same 5 read-mark slots; Native: bounded by txn-slot capacity, no WAL-index cap)
Memory safety	Manual (C)	Core engine is safe Rust; `unsafe` is limited to `fsqlite-vfs` (mmap/shm) and the optional `fsqlite-c-api` shim (FFI)
Data races	Possible (careful C)	Prevented inside the Rust engine by ownership and type-system checks
File format	SQLite 3.x	SQLite 3.x layout; UTF-8 and UTF-16le/be text encodings are admitted for reads and writes, with parity verification deepest on the UTF-8 surface
Self-healing storage	No	Native file-backed connections can generate WAL repair symbols asynchronously; automatic FEC recovery is not wired to the compatibility WAL reader
Page-level encryption	No (commercial SEE extension)	Not currently available: the XChaCha20-Poly1305 DEK/KEK implementation exists in `fsqlite-pager`, but no `PRAGMA key`/`rekey` dispatch is wired into `Connection`
SQL dialect	Full	Large and growing subset; parser coverage exceeds full execution parity today
Extensions	FTS3/4/5, R-tree, JSON1, etc.	Extension crates are present; some runtime wiring is still in progress
Cross-process MVCC	No	Partial (shared-memory coordination, bounded by the measured harness scale)
Embedded, zero-config	Yes	Yes

Design Philosophy

1. Independent Reimplementation, Not a Translation

FrankenSQLite is not a C-to-Rust transpilation. It references the C source only for behavioral specification. Every function is written in idiomatic Rust, using the type system and ownership model rather than translating C idioms.

2. MVCC at Page Granularity

Page-level versioning sits at the right point in the complexity/concurrency tradeoff:

Row-level (PostgreSQL-style) would break the file format and require VACUUM
Table-level would conflict on every write to a shared table
Page-level maps naturally to SQLite's B-tree structure. Writers to different leaf pages can perform page-version work concurrently. Commit publication still coordinates shared metadata, and transactions can also retry because of SSI dependencies or structural B-tree overlap.

3. Safe Rust Engine Core

Most of the workspace inherits unsafe_code = "forbid" from the root Cargo workspace lints, so the engine, pager, parser, VDBE, and surrounding Rust crates stay in safe Rust. Two crates override this locally: fsqlite-vfs (mmap and shared-memory regions require raw pointers) and the optional fsqlite-c-api (FFI boundary for a SQLite-compatible C ABI). If you use FrankenSQLite through the Rust crates or the CLI, you never need the C ABI shim at all. The design goal is to keep unsafe surface minimal and the engine itself in safe Rust.

4. File Format Compatibility Is Non-Negotiable

Compatibility with existing SQLite databases is a core goal of the current runtime. FrankenSQLite is built around standard .db plus rollback-journal/WAL files, and a major part of the harness exists to drive byte- and behavior-level parity against C SQLite. The runtime admits databases whose header declares encoding 1 (UTF-8) or encodings 2/3 (UTF-16le/UTF-16be) for both reads and writes. Parity verification is deepest on the UTF-8 surface; UTF-16 coverage is newer and remains an active verification track rather than a claim that every edge is already finished.

5. Serializable Snapshot Isolation (SSI) by Default

BEGIN CONCURRENT targets SERIALIZABLE isolation rather than merely Snapshot Isolation. The conservative Cahill/Fekete rule applied at page granularity ("Page-SSI") rejects a transaction that would become a dangerous rw-antidependency pivot. PostgreSQL's SSI results are useful prior art, but they do not establish FrankenSQLite's overhead; that cost remains part of this project's release benchmark matrix. PRAGMA fsqlite.serializable = OFF explicitly downgrades to plain SI for benchmarking or applications that tolerate write skew: the setting is snapped at BEGIN CONCURRENT and routes that transaction's commit through first-committer-wins validation only, skipping SSI edge validation (GH#390). When two writers touch the same page, FCW detects base drift and the current live path makes the loser retry with SQLITE_BUSY_SNAPSHOT; the safe merge ladder remains dormant. Page-lock acquisition does not wait, so it cannot form a page-lock wait-for cycle.

This guarantee belongs to the connection pipeline, which records the read/write dependencies consumed by Page-SSI. The lower-level fsqlite-mvcc::TransactionManager API does not infer those dependency flags from ordinary page reads and writes and can therefore admit classic write-skew if used by itself. It must not be treated as a serializable transaction layer (#189).

6. Strong Types Over Runtime Checks

Page numbers, transaction IDs, page sizes, error codes, opcode variants, and lock levels are all distinct Rust types (newtypes, enums), not bare integers. The compiler catches misuse that would be a runtime bug in C. A PageNumber cannot be accidentally passed where a TxnId is expected. A PageSize that isn't a power of two between 512 and 65536 cannot be constructed.

7. Layered Crate Architecture

Each subsystem lives in its own crate with explicit dependency boundaries enforced by Cargo. The parser cannot reach into the pager. The B-tree cannot call the planner. This prevents the kind of circular coupling that accumulates in a single-file C codebase and makes each component independently testable.

8. RaptorQ Native-Mode Design

The native-mode design applies RFC 6330 fountain codes to persistent objects, replication, and recovery. These sections describe design plus partial implementation; they do not claim that every compatibility-mode WAL frame or version-chain operation currently uses RaptorQ.

9. Mechanical Sympathy

Database engines live and die by cache behavior and I/O patterns. Current PageData buffers use owned Vec<u8> storage and shared Arc<[u8]> snapshots; they do not promise page_size alignment. The VFS can stage owned buffers for blocking-pool I/O, so the live path is not universally free of intermediate copies. Page-aligned buffers and reducing those copies remain performance goals, subject to actual workload measurements. The MVCC PageLockTable and SireadTable use cache-padded shards, and B-tree/codec code uses contiguous layouts where appropriate. These mechanisms are not a measured throughput claim by themselves.

Architecture

FrankenSQLite is organized as a 28-member Cargo workspace with layered dependencies:

Crate Map

Layer	Crate	Purpose
Foundation	`fsqlite-types`	PageNumber, PageSize, TxnId, SqliteValue, 190+ VDBE opcodes, serial types, limits, bitflags
	`fsqlite-error`	50+ error variants, SQLite error code mapping, recovery hints, transient detection
Storage	`fsqlite-vfs`	Virtual filesystem trait (Vfs, VfsFile) abstracting all OS operations
	`fsqlite-pager`	Page cache, rollback journal, S3-FIFO default / optional ARC eviction, dirty page write-back
	`fsqlite-wal`	Write-ahead log: frame append, checkpoint, WAL index, crash recovery
	`fsqlite-mvcc`	MVCC page versioning, snapshot management, conflict detection, epoch-based reclamation
	`fsqlite-btree`	B-tree/B+tree: cell parsing, page splitting, overflow chains, cursor navigation
SQL	`fsqlite-ast`	Typed AST nodes for all SQL statements and expressions
	`fsqlite-parser`	Hand-written statement grammar with explicit-state Pratt/SELECT parsing
	`fsqlite-planner`	Name resolution, WHERE analysis, join ordering, index selection
	`fsqlite-vdbe`	Bytecode VM: 190+ opcodes, register file, fetch-execute loop
	`fsqlite-func`	Scalar, aggregate, and window functions (abs, count, row_number, etc.)
Extensions	`fsqlite-ext-fts3`	FTS3/FTS4 query/matchinfo/offsets helpers (no virtual-table module is registered)
	`fsqlite-ext-fts5`	FTS5 with BM25 ranking
	`fsqlite-ext-rtree`	R-tree spatial indexes and geopoly scalar functions
	`fsqlite-ext-json`	JSON1 functions (extract, set, each, tree, etc.)
	`fsqlite-ext-session`	Changeset/patchset generation and application
	`fsqlite-ext-icu`	ICU collation and Unicode case folding
	`fsqlite-ext-misc`	generate_series plus misc scalars (uuid, decimal); dbstat/carray/dbpage are not implemented
Integration	`fsqlite-core`	Connection/runtime hub: parser dispatch, transaction control, schema management, VDBE bridge
	`fsqlite`	Public API: `Connection::open()`, `execute()`, `query()`, `prepare()`
	`fsqlite-cli`	Small REPL, `-c/--command`, `.read`, and decode-proof verification
	`fsqlite-observability`	Metrics, tracing, latency telemetry, conflict observability
	`fsqlite-e2e`	Differential testing, workload replay, fairness/benchmark execution
	`fsqlite-harness`	Verification/conformance/orchestration platform around the engine
	`fsqlite-c-api`	Optional C ABI shim for embedding/integration
	`fsqlite-wasm`	Experimental WebAssembly API
	`beads-doctor`	Beads database health tool

The crates/fsqlite-wasm/ crate provides experimental WebAssembly support and is included as a workspace member.

Current Implementation Status

This README describes the target end-state architecture. The runnable code today is in a hybrid state:

Public entry point: fsqlite::Connection (crates/fsqlite/src/lib.rs), implemented by fsqlite-core::Connection (crates/fsqlite-core/src/connection.rs).
Execution backend: the default table-backed path uses pager transactions plus storage cursors into the B-tree stack, executed by fsqlite-vdbe::VdbeEngine (crates/fsqlite-vdbe/src/engine.rs).
Hot compile path: fsqlite-core::Connection currently compiles most table-backed work directly through fsqlite-vdbe::codegen; the separate fsqlite-planner crate exists and is substantial, but it is not yet the primary Connection hot path for all queries.
Runtime image/fallback: fsqlite-vdbe::engine::MemDatabase is still maintained as the in-memory execution image and remains in selected compatibility/fallback paths while cutover work continues.
Persistence: for non-:memory: paths, Connection opens pager/VFS state, applies journal-mode configuration, and reloads runtime image from pager-backed data; compatibility snapshot flows remain in the codebase for specific paths.
SQL fallback boundaries: CTE/view materialization, some JOIN/GROUP BY/window-function shapes, sqlite_schema virtualization, and some INSERT ... SELECT paths still route through connection-level compatibility execution instead of fully lowered VDBE storage programs.
CLI status: fsqlite-cli is currently a small shell and command runner, not yet a full sqlite3-style front-end with the broad dot-command/output-mode surface described later in older revisions of this README.
Verification surface: most serious differential, conformance, and benchmark machinery lives in fsqlite-harness and fsqlite-e2e, not at the workspace root.
Operating modes: the current user-facing runtime is the compatibility/pager-backed path. Native-mode/ECS sections below should be read as design plus partial implementation unless explicitly called out as live behavior.
Extensions: FTS5, JSON1 (json_each/json_tree), R-tree/geopoly, ICU, and misc (generate_series) register their scalar functions and/or virtual-table modules in the live engine. FTS3/FTS4 are helper-level only — no virtual-table module is registered, so CREATE VIRTUAL TABLE ... USING fts3 (or fts4) returns a not-implemented error. The session extension is a manual library facade (see its section below). dbstat, carray, and dbpage are not implemented. Feature-gating caveat: the engine-side extension set is controlled by fsqlite-core's extensions/ext-* features, which sit in its default feature set — native deliberately does not imply them (fsqlite#356) — and the top-level fsqlite crate's json/fts5/rtree/icu/misc features forward to the matching engine registration features. With default features enabled the full built-in set is present; to strip an extension, use default-features = false on fsqlite (or fsqlite-core) and opt back into native plus the specific extension features you want.
Dormant performance machinery: the vectorized batch kernels in fsqlite-vdbe (vectorized_*.rs: hash join, sort, aggregation, morsel dispatch) are a benchmarked library with no live call sites — only the vectorized MakeRecord encoder (PRAGMA fsqlite.vectorized_makerecord, on by default) is wired; the Silo-style epoch group-commit module (fsqlite-mvcc/src/silo_epoch.rs) is an unwired scaffold; and the pattern-matching VDBE JIT is functional but off by default (PRAGMA fsqlite.jit_enable = 1 opts in; PRAGMA fsqlite_jit_stats shows whether it is engaging).
Storage stack status: fsqlite-vfs, fsqlite-pager, fsqlite-wal, fsqlite-mvcc, and fsqlite-btree are wired into default runtime execution. Remaining work focuses on removing residual fallback paths, closing opcode/behavior gaps, and finishing parity/certification tracks.
Safe write-merge ladder status: the ladder described below (intent replay + structured page patches) is design plus dormant implementation, not live commit behavior. The production commit path resolves every same-page base-drift conflict by abort/retry (SQLITE_BUSY_SNAPSHOT); the rebase and patch-merge code exists in fsqlite-mvcc but is exercised only by tests, the intent log is not yet populated during writes, and PRAGMA fsqlite.write_merge currently functions as an SSI-validation switch (SAFE/LAB_UNSAFE; OFF is not accepted). Wiring the ladder into the live conflict path is tracked in bd-3d5y3 / bd-p4dcv.

Native File Namespace Safety

On native Unix and Windows file VFSes, each live file-backed connection binds a single stable absolute database path to the identity obtained from its opened main-file descriptor. Persistent -fsqlite-ns-gate and -fsqlite-ns-use sidecars serialize admission to that namespace; they are never unlinked because unlinking a locked sidecar would split the advisory-lock domain on Unix. A new or caller-reserved empty database retains exclusive admission through pager, schema, rollback-journal, and WAL initialization. Only the successfully initialized Connection boundary publishes that generation for shared use.

Connections joining a live generation omit CREATE and must open the recorded file identity before inspecting recovery companions. Path replacement, identity drift while a generation is live, incomplete namespace transitions, and unexpected reserved-bootstrap companions therefore fail before recovery or mutation. The sidecar records are machine-local runtime state: when no live generation owns them and their transition ledger is terminal, an open may rebind a copied or corrupt record to the identity of the validated current main file. This recovery never creates a missing main file from a nonempty stale record. Read-only opens are regression-verified filesystem-inert on Unix; the sidecars here are created by read-write opens (see the Limitations entry on read-only opens for the current boundary). This is a cooperative trusted-parent protocol: native processes that bypass FrankenSQLite can ignore advisory locks, Unix can unlink or rename an open file, and the same database must not be opened through multiple hard-link aliases.

Transaction Lifecycle Introspection (bd-t6sv2.5)

fsqlite-core::Connection exposes transaction lifecycle observability through PRAGMA surfaces that are safe to query during active workloads:

PRAGMA fsqlite_txn_stats (aliases: txn_stats, fsqlite.txn_stats)
- Key/value counters for active/completed lifecycle state, snapshot age, read/write ops, savepoint depth, rollback counters, and advisor thresholds.
PRAGMA fsqlite_transactions (aliases: transactions, fsqlite.transactions)
- Per-active-transaction rows (duration/snapshot age and read/write activity shape).
PRAGMA fsqlite_txn_advisor (aliases: txn_advisor, fsqlite.txn_advisor)
- Actionable advisory rows for anti-patterns:
  - long_txn
  - large_read_set
  - deep_savepoint_stack
  - rollback_pressure
PRAGMA fsqlite_txn_timeline_json (aliases: txn_timeline_json, fsqlite.txn_timeline_json)
- JSON snapshot intended for timeline/visualizer tooling, including active state, first-read/first-write timing, savepoint/rollback counters, and advisor thresholds.

Advisor thresholds are tunable:

PRAGMA fsqlite.txn_advisor_long_txn_ms = <ms>
PRAGMA fsqlite.txn_advisor_large_read_ops = <count>
PRAGMA fsqlite.txn_advisor_savepoint_depth = <depth>
PRAGMA fsqlite.txn_advisor_rollback_ratio_percent = <percent>

All threshold PRAGMAs clamp invalid low values to safe minimums.

MVCC: How Concurrent Writers Work

Using FrankenSQLite from multiple processes or a many-agent swarm? Read docs/concurrency-contract.md before your caller library writes any workaround. It states, unambiguously, which concurrency shapes are intended (single-process / multi-Connection / MVCC WAL), which are not (single-Connection shared across threads), and which are partial at a measured harness scale (multi-process swarm-write). The reopened #70 requires a current target-platform swarm receipt with at least eight processes for at least one hour; bd-zywqc carries the remaining execution work. The concurrent-writer certification track also closed the double-allocation failure bd-9inpb on September 4; orphaned-page churn remains tracked by bd-ioq6x. The harness under crates/fsqlite-e2e/src/bin/swarm_multiprocess.rs is the canonical source of truth for what currently holds.

The Write Path

Transaction A: INSERT INTO users ...        Transaction B: INSERT INTO orders ...
         │                                           │
         ▼                                           ▼
  1. Acquire page lock on leaf page 47        1. Acquire page lock on leaf page 112
     (no conflict, different pages)              (no conflict, different pages)
         │                                           │
         ▼                                           ▼
  2. Copy-on-write: create new version        2. Copy-on-write: create new version
     of page 47 tagged with TxnId=42            of page 112 tagged with TxnId=43
         │                                           │
         ▼                                           ▼
  3. Commit: validate, append to WAL          3. Commit: validate, append to WAL
     (registry guard spans validation,            (registry guard spans validation,
      the physical commit, and publication)        the physical commit, and publication)
         │                                           │
         ▼                                           ▼
  4. Release page lock                        4. Release page lock

The page-version work can overlap. Commit validation and durable publication still coordinate shared state, so this diagram is not a claim that the complete commit path is lock-free or always parallel.

The Snapshot Read Path

read(page 47, snapshot.high = CommitSeq(41))
  │
  ├──▶ Buffer pool hit? → Return cached version visible to snapshot
  │
  ├──▶ WAL index lookup? → Read frame, cache it, return
  │
  └──▶ Database file → Read eligible durable base page, return

Readers do not acquire writer page locks for ordinary snapshot reads. Their concurrency remains bounded by configured transaction slots, WAL read marks in compatibility mode, memory, file descriptors, and shared-registry coordination.

Conflict Detection (SSI + First-Committer-Wins)

Transaction C and D both reach COMMIT:

  1. Page-Level First-Committer-Wins
     │
     ├── Both touch leaf page 47 (same B-tree leaf)?
     │   ├── Yes → First to lock page 47 wins. Loser hits base drift at commit
     │   │         and aborts/retries. The intent-replay/structured-patch merge
     │   │         ladder is not wired into the live commit path.
     │   │         Deadlock impossible (eager locking, no wait-for cycles).
     │
     └── No (different leaf pages) → page work can overlap, and both commit
         when the full tracked conflict sets stay clean — freed-page and
         shared-metadata conflict tokens, schema staleness, and SSI can
         still abort one of them.
  │
  2. SSI Validation (rw-antidependency check, after FCW passes)
     │
     ├── C has both an incoming AND outgoing rw-antidependency edge?
     │   └── Yes → ABORT C (write skew detected, even on disjoint pages)
     │
     └── No → commit proceeds

In the connection pipeline, first-committer-wins page validation runs first; SSI edge discovery and the dangerous-pivot check run only after FCW passes. Write skew is still caught even when the conflicting transactions touch disjoint pages, because the pipeline records read dependencies through the SireadTable across all pages. The direct TransactionManager caveat above still applies.

MVCC Visibility Rules

A page version V is visible to snapshot S if and only if both conditions hold:

V.commit_seq <= S.high (the version was committed before the snapshot was taken)
V is the newest version satisfying (1) (older qualifying versions are shadowed)

These rules produce snapshot isolation: each transaction sees a frozen view of the database as of its start time, regardless of concurrent commits happening around it. Testing whether one candidate version is old enough for a snapshot is a single CommitSeq comparison; locating the newest eligible version can still require an index lookup or version-chain traversal.

MVCC Core Data Structures

/// Monotonically increasing transaction identifier.
/// Allocated from an AtomicU64 with SeqCst ordering.
struct TxnId(u64);

/// Monotonically increasing commit sequence number (global "commit clock").
/// Assigned by the sequencer at COMMIT time.
struct CommitSeq(u64);

/// A frozen view of the database at BEGIN time.
/// Visibility is a single integer comparison: V.commit_seq <= S.high.
/// No in-flight bitmap or Bloom filter is needed.
struct Snapshot {
    high: CommitSeq,
    schema_epoch: SchemaEpoch,
}

/// A single versioned copy of a database page.
/// Versions are bump-allocated in a VersionArena (not heap-allocated).
/// The chain is linked via arena indices, not Box pointers.
struct PageVersion {
    pgno: PageNumber,
    commit_seq: CommitSeq,
    created_by: TxnToken,  // (txn_id, txn_epoch) — debug/audit only, not used for visibility
    data: PageData,
    prev_idx: Option<VersionIdx>,  // index into VersionArena
}

/// Exclusive page-level write locks. Sharded into 64 buckets
/// (power of two for fast modular arithmetic). Each shard is a
/// parking_lot::Mutex<HashMap<PageNumber, TxnId>>. Shards are
/// padded to 64-byte cache-line boundaries to prevent false sharing.
struct PageLockTable { shards: [Mutex<HashMap<PageNumber, TxnId>>; 64] }

/// SSI read tracking. Maps each page to the set of active
/// transactions that have read it. Used to detect rw-antidependencies.
struct SireadTable { shards: [Mutex<HashMap<PageNumber, SmallVec<TxnId>>>; 64] }

/// Semantic operation log for deterministic rebase merge.
/// Records what a transaction intended to do at the B-tree level.
enum IntentOp {
    Insert { table: TableId, key: RowId, record: Vec<u8> },
    Delete { table: TableId, key: RowId },
    Update { table: TableId, key: RowId, new_record: Vec<u8> },
    IndexInsert { index: IndexId, key: Vec<u8>, rowid: RowId },
    IndexDelete { index: IndexId, key: Vec<u8>, rowid: RowId },
}

Three Invariants (Must Hold at All Times)

INV-1 (Monotonic TxnIds): Transaction identities increase at admission and must not wrap or reuse an active identity. They identify transactions; they do not order commit visibility.
INV-2 (Page lock exclusivity): At most one active transaction holds the exclusive lock on any given page.
INV-3 (Version chain ordering): Newer committed versions have strictly higher commit_seq values. created_by is a transaction identity and may be out of order because transactions can finish in a different order from their starts.

Safe Write Merging and Intent Logs

Status: this section is design plus dormant implementation — see "Current Implementation Status" above. Today's live commit path aborts and retries every same-page conflict; the ladder is not yet wired in.

Standard page-level MVCC produces false conflicts when two transactions modify different rows that happen to live on the same B-tree leaf page. The dormant safe write-merge ladder (§5.10 in the spec) is designed to reduce aborts from commuting same-page conflicts without introducing row-level MVCC metadata.

The dormant design would record a semantic intent log (Vec<IntentOp>) for each writing transaction. If a transaction reached commit after its base page changed, a deterministic rebase would replay that log against the current committed state:

Detect base drift: the page's latest committed version differs from what the transaction read.
Attempt rebase: replay the intent log against the current snapshot.
Replay succeeds (B-tree invariants hold, no constraint violations) → commit with rebased deltas.
Replay fails (true conflict or constraint violation) → abort/retry.

The proposed strict safety ladder would govern merge-strategy selection at commit time:

Priority	Strategy	When Used
1	Deterministic rebase replay	Intent logs commute at B-tree level (preferred)
2	Structured page patch merge	Cell-disjoint modifications on same page
3	Abort/retry	True conflict; no safe merge possible

The accepted policy values are PRAGMA fsqlite.write_merge = SAFE | LAB_UNSAFE; OFF is rejected. The live commit path still aborts and retries same-page base drift as described above; raw byte-range XOR merge is forbidden for SQLite structured pages.

Garbage Collection

Old page versions are reclaimed when no active transaction can see them:

GC horizon = min(protected snapshot.high) in CommitSeq order. The live horizon is derived from the process-local ConcurrentRegistry; a cross-process shared-memory horizon is Native/partial design, not current behavior
Retain all committed versions above the horizon and the newest version of each page at or below it. Older versions may be logically pruned; physical reuse additionally waits for reader-guard safety
Epoch-based reclamation (EBR) batches retired version slots behind a global epoch counter and active reader pins
Commit-time version maintenance prunes unreachable versions, and retired slots are batch-freed once all pinned readers have advanced past the retire epoch
During WAL checkpointing, reclaimable frames are copied back to the main database file
When the optional ARC eviction policy is selected, its ghost entries (B1/B2) for pruned versions are cleaned as the GC horizon advances

Deadlock Freedom (By Construction)

The proof is simple:

Page locks are acquired eagerly: when a transaction first writes to a page, it tries to lock immediately.
If the lock is held by another transaction, the caller gets SQLITE_BUSY immediately. There is no waiting.
A transaction that does not wait cannot participate in a wait-for cycle.
No wait-for cycle means no deadlock. QED.

This trades potential throughput (a waiter could eventually succeed) for a smaller page-lock state machine. Conflict frequency is workload- and page-layout dependent and must be measured; it is not assumed to be rare.

The B-Tree Engine

SQLite stores all data in B-trees. Tables use B+trees (data in leaves, rowid keys). Indexes use plain B-trees (keys in all nodes, no separate data).

Page Types

Type	Flag byte	Contains	Used for
Interior table	0x05	Rowid keys + child page pointers	Navigating to the right leaf
Leaf table	0x0D	Rowid keys + record payloads	Actual row storage
Interior index	0x02	Index keys + child page pointers	Navigating the index
Leaf index	0x0A	Index keys only	Index entry storage

Cell Layout

Each cell in a leaf table page stores one row:

┌──────────────┬─────────────┬────────────────────────┐
│ Payload size │ Rowid       │ Record data            │
│ (varint)     │ (varint)    │ (header + column data) │
└──────────────┴─────────────┴────────────────────────┘

If the record exceeds the page's usable space minus overhead, the excess spills into overflow pages linked by a 4-byte page pointer at the end of the on-page portion.

Page Splitting

When an INSERT would cause a leaf page to exceed capacity:

Allocate a snapshot-safe reusable page from the freelist (or extend the database file).
Find the median cell by accumulated payload size (not count), favoring a split point that keeps the new cell on the less-full side.
Move cells above the median to the new page.
Insert a new cell in the parent interior page pointing to the new page. If the parent overflows, recurse upward.
The root page never moves. If the root splits, a new root is created with two children, increasing tree height by one.

The maximum B-tree depth is 20 (BTREE_MAX_DEPTH), which for a 4KB page size supports databases up to several terabytes.

The BtreeCursor provides ordered traversal:

move_to(key): Binary search within interior pages, descending to the leaf. O(log N) page reads.
next() / prev(): Move to the adjacent cell. If at the edge of a page, pop up to the parent and descend into the sibling.
insert(key, data): Navigate to the correct leaf, insert the cell, split if necessary.
delete(): Remove the cell, merge underfull pages if a neighbor has space.

Each cursor maintains a stack of (page_number, cell_index) pairs representing the path from root to current position, so ascending to the parent after reaching a page boundary requires no additional I/O.

Freelist Management

Deleted pages go onto a freelist rather than being returned to the OS. The freelist is structured as trunk pages, each containing up to (usable_page_size / 4) - 2 leaf page numbers. In the current non-concurrent allocation path, when no other local transaction is active, allocation draws from the committed freelist first. In default file-backed concurrent transactions, when the transaction is the sole active local transaction and its snapshot is current, allocation reuses committed free pages at or below the current database size. Freelist reuse under sustained concurrent overlap is regression-kept: page_count growth stays bounded under racing writer churn (the unbounded-EOF-growth defect tracked in #302 is fixed). VACUUM rebuilds the database and can reclaim space, but the current insertion-based builder can retain pages freed during its own construction or leave trailing pages, and page 1 of the rebuilt image may report a zero freelist_count that disagrees with the freelist actually present. The result is a valid, integrity-checkable database; the current builder does not promise a zero-freelist, header-consistent, or fixed-point compact image (#301).

PRAGMA auto_vacuum=FULL and INCREMENTAL are not supported as durable settings. The mode currently changes connection-local readback only and returns to NONE after reopen; FrankenSQLite does not yet write the pointer-map pages required to enable either mode safely (#265).

The SQL Parser

FrankenSQLite uses a hand-written parser rather than a parser generator. Direct statement and DDL routines handle the outer grammar, while explicit heap-backed state machines use Pratt binding powers for expressions and a separate frame stack for SELECT trees. C SQLite uses LEMON (a yacc variant); the hand-written design keeps precise source-span diagnostics and gives us direct control over precedence, associativity, and expression-height enforcement without relying on the native call stack for deeply nested expression or SELECT trees.

Lexer

The tokenizer uses memchr for SIMD-accelerated scanning of keyword and delimiter boundaries. Tokens are zero-copy: each token references the original input by byte range (Token { kind: TokenKind, span: Range<usize> }). The lexer handles:

150+ SQL keywords (SELECT, FROM, WHERE, JOIN, etc.)
String literals (single-quoted, with '' escape)
Blob literals (X'...')
Numeric literals (integer, float, hex with 0x prefix)
Identifier quoting (double-quotes, backticks, square brackets)
Single-line (--) and multi-line (/* */) comments
All operators, punctuation, and whitespace

Expression Parsing (Pratt Method)

Expressions are parsed using Pratt parsing (top-down operator precedence), which handles:

Binary operators with correct precedence: || (concat) < OR < AND < NOT < comparison (=, !=, <, >, <=, >=, IS, IN, LIKE, GLOB, BETWEEN) < bitwise (&, |) < shift (<<, >>) < addition (+, -) < multiplication (*, /, %) < unary (-, +, ~, NOT) < collate (COLLATE)
Prefix expressions: unary minus, NOT, EXISTS, CAST
Postfix expressions: IS NULL, IS NOT NULL, ISNULL, NOTNULL
Grouping: parenthesized expressions, subqueries, CASE/WHEN/THEN/ELSE/END
Function calls with argument lists, including DISTINCT and ORDER BY within aggregates
Window function syntax: OVER (PARTITION BY ... ORDER BY ... frame_spec)

Statement Coverage

The parser handles the complete SQLite SQL dialect:

Category	Statements
DML	SELECT (with CTEs, compound operators, joins, subqueries), INSERT (with UPSERT, RETURNING), UPDATE (with FROM, RETURNING), DELETE (with RETURNING), REPLACE
DDL	CREATE TABLE/INDEX/VIEW/TRIGGER, ALTER TABLE (ADD/RENAME/DROP COLUMN, RENAME TABLE), DROP TABLE/INDEX/VIEW/TRIGGER
Transaction	BEGIN (DEFERRED/IMMEDIATE/EXCLUSIVE), COMMIT, ROLLBACK, SAVEPOINT, RELEASE
Utility	ATTACH, DETACH, ANALYZE, VACUUM, REINDEX, EXPLAIN, EXPLAIN QUERY PLAN
Pragma	All PRAGMA statements (parsed as special syntax, not regular SQL)
Virtual	CREATE VIRTUAL TABLE

The VDBE (Virtual Database Engine)

Eligible SQL statements compile to a linear program of VDBE bytecode instructions; selected compatibility shapes — FOR SYSTEM_TIME temporal reads and the documented fallback boundaries in "Current Implementation Status" — still execute through Connection-level interpreted paths. The VDBE is a register-based virtual machine (not stack-based), matching SQLite's architecture. Each instruction has the form:

(opcode: u8, p1: i32, p2: i32, p3: i32, p4: P4, p5: u16)

p1-p3 are integer operands (register indices, jump targets, cursor numbers). p4 is a polymorphic operand (string, function pointer, collation, key info). p5 is a flags field.

Opcode Categories (190+ Total)

Category	Count	Key Opcodes
Control flow	8	Goto, Gosub, Return, InitCoroutine, Yield, Halt
Constants	10	Integer, Int64, Real, String8, Null, Blob, Variable
Register ops	4	Move, Copy, SCopy, IntCopy
Arithmetic	7	Add, Subtract, Multiply, Divide, Remainder, Concat
Comparison	7	Eq, Ne, Lt, Le, Gt, Ge, Compare
Branching	11	Jump, If, IfNot, IsNull, IsType, Once, And, Or, Not
Column access	4	Column, TypeCheck, Affinity, Offset
Cursor ops	16	OpenRead, OpenWrite, OpenEphemeral, SorterOpen, Close
Seek ops	8	SeekLT, SeekLE, SeekGE, SeekGT, SeekRowid, SeekScan
Index ops	4	NoConflict, NotFound, Found, IdxInsert
Row ops	5	NewRowid, Insert, Delete, RowData, Rowid
Transaction	6	Transaction, Savepoint, AutoCommit, Checkpoint
Sorting	5	SorterInsert, SorterSort, SorterData, SorterNext
Aggregation	4	AggStep, AggFinal, AggValue, AggInverse
Functions	3	Function, PureFunc, BuiltinFunc
And ~100 more	...	Schema, Cookie, Trace, Explain, Noop, etc.

Execution Loop

fn execute(program: &[VdbeOp], registers: &mut [SqliteValue]) -> Result<()> {
    let mut pc = 0;
    loop {
        let op = &program[pc];
        match op.opcode {
            Opcode::Goto      => { pc = op.p2 as usize; continue; }
            Opcode::Integer   => { registers[op.p2] = SqliteValue::Integer(op.p1 as i64); }
            Opcode::Column    => { /* read column from cursor op.p1, col op.p2, into reg op.p3 */ }
            Opcode::ResultRow => { /* yield registers[op.p1..op.p1+op.p2] as a result row */ }
            Opcode::Halt      => { return Ok(()); }
            // ... 185+ more arms
        }
        pc += 1;
    }
}

The inner loop is a single match statement over the opcode enum. Each arm reads inputs from registers, performs its operation, writes outputs back to registers, and either falls through to pc += 1 or jumps by setting pc directly.

Example: How `SELECT name FROM users WHERE age > 30` Compiles

addr  opcode         p1    p2    p3    p4             p5
----  ----------     ----  ----  ----  -----          --
0     Init           0     8     0                    0
1     OpenRead       0     2     0     3              0     (cursor 0 on table "users", root page 2, 3 cols)
2     Rewind         0     7     0                    0     (start at first row; jump to 7 if empty)
3     Column         0     2     1                    0     (read col 2 "age" into r1)
4     Le             1     6     2     (integer)30    0     (if r1 <= 30, skip to 6)
5     Column         0     1     3                    0     (read col 1 "name" into r3)
6     ResultRow      3     1     0                    0     (yield r3 as output row)
7     Next           0     3     0                    0     (advance cursor; loop back to 3)
8     Halt           0     0     0                    0

The Query Planner

The repository contains a substantial fsqlite-planner crate for name resolution, WHERE analysis, access-path costing, and join ordering. In the current runnable engine, however, fsqlite_core::Connection usually compiles table-backed statements directly through fsqlite_vdbe::codegen, so this section describes the planner crate and intended end-state architecture rather than the exact hot path for every query today.

Index Selection

For each term in the WHERE clause, the planner:

Checks whether any index covers the referenced columns
Estimates selectivity using sqlite_stat1 statistics (histogram of distinct values per index prefix)
Computes a cost model: cost = (pages_to_read * page_read_cost) + (rows_to_scan * row_compare_cost)
Picks the index (or full table scan) with the lowest estimated cost

Join Ordering

For queries with N tables:

N <= 8: Exhaustive enumeration of all N! orderings, pruned by cost bounds. The optimizer retains the cheapest plan found so far and skips any partial ordering whose cost already exceeds the best complete plan.
N > 8: Greedy heuristic. At each step, pick the next table that produces the smallest estimated intermediate result when joined with the tables already in the plan.

Optimizations

Optimization	What it does
Covering index scan	Reads only the index, never touches the table, when all needed columns are in the index
Index-assisted ORDER BY	Skips the sort step when the index already delivers rows in the requested order
LIKE/GLOB prefix	Converts `LIKE 'abc%'` into a range scan `>= 'abc' AND < 'abd'` on an index
Subquery flattening	Inlines simple subqueries into the outer query to avoid materialization
Skip-scan	Uses a multi-column index even when the leading column has no equality constraint, by iterating over its distinct values
Partial index awareness	Considers partial indexes (CREATE INDEX ... WHERE ...) when the query's WHERE clause implies the index predicate
OR optimization	Converts `WHERE a = 1 OR a = 2` into a union of two index lookups

The Type System

SQLite uses dynamic typing with type affinity, and FrankenSQLite models this precisely.

Storage Classes

Every value in the database belongs to one of five storage classes:

Class	Rust Representation	Sort Order
NULL	`SqliteValue::Null`	Sorts first (lowest)
INTEGER	`SqliteValue::Integer(i64)`	Numeric ordering
REAL	`SqliteValue::Float(f64)`	Numeric ordering (interleaved with INTEGER)
TEXT	`SqliteValue::Text(String)`	Collation-dependent (BINARY, NOCASE, RTRIM)
BLOB	`SqliteValue::Blob(Vec<u8>)`	Sorts last (highest), memcmp ordering

Integers and floats interleave in sort order: SqliteValue::Integer(3) sorts between SqliteValue::Float(2.5) and SqliteValue::Float(3.5).

Type Affinity

Column declarations map to one of five affinities, which influence how values are coerced on INSERT:

Affinity	Triggered by	Behavior
INTEGER	Column type contains "INT"	Try to coerce TEXT to integer; store REAL as integer if lossless
TEXT	Contains "CHAR", "CLOB", or "TEXT"	Coerce numeric values to their text representation
BLOB	Contains "BLOB" or has no type	Store as-is, no coercion
REAL	Contains "REAL", "FLOA", or "DOUB"	Coerce integer values to float
NUMERIC	Anything else (including bare column names)	Try integer first, then float, then store as text

Serial Type Encoding

Values in the record format use a compact encoding where a single varint encodes both the type and the byte length:

Serial Type	Meaning	Bytes
0	NULL	0
1	8-bit signed integer	1
2	Big-endian 16-bit signed integer	2
3	Big-endian 24-bit signed integer	3
4	Big-endian 32-bit signed integer	4
5	Big-endian 48-bit signed integer	6
6	Big-endian 64-bit signed integer	8
7	IEEE 754 64-bit float	8
8	Integer constant 0	0
9	Integer constant 1	0
N >= 12, even	BLOB of (N-12)/2 bytes	(N-12)/2
N >= 13, odd	TEXT of (N-13)/2 bytes	(N-13)/2

Types 8 and 9 are an optimization: booleans and small constants consume zero bytes in the data section.

Transaction Semantics

Transaction Modes

Mode	Behavior
Plain `BEGIN` (default)	Promotes to `BEGIN CONCURRENT`; writers may overlap on disjoint pages
`BEGIN CONCURRENT`	Explicit concurrent mode, with snapshot and commit-time conflict validation
Explicit `BEGIN DEFERRED`	Opts into deferred serialized-writer admission; may fail when upgrading to a writer
Explicit `BEGIN IMMEDIATE`	Requests serialized-writer admission at BEGIN; conflicting admission can return `SQLITE_BUSY`
Explicit `BEGIN EXCLUSIVE`	Requests exclusive transaction mode; reader exclusion depends on the journal/VFS path

PRAGMA fsqlite.concurrent_mode = OFF explicitly changes the policy for plain BEGIN. It is ON by default. Explicit modes have different admission and snapshot behavior; EXCLUSIVE is not a universal guarantee of reader exclusion in WAL mode.

Savepoints

Savepoints provide nested rollback points within a transaction:

BEGIN;
INSERT INTO t VALUES (1);
SAVEPOINT sp1;
INSERT INTO t VALUES (2);
ROLLBACK TO sp1;        -- undoes the second INSERT, keeps the first
INSERT INTO t VALUES (3);
RELEASE sp1;            -- collapses sp1 into the parent transaction
COMMIT;                 -- t contains (1, 3)

Savepoints are implemented as a stack. ROLLBACK TO undoes changes back to the savepoint by restoring journal pages. RELEASE removes the savepoint without undoing anything. The outermost "savepoint" is the transaction itself.

Crash Recovery

The crash model makes six explicit assumptions: (1) process crash at any point, (2) fsync() is a durability barrier, (3) writes may be reordered unless constrained by fsync barriers, (4) torn writes at sector granularity (512B or 4KB), (5) bitrot and corruption exist (checksums detect them; RaptorQ repair is a Native-mode design, not current compatibility-runtime behavior), (6) file metadata durability may require directory fsync().

The WAL provides crash recovery with the following guarantees:

Atomic commit: A transaction is either fully visible or fully invisible after crash recovery. Partial commits cannot occur. In Native mode, a commit is committed if and only if its CommitMarker is durable.
Durability: Once COMMIT returns, the data survives power loss (assuming PRAGMA synchronous = FULL). A configurable durability policy (PRAGMA durability = local, PRAGMA durability = quorum(M)) is a Native-mode design target, not current behavior: no such PRAGMA is dispatched, and unrecognised PRAGMAs are silently ignored, so setting it has no effect.
Repair symbol generation (live native path; automatic recovery pending): Native file-backed connections with a caller-owned runtime and blocking pool enqueue durable WAL ranges for background RaptorQ encoding. A group becomes protected only after its .wal-fec record and repair symbols are written and synced, after the primary WAL durability acknowledgment. Startup can regenerate missing or torn sidecar entries from surviving, validated WAL frames. Ordinary WAL recovery still stops at checksum failures and does not invoke the FEC decoder; bd-1hi.11 tracks that missing integration.
Recovery procedure:
- On database open, check for a WAL file.
- Read the WAL header; validate magic number and checksums.
- Replay all committed frames (those with a nonzero "database size" field in the frame header, indicating a commit boundary).
- Validate frame checksums. RaptorQ repair from available repair symbols is the Native-mode design; it is not attempted by the current compatibility recovery path.
- Discard any frames after the last commit boundary (incomplete transaction).
- Rebuild the WAL index from the replayed frames.

The CLI supplies the required blocking pool. Library consumers must supply one through their asupersync runtime; in-memory databases and runtimes without a blocking pool do not generate these sidecars. PRAGMA raptorq_repair_symbols controls the repair budget, with 0 disabling generation. Work is admitted at WAL fsync boundaries: synchronous=FULL provides one for each commit, while NORMAL can defer it. Await connection close to drain pending work; dropping the connection only cancels it. Generation and shutdown regression coverage is in crates/fsqlite-core/tests/wal_fec_commit_pipeline.rs and the CLI's test_shell_runtime_generates_wal_fec_before_exit. This is not a claim of automatic corruption repair or a measured end-to-end performance guarantee.

The WAL (Write-Ahead Log)

How WAL Mode Works

In WAL mode, writes append to a separate log file instead of modifying the database directly. In the live compatibility runtime, readers normally use an adapter-local published page map, built from committed WAL frames, to find the newest visible frame for each page. If a configured entry cap leaves that map partial, the adapter falls back to a backward per-frame scan. Pages absent from the visible WAL generation come from the database file.

File-backed Unix writers also publish the standard shared -shm frame/hash entries and dual WAL-index headers, and maintain shared checkpoint and reset state. Before serving pages, Unix readers validate the shared generation and retain a matching read-mark claim (aReadMark/WAL_READ_LOCK). Stock SQLite processes can therefore observe native publication, while checkpoints respect pinned reader horizons. FrankenSQLite's own page lookup still uses its adapter-local map. The public process regressions live in wal_reset_with_foreign_reader.rs; full cross-process MVCC conflict coordination remains the separate partial design below.

The September 10, 2026 public-process runs cover Linux x86_64. Native macOS validation remains open in #19.

Frame Format

WAL Header (32 bytes, file offset 0):
  Bytes 0-3:    Magic number (0x377F0682 or 0x377F0683, indicating byte order)
  Bytes 4-7:    Format version (3007000)
  Bytes 8-11:   Database page size
  Bytes 12-15:  Checkpoint sequence number
  Bytes 16-19:  Salt-1 (random, changes on each checkpoint)
  Bytes 20-23:  Salt-2
  Bytes 24-31:  Cumulative checksum of the header

Frame Header (24 bytes, before each page):
  Bytes 0-3:    Page number
  Bytes 4-7:    For commit frames: database size in pages. Otherwise: 0.
  Bytes 8-11:   Salt-1 (must match WAL header)
  Bytes 12-15:  Salt-2 (must match WAL header)
  Bytes 16-23:  Cumulative checksum over (frame header + page data)

Frame Body:
  <page_size> bytes of page content

Checksums are cumulative: each frame's checksum incorporates the previous frame's checksum, creating a hash chain. A single bit flip anywhere in the WAL is detected at the next frame read.

Checkpoint Modes

Mode	Behavior
PASSIVE	Copy committed pages back to the database file. Does not block readers or writers. Skips pages still needed by active readers.
FULL	Waits for all readers using old snapshots to finish, then copies all committed pages. Blocks new writers during the copy.
RESTART	Like FULL, but also resets the WAL file to the beginning afterward, reclaiming disk space.
TRUNCATE	Like RESTART, but truncates the WAL file to zero bytes.

MVCC Extensions to the WAL

In FrankenSQLite's Native-mode design, WAL frames carry transaction IDs and the index maps (page_number, txn_id) pairs to frame offsets; that transaction-tagged format is partial infrastructure, not the live compatibility WAL. The shipped compatibility WAL uses the standard 24-byte frame header above — page number, commit database-size, salts, cumulative checksum — with no transaction ID. Checkpoint must respect active snapshots: a frame can only be checkpointed if its page version is no longer needed by any active reader (enforced cross-process on Unix via the GH#399 reader-horizon gates).

Rollback Journal

FrankenSQLite supports rollback journal mode for reading databases not in WAL mode. The rollback journal (<database>-journal) is the legacy crash-recovery mechanism that predates WAL.

Journal format:

Journal Header (padded to sector boundary):
  Offset  Size  Description
    0       8   Magic: {0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd7}
    8       4   Page count (-1 means compute from file size)
   12       4   Random nonce for checksum
   16       4   Initial database size in pages (before this transaction)
   20       4   Sector size (header padded to this boundary)
   24       4   Page size

Journal Page Records (repeated page_count times):
  [4 bytes: page number (u32 BE)]
  [page_size bytes: original page content before modification]
  [4 bytes: checksum]

How it works: Before modifying a page, the pager writes the original page content to the journal. On crash, the journal is played back to restore the database to its pre-transaction state. The checksum uses a sparse sampling algorithm: nonce + data[page_size-200] + data[page_size-400] + ..., summing bytes at 200-byte intervals from the end of the page (20 bytes sampled for 4096-byte pages).

Hot journal recovery: On open, if a journal file exists, is non-empty, and the database's reserved lock is not held, it is a "hot journal." Recovery plays back original pages from the journal, then deletes it.

Journal modes: SQLite defines DELETE (delete journal after commit), TRUNCATE (truncate to zero), PERSIST (zero the header), MEMORY (journal in RAM only — no crash safety), WAL (switch to write-ahead logging), and OFF (no journal — no crash safety). FrankenSQLite defaults to WAL mode, and its live file-backed pager has two storage modes: WAL and crash-safe rollback-journal Delete. Every non-WAL journal_mode request routes to the rollback path; MEMORY and OFF are accepted for compatibility but currently fall through to crash-safe DELETE cleanup rather than disabling on-disk recovery.

Buffer Pool: S3-FIFO Default (ARC Optional)

LRU can perform poorly on database workloads because a table scan may evict a hot working set. The production pager configures S3-FIFO eviction by default. An ARC policy is also implemented and can be selected through PageCacheEvictionPolicy::Arc; it adapts between recency and frequency and retains ghost entries to detect changes in the workload. The README does not claim a universal competitive ratio for either implementation.

PRAGMA cache_size sets the current connection's resident-page suggestion: positive values count pages, negative values specify KiB converted using the pager's actual page size at assignment, and zero retains no eligible clean pages after an operation finishes. Shrinking reclaims clean pages; dirty pages and pending reads can defer convergence. This does not reduce the transaction buffer pool's allocation ceiling or bound retained page handles, TEMP data, query results, or process memory. Connection::memory_stats() reports the suggestion as page_cache.cache_page_budget, separately from pool capacity.

Connections to the same file keep independent suggestions. Attached schemas use their own child connection; TEMP keeps separate settings without resizing the main pager. cache_size lasts for the connection. For a file-backed schema, default_cache_size stores a default in its header for subsequent opens; TEMP's default is transaction-aware but remains local to the connection. A failed or rolled-back default write can still change the current runtime suggestion, matching SQLite. Public SQL regression coverage is in crates/fsqlite-e2e/tests/bd_aztlm_page_cache_e2e.rs (Q9–Q16); acceptance and outstanding verification are tracked by bd-dwjnq.1/.2.

MVCC-Aware Structure (Optional ARC Policy)

The optional ARC policy (fsqlite-pager::arc_cache::ArcCache) keys on (PageNumber, CommitSeq) because multiple committed versions of the same page coexist for MVCC. The following sketch is illustrative; the shipped default path uses ShardedPageCache with S3-FIFO eviction:

struct ArcPolicySketch {
    /// Pages accessed exactly once recently (recency-favored).
    t1: LinkedHashMap<CacheKey, CachedPage>,
    /// Pages accessed two or more times (frequency-favored).
    t2: LinkedHashMap<CacheKey, CachedPage>,
    /// Ghost entries evicted from T1 (metadata only, no page data).
    b1: LinkedHashSet<CacheKey>,
    /// Ghost entries evicted from T2 (metadata only).
    b2: LinkedHashSet<CacheKey>,
    /// Adaptive parameter: target size for T1 (range [0, capacity]).
    p: usize,
    /// Max pages in T1 + T2. Derived from `PRAGMA cache_size`: a positive
    /// value is a page count; a negative value is a KiB budget (the
    /// conventional -2000 gives ~2 MB, i.e. 500 pages at 4 KiB).
    capacity: usize,
}

struct CacheKey { pgno: PageNumber, commit_seq: CommitSeq }

How ARC Works

On page request (O(1) amortized):

Case	Condition	Action
Hit in T1	Page found in recency list	Promote to T2 (now frequency-tracked)
Hit in T2	Page found in frequency list	Move to T2 head (refresh)
Ghost hit in B1	Recently evicted recency page requested again	Increase `p` (favor recency), fetch from disk, insert to T2
Ghost hit in B2	Recently evicted frequency page requested again	Decrease `p` (favor frequency), fetch from disk, insert to T2
Complete miss	Not in any list	Evict if needed, fetch from disk, insert to T1

Ghost entries (B1/B2) store only the cache key, not page data. They let ARC learn access patterns without consuming page-sized memory.

Eviction Constraints (Optional ARC Policy)

These constraints describe the ARC policy. The current default (ShardedPageCache with S3-FIFO) converts PRAGMA cache_size to a fixed-page residency suggestion as described above; it has no separate byte-based allocation trigger:

Never evict a pinned page (ref_count > 0).
Never evict a dirty page (must flush to WAL first).
Prefer superseded versions (a newer committed version exists that is visible to all active snapshots).
Dual eviction trigger: fires when page count exceeds capacity OR total_bytes exceeds max_bytes (from PRAGMA cache_size).

Visibility Check

With CommitSeq-based snapshots, the eligibility test for one version is the integer comparison V.commit_seq <= S.high; no in-flight bitmap or Bloom filter is needed for that test. Finding the newest eligible version is a separate lookup/traversal cost.

Async Integration (asupersync + Cx)

FrankenSQLite uses asupersync for async I/O rather than tokio. asupersync provides capabilities that database engines require but general-purpose runtimes do not.

Cx (Capability Context) Everywhere

Every trait method that touches I/O, acquires locks, or could block accepts &Cx. This is a non-negotiable rule throughout the codebase. Pure computation (e.g., collation comparisons, CPU-only scalar functions) is the only exception.

Cx threads three capabilities through the entire call chain:

Cancellation: Pollable connection operations carry the caller's context, and long queries check its cancellation token at VDBE instruction boundaries (every N opcodes) and return SQLITE_INTERRUPT when they observe cancellation. The worker-backed AsyncConnection wrapper is narrower: cancellation after dispatch stops the caller's wait but does not interrupt the in-flight worker operation. Dropping the wrapper signals shutdown and detaches rather than joining, so Drop does not block; the worker finishes its terminal cleanup after the operation completes. Applications that require a hard kill deadline must use process isolation (#306).
Deadline propagation: Timeout budgets flow through the entire call chain. A 5-second query deadline decrements as it passes through the parser, planner, and executor.
Capability narrowing: Callers can restrict what callees are allowed to do. A read-only connection's Cx prevents write operations at the capability level.

asupersync Components

Lab reactor: Fully deterministic concurrency testing with reproducible scheduling and precise fault injection. Every MVCC interleaving can be replayed exactly.
E-processes: Anytime-valid statistical invariant monitoring. Detects anomalies (e.g., snapshot isolation violations) with bounded false-positive rates.
Mazurkiewicz traces: Enumerate all non-equivalent interleavings for exhaustive concurrency verification without combinatorial explosion.
DPOR (Dynamic Partial Order Reduction): Prunes equivalent schedules during testing. Only explores interleavings that lead to genuinely different outcomes.

Write Coordination Flow

async caller
  → Connection::execute(sql).await
    → parse and dispatch using the connection's operation Cx
    → compile eligible SQL to VDBE; dispatch supported fallback shapes
    → execute against the pager/B-tree with that Cx
    → on commit: validate → pager commit → publish
  ← Result<usize> (affected row count)

The caller supplies the executor polling this future. The default connection uses the process-global RuntimeContext; ConnectionEnv::new_with_root_cx and Connection::open_with_env opt into caller-rooted context lineage.

The live compatibility commit runs in the owning Connection; it does not submit SQL commits to an MPSC coordinator. execute_commit_with_cx takes a TimedRegistryCommitGuard through lock_registry_for_commit and holds it across FCW/SSI validation (plan_concurrent_commit_with_registry), the physical pager write (txn.commit), and CommitIndex publication (finalize_concurrent_commit_with_registry). The guard closes the issue #115 race in which a peer could claim an EOF page after its physical write but before its allocation became visible in the commit index. Statement execution and private page mutation can overlap before this coordinated commit section. The safe merge ladder is dormant.

The region-owned ensure_write_coordinator_service_started task currently waits for a shutdown signal; its existence is lifecycle infrastructure, not a live commit queue. Cancel-correct MPSC submission, batching, and the native two-fsync sequencer remain planned integration work (bd-3mgq5.7/.8).

Structured Concurrency, Cancellation, and Supervision

FrankenSQLite uses a region tree as the lifetime model for all concurrency: fsqlite-core maintains its own RegionTree bookkeeping over asupersync root-region tasks (spawned via RuntimeHandle::try_spawn with registered handles, startup checkpoints, and shutdown signals), rather than asupersync's child-region Scope API directly. Every background worker, coordinator, replicator, and long-lived service runs as a region-owned task or actor under that tree. No task may outlive the Database root region. There are no detached tasks.

Region tree (conceptual):

DbRootRegion
  ├── WriteCoordinatorRegion         (marker sequencer + compat WAL path)
  ├── SymbolStoreRegion              (local symbol logs + tiered storage fetch)
  ├── ReplicationRegion              (stream symbols; anti-entropy; membership)
  ├── CheckpointGcRegion             (checkpointer, compactor, GC horizon)
  └── ObservabilityRegion            (deadline monitor, task inspector, metrics)

PerConnectionRegion (child of DbRootRegion)
  ├── QueryExecution tasks
  └── Cursor prefetch tasks (bounded; optional)

PerTransactionRegion (child of PerConnectionRegion)
  ├── Encode/persist capsule tasks (native mode)
  ├── Witness publication tasks
  └── Validation tasks

Closing the database is a protocol, not a drop: request cancellation, drain, finalize, then return. A region does not report closed until all child tasks are completed, all finalizers have run, and all obligations are resolved.

Cancellation Is a Protocol (Request, Drain, Finalize)

Cancellation is not "drop the future." It is a multi-phase protocol with explicit checkpoints, bounded drain, and finalizers:

Created/Running → CancelRequested → Cancelling → Finalizing → Completed(Cancelled)

FrankenSQLite places cx.checkpoint() at every natural yield point that bounds uninterruptible work: VDBE instruction boundaries, B-tree descent loops, RaptorQ encode/decode loops, and any loop over user data. A cancellation-unaware hot loop is a bug.

Masked critical sections (Cx::masked) allow bounded cancellation deferral for short, atomic publication steps that must not be interrupted (e.g., publishing a commit marker after allocating commit_seq). Mask depth is bounded at MAX_MASK_DEPTH = 64. Masking is forbidden for long operations.

Obligations (Linear Resources)

Asupersync models cancellation-safe effects using obligations — linear resources with a two-phase lifecycle: Reserved → Committed or Reserved → Aborted. A reserved obligation that is dropped without resolution is a Leaked obligation — a correctness bug that fails fast in lab mode and triggers diagnostic escalation in production.

FrankenSQLite treats the following as obligations: commit pipeline SendPermit reservations, commit response delivery, TxnSlot acquisition and renewal, witness-plane reservation tokens, and any name/registration in shared state that could go stale on crash.

OTP-Style Supervision

Long-lived services (sequencers, replicators, checkpoint workers) are supervised. "Spawn a loop and hope" is forbidden. Supervision provides restart strategies (Stop, Restart(config), Escalate), restart budgets with backoff, and monotone severity (outcomes cannot be downgraded):

WriteCoordinator: Escalate on error or panic (sequencer correctness is core).
SymbolStore: Restart on transient I/O; Escalate on integrity faults.
Replicator: Restart with exponential backoff; Stop when remote disabled.
CheckpointerGc: Restart (bounded) on transient errors; escalate if repeated.

A component crash becomes an explainable, bounded event with a deterministic restart policy — not a silent hang or memory leak.

Extensions

FTS5 (Full-Text Search)

FTS5 provides full-text indexing with BM25 ranking:

Tokenizers: unicode61 (default, Unicode-aware word breaking), ascii, porter (English stemming), trigram (character n-grams for substring search)
Query syntax: Boolean operators (AND, OR, NOT), phrase matching ("exact phrase"), prefix queries (prefix*), column filters (title: search_term), NEAR queries (NEAR(a b, 10)). Column-qualified MATCH honors the column restriction (the earlier defect in #249 is fixed and regression-kept).
Ranking: BM25 by default, configurable via auxiliary functions
Auxiliary functions: highlight() wraps matches in markup, snippet() extracts context around matches
Content modes: Regular (FTS5 stores a copy), external content (references an existing table), contentless (index-only, no original text stored). The contentless delete-all control command is supported (#253 fixed); stored-content tables reject it, matching stock SQLite.
Index structure: A B-tree of terms mapping to document/position lists, with incremental merge for write performance

Upgrading from 0.1.x with a porter-tokenized table requires an FTS rebuild; see the v0.2.0 entry in CHANGELOG.md for the mode-specific procedure.

R-Tree (Spatial Indexing)

The R-tree virtual table indexes N-dimensional bounding boxes for spatial queries:

Range queries: Find all rectangles that overlap or are contained within a search rectangle
Custom geometry callbacks: Register Rust functions that define arbitrary geometric predicates
Dimensions: 1 to 5 dimensions per R-tree (configurable at table creation)
Geopoly extension: The Geopoly scalar functions (geopoly_blob, geopoly_json, geopoly_svg, geopoly_area, geopoly_overlap, geopoly_within) are registered; a CREATE VIRTUAL TABLE ... USING geopoly virtual-table module is not implemented, so polygon storage/query through a geopoly table is not available

The earlier R-Tree write-path limitations — UPDATE not persisting changed bounds (#208) and INSERT OR REPLACE unimplemented (#214) — are fixed and regression-kept.

JSON1

Full JSON manipulation within SQL:

Function	Purpose
`json_extract(doc, path)` / `->` / `->>`	Extract a value at a JSON path
`json_set(doc, path, value)`	Set a value at a path (create if missing)
`json_remove(doc, path)`	Remove a key/element at a path
`json_each(doc)` / `json_tree(doc)`	Table-valued functions for iterating JSON structure
`json_group_array(value)`	Aggregate values into a JSON array
`json_group_object(key, value)`	Aggregate key-value pairs into a JSON object
`json_patch(target, patch)`	RFC 7396 merge patch
`json_valid(doc)`	Check if a string is valid JSON

Also supports JSONB (binary JSON), a representation intended to avoid repeated text parsing; its performance relative to JSON text is not claimed here.

Session Extension

Records changes to a database as changesets that can be applied elsewhere:

Change tracking: Records INSERT, UPDATE, and DELETE operations
Changeset generation: Produces a compact binary encoding of all changes since tracking began
Patchset variant: More compact than changesets (omits original values for UPDATE); sufficient for applying changes but not for conflict detection
Conflict resolution: Callbacks invoked when applying a changeset conflicts with the target database
Changeset inversion: Generates the inverse changeset (for undo operations)
Rebasing: Combines changesets from parallel editing sessions

Status: the session crate implements the changeset/patchset codec and a Session recorder, but it is currently a manual library facade, exposed as fsqlite::session behind the top-level session Cargo feature. Callers must invoke record_insert/record_update/record_delete themselves; there is no automatic pre-update-hook capture from live SQL execution, and the crate is not part of fsqlite-core's extensions feature bundle.

Built-In Functions

Scalar Functions (Selected)

Function	Description
`abs(x)`	Absolute value
`length(x)`	String length in characters, or blob length in bytes
`substr(s, start, len)`	Substring extraction
`replace(s, from, to)`	String replacement
`upper(s)` / `lower(s)`	Case conversion
`trim(s)` / `ltrim(s)` / `rtrim(s)`	Whitespace removal
`instr(s, substr)`	Position of first occurrence
`hex(x)` / `unhex(s)`	Hex encoding/decoding
`typeof(x)`	Returns "null", "integer", "real", "text", or "blob"
`coalesce(x, y, ...)`	First non-NULL argument
`iif(cond, then, else)`	Inline conditional
`printf(fmt, ...)`	C-style string formatting
`random()`	Random 64-bit integer
`quote(x)`	SQL-safe quoting of a value

Aggregate Functions

Function	Description
`count(*)` / `count(x)`	Row count / non-NULL count
`sum(x)` / `total(x)`	Sum (integer overflow to float for `total`)
`avg(x)`	Average
`min(x)` / `max(x)`	Extrema
`group_concat(x, sep)`	Concatenation with separator

Window Functions

Function	Description
`row_number()`	Sequential integer for each row in the partition
`rank()`	Rank with gaps for ties
`dense_rank()`	Rank without gaps
`ntile(n)`	Divide partition into n buckets
`lag(x, n)` / `lead(x, n)`	Value from n rows before/after current
`first_value(x)` / `last_value(x)`	First/last value in the frame
`nth_value(x, n)`	Nth value in the frame

All aggregate functions also work as window functions when used with an OVER clause.

Date/Time Functions

Function	Description
`date(time, modifier...)`	Extract date string (YYYY-MM-DD)
`time(time, modifier...)`	Extract time string (HH:MM:SS)
`datetime(time, modifier...)`	Extract datetime string
`julianday(time, modifier...)`	Julian day number (float)
`unixepoch(time, modifier...)`	Unix timestamp (integer seconds)
`strftime(format, time, modifier...)`	Custom formatting
`timediff(a, b)`	Difference between two timestamps

Math Functions

acos, asin, atan, atan2, ceil, cos, degrees, exp, floor, ln, log, log2, mod, pi, pow, radians, sin, sqrt, tan, trunc.

The CLI Shell

The fsqlite-cli binary currently provides a small interactive SQL shell plus one-shot command execution. It is useful today, but it is not yet a full sqlite3-equivalent front-end.

Features

Multi-line statement detection with TTY-aware continuation prompts
Syntax-highlighted SQL previews in interactive continuation prompts
Output modes: list, column, csv, tabs, line, with optional headers
REPL and command-mode dot commands: .help, .quit, .exit, .read FILE, .open FILE, .tables, .schema, .dump, .mode, .headers / .header
Single-command mode: -c / --command
Batch mode for piped stdin plus explicit -batch / --batch
Startup script support via -init / --init
Decode-proof verification mode: --verify-proof
Ctrl-C clears the current pending statement; EOF exits the shell

Persistent history, full tab completion, and broader sqlite3 dot-command parity are still future work.

Public API

Basic Usage

use fsqlite::{Connection, FrankenError, SqliteValue};

async fn basic_usage() -> Result<(), FrankenError> {
    let conn = Connection::open("my.db").await?;
    conn.execute(
        "CREATE TABLE users (id INTEGER PRIMARY KEY, name TEXT, age INTEGER)",
    ).await?;
    conn.execute_with_params(
        "INSERT INTO users (name, age) VALUES (?1, ?2)",
        &[SqliteValue::from("Alice"), SqliteValue::from(30)],
    ).await?;

    let stmt = conn.prepare("SELECT name, age FROM users WHERE age > ?1").await?;
    let rows = stmt.query_with_params(&[SqliteValue::from(25)]).await?;
    for row in rows {
        if let (Some(SqliteValue::Text(name)), Some(SqliteValue::Integer(age))) =
            (row.get(0), row.get(1))
        {
            println!("{}: {age}", name.as_str());
        }
    }
    Ok(())
}

Connection methods are asynchronous; the caller supplies the executor that polls their futures. Connection::open uses a lazily initialized process-global RuntimeContext by default. To root the connection's Cx lineage in a caller-supplied Cx, open with a ConnectionEnv::new_with_root_cx environment.

Transaction API

use fsqlite::compat::TransactionExt;

let mut tx = conn.transaction().await?;
tx.execute("INSERT INTO accounts (id, balance) VALUES (1, 1000)").await?;
tx.execute("INSERT INTO accounts (id, balance) VALUES (2, 500)").await?;

tx.commit().await?; // atomic: both inserts visible, or neither

Finalize a transaction by awaiting commit() or rollback(). Dropping it records a mandatory rollback obligation, which the next SQL entry point completes before executing the caller's statement.

Concurrent Writers

use fsqlite::{Connection, FrankenError, SqliteValue};

async fn write_batch(db_path: &str, writer_id: i64) -> Result<(), FrankenError> {
    // Each concurrent task owns a separate connection.
    let conn = Connection::open(db_path).await?;
    for sequence in 0_i64..1_000 {
        let mut retries = 0_u8;
        loop {
            match conn.execute_with_params(
                "INSERT INTO events (writer, sequence) VALUES (?1, ?2)",
                &[SqliteValue::from(writer_id), SqliteValue::from(sequence)],
            ).await {
                Ok(_) => break,
                Err(error) if error.is_transient() && retries < 8 => {
                    retries += 1;
                }
                Err(error) => return Err(error),
            }
        }
    }
    Ok(())
}

Run one write_batch future per OS thread, with that thread's caller-owned executor and its own Connection. Connection is !Send + !Sync, so do not move a connection-owning future onto a Send-only task lane. To drive several connections on one thread, use asupersync's pinned local lane (Cx::spawn_local_in or JoinSet::spawn_local). Production callers should add bounded backoff appropriate to their runtime between transient retries.

Testing Strategy

Five Layers

Unit tests in each crate test components in isolation using mock implementations of trait dependencies.
Integration tests in fsqlite-core test the full query pipeline from SQL text to result rows using an in-memory VFS.
Compatibility tests in fsqlite-harness run the SQLite test corpus against both FrankenSQLite and C SQLite, comparing results row-by-row.
Fuzz tests using cargo-fuzz target the parser, record decoder, and B-tree page decoder with arbitrary byte inputs.
Concurrency tests exercise MVCC behavior: concurrent readers and writers, snapshot isolation verification, write-write conflict detection, and garbage collection under load.

Property-Based Testing (proptest)

B-tree invariants hold for arbitrary insert/delete sequences
Record serialization round-trips: deserialize(serialize(record)) == record for any Vec<SqliteValue>
Parser round-trips: parse(print(ast)) == ast for any generated AST
MVCC snapshots are consistent under arbitrary transaction interleavings

Crash Recovery Testing

Power-loss simulation: the committed fault matrix samples selected WAL cut points during commit — whole/half/third-frame cuts, single-byte checksum flips, tail zeroing — then recovers and verifies no committed data loss (not every byte boundary)
SIGKILL testing: kill the process mid-commit at chosen states, restart, and verify every commit-logged row is visible after recovery (committed-row visibility, not PRAGMA integrity_check)
Bit-flip testing: flip random bits in the WAL and database files, verify checksum detection

Conformance Target

100% behavioral parity target with C SQLite 3.52.0 for the supported surface. Any intentional divergence MUST be explicitly documented and annotated in the harness with rationale. The conformance suite runs SQL Logic Tests (SLT format) covering:

The runtime file-format surface covers encoding=1/UTF-8 plus encodings 2/3 (UTF-16le/UTF-16be) for reads and writes; the SLT parity claim is deepest on the UTF-8 surface, with UTF-16 coverage newer. Admission reads the pager-visible page 1 (WAL-authoritative when a live WAL is installed). After normal pager open/recovery and journal/WAL authority setup, admission performs no main-image rewrite or checkpoint; an ordinary open may inspect or create sibling WAL state first. PRAGMA encoding = 'UTF-16le'|'UTF-16be'|'UTF-16' matches stock sqlite3: it sets the encoding on an empty database (persisting into header bytes 56..60) and is a silent no-op on a non-empty one.

The canonical target/version contract is pinned in docs/contracts/sqlite_version_contract.toml and referenced by parity harness reports. The human-readable scope lock for that contract lives in docs/canonical_parity_contract.md.

All DML and DDL operations
All join types (INNER, LEFT, RIGHT, FULL, CROSS, NATURAL)
Subqueries, CTEs, window functions, triggers, views
Type affinity, NULL handling, collation sequences
Every built-in function
Foreign keys, UPSERT, RETURNING clause
WAL mode, concurrent readers under write load

Performance Characteristics

No numeric performance result is claimed for current main.

The async storage migration changed engine, dependency, and benchmark-driver behavior after the last published matrices. Same-host diagnostics found a release-blocking timing discontinuity, but the historical cohorts are not a controlled async-only comparison. Several older artifacts also have missing or null Git provenance, asymmetric settings, or harness defects. They remain diagnostic history in docs/progress/perf-negative-results.md, not release evidence.

The retained performance diagnostics used the Unix fallback. A later correctness receipt reporting the public iouring backend does not establish kernel I/O behavior or throughput. The intended data path and shipped size-optimized profile still require a citation-grade performance matrix; neither can be inferred from release-perf results.

bd-dqdoe tracks the same-source performance re-verification. A release may restore numeric claims here only after the repository contains an immutable artifact that records the exact source commit, binary hashes, build profile and flags, host state, commands, matched durability settings, A/A null envelope, and paired confidence intervals. The required matrix must cover the shipped profile as well as release-perf, and it must be rerun after the durability, async-actor, namespace-lifecycle, and registry changes settle.

File Format (SQLite-Compatible Layout)

Database Header (100 bytes at offset 0)

Offset  Size  Field
──────  ────  ─────────────────────────────────────────
  0      16   Magic: "SQLite format 3\0"
 16       2   Page size (512-65536)
 18       1   Write format version (1=journal, 2=WAL)
 19       1   Read format version
 20       1   Reserved bytes per page
 21       1   Max embedded payload fraction (must be 64)
 22       1   Min embedded payload fraction (must be 32)
 23       1   Leaf payload fraction (must be 32)
 24       4   File change counter
 28       4   Database size in pages
 32       4   First freelist trunk page
 36       4   Total freelist pages
 40       4   Schema cookie
 44       4   Schema format number (4 = current)
 48       4   Default page cache size
 52       4   Largest root B-tree page (auto-vacuum)
 56       4   Text encoding (1=UTF8, 2=UTF16le, 3=UTF16be)
 60       4   User version (PRAGMA user_version)
 64       4   Incremental vacuum mode
 68       4   Application ID (PRAGMA application_id)
 72      20   Reserved for expansion (must be zero)
 92       4   Version-valid-for number
 96       4   SQLite version that wrote the file

The table records SQLite's valid on-disk values. The runtime supports text encoding 1 (UTF-8) and, more recently, encodings 2 and 3 (UTF-16le/UTF-16be) for both reads and writes; TEXT is serialized in the database's declared encoding end to end.

B-tree Page Layout

┌───────────────────────────────────┐
│ Page header (8 or 12 bytes)       │
├───────────────────────────────────┤
│ Cell pointer array (2B per cell)  │
├───────────────────────────────────┤
│ Unallocated space                 │
├───────────────────────────────────┤
│ Cell content (grows from bottom)  │
├───────────────────────────────────┤
│ Reserved region                   │
└───────────────────────────────────┘

Record Format

┌─────────┬─────────────┬─────────────┬───┬──────────┬──────────┬───┐
│ Hdr size│ Serial type 1│ Serial type 2│...│ Value 1  │ Value 2  │...│
│ (varint)│ (varint)     │ (varint)     │   │ (N bytes)│ (N bytes)│   │
└─────────┴─────────────┴─────────────┴───┴──────────┴──────────┴───┘

Pointer Map and Auto-Vacuum

SQLite's auto-vacuum modes use a pointer map — a reverse lookup from a page to its parent — so relocated pages can have their parent pointers updated. When auto-vacuum is enabled, the first pointer-map page is page 2. In FULL mode, freeing a page can relocate the final page and truncate the file; INCREMENTAL mode retains reclaimable pages until PRAGMA incremental_vacuum is run.

Entry format (5 bytes per page):

Byte	Content
0	Type code: 1 = root page, 2 = freelist page, 3 = first overflow page, 4 = subsequent overflow page, 5 = non-root B-tree page
1-4	Parent page number (u32 big-endian). Meaning varies by type: for B-tree pages, it's the parent in the tree; for overflow pages, it's the page containing the cell that overflows.

Each pointer-map page holds usable_size / 5 entries (819 entries for 4096-byte pages). Pointer-map pages recur at regular intervals: pages 2, 822, 1642, ... (group size = entries_per_page + 1 = 820).

The format above describes SQLite's on-disk contract, not a current FrankenSQLite feature. FrankenSQLite does not yet create or maintain pointer-map pages or relocate pages for auto-vacuum. Setting auto_vacuum = FULL or auto_vacuum = INCREMENTAL is currently connection-local and is not persisted in the database header (#265).

Schema Management (sqlite_master)

Every SQLite database contains a sqlite_master table rooted at page 1 with this schema:

CREATE TABLE sqlite_master (
    type TEXT,      -- 'table', 'index', 'view', 'trigger'
    name TEXT,      -- object name
    tbl_name TEXT,  -- associated table name (for indexes/triggers: the parent table)
    rootpage INT,   -- root B-tree page number (0 for views/triggers)
    sql TEXT        -- original CREATE statement text (NULL for auto-indexes)
);

For the temp database, the equivalent is sqlite_temp_master.

On database creation, FrankenSQLite creates page 1 as a table leaf page containing zero rows. The first CREATE TABLE inserts a row into sqlite_master with the CREATE statement text. Every DDL operation (CREATE, DROP, ALTER) modifies this table and increments a schema cookie (a 32-bit counter at header offset 40) so that prepared statements can detect schema changes and re-prepare automatically.

ATTACH DATABASE adds a secondary database with its own sqlite_master (aliased as <schema>.sqlite_master). Cross-database queries use fully qualified names (schema.table).

The Lock-Byte Page

For databases larger than 1 GiB, the page containing byte offset 0x40000000 (1,073,741,824 — the POSIX advisory "pending byte") is reserved for file locking and must never store B-tree content. For 4096-byte pages, this is page 262145 ((0x40000000 / 4096) + 1). The exact page number depends on page size.

SQLite skips this page during allocation (allocateBtreePage() in btree.c). FrankenSQLite replicates this behavior precisely:

Never allocate this page for B-tree storage or freelist use.
On PRAGMA integrity_check, verify this page is not referenced by any B-tree pointer.
The page is simply a hole in the file that exists solely so POSIX fcntl() locks can operate on it without corrupting B-tree data.

This is critical for multi-process locking compatibility: if a B-tree page were to occupy the lock-byte region, concurrent readers using POSIX advisory locks would silently corrupt it.

Compatibility Runtime Today, Native Mode Design

The current user-facing runtime is the compatibility/pager-backed path over standard SQLite .db plus rollback-journal/WAL files. The codebase also contains substantial native-mode / ECS / time-travel machinery in crates, tests, and design docs, but PRAGMA fsqlite.mode is not currently a stable public Connection switch in the same way this README originally implied.

Compatibility Runtime (Current)

The database file uses the standard SQLite .db layout, and WAL frames use the standard SQLite WAL format. An existing C SQLite database opens without conversion when its header declares encoding 1 (UTF-8) or encodings 2/3 (UTF-16le/UTF-16be); mixed-encoding ATTACH is rejected. A FrankenSQLite-written database remains readable by C SQLite without conversion. Native public connections with a caller-owned blocking pool can emit a separate .wal-fec sidecar containing RaptorQ repair symbols after WAL fsync; the standard recovery path does not yet consume those symbols. The core .db remains SQLite-compatible when checkpointed. This mode is the default and is used for conformance testing against C SQLite within that supported surface.

Native Mode (Design / Partial Implementation)

Primary durable state is an ECS commit stream: append-only CommitCapsule objects encoded as RaptorQ symbols. The source-of-truth is the commit stream, not a mutable .db file.

A CommitCapsule is the atomic unit of commit state, containing:

commit_seq and snapshot_basis
Intent log and/or page deltas
Read/write set digests
SSI witnesses

A CommitMarker is the durable "this commit exists" record: the capsule's ObjectId plus a pointer to the previous marker, forming an append-only chain. A commit is committed if and only if its marker is durable. Recovery ignores capsules without a committed marker.

Checkpointing materializes a canonical .db for compatibility export, but the commit stream remains the source of truth. Both modes expose the same SQL and API surface.

Time Travel Queries

FrankenSQLite supports temporal queries using SQL:2011-inspired FOR SYSTEM_TIME AS OF syntax. Today this works for :memory: databases only: snapshot capture returns immediately for file-backed connections, so their ring is never populated and any temporal query against a file-backed database fails with an explicit "no snapshot available" error rather than silently returning current data.

How it works:

At each COMMIT, a snapshot of the in-memory database state is captured into a ring buffer (max 256 entries). When a SELECT ... FOR SYSTEM_TIME AS OF query is issued, the matching historical snapshot is loaded and the query executes against it using the connection-level interpreted path. The live database state is restored after the query completes.

Syntax:

-- Query by commit sequence number
SELECT * FROM orders FOR SYSTEM_TIME AS OF COMMITSEQ 42;

-- Query by timestamp (Unix seconds, ISO-8601, or SQLite datetime format)
SELECT * FROM orders FOR SYSTEM_TIME AS OF '2024-06-15 09:30:00';

What works:

COMMITSEQ-based time travel returns verified historical results. The conformance corpus now compares FOR SYSTEM_TIME AS OF COMMITSEQ ... reads against shadow rusqlite databases stopped at the same commit boundary.
Timestamp-based time travel resolves against the in-memory compatibility snapshot ring. External conformance currently pins the "latest retained snapshot" case with a far-future timestamp and explicit failure when no retained snapshot matches.
Live-state preservation: after a historical SELECT completes, the compatibility-runtime connection restores the live source state instead of leaving the historical snapshot swapped in.
No silent fallback: queries against non-existent commit sequences or timestamps return explicit errors rather than silently returning current data.
Coverage split: the public conformance suite now covers COMMITSEQ historical parity, delete/update historical visibility, latest-snapshot timestamp resolution, missing-snapshot errors, and live-state preservation after historical reads; internal engine tests additionally cover empty-table snapshots.

Limitations:

:memory:-only. capture_time_travel_snapshot early-returns for any non-:memory: path, so file-backed connections never accumulate snapshots and every file-backed FOR SYSTEM_TIME AS OF query errors explicitly. File-backed historical reads are design work: the .fsqlite-history sidecar chosen in docs/design/time-travel-file-backed.md is not yet implemented.
Snapshots are stored in memory (ring buffer, max 256). Oldest snapshots are evicted when the buffer is full.
JOINs and subqueries in time-travel SELECT use the interpreted execute_join_select path.
The VDBE/pager SetSnapshot + VersionStore path (for file-backed databases with page-level MVCC) is wired but not yet populated during normal operation. That remains the Native-mode enhancement needed for file-backed historical reads.

ECS: The Erasure-Coded Stream Substrate

In Native mode, every durable object (commit capsules, page snapshots, WAL segments, index checkpoints, schema snapshots) is stored as an ECS object.

Content-Addressed Identity

Every object is identified by a 128-bit content address:

ObjectId = Trunc128( BLAKE3( "fsqlite:ecs:v1" || canonical_header || payload_hash ) )

BLAKE3 truncated to 128 bits (16 bytes) provides sufficient collision resistance for the non-adversarial setting and halves storage overhead compared to full 256-bit hashes. Objects are immutable: the same content always produces the same ObjectId.

SymbolRecord Envelope

The atomic unit of physical storage is a SymbolRecord:

┌────────┬─────────┬───────────┬─────┬─────┬──────────────┬─────────┬──────────┐
│ Magic  │ Version │ ObjectId  │ OTI │ ESI │ Symbol Data  │ XXH3    │ Auth Tag │
│ "FSEC" │ u8 (1)  │ [u8; 16]  │     │ u32 │ [u8; T]      │ u64     │ [u8; 16] │
└────────┴─────────┴───────────┴─────┴─────┴──────────────┴─────────┴──────────┘

OTI (Object Transmission Information) carries the RaptorQ metadata needed for decoding: transfer length, symbol alignment, symbol size, source blocks, and sub-blocks. Repair symbol generation is deterministic: the same object and repair count always produce identical repair symbols, enabling idempotent writes and incremental repair.

Local Physical Layout (Native Mode)

foo.db.fsqlite/
├── ecs/
│   ├── objects/          -- symbol records, sharded by ObjectId prefix
│   │   ├── 00/
│   │   └── ff/
│   ├── commit_stream/    -- append-only CommitMarker sequence
│   │   └── stream.log
│   └── manifest.root     -- RootManifest (the ONE mutable file)
├── cache/                -- rebuildable derived state
│   ├── btree.cache       -- materialized B-tree pages
│   ├── index.cache       -- secondary index pages
│   └── schema.cache      -- parsed schema
└── compat/               -- optional compatibility export
    ├── foo.db            -- standard SQLite database file
    └── foo.db-wal        -- standard WAL

The RootManifest is the bootstrap object: it maps the logical database name to the current committed state ObjectId. It is the only mutable file in the entire layout. Repair overhead is configurable via PRAGMA raptorq_overhead (default: 20%, meaning 1.2x source symbols stored).

Native Mode Commit Protocol (Design)

The Native-mode commit protocol decouples bulk durability (payload bytes) from ordering (the marker stream). Writers persist CommitCapsule payloads concurrently using bulk I/O off the critical section. A single sequencer (WriteCoordinator) serializes only the tiny ordering step: validation, commit_seq allocation, and CommitMarker append.

Writer path (concurrent):

Finalize the write set (pages and/or intent log).
Run SSI validation using the witness plane. If SSI aborts, return SQLITE_BUSY_SNAPSHOT.
Publish witness evidence objects (pre-marker) using the cancel-safe two-phase publication protocol.
Build the CommitCapsule deterministically from intent log, page deltas, snapshot basis, and witness references.
RaptorQ-encode the capsule into systematic + repair symbols.
Persist capsule symbols to local symbol logs (and optionally stream to replicas) before acquiring the commit sequencing critical section.
Submit a tiny publish request to the WriteCoordinator containing the capsule ObjectId, write-set summary, and witness references. Await the coordinator response.

WriteCoordinator loop (serialized, tiny I/O):

FCW validation using write-set summaries (no full capsule decode needed). SSI re-validation checks for dangerous structures created by concurrent commits after the writer's local validation.
Allocate commit_seq (gap-free, derived from marker stream tip).
Persist a CommitProof ECS object.
FSYNC_1 — barrier ensuring capsule symbols and proof are durable before the marker references them.
Append CommitMarker record (~96 bytes) to the marker stream.
FSYNC_2 — barrier ensuring the marker is durable before the client receives a success response.
Publish commit_seq to shared memory with Release ordering.
Respond to the client.

Why two fsync barriers:

FSYNC_1 prevents "committed marker, lost data" — the worst-case native mode failure where recovery finds a marker but cannot decode its capsule.
FSYNC_2 prevents "client thinks committed, marker not persisted" — a silent transaction loss on crash.

Batching can amortize the two barriers across multiple commits. The shipped implementation must measure the resulting latency on the release matrix rather than assume an NVMe barrier cost.

ECS Compaction (Design)

Native Mode's append-only symbol logs (ecs/symbols/*.log) grow indefinitely. The design reclaims storage with a mark-and-compact process intended to be cancel-safe, crash-safe, cross-process safe, and incrementally schedulable. Its query-latency impact is not yet quantified.

Compaction triggers:

Space amplification: total_log_size / live_data_size > 2.0 (configurable via PRAGMA).
Time interval: PRAGMA fsqlite.auto_compact_interval.
Manual: PRAGMA fsqlite.compact.

The four phases:

Mark: Start from the RootManifest and active commit marker stream. Trace all reachable CommitCapsule, PageHistory, and witness objects. Build a BloomFilter of live ObjectIds.
Compact: Create new symbol log segments using temporary names (segment-XXXXXX.log.compacting). Scan old logs; copy live symbols to new segments, discard dead objects. Fsync new segments.
Publish: Two-phase atomic publication. First, publish the new object locator cache. Then, rename compacted segments into place. Old segments are NOT retired until both the new segments and locator are durable — preventing a crash from leaving the system with neither valid data set.
Retire: Old segments are retired only once no active readers depend on them, tracked via segment leases. On Unix, old segments are unlinked once retired (open handles remain valid). On Windows, old segments are renamed to .retired and deleted after all handles close.

Safety invariant: Compaction never mutates an existing segment. At all times, there exists at least one complete set of symbol logs sufficient to decode any reachable object under the retention policy.

Multi-Process MVCC (Design / Partial Implementation)

The design below extends MVCC coordination across OS processes via a shared-memory file (foo.db.fsqlite-shm), analogous to SQLite's WAL-index but extended for full MVCC. It is target architecture, not the complete live runtime: today, Unix compatibility connections publish and validate the standard SQLite -shm WAL-index headers, frame/hash entries, checkpoint watermarks, locks and read marks, alongside the external lock/namespace sidecars. MVCC conflict state, including the live GC horizon, remains coordinated in process-local shared session state (ConcurrentRegistry).

Shared Memory Layout

┌─────────────────────────────────────┐
│ Header                              │
│   magic: "FSQLSHM\0"               │
│   version: u32 (1)                  │
│   next_txn_id: AtomicU64            │  ← global TxnId counter
│   commit_seq: AtomicU64             │  ← global commit sequence
│   gc_horizon: AtomicU64             │  ← min protected snapshot.high (CommitSeq)
│   checksum: u64 (xxhash3)           │
├─────────────────────────────────────┤
│ TxnSlot Array (256 slots default)   │  ← one slot per active transaction
├─────────────────────────────────────┤
│ PageLockTable Region                │  ← open-addressing hash in shared mem
├─────────────────────────────────────┤
│ SIREAD Plane                        │  ← cross-process rw-antidependency tracking
└─────────────────────────────────────┘

All fields use atomic operations. The cross-process path adds shared-memory coordination; its current cost is intentionally left unquantified until the post-async release matrix is complete.

Crash Cleanup

Each TxnSlot carries a lease timestamp. If a process crashes while holding active transactions, other processes detect the stale lease and reclaim the slot after a configurable timeout. This prevents crashed processes from pinning page versions indefinitely or blocking the GC horizon from advancing.

File-Lock Fallback

On systems where shared memory is unavailable or restricted, FrankenSQLite falls back to file-lock-based coordination (POSIX fcntl or Windows LockFileEx). This degrades to single-writer behavior but preserves correctness.

Page-Level Encryption

Status: NOT WIRED. Do not rely on FrankenSQLite for encryption at rest. The envelope-encryption implementation (PageEncryptor, DEK/KEK, Argon2id) exists in fsqlite-pager, but it is not reachable from the public API: Connection implements no PRAGMA key or PRAGMA rekey, and unrecognised PRAGMAs are silently ignored for SQLite compatibility. PRAGMA key = 'passphrase' therefore parses, returns success with no rows and no error, and the database is written unencrypted. The fsqlite-c-api shim likewise exposes no sqlite3_key/sqlite3_rekey. Wiring the key-management PRAGMAs into the connection pipeline is outstanding work. The table below describes the intended design.

The design goal is page-level encryption as a built-in feature, replacing the need for SQLite's commercial Encryption Extension (SEE).

Property	Design value (not yet reachable from the public API)
Cipher	XChaCha20-Poly1305 (AEAD)
Data key (DEK)	Random 256-bit key generated at database creation
Key-encryption key (KEK)	Argon2id(passphrase, per-database random salt)
Rekey	O(1): re-wrap DEK (planned `PRAGMA rekey = 'new_passphrase'`)
Nonce	24 bytes, random per page write
Authentication tag	16 bytes (Poly1305), stored in the page's reserved space
Reserved bytes	`reserved_bytes >= 40` (24B nonce + 16B tag)
Key management API	Planned `PRAGMA key = 'passphrase'` / `PRAGMA rekey = 'new_passphrase'`; not currently dispatched

The intended scheme is envelope encryption: pages are encrypted with the DEK; the DEK is wrapped with the KEK derived from the passphrase. Random nonces eliminate global counters and remain safe under VM snapshot reverts, crashes, forks, and distributed writers.

The Native-mode design applies encryption before RaptorQ encoding (encrypt-then-code). An attacker who corrupts encrypted ECS symbols cannot forge valid ciphertext; after the design is fully wired, RaptorQ repairs the corruption and decryption follows.

The Mathematics Behind FrankenSQLite

This section records mathematical models that guide the design. A model is not evidence that the implementation satisfies its assumptions: executable proofs, fault-injection tests, and citation-grade measurements remain separate release gates.

Probabilistic Conflict Model (Birthday Paradox for Pages)

Page-level MVCC raises an obvious question: how often do two transactions actually collide on the same page? The answer maps directly to the birthday paradox.

Setup:
    P = total database pages
    W = pages written per transaction (uniform random)
    N = number of concurrent writers

Pairwise conflict probability (two transactions T1, T2):
    P(conflict) = 1 - e^(-W² / P)

    Derivation: P(no conflict) = C(P-W, W) / C(P, W)
                               ≈ ((P-W)/P)^W
                               ≈ e^(-W²/P)   for W << P

Any-conflict probability (N concurrent transactions):
    P(any conflict among N) ≈ 1 - e^{-N(N-1)W² / (2P)}

    This is the birthday paradox with n = N*W "people" and P "days."

Uniform-model threshold: Under the assumptions above, overlap becomes likely when N * W ≈ √P. Real B-tree workloads are not uniform, so this threshold is illustrative rather than a prediction of production conflict rates.

Worked example:

Hypothetical uniform workload with
P = 100,000 pages, W = 50 pages/txn, N = 8 writers:

    Pairwise:  P(conflict) ≈ 1 - e^(-2500/100000) ≈ 0.025  (2.5%)
    Per-txn:   P(any conflict for one txn) ≈ 1 - (1-0.025)^7 ≈ 0.16  (16%)

Real workloads aren't uniform — they follow Zipf distributions where a few hot pages absorb most writes:

Zipf access probability for page ranked k:
    p(k) = (1/k^s) / H(P, s)

    where H(P, s) = Σ_{i=1}^{P} 1/i^s   (generalized harmonic number)
          s is a workload parameter that must be fitted from traces

Conflict probability under Zipf:
    P(conflict, Zipf) ≈ 1 - Π_k (1 - p(k))^{n_k}

Compared with a uniform model, a fitted Zipf distribution concentrates conflicts on hot pages. Safe write merging can help when intents on such a page commute, but the benefit is workload-specific.

Result: The birthday-paradox model is a first-order hypothesis generator from page count, write-set size, and writer count. It does not establish near-linear scaling; the benchmark matrix must do that.

GF(256) Arithmetic: The Algebra of Erasure Coding

Every RaptorQ operation — encoding, decoding, repair — bottoms out in arithmetic over GF(2⁸), the Galois field with 256 elements. Each byte is a field element. FrankenSQLite also reuses this algebraic substrate for patch encoding and history compression.

The field GF(2⁸) = GF(2)[x] / p(x), where:
    p(x) = x⁸ + x⁴ + x³ + x² + 1    (irreducible polynomial, hex: 0x11D)

256 elements map to bytes 0x00-0xFF. Every byte is a polynomial:
    0xA3 = x⁷ + x⁵ + x + 1

Addition:       a + b = a XOR b   (also subtraction — every element is its own inverse)
Additive identity: 0x00

Multiplication via log/exp tables:
    The multiplicative group GF(256)* has 255 elements, cyclic with generator g = 2.

    OCT_LOG[a] = k   such that g^k = a    (for a ≠ 0)
    OCT_EXP[k] = g^k (for k = 0..254, extended to 510 entries to avoid mod)

    multiply(a, b):
        if a == 0 or b == 0: return 0
        return OCT_EXP[OCT_LOG[a] + OCT_LOG[b]]    // no mod needed: max index = 508 < 510

    inverse(b):
        return OCT_EXP[255 - OCT_LOG[b]]

    Total table storage: 768 bytes (256 + 512). O(1) per operation.
``$

**\text{Worked} \text{example} (0\text{xA3}  \times  0\text{x47}):**

$`$
\text{OCT\_LOG}[0\text{xA3}] = 146,  \text{OCT\_LOG}[0\text{x47}] = 63
146 + 63 = 209
\text{OCT\_EXP}[209] = 0\text{x8E}
∴ 0\text{xA3}  \times  0\text{x47} = 0\text{x8E}  (142 \text{decimal})
$`$

\text{For} \text{bulk} \text{operations} (\text{the} \text{inner} \text{loop} \text{of} \text{RaptorQ} \text{encoding}/\text{decoding}), \text{FrankenSQLite} \text{precomputes} \text{the} \text{full} 256 \times 256 \text{multiplication} \text{table}:

$``
MUL_TABLES: [[u8; 256]; 256]    // 65,536 bytes; cache residency is host-dependent

Precomputed once at startup:
    MUL_TABLES[a][b] = if a == 0 || b == 0 { 0 }
                        else { OCT_EXP[OCT_LOG[a] + OCT_LOG[b]] }

Usage (single table lookup, O(1)):
    fn mul(a: u8, b: u8) -> u8 { MUL_TABLES[a as usize][b as usize] }

The critical hot-path operation is symbol multiply-and-add (fused dst[i] ^= MUL[c][src[i]]), which runs in the inner loop of every RaptorQ decode. For a 4 KiB symbol this performs 4,096 table lookups and XOR operations; its latency depends on the implementation, compiler, and host and is therefore left to the benchmark matrix.

Why GF(256)? Byte-aligned arithmetic avoids bit packing, and 256 elements provide enough algebraic structure for the RaptorQ constraint system while keeping values byte-addressable. The 64 KiB multiplication table's actual cache residency and throughput are host-dependent and remain benchmark work. Its lookup loop can be branch-free, but data-dependent table indices are not a constant-time security proof.

Fountain Codes: Information-Theoretic Durability Bounds

Traditional redundancy (RAID, triple replication) provides fixed fault tolerance. The native-mode design uses RaptorQ fountain codes (RFC 6330), which can generate additional repair symbols from a source block.

Source data: K symbols (each symbol = one database page, typically 4096 bytes)

Encoding:
    Source symbols:  C'[0], C'[1], ..., C'[K-1]     (the original pages)
    Repair symbols:  generated on demand at supported, distinct ESIs,
                     within codec and schedule limits
    Each repair symbol = GF(256) linear combination of intermediate symbols

Decoder failure bounds from RFC 6330 §5.8, for its compliant decoder and
independently, uniformly sampled encoding-symbol identifiers (ESIs), stated
in terms of extended source block size K':
    With K' received symbols:            failure is at most 10⁻²
    With K'+1 received symbols:          failure is at most 10⁻⁴
    With K'+2 received symbols:          failure is at most 10⁻⁶

These are code-level decoder probabilities, not an end-to-end database
durability claim. Storage-loss correlation, metadata, implementation defects,
and the symbol-selection policy require separate analysis.

Repair symbols supply additional equations over intermediate symbols. Recovery requires enough independent equations: neither every repair symbol nor every subset of K received symbols guarantees recovery. A deficient system needs more verified symbols or an explicit decode failure. The sampling-dependent bounds above are specified by RFC 6330 §5.8; they are not measured loss probabilities for FrankenSQLite's fixed test schedules.

An end-to-end durability bound would additionally need a validated failure model, correlation assumptions, object-size policy, symbol placement and retention rules, and evidence that the shipped implementation matches that model. FrankenSQLite does not currently publish such a numeric bound.

How encoding works (simplified):

Step 1 — Constraint matrix A (L × L, where L = K' + S + H):
    Rows 0..S-1:          LDPC constraints  (sparse, ~7 non-zeros/row, over GF(2))
    Rows S..S+H-1:        HDPC constraints  (dense, over GF(256))
    Rows S+H..L-1:        LT constraints    (sparse, from degree distribution)

         |<--- K' cols --->|<- S cols ->|<- H cols ->|
    LDPC |   LDPC_LEFT     | I_S (SxS) |     0      |  S rows
    HDPC |   MT × GAMMA    |     0     | I_H (HxH)  |  H rows
    LT   |   LT_MATRIX     |     0     |     0      |  K' rows

Step 2 — Solve A × C = D for intermediate symbols C (Gaussian elimination)

Step 3 — Generate an encoding symbol with ESI e:
    if e < K: return source symbol C'[e]        (systematic: original data)
    else:     return LTEnc(K', C, e + K' - K)   (map repair ESI to internal ISI)
    ISIs K..K'-1 are local padding, not additional transmitted source data.

Decoding is a two-phase process:

Phase 1 — Peeling (O(K) average):
    While any row has exactly 1 unresolved column c:
        C[c] = (D[r] ⊕ Σ known terms) × inverse(a_{r,c})
    Continue until no degree-one row remains.

Phase 2 — Gaussian elimination on the "inactive" subsystem:
    Solve the remaining dense subsystem.
    Dense work: O(I³ + I² × T) for I inactive symbols of size T.
    The second term accounts for elimination on the payload bytes.

The peeling fraction, inactive-system size, and runtime cost depend on the code parameters and input. They are not current FrankenSQLite measurements; the release matrix must measure the shipped implementation.

Multicast bandwidth goal: One sender stream can serve several receivers, but each must collect enough independent equations. K/(1-p) is the expected transmission count for one receiver to receive K packets under independent loss probability p. It does not guarantee decoding or completion of all N receivers. If each receiver's deadline failure probability is at most q, the union bound is Nq; independent receiver failures give 1-(1-q)^N.

The native replication benchmark must compare sender bytes, repair/feedback traffic and slowest-receiver completion under the same failure budget and loss model. No fixed repair percentage or achieved multicast speedup is claimed.

Result: RaptorQ supplies a standards-defined erasure-code building block. The repository treats database-level durability as a property to prove and test across the complete storage protocol, not as a probability inferred from the decoder alone.

Safe Write Merge Ladder (Intent + Structured Patches)

When two transactions modify the same physical page, strict page-level FCW aborts one on the current live path. The dormant design could sometimes do better: if the intent operations commute (for example, inserts into distinct keys), the loser could be rebased onto the latest committed snapshot and still produce a correct state.

While XOR-deltas compose linearly as byte vectors, byte-disjointness is not a safe merge rule for SQLite structured pages (B-tree pages, overflow pages, freelist pages, pointer-map pages). Internal pointers and defragmentation can make two disjoint byte writes semantically dependent, causing lost updates.

Counterexample (B-tree lost update):

T1 moves a cell from offset X to Y and updates the cell pointer array to Y.
T2 updates the cell payload bytes at the old offset X.
The byte supports can be disjoint, yet the merged page points at Y (old value) and T2's update at X becomes unreachable garbage.

Therefore, the design permits merge only through the SAFE ladder:

Priority	Strategy	Safety Guarantee
1	Deterministic rebase replay	Re-executes intent ops against current committed snapshot
2	Structured page patch merge	Disjoint by `cell_key_digest`; header ops serialized; invariants checked
3	Abort/retry	No safe merge possible

Accepted merge-policy values are PRAGMA fsqlite.write_merge = SAFE | LAB_UNSAFE; OFF is rejected. The ladder above remains dormant in the live commit path, and raw byte-range XOR merging is forbidden for SQLite structured pages.

Three-Tier Checksum Architecture

Not all checksums are created equal. The design assigns algorithms by integrity and trust requirement; throughput is deliberately left to release artifacts.

``$ \text{Tier} 1 — \text{Hot}-\text{path} \text{integrity} (\text{every} \text{page} \text{access}): \text{Algorithm}: \text{XXH3}-128 \text{Collision}: 2⁻¹²⁸ ≈ 3 \times 10⁻³⁹ \text{Where}: \text{Buffer} \text{pool}, \text{MVCC} \text{version} \text{chain}, \text{cache} \text{reads}, \text{WAL} \text{frame} \text{verification}

\text{Tier} 2 — \text{Content} \text{identity} (\text{object} \text{addressing}): \text{Algorithm}: \text{BLAKE3} (\text{truncated} \text{to} 128 \text{bits}) \text{Collision}: \text{Cryptographic} (2⁻¹²⁸ \text{practical} \text{security}) \text{Where}: \text{ObjectId} \text{derivation}, \text{CommitCapsule} \text{identity}, \text{ECS} \text{object} \text{naming}

\text{Tier} 3 — \text{Cryptographic} \text{authentication} (\text{trust} \text{boundaries}): \text{Algorithm}: \text{asupersync}::\text{security}::\text{SecurityContext} (\text{key}-\text{dependent}) \text{Where}: \text{Replication} \text{transport}, \text{authenticated} \text{symbols}, \text{cross}-\text{node} \text{verification} $``

Policy rules that prevent misuse:

✗ NO SHA-256 on hot paths      (hot-path integrity uses XXH3-128; measured
                                 throughput remains release-evidence-only)
✗ NO XXH3 for content addressing (not cryptographic — vulnerable to preimage attacks)
✗ NO rolling own crypto         (security tier uses asupersync's vetted primitives)
✓ BLAKE3 bridges integrity tiers (cryptographic content identity without substituting
                                  for keyed authentication at trust boundaries)

WAL checksum chain (cumulative hash):

WAL header checksum:
    (s1, s2) = wal_checksum(header[0..24], 0, 0, native_byte_order)

Frame N checksum:
    (s1, s2) = wal_checksum(frame_hdr[0..8] ∥ page_data, s1_{N-1}, s2_{N-1}, native)

    Per 8-byte chunk (a, b):
        s1 = s1.wrapping_add(a).wrapping_add(s2)
        s2 = s2.wrapping_add(b).wrapping_add(s1)

Each frame's checksum incorporates the previous frame's checksum, creating a hash chain. Modifying any byte in the WAL invalidates all subsequent frames' checksums. This is how crash recovery knows exactly where the valid data ends.

Five levels of integrity verification (PRAGMA integrity_check):

Level	Scope	What It Checks
1	Page-level	Page type flags, header field ranges, XXH3 checksum (if enabled)
2	B-tree structural	Cell pointers within bounds, keys sorted, child pointers valid, freeblock list well-formed
3	Record format	Header varints valid, serial type encoding well-formed (types 10/11 tolerated as zero-length per canonical SQLite), payload sizes match, overflow chains intact
4	Cross-reference	Every page accounted for, no page in multiple B-trees, freelist consistent, pointer map matches
5	Schema	sqlite_master readable, root page numbers match existing B-trees, index entries match table data

Result: The three-tier architecture keeps hot-path integrity separate from cryptographic authentication at trust boundaries. The WAL checksum chain detects corruption at the affected frame. Five levels of integrity check give you surgical precision for diagnosing problems.

E-Processes: Anytime-Valid Invariant Monitoring

The monitoring design uses e-processes for sequential statistical evidence. Their anytime-valid threshold requires a valid conditional null model; it is not a proof that runtime instrumentation observes every invariant. Any observed hard correctness violation must fail immediately, regardless of its e-value.

An e-process (E_t) is a non-negative supermartingale starting at 1:
    E_0 = 1
    E[E_t | F_{t-1}] ≤ E_{t-1}    under null hypothesis H_0

Key guarantee (Ville's inequality):
    P_{H_0}(∃t : E_t ≥ 1/α) ≤ α

    You can check E_t after EVERY operation and reject H_0
    whenever E_t crosses the threshold — no Bonferroni correction needed!

Betting martingale update rule:
    E_t = E_{t-1} × (1 + λ × (X_t - p_0))

    where:
        X_t = 1 if invariant violation observed, 0 otherwise
        p_0 = upper bound on E[X_t | F_{t-1}] under the statistical null
        λ = predictable bet, 0 ≤ λ ≤ 1/p_0 for this upper-tail null (0 < p_0 < 1)

Under H_0, conditioning on the full past gives expected multiplier at most one. Equality gives a martingale, but does not keep every sample path near one. A marginal mean alone is insufficient for that conditional guarantee.

For independent Bernoulli observations with rate p_1 and a fixed admissible λ, the expected log increment is p_1 log(1+λ(1-p_0)) + (1-p_1) log(1-λp_0). It equals KL(p_1 ∥ p_0) only at the corresponding optimal bet, not for every λ. Detection time also depends on non-violation observations and overshoot; counting violations alone supplies no universal delay bound.

Monitored invariants:

E-Process	Invariant	What a Violation Means
E₁	INV-1: Monotonic TxnIds	`AtomicU64` counter went backward (hardware fault?)
E₂	INV-2: Lock exclusivity	Two transactions hold the same page lock (concurrency bug)
E₃	INV-3: Version chain order	Committed versions violate descending CommitSeq order
E₄	INV-4: Write set consistency	Transaction wrote a page it doesn't hold a lock on
E₅	INV-5: Snapshot stability	Snapshot mutated after creation (memory corruption)
E₆	INV-6: Commit atomicity	Partial commit visible (the worst possible bug)
E₇	INV-7: Serialized exclusivity	Two serialized-mode writers active simultaneously

Configuration:
    p0:         0.001      // null: violation rate ≤ 0.1%
    lambda:     0.5        // moderate bet
    alpha:      0.05       // reject at 5% significance → threshold = 1/0.05 = 20
    max_evalue: 10¹⁵       // overflow guard

E-processes permit repeated threshold checks under their stated model. A null budget of 0.1% cannot promise detection of a smaller 0.01% rate. Statistical monitoring remains supplementary evidence; it never licenses a nonzero rate of known database correctness violations.

Mazurkiewicz Traces: Exhaustive Concurrency Verification

Mazurkiewicz traces classify schedules by a proved independence relation. Exhaustive exploration is relative to a bounded model and its action semantics; it requires complete exploration and sound independence, not merely a trace library or a passing randomized run.

A trace monoid M(Σ, I) is defined over:
    Σ = alphabet of actions
        e.g., read_page(T1, P1), write_page(T2, P3), commit(T1), ...
    I = symmetric independence relation on Σ × Σ
        (a, b) ∈ I means swapping a and b doesn't change observable behavior

Two execution sequences w_1, w_2 are trace-equivalent (w_1 ≡_I w_2)
if one can be transformed into the other by swapping adjacent independent actions.

The trace monoid M(Σ, I) = Σ* / ≡_I
    (the set of all equivalence classes)

Independence relation for MVCC operations:

Action A	Action B	Independent?	Reason
`read(T1, P1)`	`read(T2, P2)`	Yes (if P1≠P2)	Different pages, read-read
`read(T1, P1)`	`read(T2, P1)`	Yes	Read-read, same page (MVCC snapshots)
`read(T1, P1)`	`write(T2, P1)`	No	Write changes what T1 might see
`write(T1, P1)`	`write(T2, P2)`	Conditional	Different data pages alone do not exclude shared allocation, structural or SSI dependencies
`write(T1, P1)`	`write(T2, P1)`	No	Same-page conflict
`commit(T1)`	`commit(T2)`	No	Shared validation and publication order
`begin(T1)`	`begin(T2)`	No	Snapshot capture is ordering-dependent

Foata normal form groups independent actions. DPOR can reduce redundant schedules, but the remaining space can still grow exponentially. A runtime claim must record bounds, enabledness/commutativity assumptions, completed exploration and the mapping from model actions to actual engine behavior.

The goal is to check each distinct bounded schedule against the seven MVCC invariants while avoiding equivalent schedules. Any claimed reduction or coverage requires a completed exploration receipt with those bounds and assumptions; the method alone establishes neither count nor coverage.

Formal Safety Proofs

The following six safety and liveness arguments state obligations and assumptions for the MVCC implementation. They are not machine-checked proofs of the complete engine.

Theorem 1: No Page-Ownership Wait Cycles

Claim: Nonblocking page ownership does not create page-lock wait cycles.

Proof:
    1. A deadlock requires a cycle in the wait-for graph.
    2. try_acquire() never blocks — it returns Err(SQLITE_BUSY) immediately
       if the lock is held by another transaction.
    3. This failed page-ownership acquisition adds no wait edge.
    4. With no page-ownership wait edges, there is no cycle in that graph.
    5. Therefore this mechanism cannot cause a page-lock deadlock. QED ∎

Registry/shard mutexes, I/O and lifecycle waits have separate liveness
obligations. This argument does not prove global deadlock freedom or remove
the need for cancellation, deadlines and lock-order review elsewhere.

Theorem 2: Snapshot Isolation (consistent reads)

Claim: Every transaction observes a consistent snapshot — it sees either
all or none of any other transaction's writes, never a partial set.

Proof: For reading transaction T_r with snapshot S_r (where S_r.high is
the CommitSeq at T_r's BEGIN), and any writer T_w that committed with
commit_seq C_w and created versions {V_1, ..., V_k}:

    visible(V_i, S_r) = (0 < C_w <= S_r.high)

    This condition depends ONLY on C_w and S_r.high, not on i.
    All versions of T_w share the same commit_seq C_w. The publication
    frontier must advance only after the complete version set is installed,
    with synchronization making those versions visible to snapshot readers.
    ∴ visible(V_i, S_r) has the same truth value for all i ∈ {1,...,k}.

    Exhaustive cases:
    • T_w committed after snapshot → sees NONE  (C_w > S_r.high)
    • T_w not yet committed       → sees NONE  (commit_seq = 0 fails the > 0 rule)
    • T_w committed before snapshot → sees ALL  (C_w <= S_r.high)

    In no case does T_r see a strict subset of T_w's writes.
    Snapshot S_r is immutable (INV-5), so this truth value doesn't change
    during T_r's lifetime.  QED ∎

Theorem 3: First-Committer-Wins

Claim: Under the live strict-FCW path, writers with conflicting page P changes
cannot both commit from snapshots excluding the other's publication.
The dormant SAFE-ladder design would permit
both only if a semantic resolution (intent replay / structured patch) produced
a state equivalent to some serial ordering.

Proof (two cases):
    Case A — Concurrent lock contention:
        T1 acquires lock on P first. T2 calls try_acquire(P) → Err(SQLITE_BUSY).
        T2 cannot write P at all. At most T1 commits with P.

    Case B — Sequential (T1 commits and releases before T2 acquires):
        T2 acquires lock on P and writes it.
        If T1 committed after T2's snapshot, validation makes T2 abort/retry.
        If T2's snapshot already includes T1, both may commit in serial order.
        A future activation of the SAFE
        ladder could instead commit rebased/merged deltas after validation.

    In all cases, the final committed page version follows validated serial
    order or conflict rejection. The dormant design additionally requires any
    future merged page to incorporate both writers in a serializable way. QED ∎

Theorem 4: GC Safety (no premature version reclamation)

Claim: Logical pruning preserves versions needed by protected snapshots and
ordinary future snapshots. Physical reuse also requires reader-guard safety.

Setup:
    gc_horizon = min(protected snapshot.high), in CommitSeq order.
        With no retention obligations: gc_horizon = latest committed sequence.
    Version V of page P is reclaimable iff:
        V.commit_seq < gc_horizon
        AND ∃ V' in version_chain(P):
            V'.commit_seq > V.commit_seq
            AND V'.commit_seq ≤ gc_horizon

Proof:
    For any protected T_a: T_a.snapshot.high ≥ gc_horizon
    The superseding V' satisfies V'.commit_seq ≤ gc_horizon ≤ T_a.snapshot.high
    ∴ V' is visible to T_a's snapshot (V'.commit_seq ≤ S.high).
    Since V'.commit_seq > V.commit_seq, resolve(P, T_a.snapshot) returns V'
    or newer — never V.
    Same argument holds for ordinary future snapshots with high ≥ gc_horizon.
    Historical requests below it need separately retained history or an
    explicit unavailable error; they are not covered by this argument.
    QED ∎

Theorem 5: Memory Boundedness

Conditional claim: if every retention obligation lasts at most D, and at most
A(D) commits can occur in ANY interval of length D, the logically required
committed versions per page after pruning are bounded by A(D) + 1.

Proof:
    The oldest active transaction started at most D seconds ago.
    At most A(D) commits occurred in those D seconds.
    Each creates at most one version per page.
    The version chain needs at most A(D) versions above gc_horizon,
    plus one at/below the horizon. All versions below are reclaimable
    by Theorem 4.  QED ∎

    An average commit rate alone does not bound bursts and cannot replace A(D).
    Pending GC work, private versions, reader guards, and time-travel retention
    require separate physical-memory accounting.

This is a conditional design bound, not a measured RSS limit. Public active and idle transaction lifetime enforcement (bd-6hdwo.19/.20) and complete byte and retention accounting (bd-6hdwo.21/.22) remain open requirements.

Theorem 6: Liveness (finite termination)

Claim: Every transaction either commits or aborts in finite time,
assuming (a) the application calls COMMIT or ROLLBACK, (b) runnable tasks and
lock holders make progress, (c) every I/O/allocation wait completes or returns
an error, and (d) retries and retained-history work have finite bounds.

Proof sketch:
    Begin:    bounded admission after required waits complete
    Read:     version chain bounded under Theorem 5's stated assumptions
    Write:    try_acquire is non-blocking, COW is O(page_size)
    Commit:   finite validation scan and WAL append under these assumptions
    Abort:    O(write_set_size + page_locks_size)
    Finite work plus progress of every required wait implies termination.
    Instruction counts do not bound scheduler time, I/O latency, or starvation.

Result: These arguments define obligations for the implementation. Property tests and deterministic concurrency exploration provide evidence for selected state spaces, but they are not a machine-checked proof of the complete engine.

SSI: The Cahill/Fekete Rule at Page Granularity

Snapshot Isolation alone misses write skew — an anomaly where two transactions each read something the other writes, producing a result impossible under serial execution. FrankenSQLite applies Serializable Snapshot Isolation (SSI) using the conservative Cahill/Fekete rule at page granularity.

The dangerous structure (rw-antidependency cycle):

    T1 --rw--> T2 --rw--> T3

    T1 read something T2 later wrote (rw edge T1→T2)
    T2 read something T3 later wrote (rw edge T2→T3)
    T3 committed before T1 in serialization order

T2 is the "pivot" — it has both incoming and outgoing rw-antidependency edges.

Conservative abort rule (Page-SSI):
    At commit time, if a transaction has BOTH:
        has_incoming_rw = true   (someone read a page I wrote)
        has_outgoing_rw = true   (I read a page someone else wrote)
    → ABORT the pivot transaction.

This is conservative: it may abort transactions that wouldn't actually cause
write skew. But it never misses a genuine anomaly.

Decision-theoretic justification:

Loss matrix:
                  | commit (a=0)  | abort (a=1)  |
    S = anomaly   |   L_miss=1000 |   0           |
    S = safe      |   0           |   L_fp=1      |

Abort if P(anomaly | evidence) > L_fp / (L_fp + L_miss)
       = 1 / 1001 ≈ 0.001

The loss values above are an illustrative policy preference, not measured
costs or a calibrated threshold for the current engine. They explain why the
design favors a retry over an undetected anomaly. PostgreSQL's row-granular SSI
is useful prior art, but its measurements do not establish FrankenSQLite's
page-granular abort or false-positive rate; those remain release-matrix work.

Page-SSI tracking via the SireadTable:

SireadTable: 64 shards, each a Mutex<HashMap<PageNumber, SmallVec<TxnId>>>

On every page read: record (page_number, reading_txn_id) in SireadTable
On commit: scan SireadTable for pages in write_set
    → if any reading transaction is still active → set has_outgoing_rw on reader
    → if committing transaction has pages read by committed writers → set has_incoming_rw
    → if BOTH set → abort pivot

Downgrade: PRAGMA fsqlite.serializable = OFF  → snapped at BEGIN CONCURRENT;
           commit uses FCW-only validation (plain SI, SSI edges skipped)

Result: Page-SSI is the mechanism by which BEGIN CONCURRENT targets serializable behavior without serializing every writer. Its correctness and performance are release gates; PostgreSQL measurements are prior art, not a numeric claim about this implementation.

Sheaf-Theoretic Consistency Checking

The sheaf component models each transaction's local view as a section over its read set. Its current check_sheaf_consistency checks overlapping synthetic sections against supplied observations/version chains. This is a model-level consistency check, not a serializability proof for actual multi-process SQL.

Formalism:
    Each transaction T defines a section:
        domain(T) = T.read_set                       (pages read)
        assignment(T) = { P → (version, data) }      (what T observed)

    Sheaf condition:
        For all T1, T2: if P ∈ domain(T1) ∩ domain(T2),
        then assignment(T1)[P] and assignment(T2)[P] must be consistent
        with the global version chain ordering.

    Obstruction:
        A set of sections that locally satisfy pairwise consistency
        but cannot be glued into a single global section.

The broader gluing model remains a research goal. The existing sheaf/conformal E2E test constructs synthetic sections and arithmetic task signatures; it does not open database Connections. Actual SQL history is checked separately by fsqlite-harness::serializability_oracle and the file-backed concurrency keepers. Neither model output nor a successful task schedule can replace their observed storage, transaction, publication and stock-oracle evidence.

Conformal Calibration (Design Target, Not a Current Release Gate)

Benchmark results follow unknown distributions. Any future claim about bounded MVCC overhead requires statistical rigor. The design proposes conformal prediction for distribution-free confidence intervals.

Nonconformity score:
    R_t = |observed_t - predicted_t|

Threshold (exchangeable calibration and test scores, fixed scoring procedure):
    k = ceil((n+1)(1-α))
    q = kth ordered calibration score, or +infinity when k > n

Coverage guarantee:
    P(R_{n+1} ≤ q) ≥ 1 - α    under those exchangeability conditions

    No normality assumption; heavy tails are allowed.
    Arbitrary drift or temporal dependence does not satisfy the assumptions
    merely because calibration is described as distribution-free.

This is a proposed calibration design, not a local acceptance margin. The Phase-5 v2 admission mechanics require an immutable B/T pack with full source SHAs and strict ancestry, hash-bound policy, reports/manifests, profile/host/ toolchain/feature-graph/binary provenance, and calibration and sensitivity receipts. Legacy v9 diagnostic reports cannot authorize release. No authoritative performance-policy artifact is currently tracked, so this is a typed fail-closed blocker rather than a release decision. bd-zywqc.2 tracks the remaining baseline and runner work; bd-dqdoe tracks same-source performance re-verification. The project therefore makes no current "no performance regression" claim.

Varint Encoding: Huffman-Optimal Integer Compression

SQLite's record format uses variable-length integers (varints) everywhere — record header sizes, rowids, serial type codes, overflow page pointers. The encoding is a form of prefix-free code optimized for small values.

Encoding scheme (1-9 bytes):
    Value range              Bytes   Encoding
    ─────────────────────    ─────   ────────────────────────────────
    0 to 127                 1       0xxxxxxx
    128 to 16,383            2       1xxxxxxx 0xxxxxxx
    16,384 to 2,097,151      3       1xxxxxxx 1xxxxxxx 0xxxxxxx
    ...                      ...     (continuation bit in high bit)
    > $2^{56}$                   9       11111111 xxxxxxxx × 8

    The high bit of each byte signals "more bytes follow."
    The 9th byte (if reached) uses all 8 bits for data.

Why this matters for databases: Small rowids, serial type codes, and record headers use fewer bytes than a fixed-width integer representation. The actual space reduction depends on the data distribution and is not claimed here as a universal percentage.

Decode work shape: The decoder loops over encoded bytes and tests each continuation bit. A one-byte value takes the shortest path, but whether one- or two-byte values dominate—and the resulting branch cost—depends on the database and host. No numeric varint throughput claim is made without a cited benchmark artifact.

Collation Sequences

String comparison in SQL is not memcmp — it depends on the collation sequence, which defines ordering, equality, and case sensitivity rules.

Built-in collations:
    BINARY   memcmp byte comparison (default)
    NOCASE   ASCII case-insensitive (a-z fold to A-Z, then memcmp)
    RTRIM    Like BINARY but trailing spaces are ignored

Collation selection rules:
    1. Explicit COLLATE clause wins:  WHERE name = 'foo' COLLATE NOCASE
    2. Column declaration:            name TEXT COLLATE NOCASE
    3. Left operand's collation propagates
    4. Default: BINARY

ICU collation (via fsqlite-ext-icu):
    Full Unicode collation via ICU locale rules.
    CREATE TABLE t(name TEXT COLLATE "en_US");

Collations affect not just WHERE comparisons but also ORDER BY sort order, GROUP BY grouping, DISTINCT elimination, and index lookup. A NOCASE index can satisfy a NOCASE WHERE clause without a table scan.

Foreign Key Enforcement

Foreign keys enforce referential integrity across tables. FrankenSQLite supports DEFERRABLE INITIALLY DEFERRED constraints: violations are queued during the transaction and re-checked at COMMIT.

With foreign-key enforcement enabled, PRAGMA defer_foreign_keys = ON also postpones otherwise-immediate NO ACTION checks until the end of an explicit transaction. An unresolved violation makes COMMIT fail while leaving the transaction active and deferral enabled. The application can repair the violation and retry, or issue a full ROLLBACK. A successful COMMIT or full ROLLBACK resets the pragma to OFF; enable it again for the next transaction. The stock-SQLite oracle tests in crates/fsqlite-core/tests/defer_foreign_keys_pragma_gh161_oracle.rs cover these transaction boundaries.

Enforcement modes:
    PRAGMA foreign_keys = ON    (default OFF for SQLite compat; must be per-connection)

    IMMEDIATE (default):  checked after each DML statement
    DEFERRED:             checked at COMMIT time

Actions on parent change:
    ON DELETE CASCADE     → delete all child rows referencing deleted parent
    ON DELETE SET NULL    → set FK columns to NULL
    ON DELETE SET DEFAULT → set FK columns to their DEFAULT value
    ON DELETE RESTRICT    → abort immediately (even in deferred mode)
    ON DELETE NO ACTION   → check at statement end (or COMMIT if deferred)

    Same five actions available for ON UPDATE.

Implementation:
    DML dispatch enforces each FK as an implicit action program:
    - Before INSERT on child: verify parent exists
    - Before UPDATE on child FK cols: verify new parent exists
    - After DELETE on parent: execute ON DELETE action
    - After UPDATE on parent PK: execute ON UPDATE action

Deferred foreign keys interact with savepoints: ROLLBACK TO savepoint can re-violate constraints that were previously satisfied, and the violation is re-checked at the next COMMIT.

Trigger System Architecture

Triggers fire procedural code in response to DML events. FrankenSQLite implements BEFORE, AFTER, and INSTEAD OF trigger infrastructure, but its control-flow semantics are not yet a complete SQLite match.

Trigger types:
    BEFORE INSERT/UPDATE/DELETE    fires before the row change
    AFTER INSERT/UPDATE/DELETE     fires after the row change
    INSTEAD OF INSERT/UPDATE/DELETE  only on views, replaces the DML

Pseudo-table access:
    NEW.column    → the row being inserted/updated (available in INSERT, UPDATE)
    OLD.column    → the row being deleted/updated (available in DELETE, UPDATE)

SQLite target semantics for RAISE functions:
    RAISE(IGNORE)                → abandon the rest of the current trigger
                                   program, the causing statement, and subsequent
                                   trigger programs, without rolling back changes
                                   already made
    RAISE(ROLLBACK, 'message')   → rollback entire transaction
    RAISE(ABORT, 'message')      → rollback statement, keep transaction
    RAISE(FAIL, 'message')       → stop statement but keep changes so far

Execution model:
    Trigger bodies currently re-enter Connection DML dispatch recursively;
    they are not VDBE Program subroutines.
    Each body statement is dispatched independently through the normal
    trigger/FK/constraint/transaction pipeline.
    Pure-trigger admission currently stops at depth 8. Trigger and FK-action
    programs also share an aggregate admission ceiling of 50. That aggregate
    budget is preserved across attached-schema delegation: statements executed
    on an attached child connection inherit the delegating connection's active
    recursive-program depth, and ATTACH/DETACH are rejected while any
    trigger/FK program is active (trigger bodies cannot run them at all,
    matching C SQLite's trigger-body grammar).
    Neither ceiling is a release-certified native-stack safety claim: the
    required out-of-process requested-1-MiB-stack matrix must pass in both debug
    and the exact release profile, with target and toolchain provenance, before
    a native recursive ceiling is certified.
    SQLite's default depth of 1000 remains a compatibility target gated on
    replacing recursive native dispatch with a heap work stack or trampoline.
    Recursive triggers require PRAGMA recursive_triggers = ON.

Current `RAISE(IGNORE)` handling only proves the narrower BEFORE-trigger,
single-row `SkipDml` path. Statement-wide abandonment, subsequent-trigger
suppression, and SQLite's no-rollback boundary remain release blockers.

Triggers interact with MVCC: a BEFORE trigger that reads other tables establishes rw-dependencies tracked by the SireadTable for SSI validation. A trigger that writes to other tables extends the transaction's write set and page lock set.

Shared WAL Index Hash Table and Local Page Lookup

The standard SQLite WAL index (-shm) contains a hash table mapping page numbers to WAL frame offsets. FrankenSQLite's Unix writer path publishes these entries and their committed header for stock SQLite interoperability, preserving live reader marks during append and coordinating generation changes during recovery and reset. Its own readers validate the shared publication boundary, then resolve pages through the adapter-local published page map described in the WAL section above. The shared format is implemented in wal_index.rs.

Structure:
    HASHTABLE_NPAGE = 4096    entries per hash table segment
    HASHTABLE_NSLOT = 8192    slots per hash table (2× entries for load factor ≤ 0.5)

    Hash function:
        slot = page_number * 383            (prime multiplier)
        slot = slot % HASHTABLE_NSLOT       (open addressing)

    Collision resolution: linear probing (slot + 1, slot + 2, ...)

    Multiple segments: the WAL index grows by adding hash table segments,
    each covering HASHTABLE_NPAGE frames. Lookup scans segments in reverse
    order (newest first) to find the most recent frame for a page.

Read path (no locking required):

lookup(page_number):
    for segment in segments.iter().rev():     // newest first
        slot = (page_number * 383) % 8192
        loop:
            if segment.entries[slot] == 0:     // empty slot, not in this segment
                break
            if segment.page_numbers[slot] == page_number:
                return segment.frame_offset[slot]   // found it
            slot = (slot + 1) % 8192                // linear probe
    return None  // not in WAL, read from database file

The load factor cap at 0.5 keeps the expected number of probes below 2. In C SQLite the hash table lives in shared memory (mmap), so readers access it without any system calls or lock acquisitions. FrankenSQLite's live compatibility read path instead consults its adapter-local published page map (with the capped-index backward-scan fallback); a shared O(1), syscall-free -shm read index is not the shipped hot path.

BOCPD: Workload Regime Detection

Database workloads are non-stationary. A write-heavy analytical job may start at 2 AM, a bulk import may spike contention, or a schema migration may temporarily change the page access pattern. Static thresholds for MVCC tuning parameters (GC frequency, version chain length limits, witness-plane hot/cold index compaction policy) will be wrong for at least one regime.

FrankenSQLite uses Bayesian Online Change-Point Detection (Adams & MacKay, 2007) to detect regime shifts in real time. BOCPD maintains a posterior distribution over the run length r_t (number of observations since the last change point):

P(r_t | x_{1:t}) ∝ Σ_{r_{t-1}} P(x_t | r_t, x_{t-r_t:t-1}) · P(r_t | r_{t-1}) · P(r_{t-1} | x_{1:t-1})

The predictive probability under the current regime is modeled as a conjugate Normal-Gamma for throughput and contention streams, and Beta-Binomial for abort rates. The hazard function uses a geometric prior with H = 1/250, corresponding to an expected regime length of ~4 minutes at one observation per second.

What BOCPD monitors:

Stream	Conjugate Model	Action on Change Point
Commit throughput (ops/sec)	Normal-Gamma	Log regime shift, adjust GC frequency
SSI abort rate	Beta-Binomial	If rate jumps, log warning; if rate drops, relax version chain limits
Page contention (locks/sec)	Normal-Gamma	Adjust witness-plane refinement and hot-index pressure controls
Version chain length	Normal-Gamma	Tighten/loosen GC watermarks

Why BOCPD instead of fixed-window averages:

No window size to tune (the algorithm infers the regime length).
Exact posterior inference via the run-length recursion (no MCMC needed).
Naturally handles multiple change points.
Computational cost: O(1) amortized after pruning low-probability run lengths.

BOCPD operates as an advisory harness component (Layer 3 in the monitoring stack), sitting above the e-process invariant monitors and conformal anomaly detection. It does not gate correctness decisions; it tunes heuristics for GC, eviction, and compaction scheduling.

Implementation Roadmap and Verification Gates

FrankenSQLite follows a 9-phase implementation plan. Each phase has specific verification gates — quantitative acceptance criteria that must pass before the next phase begins. No phase ships until every gate is green.

Phase Overview

Phase	Focus	Key Deliverables
1	Bootstrap	Workspace scaffold, core types, error handling, limits, opcodes
2	Storage Foundation	VFS traits, MemoryVfs, UnixVfs, pager, record format serialization
3	Trees and Parsing	B-tree engine, SQL parser, AST, property-based tests
4	Query Engine	VDBE bytecode VM, code generation, basic query execution
5	Persistence	WAL implementation, crash recovery, file format compatibility
6	Concurrency	MVCC engine, SSI, safe write merge ladder, garbage collection
7	SQL Completeness	Query planner, window functions, CTEs, triggers, views
8	Extensions	FTS5, R-tree, JSON1, session, ICU, misc extensions
9	Conformance	100% parity target with C SQLite, benchmarks, hardening

Universal Verification Gates (Every Phase)

1. cargo check --workspace                                   zero errors, zero warnings
2. cargo clippy --workspace --all-targets -- -D warnings     pedantic + nursery lints
3. cargo fmt --all -- --check                                all code formatted
4. cargo test --workspace                                    all tests pass
5. cargo doc --workspace --no-deps                           all public items documented

Phase-Specific Gates (Selected)

These are target acceptance criteria, not a list of achieved results. Each numeric target needs its own dated, source-bound execution or benchmark before it can support a capability or performance claim.

Phase 3 (Trees and Parsing):

B-tree proptest: 10,000-operation random sequence → all invariants hold
B-tree cursor iteration after random ops matches BTreeMap reference
Parser: 95% coverage of parse.y grammar productions
Parser fuzz: 1 hour fuzzing, zero panics

Phase 5 (Persistence):

File format: FrankenSQLite DB readable by C sqlite3 and vice versa
WAL recovery: 100 crash-recovery scenarios → zero data loss
RaptorQ WAL: recovery succeeds with up to R corrupted frames

Phase 6 (Concurrency) — the most demanding gate:

MVCC stress: 100 concurrent writers, 100 ops each → all committed rows present, no phantoms
SSI: write skew patterns abort under default serializable mode; succeed under PRAGMA fsqlite.serializable = OFF
SSI: zero false negatives (3-transaction Mazurkiewicz trace exploration)
E-process monitors: INV-1 through INV-7 → zero violations over 1M operations
GC memory: usage within 2× of minimum theoretical bound
Algebraic merge: 1,000 disjoint → zero false rejections; 1,000 overlapping → zero false acceptances
Crash model: 100 crash-recovery scenarios validating self-healing contract

Phase 9 (Conformance):

100% parity target across 1,000+ golden test files (with any intentional divergences documented + annotated)
Single-writer benchmarks within 3× of C SQLite
No regression against an immutable, same-source baseline under a provenance-bound release gate (not yet satisfied; tracked by bd-zywqc.2 and bd-dqdoe)

Risk Register

Every ambitious project has risks. Here they are, along with the mitigations that make each one manageable.

Risk	Severity	Mitigation
R1: SSI abort rate too high (Page-SSI is conservative, may false-positive)	High	Measure the current page-granular rate on the release matrix; refine SIREAD keys to page ranges if needed; evaluate the dormant intent-replay ladder only with repository benchmark evidence. PostgreSQL's row-granular results are prior art, not an estimate for this engine.
R2: RaptorQ overhead dominates CPU	Medium	Symbol sizing policy per object type; cache decoded objects aggressively via ARC; profile/tune encoder/decoder hot paths
R3: Append-only storage grows without bound	Medium	Checkpoint/compaction and enforced admission/retention budgets are required. Prune using protected snapshot.high in CommitSeq order; the horizon alone does not bound memory or storage growth.
R4: Bootstrap chicken-and-egg (need index to find symbols, need symbols to build index)	Low	Self-describing symbols and a root pointer permit scan recovery only with sufficient supported, authenticated records. Missing rank, metadata, keys or an unsupported layout must fail explicitly; full durable native bootstrap remains in progress.
R5: Multi-process MVCC coordination is complex	High	Shared-memory coordination protocol fully specified; lease-based TxnSlot cleanup handles process crashes; validate in-process first (Phase 6), cross-process follows (Phase 7)
R6: File format compatibility vs innovation	Medium	Compatibility runtime stays on standard SQLite files; Native/ECS work is an innovation layer pursued alongside parity harnesses and explicit status tracking
R7: Mergeable writes become a correctness minefield	High	Strict merge safety ladder (Section above); proptest invariants + DPOR tests; start with deterministic rebase for small op subset, expand guided by benchmarks
R8: Distributed mode correctness is hard	High	Leader commit clock as default; sheaf checks + TLA⁺ export for bounded model checking; implementation phased: single-node first, multi-node Phase 9

Open Questions

Multi-process writer performance envelope? → Benchmark shared-memory coordination overhead.
How far to refine SIREAD granularity? → Start page-only, collect witnesses, refine when proven necessary.
Symbol sizing policy per object type? → Benchmark, pick defaults, expose PRAGMAs for tuning.
Where to checkpoint for compat .db without bottlenecking? → Background checkpoint with ECS chunks.
Which B-tree ops for deterministic rebase? → Inserts/updates on leaf pages first.
Need B-link style concurrency for hot-page split/merge? → Benchmark; if needed, add structure modification protocol.

Comparison with Alternatives

	C SQLite	FrankenSQLite	libsql	DuckDB	Limbo
Language	C	Rust (safe)	C (SQLite fork)	C++	Rust
Concurrent writers	No (1 writer)	Yes (page-level MVCC)	Partial (WAL extensions)	Yes (different architecture)	No (1 writer)
Isolation level	Serializable (by serializing)	SSI (true serializable concurrency)	Snapshot	Snapshot	Snapshot
Memory safety	Manual	Compile-time guaranteed	Manual (C)	Manual (C++)	Compile-time guaranteed
File format	SQLite 3.x	SQLite 3.x with UTF-8 and UTF-16le/be encodings (Compat), or ECS (Native target)	SQLite 3.x (compatible)	Own format	SQLite 3.x (compatible)
Page encryption	Commercial (SEE)	XChaCha20-Poly1305 implemented in `fsqlite-pager` but not wired to the public API	No	No	No
Self-healing storage	No	Background WAL repair symbol generation on supported native runtimes; automatic recovery pending	No	No	No
Cross-process MVCC	No	Shared-memory coordination	No	Yes	No
Embeddable	Yes	Yes	Yes	Yes	Yes
Extensions	Loadable + built-in	Built-in	Built-in + WASM	Built-in	Limited
WASM target	Via Emscripten	Experimental (`fsqlite-wasm` cdylib + npm package; in-memory, no OPFS/IndexedDB persistence yet)	Yes	Yes	Yes
Async I/O	No	Yes (asupersync + Cx)	Yes	No	Yes (io_uring)

FrankenSQLite's target combines SQLite file format compatibility, concurrent writers via MVCC with SSI, page-level encryption, self-healing storage, and Rust memory safety. The current compatibility runtime covers SQLite databases in UTF-8 and UTF-16le/be encodings; parts of the durability design remain active work, and page encryption plus RaptorQ self-healing are not yet reachable from the public API. Limbo (another Rust SQLite) focuses on async I/O with io_uring but retains the single-writer model. libsql is a C fork that inherits the original codebase's complexity. DuckDB targets analytics workloads with a columnar storage format incompatible with SQLite.

Building from Source

Prerequisites

Rust nightly (rustup automatically installs the exact dated version pinned in rust-toolchain.toml)

Build

git clone --recursive https://github.com/Dicklesworthstone/frankensqlite.git
cd frankensqlite
cargo build

Run Tests

# Full test suite
cargo test

# With output
cargo test -- --nocapture

# Specific crate
cargo test -p fsqlite-types
cargo test -p fsqlite-error
cargo test -p fsqlite-btree
cargo test -p fsqlite-parser
cargo test -p fsqlite-mvcc

Quality Gates

# Type checking
cargo check --all-targets

# Linting (pedantic + nursery at deny level)
cargo clippy --all-targets -- -D warnings

# Formatting
cargo fmt --check

Benchmarks

# Run all benchmarks
cargo bench

# Specific benchmark suite
cargo bench --bench btree_perf
cargo bench --bench mvcc_scaling
cargo bench --bench parser_throughput

What We Deliberately Exclude (and Why)

FrankenSQLite deliberately omits several components of the C SQLite ecosystem. Each exclusion has a technical rationale; none are omitted from laziness.

Amalgamation build system. The C SQLite amalgamation (sqlite3.c) is a single-file build artifact produced by concatenating ~150 source files. Its purpose is simplifying C compilation. Rust's Cargo workspace with 28 members provides modularity, parallel compilation, and dependency tracking. There is no analog of the amalgamation in a Rust project.

TCL test harness. C SQLite's test suite is driven by ~90,000+ lines of TCL scripts deeply intertwined with the C API. These cannot be meaningfully ported. Instead, FrankenSQLite uses native Rust #[test] modules, proptest for property-based testing, a conformance harness comparing SQL output against C SQLite golden files, and asupersync's lab reactor for deterministic concurrency tests.

LEMON parser generator. C SQLite uses a custom LALR(1) parser generator called LEMON to produce parse.c from parse.y. FrankenSQLite instead uses hand-written statement and DDL routines plus explicit heap-backed state machines: Pratt tasks for expressions and frames for SELECT trees. This yields precise source-span diagnostics, direct expression-height enforcement, simpler maintenance, and no build-time code generation step. The parse.y grammar still serves as an authoritative reference.

Loadable extension API (.so/.dll). C SQLite supports dynamically loading extensions via sqlite3_load_extension(), requiring a C-compatible ABI and dlopen/LoadLibrary calls. FrankenSQLite instead compiles all extensions directly into the binary, controlled by Cargo features. This eliminates an entire class of security vulnerabilities (arbitrary code loading) and simplifies deployment. Users who need custom extensions implement Rust traits and recompile.

Legacy file format quirks (schema format < 4). Schema format number 4 has been the default since SQLite 3.3.0 (2006). Formats 1-3 have minor differences in how DESC indexes and boolean handling work. Supporting them would add complexity for a format that no actively maintained database uses. FrankenSQLite requires schema format 4 and rejects older formats with a clear error message.

Shared-cache mode. C SQLite's shared-cache mode allows multiple connections within the same process to share a single page cache and use table-level locking. It has been deprecated since SQLite 3.41.0 (2023) and is widely considered a source of subtle bugs. FrankenSQLite's MVCC system supersedes it entirely: multiple connections share the MVCC version chains and benefit from page-level concurrency, which is strictly superior.

Multiplexor VFS. C SQLite's multiplexor shards large databases across multiple files to work around filesystem limitations (e.g., FAT32 4GB limit). Modern filesystems do not have these limitations.

SEE (SQLite Encryption Extension). The commercial C SQLite encryption extension is not ported. FrankenSQLite's own page-level encryption design uses XChaCha20-Poly1305 with DEK/KEK envelope encryption, Argon2id key derivation, and O(1) instant rekey (only the wrapped key is rewritten, not bulk page data). That implementation lives in fsqlite-pager and is not reachable from the public API — see the Page-Level Encryption section above.

Limitations

Bounded external-snapshot database-image validation is shipped but not fully certified. The bounded structural-snapshot/publication API is part of the public Connection surface on non-WASM targets, including macOS (Darwin uses F_OFD_SETLK open-file-description locks). The closing whole-image receipt is captured while the validation transaction still owns its external fence, but native-Darwin keepers for unrelated-descriptor lifetime and stock-writer exclusion, and cancellation-safe teardown, remain outstanding (#307).
UTF-16 support is newer than the UTF-8 surface. FrankenSQLite admits header encodings 1 (UTF-8), 2 (UTF-16le), and 3 (UTF-16be) for both reads and writes, serializing TEXT in the database's declared encoding end to end (write support landed with the bd-bld9w write-encode sweep). Parity verification is deepest on UTF-8; attaching databases with mismatched encodings is rejected. This concerns SQLite TEXT encoding; arbitrary bytes stored as BLOB values are unaffected.
Legacy SQLite double-quoted-string (DQS) compatibility is a bounded rewrite, not a full fallback. DQS handling is enabled by default (PRAGMA fsqlite.dqs = ON|OFF controls it): the direct query/execute entry points (including their _with_params forms) proactively rewrite supported DQS shapes and retry unresolved double-quoted identifiers as string literals on single-statement SQL. Prepared statements (Connection::prepare) get no DQS rewriting, and multi-statement batches get only the proactive rewrite. Prefer single-quoted string literals; ordinary double-quoted identifiers are always supported.
Read-only opens are filesystem-inert; read-write opens still create sidecars. Read-only opens (OpenFlags::SQLITE_OPEN_READ_ONLY and schema-only opens) are regression-verified to create no -wal/-shm or namespace sidecars and to leave the directory byte- and timestamp-identical on Unix, including on first contact with a stock-created database (#140, #294, both fixed), and Windows no longer creates its -lock-* sidecars for read-only access. Default read-write opens still create the namespace sidecars and need a writable parent directory on first contact, and the close-time passive checkpoint writes only when it has real work. Opening from genuinely immutable/read-only media and rebinding a database copied to different media (namespace identity binds device and inode) are not yet regression-covered; treat them with care.
Windows WAL lock interoperability does not yet extend to shared-memory contents. FrankenSQLite mirrors ordinary WAL lock slots onto stock SQLite's real -shm lock bytes via LockFileEx/UnlockFileEx, but its shared-memory region contents remain process-local and heap-backed (#395 owns this data-plane boundary; #139 owns the native lock-byte receipt). Do not concurrently mix FrankenSQLite and stock SQLite WAL connections to the same database on Windows.
External-content FTS5 has a residual projection gap. The content-table-rename lifecycle defect (#211) is fixed — the connection stays usable and renaming back recovers — but external-content column projection can still return NULL even with the content table present (tracked as bd-c6jre).
Nightly Rust required. Uses edition 2024 features that aren't stabilized yet.
Rust is still the primary supported surface. An optional fsqlite-c-api crate exists for C/C++ embedding, but the main documented API and most verification effort are still centered on the Rust crates.
No loadable extensions. Extension support is configured at compile time via Cargo features; dynamic dlopen-based loading is not planned.
WASM support is experimental. The fsqlite-wasm crate now builds a wasm-bindgen browser package and npm artifact, but browser persistence backends such as OPFS and IndexedDB are still planned work. The current WASM lane is focused on a compact in-memory package, feature-gated diagnostics, and honest size-budget reporting.
MVCC adds memory overhead. Multiple page versions consume more RAM than single-version SQLite. Cache eviction and GC mitigate this but introduce background work.
No row-level locking. Two transactions modifying different rows on the same page can still conflict at the page level. The safe write-merge ladder is dormant in the live commit path, so current conflicts abort/retry. This is a deliberate tradeoff for file format compatibility.
Page encryption is not wired, and PRAGMA key/PRAGMA rekey are silently ignored. Both statements parse and return success with no rows and no error, but no key is installed and the database is written unencrypted. Do not use FrankenSQLite where encryption at rest is required, and do not treat a successful PRAGMA key as confirmation that a database is encrypted. When the design is wired, encryption will add per-page overhead: the 24-byte nonce and 16-byte tag (40 bytes total) consume reserved space in each page, and encrypted databases will not be readable without the key, even by C SQLite.
Native mode databases are not directly readable by C SQLite. The ECS commit stream format is FrankenSQLite-specific. Compatibility export (compat/foo.db) materializes a standard SQLite file on demand.

Limitations documented in earlier revisions of this README that are now fixed and regression-kept include: R-tree UPDATE/INSERT OR REPLACE (#208, #214), column-qualified FTS5 MATCH (#249), contentless delete-all (#253), FTS5 stock-SQLite integrity cleanliness (#300), TEMP-schema catalogs (#238), STRICT lossless coercions (#162, #163, #164, #272), generated-column UPDATE rejection (#165, #166), INSERT OR REPLACE delete-side FK actions (#142), PRAGMA defer_foreign_keys dispatch (#161), AUTOINCREMENT savepoint-rollback contiguity (#147), signed 32-bit header PRAGMAs (#263, #264), and WAL commit publication before sync (#187).

SQLite Behavioral Quirks

SQLite has accumulated 24 years of behavioral nuances that applications depend on. FrankenSQLite replicates all of these faithfully. Knowing them is essential for understanding compatibility edge cases.

Type affinity is advisory, not enforced. You can store a TEXT value in an INTEGER column. Affinity only affects coercion during comparison and storage, not rejection. Exception: STRICT tables (SQLite 3.37+) enforce column types at insert time.

NULL in UNIQUE constraints. SQLite allows multiple NULL values in a UNIQUE column because NULL != NULL. This differs from PostgreSQL and SQL Server.

ORDER BY on compound SELECT. ORDER BY at the end of a UNION/EXCEPT/INTERSECT uses column numbers or aliases from the first SELECT, not the last.

Integer overflow promotes to REAL. Arithmetic expressions like 9223372036854775807 + 1 silently promote to floating point rather than wrapping. But sum() raises an error on overflow.

AUTOINCREMENT vs rowid reuse. Without AUTOINCREMENT, deleted rowids can be reused — SQLite picks max(rowid)+1 for new rows. With AUTOINCREMENT, rowids never decrease (tracked via sqlite_sequence table), but there's a small write overhead per insert.

LIKE is ASCII-only. The built-in LIKE operator folds case for ASCII letters only. 'a' LIKE 'A' is true, but 'ä' LIKE 'Ä' is false without the ICU extension.

Empty string is not NULL. '' (empty string) is a zero-length TEXT value, not NULL. length('') returns 0. '' IS NULL is false. This catches people coming from Oracle, where empty strings are NULL.

Deterministic vs non-deterministic functions. random(), changes(), and last_insert_rowid() are re-evaluated for each row. The query planner cannot factor them out of loops or cache their results.

FAQ

Q: Can I open an existing SQLite database with FrankenSQLite? A: Yes, when the database uses the documented supported surface. Databases whose header declares encoding 1 (UTF-8) or encodings 2/3 (UTF-16le/UTF-16be) are admitted for reads and writes; UTF-16 support is the newer surface, and mixed-encoding ATTACH is rejected. Supported databases use the standard SQLite file and WAL layouts, subject to the extension-specific limitations above.

Q: How does MVCC interact with WAL mode? A: In the current compatibility runtime, WAL is the durability mechanism while MVCC conflict tracking lives above the pager in shared session state (ConcurrentRegistry, commit index, page locks, version store). The more ambitious WAL/native-mode extensions described elsewhere in this README are design/partial-implementation work rather than the entire hot path today.

Q: What happens when two writers conflict on the same page? A: If the page lock is held, the second writer gets SQLITE_BUSY immediately (no waiting, no deadlocks). If both reach commit on the same page, FCW detects base drift and the loser aborts/retries with SQLITE_BUSY_SNAPSHOT. The safe write-merge ladder exists as dormant implementation and is not wired into the live commit path.

Q: Why not use unsafe for performance-critical paths? A: The engine is intentionally written in safe Rust. The workspace-level lint is unsafe_code = "forbid". Two crates override this locally: fsqlite-vfs (mmap and shared-memory regions require raw pointers) and the optional fsqlite-c-api shim (FFI boundary code). If you use the Rust API or CLI, you can ignore fsqlite-c-api entirely. This keeps the highest-risk surface small while still leaving plenty of room for performance work through data structures, layout, and algorithmic tuning.

Q: Why reimplement rather than fork? A: SQLite's C codebase is well-engineered but carries 24 years of accumulated complexity (218K LOC in the amalgamation). An independent ground-up Rust reimplementation enables MVCC without fighting the existing architecture, provides compile-time memory safety, and produces a codebase that Rust developers can work with naturally.

Q: What's the conformance target? A: 100% behavioral parity target with C SQLite 3.52.0 for the supported surface, measured by running the SQLite test corpus against both implementations and comparing results. Any intentional divergence is documented and annotated with rationale. The canonical contract file is docs/contracts/sqlite_version_contract.toml, and the corresponding scope document is docs/canonical_parity_contract.md.

Q: How does MVCC garbage collection affect latency? A: The current runtime uses epoch-based reclamation rather than a periodic sweep. Commit-time version maintenance prunes unreachable versions, and retired arena slots are batch-freed only after all pinned readers have advanced past the retire epoch, keeping reclamation incremental without a background GC loop.

Q: What prevents a long-running reader from causing unbounded memory growth? A: A long-lived protected snapshot retains its floor version and newer history. Application-enforced transaction lifetime, bounded write admission and timely reclamation are needed to control growth. A query deadline alone does not end an idle transaction. Public active/idle lifetime enforcement remains tracked by bd-6hdwo.19/.20; no engine-wide memory bound is claimed from timeout settings.

Q: What is SSI and why does it matter? A: Serializable Snapshot Isolation detects write skew -- a class of anomaly where two transactions each read data the other writes, producing a result impossible under serial execution. Plain Snapshot Isolation misses this. FrankenSQLite applies the conservative Cahill/Fekete rule at page granularity: a transaction that would become a dangerous rw-antidependency pivot is aborted. PostgreSQL's SSI work is prior art, but its measured overhead is not evidence for FrankenSQLite; this implementation's cost is covered by the release matrix. You can downgrade to plain SI with PRAGMA fsqlite.serializable = OFF.

Q: What does RaptorQ actually buy me in practice? A: Native file-backed connections can now generate repair symbols in a separate .wal-fec sidecar after durable WAL commits, using a caller-owned blocking pool. This prepares recovery data; it does not yet repair corrupt databases automatically. The compatibility WAL reader still does not call the decoder (bd-1hi.11). Fountain-coded replication and version-chain compression remain Native-mode design goals, and the generation pipeline's end-to-end performance work remains open (bd-1hi.10).

Q: What is the difference between Compatibility and Native mode? A: Today, the stable user-facing runtime is the compatibility/pager-backed path over standard SQLite files (UTF-8 or UTF-16le/be encodings). Native mode refers to the ECS/content-addressed durability design and partial implementation work present in the repo. It is not yet a mature public PRAGMA fsqlite.mode toggle on Connection.

Q: How does encryption work? A: It does not work yet. PRAGMA key and PRAGMA rekey are not implemented by Connection; because unrecognised PRAGMAs are silently ignored, they return success while leaving the database unencrypted. The design — which lives in fsqlite-pager but is not wired to the public API — derives a KEK via Argon2id and unwraps a per-database random DEK; pages are encrypted with XChaCha20-Poly1305 using a fresh random 24-byte nonce per page write, with the nonce and 16-byte tag stored in each page's reserved bytes, and PRAGMA rekey re-wraps the DEK in O(1). In Native mode, encryption is designed to happen before RaptorQ encoding (encrypt-then-code).

Q: Does FrankenSQLite support Windows? A: Yes. The WindowsVfs implements the same Vfs trait as UnixVfs, using LockFileEx/UnlockFileEx for file locking, and it mirrors stock SQLite's WAL lock bytes onto the real -shm sidecar. Its shared-memory contents, however, are not a cross-process file mapping: shm_map extends the real -shm file but returns a process-local heap-backed region, so FrankenSQLite and stock SQLite WAL connections must not run concurrently against the same database on Windows (#395 tracks the data-plane boundary; #139 the native lock-byte receipt). Platform-specific code is isolated behind #[cfg(target_os)] gates. OS/2, VxWorks, and Windows CE are excluded.

Q: Can I use FrankenSQLite as a library without the CLI? A: Yes. The fsqlite crate is the public API. The CLI (fsqlite-cli) is a separate binary crate that depends on fsqlite. You can depend on fsqlite alone.

Troubleshooting

Problem	Cause	Fix
`error[E0554]: #![feature]`	Using stable Rust	Run the command from this checkout so rustup honors the dated `rust-toolchain.toml` pin; `rustup show active-toolchain` should report that pinned toolchain
`cargo clippy` warnings	Pedantic + nursery lints enabled	Fix the lint or add a targeted `#[allow]` with justification
`edition 2024` errors	Wrong or unavailable nightly	Install the exact dated toolchain recorded in `rust-toolchain.toml` (normally automatic); do not replace it with a floating nightly
Submodule missing after clone	Forgot `--recursive`	Run `git submodule update --init --recursive`
Tests fail on `fsqlite-types`	Possible float precision	Check platform; tests use exact float comparison for known values
SQLITE_BUSY in concurrent tests	Expected MVCC conflict	Wrap writes in a retry loop; see the concurrent writers example above
High memory usage with many readers	Long-lived snapshots pin old versions	Close transactions promptly; set connection timeouts
SSI abort (write skew detected)	Two concurrent transactions created rw-antidependency cycle	Retry the aborted transaction; or `PRAGMA fsqlite.serializable = OFF` if write skew is acceptable
Cannot open Native mode database in C SQLite	ECS format is FrankenSQLite-specific	Use `compat/foo.db` export, or switch to Compatibility mode
`PRAGMA key` succeeded but the database is readable without a key	Page encryption is not wired; unrecognised PRAGMAs are silently ignored	Expected behavior today — do not rely on FrankenSQLite for encryption at rest; see Page-Level Encryption above

Project Structure

frankensqlite/
├── Cargo.toml                # Workspace: 28 members, shared deps, lint config
├── Cargo.lock                # Pinned dependency versions
├── rust-toolchain.toml       # Pinned dated nightly + rustfmt + clippy
├── AGENTS.md                 # AI agent development guidelines
├── docs/
│   ├── UPGRADE_LOG.md        # Upgrade history (relocated from repo root)
│   ├── planning/             # Design corpus — all planning specs live here (not repo root)
│   │   ├── COMPREHENSIVE_SPEC_FOR_FRANKENSQLITE_V1.md  # Single source of truth (~18,200 lines / 827 KB)
│   │   ├── MVCC_SPECIFICATION.md          # Standalone MVCC formal specification
│   │   ├── PLAN_TO_PORT_SQLITE_TO_RUST.md # 9-phase implementation roadmap
│   │   ├── PROPOSED_ARCHITECTURE.md       # Crate architecture + MVCC design spec
│   │   ├── EXISTING_SQLITE_STRUCTURE.md   # SQLite behavioral specification
│   │   └── HEADS_UP_CONNECTION_RS_WIP.md  # Connection WIP heads-up (relocated from repo root)
│   ├── contracts/            # Normative surface + parity matrices
│   └── concurrency-contract.md  # Caller-facing concurrency contract
├── crates/
│   ├── fsqlite-types/        # Core types (2,800+ LOC, 64 tests)
│   ├── fsqlite-error/        # Error handling (578 LOC, 13 tests)
│   ├── fsqlite-vfs/          # Virtual filesystem
│   ├── fsqlite-pager/        # Page cache
│   ├── fsqlite-wal/          # Write-ahead log
│   ├── fsqlite-mvcc/         # MVCC engine
│   ├── fsqlite-btree/        # B-tree storage
│   ├── fsqlite-ast/          # SQL AST
│   ├── fsqlite-parser/       # SQL parser
│   ├── fsqlite-planner/      # Query planner
│   ├── fsqlite-vdbe/         # Bytecode VM
│   ├── fsqlite-func/         # Built-in functions
│   ├── fsqlite-ext-*/        # 7 extension crates
│   ├── fsqlite-core/         # Engine integration
│   ├── fsqlite/              # Public API
│   ├── fsqlite-cli/          # Small CLI shell + command runner
│   ├── fsqlite-harness/      # Verification/conformance harness
│   ├── fsqlite-e2e/          # Differential/E2E runner crate
│   ├── fsqlite-observability/ # Metrics and tracing helpers
│   ├── fsqlite-c-api/        # Optional C ABI adapter
│   ├── fsqlite-wasm/         # Experimental WebAssembly API
│   └── beads-doctor/         # Beads database health tool
├── legacy_sqlite_code/
│   └── sqlite/               # C SQLite reference (git submodule)
├── benches/                  # Criterion benchmarks
├── conformance/              # SQLite compatibility test fixtures
└── tests/                    # Release-certificate metadata; not Cargo integration targets

The root manifest is virtual. Cargo integration tests live under the owning crates' tests/ directories; root tests/regression_baseline.json is consumed by the release-certificate code and is not an executable test target.

About Contributions

Please don't take this the wrong way, but I do not accept outside contributions for any of my projects. I simply don't have the mental bandwidth to review anything, and it's my name on the thing, so I'm responsible for any problems it causes; thus, the risk-reward is highly asymmetric from my perspective. I'd also have to worry about other "stakeholders," which seems unwise for tools I mostly make for myself for free. Feel free to submit issues, and even PRs if you want to illustrate a proposed fix, but know I won't merge them directly. Instead, I'll have Claude or Codex review submissions via gh and independently decide whether and how to address them. Bug reports in particular are welcome. Sorry if this offends, but I want to avoid wasted time and hurt feelings. I understand this isn't in sync with the prevailing open-source ethos that seeks community contributions, but it's the only way I can move at this velocity and keep my sanity.

License

MIT License (with OpenAI/Anthropic Rider). See LICENSE.