JZTXT

总结

发布时间 2023-09-06 18:01:19作者: Angelia-Wang

Lecture#01 关系模型与关系代数

数据库：相关联数据的集合。存储在 CSV 文件中，不同记录用新行分隔，记录的不同属性用逗号分隔。

  • 缺点：应用程序中编写代码解析文件会出现问题：数据完整性、遍历查记录慢、不同语言的应用程序解析文件需重复造轮子、多线程并发、数据安全问题。—— DBMS 产生

DBMS：相关联数据集合 + 操作程序。

  • 优点：可被多种应用程序复用，无需重复造轮子（程序无需关心底层实现，就能对数据进行存储和分析）
  • 缺点：早期 DBMS 的逻辑层（数据库的实体和属性）和物理（存储这些实体和属性的数据结构）层紧密耦合。人们每次想要更改物理层时都要重写代码来获取逻辑层所需数据。 —— Ted Codd 提出关系模型

关系模型：以关系存储数据库；通过高级语言访问数据；逻辑层和物理层解耦。

  • 关系模型三要素：数据结构、数据完整性约束、操作

数据模型 (model) ? 模式 (schema) ：数据模型描述数据库如何组织数据 (Relational、Key/Value、Graph、Document、Column-family 等NoSQL、层次结构、网状结构)；模式指在给定的数据模型下，对特定数据集合的描述。

数据库操纵语言 DML：过程化 DML —— 关系代数；声明化 DML —— SQL。

PS: 关系代数基于集合 (无序，无重复)。SQL基于包 (无序，允许重复)。

使用底层写法，会导致数据库物理层与逻辑层紧密耦合，则一旦物理层做出更改，就需重写代码来获取逻辑层所需数据。通过关系代数也需考虑查询优化问题（先选择后连接...）。如果通过SQL我们就只需考虑需要的数据，而不用说明如何获取它，随着时间推移，数据库可能产生改变，它能不断适应并改进。

image-20210805144324222

Lecture#02 Advanced SQL

SQL 的命令组成：

  1. 数据操作语言（DML）：选择 select、插入 insert、更新 update、删除 delete（操作数据）。
  2. 数据定义语言（DDL）：模式定义（创建表以存储数据）。
  3. 数据控制语言（DCL）：安全性授权、访问控制。
  4. 其他：如何定义视图，如何定义完整性约束、参照约束，事务。

聚合函数：AVG()、MIN()、MAX()、SUM()、 COUNT()

  • group by 子句中给出的一个/多个属性构造分组，属性上取值都相同的元组被分为一组。(不使用 group by 则将整个结果视作一个分组)
  • having 子句可设置分组的限定条件。
  • select 子句和 having 子句中，只能有被聚集的属性和出现在 group by 子句中的属性。

字符串操作函数：

  • upper(s) 将字符串 s 转换为大写；lower(s) 将字符串 s 转换为小写
  • trim(s) 去除字符串 s 后面的空格
  • substring(s,first,last) 选取 s 的子串
  • 使用 like 操作符实现字符串的模式匹配，使用 escape 关键词定义转义字符；使用 not like 比较运算符搜寻不匹配项。
    • 百分号（%）：匹配任意子串
    • 下划线（_）：匹配任意一个字符
  • 标准 SQL 使用 || 拼接字符串。SQL Server 下要用 + ；MySQL 下只能通过concat()函数。
    MySQL 中若在两个字符串间不放任何东西，它们也会连接在一起（这点其他数据库系统都不行）。‘An’ ‘Dy’ ‘Pavlo’

日期/时间操作

返回当前时间戳 Postgres MySQL SQLite
NOW()函数 √ √ ×
CURRENT_TIMESTAMP() 函数 × √ ×
CURRENT_TIMESTAMP 关键字 √ √ √

输出重定向

  • 将查询输出到新表：
    SELECT col1 INTO table2 FROM table1
    CREATE TABLE table2 (select col1 FROM table1)

  • 将查询输出到旧表：

    INSERT INTO table2 (select col1 FROM table1)

输出控制：

  • ORDER BY <column*> [ASC|DESC]：排序（默认升序 ASC）
  • LIMIT [offset count]：LIMIT 表示要取的tuple数目，offset 表示要跳过的tuple数目。
  • 除非使用带有 LIMIT 的 ORDER BY 子句，否则每次调用 LIMIT 结果中的元组都可能不同。

嵌套查询

  • 外部查询的作用域包含在内部查询中（即内部查询可引用外部查询的属性，但外部不能引用内部）
  • 内部查询可出现在查询的任何地方（select，from，where）
  • 涉及操作符：
    ALL：必须满足子查询中所有行的表达式。
    ANY：子查询中至少有一行必须满足表达式。
    IN：等价于= ANY()。
    EXISTS：至少返回一行。

❗️ 能否将内部循环当做一种嵌套循环看待？

答：可以，但并非如此。for循环实际上有某种类似于顺序的概念，而所有的这些操作符（例如，IN，EXISTS，ANY）所试图表达的是在内部查询中的是否存在有满足条件的任何tuple，你并不会真的每个都要去遍历一遍。如果你将外部查询当做一个for循环考虑，因为你正在遍历每个tuple，但是服务器对内部查询的评估始终是在一个 bag 或者 set 的层面进行的。

Window 函数：跨元组执行“移动”计算。类似于聚合函数，对一个tuple子集进行函数计算，将它们聚合为一个结果，可以增量方式或移动方式进行此操作。但它仍然返回原始元组，后跟用 window 函数计算出的值。 如果采用聚合函数，则只能看到被聚集的属性和出现在 group by 子句中的属性，无法看到原来完整的 tuple。

image-20210904150318736
  • 先执行整个查询，再使用 window 函数对这些结果进行处理，然后将之放入查询结果中。
  • 函数可以是 聚合函数，如MIN()、MAX()、AVG()、COUNT()、SUM()；也可以是 特殊的 window 函数：
    • ROW_NUMBER()：当前行的行号（输出顺序）
    • RANK()：当前行的顺序位置（排序后的排名）。要配合 OVER 中的 ORDER BY 使用，否则不能正常排序。
    • ROW_NUMBER() 输出的行号代表的是出现在输出中的顺序，RANK() 则是分组排序后的组内顺序。即：DBMS在 window 函数排序后计算 RANK，排序前计算 ROW_NUMBER。
  • 分组：OVER 子句指定在计算 window 函数时如何将元组分组。
    • OVER 中包含 PARTION BY 指定分组。
    • OVER 中包含 ORDER BY 可对每个组中的条目进行排序。（可确定结果的顺序）

CTE：可视为视为仅用于一个查询的临时表。

image-20210904162100091
  • 基本工作原理：引入 WITH 子句，WITH 子句会在你执行正常的查询之前先一步执行。
  • CTE ? 嵌套查询：可在 CTE 中进行递归，但在嵌套查询中不能。

Lecture#03 Database Storage1

易失性存储设备：断电后数据丢失，随机访问，字节寻址。? 内存 (DRAM)

非易失性存储设备：断电后数据不丢失，顺序访问，块/页寻址。? 磁盘 (固态 SSD, 机械硬盘 HDD)

面向磁盘的 DBMS：数据库位于磁盘，DBMS 组件 Buffer Pool 管理数据在非易失性存储和易失性存储之间的移动。

image-20210905114702783

数据库文件中的数据被组织为页，第一个页是目录页。为了对数据进行操作，DBMS 需要将数据存入内存。它通过一个缓冲池来管理磁盘和内存之间的来回移动。

DBMS 也有一个执行引擎来执行查询。执行引擎将向缓冲池请求一个特定的页面，缓冲池将负责将该页面放到内存中，并向执行引擎提供一个指向内存中的页面的指针。缓冲池管理器将确保在执行引擎对该内存进行操作时页面在那里。

DBMS ? OS：

DBMS 对 page 的移动和 OS 中的虚拟内存很像，OS 中使用 mmap 内存映射文件 将文件的内容映射到进程的地址空间，进程在地址空间上读取，操作系统负责在磁盘和内存之间来回移动页面。如果 mmap 遇到 page fault，该进程将会被阻塞，等待操作系统将 page 从磁盘 load 到内存。

若数据库只需读取数据，使用 mmap 是可行的，但是 DBMS 还需进行写操作，而 OS 不知道哪些 page 需要在其他 page 执行前从内存刷到磁盘上的，这与日志与并发控制的实现有关。因此出于正确性和性能的考虑，不建议在DBMS中使用mmap。尽管使用 mmap 系统将具有操作系统可以提供的功能，但让 DBMS 实现这些过程本身可以提供更好的控制和性能（以正确的顺序将脏页刷到磁盘，更好的预取、buffer 替换、进程/线程调度策略）。

数据库存储，主要问题：

  1. 如何利用磁盘上的文件表示数据库
    （如何在一系列 page 上组织数据库，即如何将这些 page 存储在文件中；page 中数据如何存储）
  2. 如何管理内存预计在磁盘间来回移动数据

DBMS 将数据库以文件的形式存储在磁盘上。DBMS的 存储管理器 负责维护磁盘上的数据库文件。它将文件组织为 page 的集合。它还可以跟踪 page 上的所有读取/写入操作，以及页面中还有多少空闲空间。

一个 page 是一个固定大小的 block，每个 page 都有一个唯一的标识符 page ID。如果数据库是单个文件，那么 page ID 可以只是文件偏移量。大多数 DBMS 都有一个间接层，来将 page ID 映射到物理位置（文件路径和偏移量）。

不同的DBMS会用不同的方法管理磁盘文件中的 pages（堆文件、顺序文件、hash文件等）

heap 文件是一个无序的 page 集合。表示 heap 文件的方式：

  • Linked List：堆文件的 header 中，链表有两个指针，分别指向空闲页列表和数据页列表。若要查找指定 page，需对数据页列表进行顺序扫描。（基本没人用）
  • page directory：DBMS 维护一个特殊页面 page directory，用于跟踪数据页的位置（维护 page ID 和 page 所处位置的映射）和每个页的空闲空间数。

page 中数据的存储方式：

  • slotted-pages：page 将 slot 映射到 offset（偏移量）。
    • 头部header跟踪 使用的slot的数量、最后使用的slot的起始位置的偏移量、slot数组，slot数组跟踪每个元组的起始位置（将一个特定的slot映射到page上的某个偏移量上）。这样一个 tuple 就可由一个page id和slot id来唯一定位。
    • 要添加一个元组，从前往后对 slot 数组进行填充，而元组的数据从后往前填充。当 slot 数组和元组数据相遇时，该页被认为已满。
    • 间接层避免了物理存储位置更新信息传播到系统的其他上层部分。根据 page ID 就能在 page 目录中找到此 page 保存的位置，而根据 slot 就能找到 tuple 的相对位置。更新物理存储无需更新其他任何东西。
  • log-structured：DBMS只存储日志记录，而不存储 tuples。
    • 为了读取记录，DBMS从后往前扫描日志文件并“重新创建”元组。
    • 写快，读慢。可定期压缩日志，但会导致写放大（一遍又一遍地重写相同的数据）。

Tuple 本质上是一个字节序列（字节数组）。一个 tuple 可由 page id + slot/offset 唯一定位。

Lecture#04 Database Storage2

元组中可存储的五种主要类型：整数、可变精度数、定点精度数、可变长度值和日期/时间。

workload：

  • OLTP：在线事务处理。特征：读写简单，写比读多，通常是读/写一小部分数据，并且事务可保证数据的一致性。
  • OLAP：在线分析处理。特征：查询复杂，需要读取大批量数据进行统计分析。
  • HTAP：混合事务分析处理。将 OLTP 与 OLAP 相结合。

不同 workload 下数据库的存储方式：

  1. 行存储 是最常见、符合直观思维的存储模式，将不同属性的数据一行行的组织起来，并且存储到 page 当中。更适合 OLTP 数据库。

    • 方便快速插入/更新/删除和点查询，但不适合扫描表的大部分或属性的子集。
    • 数据库组织形式：堆组织表、索引组织表。

  2. 列存储 将表中一个列的数据存到 page 中。由于具有相同属性的数据，会更可能有类似的特征，所以这样的数据组织方式更适合压缩，节省存储空间。更适合 OLAP 数据库。

    • 方便大批量扫描数据，支持更好的压缩，但插入/更新/删除和点查询速度都很慢。
    • 数据库组织形式：固定长度偏移 (更常用)、嵌入的 tuple id (开销很大，没人用)。

Lecture#05 Buffer Pool

DBMS 管理数据在内存和磁盘间的移动，需考虑 page 的访问在时间和空间上的局部性特征，以提高 I/O 效率。（一次被访问到的 page 加载到内存之后，有可能被再次访问，这样可以避免频繁从磁盘中加载 page）

  • 空间控制策略：将 pages 写到磁盘的哪个位置，使常一起使用的 pages 能离得更近。
  • 时间控制策略：何时将 pages 读入内存/写回磁盘，使读写的次数最小。

DBMS 启动时向 OS 申请一块共享内存区域 —— Buffer Pool，用于对磁盘上的 page 进行缓存，尽量减少磁盘 IO，提升 DBMS 性能。该区域被划分为多个与 page 大小相同的小块，称为 frame，用于缓存 page。此外，还维护一个哈希表 page table，存储 page id 到 frame 的映射，以及一些 page 的元数据信息，如 page 是否为脏页，page 的引用计数 pin count 等。若请求的 page 不在 page table 中，DBMS 会先申请一个 latch，锁住该 entry，然后从 disk 中读取相关 page 到 Buffer Pool，释放 latch。

page table 的访问，一般要保证并发安全，因为在多线程环境下，对于同一个内存中 frame 的读写不能同时进行。

DBMS 如何为不同的查询分配缓冲池内存，涉及Allocation Policies：

  • 全局策略：同时考虑所有查询和事务来分配内存。
  • 局部策略：为单个查询/事务分配内存frames时不考虑其它查询的情况。可以让特定的事务表现更好，当然全局上可能会有糟糕的表现。
  • 大多数 DBMS 都兼顾全局和局部信息来进行分配。

当 Buffer Pool 空间不足时，读入新的 pages 必然需要 DBMS 从已经在 Buffer Pool 中的 pages 选择一些移除，这个选择就由 Buffer Replacement Policies 负责完成。具体算法有：LRU、Clock。二者都存在 sequential flooding （顺序溢出）问题，可采用 LRU-K、Localization (局部策略)、Priority Hints (优先级提示) 解决。

  • 顺序溢出：大量的顺序扫描 (sequential scan) 会使 buffer pool 被只读了一次之后再也不会读取的 page 污染。从而导致最近被访问的 page 实际上却是最不可能需要的 page。
  • 局部策略：使用多个 buffer 池，让每个查询本地化，DBMS 针对每个查询做出移除去 page 的限制。
  • 优先级提示：记录每个 page 在查询执行过程中的上下文信息，根据这些信息判断该 page 是否重要。

移除一个 dirty page 的成本要高于移除一般 page，有的 DBMS 使用 Background Writing (后台写) 的方式来处理。它们定期扫描 page table，发现 dirty page 就写入 disk，在 Replacement 发生时就无需考虑脏数据带来的问题。

  • ❗️ 在将 dirty page 写入 disk 之前，要确保该 dirty page 对应的修改操作写入日志——WAL

实际生产中有很多对 Buffer Pool 的优化方法：

  • Multiple Buffer Pools (复数缓存池)：在不同维度上维护多个 Buffer Pool，相同的 page hash 到相同的实例上。? 每个 database / 每种 page 类型，分配一个 Buffer Pool 等。
  • Pre-fetching (预取)：对于顺序扫描或者索引扫描，可能会读一大段连续的 page，因此可一次性把许多连续的 page 预存在缓存池中。
  • Scan Sharing (扫描共享)：多个查询存在数据共用时，可共用 cursor。
    • ? result caching (结果缓存)：计算出某些结果并将之缓存起来，再遇上相同的查询时直接使用，而不需要重新执行查询。结果缓存中，查询必须一样；扫描共享中，查询不一定要一样。
  • Buffer Pool Bypass (跳过 Buffer Pool)：大量数据的顺序扫描会导致 Buffer Pool 的污染，因此这种查询出现时，可为它单独分配一块局部内存，隔离它对 Buffer Pool 的影响。查询完成后，就丢弃这些 page。

page table ? page directory：

  • page directory：维护 pageID 到磁盘物理位置（文件路径+偏移量）的映射。所有改变都需持久化到磁盘，以保证 DBMS 重启时能找到。
  • page table：Buffer Pool 中提到额外的 indirection 层，维护 pageID 到内存中的位置（frame）的映射。是个在内存中的 hash表结构，无需存储在磁盘上（无需保证持久化，丢失了重新建立一个就好，但要线程安全）。

lock ? latch：

  • lock：保护 数据库逻辑内容 (例如元组、表、数据库)不受其他事务的影响。在事务持续期间保持，能够回滚更改。

  • latches：保护 DBMS内部数据结构 的关键部分不受其他线程的影响。操作期间保持，不能够回滚更改。

Lecture#06 HashTables

Buffer Pool Manager 之上的 Access Methods，是一种用于对数据库数据进行读/写的方式（数据库存放在磁盘的 page 中）

本章讨论数据系统内部所维护的数据结构—— hash tables、trees。

hash table 由二部分组成：

  1. Hash Function：如何将一个大的 key 映射到一个相对小范围的 integer 值。要权衡 hash 速度与冲突率。
  2. Hash Scheme：如何处理 hash 冲突。要权衡使用的内存空间与处理冲突时的额外操作。

常用的 Hash 函数中 XXHash3 性能最好。

hash scheme 有 static hashing scheme、dynamic hashing scheme。

静态哈希方案：哈希表的大小固定。 要求 DBMS 知道它想要存储的元素的数量。否则若需要增大表的大小，将重建 hash 表。扩容代价非常高 (将原本的值全复制获取后，扩容两倍)。

为尽量避免 hash 冲突，要求 hash 的槽数 (slots) 是预期元素数的两倍 slots = 2 * keys。

  • Linear Probe Hashing：线性探查哈希。
    • 插入数据时，若 hash(key) 映射的 slot 位置无数据，就直接插入 key|value 键值对；否则就线性向后探查，直到找到一个能插入数据的空 slot 为止。
    • 删除数据时，不能直接删除 key，可以 (1) 设置标记「Tombstone 墓碑」(2) 移动数据。【常用1方法】
  • Robin Hood Hashing：线性探查法的扩展。会对整个 hash table 进行平衡，试图让每个 key 尽可能靠近它原本的位置（减少它到在 hash 表中的最佳位置 hash(key) 的距离）。
    • 插入时，若要插入的键比此处原本的键更 poor（到最佳位置的距离更远），则窃取该 slot。原本的键必须重新插入到表中。因此会使写入或插入的代价更高（原本一次的写入操作变成了多次）
  • Cuckoo Hashing：维护多个具有不同 hash 函数的表。hash 函数是相同的算法 (例如，XXHash, CityHash); 它们通过使用不同的 seed 值为同一个 key 生成不同的 hash 值。(实践中，一般使用两个 hash 表，超过三个没必要)
    • 插入时，挑选一个有空闲 slot 的表；若没有表有空闲 slot，则从中随机选择一个 slot 窃取，对该 slot 原本的元素重新 hash，为之找到一个新的位置。【需标记是否已经访问过某个 slot 以发现循环】

Robin 和 Cukoo 都是线性探查法的扩展。实际表现中，大多数情况下线性探查法还是强无敌。 Robin 可以显著降低探查长度的方差，Cuckoo 查找始终 O(1)。Robin 和 Cuckoo 的插入代价很大。

动态哈希方案：能根据需要调整 hash 表的大小，而不需要重建整个 hash 表。

  • Chained Hashing：为 hash 表中的每个 slot 维护一个 bucket 的 linked list。每个 slot 不是存储元素，而是存储一个指向 bucket 组成链表的指针（引用）。
    • 可将 bucket 当做 page，在堆组织文件中，当某个 page 满了就分配新 page，并将它们链接在一起，通过 page id 指明如何遍历。
    • 可能退化为顺序扫描。删除和插入操作很简单，因为修改的是 bucket 而不是 slot array。可以做到近乎无限的扩容，也很容易实现线程安全，我们只需要对每个 slot/bucket 加上 latch 就好。
  • Extendible Hashing：改进的链列哈希，对 overflow 的 bucket 进行拆分，而不是让链永远增长。这种方法允许 hash 表中的多个 slot 位置指向同一个 bucket chain。
    • 将 key 计算哈希值后转为二进制，维护 global counter 记录定位到 bucket 指针数组 (slot array)，需要取 key 的二进制的多少位；每个 bucket 维护 local counter 记录定位到该 bucket，需要取 key 的二进制的多少位。
    • 当存储 bucket 满时，DBMS 将 bucket 拆分并重新洗牌它的元素。如果拆分 bucket 的 local counter < global counter，则新 bucket 将被添加到现有的 slot 数组中。否则，DBMS 将 slot 数组的大小翻倍以容纳新的 bucket，并增加 global counter。
    • 缺点：尽管调整指针数组的代价并不高，但调整时若 slot 数组大小需翻倍，则要对整个 slot 数组上 latch，这会成为一种性能的瓶颈。
  • Linear Hashing：不是在 bucket overflow 时立即拆分 bucket，而是维护一个 split pointer 来跟踪下一个要拆分的 bucket。不管这个指针是否指向溢出的 bucket，DBMS 总是分裂。
    • 假定最初 split pointer 指向第一个 bucket。任何 bucket overflow 时，在 pointer 位置添加一个新的 slot 位条目拆分 bucket，并创建一个新的 hash 函数（使用的是相同的 hash 函数，只是使用了不同的 seed），对该 bucket 中的所有 key 采用新的 hash 函数进行拆分。溢出桶的溢出 kv 会放在溢出页，直到该 bucket 分裂。
    • 后续查找中，如果 hash 值映射到之前被 pointer 指向的 slot（桶号小于 split pointer），再应用新的 hash 函数得到 value。
    • 当 pointer 到达最后一个 slot 时，删除原来的 hash 函数，并用新的 hash 函数替换它。
    • 若进行删除操作，删除到需要缩减合并 bucket（有bucket为空）时，split pointer 会往回移动，但这在实战中很棘手。

若想在哈希表中记录相同的 key 的不同 value「non-unique keys」，有 2 种方法：

  1. 将 key 的值存储在单独的存储区域：每个 key 的 slot 指向一个单独的链表，链表上保存的 value 对应的都是同一 key
  2. 在 hash 表中存储含冗余 key 的元素【更常用】

hash table 是一个高效的数据结构，大多时候能够在 O(1) 的情况下插入和查询数据，在数据库系统中，有很多地方都使用到了哈希表，例如前面提到的 page table，page directory，以及执行 sql 查询时一些用于 join 的临时数据结构。

但是哈希表的应用场景也有限，因为它存储的所有 key 都是无序的，这样虽然适合点查（精准匹配 key 的查找），但是无法进行范围扫描（通过关于 key 的部分条件查找，比如找出小于我给出的 key 的所有 key），在更加通用的场景下，数据库中的表索引使用最广泛的还是 B+ 树。

Lecture#07 Tree Indexes1

Hash Table 可作为表的 Hash 索引，但只适用于点查询，对于范围查询，更常用 B+Tree。

B+Tree：多（M）路平衡搜索树。一个结点的 degree 为 M，则最多可以有 M 个 pointer（向下的路径），M-1 个 key。

  • 完美平衡：每个叶结点都有相同的深度 ?(????) 。每次修改数据后，都会调整。
  • 除根节点外的每个内部结点至少是半满的（(M - 1)/2 <= num of keys <= M−1，M 是该结点出来的路径数）。
  • 每个有 k 个 key 的中间结点都有 k+1 个非空的孩子结点。

每个B+树的结点都是一组 key/value 对的数组：

  • 每个结点上的数组（几乎）按 key 排序。
  • key：来源于我们要建立索引的属性的值
  • value：根据是 Inner Node（非叶子节点）或者 Leaf Node（叶子结点）有不同的选择。
    • inner node 的 value 是指向其他 node 的指针。
    • leaf node 的 value 是具体的数据：① tuple 的 record id；② tuple 本身【聚簇索引】

B树 ? B+树

  • B树的 key 不允许重复且数据可存储在任何结点；B+树中的 key 可以重复，但数据只能存储在叶子结点中。
  • 实际上B树的性能是高于B+树的（因为 key 不允许重复，所以对空间的利用率更高），但是却很少得到使用，这是因为B+树在多线程下的表现好于B树。比如，B树中一个 inner node 进行了修改，需要将这个修改向下和向上进行传播，则要在这两个方向上都加 latch，但B+树中只对leaf node进行修改，则只需要向上传播这个修改。

B树和B+树的插入、删除图文详解