Skip to content

Latest commit

 

History

History
169 lines (118 loc) · 7.48 KB

Design.md

File metadata and controls

169 lines (118 loc) · 7.48 KB
Raw

存储层

磁盘管理

难点：

  • 如何在db读模式启动时快速收集已分配和未分配的page id信息？ 现行方案是顺序读，但显然是非常低效的(考虑bitmap？)
  • .mtd文件的logging和recovery，确保元数据能在各种情况下与数据库实际情况保持一致，这有待研究。为了避免不一致导致的后果所以采用了上一个难点的现行方案，但代价是效率奇差。

待改进：

  • 启动时高效收集已分配和未分配page id的信息，使用bitmap管理页面号信息
  • 使用bitmap做管理后就没有必要使用max_ava_pgid_、max_alloced_pgid_、alloced_pgid_和free_pgid_对page id做管理，这会占用大量空间，拿一个缓冲池(不是bpm)存放bitmap直接做管理更方便高效
  • 相同表内的数据没有做到连续存储，磁盘I/O开销会非常大！(当然这是后话，如果以实现基本功能为目标，它的优先级不高)

存储模型：行存储

页面的物理排列：所有数据都是存放在一个文件中的，依靠页面的page id得到其存储的偏移值

启动模式：创建文件启动和读文件启动，前者是在没有任何已有文件下，自行创建文件启动，后者依靠读取已有文件启动

元数据管理：DiskManager中管理以下字段：

  • max_ava_pgid_：最大可获得的page id(右开)，每次free_pgid用完后都会把max_ava_pgid_翻番，然后把多出来的free id加入到free_pgid_中
  • max_alloced_pgid_：最大已分配page id，用于定期检查以在尾端裁剪文件，否则id不断增大，文件大小永远不会缩小
  • alloced_pgid_：存储已分配页面的集合
  • free_pgid_：存储可用页面集合，每次都是分配最小的page id

读模式下，max_ava_pgid_ 可以从 .mtd 文件中读取，alloced_pgid_ 和 free_pgid_是在遍历 .db 文件时获取，遍历 .db 文件指的是扫描整个文件，查看每页的状态位，如果是已分配状态就把它加入到alloced_pgid_，否则加入free_pgid_，同时随时更新max_alloced_pgid_

缓冲池

难点：

  • 暂无

待改进：

  • frame_id的寻找和淘汰使用的是顺序搜索，效率低，因为它会访问许多不存在的帧框

和15-445实现的差不多，暂时没有什么特别的

索引层

为降低复杂度，不支持联合索引

聚簇索引

索引为立即更新模式

哈希索引

冲突解决：链表法

LinkHashPage：存放索引槽的页面，每个槽存放一个page_id指向一个LinkHashPage或TablePage

TablePage：这是实际存放数据的地方，可以形成一张单链表

每次删除都会检查删除后TablePage是否还有数据，没有就删除本TablePage

槽总数计算： LinkHashIndex的头页面假设可以存放700个page_id，LinkHashSlotPage每张可以存放700个page_id，所以槽总数就是700*700 = 490000

可以将哈希索需要的页面分为三层：

  • 第一层是一张LinkHashPage，它的槽存放着指向第二层LinkHashPage的page id
  • 第二层是存放槽的页面(LinkHashPage)，槽中记录着存储数据的第一张页面page id
  • 第三层是存放数据的页面(TablePage)，一张存放数据的页面肯定不够，所以它会形成一张双向链表

查询计划与执行

设计实现

  • 火山模型
  • Join操作使用哈希连接实现，使用布隆过滤器做优化
  • max_sql_mem：设置了每条sql语句可以使用的最大内存，目前默认设置为缓冲池总大小的三分之一
  • 每个执行器如何使用内存？
    • 采用贪心策略，每个执行器尽可能多地申请内存，直至达到max_sql_mem或者获取内存失败，按照已拿到的内存大小进行处理。如果有需要，处理完后的结果暂时存放在磁盘然后释放占用的空间。

逻辑计划：

物理计划：

执行器：

  • 表扫描执行器目前统一不依赖索引，只是做单纯的暴力扫描

待改进：

  • 在投影执行器中，聚集操作会在执行器打开的时候立马进行，这会让执行器遍历一遍表，关闭子执行器，然后再打开。如果子执行器是个连接执行器，那么系统将会做两遍连接操作！这是非常低效的，也许我们可以下推聚集操作得到更好的性能，但目前简便起见暂不做改动。

功能支持情况

  • 不支持子查询
  • 不支持查询下推，不做任何优化

目前支持的关系代数：

  • 选择(σ)
  • 投影(π)
  • 笛卡尔积(×)
  • 聚集(γ)

目前支持的聚集函数：

  • MAX()
  • MIN()
  • COUNT()
  • SUM()

支持的SQL语句

  • DDL
    • 创建表
    • 删除表
    • 重命名表(暂不实现)
    • 查看表(暂不实现)
  • DML
    • 插入数据
    • 删除数据
    • 更新数据(暂不实现)
  • DQL
    • SELECT后面只支持聚集函数和列名，不支持其它功能
    • FROM后面最多只支持两张表的联结
    • where后面支持"<" "<=" ">" ">=" "=" "!="，不支持and、or等
  • DCL
    • 目前不准备支持任何DCL

DDL

  • CREATE
    • 有且只有一个key
    • 全部not null
    • 目前支持的类型：Bool、Integer、Decimal和Char
  • DROP

DML

  • INSERT
    • 只支持如下形式：
    • INSERT INTO table_name VALUES('123', 1);
  • DELETE
  • SELECT

系统数据与管理

待改进：

  • 所有元组只支持固定长度，可以为此改进为可变长(感觉没什么必要，可变长需要修改的东西太多)
  • 目前每条数据的插入都是从前向后遍历，需要实现一套类似C++内存管理的机制以提升效率
  • 表的所有操作和管理暂时都使用大锁，以后再做更精确的控制
  • 在目前的实现中一张表拥有的页面数量是单方面增长的，但如果大量数据被删除，占用那么多空间显然是非常浪费的，需要一种机制实现页面数量的缩减，难点是考虑并发情况下的缩减不会影响其它功能而且效率不会太低
  • TablePage管理Tuple的slot只会增加，空slot不会被回收，这会导致一张页面可能有太多的空slot而占用空间(但是只要把尾端的空slot消除即可，我们不应该移动任何已经占用的slot)
  • TablePage使用的是线性寻找空slot，速度可能会很慢，也许可以用bitmap？
  • Table中的删除、更新和查找的元组位置都是利用传入的RID参数确定的，RID是否合法根本没有任何检测！也不知道RID中携带的page id是不是属于这张表的。所以如果有必要，我们需要增加一个管理性质的数据结构以确定RID的合法性。
  • Table的插入数据功能假定了磁盘是无限大的，需要处理磁盘不足导致的异常。

DBManager：内含DiskManager、BufferPoolManager和Catalog指针，它是目前是整个数据库的总控制中心

Catalog：负责管理系统元数据，目前其中包含CatalogTable，未来可能会包含更多类似CatalogTable这样的子Catalog

CatalogTable：表管理目录，用于管理表的增删改查

TableMetaData：存储表和的元数据

Table：表，由它提供的接口对表实现元组的增删改查，其背后实际上是依赖TablePage提供的功能来完成接口的工作。

TablePage：继承自Page，是对页面做实际修改的类，它本身不会考虑并发问题，完全由调用它的人做并发控制 页面中的slot数量在目前的实现中只会增加。

Tuple：元组，负责装载数据的。(暂时不能让元组中的某列置空)

注意：Tuple和TablePage中存放字符串都是不带'\0'的

目前只实现下面四种类型，暂时没必要实现更多的类型

  • Bool
  • Integer
  • Decimal
  • Char
  • BigInt(TODO) 在计算sum的时候可能会需要用到