Plan

[Kaguya-19]

1. 概述
   本次大作业要求基于给出的 ThssDB 框架，根据作业要求，使用 Java 语言补充、实现、扩展并调优一个关系型数据库管理系统。本次大作业要求完成 ThssDB 的所有基本功能，并且能够在实现基本功能的基础上提高 ThssDB 在增删改查以及事务并发处理等方面的性能。同时，本次大作业要求在提交大作业代码的同时，提交 ThssDB 的设计文档和用户文档（含运行方式）。

2. 核心模块
   2.1 元数据管理模块
   在存储引擎的基础上，实现元数据管理模块。框架中的schema包定义了一些基本概念：

• Table类：表的信息。一个Database可以有多张Table。
• Database类：数据库的信息。用户可以创建多个Database。
• Manager类：管理Database。

2.1.1 基础要求

1. 实现表的创建、删除；
2. 实现数据库的创建、删除、切换；
3. 实现表和数据库的元数据（有哪些数据库，数据库里有哪些表，每个表的结构如何）的持久化。
4. 重启数据库时从持久化的元数据中恢复系统信息。
5. 实现元数据管理模块后，ThssDB应当能够支持下列SQL语句（不区分大小写）：
6. 创建数据库
   create database dbName;
7. 删除数据库
   drop database dbName;
8. 切换数据库
   use dbName;
9. 创建表：实现“NOT NULL”和“PRIMARY KEY”这两个关键字，Type为Int，Long，Float，Double，String（必须给出长度）之一。主键仅在某一列定义。
   CREATE TABLE tableName(
   attrName1 Type1,
   attrName2 Type2,
   attrNameN TypeN NOT NULL,
   …,
   PRIMARY KEY(attrName1)
   );
   示例: CREATE TABLE person (name String(256), ID Int not null, PRIMARY KEY(ID))
10. 删除表：删除某张表的模式信息
    DROP TABLE tableName;
11. 查找表：展示某张表的模式信息(每一列的名字及其数据类型，格式自定);
    SHOW TABLE tableName;
    2.1.2 进阶要求
12. 外键约束的实现
13. 实现表结构的修改（alter table）
14. 添加、删除、修改列
15. 添加、删除表上的约束

2.2 存储模块
完成存储引擎，实现对数据的基本管理。框架中的schema包定义了一些基本概念：

• Column类：一张表的某一列的元信息。成员变量包括该列的名字（name）、数据类型（type）、是否为主键（primary）、是否可以为空（notNull）以及最大长度（maxLength，仅限于String类型）。
• Entry类：某一行记录在表中某一列的数据。
• Row类：某一行记录在表中所有列的数据。

此外，框架中的B+树索引，已在index模块中实现，包含的类有：

• BPlusTree类：用主键entry做key，用真实的row作为value。
• BPlusTreeNode类：B+树结点抽象类。
• BPlusTreeInternalNode类：B+树内部结点类。存储key数组和children数组来支持B+树的索引。
• BPlusTreeLeafNode类：B+树叶子结点类。存储key数组和value数组来支持B+树的索引和真实数据的存储，同时维护一个next指针以支持所有叶子结点可以高效遍历。
• BPlusTreeIterator类：B+树的迭代器类。通过在B+树最底层的的叶子结点维护一个链表就可以高效的实现范围查询和遍历。
  2.2.1 基础要求

1. 实现数据记录的持久化（补充说明：后续测试过程中是内存受限场景，无法全部存储在内存中）。
2. 实现对记录的增加、删除、修改。
3. 支持五种数据类型：Int，Long，Float，Double，String。
4. 实现存储管理模块后，ThssDB应当能够支持下列SQL语句（不区分大小写）：
5. 数据写入：字符串需要用单引号包围，无需考虑负数。
   INSERT INTO [tableName(attrName1, attrName2,…, attrNameN)] VALUES (attrValue1, attrValue2,…, attrValueN);
   示例：INSERT INTO person VALUES (‘Bob’, 15)
   INSERT INTO person(name) VALUES (‘Bob’)会提示字段ID不能为空
6. 数据删除：
   DELETE FROM tableName WHERE attrName = attValue;
7. 数据更新：
   UPDATE tableName SET attrName=attrValue WHERE attrName=attrValue;
   2.2.2 进阶要求
8. 尝试实现更高效的文件存储格式，并在设计文档中说明设计思路及原理，可以考虑以下优化点：
9. 提高I/O效率
10. 减小外存空间占用（合理的编码方式、数据压缩）
11. 页式存储

2.3 查询模块
实现查询引擎，包括SQL解析和查询执行两部分。其中，parser包给出了利用antlr4实现SQL解析的例子。框架中的query包提供了一些可能用到的基础类：

• MetaInfo类：存储一个表的名字和所有列，用来在Queryresult中构建用户想要获取的列的索引。
• QueryResult类：选择运算中选择某些列或全部列的结果，需要对歧义列名或不存在列名、不存在表名等错误情况进行捕捉。
• QueryTable类：选择运算中选择表的方法类，用迭代器的方式从当前表中不断获取新的行并判断其是否满足where中条件。
  负责SQL解析的Parser包提供了一些可能用于生成语法树的基础类，同学可根据需要新增SQL语句：
• parser/ThssDBSQLVisitor类处理语法树，语法树的根结点对应一个数据操纵语句即DML语句，parser/ThssDBSQLVisitor类根据树根结点选择不同函数分别执行（visitSelect_stmt调用query/QueryTable类，delete_stmt调用schema/Manager类等）。ThssDBSQLVisitor类中已经给出实现示例（CreateDatabase），请完成剩余部分。
• query/QueryTable类处理select_stmt语句，扫描From子句中对应的表，生成查询结果，并以QueryResult的形式返回，返回值为一个Table。已给出程序框架，请完成剩余部分。
• query/QueryResult类：create Table等语句的返回结果为一个Message，以表示执行是否成功，而不是一个Table。query/QueryResult类用来保留任意语句的执行结果。已给出程序框架，请完成剩余部分。

2.3.1 基础要求
经过查询模块的实现，ThssDB应当能够支持下列SQL语句（不区分大小写）：
SELECT attrName1, attrName2, … attrNameN FROM tableName [WHERE attrName1 = attrValue];

SELECT tableName1.AttrName1, tableName1.AttrName2…, tableName2.AttrName1, tableName2.AttrName2,… FROM tableName1 JOIN tableName2 ON tableName1.attrName1=tableName2.attrName2 [WHERE attrName1 = attrValue];
上述语句中，Where子句至多涉及一个比较，并且关系为‘’<“,”>”,”<=”,”>=”,”=”,”<>”之一。Select子句不包含表达式。Join至多涉及2张表，On子句的限制同Where子句。
2.3.2 进阶要求

1. 应用课程中介绍的查询优化技术
2. 支持多列主键
3. 实现三张表以上的join
4. 触发器实现

2.4 并发控制模块
实现简单的事务处理模块，支持小规模的并发。
2.4.1 基础要求

1. 实现begin transaction和commit；采用普通锁协议，实现read committed，serializable的隔离级别；
   2.4.2 进阶要求
2. 实现2PL或MVCC协议。

2.5 重启恢复模块
2.5.1 基础要求

1. 实现单一事务的WAL机制，要求实现写log和读log，在重启时能够恢复记录的数据即可。
   2.5.2 进阶要求

2. 多事务并发下的WAL机制。

3. 实现rollback、savepoint等功能。

4. 评分细则

• 本次大作业评分包含以下四个部分
  • 基本功能（50分）
  • 性能（30分）
  • 作业报告、用户手册及期末展示 （20分）
  • 进阶功能 （至多20分，不会溢出）
    3.1 基本功能
• 实现2.1,2.2,2.3所阐述的所有SQL语句，代码完整正确，并且重启数据库能够恢复所有数据及元数据
• 实现read committed，serializable的隔离级别，在并发状态下，符合隔离级别的要求，不会出现死锁
• 单一事务可以通过wal机制进行恢复
  3.2 性能
• 性能测试主要测试在OLTP的场景下每分钟能够处理的事务量，具体的性能测试相关说明会于后续发布，将定义最终性能测试的机器与JVM配置，测试场景，数据规模，测试涉及的SQL语句等。
• 评分按照排名进行分档
  • 前10%是满分 30分
  • 前10%-40% 25分
  • 前40%-70% 20分
  • 前70%-90% 15分
  • 后百分之10% 10分
    3.3 作业报告、用户手册及期末展示
• 用户手册和作业报告需结构完整，逻辑通顺
  • 用户手册主要描述ThssDB基本功能及进阶功能的使用，以及结果的展示
  • 作业报告主要分享模块的设计及重要代码的实现细节
    • 存储模块需要重点分析磁盘文件的文件结构，并分析其优劣性
    • 元数据模块分析元数据持久化的方式
    • 查询模块需要重点描述查询的执行流程
    • 并发控制模块需要描述进行并发控制和锁管理的方案，并分析其优劣性
    • wal模块需描述实现的方案和恢复的流程等
• 期末展示 （时间待定）
  • 每个组需要通过ppt以及简单的demo示例展示作业结果
    3.4 进阶功能
• 进阶功能除上述提及的进阶功能外，也可自行实现课上所学的其他的进阶功能。
• 实现好的进阶功能请在作业报告，用户手册及期末展示中进行阐述和分享。助教将根据同学实现功能的难度，同学展示的结果，以及工作量的评估进行综合性地评分。
• 例如实现了表视图功能，查询优化算法，完整的权限管理，触发器，MVCC并发控制等比较复杂的功能，将可以得到比较高的分数。

4. 提交要求
   作业的最终版本请提交作业的源代码，可运行的Jar包，作业报告以及用户手册。