# mySqlite

**Repository Path**: pmpleader/my-sqlite

## Basic Information

- **Project Name**: mySqlite
- **Description**: 数据库是如何工作的呢？为了更好的理解其原理，我尝试用C语言写一个sqlite的简易版本。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2021-08-12
- **Last Updated**: 2021-08-12

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Let's build a Simple Database

>   数据库是如何工作的呢？为了理解其原理，我尝试用C语言写一个`sqlite`的简易版本。
>
>   *“What I cannot create, I do not understand.” –* [Richard Feynman](https://en.m.wikiquote.org/wiki/Richard_Feynman)

https://translate.google.com/translate?hl=zh-CN&sl=en&tl=zh-CN&u=https%3A%2F%2Fcstack.github.io%2Fdb_tutorial%2Fparts%2Fpart1.html&anno=2&prev=search

[TOC]

## 一、简介和启动交互式环境（REPL）

作为一名Web开发者，我每天会使用各种各样的关系型数据库，然而它们对我而言却是一个黑盒。

我产生了以下问题：

-   数据的存储格式是怎样的？（内存和磁盘里）
-   如何实现数据的持久化？
-   为什么每个表只能有一个主键？
-   事务回滚是如何实现的？
-   索引是如何设计的？
-   什么时候会进行全表扫描？如何扫描？
-   `prepared statement`的存储格式是怎样的？

总而言之，数据库是如何**工作**的？

>   需要指出的是，我正在从头写一个数据库，它是仿制的是sqlite数据库，因为它非常小，它整个数据库存储在一个单独的文件当中，而且具有的特性远少于MySQL和PostgreSQL，所以我有希望能够理解它的原理！

### 1.1 Sqlite

>   在Sqlite的官网有大量相关的[文档](https://www-sqlite-org.translate.goog/arch.html?_x_tr_sl=en&_x_tr_tl=zh-CN&_x_tr_hl=zh-CN&_x_tr_pto=ajax,se,op,sc)

`Sqlite`的系统结构如下：（https://www.sqlite.org/arch.html）：

![arch2](README.assets/arch2.gif)

在Sqlite中，一个查询（query）通过一系列组件进行，以便检索或修改数据。

其前端包括：

-   词法分析器（tokenizer）
-   语法分析器（parser）
-   代码生成器（code generator）

前端的输入是一个**SQL查询语句**，输出是sqlite虚拟机字节码（本质上是一段已经被编译好的能够操作数据库的程序）

后端包括：

-   virtual machine（虚拟机）
-   B-tree（二叉查找树）
-   pager（寻呼器）
-   os interface（操作系统接口）

**虚拟机**采用前端生成的字节码来作为操作指令，能够在单表或者多表，索引上执行操作。这些表或者索引都是存储在一种名为**B-tree**的数据结构中。**虚拟机**本质上讲，就是关于字节码操作指令的**大型switch语句**。

每个**`B-tree`**包含非常多的节点，每个节点的长度是一页。`B-tree`通过向`pager`发送指令可以从磁盘获取一页或者将其保存回磁盘。

`Pager`接收去读取或者写入数据页面的命令。它负责以正确的偏移量读取或者写入数据库文件。

**os接口**是根据sqlite编译的操作系统不同而不同的一层。在本教程中，我不打算支持多个平台。

**千里之行始于足下，让我们从一些简单的东西开始：REPL**

### 1.2 写一个简单的REPL

>   当你在命令行启动sqlite时，sqlite启动了一个REPL（read-execute-print-loop，交互式环境）

```sqlite
~ sqlite3
SQLite version 3.16.0 2016-11-04 19:09:39
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> create table users (id int, username varchar(255), email varchar(255));
sqlite> .tables
users sqlite> .exit
~
```

为了实现类似的交互环境，我们需要在主函数中编写一个死循环来**输出提示**，**读取一行输入**，**然后处理输入**。

```c
int main(int argc, char* argv[]) {
  InputBuffer* input_buffer = new_input_buffer();
  while (true) {
    print_prompt(); 
    read_input(input_buffer);

    if (strcmp(input_buffer->buffer, ".exit") == 0) {
      close_input_buffer(input_buffer);
      exit(EXIT_SUCCESS);
    } else {
      printf("Unrecognized command '%s'.\n", input_buffer->buffer);
    }
  }
}
```

我们将把`InputBuffer` 定义为一个封装状态的小包装器，用于存储与getline()交互所需的状态。(稍后详细介绍)

```c
typedef struct {
  char* buffer;
  size_t buffer_length;
  ssize_t input_length;
} InputBuffer;

InputBuffer* new_input_buffer() {
  InputBuffer* input_buffer = (InputBuffer*)malloc(sizeof(InputBuffer));
  input_buffer->buffer = NULL;
  input_buffer->buffer_length = 0;
  input_buffer->input_length = 0;

  return input_buffer;
}
```

接下来，`print_prompt()`输出提示语句给用户，一般是在用户输入之前来打印提示语句。

```c
void print_prompt(){
    printf("db > ");
}
```

为了读取一行输入，使用`getline()`函数，其函数头如下：

```c
ssize_t getline(char **lineptr, size_t *n, FILE *stream); 
// 值得注意的是,getline不在标准ｃ语言库中，所以有的编译器可能无法识别．本人c使用的是gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.12)
```

-   `lineptr`: 一个指向变量的指针，该变量用于指向包含输入的缓冲区。如果它设置为`NULL `它将被'`getline `分配，因此即使命令失败，用户也应该释放它。
-   `n`: 一个指针，指向用于保存已分配缓冲区大小的变量。
-   `stream`: 要从中读取的输入流。我们将从标准输入读取数据。
-   `return value`: 读取的字节数，可能会小于缓冲区的大小。

我们调用`getline()`函数来将输入存储在`input_buffer->buffer`中，已分配缓存区的大小存储在`input_buffer->buffer_length`中，返回值存储在`input_buffer->input_length`中。

`buffer`开始是null，因此，`getline()`会分配足够多的内存空间来存储输入行并且让`buffer`指向它。

```c
void read_input(InputBuffer* input_buffer) {
    ssize_t bytes_read = getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);
    
    if (bytes_read <= 0) {
        printf("Error reading input\n");
        exit(EXIT_FAILURE);
    }
    
    // 忽略最后的换行符
    input_buffer->input_length = bytes_read - 1;
    input_buffer->buffer[bytes_read - 1] = 0;
}
```

现在，应该定义一个函数来释放为`InputBuffer *`实例和其中的`buffer`元素分配的内存。

```c
void close_input_buffer(InputBuffer* input_buffer) {
    free(input_buffer->buffer);
    free(input_buffer);
}
```

最后，我们需要做的就是解析和执行命令了。当前编写的代码中仅仅只能识别一个命令:`.exit`，它将会结束整个程序。输入其他的只会打印错误信息然后继续该循环。

```c
if (strcmp(input_buffer->buffer, ".exit") == 0) {
  close_input_buffer(input_buffer);
  exit(EXIT_SUCCESS);
} else {
  printf("Unrecognized command '%s'.\n", input_buffer->buffer);
}
```

ok，来试试效果！

![image-20210630150332817](README.assets/image-20210630150332817.png)

哇哦，cool，我们已经成功实现了一个正常工作的REPL，在接下来的章节中，我们将开始开发我们自己的命令语言．以下是这个部分所有的代码：

```c
#include <stdbool.h> // 布尔宏，使得可以使用布尔类型
#include <stdio.h>
#include <stdlib.h>  // 包含了malloc等函数
#include <string.h>  // 包含了strcmp等函数
typedef struct {
  char* buffer;
  size_t buffer_length;
  ssize_t input_length;
} InputBuffer;

InputBuffer* new_input_buffer() {
  InputBuffer* input_buffer = malloc(sizeof(InputBuffer));
  input_buffer->buffer = NULL;
  input_buffer->buffer_length = 0;
  input_buffer->input_length = 0;

  return input_buffer;
}

void print_prompt() { printf("db > "); }

void read_input(InputBuffer* input_buffer) {
  ssize_t bytes_read =
      getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);

  if (bytes_read <= 0) {
    printf("Error reading input\n");
    exit(EXIT_FAILURE);
  }

  // Ignore trailing newline
  input_buffer->input_length = bytes_read - 1;
  input_buffer->buffer[bytes_read - 1] = 0;
}

void close_input_buffer(InputBuffer* input_buffer) {
    free(input_buffer->buffer);
    free(input_buffer);
}

int main(int argc, char* argv[]) {
  InputBuffer* input_buffer = new_input_buffer();
  while (true) {
    print_prompt();
    read_input(input_buffer);

    if (strcmp(input_buffer->buffer, ".exit") == 0) {
      close_input_buffer(input_buffer);
      exit(EXIT_SUCCESS);
    } else {
      printf("Unrecognized command '%s'.\n", input_buffer->buffer);
    }
  }
}
```



## 二、世界上最简单的SQL编译器和虚拟机

我们将编写一个sqlite的克隆版本。sqlite的`前端`是一个SQL编译器，它能够解析一个字符串并且输出为被称为字节码的内部表示。

然后字节码会被传递到虚拟机中进行执行。

![arch2](./README.assets/arch2.gif?lastModify=1625037376)

分成这两个步骤有如下好处：

- 减少了每一个部分的复杂度（例如：虚拟机无需担心语法错误）
- 对于相同的查询语句可以只编译一次，然后通过缓存字节码来提升性能。

在这种思想下，让我们来重构一下我们的`main`函数并且支持两种新的关键字：

```c
 int main(int argc, char* argv[]) {
 	InputBuffer* input_buffer = new_input_buffer();
 	while (true) {
 		print_prompt();
 		read_input(input_buffer);

        if (input_buffer->buffer[0] == '.') { 
            switch (do_meta_command(input_buffer)) { 
                case (META_COMMAND_SUCCESS): 
                    continue;
                case (META_COMMAND_UNRECOGNIZED_COMMAND):
                    printf("Unrecognized command '%s'\n", input_buffer->buffer); 						continue;
            }      
        }
        
		Statement statement;
        switch (prepare_statement(input_buffer, &statement)) {
                case (PREPARE_SUCCESS):
                	break;
            	case (PREPARE_UNRECOGNIZED_STATEMENT):
                	printf("Unrecognized keyword at start of '%s'.\n", input_buffer->buffer);
                	continue;
        }
        execute_statement(&statement);
        printf("Executed.\n");
    }
 }
```

非SQL语句像`.exit`类的被称为“元命令”，它们都以点开头，因此我们在其一个单独函数中识别并处理它们。

接下来，我们添加一个步骤来将输入行转换为语句的内部表示。这是我们sqlite前端的hacky版本。

最后，我们将预处理语句(`prepare_statement`)传递给`execute_statement`，这个函数将最终成为我们的虚拟机。

**注意：**我们添加的两个新的函数均返回的是成功或者失败的枚举型：

```c
typedef enum {
  META_COMMAND_SUCCESS,
  META_COMMAND_UNRECOGNIZED_COMMAND
} MetaCommandResult;

typedef enum {
    PREPARE_SUCCESS,
    PREPARE_UNRECOGNIZED_STATEMENT
} PrepareResult;
```

`Unrecognized statement`? 这看起来像是一个异常。但`exceptions are bad`(并且c语言也不支持异常处理)，因此我将在任何地方都使用枚举结果码(enum result code)。如果我的`switch`语句无法处理枚举成员，C的编译器将会发出警告，因此，我们可以更加自信的去处理函数返回的每个结果。预计以后会有更多的结果码(result code)加入。

`do_meta_command`仅仅是现有功能的一个封装，它为以后更多的命令提供了拓展的空间。

```c
MetaCommandResult do_meta_command(InputBuffer* input_buffer) {
  if (strcmp(input_buffer->buffer, ".exit") == 0) {
    exit(EXIT_SUCCESS);
  } else {
    return META_COMMAND_UNRECOGNIZED_COMMAND;
  }
}
```

我们的`prepared statement`现在仅仅包含了含有两个可能值的枚举。当我们允许参数出现在语句(`statements`) 中时，它将会包含更多的数据。

```c
typedef enum { 
    STATEMENT_INSERT,
    STATEMENT_SELECT
} StatementType;

typedef struct {
  StatementType type;
} Statement;
```

`prepare_statement`(我们的SQL编译器)现在还不能理解SQL语句。事实上，它目前只能够理解两个单词：

```c
PrepareResult prepare_statement(InputBuffer* input_buffer,
                                Statement* statement) {
  if (strncmp(input_buffer->buffer, "insert", 6) == 0) {
    statement->type = STATEMENT_INSERT;
    return PREPARE_SUCCESS;
  }
  if (strcmp(input_buffer->buffer, "select") == 0) {
    statement->type = STATEMENT_SELECT;
    return PREPARE_SUCCESS;
  }

  return PREPARE_UNRECOGNIZED_STATEMENT;
}
```

注意：这个我们使用的是`strncmp`，因为对于`insert`这个关键字来说，它的后面允许跟随其他数据。例如:`insert 1 cstack foo@bar.com`。

> `strcmp`这个函数是比较整个字符串的，而`strncmp`可以比较字符串的前n个字符。

最后，`execute_statement`包含了一些子句：

```c
void execute_statement(Statement* statement) {
  switch (statement->type) {
    case (STATEMENT_INSERT):
      printf("This is where we would do an insert.\n");
      break;
    case (STATEMENT_SELECT):
      printf("This is where we would do a select.\n");
      break;
  }
}
```

注意，它没有返回任何错误码，因为还没什么会出错的。



有了以上的重构后，我们现在能够识别两个新关键字了！（ohhhhh！！！）

![image-20210630171527609](README.assets/image-20210630171527609.png)

我们数据库的骨架已经开始成型了...如果它真的能够存储数据那这就太nice了！在这下来的部分中，我们将实现`insert`和`select`，来造一个世界上最垃圾的数据库（QWQ）。

以下是这一部分的全部代码：

```c
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// 输入缓冲区
typedef struct
{
  char *buffer;
  size_t buffer_length;
  ssize_t input_length;
} InputBuffer;

// 元命令处理结果
typedef enum
{
  META_COMMAND_SUCCESS,
  META_COMMAND_UNRECOGNIZED_COMMAND
} MetaCommandResult;


// 预处理SQL结果
typedef enum
{
  PREPARE_SUCCESS,
  PREPARE_UNRECOGNIZED_STATEMENT
} PrepareResult;

// SQL语句类型
typedef enum
{
  STATEMENT_INSERT,
  STATEMENT_SELECT
} StatementType;

// SQL语句
typedef struct
{
  StatementType type;
} Statement;

void print_prompt();
void read_input(InputBuffer *input_buffer);
void close_input_buffer(InputBuffer *input_buffer);
MetaCommandResult do_meta_command(InputBuffer *input_buffer);
PrepareResult prepare_statement(InputBuffer *inputBuffer, Statement* statement);
void execute_statement(Statement* statement);

InputBuffer *new_input_buffer()
{
  InputBuffer *input_buffer = (InputBuffer *)malloc(sizeof(InputBuffer));
  input_buffer->buffer = NULL;
  input_buffer->buffer_length = 0;
  input_buffer->input_length = 0;

  return input_buffer;
}

int main(int argc, char *argv[])
{
  InputBuffer *input_buffer = new_input_buffer();
  while (true)
  {
    print_prompt();
    read_input(input_buffer);

    // 如果是点开头的命令（元命令），注意不要使用双引号。。。
    if (input_buffer->buffer[0] == '.')
    {
      switch (do_meta_command(input_buffer))
      {
      case META_COMMAND_SUCCESS:
        continue;
      case META_COMMAND_UNRECOGNIZED_COMMAND:
        printf("Unrecognized command '%s'\n", input_buffer->buffer);
        continue;
      default:
        break;
      }
    }

    // 如果是SQL语句
    Statement statement;
    switch (prepare_statement(input_buffer, &statement))
    {
    case PREPARE_SUCCESS:
      break;
    case PREPARE_UNRECOGNIZED_STATEMENT:
      printf("Unrecognized keyword at start of '%s'.\n", input_buffer->buffer);
      continue;
    default:
      break;
    }

    // 虚拟机执行语句
    execute_statement(&statement);
    printf("Executed.\n");

  }
}

void print_prompt()
{
  printf("db > ");
}

void read_input(InputBuffer *input_buffer)
{
  ssize_t bytes_read = getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);

  if (bytes_read <= 0)
  {
    printf("Error reading input\n");
    exit(EXIT_FAILURE);
  }

  // 忽略最后的换行符
  input_buffer->input_length = bytes_read - 1;
  input_buffer->buffer[bytes_read - 1] = 0;
}

void close_input_buffer(InputBuffer *input_buffer)
{
  free(input_buffer->buffer);
  free(input_buffer);
}

// 处理元命令
MetaCommandResult do_meta_command(InputBuffer *input_buffer)
{
  if (strcmp(input_buffer->buffer, ".exit") == 0)
  {
    exit(EXIT_SUCCESS);
  }
  else
  {
    return META_COMMAND_UNRECOGNIZED_COMMAND;
  }
}

PrepareResult prepare_statement(InputBuffer *inputBuffer, Statement* statement)
{
  // 如果是insert语句
  if (strncmp(inputBuffer->buffer, "insert", 6) == 0)
  {
    // 将statemnt中的type改成insert
    statement->type = STATEMENT_INSERT;
    return PREPARE_SUCCESS;
  }

  // 同理
  if (strcmp(inputBuffer->buffer, "select") == 0) 
  {
    statement->type = STATEMENT_SELECT;
    return PREPARE_SUCCESS;
  }

  return PREPARE_UNRECOGNIZED_STATEMENT;
}

// 虚拟机
void execute_statement(Statement* statement)
{
  switch (statement->type)
  {
  case STATEMENT_INSERT:
    printf("VM will do insert!\n");
    break;
  case STATEMENT_SELECT:
    printf("VM will do select!\n");
    break; 
  }
}
```