sqly
Work in ProgressA tiny relational SQL database written from scratch to explore storage engine internals, fixed-size pages, and B+ tree indexing mechanics.
01The Motivation: Beyond Abstract SQL
In modern application development, databases are often treated as black boxes accessed through ORM abstractions. You execute a migration or write a query, and data magically persists. But what happens underneath the SQL driver?
How are dynamic-length string records packed into fixed-size storage blocks without leaving fragmented holes? How do cursors iterate across records? How does a B+ tree split when a leaf node overflows, and why does that give us O(log N) lookups instead of O(N) full-table scans?
I began building sqly as an educational deep dive to answer these questions from first principles, writing the storage primitives directly against POSIX file APIs.
02Architectural Concepts Under Exploration
The diagram below details the storage layout and query lifecycle being investigated in sqly.
+-------------------------------------------------------------------------+
| SQL PARSER & EXECUTION |
| "SELECT id, title FROM posts WHERE id = 42;" |
| │ |
| ▼ |
| [Lexer / Tokenizer] ──► [Pratt Parser] ──► [Query Execution Plan] |
+────────────────────────────────────────────────────────┬────────────────+
│
▼
+-------------------------------------------------------------------------+
| STORAGE ENGINE & PAGE BUFFER (4096 BYTES) |
| |
| Page Header (Fixed 64-byte metadata) |
| [page_id: 12] [page_type: LEAF] [free_space_offset: 0x07B0] |
| |
| Slotted-Page Record Layout: |
| ├── Slot Array (grows forward from header): |
| │ [slot 0: offset 4016] [slot 1: offset 3920] [slot 2: ...] |
| │ |
| │ ░░░░░░░░░░░░░░░░ Free Contiguous Space ░░░░░░░░░░░░░░░░ |
| │ |
| └── Record Payloads (grow backward from end of page): |
| [...record 2] [record 1: id=42, title="..."] [record 0] |
+────────────────────────────────────────────────────────┬────────────────+
│
▼
+-------------------------------------------------------------------------+
| B+ TREE INDEXING & PERSISTENCE |
| |
| [ Root Internal Node: Keys {20, 50} ] |
| / | \ |
| ▼ ▼ ▼ |
| [Leaf 0-19] ──► [Leaf 20-49] ──► [Leaf 50+] (doubly linked) |
| │ |
| Exact match found: Key 42 |
| Returns Record Pointer {Page 12, Slot 1} |
| │ |
| ▼ |
| [POSIX File Write & fsync] |
+-------------------------------------------------------------------------+* Note: This diagram illustrates the architectural principles and learning goals explored in sqly. It represents educational systems design, not a claim of production ACID compliance or concurrency.
03Deep Dive into Engineering Concepts
1. Parsing & Execution Boundaries
Incoming SQL statements are first processed by a lexical analyzer into tokens (SELECT, FROM, identifiers, literals). A recursive-descent parser constructs an Abstract Syntax Tree (AST), verifying schema types before handing an execution plan to the virtual machine.
2. Fixed-Size 4096-Byte Pages & Slotted Layout
Disks and operating system virtual memory operate in pages (traditionally 4KB). Sqly aligns all disk I/O to 4096-byte boundaries. Inside each page, a slotted layout is used:
- A 64-byte header at the start tracks metadata and available space.
- An array of slot pointers grows forward from the top of the page.
- Actual serialized variable-length row bytes are appended from the bottom upward.
- This prevents memory fragmentation when rows are modified or deleted.
3. B-Tree vs. B+ Tree Indexing
While standard B-trees store record keys and data pointers in internal nodes, a B+ tree restricts row pointers strictly to leaf nodes. Internal nodes hold only routing keys. This maximizes fan-out per 4KB node and enables efficient range scans by linking all leaf nodes in a doubly-linked chain.
4. Table Scans vs. Indexed Cursor Traversal
Without an index on a queried column, the engine initializes a cursor at Page 0, Slot 0 and performs a sequential scan across all pages. With a B+ tree index, the engine traverses tree depth in O(log N) page reads directly to the target leaf slot.
5. Persistence & `fsync` Boundaries
Writing to a file descriptor only places data in the OS page cache. Sqly investigates explicit fsync() flush calls to guarantee physical hardware writes to persistent storage.
04Project Scope & Honest Boundaries
Sqly is an active learning exploration. In accordance with strict honest engineering documentation:
- No ACID Claims: Sqly does not claim production ACID compliance, crash recovery, multi-version concurrency control (MVCC), or distributed transactions.
- Future Topics: Write-ahead logging (WAL), multi-threaded locking, and complex nested join optimizations are designated as future exploration milestones.
- Repository: The codebase is currently being structured; public GitHub links will be released once core page-splitting routines stabilize.