2023年秋1组项目总结报告

系统架构设计

整体可分为三层：

1. 文件系统层（Rust，/backend/src，db_backend.native）：读写文件（表/索引），但不管理目录结构，也不负责维护索引和检查约束条件（type/null/default 除外）
2. 逻辑层（Python，/backend/pysrc/db_backend，db_backend）：具体的各项操作的实现，包括数据库管理、表管理、增删查改；具体的数据操作则调用
3. 应用层（Python，/app）：用户交互，包括命令行参数解析、语法解析、输入输出和一部分逻辑

各模块详细设计

1.1 页式文件系统

由于我们没有使用 C++，所以没有使用提供的参考实现而是仿照其工作方式自行编写了一套。相关文件位于 /backend/src/fs.rs。

这部分用到的一些第三方库：

• lru：一个高效的 LRU 缓存实现
• once_cell + parking_lot：线程安全相关 因为要涉及到数据在 Python 运行时与 Rust 库运行时之间的移动，必须要保证线程安全，但是实际上并没有用到多线程
• aHash：标准库中哈希表功能的替代

1.2 记录模块

相关文件位于 /backend/src/data.rs。

数据页设计：

• (4bytes) next_free: u32 空闲页链表项页号 使用 !0 表示没有下一个空闲页
• (60bytes) used_map 位图 一共 60*8=480 个槽位 记录页面使用情况
• (4096-64bytes) 数据区 每条数据的格式如下：
• (ceil(columns/8) bytes) null_map 位图 记录列是否为 null
• (4bytes) INT
• (8bytes) FLOAT
• (n bytes) VARCHAR(n)
• (4bytes) DATE (as INT) 具体存储的值是 chrono 中 NaiveDate 实现中的内部数值 根据他们的代码，其值为 (year<<13) | (ordinal << 4) | flags

空闲页链表的头指针与表定义等信息一并存储在元数据里，之后会提到

这部分用到的一些第三方库：

• bitvec 位图
• zerocopy 检查结构体内存对齐条件，保证原始二进制数据到结构体数据转换的安全性 实际上也可以不使用，但是进行数据页操作就需要引入 unsafe 代码且无法保证安全性

1.3 索引模块

相关文件位于 /backend/src/index。

这一部分主要就是一个 B+ 树的实现，以及一个索引关键字的编码方案。

索引页设计：

• (4bytes) parent: u32 父结点页号
• (4bytes) next_leaf: u32 叶结点链表项页号
• (4bytes) ty: u32 结点类型 实际上只有最低位起判断作用 但为了对齐使用 4 字节存储
• (4bytes) len: u32 结点大小
• (340*8bytes) keys: [u64; 640] 关键字
• (340*4bytes) values: [u32; 640] 值 内部结点存储叶结点页号 叶结点存储记录位置

索引关键字统一存储为 u64，是因为在 /backend/src/key 中实现了一套将任意类型数据或它们的二元组编码为 u64 的方案。具体实现为：

• INT: v + 2147483648
• FLOAT: v > 0 ? v : v & 0x7FFF_FFFF_FFFF_FFFF
• VARCHAR: v[0..8]
• 若为二元组则分别编码进高低 4 字节

这一编码方案能够保证有序性。

这一部分除了上边已经说过的 zerocopy 没用使用其他第三方库。

1.4 与 Python 的互操作

基于 PyO3（绑定）和 Maturin（构建工具）

主要内容：

1. 转换数据类型，包括记录内容和表定义等数据，相关文件位于 /backend/src/types.rs
2. 封装记录模块和索引模块提供的接口，提供给 Python 代码使用。具体接口的实现等说明见后文。

这一部分还用到的其他第三方库：

• chrono：前面提到过的用于存储 DATE 的库。使用该库主要是因为 PyO3 提供了它与 Python 内置 datetime 的转换
• thiserror：用于错误汇报 相关代码位于 /backend/src/error.rs
• bincode：用于编码表的元数据

2.1 Table

对数据表的封装，调用 native 部分提供的内部接口。相关文件位于 /backend/pysrc/db_backend/table.py

这一部分实现的具体逻辑包括：

• 单表数据增删查改
• 索引管理
• 索引数据维护：native 部分在插入数据时并不自动同步写入索引，维护操作在此处发生
• 主键约束、unique 约束检查
• 使用索引的扫描加速：依据约束条件选择合适的索引，还可以提前停止扫描

2.2 Database

一个数据库的实现。在文件系统中里对应一个文件夹，而每个表对应其一个子文件夹。相关文件位于 /backend/pysrc/db_backend/database.py

这一部分实现的具体逻辑包括：

• 数据表管理
• 外键检查
• 多表连接查询

关于连接，我们采用的连接算法大约是：

1. 根据约束条件，对要查询的表进行排序，以使得尽可能提前查询约束更强、数据更少的表
2. 依次查询每个表，查询时使用原条件中只包含该表的条件加上由已经查得的表的数据的连接构成的新条件（使用IN）
3. 对查询结果进行组合

2.3 DBMS

数据库管理。相关文件位于 /backend/pysrc/db_backend/dbms.py

2.4 AST

我们实现的 SQL 语法的抽象语法树的数据类型定义，相关文件位于 /backend/pysrc/db_backend/node.py。不过该文件中不只有 AST 的内容，也包括了索引名称生成、运算符检查等。

3.1 语法解析

我们一开始是用的是 antlr 及提供的文法文件进行解析，但是随着使用我们发现其 python 运行时 1. 缺失文档 2. 没有类型注解，十分难以使用，于是我们切换为了完全使用 Python 编写（而不是 Java！）的 Lark 库并自行编写了文法，文法文件见 /app/sql.lark。此外还有 /app/transformer.py 用于将解析器生成的语法树转化为上面我们自己定义的 AST 数据类型。

3.2 用户交互

这一部分没有太多需要额外说明的内容，主要就是对以上所有功能的封装。一个例外是 SELECT 语句的 GROUP BY 和 LIMIT OFFSET 其实是在此处实现的。

GROUP BY 的实现方式大约为：

• 按筛选条件查询“被 GROUP BY 的列”
• 对于每个查到的结果，加入为新的筛选条件重新查询

主要对用到的第三方库进行一下说明：

• Typer：命令行参数解析
• rich：输出表格
• prompt_toolkit：CLI prompt
  值得一提的是它的默认行为及可选项并不能很好的适用于 SQL 命令行这一功能，我们在阅读其源码后使用了一些 hack 来使它能够满足需求。详见 /app/app.py 中的 patched_prompt_session 函数。
• pygments：语法高亮

主要接口说明

fs

FileManager:

• sync_raw 同步页面
• make_cache 缓存页面
• get_page/get_page_mut 读取页面缓存或缓存新页面
• close 关闭文件

PagedFile:

• open/new 打开文件
• get_page 获取页面标识符
• pages/set_pages 文件长度
• alloc_page 分配新页面
• recycle_page 回收页面

native

提供给 Python 使用的接口，可见 /backend/pysrc/db_backend/native.pyi

IndexNative

• iter 完整遍历 index 或给定一个 key，遍历所有大于该 key 的索引记录
• insert 插入记录
• remove_exact 删除记录
• remove_range 删除关键字在区间内的记录（但是实际上没有用到）

TableNative

• create 创建表
• __init__ 打开表
• write_row 写入记录
• read_row 读取记录
• insert_row 插入记录
• remove_row 删除记录
• create_index 创建索引
• open_index 打开索引
• drop_index 删除索引
• iter 遍历整表
• indexes 获取索引列表
• table_def 获取定义或修改定义

系统管理

class DBMS:
    using: Database | None
    def __init__(self, base: Path):
      """
      构造函数，记录数据库地址，管理所有数据库
      """
    def create_database(self, db: str):
      """
      创建数据库
      """
    def drop_database(self, db: str):
      """
      删除数据库
      """
    def open_database(self, db: str):
      """
      打开数据库，返回数据库对象
      """
    def use_database(self, db: str):
      """
      使用数据库，将using指向该数据库对象
      """

class Database:
    def __init__(self, base: Path):
      """
      构造函数，记录数据库地址，管理所有数据表
      """
    def get_table(self, tbl: str) -> Table:
      """
      获取数据表对象
      """
    def create_table(self, stmt: CreateTable):
      """
      创建数据表及索引
      """
    def drop_table(self, tbl: str):
      """
      删除数据表
      """

查询处理

class Database:
    def check_foreign_key_parent(
        self,
        key: IndexKey,
        parent: str,
        parent_cols: list[str],
    ) -> bool:
      """
      检查外键约束，如果检索的键在父表中不存在，返回False
      """
    def check_foreign_key_child(
        self,
        parent: Table,
        old_record: Row,
        new_record: Row | None = None
    ) -> bool:
      """
      检查外键约束，如果检索的键没有被子表引用，返回True
      """
    def insert_records(self, stmt: Insert):
      """
      检查记录是否符合数据类型要求和外键约束后，调用数据表的插入接口
      """
    def delete_records(self, stmt: Delete):
      """
      检查外键约束后，调用数据表的删除接口
      """
    def update_records(self, stmt: Update):
      """
      检查外键约束后，调用数据表的更新接口
      """
    def select_records(
        self,
        selectors: list[Selector] | None,
        tbls: list[str],
        where: list[Condition],
    ):
      """
      查询
      """
    def load_data(self, stmt: LoadDataInFile):
      """
      非检查的调用table类中的insert接口，实现数据表导入
      ”“”

class Table:
    def __init__(self, path: Path):
      """
      构造函数，创建`native`对象，并恢复索引
      """
    def iter(self, conditions: list[Condition] | None = None):
      """
      返回满足 `Condition` 的迭代器
      """
    def find_column(self, name: str) -> int:
      """
      根据列名查询位置
      """
    def select_column(self, record: Row, col: TableColumn) -> Value:
      """
      根据列名返回记录中特定位置的值
      """
    def check_condition_single_table(self, record: Row, cond: Condition) -> bool:
      """
      对于给定的记录，检查是否满足 `Condition`
      """
    def insert_record(self, record: Row, check=True):
      """
      插入记录，维护索引，并进行主键约束检查
      """
    def delete_record(self, rid: Rid, record: Row):
      """
      删除记录并维护索引
      """
    def update_record(self, rid: Rid, old_record: Row, record: Row):
      """
      更新记录，维护索引并进行约束检查
      """
    def select_records(
        self,
        selectors: list[Selector] | None,
        conditions: list[Condition] | None,
    ) -> list[list[Value]]:
      """
      单表查询接口
      """

实验结果

最终我们的项目实现的功能主要就是 ci 测试中需要的全部功能，不过也需要做一些额外说明：

• 没有实现多表连接查询时的 SELECT * 操作：没有实现这个单纯只是因为时间紧张并且 ci 测试中没有要求，要实现的话也比较简单
• 索引理论上也支持 FLOAT VARCHAR DATE 类型的数据 但是没有经过充分测试
• 没有实现 SELECT 筛选条件中跨表的列比较操作（全部认为是=），但是实现了同一张表内的列比较
• LIMIT OFFSET 的实际做法是获取到全部结果后再选出需要的部分，理论上应当在扫描过程中就预先筛选；但是这里的特殊情况是query-order 测例中排序的列 L_SUPPKEY 并没有单独的索引而是二元索引的一部分，扫描效率较低，而筛选条件 L_ORDERKEY < 10 恰好有一个 L_ORDERKEY 的单独索引，扫描速度较快且筛选出的项目很少，这样实现的效率反而更高

此外，native 部分还编写了充分的单元测试（尽管没有考虑覆盖率），在 backend 目录下运行 cargo test 即可运行单元测试。这些单元测试很好的保证了 native 部分的逻辑正确性，减轻了在编写 Python 部分时面临的调试压力。单元测试中还额外用到了两个第三方库：

• rand：随机数生成
• tempfile：临时文件，用于文件系统和索引模块的测试

小组分工

• 【数据删除】：（原）语法解析、系统管理、查询处理
• 【数据删除】：系统管理、杂项
• 【数据删除】：native 部分、（重写的）语法解析、优化、杂项

参考文献

【数据删除】

Authors: Congyuan Rao