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

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

Part 4 - Our First Tests (and Bugs)

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:
column type
id integer
username varchar(32)
email varchar(255)

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

insert statements are now going to look like this:

  1. insert 1 cstack foo@bar.com

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;

Now we need to copy that data into some data structure representing the table. SQLite uses a B-tree for fast lookups, inserts and deletes. We’ll start with something simpler. Like a B-tree, it will group rows into pages, but instead of arranging those pages as a tree it will arrange them as an array.

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.

  1. +void serialize_row(Row* source, void* destination) {
  2. +  memcpy(destination + ID_OFFSET, &(source->id), ID_SIZE);
  3. +  memcpy(destination + USERNAME_OFFSET, &(source->username), USERNAME_SIZE);
  4. +  memcpy(destination + EMAIL_OFFSET, &(source->email), EMAIL_SIZE);
  5. +}
  6. +
  7. +void deserialize_row(void* source, Row* destination) {
  8. +  memcpy(&(destination->id), source + ID_OFFSET, ID_SIZE);
  9. +  memcpy(&(destination->username), source + USERNAME_OFFSET, USERNAME_SIZE);
  10. +  memcpy(&(destination->email), source + EMAIL_OFFSET, EMAIL_SIZE);
  11. +}

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)

Rows should not cross page boundaries. Since pages probably won’t exist next to each other in memory, this assumption makes it easier to read/write rows.

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. + Table* new_table() {
  2. +  Table* table = malloc(sizeof(Table));
  3. +  table->num_rows = 0;
  4. +
  5. +  return table;
  6. +}
  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.          break;
  10. +      case (PREPARE_SYNTAX_ERROR):
  11. +        printf("Syntax error. Could not parse statement.\n");
  12. +        continue;
  13.        case (PREPARE_UNRECOGNIZED_STATEMENT):
  14.          printf("Unrecognized keyword at start of '%s'.\n",
  15.                 input_buffer->buffer);
  16.          continue;
  17.      }
  19. -    execute_statement(&statement);
  20. -    printf("Executed.\n");
  21. +    switch (execute_statement(&statement, table)) {
  22. +      case (EXECUTE_SUCCESS):
  23. +        printf("Executed.\n");
  24. +        break;
  25. +      case (EXECUTE_TABLE_FULL):
  26. +        printf("Error: Table full.\n");
  27. +        break;
  28. +    }
  29.    }
  30.  }

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->username), source + USERNAME_OFFSET, USERNAME_SIZE);
  72. +  memcpy(&(destination->email), source + EMAIL_OFFSET, EMAIL_SIZE);
  73. +}
  74. +
  75. +void* row_slot(Table* table, uint32_t row_num) {
  76. +  uint32_t page_num = row_num / ROWS_PER_PAGE;
  77. +  void* page = table->pages[page_num];
  78. +  if (!page) {
  79. +    // Allocate memory only when we try to access page
  80. +    page = table->pages[page_num] = malloc(PAGE_SIZE);
  81. +  }
  82. +  uint32_t row_offset = row_num % ROWS_PER_PAGE;
  83. +  uint32_t byte_offset = row_offset * ROW_SIZE;
  84. +  return page + byte_offset;
  85. +}
  86. +
  87. +Table* new_table() {
  88. +  Table* table = malloc(sizeof(Table));
  89. +  table->num_rows = 0;
  90. +
  91. +  return table;
  92. +}
  93. +
  94.  InputBuffer* new_input_buffer() {
  95.    InputBuffer* input_buffer = malloc(sizeof(InputBuffer));
  96.    input_buffer->buffer = NULL;
  97. @@ -64,6 +137,12 @@ PrepareResult prepare_statement(InputBuffer* input_buffer,
  98.                                  Statement* statement) {
  99.    if (strncmp(input_buffer->buffer, "insert", 6) == 0) {
  100.      statement->type = STATEMENT_INSERT;
  101. +    int args_assigned = sscanf(
  102. +        input_buffer->buffer, "insert %d %s %s", &(statement->row_to_insert.id),
  103. +        statement->row_to_insert.username, statement->row_to_insert.email);
  104. +    if (args_assigned < 3) {
  105. +      return PREPARE_SYNTAX_ERROR;
  106. +    }
  107.      return PREPARE_SUCCESS;
  108.    }
  109.    if (strcmp(input_buffer->buffer, "select") == 0) {
  110. @@ -74,18 +153,39 @@ PrepareResult prepare_statement(InputBuffer* input_buffer,
  111.    return PREPARE_UNRECOGNIZED_STATEMENT;
  112.  }
  114. -void execute_statement(Statement* statement) {
  115. +ExecuteResult execute_insert(Statement* statement, Table* table) {
  116. +  if (table->num_rows >= TABLE_MAX_ROWS) {
  117. +    return EXECUTE_TABLE_FULL;
  118. +  }
  119. +
  120. +  Row* row_to_insert = &(statement->row_to_insert);
  121. +
  122. +  serialize_row(row_to_insert, row_slot(table, table->num_rows));
  123. +  table->num_rows += 1;
  124. +
  125. +  return EXECUTE_SUCCESS;
  126. +}
  127. +
  128. +ExecuteResult execute_select(Statement* statement, Table* table) {
  129. +  Row row;
  130. +  for (uint32_t i = 0; i < table->num_rows; i++) {
  131. +    deserialize_row(row_slot(table, i), &row);
  132. +    print_row(&row);
  133. +  }
  134. +  return EXECUTE_SUCCESS;
  135. +}
  136. +
  137. +ExecuteResult execute_statement(Statement* statement, Table* table) {
  138.    switch (statement->type) {
  139.      case (STATEMENT_INSERT):
  140. -      printf("This is where we would do an insert.\n");
  141. -      break;
  142. +      return execute_insert(statement, table);
  143.      case (STATEMENT_SELECT):
  144. -      printf("This is where we would do a select.\n");
  145. -      break;
  146. +      return execute_select(statement, table);
  147.    }
  148.  }
  150.  int main(int argc, char* argv[]) {
  151. +  Table* table = new_table();
  152.    InputBuffer* input_buffer = new_input_buffer();
  153.    while (true) {
  154.      print_prompt();
  155. @@ -105,13 +205,22 @@ int main(int argc, char* argv[]) {
  156.      switch (prepare_statement(input_buffer, &statement)) {
  157.        case (PREPARE_SUCCESS):
  158.          break;
  159. +      case (PREPARE_SYNTAX_ERROR):
  160. +        printf("Syntax error. Could not parse statement.\n");
  161. +        continue;
  162.        case (PREPARE_UNRECOGNIZED_STATEMENT):
  163.          printf("Unrecognized keyword at start of '%s'.\n",
  164.                 input_buffer->buffer);
  165.          continue;
  166.      }
  168. -    execute_statement(&statement);
  169. -    printf("Executed.\n");
  170. +    switch (execute_statement(&statement, table)) {
  171. +      case (EXECUTE_SUCCESS):
  172. +        printf("Executed.\n");
  173. +        break;
  174. +      case (EXECUTE_TABLE_FULL):
  175. +        printf("Error: Table full.\n");
  176. +        break;
  177. +    }
  178.    }
  179.  }

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

Part 4 - Our First Tests (and Bugs)

原文: https://cstack.github.io/db_tutorial/parts/part3.html