Let's Write a Database

2 hours ago 2

So, confession, I love playing on the computer, but I’m terrible at SQL. I know that it’s Good or whatever and there’s this whole very sensible looking Relational Algebra behind it all, but like when I have to interact with it, I get the job done and then immediately wipe whatever I learned from my brain.

Enough is enough. It’s time to learn it properly. And what better way than to write an ANSI SQL database from scratch!

Disclaimers etc

Setting some expectations, this is very much a “fun” learning project, and we’re gonna get a lot of things wrong. We’ll be using Rust, because I write that a lot atm and so it’s what my brain thinks in, but I would definitely not read this hoping for a Rust tutorial because I am almost as bad at Rust as SQL. I am going to describe things in a very hand-wavy way that will probably annoy people that know what they’re talking about, but it’s my blog and I can do what I want.

So, let’s do it?

OK. So what we’re going to do in part 1 is:

Make (steal) a SQL parser
Do a table scan (From)
Filter results from that table (Filter)
Choose the fields we want to look at (Project)

We’re going to be concentrating on the Query Engine part of the database initially,mostly because I’m more interested in it, so our tables are going to be static JSON files taken from the chinook dataset. We are using this because it’s full of rock albums and it’s nice to be reminder that Led Zeppelin are a totally sick band from time to time.

Our types

We might not be implementing in Haskell but it’s spirit lives on - let’s start by defining the types of our query.

// the type that defines a query enum Query { From(From), Filter(Filter), Project(Project) } // select `FROM` a table struct From { table_name: TableName } // filter the results for a `WHERE` clause struct Filter { from: Box<Query>, filter: Expr, } // boolean expression type pub enum Expr { ColumnComparison { column: Column, op: Op, literal: serde_json::Value, } } // compare two items pub enum Op { Equals, } // choose which fields to return struct Project { from: Box<Query>, fields: Vec<ColumnName> } // name of a table struct TableName(pub String); // name of a column struct ColumnName(pub String);

A parser

This could quickly become a parsing tutorial and we don’t want that, so we’re going to use the sqlparser crate. It takes a string input and returns either it’s own AST or an error. We’ll pattern match on this and extract only the things we support into a Query type we defined above.

Nothing about this is very interesting, so I will just link to it. Know that we parse some SQL and make the types above.

Our run_query function

Now we’ve worked out what the user wants, we need to run the query. Initially we’ll do this by matching on the Query type.

pub fn run_query(query: &Query) -> Vec<serde_json::Value> { match query { Query::From(_) => todo!("Query::From"), Query::Filter(_) => todo!("Query::Filter"), Query::Project(_) => todo!("Query::Project") } }

We’ll fill these todo! out one by one now.

Query::From

The first thing we’ll implement is a simple table scan. A table scan is “get all of the rows in the table”. If you’re thinking “that doesn’t sound wildly performant”, rest assured your Software Craftsperson spidey-sense is still working correctly. However, our tables only have ~300 items in them, so for now we’ll live with it until we start thinking about indexes.

Here is some code. Forgive me, Padre.

fn table_scan(table_name: &TableName) -> Vec<serde_json::Value> { match table_name.0.as_str() { "Album" => { let my_str = include_str!("../static/Album.json"); serde_json::from_str::<Vec<serde_json::Value>>(my_str).unwrap() }, "Artist" => { let my_str = include_str!("../static/Artist.json"); serde_json::from_str::<Vec<serde_json::Value>>(my_str).unwrap() } _ => panic!("table not found {table_name:?}"), } }

Let’s smash that into our run_query function:

pub fn run_query(query: &Query) -> Vec<serde_json::Value> { match query { Query::From(From { table_name }) => table_scan(table_name), // ..

It is not good code, but it is code. We’d test it, but it would still fail because of the other todo!. Oh well. Onwards.

Query::Filter

Call me a staunch traditionalist, but often when I am accessing a database I do not wish to download all of it’s data at once. We’re going to allow users to filter data using a where clause, which lets us define properties about rows we are interested in.

Let’s recap on our Expr type:

pub enum Expr { ColumnComparison { column: Column, op: Op, literal: serde_json::Value, }, } pub enum Op { Equals, }

This is pretty limited, but it does let us express select * from Album where album_id = 1.

We start by defining a function for deciding whether we care about a row. It takes a row (which we store as a serde_json::Value) and an Expr, returning a bool telling us to keep the row or throw it in the bin.

fn apply_predicate(row: &serde_json::Value, where_expr: &Expr) -> bool { match where_expr { Expr::ColumnComparison { column, op, literal, } => { // unwrap row into a map let row_object = row.as_object().unwrap(); // grab the column we care about let value = row_object.get(&column.name).unwrap(); // compare it to `value` match op { Op::Equals => value == literal, } } } }

Let’s use it in our run_query function:

We’d test a query, but it’d still fail. But nearly!

Query::Project

So far we return every single field from our table scan, so every select is a select * from .... We can do better than that, let’s implement Project, which is how we extract fields from rows. Eventually, we’ll allowing renaming things with aliases, but that’s quite boring and fiddly, so for now we’re just supporting stuff like select Title, ArtistId from Album.

fn project_fields(row: serde_json::Value, fields: &[Column]) -> serde_json::Value { // make set of columns to keep let field_set: BTreeSet<_> = fields .iter() .map(|c| c.name.clone()) .collect(); if let serde_json::Value::Object(map) = row { // collect all the items we still want let new_map = map .into_iter() .filter(|(k, _)| field_set.contains(k)) .collect(); // wrap it back up again serde_json::Value::Object(new_map) } else { panic!("expected Object") } }

Then we add it to run_query, completing it for now.

pub fn run_query(query: &Query) -> Vec<serde_json::Value> { match query { Query::From(From { table_name }) => table_scan(table_name), Query::Filter(Filter { from, filter }) => run_query(from) .into_iter() .filter(|row| apply_predicate(row, filter)) .collect(), Query::Project(Project { from, fields }) => { // filter the columns in each row run_query(from) .into_iter() .map(|row| project_fields(row, fields)) .collect(), } } }

Bringing it together

We then add a basic CLI using clap, that takes a single argument --sql. Nothing surprising or interesting here, sorry.

use clap::Parser; use core::{parse, run_query}; #[derive(Parser, Debug)] #[command(version, about, long_about = None)] struct Args { /// SQL query to run #[arg(short, long)] sql: String, } fn main() { let args = Args::parse(); let query = parse(&args.sql).unwrap(); let results = run_query(&query); for result in results { println!("{result}"); } }

This means we can run a query with cargo run --bin cli -- --sql 'select Title from Album where AlbumId = 48' | jq and look what we get:

{ "AlbumId": 48, "Title": "The Essential Miles Davis (Disc 1)", "ArtistId": 68 }

Not bad, not bad at all.

What’s next?

If you’ve made it this far without being furious about my use of unwrap(), then in part two we’re going to add some JOINS.

Make sense? If not, get in touch!

Read Entire Article