跳转至

2023年秋39组项目总结报告

系统架构设计

我们的数据库按照课程建议主要分为七个模块，从上层到下层依次为：前端、解析器、系统管理、查询处理、索引管理、记录管理、文件管理。其中文件管理采用课程提供的页式文件系统，解析器使用课程提供的语法文件并复写antlr的visitor实现，其余模块均为小组成员实现。 - 前端用于与用户以及CI进行交互，读取指令并将指令字符串传递给解析器，并收集系统管理/查询处理模块传入的信息，并输出到标准输出。同时前端还用于输出调试信息并提升用户命令行使用体验。 - 解析器用于解析SQL指令。当接收到前端传来的指令后调用antlr生成AST抽象语法树，并遍历语法树上的每个结点，在遍历过程中调用系统管理/查询处理提供的接口以实现相关SQL操作。 - 系统管理分为system_manager和database_manager。其中system_manager用于对整个数据库进行管理，可以创建删除数据库，管理数据库；database_manager用于管理单个数据库，并对数据库中的数据表进行管理。系统管理进行文件夹的创建，并调用记录管理提供的接口管理数据表。 - 查询处理分为process和alter两个部分，其中process部分主要负责处理数据库增删查改请求，alter主要负责处理对键的schema管理。查询处理模块调用索引管理提供的接口，可对建立索引的数据表进行加速查询，同时查询处理模块调用记录管理提供的接口实现对于数据表的增删查改。 - 索引管理主要是对数据表的索引进行管理，采用B+树的数据结构管理索引，提供O(logn)的访存友好的查询接口等。索引管理通过记录管理和文件管理提供的接口进行索引的创建和管理。 - 记录管理是对数据表进行管理，将数据表保存到硬盘上并可从硬盘上读取记录。管理数据表的元数据，对数据表进行序列化和反序列化处理。记录管理通过调用页式文件系统的接口访问硬盘。 - 页式文件系统是系统最底层的模块，主要管理数据在硬盘的存储，将数据分页处理以提供更高效的 访存效率。

各模块详细设计与主要接口说明

前端

前端主要负责与用户和CI交互。采用iostream提供的流式输入输出实现，默认将输出输出到标准输出，将调试信息输出到标准错误，从标准输入中读取指令。为了方便其他模块调用，我们将前端实例化为一个全局变量。

前端将用户的输入进行字符串拼接，以结尾的分号作为指令结束的标志，并删除多余的换行，返回可以用于antlr解析的字符串。

为了方便调用，前端实现了多种输出格式的接口，满足不同格式数据的输出需求： - welcome/put_prompt/put_align：输出各种提示信息，用于交互模式下提升用户体验。 - put_output：输出结果，用于最基本的输出需求。 - put_info/put_error：输出调试/错误信息。 - put_table：用于制表，提高查询结果的可读性。 - put_summary：输出查询的额外信息如查询用时等。

解析器

解析器用于解析SQL指令，首先从前端获取指令并使用antlr解析为AST，然后重写antlr的visitor对AST进行遍历，在遍历的过程中完成操作。解析器工作流程与文档中给出的相同：

ANTLRInputStream sInputStream(sSQL);
SQLLexer iLexer(&sInputStream);
CommonTokenStream sTokenStream(&iLexer);
SQLParser iParser(&sTokenStream);
auto iTree = iParser.program();
CommandVisitor iVisitor;
iVisitor.visit(iTree);

CommandVisitor是我们的指令解析器，对于每条指令的遍历，首先遍历可能存在的子节点以获取identifier和clause、column等信息。然后根据指令的类型调用系统管理/查询处理模块提供的接口对指令进行实现，指令的结果直接在系统管理/查询处理模块中输出。

在实现过程中我们修改了文法文件以实现对日期数据类型的支持。

系统管理

系统管理对整个数据库系统进行管理。分为system_manager和database_manager两个部分。 - system_manager负责对数据库系统进行管理，包括创建数据库，删除数据库等操作，我们采用文件夹即数据库的模式，因此创建数据库与删除数据库实际上就是创建和删除文件夹，通过filesystem实现。 - database_manager主要负责对数据表进行管理，包括数据表的增删查改等，我们采用文件即数据表的方式，因此创建数据表与删除数据表实际上就是创建和删除文件，我们通过页式文件系统提供的接口进行文件创建，并使用filesystem进行文件删除。

其中system_manager是提供给外部的接口，其他模块通过访问system_manger的接口访问到database_manager提供的接口。主要接口包括： - create_database/del_database/use_database：创建/删除/切换数据库 - create_table/del_table：创建/删除数据表 - show_databases/show_tables：展示数据库/数据表 - fetch_table/release_table：获取数据表指针/释放数据表 - describe_table：描述数据表 - load_tables：加载数据表

查询处理

在解析完成后，具体的修改与查询处理会交给本模块。首先是不考虑索引加速的部分，只需要调用记录管理的接口来遍历整张表，根据传进来的 where 子句集合判断是否满足条件。此外需要检查完整性约束。

在添加 B+ 树索引之后，可以更高效地支持更多操作。

  • 首先是加速查找，找到存在 where 子句约束的索引，于是可以在该索引上按顺序查找，大大缩小了遍历的规模。
  • 其次是可以支持 ORDER BY 约束，找到排序列对应的索引 (若不存在则创建一个)，接着就可以在这一列上按顺序遍历了，也就是我们不需要同时将所有数据读取到内存中就能完成排序操作。
  • 以及支持外键链接起来的多表合并，可以写成 DFS 的形式，暴力遍历的时间复杂度是指数级的。但是如果当前表与前一个表有等值的约束，且在当前表对应的列上存在索引，就可以使用索引加速。DFS 到底层时意味着每张表行的选择被确定了，此时可以再检查所有 where 子句是否被满足(也能在 DFS 过程中判断，剪枝并避免访问某些不必要的状态)。

索引管理

我们实现了基于 B+ 树的索引，以用于加速查找与按顺序遍历。每个约束都对应一个 B+ 树索引，并独立存储在一个文件之中，文件的每一个页对应了一个节点。类似于记录管理，页 0 存储了 B+ 树的元数据(根节点的 page_id 和已使用的页数)。

分支节点使用结构体 ForkPage 表示，叶节点使用结构体 LeafPage 表示。分支节点需要维护最多 255 个孩子与中间值，叶节点维护最多 255 条键值到 RID 的映射。按照常规搜索树的方式插入节点，当叶子的维护的记录达到 256 条时，则开始上溢：当前节点被拆分为两个等长的节点，则父节点的分叉树会增加 1 ，如果又满了则继续上溢。删除也是类似的，当能与相邻节点合并时则合并，可能导致向上继续合并。为了应对 B+ 树反复增删的情况，需要对已经清空的页使用双向链表串联起来，实现垃圾回收功能。限于实现的复杂性，本项目仅实现了插入时对于上溢的处理。

此外 B+ 树的叶子节点需要按照顺序使用双向链表串联起来，这样就能实现快速的按顺序遍历。

运行过程中，B+ 树对外被抽象成了一个类 BPTree ，对外提供接口来支持快速增删与查找：

class BPTree {
    BPTreeMeta *meta;
    // ...
    public:
    void create(BufPageManager *_bpm, int _file_id);
    void load(BufPageManager *_bpm, int _file_id);
    void save();
    void insert(const KEY &key, const RID &rid);
    void remove(const KEY &key, const RID &rid);
    // 返回第一个满足 KEY >= key 的位置 kid
    KID find_first(const KEY &key);
    KID find_next(KID kid);
    // 根据 KID 获取记录
    pair<KEY,RID> get_KEY_RID(KID kid);
};

记录管理

我们的记录管理的实现大致按照试验文档里的方式。每个数据表被存储在一个文件中，并使用页式文件系统管理。

表的元数据使用结构体 TableMeta 表示，其大小为固定值且略小于 8KB ，被存储在页 0 之上。除了基本信息之外， TableMeta 还存储了 ConstraintMeta 类型 (里面还包括指向 B+ 树的指针) 数组来维护所有约束。

struct TableMeta {
    int full_L, full_R;
    int free_L, free_R;
    char table_name[NAME_LEN];
    int column_count;
    ColumnMeta columns[COL_MX];
    u8 column_default[RECORD_LEN];
    int row_length;
    int page_row_count;
    int page_count;
    int constraint_count;
    ConstraintMeta constraints[CONSTRAINT_MX];
};

其余页则使用结构体 Page 表示，在抽象层面空闲页和满页分别构成了双向链表。页头也维护了位图，用于快速找到未使用的槽位，与快速找到下一个被使用的槽位。这样就能快速完成记录的插入，删除，遍历

struct Page {
    int full_L, full_R;
    int free_L, free_R;
    int slot_mx;
    u64 used[SLOT_MX / 64];
    u8 bytes[PAGE_LEN];
}

数据在文件中是以字节流形式存储的，所以也需要提供序列化与反序列化的函数来方便两种表示的相互转化 (下面代码中的 ITEM 是抽象的表中元素)

vector<u8> serialize(const TableMeta *meta, const vector<ITEM> &record);
vector<ITEM> deserialize(const TableMeta *meta, const u8 *data);

运行过程中，数据表对外被抽象为了一个类 Table ，包含指向元数据的指针，并由该类对外提供接口来维护数据表，主要如下：

class Table {
    TableMeta *meta;
    // ...
    public:
    void create(FileManager *fm, BufPageManager *bpm, int file_id, ...);
    void load(FileManager *fm, BufPageManager *bpm, int file_id);
    void save(); // 保存表，包括表元数据 Writeback 与索引文件保存
    RID insert(const vector<ITEM> &record);
    void remove(const RID &rid);
    void update(const RID &rid, const vector<ITEM> &record);
    vector<ITEM> select(const RID &rid);
    RID find_first();
    RID find_next(const RID &rid);
    // 根据索引，按顺序查找，其中 KID 表示 B+ 树中的编号
    pair<KID,RID> index_find_first(BPTree *bpt, const KEY &Left, const KEY
    &Right);
    pair<KID,RID> index_find_next(BPTree *bpt, const KEY &Right, const KID
    &kid);
    void create_key(KeyRaw keyRaw);
    void remove_key(string name);
    Key get_key(string name);
    vector<Key> get_keys(CONTSTR type);
}

页式文件系统

页式文件系统主要是对硬盘上的数据进行管理，并对存取过程进行分页处理提高性能。

我们复用了课程提供的页式文件系统，基本没有做任何修改。

实验结果

【数据删除】

小组分工

  • 【数据删除】：编写记录管理与B+树索引模块，实现记录增删查改接口，使用索引加速处理对应请求，支持多表 JOIN，模糊查询与排序分页

  • 【数据删除】：编写解释器、系统管理、前端模块，实现基本报错、双表JOIN、完整性约束schema增删等基本功能，实现 DATE、UNIQUE、NULL等拓展功能。

参考文献

  • 外部库1：antlr4，用于解析命令。
  • 外部库2：cxxopts，用于解析命令行参数。
  • 使用c++ stl标准库。
Authors: Congyuan Rao