# Theoretical Storage Engine Specification ## 1. Scope This document specifies a theoretical storage architecture for the database language and runtime. The design targets: - low-latency OLTP - high point-read performance - efficient small-field updates - MVCC - strong transactional durability - reactive subscriptions - durable changefeeds - graph traversal - structured records - full-text, vector, spatial, and time-series indexing - future analytical acceleration - low conceptual burden at the language level This document defines architectural goals and recommended structures rather than a frozen on-disk compatibility format. ## 2. Core Physical Abstractions The storage engine is organized around three primary abstractions: ```text record identity commit sequence immutable version ``` A logical record is not defined by physical page location. The core model is: ```text record X has state Y as of commit Z ``` Pages, segments, indexes, and files are implementation machinery. ## 3. Stable Record Identity Every persistent record has stable logical identity. Examples: ```text player:42 item:105 guild:'dragons' ``` Physical movement shall not change identity. Secondary indexes should refer to stable record identity or an internal stable record slot rather than directly encoding mutable physical tuple location wherever practical. ## 4. Record Directory Each table should maintain a compact mapping from logical identity or dense record slot to the current physical version locator. Conceptually: ```text record slot segment offset version flags ``` For dense generated identities, the directory may support near-direct array lookup. For arbitrary UUID or textual identities, a key-to-slot index may precede the directory lookup. The directory should be engineered to remain compact and cache-resident for common working sets. ## 5. Version Model Committed record versions should be immutable. A record head points to the newest visible committed version. Conceptually: ```text record head -> version N -> version N-1 -> version N-2 ``` A version contains: ```text record slot commit sequence schema version previous version locator changed-field mask payload flags ``` ## 6. Delta MVCC Small updates should not require rewriting a complete logical record. A version may be either: ```text base delta ``` A base contains a complete materialized record. A delta contains: - changed-field mask - changed field values - previous-version locator Example: ```text base name level gold position settings delta gold delta position delta gold ``` The engine reconstructs a visible row from the nearest base plus applicable deltas. ## 7. Delta Chain Limits Unbounded version chains are prohibited as a design goal. The engine should materialize a new base when one or more thresholds are exceeded, such as: - delta count, - delta bytes, - changed-field density, - read amplification, - update frequency, - historical retention requirements. The exact threshold should remain adaptive and implementation-defined. ## 8. MVCC Visibility Transactions operate on logical snapshots. Committed transactions receive monotonic commit sequence numbers. A reader at snapshot sequence `S` observes the newest version whose commit sequence is visible at `S`. Uncommitted versions shall not become globally visible. Aborted versions may be reclaimed without publication. ## 9. Commit Sequence Numbers A global or logically monotonic commit sequence should unify: - MVCC visibility - subscription ordering - changefeeds - replication - historical reads - audit cursors Example: ```text csn 1949284 ``` The representation may be 64-bit or otherwise implementation-specific. ## 10. Transaction Pipeline The preferred write path is log-first. ```text incoming command ↓ admission / dependency preparation ↓ deterministic decision core ↓ logical mutation set ↓ transaction validation ↓ append commit record ↓ group durable flush ↓ commit sequence publication ↓ update in-memory authoritative state ↓ subscription / change consumers ↓ background segment materialization ``` The synchronous critical path should not require random writes into a conventional table heap. The writer's primary responsibilities are: 1. evaluate the transaction against authoritative logical state, 2. produce a deterministic mutation set, 3. durably append that mutation set, 4. publish its commit order, 5. update current in-memory state. Cold storage materialization may lag behind committed state so long as recovery and visibility guarantees remain correct. Exact internal ordering may vary where equivalent durability and visibility semantics are preserved. ## 11. Authoritative Commit Log The engine shall use an append-only durable commit log as the authoritative ordering and recovery record for committed mutations. The commit log is stronger than a conventional auxiliary WAL: current materialized database state derives from the ordered mutation history it records. Committed data shall be recoverable from the durable commit log even when compacted table segments have not yet incorporated the commit. The commit log should contain enough structured information to support: - crash recovery - replication - changefeeds - subscription delta derivation - audit - deterministic replay - segment materialization - diagnostic comparison between engine versions A logical mutation representation is preferred where practical. Example: ```text transaction 91822 update record player:42 field gold old 5000 new 4900 insert record inventory:912 event item_purchased {...} ``` Physical recovery metadata may coexist with this logical form. The user-facing schema shall not require application-level event sourcing. Developers continue to observe ordinary current-state tables and records. Append-only mutation history is an internal storage and execution property. ## 12. Group Commit Durable flushes should batch compatible transactions. Conceptually: ```text tx a ─┐ tx b ─┤ tx c ─┼→ wal flush → publish commits tx d ─┤ tx e ─┘ ``` The engine should avoid one storage flush per transaction where batching can preserve requested durability semantics. ## 13. Page Size The initial implementation should support an engine-wide page size selected from benchmarking rather than inherited convention. Recommended initial candidates: ```text 8 kib 16 kib 32 kib ``` A 16 KiB starting point is reasonable for modern NVMe and memory systems but shall not be treated as settled without workload data. ## 14. Slotted Pages Variable-size record material within mutable pages should use slotted-page organization. Conceptually: ```text page header slot directory free space record bodies optional metadata ``` Slots permit record bodies to move within a page without invalidating page-local references. ## 15. Segment-Oriented Table Storage Tables should be organized primarily as immutable compacted segments rather than one monolithic mutable heap. Conceptually: ```text player/ segment-001 segment-002 segment-003 ``` Recent authoritative state lives primarily in the commit log and in-memory record state until background workers materialize or compact it into immutable segments. Disk should be overwhelmingly immutable outside the active commit log and small engine metadata structures. Immutable segments enable: - compression - zone maps - bloom filters - columnar transformation - cheap snapshotting - efficient replication - background compaction ## 16. Schema-Aware Record Encoding Strict-schema records should not store repeated field names or generic type tags for every value. The schema compiler should produce physical layout metadata. A record may contain: ```text record header schema version unknown bitmap variable-field offsets fixed field region variable field region extension region ``` Fixed-width fields should be densely encoded. Variable-width fields should use compact offsets or references. ## 17. Nested Structure Encoding Declared nested objects should be flattened physically where useful. Logical: ```text position.x position.y position.z ``` may be stored as adjacent fixed fields rather than a generic nested object. Logical hierarchy shall not force pointer-rich physical representation. ## 18. Flexible Field Region Flexible structures should not impose generic document overhead on strict fields. Records containing flexible extensions should use a sparse extension region. A flexible field entry may contain: ```text field id type length value ``` Numeric schema-dictionary field IDs are preferred over repeated textual names. Only records that use flexible fields should pay the corresponding storage cost. ## 19. Unknown Bitmap Unknownability should be represented compactly. Strict records should use a bitmap or similarly dense structure for nullable/unknown-capable fields. Fields constrained `not unknown` need not consume unknown-state bits where schema layout permits their omission. ## 20. Boolean Packing Boolean and other very small fixed-domain fields should be bit-packed where beneficial. A nested settings object with several booleans should not require one byte or machine word per field unless that layout is measurably faster for the workload. ## 21. Large-Value Arena Large variable values should be stored out-of-line. Candidate values include: - large text - bytes - large arrays - large nested objects - vectors - large geometry A value reference may contain: ```text segment offset length codec flags ``` Small values remain inline. Medium values may be compressed inline. Large immutable values may be shared across record versions. ## 22. Compression Compression should be segment- and field-aware. Potential strategies include: - dictionary compression for repeated text - delta encoding for monotonic numeric values - bit packing - run-length encoding - general block compression - specialized vector compression Compression shall be selected by measured benefit, not exposed as ordinary application complexity. ## 23. Hot/Cold Field Separation The engine should support physical separation of frequently accessed and rarely accessed fields. Logical records remain unified. Example: ```text player hot id zone position level player cold bio settings appearance ``` The engine may infer this split from workload telemetry or accept optional administrative hints. The language shall not require ordinary applications to manually normalize around storage temperature. ## 24. Memory-First Current State The decision plane should treat current logical state as an in-memory materialization over the authoritative commit history. The engine shall distinguish at least conceptually between: ```text resident hot cold ``` `resident` state is required for immediate decision correctness or very high-frequency access. `hot` state is likely to be useful soon and should receive strong cache preference. `cold` state may be reconstructed or fetched from immutable storage on demand. This classification is an execution and caching concern, not a semantic distinction visible to queries. Point reads and small-record updates remain primary design targets. The database must remain correct when the complete logical database does not fit in memory. ## 25. Decision Plane and Data Plane The engine should separate two operational planes. The decision plane is: ```text deterministic synchronous hot small authoritative for transaction ordering ``` The data plane is: ```text parallel storage-heavy query-heavy cold-capable replicated where useful ``` The decision plane should perform domain state transitions and produce commit deltas. The data plane should perform work such as: - compaction, - historical lookup, - large scans, - blob access, - full-text search, - vector search, - analytics, - backup, - replica serving. Both planes expose one logical database and one transaction history. ## 26. Command Admission Commands intended for the deterministic decision core should pass through an admission stage. The admission stage may: - authenticate callers, - validate routine arguments, - derive likely read dependencies, - prefetch cold records, - prepare index ranges, - ensure required state is resident, - reject obviously invalid commands before writer admission. Conceptually: ```text client command ↓ admission ├── auth ├── validate ├── derive dependencies ├── prefetch └── ensure residency ↓ decision queue ↓ deterministic writer ``` Routine compilation and query planning should expose enough dependency information to make admission-time prefetching possible where practical. ## 27. Cold Faults The engine shall not require the complete decision working set to fit permanently in memory. If the decision core encounters required cold state unexpectedly, it should avoid blocking the global writer on slow storage I/O where practical. A preferred recovery path is: ```text routine encounters cold dependency ↓ yield or abort provisional execution ↓ prefetch dependency ↓ re-admit command ↓ retry against a current snapshot ``` Normal retryable routines are well suited to this model. Cold faults are performance events, not correctness failures. ## 28. Automatic Residency Persistent query interest, routine access frequency, index usage, and subscription dependencies should influence residency automatically. A subscription such as: ```text select id, position, animation from player where zone = :zone ``` creates strong evidence that the relevant records and projected fields should remain hot. An ordinary one-shot cold query should not permanently pin its result in memory. The engine should infer residency pressure instead of requiring applications to manage cache pinning manually. ## 29. Append-Over-Identity Updates Logical updates should append new immutable versions rather than rewrite historical record bytes in place. Conceptually: ```text message:42 -> log position 91821 message:42 -> log position 95011 message:42 -> log position 1000388 ``` The in-memory record directory advances to the newest committed version: ```text message:42 -> 1000388 ``` Older versions may remain available for retention, replication, or historical reads until compaction and reclamation make them obsolete. This model is especially well suited to workloads where recent records dominate decision activity while historical data is large. ## 30. Row-Oriented Materialization Compacted current-state segments should initially use row-oriented representation for OLTP workloads. The engine shall not require columnar decoding for ordinary record lookup. Current in-memory state and row-oriented compacted bases form the fast path for point access. ## 31. Adaptive Columnar Compaction Immutable or scan-heavy segments may be transformed into column-oriented representations. Conceptually: ```text mutable row segment ↓ compaction ↓ immutable row or columnar segment ``` Columnar conversion should be considered for: - telemetry - metrics - audit history - combat logs - append-heavy event data - old/cold transactional segments Logical query semantics remain unchanged. ## 32. Segment Metadata Each immutable segment should maintain inexpensive pruning metadata. Possible metadata includes: ```text row count min/max values unknown counts bloom filters field presence commit range schema version range compression metadata ``` The planner may reject irrelevant segments without reading record payloads. ## 33. Primary Lookup Dense generated record IDs should avoid unnecessary B-tree traversal. Preferred fast path: ```text table → record slot → record directory → segment/page → visible version ``` Arbitrary keys may require: ```text key index → record slot → record directory → version ``` ## 34. Secondary Indexes The baseline general-purpose secondary index should be B-tree. Secondary entries should map indexed keys to stable record slots or record identities. Specialized families may include: - hash - full-text inverted - spatial - HNSW/vector - coarse range/segment indexes ## 35. Covering Indexes Indexes may include non-key payload fields. Example logical index: ```text key: zone record: player:42 payload: name, position version metadata ``` Where visibility can be verified without base-record access, index-only execution should be supported. ## 36. Index Versioning Secondary indexes must remain transactionally consistent with visible record versions. The engine should avoid rewriting unrelated secondary entries when an update changes no indexed fields. Stable record identity should minimize physical-location churn in indexes. ## 37. Relation Storage Relations use ordinary record machinery. A relation contains at least: ```text id from to fields... ``` The engine automatically maintains adjacency indexes equivalent to: ```text (from, relation type) (to, relation type) ``` Traversal syntax lowers into adjacency lookups or equivalent relational plans. A separate graph consistency engine is not required. ## 38. Subscription Integration Transaction deltas should directly feed subscription maintenance. Each mutation should expose: ```text record identity changed-field mask old visibility new visibility commit sequence ``` Subscription plans should track dependencies on: - predicates - projections - joins - relation traversals - aggregates where supported Unrelated commits should be discarded without query rerun. ## 39. Changefeed Integration The durable commit stream should serve as the basis for `changes`. Changefeed consumers track a commit cursor. Retention is bounded by policy and consumer requirements. The engine should distinguish: ```text live subscription state durable mutation history application semantic events ``` These are related but not identical streams. ## 40. Event Integration Application events emitted during a transaction should be recorded in the same atomic commit envelope as data mutations. They become visible only when the containing transaction commits. This avoids manual outbox patterns. ## 41. Replication Replication should ship committed transaction envelopes or a compact equivalent. A replica should be able to apply transactions in commit order without requiring logical re-execution of arbitrary application code. Deterministic routine invocation logs may supplement but should not be the sole durability representation unless proven safe. ## 42. Historical Reads The version architecture should permit historical visibility. Potential query semantics include: ```text record state at commit sequence record state as of timestamp ``` Historical reads are optional at the language level but should not be precluded by storage design. ## 43. Reclamation Horizon Version reclamation should be based on the oldest state still required by: - active transactions - replication consumers - changefeed consumers - configured historical retention - backups/snapshots - subscription recovery guarantees Anything older and unreachable may be reclaimed. ## 44. Continuous Reclamation Space reclamation should be an engine responsibility. Routine user-issued vacuuming should not be required. Background compaction and reclamation should replace application-visible dead-tuple maintenance. Administrative controls may exist for diagnosis and tuning. ## 45. Compaction Compaction may: - collapse delta chains - materialize new bases - remove unreachable historical versions - rewrite fragmented pages - recompress immutable values - merge small segments - split oversized segments - transform eligible segments columnarly Compaction shall preserve record identity and transaction semantics. ## 46. Snapshot and Backup Immutable segments and WAL ranges should make snapshots inexpensive. A consistent backup may consist conceptually of: ```text catalog snapshot segment set blob set wal/commit boundary ``` Incremental backups should be possible by transferring new immutable segments and WAL ranges. ## 47. Recovery Crash recovery shall: 1. restore durable catalog/storage state, 2. replay committed WAL records not reflected in persisted segments/pages, 3. discard incomplete/uncommitted transactions, 4. rebuild ephemeral caches and indexes if required. Recovery shall never expose partial committed transactions. ## 48. Schema Versioning Each stored version should identify the schema layout under which its payload was encoded. The engine may decode older schema versions lazily. Schema migration may therefore be: - eager, - lazy, - mixed. Semantic compatibility is mandatory even when physical rewrite is deferred. ## 49. Physical Type Layout Fixed types should use compact native-width or packed encodings. Examples: ```text int32 -> 4 bytes int64 -> 8 bytes float32 -> 4 bytes float64 -> 8 bytes uuid -> 16 bytes record slot -> compact fixed-width internal id ``` Endianness and exact disk representation shall be explicitly versioned. ## 50. Query Execution Interface The storage engine should expose typed field access rather than forcing every value through a generic boxed tree. Preferred path: ```text encoded record → typed field view → predicate / projection → result vector → wire encoder ``` Avoid: ```text encoded record → generic object tree → generic value tree → query object → serialization object ``` unless flexible data requires it. ## 51. Zero-Copy and Borrowing Where lifetime rules permit, query execution should borrow directly from: - page buffers - decompressed blocks - blob slices - index payloads - result vectors Copying should occur only when required by ownership, persistence, reordering, or wire framing. ## 52. Vectorized Execution Scan-heavy execution should support vectorized predicate and projection evaluation. The storage format should permit batches of typed field values to be decoded without constructing per-row heap objects. This is especially important for: - aggregates - analytical scans - search scoring - subscription recomputation - columnar segments ## 53. Planner Statistics The engine should maintain statistics at multiple levels: ```text table segment index field relation adjacency ``` Candidate statistics include: - row count - distinct count - histograms - min/max - unknown fraction - average width - correlation - relation degree - segment selectivity metadata Statistics maintenance should be incremental where practical. ## 54. Workload Adaptation The engine may collect internal workload telemetry to guide: - hot/cold field splitting - index recommendations - segment organization - compaction thresholds - columnar conversion - cache placement Adaptive behavior shall not alter logical semantics. ## 55. Cache Architecture The buffer/cache layer should distinguish: - record-directory pages - B-tree/internal index pages - hot row pages - immutable segment blocks - blob blocks - decompressed column blocks Record directories and index upper levels should receive strong residency preference because of their high fan-out value. ## 56. Embedded Mode The storage engine should support in-process embedding without changing the persistent format or transaction semantics. Embedded and server modes should share: - storage engine - WAL - transaction manager - planner - indexes - recovery Networking is an outer execution surface, not a separate database implementation. ## 57. Conventional SQL Workloads A basic table-based application shall not pay mandatory storage overhead for: - graph traversal - subscriptions - vectors - flexible documents - local client mirrors Strict scalar tables should remain compact and efficient. Advanced storage machinery should be activated only when used. ## 58. Specialized Workloads The same storage engine should permit: ```text OLTP row records graph relations document-like structured records search indexes vector indexes spatial indexes time-series segments reactive subscriptions ``` These capabilities share the same transaction and commit model. ## 59. LSM Position The engine should not default to a full LSM-tree architecture for all data. Useful LSM ideas to borrow include: - immutable runs - append-oriented writes - compaction - background merging The design should avoid unnecessary universal: - read amplification - write amplification - space amplification - compaction pressure A hybrid segment architecture is preferred for initial investigation. ## 60. Column Store Position The engine should not make pure columnar storage the primary transactional representation. Row-oriented current state is preferred for OLTP. Columnar representation should be an adaptive optimization for immutable or scan-heavy data. ## 61. Initial v1 Architecture A practical first implementation should contain: ```text database │ ├── catalog ├── authoritative commit log ├── command admission layer ├── deterministic decision core ├── transaction manager ├── commit sequence manager ├── in-memory record directories ├── hot record/index state ├── immutable row-oriented table segments ├── blob arena ├── b-tree secondary indexes ├── relation adjacency indexes ├── cold/query workers ├── background compactor └── commit/change stream ``` Optional later components: ```text columnar segment encoder full-text index vector index spatial index subscription dependency engine replication transport historical query layer ``` ## 62. Recommended v1 Record Version Conceptually: ```text record_version { record_slot schema_version commit_sequence previous_version field_mask flags payload } ``` The exact packed representation should be benchmark-driven. ## 63. Recommended v1 Priorities Implementation effort should prioritize: 1. crash-safe authoritative commit log 2. transaction correctness 3. deterministic writer execution 4. stable record identity 5. compact in-memory record directory 6. hot-state point reads 7. admission and cold-prefetch path 8. B-tree indexes 9. schema-aware row encoding 10. delta MVCC 11. immutable segment materialization 12. background base compaction 13. change-stream integration Columnar conversion and specialized indexes should follow only after the core OLTP engine is proven. ## 64. Performance Principle Data representation and data flow take priority over local instruction-count optimization. The engine should minimize: - unnecessary copying - repeated serialization - generic boxing - pointer chasing - cache-hostile metadata - redundant version rewrites - index churn - synchronous storage waits ## 65. Architectural Principle The logical record model, transaction delta representation, commit-log representation, subscription delta representation, replication envelope, and wire representation should be designed together. They need not be byte-identical, but needless translation between generic intermediate structures should be avoided. One commit should ideally be able to feed: ```text recovery replication changefeeds subscriptions audit application events ``` without reconstructing the same semantic mutation repeatedly. ## 66. Guiding Rule The storage engine should optimize for the abstraction: ```text record X has state Y as of commit Z ``` rather than: ```text row X lives permanently at page P and slot S ``` Stable identity, immutable versions, compact schema-aware storage, and a unified commit stream form the architectural foundation.