SQL database engine from scratch

Francisco Javier Portasany Arias

javierportasanyarias@gmail.com

LinkedIn

Project's github

Databases are a fundamental cornerstone of the modern big data ecosystem. From transactional records to unstructured data supplying context to Large Language Models (LLMs), they manage vast quantities of information while executing a wide array of operations. This project originated as an endeavor to master C++, as my prior programming background was restricted to high-level languages like Python and MATLAB/Octave. However, it quickly evolved beyond lower-level language syntax, serving as a deep dive into complex software architecture and systems engineering. From manual memory management to natural language processing for SQL parsing and execution, this project provided a profound appreciation for the inner mechanics of database engines and offered valuable insight into how high-level query strings are compiled into executable instructions. This initiative also felt like a natural extension of my master's degree, where I extensively studied relational and non-relational database paradigms, including both their theoretical foundations and underlying algorithms. Equipped with this theoretical background and a strong drive to understand system design, I concluded that constructing a relational SQL database engine from scratch was the most effective way to consolidate this knowledge. This project implements an SQL database engine supporting fundamental CRUD operations (table creation, data insertion, table deletion, and basic querying). More advanced features, such as JOIN operations, were intentionally omitted due to scope and time constraints, as the primary objective was to design the core architecture of an SQL engine in C++ rather than a production-grade commercial product. In this post, we will dissect the overall system architecture and examine its core components.

Index of content

  1. Database architecture overview
  2. SQL token generation
  3. Task queue creation
  4. Task execution
  5. Variable types
  6. Disk I/O
  7. Row buffering
  8. Write Ahead Log
  9. Logging
  10. Memory management
  11. The role of AI within the project

1. Database architecture overview

This project implements the core of an SQL database engine featuring partitioned columnar storage, leveraging I/O buffering to minimize memory consumption. User input and SQL queries are parsed and executed through a two-stage process: first, raw SQL strings are tokenized into a linked list of instruction tokens. Once constructed, an Abstract Syntax Tree (AST) is generated for each SQL statement, and these trees are placed into a task queue. Execution occurs sequentially only after the queue is fully populated.

Table information is decoupled into metadata and data across both memory and disk. Data is stored strictly in columnar format in both domains. Non-volatile disk data is partitioned, utilizing dedicated I/O buffers to retrieve only one partition at a time when required. This mechanism drastically reduces memory overhead, particularly when processing large datasets. Furthermore, both data and metadata are logged to a unified recovery file—the Write Ahead Log (WAL)—ensuring data redundancy and consistency in the event of system failures or execution interruptions.

Database Engine flowchart
Fig. 1: Overview of the database main execution loop. Two distinct control flows are illustrated: nominal operation follows an indefinite loop of input ingestion, parsing, and execution; conversely, if the exit condition is triggered, all in-memory data and metadata are flushed to disk immediately prior to process shutdown.

2. SQL token generation

The file "textutils.cpp" handles raw string processing, transforming input text into a linear linked list where each node represents an SQL keyword or operational token. The raw string is first stripped of redundant whitespace and normalized before the linked list is instantiated. While individual words generally map to single nodes, specific multi-word SQL directives are reserved and combined into single consolidated nodes, namely: "CREATE TABLE", "PRIMARY KEY", "INSERT INTO", and "DROP TABLE".

3. Task queue creation

Once the token linked list is established, the task queue is constructed by "process_tokens.cpp". Each queue node encapsulates an Abstract Syntax Tree (AST) corresponding to a single SQL statement. The structural hierarchy of the tree varies depending on the statement type:

  • Table metadata definition nodes:

    • NodeType1: Contains table metadata (table name, alias, table structure) and a vector of one or more NodeType2 nodes representing field metadata.
    • NodeType2: Encapsulates individual column metadata (column name, data type, and primary key flag). It includes support for child nodes of the same type, though this capability is currently unused and scheduled for deprecation.

  • Table data insertion nodes:

    • NodeType3: Designed for data insertion tasks. It stores the target table name, a vector of column names, and a nested vector of column values. Each subvector within the value vector mirrors the ordering of the column name vector.

  • Table query nodes:

    • QueryNode: Serves as the root hub for query operations, linking a SelectNode and a FromNode.
    • FromNode: Stores the queried table name and its alias.
    • SelectNode: Contains a vector of one or more ItemNode elements.
    • ItemNode: Encapsulates a specific column name.

  • Table deletion nodes:

    • DropTableNode: Encapsulates the target table name scheduled for deletion.

Through these structures, the engine generates metadata definition trees (a NodeType1 root followed by one or more NodeType2 children) and query evaluation trees (rooted at QueryNode, branching into FromNode and SelectNode). While FromNode acts as a leaf, SelectNode can host multiple ItemNode children. Data insertion and table deletion operations do not require full tree structures and are represented as single nodes (NodeType3 and DropTableNode, respectively), which are directly integrated into the task queue. This extensible design facilitates the seamless addition of more advanced CRUD capabilities in future iterations.

Tree for query definition
Fig. 2.1: Tree for query definition.
Tree for metadata definition
Fig. 2.2: Tree for metadata definition.
Fig. 2: Data insertion and table deletion operations are encapsulated within single nodes (NodeType3 and DropTableNode, respectively) rather than multi-tier trees; hence, they are omitted from this diagram.

"process_tokens.cpp" also incorporates robust exception handling to detect common SQL syntax errors, such as keyword misspellings or references to non-existent tables. These exceptions are caught by the main event loop in "main.cpp", terminating process execution with "return 0" to ensure a clean shutdown and prevent memory leaks.

5. Variable types

The database engine supports a core set of primitive data types, categorized by memory layout into fixed-length and variable-length types:

  • Fixed-length data types:

    • Integer: Maps to C++ standard int types, occupying 4 or 8 bytes in length.
    • Float: Maps to C++ standard float types, occupying 4 or 8 bytes in length.
    • Bool: Maps to C++ standard bool types, occupying 1 byte in length (while representing a single bit of boolean information, system addressability requires 8 bits or 1 byte).

  • Variable-length data types:

    • Strings: Maps to C++ std::string, corresponding to SQL VARCHAR with unrestricted maximum length.
    • Unknowns: Implemented as a raw character array. Ideally suited for unformatted data or payload fields that do not fit standard primitives. Serves as a generic byte container, as all stored data ultimately reduces to a byte sequence.

4. Task execution

Task execution is sequentially orchestrated by "execution.cpp". Query execution handles two primary modes: full-column selection and arbitrary column projection. Low-level disk operations are delegated to external I/O modules, which persist and retrieve data in a strictly columnar format. Within this phase, interactions with the Write Ahead Log (WAL) are limited to synchronous row-level writes, contrasting with the engine's primary columnar storage layout. Upon successful execution of a task, its corresponding queue node is deallocated; once all tasks are processed, the entire queue structure is cleared from memory.

6. Disk I/O

Persisted data and metadata are stored in dedicated directories at the project root ("data" and "metadata", respectively). A single metadata file is maintained per table, designated as <table_name>_meta.bin.

Bytewise metadata file layout
Fig. 3: Bytewise layout of a metadata file. Each column/field metadata block encodes the column name size, column name, data type, and primary key flag. This flag is used to determine whether a column is a primary key or not. Note that while this primary key flag represents a boolean state, it is persisted as a 1-byte value because disk writes operate on byte boundaries—the smallest addressable and indivisible unit of disk storage—rather than individual bits.

In contrast, table data is organized hierarchically: each table owns a dedicated directory, within which each column or field has its own subfolder. Inside each field directory, data is stored in one or two files per partition depending on the data type:

  • Fixed-length data types: Primitives like integers, floats, and booleans have static byte widths. Consequently, the total record count can be inferred directly from file size and vice versa. Each partition requires only a single .dat file, simplifying read and write routines.
  • Variable-length data types: Strings and "Unknown" byte arrays exhibit arbitrary lengths. As a result, each partition requires two distinct files: a .bin file for raw binary data and an .idx file tracking cumulative byte offsets across the partition. Due to the variable nature of this layout, I/O operations are managed via a Finite State Machine (FSM) architecture.

Both binary data files (.dat/.bin) and index files (.idx) adhere to a standardized naming convention: partitions are indexed sequentially starting from zero as part_.bin/.dat/.idx.

Table data layout
Fig. 4: Structural layout of a table's data directory. Fixed-length columns maintain a single .dat file per partition, whereas variable-length columns utilize paired .bin and .idx files for each partition

Disk interaction is divided into metadata and data I/O modules:

  • Metadata I/O: Metadata operations form a distinct use case, as all table metadata is aggregated into a contiguous buffer before being written in a single operation. This logic is implemented in "disk_metadata.cpp".
  • Data I/O: Read and write operations are handled by modules within the "disk_in" and "disk_out" directories, respectively. The final flush of modified data and metadata to disk upon program termination is coordinated by "disk_io.cpp". Both reading and writing utilize fixed-size I/O buffers, significantly bounding memory consumption even when dealing with large partitions.

Auxiliary functions supporting both metadata and data I/O reside in the "disk_aux" folder.

7. Row buffering

To support operations requiring row-wise data access, an auxiliary abstraction layer was developed in "disk_buffer/disk_buffer.cpp" to bridge the columnar disk layout with row-oriented consumption. This module abstracts the underlying complexity of reading columnar disk structures and reassembling them into row-based tuples, seamlessly unifying in-memory and persisted data sources. Specialized buffer objects were implemented for specific workflows, including query execution and WAL logging. Thanks to this abstraction, higher-level execution routines simply request consecutive rows iteratively until all in-memory and persisted data streams are consumed.

8. Write Ahead Log

While the primary disk storage framework ensures persistence under normal operation, runtime exceptions or sudden system halts could cause uncommitted in-memory data and metadata to be lost without a crash recovery mechanism. To prevent data loss, modules within the "disk_wal" folder manage I/O operations targeting a unified recovery file: the Write Ahead Log (WAL). Log write operations are executed directly within "execution.cpp" where, unlike standard columnar disk flushes, rows and metadata are written synchronously upon definition to minimize the vulnerability window between instantiation and persistence. Replay of the WAL occurs automatically at process startup prior to standard disk loading.

The WAL file consists of interleaved data and metadata blocks ordered chronologically by in-memory definition. Each block is prepended by a 1-byte flag encoding the block type (0 for metadata and 1 for data). The structural composition of these blocks is detailed below:

WAL data block bytewise layout
Fig. 5: Structural representation of WAL data and metadata blocks. Data is persisted in a row-oriented format, whereas metadata is written and read as a single contiguous buffer in a single I/O operation, as its small footprint poses no risk of memory exhaustion.
WAL metadata data block bytewise layout
Fig. 6: WAL metadata blocks omit three fields present in standard metadata stores: table name and table name size (which are already captured in the block's pre-content header), and the disk row count (which is unnecessary for crash recovery operations).

Reading a single, heterogeneous file containing both metadata and row-formatted data introduced significant engineering constraints. First, all WAL read and write passes had to be governed by Finite State Machines (FSMs). Second, a padded buffer mechanism was incorporated into WAL I/O routines. The padding size utilized for a given block is encoded directly within its header, ensuring that memory alignment remains strictly consistent across both serialization and deserialization.

9. Logging

Terminal output is vital for both runtime debugging and user interaction. Initially, logging relied on ad-hoc std::cout statements; however, as the project expanded in scope and file count, this approach became unmaintainable. Furthermore, unbuffered or uncontrolled console flushing resulted in out-of-order terminal output, hindering effective debugging. To address these issues and achieve deterministic, configurable log output, a centralized logging system was implemented within the "log" directory. The log manager provides fine-grained control over line buffering and console flushing, while also handling main program SQL input ingestion.

10. Memory management

As the project reached structural completion and succeeded in compilation, a critical aspect required comprehensive audit: memory leaks and double-free errors. Although memory safety was prioritized throughout development, rigorous validation was necessary to guarantee stability. Using Valgrind, dynamic analysis was conducted across both nominal execution flows and invalid syntax error paths. This empirical testing confirmed robust memory management and zero leaks across a wide range of operational scenarios.

11. The role of AI within the project

Given the widespread adoption of Large Language Models (LLMs) in software development, I consider it important to transparently outline how and where AI tools were utilized in this project:

  • Systems Architecture Advisory (Gemini): Lacking a formal background in software engineering or systems architecture, I faced a learning curve regarding database internals and execution engines. I leveraged AI extensively as a technical tutor to master key paradigms, including Abstract Syntax Trees (ASTs), Write-Ahead Logging (WAL), columnar storage design, and buffered disk I/O.
  • Debugging & Root Cause Analysis (Gemini): Having worked predominantly in high-level, managed environments like Python, I had never previously encountered low-level memory issues such as double-deletion errors. Encountering these concepts for the very first time required extra guidance; thus, Gemini was employed as an advisory support tool to help analyze complex runtime bugs, accelerate diagnostic workflows, and guide me through unfamiliar debugging territory.
  • Code Documentation & Translation (Local Qwen 32B): During development, code comments and documentation were initially written in Spanish. To ensure maximum accessibility, these annotations were translated to English. Critical comments were translated manually, while routine inline documentation was processed using a local LLM due to time constraints.

In summary, AI served not as an automated code generator, but as an interactive technical mentor, facilitating the architectural understanding required to engineer this database engine from scratch.

Software and Tooling Credits:

  • C++ Development Tooling: clang-format (code formatting and style enforcement), cppcheck (static code analysis), Valgrind (dynamic memory analysis and profiling).
  • Visualization Frameworks: Mermaid.js and Graphviz (architectural flowcharts, byte structures, and AST diagrams).