Database System Concepts 7th

前面使用部分不太感兴趣，直接从第十章开始看

Ep10 大数据分析

偏向大数据一些的基础架构。回头写。

Ep 11 数据分析

偏向利用 Ep10 拿到的结果再做一些分析。回头写。

Ep12 物理存储系统

首先存储是分层的，具体而言是：

  1. cache
  2. main memory
  3. flash memory(SSD)
  4. 磁盘存储（感觉经常在商业系统存一些冷数据）
  5. 光学存储器（类似 DVD）
  6. 磁带存储器

此外存储器还有接口，对应物理接口和一些协议栈：

  1. SATA 总线
  2. PCIe 总线

在协议上也有区别

  1. NVMe 协议
  2. SCSI 协议

此外，硬件接口也有区别，最常见的是 mSATA 和 M.2. 这个可以去 jd 搜搜，一看就懂。

具体可看：https://sjtu-sjtug.feishu.cn/docs/doccnfdnoqmgt6qqko5GM0tAKkh# 和 《深入浅出 SSD》这两个材料。

存储设备在互联网上可能以 SAN 的形式组织，这种形式提供了盘一样的访问接口，现在也有 ifiniBand 之类的方式。此外还有 NAS 之类的，提供网络文件系统的形式（我在家组了个 NAS 放片，爽的）。

磁盘

以 sector 为形式组织，受限于物理的访问，磁盘生命取决于保存和访问。对外提供的性能大概是：

  1. 2-20ms 的 seek time
  2. 旋转时间: 可能又是个位数 ms
  3. 传输：50-200MB/s
  4. sector: 可能是 512B

闪存

SSD 性质看看我之前介绍就行，in short，长一点的可以看之前那个：

  1. 我之前抄的：https://zhuanlan.zhihu.com/p/430451374
  2. 长一点的，感谢 SJTU：https://sjtu-sjtug.feishu.cn/docs/doccnfdnoqmgt6qqko5GM0tAKkh#

关于性能，可以到数千 MB/s, 同时有一定的并行读写能力。我感觉现在一般大公司内部都一堆 SSD 来 Handle 用户的写入

RAID

上大学的时候背过 RAID0-RAID5 应付考试，现在全忘光了，感觉再背一遍也没什么意思，就主要讲讲思路吧。

  1. 冗余以提高可靠性
    1. 这点对现在的人其实有点 confusing，为什么呢，现在的时代很多时候可能单机都不需要考虑数据的靠谱，靠 GFS Style 的备份之类的是更常见的 idiom. 跟群友讨论了下，ebs/GFS 这种感觉目前还是领先地位的，RAID0 RAID1 是可以用的
  2. 并行以提高性能
    1. 感觉这个在 SSD 上用处有限，HDD 上倒是好一些？

EP13 数据存储结构

这章感觉也很 trivial，就讨论了各种存储的结构：

  1. 架设在行存中的数据库
  2. 架设在列存中的数据库
  3. 内存数据库/NVM 数据库

行存的数据组织

传统的 RDBMS 会以 Block/Page 为粒度组织系统，本身 HDD/SDD 都是基于块的存储设备。它们的大小通常为 4kB/8kB/16kB。

假设 Page 大小是固定的。定长记录可以从 Catalog 里面知道长度，直接顺序存就行，变长记录可能需要一些特殊方式：

E4DE3EA7-EA78-4FE0-9A54-1F6459096D96

上图是 PG 中的处理形式，PG 的 HeapPage 单个 Page 内会这样组织数据。这里有个很清晰的问题是，在数据删除比较多的时候会怎么重新组织，这个时候它会在 Vacuum 阶段处理这些数据。

此外，MySQL 的 InnoDB Page 内部记录组织会更复杂一些。采用了链表+minmax+稀疏索引的形式。究其原因，InnoDB 对写操作支持要好很多，这些都可以算在写操作的支持里面。

大对象存储

MySQL 的 Page 要求 Btr 的 Page 会至少存储两个 record, 多的纪录会放到 BLOB 对象和 Page 中。

PostgreSQL 有 TOAST 对象，具体如下：https://cch1996.github.io/2020/09/22/postgres-04/

简单来说，TOAST 记录会放在 TOAST 表中。

文件记录的组织

  1. HeapFile 组织，记录放在文件的人和地方
  2. 顺序文件组织
  3. B+Tree 文件组织
  4. Hashing 文件组织

Record 的组织可以看我之前写的内容的 Tuple 部分：https://zhuanlan.zhihu.com/p/457605514

对于传统的 RDBMS，在 Stonebraker 的文章 中，表示虽然文件系统可能会有一些特殊的组织方式，不会按文件的格式顺序存放所有块，但是直接用文件组织的话，开销是比较小的。新时代随着 SPDK 等技术的发展，这个可能会有一点变化，但是程序员我感觉也不用太关注。

对于 Page 的组织，PostgreSQL 做的简单一些，会放在 Database Cluster 的空间中，PG 除了表文件，还有对应的 _fsm （空间空间映射）和 _vm （可见性映射），通过在 fsm 的标记找到可用的 Page，然后找到写入的 Page。

InnoDB 这个要复杂一些：

  1. Extent （区）：连续存放 64 个 Page，希望提高 Page 分配的局部性
  2. Segment（段）：存放不同类型的数据，比如叶子结点段、非叶子结点段。Segment 会向 OS 申请 Extent 大小的存储空间。

回收的时候，PG 根据 Freeze/Vacuum 和 _vm 的标记来回收，InnoDB 则会根据 Extent 的链表（XDES）来做回收

Partition

数据根据某个 key 划分成多个文件/空间。这种方式能够将单个库拆分、做冷热分离，但也会影响跟这个 key 无关的请求。

Catalog

一般 Catalog 可以全部保持在内存中，存储的时候要持久化。

Buffer Pool Manager

掠过不谈，反正就经典 Pin, Cache Replacement, Dirty 之类的。看 InnoDB 策略、ARC 基本就行了。

这里还有个写顺序和 WAL 的问题，略过不谈，反正 recovery system 可以讲。

本质上就是预测用户行为，然后丢缓存之类的。

面向列的存储

没啥说的，基本参考 abadi 的 Columnar DBMS，存储看我这篇：https://zhuanlan.zhihu.com/p/457889634

Main-Memory DB

感觉这部分讲的还是内存上的，行列都讲，就写的不是很清晰，没啥意思。

Ep14 索引结构

B+Tree 都看吐了，我一个字都不想写。就跟 Btree 比一下简单一些，Btree 省空间一点，但是没啥意义，很容易被抹平。

SSD 上的 Btree Style 索引：

  1. BwTree
  2. FDTree
  3. MassTree

我个人反正感觉这些东西反而很多都没用上，除了 ms 的论文，就 Ark 用了下 BwTree。不知道是这些结构本身不靠谱，还是 TP 系统和 Btree 已经是时代的眼泪了。

Btree 本身是为 HDD 那样的结构设计的，在 SSD 上，Btree 还是有优势的，因为内存和 SSD 还是有 gap 的，而且 Btr 本身会有一些很细的优化，比如 trxn 之类的，但是这套东西也还是很难实现的。以 BwTree 为例：

BwTree 做了：

  1. Mapping Table: 对 Node 或者写入的映射
  2. 写入类似 Log 的形式存放，Btree 也预留了空间
  3. 无锁

主存上的索引类似 ART.

还有 hashing 索引什么的，我感觉这些国内材料比较少，我自己也没写过，就不谈了。

LSM 是新时代的宠儿，因为实现比 Btr 简单，性能不错，写性能很好（设计者认为，读是很好优化的）可调整可预测，还有 RocksDB 什么的。这里还有些 WiscKey 之类的 SSD 友好结构，不过 WiscKey 设计也有一些问题，比如: https://www.skyzh.dev/posts/articles/2021-08-07-lsm-kv-separation-overview/ 。此外 LSM 虽然本身是一个写优化的结构，但是它的思路被放到了很多 HTAP 类似的读写混合系统里面。

这里还提到了 Buffer Tree，我觉得有点类似 FD-Tree, 把更新搞到一个缓冲区（Delta），然后先找 Delta 再找下面，Buffer 满了之后按一定策略来下推。

位图索引（我记得 PG 有这个），本身和列存那套差不多，当然这套东西也可以做到 Btree 上(防止一个 Page 放不下？)。删除记录可能在定位的地方产生洞，这里可以用一个 exist 的位图表示，不过我觉得 TUM 的 PDT 思路好一些，它用了一个偏移量的 B树（Position Delta Tree）来表述。此外：

  1. 如果只有某个值出现的比较多，可以单独给它一个索引
  2. 如果叶子结点发现可以位图压缩，那就用

上面这些优化我感觉都是看上去能省空间，但是实际情况有点 confusing 的，暂且不表吧。

空间结构：k-d-B 树。这名字有点复杂，可以先看 k-d 树：https://oi-wiki.org/ds/kdt/#_3 。k-d 树形态上是一个 Binary Search Tree，这里相当于提供了一个 Btree 的形式。

Ep15 查询执行

直接看这个就行，对应本章的笔记：https://zhuanlan.zhihu.com/p/349943902

Ep16 查询优化

统计信息参见：https://zhuanlan.zhihu.com/p/350255430

执行计划的估计可以参考：

  1. Selinger 的 System R 优化器
  2. Graefe Goetz 的 Cascades/Volcano Planner

我感觉上面 15-721 的 slide 写的很详细，目测 noisepage 参考 Columbia 抄了个 Cascade Planner。

关于连接顺序的，基本是个 DP。不过复杂度很高，基本是 $O(3^n)$, Selinger 那篇采用了 启发式 做一些优化，比如：

  1. outer join 最后 Plan
  2. Selection 先下推 （这个在一些 case，比如 A Join B, 选择在 B 的字段，且 JOIN 可以走索引的场景下，工作的不是很好）
  3. Projection 先下推

然后有一些 interesting order 或者 physical properties 的方式来施加一些限制。

Cascades/Volcano 框架则有下列的思想：

  1. 有一些被称为物理等价规则(physical equivalence rule) 的规则，来完成 transform。通常这些规则一般都是原子的，即不能被别的规则组合出来
  2. 这些规则是和代价估计结合在一起的
  3. memorization 来存储最优的形式
  4. 保存一些子结构

有一个很重要的东西是 Join Order 的选择，其实是这样的：

  1. 表多直接遗传算法了，比如 PG 那种，超过 12个表直接遗传算法
  2. 传统的 Selinger 那篇文章，只考虑了 left deep tree。有一些复杂的算法会考虑 bushy tree，比如 dpccp

有一个重要的话题是子查询的优化，可以把一些 EXIST 之类的改成 Semijoin，不过这个规则有点啰嗦，PG 有一块就是处理子查询，我看的人一愣一愣的…TUM 有一篇处理任意子查询的论文，这里有个二手博客：https://zhuanlan.zhihu.com/p/60380557

有一个比较重要的部分是物化视图，随着最近 OLAP 系统的火热，物化视图越来越热门。不过老大难的问题是物化视图的更新，最新的参考 Google 的 Napa 系统。老大难的问题是物化视图的选择（类似索引选择）和更新（实时性 — 写性能 — 成本），Napa 用一个 ts 来让你自己选。我们考虑下面的更新：

  1. JOIN: 相当于单条记录 Join 另一张表，然后增加/删除记录
  2. Selection/Projection: Selection 可能好处理一些，直接区间操作就行；Projection 可能要记录数据的来源/counting，在其上操作
  3. Agg: count/sum/avg 这些比较好处理，min/max 可能需要在有序集合上处理。维护 min/max 的插入很简单，但是要在上面处理删除是很难得。

还有一些 advance 的内容，15-721 也有列，包括：

  1. top-K 优化
  2. adaptive 的查询处理
  3. 参数化的查询优化
  4. 共享扫描、多查询优化

Ep17 事务

事务有着 ACID 的概念，这里我看到过介绍的最好的是 DDIA 那本书：

  1. A: 事务本身多个操作是可以原子性 abort 的
  2. C: 对外的状态满足某些一致性约束
  3. I: 可见性之类的东西受到约束
  4. D: 提交、掉电之后还在

串行化是假设事务一个接一个执行的情况，这种情况叫「串行化」。而并发控制组件（concurrency-control）会控制事务的访问。对于逻辑上等同于串行化的调度，成为「冲突可串行化」。同时，通过事务的读写关系，能定义事务之间的偏序关系。

这里（ https://zhuanlan.zhihu.com/p/293533311）介绍了一种用图描绘冲突的方式，我觉得是一种相当好的定义方式。

这里调度还要考虑「可恢复（reconverable）」和「无级联调度（cascadeless）」:

  1. 可恢复调度指的是，A depends on B, A commit 了, B 没有 commit, 那么可能 B abort 了，A 就没法恢复了。
  2. A->B->C，C abort 了，那 B/A 需要级联 abort。OCC 中可能遇到这种情况，S2PL 应该不会。

然后这里介绍了一下隔离级别，可以参考我之前发的那玩意。隔离级别可以用 锁、ts、MVCC 或者组合来实现，这些概念其实是可以杂糅在一起的，具体还是看具体实现。

Ep18 并发控制

这节感觉是有点难度的，讨论了传统的各种并发控制，和一些杂项。然后讨论了一下 Online DDL 之类的。

协议部分见：

  1. https://zhuanlan.zhihu.com/p/294657612
  2. https://zhuanlan.zhihu.com/p/298576970

然后 Online DDL 基本是 快照读 + 排序 + 追增量。Percolator + F1 是在写的时候做了状态兼容，把追增量这部替换掉了，其实是差不多的。

Ep19 恢复系统

见：https://zhuanlan.zhihu.com/p/397469987