【译】数据库基础：用 Go 从零开始写一个 SQL 数据库 —— 第二部分

2023-12-31 21:58:40

Database basics: writing a SQL database from scratch in Go —— part 2

【译】数据库基础：用 Go 从零开始写一个 SQL 数据库 —— 第二部分

目录

解析 insert 语句

我们看下下面的这些 token 模式：

  • 1.INSERT
  • 2.INTO
  • 3.$table-name
  • 4.VALUES
  • 5.(
  • 6.$expression [, ...]
  • 7.)

在现有的辅助函数基础上，实现很简单：

func parseInsertStatement(tokens []*token, initialCursor uint, delimiter token) (*InsertStatement, uint, bool) {
    cursor := initialCursor

    // 查看是否 INSERT
    if !expectToken(tokens, cursor, tokenFromKeyword(insertKeyword)) {
        return nil, initialCursor, false
    }
    cursor++

    // 查看是否 INTO
    if !expectToken(tokens, cursor, tokenFromKeyword(intoKeyword)) {
        helpMessage(tokens, cursor, "Expected into")
        return nil, initialCursor, false
    }
    cursor++

这就是解析一个 INSERT 语句！

解析 create 语句

最后，我们看看 create 的语句对应的 token：

  • 1.CREATE
  • 2.$table-name
  • 3.(
  • 4.[$column-name $column-type [, ...]]
  • 5.)

我们实现了新的 parseColumnDefinitions 辅助函数：

func parseCreateTableStatement(tokens []*token, initialCursor uint, delimiter token) (*CreateTableStatement, uint, bool) {
    cursor := initialCursor

    if !expectToken(tokens, cursor, tokenFromKeyword(createKeyword)) {
        return nil, initialCursor, false
    }
    cursor++

    if !expectToken(tokens, cursor, tokenFromKeyword(tableKeyword)) {
        return nil, initialCursor, false
    }
    cursor++

    name, newCursor, ok := parseToken(tokens, cursor, identifierKind)
    if !ok {
        helpMessage(tokens, cursor, "Expected table name")
        return nil, initialCursor, false
    }
    cursor = newCursor

    if !expectToken(tokens, cursor, tokenFromSymbol(leftparenSymbol)) {
        helpMessage(tokens, cursor, "Expected left parenthesis")
        return nil, initialCursor, false
    }
    cursor++

    cols, newCursor, ok := parseColumnDefinitions(tokens, cursor, tokenFromSymbol(rightparenSymbol))
    if !ok {
        return nil, initialCursor, false
    }
    cursor = newCursor

    if !expectToken(tokens, cursor, tokenFromSymbol(rightparenSymbol)) {
        helpMessage(tokens, cursor, "Expected right parenthesis")
        return nil, initialCursor, false
    }
    cursor++

    return &CreateTableStatement{
        name: *name,
        cols: cols,
    }, cursor, true
}

parseColumnDefinitions 辅助函数会查看字段类型后面的字段名，它们通过逗号分隔并且以分隔符结束：

func parseColumnDefinitions(tokens []*token, initialCursor uint, delimiter token) (*[]*columnDefinition, uint, bool) {
    cursor := initialCursor

    cds := []*columnDefinition{}
    for {
        if cursor >= uint(len(tokens)) {
            return nil, initialCursor, false
        }

        // 查找分隔符
        current := tokens[cursor]
        if delimiter.equals(current) {
            break
        }

        // 查找逗号
        if len(cds) > 0 {
            if !expectToken(tokens, cursor, tokenFromSymbol(commaSymbol)) {
                helpMessage(tokens, cursor, "Expected comma")
                return nil, initialCursor, false
            }

            cursor++
        }

        // 查找字段名
        id, newCursor, ok := parseToken(tokens, cursor, identifierKind)
        if !ok {
            helpMessage(tokens, cursor, "Expected column name")
            return nil, initialCursor, false
        }
        cursor = newCursor

        // 查找字段类型
        ty, newCursor, ok := parseToken(tokens, cursor, keywordKind)
        if !ok {
            helpMessage(tokens, cursor, "Expected column type")
            return nil, initialCursor, false
        }
        cursor = newCursor

        cds = append(cds, &columnDefinition{
            name:     *id,
            datatype: *ty,
        })
    }

    return &cds, cursor, true
}

以上就是解析过程！如果你从项目中把 parser_test.go 文件拷贝出来执行单元测试，应该会通过。

内存后端

我们的“内存后端”应该符合一个通用的后端接口，该接口允许用户创建、选择和插入数据

package main

import "errors"

type ColumnType uint

const (
    TextType ColumnType = iota
    IntType
)

type Cell interface {
    AsText() string
    AsInt() int32
}

type Results struct {
    Columns []struct {
        Type ColumnType
        Name string
    }
    Rows [][]Cell
}

var (
    ErrTableDoesNotExist  = errors.New("Table does not exist")
    ErrColumnDoesNotExist = errors.New("Column does not exist")
    ErrInvalidSelectItem  = errors.New("Select item is not valid")
    ErrInvalidDatatype    = errors.New("Invalid datatype")
    ErrMissingValues      = errors.New("Missing values")
)

type Backend interface {
    CreateTable(*CreateTableStatement) error
    Insert(*InsertStatement) error
    Select(*SelectStatement) (*Results, error)
}

这为我们在后面的基于硬盘的后端程序实现留出了空间

内存布局

我们的内存后端会存储一个 table 列表。每个表都有行和列。每一列都有一个名称和类型，每一行都有一个字节数组列表

package main

import (
    "bytes"
    "encoding/binary"
    "fmt"
    "strconv"
)

type MemoryCell []byte

func (mc MemoryCell) AsInt() int32 {
    var i int32
    err := binary.Read(bytes.NewBuffer(mc), binary.BigEndian, &i)
    if err != nil {
        panic(err)
    }

    return i
}

func (mc MemoryCell) AsText() string {
    return string(mc)
}

type table struct {
    columns     []string
    columnTypes []ColumnType
    rows        [][]MemoryCell
}

type MemoryBackend struct {
    tables map[string]*table
}

func NewMemoryBackend() *MemoryBackend {
    return &MemoryBackend{
        tables: map[string]*table{},
    }
}

实现表的创建

在创建表时，我们将在后端的映射表中创建一个新的记录。然后我们将创建 AST 对应的列。

func (mb *MemoryBackend) CreateTable(crt *CreateTableStatement) error {
    t := table{}
    mb.tables[crt.name.value] = &t
    if crt.cols == nil {

        return nil
    }

    for _, col := range *crt.cols {
        t.columns = append(t.columns, col.name.value)

        var dt ColumnType
        switch col.datatype.value {
        case "int":
            dt = IntType
        case "text":
            dt = TextType
        default:
            return ErrInvalidDatatype
        }

        t.columnTypes = append(t.columnTypes, dt)
    }

    return nil
}

实现表的 insert

为了简单起见，我们假设传递的值可以正确映射到指定列的类型

We‘ll reference a helper for mapper values to internal storage, tokenToCell.
我们引用一个 helper 将值映射到内部存储，helper 即 tokenToCell

func (mb *MemoryBackend) Insert(inst *InsertStatement) error {
    table, ok := mb.tables[inst.table.value]
    if !ok {
        return ErrTableDoesNotExist
    }

    if inst.values == nil {
        return nil
    }

    row := []MemoryCell{}

    if len(*inst.values) != len(table.columns) {
        return ErrMissingValues
    }

    for _, value := range *inst.values {
        if value.kind != literalKind {
            fmt.Println("Skipping non-literal.")
            continue
        }

        row = append(row, mb.tokenToCell(value.literal))
    }

    table.rows = append(table.rows, row)
    return nil
}

tokenToCell 会把数字转成二进制字节写入，并且将字符串转成字节写入：

func (mb *MemoryBackend) tokenToCell(t *token) MemoryCell {
    if t.kind == numericKind {
        buf := new(bytes.Buffer)
        i, err := strconv.Atoi(t.value)
        if err != nil {
            panic(err)
        }

        err = binary.Write(buf, binary.BigEndian, int32(i))
        if err != nil {
            panic(err)
        }
        return MemoryCell(buf.Bytes())
    }

    if t.kind == stringKind {
        return MemoryCell(t.value)
    }

    return nil
}

实现表的 select 查询

最后，对于 select，我们会遍历表中的每一行，并根据 AST 指定的列返回单元值。

func (mb *MemoryBackend) Select(slct *SelectStatement) (*Results, error) {
    table, ok := mb.tables[slct.from.table]
    if !ok {
        return nil, ErrTableDoesNotExist
    }

    results := [][]Cell{}
    columns := []struct {
        Type ColumnType
        Name string
    }{}

    for i, row := range table.rows {
        result := []Cell{}
        isFirstRow := i == 0

        for _, exp := range slct.item {
            if exp.kind != literalKind {
                // 暂不支持，请忽略
                fmt.Println("Skipping non-literal expression.")
                continue
            }

            lit := exp.literal
            if lit.kind == identifierKind {
                found := false
                for i, tableCol := range table.columns {
                    if tableCol == lit.value {
                        if isFirstRow {
                            columns = append(columns, struct {
                                Type ColumnType
                                Name string
                            }{
                                Type: table.columnTypes[i],
                                Name: lit.value,
                            })
                        }

                        result = append(result, row[i])
                        found = true
                        break
                    }
                }

                if !found {
                    return nil, ErrColumnDoesNotExist
                }

                continue
            }

            return nil, ErrColumnDoesNotExist
        }

        results = append(results, result)
    }

    return &Results{
        Columns: columns,
        Rows:    results,
    }, nil
}

REPL

最后，我们准备在 REPL 中封装解析器和内存后端。最复杂的部分是显示 select 查询结果。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"

    "github.com/eatonphil/gosql"
)

func main() {
    mb := gosql.NewMemoryBackend()

    reader := bufio.NewReader(os.Stdin)
    fmt.Println("Welcome to gosql.")
    for {
        fmt.Print("# ")
        text, err := reader.ReadString(‘\n‘)
        text = strings.Replace(text, "\n", "", -1)

        ast, err := gosql.Parse(text)
        if err != nil {
            panic(err)
        }

        for _, stmt := range ast.Statements {
            switch stmt.Kind {
            case gosql.CreateTableKind:
                err = mb.CreateTable(ast.Statements[0].CreateTableStatement)
                if err != nil {
                    panic(err)
                }
                fmt.Println("ok")
            case gosql.InsertKind:
                err = mb.Insert(stmt.InsertStatement)
                if err != nil {
                    panic(err)
                }

                fmt.Println("ok")
            case gosql.SelectKind:
                results, err := mb.Select(stmt.SelectStatement)
                if err != nil {
                    panic(err)
                }

                for _, col := range results.Columns {
                    fmt.Printf("| %s ", col.Name)
                }
                fmt.Println("|")

                for i := 0; i < 20; i++ {
                    fmt.Printf("=")
                }
                fmt.Println()

                for _, result := range results.Rows {
                    fmt.Printf("|")

                    for i, cell := range result {
                        typ := results.Columns[i].Type
                        s := ""
                        switch typ {
                        case gosql.IntType:
                            s = fmt.Sprintf("%d", cell.AsInt())
                        case gosql.TextType:
                            s = cell.AsText()
                        }

                        fmt.Printf(" %s | ", s)
                    }

                    fmt.Println()
                }

                fmt.Println("ok")
            }
        }
    }
}

将结果全部放在一起：

$ go run *.go
Welcome to gosql.
# CREATE TABLE users (id INT, name TEXT);
ok
# INSERT INTO users VALUES (1, ‘Phil‘);
ok
# SELECT id, name FROM users;
| id | name |
====================
| 1 |  Phil |
ok
# INSERT INTO users VALUES (2, ‘Kate‘);
ok
# SELECT name, id FROM users;
| name | id |
====================
| Phil |  1 |
| Kate |  2 |
ok

这样我们就完成了一个非常简单的 SQL 数据库！

接下来我们会讨论过滤、排序和索引。

延伸阅读

写一个简单的 JSON 解析器
这篇文章更详细的介绍了解析的理论和基础
数据库系统：设计、实现和管理的使用方法
一本很厚的书，但也是一个优秀的并且非常简单的数据库理论介绍。

评论

请在 Twitter 上回答问题或进行评论

【译】数据库基础：用 Go 从零开始写一个 SQL 数据库 —— 第二部分

上一篇：oracle 两表数据对比---minus


下一篇：MySQL-事务