CMU 15-445 数据库系统 课程笔记

发表于 分类于 ， 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

Fall 的课程是 Andy Pavlo 大佬开的

#Lecture 1: 背景

  • DB vs DBMS
  • 平面文件数据库 vs 关系型数据库
  • DML: 过程式 vs 声明式(SQL)
  • 关系代数: Select Projection Union Intersection Difference Product Join Observation

#Lecture 2: SQL

  • 关系型语言

  • SQL标准 历史

  • Join

  • 聚合函数

  • 字符串操作: 大小写敏感 单引号 模式匹配

  • 日期和时间

  • 输出重定向

  • 输出控制: ASC DESC ORDER BY LIMIT

  • 嵌套子查询:

    SELECT in SELECT

    SELECT in FROM

    SELECT in WHERE

    通常难以优化

    输出处理: ALL ANY IN EXISTS

  • 窗口函数: OVER ORDER BY

  • 公用表表达式(CTE): WITH 临时表, WITH RECURSIVE

#Lecture 3: 存储 Part 1

#易失性设备

一般支持高速随机按字节访问

通常叫memory

#非易失性设备

一般支持按块/页存取

通常顺序存取更快

通常叫disk

#持久化内存 / 非易失性内存

用的少 不讲

#NVMe SSDs

仍然属于disk

#面向硬盘的DBMS

Buffer Pool: 把需要用到的数据页从硬盘搬到内存上

能否利用OS的mmap()？不好，难以控制OS什么时候刷盘，可以用的：madvise(), mlock(), msync()

Storage Manager: 管理硬盘上存储的文件，记录文件包含的页，文件剩余的存储空间等

#页

  • 硬件页: 4K 可以保证原子写
  • OS页：4K
  • 数据库页：1-16K

#页堆

堆文件组织是一种组织页的方式。包括一个堆文件，其中包含无序的页集合。

具体有两种组织方式：

  1. 链表：每个页指向下一个页，需要O(n)遍历，效率低
  2. 页目录：维护特殊的页记录每个数据页的信息

#页结构

  • 页大小
  • 校验码
  • 版本
  • 事务可见性
  • 自包含

两种页内数据组织方式：

  1. Slotted-Page

    现在大多数DBMS使用的

    每个slot存一个元组

    头部保存slot索引，元组从后往前增长

  2. Log-Structured

#元组结构

元组是细粒度的数据，字节序列

  • 元组头
  • 元组数据
  • UID
  • 逆正规化元组数据

#Lecture 4: 存储 Part 2

#Log-Structured

Slotted-Page的问题：

  • 内碎片：删除元组产生一个空洞
  • 写放大：需要读写整个块

Log-Structured 的好处：

  • 日志保存的是对数据库的操作 (put, delete)
  • 读记录的时候，DMBS从新到旧扫描日志文件，重建元组
  • 写很快，读可能会慢，已经写过的页是不可变的，减小随机IO
  • …

#数据表示

  • 整数，浮点数：INTEGER，BIGINT，SMALLINT，TINYINT，FLOAT，REAL 按照IEEE-754标准，与C++类型一致
  • 定点数：NUMERIC，DECIMAL，存储方式类似字符串
  • 变长数据：VARCHAR，VARBINARY，TEXT，BLOB
  • 日期和时间：TIME，DATE，TIMESTAMP

#Lecture 5: 存储模型 & 压缩

#数据库的Workload

  • OLTP
  • OLAP
  • HTAP

#存储模型

  • NSM n元存储模型
    • …
  • DSM 分解存储模型
    • …
  • PAX 分区字段
    • …

#数据库压缩

  • 真实世界的数据都是高可压缩的
  • 元组的字段之间有很强的关联性

压缩的要求

  • 压缩完最好是固定长度
  • lazy解压
  • 必须是无损压缩

压缩粒度

  • 块级别
  • 元组级别
  • 字段级别
  • 列级别

#简易压缩

#列式压缩

  • 游程编码
  • 位编码
  • …

#Lecture 6: 缓冲池

Project 1内容，略

#OS 页缓存

大多数DBMS绕过OS的页缓存（通过直接IO），Postgres除外

#磁盘IO调度

  • Sequencial vs. Random I/O
  • Critical Path Task vs. Background Task
  • Table vs. Index vs. Log vs. Ephemeral Data
  • Transaction Information
  • User-based SLAs

#Lecture 7: 哈希表

数据结构课几乎都学过，略

XXHash3最nb

哈希表 = 哈希函数 + 哈希策略

哈希策略：解决哈希冲突的方法

静态哈希策略

  • 线性扫描哈希
  • Cuckoo哈希

动态哈希策略

  • 链式哈希
  • 可拓展哈希
  • 线性哈希

#Lecture 8: 树索引

数据结构课几乎都学过，略

#Lecture 9: 索引并发控制

锁，OS课几乎都学过，略

#Lecture 10: 排序 & 聚合算法

#查询计划

DBMS 会首先把SQL编译成查询计划，编译的目标是最小化I/O。

#排序

关系模型没有定义数据元组保存的顺序，当执行 ORDER BY, GROUP BY, JOIN, DISTINCT 运算符的时候，可能需要先对数据排序。对于小数据直接在内存中排序，大量数据就需要用到外排序。

外排序的标准算法是使用归并排序。

  • 两路归并
  • K路归并

优化思路：

  • 双倍缓冲优化
  • 比较优化
  • 用B+树索引

另外，当查询同时包含了 ORDER BY 和 LIMIT 时，就等价于查询数据的 Top-N 元素，可以用另外的算法。

#聚合

聚合运算将一个或多个元组合并成单个标量值。运算符包括 GROUP BY，

#Lecture 11: 连接算法

The goal of a good database design is to minimize the amount of information repetition.

TODO

#Lecture 12 & 13: 查询执行

TODO

#Lecture 14: 查询计划 & 优化