Building a SQL Database Engine in C

This project is a lightweight SQLite-style database engine written from scratch in C.

Motivation

I can't say I am particularly interested in databases but I was confused about how they worked under the hood. I did a bit of Computer Architecture during my undergrad so I could've made a few guesses, but I figured if I was ever going to be a good computer scientist, a deep dive was needed.

Unfortunately, by the time this blog went live, I'd long finished this project, and I can't go into as much detail as I'd like.

Architecture

The database has a front-end and a back-end.

The Frontend

The front-end is responsible for converting the human-readable SQL code into something a machine can understand.

The front-end has three components:

1. The Tokenizer

This is also called the Lexer. It is the first point of contact for all SQL queries and its job is to break any long command into smaller, easier-to-digest chunks called tokens.

For example, 'SELECT name FROM users' might be broken down into: SELECT, var(name), FROM, var(users).

2. The Parser

This takes the tokens from the last step and organises them into an Abstract Syntax Tree (AST). This is somewhat unintuitive if you haven't already learned computer science, and I only vaguely understood it until I learned Model Driven Engineering (MDE).

An AST is a hierarchical data structure that represents the logical structure of a program's source code. As the name suggests, it is a tree. Usually, the root node represents the entire file and child nodes represent structures one level down.

For example (a pretty useless example), the expression

y = x + 2

might be represented as an AST where the root node is the assignment operator (=). This node has two children, the variable y and the binary operator (+). The binary operator likewise has two children, the variable x and the constant (literal) 5. While the example is trivial, it shows how the program would understand the expression and start processing it.

The previous example might also be represented as a tree: The root is a SelectStatement. This root node has two child nodes: A SelectClause (a list) and a FromClause (another list). The SelectClause has a child node, Identifier(name), and the FromClause also has a child node, TableFactor(users).

As a thought experiment, try and figure out (if you're familiar with SQL in any way) how a WHERE clause changes this tree.

In a more complicated program, these nodes could be functions or classes.

Naturally, ASTs are very useful. If you're a webdev, you most likely see it used mostly to transform code. Tools like Babel use ASTs to understand your (hopefully) ES6 JavaScript and Transpile it to older versions.

More useful for this application, however, is Static Analysis. An analyser can traverse the AST to find bugs or where the syntax of the language has been violated without having to run the code.

3. The Code Generator

This is the final step of the frontend and it converts the AST from the previous step into a format the database's virtual machine (or execution engine) can actually run.

This format is usually in the form of instructions or bytecode (called opcodes).

In some systems, this also includes an optimizer that finds out the most efficient way to execute a query long before the final code is generated.

The Backend

The backend has four components: the virtual machine, the B-tree, the pager, and the OS interface.

1. Virtual Machine

The virtual machine (VM) takes bytecode generated by the front-end and then performs those operations on one or more tables or indexes, each of which is stored in a data structure called a B-tree.

If you already know what opcodes are, then you know roughly how a virtual machine works. If you don't, then it is essentially just a big switch statement on the bytecode instructions. Every instruction has its associated logic and the virtual machine determines which instruction is being run and what data is needed for it, and then delegates to the function or section that handles that specific operation.

2. The B-Tree

A B-Tree needs its own article to fully understand, and I go into more detail here. The B-tree module organises the database into many B-trees. Each B-tree consists of many nodes, and each node is one page in length.

SQLite uses a B-tree for storage because it provides ordered storage with logarithmic (O(logN)) performance.

It is important to note that the B-tree layer never actually touches the storage. The B-tree can retrieve a page from the disk and save it back to the disk by issuing commands to the pager.

3. The Pager

The pager receives commands to read or write pages of data.

SQLite typically treats the database as a logical array of fixed-size pages (usually 1KB to 64KB), and this layer is responsible for reading/writing at appropriate offsets in the database file. It also keeps a cache of recently-accessed pages in memory, and determines when those pages need to be written back to the disk, ensuring ACID compliance.

4. The OS Interface

Also called thhe Virtual File System (VFS). As the name implies, this is the only layer that actually interacts with the operating system.

It provides a uniform interface for file I/O, hiding the differences between OS platforms like Windows, macOS and Linux (and any other supported OS). This tutorial doesn't support multiple operating systems (and since it is in C, I honestly wouldn't recommend Windows either.)

Key Lessons

• One of the key lessons for me was realising just how rusty I had gotten with programming C. I took a Security Engineering course a few months before this that focused mostly on C and Linux, but I realised it is far easier to break than it is to create (although vibe-coding now makes it pretty easy to do both, sometimes in a monkey-pawesque fashion).

• One of my weaknesses, not having a background in CS, is tree structures. I am someone who typically just finds ways to get really creative with lists and dictionaries, but reading through the analysis of their choice of data structures and how it works, really opened my mind to all the possibilities I was overlooking because of my stubbornness.

• This gave me a passing interest in how compilers and VMs function, and that interest really helped me when I was learning Model-Driven Engineering and Computer Architecture and Organisation. When you start breaking into a new field, the first few lessons (or books) are really daunting, but past a certain point, they just reinforce each other and the reading experience is a walk in the park. Whenever I want to learn a new skill, I just remember that. You'll never regret digging a well deep.

• Testing in this tutorial was done with RSpec, and it was my first introduction to Ruby. It is a fascinating language and I'd love to do some more work in it soon.

Other Observations

One thing I really disliked about the tutorial was how every piece of code was organised as snippets. C is a programming language that is (perhaps oddly) strict about order, and you cannot use a function above the line it is defined on, even though it has global scope. That is usually a good thing, but this tutorial doesn't make the best case. As a result, if you want to recreate this program, I'd strongly advise just going through my commits, as I made sure to commit at least once on each chapter, at the end.

Current State

The engine supports basic INSERT, SELECT, UPDATE and DELETE (naturally) with limited data types. Work is ongoing to add multi-table joins, support for a richer schema, multi-OS support and other QoL features like Common Table Expressions (CTEs).

I will look into the implementation of other popular SQL engines in the future. If I ever revisit this tutorial, I will document the process chapter-by-chapter for a better review.

Source: GitHub

Original Tutorial