Part 1 - Introduction and Setting up the REPL

As a web developer, I use relational databases every day at my job, but they’re a black box to me. Some questions I have:

  • What format is data saved in? (in memory and on disk)
  • When does it move from memory to disk?
  • Why can there only be one primary key per table?
  • How does rolling back a transaction work?
  • How are indexes formatted?
  • When and how does a full table scan happen?
  • What format is a prepared statement saved in?
    In other words, how does a database work?

To figure things out, I’m writing a database from scratch. It’s modeled off sqlite because it is designed to be small with fewer features than MySQL or PostgreSQL, so I have a better hope of understanding it. The entire database is stored in a single file!

Sqlite

There’s lots of on their website, plus I’ve got a copy of SQLite Database System: Design and Implementation.

|

A query goes through a chain of components in order to retrieve or modify data. The front-end consists of the:

  • tokenizer
  • parser
  • code generator
    The input to the front-end is a SQL query. the output is sqlite virtual machine bytecode (essentially a compiled program that can operate on the database).

The back-end consists of the:

  • virtual machine
  • B-tree
  • pager
  • os interface
    The virtual machine takes bytecode generated by the front-end as instructions. It can then perform operations on one or more tables or indexes, each of which is stored in a data structure called a B-tree. The VM is essentially a big switch statement on the type the bytecode instruction.

Each B-tree consists of many nodes. Each node is one page in length. The B-tree can retrieve a page from disk or save it back to disk by issuing commands to the pager.

The pager receives commands to read or write pages of data. It 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 disk.

A journey of a thousand miles begins with a single step, so let’s start with something a little more straightforward: the REPL.

Sqlite starts a read-execute-print loop when you start it from the command line:

To do that, our main function will have an infinite loop that prints the prompt, gets a line of input, then processes that line of input:

  2.   InputBuffer* input_buffer = new_input_buffer();
  3.   while (true) {
  4.     print_prompt();
  5.     read_input(input_buffer);
  7.     if (strcmp(input_buffer->buffer, ".exit") == 0) {
  8.       exit(EXIT_SUCCESS);
  9.     } else {
  10.       printf("Unrecognized command '%s'.\n", input_buffer->buffer);
  11.     }
  12.   }
  13. }

We’ll define InputBuffer as a small wrapper around the state we need to store to interact with . (More on that in a minute)

  1. struct InputBuffer_t {
  2.   char* buffer;
  3.   size_t buffer_length;
  4.   ssize_t input_length;
  5. };
  6. typedef struct InputBuffer_t InputBuffer;
  8. InputBuffer* new_input_buffer() {
  9.   input_buffer->buffer = NULL;
  10.   input_buffer->buffer_length = 0;
  11.   input_buffer->input_length = 0;
  13.   return input_buffer;
  14. }

Next, print_prompt() prints a prompt to the user. We do this before reading each line of input.

To read a line of input, use getline():

  1. ssize_t getline(char **lineptr, size_t *n, FILE *stream);

lineptr : a pointer to the variable we use to point to the buffer containing the read line.

n : a pointer to the variable we use to save the size of allocated buffer.

return value : the number of bytes read, which may be less than the size of the buffer.

We tell getline to store the read line in input_buffer->buffer and the size of the allocated buffer in . We store the return value in input_buffer->input_length.

buffer starts as null, so getline allocates enough memory to hold the line of input and makes buffer point to it.

  1. void read_input(InputBuffer* input_buffer) {
  2.   ssize_t bytes_read =
  3.       getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);
  5.   if (bytes_read <= 0) {
  6.     printf("Error reading input\n");
  7.     exit(EXIT_FAILURE);
  8.   }
  10.   // Ignore trailing newline
  11.   input_buffer->input_length = bytes_read - 1;
  12.   input_buffer->buffer[bytes_read - 1] = 0;
  13. }

Finally, we parse and execute the command. There is only one recognized command right now : .exit, which terminates the program. Otherwise we print an error message and continue the loop.

Let’s try it out!

  1. ~ ./db
  2. db > .tables
  3. Unrecognized command '.tables'.
  4. db > .exit
  5. ~

Alright, we’ve got a working REPL. In the next part, we’ll start developing our command language. Meanwhile, here’s the entire program from this part:

  1. #include <stdbool.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  6. struct InputBuffer_t {
  7.   char* buffer;
  8.   size_t buffer_length;
  9.   ssize_t input_length;
  10. };
  11. typedef struct InputBuffer_t InputBuffer;
  14.   input_buffer->buffer = NULL;
  15.   input_buffer->buffer_length = 0;
  16.   input_buffer->input_length = 0;
  18.   return input_buffer;
  19. }
  21. void print_prompt() { printf("db > "); }
  23. void read_input(InputBuffer* input_buffer) {
  24.   ssize_t bytes_read =
  25.       getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);
  27.   if (bytes_read <= 0) {
  28.     printf("Error reading input\n");
  29.     exit(EXIT_FAILURE);
  30.   }
  32.   // Ignore trailing newline
  33.   input_buffer->input_length = bytes_read - 1;
  34.   input_buffer->buffer[bytes_read - 1] = 0;
  35. }
  37. int main(int argc, char* argv[]) {
  38.   InputBuffer* input_buffer = new_input_buffer();
  39.   while (true) {
  40.     print_prompt();
  41.     read_input(input_buffer);
  43.     if (strcmp(input_buffer->buffer, ".exit") == 0) {
  44.       exit(EXIT_SUCCESS);
  45.     } else {
  46.       printf("Unrecognized command '%s'.\n", input_buffer->buffer);
  47.     }
  48.   }
  49. }