Pilot

DBMS

A database is an organized collection of inter-related data that models some aspect of the real-world.

A DBMS is a software that allows applications to store and analyze information in a database.

不要混淆“数据库(database)”和“数据库管理系统(database management system, DBMS)”。PostgreSQL, Oracle, SQLite, Snowflake这些都是DBMS。

关系模型与关系代数

关系模型基于关系定义数据库抽象，解耦合逻辑层与物理层。

将数据库存储在简单的数据结构(关系)中。
通过高级语言访问数据，DBMS找出最佳执行策略。
物理存储留给DBMS实现。

从数据库中存储和检索信息通常有两种语言：

Procedural：查询命令需要指定 DBMS 执行时的具体查询策略（关系代数）
Non-Procedural（Declarative）：只需要指定想要查询哪些数据，无需关心具体查询实现（关系演算）

关系代数是一种Procedural语言，因为它定义了如何计算查询的high-level步骤（比如先做join还是projection，这对于查询优化很重要）

现代SQL

SQL是关系数据库的Declarative的查询语言。当前SQL的标准是SQL-2016，目前大部分DBMS至少支持SQL-92标准。

窗口函数

窗口函数在一组相关的元组之间执行“滑动”计算。类似于聚合，但元组不是分组合并到单个输出元组，而是每个元组新增了一列窗口函数的计算结果。除了普通聚合函数外，还有些特殊的窗口函数，如ROW_NUMBER()和RANK()。

1
2
3
4
5
6
--  Find the student with the second highest grade for each course.
SELECT * FROM (
  SELECT *, RANK() OVER (PARTITION BY cid
    ORDER BY grade ASC) AS rank_
  FROM enrolled) AS ranking
WHERE ranking.rank_ = 2;

CTE

CTE可用作复杂查询时的临时中间表。

1
2
3
4
WITH cteName (col1, col2) AS (
    SELECT 1, 2
)
SELECT col1 + col2 FROM cteName

Recursive CTE可以在SQL查询中实现递归。

1
2
3
4
5
6
7
8
--  Print the sequence of numbers from 1 to 10.
WITH RECURSIVE cteSource (counter) AS (
    (SELECT 1)
    UNION ALL
    (SELECT counter + 1 FROM cteSource
      WHERE counter < 10)
)
SELECT * FROM cteSource;

存储

主要讨论“面向磁盘”的DBMS体系结构，该体系结构假设数据库的主要存储位置在non-volatile磁盘(SSD, HDD)上。

面向磁盘的DBMS

disk-oriented-dbms

数据库全部在磁盘上，数据库文件中的数据被组织成页，第一页是目录页。为了对数据进行操作，DBMS需要将数据放入内存中。它通过缓冲池（Buffer Pool）来管理数据在磁盘和内存之间的来回移动。执行引擎将向缓冲池请求特定的页面，缓冲池将负责将该页放入内存，并向执行引擎提供内存中该页的指针。

为什么不用mmap

简单来说，不用 mmap 是为了更好的控制和性能。如果 mmap 遇到 page fault，进程将会被阻塞。mmap 不好做异常处理，也存在事务安全问题。 DBMS 比 OS 拥有更多、更充分的知识来决定数据移动的时机和数量，具体包括：

将 dirty pages 按正确地顺序写到磁盘
根据具体情况预获取数据
定制化缓存置换策略
线程/进程调度

更详细的讨论可以看这篇论文 Are You Sure You Want to Use MMAP in Your Database Management System?

文件存储

DBMS的存储管理器负责管理数据库的文件。它将文件表示为page的集合。它还跟踪哪些数据被读和写到了page上，以及这些page有多少可用空间。

Database Pages

OS 的文件系统通常将文件切分成 pages 进行管理，DBMS 也不例外。通常 page 是固定大小的一块数据，每个 page 内部可能存储着 tuples、meta-data、indexes 以及 logs 等。大多数DBMS使用固定大小的page(1-16KB)，以避免支持可变大小page所需的工程开销。

不同 DBMS 管理 pages 的方式不同，主要分为以下几种：

Heap File Organization
Tree File Organization
Sequential/Sorted File Organization (ISAM)
Hashing File Organization

Heap File Organization

Heap file 是一个无序的 pages 集合，pages 管理模块需要记录哪些 pages 已经被使用，哪些尚未被使用。主要有以下两种方法：

Linked List: Header page 持有指向free pages list和data pages list的指针。它必须在数据页列表上进行顺序扫描。
Page Directory: pages 管理模块维护着一些特殊的 pages（directory pages），它们负责记录 data pages 的位置和空闲空间大小。

Page Layout

每个 page 被分为两个部分：header 和 data，header通常包含：page大小, checksum, DBMS版本, 事务可见性, 压缩信息。 data 中记录着真正存储的数据，数据记录的形式主要有:

Tuple-oriented（slotted-pages）：记录数据本身
Log-structured：记录数据的操作日志

Slotted Pages

Tuple-oriented中，最常用的Layout方案是 slotted pages。header 中的 slot array 记录每个 slot 的信息，如大小、位移等。 slotted_page

新增记录时：在 slot array 中新增一条记录，存放该记录的入口地址。slot array 与 data 从 page 的两端向中间生长，二者相遇时，就认为这个 page 已经满了。
删除记录时：假设删除 tuple #3，可以将 slot array 中的第三条记录删除，并将 tuple #4 及其以后的数据都都向后移动，填补 tuple #3 的空位。

Log-Structured

Slotted-Page Design 带来的问题：

Fragmentation：删除tuple会在page中留下碎片。
Useless Disk I/O：由于非易失性存储的block-oriented的性质，需要读取整个块来获取tuple。
Random Disk I/O：磁盘阅读器可能不得不跳到20个不同的地方来更新20个tuples，这可能会非常慢。

log-structured page 只存储更改（PUT, DELETE）的日志记录。因此，增删改的效率很高。为了读取一条记录，DBMS从最新到最旧扫描page并重新创建tuple。为了加快查询效率，通常会对操作日志在记录 id 上建立索引。还需要定期做日志压缩。

Tuple Layout

每个 tuple 被分配一个唯一的记录标识符。最常用的方式：page_id + offset/slot。例如，PostgreSQL使用 CTID (6-bytes)，SQLite使用 ROWID (8-bytes)。 tuple 的元数据包含：

Visibility Info (concurrency control)
Bit Map for NULL values

OLTP & OLAP

OLTP(Online Transaction Processing): 主要处理简单的读写语句，且每个语句都只操作数据库中的一小部分数据
OLAP(Online Analytical Processing): 主要处理复杂的，需要检索大量数据并聚合的操作
HTAP(Hybrid Transaction + Analytical Processing)

Storage Models

行存储：NSM (N-ary Storage Model)：将一个 tuple 的所有 attributes 在 page 中连续存储，适合 OLTP 场景。
- 优点：增删改、查询整条记录较快
- 缺点：不适合对大块的tuples、部分attributes的操作
列存储：DSM (Decomposition Storage Model)：将所有 tuples 的单个 attribute 连续存储，适用于 OLAP 场景。
- 优点：按需查询，减少I/O、有利于数据压缩
- 缺点：点查询、增删改较慢

在列存储的情形下，有两种方法标识tuple：定长offset（每个attribute大小一样）、embedded_tuple_id。

CMU15-445(Fall 2022) 笔记：Pilot

相关文章：