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
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.