数据库

数据库是“按照数据结构来组织、存储和管理数据的仓库”。是一个长期存储在计算机内的、有组织的、有共享的、统一管理的数据集合

数据库系统的目标是为了解决文件处理系统的弊端：

  1. 数据冗余和不一致
  2. 数据访问困难
  3. 数据孤立
  4. 完整性问题
  5. 原子性问题
  6. 并发访问异常
  7. 安全性问题

数据库的4个基本概念

数据系统的特点

数据视图

系统开发人员通过几个层次上的抽系来对用户屏蔽复杂性，以简化用户与系统的交互

物理层（实际数据在物理上的存储结构）->逻辑层（数据库中存储什么数据及这些数据间存 在什么关系）->视图层（某种视角看到的数据）

实例是特定时刻存储在数据库中的信息集合，模式是数据库的整体设计。因此，数据库系统通常可以分为几种不同的模式：

数据模型是描述数据、数据联系、数据语义以及一致性约束等的一套工具，有四类

关系模型

关系模型基本概念对应的关系数据库的概念：

码

用元组的属性来区分不同的元组

模式图

erDiagram    SYS_PERMISSION ||--o{ SYS_ROLE_PERMISSION : "has"    SYS_ROLE ||--o{ SYS_ROLE_PERMISSION : "has"    SYS_ROLE ||--o{ SYS_USER_ROLE : "has"    SYS_USER ||--o{ SYS_USER_ROLE : "has"    SYS_PERMISSION {        int id PK "Primary Key"        varchar(50) permName "Permission Name"        varchar(50) permTag "Permission Tag"        varchar(255) url "URL"    }    SYS_ROLE {        int id PK "Primary Key"        varchar(50) roleName "Role Name"        varchar(50) roleDesc "Role Description"    }    SYS_USER {        int id PK "Primary Key"        varchar(50) username "Username"        varchar(50) realname "Real Name"        varchar(50) password "Password"        date createDate "Creation Date"        date lastLoginTime "Last Login Time"        int enabled "Enabled"        int accountNonExpired "Account Non-Expired"        int accountNonLocked "Account Non-Locked"        int credentialsNonExpired "Credentials Non-Expired"    }    SYS_ROLE_PERMISSION {        int role_id FK "Foreign Key"        int perm_id FK "Foreign Key"    }    SYS_USER_ROLE {        int user_id FK "Foreign Key"        int role_id FK "Foreign Key"    }

关系运算

形式化关系查询语言

关系代数

一种过程化查询语言。它包括 一个运算的集合，这些运算以一个或两个关系为输入， 产生一个新的关系作为结果

运算类型：

关系代数中基本的表达式是：

数据库语言SQL

使用 DDL 来定义数据模式，使用 DML 来表达数据库的查询与更新

DML 分为过程式与声明式，像SQL就是典型的声明式

关系数据库基本概念

文件组织

定长记录

定长记录的文件可以通过维护一个已删除的位置链表，方便后续插入

变长记录

问题：

使用（偏移量，长度）描述一个字段

如何存储动态长度的行：用表头记录位置，尾部通过类似于顺序表的方式管理空间

行在文件中的组织方式

一个文件并非只能存一个表，多表聚簇文件组织可以将多个相关联的表在物理上存储到同一个文件组中，这样在查询的时候可以提高效率，同时也能降低空间成本

数据字典存储

描述表、索引、用户的数据如何存储，大部分数据库都将这些元数据以表的形式暴露出来，供外部读取操作

必须存储的信息类型：

数据库缓冲

数据库缓冲设计跟其他的缓存系统很像，要考虑缓存的淘汰策略，但也有一些是常规缓存没有的：

数据存储和查询

存储管理器

负责在数据库中存储的低层数据与应用程序以及向系统提交的查询之间提供接口的部件

查询处理器

查询处理

数据库将 SQL 转为关系代数，并对关系代数附上注释叫做计算原语，执行一个查询的原语操作序列称为查询执行计划(query-execution plan)，查询执行引擎执行查询执行计划并将结果返回给前端，构造具有最小查询执行代价的查询执行计划叫做查询优化

衡量查询的代价：

选择运算

使用文件扫描和索引的选择

涉及比较的选择

复杂选择的实现

排序

数据库对不能全部放在内存中的关系会进行外排序，最常用的就是外部排序归并算法，利用外部文件多路归并拉实现

连接运算实现

所以为了效率，在选择外层循环的表（驱动表）的时候，一般是选择小表

由于内存缓冲总是有限的，块嵌套循环的驱动表能放入内存缓冲的数量也是有限的，由于内存缓冲的淘汰策略大部分都是LRU，可能就会导致内存缓冲的数据不断被淘汰，以载入块嵌套的缓冲，而这些被淘汰的数据可能都是热数据，这就很影响性能

其他运算实现

表达式计算

查询优化原理

一个给定的查询，通常会有许多种可能的执行策略，查询优化就是从这许多策略中找出最搞笑的查询执行计划的过程

产生逻辑一致的表达式 -> 产生不同的查询计划 -> 评估查询计划，选择代价最小的

关系表达式的转换

如果两个关系表达式在每一个有效数据库实例中都会产生相同的元组集，则称它们是等价的

等价规则

如集合的结合律：$$(E1\cup E2) \cup E3 = E1\cup (E2 \cup E3)$$

连接的次序

巧妙编排连接中关系的顺序可以有效减少临时结果大小

一个小关系连接大关系比大关系连接小关系查的更快

等价表达式的枚举

为了查询得到所有等价表达式，通过递归将子表达式进行等价替换来得到所有等价的表达式，在枚举这些表达式的过程中，可以根据代价来对一些表达式进行剪枝

表达式结果集统计大小的估计

为了计算查询的代价，要通过一些统计信息来进行，这个估计并不十分精确，这些统计数据大部分都是通过随机抽样来生成的，还有些数据库不会自动更新统计数据，而是让 DBA 手动运行命令的方式来进行生成

整体来说，这一部分就是要通过计算概率的方式，来计算出执行的代价

执行计划选择

物化视图

通过冗余，其内容已计算并存储的识图，这种物理视图的读取代价比逻辑视图低

视图维护

手工代码维护：真正的数据修改之后，再额外去修改物化视图的数据

增量视图维护：这种就是根据视图的查询语句，计算每次更新与物理视图会产生什么差异，再由系统去修改视图的数据，如：

查询优化和物化视图

物化视图可以被用来优化一些查询，假设要查询 a join b join c

现有 物化视图 v = a join b，通过 v join c 可以有效降低临时结果，降低查询代价

反过来也是 如果物化视图查询代价过高，可以把它拆分成原始查询

其他优化

数据库体系结构

集中式系统

运行在单台计算机系统上，不与其他计算机系统交互

粗粒度并行的机器只有几个核心，一般一个查询只会跑在一个核心上

细粒度并行的机器则有大量处理器，将并行执行用户提交的查询

CS系统

sequenceDiagram  客户端 ->> 服务端: 提交查询  服务端 ->> 客户端: 返回结果

服务器系统体系结构

block-beta  columns 3  block:用户进程组:3    columns 3    用户进程1 用户进程2 用户进程3  end  space space space  block:服务器进程组:3    columns 3    服务器进程1 服务器进程2 服务器进程3  end  用户进程1 --> 服务器进程1  用户进程2 --> 服务器进程2  用户进程3 --> 服务器进程3  space space space  block:共享内存:2    %% columns auto (default)    缓冲池    查询计划高速缓存    日志缓冲区 锁表  end  服务器进程1 --> 共享内存  服务器进程2 --> 共享内存  服务器进程3 --> 共享内存  block:进程组:1    columns 1    进程监控进程 锁管理器进程  end  space space space  数据库写进程 日志写进程 检查点进程  数据磁盘[("数据磁盘")] space 日志磁盘[("日志磁盘")]  日志缓冲区 --> 日志写进程  日志缓冲区 --> 检查点进程  日志写进程 --> 日志磁盘  缓冲池 --> 数据库写进程  数据库写进程 --> 数据磁盘

并行系统

通过增加并行度在更短的时间内运行一个给定的任务称为加速比(speedup)。通过增加并行度来处理更大的任务称为扩展比(scaleup)

20230508204919

20230508204943

并行数据库体系结构

并行数据库

并行系统设计需注意到的可用性问题：

IO 并行

将关系划分到多张磁盘上来缩减从磁盘上对关系进行检索所需的时间，是一种数据分区

划分技术：

除了轮转分区，其他两种方式都有可能产生数据倾斜，为了规避倾斜，通常有两种方式：

  1. 事先进行统计，根据数据的分布规划分区
  2. 一致性哈希

查询间并行

不同查询或事务彼此并行执行

这种并行需要考虑不同节点之间的数据一致性问题

查询内并行

单个查询在多个处理器和磁盘上并行执行

并行需要考虑以下代价：

  1. 启动运算的代价
  2. 数据倾斜导致计算不均衡
  3. 数据的并发竞争
  4. 各个节点计算完成之后统一汇总的代价

并行使得查询优化更复杂：代价模型更复杂、考虑倾斜、并发竞争...

分布式数据库

服务于写多读少、低延时、海量并发 OLTP 场景的，具备海量数据存储能力和高可靠性的关系型数据库

一致性

观察数据一致性的两个视角：

架构风格

PostgreSQL-XC

20221212171450

NewSQL

20221212171629

很多产品为了获得更好的计算性能，会尽量将更多计算下压到存储节点执行，更偏向于PostgreSQL-XC风格

全局时钟

TrueTime

时间源是 GPS 和原子钟，所以属于多时间源和物理时钟，同时它也采用了多点授时机制，依赖于特定硬件设备

HLC

每个节点会使用本地时钟作为参照，但不受到时钟回拨的影响，可以保证单调递增。本质上，HLC 还是 Lamport 逻辑时钟的变体，所以对于不同节点上没有调用关系的两个事件，是无法精确判断先后关系的

TSO

20221212172944

STP

20221212173331

可用性

分布式数据库为了提升可用性：

HTAP

为了解决 OLAP 的时效性问题，有两种思路：

  1. 以 KAPPA 架构为代表的准实时数据计算替代批处理
  2. 在 OLTP 内扩展，实现又能 TP 又能 AP，称之为 HTAP

存储设计：

  1. 融合性存储 PAX（Partition Attributes Across）方案
  2. 在原有行式存储的基础上，新增列式存储，通过数据同步的方式，将行数据同步为列数据进行分析，对于分析请求，每次都要确认本地的数据是否足够新，而后才会执行查询操作

分布式查询处理

由于分布式数据库引入了分区，在进行查询时就没那么方便了，执行器要根据 where 条件决定去哪里查，还有 join 也更复杂了，查询符合条件的数据要如何查代价才小，还有查询完成之后的汇总合并

存算分离下的查询优化：

存算分离下的 join 处理：

聚合计算加速：

火山模型：查询执行引擎可以优雅地将任意 Operator 组装在一起，而不需要考虑每个 Operator 的具体处理逻辑

select count(*) from store_sales where ss_item_sk = 1000;
sequenceDiagram  Aggegation ->> Project: Next()  Project ->> Filter: Next()  Project ->> TableScan: Next()  TableScan ->> DataBase: Next()  DataBase ->> TableScan: Tuple  TableScan ->> Filter: Tuple  Filter ->> Project: Tuple  Project ->> Aggegation: Tuple

火山模型的问题在于每次调用 Next 虚函数有一定开销，同时使用这种抽象的模式也没法充分利用 CPU 的循环展开、SIMD 等特性，有一些优化手段：

  1. 运算符融合：简化运算符嵌套关系，从而降低虚函数调用次数
  2. 向量化：每次不止取出一个 Tuple，而是一批 Tuple 进行计算，利用 SIMD 的能力提升速度
  3. 代码生成：通过编译器将 SQL 编译为简单循环，便于 CPU 能进行循环展开优化

特种数据库

时序数据库

数据的时间维度

时序数据库

双时态数据库既支持事务时间又支持有效时间

时态数据查询语言

多媒体数据库

对象数据库

对象数据库系统可以直接将对象存储在本地硬盘或内存中，并提供相应的数据管理和查询接口

SQL中的结构类型和继承

CREATE TYPE Name AS(firstname VARCHAR(20),lastname VARCHAR(20)) final;
CREATE TYPE Apple UNDER Fruit

表继承

CREATE TABLE Apple UNDER Fruit

对象持久化

对象数据库提供了多种对象持久化方式，包括按类持久化、按创建持久化、按标志持久化和按可达性持久化等

数据库系统的历史

NoSQL

充分利用各种不同NoSQL数据库的特性来助推业务