1. Query Engine

1.1. Relational Model

关系型数据库是建模现实世界的关联数据的有组织的集合。最早期数据库难于构建,逻辑与物理层强耦合。

查询流程

SQL(Parser):词法分析和语法分析。

AST(Logical Optimizer):基于关系代数表达式的逻辑计划,基于规则的优化,依据关系代数的等价交换原则做逻辑变换。

Logical Plan(Physical Optimizer):基于代价的优化,依据统计信息,对数据读取,表连接方式,连接顺序等进行优化;计算多种可能的执行计划的代价,生成代价最小的物理执行计划

Physical Plan(Executor):采取串行或者是并行的方式执行Operator,自顶向下或者自顶向上返回数据。

关系代数等价原则

在满足生成相同结果集的条件下,依据关系代数的等价交换原则做逻辑交换,包括:谓词下推(尽早进行过滤;分解复杂条件;笛卡尔积转Join),投影下推,排序、Limit、聚合下推,投影消除,排序消除等。

非关联子查询(子查询不包含非子查询的列):将子查询展开改写,对于包含IN的子查询转为JOIN

关联子查询(子查询包含非子查询的列):优化器添加Apply Operator,将整个包含子查询的表达式转移到Apply的右子树上,尽力将Apply转化为等价的JOIN。需要将INNER PLAN包含相关的列的算子提前到Apply中或之上。

1.2. Execution Engine

1.3. Storage

插入流程:

  1. Client发起请求,查询处理器使用数据字典和统计信息生成最有执行计划
  2. 调用事务管理相关逻辑,如锁、分配事务号时间戳等
  3. 调用文件管理器WAL,向缓存区管理器插入数据和索引

检索流程:

  1. Client发起请求,查询处理器使用数据字典和统计信息生成最有执行计划
  2. 调用事务管理相关逻辑,如锁、分配事务号时间戳等
  3. 调用缓存区管理器查询索引或者是数据的缓存,向文件管理器查询数据和索引,并且写入缓存

存储形式组织

列存储:方便数据压缩,适用于OLAP,或者是查询只涉及部分列。

如果涉及到多个不同的列,就需要多次IO来组合最后的记录

数据粒度Page:将多行数据聚合Page,用于传统的MySQL,PostgreSQL等。存在读写放大问题,元数据少。

数据粒度Tuple:适用于新型NVM介质,但行记录就是最小的访问单元,减少Tuple和Page之间的编解码,元数据多。

索引组织结构

B-Tree:

优点:1. 非叶子结点不包含数据,高度小,单次请求设计的磁盘IO次数少; 2. 每次查询都要到叶子结点,路径长度相同,效率稳定; 3. 所有查询都从根节点出发,范围查询效率高。

缺点:分裂时,逻辑连续的叶子节点在物理上不连续,会产生大量随机的IO,影响性能。

LSM(Log- Structured Merge Tree)

通过内存插入与磁盘顺序写一致,大幅提升写操作,适用于HBase,效率比MySQL高一个量级。

位图索引:

统计范围速度较快,不适用于范围广、或者频繁更新的列

2. Log

2.1. Undo Log

Undo存储位置,在Undo Tablespace的页面,和正常的表空间一样,修改也由redolog记录,所以事物会滚时会操作两边redolog。落盘时,也和普通的数据页一样,由backgroud thread定期从缓冲区刷入磁盘。