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中或之上。

插入流程：

检索流程：

存储形式组织

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

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

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

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

索引组织结构

B-Tree：

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

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

LSM（Log- Structured Merge Tree）

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

位图索引：

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

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