So I wanted to learn how to use SQL databases and what better way to than to build one and learn how things works, well couldn't cover as much as planned still touched core components and basic queries. Here is how I started.
Resources that I referred to
- Architecture of a Database System (majorly)
- database-management-systems-raghu-ramakrishnan (for query planner & optimization)
Source
https://github.com/lightsigma96/db_scratch
This is a simple single-threaded database built for learning purposes.
It supports basic operations such as:
- Creating schemas
- Creating tables
- Inserting rows
Supported data types:
- INT
- STRING
- FLOAT
Build and Run (Local)
Build the project using CMake:
cmake -S . -B build
cmake --build build
Run the database:
./build/db_scratch
Using Docker
A Dockerfile is provided to build and run the project inside a container.
Build the image
docker build -t db_scratch .
Run the container (interactive)
docker run -it db_scratch
Inside the container:
./build/db_scratch
Notes
-
The Docker image includes build tools and is intended for both development and debugging.
-
If you modify the source code, rebuild the image:
docker build -t db_scratch .
CMake
Uses a basic CMake setup for building the project.
Storage Manager
This is the core of disk-based database, it's function is to interact with disk,
handle various db files and manage pages.
Buffer Pool
Buffer Pool caches pages from heap files in memory (which are responsible for storage of rows), pages are small fragments of heap file which are of fixed size (4kb in my case).
Reading or Writing from heap file on disk can be slow, hence pages from heap
file are loaded into memory (RAM) through buffer pool which is much faster.
Now obviously we cannot load entire file into memory, as that that can lead to out of memory error.
Hence we load file in pages into buffer pool which sits in memory.
Buffer Pool has a page replacement policy which evicts certain pages when buffer
pool is full.
In my case I implemented a simple FIFO replacement policy which tracks pages in
order of insertion into buffer pool, which checks if the page is pinned (pages which are frequently used or are being used by some component are pinned, pin count shows how many components are using that page), if yes then send them back in the queue, if no then flush them (write to disk) and evict them.
Buffer pools also contains a Disk Operator responsible for writing to file and
other things (implementations can vary).
Access Methods
Access Methods provides with necessary data structure and algorithms to organize
and access data.
On heap file rows are stored one after another and heap scan from access methods scan each one of them to find correct row based on given SARG.
SARGs (Search Arguments) describes condition for finding a row, they contain
column, operator and constant.
Heap scan may require scanning all rows across multiple pages resulting in O(n)
search complexity, hence a index scan can be implemented using B+ Trees.
B+ Tree consists of leaf nodes and internal nodes, Leaf nodes store key and RID (Row Identifier) which points to the exact row in heap file,
B+ Tree reduces index traversal cost from scanning many pages to traversing a small number of pages proportional to tree height, after which corresponding heap pages can be accessed using RID.
The downside of index scan is that index keys are built on specific columns.If query predicates do not use indexed columns then planner may fallback to heap scan.
Query Planner and Optimizer
After Buffer Pool and Access Methods, rows can be stored on disk and retrieved,
next comes the query planner & optimizer which makes plan for execution of query
and optimizes that plan.
Lexer & Parser
Queries are tokenized into keywords, identifiers, literals and special symbols
which are then passed to parser.
Parser is responsible for checking grammar and construct AST based on tokens
passed.
Parser's implementation can vary, in my case Lexer provides a tokenizer which is
used to iterate token forward/backward, and peek tokens.
Parser uses these token to check grammar of different queries.
Once this has been done Parser produces an AST specific to each query.
Planner and Optimizer
The AST produced by Parser is consumed by Planner which has a plan defined for
each query.
For example plan for select query involves three steps (from top to bottom):
Projection : Selects specific columns from tuples returned by child operators.
Filter : Based on SARG matching, this steps filters out rows returned by heap scan.
Scan : This calls heap scan and returns the output above in the chain.
(Rows flow upward from Scan → Filter → Projection)
Each operator pulls one tuple at a time from its child operator.
Optimization depends on type of query, for example if a index for columns exists then index scan can be used instead of heap scan.
Catalog Manager
Catalog Manager is logically separate from query execution components and is
responsible for schema metadata management.
This is used to enforce schema and handle writing and reading to/from a schema file.
To write schema to a file a serializer has to be made which writes schema in
format:
- Schema name size
- Schema name
- - heap page offset
- - heap page id
- - Table name size
- - Table name
- - - Column size
- - - Column name
The only caveat here is, before every name I had to store it's size as I have used C++ string over here which stores pointer to actual string allocated in memory, so if I directly write it on file, I would be writing garbage memory address.
Deserializer reads this back from file.
Main Server
This initializes all the necessary objects like buffer manager, access methods,
query planner, catalog manager.
I have two pipelines, DB Pipeline, TUI Pipeline, initially I wanted to have a
client-server architecture with a tcp server requesting DB but instead I thought
of going with direct function calls.
DB Pipeline
This function is responsible for orchestration of database pipeline (A TCP server can also be created which would be responsible for preprocessing cli input and calling db).
First the input query is tokenized and checked for correctness by lexer and parser.
If query is valid then AST is generated which is then goes through their respective processing (like for SELECT query it is passed through select plan and create table is passed through create table provided by catalog manager).
A response is finally returned by this function, implementation for this pipeline can be different.
With all the things above a database can support basic things like creating schema,table,columns executing basic queries like SELECT, INSERT, DELETE (same architecture can be extended to support JOINS and Stored Procedure).
Some other core components included:
- WAL (Write Ahead Log): Ensures durability and crash recovery by logging changes before modified pages are written to disk. Follows ACID properties.
- Lock Manager: Used to gain locks for multi-threading.