Part 3 - An In-Memory, Append-Only, Single-Table Database

    We’re going to start small by putting a lot of limitations on our database. For now, it will:

    • support two operations: inserting a row and printing all rows
    • reside only in memory (no persistence to disk)
    • support a single, hard-coded table
      Our hard-coded table is going to store users and look like this:

    This is a simple schema, but it gets us to support multiple data types and multiple sizes of text data types.

    statements are now going to look like this:

    That means we need to upgrade our prepare_statement function to parse arguments

    1.    if (strncmp(input_buffer->buffer, "insert", 6) == 0) {
    2.      statement->type = STATEMENT_INSERT;
    3. +    int args_assigned = sscanf(
    4. +        input_buffer->buffer, "insert %d %s %s", &(statement->row_to_insert.id),
    5. +        statement->row_to_insert.username, statement->row_to_insert.email);
    6. +    if (args_assigned < 3) {
    7. +      return PREPARE_SYNTAX_ERROR;
    8. +    }
    9.      return PREPARE_SUCCESS;
    10.    }
    11.    if (strcmp(input_buffer->buffer, "select") == 0) {

    We store those parsed arguments into a new Row data structure inside the statement object:

    1. +const uint32_t COLUMN_USERNAME_SIZE = 32;
    2. +const uint32_t COLUMN_EMAIL_SIZE = 255;
    3. +struct Row_t {
    4. +  uint32_t id;
    5. +  char username[COLUMN_USERNAME_SIZE];
    6. +  char email[COLUMN_EMAIL_SIZE];
    7. +};
    8. +typedef struct Row_t Row;
    9. +
    10.  struct Statement_t {
    11.    StatementType type;
    12. +  Row row_to_insert;  // only used by insert statement
    13.  };
    14.  typedef struct Statement_t Statement;

    Here’s my plan:

    • Store rows in blocks of memory called pages
    • Each page stores as many rows as it can fit
    • Rows are serialized into a compact representation with each page
    • Pages are only allocated as needed
    • Keep a fixed-size array of pointers to pages
      First we’ll define the compact representation of a row:
    1. +#define size_of_attribute(Struct, Attribute) sizeof(((Struct*)0)->Attribute)
    2. +
    3. +const uint32_t ID_SIZE = size_of_attribute(Row, id);
    4. +const uint32_t USERNAME_SIZE = size_of_attribute(Row, username);
    5. +const uint32_t EMAIL_SIZE = size_of_attribute(Row, email);
    6. +const uint32_t ID_OFFSET = 0;
    7. +const uint32_t USERNAME_OFFSET = ID_OFFSET + ID_SIZE;
    8. +const uint32_t EMAIL_OFFSET = USERNAME_OFFSET + USERNAME_SIZE;
    9. +const uint32_t ROW_SIZE = ID_SIZE + USERNAME_SIZE + EMAIL_SIZE;

    This means the layout of a serialized row will look like this:

    column size (bytes) offset
    id 4 0
    username 32 4
    email 255 36
    total 291

    We also need code to convert to and from the compact representation.

    Next, a Table structure that points to pages of rows and keeps track of how many rows there are:

    1. +const uint32_t PAGE_SIZE = 4096;
    2. +const uint32_t TABLE_MAX_PAGES = 100;
    3. +const uint32_t ROWS_PER_PAGE = PAGE_SIZE / ROW_SIZE;
    4. +const uint32_t TABLE_MAX_ROWS = ROWS_PER_PAGE * TABLE_MAX_PAGES;
    5. +
    6. +struct Table_t {
    7. +  void* pages[TABLE_MAX_PAGES];
    8. +  uint32_t num_rows;
    9. +};
    10. +typedef struct Table_t Table;

    I’m making our page size 4 kilobytes because it’s the same size as a page used in the virtual memory systems of most computer architectures. This means one page in our database corresponds to one page used by the operating system. The operating system will move pages in and out of memory as whole units instead of breaking them up.

    I’m setting an arbitrary limit of 100 pages that we will allocate. When we switch to a tree structure, our database’s maximum size will only be limited by the maximum size of a file. (Although we’ll still limit how many pages we keep in memory at once)

    Speaking of which, here is how we figure out where to read/write in memory for a particular row:

    1. +void* row_slot(Table* table, uint32_t row_num) {
    2. +  uint32_t page_num = row_num / ROWS_PER_PAGE;
    3. +  void* page = table->pages[page_num];
    4. +  if (!page) {
    5. +    // Allocate memory only when we try to access page
    6. +    page = table->pages[page_num] = malloc(PAGE_SIZE);
    7. +  }
    8. +  uint32_t row_offset = row_num % ROWS_PER_PAGE;
    9. +  uint32_t byte_offset = row_offset * ROW_SIZE;
    10. +  return page + byte_offset;
    11. +}

    Now we can make execute_statement read/write from our table structure:

    1. -void execute_statement(Statement* statement) {
    2. +ExecuteResult execute_insert(Statement* statement, Table* table) {
    3. +  if (table->num_rows >= TABLE_MAX_ROWS) {
    4. +    return EXECUTE_TABLE_FULL;
    5. +  }
    6. +
    7. +  Row* row_to_insert = &(statement->row_to_insert);
    8. +
    9. +  serialize_row(row_to_insert, row_slot(table, table->num_rows));
    10. +  table->num_rows += 1;
    11. +
    12. +  return EXECUTE_SUCCESS;
    13. +}
    14. +
    15. +ExecuteResult execute_select(Statement* statement, Table* table) {
    16. +  Row row;
    17. +  for (uint32_t i = 0; i < table->num_rows; i++) {
    18. +    deserialize_row(row_slot(table, i), &row);
    19. +    print_row(&row);
    20. +  }
    21. +  return EXECUTE_SUCCESS;
    22. +}
    23. +
    24. +ExecuteResult execute_statement(Statement* statement, Table* table) {
    25.    switch (statement->type) {
    26.      case (STATEMENT_INSERT):
    27. -      printf("This is where we would do an insert.\n");
    28. -      break;
    29. +      return execute_insert(statement, table);
    30.      case (STATEMENT_SELECT):
    31. -      printf("This is where we would do a select.\n");
    32. -      break;
    33. +      return execute_select(statement, table);
    34.    }
    35.  }

    Lastly, we need to initialize the table and handle a few more error cases:

    1.  int main(int argc, char* argv[]) {
    2. +  Table* table = new_table();
    3.    InputBuffer* input_buffer = new_input_buffer();
    4.    while (true) {
    5.      print_prompt();
    6. @@ -105,13 +203,22 @@ int main(int argc, char* argv[]) {
    7.      switch (prepare_statement(input_buffer, &statement)) {
    8.        case (PREPARE_SUCCESS):
    9. +      case (PREPARE_SYNTAX_ERROR):
    11. +        continue;
    12.        case (PREPARE_UNRECOGNIZED_STATEMENT):
    13.          printf("Unrecognized keyword at start of '%s'.\n",
    14.                 input_buffer->buffer);
    15.          continue;
    16.      }
    18. -    execute_statement(&statement);
    19. -    printf("Executed.\n");
    20. +    switch (execute_statement(&statement, table)) {
    21. +      case (EXECUTE_SUCCESS):
    22. +        printf("Executed.\n");
    23. +        break;
    24. +      case (EXECUTE_TABLE_FULL):
    25. +        printf("Error: Table full.\n");
    26. +        break;
    27. +    }
    28.    }
    29.  }

    With those changes we can actually save data in our database!

    1. ~ ./db
    2. db > insert 1 cstack foo@bar.com
    3. Executed.
    4. db > insert 2 bob bob@example.com
    5. Executed.
    6. db > select
    7. (1, cstack, foo@bar.com)
    8. (2, bob, bob@example.com)
    9. Executed.
    10. db > insert foo bar 1
    11. Syntax error. Could not parse statement.
    12. db > .exit
    13. ~

    Now would be a great time to write some tests, for a couple reasons:

    • We’re planning to dramatically change the data structure storing our table, and tests would catch regressions.
    • There are a couple edge cases we haven’t tested manually (e.g. filling up the table)
      We’ll address those issues in the next part. For now, here’s the complete diff from this part:
    1.  typedef struct InputBuffer_t InputBuffer;
    3. +enum ExecuteResult_t { EXECUTE_SUCCESS, EXECUTE_TABLE_FULL };
    4. +typedef enum ExecuteResult_t ExecuteResult;
    5. +
    6.  enum MetaCommandResult_t {
    7.    META_COMMAND_SUCCESS,
    8.    META_COMMAND_UNRECOGNIZED_COMMAND
    9.  };
    10.  typedef enum MetaCommandResult_t MetaCommandResult;
    12. -enum PrepareResult_t { PREPARE_SUCCESS, PREPARE_UNRECOGNIZED_STATEMENT };
    13. +enum PrepareResult_t {
    14. +  PREPARE_SUCCESS,
    15. +  PREPARE_SYNTAX_ERROR,
    16. +  PREPARE_UNRECOGNIZED_STATEMENT
    17. +};
    18.  typedef enum PrepareResult_t PrepareResult;
    20.  enum StatementType_t { STATEMENT_INSERT, STATEMENT_SELECT };
    21.  typedef enum StatementType_t StatementType;
    23. +const uint32_t COLUMN_USERNAME_SIZE = 32;
    24. +const uint32_t COLUMN_EMAIL_SIZE = 255;
    25. +struct Row_t {
    26. +  uint32_t id;
    27. +  char username[COLUMN_USERNAME_SIZE];
    28. +  char email[COLUMN_EMAIL_SIZE];
    29. +};
    30. +typedef struct Row_t Row;
    31. +
    32.  struct Statement_t {
    33.    StatementType type;
    34. +  Row row_to_insert;  // only used by insert statement
    35.  };
    36.  typedef struct Statement_t Statement;
    38. +#define size_of_attribute(Struct, Attribute) sizeof(((Struct*)0)->Attribute)
    39. +
    40. +const uint32_t ID_SIZE = size_of_attribute(Row, id);
    41. +const uint32_t USERNAME_SIZE = size_of_attribute(Row, username);
    42. +const uint32_t EMAIL_SIZE = size_of_attribute(Row, email);
    43. +const uint32_t ID_OFFSET = 0;
    44. +const uint32_t USERNAME_OFFSET = ID_OFFSET + ID_SIZE;
    45. +const uint32_t EMAIL_OFFSET = USERNAME_OFFSET + USERNAME_SIZE;
    46. +const uint32_t ROW_SIZE = ID_SIZE + USERNAME_SIZE + EMAIL_SIZE;
    47. +
    48. +const uint32_t PAGE_SIZE = 4096;
    49. +const uint32_t TABLE_MAX_PAGES = 100;
    50. +const uint32_t ROWS_PER_PAGE = PAGE_SIZE / ROW_SIZE;
    51. +const uint32_t TABLE_MAX_ROWS = ROWS_PER_PAGE * TABLE_MAX_PAGES;
    52. +
    53. +struct Table_t {
    54. +  void* pages[TABLE_MAX_PAGES];
    55. +  uint32_t num_rows;
    56. +};
    57. +typedef struct Table_t Table;
    58. +
    59. +void print_row(Row* row) {
    60. +  printf("(%d, %s, %s)\n", row->id, row->username, row->email);
    61. +}
    62. +
    63. +void serialize_row(Row* source, void* destination) {
    64. +  memcpy(destination + ID_OFFSET, &(source->id), ID_SIZE);
    65. +  memcpy(destination + USERNAME_OFFSET, &(source->username), USERNAME_SIZE);
    66. +  memcpy(destination + EMAIL_OFFSET, &(source->email), EMAIL_SIZE);
    67. +}
    68. +
    69. +void deserialize_row(void* source, Row* destination) {
    70. +  memcpy(&(destination->id), source + ID_OFFSET, ID_SIZE);
    71. +  memcpy(&(destination->email), source + EMAIL_OFFSET, EMAIL_SIZE);
    73. +
    74. +void* row_slot(Table* table, uint32_t row_num) {
    75. +  uint32_t page_num = row_num / ROWS_PER_PAGE;
    76. +  void* page = table->pages[page_num];
    77. +  if (!page) {
    78. +    // Allocate memory only when we try to access page
    79. +    page = table->pages[page_num] = malloc(PAGE_SIZE);
    80. +  }
    81. +  uint32_t row_offset = row_num % ROWS_PER_PAGE;
    82. +  uint32_t byte_offset = row_offset * ROW_SIZE;
    83. +  return page + byte_offset;
    84. +}
    85. +
    86. +Table* new_table() {
    87. +  Table* table = malloc(sizeof(Table));
    88. +  table->num_rows = 0;
    89. +
    90. +  return table;
    91. +}
    92. +
    93.  InputBuffer* new_input_buffer() {
    94.    InputBuffer* input_buffer = malloc(sizeof(InputBuffer));
    95.    input_buffer->buffer = NULL;
    96. @@ -64,6 +137,12 @@ PrepareResult prepare_statement(InputBuffer* input_buffer,
    97.                                  Statement* statement) {
    98.    if (strncmp(input_buffer->buffer, "insert", 6) == 0) {
    99.      statement->type = STATEMENT_INSERT;
    100. +    int args_assigned = sscanf(
    101. +        input_buffer->buffer, "insert %d %s %s", &(statement->row_to_insert.id),
    102. +        statement->row_to_insert.username, statement->row_to_insert.email);
    103. +    if (args_assigned < 3) {
    104. +      return PREPARE_SYNTAX_ERROR;
    105. +    }
    106.      return PREPARE_SUCCESS;
    107.    }
    108.    if (strcmp(input_buffer->buffer, "select") == 0) {
    109. @@ -74,18 +153,39 @@ PrepareResult prepare_statement(InputBuffer* input_buffer,
    110.    return PREPARE_UNRECOGNIZED_STATEMENT;
    111.  }
    113. -void execute_statement(Statement* statement) {
    114. +ExecuteResult execute_insert(Statement* statement, Table* table) {
    115. +  if (table->num_rows >= TABLE_MAX_ROWS) {
    116. +    return EXECUTE_TABLE_FULL;
    117. +  }
    118. +
    119. +  Row* row_to_insert = &(statement->row_to_insert);
    120. +
    121. +  serialize_row(row_to_insert, row_slot(table, table->num_rows));
    122. +  table->num_rows += 1;
    123. +
    124. +  return EXECUTE_SUCCESS;
    125. +}
    126. +
    127. +ExecuteResult execute_select(Statement* statement, Table* table) {
    128. +  Row row;
    129. +  for (uint32_t i = 0; i < table->num_rows; i++) {
    130. +    deserialize_row(row_slot(table, i), &row);
    131. +    print_row(&row);
    132. +  }
    133. +  return EXECUTE_SUCCESS;
    134. +}
    135. +
    136. +ExecuteResult execute_statement(Statement* statement, Table* table) {
    137.    switch (statement->type) {
    138.      case (STATEMENT_INSERT):
    139. -      printf("This is where we would do an insert.\n");
    140. -      break;
    141. +      return execute_insert(statement, table);
    142.      case (STATEMENT_SELECT):
    143. -      printf("This is where we would do a select.\n");
    144. -      break;
    145. +      return execute_select(statement, table);
    146.    }
    147.  }
    149.  int main(int argc, char* argv[]) {
    150. +  Table* table = new_table();
    151.    InputBuffer* input_buffer = new_input_buffer();
    152.    while (true) {
    153.      print_prompt();
    154. @@ -105,13 +205,22 @@ int main(int argc, char* argv[]) {
    155.      switch (prepare_statement(input_buffer, &statement)) {
    156.        case (PREPARE_SUCCESS):
    157.          break;
    158. +      case (PREPARE_SYNTAX_ERROR):
    159. +        printf("Syntax error. Could not parse statement.\n");
    160. +        continue;
    161.        case (PREPARE_UNRECOGNIZED_STATEMENT):
    162.          printf("Unrecognized keyword at start of '%s'.\n",
    163.                 input_buffer->buffer);
    164.          continue;
    165.      }
    167. -    execute_statement(&statement);
    168. -    printf("Executed.\n");
    169. +    switch (execute_statement(&statement, table)) {
    170. +      case (EXECUTE_SUCCESS):
    171. +        printf("Executed.\n");
    172. +        break;
    173. +      case (EXECUTE_TABLE_FULL):
    174. +        printf("Error: Table full.\n");
    175. +        break;
    176. +    }
    177.  }

    Part 2 - World's Simplest SQL Compiler and Virtual Machine